18.785: Analytic Number Theory, MIT, spring 2007 (K.S. Kedlaya)
Prime k-tuples
This unit begins the third part of the course, in which we apply the results gatheredin the first two parts in order to say something about the extent to which primes cluster
together in short intervals.
Reference cited below: P.X. Gallagher, On the distribution of primes in short interval,Mathematika 23 (1976), 4–9; corrigendum, ibid. 28 (1981), 86. (I couldn’t find this online.)

1The Hardy-Littlewood k-tuples conjecture

Let H denote a k-tuple of distinct integers. What does one expect about the distribution of
the integers n such that n + h is prime for each h ∈ H?
Here is a rather simple-minded guess. The prime number theorem suggests that if one
chooses a random integer of size x, it will be prime with probability 1/(log x). If one thenchooses k distinct integers of size x, and there is no obvious reason why they cannot all beprime, then one might expect them to be simultaneously prime with probability log −k x, andthe number of such tuples with terms bounded by x should be asymptotic to x log −k x, withthe constant 1.
However, this turns out not to be the correct constant, as is easily verified against experimental evidence in the case of twin primes. The reason is perhaps obvious: the facts that thedifferent n + h are coprime to a fixed prime p are not independent, and one needs to accountfor this. Here is the recipe for doing so proposed by Hardy-Littlewood (and mentioned by
Ben Green in his guest lecture).
Fix a prime p. The probability that k randomly chosen integers are all not divisible byp is (1 − 1/p)k . On the other hand, the probability that the n + h are all coprime to p is1 − vH (p)/p, where vH (p) is the number of residue classes modulo p represented by elementsof H. We thus set−kY
vH (p)
1S(H) =
1−1−ppp(called the “singular series”, because it occurs in the Hardy-Littlewood circle method as aseries summed over singularities of some integral) and conjecture as follows.

Conjecture 1 (Hardy-Littlewood). Suppose that vH (p) < p for all p. Then the number ofintegers n ≤ x such that n + h is prime for each h ∈ H is asymptotic to S(H)x log −k x.
Of course if vH (p) = 0 for some p, then there is a trivial obstruction created by divisibility
mod p, so you only get finitely many prime k-tuples of that shape. On the other hand, ifvH (p) < p for all p, then the product converges absolutely and so S(H) > 0.
Convention: it will be convenient later to take the same definition for S(H) even if H
does not have distinct entries.

1

2

k-tuples and prime gaps

If one is only interested in looking for primes which are close together, without specifying
exactly what the gaps are, one could go back to the probabilistic model (attributed toCramér, more famous for his rule for solving linear systems). It suggests that the distributionof π(n + h) − π(n), for n ≤ N and h ∼ λ log N with λ fixed, should approach a Poisson
distribution with parameter λ as N → ∞. The fact that this follows from a suitably uniform
version of the k-tuples conjecture is due to Gallagher; the main part of the argument is thefollowing result, which we will need later.
Theorem 2 (Gallagher). We have
XS(H) ∼ xk .

H∈{1,...,x}kIn other words, the fudge factor S(H) between the probabilistic model and the HardyLittlewood prediction averages out to 1, so the prediction based on the probabilistic model isconsistent with Hardy-Littlewood. (Note: the contribution from tuples not having distinct
entries is O(xk−1 ), so it doesn’t matter whether we include them or not.)Here is a sketch of Gallagher’s proof, with the missing details left as exercises. (Throughout, keep k fixed.) Put−km
1a(p, m) = 1 −−11−ppaH (p) = a(p, vH (p))
so that
S(H) =Y(1 + aH (p)).

pExtend a by multiplicativity to squarefree arguments d, so that
XS(H) =aH (d)dwith the sum on the right being absolutely convergent.
We can truncate the sum over d by showing that for each fixed  > 0,X
XXS(H) =aH (d) + O(xk (xy) /y)d≤yH∈{1,...,x}kHwith the constant depending only on k,  and not on x, y (exercise).
For any given d, we can rewrite the inner sum of (1) as a sumX Y
 a(p, v(p)) fd (x, v),vp|d2(1)where v runs over vectors indexed by the prime factors of d, with v(p) ∈ {1, . . . , p} for eachp|d, and fd (x, v) counts k-tuples H ∈ {1, . . . , x}r which occupy exactly v(p) residue classes
modulo p for each p|d.
Write ab for the number of partitions of an a-element set into b unordered parts (Stirlingnumber of the second kind). If we set
XYpkA(d) =a(p, v(p))
v(p)!
v(p)
v(p)
v p|dXYpkB(d) =|a(p, v(p))|
v(p)!
v(p)
v(p)
v p|dXYC(d) =|a(p, v(p))|,vthenX

p|daH (d) = (x/d)k A(d) + O((x/d)k−1 B(d)) + O(xk−1 C(d)).

(2)

HFrom this, plus the identitiesp    Xpkv!
= pkv
v
v=1pX p  k vv!
= pk+1 − (p − 1)k p,vv
v=1(3)(4)

it is not difficult to deduce Theorem 2.

Exercises
1. Prove that for k a positive integer,
Z xlog−k t dt ∼ x log−k x.
2

2. Prove (1). (If you get stuck, see the hint for problem 5.)
3. Prove (2). (Hint: it might help to think in terms of counting lattice points.)
4. Prove the identities (3), (4).
5. Complete the proof of Theorem 2 from (1) and (2). (Hint: first use the Stirling number
identities to calculate A(d). Then estimate B(d) and C(d), using the bound(c(k)(p − 1)−2 m = k|a(p, m)| ≤c(k)(p − 1)−1 m < k.
3

That is, the constant c(k) depends on k but not on p or m. Finally, take y = x1/2 in(1).)

4