This post continues my series on favorite theorems of the twenty-first century. For an overview of the categories and my earlier selections, see this introductory post.
My choice for 2006 in Number Theory is a theorem of Ben Green and Terence Tao giving an asymptotic formula for the number of four-term arithmetic progressions of primes. More generally, their paper developed a method for counting solutions of systems of linear equations in which all unknowns are required to be prime. The paper was first posted online in June 2006 and appeared in the Annals of Mathematics in 2010 (Green and Tao 2010).
In a previous post, we discussed my favorite theorem of 2004: Green and Tao proved that the set of prime numbers contains arbitrarily long arithmetic progressions (Green and Tao 2008). Their result established the existence of infinitely many such progressions for every fixed length. However, it did not determine precisely how many of them there are.
For example, how many quadruples of primes form an arithmetic progression, that is, satisfy Equivalently, we want to count pairs of positive integers such that are all prime and .
There are approximately pairs of positive integers satisfying . On the other hand, the prime number theorem tells us that the probability that an integer of size approximately is prime is about . Here denotes the natural logarithm.
If we naively assume that the four numbers behave independently, we might therefore predict approximately four-term arithmetic progressions of primes.
However, this heuristic ignores restrictions arising from divisibility by small primes. For example, in any four-term arithmetic progression of primes greater than , the common difference must be divisible by . Indeed, if were odd, some terms would be even, while if were not divisible by , one of the first three terms would be divisible by .
Similar restrictions arise from other primes. Accounting for all of them leads to a correction factor expressed as an infinite product over primes.
Green and Tao proved that, after including these corrections, the heuristic gives the exact asymptotic answer.
The infinite product in the theorem converges to a positive number. Its factors describe the corrections to the naive probability arising from divisibility by each prime. Thus, the theorem does not merely prove that there are infinitely many four-term arithmetic progressions of primes, but determines their number asymptotically, including the exact leading constant.
In fact, the paper proves much more than this special case. Recall that a linear polynomial in variables with integer coefficients is a polynomial of the form where are integers.
Consider a collection of such polynomials We would like to know how often all of them take prime values simultaneously.
An obvious necessary condition is that, for every prime , we can choose integer values of such that none of the numbers is divisible by . Such a collection of polynomials is called admissible. Otherwise, at least one of the polynomial values is necessarily divisible by , so simultaneous primality is impossible apart from exceptional cases where that value equals itself.
We must also require that there are sufficiently many choices of the variables for which all the polynomial values are positive.
Finally, we exclude systems in which two polynomials are affinely related, meaning that for some rational constants . This condition excludes particularly difficult problems such as the twin prime conjecture, which asks whether and are simultaneously prime for infinitely many integers .
The general prediction is that, under these assumptions, the number of choices for which all are prime should be asymptotic to where is a constant determined by the polynomials. Like the constant in Theorem , it incorporates geometric restrictions and corrections for divisibility by primes.
In their 2006 paper, Green and Tao established this prediction unconditionally for a large class of systems, including those described by at most two independent nondegenerate linear equations. The general result was conditional on two conjectures concerning the apparent randomness of certain number-theoretic sequences.
The paper also obtained some surprising consequences beyond ordinary arithmetic progressions. For example, Green and Tao determined asymptotically how many three-term arithmetic progressions of primes have a common difference that is one more, or one less, than another prime. They also obtained results concerning representations of integers as sums of three primes with additional linear restrictions.
Let us briefly discuss the proof. The main difficulty is that prime numbers are not distributed completely randomly: their divisibility properties impose strong correlations. The authors first separate out these unavoidable restrictions by considering residue classes modulo products of small primes.
They then use a technique called the transference principle, developed in their earlier work. Roughly speaking, this technique allows one to replace certain problems about the sparse set of prime numbers by analogous problems about more regular, pseudorandom sequences. A sequence is called pseudorandom if, despite being defined deterministically, it behaves like a random sequence with respect to a suitable collection of statistical tests.
The required tests are related to Gowers norms, which measure the presence of structured additive patterns in numerical sequences. The proof also uses estimates involving the Möbius function, defined by The main idea is that, once the necessary divisibility restrictions have been removed, the primes behave sufficiently randomly for the predicted asymptotic formulas to hold.
At the time, the required pseudorandomness results were known only for certain relatively simple configurations, including four-term arithmetic progressions. Consequently, the general theorem remained conditional.
The story was completed in 2012. Green and Tao (Green and Tao 2012) proved the required conjecture concerning the Möbius function, while Green, Tao, and Ziegler (Green et al. 2012) established the remaining conjecture about Gowers norms. Together with the 2006 paper, these results established the predicted asymptotic for every fixed admissible collection of pairwise affine-independent linear polynomials, provided that the region where all polynomials are positive has nonzero limiting density.
In particular, for every fixed integer , the number of -term arithmetic progressions of primes is now known to be where is an explicitly computable constant depending only on .
Thus, the work initiated by Green and Tao in 2006 eventually provided a remarkably general solution to the problem of counting nondegenerate linear patterns in prime numbers. It not only established that such patterns exist, but also determined their asymptotic frequencies, revealing an extraordinary degree of regularity in the distribution of primes.