60

The question is contained in the title; I mean the standard axioms ZFC. The wiki link: Riemann hypothesis. There are finite algorithms allowing one to decide if there are non-trivial zeroes of the $\zeta$-function in the domains whose union exhausts the whole strip $0<\Re z<1$, but this does not seem to be the obstacle for undecidability. Are there other arguments?

Community
  • 1
Shaqq
  • 609
  • Are you sure those finite algorithms allow one to decide (as in, will definitely give either a "YES" or "NO" answer) whether or not there are non-trivial zeros? Or do they just semidecide (as in, will say "YES" if the answer is "YES", but run forever if the answer is "NO") or some such thing? – Sridhar Ramesh Nov 01 '11 at 07:40
  • I meant a countable collection of finite domains, in which the number of zeroes can be found by integrating the logarithm of $\zeta$ along the boundaries. Since the result is an integer, it suffices to calculate the integral, say, up to 0.4, and thus a finite algorithm exists for each domain. – Shaqq Nov 01 '11 at 08:14
  • Oh, but then, to know that there are NO zeros would require checking each of infinitely many domains. So, yes, this gives an algorithm to semi-decide for the existence of non-trivial zeros, which establishes the Riemann Hypothesis as a $\Pi_1$-statement (and thus disprovable if false), but doesn't rule out the possibility of undecidability altogether. – Sridhar Ramesh Nov 01 '11 at 08:17
  • By the way: is there a distinction between "undecidable" and "true but unprovable"? When I mentioned the former, I meant the latter; I admit a lack of my education in this area. – Shaqq Nov 01 '11 at 09:16
  • 7
    @Shaqq: undecidable means “neither provable nor refutable”. In particular, an undecidable statement may also be false (but not refutable). OTOH, in principle, a true but unprovable statement may be refutable and therefore decidable (if ZFC is not a sound theory). Finally, it is much better to say “independent” instead of “undecidable”, since the latter word is also used to mean “not computable by an algorithm” in recursion theory, and an awful lot of people get thoroughly confused by mixing these two unrelated terms. – Emil Jeřábek Nov 01 '11 at 11:58
  • 1
    related: Is the RH equivalent to a $\Pi_1$ sentence? – Kaveh Nov 01 '11 at 16:50
  • 1
    A working link: http://mathoverflow.net/questions/31846 . – Emil Jeřábek Nov 01 '11 at 17:41
  • @Emil: I should have formulated my question more carefully, I meant only the situation from the previous discussion. Let me repeat: assume that there is an algorithm that stops if the conjecture is false and does not stop otherwise, like for the domains exhausting the strip for the Riemann hypothesis. As far as I understand now, then there is no distinction between 'true but not provable' and 'undecidable=independent on the axioms under consideration'. Please correct me if I am wrong. – Shaqq Nov 01 '11 at 19:41
  • 25
    Whether or not it is logically possible that the Riemann hypothesis is undecidable, I submit that there is no good reason to believe it is undecidable. "Gosh, people have been trying to prove it for a while without success" is not a good reason - that philosophy has been incorrect on a bazillion theorems so far. – Greg Martin Nov 01 '11 at 20:21
  • @Greg: I agree that the reason you quoted is not a good reason. But note that Martin Davis reason below is more complicated than this. – godelian Nov 01 '11 at 21:26
  • In what way? From the quote in your answer, Martin Davis's reason seems to amount to "Brilliant mathematicians, including Paul Cohen, have tried to prove it for a while without success. Wouldn't it be great if it were independent from [whatever]?" – Sridhar Ramesh Nov 01 '11 at 22:16
  • Actually, if someone proved that the Riemann Hypothesis was unprovable, that would mean that it is impossible to find a zero on the critical strip. Wouldn't that imply then, that the Hypothesis is true? – Matthias Ludewig Nov 01 '11 at 23:36
  • @Sridhar: Well, it's clear for me from what he said that he supports Gödel's views at the mentioned lecture regarding this issue, and it is from that perspective that he answers. As I understand him, it is not unreasonable to suspect that (for instance) ZFC is simply not enough, and that possibility should be considered as seriously as the possibility that RH is actually decidable. He also confess he would like it to be undecidable, but that's another thing. – godelian Nov 02 '11 at 00:18
  • By the way, I believe it is relevant at this point to mention that the notes from Gödel's lecture Martin Davis referred to appear in the 3rd volume of "Kurt Gödel - Collected works", pp. 304. There is also an introduction to them by George Boolos. – godelian Nov 02 '11 at 00:22
  • 1
    @Shaqq: The way you formulated it, there always such an algorithm: let A be the algorithm which immediately halts, and B the algorithm which goes into an infinite loop. Then either A or B satisfies your condition. What you need for the equivalence of “true but unprovable” with “independent” is that (1) there is one fixed algorithm A such that ZFC proves that A halts iff the conjecture fails, and (2) the assumption that ZFC is sound (whatever it proves is true). – Emil Jeřábek Nov 02 '11 at 11:03
  • 3
    @Kofi: I suppose you meant to say that the negation of the Riemann hypothesis was unprovable. Yes, this would imply that RH is true, but it is quite a mess to verify this directly using definition: you have to prove first that “find a [nontrivial] zero on the critical strip” is something you can certify by a finite object. This can be done for example by fixing a rectangle $c$ with Gaussian rational endpoints, disjoint from the critical line, such that the integral of $\zeta'/\zeta$ over $c$ is nonzero, provided you show that you can approximate the integral with sufficient accuracy, ... – Emil Jeřábek Nov 02 '11 at 11:15
  • 1
    ... which in turn requires you to show that you can compute approximation of $\zeta$ and $\zeta'$ to suitable accuracy and so on. That’s why this property may be established more easily using another equivalent formulation of the Hypothesis, such as in Sridhar’s answer. – Emil Jeřábek Nov 02 '11 at 11:18
  • If you developed an axiomatic system where i could be evaluated to a natural number, then RH would be a trivial proof by induction. Because evaluating i is not allowed, RH will never be solved. – D J Sims Jul 10 '16 at 23:28

5 Answers5

67

I do not know anything about zero-finding algorithms for $\zeta$, so I will make only one small remark which doesn't require such knowledge: If the Riemann Hypothesis is false, then it is provably false (in ZFC, or any similar system).

This is because Robin's theorem tells us that the Riemann hypothesis is equivalent to the assertion that, for every natural $n \geq 5041$, the sum of the divisors of $n$ is less than $e^{\gamma} n \log{\log{n}}$; since there are programs which calculate this latter quantity to arbitrary precision, and thus can verify whether this inequality holds for any given $n$, we find that the Riemann hypothesis is a $\Pi_1$ statement: it is equivalent to the assertion that some computer program never outputs "NO" on any input. (Although not familiar with the proofs of Robin's theorem, etc., I assume they can be carried out in ZFC, and thus establish the relevant equivalence within ZFC.). There may be more direct ways to establish that the Riemann hypothesis is a $\Pi_1$ statement, such as by knowledge of algorithms which enumerate to arbitrary precision the zeros of $\zeta$, but at any rate, there is this one.

Accordingly, if the Riemann hypothesis is false, then the relevant computer program does output "NO" on some input, from which it would follow that ZFC proves that that computer program outputs "NO" on that input, and thus ZFC would prove the Riemann hypothesis to be false.

The possibility still remains, however, as far as I know, that the Riemann hypothesis may be true but unprovable in ZFC.

Sridhar Ramesh
  • 5,642
  • I have heard that the Riemann hypothesis cannot be true but unprovable in ZFC. But I have no access to the source anymore, that is why I ask my question here. – Shaqq Nov 01 '11 at 08:31
  • Lightface $\Pi_1$? – Not Mike Nov 01 '11 at 08:56
  • The $\Pi_1$-ness of RH was proved by Matiyasevich, prior to Robin's work. I don't have a reference handy. – Gerry Myerson Nov 01 '11 at 11:20
  • 5
    @Michael: it is $\Pi^0_1$, period. This is a classification of sentences up to provable equivalence, not a classification of sets of reals, therefore the concept of boldface does not make sense here. As a set of reals, any statement has trivial complexity (since it is either the empty set or the full set, depending on whether the statement is true). – Emil Jeřábek Nov 01 '11 at 11:51
  • 5
    @Shaqq: It seems likely that you’ve heard (but misremembered) that the negation of the Riemann hypothesis cannot be true but unprovable (which is what Sridhar’s answer is about). – Emil Jeřábek Nov 01 '11 at 12:00
  • 4
    @Emil: probably Shaqq heard it in this form: if the Riemann hypothesis is undecidable in ZFC then it is true. That's the most common way I've heard it bandied about. – Timothy Chow Nov 01 '11 at 14:13
  • Does Robin's theorem really use AC? If not, your argument shows that if RH is false, it is provably false in ZF without C. – Joël Nov 01 '11 at 15:25
  • 1
    @Joël: If RH is false, then it is provably false even in, say, Robinson arithmetic, since the latter is $\Sigma^0_1$-complete. – Ed Dean Nov 01 '11 at 15:49
  • 2
    @Ed: Not really, since Robinson arithmetic most likely does not prove the equivalence of RH to the relevant $\Sigma^0_1$-sentence. In fact, the RH as such is not even an arithmetical statement (it speaks about complex zeroes). I do not know whether Robin’s theorem is provable in ZF, but I note that a good deal of elementary analysis relies on DC (or at least, countable AC). – Emil Jeřábek Nov 01 '11 at 16:12
  • And as usual with $\Pi_1$ statement, if it is shown to be undecidable in ZFC, then there are good reason to adopt it as a new axiom. – Ori Gurel-Gurevich Nov 01 '11 at 18:01
  • @Emil: Nope, I have heard precisely what I wrote here. Nevertheless, thanks for the idea that I could hear a wrong statement )) – Shaqq Nov 01 '11 at 19:30
  • 3
    Is it possible, for a given $n$ and $K=\sigma_1(n),$ for the statement "$e^\gamma n\log\log n=K$" to be undecidable? Our arbitrary-precision approximations just showing values closer and closer to $K$ and that's all we know? – Daniel Briggs Dec 18 '11 at 17:33
  • 1
    @Daniel: You're right! I haven't ruled out this possibility! All these years, sitting there unnoticed... That having been said, various sources give Robin's criterion instead as "for all $n > 5040$, $\sigma_1(n) \leq e^{\gamma} n \log \log n$.. To this, exact equality would not serve as a counter-example, and thus falsehood would entail provable falsehood. That having been said, I am not, in fact, familiar enough with the relevant material to verify whether the "$\leq$" form of Robin's criterion is genuine, or, I paranoidly worry, merely the result of careless transcription of the "$<$" form. – Sridhar Ramesh May 13 '14 at 01:39
  • 2
    There is no need for Robin's condition. Already Turing's method can check the RH up to a given height, and simply increasing the height more and more (just like increasing your $n$) will again prove RH false if it is indeed so. – post.as.a.guest Mar 25 '16 at 10:57
18

Without worrying about reductions, if RH is false, it is provably false: suppose $\rho\in\mathbb{C}$ is a zero in the critical strip but off the critical line (say, $\Re(\rho)>\frac12$). Then for a little rectangle $R$ with (say) rational corners, containing $\rho$ in its interior but not containing the pole at $s=1$ or intersecting the critical line we'd have $$\frac{1}{2\pi i}\oint_{\partial R} \frac{\zeta'}{\zeta}(s)\mathrm{d}s \geq 1$$ by the argument principle.

But we can approximate $\zeta(s),\zeta'(s)$ to arbitrary precisition by a finite computation, and similarly we can approximate the integral to arbitrary precision by a numerical computation. In other words, there is a finite computation which provably approximates the integral above to within $\frac{1}{2}$. Then the non-vanishing of the approximation proves the falsity of RH.

Similarly, RH is equivalent to estimates on the prime-counting function, for example to $$|\psi(x)-(x)|<\sqrt{x}\log^2 x$$ where $\psi(x) = \sum_{p^r<x}\log p$.

While the models can disagree about some aspects of the real numbers, I don't think they can disagree about the logarithm of an integer (in the sense that $\log(n)=-\log(1/n) = \sum_{k=1}^\infty \frac{(n-1)^k}{kn^k}$), and it's enough to consider integer $x$ in the inequality. This means that if RH is false in a model, RH will be false in any model whose integers contains those of the original model.

.

Edited to clarify the last comment: in the prime-counting inequality, replace the term $\log p$ associated to the prime power $p^r$ with $\sum_{k=1}^{100p^{2r}} \frac{(p-1)^k}{kp^k}$. Similarly, replace the $\log x$ with a truncation of the logarithm series. RH is still equivalent to the inequality using the truncated logarithm, and in the new formulation both sides of the inequality are explicit rational numbers! In other words, RH is equivalent to a countable sequence of inequalities about explicit rational numbers.

Second edit: I realize that the direct formulation can also be converted to a statement about rationals. Let $R_n$ be the axis-parallel rectangle with corners at $\frac{1}{2}+\frac{1}{n}+i$ and $1+ni$. Let $I_n$ be a rational approximation to the zero-counting integral above around $R_n$, accurate to better than $\frac{1}{2}$ (obtained by dividing the boundary of $R$ into many points, at each point approximating $\frac{\zeta'}{\zeta}$ by a rational number, and then integrating numerically). This is an explicit finite computation, and RH is equivalent to the infinite system of inequalities $I_n<0.5$.

Third edit: removed false statement about submodels.

Lior Silberman
  • 2,735
  • “$\cal U$ contains an isomorphism between the natural numbers of $\cal U$ and the natural numbers in a model of ZFC inside $\cal U$” — this is not necessarily the case; even if $\cal U$ is a transitive model of ZFC, the submodel inside $\cal U$ might have non-standard natural numbers. – Yury Dec 23 '15 at 22:46
  • Accordingly, there might be a “counterexample” $x$ to RH in the model in $\cal U$, which is a non-standard natural number. – Yury Dec 23 '15 at 22:50
  • 1
    Ah I see my error: the "set of standard natural numbers" in the submodel will satisfy the Peano axioms, but need not be a set in the submodel. – Lior Silberman Dec 23 '15 at 23:00
  • But still the embedding of the natural numbers of $\cal{U}$ in the natural numbers of the submodel will show that if RH is false in $\cal{U}$ it's false in the submodel. – Lior Silberman Dec 23 '15 at 23:03
  • Answer edited accordingly – Lior Silberman Dec 23 '15 at 23:07
  • You seem to be actually answering https://mathoverflow.net/questions/31846/is-the-riemann-hypothesis-equivalent-to-a-pi-1-sentence rather than the original question here. – Emil Jeřábek Dec 24 '15 at 16:33
14

If the negation of the Riemann hypothesis is not provable in the Peano arithmetic, then the Riemann hypothesis is true.

Vladimir Reshetnikov
  • 6,709
  • 1
    Where do you get this from? – Connor McCormick Aug 22 '22 at 21:48
  • 1
    Consider the contrapositive: if the RH is false, then ¬RH is provable in PA. It just means that if there is a counterexample to the RH (a non-trivial root of the Riemann ζ-function off the critical line), it can be demonstrated by a straightforward calculation. It can be done even in a weaker theory than PA. – Vladimir Reshetnikov Aug 23 '22 at 23:21
13

In an interview with Martin Davis that appeared in the notices of the AMS, he speculates by the end (pp. 570) with the possibility of RH being undecidable. He was explaining that every $\Pi_1^0$ is equivalent to a statement asserting about a particular polynomial equation with integer coefficients that that equation has no natural number solutions, and that RH was a statement of that kind, as worked out in "Hilbert’s tenth problem: Diophantine equations: positive aspects of a negative solution", by Martin Davis, Yuri Matijasevic, and Julia Robinson, in Mathematical developments arising from Hilbert problems, Proc. Sympos. Pure Math., AMS, 1976. He then goes on:

"I am certainly no analyst, but the reason I think the Riemann Hypothesis is a good candidate for undecidability by elementary methods is that it is sitting right in the middle of classical analysis, and it has been attacked by brilliant mathematicians—Paul Cohen spent a lot of time on it—and the existing methods just don’t seem to resolve it. It’s hard to believe it isn’t true. And why shouldn’t it be one of those propositions that require set theoretic methods? That would be great!"

As he previously explained, there are some mathematical propositions that "have a very simple form involving solvability of specific Diophantine equations and that require set-theoretic methods for their resolution". The fact that RH might be of that character, as he remarks, had already been conjectured by Gödel at the Gibbs lecture. "And that wouldn’t surprise me in the least", he claims.

godelian
  • 5,682
  • 5
    When Davis mentions set-theoretic methods, this suggests that he means undecidability in Peano arithmetic rather than undecidability in ZFC. (The text is unclear, since first he discusses algorithmic decidability but then he mentions measurable cardinals.) RH may well be unprovable in PA and yet provable in ZFC. However, the same basic ideas apply. – Toby Bartels Nov 01 '11 at 16:58
  • 1
    I believe Davis talks about both aspects because he's thinking about what Gödel said at the lecture. There, Gödel was talking about different levels of set theoretic constructions (sets of integers, then sets of sets of integers and so on, eventually iterating this through transfinite ordinals and then using this operation to define further sets...). Gödel emphasized that there might be some set theoretic axioms describing the behaviour of sets of a certain level in the hierarchy which actually have consequences in the 0 level. but he remarks that there is no end in this hierarchy of axioms... – godelian Nov 01 '11 at 21:05
9

Yes.

That being said, it's pure speculation. We can as well talk about the decidability of any other famous open problem, but in my experience that usually doesn't lead to anything new. To me, it's highly unlikely that is undecidable, but of course, we can't exclude it. Compare it for example to the rationality of $2*\pi^{4/3} - e^{3/2}$.

Woett
  • 1,533
  • Is the question of the rationality of $2 \pi^{4/3}- e^{3/2}$ undecidable? Or is this just an example of a difficult question? – Bart Snapp Dec 18 '11 at 17:19
  • 4
    It just seems to be extremely hard :) – Woett Dec 19 '11 at 14:30
  • 1
    I think Woett's answer wants to point out the following analogy: it is relatively easy to prove that there are many transcendental numbers (Cantor) or many undecidable sentence (Godel) but to prove that a given, mathematically interesting number/sentence is transcendental/undecidable is much much harder. – Joël Mar 21 '12 at 16:02
  • 2
    Interesting! But what I was going for was the following analogy: in both cases something is extremely hard (proving RH, or proving that some number is irrational), which may lead to some speculation that it just can't be done (that either RH is undecidable or the number is actually rational). While it is OK, I guess, to keep that possibility in the back of your mind, the chances of that happening are, in my belief system, very very slim. – Woett Mar 22 '12 at 13:38
  • 2
    I believe even the rationality of $\pi\cdot e$ is open. – Vladimir Reshetnikov Jun 02 '17 at 00:58