Deformation Techniques for Efficient Polynomial Equation Solving

Joos HEINTZ, Teresa KRICK, Susana PUDDU, Juan SABIA and Ariel WAISSBEIN

February 17^{th}, 1998

Abstract

Suppose we are given a parametric polynomial equation system encoded by an arithmetic circuit, which represents a generically flat and unramified family of zero-dimensional algebraic varieties. Let us also assume that there is given the complete description of the solution of a particular unramified parameter instance of our system. We show that it is possible to “move” the given particular solution along the parameter space in order to reconstruct —by means of an arithmetic circuit— the coordinates of the solutions of the system for an arbitrary parameter instance. The underlying algorithm is highly efficient, i.e. polynomial in the syntactic description of the input and the following geometric invariants : the number of solutions of a typical parameter instance and the degree of the polynomials occurring in the output.

In fact, we prove a slightly more general result, which implies the previous statement by means of a well-known primitive element algorithm. We produce an efficient algorithmic description of the hypersurface obtained projecting polynomially the given generically flat family of varieties into a suitable affine space.

Keywords: Polynomial equation system, arithmetic circuit, shape (or primitive element) lemma, Newton–Hensel iteration. Subject classification: 68C25

1 Introduction

Suppose we have a (nonparametric) equation system given by sparse polynomials and assume that this equation system defines a zero–dimensional variety. Replacing some of the coefficients in the given polynomials by indeterminates we obtain a parametric equation system. If we take care that this replacement of coefficients by indeterminates produces a generically flat and unramified family of zero–dimensional varieties with underlying finite morphism, we may move the indeterminate coefficients to a certain value (e.g. the value zero, introducing thus more sparsity in the moved equation system). If we are finally able to solve this new simplified equation system we will also be able to solve efficiently the original equation system. Typical examples of equation systems where this method can be applied easily are the socalled “Pham systems” (see [LV98], [MP97]). By the method exposed in this paper we are able to solve such systems in time which is polynomial in their Bézout-number (without hiding an extra exponential factor of 2^{n} as in [MP97]). This example also shows that the good algebraic and geometric properties of Pham systems do not help much to produce low complexities for their solution which seems intrinsically high (namely exponential).

Since a long time there exist numerical and symbolic attempts to solve polynomial equation systems by means of deformation techniques based on a perturbation of the original equation system and subsequent path–following methods (see e.g. [AS88], [CG83], [SS94], [Can90], [GH93], [KP96], [VH94] for the algebraically closed case and [GV88], [HRS90], [Ren92], [BPR97] for the real case). The drawback of these methods is that they typically introduce spurious solutions which may be expensive to identify and to eliminate. In this sense our method is quite different because it requires and makes possible a more careful use of perturbations in such situations.

The original aim of this paper is a better understanding of the main algorithmic idea contained in the papers [GHH^{+}97], [GHM^{+}98],[GHMP97], [Mor97], [HMPS98] and [BGHM]. For this purpose it is necessary to isolate this main idea. In this way we will also obtain an explanation for the long list of assumptions on the input equation system which appears in all statements of the papers mentioned before. On the other hand these assumptions seem to be quite natural, in the sense that they occur in many mathematical and even practical applications of polynomial equation solving (e.g. in calibration problems of robots, see [Kov90]).

A secondary aim of our paper is the analysis of the relation of our symbolic method to solve polynomial equation systems with the numerical methods of [SS93a, SS93b, SS93c, SS96b, SS94] which are also based on ideas of deformation in combination with the classical Newton algorithm (see also [Cas97]). In this contribution we limit ourselves to the problem of finding a way for uncoupling the variables of the original equation system. In view of the shape (or primitive element) lemma used in [KP96], [GHM^{+}98] such an uncoupling can easily be extended to a complete solution of the given polynomial system.

An important outcome of this paper is the following “golden rule” (in the spirit of A. Schönhage, [SGV94]):

Be careful in selecting the projections when dealing with zero-dimensional elimination problems. Avoid generic primitive elements!

This paper aims to illustrate that by a careful choice of the direction of projection of a given zero-dimensional variety (or a given generically flat and unramified family of zero-dimensional varieties) the degree of the output equation may be small and that this degree influences stronlgy the complexity of the algorithm. This observation is the key point of our examples and might be decisive for future (hopefully successful) computer implementations (see [GHL^{+}97], [TER97], [Bru98]). Finally, let us mention the relation between our work and Groebner solving ([Buc85], [WB93], [Mis93]): parametric equation solving is particularly intricate for rewriting based methods. The corresponding algorithms solve the parametric polynomial equation systems by means of comprehensive Groebner bases. Since the output polynomials of the algorithmic problems under considerations are typically dense and contain many (parameter) variables, any rewriting based method faces here a big complexity problem just for writing down the resulting output.

1.1 Terminology

Before stating our results precisely let us fix some terminology and notations :

If f_{1}, …, f_{s} are polynomials in n indeterminates with coefficients in the field of rational numbers Q, we will denote by (f_{1}, …, f_{s}) the ideal spanned by them in Q[X_{1}, …, X_{n}], and by rad(f_{1}, …, f_{s}) its radical ideal. The algebraic varieties V we consider in the sequel will always be affine, their points having coordinates in C, the field of complex numbers. These varieties will be defined by explicit polynomial equations having coefficients in Q. The coordinate ring of V is denoted by Q[V]. The dimension of a variety V, denoted by dim(V), is defined in the usual way as the maximum of the Krull dimensions of its irreducible components. We call a variety equidimensional if all its components have the same dimension. Following [Hei83] we define the degree deg(V) of the variety V as the sum of the degrees of all its irreducible components. As usual, A^{n} denotes the n−dimensional affine space C^{n} equipped with its Zariski topology. Finally, Z and N will denote the ring of rational integers and the set of natural numbers.

For the precise statement of our main result, it is necessary to explain what we mean by a “description of a geometric solution of a given zero–dimensional equation system (or variety)”. In fact such a description is based on the main content of the shape (or primitive element) lemma for the description of the radical of a zero–dimensional ideal (see [Kro82], [Zar95, Chapter 1], [Nar66], [GM89], [Koe03], [Mac96, Chapter II] and [CG83] for early forms of such shape lemmas). Our (implicit) use of such shape lemmas is algorithmic and follows [GH93], [KP96], [GHM^{+}98], [GHH^{+}97],

[HMPS98] and [TER97].

Definition 1 Let X := (X_{1}, …, X_{n}) and Y be indeterminates over Q. Let f_{1}, …, f_{s} ∈ Q[X] be polynomials defining a zero–dimensional variety V ⊂ A^{n}. A description of a geometric solution of the system f_{1} = 0, …, f_{s} = 0 (or of the variety V) is given by a (nonzero) Q–linear form U := λ_{1}X_{1} + ⋯ + λ_{n}X_{n} and n + 1 univariate polynomials q, v_{1}, …, v_{n} ∈ Q[Y] such that the following conditions are satisfied:

i) V = {(v_{1}(η), …, v_{n}(η)); η ∈ C , q(η) = 0} and {η ∈ C ; q(η) = 0} = {U(ξ); ξ ∈ V }.

ii) the polynomial q is monic of degree #V and the degrees of v_{1}, …, v_{n} are strictly less than #V.

In such a description, we require U and q, v_{1}, …, v_{n} to be given by the arrays of their coefficients.

Let us here observe that the condition deg q = #V and condition i) are equivalent to the usual Shape Lemma statement:

iii) rad(f_{1}, …, f_{s}) = (q(U), X_{1} − v_{1}(U), …, X_{n} − v_{n}(U)).

1.2 The main result

We are now ready to state our main result. For the unfamiliarized reader, the notion of division–free arithmetic circuit will be made explicit in Section 1.3.

Theorem 2 Let T := (T_{1}, …, T_{m}), X := (X_{1}, …, X_{n}) and Y be indeterminates over Q. Let F_{1}, …, F_{n} and G ∈ Q[T, X] be polynomials given by a division–free arithmetic circuit β in Q[T, X] . Suppose that the polynomials F_{1}, …, F_{n} define an equidimensional subvariety V of A^{m} × A^{n} = A^{m+n} of dimension m, and that the morphism of affine varieties π : V → A^{m} induced by the canonical projection of A^{m} × A^{n} onto A^{m} is finite and surjective. Suppose furthermore that π is generically unramified (in the scheme– theoretical sense). Let π̃ : V → A^{m+1} be the (finite) morphism of affine varieties defined by π̃(v) := (π(v), G(v)) for v ∈ V and let P (T, Y) ∈ Q[T, Y] be the minimal equation of the image variety π̃(V) (interpreted as a closed affine subvariety of A^{m+1} of codimension 1). Suppose that there is given a point t = (t_{1}, …, t_{m}) ∈ Q^{m} satisfying the condition that its (finite) fiber π^{−1}(t) is (scheme–theoretically) unramified and that G maps π^{−1}(t) onto deg_{Y} P distinct points of A^{1}. Assume finally that there is given a description of a geometric solution of the fiber π^{−1}(t) (see Definition 1). Then, if the length and the nonscalar depth of β are bounded by L and λ respectively, d is an upper bound for deg_{X} F_{1}, …, deg_{X} F_{n} and D := deg π, there exists a divisionfree arithmetic circuit γ in Q[T] with the following properties:

i) γ computes the coefficients of the polynomial P with respect to the main variable Y.

ii) γ has size O(d^{2}n^{7} deg_{T}^{2} P log(deg_{T} P)L) + D^{O(1)} deg_{T}^{2} P log(deg_{T} P).

iii) γ has nonscalar depth O((log n + λ) log(deg_{T} P) + log D).

Moreover, there exists a uniform family of arithmetic networks of asymptotically the same size and nonscalar depth than γ which produces γ from the following data:

– the input arithmetic circuit β.

– the rational numbers which represent the coordinates of t and the given description of a geometric solution of the fiber π^{−1}(t).

We will say that the polynomials F_{1}, …, F_{n}, G describe the general instance of the elimination problem we are considering in Theorem 2. The solution of this general problem instance will be given by the polynomial P, and the output we are looking for is a division–free straight–line program γ in Q[T] which evaluates the coefficients of the polynomial P with respect to the variable Y. We call T := (T_{1}, …, T_{m}) the parameters and X := (X_{1}, …, X_{n}) the variables of our general problem instance. Each parameter point τ ∈ A^{m} determines a specific problem instance which is given by the polynomials F_{1}(τ, X), …, F_{n}(τ, X), G(τ, X) and which has a solution represented by the specialized polynomial P (τ, Y). Observe that the n–variate polynomial P (τ, G(τ, X)) vanishes on the zero–dimensional variety π^{−1}(τ). Thus, if we map by G(τ, X) the common zeroes of the polynomial equation system F_{1}(τ, X) = 0, …, F_{n}(τ, X) = 0 into the affine space A^{1}, the polynomial P (τ, Y) vanishes on each image point of this map and, for a generically chosen point τ ∈ A^{m}, exactly on them. Moreover, since the polynomial P (T, Y) is monic in Y, we have P (τ, Y) ≠ 0 for any parameter point τ ∈ A^{m}. In this sense, the elimination problem we are considering (namely that of finding a straight–line program representation for the polynomial P starting with the given data F_{1}, …, F_{n}, G and t) is of parametric nature.

How do we proceed if our task is to find for an arbitrarily given parameter point τ ∈ Q^{m} a description of a geometric solution of the zero–dimensional variety defined by the equations F_{1}(τ, X), …, F_{n}(τ, X)? In this case we choose a generic linear form U := λ_{1}X_{1} + ⋯ + λ_{n}X_{n} of Q[X_{1}, …, X_{n}] and compute solutions for the 2n specific problem instances F_{1}(τ, X), …, F_{n}(τ, X), X_{i} and F_{1}(τ, X), …, F_{n}(τ, X), U − λ_{i}X_{i}, where 1 ≤ i ≤ n. From these solution polynomials we compute now easily a description of the geometric solution of the polynomial equation system F_{1}(τ, X) = 0, …, F_{n}(τ, X) = 0 applying the algorithms subjacent to [KP96], Lemma 26, Proposition 27 and Theorem 22.

In order to enlighten the long list of assumptions for our input equation system in Theorem 2, let us comment here some of its aspects :

i) Under the assumption that V is equidimensional and that π is finite and surjective, the condition of π being generically unramified in the scheme-theoretical sense is equivalent to the requirement that the polynomials F_{1}, …, F_{n} span a radical ideal in Q(T)[X]. Thus, under the assumptions of Theorem 2, if F_{1}, …, F_{n} form a regular sequence in Q[T, X], it turns out that the ideal (F_{1}, …, F_{n}) is a radical ideal of Q[T, X].

ii) As the image of π̃ is an hypersurface of A^{m+1}, its minimal polynomial P (T, Y) is well defined. Since Q is a perfect field, the minimal polynomial P (T, Y) is square free and since the morphism π is finite, P (T, Y) is monic in Y. The polynomial P (T, G) vanishes on the variety V and belongs to the ideal spanned by F_{1}, …, F_{n} in Q(T)[X]. Moreover, if F_{1}, …, F_{n} is a regular sequence in Q[T, X] , the polynomial P (T, G) belongs to the ideal spanned by F_{1}, …, F_{n} in Q[T, X].

iii) The assumption that the given parameter point t = (t_{1}, …, t_{m}) ∈ Q^{m} has a scheme-theoretically unramified fiber π^{−1}(t) means that the specialized ideal (F_{1}(t, X), …, F_{n}(t, X)) is radical in Q[X]. This, in turn, implies that the fiber π^{−1}(t) contains only smooth points of the variety V, having regular local rings. Thus, the semilocal ring

Q[T]_{(T_{1}−t_{1},...,T_{m}−t_{m})}[X]/(F_{1}, …, F_{n})

is Cohen–Macaulay and from the finiteness of π we deduce that

#π^{−1}(t) = dim_{Q(T)} Q(T)[X]/(F_{1}, …, F_{n})

holds (here #π^{−1}(t) denotes the cardinality of the set π^{−1}(t) and

dim_{Q(T)} Q(T)[X]/(F_{1}, …, F_{n}) denotes the dimension of the Q(T)–vector space Q(T)[X]/(F_{1}, …, F_{n})). In other words, #π^{−1}(t) equals the cardinality D = deg π of the generic fiber of π. This fact may also be circumscribed as the generic flatness of the morphism π. Moreover the given description of a geometric solution of the fiber π^{−1}(t) provides an explicit description of the multiplication tensor of the Q–algebra Q[X]/(F_{1}(t, X), …, F_{n}(t, X)).

iv) The assumption that G maps the fiber π^{−1}(t) onto deg_{Y} P distinct points of A^{1} is equivalent to the requirement that the specialized polynomial P (t, Y) := P (t_{1}, …, t_{m}, Y) ∈ Q[Y] is square–free, i.e. that the discriminant of P (T, Y) as a polynomial in Y does not vanish on the point t.

v) Finally observe that by our assumptions the squarefreeness of P (T, Y) and the generical unramifiedness of π can be expressed as consistent Zariski open conditions in A^{m}. Therefore, there always exists a point t satisfying our requirements.

Let us observe that in case D ≪ deg V and deg P ≪ deg V. deg G the algorithm underlying Theorem 2 is particularly efficient for the purpose of representing P by a “short” straight–line program. In many (mathematical) applications, D and deg P are relatively small numbers whereas deg V tends to be close to the “global” Bézout–number \overline{δ} := ∏_{1≤i≤n} deg_{T,X} F_{i}.

It may even occur that the “local” Bézout–number δ := ∏_{1≤i≤n} deg_{X} F_{i} remains ac-

ceptable for computational purposes whereas \overline{δ} becomes exorbitant. Let us recall that d was a given upper bound for deg_{X} F_{1}, …, deg_{X} F_{n}. Let us suppose that there is also given an upper bound \overline{d} for deg_{T,X} F_{1}, …, deg_{T,X} F_{n}. With this notation one deduces easily from the Bézout Inequality in its simplest form (see e.g. [Hei83], [Ful84], [Vog84], [Sch95], [Som97] and [SS96a]) the following estimates:

D ≤ deg V, δ ≤ \overline{δ},

deg V ≤ \overline{δ} ≤ \overline{d}^{n}, D ≤ δ ≤ d^{n},

deg P ≤ deg V. deg G ≤ \overline{δ}. deg G ≤ \overline{d}^{n}. deg G,

deg_{Y} P ≤ D ≤ δ ≤ d^{n}.

Let us also mention that, disregarding the aspect of nonscalar complexity, the estimates of Theorem 2 concerning the size of the straight–line program γ and the arithmetic network producing γ may be refined to the more accurate bound

O(d^{2}n^{3} deg_{T}^{2} P log(deg_{T} P)L + D^{2} log D log log D deg_{T}^{2} P log(deg_{T} P)).

This means that sequential time, roughly quadratic in the degrees of the morphism π and the output polynomial P, and linear in the length of the input circuit β, suffices to represent the polynomial P by a straight–line program γ. The highlight of this complexity outcome is that the underlying algorithm can be executed in storage space which is almost linear in the geometric quantities n, D and deg_{T} P and the memory space necessary to evaluate the circuit β in time L (in all these considerations we are disregarding a logarithmic factor). Since these accurate complexity results are not within the scope of this paper, we refer to [TER97], where suitable methods which allow to refine our algorithmic results in the indicated direction can be found.

Although in this paper we are not concerned with explicit bit complexity aspects, the nonscalar parallel and sequential time estimations of Theorem 2 allow to control suitably the height of the rational numbers occurring as intermediate and final results of our computations if the height of the parameters of the input circuit β and of the point t and its fiber π^{−1}(t) are given. For a sufficiently generic input point t, we are even able to control the logarithmic height of the output polynomial P in this way (see [HMPS98]). On the other hand, the rational numbers representing the parameters of the input circuit β, the input point t and the given description of a geometric solution of the fiber π^{−1}(t), may be given in their turn by a straight– line program α in Q, which computes them from the input bits 0 and 1. Under these circumstances our complexity results do not change substantially. In particular, if the straight–line program α describing the data β, t and π^{−1}(t) is again of length bounded by L, the asymptotic order of the sequential time of the algorithm underlying Theorem 2 remains unchanged.

Our paper contains also a refinement of the above mentioned result for the case that the Galois group of C over Q does not act transitively on the fiber π^{−1}(t) (see Corollary 8 below). Finally, we illustrate the usefulness of our main result Theorem 2 and of our method by means of two classical computational examples.

1.3 The computational model

Our algorithms will be realized by uniform families of arithmetic networks (arithmetic Boolean circuits) over Q. An arithmetic network is a pair Γ = (G, Q), where G is a directed acyclic graph and Q is a labeling which assigns to each node of the graph G an arithmetic or Boolean operation. A labeled node is also called a gate of Γ. A node of indegree zero may be labeled by a rational number or by an input variable. A node of indegree one or two may be labeled by an arithmetic operation ∗ ∈ {+, −, ×, ÷} or a Boolean operation. Other nodes act as equality tests (decision gates) or are selector gates associated to an equality test. Some internal nodes of the graph G (among them all those of outdegree zero) are labeled as output gates of the arithmetic circuit Γ. We shall always suppose that Γ is division–free. This means that when evaluating (running) Γ on a generic input (e.g. on its input variables), we will execute —if any— only divisions by nonzero rational numbers. This assumption implies that Γ computes only rational numbers and polynomials with rational coefficients in the input variables. If a node of Γ represents a multiplication of two polynomials of positive degree, we shall call nonscalar this multiplication and this node (gate). We count arithmetic or Boolean operations, equality tests and selections (performed by selector gates) only at unit cost. Thus, any arithmetic operation involving rational numbers or polynomials counts just as one unit, independently of the height of the rational numbers or degree of the polynomials we are processing. In this sense, we associate to a given arithmetic network Γ = (G, Q) two complexity measures:

• sequential time, measured by the size of Γ (i.e., by the number of internal nodes of G).

• nonscalar parallel time, measured by the nonscalar depth of Γ (i.e., by the longest oriented path in G, counting only nodes labeled by nonscalar multiplications).

Sometimes we will also refer to sequential time under storage space restrictions. In this case, time and space are measured by a pebble game on the graph G (see [Bor93]). If Γ is an arithmetic network without decision and selector gates (and, consequently, without Boolean operations), we call it an arithmetic circuit or straight– line program. Thus, our arithmetic circuits will always be division–free and will compute rational numbers and polynomials in the input variables having coefficients in Q.

For the sake of simplicity, we restrict ourselves to the field of rational numbers Q as ground field, contained in the field of complex numbers C. Nevertheless, our arguments can be easily extended to an arbitrary ground field of characteristic zero and any algebraically closed field containing it. With some slight modifications, our methods can be applied to any infinite (or finite, but sufficiently large) perfect ground field of positive characteristic and to its algebraic closure. In both cases, the complexity outcome remains essentially the same as before (see [GH93], [GHM^{+}98] and [GHH^{+}97] for more details).

The (generally multivariate) polynomials over Q we deal with will be encoded in one of the following ways:

i) in dense form, as arrays (vectors) of elements of Q. ii) as arithmetic circuits (straight–line programs).

iii) in mixed representation: in this case, the given polynomial is encoded in dense form with respect to a specific main variable whereas its coefficients with respect to this variable are encoded by an arithmetic circuit.

For precise definitions and elementary properties of the notions arithmetic network and straight–line program see [BCA97], [vzG86], [vzG93] and [KP96].

1.4 Algorithmic tools

The algorithms we are going to design in this paper are based on the following three procedures:

i) A particular symbolic adaptation of the classical Newton–Hensel iteration to the context of polynomial elimination and arithmetic circuits. This consists in fact in a refinement and a simplification of the main algorithmic idea of [GHH^{+}97, Lemma 30], [GHM^{+}98], [GHMP97], [Mor97] and [HMPS98].

ii) Linear algebra routines, like the well–parallelizable polynomial algorithm of Berkowitz for the computation of the characteristic polynomial of a square matrix over any domain ([Ber84] (see also [vzG93] and [TER97]) and greatest common divisor (gcd) computations for multivariate polynomials given in mixed representation (see [Kal85] and [KP96]). This gcd computations may always be executed with sufficient efficiency by means of the algorithm of Berkowitz.

iii) Suitable versions of Strassen’s basic algorithm “Vermeidung von Divisionen” (see [Str73], [KP96] and [GHH^{+}97]).

2 Proofs

The procedure underlying Theorem 2 represents an algorithmic deformation of the given fiber π^{−1}(t) along the parameter variety A^{m}. Implicitly, this procedure makes use of the generic flatness of the morphism π.

The proof of Theorem 2 is based on the consideration of the multiplication tensor in the Q[T_{1}, …, T_{m}]–algebra Q[T_{1}, …, T_{m}, X_{1}, …, X_{n}]/rad (F_{1}, …, F_{n}).

From now on, we will maintain the following notations :

T := (T_{1}, …, T_{m}) and X := (X_{1}, …, X_{n})

Given a parameter point t := (t_{1}, …, t_{m}) belonging to Q^{m}, we shall write T − t := (T_{1} − t_{1}, …, T_{m} − t_{m}) and Q[[T − t]] := Q[[T_{1} − t_{1}, …, T_{m} − t_{m}]] for the power series ring corresponding to T − t.

Observe that the following “algebraic” and “geometric” Q–algebras are isomorphic :

Q[T] ≅ Q[A^{m}] and Q[T, X]/rad (F_{1}, …, F_{n}) ≅ Q[V]

Let us also observe that the generic unramifiedness and the finiteness of the epimorphism π imply that Q[T, X]/(F_{1}, …, F_{n}) ≅ Q[V] holds if F_{1}, …, F_{n} is a regular sequence in Q[T, X].

By assumption, π is a finite morphism mapping the variety V onto the affine space A^{m}. Therefore, Q[T, X]/rad (F_{1}, …, F_{n}) is a finite Q[T]–module containing Q[T] as a subalgebra. Since Q[T] is integrally closed in its fraction field Q(T), the polynomial P ∈ Q[T, Y] we are looking for is the minimal equation of the residue class of G of the quotient ring Q[T, X]/rad (F_{1}, …, F_{n}) over the subalgebra Q[T]. The way we compute the polynomial P is the following: first we approximate in a suitable way a matrix representation of the multiplication tensor of the (reduced) Q(T)–algebra

Q(T)[X]/(F_{1}, …, F_{n})

(the reduceness of this algebra follows from the assumption that π is generically unramified, finite and surjective). For this purpose, we use a suitable Q(T)–vector space basis of this Q(T)–algebra. This basis will be determined by a suitably chosen primitive element U = λ_{1}X_{1} + ⋯+λ_{n}X_{n} of Q[X]. Then we compute a suitable approximation of the characteristic polynomial X_{G}(Y) of the Q(T)–linear map induced by the multiplication by the residue class of G in Q(T)[X]/(F_{1}, …, F_{n}). From the finiteness of the morphism π we deduce that X_{G} belongs to the polynomial ring Q[T, Y]. The given approximation of the characteristic polynomial X_{G} and the knowledge of the fiber π^{−1}(t) (and hence of the polynomial P (t, Y)) allows us to compute an approximation to the polynomial P (see Lemma 7 below). From this approximation we compute an exact representation of the polynomial P by means of a procedure of the type “Vermeidung von Divisionen”. The underlying approximation process is based on the previously mentioned symbolic adaptation of Newton–Hensel lifting in the power series ring Q[[T − t]].

Let us now go further into the details of the proof of Theorem 2.

For this purpose, we explain briefly the ideas involving matrix computations in zero– dimensional algebras. We do this in the particular case of the unramified fiber π^{−1}(t) whose coordinate ring is the reduced Q–algebra

Q[X]/(F_{1}(t, X), …, F_{n}(t, X)).

In order to simplify notations, let us write π^{−1}(t) = {t} × V_{t}, where V_{t} is the zerodimensional subvariety of A^{n} defined by :

V_{t} := { ξ ∈ C^{n}; F_{1}(t, ξ) = 0, …, F_{n}(t, ξ) = 0 }

By assumption, we have at our disposal a description of a geometric solution of V_{t}, i.e. a primitive element U = λ_{1}X_{1} + ⋯ + λ_{n}X_{n} in Q[X] and polynomials q, v_{1}, …, v_{n} ∈ Q[Y] such that the conditions i) and ii) of Definition 1 are satisfied. The polynomial q is monic and has degree deg q = #V_{t} = # π^{−1}(t) = D (recall that π^{−1}(t) unramified implies # π^{−1}(t) = D). Moreover, q is separable and the degrees of the polynomials v_{1}, …, v_{n} are strictly less than D. Furthermore, since (F_{1}(t, X), …, F_{n}(t, X)) is a radical ideal, we have

(F_{1}(t, X), …, F_{n}(t, X)) = (q(U), X_{1} − v_{1}(U), …, X_{n} − v_{n}(U)).  (1)

This implies that

Q[V_{t}] ≅ Q[X]/(F_{1}(t, X), …, F_{n}(t, X)) ≅ Q[Y]/(q(Y))

holds. In particular Q[V_{t}] is a finite dimensional Q−algebra of dimension D. Let us denote the residue class of the linear form U in Q[X]/(F_{1}(t, X), …, F_{n}(t, X)) by u. Note that we may also interpret u as the restriction U|_{V_{t}} of the linear form U to the variety V_{t}. The morphism u : V_{t} ⟶ A^{1} separates the points of V_{t} and it is clear that B := {1, u, …, u^{D−1}} is a Q–vector space basis of Q[X]/(F_{1}(t, X), …, F_{n}(t, X)).

Let us now write V_{t} = {ξ^{(ℓ)}; 1 ≤ ℓ ≤ D}, with ξ^{(ℓ)} = (ξ_{1}^{(ℓ)}, …, ξ_{n}^{(ℓ)}) ∈ A^{n}, and π^{−1}(t) = {(t, ξ^{(ℓ)}); 1 ≤ ℓ ≤ D}. Since the coordinate function u ∈ Q[V_{t}] separates the points of the variety V_{t}, the D distinct roots of the univariate polynomial q (which are algebraic numbers belonging to C) coincide with the image of V_{t} under the map u. Thus we have {y ∈ C; q(y) = 0} = {u(ξ); ξ ∈ V_{t}}. Moreover, from (1) we deduce that for 1 ≤ ℓ ≤ D the identity

ξ^{(ℓ)} = (v_{1}(u(ξ^{(ℓ)})), …, v_{n}(u(ξ^{(ℓ)})))  (2)

holds.

Considering the Q–linear homothety η of Q[X]/(F_{1}(t, X), …, F_{n}(t, X)) induced by the multiplication by u, we see that the matrix M of η with respect to the basis B is the companion matrix of the polynomial q. The eigenvalues of this matrix are exactly the zeroes of the polynomial q, which are all distinct and identical to the D values u(ξ^{(1)}), …, u(ξ^{(D)}). Therefore, there exists a C–vector space basis B′ of the C–algebra C[X]/(F_{1}(t, X), …, F_{n}(t, X)) such that the matrix M′ of the homothety η with respect to the basis B′ has the following diagonal form:

M′ = ( \begin{matrix}u(ξ^{(1)}) & ⋯ & 0 \\ ⋮ & ... & ⋮ \\ 0 & ⋯ & u(ξ^{(D)}) \end{matrix} ) .  (3)

Let us now consider the Q[T]–algebra

Q[T, X]/(F_{1}(t, X), …, F_{n}(t, X)) = Q[T] ⊗ Q[X]/(F_{1}(t, X), …, F_{n}(t, X))

which is clearly a free Q[T]–module having the same basis B as the Q–algebra Q[X]/(F_{1}(t, X), …, F_{n}(t, X)). Observe also that B′ is a basis of the free C[T]–module C[T, X]/(F_{1}(t, X), …, F_{n}(t, X)).

For any polynomial H of Q[X] or Q[T, X], we may consider the homothety η_{H} induced by the multiplication by the residue class h of H in the corresponding algebra. We shall denote the matrices of η_{H} with respect to the basis B and B′ by M_{H} and M′_{H} respectively. These matrices have the same characteristic and minimal polynomials since they are similar. Observe that the homotheties η_{X_{1}}, …, η_{X_{n}} (and therefore the matrices M_{X_{1}}, …, M_{X_{n}} and M′_{X_{1}}, …, M′_{X_{n}}) commute. This implies that, for any polynomial H in Q[T, X]

η_{H} = H(η_{X_{1}}, …, η_{X_{n}}) , M_{H} = H(M_{X_{1}}, …, M_{X_{n}}) and M′_{H} = H(M′_{X_{1}}, …, M′_{X_{n}}).

holds. Let us now analyze the homotheties and matrices η_{X_{1}}, …, η_{X_{n}}, M_{X_{1}}, …, M_{X_{n}} and M′_{X_{1}}, …, M′_{X_{n}}. From (1) we deduce the following identities between Q-linear endomorphisms of Q[X]/(F_{1}(t, X), …, F_{n}(t, X)) and matrices over Q and C:

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

Thus, for any polynomial H in Q[T, X], we obtain the following identities between Q[T]–linear endomorphisms of Q[T, X]/(F_{1}(t, X), …, F_{n}(t, X)) and matrices over Q[T] and C[T] :

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

Since M′ is a diagonal matrix, M′_{H} is a diagonal matrix too and we have :

M′_{H} = ( \begin{matrix}H(T, v_{1}(u(ξ^{(1)})), …, v_{n}(u(ξ^{(1)}))) & ⋯ & 0 \\ ⋮ & ... & ⋮ \\ 0 & ⋯ & H(T, v_{1}(u(ξ^{(D)})), …, v_{n}(u(ξ^{(D)}))) \end{matrix} ) .

From (2), we deduce the representation

M′_{H} = ( \begin{matrix}H(T, ξ^{(1)}) & ⋯ & 0 \\ ⋮ & ... & ⋮ \\ 0 & ⋯ & H(T, ξ^{(D)}) \end{matrix} ) .

In particular, for G(t, X), we have :

M′_{G(t,X)} = ( \begin{matrix}G(t, ξ^{(1)}) & ⋯ & 0 \\ ⋮ & ... & ⋮ \\ 0 & ⋯ & G(t, ξ^{(D)}) \end{matrix} ) .

Therefore, G(t, ξ^{(1)}), …, G(t, ξ^{(D)}) are the eigenvalues of the homothety η_{G(t,X)} and hence of the matrix M_{G(t,X)}. Since these values (eliminating repetitions) are exactly the zeroes of the separable polynomial P (t, Y) and the homothety η_{G(t,X)} is diagonalizable, we deduce that P (t, Y) is the minimal polynomial of M_{G(t,X)}.

Let us now take a little distance from our detailed analysis of matrix computations in the Q–algebra Q[X]/(F_{1}(t, X), …, F_{n}(t, X)), which represents the coordinate ring of the zero–dimensional variety V_{t} and the fiber π^{−1}(t). The outcome of our analysis was the conclusion that the specialized polynomial P (t, Y) is the minimal polynomial of the homothety η_{G(t,X)}, whose representation with respect to the basis B is the matrix M_{G(t,X)}. Our arguments were based on two fundamental assumptions:

– the fiber π^{−1}(t) is zero–dimensional

– the fiber π^{−1}(t) is unramified.

The zero dimensionality and the unramifiedness of the fiber π^{−1}(t) can be expressed algebraically by the fact that Q[X]/(F_{1}(t, X), …, F_{n}(t, X)) is a finite–dimensional, reduced Q–algebra of dimension D = deg π.

Hence, the same argumentation can be applied to the generic fiber of π, which is scheme–theoretically represented by the finite–dimensional reduced Q(T)–algebra Q(T)[X]/(F_{1}, …, F_{n}) of dimension D. Therefore we conclude that the polynomial P is the minimal polynomial of the homothety η_{G} in Q(T)[X]/(F_{1}, …, F_{n}) induced by the multiplication by the residue class of G (observe that the finiteness and the surjectivity of the morphism π and the fact that Q[T] is integrally closed in its fraction field Q(T) implies that the minimal polynomial of η_{G} belongs, in fact, to the Q–algebra Q[T, Y]).

The question is now : how can we compute the minimal polynomial of the homothety η_{G} without determining first a matrix form of the multiplication tensor of the Q(T)– algebra Q(T)[X]/(F_{1}, …, F_{n})? This computation will be done by means of an approximation method based on the Newton–Hensel procedure.

Our first aim is to “lift” algorithmically each point ξ = (ξ_{1}, …, ξ_{n}) of V_{t} = π^{−1}(t) to a n–tuple R^{(ξ)} := (R_{1}^{(ξ)}, …, R_{n}^{(ξ)}) of power series of C[[T − t]] such that the following two conditions hold :

• F_{1}(T, R^{(ξ)}) = 0 , …, F_{n}(T, R^{(ξ)}) = 0

• R^{(ξ)}(t) := (R_{1}^{(ξ)}(t), …, R_{n}^{(ξ)}(t)) = (ξ_{1}, …, ξ_{n}) = ξ.

We will show that, by our unramifiedness assumptions on π and π^{−1}(t) and Lemma 3 below, such a lifting procedure always exists. Thus, the D distinct points R^{(ξ^{(1)})}, …, R^{(ξ^{(D)})} of C[[T −t]]^{n} have coordinates which are algebraic over Q(T) and they form a complete solution set of the zero–dimensional equation system

{ F_{1}(T, X) = 0, …, F_{n}(T, X) = 0 }

over the ground field Q(T). From our previous argumentation one deduces immediately that P (T, Y) is the minimal polynomial of the diagonal matrix

( \begin{matrix}G(T, R^{(ξ^{(1)})}) & ⋯ & 0 \\ ⋮ & ... & ⋮ \\ 0 & ⋯ & G(T, R^{(ξ^{(D)})}) \end{matrix} ) .

This matrix represents the homothety η_{G} in a suitable C(T)–vector space basis of C(T)[X]/(F_{1}, …, F_{n}).

Let M := (T_{1} − t_{1}, …, T_{m} − t_{m}) be the maximal ideal of C[T] corresponding to the parameter point t. Denote by C[T]_{M} and C[T]_{M}[X]/(F_{1}, …, F_{n}) = (C[T][X]/(F_{1}, …, F_{n}))_{M} the localization by M of the corresponding C[T]–modules.

Since the C–algebra C[X]/(F_{1}(t, X), …, F_{n}(t, X)) is reduced we easily see that the Jacobian matrix

( \begin{matrix}\frac{∂F_{1}(t,X)}{∂X_{1}} & … & \frac{∂F_{1}(t,X)}{∂X_{n}} \\ ⋮ & ... & ⋮ \\ \frac{∂F_{n}(t,X)}{∂X_{1}} & … & \frac{∂F_{n}(t,X)}{∂X_{n}} \end{matrix} )

is unimodular over this algebra (this means that the residue class of its determinant is a unit of the algebra). From this we deduce that the Jacobian matrix

DF (X) := DF (T, X) := ( \begin{matrix}\frac{∂F_{1}(T,X)}{∂X_{1}} & … & \frac{∂F_{1}(T,X)}{∂X_{n}} \\ ⋮ & ... & ⋮ \\ \frac{∂F_{n}(T,X)}{∂X_{1}} & … & \frac{∂F_{n}(T,X)}{∂X_{n}} \end{matrix} )  (6)

is also unimodular over the localized C–algebra C[T]_{M}[X]/(F_{1}, …, F_{n}) and that this algebra is, therefore, reduced.

This allows us to state the announced lifting procedure, which is in fact a variant of the Newton–Hensel Lemma (see e.g., [Ive73, Proposition 7.2]). Although this result is well known, we will give a self–contained and constructive proof in order to give a mathematical illustration of the particular algorithmic techniques we are using in this paper.

Lemma 3 Let assumptions and notations be as before. Then, for any point ξ = (ξ_{1}, …, ξ_{n}) ∈ V_{t}, there exists a unique n–tuple R^{(ξ)} = (R_{1}^{(ξ)}, …, R_{n}^{(ξ)}) ∈ C[[T − t]]^{n} of formal power series such that the following two conditions are satisfied:

• F_{1}(T, R^{(ξ)}) = 0, …, F_{n}(T, R^{(ξ)}) = 0

• R^{(ξ)}(t) := (R_{1}^{(ξ)}(t), …, R_{n}^{(ξ)}(t)) = ξ.

Proof.– Our arguments follow the lines of [Mat97]. They are based on the iterated application of the Newton–Hensel operator we are going to explain now:

Let F (X) := (F_{1}(T, X), …, F_{n}(T, X)) and let DF (X) be defined as in (6). The Newton–Hensel operator associated to F (X) is the n–tuple N_{F} (X) of rational functions of Q(T, X) defined by

N_{F} (X)^{t} := ( X_{1} ; ⋮ ; X_{n} ) − DF (X)^{−1} · ( F_{1}(T, X) ; ⋮ ; F_{n}(T, X) ) = X^{t} − DF (X)^{−1} · F (X)^{t}

where ^{t} denotes transposition. The remark made above on the determinant JF (X) of the Jacobian matrix DF (X) implies that the residue classes of the entries of the n-tuple N_{F} (X) are elements of the Q–algebra Q[T]_{M}[X]/(F_{1}, …, F_{n}).

Given ξ ∈ V_{t} we define recursively for each k ∈ Z_{≥0} an n–tuple R^{(k,ξ)} = (R_{1}^{(k,ξ)}, …, R_{n}^{(k,ξ)}) of elements of C[T]_{M} as follows:

\{ \begin{matrix}R^{(0,ξ)} := (R_{1}^{(0,ξ)}, …, R_{n}^{(0,ξ)}) := ξ \\ R^{(k,ξ)} := (R_{1}^{(k,ξ)}, …, R_{n}^{(k,ξ)}) = N_{F} (R^{(k−1,ξ)}) \end{matrix}

The definition may also be rephrased as follows :

R^{(k,ξ)} := N_{F}^{k}(ξ) for any k ∈ Z_{≥0},  (7)

where N_{F}^{k} denotes the k–fold iterated application of the Newton–Hensel operator. Let M_{M} denote the extension ideal of M in C[T]_{M}. In order to show that our sequence (R^{(k,ξ)})_{k∈Z_{≥0}} is well defined, we will prove recursively the following assertions :

(I) F_{i}(T, R^{(k,ξ)}) ∈ M_{M}^{2^{k}} for any 1 ≤ i ≤ n and any k ∈ Z_{≥0}. (II) JF (T, R^{(k,ξ)}) := det(DF (T, R^{(k,ξ)})) ∉ M_{M}.

Proof of the assertions (I) and (II).– Assertions (I) and (II) will be proved by induction on k. The case k = 0 follows from the assumption that the fiber π^{−1}(t) is unramified and that ξ belongs to π^{−1}(t). Now, suppose that both assertions hold for k ≥ 0. Thus induction hypothesis (II) implies that R^{(k+1,ξ)} is well defined. Let Y := (Y_{1}, …, Y_{n}) be new indeterminates, and write (X − Y) for the ideal generated by X_{1} − Y_{1}, …, X_{n} − Y_{n} in C[T, X, Y]. Let R^{(k+1,ξ)} − R^{(k,ξ)} := (R_{1}^{(k+1,ξ)} − R_{1}^{(k,ξ)}, …, R_{n}^{(k+1,ξ)} − R_{n}^{(k,ξ)}). Considering the formal Taylor expansion of F and of its first partial derivatives in Y we obtain, for any 1 ≤ i ≤ n :

F_{i}(T, X) ≡ F_{i}(T, Y) + ∑_{j=1}^{n} \frac{∂F_{i}}{∂X_{j}} (T, X) · (X_{j} − Y_{j}) mod (X − Y)^{2}  (8)

Replacing X by R^{(k+1,ξ)} and Y by R^{(k,ξ)} we deduce from (8) the following congruence relations in C[T]_{M}:

F_{i}(T, R^{(k+1,ξ)}) ≡ F_{i}(T, R^{(k,ξ)})+  (9)

+ ∑_{j=1}^{n} \frac{∂F_{i}}{∂X_{j}} (T, R^{(k+1,ξ)}) · (R_{j}^{(k+1,ξ)} − R_{j}^{(k,ξ)}) mod (R^{(k+1,ξ)} − R^{(k,ξ)})^{2}

Recall that we have by definition R^{(k+1,ξ)} = N_{F} (R^{(k,ξ)}). This implies the identity :

( R_{1}^{(k+1,ξ)} − R_{1}^{(k,ξ)} ; ⋮ ; R_{n}^{(k+1,ξ)} − R_{n}^{(k,ξ)} ) = −DF (T, R^{(k,ξ)})^{−1} ( F_{1}(T, R^{(k,ξ)}) ; ⋮ ; F_{n}(T, R^{(k,ξ)}) )  (10)

Taking into account the induction hypothesis (I) we deduce from identity (10) that for any 1 ≤ i ≤ n

R_{i}^{(k+1,ξ)} − R_{i}^{(k,ξ)} ∈ M_{M}^{2^{k}}  (11)

holds.

Now, let DF_{i}(T, X) := (\frac{∂F_{i}}{∂X_{1}} , …, \frac{∂F_{i}}{∂X_{n}}) be the i–th row of the matrix DF (T, X). Multiplying the identity (10) by DF_{i}(T, R^{(k,ξ)}) we conclude :

DF_{i}(T, R^{(k,ξ)}) (R^{(k+1,ξ)} − R^{(k,ξ)})^{t} =
= DF_{i}(T, R^{(k,ξ)}) ( − DF (T, R^{(k,ξ)})^{−1}) ( F_{1}(T, R^{(k,ξ)}) ; ⋮ ; F_{n}(T, R^{(k,ξ)}) )

= −(0, …, 1, …, 0) ( F_{1}(T, R^{(k,ξ)}) ; ⋮ ; F_{n}(T, R^{(k,ξ)}) )

= −F_{i}(T, R^{(k,ξ)}),

where the value 1 occurs in the i–th entry of the n–tuple (0, …, 1, …, 0).

Finally, plugging this identities in the Taylor expansion (9), we obtain the congruence relations :

F_{i}(T, R^{(k+1,ξ)}) ≡ F_{i}(T, R^{(k,ξ)}) − F_{i}(T, R^{(k,ξ)}) ≡ 0 mod (R^{(k+1,ξ)} − R^{(k,ξ)})^{2}.

In conclusion we have for any 1 ≤ i ≤ n the ideal membership relation

F_{i}(T, R^{(k+1,ξ)}) ∈ (R^{(k+1,ξ)} − R^{(k,ξ)})^{2}

in the ring C[T]_{M}. From (11) we deduce now that F_{i}(T, R^{(k+1,ξ)}) ∈ M_{M}^{2^{k+1}} holds for any 1 ≤ i ≤ n. This proves assertion (I) for k + 1.

In order to prove assertion (II) for k + 1, we use again a formal Taylor expansion, but this time that of the polynomial JF (X) := det (DF (X)). In the same manner as in (8) we deduce the congruence relation

JF (T, X) ≡ JF (T, Y) + ∑_{j=1}^{n} \frac{∂JF}{∂X_{j}} (T, Y) · (X_{j} − Y_{j}) mod (X − Y)^{2}

Replacing in this expression X by R^{(k+1,ξ)} and Y by R^{(k,ξ)} we obtain

JF (T, R^{(k+1,ξ)}) ≡  (12)

≡ JF (T, R^{(k,ξ)}) + ∑_{j=1}^{n} \frac{∂JF}{∂X_{j}} (R^{(k,ξ)}) · (R_{j}^{(k+1,ξ)} − R_{j}^{(k,ξ)}) mod (R^{(k+1,ξ)} − R^{(k,ξ)})^{2}.

From (11) we deduce that, for any 1 ≤ i ≤ n, the ideal membership relation R_{i}^{(k+1,ξ)} − R_{i}^{(k,ξ)} ∈ M_{M}^{2^{k}} ⊂ M_{M} holds in C[T]_{M}. By induction hypothesis (II) we have JF (T, R^{(k,ξ)}) ∉ M_{M}. Therefore we infer from (12) that JF (T, R^{(k+1,ξ)}) does not belong to the ideal M_{M}. This shows assertion (II) for k + 1 and finishes the proof of both assertions.

Observing now that (11) is true for any k ∈ Z_{≥0}, we infer that, for 1 ≤ i ≤ n, the sequence of rational functions (R_{i}^{(ξ,k)})_{k∈Z_{≥0}} converges to a power series R_{i}^{(ξ)} of

C[[T − t]]. Let us write R^{(ξ)} := (R_{1}^{(ξ)}, …, R_{n}^{(ξ)}). From assertion (I) we deduce that for 1 ≤ i ≤ n and any k ∈ Z_{≥0}, the rational function F_{i}(T, R^{(k,ξ)}) belongs to the ideal M_{M}^{2^{k}} of C[T]_{M}. This means that the identity F_{i}(T, R^{(ξ)}) = 0 holds in C[[T − t]] for any 1 ≤ i ≤ n.

Taking into account that by definition R^{(0,ξ)} = ξ holds we deduce from (11) the identity R^{(ξ)}(t) = ξ.

This finishes the proof of the existence of the power series R_{1}^{(ξ)}, …, R_{n}^{(ξ)} contained in the statement of Lemma 3.

In order to prove their uniqueness, suppose there is given another n–tuple \overline{R}^{(ξ)} := (\overline{R_{1}}^{(ξ)}, …, \overline{R_{n}}^{(ξ)}) of power series of C[[T −t]], such that F_{i}(T, \overline{R}^{(ξ)}) = 0 and \overline{R}^{ξ}(t) = ξ holds for any 1 ≤ i ≤ n. Then, replacing X by R^{(ξ)} and Y by \overline{R}^{(ξ)} in (8), we deduce that in C[[T − t]] the congruence relation

F_{i}(T, R^{(ξ)}) ≡ F_{i}(T, \overline{R}^{(ξ)}) + ∑_{j=1}^{n} \frac{∂F_{i}}{∂X_{j}} (T, R^{(ξ)}) · (R_{j}^{(ξ)} − \overline{R}_{j}^{(ξ)}) mod (R^{(ξ)} − \overline{R}^{(ξ)})^{2}

holds for any 1 ≤ i ≤ n. This implies the congruence relation

DF (T, R^{(ξ)}) · (R^{(ξ)} − \overline{R}^{(ξ)})^{t} ≡ 0 mod (R^{(ξ)} − \overline{R}^{(ξ)})^{2}

in C[[T − t]]. By assumption, for any 1 ≤ i ≤ n both series R_{i}^{(ξ)} and \overline{R}_{i}^{(ξ)} have the same constant term, namely R_{i}^{(ξ)}(t) = \overline{R}_{i}^{(ξ)}(t) = ξ_{i}. Moreover, by assertion (II), for any k ∈ Z_{≥0}, the rational function JF (T, R^{(k,ξ)}) does not belong to the ideal M_{M} of C[T]_{M}. This imlies that DF (T, R^{(ξ)}) is a unimodular matrix with entries in C[[T − t]]. Therefore we conclude that, for any 1 ≤ i ≤ n, the difference of series R_{i}^{(ξ)} − \overline{R_{i}}^{(ξ)} must belong to the ideal (T − t)^{2} of C[[T − t]] (here (T − t) = (T_{1} − t_{1}, …, T_{m} − t_{m}) denotes the maximal ideal of the local ring C[[T − t]]). Repeating inductively this argument, we deduce that R_{i}^{(ξ)} − \overline{R_{i}}^{(ξ)} belongs to the ideal (T − t)^{2^{k}} for any k ∈ Z_{≥0} . This implies that R_{i}^{(ξ)} = \overline{R_{i}}^{(ξ)} holds.

Our main algorithmic tool will be the Newton–Hensel operator, but it is evident that we cannot use this operator infinitely often in a finite step procedure. In this sense, we have to fix a precision of approximation which limits the number of iterated applications of the operator. This leads to the following notion of approximation :

Definition 4 Let K be the field Q or C. Let t ∈ Q^{m} be a parameter point and let Φ, Φ̃ ∈ K[[T − t]] be formal power series. Let (T − t) := (T_{1} − t_{1}, …, T_{m} − t_{m}) be the maximal ideal of the local ring K[[T − t]].

For s ∈ N we say that Φ̃ approximates Φ with precision s in K[[T − t]] if

Φ ≡ Φ̃ mod (T − t)^{s} holds.

If Q, Q̃ ∈ K[[T − t]][Y] are polynomials in a single variable Y (of the same formal degree) with coefficients being formal power series, we will say that Q̃ approximates Q with precision s if each coefficient of Q̃ approximates the corresponding coefficient of Q with precision s.

Let us fix for the moment a nonnegative integer k and let us consider the k–fold iterated Newton–Hensel operator N_{F}^{k}(X) introduced in the proof of Lemma 3 (recall that we have N_{F}^{0}(X)^{t} = X^{t}, N_{F}^{1}(X)^{t} = X^{t} − DF^{−1} · F^{t}, etc). Observe that there exist polynomials g_{1}^{(k)}, …, g_{n}^{(k)} and h^{(k)} of Q[T, X] such that

N_{F}^{k}(X) = (\frac{g_{1}^{(k)}}{h^{(k)}} , …, \frac{g_{n}^{(k)}}{h^{(k)}} )  (13)

holds and such that the residue class of h^{(k)} is a unit of the reduced Q–algebra Q[T]_{M}[X]/(F_{1}, …, F_{n}).

In the sequel we shall need the following complexity result (see [GHH^{+}97, Lemma 30]):

Lemma 5 Let β be a division-free arithmetic circuit of size L and nonscalar depth λ computing F_{1}, …, F_{n} in Q[T, X], and let d be an upper bound for deg_{X} F_{i} (1 ≤ i ≤ n). Suppose that the Jacobian matrix DF (T, X) has a nonzero determinant. Then, there exists a division–free arithmetic circuit β_{∗} in Q[T, X] of size O(kd^{2}n^{7}L) and nonscalar depth O(k(log n+λ)) which evaluates suitable polynomials g_{1}^{(k)}, …, g_{n}^{(k)} and h^{(k)} of Q[T, X] such that the residue class of h^{(k)} is a unit of the reduced Q−algebra Q[T]_{M}[X]/(F_{1}, …, F_{n}) and such that

N_{F}^{k}(X) = (\frac{g_{1}^{(k)}}{h^{(k)}} , …, \frac{g_{n}^{(k)}}{h^{(k)}} )

holds. This arithmetic circuit can be produced by a uniform arithmetic network of asymptotically the same size and nonscalar depth as the output circuit β_{∗}.

The index k being fixed, we may write

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

Since the residue class of the polynomial h is a unit of Q[T]_{M}[X]/(F_{1}, …, F_{n}), the homothety η_{h(t,X)} is a regular Q–linear endomorphism of

Q[X]/(F_{1}(t, X), …, F_{n}(t, X)).

Therefore, from (5) we deduce that the matrix M_{h(t,X)} = h(t, v_{1}(M), …, v_{n}(M)) ∈ Q^{D×D} is regular and that h(T, v_{1}(M), …, v_{n}(M)) is a unimodular D × D matrix of Q[T]_{M}^{D×D}.

Finally we conclude that the matrices

N_{i} := \frac{g_{i}}{h} (T, v_{1}(M), …, v_{n}(M)) := h(T, v_{1}(M), …, v_{n}(M))^{−1} g_{i}(T, v_{1}(M) …, v_{n}(M))

are well defined in Q[T]_{M}^{D×D} for 1 ≤ i ≤ n.

We are now ready to state our first approximation result, which is a variant of [GHH^{+}97, Lemma 30]:

Lemma 6 Let notations and assumptions be as before. Let η_{G} be the homothety induced by G in the Q(T)−algebra Q(T)[X]/(F_{1}, …, F_{n}), and denote by X_{G} ∈ Q[T, Y] its characteristic polynomial.

Write M̃_{G} := G(T, N_{1}, …, N_{n}) ∈ Q[T]_{M}^{D×D} for the matrix obtained by substituting in G the variables X_{1}, …, X_{n} by the matrices N_{1}, … N_{n}, and denote by X̃_{G} ∈ Q[T]_{M}[Y] the characteristic polynomial of M̃_{G}

Then, interpreting X_{G} and X̃_{G} as elements of Q[[T − t]][Y], we see that X̃_{G} approximates X_{G} with precision 2^{k} in Q[[T − t]][Y].

Intuitively speaking, the previous lemma states that the coefficients of the “approximate” characteristic polynomial X̃_{G}, obtained by means of the k–fold iteration of the Newton–Hensel operator N_{F}, approximate the coefficients of the “exact” characteristic polynomial X_{G} with precision 2^{k} in Q[[T − t]].

Proof.– For 1 ≤ ℓ ≤ D, consider R^{(ξ^{(ℓ)})} := (R_{1}^{(ξ^{(ℓ)})}, …, R_{n}^{(ξ^{(ℓ)})}) ∈ C[[T − t]]^{n}, the n–tuple of formal power series defined in Lemma 3. Let \overline{Q(T)} be an algebraic closure of the function field Q(T) and consider the homothety η_{G} induced by the polynomial G in the Q(T)−algebra Q(T)[X]/(F_{1}, …, F_{n}) and in the \overline{Q(T)}−algebra \overline{Q(T)}[X]/(F_{1}, …, F_{n}). With respect to a suitable \overline{Q(T)} vector space basis of the latter algebra, the homothety η_{G} can be represented by a diagonal matrix of the form

( \begin{matrix}G(T, R^{(ξ^{(1)})}) & ⋯ & 0 \\ ⋮ & ... & ⋮ \\ 0 & ⋯ & G(T, R^{(ξ^{(D)})}) \end{matrix} ) .

Therefore, we have X_{G} = ∏_{ℓ=1}^{D}(Y − G(T, R^{(ξ^{(ℓ)})})).

Now, recall from (3) that there exists an invertible matrix C ∈ C^{D×D} such that

C M C^{−1} = M′ = ( \begin{matrix}u(ξ^{(1)}) \\ & . & . & . \\ & & & & u(ξ^{(D)}) \end{matrix} )

holds. Let 1 ≤ i ≤ n. One deduces easily the following matrix identities:

C N_{i} C^{−1} = C \frac{g_{i}}{h} (T, v_{1}(M), …, v_{n}(M)) C^{−1}
= \frac{g_{i}}{h} (T, C v_{1}(M) C^{−1}, …, C v_{n}(M) C^{−1})
= \frac{g_{i}}{h} (T, v_{1}(C M C^{−1}), …, v_{n}(C M C^{−1})) .

Therefore, by means of (2), (7) and (13) we deduce that

C N_{i} C^{−1} =

= ( \begin{matrix}\frac{g_{i}}{h} & (T, v_{1}(u(ξ^{(1)})), …, v_{n}(u(ξ^{(1)}))) \\ & & . & . & . \\ & & & & & \frac{g_{i}}{h} & (T, v_{1}(u(ξ^{(D)})), …, v_{n}(u(ξ^{(D)}))) \end{matrix} )

= ( \begin{matrix}\frac{g_{i}}{h} (T, ξ^{(1)}) \\ & . & . & . \\ & & & & \frac{g_{i}}{h} (T, ξ^{(D)}) \end{matrix} )

= ( \begin{matrix}R_{i}^{(k,ξ^{(1)})} \\ & . & . & . \\ & & & & R_{i}^{(k,ξ^{(D)})} \end{matrix} )

holds. In this way we obtain

C M̃_{G} C^{−1} = C G(T, N_{1}, …, N_{n})C^{−1} = G(T, C N_{1} C^{−1}, …, C N_{n} C^{−1}),

which means :

C M̃_{G} C^{−1} = ( \begin{matrix}G(T, R^{(k,ξ^{(1)})}) \\ & . & . & . \\ & & & & G(T, R^{(k,ξ^{(D)})}) \end{matrix} ) .

From the similarity of the matrices M̃_{G} and C M̃_{G} C^{−1}, we deduce that

X̃_{G}(Y) = ∏_{1≤ℓ≤D}(Y − G(T, R^{(k,ξ^{(ℓ)})}))

holds. Now, from Lemma 3 and statement (11) of its proof it follows immediately that X̃_{G} approximates X_{G} with precision 2^{k} in Q[[T − t]][Y].

The next result will give us a way to compute efficiently the minimal polynomial P (T, Y) of the homothety induced by G in the Q(T)–algebra Q(T)[X]/(F_{1}, …, F_{n}), from the knowledge of the approximating characteristic polynomial X̃_{G} and the minimal polynomial P (t, Y) of the homothety η_{G(t,X)} of Q[X]/(F_{1}(t, X), …, F_{n}(t, X)).

Lemma 7 Let Q(T, Y) and Q̃(T, Y) ∈ Q[T][Y] be polynomials, monic in the (single) variable Y satisfying the condition deg_{Y} Q = deg_{Y} Q̃.

Write R := \frac{Q}{gcd_{Y} (Q, \frac{∂Q}{∂Y})} ∈ Q[T][Y].

Let t ∈ Q^{m} and assume that the following holds :

• deg_{Y} gcd_{Y} (Q, \frac{∂Q}{∂Y}) = deg gcd(Q(t, Y), \frac{∂}{∂Y} Q(t, Y)).

• Q̃ approximates Q with positive precision s in Q[[T − t]][Y] (thus we have in particular Q̃(t, Y) = Q(t, Y)).

Suppose that the coefficients of Q̃ ∈ Q[T][Y] are given by a division–free arithmetic circuit β̃ in Q[T] of size L̃ and nonscalar depth λ̃. Then there exists a division–free arithmetic circuit γ̃ in Q[T] of size L̃+(deg_{Y} Q̃)^{O(1)} log s and nonscalar depth λ̃+O(log deg_{Y} Q̃+log s) which computes the coefficients in Q[T] of a polynomial R̃ ∈ Q[T][Y] satisfying :

• deg_{Y} R̃ = deg_{Y} R

• R̃ approximates R with precision s in Q[[T − t]][Y]

The circuit γ̃ can be produced from the input circuit β̃ and from the coefficient representation of Q(t, Y) = Q̃(t, Y) by a uniform arithmetic network of asymptotically the same size and nonscalar depth as γ̃.

Proof.– All the polynomials ocurring in this proof are considered as polynomials in the variable Y. The idea of the proof consists in the observation that the polynomial R(T, Y) can be represented by means of minors of a submatrix of the Sylvester matrix of Q and \frac{∂Q}{∂Y}. This submatrix can be made explicit analyzing the Sylvester matrix of Q(t, Y) = Q̃(t, Y) and Q′(t, Y) = Q̃′(t, Y). Then mimicking this representation of R(T, Y) by means of the corresponding minors of the Sylvester matrix of Q̃ and \frac{∂_{Q}}{∂Y} we obtain the required approximation polynomial R̃(T, Y).

Let us write Q′ := \frac{∂Q}{∂Y}, gcd(Q, Q′) := gcd_{Y} (Q, Q′), d := deg_{Y} Q(T, Y) and r := deg_{Y} R(T, Y). Since by assumption Q is monic in Y and deg_{Y} gcd(Q, Q′) = deg gcd(Q(t, Y), Q′(t, Y)) holds, we conclude gcd(Q(t, Y), Q′(t, Y)) = gcd(Q, Q′)(t, Y).

Therefore we have R(t, Y) = \frac{Q(t, Y)}{gcd(Q(t, Y), Q′(t, Y))}, and deg R(t, Y) = r.

Consider now the Q(T)– linear mapping φ from Q(T)^{r+1} ⊕ Q(T)^{r} to Q(T)^{d+r} given by the polynomial expression

A(T, Y)Q′(T, Y) + B(T, Y)Q(T, Y)

and the degree restrictions deg_{Y} A ≤ r and deg_{Y} B ≤ r − 1. This Q(T)–linear mapping has a one–dimensional kernel which can be described by the polynomial expressions

A(T, Y) = C(T)R(T, Y) and B(T, Y) = −C(T)\frac{Q′}{gcd(Q, Q′)}  (14)

with C(T) ranging over Q(T) − {0}. Analogously we may consider the Q–linear mapping φ_{t} from Q(t)^{r+1} ⊕ Q(t)^{r} to Q(t)^{d+r} given by the polynomial expression

a(Y)Q′(t, Y) + b(Y)Q(t, Y)

and the degree restrictions deg a ≤ r and deg b ≤ r − 1. Again this Q–linear mapping has a one–dimensional kernel which can be described by the polynomial expressions

a(Y) = cR(t, Y) and b(Y) = −c\frac{Q′(t, Y)}{gcd(Q(t, Y), Q′(t, Y))}  (15)

with c ranging over Q − {0}. Since the linear mappings φ and φ_{t} have one–dimensional kernel and their source space is 2r + 1–dimensional, they have 2r–dimensional image. With respect to the respective canonical vectorspace bases the matrices of φ and φ_{t} are suitable (d + r) × (2r + 1) submatrices of the Sylvester matrices of Q(T, Y), Q′(T, Y) and Q(t, Y), Q′(t, Y) respectively. Since φ and φ_{t} have 2r–dimensional images their matrices have both rank 2r. Selecting 2r linear independent rows from the matrix of φ_{t} we obtain a matrix M_{t} ∈ Q^{2r×(2r+1)} of rank 2r which determines a homogeneous linear equation system admitting up to scaling just one nontrivial solution in Q^{2r+1}. From (15) we deduce that this nontrivial solution represents the coefficients of the

univariate and monic polynomials R(t, Y) and \frac{Q′(t, Y)}{gcd(Q(t, Y), Q′(t, Y))} up to a com-

mon nonzero rational scaling factor. The matrix M_{t} is a submatrix of the matrix of φ_{t} and hence of the Sylvester matrix of Q(t, Y) and Q′(t, Y). Therefore M_{t} is determined by a certain choice of 2r rows and 2r + 1 columns of the Sylvester matrix of Q(t, Y) and Q′(t, Y). By the same choice of rows and columns we determine a certain 2r × (2r + 1) submatrix M(T) of the Sylvester matrix of Q(T, Y) and Q′(T, Y). Thus M(T) ∈ Q[T]^{2r×(2r+1)}. Since the 2r × (2r + 1) matrix M_{t} has rank 2r we may choose a nonzero 2r × 2r– minor of it. The corresponding minor of M(T) is nonzero too. Therefore we see that the rank of the matrix M(T) ∈ Q[T]^{2r×(2r+1)} is 2r as well. In a similar way as before we deduce from (14) that the homogeneous linear equation system given by

the matrix M determines the (in Y monic) polynomials R(T, Y) and \frac{Q′}{gcd(Q, Q′)} up

to a nonzero scaling factor of Q(T). Moreover we have M(t) = M_{t}. For 1 ≤ j ≤ r+1, let M_{j}(T) denote the minor of M(T) obtained by deleting the j−th column of M(T). Appending for each 1 ≤ i ≤ n to the matrix M(T) its i−th row as the first row, and developing the determinant of this new matrix by its first row, we immediately deduce that the vector (M_{1}(T), −M_{2}(T), …, M_{2r+1}(T)) is a nontrivial solution of the homogeneous linear equation system represented by the rank 2r matrix M(T). Similarly we see that the vector (M_{1}(t), −M_{2}(t), …, M_{2r+1}(t)) is also a nontrivial solution of the homogeneous linear equation system represented by the rank 2r matrix M_{t} = M(t). Since the polynomial R(t, Y) is monic we deduce easily from (15) that

M_{1}(t)Y^{r} − M_{2}(t)Y^{r−1} + … + (−1)^{r}M_{r+1}(t) = M_{1}(t)R(t, Y)

and that therefore M_{1}(t) ≠ 0 holds. This implies M_{1}(T) ≠ 0. In an analogous way we deduce from (14) the identity

M_{1}(T)Y^{r} − M_{2}(T)Y^{r−1} + … + (−1)^{r}M_{r+1}(T) = M_{1}(T)R(T, Y).

Taking into account M_{1}(T) ≠ 0 we conclude :

R(T, Y) := \frac{1}{M_{1}(T)} ∑_{0≤j≤r}(−1)^{r−j}M_{r+1−j}(T)Y^{j}.

Now we are going to construct our approximation polynomial R̃(T, Y): Let M̃(T) be the 2r × (2r + 1) submatrix of the Sylvester matrix of Q̃ and Q̃′ := \frac{∂_{Q}}{∂Y} determined by the same choice of rows and columns as the matrices M_{t} and M(T) (this makes sense because we have, by assumption, deg_{Y} Q̃ = deg_{Y} Q). Again, for 1 ≤ j ≤ r + 1, denote by M̃_{j}(T) the minor of M(T) obtained by deleting the j−th column. As by assumption Q̃(t, Y) = Q(t, Y) holds we deduce easily the identities M̃_{j}(t) = M_{j}(t) for 1 ≤ j ≤ r + 1. In particular we have M̃_{1}(t) ≠ 0 and M̃_{1}(T) ≠ 0. More precisely, M_{1}(t) ≠ 0 implies that M̃_{1}(T) is a unit of the local

Q–algebra Q[T]_{M}. In particular, for any 1 ≤ j ≤ r + 1 the rational function \frac{M̃_{j}(T)}{M̃_{1}(T)}

belongs to Q[T]_{M}. We would like to use the expression

\frac{1}{M̃_{1}(T)} ∑_{0≤j≤r}(−1)^{r−j}M̃_{r+1−j}(T)Y^{j}  (16)

for the definition of the approximation polynomial R̃(T, Y). However the expression (16) contains terms which are rational functions in T = (T_{1}, …, T_{m}). In order to avoid this difficulty we replace the rational functions

\frac{M̃_{r+1−j}(T)}{M̃_{1}(T)} ocurring in (16) by suitable approximation polynomials of Q[T]. For

this purpose we proceed as follows: Without loss of generality we may assume that M_{1}(t) = M̃_{1}(t) = 1 holds. Let us write H := 1 − M_{1} and H̃ := 1 − M̃_{1}. Hence, H(t) = H̃(t) = 0 and we obtain the following identities in the power series ring Q[[T − t]]:

\frac{1}{M_{1}} = ∑_{ℓ≥0} H^{ℓ} and \frac{1}{M̃_{1}} = ∑_{ℓ≥0} H̃^{ℓ}

Thus, in order to approximate R(T, Y) with precision s in Q[[T − t]], we define the polynomial R̃(T, Y) ∈ Q[T, Y] as

R̃(T, Y) := ∑_{0≤ℓ≤s} H̃^{ℓ}(T) ∑_{0≤j≤r}(−1)^{r−j}M̃_{r+1−j}(T)Y^{j}.

Let us verify that R̃ satisfies the requirements of the statement of Lemma 7 :

• Obviously we have R̃ ≠ 0 and from M̃_{1} ≠ 0 we deduce that deg_{Y} R̃ = r = deg_{Y} R holds.

• Since by assumption the polynomial Q̃ approximates Q in Q[[T − t]][Y] with precision s, we immediately see that for 1 ≤ j ≤ r + 1 the polynomial M̃_{j} approximates M_{j} with precision s and that the polynomial ∑_{0≤ℓ≤s} H̃^{ℓ} approxi-

mates the power series \frac{1}{M_{1}} = ∑_{ℓ≥0} H^{ℓ} with precision s. This implies that the

polynomial R̃(T, Y) approximates R(T, Y) with precision s in Q[[T − t]][Y].

Finally, we design a suitable arithmetic network which produces the polynomial R̃ from the input circuit β̃ representing Q̃ and the coefficient representation of Q(t, Y) = Q̃(t, Y). The first step in the construction consists in writing down the matrix of the linear mapping φ_{t} and to extract 2r independent rows from it. This allows to identify the matrices M_{t} = M̃(t) and M̃(T) as submatrices of the Sylvester matrices of Q(t, Y), Q′(t, Y) and Q̃(T, Y), \frac{∂_{Q}}{∂Y}(T, Y). This can be done by means of an arithmetic network of size r^{O(1)} and nonscalar depth O(log r) using the coefficients of Q(t, Y) = Q̃(t, Y) which represent part of the input. Then we compute the polynomials M̃_{j}(T). This can be done by a division–free arithmetic circuit in Q[T] (which extends the input circuit β̃) of size L̃ + (2r + 1)^{O(1)} and nonscalar depth λ̃ + O(log(2r)). Finally we compute H̃, ∑_{0≤ℓ≤s} H̃^{ℓ} and all the coefficients in Y of R̃ using O(r log s) additional

arithmetic operations, organized in a circuit of nonscalar depth O(log s). In this way we obtain a division-free arithmetic circuit γ̃ of required size and nonscalar depth.

Combining our previous results, we are now able to prove Theorem 2.

Proof of Theorem 2.- Let k := ⌊log_{2} deg_{T} P ⌋ + 1. Applying Lemma 5 to the input circuit β, we obtain a division–free arithmetic circuit γ_{1} in Q[T, X] of size O(kd^{2}n^{7}L) and non–scalar depth O(k(log_{2}n + λ)) which evaluates numerators g_{1} := g_{1}^{(k)}, …, g_{n} := g_{n}^{(k)} and a non–zero denominator h := h^{(k)} for the k–fold iteration of the Newton–Hensel operator N_{F}^{k} (such that N_{F}^{k}(X) =

(\frac{g_{1}}{h} , …, \frac{g_{n}}{h} ) holds).

Now, we apply γ_{1} to compute the matrices

g_{1}(T, v_{1}(M), …, v_{n}(M)), …, g_{n}(T, v_{1}(M), …, v_{n}(M))

and

h(T, v_{1}(M), …, v_{n}(M))

in Q[T]^{D×D} (compare with (4)). By means of the well–parallelizable polynomial algorithm of Berkowitz ([Ber84]) we compute the coefficients of the characteristic polynomial X_{h} ∈ Q[T][Y] of the matrix h(T, v_{1}(M), …, v_{n}(M)). Let

X_{h} = ∑_{ℓ=0}^{D} a_{ℓ}(T)Y^{ℓ}

with a_{0}, …, a_{D} ∈ Q[T] and let

h^{∗}(T, X) := ∑_{ℓ=1}^{D} a_{ℓ}(T)h^{ℓ−1}

Recall from the comments on Lemma 5 that the matrix h(T, v_{1}(M), …, v_{n}(M)) is unimodular in Q[T]_{M}^{D×D}. Thus a_{0} is a unit of Q[T]_{M} and in particular we have a_{0}(t) ≠ 0. Hence, the Cayley-Hamilton Theorem implies that

h(T, v_{1}(M), …, v_{n}(M))^{−1} = \frac{−1}{a_{0}}h^{∗}(T, v_{1}(M), …, v_{n}(M))  (17)

holds in Q[T]_{M}^{D×D}. We compute now the entries of the matrix h^{∗}(T, v_{1}(M), …, v_{n}(M)) by means of an arithmetic circuit γ_{2} which extends γ_{1} increasing the size and nonscalar depth of γ_{1} by D^{O(1)} and O(log D) respectively. We would like to compute the matrix h(T, v_{1}(M), …, v_{n}(M))^{−1} by means of formula (17). However we are unable to do that in Q[T] because this would require division by the polynomial a_{0}(T). Therefore we replace the matrix h(T, v_{1}(M), …, v_{n}(M))^{−1} by a suitable approximation in our subsequent argumentation. For this purpose let us use the following identity in Q[[T − t]]:

\frac{−1}{a_{0}(T)} = \frac{1}{a_{0}(t)} ∑_{ℓ=0}^{∞} (\frac{a_{0}(T) − a_{0}(t)}{a_{0}(t)})^{ℓ} .

Thus, the polynomial

a_{0}^{∗}(T) := \frac{1}{a_{0}(t)} ∑_{ℓ=0}^{2^{k}} (\frac{a_{0}(T) − a_{0}(t)}{a_{0}(t)})^{ℓ}

approximates the rational function \frac{−1}{a_{0}(T)} in Q[[T − t]] with precision 2^{k}. We are now going to compute an approximation of the matrix

M̃_{G} := G(T, \frac{g_{1}}{h} (T, v_{1}(M), …, v_{n}(M)), …, \frac{g_{n}}{h} (T, v_{1}(M), …, v_{n}(M))

(recall that, by Lemma 6, the characteristic polynomial X̃_{G} of M̃_{G} approximates the characteristic polynomal X_{G} of the homothety induced by G in Q(T)[X]/(F_{1}, …, F_{n}) with precision 2^{k}). Let us consider the matrix

M̂_{G} := G (T, (a_{0}^{∗}h^{∗}g_{1})(T, v_{1}(M), …, v_{n}(M)), …, (a_{0}^{∗}h^{∗}g_{n})(T, v_{1}(M), …, v_{n}(M)))

(18)

The polynomial entries of the matrix M̂_{G} clearly approximate the corresponding entries of the matrix M̃_{G} with precision 2^{k} in Q[[T − t]]. In order to compute a_{0}^{∗}(T) from a_{0}(T), we use the division–free arithmetic circuit underlying the formula :

∑_{ℓ=0}^{2^{k}} (\frac{a_{0}(T) − a_{0}(t)}{a_{0}(t)})^{ℓ} =

= (1 + \frac{a_{0}(T) − a_{0}(t)}{a_{0}(t)}) (1 + (\frac{a_{0}(T) − a_{0}(t)}{a_{0}(t)})^{2}) ⋯ (1 + (\frac{a_{0}(T) − a_{0}(t)}{a_{0}(t)})^{2^{k−1}} ) +

+ (\frac{a_{0}(T) − a_{0}(t)}{a_{0}(t)})^{2^{k}} .

Plugging this circuit in the arithmetic circuit underlying formula (18) we obtain a division-free circuit γ_{3} which extends γ_{2}. The arithmetic circuit γ_{3} computes the entries of M̂_{G} and has the same asymptotic complexity as γ_{2}, namely size O(kd^{2}n^{7}L) + D^{O(1)} and nonscalar depth O(k(log n + λ) + log D).

Observe that the characteristic polynomial X̂_{G} of the matrix M̂_{G} approximates the characteristic polynomial X̃_{G} of M̃_{G}(T, Y) with precision 2^{k} in Q[[T − t]]. Hence, X̂_{G} also approximates the characteristic polynomial X_{G} of the homothety induced by G in Q(T)[X]/(F_{1}, …, F_{n}) with the same precision.

Applying the algorithm of Berkowitz ([Ber84]), we extend γ_{3} to a circuit γ_{4} which computes the coefficients of the characteristic polynomial X̂_{G}. The size and nonscalar depth of γ_{4} are asymptotically of the same order than those of γ_{3}.

Now, observing that the polynomials X̂_{G} and X_{G} satisfy the assumptions of Lemma 7, we obtain from the coefficients of X̂_{G} ∈ Q[T][Y] the coefficients of a polynomial P̃ ∈ Q[T][Y] in Y which approximates with precision 2^{k} in Q[[T − t]] the required minimal polynomial P of the homothety induced by G. The division–free arithmetic circuit γ_{5} in Q[T] we use by means of Lemma 7 for this purpose, increases the size and depth of γ_{4} by kD^{O(1)} and O(log D + k) respectively. Thus, γ_{5} has size O(kd^{2}n^{7}L) + kD^{O(1)} and nonscalar depth O(k(log n + λ) + log D).

Finally, we compute the exact coefficients of P by the following variant of the Vermeidung von Divisionen technique. In the following way we introduce a new variable Z in the arithmetic circuit γ_{5} which evaluates the coefficients of the polynomial P̃ ∈ Q[T][Y] with respect to the variable Y : we replace the variables T_{1}, …, T_{m} in γ_{5} by the monomials ZT_{1}, …, ZT_{m}. In this manner, we compute the coefficients of the polynomial

P̃(ZT_{1}, …, ZT_{m}, Y) ∈ Q[T, Z][Y]

with respect to the variable Y by means of a new division–free circuit γ_{6} in Q[T, Z]. The size and nonscalar depth of the circuit γ_{6} are asymptotically the same as those of the circuit γ_{5}. Now we modify the circuit γ_{6} as follows: in each computation step we write the corresponding intermediate result as a polynomial in the variable Z (performing interpolation in Z) and eliminate all monomial terms of degree strictly greater than deg_{T} P. Hence, simulating the execution of the arithmetic circuit γ_{6} performing step by step the above modification, the elements of Q[T] we obtain as coefficients of monomials in Z are all the coefficients of P̃ up to degree deg_{T} P. In this way, we obtain a division–free arithmetic circuit γ_{7} in Q[T, Z] which computes approximations to the input polynomials of γ_{6} with precision deg_{T} P with respect to the variable Z. The final circuit γ is obtained from γ_{7} by specializing the variable Z into the value 1. Thus, γ computes the coefficients of the minimal polynomial P exactly. Finally let us notice that γ has asymptotically the same size and nonscalar depth than the circuit γ_{7}, and γ_{7} has the same nonscalar depth than γ_{6} whereas its size becomes increased by a factor deg_{T}^{2} P with respect to the size of the circuit γ_{6}. Thus, the circuit γ has size O(d^{2}n^{7} deg_{T}^{2} P log(deg_{T} P)L) + D^{O(1)} deg_{T}^{2} P log(deg_{T} P) and nonscalar depth O((log n + λ) log(deg_{T} P) + log D).

3 Refinement of the main result and examples

3.1 Refinement of the main result

The complexity bound stated in our main result, namely Theorem 2, depends substantially on linear algebra computations with D × D matrices. The original D × D matrix we deal with is M, the companion matrix of the polynomial q appearing in the given description of a geometric solution of the fiber π^{−1}(t). Suppose now that the Galois group of C over Q does not act transitively on the fiber π^{−1}(t) and that a certain factorization of the polynomial q over Q[Y] is given, capturing this situation. Let us suppose that q has the form

q = ∏_{j=1}^{s} q_{j}

where q_{1}, …, q_{s} are nonconstant polynomials of Q[Y] with D_{j} := deg q_{j} and

∑_{j=1}^{s} D_{j} = D. Observe that the polynomials q_{1}, …, q_{s} are pairwise coprime since the

polynomial q is separable by assumption. Instead of working with the companion matrix M directly, we may take into account its special block form corresponding to the given factorization of the polynomial q. Thus, let us consider the matrix

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

where, for each 1 ≤ j ≤ s, we denote by M_{j} the companion matrix of the polynomial q_{j}. From the fact that the polynomials q_{1}, …, q_{s} are pairwise coprime and the Chinese remainder theorem, we deduce easily that M^{∗} is similar to the matrix M. Thus q is the characteristic and —by its separability— also the minimal polynomial of M^{∗}.

As it is unlike that linear algebra routines dealing with special matrices like those occurring in polynomial elimination theory will become one day linear time procedures, we may profit from the block structure of the matrix M^{∗}.

For example, if during our main algorithm (see proof of Theorem 2), we need to apply a quadratic time linear algebra routine to the D × D matrix M, replacing the matrix M by the similar matrix M^{∗} the complexity becomes O(D_{1}^{2} + ⋯ + D_{s}^{2}) instead of O(D^{2}) = O((D_{1} + ⋯ + D_{s})^{2}). Doing so, the time economy is of order O( ∑_{1≤j<k≤s} D_{j}D_{k}), which may be of decisive importance when implementing (and

running) our main algorithm on a real world computer. This leads to the following reformulation of our main result in the case that a factorization of the polynomial q in nonconstant polynomials q_{1}, …, q_{s} ∈ Q[Y] is given.

Corollary 8 Let notations and assumptions be as in Theorem 2. Assume, furthermore, that there are given s polynomials q_{1}, …, q_{s} ∈ Q[Y] of positive degrees D_{1}, …, D_{s} respectively such that q = q_{1} · . . . · q_{s} holds. Let ω be the maximal exponent of the matrix operations we are going to use during our algorithm. Then, there exists a division–free arithmetic circuit γ in Q[T] with the following properties

i) γ computes the coefficients of the polynomial P with respect to the main variable Y

ii) γ has size O(d^{2}n^{7} deg_{T}^{2} P log(deg_{T} P)L + (D_{1}^{ω} + ⋯ + D_{s}^{ω}) deg_{T}^{2} P log(deg_{T} P))

iii) γ has nonscalar depth O((log n + λ) log(deg_{T} P) + log(max{D_{i}; 1 ≤ i ≤ s}))

Moreover, there exists a uniform family of arithmetic networks of asymptotically the same size and nonscalar depth than γ which produces γ from the following data:

– the input arithmetic circuit β

– the rational numbers which represent the coordinates of t and the given description of a geometric solution of the fiber π^{−1}(t) (containing the polynomial q)

– the coefficients of the polynomials q_{1}, …, q_{s}.

3.2 Examples

Example 1

The aim of this example is to analyze what occurs with the following parametric situation when our main result is applied. Let T := (T_{1}, …, T_{m}) be indeterminates and let A_{n−1}, …, A_{0} be polynomials ofQ[T] of degree not exceeding an a priori fixed bound Δ. Suppose that the polynomials A_{n−1}, …, A_{0} are given by a division–free arithmetic circuit β in Q[T]. Let L be the size of β. We consider the following polynomials of Q[T][X]

F_{n−1} := σ_{n−1} − A_{n−1}, …, F_{0} := σ_{0} − (−1)^{n}A_{0}

(where σ_{i} denotes the i−th elementary symmetric function in the variables X := (X_{1}, …, X_{n})). Obviously, the zeroes of the polynomial equation system

F_{0} = 0, …, F_{n−1} = 0  (19)

are closely related to the zeroes of the polynomial equation Q = 0 with

Q(Y) = Y^{n} + A_{n−1}Y^{n−1} + ⋯ + A_{0} ∈ Q[T][Y].

First, let us analyze the non-parametric case of the equation system (19) : For given a_{0}, …, a_{n−1} ∈ Q, let us consider the following polynomials of Q[X] :

f_{n−1} := σ_{n−1} − a_{n−1}, …, f_{0} := σ_{0} − (−1)^{n}a_{0}

Assume that the corresponding polynomial Q^{∗} := Y^{n} + a_{n−1}Y^{n−1} + ⋯ + a_{0} ∈ Q[Y] is separable. The polynomials f_{n−1}, …, f_{0} define a zero–dimensional equation system without parameters (corresponding to the polynomial equation system (19) with m = 0) which admits n! solutions. Observe that this system has no solution at infinity and that its Bézout–number is also n!. Observe that the polynomials Q^{∗}(X_{1}), …, Q^{∗}(X_{n}) represent a succinct uncoupling of the variables X_{1}, …, X_{n} occurring in the polynomial system f_{n−1} = 0, …, f_{0} = 0. The polynomials Q^{∗}(X_{1}), …, Q^{∗}(X_{n}) can be represented by an array of n^{2} elements of Q or by a division–free arithmetic circuit of length O(n log n) in Q[X]. However, for the input polynomials f_{0}, …, f_{n−1}, the main algorithm of [GHH^{+}97] and [GHMP97] (like many other symbolic procedures designed for the special purpose of algorithmic Galois theory as e.g. [Val95] and [Col97]) chooses a sufficiently generic Q-linear combination U of the variables X_{1}, …, X_{n} and produces the resolvent, say R_{U}, of the equation Q = 0 with respect to the variable U. The resolvent R_{U} belongs to the polynomial ring Q[U] and its degree equals the order of the Galois group of the splitting field of Q. The main algorithm of [GHH^{+}97] and [GHM^{+}98] requires (n!)^{O(1)} = n^{O(n)} arithmetic operations in Q in order to produce the polynomial R_{U}.

Let us now come back to the situation of the original parametric equation system F_{0} = 0, …, F_{n−1} = 0 :

Let us suppose that the polynomial Q is separable with respect to the variable Y. Note that the polynomials F_{n−1}, …, F_{0} form a regular sequence in Q[T, X] and, therefore, they define an equidimensional variety of dimension m, namely

V := {F_{n−1} = 0, …, F_{0} = 0} ⊂ A^{m+n}.

The morphism of affine varieties π : V → A^{m} induced by the canonical projection of A^{m+n} onto A^{m} is finite, generically unramified and has degree n!. Suppose that there is given a point t ∈ Q^{m} for which the specialized polynomial Q(t, Y) := Y^{n} + A_{n−1}(t)Y^{n−1} + ⋯ + A_{0}(t) is separable (i.e., where the fiber π^{−1}(t) is unramified). Assume furthermore that we have “sufficient information” about the geometric nature of the fiber π^{−1}(t). In particular, we suppose that the polynomial Q(t, Y) (and the Galois group of Q(t, Y)) is known. Then, applying the arithmetic network of Theorem 2 to the general problem instance F_{0}, …, F_{n−1}, G with G := X_{1}, we are able to find the polynomial Q in sequential time O(n^{9}LΔ^{2} log Δ + (n!)^{ω}Δ^{2} log Δ) where ω denotes the maximal exponent of matrix operations used in the algorithm. In case Q(t, Y) has a known decomposition into linear factors of Q[Y], Corollary 8 implies this complexity bound can be lowered to O(n^{9}LΔ^{2} log Δ + n!Δ^{2} log Δ). But in fact, in this particular case, it is possible to design a variant of our algorithm with better complexity bounds :

Remark 9 Let notations be as before and assume that the univariate polynomial Q(t, Y) has a known decomposition into linear factors of Q[Y]. Then there exists a division-free arithmetic circuit γ in Q[T] of size O(n^{9}LΔ^{2} log Δ) and nonscalar depth O(log Δ(log n + λ)) which recovers the polynomial Q ∈ Q[T, Y].

Proof.– Let y_{1}, …, y_{n} ∈ Q be the n distinct roots of Q(t, Y). As we want to compute the minimal polynomial of G := X_{1} modulo the ideal (F_{0}, …, F_{n−1}) and since π^{−1}(t) = {t} × V_{t} with

V_{t} = {τ(y_{1}, …, y_{n}) : τ is a permutation of n elements}

holds, it suffices to consider the n distinct rational points

ξ^{(1)} := (y_{1}, y_{2} …, y_{n})
ξ^{(2)} := (y_{2}, …, y_{n}, y_{1})
⋮
ξ^{(n)} := (y_{n}, y_{1}, …, y_{n−1})

all belonging to V_{t} and having distinct first coordinates. Applying Lemma 3 to the rational points ξ^{(1)}, …, ξ^{(n)} ∈ V_{t} we obtain for each 1 ≤ ℓ ≤ n an n–tuple of power series R^{ξ^{(ℓ)}} := (R_{1}^{(ξ^{(ℓ)})}, …, R_{n}^{(ξ^{(ℓ)})}) ∈ Q[[T − t]]^{n} such that R^{ξ^{(ℓ)}}(t) = ξ^{ℓ} and F_{0}(T, R^{ξ^{(ℓ)}}) = 0, …, F_{n−1}(T, R^{ξ^{(ℓ)}}) = 0 holds. Since R_{1}^{(ξ^{(ℓ)})}(t) = y_{ℓ} ≠ y_{ℓ′} = R_{1}^{ξ^{(ℓ′)}} holds for any 1 ≤ ℓ ≠ ℓ′ ≤ n, we conclude that the series R_{1}^{ξ^{(1)}}, …, R_{1}^{ξ^{(n)}} ∈ Q[[T − t]] are all distinct. Hence the minimal polynomial of the homothety η_{X_{1}} of multiplication by X_{1} in Q(T)[X]/(F_{0}, …, F_{n−1}) can be

written as P_{X_{1}} := ∏_{ℓ=1}^{n}(Y − R_{1}^{(ξ^{(ℓ)})}).

Now, we repeat, one by one, exactly the same steps than in the proof of Theorem 2 in order to compute the minimal polynomial P_{X_{1}} which is the characteristic polynomial of the n × n matrix

( \begin{matrix}R_{1}^{(ξ^{(1)})} \\ & . & . & . \\ & & & & R_{1}^{(ξ^{(n)})} \end{matrix} )

The reduction of the complexity of the algorithm underlying the statement of Remark 9 is simply due to the fact that instead of dealing with n! × n! matrices as in the proof of Theorem 2, we may restrict ourselves to the consideration of matrices having size only n × n.

Example 2 Let T := (T_{1}, …, T_{n}) and X := (X_{1}, …, X_{n}). Let be given polynomials f_{1}, …, f_{n} ∈ Q[X] of degree at most d which define a morphism φ := (f_{1}, …, f_{n}) of the affine space A^{n} onto itself which is supposed to be an automorphism of A^{n}. Suppose that f_{1}, …, f_{n} are represented by a division–free arithmetic circuit in Q[X] of length L. Let Q_{1}, …, Q_{n} be the polynomials of Q[X] which define the inverse map of φ, i.e. let φ^{−1} = (Q_{1}, …, Q_{n}). Furthermore, let Δ := max{deg Q_{1}, …, deg Q_{n}}. We consider the polynomials F_{1} := T_{1} − f_{1}, …, F_{n} := T_{n} − f_{n} ∈ Q[T, X]. The polynomials F_{1}, …, F_{n} generate a complete intersection ideal in Q[T, X] which is prime and hence radical. Hence, the variety V defined by the equations F_{1} = 0, …, F_{n} = 0 is equidimensional, of dimension n, and the morphism π : V → A^{n} induced by the canonical first projection of A^{2n} onto A^{n}, is an isomorphism of varieties. Therefore the morphism π is finite and unramified. Note that Bézout’s Theorem implies that deg V ≤ d^{n} holds. Moreover, we have deg π = 1. From Gabber’s Theorem ([BCW82]) we deduce Δ ≤ d^{n}.

Let P_{1}, …, P_{n} be the elimination polynomials of the linear forms X_{1}, …, X_{n} with respect to the variety V. These polynomials belong to Q[T][Y] and have the form P_{1} = Y − Q_{1}, …, P_{n} = Y − Q_{n}. Thus, the computation of P_{1}, …, P_{n} yields the inverse map φ^{−1}. Using the algorithm underlying Theorem 2 in order to compute the polynomials P_{1}, …, P_{n}, we obtain a division–free arithmetic circuit γ in Q[T] of size O(d^{2}n^{8}Δ^{2} log ΔL) = O(n^{8}d^{2n+2}L), which represents the polynomials Q_{1}, …, Q_{n} and, hence, the inverse map φ^{−1}.

References

[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. Connelle, and T. Wright. The jacobian conjecture: reduction of degree and formal expansion of the inverse. Bull. AMS, 7(2):287–330, 1982.

[Ber84] S. J. Berkowitz. On computing the determinant in small parallel time using a small number of processors. Information Processing Letters, 18:147–150, 1984.

[BGHM] 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. Best Paper Award J. of Complexity 1997.

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

[BPR97] Saugata Basu, Richard Pollack, and Marie-Françoise Roy. On computing a set of points meeting every cell defined by a family of polynomials on a variety. J. of Complexity, 13(1):28–37, 1997.

[Bru98] N. Bruno. Esquemas de compilación de circuitos aritméticos uniformes descriptos por medio de funciones generatrices. Master’s thesis, FaMAF, Universidad de Córdoba, Argentina, 1998.

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

[Can90] John Canny. Generalised characteristic polynomials. Journal of Symbolic Computation, 9(3):241–250, 1990.

[Cas97] D. Castro. Sobre la complejidad de la aproximación diofántica y los fundamentos del análisis numérico. Master’s thesis, Universidad de Cantabria, Santander, Spain, 1997.

[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.

[Col97] A. Colin. Théorie des invariants effective. PhD thesis, Ecole Polytechnique, Palaiseau-Paris, France, 1997.

[Ful84] W. Fulton. Intersection Theory. Number 3 in Ergebnisse der Mathematik. Springer, 2 edition, 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, Symposia Matematica, vol. XXXIV, Cambridge University Press, 216-256, 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, J. Pure Appl. Algebra, 117 & 118, 277-317, 1997.

[GHL^{+}97] Marc Giusti, Klemens Hägele, Grégoire Lecerf, Joël Marchand, and Bruno Salvy. Computing the dimension of a projective variety: the projective noether Maple package. Research report 3224, INRIA, France, July 1997.

[GHM^{+}98] M. Giusti, J. Heintz, J. E. Morais, J. Morgenstern, and L. M. Pardo. Straight–line programs in geometric elimination theory. J. Pure and Appl. Algebra, 124:101–146, 1998.

[GHMP97] M. Giusti, J. Heintz, J. E. Morais, and L. M. Pardo. Le rôle des structures de données dans les problèmes d’élimination. C. R. Acad. Sci. Paris, 325:1223–1228, 1997.

[GM89] P. Gianni and T. Mora. Algebraic solution of systems of polynomial equations using Gröbner bases. In Proceedings AAECC-5, Springer LNCS, 356, 247-257, 1989.

[GV88] D. Yu. Grigoriev and N. N. Vorobjov, Jr. Solving systems of polynomial inequalities in sub-exponential time. Journal of Symbolic Computation, 5(1-2):37–64, 1988.

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

[HMPS98] K. Hägele, J. E. Morais, L. M. Pardo, and M. Sombra. On the intrinsic complexity of the arithmetic Nullstellensatz. To appear in J. Pure Appl. Algebra, Manuscript, 1998.

[HRS90] J. Heintz, M.-F. Roy, and P. Solernó. Sur la complexité du principe de Tarski-Seidenberg. Bull. Soc. Math. de France, 118:101–126, 1990.

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

[Kal85] E. Kaltofen. Computing with polynomials given by straight-line programs I: Greatest common divisors. In Proceedings of the 17th Ann. ACM Symposium on Theory of Computing (Providence, RI), ACM Press, New York, 131-142, 1985.

[Koe03] J. Koenig. Einleitung in die allgemeine Theorie der algebraischen Grössen. B. G. Teubner, Leipzig, 1903.

[Kov90] P. Kovacs. Minimum degree solutions for the inverse kinematics problem by application of the Buchberger algorithm. In Proceedings of the 2nd Int. Workshop on Advances in Robot Kinematics. University of Linz, Austria, Sept 10–12, 1990, Springer, to appear, 1990.

[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, Progress in Mathematics, vol. 143, Birkhäuser Verlag, 193-254, 1996.

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

[LV98] M. J. Gonzalez Lopez and L. Gonzalez Vega. Newton identities in the multivariate case: Pham systems. London Mathematical Society Lecture Notes Series, 251:351–366, 1998.

[Mac96] F. S. Macaulay. Algebraic Theory of Module Systems. Cambridge University Press, 1996.

[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.

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

[MP97] B. Mourrain and V. Pan. Solving special polynomial systems by using structural matrices and algebraic residues. In F. Cucker and M. Shub, editors, Proceedings Foundations of Computational Mathematics (FOCM’97),Springer Verlag, 287-304, 1997.

[Nar66] R. Narasimhan. Introduction to the theory of analytic spaces. Springer LNM 25, 1966.

[Ren92] James Renegar. On the computational complexity and geometry of the first-order theory of the reals. part I: Introduction. preliminaries. the geometry of semi-algebraic sets. the decision problem for the existential theory of the reals. Journal of Symbolic Computation, 13(3):255–299, 1992.

[Sch95] J. Schmid. On the affine Bézout inequality. Manuscripta Math., 88:225– 232, 1995.

[SGV94] A. Schönhage, F. W. Grotefeld, and E. Vetter. Fast Algorithms: A Multitape Turing Machine Implementation. B.I. Wissenschaftsverlag, Mannheim, 1994.

[Som97] M. Sombra. Bounds for the Hilbert function of polynomial ideals and for the degrees in the Nullstellensatz. In Proceedings of MEGA’96, J. Pure Appl. Algebra, 117 & 118, 565-599, 1997.

[SS93a] M. Shub and S. Smale. Complexity of Bézout’s theorem I: Geometric aspects. J. of the AMS, 6(2):459–501, 1993.

[SS93b] M. Shub and S. Smale. Complexity of Bézout’s theorem II: Volumes and probabilities. In Proceedings of MEGA’92, Progress in Mathematics, vol. 109, Birkhäuser Verlag, 267–285, 1993.

[SS93c] M. Shub and S. Smale. Complexity of Bézout’s theorem III: Condition number and packing. J. of Complexity, 9:4–14, 1993.

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

[SS96a] 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.

[SS96b] Michael Shub and Steve Smale. Complexity of Bezout’s theorem. IV. probability of success and extensions. SIAM Journal on Numerical Analysis, 33(1):128–148, 1996.

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

[TER97] TERA Development Group. Some remarks on the time–space tradeoff of geometric elimination procedures. Manuscript, 1997.

[Val95] A. Vallibouze. Computations of the Galois groups of the resolvent factors for the direct and indirect Galois problem. In M. Giusti, G. Cohen and T. Mora, editors, Proceedings of AAECC-11, Springer LNCS 948, 456–468, 1995.

[VH94] J. Verschelde and A. Haegemans. Homotopies for solving polynomial systems within a bounded domain. Theoretical Computer Science, 133(1):165–185, 1994.

[Vog84] W. Vogel. Results on Bezout’s Theorem. Tata Institute of Fundamental Research. Springer Verlag, 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, Springer LNCS 233, 93–112, 1986.

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

[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 Verlag, 1993.

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

Research was partially supported by the following Argentinian and Spanish grants: UBACYT EX-001, PIP CONICET 4571, DGICYT PB96-0671-C02-02, ANPCyT 03-00000-01593.

Joos Heintz (corresponding author) Departamento de Matemática, Facultad de Ciencias Exactas y Naturales, Universidad de Buenos Aires, Ciudad Universitaria, Pab. I, (1428) Buenos Aires, Argentina and Departamento de Matemática, Estadística y Computación, Facultad de Ciencias, Universidad de Cantabria, Avda. de los Castros s/n, E-390071 Santander, Spain e-mails: joos@mate.dm.uba.ar and heintz@matesco.unican.es

Teresa Krick, Susana Puddu, Juan Sabia and Ariel Waissbein Departamento de Matemática, Facultad de Ciencias Exactas y Naturales, Universidad de Buenos Aires, Ciudad Universitaria, Pab. I, (1428) Buenos Aires, Argentina