El DéCimo Problema De Hilbert

1. El décimo problema de Hilbert

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

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

4. Ecuaciones diofantinas.
•Una ecuación diofantina es de la forma
D(x
1
, x
2
, ..., x
m
)=0
donde D es un polinomio con coeficientes
enteros racionales. El nombre se debe a
Diofanto, matemático griego de la
antigüedad.

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

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

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

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

9. “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.

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

11. Conjuntos diofantinos
•Consideremos la ecuación diofantina
D(a
1
, ..., a
n
, x
1
, ..., x
m
)=0
en la que separamos a las variables en dos
colecciones: los parámetros a
1
, ..., a
n
; y
las incógnitas x
1
, ..., x
m
. Se dice que el
conjunto de valores de los parámetros
para los que esta ecuación tiene solución
es un conjunto diofantino.

12. Ejemplos de conjuntos
diofantinos
•El conjunto de todos los cuadrados:
a-x
2
=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-z
2
-x-1)
2
+((z+1)
2
-a-y-1)
2
=0

13. 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?

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

15. Funciones de crecimiento
exponencial.
•Son funciones del orden de magnitud 2
n
.
•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.

16. La sucesión de Fibonacci
•Es la famosa sucesión definida por
F
0
=0
F
1
=1
F
n+2
=F
n
+F
n+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.

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

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

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

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

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

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