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
where is the function
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 have
where
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
where
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
where
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 2 Let
and
be such that
holds. Let
be an integer, define
and
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
v08ltu
If 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
v08ltu
The 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 Harcos
What 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
v08ltu
The
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 Harcos
Yes, I have now understood this. Thank you!
12 June, 2013 at 1:05 am
Gergely Harcos
This 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 Harcos
Actually 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 Paldi
Can 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 Harcos
12 June, 2013 at 5:43 am
Eytan Paldi
Thanks. Consider now the integral above, denoting
for its lower bound and
for the exponent
.
by
.
, the resulting new bound
should be better then the exponential one since it captures better the integrand behavior for large values of t.
The new upper bound is most simply obtained by replacing in the integrand
Note that for large
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.
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.
Fortunately the above numerical instability can be avoided by using the substitution
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
(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!)
only for EVEN
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 Tao
Thanks 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 Harcos
1. 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
v08ltu
Can 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
v08ltu
It could be that we could almost obtain
, if the upper bound of
were nearly sharp.
12 June, 2013 at 2:10 am
Eytan Paldi
It seems that there is a typo in the summands in (3).
12 June, 2013 at 2:11 am
Gergely Harcos
I mentioned this above (see item #1 in “Some typos”).
12 June, 2013 at 5:13 am
Gergely Harcos
Using 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 Paldi
A suggestion to further optimize
:
is done
It seems that always the minimization of
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.)
from the previous iteration FIXED (in order to keep a GLOBAL optimization at each iteration.)
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
Remark: Note that the current values of
and 
have the same order of magnitude!
12 June, 2013 at 3:05 pm
Gergely Harcos
1. 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 Paldi
Thank you for the data!
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
. (since it involves a small number of trials, I think it worth the effort!)
It follows therefore that for each given
to a new record of
13 June, 2013 at 5:45 am
Eytan Paldi
I’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.)
in
for
(which was quite expected), but the dependence of this ratio on
in
in
for
must be WRONG because
It is easy to see from your data the almost linear dependence of the ratio
on
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 Harcos
I 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 Paldi
But 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 Harcos
There 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 Paldi
It 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 Harcos
The 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
v08ltu
I 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 Paldi
It 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
v08ltu
I agree with this bound.
12 June, 2013 at 9:00 am
Craig Helfgott
I 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 Helfgott
Okay, 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 mathematician
Dear 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
Ghaith
Dear 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 Harcos
Not 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 Goldston
All 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
Pete
Obviously 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 Harcos
Actually 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
Pete
Sure, 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 Harcos
I 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
bengreen
I 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 Harcos
Actually
is now below 250000 :-)
16 June, 2013 at 9:05 am
unknown mathematician
First 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 Bennet
I 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 Harcos
Some 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 Harcos
Actually, in the definition of
, the exponent
should be
. Two occurrences.
[Corrected, thanks – T.]
12 June, 2013 at 11:23 pm
Gergely Harcos
In the definition of
, the denominator should be
instead of
. Two occurrences.
[Corrected, thanks – T.]
13 June, 2013 at 5:00 pm
Non-Mathematician
I 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 Harcos
I 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 Tao
Actually, 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 Harcos
You 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 Harcos
Actually
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 Tao
I’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 Harcos
Sorry 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 Harcos
This 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 Harcos
In practice one can replace
by the clean
14 June, 2013 at 5:51 am
Eytan Paldi
In 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 Harcos
The 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 Tao
Very 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 Paldi
In proposition 1, in both sums n should start with 1 (not 0)
14 June, 2013 at 6:00 am
Gergely Harcos
No 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 Paldi
But
means that there are no integration variables!
14 June, 2013 at 6:33 am
Gergely Harcos
Yes. 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 Paldi
I don’t understand why do you call this empty integral “multiplicative” and the logic behind its definition as 1 (irrespective of its integrand)
summand from the sum (because I don’t think this convention to be a standard one.)
Anyway, for clarification I suggest to separate the
14 June, 2013 at 8:05 am
Terence Tao
The 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.
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
Anonymous
Pintz’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 Paldi
I 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 Paldi
Minor 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 Paldi
In 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 Paldi
A 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 Paldi
In the fifth line above theorem 2, “we see” may be inserted before “that”.
15 June, 2013 at 5:32 pm
Gergely Harcos
This 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
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 Tao
Dear 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 Harcos
You 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 Harcos
Terry 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
As a simple consequence, we shall have
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
Renaming
to
, and
to
, we have reduced the induction step to the already mentioned consequence
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 Harcos
Actually 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 Tao
Perhaps 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 Harcos
You are right about
, let me post a new comment about this below.
16 June, 2013 at 5:53 am
Eytan Paldi
There 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
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:
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 Harcos
For
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 Paldi
In 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 Paldi
Thanks! (I used the equivalent expansions
and
)
18 June, 2013 at 9:03 am
Gergely Harcos
I 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 (https://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
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
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
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 Harcos
Actually this proof gives the stronger statement that I anticipated before:
18 June, 2013 at 9:52 am
Gergely Harcos
Actually, 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 Harcos
The statement I tried to prove here is false, see https://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 Tao
Time to close this thread and move on to the next one:
https://terrytao.wordpress.com/2013/06/18/a-truncated-elementary-selberg-sieve-of-pintz/