60
$\begingroup$

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.

$\endgroup$
17
  • 8
    $\begingroup$ 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 $\endgroup$ Jul 14, 2010 at 13:01
  • 2
    $\begingroup$ 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. $\endgroup$
    – Kaveh
    Jul 14, 2010 at 13:31
  • 1
    $\begingroup$ @BCnrd: Sorry, but I don't see what speculation you are referring to. The question was obviously not about making progress on the RH, and I don't know if these formulations are of any interest in that regard. As I mentioned in the question, Kreisel's motivation was completely different. The statement that the RH has a $\Pi_1$ equivalent provably in PA (or weaker theories) is interesting in itself for different reasons. $\endgroup$
    – Kaveh
    Jul 16, 2010 at 2:19
  • 2
    $\begingroup$ @BCnrd: the interest of reformulating RH in this way is to answer the question of whether RH is falsifiable, in the sense that there is a computer program that (given unlimited time and memory) would find a counterexample if one exists. This is not manifest in the original complex analysis formulation. It would be philosophically interesting if a subject as concrete as number theory had coronated as its centerpiece a conjecture with no falsifiable equivalent. This has nothing to do with progress toward solving RH, but is a side question with a life of its own. $\endgroup$
    – T..
    Jul 22, 2010 at 6:46
  • 2
    $\begingroup$ the simplest way to formulate the RH is with the Mertens function $M(1) = 1, M(n) = 1-\sum_{k=1}^{n-1} M(\lfloor n/k \rfloor)$ to ask for $|M(n)| < C n^{1/2+\epsilon}$ $\endgroup$
    – reuns
    Mar 1, 2016 at 2:46

5 Answers 5

42
$\begingroup$

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.)

$\endgroup$
17
  • $\begingroup$ Oh, yes, that's a nice article. For some reason I thought it was older. $\endgroup$ Jul 14, 2010 at 15:59
  • 14
    $\begingroup$ 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)$. $\endgroup$ Jul 15, 2010 at 4:33
  • 2
    $\begingroup$ 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. $\endgroup$ Jul 15, 2010 at 8:54
  • 1
    $\begingroup$ 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. $\endgroup$
    – Kaveh
    Jul 15, 2010 at 12:00
  • 2
    $\begingroup$ @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. $\endgroup$
    – Kaveh
    Jul 15, 2010 at 13:16
36
$\begingroup$

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.)

$\endgroup$
6
  • $\begingroup$ Is there an equivalent like 3 but with the theta function instead of psi? $\endgroup$
    – EGME
    Apr 30, 2022 at 23:25
  • $\begingroup$ @EGME Sure, it can be formulated with $\theta$ or $\pi$ instead of $\psi$. $\endgroup$ May 1, 2022 at 6:49
  • $\begingroup$ Would you have a reference? Thank you! $\endgroup$
    – EGME
    May 1, 2022 at 7:51
  • $\begingroup$ It's the same argument as in the answer. $\endgroup$ May 1, 2022 at 8:29
  • 2
    $\begingroup$ As I write in the answer, the equivalence of 1 to 2 is well known and can be found in any number of basic texts, while the equivalence of 1 and 2 to 3 is due to Schoenfeld. Meaning, Lowell Schoenfeld, Sharper bounds for the Chebyshev functions $\theta(x)$ and $\psi(x)$, II, Mathematics of Computation 30 (1974), no. 134, pp. 337–360. For $\theta$, 3 can be formulated as $|\theta(x)-x|\le\frac1{8\pi}\sqrt x(\log x)^2$ for all $x\ge599$. $\endgroup$ May 1, 2022 at 8:51
32
$\begingroup$

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.


Update, Jun 22/16: Interest in recent work of Scott Aaronson and Adam Yedidia on small Turing machines whose behavior is not decidable in $\mathsf{ZFC}$ had the side effect of leading to explicit examples of Turing machines that halt if and only if there is a counterexample to Riemann's hypothesis. One such machine is described (with links) starting on page 11 of their paper, using Lagarias equivalence mentioned in François's answer. A short discussion (in Spanish), also providing the relevant links, can be seen here. The results were announced in Scott's blog, here.

$\endgroup$
1
  • 1
    $\begingroup$ 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. $\endgroup$
    – Kaveh
    Jul 15, 2010 at 11:55
29
$\begingroup$

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.

$\endgroup$
4
  • 3
    $\begingroup$ +1 for giving an actual program $\endgroup$ Jul 11, 2013 at 2:07
  • $\begingroup$ Nice! Could you give a reference for the equivalence with RH? $\endgroup$
    – Hanno
    Oct 19, 2014 at 8:24
  • $\begingroup$ This is the M. Davis, Y. Matijasevic, and Julia Robinson (DMR 1974) equivalence that is cited by Andres Caicedo's answer as well as in a few other places on this page. $\endgroup$ May 3, 2017 at 14:02
  • $\begingroup$ Isn't any sentence that is proved or disproved mathematically equivalent to a $\Delta_0^0$ statement, i.e., $\bot$ or $\top$? $\endgroup$ Feb 24, 2019 at 8:57
19
$\begingroup$

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.)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.