18.785: Analytic Number Theory, MIT, spring 2007 (K.S. Kedlaya)
Small gaps between primes (after Goldston-Pintz-Yıldırım)In this section, we introduce the strategy initiated by Goldston-Yıldırım, and carried out
by them and Pintz, for proving new results on the existence of short gaps between primes.
Some calculations are postponed to a later unit.
References: much of this unit is liberally plagiarized from K. Soundararajan, Small gaps
between prime numbers: the work of Goldston-Pintz-Yıldırım, Bull. Amer. Math. Soc.
44 (2007), 1–18. For more details (which will be plagiarized later), see D.A. Goldston,Y. Motodashi, J. Pintz, and C. Yıldırım, Small gaps between primes exist, Proc. JapanAcad. Ser. A Math. Sci. 82 (2006), 61–65. (Both references are available online, e.g., via
MathSciNet.)1

The target theorem

Let pn denote the n-th prime. As noted in the previous unit, we can use a probabilistic
model to make plausible predictions about the ratio (pn+1 − pn )/(log pn ), by supposing thatπ(x + y) − π(x), for x large and y ∼ λ log x, obeys a Poisson distribution with parameter λ.
What we will prove is a rather crude assertion consistent with this model. (Before thiswork, this was only known for  ≈ 0.24.)
Theorem 1 (GPY). For any  > 0, there exist infinitely many pn such that pn+1 − pn < log pn .
Goldston et al also get a quantitative version of this, and they can even do this withpn+1 − pn < (log pn )1− for some specific  > 0. For simplicity, I won’t get into these
improvements. But I will discuss the following, whose proof is a good setup for the proof ofTheorem 1.
Theorem 2 (GPY). Assume the Elliott-Halberstam conjecture for Q = x θ with any fixedθ > 1/2. Then there exists c = c(θ) such that there exist infinitely many p n such thatpn+1 − pn < c. (If θ > 20/21, one has c(θ) = 20.)

2The approachFix a positive integer k; the basic idea is to try to prove a weak version of the HardyLittlewood k-tuples conjecture, for a k-tuple H = (h1 , . . . , hk ) of distinct integers. Namely,
we’ll try to prove that there are infinitely many n such that at least two of n + h1 , . . . , n + hk
are prime; this would imply that there are infinitely many prime gaps no greater thanmax H − min H.
To do this, we will try to find an arithmetic function a(n) with nonnegative values, suchthat for j = 1, . . . , k, we can establish
X
1 X
a(n) >a(n).
(1)
k x<n≤2xx<n≤2x,n+h =pj1

If we had such a function, we could sum over j to obtainXX#{1 ≤ j ≤ k : n + hj prime} · a(n) >a(n),x<n≤2xx<n≤2xwhich would immediately imply that for some x < n ≤ 2x, at least two of n + h1 , . . . , n + hk
are prime. (Note: this strategy is poorly adapted to look for three or more primes in thesame tuple. In fact, no satisfactory alternative has been proposed!)
Note that if a(n) is supported only on those n for which n + h1 , . . . , n + hk is prime, thenthe k-tuples conjecture would imply (1), but we have no hope of proving (1) directly. Instead,
we make a transition that is directly inspired by the transition from the combinatorial sieveto the Selberg sieve.

3Selberg revisited

Namely, we pick a cutoff parameter R (which will ultimately depend on k and x), and choosea(n) of the form
2X
a(n) = ρ(d)
d|(n+h1 )···(n+hk )for some arithmetic function ρ with ρ(1) = 1 and support in {1, . . . , R}. As in Selberg’ssieve, we have built the nonnegativity requirement into the construction, and we are now
free to vary the values of ρ in order to maximize the ratio between the two sides of (1).
Unfortunately, we are not in as simple a situation as in Selberg’s sieve, where we could
simply diagonalize a quadratic form to find the desired minimum. In our case, we arecomparing two different quadratic forms, which cannot be simultaneously diagonalized, andhitting the situation with Lagrange multipliers creates a mess. The best we can hope to do
is to pick ρ of a special form with at least one parameter left in, run the calculation, andthen optimize the choice of the parameter(s).
In Selberg’s sieve, the optimal choice would have beenk(d ≤ R).

k+`(d ≤ R)

log R/dρ(d) ≈ µ(d)log RIn our setting, we will instead put
log R/dρ(d) = µ(d)log Rfor ` a nonnegative integer depending on k, in a fashion to be specified later.

2(2)

4

Comparing the two sides

With this choice, one can calculate the two sides of (1) using the sorts of techniques we usedin the first section of this course. I will postpone those calculations to a later unit, so that
I can continue giving an overview of the method. First, here is what one gets for the rightside of (1).
Lemma 3. With notation as above, there exist C, c > 0 depending on k, `, such that forR ≤ x1/2 /(log x)C , X
S(H)(k + `)!22`
x(log x)k+2`−1 (log log x)ck+2`
a(n) =.
x(log R)+O(k + 2`)!(log R)2k+2` `(log R)2k+2`
x<n≤2xThe left side of (1) is more complicated, because of the extra restriction that n + hj
must be prime. It is on this side that the arithmetic subtleties will creep in. Expanding thesquare, we getXρ(d1 )ρ(d2 )#{x < n ≤ 2x : [d1 , d2 ]|(n + h1 ) · · · (n + hk ), n + hj prime}.
(3)
d1 ,d2 ≤R

The count on the right side involves first pinning n down among some number of arithmetic
progressions modulo the lcm [d1 , d2 ], then looking for primes in that arithmetic progression.
Thus one expects to be able to approximate (3) byXxg([d1 , d2 ])ρ(d1 )ρ(d2 ),log x d ,d ≤R
φ([d1 , d2 ])1(4)2where g is the multiplicative function with g(p) = vH (p) − 1.
Lemma 4. With notation as above, there exist C, c > 0 depending on k, `, such that forR ≤ x1/2 /(log x)C , we have the following.
(a) For h ∈/ H, (4) equals 
x(log x)k+2`−2 (log log x)cx
S(H, h) (k + `)!2 2`
k+2`(log R)+O.
(log R)2k+2` (k + 2`)! ` log x(log R)2k+2`(b) For h ∈ H, (4) equals

S(H)
(k + `)!22(` + 1)x(log x)k+2`−1 (log log x)cx
k+2`+1.
(log R)+O(log R)2k+2` (k + 2` + 1)! ` + 1 log x(log R)2k+2`
Crunching the numbers, we see that the ratio between (4) and the right side of (1) isasymptotic tolog R
2k(2` + 1).
(5)
log x (` + 1)(k + 2` + 1)
3

The second fraction is always less than 4, but it tends to 4 as k, ` → ∞. Thus if wecan safely approximate (3) by (4) in the range R ≤ x1/2− , or even R ≤ x1/4+ , we getbounded gaps between primes. (Here’s where we get stuck looking for three primes in one
tuple: we can’t hope to get past R = x1/2− because of our earlier errors.) For instance,
if we could take R = x1/2− , then already we get (4) with k = 7, ` = 1. Using the 7-tuple
H = {11, 13, 17, 19, 23, 29, 31}, one then deduces that there are infinitely many prime gapsof size at most 20.
One can tweak the above argument by changing (2) to allow a polynomial P (log(R/d)/(log R))
instead of just a power. That polynomial must satisfy P (1) = 1 and must vanish to orderat least k at 0. The quantity analogous to (5) isR 1 yk−2 (k−1)(1 − y)2 dy
log R 0 (k−2)! P
k R 1 yk−1.
log xP (k) (1 − y)2 dy(6)0 (k−1)!

If we can take R = x1/2− , then one can get this ratio over 1 already with k = 6, so one gets
infinitely many prime gaps bounded by 16 (using H = {7, 11, 13, 17, 19, 23}) rather than 20.
But even with the flexibility of choosing P , one can never get the second factor (excluding(log R)/(log x)) over 4 (exercise)!

5The error terms, first attempt

None of the above matters unless we can control the discrepancy between (3) and (4). This
discrepancy is spawned by error terms in the prime number theorem with moduli of the form
[d1 , d2 ] for d1 , d2 ≤ R, so the moduli can run up to R2 .
Now recall what we know about these discrepancies. Let π(x; N, m) be the number ofprimes p ≤ x congruent to m modulo N . If we allow Elliott-Halberstam, then for any fixed
A > 0 and  > 0, there exists c > 0 such thatXq≤Qmax ∗ π(2x; N, m) − π(x; N, m) −m∈(Z/N Z)x≤ cx(log x)−Aφ(N ) log xfor Q = x1− . This would allow taking R = x1/2− ; we thus deduce Theorem 2.
Unconditionally, Bombieri-Vinogradov only allows Q = x1/2− . This looks like a disaster:we must take R = x1/4− , and so we can never get (1)! What now?

6The error terms, second attempt

Remember that Theorem 1 is a much weaker assertion than the existence of infinitely manybounded gaps between primes; there is thus no need to insist on establishing (1) for any
particular tuple H. Instead, we are free to aggregate over all H in a certain range; to clarify,write a(n; H) instead of a(n) to indicate the dependence on H.
4

Fix δ > 0 for which we want infinitely many n with pn+1 − pn ≤ H = δ log x. We will
now try to prove the inequality
XX

H∈{1,...,H}k 1≤h≤H,n+h=pa(n, H, h) >1hXXXa(n, H),(7)H∈{1,...,H}k 1≤h≤H,n+h=p x<n≤2xwhich again is enough: now we get an n such that at least two of n + 1, . . . , n + h are prime.
For the right side of (7), Gallagher’s result from the previous unit gives us the same
asymptotics as before, except with S(H) replaced by 1 and slightly worse error terms. We
get an improvement on the left side, which we separate into terms with h ∈/ H and termswith h ∈ H. We estimate the latter termse exactly as before; for the former terms, we notethat if n + h is prime, thena(n; H) = a(n; H, h).
Namely, the difference comes from summands d which divide (n + h1 ) · · · (n + hk )(n + h) but
not (n + h1 ) · · · (n + hk ); those are all multiples of n + h > x > R, so ρ(d) = 0 for such d.
Thus we can simply appeal back to Lemma 3 with k replaced by k + 1 and H replaced by
H, h. If we now compare the ratio of the two sides of (7), the contribution in the numerator
from h ∈ H is exactly (5), to which we add the contribution H/(log x) = δ from the termswith h ∈/ H. As noted earlier, that’s just enough to get over 1 with R = x1/2− and k, `sufficiently large. This yields Theorem 1.

Exercises
1. Use the Poisson distribution model to compute a predicted distribution for the ratio(pn+1 − pn )/(log pn ).
2. Say we want to produce large gaps between primes. Take N to be the product of theprimes up to m, and consider N + 2, . . . , N + m. For what function f does this imply
pn+1 − pn > f (pn ) for infinitely many n?
3. Let P be a polynomial with P (1) = 1 vanishing to order at least k at 0. Prove thatthe quantity (6) sans the factor (log R)/(log x) is at most 4.

5