Conjunto diofántico

Solución de algunas ecuaciones diofánticas

En matemáticas , una ecuación diofántica es una ecuación de la forma P ( x ₁ , ..., x _j , y ₁ , ..., y _k ) = 0 (generalmente abreviada P ( x , y ) = 0) donde P ( x , y ) es un polinomio con coeficientes enteros , donde x ₁ , ..., x _j indican parámetros e y ₁ , ..., 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, ${\displaystyle \mathbb {N} ^{j}}$

${\displaystyle {\bar {x}}\in S\iff (\exists {\bar {y}}\in \mathbb {N} ^{k})(P({\bar {x}},{\bar {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] ${\displaystyle \mathbb {Q} }$

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.

Ejemplos

En los siguientes ejemplos, los números naturales se refieren al conjunto de números enteros positivos.

La ecuación

${\displaystyle x=(y_{1}+1)(y_{2}+1)}$

es un ejemplo de ecuación diofántica con un parámetro x y las incógnitas y ₁ e y ₂ . La ecuación tiene una solución en y ₁ e y ₂ precisamente cuando x puede expresarse como un producto de dos números 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

{4, 6, 8, 9, 10, 12, 14, 15, 16, 18, ...}

que consiste en los números compuestos.

Otros ejemplos de definiciones diofánticas son los siguientes:

• La ecuación con parámetro x e incógnitas y ₁ , y ₂ solo tiene soluciones en cuando x es suma de dos cuadrados perfectos . El conjunto diofántico de la ecuación es {2, 5, 8, 10, 13, 17, 18, 20, 25, 26, ...}. ${\displaystyle x=y_{1}^{2}+y_{2}^{2}}$ ${\displaystyle \mathbb {N} }$
• La ecuación con parámetro x e incógnitas y ₁ , y ₂ . Se trata de una ecuación de Pell , es decir, solo tiene soluciones en cuando x no es un cuadrado perfecto. El conjunto diofántico es {2, 3, 5, 6, 7, 8, 10, 11, 12, 13, ...}. ${\displaystyle y_{1}^{2}-xy_{2}^{2}=1}$ ${\displaystyle \mathbb {N} }$
• La ecuación es una ecuación diofántica con dos parámetros x ₁ , x ₂ y una incógnita y , que define el conjunto de pares ( x ₁ , x ₂ ) tales que x ₁ < x ₂ . ${\displaystyle x_{1}+y=x_{2}}$

Teorema de Matiyasevich

El teorema de Matiyasevich, también llamado teorema Matiyasevich - Robinson - Davis - Putnam o teorema MRDP, dice:

Todo conjunto computablemente enumerable es diofántico, y viceversa.

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 eventualmente 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 ₁ , ..., x _k ) tal que un número entero n está en S si y solo si existen algunos números enteros x ₁ , ..., x _k tales que f ( n , x ₁ , ..., x _k ) = 0.

Por el contrario, todo conjunto diofántico es computablemente enumerable : considérese una ecuación diofántica f ( n , x ₁ , ..., x _k ) = 0. Ahora hacemos un algoritmo que simplemente prueba todos los valores posibles para n , x ₁ , ..., 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 ₁ , ..., x _k ) = 0. Este algoritmo obviamente se ejecutará para siempre y listará exactamente los n para los cuales f ( n , x ₁ , ..., x _k ) = 0 tiene una solución en x ₁ , ..., x _k .

Técnica de prueba

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.

Aplicación al décimo problema de Hilbert

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.

Refinamientos

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).

Otras aplicaciones

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:

En correspondencia con cualquier axiomatización consistente dada de la teoría de números, ^[5] se puede construir explícitamente una ecuación diofántica que no tiene soluciones, pero tal que este hecho no se puede demostrar dentro de la axiomatización dada.

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.

Notas

1. "Conjunto diofántico". Enciclopedia de Matemáticas . Consultado el 11 de marzo de 2022 .
2. Pheidas, Thanases; Zahidi, Karim (2008). "Problemas de decisión en álgebra y análogos del décimo problema de Hilbert". Teoría de modelos con aplicaciones al álgebra y al análisis. Vol. 2. Serie de notas de conferencias de la London Mathematical Society. Vol. 350. Cambridge University Press. págs. 207–235. doi :10.1017/CBO9780511735219.007. ISBN 978-0-521-70908-8.Señor 2436143  .
3. El teorema fue establecido en 1970 por Matiyasevich y por eso también se lo conoce como teorema de Matiyasevich. Sin embargo, la prueba dada por Matiyasevich se basó ampliamente en trabajos previos sobre el problema y la comunidad matemática ha pasado a llamar al resultado de equivalencia teorema MRDP o teorema de Matiyasevich–Robinson–Davis–Putnam, un nombre que reconoce a todos los matemáticos que hicieron contribuciones significativas a este teorema.
4. David Hilbert planteó el problema en su célebre lista, de su discurso de 1900 en el Congreso Internacional de Matemáticos .
5. Más precisamente, dada una fórmula que representa el conjunto de números de Gödel de oraciones que axiomatizan recursivamente una teoría consistente que extiende la aritmética de Robinson . ${\displaystyle \Sigma _{1}^{0}}$

Referencias

• Matiyasevich, Yuri V. (1970). Диофантовость перечислимых множеств[Los conjuntos enumerables son diofánticos]. Doklady Akademii Nauk SSSR (en ruso). 191 : 279–282. MR  0258744.Traducción al inglés en Soviet Mathematics 11 (2), págs. 354–357.
• Davis, Martin (1973). "El décimo problema de Hilbert es irresoluble". American Mathematical Monthly . 80 (3): 233–269. doi :10.2307/2318447. ISSN  0002-9890. JSTOR  2318447. Zbl  0277.02008.
• Matiyasevich, Yuri V. (1993). El décimo problema de Hilbert . MIT Press Series in the Foundations of Computing. Prólogo de Martin Davis y Hilary Putnam. Cambridge, MA: MIT Press. ISBN 0-262-13295-8.Zbl 0790.03008  .
• 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  .
• Sun Zhi-Wei (1992). "Reducción de incógnitas en representaciones diofánticas" (PDF) . Science China Mathematics . 35 (3): 257–269. Zbl  0773.11077. Archivado (PDF) desde el original el 7 de julio de 2011.

Enlaces externos

• Artículo sobre el teorema de Matiyasevich en Scholarpedia .