Conditional dbn bounds

[km-git-acc]

@rudolph-git-acc
I have added the sawtooth and approximate bounds to the repo here
https://github.com/km-git-acc/dbn_upper_bound/blob/master/dbn_upper_bound/pari/abbeff_largex_bounds.txt

Also, the full mollifier has been changed back to mollifier, and the mollifier with prime terms has been changed to mollifier_prime
There are also multiple functions now for the approximate bounds
ep_tbound and ep_lbound which are exact and use the full mollifier
ep_tbound_mollp and ep_lbound_mollp which are exact and use the prime mollifier
ep_tbound_approx and ep_lbound_approx which currently use the prime mollifier but can use the full one too

Both the mollifier functions needed the t parameter too which I have added. It worked earlier if t was assigned a value at the beginning itself but could have been prone to errors.

Added the ball script for the sawtooth bounds to the repo here
https://github.com/km-git-acc/dbn_upper_bound/blob/master/dbn_upper_bound/arb/Mollifier.3.and.5.sawtooth.bound.script.txt
You may want to update it with a generalized mollifier.

Also, added an approx function for (A+B)/B0 using N0 terms in the barrier multieval script. I have tried it at x=10^100 and it works (though the precision \p may have to be increased first to around log(x)). Ofcourse when y and t are small the quality of the approximation is not clear. The approximation gets better the larger the B exponents and should be good enough at real(exponents) >> 1 (similar to how the zeta function behaves). Ofcourse when the real(exponents) >> 1, (A+B)/B0 moves close to 1, so the area of interest is small t and y where the approximation may not be that great.

[km-git-acc]

@rudolph-git-acc
I have started running the bound calculations from N=892063 to 30 mil, y=0.2, t=0.16, mollifier 5. It's running through 35000 N values in a minute, so I guess will take around 13 hours.

Have also added a function barrier_strip_search to the barrier_multieval script which can be used to generate euler product data near a chosen X (which then has to be filtered and searched for good X candidates, maybe in a spreadsheet or an adhoc script).

EDIT1: Since it is appending output to an already large file, the speed has reduced to 25000 N vals a minute, and probably will keep decreasing gradually. Even though the bounds allow us to complete things in a single run, it may be a good idea practically to have multiple 'tooths' instead of a single one for large runs.

[rudolph-git-acc]

Great! I will start the same batch in Sage Balls when I am back online tonight, so we can compare output. As soon as we have found a good spot for the barrier, happy to run the barrier clearing as well. P.S. I was checking the general Wiki page on the De Bruijn Newman constant and was surprised to see that the page was immediately updated after we announced the Lambda =0.22 result. Somebody is closely monitoring our progress :-) Verstuurd vanaf mijn iPad

…

Op 6 mei 2018 om 08:30 heeft KM ***@***.***> het volgende geschreven: @rudolph-git-acc I have started running the bound calculations from N=892063 to 30 mil, y=0.2, t=0.16, mollifier 5. It's running through 35000 N values in a minute, so I guess will take around 13 hours. Have also added a function barrier_strip_search to the barrier_multieval script which can be used to generate euler product data near a chosen X (which then has to be filtered and searched for good X candidates, maybe in a spreadsheet or an adhoc script). — You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub, or mute the thread.

[km-git-acc]

@rudolph-git-acc
Great. I think the results are being updated by Prof. Tao himself.

The below analysis can be treated as an exercise in overcaution, but it could be useful as a backup.

Our formula for bound_(N+1) is bound_N - (Extra D terms at N+1) (- also a small error term; ignoring that for now)

As N increases, modgamma decreases so we are nicely conservative with the 1-a1 = 1-modgamma term

The exponent sig also increases as N increases, so we are conservative here as well.

The common term in the lemma bound sum (which we want as large as possible to be conservative) |(1-a1)/(1+a1)| = |(1-gamma)/(1+gamma)| is actually slightly different from (1-modgamma)/(1+modgamma). |1-gamma| >= 1-modgamma and |1+gamma| <= 1+modgamma, so the actual term is slightly larger than what we are using (also the modgamma we are using is actually a upper bound on gamma making our current sum even smaller). But it's not clear whether we can take gamma as gamma(xN) since it may or may not not be monotone decreasing in the same N interval.

Secondly, (1-modgamma)/(1+modgamma) increases as N increases, so we are not conservative if we use a smaller common term in the prevbound calculations while calculating the bound at N+1 (since then max((b-a), c*(b+a)) would be often if not always smaller than what would have happened if the N+1 bound was calculated normally)

The maximum possible value of (1-modgamma)/(1+modgamma) should be 1, and more strictly that of |1-gamma|/|1+gamma| should be (1+modgamma)/(1-modgamma). The latter actually decreases towards 1 as N increases which is its ideal behavior.
So while calculating both the base bound and then the sawtooth bounds, we should take the common term to be either 1 or more conservatively (1+modgamma)/(1-modgamma).

Since the current full bound is used for normal calculations as well, its better to create another version of the full bound which would be used only with the sawtooth bounds function.

Ofcourse, currently some of the quantities work in our favor and the common term does not, so (non-rigorously) their effect likely cancels out and even the current bounds may be fine, but I will write two additional functions (one each for the base and sawtooth bounds) which can calculate according to the above.

EDIT: Actually on thinking further it seems that modgamma enters the derivation early at
bound >= |B sum| - modgamma*|A sum|
so we may not worry about |1-gamma|/|1+gamma| or that modgamma is an upper bound for gamma at a given N.
So we could take commonterm=1 (which gives a comfortably positive base bound (0.0741104187469) for N=892062 Euler 5 but takes things negative even for N=69098 Euler 7), or more optimally commonterm = (1-modgamma_(N_end))/(1+modgamma_(N_end)) which is the highest value of commonterm in the chosen N verification range.

With the more optimal latter setting,
N=69098,y=0.2,t=0.2, mtype=7 gives a base bound of 0.0338943569372946644
N=892062,y=0.2,t=0.16, mtype=5 gives a base bound around 0.11

Also I have updated the script
https://github.com/km-git-acc/dbn_upper_bound/blob/master/dbn_upper_bound/pari/abbeff_largex_bounds.txt
with 4 functions

• abbeff_largex_ep_lbound_sawtooth_loop (similar as earlier but eliminates the repeated computation of the mollifier and some constants)
• lembound_conservative (which uses the conservative common term to calculate the lemmabound)
• abbeff_largex_ep_lbound_conservative (which uses lembound_conservative with appropriate parameters)
• abbeff_largex_ep_lbound_sawtooth_conservative_loop (similar to abbeff_largex_ep_lbound_sawtooth_loop but with the common term updated)

[rudolph-git-acc]

@km-git-acc

Thanks for the additions and good that you went through the sawtooth method once more to verify we hadn't missed a 'progressive' variable when jumping from N to N+1.

Just kicked off the run for: N = 892062 to 30000000, step 1, t=0.16, y=0.2 euler5 (although we probably could have tried euler3 as well). Will spend tomorrow on trying to update P15's ARB script to accommodate y < 1/3. He has already developed a generalised mollifier formula, which is something I unfortunately can't build in Sage Balls (no arrays, lists, vectors, etc. supported for Sage ARB's or Sage ACB's yet).

[km-git-acc]

@rudolph-git-acc
Great. I have reached around 27 mil (with the non-conservative version) and the bound value looks like it will stay above 0.1772. So hardly any change from 0.178!

Incidentally, the output file currently is around 3.6 gb (although compression should reduce it quite a bit). One thing we can do for large runs is to print the output for only every 100th or 1000th or some 10^kth N value. Since the formula is recursive and relies on the previous bound, it implies the bounds for the non-printed N lie in between the printed bounds. Another redundancy is the t and y being printed on every line, when they could just go into the filename. Will make these changes later.

[rudolph-git-acc]

@km-git-acc

Yeah, we could indeed simplify the output a bit further. To my surprise my run just completed already... ...and I discovered that I had run till 3 mln instead to 30 mln :-) Running again!

[km-git-acc]

@rudolph-git-acc

Some more analysis of our approach while verifying the lemmabounds between [Nmin,Nmax]:

|bn-an| = |1-modgamma*n^y||f_(n,mollifier)| and
|bn+an| = |1+modgamma*n^y||f_(n,mollifier)|

Hence |bn+an| >= |bn-an|
Also, |bn+an| decreases with increasing N hence is conservative
while |bn-an| increases with increasing N, hence may not be conservative

If common = |1-a1|/|1+a1| = |1-modgamma|/|1+modgamma|
is replaced by 1, then max(|bn-an|,common*|bn+an|) = |bn+an| hence our approach becomes conservative again

If common = |1-a1|/|1+a1| = |1-modgamma|/|1+modgamma|
is replaced optimally by |1-modgamma_(Nmax)|/|1+modgamma_(Nmax)| = c, then the analysis is a bit more delicate.
We then want
|1-modgamma*n^y|/|1+modgamma*n^y| <= c
Taking modgamma = 1/N^y (both are very close)
we want |N^y-n^y|/|N^y+n^y| <= c
So for the case n <= N, we want n >= N*[(1-c)/(1+c)]^(1/y) = N/Nmax
and for the case n >= N, we want n <= N*[(1+c)/(1-c)]^(1/y) = N*Nmax

For Nmin = 69098, Nmax = 1.5 mil, y = 0.2
c = 0.89 (approx)
hence approx n >= N/(1.5 mil) and n < N*(1.5 mil)
or conservatively, n >= Nmax/(1.5 mil) and n < Nmin*(1.5 mil)
i.e. n >= 1 and n < 10 billion (approx)
This should be valid for upto a mollifier with D < (10 bil)/(1.5 mil) = 6666 or Euler mollifier 11

So if use the optimal setting for commonterm, and if any of our bounds are positive enough till mollifier 11 (and I saw yesterday that with Euler 7, we were getting a conservative base bound of around 0.03389), we should be good.

And when commonterm=1 itself gives a positive bound, we can use that since then we are not restricted in either our mollifier usage or our choice of Nmax.

[rudolph-git-acc]

@km-git-acc

Your reassuring analysis looks sound to me.

In the mean time my run up to 30mln has completed as well:

https://drive.google.com/open?id=1ILU67z84X8akrS4MfFSOrLQLlAQ1Wp-1

Have spent most of the day on changing the ARB code. Have completed most of the coding and the script compiles without any errors. Currently in test phase but struggling with an unexpected 'segmentation error: 11' issue, that seems to have to do something with the bt and at arrays. Will plough forward step by step :-)

[km-git-acc]

@rudolph-git-acc
Great. I am currently working on the tex derivation for the writeup.

[rudolph-git-acc]

@km-git-acc

I now have a fully working ARB-version of the Lemma bound (so, valid for all y) :-)

Need a to make a small final tweak (related to the max-function that is not supported in acb-poly language). It is super fast and supports generic choice of the Euler mollifiers (thanks to P15, whose module I could fully reuse).

Will share the script tomorrow.

[rudolph-git-acc]

@km-git-acc

Here is the ARB-script for the Lemma bound (fully written in acb-poly functions). It was a bit of a learning curve, but I feel now quite comfortable coding other functions as well.

https://github.com/km-git-acc/dbn_upper_bound/blob/master/dbn_upper_bound/arb/main.c

Grateful if you could try it out. Is there anything you would recommend me to code next?

P.S.: t=0.19, y=0.2 at 69098 with Euler 11 is indeed negative: -0.08732291084 (it ran in 1.5 hours).

[km-git-acc]

@rudolph-git-acc
Awesome. I will try it out.
Well, one thing we had discussed in the past is that although the barrier calculations using the Taylor expansion method is quite fast, it may work even better in Arb. That is something we could try out and would also make a meaningful difference at x=10^13.

[rudolph-git-acc]

@km-git-acc

Will take a look at the Barrier script.

I now also could compute the bound for a few higher 'conditional' N:

   N        xN       moll       t       y      bound
282094   (x=10^12), euler 3, t=0.16, y=0.2, -0.4786244069
282094   (x=10^12), euler 3, t=0.17, y=0.2, -0.1228575095
282094   (x=10^12), euler 3, t=0.18, y=0.2,  0.1326973081
892962   (x=10^13), euler 3, t=0.15, y=0.2, -0.2543316258
892962   (x=10^13), euler 3, t=0.16, y=0.2,  0.08506987434
2820947  (x=10^14), euler 3, t=0.14, y=0.2, -0.1053221945
2820947  (x=10^14), euler 3, t=0.15, y=0.2,  0.227463558
8920621  (x=10^15), euler 3, t=0.13, y=0.2, -0.02371181138
8920621  (x=10^15), euler 3, t=0.14, y=0.2,  0.3166296087
28209479 (x=10^16), euler 3, t=0.12, y=0.2, -0.009041863662
28209479 (x=10^16), euler 3, t=0.13, y=0.2,  0.3611995469

It seems that with every extra power of 10, the bound becomes positive for a t-0.01. What surprises me is that this process seems to accelerate (i.e. the bound becoming positive sooner). Do you seen the same pattern? Now running 10^17.

[km-git-acc]

@rudolph-git-acc
Well increasing N should have a positive effect on the bound, but I dont't have a firm opinion on the speed of that effect yet and will have to do some such exercises myself to understand better.

Have been busy with some personal stuff so haven't been able to give enough time to the project this week, and decided to first complete the pending writeup part with whatever time I had. I should be able to get back to normal mode during the weekend and after.

I have edited the writeup (pg 35 and 36) with the incremental approach (conservative). Two things I realized during derivation is that |bn-an|/|bn+an| probably cant be written simply as |1-modgamma*n^y|/|1+modgamma*n^y| due to the additional d^y factors in the mollification of an, but then have to written as |g(n,moll)-modgamma*n^y|/|g(n,moll)+modgamma*n^y| which I then computationally verified meets the desired properties.
Secondly, when N to N+1, it is not just the end D terms which have to be accounted for. For each divisor d of D, the numerators of the terms n=dN+[1,d] should also change a bit, due to the n <= dN part.

Due to the multiple minor changes in this approach, I feel it's better to first get feedback and close any remaining possible loopholes, before making definitive changes in our bound scripts.