Skip to content

Watching Over the Zeroes

October 10, 2018
tags: , , , , , ,
by


How confident should we be that the Riemann Hypothesis is true?

Composite of src1, src2

Andrew Odlyzko and Herman te Riele, in a 1985 paper, refuted a once widely believed conjecture from 1885 that implies the Riemann Hypothesis. The belief began a U-turn in the 1940s, and by the late 1970s the community was convinced its refutation would come from algorithmic advances to bring the needed computation into a feasible range. Odlyzko and te Riele duly credit advances in algorithms—not mere computing power—for their refutation.

Today we consider reasons for and against a belief in the Riemann Hypothesis (RH), contrast them with the situation for {\mathsf{P = NP}}, and point out that there are numerous conjectures weaker than RH but wide open which an RH claimant might try to crack first.

The conjecture in question is named for Franz Mertens but was first made by Thomas Stieltjes in a letter to Charles Hermite. We have talked about it in some detail here and here. Shorn of detail, the Mertens conjecture has the form:

\displaystyle \text{For all } n\text{, } f(n) \leq g(n),

where {f(n)} and {g(n)} are computable—indeed {g(n) = \lfloor n^{1/2} \rfloor}. If any conjecture of this kind is false, it can be falsified by a finite computation that gives an {n_0} such that {f(n_0) > g(n_0)}.

Recall the RH says that all the zeroes of the analytically-continued complex function {\zeta(s)}, other than “trivial” ones {s = -2k} for integers {k \geq 1}, have the form {\frac{1}{2} + it} for some real {t}. There are statements of the same kind that are equivalent to RH, including this by Jeff Lagarias:

\displaystyle \text{For all } n \geq 1,~ \sum_{d~|~n} d \leq h_n + e^{h_n}\ln(h_n),\qquad\text{where}\qquad h_n = \sum_{r=1}^n \frac{1}{r}.

Enrico Bombieri, in his essay on RH for the Clay Mathematical Institute, details how RH (plus the condition that all the zeroes are simple) can be verified directly for {t} up to any fixed {T_0} by a finite computation. Odlyzko and te Riele and others have computed many zeroes to high precision, not only up to certain heights {T_0} but in regions around select much higher {T} values. Odlyzko and Arnold Schönhage designed an algorithm that enabled higher computations including Xavier Gourdon’s 2004 verification of RH for the first {10^{13}} zeroes and some higher patches.

Some Lessons

This work yields some further lessons that we feel are relevant to the current discussion over and what bearing Sir Michael Atiyah recent ideas may have on it.


{\bullet} Know the data. The key data in Odlyzko and te Riele’s computation came from their own extensive tabulation of zeroes of {\zeta}. Odlyzko’s tables are online.


{\bullet} Initial data may mislead. This is an old lesson but always bears repeating. The Mertens conjecture was initially believed based on its holding for incredibly many {n}. Now we know that all {n} up to {10^{14}} obey {f(n) \leq g(n)} and there are strong reasons for believing this continues through {n = 10^{20}} and maybe {10^{30}}.


{\bullet} Augment computation by proof. Odlyzko and te Riele did not simply search for a counterexample {n_0}. Instead their finite computation used a portion of their known zeroes, new lattice reduction techniques, and methods of complex analysis to prove that {f(n)} must somewhere rise above {1.06 g(n)}. In fact, no concrete {n_0} is yet known—only an upper bound of about {10^{40}} in a 2006 paper by te Riele with Tadej Kotnik.

This situation also still holds with regard to John Littlewood’s refutation of Bernhard Riemann’s further quasi-conjecture that the number {\pi(x)} of primes up to {x} is strictly bounded above by the log integral {Li(x) = \int_0^x (1/\ln t)dt}, which would imply the RH. He proved that {x_0} giving {\pi(x_0) > Li(x_0)} must exist, and his student Stanley Skewes at Cambridge extracted an astronomical but finite upper bound for {x_0} from the analytical techniques. The challenge of improving the bounds and maybe finding an {x_0} drew Alan Turing into drafting computational devices and methods for RH. See Odlyzko’s 2012 Turing Centennial slides for a blueprint of Turing’s “zeta machine” and his 2012 paper with Dennis Hejhal for much more.


{\bullet} Know the neighbors. Odlyzko and te Riele address the weaker form of the Mertens conjecture that asserts {f(n) = O(g(n))}. Stieltjes thought he had proved this. They give reasons to expect that expanding their methods and their zeta dataset will falsify this too by replacing the constant {1.06} to an arbitrarily high one. For a case in point, the paper with Kotnik also raised the constant to {1.218}.

The RH is, however, equivalent to {f(n) \leq g(n)^{1 + o(1)}}. Similarly, it is equivalent to

\displaystyle |Li(x) - \pi(x)| = x^{\frac{1}{2} + o(1)}.


This leads to a further remark. If there is a zero {s = \sigma + it} with {\frac{1}{2} < \sigma < 1} then {|Li(x) - \pi(x)|} sometimes exceeds {x^{\sigma}} and vice-versa. It has not even been proved that there are no zeroes with real part {\sigma = 0.9999999.} Such a partial result ought to be more tractable, for reasons including that the possible densities of zeroes {\sigma + it} are known to dwindle as {\sigma} approaches {1} (or {0} by symmetry), while at least 40% of the zeroes are known to be exactly on the line. Hence bounding {\sigma} strictly away from {1} ought to be a first step for an RH claimant that may yield easier verification—and even if that is the only thing proved it would still be a monumental advance.

Beliefs About the Riemann Hypothesis

The great RH may be solved or may not. But it is interesting to see that not all believe that the RH is true. Most papers on the RH are cautious about whether it is true or not. The original paper of Riemann called it “very probable.” Littewood famously stated his belief that the RH is false; Paul Turán disbelieved it and for most of his life so did Turing. The last main chapter of John Derbyshire’s 2003 book Prime Obsession is titled with a quote given him by Odlyzko:


Either it’s true, or it isn’t.

We in computer theory have our own Clay Problem, the {\mathsf{P=NP}} problem. While most seem to believe that {\mathsf{P}} is not equal to {\mathsf{NP}}, some do believe that it could be the case that {\mathsf{P=NP}}. One important difference from the RH is that neither side is known to be falsifiable or verifiable by a finite computation. We note the near-perfect balance between claims of {\mathsf{P=NP}} and claims of {\mathsf{P \neq NP}} on Gerhard Woeginger’s claims page. On the other hand, we noted above that a refutation of the RH that can be feasibly executed and checked might need to do argumentation rather than just a finite computation.
This suggests that it may be useful to treat the problems similarly and look at the reasons behind beliefs both for and against the RH. So let’s look at the usual arguments—we follow Wikipedia and a 2003 survey by Aleksandar Ivić on reasons to doubt the RH—with a view to how they are tending.


{\bullet } Several analogues of the RH over finite fields have already been proved. This is emphasized in nice detail by Bombieri’s essay and we defer to it.


{\bullet } Numerical evidence goes beyond verifying that the first 10 trillion zeroes obey the RH. Turing’s negative belief was not only that the RH is false but that past a certain point {T_0}, counterexamples would occur with non-negligible frequency. If so, then one could refute the RH by doing relatively less computation but starting at much higher values of {t}. Odlyzko and others have sampled such high regions and found many zeroes there. All of them obey the RH.

To be sure, there are reasons for believing that critical magnitudes for testing the RH have not yet been reached. And of course there are other conjectures in analytic number theory besides those mentioned above that have been supported by large amounts of numerical evidence yet have turned out to be false. So watch out. We note also this paper about numerical RH experiments with beautiful plots.


{\bullet } The probabilistic argument for the RH based on the behavior of the Möbius function. If it behaves roughly randomly, then the {x^{1/2 + o(1)}} bound mentioned above should hold and make the RH true. See, however, these remarks by Eric Bach and Jeffrey Shallit.


{\bullet } Odlyzko in 1987 opened a new avenue by deep statistical testing of a conjecture by Hugh Montgomery about correlations between pairs of zeroes of {\zeta}. This enhanced an observation by Freeman Dyson that the correlations are the same as for random Hermitian matrices from the Gaussian unitary ensemble (GUE) often used in physics. David Hilbert and George Pólya had earlier conjectured that the zeroes correspond to eigenvalues of some positive linear operator in a way that implies the RH. This led to a spurt of optimism, represented by a 2000 paper by John Brian Conrey on the “GUE Conjecture,” for finding such an operator. This 2015 survey by Marek Wolf gives more recent news. It is titled “Will a physicist prove the Riemann Hypothesis?” and its later sections may verge on the intuitions accompanying Sir Michael Atiyah’s claims about the RH.


{\bullet } A flip side about these correlations, however, starts with Derrick Lehmer’s 1956 observation of a phenomenon where two zeros are sometimes very close. This leads to a possible argument that the RH is false. In January of this year, Brad Rogers and Terence Tao turned up the heat on this connection by proving that the GUE conjecture entails the existence of infinitely many Lehmer pairs. Further, they showed that an equivalent form of the RH in terms that an asymptotically-defined numerical constant {\Lambda} being non-positive can in fact hold only if {\Lambda} is exactly zero. Intuitively this reduces the “margin of error” for the RH to hold—see also discussion in this earlier survey.

This last point brings us right back to our question about proving partial results toward the RH. A PolyMath project on bounding {\Lambda} from above has achieved {\Lambda \leq 0.22}, and a bound of {0.11} is known to follow if and when the RH is verified for {t} up to {5 \times 10^{19}}. There was previously a lower bound {\Lambda \geq -0.0000000000115}, a hair-breadth away from the critical value {0}. A partial result on the way to {\mathsf{NP \neq P}} would be proving that {\mathsf{SAT}} is not in time {n^{1 + o(1)}}. Proving such a just-above-linear lower bound for {\mathsf{SAT}} wouldn’t even be placing it outside of {\mathsf{P}} yet it would be monumental, just as would proving that no zero has real part above {0.999}. Claimers of {\mathsf{NP \neq P}} never seem to address such simple milestones, and the same seems to be true about RH claims that we have perused.

Open Problems

If we plotted community belief in the RH over time on a scale from 0% likely to 100% likely, what would the graph look like? Is it still ascending, or are there signs of its rounding over as with the (big-{O} form of the) Mertens conjecture? Odlyzko’s quote prompts us to wonder, has it ever touched the line of being 50-50?

Another issue: why do claimers always claim “it all”—why do they never claim a big partial result? Is this some deep psychological human trait?

[added Bach-Shallit reference for random argument]

from → All Posts, History, Ideas, News, Open Problems, P=NP, primes
10 Comments leave one →
  1. a permalink
    October 10, 2018 7:08 pm

    Unlikely RH is true and unlikely SAT is not in $O(n)$.

    Reply
  2. vegafrank permalink
    October 11, 2018 7:59 am

    See my proof of P = NP in

    https://www.academia.edu/37469408/P_versus_NP

    Thanks in advance…

    Reply
  3. Richard Harris permalink
    October 11, 2018 9:22 am

    Proof

    Q: \forall_{s \in \mathbb C}( (\zeta(s) = \sum^{\infty}_{n=1} n^{-s} = 0 \wedge Im(s) \ne 0) \implies Re(s) = 1/2)?
         
    (Plain version: Do all nontrivial roots of \zeta fall on the critical line?)
         
    (Short version: Is RH true?)

    A: yes

    P: vector form reveals — formally \zeta(s) = V(s) \bullet V(0) (Q. E. D.)

    (elaborations will immediately follow)

    — RH

    Reply
  4. Richard Harris permalink
    October 11, 2018 9:23 am

    Elaboration(terse)

    To represent \zeta in terms of vectors, vectors will have to be in the form where each dimension value is just one of the (infinite) terms in the \zeta summation, i.e. V(s) = (1^{-s}, \; 2^{-s}, \; 3^{-s}, \; ...). Besides, the dot (\bullet) can be nothing but the dot (product) to have \zeta(s) equal V(s) \bullet V(0).

    Obviously, \zeta(s) is zero iff s is root. Furthermore, V(s) and V(0) must be orthogonal to each other (for their inner product to be zero).

    The Hypothesis then becomes simply asking: Is it possible to move a vector in a same general direction when pulling it in opposite directions?

    (more elaborate versions below)

    — Zeta In Terms Of Vectors for RH

    Reply
  5. Richard Harris permalink
    October 11, 2018 9:25 am

    Exposition(detailed)

    Conventional wisdom seems to hold that 30 pages may barely contain needed lemmas, any of which a possible mini-volume itself, and 300 pages might not even be able to bring it to arguably elementary level. Therefore, a 3-page exposé ought to be impossible and the mere thought of a proof in just 3 words has to be an insult.

    We can not have anybody insulted; we need to bring it down to 1 morphemic unit:

    \zeta(s) = V(s) \bullet V(0)

    Due to my incompetence, exhibited through genuine failures over the years, in getting the above simple fact across, please do not expect too much. While mathematical prophecy is easily faked, it is wise to not, at a minimum, fake a bet of your house on it, even if it is no longer yours.

    Vector form in this context won’t allow ambiguity.

    To represent \zeta in terms of vectors, vectors will have to be in the form where each dimension value is just one of the (infinite) terms in the \zeta summation, i.e. V(s) = (1^{-s}, \; 2^{-s}, \; 3^{-s}, \; ...). In particular, V(0) = (1^{0}, \; 2^{0}, \; 3^{0}, \; ...) = (1, \; 1, \; 1, \; ...) is an identity vector. Besides, the dot (\bullet) can be nothing but the dot (product) to have \zeta(s) equal V(s) \bullet V(0). Therefore, “vector form reveals” can have no interpretation other than what is presented here, and the consequences aren’t going to be much flexible, either.

    In plain English: Once put into vector form, seen as \zeta(s) = V(s) \bullet V(0) for example, the triviality of the answer should be immediately obvious: \zeta(1/2 \pm it \pm \delta) = 0 only if $\delta = 0$.

    On the one hand, a faint notion (of vector form) should bring \zeta(1/2 \pm it \pm \delta) = [V(1/2 \pm it) \circ V(\pm \delta)] \bullet V(0), and on the other, the sight of it can leave no doubt as to what V, V(0), \circ or \bullet precisely stand for, and the basic notations of addition (+), multiplication (\times), term-wise product (\circ) and inner product (\bullet), either explicit or implied, can only be denounced as confusing through highly suspicious ulterior motive.

    People may remember the disguise of sequence in “Prime Obsession” when John Derbyshire just barely finished elaborating Weierstrass without invoking the name. If the representing vector (i.e. one representing the sequence) is constructed from the sequence such that the ith entry of the vector is just the ith in the sequence, then the corresponding series (i.e. sum of the sequence) is just the result of dot-product of that representing vector with a vector having the same number of entries all valued 1. In this sense, \zeta is ‘masked’ result, disguised by V(0) through inner product. This particular settlement of Riemann Hypothesis just takes observation of this simple and basic fact, turning \zeta into its vector representation for a trivial proof.

    Obviously, \zeta(s) is zero iff s is root. Furthermore, V(s) and V(0) must be orthogonal to each other (for their inner product to be zero), which is to say that, in such vector view, there is the obvious property: vector V(s) for any corresponding root s must be (on plane \mathscr{P}) perpendicular to the identity vector V(0), and vice versa.

    The Hypothesis then becomes simply asking: Is it possible to move a vector in a same general direction when pulling it in opposite directions?

    (If the reader already concludes, the rest can be skipped.)

    The commonsensical and analogical equivalent is a car parked at a spot. Is it possible, when moving northwest and southeast from that spot, for it to have pure (positive) northward shift in both movements? Interpreted into formal jargon: Is it possible to affect V(1/2 \pm it) in opposite directions by V(\delta) and by V(-\delta) (via Hadamard product \circ) to have it moved onto a certain plane \mathscr{P} in both cases? (1)

    In more formal settings, of course, the obvious thing is \zeta(1/2 \pm it \pm \delta) = V(1/2 \pm it \pm \delta) \bullet V(0) = [V(1/2 \pm it) \circ V(\pm \delta)] \bullet V(0) = 0, and the question, rephrased almost without rephrasing, is: Can that hold true if \delta is not zero? And more generically: Can it, for any x \in \mathbb{C} and non-zero real \delta, hold true that \zeta(x + \delta) = \zeta(x - \delta) = 0?

    In face of (1), V(1/2 \pm it), or V(x), faces a decisive moment: Is it orthogonal to V(0)?

    (If the reader needs to skip the rest, the rest can be skipped.)

    For a complete and formal write-up, please refer to EGG ?N OUR FACE (or if from-cover-to-cover experience is desired).

    A request may be put to zetaITOvectors@gmail.com for a copy of the proof(s) in PDF format (as well as LaTeX version of this set of expositions) if it is to be freely distributed, or is to be made freely accessible, to the general public.

    — Zeta In Terms Of Vectors for RH

    Reply
  6. abc permalink
    October 11, 2018 1:10 pm

    Another “proof” of the Riemann Hypothesis here: https://arxiv.org/abs/1810.02204

    Reply
  7. vznvzn permalink
    October 11, 2018 4:08 pm

    thx for covering the RH empirical work + recent polymath/ Tao drive. posted about it on reddit recently and some skeptical respondents denied it could have any relevance to studying RH. it would be really neat if you also looked into the ways that RH is reformulated into discrete problems that dont involve floating point arithmetic & all the imprecision difficulties that can entail. btw in my long travels thru various cyberspace corners have encountered some anti-empirical bias among professionals, itd be interesting to cultural- and psycho-analyze/ deconstruct that further also.

    Reply
  8. vznvzn permalink
    October 11, 2018 11:23 pm

    😎 ❗ :star: 😀 💡 <3 am browsing this great Chris King ref you cited with the beautiful RH plots. pg25-28 are on collatz and a generalization to the reals. King is one of the few mathematicians who isnt afraid to talk about a deep link between fractals and number theory, and the similarity of RH + collatz in this context. have remarked on the fractal aspects of Collatz for years on my blog. nice ref! thx for the tip! hope other continue to notice/ investigate/ build on these very deep/ extraordinary/ beautiful ideas. https://empslocal.ex.ac.uk/people/staff/mrwatkin/zeta/king2010.pdf there is some recent very notable work of Torquato et al that also finds crystallography fractal patterns in the primes, hope serious mathematicians take more notice. https://vzn1.wordpress.com/2018/09/26/atiyah-riemann-attack-post-mortem-autopsy-primes-torch-carried-on/

    Reply
  9. Sunkhirous Yadegar permalink
    October 15, 2018 11:50 am

    Odlyzko and Herman work assumes the 1/2 part , !!!

    Reply
  10. Javaid Aslam permalink
    October 17, 2018 11:48 pm

    Why are we seeing this new ad bar at the top of the browser? It just started couple of weeks ago. I see this in Firefox as well as in Chrome.

    Reply

Leave a Reply

Discover more from Gödel's Lost Letter and P=NP

Subscribe now to keep reading and get access to the full archive.

Continue reading