This is the tenth thread for the Polymath8b project to obtain new bounds for the quantity

;

the previous thread may be found here.

Numerical progress on these bounds have slowed in recent months, although we have very recently lowered the unconditional bound on from 252 to 246 (see the wiki page for more detailed results). While there may still be scope for further improvement (particularly with respect to bounds for with , which we have not focused on for a while, it looks like we have reached the point of diminishing returns, and it is time to turn to the task of writing up the results.

A draft version of the paper so far may be found here (with the directory of source files here). Currently, the introduction and the sieve-theoretic portions of the paper are written up, although the sieve-theoretic arguments are surprisingly lengthy, and some simplification (or other reorganisation) may well be possible. Other portions of the paper that have not yet been written up include the asymptotic analysis of for large k (leading in particular to results for m=2,3,4,5), and a description of the quadratic programming that is used to estimate for small and medium k. Also we will eventually need an appendix to summarise the material from Polymath8a that we would use to generate various narrow admissible tuples.

One issue here is that our current unconditional bounds on for m=2,3,4,5 rely on a distributional estimate on the primes which we believed to be true in Polymath8a, but never actually worked out (among other things, there was some delicate algebraic geometry issues concerning the vanishing of certain cohomology groups that was never resolved). This issue does not affect the m=1 calculations, which only use the Bombieri-Vinogradov theorem or else assume the generalised Elliott-Halberstam conjecture. As such, we will have to rework the computations for these , given that the task of trying to attain the conjectured distributional estimate on the primes would be a significant amount of work that is rather disjoint from the rest of the Polymath8b writeup. One could simply dust off the old maple code for this (e.g. one could tweak the code here, with the constraint 1080*varpi/13+ 330*delta/13<1 being replaced by 600*varpi/7+180*delta/7<1), but there is also a chance that our asymptotic bounds for (currently given in messy detail here) could be sharpened. I plan to look at this issue fairly soon.

Also, there are a number of smaller observations (e.g. the parity problem barrier that prevents us from ever getting a better bound on than 6) that should also go into the paper at some point; the current outline of the paper as given in the draft is not necessarily comprehensive.

## 121 comments

Comments feed for this article

14 April, 2014 at 2:16 pm

AnonymousWhile I do find these recent breakthroughs incredibly interesting, I am sadly unable to understand the details (yet!). What prerequisites (in terms of classes, e.g “basic understanding of subject X, deep understanding of subject Y) are required to understand the math performed here? In particular, could a (intellectually gifted as any other math undergrad, but still mortal) hope to grasp it? I am looking through a lot of math I don’t really understand yet in hope that “listening to the music while not grasping the lyrics” will eventually pay off, but I feel myself growing a bit impatient. (This might be better suited in some career-advice page, but hey, what’s a comment-field without at least one poster going off-topic?)

14 April, 2014 at 2:18 pm

AnonymousThat is supposed to read “could an undergraduate…”

14 April, 2014 at 3:21 pm

Terence TaoOne could start by having a look at Andrew Granville’s recent survey article http://www.dms.umontreal.ca/~andrew/CEBBrochureFinal.pdf , which starts out fairly gently. But if you haven’t seen, for instance, a proof of the prime number theorem (or, at bare minimum, Mertens’ theorem), it is probably going to be somewhat rough going once one plunges into the details. (The sieve-theoretic aspects of the argument are elementary, and one could in principle understand these aspects at least if one is willing to accept certain estimates (e.g. the Bombieri-Vinogradov theorem) as a black box, but my feeling is that one will not really appreciate what is going on if one solely focuses on the sieve theory.)

14 April, 2014 at 2:26 pm

Will SawinDo you have written up somewhere exactly what cohomology vanishing statements (or exponential sum bounds) you need to check?

14 April, 2014 at 3:14 pm

Terence TaoYes, this was briefly stated in http://terrytao.wordpress.com/2013/09/22/polymath8-writing-the-paper-iii/#comment-247146 and I can reproduce it here.

Let be generic elements of for some large prime p. Form the rational function

and then the Kloosterman-type sum

where is a primitive character (and we delete the bounded number of values of for which is infinite). Weil tells us that this is a bounded function (it corresponds to a lisse sheaf with vanishing H^0). By some ad hoc calculations using the sheaf-theoretic Fourier transform, we can also get cancellation for the sums

namely that for any non-zero l; see Theorem 8.17 of Polymath8a.

But now we need one more round of cancellation, to show that the expression

is also O(1) for any . This expands out to an exponential sum in four variables for which the associated sheaf needs to be middle-extension; this should certainly be true, but we don’t have a systematic way to approach the problem.

18 April, 2014 at 6:32 am

Philippe MichelHi Terry,

This has been a little while… I have only loosely followed Polymath8b so farbut I was pursuing other projects (with the same usual suspects). One good thing is that we have gained experience further on handling further exponential sums together with new applications not totally unrelated to polymath8. Maybe the moment is ripe for thinking again on improving further the level of distribution of the primes over smooth and not so smooth moduli (maybe a polymath8c ?) which could be further discussed while everybody is at IHES.

Anyway here is the answer to the above problem (I will write the details into the adequate file of polymath8b wherever you tell me):

this is again the fourier transform trick (which after all is maybe not so “ad-hoc”)

one needs to show that does not contain a quadratic phase ; by the criterion of polymath8a it is sufficient to look at the Fourier transform but is an additive convolution of K_f with the conjugate of itself and therefore its fourier transform is the product of the fourier transform and its complex congugate (and the sheaf Fourier transform of the sheaf associated to is the tensor product of the the FT of and its dual). Again from polymath8a we know is a pullback of a Kloosterman sheaf which is irreducible with known geometric monodromy group (SL_3) it follow that decompose as the trivial representation and an 8-dim irreducible representation (the decomposition of the End representation of SL_3).

This type argument shows that above “quadratic phase” can be replaced by any polynomial phase (with some small care for polynomials of degree 9, whose FT yield an irred 8-dim sheaf but the infinity representation differentiate the two). Therefore it is likely that further games can be played…

see you in Cambridge soon !

Philippe

18 April, 2014 at 8:11 am

Terence TaoGreat news! From your description it sounds like we could squeeze a proof of our tentative MPZ estimate into a technical “Appendix B” for the Polymath8b paper, which would cite heavily from Polymath8a but would otherwise contain all the required details. In that case, it may not be so urgent to redo the m=2,3,4,5 computations with the weaker MPZ estimate (though having both of the numbers out there would be a nice numerical illustration of the gain that the new estimate gives).

In other news, I’ve almost finished transcribing the M_k asymptotics from the wiki to the paper. Unfortunately I remember now why it is difficult to extend these arguments to M_{k,eps} (and thus to get better bounds using GEH instead of EH, or to improve the unconditional bounds slightly): the bounds from M_k come from carefully estimating the defect in the upper bound . We do have upper bounds for , but they are nowhere near as tight as the bound, so the defect is much larger and we lose a lot more when trying to estimate it.

Once I’m done transcribing that section, I’ll try to work on “Appendix B”, in particular citing my way through Polymath8a to reduce the MPZ estimate to the exponential sum estimate, which I think I will then turn over to you to fill in. :)

19 April, 2014 at 7:07 am

Terence TaoI’ve been going through the exponential sum/ advanced type I parts of Polymath8a again, and realise that the exponential sum estimate we really need is actually slightly different, because we’re not applying two 1-dimensional van der Corput’s one after another, but are instead applying a single two-dimensional van der Corput. The more precise statement we need is that for “generic” , if we write for the Kloosterman-type sum

then for “generic” shifts (a,b), we have

for any . This should reduce to an assertion to the effect that does not contain a quadratic phase along any (generic) line, but because we now have a 2D exponential sum instead of a 1D exponential sum (and need Deligne-level cancellation rather than Weil-level) I’m not sure how to encode this into the 1D sheaf language properly.

EDIT: In a little more detail, the objective is to obtain a “2D van der Corput” exponential sum estimate of the form

when and (actually the main region is when ). One can try doing two separate 1D van der Corputs to get this bound, but one ends up with something weaker when one does so; it seems that it is only the 2D van der Corput (in which one shifts (l,d) by a 2D vector (a,b)) that gives the best results here, but then we need 2D Deligne type bounds.

21 April, 2014 at 8:07 am

Terence TaoA little more detail on the precise issue. There are a number of ways to estimate a sum of the form

assuming that all the completed sums involving exhibit square root cancellation, and that .

For instance, we have a trivial bound of , while simultaneous completion of sums gives the dual bound . q-van der Corput in d and triangle inequality in l gives an upper bound of

(1)

whenever , which is what Polymath8a is using. Ideally, a simultaneous q-van der Corput in (d,l) should be available, giving the bound of

(2)

but this requires square root cancellation for a certain two-dimensional sum involving K as in the previous comment, and I don’t see how to get this from 1D trace weight technology. More feasible (and pretty much solved by Phillipe’s previous comment) is to first van der Corput in d, giving an intermediate bound of the form

where . The term contributes , and the terms contribute if one just uses completion of sums in the d aspect; but if one applies a second van der Corput in the l sum also, then one arrives at a bound of

(3)

which is a little better than (1) but not as good as (2), and would ultimately lead to a value of intermediate between 6/700 and 13/1080 (I haven’t checked exactly what we get though).

So it’s a little unclear exactly what we can hope to get right now, because it hinges on whether we can get squareroot cancellation for the complicated sum

14 April, 2014 at 2:28 pm

Andrew V. SutherlandI can help assemble the material for Appendix A. There are actually a couple of additional tricks I used to more efficiently construct narrow admissible tuples for some of the larger values of k needed to get bounds for m=2,3,4,5.

But it probably makes sense to wait to finalize this until after we have settled on the exact values of k we want to use for these m.

14 April, 2014 at 5:59 pm

David RobertsCongratulations to all involved. I think this project has been an excellent opportunity to publicise the ongoing work of mathematicians, and the human, interactive element of what we do.

15 April, 2014 at 1:16 am

AnonymousThere’s a typo in the definition of \(H_m\): \(p_m\) should’ve been \(p_n\).

[Corrected, thanks – T.]15 April, 2014 at 3:04 am

Eytan PaldiIs it possible to find an explicit (numerical) upper bound on the constant implied by the O-term in theorem 1.4(vi)?

17 April, 2014 at 9:26 am

Terence TaoYes, this is in principle possible by working through the calculations at http://michaelnielsen.org/polymath1/index.php?title=Selberg_sieve_variational_problem#Asymptotic_analysis with explicit choices of parameters. I plan to spend some time today revisiting the computations here and seeing if it can be done more cleanly and efficiently; the current calculations are quite a mess and far from optimal, I think.

16 April, 2014 at 12:57 am

Andrew V. SutherlandI added Bounded gaps between primes with a given primitive root” to the wiki.

16 April, 2014 at 5:44 pm

xfxieI will find some time to compute k values for 600*varpi/7+180*delta/7<1 in a few days.

17 April, 2014 at 10:43 am

DanielCongratulations on the project. Excellent their work to the benefit of us who like the world of mathematics. A greeting.

17 April, 2014 at 1:26 pm

xfxieHere are the k0 values (under the constraint 600*varpi/7+180*delta/7<1):

k0=35410 for m=2

k0=1649821 for m=3

k0=75845707 for m=4

k0=3473955908 for m=5

17 April, 2014 at 4:16 pm

Terence TaoFor sake of comparison, now that Gergely has observed that James’ bound is valid for all k, this gives a criterion for whenever , but this gives significantly worse numerology (k ~ 527751 for m=2, for instance).

28 April, 2014 at 3:00 pm

Aubrey de GreyTerry, how did you get 527751 here? It seems to me that k=515738 is the minimum possible.

Less trivially (I hope): what is the obstacle to refining this bound using MPZ technology, i.e. to replacing 4m by 1080m/283 (giving, e.g., k=334989 for m=2)?

29 April, 2014 at 6:48 am

Terence TaoSorry, I meant to say 5277510 here (note we are working with m=1 rather than m=2): https://www.wolframalpha.com/input/?i=solve+ln%28x%29-2*ln%28ln%28x%29%29-2%3D8

One could probably get some bound like this using MPZ if one went through the argument in Maynard’s paper carefully, but it would probably not beat the bound k=395106 that we currently have.

17 April, 2014 at 1:50 pm

Aubrey de GreyWhat can be said at this point about the possibility of obtaining better values of H_m assuming GEH versus EH for values of m greater than 1? Since the paper will give such prominence to the achievement of H_1 = 6 assuming GEH versus only 12 assuming only EH, it seems that readers will be quite interested in whether similarly substantial differences arise for H_2 etc.

Also, while writing: this thread is not yet linked-to from http://michaelnielsen.org/polymath1/index.php?title=Bounded_gaps_between_primes .

17 April, 2014 at 2:19 pm

Terence TaoLink added, thanks.

Regarding GEH vs EH, it is true that the epsilon trick becomes available when GEH is assumed; however, in that setting there is an additional constraint which has never been important in the small k cases, but becomes so for larger k. For instance, Pace's recent bound gave us , but does not directly bound on GEH because the epsilon choice is too large. Presumably one could split the difference and work with some choice like and improve the EH bound on a little bit on GEH, but I don't know how long that would take to compute. There is some parallel gain for the larger values of k in the asymptotic analysis of to be had also, though my feeling is that the gain is somewhat modest.

I'm starting to write up the asymptotic analysis of M_k section, and I'll look out to see if there is some easy way to work in the epsilon trick, which would also improve the non-EH bounds.

17 April, 2014 at 2:49 pm

Andrew V. SutherlandPreliminary H values for the k0 values posted by xfxie above:

m=2, k0=35,410, H=398,646

m=3, k0=1,649,821, H=25,816,462

m=4, k0=75,845,707, H=1,541,858,666

m=5, k0=3,473,955,908, H=84,449,123,072

I just kicked off computations to further optimize these, but this will take some time.

18 April, 2014 at 9:27 am

Andrew V. SutherlandSome improved bounds:

m=2, k0=35,410, H=398,244

m=3, k0=1,649,821, H=24,798,306

m=4, k0=75,845,707, H=1,541,183,756

m=5, k0=3,473,955,908, H=84,499,103,908

The admissible tuple for m=4 is obtained by taking k0 consecutive primes starting with p_4223718=71,910,101.

The admissible tuple for m=5 is obtained by taking k0 consecutive primes starting with p_166088916=3,473,846,231.

19 April, 2014 at 8:53 am

interested non-expertYour “improved” value of m=5 is bigger than the original one. I guess there is a typo in either “84,449,123,072” or “84,499,103,908”. (see 8th digit 4 vs. 9)

19 April, 2014 at 9:51 am

Andrew V. SutherlandYou are right there is a typo, the improved value should be 84,449,103,908, thanks for catching this.

28 April, 2014 at 8:23 am

Andrew V. SutherlandFurther improvements for the values of k0 obtained by xfxie under the constraint 600*varpi/7+180*delta/7 < 1.

m=2, k0=35,410, H=398,130.

m=3, k0=1,649,821, H=24,797,814.

m=4, k0=75,845,707, H=1,526,698,470=p_1533587021-p_6888551.

m=5, k0=3,473,955,908, H=83,833,839,882=p_3487335728-p_13379821.

The last two bounds were obtained using a cache-friendly omp-based implementation of the admissiblity testing algorithm described in Section 3.1 of the Polymath8a paper that has been optimized to treat sequences of consecutive primes. I’ll post the source code to the wiki later today (possibly tomorrow).

28 April, 2014 at 9:20 am

Aubrey de GreyThose are quite big improvements! Is it worth also running your new code on the 1080/13 constraint? – do you think there is more to be squeezed there in acceptable running times?

28 April, 2014 at 9:23 am

Andrew V. SutherlandYes, in fact the computations are running now. I should have some results tomorrow.

29 April, 2014 at 5:14 pm

Andrew V. SutherlandFast multi-threaded code that can be used to verify large tuples of consecutive primes has been posted to the wiki and is also available here.

In the process of testing I found that the code was being a bit too pessimistic in its search for an optimal choice of n <= k0 for which the tuple p_{n+1},…,p_{n+k0} is admissible. Fixing this yielded a slightly better result for the m=5, k0=3,473,955,908 case. Using n=13379818 gives a diameter of

H=83,833,839,848.

For anyone who wants to verify the m=4,5 results, compile the code at the link above on a 64-bit linux box and run

zhangverify 75845707 469552

zhangverify 3473955908 13379818

The first case takes about a minute on a 24 core Intel Xeon E5-2697v2@2.7GHz, while the second case takes about 5 hours (for comparison, verifying the largest case k0=3,500,000, n=33,639 listed in the benchmarks table takes less than a second).

I am now re-running computations for some of the larger k-values in the current records table that I started yesterday. I should have the results tomorrow morning.

18 April, 2014 at 1:19 pm

Eytan PaldiIt seems that in the DHL sufficient condition below theorem 3.11, it should be “" (instead of "")

[Corrected, thanks – T.]19 April, 2014 at 2:20 pm

Eytan PaldiIn the RHS of (6.4), it should be

[Corrected, thanks – T.]20 April, 2014 at 12:58 pm

Eytan PaldiIn theorem 3.2(vi), the fraction in the exponent should be updated (and also in the last inequality below theorem 3.11).

[Corrected, thanks – T.]23 April, 2014 at 3:47 am

Eytan PaldiThere is an extra “-” (in both places).

[Corrected, thanks – T.]23 April, 2014 at 8:53 pm

AnonymousAbstract, l. 1 + Intro., l. 2: Parentheses around .

[Parentheses added – T.]21 April, 2014 at 3:18 am

einsteinsHi,I love all professores of this project.I am sure 100% with current speed, all you prove H=2 within August.2014.I do not joke

21 April, 2014 at 9:08 am

James MaynardI’ve had a first read-through of the sieving sections and in general it all looks good. I’m still going through it slowly (playing with a separate tex file), but this will likely take me a little while.

A couple of minor thoughts on possible `streamlining’ modifications (although these would only save a few lines at best):

1. If we modified Lemma 4.1 to also have the coprime to a fixed integer (this is a trivial change), then we could use a Selberg upper bound instead of the large sieve argument on page 23 to bound . This would have the advantage that we could essentially quote the result straight from Lemma 4.1, possibly saving some space.

2. To establish (4.16), I think we can just pass straight to an Euler product upper bound (taking into account prime powers ) since everything is multiplicative and non-negative.

3. (This is more of an observation) I think the convergence of the is assured by Cauchy-Schwarz and the bound from Proposition 4.2 (this shows , and the are increasing for the case .

One very minor thing: I just wanted to check I followed the argument correctly. For the bound for at the top of page 31, I had something like instead of (obviously this would work fine for the subsequent bound). Did I make a mistake?

James

21 April, 2014 at 11:05 am

Terence Tao1. Ah, I see, yes, that would work, and would be conceptually simpler in that we then use the Selberg sieve exclusively for our sieve upper bounds and asymptotics. (Of course, the large sieve and Selberg sieve are very closely related in any case, but this would also make the paper more self-contained.)

2. Yes, this seems to work; I’m surprised I missed that and went for the more complicated combinatorial approach instead, but I think I was overly nervous about the non-squarefree contribution.

3. Yes, this can be inserted as a remark. I still feel there should be some more conceptual proof of the computation of the limit of c”_eps than what is given in the notes, though.

Finally – yes, you’re right, I had the wrong expression here (and on the next display).

I am not working currently on these sections, planning to look instead at the appendix on Type I estimates. Do you plan to edit in the changes you have found (there are also a lot of other typos and bad formatting to clean up, it is a zeroth draft right now)? Otherwise I can try to work in your comments (and do some other cleanup).

21 April, 2014 at 12:20 pm

James MaynardI’m planning on going through the section carefully to try to pick up most minor typos etc. I guess its easiest if I add in the above changes to the dropbox tex file when I make the other changes, and leave you to look at the other sections.

21 April, 2014 at 12:23 pm

James Maynard(I also keep on thinking there should be an `obvious’ approach for the integral identities, or maybe bootstrapping the fact we know it holds for F of small support, but I haven’t seen it. At least the current approach isnt too bad – the original sketch I had which was a horrendous mess)

21 April, 2014 at 12:28 pm

Terence TaoOK, I won’t touch these sections until you’re done with them then.

I had an idea to try to prove the identities by first working in the case when F is a finite combination of exponential functions in which case things are rather explicit, but in order to take the limit and arrive at general F, I needed to reproduce a large chunk of the machinery already in the paper to justify passage to the limit. Perhaps we can pose as an open problem the task of finding a more conceptual proof of these identities in the general case.

22 April, 2014 at 1:21 am

Andrew V. SutherlandI added On limit points of the sequence of normalized prime gaps to the wiki.

22 April, 2014 at 5:09 am

OMFNot to sound like a philistine, but when writing up the paper, I think some kind of “greater context” interpretation of the result is warranted. I say this because, since the methods used are fairly accessable, and the more advanced methods may end up being simplified over the years, future generations may end up considering bounded gaps as a standard fact about primes. So the paper should have a section explaining what mathematicians concepts of primes numbers were like before this result, and how the result changed them.

22 April, 2014 at 8:21 am

Gergely HarcosIn the recent preprint by Banks-Freiberg-Maynard (http://arxiv.org/abs/1404.5094) equation (4.4) says that , and that this result was derived as part of this PolyMath project. Where can I find the proof? I am only aware of the bound .

22 April, 2014 at 8:30 am

Gergely HarcosI see, this bound is part of Theorem 3.9 in the draft paper.

23 April, 2014 at 3:35 am

Eytan PaldiIn the assumption for theorem 3.2(xii), it should be GEH (instead of EH).

[Corrected, thanks – T.]24 April, 2014 at 1:35 am

Eytan PaldiIn the asymptotic analysis (below the proof of theorem 6.5), in the last integral estimate of , it seems clearer to replace in the integrand denominator by .

24 April, 2014 at 6:25 am

Eytan PaldiPerhaps it is even better to represent as the current integral (with in the integrand denominator) + o(1) (i.e. the current integral is the large k asymptotic of ).

[Corrected, thanks – T.]26 April, 2014 at 10:35 am

Terence TaoAs the situation with the exponential sums (and hence, the best bounds for k and H for m=2,3,4,5) are still in flux (but Phillipe tells me he is going to meet with Emmanuel Kowalski and Paul Nelson soon to try to sort things out), I’m starting to work on other sections that are not directly impacted by this issue. I’ve written up a brief section on the parity problem obstruction, and now plan to write on the M_k bounds for k=3,4,50,53, and trying to glue in what Pace and Ignace have written on these topics.

On a separate point: I’ve received an offer from Ken Ono to submit this forthcoming Polymath paper to a new open access journal that he is editor of, Research in the Mathematical Sciences http://www.resmathsci.com/ . Another option would be to submit to the same journal (Algebra & Number Theory) that Polymath8a was submitted to (but the refereeing process for that journal is not concluded yet). In any event, we are still many weeks away from having a submittable form of the paper, so there is no urgency to decide yet where to send it.

27 April, 2014 at 6:19 pm

David RobertsMy goodness, why on earth does Springer ask for ridiculous formatting constraints on articles submitted to RitMS? And the section headings? And the totally insane detailed referencing style commandments? Someone didn’t check that mathematics articles aren’t the same as articles in experimental sciences. (rant over)

On a less hysterical note, the style of the journal appears to be such that (sub)sections aren’t numbered. This is a backwards step in my opinion. But I’m not in a position to make this decision, but I applaud the option of an open access journal.

26 April, 2014 at 9:18 pm

James MaynardI’ve modified introduction.tex, subtheorems.tex and sieving.tex in the dropbox folder.

I’ve made a number of very minor changes alongside the variations we already talked about. Most of these are just slight rewording or reformatting or correcting a typo. Anything where I’ve tried to make a slightly more significant change I’ve marked with a comment of the form %%JM. Of course, many of these are based on my subjective preferences and anyone is completely free to change anything if they prefer to present it in a different way.

I’m away next week, but the week after I should be free to start going through the later sections which are written up.

27 April, 2014 at 2:17 am

Eytan PaldiThe “” in (6.15) should be in (6.14).

[Corrected, thanks – T.]27 April, 2014 at 8:29 am

Eytan PaldiIt seems that certain formula numbering in the following text should be updated.

29 April, 2014 at 11:30 am

Eytan PaldiMore precisely, it seems that (because of the above correction) in each reference (in the text) to an equation below (6.14), its number should be shifted backward by 1.

28 April, 2014 at 1:48 am

AnonymousTypographical comments to the paper:

(1) One should use “\colon” instead of “:” in maps to get the correct horizontal spacing. (Example: .)

(2) One should use “\coloneqq” from the mathtools package instead of “:=” in definitions to avoid bad linebreak among other things.

29 April, 2014 at 4:57 am

Eytan PaldiOn the monotonicity of :

Let . Define on by

(1)

where , and

(2)

It follows that for

(3)

Since , summation over gives

(4)

It is easy to verify that

(5)

By taking for , the ratio between the integrals in (4), (5) tends to 1 as tends to 0. Implying

(6)

Hence (by taking the supremum over )

(7)

29 April, 2014 at 6:01 am

Eytan PaldiCorrection: the RHS of (6) should be multiplied by

(which is the ratio between the integrals in (4), (5)).

So (7) follows by both taking the supremum over , and letting tend to 0.

1 May, 2014 at 5:25 am

Andrew V. SutherlandUsing the new code for fast admissibility testing (available on the wiki), I was able to improve three of the bounds in the current records table.

Under the 1080/13*varpi+330/13*delta < 1 constraint we have:

m=5, k0=3,400,000,000, H=81,973,172,502.

The bound on H uses the tuple p_{n+1},…,p_{n+k0} with n=13,179,173.

Under the Deligne-free 168*varpi+48*delta < 1 constraint we have:

m=4, k0=105,754,838, H=2,165,674,446;

m=5, k0=5,300,000,000, H=130,235,143,908.

Here the bounds on H use the tuple p_{n+1},…,p_{n+k0} with n=623,411 and n=19,662,782, respectively. To verify these result, compile the fast admissibility testing code and run

zhangverify 3400000000 13179173

zhangverify 105754838 623411

zhangverify 5300000000 19662782

1 May, 2014 at 7:39 am

Aubrey de GreyI’m unclear as to how the values for k are being optimised for m greater than 1. In the Maple code, how are you and xfxie finding the best values for c and T ? – does the end result vary smoothly enough that simple interpolation suffices? Also, in the expression that defines g, should the “t” actually be “T” ? (Not knowing or having Maple I don’t know whether case matters, but it seems worth asking!)

1 May, 2014 at 8:16 am

Andrew V. SutherlandMaple is case sensitive. The lower case t in the definition of g is a symbolic variable that is being integrated over the interval [0,T], as in the script Terry originally posted (so g=g(t) is really a function of t).

The values of k0 I obtained were found by sampling a grid of (c,T) values — interpolating didn’t seem to work that well, the bounds do not vary as smoothly as one might like. But xfxie may be doing something more clever than this.

Certainly the m=5 bounds k0=3400000000 and the Deligne-free k0=5300000000 can be improved, and I suspect there is still room for improvement in some of the others.

1 May, 2014 at 8:22 am

Aubrey de GreyMany thanks Drew. I see now – g is basically a macro that is expanded in the subsequent lines.

3 May, 2014 at 8:21 pm

Aubrey de GreyI just reimplemented Terry’s k-validating Maple script in Mathematica and embedded it in a fairly naive hill-climbing algorithm, so as to get good values for m=5, and I checked all other cases too. I think my only other improvements over already-determined values are for m=2, 3 and 4 with no Deligne, on which I don’t think xfxie ever reported. All values reported by xfxie are the same as I get – which I guess constitutes not only validation, but also circumstantial evidence that there are probably no other values of c and T that allow smaller k. Since the previous reports are scattered over so many posts, here is a full tabulation:

1080/13, 330/13 (provisional, unconditional, Deligne)

m=2: 35146

3: 1628943

4: 74487363

5: 3393468735 with c=0.04593783, T=0.0340499

600/7, 180/7 (confirmed, unconditional, Deligne)

m=2: 35410

3: 1649821

4: 75845707

5: 3473955908

168, 48 (confirmed, unconditional, no Deligne)

m=2: 41697 with c=0.0935, T=0.08025 (eclipsed by 41588 from m=4[EH])

3: 2113163 with c=0.06893, T=0.05518

4: 105754479 with c=0.0544852, T=0.04183

5: 5274206963 with c=0.0450055, T=0.0336093

4, 0 (confirmed, conditional on EH)

m=2: 698 (eclipsed by other methods, obviously)

3: 5511

4: 41588

5: 309661

4 May, 2014 at 12:37 pm

Andrew V. SutherlandThanks for this Aubrey. Here are H bounds corresponding to your improved k0 values:

provisional, unconditional, Deligne:

m=5, k0=3,393,468,735, H=79,929,339,154

confirmed, unconditional, no Deligne:

m=3, k0=2,113,163, H=32,588,668

m=4, k0=105,754,479, H=2,111,597,632

m=5, k0=5,274,206,963, H=126,630,432,986

The bounds for m > 3 all correspond to Hensley-Richards tuples. They can be verified using:

hrverify 105754479 659165

hrverify 3393468735 13773747

hrverify 5274206963 20369534

[Results added, though it seemed the k=3 results do not improve upon your previous result at http://terrytao.wordpress.com/2013/12/20/polymath8b-iv-enlarging-the-sieve-support-more-efficient-numerics-and-explicit-asymptotics/#comment-258810 ]4 May, 2014 at 1:10 pm

Aubrey de GreyThanks back! Out of interest, what is your current assessment of the prospects for going beyond Hensley-Richards for the larger values of k?

4 May, 2014 at 2:31 pm

Andrew V. SutherlandIt should be feasible to do an asymmetric version of Hensley-Richards, although I suspect the gain will be fairly small. If I have time I’ll try to take a look at this next week.

5 May, 2014 at 8:25 am

Aubrey de GreyTerry: is there any straightforward option for further tightening the derivation of lower bounds for M_k that your Maple script implements? I ask mainly because my (and probably xfxie’s) technology for finding the minimal k seems to be fast enough to justify experimenting with more complex computations, in the event that any steps in your current derivation exist just for simplicity.

6 May, 2014 at 7:33 am

Terence TaoThere is some room to make some small improvements in this regard, although it would only affect the m=2,3,4,5 bounds and not the m=1 bound, so it has not been a priority thus far (and also I suspect that there may be a completely different way to generate lower bounds for M_k that may be significantly more efficient). I’m somewhat busy this week, but I’ll try to revisit that part of the paper and see if there are any “cheap” improvements that don’t require significant additional justification.

Incidentally, there was some issue with previous dropbox links to the paper, so I’ve generated a fresh one at https://www.dropbox.com/sh/0xb4xrsx4qmua7u/tfwv3_O_WY/Polymath8b/newergap.pdf (with directory at https://www.dropbox.com/sh/0xb4xrsx4qmua7u/WOhuo2Gx7f/Polymath8b ).

5 May, 2014 at 9:23 am

Andrew V. SutherlandHere is a better tuple for the m=3 unconditional no-Deligne case:

m=3, k0=2,113,163, H=32,285,928.

2 May, 2014 at 10:55 am

Andrew V. SutherlandI just posted updated fast admissibility testing code to the wiki that now handles Hensley-Richards tuples

This yields improved bounds on H for all the m=4,5 cases.

Under the 1080/13*varpi+330/13*delta < 1 constraint we now have

m=4, k0=74,487,363, H=1,460,493,420

m=5, k0=3,400,000,000, H=80,088,836,006

Under the weaker 600/7*varpi+180/7*delta < 1 constraint we get

m=4, k0=75,845,707, H=1,488,227,220

m=5, k0=3,473,955,908, H=81,912,638,914

Under the Deligne-free 168*varpi+48*delta < 1 constraint we get

m=4, k0=105,754,838, H=2,111,605,786

m=5, k0=5,300,000,000, H=127,277,395,046

To verify the above results, compile the fast admissibility testing code and then use

hrverify 74487363 492570

hrverify 75845707 492570

hrverify 105754838 659165

hrverify 3400000000 13773747

hrverify 3473955908 14132283

hrverify 5300000000 20479497

3 May, 2014 at 12:36 pm

Terence TaoI was working on Section 7.1 (lower bounds on for medium k, such as k=50 and k=54 and realised that I don’t fully understand how the integrals

(*)

and also the more complicated

(**)

are computed numerically when the are functions of the form for some signature consisting of even exponents. (Firstly, just to clarify: is the sum of all distinct monomials which are permutations of ?) There is a beta function identity to integrate pure monomials (Lemma 7.2 in the current draft), is the idea just to decompose into pure monomials?

I was thinking about a possible alternate approach to and (but I’ll focus here on for simplicity), in which one works with of the form where are the sum of the d^th powers. The point here is that multiplication is very easy, and (for the sum (*) at least) one is reduced to computing integrals of the form

The integrand has total degree , and so one can also rewrite this as

which one can also write as

If d is relatively small, say d=10, then perhaps we can compute enough terms of the Taylor series of in , and then raise to the power to extract all the relevant structure constants. But I’m not sure if this is much of a speedup over the existing methods (I’m a bit unclear as to what the bottleneck is.)

3 May, 2014 at 2:25 pm

Pace NielsenFirst, yes, is the sum of all distinct monomials which are permutations of where .

Second, again yes, the idea is to just get a pure monomial (possibly with a factor of attached) in order to apply the beta function identity.

Third, finding the relevant structure constants for a simple product is now very fast, and is not a bottleneck.

The current bottleneck is actually using the beta-function identity, after first integrating out one variable and squaring (i.e. finding the integrals in the more complicated case) to compute (the exact) rational entries for one of the large matrices corresponding to the quadratic form. It may be the case that this could be sped up. I haven’t taken a look at the code for a while now.

I have not checked exactly which step is the slowest, but my impression was it occurs when adding a whole bunch of relatively large rational numbers together during the matrix formation stage. [When we apply the beta function identity, after integrating and squaring, there are sometimes a lot of terms, with very big and distinct denominators.] I’ll try to double-check this on Monday (and I wouldn’t mind anyone else taking a look at the code if they have the time).

3 May, 2014 at 6:14 pm

Terence TaoThat clarifies things, thanks!

6 May, 2014 at 2:45 am

Eytan PaldiIt should be remarked that the two matrices needed for

computation may be computed using symbolic (since their elements are polynomials in ).

So they have a representation of the form

(1)

with computable matrices .

Therefore (using the above matrix representation), there is no need to repeat the numerical computation of the two matrices for each (during optimization).

Remark: it may be easier to compute a representation of the form

(2)

with appropriate (computable) matrices .

9 May, 2014 at 7:05 am

Ignace BogaertHi, I just wanted to point out that the type of symmetric polynomials discussed above:

was also used (inspired by the comments on this blog) in my calculations for . The integrals that one encounters

were computed as explicit functions of , by means of a recurrence formula between the various integrals. Now, in my code, the integrals were all recursively computed and stored, which eventually led to very high memory requirements (each integral was a polynomial in ). Perhaps your neat trick with the Taylor series can help in this regard, by recursively computing the integrals for specific . Storing values instead of polynomials should require less memory and may allow a somewhat higher degree than my code currently does.

I also have a question: has anyone constructed the eigenfunction (analytically, if possible) that realizes the maximal value for ? For , this function and its associated eigenvalue are known, but I have been unable to find a similar result for nonzero …

Edit: I have not yet sought very hard for this eigenfunction, I just did not immediately find it on this blog.

9 May, 2014 at 11:09 am

Terence TaoThanks for the remark! As far as I am aware the eigenfunction for has not been computed. Eytan has some calculations for the analogue of when the function F is of the one-dimensional form , but these do not come close to optimising when is not constrained to be one-dimensional in nature.

9 May, 2014 at 11:42 am

Ignace BogaertThanks back! I may try and look into that, for use as a test case for the numerical equivalent.

16 May, 2014 at 12:35 am

Ignace BogaertI have now done some analytical calculations for the eigenfunction associated with (I do hope I did not make any obvious mistakes). It turns out that the calculations do not become more difficult, but just more involved. You can find it at the following link: http://users.ugent.be/~ibogaert/KrylovMk/M2eps.pdf

16 May, 2014 at 11:52 am

Eytan PaldiThis very interesting solution has the properties:

1. For each , is analytic on

– implying that the eigenfunction is real analytic on its support, except on the jump singularities on the intersection of the lines and with support.

2. The threshold is probably related to the same threshold above which has a reduced support (i.e. vanishes on a certain inner triangle ).

16 May, 2014 at 1:56 pm

Terence TaoVery nice! I’ve added a summary of your results to Section 6 of the draft paper. I’m going through the paper now to try to clean it up and move it closer to a publishable state; hopefully I can be done in a few days (modulo some remaining gaps, such as Appendix A) and then I will roll over the thread.

9 May, 2014 at 12:25 pm

Eytan PaldiIn a previous comment, it was remarked that any optimal function for the value must vanish on a certain inner simplex (defined by ) of – since the functionals do not(!) depend on the function values on this inner simplex.

Therefore, any such optimal can’t be real-analytic (and in particular polynomial) over the whole simplex .

This explains why the convergence to is very slow by using polynomials (which do not vanish on this inner simplex as the optimal function does.)

10 May, 2014 at 12:30 pm

Eytan PaldiThis gives the following generalization of Ignace polynomial basis method for the case of computation:

Let and

where denotes the inner simplex above (on which the optimal should vanish). Clearly, is the intersection of half-spaces defined by

and an additional half-space defined by and

i.e. in terms of the new variables , the set is the simplex – showing that the simplex is empty(!) for .

So the integral over should be easy (using also the constant Jacobian of the transformation to the variables .)

10 May, 2014 at 2:03 pm

Eytan PaldiIt seems that the same problem appeared again (the same(!)s lines in the middle of my last comment above were deleted again). So I’ll try here to give them:

1. In line 8, after “… and an additional half-space defined by”, it should be

, and

2. The last five lines in my comment above (starting with "i.e. in terms of …) should remain.

[

Unfortunately I can’t recover the text between and 0. Use < and > instead of < and > to avoid text between < and > from being interpreted as HTML. Or, email me the relevant text and I will paste it in. – T.]10 May, 2014 at 2:54 pm

Eytan PaldiThe problem appeared again! it seems to be a latex problem, so I’ll try to concentrate on the main points:

1. Since the optimal is supported on , the basic idea is to approximate by polynomials supported on . i.e approximating by where is a polynomial.

2. The important observation is that for functions supported on we have

In particular, it follows that repeated applications of this operator (starting with – as in Ignace method) generate a sequence of polynomials supported on and converging to the optimal . This is the desired generalization of Ignace method for computation!

3. The needed inner products should be now on (instead of ) and can be computed for polynomials

by

So we need only to compute integrals of polynomials over – which can be done efficiently using the new variables

In terms of the new variables the simplex is given as in the above comment (note that is empty(!) for

) so the integration of polynomials over can be done efficiently (using the constant Jacobian of the transformation).

11 May, 2014 at 11:51 am

Eytan PaldiLet defined as in my comment above. It is easy to verify that for each function supported on , it follows that is supported on (i.e. vanishes on the inner simplex ) which is not surprising (since repeated application of this operator should converge to the optimal which is supported on ). But now it seems to me that the the simplified representation of this operator for functions supported on , as claimed in my comment above, may be wrong!

Therefore, unfortunately, the basis functions generated by this operator can be piecewise polynomials (not necessarily polynomials over – as claimed in my comment above.)

But we can still improve the current lower bounds for by working with polynomials supported on , so the denominator functional for a polynomial should be

which is smaller(!) than the current denominator

As remarked in my comment above, the elements of the matrix representing the new denominator can be computed efficiently.

12 May, 2014 at 1:22 am

Ignace BogaertThanks, Eytan, for all your thoughts on this. Indeed, it seems that any polynomial is quickly turned into a piecewise polynomial by the repeated application of . The integration in produces a piecewise function with its pieces differing from the original one $1_{R’}$. After summing over , the function is no longer analytic times , which is quite unfortunate…

I think your point about the denominator is an excellent one. Perhaps this will allow the further lowering of , without necessarily increasing the degree of the polynomial basis.

12 May, 2014 at 11:59 am

Eytan PaldiThanks for your response!

In fact, I think that the polynomial convergence rate in to the optimal function should depend strongly on the types of possible singularities of inside .

Since (i.e. the inner simplex is empty) exactly for , it seems that the current method should converge much faster for such values than for values above the threshold .

This assumption on the dependence of the convergence rate on the values of , if numerically confirmed, should indicate that the presence of the inner simplex is the main obstruction for fast convergence of the current method (without denominator modification).

3 May, 2014 at 9:18 pm

Aubrey de GreyThere was some interest a while back in finding the simplest set of polynomials that would give M_3>2 under GEH using the partitioned half-cube. At that time I posted a set that aimed to minimise the number of monomials (81), but perhaps a more intuitive measure is to minimise the absolute value of the largest coefficient under the constraint that all coefficients are integer. That seems to need somewhat more monomials (97), but unlike the monomial-minimising version it uses only monomials of total degree at most 3. Here’s my best try, with M checked using Pace’s Mathematica code (I don’t have Maple to do the cross-check, unfortunately); I used epsilon=1/4 so as to eliminate the M6 and M8 constraints.

FA = -268+393 x-602 x^2+528 x^3+527 y-500 x y+426 x^2 y-1170 y^2+1652 y^3+406 z-237 x z+234 x^2 z-400 y z+199 x y z+245 y^2 z-461 z^2+90 x z^2+271 y z^2+207 z^3

FB = -166+211 x-298 x^2+102 x^3+444 y-272 x y+284 x^2 y-1221 y^2+243 x y^2+1526 y^3+134 z+63 x z+89 x^2 z-163 y z-176 x y z+308 y^2 z-146 z^2-97 x z^2+98 y z^2+82 z^3

FC = -89+184 x-145 x^2+257 y-406 x y+338 x^2 y-575 y^2+214 x y^2+742 y^3

FE = -51+36 x+136 y

FG = 21105-79320 x+74220 x^2-20480 x^3-71976 y+178336 x y-82368 x^2 y+64428 y^2-75840 x y^2-18304 y^3-42828 z+107408 x z-50304 x^2 z+97616 y z-121088 x y z-43776 y^2 z+28964 z^2-36352 x z^2-33088 y z^2-6528 z^3

FH = 32 z

FS = -27+36 x+72 y

FT = 66-107 x+42 x^2+176 y-92 x y-264 y^2-176 z+130 x z+88 z^2

FU = 370-7360 x+23485 x^2-20480 x^3+240 y-1192 x^2 y+420 y^2+5760 x z-9716 x^2 z-768 y^2 z-508 z^2-1088 x z^2+256 z^3

Intriguingly, M=1.99 can be achieved with the following much simpler set:

FA = 53 – 45x – 31y – 35z

FB = 29 – 19x – 29y – 9z

FC = 18 – 20x – 17y

FE = 6

FH = -6

FG = FS = FT = FU = 0

which arguably suggests that a modest amount of additional partitioning of FG and possibly FU, allowing them to be handled by two or three polynomials rather than one, could allow for considerably simpler polynomials to reach M=2. I have insufficient understanding of the partitioning process to be able to explore this, unfortunately.

7 May, 2014 at 8:01 am

Eytan PaldiWhat is the M-value for the above piecewise polynomial? (if it is very close to 2, than the coefficients can’t vary much – so they must have a minimal number of digits. Perhaps the larger number of digits in the coefficients of FG and FU is really needed to satisfy the marginal vanishing conditions.)

4 May, 2014 at 4:47 am

AnonymousI’m sorry many times,proving H=2 in October.2014,(not August).That’s an earthquake in maths.I bet all the world.

6 May, 2014 at 5:58 am

Alastair IrvingA few corrections to Section 3:

1. At the start of section 3:

“Recall that for any ”

should be .

2. IN Theorem 3.2 part (xi) it should be DHL[k,m+1] not DHL[k,m].

3. The in (3.6) must be wrong, should it be ?

4. In Theorem 3.5, the definition of , it should presumably be not and not .

[Corrected, thanks – T.]6 May, 2014 at 6:23 am

Alastair IrvingLemma 4.1 doesn’t make sense as there is no N on the LHS. I’m guessing there’s a missing constraint on the summation.

[Corrected, thanks – T]6 May, 2014 at 5:16 pm

Aubrey de GreyTerry: I just saw your Remark 7.4 in the draft paper. I don’t have the explicit polynomial giving M_4,epsilon=2.05411, I’m afraid: I obtained that value by modifying Pace’s code for k=53 (the version that’s in the dropbox as DegreeOptimizer-2014-02-13-BiggerRegion5.nb), and I can’t immediately see how to extract monomials from the rationalised eigenvector with that code – maybe Pace can. (Pace: if so, possibly we can resolve the outstanding question of whether it is safe to let the degree equal k when k is even. I printed the rationalised eigenvector and notice that its last element is always zero when d=k – is that a clue?) The value 2.05411 is obtained by evaluating Output[4,3,0,5/21]; Output[4,4,0,11/48] (if confirmed safe) is 2.06292. (Note: in looking into this I noticed an error in my post of March 4th, namely that the optimised epsilon that I stated, 0.2294921875, was actually for the quartic computation rather than the cubic one. Terry, please change it to 5/21 in the Remark – thanks.]

Concerning the last sentence in Remark 7.4, Pace’s same code can be used to get values for k=3; sure enough, Output[3,3,0,56/113] gives 1.91726.

Also, I realised that “zstart”, the third parameter to Output, which is the power of (1-P1) in the overall polynomial, was always 0 in my tests (including those reported above). The code throws errors for me when I set zstart=k, but not when zstart=k-1. Is it OK to have d+zstart greater than k? I suspect it is, because the best I get with Output[3,1,2,8/33] is 1.87392, just minutely less than the value of 1.87459 that you showed to be optimal when F is not restricted to be a polynomial, and similarly Output[4,1,3,2/11] is 2.01836 versus 2.01869 (twice as close as in the k=3 case – does this constitute encouragement that polynomials are all we need to investigate?) – but please confirm. If so, we can obtain the following marginally better values:

Output[4,3,3,7/29] = 2.05957

Output[4,4,3,17/67] = 2.06913 (just in case Pace determines that d=k=4 is indeed OK)

Output[3,3,2,20/39] = 1.91988

[In case anyone wonders, all values of epsilon above minimise its denominator subject to maximising M to the five decimal places given, as identified by Mathematica’s Rationalize function. The optimality of Output[k,1,k-1,8/11k] holds extremely accurately for the next few k too.]

[Corrections to remark made, thanks – T.]6 May, 2014 at 8:15 pm

Pace NielsenI did not test the zstart part of the code as extensively as I would have liked. (It allows the power on (1-P_1) to grow larger than d; and from testing it I seem to recall that it did not provide much improvement.)

I think there is a chance that setting d>= k can lead to problems, and cannot vouch for the results of the code in those cases.

6 May, 2014 at 8:19 pm

Pace NielsenSo, for instance, if you set zstart=2 then your set of polynomials is of the form where and . But as I said, I didn’t extensively test this part– I always just take zstart=0.

7 May, 2014 at 11:43 am

Alastair IrvingThe links in the post to the paper on Dropbox don’t seem to work any more. Please could someone with access to the folder provide an updated URL?

[Corrected, thanks – T.]7 May, 2014 at 2:06 pm

Pace NielsenI quickly read through the draft. Here are some (mostly minor) comments.

1. In Theorems 1.3, 1.4, and so forth, do you want to specify that the absolute constant is effective? [I imagine most people don’t really care. You might just add a comment at the beginning of the paper that all absolute constants in the paper are effective.]

2. In Equation (1.2) (and elsewhere), the symbol is used, although it wasn’t defined in the asymptotic notation section.

3. When I initially read Claim 2.4, the math symbol looked like the word “a”. Some rewording may help here, maybe something like “If the residue class…”.

4. Page 7. The word “”sectoins” should be “sections”.

5. Page 7, the line above 3.2 needs a colon.

6. In equations (4.13) and (4.14), I believe all ‘s need to be ‘s (otherwise I’m seeing a disconnect with (4.12)).

7. In equation (5.1), should the right-hand side be ? (I.e. does the numerator need a 2?)

8. There are 4 places where it reads , and the dots needs a backslash.

9. Page 35, line 2, there is no space between and “supported”.

10. Page 45, last line. Is the integral missing a ?

11. Page 49, line -2. Is correct?

That’s it!

Would you like me to write some text to fill in some of the missing material in Section 7.2? So far, the paper reads VERY well, and I’m sure you could fill in the missing material better than I could, but I’m happy to help.

8 May, 2014 at 3:09 pm

Terence TaoThanks for the corrections! Yes, any help you could give with Sections 7.1, 7.2, and 7.4 in particular would be great.

9 May, 2014 at 5:14 am

Andrew V. SutherlandI updated the fast admissibility testing code to handle verification of asymmetric Hensley-Richards tuples

\{-p_{n+\lfloor k_0/2\rfloor – 1-i}, \ldots, -p_{n+1}, -1, 1, p_{n+1},\ldots, p_{n+\lfloor (k_0+1)/2\rfloor-1+i}\}.

This yields some small improvements to the bounds on H for the m=4,5 cases.

Under the 1080/13*varpi+330/13*delta < 1 constraint we now have

m=4, k0=74,487,363, H=1,460,485,532

m=5, k0=3,393,468,735 H=79,929,332,990

Under the weaker 600/7*varpi+180/7*delta < 1 constraint we get

m=4, k0=75,845,707, H=1,488,222,198

m=5, k0=3,473,955,908, H=81,912,604,302

Under the Deligne-free 168*varpi+48*delta < 1 constraint we get

m=4, k0=105,754,838, H=2,111,417,340

m=5, k0=5,274,206,963 H=126,630,386,774

To verify the above results, compile the fast admissibility testing code and then use

ahrverify 74487363 492570 98449

ahrverify 75845707 492570 80322

ahrverify 105754838 654992 626457

ahrverify 3393468735 13773747 64666

ahrverify 3473955908 14132283 1872052

ahrverify 5274206963 20369534 11602015

I'm also looking into the possibility of implementing greedy sieving for k0 values in this range. If this can be done it would yield much larger improvements, but I'm not sure yet how feasible this is (my guess is we can probably get the m=4 cases, but the m=5 cases may be out of reach).

10 May, 2014 at 4:05 pm

Terence TaoGiven the issues with the constraint, I have commented out the portion of the paper using this constraint and reverted to the verified constraint. When doing so, I verified the various values of in the m=2,3,4,5 computations. While they all check out, I am finding an unusual amount of slack in the m=4, k=75845707 and m=5, k=3473955908 calculations (from http://www.cs.cmu.edu/~xfxie/project/admissible/k0/sol_varpi600d7m4_75845707.mpl and http://www.cs.cmu.edu/~xfxie/project/admissible/k0/sol_varpi600d7m5_3473955908.mpl respectively), in that is well below 7 in these cases (of the order of ). But this may be because I am not using sufficient precision in these two cases. All the other values look pretty tight though (e.g. the error between and 7 is more like in the k=2,3 cases). It may be worth double checking the k=4,5 values.

10 May, 2014 at 4:42 pm

xfxieIt might be caused by a precision problem as pointed by Wouter. In the computation for large m values, a high precision (e.g., Digits := 50) should be used.

10 May, 2014 at 6:08 pm

Aubrey de GreyMy implementation terminates at 75845709 for m=4 (with c=0.055506225585937443712, T=0.042440185546874981126) and 3473955910 for m=5 (with c=0.045880571365356399849, T=0.034099090576171831035). Each of these k’s is 2 greater than xfxie’s values, but I expect that’s a (different) precision issue – I didn’t explore how to improve that in Mathematica.

If you can work out the constraint on varpi and delta that you mentioned on April 21st (arising from doing two sequential vdC’s rather than one 2D one), I’ll provide the corresponding best values for k.

10 May, 2014 at 7:06 pm

xfxieBTW: For Digits := 50, the slack values in my solutions are:

m=4: 0.224593440614655464852452317001727394641205E-8

m=5: 0.107816913476554204615005610883051801771250E-9

11 May, 2014 at 7:10 am

Terence TaoYes, it was a precision issue, my run of Maple now matches your numbers, thanks!

11 May, 2014 at 5:00 am

Eytan PaldiIn the definition of the operator (now at the end of page 55), the integration upper limit should be corrected.

[Corrected, thanks – T.]12 May, 2014 at 6:54 am

Svyatoslav ShmidtTerence, Thank you a lot for yours knowledge! While playing with the function of the gaps between primes, I found an interesting image.Plot of the function g_n=log_2〖(P_(n+1) 〗-P_n) In the polar coordinate system looks like the ripples. (pic. : http://cs617127.vk.me/v617127546/8b0f/Hg97K3QccO4.jpg ) Good luck in your research!

13 May, 2014 at 12:32 am

Andrew V. SutherlandI added Dense clusters of primes in subsets to the wiki.

13 May, 2014 at 12:34 pm

Pace NielsenI’m starting to work on section 7. I should have my additions done either later today or tomorrow.

13 May, 2014 at 1:25 pm

Pace NielsenI’ve uploaded the changes for section 7 as h1-new.tex and xyplot-new.pdf. If you like the changes, just remove “-new” from the filenames.

The new plot is to scale when . Because of this, you might want to point out that in the integral formula for , one of the terms disappears. If you want me to make further changes to the plot, that would be easy to do.

I made a few comments in the file about possible ways to simplify the exposition (such as modifying the Beta integral identity to account for additional powers of ). I wasn’t sure what you wanted for section 7.2, so I gave a very “bare-bones” description of the ideas.

I hope this is somewhat helpful

As always, thank you for all you do in directing this venture!!

13 May, 2014 at 4:51 pm

Anonymous@Pace: I just had a look at h1-new.tex and noticed that you used $$…$$ for displayed equations. This is not good. (See e.g. http://tex.stackexchange.com/questions/503/why-is-preferable-to.)

13 May, 2014 at 6:55 pm

James MaynardI’ve just made a number of minor changes to more-sieving.tex and asymptotics.tex. They both look good to me.

For the Goldbach/Twin prime result, isn’t it the case that (under the assumption of GEH and the falsity of the twin prime conjecture) that we get all sufficiently large even numbers, rather than just multiples of 6? (the admissible set shows that either 6N and 6N+2 are the sum of at most 2 primes, and so both are within 2 of such a number, and similarly the admissible set , shows that either 6N or 6N-2 are the sum of at most 2 primes, so all of 6N-2,6N and 6N+2 are within 2 of such a number. I guess we should add a remark about the slight modification of the argument needed to deal with two of the linear functions having common factors (since we need a result uniform in the coefficients).

14 May, 2014 at 4:17 pm

Terence TaoAh, you’re right, we do get every even number within 2 of a sum of two primes from this argument. (What we almost, but don’t quite get, though, is that every odd number is within 1 of a sum of two primes.) I’ve modified the paper slightly to indicate this.

14 May, 2014 at 4:42 am

Eytan PaldiThe exponent in theorem 3.2(vi) should be corrected.

[Corrected, thanks – T.]14 May, 2014 at 5:50 am

Andrew V. SutherlandI just posted fast admissibility testing code to the wiki that supports Schinzel sieving. Specifically, it sieves a given interval [s,s+d] of all integers congruent to 1 mod 2 and all integers congruent to 0 mod p up to a specified prime p_n. It then checks that the set of survivors is admissible modulo all primes up to k0 and picks a subsequence of k0 survivors that minimizes the diameter.

This gives improved H bounds for all the m=4,5 cases.

Under the 1080/13*varpi+330/13*delta < 1 constraint we have

m=4, k0=74,487,363, H=1,440,495,268

m=5, k0=3,393,468,735, H=78,807,316,822

Under the 600/7*varpi+180/7*delta < 1 constraint we have

m=4, k0=75,845,707, H=1,467,584,468

m=5, k0=3,473,955,908, H=80,761,835,464

Under the Deligne-free 168*varpi+48*delta < 1 constraint we have

m=4, k0=105,754,837, H=2,082,729,956

m=5, k0=5,274,206,963, H=124,840,189,042

These bounds can be verified by compiling the fast admissibility testing code and then:

schinzelverify 74487363 74487363 1441846336 467557

schinzelverify 75845707 75845707 1468058816 467557

schinzelverify 105754837 105754837 2084601984 629732

schinzelverify 3393468735 3393468735 78881864192 13361346

schinzelverify 3473955908 3473955908 80835304192 13664637

schinzelverify 5274206963 5274206963 124956217600 19706960

The four numbers listed in each line above are the values of k0, s, d, and n.

For the record, I should also note the sub intervals of the sieved interval [s,s+d] that yield the above H bounds are:

k0=74487363: [74489356,1514984624]

k0=75845707: [75856874,1543441342]

k0=105754837: [105767006,2188496962]

k0=3393468735: [3467835454,82275152276]

k0=3473955908: [3547420054,84309255518]

k0=5274206963: [5389030684,130229219726]

14 May, 2014 at 9:34 am

Aubrey de GreyQuite big improvements, as you predicted. Did you already use this sieve (or a better one) for all the smaller k0 values of interest?

14 May, 2014 at 10:02 am

Andrew V. SutherlandFor the smaller k0 values I used a greedy sieve, which does even better. For comparison, for k0=2,113,163 using the Schinzel sieve as above yields a diameter of 33,286,862, versus the 32,285,928 obtained using a greedy sieve.

It should certainly be possible to get further improvements for the m=4,5 cases using a greedy sieve, but the algorithm is more memory intensive and more difficult to parallelize, so this will take some effort (and computer time). I will try to work on this some more over the weekend (I also need to start writing up Appendix A, which I have been delaying until we settle on the best algorithm for obtaining large admissible tuples).

14 May, 2014 at 4:03 pm

Eytan PaldiIn the line above the end of prop. 6.5 proof, inside the parentheses of the RHS integrand, it should be

[Corrected, thanks – T.]15 May, 2014 at 4:10 am

Eytan PaldiIn the line above theorem 6.7, it should be “term” (instead of “factor”).

[Corrected, thanks – T.]16 May, 2014 at 3:30 pm

Eytan PaldiIn section 7.4, there is a typo in the first term of the polynomial on

[Corrected, thanks – T.]16 May, 2014 at 8:51 pm

James MaynardHmmm, Eytan’s corrections have made me realise that many of the last set of changes I attempted to make didn’t seem to go through correctly. I’m not sure why this was, but since you’re looking at the files I thought I’d write out a list of things I’d noticed here to avoid conflicts. I think I’ve managed to recall them all. (The only other changes I tried to make were minor layout/language changes which can be made later).

Page 33: eq (5.7): integration should be over instead of , and it should be the -fold differential with respect to instead of all variables.

Paragraph after (5.9): I think the reference (5.5) should be to the set defined in the equation above.

Page 34: after (5.10): maybe mention is fixed.

After (5.13): maybe recall definition (3.6) of

Page 36: equation after (5.14): again, integration over , and derivative (wrt variables other than ).

Page 38: first line: not .

Line 3: instead of .

Eq 5.19: there is an accidental in the second sum.

Line -7: for instead of

Line -3: should this be instead of (obviously the second is also true). Also for page 39 line 2.

Page 39: line 5: `.. we prove Theorem 3.14’ instead of Theorem 3.12.

Page 40: equations after 5.22: I think we use EH to prove the lower bound for the prime sums, and GEH to prove the asymptotic for the non-prime sums, so these should be the other way round. Also (as above) should it be rather than .

Page 42: line -4: instead of .

Page 46: line 10: maybe mention that we are extending to by .

inequality before (6.20): instead of .

Page 47: In various places I think we need to swap strict and weak inequalities, since the equation doesn’t hold if (and is not defined at 0). This occurs on line 1 and twice on line 5.

Line 7: instead of .

Line 11: `third equality’ instead of `second equality’.

Line -3: Maybe note we are using (6.12) here.

(6.24): There should be a factor of on the right hand side.

Page 48: line 6: not

Line 8: Maybe note we are using (6.10) here.

Line -6: The use of for general hasn’t been defined; maybe better to stick with .

Page 49: line 14: any not .

Page 50: line 8: ds missing from integral.

Page 52: line 5: I get as the final constraint.

Page 53: before section 7: Maybe mention that the constraints (6.10)-(6.12) hold for each of these choices of parameters.

[Added, thanks – T.]17 May, 2014 at 10:27 am

Polymath 8b, XI: Finishing up the paper | What's new[…] the previous thread may be found here. […]