You are currently browsing the tag archive for the ‘Yitang Zhang’ tag.

As in previous posts, we use the following asymptotic notation: ${x}$ is a parameter going off to infinity, and all quantities may depend on ${x}$ unless explicitly declared to be “fixed”. The asymptotic notation ${O(), o(), \ll}$ is then defined relative to this parameter. A quantity ${q}$ is said to be of polynomial size if one has ${q = O(x^{O(1)})}$, and bounded if ${q=O(1)}$. We also write ${X \lessapprox Y}$ for ${X \ll x^{o(1)} Y}$, and ${X \sim Y}$ for ${X \ll Y \ll X}$.

The purpose of this post is to collect together all the various refinements to the second half of Zhang’s paper that have been obtained as part of the polymath8 project and present them as a coherent argument (though not fully self-contained, as we will need some lemmas from previous posts).

In order to state the main result, we need to recall some definitions.

Definition 1 (Singleton congruence class system) Let ${I \subset {\bf R}}$, and let ${{\mathcal S}_I}$ denote the square-free numbers whose prime factors lie in ${I}$. A singleton congruence class system on ${I}$ is a collection ${{\mathcal C} = (\{a_q\})_{q \in {\mathcal S}_I}}$ of primitive residue classes ${a_q \in ({\bf Z}/q{\bf Z})^\times}$ for each ${q \in {\mathcal S}_I}$, obeying the Chinese remainder theorem property

$\displaystyle a_{qr}\ (qr) = (a_q\ (q)) \cap (a_r\ (r)) \ \ \ \ \ (1)$

whenever ${q,r \in {\mathcal S}_I}$ are coprime. We say that such a system ${{\mathcal C}}$ has controlled multiplicity if the

$\displaystyle \tau_{\mathcal C}(n) := |\{ q \in {\mathcal S}_I: n = a_q\ (q) \}|$

obeys the estimate

$\displaystyle \sum_{C^{-1} x \leq n \leq Cx: n = a\ (r)} \tau_{\mathcal C}(n)^2 \ll \frac{x}{r} \tau(r)^{O(1)} \log^{O(1)} x + x^{o(1)}. \ \ \ \ \ (2)$

for any fixed ${C>1}$ and any congruence class ${a\ (r)}$ with ${r \in {\mathcal S}_I}$. Here ${\tau}$ is the divisor function.

Next we need a relaxation of the concept of ${y}$-smoothness.

Definition 2 (Dense divisibility) Let ${y \geq 1}$. A positive integer ${q}$ is said to be ${y}$-densely divisible if, for every ${1 \leq R \leq q}$, there exists a factor of ${q}$ in the interval ${[y^{-1} R, R]}$. We let ${{\mathcal D}_y}$ denote the set of ${y}$-densely divisible positive integers.

Now we present a strengthened version ${MPZ'[\varpi,\delta]}$ of the Motohashi-Pintz-Zhang conjecture ${MPZ[\varpi,\delta]}$, which depends on parameters ${0 < \varpi < 1/4}$ and ${0 < \delta < 1/4}$.

Conjecture 3 (${MPZ'[\varpi,\delta]}$) Let ${I \subset {\bf R}}$, and let ${(\{a_q\})_{q \in {\mathcal S}_I}}$ be a congruence class system with controlled multiplicity. Then

$\displaystyle \sum_{q \in {\mathcal S}_I \cap {\mathcal D}_{x^\delta}: q< x^{1/2+2\varpi}} |\Delta(\Lambda 1_{[x,2x]}; a_q)| \ll x \log^{-A} x \ \ \ \ \ (3)$

for any fixed ${A>0}$, where ${\Lambda}$ is the von Mangoldt function.

The difference between this conjecture and the weaker conjecture ${MPZ[\varpi,\delta]}$ is that the modulus ${q}$ is constrained to be ${x^\delta}$-densely divisible rather than ${x^\delta}$-smooth (note that ${I}$ is no longer constrained to lie in ${[1,x^\delta]}$). This relaxation of the smoothness condition improves the Goldston-Pintz-Yildirim type sieving needed to deduce ${DHL[k_0,2]}$ from ${MPZ'[\varpi,\delta]}$; see this previous post.

The main result we will establish is

Theorem 4 ${MPZ'[\varpi,\delta]}$ holds for any ${\varpi,\delta>0}$ with

$\displaystyle 148\varpi+33\delta < 1. \ \ \ \ \ (4)$

This improves upon previous constraints of ${87\varpi + 17 \delta < \frac{1}{4}}$ (see this blog comment) and ${207 \varpi + 43 \delta < \frac{1}{4}}$ (see Theorem 13 of this previous post), which were also only established for ${MPZ[\varpi,\delta]}$ instead of ${MPZ'[\varpi,\delta]}$. Inserting Theorem 4 into the Pintz sieve from this previous post gives ${DHL[k_0,2]}$ for ${k_0 = 1467}$ (see this blog comment), which when inserted in turn into newly set up tables of narrow prime tuples gives infinitely many prime gaps of separation at most ${H = 12,012}$.

As in previous posts, we use the following asymptotic notation: ${x}$ is a parameter going off to infinity, and all quantities may depend on ${x}$ unless explicitly declared to be “fixed”. The asymptotic notation ${O(), o(), \ll}$ is then defined relative to this parameter. A quantity ${q}$ is said to be of polynomial size if one has ${q = O(x^{O(1)})}$, and said to be bounded if ${q=O(1)}$. Another convenient notation: we write ${X \lessapprox Y}$ for ${X \ll x^{o(1)} Y}$. Thus for instance the divisor bound asserts that if ${q}$ has polynomial size, then the number of divisors of ${q}$ is ${\lessapprox 1}$.

This post is intended to highlight a phenomenon unearthed in the ongoing polymath8 project (and is in fact a key component of Zhang’s proof that there are bounded gaps between primes infinitely often), namely that one can get quite good bounds on relatively short exponential sums when the modulus ${q}$ is smooth, through the basic technique of Weyl differencing (ultimately based on the Cauchy-Schwarz inequality, and also related to the van der Corput lemma in equidistribution theory). Improvements in the case of smooth moduli have appeared before in the literature (e.g. in this paper of Heath-Brown, paper of Graham and Ringrose, this later paper of Heath-Brown, this paper of Chang, or this paper of Goldmakher); the arguments here are particularly close to that of the first paper of Heath-Brown. It now also appears that further optimisation of this Weyl differencing trick could lead to noticeable improvements in the numerology for the polymath8 project, so I am devoting this post to explaining this trick further.

To illustrate the method, let us begin with the classical problem in analytic number theory of estimating an incomplete character sum

$\displaystyle \sum_{M+1 \leq n \leq M+N} \chi(n)$

where ${\chi}$ is a primitive Dirichlet character of some conductor ${q}$, ${M}$ is an integer, and ${N}$ is some quantity between ${1}$ and ${q}$. Clearly we have the trivial bound

$\displaystyle |\sum_{M+1 \leq n \leq M+N} \chi(n)| \leq N; \ \ \ \ \ (1)$

we also have the classical Pólya-Vinogradov inequality

$\displaystyle |\sum_{M+1 \leq n \leq M+N} \chi(n)| \ll q^{1/2} \log q. \ \ \ \ \ (2)$

This latter inequality gives improvements over the trivial bound when ${N}$ is much larger than ${q^{1/2}}$, but not for ${N}$ much smaller than ${q^{1/2}}$. The Pólya-Vinogradov inequality can be deduced via a little Fourier analysis from the completed exponential sum bound

$\displaystyle | \sum_{n \in {\bf Z}/q{\bf Z}} \chi(n) e_q( an )| \ll q^{1/2}$

for any ${a \in {\bf Z}/q{\bf Z}}$, where ${e_q(n) :=e^{2\pi i n/q}}$. (In fact, from the classical theory of Gauss sums, this exponential sum is equal to ${\tau(\chi) \overline{\chi(a)}}$ for some complex number ${\tau(\chi)}$ of norm ${\sqrt{q}}$.)

In the case when ${q}$ is a prime, improving upon the above two inequalities is an important but difficult problem, with only partially satisfactory results so far. To give just one indication of the difficulty, the seemingly modest improvement

$\displaystyle |\sum_{M+1 \leq n \leq M+N} \chi(n)| \ll p^{1/2} \log \log p$

to the Pólya-Vinogradov inequality when ${q=p}$ was a prime required a 14-page paper in Inventiones by Montgomery and Vaughan to prove, and even then it was only conditional on the generalised Riemann hypothesis! See also this more recent paper of Granville and Soundararajan for an unconditional variant of this result in the case that ${\chi}$ has odd order.

Another important improvement is the Burgess bound, which in our notation asserts that

$\displaystyle |\sum_{M+1 \leq n \leq M+N} \chi(n)| \lessapprox N^{1-1/r} q^{\frac{r+1}{4r^2}} \ \ \ \ \ (3)$

for any fixed integer ${r \geq 2}$, assuming that ${q}$ is square-free (for simplicity) and of polynomial size; see this previous post for a discussion of the Burgess argument. This is non-trivial for ${N}$ as small as ${q^{1/4+o(1)}}$.

In the case when ${q}$ is prime, there has been very little improvement to the Burgess bound (or its Fourier dual, which can give bounds for ${N}$ as large as ${q^{3/4-o(1)}}$) in the last fifty years; an improvement to the exponents in (3) in this case (particularly anything that gave a power saving for ${N}$ below ${q^{1/4}}$) would in fact be rather significant news in analytic number theory.

However, in the opposite case when ${q}$ is smooth – that is to say, all of its factors are much smaller than ${q}$ – then one can do better than the Burgess bound in some regimes. This fact has been observed in several places in the literature (in particular, in the papers of Heath-Brown, Graham-Ringrose, Chang, and Goldmakher mentioned previously), but also turns out to (implicitly) be a key insight in Zhang’s paper on bounded prime gaps. In the case of character sums, one such improved estimate (closely related to Theorem 2 of the Heath-Brown paper) is as follows:

Proposition 1 Let ${q}$ be square-free with a factorisation ${q = q_1 q_2}$ and of polynomial size, and let ${M,N}$ be integers with ${1 \leq N \leq q}$. Then for any primitive character ${\chi}$ with conductor ${q}$, one has

$\displaystyle | \sum_{M+1 \leq n \leq M+N} \chi(n) | \lessapprox N^{1/2} q_1^{1/2} + N^{1/2} q_2^{1/4}.$

This proposition is particularly powerful when ${q}$ is smooth, as this gives many factorisations ${q = q_1 q_2}$ with the ability to specify ${q_1,q_2}$ with a fair amount of accuracy. For instance, if ${q}$ is ${y}$-smooth (i.e. all prime factors are at most ${y}$), then by the greedy algorithm one can find a divisor ${q_1}$ of ${q}$ with ${y^{-2/3} q^{1/3} \leq q_1 \leq y^{1/3} q^{1/3}}$; if we set ${q_2 := q/q_1}$, then ${y^{-1/3} q^{2/3} \leq q_2 \leq y^{2/3} q^{2/3}}$, and the above proposition then gives

$\displaystyle | \sum_{M+1 \leq n \leq M+N} \chi(n) | \lessapprox y^{1/6} N^{1/2} q^{1/6}$

which can improve upon the Burgess bound when ${y}$ is small. For instance, if ${N = q^{1/2}}$, then this bound becomes ${\lessapprox y^{1/6} q^{5/12}}$; in contrast the Burgess bound only gives ${\lessapprox q^{7/16}}$ for this value of ${N}$ (using the optimal choice ${r=2}$ for ${r}$), which is inferior for ${y < q^{1/8}}$.

The hypothesis that ${q}$ be squarefree may be relaxed, but for applications to the Polymath8 project, it is only the squarefree moduli that are relevant.

Proof: If ${N \ll q_1}$ then the claim follows from the trivial bound (1), while for ${N \gg q_2}$ the claim follows from (2). Hence we may assume that

$\displaystyle q_1 < N < q_2.$

We use the method of Weyl differencing, the key point being to difference in multiples of ${q_1}$.

Let ${K := \lfloor N/q_1 \rfloor}$, thus ${K \geq 1}$. For any ${1 \leq k \leq K}$, we have

$\displaystyle \sum_{M+1 \leq n \leq M+N} \chi(n) = \sum_n 1_{[M+1,M+N]}(n+kq_1) \chi(n+kq_1)$

and thus on averaging

$\displaystyle \sum_{M+1 \leq n \leq M+N} \chi(n) = \frac{1}{K} \sum_n \sum_{k=1}^K 1_{[M+1,M+N]}(n+kq_1) \chi(n+kq_1). \ \ \ \ \ (4)$

By the Chinese remainder theorem, we may factor

$\displaystyle \chi(n) = \chi_1(n) \chi_2(n)$

where ${\chi_1,\chi_2}$ are primitive characters of conductor ${q_1,q_2}$ respectively. As ${\chi_1}$ is periodic of period ${q_1}$, we thus have

$\displaystyle \chi(n+kq_1) = \chi_1(n) \chi_2(n+kq_2)$

and so we can take ${\chi_1}$ out of the inner summation of the right-hand side of (4) to obtain

$\displaystyle \sum_{M+1 \leq n \leq M+N} \chi(n) = \frac{1}{K} \sum_n \chi_1(n) \sum_{k=1}^K 1_{[M+1,M+N]}(n+kq_1) \chi_2(n+kq_1)$

and hence by the triangle inequality

$\displaystyle |\sum_{M+1 \leq n \leq M+N} \chi(n)| \leq \frac{1}{K} \sum_n |\sum_{k=1}^K 1_{[M+1,M+N]}(n+kq_1) \chi_2(n+kq_1)|.$

Note how the characters on the right-hand side only have period ${q_2}$ rather than ${q=q_1 q_2}$. This reduction in the period is ultimately the source of the saving over the Pólya-Vinogradov inequality.

Note that the inner sum vanishes unless ${n \in [M+1-Kq_1,M+N]}$, which is an interval of length ${O(N)}$ by choice of ${K}$. Thus by Cauchy-Schwarz one has

$\displaystyle | \sum_{M+1 \leq n \leq M+N} \chi(n) | \ll$

$\displaystyle \frac{N^{1/2}}{K} (\sum_n |\sum_{k=1}^K 1_{[M+1,M+N]}(n+kq_1) \chi_2(n+kq_1)|^2)^{1/2}.$

We expand the right-hand side as

$\displaystyle \frac{N^{1/2}}{K} |\sum_{1 \leq k,k' \leq K} \sum_n$

$\displaystyle 1_{[M+1,M+N]}(n+kq_1) 1_{[M+1,M+N]}(n+k'q_1) \chi_2(n+kq_1) \overline{\chi_2(n+k'q_1)}|^{1/2}.$

We first consider the diagonal contribution ${k=k'}$. In this case we use the trivial bound ${O(N)}$ for the inner summation, and we soon see that the total contribution here is ${O( K^{-1/2} N ) = O( N^{1/2}q_1^{1/2} )}$.

Now we consider the off-diagonal case; by symmetry we can take ${k < k'}$. Then the indicator functions ${1_{[M+1,M+N]}(n+kq_1) 1_{[M+1,M+N]}(n+k'q_1)}$ restrict ${n}$ to the interval ${[M+1-kq_1, M+N-k'q_1]}$. On the other hand, as a consequence of the Weil conjectures for curves one can show that

$\displaystyle |\sum_{n \in {\bf Z}/q_2{\bf Z}} \chi_2(n+kq_1) \overline{\chi_2(n+k'q_1)} e_{q_2}(an)| \lessapprox q_2^{1/2} (k-k',q_2)^{1/2}$

for any ${a \in {\bf Z}/q_2{\bf Z}}$; indeed one can use the Chinese remainder theorem and the square-free nature of ${q_2}$ to reduce to the case when ${q_2}$ is prime, in which case one can apply (for instance) the original paper of Weil to establish this bound, noting also that ${q_1}$ and ${q_2}$ are coprime since ${q}$ is squarefree. Applying the method of completion of sums (or the Parseval formula), this shows that

$\displaystyle |\sum_n 1_{[M+1,M+N]}(n+kq_1) 1_{[M+1,M+N]}(n+k'q_1) \chi_2(n+kq_1) \overline{\chi_2(n+k'q_1)}|$

$\displaystyle \lessapprox q_2^{1/2} (k-k',q_2)^{1/2}.$

Summing in ${k,k'}$ (using Lemma 5 from this previous post) we see that the total contribution to the off-diagonal case is

$\displaystyle \lessapprox \frac{N^{1/2}}{K} ( K^2 q_2^{1/2} )^{1/2}$

which simplifies to ${\lessapprox N^{1/2} q_2^{1/4}}$. The claim follows. $\Box$

A modification of the above argument (using more complicated versions of the Weil conjectures) allows one to replace the summand ${\chi(n)}$ by more complicated summands such as ${\chi(f(n)) e_q(g(n))}$ for some polynomials or rational functions ${f,g}$ of bounded degree and obeying a suitable non-degeneracy condition (after restricting of course to those ${n}$ for which the arguments ${f(n),g(n)}$ are well-defined). We will not detail this here, but instead turn to the question of estimating slightly longer exponential sums, such as

$\displaystyle \sum_{1 \leq n \leq N} e_{d_1}( \frac{c_1}{n} ) e_{d_2}( \frac{c_2}{n+l} )$

where ${N}$ should be thought of as a little bit larger than ${(d_1d_2)^{1/2}}$.

This is the final continuation of the online reading seminar of Zhang’s paper for the polymath8 project. (There are two other continuations; this previous post, which deals with the combinatorial aspects of the second part of Zhang’s paper, and this previous post, that covers the Type I and Type II sums.) The main purpose of this post is to present (and hopefully, to improve upon) the treatment of the final and most innovative of the key estimates in Zhang’s paper, namely the Type III estimate.

The main estimate was already stated as Theorem 17 in the previous post, but we quickly recall the relevant definitions here. As in other posts, we always take ${x}$ to be a parameter going off to infinity, with the usual asymptotic notation ${O(), o(), \ll}$ associated to this parameter.

Definition 1 (Coefficient sequences) A coefficient sequence is a finitely supported sequence ${\alpha: {\bf N} \rightarrow {\bf R}}$ that obeys the bounds

$\displaystyle |\alpha(n)| \ll \tau^{O(1)}(n) \log^{O(1)}(x) \ \ \ \ \ (1)$

for all ${n}$, where ${\tau}$ is the divisor function.

• (i) If ${\alpha}$ is a coefficient sequence and ${a\ (q) = a \hbox{ mod } q}$ is a primitive residue class, the (signed) discrepancy ${\Delta(\alpha; a\ (q))}$ of ${\alpha}$ in the sequence is defined to be the quantity

$\displaystyle \Delta(\alpha; a \ (q)) := \sum_{n: n = a\ (q)} \alpha(n) - \frac{1}{\phi(q)} \sum_{n: (n,q)=1} \alpha(n). \ \ \ \ \ (2)$

• (ii) A coefficient sequence ${\alpha}$ is said to be at scale ${N}$ for some ${N \geq 1}$ if it is supported on an interval of the form ${[(1-O(\log^{-A_0} x)) N, (1+O(\log^{-A_0} x)) N]}$.
• (iii) A coefficient sequence ${\alpha}$ at scale ${N}$ is said to be smooth if it takes the form ${\alpha(n) = \psi(n/N)}$ for some smooth function ${\psi: {\bf R} \rightarrow {\bf C}}$ supported on ${[1-O(\log^{-A_0} x), 1+O(\log^{-A_0} x)]}$ obeying the derivative bounds

$\displaystyle \psi^{(j)}(t) = O( \log^{j A_0} x ) \ \ \ \ \ (3)$

for all fixed ${j \geq 0}$ (note that the implied constant in the ${O()}$ notation may depend on ${j}$).

For any ${I \subset {\bf R}}$, let ${{\mathcal S}_I}$ denote the square-free numbers whose prime factors lie in ${I}$. The main result of this post is then the following result of Zhang:

Theorem 2 (Type III estimate) Let ${\varpi, \delta > 0}$ be fixed quantities, and let ${M, N_1, N_2, N_3 \gg 1}$ be quantities such that

$\displaystyle x \ll M N_1 N_2 N_3 \ll x$

and

$\displaystyle N_1 \gg N_2, N_3$

and

$\displaystyle N_1^4 N_2^4 N_3^5 \gg x^{4+16\varpi+\delta+c}$

for some fixed ${c>0}$. Let ${\alpha, \psi_1, \psi_2, \psi_3}$ be coefficient sequences at scale ${M,N_1,N_2,N_3}$ respectively with ${\psi_1,\psi_2,\psi_3}$ smooth. Then for any ${I \subset [1,x^\delta]}$ we have

$\displaystyle \sum_{q \in {\mathcal S}_I: q< x^{1/2+2\varpi}} \sup_{a \in ({\bf Z}/q{\bf Z})^\times} |\Delta(\alpha \ast \beta; a)| \ll x \log^{-A} x.$

In fact we have the stronger “pointwise” estimate

$\displaystyle |\Delta(\alpha \ast \psi_1 \ast \psi_2 \ast \psi_3; a)| \ll x^{-\epsilon} \frac{x}{q} \ \ \ \ \ (4)$

for all ${q \in {\mathcal S}_I}$ with ${q < x^{1/2+2\varpi}}$ and all ${a \in ({\bf Z}/q{\bf Z})^\times}$, and some fixed ${\epsilon>0}$.

(This is very slightly stronger than previously claimed, in that the condition ${N_2 \gg N_3}$ has been dropped.)

It turns out that Zhang does not exploit any averaging of the ${\alpha}$ factor, and matters reduce to the following:

Theorem 3 (Type III estimate without ${\alpha}$) Let ${\delta > 0}$ be fixed, and let ${1 \ll N_1, N_2, N_3, d \ll x^{O(1)}}$ be quantities such that

$\displaystyle N_1 \gg N_2, N_3$

and

$\displaystyle d \in {\mathcal S}_{[1,x^\delta]}$

and

$\displaystyle N_1^4 N_2^4 N_3^5 \gg d^8 x^{\delta+c}$

for some fixed ${c>0}$. Let ${\psi_1,\psi_2,\psi_3}$ be smooth coefficient sequences at scales ${N_1,N_2,N_3}$ respectively. Then we have

$\displaystyle |\Delta(\psi_1 \ast \psi_2 \ast \psi_3; a)| \ll x^{-\epsilon} \frac{N_1 N_2 N_3}{d}$

for all ${a \in ({\bf Z}/d{\bf Z})^\times}$ and some fixed ${\epsilon>0}$.

Let us quickly see how Theorem 3 implies Theorem 2. To show (4), it suffices to establish the bound

$\displaystyle \sum_{n = a\ (q)} \alpha \ast \psi_1 \ast \psi_2 \ast \psi_3(n) = X + O( x^{-\epsilon} \frac{x}{q} )$

for all ${a \in ({\bf Z}/q{\bf Z})^\times}$, where ${X}$ denotes a quantity that is independent of ${a}$ (but can depend on other quantities such as ${\alpha,\psi_1,\psi_2,\psi_3,q}$). The left-hand side can be rewritten as

$\displaystyle \sum_{b \in ({\bf Z}/q{\bf Z})^\times} \sum_{m = b\ (q)} \alpha(m) \sum_{n = a/b\ (q)} \psi_1 \ast \psi_2 \ast \psi_3(n).$

From Theorem 3 we have

$\displaystyle \sum_{n = a/b\ (q)} \psi_1 \ast \psi_2 \ast \psi_3(n) = Y + O( x^{-\epsilon} \frac{N_1 N_2 N_3}{q} )$

where the quantity ${Y}$ does not depend on ${a}$ or ${b}$. Inserting this asymptotic and using crude bounds on ${\alpha}$ (see Lemma 8 of this previous post) we conclude (4) as required (after modifying ${\epsilon}$ slightly).

It remains to establish Theorem 3. This is done by a set of tools similar to that used to control the Type I and Type II sums:

• (i) completion of sums;
• (ii) the Weil conjectures and bounds on Ramanujan sums;
• (iii) factorisation of smooth moduli ${q \in {\mathcal S}_I}$;
• (iv) the Cauchy-Schwarz and triangle inequalities (Weyl differencing).

The specifics are slightly different though. For the Type I and Type II sums, it was the classical Weil bound on Kloosterman sums that were the key source of power saving; Ramanujan sums only played a minor role, controlling a secondary error term. For the Type III sums, one needs a significantly deeper consequence of the Weil conjectures, namely the estimate of Bombieri and Birch on a three-dimensional variant of a Kloosterman sum. Furthermore, the Ramanujan sums – which are a rare example of sums that actually exhibit better than square root cancellation, thus going beyond even what the Weil conjectures can offer – make a crucial appearance, when combined with the factorisation of the smooth modulus ${q}$ (this new argument is arguably the most original and interesting contribution of Zhang).

This is one of the continuations of the online reading seminar of Zhang’s paper for the polymath8 project. (There are two other continuations; this previous post, which deals with the combinatorial aspects of the second part of Zhang’s paper, and a post to come that covers the Type III sums.) The main purpose of this post is to present (and hopefully, to improve upon) the treatment of two of the three key estimates in Zhang’s paper, namely the Type I and Type II estimates.

The main estimate was already stated as Theorem 16 in the previous post, but we quickly recall the relevant definitions here. As in other posts, we always take ${x}$ to be a parameter going off to infinity, with the usual asymptotic notation ${O(), o(), \ll}$ associated to this parameter.

Definition 1 (Coefficient sequences) A coefficient sequence is a finitely supported sequence ${\alpha: {\bf N} \rightarrow {\bf R}}$ that obeys the bounds

$\displaystyle |\alpha(n)| \ll \tau^{O(1)}(n) \log^{O(1)}(x) \ \ \ \ \ (1)$

for all ${n}$, where ${\tau}$ is the divisor function.

• (i) If ${\alpha}$ is a coefficient sequence and ${a\ (q) = a \hbox{ mod } q}$ is a primitive residue class, the (signed) discrepancy ${\Delta(\alpha; a\ (q))}$ of ${\alpha}$ in the sequence is defined to be the quantity

$\displaystyle \Delta(\alpha; a \ (q)) := \sum_{n: n = a\ (q)} \alpha(n) - \frac{1}{\phi(q)} \sum_{n: (n,q)=1} \alpha(n). \ \ \ \ \ (2)$

• (ii) A coefficient sequence ${\alpha}$ is said to be at scale ${N}$ for some ${N \geq 1}$ if it is supported on an interval of the form ${[(1-O(\log^{-A_0} x)) N, (1+O(\log^{-A_0} x)) N]}$.
• (iii) A coefficient sequence ${\alpha}$ at scale ${N}$ is said to obey the Siegel-Walfisz theorem if one has

$\displaystyle | \Delta(\alpha 1_{(\cdot,q)=1}; a\ (r)) | \ll \tau(qr)^{O(1)} N \log^{-A} x \ \ \ \ \ (3)$

for any ${q,r \geq 1}$, any fixed ${A}$, and any primitive residue class ${a\ (r)}$.

• (iv) A coefficient sequence ${\alpha}$ at scale ${N}$ is said to be smooth if it takes the form ${\alpha(n) = \psi(n/N)}$ for some smooth function ${\psi: {\bf R} \rightarrow {\bf C}}$ supported on ${[1-O(\log^{-A_0} x), 1+O(\log^{-A_0} x)]}$ obeying the derivative bounds

$\displaystyle \psi^{(j)}(t) = O( \log^{j A_0} x ) \ \ \ \ \ (4)$

for all fixed ${j \geq 0}$ (note that the implied constant in the ${O()}$ notation may depend on ${j}$).

In Lemma 8 of this previous post we established a collection of “crude estimates” which assert, roughly speaking, that for the purposes of averaged estimates one may ignore the ${\tau^{O(1)}(n)}$ factor in (1) and pretend that ${\alpha(n)}$ was in fact ${O( \log^{O(1)} n)}$. We shall rely frequently on these “crude estimates” without further citation to that precise lemma.

For any ${I \subset {\bf R}}$, let ${{\mathcal S}_I}$ denote the square-free numbers whose prime factors lie in ${I}$.

Definition 2 (Singleton congruence class system) Let ${I \subset {\bf R}}$. A singleton congruence class system on ${I}$ is a collection ${{\mathcal C} = (\{a_q\})_{q \in {\mathcal S}_I}}$ of primitive residue classes ${a_q \in ({\bf Z}/q{\bf Z})^\times}$ for each ${q \in {\mathcal S}_I}$, obeying the Chinese remainder theorem property

$\displaystyle a_{qr}\ (qr) = (a_q\ (q)) \cap (a_r\ (r)) \ \ \ \ \ (5)$

whenever ${q,r \in {\mathcal S}_I}$ are coprime. We say that such a system ${{\mathcal C}}$ has controlled multiplicity if the

$\displaystyle \tau_{\mathcal C}(n) := |\{ q \in {\mathcal S}_I: n = a_q\ (q) \}|$

obeys the estimate

$\displaystyle \sum_{C^{-1} x \leq n \leq Cx: n = a\ (r)} \tau_{\mathcal C}(n)^2 \ll \frac{x}{r} \tau(r)^{O(1)} \log^{O(1)} x + x^{o(1)}. \ \ \ \ \ (6)$

for any fixed ${C>1}$ and any congruence class ${a\ (r)}$ with ${r \in {\mathcal S}_I}$.

The main result of this post is then the following:

Theorem 3 (Type I/II estimate) Let ${\varpi, \delta, \sigma > 0}$ be fixed quantities such that

$\displaystyle 11 \varpi + 3\delta + 2 \sigma < \frac{1}{4} \ \ \ \ \ (7)$

and

$\displaystyle 29\varpi + 5 \delta < \frac{1}{4} \ \ \ \ \ (8)$

and let ${\alpha,\beta}$ be coefficient sequences at scales ${M,N}$ respectively with

$\displaystyle x \ll MN \ll x \ \ \ \ \ (9)$

and

$\displaystyle x^{\frac{1}{2}-\sigma} \ll N \ll M \ll x^{\frac{1}{2}+\sigma} \ \ \ \ \ (10)$

with ${\beta}$ obeying a Siegel-Walfisz theorem. Then for any ${I \subset [1,x^\delta]}$ and any singleton congruence class system ${(\{a_q\})_{q \in {\mathcal S}_I}}$ with controlled multiplicity we have

$\displaystyle \sum_{q \in {\mathcal S}_I: q< x^{1/2+2\varpi}} |\Delta(\alpha \ast \beta; a_q)| \ll x \log^{-A} x.$

The proof of this theorem relies on five basic tools:

• (ii) completion of sums;
• (iii) the Weil conjectures;
• (iv) factorisation of smooth moduli ${q \in {\mathcal S}_I}$; and
• (v) the Cauchy-Schwarz and triangle inequalities (Weyl differencing and the dispersion method).

For the purposes of numerics, it is the interplay between (ii), (iii), and (v) that drives the final conditions (7), (8). The Weil conjectures are the primary source of power savings (${x^{-c}}$ for some fixed ${c>0}$) in the argument, but they need to overcome power losses coming from completion of sums, and also each use of Cauchy-Schwarz tends to halve any power savings present in one’s estimates. Naively, one could thus expect to get better estimates by relying more on the Weil conjectures, and less on completion of sums and on Cauchy-Schwarz.

The purpose of this post is to isolate a combinatorial optimisation problem regarding subset sums; any improvement upon the current known bounds for this problem would lead to numerical improvements for the quantities pursued in the Polymath8 project. (UPDATE: Unfortunately no purely combinatorial improvement is possible, see comments.) We will also record the number-theoretic details of how this combinatorial problem is used in Zhang’s argument establishing bounded prime gaps.

First, some (rough) motivational background, omitting all the number-theoretic details and focusing on the combinatorics. (But readers who just want to see the combinatorial problem can skip the motivation and jump ahead to Lemma 5.) As part of the Polymath8 project we are trying to establish a certain estimate called ${MPZ[\varpi,\delta]}$ for as wide a range of ${\varpi,\delta > 0}$ as possible. Currently the best result we have is:

Theorem 1 (Zhang’s theorem, numerically optimised) ${MPZ[\varpi,\delta]}$ holds whenever ${207\varpi + 43\delta< \frac{1}{4}}$.

Enlarging this region would lead to a better value of certain parameters ${k_0}$, ${H}$ which in turn control the best bound on asymptotic gaps between consecutive primes. See this previous post for more discussion of this. At present, the best value ${k_0=23,283}$ of ${k_0}$ is applied by taking ${(\varpi,\delta)}$ sufficiently close to ${(1/899,71/154628)}$, so improving Theorem 1 in the neighbourhood of this value is particularly desirable.

I’ll state exactly what ${MPZ[\varpi,\delta]}$ is below the fold. For now, suffice to say that it involves a certain number-theoretic function, the von Mangoldt function ${\Lambda}$. To prove the theorem, the first step is to use a certain identity (the Heath-Brown identity) to decompose ${\Lambda}$ into a lot of pieces, which take the form

$\displaystyle \alpha_{1} \ast \ldots \ast \alpha_{n} \ \ \ \ \ (1)$

for some bounded ${n}$ (in Zhang’s paper ${n}$ never exceeds ${20}$) and various weights ${\alpha_{1},\ldots,\alpha_n}$ supported at various scales ${N_1,\ldots,N_n \geq 1}$ that multiply up to approximately ${x}$:

$\displaystyle N_1 \ldots N_n \sim x.$

We can write ${N_i = x^{t_i}}$, thus ignoring negligible errors, ${t_1,\ldots,t_n}$ are non-negative real numbers that add up to ${1}$:

$\displaystyle t_1 + \ldots + t_n = 1.$

A key technical feature of the Heath-Brown identity is that the weight ${\alpha_i}$ associated to sufficiently large values of ${t_i}$ (e.g. ${t_i \geq 1/10}$) are “smooth” in a certain sense; this will be detailed below the fold.

The operation ${\ast}$ is Dirichlet convolution, which is commutative and associative. We can thus regroup the convolution (1) in a number of ways. For instance, given any partition ${\{1,\ldots,n\} = S \cup T}$ into disjoint sets ${S,T}$, we can rewrite (1) as

$\displaystyle \alpha_S \ast \alpha_T$

where ${\alpha_S}$ is the convolution of those ${\alpha_i}$ with ${i \in S}$, and similarly for ${\alpha_T}$.

Zhang’s argument splits into two major pieces, in which certain classes of (1) are established. Cheating a little bit, the following three results are established:

Theorem 2 (Type 0 estimate, informal version) The term (1) gives an acceptable contribution to ${MPZ[\varpi,\delta]}$ whenever

$\displaystyle t_i > \frac{1}{2} + 2 \varpi$

for some ${i}$.

Theorem 3 (Type I/II estimate, informal version) The term (1) gives an acceptable contribution to ${MPZ[\varpi,\delta]}$ whenever one can find a partition ${\{1,\ldots,n\} = S \cup T}$ such that

$\displaystyle \frac{1}{2} - \sigma < \sum_{i \in S} t_i \leq \sum_{i \in T} t_i < \frac{1}{2} + \sigma$

where ${\sigma}$ is a quantity such that

$\displaystyle 11 \varpi + 3\delta + 2 \sigma < \frac{1}{4}.$

Theorem 4 (Type III estimate, informal version) The term (1) gives an acceptable contribution to ${MPZ[\varpi,\delta]}$ whenever one can find ${t_i,t_j,t_k}$ with distinct ${i,j,k \in \{1,\ldots,n\}}$ with

$\displaystyle t_i \leq t_j \leq t_k \leq \frac{1}{2}$

and

$\displaystyle 4t_k + 4t_j + 5t_i > 4 + 16 \varpi + \delta.$

The above assertions are oversimplifications; there are some additional minor smallness hypotheses on ${\varpi,\delta}$ that are needed but at the current (small) values of ${\varpi,\delta}$ under consideration they are not relevant and so will be omitted.

The deduction of Theorem 1 from Theorems 2, 3, 4 is then accomplished from the following, purely combinatorial, lemma:

Lemma 5 (Subset sum lemma) Let ${\varpi,\delta > 0}$ be such that

$\displaystyle 207\varpi + 43\delta < \frac{1}{4}. \ \ \ \ \ (2)$

Let ${t_1,\ldots,t_n}$ be non-negative reals such that

$\displaystyle t_1 + \ldots + t_n = 1.$

Then at least one of the following statements hold:

• (Type 0) There is ${1 \leq i \leq n}$ such that ${t_i > \frac{1}{2} + 2 \varpi}$.
• (Type I/II) There is a partition ${\{1,\ldots,n\} = S \cup T}$ such that

$\displaystyle \frac{1}{2} - \sigma < \sum_{i \in S} t_i \leq \sum_{i \in T} t_i < \frac{1}{2} + \sigma$

where ${\sigma}$ is a quantity such that

$\displaystyle 11 \varpi + 3\delta + 2 \sigma < \frac{1}{4}.$

• (Type III) One can find distinct ${t_i,t_j,t_k}$ with

$\displaystyle t_i \leq t_j \leq t_k \leq \frac{1}{2}$

and

$\displaystyle 4t_k + 4t_j + 5t_i > 4 + 16 \varpi + \delta.$

The purely combinatorial question is whether the hypothesis (2) can be relaxed here to a weaker condition. This would allow us to improve the ranges for Theorem 1 (and hence for the values of ${k_0}$ and ${H}$ alluded to earlier) without needing further improvement on Theorems 2, 3, 4 (although such improvement is also going to be a focus of Polymath8 investigations in the future).

Let us review how this lemma is currently proven. The key sublemma is the following:

Lemma 6 Let ${1/10 < \sigma < 1/2}$, and let ${t_1,\ldots,t_n}$ be non-negative numbers summing to ${1}$. Then one of the following three statements hold:

• (Type 0) There is a ${t_i}$ with ${t_i \geq 1/2 + \sigma}$.
• (Type I/II) There is a partition ${\{1,\ldots,n\} = S \cup T}$ such that

$\displaystyle \frac{1}{2} - \sigma < \sum_{i \in S} t_i \leq \sum_{i \in T} t_i < \frac{1}{2} + \sigma.$

• (Type III) There exist distinct ${i,j,k}$ with ${2\sigma \leq t_i \leq t_j \leq t_k \leq 1/2-\sigma}$ and ${t_i+t_j,t_i+t_k,t_j+t_k \geq 1/2 + \sigma}$.

Proof: Suppose Type I/II never occurs, then every partial sum ${\sum_{i \in S} t_i}$ is either “small” in the sense that it is less than or equal to ${1/2-\sigma}$, or “large” in the sense that it is greater than or equal to ${1/2+\sigma}$, since otherwise we would be in the Type I/II case either with ${S}$ as is and ${T}$ the complement of ${S}$, or vice versa.

Call a summand ${t_i}$ “powerless” if it cannot be used to turn a small partial sum into a large partial sum, thus there are no ${S \subset \{1,\ldots,n\} \backslash \{i\}}$ such that ${\sum_{j \in S} t_j}$ is small and ${t_i + \sum_{j \in S} t_j}$ is large. We then split ${\{1,\ldots,n\} = A \cup B}$ where ${A}$ are the powerless elements and ${B}$ are the powerful elements.

By induction we see that if ${S \subset B}$ and ${\sum_{i \in S} t_i}$ is small, then ${\sum_{i \in S} t_i + \sum_{i \in A} t_i}$ is also small. Thus every sum of powerful summand is either less than ${1/2-\sigma-\sum_{i \in A} t_i}$ or larger than ${1/2+\sigma}$. Since a powerful element must be able to convert a small sum to a large sum (in fact it must be able to convert a small sum of powerful summands to a large sum, by stripping out the powerless summands), we conclude that every powerful element has size greater than ${2\sigma + \sum_{i \in A} t_i}$. We may assume we are not in Type 0, then every powerful summand is at least ${2\sigma + \sum_{i \in A} t_i}$ and at most ${1/2 - \sigma - \sum_{i \in A} t_i}$. In particular, there have to be at least three powerful summands, otherwise ${\sum_{i=1}^n t_i}$ cannot be as large as ${1}$. As ${\sigma > 1/10}$, we have ${4\sigma > 1/2-\sigma}$, and we conclude that the sum of any two powerful summands is large (which, incidentally, shows that there are exactly three powerful summands). Taking ${t_i,t_j,t_k}$ to be three powerful summands in increasing order we land in Type III. $\Box$

Now we see how Lemma 6 implies Lemma 5. Let ${\varpi,\delta}$ be as in Lemma 5. We take ${\sigma}$ almost as large as we can for the Type I/II case, thus we set

$\displaystyle \sigma := \frac{1}{8} - \frac{11}{2} \varpi - \frac{3}{2} \delta - \epsilon \ \ \ \ \ (3)$

for some sufficiently small ${\epsilon>0}$. We observe from (2) that we certainly have

$\displaystyle \sigma > 2 \varpi$

and

$\displaystyle \sigma > \frac{1}{10}$

with plenty of room to spare. We then apply Lemma 6. The Type 0 case of that lemma then implies the Type 0 case of Lemma 5, while the Type I/II case of Lemma 6 also implies the Type I/II case of Lemma 5. Finally, suppose that we are in the Type III case of Lemma 6. Since

$\displaystyle 4t_i + 4t_j + 5 t_k = \frac{5}{2} (t_i+t_k) + \frac{5}{2}(t_j+t_k) + \frac{3}{2} (t_i+t_j)$

we thus have

$\displaystyle 4t_i + 4t_j + 5 t_k \geq \frac{13}{2} (\frac{1}{2}+\sigma)$

and so we will be done if

$\displaystyle \frac{13}{2} (\frac{1}{2}+\sigma) > 4 + 16 \varpi + \delta.$

Inserting (3) and taking ${\epsilon}$ small enough, it suffices to verify that

$\displaystyle \frac{13}{2} (\frac{1}{2}+\frac{1}{8} - \frac{11}{2} \varpi - \frac{3}{2}\delta) > 4 + 16 \varpi + \delta$

but after some computation this is equivalent to (2).

It seems that there is some slack in this computation; some of the conclusions of the Type III case of Lemma 5, in particular, ended up being “wasted”, and it is possible that one did not fully exploit all the partial sums that could be used to create a Type I/II situation. So there may be a way to make improvements through purely combinatorial arguments. (UPDATE: As it turns out, this is sadly not the case: consderation of the case when ${n=4}$, ${t_1 = 1/4 - 3\sigma/2}$, and ${t_2=t_3=t_4 = 1/4+\sigma/2}$ shows that one cannot obtain any further improvement without actually improving the Type I/II and Type III analysis.)

A technical remark: for the application to Theorem 1, it is possible to enforce a bound on the number ${n}$ of summands in Lemma 5. More precisely, we may assume that ${n}$ is an even number of size at most ${n \leq 2K}$ for any natural number ${K}$ we please, at the cost of adding the additioal constraint ${t_i > \frac{1}{K}}$ to the Type III conclusion. Since ${t_i}$ is already at least ${2\sigma}$, which is at least ${\frac{1}{5}}$, one can safely take ${K=5}$, so ${n}$ can be taken to be an even number of size at most ${10}$, which in principle makes the problem of optimising Lemma 5 a fixed linear programming problem. (Zhang takes ${K=10}$, but this appears to be overkill. On the other hand, ${K}$ does not appear to be a parameter that overly influences the final numerical bounds.)

Below the fold I give the number-theoretic details of the combinatorial aspects of Zhang’s argument that correspond to the combinatorial problem described above.

This post is a continuation of the previous post on sieve theory, which is an ongoing part of the Polymath8 project to improve the various parameters in Zhang’s proof that bounded gaps between primes occur infinitely often. Given that the comments on that page are getting quite lengthy, this is also a good opportunity to “roll over” that thread.

We will continue the notation from the previous post, including the concept of an admissible tuple, the use of an asymptotic parameter ${x}$ going to infinity, and a quantity ${w}$ depending on ${x}$ that goes to infinity sufficiently slowly with ${x}$, and ${W := \prod_{p (the ${W}$-trick).

The objective of this portion of the Polymath8 project is to make as efficient as possible the connection between two types of results, which we call ${DHL[k_0,2]}$ and ${MPZ[\varpi,\delta]}$. Let us first state ${DHL[k_0,2]}$, which has an integer parameter ${k_0 \geq 2}$:

Conjecture 1 (${DHL[k_0,2]}$) Let ${{\mathcal H}}$ be a fixed admissible ${k_0}$-tuple. Then there are infinitely many translates ${n+{\mathcal H}}$ of ${{\mathcal H}}$ which contain at least two primes.

Zhang was the first to prove a result of this type with ${k_0 = 3,500,000}$. Since then the value of ${k_0}$ has been lowered substantially; at this time of writing, the current record is ${k_0 = 26,024}$.

There are two basic ways known currently to attain this conjecture. The first is to use the Elliott-Halberstam conjecture ${EH[\theta]}$ for some ${\theta>1/2}$:

Conjecture 2 (${EH[\theta]}$) One has

$\displaystyle \sum_{1 \leq q \leq x^\theta} \sup_{a \in ({\bf Z}/q{\bf Z})^\times} |\sum_{n < x: n = a\ (q)} \Lambda(n) - \frac{1}{\phi(q)} \sum_{n < x} \Lambda(n)|$

$\displaystyle = O( \frac{x}{\log^A x} )$

for all fixed ${A>0}$. Here we use the abbreviation ${n=a\ (q)}$ for ${n=a \hbox{ mod } q}$.

Here of course ${\Lambda}$ is the von Mangoldt function and ${\phi}$ the Euler totient function. It is conjectured that ${EH[\theta]}$ holds for all ${0 < \theta < 1}$, but this is currently only known for ${0 < \theta < 1/2}$, an important result known as the Bombieri-Vinogradov theorem.

In a breakthrough paper, Goldston, Yildirim, and Pintz established an implication of the form

$\displaystyle EH[\theta] \implies DHL[k_0,2] \ \ \ \ \ (1)$

for any ${1/2 < \theta < 1}$, where ${k_0 = k_0(\theta)}$ depends on ${\theta}$. This deduction was very recently optimised by Farkas, Pintz, and Revesz and also independently in the comments to the previous blog post, leading to the following implication:

Theorem 3 (EH implies DHL) Let ${1/2 < \theta < 1}$ be a real number, and let ${k_0 \geq 2}$ be an integer obeying the inequality

$\displaystyle 2\theta > \frac{j_{k_0-2}^2}{k_0(k_0-1)}, \ \ \ \ \ (2)$

where ${j_n}$ is the first positive zero of the Bessel function ${J_n(x)}$. Then ${EH[\theta]}$ implies ${DHL[k_0,2]}$.

Note that the right-hand side of (2) is larger than ${1}$, but tends asymptotically to ${1}$ as ${k_0 \rightarrow \infty}$. We give an alternate proof of Theorem 3 below the fold.

Implications of the form Theorem 3 were modified by Motohashi and Pintz, which in our notation replaces ${EH[\theta]}$ by an easier conjecture ${MPZ[\varpi,\delta]}$ for some ${0 < \varpi < 1/4}$ and ${0 < \delta < 1/4+\varpi}$, at the cost of degrading the sufficient condition (2) slightly. In our notation, this conjecture takes the following form for each choice of parameters ${\varpi,\delta}$:

Conjecture 4 (${MPZ[\varpi,\delta]}$) Let ${{\mathcal H}}$ be a fixed ${k_0}$-tuple (not necessarily admissible) for some fixed ${k_0 \geq 2}$, and let ${b\ (W)}$ be a primitive residue class. Then

$\displaystyle \sum_{q \in {\mathcal S}_I: q< x^{1/2+2\varpi}} \sum_{a \in C(q)} |\Delta_{b,W}(\Lambda; q,a)| = O( x \log^{-A} x) \ \ \ \ \ (3)$

for any fixed ${A>0}$, where ${I = (w,x^{\delta})}$, ${{\mathcal S}_I}$ are the square-free integers whose prime factors lie in ${I}$, and ${\Delta_{b,W}(\Lambda;q,a)}$ is the quantity

$\displaystyle \Delta_{b,W}(\Lambda;q,a) := | \sum_{x \leq n \leq 2x: n=b\ (W); n = a\ (q)} \Lambda(n) \ \ \ \ \ (4)$

$\displaystyle - \frac{1}{\phi(q)} \sum_{x \leq n \leq 2x: n = b\ (W)} \Lambda(n)|.$

and ${C(q)}$ is the set of congruence classes

$\displaystyle C(q) := \{ a \in ({\bf Z}/q{\bf Z})^\times: P(a) = 0 \}$

and ${P}$ is the polynomial

$\displaystyle P(a) := \prod_{h \in {\mathcal H}} (a+h).$

This is a weakened version of the Elliott-Halberstam conjecture:

Proposition 5 (EH implies MPZ) Let ${0 < \varpi < 1/4}$ and ${0 < \delta < 1/4+\varpi}$. Then ${EH[1/2+2\varpi+\epsilon]}$ implies ${MPZ[\varpi,\delta]}$ for any ${\epsilon>0}$. (In abbreviated form: ${EH[1/2+2\varpi+]}$ implies ${MPZ[\varpi,\delta]}$.)

In particular, since ${EH[\theta]}$ is conjecturally true for all ${0 < \theta < 1/2}$, we conjecture ${MPZ[\varpi,\delta]}$ to be true for all ${0 < \varpi < 1/4}$ and ${0<\delta<1/4+\varpi}$.

Proof: Define

$\displaystyle E(q) := \sup_{a \in ({\bf Z}/q{\bf Z})^\times} |\sum_{x \leq n \leq 2x: n = a\ (q)} \Lambda(n) - \frac{1}{\phi(q)} \sum_{x \leq n \leq 2x} \Lambda(n)|$

then the hypothesis ${EH[1/2+2\varpi+\epsilon]}$ (applied to ${x}$ and ${2x}$ and then subtracting) tells us that

$\displaystyle \sum_{1 \leq q \leq Wx^{1/2+2\varpi}} E(q) \ll x \log^{-A} x$

for any fixed ${A>0}$. From the Chinese remainder theorem and the Siegel-Walfisz theorem we have

$\displaystyle \sup_{a \in ({\bf Z}/q{\bf Z})^\times} \Delta_{b,W}(\Lambda;q,a) \ll E(qW) + \frac{1}{\phi(q)} x \log^{-A} x$

for any ${q}$ coprime to ${W}$ (and in particular for ${q \in {\mathcal S}_I}$). Since ${|C(q)| \leq k_0^{\Omega(q)}}$, where ${\Omega(q)}$ is the number of prime divisors of ${q}$, we can thus bound the left-hand side of (3) by

$\displaystyle \ll \sum_{q \in {\mathcal S}_I: q< x^{1/2+2\varpi}} k_0^{\Omega(q)} E(qW) + k_0^{\Omega(q)} \frac{1}{\phi(q)} x \log^{-A} x.$

The contribution of the second term is ${O(x \log^{-A+O(1)} x)}$ by standard estimates (see Proposition 8 below). Using the very crude bound

$\displaystyle E(q) \ll \frac{1}{\phi(q)} x \log x$

and standard estimates we also have

$\displaystyle \sum_{q \in {\mathcal S}_I: q< x^{1/2+2\varpi}} k_0^{2\Omega(q)} E(qW) \ll x \log^{O(1)} A$

and the claim now follows from the Cauchy-Schwarz inequality. $\Box$

In practice, the conjecture ${MPZ[\varpi,\delta]}$ is easier to prove than ${EH[1/2+2\varpi+]}$ due to the restriction of the residue classes ${a}$ to ${C(q)}$, and also the restriction of the modulus ${q}$ to ${x^\delta}$-smooth numbers. Zhang proved ${MPZ[\varpi,\varpi]}$ for any ${0 < \varpi < 1/1168}$. More recently, our Polymath8 group has analysed Zhang’s argument (using in part a corrected version of the analysis of a recent preprint of Pintz) to obtain ${MPZ[\varpi,\delta]}$ whenever ${\delta, \varpi > 0}$ are such that

$\displaystyle 207\varpi + 43\delta < \frac{1}{4}.$

The work of Motohashi and Pintz, and later Zhang, implicitly describe arguments that allow one to deduce ${DHL[k_0,2]}$ from ${MPZ[\varpi,\delta]}$ provided that ${k_0}$ is sufficiently large depending on ${\varpi,\delta}$. The best implication of this sort that we have been able to verify thus far is the following result, established in the previous post:

Theorem 6 (MPZ implies DHL) Let ${0 < \varpi < 1/4}$, ${0 < \delta < 1/4+\varpi}$, and let ${k_0 \geq 2}$ be an integer obeying the constraint

$\displaystyle 1+4\varpi > \frac{j_{k_0-2}^2}{k_0(k_0-1)} (1+\kappa) \ \ \ \ \ (5)$

where ${\kappa}$ is the quantity

$\displaystyle \kappa := \sum_{1 \leq n < \frac{1+4\varpi}{2\delta}} (1 - \frac{2n \delta}{1 + 4\varpi})^{k_0/2} \prod_{j=1}^{n} (1 + 3k_0 \log(1+\frac{1}{j})) ).$

Then ${MPZ[\varpi,\delta]}$ implies ${DHL[k_0,2]}$.

This complicated version of ${\kappa}$ is roughly of size ${3 \log(2) k_0 \exp( - k_0 \delta)}$. It is unlikely to be optimal; the work of Motohashi-Pintz and Pintz suggests that it can essentially be improved to ${\frac{1}{\delta} \exp(-k_0 \delta)}$, but currently we are unable to verify this claim. One of the aims of this post is to encourage further discussion as to how to improve the ${\kappa}$ term in results such as Theorem 6.

We remark that as (5) is an open condition, it is unaffected by infinitesimal modifications to ${\varpi,\delta}$, and so we do not ascribe much importance to such modifications (e.g. replacing ${\varpi}$ by ${\varpi-\epsilon}$ for some arbitrarily small ${\epsilon>0}$).

The known deductions of ${DHL[k_0,2]}$ from claims such as ${EH[\theta]}$ or ${MPZ[\varpi,\delta]}$ rely on the following elementary observation of Goldston, Pintz, and Yildirim (essentially a weighted pigeonhole principle), which we have placed in “${W}$-tricked form”:

Lemma 7 (Criterion for DHL) Let ${k_0 \geq 2}$. Suppose that for each fixed admissible ${k_0}$-tuple ${{\mathcal H}}$ and each congruence class ${b\ (W)}$ such that ${b+h}$ is coprime to ${W}$ for all ${h \in {\mathcal H}}$, one can find a non-negative weight function ${\nu: {\bf N} \rightarrow {\bf R}^+}$, fixed quantities ${\alpha,\beta > 0}$, a quantity ${A>0}$, and a fixed positive power ${R}$ of ${x}$ such that one has the upper bound

$\displaystyle \sum_{x \leq n \leq 2x: n = b\ (W)} \nu(n) \leq (\alpha+o(1)) A\frac{x}{W}, \ \ \ \ \ (6)$

the lower bound

$\displaystyle \sum_{x \leq n \leq 2x: n = b\ (W)} \nu(n) \theta(n+h_i) \geq (\beta-o(1)) A\frac{x}{W} \log R \ \ \ \ \ (7)$

for all ${h_i \in {\mathcal H}}$, and the key inequality

$\displaystyle \frac{\log R}{\log x} > \frac{1}{k_0} \frac{\alpha}{\beta} \ \ \ \ \ (8)$

holds. Then ${DHL[k_0,2]}$ holds. Here ${\theta(n)}$ is defined to equal ${\log n}$ when ${n}$ is prime and ${0}$ otherwise.

Proof: Consider the quantity

$\displaystyle \sum_{x \leq n \leq 2x: n = b\ (W)} \nu(n) (\sum_{h \in {\mathcal H}} \theta(n+h) - \log(3x)). \ \ \ \ \ (9)$

By (6), (7), this quantity is at least

$\displaystyle k_0 \beta A\frac{x}{W} \log R - \alpha \log(3x) A\frac{x}{W} - o(A\frac{x}{W} \log x).$

By (8), this expression is positive for all sufficiently large ${x}$. On the other hand, (9) can only be positive if at least one summand is positive, which only can happen when ${n+{\mathcal H}}$ contains at least two primes for some ${x \leq n \leq 2x}$ with ${n=b\ (W)}$. Letting ${x \rightarrow \infty}$ we obtain ${DHL[k_0,2]}$ as claimed. $\Box$

In practice, the quantity ${R}$ (referred to as the sieve level) is a power of ${x}$ such as ${x^{\theta/2}}$ or ${x^{1/4+\varpi}}$, and reflects the strength of the distribution hypothesis ${EH[\theta]}$ or ${MPZ[\varpi,\delta]}$ that is available; the quantity ${R}$ will also be a key parameter in the definition of the sieve weight ${\nu}$. The factor ${A}$ reflects the order of magnitude of the expected density of ${\nu}$ in the residue class ${b\ (W)}$; it could be absorbed into the sieve weight ${\nu}$ by dividing that weight by ${A}$, but it is convenient to not enforce such a normalisation so as not to clutter up the formulae. In practice, ${A}$ will some combination of ${\frac{\phi(W)}{W}}$ and ${\log R}$.

Once one has decided to rely on Lemma 7, the next main task is to select a good weight ${\nu}$ for which the ratio ${\alpha/\beta}$ is as small as possible (and for which the sieve level ${R}$ is as large as possible. To ensure non-negativity, we use the Selberg sieve

$\displaystyle \nu = \lambda^2, \ \ \ \ \ (10)$

where ${\lambda(n)}$ takes the form

$\displaystyle \lambda(n) = \sum_{d \in {\mathcal S}_I: d|P(n)} \mu(d) a_d$

for some weights ${a_d \in {\bf R}}$ vanishing for ${d>R}$ that are to be chosen, where ${I \subset (w,+\infty)}$ is an interval and ${P}$ is the polynomial ${P(n) := \prod_{h \in {\mathcal H}} (n+h)}$. If the distribution hypothesis is ${EH[\theta]}$, one takes ${R := x^{\theta/2}}$ and ${I := (w,+\infty)}$; if the distribution hypothesis is instead ${MPZ[\varpi,\delta]}$, one takes ${R := x^{1/4+\varpi}}$ and ${I := (w,x^\delta)}$.

One has a useful amount of flexibility in selecting the weights ${a_d}$ for the Selberg sieve. The original work of Goldston, Pintz, and Yildirim, as well as the subsequent paper of Zhang, the choice

$\displaystyle a_d := \log(\frac{R}{d})_+^{k_0+\ell_0}$

is used for some additional parameter ${\ell_0 > 0}$ to be optimised over. More generally, one can take

$\displaystyle a_d := g( \frac{\log d}{\log R} )$

for some suitable (in particular, sufficiently smooth) cutoff function ${g: {\bf R} \rightarrow {\bf R}}$. We will refer to this choice of sieve weights as the “analytic Selberg sieve”; this is the choice used in the analysis in the previous post.

However, there is a slight variant choice of sieve weights that one can use, which I will call the “elementary Selberg sieve”, and it takes the form

$\displaystyle a_d := \frac{1}{\Phi(d) \Delta(d)} \sum_{q \in {\mathcal S}_I: (q,d)=1} \frac{1}{\Phi(q)} f'( \frac{\log dq}{\log R}) \ \ \ \ \ (11)$

for a sufficiently smooth function ${f: {\bf R} \rightarrow {\bf R}}$, where

$\displaystyle \Phi(d) := \prod_{p|d} \frac{p-k_0}{k_0}$

for ${d \in {\mathcal S}_I}$ is a ${k_0}$-variant of the Euler totient function, and

$\displaystyle \Delta(d) := \prod_{p|d} \frac{k_0}{p} = \frac{k_0^{\Omega(d)}}{d}$

for ${d \in {\mathcal S}_I}$ is a ${k_0}$-variant of the function ${1/d}$. (The derivative on the ${f}$ cutoff is convenient for computations, as will be made clearer later in this post.) This choice of weights ${a_d}$ may seem somewhat arbitrary, but it arises naturally when considering how to optimise the quadratic form

$\displaystyle \sum_{d_1,d_2 \in {\mathcal S}_I} \mu(d_1) a_{d_1} \mu(d_2) a_{d_2} \Delta([d_1,d_2])$

(which arises naturally in the estimation of ${\alpha}$ in (6)) subject to a fixed value of ${a_1}$ (which morally is associated to the estimation of ${\beta}$ in (7)); this is discussed in any sieve theory text as part of the general theory of the Selberg sieve, e.g. Friedlander-Iwaniec.

The use of the elementary Selberg sieve for the bounded prime gaps problem was studied by Motohashi and Pintz. Their arguments give an alternate derivation of ${DHL[k_0,2]}$ from ${MPZ[\varpi,\theta]}$ for ${k_0}$ sufficiently large, although unfortunately we were not able to confirm some of their calculations regarding the precise dependence of ${k_0}$ on ${\varpi,\theta}$, and in particular we have not yet been able to improve upon the specific criterion in Theorem 6 using the elementary sieve. However it is quite plausible that such improvements could become available with additional arguments.

Below the fold we describe how the elementary Selberg sieve can be used to reprove Theorem 3, and discuss how they could potentially be used to improve upon Theorem 6. (But the elementary Selberg sieve and the analytic Selberg sieve are in any event closely related; see the appendix of this paper of mine with Ben Green for some further discussion.) For the purposes of polymath8, either developing the elementary Selberg sieve or continuing the analysis of the analytic Selberg sieve from the previous post would be a relevant topic of conversation in the comments to this post.

In a recent paper, Yitang Zhang has proven the following theorem:

Theorem 1 (Bounded gaps between primes) There exists a natural number ${H}$ such that there are infinitely many pairs of distinct primes ${p,q}$ with ${|p-q| \leq H}$.

Zhang obtained the explicit value of ${70,000,000}$ for ${H}$. A polymath project has been proposed to lower this value and also to improve the understanding of Zhang’s results; as of this time of writing, the current “world record” is ${H = 4,802,222}$ (and the link given should stay updated with the most recent progress.

Zhang’s argument naturally divides into three steps, which we describe in reverse order. The last step, which is the most elementary, is to deduce the above theorem from the following weak version of the Dickson-Hardy-Littlewood (DHL) conjecture for some ${k_0}$:

Theorem 2 (${DHL[k_0,2]}$) Let ${{\mathcal H}}$ be an admissible ${k_0}$-tuple, that is to say a tuple of ${k_0}$ distinct integers which avoids at least one residue class mod ${p}$ for every prime ${p}$. Then there are infinitely many translates of ${{\mathcal H}}$ that contain at least two primes.

Zhang obtained ${DHL[k_0,2]}$ for ${k_0 = 3,500,000}$. The current best value of ${k_0}$ is ${341,640}$, as discussed in this previous blog post. To get from ${DHL[k_0,2]}$ to Theorem 1, one has to exhibit an admissible ${k_0}$-tuple of diameter at most ${H}$. For instance, with ${k_0 = 341,640}$, the narrowest admissible ${k_0}$-tuple that we can construct has diameter ${4,802,222}$, which explains the current world record. There is an active discussion on trying to improve the constructions of admissible tuples at this blog post; it is conceivable that some combination of computer search and clever combinatorial constructions could obtain slightly better values of ${H}$ for a given value of ${k_0}$. The relationship between ${H}$ and ${k_0}$ is approximately of the form ${H \approx k_0 \log k_0}$ (and a classical estimate of Montgomery and Vaughan tells us that we cannot make ${H}$ much narrower than ${\frac{1}{2} k_0 \log k_0}$, see this previous post for some related discussion).

The second step in Zhang’s argument, which is somewhat less elementary (relying primarily on the sieve theory of Goldston, Yildirim, Pintz, and Motohashi), is to deduce ${DHL[k_0,2]}$ from a certain conjecture ${MPZ[\varpi,\delta]}$ for some ${\varpi,\delta > 0}$. Here is one formulation of the conjecture, more or less as (implicitly) stated in Zhang’s paper:

Conjecture 3 (${MPZ[\varpi,\delta]}$) Let ${{\mathcal H}}$ be an admissible tuple, let ${h_i}$ be an element of ${{\mathcal H}}$, let ${x}$ be a large parameter, and define

$\displaystyle D := x^{1/4+\varpi},$

$\displaystyle {\mathcal P} := \prod_{p: p < x^{\delta}} p,$

$\displaystyle P(n) := \prod_{h \in {\mathcal H}} (n+h),$

$\displaystyle C_i(d) := \{ c \in {\bf Z}/d{\bf Z}: (c,d) = 1; P(c-h_i) = 0 \hbox{ mod } d \}$

for any natural number ${d}$, and

$\displaystyle \Delta(\gamma;d,c) = \sum_{x \leq n \leq 2x: n = c \hbox{ mod } d} \gamma(n) - \frac{1}{\varphi(d)} \sum_{x \leq n \leq 2x: (n,d) = 1} \gamma(n)$

for any function ${\gamma: {\bf N} \rightarrow {\bf C}}$. Let ${\theta(n)}$ equal ${\log p}$ when ${n}$ is a prime ${p}$, and ${\theta(n)=0}$ otherwise. Then one has

$\displaystyle \sum_{d < D^2; d|{\mathcal P}} \sum_{c \in C_i(d)} |\Delta(\theta; d, c )| \ll x \log^{-A} x$

for any fixed ${A > 0}$.

Note that this is slightly different from the formulation of ${MPZ[\varpi]}$ in the previous post; I have reverted to Zhang’s formulation here as the primary purpose of this post is to read through Zhang’s paper. However, I have distinguished two separate parameters here ${\varpi,\delta}$ instead of one, as it appears that there is some room to optimise by making these two parameters different.

In the previous post, I described how one can deduce ${DHL[k_0,2]}$ from ${MPZ[\varpi,\delta]}$. Ignoring an exponentially small error ${\kappa}$, it turns out that one can deduce ${DHL[k_0,2]}$ from ${MPZ[\varpi,\delta]}$ whenever one can find a smooth function ${g: [0,1] \rightarrow {\bf R}}$ vanishing to order at least ${k_0}$ at ${1}$ such that

$\displaystyle k_0 \int_0^1 g^{(k_0-1)}(x)^2 \frac{x^{k_0-2}}{(k_0-2)!}\ dx > \frac{4}{1+4\varpi} \int_0^1 g^{(k_0)}(x)^2 \frac{x^{k_0-1}}{(k_0-1)!}\ dx.$

By selecting ${g(x) := \frac{1}{(k_0+l_0)!} (1-x)^{k_0+l_0}}$ for a real parameter ${l_0>0}$ to optimise over, and ignoring the technical ${\kappa}$ term alluded to previously (which is the only quantity here that depends on ${\delta}$), this gives ${DHL[k_0,2]}$ from ${MPZ[\varpi,\delta]}$ whenever

$\displaystyle k_0 > (\sqrt{1+4\varpi} - 1)^{-2} \ \ \ \ \ (1)$

It may be possible to do better than this by choosing smarter choices for ${g}$, or performing some sort of numerical calculus of variations or spectral theory; people interested in this topic are invited to discuss it in the previous post.

The final, and deepest, part of Zhang’s work is the following theorem (Theorem 2 from Zhang’s paper, whose proof occupies Sections 6-13 of that paper, and is about 32 pages long):

Theorem 4 (Zhang) ${MPZ[\varpi,\varpi]}$ is true for all ${0 < \varpi \leq \frac{1}{1168}}$.

The significance of the fraction ${1/1168}$ is that Zhang’s argument proceeds for a general choice of ${\varpi > 0}$, but ultimately the argument only closes if one has

$\displaystyle \frac{31}{32} + 36 \varpi \leq 1 - \frac{\varpi}{2}$

(see page 53 of Zhang) which is equivalent to ${\varpi \leq 1/1168}$. Plugging in this choice of ${\varpi}$ into (1) then gives ${DHL[k_0,2]}$ with ${k_0 = 341,640}$ as stated previously.

Improving the value of ${\varpi}$ in Theorem 4 would lead to improvements in ${k_0}$ and then ${H}$ as discussed above. The purpose of this reading seminar is then twofold:

1. Going through Zhang’s argument in order to improve the value of ${\varpi}$ (perhaps by decreasing ${\delta}$); and
2. Gaining a more holistic understanding of Zhang’s argument (and perhaps to find some more “global” improvements to that argument), as well as related arguments such as the prior work of Bombieri, Fouvry, Friedlander, and Iwaniec that Zhang’s work is based on.

In addition to reading through Zhang’s paper, the following material is likely to be relevant:

I envisage a loose, unstructured format for the reading seminar. In the comments below, I am going to post my own impressions, questions, and remarks as I start going through the material, and I encourage other participants to do the same. The most obvious thing to do is to go through Zhang’s Sections 6-13 in linear order, but it may make sense for some participants to follow a different path. One obvious near-term goal is to carefully go through Zhang’s arguments for ${MPZ[\varpi,\delta]}$ instead of ${MPZ[1/1168,1/1168]}$, and record exactly how various exponents depend on ${\varpi,\delta}$, and what inequalities these parameters need to obey for the arguments to go through. It may be that this task can be done at a fairly superficial level without the need to carefully go through the analytic number theory estimates in that paper, though of course we should also be doing that as well. This may lead to some “cheap” optimisations of ${\varpi}$ which can then propagate to improved bounds on ${k_0}$ and ${H}$ thanks to the other parts of the Polymath project.

Everyone is welcome to participate in this project (as per the usual polymath rules); however I would request that “meta” comments about the project that are not directly related to the task of reading Zhang’s paper and related works be placed instead on the polymath proposal page. (Similarly, comments regarding the optimisation of ${k_0}$ given ${\varpi}$ and ${\delta}$ should be placed at this post, while comments on the optimisation of ${H}$ given ${k_0}$ should be given at this post. On the other hand, asking questions about Zhang’s paper, even (or especially!) “dumb” ones, would be very appropriate for this post and such questions are encouraged.

Suppose one is given a ${k_0}$-tuple ${{\mathcal H} = (h_1,\ldots,h_{k_0})}$ of ${k_0}$ distinct integers for some ${k_0 \geq 1}$, arranged in increasing order. When is it possible to find infinitely many translates ${n + {\mathcal H} =(n+h_1,\ldots,n+h_{k_0})}$ of ${{\mathcal H}}$ which consists entirely of primes? The case ${k_0=1}$ is just Euclid’s theorem on the infinitude of primes, but the case ${k_0=2}$ is already open in general, with the ${{\mathcal H} = (0,2)}$ case being the notorious twin prime conjecture.

On the other hand, there are some tuples ${{\mathcal H}}$ for which one can easily answer the above question in the negative. For instance, the only translate of ${(0,1)}$ that consists entirely of primes is ${(2,3)}$, basically because each translate of ${(0,1)}$ must contain an even number, and the only even prime is ${2}$. More generally, if there is a prime ${p}$ such that ${{\mathcal H}}$ meets each of the ${p}$ residue classes ${0 \hbox{ mod } p, 1 \hbox{ mod } p, \ldots, p-1 \hbox{ mod } p}$, then every translate of ${{\mathcal H}}$ contains at least one multiple of ${p}$; since ${p}$ is the only multiple of ${p}$ that is prime, this shows that there are only finitely many translates of ${{\mathcal H}}$ that consist entirely of primes.

To avoid this obstruction, let us call a ${k_0}$-tuple ${{\mathcal H}}$ admissible if it avoids at least one residue class ${\hbox{ mod } p}$ for each prime ${p}$. It is easy to check for admissibility in practice, since a ${k_0}$-tuple is automatically admissible in every prime ${p}$ larger than ${k_0}$, so one only needs to check a finite number of primes in order to decide on the admissibility of a given tuple. For instance, ${(0,2)}$ or ${(0,2,6)}$ are admissible, but ${(0,2,4)}$ is not (because it covers all the residue classes modulo ${3}$). We then have the famous Hardy-Littlewood prime tuples conjecture:

Conjecture 1 (Prime tuples conjecture, qualitative form) If ${{\mathcal H}}$ is an admissible ${k_0}$-tuple, then there exists infinitely many translates of ${{\mathcal H}}$ that consist entirely of primes.

This conjecture is extremely difficult (containing the twin prime conjecture, for instance, as a special case), and in fact there is no explicitly known example of an admissible ${k_0}$-tuple with ${k_0 \geq 2}$ for which we can verify this conjecture (although, thanks to the recent work of Zhang, we know that ${(0,d)}$ satisfies the conclusion of the prime tuples conjecture for some ${0 < d < 70,000,000}$, even if we can’t yet say what the precise value of ${d}$ is).

Actually, Hardy and Littlewood conjectured a more precise version of Conjecture 1. Given an admissible ${k_0}$-tuple ${{\mathcal H} = (h_1,\ldots,h_{k_0})}$, and for each prime ${p}$, let ${\nu_p = \nu_p({\mathcal H}) := |{\mathcal H} \hbox{ mod } p|}$ denote the number of residue classes modulo ${p}$ that ${{\mathcal H}}$ meets; thus we have ${1 \leq \nu_p \leq p-1}$ for all ${p}$ by admissibility, and also ${\nu_p = k_0}$ for all ${p>h_{k_0}-h_1}$. We then define the singular series ${{\mathfrak G} = {\mathfrak G}({\mathcal H})}$ associated to ${{\mathcal H}}$ by the formula

$\displaystyle {\mathfrak G} := \prod_{p \in {\mathcal P}} \frac{1-\frac{\nu_p}{p}}{(1-\frac{1}{p})^{k_0}}$

where ${{\mathcal P} = \{2,3,5,\ldots\}}$ is the set of primes; by the previous discussion we see that the infinite product in ${{\mathfrak G}}$ converges to a finite non-zero number.

We will also need some asymptotic notation (in the spirit of “cheap nonstandard analysis“). We will need a parameter ${x}$ that one should think of going to infinity. Some mathematical objects (such as ${{\mathcal H}}$ and ${k_0}$) will be independent of ${x}$ and referred to as fixed; but unless otherwise specified we allow all mathematical objects under consideration to depend on ${x}$. If ${X}$ and ${Y}$ are two such quantities, we say that ${X = O(Y)}$ if one has ${|X| \leq CY}$ for some fixed ${C}$, and ${X = o(Y)}$ if one has ${|X| \leq c(x) Y}$ for some function ${c(x)}$ of ${x}$ (and of any fixed parameters present) that goes to zero as ${x \rightarrow \infty}$ (for each choice of fixed parameters).

Conjecture 2 (Prime tuples conjecture, quantitative form) Let ${k_0 \geq 1}$ be a fixed natural number, and let ${{\mathcal H}}$ be a fixed admissible ${k_0}$-tuple. Then the number of natural numbers ${n < x}$ such that ${n+{\mathcal H}}$ consists entirely of primes is ${({\mathfrak G} + o(1)) \frac{x}{\log^{k_0} x}}$.

Thus, for instance, if Conjecture 2 holds, then the number of twin primes less than ${x}$ should equal ${(2 \Pi_2 + o(1)) \frac{x}{\log^2 x}}$, where ${\Pi_2}$ is the twin prime constant

$\displaystyle \Pi_2 := \prod_{p \in {\mathcal P}: p>2} (1 - \frac{1}{(p-1)^2}) = 0.6601618\ldots.$

As this conjecture is stronger than Conjecture 1, it is of course open. However there are a number of partial results on this conjecture. For instance, this conjecture is known to be true if one introduces some additional averaging in ${{\mathcal H}}$; see for instance this previous post. From the methods of sieve theory, one can obtain an upper bound of ${(C_{k_0} {\mathfrak G} + o(1)) \frac{x}{\log^{k_0} x}}$ for the number of ${n < x}$ with ${n + {\mathcal H}}$ all prime, where ${C_{k_0}}$ depends only on ${k_0}$. Sieve theory can also give analogues of Conjecture 2 if the primes are replaced by a suitable notion of almost prime (or more precisely, by a weight function concentrated on almost primes).

Another type of partial result towards Conjectures 1, 2 come from the results of Goldston-Pintz-Yildirim, Motohashi-Pintz, and of Zhang. Following the notation of this recent paper of Pintz, for each ${k_0>2}$, let ${DHL[k_0,2]}$ denote the following assertion (DHL stands for “Dickson-Hardy-Littlewood”):

Conjecture 3 (${DHL[k_0,2]}$) Let ${{\mathcal H}}$ be a fixed admissible ${k_0}$-tuple. Then there are infinitely many translates ${n+{\mathcal H}}$ of ${{\mathcal H}}$ which contain at least two primes.

This conjecture gets harder as ${k_0}$ gets smaller. Note for instance that ${DHL[2,2]}$ would imply all the ${k_0=2}$ cases of Conjecture 1, including the twin prime conjecture. More generally, if one knew ${DHL[k_0,2]}$ for some ${k_0}$, then one would immediately conclude that there are an infinite number of pairs of consecutive primes of separation at most ${H(k_0)}$, where ${H(k_0)}$ is the minimal diameter ${h_{k_0}-h_1}$ amongst all admissible ${k_0}$-tuples ${{\mathcal H}}$. Values of ${H(k_0)}$ for small ${k_0}$ can be found at this link (with ${H(k_0)}$ denoted ${w}$ in that page). For large ${k_0}$, the best upper bounds on ${H(k_0)}$ have been found by using admissible ${k_0}$-tuples ${{\mathcal H}}$ of the form

$\displaystyle {\mathcal H} = ( - p_{m+\lfloor k_0/2\rfloor - 1}, \ldots, - p_{m+1}, -1, +1, p_{m+1}, \ldots, p_{m+\lfloor (k_0+1)/2\rfloor - 1} )$

where ${p_n}$ denotes the ${n^{th}}$ prime and ${m}$ is a parameter to be optimised over (in practice it is an order of magnitude or two smaller than ${k_0}$); see this blog post for details. The upshot is that one can bound ${H(k_0)}$ for large ${k_0}$ by a quantity slightly smaller than ${k_0 \log k_0}$ (and the large sieve inequality shows that this is sharp up to a factor of two, see e.g. this previous post for more discussion).

In a key breakthrough, Goldston, Pintz, and Yildirim were able to establish the following conditional result a few years ago:

Theorem 4 (Goldston-Pintz-Yildirim) Suppose that the Elliott-Halberstam conjecture ${EH[\theta]}$ is true for some ${1/2 < \theta < 1}$. Then ${DHL[k_0,2]}$ is true for some finite ${k_0}$. In particular, this establishes an infinite number of pairs of consecutive primes of separation ${O(1)}$.

The dependence of constants between ${k_0}$ and ${\theta}$ given by the Goldston-Pintz-Yildirim argument is basically of the form ${k_0 \sim (\theta-1/2)^{-2}}$. (UPDATE: as recently observed by Farkas, Pintz, and Revesz, this relationship can be improved to ${k_0 \sim (\theta-1/2)^{-3/2}}$.)

Unfortunately, the Elliott-Halberstam conjecture (which we will state properly below) is only known for ${\theta<1/2}$, an important result known as the Bombieri-Vinogradov theorem. If one uses the Bombieri-Vinogradov theorem instead of the Elliott-Halberstam conjecture, Goldston, Pintz, and Yildirim were still able to show the highly non-trivial result that there were infinitely many pairs ${p_{n+1},p_n}$ of consecutive primes with ${(p_{n+1}-p_n) / \log p_n \rightarrow 0}$ (actually they showed more than this; see e.g. this survey of Soundararajan for details).

Actually, the full strength of the Elliott-Halberstam conjecture is not needed for these results. There is a technical specialisation of the Elliott-Halberstam conjecture which does not presently have a commonly accepted name; I will call it the Motohashi-Pintz-Zhang conjecture ${MPZ[\varpi]}$ in this post, where ${0 < \varpi < 1/4}$ is a parameter. We will define this conjecture more precisely later, but let us remark for now that ${MPZ[\varpi]}$ is a consequence of ${EH[\frac{1}{2}+2\varpi]}$.

We then have the following two theorems. Firstly, we have the following strengthening of Theorem 4:

Theorem 5 (Motohashi-Pintz-Zhang) Suppose that ${MPZ[\varpi]}$ is true for some ${0 < \varpi < 1/4}$. Then ${DHL[k_0,2]}$ is true for some ${k_0}$.

A version of this result (with a slightly different formulation of ${MPZ[\varpi]}$) appears in this paper of Motohashi and Pintz, and in the paper of Zhang, Theorem 5 is proven for the concrete values ${\varpi = 1/1168}$ and ${k_0 = 3,500,000}$. We will supply a self-contained proof of Theorem 5 below the fold, the constants upon those in Zhang’s paper (in particular, for ${\varpi = 1/1168}$, we can take ${k_0}$ as low as ${341,640}$, with further improvements on the way). As with Theorem 4, we have an inverse quadratic relationship ${k_0 \sim \varpi^{-2}}$.

In his paper, Zhang obtained for the first time an unconditional advance on ${MPZ[\varpi]}$:

Theorem 6 (Zhang) ${MPZ[\varpi]}$ is true for all ${0 < \varpi \leq 1/1168}$.

This is a deep result, building upon the work of Fouvry-Iwaniec, Friedlander-Iwaniec and BombieriFriedlanderIwaniec which established results of a similar nature to ${MPZ[\varpi]}$ but simpler in some key respects. We will not discuss this result further here, except to say that they rely on the (higher-dimensional case of the) Weil conjectures, which were famously proven by Deligne using methods from l-adic cohomology. Also, it was believed among at least some experts that the methods of Bombieri, Fouvry, Friedlander, and Iwaniec were not quite strong enough to obtain results of the form ${MPZ[\varpi]}$, making Theorem 6 a particularly impressive achievement.

Combining Theorem 6 with Theorem 5 we obtain ${DHL[k_0,2]}$ for some finite ${k_0}$; Zhang obtains this for ${k_0 = 3,500,000}$ but as detailed below, this can be lowered to ${k_0 = 341,640}$. This in turn gives infinitely many pairs of consecutive primes of separation at most ${H(k_0)}$. Zhang gives a simple argument that bounds ${H(3,500,000)}$ by ${70,000,000}$, giving his famous result that there are infinitely many pairs of primes of separation at most ${70,000,000}$; by being a bit more careful (as discussed in this post) one can lower the upper bound on ${H(3,500,000)}$ to ${57,554,086}$, and if one instead uses the newer value ${k_0 = 341,640}$ for ${k_0}$ one can instead use the bound ${H(341,640) \leq 4,982,086}$. (Many thanks to Scott Morrison for these numerics.) UPDATE: These values are now obsolete; see this web page for the latest bounds.

In this post we would like to give a self-contained proof of both Theorem 4 and Theorem 5, which are both sieve-theoretic results that are mainly elementary in nature. (But, as stated earlier, we will not discuss the deepest new result in Zhang’s paper, namely Theorem 6.) Our presentation will deviate a little bit from the traditional sieve-theoretic approach in a few places. Firstly, there is a portion of the argument that is traditionally handled using contour integration and properties of the Riemann zeta function; we will present a “cheaper” approach (which Ben Green and I used in our papers, e.g. in this one) using Fourier analysis, with the only property used about the zeta function ${\zeta(s)}$ being the elementary fact that blows up like ${\frac{1}{s-1}}$ as one approaches ${1}$ from the right. To deal with the contribution of small primes (which is the source of the singular series ${{\mathfrak G}}$), it will be convenient to use the “${W}$-trick” (introduced in this paper of mine with Ben), passing to a single residue class mod ${W}$ (where ${W}$ is the product of all the small primes) to end up in a situation in which all small primes have been “turned off” which leads to better pseudorandomness properties (for instance, once one eliminates all multiples of small primes, almost all pairs of remaining numbers will be coprime).