Décimo problema de Hilbert

Sobre la solubilidad de las ecuaciones diofánticas

El décimo problema de Hilbert es el décimo en 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), pueda 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. ${\displaystyle 3x^{2}-2xy-y^{2}z-7=0}$ ${\displaystyle x=1,\ y=2,\ z=-2}$ ${\displaystyle x^{2}+y^{2}+1=0}$

El décimo problema de Hilbert ha sido resuelto y tiene una respuesta negativa: no puede existir un algoritmo tan general. Este es el resultado del trabajo combinado de Martin Davis , Yuri Matiyasevich , Hilary Putnam y Julia Robinson que se extendió durante 21 años, y Matiyasevich completó el teorema en 1970. ^[1] El teorema ahora se conoce como el teorema de Matiyasevich o el teorema MRDP (una sigla 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 polinomial se convierte en una variación decidible (libre de exponenciación) del problema de álgebra de secundaria de Tarski , a veces denotado ^[2] ${\displaystyle {\overline {HSI}}.}$

Fondo

Formulación original

Hilbert formuló el problema de la siguiente manera: ^[3]

Dada una ecuación diofántica con cualquier número de cantidades desconocidas 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 resoluble en números enteros racionales.

Las palabras "proceso" y "número finito de operaciones" se han interpretado como que Hilbert estaba pidiendo un algoritmo . El término "integral racional" se refiere simplemente a los números enteros, positivos, negativos o cero: 0, ±1, ±2, ... . Por lo tanto, Hilbert estaba pidiendo un algoritmo general para decidir si una ecuación diofántica polinómica dada con coeficientes enteros tiene una solución en números enteros.

El problema de Hilbert no se ocupa de encontrar las 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 .

Conjuntos diofánticos

En una ecuación diofántica, hay dos tipos de variables: los parámetros y las incógnitas. El conjunto diofántico consta de las 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,

${\displaystyle a_{1}x+a_{2}y=a_{3}}$,

donde la ecuación es resoluble si y solo si el máximo común divisor divide exactamente a . 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. ${\displaystyle \gcd(a_{1},a_{2})}$ ${\displaystyle a_{3}}$ ${\displaystyle (a_{1},a_{2},a_{3})}$ ${\displaystyle a_{1}x+a_{2}y=a_{3}}$

El problema se entiende generalmente en términos de números naturales (es decir, los enteros no negativos) en lugar de 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 para convertirlo en un algoritmo que decida si una ecuación diofántica dada tiene una solución en números naturales, y viceversa. Por el teorema de los cuatro cuadrados de Lagrange , cada número natural es la suma de los cuadrados de cuatro enteros, por lo que podríamos reescribir cada parámetro de valor natural en términos de la suma de los cuadrados de cuatro nuevos parámetros de valor entero. De manera similar, dado que cada entero es la diferencia de dos números naturales, podríamos reescribir cada parámetro 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 . ${\displaystyle p_{1}=0,\ldots ,p_{k}=0}$ ${\displaystyle p_{i}}$ ${\displaystyle p_{1}^{\,2}+\cdots +p_{k}^{\,2}=0}$

Conjuntos enumerables recursivamente

Un conjunto recursivamente enumerable puede caracterizarse como aquel para el cual existe un algoritmo que finalmente se detendrá cuando se proporcione un miembro del conjunto como entrada, pero puede continuar indefinidamente cuando la entrada no sea un miembro. Fue el desarrollo de la teoría de la computabilidad (también conocida como teoría de la recursión) 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 sea perfectamente rigurosa. Es evidente que los conjuntos diofánticos son recursivamente enumerables (también conocidos como semidecidibles). Esto se debe a que uno puede ordenar todas las tuplas posibles de valores de las incógnitas en una secuencia y luego, para un valor dado del parámetro o parámetros, probar estas tuplas, una tras otra, para ver si son soluciones de la ecuación correspondiente. La imposibilidad de resolver el décimo problema de Hilbert es una consecuencia del hecho sorprendente de que la inversa es cierta:

Todo conjunto enumerable recursivamente es diofántico.

Este resultado se conoce como teorema de Matiyasevich (porque proporcionó el paso crucial que completó la prueba) y teorema MRDP (por Yuri Matiyasevich , Julia Robinson , Martin Davis y Hilary Putnam ). Debido a que existe un conjunto recursivamente enumerable que no es computable, la imposibilidad de solución del décimo problema de Hilbert es una consecuencia inmediata. De hecho, se puede decir más: existe un polinomio

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

con coeficientes enteros tales que el conjunto de valores de para los cuales la ecuación ${\displaystyle a}$

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

tiene soluciones en números naturales no es computable. Por lo tanto, no sólo no existe un algoritmo general para probar la solubilidad de las ecuaciones diofánticas, sino que tampoco existe ninguno para esta familia de ecuaciones de un solo parámetro.

Historia

Aplicaciones

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. Tal vez la más sorprendente sea la existencia de una ecuación diofántica universal :

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

$${\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 enumerables recursivamente, 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 que para cualquier conjunto diofántico de números enteros positivos, existe un polinomio ${\displaystyle S}$

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

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

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

rango de 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 , entonces basta con establecer ${\displaystyle S}$

$${\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 cuya parte positiva de su rango son exactamente los números primos. (Por otra parte, ningún polinomio puede tomar únicamente 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] Estas son como la conjetura de Goldbach , al afirmar que todos los números naturales poseen una cierta propiedad que es algorítmicamente comprobable para cada número particular. ^[9] El teorema de Matiyasevich/MRDP implica que cada una de esas proposiciones es equivalente a una afirmación que afirma que alguna ecuación diofántica particular no tiene soluciones en números naturales. ^[10] Una serie de 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 por números naturales de tal manera que la propiedad de ser el número que representa una prueba sea algorítmicamente comprobable. ${\displaystyle \Pi _{1}^{0}}$ ${\displaystyle \Pi _{1}^{0}}$

${\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 usuales. Esto se debe a que la falsedad equivale a la existencia de un contraejemplo que puede verificarse mediante aritmética simple. Por lo tanto, 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 requerida ]} ${\displaystyle \Pi _{1}^{0}}$

Una forma particularmente sorprendente 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. Sea un algoritmo que genera una secuencia de números naturales tal que la ecuación correspondiente ${\displaystyle A}$ ${\displaystyle n}$

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

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

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

no tiene soluciones en números naturales.

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

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

y podemos asociar un algoritmo con cualquiera de los sistemas formales usuales, 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 aparece una oración de la forma ${\displaystyle A}$ ${\displaystyle n}$

${\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 un enunciado falso de esta forma o bien queda sin demostrar uno verdadero en el sistema en cuestión.

Resultados adicionales

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 decir que la dimensión de un conjunto de este tipo es la menor cantidad de incógnitas en una ecuación definitoria. 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 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 inferior. 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; 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. 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 afinó sus métodos para demostrar que bastan 9 incógnitas. Aunque bien puede ser que este resultado no sea el mejor posible, no ha habido ningún progreso posterior. ^[11] Así, en particular, no existe un 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 es irresoluble incluso para ecuaciones con no más de 11 incógnitas.

Martin Davis estudió cuestiones algorítmicas que involucran el número de soluciones de una ecuación diofántica. El décimo problema de Hilbert pregunta si ese número es o no 0. Sea y sea un subconjunto propio no vacío de . Davis demostró que no existe un algoritmo para probar una ecuación diofántica dada para determinar si el número de sus soluciones es un miembro del conjunto . Por lo tanto, no existe un algoritmo para determinar si el número de soluciones de una ecuación diofántica es finito, impar, un cuadrado perfecto, un primo, etc. ${\displaystyle A=\{0,1,2,3,\ldots ,\aleph _{0}\}}$ ${\displaystyle C}$ ${\displaystyle A}$ ${\displaystyle C}$

La prueba del teorema MRDP se ha formalizado en Coq . ^[12]

Extensiones del décimo problema de Hilbert

Alexandra Shlapentokh (en el centro) en 2003

Aunque Hilbert planteó el problema para los números 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 los números enteros de los cuerpos de números 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 cuerpos de números 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 números enteros de cualquier cuerpo de números algebraicos cuyo grupo de Galois sobre los racionales sea abeliano .

Shlapentokh y Thanases Pheidas (independientemente uno del otro) obtuvieron el mismo resultado para cuerpos de números algebraicos que admitían exactamente un par de incrustaciones conjugadas complejas.

El problema para el anillo de números enteros de cuerpos de números algebraicos distintos de los cubiertos por los resultados anteriores sigue abierto. Asimismo, a pesar del gran interés, el problema para 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.

Notas

1. S. Barry Cooper , Teoría de la computabilidad , pág. 98
2. Stanley Burris, Simon Lee, Las identidades de Tarski en la escuela secundaria , American Mathematical Monthly , 100 , (1993), n.º 3, págs. 231–236.
3. Hilbert 1902, pág. 458.
4. Yuri Matiyasevich (1993). El décimo problema de Hilbert . Prensa del MIT.
5. Una revisión de la publicación conjunta de Davis, Putnam y Robinson en Mathematical Reviews ( MR 0133227) conjeturó, en efecto, que JR era falsa.
6. Matiyasevich, Yuri (1992). "Mi colaboración con Julia Robinson". The Mathematical Intelligencer . 14 (4): 38–45. doi :10.1007/bf03024472. S2CID  123582378.
7. Sacks, Gerald E. (2003). Lógica matemática en el siglo XX . World Scientific. págs. 269–273.
8. Las oraciones se encuentran en uno de los niveles más bajos de la llamada jerarquía aritmética . ${\displaystyle \Pi _{1}^{0}}$
9. Así, la propia conjetura de Goldbach puede expresarse diciendo que, para cada número natural, el número es la suma de dos números primos. Por supuesto, existe un algoritmo sencillo para comprobar si un número dado es la suma de dos números primos. ${\displaystyle n}$ ${\displaystyle 2n+4}$
10. De hecho, la equivalencia es demostrable en la aritmética de Peano .
11. En este punto, ni siquiera 3 puede excluirse como límite superior absoluto.
12. Dominique Larchey-Wendling y Yannick Forster (2019). El décimo problema de Hilbert en Coq (PDF) (Informe técnico). Universidad del Sarre .
13. Poonen, Bjorn (2003). "El décimo problema de Hilbert y la conjetura de Mazur para grandes subanillos de Q {\displaystyle \mathbb {Q} }" (PDF) . Revista de la Sociedad Matemática Americana . 16 (4): 981–990. doi :10.1090/S0894-0347-03-00433-8. MR  1992832. S2CID  8486815.

Referencias

• Hilbert, David (1901). "Problema matemático". Archiv der Mathematik und Physik . 3ª serie (en alemán). 1 : 44–63, 213–247.
• Hilbert, David (julio de 1902). "Problemas matemáticos". Bull. Amer. Math. Soc. 8 (10): 437–479. doi : 10.1090/S0002-9904-1902-00923-3 .
• Yuri V. Matiyasevich , El décimo problema de Hilbert , MIT Press, Cambridge, Massachusetts, 1993.
• 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 sobre 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, págs. 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, 1982.
• Davis, Martin ; Hersh, Reuben (1973). "El décimo problema de Hilbert". Scientific American . 229 (5): 84–91. Código Bibliográfico :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). 

Lectura adicional

• El problema de álgebra de la escuela secundaria de Tarski
• 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  .

Enlaces externos

• El décimo problema de Hilbert: una historia del descubrimiento matemático
• ¡Página del décimo problema de Hilbert!
• Zhi Wei Sun: Sobre el décimo problema de Hilbert y temas relacionados
• Tráiler de El décimo problema de Julia Robinson y Hilbert en YouTube