You are currently browsing the monthly archive for February 2018.
This is the fourth “research” thread of the Polymath15 project to upper bound the de Bruijn-Newman constant , continuing https://terrytao.wordpress.com/2018/01/24/polymath-proposal-upper-bounding-the-de-bruijn-newman-constant/. Progress will be summarised at this Polymath wiki page.
We are getting closer to finishing off the following test problem: can one show that whenever
,
? This would morally show that
. A wiki page for this problem has now been created here. We have obtained a number of approximations
to
(see wiki page), though numeric evidence indicates that the approximations are all very close to each other. (Many of these approximations come with a correction term
, but thus far it seems that we may be able to avoid having to use this refinement to the approximations.) The effective approximation
also comes with an effective error bound
for some explicit (but somewhat messy) error terms : see this wiki page for details. The original approximations
can be considered deprecated at this point in favour of the (slightly more complicated) approximation
; the approximation
is a simplified version of
which is not quite as accurate but might be useful for testing purposes.
It is convenient to normalise everything by an explicit non-zero factor . Asymptotically,
converges to 1; numerically, it appears that its magnitude (and also its real part) stays roughly between 0.4 and 3 in the range
, and we seem to be able to keep it (or at least the toy counterpart
) away from zero starting from about
(here it seems that there is a useful trick of multiplying by Euler-type factors like
to cancel off some of the oscillation). Also, the bounds on the error
seem to be of size about 0.1 or better in these ranges also. So we seem to be on track to be able to rigorously eliminate zeroes starting from about
or so. We have not discussed too much what to do with the small values of
; at some point our effective error bounds will become unusable, and we may have to find some more faster ways to compute
.
In addition to this main direction of inquiry, there have been additional discussions on the dynamics of zeroes, and some numerical investigations of the behaviour Lehmer pairs under heat flow. Contributors are welcome to summarise any findings from these discussions from previous threads (or on any other related topic, e.g. improvements in the code) in the comments below.
Kevin Ford, Sergei Konyagin, James Maynard, Carl Pomerance, and I have uploaded to the arXiv our paper “Long gaps in sieved sets“, submitted to J. Europ. Math. Soc..
This paper originated from the MSRI program in analytic number theory last year, and was centred around variants of the question of finding large gaps between primes. As discussed for instance in this previous post, it is now known that within the set of primes , one can find infinitely many adjacent elements
whose gap
obeys a lower bound of the form
where denotes the
-fold iterated logarithm. This compares with the trivial bound of
that one can obtain from the prime number theorem and the pigeonhole principle. Several years ago, Pomerance posed the question of whether analogous improvements to the trivial bound can be obtained for such sets as
Here there is the obvious initial issue that this set is not even known to be infinite (this is the fourth Landau problem), but let us assume for the sake of discussion that this set is indeed infinite, so that we have an infinite number of gaps to speak of. Standard sieve theory techniques give upper bounds for the density of that is comparable (up to an absolute constant) to the prime number theorem bounds for
, so again we can obtain a trivial bound of
for the gaps of
. In this paper we improve this to
for an absolute constant ; this is not as strong as the corresponding bound for
, but still improves over the trivial bound. In fact we can handle more general “sifted sets” than just
. Recall from the sieve of Eratosthenes that the elements of
in, say, the interval
can be obtained by removing from
one residue class modulo
for each prime up to
, namely the class
mod
. In a similar vein, the elements of
in
can be obtained by removing for each prime
up to
zero, one, or two residue classes modulo
, depending on whether
is a quadratic residue modulo
. On the average, one residue class will be removed (this is a very basic case of the Chebotarev density theorem), so this sieving system is “one-dimensional on the average”. Roughly speaking, our arguments apply to any other set of numbers arising from a sieving system that is one-dimensional on average. (One can consider other dimensions also, but unfortunately our methods seem to give results that are worse than a trivial bound when the dimension is less than or greater than one.)
The standard “Erdős-Rankin” method for constructing long gaps between primes proceeds by trying to line up some residue classes modulo small primes so that they collectively occupy a long interval. A key tool in doing so are the smooth number estimates of de Bruijn and others, which among other things assert that if one removes from an interval such as
all the residue classes
mod
for
between
and
for some fixed
, then the set of survivors has exceptionally small density (roughly of the order of
, with the precise density given by the Dickman function), in marked contrast to the situation in which one randomly removes one residue class for each such prime
, in which the density is more like
. One generally exploits this phenomenon to sieve out almost all the elements of a long interval using some of the primes available, and then using the remaining primes to cover up the remaining elements that have not already been sifted out. In the more recent work on this problem, advanced combinatorial tools such as hypergraph covering lemmas are used for the latter task.
In the case of , there does not appear to be any analogue of smooth numbers, in the sense that there is no obvious way to arrange the residue classes so that they have significantly fewer survivors than a random arrangement. Instead we adopt the following semi-random strategy to cover an interval
by residue classes. Firstly, we randomly remove residue classes for primes
up to some intermediate threshold
(smaller than
by a logarithmic factor), leaving behind a preliminary sifted set
. Then, for each prime
between
and another intermediate threshold
, we remove a residue class mod
that maximises (or nearly maximises) its intersection with
. This ends up reducing the number of survivors to be significantly below what one would achieve if one selects residue classes randomly, particularly if one also uses the hypergraph covering lemma from our previous paper. Finally, we cover each the remaining survivors by a residue class from a remaining available prime.
This is the third “research” thread of the Polymath15 project to upper bound the de Bruijn-Newman constant , continuing this previous thread. 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.
We are making progress on the following test problem: can one show that whenever
,
, and
? This would imply that
which would be the first quantitative improvement over the de Bruijn bound of (or the Ki-Kim-Lee refinement of
). Of course we can try to lower the two parameters of
later on in the project, but this seems as good a place to start as any. One could also potentially try to use finer analysis of dynamics of zeroes to improve the bound
further, but this seems to be a less urgent task.
Probably the hardest case is , as there is a good chance that one can then recover the
case by a suitable use of the argument principle. Here we appear to have a workable Riemann-Siegel type formula that gives a tractable approximation for
. To describe this formula, first note that in the
case we have
and the Riemann-Siegel formula gives
for any natural numbers , where
is a contour from
to
that winds once anticlockwise around the zeroes
of
but does not wind around any other zeroes. A good choice of
to use here is
In this case, a classical steepest descent computation (see wiki) yields the approximation
where
Thus we have
where
with and
given by (1).
Heuristically, we have derived (see wiki) the more general approximation
for (and in particular for
), where
In practice it seems that the term is negligible once the real part
of
is moderately large, so one also has the approximation
For large , and for fixed
, e.g.
, the sums
converge fairly quickly (in fact the situation seems to be significantly better here than the much more intensively studied
case), and we expect the first term
of the series to dominate. Indeed, analytically we know that
(or
) as
(holding
fixed), and it should also be provable that
as well. Numerically with
, it seems in fact that
(or
) stay within a distance of about
of
once
is moderately large (e.g.
). This raises the hope that one can solve the toy problem of showing
for
by numerically controlling
for small
(e.g.
), numerically controlling
and analytically bounding the error
for medium
(e.g.
), and analytically bounding both
and
for large
(e.g.
). (These numbers
and
are arbitrarily chosen here and may end up being optimised to something else as the computations become clearer.)
Thus, we now have four largely independent tasks (for suitable ranges of “small”, “medium”, and “large” ):
- Numerically computing
for small
(with enough accuracy to verify that there are no zeroes)
- Numerically computing
for medium
(with enough accuracy to keep it away from zero)
- Analytically bounding
for large
(with enough accuracy to keep it away from zero); and
- Analytically bounding
for medium and large
(with a bound that is better than the bound away from zero in the previous two tasks).
Note that tasks 2 and 3 do not directly require any further understanding of the function .
Below we will give a progress report on the numeric and analytic sides of these tasks.
— 1. Numerics report (contributed by Sujit Nair) —
There is some progress on the code side but not at the pace I was hoping. Here are a few things which happened (rather, mistakes which were taken care of).
- We got rid of code which wasn’t being used. For example, @dhjpolymath computed
based on an old version but only realized it after the fact.
- We implemented tests to catch human/numerical bugs before a computation starts. Again, we lost some numerical cycles but moving forward these can be avoided.
- David got set up on GitHub and he is able to compare his output (in C) with the Python code. That is helping a lot.
Two areas which were worked on were
- Computing
and zeroes for
around
- Computing quantities like
,
,
, etc. with the goal of understanding the zero free regions.
Some observations for ,
,
include:
does seem to avoid the negative real axis
(based on the oscillations and trends in the plots)
seems to be settling around
range.
See the figure below. The top plot is on the complex plane and the bottom plot is the absolute value. The code to play with this is here.
— 2. Analysis report —
The Riemann-Siegel formula and some manipulations (see wiki) give , where
where is a contour that goes from
to
staying a bounded distance away from the upper imaginary and right real axes, and
is the complex conjugate of
. (In each of these sums, it is the first term that should dominate, with the second one being about
as large.) One can then evolve by the heat flow to obtain
, where
Steepest descent heuristics then predict that ,
, and
. For the purposes of this project, we will need effective error estimates here, with explicit error terms.
A start has been made towards this goal at this wiki page. Firstly there is a “effective Laplace method” lemma that gives effective bounds on integrals of the form if the real part of
is either monotone with large derivative, or has a critical point and is decreasing on both sides of that critical point. In principle, all one has to do is manipulate expressions such as
,
,
by change of variables, contour shifting and integration by parts until it is of the form to which the above lemma can be profitably applied. As one may imagine though the computations are messy, particularly for the
term. As a warm up, I have begun by trying to estimate integrals of the form
for smallish complex numbers , as these sorts of integrals appear in the form of
. As of this time of writing, there are effective bounds for the
case, and I am currently working on extending them to the
case, which should give enough control to approximate
and
. The most complicated task will be that of upper bounding
, but it also looks eventually doable.
This is the second “research” thread of the Polymath15 project to upper bound the de Bruijn-Newman constant , continuing this previous thread. 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.
We now have the following proposition (see this page for a proof sketch) that looks like it can give a numerically feasible approach to bound :
Proposition 1 Suppose that one has parameters
obeying the following properties:
- All the zeroes of
with
are real.
- There are no zeroes
with
in the region
.
- There are no zeroes
with
and
.
Then one has
.
The first hypothesis is already known for up to about
(we should find out exactly what we can reach here). Preliminary calculations suggest that we can obtain the third item provided that
. The second hypothesis requires good numerical calculation for
, to which we now turn.
The initial definition of is given by the formula
where
This formula has proven numerically computable to acceptable error up until about the first hundred zeroes of , but degrades after that, and so other exact or approximate formulae for
are needed. One possible exact formula that could be useful is
where
and
and can be chosen arbitrarily. We are still trying to see if this can be implemented numerically to give better accuracy than the previous formula.
It seems particularly promising to develop a generalisation of the Riemann-Siegel approximate functional equation for . Preliminary computations suggest in particular that we have the approximation
where
Some very preliminary numerics suggest that this formula is reasonably accurate even for moderate values of , though further numerical verification is needed. As a proof of concept, one could take this approximation as exact for the purposes of seeing what ranges of
one can feasibly compute with (and for extremely large values of
, we will presumably have to introduce some version of the Odlyzko-Schönhage algorithm. Of course, to obtain a rigorous result, we will eventually need a rigorous version of this formula with explicit error bounds. It may also be necessary to add more terms to the approximation to reduce the size of the error.
Sujit Nair has kindly summarised for me the current state of affairs with the numerics as follows:
—
- We need a real milestone and work backward to set up intermediate goals. This will definitely help bring in focus!
- So far, we have some utilities to compute zeroes of
with a nonlinear solver which uses roots of
as an initial condition. The solver is a wrapper around MINPACK’s implementation of Powell’s method. There is some room for optimization. For example, we aren’t providing the solver with the analytical Jacobian which speeds up the computation and increases accuracy.
- We have some results in the output folder which contains the first 1000 roots of
for some small values of
, etc. They need some more organization and visualization.
We have a decent initial start but we have some ways to go. Moving forward, here is my proposition for some areas of focus. We should expand and prioritize after some open discussion.
- Short term Optimize the existing framework and target to have the first million zeros of
(for a reasonable range of
) and the corresponding plots. With better engineering practice and discipline, I am confident we can get to a few tens of millions range. Some things which will help include parallelization, iterative approaches (using zeroes of
to compute zeroes of
), etc.
- Medium term We need to explore better ways to represent the zeros and compute them. An analogy is the computation of Riemann zeroes up to height
. It is computed by computing the sign changes of
(page 119 of Edwards) and by exploiting the
speed up with the Riemann-Siegel formulation (over Euler-Maclaurin). For larger values of
, I am not sure the root solver based approach is going to work to understand the gaps between zeroes.
- Long term We also need a better understanding of the errors involved in the computation — truncation, hardware/software, etc.
Recent Comments