As in previous posts, we use the following asymptotic notation: is a parameter going off to infinity, and all quantities may depend on unless explicitly declared to be “fixed”. The asymptotic notation is then defined relative to this parameter. A quantity is said to be *of polynomial size* if one has , and said to be *bounded* if . Another convenient notation: we write for . Thus for instance the divisor bound asserts that if has polynomial size, then the number of divisors of is .

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

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

where is a primitive Dirichlet character of some conductor , is an integer, and is some quantity between and . Clearly we have the trivial bound

we also have the classical Pólya-Vinogradov inequality

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

for any , where . (In fact, from the classical theory of Gauss sums, this exponential sum is equal to for some complex number of norm .)

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

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

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

for any fixed integer , assuming that is square-free (for simplicity) and of polynomial size; see this previous post for a discussion of the Burgess argument. This is non-trivial for as small as .

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

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

Proposition 1Let be square-free with a factorisation and of polynomial size, and let be integers with . Then for any primitive character with conductor , one has

This proposition is particularly powerful when is smooth, as this gives many factorisations with the ability to specify with a fair amount of accuracy. For instance, if is -smooth (i.e. all prime factors are at most ), then by the greedy algorithm one can find a divisor of with ; if we set , then , and the above proposition then gives

which can improve upon the Burgess bound when is small. For instance, if , then this bound becomes ; in contrast the Burgess bound only gives for this value of (using the optimal choice for ), which is inferior for .

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

*Proof:* If then the claim follows from the trivial bound (1), while for the claim follows from (2). Hence we may assume that

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

Let , thus . For any , we have

By the Chinese remainder theorem, we may factor

where are primitive characters of conductor respectively. As is periodic of period , we thus have

and so we can take out of the inner summation of the right-hand side of (4) to obtain

and hence by the triangle inequality

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

Note that the inner sum vanishes unless , which is an interval of length by choice of . Thus by Cauchy-Schwarz one has

We expand the right-hand side as

We first consider the diagonal contribution . In this case we use the trivial bound for the inner summation, and we soon see that the total contribution here is .

Now we consider the off-diagonal case; by symmetry we can take . Then the indicator functions restrict to the interval . On the other hand, as a consequence of the Weil conjectures for curves one can show that

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

Summing in (using Lemma 5 from this previous post) we see that the total contribution to the off-diagonal case is

which simplifies to . The claim follows.

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

where should be thought of as a little bit larger than .

It will be convenient to introduce a little bit of formal algebraic notation. For the narrow task of establishing a new estimate on an incomplete Kloosterman-type sum of the type used in Zhang’s paper, one does not really need all this formalism, but it may be useful to have this formalism around for future generalisations and strengthenings of this estimate (e.g. when trying to set up a Burgess-style argument).

Define an *integral rational function* to be a formal rational function in a formal indeterminate where are polynomials with integer coefficients, and is monic; in particular any polynomial can be identified with the integral rational function . For minor technical reasons we do *not* equate integral rational functions under cancelling, thus for instance we consider to be distinct from ; we need to do this because the domain of definition of these two functions is a little different (the former is not defined when , but the latter can still be defined here). Because we refuse to cancel, we have to be a little careful how we define algebraic operations: specifically, we define

Note that the denominator always remains monic with respect to these operations. This is not quite a ring with a derivation (the subtraction operation does not quite cancel the addition operation due to the inability to cancel) but this will not bother us in practice. (On the other hand, addition and multiplication remain associative, and the latter continues to distribute over the former, and differentiation obeys the usual sum and product rules.)

In applications to bounded gaps between primes, we will deal with integral rational functions of the explicit form

for various integers , but much of the theory below extends without much difficulty to more general integral rational functions, so we shall state it in that level of generality.

Note that if is an integral rational function, we can localise it modulo for any modulus to obtain a rational function that is the ratio of two polynomials in , with the denominator monic and hence non-vanishing. We can define the algebraic operations of addition, subtraction, multiplication, and differentiation on integral rational functions modulo by the same formulae as above, and we observe that these operations are completely compatible with their counterparts over (even without the ability to cancel), thus for instance . We say that is *divisible* by , and write , if the numerator of has all coefficients divisible by .

If is an integral rational function and , then is well defined as an element of except when is a zero divisor in . We adopt the convention that when is a zero divisor in , thus is really shorthand for ; by abuse of notation we view both as a function on and as a -periodic function on . Thus for instance

Note that if , then for all for which is well defined. We define to be the largest factor of for which ; in particular, if is square-free, we have

We recall the following Chinese remainder theorem:

Lemma 2 (Chinese remainder theorem)Let with coprime positive integers. If is a rational function, thenfor all integers , where is the inverse of in and similarly for .

When there is no chance of confusion we will write for (though note that does not qualify as an integral rational function since the constant is not monic).

*Proof:* See Lemma 7 of this previous post.

We need the following algebraic version of the fundamental theorem of calculus:

Lemma 3 (Fundamental theorem of calculus)Let be a rational function, and let be a positive integer. If and all prime factors of are sufficiently large depending on the degrees of , then there exists such that .

*Proof:* By definition, the constraint may be rewritten as

By abuse of notation, we view as polynomials over (i.e. all occurrences of in what follows should actually be if we did not abuse notation). If has degree larger than , then by inspecting the coefficient of this equation we obtain a contradiction if all prime factors of are large enough. Thus we may assume that ; since is monic, this implies that for some with . We can then rewrite the previous constraint as

If is non-zero, then inspecting the coefficient of this equation leads to a contradiction if all prime factors of are large enough. Thus is zero, and so as required.

Now we give an estimate for complete exponential sums, which combines both Ramanujan sum bounds with Weil conjecture bounds.

Proposition 4 (Ramanujan-Weil bounds)Let be a positive square-free integer of polynomial size, and let be an integral rational function with of bounded degree. Then we have

For instance, if we set for some integer , we obtain the familiar Ramanujan sum bound

More generally, if we set for some integers , we obtain Weil’s Kloosterman sum bound

and so forth.

The bound in Proposition 4 is quite sharp, with one exception of relevance to the polymath8 project, namely the estimation of the degenerate Kloosterman-type sum

with integers. Proposition 4 gives a bound of in this case, but one can do better by performing the change of variables that transforms this sum into a Ramanujan sum, yielding the superior bound

One could try to modify the argument below to incorporate this improvement, but it leads to a significantly more complicated right-hand side for the estimate, so we will not do so here.

*Proof:* By the Chinese remainder theorem and the divisor bound, it suffices to verify this when is a single prime and with replaced by , thus we wish to show that

otherwise. We may assume that is sufficiently large depending on the degrees of as the claim is trivial otherwise.

The first bound trivially follows from the triangle inequality, so we turn to the second bound. Since , we conclude from Lemma 3 that there is such that ; since , must be non-zero. Since , another application of Lemma 3 shows that there is such that . Thus whenever is well-defined. Since the denominator of has only bounded number of zeroes, we conclude that for all but a bounded number of . The claim then follows (7) from the Fourier identity

Now we prove (8). By abuse of notation, we view and as polynomials over the field rather than over the integers. Let be the (monic) greatest common divisor, thus and with coprime and of bounded degree with monic. As in the previous paragraph, we have for all but a bounded number of . So it suffices to show that

We now use the Weil bound for exponentials of rational functions over a field of prime order, as stated for instance in this paper of Perelmuter or this paper of Cochrane and Pinner (in the case when is polynomial, one can also use the original paper of Weil, who also treats the important case of Kloosterman sums when is a fractional linear transformation). We remark that the Cochrane-Pinner paper uses Stepanov’s method and is thus essentially elementary in nature, whereas the other papers use more sophisticated tools from arithmetic geometry (such as -adic cohomology). In any event, the results in these papers give the required bound except when the rational function has the form

in the field of rational functions over for some and . (The presence of the factor arises because of elements of are all roots of .)

Suppose that (9) holds. Writing for some coprime polynomials with monic, we conclude on multiplying everything out that

in the polynomial ring . By unique factorisation, this forces to divide , which for large enough forces to have degree zero, thus as is monic. We thus have

Inspecting the coefficient of this equation, we obtain (for large enough) a contradiction unless has degree zero, thus is constant. In particular and so is a scalar multiple of , hence is a scalar multiple of and so , contradicting the hypothesis. This covers all cases and we are done.

Now we obtain a bound for incomplete exponential sums to smooth moduli. We will focus attention here on the specific sum we need to bound for the Polymath8 project, namely a sum of the form

where are square-free numbers (not necessarily coprime), are integers, , and is a function supported on an interval of length that obeys the smoothness bounds

for any fixed . The arguments below also apply to more general exponential sums as these, but the specific sum benefits from the additional cancellation (6) that is not available for more general sums.

Proposition 5Let be as above. Write and .

The estimate (ii) is a slightly improved version of Lemma 11 of Zhang’s paper (which is a key estimate to treat the Type I/II sums); one can also write the second term on the right-hand side more suggestively as . But it is the estimate (iii) which is a more substantial improvement, as for the medium-sized values of that come up in Zhang’s argument, the first two terms that appear in (12) are superior to the main term in (11). (Admittedly, the final term in (12) is worse than the final term in (11), but in practice these terms are not dominant.) The improved bound (12) leads to significantly better values of and for the assertion that we need for bounded gaps between primes; this is sketched in this previous comment and will be detailed in a subsequent post.

*Proof:* The trivial bound (10) is immediate from the triangle inequality and the bounds and support of , so we turn now to the standard bound (11). We can write

where and is the integral rational function

By Fourier inversion and the -periodicity of , one can rewrite as

From the Poisson summation formula and integration by parts, we have the standard bounds

for all (which, by abuse of notation, we identify with ) and any fixed .

Consider first the term in (14). By the Chinese remainder theorem, we may factor as

Applying (6) to the first two factors and the trivial bound of to the second factor, we conclude that

and so the contribution of the term is acceptable. It remains to establish that

Let be fixed. For the bound is trivial from (15) (for large enough), so by overspill it will suffice to show that

By Proposition 4 and (15), the left-hand side is

Writing , we may bound the previous expression by

Since

vanishes at infinity, we see that implies . Thus

and hence by the divisor bound

and the claim follows.

Now we prove (12). We first observe that if , then and the claim (12) follows already from the trivial bound (10). Similarly, if , then and also

so (12) follows from (11) in this case. Thus we may restrict attention to the regime

As before, we can rewrite as (14). Now set

so . Shifting by for and averaging, we may then rewrite (14) as

From Lemma 2, we have

and so we may bound by

By Proposition 4 (and the coprimality of ), we have

Thus we may bound the previous expression by

Next, let be a small fixed quantity. By (15) as before, the contribution of those outside of the interval is negligible, so it will suffice to show that

Bounding , we may bound this sum by

The inner sum is only non-vanishing when , and in that case we have a bound of as in the proof of (11); note that

so we may replace by . By the divisor bound we may thus bound (18) by

By Cauchy-Schwarz, we may thus bound the left-hand side of (17) by

We may square out as

Now observe from Fourier analysis that the sum

equals when and , and vanishes otherwise. Thus we may simplify the above expression as

Substituting , this becomes

As is supported in an interval of length , we obtain the bound

We first isolate the diagonal terms . In this case the inner sum is a Ramanujan sum, so by (5) the diagonal contribution is bounded by

Summing in using Lemma 5 from this previous post, this is bounded by

Now we handle the non-diagonal terms . By Proposition 4, this contribution to is

Bounding

we can bound the preceding expression by

The inner sum vanishes unless . In that case, is restricted to a single residue class modulo , and so the inner sum is . From the divisor bound we conclude that

and thus this contribution to is bounded by

From the explicit formula (13) we see that if , then if and only if

For large enough, this only happens if or . We conclude that

and thus this contribution to is

If we estimate

we have

This contribution to is thus

and thus

Inserting this back into (19) gives the desired bound (17). This completes the proof of (12).

## 24 comments

Comments feed for this article

22 June, 2013 at 7:14 pm

v08ltu“(In fact, from the classical theory of Gauss sums, this exponential sum is equal to {\tau(\chi) \chi(a)} for some complex number {\tau(\chi)} of norm one.”

I think has norm . Maybe I do not understand.

[Oops, that was a typo, fixed – T.]23 June, 2013 at 7:16 am

Matt YoungProposition 1 looks to be related to a result of Heath-Brown: Hybrid bounds for Dirichlet L-functions. Invent. Math. 47 (1978), no. 2, 149–170. Specifically, compare with Heath-Brown’s Theorem 2.

23 June, 2013 at 7:34 am

Terence TaoThanks for the reference! I was surprised that I was not able to locate this argument before in the literature, given how simple it was. Indeed Theorem 2 of Heath-Brown is essentially the same result with the same proof (except that he considers the Dirichlet series of a character rather than a character sum). I’ve updated the post to reflect this. I wonder why this trick (with Heath-Brown calls “a q-analogue of van der Corput”) is not used more often in the literature.

23 June, 2013 at 7:59 am

bengreenTerry, one place it is used is in Heath-Brown’s 2009 preprint on cubic weyl sums http://arxiv.org/pdf/0905.1869.pdf

Roger says in that paper that some credit must go to C. Ringrose, whose 1985 PhD thesis (written under Heath-Brown’s supervision) is in fact entitled “The q-analogue of van der Corput’s method”.

23 June, 2013 at 9:13 am

Terence TaoThanks for the reference! I was aware of a paper of Graham and Ringrose on the topic but did not realise until now that this paper is indeed based in part on the earlier paper of Heath-Brown. (The main theorem, Theorem 5, of Graham-Ringrose looked weaker to me than what is in this post or in Heath-Brown, but on closer inspection I now see that the k=0 case of that theorem is basically what is given here (although this was not obvious at a first glance)).

23 June, 2013 at 9:03 am

Gergely HarcosJust a note that might be relevant: recently Djordje Milićević developed a powerful theory of p-adic exponential pairs in his manuscript “Sub-Weyl subconvexity for Dirichlet L-functions to prime power moduli”. A related paper is his joint work with Valentin Blomer, “p-adic analytic twists and strong subconvexity”. These papers are not public yet, but will appear soon (I think). Abstract of a very recent talk by Valentin: http://www.cirm.univ-mrs.fr/RepRenc/746/abstracts746.pdf

23 June, 2013 at 2:46 pm

Terence TaoI’m recording here some minor reductions that make the proof of Proposition 5 marginally simpler, though not by much:

* We can assume that , since otherwise we can cancel the common factor from both and . (Actually one has to dispose of the condition to do this, but this can be done by a routine Mobius inversion argument.) Similarly we may assume that .

* By partitioning the integers into residue classes modulo , and making the change of variables for each such residue class and summing using the triangle inequality, we may reduce to the case when (so that and ).

* Once we have reduced to , we can translate using the Chinese remainder theorem to reduce to the case . The phase then simplifies to a single phase for some coprime to .

When we are working in the case and (which we can essentially reduce to from the above discussion), then Proposition 5(iii) gives

Actually, in view of the above reductions, I think the same argument actually gives

for any other factorisation . Given how smooth (or at least how densely divisible) all the moduli we are working with are, this could lead to some further optimisation of this exponential sum estimate which would lead to further improvement in the Type I/II estimates. But it will lead to some technical complications on the GPY sieving side: we may need to strengthen the notion of “-densely divisible” to something like being “doubly -densely divisible, namely that any modulus can be factored into two factors in specified intervals of multiplicative width , such that each factor is itself -densely divisible. I might experiment with this in a few days to see if it really does give any significant improvement.

23 June, 2013 at 9:01 pm

David RobertsKowalski says that the work in the paper can be done without the Weyl-type shifts, here:

http://blogs.ethz.ch/kowalski/2013/06/22/bounded-gaps-between-primes-the-dawn-of-some-enlightenment/

and that they get exponent of distribution 4/7 ” for the ternary divisor function with nicely factorable moduli” (does that give us ? Or am I getting some quantities confused? I’m only following this story with half an eye)

23 June, 2013 at 11:28 pm

Terence TaoThe relationship is more complicated than this because the ternary divisor function is a reduced component of the Type III sums but is not the entire Type III sum (and in any event the Type III estimates have to be balanced against the Type I/II estimates). I computed the numerology against an older version of the Type I/II sums in http://terrytao.wordpress.com/2013/06/14/estimation-of-the-type-iii-sums/#comment-235226 . Redoing the numerology, it appears that if we assumed the 4/7 level of distribution for the ternary divisor function as a black box and ignored , we would have to balance (and also , but this turns out to be weaker) against , which would get us to the value of . With this new numerology it appears that it would still be worthwhile to improve the 4/7=0.5714 a little further; if one could get to 26/45=0.5778 for ternary divisor function then would hit the nice round value of , and then further improvements in Type III bounds do not gain anything unless one also improves on the Type I sums (or else starts dealing with Type IV and Type V sums related to the fourth and fifth order divisor functions…).

23 June, 2013 at 9:14 pm

The distribution of primes in densely divisible moduli | What's new[…] new input that was not present in the previous Type I analysis. Applying Proposition 5(iii) from this previous post, and noting that are coprime, we can bound the left-hand side of (51) […]

24 June, 2013 at 9:37 am

Terence TaoI just realised that Proposition 5(iii) can be proven without as much recourse to the Fourier transform, because the main terms on the RHS have a factor of and are thus morally invariant with respect to Fourier transforming/Poisson summation (it’s like bounding an L-function on the critical line , it shouldn’t help to apply the functional equation). Because of this, I think I can improve the final term in (iii) to get

.

This doesn’t directly improve the exponents, but it does make the estimation of certain secondary terms in the analysis easier.

I sketch the proof as follows. By the reductions mentioned in my previous comment, we may assume that . (One may also assume but this does not simplify the analysis.) As in the main post we may also take otherwise the standard bound (ii) is superior. It then suffices to show that

.

This can be proven by an argument very similar to the proof of Proposition 1. Namely, we perform Weyl differencing, replacing by for , where . This transforms the above sum to

.

The variable is localised to an interval of length , so by Cauchy-Schwarz it suffices to show that

.

The left-hand side expands as the sum of a diagonal term of and the off-diagonal terms

By completion of sums, the inner sum may be bounded by ; summing in this gives a bound of by the hypothesis , and the claim follows.

—

One further comment. Until recently, when one needed to bound the sum

the quantity was a bit larger than and so, given a choice between the trivial bound (i) and the standard bound (ii), the standard bound was superior (and was what was used in Zhang’s paper). But with the latest critical numerology, has fallen below , and in fact it appears that the shorter we can make (relative to ) and still get an improvement on the trivial bound, the better the Type I analysis becomes. The new bound (iii) gets us down to if we have dense divisibility in (and if are negligible, which they usually are in practice). So now we are in the realm where we want to start applying Burgess-type arguments in combination with the Weyl differencing (aka the q-analogue of van der Corput). Here it seems that the Graham-Ringrose paper http://www.ams.org/mathscinet-getitem?mr=1084186 will be relevant, because they do exactly this (but for character sums instead of Kloosterman sums). Basically the idea seems to be to perform Weyl differencing more than once – probably in our context twice is all we will need (and any further Weyl differencing presumably becomes counterproductive).

24 June, 2013 at 9:58 am

Terence TaoOh, I begin to see what’s going on. The first Weyl differencing replaces a sum such as S with a sum of the form

and the latter was then dealt with by the standard estimate coming from completion of sums. But there is nothing stopping us from iterating the procedure, factoring in a well-chosen fashion into, say, and performing Weyl differencing again (the rational functions in the phase become increasingly complicated when one does this, but that’s OK I think, the Weil conjectures can bound all of the completed exponential sums that arise). In principle one can get non-trivial bounds for as small a power of as we please (but we make increasing reliance on the dense divisibility by doing so, and the gain becomes exponentially smaller as we shrink ). This is all consistent with Graham-Ringrose (who refer to this Weyl differencing procedure as the “q-analogue of the van der Corput A-process”. Hmm – it occurs to me that the Fourier transform/Poisson summation is the q-analogue of the van der Corput B-process, so in principle all the van der Corput exponent pairs are available for use here…).

I have to work out the details, but it is likely that this is going to give another significant improvement to the numerology (beyond what we have tentatively worked out just through optimising the first Weyl differencing through refactoring). Basically, in the Type I analysis, one only has to gain a factor of over the trivial bound for in order to win (one has to overcome a previous loss of coming from completion of sums, amplified to coming from a previous use of Cauchy-Schwarz). While is beginning to get large enough that this factor is beginning to get noticeable, I don’t think that it is dominating the analysis yet, and enlarging the range of for which non-trivial bounds on are available should still be the better win. The numerology is that and ; making as small a power of as possible would allow us to raise as high as possible, which is good because of the lower bounds on coming from the Type III analysis (and also from the combinatorial constraint , although this is not yet dominant).

24 June, 2013 at 10:50 am

Terence TaoLet’s try blindly plugging in the numerology from Theorem 5 of Graham-Ringrose to get a rough idea of what to expect. For smooth squarefree moduli q, this theorem is basically asserting that

for , where and . By analogy (and ignoring delta), we would expect

(Although since Kloosterman sums do not have mean zero like character sums, there should also be a lower order term that is linear in N that we will ignore here.)

For k=0 this becomes

which basically is our current estimate (iii) after optimising the factorisation, and gives non-trivial bounds for . The k=1 version is

which is non-trivial for . Roughly speaking, to win using this estimate we would need

which rearranges to

which (I think) simplifies to

.

Balancing this against gives (I think)

(so the critical numerology is now , ). So in principle we have gained a bit over the previous estimate.

Let’s push our luck and try k=2:

which is non-trivial for . We now win if

which is

balancing against seems to give

so we are no longer winning (the gains in the aspect are finally being overwhelmed by the exponentially growing losses in the aspect). So the method seems to max out at , although one should do a bit better if we plug in the level of distribution for d_3 announced by FKM which replaces with and , which by my rough calculation should get us to .

LOTS of details to check before this is fleshed out properly though…

24 June, 2013 at 3:34 pm

Terence TaoIncidentally, the Type II analysis (which until now has not been a dominant source of constraints) currently has a barrier at (or more precisely, the current Type II arguments only work when ) but I am sure this can be lowered using the improved exponential sum estimates discussed here (and also perhaps by exploiting generic coprimality of and , something which has thus far been unexploited as it previously only affected non-dominant terms).

25 June, 2013 at 4:56 am

Enrique TrevinoIf (the type 3 barrier) then the best one could get for is which yields .

If then the best possible is which yields .

If the best is yielding .

The values for are according to the Engelsma and Sutherland lists. The comes from checking .

25 June, 2013 at 12:46 pm

Terence TaoThanks for the calculations! A fair bit of work will need to be done before we can claim these numbers (or some reasonably close values to these numbers) as confirmed, but it gives us some idea of what to expect we can get by pushing the ideas we currently have…

25 June, 2013 at 1:47 pm

Terence TaoI’m recording some more rigorous bounds on exponential sums of the form

where are of polynomial size, is square-free, is a smooth function on an interval of length , and is an integral rational function. Strictly speaking, depends not just on , but on the choice of smooth function , but I will abuse notation by suppressing this latter dependence. For technical reasons we will restrict attention to rational functions which

vanish at infinityin the sense that ; certainly Kloosterman type phases (e.g. ) fall into this category, and any linear combination of functions that vanish at infinity, or their derivatives and translates, will also vanish at infinity.For minor technical reasons (to avoid low characteristic issues) it is also convenient to assume that has no prime factor smaller than , where ; fortunately for our applications this is automatic.

We have the trivial bound

(1)

I now claim the following van der Corput bounds:

Van der Corput boundLet be fixed, and let . Thenwhere and .

Thus, for instance, the k=1 bound is

the k=2 bound is

when , and the k=3 bound is

when . As mentioned earlier, I believe that k=3 is the optimal value of k for the polymath8 project; any further increase in k looks to be counterproductive.

The van der Corput bound is proven by induction on k, so fix k and assume that the claim has already been proven for smaller values of k.

We first observe that we can reduce to the case , because any common factor between and is also a common factor between and (here we use the vanishing of at infinity, as well as the absence of small primes) and can thus be factored out of the phase by reducing appropriately. (This leaves behind a residual constraint that the denominator of be coprime to , but this constraint can be dealt with by Mobius inversion or else carried throughout the arguments below.) So henceforth we assume , so that and . Note that this also implies that , because any prime that divides will also divide by the fundamental theorem of calculus and the vanishing at infinity.

Now we prove the k=1 case. It suffices to show that

since the second term dominates only when . By chopping up into shorter pieces we may assume that . By completion of sums we can bound the LHS by

.

By the Weil conjectures , this is

and the summation is , giving the claim.

Now assume that and that the k-1 case has already been proven. If then the claim follows from the induction hypothesis (concatenating into a single ), since in this case. So we may assume that . We may also assume that , since otherwise and the claim already follows from the trivial bound.

We perform Weyl differencing, shifting to for , where . This lets us write as

We can factor

so that is bounded by

By Cauchy-Schwarz we may bound this by

The expression inside parentheses is expanded as

(**)

where . This is an expression of the form

The diagonal terms contribute a final factor of using the trivial bound, and this is acceptable. For the non-diagonal terms we use the induction hypothesis to bound this by

where

.

All the terms except for the last term

(***)

give an acceptable contribution. To control this last term we need to understand

(****).

Suppose that a (large) prime p divides . If p does not divide , this implies on translation and telescoping that divides for every , which makes constant and thus zero modulo p. Conversely, if divides then it certainly divides . We conclude that (****) is equal to , and (***) is then equal to

This sums to

which is dominated by the term since . Since that term was already under control, we see that this term is also acceptable. This proves the bound.

25 June, 2013 at 2:06 pm

Terence TaoBy the way, it looks like one can improve these estimates further by taking advantage of more averaging. Indeed, note that to bound a single sum , one only needs to control the Weyl-differenced sums

on averagein (and furthermore that the absolute values lieoutsidethe summation). This suggests that one should carry the averaging with us in the iteration, and perform Weyl differencing in those parameters as well. This should reduce the influence of the diagonal terms that show up (much as they did in the Type III analysis) and should lead to further improvements. Also when these exponential sums are used in the Type I/II analysis there is a similar averaging (again over parameters named h,h’) which could conceivably also be exploited. This could get a bit messy though, I will probably return to explore this point further once the non-averaged exponential sum estimates above are written up properly (and one also has to figure out the right notion of “double dense divisibility” in order to be able to get good triple factorisations , currently our dense divisibility hypothesis only gives us factorisations of the form , but this is a secondary issue as it only impacts which we now expect to be almost negligible).26 June, 2013 at 1:46 pm

Avi LevyMinor question: two displays before (4), it doesn’t seem to me like the cases , , and cover all possibilities. For instance, take , , and . Are you implicitly passing to a subsequence here?

26 June, 2013 at 1:59 pm

Terence TaoYes, one can pass to a subsequence to recover the law of the excluded middle in this sort of “cheap nonstandard analysis” (as I discussed in this previous post). Another option is to go the full nonstandard analysis route and install an ultrafilter in the parameter to decide when statements depending on are true or false (personally this is my favorite option, but I understand that many people prefer not to see ultrafilters present when they aren’t strictly necessary to an argument). Or one could turn off the asymptotic notation and have lots of ‘s and quantifiers instead, but this ends up cluttering the arguments with a lot of distracting technicalities.

30 June, 2013 at 12:39 pm

Bounded gaps between primes (Polymath8) – a progress report | What's new[…] 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 […]

7 July, 2013 at 11:17 pm

The distribution of primes in doubly densely divisible moduli | What's new[…] Proof: See Proposition 4 of this previous post. […]

8 July, 2013 at 2:58 pm

Gergely HarcosSome minor corrections and suggestions (sorry if they are slightly obsolete now):

1. In the endgame of the proof of (11), you remark that implies . This is certainly true, but not necessary for the proof of (11). We use here, but not , I think.

2. Four lines above (19), you remark that . I don’t see this, but we don’t need it either. We can bound the term in (14) as in the proof of (11), and then use as in the same proof.

3. In the second, fourth, and fifth display below (19), a factor is missing. This does not affect the subsequent argument.

4. The Gauss sum equals instead of .

5. In the proof of Lemma 3, should be , should be , and should be .

6. In (5) and in the next display, should be .

7. In the proof of Proposition 4, “ is well-defined” should be “ is well-defined”.

8. In the third display below (15), should be .

9. Six lines above (16), the inequality should be reversed. In the next line, both inequalities should be reversed.

10. Below (18), the text "We may rearrange this as" should be deleted.

11. In the fifth display below (19), the condition should be deleted, since is eliminated at this point. In the next line, the comment "we may use (15)" seems irrelevant and should be deleted.

12. "by (7) the diagonal contribution" should be "by (5) the diagonal contribution".

13. In the last two displays, should be multiplied by .

[Corrected, thanks – T.]9 July, 2013 at 10:10 am

Gergely HarcosDear Terry, just two small comments regarding these corrections:

3. For the sake of the reader I would write the fifth display below (19) as

.

5. The last point has not been implemented: should be .

[Corrected, thanks – T.]