Un problema de Eliminación Geométrica en sistemas de

Pham–Brieskorn

Agustín Bompadre Febrero de 2000

Agustín Bompadre Departamento de Matemáticas, Facultad de Ciencias Exactas y Naturales, Universidad de Buenos Aires, Pabellón 1, Ciudad Universitaria, Buenos Aires, Argentina.

Título Original: “Un problema de Eliminación Geométrica en sistemas de Pham–Brieskorn” Tesis de Licenciatura en Matemáticas. Universidad de Buenos Aires. Febrero de 2000.

Director de Tesis: Joos U. Heintz.

Co–director de Tesis: Guillermo Matera.

Contenidos

Resumen 4

1 Introducción 5 1.1 Definiciones y notación . . . . . . . . . . . . . . . . . . . . . . . . . . 5 1.2 Comentario breve . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 1.3 Establecimiento del resultado principal . . . . . . . . . . . . . . . . . 6

2 Preliminares 9 2.1 Modelo computacional . . . . . . . . . . . . . . . . . . . . . . . . . . 9 2.2 Definiciones y resultados geométricos . . . . . . . . . . . . . . . . . . 17 2.3 Bases de Gröbner . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 2.4 Teoría de Eliminación . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 2.5 Series de Puiseux . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21

3 Un algoritmo para el cálculo de un polinomio minimal 22

4 Operador de Newton sin divisiones 34

5 Las cuentas y su complejidad 45 5.1 Solución geométrica de V′ . . . . . . . . . . . . . . . . . . . . . . . . 45 5.2 El resultado principal . . . . . . . . . . . . . . . . . . . . . . . . . . . 53

Bibliografía 63

Resumen

En [GHM^{+}98], [GHH^{+}97], [HKP^{+}98] y [Mor97] se desarrollan algoritmos que resuelven el siguiente problema: dados como input n polinomios en n variables con coeficientes en Q que definen una variedad algebraica cero–dimensional en C^{n}, dar como output una descripción adecuada (la solución geométrica) de esta variedad. En estos algoritmos es necesario poder resolver el problema de hallar la ecuación minimal que verifica un polinomio dado H en el anillo de coordenadas definido por una variedad m–dimensional V incluída en un espacio n–dimensional. Para ello, se trabaja con un elemento de Q^{n−m}, llamado punto de levantamiento. El punto de levantamiento es un punto no ramificado; esta restricción se traduce en que un cierto polinomio no se anule en este punto y esto implica que un elemento genérico de Q^{n−m} es un punto de levantamiento. En [HKP^{+}98] se refinan las cotas de complejidad, pasando a depender de la elección del punto de levantamiento. Más preciso, se mejora la complejidad para puntos de levantamiento “especiales”. Hay que tener en cuenta que trabajar con un punto genérico implica una complejidad del peor caso y por esta razón es interesante poder debilitar las restricciones que pesan sobre el punto de levantamiento. En esta tesis se eliminan estas restricciones para variedades 1–dimensionales definidas por un sistema de Pham–Brieskorn. Un resultado de este tipo para curvas algebraicas no es restrictivo según el algoritmo desarrollado en [HMW99].

1 Introducción

1.1 Definiciones y notación

En lo que sigue, notaremos Qal cuerpo de los números racionales, Cal de los números complejos. Más adelante necesitaremos más generalidad, por lo que notaremos k a un cuerpo de característica cero. IA^{n} denotará al espacio n–dimensional afín C^{n} provisto de la topología Zariski. Sean ε, X_{1}, …, X_{n}, T indeterminadas sobre Q. Sean f_{1}, …, f_{s} polinomios en Q[ε, X_{1}, …, X_{n}], sea (f_{1}, …, f_{s}) el ideal que generan en Q[ε, X_{1}, …, X_{n}] y sea V := V (f_{1}, …, f_{s}) ⊆ IA^{n+1} la variedad algebraica afín definida por (f_{1}, …, f_{s}). El anillo de coordenadas de V es Q[V]. log() nota a la función logaritmo en base 2. Dado f un polinomio, deg(f) denota el grado total de f. Finalmente, ZZ y IN denotan al anillo de los números enteros y al conjunto de los enteros positivos respectivamente. En esta tesis seguimos la terminología y notaciones estándar del álgebra conmutativa y de la geometría algebraica tal como se encuentran en libros como [AM69], [Eis95] (álgebra conmutativa), [Wal78] y [Sha84] (geometría algebraica).

1.2 Comentario breve

En esta tesis estudiamos una variante del problema de Eliminación en Geometría Algebraica que llamamos el Problema de Proyección (ver [HKP^{+}98]). El Problema de Proyección es el siguiente:

Sea V ⊆ IA^{p} una variedad algebraica equidimensional de dimensión m = dim V definida por un sistema de p − m ecuaciones polinomiales sobre Q. Sea π : V → IA^{m} el morfismo inducido por la proyección en las primeras coordenadas pensando a V ⊂ IA^{p} = IA^{m} ×IA^{p−m}, y supongamos que π es un epimorfismo finito de variedades. Sea h ∈ Q[V] un elemento en el anillo de coordenadas de V dado por un polinomio p–variado H sobre Q. Consideramos al morfismo π̃ : V → IA^{m+1} definido por la regla π̃(x) := (π(x), h(x)) para x en V. Por construcción π̃ resulta un morfismo finito, y dado que IA^{m} es normal , se sigue que la imagen de π̃ es una subvariedad equidimensional de codimensión 1 de IA^{m+1}, i.e. una hipersuperficie. Supongamos además que es conocido un punto t ∈ IA^{m} tal que su fibra por π, o sea π^{−1}(t), es no ramificada, y que de hecho π es genéricamente playo y genéricamente no ramificado. Sean T_{1}, …, T_{m}, Y indeterminadas sobre Q. Entonces existe una única ecuación minimal m_{H} ∈ Q[T_{1}, …, T_{m}][Y] que define, la imagen de π̃. Llamamos problema de proyección al de, dados polinomios con coeficientes en Q que definen a la variedad algebraica V, la función regular h, y una descripción de la variedad π^{−1}(t), encontrar un polinomio (m + 1)–variado sobre Q que represente a la ecuación de dependencia entera minimal que satisface la función regular h en la extensión Q[T_{1}, …, T_{m}] → Q[V].

Este es un problema fundamental para los procedimientos de eliminación geométrica y fue considerado por varios autores (ver por ejemplo [GH93], [KP96], [GHMP95], [GHM^{+}98], [GHH^{+}97], [Mor97]). Más precisamente, se utilizan algoritmos que resuelven instancias particulares de este problema como pasos intermedios en el problema de hallar una solución geométrica de una variedad cero–dimensional (una definición de solución geométrica está establecida en 11). En [HMW99] y [GLS99] se plantean variantes para resolver este último problema donde es necesario la proyección de formas lineales en variedades 1–dimensionales. En esta tesis estudiamos el problema de proyección en una curva definida por un sistema de Pham– Brieskorn (ver Subsección siguiente). Es una variante del problema de proyección pues no trabajamos con un punto de levantamiento.

Una tarea paralela al desarrollo de un algoritmo es estudiar su complejidad en espacio y tiempo. Para ello, se definen medidas del espacio y tiempo utilizado y se obtienen cotas en función del “tamaño” del input. La razón es clara, dada una instancia particular de un problema nos interesa saber de antemano si se puede resolver con los recursos que disponemos. Las medidas de espacio y tiempo se definen en la Subsección 2.1.

Un aspecto al que hay que prestar atención es al de las estructuras de datos utilizadas para representar polinomios multivariados. Típicamente, los polinomios se representan por su escritura densa. Sin embargo, un ejemplo debido a D. Lazard, T. Mora, W. Masser y P. Philippon (ver [Bor93]) muestra que un comportamiento super–exponencial en tiempo es inevitable utilizando esta representación.

Una alternativa es codificar los polinomios por circuitos aritméticos y sus esquemas de evaluación asociados, los straight–line programs. Un ejemplo de straight–line program es la conocida regla de Horner. La filosofía detrás de esta representación es la de recordar que los polinomios son funciones. El input del algoritmo es dado entonces por straight–line programs y los polinomios intermedios y el polinomio que será el output también estarán codificados por straight–line programs. En esta tesis utilizaremos esta codificación; las definiciones de circuito aritmético y straight–line program se encuentran en la Subsección 2.1.

1.3 Establecimiento del resultado principal

Sean G_{1}, …, G_{n} polinomios en Q[X_{1}, …, X_{n}], sea d en IN tal que d > deg(G_{i}) para 1 ≤ i ≤ n. Consideramos el sistema de Pham–Brieskorn en Q[ε, X_{1}, …, X_{n}]:

{ F_{1}(ε, X_{1}, …, X_{n}) := X_{1}^{d} − εG_{1}(X_{1}, …, X_{n}) ; ⋮ ; F_{n}(ε, X_{1}, …, X_{n}) := X_{n}^{d} − εG_{n}(X_{1}, …, X_{n})  (1)

Supongamos que para cada 1 ≤ i ≤ n, α_{i} := G_{i}(0, …, 0) es no nulo. Sea I el ideal generado por F_{1}, …, F_{n} en Q[ε, X_{1}, …, X_{n}], sea B el ágebra Q[ε, X_{1}, …, X_{n}]/I y sea V la variedad algebraica definida por I:

V := {F_{1} = 0, …, F_{n} = 0} := {(τ, ξ) ∈ IA^{1} × IA^{n}; F_{1}(τ, ξ) = … = F_{n}(τ, ξ) = 0}.

Sea V′ ⊆ IA^{n} la variedad algebraica cero–dimensional definida por los ceros comunes de X_{1}^{d} − α_{1}, …, X_{n}^{d} − α_{n}. Sea π : V ⟶ IA^{1} el morfismo de variedades algebraicas inducido por la proyección canónica de IA^{1} × IA^{n} en IA^{1}. Este morfismo resulta finito, en particular implica que el morfismo de anillos

Q[ε] ⟶ B

es entero, es decir que para todo polinomio H en Q[ε, X_{1}, …, X_{n}] existe un polinomio q_{H} en Q[ε][T], mónico en T, tal que q_{H}(H) = 0 en B. La indeterminada ε juega entonces el rol de variable libre, mientras que las indeterminadas X_{1}, …, X_{n} dependen de ε. La variedad V definida por los polinomios F_{1}, …, F_{n} en C^{n+1} resulta una curva, y para todo número complejo z existen a lo sumo d^{n} elementos de C^{n}, que numeraremos ξ(z)_{1}, …, ξ(z)_{K_{z}}, tal que los puntos (z, ξ(z)_{1}), …, (z, ξ(z)_{K_{z}}) pertenecen a la variedad V, esto se debe a que el grado geométrico de V es d^{n} como probamos en 26. Dado un complejo z, el cardinal del conjunto π^{−1}(z) = {(z, ξ) ∈ IA^{n+1} : (z, ξ) ∈ V } es menor o igual que d^{n}, y la igualdad vale para todo complejo salvo un número finito de ellos. Un complejo z tal que #π^{−1}(z) = d^{n} es llamado un punto de levantamiento y el conjunto π^{−1}(z) es llamado la fibra de levantamiento de z. Se observa que el origen 0 ∈ IA no es un punto de levantamiento pues su fibra π^{−1}(0) está compuesta por un único punto, el vector (0, 0, …, 0) ∈ IA^{n+1}. Dada π^{−1}(z) una fibra de levantamiento con z ∈ Q, se denomina una solución geométrica de π^{−1}(z) al conjunto formado por una forma lineal U ∈ Q[X_{1}, …, X_{n}], y polinomios q, v_{1}, …, v_{n} ∈ Q[T] tal que se tiene el isomorfismo de álgebras inducido por la forma U

Q[π^{−1}(z)] ≃ Q[T]/(q(T)) ≃ Q[X_{1}, …, X_{n}]/(q(U), X_{1} − v_{1}(U), …, X_{n} − v_{n}(U)).

Dado un polinomio H en Q[ε, X_{1}, …, X_{n}], se quiere un algoritmo que encuentre el polinomio mónico en T, de grado mínimo en T (de hecho, de grado total mínimo), m_{H} tal que m_{H}(H) ∈ I. En [GHM^{+}98], [GHH^{+}97] y [Mor97], en un contexto más general, se obtiene el polinomio buscado a partir de la información que se tiene de una fibra de levantamiento. Para ello, se utiliza una versión simbólica del operador de Newton en varias variables, que obtiene las series formales que se anulan en V, de las variables libres, respecto de las variables dependientes. La información necesaria es una descripción de una solución geométrica de la fibra de levantamiento. El algoritmo opera sobre la matriz compañera de q, siendo esta matriz en nuestro contexto de tamaño d^{n} × d^{n}. Por último, en ([HMW99, Theorem 11] y [Wai99]) se refinan las cotas de complejidad en espacio y tiempo de los dos trabajos anteriormente citados.

Un punto de levantamiento z de V es un punto no ramificado: esto significa que el ideal especializado (F_{1}(z, X_{1}, …, X_{n}), …, F_{n}(z, X_{1}, …, X_{n})) es radical en Q[X_{1}, …, X_{n}]. Esto implica que la fibra π^{−1}(z) sólo contiene puntos lisos. Esto es equivalente a pedir que la matriz jacobiana (\frac{∂F_{i}}{∂X_{j}})_{1≤i,j≤n}, evaluada en cualquier punto de la fibra π^{−1}(z), sea inversible. En esta tesis se busca eliminar esta restricción: el algoritmo desarrollado obtiene el polinomio buscado m_{H} a partir de la fibra correspondiente al origen, que no es un punto de levantamiento. Para ello, se calculan los primeros términos de las series de Puiseux (una generalización de las series formales) de las variables dependientes X_{1}, …, X_{n} respecto de la variable libre ε. A partir de esta información y mediante una transformación del sistema de polinomios F_{1}, …, F_{n} se está en condiciones de aplicar el operador de Newton. El rol que juega la fibra de levantamiento en los algoritmos citados es jugado ahora por la variedad cero–dimensional V′ donde V′ son los ceros comunes de los polinomios X_{1}^{d} − α_{1}, …, X_{n}^{d} − α_{n}. Recordamos que G_{i} ∈ Q[X_{1}, …, X_{n}] son los polinomios que definen el sistema de Pham–Brieskorn y α_{i} = G_{i}(0, …, 0) ≠ 0 para todo 1 ≤ i ≤ n.

Una idea desarrollada en ([HKP^{+}98], ver también [Wai99]) es la siguiente: supongamos que el polinomio q de la solución geométrica de la fibra de levantamiento se factoriza en s factores no constantes en Q[T], q = q_{1} … q_{s}. En lugar de trabajar con la matriz compañera de q, se trabaja con una matriz semejante, la matriz por bloques formada por las matrices compañeras de q_{1}, …, q_{s}. Esto produce una mejora en la complejidad en espacio y en tiempo del algoritmo.

Sea (U, q, v_{1}, …, v_{n}) una solución geométrica correspondiente a la variedad V′, supongamos que q se factoriza en s factores no constantes en Q[T], q = q_{1} … q_{s}, q_{i} ∈ Q[T] y sean D_{i} = deg(q_{i}). Sin pérdida de generalidad suponemos D_{1} ≤ D_{2} ≤ … ≤ D_{s}. Sea β un straight–line program (sin divisiones esenciales) que computa en espacio S y tiempo T a los polinomios F_{1}, …, F_{n} del sistema de Pham–Brieskorn (1), a un polinomio H ∈ Q[ε, X_{1}, …, X_{n}] y a los polinomios U, q_{1}, …, q_{s}, v_{1}, …, v_{n}. El algoritmo desarrollado en esta tesis (ver Teorema 45) es un straight–line program (sin divisiones esenciales) que computa al polinomio minimal m_{H} con complejidad asintótica en espacio lineal respecto de S, D_{1}^{2} + … + D_{s}^{2} y deg(H)^{2} y en tiempo lineal respecto de T , max(sD_{s}^{3}; s^{2}D_{s}^{2}), deg(H)^{2} y n^{5}. En las cotas de complejidad enunciadas se omiten factores logarítmicos.

2 Preliminares

2.1 Modelo computacional

Consideraremos la representación de polinomios multivariados mediante circuitos aritméticos. Sea Q(ε, X_{1}, …, X_{n}) el cuerpo de las funciones racionales sobre Q en las variables ε, X_{1}, …, X_{n}. Un circuito aritmético β en Q(ε, X_{1}, …, X_{n}) es un grafo orientado acíclico cuyos nodos tienen grado de entrada igual a 0 o 2. Los nodos de grado 0 están etiquetados por elementos de Q ∪ {ε, X_{1}, …, X_{n}} y los nodos de grado 2 (llamados nodos internos) están etiquetados con alguna de las siguientes operaciones aritméticas: adición, substracción, multiplicación o división. Los nodos de grado cero etiquetados con elementos de ε, X_{1}, …, X_{n} son nodos input. Los nodos de grado cero etiquetados con elementos de Q son nodos de parámetros. Finalmente, algunos nodos de β están etiquetados como nodos output. Se denota el grafo de computación de β por Γ(β). A cada nodo ρ le corresponde una función racional Q_{ρ} que es el resultado de los pasos anteriores. Dadas s funciones racionales distintas F_{1}, …, F_{s} ∈ Q[ε, X_{1}, …, X_{n}] y β un circuito aritmético en Q(ε, X_{1}, …, X_{n}) con s nodos output, F_{1}, …, F_{s} son representadas por β si F_{1}, …, F_{s} son las funciones racionales asociadas a los nodos output de β. En adelante trabajaremos con circuitos aritméticos en Q[ε, X_{1}, …, X_{n}] no conteniendo divisiones esenciales (es decir, sólo divisiones por elementos no nulos de Q). Se introduce la noción de pebble game para modelizar la computación en un circuito aritmético. Un pebble game convierte un circuito aritmético dado en un algoritmo secuencial (llamado también straight line program) y se definen medidas de espacio y tiempo asociadas. En el grafo de computación Γ(β) de un circuito aritmético es posible jugar un pebble game sujeto a las siguientes reglas (ver [Bor93]):

P1 se puede ocupar con una piedra cualquier nodo de grado cero.

P2 si los nodos anteriores a un dado nodo ρ se encuentran ocupados, entonces ρ puede ser ocupado con una piedra nueva o moviendo una piedra de un nodo predecesor.

P3 siempre se puede remover una piedra de un nodo ocupado.

Un pebble game finaliza cuando han sido ocupados todos los nodos output. Observamos que un grafo de computación Γ(β) no determina un único pebble game. Asociamos a un dado pebble game las siguientes medidas de complejidad:

C1 una medida del espacio utilizado dada por el máximo número de piedras utilizadas durante el juego.

C2 una medida del tiempo dada por el número de ubicación de piedras durante el juego siguiendo las reglas P1 y P2.

Un pebble game fijo en un grafo de computación Γ(β) define un algoritmo que llamamos un straight line program. Un straight line program en Q(ε, X_{1}, …, X_{n}) que computa funciones racionales F_{1}, …, F_{s} es una secuencia β = (Q_{1}, …, Q_{r}) de elementos en el cuerpo Q(X_{1}, …, X_{n}) con las siguientes propiedades:

• {F_{1}, …, F_{s}} ⊆ {Q_{1}, …, Q_{r}},

• para todo 1 ≤ ρ < r, la función racional Q_{ρ} pertenece a Q ∪ {ε, X_{1}, …, X_{n}} o existen 1 ≤ ρ_{1}, ρ_{2} < ρ y una operación aritmética op_{ρ} en {+, −, ×, ÷} tal que vale Q_{ρ} = Q_{ρ_{1}}op_{ρ}Q_{ρ_{2}}.

En adelante trabajaremos con circuitos aritméticos en Q[ε, X_{1}, …, X_{n}] conteniendo divisiones no esenciales (es decir, sólo divisiones por elementos no nulos de Q).

Algunos resultados útiles:

Lema 1 ([HMW99]) Sea R un anillo de polinomios y sea K su cuerpo de cocientes. Sea Y una indeterminada sobre R, sean q(Y), f(Y) y g(Y) polinomios de R[Y]. Supongamos que q(Y) es separable y mónico respecto de Y y sea D := deg_{Y} q(Y). Supongamos además que q(Y) y g(Y) son coprimos en K[Y] y sea β un straightline program sin divisiones en R[Y] que computa los coeficientes del polinomio q(Y) respecto de la variable Y y evalúa a los polinomios f(Y) y g(Y) respecto de todas las variables (incluída Y) en espacio S y tiempo T . Entonces existe un straight-line program sin divisiones en R[Y], de espacio O(SD) y tiempo O(T D^{2} log D log log D), que computa un elemento α distinto de cero en R y los coeficientes de un polinomio h(Y) de R[Y] de grado deg_{Y} h ≤ D−1 tal que se verifica g(Y)h(Y) ≡ αf(Y) módulo q(Y) en R[Y].

Para encontrar el polinomio buscado haremos nuestras computaciones en R[Y]/(q(Y)), i.e. trabajaremos siempre con los restos módulo q(Y) de los polinomios que aparezcan en cada nodo del straight–line program que encuentra la solución. De esta manera todo polinomio con el que trabajemos tendrá grado (en Y) acotado por D, podrá ser representado por un straight–line program en R que calcule sus coeficientes, y así mantendremos la complejidad del straight–line program output acotada. Esta técnica, que conocemos como aritmética modular, suele ser útil cuando se quiere mantener acotada la complejidad (o la altura) de las entradas que maneja el algoritmo (ver [BS98]). Notamos también, que para sistemas especiales (e.g. si sabemos que deg_{Y} f ≪ D y deg_{Y} g ≪ D) podremos agilizar este procedimiento no haciendo todas las computaciones módulo q(Y), sino sólo las necesarias (ver [BS98]).

Demostración.– Calculemos primero a los restos de dividir a f(Y) y a g(Y) por el polinomio q(Y). Llamamos a estos restos f̃(Y) y g̃(Y) respectivamente. Computacionalmente lo que hacemos es simular al straight–line program β, que calcula a f(Y) y a g(Y), reemplazando cada nodo (que representa un polinomio en R[Y]) por el resto de dividir a este polinomio por q(Y), y guardándolo como un vector de R^{D}.

De esta manera, los nodos suma son reemplazados de manera obvia: la salida módulo q(Y). Hace falta tener algo más de cuidado con las multiplicaciones. Sean dados dos polinomios e_{1}(Y), e_{2}(Y) ya reducidos módulo q(Y), y supongamos que β calcula su producto (e_{1} · e_{2})(Y). Utilizamos primero un algoritmo basado en FFT para la multiplicación (transformadas rápidas de Fourier, ver [BP94]), y luego el algoritmo de Sieveking–Kung basado en inversión de series de potencias formales (ver [Sie72],

[BM72] o [BP94]) para la reducción módulo q(Y) obteniendo así un vector en R^{D} que representa a los coeficientes en la variable principal Y de un polinomio en R[Y] congruente a (e_{1}·e_{2})(Y) módulo q(Y). Este nuevo straight–line program con el nodo de multiplicación reemplazado usa espacio O(D) y tiempo O(D^{2} log D log log D).

Al recorrer todo β haciendo los reemplazos recién expuestos obtenemos un nuevo circuito aritmético sin divisiones que calcula a los coeficentes de f̃(Y) y g̃(Y) en espacio a los más O(SD) y tiempo O(T D^{2} log D log log D).

Como segundo paso calculamos un elemento α de R, y un polinomio h̃(Y) en R[Y] tales que g̃h̃ ≡ α módulo q(Y) usando un algoritmo para matrices de tipo Hankel (ver [Sen90] y [SL92]). Obtenemos así un circuito aritmético sin divisiones en R que calcula al elemento α y los coeficientes del polinomio h̃(Y) en espacio adicional O(D) y tiempo O(D^{2} log D log log D).

El elemento α de R de la tesis es aquel ya calculado. Para obtener a h(Y) calculamos al polinomio (f ·h̃)(Y) que resulta de multiplicar a los polinomios f(Y) y h̃(Y) entre sí por el método de aritmética modular desarrollado a principios de la demostración. Finalmente notamos que esta computación no altera la complejidad asintótica ya calculada terminando entonces la demostración del Lema.

Lema 2 ([HMW99]) Con las notaciones e hipótesis del Lema (1), sea M la matriz compañera del polinomio q(Y). Entonces g(M) es una matriz de R^{D×D}, inversible en el anillo K^{D×D}. Sea N la matriz N := f(M)g(M)^{−1}. Entonces existe un straight-line program en R que computa en espacio O(SD) y tiempo O((T + D)D log D log log D) los α^{D}-múltiplos de los coeficientes del polinomio característico χ_{N}(Y) de N. En particular, estos α^{D}-múltiplos de los coeficientes de χ_{N}(Y) son elementos de R.

Supongamos calculado el polinomio característico χ_{αN}(Y) de la matriz N. Entonces notamos que haciendo la especialización αY en Y obtenemos al polinomio

χ_{αN}(αY) = α^{D}χ_{N}(Y) ,

terminando el algoritmo.

Para encontrar al polinomio característico χ_{αN}(Y) de la matriz αN calcularemos primero las trazas tr(αN), …, tr((αN)^{D}) de las primeras D potencias de la matriz αN y después usamos las relaciones de Newton para obtener los coeficientes de χ_{αN}(Y), su polinomio característico.

Consideramos en K̄[Z] la descomposición del polinomio q(Z) en factores lineales, digamos para establecer la notación

q(Z) = ∏_{ℓ=1}^{D}(Z − z_{ℓ}) ,

donde z_{1}, …, z_{D} son elementos de C. Consideremos además a la derivada formal q′(Z) de q(Z) en la variable Z. Con la notación recién establecida se tiene la identidad

q′(Z) = ∑_{ℓ=1}^{D} ∏_{ℓ≠k}(Z − z_{k}) .

Y notamos que deg_{Z} q′ = D − 1.

A partir de estas dos identidades deduciremos congruencias que nos permitirán calcular las trazas de las primeras D potencias de αN efectivamente. Sea 1 ≤ ℓ ≤ D fijo, luego se verifica la congruencia

Z ∏_{k≠ℓ}(Z − z_{k}) ≡ z_{ℓ} ∏_{k≠ℓ}(Z − z_{k}) módulo q(Z)

en C[Z]. Sumando ahora esta congruencia para cada 1 ≤ ℓ ≤ D se tiene que

Z ∑_{ℓ=1}^{D} ∏_{k≠ℓ}(Z − z_{k}) ≡ ∑_{ℓ=1}^{D} z_{ℓ} ∏_{k≠ℓ}(Z − z_{k}) módulo q(Z) .

Notamos que las dos identidades anteriores son también válidas en \overline{K}[Z]. Sea ahora p(Z) un polinomio arbitrario en R[Z]. Entonces se sigue la congruencia

\begin{matrix}p(Z)q′(Z) = & p(Z) ∑_{ℓ=1}^{D} ∏_{k≠ℓ}(Z − z_{k}) \\ ≡ & ∑_{ℓ=1}^{D} p(z_{ℓ}) ∏_{k≠ℓ}(Z − z_{k}) módulo q(Z) \end{matrix}  (2)

en R[Y]. De (2) deducimos que la traza tr(p(M)) = ∑_{ℓ=1}^{D} p(z_{ℓ}) de la matriz p(M) no es más que el coeficiente principal del resto de dividir a (p · q′)(Z) por q(Z).

Para obtener la traza tr((αN)^{ℓ}) = tr(h(M)^{ℓ}) para 1 ≤ ℓ ≤ D observamos que esta es exactamente el coeficiente (D − 1)–ésimo del polinomio obtenido al dividir a (q′ · h^{ℓ})(Z) por el polinomio q(Z).

Enunciemos ahora la forma computacional que generamos a partir de las deducciones en los párrafos precedentes de esta demostración, y los correspondientes cálculos de complejidad. Como primer paso utilizamos el Lema 1 para calcular al elemento α de R y al polinomio h(Y) en R[Z] usando el espacio y el tiempo del enunciado. Recordamos que q(Z) es un polinomio de grado deg_{Z} q(Z) = D con coeficientes racionales, luego su derivada q′(Z) puede calcularse sin alterar la complejidad asintótica del procedimiento. Notamos además que el elemento α y los coeficientes de q(Y) y q′(Y) módulo q(Y), que guardaremos durante todo este procedimiento, y los coeficientes de h(Y) que guardamos temporalmente, pueden guardarse en memoria usando espacio O(D).

Calcularemos las distintas trazas recurrentemente. Con la misma táctica usada en la demostración del Lema 1 calculamos al resto de dividir al polinomio (q′·h)(Y) por q(Y). Y guardamos al resultado en la memoria temporalmente, salvo el coeficiente (D − 1)–ésimo que es la traza tr(αN) que guardamos y no será borrado hasta el final del procedimiento.

En el k–ésimo paso, para 1 ≤ k < D calculamos, a partir de los coeficientes de q(Y), q′(Y) módulo q(Y) y (h^{k} · q′)(Y), a los coeficientes de (h^{k+1} · q′)(Y) módulo q(Y) guardandolos temporariamente y despejando de la memoria temporal los coeficientes de (h^{k}·q′)(Y) (recordemos que el (D−1)–ésimo ya fue almacenado como tr((αN)^{k})). De esta manera encontramos a las trazas tr(αN), …, tr((αN)^{D}) usando espacio adicional O(D) y en tiempo O(D^{2} log D log log D).

Finalmente utilizamos las relaciones de Newton para calcular los coeficientes del polinomio característico χ_{αN}(Y) de αN sin aumentar la complejidad asintótica del procedimiento. Y luego multiplicamos estos coeficientes por potencias adecuadas de α obteniendo así a los coeficientes del polinomio α^{D}χ_{αN}(Y) = χ_{αN}(αY), nuevamente sin aumentar la complejidad asintótica del procedimiento. Sumando las complejidades de la subrutina descrita deducimos que existe un straight–line program que calcula a los coeficientes del polinomio α^{D}χ_{N}(Y) en espacio O(SD) y tiempo O(T D log D log log D + D^{2} log D log log D) = O(T D^{2} log D log log D).

Por otro lado, aplicando las reglas de derivación (forward mode) se concluye un resultado del tipo:

Lema 3 Sea R un dominio y sea β un esquema de evaluación en R[X_{1}, …, X_{n}] en espacio S y tiempo T que representa la familia de polinomios {f_{1}, …, f_{s}} ⊂ R[X_{1}, …, X_{n}]. En estas condiciones, existe un esquema de evaluación en R[X_{1}, …, X_{n}] en espacio S+1 y tiempo (2n+1)T con los mismos parámetros de β que evalúa f_{1}, …, f_{s} y todas sus derivadas parciales de primer orden:

\{\frac{∂f_{i}}{∂X_{j}} : 1 ≤ i ≤ s, 1 ≤ j ≤ n\}.

Una técnica importante es la conocida como “Vermeidung von Divisionen” debida a V. Strassen ([Str73]) y permite calcular el cociente de dos polinomios cuando el resultado también es un polinomio. En la proposición es necesario la computación de las componentes homogéneas de un polinomio dado por un esquema de evaluación. Este es el contenido del siguiente Lema:

Lema 4 Sea F (X_{1}, …, X_{m}) un polinomio con coeficientes racionales en las variables X_{1}, …, X_{m} de grado deg F = D que es calculado por un circuito aritmético sin divisiones β en Q[X_{1}, …, X_{m}] en espacio S y en tiempo T . Entonces existe un circuito aritmético sin divisiones que calcula las componentes homogéneas de F (X_{1}, …, X_{m}) en espacio O(SD) y tiempo O(T D log D log log D).

Demostración.– Seguimos la demostración de [Mat97]. Sea Z una nueva indeterminada que consideramos auxiliarmente para la demostración de este Lema. Para encontrar la descomposición de F (X_{1}, …, X_{m}) en componentes homogéneas trabajamos en el Q(X_{1}, …, X_{m})–espacio vectorial Q(X_{1}, …, X_{m})[Z]/(Z^{D+1}). Dado un elemento G ∈ Q[X_{1}, …, X_{m}][Z] denotamos por \overline{G} a la clase de este polinomio en Q(X_{1}, …, X_{m})[Z]/(Z^{D+1}). Notamos que B := {1, Z, …, Z^{D}} es una base del espacio vectorial en la cual las coordenadas del vector que representa a \overline{F (ZT_{1}, …, ZT_{m})} son exactamente las componentes homogéneas de F (X_{1}, …, X_{m}).

Para obtenerlas definimos a η_{F} la transformación Q(X_{1}, …, X_{m})–lineal inducida por la homotecia por la función regular \overline{F (ZT_{1}, , …, ZT_{m})} en Q(X_{1}, …, X_{m})[Z]/(Z^{D+1}) y consideramos a M_{F} la matriz de η_{F} en la base B. Teniendo en cuenta que η_{F} (\overline{1}) = F deducimos, dado que \overline{1} se escribe como (1, 0, …, 0) ∈ Q(X_{1}, …, X_{m})^{(D+1)×(D+1)}, que las componentes homogéneas de F (X_{1}, …, X_{m}) son las entradas que aparecen en la primera columna de la matriz M_{F} = F (MT_{1}, …, MT_{m}).

Para calcular las distintas entradas de la matriz M_{F} introducimos un nuevo nodo de entrada, y reemplazamos en β las entradas Y_{1}, …, Y_{m} por las entradas ZT_{1}, …, ZT_{m} obteniendo un nuevo circuito aritmético. Sea M la matriz que representa la homotecia por \overline{Z}

M = ( \begin{matrix}0 & 0 & … & 0 \\ 1 & 0 & … & 0 \\ & ... & ... & ⋮ \\ 0 & … & 1 & 0 \end{matrix} ) ,

luego reemplazamos al nodo de entrada Z por M obteniendo así un circuito aritmético que calcula a la matriz F (MT_{1}, …, MT_{m}) de Q[X_{1}, …, X_{m}]^{(D+1)×(D+1)}. En definitiva las únicas operaciones que hace el nuevo circuito aritmético son las que resultan de reemplazar cada nodo de β por una operación de matrices de tamaño (D + 1) × (D + 1), que usando técnicas de multiplicación basados en FFT ([BP94]), resultan en los recursos estimados.

Lema 5 ([Str73], [HMW99]) Sea F := {F_{0}, …, F_{m}} un conjunto finito de polinomios de Q[Y_{1}, …, Y_{n}] de grado a lo sumo δ, computados por un straight-line program β en espacio S y tiempo T . Supongamos que F_{0} ≠ 0 y tal que F_{0} divide a F_{i} en Q[Y_{1}, …, Y_{n}] para 1 ≤ i ≤ m. Entonces existe un straight-line program que calcula los polinomios

P_{1} := \frac{F_{1}}{F_{0}} , …, P_{m} := \frac{F_{m}}{F_{0}}

en espacio O(Sδ) y tiempo O((T + log δ)δ log δ log log δ) = O(T δ log^{2} δ log log δ).

Demostración.– Sean g_{i}(Y_{1}, …, Y_{n}) = F_{i}(Y_{1} + t_{1}, …, Y_{n} + t_{n}) para 0 ≤ i ≤ m los polinomios que resultan de trasladar a F_{0}, …, F_{m} en el punto t = (t_{1}, …, t_{n}). Luego, para cada 1 ≤ i ≤ m, el polinomio \frac{F_{i}}{F_{0}} (Y_{1}+t_{1}, …, Y_{n}+t_{n}) puede ser calculado como la

suma de las primeras δ+1 componentes homogéneas del polinomio \frac{g_{i}}{ρ} ∑_{k=0}^{δ} (\frac{ρ − g_{0}}{ρ} )^{k}.

Este último polinomio puede calcularse usando espacio O(S) y tiempo O(T +log δ). Usando el Lema anterior calculamos sus primeras δ + 1 componentes homogéneas con la complejidad enunciada.

Una observación que será útil más adelante es la siguiente:

Observación 6 Bajo las hipótesis y notación de la proposición anterior con n = 1, es decir si F_{0}, …, F_{m} son polinomios de Q[Y_{1}], el straight–line program β anterior calcula la representación densa de los polinomios

P_{1} := \frac{F_{1}}{F_{0}} , …, P_{m} := \frac{F_{m}}{F_{0}} .

Lema 7 ([HMW99]) Sea R un anillo de polinomios y sea K su cuerpo de cocientes. Sea β un straight-line program en R que computa los coeficientes de dos polinomios univariados r(Y) y s(Y) ∈ R[Y] con s(Y) ≠ 0, en espacio S y tiempo T . Sean u(Y), v(Y) dos polinomios coprimos de K[Y] que verifican que \frac{r}{s} = \frac{u}{v}, deg_{Y} u = D y deg_{Y} v < D. Supongamos además que u(Y) es mónico en Y. Entonces existe un straight-line program en R que computa un elemento no nulo γ ∈ R y un γ-múltiplo de los coeficientes de u en espacio O(S + D) y tiempo O(T + D^{2} log D log log D). En particular, los coeficientes de γu pertenecen a R.

Demostración.– Sin pérdida de generalidad podemos asumir r(Y) ≠ 0, sino el resultado es trivial.

Sea dado un elemento y ∈ Q tal que S(y) ≠ 0 (notamos que un tal y puede ser encontrado mediante un test aleatorio de Zippel–Schwartz (ver [Zip79], [Sch80] o [Zip93], también [HS80] y [HS82]), e.g. en el hipercubo [1, 2D] ∩ ZZ en espacio S y tiempo 2T ).

Sea u(Y) = Y^{D} + u_{D−1}Y^{D−1} + ⋯ + u_{0} donde u_{D−1}, …, u_{0} son elementos de K. Y sea

\frac{v((Y − y)^{−1})}{(Y − y)u((Y − y)^{−1})} = \frac{s((Y − y)^{−1})}{(Y − y)r((Y − y)^{−1})} = ∑_{i=0}^{+∞} h_{i}(Y − y)^{i}.  (3)

la representación en serie de potencias formal de la función racional \frac{v((Y −y)^{−1})}{(Y −y)u((Y −y)^{−1})}.

Entonces por [BP94, Proposition 2.9.1] se sigue la identidad

( \begin{matrix}h_{0} & h_{1} & … & h_{δ−1} \\ h_{1} & h_{2} & … & h_{δ} \\ ⋮ & ⋮ & & ⋮ \\ h_{δ−1} & h_{δ} & … & h_{2δ−2} \end{matrix} ) ( u_{0} ; u_{1} ; ⋮ ; u_{δ−1} ) = − ( h_{δ} ; h_{δ+1} ; ⋮ ; h_{2δ−1} )  (4)

Dado que r(Y) es no nulo, deducimos que los primeros D coeficientes del desarrollo en series de potencias (3) es no nulo, i.e. (h_{0}, …, h_{D−1}) ≠ 0. De esta manera aplicamos el algoritmo de Sieveking–Kung para encontrar un elemento ρ de R y a los elementos ρ^{D}h_{0}, …, ρ^{D}h_{D−1} de R que representan múltiplos por ρ^{D} de los primeros D coeficientes del desarrollo en series de potencias (3). Notamos que esto puede hacerse en espacio O(D) y en tiempo O(D log^{2} D log log D).

Sea γ := ρ^{D}, y notemos que el sistema (4) tiene la misma solución que el nuevo sistema que obtenemos al reemplazar las entradas h_{0}, …, h_{D−1} por sus múltiplos γh_{0}, …, γh_{D−1}, ergo encontremos una solución del nuevo sistema. Dado que la matriz que queda definida es de tipo Hankel, resolvemos al nuevo sistema (o equivalentemente a (4)) usando una ligera variación del procedimiento descripto en [SL92] usando espacio adicional O(D) y en tiempo adicional O(D^{2} log D log log D). Aclaramos que mediante dicha variación encontraremos no a la solución exacta, sino al múltiplo (γu_{0}, …, γu_{D−1}) con las mismas cotas asintóticas de complejidad.

2.2 Definiciones y resultados geométricos

Sea V ∈ IA^{n} una variedad algebraica equidimensional. Si V es cero dimensional se define el grado geométrico de V como el número de puntos en V . Supongamos que la dimensión de V es positiva e igual a r ≤ n. En este caso consideramos la clase D de subespacios afines de dimensión r.

Definición 8 Sea D_{V} la subclase de D de todos los subespacios afines H ∈ D tales que H ∩ D es una variedad cero dimensional. Definimos el grado de V como el máximo de los grados de las intersecciones de V con los subespacios afines de la clase D_{V}.

En el caso general, si V es una variedad algebraica y V = ∪_{i}C_{i} es una descomposición irredundante de la variedad en componentes irreducibles, se define el grado de V como

deg(V) := ∑_{i} deg(C_{i}).

El grado así definido es siempre un número natural positivo. Además verifica la siguiente propiedad conocida como desigualdad de Bézout:

Teorema 9 (Desigualdad de Bézout) Sean V y W dos variedades algebraicas. Se tiene

deg(V ∩ W) ≤ deg(V). deg(W).

El grado geométrico de una variedad y la desigualdad de Bézout son conceptos desarrollados en [Hei83] (ver también [Ful84]).

Proposición 10 ([GHS93]) Sea k un cuerpo de característica cero, sea f_{1}, …, f_{r} una sucesión regular de polinomios en k[X_{1}, …, X_{m}] y supongamos que las variables están en posición de Noether con respecto al ideal F = (f_{1}, …, f_{r}). Supongamos además que F es un ideal radical. Sea A := k[X_{1}, …, X_{r}] y B := k[X_{1}, …, X_{m}]/F. Entonces, B es un A–módulo libre de rango acotado por el grado de la variedad definida por F.

Finalmente definimos el concepto de solución geométrica de una variedad cero– dimensional.

Definición 11 ([HKP^{+}98]) Sea k un cuerpo de característica cero, y sea k̄ un cuerpo algebraicamente cerrado que contiene al cuerpo k. Sea n ∈ IN, sean X_{1}, …, X_{n}, Y indeterminadas sobre k. Sean dados polinomios f_{1}, …, f_{s} ∈ k[X_{1}, …, X_{n}] que definen una subvariedad cero–dimensional de IA^{n}(k̄). Una solución geométrica de la subvariedad cero–dimensional V (o de la extensión k → k[V]) está dada por una forma k–lineal U = λ_{1}X_{1} + ⋯ + λ_{n}X_{n} ∈ k[X_{1}, …, X_{n}] y por n + 1 polinomios univariados q, v_{1}, …, v_{n} ∈ k[Y] tales que las siguientes condiciones algebraicas y geométricas se cumplen:

• el polinomio q es mónico, separable y tiene grado la cardinalidad de V y los grados de v_{1}, …, v_{n} son estrictamente menores que la cardinalidad de V, i.e.

deg q = #V  y  deg v_{i} < #V  ,

• {η ∈ k̄ : q(η) = 0} = {U(ξ) : ξ ∈ V } y V = {(v_{1}(η), …, v_{n}(η)) : η ∈ k̄ y q(η) = 0}.

2.3 Bases de Gröbner

Esta subsección y la siguiente son un resumen de resultados conocidos en la teoría de bases de Gröbner. Para más información, ver [CLO92]. En lo que sigue, F denotará a un anillo de polinomios k[Z_{1}, …, Z_{m}] sobre un cuerpo k. Un monomio m de F es un elemento que se puede escribir m = Z_{1}^{a_{1}} … Z_{m}^{a_{m}} para alguna m–upla (a_{1}, …, a_{m}) ∈ IN_{0}^{m}, un término de F es un monomio multiplicado por un escalar.

Un ideal I ⊆ F generado por un conjunto de monomios es llamado un ideal monomial. Sean m_{1}, m_{2} dos monomios en F, m_{1} = Z_{1}^{a_{1}} … Z_{m}^{a_{m}}, m_{2} = Z_{1}^{b_{1}} … Z_{m}^{b_{m}}, el máximo común divisor entre m_{1} y m_{2} es el monomio

MCD(m_{1}; m_{2}) := Z_{1}^{min{a_{1};b_{1}}} … Z_{m}^{min{a_{m};b_{m}}}.

Definición 12 Un orden monomial en F es un orden total > en los monomios de F tal que si m_{1}, m_{2} son monomios de F y n ≠ 1 es un monomio de F, entonces

m_{1} > m_{2} implica nm_{1} > nm_{2} > m_{2}.

Si > es un orden monomial, entonces para todo f ∈ F definimos el término inicial de f, y lo notamos M(f), al término de f de mayor orden respecto de >, y si I ⊆ F es un ideal, definimos M(I) al ideal de F generado por {M(f) : f ∈ I}. Sean m_{1}, m_{2} en F, m_{1} = Z_{1}^{a_{1}} … Z_{m}^{a_{m}}, m_{2} = Z_{1}^{b_{1}} … Z_{m}^{b_{m}}, se tienen los siguientes órdenes monomiales: Orden lexicográfico. m_{1} >_{lex} m_{2} si y sólo si a_{i} > b_{i} donde i es el primer índice tal que a_{i} ≠ b_{i}. Orden lexicográfico homogéneo. m_{1} >_{hlex} m_{2} si y sólo si deg(m_{1}) > deg(m_{2}) ó deg(m_{1}) = deg(m_{2}) y a_{i} > b_{i} donde i es el primer índice tal que a_{i} ≠ b_{i}. Si tenemos una secuencia de órdenes parciales >_{1}, >_{2}, …, se define el orden parcial, llamado producto lexicográfico, como el orden en el cual m_{1} > m_{2} si existe i ∈ IN tal que m_{1} >_{i} m_{2}, y para todo j < i, m_{1} y m_{2} no son comparables respecto del orden >_{j}. Si I ⊆ F es un ideal generado por monomios m_{1}, …, m_{t}, es trivial decidir cuándo un monomio m pertenece a I: esto ocurre si y sólo si m es divisible por algún m_{i}. Más generalmente, un polinomio f ∈ F pertenece a un ideal monomial I si y sólo si cada uno de sus monomios pertenece a I. Un resultado importante es el siguiente:

Teorema 13 (Macaulay) Sea I un ideal de F, sea > un orden monomial en F, el conjunto B de todos los monomios que no están en M(I) es una base del k-espacio vectorial F/I.

Definición 14 Sea I un ideal de F. Una base de Gröbner de I respecto de un orden monomial > es un conjunto de polinomios g_{1}, …, g_{t} tal que:

i) {g_{1}, …, g_{t}} genera a I.

ii) {M(g_{1}), …, M(g_{t})} genera a M(I).

Una base de Gröbner g_{1}, …, g_{t} tal que M(g_{i}) no divide a ningún monomio de g_{j} para todo i ≠ j es llamada una base reducida. Más resultados útiles:

Lema 15 Todo orden monomial en F es un buen orden, es decir que todo subconjunto tiene primer elemento.

Lema 16 Sea I = (g_{1}, …, g_{t}) un ideal de F y > un orden monomial dado. Si M(g_{1}), …, M(g_{t}) son coprimos dos a dos, entonces g_{1}, …, g_{t} es una base de Gröbner.

Lema 17 (Algoritmo de división à la Hironaka) Sea > un orden monomial dado en F, y sean f, g_{1}, …, g_{t} polinomios en F. Existen f′, f_{1}, …, f_{t} en F tal que

f = ∑_{i=1}^{t} f_{i}g_{i} + f′

donde ninguno de los monomios de f′ pertenece al ideal (M(f_{1}), …, M(f_{t})). Más aún, M(f) ≥ M(f_{i}g_{i}) para todo i.

2.4 Teoría de Eliminación

Dadas Y_{1}, …, Y_{r}, Z_{1}, …, Z_{m} indeterminadas sobre un cuerpo k, sea F := k[Z_{1}, …, Z_{m}], dado un ideal I ⊆ F [Y_{1}, …, Y_{r}] = k[Z_{1}, …, Z_{m}, Y_{1}, …, Y_{r}] se quiere calcular J = I ∩ F. El significado geométrico de la eliminación es la proyección: dada la variedad algebraica V ⊆ k^{m+r} definida por los ceros de I, la proyección de V en k^{m} es un conjunto cuya clausura (en la topología Zariski) es la variedad definida por los ceros de J. Para eliminar variables usando bases de Gröbner se trabaja con un orden en T = k[Z_{1}, …, Z_{m}, Y_{1}, …, Y_{r}] que verifique:

Si f ∈ T y M(f) ∈ F, entonces f ∈ F.

Un orden con esta propiedad es llamado un orden de eliminación (respecto de Y_{1}, …, Y_{r}). Se tiene el siguiente resultado:

Lema 18 Sea > un orden monomial en T = F [Y_{1}, …, Y_{r}], y supongamos que > es un orden de eliminación respecto de las variables Y_{1}, …, Y_{r}. Si I ⊆ T es un ideal, entonces respecto al orden monomial de F resultante de restringir >, tenemos

M(I ∩ F) = M(I) ∩ F

Más aún, si g_{1}, …, g_{t} es una base de Gröbner de I, y g_{1}, …, g_{u} son los g_{i} que no contienen variables Y_{j}, entonces g_{1}, …, g_{u} es una base de Gröbner en F de I ∩ F.

2.5 Series de Puiseux

El dominio y el cuerpo de las series formales de potencias. Un polinomio sobre un dominio D se define como una suma formal finita, a_{0} + a_{1}X + … + a_{n}X^{n}, donde los coeficientes a_{i} pertenecen al dominio D y X es una indeterminada sobre D. Si se permiten sumas infinitas de este tipo, a_{0} +a_{1}X +…+a_{n}X^{n} +… se obtiene un conjunto llamado las series formales de potencias sobre D y se nota D[|X|]. Dos series se suman y multiplican de la misma manera que dos polinomios, y D[|X|] resulta un dominio. Sea k un cuerpo, sea k((X)) el cuerpo de fracciones de k[|X|]. Se prueba que los elementos de k((X)) son series formales de potencias con un finito número de términos con exponente negativo.

El cuerpo k(X)^{∗} de las series de potencias fraccionarias. Consideramos para cada n ∈ IN el cuerpo k((X^{1/n})). Sea k(X)^{∗} := ⋃_{n∈IN} k((X^{1/n})) el conjunto formado por la unión de los cuerpos k((X^{1/n})). Si x̄, ȳ son dos elementos de k(X)^{∗}, entonces existen n, m ∈ N tal que x̄ ∈ k((X^{1/n})), ȳ ∈ k((X^{1/m})). Por lo tanto, x̄, ȳ ∈ k((X^{1/nm})) y también su suma, producto y cociente (si ȳ ≠ 0). Se sigue que k(X)^{∗} es un cuerpo. Los elementos de k(X)^{∗} se llaman series de Puiseux de X en k. Un elemento r̄ de k(X)^{∗} tiene una única escritura de tipo ∑_{j=z_{0}}^{∞} a_{j}X^{j/n} donde z_{0} ∈ ZZ, n ∈ IN, a_{j} ∈ k y a_{z_{0}} ≠ 0. Se define el orden de r̄ como el número z_{0}/n y se lo nota O(r̄).

Sea C(ε)^{∗} el cuerpo de las series de Puiseux de ε en C, sea d en IN, sea C[|ε^{1/d}|] ⊂ C(ε)^{∗} el anillo de las series formales en ε^{1/d}. Este anillo es completo respecto de M = (ε^{1/d}), su único ideal maximal. Se tiene la siguiente versión del Lema de Hensel ([Eis95, pages 210]):

Proposición 19 Sean f_{1}, …, f_{n} ∈ C[|ε^{1/d}|][X_{1}, …, X_{n}], sea J(x) la matriz jacobiana

J(x) = (∂f_{i}/∂X_{j}),

sea ā = (ā_{1}, …, ā_{n}) ∈ C[|ε^{1/d}|]^{n} y supongamos que det(J(ā)) es una unidad en C[|ε^{1/d}|]. Si

f_{i}(ā) ∈ M para 1 ≤ i ≤ n,

entonces existe un único elemento b̄ = (b̄_{1}, …, b̄_{n}) ∈ C[|ε^{1/d}|]^{n} tal que f_{i}(b̄) = 0 para 1 ≤ i ≤ n y b̄_{i} − ā_{i} ∈ M para 1 ≤ i ≤ n.

Para mayor información sobre series de Puiseux, ver ([Wal78]).

3 Un algoritmo para el cálculo de un polinomio minimal

Sean G_{1}, …, G_{n} polinomios en Q[X_{1}, …, X_{n}], sea d en IN tal que d > deg(G_{i}) para 1 ≤ i ≤ n. Consideramos el sistema de Pham–Brieskorn en Q[ε, X_{1}, …, X_{n}]:

{ F_{1}(ε, X_{1}, …, X_{n}) = X_{1}^{d} − εG_{1}(X_{1}, …, X_{n}) ; ⋮ ; F_{n}(ε, X_{1}, …, X_{n}) = X_{n}^{d} − εG_{n}(X_{1}, …, X_{n})  (5)

Supongamos que para cada 1 ≤ i ≤ n, α_{i} := G_{i}(0, …, 0) es no nulo.

Notación 20 Para i = 1, …, n, k = 1, …, d enumeramos con a_{i}^{(k)} a las raíces d–ésimas de α_{i} en C.

Consideramos F_{1}, …, F_{n} como polinomios de C(ε)^{∗}[X_{1}, …, X_{n}]. Las siguientes dos proposiciones caracterizan a las series de Puiseux en ε que se anulan en los polinomios F_{1}, …, F_{n}.

Proposición 21 Sean r̄_{1}, …, r̄_{n} ∈ C(ε)^{∗} tales que para i = 1, …, n se verifica la siguiente identidad en C(ε)^{∗}:

F_{i}(r̄_{1}, …, r̄_{n}) = 0

Entonces existe una n–upla a_{1}^{(k_{1})}, …, a_{n}^{(k_{n})} de raíces d–ésimas de α_{1}, …, α_{n} respectivamente tal que O(r̄_{i}) = 1/d y O(r̄_{i} − a_{i}^{(k_{i})}ε^{1/d}) > 1/d.

Demostración.– Dado que para 1 ≤ i ≤ n vale 0 = F_{i}(r̄_{1}, …, r̄_{n}) = r̄_{i}^{d} − εG_{i}(r̄_{1}, …, r̄_{n}), se tiene que r̄_{i}^{d} = εG_{i}(r̄_{1}, …, r̄_{n}) para 1 ≤ i ≤ n. Queremos ver que O(r̄_{i}) ≥ 0 :

Supongamos que no. Sea i_{0} tal que O(r̄_{i_{0}}) = min{O(r̄_{i})} < 0. Dado que por hipótesis, d > deg(G_{i_{0}}) y que estamos suponiendo O(r̄_{i_{0}}) negativo se tienen las desigualdades

O(r̄_{i_{0}}^{d}) = dO(r̄_{i_{0}}) < deg(G_{i_{0}})O(r̄_{i_{0}}) < deg(G_{i_{0}})O(r̄_{i_{0}}) + 1 ≤ O(εG_{i_{0}}(r̄_{1}, …, r̄_{n})).

Pero esto es absurdo pues O(r̄_{i_{0}}^{d}) = O(εG_{i_{0}}(r̄_{1}, …, r̄_{n})). Como O(r̄_{i}) ≥ 0 para todo i, se tiene que O(εG_{i}(r̄_{1}, …, r̄_{n})) ≥ 1 y por lo tanto O(r̄_{i}^{d}) = d.O(r̄_{i}) = O(εG_{i}(r̄_{1}, …, r̄_{n})) ≥ 1. Es decir que O(r̄_{i}) ≥ 1/d para todo i.

Ahora bien, si O(r̄_{i}) ≥ 1/d > 0 para todo i, el orden de εG_{i}(r̄_{1}, …, r̄_{n}) es igual a 1 pues G_{i}(0, …, 0) = α_{i} ≠ 0 por hipótesis. El término de menor orden de εG_{i}(r̄_{1}, …, r̄_{n}) resulta entonces ser α_{i}ε. Puesto que 0 = r̄_{i}^{d} − εG_{i}(r̄_{1}, …, r̄_{n}), el orden de r̄_{i}^{d} es 1 y su término de menor orden es igual a α_{i}ε, y por lo tanto el término de menor orden de r̄_{i} es igual a a_{i}^{(k_{i})}ε^{1/d} para alguna raíz d–ésima a_{i}^{(k_{i})} de α_{i}, que era lo que se quería probar.

Proposición 22 Dada una n–upla a_{1}^{(k_{1})}, …, a_{n}^{(k_{n})} de raíces d–ésimas de α_{1}, …, α_{n} respectivamente existen únicas r̄_{1}, …, r̄_{n} en C(ε)^{∗} que verifican las siguientes condiciones:

• O(r̄_{i}) = 1/d para 1 ≤ i ≤ n.

• O(r̄_{i} − a_{i}^{(k_{i})}ε^{1/d}) > 1/d para 1 ≤ i ≤ n.

• F_{i}(r̄_{1}, …, r̄_{n}) = 0.

Además, r̄_{1}, …, r̄_{n} pertenecen a C[|ε^{1/d}|].

Demostración.– Dada una n–upla a_{1}^{(k_{1})}, …, a_{n}^{(k_{n})} se definen los polinomios F̃_{1}, …, F̃_{n} ∈ C(ε)^{∗}[X_{1}, …, X_{n}] de la siguiente manera:

{ F̃_{1}(X_{1}, …, X_{n}) = (F_{1}((X_{1} + a_{1}^{(k_{1})})ε^{1/d}, …, (X_{n} + a_{n}^{(k_{n})})ε^{1/d}))ε^{−1} ; ⋮ ; F̃_{n}(X_{1}, …, X_{n}) = (F_{n}((X_{1} + a_{1}^{(k_{1})})ε^{1/d}, …, (X_{n} + a_{n}^{(k_{n})})ε^{1/d}))ε^{−1}

Estos polinomios pertenecen a C[ε^{1/d}][X_{1}, …, X_{n}] pues F̃_{i} = (F_{i}((X_{1} +a_{1}^{(k_{1})})ε^{1/d}, …, (X_{n} +a_{n}^{(k_{n})})ε^{1/d}))ε^{−1} = (((X_{i} +a_{i}^{(k_{i})})ε^{1/d})^{d} −εG_{i}((X_{1} + a_{1}^{(k_{1})})ε^{1/d}, …, (X_{n} + a_{n}^{(k_{n})})ε^{1/d})))ε^{−1} = (X_{i} + a_{i}^{(k_{i})})^{d} − G_{i}((X_{1} + a_{1}^{(k_{1})})ε^{1/d}, …, (X_{n} + a_{n}^{(k_{n})})ε^{1/d})).

Notamos DF̃) a la matriz jacobiana (∂F̃_{i}/∂X_{j})_{1≤i,j≤n}. Tenemos la siguiente afirmación:

Afirmación: Evaluando los polinomios F̃_{1}, …, F̃_{n} en el origen 0 = (0, …, 0) ∈ C[|ε^{1/d}|]^{n} se tiene que :

i) O(F̃_{i}(0)) ≥ 1/d para 1 ≤ i ≤ n.

ii) det(DF̃)(0) es inversible en C[|ε^{1/d}|].

El polinomio F̃_{i}, evaluado en (0, …, 0) resulta:

F̃_{i}(0, …, 0) = (F_{i}((0 + a_{1}^{(k_{1})})ε^{1/d}, …, (0 + a_{n}^{(k_{n})})ε^{1/d}))ε^{−1} =
= (((0 + a_{i}^{(k_{i})})ε^{1/d})^{d} − εG_{i}((0 + a_{1}^{(k_{1})})ε^{1/d}, …, (0 + a_{n}^{(k_{n})})ε^{1/d}))ε^{−1} =
= (a_{i}^{(k_{i})})^{d} − G_{i}(a_{1}^{(k_{1})}ε^{1/d}, …, a_{n}^{(k_{n})}ε^{1/d})

Dado que (a_{i}^{(k_{i})})^{d} = α_{i} y que O(G_{i}(a_{1}^{(k_{1})}ε^{1/d}, …, a_{n}^{(k_{n})}ε^{1/d}) − α_{i}) ≥ 1/d, se tiene la primer afirmación. La derivada parcial de F̃_{i} respecto de X_{j} es

\frac{∂}{∂X_{j}} F̃_{i} = \frac{∂}{∂X_{j}} (X_{i} + a_{i}^{(k_{i})})^{d} − \frac{∂}{∂X_{j}} G_{i}((X_{1} + a_{1}^{(k_{1})})ε^{1/d}, …, (X_{n} + a_{n}^{(k_{n})})ε^{1/d}) =

= δ_{i,j}d(X_{i} + a_{i}^{(k_{i})})^{d−1} − \frac{∂}{∂X_{j}} G_{i}(a_{1}^{(k_{1})}ε^{1/d}, …, a_{n}^{(k_{n})}ε^{1/d})ε^{1/d}

Donde δ_{i,j} vale 1 si i = j y 0 en otro caso. Evaluada en 0 = (0, …, 0) resulta

\frac{∂}{∂X_{j}} F̃_{i}(0) = δ_{i,j}d(a_{i}^{(k_{i})})^{d−1} − \frac{∂}{∂X_{j}} G_{i}(a_{1}^{(k_{1})}, …, a_{n}^{(k_{n})})ε^{1/d}

En particular se tiene que O(\frac{∂}{∂X_{j}} F̃_{i}(0)) = 0 si i = j y O(\frac{∂}{∂X_{j}} F̃_{i}(0)) ≥ 1/d si i ≠ j.

Por lo tanto, O(det(DF̃)(0) − d^{n} ∏_{i=1}^{n}(a_{i}^{(k_{i})})^{d−1}) ≥ 1/d. Dado que d^{n} ∏_{i=1}^{n}(a_{i}^{(k_{i})})^{d−1} es distinto de cero, se sigue que det(DF̃)(0) es inversible en C[|ε^{1/d}|], que es lo que queríamos demostrar.

De acuerdo a la Proposición 19, existe un único elemento r̃ = (r̃_{1}, …, r̃_{n}) ∈ C[|ε^{1/d}|]^{n} tal que

O(r̃_{i}) ≥ 1/d y F̃_{i}(r̃_{1}, …, r̃_{n}) = 0 para 1 ≤ i ≤ n.

Definimos r̄ = (r̄_{1}, …, r̄_{n}) := ((a_{1}^{(k_{1})} + r̃_{1})ε^{1/d}, …, (a_{n}^{(k_{n})} + r̃_{n})ε^{1/d}) ∈ C[|ε^{1/d}|]^{n}. r̄ es el único elemento de C[|ε^{1/d}|]^{n} que verifica las condiciones enunciadas, es decir:

• O(r̄_{i}) = 1/d para 1 ≤ i ≤ n.

• O(r̄_{i} − a_{i}^{(k_{i})}ε^{1/d}) > 1/d para 1 ≤ i ≤ n.

• F_{i}(r̄_{1}, …, r̄_{n}) = 0.

Resta probar la unicidad de la solución en (C(ε)^{∗})^{n}. Sea ȳ = (ȳ_{1}, …, ȳ_{n}) ∈ (C(ε)^{∗})^{n} una serie que verifica lo pedido. Existe m ∈ IN tal que ȳ ∈ C[|ε^{1/m}|]^{n} y por lo tanto ȳ, r̄ ∈ C[|ε^{1/md}|]^{n}. Ahora bien, los polinomios F̃_{1}, …, F̃_{n} pertenecen a C[ε^{1/md}][X_{1}, …, X_{n}] y el origen (0, …, 0) ∈ C[|ε^{1/md}|]^{n} sigue verificando las hipótesis de la Proposición 19, esta vez en el anillo C[|ε^{1/md}|]^{n}. Puesto que esta Proposición garantiza unicidad de la solución, se sigue entonces que ȳ = r̄.

Como consecuencia de las dos proposiciones anteriores se tiene que hay en total d^{n} raíces r̄^{(i)} = (r̄_{1}^{(i)}, …, r̄_{n}^{(i)}) en C[|ε^{1/d}|]^{n} del ideal (F_{1}, …, F_{n}) y quedan unívocamente determinadas por su primer n–upla: la coordenada j–ésima de r̄^{(i)} se escribe r̄_{j}^{(i)} = a_{j}^{(k_{i})}ε^{1/d} + términos de orden superior a 1/d, donde a_{j}^{(k_{i})} es una raíz d–ésima de α_{j}. La proposición siguiente será necesaria para probar la radicalidad del ideal generado por F_{1}, …, F_{n} en Q[ε, X_{1}, …, X_{n}].

Proposición 23 Sea D un dominio, d ∈ IN, p un polinomio en D[X_{1}, …, X_{n}] tal que para 1 ≤ i ≤ n, deg_{X_{i}} p < d y sean, para 1 ≤ i ≤ n, 1 ≤ k ≤ d, elementos ξ_{i}^{(k)} ∈ D tales que ξ_{i}^{(k)} ≠ ξ_{i}^{(k′)} para k ≠ k′ y p(ξ_{1}^{(k_{1})}, …, ξ_{n}^{(k_{n})}) = 0 para toda n–upla (ξ_{1}^{(k_{1})}, …, ξ_{n}^{(k_{n})}). Entonces p es el polinomio nulo.

Demostración.– Se prueba por inducción en la cantidad de variables n. Si n = 1, se tiene que p es un polinomio en D[X_{1}] de grado menor que d y con d raíces, por lo que p = 0. Supongamos que vale para n = h, sea n = h + 1: Sea p = ∑_{i=0}^{d−1} a_{i}X_{h+1}^{i}, a_{i} ∈ D[X_{1}, …, X_{h}] su escritura respecto de la variable Xh + 1. Evaluando las primeras h variables en una h–upla (ξ_{1}^{(k_{1})}, …, ξ_{h}^{(k_{h})}) se tiene un polinomio en D[X_{h+1}], de grado menor que d y con d raíces, por lo que a_{i}(ξ_{1}^{(k_{1})}, …, ξ_{h}^{(k_{h})}) = 0 para 0 ≤ i < d. Aplicando la hipótesis inductiva en los polinomios a_{i} se sigue que p es el polinomio nulo.

Definición 24 Sea > el orden monomial en Q[ε, X_{1}, …, X_{n}] que es producto lexicográfico del orden parcial definido por el grado total en X_{1}, …, X_{n} y el orden lexicográfico donde X_{1} > … > X_{n} > ε.

Con este orden, para cada 1 ≤ i ≤ n, el término inicial de F_{i} es M(F_{i}) = X_{i}^{d}.

Proposición 25 El ideal I = (F_{1}, …, F_{n}) generado por los polinomios del sistema de Pham–Brieskorn en (1) es radical en Q[ε, X_{1}, …, X_{n}].

Demostración.– Supongamos al contrario que exista f ∈ Q[ε, X_{1}, …, X_{n}], m ∈ IN tal que f ∉ I y f^{m} ∈ I. Sea > el orden monomial en Q[ε, X_{1}, …, X_{n}] dado en la Definición 24. Por el algoritmo de división de Hironaka (ver Lema 17), existen g_{1}, …, g_{n}, r ∈ Q[ε, X_{1}, …, X_{n}] tal que f − ∑_{i=1}^{n} g_{i}F_{i} = r y ningún término de r pertenece al ideal (M(F_{1}), …, M(F_{n})) = (X_{1}^{d}, …, X_{n}^{d}). Es decir que todo término aX_{1}^{w_{1}}, …, X_{1}^{w_{1}}ε^{w} de r verifica que w_{i} < d para 1 ≤ i ≤ n. Por otra parte, dado que r ≡ f módulo I, y f^{m} ≡ 0 módulo I, se tiene que r^{m} ≡ 0 módulo I. Sea r̄^{(i)} ∈ C[|ε^{1/d}|]^{n} una n–upla de series de Puiseux que anula a los polinomios de I (ver Proposiciones 21 y 22), se tiene entonces que r^{m}(r̄^{(i)}) = 0 en C[|ε^{1/d}|] y, dado que C[|ε^{1/d}|] es un dominio, se tiene que r(r̄^{(i)}) = 0 en C[|ε^{1/d}|]. Escribimos r = ∑_{j} p_{j}, donde los términos m = a_{m}X_{1}^{m_{1}} … X_{n}^{m_{n}}ε_{m} de p_{j} verifican \frac{1}{d} ∑_{i=1}^{n} m_{i} + m̃ = j. Sea j_{0} := min\{j : p_{j} ≠ 0\}.

Afirmación: Pensamos al polinomio p_{j_{0}} en el anillo C[|ε^{1/d}|][X_{1}, …, X_{n}]; dada una n–upla a_{1}^{(k_{1})}, …, a_{n}^{(k_{n})} de raíces d–ésimas de α_{1}, …, α_{n} se tiene que p_{j_{0}}(a_{1}^{(k_{1})}ε^{1/d}, …, a_{n}^{(k_{n})}ε^{1/d}) = 0 en C[|ε^{1/d}|].

El polinomio p_{j_{0}}, evaluado en a_{1}^{(k_{1})}ε^{1/d}, …, a_{n}^{(k_{n})}ε^{1/d}, ó bien es un elemento de C[|ε^{1/d}|] de orden j_{0}, ó bien es el elemento nulo. Sabemos de la Proposición 22 que, dada una n–upla a_{1}^{(k_{1})}, …, a_{n}^{(k_{n})} existen r̄_{1}, …, r̄_{n} en C[|ε^{1/d}|] tales que r(r̄_{1}, …, r̄_{n}) = 0 y r̄_{i} = a_{i}^{(k_{i})}ε^{1/d} + términos de orden superior. Dado que O(r − p_{j_{0}})(r̄_{1}, …, r̄_{n}) > j_{0} y O(p_{j_{0}}(r̄_{1}, …, r̄_{n}) − p_{j_{0}}(a_{1}^{(k_{1})}ε^{1/d}, …, a_{n}^{(k_{n})}ε^{1/d})) > j_{0} se concluye de r(r̄_{1}, …, r̄_{n}) = 0 que vale p_{j_{0}}(a_{1}^{(k_{1})}ε^{1/d}, …, a_{n}^{(k_{n})}ε^{1/d}) = 0 en C[|ε^{1/d}|]. Ahora bien, el polinomio p_{j_{0}} ∈ Q[ε, X_{1}, …, X_{n}] verifica que deg_{X_{i}}(p_{j_{0}}) < d para 1 ≤ i ≤ n y se anula en las n–uplas a_{1}^{(k_{1})}ε^{1/d}, …, a_{n}^{(k_{n})}ε^{1/d}. Pensando al polinomio p_{j_{0}} en el anillo de polinomios C[|ε^{1/d}|][X_{1}, …, X_{n}], la Proposición 23 nos permite concluir que p_{j_{0}} es el polinomio nulo, pero esto es absurdo pues j_{0} = min{j : p_{j} ≠ 0}.

Sea V ∈ IA^{n+1} la variedad algebraica afín definida por los ceros de I = (F_{1}, …, F_{n}), el sistema de Pham definido en (1). Observamos que V es no vacía pues el origen pertenece a V. Sea B el ágebra Q[ε, X_{1}, …, X_{n}]/I. De la Proposición 25 el ideal I es radical, y B resulta el anillo de coordenadas de V. Recordamos la definición de orden monomial dada en 24: Sea > el orden monomial en Q[ε, X_{1}, …, X_{n}] que es producto lexicográfico del orden parcial definido por el grado total en X_{1}, …, X_{n} y el orden lexicográfico donde X_{1} > … > X_{n} > ε. Notar que este orden verifica que si f ∈ Q[ε, X_{1}, …, X_{n}] y M(f) ∈ Q[ε], entonces f ∈ Q[ε], por lo tanto es un orden de eliminación respecto de X_{1}, …, X_{n}. Con este orden, para cada 1 ≤ i ≤ n, el término inicial de F_{i} es M(F_{i}) = X_{i}^{d}.

Proposición 26 Bajo las hipótesis y notación anteriores se verifica:

i) G := {F_{1}, …, F_{n}} es una base de Gröbner reducida de I ⊆ Q[ε, X_{1}, …, X_{n}] para el orden monomial definido anteriormente y M(I) = (X_{1}^{d}, …, X_{n}^{d}).

ii) El morfismo

\begin{matrix}π : V ⟶ IA^{1} \\ π(τ, ξ_{1}, …, ξ_{n}) = τ \end{matrix}

es finito, es decir que las variables están en posición de Noether respecto de V.

iii) V es una curva.

iv) F_{1}, …, F_{n} es una sucesión regular en Q[ε, X_{1}, …, X_{n}].

v) deg(V) = d^{n}.

Demostración.– i) Los polinomios F_{1}, …, F_{n} generan I y los monomios M(F_{i}) = X_{i}^{d} son coprimos dos a dos; del Lema 16 se sigue que G es una base de Gröbner de I. Dado que G es una base de Gröbner, M(I) = (M(F_{1}), …, M(F_{n})) = (X_{1}^{d}, …, X_{n}^{d}). Puesto que X_{i}^{d} > M(F_{j} − X_{j}^{d}) y X_{i}^{d}, X_{j}^{d} son coprimos dos a dos para i ≠ j, se tiene que X_{i}^{d} no divide a ningún monomio de F_{j}, y por lo tanto G es una base de Gröbner reducida.

ii) Por definición, el morfismo π es finito si π(V) es denso en IA^{1} y el morfismo de anillos asociado

π^{∗} : Q[ε] ⟶ B

es entero. La clausura de π(V) es igual a la variedad V_{ε} definida por el ideal J_{ε} = I ∩ Q[ε] en Q[ε]. Queremos ver entonces que V_{ε} es IA^{1}:

Sea F = Q[ε], T = Q[ε, X_{1}, …, X_{n}]. > es un orden de eliminación respecto de X_{1}, …, X_{n} y G = {F_{1}, …, F_{n}} es una base de Gröbner de (F_{1}, …, F_{n}). Por el Lema 18, tenemos que M(J_{ε}) = (X_{1}^{d}, …, X_{n}^{d})∩Q[ε]. Ahora bien, (X_{1}^{d}, …, X_{n}^{d})∩Q[ε] = {0} por lo que J_{ε} = {0} y entonces la variedad V_{ε} = V (J_{ε}) = IA^{1}.

Dado que B es una Q[ε]–álgebra finitamente generada, B es entero sobre π^{∗}(Q[ε]) ≃ Q[ε] si y sólo si B es finito como Q[ε]–módulo ([AM69]). De acuerdo al Teorema 13, el conjunto E formado por los monomios de Q[ε, X_{1}, …, X_{n}] que no pertenecen al ideal monomial M(I) es una base del Q–espacio vectorial Q[ε, X_{1}, …, X_{n}]/I. Ahora bien, un monomio m pertenece a M(I) si y sólo si es divisible por algún X_{i}^{d}. Es decir que E se escribe

E = {m ∈ Q[ε, X_{1}, …, X_{n}] : m = X_{1}^{a_{1}} … X_{n}^{a_{n}}.ε^{b}, a_{i} < d}.

Por lo tanto, el conjunto D = {m ∈ Q[ε, X_{1}, …, X_{n}] : m = X_{1}^{a_{1}} … X_{n}^{a_{n}}, a_{i} < d} es una base de Q[ε, X_{1}, …, X_{n}]/I como Q[ε]–módulo y además es un conjunto finito.

iii) Dado que π : V ⟶ IA^{1} es un morfismo entero, tenemos que dim(V) = dim(IA^{1}) = 1. Ahora bien, no hay componentes de dimensión menor pues V es una variedad en (n + 1) variables generada por n polinomios, por lo que toda componente tiene dimensión ≥ (n + 1) − n = 1. Concluímos entonces que todas las componentes tienen dimensión 1.

iv) Para 1 ≤ k < n, sean I_{k} = (F_{1}, …, F_{k}). Igual que en i) se prueba que F_{1}, …, F_{k} es una base de Gröbner reducida de I_{k}, y entonces M(I_{k}) = (M(F_{1}), …, M(F_{k})) = = (X_{1}^{d}, …, X_{k}^{d}). Por definición, F_{1}, …, F_{n} es sucesión regular en Q[ε, X_{1}, …, X_{n}] si para 1 ≤ k < n, el polinomio F_{k+1} no es divisor de cero de Q[ε, X_{1}, …, X_{n}]/I_{k}. Sea C := {g ∈ Q[ε, X_{1}, …, X_{n}] : g.F_{k+1} ∈ I_{k} y g ∉ I_{k}}. El conjunto C es vacío si y sólo si el polinomio F_{k+1} no es divisor de cero del álgebra Q[ε, X_{1}, …, X_{n}]/I_{k}. Supongamos por el contrario que C ≠ ∅:

Sea g_{0} un elemento de C, de orden mínimo entre todos los elementos de C, respecto del orden monomial definido en 24, es decir que M(g_{0}) = min{M(g) : g ∈ C}. Existe un tal g_{0} pues todo subconjunto de Q[ε, X_{1}, …, X_{n}] tiene primer elemento respecto de un orden monomial > fijo (ver Lema 15). Se tiene que M(g_{0}.F_{k+1}) = M(g_{0})M(F_{k+1}) = X_{k+1}^{d}M(g_{0}) ∈ M(I_{k}). Al ser M(I_{k}) un ideal generado por monomios, un monomio pertenece al mismo si y sólo si es divisible por algún monomio generador. Calculamos el máximo común divisor entre los términos iniciales de F_{i} y F_{k+1}: MCD(M(F_{k+1}); M(F_{i})) = MCD(X_{k+1}^{d}; X_{i}^{d}) = 1 para 1 ≤ i ≤ k resulta entonces que M(g_{0}.F_{k+1}) ∈ I_{k} implica que M(g_{0}) ∈ M(I_{k}). Sea h ∈ I_{k} tal que M(g_{0}) = M(h). Se tiene que (g_{0} − h)F_{k+1} ∈ I_{k} y M(g_{0} − h) < M(g_{0}) = min{M(g) : g ∈ C}. Si g_{0} − h ∈ I_{k}, entonces g_{0} ∈ I_{k}, lo cual es falso, y si g_{0} − h ∉ I_{k}, entonces g_{0} − h ∈ C, pero esto es absurdo pues M(g_{0} − h) < M(g_{0}).

v) De la desigualdad de Bézout y de la observación de que el grado de una hipersuperficie es igual al grado del polinomio que la define, se deduce que, al ser V una variedad definida por la sucesión regular F_{1}, …, F_{n} de grado d, se tiene que deg(V) ≤ d^{n}. La otra desigualdad se deduce de la Proposición 10: En nuestro caso, F_{1}, …, F_{n} es una sucesión regular en Q[ε, X_{1}, …, X_{n}], A = Q[ε], B = B, el ideal (F_{1}, …, F_{n}) es radical en Q[ε, X_{1}, …, X_{n}] (ver Proposición 25) y las variables se encuentran en posición de Noether, así que tenemos la desigualdad deg(V) ≥ #D = d^{n} donde D es la base obtenida en ii).

Observación 27 El punto 0 ∈ IA^{n+1} es un punto singular de la variedad V y es el único elemento de la fibra π^{−1}(0).

Sea H un polinomio perteneciente a Q[ε, X_{1}, …, X_{n}]. Dado que el morfismo de anillos Q[ε] ⟶ B es entero, existe un único polinomio m_{H} en Q[ε][T], mónico en T y de grado mínimo en T, tal que m_{H}(H) = 0 en B.

Tenemos la siguiente cota para el grado total de m_{H} :

Proposición 28 ([SS96]) Sea F en k[X_{1}, …, X_{m}] un ideal radical, V:=V(F) y supongamos que la dimensión de V es r y que las variables están en posición de Noether. Sea A := k[X_{1}, …, X_{r}] y B := k[X_{1}, …, X_{m}]/F y sea f ∈ k[X_{1}, …, X_{m}]. Entonces, existe un polinomio mónico F ∈ A[T] que verifica que F (f) = 0 en B y cuyo grado total está acotado por deg(V). deg(f).

En nuestro caso, k = Q, F = I, la variedad V tiene dimensión 1 y A = Q[ε]. Entonces, dado H ∈ Q[ε, X_{1}, …, X_{n}], el polinomio m_{H} ∈ Q[ε][T] tiene grado total acotado por d^{n}. deg(H).

Observación 29 El grado en la variable T de m_{H} está acotado por el grado de V.

Esto se debe a que B es un Q[ε] - módulo de rango igual al grado geométrico de V.

Recordamos que a partir de las Proposiciones 21 y 22 se tienen exactamente d^{n} n– uplas r̄^{(i)} en C[|ε^{1/d}|]^{n} que se anulan en los polinomios F_{1}, …, F_{n}. Cada coordenada r_{j}^{(i)} de la n–upla r̄^{(i)} = (r_{1}^{(i)}, …, r_{n}^{(i)}) se escribe r_{j}^{(i)} = a_{j}^{(k_{i})}ε^{1/d} + R_{i,j} donde a_{j}^{(k_{i})} es una raíz d–ésima de α_{j} y O(R_{i,j}) > 1/d. Dado que hay una cantidad finita de n–uplas que se anulan en los polinomios F_{1}, …, F_{n}, existe U = ∑_{k=1}^{n} λ_{k}X_{k} ∈ Q[X_{1}, …, X_{n}] una forma lineal tal que U(r̄^{(i)}) ≠ U(r̄^{(j)}) para n–uplas distintas r̄^{(i)}, r̄^{(j)}. Existe una tal forma lineal, una manera de probarlo es utilizando la siguiente afirmación: Afirmación: Dado m ∈ IN, sean P_{1}, …, P_{m} elementos distintos de C^{n}. Existe una forma lineal U = ∑_{k=1}^{n} λ_{k}X_{k} ∈ Q[X_{1}, …, X_{n}] tal que U(P_{i}) ≠ U(P_{j}) para P_{i} ≠ P_{j}.

Dada una forma lineal U = ∑_{k=1}^{n} λ_{k}X_{k} ∈ Q[X_{1}, …, X_{n}], evaluar U en un elemento P ∈ C^{n} es igual a hacer el producto interno usual de C^{n} entre P y λ = (λ_{1}, …, λ_{n}). Pedir que U(P_{i}) ≠ U(P_{j}) para P_{i} ≠ P_{j} es equivalente a pedir que U(P_{i})−U(P_{j}) ≠ 0 para P_{i} ≠ P_{j} y puesto que U(P_{i}) − U(P_{j}) = U(P_{i} − P_{j}) es el producto interno entre los vectores λ = (λ_{1}, …, λ_{n}) y P̄_{i} − P_{j}, esto es equivalente a pedir que el vector (λ_{1}, …, λ_{n}) no sea perpendicular a los vectores P̄_{i} − P_{j} para todo par i, j distintos. Fijando i ≠ j, el conjunto W_{i,j} := {w ∈ C^{n} :< w; P̄_{i} − P_{j} >= 0} de vectores perpendiculares al vector P̄_{i} − P_{j} es un subespacio lineal cerrado de dimensión n − 1, y su complemento es un abierto denso de C^{n}. La unión finita de subespacios de dimensión n − 1 es un cerrado incluído estrictamente en C^{n}, y su complemento es un abierto denso de C^{n}. Puesto que Q^{n} también es un conjunto denso en C^{n}, existe λ = (λ_{1}, …, λ_{n}) ∈ Q^{n} que no pertenece a W_{i,j} para todo par i ≠ j y por lo tanto la forma lineal U = ∑_{k=1}^{n} λ_{k}X_{k} ∈ Q[X_{1}, …, X_{n}] verifica que U(P_{i}) ≠ U(P_{j}) para P_{i} ≠ P_{j}.

Sean P_{1}, …, P_{d^{n}} ∈ C^{n} todas las n–uplas tales que sus coordenadas son raíces d– ésimas de α_{1}, …, α_{n} respectivamente. Sea U = ∑_{k=1}^{n} λ_{k}X_{k} ∈ Q[X_{1}, …, X_{n}] una forma lineal tal que U(P_{i}) ≠ U(P_{j}) para P_{i} ≠ P_{j}, entonces U(r̄^{(i)}) ≠ U(r̄^{(j)}) para n–uplas distintas r̄^{(i)}, r̄^{(j)}.

Sea m_{u} ∈ Q[ε][T] el polinomio mónico en T y de grado mínimo en T tal que m_{u}(U) ∈ I. Este polinomio existe y tiene grado en T acotado por d^{n}; esto es consecuencia de la Proposición 26. Existen g_{1}, …, g_{n} ∈ Q[ε, X_{1}, …, X_{n}] tal que

m_{u}(U) = ∑_{i=1}^{n} g_{i}F_{i} en Q[ε, X_{1}, …, X_{n}].

Evaluando esta igualdad en las n–uplas r̄^{(i)} para 1 ≤ i ≤ d^{n} se tiene

m_{u}(U)(r̄^{(i)}) = m_{u}(U((r̄^{(i)}))) = 0 en C[|ε^{1/d}|].

Dado que U((r̄^{(i)})) ≠ U((r̄^{(j)})) para n–uplas distintas se tienen d^{n} raíces de m_{u} en C[|ε^{1/d}|] y son todas por la cota de grado de m_{u}. Puesto que C[|ε^{1/d}|][T] es un dominio de factorización única, m_{u} se factoriza

m_{u} = ∏_{k=1}^{d^{n}}(T − U((r̄^{(k)}))) en C[|ε^{1/d}|][T].

La forma lineal U permite obtener una base del Q(ε)–espacio vectorial B′ := = Q(ε) ⊗_{Q[ε]} B de la siguiente manera: siendo u la imagen de U en B′, el conjunto de las potencias P := {1, u, …, u^{d^{n}−1}} es una base. Sean v_{1}, …, v_{n} ∈ Q(ε)[T] tal que X_{i} − v_{i}(u) ∈ B. El grado de cada polinomio v_{i} está acotado por d^{n} − 1. Consideramos la homotecia Q[ε] - lineal η en B correspondiente a multiplicar por u. Se sigue que la matriz M de η en la base P es la matriz compañera del polinomio m_{u}. Los autovalores de esta matriz son las raíces del polinomio m_{u}. Por lo tanto, existe una base P′ de la C(ε)^{∗} - álgebra C(ε)^{∗}[X_{1}, …, X_{n}]/(F_{1}, …, F_{n}) tal que la matriz M′ de la homotecia η tiene la forma

M′ = ( \begin{matrix}u(r̄^{(1)}) & 0 & … & 0 \\ 0 & u(r̄^{(2)}) & … & 0 \\ ⋮ & ⋮ & ... & ⋮ \\ 0 & 0 & … & u(r̄^{(d^{n})}) \end{matrix} )

Para 1 ≤ i ≤ n consideramos las homotecias η_{X_{i}} inducidas por la multiplicación por la clase de X_{i} en B. Sean M_{X_{i}} ∈ Q(ε)^{d^{n}×d^{n}} las matrices correspondientes a estas homotecias en la base P. Dado un polinomio H ∈ Q[ε, X_{1}, …, X_{n}], sea η_{H} la homotecia asociada y M_{H} la matriz de η_{H} en la base P. Puesto que B es un álgebra conmutativa, se sigue que las homotecias η_{X_{1}}, …, η_{X_{n}} y por lo tanto las matrices M_{X_{1}}, …, M_{X_{n}} conmutan entre sí. Esto implica que η_{H} = H(η_{X_{1}}, …, η_{X_{n}}), M_{H} = H(M_{X_{1}}, …, M_{X_{n}}). La igualdad de ideales I = (m_{u}(U), X_{1} −v_{1}(U), …, X_{n} −v_{n}(U)) en Q(ε)[X_{1}, …, X_{n}] implica las siguientes identidades:

η_{X_{1}} = v_{1}(η), …, η_{X_{n}} = v_{n}(η),
M_{X_{1}} = v_{1}(M), …, M_{X_{n}} = v_{n}(M).

Entonces, para cualquier polinomio H de Q[ε, X_{1}, …, X_{n}] vale que:

η_{H} = H(v_{1}(η), …, v_{n}(η)),
M_{H} = H(v_{1}(M), …, v_{n}(M)).

Por lo tanto, la matriz M_{H} es semejante a la matriz

M′_{H} = ( \begin{matrix}H(v_{1}(u(r̄^{(1)})), …, v_{n}(u(r̄^{(1)}))) & … & 0 \\ ⋮ & ... & ⋮ \\ 0 & … & H(v_{1}(u(r̄^{(d^{n})})), …, v_{n}(u(r̄^{(d^{n})}))) \end{matrix} )

= ( \begin{matrix}H(r̄^{(1)}) & … & 0 \\ ⋮ & ... & ⋮ \\ 0 & … & H(r̄^{(d^{n})}) \end{matrix} )

Sea q ∈ Q(ε)[T] el polinomio característico de M_{H} y μ ∈ Q(ε)[T] su polinomio minimal. Se tiene la siguiente observación:

Observación 30 Los polinomios q y μ pertenecen a Q[ε][T].

Demostración.– Sea m_{H} ∈ Q[ε][T] el polinomio mónico en T y de grado mínimo en T tal que m_{H}(H) ∈ I. Notamos que m_{H}(M_{H}) = M_{m_{H}(H)} = 0 y por lo tanto μ divide a m_{H}. Puesto que los polinomios m_{H} y μ son mónicos deducimos del Lema de Gauss que μ pertenece a Q[ε][T] y también q.

Sea q ∈ Q[ε][T] el polinomio característico de M_{H}. Por el teorema de Cayley-Hamilton se tiene que la matriz q(M_{H}) = M_{q(H)} es la matriz nula y, puesto que la matriz M_{q(H)} es la matriz de la homotecia η_{q(H)} en la base P, se deduce que el polinomio q(H) pertenece a I. Dado que B es un álgebra reducida, el polinomio minimal de M_{H} es el polinomio minimal de H en B. Hemos probado entonces la siguiente proposición:

Proposición 31 Con la notación anterior, sea q := ∏_{k=1}^{d^{n}}(T −H(r̄^{(k)})) en C(ε)^{∗}[T]. Entonces, q pertenece a Q[ε][T] y q(H) = 0 en B. Más aun, el polinomio m_{H} := q/MCD(q; q′) es el polinomio minimal buscado.

Idea de lo que sigue : Queremos encontrar las series de Puiseux de las variables (X_{1}, …, X_{n}) respecto de ε. Dado que la fibra correspondiente al cero está compuesta por un punto singular, no se puede aplicar el operador de Newton directamente. Entonces, a partir de la información que tenemos sobre las series de Puiseux buscadas ( Proposiciones 21 y 22) componemos el primer término de cada serie en los polinomios F_{1}, …, F_{n} y aplicamos el operador de Newton a los nuevos polinomios. Las series que se obtienen del nuevo sistema de polinomios permiten conocer las series originales.

Sean B_{1}, …, B_{n} indeterminadas sobre Q[ε, X_{1}, …, X_{n}], sean F̃_{1}, …, F̃_{n} ∈ Q[B_{1}, …, B_{n}]/(B_{1}^{d} − α_{1}, …, B_{n}^{d} − α_{n})(ε^{1/d})[X_{1}, …, X_{n}] definidos de la siguiente manera:

{ F̃_{1} = (F_{1}((X_{1} + B_{1})ε^{1/d}, …, (X_{n} + B_{n})ε^{1/d}))ε^{−1} ; ⋮ ; F̃_{n} = (F_{n}((X_{1} + B_{1})ε^{1/d}, …, (X_{n} + B_{n})ε^{1/d}))ε^{−1}  (6)

Los polinomios F̃_{1}, …, F̃_{n} ∈ Q[B_{1}, …, B_{n}]/(B_{1}^{d} − α_{1}, …, B_{n}^{d} − α_{n})(ε^{1/d})[X_{1}, …, X_{n}] “representan”, de alguna manera, a los polinomios F̃_{1}, …, F̃_{n} ∈ C[ε^{1/d}][X_{1}, …, X_{n}] definidos en la Proposición 22 pues las indeterminadas B_{1}, …, B_{n} son raíces d– ésimas de α_{1}, …, α_{n} respectivamente en el anillo Q[B_{1}, …, B_{n}]/(B_{1}^{d} − α_{1}, …, B_{n}^{d} − α_{n}).

Observación 32 Los polinomios F̃_{1}, …, F̃_{n} pertenecen a Q[B_{1}, …, B_{n}]/(B_{1}^{d} − α_{1}, …, B_{n}^{d} − α_{n})[ε^{1/d}][X_{1}, …, X_{n}].

Demostración.– Los polinomios están en Q[B_{1}, …, B_{n}]/(B_{1}^{d} − α_{1}, …, B_{n}^{d} − α_{n})[ε^{1/d}][X_{1}, …, X_{n}] pues F̃_{i} = (F_{i}((X_{1} + B_{1})ε^{1/d}, …, (X_{n} + B_{n})ε^{1/d}))ε^{−1} = (((X_{i} + B_{i})ε^{1/d})^{d} − εG_{i}((X_{1} + B_{1})ε^{1/d}, …, (X_{n}+B_{n})ε^{1/d})))ε^{−1} = (X_{i}+B_{i})^{d}−G_{i}((X_{1}+B_{1})ε^{1/d}, …, (X_{n}+B_{n})ε^{1/d})).

Definición 33 Sea R el anillo semilocal Q[B_{1}, …, B_{n}]/(B_{1}^{d}−α_{1}, …, B_{n}^{d}−α_{n})[|ε^{1/d}|].

Un elemento f de R es una serie formal en ε^{1/d}, con coeficientes en Q[B_{1}, …, B_{n}]/(B_{1}^{d} − α_{1}, …, B_{n}^{d} − α_{n}). f se escribe entonces ∑_{k=k_{0}}^{∞} a_{k}ε^{k/d} donde k_{0} ≥ 0 y a_{k_{0}} ≠ 0. Se define el orden de f como el número racional k_{0}/d. Via la inclusión Q[B_{1}, …, B_{n}]/(B_{1}^{d} − α_{1}, …, B_{n}^{d} − α_{n})[ε^{1/d}] ↪ R se puede pensar a los polinomios F̃_{i} en R[X_{1}, …, X_{n}].

Observación 34 Sea g ∈ R inversible, sea f ∈ R tal que O(f − g) > 0, entonces f es inversible en R.

Demostración.– f tiene una escritura de tipo ∑_{k=0}^{∞} a_{k}ε^{k/d} donde a_{k} ∈ Q[B_{1}, …, B_{n}]/(B_{1}^{d} − α_{1}, …, B_{n}^{d} − α_{n}). Dado que O(f − g) > 0, resulta a_{0} el término constante de la escritura de g como serie de potencias de ε^{1/d}. Puesto que g es inversible en R, a_{0} es inversible en Q[B_{1}, …, B_{n}]/(B_{1}^{d} − α_{1}, …, B_{n}^{d} − α_{n}). Definimos b_{k} recursivamente: b_{0} = a_{0}^{−1} b_{k} = −a_{0}^{−1} ∑_{j=0}^{k−1} a_{k−j}b_{j} si k ≥ 1 Se prueba inductivamente que b_{k} ∈ Q[B_{1}, …, B_{n}]/(B_{1}^{d} − α_{1}, …, B_{n}^{d} − α_{n}) y que ∑_{k=0}^{∞} b_{k}ε^{k/d} es el inverso de f.

Observación 35 El vector 0 = (0, …, 0) ∈ R^{n} verifica:

i) O(F̃_{i}(0)) ≥ 1/d para 1 ≤ i ≤ n.

ii) det(DF̃)(0) es inversible en R y por lo tanto D(F̃)(0) es inversible en R^{n×n}.

Demostración.– El polinomio F̃_{i}, evaluado en 0 resulta:

F̃_{i}(0) = (F_{i}((0 + B_{1})ε^{1/d}, …, (0 + B_{n})ε^{1/d}))ε^{−1} =
= (((0 + B_{i})ε^{1/d})^{d} − εG_{i}((0 + B_{1})ε^{1/d}, …, (0 + B_{n})ε^{1/d}))ε^{−1} =
= (B_{i})^{d} − G_{i}((B_{1})ε^{1/d}, …, (B_{n})ε^{1/d})

Dado que B_{i}^{d} = α_{i} y que O(G_{i}((B_{1})ε^{1/d}, …, (B_{n})ε^{1/d})−α_{i}) ≥ 1/d, se tiene la primer afirmación. La derivada parcial de F̃_{i} respecto de X_{j} es

\frac{∂}{∂X_{j}} F̃_{i} = \frac{∂}{∂X_{j}} (X_{i} + B_{i})^{d} − \frac{∂}{∂X_{j}} G_{i}((X_{1} + B_{1})ε^{1/d}, …, (X_{n} + B_{n})ε^{1/d}) =

= δ_{i,j}d(X_{i} + B_{i})^{d−1} − \frac{∂}{∂X_{j}} G_{i}(B_{1}ε^{1/d}, …, B_{n}ε^{1/d})ε^{1/d},

donde δ_{i,j} vale 1 si i = j y 0 en otro caso. Evaluada en 0 resulta

\frac{∂}{∂X_{j}} F̃_{i}(0) = δ_{i,j}dB_{i}^{d−1} − \frac{∂}{∂X_{j}} G_{i}(B_{1}, …, B_{n})ε^{1/d}

En particular se tiene que O(\frac{∂}{∂X_{j}} F̃_{i}(0)) = 0 si i = j y O(\frac{∂}{∂X_{j}} F̃_{i}(0)) ≥ 1/d si i ≠ j y por lo tanto

O(det(DF̃)(0) − d^{n} ∏_{i=1}^{n} B_{i}^{d−1}) ≥ 1/d.  (7)

d^{n} ∏_{i=1}^{n} B_{i}^{d−1} es inversible en R pues B_{i} es inversible en R para todo i, y se sigue de la Observación 34 que det(DF̃)(0) es inversible en R. Esto implica que D(F̃)(0) es inversible en R^{n×n} y su inversa es la matriz

(det(DF̃))(0))^{−1}Adj(D(F̃))(0).

4 Operador de Newton sin divisiones

Recordamos la definición de los polinomios F̃_{1}, …, F̃_{n} ∈ Q[B_{1}, …, B_{n}]/(B_{1}^{d}−α_{1}, …, B_{n}^{d}−α_{n})[ε^{1/d}][X_{1}, …, X_{n}] dada en la sección anterior,

{ F̃_{1} = (F_{1}((X_{1} + B_{1})ε^{1/d}, …, (X_{n} + B_{n})ε^{1/d}))ε^{−1} ; ⋮ ; F̃_{n} = (F_{n}((X_{1} + B_{1})ε^{1/d}, …, (X_{n} + B_{n})ε^{1/d}))ε^{−1}

Recordamos también que definimos el anillo R := Q[B_{1}, …, B_{n}]/(B_{1}^{d} − α_{1}, …, B_{n}^{d} − α_{n})[|ε^{1/d}|] y que podemos pensar a los polinomios F̃_{1}, …, F̃_{n} en R[X_{1}, …, X_{n}]. Sea F̃ := (F̃_{1}, …, F̃_{n}) y sea D(F̃) := (\frac{∂_{F_{i}}}{∂X_{j}})_{1≤i,j≤n} la matriz jacobiana de los polinomios

F̃_{1}, …, F̃_{n}. Suponiendo que esta matriz es regular y considerando los polinomios F̃_{1}, …, F̃_{n} como funciones racionales en (X_{1}, …, X_{n}), se define el siguiente operador de Newton–Hensel:

N_{F}(X_{1}, …, X_{n}) := ( X_{1} ; ⋮ ; X_{n} ) − D(F̃)^{−1} ( F̃_{1}(X_{1}, …, X_{n}) ; ⋮ ; F̃_{n}(X_{1}, …, X_{n}) ) .

Se tiene la siguiente versión del Lema de Hensel ([Mat97]):

Lema 36 Existen únicas series de potencias R_{1}, …, R_{n} en R que verifican las siguientes condiciones:

• Para i = 1, …, n vale la siguiente identidad en R:

F̃_{i}(R_{1}, …, R_{n}) = 0.

• Para i = 1, …, n vale que O(R_{i}) ≥ 1/d.

Demostración.– Se define la siguiente sucesión en R^{n}:

R^{(0)} := (0, …, 0)

R^{(N+1)} := N_{F}(R^{(N)})^{t} para N ≥ 0

donde A^{t} denota la matriz transpuesta de A. Obsérvese que de la definición de R^{(N)}, por medio de un argumento inductivo se deduce que cada R_{j}^{(N)} representa una función racional de Q(ε^{1/d}, X_{1}, …, X_{n}). Se nota por M el ideal M := (ε^{1/d}) generado por ε^{1/d} en R. Entonces las siguientes afirmaciones son válidas para todo N ∈ IN:

i) F̃_{i}(R^{(N)})) ∈ M^{2^{N}} para 1 ≤ i ≤ n.

ii) det(D(F̃))(R^{(N)}) es un elemento inversible de R y por lo tanto R^{(N+1)} está bien definido.

Estas afirmaciones se demuestran por inducción en N. En el caso N = 0, las afirmaciones i) e ii) se probaron en la Observación 35. En el caso general, suponiendo ambas afirmaciones ciertas para el caso N, veamos que se verifican para el caso N +1. Sean Y_{1}, …, Y_{n} nuevas indeterminadas. A partir de un desarrollo formal de Taylor de los polinomios F̃_{1}, …, F̃_{n} en torno a Y_{1}, …, Y_{n} se obtiene la siguiente identidad en R[X_{1}, …, X_{n}, Y_{1}, …, Y_{n}]:

\begin{matrix}F̃_{i}(X_{1}, …, X_{n}) = F̃_{i}(Y_{1}, …, Y_{n}) + ∑_{j=1}^{n} \frac{∂_{F_{i}}}{∂X_{j}} (Y_{1}, …, Y_{n}).(X_{j} − Y_{j}) \\ módulo (X_{1} − Y_{1}, …, X_{n} − Y_{n})^{2} \end{matrix}  (8)

para i = 1, …, n, donde (X_{1} − Y_{1}, …, X_{n} − Y_{n}) denota el ideal generado por los polinomios X_{1} − Y_{1}, …, X_{n} − Y_{n} en R[X_{1}, …, X_{n}, Y_{1}, …, Y_{n}]. Reemplazando en la ecuación (8) las variables X_{1}, …, X_{n} por R_{1}^{(N+1)}, …, R_{n}^{(N+1)} e Y_{1}, …, Y_{n} por R_{1}^{(N)}, …, R_{n}^{(N)}, se obtiene la siguiente identidad en R:

\begin{matrix}F̃_{i}(R^{(N+1)}) = F̃_{i}(R^{(N)}) + ∑_{j=1}^{n} \frac{∂_{F_{i}}}{∂X_{j}} (R^{(N)}).(R_{j}^{(N+1)} − R_{j}^{(N)}) \\ módulo (R_{1}^{(N+1)} − R_{1}^{(N)}, …, R_{n}^{(N+1)} − R_{n}^{(N)})^{2} \end{matrix}  (9)

De la definición de R^{(N)} resulta:

R^{(N+1)} − R^{(N)} = −D(F̃)^{−1}(R^{(N)}). ( F̃_{1}(R^{(N)}) ; ⋮ ; F̃_{n}(R^{(N)}) )

En consecuencia, multiplicando ambos miembros de esta identidad por el vector (\frac{∂_{F_{i}}}{∂X_{1}} (R^{(N)}), …, \frac{∂_{F_{i}}}{∂X_{n}} (R^{(N)})), que constituye la i–ésima fila de la matriz D(F̃)(R^{(N)}), se tiene la siguiente ecuación:

(\frac{∂F̃_{i}}{∂X_{1}} (R^{(N)}), …, \frac{∂F̃_{i}}{∂X_{n}} (R^{(N)})).(R^{(N+1)} − R^{(N)})^{t} =

(\frac{∂F̃_{i}}{∂X_{1}} (R^{(N)}), …, \frac{∂F̃_{i}}{∂X_{n}} (R^{(N)})).(−D(F̃)^{−1}(R^{(N)})). ( F̃_{1}(R^{(N)}) ; ⋮ ; F̃_{n}(R^{(N)}) ) =

= −(0, …, \overbrace{1}^{i}, 0, …, 0). ( F̃_{1}(R^{(N)}) ; ⋮ ; F̃_{n}(R^{(N)}) ) = −F̃_{i}(R^{(N)})

Por lo tanto, reemplazando esta última identidad en (9) se obtiene:

F̃_{i}(R^{(N+1)}) = F̃_{i}(R^{(N)})+

+(\frac{∂F̃_{i}}{∂X_{1}} (R^{(N)}), …, \frac{∂F̃_{i}}{∂X_{n}} (R^{(N)})).(−D(F̃)^{−1}(R^{(N)})). ( F̃_{1}(R^{(N)}) ; ⋮ ; F̃_{n}(R^{(N)}) ) =

= F̃_{i}(R^{(N)}) − F̃_{i}(R^{(N)}) = 0
módulo (R_{1}^{(N+1)} − R_{1}^{(N)}, …, R_{n}^{(N+1)} − R_{n}^{(N)})^{2}

de donde se deduce que

F̃_{i}(R^{(N+1)}) ∈ (R_{1}^{(N+1)} − R_{1}^{(N)}, …, R_{n}^{(N+1)} − R_{n}^{(N)})^{2}

para i = 1, …, n. Ahora bien, como

(R^{(N+1)} − R^{(N)}))^{t} = −D(F̃)^{−1}(R^{(N)}). ( F̃_{1}(R^{(N)}) ; ⋮ ; F̃_{n}(R^{(N)}) )

y F̃_{i}(R^{(N)}) ∈ M^{2^{N}} para i = 1, …, n por hipótesis inductiva, resulta entonces que

(R_{1}^{(N+1)} − R_{1}^{(N)}, …, R_{n}^{(N+1)} − R_{n}^{(N)})^{2} ⊆ (M^{2^{N}})^{2} = M^{2^{N+1}}

lo que demuestra i). Con respecto a la segunda afirmación, realizando un desarrollo de Taylor formal del polinomio det(D(F̃)) como en (8), se obtiene la siguiente expresión:

det(D(F̃))(X_{1}, …, X_{n}) = det(D(F̃))(Y_{1}, …, Y_{n})+

+ ∑_{j=1}^{n} \frac{∂ det(D(F̃))}{∂X_{j}}(Y_{1}, …, Y_{n}).(X_{j} − Y_{j}) módulo (X_{1} − Y_{1}, …, X_{n} − Y_{n})^{2} (10)

Si se reemplaza en esta ecuación, del mismo modo que en (9), las variables X_{1}, …, X_{n} por R_{1}^{(N+1)}, …, R_{n}^{(N+1)} y las variables Y_{1}, …, Y_{n} por R_{1}^{(N)}, …, R_{n}^{(N)} se obtiene la siguiente identidad:

det(D(F̃))(R^{(N+1)}) = det(D(F̃))(R^{(N)})+

+ ∑_{j=1}^{n} \frac{∂ det(D(F̃))}{∂X_{j}}(R^{(N)}).(R_{j}^{(N+1)} − R_{j}^{(N)})

módulo (R_{1}^{(N+1)} − R_{1}^{(N)}, …, R_{n}^{(N+1)} − R_{n}^{(N)})^{2}

Dado que se verifica que R_{j}^{(N+1)} − R_{j}^{(N)} ∈ M^{2^{N}} ⊆ M para j = 1, …, n y det(D(F̃))(R^{(N)}) es inversible en R por hipótesis, se deduce de la observación (34) que det(D(F̃))(R^{(N+1)}) también es inversible en R. De las afirmaciones i) e ii) se desprende que la sucesión {R_{j}^{(N)}}_{N∈IN} converge en R a una serie de potencias R_{j} para j = 1, …, n. Estas son las series de potencias cuya existencia afirma el enunciado del Lema. Denótese por R el vector de series de potencias R := (R_{1}, …, R_{n}). En primer lugar, dado que R_{j}^{(N+1)} − R_{j}^{(N)} ∈ M^{2^{N}} para todo N ∈ IN, se deduce que

R_{j} ≡ R_{j}^{(N)} módulo M^{2^{N}} para todo N ∈ IN  (11)

Combinando esta observación con la ecuación (8), se tiene que

F̃_{i}(R) = F̃_{i}(R^{(N)}) + D(F̃)(R^{(N)}). ( R_{1} − R_{1}^{(N)} ; ⋮ ; R_{n} − R_{n}^{(N)} ) módulo M^{2^{N}}

para i = 1, …, n, de donde se deduce que F̃_{i}(R) ∈ M^{2^{N}} para todo N ∈ IN. Luego

F̃_{i}(R) = 0 en R

para i = 1, …, n, que era lo que se quería demostrar. Por otra parte, de (11) y de que (R_{1}^{(0)}, …, R_{n}^{(0)}) = (0, …, 0) se sigue que O(R) ≥ 1/d. En cuanto a la unicidad, suponiendo que existiera otra solución distinta R̃ = (R̃_{1}, …, R̃_{n}) en las condiciones del enunciado, es decir que se anula en F̃ y para i = 1, …, n vale que O(R̃_{i}) ≥ 1/d, aplicando una vez más la expresión (8) se obtiene:

F̃_{i}(R) = F̃_{i}(R̃) + D(F̃)(R̃). ( R_{1} − R̃_{1} ; ⋮ ; R_{n} − R̃_{n} )

módulo (R_{1} − R̃_{1}, …, R_{n} − R̃_{n})^{2}

Como F̃_{i}(R) = F̃_{i}(R̃) = 0, se tiene:

( 0 ⋮ 0 ) = D(F̃)(R̃). ( R_{1} − R̃_{1} ; ⋮ ; R_{n} − R̃_{n} )

módulo (R_{1} − R̃_{1}, …, R_{n} − R̃_{n})^{2}  (12)

Puesto que para i = 1, …, n vale que O(R_{i}) ≥ 1/d, O(R̃_{i}) ≥ 1/d, se sigue que R_{i} − R̃_{i} ∈ M para i = 1, …, n. Reemplazando en la ecuación (10) las variables X_{1}, …, X_{n} por R_{1}, …, R_{n} y las variables Y_{1}, …, Y_{n} por R̃_{1}, …, R̃_{n} se obtiene la siguiente identidad:

det(D(F̃))(R) = det(D(F̃))(R̃)+

+ ∑_{j=1}^{n} \frac{∂ det(D(F̃))}{∂X_{j}}(R̃).(R_{j} − R̃_{j})

módulo (R_{1} − R̃_{1}, …, R_{n} − R̃_{n})^{2}

Puesto que hemos probado que det(D(F̃))(R) ∉ M, se sigue de esta última ecuación y del hecho que R_{i} − R̃_{i} ∈ M para i = 1, …, n que det(D(F̃))(R̃) ∉ M. De ésto y de la ecuación (12) se deduce entonces que R_{i} − R̃_{i} ∈ M^{2} para i = 1, …, n. Utilizando la ecuación (12) se demuestra inductivamente que R_{i} − R̃_{i} ∈ M^{2^{N}} para todo N ∈ IN, i = 1, …, n, lo que a su vez implica que R_{i} = R̃_{i} para i = 1, …, n, como se quería demostrar.

Gracias a la cota del grado total de m_{H} obtenida en la Proposición 28 y al “orden” de convergencia de la sucesión R^{N} que se obtiene de la ecuación (11), será suficiente calcular hasta la ⌈log(deg(H)) + (n + 1) log(d)⌉– ésima iteración del operador de Newton. Sea A = Q[B_{1}, …, B_{n}, ε^{1/d}], sea K su cuerpo de fracciones. Se puede pensar al operador de Newton definido para funciones de K(X_{1}, …, X_{n}). Por lo tanto, para cualquier número natural k ∈ IN, existen polinomios g_{1}^{(k)}, …, g_{n}^{(k)}, h^{(k)} ∈ A[X_{1}, …, X_{n}] tales que

N (k) ; _{F} = (\frac{g_{1}^{(k)}}{h^{(k)}} , …, \frac{g_{n}^{(k)}}{h^{(k)}} ) .

El Lema siguiente muestra la existencia de un esquema de evaluación que calcula tales polinomios sin utilizar divisiones.

Lema 37 Supongamos que los polinomios F̃_{1}, …, F̃_{n} vienen dados por un circuito aritmético β en espacio S y tiempo T . Entonces, existe un circuito aritmético en espacio O(Sn) y tiempo O((T n + n^{4})k) que, utilizando los mismos parámetros que β, computa los numeradores g_{1}^{(k)}, …, g_{n}^{(k)} y un denominador (distinto de cero) h^{(k)}

para N (k) ; _{F}.

Más aún, el denominador h^{(k)} evaluado en 0, …, 0 es un elemento inversible del anillo R = Q[B_{1}, …, B_{n}]/(B_{1}^{d} − α_{1}, …, B_{n}^{d} − α_{n})[|ε^{1/d}|].

Demostración.– Calculamos las n^{2} entradas de la matriz Jacobiana D(F̃) espacio S + 1 y tiempo (2n + 1)T según el Lema (3). Sea Adj(D(F̃)) = (a_{i,j})_{1≤i,j≤n} la matriz adjunta de D(F̃). Tanto Adj(D(F̃)) como el determinante de la matriz jacobiana D(F̃) se evalúan mediante una adaptación del algoritmo de Samuelson para el cálculo de determinantes (ver [FF63] o [Abd97]) en espacio O(log n + S) y tiempo O(n^{5} + nT ). Puesto que D(F̃)^{−1} = det(DF̃))^{−1}Adj(D(F̃)), el operador N_{F} se puede escribir como

N_{F} = \frac{det(DF̃)) ( X_{1} ; ⋮ ; X_{n} ) − Adj(D(F̃)) ( F̃_{1}(X_{1}, …, X_{n}) ; ⋮ ; F̃_{n}(X_{1}, …, X_{n}) )}{det(DF̃)}  (13)

Los coeficientes a_{i,j} de la matriz Adj(D(F̃)) son polinomios en A[X_{1}, …, X_{n}] con grado acotado por (n − 1)(d − 1). Por otro lado, es evidente que el determinante de la matriz jacobiana det(DF̃) es un polinomio en A[X_{1}, …, X_{n}] cuyo grado está acotado superiormente por n(d − 1). Definimos ahora, para 1 ≤ i ≤ n, los siguientes polinomios de A[X_{1}, …, X_{n}]

g_{i} := det(DF̃)X_{i} − ∑_{j=1}^{n} a_{i,j}F̃_{j}.

Veamos, en primer lugar, que el grado total de g_{i} está acotado por v := n(d − 1) + 1. Para ello, basta escribir el desarrollo de det(DF̃) por los elementos de la columna i–ésima de DF̃, es decir, det(DF̃) = ∑_{j=1}^{n} a_{i,j} \frac{∂_{F_{j}}}{∂X_{i}}. Así,

g_{i} = ∑_{j=1}^{n} a_{i,j}(\frac{∂F̃_{j}}{∂X_{i}} .X_{i} − F̃_{j}).

Esta identidad demuestra que, efectivamente, el grado de g_{i} es menor o igual que v. Introducimos una nueva variable X_{0} y sean (^{h}g_{i})(X_{0}, X_{1}, …, X_{n}) ∈ A[X_{0}, …, X_{n}] y (^{h}det(DF̃))(X_{0}, …, X_{n}) ∈ A[X_{0}, …, X_{n}] los polinomios homogeneizados de g_{i} y del determinante jacobiano, det(DF̃), con respecto a la variable X_{0}.

Sean ahora:

• g̃_{i}(X_{0}, …, X_{n}) := X_{0}^{v−deg(g_{i})}.(^{h}g_{i}),

• h̃(X_{0}, …, X_{n}) := X_{0}^{v−deg(det(D_{F}))}.(^{h}det(DF̃)).

Estos polinomios pertenecen a A[X_{0}, …, X_{n}]. De acuerdo al Lema (4), existe un esquema de evaluación sin divisiones en espacio O(log n + S) y tiempo O(d^{2}(n^{7} + n^{3}T )) que representa a los polinomios g̃_{1}, …, g̃_{n}, h̃. Por otro lado, definimos, de manera recursiva, los polinomios siguientes:

• para k = 1 y 1 ≤ i ≤ n, sea

g_{i}^{(1)} := g̃_{i}(1, X_{1}, …, X_{n}) y

h^{(1)} := h̃(1, X_{1}, …, X_{n}),

• para k ≥ 2 y 1 ≤ i ≤ n, sea

g_{i}^{(k)} := g̃_{i}(h̃^{(k−1)}, g̃_{1}^{(k−1)}, …, g̃_{n}^{(k−1)}) y

h^{(k)} := h̃(h^{(k−1)}, g_{1}^{(k−1)}, …, g_{n}^{(k−1)}).

Probaremos por inducción en k que h^{(k)}(0, …, 0) es inversible en R y que g_{1}^{(k)}, …, g_{n}^{(k)}, h^{(k)} son los numeradores y el denominador de N (k) ; _{F}.

Claramente g_{1}^{(1)}, …, g_{n}^{(1)}, h^{(1)} son los numeradores y el denominador de N (1) ; _{F}. De acuerdo a la ecuación (7) de la Observación 35, el polinomio h^{(1)} evaluado en (0, …, 0) verifica la siguiente relación de congruencia:

h^{(1)}(0, …, 0) ≡ d^{n} ∏_{i=1}^{n} B_{i}^{d−1} módulo ε^{1/d}

y puesto que B_{i} es inversible en R para 1 ≤ i ≤ n, h^{(1)}(0, …, 0) resulta inversible en R. Es claro que los polinomios g_{1}^{(k)}, …, g_{n}^{(k)}, h^{(k)} pertenecen a A[X_{1}, …, X_{n}] = = Q[B_{1}, …, B_{n}, ε^{1/d}, X_{1}, …, X_{n}]. Además los polinomios g_{1}^{(k)}, …, g_{n}^{(k)} y el polinomio h^{(k)} son, respectivamente, numeradores y denominador del operador de Newton– Hensel iterado k veces:

\frac{g_{i}^{(k)}}{h^{(k)}} = \frac{g_{i}(\frac{g_{1}^{(k−1)}}{h^{(k−1)}} , …, \frac{g_{n}^{(k−1)}}{h^{(k−1)}} )}{det(DF̃)(\frac{g_{1}^{(k−1)}}{h^{(k−1)}} , …, \frac{g_{n}^{(k−1)}}{h^{(k−1)}} )} = \frac{(h^{(k−1)})^{(v)}}{(h^{(k−1)})^{(v)}} .\frac{g_{i}(\frac{g_{1}^{(k−1)}}{h^{(k−1)}} , …, \frac{g_{n}^{(k−1)}}{h^{(k−1)}} )}{det(DF̃)(\frac{g_{1}^{(k−1)}}{h^{(k−1)}} , …, \frac{g_{n}^{(k−1)}}{h^{(k−1)}} )} =

= \frac{(h^{(k−1)})^{(v−deg(g_{i}))}.(^{h}g_{i})(h^{(k−1)}, g_{1}^{(k−1)}, …, g_{n}^{(k−1)})}{(h^{(k−1)})^{(v−deg(det(D_{F})))}.(^{h}det(DF̃))(h^{(k−1)}, g_{1}^{(k−1)}, …, g_{n}^{(k−1)})} =

= \frac{g̃_{i}(h^{(k−1)}, g_{1}^{(k−1)}, …, g_{n}^{(k−1)})}{h̃(h^{(k−1)}, g_{1}^{(k−1)}, …, g_{n}^{(k−1)})}.

Por otra parte, supongamos que el polinomio h^{(k−1)} evaluado en (0, …, 0) es inversible en R. El polinomio h^{(k)} se define

h^{(k)} := h̃(h^{(k−1)}, g_{1}^{(k−1)}, …, g_{n}^{(k−1)}) =

= (h^{(k−1)})^{v−deg(det(D_{F}))}.(^{h}det(DF̃))(h^{(k−1)}, g_{1}^{(k−1)}, …, g_{n}^{(k−1)}).

Notamos 0 al vector (0, …, 0). Puesto que h^{(k−1)}(0) es inversible en R se tienen las siguientes igualdades en R:

h^{(k)}(0) = (h^{(k−1)})^{v−deg(det(D_{F}))}(0).(^{h}det(DF̃)(h^{(k−1)}(0), g_{1}^{(k−1)}(0), …, g_{n}^{(k−1)}(0))) =

= (h^{(k−1)})^{v}(0) det(DF̃)(\frac{g_{1}^{(k−1)}(0)}{h^{(k−1)}(0)}, …, \frac{g_{n}^{(k−1)}(0)}{h^{(k−1)}(0)})  (14)

Resta demostrar que det(DF̃)(\frac{g_{1}^{(k−1)}(0)}{h^{(k−1)}(0)}, …, \frac{g_{n}^{(k−1)}(0)}{h^{(k−1)}(0)}) es inversible en R^{n}. Ahora

bien, por hipótesis inductiva la n–upla (\frac{g_{1}^{(k−1)}(0)}{h^{(k−1)}(0)}, …, \frac{g_{n}^{(k−1)}(0)}{h^{(k−1)}(0)}) ∈ R^{n} es igual a R^{(k−1)}, donde R^{(N)} ∈ R^{n} se definía en el Lema 36 de la siguiente manera :

R^{(0)} := (0, …, 0)

R^{(N+1)} := N_{F}(R^{(N)})^{t} para N ≥ 0.

En ese Lema se prueba que

det(D(F̃))(R^{(k)}) = det(D(F̃))(R^{(k−1)})+

+ ∑_{j=1}^{n} \frac{∂ det(D(F̃))}{∂X_{j}}(R^{(k−1)}).(R_{j}^{(k)} − R_{j}^{(k−1)})

módulo (R_{1}^{(k)} − R_{1}^{(k−1)}, …, R_{n}^{(k)} − R_{n}^{(k−1)})^{2}

Puesto que R_{j}^{N+1} ≡ R_{j}^{(N)} módulo ε^{1/d} para 1 ≤ N, 1 ≤ j ≤ n según la ecuación (11) del Lema 36, se deduce que

det(D(F̃))(R^{(k)}) ≡ det(D(F̃))(R^{(1)}) módulo ε^{1/d}

en R. Dado que det(D(F̃))(R^{(1)}) es inversible en R, se tiene que det(D(F̃))(R^{(k)}) también lo es. Retomando la ecuación (14), se prueba la inversibilidad de h^{(k)}(0) en R que es lo que se quería demostrar.

Para evaluar tales polinomios, no es preciso más que iterar k veces el esquema de evaluación anteriormente descrito. De tal forma, se obtienen las complejidades que se establecen en el enunciado del Lema.

El operador de Newton definido en el Lema anterior es aplicable a w-múltiplos de los polinomios F̃_{1}, …, F̃_{n} donde w ∈ Q[ε^{1/d}] es un polinomio no nulo. En nuestro algoritmo nos será útil poder aplicar el circuito aritmético anterior a los polinomios εF̃_{1}, …, εF̃_{n}. Para ello necesitamos la siguiente observación:

Observación 38 Bajo las hipótesis y notación anteriores, sean g_{1}^{(k)}, …, g_{n}^{(k)}, h^{(k)} los polinomios que se obtienen en el circuito aritmético descripto en el Lema anterior. Sea w ∈ Q[ε^{1/d}] un polinomio no nulo, y supongamos que los polinomios w, F̃_{1}, …, F̃_{n} vienen dados por un circuito aritmético β en espacio S y tiempo T . Entonces, el circuito aritmético descripto en el Lema anterior es aplicable a los polinomios wF̃_{1}, …, wF̃_{n} y los numeradores g_{1}^{(w,k)}, …, g_{n}^{(w,k)} y el denominador h^{(w,k)} obtenidos son w̃_{k}-múltiplos de los polinomios g_{1}^{(k)}, …, g_{n}^{(k)}, h^{(k)}, donde w̃_{k} es una potencia de w. Vale la siguiente igualdad en Q(B_{1}, …, B_{n}, ε^{1/d}, X_{1}, …, X_{n}) :

N (k) ; _{F} = (\frac{g_{1}^{(k)}}{h^{(k)}} , …, \frac{g_{n}^{(k)}}{h^{(k)}} ) = (\frac{w̃_{k}g_{1}^{(k)}}{w̃_{k}h^{(k)}} , …, \frac{w̃_{k}g_{n}^{(k)}}{w̃_{k}h^{(k)}} ) = (\frac{g_{1}^{(w,k)}}{h^{(w,k)}} , …, \frac{g_{n}^{(w,k)}}{h^{(w,k)}} ).

El nuevo circuito aritmético utiliza espacio O(Sn) y tiempo O((T n + n^{4})k).

Demostración.– Se prueba por inducción en k, el número de iteraciones del operador de Newton que realiza el circuito aritmético. Notamos D(wF̃) ∈ A[X_{1}, …, X_{n}]^{n×n} a la matriz jacobiana correspondiente a los polinomios wF̃_{1}, …, wF̃_{n}, sea Adj(D(wF̃)) = (a_{i,j}^{(w)})_{1≤i,j≤n} la matriz adjunta de D(wF̃). Recordamos que Adj(D(F̃)) = (a_{i,j})_{1≤i,j≤n} es la matriz adjunta de D(F̃). Puesto que vale la siguiente igualdad entre las matrices jacobianas D(wF̃) = wD(F̃), por propiedad del determinante se tienen las siguientes igualdades:

i) (a_{i,j}^{(w)})_{1≤i,j≤n} = Adj(D(wF̃)) = w^{n−1}Adj(D(F̃)) = w^{n−1}(a_{i,j})_{1≤i,j≤n}. ii) det(D(wF̃)) = w^{n} det(DF̃).

Recordamos la definición de los siguientes polinomios de A[X_{1}, …, X_{n}], para 1 ≤ i ≤ n:

g_{i} := det(DF̃)X_{i} − ∑_{j=1}^{n} a_{i,j}F̃_{j}.

Notamos g_{i}^{(w)} a estos polinomios calculados a partir de wF̃, es decir g_{i}^{(w)} := det(D(wF̃))X_{i} − ∑_{j=1}^{n} a_{i,j}^{(w)}wF̃_{j}.

A partir de las igualdades i) e ii) se tienen las siguientes igualdades: g_{i}^{(w)} := det(D(wF̃))X_{i} − ∑_{j=1}^{n} a_{i,j}^{(w)}wF̃_{j} = w^{n} det(DF̃)X_{i} − w^{n−1}w ∑_{j=1}^{n} a_{i,j}F̃_{j} = w^{n}(det(DF̃)X_{i} − ∑_{j=1}^{n} a_{i,j}F̃_{j}) = w^{n}g_{i}. Recordamos que v := n(d−1)+1 es una cota superior de los grados de los polinomios g_{i} y por lo tanto también de g_{i}^{(w)}. Introduciendo una nueva variable X_{0}, recordamos que (^{h}g_{i})(X_{0}, X_{1}, …, X_{n}) ∈ A[X_{0}, …, X_{n}] y (^{h}det)(DF̃)(X_{0}, …, X_{n}) ∈ A[X_{0}, …, X_{n}] son los polinomios homogeneizados de g_{i} y del determinante jacobiano, det(DF̃), con respecto a la variable X_{0}.

Recordamos la definición de los polinomios g̃_{i}, h̃:

• g̃_{i}(X_{0}, …, X_{n}) := X_{0}^{v−deg(g_{i})}.(^{h}g_{i}),

• h̃(X_{0}, …, X_{n}) := X_{0}^{v−deg(det(D_{F}))}.(^{h}det(DF̃)).

Estos polinomios, calculados a partir de wF̃, resultan:

• g̃_{i}^{(w)}(X_{0}, …, X_{n}) := X_{0}^{v−deg(g_{i})}.(^{h}g_{i}^{(w)}),

• h̃^{(w)}(X_{0}, …, X_{n}) := X_{0}^{v−deg(det(D_{F}))}.(^{h}det(D(wF̃))).

De las igualdades demostradas anteriormente se tienen las siguientes identidades:

g̃_{i}^{(w)} = X_{0}^{v−deg(g_{i})}.w^{n}.(^{h}g_{i}),

h̃^{(w)} = X_{0}^{v−deg(det(D_{F}))}.w^{n}.(^{h}det(DF̃)).

Por último en el Lema anterior se definían de manera recursiva los polinomios siguientes:

• para k = 1 y 1 ≤ i ≤ n:

g_{i}^{(1)} := g̃_{i}(1, X_{1}, …, X_{n}) y

h^{(1)} := h̃(1, X_{1}, …, X_{n}),

• para k ≥ 2 y 1 ≤ i ≤ n:

g_{i}^{(k)} := g̃_{i}(h^{(k−1)}, g_{1}^{(k−1)}, …, g_{n}^{(k−1)}) y

h^{(k)} := h̃(h^{(k−1)}, g_{1}^{(k−1)}, …, g_{n}^{(k−1)}).

Recordamos que los polinomios g_{1}^{(k)}, …, g_{n}^{(k)} y que el polinomio h^{(k)} son, respectivamente, numeradores y denominador del operador de Newton–Hensel iterado k veces, aplicado a los polinomios F̃_{1}, …, F̃_{n}. Los polinomios g_{i}^{(k)}, h^{(k)}, calculados a partir de wF̃, resultan:

Para k = 1 y 1 ≤ i ≤ n:

g_{i}^{(w,1)} := g̃_{i}^{(w)}(1, X_{1}, …, X_{n}) = w^{n}g̃_{i}(1, X_{1}, …, X_{n}) = w^{n}g_{i}^{(1)} y h^{(w,1)} := h̃^{(w)}(1, X_{1}, …, X_{n}) = w^{n}h̃(1, X_{1}, …, X_{n}) = w^{n}h^{(1)}.

Entonces la observación es cierta para el caso k = 1, donde w̃_{1} resulta igual a w^{n}.

Para k ≥ 2 y 1 ≤ i ≤ n:

g_{i}^{(w,k)} := g̃_{i}^{(w)}(h^{(w,k−1)}, g_{1}^{(w,k−1)}, …, g_{n}^{(w,k−1)}) y h^{(w,k)} := h̃^{(w)}(h^{(w,k−1)}, g_{1}^{(w,k−1)}, …, g_{n}^{(w,k−1)}).

Supongamos cierta la observación para el caso k = k_{0} − 1, veamos que es cierta para k = k_{0}. Por hipótesis inductiva, existe w̃_{k_{0}−1} potencia de w tal que valen las igualdades:

g_{i}^{(w,k_{0}−1)} = w̃_{k_{0}−1}.g_{i}^{(k_{0}−1)}, h^{(w,k_{0}−1)} = w̃_{k_{0}−1}.h^{(k_{0}−1)}. De la definición recursiva de g_{i}^{(w,k_{0})} se tienen las igualdades:

g_{i}^{(w,k_{0})} := g̃_{i}^{(w)}(h^{(w,k_{0}−1)}, g_{1}^{(w,k_{0}−1)}, …, g_{n}^{(w,k_{0}−1)}) = = (h^{(w,k_{0}−1)})^{v−deg(g_{i})}.(^{h}g_{i}^{(w)}(h^{(w,k_{0}−1)}, g_{1}^{(w,k_{0}−1)}, …, g_{n}^{(w,k_{0}−1)})) = = w̃_{k_{0}−1}^{v}.(h^{(k_{0}−1)})^{v−deg(g_{i})}.w^{n}.(^{h}g_{i}(h^{(k_{0}−1)}, g_{1}^{(k_{0}−1)}, …, g_{n}^{(k_{0}−1)})) = w̃_{k_{0}−1}^{v}.w^{n}.g_{i}^{(k_{0})}.

Análogamente se sigue que h^{(w,k_{0})} = w̃_{k_{0}−1}^{v}.w^{n}.h^{(k_{0})}. Puesto que w̃_{k_{0}−1} es potencia de w, se sigue que w̃_{k_{0}−1}^{v}.w^{n} también lo es, lo que prueba la hipótesis inductiva.

5 Las cuentas y su complejidad

5.1 Solución geométrica de V′

Sea ahora el álgebra

A′ := Q[B_{1}, …, B_{n}]/(B_{1}^{d} − α_{1}, …, B_{n}^{d} − α_{n}).

Recordamos que α_{i} = G_{i}(0, …, 0) para 1 ≤ i ≤ n, donde los polinomios G_{i} son los del sistema de Pham (1). Sean I′ := (B_{1}^{d} − α_{1}, …, B_{n}^{d} − α_{n}) ⊆ Q[B_{1}, …, B_{n}], V′ := V (I′) ⊆ IA^{n}. Claramente se tiene que V′ = {(ξ_{1}, …, ξ_{n}) ∈ IA^{n} : ξ_{i}^{d} = α_{i}}, es decir que los elementos de V′ son todas las n - uplas a_{1}^{(k_{1})}, …, a_{n}^{(k_{n})} de raíces d–ésimas de α_{1}, …, α_{n} y por lo tanto #(V′) = d^{n}. Fijamos un orden en los elementos de V′ = {ξ^{(k)} : 1 ≤ k ≤ d^{n}}.

Proposición 39 Bajo las hipótesis y notación anteriores se verifica:

i) B_{1}^{d} − α_{1}, …, B_{n}^{d} − α_{n} es una sucesión regular en Q[B_{1}, …, B_{n}].

ii) I′ es un ideal radical y por lo tanto A′ es un álgebra reducida.

iii) A′ es un Q - espacio vectorial de dimensión finita, y dim_{Q}A′ = #(V′) = d^{n}.

Demostración.– i) Para 1 ≤ k < n fijo, sea el ideal I′_{k} := (B_{1}^{d} − α_{1}, …, B_{k}^{d} − α_{k}) en Q[B_{1}, …, B_{n}]. Sea > el orden monomial lexicográfico en Q[B_{1}, …, B_{n}]. Con este orden se tiene que el término inicial del polinomio B_{i}^{d} − α_{i} es M(B_{i}^{d} − α_{i}) = B_{i}^{d}. Como B_{i}^{d}, B_{j}^{d} son coprimos para i ≠ j, del Lema 16 se sigue que B_{1}^{d}−α_{1}, …, B_{k}^{d}−α_{k} es una base de Gröbner de I′_{k}. Sea C := {g ∈ Q[B_{1}, …, B_{n}] : g.(B_{k+1}^{d} − α_{k+1}) ∈ I′_{k} y g ∉ I′_{k}}. Por definición, B_{k+1}^{d} − α_{k+1} no es divisor de cero en Q[B_{1}, …, B_{n}]/I′_{k} si y sólo si el conjunto C es vacío. Supongamos por el contrario que C ≠ ∅: Sea g_{0} tal que M(g_{0}) = min{M(g) : g ∈ C}. Existe un tal g_{0} pues todo subconjunto de Q[ε, X_{1}, …, X_{n}] tiene primer elemento respecto de un orden monomial > fijo (ver Lema 15). Se tiene que M(g_{0}.(B_{k+1}^{d} − α_{k+1})) = M(g_{0})M(B_{k+1}^{d} − α_{k+1}) = B_{k+1}^{d}M(g_{0}) ∈ M(I′_{k}). Al ser M(I′_{k}) un ideal generado por monomios, un monomio pertenece al mismo si y sólo si es divisible por algún monomio generador. Calculamos el máximo común divisor entre los términos iniciales de B_{k+1}^{d} − α_{k+1} y B_{i}^{d} − α_{i}: MCD(M(B_{k+1}^{d}−α_{k+1}); M(B_{i}^{d}−α_{i})) = MCD(B_{k+1}^{d}; B_{i}^{d}) = 1 para 1 ≤ i ≤ k, resulta entonces que M(g_{0}.(B_{k+1}^{d} − α_{k+1})) ∈ I′_{k} implica que M(g_{0}) ∈ M(I′_{k}). Sea h ∈ I′_{k} tal que M(g_{0}) = M(h). Se tiene que (g_{0} −h)(B_{k+1}^{d} −α_{k+1}) ∈ I′_{k} y M(g_{0} −h) < M(g_{0}) = min{M(g) : g ∈ C}. Si g_{0} −h ∈ I′_{k}, entonces g_{0} ∈ I′_{k}, lo cual es falso, y si g_{0} −h ∉ I′_{k}, entonces g_{0} − h ∈ C, pero esto es absurdo pues M(g_{0} − h) < M(g_{0}). Por lo tanto, el polinomio B_{k+1}^{d} − α_{k+1} no es divisor de cero en Q[B_{1}, …, B_{n}]/I′_{k}. Dado que este razonamiento se hace para todo 1 ≤ k < n, se sigue que B_{1}^{d} − α_{1}, …, B_{n}^{d} − α_{n} es una sucesión regular en Q[B_{1}, …, B_{n}].

ii) Sea f ∈ Q[B_{1}, …, B_{n}] y m ∈ IN tal que f^{m} ∈ I′. Sea > el orden monomial definido en el ítem i). De acuerdo al algoritmo de división, existen h_{1}, …, h_{n}, r ∈ Q[B_{1}, …, B_{n}] tal que f = ∑_{i=1}^{n} h_{i}(B_{i}^{d}−α_{i})+r donde ningún monomio de r pertenece al ideal (B_{1}^{d}, …, B_{n}^{d}), lo cual implica que deg_{B_{i}}(r) < d para 1 ≤ i ≤ n. Por otra parte, como f^{m} ∈ I′ se tiene que r^{m} ∈ I′. Dado que los polinomios de I′ se anulan en V′, se sigue que r^{m} (y por lo tanto r) se anula en V′. De acuerdo a la Proposición 23, se sigue que r es el polinomio nulo y por lo tanto f ∈ I′.

iii) Dado que I′ es un ideal radical se tiene que A′ = Q[V′]. Puesto que #(V′) = d^{n} se sigue que A′ es un Q–espacio vectorial de dimensión d^{n}.

Sea U ∈ ZZ[B_{1}, …, B_{n}] una forma lineal que separa los puntos de la variedad V′ (es decir, se satisface que U(ξ^{(k)}) ≠ U(ξ^{(j)}) para todo par de puntos distintos ξ^{(k)}, ξ^{(j)} ∈ V′). Existe una tal forma lineal pues V′ es un conjunto finito. Una forma lineal en estas condiciones permite obtener una base de A′ como Q - espacio vectorial de la siguiente manera: siendo u la imagen de U en A′, el conjunto de las potencias P := {1, u, u^{2}, …, u^{d^{n}−1}} es una base. En tal caso, se llama a u un elemento primitivo de A′. Sean v_{1}, …, v_{n} ∈ Q[T] tales que B_{i} − v_{i}(u) ∈ A′. El grado de cada polinomio v_{i} está acotado por d^{n} − 1. Sea q ∈ Q[T] el polinomio minimal de u en A′. El polinomio q es mónico y tiene grado deg q = #V′ = d^{n}. Puesto que U separa puntos de V′, se tiene que q(T) tiene como raíces a las imágenes de V′ bajo U, es decir que q(T) = ∏_{i=1}^{d^{n}}(T − U(ξ^{(i)})). Consideramos la homotecia Q - lineal η en A′ correspondiente a multiplicar por u. Se sigue que la matriz M de η en la base P es la matriz compañera del polinomio q. Los autovalores de esta matriz son las raíces del polinomio q. Por lo tanto, existe una base P′ (y una matriz de cambio de base C ∈ C^{d^{n}×d^{n}}) de la C - álgebra C[B_{1}, …, B_{n}]/(B_{1}^{d} − α_{1}, …, B_{n}^{d} − α_{n}) tal que la matriz M′ de la homotecia η tiene la forma

CMC^{−1} = M′ = ( \begin{matrix}u(ξ^{(1)}) & 0 & … & 0 \\ 0 & u(ξ^{(2)}) & … & 0 \\ ⋮ & ⋮ & ... & ⋮ \\ 0 & 0 & … & u(ξ^{(d^{n})}) \end{matrix} )

Para 1 ≤ i ≤ n consideramos las homotecias η_{B_{i}} inducidas por la multiplicación por la clase de B_{i} en la Q - álgebra A′. Sean M_{B_{i}} las matrices correspondientes a estas homotecias en la base P. Sea S un polinomio en Q[B_{1}, …, B_{n}], η_{S} la homotecia asociada y M_{S} la matriz de η_{S} en la base P. Puesto que A′ es un álgebra conmutativa, se sigue que las homotecias η_{B_{1}}, …, η_{B_{n}} y por lo tanto las matrices M_{B_{1}}, …, M_{B_{n}} conmutan entre sí. Esto implica que para cualquier polinomio S ∈ Q[B_{1}, …, B_{n}] se tiene que η_{S} = S(η_{B_{1}}, …, η_{B_{n}}), M_{S} = S(M_{B_{1}}, …, M_{B_{n}}). La igualdad de ideales I′ = (q(U), B_{1} − v_{1}(U), …, B_{n} − v_{n}(U)) en Q[B_{1}, …, B_{n}] implica las siguientes identidades:

η_{B_{1}} = v_{1}(η), …, η_{B_{n}} = v_{n}(η),
M_{B_{1}} = v_{1}(M), …, M_{B_{n}} = v_{n}(M).

En particular se tiene que, para 1 ≤ i ≤ n la matriz de η_{B_{i}} en la base P′ tiene la forma

CM_{B_{i}}C^{−1} = v_{i}(CMC^{−1}) = ( \begin{matrix}a_{i}^{(1)} & 0 & … & 0 \\ 0 & a_{i}^{(2)} & … & 0 \\ ⋮ & … & ... & ⋮ \\ 0 & 0 & … & a_{i}^{(d^{n})} \end{matrix} )  (15)

Entonces, para cualquier polinomio S de Q[B_{1}, …, B_{n}] vale que:

η_{S} = S(v_{1}(η), …, v_{n}(η)),
M_{S} = S(v_{1}(M), …, v_{n}(M)).  (16)

Supongamos que el polinomio minimal q del elemento primitivo u sea reducible en Q[T]. Sea q = q_{1} … q_{s} su descomposición en factores irreducibles no constantes en Q[T]. Sean D_{i} = deg q_{i}, se tiene que D_{1} + … + D_{s} = d^{n}. Los polinomios q_{i} son coprimos pues q es un polinomio separable. Sea la siguiente matriz:

M^{∗} := ( \begin{matrix}M_{1} & 0 & … & 0 \\ 0 & M_{2} & … & 0 \\ ⋮ & … & ... & ⋮ \\ 0 & 0 & … & M_{s} \end{matrix} )

donde, para cada 1 ≤ i ≤ s, la matriz M_{i} es la matriz compañera de q_{i}. Del hecho que los polinomios son coprimos dos a dos y del Teorema Chino del Resto se deduce que M^{∗} es similar a la matriz M. Trabajar con la matriz M^{∗} en lugar de M produce una reducción en la complejidad del algoritmo formulado anteriormente, ya que el algoritmo trabaja con las matrices M_{B_{i}} = v_{i}(M); a partir de M^{∗}, tenemos las matrices M_{B_{i}}^{∗} = v_{i}(M^{∗}). Recordamos que en el Lema 37 se construye un circuito aritmético que teniendo como entrada a los polinomios F̃_{1}, …, F̃_{n} computa numeradores g_{1}^{(κ)}, …, g_{n}^{(κ)} ∈ Q[B_{1}, …, B_{n}, ε^{1/d}, X_{1}, …, X_{n}] y un denominador (distinto de cero) h^{(κ)} ∈ Q[B_{1}, …, B_{n}, ε^{1/d}, X_{1}, …, X_{n}] correspondientes a aplicar κ pasos de iteración del operador de Newton N (κ) ; _{F}. La cantidad de iteraciones del operador de Newton necesarias en nuestro algoritmo es κ := ⌈log(deg(H)) + (n + 1) log(d)⌉. Reemplazamos formalmente las indeterminadas B_{i} por las matrices M_{B_{i}} y las indeterminadas X_{j} por 0 en g_{1}^{(κ)}, …, g_{n}^{(κ)}, h^{(κ)} y definimos para i = 1, …, n las siguientes matrices en Q[|ε^{1/d}|]^{d^{n}×d^{n}} :

N_{i}^{(κ)} := (M_{B_{i}} + g_{i}^{(κ)}(M_{B_{1}}, …, M_{B_{n}}, 0, …, 0).h^{(κ)}(M_{B_{1}}, …, M_{B_{n}}, 0, …, 0)^{−1})ε^{1/d}.

(17)

Para la buena definición de las matrices N_{i}^{(κ)} necesitamos que la matriz h^{(κ)}(M_{B_{1}}, …, M_{B_{n}}, 0, …, 0) sea inversible en Q[|ε^{1/d}|]^{d^{n}×d^{n}}. Para ello probamos la siguiente observación:

Sea J ⊆ Q^{d^{n}×d^{n}} la Q- álgebra generada por las matrices I, M_{B_{1}}, …, M_{B_{n}}. Es un álgebra conmutativa pues las matrices que la generan conmutan entre sí. Se tiene el siguiente isomorfismo de álgebras:

Observación 40 La función

î: J ⟶ A′ = Q[B_{1}, …, B_{n}]/(B_{1}^{d} − α_{1}, …, B_{n}^{d} − α_{n})
M_{B_{i}} ⟶ B_{i}

está bien definida y es un isomorfismo de Q - álgebras.

Demostración.– Debemos probar que es un morfismo de Q - álgebras, para lo cual basta ver que dado P ∈ Q[X_{1}, …, X_{n}] un polinomio tal que P (M_{B_{1}}, …, M_{B_{n}}) = 0 en J entonces P (B_{1}, …, B_{n}) = 0 en A′. Recordamos (ver ecuación (15)) que existe C ∈ C^{d^{n}×d^{n}} inversible tal que para 1 ≤ i ≤ n vale:

CM_{B_{i}}C^{−1} = ( \begin{matrix}a_{i}^{(1)} & 0 & … & 0 \\ 0 & a_{i}^{(2)} & … & 0 \\ ⋮ & … & ... & ⋮ \\ 0 & 0 & … & a_{i}^{(d^{n})} \end{matrix} )

Entonces se tienen las igualdades 0 = CP (M_{B_{1}}, …, M_{B_{n}})C^{−1} = P (CM_{B_{1}}C^{−1}, …, CM_{B_{n}}C^{−1}) =

= ( \begin{matrix}P (a_{1}^{(1)}, …, a_{n}^{(1)}) & 0 & … & 0 \\ 0 & P (a_{1}^{(2)}, …, a_{n}^{(2)}) & … & 0 \\ ⋮ & … & ... & ⋮ \\ 0 & 0 & … & P (a_{1}^{(d^{n})}, …, a_{n}^{(d^{n})}) \end{matrix} ) .

Puesto que V′ = {ξ_{1}^{(1)}, …, ξ_{1}^{(d^{n})}}, P se anula en la variedad V′, lo cual dado que el ideal (B_{1}^{d} − α_{1}, …, B_{n}^{d} − α_{n}) es radical se sigue que P (B_{1}, …, B_{n}) = 0 en A′, que es lo que se quería demostrar. La inyectividad de î se prueba de manera análoga y dado que es un morfismo sobreyectivo se tiene el isomorfismo probado.

Observación 41 h^{(κ)}(M_{B_{1}}, …, M_{B_{n}}, 0, …, 0) es inversible en Q[|ε^{1/d}|]^{d^{n}×d^{n}}.

Demostración.– Recordamos que se probó en el Lema 37 que para todo k ∈ IN, el denominador h^{(k)} ∈ Q[B_{1}, …, B_{n}, ε^{1/d}][X_{1}, …, X_{n}], evaluado en 0, …, 0 es un elemento inversible de R = Q[B_{1}, …, B_{n}]/(B_{1}^{d} − α_{1}, …, B_{n}^{d} − α_{n})[|ε^{1/d}|]. De acuerdo a la Observación 40 el álgebra generada por las matrices M_{B_{1}}, …, M_{B_{n}} es isomorfa al álgebra A′ = Q[B_{1}, …, B_{n}]/(B_{1}^{d} − α_{1}, …, B_{n}^{d} − α_{n}). Por lo tanto h^{(κ)}(M_{B_{1}}, …, M_{B_{n}}, 0, …, 0) es inversible en Q[|ε^{1/d}|]^{d^{n}×d^{n}}.

Recordamos la observación hecha en esta Subsección sobre la conveniencia de trabajar con la matriz por bloques M^{∗} en lugar de la matriz compañera de q(T), M. Para 1 ≤ i ≤ s, 1 ≤ j ≤ n definimos las matrices M_{(B_{j},i)} := v_{j}(M_{i}) donde M_{i} es la matriz compañera de q_{i}. Definimos para 1 ≤ i ≤ s, 1 ≤ j ≤ n las matrices de Q[|ε^{1/d}|]^{D_{i}×D_{i}} :

N_{(j,i)}^{(κ)} :=
:= (M_{(B_{j},i)} + \frac{g_{j}^{(κ)}}{h^{(κ)}} (M_{(B_{1},i)}, …, M_{(B_{n},i)}, 0, …, 0))ε^{1/d}.  (18)

Para todo 1 ≤ j ≤ n, la matriz N_{j}^{(κ)} es semejante a la matriz por bloques:

( \begin{matrix}N_{(j,1)}^{(κ)} & 0 & … & 0 \\ 0 & N_{(j,2)}^{(κ)} & … & 0 \\ ⋮ & … & ... & ⋮ \\ 0 & 0 & … & N_{(j,s)}^{(κ)} \end{matrix} ) .

Esto se deduce de que la matriz M es semejante a la matriz por bloques M^{∗} y de la ecuación (16).

Sea H ∈ Q[ε, X_{1}, …, X_{n}] un polinomio, sea M_{H} ∈ Q(ε)^{d^{n}×d^{n}} la matriz correspondiente a la homotecia “multiplicar por H” en el álgebra B, en alguna base. Sea q_{H} = ∑_{k=1}^{d^{n}} a_{k}T^{k} ∈ Q[|ε|][T] su polinomio característico . Reemplazando las indeterminadas X_{i} por las matrices N_{i}^{(κ)}, sea M_{H} := H(N_{1}^{(κ)}, …, N_{n}^{(κ)}) ∈ Q[|ε^{1/d}|]^{d^{n}×d^{n}}, sea χ_{M} = ∑_{k=1}^{d^{n}} b_{k}T^{k} ∈ Q[|ε^{1/d}|][T] su polinomio característico. El siguiente Lema muestra que χ_{M} aproxima, en un sentido a precisar por el mismo Lema, al polinomio característico q_{H}.

Lema 42 Bajo las hipótesis y notación anteriores, los coeficientes de χ_{M} y q_{H} verifican la siguiente condición en C[|ε^{1/d}|]:

a_{k} ≡ b_{k} módulo (ε)^{deg(H)d^{n}}

para k = 1, …, d^{n}.

Demostración.– De la Proposición 31 sabemos que q_{H} := ∏_{k=1}^{d^{n}}(T − H(r̄^{(k)})) en C[|ε^{1/d}|][T] donde r̄^{(k)} = (r̄_{1}^{(k)}, …, r̄_{n}^{(k)}) para 1 ≤ k ≤ d^{n} son las series de Puiseux de X_{1}, …, X_{n} respecto de ε. Abreviamos (ξ^{(j)}, 0) por (a_{1}^{(j)}, …, a_{n}^{(j)}, 0, …, 0) ∈ IA^{2n} para 1 ≤ j ≤ d^{n}. Recordamos que a_{i}^{(j)} ∈ C son raíces d–ésimas de α_{i} y que el conjunto {ξ^{(j)} : 1 ≤ j ≤ d^{n}} es la variedad V′ definida al comienzo de esta sección. A partir de las identidades (15) y (16) se deduce que cada matriz N_{i}^{(κ)} es semejante a

CN_{i}^{(κ)}C^{−1} = ( \begin{matrix}(a_{i}^{(1)} + \frac{g_{i}^{(κ)}(ξ^{(1)},0)}{h^{(κ)}(ξ^{(1)},0)})ε^{1/d} & … & 0 \\ ⋮ & ... & ⋮ \\ 0 & … & (a_{i}^{(d^{n})} + \frac{g_{i}^{(κ)}(ξ^{(d^{n})},0)}{h^{(κ)}(ξ^{(d^{n})},0)})ε^{1/d} \end{matrix} )  (19)

Abreviamos g̃^{(κ)}(ξ^{(j)}, 0) por ((a_{1}^{(j)} + g_{1}^{(κ)}(ξ^{(j)}, 0).h^{(κ)}(ξ^{(j)}, 0)^{−1})ε^{1/d}, …, (a_{n}^{(j)} + g_{n}^{(κ)}(ξ^{(j)}, 0).h^{(κ)}(ξ^{(j)}, 0)^{−1})ε^{1/d}). Se tiene entonces que la matriz M_{H} es semejante a

CM_{H}C^{−1} = ( \begin{matrix}H(g̃^{(κ)}(ξ^{(1)}, 0)) & … & 0 \\ ⋮ & ... & ⋮ \\ 0 & … & H(g̃^{(κ)}(ξ^{(d^{n})}, 0)) \end{matrix} )

Y por lo tanto su polinomio característico se factoriza:

χ_{M} = ∑_{k=1}^{d^{n}} b_{k}T^{k} = ∏_{k=1}^{d^{n}}(T − H(g̃^{(κ)}(ξ^{(k)}, 0))) en C[|ε^{1/d}|][T].  (20)

Recordamos la definición de κ = ⌈log(deg(H)) + (n + 1) log(d)⌉. De acuerdo a la ecuación (11) de la demostración del Lema 36 se tiene que

R^{(κ)} ≡ R módulo (ε)^{deg(H)d^{n}}

en (Q[B_{1}, …, B_{n}]/(B_{1}^{d} − α_{1}, …, B_{n}^{d} − α_{n})[|ε^{1/d}|])^{n}. Es decir que para todo 1 ≤ i ≤ n se tiene la relación de congruencia R_{i}^{(κ)} ≡ R_{i} módulo (ε)^{deg(H)d^{n}}. De estas equaciones se deduce que (B_{i} + R_{i}^{(κ)})ε^{1/d} ≡ (B_{i} + R_{i})ε^{1/d} módulo (ε)^{deg(H)d^{n}} para todo 1 ≤ i ≤ n. Evaluando las indeterminadas B_{1}, …, B_{n} en las matrices M_{B_{1}}, …, M_{B_{n}} en esta última relación de congruencia (recordar la Observación 40) se tiene:

(M_{B_{i}}+R_{i}^{(κ)}(M_{B_{1}}, …, M_{B_{n}}))ε^{1/d} ≡ (M_{B_{i}}+R_{i}(M_{B_{1}}, …, M_{B_{n}}))ε^{1/d} módulo (ε)^{deg(H)d^{n}}

en Q[|ε^{1/d}|]^{d^{n}×d^{n}}. Notar que la matriz de la izquierda es la matriz N_{i}^{(κ)}. Multiplicamos a izquierda por la matriz C y a derecha por C^{−1} y tenemos:

CN_{i}^{(κ)}C^{−1} ≡ (CM_{B_{i}}C^{−1} + R_{i}(CM_{B_{1}}C^{−1}, …, CM_{B_{n}}C^{−1}))ε^{1/d} módulo (ε)^{deg(H)d^{n}}

La matriz de la izquierda es semejante a la matriz N_{i}^{(κ)} de acuerdo a la ecuación (19). La matriz de la derecha es la matriz

( \begin{matrix}r̄_{i}^{(1)} & … & 0 \\ ⋮ & ... & ⋮ \\ 0 & … & r̄_{i}^{(d^{n})} \end{matrix} ) .

Vale decir que para todo 1 ≤ i ≤ n, 1 ≤ j ≤ d^{n} se tiene la relación de congruencia (a_{i}^{(j)} + \frac{g_{i}^{(κ)}(ξ^{(j)},0)}{h^{(κ)}(ξ^{(j)},0)})ε^{1/d} ≡ r_{i}^{(j)} módulo (ε)^{deg(H)d^{n}}. Sea σ_{j} la j–ésima función simétrica elemental en d^{n} variables. Entonces, los j–ésimos coeficientes de q_{H} y χ_{M} verifican

a_{j} = (−1)^{j}σ_{j}(H(r̄^{(1)}), …, H(r̄^{(d^{n})})),
b_{j} = (−1)^{j}σ_{j}(H(g̃^{(κ)}(ξ^{(1)}, 0)), …, H(g̃^{(κ)}(ξ^{(d^{n})}, 0)).

De donde se deduce que

a_{k} ≡ b_{k} módulo (ε)^{deg(H)d^{n}}.

Sea H_{1} ∈ Q[X_{1}, …, X_{n}] la forma lineal correspondiente al desarrollo de Taylor de H en el origen (0, …, 0) ∈ IA^{n}, respecto de las variables X_{1}, …, X_{n}. Sea m_{H} ∈ Q[ε, X_{1}, …, X_{n}] el polinomio minimal de H y supongamos que #{H_{1}(V′)} = deg_{T} (m_{H}).

El Lema siguiente es una variante del Lema 29 de [GHH^{+}97].

Lema 43 ([GHH^{+}97, Lemma 29]) Bajo las hipótesis y notación anteriores, sea m_{H} ∈ Q[ε, X_{1}, …, X_{n}] el polinomio minimal de H, sea m̃_{H} ∈ Q[|ε^{1/d}|][X_{1}, …, X_{n}] el polinomio minimal de la matriz M_{H}. Supongamos que vale la igualdad deg_{T} (m̃_{H}) = deg_{T} (m_{H}). Entonces se tiene la relación de congruencia:

m_{H} ≡ m̃_{H} módulo ε^{d^{n} deg(H)} en Q[|ε^{1/d}|][T].

5.2 El resultado principal

Recordamos la definición del álgebra A′ :

A′ = Q[B_{1}, …, B_{n}]/(B_{1}^{d} − α_{1}, …, B_{n}^{d} − α_{n}),

y la variedad V′ = V (B_{1}^{d}−α_{1}, …, B_{n}^{d}−α_{n}) ⊂ IA^{n}. La forma lineal U ∈ Q[B_{1}, …, B_{n}] es un elemento primitivo de A′ y los polinomios q = q_{1} … q_{s}, v_{1}, …, v_{n} ∈ Q[T] − {0} corresponden a la solución geométrica de V′, es decir que se tiene el isomorfismo de álgebras

A′ ≃ Q[B_{1}, …, B_{n}]/(q(U), B_{1} − v_{1}(U), …, B_{n} − v_{n}(U)).

Sea D_{i} = deg(q_{i}). Sin pérdida de generalidad suponemos D_{1} ≤ D_{2} ≤ … ≤ D_{s}.

El input del algoritmo del Teorema 45 es un straight–line program β que computa en espacio S y tiempo T los siguientes polinomios:

• Los polinomios F_{1}, …, F_{n} ∈ Q[ε, X_{1}, …, X_{n}] que definen el sistema de Pham– Brieskorn (1),

• un polinomio H ∈ Q[ε, X_{1}, …, X_{n}],

• Una forma lineal U ∈ Q[B_{1}, …, B_{n}] y los polinomios q_{1}, …, q_{s}, v_{1}, …, v_{n} ∈ Q[T] correspondientes a la solución geométrica del álgebra V′.

El output del algoritmo es un straight–line program que computa al (único) polinomio m_{H} ∈ Q[ε, T], mónico en T y de grado mínimo en T tal que m_{H}(ε, H) ∈ (F_{1}, …, F_{n}).

Definimos los siguientes polinomios en Q[ε^{1/d}, B_{1}, …, B_{n}, X_{1}, …, X_{n}]:

Ĥ(ε^{1/d}, B_{1}, …, B_{n}, X_{1}, …, X_{n}) := H(ε, (B_{1} + X_{1})ε^{1/d}, …, (B_{n} + X_{n})ε^{1/d}),
F̂_{i}(ε^{1/d}, B_{1}, …, B_{n}, X_{1}, …, X_{n}) := F_{i}(ε, (B_{1} + X_{1})ε^{1/d}, …, (B_{n} + X_{n})ε^{1/d})

para 1 ≤ i ≤ n.

Observación 44 Los polinomios F̂_{1}, …, F̂_{n}, Ĥ pueden ser computados por un straight-line program en Q[ε^{1/d}] que usa espacio O(S + n + log d) y tiempo O(T + n + log d).

Demostración.– El polinomio ε se obtiene a partir del polinomio ε^{1/d} en espacio y tiempo O(log d). Los polinomios (B_{1} + X_{1})ε^{1/d}, …, (B_{n} + X_{n})ε^{1/d} se obtienen en espacio y tiempo adicional O(n). Componiendo estos polinomios en los polinomios F_{1}, …, F_{n}, H se obtienen los polinomios pedidos con la complejidad afirmada.

Los polinomios F̃_{1}, …, F̃_{n} definidos en (6) se obtienen como cociente de los polinomios F̂_{1}, …, F̂_{n} por el polinomio ε. Para evitar divisiones por polinomios en nuestro algoritmo, trabajaremos con los polinomios F̂_{1}, …, F̂_{n} en lugar de los polinomios F̃_{1}, …, F̃_{n}.

El Teorema 45 es el resultado principal de esta tesis, y se ha desarrollado adaptando el Teorema 11 de ([HMW99]) y las ideas de ([HKP^{+}98]) al contexto del sistema de Pham–Brieskorn (1).

Idea general del algoritmo: queremos un straight–line program que compute el polinomio m_{H}, para lo cual primero vamos a obtener un straight–line program que compute el polinomio característico q_{H} correspondiente a la homotecia “multiplicar por H” en el álgebra B (recordar Proposición 31), luego computaremos el máximo común divisor entre q_{H} y su derivada en la variable T y por último obtendremos el polinomio m_{H} que es igual a q_{H}/MCD(q_{H}; \frac{∂q_{H}}{∂T}). Recordamos la definición de las matrices N_{j}^{(κ)} para 1 ≤ j ≤ n dada en (17),

N_{j}^{(κ)} := (M_{B_{j}} + g_{j}^{(κ)}(M_{B_{1}}, …, M_{B_{n}}, 0, …, 0).h^{(κ)}(M_{B_{1}}, …, M_{B_{n}}, 0, …, 0)^{−1})ε^{1/d}.

En lugar de computar el polinomio q_{H} calculamos el polinomio característico χ_{M} de la matriz M_{H} := H(N_{1}^{(κ)}, …, N_{n}^{(κ)}), luego computamos su representación separable m̃_{H} = χ_{M}/MCD(χ_{M}; \frac{∂χ_{M}}{∂T}) ya que el polinomio minimal m_{H} se obtiene a partir de m̃_{H} según se desprende de la cota de grado total del polinomio minimal m_{H} dada en la Proposición 28: deg(m_{H}) ≤ d^{n} deg(H) y de la relación de congruencia entre m_{H} y m̃_{H} dada en el Lema 43. Ahora se imponen dos observaciones:

• Las matrices N_{j}^{(κ)} tienen tamaño d^{n} × d^{n} y son funciones de M, la matriz compañera de q(T). Si el polinomio q(T) se factoriza en s factores no constantes de Q[T], q(T) = ∏_{i=1}^{s} q_{i}(T), la matriz M es semejante a la matriz por bloques formados por las matrices compañeras de q_{i} según se observó en la Subsección 5.1. Para 1 ≤ i ≤ s, 1 ≤ j ≤ n se definen las matrices M_{(B_{j},i)} := v_{j}(M_{i}) donde M_{i} es la matriz compañera de q_{i}, y a partir de éstas se definen (18) para 1 ≤ i ≤ s, 1 ≤ j ≤ n las matrices N_{(j,i)}^{(κ)} :

N_{(j,i)}^{(κ)} := (M_{(B_{j},i)} + \frac{g_{j}^{(κ)}}{h^{(κ)}} (M_{(B_{1},i)}, …, M_{(B_{n},i)}, 0, …, 0))ε^{1/d}.

Cada matriz N_{j}^{(κ)} es semejante a la matriz por bloques formados por las s matrices N_{(j,i)}^{(κ)}, y entonces la matriz M_{H} = H(N_{1}^{(κ)}, …, N_{n}^{(κ)}) es semejante a la matriz por bloques formados por las matrices M_{H,i} := H(N_{(1,i)}^{(κ)}, …, N_{(n,i)}^{(κ)}). El polinomio característico χ_{M} es producto de los polinomios característicos de M_{H,i}. La idea es entonces trabajar con las s matrices M_{H,i} en lugar de M puesto que se produce una economía de espacio y tiempo. Esta idea viene de [HKP^{+}98].

• En la definición de las matrices N_{(j,i)}^{(κ)} se utilizan las inversas de las matrices h^{(κ)}(M_{(B_{1},i)}, …, M_{(B_{n},i)}, 0, …, 0). Para controlar la compejidad en espacio y tiempo de esta operación (y por ende del algoritmo) utilizaremos las rutinas de álgebra lineal y seguiremos la estrategia de [HMW99].

La estrategia a seguir en el agoritmo es la siguiente: primero se calculan los polinomios característicos de M_{H,i} para 1 ≤ i ≤ s, luego los polinomios minimales m̃_{H,i} de M_{H,i} a partir de éstos , y después se calcula el mínimo común múltiplo de m̃_{H,1}, …, m̃_{H,s}. Por último, “truncando” hasta el grado d^{n} deg(H) la serie de potencias en ε^{1/d} de este último polinomio se obtiene el polinomio minimal m_{H}.

Teorema 45 Bajo las hipótesis y notaciones anteriores, los coeficientes del polinomio minimal m_{H} ∈ Q[ε][T] que satisface la condición m_{H}(ε, H) ∈ (F_{1}, …, F_{n}) pueden ser computados a partir de una solución geométrica de la variedad V′ por un straight-line program en Q[ε^{1/d}] que usa espacio O((S + n + log d) deg(H)(n + deg(H))(D_{1}^{2} + … + D_{s}^{2})) y tiempo O(((T +n+log d) deg(H)+n^{4}) max(∑_{i=1}^{s} D_{i}^{3}; ∑_{i=1}^{s}(s−1−i)D_{i}^{2}) log^{2} d^{n} log log d^{n}) ≤ O(((T + n + log d) deg(H) + n^{4}) max(sD_{s}^{3}; s^{2}D_{s}^{2}) log^{2} d^{n} log log d^{n}).

Demostración.– A partir del straight–line program dado como input, calculamos los polinomios F̂_{1}, …, F̂_{n}, Ĥ en espacio del orden de S̃:= S+n+log d y tiempo del orden de T̃ := T +n+log d según la Observación 44. Aplicamos la κ = ⌈log(deg(H)d^{n+1})⌉– ésima iteración del Operador de Newton a los polinomios F̂_{1}, …, F̂_{n} de acuerdo al straight–line program definido en el Lema 37 y en la Observación 38, obteniendo entonces los numeradores g_{1}^{(ε^{1/d},κ)}, …, g_{n}^{(ε^{1/d},κ)} ∈ Q[ε^{1/d}, B_{1}, …, B_{n}, X_{1}, …, X_{n}] y el denominador h^{(ε^{1/d},κ)} ∈ Q[ε^{1/d}, B_{1}, …, B_{n}, X_{1}, …, X_{n}] tales que

N (κ) ; _{F} = (\frac{g_{1}^{(ε^{1/d},κ)}}{h^{(ε^{1/d},κ)}} , …, \frac{g_{n}^{(ε^{1/d},κ)}}{h^{(ε^{1/d},κ)}} ) .

El operador de Newton–Hensel es aplicable a los polinomios F̂_{1}, …, F̂_{n} según se demostró en la Observación 38. En esta Observación se prueba que los polinomios g_{1}^{(ε^{1/d},κ)}, …, g_{n}^{(ε^{1/d},κ)}, h^{(ε^{1/d},κ)} son w̃− múltiplos de g_{1}^{(κ)}, …, g_{n}^{(κ)}, h^{(κ)} donde w̃ es una potencia de ε^{1/d} y g_{1}^{(κ)}, …, g_{n}^{(κ)}, h^{(κ)} ∈ Q[ε^{1/d}, B_{1}, …, B_{n}, X_{1}, …, X_{n}] son los numeradores y el denominador que se obtienen en la κ–ésima iteración del Operador de Newton aplicado a los polinomios F̃_{1}, …, F̃_{n}. En particular se tiene la igualdad

N (κ) ; _{F} = N (κ) ; _{F} en Q(B_{1}, …, B_{n}, ε^{1/d}, X_{1}, …, X_{n}).

El cálculo de los polinomios g_{1}^{(ε^{1/d},κ)}, …, g_{n}^{(ε^{1/d},κ)}, h^{(ε^{1/d},κ)} se realiza en espacio O(S̃n) y tiempo O((T̃ n + n^{4}) log(deg(H)d^{n+1})) según se establece en la Observación 38.

Recordamos que la forma lineal U ∈ Q[B_{1}, …, B_{n}] y los polinomios v_{1}(T), …, v_{n}(T) ∈ Q[T] correspondientes a la solución geométrica de V′ verifican que v_{j}(U) = B_{j} en A′ para todo 1 ≤ j ≤ n. Especializando las variables X_{1}, …, X_{n} en 0, …, 0 y las variables B_{1}, …, B_{n} en los polinomios v_{1}(T), …, v_{n}(T) se tienen los siguientes polinomios de Q[ε^{1/d}][T]:

• g_{j}(T) := g_{j}^{(ε^{1/d},κ)}(ε^{1/d}, v_{1}(T), …, v_{n}(T), 0, …, 0) para 1 ≤ j ≤ n,

• h(T) := h^{(ε^{1/d},κ)}(ε^{1/d}, v_{1}(T), …, v_{n}(T), 0, …, 0).

Para 1 ≤ i ≤ s, consideramos en Q(ε^{1/d})[T] la función racional

f(T) := Ĥ(ε^{1/d}, v_{1}(T), …, v_{n}(T), \frac{g_{1}(T)}{h(T)}, …, \frac{g_{n}(T)}{h(T)})

módulo el polinomio q_{i}(T). Recordamos que q(T) = ∏_{i=1}^{s} q_{i}(T) es el polinomio minimal de la forma lineal U en el álgebra A′. Para evitar divisiones por polinomios en el cálculo de f(T), computamos la descomposición homogénea de Ĥ,

Ĥ(ε^{1/d}, B_{1}, …, B_{n}, X_{1}, …, X_{n}) = ∑_{k=0}^{deg(H)} Ĥ_{k}(ε^{1/d}, B_{1}, …, B_{n}, X_{1}, …, X_{n})

considerando a Ĥ un polinomio en las variables X_{1}, …, X_{n} con coeficientes en el anillo Q[ε^{1/d}, B_{1}, …, B_{n}]. Esta descomposición se calcula mediante el procedimiento descrito en la demostración del Lema 5 usando espacio O(S̃ deg(H)) y tiempo O(T̃ deg(H) log deg(H) log log deg(H)). Considerando en Q(ε^{1/d})[T] las siguientes identidades:

f(T) := Ĥ(ε^{1/d}, v_{1}(T), …, v_{n}(T), \frac{g_{1}(T)}{h(T)}, …, \frac{g_{n}(T)}{h(T)})

= ∑_{k=0}^{deg(H)} Ĥ_{k}(ε^{1/d}, v_{1}(T), …, v_{n}(T), \frac{g_{1}(T)}{h(T)}, …, \frac{g_{n}(T)}{h(T)})

= ∑_{k=0}^{deg(H)} \frac{Ĥ_{k}(ε^{1/d}, v_{1}(T), …, v_{n}(T), g_{1}(T), …, g_{n}(T))}{(h(T))^{k}}

= \frac{∑_{k=0}^{deg(H)} Ĥ_{k}(ε^{1/d}, v_{1}(T), …, v_{n}(T), g_{1}(T), …, g_{n}(T))(h(T))^{deg(H)−k}}{(h(T))^{deg(H)}} ,

concluímos que el numerador y el denominador de la función racional f(T) se calculan en espacio O(S̃(n + deg(H))) y tiempo O((T̃ n deg(H) + n^{4}) log(deg(H)d^{n})) realizando divisiones por elementos no nulos de Q.

Es necesaria la siguiente afirmación técnica.

Afirmación: Los polinomios h(T) y q(T) = ∏_{i=1}^{s} q_{i}(T) son coprimos en Q(ε^{1/d})[T].

Recordamos que en la Subsección 5.1 se probó que el polinomio q(T) ∈ Q[T] se factoriza ∏_{j=1}^{d^{n}}(T − U(ξ^{(j)})) donde ξ^{(j)} ∈ IA^{n} son n–uplas de raíces d–ésimas de α_{1}, …, α_{n}, es decir que {ξ^{(j)} : 1 ≤ j ≤ d^{n}} es la variedad V′. Por lo tanto basta ver que el polinomio h(T) no se anula en U(ξ^{(j)}) para ningún 1 ≤ j ≤ d^{n}. Recordamos que v_{i}(U) ≡ B_{i} en A′ para todo 1 ≤ i ≤ n implica las igualdades v_{i}(U(ξ^{(j)})) = ξ_{i}^{(j)} para todo 1 ≤ i ≤ n, 1 ≤ j ≤ d^{n}. Fijamos 1 ≤ j ≤ d^{n} y evaluamos h(T) en U(ξ^{(j)}):

h(U(ξ^{(j)})) = h^{(ε^{1/d},κ)}(ε^{1/d}, v_{1}(U(ξ^{(j)})), …, v_{n}(U(ξ^{(j)})), 0, …, 0) =
= h^{(ε^{1/d},κ)}(ε^{1/d}, ξ_{1}^{(j)}, …, ξ_{n}^{(j)}, 0, …, 0).  (21)

Recordamos que el polinomio h^{(ε^{1/d},κ)} es el denominador que se obtiene en la κ– ésima iteración del Operador de Newton aplicado a los polinomios F̂_{1}, …, F̂_{n}, y es w̃–múltiplo del polinomio h^{(κ)} donde w̃ es una potencia de ε^{1/d} y h^{(κ)} ∈ Q[ε^{1/d}, B_{1}, …, B_{n}, X_{1}, …, X_{n}] es el denominador que se obtiene en la κ–ésima iteración del Operador de Newton aplicado a los polinomios F̃_{1}, …, F̃_{n}. Ahora bien, el polinomio h^{(κ)}, evaluando las indeterminadas X_{1}, …, X_{n} en 0, …, 0, es inversible en R = Q[B_{1}, …, B_{n}]/(B_{1}^{d} − α_{1}, …, B_{n}^{d} − α_{n})[|ε^{1/d}|] (ver Lema 37), por lo tanto existe h_{0} ∈ A′ = Q[B_{1}, …, B_{n}]/(B_{1}^{d} − α_{1}, …, B_{n}^{d} − α_{n}) inversible tal que

h^{(κ)}(ε^{1/d}, B_{1}, …, B_{n}, 0, …, 0) ≡ h_{0} módulo ε^{1/d} en R.  (22)

Dado que h_{0} es inversible en A′, se sigue que h_{0}(ξ^{(j)}) ≠ 0 y por lo tanto h^{(κ)}(ε^{1/d}, ξ^{(j)}, 0, …, 0) ≠ 0. Retomando la ecuación (21) se sigue que

h(U(ξ^{(j)})) = w̃h^{(κ)}(ε^{1/d}, ξ^{(j)}, 0, …, 0) ≠ 0

para 1 ≤ j ≤ d^{n} que es lo que se quería probar.

Dado entonces que h(T) y q(T) = ∏_{i=1}^{s} q_{i}(T) son coprimos en Q(ε^{1/d})[T] se puede aplicar, para cada 1 ≤ i ≤ s, el procedimiento descrito en el comienzo de la demostración del Lema 1 para calcular polinomios f̃_{i}(T) ∈ Q[ε^{1/d}][T] de grado en T a lo sumo D_{i} − 1 y elementos α_{i} ∈ Q[ε^{1/d}] satisfaciendo en Q[ε^{1/d}][T] la condición

(h(T))^{deg(H)}f̃_{i}(T) ≡ α_{i}G(T) módulo q_{i}(T)

donde

G(T) := ∑_{1≤k≤deg(H)} Ĥ_{k}(ε^{1/d}, v_{1}(T), …, v_{n}(T), g_{1}(T), …, g_{n}(T)).(h(T))^{deg(H)−k}.

Entonces tenemos en Q(ε^{1/d})[T] la relación de congruencia f̃_{i}(T) ≡ α_{i}f(T) módulo q_{i}(T) para 1 ≤ i ≤ s. Evaluando la indeterminada T en M_{i}, la matriz compañera de q_{i}(T), se tiene para cada 1 ≤ i ≤ s :

f̃_{i}(M_{i}) = α_{i}f(M_{i})
= α_{i}H(ε, N_{(1,i)}, …, N_{(n,i)}) = α_{i}M_{H,i}

donde las matrices N_{(j,i)} se definían en (18) y la matriz M_{H,i} es por definición la matriz H(ε, N_{(1,i)}, …, N_{(n,i)}). Para cada 1 ≤ i ≤ s, los polinomios f̃_{i}(T) y α_{i} pueden ser calculados por un straight-line program en espacio O(S̃(D_{i})(n+deg(H))) y tiempo O((T̃ deg(H) + n^{4})(D_{i}^{2}) log^{2} d^{n} log log d^{n}).

Usando un procedimiento similar al de la demostración del Lema 2 podemos calcular, para cada 1 ≤ i ≤ s, α_{i}^{D_{i}}- múltiplos de los coeficientes del polinomio característico χ_{i}(T) := χ_{M_{H,i}}(T) de M_{H,i} en espacio O(S̃(D_{i})(n + deg(H))) y tiempo O((T̃ deg(H) + n^{4})(D_{i}^{2}) log^{2} d^{n} log log d^{n}). Supongamos entonces que tenemos computados para todo 1 ≤ i ≤ s los coeficientes del polinomio α_{i}^{D_{i}}χ_{M_{H,i}}(T).

Dado que la matriz M_{H} es semejante a la matriz por bloques formados por las s matrices M_{H,i}, el polinomio característico χ(T) de M_{H} es el producto de los polinomios característicos χ_{M_{H,1}}(T), …, χ_{M_{H,s}}(T). Puesto que estamos interesados en computar el polinomio minimal m̃_{H} de M_{H} y dado que la matriz M_{H} es diagonalizable, es suficiente entonces eliminar del polinomio característico χ(T) = ∏_{i=1}^{s} χ_{M_{H,i}}(T) los factores múltiples para obtener el polinomio minimal m̃_{H} de M_{H}. Para ello primero queremos calcular para todo 1 ≤ i ≤ s el numerador mónico de la representación irreducible de la función racional \frac{α_{i}^{D_{i}}χ_{i}(T)}{α_{i}^{D_{i}}χ′_{i}(T)} = \frac{χ_{i}(T)}{χ′_{i}(T)}. Este numerador mónico es el polinomio minimal m̃_{H,i} = ∑_{k=0}^{deg(_{m_{H,i}})} a_{(k,i)} de M_{H,i}. El polinomio minimal m̃_{H} de M_{H} es el mínimo común múltiplo de los polinomios m̃_{H,1}, …, m̃_{H,s}.

Para cada 1 ≤ i ≤ s queremos aplicar el Lema 7 a la función racional \frac{α_{i}^{D_{i}}χ_{i}(T)}{α_{i}^{D_{i}}χ′_{i}(T)} y com-

putar elementos γ_{i} ∈ Q[ε^{1/d}] y γ_{i}-múltiplos de los coeficientes a_{(0,i)}, …, a_{(deg(_{m_{H,i}}),i)} del polinomio minimal m̃_{H,i} tal que γ_{i}a_{(0,i)}, …, γ_{i}a_{(deg(_{m_{H,i}}),i)} sean elementos de Q[ε^{1/d}]. Para poder aplicar el Lema 7 es necesario conocer el grado en T del nu-

merador de la representación irreducible de \frac{α_{i}^{D_{i}}χ_{i}(T)}{α_{i}^{D_{i}}χ′_{i}(T)}, es decir el grado en T de m̃_{H,i}.

Este grado se averigua evaluando ε^{1/d} en un elemento y ∈ Q genérico y calculando el máximo común divisor de los polinomios α_{i}^{D_{i}}(y)χ_{i}(y, T), α_{i}^{D_{i}}(y)χi^{′}(y, T) ∈ Q[T]. Siendo y un punto genérico, el grado de este máximo común divisor coincide con el grado en T del máximo común divisor de α_{i}^{D_{i}}χ_{i}(T), α_{i}^{D_{i}}χi^{′}(T) en Q(ε^{1/d})[T]. La complejidad del cálculo del máximo común divisor de dos polinomios en Q[T] (de grado acotado por D_{i}) es del orden de O(D_{i} log D_{i} log log D_{i}) en espacio y O(D_{i}^{2} log D_{i} log log D_{i}) en tiempo (ver [BP94]). Conociendo el grado del máximo común divisor, y conociendo el grado (en T) de α_{i}^{D_{i}}χ_{i}(T) se conoce el grado (en

T) de m̃_{H,i}. Aplicar el Lema 7 a la función racional \frac{α_{i}^{D_{i}}χ_{i}(T)}{α_{i}^{D_{i}}χ′_{i}(T)} se hace con espacio

O(S̃(n+deg(H))(D_{i})) y tiempo O((T̃ deg(H)+n^{4})(D_{i}^{2}) log^{2} d^{n} log log d^{n}), para cada 1 ≤ i ≤ s.

El straight–line program β_{1} definido hasta el momento computa los polinomios γ_{1}, …, γ_{s} ∈ Q[ε^{1/d}] y los polinomios γ_{1}m̃_{H,1}, …, γ_{s}m̃_{H,s} ∈ Q[ε^{1/d}, T] y tiene complejidad O(S̃(n + deg(H))(∑_{i=1}^{s} D_{i})) en espacio y O((T̃ deg(H)+n^{4})(∑_{i=1}^{s} D_{i}^{2}) log^{2} d^{n} log log d^{n}) en tiempo. Debemos calcular el mínimo común múltiplo de m̃_{H,1}, …, m̃_{H,s} y es lo que haremos a continuación. Para ello, vamos a eliminar los factores repetidos de estos polinomios utilizando el siguiente procedimiento: dados dos polinomios separables u_{1} y u_{2} ∈ Q[ε^{1/d}, T], y supongamos por simplicidad que deg_{T} u_{1} > deg_{T} u_{2}, calculamos un polinomio γ ∈ Q[ε^{1/d}] y el γ–múltiplo del numerador irreducible n_{1} de la fracción \frac{u_{1}}{u_{2}} utilizando el straight–line program dado por el Lema 7. Los polinomios n_{1} y u_{2} son separables y coprimos entre sí y su producto es el mínimo común múltiplo de los polinomios u_{1} y u_{2} en Q(ε^{1/d})[T].

Este procedimiento utiliza dos straight–line programs , uno calcula el grado en la variable T del polinomio n_{1} y otro es el dado por el Lema 7.

El straight–line program aplica este procedimiento, tomando de a dos a los polinomios m̃_{H,1}, …, m̃_{H,s}, es decir que se repite s(s − 1) veces el procedimiento; esto explica el factor s^{2} en la complejidad en tiempo del straight–line program .

Vamos a definir el straight–line program esbozado; para ello, supongamos que para algún 1 ≤ i_{0} < s fijo vale la siguiente condición:

• Los polinomios m̃_{H,1}, …, m̃_{H,i_{0}} son coprimos en Q[ε^{1/d}][T].

Definamos el conjunto S_{i_{0}} := {m̃_{H,1}, …, m̃_{H,i_{0}}}. Bajo la suposición anterior, este conjunto está formado por polinomios mónicos en T y coprimos en Q[ε^{1/d}][T] y decimos que está en las condiciones iniciales. Más generalmente, decimos que un conjunto S = {u_{1}, …, u_{k}} ⊂ Q[ε^{1/d}][T] está en las condiciones iniciales si valen las siguientes condiciones:

• Los polinomios u_{1}, …, u_{k} son mónicos en T y coprimos en Q[ε^{1/d}][T].

• El polinomio ∏_{i=1}^{k} u_{i} es el mínimo común múltiplo de los polinomios

m̃_{H,1}, …, m̃_{H,k}

Notar que el conjunto S_{1}, formado por un único elemento, m̃_{H,1}, está en las condiciones iniciales.

Volviendo al conjunto S_{i_{0}} definido anteriormente y bajo la suposición que el mismo está en las condiciones iniciales, nuestro primer paso es obtener un straight–line program que compute polinomios u_{1}, …, u_{i_{0}+1} coprimos en Q[ε^{1/d}][T] tales que el producto de ellos sea el mínimo común múltiplo de los polinomios m̃_{H,1}, …, m̃_{H,i_{0}+1}.

Paso I: Computar el mínimo común múltiplo de dos polinomios de Q[ε^{1/d}][T].

Para calcular el mínimo común múltiplo entre m̃_{H,1} y m̃_{H,i_{0}+1} vamos a calcular un múltiplo del numerador de la representación irreducible de la fracción \frac{γ_{i_{0}+1}_{m_{H,i_{0}+1}}}{γ_{1}_{m_{H,1}}}

(o bien de la fracción \frac{γ_{1}_{m_{H,1}}}{γ_{i_{0}+1}_{m_{H,i_{0}+1}}} si deg_{T} (m̃_{H,1}) > deg_{T} (m̃_{H,i_{0}+1}) ), utilizando el straight–line program dado por el Lema 7. Como sabemos, es necesario conocer el grado en T de los polinomios m̃_{H,1}, m̃_{H,i_{0}+1} y de su máximo común divisor. Para ello, evaluamos ε^{1/d} en un y ∈ Q genérico y calculamos el máximo común divisor entre γ_{1}(y)m̃_{H,1}(y) y γ_{i_{0}+1}(y)m̃_{H,i_{0}+1}(y). El cálculo de la representación densa de los polinomios γ_{1}(y)m̃_{H,1}(y) y γ_{i_{0}+1}(y)m̃_{H,i_{0}+1}(y) y el cálculo de su máximo común divisor se realiza con complejidades inferiores a las del Lema 7

Si deg_{T} (m̃_{H,i_{0}+1}) > deg_{T} (m̃_{H,1}) entonces aplicamos el straight–line program dado por el Lema 7 al cociente de polinomios \frac{γ_{i_{0}+1}_{m_{H,i_{0}+1}}}{γ_{1}_{m_{H,1}}} (si en cambio deg_{T} (m̃_{H,1}) < deg_{T} (m̃_{H,i_{0}+1}) aplicamos el straight–line program dado por el Lema 7 al cociente de polinomios \frac{γ_{1}_{m_{H,1}}}{γ_{i_{0}+1}_{m_{H,i_{0}+1}}} y se continúa de manera análoga. Si los grados son iguales se

aplica el straight–line program dado por el Lema 7 al cociente \frac{(T −y_{1})γ_{1}_{m_{H,1}}}{γ_{i_{0}+1}_{m_{H,i_{0}+1}}} donde y_{1} es un punto genérico de Qy luego se elimina el factor (T −y_{1}) utilizando nuevamente el Lema 7) obteniendo un polinomio γ^{(1)} ∈ Q[ε^{1/d}] y un γ^{(1)}- múltiplo del numerador mónico de la representación irreducible de esta fracción en Q[ε^{1/d}][T], es decir que obtenemos polinomios γ^{(1)} ∈ Q[ε^{1/d}], u^{(1)} ∈ Q[ε^{1/d}][T] que verifican:

• El polinomio \frac{u^{(1)}}{γ^{(1)}} pertenece a Q[ε^{1/d}][T] y es mónico.

• \frac{u^{(1)}}{γ^{(1)}} y m̃_{H,1} son coprimos en Q[ε^{1/d}][T].

• El polinomio \frac{u^{(1)}}{γ^{(1)}} es igual al polinomio m̃_{H,i_{0}+1}/MCD(m̃_{H,i_{0}+1}; m̃_{H,1}).

Recordando que suponemos D_{1} ≤ … ≤ D_{s}, entonces utilizar el straight–line program dado por el Lema 7 representa un costo adicional de O(S̃(n+deg(H))+D_{i_{0}+1}) en espacio y O((T̃ deg(H) + n^{4})(D_{i_{0}+1}^{2}) log^{2} d^{n} log log d^{n}) en tiempo. Luego de estos cómputos, tenemos un straight–line program que computa polinomios γ_{1}, …, γ_{i_{0}}, γ^{(1)}, γ_{i_{0}+2}, …, γ_{s} ∈ Q[ε^{1/d}], y polinomios γ_{1}m̃_{H,1}, …, γ_{i_{0}} m̃_{H,i_{0}}, u^{(1)}, γ_{i_{0}+2}m̃_{H,i_{0}+2}, …, γ_{s}m̃_{H,s} ∈ Q[ε^{1/d}, T] tales que

• Los polinomios m̃_{H,1}, …, m̃_{H,i_{0}} son coprimos en Q[ε^{1/d}][T].

• Los polinomios m̃_{H,1} y \frac{u^{(1)}}{γ^{(1)}} son coprimos en Q[ε^{1/d}][T] y \frac{u^{(1)}}{γ^{(1)}} m̃_{H,1} es el mínimo común múltiplo de los polinomios m̃_{H,1} y m̃_{H,i_{0}+1}.

Fin Paso I

Entonces repetimos el Paso I, esta vez con los polinomios γ_{2}, γ^{(1)} ∈ Q[ε^{1/d}] y m̃_{H,2}, u^{(1)} ∈ Q[ε^{1/d}, T]. Para evitar complicar la notación supongamos nuevamente que deg_{T} (m̃_{H,2}) ≥ deg_{T} (u^{(1)}). Se obtiene entonces un nuevo γ^{(2)} ∈ Q[ε^{1/d}] y un nuevo u^{(2)} ∈ Q[ε^{1/d}, T] que verifica que es coprimo con los polinomios m̃_{H,1}, m̃_{H,2} y el producto \frac{u^{(2)}}{γ^{(2)}} .m̃_{H,1}.m̃_{H,2} es el mínimo común múltiplo de m̃_{H,1}, m̃_{H,2}, m̃_{H,i_{0}+1} (igual que antes, si deg_{T} (m̃_{H,2}) < deg_{T} (u^{(1)}), al aplicar el Paso I el polinomio modificado resulta ser m̃_{H,2}). Resumiendo, partiendo del conjunto S_{i_{0}} en las condiciones iniciales, se repite i_{0} veces el Paso I y se obtiene un straight–line program que computa polinomios γ̃_{1}, …, γ̃_{i_{0}+1}, γ_{i_{0}+2}, …, γ_{s} ∈ Q[ε^{1/d}], y polinomios u_{1}, …, u_{i_{0}+1}, γ_{i_{0}+2}m̃_{H,i_{0}+2}, …, γ_{s}m̃_{H,s} ∈ Q[ε^{1/d}, T] tales que

• Las funciones racionales \frac{u_{1}}{_{γ_{1}}} , …, \frac{u_{i_{0}+1}}{_{γ_{i_{0}+1}}} son polinomios en Q[ε^{1/d}][T], mónicos en la variable T.

• \frac{u_{1}}{_{γ_{1}}} , …, \frac{u_{i_{0}+1}}{_{γ_{i_{0}+1}}} son coprimos en Q[ε^{1/d}][T].

• El polinomio ∏_{i=1}^{i_{0}+1} \frac{u_{i}}{_{γ_{i}}} es el mínimo común múltiplo de los polinomios

m̃_{H,1}, …, m̃_{H,i_{0}+1} en Q[ε^{1/d}][T].

Definimos el conjunto S_{i_{0}+1} := S_{i_{0}} ∪ \{\frac{u_{i_{0}+1}}{_{γ_{i_{0}+1}}} \}. Este conjunto verifica las condiciones iniciales y repetimos entonces el Paso I, ahora con el conjunto S_{i_{0}+1}.

Debemos establecer la complejidad del ciclo i_{0}–ésimo que a partir del conjunto S_{i_{0}} en las condiciones iniciales obtiene un conjunto S_{i_{0}+1} en las condiciones iniciales. Para ello vemos que computamos i_{0} veces el Paso I cuya complejidad asintótica es la del Lema 7. Dado que aplicamos este Lema a polinomios de grado en T acotado por D_{i_{0}+1} y recordando que el input del ciclo era un straight–line program β_{1} de espacio O(S̃(n+deg(H))(∑_{i=1}^{s} D_{i})) y tiempo O((T̃ deg(H)+n^{4})(∑_{i=1}^{s} D_{i}^{2}) log^{2} d^{n} log log d^{n}), concluímos que la complejidad del straight–line program definido por el ciclo i_{0}– ésimo es O(S̃(n + deg(H))(∑_{i=1}^{s} D_{i})) en espacio y O((T̃ deg(H) + n^{4})(∑_{i=1}^{i_{0}+1} D_{i_{0}+1}^{2} + ∑_{i=1}^{s} D_{i}^{2}) log^{2} d^{n} log log d^{n}) = O((T̃ deg(H) + n^{4})((i_{0} + 1)D_{i_{0}+1}^{2} + ∑_{i=1}^{s} D_{i}^{2}) log^{2} d^{n} log log d^{n}) en tiempo.

Ahora bien, originalmente sabemos que el conjunto S_{1} = {m̃_{H,1}} se encuentra en lo que definimos como las condiciones iniciales. Iterando s − 1 veces el ciclo anterior a partir de β_{1} y S_{1} obtenemos finalmente un straight–line program β_{2} que computa polinomios γ̃_{1}, …, γ̃_{s} ∈ Q[ε^{1/d}], u_{1}, …, u_{s} ∈ Q[ε^{1/d}][T] tales que:

• Las funciones racionales \frac{u_{1}}{_{γ_{1}}} , …, \frac{u_{s}}{_{γ_{s}}} pertenecen a Q[ε^{1/d}][T] y son polinomios mónicos en T.

• El producto ∏_{i=1}^{s} \frac{u_{i}}{_{γ_{i}}} es el mínimo común múltiplo de los polinomios

m̃_{H,1}, …, m̃_{H,s}, es decir es igual al polinomio minimal m̃_{H} de M_{H}.

La complejidad del straight–line program β_{2} es la siguiente: ya estimamos la compejidad del ciclo i_{0}– ésimo, para obtener a β_{2} iteramos s − 1 veces el ciclo anterior, por lo tanto la complejidad es O(S̃(n + deg(H))(∑_{i=1}^{s} D_{i})) en espacio y O((T̃ deg(H) + n^{4})((s − 1)D_{s}^{2} + (s − 2)D_{s−1}^{2} + … + D_{2}^{2}) log^{2} d^{n} log log d^{n}) ≤ ≤ O((T̃ deg(H) + n^{4})(s^{2}D_{s}^{2}) log^{2} d^{n} log log d^{n}) en tiempo.

Tomando en cuenta la relación de congruencia

m_{H} ≡ m̃_{H} = ∏_{i=1}^{s} \frac{u_{i}}{γ̃_{i}} módulo (ε)^{deg(H)d^{n}}

en Q[ε^{1/d}][T] (ver 43) y del hecho que deg(m_{H}) ≤ deg(H)d^{n} (ver 28) deducimos que se obtiene el polinomio m_{H} a partir del cálculo, para cada 1 ≤ k ≤ D_{s}, para cada 1 ≤ i ≤ s, de la expansión en series de potencias (en ε^{1/d}) hasta grado deg(H)d^{n} del k–ésimo coeficiente a_{(k,i)} del polinomio \frac{u_{i}}{_{γ_{i}}}. Dado que para cada 1 ≤ i ≤ s los polinomios γ_{i}a_{(0,i)}, …, γ_{i}a_{(D_{i},i)}, γ_{i} ∈ Q[ε^{1/d}] fueron calculados por un straightline program sin divisiones, podemos computar los polinomios a_{(0,i)}, …, a_{(D_{i},i)} utilizando el Lema 5. Esto se realiza en espacio O(S̃ deg(H)(n + deg(H))(D_{1}^{2} + … + D_{s}^{2})) y tiempo O((T̃ n deg(H) + n^{4}) deg(H)(D_{1}^{3} + … + D_{s}^{3}) log^{3} d^{n} log^{2} log d^{n}). Por último se calcula el producto ∏_{i=1}^{s} \frac{u_{i}}{γ_{i}}, que no cambia la complejidad asintótica final. La compejidad final entonces es O(S̃ deg(H)(n + deg(H))(D_{1}^{2} + … + D_{s}^{2})) en espacio y O((T̃ deg(H) + n^{4}) max(∑_{i=1}^{s} D_{i}^{3}; ∑_{i=1}^{s}(s − 1 − i)D_{i}^{2}) log^{2} d^{n} log log d^{n}) ≤ O((T̃ deg(H) + n^{4}) max(sD_{s}^{3}; s^{2}D_{s}^{2}) log^{2} d^{n} log log d^{n}) en tiempo.

Si el polinomio q ∈ Q[T] correspondiente a la solución geométrica de V′ es irreducible en Q[T], el algoritmo anterior tiene las complejidades del algoritmo de [HMW99, Theorem 11]. Eso es lo que dice la siguiente Observación:

Observación 46 Si el polinomio q ∈ Q[T] correspondiente a la solución geométrica de V′ es irreducible en Q[T] (es decir s = 1), existe un straight–line program que computa los coeficientes del polinomio minimal m_{H} ∈ Q[ε][T] que satisface la condición m_{H}(ε, H) ∈ (F_{1}, …, F_{n}) utilizando espacio O((S + n + log d) deg(H)(n + deg(H))(d^{2n})) y tiempo O(((T + n + log d) deg(H) + n^{4})d^{3n} log^{2} d^{n} log log d^{n}).

Demostración.– Bajo estas hipótesis, el straight–line program β_{1} definido en el Teorema anterior computa un polinomio γ ∈ Q[ε^{1/d}] y un polinomio γm̃_{H} ∈ Q[ε^{1/d}, T] y tiene complejidad O((S + n + log d)(n + deg(H))(d^{n})) en espacio y O(((T + n + log d) deg(H) + n^{4})(d^{2n}) log^{2} d^{n} log log d^{n}) en tiempo. Tomando en cuenta la relación de congruencia

m_{H} ≡ m̃_{H} módulo (ε)^{deg(H)d^{n}}

en Q[ε^{1/d}][T] (ver 43) y del hecho que deg(m_{H}) ≤ deg(H)d^{n} (ver 28) deducimos que se obtiene el polinomio m_{H} a partir del cálculo, para cada 1 ≤ k ≤ deg(m_{H}), de la expansión en series de potencias hasta grado deg(H)d^{n} del k–ésimo coeficiente a_{(k)} del polinomio \frac{γ_{m_{H}}}{γ}. Para ello utilizando el Lema 5. Esto se realiza en espacio O((S +n+log d) deg(H)(n+deg(H))((d^{n})^{2})) y tiempo O(((T +n+log d)n deg(H)+ n^{4}) deg(H)((d^{n})^{3}) log^{3} d^{n} log^{2} log d^{n}).

References

[Abd97] J. Abdeljaoued. Algorithmes rapides pour le Calcul du Polynôme Caractéristique. PhD thesis, Université de Franche Compte, Besançon, France, 1997.

[ABRW96] M. E. Alonso, E. Becker, M.-F. Roy, and T. Wörmann. Zeroes, multiplicities and idempotents for zerodimensional systems. In Algorithms in Algebraic Geometry and Applications. Proceedings of MEGA’94, volume 142 of Progress in Mathematics, pages 1–15. Birkhäuser, 1996.

[AHU76] A.V. Aho, J.E. Hopcroft, and J.D. Ullman. The design and analysis of computer algorithms. Addison–Wesley, Reading, Massachusetts, 1976.

[AM69] M.F. Atiyah and I.G. Macdonald. Introducción al Algebra Conmutativa. Editorial Reverté, S.A., 1969.

[Amo96] F. Amoroso. On a conjeture by c. bernstein and a. yger. In L. González-Vega and T. Recio, editors, Algorithms in Algebraic Geometry and Aplications, volume 143 of Progress in Mathematics, pages 17–28. Elsevier Science Publishers, 1996.

[AS88] W. Auzinger and H.J. Stetter. An elimination algorithm for the computation of all zeros of a system of multivariate polynomial equations. International Series of Numerical Mathematics, 80:11–30, 1988.

[BCA97] P. Bürgisser, M. Clausen, and M. Amin Shokrollahi. Algebraic Complexity Theory, volume 315 of Grundlehren der mathematischen Wissenschaften. Springer, 1997.

[BCW82] H. Bass, E. Conelle, and T. Wright. The jacobian conjeture: Reduction of degree and formal expansion of the inverse. Bull. AMS, 7(1), 1982.

[BDG88] J. L. Balcázar, J. Díaz, and J. Gabarró. Structural complexity I, volume 11 of EATCS. Springer, 1988.

[BGHM97] B. Bank, M. Giusti, J. Heintz, and G. Mbakop. Polar varieties and efficient real equation solving: The hypersurface case. J. of Complexity, 13(1):5–27, 1997.

[BM72] A. Borodin and J. Munro. The Computational Complexity of Algebraic and Numeric Problems. Elsevier, 1972.

[Bor93] A. Borodin. Time space tradeoffs (getting closer to the barrier ?). In Algorithms and Computation. Proceedings 4. ISSAC, volume 762 of LNCS, pages 209–220. Springer, 1993.

[BP94] D. Bini and V. Pan. Polynomial and matrix computations. Progress in theoretical computer science. Birkhäuser Boston–Basel–Berlin, 1994.

[Bro87] D. W. Brownawell. Bounds for the degree in the nullstellensatz. Annals of Math., 126:577–591, 1987.

[BS88] D. Bayer and M. Stillman. On the complexity of computing syzygies. Journal of Symbolic Computation, 6:135–147, 1988.

[BS98] E. Bach and J. Shallit. Algorithmic Number Theory, volume I of Foundations of Computing. MIT Press, Cambridge, Massachusetts, London, England, 1998.

[Buc85] B. Buchberger. Gröbner bases: An algoritmic method in polynomial ideal theory. In N. K. Bose et al, editor, Multidimensional System Theory, pages 374–383. Reidel, Dordrecht, 1985.

[BY91a] C. Berenstein and A. Yger. Effective Bézout identities in Q[X_{1}, …, X_{n}]. Acta. Math., 166:69–120, 1991.

[BY91b] C. Berenstein and A. Yger. Une formule de jacobi et ses conséquences. Ann. Sci. E.N.S., 24(4):363–377, 1991.

[Caf99] A.A. Cafure. Eliminación geométrica sobre cuerpos finitos, 1999.

[Can88] J. Canny. Some algebraic and geometric problems in PSPACE. In Proceedings 20. ACM STOC, pages 460–467, 1988.

[CG83] A. L. Chistov and D. Y. Grigoriev. Subexponential time solving systems of algebraic equations. LOMI preprint E-9-83, E-10-83, Steklov Institute, Leningrad, 1983.

[CGG91] L. Caniglia, J. A. Guccione, and J. J. Guccione. Local membership problems for polynomial ideals. In T. Mora and C. Traverso, editors, Effective Methods in Algebraic Geometry, volume 94 of Progress in Mathematics, pages 31–45. Birkhäuser, 1991.

[CGH88] L. Caniglia, A. Galligo, and J. Heintz. Borne simple exponentielle pour les degrés dans le théorème des zéros sur un corps de charactéristique quelconque. C. R. Acad. Sci. Paris, 307:255–258, 1988.

[CGH89] L. Caniglia, A. Galligo, and J. Heintz. Some new effectivity bounds in computational geometry. In T. Mora et al, editor, Applied Algebra, Algebraic Algorithms and Error Correcting Codes. Proceedings of AAECC-6, volume 357 of LNCS, pages 131–152. Springer, 1989.

[CGH^{+}99] D. Castro, M. Giusti, J. Heintz, G. Matera, and L.M. Pardo. Data structures and smooth interpolation procedures in elimination theory. Manuscrito de 49 hojas, 1999.

[CLO92] D. Cox, J. Little, and D. O’Shea. Ideals, Varieties, and Algorithms: an introduction to computational algebraic geometry and commutative algebra. Undergraduate Texts in Mathematics. Springer Verlag, Berlin, 1992.

[Col67] G.E. Collins. Subresultants and reduced polynomial sequences. Journal of the Association for Computing Machinery, 14:128–142, 1967.

[Dav96] J. H. Davenport. Prooving and certifying polynomial irreducibility. Submitted to Math. Comp., 1996.

[Dav98] J. H. Davenport. Galois group and the simplification of polynomials. Journal, pages 1–17, 1998.

[DFGS91] A. Dickenstein, N. Fitchas, M. Giusti, and C. Sessa. The membership problem for unmixed polynomial ideals is solvable in single exponential time. Discrete Applied Mathematics, 33:73–94, 1991.

[DH88] J. H. Davenport and J. Heintz. Real quantifier elimination is doubly exponential. Journal of Symbolic Computation, 5:29–35, 1988.

[Eis95] D. Eisenbud. Commutative Algebra with a View Toward Algebraic Geometry. GTM 150. Springer, 1995.

[FF63] D.K. Faddeev and V.N. Faddeeva. Computational methods of linear algebra. W.H. Freeman, San Francisco, 1963.

[FG90] Noai Fitchas and A. Galligo. Nullstellensatz effectif et conjecture de serre (théorème de quillen-suslin) pour le calcul formel. Math. Nachr., 149:231–253, 1990.

[FGM90a] N. Fitchas, A. Galligo, and J. Morgenstern. Algorithmes rapides en sequentiel et en parallele pour l’élimination des quantificateurs en Géométrie élementaire. Seminaire sur les structures algebraiques ordonnees, pages 103–145, 1990.

[FGM90b] N. Fitchas, A. Galligo, and J. Morgenstern. Precise sequential and parallel complexity bounds for quantifier elemination over algebraically closed fields. Journal of Pure and Applied Algebra, 67:1–14, 1990.

[FGS95] N. Fitchas, M. Giusti, and F. Smietanski. Sur la complexité du théorème des zéros. In J. Guddat et al, editor, Approximation and Optimization in the Caribbean II, Proceedings 2nd Int. Conf. on Non-Linear Optimization and Approximation, volume 8 of Approximation and Optimization, pages 247–329. Peter Lange Verlag, Frankfurt am Main, 1995.

[Ful84] W. Fulton. Intersection Theory, volume 2 of Ergebnisse der Mathematik. Springer, 1984.

[GH93] M. Giusti and J. Heintz. La détermination des points isolés et de la dimension d’une variété algébrique peut se faire en temps polynomial. In D. Eisenbud and L. Robbiano, editors, Computational Algebraic Geometry and Commutative Algebra, volume XXXIV of Symposia Matematica, pages 216–256. Cambridge University Press, 1993.

[GHH^{+}97] M. Giusti, K. Hägele, J. Heintz, J. E. Morais, J. L. Montaña, and L. M. Pardo. Lower bounds for diophantine approximation. In Proceedings of MEGA’96, volume 117,118, pages 277–317. Journal of Pure and Applied Algebra, 1997.

[GHM^{+}98] M. Giusti, J. Heintz, J. E. Morais, J. Morgenstern, and L. M. Pardo. Straight–line programs in geometric elimination theory. J. of Pure and App. Algebra, pages 1–46, 1998.

[GHMP95] M. Giusti, J. Heintz, J. E. Morais, and L. M. Pardo. When polynomial equation systems can be solved fast ? In G. Cohen, H. Giusti, and T. Mora, editors, Applied Algebra, Algebraic Algorithms and Error Correcting Codes, Proceedings AAECC-11, volume 948 of LNCS, pages 205–231. Springer, 1995.

[GHS93] M. Giusti, J. Heintz, and J. Sabia. On the efficiency of effective nullstellensätze. Computational Complexity, 3:56–95, 1993.

[GJ79] M. Garey and D. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman, San Francisco, 1979.

[GLS99] M. Giusti, G. Leceref, and B. Salvy. A new algorithm to solve polynomial equations implemented en magma system. Manuscrito École Polytechnique, 1999.

[Har77] Robin Hartshorne. Algebraic Geometry, volume 52 of Graduate Texts in Mathematics. Springer, 1977.

[Hei83] J. Heintz. Definability and fast quantifier elimination in algebraically closed fields. Theor. Comput. Sci., 24(3):239–277, 1983.

[HKP^{+}98] J. Heintz, T. Krick, S. Puddu, J. Sabia, and A. Waissbein. Deformation techniques for efficient polynomial equation solving. In T. Lickteig, M. Shub, F. Cucker, M.–F. Roy editors, Journal of Complexity (special issue “Complexity and Continuous Algorithms”), 2000.

[HMPS97] K. Hägele, J. E. Morais, L. M. Pardo, and M. Sombra. On the intrinsic complexity of the arithmetic nullstellensatz. In Proceedings of TERA’97, Córdoba, Argentina, September 1997.

[HMPS98] K. Hägele, J. E. Morais, L. M. Pardo, and M. Sombra. On the intrinsic complexity of the arithmetic nullstellensatz. Preprint 4/99 Depto. Matemáticas, Universidad de Cantabria, Santander, Spain, april 1998.

[HMPW98] J. Heintz, G. Matera, L. M. Pardo, and R. Wachenchauzer. About the intrinsic complexity of elimination. WAIT’97, Buenos Aires, Argentina, 1998.

[HMW99] J. Heintz, G. Matera, and A. Waissbein. On the time–space complexity of geometric elimination procedures. Manuscript 61 pages, submitted to AAECC Journal, 1999.

[HS80] J. Heintz and M. Sieveking. Lower bounds for polynomials with algebraic coefficients. Theo. Comp. Sci., 11:321–330, 1980.

[HS80] J. Heintz and C. P. Schnorr. Testing polynomials which are easy to compute. In Proccedings of ACM 12th Symposium on Theory of Computing , 262-272, 1980.

[HS82] J. Heintz and C. P. Schnorr. Testing polynomials which are easy to compute. In Logic and Algorithmic, volume 30 of Monographie de l’Enseignement Mathématique, pages 237–254, 1982.

[HW75] J. Heintz and R. Wüthrich. An efficient quantifier elimination algorithm for algebraically closed fields of any characteristic. SIGSAM Bulletin, 9(4):11, 1975.

[IM83] O. H. Ibarra and S. Moran. Equivalence of straight-line programs. Journal of the ACM, 30:217–228, 1983.

[IMR81] O. H. Ibarra, S. Moran, and L. E. Rosier. Probabilistic algorithms and straight-line programs for some rank decision problems. Information Processing Letters, 12(5):227–232, 1981.

[Ive73] B. Iversen. Generic local structure of the morphisms in Commutative Algebra, volume 310 of LNM. Springer, 1973.

[Ja’83] J. Ja’Ja’. Time–space tradeoffs for some algebraic problems. Journal of the Association for Computing Machinery, 30(3):657–667, 1983.

[Kal86] E. Kaltofen. Uniform closure properties of P-computable functions. In Proceedings of the 18th Ann. ACM Symposium on Theory of Computing (Berkeley, CA), pages 330–337, New York, 1986. ACM, ACM Press.

[Kal94] E. Kaltofen. Asymptotically fast solution of toeplitz–like singular linear systems. In J. von zur Gathen and M. Giesbrecht, editors, Proceedings of the 1994 International Symposium on Symbolic and Algebraic Computation, ISSAC’94 (Oxford, July 20–22 1994), ACM Press, pages 297–304, New York, 1994. ACM.

[Kol88] J. Kollár. Sharp effective nullstellensatz. J. of the AMS, 1:963–975, 1988.

[KP96] T. Krick and L. M. Pardo. A computational method for diophantine approximation. In L. González-Vega and T. Recio, editors, Algorithms in Algebraic Geometry and Applications. Proceedings of MEGA’94, volume 143 of Progress in Mathematics, pages 193–254. Birkhäuser Verlag, 1996.

[Kro82] L. Kronecker. Grundzüge einer arithmetischen theorie de algebraischen grössen. J. reine angew. Math., 92:1–122, 1882.

[Kru28] W. Krull. Primidealketten in allgemmeinen ringbereichen. S.–B. Heidelberg Akad. Wiss., 7, 1928.

[KSS97] T. Krick, J. Sabia, and P. Solernó. On intrinsic bounds in the nullstellensatz. Applicable Algebra in Engineering Communications and Computing (AAECC Journal), 8:125–134, 1997.

[Kun85] E. Kunz. Introduction to Commutative Algebra and Algebraic Geometry. Birkhäuser, 1985.

[Laz81] D. Lazard. Résolution des systèmes d’équations algébriques. Theo. Comp. Sci., 15:77–110, 1981.

[LV93] D. Lazard and A. Valibouze. Computing subfields: reverse and primitive element problem. In Proceedings MEGA ‘92, volume 109 of Progress in Mathematics, pages 163–176. Bifhäuser, Boston, 1993.

[Mat86] H. Matsumura. Commutative Ring Theory. Cambridge University Press, 1986.

[Mat97] G. Matera. Sobre la complejidad en espacio y tiempo de la eliminación geométrica. PhD thesis, Universidad de Buenos Aires, Argentina, 1997.

[Mis93] B. Mishra. Algorithmic Algebra. Springer Verlag, New York, 1993.

[ML78] R. A. De Millo and R. J. Lipton. A probabilistic remark on algebraic program testing. Inf. Proc. Letters, 7(4):193–195, 1978.

[MM82] E. Mayr and A. Meyer. The complexity of the word problem for commutative semigroups. Adv. in Math., 46:305–329, 1982.

[MMP96] J. L. Montaña, J. E. Morais, and L. M. Pardo. Lower bounds for arithmetic networks II: Sum of betti numbers. Applicable Algebra in Engineering Communications and Computing, 7:41–51, 1996.

[Mor97] J. E. Morais. Resolución eficaz de sistemas de ecuaciones polinomiales. PhD thesis, Universidad de Cantabria, Santander, Spain, 1997.

[MP93] J. L. Montaña and Luis M. Pardo. Lower bounds for arithmetic networks. In AAECC-4, AAECC, pages 1–24. Springer, 1993.

[Mum88] David Mumford. The Red Book of Varieties and Schemes, volume 1358 of LNM. Springer, Berlin, 1 edition, 1988.

[Mus78] D. R. Musser. On the efficiency of a polynomial irreducibility test. J. ACM, 25:271–282, 1978.

[Ost54] A. M. Ostrowski. On two problems in abstract algebra connected with horner’s rule. In Studies in Math. and Mech. presented to Richard von Mises, pages 40–48. Academic Press, 1954.

[Par95] Luis M. Pardo. How lower and upper complexity bounds meet in elimination theory. In G. Cohen, H. Giusti, and T. Mora, editors, Applied Algebra, Algebraic Algorithms and Error Correcting Codes. Proceedings of AAECC-11, volume 948 of LNCS. Springer, 1995.

[Phi91] P. Philippon. Sur des hauteurs alternatives, I. Math. Ann., 289:255–283, 1991.

[Phi94] P. Philippon. Sur des hauteurs alternatives, II. Ann. Inst. Fourier, Grenoble, 44(2):1043–1065, 1994.

[Phi95] P. Philippon. Sur des hauteurs alternatives, III. J. Math. Pures Appl., 74:345–365, 1995.

[Rou96] F. Rouillier. Algorithmes efficaces pour l’étude des zéros réels des systèmes polynomiaux. PhD thesis, Université de Rennes I, France, 1996.

[Sch80] J. T. Schwartz. Fast probabilistic algorithms for verification of polynomial identities. Journal of the ACM, 27(4):701–717, October 1980.

[Sen90] J.R. Sendra. Algoritmos simbólicos de Hankel en álgebra computacional. PhD thesis, Universidad de Alcalá de Henares, Madrid, Spain, 1990.

[Sha84] I.R. Shafarevich. Basic algebraic geometry. Graduate Texts in Mathematics. Springer-Verlag, 1984.

[Sie72] M. Sieveking. Algorithm for division of power series. Computing, 10:153–156, 1972.

[SL92] R. Sendra and J. Llovet. An extended polynomial gcd algorithm using hankel matrices. Journal of Symbolic Computation, 13:25–39, 1992.

[Som96] M. Sombra. Bounds for the hilbert function of polynomial ideal and for the degrees in the nullstellensatz. In Proceedings of MEGA’96. North-Holland, 1996.

[SS94] M. Shub and S. Smale. Complexity of Bézout’s theorem V: Polynomial time. Theor. Comp. Sci., 133:141–164, 1994.

[SS96] J. Sabia and P. Solernó. Bounds for traces in complete intersections and degrees in the nullstellensatz. Applicable Algebra in Engineering Communications and Computing (AAECC Journal), 6:353–376, 1996.

[Str73] V. Strassen. Vermeidung von divisionen. Crelle J. Reine Angew. Math,, 264:182–202, 1973.

[Str90] V. Strassen. Algebraic complexity theory. In Handbook of Theoretical Computer Science, chapter 11, pages 634–671. Elsevier, 1990.

[vdW54] B.L. van der Waerden. Science Awakening. P. Noordhoff Ltd. – Groningen, Holland, 1954.

[Vog84] W. Vogel. Results on Bezout’s Theorem. Tata Institute of Fundamental Research. Springer, 1984.

[vzG86] J. von zur Gathen. Parallel arithmetic computations: a survey. In B. Rovan J. Gruska and J. Wiedermann, editors, Proceedings of the 12th Symposium on Mathematical Foundations of Computer Science, volume 233 of LNCS, pages 93–112, Bratislava, Czechoslovakia, August 1986. Springer.

[vzG93] J. von zur Gathen. Parallel linear algebra. In John H. Reif, editor, Synthesis of Parallel Algorithms. Morgan Kaufmann, 1993.

[Wai99] A. Waissbein. Eliminación en la argentina. Master’s thesis, FCEyN, Universidad de Buenos Aires, Argentina, 1999.

[Wal78] R.J. Walker. Algebraic curves. Springer-Verlag, Berlin Heidelberg New York, 1978.

[WB93] V. Weispfenning and T. Becker. Groebner bases: a computational approach to commutative algebra, volume 141 of Graduate Texts in Mathematics: readings in mathematics. Springer, 1993.

[Wei88] V. Weispfennig. The complexity of linear problems in fields. Journal of Symbolic Computation, 5(5):3–27, 1988.

[Yap91] C.K. Yap. A new lower bound construction for commutative thues systems with applications. Journal of Symbolic Computation, 12:1–27, 1991.

[Zar95] O. Zariski. Algebraic surfaces. Classics in Mathematics. Springer Verlag, 1995.

[Zip79] R. Zippel. Probabilistic algorithms for sparse polynomials. In Proceedings EUROSAM’ 79, volume 72 of LNCS, pages 216–226, 1979.

[Zip90] R. Zippel. Interpolating polynomials from their values. J. Symbol. Comput., 9:147–175, 1990.

[Zip93] R. Zippel. Effective Polynomial Computation. ECS 241. Kluwer Academic Publishers, 1993.