El décimo problema de Hilbert

Enunciado del problema

• 10. Entscheidung der Lösbarkeit einer Diophantischen Gleichung.

• Eine Diophantische Gleichung mit irgend welchen Unbekannten und mit ganzen rationalen Zahlencoefficienten sei vorgelegt: man soll ein Verfahren angeben, nach welchem sich mittelst einer endlichen Anzahl von Operationen entscheiden läßt, ob die Gleichung in ganzen rationalen Zahlen lösbar ist.

Traducción

• 10. Decisión sobre la solubilidad de una ecuación diofantina.

• Dada una ecuación diofantina con cualquier cantidad de incógnitas y con coeficientes enteros racionales, dar un procedimiento a través del cual se pueda determinar con un número finito de operaciones, si dicha ecuación tiene soluciones enteras racionales.

Ecuaciones diofantinas.

• Una ecuación diofantina es de la forma

D(x1, x2, ..., xm)=0

donde D es un polinomio con coeficientes enteros racionales. El nombre se debe a Diofanto, matemático griego de la antigüedad.

Enteros racionales.

• En conjunto de enteros racionales es simplemente Z={…, -2, -1, 0, 1, 2, …}

• Se le llama así para distinguirlo de otros conjuntos de enteros (posteriormente mencionaré a uno de ellos, el de los enteros gaussianos).

Los 23 problemas de Hilbert

• En 1900, durante el congreso internacional de matemáticos en París, David Hilbert presentó una famosa lista de 23 problemas matemáticos. Los consideraba los retos más importantes para los matemáticos del siglo XX.

Problemas de decisión

• Desde los tiempos de Diofanto se han encontrado muchos métodos para resolver algunos tipos particulares de ecuaciones diofantinas.

• Sin embargo, Hilbert pide un sólo procedimiento que permita decidir si una ecuación diofantina tiene o no solución.

Soluciones naturales

• (x+1)3+(y+1)3=(z+1)3 no tiene soluciones naturales, pero tiene una infinidad de soluciones enteras.

• Hilbert pide soluciones enteras para las ecuaciones. También es posible considerar soluciones naturales (N={0, 1, 2, …})

• Se puede mostrar que estos dos problemas de decisión son equivalentes.

• Mientras no se diga otra cosa, a partir de ahora me referiré al décimo problema de Hilbert restringido a soluciones naturales (los coeficientes sí pueden ser negativos).

“Procedimientos”

• Hilbert pide un “procedimiento”; pero, ¿qué quiere decir exactamente esto?

• Uno de los grandes avances fue definir con precisión qué significa, se introdujeron conceptos como máquinas de Turing, funciones recursivas, cálculo λ… pero luego se demostró que todos ellos son equivalentes y se aceptan como definición de “procedimiento” en el sentido del décimo problema de Hilbert (y otros problemas de decisión). A dichos “procedimientos” se les llama algoritmos.

La solución

• En 1970, Yuri Matiyasevich resolvió el problema en forma negativa, esto es, no existe ningún algoritmo que, dada una ecuación diofantina arbitraria, nos diga si dicha ecuación tiene solución o no. En términos técnicos, el décimo problema de Hilbert es indecidible como problema de decisión.

Conjuntos diofantinos

• Consideremos la ecuación diofantina

D(a1, ..., an, x1, ..., xm)=0

en la que separamos a las variables en dos colecciones: los parámetros a1, ..., an; y las incógnitas x1, ..., xm. Se dice que el conjunto de valores de los parámetros para los que esta ecuación tiene solución es un conjunto diofantino.

Ejemplos de conjuntos diofantinos

• El conjunto de todos los cuadrados:a-x2=0

• El conjunto de todos los números compuestos:a-(x+2)(y+2)=0

• El conjunto de los enteros positivos que no son potencias de 2:

a-(2x+3)y=0• El conjunto de los números que no son

cuadrados:(a-z2-x-1)2+((z+1)2-a-y-1)2=0

Preguntas interesantes

• ¿Es el conjunto de todos los números primos un conjunto diofantino?

• ¿Es el conjunto de todas las potencias de 2 un conjunto diofantino?

Funciones diofantinas

• Una función es diofantina si, vista como conjunto de pares ordenados, es un conjunto diofantino.

• Es claro que las funciones diofantinas son recursivas.

Funciones de crecimiento exponencial.

• Son funciones del orden de magnitud 2n.

• Después de mucho trabajo, se llegó a la conclusión de que sólo es necesario que exista una función diofantina de crecimiento exponencial.

La sucesión de Fibonacci

• Es la famosa sucesión definida por

F0=0

F1=1

Fn+2=Fn+Fn+1

Claramente se trata de una función de crecimiento exponencial. El último paso histórico en la demostración de Matiyasevich fue demostrar que es una función diofantina.

Consecuencia interesante

• Existe un polinomio en diez variables (y se sabe explícitamente cuál es) cuya imagen es el conjunto de números primos.

Replanteamiento del décimo problema de Hilbert

• Después de resolver en décimo problema de Hilbert en la forma en que fue planteado, Matiyasevich le ha dado una interpretación más amplia, generalizándolo.

• Por ejemplo, Hilbert plantea el problema en términos de soluciones enteras; pero se resuelve en términos de soluciones naturales aprovechando su equivalencia como problemas de decisión. Pero Diofanto buscaba soluciones racionales.

Generalizaciones

• Consideremos a los enteros gaussianos (números complejos cuyas partes real e imaginaria son ambas enteras), Denef demostró que el décimo problema de Hilbert para este conjunto también es indecidible.

• Pero el décimo problema de Hilbert para números racionales está aún sin resolver.

• Se puede considerar el problema en muchos otros conjuntos: enteros p-ádicos, anillos de enteros en campos de números, en campos de funciones, etc.

Número de variables, grado de los polinomios

• El problema de Hilbert restringido a polinomios de grado cuatro es indecidible, restringido a polinomios de grado dos es decidible… ¿qué tal restringido a polinomios de grado tres? ¡Es un problema muy difícil!

• Se conjetura que el décimo problema de Hilbert restringido a dos incógnitas es indecidible.

Aritmetización

• Muchos problemas tienen una equivalencia diofantina, o sea que son equivalentes a que cierto polinomio no tenga soluciones enteras. Por ejemplo

La conjetura de Fermat (ya está resuelta).

La conjetura de Goldbach.

La conjetura de Riemann.

La conjetura de los cuatro colores (resuelta).

Relación con el teorema de Gödel

• En cada sistema deductivo gödeliano, existe una ecuación diofantina formalmente indecidible.

• Vale la pena estudiar en detalle por lo menos una vez estos resultados.