# Is the Riemann Hypothesis equivalent to a $\Pi_1$ sentence?

1) Can the Riemann Hypothesis (RH) be expressed as a $\Pi_1$ sentence?

More formally,

2) Is there a $\Pi_1$ sentence which is provably equivalent to RH in PA?

### Update (July 2010):

So we have two proofs that the RH is equivalent to a $\Pi_1$ sentence.

1. Martin Davis, Yuri Matijasevic, and Julia Robinson, "Hilbert's Tenth Problem. Diophantine Equations: Positive Aspects of a Negative Solution", 1974.
Published in "Mathematical developments arising from Hilbert problems", Proceedings of Symposium of Pure Mathematics", XXVIII:323-378 AMS.
Page 335 $$\forall n >0 \ . \ \left(\sum_{k \leq \delta(n)}\frac{1}{k} - \frac{n^2}{2} \right)^2 < 36 n^3$$

2. Jeffrey C. Lagarias, "An Elementary Problem Equivalent to the Riemann Hypothesis", 2001 $$\forall n>60 \ .\ \sigma(n) < \exp(H_n)\log(H_n)$$

But both use theorems from literature that make it difficult to judge if they can be formalized in PA. The reason that I mentioned PA is that, for Kreisel's purpose, the proof should be formalized in a reasonably weak theory. So a new question would be:

3) Can these two proofs of "RH is equivalent to a $\Pi_1$ sentence" be formalized in PA?

### Motivation:

This is mentioned in P. Odifreddi, "Kreiseliana: about and around George Kreisel", 1996, page 257. Feferman mentions that when Kreisel was trying to "unwind" the non-constructive proof of Littlewood's theorem, he needed to deal with RH. Littlewood's proof considers two cases: there is a proof if RH is true and there is another one if RH is false. But it seems that in the end, Kreisel used a $\Pi_1$ sentence weaker than RH which was sufficient for his purpose.

### Why is this interesting?

Here I will try to explain why this question was interesting from Kreisel's viewpoint only.

Kreisel was trying to extract an upperbound out of the non-constructive proof of Littlewood. His "unwinding" method works for theorems like Littlewood's theorem if they are proven in a suitable theory. The problem with this proof was that it was actually two proofs:

1. If the RH is false then the theorem holds.
2. If the RH is true then the theorem holds.

If I remember correctly, the first one already gives an upperbound. But the second one does not give an upperbound. Kreisel argues that the second part can be formalized in an arithmetic theory (similar to PA) and his method can extract a bound out of it assuming that the RH is provably equivalent to a $\Pi_1$ sentence. (Generally adding $\Pi_1$ sentences does not allow you to prove existence of more functions.) This is the part that he needs to replace the usual statement of the RH with a $\Pi_1$ statement. It seems that at the end, in place of proving that the RH is $\Pi_1$, he shows that a weaker $\Pi_1$ statement suffices to carry out the second part of the proof, i.e. he avoids the problem in this case.

A simple application of proving that the RH is equivalent to a $\Pi_1$ sentences in PA is the following: If we prove a theorem in PA+RH (even when the proof seems completely non-constructive), then we can extract an upperbound for the theorem out of the proof. Note that for this purpose, we don't need to know whether the RH is true or is false.

Note: Feferman's article mentioned above contains more details and reflections on "Kreisel's Program" of "unwinding" classical proofs to extract constructive bounds. My own interest was mainly out of curiosity. I read in Feferman's paper that Kreisel mentioned this problem and then avoided it, so I wanted to know if anyone has dealt with it.

-
How do you formulate RH in PA? For a Pi_1 statement equivalent to RH in ZFC, see this paper by Jeff Lagarias, An elementary problem equivalent to the Riemann hypothesis, Amer. Math. Monthly , 109 (2002), 534--543. math.lsa.umich.edu/~lagarias/zeta.html – François G. Dorais Jul 14 '10 at 13:01
Feferman says that Kreisel is not clear about this. Kreisel claims that proofs in large parts of the theory of functions of a complex variable can be presented in a arithmetical system he calls $Z_\mu$ and then moves to constructive approximations to zeros of analytic functions. So it seems to me that he is using the computable functions to approximate the roots of zeta function to express RH. But again, there are no details on how he formalizes these in the language of arithmetic. – Kaveh Jul 14 '10 at 13:31
Thank you for the link. I haven't finished reading it but it seems to me that the problem E in the paper is easily expressible in the language of PA. It would be nice if the proof is also formalizable in PA (or a conservative extension of it). – Kaveh Jul 14 '10 at 13:40
(I'm posting my comment as a partial answer.) – François G. Dorais Jul 14 '10 at 15:42
François G. Dorais and Andres Caicedo have both given partial answers to my question. I think checking that the proofs can be formalized in PA may need more serious work. I would prefer to accept both of the answers, but there is only one accepted answer, so I guess it is more appropriate to accept the first one. Thank you. – Kaveh Jul 15 '10 at 12:26

I don't know the best way to express RH inside PA, but the following inequality $$\sum_{d \mid n} d \leq H_n + \exp(H_n)\log(H_n),$$ where $H_n = 1+1/2+\cdots+1/n$ is the $n$-th harmonic number, is known to be equivalent to RH. [J. Lagarias, An elementary problem equivalent to the Riemann hypothesis, Amer. Math. Monthly, 109 (2002), 5347–543.] The same paper mentions another inequality of Robin, $$\sum_{d \mid n} d \leq e^\gamma n \log\log n \qquad (n \geq 5041),$$ where $e^\gamma = 1.7810724\ldots$, which is also equivalent to RH. Despite the appearance of $\exp,$ $\log$ and $e^\gamma$, it is a routine matter to express these inequalities as $\Pi^0_1$ statement. (Indeed, the details in Lagarias's paper make this even simpler than one would originally think.)

-
Oh, yes, that's a nice article. For some reason I thought it was older. – Andrés Caicedo Jul 14 '10 at 15:59
I think that a reasonable way to state RH in the first-order language of arithmetic is $|\pi(x)-Li(x)| = O(\sqrt{x} \ln x)$. It's not too much of a stretch to say that this estimate is "why we care" about RH, so I think it's just as good as (if not better than!) the more familiar statement about the zeros of $\zeta(s)$. – Timothy Chow Jul 15 '10 at 4:33
Lagarias says that for your first equation, the inequality needs to be strict for n >= 1. And the paper also uses a strict inequality for the second equation. Once the inequalities are strict it is no longer a routine matter to express the inequalities as $\Pi$^0_1. – Russell O'Connor Jul 15 '10 at 8:54
It seems to me that it should not be difficult, as we can use the error estimates for the approximations of $\exp$ and $\log$ to solve the problem of strictness you mentioned. – Kaveh Jul 15 '10 at 12:00
@Russel O'Connor: Actually rhs not being an integer would suffice, since lhs is an integer, but I see your point, strict inequality is an $\Sigma_1$ (r.e.) relation over real numbers. I checked the proof again, and it seems that the theorem mentioning the inequality is strict for $1<n$ is just an extra, since if I am not making a mistake (again), they show that the RH implies the strict form, but to prove the RH it suffices to use the weak inequality version. – Kaveh Jul 15 '10 at 13:16

Yes. This is a consequence of the Davis-Matiyasevich-Putnam-Robinson work on Hilbert's 10th problem, and some standard number theory. A number of papers have details of the $\Pi^0_1$ sentence. To begin with, take a look at the relevant paper in Mathematical developments arising from Hilbert's problems (Proc. Sympos. Pure Math., Northern Illinois Univ., De Kalb, Ill., 1974), Amer. Math. Soc., Providence, R. I., 1976.

-
Thanks for the reference. Lagarias' paper also notes that this paper by M. Davis, Y. Matijasevic, and Julia Robinson (DMR 1974) give an elementary ($\Pi_1$) equivalent of the RH. Kreisel's outlines of a direct proof is also mentioned in DMR 1974, p. 334. They give an alternative indirect proof that the RH is equivalent to a $\Pi_1$ formula. Unfortunately, their proof is also using theorems from literature that (like Lagarias' paper) makes it unclear if the equivalence is provable in PA. The list of theorems they are using is on page 335. – Kaveh Jul 15 '10 at 11:55

Andres Caicedo's answer is the correct one, but my comment is too big to fit in a comment box.

Here is a Haskell program that exhibits the Riemann Hypothesis:

rh :: Integer -> Bool
rh n = (h - n'^2/2)^2 < 36*n'^3
where
n' = toRational n
h = sum [1/toRational k|k <- [1..d]]
d = product [product [e j|j <- [2..m]] | m <- [2..n-1]]
e x = foldr gcd 0 [a|a <- [2..x], x mod a == 0]


The Riemann Hypothesis is equivalent to saying that the program rh returns True on all positive inputs. This equivalence is, of course, mathematical equivalence and not logical equivalence. Once we prove or disprove the Riemann Hypothesis it will be known to be mathematically equivalent to a $\Delta^0_0$ statement.

-
+1 for giving an actual program – Daniel Miller Jul 11 '13 at 2:07
Nice! Could you give a reference for the equivalence with RH? – Hanno Becker Oct 19 '14 at 8:24

One can write a program that, given enough time, will eventually detect the presence of zeros off the critical line if any exist, by computing contour integrals of $\zeta' (s)/ \zeta(s)$ on a sequence of small squares (with rational vertices) exhausting increasingly fine finite grids that cover more and more of the critical strip to greater and greater height.

From the formulae for analytic continuation of $\zeta (s)$ one can extract effective moduli of uniform continuity and from that one can approximate the integral by dividing each side of the square into some large number of equal pieces, approximating the function at those rational points, and calculating the Riemann sum. The necessary accuracy can be determined from the modulus of continuity and formulas for $\zeta$.

(The grids I have in mind come within $1/n$ of the sides of the critical strip, with height going from $0$ to $n$, and are divided into squares of size $1/n^2$, so eventually any zero will be isolated inside one such square.)

EDIT: to express RH in Peano Arithmetic, there are two ways.

One is to use Matiyasevich (sp?) theorem that for any halting problem one can construct a Diophantine equation whose solvability is equivalent to halting. Or in the same vein, use Matiyasevich/Robinson approach to Diophantine encode an elementary inequality equivalent to RH, as was done in Matiyasevich-Davis-Robinson's paper on Hilbert's 10th Problem: Positive Aspects of a Negative Solution. Another way is to express enough complex analysis in Peano Arithmetic to carry the contour integral argument above, which can be done because ultimately everything involves formulas and estimates that can be made sufficiently explicit. How to do this is explained in Gaisi Takeuti's essay Two Applications Of Logic to Mathematics.

EDIT-2: re: verifications of RH, the ZetaGrid distributed computation checked that at least the first 100 billion (10^11) zeros, ordered by imaginary part, are on the critical line. The zero computations are opposite to the $\Pi_1$ approach: instead of falsifying RH if it's wrong, if run for unlimited time they would validate RH as far as the program can reach, but could get stuck if there are double zeros anywhere. The algorithms assume RH and whatever other conjectures are useful for finding zeros, such as the absence of multiple roots, or GUE spacings between zeros. Every time they locate another zero, a contour integral then verifies that there are no other zeros up to that height, and RH continues to hold. But if there is a double zero the program could get stuck in an endless attempt to show that it's a single zero. Single zeros off the line would be detected by most algorithms, but not necessarily localized: once you know one is there you can take a big gulp and run a separate program to find it precisely.

(Concerning the philosophical interest of the $\Pi_1$ formulation of RH, see also the comments under the question.)

-

I realized that none of the answers present what I consider to be the most straightforward $\Pi^0_1$ expression for the Riemann hypothesis, namely bounds on the error term in the prime number theorem. I will write it in terms of Chebyshev’s $\psi$ function as I find it more natural, but it works for $\pi$ just the same. The following are equivalent:

1. The Riemann hypothesis.

2. $\psi(x)-x=O(x^{1/2+\epsilon})$ for all $\epsilon>0$.

3. $|\psi(x)-x|\le\frac1{8\pi}\sqrt x\log^2 x$ for all $x\ge74$.

The equivalence of 1 and 2 is classical, the explicit bound in 3 is due to Schoenfeld. Now, the large leeway between 2 and 3 allows one to write the bound as a $\Pi^0_1$ sentence, even though we cannot compute exactly all the logarithms involved: let $\mathrm{psi}(n)$, $\mathrm{sqrt}(n)$, and $\mathrm l(n)$ be computable functions that provide rational approximations within distance $1$ of $\psi(n)$, $\sqrt n$, and $\log n$, respectively. Then RH is equivalent to $$\forall n\,|\mathrm{psi}(n)-n|\le42+\mathrm{sqrt}(n)\,\mathrm l(n)^2.$$

The beauty of this is not only that it is in line with the form of RH most likely to be useful in elementary number theoretic arguments, but perhaps more importantly, it easily generalizes to extensions of the RH to other $L$-functions.

For a specific formulation, Section 5.7 of Iwaniec and Kowalski’s Analytic number theory states for a large class of $L$-functions (basically, functions in the Selberg class with a polynomial Euler product; the assumptions are somewhat negotiable, in particular I’m confident one can eliminate the Ramanujan–Petersson hypothesis at the expense of somewhat worse bounds) the equivalence of

1. The Riemann hypothesis for $L(s)$.

2. $\psi_L(x)-n_Lx=O(x^{1/2+\epsilon})$ for all $\epsilon>0$.

3. $|\psi_L(x)-n_Lx|\le c\sqrt x\,(\log x)\log(x^dq_L)$.

Here $c$ is an absolute constant that can (in principle) be extracted from the proof, $d$ is the degree of the Euler product, $n_L$ is the order of the pole of $L(s)$ at $s=1$, $q_L$ is a conductor of sorts, and $$\psi_L(x)=\sum_{n\le x}\Lambda_L(n),$$ where $\Lambda_L(n)$ is a “von Mangoldt” function of $L$ extracted from the expansion of the logarithmic derivative of $L$ as a Dirichlet series: $$-\frac{L'(s)}{L(s)}=\sum_{n=1}^\infty\Lambda_L(n)\,n^{-s}.$$ The upshot is that the RH for a class of $L$-functions is $\Pi^0_1$, provided the class is “recursively enumerable”: we can parametrize the class as $L(s,a)$ where the $a$’s are finite objects (including basic data like $d,n_L,q_L$) in such a way that the set of valid $a$’s is r.e., and given $a$, $n$, and $\epsilon>0$, we can compute an approximation of $\Lambda_L(n)$ within distance $\epsilon$ (or equivalently, if we can approximately compute terms of the Euler product).

For example, each of the following can be expressed as a $\Pi^0_1$ sentence:

• The RH for Dirichlet $L$-functions.

• The RH for Dedekind zeta-functions.

• The RH for Hecke $L$-functions.

(The first two classes can be enumerated in a straightforward way. Finite-order Hecke characters are also easily enumerable, as ray class groups are finite and computable. The case of general Hecke characters needs a bit more work, but basically, one can enumerate a basis of suitably normalized infinity types using an effective version of Dirichlet’s unit theorem.)

I can’t tell (but would be interested to hear from someone more knowledgeable) whether the RH for standard automorphic $L$-functions is also $\Pi^0_1$, that is, whether these functions are recursively enumerable. (There are certainly only countably many up to normalization, and polynomially many of bounded analytic conductor, so conceivably this may be true.)

-