A Symbolic Homotopy Algorithm for Solving Composable Polynomial Systems

Resumen Técnico: Un Algoritmo de Homotopía Simbólica para Resolver Sistemas Polinómicos Composicionales

Planteamiento del Problema
El artículo aborda el problema de calcular las soluciones regulares aisladas de un sistema de $n$ ecuaciones polinómicas en $n$ variables, $\mathbf{f} = (f_1, \dots, f_n) \subset k[X_1, \dots, X_n]$, sobre un cuerpo $k$ de característica cero. El enfoque se centra específicamente en sistemas polinómicos composicionales, donde cada ecuación $f_i$ puede expresarse como una composición $f_i = h_i(g_1, \dots, g_n)$. Aquí, $\mathbf{g} = (g_1, \dots, g_n)$ representa un mapa polinómico interno y $\mathbf{h} = (h_1, \dots, h_n)$ un mapa polinómico externo.

Resolver directamente $\mathbf{f} = 0$ es generalmente NP-duro, y los algoritmos simbólicos estándar a menudo incurren en una complejidad dependiente del límite de Bézout del sistema compuesto, $\prod \deg(f_i)$. Dado que $\deg(f_i)$ puede ser significativamente mayor que los grados de los mapas constituyentes $\mathbf{h}$ y $\mathbf{g}$ (debido a la composición), resolver el sistema directamente es computacionalmente costoso. El artículo se dirige a escenarios donde la estructura algebraica de $\mathbf{f}$ como $\mathbf{h} \circ \mathbf{g}$ puede explotarse para reducir este costo. Las aplicaciones clave incluyen sistemas donde $\mathbf{f}$ pertenece a un subanillo generado por polinomios algebraicamente independientes, y sistemas de polinomios invariantes bajo grupos de reflexión finitos (por ejemplo, grupos simétricos $S_n$, grupos hiperoctaédricos $B_n$ y grupos excepcionales), donde el anillo invariante es un álgebra polinómica generada por $\mathbf{g}$.

Metodología
El enfoque propuesto descompone el proceso de solución en dos etapas, aprovechando la estructura composicional $\mathbf{f} = \mathbf{h} \circ \mathbf{g}$:

1. Resolución del Sistema Externo: El algoritmo primero resuelve el sistema $\mathbf{h}(\mathbf{Y}) = 0$ en las variables intermedias $\mathbf{Y}$. Esto se logra utilizando un algoritmo de homotopía simbólica probabilístico (Homotopy_Nonsingular).

   • Construye un "sistema inicial" $\mathbf{p}$ compuesto por productos de formas lineales aleatorias, que es fácilmente resoluble.
   • Una homotopía $\mathbf{r}(\mathbf{Y}, T) = (1-T)\mathbf{p}(\mathbf{Y}) + T\mathbf{h}(\mathbf{Y})$ deforma el sistema inicial hacia el sistema objetivo.
   • Un procedimiento global de elevación Newton-Hensel (GLS_Lifting) eleva las soluciones del sistema inicial a lo largo de la curva de homotopía para obtener una parametrización de dimensión cero (específicamente una Representación Univariable Racional o una Resolución Geométrica) de las soluciones regulares de $\mathbf{h} = 0$.
   • Los puntos singulares se eliminan mediante un procedimiento dedicado.

2. Elevación a través del Mapa Interno: Una vez que las soluciones de $\mathbf{h} = 0$ se parametrizan como $\mathbf{Y} = \mathbf{v}(T)$, el problema se reduce a resolver $\mathbf{g}(\mathbf{X}) = \mathbf{v}(T)$.

   • El algoritmo trata esto como un sistema paramétrico en las variables $\mathbf{X}$ y el parámetro $T$.
   • Calcula una resolución geométrica de la fibra en un punto aleatorio $s_0$ y luego aplica un esquema de elevación Newton-Hensel paramétrico (Parametric) para elevar estas soluciones a una parametrización sobre la variable $T$ hasta una precisión requerida.
   • Se utiliza la reconstrucción de funciones racionales para recuperar parametrizaciones polinómicas exactas.

3. Fusión y Finalización: Las parametrizaciones de los sistemas externo e interno se combinan. El sistema se reduce a encontrar la intersección de la curva de homotopía del sistema externo y la curva elevada del sistema interno. Se calcula una resolución geométrica final para las variables combinadas, y los puntos singulares se filtran para obtener las soluciones regulares aisladas del sistema original $\mathbf{f} = 0$.

Contribuciones y Resultados Clave

• Algoritmo: El artículo presenta un algoritmo aleatorizado (Monte Carlo), Solve_h_circ_g, que calcula una resolución geométrica de las soluciones regulares aisladas de sistemas composicionales.
• Límites de Complejidad: El resultado teórico principal es que la complejidad aritmética es suavemente polinómica en el tamaño de la entrada (específicamente las longitudes de los Programas de Línea Recta, $L_\mathbf{h}$ y $L_\mathbf{g}$) y en cantidades relacionadas con los grados de los mapas interno y externo por separado, en lugar de su composición.
  • Sea $C = \prod \deg(h_i)$ (límite de soluciones del sistema externo) y $D = \prod \deg(g_i)$ (límite de soluciones del sistema interno).
  • Sea $E = \prod (\deg(h_i) + 1)$ y $J = \prod (\deg(g_i) + 1)$.
  • La complejidad es $O^\sim(n(L_\mathbf{h} + L_\mathbf{g} + n^2(\gamma + \sigma))(CE + DJ + DC))$, donde $\gamma$ y $\sigma$ son los grados máximos de $\mathbf{h}$ y $\mathbf{g}$ respectivamente.
• Comparación con la Resolución Directa: En contraste, resolver $\mathbf{f} = 0$ directamente dependería típicamente del límite de Bézout $\prod \deg(f_i)$, que puede ser exponencialmente mayor que $C$ o $D$. El método propuesto logra ahorros sustanciales al desacoplar la complejidad de los mapas interno y externo.
• Generalidad: El método maneja sistemas donde $\mathbf{f}$ es invariante bajo grupos de reflexión finitos, ya que sus anillos invariantes son álgebras polinómicas generadas por polinomios algebraicamente independientes.

Significado y Afirmaciones
El artículo afirma que la principal novedad radica en la descomposición estructurada del problema. Si bien la elevación por homotopía y las resoluciones geométricas son herramientas clásicas, su combinación con la estructura composicional para obtener límites de complejidad que dependen por separado de los mapas interno y externo no ha sido explotada previamente.

Los autores declaran que este enfoque demuestra que explotar la estructura algebraica puede reducir sustancialmente el costo de la resolución simbólica de sistemas polinómicos. El artículo no afirma resolver componentes singulares o de dimensión positiva en su algoritmo principal (aunque señala que modificaciones menores pueden manejar puntos singulares aislados). Hace hincapié en que el algoritmo es probabilístico, dependiendo de elecciones aleatorias de conjuntos abiertos de Zariski para garantizar la corrección con alta probabilidad.

El artículo concluye señalando que, aunque la complejidad teórica es favorable, la eficiencia práctica requiere más trabajo de implementación, particularmente en lo referente a los Programas de Línea Recta, y sugiere direcciones futuras como el manejo de componentes de dimensión positiva, el desarrollo de variantes dispersas y la aplicación del marco a la teoría de invariantes, la optimización y la criptografía multivariable.