¿Es la Hipótesis de Riemann equivalente a una $\Pi_1$ ¿sentencia?

Question

1) ¿Se puede expresar la Hipótesis de Riemann (HR) como una $\Pi_1$ ¿sentencia?

Más formalmente,

2) ¿Existe una $\Pi_1$ ¿una sentencia que sea demostrablemente equivalente a RH en PA?

---

Actualización (julio de 2010):

Así que tenemos dos pruebas de que el RH es equivalente a un $\Pi_1$ sentencia.

1. Martin Davis, Yuri Matijasevic y Julia Robinson, "El décimo problema de Hilbert. Ecuaciones Diofantinas: Positive Aspects of a Negative Solution", 1974.
   Publicado en " Desarrollos matemáticos derivados de los problemas de Hilbert ", Proceedings of Symposium of Pure Mathematics", XXVIII:323-378 AMS.
   Página 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, " Un problema elemental equivalente a la hipótesis de Riemann ", 2001 $$\forall n>60 \ .\ \sigma(n) < \exp(H_n)\log(H_n)$$

Pero ambos utilizan teoremas de la literatura que hacen difícil juzgar si se pueden formalizar en AP. La razón por la que mencioné PA es que, para el propósito de Kreisel, la prueba debe ser formalizada en una teoría razonablemente débil. Así que una nueva pregunta sería:

3) ¿Pueden estas dos pruebas de "RH es equivalente a una $\Pi_1$ ¿se formaliza la "sentencia" en AP?

---

Motivación:

Esto se menciona en P. Odifreddi, " Kreiseliana: sobre y alrededor de George Kreisel ", 1996, página 257. Feferman menciona que cuando Kreisel intentaba "desenredar" la prueba no constructiva de Teorema de Littlewood tenía que lidiar con RH. La prueba de Littlewood considera dos casos: hay una prueba si RH es verdadera y hay otra si RH es falsa. Pero parece que al final, Kreisel utilizó una $\Pi_1$ frase más débil que RH que era suficiente para su propósito.

¿Por qué es interesante?

Aquí trataré de explicar por qué esta cuestión era interesante sólo desde el punto de vista de Kreisel.

Kreisel intentaba extraer un límite superior de la prueba no constructiva de Littlewood. Su método de "desenrollado" funciona para teoremas como el de Littlewood si se demuestran en una teoría adecuada. El problema de esta prueba es que en realidad se trata de dos pruebas:

1. Si la RH es falsa, el teorema se cumple.
2. Si la RH es verdadera, el teorema se cumple.

Si no recuerdo mal, el primero ya da un límite superior. Pero la segunda no da un límite superior. Kreisel argumenta que la segunda parte se puede formalizar en una teoría aritmética (similar a la de PA) y su método puede extraer una cota de la misma asumiendo que la HR es demostrablemente equivalente a una $\Pi_1$ frase. (Generalmente se añade $\Pi_1$ las sentencias no le permiten demostrar la existencia de más funciones). Esta es la parte que necesita para sustituir el enunciado habitual de la RH por un $\Pi_1$ declaración. Parece que al final, en lugar de demostrar que el RH es $\Pi_1$ muestra que un $\Pi_1$ La afirmación basta para llevar a cabo la segunda parte de la prueba, es decir, evita el problema en este caso.

Una aplicación sencilla de demostrar que el RH es equivalente a un $\Pi_1$ Las sentencias en PA son las siguientes: Si probamos un teorema en PA+RH (incluso cuando la prueba parece completamente no constructiva), entonces podemos extraer un límite superior para el teorema de la prueba. Nótese que para este propósito, no necesitamos saber si la RH es verdadera o falsa.

Nota: El artículo de Feferman mencionado anteriormente contiene más detalles y reflexiones sobre el "Programa de Kreisel" de "desenrollar" las pruebas clásicas para extraer límites constructivos. Mi interés se debe principalmente a la curiosidad. Leí en el artículo de Feferman que Kreisel mencionó este problema y luego lo evitó, así que quería saber si alguien se había ocupado de él.

Answer 1

No sé cuál es la mejor manera de expresar RH dentro de PA, pero la siguiente desigualdad $$\sum_{d \mid n} d \leq H_n + \exp(H_n)\log(H_n),$$ donde $H_n = 1+1/2+\cdots+1/n$ es el $n$ -número armónico, se sabe que es equivalente a RH. [J. Lagarias, Un problema elemental equivalente a la hipótesis de Riemann , Amer. Math. Monthly, 109 (2002), 5347-543]. El mismo artículo menciona otra desigualdad de Robin, $$\sum_{d \mid n} d \leq e^\gamma n \log\log n \qquad (n \geq 5041),$$ donde $e^\gamma = 1.7810724\ldots$ que también es equivalente a RH. A pesar de la aparición de $\exp,$ $\log$ et $e^\gamma$ es una cuestión rutinaria expresar estas desigualdades como $\Pi^0_1$ declaración. (De hecho, los detalles del artículo de Lagarias hacen que esto sea incluso más sencillo de lo que se podría pensar en un principio).

Answer 2

Me di cuenta de que ninguna de las respuestas presenta lo que considero más sencillo $\Pi^0_1$ expresión para la hipótesis de Riemann, es decir, los límites del término de error en el teorema de los números primos. La escribiré en términos de de Chebyshev $\psi$ función ya que lo encuentro más natural, pero funciona para $\pi$ igual. Los siguientes son equivalentes:

1. La hipótesis de Riemann.

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

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

La equivalencia de 1 y 2 es clásica, el límite explícito en 3 se debe a Schoenfeld. Ahora, el gran margen de maniobra entre 2 y 3 permite escribir el límite como $\Pi^0_1$ sentencia, aunque no podamos calcular exactamente todos los logaritmos implicados: dejemos $\mathrm{psi}(n)$ , $\mathrm{sqrt}(n)$ y $\mathrm l(n)$ sean funciones computables que proporcionen aproximaciones racionales dentro de la distancia $1$ de $\psi(n)$ , $\sqrt n$ y $\log n$ respectivamente. Entonces RH es equivalente a $$\forall n\,|\mathrm{psi}(n)-n|\le42+\mathrm{sqrt}(n)\,\mathrm l(n)^2.$$

La belleza de esto no es sólo que está en línea con la forma de RH más probable que sea útil en los argumentos elementales de la teoría de los números, pero tal vez más importante, se generaliza fácilmente a las extensiones de la RH a otros $L$ -funciones.

Para una formulación específica, la sección 5.7 de la obra de Iwaniec y Kowalski Teoría analítica de los números estados para una gran clase de $L$ -(básicamente, funciones de la clase Selberg con un producto de Euler polinómico; los supuestos son algo negociables, en particular confío en que se pueda eliminar la hipótesis de Ramanujan-Petersson a costa de límites algo peores) la equivalencia de

1. La hipótesis de Riemann para $L(s)$ .

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

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

Aquí $c$ es una constante absoluta que puede (en principio) extraerse de la prueba, $d$ es el grado del producto de Euler, $n_L$ es el orden del polo de $L(s)$ en $s=1$ , $q_L$ es una especie de conductor, y $$\psi_L(x)=\sum_{n\le x}\Lambda_L(n),$$ donde $\Lambda_L(n)$ es una función "von Mangoldt" de $L$ extraído de la expansión de la derivada logarítmica de $L$ como una serie de Dirichlet: $$-\frac{L'(s)}{L(s)}=\sum_{n=1}^\infty\Lambda_L(n)\,n^{-s}.$$ El resultado es que la HR para una clase de $L$ -funciones es $\Pi^0_1$ siempre que la clase sea "recursivamente enumerable": podemos parametrizar la clase como $L(s,a)$ donde el $a$ son objetos finitos (incluyendo datos básicos como $d,n_L,q_L$ ) de tal forma que el conjunto de los válidos $a$ es r.e., y dado $a$ , $n$ y $\epsilon>0$ podemos calcular una aproximación de $\Lambda_L(n)$ a poca distancia $\epsilon$ (o de forma equivalente, si podemos calcular aproximadamente los términos del producto de Euler).

Por ejemplo, cada una de las siguientes puede expresarse como $\Pi^0_1$ sentencia:

• La RH para Dirichlet $L$ -funciones.

• La RH para las funciones zeta de Dedekind.

• La RH de Hecke $L$ -funciones.

(Las dos primeras clases se pueden enumerar de forma sencilla. Los caracteres de Hecke de orden finito también son fácilmente enumerables, ya que los grupos de clases de rayos son finitos y computables. El caso de los caracteres de Hecke generales requiere un poco más de trabajo, pero básicamente se puede enumerar una base de tipos infinitos convenientemente normalizados utilizando una versión efectiva del teorema de la unidad de Dirichlet).

No puedo decir (pero me interesaría saber de alguien más conocedor) si el RH para los automórficos estándar $L$ -funciones es también $\Pi^0_1$ es decir, si estas funciones son recursivamente enumerables. (Ciertamente, sólo hay muchas contables hasta la normalización, y polinomialmente muchas de conductor analítico acotado, por lo que es concebible que esto sea cierto).

Answer 3

Sí, es una consecuencia del trabajo de Davis-Matiyasevich-Putnam-Robinson sobre el décimo problema de Hilbert y de la teoría de números estándar. Una serie de trabajos tienen detalles de la $\Pi^0_1$ sentencia. Para empezar, eche un vistazo al documento correspondiente en Desarrollos matemáticos derivados de los problemas de Hilbert (Proc. Sympos. Pure Math., Northern Illinois Univ., De Kalb, Ill., 1974), Amer. Math. Soc., Providence, R. I., 1976.

---

Actualización, 22/06/16: El interés por los recientes trabajo de Scott Aaronson y Adam Yedidia sobre pequeñas máquinas de Turing cuyo comportamiento no es decidible en $\mathsf{ZFC}$ tuvo el efecto secundario de conducir a ejemplos explícitos de máquinas de Turing que se detienen si y sólo si hay un contraejemplo a la hipótesis de Riemann. Una de estas máquinas se describe (con enlaces) a partir de la página 11 de su artículo, utilizando la equivalencia de Lagarias mencionada en la respuesta de François. Una breve discusión (en español), que también proporciona los enlaces pertinentes, puede verse aquí . Los resultados se anunciaron en el blog de Scott, aquí .

Answer 4

La respuesta de Andrés Caicedo es la correcta, pero mi comentario es demasiado grande para caber en una caja de comentarios.

He aquí un programa Haskell que expone la Hipótesis de Riemann:

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]

La Hipótesis de Riemann equivale a decir que el programa rh devuelve True en todas las entradas positivas. Esta equivalencia es, por supuesto, una equivalencia matemática y no una equivalencia lógica. Una vez que demostremos o refutemos la Hipótesis de Riemann se sabrá que es matemáticamente equivalente a una $\Delta^0_0$ declaración.

Answer 5

Se puede escribir un programa que, dado el tiempo suficiente, detecte eventualmente la presencia de ceros fuera de la línea crítica si es que existen, calculando integrales de contorno de $\zeta' (s)/ \zeta(s)$ en una secuencia de pequeños cuadrados (con vértices racionales) agotando mallas finitas cada vez más finas que cubren cada vez más la franja crítica a mayor altura.

A partir de las fórmulas de continuación analítica de $\zeta (s) $ se pueden extraer los módulos efectivos de continuidad uniforme y a partir de ellos se puede aproximar la integral dividiendo cada lado del cuadrado en algún gran número de trozos iguales, aproximando la función en esos puntos racionales y calculando la suma de Riemann. La precisión necesaria puede determinarse a partir del módulo de continuidad y de las fórmulas para $\zeta$ .

(Las rejillas que tengo en mente vienen dentro de $1/n$ de los lados de la franja crítica, con una altura que va desde $0$ a $n$ y se dividen en cuadrados de tamaño $1/n^2$ por lo que finalmente cualquier cero quedará aislado dentro de uno de esos cuadrados).

EDIT: para expresar la HR en aritmética de Peano, hay dos maneras.

Una de ellas es utilizar el teorema de Matiyasevich de que para cualquier problema de parada se puede construir una ecuación diofantina cuya solvencia es equivalente a la parada. O, en la misma línea, utilizar el enfoque de Matiyasevich/Robinson para codificar de forma diofantina una desigualdad elemental equivalente a RH, como se hizo en el artículo de Matiyasevich-Davis-Robinson sobre El décimo problema de Hilbert: aspectos positivos de una solución negativa . Otra forma es expresar un análisis suficientemente complejo en Aritmética de Peano para llevar el argumento de la integral de contorno anterior, lo que puede hacerse porque en última instancia todo implica fórmulas y estimaciones que pueden hacerse suficientemente explícitas. Cómo hacerlo se explica en el ensayo de Gaisi Takeuti Dos aplicaciones de la lógica a las matemáticas .

EDIT-2: re: verificaciones de RH, el cálculo distribuido de ZetaGrid comprobó que al menos los primeros 100 mil millones (10^11) de ceros, ordenados por parte imaginaria, están en la línea crítica. Los cálculos de los ceros son opuestos a los $\Pi_1$ enfoque: en lugar de falsear la HR si es errónea, si se ejecutan durante un tiempo ilimitado validarían la HR hasta donde el programa pueda llegar, pero podrían atascarse si hay dobles ceros en cualquier parte. Los algoritmos asumen RH y cualquier otra conjetura que sea útil para encontrar ceros, como la ausencia de raíces múltiples, o los espacios GUE entre ceros. Cada vez que localizan otro cero, una integral de contorno verifica entonces que no hay otros ceros hasta esa altura, y RH se sigue manteniendo. Pero si hay un doble cero el programa podría atascarse en un intento interminable de demostrar que es un solo cero. Los ceros simples fuera de la línea serían detectados por la mayoría de los algoritmos, pero no necesariamente localizados: una vez que sabes que hay uno puedes tomar un gran trago y ejecutar un programa separado para encontrarlo con precisión.

(Sobre el interés filosófico de la $\Pi_1$ formulación de RH, véanse también los comentarios bajo la pregunta).