[FOM] \Pi-0-1 equivalent of the Riemann Hypothesis

Martin Davis martin at eipye.com
Wed Jan 14 16:39:04 EST 2009

Joe Shipman wrote:
 >For the Riemann Hypothesis, the simplest equivalent formulation I 
know is Lagarias's:?Let H(n) = 1 + 1/2 + >... + 1/n, RH is equivalent to
 >"For all n, the sum of the divisors of n is <= H(n) + ln(H(n))*exp(H(n))."?
 >This has only one quantifier but of course?it involves real numbers 
and real functions. There are arithmetical >equivalents which are not 
too hard which involve 3 quantifiers (formalizing that the Mobius 
function is >eventually dominated by x^alpha whenever alpha > 1/2 ) 
but I'd like to know if there is an arithmetical >
 >equivalent that is easy and requires only one quantifier.?

For a simple \Pi-0-1 equivalent of RH see: Martin Davis, Yuri 
Matiyasevich & Julia Robinson,  Proc. Symposia Pure Mathematics, vol. 


                           Martin Davis
                    Visiting Scholar UC Berkeley
                      Professor Emeritus, NYU
                          martin at eipye.com
                          (Add 1 and get 0)

More information about the FOM mailing list