There is an interesting question implicit 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.

Obviously, we have already proved this for \(a=4\). It is easy to prove for \(a=2\)!

It is also possible to prove this for \(b=1\) without developing bigger tools, but it involves some details about polynomial factorization that are not worth spending time on now. Finding and verifying those details in a standard text makes a great student project!

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?

Can you get a sequence \[ak+b,k=0,1,2,3,\ldots n\] to all be 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\).
• 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? (Hint: there is a small one where the differences and starting number are both less than 10.)

The question can be raised whether one 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). The highest ones are listed at this website.

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

Then one usually finds such lists by this method:

• First compute a large set of primes \(a\cdot q\#+1\) for fixed \(q\).
• Find arithmetic progressions among the \(a\) values (not the \(a\cdot q\# +1\) guys).
• If you find \(a\) values in progression \(k+\ell\cdot n\), then...
• You've found the progression of primes \((k\cdot q\#+1)+(\ell\cdot q\#) n\)

Great! But how might one prove these can go as long as possible? That might seem mysterious, so here is the gist of the approach to it.

• Remember how there seem to be fewer primes the further out we go, also in an arithmetic sequence (e.g. prime mod 4 or mod 8)? That isn't a coincidence.
• There is a technical way to measure this: \[\lim_{n\to\infty}\frac{\pi(n)}{n}=0\; .\] This follows from the estimate we proved of Chebyshev's last time, and is called having zero density.
• If the limit were positive, then it would be called positive density. We can see this with specific numbers:
  • \(\pi(100)/100 = 1/4=0.25\)
  • \(\pi(200)/200=0.23\)
  • \(\pi(1000)/1000=0.168\), or under 17%.
• Now, if you have a collection of numbers which has positive density, it is a theorem from 1974 (Endre Szemeredi) that you can get arithmetic progressions of arbitrary length in such sets. Of course, it looks like the primes are approaching zero density.
• But Green and Tao managed to show this still works for the primes! It won't be true for any old set; but somehow, although there are not many primes, there are just enough for it to work.

The following example, the first of length 26, was found quite recently, on April 10, 2010. There are currently only four known 26-length sequences (see this canonical site).

As of this writing, there are no known 27-length sequences (though they must exist, by the Green/Tao theorem). They must even obey the following ridiculous bound.