Décimo problema de Hilbert

El décimo problema de Hilbert es uno de los conocidos como veintitrés Problemas de Hilbert, publicados en 1900 por el matemático alemán David Hilbert. Su enunciado original es:

En términos de programación informática, Hilbert solicitaba a sus colegas del futuro un algoritmo capaz de admitir como entrada (input) una ecuación diofántica cualquiera, y de devolver SÍ como resultado (output) si la ecuación procesada tenía soluciones en números enteros o NO si la ecuación procesada carecía de soluciones en números enteros.

El problema no se resolvió hasta 70 años después, y en sentido negativo. En 1970 Yuri Matiyasévich culminó más de veinte años de trabajo de varios matemáticos, entre ellos Martin Davis, Julia Robinson y Hilary Putnam, con la demostración de imposibilidad del décimo problema: ningún algoritmo es capaz de determinar la resolubilidad de cualquier ecuación diofántica. El planteamiento, desarrollo y demostración del problema tienen gran interés en matemática moderna, porque en ellos participan conceptos de teoría de números y de lógica matemática, y se abren nuevos campos de investigación en ambas disciplinas.

Las palabras «proceso» y «número finito de operaciones» de su enunciado original sugieren claramente que Hilbert pedía un algoritmo. El término «racional entero» se refiere simplemente a los números enteros, positivos, negativos o cero: ${\displaystyle 0,\pm 1,\pm 2,\ldots \,}$.^[1]​ Por tanto, Hilbert estaba pidiendo un algoritmo general que decidiera si un polinomio dado de coeficientes enteros —una ecuación diofántica— tenía solución en el dominio de los enteros.

Hoy sabemos que la respuesta es negativa: no existe tal algoritmo general.

Puede que el propio Hilbert no confiara en su existencia. Antes de presentar la lista de problemas, parecía presagiar la ausencia de solución, diciendo:

En ocasiones ocurre que perseguimos la solución basándonos en hipótesis insuficientes, o en un sentido incorrecto, y por eso fracasamos. Entonces surge el problema: demostrar la imposibilidad de obtener una solución con tales hipótesis o en el sentido contemplado.

Otros opinan que la «solución de insolubilidad» a la que se llegó siete décadas después no solo hubiera sorprendido al auditorio que asistió en 1900 en la Sorbona a la presentación de Hilbert,^[2]​ sino posiblemente incluso al propio Hilbert, ya que se esperaba obtener un conjunto de instrucciones que definieran un procedimiento, y a lo que se llegó finalmente fue a una demostración de la inexistencia de tal conjunto de instrucciones.^[3]​

Los trabajos de solución del problema casi siempre se han planteado en términos de enteros no negativos o números naturales, ${\displaystyle \mathbb {N} =\{0,1,2,3\ldots \}\,}$,^[4]​ más que con números enteros. Es irrelevante, porque puede demostrarse que si existiera un algoritmo que detectara la existencia de solución en ${\displaystyle \mathbb {N} \,}$, podría usarse también para detectar la existencia de solución en ${\displaystyle \mathbb {Z} \,}$.

• En efecto: conocido un algoritmo que detecte la resolubilidad en ${\displaystyle \mathbb {N} \,}$, podríamos usarlo para detectar si la ecuación de ${\displaystyle n\,}$ incógnitas,

${\displaystyle p(x_{1},x_{2},\ldots ,x_{n})=0,\,}$

tiene solución entera, aplicando el hipotético algoritmo a las ${\displaystyle 2^{n}\,}$ ecuaciones

${\displaystyle p(\pm x_{1},\pm x_{2},\ldots ,\pm x_{n})=0.\,}$

• Inversamente, un algoritmo capaz de detectar la resolubilidad en ${\displaystyle \mathbb {Z} \,}$ puede usarse para determinar si una ecuación dada es resoluble en ${\displaystyle \mathbb {N} \,}$, sin más que sustituir cada incógnita de la ecuación por la suma de los cuadrados de cuatro nuevas variables enteras. El teorema de Lagrange de los cuatro cuadrados garantiza que cualquier número natural puede igualarse a la suma de los cuadrados de un máximo de cuatro números enteros.

Se denomina conjuntos diofánticos a los conjuntos de números naturales, de pares de números naturales, o de forma más general de ${\displaystyle n\,}$-tuplas de números naturales, que tienen definiciones diofánticas. Tanto un sistema de ecuaciones diofánticas simultáneas como una ecuación diofántica individual pueden definir un conjunto diofántico, porque el sistema

${\displaystyle p_{1}=0,\ldots ,p_{k}=0\,}$

es equivalente a la ecuación individual

${\displaystyle p_{1}^{2}+\ldots +p_{k}^{2}=0.\,}$

Dicho de otro modo, si existe una ecuación (o sistema) diofántica cuya solución sea el conjunto de ${\displaystyle n\,}$-tuplas de números naturales ${\displaystyle C\,}$, entonces ${\displaystyle C\,}$ es un conjunto diofántico.

Se define un conjunto recursivamente enumerable como un conjunto para el que existe un algoritmo que se detendrá si su entrada es un elemento del conjunto, pero seguirá corriendo indefinidamente si su entrada no pertenece al conjunto. El concepto de enumerabilidad recursiva pertenece al ámbito de la teoría de la computabilidad, también llamada teoría de la recursión, cuyo desarrollo aportó una explicación precisa de la noción intuitiva de computabilidad algorítmica, dando pleno rigor al concepto de enumerabilidad recursiva.

Resulta evidente que los conjuntos diofánticos son, por definición, recursivamente enumerables. Dada una ecuación o sistema diofántico, pueden formarse secuencialmente todas las tuplas posibles de valores de las incógnitas y después, para un valor dado de los parámetros, comprobar una tras otra las tuplas, para detectar si son o no solución de la ecuación o sistema. Luego la propia ecuación o sistema que define el conjunto diofántico define el algoritmo que avala la enumerabilidad recursiva del conjunto. La imposibilidad de resolver el décimo problema de Hilbert es consecuencia de que el inverso también es cierto:

Este resultado se conoce de dos formas: como Teorema de Matiyasevich, porque fue Yuri Matiyasévich el que consiguió el desarrollo final que permitió demostrar el teorema, y como Teorema MRDP, nombre que agrupa a los matemáticos que consiguieron el desarrollo completo, empezando por el citado Matiyasevich, para continuar por Julia Robinson, Martin Davis y Hilary Putnam. Dado que existe un conjunto recursivamente enumerable que no es computable, la irresolubilidad del décimo problema de Hilbert es una consecuencia inmediata. De hecho, puede decirse más. Existe un polinomio

${\displaystyle p(a,x_{1},\ldots ,x_{n})\,}$

con coeficientes enteros, tal que el conjunto de valores de ${\displaystyle a}$ para el que la ecuación

${\displaystyle p(a,x_{1},\ldots ,x_{n})=0\,}$

tiene soluciones en los números naturales no es computable. Así pues, no solo no existe un algoritmo general para detectar la resolubilidad de las ecuaciones diofánticas, sino que también puede demostrarse que ni siquiera existe un algoritmo particular para la familia de ecuaciones con un único parámetro.

Año	Sucesos
1944	Emil Leon Post declara que el décimo problema de Hilbert «está implorando una prueba de irresolubilidad».
1949	Martin Davis utiliza el método de Kurt Gödel para aplicar el teorema chino del residuo como truco de codificación para obtener en su forma normal conjuntos recursivamente enumerables: ${\displaystyle \{\,a\mid \exists y\,\forall k\!\leq y\,\exists x_{1},\ldots ,x_{n}[p(a,k,y,x_{1},\ldots ,x_{n})=0]\,\}\,}$ donde ${\displaystyle p\,}$ es un polinomio con coeficientes enteros. Formalmente, solo el cuantificador universal estorba para que se considere esto como una definición diofántica de conjuntos. Usando una prueba no constructiva, pero muy sencilla, Davis notó que hay un conjunto diofántico cuyo complementario no es diofántico. Dado que los conjuntos recursivamente enumerables tampoco son cerrados para el complemento, Davis conjeturó la identidad de ambas clases.
1950	Julia Robinson no conocía el trabajo de Davis, pero sospechando que la función exponencial era de importancia clave, intentaba demostrar que EXP, el conjunto de tripletes ${\displaystyle (a,b,c)\,}$ para los cuales ${\displaystyle a=b^{c}\,}$ es diofántico. No tuvo éxito, lo que la condujo a su hipótesis (luego llamada ${\displaystyle J.R.\,}$): Existe un conjunto diofántico ${\displaystyle D\,}$ de pares ${\displaystyle (a,b)\,}$ tal que ${\displaystyle (a,b)\in D\Rightarrow b<a^{a}\,}$ pero para cada ${\displaystyle k>0\,}$, ${\displaystyle \exists (a,b)\in D\,}$ tal que ${\displaystyle b>a^{k}.\,}$ Usando algunas propiedades de la ecuación de Pell, Robinson demostró que ${\displaystyle J.R.\,}$ implica que EXP es diofántico. Y finalmente demostró que si EXP es diofántico, entonces también lo son los coeficientes binomiales, el factorial y los primos.
1959	Trabajando juntos, Davis y Putnam estudiaron los conjuntos diofánticos exponenciales, es decir, los conjuntos definibles por ecuaciones diofánticas en los que algunos de los exponentes pueden ser incógnitas. Usando la forma normal de Davis junto con los métodos de Robinson, pero suponiendo la entonces indemostrada conjetura de que hay progresiones aritméticas arbitrariamente largas compuestas de números primos[5]​ demostraron que todo conjunto recursivamente enumerable es un conjunto exponencial diofántico, y que como consecuencia, ${\displaystyle J.R.\,}$ implicaba que todo conjunto recursivamente enumerable es diofántico, y que el décimo problema de Hilbert es irresoluble.
1960	Robinson mostró como evitar el uso de la indemostrada conjetura de los números primos en progresiones aritméticas, y simplificó notablemente la demostración. ${\displaystyle J.R.\,}$ se revelaba como la clave para seguir avanzando, aunque muchos dudaban de su veracidad.[6]​
1961-1969	Davis y Putnam encontraron algunas proposiciones que implicaban ${\displaystyle J.R.\,}$ Matiyasevich publicó algunas reducciones del décimo problema de Hilbert. Robinson demostró que la existencia de un conjunto diofántico infinito de primos bastaría para demostrar ${\displaystyle J.R.\,}$
1970	Matiyasevich presentó un sistema de 10 ecuaciones simultáneas de primer y segundo grado que aportaba una definición diofántica del conjunto de pares ${\displaystyle (a,b)\,}$ tal que ${\displaystyle b=F_{2a}\,}$ donde ${\displaystyle \,F_{n}\,}$ es el n-simo número de Fibonacci. Con esto quedaba demostrado ${\displaystyle J.R.\,}$, completándose por tanto la prueba de que todos los conjuntos recursivamente enumerables son diofánticos, lo que implica que el décimo problema de Hilbert es irresoluble.

El teorema de Matiyasevich/MRDP relaciona dos conceptos, uno procedente de la teoría de la computabilidad, y el otro de la teoría de números, y tiene algunas consecuencias inesperadas. Quizás la más sorprendente sea la existencia de una ecuación diofántica universal.

Existe un polinomio ${\displaystyle p(a,n,x_{1},\ldots ,x_{k})\,}$ tal que, dado cualquier conjunto diofántico ${\displaystyle S\,}$, hay un número ${\displaystyle n_{0}\,}$ tal que

${\displaystyle S=\{\,a\mid \exists x_{1},\ldots ,x_{k}[p(a,n_{0},x_{1},\ldots ,x_{k})=0]\,\}\,}$

Puede verse que esto es cierto simplemente porque hay máquinas universales de Turing capaces de ejecutar cualquier algoritmo. Precisamente esta consecuencia de ${\displaystyle J.R.\,}$ es la que había despertado más suspicacias, haciendo dudar de la veracidad de la hipótesis de Julia Robinson.

Hilary Putnam ha hecho notar que para cada conjunto diofántico ${\displaystyle S\,}$ de enteros positivos existe un polinomio

${\displaystyle q(x_{0},x_{1},\ldots ,x_{n})\,}$

tal que ${\displaystyle S\,}$ está formado precisamente por los números positivos entre los valores supuestos por ${\displaystyle q\,}$ como las variables

${\displaystyle x_{0},x_{1},\ldots ,x_{n}\,}$

recorren todos los números naturales. Esto puede verse como sigue: si

${\displaystyle p(a,y_{1},\ldots ,y_{n})=0\,}$

proporciona una definición diofántica de ${\displaystyle S\,}$, entonces ello basta para fijar

${\displaystyle q(x_{0},x_{1},\ldots ,x_{n})=x_{0}[1-p(x_{0},x_{1},\ldots ,x_{n})^{2}].\,}$

Así, por ejemplo, hay un polinomio para el cual la parte positiva de este intervalo son exactamente los números primos (por otro lado, sin embargo, no existe ningún polinomio que devuelva solo números primos).

Otras aplicaciones tienen que ver con lo que los lógicos denominan proposiciones ${\displaystyle \Pi _{1}^{0}\,}$, llamadas también a veces proposiciones de tipo Goldbach^[7]​ Estas son como la conjetura de Goldbach, propuestas que asignan a todo número natural una propiedad que es comprobable algorítmicamente para cada número en particular^[8]​ El teorema de Matiyasevich/MRDP implica que cada una de tales proposiciones es equivalente a un enunciado que afirma que existe una ecuación diofántica particular que carece de solución en los números naturales.^[9]​ Cierto número de problemas importantes y bien conocidos tienen esta forma, entre ellos el último teorema de Fermat, la hipótesis de Riemann y el teorema de los cuatro colores. Además, la afirmación de que algunos sistemas formales, tales como la aritmética de Peano o el sistema ZFC son consistentes puede expresarse como sentencias ${\displaystyle \Pi _{1}^{0}\,}$. La idea es seguir la estrategia de Kurt Gödel de codificación mediante números naturales de forma tal que la propiedad de ser el número que representa a una demostración sea algorítmicamente comprobable.

Los enunciados ${\displaystyle \Pi _{1}^{0}\,}$ tienen la propiedad de que en el caso de ser falsos, tal falsedad será siempre demostrable en cualquiera de los sistemas formales en uso. Esto se debe a que la falsedad determina la existencia de un contraejemplo que puede ser verificado por aritmética simple. Así, si en uno de estos sistemas formales no pueden probarse ni la proposición ${\displaystyle \Pi _{1}^{0}\,}$ ni su negación, esa proposición debe ser verdadera.

Una forma particularmente impactante del teorema de incompletitud de Gödel es asimismo consecuencia del teorema de Matiyasevich/MRDP.

Sea

${\displaystyle p(a,x_{1},\ldots ,x_{k})=0\,}$

una definición diofántica de un conjunto no computable.

Sea ${\displaystyle A\,}$ un algoritmo que devuelve una sucesión de números naturales ${\displaystyle n\,}$ tal que la ecuación correspondiente

${\displaystyle p(n,x_{1},\ldots ,x_{k})=0\,}$

carece de soluciones en los números naturales. Entonces existe un número ${\displaystyle n_{0}\,}$ que no es devuelto por ${\displaystyle A\,}$, en tanto que, de hecho, la ecuación

${\displaystyle p(n_{0},x_{1},\ldots ,x_{k})=0\,}$

carece de soluciones en los números naturales.

Para darse cuenta de que el teorema es cierto, basta con observar que si no existiera tal número ${\displaystyle n_{0}\,}$, se podría testar algorítmicamente la pertenencia de un número ${\displaystyle n\,}$ a ese conjunto no-computable, haciendo correr simultáneamente el algoritmo ${\displaystyle A\,}$ para comprobar si devuelve ${\displaystyle n\,}$, al tiempo que se comprueban todas las posibles ${\displaystyle k\,}$-tuplas de números naturales buscando una solución de la ecuación

${\displaystyle p(n,x_{1},\ldots ,x_{k})=0.\,}$

Podemos asociar un algoritmo ${\displaystyle A\,}$ con cualquiera de los sistemas formales en uso, tales como la Aritmética de Peano o ZFC, dejando que el algoritmo genere sistemáticamente consecuencias de los axiomas y devuelva un número ${\displaystyle n\,}$ cada vez que se genere una proposición de la forma

${\displaystyle \neg \exists x_{1},\ldots ,x_{k}[p(n,x_{1},\ldots ,x_{k})=0]\,}$

Entonces el teorema nos dice que o bien una proposición falsa del sistema será demostrada de esta forma, o bien una verdadera quedará sin demostrar en el sistema en cuestión, lo que demuestra la incompletitud del sistema.

Podemos aludir al grado de un conjunto diofántico, como el mínimo grado de un polinomio en la ecuación que defina el conjunto. De forma similar, podemos llamar dimensión de un conjunto diofántico al menor número de incógnitas de una ecuación que lo defina. Dado que existe una ecuación diofántica universal, está claro que ambas cantidades, grado y dimensión, tienen cotas superiores absolutas. Determinar estos valores máximos ha despertado mucho interés en los matemáticos.

Ya en los años 1920, Thoralf Skolem mostró que cualquier ecuación diofántica es equivalente a una de grado 4 o inferior. Su estrategia fue introducir nuevas incógnitas añadiendo ecuaciones que las igualaban al cuadrado de una incógnita, o al producto de dos. Repitiendo este proceso se obtiene un sistema de ecuaciones de segundo grado, y sumando luego los cuadrados se pasa a otra de grado 4. Así pues, una ecuación diofántica es de grado 4 o inferior, si bien se desconoce si este resultado es el óptimo.

Julia Robinson y Yuri Matiyasevich mostraron que todo conjunto diofántico tiene dimensión menor o igual que 13. Después, Matiyasevich refinó el método para demostrar que bastaba con 9 incógnitas. Aunque nadie imagina que este sorprendente resultado sea el mejor posible, no ha habido progresos posteriores^[10]​ Así pues, en particular, no existe ningún algoritmo que pueda probar la resolubilidad en los enteros positivos de ecuaciones diofánticas de 9 incógnitas o menos. Para el caso de números enteros (como Hilbert había planteado inicialmente), el truco de los cuatro cuadrados muestra que no hay algoritmo para ecuaciones que no tengan más de 36 incógnitas. Pero Zhi Wei Sun demostró que, tratándose de números enteros, el problema es irresoluble incluso para ecuaciones que no excedan las 11 incógnitas.

Martin Davis estudió problemas algorítmicos relacionados con el número de soluciones de una ecuación diofántica. El décimo problema de Hilbert reclama un algoritmo que decida si el número de soluciones es ${\displaystyle 0\,}$ o distinto de ${\displaystyle 0\,}$. Supongamos que ${\displaystyle A=\{0,1,2,3,\ldots ,\aleph _{0}\}\,}$ y sea ${\displaystyle C\,}$ un subconjunto estricto y no vacío de ${\displaystyle A\,}$. Davis demostró que no existe algoritmo que pueda decidir si una ecuación diofántica dada tiene un número de soluciones que sea elemento del conjunto ${\displaystyle C\,}$. Por tanto, no existe ningún algoritmo que pueda determinar si el número de soluciones es finito o infinito, par o impar, primo o compuesto, cuadrado perfecto, etc.

Aunque Hilbert propuso el problema para el caso de los racionales enteros, es claro que la pregunta puede hacerse para muchos anillos. Ejemplos obvios son los anillos de enteros de cuerpos numéricos algebraicos, así como los números racionales. Seguramente Hilbert era consciente de que un algoritmo como el que estaba reclamando podría extenderse a esas estructuras. Por ejemplo, la ecuación

${\displaystyle p(x_{1},\ldots ,x_{k})=0\,}$

donde ${\displaystyle p\,}$ es un polinomio de grado ${\displaystyle d\,}$ es resoluble en los números racionales negativos si y solo si

${\displaystyle (z+1)^{d}\;p\left({\frac {x_{1}}{z+1}},\ldots ,{\frac {x_{k}}{z+1}}\right)=0\,}$

es resoluble en los números naturales (si se tiene un algoritmo para determinar la resolubilidad en racionales no negativos, podrá usarse fácilmente para determinar la resolubilidad en los racionales). Sin embargo, el conocimiento de que no existe el algoritmo que reclamaba Hilbert no nos aporta ninguna información sobre otras estructuras. Puede existir o no para ellas.

Se ha trabajado mucho en la aplicación del décimo problema de Hilbert a los anillos de enteros de cuerpos algebraicos de números. Basándose en trabajos anteriores de Jan Denef y Leonard Lipschitz, y usando la teoría de clases, Harold N. Shapiro y Alexandra Shlapentokh consiguieron demostrar:

Shlapentokh y Thanases Pheidas (trabajando independientemente) obtuvieron el mismo resultado para cuerpos algebraicos de números que admitan exactamente un par de encajes complejos conjugados.

El problema del anillo de integridad de los cuerpos numéricos algebraicos distintos de los cubiertos por los resultados anteriores sigue estando sin resolver. Asimismo, y pese a despertar mucho interés, el problema sigue también abierto para las ecuaciones sobre los racionales.

• Yuri V. Matiyasevich, Hilbert's Tenth Problem, MIT Press, Cambridge, Massachusetts, 1993.
• Martin Davis, Yuri Matiyasevich, and Julia Robinson, "Hilbert's Tenth Problem: Diophantine Equations: Positive Aspects of a Negative Solution," Proceedings of Symposia in Pure Mathematics, vol.28(1976), pp. 323-378; reprinted in The Collected Works of Julia Robinson, Solomon Feferman, editor, pp.269-378, American Mathematical Society 1996.
• Martin Davis, "Hilbert's Tenth Problem is Unsolvable," American Mathematical Monthly, vol.80(1973), pp. 233-269; reprinted as an appendix in Martin Davis, Computability and Unsolvability, Dover reprint 1982.
• Jan Denef, Leonard Lipschitz, Thanases Pheidas, Jan van Geel, editors, "Hilbert's Tenth Problem: Workshop at Ghent University, Belgium, November 2-5, 1999." Contemporary Mathematics vol. 270(2000), American Mathematical Society.

• Hamilton, A.G. (1981). Lógica para matemáticos. Madrid Paraninfo. ISBN 84-283-1101-3. 
• du Sautoy, Marcus (2007). La música de los números primos. Barcelona, ACANTILADO. ISBN 978-84-96489-83-7. 

• Problemas de Hilbert

• Hilbert's Tenth Problem: a History of Mathematical Discovery
• Hilbert's Tenth Problem page!
• Zhi Wei Sun: On Hilbert's Tenth Problem and Related Topics