For mathematicians, prime numbers are a thing of beauty. They are like atoms to a chemist or DNA to a geneticist, the fundamental blocks from which all whole numbers can be built. As any third grader can tell you, prime numbers are those that cannot be divided evenly by any smaller number other than 1 (such as 2, 3, 5, 7, 11, 13, 17, and 19). But what no mathematician had proved until this year is the long-standing conjecture that prime numbers come in arbitrarily long, finite arithmetic progressions.
You get an arithmetic progression by starting at a particular number and going up in fixed amounts. For example, start with 5 and go up in jumps of 12 and you get the sequence 5, 17, 29, 41, 53, 65, . . . For this sequence, the first five numbers are all primes. Thus, 5, 17, 29, 41, 53 is a five-number arithmetic progression of primes. Since 65 is not prime (it can be divided by both 5 and 13), this particular sequence cannot be extended to a progression of six. Can other sequences go longer? The answer is yes. In fact, 199, 409, 619, 829, 1,039, 1,249, 1,459, 1,669, 1,879, 2,089 is a 10-term arithmetic progression of primes with a difference of 210 between each.
To date, the largest known number of primes in an arithmetic progression is 22. Two such sequences have been found. One starts at 11,410,337,850,553 and goes up in steps of 4,609,098,694,200; the other starts at 376,859,931,192,959 and increases in steps of 18,549,279,769,020.
As you can readily see, prime numbers thin out as you make your way up through all numbers. But ancient Greek mathematicians knew that they never peter out completely—there are an infinite number of them. Although the primes seem to occur in a random fashion, Jacques Hadamard of France and Charles de la Vallée Poussin of Belgium proved at the end of the 19th century that there is a hidden pattern to the way they thin out. (For those who know a bit of calculus, the primes thin out in a way described by the natural logarithm function.) So there is definitely some order in the seeming chaos.
The existence of arbitrarily long (finite) arithmetic progressions of primes would be another pattern. Although mathematicians long suspected their existence, until this year no one had been able to prove it. The only real progress on the question came in 1939 when Johannes van der Corput of the Netherlands showed that there are infinitely many three-term arithmetic progressions of primes. Then, last spring, Ben Green, then of the University of British Columbia, and Terence Tao of UCLA, announced that they had cracked the problem completely, proving that there are indeed arithmetic progressions of primes of any finite length.
The new proof does not exhibit any arithmetic progressions of primes, nor does it even tell you how to find any. It’s what mathematicians call a nonconstructive existence proof. The two mathematicians, both still in their twenties, began with a 1975 result of the Hungarian mathematician Endre Szemerédi. Loosely speaking, Szemerédi showed that in any infinite set of numbers that does not thin out too rapidly, there definitely will be arithmetic progressions of all finite lengths.
Unfortunately, primes do thin out too rapidly. However, Green and Tao found a cunning way around this problem: Think relatively. If you take all the numbers and throw away some nonprimes, then relative to this thinned-out set, the primes thin out less rapidly.
Can you do this pruning in such a way that Szemerédi’s argument still works? The answer turns out to be yes. Green and Tao found an infinite set, call it x, consisting of all the primes as well as some nonprimes that have few divisors compared to their size, for which Szemerédi’s result still holds. Thus, any infinite subset of x that does not thin out too rapidly relative to x will contain arithmetic progressions of all finite lengths. Because the primes do not thin out too rapidly relative to the set x, this implies that there are arithmetic progressions of primes of all finite lengths. QED.
