Sesión Álgebra Computacional y Conmutativa

Diciembre 15, 11:00 ~ 11:20

Complejidad bit de la resolución de sistemas polinomiales sobre los racionales

GIMENEZ, Nardo

En esta comunicación discutimos un algoritmo probabilístico \`{a} la Kronecker que resuelve sistemas polinomiales sobre los racionales que definen una intersección completa, cuya complejidad bit es esencialmente cuadrática en el número de Bézout del sistema de entrada y lineal en su tama\~{n}o bit. Más precisamente, sean $F_1, \dots, F_r\in\mathbb{Q}[X_1,\ldots,X_n]$ polinomios de grado a lo sumo $d$ y coeficientes enteros de longitud bit a lo sumo $h$ que forman una sucesión regular reducida. Siguiendo una sugerencia de $[4]$, a fin de controlar la longitud bit de los enteros durante los cálculos intermedios, nuestro algoritmo resuelve el sistema de entrada $F_1=0, \dots, F_r=0$ módulo un primo $p$, para luego obtener la salida por medio de un proceso de levantamiento $p$-ádico. Para esto, determinamos condiciones que implican que un primo $p$ es ``lucky'', es decir, condiciones que aseguran que la variedad (sobre la clausura algebraica del cuerpo finito $\mathbb{F}_p$ de $p$ elementos) que define la reducción del sistema de entrada módulo $p$ satisface ciertas propiedades geométricas y algebraicas fundamentales que satisface la variedad que define el sistema original sobre los números complejos, como por ejemplo, la de poseer la misma dimensión y el mismo grado, y el hecho de que los polinomios $F_1,\ldots,F_r$ módulo $p$ formen una sucesión regular reducida. En tal sentido, demostramos la existencia de un múltiplo entero $\mathfrak{N}$ de todos los primos que no son ``lucky'', cuya longitud bit acotamos superiormente usando las estimaciones de alturas de variedades equidimensionales de $[2]$. A partir de esta cota y resultados conocidos sobre la existencia de primos que no dividen un entero dado obtenemos un algoritmo probabilístico que calcula un primo $p$ ``lucky'' de longitud bit $\mathcal{O}(\log (nd^rh))$ (salvo factores logarítmicos). Combinando el algoritmo de $[1]$ para la resolución de sistemas polinomiales sobre cuerpos finitos con un proceso de levantamiento $p$-ádico como en $[4]$ obtenemos un algoritmo que calcula %toma como entrada un straight--line program de %longitud $L$ que representa los polinomios $F_1, \dots, F_r$ y %entrega como salida una representación ``\`a la Kronecker'' (es decir, una parametrización de una sección lineal cero-dimensional genérica) de la variedad $V(F_1,\ldots,F_r)$ definida por $F_1, \ldots, F_r$. Si $\delta:=\max_{1\le i\le r}\deg V(F_1,\ldots,F_i)$ es el ``grado del sistema'' $F_1=0, \ldots, F_r=0$, el algoritmo realiza $\mathcal{O}\big(n^{\mathcal{O}(1)}L\delta(d\delta+d^rh)\big)$ operaciones bit (salvo factores logarítmicos), donde $L$ es la cantidad de operaciones aritméticas necesarias para evaluar $F_1,\ldots,F_r$. Este resultado mejora significativamente los resultados de $[3]$ y $[5]$ sobre la complejidad bit para esta clase de algoritmos. \begin{thebibliography}{10} \bibitem{CaMa06a} A.~Cafure and G.~Matera, \emph{Fast computation of a rational point of a variety over a finite field}, Math. Comp. \textbf{75} (2006), no.~256, 2049--2085. \bibitem{DaKrSo13} C.~{D'Andrea}, T.~Krick, and M.~Sombra, \emph{Heights of varieties in multiprojective spaces and arithmetic {Nullstellens\"atze}}, Ann. Sci. Éc. Norm. Supér. (4) \textbf{46} (2013), no.~4, 571--649. \bibitem{GiHaHeMoMoPa97} M.~Giusti, K.~H{\"a}gele, J.~Heintz, J.E. Morais, J.L. {Monta\~na}, and L.M. Pardo, \emph{Lower bounds for {Diophantine} approximation}, J. Pure Appl. Algebra \textbf{117,118} (1997), 277--317. %\bibitem{GiHeMoMoPa98} %M.~Giusti, J.~Heintz, J.E. Morais, J.~Morgenstern, and L.M. Pardo, % \emph{Straight--line programs in geometric elimination theory}, J. Pure Appl. % Algebra \textbf{124} (1998), 101--146. \bibitem{GiLeSa01} M.~Giusti, G.~Lecerf, and B.~Salvy, \emph{A {Gr\"obner} free alternative for polynomial system solving}, J. Complexity \textbf{17} (2001), no.~1, 154--211. \bibitem{HaMoPaSo00} K.~H{\"a}gele, J.E. Morais, L.M. Pardo, and M.~Sombra, \emph{On the intrinsic complexity of the arithmetic {Nullstellensatz}}, J. Pure Appl. Algebra \textbf{146} (2000), no.~2, 103--183. \end{thebibliography}

Autores: GIMENEZ, Nardo / Matera, Guillermo.