Décimo problema de Hilbert

El décimo problema de Hilbert es el décimo de la lista de problemas matemáticos que planteó el matemático alemán David Hilbert en 1900. El reto es proporcionar un algoritmo general que, para cualquier La ecuación diofántica (una ecuación polinomial 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 Diofantina ${displaystyle 3x^{2}-2xy-y^{2}z-7=0}$ tiene una solución de entero: ${displaystyle x=1, y=2, z=-2}$. Por el contrario, la ecuación Diofantina ${displaystyle x^{2}+y^{2}+1=0}$ no tiene tal solución.

El décimo problema de Hilbert ha sido resuelto y tiene una respuesta negativa: tal algoritmo general no existe. Este es el resultado del trabajo combinado de Martin Davis, Yuri Matiyasevich, Hilary Putnam y Julia Robinson que abarca 21 años, con Matiyasevich completando el teorema en 1970. El teorema ahora se conoce como el teorema de Matiyasevich o el teorema MRDP (un inicialismo de los apellidos de los cuatro principales contribuyentes a su solución).

Cuando todos los coeficientes y variables están restringidos a ser positivo integers, el problema relacionado de las pruebas de identidad polinomial se convierte en una variación (sin expansión) de Tarski del problema del álgebra de secundaria, a veces denotado ${displaystyle {overline {}}}$

Antecedentes

Formulación original

Hilbert formuló el problema de la siguiente manera:

Dada una ecuación de Diofantina con cualquier número de cantidades desconocidas y con coeficientes numéricos integrales racionales: Desarrollar un proceso según el cual se puede determinar en un número finito de operaciones si la ecuación es solvable en enteros racionales.

Las palabras "proceso" y "número finito de operaciones" se han interpretado en el sentido de que Hilbert estaba pidiendo un algoritmo. El término "integral racional" simplemente se refiere a los números enteros, positivo, negativo o cero: 0, ±1, ±2,.... Así que Hilbert estaba pidiendo un algoritmo general para decidir si una ecuación polinomial diofantina dada con coeficientes enteros tiene una solución en números enteros.

El problema de Hilbert no tiene que ver con encontrar las soluciones. Solo 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" por responder a esa pregunta. En términos modernos, el décimo problema de Hilbert es un problema indecidible. Aunque es poco probable que Hilbert hubiera concebido tal posibilidad, antes de pasar a enumerar los problemas, comentó proféticamente:

Ocasionalmente sucede que buscamos la solución bajo hipótesis insuficientes o en un sentido incorrecto, y por esta razón no tienen éxito. El problema surge entonces: mostrar la imposibilidad de la solución bajo las hipótesis dadas o en el sentido contemplado.

Probar que el décimo problema es indecidible es entonces una respuesta válida incluso en los términos de Hilbert, ya que es una prueba sobre "la imposibilidad de la solución".

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_{1}+a_{2}x_{2}=a_{3}$,

donde la ecuación es solvable cuando el mayor divisor común ${displaystyle a_{1},a_{2}$ divideciones ${displaystyle A_{3}$. Los valores para ${displaystyle a_{1},a_{2},a_{3}$ que satisfacen esta restricción son un conjunto de Diofantina y la ecuación anterior es su definición de Diofantina.

Las definiciones diofánticas pueden ser proporcionadas por sistemas simultáneos de ecuaciones así como por ecuaciones individuales porque el sistema

${displaystyle p_{1}=0,ldotsp_{k}=0}$

es equivalente a la ecuación simple

${displaystyle P_{1}{2}+cdots ¿Qué?$

Los conjuntos de números naturales, de pares de números naturales (o incluso de n-tuplas de números naturales) que tienen definiciones diofánticas se denominan conjuntos diofánticos. En estos términos, el décimo problema de Hilbert pregunta si existe un algoritmo para determinar si un conjunto diofántico dado no está vacío.

El trabajo sobre el problema ha sido en términos de soluciones en números naturales (entendidos como los números enteros no negativos) en lugar de números enteros arbitrarios. 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 un número natural, y viceversa. Esto se puede ver de la siguiente manera: el requisito de que las soluciones sean números naturales se puede expresar con la ayuda del teorema de los cuatro cuadrados de Lagrange: cada número natural es la suma de los cuadrados de cuatro enteros, por lo que simplemente reemplazamos cada parámetro con la suma de los cuadrados de cuatro parámetros adicionales. De manera similar, dado que cada número entero se puede escribir como la diferencia de dos números naturales, podemos reemplazar cada parámetro que varía en números enteros con la diferencia de dos parámetros que varían en números naturales.

Conjuntos recursivamente enumerables

Un conjunto recursivamente enumerable se puede caracterizar como uno para el que 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 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í perfectamente rigurosa la noción de enumerabilidad recursiva. Es evidente que los conjuntos diofánticos son recursivamente enumerables (también conocidos como semidecidibles). Esto se debe a que uno puede organizar 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 imposibilidad de resolver el décimo problema de Hilbert es una consecuencia del hecho sorprendente de que lo contrario es cierto:

Cada conjunto repetidamente enumerable es Diofantina.

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

${displaystyle p(a,x_{1},ldotsx_{n}}$

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

${displaystyle p(a,x_{1},ldotsx_{n}=0}$

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

Historia

Año	Eventos
1944	Emil Leon Post declara que el décimo problema de Hilbert "pega por una prueba de insolvabilidad".
1949	Martin Davis utiliza el método de Kurt Gödel para aplicar el teorema del resto chino como un truco de codificación para obtener su forma normal para conjuntos repetidamente enumerables: ${displaystyle left{amid exists yforall kleqslant yexists x_{1},ldotsx_{n}:pleft(a,k,y,x_{1},ldotsx_{n}right)=0right}$ Donde ${displaystyle p}$ es un polinomio con coeficientes enteros. Puramente formalmente, es sólo el cuantificador universal atado que se interpone en el camino de ser una definición Diofantina. Usando una prueba no constructiva pero fácil, deriva como corolario a esta forma normal que el conjunto de conjuntos de Diofantina no se cierra bajo la complementación, mostrando que existe un conjunto de Diofantina cuyo complemento no es Diofantina. Debido a que los conjuntos recurrentemente enumerables también no están cerrados bajo la complementación, él conjetura que las dos clases son idénticas.
1950	Julia Robinson, sin darse cuenta del trabajo de Davis, investiga la conexión de la función exponencial al problema, e intenta demostrar que EXP, el conjunto de trillizos ${displaystyle (a,b,c)}$ para la cual ${displaystyle a=b^{c}$Es Diofantina. No tiene éxito, hace lo siguiente hipótesis (Más tarde J.R.): Hay un juego de Diofantina ${displaystyle D}$ de pares ${displaystyle (a,b)}$ tales que ${displaystyle (a,b)in DRightarrow b madea^{a}$ y para todos los positivos ${displaystyle k,}$ existe ${displaystyle (a,b)in D}$ tales que ${displaystyle b confiara^{k}$ Utilizando propiedades de la ecuación Pell, demuestra que J.R. implica que EXP es Diophantine, así como los coeficientes binomiales, el factorial y los primos.
1959	Trabajando juntos, Davis y Putnam estudio exponencial Diophantine sets: establece definibles por ecuaciones Diophantine en las que algunos de los exponentes pueden ser desconocidos. Usando la forma normal de Davis junto con los métodos de Robinson, y asumiendo la entonces conjetura no comprobada que hay progresiones aritméticas arbitrariamente largas que consisten en números primos, prueban que cada conjunto recurrentemente enumerable es la Diofantina exponencial. También prueban como corolario que J.R. implica que cada conjunto repetidamente enumerable es Diophantine, que a su vez implica que el décimo problema de Hilbert es insolvable.
1960	Robinson simplifica la prueba del resultado condicional de los conjuntos de Diofantina exponenciales y lo hace independiente de la conjetura sobre primos y por lo tanto un teorema formal. Esto hace que la hipótesis J.R. sea una condición suficiente para la insolvabilidad del décimo problema de Hilbert. Sin embargo, muchas dudas de que J.R. es verdad.
1961-1969	Durante este período, Davis y Putnam encuentran varias proposiciones que implican J.R., y Robinson, habiendo demostrado previamente que J.R. implica que el conjunto de primos es un conjunto de Diofantina, prueba que esto es un si y sólo si condición. Yuri Matiyasevich publica algunas reducciones del décimo problema de Hilbert.
1970	Partiendo de la obra recientemente publicada de Nikolai Vorob'ev sobre números Fibonacci, Matiyasevich demuestra que el conjunto ${displaystyle P={(a,b) WordPressa confianza0,b=F_{2a}}$ Donde ${displaystyle F_{n}$ es el nT El número de Fibonacci es Diofantina y presenta un crecimiento exponencial. Esto demuestra la hipótesis de J.R., que para entonces había sido una pregunta abierta durante 20 años. Combinando J.R. con el teorema que cada conjunto recurrentemente enumerable es la Diofantina exponencial, demuestra que los conjuntos recurrentemente enumerables son Diofantina. Esto hace que el décimo problema de Hilbert sea insolvable.

Aplicaciones

El teorema de Matiyasevich/MRDP relaciona dos nociones, una de la teoría de la computabilidad y la otra de la teoría de los números, y tiene algunas consecuencias sorprendentes. Quizás lo más sorprendente es la existencia de una ecuación diofántica universal:

Existe un polinomio ${displaystyle p(a,n,x_{1},ldotsx_{k}}$ tal que, dada cualquier conjunto de Diofantina ${displaystyle S.$ hay un número ${displaystyle No.$ tales que

${displaystyle S={,amid exists x_{1},ldotsx_{k}[p(a,n_{0},x_{1},ldotsx_{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 que para cualquier juego de Diofantina ${displaystyle S.$ de enteros positivos, hay un polinomio

${displaystyle q(x_{0},x_{1},ldotsx_{n}}$

tales 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},ldotsx_{n}$

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

${displaystyle p(a,y_{1},ldotsy_{n}=0}$

proporciona una definición de Diofantina ${displaystyle S.$, entonces basta establecer

${displaystyle q(x_{0},x_{1},ldotsx_{n}=x_{0}[1-p(x_{0},x_{1},ldotsx_{n}}{2}].}}$

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 solo puede tomar valores primos). Lo mismo se aplica a 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ógicas se refieren como ${displaystyle Pi _{1} {0}}$ proposiciones, a veces también llamadas proposiciones de Tipo Goldbach. Estos son como la conjetura de Goldbach, al afirmar que todos los números naturales poseen una determinada propiedad que es algorítmicamente verificable para cada número particular. El teorema Matiyasevich/MRDP implica que cada propuesta de este tipo es equivalente a una afirmación que afirma que alguna ecuación Diofantina en particular no tiene soluciones en números naturales. Una serie de problemas importantes y celebrados son de esta forma: en particular, el último teorema de Fermat, la hipótesis de Riemann, y el teorema de cuatro colores. Además, la afirmación de que determinados sistemas formales como Peano arithmetic o ZFC son consistentes puede expresarse como ${displaystyle Pi _{1} {0}}$ oraciones. La idea es seguir a Kurt Gödel en pruebas de codificación por números naturales de tal manera que la propiedad de ser el número que representa una prueba es algorítmicamente verificable.

${displaystyle Pi _{1} {0}}$ las oraciones tienen la propiedad especial que si son falsas, ese hecho será provable en cualquiera de los sistemas formales habituales. Esto se debe a que la falsedad equivale a la existencia de un contra-ejemplo que puede ser verificado por aritmética simple. Así que si ${displaystyle Pi _{1} {0}}$ La frase es tal que ni ella ni su negación es provable en uno de estos sistemas, esa frase debe ser verdadera.

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

Vamos

${displaystyle p(a,x_{1},ldotsx_{k}=0}$

proporcionar una definición de Diophantine de un conjunto no computarable. Vamos ${displaystyle A}$ ser un algoritmo que produce una secuencia de números naturales ${displaystyle n}$ tal que la ecuación correspondiente

${displaystyle p(n,x_{1},ldotsx_{k}=0}$

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

${displaystyle p(n_{0},x_{1},ldotsx_{k}=0}$

no tiene soluciones en números naturales.

Para ver que el teorema es verdad, basta notar que si no hubiera tal número ${displaystyle No.$, uno podría probar algoritmos de la membresía de un número ${displaystyle n}$ en este conjunto no compatible ejecutando simultáneamente el algoritmo ${displaystyle A}$ para ver si ${displaystyle n}$ es la salida mientras que también comprobar todo lo posible ${displaystyle k}$-tuples de números naturales buscando una solución de la ecuación

${displaystyle p(n,x_{1},ldotsx_{k}=0}$

y podemos asociar un algoritmo ${displaystyle A}$ con cualquiera de los sistemas formales habituales como Peano arithmetic o ZFC, permitiéndole generar sistemáticamente consecuencias de los axiomas y luego producir un número ${displaystyle n}$ cuando una frase del formulario

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

se genera. Entonces el teorema nos dice que o bien se prueba un enunciado falso de esta forma o bien queda sin demostrar uno verdadero en el sistema en cuestión.

Otros resultados

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 equivale a una de grado 4 o menor. Su truco consistía en introducir nuevas incógnitas mediante ecuaciones igualándolas 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 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 cada conjunto diofántico tiene una dimensión no superior a 13. Más tarde, Matiyasevich perfeccionó sus métodos para demostrar que basta con 9 incógnitas. Aunque bien puede ser que este resultado no sea el mejor posible, no ha habido más avances. Entonces, en particular, no existe un algoritmo para probar ecuaciones diofánticas con 9 o menos incógnitas para la resolución en números naturales. Para el caso de soluciones enteras racionales (como Hilbert lo planteó 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 con el número de soluciones de una ecuación de Diofantina. El décimo problema de Hilbert pregunta si ese número es 0 o no. Vamos ${displaystyle A={0,1,2,3,ldotsaleph ¿Qué?$ y dejar ${displaystyle C}$ ser un subconjunto no vacío adecuado ${displaystyle A}$. Davis demostró que no hay algoritmo para probar una ecuación Diofantina dada para determinar si el número de sus soluciones es miembro del conjunto ${displaystyle C}$. Por lo tanto no hay algoritmo para determinar si el número de soluciones de una ecuación Diofantina es finito, extraño, un cuadrado perfecto, un primo, etc.

La demostración del teorema MRDP se ha formalizado en Coq.

Extensiones del décimo problema de Hilbert

Alexandra Shlapentokh (middle) en 2003

Aunque Hilbert planteó el problema para los números enteros racionales, también se puede preguntar para muchos anillos (en particular, para cualquier anillo cuyo número de elementos sea numerable). 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 cuerpos numéricos algebraicos. Basándose en el trabajo anterior de Jan Denef y Leonard Lipschitz y utilizando la teoría del campo de clases, Harold N. Shapiro y Alexandra Shlapentokh pudieron demostrar:

El décimo problema de Hilbert es insolvable para el anillo de enteros de cualquier campo número algebraico cuyo grupo Galois sobre los racionales es abeliano.

Shlapentokh y Thanases Pheidas (independientemente uno del otro) obtuvieron el mismo resultado para campos numéricos algebraicos que admitían exactamente un par de incrustaciones conjugadas complejas.

El problema para el anillo de enteros de campos numéricos algebraicos distintos a los cubiertos por los resultados anteriores permanece abierto. Asimismo, a pesar de mucho interés, el problema de las ecuaciones sobre los racionales permanece abierto. Barry Mazur ha conjeturado que para cualquier variedad sobre los racionales, el cierre topológico sobre los reales del conjunto de soluciones tiene solo un número finito de componentes. 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 que se usa para otros anillos.