En matemáticas , una ecuación diofántica es una ecuación de la forma P ( x 1 , ..., x j , y 1 , ..., y k ) = 0 (generalmente abreviada P ( x , y ) = 0) donde P ( x , y ) es un polinomio con coeficientes enteros , donde x 1 , ..., x j indican parámetros e y 1 , ..., y k indican incógnitas.
Un conjunto diofántico es un subconjunto S de , el conjunto de todas las j -tuplas de números naturales, de modo que para alguna ecuación diofántica P ( x , y ) = 0,
Es decir, un valor de parámetro está en el conjunto diofántico S si y sólo si la ecuación diofántica asociada es satisfacible bajo ese valor de parámetro. El uso de números naturales tanto en S como en la cuantificación existencial simplemente refleja las aplicaciones habituales en la teoría de la computabilidad y la teoría de modelos . No importa si los números naturales se refieren al conjunto de números enteros no negativos o enteros positivos ya que las dos definiciones para conjuntos diofánticos son equivalentes. También podemos hablar igualmente de conjuntos diofánticos de números enteros y reemplazar libremente la cuantificación sobre números naturales por la cuantificación sobre los números enteros. [1] También es suficiente suponer que P es un polinomio sobre y multiplicar P por los denominadores apropiados para obtener coeficientes enteros. Sin embargo, si la cuantificación sobre racionales también puede sustituirse por la cuantificación sobre los números enteros es un problema abierto notoriamente difícil. [2]
El teorema MRDP (llamado así por las iniciales de los cuatro principales contribuyentes a su solución) establece que un conjunto de números enteros es diofántico si y solo si es computablemente enumerable . [3] Un conjunto de números enteros S es computablemente enumerable si y solo si hay un algoritmo que, cuando se le da un número entero, se detiene si ese número entero es miembro de S y se ejecuta indefinidamente en caso contrario. Esto significa que el concepto de conjunto diofántico general, aparentemente perteneciente a la teoría de números , puede tomarse más bien en términos lógicos o de teoría de la computabilidad. Sin embargo, esto está lejos de ser obvio y representó la culminación de algunas décadas de trabajo.
La finalización del teorema MRDP por parte de Matiyasevich resolvió el décimo problema de Hilbert . El décimo problema de Hilbert [4] consistía en encontrar un algoritmo general que pudiera decidir si una ecuación diofántica dada tiene una solución entre los números enteros. Si bien el décimo problema de Hilbert no es un enunciado matemático formal como tal, la aceptación casi universal de la identificación (filosófica) de un algoritmo de decisión con un predicado computable total nos permite usar el teorema MRDP para concluir que el décimo problema es irresoluble.
En los siguientes ejemplos, los números naturales se refieren al conjunto de números enteros positivos.
La ecuación
es un ejemplo de ecuación diofántica con un parámetro x y las incógnitas y 1 e y 2 . La ecuación tiene una solución en y 1 e y 2 precisamente cuando x puede expresarse como un producto de dos enteros mayores que 1, en otras palabras x es un número compuesto . Es decir, esta ecuación proporciona una definición diofántica del conjunto
que consiste en los números compuestos.
Otros ejemplos de definiciones diofánticas son los siguientes:
El teorema de Matiyasevich, también llamado teorema Matiyasevich - Robinson - Davis - Putnam o teorema MRDP, dice:
Un conjunto S de números enteros es computablemente enumerable si existe un algoritmo tal que: Para cada entrada entera n , si n es un miembro de S , entonces el algoritmo finalmente se detiene; de lo contrario, se ejecuta indefinidamente. Eso es equivalente a decir que hay un algoritmo que se ejecuta indefinidamente y enumera los miembros de S . Un conjunto S es diofántico precisamente si existe algún polinomio con coeficientes enteros f ( n , x 1 , ..., x k ) tal que un número entero n está en S si y solo si existen algunos números enteros x 1 , ..., x k tales que f ( n , x 1 , ..., x k ) = 0.
Por el contrario, todo conjunto diofántico es computablemente enumerable : considérese una ecuación diofántica f ( n , x 1 , ..., x k ) = 0. Ahora hacemos un algoritmo que simplemente prueba todos los valores posibles para n , x 1 , ..., x k (en, digamos, algún orden simple consistente con el orden creciente de la suma de sus valores absolutos), e imprime n cada vez que f ( n , x 1 , ..., x k ) = 0. Este algoritmo obviamente se ejecutará para siempre y listará exactamente los n para los cuales f ( n , x 1 , ..., x k ) = 0 tiene una solución en x 1 , ..., x k .
Yuri Matiyasevich utilizó un método que involucraba números de Fibonacci , que crecen exponencialmente , para demostrar que las soluciones de ecuaciones diofánticas pueden crecer exponencialmente. Trabajos anteriores de Julia Robinson , Martin Davis y Hilary Putnam (de ahí el nombre de MRDP) habían demostrado que esto es suficiente para demostrar que todo conjunto computablemente enumerable es diofántico.
El décimo problema de Hilbert pide un algoritmo general que determine la resolubilidad de las ecuaciones diofánticas. La conjunción del resultado de Matiyasevich con el hecho de que la mayoría de los lenguajes recursivamente enumerables no son decidibles implica que una solución al décimo problema de Hilbert es imposible.
Trabajos posteriores han demostrado que la cuestión de la solubilidad de una ecuación diofántica es indecidible incluso si la ecuación sólo tiene 9 variables de números naturales (Matiyasevich, 1977) u 11 variables enteras ( Zhi Wei Sun , 1992).
Desde entonces, el teorema de Matiyasevich se ha utilizado para demostrar que muchos problemas de cálculo y ecuaciones diferenciales son irresolubles.
También se puede derivar la siguiente forma más fuerte del primer teorema de incompletitud de Gödel a partir del resultado de Matiyasevich:
Según los teoremas de incompletitud , una teoría axiomática suficientemente consistente y potente es incompleta, lo que significa que la verdad de algunas de sus proposiciones no puede establecerse dentro de su formalismo. La afirmación anterior dice que esta incompletitud debe incluir la resolubilidad de una ecuación diofántica, suponiendo que la teoría en cuestión sea una teoría de números.
