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\). 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 that introduced limiting and calculus methods to the study of number theory.

That is, \(ax+b\) defines a progression of numbers separated always by \(a\), 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.

We have already proved this for \(a=4\). It is easy to prove for \(a=2\)! (See Exercise 22.4.4.)

It is also possible to prove the theorem for \(b=1\), or \(b=-1\), without developing much bigger tools. In the article [C.6.1] a lot of factoring and expanding is used, and a much more recent article by Xianzu Lin [C.6.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)\), but doing so involves some high-level details about polynomial factorization (see Murty and Thain's paper for details).

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?

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\).

• 41, 47, 53, and 59 is an arithmetic progression of length 4, where \(a=6\).

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.)

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 the approach to it.

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\; .\end{equation*} This follows from Chebyshev's estimate in Theorem 21.3.4, and is called having zero density. We can try this for \(\pi\) with specific numbers:

• \(\pi(100)/100 = 1/4=0.25\)

• \(\pi(200)/200=0.23\)

• \(\pi(1000)/1000=0.168\), or under 17%.

• \(\pi(1000000)/1000000\approx 0.0785\), 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 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 following example, the first of length 26, was found quite recently, on April 10, 2010.

There are currently only six known 26-length sequences, as of this writing (including one found just days before). Currently, there are no known 27-length sequences (though they must exist, by the Green/Tao theorem). They must even obey the following ridiculous bound.

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

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

• First, for some fixed \(p\), compute a large set of primes of the form \(a\cdot p\#+1\), 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\), then you've also found a progression of primes of the form \((k\cdot q\#+1)+(\ell\cdot q\#) n\).

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