You are currently browsing the monthly archive for April 2019.
The Polymath15 paper “Effective approximation of heat flow evolution of the Riemann function, and a new upper bound for the de Bruijn-Newman constant“, submitted to Research in the Mathematical Sciences, has just been uploaded to the arXiv. This paper records the mix of theoretical and computational work needed to improve the upper bound on the de Bruijn-Newman constant . This constant can be defined as follows. The function
where is the Riemann function
has a Fourier representation
where is the super-exponentially decaying function
The Riemann hypothesis is equivalent to the claim that all the zeroes of are real. De Bruijn introduced (in different notation) the deformations
of ; one can view this as the solution to the backwards heat equation starting at . From the work of de Bruijn and of Newman, it is known that there exists a real number – the de Bruijn-Newman constant – such that has all zeroes real for and has at least one non-real zero for . In particular, the Riemann hypothesis is equivalent to the assertion . Prior to this paper, the best known bounds for this constant were
with the lower bound due to Rodgers and myself, and the upper bound due to Ki, Kim, and Lee. One of the main results of the paper is to improve the upper bound to
At a purely numerical level this gets “closer” to proving the Riemann hypothesis, but the methods of proof take as input a finite numerical verification of the Riemann hypothesis up to some given height (in our paper we take ) and converts this (and some other numerical verification) to an upper bound on that is of order . As discussed in the final section of the paper, further improvement of the numerical verification of RH would thus lead to modest improvements in the upper bound on , although it does not seem likely that our methods could for instance improve the bound to below without an infeasible amount of computation.
We now discuss the methods of proof. An existing result of de Bruijn shows that if all the zeroes of lie in the strip , then ; we will verify this hypothesis with , thus giving (1). Using the symmetries and the known zero-free regions, it suffices to show that
whenever and .
For large (specifically, ), we use effective numerical approximation to to establish (2), as discussed in a bit more detail below. For smaller values of , the existing numerical verification of the Riemann hypothesis (we use the results of Platt) shows that
for and . The problem though is that this result only controls at time rather than the desired time . To bridge the gap we need to erect a “barrier” that, roughly speaking, verifies that
for , , and ; with a little bit of work this barrier shows that zeroes cannot sneak in from the right of the barrier to the left in order to produce counterexamples to (2) for small .
To enforce this barrier, and to verify (2) for large , we need to approximate for positive . Our starting point is the Riemann-Siegel formula, which roughly speaking is of the shape
where , is an explicit “gamma factor” that decays exponentially in , and is a ratio of gamma functions that is roughly of size . Deforming this by the heat flow gives rise to an approximation roughly of the form
where and are variants of and , , and is an exponent which is roughly . In particular, for positive values of , increases (logarithmically) as increases, and the two sums in the Riemann-Siegel formula become increasingly convergent (even in the face of the slowly increasing coefficients ). For very large values of (in the range for a large absolute constant ), the terms of both sums dominate, and begins to behave in a sinusoidal fashion, with the zeroes “freezing” into an approximate arithmetic progression on the real line much like the zeroes of the sine or cosine functions (we give some asymptotic theorems that formalise this “freezing” effect). This lets one verify (2) for extremely large values of (e.g., ). For slightly less large values of , we first multiply the Riemann-Siegel formula by an “Euler product mollifier” to reduce some of the oscillation in the sum and make the series converge better; we also use a technical variant of the triangle inequality to improve the bounds slightly. These are sufficient to establish (2) for moderately large (say ) with only a modest amount of computational effort (a few seconds after all the optimisations; on my own laptop with very crude code I was able to verify all the computations in a matter of minutes).
The most difficult computational task is the verification of the barrier (3), particularly when is close to zero where the series in (4) converge quite slowly. We first use an Euler product heuristic approximation to to decide where to place the barrier in order to make our numerical approximation to as large in magnitude as possible (so that we can afford to work with a sparser set of mesh points for the numerical verification). In order to efficiently evaluate the sums in (4) for many different values of , we perform a Taylor expansion of the coefficients to factor the sums as combinations of other sums that do not actually depend on and and so can be re-used for multiple choices of after a one-time computation. At the scales we work in, this computation is still quite feasible (a handful of minutes after software and hardware optimisations); if one assumes larger numerical verifications of RH and lowers and to optimise the value of accordingly, one could get down to an upper bound of assuming an enormous numerical verification of RH (up to height about ) and a very large distributed computing project to perform the other numerical verifications.
This post can serve as the (presumably final) thread for the Polymath15 project (continuing this post), to handle any remaining discussion topics for that project.
Just a brief announcement that the AMS is now accepting (until June 30) nominations for the 2020 Joseph L. Doob Prize, which recognizes a single, relatively recent, outstanding research book that makes a seminal contribution to the research literature, reflects the highest standards of research exposition, and promises to have a deep and long-term impact in its area. The book must have been published within the six calendar years preceding the year in which it is nominated. Books may be nominated by members of the Society, by members of the selection committee, by members of AMS editorial committees, or by publishers. (I am currently on the committee for this prize.) A list of previous winners may be found here. The nomination procedure may be found at the bottom of this page.
Joni Teräväinen and I have just uploaded to the arXiv our paper “Value patterns of multiplicative functions and related sequences“, submitted to Forum of Mathematics, Sigma. This paper explores how to use recent technology on correlations of multiplicative (or nearly multiplicative functions), such as the “entropy decrement method”, in conjunction with techniques from additive combinatorics, to establish new results on the sign patterns of functions such as the Liouville function . For instance, with regards to length 5 sign patterns
of the Liouville function, we can now show that at least of the possible sign patterns in occur with positive upper density. (Conjecturally, all of them do so, and this is known for all shorter sign patterns, but unfortunately seems to be the limitation of our methods.)
The Liouville function can be written as , where is the number of prime factors of (counting multiplicity). One can also consider the variant , which is a completely multiplicative function taking values in the cube roots of unity . Here we are able to show that all sign patterns in occur with positive lower density as sign patterns of this function. The analogous result for was already known (see this paper of Matomäki, Radziwiłł, and myself), and in that case it is even known that all sign patterns occur with equal logarithmic density (from this paper of myself and Teräväinen), but these techniques barely fail to handle the case by itself (largely because the “parity” arguments used in the case of the Liouville function no longer control three-point correlations in the case) and an additional additive combinatorial tool is needed. After applying existing technology (such as entropy decrement methods), the problem roughly speaking reduces to locating patterns for a certain partition of a compact abelian group (think for instance of the unit circle , although the general case is a bit more complicated, in particular if is disconnected then there is a certain “coprimality” constraint on , also we can allow the to be replaced by any with divisible by ), with each of the having measure . An inequality of Kneser just barely fails to guarantee the existence of such patterns, but by using an inverse theorem for Kneser’s inequality in this previous paper of mine we are able to identify precisely the obstruction for this method to work, and rule it out by an ad hoc method.
The same techniques turn out to also make progress on some conjectures of Erdös-Pomerance and Hildebrand regarding patterns of the largest prime factor of a natural number . For instance, we improve results of Erdös-Pomerance and of Balog demonstrating that the inequalities
and
each hold for infinitely many , by demonstrating the stronger claims that the inequalities
and
each hold for a set of of positive lower density. As a variant, we also show that we can find a positive density set of for which
for any fixed (this improves on a previous result of Hildebrand with replaced by . A number of other results of this type are also obtained in this paper.
In order to obtain these sorts of results, one needs to extend the entropy decrement technology from the setting of multiplicative functions to that of what we call “weakly stable sets” – sets which have some multiplicative structure, in the sense that (roughly speaking) there is a set such that for all small primes , the statements and are roughly equivalent to each other. For instance, if is a level set , one would take ; if instead is a set of the form , then one can take . When one has such a situation, then very roughly speaking, the entropy decrement argument then allows one to estimate a one-parameter correlation such as
with a two-parameter correlation such as
(where we will be deliberately vague as to how we are averaging over and ), and then the use of the “linear equations in primes” technology of Ben Green, Tamar Ziegler, and myself then allows one to replace this average in turn by something like
where is constrained to be not divisible by small primes but is otherwise quite arbitrary. This latter average can then be attacked by tools from additive combinatorics, such as translation to a continuous group model (using for instance the Furstenberg correspondence principle) followed by tools such as Kneser’s inequality (or inverse theorems to that inequality).
(This post is mostly intended for my own reference, as I found myself repeatedly looking up several conversions between polynomial bases on various occasions.)
Let denote the vector space of polynomials of one variable with real coefficients of degree at most . This is a vector space of dimension , and the sequence of these spaces form a filtration:
A standard basis for these vector spaces are given by the monomials : every polynomial in can be expressed uniquely as a linear combination of the first monomials . More generally, if one has any sequence of polynomials, with each of degree exactly , then an easy induction shows that forms a basis for .
In particular, if we have two such sequences and of polynomials, with each of degree and each of degree , then must be expressible uniquely as a linear combination of the polynomials , thus we have an identity of the form
for some change of basis coefficients . These coefficients describe how to convert a polynomial expressed in the basis into a polynomial expressed in the basis.
Many standard combinatorial quantities involving two natural numbers can be interpreted as such change of basis coefficients. The most familiar example are the binomial coefficients , which measures the conversion from the shifted monomial basis to the monomial basis , thanks to (a special case of) the binomial formula:
thus for instance
More generally, for any shift , the conversion from to is measured by the coefficients , thanks to the general case of the binomial formula.
But there are other bases of interest too. For instance if one uses the falling factorial basis
then the conversion from falling factorials to monomials is given by the Stirling numbers of the first kind :
thus for instance
and the conversion back is given by the Stirling numbers of the second kind :
thus for instance
If one uses the binomial functions as a basis instead of the falling factorials, one of course can rewrite these conversions as
and
thus for instance
and
As a slight variant, if one instead uses rising factorials
then the conversion to monomials yields the unsigned Stirling numbers of the first kind:
thus for instance
One final basis comes from the polylogarithm functions
For instance one has
and more generally one has
for all natural numbers and some polynomial of degree (the Eulerian polynomials), which when converted to the monomial basis yields the (shifted) Eulerian numbers
For instance
These particular coefficients also have useful combinatorial interpretations. For instance:
- The binomial coefficient is of course the number of -element subsets of .
- The unsigned Stirling numbers of the first kind are the number of permutations of with exactly cycles. The signed Stirling numbers are then given by the formula .
- The Stirling numbers of the second kind are the number of ways to partition into non-empty subsets.
- The Eulerian numbers are the number of permutations of with exactly ascents.
These coefficients behave similarly to each other in several ways. For instance, the binomial coefficients obey the well known Pascal identity
(with the convention that vanishes outside of the range ). In a similar spirit, the unsigned Stirling numbers of the first kind obey the identity
and the signed counterparts obey the identity
The Stirling numbers of the second kind obey the identity
and the Eulerian numbers obey the identity
Recent Comments