Bounded gaps between primes (Polymath8) – a progress report

30 June, 2013 in expository, math.NT, polymath | Tags: polymath8

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:

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

— 1. Finding narrow prime tuples —

For any ${k_0 \geq 2}$ , we define an admissible ${k_0}$ -tuple to be a tuple ${{\mathcal H} = (h_1,\ldots,h_{k_0})}$ of ${k_0}$ distinct integers ${h_1 < \ldots < h_{k_0}}$ , such that ${{\mathcal H}}$ avoids at least one residue class modulo ${p}$ for each prime ${p}$ . Thus for instance ${(0,2)}$ is an admissible ${2}$ -tuple, and ${(0,2,6)}$ is an admissible ${3}$ -tuple, but ${(0,2,4)}$ is not admissible (it does not avoid any residue classes modulo ${3}$ ).

The prime tuples conjecture asserts that whenever ${{\mathcal H} = (h_1,\ldots,h_{k_0})}$ is an admissible ${k_0}$ -tuple, then there are infinitely many translates ${n+{\mathcal H} = (n+h_1,\ldots,n+h_{k_0})}$ that consist entirely of primes. This conjecture is still out of reach of current methods, but we can hope to establish results of the following form for a given ${k_0 \geq 2}$ :

Conjecture 2 ( ${DHL[k_0,2]}$ ) If ${{\mathcal H}}$ is an admissible ${k_0}$ -tuple, then there are infinitely many translates ${n + {\mathcal H}}$ of ${{\mathcal H}}$ that contain at least two primes.

Let ${H(k_0)}$ be the minimal diameter ${h_{k_0}-h_1}$ of an admissible ${k_0}$ -tuple: thus for instance ${H(2) = 2}$ , ${H(3) = 6}$ , and ${H(4)=8}$ . It is clear that if ${DHL[k_0,2]}$ holds for some ${k_0}$ , then ${B[H]}$ is true for ${H = H(k_0)}$ , since we have an admissible ${k_0}$ -tuple ${{\mathcal H}}$ of diameter ${H(k_0)}$ , and any translate of that tuple that contains two primes will generate a pair of consecutive primes of distance at most ${H}$ apart. So we can use statements of the form ${DHL[k_0,2]}$ to deduce estimates of the form ${B[H]}$ , provided that we can find admissible ${k_0}$ -tuples that are as narrow as possible, in order to obtain as good a value of ${H}$ that one can hope to get.

Perhaps the easiest way to obtain an admissible ${k_0}$ -tuple of reasonably narrow width is to take “the first ${k_0}$ primes past ${k_0}$ “, i.e. the tuple ${(p_{m+1},\ldots,p_{m+k_0})}$ , where ${p_{m+1}}$ is the first prime larger than ${k_0}$ . It is not difficult to show that this is an admissible tuple. Zhang used this construction with ${k_0 = 3,500,000}$ to obtain ${H[3,500,000] \leq 70,000,000}$ ; as observed later by Trudgian, this construction actually has diameter ${59,874,594}$ , giving the bound ${H[3,500,000] \leq 59,874,594}$ .

For large ${k_0}$ , this construction gives an asymptotic of the form

$\displaystyle H(k_0) \leq k_0 \log k_0 + k_0 \log\log k_0 + O(k_0)$

as can be seen by a careful application of the prime number theorem.

One can do better than this in a number of ways. Firstly, it turns out that one can reduce ${m}$ a bit and still have ${(p_{m+1},\ldots,p_{m+k_0})}$ admissible; for ${k_0=3,500,000}$ , it turns out after some computation that this trick lowers the diameter a little bit to ${59,093,364}$ ; asymptotically this gives

$\displaystyle H(k_0) \leq k_0 \log k_0 + k_0 \log\log k_0 - k_0 + o(k_0)$

(because ${m}$ can be taken to be ${o(k_0/\log k_0)}$ ). A larger improvement comes from the work of Hensley and Richards, namely to shift the tuple to cover positive and negative primes around the origin, in order to exploit the slightly increased density of the primes in this interval. Specifically, if one uses a tuple of the form

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

and optimises in ${m}$ , one can bound ${H[3,500,000] \leq 57,554,068}$ . Asymptotically, this gives the slight improvement

$\displaystyle H(k_0) \leq k_0 \log k_0 + k_0 \log\log k_0 - (1 + \log 2) k_0 + o(k_0).$

One can get a little more improvement by deleting a few primes from one end of this tuple and adding them to another, although the gains here are modest. Incidentally, Hensley and Richards used this improved asymptotic to demonstrate that the prime tuples conjecture was inconsistent with the second Hardy-Littlewood conjecture, which is now widely believed to be false.

One can view the Hensley-Richard construction as a “sieve” similar to the sieve of Eratosthenes, formed by starting with the integers in an interval ${[-p_{m+\lfloor k_0-2/2\rfloor}, \ldots,p_{m+\lfloor k_0-1/2 \rfloor}]}$ and striking out the residue class ${0 \ (p) = 0 \hbox{ mod } (p)}$ for all primes ${p}$ up to ${p_m}$ . (In principle, this sieve could leave a few extra survivors, namely powers of primes larger than ${p_m}$ , together with their negations, though in practice such powers fall outside the interval of interest.) This sieve already does most of the “work” of establishing admissibility as it handles all the small moduli, leaving only the larger moduli to be checked computationally. It was observed by Schinzel that one could do very slightly better than this by sieving out the odd integers ${1\ (2)}$ rather than the even integers ${0\ (2)}$ , leaving behind numbers of the form ${\pm 2^j p}$ for various primes ${p}$ ; this is conjecturally believed to give the bound

$\displaystyle H(k_0) \leq k_0 \log k_0 + k_0 \log\log k_0 - (1 + 2\log 2) k_0 + o(k_0).$

By similarly sieving out ${1\ (p)}$ for other small primes ${p}$ , it is in fact conjectured that

$\displaystyle H(k_0) \leq k_0 \log k_0 + k_0 \log\log k_0 - (1+o(1)) k_0 \log\log\log k_0$

(see this paper of Gordon and Rodemich for a heuristic justification) although for the values of ${k_0}$ that we have worked with, these asymptotically superior constructions are actually numerically inferior to what one can get just from the first version of the Schinzel sieve. As before, some slight further gains can be obtained by shifting the interval that one is sieving over.

More recently, we have worked with tuples that initially started from partially performing the sieving from a Schinzel construction, but at some point switching to a “greedy” algorithm in which one deletes, for each prime, the residue class that removes the fewest elements from the tuple. The next technical innovation was a “merging” approach in which one took two reasonably good tuples already constructed, merged them together by taking their union, and then greedily pruning away residue classes to obtain a merged tuple that is hopefully superior to either of its two “parents”. This procedure can be iterated, and also combined with local optimisations in which the sieving interval is shifted or a small number of elements are otherwise added and deleted. This has produced many of the best constructions so far, typically about 5% narrower than what previous constructions such as the Schinzel sieve construction gave. (For small values of ${k_0}$ , say ${k_0 \leq 4000}$ , the older work of Engelsma on finding narrow tuples, which used slightly different methods, is often still the record-holder.

Very recently, a web page has been set up to record the best known tuples of cardinality up to ${5,000}$ (including the older data of Engelsma), and to accept submissions for new “record holders”. This will help with further improvements to ${B[H]}$ , but the database of narrow tuples is likely to have other uses in effective prime number theory as well.

Numerical regression suggests that ${H(k_0)}$ is roughly ${k_0 \log k_0 + k_0}$ for small or medium values of ${k_0}$ . There is no theoretical justification for this bound; the best lower bounds we have on ${H(k_0)}$ asymptotically come from the Brun-Titchmarsh theorem and its refinements (and in particular various versions of the large sieve), and take the form

$\displaystyle H(k_0) \geq (\frac{1}{2} + o(1)) k_0 \log k_0.$

It looks very difficult to improve upon this loss of ${1/2}$ (this problem may possibly be related to the parity problem in sieve theory, although the precise connection is unclear).

Further information on this part of the Polymath8 project may be found at this page.

— 2. Sieving and Dickson-Hardy-Littlewood type results —

Now we informally describe how to obtain results of the form ${DHL[k_0,2]}$ . Zhang’s approach (and thus ours) follows the basic strategy given by the breakthrough paper of Goldston, Pintz, and Yildirim establishing small (but not bounded) gaps between primes.

Let ${{\mathcal H} = (h_1,\ldots,h_{k_0})}$ be an admissible ${k_0}$ -tuple. The basic difficulty in trying to locate translates ${n + {\mathcal H} = (n+h_1,\ldots,n+h_{k_0})}$ that contain two or more primes is that the primes get sparser and sparser when one goes out to infinity, so if one chooses ${n}$ to be an integer chosen at random from (say) the interval ${[x,2x]}$ , one would expect most such tuples to in fact contain no primes.

The trick of Goldston, Pintz, and Yildirim is not to pick ${n}$ uniformly from ${[x,2x]}$ , but instead to pick ${n}$ in a weighted fashion that significantly increases the probability of each member ${n+h_i}$ of the translated tuple being prime. To oversimplify, suppose we could construct a moderately large subset ${A}$ of ${[x,2x]}$ with the property that for each ${1 \leq i \leq k_0}$ , we have that ${n+h_i}$ is prime for more than ${1/k_0}$ of the elements ${n}$ of ${A}$ . Then just from the pigeonhole principle, one could conclude the existence of at least one ${n \in A}$ such that ${n+h_i}$ is prime for at least two choices of ${i}$ , which give ${DHL[k_0,2]}$ .

Of course, one has to choose a set ${A}$ for which one can prove the desired claim, that each ${n+h_i}$ is prime for more than ${1/k_0}$ of the elements ${n}$ of ${A}$ . Intuitively, the strategy of Goldston, Pintz, and Yildirim is to let ${A}$ consist of those ${n \in [x,2x]}$ for which the quantity ${P(n) := \prod_{i=1}^{k_0} (n+h_i)}$ is almost prime – that it only has a relatively small number of prime factors (not much more than ${k_0}$ ).

Actually, it turns out that it is best not to try to use a set ${A}$ for the above strategy, but rather a non-negative weight function ${\nu}$ on ${[x,2x]}$ which is concentrated on those ${n}$ for which ${P(n)}$ is almost prime. One then seeks to maximise the ratio

$\displaystyle \frac{ \sum_n \nu(n) 1_{n+h_i \hbox{ prime}} }{\sum_n \nu(n) } \ \ \ \ \ (1)$

for each ${i}$ ; in particular, if one can get these ratios all above ${1/k_0}$ , one has proven ${DHL[k_0,2]}$ .

One then needs to construct a non-negative weight ${\nu}$ for which the ratio (1) is (a) computable, and (b) as large as possible. For this one uses a version of the Selberg sieve, choosing ${\nu}$ of the form

$\displaystyle \nu(n) := 1_{[x,2x]}(n) (\sum_{d|P(n)} \lambda_d)^2$

for some weights ${\lambda_d}$ to be optimised later. In order to be able to compute both the numerator and denominator of (1), one needs to limit the sieve weights ${\lambda_d}$ to be supported on the range ${d \leq R}$ for some sieve level ${R}$ , which one would like to be as large as possible to give maximum flexibility to the sieve. The denominator of (1) is relatively easy to compute (as long as ${R}$ does not exceed ${x^{1/2}}$ , but the numerator is more difficult. Expanding out the formula for ${\nu}$ , the numerator becomes

$\displaystyle \sum_{d_1,d_2} \lambda_{d_1} \lambda_{d_2} \sum_{n \in [x,2x]: [d_1,d_2] | P(n)} 1_{n+h_i \hbox{ prime}}.$

As is standard in analytic number theory, it is slightly more convenient to replace this sum by the closely related sum

$\displaystyle \sum_{d_1,d_2} \lambda_{d_1} \lambda_{d_2} \sum_{n \in [x,2x]: [d_1,d_2] | P(n)} \Lambda(n+h_i)$

where ${\Lambda}$ is the von Mangoldt function, which serves as a useful proxy for the prime numbers.

The ${n}$ summation is restricted to a fairly small number of residue classes ${a_q\ (q)}$ modulo ${q := [d_1,d_2]}$ , which is a modulus of size at most ${R^2}$ . To control the numerator of (1), one thus needs some sort of distribution result for the primes (or the von Mangoldt function) in arithmetic progressions of modulus ${q}$ at least as large as ${R^2}$ . If one had to get good distribution for all moduli ${q}$ up to this level, this would be a task comparable to the generalised Riemann hypothesis, and thus hopeless; but fortunately we only need such distribution results on average for such moduli ${q}$ . For this, standard tools such as the Bomberi-Vinogradov theorem are available, at least for ${R^2}$ up to about ${x^{1/2}}$ or so. This was already strong enough for Goldston, Pintz, and Yildirim to obtain reasonably narrow prime gaps (in which ${p_{n+1}-p_n = o(\log p_n)}$ , for instance), but to get bounded prime gaps it turns out to be necessary to obtain distribution results up to a slightly higher exponent ${x^{1/2+2\varpi}}$ for some ${\varpi > 0}$ . The standard distribution conjecture in this direction is the Elliott-Halberstam conjecture

$\displaystyle \sum_{q \leq x^{1/2+2\varpi}} | \sum_{n = a_q\ (q): n \in [x,2x]} \Lambda(n) - \frac{1}{\phi(q)} \sum_{n \in [x,2x]} \Lambda(n) | \ll x \log^{-A} x \ \ \ \ \ (2)$

for any fixed ${A>0}$ , where ${a_q\ (q)}$ is a primitive residue class modulo ${q}$ for each ${q}$ , and ${\phi}$ is the Euler totient function. This estimate is conjectured to hold for ${\varpi}$ arbitrarily close to ${1/4}$ , and Goldston, Pintz and Yildirim showed that the assertion (2) for even a small ${\varpi>0}$ was sufficient to imply ${DHL[k_0,2]}$ for some ${k_0}$ (the condition they obtained was asymptotically of the form ${k_0 \sim \varpi^{-2}}$ , and if one could get ${\varpi}$ sufficiently close to ${1/4}$ , one could in fact obtain ${DHL[6,2]}$ ). Unfortunately, the Elliott-Halberstam conjecture (2) remains open for any choice of ${\varpi>0}$ .

Zhang made a number of observations to get around this obstacle. First, he observed that the residue classes ${a_q\ (q)}$ needed for the application to ${DHL[k_0,2]}$ were not completely arbitrary, but were linked to each other, basically obeying a Chinese remainder theorem

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

for any coprime ${q,r}$ . (These congruences ${a_q\ (q)}$ basically come from the roots of the polynomial ${P}$ modulo ${q}$ .) Secondly, he observed that by suitably truncating the Selberg sieve, one did not need to establish (2) for all moduli ${q}$ , but only those moduli which were squarefree and smooth, in the sense that all prime divisors of ${q}$ were at most ${x^\delta}$ for some small ${\delta>0}$ . (This observation had also been made previously by Motohashi and Pintz.) One had the freedom to select ${\delta}$ as one wished, although if one set ${\delta}$ to be too small, the value of ${k_0}$ one obtained would increase.

One can then formulate a weakened version of (2) which we have called ${MPZ[\varpi,\delta]}$ (the MPZ standing for Motohashi, Pintz, and Zhang), in which the ${a_q\ (q)}$ are constrained to obey the Chinese remainder theorem and the ${q}$ are constrained to be square-free and smooth. Zhang was able to establish ${MPZ[\varpi,\delta]}$ for ${\varpi = \delta = 1/1,168}$ , which he could then use to establish ${DHL[k_0,2]}$ for ${k_0 = 3,500,000}$ (note that ${k_0}$ is roughly of the order of ${\varpi^{-2}}$ as mentioned previously).

We have improved Zhang’s argument in a number of ways. Firstly, we have made the sieving argument that deduces ${DHL[k_0,2]}$ from results of the form (2) more efficient by optimising a certain cutoff function involved in the construction of the Selberg sieve; the optimal cutoff turns out to be given in terms of a certain Bessel function, and improves the relationship ${k_0 \sim \varpi^{-2}}$ to ${k_0 \sim \varpi^{-3/2}}$ ; see this post for details. Also, a modification of the truncated Selberg sieve due to Pintz allows one to take ${\delta}$ to be extremely small with almost no impact on ${k_0}$ (but at a certain technical cost, namely that the property of being smooth has to be weakened to another property which we have called “dense divisibility”, replacing the conjecture ${MPZ[\varpi,\delta]}$ by a variant that we have called ${MPZ'[\varpi,\delta]}$ ); see this post for details. Finally, by optimising the remaining steps in Zhang’s argument (see below), we have managed to increase ${\varpi}$ significantly, with the currently largest value of ${\varpi}$ that we can use being close to ${1/148}$ (and provisionally to ${1/108}$ ). The combination of these improvements has allowed us to take ${k_0}$ as low as ${1,466}$ (and provisionally to ${962}$ ).

At this stage we believe our arguments converting ${MPZ[\varpi,\delta]}$ (or variants thereof) to ${DHL[k_0,2]}$ is about as efficient as can be hoped for given the methods we have, and that the most significant further improvements will be coming from raising ${\varpi}$ beyond the currently available range.

— 3. The Heath-Brown identity and combinatorics —

Now we discuss how to establish estimates such as (2) in the case of smooth moduli, and in the case of congruences obeying a Chinese remainder theorem. Prior to Zhang’s paper, there were a number of results of this type established in a series of papers by (various combinations of) Bombieri, Fouvry, Friedlander, and Iwaniec, as well as some followup work by later authors, although the prior results were not directly applicable for the current problem (either because the function ${\Lambda}$ was replaced by a simpler arithmetic function, or the absolute values in (2) were replaced instead with a “well-factorable” weight, or the congruence classes ${a_q\ (q)}$ involved were more specialised, e.g. of the form ${a\ (q)}$ where ${a}$ was bounded and independent of ${q}$ ). However, Zhang was able to adapt and improve the analysis in the previous literature in a number of ways, to the point where he could in fact obtain an estimate ${MPZ[\varpi,\delta]}$ of the required strength.

We won’t describe the entire proof here, but give some of the important ideas in these arguments. The first observation is that one can decompose the von Mangoldt function ${\Lambda}$ as a combination of simpler functions, such as the ${k^{th}}$ order divisor functions

$\displaystyle \tau_k(n) := \sum_{n_1,\ldots,n_k \geq 1: n_1 \ldots n_k = n} 1,$

the modified ${k^{th}}$ order divisor functions

$\displaystyle \tau'_k(n) := \sum_{n_1,\ldots,n_k > 1: n_1 \ldots n_k = n} 1,$

or more generally certain combinations

$\displaystyle \psi_1 \ast \ldots \ast \psi_k$

of “nice” arithmetic functions ${\psi_1,\ldots,\psi_k}$ (we will be vague about what “nice” means here), where ${f \ast g(n) := \sum_{d|n} f(d) g(\frac{n}{d})}$ is the usual Dirichlet convolution. The point is that functions with this convolution structure are easier to sum and estimate. For instance, the basic estimate

$\displaystyle \sum_{n \leq x} \Lambda(n) = x + o(x)$

is of course the prime number theorem, which is already non-trivial, and improving the error term ${o(x)}$ here to ${O(x^{1-\epsilon})}$ for some fixed ${\epsilon>0}$ is a major open problem (and would be a huge breakthrough towards the Riemann hypothesis). In contrast, the divisor function

$\displaystyle \tau(n) = \tau_2(n) = \sum_{n_1,n_2 \geq 1: n_1 n_2 = n} 1$

is much easier to sum, and one can easily obtain the estimate

$\displaystyle \sum_{n \leq x} \tau(n) = x \log x + (2\gamma-1) x + O( x^{1/2} )$

by the elementary Dirichlet hyperbola method, which ultimately relies on the Dirichlet convolution structure ${\tau = 1 \ast 1}$ of ${\tau}$ . Similarly for the higher order divisor functions ${\tau_k}$ and their variants ${\tau'_k}$ , although the error terms become harder to estimate well when ${k}$ increases.

Why would we expect ${\Lambda}$ to be expressible in terms of functions such as ${\tau_k}$ or ${\tau'_k}$ ? To illustrate this sort of decomposition, let us make the major cheat that all numbers ${n}$ are square-free and have at most (say) four prime factors. (This is clearly quite a cheat; but note that a positive fraction of integers are square-free, and if we restrict attention to large prime factors, say factors larger than ${n^{1/5}}$ , then we do indeed have at most four such prime factors, so the cheat actually is not so terrible in some ways.) Then the quantity ${\Lambda(n)}$ is equal to ${\log n}$ when ${n}$ has one prime factor and zero when ${n}$ has two, three, or four prime factors. Meanwhile, ${\tau'_2(n)}$ is equal to ${0, 2, 6, 14}$ when ${n}$ has one, two, three, or four prime factors respectively. Similarly ${\tau'_3(n)}$ is equal to ${0, 0, 6, 36}$ and ${\tau'_4(n)}$ is equal to ${0,0,0,24}$ . Thus we see in all cases that

$\displaystyle \Lambda(n) = \log(n) ( 1 - \frac{1}{2} \tau'_2(n) + \frac{1}{3} \tau'_3(n) - \frac{1}{4} \tau'_4(n) ).$

Note that while a little computation is required to verify this identity, it is immediate from linear algebra that some identity of this type must exist, at least for square-free numbers with a bounded number of factors.

More generally, we have Linnik’s identity

$\displaystyle \Lambda(n) = \log n \sum_{k=1}^\infty \frac{(-1)^{k-1}}{k} \tau'_k(n), \ \ \ \ \ (4)$

which is valid for all natural numbers ${n}$ ; this identity can be proven by starting with the formal identity

$\displaystyle \log \zeta(s) = \sum_{k=1}^\infty \frac{(-1)^{k-1}}{k} (\zeta(s) - 1)^k$

for the Riemann zeta function ${\zeta(s) := \sum_{n=1}^\infty \frac{1}{n^s}}$ , differentiating this identity, then comparing Dirichlet series coefficients. (It is also a fun exercise to find a purely combinatorial proof of this identity.)

Morally speaking, Linnik’s identity reduces the task of proving (2) (or variants thereof) to the task of proving

$\displaystyle \sum_{q \leq x^{1/2+2\varpi}} | \sum_{n = a_q\ (q): n \in [x,2x]} \tau'_k(n) - \frac{1}{\phi(q)} \sum_{n \in [x,2x]} \tau'_k(n) | \ll x \log^{-A} x \ \ \ \ \ (5)$

for ${k=1,2,3,\ldots}$ . However, this implication is not quite rigorous, because the ${k}$ parameter on the right-hand side is unbounded. There is however a clever truncation of Linnik’s identity due to Heath-Brown, which only has finitely many terms, each one of which resembles a divisor function ${\tau_k}$ , albeit one which is averaged by an additional Dirichlet convolution. The precise identity is a little complicated (although not difficult to prove); see this post for details. Using this identity, we can indeed reduce (2) to slightly more complicated versions of the identities (5). By decomposing the versions of (5) obtained in this fashion into dyadic pieces (actually, one uses a decomposition that is slightly finer than the dyadic decomposition, but never mind this technical detail), it turns out that one can organise the resulting estimates to be proven into three classes, which Zhang calls “Type I estimates”, “Type II estimates”, and “Type III estimates”. The precise formulation of such estimates depends on the two parameters ${\varpi,\delta}$ alluded to earlier, as well as an additional parameter ${1/10 \leq \sigma \leq 1/2}$ demarcating the boundary between the Type I and Type III estimates. (The lower bound ${\sigma \geq 1/10}$ is needed to effect the combinatorial partition into Type I, Type II, Type III sums; it would be nice to remove this bound, but this seems to necessitate the introduction of further types of estimates (“Type IV” and “Type V”) which we have so far been unable to deal with effectively.) A precise definition of these estimates may be found at this page, but let us for now give an oversimplified caricature of what these estimates look like. A model case of a Type I estimate takes the form

$\displaystyle \sum_{q \leq x^{1/2+2\varpi}} | \sum_{n = a_q\ (q)} \alpha \ast \beta(n) - \frac{1}{\phi(q)} \sum_n \alpha\ast \beta(n) | \ll x \log^{-A} x \ \ \ \ \ (6)$

where ${\alpha,\beta: {\bf N} \rightarrow {\bf C}}$ are two sequences localised to scales ${\{ m: m \sim M\}}$ and ${\{ n: n \sim N\}}$ respectively, where one should think of ${M}$ and ${N}$ as being like ${x^{1/2+\sigma}}$ and ${x^{1/2-\sigma}}$ respectively; the functions ${\alpha,\beta}$ also obey certain bounds similar to those enjoyed by the divisor functions ${\tau_k}$ (e.g. their average value should be ${O(\log^{O(1)} x)}$ ) which we do not give in detail here. The modulus ${q}$ should be understood to be squarefree and smooth as in the statement of ${MPZ[\varpi,\delta]}$ (or if one is trying to prove ${MPZ'[\varpi,\delta]}$ instead, “smooth” needs to be replaced by “densely divisible”). The Type II sums are similar, except that one should now think of ${M}$ and ${N}$ as both being like ${x^{1/2}}$ . A model case of a Type III estimate takes the form

$\displaystyle \sum_{q \leq x^{\alpha}} | \sum_{n = a_q\ (q): n \in [x,2x]} \tau_3(n) - \frac{1}{\phi(q)} \sum_{n \in [x,2x]} \tau_3(n) | \ll x \log^{-A} x \ \ \ \ \ (7)$

where ${\alpha = \frac{1/2 + 2 \varpi}{\frac{3}{2}(\frac{1}{2}-\sigma)}}$ , and again ${q}$ should be understood to be square-free and smooth. (This is an oversimplification; the true Type III estimate involves a smoothly truncated, averaged version of ${\tau_3}$ , and it is to compensate for this oversimplification that the upper bound for ${q}$ has changed.) The Type I estimates are harder to prove when ${\sigma}$ gets larger, while the Type III estimates become easier. It is thus necessary to work out what estimates one can prove on both the Type I and Type III sides before one can optimise in ${\sigma}$ . The Type II estimates are less important (and in practice, in all the regimes in which we can prove Type I and Type III estimates so far, we have also been able to prove Type II estimates), but still need to be dealt of course. Thus far we have not been able to improve upon this portion of Zhang’s arguments much; we rely on the same Heath-Brown identity and combinatorial decomposition that Zhang does, as they seem to be more or less optimally efficient for decompositions of this type, at least for the appliction at hand. The task of proving ${MPZ[\varpi,\delta]}$ (or ${MPZ'[\varpi,\delta]}$ ) and hence ${DHL[k_0,2]}$ and ${B[H]}$ for various choices of parameters ${\varpi,\delta,k_0,H}$ is thus reduced to that of verifying Type I, Type II, and Type III estimates.

— 4. Type I estimates —

Now we give a very informal sketch of Zhang’s argument for establishing Type I estimates (details may be found at these two posts). It is based on previous arguments of Bombieri, Friedlander, and Iwaniec, relying on various analytic manipulations such as the use of the Cauchy-Schwarz inequality (and in particular on the dispersion method of Linnik that is based on this inequality) and Fourier identities (such as the Pólya-Vinogradov method of completion of sums), in order to eliminate the poorly understood sequences ${\alpha,\beta}$ , until one is only left with the task of estimating a certain incomplete Kloosterman-type sum, to which one uses standard tools from analytic number theory (such as the Weil bound for completed Kloosterman sums). We have continued to follow the same general strategy, but have found some improvements based on better bounds for incomplete Kloosterman sums.

We now give a little more detail. We will ignore the role of the technical parameter ${\delta}$ , and assume simply that all moduli are as smooth as needed for the argument. We change notation a little bit, replacing ${n}$ and ${q}$ by ${\tilde n}$ and ${\tilde q}$ , and consider a dyadic component of (8), namely

$\displaystyle \sum_{\tilde q \sim x^{1/2+2\varpi}} | \sum_{\tilde n = a_{\tilde q}\ (\tilde q)} \alpha \ast \beta(\tilde n) - \frac{1}{\phi(\tilde q)} \sum_{\tilde n} \alpha\ast \beta(\tilde n) | \ll x \log^{-A} x \ \ \ \ \ (8)$

One now takes advantage of the square-free smooth nature of ${\tilde q}$ to factor ${\tilde q = qr}$ , where ${q,r}$ are coprime, and ${r}$ is a little bit smaller than ${N = x^{1/2-\sigma}}$ , so that ${q}$ is a little bit larger than ${x^{1/2+2\varpi}/N = x^{\sigma+2\varpi}}$ ; the reason for this choice of factorisation is that it will turn out that we want ${r}$ to be as large as possible while still staying a bit less than ${N}$ . There is also a technical step in which we shift all the tiny prime factors of ${qr}$ to ${r}$ and not to ${q}$ (where “tiny” means something like “less than ${\exp(\log^{1/3} x)}$ “); this is needed to ensure that most pairs of ${q}$ ‘s that we encounter become coprime at a crucial juncture later in the argument. See this post for more details of this step. The congruence ${\tilde n = a_{\tilde q}\ (\tilde q)}$ similarly factors into ${\tilde n = a_q\ (q)}$ and ${\tilde n = a_r\ (r)}$ by (3), so we now have to prove something like

$\displaystyle \sum_{r \sim R} \sum_{q \sim Q: (q,r)=1} | \sum_{\tilde n = a_{q}\ (q); \tilde n = a_r\ (r); \tilde n \in [x,2x]} \alpha \ast \beta(\tilde n)$

$\displaystyle - \frac{1}{\phi(q) \phi(r)} \sum_{\tilde n \in [x,2x]} \alpha\ast \beta(\tilde n) | \ll x \log^{-A} x$

where ${R = x^{1/2-\sigma-\epsilon}}$ for some small ${\epsilon>0}$ and ${Q = x^{\sigma+2\varpi+\epsilon}}$ .

Roughly speaking, this estimate is asserting that we can estimate a quantity such as

$\displaystyle \sum_{r \sim R} \sum_{q \sim Q: (q,r)=1} c_{q,r} \sum_{\tilde n = a_{q}\ (q); \tilde n = a_r\ (r); \tilde n \in [x,2x]} \alpha \ast \beta(\tilde n)$

to accuracy ${O( x \log^{-A} x )}$ whenever ${c_{q,r}}$ are arbitrary bounded coefficients (where we will be a bit vague on what it means to estimate something to a given accuracy). Splitting ${\alpha \ast \beta(\tilde n)}$ as ${\sum_{m,n: mn = \tilde n} \alpha(m) \beta(n)}$ and ignoring the constraint ${\tilde n \in [x,2x]}$ , we may rearrange this expression as

$\displaystyle \sum_m \alpha(m) \sum_{r \sim R} \sum_{q \sim Q: (q,r)=1} c_{q,r} \sum_{n: mn = a_{q}\ (q); mn = a_r\ (r)} \beta(n).$

We are unable to take much advantage of the ${r}$ averaging, and will thus seek to estimate

$\displaystyle \sum_m \alpha(m) \sum_{q \sim Q: (q,r)=1} c_{q,r} \sum_{n: mn = a_{q}\ (q); mn = a_r\ (r)} \beta(n)$

to accuracy ${O( x R^{-1} \log^{-A} x)}$ for a fixed ${r \sim R}$ .

Now we start eliminating some of the poorly controlled expressions ${\alpha, c_{q,r}, \beta}$ . Applying a Cauchy-Schwarz, it (morally) suffices to estimate

$\displaystyle \sum_{m \sim M} | \sum_{q \sim Q: (q,r)=1} c_{q,r} \sum_{n: mn = a_{q}\ (q); mn = a_r\ (r)} \beta(n)|^2$

to accuracy ${O( x^2 R^{-2} M^{-1} \log^{-A} x )}$ , i.e. a little bit better than ${O( x^{1/2 + \sigma} )}$ . Note that because ${r}$ is a little bit less than ${N}$ , we have a non-trivial number of ${n \sim N}$ obeying the congruence condition ${mn = a_r\ (r)}$ for any given ${m}$ . This prevents the summation inside the absolute values from being so trivial that Cauchy-Schwarz could not gain anything.

The above expression can be rearranged as

$\displaystyle \sum_{q_1,q_2 \sim Q: (q_1q_2,r)=1} c_{q_1,r} \overline{c_{q_2,r}} \sum_{n,n'} \beta(n) \overline{\beta(n')}$

$\displaystyle \sum_{m \sim M: mn=a_{q_1}\ (q_1); mn' = a_{q_2}\ (q_2); mn=mn' = a_r\ (r)} 1.$

The constraint ${mn=mn' = a_r\ (r)}$ forces ${n=n'\ (r)}$ . Since ${r}$ is so close to ${N}$ , this basically forces ${n'}$ to equal ${n}$ (or to equal a shift ${n+kr}$ of ${n}$ for some small ${k}$ ). To simplify the exposition we will just look at the diagonal case ${n=n'}$ (the off-diagonal terms are treated similarly). Our task is now to control

$\displaystyle \sum_{q_1,q_2 \sim Q: (q_1q_2,r)=1} c_{q_1,r} \overline{c_{q_2,r}} \sum_{n} |\beta(n)|^2 \sum_{m \sim M: mn = a_{q_1}\ (q_1); mn = a_{q_2}\ (q_2); mn = a_r\ (r)} 1$

with accuracy better than ${O( x^{1/2+\sigma})}$ . Using averaging notation, this is basically the same as controlling

$\displaystyle {\bf E}_{q_1,q_2 \sim Q: (q_1q_2,r)=1} c_{q_1,r} \overline{c_{q_2,r}} {\bf E}_{n \sim N} |\beta(n)|^2$

$\displaystyle \sum_{m \sim M: mn = a_{q_1}\ (q_1); mn = a_{q_2}\ (q_2); mn = a_r\ (r)} 1$

with accuracy better than ${O( x^{-4\varpi})}$ .

Recall that we had the foresight to remove all the tiny primes from ${q_1,q_2}$ . This has the effect of making ${q_1,q_2}$ typically coprime. We will discard the non-coprime contributions (it turns out that they can be controlled with relatively easy estimates) and insert the condition ${(q_1,q_2)=1}$ in the above summation. We can also make ${n}$ coprime to ${q_1q_2r}$ since the ${m}$ summation vanishes otherwise.

The ${m}$ summation is over an interval of length ${M = x^{1/2+\sigma}}$ over a single congruence class ${a_{q_1 q_2 r}/n\ (q_1 q_2 r)}$ of modulus ${q_1 q_2 r \sim x^{1/2+\sigma+4\varpi}}$ . This sum can then be inverted via the Fourier transform to a dual sum over a range ${H \sim x^{4\varpi}}$ ; morally speaking we may replace

$\displaystyle \sum_{m \sim M: m = a_{q_1 q_2 r} / n\ (q_1 q_2 r)} 1$

with something like

$\displaystyle {\bf E}_{h = O(H)} e_{q_1 q_2 r}( \frac{a_{q_1 q_2 r}h}{n} ) \ \ \ \ \ (9)$

where ${e_q(n) := e^{2\pi in/q}}$ for ${x \in {\bf Z}/q{\bf Z}}$ , and the reciprocal ${\frac{1}{n}}$ here is taken inside the ring ${{\bf Z}/q_1q_2 r{\bf Z}}$ . The zero frequency ${h=0}$ can be controlled directly; we ignore it and work with non-zero ${h}$ . We are now trying to control

$\displaystyle {\bf E}_{n \sim N; h = O(H); q_1,q_2 \sim Q: (q_1 q_2,r) = (q_1,q_2)=1} |\beta(n)|^2 c_{q_1,r} \overline{c_{q_2,r}} e_{q_1 q_2 r}( \frac{a_{q_1 q_2 r}h}{n} ) \ \ \ \ \ (10)$

to accuracy better than ${O( x^{-4\varpi})}$ .

We can eliminate the ${\beta}$ next by performing a Cauchy-Schwarz in ${n}$ , but it turns out to be a bit more efficient to Cauchy-Schwarz in ${n}$ and ${q_1}$ , not just in ${n}$ . This places us in the position of having to control

$\displaystyle {\bf E}_{n \sim N; h,h' = O(H); q_1,q_2,q'_2 \sim Q} \overline{c_{q_2,r}} c_{q'_2,r} e_{q_1 q_2 r}( \frac{a_{q_1 q_2 r}h}{n} ) e_{q_1 q'_2 r}( - \frac{a_{q_1 q'_2 r}h'}{n} )$

to accuracy better than ${O( x^{-8\varpi} )}$ , where we have suppressed the various coprimality conditions on the ${q_1,q_2,q'_2}$ for brevity. So it suffices to get bounds on the exponential sum

$\displaystyle {\bf E}_{n \sim N} e_{q_1 q_2 r}( \frac{a_{q_1 q_2 r}h}{n} ) e_{q_1 q'_2 r}( - \frac{a_{q_1 q'_2 r}h'}{n} )$

which beat the trivial bound of ${O(1)}$ by about ${x^{8\varpi}}$ on average, for “typical” values of ${h,h',q_1,q_2,q'_2}$ . This is basically an incomplete Kloosterman sum of the shape

$\displaystyle \frac{1}{N} \sum_{n \sim N} e_q( \frac{c}{n} ) \ \ \ \ \ (11)$

for some modulus ${q}$ of typical size ${q \sim q_1 q_2 q'_2 r \sim x^{1/2+2\sigma+6\varpi}}$ and a coefficient ${c}$ which turns out to typically be more or less coprime to ${q}$ except in a certain diagonal case ${hq'_2 = h'q_2}$ , but it turns out in the Type I case that this diagonal contribution is manageable. A standard “Pólya-Vinogradov” type bound for such sums, ultimately based on Weil’s famous bound

$\displaystyle |\sum_{n \in {\bf Z}/p{\bf Z}: n \neq 0} e_p( \frac{a}{n} + bn)| \leq 2\sqrt{p}$

for completed Kloosterman sums, allows one to bound (11) by ${O( \frac{1}{N} \sqrt{q} )}$ (ignoring some logarithmic type errors and lower order terms). This gives us an acceptable estimate if

$\displaystyle \frac{1}{ x^{1/2-\sigma} } \sqrt{ x^{1/2+2\sigma+6\varpi} } \ll x^{-8\varpi}$

which may be rearranged as

$\displaystyle 8 \sigma + 44 \varpi < 1.$

(Recall that we are treating ${\delta}$ as negligible, otherwise we have to insert some factors of ${\delta}$ in this constraint as well.) Crucially, this constraint allows ${\sigma}$ to exceed ${1/10}$ , and thus gives a good range of Type I estimates if ${\varpi}$ is small enough. Further improvements have been obtained by using more refined estimates on incomplete Kloosterman sums (first discussed here); to date we have managed to (provisionally) replace the above constraint to

$\displaystyle 5 \sigma + 54 \varpi < 1$

which turns out to give superior numerical results. This reveals a tradeoff, in that more advanced exponential sum estimates can improve ${\sigma}$ at the expense of ${\varpi}$ ; we have not yet located what the optimal balance for this tradeoff is.

— 5. Type II estimates —

The Type II estimates are treated quite similarly to the Type I estimates and will only be discussed briefly here. If one repeats the Type I estimates verbatim, most of the same arguments go through (in fact they become better because the ${\sigma}$ terms are not present); however it turns out that the diagonal contribution ${hq'_2=h'q_2}$ that was manageable in the Type I setting, no longer becomes manageable in the Type II setting. To get around this one has to reduce the influence of the diagonal by taking a narrower Cauchy-Schwarz when eliminating ${\beta}$ from (10), namely that one only performs a Cauchy-Schwarz in ${n}$ rather than ${n,q_1}$ . The price one pays for this is that the off-diagonal terms become slightly worse (conceding a few more powers of ${\varpi}$ ); the best estimate we currently have here (again ignoring ${\delta}$ issues) is

$\displaystyle 68 \varpi < 1.$

— 6. Type III estimates —

The Type III estimates (7) were originally treated by Zhang using the method of Weyl differencing. More recently, a simpler method which gives better numerology was introduced by Fouvry, Kowalski, Michel, and Nelson, and may be sketched as follows. Our goal here is to control something like

$\displaystyle \sum_{q \sim Q} c_q \sum_{n = a_q\ (q): n \in [x,2x]} \tau_3(n)$

to accuracy better than ${O( x )}$ , where ${c_q}$ are bounded coefficients, and ${Q}$ is a quantity larger than ${x^{1/2}}$ (which we would like to take to be as large as possible). Expanding out the ${\tau_3}$ function and using dyadic decomposition, this basically amounts to controlling

$\displaystyle \sum_{q \sim Q} c_q \sum_{n_1 \sim N_1; n_2 \sim N_2; n_3 \sim N_3} 1_{n_1 n_2 n_3 = a_q\ (q)}$

to accuracy ${O( x \log^{-A} x)}$ for some ${N_1,N_2,N_3}$ that multiply to ${x}$ (e.g. one can take ${N_1=N_2=N_3=x^{1/3}}$ for sake of discussion, although the precise choice of ${N_1,N_2,N_3}$ turns out to not be so important). Applying Fourier decomposition as in (9), one can write this expression roughly speaking as

$\displaystyle \sum_{q \sim Q} c_q {\bf E}_{h_1 = O(H_1), h_2 = O(H_2), h_3 = O(H_3)} \sum_{x,y,z \in {\bf Z}/q{\bf Z}: xyz=a_q} e_q( h_1 x + h_2 y + h_3 z )$

where ${H_1,H_2,H_3}$ are the dual scales ${H_i := Q / N_i}$ . It turns out that the contributions when ${h_1,h_2,h_3}$ vanish, or more generally share a common factor with ${q}$ , can be dealt with, so we ignore them and assume that ${h_1,h_2,h_3}$ are coprime with ${q}$ . In this case, we can write the inner sum after a change of variables as

$\displaystyle \sum_{x,y,z \in {\bf Z}/q{\bf Z}: xyz=a_q} e_q( h_1 x + h_2 y + h_3 z ) = q K_3( a_q h_1 h_2 h_3; q )$

where ${K_3}$ is the hyper-Kloosterman sum

$\displaystyle K_3(a;q) := \frac{1}{q} \sum_{x,y,z \in {\bf Z}/q{\bf Z}: xyz = a} e_q(x+y+z). \ \ \ \ \ (12)$

The normalisation ${\frac{1}{q}}$ in (12) reflects the expected square root cancellation in this sum, which is a sum of about ${O(q^2)}$ phases that one expects to behave more or less independently of each other. Indeed, using the deep results of Deligne on the Weil conjectures, one can show that

$\displaystyle |K_3(a;q)| \ll 1 \ \ \ \ \ (13)$

for ${a}$ coprime to ${q}$ (ignoring some log factors).

Replacing ${q}$ by ${Q}$ (which can be done by adjusting the ${c_q}$ a little bit), our task is now to control

$\displaystyle \sum_{q \sim Q} c_q {\bf E}_{h_1 = O(H_1), h_2 = O(H_2), h_3 = O(H_3)} K_3(a_q h_1 h_2 h_3; q)$

to accuracy better than ${O( x / Q )}$ . If we apply Deligne’s bound (13) right away, we get a bound of ${O(Q)}$ , which only works for ${Q < x^{1/2}}$ , which recovers the Bombieri-Vinogradov theorem for ${\tau_3}$ but no better. To improve upon this we perform a Cauchy-Schwarz. We first perform the useful substitution ${h=h_1h_2h_3}$ , which rewrites the above sum as something like

$\displaystyle \sum_{q \sim Q} c_q {\bf E}_{h = O(H_1 H_2 H_3)} \tilde \tau_3(h) K_3(a_q h; q)$

where ${\tilde \tau_3}$ is a truncated version of ${\tau_3}$ (counting factorisations ${h=h_1h_2h_3}$ with ${h_1 = O(H_1), h_2 = O(H_2), h_3=O(H_3)}$ ). Note that ${H := H_1 H_2 H_3}$ is given by ${H = Q^3 / N_1 N_2 N_3 \sim Q^3 / x}$ , so that ${x/Q \sim Q^2 / H}$ . We interchange the sum, so we are now asking to bound

$\displaystyle {\bf E}_{h = O(H)} \tilde \tau_3(h) {\bf E}_{q \sim Q} c_q K_3(a_q h; q)$

to accuracy better than ${Q/H}$ .

At this point it turns out to be optimal to use the smoothness of the modulus ${q}$ to split ${q=rs}$ where ${r,s \sim Q^{1/2}}$ , so we wish to control something like

$\displaystyle {\bf E}_{h = O(H); r \sim Q^{1/2}} \tilde \tau_3(h) {\bf E}_{s \sim Q^{1/2}} c_{rs} K_3(a_{rs} h; rs).$

to accuracy better than ${Q/H}$ . If we Cauchy-Schwarz in ${h}$ and ${r}$ , we end up having to bound

$\displaystyle {\bf E}_{h = O(H); r \sim Q^{1/2}} {\bf E}_{s,s' \sim Q^{1/2}} c_{rs} c_{rs'} K_3(a_{rs} h; rs) \overline{K_3(a_{rs'} h; rs')}$

to accuracy better than ${Q^2/H^2}$ . The diagonal contribution ${s=s'}$ is ${O( Q^{-1/2} )}$ thanks to (13). Now we turn to the opposite case when ${s,s'}$ are coprime. The goal is then to establish the estimate

$\displaystyle | {\bf E}_{h= O(H)} K_3(a_{rs} h; rs) \overline{K_3(a_{rs'} h; rs')} | \ll Q^2 / H^2$

for an incomplete Kloosterman correlation with net modulus ${rss'}$ . It turns out that there is a Pólya-Vinogradov type bound of ${O( (rss')^{1/2} / H ) \sim Q^{3/4} / H}$ for this sum (though this requires a non-trivial amount of Deligne’s Weil conjecture machinery to actually prove). So we are done if

$\displaystyle Q^{-1/2}, Q^{3/4}/H \ll Q^2 / H^2$

which simplifies to ${H \ll Q^{5/4}}$ , or equivalently ${Q \ll x^{4/7}}$ . So this argument allows one to obtain (7) for ${\alpha}$ up to ${4/7}$ , which corresponds to the constraint

$\displaystyle 12 \sigma > 1 + 28 \varpi$

which, happily, overlaps enough with the Type I bounds and the combinatorial constraint ${\sigma > 1/10}$ to give ${MPZ[\varpi,\delta]}$ (or ${MPZ'[\varpi,\delta]}$ ) for relatively good values of ${\varpi}$ (and ${\delta}$ , which we have ignored in this discussion). We have managed to (provisionally) improve upon this constraint to

$\displaystyle 18 \sigma > 1 + 56 \varpi$

by exploiting an additional averaging that is present in the true Type III estimate (and which was suppressed in (7)). Combining this with the best Type I estimate we currently have (and with the combinatorial constraint ${\sigma > 1/10}$ ) gives us the best value of ${\varpi}$ currently available, namely ${1/108}$ (note that this is well below the Type II constraint, which may thus be ignored). Actually, the Type III estimates are now so strong that they are no longer critical for further improvements in the numerology; it is either the Type I estimate or the combinatorial constraint ${\sigma>1/10}$ that needs improving instead. (Alternatively, if one is willing to use a worse value of ${\varpi}$ , namely ${\varpi < 1/324}$ , one can use the Type I estimates to raise ${\sigma}$ up to ${1/6}$ , which closes off the Type III case completely and allows for a slightly more elementary proof of Zhang’s theorem in that the full strength of Deligne’s proof of the Weil conjectures is no longer needed (although Weil’s classical bound on Kloosterman sums is still required).)

86 comments

Comments feed for this article

30 June, 2013 at 12:46 pm

Muchos están esperando tu ayuda y que les prediques la palabra de Dios.

[…] formula 1Bounded gaps between primes (Polymath8) – a progress report For any , let denote the assertion that there are infinitely many pairs of consecutive primes whose […]

30 June, 2013 at 1:34 pm

bengreen

I haven’t been following every detail of this so far, but if it’s true that the Type I/II estimates cover everything, as hence you avoid the deeper Deligne stuff, then to my tastes that’s the most significant development of the polymath project so far. It means one could in principle teach the whole proof in a graduate course. Furthermore (I haven’t checked this) if you can do Type I for $\sigma \geq \frac{1}{6}$ then can’t you in fact use Vaughan’s identity instead of Heath-Brown?

30 June, 2013 at 11:47 pm

v08ltu

I agree this would be quite significant. I think the gain is described here: https://terrytao.wordpress.com/2013/06/23/the-distribution-of-primes-in-densely-divisible-moduli/#comment-236387

Namely we achieve $\sqrt N(d_1d_2)^{1/6}=\sqrt N(Q^3R)^{1/6}$ rather than the (dominant) $\sqrt NQ$ of Lemma 10. My calculations agree that this allows one to take $\sigma$ as large as 1/5. Here $R\sim N\sim x^{1/2-\sigma},Q\sim d/N\sim \sqrt x/N\sim x^\sigma$ (up to $\omega,\delta$ parts), and the above expressions need to be less than $N$ .

1 July, 2013 at 7:28 am

Terence Tao

Just recording the results of a discussion I had with Ben on this. It does look like Vaughan’s identity with $U=V=x^{1/3}$ , together with a Zhang-Type I estimate that works for $\sigma = 1/6$ , is enough to establish Zhang’s theorem; the Vaughan-Type II sums can be handled by Zhang’s Type I/II analysis, and the Vaughan-Type I sums can be handled by either Zhang Type I/II or Zhang Type 0, depending on the exact scales involved. So one does not need either the Heath-Brown identity or Deligne’s theory to prove Zhang’s theorem, just Weil’s bound on completed exponential sums. Actually Ben pointed out that the more elementary bound $|\sum_{n \in {\bf Z}/p{\bf Z}} e(f(n))| \ll p^{3/4}$ of Kloosterman for nonlinear rational functions $f$ , when combined with sufficiently many iterations of the q-van der Corput method, give non-trivial bounds on even very short incomplete Kloosterman sums on smooth moduli that suffice to give Type I/II estimates for $\sigma$ arbitrarily close to 1/2, and in particular at least as large as 1/6, which suffices for the purposes of establishing Zhang’s theorem (albeit with somewhat worse values of $\varpi,k_0,H$ ).

1 July, 2013 at 9:39 am

Deligne’s proof of the Weil conjectures, technically, is absolutely “needed” for Dr. Zhang to have his paper accepted by Annals of Math.quickly. If such an amazing big result had been announced with only an elementary proof by a guy whom basically no one knows of, the editors wouldn’t even have taken a look at his manuscript.

30 June, 2013 at 2:24 pm

David Roberts

In point 1 near the top the link to the k-tuples page is missing – did you mean for it to be on the word ‘here’?

[Corrected, thanks – T.]

30 June, 2013 at 2:46 pm

Greg

Small typo: two displayed equations before (4), the coefficient of $x$ should be $2\gamma-1$ instead of $-1$ .

[Corrected, thanks – T.]

30 June, 2013 at 3:57 pm

Sniffnoy

Also, something seems to have gotten lost here:

“This has produced many of the best constructions so far, typically 5 Very recently,”

[Corrected, thanks – T.]

30 June, 2013 at 4:04 pm

Gergely Harcos

I just posted an improvement (hopefully) to Theorem 8 in the earlier thread (https://terrytao.wordpress.com/2013/06/23/the-distribution-of-primes-in-densely-divisible-moduli/). The point is that by properly averaging over $q_1$ , the constraint (47) can be weakened so that it follows from (45). I have not checked if this leads to any improvement in Theorem 4 of the earlier thread, but eliminating a condition is always a good thing.

30 June, 2013 at 10:50 pm

Terence Tao

Thanks for this! Actually it turns out that this condition could already be eliminated by a later refinement of the incomplete Kloosterman sum estimate in which the $(c_1,d'_1)^{1/4}/(d'_1)^{1/4}$ factor was improved to $\frac{(c_1,d'_1)}{d'_1} \frac{(c_2,d'_2)}{d'_2}$ (basically by using the older completion of sums method instead of the van der Corput method when N is large: see https://terrytao.wordpress.com/2013/06/22/bounding-short-exponential-sums-on-smooth-moduli-via-weyl-differencing/#comment-236033 . But this additional refinement you have pushes this contribution down even further, although it is currently not the dominant constraint so unfortunately it does not (yet) give any improvement to the numerology. (But as you say, it doesn’t hurt. :-).

1 July, 2013 at 11:31 am

Gergely Harcos

Thank you! I will try to catch up with the latest developments. It is not easy (for me): the blog entries and comments that constitute polymath8 would occupy now about 450 printed pages!

30 June, 2013 at 4:22 pm

Andrew Sutherland

Regarding the second Hardy-Littlewood conjecture, this graph (http://math.mit.edu/~drew/hw2data.gif) may be of interest. It shows lower bounds for k-pi(w) versus w, with w=H(k)+1, using the most current upper bounds on H(k) from the new tuples database (which in just 4 days has processed more than 1000 submissions, improving some 800 H(k) values). The dips in the chart are good targets for future improvement.

30 June, 2013 at 10:46 pm

Terence Tao

Dear Andrew,

It looks like the link is 403’ed currently (permissions are not set properly). EDIT: Never mind, it seems to work now.

30 June, 2013 at 11:16 pm

Andrew Sutherland

The 403 error is an intermittent problem that are IT folks are working on, just hit refresh if it happens again.

30 June, 2013 at 6:17 pm

Qiaochu Yuan

Thanks for the update! This was helpful.

Some formatting seems to have gone wrong around “but only those moduli which were squarefree and http://www.ams.org/mathscinet-getitem?mr=2414788.)…”

[Corrected, thanks – T.]

30 June, 2013 at 6:40 pm

xfxie

Let my computer did a systematic scan to obtain feasible $k_0$ values for different $(\varpi, \delta)$ settings. The table can be found here:

http://www.cs.cmu.edu/~xfxie/project/admissible/k0table.html

A basic observation is that the coefficient for $\delta$ seems to have a quite minor effect on determining $k_0$ values. So I assume that testing on a single $\delta$ coefficient (or a few more) might be sufficient to gain some knowledge on possible $k_0$ values. I did test some rows to confirm more.

All these data could be generated by an old MacBook machine (otherwise it might be idle forever) in less than one day. So there is no difficulty to generate a more complete table, if it might be useful for some guys. I assume many of them might still be improved. I am also not quite sure about the correctness of the settings of parameter ranges.

1 July, 2013 at 6:44 pm

xfxie

Just cleared the code and put a download link in the webpage above.

1 July, 2013 at 12:19 am

Shizhuo Looi

Thank you for this summary and update; it was helpful. Just a very minor point: when you summarize Zhang’s argument, there seems to be a missing parenthesis at the end of point 1.

[Corrected, thanks – T.]

1 July, 2013 at 1:28 am

Grégoire Nicollier

In Section 3, a prime is missing in the definition of the modified order divisor functions.

[Corrected, thanks – T.]

1 July, 2013 at 3:31 am

Michael

The direction of the $\gg$ sign in the third-to-last display is opposite sense to the following line

[Corrected, thanks – T.]

1 July, 2013 at 4:55 am

pigh3

In point 3 of introduction, TypeIII[\varpi, \delta] (last mention of TypeIII) should probably be TypeIII[\varpi, \delta, \sigma].

[Corrected, thanks – T.]

1 July, 2013 at 9:20 am

Pace Nielsen

General questions for the polymath participants:

While I’m comfortable with convolutions, I’m not as familiar with the methods which require smoothness of one of the convolved functions. In particular, I’ve enjoyed learning about “completion of sums,” although it is still somewhat of a black box for me in some of the discussions.

I noticed that in the (more detailed) Type I analysis, we replace $\alpha$ (after some Cauchy-Schwarzing) by a smooth sequence, in order to take advantage of completion of sums. On the other hand, in the Type III analysis, smoothness is used (as far as I can tell) to do completion of sums twice, and to give a Taylor series once. I was wondering: Can a similar trick as in the Type I case be used to allow non-smoothness in one or more of the completion of sums in the Type III case?

Also, if $\psi_1,\psi_2$ are smooth, how “far away” is $\psi_1\ast \psi_2$ from being smooth?

1 July, 2013 at 10:45 pm

Terence Tao

Dear Pace,

I can answer your second question first: because Dirichlet convolution is based on the multiplicative structure of the integers rather than the additive structure, the convolution of two smooth functions is unfortunately not very smooth in general. For instance the divisor function $\tau = 1 \ast 1$ is quite rough, jumping down to 2 at the primes but typically much larger (the average value of $\tau(n)$ is about $\log n$ ).

If one replaced a smooth sequence by a rough sequence in the Type III sums, one could eliminate it by Cauchy-Schwarz, but each use of Cauchy-Schwarz tends to halve any gains one gets later on in the argument (e.g. from the Weil conjectures), or equivalently doubles the amount of gain one has to generate in order to make up for losses (e.g. from completion of sums). Conversely, one might be able to improve the Type I sum numerology if $\beta$ was smooth as we could avoid one application of Cauchy-Schwarz; this may potentially deal with some “Type IV” sums (of the form $\psi_1 * \ldots * \psi_4$ where the $\psi_i$ are smooth and supported near $x^{1/5}, x^{1/5}, x^{1/5}, x^{2/5}$ respectively) but not unfortunately for “Type V” sums (of the form $\psi_1 * \ldots * \psi_5$ where the $\psi_i$ are all smooth and supported near $x^{1/5}$ ) where $\beta$ looks a bit like $\tau$ and thus not very smooth. (There are some fancy techniques coming from Eisenstein series that I don’t understand that could potentially start controlling exponential sums such as $\sum_n \beta(n) \beta(n+l) \Phi(\ldots)$ when $\beta$ looks like a divisor function $\tau$ , but the gains are very small and also rather complicated, and may end up being inferior to the current Cauchy-Schwarz methods.)

2 July, 2013 at 6:14 am

Pace Nielsen

Dear Terry,

Thanks for explaining this so clearly. The reason I asked is that, at present, it isn’t the Type III sums which are the roadblock, and so we can be a little more lossy if we also able to deal with the combinatorial problems. And the Type IV, V,… sums are incorporated into Type III if among $\psi_1,\psi_2,\psi_3$ , both $\psi_1$ and one of the other two sequences can be assumed non-smooth.

My current project is to understand these sums well enough to work out how this change affects the numerology, and whether the losses incurred by two Cauchy-Schwarzes are offset by the ability to lower $\sigma$ to 0.

1 July, 2013 at 11:02 am

E.L. Wisty

Reblogged this on Pink Iguana.

1 July, 2013 at 5:25 pm

Avi Levy

The first two paragraphs below the fold (right before Conjecture 2) have a couple typos regarding $k$ and $k_0$ being flipped at times. Perhaps just stick to $k_0$ to avoid confusion?

[Corrected, thanks – T.]

1 July, 2013 at 9:59 pm

Terence Tao

I’m recording the outcome of the idea (inspired by a comment of Philippe Michel) to readjust the Cauchy-Schwarz in the Type I sums (something that I’ve called “Level 6” on the wiki, skipping Level 5 for now which was more difficult to implement than I had hoped). This time around it does seem to improve the final value for $\varpi$ , in contrast to the Level 4 estimates which actually made things worse. (Although Level 4 (if iterated) does have the effect of showing that Type I estimates hold for $\sigma$ arbitrarily close to 1/2 if one is willing to set $\varpi$ sufficiently close to zero. This observation might be useful for some other application than bounded gaps beween primes, but doesn’t seem to be directly useful for our current project.)

Anyway, to Level 6. We will need some sort of “double dense divisibility”, but I will punt on this as before by first working in the case when the modulus is $x^\delta$ -smooth, which gives us all the dense divisibility we need (at the cost of making the numerology to get from $MPZ[\varpi,\delta]$ to $DHL[k_0,2]$ a bit worse, by forcing $\delta$ and $\delta'$ to be equal).

If we go through the Type I argument from https://terrytao.wordpress.com/2013/06/12/estimation-of-the-type-i-and-type-ii-sums/ , we reach a point (see equation (39) from that post) where we have to prove the estimate

$\sum_{1 \leq h \leq H} \sum_{q_1,q_2 \sim Q} c_{h,q_1,q_2} \sum_{n} \beta(n) \beta(n+kr) \Phi(h,q_1,q_2; n) \lessapprox x^{-\varepsilon} Q^2 N$ (*)

where the $c_{h,q_1,q_2}$ are bounded coefficients, and

$x^{1/2-\sigma} \ll N \ll x^{1/2-2\varpi-\varepsilon}$

$M \sim x/N$

$x^{-\delta-\varepsilon} N \ll R \ll x^{-\varepsilon} N$

$Q \ll x^{1/2+2\varpi}/R$

$H = x^\varepsilon Q^2 R/M$

$\Phi(h,q_1,q_2;n) = 1_{(q_1,r)=(q_2,r)=(q_1,q_2)=(n,r)=(n,q_1)=(n+kr,q_2)=1}$

$e_r( \frac{a_r h}{nq_1 q_2} ) e_{q_1}( \frac{b_{q_1}h}{n r q_2} ) e_{q_2}( \frac{b'_{q_2} h}{(n+kr) r q_1} ) .$

Previously we have dealt with (*) in the Type I case by performing Cauchy-Schwarz in the $n, q_1$ variables. Now we rebalance this by factoring $q_2$ (which is $x^\delta$ -smooth by construction) as $q_2 = s_2 t_2$ where $s_2 \sim S$ , $t_2 \sim T$ for some $ST \sim Q$ , and we can force

$x^{-\delta} S_0 \ll S \ll S_0$

for some $1\leq S_0 \leq Q$ to be chosen later. We now need to establish

$\sum_h \sum_{q_1 \sim Q; s_2 \sim S; t_2\sim T} c_{h,q_1,s_2 t_2} \sum_{n} \beta(n) \beta(n+kr) \Phi(h,q_1,s_2 t_2; n) \lessapprox x^{-\varepsilon} Q^2 N$ .

If we perform Cauchy-Schwarz now in $n,q_1,s_2$ , we reduce to

$\sum_{1 \leq h,h' \leq H} \sum_{q_1 \sim Q; s_2 \sim S; t_2,t'_2\sim T}$

$|\sum_{n} \psi_N(n) \Phi(h,q_1,s_2 t_2; n) \overline{\Phi(h,q_1,s_2 t'_2; n)}|$

$\lessapprox x^{-\varepsilon} Q^2 T N$ .

We first control the diagonal case $h t'_2 = h' t_2$ , which is a little stronger than it was in previous arguments. By the divisor bound, there are $\lessapprox H Q S T$ possible values of $(h,h',q_1,s_2,t_2,t'_2)$ that contribute to this diagonal case, and for each such contribution we use the
trivial bound of $O(N)$ for the $n$ summation. (It just occurred to me on writing this that one could perhaps do a bit better than the trivial bound here, but then I realised that the $(h,t_2)=(h',t'_2)$ subcomponent of the diagonal has no such cancellation and is already a significant fraction of the diagonal, so it seems there is no gain available). The diagonal contribution is thus acceptable if

$HQ S T N \lessapprox x^{-\varepsilon} Q^2 T N$

thus

$S \lessapprox x^{-\varepsilon} Q / H.$

We thus set $S_0 := x^{-\varepsilon} Q/H$ . (This requires us to have $S_0 \gtrapprox 1$ , but this turns out to follow from the Type I condition $N \ll x^{1/2-2\varpi-\varepsilon}$ .)

Now for the off-diagonal terms. On using the rebalanced van der Corput estimate (see https://terrytao.wordpress.com/2013/06/23/the-distribution-of-primes-in-densely-divisible-moduli/#comment-236387 ) we have

$|\sum_{n} \psi_N(n) \Phi(h,q_1,s_2 t_2; n) \overline{\Phi(h,q_1,s_2 t'_2; n)}|$

$\lessapprox N^{1/2} x^{\delta/6} (RQST^2)^{1/6} + \frac{(ht'_2-h't_2,r)}{r} N,$

so the total off-diagonal contribution is

$\lessapprox H^2 QST^2 ( N^{1/2} x^{\delta/6} (RQST^2)^{1/6} + R^{-1} N ),$

and we win if we have both

$N^{1/2} x^{\delta/6} ( RQST^2 )^{1/6} \lessapprox x^{-\varepsilon} N / H^2$

and

$R^{-1} \lessapprox x^{-\varepsilon} / H^2.$

We can bound

$RQST^2 = RQ^3 / S \lessapprox x^{\delta+\varepsilon} RQ^2 H$

so the conditions become

$x^{\delta/3} R^{1/6} Q^{1/3} \lessapprox x^{-7\varepsilon/6} N^{1/2} H^{-13/6}$

and

$H^2 \lessapprox x^{-\varepsilon} R.$

The worst case arises when

$QR = x^{1/2+2\varpi}, N = x^{1/2-\sigma}, R = x^{1/2-\sigma-\delta-\varepsilon}$

in which case we have

$Q = x^{2\varpi + \sigma + \delta + \varepsilon}, H = x^{4\varpi + \delta + \varepsilon}$

and the conditions become

$\frac{\delta}{3} + \frac{1}{6} (\frac{1}{2}-\sigma-\delta) + \frac{1}{3} (2\varpi+\sigma+\delta)$

$< \frac{1}{2} (\frac{1}{2}-\sigma) - \frac{13}{6} (4\varpi + \delta)$

and

$2 (4\varpi + \delta) < \frac{1}{2}-\sigma-\delta$

which simplify to

$56 \varpi + 16 \delta + 4 \sigma < 1$

and

$16 \varpi + 6 \delta + 2\sigma < 1$

The second condition is implied by the first, so we have obtained a Type I estimate whenever

$56 \varpi + 16 \delta + 4 \sigma < 1$ .

Playing this against $\sigma > 1/10$ (the Type II and Type III constraints can be checked to be non-dominant here) gives

$\frac{280}{3} \varpi + \frac{80}{3} \delta < 1$

which is a little bit better than before in the $\varpi$ aspect, but worse in the $\delta$ aspect, particularly since we had to use $x^\delta$ -smoothness rather than dense divsibility and so will have to take $\delta'=\delta$ when converting to $k_0$ . However this latter defect is presumably temporary once we figure out what “double dense divisibility” means. (Though the complexity of this argument is beginning to raise the question of whether the final paper should focus on the messiest but strongest results, or instead focus on a slightly less strong but cleaner result. I guess it’s still a bit premature to discuss these things though.)

1 July, 2013 at 10:32 pm

Terence Tao

Incidentally, I’m coming around to the opinion that absent a radically different way to do the Type I estimates, we’re almost at the end of the road for easy improvements here (and thus probably for the Polymath8 project as a whole). In order to get to the point where we are estimating an exponential sum such as

$\sum_n \psi_N(n) \Phi(\ldots) \overline{\Phi(\ldots)}$ , (*)

one has to perform one completion of sums (to deal with the congruence conditions) and two Cauchy-Schwarz’s (to eliminate the $\alpha,\beta$ coefficients). The completion of sums costs a factor of $H$ , which is about $x^{4\varpi}$ , and this is amplified to $H^2 \approx x^{8\varpi}$ by the Cauchy-Schwarz. So one has to gain a factor of about $x^{8\varpi}$ over the trivial bound in (*). Even in the best-case scenario (Hooley conjecture) that one has square root cancellation in (*), we still need $x^{8\varpi} \ll N^{1/2}$ ; since $N$ can be as low as $x^{1/2-\sigma}$ and $\sigma$ has to be at least 1/10, this forces $\varpi > 1/40$ . Now we are a long way from actually reaching the Hooley conjecture, even for smooth moduli, which is why our values of $\varpi$ are more like 1/108 or 3/280; it is conceivable that some increasingly heroic efforts could shave a bit more off of the exponential sum estimates (possibly by exploiting the additional averaging in h, r parameters that are available, although my initial efforts in this direction have been rather fruitless) but I think the era of dramatic improvements in the numerology are basically over, I’m afraid, absent a radical new way to perform these estimates (or else a new way to perform Type IV and Type V estimates, which would let us get past the annoying $\sigma > 1/10$ barrier).

2 July, 2013 at 2:48 am

Eytan Paldi

1. Perhaps the combinatorial lemma should be somehat modified (as well as the definitions of types) to improve the estimate of the “modified type I”?

2 July, 2013 at 4:52 pm

Brian Rothbach

I think you can gain a little bit by replacing the $\sigma$ in the combinatorial lemma with two parameters: instead of using type II estimates on the interval $[1/2-\sigma,1/2+\sigma]$ , use them on the interval $[1/2-\sigma_1,1/2+\sigma_2]$ . The restraint on sigma becomes $3\sigma_1+2\sigma_2>=1/2$ (and that the \sigma’s are positive), by the exact same argument as before, but now you can optimize the two parameters separately to improve the parameters for type I estimates.

2 July, 2013 at 5:36 pm

Pace Nielsen

Suppose we are looking at the situation where we have two numbers whose sum is 1 (which is what happens both in the Type I and Type II cases). Thus, one number is $1/2-\sigma$ and the other number is $1/2+\sigma$ . Hence, the extra generality of an uneven interval is no help in Type I/II situations. If you optimize on one end, you must have the same $\sigma$ on the other side.

You could possibly introduce another type of summation where the boundaries are uneven. If you want to do so, consider the following main case when there are five equal numbers $t_1=\cdots =t_5=1/5$ . There are only so many ways to combine them all. Combining them into two numbers either gives $2/5,3/5$ or $1/5,4/5$ or $0,1$ . The last doesn’t work, for a number of reasons (lack of a Siegel-Walfisz theorem, lack of picking divisors in appropriate intervals, etc…). The first one is better than the second, and so $2/5,3/5$ is the best option, combinatorially, when combining into two numbers.

Now you can work out what happens when trying to combine them into three numbers, etc…

2 July, 2013 at 7:27 pm

Brian Rothbach

Ah, I see. I was misinterpreting which of the Type estimates correspond to cases in the combinatorial lemma, and the estimates that are causing difficulties are exactly the ones where the unequal intervals don’t help.

2 July, 2013 at 5:58 pm

Pace Nielsen

Brian,

By the way, I proposed something like that, consisting of a new Type consisting of a convolution of three sequences: the biggest one nonsmooth, and the smaller ones both smooth. In terms of the case I gave above, this would correspond to the decomposition $3/5, 1/5,1/5$ . The analysis would probably follow the same path as for Type I sums, except we would replace $\beta$ everywhere by a convolution of two smooth sequences (coming from the Heath-Brown decomposition). The trouble would then be to decouple that convolution in a reasonable manner (which unfortunately seems unlikely).

2 July, 2013 at 7:54 am

xfxie

Initial calculation got $k_0$ =722 for (280/3,80/3), for $\varpi$ = 3/280-2.9850449068186893*10-5, $\delta'$ =0.03373456067881111, and $A$ =618.7045821541182.

Hopefully it does not violate some constraints.

2 July, 2013 at 8:00 am

Terence Tao

This will probably be close to the truth once we figure out how to relax the condition of $x^\delta$ -smoothness we are currently using (probably by developing some sort of notion of “double dense divisbility”) but right now we are forced to take $\delta=\delta'$ in order to get the smoothness (which makes kappa_3 vanish and renders A irrelevant), which will probably make k_0 increase a little bit (but it should still be better than what we had before).

2 July, 2013 at 9:08 am

Hannes

For $\delta = \delta'$ I think $k_0 = 873, \varpi = 3/280 - 0.1147/10^2$ works. This is a $k_0$ for which Engelsma’s bound has been improved.

Tao: In a previous post you write $\delta = \tilde\delta$ instead of $\delta = \delta'$ .

[Corrected, thanks – T.]

2 July, 2013 at 10:40 pm

Terence Tao

Thanks for this! This illustrates the fair amount of gain we could extract if we could relax back from $x^\delta$ -smoothness to something more like dense divisibility, then we would get something much closer to xfxie’s computed values of 720. I’ll try to see if the arguments for the Type I sums can be recast in terms of something like dense divisibility.

2 July, 2013 at 10:38 am

xfxie

The maple file is here: http://www.cs.cmu.edu/~xfxie/sol_872.mpl

The script is based on the maple script by Terence — just added a new constraint $\delta' = \delta$ .

This file stands for $k_0$ =872 for (280/3,80/3), as $\varpi= 3/280-4992.469008926887/10^5$ , $A$ =927.8564427404251.

Hopefully this one will be slightly more correct.

2 July, 2013 at 12:10 pm

Hannes

Unfortunately I think $\varpi > 0$ is not satisfied in this case.

2 July, 2013 at 12:43 pm

xfxie

@Hannes, Thanks for pointing out the error. Now I get more sense in setting parameters.

2 July, 2013 at 8:17 am

xfxie

A refined result is $k_0$ =720 for (280/3,80/3), for $\varpi$ = 3/280-1.1591660703532822*10-5, $\delta'$ =0.006805137872659862, and $A$ =369.2931543045393 .

Seems A is quite flexible, A=369 also works.

2 July, 2013 at 7:30 pm

The quest for narrow admissible tuples | Secret Blogging Seminar

[…] guest post summarizing the current state of affairs. This task is made easier by Tao’s recent progress report on the polymath project to sharpen Zhang’s result on bounded gaps between primes. If you […]

3 July, 2013 at 7:55 am

Terence Tao

I’m recording here some notes on double dense divisibility that almost allow us to recover the near-optimal numerology of the Pintz sieve (and in particular to not have to force $\delta'=\delta$ ).

Recall that a number $n$ is said to be $x^\delta$ -densely divisible if, for every $1 \leq R \leq n$ , one can find a factor of $n$ in the range $[x^{-\delta} R, R]$ . Let us say that $n$ is doubly $x^\delta$ -densely divisible if, for every $1 \leq R \leq n$ , one can find a factor of $n$ in $[x^{-\delta} R,R]$ which is itself $x^\delta$ -densely divisible. Clearly double $x^\delta$ -dense divisibility implies $x^\delta$ -dense divisibility; also, being $x^\delta$ -smooth implies double $x^\delta$ -dense divisibility because $x^\delta$ -smooth numbers are $x^\delta$ -densely divisible, and any factor of a $x^\delta$ -smooth number is again $x^\delta$ -densely divisible.

Note though that double dense divisibility is stronger than single dense divisibility. For instance, if $p,q$ are primes of size about $x^{1/3}, x^{2/3}$ respectively, then the product $pq$ is $x^{1/3+\varepsilon}$ -densely divisible, but not doubly $x^{1/3+\varepsilon}$ -densely divisible.

In https://terrytao.wordpress.com/2013/06/18/a-truncated-elementary-selberg-sieve-of-pintz/ it was shown that if $\delta \leq \delta'$ and $n$ was a squarefree $x^{\delta'}$ -smooth number with

$\prod_{p|n: p < x^\delta} p > x^{\delta'-\delta}$

then $n$ was $x^\delta$ -densely divisible. Indeed, to get a prime factor of $n$ in the interval $[x^{-\delta} R, R]$ one multiplies together all the big ( $\geq x^\delta$ ) factors of $n$ together until just before one exceeds $R$ (or one runs out of big factors), and then multiplies together small factors until one enters the interval $[x^{-\delta} R, R]$ .

An iteration of this argument shows that if we instead assume the stronger condition

$\prod_{p|n: p < x^\delta} p > x^{2(\delta'-\delta)}$

then $n$ is doubly $x^\delta$ -densely divisible. Indeed if one runs the previous argument to find a factor $d$ of $n$ in $[x^{-\delta} R, R]$ , one will find that there are still enough small prime factors left over in $n/d$ to make $n/d$ $x^\delta$ -densely divisible by the previous argument (indeed, $n/d$ will either be $x^\delta$ -smooth, or else be such that $\prod_{p|n/d: p < x^\delta} p > x^{\delta'-\delta}$ . Replacing $R$ with $n/R$ and $d$ with $n/d$ we then obtain the claim.

Let $MPZ''[\varpi,\delta]$ be the same conjecture as $MPZ'[\varpi,\delta]$ defined in Conjecture 2 of https://terrytao.wordpress.com/2013/06/18/a-truncated-elementary-selberg-sieve-of-pintz/ , but with dense divisibility replaced by double dense divisibility. We can then repeat the proof of Theorem 5 of that post with only minor changes and obtain that $MPZ''[\varpi,\delta]$ implies $DHL[k_0,2]$ assuming the hypotheses stated in that theorem are obeyed, except that the quantity $(\delta'-\delta)/2$ in the definition of $\tilde \theta$ is replaced instead with $\delta'-\delta$ . (Amusingly, this cancels out an improvement of Gergely Harcos made in the comments to that post in which he had inserted the factor of $1/2$ in the theorem.) Thus the Maple verification code for double dense divisibility now takes the following form:

k0 := [INSERT VALUE HERE]; varpi := [INSERT VALUE HERE]; delta := [INSERT VALUE HERE]; deltap := [INSERT VALUE HERE]; A := [INSERT VALUE HERE]; theta := deltap / (1/4 + varpi); thetat := ((deltap - delta) + varpi) / (1/4 + varpi); deltat := delta / (1/4 + varpi); j := BesselJZeros(k0-2,1); eps := 1 - j^2 / (k0 * (k0-1) * (1+4*varpi)); kappa1 := int( (1-t)^((k0-1)/2)/t, t = theta..1, numeric); kappa2 := (k0-1) * int( (1-t)^(k0-1)/t, t=theta..1, numeric); alpha := j^2 / (4 * (k0-1)); e := exp( A + (k0-1) * int( exp(-(A+2*alpha)*t)/t, t=deltat..theta, numeric ) ); gd := (j^2/2) * BesselJ(k0-3,j)^2; tn := sqrt(thetat)*j; gn := (tn^2/2) * (BesselJ(k0-2,tn)^2 - BesselJ(k0-3,tn)*BesselJ(k0-1,tn)); kappa3 := (gn/gd) * e; eps2 := 2*(kappa1+kappa2+kappa3); # we win if eps2 < eps

Next, I claim that the MPZ estimate established in the previous comment https://terrytao.wordpress.com/2013/06/30/bounded-gaps-between-primes-polymath8-a-progress-report/#comment-237087 for $\frac{280}{3} \varpi + \frac{80}{3} \delta < 1$ under the assumption of $x^\delta$ -smoothness of the original moduli, also works under the weaker hypothesis of double $x^\delta$ -dense divisibility. This was already known for the Type II and Type III estimates (which only need single dense divisibility) so it's just a matter of checking that things are OK for the Type I estimate. But by construction, the quantities $q_1 r, q_2 r$ in the Type I argument are doubly $x^\delta$ -divisible, so one can arrange matters so that $q_1,q_2$ are singly $x^\delta$ -divisible while still staying in the same intervals as before. (There is also the point that one has to remove all the tiny prime factors of $q_1,q_2$ , which can affect dense divisibility slightly, but the net effect here is $x^{o(1)}$ and can be neglected.) Thus we can obtain the factorisation $q_2 = s_2 t_2$ needed in the above comment without difficulty.

So, one just has to optimise for $k_0$ in the above code subject to the condition $\frac{280}{3} \varpi + \frac{80}{3} \delta < 1$ , which should bring us very close to xfxie's calculation of 720 or so.

3 July, 2013 at 9:07 am

Gergely Harcos

Very interesting! For clarity I would change “make $n/d$ $x^\delta$ -densely divisible” to “ensure that $n/d$ is $x^\delta$ -densely divisible, namely either $n/d$ is $x^\delta$ -smooth or its $x^\delta$ -smooth part exceeds $x^{\delta'-\delta}$ “. I know you are very busy, but it would be nice and useful to have an updated version of the earlier treatment (https://terrytao.wordpress.com/2013/06/23/the-distribution-of-primes-in-densely-divisible-moduli/), because all the improvements are now scattered in the comments. Perhaps it could be a post entitled “The distribution of primes in doubly densely divisible moduli”?

[Corrected, thanks. I’ll probably write up a post of this sort this weekend. -T]

3 July, 2013 at 9:14 am

xfxie

Great. Seems it is possible to get $k_0=722$ under the new condition. Here is the maple code for validation:

http://www.cs.cmu.edu/~xfxie/sol_722.mpl

Hopefully this time the solution is correct :).

3 July, 2013 at 9:28 am

xfxie

Seems I was too rush again, $k_0$ can be 721:

http://www.cs.cmu.edu/~xfxie/sol_721.mpl

Actually, I am using TeamView in my android phone to connect to my macbook. Somebody might try to further improve the result using the code:

http://www.cs.cmu.edu/~xfxie/project/admissible/k0table.html

Just notice there is a slight change in the maple code ( (deltap – delta) instead of (deltap – delta)/2 for thetat), as mentioned by Terence above.

3 July, 2013 at 10:07 am

xfxie

Further search returned the same 720:

http://www.cs.cmu.edu/~xfxie/sol_720.mpl

3 July, 2013 at 10:42 am

xfxie

Before the termination condition satisfied, a new solution k0=719 was found.

http://www.cs.cmu.edu/~xfxie/sol_719.mpl

3 July, 2013 at 10:49 am

xfxie

Sorry, the result 719 is wrong, after I managed to remotely validate using maple.

3 July, 2013 at 11:30 am

xfxie

Just found the reason. As I tried to verify the correctness of the solution $k_0=720$ using maple, its output (a negative value for eps2 – eps) overwrote the file that the search algorithm was using, and thus fooled the algorithm.

4 July, 2013 at 11:40 pm

Gergely Harcos

I confirmed this value below (with slightly cleaner and more optimal parameters). So it seems that we have prime gaps of size at most 5414 infinitely often.

3 July, 2013 at 11:58 am

Eytan Paldi

Is the coefficient $2$ in the exponent $2 (\delta' - \delta)$ the minimal one required to get $n$ doubly $x^{\delta}$ – densely divisible?

3 July, 2013 at 10:07 am

Richard Elwes – Carnival of Mathematics 100

[…] • Let’s start with the biggest mathematical news story at the moment. Back in May, Yitang Zhang announced a proof of the following great breakthrough: there are infinitely many pairs of primes which are at most 70,000,000 (= H) apart. Terry Tao reports on subsequent huge success: […]

3 July, 2013 at 7:11 pm

Daniel Reem

Following the “high level” spirit of this post, I wonder whether some geometric arguments can be used in order to improve the analysis (and in particular, some parameters). Let me give a more concrete example. It can be seen that the Cauchy-Schwarz inequality appears over and over again
in the analysis. However, it is used as it is, in an “analytic manner”, without any attempt to try to use its full power by estimating the angle between the involved vectors. Doing so may indeed be a non-trivial task, but if one can somehow show (at least in certain cases) that the vectors are close to be orthogonal, or at least the angle between them is bounded away from 0 and pi, then this is expected to improve the outcome.

P.S. It is very interesting to see how much progress has been made in a so short period.

4 July, 2013 at 11:36 pm

Gergely Harcos

Just a confirmation that xfxie’s $k_0=720$ seems correct, and this yields prime gaps of size $H=5414$ (cf. http://math.mit.edu/~primegaps/tuples/admissible_720_5414.txt). Using $\varpi=3/280-1/62000$ , $\delta=(3-280\varpi)/80$ , $\delta'=1/100$ , $A=252$ , I am getting $\epsilon\approx 1.24\times 10^{-6}$ , $2\kappa_1\approx 1.02\times 10^{-7}$ , $2\kappa_2\approx 2.96\times 10^{-11}$ , $2\kappa_3\approx 7.33\times 10^{-9}$ .

5 July, 2013 at 4:51 pm

Pace Nielsen

Just a comment about the combinatorics part of the program.

The Type III sums take advantage of the case where there are three somewhat large scale, smooth functions, at the cost of working with bounds on $K_3$ . We can, instead break things into cases as follows:

Let $\psi_P$ be the largest smooth function in the Heath-Brown decomposition, with scale $1\ll P\ll x$ . (Perhaps this can be chosen in the Linnik decomposition, if done correctly.) Write $P = x^{t}$ . If we have $t\geq 1/2+2\varpi$ we are in Type 0. If $1/2-2\varpi \leq t \leq 1/2+2\varpi$ we are in Type II, but with one of the components smooth (which we won’t use). If $2\sigma \leq t \leq 1/2-2\varpi$ , then we are in Type I, but with the smallest component smooth. Finally, if $t\leq 2\sigma$ we are in Type I/II.

On the positive side, in this new breakdown $\sigma$ can be arbitrarily small. On the negative side, we are ignoring some extra information (which allows for the creation of the Type III sums). On the positive side again, these new sums are much easier to compute.

Thus, we still do the Type 0,I,II computations, but also do a Type I computation with $\beta$ smooth and $x^{2\sigma}\ll N$ (let’s call this new sum, Type IV for now). If I computed correctly, the improved bound from the (first) Type I computations, modified to Type IV, yields the bound $4\varpi +\frac{1}{2}\mu+\frac{1}{2}\delta < \sigma$ . This seems like a much better border than between Type I and Type III.

(Note: This inequality was worked on scratch paper, fairly quickly. Others may want to rework it, to double check that the Type I/IV border is better than the Type I/III border.)

5 July, 2013 at 5:34 pm

Pace Nielsen

If the work above holds, we get the new inequality (which barely misses the Type II bound):

$76\varpi + 16\delta < 1$ .

The work above followed the Type I level 1 computations, but without the last use of Cauchy-Schwarz, and thus needing only to bound $|\sum_{n}\psi_N(n)\Phi(h,q_1,q_2;n)|$ .

5 July, 2013 at 6:39 pm

Gergely Harcos

You say: if $2\sigma \leq t \leq 1/2-2\varpi$ , then we are in Type I, but with the smallest component smooth. I don’t see this. For example, there can be several tiny $t$ ‘s which correspond to Möbius convolution factors restricted to small dyadic intervals. Also, Zhang’s argument (and the one presented here) is based on grouping together certain convolution factors in order to create arithmetic functions with fairly large supports and possibly with the requirement of smoothness as well. I don’t see how to achieve that with your classification based on a single $t$ only. If you have a new way to treat the whole problem (new types of sums, and new estimates for them), then provide all the details so that we can verify them.

5 July, 2013 at 6:48 pm

Pace Nielsen

To clarify, if $2\sigma\leq t\leq 1/2-2\varpi$ , we are in Type I only in the sense that we are looking at a sum with two convolved sequences $\alpha,\beta$ (where $\beta$ is the single smooth component corresponding to $t$ , and $\alpha$ is the convolution of the rest of the components). But we are *not* in Type I in the sense that the sequences have scale $x^{1/2+\sigma},x^{1/2-\sigma}$ . Rather, the scales are (at worst) $M=x^{1-2\sigma}, N=x^{2\sigma}$ . That’s why I called it Type IV.

So, we are still grouping things together. We just leave the biggest smooth piece alone. The tiny $t$ ‘s, which are not smooth, all get sucked into the $\alpha$ . I hope this clarifies things.

5 July, 2013 at 7:03 pm

Gergely Harcos

Let us focus on the ranges $M=x^{1-2\sigma}$ and $N=x^{2\sigma}$ , and let $\beta$ be smooth. How do you prove (42) from the earlier thread (https://terrytao.wordpress.com/2013/06/23/the-distribution-of-primes-in-densely-divisible-moduli/)?

5 July, 2013 at 7:44 pm

Pace Nielsen

I was following the ideas from the even earlier thread (https://terrytao.wordpress.com/2013/06/12/estimation-of-the-type-i-and-type-ii-sums/). First, we replace $\beta(n)\beta(n+kr)$ by $\psi_{N}(n)$ (a smooth function). We combine the two exponential terms $e_{r}(\frac{a_r h}{nq_1 q_2})$ and $e_{q_1}(\frac{b_{q_1}h}{nrq_2})$ into a single exponential. Then we use Corollary 10 from that thread, and bound things just as is done there (but since we never had to do the squaring, from the Cauchy-Schwarz, things work out a bit better).

So, if I did things right, I get

$|\sum_ n \psi_{N}(n)\Phi(h,q_1,q_2;n)| \ll x^{o(1)}(QR^{1/2}+NHR^{-1})|$

by using Corollary 10. Here, we have $d_1:=rq_2$ and $d_2:=q_2$ . So $(d_1,d_2)=1$ . We again bound $(c_2,d_2)$ by $d_2$ , and $(c_1,q_1)$ by $(c_1,r)q_1$ . However, here $(c_1,r)=(h,r)$ can be approximated by $H$ rather than $HQ$ .

———————-

To establish the needed bound, we now need to establish two inequalities. The first is

$HQ^3 R^{1/2} \ll x^{-2\epsilon+o(1)}Q^{2}N$ .

Recalling that $H=x^{\epsilon}Q^2 R/M$ , ignoring $\epsilon$ s, we plug in and find that we need (contrary to my earlier computation, by the way, I accidentally dropped one power of $Q$ ):

$(QR)^{3} \ll x(R/N)^{3/2}N^{3/2}$ .

This leads to

$\frac{3}{2}+6\varpi \leq 1-\frac{3}{2}\mu-\frac{3}{2}\delta+\frac{3}{2}(2\sigma)$

which simplifies to

$\frac{1}{6}+2\varpi + \frac{1}{2}\mu+\frac{1}{2}\delta \leq \sigma$ .

So, unfortunately, we have $\sigma \geq 1/6$ here. However, there is some hope that this inequality can be improved as we apply the improvements obtained in the Type I case.

Sorry for dropping that extra $Q$ , and thanks for making me double check everything.

5 July, 2013 at 8:05 pm

Gergely Harcos

I think this is an interesting direction that merits attention.

5 July, 2013 at 7:11 pm

Gergely Harcos

You also say: if $t\leq 2\sigma$ we are in Type I/II. Why is that?

5 July, 2013 at 7:31 pm

Pace Nielsen

I’m typing up my answer to your question above, but I can answer this one easily.

If all $t$ ‘s are $\leq 2\sigma$ , then a greedy algorithm allows us to get into the Type I/II situation. (It is the same argument used in the original combinatorics.) We don’t leave the biggest $t$ alone in this case, but force $\alpha,\beta$ to have scales as close as possible (and neither are smooth anymore).

5 July, 2013 at 8:01 pm

Gergely Harcos

The assumption $t\leq 2\sigma$ is initially made for the smooth convolution factors only, so I guess you are implicitly assuming that the rest of the $t$ ‘s are automatically at most $2\sigma$ . This can be achieved, but it requires (e.g. when working with the Heath-Brown decomposition) that $\sigma$ remains above $1/K$ . Here $K$ is as in https://terrytao.wordpress.com/2013/06/10/a-combinatorial-subset-sum-problem-associated-with-bounded-prime-gaps/. I need to leave the computer now, but it would be nice to get an improved and simplified argument along these lines.

5 July, 2013 at 8:07 pm

Pace Nielsen

You can choose $K$ as large as you like, so this issue causes no problems. But yes you understood correctly.

5 July, 2013 at 8:18 pm

Pace Nielsen

I guess to improve and simplify the argument, we would simply say: Let $\psi$ be the sequence in the Heath-Brown decomposition, where if we write the scale as $x^{t}$ , then $t$ is the largest real number that occurs. Letting $K$ be big enough, we only assume smoothness for $\psi$ when $t\geq 2\sigma$ (for $\sigma$ [and hence $K$ ] to be optimized later, using inequalities involving only fixed objects).

6 July, 2013 at 8:53 am

Improved bounds on Prime number gaps | On the learning curve...

[…] and his team steadily managed to improve the bound. Tao has already knitted a nice and detailed summary on the progress. As of last week, the proven gap was , but now the updated gap could be as small as (which is […]

6 July, 2013 at 9:41 am

Pace Nielsen

Just for fun, I plugged in what would happen in the Type I-Level 6 computations if we used the worse case bounds

$N\approx x^{2\sigma},\ R\approx x^{2\sigma-\delta},\ Q\approx x^{2\varpi +\frac{1}{2}-2\sigma+\delta}$

which are what arise when trying to do the new Type IV computations with scales $M,N$ nearly $x^{1-2\sigma},x^{2\sigma}$ .

In this case, we obtain the inequality

$\frac{1}{8} + 7\varpi + 2\delta<\sigma$ .

Note that this is obtained by following the Type I-Level 6 ideas in the new Type IV situation, *without* taking advantage of the fact that $\beta$ is smooth. So there has to be some room for improvement here, but it would have to be in the constant $\frac{1}{8}$ to improve the current record.

7 July, 2013 at 11:59 am

Parents of Invention | DeepWeave

[…] find shorter and more elegant ways to achieve it. As of June 30, a collaborative project hosted by Terence Tao had pushed H down to 12,006 and provisionally as low as 6,996. They already know that the path […]

7 July, 2013 at 11:17 pm

The distribution of primes in doubly densely divisible moduli | What's new

[…] with respect to the parameter (which, using this constraint, gives a value of as verified in comments, which then implies a value of […]

7 July, 2013 at 11:25 pm

Terence Tao

New thread is up: https://terrytao.wordpress.com/2013/07/07/the-distribution-of-primes-in-doubly-densely-divisible-moduli/

As requested, the latest Type I, II, and III arguments are presented. The Type III arguments turned out to have a few technical twists that were not anticipated in the previous writeups, but fortunately this only affected some lower order terms and the numerology is still basically unchanged. In any case the Type III estimates are currently quite far from being the critical obstacle towards further improvements of the estimates. (I would still recommend the sketchier arguments given in this current post than the more detailed arguments in the most recent post if one just wants to get a sense of how the arguments work, and to play with the numerology.)

8 July, 2013 at 4:31 am

Gergely Harcos

Thank you! I will study it in the coming days.

9 July, 2013 at 11:23 am

The p-group fixed point theorem | Annoying Precision

[…] theorem on bounded gaps between primes (although my understanding is that this step is unnecessary just to establish the […]

10 July, 2013 at 6:28 pm

Gergely Harcos

Some typos:

1. “an interval $[-p_{m+\lfloor k_0-2/2\rfloor}, \ldots, -p_{m+1},-1,+1,p_{m+1},\ldots,p_{m+\lfloor k_0-1/2 \rfloor}]$ ” should be “an interval $[-p_{m+\lfloor k_0-2/2\rfloor}, \ldots, p_{m+\lfloor k_0-1/2 \rfloor}]$ “.

2. “optimised in later” should be “optimised later”.

3. In the two displays following “the numerator becomes”, the weight $\lambda_{d_1}\lambda_{d_2}$ is missing, but perhaps intentionally for the sake of exposition?

4. “Polyá-Vinogradov” should be “Pólya-Vinogradov”.

5. In the display following “expression can be rearranged as”, the condition $mn=a_{q_1}\ (q)$ should be $mn=a_{q_1}\ (q_1)$ .

[Corrected, thanks – T.]

11 July, 2013 at 4:35 am

Batch Auctions, US/EU Swap Reg Deal, and Primal Madness « Pink Iguana

[…] Internet race in a project called Polymath8. A recent e-mail from Tao announced the latest result: a gap of no more than 12,006 numbers between primes, and a provisional gap of only 6,966—conditi…. The details are in the link […]

11 July, 2013 at 11:59 am

Martin Maulhardt

Dear Mr Tao,
I’ve followed and admired your work for a long time and I’m pleased that you mentioned this subject on Zhang’s theorem.
In connection with this theorem on the difference between two consecutive prime numbers, I wanted to share with you a result I proved recently: “There are infinitely many terns of consecutive primes such that the difference between the two second ones is smaller or equal than the difference between the first two ones.” For example (7,11,13).
I’d be honored if you want to read more on my paper that I posted on my website (http://martinmaulhardt.com/?page_id=6).

11 July, 2013 at 1:59 pm

Gergely Harcos

Your result follows from Zhang’s theorem: if $d_n:=p_{n+1}-p_n$ is the difference between the $n$ -th prime and the next one, then for any $N>0$ the assumption that $d_n$ is increasing for $n>N$ would imply that $d_n$ tends to infinity (because they tend to infinity on average), contrary to Zhang’s theorem. In fact Erdős and Turán proved already in 1948 that $d_{n+1}-d_n$ changes sign infinitely often (see (7) here: http://www.ams.org/journals/bull/1948-54-04/S0002-9904-1948-09010-3/S0002-9904-1948-09010-3.pdf).

11 July, 2013 at 9:31 pm

Martin Maulhardt

Dear Gergely,
Thanks for your valuable post and I have to admit that I was not aware of the result of Erdos and Turan. So my result is not new as I first thought. But revising the proof that these great mathematicians had constructed I have to say that mine is completely different and simpler.
Of course I have not the slightest pretension to compare myself with either of these great mathematicians by saying that my proof is simpler and different.

12 July, 2013 at 7:58 am

Terence Tao

A survey of the known results about the difference $d_n$ between consecutive primes can be found in this recent article of Pintz http://arxiv.org/abs/1305.6289 (see in particular Section 2.4).

12 July, 2013 at 8:31 am

Martin Maulhardt

Thanks very much!

2 September, 2013 at 2:32 pm

Polymath8: Writing the paper, II | What's new

[…] (For a discussion of the terminology, and for a general overview of the proof strategy, see this previous progress report on the Polymath8 project.) This post can also contain any other discussion pertinent to any […]

20 February, 2014 at 6:54 am

zeggari

i am not a matimatician expert but i have some ideas:
let S the count of the digit of a number. EX S(99)=S(18)=S(9)=9.
S(i) must be between [2;9], i>1.
to verify if two number’s are not twin:
“IF S(p)*S(p+2) different to 8 then p and p+2 are not twin prime numbers”
note that
1)S(p+i)=S(S(p)+i)
2)S(i)*S(j)=S(i*j)
EX:
S(111413131313131343534231331663534342442442442355343434351141879678685757575756464545353422211109)=6 and S(111413131313131343534231331663534342442442442355343434351141879678685757575756464545353422211111)=6+2
S(6*8)=S(48)=S(12)=S(3)=3 fifferent to 8 . this two numbers are not twin prime numbers (vérified by hand on less then 3 minutes).

20 February, 2014 at 7:04 am

zeggari

Problem of over bound of the web page
this is a new exemple beacouse i loste the first number
EX:
S(111413131313131343534231331663534342442442442355343434 351141)=7 and S(111413131313131343534231331663534342442442442355343434 351143)=7+2
S(7*9)=S(63)=S(9)=9 . this two numbers are not twin prime numbers

20 February, 2014 at 12:09 pm

zeggari

sorry, i think that this means simply if we look to test p1 and p2 if they are not twin prime numbers you must devide first p1/3 then p2/3 and so on.

26 December, 2014 at 12:23 am

王晓明

There are infinitely many primes P and P + 2 is a prime number
The twin prime formula Using the criterion of prime numbers, we can get the following conclusions:

“if the natural numbers q and q+2 cannot be any less than\sqrt{q+2} prime divisibility, then q and q+2 is prime.。
This is because a natural numbern is prime if and only if it can’t be any less than other prime divisibility on\sqrt{n} .
Using mathematical language expresses the conclusions above, is:
There is a group of natural numberb_{1}, b_{2} \cdot , b_{k} making

q=p_{1}m_{1}+b_{1}=p_{2}m_{2}+b_{2}=\dots=p_{k}m_{k}+b_{k} \qquad \qquad \qquad \cdots \qquad (1)

Thep_{1},p_{2},\dots,p_{k} from small to large order during the first k prime numbers: 2, 3, 5,…. And meet。

\forall 1 \le i \le k, \ \ 0 < b_{i} < p_{i}, \ b_{i} \neq 0, \ b_{i} \neq p_{i} – 2.
Natural number q so obtained if meet the q<p^{2}_{K+1}-2，qandq+2 ，

are a pair of twin primes. We can think of (1) equivalence of content type conversion become congruence equations。

q \equiv b_1 \pmod{p_1}, q \equiv b_2 \pmod{p_2}, \dots, q \equiv b_k \pmod{p_k} \qquad \qquad \qquad \cdots \qquad (2)
Because of (2).p_{1},p_{2},…,p_{k} are all prime numbers, so two two coprime,based on the Chinese Remainder Theorem (China remainder theorem), for a givenb_{1}, b_{2} \cdot , b_{k}, (2) is only a less than positive integerp_{1} p_{2} \cdots p_{k} solution。.

Example
For example, k=1,q=2m_{1}+1，solutionq=3, 5 。 Since5<3^2-2 ，

so that 3 and3+2 ；5 and5+2 are the twin prime. Thus the interval(3, 3^2) in the
whole of prime twins.。
For instance

k=2, equation of q=2m_{1}+1=3m_{2}+2， solutionq=5, 11, 17。Since17<5^2-2，
so the11 with11+2 ；17 and 17+2 are the twin primes.
Because this isall possible b_{1}, b_{2} \cdot , b_{k} value, so the interval (5, 5^2) are of prime twins.。
k=3 5m_{3}+1 5m_{3}+2 5m_{3}+4
q=2m_{1}+1=3m_{2}+2= 11,41 17 29
Because this is all possibleb_{1}, b_{2} \cdot , b_{k} value, so the interva(7, 7^2)are of prime twins。

k=4 7m_{4}+1 7m_{4}+2 7m_{4}+3 7m_{4}+4 7m_{4}+6
q=2m_{1}+1=3m_{2}+2=5m_{3}+1= 71 191 101 11 41
q=2m_{1}+1=3m_{2}+2=5m_{3}+2= 197 107 17 137 167
q=2m_{1}+1=3m_{2}+2=5m_{3}+4= 29 149 59 179 209
　　 Because this is all possibleb_{1}, b_{2} \cdot , b_{k} value, so the interva(11, 11^2)are of prime twins。　8 less than the 121-2 of the solution。　

　　　　Copy this to be a not leak to find all the prime twins within an arbitrary largenumber of. For all the possibleb_{1}}, b_{2} … , b_{k} value, (1) and (2) in the（p_{1}）（p_{2}）(p_{3})…（p_{k}）range,， with（p_{1}-1）（p_{2}-2）(p_{3}-2)…（p_{k}-2）…..（3）solution。

Conclusion
The twin prime conjecture is (1) and (2) type, value arbitrarily large when a q<p^{2}_{K+1}-2 solution in K.

	Dan Asimov on Inequalities, convergence, and…
	Dan Asimov on Inequalities, convergence, and…
	Anonymous on AI to Assist Mathematical Reas…
	Terence Tao on AI to Assist Mathematical Reas…
	Mathur Maynard Amadi on Inequalities, convergence, and…
	Alex Kontorovich on Inequalities, convergence, and…
	Gabe Khan on Inequalities, convergence, and…
	"不等式、收敛与连续性作为“特… on Inequalities, convergence, and…
	Some interesting thi… on PCAST Working Group on Generat…
	jack morava on Inequalities, convergence, and…
	Wednesday assorted l… on Inequalities, convergence, and…
	Wednesday assorted l… on Inequalities, convergence, and…
	Wednesday assorted l… on Inequalities, convergence, and…
	Mark Lewko on Inequalities, convergence, and…
	Wednesday assorted l… on Inequalities, convergence, and…

Bounded gaps between primes (Polymath8) – a progress report

Recent Comments

Articles by others

Diversions

Mathematics

Selected articles

Software

The sciences

Top Posts

Archives

Categories

The Polymath Blog

86 comments

Leave a Reply Cancel reply

For commenters

Bounded gaps between primes (Polymath8) – a progress report

Share this:

Like this:

Recent Comments

Articles by others

Diversions

Mathematics

Selected articles

Software

The sciences

Top Posts

Archives

Categories

The Polymath Blog

86 comments

Leave a Reply Cancel reply

For commenters