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

As usual, we let be a large asymptotic parameter, and a sufficiently slowly growing function of . Let and be such that holds (see this previous post for a definition of this assertion). We let be a fixed admissible -tuple, let , let be the square-free numbers with prime divisors in , and consider the truncated GPY sieve

where

where , is the polynomial

and is a fixed smooth function supported on . As discussed in the previous post, we are interested in obtaining an upper bound of the form

as well as a lower bound of the form

for all (where when is prime and otherwise), since this will give the conjecture (i.e. infinitely many prime gaps of size at most ) whenever

It turns out we in fact have precise asymptotics

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

and (3) is similarly equivalent to

Here is the number of prime factors of .

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

We would now like to replace the truncated interval with the untruncated interval , where . Unfortunately this replacement was not quite done correctly in the previous post, and this will now be corrected here. We first observe that if is any finitely supported function, then by Möbius inversion we have

Note that if and only if we have a factorisation , with and coprime to , and that this factorisation is unique. From this, we see that we may rearrange the previous expression as

Applying this to (4), and relabeling as , we conclude that the left-hand side of (4) is equal to

This is almost the same formula that we had in the previous post, except that the Möbius function of the greatest common divisor of was missing, and also the coprimality condition was not handled properly in the previous post.

We may now eliminate the condition as follows. Suppose that there is a prime that divides both and . The expression

can then be bounded by

which may be factorised as

which by Mertens’ theorem (or the simple pole of at ) is

Summing over all gives a negligible contribution to (6) for the purposes of (4). Thus we may effectively replace (6) by

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

Note that vanishes if or . In practice, we will work with functions in which has a definite sign (in our normalisations, will be non-positive), making non-negative.

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

We may factor for some with ; in particular, . The previous expression now becomes

Using Mertens’ theorem, we thus conclude an exact formula for , and similarly for :

Proposition 1 (Exact formula)We havewhere

Similarly we have

where and are defined similarly to and by replacing all occurrences of with .

These formulae are unwieldy. However if we make some monotonicity hypotheses, namely that is positive, is negative, and is positive on , then we can get some good estimates on the (which are now non-negative functions) and hence on . Namely, if is negative but increasing then we have

for and , which implies that

for any . A similar argument in fact gives

for any . Iterating this we conclude that

and similarly

From Cauchy-Schwarz we thus have

Observe from the binomial formula that of the pairs with , of them have even, and of them have odd. We thus have

We have thus established the upper bound

By symmetry we may factorise

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

and so

Note that

and hence

where

In practice we expect the term to dominate, thus we have the heuristic approximation

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

But we have an improvment in the lower bound in the case, because in this case we have

From the positive decreasing nature of we see that and so is non-negative and can thus be ignored for the purposes of lower bounds. (There are similar improvements available for higher but this seems to only give negligible improvements and will not be pursued here.) Thus we obtain

Estimating similarly to we conclude that

where

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

By Theorem 14 and Lemma 15 of this previous post, we may take the ratio to be arbitrarily close to . We conclude the following theorem.

Theorem 2Let and be such that holds. Let be an integer, defineand

and suppose that

Then holds.

As noted earlier, we heuristically have

and is negligible. This constraint is a bit better than the previous condition, in which was not present and was replaced by a quantity roughly of the form .

## 91 comments

Comments feed for this article

11 June, 2013 at 10:01 pm

REMIDI UAS SEMESTER 2[…] Further analysis of the truncated GPY sieve This post is a continuation of the previous post on sieve theory, which is an ongoing part of the Polymath8 project. As the previous post was getting somewhat full, we are rolling the thread over to the current post. We also take the opportunity to correct some errors in the treatment of the truncat … Wed, 12 Jun 2013 00:54:00 CDT more info… […]

11 June, 2013 at 10:04 pm

The prime tuples conjecture, sieve theory, and the work of Goldston-Pintz-Yildirim, Motohashi-Pintz, and Zhang | What's new[…] The above argument is not quite correct; a corrected (and improved) version is given at this newer post.] The product is by e.g. Mertens’ theorem, while . So the contribution of this case is […]

11 June, 2013 at 11:31 pm

v08ltuIf it all holds up, using the exponential integral directly instead of the approximant (this saves about 5%), I get that and is best. I have rather than that comes from the approximant.

11 June, 2013 at 11:53 pm

v08ltuThe relative error in the exponential integral approximation is about (5%). On the other hand, with as following Pintz, I think the main effect is at as above, so only lose 0.15%.

12 June, 2013 at 2:11 am

Gergely HarcosWhat is the value of ? Also, what do you get with the improved and analogous that I suggested below? My preliminary calculation tells that we save about 2%.

12 June, 2013 at 1:18 pm

v08ltuThe would be about the square, or . There is really no reason to make any approximations in the case, which should dominate, for there the integrals are easy. But you’ve probably worked this all out by now.

12 June, 2013 at 2:40 pm

Gergely HarcosYes, I have now understood this. Thank you!

12 June, 2013 at 1:05 am

Gergely HarcosThis is very nice and clean. We can improve on as follows. By a similar argument as in the post,

.

By Cauchy,

Applying the first observation iteratively on both factors,

Therefore in (8) and in the definition of we can lower to , and for the new we infer

.

From here we can proceed as in the post, using , but the integral should be straightforward numerically.

Some typos:

1. In (3) the factor is missing.

2. " coprime to " should be " coprime to ".

3. "which are now non-negative functions" should be "which are now functions of constant sign".

4. Three displays above (8), should be .

[Corrections 1-4 implemented, thanks. -T.]12 June, 2013 at 1:13 am

Gergely HarcosActually the upper bound I stated for the new is an identity. All in all, the above modification simplifies the proof and produces a better result.

12 June, 2013 at 3:10 am

Eytan PaldiCan you please state explicitly the identity? (because there is a stable numerical expression for the last one dimensional integral – showing it to be a remainder term for Taylor series approximation of the log function, which gives a new improved upper bound for the integral in terms of a power of instead of the current exponential bound.)

12 June, 2013 at 3:28 am

Gergely Harcos12 June, 2013 at 5:43 am

Eytan PaldiThanks. Consider now the integral above, denoting for its lower bound and for the exponent .

The new upper bound is most simply obtained by replacing in the integrand by .

Note that for large , the resulting new bound

should be better then the exponential one since it captures better the integrand behavior for large values of t.

Note that by trying directly to evaluate the integral by expanding

in the integral and then integrate termwise, may lead to serious numerical problems since the alternating large binomial coefficients may lead to a significant loss of precision.

Fortunately the above numerical instability can be avoided by using the substitution so the integrand becomes

, so by term-wise integration it follows that the integral is in fact the remainder term for the k-th degree Taylor series approximation of in powers of u at

, which implies the same new bound above.

Practical remark: it is important to note that all the coefficients of the above Taylor series approximation of in powers of

are positive and slowly decreasing so its computation at

should be numerically stable!

Final remark: in your integral bound, which is integer

only for EVEN (otherwise, it is expressed by incomplete Beta function which can’t be expressed by a finite sum of elementary functions as above, but the new bound still holds!)

12 June, 2013 at 6:28 am

Gergely Harcos@Eytan: At this point I leave the calculation to computers. SAGE does a good job in evaluating such integrals numerically. For example, for I get

,

and is essentially .

12 June, 2013 at 7:33 am

Terence TaoThanks for this! One amusing thing is that the bound is in fact very slightly worse than , but the product formulation ends up being so much cleaner that it is easier to see the opportunity to improve upon the bound involving the exponential function. The above estimates also reveal that the (upper bounds on the) terms in which are smaller than the others by an additional factor of at least , which in principle can improve the , factors to be close to respectively for , although this only leads to negligible improvements at the cost of a messier formula.

12 June, 2013 at 2:14 pm

Gergely Harcos1. Amusing indeed! In fact the optimized version of

reads

which by induction recovers the original

2. We beat the quarter million barrier for prime gaps!

12 June, 2013 at 2:35 pm

v08ltuCan one improve the lower bound on via not being so lossy on , which now appears to go as and , so it’s nonnegative? (In fact, by symmetry.) Maybe an improvement would use convexity somehow, or simply use the explicit expressions for ?

12 June, 2013 at 3:05 pm

v08ltuIt could be that we could almost obtain , if the upper bound of were nearly sharp.

12 June, 2013 at 2:10 am

Eytan PaldiIt seems that there is a typo in the summands in (3).

12 June, 2013 at 2:11 am

Gergely HarcosI mentioned this above (see item #1 in “Some typos”).

12 June, 2013 at 5:13 am

Gergely HarcosUsing the small improvement I described above, SAGE tells me that and is best. For this choice, and .

12 June, 2013 at 12:50 pm

Eytan PaldiA suggestion to further optimize :

It seems that always the minimization of is done

1. Subject to the (unnecessary) restriction that is an integer, and

2. is determined by to satisfy the admissibility inequality constraint as EQUALITY constraint (i.e. the maximal

possible under the constraint).

My suggestion to deal with these two problems is:

1′. To refine the optimization of in its neighborhood by allowing it to be a multiple of 0.1 (or 0.01) in the interval (890, 892).

2′. Using the previously optimized (not necessarily integer!) value of

FIXED, and optimizing the previous value of

as an integer satisfying the admissibility constraint (in order to get a GLOBAL search for – not only near the admissibility boundary!) and then using a finer LOCAL optimization search for

as a multiple of 0.1 (or 0.01).

Since both steps (1′), (2′) can only reduce the value of , by alternating between this steps, k_0 should converge to a local minimum (by making the local search in (1′), (2′) finer enough.)

One may find many variants to this “alternating search” optimization, in particular a coarse GLOBAL search may be added at the beginning of (1′) in each iteration, using the value of from the previous iteration FIXED (in order to keep a GLOBAL optimization at each iteration.)

Remark: Note that the current values of and

have the same order of magnitude!

12 June, 2013 at 3:05 pm

Gergely Harcos1. The expressions for and are decreasing in , hence for a given we do not lose anything by taking the satisfying .

2. I believe that is optimal for the current version of Theorem 2. I don’t have a formal proof, but it is advantageous to see how the ratio of and changes as we vary or . For , the ratio is when , it is when , and it is when . For , the ratio is when , it is when , and it is $0.9999990240$ when .

12 June, 2013 at 4:07 pm

Eytan PaldiThank you for the data!

It follows therefore that for each given the optimal

is determined such that the admissibility constraint should becomes equality (i.e. the maximal permissible ), which leaves as the ONLY free parameter to minimize . Therefore (since is NOT restricted to be an integer), I suggest to vary with small steps (0.1 say) in the interval (890, 892) to see if one of these 19 values of leads

to a new record of . (since it involves a small number of trials, I think it worth the effort!)

13 June, 2013 at 5:45 am

Eytan PaldiI’m trying to analyze your data about the ratio above as a function of

and as free parameters ( is not free because of its dependence on via the restriction equality.)

It is easy to see from your data the almost linear dependence of the ratio

on in for (which was quite expected), but the dependence of this ratio on in

in for must be WRONG because

1. The ratio should be for the admissible pair

, while the ratio you gave was

.

2. For the dependence of the above ratio on

in is NOT monotonic (as it should be.)

It seems that the problem is due to a WRONG computation of the above ratio for the pair . Can you check it please and let me know the correct ratio. Thanks

13 June, 2013 at 5:53 am

Gergely HarcosI am confident my calculations are correct, and v08ltu independently confirmed them. Terry Tao also checks everything here.

13 June, 2013 at 6:00 am

Eytan PaldiBut how is it possible that the admissible pair (892, 22249) gave a ratio LESS than 1? (it contradict the admissibility criterion in theorem 2!)

13 June, 2013 at 6:27 am

Gergely HarcosThere is no contradiction to Theorem 2. Let us fix . In the interval the expression (for the optimized ) is decreasing, hence and are increasing. So in Theorem 2 we are looking at the ratio of two increasing quantities: and . The fact that the ratio has a local maximum in simply reflects the fact that grows faster than on the left end of this interval, but this tendency changes somewhere inside the interval.

13 June, 2013 at 6:55 am

Eytan PaldiIt seems VERY strange that the criterion in theorem 2 is sufficient to decide that for , the parameter is admissible (since the above ratio is greater than 1), while for

(which obviously should be admissible) it can’t do so (because of ratio less than 1).

It is still possible (since the criterion is only sufficient), but it still seems very strange!

13 June, 2013 at 8:42 am

Gergely HarcosThe phenomenon is not so strange if you think of the role and meaning of the parameter . Ideally it would be infinite, i.e. we would use all divisors for the sieve leading to Theorem 2. In that case we would not have to consider and at all (they would be zero), and the crucial ratio would be proportional to , i.e. monotonic as you expect it to be. The reason that we do need a finite is our lack of understanding of the equidistribution of primes to large moduli, including those with possibly large prime factors. Zhang’s discovery is that for sufficiently small , we can allow sufficiently many (but not all) prime factors to participate in the moduli, and this is measured by . At this point we have two opposite forces: Theorem 2 wants a as large as possible, but the necessary hypothesis is only available for sufficiently small depending on . So the question is: which gives the best compromising value of , one that is sufficiently small for the hypothesis to hold provably, and one that is sufficiently large for a good value of . As things stand now, the best value lies somewhere between and . It is a complicated proof!

12 June, 2013 at 3:13 pm

v08ltuI always use tenths of an integer in the reciprocal of , but the -result has never needed such precision in reporting.

12 June, 2013 at 4:19 pm

Eytan PaldiIt depends on the sensitivity of to small changes in

as well as how the above ratio is close to 1 (i,e, very small changes may lead to a downward “jump” to if the ratio is sufficiently close to 1.)

12 June, 2013 at 1:40 pm

v08ltuI agree with this bound.

12 June, 2013 at 9:00 am

Craig HelfgottI have one question, and it may be obvious, but it is confusing me: When you derive (6) from the preceding line, you are apparently factorizing as . Why is this allowed?

12 June, 2013 at 9:04 am

Craig HelfgottOkay, went back to the previous post for the definition of . Sorry, I thought you were using Big-Omega notation.

12 June, 2013 at 1:10 pm

unknown mathematicianDear Prof. Tao and other top mathematicians here,

Is the purpose of this to turn Zhang´s paper obsolete even before it appears in print? It seems that this is already the case.

I wonder if had the author of the paper being studied been one of the top people in the area (one of you) if it would have generated such a collective effort to improve the result. I have never seen anything like this before.

I am a big fan of many math blogs and this is one of my favorites, but I cannot help the feeling that there is something not very nice happening here.

12 June, 2013 at 1:29 pm

GhaithDear unknown mathematician, I don’t think this is the case. Zhang’s result is amazing (I certainly wasn’t expecting to see something like it that soon). I think the collective effort you observe is natural since this is the most exciting thing to happen in number theory in a while. As a result, some people (e.g. me!) have gotten far more interested in learning about the proof. I think that the progress that has been made since then is impressive, and impressively rapid.

12 June, 2013 at 2:35 pm

Gergely HarcosNot at all! First Zhang’s paper already appeared in “print” (the final version is on the journal webpage, the physical paper is not important). Second, nothing can make the work of Zhang or Goldston-Pintz-Yildirim obsolate, since the ground-breaking ideas are there. I think what is happening is this. A few months ago noone (except for Zhang perhaps) thought that we would see bounded gaps between primes. Zhang’s “70 million” is not an astronomical constant like that was customary in similar advances such as ternary Goldbach, Waring for cubes, Catalan’s conjecture etc. So one simply wonders what Zhang’s method with some tweaks is capable of. I find this a nice way to pay respect to Zhang, respond to the basic curiosity “So how small are those gaps, really?”, have fun together as a PolyMath group, and understand the argument as well as possible. There is really no reason to hold back progress, time is our real enemy.

12 June, 2013 at 4:28 pm

Dan GoldstonAll this interest and activity generated by Zhang’s work is a tribute to the importance of his contribution. It is true that the paper will not appear in print for years, but it is accepted for publication and available for others to build on. I think that anyone working on this problem for years to come is going to study Zhang’s paper for his insight.

13 June, 2013 at 1:58 am

PeteObviously I don’t know how Zhang feels about it, but for sure I would be extremely happy if a result of mine was getting this kind of attention. It says: this result is not just worth a paper in Annals, it is worth weeks or months of time of the world’s best mathematicians (and it will surely be judged worth prize(s) as well).

Eventually there will be a (probably) Polymath long paper which gives substantially better bounds than Zhang’s original. It will probably also be published in Annals. But it will surely be written to be very clear that the improvements are absolutely relying on Zhang’s fundamental breakthrough. And no-one will get prizes for it.

There are also different levels of achievement on this problem. Pre-Zhang, the best known result was only somewhat better than the trivial point that the minimum gap isn’t larger than the average gap (and this was already a big result). Probably it was expected that the next result would be some slowly-growing-function gap, and as several people already said, no-one expected to see bounded gaps any time soon. In that context, if you can prove any bounded gaps theorem, then you are happy: you don’t really care if the bound is in the thousands, millions, or some tower of exponents (and exponentials usually appear in these kinds of things the first time, in some sense Zhang got lucky that his approach doesn’t need any). Zhang himself fairly obviously did not care too much: he deliberately didn’t optimise his work in the interests of writing a more readable paper, whereas the polymath version will probably have a lot of strange numbers and optimisations done by computer, as well as the ‘genuine’ improvements by modifying the approach, which will make it a lot harder going.

The books will record the fact of bounded gaps in the primes as ‘Zhang’s Theorem’, and the polymath result will be a note as an ‘improved Zhang’s Theorem’ or such: it seems very likely that the approach will not get to any gap such as 16, or 6, let alone 2, which would merit a new name.

13 June, 2013 at 2:06 am

Gergely HarcosActually before Zhang it was known that around we can find prime gaps of size less than , a result by Pintz improving on a similar result of Goldston-Pintz-Yildirim with exponent in place of . I would not call this “somewhat better than the trivial point”, it was already a fantastic result.

13 June, 2013 at 3:35 am

PeteSure, but when log is easy and the aim is 2, polylog doesn’t look like a big step. I think the point you (and I) are trying to make is that even polylog was already very hard.

13 June, 2013 at 5:48 am

Gergely HarcosI always thought of as being half-way between the trivial gaps and bounded gaps (although, admittedly, I did not expect to see bounded gaps in my life). In some sense Zhang justified this feeling of mine.

13 June, 2013 at 2:42 am

bengreenI think these are pretty good responses to unknown mathematician’s comment. If polymath wasn’t happening, the alternatives would be that Zhang’s 70000000 just sat there for everyone to admire, or else people would publish piecemeal improvements and there would be one enormous mess deciding priorities (for those who cared) and even correctness. Even now, with the bound on around 300000, there could yet be over 100000 papers on the subject of improving the gap if we were proceeding in this way. The polymath is the perfect solution to this problem in my view. It’s highly inclusive and no-one fusses over priorities and credit. In addition, as pointed out above, these great ideas – not just of Zhang, but also of GPY, BFFI, etc – are getting publicly celebrated and debated. I can’t really imagine why that would annoy any of them.

To echo Pete’s comment, Zhang pretty explicitly states that his exponents are not optimised. Most likely he knew a few of the improvements that have come to light already in the polymath discussion, but he deferred from mentioning them so as to write a more readable paper. Anyway, I don’t get any kind of sense that the contributors to this blog are rushing to show Zhang how he could have done better, if that was the aspect of this thought to be “not very nice” by unknown mathematician.

13 June, 2013 at 5:44 am

Gergely HarcosActually is now below 250000 :-)

16 June, 2013 at 9:05 am

unknown mathematicianFirst I want to thank you for all the responses to my comment. I also want to apologize for my very poor choice of words in it. I do have the highest respect for the mathematicians here not only for their mathematical abilities but also for the very high ethical stand assumed. As was mentioned before I too, would feel honored if one of my papers would get this much attention from a mathematician like Terence Tao.

I did not say that Zhang would not be given the proper credit for his work. His name is already in History and every response to my comment made that clear.

The only thing I still suspect ( I cannot be sure for I am not a number theorist) is that after all the work done here, if there are still insights in the original paper that have not been “dissected” here.

This went too far and I do regret to have written the above comment but cannot undo it … yet.

13 June, 2013 at 4:10 am

Mark BennetI think that Zhang gets huge credit through this approach to his work, because it is clear that the improvements are founded on his work and insight – as an interested non-specialist that’s what I read – and he will also see the cascade of ideas and improvements his work has started.

Another advantage, as yet unstated, is that the Polymath approach here also tests the limits of what is possible using Zhang’s insights and maps the various barriers to progress. So that helps to see where new insight is necessary to go further.

13 June, 2013 at 7:10 am

Andre K.Dear Unknown Mathematician,

My feeling reading this blog is exactly the opposite of yours. I see it as a tribute to Zhang. I would be very proud to see so many advances based on my own ideas. Also, for people like me, amateur mathematicians (did my undergrad in math but moved on to other jobs), a blog like this is a magnificent window on how ‘real mathematicians’ work. It is an opportunity to see the work build up with all the unfruitful paths that do not work out and the little by little progress that is made. Otherwise, we would only see the final product – the paper in a journal. I commend Terence Tao for exposing all of us to this wonderful adventure. Andre K.

12 June, 2013 at 2:21 pm

Gergely HarcosSome typos: In the display below the definition of , should be . In the definition of , should be , and integration should end at . In Theorem 2, the values of and should be updated similarly.

[Corrected, thanks – T.]12 June, 2013 at 3:32 pm

Gergely HarcosActually, in the definition of , the exponent should be . Two occurrences.

[Corrected, thanks – T.]12 June, 2013 at 11:23 pm

Gergely HarcosIn the definition of , the denominator should be instead of . Two occurrences.

[Corrected, thanks – T.]13 June, 2013 at 5:00 pm

Non-MathematicianI am absolutely a non-mathematician and find this site fascinating, and feel good for Zhang every time I visit here. No I don’t read the math discussions, but only read the shrinking numbers (and why they got crossed out.)

14 June, 2013 at 1:37 am

Gergely HarcosI claim that is nonnegative, hence is admissible in Theorem 2. For the proof let us consider functions of the form

where is a fixed measure on , and are decreasing nonnegative functions such that the integrand is integrable. Let us call a function nice, if it is a sum of functions of the above form. We observe that if is nice, then and are nice for for any . Moreover, and are nice for any . It follows that

is nice for any . Now we see that, for any , the function is nice, hence its value at is nonnegative. However, we can check by induction on that this this value is nothing but

Specializing to gives the claim.

14 June, 2013 at 10:12 am

Terence TaoActually, could you give more detail as to why is nice? Taking Newton quotients this would seem to imply that is also nice, which looks like a statement that would need control on higher derivatives of .

In our specific case, we do know that the Bessel-type function has derivatives with a fixed (alternating) sign, but one has to be careful when truncating at the endpoint since one only has a limited amount of regularity at this endpoint.

14 June, 2013 at 6:38 pm

Gergely HarcosYou are right, I announced the result too quickly. I think the new values of and are still ok, we don’t need any regularity at .

To fix the proof, let us call a function appropriate if it is supported on some such that has sign in . If is appropriate, then so is for any , while is a sum of two appropriate functions for any . Hence if we restrict to appropriate functions in the definition of nice functions, and we take restricted to , then the argument goes through to yield

.

We apply this for restricted to to see that the new is admissible. To obtain , we use instead and , all restricted to .

So do you agree that Theorem 2 holds with the new values of and ?

14 June, 2013 at 6:47 pm

Gergely HarcosActually should be here and also in my comment today at 4:56 am. Note that for these values

are equal.

15 June, 2013 at 7:58 am

Terence TaoI’m not yet clear why is the sum of two appropriate functions, particularly in the case when when one has to cross a point of potential discontinuity of . Could you elaborate?

15 June, 2013 at 5:35 pm

Gergely HarcosSorry my setup was still incompatible with my intuition. I think I got it right now, see my longer post below, sent a few minutes ago.

14 June, 2013 at 4:56 am

Gergely HarcosThis is a continuation of my previous comment. Let us introduce the notation

so that by Cauchy, with equality when and . Let us also fix . Then we can see, as in the main post, that replacing by or for any multiplies the function by at most , while replacing by or for any cannot increase . It follows, by Minkowski’s inequality, that for any , hence for any we have

.

In particular, using the point we infer

.

Specializing to the nice function we obtain finally

.

This is an improved version of (8), and yields Theorem 2 with the smaller values and

.

14 June, 2013 at 5:20 am

Gergely HarcosIn practice one can replace by the clean

.

14 June, 2013 at 5:51 am

Eytan PaldiIn fact, you reduced (in the sum) the factor to

but since (in general) dominates, the improvement in might be small. I think that the elimination of could be more significant.

14 June, 2013 at 5:56 am

Gergely HarcosThe elimination of is also insignificant, because it has no term. At the moment the improved values serve esthetic purposes, but for smaller values of they might be useful eventually.

14 June, 2013 at 8:45 am

Terence TaoVery neat! I’m impressed that you got all this positivity just from the monotone nature of and ; I would have thought that further properties of higher derivatives would be needed, but apparently not.

As you say it probably doesn’t lead to any improvement on with our current values of but may make a contribution in the future.

14 June, 2013 at 5:32 am

Eytan PaldiIn proposition 1, in both sums n should start with 1 (not 0)

14 June, 2013 at 6:00 am

Gergely HarcosNo they are ok. The terms are the leading terms and , while the terms are compared to these, the respective ratios being bounded by and .

14 June, 2013 at 6:23 am

Eytan PaldiBut means that there are no integration variables!

14 June, 2013 at 6:33 am

Gergely HarcosYes. It is an empty multiplicative integral, i.e. equal to 1 (just like an empty product). This is a convention that Terry uses. If you look at the second display before Proposition 1, you will see that the term corresponds to the term there (because this is the only number with no prime factor), and this term equals .

14 June, 2013 at 6:46 am

Eytan PaldiI don’t understand why do you call this empty integral “multiplicative” and the logic behind its definition as 1 (irrespective of its integrand)

Anyway, for clarification I suggest to separate the summand from the sum (because I don’t think this convention to be a standard one.)

14 June, 2013 at 8:05 am

Terence TaoThe logic is similar to the reason why powers for , or more generally products for , are by convention set equal to when (see the Wikipedia entry on “empty products“), and can in fact be deduced from that standard convention as follows.

is the standard real -dimensional vector space. Thus is the standard zero-dimensional vector space, i.e. the point . More formally, by definition is the set of -tuples , with the zero tuple identified with ; thus, is the set of -tuples , but there is only one such tuple (cf. the rule mentioned earlier), and we identify this tuple with .

To normalise n-dimensional Riemann or Lebesgue integration, we define the measure of a box when for all to equal . In the zero dimensional case , the box is a singleton set consists only of the empty tuple (as can be seen by carefully checking the definition, noting that universal quantification over an empty set is vacuously true), and the product is one by the empty product convention. Thus we see that has Lebesgue measure one. (Another way of seeing this is recalling that -dimensional Lebesgue measure in is the same thing as -dimensional Hausdorff measure on , and that 0-dimensional Hausdorff measure is counting measure.) In particular, if is a function, the empty integral

is equal to the value of at the origin . Thus for instance

when is equal to the evaluation of the integrand at the origin (note carefully that the region of integration is the singleton set rather than the empty set). The denominator looks scary, but recall that the empty product is 1, so that when , and so the expression simplifies to , which is if one works through the definitions.

In the special case when one is integrating a tensor product

for well-behaved functions then it is particularly clear that the case of this integral should be , since Fubini’s theorem factors this integral as

and by convention the empty product is 1 (informally, the zero-dimensional integral of a “multiplicative” integrand is automatically 1). Another relevant example comes from the identity

which extends without difficulty to the case using the correct conventions for zero-dimensional integration and for .

Basically, all of n-dimensional integration theory extends without difficulty to the 0-dimensional case when one adopts the correct conventions, much as the theory of exponentiation for non-zero x and natural number n extends without difficulty to the case when one adopts the correct conventions. Isolating the case can be done if desired, but is not necessary (much as one could write, for instance, the Taylor series as if one was for some reason uncomfortable with the standard conventions for and ). In order to keep the presentation short and avoid needless duplication of effort in handling a seemingly degenerate case that does not actually need any special attention, I have generally elected keep the n=0 case combined with the positive n cases.

14 June, 2013 at 6:34 am

AnonymousPintz’s paper on arxiv has already been corrected can someone update the wiki to reflect that?

[Done, thanks – T.]14 June, 2013 at 11:04 am

Eytan PaldiI understand the extension of integration on 0-th euclidean space using its Housdorff measure (which makes sense as “natural”), but I am not sure about the extension of Fubini theorem for this case. Also, It is not clear to me whether this is the only “natural” (and even “the” standard) extension.

(For example, “the” sum of the natural numbers was “naturally” interpreted by Ramanujan as .)

15 June, 2013 at 9:02 am

Eytan PaldiMinor remark: perhaps it is better in proposition 1 to replace the summation index i (running over T) by j.

15 June, 2013 at 11:23 am

Eytan PaldiIn the 4-th and 6-th lines before (10), the index n should be 1.

[As explicitly stated just before these lines, the text here is restricted to the case (except for the parenthetical comment, which is explicitly restricted to the higher cases.) -T.]15 June, 2013 at 1:34 pm

Eytan PaldiA combinatorial question: the numbers of partitions above to S and T are REGARDING the order of S and T.

Is it necessary? (otherwise, the bounds may be improved.)

15 June, 2013 at 5:15 pm

Eytan PaldiIn the fifth line above theorem 2, “we see” may be inserted before “that”.

15 June, 2013 at 5:32 pm

Gergely HarcosThis is my third attempt to improve (8) to

for . This implies my earlier claimed improved value for , while follows similarly.

Let us restrict to functions supported on some initial segment such that is bounded and of sign on . Such functions will be called -appropriate. For let us consider the functions

and

initially defined on and then extended to be zero on . We observe that and are -appropriate, and their sum equals on . As in the main post, for the inner product

we have . Moreover, implies .

Let be -appropriate. For any with sum at most , let us consider the bilinear form

Then we have

.

Noting that equals on the support of , we infer

.

The point is the we have two terms with signs instead of three terms with signs . By induction and the above remarks, we readily establish

.

Specializing to and yields

.

15 June, 2013 at 7:55 pm

Terence TaoDear Gergely,

I think that the assertion that equals on the support of is not quite enough to conclude that is equal to except when , because of the non-local nature of the bilinear form.

16 June, 2013 at 3:18 am

Gergely HarcosYou are right, I overlooked again. I found a new approach, please have a look at my comment below. Thanks for your patience and checking everything carefully!

16 June, 2013 at 3:15 am

Gergely HarcosTerry is right, I was wrong again. But here is my fourth attempt to prove the same!

I will use the notation from my previous comment. Let be -appropriate functions, and let

be arbitrary numbers with sum . I claim that the function

is decreasing on .

As a simple consequence, we shall have

for .

We prove the monotonicity claim by induction on . For the statement follows from the fact that and are nonnegative and decreasing. Now assume the statement for in place of . For we obtain, by definition,

,

where is -appropriate. Hence it suffices to show that

for .

Renaming to , and to , we have reduced the induction step to the already mentioned consequence

for .

To see the last inequality, we combine the identity

with the induction hypothesis. We obtain

,

and we are done. As a useful consequence, the identity now implies

.

By induction again and the remarks in my previous comment, we can now readily establish

.

Specializing to and yields

.

16 June, 2013 at 5:16 am

Gergely HarcosActually I am still not happy with the argument. Here are some thoughts that resonate with Terry’s earlier warnings.

1. We need to allow (resp. ) to be -appropriate (resp. -appropriate) with possibly different . We have no regularity at and , so we cannot really go beyond the range by considering higher derivatives. This means that the final conclusion

is restricted to . Perhaps some combinatorial ideas can establish the lower bound in general, e.g. by cleverly arranging the terms in , and then the upper bound follows as well. In fact we would only need the lower bound for .

2. For similar reasons we cannot really deduce for from the fact that is decreasing on . This can be remedied, however, by adding nonnegativity to the monotonicity statement, and inducting on for the stronger statement.

16 June, 2013 at 7:43 am

Terence TaoPerhaps one should focus on the n=2 case for now, as this would generate the lion’s share of the savings even if it does not lead to the most elegant results.

In any event, for the specific example of Bessel functions, we should be able to get some more improvement in kappa from direct calculation of the n=1 terms rather than by upper bounds, but this would require numerical integration of Bessel functions of high order (not too computationally infeasible, but it may require a little more than simply using the off-the-shelf integration command for Maple/SAGE/Mathematica/etc. if one is to be confident about the accuracy of the integral). Although one thing that is working in our favour is that is now dropping to levels (such as 6329) in which accurate numerical computations for the relevant integrals look quite feasible.

16 June, 2013 at 10:07 pm

Gergely HarcosYou are right about , let me post a new comment about this below.

16 June, 2013 at 5:53 am

Eytan PaldiThere is a simpler and better way than using the trick with the (somewhat crude) inequality above, the idea is to find the MINIMAL function satisfying

whenever are in

, but for a specific proportional to the Bessel solution!

As it turns out, the solution is implied by the following sub-multiplicativity property for g (proportional to the Bessel solution) normalized to g(0) = 1:

, whenever are in

Clearly, this property should give simpler and better bounds. (I’ll send the details in some hours.)

16 June, 2013 at 10:09 pm

Gergely HarcosFor it is straightforward to generalize the treatment of in the post. Let be nonnegative, continuous, and decreasing. Then

,

and

This implies

.

In addition,

.

This shows that

is valid for , and the same is true with in place of . As a result, in the expression for , the term can be omitted, while for the term can be multiplied by .

17 June, 2013 at 4:21 pm

Eytan PaldiIn the third line above (8), it should be trinomial (instead of binomial)

[Depends on how you count it. I used the sum and difference of binomial formulae and to arrive at these conclusions. -T.]17 June, 2013 at 5:23 pm

Eytan PaldiThanks! (I used the equivalent expansions and

)

18 June, 2013 at 9:03 am

Gergely HarcosI think I proved that for any nonnegative, continuous, and decreasing functions , and for any ,

.

We use the convention that are extended to be zero on , and we borrow notation from our earlier attempt (http://terrytao.wordpress.com/2013/06/11/further-analysis-of-the-truncated-gpy-sieve/#comment-234683). Combining nonnegativity with the recursion identity

,

where * abbreviates , we obtain by induction

.

This yields Theorem 2 with and

.

The main idea of the proof is that can be approximated arbitrarily well in sup-norm by decreasing step functions, which in turn are nonnegative linear combinations of the characteristic functions extended by zero on . Hence it suffices to verify

for any .

We work with the measure supported on , hence we have the scaling property

.

That is, we can restrict to without loss of generality, and it suffices to show

for any .

We shall prove more, namely that the left hand side decreases in . This implies nonnegativity, as the left hand side approaches zero for .

With the convention that for , the recursion identity expresses the left hand side as

.

By the scaling property, we can rewrite this as

for ,

for .

Based on these scaled recursion formulae, we shall prove the following claim by induction on : for any fixed , there is a finite set such that on any interval the function is of the form with nonnegative constants . The claim implies that decreases on , hence in fact on by its continuity in .

Now we show the claim by induction on . For the statement follows from . Let us assume the statement for in place of . Let us fix , and consider the exceptional set corresponding to . Let be the set of points such that any of the following expressions lies in : , , , . Add also to . Now let be any interval. By the scaled recursion formulae and the induction hypothesis, there are nonnegative constants , such that takes one of the following two forms on all of :

,

or

.

The first expression simplifies to , while the second simplifies to

.

In both cases is of the form on , where are nonnegative constants, hence we are done.

18 June, 2013 at 9:17 am

Gergely HarcosActually this proof gives the stronger statement that I anticipated before:

decreases on .

18 June, 2013 at 9:52 am

Gergely HarcosActually, I erred again, in the last step: I proceeded as if each of , , , mapped into the same interval lying in . This is clearly false. Nevertheless, I believe the ideas in this approach are good ones. One needs to understand explicitly enough to conclude that it is nonnegative. I believe this is doable (although not really important for the project).

19 June, 2013 at 7:09 am

Gergely HarcosThe statement I tried to prove here is false, see http://terrytao.wordpress.com/2013/06/18/a-truncated-elementary-selberg-sieve-of-pintz/#comment-235214

18 June, 2013 at 6:19 pm

A truncated elementary Selberg sieve of Pintz | What's new[…] post is a continuation of the previous post on sieve theory, which is an ongoing part of the Polymath8 project. As the previous post was getting somewhat full, […]

18 June, 2013 at 6:40 pm

Terence TaoTime to close this thread and move on to the next one:

http://terrytao.wordpress.com/2013/06/18/a-truncated-elementary-selberg-sieve-of-pintz/