This is the tenth “research” thread of the Polymath15 project to upper bound the de Bruijn-Newman constant , continuing this post. Discussion of the project of a non-research nature can continue for now in the existing proposal thread. Progress will be summarised at this Polymath wiki page.
Most of the progress since the last thread has been on the numerical side, in which the various techniques to numerically establish zero-free regions to the equation have been streamlined, made faster, and extended to larger heights than were previously possible. The best bound for now depends on the height to which one is willing to assume the Riemann hypothesis. Using the conservative verification up to height (slightly larger than) , which has been confirmed by independent work of Platt et al. and Gourdon-Demichel, the best bound remains at . Using the verification up to height claimed by Gourdon-Demichel, this improves slightly to , and if one assumes the Riemann hypothesis up to height the bound improves to , contingent on a numerical computation that is still underway. (See the table below the fold for more data of this form.) This is broadly consistent with the expectation that the bound on should be inversely proportional to the logarithm of the height at which the Riemann hypothesis is verified.
As progress seems to have stabilised, it may be time to transition to the writing phase of the Polymath15 project. (There are still some interesting research questions to pursue, such as numerically investigating the zeroes of for negative values of , but the writeup does not necessarily have to contain every single direction pursued in the project. If enough additional interesting findings are unearthed then one could always consider writing a second paper, for instance.
Below the fold is the detailed progress report on the numerics by Rudolph Dwars and Kalpesh Muchhal.
— Quick recap —
The effectively bounded and normalised, Riemann-Siegel type asymptotic approximation for :
enables us to explore its complex zeros and to establish zero-free regions. By choosing a promising combination and , and then numerically and analytically showing that the right-hand side doesn’t vanish in the rectangular shaped “canopy” (or a point on the blue hyperbola), a new DBN upper bound will be established. Summarized in this visual:
— The Barrier approach —
To verify that in such a rectangular strip, we have adopted the so-called Barrier-approach that comprises of three stages (illustrated in a picture below):
- Use the numerical verification work of the RH already done by others. Independent teams have now verified the RH up to , and a single study took it up to . This work allows us to rule out, up to a certain , that a complex zero has flown through the critical strip into any defined canopy. To also cover the x-domains that lie beyond these known verifications, we have to assume the RH up to . This will then yield a that is conditional on this assumption.
- Complex zeros could also have horizontally flown into the ‘forbidden tunnel’ at high velocity. To numerically verify this hasn’t occurred, a Barrier needs to be introduced at and checked for any zeros having flown around, through or over it.
- Verifying the range (or ) is done through testing that the lower bound of always stays higher than the upper bound of the error terms. This has to be done numerically up to a certain point , after which analytical proof takes over.
So, new numerical computations are required to verify that both the Barrier at and the non-analytical part of the range are zero-free for a certain choice of .
— Verifying the Barrier is zero-free —
So, how to numerically verify that the Barrier is zero-free?
- The Barrier is required to have two nearby screens at and to ensure that no complex zeros could fly around it. Hence, it has the 3D structure: .
- For the numerical verification that the Barrier is zero-free, it is treated as a ‘pile’ of rectangles. For each rectangle the winding number is computed using the argument principle and Rouché’s theorem.
- For each rectangle, the number of mesh points required is decided using the -derivative, and the t-step is decided using the -derivative.
Optimizations used for the barrier computations
- To efficiently calculate all required mesh points of on the rectangle sides, we used a pre-calculated stored sum matrix that is Taylor expanded in the and -directions. The resulting polynomial is used to calculate the required mesh points. The formula for the stored sum matrix:
with and , where and are the number of Taylor expansion terms required to achieve the required level of accuracy (in our computations we used 20 digits and an algorithm to automatically determine and ).
- We found that a more careful placement of the Barrier at an makes a significant difference in the computation time required. A good location is where has a large relative magnitude. Since retains some Euler product structure, such locations can be quickly guessed by evaluating a certain euler product upto a small number of primes, for multiple X candidates in an X range.
- Since and have smooth i.e. non-oscillatory behavior, using conservative numeric integrals with the Lemma 9.3 summands, , instead of the actual summation is feasible, and is significantly faster (the time complexity of estimation becomes independent of )
- Using a fixed mesh for a rectangle contour (can change from rectangle to rectangle) allows for vectorized computations and is significantly faster than using an adaptive mesh. To determine the number of mesh points, it is assumed that will stay above 1 (which is expected given the way the X location has been chosen, and is later verified after has been computed at all the mesh points). The number is chosen as
- Since for the above fixed mesh generally comes way above 1, the lower bound along the entire contour (not just on the mesh points) is higher than what would be the case with an adaptive mesh. This property is used to obtain a larger t-step while moving in the t-direction
— Verifying the range —
This leaves us with ensuring the range (where is the value of corresponding to the barrier ) is zero-free through checking that for each , the lower bound always exceeds the upper bound of the error terms.
- From theory, two lower bounds are available: the Lemma-bound (eq. 80 in the writeup) and an approximate Triangle bound (eq. 79 in the writeup). Both bounds can be ‘mollified’ by choosing an increasing number of primes (to a certain extent) until the bound is sufficiently positive.
- The Lemma bound is used to find the number of ‘mollifiers’ required to make the bound positive at . We found that using primes was the max. number of primes still allowing an acceptable computational performance.
- The approximate Triangle bound evaluates faster and is used to establish the mollified (either 0 primes or only prime 2) end point before the analytical lower bound takes over.
- The Lemma-bound is then also used to calculate that for each in , the lower bound stays sufficiently above the error terms. The Lemma bound only needs to be verified for the line segment _{,} since the Lemma bound monotonically increases when goes to 1.
Optimizations used for Lemmabound calculations
- To speed up computations a fast “sawtooth” mechanism has been developed. This only calculates the minimally required incremental Lemma bound terms and only induces a full calculation when the incremental bound goes below a defined threshold (that is sufficiently above the error bounds).
where
(as presented within section 9 of the writeup, pg. 42)
— Software used —
To accommodate the above, he following software has been developed in both pari/gp (https://pari.math.u-bordeaux.fr) and ARB (http://arblib.org):
For verifying the Barrier:
- Barrier_Location_Optimizer to find the optimal location to place the Barrier.
- Stored_Sums_Generator to generate in matrix form, the coefficients of the Taylor polynomial. This is one-off activity for a given , post which the coefficients can be used for winding number computations in different and ranges.
- Winding_Number_Calculator to verify that no complex zeros passed the Barrier.
For verifying the range:
- N_{b}_Location_Finder for the number of mollifiers to make the bound positive.
- Lemmabound_calculator Firstly, different mollifiers are tried to see which one gives a sufficiently positive bound at . Then the calculator can be used with that mollifier to evaluate the bound for each in . The range can also be broken up into sub-ranges, which can then be tackled with different mollifiers.
- LemmaBound_Sawtooth_calculator to verify each incrementally calculated Lemma bound stays above the error bounds. Generally this script and the Lemmabound calculator script are substitutes for each other, although the latter may also be used for some initial portion of the N range.
Furthermore we have developed software to compute:
- as and/or .
- the exact value (using the bounded version of the 3^{rd} integral approach).
The software supports parallel processing through multi-threading and grid computing.
— Results achieved —
For various combinations of , these are the numerical outcomes:
The numbers suggest that we now have numerically verified that (even at two different Barrier locations). Also, conditionally on the RH being verified up to various , we have now reached a . We are cautiously optimistic, that the tools available right now, do even bring a conditional within reach of computation.
— Timings for verifying DBN —
Procedure |
Timings |
Stored sums generation at X=6*10^10 + 83951.5 | 42 sec |
Winding number check in the barrier for t=[0,0.2], y=[0.2,1] |
42 sec |
Lemma bounds using incremental method for N=[69098, 250000] and a 4-prime mollifier {2,3,5,7} |
118 sec |
Overall Timings |
~200 sec |
Remarks:
- Timings to be multiplied by a factor of ~3.2 for each incremental order of magnitude of x.
- Parallel processing significantly improves speed (e.g. Stored sums was done in < 7 sec).
- Mollifier 2 analytical bound at is .
— Links to computational results and software used: —
Numerical results achieved:
- Stored sums https://github.com/km-git-acc/dbn_upper_bound/tree/master/output/storedsums
- Winding numbers https://github.com/km-git-acc/dbn_upper_bound/tree/master/output/windingnumbers
- Lemmabound N_a…N_b https://github.com/km-git-acc/dbn_upper_bound/tree/master/output/eulerbounds
Software scripts used:
18 comments
Comments feed for this article
6 September, 2018 at 11:06 pm
scienaimer
Thanks😄, I admire you so much
7 September, 2018 at 7:12 am
Anonymous
Is it possible to reduce the computational complexity by making the width of the barrier variable (not necessarily 1) and choosing a “good” value for it ?
7 September, 2018 at 7:30 am
Terence Tao
The barrier can be reduced in area by a factor of about two (at the cost of replacing its rectangular shape with a region bounded by two straight lines and a parabola), but it can’t be made arbitrarily small (at least with the current arguments). The reason why the barrier needs to be somewhat thick is because one needs to ensure that the complex zeroes (paired with their complex conjugates) on the right of the barrier cannot exert an upward force on any complex zero above the real axis to the left of the barrier; this is to prevent the bad scenario of a complex zero swooping in under the barrier at high velocity, and then being pulled up by zeroes still to the right of the barrier to end up having an imaginary part above at the test time . If the barrier is too thin, then a zero just to the left of it could be pulled up strongly by a zero just to the right and a little bit higher, to an extent that cannot be counteracted by the complex conjugate of the zero to the right. (Though, as I write this, I realise that also the complex conjugate of the zero on the left would also be helpful in pulling the zero down. This may possibly help reduce the size of the barrier a little bit further, although it still can’t be made arbitrarily thin. I’ll try to make a back-of-the-envelope calculation on this shortly. EDIT: ah, I remember the problem now… if one has _many_ zeroes on the right of the barrier trying to pull the zero on the left up, they can overwhelm the effect of the complex conjugate of that zero, so one can’t exploit that conjugate unless one also has some quantitative control on how many zeroes there are just to the right of the barrier.)
My understanding is that verification that the barrier is zero-free has not been the major bottleneck in computations, with the numerical verification of a large rectangular zero-free region to the right of the barrier at time being the more difficult challenge, but perhaps the situation is different at very large heights (I see for instance that there is one choice of parameters in which the rectangular region is in fact completely absent).
7 September, 2018 at 12:19 pm
KM
If we use the Euler 2 analytic bound, and try to maintain the trend of the dbn constant decreasing by 0.01 or more for every order of magnitude change in X, without having to validate any rightward rectangular region, we find such good t0,y0 combinations only till X=10^19.
For example, for X=10^20, we don’t find a combination which could give dbn <= 0.11 by itself (although 0.1125 is manageable), and validating an extra region becomes necessary. We could instead assume a new such trend starts at X=10^20 and ends at X=10^22 with dbn going from 0.12 to 0.10.
If we validate a rightward rectangular region at these heights, it does take significant time. Here, the stored sums generation also takes substantial time (for eg. the 10^19 stored sums took about 30 processor-days (although quite parallelized)). We can choose a larger X to eliminate or reduce the rectangular region but at the cost of more time for the stored sums.
7 September, 2018 at 11:45 am
curious
With unbounded computation capability and infinite time is there a lower bound on ?
7 September, 2018 at 4:24 pm
Terence Tao
Well, it’s now a theorem that , and the Riemann hypothesis is now known to be equivalent to , so it is unlikely that this lower bound will ever be improved :)
Conversely, in the unlikely event that we were able to numerically locate a violation of the Riemann hypothesis, that is to say a zero of off the real line, one could hopefully use some of the numerical methods to calculate developed here to also locate failure of the Riemann hypothesis at or near this location for some positive values of as well. This would then give a positive lower bound to . But I doubt this scenario will ever come to pass. (I doubt that RH will ever be disproven, but if it is, my guess is that the disproof will come more from analytic considerations than from numerically locating a counterexample, which might be of an incredibly large size (e.g., comparable to Skewes number).)
7 September, 2018 at 1:15 pm
Anonymous
In step 4 (of “verifying the range”), the meaning of “the line ” is not clear.
[Text clarified – T.]
7 September, 2018 at 5:31 pm
Anonymous
It seems that should be .
[Corrected, thanks – T.]
7 September, 2018 at 1:21 pm
Anonymous
It is possible to prove that using the zero-free regions method? For example, prove that for every positive ?
7 September, 2018 at 4:26 pm
Anonymous
What you are asking for is a proof that the Riemann hypothesis fails.
RH implies lambda <= 0.
7 September, 2018 at 4:34 pm
Anonymous
Sorry… i wanted to say . I wasn’t pay atention. Thanks!
7 September, 2018 at 4:49 pm
Terence Tao
As I think I mentioned in the previous thread, establishing an upper bound is roughly comparable in difficulty to verifying the Riemann hypothesis up to height for some absolute constant . The computational difficulty of this task is in turn of the order of for some other absolute constant . So the method can in principle obtain any upper bound of the form (assuming of course that RH is true), but the time complexity grows exponentially with the reciprocal of the desired upper bound . My feeling is that absent any major breakthrough on RH, these exponential type bounds are here to stay, although one may be able to improve the values of and somewhat.
7 September, 2018 at 6:55 pm
curious
Does the behavior come from proposition 10.1? Also you say it is unlikely to beat and perhaps it would be nice to state the best behavior if it is beaten to and what is the unlikely event that would trigger?
7 September, 2018 at 7:42 pm
Terence Tao
See my previous comment on this at https://terrytao.wordpress.com/2018/05/04/polymath15-ninth-thread-going-below-0-22/#comment-501625
21 September, 2018 at 5:55 am
Anonymous
Stay tuned:
https://www.newscientist.com/article/2180406-famed-mathematician-claims-proof-of-160-year-old-riemann-hypothesis/
21 September, 2018 at 7:02 am
Anonymous
Such claim from him seems really promising …
22 September, 2018 at 9:26 pm
Anonymous
Dear Prof. Tao,
Are you aware of any details on the supposed proof of the RH by Atiyah?
Best,
23 September, 2018 at 12:22 pm
sylvainjulien
There’s a question on Mathoverflow with a link towards a preprint by Sir Michael : https://mathoverflow.net/questions/311254/is-there-an-error-in-the-pre-print-published-by-atiyah-with-his-proof-of-the-rie