The Goldston-Pintz-Yildirim result, and how far do we have to walk to twin primes ?

When D. Goldston, J. Pintz and C. Yildirim proved the spectacular result that the gaps between consecutive primes satisfy

\liminf \frac{p_{n+1}-p_n}{\log n}=0\ \ \ \ \ \ \ (*)

(which means that those gaps are infinitely often smaller than an arbitrarily small multiple of their average size) there was a great hope that maybe some of their ideas would lead to a proof of the much stronger result

\liminf (p_{n+1}-p_n) \text{ is finite}\ \ \ \ \ \ \ (**)

and possibly to the twin prime conjecture (in the form stating that this liminf should be equal to 2). Since then, titles of lectures like Goldston’s “Revenge of the twin prime conjecture” have shown that this hope was, maybe, somewhat sanguine.

The work of Goldston-Pintz-Yildirim has been the subject of a number of surveys, and there is an excellent recent blog post on this topic by T. Tao (the first paragraph of which links to three of these surveys). In this post, I wish to discuss a complementary topic which is not addressed in detail in any of these: what, exactly, is needed to go to finite gaps (i.e., to prove (**))? why did it seem reasonable to hope that it might be accessible, and how hard can we guess this extra step to actually be? Some of this is discussed in my own Bourbaki report, but there will be new information towards the end, based on some discussions I had with É. Fouvry after I had written it.

The basic data that the method of Goldston-Pintz-Yildirim depends on is the quantitative equidistribution of primes in arithmetic progression, which is measured by the functions

E(x;q,a)=\ \ \ \ \ \sum_{p\leq x,\ p\equiv a\text{ mod } q}{\ \log p}\ \ \ -\ \ \frac{x}{\varphi(q)},

defined for any modulus q> 0 and residue class a modulo q, coprime with q. The basic information is that, in various senses, E(x;q,a) is small, and the difficulty (in this method as well as in countless other problems of analytic number theory) is that we must quantify this intuition in various ranges of the three variables, and most often uniformly.

What is known, and gives a reasonably strong foundation for further results and expectations, is that

|E(x;q,a)|\leq C(A)\frac{x}{(\log x)^A}

for any A>0, for some constant C(A) which is independent of q and a, but which is however ineffective (not actually computable for any given A). This looks good but recall the “main term” involved is


and because the Euler function is of size roughly q (up to small oscillations which are not important in this post), this means that the estimate we obtain is, in fact, trivial (and turns out to be useless) if q grows with x faster than any power of logarithm. For instance, this theorem (due to Siegel and Walfisz) doesn’t give any information about

\ \ \ \ \ \sum_{p\leq x,\ p\equiv a\text{ mod } q}{\ \log p}

if q is a small power of x (in particular, one can not guarantee the existence of primes occuring in the summation even if the main term x/φ(q) suggests there should be plenty of them).

Now, what is needed for (*) and (**)? (Note that by jumping to this, I — purposely in this post — am leaving aside the extremely ingenious and beautiful original ideas of Goldston, Pintz and Yildirim). Well, for (*), it suffices to know some upper bound on average over q up to, roughly, the square root of x, and uniformly over a: it suffices to find some B, depending on A, such that

\sum_{q\leq \sqrt{x}/(\log x)^B}{\max_{a\text{ mod } q}{|E(x;q,a)|}}\leq C(A)\frac{x}{(\log x)^A},

(where the constant C(A) may of course be another one than the one before). Now this is much stronger than the Siegel-Walfisz Theorem, and at first sight one may wonder if this is reasonable. That it is, indeed, expected, was known for a long time before it was proved unconditionally by Bombieri and Vinogradov (independently) in the 1960’s. The reason is that this estimate (with some specific value of B which I won’t write down explicitly) is a trivial consequence of the Generalized Riemann Hypothesis for Dirichlet L-functions (widely expected to be true…) and the so-called “Explicit formulas” which transform sums over primes in arithmetic progressions into sums over the zeros of the relevant L-functions. Indeed, as in this post, the “trivial” refers here to transforming an identity (or something close to it) to an upper bound by using the triangle inequality for a sum.

(Of course, the fact that this was expected does not mean that the result is easy: proving the Bombieri-Vinogradov theorem was a remarkable breakthrough in analytic number theory, and it was one of the main achievements that led to Bombieri being awarded the Fields Medal in 1974).

So, in a sense, the Bombieri-Vinogradov theorem explains why (*) is a theorem today. As to (**), much more is needed: it would suffice to extend the Bombieri-Vinogradov theorem to any range of modulus larger than the square-root of x, i.e., to prove, for any A, that

\sum_{q\leq x^{\delta}}{\max_{a\text{ mod } q}{|E(x;q,a)|}}\leq D(A)\frac{x}{(\log x)^A},\ \ \ \ \ \ \ (***)

for some δ>1/2 (independent of A); precisely, if this holds for a given δ, it follows that there are infinitely many primes at a finite distance from each other, the bound on the distance depending on δ. Currently (as far as I know), assuming the best possible result, which is that any δ<1 will work, one gets primes at a distance at most 16 from each other.

But any estimate of the type above remains completely conjectural! And based on the previous description of the Bombieri-Vinogradov Theorem, one can understand: the latter is, in some sense, an unconditional confirmation of what the Generalized Riemann Hypothesis suggests should be true. But GRH says nothing about primes in arithmetic progressions where the modulus exceeds (roughly) the square root of the length! So estimates like the one we need are unknown, even under the assumption of GRH.

This may lead to some scratching of chin, and some wonderment whether those statements are, in fact, correct. This is definitely a legitimate question: based on very clever ideas of Maier, Friedlander and Granville have shown that some very optimistic versions where the bound on the modulus is

x/(\log x)^B\text{ instead of } x^{\delta},\ \delta<1

are definitely false. But there are reasons to hope, at least for δ just slightly larger than 1/2, if one remembers that GRH implies the Bombieri-Vinogradov by a trivial treatment of a sum over zeros of L-functions: surely, the ordinates of the latter must be distributed randomly enough to lead to compensations when the sum is not submitted to the rough treatment of the triangle inequality!

A further — and more convincing — cause to hope is given by the remarkable work of Fouvry and Iwaniec first, strenghtened later by Bombieri, Friedlander and Iwaniec: for certain specific types of weights (arising naturally in sieve theory), and for certain explicit δ>1/2 (namely any δ<4/7 in the strongest version), we have

\sum_{q\leq x^{\delta}}{\gamma_q E(x;q,a)}\leq D(a,A)\frac{x}{(\log x)^A}.

This type of statements (which go back to the beginning to mid 1980’s) rank among the deepest known results in analytic number theory. Indeed, note that, for the reason sketched above, this can not be deduced from the Generalized Riemann Hypothesis, and yet it is an unconditional result: hence, it goes well beyond the already remarkable Bombieri-Vinogradov Theorem. (It would actually be interesting to have a proof of such results assuming — and using! — GRH, since apparently it involves in some mysterious way the detection of randomness in the ordinates of zeros of L-functions, but I don’t think there has been any work in this direction).

The proofs of these bounds for primes in arithmetic progressions to large moduli depend essentially on general estimates from the spectral theory of Kloosterman sums (due largely to Deshouillers and Iwaniec), and thus (ultimately) on properties of modular forms and eigenfunctions of the hyperbolic Laplace operator on finite area hyperbolic surfaces. Among applications, one may mention a result of Fouvry which was used (among other applications) in the first version of the deterministic polynomial-time algorithm for primality testing of Agrawal, Kayal and Saxena.

Coming back to (**), the fact that the exponent 4/7 is larger than 1/2 may suggest that the job is done. Unfortunately, there are two difficulties: (i) the weights γq are not arbitrary, and can not be chosen to give the absolute value in the summation; (ii) more importantly, the residue class a is now fixed. This second condition is the crucial one, because the method of Goldston, Pintz and Yildirim fundamentally requires to use more than one residue class.
Despite renewed efforts, it would seem to be very hard to obtain (***) using anything like the methods of Bombieri, Fouvry, Friedlander and Iwaniec.

However, one shouldn’t discard any hope too quickly: looking at the proof of (**), one realizes that it is not (***) really which is needed, but the following type of inequality

\sum_{q\leq x^{\delta}}{\sum_{a\in S(P,q)}{|E(x;q,a)|}}\leq D(A)\frac{x}{(\log x)^A},\ \ \ \ \ \ \ (****)

where the moduli q can be restricted to squarefree ones while the set of residue classes in the inner sum is

S(P,q)=\{a\text{ mod }q\,\mid\, (a,q)=1\text{ and } P(a)\equiv 0\text{ mod } q\},

for some integral (monic) polynomial which is fixed (though its degree may be fairly high). This special structure may be more accessible, because

\sum_{q\leq Q}{|S(P,q)|}\ll Q(\log Q)^{E}

for some (fixed) exponent E>0, so the number of residue classes considered is, on average, not very large. In particular, note that a trivial summation of the Bombieri-Fouvry-Friedlander-Iwaniec bounds over

0<a\leq (\log x)^{B}

shows (together with the information that the implied constant is polynomial in a) that their result does hold uniformly over sets with that many residue classes… except that those must, in the current state of knowledge, be located in the beginning interval, and not be spread out all over the residue classes, like the roots of P modulo q are likely to be.

Fouvry has looked a little bit at this type of inequalities, starting at the beginning; unfortunately, his rough computations give no particular reason to be optimistic at this point: it seems one needs to understand averages of very short Kloosterman sums in many variables, and both the length and the number of variables depend on the degree of the polynomial. Now, this polynomial is not arbitrary: in a somewhat delicate way, its degree ends up dictating for which value of θ>1/2 one needs to get (****) in order to derive (**). But the larger the degree, the smaller the exponent one can actually achieve assuming the most optimistic bounds for those short exponential sums (which are utterly out of reach anyway).

The conclusion? Well, one which seems to be unavoidable is that it really looks like a significant new idea is needed to get bounded gaps between primes: either to bypass the type of strategies which have been successful up to now in studying the distribution of primes in arithmetic progressions; or to find a way to bring those techniques to an entirely new level!

Published by


I am a professor of mathematics at ETH Zürich since 2008.

5 thoughts on “The Goldston-Pintz-Yildirim result, and how far do we have to walk to twin primes ?”

  1. Great post, very informative!

    A typo maybe: “[…]primes occuring in the summation even in the main term x/φ(q) suggests[…]” (I think you meant “even if the main term”).

Leave a Reply

Your email address will not be published. Required fields are marked *