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

NARDO GIMÉNEZ; GUILLERMO MATERA

Buenos Aires

Congreso; Primer Encuentro Conjunto de la Real Sociedad Matemática Española y la Unión Matemática Argentina; 2017

Real Sociedad Matemática Española y Unión Matemática Argentina

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ño bit. Más precisamente, sean F_1,...,F_r en Q[X_1,...,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.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,...,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 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,...,F_r módulo p formen una sucesión regular reducida.En tal sentido, demostramos la existencia de un múltiplo entero N de todos los primos que no son "lucky", cuya longitud bit acotamos superiormente usando estimaciones de alturas de variedades equidimensionales. 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 O(log(nd^rh)) (salvo factores logarítmicos). Combinando un algoritmo para la resolución de sistemas polinomiales sobre cuerpos finitos con un proceso de levantamiento p-ádico obtenemos un algoritmo que calcula 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,...,F_r) definida por F_1,...,F_r. Si delta:= max_i deg V(F_1,...,F_i) es el "grado del sistema" F_1=0,...,F_r=0, el algoritmo realiza O(n^{O(1)}L delta(d delta + d^r h)operaciones bit (salvo factores logarítmicos), donde L es la cantidad de operaciones aritméticas necesarias para evaluar F_1,...,F_r. Este resultado mejora significativamente los resultados previos conocidos sobre la complejidad bit para esta clase de algoritmos.