An AI Proof of 18-Variable Undecidability for Diophantine Equations over $\mathbb Z[i]$

Resumen Técnico: Una prueba de IA de la indecidibilidad de 18 variables para ecuaciones diofánticas sobre $\mathbb{Z}[i]$

Planteamiento del problema
Este artículo aborda el décimo problema de Hilbert sobre el anillo de los enteros de Gauss, $\mathbb{Z}[i]$. El problema consiste en determinar si existe un algoritmo para decidir si una ecuación polinómica arbitraria sobre un dado anillo tiene solución. Si bien la indecidibilidad de este problema sobre los enteros $\mathbb{Z}$ fue establecida por el teorema de Matiyasevich, Davis, Putnam y Robinson, una refinación natural se refiere al número mínimo de incógnitas requeridas para mantener la indecidibilidad. Trabajos previos de Matiyasevich y Sun establecieron que la indecidibilidad se mantiene para ecuaciones con 20 incógnitas sobre $\mathbb{Z}[i]$. Este artículo presenta una prueba que reduce este límite a 18 incógnitas.

Metodología y marco de trabajo
La prueba conserva el marco general establecido por Matiyasevich y Sun, el cual se basa en tres componentes centrales:

1. El Teorema de Variables Fijas de Sun: Utilizando un conjunto $A \subseteq \mathbb{N}$ recursivamente enumerable pero no recursivo y un polinomio $P(Z_0, \dots, Z_{10})$ tal que la pertenencia a $A$ es equivalente a la existencia de soluciones enteras para $P(a, z_1, \dots, z_{10}) = 0$ con $z_{10} \neq 0$.
2. Test Diofántico para Enteros Racionales: Utilizando un test polinómico específico (Lema 3) para determinar si los elementos en $\mathbb{Z}[i]$ son en realidad enteros racionales.
3. Criterio de Racionalidad: Aplicando un criterio (Lema 4) sobre $\mathbb{Q}(i)$ para forzar a las variables a ser enteros racionales basándose en la racionalidad de una suma construida específicamente.

Los autores logran la reducción de 20 a 18 variables introduciendo dos modificaciones específicas a la construcción anterior:

Contribuciones clave y modificaciones técnicas

1. Eliminación de la variable de cancelación de denominadores:
   En la construcción de 20 variables, se introdujo una variable auxiliar para cancelar denominadores al aplicar el criterio de racionalidad. Los autores reemplazan esto con dos condiciones enteras directas impuestas a las variables $Z_1, \dots, Z_{10}$.
   Sea $Y = 2 \prod_{k=1}^{10} (3Z_k + 1)$. En lugar de añadir una variable para cancelar denominadores, la prueba impone las condiciones:
   $$Y^{10} \in \mathbb{Z} \quad \text{y} \quad Y^{11} + \sum_{k=1}^{10} Z_k Y^{10-k} \in \mathbb{Z}.$$
   Dado que $Y \neq 0$, estas condiciones aseguran que la cantidad $Y + \sum Z_k Y^{-k}$ sea un número racional. Por el criterio de racionalidad, esto fuerza a todos los $Z_k$ a ser enteros racionales. Esta modificación ahorra una variable.

2. Absorción de la condición de no nulidad mediante un gadget de una variable:
   La construcción anterior requería dos variables para imponer una condición de no nulidad (específicamente para el producto $Z_{10}V_0V_1$). Los autores introducen un gadget polinómico de una variable $Q(R) = (2R + 1)(3R + 1)$.

• Propiedades: $Q(R)$ nunca se anula en $\mathbb{Z}[i]$. Además, para cada entero no nulo $n$, existe un entero $R$ tal que $n \mid Q(R)$.
• Aplicación: Este gadget se integra en el "lema de combinación de relaciones" (Lema 2). En lugar de una ecuación separada para imponer la no nulidad, la condición se absorbe en la única ecuación $f(C_0, C_1, N, Q(R), M) = 0$. Si $N=0$, la ecuación se reduce a $Q(R)^4 = 0$, lo cual es imposible. Por lo tanto, la ecuación fuerza implícitamente que $N \neq 0$ sin requerir una variable adicional. Esta modificación ahorra una segunda variable.

Desglose de variables
El sistema resultante utiliza exactamente 18 variables:

• $Z_1, \dots, Z_{10}$: Las 10 variables de la entrada de variables fijas de Sun.
• $V_0, X_0, Y_0$ y $V_1, X_1, Y_1$: Dos conjuntos de 3 variables utilizados para los tests de enteros en $U_0 = Y^{10}$ y $U_1 = W$ (donde $W$ se deriva de la suma).
• $M$: La variable de combinación del lema de combinación de relaciones.
• $R$: La única variable del gadget de no nulidad.
  Total: $10 + 3 + 3 + 1 + 1 = 18$.

Resultado principal
El artículo demuestra el Teorema 1: No existe un algoritmo para decidir si una ecuación polinómica arbitraria $F(X_1, \dots, X_{18}) = 0$ con coeficientes en $\mathbb{Z}$ tiene solución en $\mathbb{Z}[i]^{18}$.

La prueba demuestra que la pertenencia al conjunto no recursivo $A$ puede representarse mediante una única ecuación polinómica sobre $\mathbb{Z}[i]$ en 18 incógnitas. Según el Lema 1, el sistema finito de ecuaciones derivado de la construcción puede combinarse en una sola ecuación polinómica sin introducir nuevas variables, preservando los coeficientes enteros.

Significado y pretensiones
Los autores afirman que este resultado mejora el teorema de 20 incógnitas de Matiyasevich y Sun al reducir el conteo de variables en dos. El artículo señala explícitamente que no pretende la optimalidad absoluta; reducir el conteo aún más (por ejemplo, a 17) requeriría mejoras adicionales, tales como un test de enteros más pequeño, un testigo compartido para las condiciones enteras, una entrada de variables fijas más fuerte o un mecanismo de combinación diferente. El trabajo sirve como un refinamiento técnico dentro del marco establecido de la indecidibilidad diofántica sobre los enteros de Gauss.