You are currently browsing the monthly archive for June 2013.

For any {H \geq 2}, let {B[H]} denote the assertion that there are infinitely many pairs of consecutive primes {p_n, p_{n+1}} whose difference {p_{n+1}-p_n} is at most {H}, or equivalently that

\displaystyle  \lim\inf_{n \rightarrow \infty} p_{n+1} - p_n \leq H;

thus for instance {B[2]} is the notorious twin prime conjecture. While this conjecture remains unsolved, we have the following recent breakthrough result of Zhang, building upon earlier work of Goldston-Pintz-Yildirim, Bombieri, Fouvry, Friedlander, and Iwaniec, and others:

Theorem 1 (Zhang’s theorem) {B[H]} is true for some finite {H}.

In fact, Zhang’s paper shows that {B[H]} is true with {H = 70,000,000}.

About a month ago, the Polymath8 project was launched with the objective of reading through Zhang’s paper, clarifying the arguments, and then making them more efficient, in order to improve the value of {H}. This project is still ongoing, but we have made significant progress; currently, we have confirmed that {B[H]} holds for {H} as low as {12,006}, and provisionally for {H} as low as {6,966} subject to certain lengthy arguments being checked. For several reasons, our methods (which are largely based on Zhang’s original argument structure, though with numerous refinements and improvements) will not be able to attain the twin prime conjecture {B[2]}, but there is still scope to lower the value of {H} a bit further than what we have currently.

The precise arguments here are quite technical, and are discussed at length on other posts on this blog. In this post, I would like to give a “high level” summary of how Zhang’s argument works, and give some impressions of the improvements we have made so far; these would already be familiar to the active participants of the Polymath8 project, but perhaps may be of value to people who are following this project on a more casual basis.

While Zhang’s arguments (and our refinements of it) are quite lengthy, they are fortunately also very modular, that is to say they can be broken up into several independent components that can be understood and optimised more or less separately from each other (although we have on occasion needed to modify the formulation of one component in order to better suit the needs of another). At the top level, Zhang’s argument looks like this:

  1. Statements of the form {B[H]} are deduced from weakened versions of the Hardy-Littlewood prime tuples conjecture, which we have denoted {DHL[k_0,2]} (the {DHL} stands for “Dickson-Hardy-Littlewood”), by locating suitable narrow admissible tuples (see below). Zhang’s paper establishes for the first time an unconditional proof of {DHL[k_0,2]} for some finite {k_0}; in his initial paper, {k_0} was {3,500,000}, but we have lowered this value to {1,466} (and provisionally to {902}). Any reduction in the value of {k_0} leads directly to reductions in the value of {H}; a web site to collect the best known values of {H} in terms of {k_0} has recently been set up here (and is accepting submissions for anyone who finds narrower admissible tuples than are currently known).
  2. Next, by adapting sieve-theoretic arguments of Goldston, Pintz, and Yildirim, the Dickson-Hardy-Littlewood type assertions {DHL[k_0,2]} are deduced in turn from weakened versions of the Elliott-Halberstam conjecture that we have denoted {MPZ[\varpi,\delta]} (the {MPZ} stands for “Motohashi-Pintz-Zhang”). More recently, we have replaced the conjecture {MPZ[\varpi,\delta]} by a slightly stronger conjecture {MPZ'[\varpi,\delta]} to significantly improve the efficiency of this step (using some recent ideas of Pintz). Roughly speaking, these statements assert that the primes are more or less evenly distributed along many arithmetic progressions, including those that have relatively large spacing. A crucial technical fact here is that in contrast to the older Elliott-Halberstam conjecture, the Motohashi-Pintz-Zhang estimates only require one to control progressions whose spacings {q} have a lot of small prime factors (the original {MPZ[\varpi,\delta]} conjecture requires the spacing {q} to be smooth, but the newer variant {MPZ'[\varpi,\delta]} has relaxed this to “densely divisible” as this turns out to be more efficient). The {\varpi} parameter is more important than the technical parameter {\delta}; we would like {\varpi} to be as large as possible, as any increase in this parameter should lead to a reduced value of {k_0}. In Zhang’s original paper, {\varpi} was taken to be {1/1168}; we have now increased this to be almost as large as {1/148} (and provisionally {1/108}).
  3. By a certain amount of combinatorial manipulation (combined with a useful decomposition of the von Mangoldt function due Heath-Brown), estimates such as {MPZ[\varpi,\delta]} can be deduced from three subestimates, the “Type I” estimate {Type_I[\varpi,\delta,\sigma]}, the “Type II” estimate {Type_{II}[\varpi,\delta]}, and the “Type III” estimate {Type_{III}[\varpi,\delta,\sigma]}, which all involve the distribution of certain Dirichlet convolutions in arithmetic progressions. Here {1/10 < \sigma < 1/2} is an adjustable parameter that demarcates the border between the Type I and Type III estimates; raising {\sigma} makes it easier to prove Type III estimates but harder to prove Type I estimates, and lowering {\sigma} of course has the opposite effect. There is a combinatorial lemma that asserts that as long as one can find some {\sigma} between {1/10} and {1/2} for which all three estimates {Type_I[\varpi,\delta,\sigma]}, {Type_{II}[\varpi,\delta]}, {Type_{III}[\varpi,\delta,\sigma]} hold, one can prove {MPZ[\varpi,\delta]}. (The condition {\sigma > 1/10} arises from the combinatorics, and appears to be rather essential; in fact, it is currently a major obstacle to further improvement of {\varpi} and hence {k_0} and {H}.)
  4. The Type I estimates {Type_I[\varpi,\delta,\sigma]} are asserting good distribution properties of convolutions of the form {\alpha * \beta}, where {\alpha,\beta} are moderately long sequences which have controlled magnitude and length but are otherwise arbitrary. Estimates that are roughly of this type first appeared in a series of papers by Bombieri, Fouvry, Friedlander, Iwaniec, and other authors, and Zhang’s arguments here broadly follow those of previous authors, but with several new twists that take advantage of the many factors of the spacing {q}. In particular, the dispersion method of Linnik is used (which one can think of as a clever application of the Cauchy-Schwarz inequality) to ultimately reduce matters (after more Cauchy-Schwarz, as well as treatment of several error terms) to estimation of incomplete Kloosterman-type sums such as

    \displaystyle  \sum_{n \leq N} e_d( \frac{c}{n} ).

    Zhang’s argument uses classical estimates on this Kloosterman sum (dating back to the work of Weil), but we have improved this using the “{q}-van der Corput {A}-process” introduced by Heath-Brown and Ringrose.

  5. The Type II estimates {Type_{II}[\varpi,\delta]} are similar to the Type I estimates, but cover a small hole in the coverage of the Type I estimates which comes up when the two sequences {\alpha,\beta} are almost equal in length. It turns out that one can modify the Type I argument to cover this case also. In practice, these estimates give less stringent conditions on {\varpi,\delta} than the other two estimates, and so as a first approximation one can ignore the need to treat these estimates, although recently our Type I and Type III estimates have become so strong that it has become necessary to tighten the Type II estimates as well.
  6. The Type III estimates {Type_{III}[\varpi,\delta,\sigma]} are an averaged variant of the classical problem of understanding the distribution of the ternary divisor function {\tau_3(n) := \sum_{abc=n} 1} in arithmetic progressions. There are various ways to attack this problem, but most of them ultimately boil down (after the use of standard devices such as Cauchy-Schwarz and completion of sums) to the task of controlling certain higher-dimensional Kloosterman-type sums such as

    \displaystyle  \sum_{t,t' \in ({\bf Z}/d{\bf Z})^\times} \sum_{l \in {\bf Z}/d{\bf Z}: (l,d)=(l+k,d)=1} e_d( \frac{t}{l} - \frac{t'}{l+k} + \frac{m}{t} - \frac{m'}{t'} ).

    In principle, any such sum can be controlled by invoking Deligne’s proof of the Weil conjectures in arbitrary dimension (which, roughly speaking, establishes the analogue of the Riemann hypothesis for arbitrary varieties over finite fields), although in the higher dimensional setting some algebraic geometry is needed to ensure that one gets the full “square root cancellation” for these exponential sums. (For the particular sum above, the necessary details were worked out by Birch and Bombieri.) As such, this part of the argument is by far the least elementary component of the whole. Zhang’s original argument cleverly exploited some additional cancellation in the above exponential sums that goes beyond the naive square root cancellation heuristic; more recently, an alternate argument of Fouvry, Kowalski, Michel, and Nelson uses bounds on a slightly different higher-dimensional Kloosterman-type sum to obtain results that give better values of {\varpi,\delta,\sigma}. We have also been able to improve upon these estimates by exploiting some additional averaging that was left unused by the previous arguments.

As of this time of writing, our understanding of the first three stages of Zhang’s argument (getting from {DHL[k_0,2]} to {B[H]}, getting from {MPZ[\varpi,\delta]} or {MPZ'[\varpi,\delta]} to {DHL[k_0,2]}, and getting to {MPZ[\varpi,\delta]} or {MPZ'[\varpi,\delta]} from Type I, Type II, and Type III estimates) are quite satisfactory, with the implications here being about as efficient as one could hope for with current methods, although one could still hope to get some small improvements in parameters by wringing out some of the last few inefficiencies. The remaining major sources of improvements to the parameters are then coming from gains in the Type I, II, and III estimates; we are currently in the process of making such improvements, but it will still take some time before they are fully optimised.

Below the fold I will discuss (mostly at an informal, non-rigorous level) the six steps above in a little more detail (full details can of course be found in the other polymath8 posts on this blog). This post will also serve as a new research thread, as the previous threads were getting quite lengthy.

Read the rest of this entry »

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}.

Read the rest of this entry »

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}}.

Read the rest of this entry »

This post is a continuation of the previous post on sieve theory, which is an ongoing part of the Polymath8 project. As the previous post was getting somewhat full, we are rolling the thread over to the current post.

In this post we will record a new truncation of the elementary Selberg sieve discussed in this previous post (and also analysed in the context of bounded prime gaps by Graham-Goldston-Pintz-Yildirim and Motohashi-Pintz) that was recently worked out by Janos Pintz, who has kindly given permission to share this new idea with the Polymath8 project. This new sieve decouples the {\delta} parameter that was present in our previous analysis of Zhang’s argument into two parameters, a quantity {\delta} that used to measure smoothness in the modulus, but now measures a weaker notion of “dense divisibility” which is what is really needed in the Elliott-Halberstam type estimates, and a second quantity {\delta'} which still measures smoothness but is allowed to be substantially larger than {\delta}. Through this decoupling, it appears that the {\kappa} type losses in the sieve theoretic part of the argument can be almost completely eliminated (they basically decay exponential in {\delta'} and have only mild dependence on {\delta}, whereas the Elliott-Halberstam analysis is sensitive only to {\delta}, allowing one to set {\delta} far smaller than previously by keeping {\delta'} large). This should lead to noticeable gains in the {k_0} quantity in our analysis.

To describe this new truncation we need to review some notation. As in all previous posts (in particular, the first post in this series), we have an asymptotic parameter {x} going off to infinity, and all quantities here are implicitly understood to be allowed to depend on {x} (or to range in a set that depends on {x}) unless they are explicitly declared to be fixed. We use the usual asymptotic notation {O(), o(), \ll} relative to this parameter {x}. To be able to ignore local factors (such as the singular series {{\mathfrak G}}), we also use the “{W}-trick” (as discussed in the first post in this series): we introduce a parameter {w} that grows very slowly with {x}, and set {W := \prod_{p<w} p}.

For any fixed natural number {k_0}, define an admissible {k_0}-tuple to be a fixed tuple {{\mathcal H}} of {k_0} distinct integers which avoids at least one residue class modulo {p} for each prime {p}. Our objective is to obtain the following conjecture {DHL[k_0,2]} for as small a value of the parameter {k_0} as possible:

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

The twin prime conjecture asserts that {DHL[k_0,2]} holds for {k_0} as small as {2}, but currently we are only able to establish this result for {k_0 \geq 6329} (see this comment). However, with the new truncated sieve of Pintz described in this post, we expect to be able to lower this threshold {k_0 \geq 6329} somewhat.

In previous posts, we deduced {DHL[k_0,2]} from a technical variant {MPZ[\varpi,\delta]} of the Elliot-Halberstam conjecture for certain choices of parameters {0 < \varpi < 1/4}, {0 < \delta < 1/4+\varpi}. We will use the following formulation of {MPZ[\varpi,\delta]}:

Conjecture 2 ({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) \ \ \ \ \ (1)

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) \ \ \ \ \ (2)

\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).

The conjecture {MPZ[\varpi,\delta]} is currently known to hold whenever {87 \varpi + 17 \delta < \frac{1}{4}} (see this comment and this confirmation). Actually, we can prove a stronger result than {MPZ[\varpi,\delta]} in this regime in a couple ways. Firstly, the congruence classes {C(q)} can be replaced by a more general system of congruence classes obeying a certain controlled multiplicity axiom; see this post. Secondly, and more importantly for this post, the requirement that the modulus {q} lies in {{\mathcal S}_I} can be relaxed; see below.

To connect the two conjectures, the previously best known implication was the folowing (see Theorem 2 from this post):

Theorem 3 Let {0 < \varpi < 1/4}, {0 < \delta < 1/4 + \varpi} and {k_0 \geq 2} be such that we have the inequality

\displaystyle  (1 +4 \varpi) (1-\kappa') > \frac{j^2_{k_0-2}}{k_0(k_0-1)} (1+\kappa) \ \ \ \ \ (3)

where {j_{k_0-2} = j_{k_0-2,1}} is the first positive zero of the Bessel function {J_{k_0-2}}, and {\kappa,\kappa'>0} are the quantities

\displaystyle  \kappa := \sum_{1 \leq n < \frac{1+4\varpi}{4\delta}} \frac{3^n+1}{2} \frac{k_0^n}{n!} (\int_{4\delta/(1+4\varpi)}^1 (1-t)^{k_0/2}\ \frac{dt}{t})^n


\displaystyle  \kappa' := \sum_{2 \leq n < \frac{1+4\varpi}{4\delta}} \frac{3^n-1}{2} \frac{(k_0-1)^n}{n!}

\displaystyle (\int_{4\delta/(1+4\varpi)}^1 (1-t)^{(k_0-1)/2}\ \frac{dt}{t})^n.

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

Actually there have been some slight improvements to the quantities {\kappa,\kappa'}; see the comments to this previous post. However, the main error {\kappa} remains roughly of the order {\delta^{-1} \exp( - 2 k_0\delta )}, which limits one from taking {\delta} too small.

To improve beyond this, the first basic observation is that the smoothness condition {q \in {\mathcal S}_I}, which implies that all prime divisors of {q} are less than {x^\delta}, can be relaxed in the proof of {MPZ[\varpi,\delta]}. Indeed, if one inspects the proof of this proposition (described in these three previous posts), one sees that the key property of {q} needed is not so much the smoothness, but a weaker condition which we will call (for lack of a better term) dense divisibility:

Definition 4 Let {y > 1}. A positive integer {q} is said to be {y}-densely divisible if for every {1 \leq R \leq q}, one can find a factor of {q} in the interval {[y^{-1} R, R]}. We let {{\mathcal D}_y} denote the set of positive integers that are {y}-densely divisible.

Certainly every integer which is {y}-smooth (i.e. has all prime factors at most {y} is also {y}-densely divisible, as can be seen from the greedy algorithm; but the property of being {y}-densely divisible is strictly weaker than {y}-smoothness, which is a fact we shall exploit shortly.

We now define {MPZ'[\varpi,\delta]} to be the same statement as {MPZ[\varpi,\delta]}, but with the condition {q \in {\mathcal S}_I} replaced by the weaker condition {q \in {\mathcal S}_{[w,+\infty)} \cap {\mathcal D}_{x^\delta}}. The arguments in previous posts then also establish {MPZ'[\varpi,\delta]} whenever {87 \varpi + 17 \delta < \frac{1}{4}}.

The main result of this post is then the following implication, essentially due to Pintz:

Theorem 5 Let {0 < \varpi < 1/4}, {0 < \delta \leq \delta' < 1/4 + \varpi}, {A \geq 0}, and {k_0 \geq 2} be such that

\displaystyle  (1 +4 \varpi) (1-2\kappa_1 - 2\kappa_2 - 2\kappa_3) > \frac{j^2_{k_0-2}}{k_0(k_0-1)}


\displaystyle  \kappa_1 := \int_{\theta}^1 (1-t)^{(k_0-1)/2}\ \frac{dt}{t}

\displaystyle  \kappa_2 := (k_0-1) \int_{\theta}^1 (1-t)^{k_0-1}\ \frac{dt}{t}

\displaystyle  \kappa_3 := e^A \frac{G_{k_0-1,\tilde \theta}(0,0)}{G_{k_0-1}(0,0)} \sum_{0 \leq J \leq 1/\tilde \delta} \frac{(k_0-1)^J}{J!} (\int_{\tilde \delta}^\theta e^{-At} \frac{dt}{t})^J


\displaystyle  \theta := \frac{\delta'}{1/4+\varpi}

\displaystyle  \tilde \theta := \frac{(\delta' - \delta)/2 + \varpi}{1/4 + \varpi}

\displaystyle  \tilde \delta := \frac{\delta}{1/4+\varpi}

\displaystyle  G_{k_0-1}(0,0) := \int_0^1 f(t)^2 \frac{t^{k_0-2}}{(k_0-2)!}\ dt

\displaystyle  G_{k_0-1,\tilde \theta}(0,0) := \int_0^{\tilde \theta} f(t)^2 \frac{t^{k_0-2}}{(k_0-2)!}\ dt


\displaystyle  f(t) := t^{1-k_0/2} J_{k_0-2}( \sqrt{t} j_{k_0-2} ).

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

This theorem has rather messy constants, but we can isolate some special cases which are a bit easier to compute with. Setting {\delta' = \delta}, we see that {\kappa_3} vanishes (and the argument below will show that we only need {MPZ[\varpi,\delta]} rather than {MPZ'[\varpi,\delta]}), and we obtain the following slight improvement of Theorem 3:

Theorem 6 Let {0 < \varpi < 1/4}, {0 < \delta < 1/4 + \varpi} and {k_0 \geq 2} be such that we have the inequality

\displaystyle  (1 +4 \varpi) (1-2\kappa_1-2\kappa_2) > \frac{j^2_{k_0-2}}{k_0(k_0-1)} \ \ \ \ \ (4)


\displaystyle  \kappa_1 := \int_{4\delta/(1+4\varpi)}^1 (1-t)^{(k_0-1)/2}\ \frac{dt}{t}

\displaystyle  \kappa_2 := (k_0-1) \int_{4\delta/(1+4\varpi)}^1 (1-t)^{k_0-1}\ \frac{dt}{t}.

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

This is a little better than Theorem 3, because the error {2\kappa_1+2\kappa_2} has size about {\frac{1}{2 k_0 \delta} \exp( - 2 k_0 \delta) + \frac{1}{2 \delta} \exp(-4 k_0 \delta)}, which compares favorably with the error in Theorem 3 which is about {\frac{1}{\delta} \exp(-2 k_0 \delta)}. This should already give a “cheap” improvement to our current threshold {k_0 \geq 6329}, though it will fall short of what one would get if one fully optimised over all parameters in the above theorem.

Returning to the full strength of Theorem 5, let us obtain a crude upper bound for {\kappa_3} that is a little simpler to understand. Extending the {J} summation to infinity and using the Taylor series for the exponential, we have

\displaystyle  \kappa_3 \leq \frac{G_{k_0-1,\tilde \theta}(0,0)}{G_{k_0-1}(0,0)} \exp( A + (k_0-1) \int_{\tilde \delta}^\theta e^{-At} \frac{dt}{t} ).

We can crudely bound

\displaystyle  \int_{\tilde \delta}^\theta e^{-At} \frac{dt}{t} \leq \frac{1}{A \tilde \delta}

and then optimise in {A} to obtain

\displaystyle  \kappa_3 \leq \frac{G_{k_0-1,\tilde \theta}(0,0)}{G_{k_0-1}(0,0)} \exp( 2 (k_0-1)^{1/2} \tilde \delta^{-1/2} ).

Because of the {t^{k_0-2}} factor in the integrand for {G_{k_0-1}} and {G_{k_0-1,\tilde \theta}}, we expect the ratio {\frac{G_{k_0-1,\tilde \theta}(0,0)}{G_{k_0-1}(0,0)}} to be of the order of {\tilde \theta^{k_0-1}}, although one will need some theoretical or numerical estimates on Bessel functions to make this heuristic more precise. Setting {\tilde \theta} to be something like {1/2}, we get a good bound here as long as {\tilde \delta \gg 1/k_0}, which at current values of {\delta, k_0} is a mild condition.

Pintz’s argument uses the elementary Selberg sieve, discussed in this previous post, but with a more efficient estimation of the quantity {\beta}, in particular avoiding the truncation to moduli {d} between {x^{-\delta} R} and {R} which was the main source of inefficiency in that previous post. The basic idea is to “linearise” the effect of the truncation of the sieve, so that this contribution can be dealt with by the union bound (basically, bounding the contribution of each large prime one at a time). This mostly avoids the more complicated combinatorial analysis that arose in the analytic Selberg sieve, as seen in this previous post.

Read the rest of this entry »

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


\displaystyle  N_1 \gg N_2, N_3


\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


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


\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).

Read the rest of this entry »

Tamar Ziegler and I have just uploaded to the arXiv our joint paper “A multi-dimensional Szemerédi theorem for the primes via a correspondence principle“. This paper is related to an earlier result of Ben Green and mine in which we established that the primes contain arbitrarily long arithmetic progressions. Actually, in that paper we proved a more general result:

Theorem 1 (Szemerédi’s theorem in the primes) Let {A} be a subset of the primes {{\mathcal P}} of positive relative density, thus {\limsup_{N \rightarrow \infty} \frac{|A \cap [N]|}{|{\mathcal P} \cap [N]|} > 0}. Then {A} contains arbitrarily long arithmetic progressions.

This result was based in part on an earlier paper of Green that handled the case of progressions of length three. With the primes replaced by the integers, this is of course the famous theorem of Szemerédi.

Szemerédi’s theorem has now been generalised in many different directions. One of these is the multidimensional Szemerédi theorem of Furstenberg and Katznelson, who used ergodic-theoretic techniques to show that any dense subset of {{\bf Z}^d} necessarily contained infinitely many constellations of any prescribed shape. Our main result is to relativise that theorem to the primes as well:

Theorem 2 (Multidimensional Szemerédi theorem in the primes) Let {d \geq 1}, and let {A} be a subset of the {d^{th}} Cartesian power {{\mathcal P}^d} of the primes of positive relative density, thus

\displaystyle  \limsup_{N \rightarrow \infty} \frac{|A \cap [N]^d|}{|{\mathcal P}^d \cap [N]^d|} > 0.

Then for any {v_1,\ldots,v_k \in {\bf Z}^d}, {A} contains infinitely many “constellations” of the form {a+r v_1, \ldots, a + rv_k} with {a \in {\bf Z}^k} and {r} a positive integer.

In the case when {A} is itself a Cartesian product of one-dimensional sets (in particular, if {A} is all of {{\mathcal P}^d}), this result already follows from Theorem 1, but there does not seem to be a similarly easy argument to deduce the general case of Theorem 2 from previous results. Simultaneously with this paper, an independent proof of Theorem 2 using a somewhat different method has been established by Cook, Maygar, and Titichetrakun.

The result is reminiscent of an earlier result of mine on finding constellations in the Gaussian primes (or dense subsets thereof). That paper followed closely the arguments of my original paper with Ben Green, namely it first enclosed (a W-tricked version of) the primes or Gaussian primes (in a sieve theoretic-sense) by a slightly larger set (or more precisely, a weight function {\nu}) of almost primes or almost Gaussian primes, which one could then verify (using methods closely related to the sieve-theoretic methods in the ongoing Polymath8 project) to obey certain pseudorandomness conditions, known as the linear forms condition and the correlation condition. Very roughly speaking, these conditions assert statements of the following form: if {n} is a randomly selected integer, then the events of {n+h_1,\ldots,n+h_k} simultaneously being an almost prime (or almost Gaussian prime) are approximately independent for most choices of {h_1,\ldots,h_k}. Once these conditions are satisfied, one can then run a transference argument (initially based on ergodic-theory methods, but nowadays there are simpler transference results based on the Hahn-Banach theorem, due to Gowers and Reingold-Trevisan-Tulsiani-Vadhan) to obtain relative Szemerédi-type theorems from their absolute counterparts.

However, when one tries to adapt these arguments to sets such as {{\mathcal P}^2}, a new difficulty occurs: the natural analogue of the almost primes would be the Cartesian square {{\mathcal A}^2} of the almost primes – pairs {(n,m)} whose entries are both almost primes. (Actually, for technical reasons, one does not work directly with a set of almost primes, but would instead work with a weight function such as {\nu(n) \nu(m)} that is concentrated on a set such as {{\mathcal A}^2}, but let me ignore this distinction for now.) However, this set {{\mathcal A}^2} does not enjoy as many pseudorandomness conditions as one would need for a direct application of the transference strategy to work. More specifically, given any fixed {h, k}, and random {(n,m)}, the four events

\displaystyle  (n,m) \in {\mathcal A}^2

\displaystyle  (n+h,m) \in {\mathcal A}^2

\displaystyle  (n,m+k) \in {\mathcal A}^2

\displaystyle  (n+h,m+k) \in {\mathcal A}^2

do not behave independently (as they would if {{\mathcal A}^2} were replaced for instance by the Gaussian almost primes), because any three of these events imply the fourth. This blocks the transference strategy for constellations which contain some right-angles to them (e.g. constellations of the form {(n,m), (n+r,m), (n,m+r)}) as such constellations soon turn into rectangles such as the one above after applying Cauchy-Schwarz a few times. (But a few years ago, Cook and Magyar showed that if one restricted attention to constellations which were in general position in the sense that any coordinate hyperplane contained at most one element in the constellation, then this obstruction does not occur and one can establish Theorem 2 in this case through the transference argument.) It’s worth noting that very recently, Conlon, Fox, and Zhao have succeeded in removing of the pseudorandomness conditions (namely the correlation condition) from the transference principle, leaving only the linear forms condition as the remaining pseudorandomness condition to be verified, but unfortunately this does not completely solve the above problem because the linear forms condition also fails for {{\mathcal A}^2} (or for weights concentrated on {{\mathcal A}^2}) when applied to rectangular patterns.

There are now two ways known to get around this problem and establish Theorem 2 in full generality. The approach of Cook, Magyar, and Titichetrakun proceeds by starting with one of the known proofs of the multidimensional Szemerédi theorem – namely, the proof that proceeds through hypergraph regularity and hypergraph removal – and attach pseudorandom weights directly within the proof itself, rather than trying to add the weights to the result of that proof through a transference argument. (A key technical issue is that weights have to be added to all the levels of the hypergraph – not just the vertices and top-order edges – in order to circumvent the failure of naive pseudorandomness.) As one has to modify the entire proof of the multidimensional Szemerédi theorem, rather than use that theorem as a black box, the Cook-Magyar-Titichetrakun argument is lengthier than ours; on the other hand, it is more general and does not rely on some difficult theorems about primes that are used in our paper.

In our approach, we continue to use the multidimensional Szemerédi theorem (or more precisely, the equivalent theorem of Furstenberg and Katznelson concerning multiple recurrence for commuting shifts) as a black box. The difference is that instead of using a transference principle to connect the relative multidimensional Szemerédi theorem we need to the multiple recurrence theorem, we instead proceed by a version of the Furstenberg correspondence principle, similar to the one that connects the absolute multidimensional Szemerédi theorem to the multiple recurrence theorem. I had discovered this approach many years ago in an unpublished note, but had abandoned it because it required an infinite number of linear forms conditions (in contrast to the transference technique, which only needed a finite number of linear forms conditions and (until the recent work of Conlon-Fox-Zhao) a correlation condition). The reason for this infinite number of conditions is that the correspondence principle has to build a probability measure on an entire {\sigma}-algebra; for this, it is not enough to specify the measure {\mu(A)} of a single set such as {A}, but one also has to specify the measure {\mu( T^{n_1} A \cap \ldots \cap T^{n_m} A)} of “cylinder sets” such as {T^{n_1} A \cap \ldots \cap T^{n_m} A} where {m} could be arbitrarily large. The larger {m} gets, the more linear forms conditions one needs to keep the correspondence under control.

With the sieve weights {\nu} we were using at the time, standard sieve theory methods could indeed provide a finite number of linear forms conditions, but not an infinite number, so my idea was abandoned. However, with my later work with Green and Ziegler on linear equations in primes (and related work on the Mobius-nilsequences conjecture and the inverse conjecture on the Gowers norm), Tamar and I realised that the primes themselves obey an infinite number of linear forms conditions, so one can basically use the primes (or a proxy for the primes, such as the von Mangoldt function {\Lambda}) as the enveloping sieve weight, rather than a classical sieve. Thus my old idea of using the Furstenberg correspondence principle to transfer Szemerédi-type theorems to the primes could actually be realised. In the one-dimensional case, this simply produces a much more complicated proof of Theorem 1 than the existing one; but it turns out that the argument works as well in higher dimensions and yields Theorem 2 relatively painlessly, except for the fact that it needs the results on linear equations in primes, the known proofs of which are extremely lengthy (and also require some of the transference machinery mentioned earlier). The problem of correlations in rectangles is avoided in the correspondence principle approach because one can compensate for such correlations by performing a suitable weighted limit to compute the measure {\mu( T^{n_1} A \cap \ldots \cap T^{n_m} A)} of cylinder sets, with each {m} requiring a different weighted correction. (This may be related to the Cook-Magyar-Titichetrakun strategy of weighting all of the facets of the hypergraph in order to recover pseudorandomness, although our contexts are rather different.)

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)


\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)


\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:

  • (i) the Bombieri-Vinogradov theorem;
  • (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.

Read the rest of this entry »

This post is a continuation of the previous post on sieve theory, which is an ongoing part of the Polymath8 project. As the previous post was getting somewhat full, we are rolling the thread over to the current post. We also take the opportunity to correct some errors in the treatment of the truncated GPY sieve from this previous post.

As usual, we let {x} be a large asymptotic parameter, and {w} a sufficiently slowly growing function of {x}. Let {0 < \varpi < 1/4} and {0 < \delta < 1/4+\varpi} be such that {MPZ[\varpi,\delta]} holds (see this previous post for a definition of this assertion). We let {{\mathcal H}} be a fixed admissible {k_0}-tuple, let {I := [w,x^\delta]}, let {{\mathcal S}_I} be the square-free numbers with prime divisors in {I}, and consider the truncated GPY sieve

\displaystyle  \nu(n) := \lambda(n)^2


\displaystyle  \lambda(n) := \sum_{d \in {\mathcal S}_I: d|P(n)} \mu(d) g(\frac{\log d}{\log R})

where {R := x^{1/4+\varpi}}, {P} is the polynomial

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

and {g: {\bf R} \rightarrow {\bf R}} is a fixed smooth function supported on {[-1,1]}. As discussed in the previous post, we are interested in obtaining an upper bound of the form

\displaystyle  \sum_{x \leq n \leq 2x} \nu(n) \leq (\alpha+o(1)) (\frac{W}{\phi(W)})^{k_0} \frac{x}{W \log^{k_0} R}

as well as a lower bound of the form

\displaystyle  \sum_{x \leq n \leq 2x} \nu(n) \theta(n+h) \geq (\beta+o(1)) (\frac{W}{\phi(W)})^{k_0} \frac{x}{W \log^{k_0-1} R}

for all {h \in {\mathcal H}} (where {\theta(n) = \log n} when {n} is prime and {\theta(n)=0} otherwise), since this will give the conjecture {DHL[k_0,2]} (i.e. infinitely many prime gaps of size at most {k_0}) whenever

\displaystyle  1+4\varpi > \frac{4\alpha}{k_0 \beta}. \ \ \ \ \ (1)

It turns out we in fact have precise asymptotics

\displaystyle  \sum_{x \leq n \leq 2x} \nu(n) = (\alpha+o(1)) (\frac{W}{\phi(W)})^{k_0} \frac{x}{W \log^{k_0} R} \ \ \ \ \ (2)


\displaystyle  \sum_{x \leq n \leq 2x} \nu(n) \theta(n+h) = (\beta+o(1)) (\frac{W}{\phi(W)})^{k_0} \frac{x}{W \log^{k_0} R} \ \ \ \ \ (3)

although the exact formulae for {\alpha,\beta} are a little complicated. (The fact that {\alpha,\beta} could be computed exactly was already anticipated in Zhang’s paper; see the remark on page 24.) We proceed as in the previous post. Indeed, from the arguments in that post, (2) is equivalent to

\displaystyle  \sum_{d_1,d_2 \in {\mathcal S}_I} \mu(d_1) g(\frac{\log d_1}{\log R}) \mu(d_2) g(\frac{\log d_2}{\log R}) \frac{k_0^{\Omega([d_1,d_2])}}{[d_1,d_2]} \ \ \ \ \ (4)

\displaystyle  = (\alpha + o(1)) (\frac{W}{\phi(W)})^{k_0} \log^{-k_0} R

and (3) is similarly equivalent to

\displaystyle  \sum_{d_1,d_2 \in {\mathcal S}_I} \mu(d_1) g(\frac{\log d_1}{\log R}) \mu(d_2) g(\frac{\log d_2}{\log R}) \frac{(k_0-1)^{\Omega([d_1,d_2])}}{[d_1,d_2]} \ \ \ \ \ (5)

\displaystyle  = (\beta + o(1)) (\frac{W}{\phi(W)})^{k_0-1} \log^{-k_0+1} R.

Here {\Omega(d)} is the number of prime factors of {d}.

We will work for now with (4), as the treatment of (5) is almost identical.

We would now like to replace the truncated interval {I = [w,x^\delta]} with the untruncated interval {I \cup J = [w,\infty)}, where {J = (x^\delta,\infty)}. Unfortunately this replacement was not quite done correctly in the previous post, and this will now be corrected here. We first observe that if {F(d_1,d_2)} is any finitely supported function, then by Möbius inversion we have

\displaystyle  \sum_{d_1,d_2 \in {\mathcal S}_I} F(d_1,d_2) = \sum_{d_1,d_2 \in {\mathcal S}_{I \cup J}} F(d_1,d_2) \sum_{a \in {\mathcal S}_J} \mu(a) 1_{a|[d_1,d_2]}.

Note that {a|[d_1,d_2]} if and only if we have a factorisation {d_1 = a_1 d'_1}, {d_2 = a_2 d'_2} with {[a_1,a_2] = a} and {d'_1 d'_2} coprime to {a_1 a_2}, and that this factorisation is unique. From this, we see that we may rearrange the previous expression as

\displaystyle  \sum_{a_1,a_2 \in {\mathcal S}_J} \mu( [a_1,a_2] ) \sum_{d'_1,d'_2 \in {\mathcal S}_{I \cup J}: (d'_1 d'_2, a_1 a_2) = 1} F( a_1 d'_1, a_2 d'_2 ).

Applying this to (4), and relabeling {d'_1,d'_2} as {d_1,d_2}, we conclude that the left-hand side of (4) is equal to

\displaystyle  \sum_{a_1,a_2 \in {\mathcal S}_J} \mu( [a_1,a_2] ) \sum_{d_1,d_2 \in {\mathcal S}_{I \cup J}: (d_1d_2,a_1a_2)=1}

\displaystyle \mu(a_1d_1) g(\frac{\log a_1d_1}{\log R}) \mu(a_2d_2) g(\frac{\log a_2d_2}{\log R}) \frac{k_0^{\Omega([a_1 d_1,a_2 d_2])}}{[a_1 d_1,a_2 d_2]}

which may be rearranged as

\displaystyle  \sum_{a_1,a_2 \in {\mathcal S}_J} \frac{\mu( (a_1,a_2) ) k_0^{\Omega([a_1,a_2])}}{[a_1,a_2]} \sum_{d_1,d_2\in {\mathcal S}_{I \cup J}: (d_1d_2,a_1a_2)=1} \ \ \ \ \ (6)

\displaystyle  \mu(d_1) g(\frac{\log a_1d_1}{\log R}) \mu(d_2) g(\frac{\log a_1 d_2}{\log R}) \frac{k_0^{\Omega([d_1,d_2])}}{[d_1, d_2]}.

This is almost the same formula that we had in the previous post, except that the Möbius function {\mu((a_1,a_2))} of the greatest common divisor {(a_1,a_2)} of {a_1,a_2} was missing, and also the coprimality condition {(d_1d_2,a_1a_2)=1} was not handled properly in the previous post.

We may now eliminate the condition {(d_1d_2,a_1a_2)=1} as follows. Suppose that there is a prime {p_* \in J} that divides both {d_1d_2} and {a_1a_2}. The expression

\displaystyle  \sum_{a_1,a_2 \in {\mathcal S}_J} \frac{k_0^{\Omega([a_1,a_2])}}{[a_1,a_2]} \sum_{d_1,d_2 \in {\mathcal S}_{I \cup J}: p_* | (d_1d_2,a_1a_2)}

\displaystyle |g(\frac{\log a_1d_1}{\log R})| |g(\frac{\log a_1 d_2}{\log R})| \frac{k_0^{\Omega([d_1,d_2])}}{[d_1, d_2]}

can then be bounded by

\displaystyle  \ll \sum_{a_1,a_2} \sum_{d_1,d_2: p_* | (d_1d_2,a_1a_2)} \frac{k_0^{\Omega([a_1,a_2])}}{[a_1,a_2]} \frac{k_0^{\Omega([d_1,d_2])}}{[d_1, d_2]} (a_1 a_2 d_1 d_2)^{-1/\log R}

which may be factorised as

\displaystyle  \ll \frac{1}{p_*^2} \prod_p (1 + \frac{O(1)}{p^{1+1/\log R}})

which by Mertens’ theorem (or the simple pole of {\zeta(s)} at {s=1}) is

\displaystyle  \ll \frac{\log^{O(1)} R}{p_*^2}.

Summing over all {p_* > x^\varpi} gives a negligible contribution to (6) for the purposes of (4). Thus we may effectively replace (6) by

\displaystyle  \sum_{a_1,a_2 \in {\mathcal S}_J} \frac{\mu( (a_1,a_2) ) k_0^{\Omega([a_1,a_2])}}{[a_1,a_2]} \sum_{d_1,d_2\in {\mathcal S}_{I \cup J}}

\displaystyle \mu(d_1) g(\frac{\log a_1d_1}{\log R}) \mu(d_2) g(\frac{\log a_1 d_2}{\log R}) \frac{k_0^{\Omega([d_1,d_2])}}{[d_1, d_2]}.

The inner summation can be treated using Proposition 10 of the previous post. We can then reduce (4) to

\displaystyle  \sum_{a_1,a_2 \in {\mathcal S}_J} \frac{\mu( (a_1,a_2) ) k_0^{\Omega([a_1,a_2])}}{[a_1,a_2]} G_{k_0}( \frac{\log a_1}{\log R}, \frac{\log a_2}{\log R} ) = \alpha+o(1) \ \ \ \ \ (7)

where {G_{k_0}} is the function

\displaystyle  G_{k_0}(t_1,t_2) := \int_0^1 g^{(k_0)}(t+t_1) g^{(k_0)}(t+t_2) \frac{t^{k_0-1}}{(k_0-1)!}\ dt.

Note that {G} vanishes if {t_1 \geq 1} or {t_2 \geq 1}. In practice, we will work with functions {g} in which {g^{(k_0)}} has a definite sign (in our normalisations, {g^{(k_0)}} will be non-positive), making {G_{k_0}} non-negative.

We rewrite the left-hand side of (7) as

\displaystyle  \sum_{a \in {\mathcal S}_J} \frac{k_0^{\Omega(a)}}{a} \sum_{a_1,a_2: [a_1,a_2] = a} \mu((a_1,a_2)) G_{k_0}( \frac{\log a_1}{\log R}, \frac{\log a_2}{\log R} ).

We may factor {a = p_1 \ldots p_n} for some {x^\delta < p_1 < \ldots < p_n} with {p_1 \ldots p_n \leq R}; in particular, {n < \frac{1 + 4\varpi}{4\delta}}. The previous expression now becomes

\displaystyle  \sum_{0 \leq n < \frac{1+4\varpi}{4\delta}} k_0^n \sum_{x^\delta < p_1 < \ldots < p_n} \frac{1}{p_1 \ldots p_n}

\displaystyle  \sum_{\{1,\ldots,n\} = S \cup T} (-1)^{|S \cap T|} G_{k_0}( \sum_{i \in S} \frac{\log p_i}{\log R}, \sum_{j \in T} \frac{\log p_j}{\log R} ).

Using Mertens’ theorem, we thus conclude an exact formula for {\alpha}, and similarly for {\beta}:

Proposition 1 (Exact formula) We have

\displaystyle  \alpha = \sum_{0 \leq n < \frac{1+4\varpi}{4\delta}} k_0^n \int_{\frac{4\delta}{1+4\varpi} < t_1 < \ldots < t_n} G_{k_0,n}(t_1,\ldots,t_n) \frac{dt_1 \ldots dt_n}{t_1 \ldots t_n}


\displaystyle  G_{k_0,n}(t_1,\ldots,t_n) := \sum_{\{1,\ldots,n\} = S \cup T} (-1)^{|S \cap T|} G_{k_0}( \sum_{i \in S} t_i, \sum_{j \in T} t_j ).

Similarly we have

\displaystyle  \beta = \sum_{0 \leq n < \frac{1+4\varpi}{4\delta}} (k_0-1)^n \int_{\frac{4\delta}{1+4\varpi} < t_1 < \ldots < t_n} G_{k_0-1,n}(t_1,\ldots,t_n) \frac{dt_1 \ldots dt_n}{t_1 \ldots t_n}

where {G_{k_0-1}} and {G_{k_0-1,n}} are defined similarly to {G_{k_0}} and {G_{k_0,n}} by replacing all occurrences of {k_0} with {k_0-1}.

These formulae are unwieldy. However if we make some monotonicity hypotheses, namely that {g^{(k_0-1)}} is positive, {g^{(k_0)}} is negative, and {g^{(k_0+1)}} is positive on {[0,1)}, then we can get some good estimates on the {G_{k_0}, G_{k_0-1}} (which are now non-negative functions) and hence on {\alpha,\beta}. Namely, if {g^{(k_0)}} is negative but increasing then we have

\displaystyle  -g^{(k_0)}(t+t_1) \leq -g^{(k_0)}(\frac{t}{1-t_1})

for {0 \leq t_1 < 1} and {t \in [0,1]}, which implies that

\displaystyle  G_{k_0}(t_1,t_1) \leq (1-t_1)_+^{k_0} G_{k_0}(0,0)

for any {t_1 \geq 0}. A similar argument in fact gives

\displaystyle  G_{k_0}(t_1+t_2,t_1+t_2) \leq (1-t_1)_+^{k_0} G_{k_0}(t_2,t_2)

for any {t_1,t_2 \geq 0}. Iterating this we conclude that

\displaystyle  G_{k_0}(\sum_{i \in S} t_i, \sum_{i \in S} t_i) \leq (\prod_{i \in S} (1-t_i)_+^{k_0}) G_{k_0}(0,0)

and similarly

\displaystyle  G_{k_0}(\sum_{i \in T} t_i, \sum_{i \in T} t_i) \leq (\prod_{i \in T} (1-t_i)_+^{k_0}) G_{k_0}(0,0).

From Cauchy-Schwarz we thus have

\displaystyle  G_{k_0}( \sum_{i \in S} t_i, \sum_{i \in T} t_i ) \leq (\prod_{i=1}^n (1 - t_i)_+^{k_0/2}) G_{k_0}(0,0).

Observe from the binomial formula that of the {3^n} pairs {(S,T)} with {S \cup T = \{1,\ldots,n\}}, {\frac{3^n+1}{2}} of them have {|S \cap T|} even, and {\frac{3^n-1}{2}} of them have {|S \cap T|} odd. We thus have

\displaystyle  -\frac{3^n-1}{2} (\prod_{i=1}^n (1 - t_i)_+^{k_0/2}) G_{k_0}(0,0) \leq G_{k_0,n}(t_1,\ldots,t_n) \ \ \ \ \ (8)

\displaystyle  \leq \frac{3^n+1}{2} (\prod_{i=1}^n (1 - t_i)_+^{k_0/2}) G_{k_0}(0,0).

We have thus established the upper bound

\displaystyle  \alpha \leq G_{k_0}(0,0) (1 + \kappa) \ \ \ \ \ (9)


\displaystyle  \kappa := \sum_{1 \leq n < \frac{1+4\varpi}{4\delta}} \frac{3^n+1}{2} k_0^n \int_{\frac{4\delta}{1+4\varpi} < t_1 < \ldots < t_n} (\prod_{i=1}^n (1 - t_i)_+^{k_0/2}) \frac{dt_1 \ldots dt_n}{t_1 \ldots t_n}.

By symmetry we may factorise

\displaystyle  \kappa := \sum_{1 \leq n < \frac{1+4\varpi}{4\delta}} \frac{3^n+1}{2} \frac{k_0^n}{n!} ( \int_{\frac{4\delta}{1+4\varpi} < t \leq 1} (1-t)^{k_0/2}\ \frac{dt}{t})^n.

The expression {\kappa} is explicitly computable for any given {\varpi,\delta,k_0}. Following the recent preprint of Pintz, one can get a slightly looser, but cleaner, bound by using the upper bound

\displaystyle  1-t \leq \exp(-t)

and so

\displaystyle  \kappa \leq \sum_{1 \leq n < \frac{1+4\varpi}{4\delta}} \frac{3^n+1}{2} \frac{k_0^n}{n!} (\int_{4\delta/(1+4\varpi)}^\infty \exp( - \frac{k_0}{2} t )\ \frac{dt}{t})^n.

Note that

\displaystyle  \int_{4\delta/(1+4\varpi)}^\infty \exp( - \frac{k_0}{2} t )\ \frac{dt}{t} = \int_1^\infty \exp( - \frac{2k_0 \delta}{1+4\varpi} t)\ \frac{dt}{t}

\displaystyle < \int_1^\infty \exp( - \frac{2k_0 \delta}{1+4\varpi} t)\ dt

\displaystyle  = \frac{1+4\varpi}{2k_0\delta} \exp( - \frac{2k_0 \delta}{1+4\varpi} )

and hence

\displaystyle \kappa \leq \tilde \kappa


\displaystyle  \tilde \kappa := \sum_{1 \leq n < \frac{1+4\varpi}{4\delta}} \frac{1}{n!} \frac{3^n+1}{2} (\frac{1+4\varpi}{2\delta} \exp( - \frac{2k_0 \delta}{1+4\varpi} ))^n.

In practice we expect the {n=1} term to dominate, thus we have the heuristic approximation

\displaystyle  \kappa \lessapprox \frac{1+4\varpi}{\delta} \exp( - \frac{2k_0 \delta}{1+4\varpi} ).

Now we turn to the estimation of {\beta}. We have an analogue of (8), namely

\displaystyle  -\frac{3^n-1}{2} (\prod_{i=1}^n (1-t_i)^{(k_0-1)/2}) G_{k_0-1}(0,0) \leq G_{k_0-1,n}(t_1,\ldots,t_n)

\displaystyle  \leq \frac{3^n+1}{2} (\prod_{i=1}^n (1-t_i)^{(k_0-1)/2}) G_{k_0-1}(0,0).

But we have an improvment in the lower bound in the {n=1} case, because in this case we have

\displaystyle  G_{k_0-1,n}(t) = G_{k_0-1}(t,0) + G_{k_0-1}(0,t) - G_{k_0-1}(t,t).

From the positive decreasing nature of {g^{(k_0-1)}} we see that {G_{k_0-1}(t,t) \leq G_{k_0-1}(t,0)} and so {G_{k_0-1,n}(t)} is non-negative and can thus be ignored for the purposes of lower bounds. (There are similar improvements available for higher {n} but this seems to only give negligible improvements and will not be pursued here.) Thus we obtain

\displaystyle  \beta \geq G_{k_0-1}(0,0) (1-\kappa') \ \ \ \ \ (10)


\displaystyle  \kappa' := \sum_{2 \leq n < \frac{1+4\varpi}{4\delta}} \frac{3^n-1}{2} \frac{(k_0-1)^n}{n!}

\displaystyle (\int_{4\delta/(1+4\varpi)}^1 (1-t)^{(k_0-1)/2}\ \frac{dt}{t})^n.

Estimating {\kappa'} similarly to {\kappa} we conclude that

\displaystyle  \kappa' \leq \tilde \kappa'


\displaystyle  \tilde \kappa' := \sum_{2 \leq n < \frac{1+4\varpi}{4\delta}} \frac{1}{n!} \frac{3^n-1}{2} (\frac{1+4\varpi}{2\delta} \exp( - \frac{2(k_0-1) \delta}{1+4\varpi} ))^n.

By (9), (10), we see that the condition (1) is implied by

\displaystyle  (1+4\varpi) (1-\kappa') > \frac{4G_{k_0}(0,0)}{k_0 G_{k_0-1}(0,0)} (1+\kappa).

By Theorem 14 and Lemma 15 of this previous post, we may take the ratio {\frac{4G_{k_0}(0,0)}{k_0 G_{k_0-1}(0,0)}} to be arbitrarily close to {\frac{j_{k_0-2}^2}{k_0(k_0-1)}}. We conclude the following theorem.

Theorem 2 Let {0 < \varpi < 1/4} and {0 < \delta < 1/4 + \varpi} be such that {MPZ[\varpi,\delta]} holds. Let {k_0 \geq 2} be an integer, define

\displaystyle  \kappa := \sum_{1 \leq n < \frac{1+4\varpi}{4\delta}} \frac{3^n+1}{2} \frac{k_0^n}{n!} (\int_{4\delta/(1+4\varpi)}^1 (1-t)^{k_0/2}\ \frac{dt}{t})^n


\displaystyle  \kappa' := \sum_{2 \leq n < \frac{1+4\varpi}{4\delta}} \frac{3^n-1}{2} \frac{(k_0-1)^n}{n!}

\displaystyle (\int_{4\delta/(1+4\varpi)}^1 (1-t)^{(k_0-1)/2}\ \frac{dt}{t})^n

and suppose that

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

Then {DHL[k_0,2]} holds.

As noted earlier, we heuristically have

\displaystyle  \tilde \kappa \approx \frac{1+4\varpi}{\delta} \exp( - \frac{2k_0 \delta}{1+4\varpi} )

and {\tilde \kappa'} is negligible. This constraint is a bit better than the previous condition, in which {\tilde \kappa'} was not present and {\tilde \kappa} was replaced by a quantity roughly of the form {2 \log(2) k_0 \exp( - \frac{2k_0 \delta}{1+4\varpi})}.

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}


\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}


    \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


\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.

Read the rest of this entry »

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<w} 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.

Read the rest of this entry »