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:

Dada una ecuación diofántica con cualquier número de incógnitas y con coeficientes numéricos racionales enteros:

Idear un proceso de acuerdo con el cual pueda determinarse, en un número finito de operaciones, si la ecuación es resoluble en números racionales enteros.

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:

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,3ldots },}$,^[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} ,}$.

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

es equivalente a la ecuación individual

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:

Todo conjunto recursivamente enumerable es diofántico.

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

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

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.

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.

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

pero para cada ${displaystyle k>0,}$,

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.

${displaystyle (a,b),}$ tal que

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.

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

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

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

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

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

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

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

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

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

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

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

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:

El décimo problema de Hilbert es irresoluble para el anillo de integridad de cualquier cuerpo numérico algebraico cuyo grupo de Galois sobre los racionales sea abeliano.

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.

---