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. Es el desafío de 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), puede decidir si la ecuación tiene una solución con todas las incógnitas tomando valores enteros.
Por ejemplo, la ecuación diofántica tiene una solución entera: . Por el contrario, la ecuación diofántica no tiene tal solución.
El décimo problema de Hilbert ha sido resuelto y tiene una respuesta negativa: un algoritmo tan general no puede existir. Este es el resultado del trabajo combinado de Martin Davis , Yuri Matiyasevich , Hilary Putnam y Julia Robinson que abarca 21 años, y Matiyasevich completó el teorema en 1970. [1] El teorema ahora se conoce como teorema de Matiyasevich o teorema MRDP (una inicialización para los apellidos de los cuatro principales contribuyentes a su solución).
Cuando todos los coeficientes y variables se restringen a ser números enteros positivos , el problema relacionado de la prueba de identidad polinómica se convierte en una variación decidible (libre de exponenciación) del problema de álgebra de la escuela secundaria de Tarski , a veces denotado [2]
Hilbert formuló el problema de la siguiente manera: [3]
Dada una ecuación diofántica con cualquier número de incógnitas y con coeficientes numéricos integrales racionales: Idear un proceso según el cual se pueda determinar en un número finito de operaciones si la ecuación es solucionable en números enteros racionales.
Se ha interpretado que las palabras "proceso" y "número finito de operaciones" significan que Hilbert estaba pidiendo un algoritmo . El término "integral racional" simplemente se refiere a los números enteros, positivos, negativos o cero: 0, ±1, ±2,.... Entonces Hilbert estaba pidiendo un algoritmo general para decidir si una ecuación polinómica diofántica dada con coeficientes enteros tiene una solución en números enteros.
El problema de Hilbert no se refiere a encontrar soluciones. Sólo pregunta si, en general, podemos decidir si existen una o más soluciones. La respuesta a esta pregunta es negativa, en el sentido de que no se puede idear ningún "proceso" para responder a esa pregunta. En términos modernos, el décimo problema de Hilbert es un problema indecidible .
En una ecuación diofántica, hay dos tipos de variables: los parámetros y las incógnitas. El conjunto diofántico consta de asignaciones de parámetros para las que se puede resolver la ecuación diofántica. Un ejemplo típico es la ecuación diofántica lineal con dos incógnitas,
donde la ecuación se puede resolver si y solo si el máximo común divisor divide uniformemente . El conjunto de todas las ternas ordenadas que satisfacen esta restricción se denomina conjunto diofántico definido por . En estos términos, el décimo problema de Hilbert pregunta si existe un algoritmo para determinar si el conjunto diofántico correspondiente a un polinomio arbitrario no está vacío.
El problema generalmente se entiende en términos de números naturales (es decir, enteros no negativos) en lugar de números enteros arbitrarios. Sin embargo, los dos problemas son equivalentes: cualquier algoritmo general que pueda decidir si una ecuación diofántica dada tiene una solución entera podría modificarse en un algoritmo que decida si una ecuación diofántica dada tiene una solución en números naturales, y viceversa. Según el teorema de los cuatro cuadrados de Lagrange , cada número natural es la suma de los cuadrados de cuatro números enteros, por lo que podríamos reescribir cada parámetro con valores naturales en términos de la suma de los cuadrados de cuatro nuevos parámetros con valores enteros. De manera similar, dado que cada número entero es la diferencia de dos números naturales, podríamos reescribir cada parámetro de un entero como la diferencia de dos parámetros naturales. [4] Además, siempre podemos reescribir un sistema de ecuaciones simultáneas (donde cada una es un polinomio) como una sola ecuación .
Un conjunto recursivamente enumerable se puede caracterizar como uno para el cual existe un algoritmo que finalmente se detendrá cuando un miembro del conjunto se proporcione como entrada, pero que puede continuar indefinidamente cuando la entrada no sea miembro. Fue el desarrollo de la teoría de la computabilidad (también conocida como teoría de la recursividad) lo que proporcionó una explicación precisa de la noción intuitiva de computabilidad algorítmica, haciendo así que la noción de enumerabilidad recursiva fuera perfectamente rigurosa. Es evidente que los conjuntos diofánticos son recursivamente enumerables (también conocidos como semidecidibles). Esto se debe a que se pueden ordenar todas las tuplas posibles de valores de las incógnitas en una secuencia y luego, para un valor dado de los parámetros, probar estas tuplas, una tras otra, para ver si son soluciones de la ecuación correspondiente. La insolubilidad del décimo problema de Hilbert es consecuencia del hecho sorprendente de que ocurre lo contrario:
Todo conjunto recursivamente enumerable es diofántico.
Este resultado se conoce como teorema de Matiyasevich (porque proporcionó el paso crucial que completó la demostración) y teorema de MRDP (por Yuri Matiyasevich , Julia Robinson , Martin Davis y Hilary Putnam ). Como existe un conjunto recursivamente enumerable que no es computable, la insolubilidad del décimo problema de Hilbert es una consecuencia inmediata. De hecho, se puede decir más: existe un polinomio
con coeficientes enteros tales que el conjunto de valores para los cuales la ecuación
tiene soluciones en números naturales no es computable. Entonces, no solo no existe un algoritmo general para probar la solubilidad de las ecuaciones diofánticas, sino que incluso para esta familia de ecuaciones de un solo parámetro, no existe ningún algoritmo.
El teorema de Matiyasevich/MRDP relaciona dos nociones (una de la teoría de la computabilidad y la otra de la teoría de números) y tiene algunas consecuencias sorprendentes. Quizás lo más sorprendente sea la existencia de una ecuación diofántica universal :
Esto es cierto simplemente porque los conjuntos diofánticos, al ser iguales a los conjuntos recursivamente enumerables, también lo son 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 que para cualquier conjunto diofántico de números enteros positivos, existe un polinomio
tal que consiste exactamente en los números positivos entre los valores asumidos por las variables
abarca todos los números naturales. Esto se puede ver de la siguiente manera: Si
proporciona una definición diofántica de , entonces basta con establecer
Entonces, por ejemplo, hay un polinomio para el cual la parte positiva de su rango son exactamente los números primos. (Por otro lado, ningún polinomio sólo puede tomar valores primos). Lo mismo se aplica a otros conjuntos de números naturales recursivamente enumerables: el factorial, los coeficientes binomiales, los números de Fibonacci, etc.
Otras aplicaciones se refieren a lo que los lógicos denominan proposiciones, a veces también llamadas proposiciones de tipo Goldbach . [8] Estos son como la conjetura de Goldbach , al afirmar que todos los números naturales poseen una determinada propiedad que es comprobable algorítmicamente para cada número en particular. [9] El teorema de Matiyasevich/MRDP implica que cada una de estas proposiciones es equivalente a una afirmación que afirma que alguna ecuación diofántica particular no tiene soluciones en números naturales. [10] 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 sistemas formales particulares como la aritmética de Peano o ZFC son consistentes se puede expresar como 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 algorítmicamente comprobable.
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 simple aritmética. Entonces, si una oración es tal que ni ella ni su negación son demostrables en uno de estos sistemas, esa oración debe ser verdadera. [ cita necesaria ]
Una forma particularmente sorprendente del teorema de incompletitud de Gödel es también consecuencia del teorema de Matiyasevich/MRDP:
Dejar
proporcionar una definición diofántica de un conjunto no computable. Sea un algoritmo que genere una secuencia de números naturales tal que la ecuación correspondiente
no tiene soluciones en números naturales. Entonces hay un número que no se genera cuando en realidad la ecuación
no tiene soluciones en números naturales.
Para ver que el teorema es verdadero, basta notar que si no existiera tal número , se podría probar algorítmicamente la pertenencia de un número a este conjunto no computable ejecutando simultáneamente el algoritmo para ver si se genera y al mismo tiempo verificar todos los posibles . tuplas de números naturales que buscan una solución de la ecuación
y podemos asociar un algoritmo con cualquiera de los sistemas formales habituales, como la aritmética de Peano o ZFC , permitiéndole generar sistemáticamente consecuencias de los axiomas y luego generar un número cada vez que una oración de la forma
es generado. Entonces el teorema nos dice que o un enunciado falso de esta forma queda demostrado o uno verdadero permanece sin demostrar en el sistema en cuestión.
Podemos hablar del grado de un conjunto diofántico como el menor grado de un polinomio en una ecuación que define ese conjunto. De manera similar, podemos llamar a la dimensión de dicho conjunto la menor cantidad de incógnitas en una ecuación definitoria. Debido a la existencia de una ecuación diofántica universal, está claro que existen límites superiores absolutos para ambas cantidades, y ha habido mucho interés en determinar estos 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 menos. Su truco 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; entonces se obtiene una ecuación de grado 4 sumando los cuadrados. Entonces, cada conjunto diofántico es trivialmente de grado 4 o menos. No se sabe 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. Más tarde, 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 avances. [11] Entonces, en particular, no existe ningún algoritmo para probar la solubilidad de ecuaciones diofánticas con 9 o menos incógnitas en números naturales. Para el caso de soluciones enteras racionales (como Hilbert lo había planteado originalmente), el truco de los 4 cuadrados muestra que no existe un algoritmo para ecuaciones con no más de 36 incógnitas. Pero Zhi Wei Sun demostró que el problema de los números enteros no tiene solución incluso para ecuaciones con no más de 11 incógnitas.
Martin Davis estudió cuestiones algorítmicas relacionadas 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 y sea un subconjunto adecuado no vacío de . 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 es miembro del conjunto . Por tanto, no existe ningún algoritmo para determinar si el número de soluciones de una ecuación diofántica es finita, impar, cuadrado perfecto, prima, etc.
La demostración del teorema MRDP ha sido formalizada en Coq . [12]
Aunque Hilbert planteó el problema para los números enteros racionales, también se puede plantear para muchos anillos (en particular, para cualquier anillo cuyo número de elementos sea contable ). Ejemplos obvios son los anillos de números enteros de campos numéricos algebraicos , así como los números racionales .
Se ha trabajado mucho en el décimo problema de Hilbert para los anillos de números enteros de campos numéricos algebraicos. Basándose en trabajos anteriores de Jan Denef y Leonard Lipschitz y utilizando la teoría de campos de clases, Harold N. Shapiro y Alexandra Shlapentokh pudieron demostrar:
El décimo problema de Hilbert no tiene solución para el anillo de números enteros de cualquier campo numérico algebraico cuyo grupo de Galois sobre los racionales sea abeliano .
Shlapentokh y Thanases Pheidas (independientemente uno del otro) obtuvieron el mismo resultado para campos de números algebraicos que admiten exactamente un par de incrustaciones conjugadas complejas.
El problema del anillo de números enteros de campos numéricos algebraicos distintos de los cubiertos por los resultados anteriores permanece abierto. Asimismo, a pesar del gran interés, el problema de las ecuaciones sobre los racionales sigue abierto. Barry Mazur ha conjeturado que para cualquier variedad sobre los racionales, el cierre topológico sobre los reales del conjunto de soluciones tiene sólo un número finito de componentes. [13] Esta conjetura implica que los números enteros no son diofánticos sobre los racionales y, por lo tanto, si esta conjetura es cierta, una respuesta negativa al Décimo Problema de Hilbert requeriría un enfoque diferente al utilizado para otros anillos.
![{\displaystyle S=\{\,a\mid \existe x_{1},\ldots ,x_{k}[p(a,n_{0},x_{1},\ldots ,x_{k})= 0]\,\}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b1f9d623436e8c344911650e2fea17df2a729127)
![{\displaystyle q(x_{0},x_{1},\ldots ,x_{n})=x_{0}[1-p(x_{0},x_{1},\ldots ,x_{n} )^{2}].}](https://wikimedia.org/api/rest_v1/media/math/render/svg/9233a68b8b8f4414dc29d56ef48a955caa1801fc)
![{\displaystyle \neg \exists x_{1},\ldots ,x_{k}[p(n,x_{1},\ldots ,x_{k})=0]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5da04caabd441b185e9d103c919907ac5565679a)
