Welcome to MathOverflow

Question

7

3

Gregory Chaitin has quoted Marcus du Sautoy to the effect that:

If the Riemann Hypothesis (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.

Question(s) Which of the other five (at present) unsolved Clay Institute Millenium Prize Problems similarly have the attribute $\text{undecidable}\to\text{true}$? And do any of the five have the attribute $\text{undecidable}\to\text{false}$?

Context This question first arose in the discussion of "a whole lot of basic questions" that were asked by Tim Gowers on Dick Lipton and Ken Regan's weblog Gödel's Lost Letter and P-NP.

Edit Dick and Ken subsequently posted an essay Why We Lose Sleep Some Nights in which (in a comment) the question is associated to the immanence of the eschaton (or perhaps not) in computational complexity theory. ☺

edited Sep 30 at 12:30

asked Sep 30 at 1:56

John Sidles
973●6●16

8

The point is that if there's a counterexample then one can prove it by a contour integral: no need to actually locate the zero, only to prove there's one in a circle disjoint from the critical line. – Noam D. Elkies Sep 30 at 3:03

2

So if I understand correctly, this is essentially asking which of these statements are equivalent to a $\Pi_1^0$ statement, right? – Harry Altman Sep 30 at 4:01

2

If an elliptic curve has rank at least $n$ we can always write down $n$ rational solutions. If the $L$-function has a zero of order less than $n$ at $s=1$ then we can determine this by accurately approximating a contour integral in sufficiently small loop around $s=1$, which I think is always possible. If this works then undecidability of BSD implies that the analytic rank is greater than the algebraic rank. The other inequality appears more elusive. – Will Sawin Sep 30 at 5:59

4

Will - yes, but the undecidable bit is to prove that a CW-complex is not simply connected. There is a partial algorithm that terminates if and only if an input CW-complex is simply connected or, equivalently, an group presentation presents the trivial group, and this is enough for these purposes. The partial algorithm simply tries to write each generator as a product of conjugates of relators. – HW Sep 30 at 6:54

2

It is undecidable whether a 2-complex is simply connected, but it is decidable whether a 3-manifold is simply connected. (This should not be shocking to someone who know how to make a 4-manifold with arbitrary fundamental group.) – Ben Wieland Sep 30 at 19:03

show 9 more comments

For which Millennium Problems does undecidable -> true?

Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.