Skip to the Main Content

Note:These pages make extensive use of the latest XHTML and CSS Standards. They ought to look great in any standards-compliant modern browser. Unfortunately, they will probably look horrible in older browsers, like Netscape 4.x and IE 4.x. Moreover, many posts use MathML, which is, currently only supported in Mozilla. My best suggestion (and you will thank me when surfing an ever-increasing number of sites on the web which have been crafted to use the new standards) is to upgrade to the latest version of your browser. If that's not possible, consider moving to the Standards-compliant and open-source Mozilla browser.

September 7, 2019

The Riemann Hypothesis (Part 1)

Posted by John Baez

I’ve been trying to understand the Riemann Hypothesis a bit better. Don’t worry, I’m not trying to prove it — that’s a dangerous quest. Indeed Ricardo Pérez-Marco has a whole list of things not to do if you want to prove the Riemann Hypothesis, such as:

Don’t expect that the problem consists in resolving a single hard difficulty. In this kind of hard problem many enemies are on your way, well hidden, and waiting for you.

and

Don’t go for it unless you have succeeded in other serious problems. “Serious problems” means problems that have been open and well known for years. If you think that the Riemann Hypothesis will be your first major strike, you probably deserve failure.

Taken together, his pieces of advice are sufficiently discouraging that he almost could have just said “don’t try to prove the Riemann Hypothesis”.

But trying to understand what it means, and how people have proved vaguely similar conjectures — that seems like a more reasonable hobby.

In what follows I want to keep things as simple as possible, because I’m finding, as I study this stuff, that people are generally too eager to dive into technical details before sketching out ideas in a rough way. But I will skip over a lot of standard introductory stuff on the Riemann zeta function, since that’s easy to find.

Of course the Riemann Hypothesis says that the Riemann zeta function has zeros only at negative even integers (the ‘trivial zeros’) and on the line Re(z)=1/2Re(z) = 1/2 (the ‘nontrivial zeros’). The function looks simple enough that it’s surprising nobody has settled this. But still, the skeptic might ask: is solving this really worth a million dollars? Is this problem famous just because it’s hard?

If you dig a bit deeper you’ll see that the Riemann Hypothesis implies or is equivalent to a lot of nice statements in number theory. These reveal a bit more about why it matters. I’d summarize them all by saying that prime numbers are distributed as nicely as they could be. For example, if the number of primes n\le n is π(n)\pi(n), the Prime Number Theorem says that a pretty good approximation to π(n)\pi(n) is

li(n)= 0 ndtlnt li(n) = \int_0^n \frac{dt}{\ln t}

More precisely, it says

lim nπ(n)li(n)=1 \lim_{n \to \infty} \frac{\pi(n) }{li(n)} = 1

But the Riemann Hypothesis says more about how good this approximation is! The Riemann Hypothesis is equivalent to

|li(n)π(n)|Cnln(n) \big|\li(n) - \pi(n)\big| \le C \sqrt{n} \; \ln(n)

for some C>0C > 0 for all nn.

I bet someone has given a heuristic argument for this by assuming the primes are ‘randomly distributed’ in some reasonable way. If so, the Riemann Hypothesis says there aren’t ‘unreasonably large fluctuations’ in the distribution of primes.

One can sharpen this idea to a crazy level of precision: in 1976 Schoenfeld showed the Riemann Hypothesis is equivalent to

|li(n)π(n)|18πnln(n)foralln2657 \big|\li(n) - \pi(n)\big| \le \frac{1}{8 \pi} \sqrt{n}\; \ln(n) \; for \; all n \ge 2657

That’s impressive. But I don’t think this particular statement, including the number 2657, gets us much closer to the deep inner meaning of the Riemann Hypothesis.

If you dig into how the zeros of the zeta function are connected to the distribution of primes, you soon meet Riemann’s explicit formula. This is a formula for π(x)\pi(x) as a sum over zeros of the zeta function. The trivial zeros give a simple approximation to π(x)\pi(x), while the nontrivial zeros contribute a bunch of corrections. Each of these corrections is an ever-growing wave-like function, whose frequency and rate of growth depends on the location of that zero!

So, we could say the prime numbers and the nontrivial zeros of the Riemann zeta function give the ‘particle’ and ‘wave’ pictures of the same phenomenon… where I’m alluding to ideas from quantum mechanics, and the Fourier transform. This analogy seems to be fairly deep, and maybe I’ll say more about it sometime.

More poetically, we could say the Riemann zeta zeros reveal the ‘music of the primes’. That’s one of the guiding metaphors of this book:

  • Barry Mazur and William Stein, Prime Numbers and the Riemann Hypothesis, Cambridge U. Press, Cambridge, 2016.

and I really recommend this book if you want to get a feeling for Riemann’s explicit formula without sinking into technicalities.

Before I show you Riemann’s explicit formula, let me show you a movie of how it works:

Here J. Laurie Snell, Bill Peterson, Jeanne Albert and Charles Grinstead show what happens when you start with the simple approximation to π(x)\pi(x) and then add up the waves coming from the first 500 nontrivial zeros of the Riemann zeta function.

That movie is really fun. I must have watched it dozens of times by now. And if you look carefully you’ll see some interesting things.

First, you can see a version of the Gibbs phenomenon: the strong oscillations near the primes, where π(x)\pi(x) takes a step up. But this is something you should always expect when trying to approximate a step function with a sum of smooth waves.

More subtly, there are little ‘glitches’ at the prime powers. Why is that? Well, it’s because Riemann’s explicit formula starts out life as a formula not for π(x)\pi(x) but another function Π(x)\Pi(x). This counts not only all primes but all prime powers x\le x, but in a funny way: it counts a prime power p np^n as worth 1/n1/n. So, for example, Π(6)=312\Pi(6) = 3\frac{1}{2} since there are 3 primes less than 6, but also the prime power 2 22^2.

From Riemann’s explicit formula for Π(x)\Pi(x) you can work out one for π(x)\pi(x). But the prime powers still maintain a ghostly presence as ‘glitches’, which only go away in the limit where you add up all the waves.

What are these waves, exactly? It’s easiest to give the formula for Π(x)\Pi(x). Here’s the formula:

Π(x)=li(x)ln2+ x dtt(t 21)lnt ρli(x ρ) \Pi(x) = li(x) - \ln 2 + \int_x^\infty \frac{d t}{t(t^2 - 1)\ln t} - \sum_\rho li(x^{\rho})

where ρ\rho are the nontrivial zeros of the Riemann zeta function. The scary integral is due to the trivial zeros of the zeta function, but let’s ignore that! I only want you to look at the sum over the nontrivial zeros.

The lili function makes everything more complicated, so just think about x ρx^{\rho}. If we assume the Riemann Hypothesis, the real part of ρ\rho is always 1/21/2, so

ρ=12+iσ \rho = \frac{1}{2} + i \sigma

with σ\sigma real, so

x ρ=x 1/2x iσ x^{\rho} = x^{1/2} x^{ i \sigma}

In short, this function grows like x\sqrt{x} but also oscillates at a rate depending on σ\sigma. (You may wonder how Π(x)\Pi(x) gets to be real, but that’s because the nontrivial zeros come in complex conjugate pairs.)

So, if the Riemann Hypothesis is true, we know these correction terms li(x ρ)\li(x^{\rho}) grow at a known rate, and that helps experts get good estimates on Π(x)\Pi(x) and then the prime counting function π(x)\pi(x). But if the Riemann Hypothesis is false, all this gets ruined. There will then be zeros with real part greater than 1/2, and these will give correction terms that grow faster.

That last paragraph was extremely superficial, mainly because of my ignorance. But there’s a reason for my ignorance: when I reached this point, I decided that this direction was not the most interesting.

What I really wanted to know is why the Riemann Hypothesis should be true. I figured that to get some sense of this, I should look at the Weil Conjectures, which are a kind of baby version of the Riemann Hypothesis. Unlike the Riemann Hypothesis, these conjectures have actually been proved. So we have some idea why they’re true!

Like the Riemann Hypothesis, these conjectures describe ‘wave-like corrections’ to a simple formula for counting something: not primes, but points on an algebraic variety over a finite field. Again, there’s one such correction for each zero (or pole) of some kind of zeta function. But in this case there’s an actual explanation for the location of the zeta function zeros! So there’s a good reason that they lie where they do. And it turns out to be quite mind-blowing.

That’s what I really wanted to talk about today. But I see that my preparatory throat-clearing has gone on so long that at least one more blog post will be required.

In the meantime, you can watch another video of how the prime counting function π(x)\pi(x) gets approximated by waves coming from the nontrivial zeta zeros:

It’s interesting to me how the whole curve sways up and down. I’m not sure what causes that.

Posted at September 7, 2019 8:00 AM UTC

TrackBack URL for this Entry:   https://golem.ph.utexas.edu/cgi-bin/MT-3.0/dxy-tb.fcgi/3139

17 Comments & 0 Trackbacks

Re: The Riemann Hypothesis (Part 1)

Have you seen this blog post by Scott Aaronson?

We discussed his work on the Busy Beaver problem somewhere and this Turing Machine design was a bonus from that work.

Apart from the techniques for Optimising turing machine design it uses the fact that it is possible to state the Riemann Hypothesis very simply (low on the arithmetical hierarchy).

Posted by: Roger Witte on September 8, 2019 5:22 PM | Permalink | Reply to this

Re: The Riemann Hypothesis (Part 1)

Thanks! I hadn’t seen that post by Scott, but I had been wondering a lot whether the Riemann Hypothesis was Π 1\Pi_1, and finally someone showed me a paper by Yuri Matiyasevich pointing to a proof by Georg Kreisel that this is true. This means that if it’s not satisfied in some model of ZFC, we can find, in that model, the Gödel number of a disproof.

(People usually summarize this by saying “if it’s false, it’s provably false”, but I try to avoid talking in terms of a “standard model” of the natural numbers in which all “true” sentences are satisfied, because I don’t know how to tell which sentences are “true”.)

Unfortunately I’m not finding that paper by Matiyasevich now… but instead, to my amazement, I found that in 2007–2009 he wrote two papers on the Riemann Hypothesis.

Posted by: John Baez on September 9, 2019 4:06 AM | Permalink | Reply to this

Re: The Riemann Hypothesis (Part 1)

Is the Riemann Hypothesis equivalent to a Π 1\Pi_1 sentence?

has the references you were looking for.

The relevant search term is ‘absolute’.

An absolute sentence is one whose truth cannot be changed using Cohen’s forcing technique.

I don’t like your comment about not knowing which model of PA is true because it is irrelevant. All models of PA have an initial segment equivalent to ‘true natural numbers’ whatever that is. So long as the Godel number is in that initial segment, we’ll be fine. But if the Reimann Hypothesis is false, the Godel Number disproof will be in the initial segment. If it isn’t in the initial segment, the Turing machine doesn’t halt.

However I think the work by Aaronson et al is deeper than just the number theoretic results produced.

Firstly they demystify Godel numbering by identifying it with the relationship between a text and it’s relationship to the corresponding bit sequence in ASCII

Then they write a programming language and a compiler that compiles the language into turing machine states. This emphasises that the fancy turing machine is now a household item (very nearly - machines are still finite)

I am wondering if another side effect of this work is to identify the arithmetic (or algebraic) hierarchy directly with computational complexity classes.

Posted by: Roger Witte on September 9, 2019 10:21 PM | Permalink | Reply to this

Re: The Riemann Hypothesis (Part 1)

Roger wrote:

I don’t like your comment about not knowing which model of PA is true because it is irrelevant.

That’s what I expect most people to feel, and of course none of this stuff has anything to do with what I’m trying to talk about in this series of posts, so I should probably let this issue drop.

However, I have trouble letting things drop.

All models of PA have an initial segment equivalent to ‘true natural numbers’ whatever that is. So long as the Gödel number is in that initial segment, we’ll be fine. But if the Riemann Hypothesis is false, the Gödel Number disproof will be in the initial segment.

Let me see if I’m confused.

The concept of ‘model’ invokes set theory. Let’s suppose the Riemann Hypothesis is independent of ZFC. Then both ZFC + RH and ZFC + ¬\negRH are consistent. We can use either of these as a version of set theory in which to do mathematics.

In either of these set theories, we can define the concept of ‘model of PA’, and there will exist models. In either one there will be a ‘standard model’ of PA, which is the unique (up to isomorphism) model of PA that embeds as an initial segment in all models. We call elements of the standard model ‘standard natural numbers’.

I believe that in ZFC + RH, the standard model will contain no counterexample to RH (re-expressed as a Π 1\Pi_1 sentence).

I believe that if in ZFC + ¬\negRH, the standard model will contain a counterexample to RH.

Am I mixed up?

Posted by: John Baez on September 11, 2019 4:58 PM | Permalink | Reply to this

Re: The Riemann Hypothesis (Part 1)

I believe that in ZFC + RH, the standard model will contain no counterexample to RH (re-expressed as a Π₁ sentence).

I believe that if in ZFC + ¬RH, the standard model will contain a counterexample to RH.

Am I mixed up?

No, that’s exactly right!

The easiest way to avoid the issues observed by Mike is to just think of RH as a Π1 sentence, that is as a sentence starting with a universal quantifier followed by some quantifier-free formula. By “quantifier-free”, logicians don’t quite mean the literal “no quantifiers may appear”: Bounded quantifiers, as in “for all numbers less than …” or “there exists a number less than …” are still okay.

For quantifier-free formulas, the issue mentioned by Mike cannot arise. That is, if a quantifier-free formula is true (with respect to some meta theory), then there already exists (as judged by the meta theory) a proof in the extremely weak Robinson arithmetic (Peano arithmetic without any form of induction).

One small addition:

The concept of ‘model’ invokes set theory.

This is only true if interpreted literally (“a model consists of a set together with … such that …”). The notion of a “model” also makes sense in different backgrounds, such as type theory (where we would define “a model consists of a type together with …”) and even in the language of arithmetic.

Posted by: Ingo Blechschmidt on September 17, 2019 9:15 PM | Permalink | Reply to this

Re: The Riemann Hypothesis (Part 1)

Thanks!

In my discussions of this stuff I’m taking a traditional model theorist’s attitude, and considering only set-based models of first-order theories, unless I say otherwise.

(This is not because I think that’s the best approach. It’s mainly because I’m busy learning this sort of model theory with Michael Weiss.)

Posted by: John Baez on September 18, 2019 5:40 AM | Permalink | Reply to this

Re: The Riemann Hypothesis (Part 1)

I am confused by this at a more basic level. RH is a universal statement: all zeros have property P. Assuming classical logic, therefore, its negation is an existential statement: there exists a zero that does not have property P. So if it is false, there is a counterexample. Is the point that in some model VV of ZFC there might — in theory, before we know that RH is Π 1\Pi_1 — be a zero, say zz, such that zz is a counterexample (in VV) but for which VV does not contain the Gödel code of a proof that zz is a counterexample?

In particular, does the phrase “we can find” mean anything different than “there exists”? (Maybe the fact that I have to ask that question means I’ve been hanging out with constructivists too much.)

Posted by: Mike Shulman on September 11, 2019 9:43 PM | Permalink | Reply to this

Re: The Riemann Hypothesis (Part 1)

Mike wrote:

Is the point that in some model VV of ZFC there might — in theory, before we know that RH is Π 1\Pi_1 — be a zero, say zz, such that zz is a counterexample (in VV) but for which VV does not contain the Gödel code of a proof that zz is a counterexample?

I guess there are a few things to worry about. I wasn’t thinking about this! But now I am.

Let me make your worry less counterfactual by replacing the zeta function by any other computable function ff from some open set of \mathbb{C} to \mathbb{C}. (Computable real functions are defined here and computable complex functions are defined similarly. We can define what it means for a complex function to be computable on an open set, and the zeta function is computable on its domain of definition, {1}\mathbb{C} - \{1\}.)

Suppose in some model VV of ZFC there exists zz \in \mathbb{C} with f(z)=0f(z) = 0 and Re(z)1/2Re(z) \ne 1/2. Could there be no Gödel number of a proof that f(z)=0f(z) = 0 and Re(z)1/2Re(z) \ne 1/2?

First of all, if zz is not definable in ZFC then we can’t even expressf(z)=0f(z) = 0” in the language of ZFC. So “nn is the Gödel number of a proof that f(z)=0f(z) = 0 and Re(z)1/2Re(z) \ne 1/2” doesn’t even make sense.

But let’s suppose zz is definable, so “nn is the Gödel number of a proof that f(z)=0f(z) = 0 and Re(z)1/2Re(z) \ne 1/2” makes sense. Then my instinct is that sure, there might not be any such nn. I haven’t found a computable ff that realizes this situation, though.

It helps my intuition to assume zz is not just definable but computable. I think all the zeros of the Riemann zeta function are computable. If zz is computable and Re(z)1/2Re(z) \ne 1/2 then it is provable in ZFC that Re(z)0Re(z) \ne 0. However, even if ff and zz are computable, I don’t see why f(z)=0f(z) = 0 should be provable. We might be able to find for each nn a proof that |f(z)|1/n|f(z)| \le 1/n, yet not be able to organize all these proofs into a single proof that n|f(z)|1/n\forall n |f(z)| \le 1/n.

I’m not sure I answered your question. But I think my answer was “yes”.

In particular, does the phrase “we can find” mean anything different than “there exists”? (Maybe the fact that I have to ask that question means I’ve been hanging out with constructivists too much.)

I’m using classical logic in my comments here, so I was simply using “we can find” to mean “there exists” when I said:

This means that if RH (translated into a Π 1\Pi_1 statement in the language of arithmetic) is not satisfied in some model of ZFC, we can find, in that model, the Gödel number of a disproof.

But I think we could write a program that would cough up this Gödel number. I think if the counterexample to RH is a ‘standard’ natural number this Gödel number will be standard, otherwise not.

Posted by: John Baez on September 12, 2019 3:51 AM | Permalink | Reply to this

Re: The Riemann Hypothesis (Part 1)

the Riemann Hypothesis says that the Riemann zeta function has zeros only at negative odd integers (the ‘trivial zeros’) and on the line Re(𝑧)=1/2 (the ‘nontrivial zeros’)

(Surely you mean the negative even integers… otherwise, I have a very nice counterexample.)

Posted by: Jon on September 8, 2019 10:10 PM | Permalink | Reply to this

Re: The Riemann Hypothesis (Part 1)

Fixed… before I even saw your comment! (Otherwise I’d feel very ashamed.)

Posted by: John Baez on September 9, 2019 3:27 AM | Permalink | Reply to this

Re: The Riemann Hypothesis (Part 1)

As of this writing, it’s not yet fixed. (I just hit refresh to make sure.) Feel free to delete this comment at any time!

Posted by: Owen Biesel on September 11, 2019 1:42 PM | Permalink | Reply to this

Re: The Riemann Hypothesis (Part 1)

Ugh, I must be messing around with too many versions on my laptop. I’ll leave your comment here to help explain to readers what happened. It’s really fixed now.

I apologize to another reader whose re-correction I deleted, thinking I’d already fixed the problem.

Posted by: John Baez on September 11, 2019 4:29 PM | Permalink | Reply to this

Re: The Riemann Hypothesis (Part 1)

Thank you for posting the charts - they make it so much easier to undestand the concepts than looking at a page full of symbols. Hope someone can prove it one day.

Posted by: Rhiana on September 9, 2019 2:29 AM | Permalink | Reply to this

Looking forward to the mind-blowing sequel. Looked through the Weil Conjectures but it didn’t jump out at me.

Posted by: Jim Walters on September 9, 2019 5:34 PM | Permalink | Reply to this

The Weil Conjectures are normally explained in a way that’s hard to understand. Unfortunately the sequel will require further sequels to be truly mind-blowing, but I hope the key idea — ‘oscillatory correction terms’ — is clearly explained.

Posted by: John Baez on September 10, 2019 1:22 PM | Permalink | Reply to this

Re: The Riemann Hypothesis (Part 1)

I sketched a quick simple derivation of Riemann’s “Jump” function for the primes at https://tcjpn.wordpress.com/2011/11/22/jx/ presenting Riemann’s jump function for counting the primes as introduced in H. M. Edward’s Riemann’s Zeta Function (Dover, 2001), couched in terms of the Dirac delta function and the inverse Mellin transform.

Posted by: Tom Copeland on September 15, 2019 4:11 PM | Permalink | Reply to this

Re: The Riemann Hypothesis (Part 1)

Nice! Not as loquacious as I’d like, but nice.

Posted by: John Baez on September 16, 2019 10:12 AM | Permalink | Reply to this

Post a New Comment