El décimo problema de Hilbert

El décimo problema de Hilbert es el décimo de la lista de problemas matemáticos que el matemático alemán David Hilbert planteó en 1900. Consiste en proporcionar un algoritmo general que, para cualquier ecuación diofántica dada (una ecuación polinómica con coeficientes enteros y un número finito de incógnitas), pueda determinar si la ecuación tiene una solución en la que todas las incógnitas toman valores enteros.

Por ejemplo, la ecuación diofántica${\displaystyle 3x^{2}-2xy-y^{2}z-7=0}$tiene una solución entera:${\displaystyle x=1,\ y=2,\ z=-2}$Por el contrario, la ecuación diofántica${\displaystyle x^{2}+y^{2}+1=0}$No existe tal solución.

La solución al décimo problema de Hilbert demuestra que no puede existir un algoritmo tan general. Este es el resultado del trabajo conjunto de Martin Davis , Yuri Matiyasevich , Hilary Putnam y Julia Robinson a lo largo de 21 años, y Matiyasevich completó el teorema en 1970. ^{[ 1 ] [ 2 ] [ 3 ]} El teorema se conoce ahora como el teorema de Matiyasevich o el teorema MRDP (un acrónimo de los apellidos de los cuatro principales contribuyentes a su solución).

Cuando todos los coeficientes y variables están restringidos a ser enteros positivos , el problema relacionado de la prueba de identidad polinómica es una variación decidible (sin exponenciación) del problema de álgebra de la escuela secundaria de Tarski , a veces denotado${\displaystyle {\overline {HSI}}.}$^{[ 4 ]}

El teorema de Matiyasevich/MRDP relaciona dos nociones —una de la teoría de la computabilidad y otra de la teoría de números— y tiene algunas consecuencias sorprendentes. 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})}$de tal manera que, dado cualquier conjunto diofántico${\displaystyle S}$hay un número${\displaystyle n_{0}}$de tal manera que

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

Esto es cierto simplemente porque los conjuntos diofánticos, al ser iguales a los conjuntos recursivamente enumerables, también son iguales a las máquinas de Turing . Es una propiedad bien conocida de las máquinas de Turing que existen máquinas de Turing universales, capaces de ejecutar cualquier algoritmo.

Hilary Putnam ha señalado ^{[ 8 ]} que para cualquier conjunto diofántico${\displaystyle S}$de enteros positivos, existe un polinomio

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

de tal manera que${\displaystyle S}$consiste exactamente en los números positivos entre los valores asumidos por${\displaystyle q}$como las variables

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

abarca todos los números naturales. Esto se puede ver de la siguiente manera: Si

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

proporciona una definición diofántica de${\displaystyle S}$, entonces basta con establecer

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

Así, por ejemplo, existe un polinomio cuya parte positiva de su rango son precisamente los números primos. (Por otro lado, ningún polinomio puede tomar únicamente valores primos). Lo mismo ocurre con otros conjuntos recursivamente enumerables de números naturales: el factorial, los coeficientes binomiales, los números de Fibonacci, etc.

Otras aplicaciones se refieren a lo que los lógicos denominan${\displaystyle \Pi _{1}^{0}}$proposiciones, a veces también llamadas proposiciones de tipo Goldbach . ^{[ b ]} Estas son como la conjetura de Goldbach , al afirmar que todos los números naturales poseen una cierta propiedad que se puede verificar algorítmicamente para cada número en particular. ^{[ c ]} El teorema de Matiyasevich/MRDP implica que cada una de estas proposiciones es equivalente a una afirmación que sostiene que alguna ecuación diofántica en particular no tiene soluciones en los números naturales. ^{[ d ]} Varios problemas importantes y célebres son de esta forma: en particular, el último teorema de Fermat , la hipótesis de Riemann y el teorema de los cuatro colores . Además, la afirmación de que ciertos sistemas formales como la aritmética de Peano o ZFC son consistentes se puede expresar como${\displaystyle \Pi _{1}^{0}}$oraciones. La idea es seguir a Kurt Gödel en la codificación de pruebas mediante números naturales de tal manera que la propiedad de ser el número que representa una prueba sea verificable algorítmicamente.

${\displaystyle \Pi _{1}^{0}}$Las oraciones tienen la propiedad especial de que si son falsas, ese hecho será demostrable en cualquiera de los sistemas formales habituales. Esto se debe a que la falsedad equivale a la existencia de un contraejemplo que puede verificarse mediante aritmética simple. Entonces, si una${\displaystyle \Pi _{1}^{0}}$Si una oración es tal que ni ella ni su negación se pueden probar en uno de estos sistemas, entonces esa oración debe ser verdadera.

Una forma particularmente llamativa del teorema de incompletitud de Gödel es también una consecuencia del teorema de Matiyasevich/MRDP:

Dejar

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

Proporcione una definición diofántica de un conjunto no computable.${\displaystyle A}$ser un algoritmo que produce una secuencia de números naturales${\displaystyle n}$de tal manera que la ecuación correspondiente

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

no tiene soluciones en números naturales. Entonces hay un número${\displaystyle n_{0}}$que no es producido por${\displaystyle A}$mientras que de hecho la ecuación

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

no tiene soluciones en números naturales.

Para comprobar que el teorema es verdadero, basta con observar que si no existiera tal número${\displaystyle n_{0}}$, se podría probar algorítmicamente la pertenencia a un número${\displaystyle n}$en este conjunto no computable ejecutando simultáneamente el algoritmo${\displaystyle A}$para ver si${\displaystyle n}$es la salida mientras también se comprueban todas las posibles${\displaystyle k}$-tuplas de números naturales que buscan una solución de la ecuación

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

y podemos asociar un algoritmo${\displaystyle A}$con cualquiera de los sistemas formales habituales como la aritmética de Peano o ZFC, permitiendo que genere sistemáticamente consecuencias de los axiomas y luego genere un número${\displaystyle n}$siempre que una oración de la forma

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

se genera. Entonces el teorema nos dice que o bien se demuestra una afirmación falsa de esta forma, o bien una verdadera permanece sin demostrar en el sistema en cuestión.

Podemos definir el grado de un conjunto diofántico como el grado mínimo de un polinomio en la ecuación que lo define. De manera similar, podemos llamar a la dimensión de dicho conjunto el número mínimo de incógnitas en la ecuación que lo define. Debido a la existencia de una ecuación diofántica universal, es evidente que existen límites superiores absolutos para ambas cantidades, y ha habido mucho interés en determinar dichos límites.

Ya en la década de 1920, Thoralf Skolem demostró que cualquier ecuación diofántica es equivalente a una de grado 4 o inferior. Su método consistía en introducir nuevas incógnitas mediante ecuaciones que las igualaban al cuadrado de una incógnita o al producto de dos incógnitas. La repetición de este proceso da como resultado un sistema de ecuaciones de segundo grado; luego, sumando los cuadrados, se obtiene una ecuación de grado 4. Por lo tanto, todo conjunto diofántico es trivialmente de grado 4 o inferior. Se desconoce si este resultado es el mejor posible.

Julia Robinson y Yuri Matiyasevich demostraron que todo conjunto diofántico tiene una dimensión no mayor que 13. Posteriormente, Matiyasevich perfeccionó sus métodos para demostrar que 9 incógnitas son suficientes. Aunque es posible que este resultado no sea el mejor posible, no ha habido más progreso. ^{[ e ]} Por lo tanto, en particular, no existe un algoritmo para probar la resolubilidad de ecuaciones diofánticas con 9 o menos incógnitas en números naturales. Para el caso de soluciones racionales enteras (como lo planteó originalmente Hilbert), el truco de los 4 cuadrados muestra que no existe un algoritmo para ecuaciones con no más de 36 incógnitas. Pero Zi-Wei Sun demostró que el problema para enteros es irresoluble incluso para ecuaciones con no más de 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 pregunta si ese número es 0 o no. Sea${\displaystyle A=\{0,1,2,3,\ldots ,\aleph _{0}\}}$y dejar${\displaystyle C}$ser un subconjunto propio no vacío de${\displaystyle A}$Davis demostró que no existe ningún algoritmo para probar una ecuación diofántica dada para determinar si el número de sus soluciones pertenece al conjunto${\displaystyle C}$Por lo tanto, no existe ningún algoritmo para determinar si el número de soluciones de una ecuación diofántica es finito, impar, un cuadrado perfecto, un número primo, etc.

La demostración del teorema MRDP se ha formalizado en Rocq (anteriormente conocido como Coq ). ^{[ 9 ]}

Aunque Hilbert planteó el problema para los enteros racionales, también puede plantearse para muchos anillos (en particular, para cualquier anillo cuyo número de elementos sea numerable ). Ejemplos obvios son los anillos de enteros de cuerpos de números algebraicos , así como los anillos de números racionales .

Se ha trabajado mucho en el décimo problema de Hilbert para los anillos de enteros de cuerpos numéricos algebraicos. Basándose en trabajos anteriores de Jan Denef y Leonard Lipschitz y utilizando la teoría de cuerpos de clases, Harold N. Shapiro y Alexandra Shlapentokh pudieron demostrar:

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

Shlapentokh y Thanases Pheidas (de forma independiente) obtuvieron el mismo resultado para cuerpos numéricos algebraicos que admiten exactamente un par de incrustaciones conjugadas complejas.

El problema del anillo de enteros de cuerpos numéricos algebraicos distintos de los cubiertos por los resultados anteriores permanece abierto. De igual modo, a pesar del gran interés suscitado, el problema de las ecuaciones sobre los racionales sigue abierto. Barry Mazur ha conjeturado que, para cualquier variedad sobre los racionales, la clausura topológica sobre los reales del conjunto de soluciones tiene solo un número finito de componentes. ^{[ 10 ]} Esta conjetura implica que los enteros no son diofánticos sobre los racionales, por lo que, si esta conjetura es cierta, una respuesta negativa al Décimo Problema de Hilbert requeriría un enfoque diferente al utilizado para otros anillos.

En 2024, Peter Koymans y Carlo Pagano publicaron una supuesta demostración de que el décimo problema de Hilbert es indecidible para todo anillo de enteros utilizando combinatoria aditiva . ^{[ 11 ] [ 12 ]} Posteriormente, otro equipo de matemáticos afirmó otra demostración del mismo resultado, utilizando métodos diferentes. ^{[ 11 ] [ 13 ]}

• El problema de álgebra de la escuela secundaria de Tarski

• Hilbert, David (1901). "Problema matemático". Archiv der Mathematik und Physik . 3ª serie (en alemán). 1 : 44-63 , 213-247 .
• Davis, Martin ; Matiyasevich, Yuri ; Robinson, Julia (1976). «El décimo problema de Hilbert: ecuaciones diofánticas: aspectos positivos de una solución negativa». En Felix E. Browder (ed.). Desarrollos matemáticos derivados de los problemas de Hilbert . Actas de simposios de matemáticas puras . Vol.  XXVIII.2. Sociedad Matemática Americana . págs. 323–378 . ISBN  0-8218-1428-1. Zbl 0346.02026 .  Reimpreso en The Collected Works of Julia Robinson , Solomon Feferman , editor, pp.  269 – 378, American Mathematical Society 1996.
• Martin Davis , " El décimo problema de Hilbert es irresoluble", American Mathematical Monthly , vol. 80 (1973), págs.  233-269 ; reimpreso como apéndice en Martin Davis, Computability and Unsolvability , reimpresión de Dover de 1982.
• Davis, Martin ; Hersh, Reuben (1973). "El décimo problema de Hilbert". Scientific American . 229 (5): 84– 91. Bibcode : 1973SciAm.229e..84D . doi : 10.1038/scientificamerican1173-84 .
• Jan Denef , Leonard Lipschitz, Thanases Pheidas, Jan van Geel, editores, "El décimo problema de Hilbert: Taller en la Universidad de Gante, Bélgica, del 2 al 5 de noviembre de 1999" . Contemporary Mathematics vol. 270 (2000), American Mathematical Society.
• M. Ram Murty y Brandon Fodden: «El décimo problema de Hilbert: una introducción a la lógica, la teoría de números y la computabilidad», American Mathematical Society, ISBN 978-1-4704-4399-3(Junio ​​de 2019).
• Shlapentokh, Alexandra (2007). El décimo problema de Hilbert. Clases diofánticas y extensiones a cuerpos globales . Nuevas Monografías Matemáticas. Vol.  7. Cambridge: Cambridge University Press . ISBN 978-0-521-83360-8. Zbl 1196.11166 . 

• El décimo problema de Hilbert: una historia del descubrimiento matemático.
• ¡Página del décimo problema de Hilbert!
• Sun, Zhi-Wei (14 de abril de 2000). "Sobre el décimo problema de Hilbert y temas relacionados" (PDF) . maths.nju.edu.cn . Consultado el 27 de septiembre de 2025 .
• Tráiler de Julia Robinson y el décimo problema de Hilbert en YouTube