NTIC Sequences and Primes

Section 22.2 Sequences and Primes

Subsection 22.2.1 Primes in sequences

There is an interesting question implicit in the prime races. To legitimize doing the first prime race, we proved that there are infinitely many primes of the forms

$4k+1$ and

$4k+3\text{.}$ However, we then proceeded to do prime races for several other such forms. Is it legitimate to do so?

🔗

The answer is yes, as proved in this major theorem of 1837 that introduced limiting and calculus methods to the study of number theory.

🔗

Theorem 22.2.1. Dirichlet's Theorem on Primes in an Arithmetic Progression.

If $\gcd(a,b)=1\text{,}$ then there are infinitely many primes of the form $ax+b$ for $x$ an integer.

🔗

Proof.

The proof of this theorem is far beyond the level of this text, but [C.4.6] is a standard resource for this.

🔗

That is,

$ax+b$ defines a progression of numbers separated always by

$a\text{,}$ and this theorem says there are infinitely many primes in any such progression that makes sense in terms of relative primeness. It is a weak version of a prime race; it just says that it makes sense to do them, though (as we saw) there is much more information one can glean from them.

xxxxxxxxxx
 
@interact
def _(a=8,b=7,n=100):
    if gcd(a,b)!=1:
        pretty_print(html("Oops!  The progression won't have many primes if"))
        pretty_print(html("$a$ and $b$ share a common factor!"))
    else:
        pretty_print(html("Primes of the form $%sx+%s$ up to $%s$:"%(a,b,n)))
        for x in prime_range(n):
            if x%a==b:
                print(x)

🔗

We have already proved this for

$a=4\text{.}$ It is easy to prove for

$a=2\text{!}$ (See Exercise 22.4.4.)

🔗

It is also possible to prove the theorem for

$b=1\text{,}$ or

$b=-1\text{,}$ without developing much bigger tools. In the article [C.7.1] a lot of factoring and expanding is used, and a much more recent article by Xianzu Lin [C.7.7] is similarly elementary. One can even prove Dirichlet's theorem without Dirichlet's methods for any

$b$ such that

$b^2\equiv 1 (\text{mod }a)\text{,}$ but doing so involves some high-level details about polynomial factorization (see Murty and Thain's paper for details).

🔗

Subsection 22.2.2 Sequences in primes

🔗

We can also look at the opposite question. Instead of considering whether primes exist in a given arithmetic progression, are there arithmetic progressions made of solely of primes?

🔗

Question 22.2.2.

Can you get a (finite) sequence of the form

$\begin{equation*} ak+b,k=0,1,2,3,\ldots n \end{equation*}$

where all entries are prime?

🔗

It's easy to find short arithmetic progressions in the primes. We say such a progression has length

$n+1$ in the above notation.

3, 5, 7 is an arithmetic progression of length 3, where $a=2\text{.}$
41, 47, 53, and 59 is an arithmetic progression of length 4, where $a=6\text{.}$

🔗

Longer ones get harder to find. Can you find a progression of length 5? (This is Exercise 22.4.5; there is a small one where the differences and starting number are both less than 10. See also Exercise 22.4.6.)

xxxxxxxxxx
 
@interact
def _(p = prime_range(200), n=110):
    L = [p,p+n,..p+4*n]
    for z in L:
        if is_prime(z):
            print(z)
        else:
            print(factor(z))
            break

🔗

Fact 22.2.3.

There is such a sequence of length 10 starting at 199, with differences of 210.

🔗

Question 22.2.4.

Can find arbitrarily long such sequences in the primes?

🔗

The answer is yes! This is a theorem of Ben Green and Terry Tao, which was a significant piece of Tao's 2006 Fields Medal (though he probably would have won it even without this, remarkable as it may seem). How might one prove this? That might seem mysterious, so we give the gist of an approach.

🔗

Remember how there seem to be fewer primes the further out we go, even in an arithmetic subsequence (e.g. prime mod 4 or mod 8)? That isn't a coincidence. There is a technical way to measure this:

$\begin{equation*} \lim_{n\to\infty}\frac{\pi(n)}{n}=0\text{.} \end{equation*}$

🔗

This follows from Chebyshev's estimate in Theorem 21.3.4, and is called having zero density. We can try estimating this for

$\pi$ with specific numbers:

$\pi(100)/100 = 1/4=0.25$
$\pi(200)/200=0.23$
$\pi(1000)/1000=0.168\text{,}$ or under 17%.
$\pi(1000000)/1000000\approx 0.0785\text{,}$ or under 8%.

🔗

Now, if you have a collection of numbers which has positive density (i.e. the limit is positive, not zero), it is a theorem from 1974 (by Endre Szemerédi) that you can get arithmetic progressions of arbitrary length in such sets. Sadly, even our data suggests the primes are indeed approaching zero density.

🔗

But Green and Tao managed to show this type of method still works for the primes! You can't get arithmetic progressions in just any old set with zero density; but somehow, although there are not many primes, there are just enough for things to work.

🔗

If you are interested in the current status of really long sequences, see the primerecords.dk website. The first example of length 27 was found recently, on September 23, 2019; evaluate the following cell to see the whole thing.

xxxxxxxxxx
 
difference=81292139*2*3*5*7*11*13*17*19*23
start=224584605939537911
for n in [0..26]:
    print(start+n*difference,is_prime(start+n*difference))

🔗

There are also only ten known 26-length sequences, as of this writing (2020), and there are no known 28-length sequences (though they must exist, by the Green/Tao theorem). They must even obey the following ridiculous bound (published in a followup to the original paper).

🔗

Fact 22.2.5.

A sequence of length $k$ must occur before

$\begin{equation*} 2^{2^{2^{2^{2^{2^{2^{100k}}}}}}} \end{equation*}$

🔗

How do people find such lists? For that, we need a new notation.

🔗

Definition 22.2.6.

For a prime $p\text{,}$ we call the primorial the number

$\begin{equation*} p\#=\prod_{q\leq p,\; q\text{ prime}} q \end{equation*}$

where the “p sharp” or “p hash”¹ denotes $p$ primorial.

🔗

Armed with primorials, one usually finds such lists by the following method.

First, for some fixed $p\text{,}$ compute a large set of primes of the form $a\cdot p\#+1\text{,}$ keeping track of the $a$ values in question.
Next, find arithmetic progressions among the values of $a$ from your list (not the values of $a\cdot p\# +1$ ).
If you find a bunch of $a$ values in a progression of the form $k+\ell\cdot n\text{,}$ then you've also found a progression of primes of the form $(k\cdot q\#+1)+(\ell\cdot q\#) n\text{.}$

🔗

If you want to, you can even sign up to find a length 27 sequence at the PrimeGrid distributed search!