Chaitin, Thoughts on the Riemann Hypothesis

Thoughts on the Riemann Hypothesis

G. J. Chaitin,IBM Research

The simultaneous appearance in May 2003 of four books on the Riemann hypothesis (RH) provoked these reflections. We briefly discuss whether the RH should be added as a new axiom, or whether a proof of the RH might involve the notion of randomness.

New pragmatically-justified mathematical axioms that are not at all self-evident

Are there important mathematical propositions for which there is a considerable amount of computational evidence, evidence that is so persuasive that a physicist would regard them as experimentally verified? Yes, I believe there are.

Currently, the two best candidates* for useful new axioms of the kind that GÃ¶del and I propose that are justified pragmatically as in physics are:

• the P ¹ NP hypothesis in theoretical computer science that conjectures that many problems require an exponential amount of work to resolve, and

• the Riemann hypothesis concerning the location of the complex zeroes of the Riemann zeta-function

 z(s) º Ã¥nn-s = Ã?p 1/( 1 - p-s ). (Here n ranges over positive integers and p ranges over the primes.)**

Knowing the zeroes of the zeta function, i.e., the values of s for which z(s) = 0, tells us a lot about the smoothness of the distribution of prime numbers, as is explained in these four books:

• Marcus du Sautoy, The Music of the Primes, Harper Collins, 2003.

• John Derbyshire, Prime Obsession, Joseph Henry Press, 2003.

• Karl Sabbagh, The Riemann Hypothesis, Farrar, Strauss and Giroux, 2003.

• Julian Havil, Gamma, Princeton University Press, 2003.

(Supposedly this book is on Euler's constant g, not the RH, but ignore that.
Sections 15.6, 16.8 and 16.13 are particularly relevant to the discussion below.)

[*Yet another class of pragmatically-justified axioms are the large cardinal axioms or the axiom of determinacy used in set theory, as discussed in Mary Tiles, The Philosophy of Set Theory, Chapters 8 and 9.]

[**You start with this formula and then you get the full zeta function by analytic continuation.]

The Riemann zeta function is like my W number: it captures a lot of information about the primes in one tidy package. W on the other hand is a single real number that contains a lot of information about the halting problem.

Of the authors of the above four books on the RH, the one who takes GÃ¶del most seriously is du Sautoy, who has an entire chapter on GÃ¶del and Turing in his book. In that chapter on p. 181, du Sautoy raises the issue of whether the RH might require new axioms. On p. 182 he quotes GÃ¶del,* who specifically mentions that this might be the case for the RH. And on p. 202 of that chapter du Sautoy points out that if the RH is undecidable this implies that it's true, because if the RH were false it would be easy to confirm that a particular zero of the zeta function is in the wrong place.

[*Unfortunately du Sautoy does not identify the source of his GÃ¶del quote. I have been unable to find it in GÃ¶del's Collected Works.]

Later in his book, on pp. 256-257, du Sautoy again touches upon the issue of whether the RH might require a new axiom. He relates how Hugh Montgomery sought reassurance from GÃ¶del that a famous number-theoretic conjecture---it was the twin prime conjecture, which asserts that there are infinitely many pairs p, p + 2 that are both prime---does not require new axioms. GÃ¶del, however, was not sure. In du Sautoy's words, sometimes one needs "a new foundation stone to extend the base of the edifice" of mathematics, and this might conceivably be the case both for the twin prime conjecture and for the RH.

On the other hand, on pp. 128-131 du Sautoy tells the story of the Skewes number, an enormous number

10101034

that turned up in a proof that an important conjecture must fail for extremely large cases. The conjecture in question was Gauss's conjecture that the logarithmic integral Li(x) is always greater than the number p(x) of primes less than or equal to x. This was verified by direct computation for all x up to very large values, and was then refuted by Littlewood without exhibiting a counter-example, and finally by Skewes with his enormous upper bound on a counter-example, raising the horrendous possibility that even though Gauss's conjecture is wrong, we might never ever see a specific counter-example. In other words, we might never ever know a specific value of x for which Li(x) is less than p(x). This possibility would seem to pull the rug out from under all mathematical experimentation and computational evidence! However, I don't believe that it actually does.

The traditional view held by most mathematicians is that these two assertions, P ¹ NP and the RH, cannot be taken as new axioms, and cannot require new axioms, we simply must work much harder to prove them. According to the received view, we're not clever enough, we haven't come up with the right approach yet. This is very much the current consensus. However this majority view completely ignores* the incompleteness phenomenon discovered by GÃ¶del, by Turing, and extended by my own work on information-theoretic incompleteness. What if there is no proof?

In fact, new axioms can never be proved; if they can, they're theorems, not axioms. So they must either be justified by direct, primordial mathematical intuition, or pragmatically, because of their rich and important consequences, as is done in physics. And in line with du Sautoy's observation on p. 202, one cannot demand a proof that the RH is undecidable before being willing to add it as a new axiom, because such a proof would in fact yield the immediate corollary that the RH is true. So proving that the RH is undecidable is no easier than proving the RH, and the need to add the RH as a new axiom must remain a matter of faith. The mathematical community will never be convinced!**

[*As du Sautoy puts it, p. 181, "mathematicians consoled themselves with the belief that anything that is really important should be provable, that it is only tortuous statements with no valuable mathematical content that will end up being one of GÃ¶del's unprovable statements."]

[**The situation with respect to P ¹ NP may be different. In a paper "Consequences of an exotic definition for P = NP" to appear in Applied Mathematics and Computation, N. C. A. da Costa and F. A. Doria show that if ZFC (Zermelo-Fraenkel set theory + the axiom of choice) is consistent, then a version of P = NP is consistent with ZFC, so a version of P ¹ NP cannot be demonstrated within ZFC. It will be interesting to see the reaction of the theoretical computer science community to this paper.]

Someone recently asked me, "What's wrong with calling the RH a hypothesis? Why does it have to be called an axiom? What do you gain by doing that?" Yes, but that's beside the point, that's not the real issue. The real question is, Where does new mathematical knowledge come from?

Let me put it this way: Yes, I agree, mathematics and physics are different, but perhaps they are not as different as most people think, perhaps it's a continuum of possibilities. At one end, rigorous proofs, at the other end, heuristic plausibility arguments, with absolute certainty as an unattainable limit point.

I've been publishing papers defending this thesis for more than a quarter of a century,* but few are convinced by my arguments. So in a recent paper I've tried a new tactic. I use quotes from Leibniz, Einstein and GÃ¶del to make my case, like a lawyer citing precedents in court...

[*See, for example, the introductory remarks in my 1974 J. ACM paper.]

In spite of the fact that I regard the Riemann hypothesis as an excellent new-axiom candidate---whether GÃ¶del agrees or merely thinks that a new axiom might be needed to prove the RH, I'm not sure---let me briefly wax enthusiastic over a possible approach to a proof of the RH that involves randomness. Disclaimer: I'm not an expert on the RH. What I'm about to relate is definitely an outsider's first impression, not an expert opinion.

A possible attack on the Riemann hypothesis?

Here is a concrete approach to the RH, one that uses no complex numbers. It's a probabilistic approach, and it involves the notion of randomness! It's originally due to Stieltjes, who erroneously claimed to have proved the RH with a variant of this approach.

The MÃ¶bius m function is about as likely to be +1 or -1 (see Derbyshire, Prime Obsession, pp. 322-323).

 m(n) = 0 if k2 divides n, k > 1, = (-1)number of different prime divisors of n if n is square-free.

The RH is equivalent to assertion that as k goes from 1 to n, m(k) is positive as often as negative. More precisely, the RH is closely related to the assertion that the difference between

• the number of k from 1 to n for which m(k) = -1, and

• the number of k from 1 to n for which m(k) = +1

is of the order of square root of n, i.e., is bounded by a constant times the square root of n. This is the kind of behavior that one would expect if the sign of the m function were chosen at random using independent tosses of a fair coin.*

[*For a more precise idea of what to expect if the sign of the m function were chosen at random, see the chapter on the law of the iterated logarithm in Feller, An Introduction to Probability Theory and Its Applications, vol. 1, VIII.5 through VIII.7. See also Good and Churchhouse, 1968 and the remark on this paper in Odlyzko and te Riele, 1985.]

This is usually formulated in terms of the Mertens function M(n):

M(n) º Ã¥1 £ k £ nm(k).

According to Derbyshire, pp. 249-251,

M(n) = order of square root of n

implies the RH, but is actually stronger than the RH. The RH is equivalent to the assertion that for any e > 0,

M(n) = order of n1/2 + e.

This approach for a possible attack on the RH caught my eye while I was reading this May's crop of RH books. I have always had an interest in probabilistic methods in elementary number theory. This was one of the things that inspired me to come up with my definition of algorithmic randomness and to find algorithmic randomness in arithmetic in connection with diophantine equations. However, I doubt that this work on algorithmic randomness is directly applicable to the RH.

In particular, these two publications greatly interested me as a child:

I think that anyone contemplating a probabilistic attack on the RH via the m function should read these two publications. There is also some interesting work on random sieves, which are probabilistic versions of the sieve of Eratosthenes:

• D. Hawkins, "Mathematical sieves," Scientific American, December 1958, pp. 105-112.

As PÃ³lya shows in the above paper---originally American Mathematical Monthly 66, pp. 375-384---probabilistic heuristic reasoning can do rather well with the distribution of twin primes. By the way, this involves Euler's g constant. Can a refinement of PÃ³lya's technique shed new light on m and on the RH? I don't know, but I think that this is an interesting possibility.

By the way, P ¹ NP also involves randomness, for as Charles Bennett and John Gill showed in 1981---SIAM Journal on Computing 10, pp. 96-113---with respect (relative) to a random oracle A, PA¹ NPA with probability one.