STRAIGHT–LINE PROGRAMS IN GEOMETRIC ELIMINATION THEORY

M. Giusti ^{1,3} J. Heintz ^{2,3} J.E. Morais^{2,3} J. Morgenstern L.M. Pardo ^{2,3}

Dedicated to Volker Strassen for his work on complexity

Abstract

We present a new method for solving symbolically zero–dimensional polynomial equation systems in the affine and toric case. The main feature of our method is the use of problem adapted data structures : arithmetic networks and straight–line programs. For sequential time complexity measured by network size we obtain the following result : it is possible to solve any affine or toric zero–dimensional equation system in non–uniform sequential time which is polynomial in the length of the input description and the “geometric degree” of the equation system. Here, the input is thought to be given by a straight–line program (or alternatively in sparse representation), and the length of the input is measured by number of variables, degree of equations and size of the program (or sparsity of the equations). The geometric degree of the input system has to be adequately defined. It is always bounded by the algebraic–combinatoric “Bézout number” of the system which is given by the Hilbert function of a suitable homogeneous ideal. However, in many important cases, the value of the geometric degree of the system is much smaller than its Bézout number since this geometric degree does not take into account multiplicities or degrees of extraneous components (which may appear at infinity in the affine case or may be contained in some coordinate hyperplane in the toric case).

Our method contains a new application of a classic tool to symbolic computation : we use Newton iteration in order to simplify straight–line programs occurring in elimination procedures. Our new technique allows for practical implementations a meaningful characterization of the intrinsic algebraic complexity of typic elimination problems and reduces the still unanswered question of their intrinsic bit complexity to algorithmic arithmetics. However our algorithms are not rational anymore as are the usual ones in elimination theory. They require some restricted computing with algebraic numbers. This is due to its numeric ingredients (Newton iteration). Nevertheless, at least in the case of polynomial equation systems depending on parameters, the practical advantage of our method with respect to more traditional ones in symbolic and numeric computation is clearly visible. Our approach produces immediately a series of division theorems (effective Nullstellensätze) with new and more differentiated degree and complexity bounds (we shall state two of them).

1: GAGE, Centre de Mathématiques. École Polytechnique. F-91228, Palaiseau Cedex.

FRANCE

2: Dept. de Matemáticas, Estadística y Computación. F. de Ciencias. U. Cantabria.

E-39071 SANTANDER, Spain

3: Research was partially supported by the following European, French and Spanish grants :

PoSSo ESPRIT/BRA 6846, GDR CNRS 1026 MEDICIS, DGCYT PB92–0498–C02–01 and PB93–0472–C02–02

It should be well understood that our method does not improve the well known worst–case complexity bounds for zero–dimensional equation solving in symbolic and numeric computing.

Part of the results of this paper were announced in [25].

Keywords. Polynomial system solving, elimination, division theorem, Nullstellensatz, geometric degree, arithmetic network, straight–line program, complexity.

Subject classifications. 68Q25, 14Q15.

1 Introduction and Statement of Results

Let k be an infinite, perfect field which we think “effective” with respect to arithmetic operations as addition/subtraction, multiplication/division and extraction of p –th roots in case that k has positive characteristic p. Let k̄ be a fixed algebraic closure of k.

An important problem in elimination theory is the computation of the isolated points of an affine algebraic variety. This means we consider the algebraic variety

V := V (f_{1}, …, f_{s}):= {x ∈ A^{n}(k̄) : f_{1}(x) = 0, …, f_{s}(x) = 0},

where f_{1}, …, f_{s} ∈ k[X_{1}, …, X_{n}] with s ≥ n are polynomials of degree at most d in the variables X_{1}, …, X_{n} and we look at the following problem : given a nonzero linear form H ∈ k[X_{1}, …, X_{n}] and a new variable T , compute a nonzero polynomial p ∈ k[T] such that p(H) vanishes on all isolated points of V . This “weak” form of symbolic solving of the equation system given by the polynomials f_{1}, …, f_{s} is in all thinkable aspects (effectivity, practical efficiency and theoretical complexity) equivalent to the following more explicit form : find univariate polynomials q, v_{1}, …, v_{n} ∈ k[T] such that the set of isolated points of V can be written as {(v_{1}(t), …, v_{n}(t)) ; t ∈ A^{1}(k̄) , q(t) = 0} (see [24], [40] and Lemma 14 below).

As many authors do (see for instance, [3], [4], [7], [8], [9], [10], [12], [17], [19], [24], [26], [39], [40], [41], [43], [51], [52]), we replace the original input system by n generic k –linear combinations of the equations f_{1}, …, f_{s}. This preparation of the input conserves all irreducible components (and, in particular, the isolated points) of V and adds possibly some new, extraneous ones (these components have to be eliminated afterwards). Thus, let us suppose from now on that s = n holds. This implies that the input system f_{1}, …, f_{n} forms locally a complete intersection with respect to the isolated points of V . In view of the surprisingly low (linear) regularity bound for homogeneous global complete intersection ideals (see [6], [44], [46]) one is tempted to replace the original equations f_{1}, …, f_{n} ∈ k[X_{1}, …, X_{n}] by new homogeneous ones, G_{1}, …, G_{n} ∈ k[X_{0}, …, X_{n}] , and the affine variety V = V (f_{1}, …, f_{n}) by the corresponding projective one, namely W := V (G_{1}, …, G_{n}) = {x ∈ IP^{n}(k̄) ; G_{1}(x) = 0, …, G_{n}(x) = 0}. A simple minded way to proceed consists in taking as G_{1}, …, G_{n} just the homogenizations of the original system f_{1}, …, f_{n}. However this idea does not produce the desired effect even in case that the polynomials f_{1}, …, f_{n} form a regular sequence in k[X_{1}, …, X_{n}] . The reason is that the homogenizations of f_{1}, …, f_{n} need not to generate a complete intersection ideal.

In order to remedy this defect, many authors use homotopic deformations and path– following methods for the construction of a regular sequence of auxiliar homogeneous polynomials G_{1}, …, G_{n}, from whose zeroes the solutions of the original system f_{1}, …, f_{n} are then extracted (see [1], [10], [11], [12], [16], [22], [24], [27], [40], [41], [43], [47], [56]). The polynomials G_{1}, …, G_{n} are homogeneous in the variables X_{0}, X_{1}, …, X_{n}. Moreover they depend on a deformation parameter ε and form a regular sequence in k(ε)[X_{0}, X_{1}, …, X_{n}] . They define a zero dimensional projective subvariety of IP^{n}(\overline{k(ε)}) without points at infinity (here \overline{k(ε)} denotes any algebraic closure of the function field k(ε) ). Specializing the polynomials G_{1}, …, G_{n} in ε = 0 we obtain a projective subvariety of IP^{n}(k̄) which contains the isolated points of V as irreducible components. Since the underlying deformation is flat in the isolated points of V , well known techniques based on the implicit or explicit use of Macaulay’s u–resultant allow first to find the solutions of V (G_{1}, …, G_{n}) and finally the isolated points of V .

This deformation method introduces a somehow artificial dependency of the complexity of the algorithms on the regularity of the Hilbert function of the homogeneous ideal (G_{1}, …, G_{n}) of k(ε)[X_{0}, X_{1}, …, X_{n}] and on the degree of (G_{1}, …, G_{n}) which is defined by means of the Hilbert polynomial and is called its Bézout number. The regularity of (G_{1}, …, G_{n}) is bounded by nd − n. This implies that deformation based algorithms have

to triangulate rectangular matrices of size \binom{nd}{n} × n\binom{nd}{n} in order to extract from this

data some “geometrically meaningful” square matrix of size the Bézout number. The characteristic polynomial of this square matrix is the basic eliminating form that all algorithms work with. However, the Bézout number of the ideal (G_{1}, …, G_{n}) (i.e. the degree of the eliminating form) includes multiplicities and degrees of extraneous components which the previous deformation process adds to the original variety V . The exact value of the Bézout number is ∏_{i=1}^{n} degG_{i} which is of order d^{n}.

The method we present in this paper will be independent of “algebraic” quantities such as regularity of the Hilbert function or Bézout number of an appropriate homogeneous ideal. This allows in geometrically well suited cases (typically when the geometric degree of the variety V is low) to reduce the size of the matrices in the algorithms (and hence the complexity of the procedures). However, in worst case (e.g. when the equations f_{1}, …, f_{n} are generic) our complexity bounds are roughly the same as those obtained by deformation based algorithms. This is not surprising in view of the known lower bounds for elimination problems ( [31], [57]).

An important aspect of elimination procedures consists in the encoding of the polynomials appearing as inputs, outputs or intermediate results of the algorithm. Encoding polynomials by their coefficients (dense representation) faces us with an input size of order

\binom{d + n}{n} ≤ c · d^{n} (if n, d ≥ 3 we can take c = 1 , otherwise we can take as c the base

of the natural logarithm). If the equations f_{1}, …, f_{n} are generic, the geometric degree of the variety V and the Bézout number of the system (given by the homogenizations of f_{1}, …, f_{n}) coincide and are of order d^{n}. Thus, a complexity bound of type d^{O(n)} is both polynomial in the dense input size and the degree of the variety V , what is the best we can hope in worst case (see [31] and [57]).

However, when the geometric degree of V is low, one wishes to use more economic encodings of inputs, outputs and intermediate results. Such an encoding is given, for instance, by the data structure straight–line program.

For the moment let us fix the following notations and assumptions :

There is given a family of n input polynomials f_{1}, …, f_{n} ∈ k[X_{1}, …, X_{n}] which are thought to be encoded by a straight–line program (arithmetic circuit) β without essential divisions in k[X_{1}, …, X_{n}] (this means we allow β only to contain divisions by non–zero elements of k). We denote the nonscalar size (“nonscalar length” in more traditional terminology) and the nonscalar depth of β by L and ℓ respectively (see [23], [30], [40],

[59] and Section 2 for the notions of straight–line program, arithmetic network and the complexity measures we shall use subsequently).

Let us first consider the affine case. Here, we suppose that f_{1}, …, f_{n} form a regular sequence in k[X_{1}, …, X_{n}] . Fix 1 ≤ i ≤ n. The affine variety defined by the ideal (f_{1}, …, f_{i}) , namely V (f_{1}, …, f_{i}) , is a Zariski closed subset of A^{n} := A^{n}(k̄) of pure dimension n−i (i.e. all irreducible components of V (f_{1}, …, f_{i}) have the same dimension n − i; we say also that V (f_{1}, …, f_{i}) is an equidimensional variety of dimension n − i). The (geometric) affine degree of V (f_{1}, …, f_{i}) is defined as usual as the cardinality of the finite set of points we obtain cutting V (f_{1}, …, f_{i}) by n − i generic affine hyperplanes of A^{n} (more generally, we define the affine degree of a closed Zariski subset of A^{n} as the sum of the degrees of its irreducible components. See e.g. [29] or [21] for this notion of degree and its motivation). We denote the affine degree of V (f_{1}, …, f_{i}) by degV (f_{1}, …, f_{i}) .

Let us now define δ:= max{degV (f_{1}, …, f_{i}) ; 1 ≤ i ≤ n} as the (geometric) affine degree of the equation system f_{1}, …, f_{n}. We write V := V (f_{1}, …, f_{n}) and observe that V contains only finitely many, namely degV ≤ δ points.

Let us now consider the toric case. Fix 1 ≤ i ≤ n. We define the toric irreducible components of the affine variety V (f_{1}, …, f_{i}) as those which are not contained in one of the hyperplanes V (X_{j}) , 1 ≤ j ≤ n, of A^{n}. We suppose that f_{1}, …, f_{i} form a toric complete intersection. This means that toric irreducible components of V (f_{1}, …, f_{i}) exist having all dimension n − i. The (geometric) toric degree of V (f_{1}, …, f_{i}) is denoted by deg^{∗}V (f_{1}, …, f_{i}) and is defined as the sum of the affine degrees of all toric components of V (f_{1}, …, f_{i}) . We call δ^{∗}:= max{deg^{∗}V (f_{1}, …, f_{i}) ; 1 ≤ i ≤ n} the (geometric) toric degree of the equation system f_{1}, …, f_{n}.

Let be given a non–zero linear form H of k[X_{1}, …, X_{n}] represented by its coefficients and let T be a new variable. We consider as the fixed input of all our principal algorithms the division free straight–line program β which computes f_{1}, …, f_{n} and, where it makes sense, the coefficient n –tuple of H. We recall that d is an upper bound for the degrees of the polynomials of the input system f_{1}, …, f_{n}, that δ and δ^{∗} represent the geometric affine degree and the geometric toric degree of the system f_{1}, …, f_{n} respectively. Furthermore we recall that L and ℓ are the nonscalar size and depth of β respectively.

With these notations and assumptions, we may state our main results as follows :

Theorem 1 (the affine case) Assume that f_{1}, …, f_{n} form a regular sequence in k[X_{1}, …, X_{n}] . Suppose furthermore that for 1 ≤ i ≤ n the ideal (f_{1}, …, f_{i}) generated by f_{1}, …, f_{i} in k[X_{1}, …, X_{n}] is radical. Then there exists an arithmetic network with parameters in k̄ which, from the input given by β and H, computes the coefficients of a monic polynomial p ∈ k[T] such that p(H) vanishes on V = V (f_{1}, …, f_{n}) .The nonscalar size and depth of the network are (ndδL)^{O(1)} and O(n(log_{2}(nd) + ℓ)log_{2}δ) respectively.

Theorem 2 (the toric case) Assume that for 1 ≤ i ≤ n the polynomials f_{1}, …, f_{i} form a toric complete intersection and generate an ideal in k[X_{1}, …, X_{n}] whose localization (f_{1}, …, f_{i})_{∏_{j=1}^{n} X_{j}} is radical. Then there exists an arithmetic network with parameters

in k̄ which, from the input given by β and H, computes the coefficients of a monic polynomial p^{∗} ∈ k[T] such that p^{∗}(H) vanishes on the toric variety V^{∗} := V \ V ( ∏_{j=1}^{n} X_{j}) .

The nonscalar size and depth of the network are (ndδ^{∗}L)^{O(1)} and O(n(log_{2}(nd)+ℓ)log_{2}δ^{∗}) respectively.

Let us remark that the algorithms underlying Theorems 1 and 2 make substantial use of linear algebra subroutines dealing with matrices of size at most 2dδ (affine case) and 2dδ^{∗} (toric case).

We may sharpen the assertions of Theorem 1 and 2 to the following statement :

Theorem 3 Let f_{1}, …, f_{n} be polynomials of k[X_{1}, …, X_{n}] which satisfy the assumptions of Theorems 1 or 2. Then there exists an arithmetic network with parameters in k̄ which from the input given by the circuit β computes in the affine case the coefficients of polynomials q, v_{1}, …, v_{n} ∈ k[T] and in the toric case the coefficients of polynomials q^{∗}, v_{1}^{∗}, …, v_{n}^{∗} ∈ k[T] such that the following conditions hold :

i) q and q^{∗} are monic and have degrees degq = degV and degq^{∗} = degV^{∗} = deg^{∗}V respectively. Moreover v_{1}, …, v_{n} and v_{1}^{∗}, …, v_{n}^{∗} satisfy the degree bounds max{degv_{i} ; 1 ≤ i ≤ n} < degq and max{degv_{i}^{∗} ; 1 ≤ i ≤ n} < degq^{∗}.

ii) the zerodimensional varieties V and V^{∗} can be parameterized as

V = {(v_{1}(t), …, v_{n}(t)) ; t ∈ A^{1} , q(t) = 0} and
V^{∗} = {(v_{1}^{∗}(t), …, v_{n}^{∗}(t)) ; t ∈ A^{1} , q^{∗}(t) = 0}

.

The nonscalar size and depth of the network are (ndδL)^{O(1)} and O(n(log_{2}(nd) + ℓ)log_{2}δ) in the affine case and (ndδ^{∗}L)^{O(1)} and O(n(log_{2}(nd) + ℓ)log_{2}δ^{∗}) in the toric case.

Of course we can reformulate Theorems 1, 2 and 3 for sparse inputs. In this case the parameters L and ℓ measuring nonscalar size and depth of the input circuit β can be replaced by the sparsity N of the polynomials f_{1}, …, f_{n} and by log_{2}d respectively (the sparsity is the number of monomials with non–zero coefficients appearing in f_{1}, …, f_{n}). The nonscalar size and depth of the resulting network are then (ndδN)^{O(1)} and O(nlog_{2}(nd)log_{2}δ) in the affine case and (ndδ^{∗}N)^{O(1)} and O(nlog_{2}(nd)log_{2}δ^{∗}) in the toric case

The most important context of applications of Theorems 1, 2 and 3 is the following situation of “parametric/numeric equation solving” :

let Ω be a prime field with algebraic closure Ω̄ and let θ_{1}, …, θ_{m} be indeterminates over Ω (called “parameters”). Let k := Ω(θ_{1}, …, θ_{m}) (there will be no harm to our arguments in characteristic p since Ω is perfect). Suppose now that β is a division free straight–line program in Ω[θ_{1}, …, θ_{m}, X_{1}, …, X_{n}] of nonscalar length and depth L and ℓ respectively. Thus our polynomials f_{1}, …, f_{n} belong to the polynomial ring Ω[θ_{1}, …, θ_{m}, X_{1}, …, X_{n}] . Assume that H is a nonzero linear form of Ω[X_{1}, …, X_{n}] . The varieties V and V^{∗} are interpreted as subvarieties of the affine space A^{n}(k̄) = A^{n}(\overline{Ω(θ_{1}, …, θ_{m})}) . The remaining assumptions and notations are the same as in Theorems 1, 2 and 3 for k := Ω(θ_{1}, …, θ_{m}) .

In this situation the statement of Theorem 1, 2 and 3 can be sharpened as follows :

Theorem 4 There exists an arithmetic network with parameters from the field Ω̄ , which has nonscalar length (ndδL)^{O(1)} and depth O(n(log_{2}(nd) + ℓ)log_{2}δ) in the affine and which has nonscalar length (ndδ^{∗}L)^{O(1)} and depth O(n(log_{2}(nd) + ℓ)log_{2}δ^{∗}) in the toric case. This arithmetic network produces as output a division free straight–line program in Ω̄[θ_{1}, …, θ_{m}] , say γ, in the affine and γ^{∗} in the toric case. This straight–line program has the following properties :

• according to the case (affine or toric) the circuits γ and γ^{∗} represent the coefficients with respect to the variable T of polynomials p and p^{∗} or q, w_{1}, …, w_{n} and q^{∗}, w_{1}^{∗}, …, w_{n}^{∗} which belong to Ω[θ_{1}, …, θ_{m}, T] . Moreover in the situation where it makes sense γ and γ^{∗} compute also the (nonzero) discriminants ρ ∈ Ω[θ_{1}, …, θ_{m}] and ρ^{∗} ∈ Ω[θ_{1}, …, θ_{m}] of q and q^{∗}.

• the straight–line programs γ and γ^{∗} have asymptotically the same nonscalar size and depth as the arithmetic network generating them.

• the (monic in T ) polynomials p, p^{∗}, q, q^{∗} ∈ Ω[θ_{1}, …, θ_{m}, T] and the rational functions v_{1} := \frac{w_{1}}{ρ} , …, \frac{w_{n}}{ρ} ∈ Ω(θ_{1}, …, θ_{m})[T] and v_{1}^{∗}:= \frac{w_{1}^{∗}}{ρ} , …, \frac{w_{n}^{∗}}{ρ} ∈ Ω(θ_{1}, …, θ_{m})[T] have the properties stated for them in Theorems 1, 2 and 3 respectively. For instance in the situation of Theorem 1 the polynomial p(θ_{1}, …, θ_{m}, H) vanishes on V = V (f_{1}, …, f_{n}) = \{x ∈ \overline{Ω(θ_{1}, …, θ_{m})}^{n} ; f_{1}(x) = 0, …, f_{n}(x) = 0\} and in the situation of Theorem 3(i) the algebraic variety V has the form V = {v_{1}(t), …, v_{n}(t) ; t ∈ \overline{Ω(θ_{1}, …, θ_{m})} , q(θ_{1}, …, θ_{m}, t) = 0\}.

We shall omit the proof of Theorem 4 because it would be almost textually the same as that of Proposition 17 below.

A natural question to ask is the following one : what “real life” complexities are hidden behind the notions of arithmetic network and straight–line program with parameters in k̄? What is the link of these data structures to “ordinary” rational arithmetic networks and straight–line programs with parameters in the coefficient field k? For answering this question let us restrict ourselves to the affine case (the toric case can be discussed analogously).

A simple minded translation of the arithmetic network with parameters in k̄ underlying Theorem 1 to the rational context over k would produce an ordinary arithmetic network with parameters in k of nonscalar size and depth (ndδ^{n}L)^{O(1)} and O(n(log_{2}(dδ)+ℓ)) respectively. Whereas the nonscalar depth is fine, the nonscalar size of the network grows up to order of the sequential time complexity of usual Groebner basis computations for the elimination task we are considering, i.e. to (nd^{n^{2}})^{O(1)} in worst case (here we assume

that δ = d^{n} and L = \binom{d + n}{n} = O(d^{n}) holds; see [8] and [16]).

The problem arising in this way can be localized in the iterative character of the algorithm ( n iterations) which in the ordinary rational arithmetic network version produces stupidly growing straight–line programs for the representation of intermediate results. This is due to the repeated use of interpolation subroutines which nevertheless can be summarized by suitable FOR commands (see [25]). However, applying “data compression” by means of the already mentioned homotopic deformation method one can lower this ordinary network size to (nd^{n})^{O(1)} which is an already known complexity bound for the elimination task we are considering ([10], [11], [24], [40], [43]. See also [3], [12], [31], [44]). This means the advantage of the rational version of our method is reduced to exegetic “practical complexity” as far as running time is concerned (nevertheless we may have saved something with respect to storage space).

However a more radical compression of the enormously expanding straight–line programs during the execution of the algorithms is possible thanks to a symbolic adaptation of Newton’s method (or Hensel iteration as someones like to call it in case of positive characteristic) in combination with “Vermeidung von Divisionen” ([60]). This compression is done by the algorithm underlying the fundamental technical Lemmas 5 and 7 below.

The key point of our method consists in a consequent use of problem adapted data structures : arithmetic networks and straight–line programs with parameters in k̄ (or k). A similar ground idea may be found in the impressive theoretical and practical work of D. Duval and her school on dynamic evaluation ([18]). Closest to our complexity results comes the numeric method of M. Shub and S. Smale for finding “approximate” solutions of zero–dimensional homogeneous “average” equations systems ([56]). Their method too is independent on the Bézout number and the regularity of the input ideal. The sequential time complexity of their algorithm (measured as ours by counting just

arithmetic operations) is polynomial in n\binom{d + n}{n} (the size of the densely given input

system) and the number of approximate solutions wanted. However caution is necessary in the interpretation of their result as “equation solving” in the sense of computer algebra. First they need sufficient genericity of the system (just the contrary of the point of view of computer algebra which focuses on “special systems”). Secondly Newton iteration (for which they seek approximate solutions) is inefficient in terms of bit–complexity if the rational numbers appearing in it are given in binary coding. This fact is due to Liouville’s estimate (see [50]). However this second drawback can be avoided coding rational numbers by straight–line programs. Identity of rational numbers given by such encodings can be detected in random polynomial time by a BPP–test ([54], [34]) or a fixed sample test (as in [32] or [13]) which is due to [28]. Summarizing this we can say that in case Ω := 0 Q and k:= 0 Q(θ_{1}, …, θ_{m}) with θ_{1}, …, θ_{m} algebraically independent, our algorithms have a reasonable translation to the (probabilistic) bit–model and that this translation conserves the overall complexity character of our algorithms (this is work in progress and will be the subject of a further publication; see Section 7). Of course it would also be advantageous to dispose of algorithms of the same complexity type which are realizable exclusively by rational arithmetic networks and straight–line programs (with parameters in k). This is a question which we shall also consider in further work.

Our paper is organized as follows : in Section 2 we introduce our computational model of arithmetic networks and straight– line programs with parameters in k̄ (or k). In Section 3 we prove Lemma 5 and 7 which represent a key tool for our algorithms. Thanks to these lemmas we are able to compress efficiently certain straight–line programs which appear as intermediate computations in our procedures. The algorithm underlying Lemma 5 and 7 requires the use of algebraic numbers (observe that this situation produces the side effect that our subsequent arithmetic networks and straight–line programs depend on algebraic parameters). In Section 4 we review some known technical lemmas which are necessary for the proofs in Section 5. The essential steps of the proof of Theorem 1, 2 and 3 are contained in Section 5. This proof is based on a recursive construction of a Noether normalization and a primitive element for the varieties V (f_{1}, …, f_{i}) , 1 ≤ i ≤ n, followed by a procedure of cleaning extraneous irreducible components. This recursive construction is explained in Section 5 and a recursion law of the complexity of the underlying algorithm is given. At this point the application of Lemma 5 and 7 of Section 3 becomes crucial. A simple minded iteration of the recursive construction we introduce in Section 5 would lead to a size explosion of straight–line programs. Lemma 5 and 7 allow us to compress after each iteration step the straight–line programs occuring in our algorithm. The core of the proof of Theorem 1, 2 and 3 is contained in Proposition 17 and 18 which generalizes the statement of Theorem 3 to the case of arbitrary reduced complete intersection ideals. This proposition is used in Section 6 in order to formulate two division theorems (effective Nullstellensätze) with new complexity and degree bounds which are polynomial in our parameters n, d, δ and L (Theorem 19 and 20). These new division theorems do not improve the degree (and height) bounds of the classical ones ([3], [7], [8], [9], [17], [39], [40], [41], [51], [52]) but they have three advantages : the first one is that they are better suited for computational issues, the second one is that they are more general and the third one is that they explain better the classical results.

2 The Computational Model

The idea of using straight–line programs as succinct encodings of special polynomials (as they appear in elimination problems) goes back to the late seventies and was discovered by different people independently (one of them being our coauthor J. Morgenstern who prefered oral “hadise” to hardcover publications for the dissemination of his thought). This idea appears implicitly or explicitly in the following representative (although not exhaustive) list of papers, mostly dedicated to probabilistic testing of polynomial identities : [32], [34], [55], [15], [64]. First applications of this point of view to computer algebra dealt only with elimination of just one variable (absolute primality testing, greatest common divisor computation and factorization of multivariate polynomials; see [33], [37], [38]) and were later extended to multivariate elimination problems by means of “duality techniques” of different type and “Vermeidung von Divisionen” ([19], [24], [26], [40], [41]; see also [31]).

Straight–line programs and arithmetic circuits have their origins in the design of semi– numerical algorithms and represent a link between numerical analysis and computer science (see [23], [30], [59] and the references given there). In this section, we slightly modify the notion of “ordinary” arithmetic networks adding a special type of computation nodes, called “algebraic gates”. These gates display (generally algebraic) elements of k̄ which are given as zeroes of a precomputed univariate polynomial over k. We are now going to explain what we mean by “arithmetic network” and “straight–line program with parameters in k̄ (or k)”. Let for the moment K be any of the fields k or k̄.

A piecewise rational function (over K) is a mapping φ : A^{n} ⟶ A^{1} such that there exists a partition of A^{n} in K –definable constructible subsets {C_{j} : 1 ≤ j ≤ M}, such that for any 1 ≤ j ≤ M there exists a rational function ϕ_{j} ∈ K(X_{1}, …, X_{n}) defined everywhere on C_{j}, which verifies :

φ | C_{j} = ϕ_{j} | C_{j} .

An “ordinary” arithmetic network over K is a device that evaluates piecewise rational functions. However, in our applications, most of the functions are piecewise polynomial, i.e. the ϕ_{j} are polynomials belonging to K[X_{1}, …, X_{n}] .

An arithmetic network Γ over K is a pair Γ = (G, Q) , where G is directed acyclic graph, with vertices (called nodes or gates of Γ ) of indegree 0, 1, 2 or 3 and where Q is an assignment (labeling) of instructions and (piecewise) rational functions (“intermediate results”) to nodes (the labeling will be specified subsequently). The graph G contains n nodes of indegree 0, labeled by the variables X_{1}, …, X_{n}, which are called the input nodes of Γ .

We define the depth of a node ν of the graph G as the length of the longest path joining ν with some input gate. Let us denote any node of G by a pair of integers (i, j) , where i represents the depth of the node and j is an ordinal number assigned to the node which is given by some ordering of the set of nodes of depth i (see [40], [48] for this type of encoding of arithmetic networks).

Let (i, j) be a node of G. If (i, j) has indegree 0 and does not represent an input, the labeling Q assigns to this node a constant from K (which we call subsequently a parameter of Γ ). If (i, j) has indegree 2 the labeling Q assigns to it an arithmetic operation of k. If (i, j) has indegree 1 the labeling Q assigns to it a sign (i.e. equal to zero) test and a boolean variable. If (i, j) has indegree 3 the labeling Q assigns to it a selector which makes a choice between two prefixed nodes of G according to the value of a boolean variable associated with a third node. A node of G labeled in this manner is called a gate of Γ . We have already introduced the input gates. A gate which is labeled by a constant or an arithmetic operation of K is called a computation gate (in case of positive characteristic p we consider also extraction of p –th roots of elements of K as arithmetic operations). The other gates are called sign or selector gates, depending on their labeling. We suppose that the labeling Q is “meaningful”, i.e. computation gates have ingoing edges (if any) coming from computation or input gates, sign gates have an ingoing edge coming from a computation gate , and selector gates have two ingoing edges coming from computation or input gates and another ingoing edge coming from a sign gate. Under this hypothesis the labeling Q associates in a obvious way to each computation gate (i, j) a rational function which we denote by Q_{i,j}. Let (i, j) be a sign gate with ingoing edge coming from a node (r, s) and let x be a point of A^{n} where Q_{r,s} is defined. Then the boolean variable B_{i,j} associated to (i, j) takes the value 1 or 0 according to the truth or falseness of the statement “ Q_{i,j}(x) = 0 ”. If (i, j) is a selector gate with two ingoing edges coming from computation gates (k, l) and (k′, l′) and if x is a point of A^{n} where Q_{k,l} and Q_{k′,l′} are defined and if the third ingoing edge of (i, j) comes from the sign gate (r, s) then we associate to (i, j) the field element Q_{k,l}(x) or Q_{k′,l′}(x) according to the value which takes in x the boolean variable B_{r,s} associated to the sign gate. We consider the gates of Γ with outdegree 0 as outputs and we suppose that for each x ∈ A^{n} there exists a “stream” of “consistent” paths (with all rational functions defined in x) to a prefixed number of output gates.

A computation gate of Γ is called nonscalar (with respect to K) if the instruction associated to it corresponds to a multiplication of nonconstant rational functions or to a division by a nonconstant rational function. We assign to nonscalar computation gates unit costs whereas all other gates are taken cost–free (in particular, computation gates of Γ corresponding to K –linear operations are free). In this way, we associate two complexity measures to the arithmetic network Γ :

• nonscalar sequential time or the nonscalar size of Γ , defined as the total number of nonscalar computation gates of Γ ,

• nonscalar parallel time or the nonscalar depth of Γ defined as the longest oriented path of Γ joining an input gate with an output gate when only nonscalar computation gates are taken into account for the “length”.

These two nonscalar complexity measures are fairly realistic with respect to operation counting because Γ can always be rearranged such that the total number of gates and the total depth of Γ are bounded roughly by the square of its nonscalar size and depth respectively. The intuitive meaning of the nonscalar size of Γ is (sequential) running time whereas the nonscalar depth is linked to rather mathematical quantities as degree and height (in case K:= 0 Q ) of the rational functions appearing as intermediate results of Γ . The total depth of Γ has a natural interpretation as minimal storage space (see [40] for more details on this subject).

A special case of arithmetic networks are those which have as single output a boolean combination of sign gates. We call them decision networks. Another important case of special networks is represented by those which contain only computation gates (no sign or selector gates). They are called straight–line programs or arithmetic circuits and they compute (or represent) rational functions belonging to K(X_{1}, …, X_{n}) . Often we call the (nonscalar) size of a straight–line program its (nonscalar) length.

An arithmetic network or a straight–line program without any nonscalar division (only divisions by non–zero elements of K are allowed in this case) is called division free. Division free straight–line programs compute polynomials of K[X_{1}, …, X_{n}] . Finally we say that a family of arithmetic networks with nonscalar sequential time cost function L is well parallelizable if its nonscalar parallel time cost function ℓ behaves as ℓ = O(log_{2}L) .

Since we are not considering other complexity measures than the nonscalar ones, we simplify our terminology from now on saying just size/sequential time or depth/parallel time with reference to the nonscalar cost measure.

Suppose now K := k. We are going to extend the model of “ordinary” arithmetic networks (with parameters in k) introducing a new type of computation nodes, called algebraic gates. These algebraic gates involve for given inputs from k elements of k̄ which generally are algebraic over k ( in other words, these gates “compute” algebraic functions in the inputs). In order to explain the nature of these new gates let us assume that the arithmetic network Γ in question disposes over a second type of input nodes, labeled by indeterminates, say A_{1}, …, A_{m} which are called parameter variables. To understand this, remember that the concrete input for our geometric problems (e.g. in Theorem 1, 2 and 3) is always a division free straight–line program β in k[X_{1}, …, X_{n}] which represents the equations of the input system. The parameter variables A_{1}, …, A_{m} of Γ are specialized for a concrete input circuit β into the values of the program parameters of β, i.e. into values belonging to k. Therefore in all our applications the number m will be of order L^{2} . Some computation nodes of the arithmetic circuit Γ will therefore depend exclusively on the parameter variables A_{1}, …, A_{m}. The labeling Q assigns to these nodes a rational function of k(A_{1}, …, A_{m}) . We call such a node of Γ parameter gate. Let T be a new indeterminate. An algebraic gate of Γ is now a node (i, j) which has indegree and outdegree N , where N is an arbitrary (but fixed) natural number. The ingoing edges of (i, j) are supposed to come from N parameter gates of Γ , say (s_{0}, r_{0}), …, (s_{N−1}, r_{N−1}) , to which the labeling Q assigns polynomials h_{0}, …, h_{N−1} ∈ k[A_{1}, …, A_{m}] . Consider now an arbitrary specialization α = (α_{1}, …, α_{m}) ∈ k^{m} of the parameter variables A_{1}, …, A_{m} in k (such a specialization represents in our applications always a concrete input circuit β). The polynomials h_{0}, …, h_{N−1} take in the argument α values η_{0} := h_{0}(α), …, η_{N−1} := h_{N−1}(α) which belong to k. The algebraic gate (i, j) assigns then to its N outgoing edges the totality of the zeroes of the univariate polynomial T^{N} + η_{N−1}T^{N−1} + ⋯ + η_{0} ∈ k[T] in arbitrary order (possibly with repetitions if the polynomial is not separable). Let us observe that the network Γ evaluates the polynomials h_{0}, …, h_{N−1} in the argument α using possibly algebraic parameters which come from the previous use of algebraic gates. Thus the network contains implicitly a straight–line program representation of the values h_{0}(α), …, h_{N−1}(α) which will be division free in all our applications and which contains possibly algebraic parameters. If Γ is an arithmetic network which contains algebraic gates we shall say that Γ has parameters in k̄.

3 Compressing Straight–line Programs

In this section we show how we can compress in the algorithm underlying Theorems 1, 2 and 3 some of the straight–line programs which compute intermediate results. The principal outcome is the following statement :

Lemma 5 (the affine case) Let be given polynomials f_{1}, …, f_{i} ∈ k[X_{1}, …, X_{n}] and suppose that f_{1}, …, f_{i} are represented by a division free straight–line program β in k[X_{1}, …, X_{n}] of length and depth L and ℓ respectively. Assume that the polynomials f_{1}, …, f_{i} form a regular sequence in k[X_{1}, …, X_{n}] and that they generate a radical ideal I:= (f_{1}, …, f_{i}) . Let W:= V (f_{1}, …, f_{i}) = V (I) be the affine variety defined by f_{1}, …, f_{i} and denote by δ := degW the (geometric affine) degree of W and by r := n − i its dimension (observe that by assumption the ideal I is unmixed and the variety W is equidimensional). Suppose that X_{1}, …, X_{n} are in Noether position with respect to the variety W , the variables X_{1}, …, X_{r} being free and assume that there is given by its coefficients a nonzero linear form u ∈ k[X_{r+1}, …, X_{n}] which represents a primitive element for I (see Section 4.3 below). The equations f_{1}, …, f_{i}, the variables X_{1}, …, X_{n} and the linear form u determine uniquely the following mathematical objects :

• the minimal polynomial q ∈ k[X_{1}, …, X_{r}, u] of u modulo the ideal I. This polynomial is monic and without loss of generality separable with respect to u and satisfies deg_{u}q = degq ≤ δ. Let us call δ̄:= deg_{u}q = degq.

• the (nonzero) discriminant ρ ∈ k[X_{1}, …, X_{r}] of q and polynomials v_{r+1}, …, v_{n} ∈ k[X_{1}, …, X_{r}, u] satisfying the conditions

I_{ρ} = (q(u), ρX_{r+1} − v_{r+1}(u), …, ρX_{n} − v_{n}(u))_{ρ}
max{deg_{u}v_{j} ; r < j ≤ n} < δ̄ ≤ δ.

Finally we assume that the polynomial ρ and the coefficients of q and v_{r+1}, …, v_{n} with respect to u are given by a division free straight–line program β′ in k̄[X_{1}, …, X_{r}] having length and depth Λ and λ respectively.

Under these assumptions there exists an arithmetic network with parameters in k̄ which from the input circuits β and β′ constructs a division free straight–line program γ in k[X_{1}, …, X_{r}] of length O((i^{5} + L)δ^{11}) and depth O((log_{2}i + ℓ)log_{2}δ) such that γ represents ρ and the coefficients of q and v_{r+1}, …, v_{n} with respect to u. The size and depth of this network is O((i^{5} + L)δ^{11}) + Λ and O((log_{2}i + ℓ)log_{2}δ) + λ respectively.

For the proof of Lemma 5 we need the following fact :

Remark 6 (the affine case) Let assumptions and notations be as in Lemma 5. Then the degrees of ρ and of the coefficients of v_{r+1}, …, v_{n} with respect to u are bounded by 2(degq)^{3} = 2δ̄^{3} , i.e. by 2δ^{3} .

We show this remark later.

Proof of Lemma 5.

Let us introduce the following notations :

B:= k[X_{1}, …, X_{n}]/I ; A:= k[X_{1}, …, X_{r}]
K:= k(X_{1}, …, X_{r}) ; B′:= K[X_{r+1}, …, X_{n}]/(I),

where (I) denotes the ideal generated by the set I (or by f_{1}, …, f_{i}) in K[X_{r+1}, …, X_{n}] .

Recall that the polynomials f_{1}, …, f_{i} form a regular sequence in k[X_{1}, …, X_{n}] and that the variables X_{1}, …, X_{n} are in Noether position with respect to W , the variables X_{1}, …, X_{r} being free. Taking this into account, we write π : W ⟶ A^{r} for the finite and surjective morphism of affine varieties induced by the coordinates X_{1}, …, X_{r}. Furthermore we deduce from our assumptions (in particular from the assumption q separable with respect to u) that the finite dimensional K –algebra B′ is unramified and that dim_{K}B′ = deg_{u}q ≤ degW = δ holds ([35]). From this we infer that the jacobian

Δ:= det (\frac{∂f_{k}}{∂X_{j}} )_{{1≤k≤i \atop r+1≤j≤n}}

is a nonzero divisor modulo I. Let us observe that the polynomial Δ can be evaluated by a division free straight–line program in k[X_{1}, …, X_{n}] of length O(i^{5} + L) and depth O(log_{2}i + ℓ) .

Let μ ∈ k[X_{1}, …, X_{r}] be the constant term of the characteristic polynomial of Δ modulo I. Since Δ represents a nonzero divisor of B we conclude μ ≠ 0 . Furthermore we observe that μ can be evaluated by a division free straight–line program in k[X_{1}, …, X_{r}] of length (iδL)^{O(1)} + Λ and depth O(log_{2}(iδ) + ℓ) + λ, and so does the product ρ · μ.

Using a correct test sequence (see [32]) we are able to find in sequential time (iδL)^{O(1)}Λ^{2} and parallel time O(log_{2}(iδ) + ℓ) + λ a “rational” point η = (η_{1}, …, η_{r}) ∈ k^{r} which satisfies (ρ · μ)(η) ≠ 0 (thus we have ρ(η) ≠ 0 and μ(η) ≠ 0 ). From μ(η) ≠ 0 we deduce that the morphism π is unramified in the point η what implies that π^{−1}(η) consists of exactly δ̄ nonsingular points of W . To be more precise, let π^{−1}(η) = {ξ_{1}, …, ξδ̄} ⊂ W be the set of these points. Then we infer from μ(η) ≠ 0 that Δ(ξ_{l}) ≠ 0 holds for any 1 ≤ l ≤ δ̄.

From π(ξ_{l}) = η = (η_{1}, …, η_{r}) we conclude that the point ξ_{l} has the form ξ_{l} = (η_{1}, …, η_{r}, ξ_{r+1}^{(l)}, …, ξ_{n}^{(l)}) ∈ k̄^{n} where the first r coordinates η_{1}, …, η_{r} are rational and independent of the index l and the last n − r coordinates ξ_{r+1}^{(l)}, …, ξ_{n}^{(l)} are algebraic (i.e. belong to k̄ and not necessarily to k) and dependent on l. Let the linear form u have the form u = θ_{r+1}X_{r+1} + ⋯ + θ_{n}X_{n} with θ_{r+1}, …, θ_{n} ∈ k. For 1 ≤ l ≤ δ̄ we write ζ_{l}:= u(ξ_{l}) = θ_{r+1}ξ_{r+1}^{(l)} + ⋯ + θ_{n}ξ_{n}^{(l)} (observe that ζ_{l} is typically an algebraic element of k̄). Let us consider u as an indeterminate over k and over k[X_{1}, …, X_{r}] . In this sense q = q(X_{1}, …, X_{r}, u) becomes a polynomial in u with coefficients in k[X_{1}, …, X_{r}] and q(η, u) := q(η_{1}, …, η_{r}, u) becomes a polynomial in u with coefficients in k (i.e. we have q(η, u) ∈ k[u] ). Since q is monic in u and of degree δ̄ we conclude that q(η, u) is monic and of degree δ̄ too. Furthermore ρ(η) is the discriminant of q(η, u) and from ρ(η) ≠ 0 we deduce that q(η, u) has exactly δ̄ zeroes in k̄ which are all distinct. Let us analyze this fact more in detail : for any polynomial p ∈ k[X_{1}, …, X_{n}] let us write p(η, X_{r+1}, …, X_{n}) := p(η_{1}, …, η_{r}, X_{r+1}, …, X_{n}) (thus we have p(η, X_{r+1}, …, X_{n}) ∈ k[X_{r+1}, …, X_{n}] ). We observe that {ξ_{1} …, ξδ̄} = π^{−1}(η) = {η}×V (f_{1}(η, X_{r+1}, …, X_{n}), …, f_{i}(η, X_{r+1}, …, X_{n})) holds. From I_{ρ} = (q(u), ρX_{r+1} − v_{r+1}(u), …, ρX_{n} − v_{n}(u))_{ρ} we deduce that for any 1 ≤ l ≤ δ̄ the identities

ξ_{l} = (η_{1}, …, η_{r}, \frac{v_{r+1}(η, ζ_{l})}{ρ(η)}, …, \frac{v_{n}(η, ζ_{l})}{ρ(η)})

and q(η, ζ_{l}) = 0 hold (as before we write v_{j}(η, u):= v_{j}(η_{1}, …, η_{r}, u) ∈ k[u] for r < j ≤ n). Since the points ξ_{1}, …, ξδ̄ are all different we conclude that the values ζ_{1}, …, ζδ̄ ∈ k̄ are distinct zeroes of the polynomial q(η, u) ∈ k[u] . Since q(η, u) is monic and of degree δ̄ we conclude now that

q(η, u) = ∏_{l=1}^{δ̄}(u − ζ_{l})

holds. Thus the values ζ_{1}, …, ζ_{δ} are exactly the zeroes of q(η, u) .

Replacing in all polynomials f_{1}, …, f_{i}, ρ, q, v_{r+1}, …, v_{n} the variables X_{1}, …, X_{r} by the new ones X_{1} − η_{1}, …, X_{r} − η_{r} and leaving the remaining variables X_{r+1}, …, X_{n} and u unchanged, we may assume without loss of generality that η = (0, …, 0) ∈ k^{r} holds. Let 1 ≤ l ≤ δ̄. Recall that ξ_{l} = (η_{1}, …, η_{r}, ξ_{r+1}^{(l)}, …, ξ_{n}^{(l)}) = (0, …, 0, ξ_{r+1}^{(l)}, …, ξ_{n}^{(l)}) ,

0 = f_{1}(ξ_{l}) = f_{1}(η, ξ_{r+1}^{(l)}, …, ξ_{n}^{(l)}) = f_{1}(0, …, 0, ξ_{r+1}^{(l)}, …, ξ_{n}^{(l)})

⋮
0 = f_{i}(ξ_{l}) = f_{i}(η, ξ_{r+1}^{(l)}, …, ξ_{n}^{(l)}) = f_{i}(0, …, 0, ξ_{r+1}^{(l)}, …, ξ_{n}^{(l)})

and

0 ≠ Δ(ξ_{l}) = Δ(η, ξ_{r+1}^{(l)}, …, ξ_{n}^{(l)}) = Δ(0, …, 0, ξ_{r+1}^{(l)}, …, ξ_{n}^{(l)})

holds. Thus the point (ξ_{r+1}^{(l)}, …, ξ_{n}^{(l)}) ∈ k̄^{i} is a nondegenerate zero of the equation system given by the polynomials f_{1}(η, X_{r+1}, …, X_{n}), …, f_{i}(η, X_{r+1}, …, X_{n}) ∈ k[X_{r+1}, …, X_{n}] which are in fact the polynomials f_{1}(0, …, 0, X_{r+1}, …, X_{n}), …, f_{i}(0, …, 0, X_{r+1}, …, X_{n}) . From Hensel’s lemma (which represents a symbolic version of the Implicit Function Theorem) we deduce that there exist formal power series R_{r+1}^{(l)}, …, R_{n}^{(l)} ∈ k̄[[X_{1}, …, X_{r}]] with R_{r+1}^{(l)}(η) = ξ_{r+1}^{(l)}, …, R_{n}^{(l)}(η) = ξ_{n}^{(l)} such that for R^{(l)} := (X_{1}, …, X_{r}, R_{r+1}^{(l)}, …, R_{n}^{(l)}) the identities

f_{1}(R^{(l)}) = 0, …, f_{i}(R^{(l)}) = 0  (1)

hold in k̄[[X_{1}, …, X_{r}]] (see [35] or [63]). Our next task is the construction of a “sufficiently accurate rational approximation” of the solution R^{(l)} of the system given by the polynomials f_{1}, …, f_{i}. This rational approximation will be represented by rational functions R̃_{r+1}^{(l)}, …, R̃_{n}^{(l)} ∈ k̄(X_{1}, …, X_{r}) which are all defined in the point η = (0, …, 0) and can therefore be interpreted as power series belonging to k̄[[X_{1}, …, X_{r}]] . For each r < j ≤ n the power series interpretation of the rational function R̃_{j}^{(l)} will satisfy the congruence relation

R_{j}^{(l)} − R̃_{j}^{(l)} ∈ (X_{1}, …, X_{r})^{2δ̄^{3}+1}  (2)

where (X_{1}, …, X_{r})^{2δ̄^{3}+1} denotes the ( 2δ̄^{3} +1 )–th power of the ideal generated by X_{1}, … …, X_{r} in k̄[[X_{1}, …, X_{r}]] . The i –tuple of rational functions (R̃_{r+1}^{(l)}, …, R̃_{n}^{(l)}) is defined by applying to the system f_{,} …, f_{i} at least 3⌈log_{2}δ̄⌉+2 , i.e. roughly 3⌈log_{2}δ⌉+2 Newton iteration steps starting from the particular nondegenerate solution ξ_{l} = (0, …, 0, ξ_{r+1}^{(l)}, …, ξ_{n}^{(l)}) ∈ k̄^{n} (here we consider f_{1}, …, f_{i} as i –variate polynomials depending on the variables X_{r+1}, …, X_{n}). In order to compute (R̃_{r+1}^{(l)}, …, R̃_{n}^{(l)}) we have to evaluate the polynomials f_{k} and their partial derivatives \frac{∂f_{k}}{∂X_{j}} for 1 ≤ k ≤ i and r < j ≤ n at 3⌈log_{2}δ⌉ + 2 iteration points. By [2] and [40] (see also [49]) this can be done by a division free straight– line program of size O(Llog_{2}δ) and depth O(ℓlog_{2}δ) . Moreover we have to invert the jacobian matrix (\frac{∂f_{k}}{∂X_{j}} )_{{1≤k≤i \atop r<j≤n}} at the same 3⌈log_{2}δ⌉ + 2 iteration points. This costs addi-

tional O(i^{5}log_{2}δ) nonscalar arithmetic operations organized in depth O(log_{2}ilog_{2}δ) (see [5]; observe also that these matrix inversions require divisions). Thus (R̃_{r+1}^{(l)}, …, R̃_{n}^{(l)}) are represented by a straight–line program γ̃_{l} in k̄(X_{1}, …, X_{r}) which contains as intermediate results only rational functions which are defined in the point η = (0, …, 0) . The size and depth of γ̃_{l} are O((i^{5} + L) log_{2} δ) and O((log_{2}i + ℓ) log_{2} δ) respectively.

For each 1 ≤ l ≤ δ̄, let us write R̃^{(l)} := (X_{1}, …, X_{r}, R̃_{r+1}^{(l)}, …, R̃_{n}^{(l)}) . We are going to consider u^{(l)} := u(R^{(l)}) = θ_{r+1}R_{r+1}^{(l)} + ⋯ + θ_{n}R_{n}^{(l)} and ũ^{(l)} := u(R̃^{(l)}) = θ_{r+1}R̃_{r+1}^{(l)} + ⋯ + θ_{n}R̃_{n}^{(l)} . Observe that R_{r+1}^{(l)}(η) = ξ_{r+1}^{(l)}, …, R_{n}^{(l)}(η) = ξ_{n}^{(l)} implies u^{(l)}(η) = ζ_{l}. Without any nonscalar extra cost we may assume that γ̃_{l} computes also the rational function ũ^{(l)} = θ_{r+1}R̃_{r+1}^{(l)} + ⋯ + θ_{n}R̃_{n}^{(l)} . Let γ̃ be the straight–line program in k̄(X_{1}, …, X_{r}) which we obtain by joining all circuits γ̃_{1}, …, γ̃δ̄. The straight–line program γ̃ computes ũ^{(1)}, …, ũ^{(δ̄)} and has size O((i^{5} + L)δ log_{2} δ) and depth O((log_{2}i + ℓ) log_{2} δ) . Observe that all the intermediate results of γ̃ are defined in the point η = (0, …, 0) .

Let 1 ≤ l ≤ δ̄. Taking into account that q is the minimal polynomial of u modulo the ideal I = (f_{1}, …, f_{i}) we deduce from (1) and the assumptions of the lemma the identity q(X_{1}, …, X_{r}, u^{(l)}) = 0 . Moreover (2) implies that the congruence relation

u^{(l)} − ũ^{(l)} ∈ (X_{1}, …, X_{r})^{2δ̄^{3}+1}  (3)

holds in the power series ring k̄[[X_{1}, …, X_{r}]] .

Recall that we consider q as a polynomial in u with coefficients in k[X_{1}, …, X_{r}] . Moreover q is monic in u and of total degree δ̄. Thus the polynomial q has the form

q = ∑_{0≤m≤δ̄}q_{m}u^{m} with q_{m} ∈ k[X_{1}, …, X_{r}] and degq_{m} ≤ δ̄ for 0 ≤ m ≤ δ̄. Furthermore

we have q_{δ̄} = 1 . On the other hand we know already that q(X_{1}, …, X_{r}, u^{(l)}) = 0 holds for any 1 ≤ l ≤ δ̄. From u^{(l)}(η) = ζ_{l} we deduce that the power series u^{(1)}, …, u^{(δ̄)} are all distinct. Since q is monic and of degree δ̄ in u and u^{(1)}, …, u^{(δ̄)} are distinct zeroes of q we conclude that in k̄[[X_{1}, ⋯, X_{r}]][u] the identity

q = ∏_{1≤l≤δ̄}(u − u^{(l)})  (4)

holds. For 0 ≤ m ≤ δ̄ let us denote by σ_{m} the m –th elementary symmetric function in δ̄ arguments. From (4) we deduce q_{m} = (−1)^{δ̄−m}σ_{m}(u^{(1)}, …, u^{(δ̄)}) . In combination with (3) this implies that for 0 ≤ m < δ̄ the congruence relation

q_{m} − (−1)^{δ̄−m}σ_{m}(ũ^{(1)}, …, ũ^{(δ̄)}) ∈ (X_{1}, …, X_{r})^{δ̄+1}  (5)

holds in the power series ring k̄[[X_{1}, …, X_{r}]] . As for 0 ≤ m ≤ δ̄ the polynomial q_{m} ∈ k[X_{1}, …, X_{r}] has degree at most δ̄ we deduce from (5) that the power series expansion of (−1)^{δ̄−m}σ_{m}(ũ^{(1)}, …, ũ^{(δ̄)}) ∈ k̄[[X_{1}, …, X_{r}]] coincides up to degree δ̄ with q_{m}. Combining the straight–line program γ̃ which computes the rational functions ũ^{(1)}, …, ũ^{(δ̄)} with a fast and well–parallelizable algorithm for the evaluation of the set of elementary symmetric functions {σ_{m} ; 0 ≤ m ≤ δ̄} (see [61], Satz 3.1. and [36], Chapter 8, Exercise 8.15) we obtain an arithmetic circuit γ_{0} in k̄(X_{1}, …, X_{r}) which for 0 ≤ m < δ̄ computes all rational functions (−1)^{δ̄−m}σ_{m}(ũ^{(1)}, …, ũ^{(δ̄)}) . The circuit γ_{0} has size O((i^{5} + L)δ log_{2} δ) and depth O((log_{2}i + ℓ) log_{2} δ) and all its intermediate results are rational functions of k̄(X_{1}, …, X_{r}) which are defined in η = (0, …, 0) . Taking this last observation into account we apply to the circuit γ_{0} the well–parallelizable Vermeidung von Divisionen technique contained in the proof of [40], Proposition 21. (With respect to parallelism we observe here that only one division by a suitable power of Δ is necessary at the very end of the procedure. If one is interested only in the sequential aspect of this technique one may apply directly the simpler algorithm underlying [60], Satz 2). In this way we obtain a division free straight–line program γ_{1} in k̄[X_{1}, …, X_{r}] which for 0 ≤ m < δ̄ computes the power series expansion in k̄[[X_{1}, …, X_{r}]] of all rational functions (−1)^{δ̄−m}σ_{m}(ũ^{(1)}, …, ũ^{(δ̄)}) up to degree δ̄. Since for 0 ≤ m < δ̄ these truncated power series expansions coincide with the polynomials q_{m} ∈ k[X_{1}, …, X_{r}] we conclude that γ_{1} represents these polynomials and hence the coefficients of q in the representation q = ∑_{0≤m≤δ̄}q_{m}u^{m}. The size and depth of γ_{1} are O((i^{5} + L)δ^{3} log_{2} δ) and

O((log_{2}i + ℓ) log_{2} δ) respectively.

Once given the straight–line program representation γ_{1} of the coefficients q_{m} of the polynomial q we are able to compute the discriminant ρ using additional O(δ^{5}) arithmetic operations organized in depth O(log_{2}δ) . Therefore we can extend the circuit γ_{1} to a division free straight–line program γ_{2} in k̄[X_{1}, …, X_{r}] of roughly the same size and depth as γ_{1} , such that γ_{2} computes also the discriminant ρ.

In order to finish the proof of Lemma 5 we have to find a straight–line program representation of the coefficients of the polynomials v_{r+1}, …, v_{n} with respect to the variable u such that the resulting circuit has about the same size and depth as γ_{2} . By the way we shall assume without loss of generality that the circuit γ_{1} (and hence γ_{2} ) contains the circuit γ̃.

Let r < j ≤ n and let v_{j} = ∑_{0≤m<δ̄}a_{m}^{(j)}u^{m} with a_{m}^{(j)} ∈ k[X_{1}, …, X_{r}] . From (1) and

the assumptions of the lemma we deduce that for any 1 ≤ l ≤ δ̄ the identity

v_{j}(u^{(l)}) − ρR_{j}^{(l)} = 0  (6)

holds. Taking into account the degree bound deg_{u}v_{j} < δ̄ we interpret the identities (6) as an inhomogeneous δ̄×δ̄ linear equation system for the coefficient vector (a_{0}^{(j)}, …, a_{δ̄−1}^{(j)}) of v_{j}. The matrix of this equation system is the δ̄×δ̄ Vandermonde matrix corresponding to the δ̄ (distinct) power series (u^{(1)}, …, u^{(δ̄)}) and its inhomogeneous part is the row vector we get transposing the δ̄–tuple (ρR_{j}^{(1)}, …, ρR_{j}^{(δ̄)}) . From (2) and (3) and the assumptions of the lemma we deduce as before that for any 1 ≤ l ≤ δ̄ the congruence relation

v_{j}(ũ^{(l)}) − ρR̃_{j}^{(l)} ∈ (X_{1}, …, X_{r})^{2δ̄^{3}+1}  (7)

holds in k̄[[X_{1}, …, X_{r}]] . We interpret now the congruence relations (7) as an inhomogeneous δ̄ × δ̄ linear equation system whose (unique) solution is a rational approximation to the coefficient vector (a_{0}^{(j)}, …, a_{δ̄−1}^{(j)}) of v_{j}. More precisely we extend the circuit γ_{2}

which computes ρ and for 1 ≤ l ≤ δ̄ the rational functions ũ^{(l)} and R̃_{j}^{(l)} to a straight– line program γ′_{j} in k̄(X_{1}, …, X_{r}) as follows : for 1 ≤ l ≤ δ̄ the circuit γ′_{j} contains as intermediate results the rational functions ρR̃_{j}^{(l)} . Moreover γ′_{j} computes rational func-

tions ã_{0}^{(j)}, …, ã_{δ̄−1}^{(j)} which are obtained by multiplying the δ̄–tuple (ρR_{j}^{(1)}, …, ρR_{j}^{(δ̄)}) by the inverse of the Vandermonde matrix corresponding to the (distinct) rational functions (ũ^{(1)}, …, ũ^{(δ̄)}) . We observe that all intermediate results of γ′_{j} are rational functions of k̄(X_{1}, …, X_{r}) which are defined in the point η = (0, …, 0) . Moreover γ′_{j} has size and depth O((i^{2} + L)δ^{3}log_{2}δ + δ^{5}) and O((log_{2}i + ℓ)log_{2}δ) respectively. From (6) and (7) we deduce that for any 0 ≤ m < δ̄ the congruence relation

a_{m}^{(j)} − ã_{m}^{(j)} ∈ (X_{1}, …, X_{r})^{2δ̄^{3}+1}  (8)

holds in k̄[[X_{1}, …, X_{r}]] .

By Remark 6 the degree of any polynomial a_{m}^{(j)} ∈ k[X_{1}, …, X_{r}] is bounded by 2δ̄^{3} . Therefore (8) implies that the power series expansion of the rational function ã_{m}^{(j)} in k̄[[X_{1}, …, X_{r}]] coincides up to degree 2δ̄^{3} with a_{m}^{(j)} . We join now all the circuits γ′_{r+1}, …, γ′_{n} and apply to them the same Vermeidung von Divisionen technique as before. In this way we obtain a division–free straight–line program γ in k̄[X_{1}, …, X_{r}] which computes for r < j ≤ n and 0 ≤ m < δ̄ the power series expansions in k̄[[X_{1}, …, X_{r}]] of all rational functions ã_{m}^{(j)} up to degree 2δ̄^{3} . Since for r < j ≤ n and 0 ≤ m < δ̄ this truncated power series expansions coincide with the polynomials a_{m}^{(j)} , the circuit γ represents all coefficients with respect to u of the polynomials v_{r+1}, …, v_{n}. Without loss of generality we may assume that the straight–line program γ extends the circuit γ_{2} . Thus finally the straight–line program γ computes ρ and all the coefficients of q and v_{r+1}, …, v_{n}. with respect to u. The size and depth of γ are O((i^{5} + L)δ^{9}log_{2}δ + δ^{11}) = O((i^{5} + L)δ^{11}) and O((log_{2}i + ℓ)log_{2}δ) respectively.

We shall make use of Lemma 5 in the proof of Theorem 1 and Theorem 3 (i) which deal with the zerodimensional algorithmic elimination problem in the affine case. For the same problem in the toric case, i.e. for Theorem 2 and Theorem 3 (ii) , we need a slightly different version of Lemma 5.

This is the content of the next statement.

Lemma 7 (the toric case) Let be given polynomials f_{1}, …, f_{i} ∈ k[X_{1}, …, X_{n}] and suppose that f_{1}, …, f_{i} are represented by a division free straight–line program β in k[X_{1}, …, X_{n}] of length and depth L and ℓ respectively. Let also g := ∏_{j=1}^{n} X_{j}. Assume

that the polynomials f_{1}, …, f_{i} form a toric complete intersection ideal I := (f_{1}, …, f_{i}) whose localization I_{g} is radical. Let W^{∗} be the union of the toric irreducible components of the affine variety V (f_{1}, …, f_{i}) = V (I) defined by f_{1}, …, f_{i} and denote by δ^{∗} := degW^{∗} = deg^{∗}V (f_{1}, …, f_{i}) the (geometric) degree of W^{∗} and by r := n − i its dimension (observe that by assumption the localized ideal I_{g} is unmixed and the “toric” variety W^{∗} is equidimensional). We assume that W^{∗} is not empty, i.e. δ^{∗} > 0 . Suppose that X_{1}, …, X_{n} are in Noether position with respect to the variety W^{∗}, the variables X_{1}, …, X_{r} being free and assume that there is given by its coefficients a nonzero linear form u ∈ k[X_{r+1}, …, X_{n}] which represents a primitive element for I_{g} (see Section 4.3 below). The equations f_{1}, …, f_{i}, the variables X_{1}, …, X_{n} and the linear form u determine uniquely the following mathematical objects :

• a polynomial q^{∗} ∈ k[X_{1}, …, X_{r}, u] which is monic and without loss of generality separable with respect to u and satisfies deg_{u}q^{∗} = degq^{∗} ≤ δ^{∗}

• the (nonzero) discriminant ρ^{∗} ∈ k[X_{1}, …, X_{r}] of q^{∗} and polynomials v_{r+1}^{∗}, …, v_{n}^{∗} ∈ k[X_{1}, …, X_{r}, u] satisfying the conditions

I_{ρ^{∗}g} = (q^{∗}(u), ρ^{∗}X_{r+1} − v_{r+1}^{∗}(u), …, ρ^{∗}X_{n} − v_{n}^{∗}(u))_{ρ^{∗}g}
max{deg_{u}v_{j}^{∗} ; r < j ≤ n} < degq^{∗} ≤ δ^{∗}.

Finally we assume that the polynomial ρ^{∗} and the coefficients of q^{∗} and v_{r+1}^{∗}, …, v_{n}^{∗} with respect to u are given by a division free straight–line program β^{∗} in k̄[X_{1}, …, X_{r}] having length and depth Λ^{∗} and λ^{∗} respectively.

Under these assumptions there exists an arithmetic network with parameters in k̄ which from the input circuits β and β^{∗} constructs a division free straight–line program γ^{∗} in k̄[X_{1}, …, X_{r}] of length O((i^{5} + L)δ^{∗}^{11}) and depth O((log_{2}i + ℓ)log_{2}δ^{∗}) such that γ^{∗} represents ρ^{∗} and the coefficients of q^{∗} and v_{r+1}^{∗}, …, v_{n}^{∗} with respect to u. The size and depth of this network is O((i^{5} + L)δ^{∗}^{11}) + Λ^{∗} and O((log_{2}i + ℓ)log_{2}δ^{∗}) + λ^{∗} respectively. This statement remains true if “toricity” is understood with respect to a linear change of the original variables X_{1}, …, X_{n} and the polynomial g = ∏_{j=1}^{n} X_{j} is replaced by the

product of the new variables.

Since the proof of Lemma 5 is completely local, only minor changes at its very beginning and the application of a suitable toric version of Remark 6 at its very end are necessary to convert it into a proof of Lemma 7. The essential steps and arguments are almost textually the same. The most subtle point is the toric version of Remark 6 we need at the end of the proof. For the statement of this toric version we replace just in Remark 6 the polynomials ρ, v_{r+1}, …, v_{n} by ρ^{∗}, v_{r+1}^{∗}, …, v_{n}^{∗} and the degree bound by 2(degq^{∗})^{3} , i.e. by 2(δ^{∗})^{3} . We shall come back to the proof of that at the end of this section. In order to avoid repetitive argumentation we omit the proof of Lemma 7.

The following Remark 8 refers to work in progress. It answers the question whether computing with algebraic elements of k̄ is really necessary in the algorithm underlying Lemma 5 and 7. On the other hand one might ask whether to this algorithm corresponds a counterpart in the bit model of boolean circuits in case k:= 0 Q . We postpone the answer to this second question to the end of the paper (see Section 7).

Suppose now that k is a hilbertian field for which a factorization algorithm for univariate polynomials is available at “moderate arithmetic costs”. This means that we may add (in a computationally reasonable way) to our arithmetic networks over k special factorization gates for univariate polynomials of degree D, where D is an arbitrary (but fixed) natural number. Our new complexity model takes such a gate into account at costs of D^{O(1)} with respect to sequential time (this is quite realistic in view of [45]) and at costs of O(log_{2}D) with respect to parallel time (this is rather cheap). We call such a base field k hilbertian with univariate polynomial factorization at moderate costs and the corresponding algebraic complexity model is called arithmetic network (over k) with factorization gates. Observe that this model is nonuniform by the way we have introduced it. However in view of [28] and the evidence that “efficient” (rather than “effective”) versions of Hilbert’s Irreducibility Theorem must exist (see e.g. [14], [20], [58] and [62]), we may hope to obtain at least a reasonable randomization (if not uniformization) of the algorithm underlying the next statement which we pronounce without proof.

Remark 8 Suppose that k is a hilbertian field with univariate factorization at moderate costs. Suppose that there is given the same situation (with the same notations) as in Lemma 5 and 7 and make the additional assumption that the circuits β′ and β^{∗} use only parameters from the base field k. Then, subject to the following modifications, the same conclusions as in Lemma 5 and 7 are true :

• the output network in question is an arithmetic network over k with factorization gates

• the straight–line programs γ and γ^{∗} are division free circuits in k[X_{1}, …, X_{r}] (which use only parameters from k).

We finish this section showing the assertion of Remark 6 and of its toric counterpart.

Proof of Remark 6. Let assumptions and notations be as in Lemma 5 and its proof. We shall consider the k –algebras C:= k[X_{1}, …, X_{r}, u]/q(u) and

C_{ρ}:= k[X_{1}, …, X_{r}]_{ρ}[u]/(q(u))_{ρ}

and compare them to the k –algebra B:= k[X_{1}, …, X_{n}]/(f_{1}, …, f_{i}) and its localization

B_{ρ}:= k[X_{1}, …, X_{r}]_{ρ}[X_{r+1}, …, X_{n}]/(f_{1}, …, f_{i})_{ρ}.

Let us denote by ¯ the canonical k –algebra homomorphism which associates to each element in k[X_{1}, …, X_{n}] , k[X_{1}, …, X_{r}]_{ρ}[X_{r+1}, …, X_{n}] , k[X_{1}, …, X_{r}, u] or k[X_{1}, …, X_{r}]_{ρ}[u] its residue class in B, B_{ρ}, C or C_{ρ}. Observe that the condition (f_{1}, …, f_{i})_{ρ} = I_{ρ} = (q(u), ρX_{r+1} − v_{r+1}(u), …, ρX_{n} − v_{n}(u))_{ρ} induces a k –algebra isomorphism τ : B_{ρ} ⟶ C_{ρ} which leaves

k[X_{1}, …, X_{r}]_{ρ} fixed and which satisfies the condition τ(X̄_{r+1}) = \frac{v_{r+1}(ū)}{ρ}, …, τ(X̄_{n}) =

\frac{v_{n}(ū)}{ρ} . Since the polynomials f_{1}, …, f_{i} form a regular sequence in k[X_{1}, …, X_{n}] and the

variables X_{1}, …, X_{n} are in Noether position with respect to the ideal (f_{1}, …, f_{i}) , the k –algebra B is a free k[X_{1}, …, X_{r}] –module of rank δ̄ (see e.g. [26], Lemma 3.3.1). The same is true for the k –algebra C. Hence B_{ρ} and C_{ρ} are free k[X_{1}, …, X_{r}]_{ρ} –modules of rank δ̄. The polynomial is q by assumption separable with respect to the variable u. Thus we conclude that B_{ρ} and C_{ρ} are unramified k[X_{1}, …, X_{r}]_{ρ} –algebras (this fact has already been used in the proof of Lemma 5). Therefore the (ordinary) traces which map B and C onto k[X_{1}, …, X_{r}] are nonzero and the corresponding traces of B_{ρ} and C_{ρ} are nondegenerate (observe that ρ is the discriminant of the k[X_{1}, …, X_{r}] –module basis of C given by the elements ¯1, ū, …, ū^{δ̄−1} ). Since the k –algebra isomorphism τ is k[X_{1}, …, X_{r}]_{ρ} –linear it leaves the traces fixed. We denote them therefore by the same symbol “Tr” (see [42], Appendix F as reference for traces in noetherian algebras over rings). Let r < j ≤ n. As in the proof of Lemma 5 let us write v_{j} = ∑_{0≤m<δ̄}a_{m}^{(j)}u^{m}

with a_{m}^{(j)} ∈ k[X_{1}, …, X_{r}] . Observe that ρX̄_{j} = v_{j}(ū) = ∑_{0≤m<δ̄}a_{m}^{(j)}ū^{m} holds in B. For

0 ≤ m′ < δ̄ consider the polynomial

c_{m′}^{(j)} := ρT r(X̄_{j}ū^{m′}) = ∑_{0≤m<δ̄}a_{m}^{(j)}T r(ū^{m+m′})  (9)

which belongs to k[X_{1}, …, X_{r}] .

Observe that T r(X̄_{j}ū^{m′}) is also a polynomial of k[X_{1}, …, X_{r}] which satisfies by [52], Theorem 13 the degree bound degT r(X̄_{j}ū^{m′}) ≤ degW deg(X_{j}u^{m′}) = (m′+1)δ̄ ≤ δ̄^{2} . Thus c_{m′}^{(j)} is divisible in k[X_{1}, …, X_{r}] by ρ and \frac{c_{m′}^{(j)}}{ρ} satisfies the degree bound

deg \frac{c_{m′}^{(j)}}{ρ} ≤ δ̄^{2}.  (10)

In the same way we see that for any 0 ≤ m < δ̄ the trace T r(ū^{m+m′}) is an element of k[X_{1}, …, X_{r}] which satisfies the degree condition

degT r(ū^{m+m′}) ≤ 2δ̄(δ̄ − 1).  (11)

For j fixed and m verifying 0 ≤ m < δ̄ we interpret the equations (9) as an inhomogeneous δ̄×δ̄ linear equation system for the coefficient vector (a_{0}^{(j)}, …, a_{δ̄−1}^{(j)}) . The matrix

of this equation system is (T r(ū^{m+m′}))_{0≤m,m′<δ̄} whose entries belong to k[X_{1}, …, X_{r}] . The determinant of the equation system is therefore ρ, which is the discriminant of the k[X_{1}, …, X_{r}] –module basis 1, ū, …, ū^{δ̄−1} of C. The inhomogeneous vector of the equation system is obtained transposing the δ̄–tuple (c_{0}^{(j)}, …, c_{δ̄−1}^{(j)}) .

From Cramer’s rule and the degree bounds (10) and (11) we conclude therefore

dega_{m}^{(j)} ≤ 2δ̄^{3}

for any r < j ≤ n and 0 ≤ m < δ̄. Similarly we deduce from (11) the degree bound degρ ≤ 2δ̄^{3} ≤ 2δ^{3} .

The toric version of Remark 6 can be proved essentially by the same method. One has only to replace the k –algebra B by the (reduced) coordinate ring of the “toric” variety W^{∗}. Of course this coordinate ring is not a free k[X_{1}, …, X_{r}] –module anymore, but it is still a finite faithful module over k[X_{1}, …, X_{r}] , i.e. an integral extension of k[X_{1}, …, X_{r}] . This is sufficient for traces to be well defined and for [52], Theorem 13 to be true also in this new context. The rest of the proof of the toric version of Remark 6 is textually the same as in the affine case.

Let us also observe that Remark 6 can be formulated with a slightly better degree bound of δ̄^{2} + 1 , i.e. of δ^{2} + 1 in the affine case and (degq^{∗})^{2} + 1 , i.e of δ^{∗2} + 1 in the toric case. This can be easily deduced from our elementary arguments in Section 5 taking into account that all the polynomials involved are homogeneous.

4 Technical Lemmas

4.1 Squarefree Representation and Greatest Common Divisor Computation of Univariate Polynomials

Let R be an integral and factorial k –algebra with fraction field K, T a new variable, D a fixed natural number and P, Q ∈ R[T] two polynomials of formal degree D. We think that P and Q are given by their coefficient vectors each of length D. In the statements which follow now we refer to (ordinary) arithmetic networks and straight–line programs over R which receive the coefficient vectors of P and Q as inputs. Furthermore greatest common divisors (gcd’s) will always be taken with respect to the principal ideal domain K[T] although they are represented in R[T] (thus they are not unique up to units in R). The proofs of the following well-known lemmas can be found in [40].

Lemma 9 There exists a division free well parallelizable arithmetic network Γ of size O(D^{6}) which from the coefficients of P and Q computes the coefficients of a greatest common divisor (belonging to R[T] ) of these polynomials.

The greatest common divisor computed by the algorithm underlying this Lemma is a (not necessarily primitive) polynomial of R[T] which we denote by gcd(P, Q) . A similar well parallelizable ( O(s^{5}D^{6}) sequential time ) complexity bound holds for the computation of the simultaneous greatest common divisor of more than two (say s) polynomials of degree at most D belonging to R[T] .

Sometimes the second polynomial Q is given by a division free straight–line program in R[T] of length L and depth ℓ instead by its coefficients. In this case we have

Lemma 10 There exists a division free arithmetic network of size LD^{O(1)} and depth O(log_{2}(D) + ℓ) which computes the coefficients of the greatest common divisor of P and Q.

The algorithm underlying Lemma 10 uses linear algebra subroutines which deal with square matrices over R of size at most 2D − 1 .

As before this lemma can be generalized to the case of the computation of the simultaneous greatest common divisor of more than two (say s) polynomials, one of them given by its coefficient vector and having degree at most D and the others given by a division free straight–line program in R[T] of length L and depth ℓ. The outcome is then a division free arithmetic network of size (L + s)D^{O(1)} and depth O(log_{2}(D) + ℓ) which computes the coefficients of the greatest common divisor in question. Again the linear algebra subroutines deal only with square matrices of size at most 2D − 1 . Lemma 9 can be used in order to compute a separable (and hence in K[T] squarefree) polynomial P̃ ∈ R[T] which has the same zeroes as P (we call such a polynomial P̃ a separable representation of P ). If the characteristic of k (and hence of R and K) is zero this is a immediate consequence of the next lemma putting P̃ := P^{∗}. In case of positive characteristic we need a more refined analysis of the situation.

Observe that the coefficients of the derivative P′ of P are immediately obtained from the (given) coefficients of P . Therefore we have

Lemma 11 Suppose that the derivative P′ is nonzero. Then there exists a division free well parallelizable arithmetic network of size O(D^{6}) which from the coefficients of P computes the coefficients of a univariate polynomial P^{∗} ∈ R[T] and a non–zero element of the ring θ ∈ R, such that :

P^{∗} = θ \frac{P}{gcd(P, P′)}

holds.

Suppose now that the characteristic of k, K and R is positive, say p. In all our applications of the technical lemmas of this section R will be a polynomial ring over k generated by some k –linear forms in the variables X_{1}, …, X_{n}, say Y_{1}, …, Y_{r} with 0 ≤ r ≤ n (see Section 5). As one easily verifies there is no essential change to the outcome of our main algorithm in Section 5 if we replace the variables X_{1}, …, X_{n} of our input equation system f_{1}, …, f_{n} by suitable p^{k} –th powers of them with k ∈ IN not too big (recall that we suppose the ground field to be perfect and our arithmetic networks and straight–line programs to include special gates for the extraction of p –th roots in k and in k̄). Thus we may suppose without loss of generality that we are able to extract suitable p –th roots in R (and hence in K) of not too high degree ( p^{k} ≤ D will suffice). Applying now Lemma 11 iteratively (with at most log_{p}D iterations) we see that we obtain in sequential time O(D^{7}) a separable representation P̃ ∈ R[T] of the polynomial P . Taking into account that in all our applications the factor θ appearing in Lemma 11 will be monic with respect to one of its variables and using standard tricks of parallelization we get a division free and well parallelizable arithmetic network of size D^{O(1)} which from the coefficients of P computes the coefficients of a separable representation P̃ ∈ R[T] of P (see [24], 2.1. and [26] for more details about how to modify algorithms in order to achieve the assumptions which allows to compute P̃).

4.2 Correct Test Sequences and “Vermeidung von Divisionen”

The algorithms in [19], [24], [26], [40], [41] rely heavily on the use of “correct test sequences” ([13], [32], [40]) as a tool for deciding identity of polynomials given by straight–line programs. Unlike the probabilistic identity tests [15], [34], [55], [64] the choice of a suitable correct test sequence does not depend on the specific polynomials whose identity has to be checked but only on the number of variables and the size of the input circuit. The outcome are nonuniform deterministic or random algorithms of a stronger type as those proposed in [55] and [64].

Definition 12 Let F be a set of polynomials of k[X_{1}, …, X_{n}] such that 0 belongs to F. Let Q be a subset of k^{n}. Q is called a correct test sequence (or questor set) for F if for any P ∈ F the following implication holds :

P (x) = 0 for all x ∈ Q ⟹ P = 0 .

The cardinality #Q is called the length of the test sequence Q.

The existence of short correct test sequences is warranted by the following fact :

Lemma 13 Let F be the class of all polynomials of k[X_{1}, …, X_{n}] which can be evaluated by a straight–line program in k̄(X_{1}, …, X_{n}) of (nonscalar) size L and depth ℓ. Let ω := (2^{ℓ+1} − 2) (2^{ℓ} + 1)^{2} and σ := 6 (ℓL)^{2} . Then for any collection Ω of ω elements of k the set Ω^{n} ⊂ k^{n} contains at least ω^{nσ} (1 − ω^{− \frac{σ}{6}} ) correct test sequences of length σ for the class F.

If the characteristic of k is zero we can always make the standard choice Ω := {1, …, ω} ⊂ ZZ .

Lemma 13 implies that for L > 0 and ℓ > 0 there always exist correct test sequences for F having length σ which is polynomial in L, and that any random choice of σ elements in Ω^{n} leads to a correct test sequence for F with an error probability of ω^{− \frac{σ}{6}} << \frac{1}{2} . The proof of Lemma 13 can be found in [40] (see also [32]).

We shall make frequent use of a method called “Vermeidung von Divisionen” which is due to [60] and which allows to transform any straight–line program Γ (with parameters in k or k̄) which computes a polynomial and contains essential divisions into an equivalent division free one, say Γ′. If the size and the depth of Γ are L and ℓ respectively, then the size and depth of Γ′ are D^{2}L and O(ℓ) (see [40] for the proof of this precise statement).

4.3 Construction of a Primitive Element

Primitive element constructions (or “shape lemmas”) are crucial for solving zerodimensional polynomial systems symbolically (see [1], [10], [11], [12], [24], [27], [31], [40], [43], [47]). They furnish a handy description of the multiplication tensor of the finite dimensional k − algebras which arise as (typically reduced) coordinate rings of such equation systems.

Let R be an integral k –algebra with fraction field K. Let I be a zero-dimensional ideal of K[X_{1}, …, X_{n}] . We denote the radical of I by \sqrt{I}.

For any maximal ideal Q associated to I, let K(Q) be the field

K(Q):= K[X_{1}, …, X_{n}]/Q.

A linear form u = t_{1}X_{1} + ⋯ + t_{n}X_{n} ∈ R[X_{1}, …, X_{n}] is said to be a primitive element for I (or for the finite dimensional K − algebra K[X_{1}, …, X_{n}]/\sqrt{I}) if it satisfies the following two conditions :

• for any maximal ideal Q associated to I, the minimal equation (minimal polynomial) of u modulo Q has degree [K(Q) : K]_{sep} (here [K(Q) : K]_{sep} denotes the separability degree of the finite field extension K ⟶ K(Q) ).

• For any two different maximal ideals Q and Q′ associated to I, the minimal polynomials of u modulo Q and Q′ are distinct.

If the algebra K[X_{1}, …, X_{n}]/\sqrt{I} is unramified over K then a linear form u ∈ R[X_{1}, …, X_{n}] represents a primitive element for I if and only if the set {1, u, u^{2}, u^{3}, …} generates modulo \sqrt{I} the K− vector space K[X_{1}, …, X_{n}]/\sqrt{I}. We shall also apply the notion of “primitive element” to zerodimensional localizations (by a given polynomial) of generally nonzerodimensional ideals. When doing so (e.g. in Lemma 7) we have to think I as the intersection of all primary components of the given ideal which do not contain the polynomial.

For the construction of a primitive element from a given set of generators of I we follow the lines of [24] or [40].In order to explain our method we introduce new variables T_{1}, …, T_{n} and for 1 ≤ j ≤ n we consider the following domains :

R_{j} := R[T_{1}, …, T_{j−1}, T_{j+1}, …, T_{n}]
K_{j} := K(T_{1}, …, T_{j−1}, T_{j+1}, …, T_{n}),

and the following linear form in X_{1}, …, X_{j−1}, X_{j+1}, …, X_{n} :

Z_{j}:= T_{1}X_{1} + ⋯ + T_{j−1}X_{j−1} + T_{j+1}X_{j+1} + ⋯ + T_{n}X_{n}.

Furthermore we consider the following linear form U in X_{1}, …, X_{n} :

U:= T_{1}X_{1} + ⋯ + T_{n}X_{n}.

We observe that for any 1 ≤ j ≤ n the identity U = Z_{j} + T_{j}X_{j} holds. Let T be an additional variable and D a natural number. The way how we shall generate a primitive element is contained in the following statement :

Lemma 14 Let be given the following inputs :

• monic polynomials f_{1}, …, f_{n} ∈ R[T] of degree at most D such that for each 1 ≤ j ≤ n the specialization f_{j}(X_{j}) belongs to the ideal I.

• for each 1 ≤ j ≤ n a polynomial g_{j} ∈ R_{j}[T] which is monic in T and which has total degree at most D such that the specialization g_{j}(Z_{j}) belongs to the ideal K_{j} ⨂_{K} I.

We suppose further that f_{1}, …, f_{n} and g_{1}, …, g_{n} are represented by their coefficients with respect to the variable T . Moreover we assume that the coefficients of g_{1}, …, g_{n} themselves are given by a division free straight–line program in R[T_{1}, …, T_{n}] of length L and depth ℓ.

Then there exists a division free arithmetic network in R of size (nDL)^{O(1)} and depth O(log_{2}(nD) + ℓ) which computes the coefficient representation of the following items :

i) a primitive element u = λ_{1}X_{1} + ⋯ + λ_{n}X_{n} ∈ k[X_{1}, …, X_{n}] for the ideal I,

ii) a non–zero element ρ ∈ R and for each 1 ≤ j ≤ n a polynomial v_{j} ∈ R[T] such that ρX_{j} − v_{j}(u) ∈ \sqrt{I} holds,

iii) a monic polynomial q ∈ R[T] such that q(u) ∈ \sqrt{I} holds.

Moreover we have degv_{i} < degq for 1 ≤ i ≤ n. From the observations at the end of Section 4.1 we deduce that we may suppose without loss of generality that q is separable with respect to the variable T and hence squarefree. This implies that the algebra K[X_{1}, …, X_{n}]/\sqrt{I} is unramified over K and that \sqrt{I} = (q(u), ρX_{1} − v_{1}(u), …, ρX_{n} − v_{n}(u)) holds in K[X_{1}, …, X_{n}] .

Lemma 14 is contained in [40], Proposition 27 and its proof (see also [24], Sections 3.4.6 and 3.4.7).

5 The Algorithm

In this Section we describe the algorithmic procedure underlying Theorem 1, 2 and 3.

Let us fix the following notions and notations : let X_{0} be a new variable. For any non–zero polynomial p ∈ k[X_{1}, …, X_{n}] of degree D we define its homogenization ^{h}p (with respect to the variable X_{0} ) as

hp:= X_{0}^{D}p(X_{1}/X_{0}, …, X_{n}/X_{0}).

For p = 0 we put ^{h}p:= 0 . Of course ^{h}p is a homogeneous polynomial in k[X_{0}, …, X_{n}] of degree D. For any ideal I of k[X_{1}, …, X_{n}] , we define its homogenization ^{h}I as the (homogeneous) ideal in k[X_{0}, …, X_{n}] generated by the set of polynomials {^{h}f : f ∈ I}.

We maintain assumptions and notations of Section 1. In particular we suppose to be given input polynomials f_{1}, …, f_{n} ∈ k[X_{1}, …, X_{n}] of degree at most d which are encoded by a division free straight–line program of size L and depth ℓ. We suppose that f_{1}, …, f_{n} form an affine or toric complete intersection, according to the problem we are considering. Let H be a non–zero linear form of k[X_{1}, …, X_{n}] given by its coefficients. The fundamental problem we want to solve is the following : find a non–zero polynomial p (in the affine case) or a non–zero polynomial p^{∗} (in the toric case) belonging to k[T] such that p(H) vanishes on V = V (f_{1}, …, f_{n}) (in the affine case) or p^{∗}(H) vanishes on

V^{∗} = V (f_{1}, …, f_{n}) \ V ( ∏_{i=1}^{n} X_{i}) (in the toric case). This is the content of Theorem 1 and

2.

From [40] Lemma 13 we deduce that the homogeneous polynomials ^{h}f_{1} , …, ^{h}f_{n} can be evaluated by a division free straight–line program in k[X_{0}, …, X_{n}] of (nonscalar) size and depth d(d + 1)^{2}L and log_{2}d + 2ℓ respectively.

For 1 ≤ i ≤ n we denote by I_{i} := (f_{1}, …, f_{i}) the ideal generated by f_{1}, …, f_{i} in k[X_{1}, …, X_{n}] . Let us now introduce the specific notions and notations which we need in the affine case. Fix 1 ≤ i ≤ n and let J_{i} := \sqrt{^{h}I_{i}} be the radical of the homogenization of I_{i} = (f_{1}, …, f_{i}) . Thus J_{i} is a homogeneous and unmixed radical ideal of codimension i and the corresponding projective variety does not contain any irreducible component at infinity. Furthermore the homogeneous polynomial ^{h}f_{i+1} is a non–zero divisor modulo J_{i} for i < n. Let I_{i}:= (^{h}f_{i}, J_{i−1}) be the homogeneous ideal generated by ^{h}f_{i} and J_{i−1} . We observe that J_{i} is the intersection of all codimension i prime homogeneous ideals which contain I_{i} but not the form X_{0} (of course, these are associated primes of I_{i}).

Let us finally consider the specific notions and notations of the toric case. Let 1 ≤ i ≤ n. We denote by J_{i}^{∗} the intersection of all homogeneous prime ideals of codimension

i which contain ^{h}I_{i} but not the form ∏_{i=0}^{n} X_{i} (these prime ideals are again associated to

hI_{i}). By hypothesis (the family f_{1}, …, f_{n} forms a toric complete intersection) the variety

V (I_{i}) is not contained in V ( ∏_{i=1}^{n} X_{i}) and therefore J_{i}^{∗} ≠ (X_{0}, …, X_{n}) . Furthermore the

homogeneous polynomial ^{h}f_{i+1} is not a zero divisor modulo J_{i}^{∗} for i < n. Finally, as in the affine case, J_{i}^{∗} is the intersection of all codimension i homogeneous (associated)

prime ideals which contain (^{h}f_{i}, J_{i−1}^{∗}) but not the form ∏_{i=0}^{n} X_{i}.

With these notions and notations fixed we are now able to describe the principal items which are produced as intermediate results by the algorithm underlying Theorems 1, 2 and 3 and to indicate their main properties.

For the affine as well as for the toric case the algorithm proceeds in an analogous manner in n recursive steps. We give now a simultaneous account of the i –step of the algorithm both for the affine and the toric case (here 1 ≤ i ≤ n). The algorithm produces first a linear change of the variables X_{0}, …, X_{n} into new variables Y_{0}, …, Y_{n} such that the following canonical ring homomorphism becomes a generically unramified integral extension :

• in the affine case :

k[Y_{0}, …, Y_{n−i}] ⟶ k[Y_{0}, …, Y_{n}]/J_{i}

• in the toric case :

k[Y_{0}, …, Y_{n−i}] ⟶ k[Y_{0}, …, Y_{n}]/J_{i}^{∗}

Next the algorithm generates a nonzero linear form u_{i} ∈ k[Y_{n−i+1}, …, Y_{n}] and a homogeneous polynomial of k[Y_{0}, …, Y_{n−i}, T] which is monic and separable with respect to the variable T and which we denote by q_{i} in the affine and by q_{i}^{∗} in the toric case. The linear form u_{i} is a primitive element for the ideal J_{i} in the affine and for J_{i}^{∗} in the toric case having minimal polynomial q_{i} or q_{i}^{∗} respectively. Finally the algorithm produces in the affine case homogeneous polynomials ρ_{i} ∈ k[Y_{0}, …, Y_{n−i}] and v_{n−i+1}^{(i)}, …, v_{n}^{(i)} ∈ k[Y_{0}, …, Y_{n−i}, T] with ρ_{i} ≠ 0 such that in the localized ring k[Y_{0}, …, Y_{n−i}]_{ρ_{i}}[Y_{n−i+1} …, Y_{n}] the ideal generated by

q_{i}(u_{i}), ρ_{i}Y_{n−i+1} − v_{n−i+1}^{(i)}(u_{i}), …, ρ_{i}Y_{n} − v_{n}^{(i)}(u_{i})

is identical with the ideal (J_{i})_{ρ}. The polynomial ρ_{i} will be the discriminant of the (separable) polynomial q_{i} with respect to the variable T .

A similar statement is valid for the toric case if we replace q_{i} by q_{i}^{∗} and J_{i} by J_{i}^{∗}. In order to avoid accumulation of diacritic symbols in the proof we shall not use extra notation for the polynomials which play in the toric case the rôle of ρ_{i} and v_{n−i+1}^{(i)}, …, v_{n}^{(i)} . The same notation will be applied in the affine case as well as in the toric case, no ambiguity will arise from that. Thus for example ρ_{i} will be interpreted as the discriminant of q_{i} or as the discriminant of q_{i}^{∗}, following the context.

Let us also remark that the degree of v_{n−i+1}^{(i)}, …, v_{n}^{(i)} with respect to the variable T will be strictly less than the degree of q_{i} or q_{i}^{∗} respectively (this latter condition makes v_{n−i+1}^{(i)}, …, v_{n}^{(i)} unique in k(Y_{0}, …, Y_{n−i})[T] ).

Thus the k(Y_{0}, …, Y_{n−i})− algebra k(Y_{0}, …, Y_{n−i})[T]/(q_{i}) (or equivalently k(Y_{0}, …, Y_{n−i})[u_{i}]/(q_{i}(u_{i})) ) is isomorphic to k(Y_{0}, …, Y_{n−i})[Y_{n−i+1}, …, Y_{n}]/(J_{i}) in the affine case (and the isomorphism can be effectively computed). Both algebras are unramified. An analogous statement is true in the toric case.

The linear form u_{i} will be given by its coefficients with respect to the variables Y_{n−i+1}, …, Y_{n}, whereas q_{i}, q_{i}^{∗}, v_{n−i+1}^{(i)}, …, v_{n}^{(i)} will be given by their coefficients (which belong to k[Y_{0}, …, Y_{n−i}] ) with respect to the variable T . These coefficients and the polynomial ρ_{i} will be represented by a division free straight–line program in k̄[Y_{0}, …, Y_{n−i}] ). Furthermore our procedure will produce this straight–line program.

Finally let us observe that these items which appear as intermediate results of our procedure are canonical and intrinsic objects with a precise geometric meaning (on just this meaning is based the data compression contained in Lemma 5 and 7 which is fundamental for our approach). Let us consider only the affine case : to the linear change of the variables X_{0}, …, X_{n} into Y_{0}, …, Y_{n} corresponds a finite surjective morphism of affine varieties π_{i} : V (f_{1}, …, f_{i}) ⟶ A^{n−i}. The linear form u_{i} complements π_{i} to a finite morphism (π_{i}, u_{i}) which maps V (f_{1}, …, f_{i}) onto a hypersurface of A^{n−i+1} . The minimal equation of this hypersurface is just the polynomial we obtain specializing in q_{i} ∈ k[X_{0}, …, X_{n}] the variable X_{0} to 1 . With the same type of specialization we see that ρ_{i} describes the discriminant variety of the generic fiber of π_{i} and that the polynomials v_{n−i}^{(i)}, …, v_{n}^{(i)} represent a “univariate” rational parameterization of the π_{i} –fibers of the points of A^{n−i} which lie outside of this discriminant variety.

5.1 The Recursion

Keep 1 ≤ i < n and notions and notations of the last subsection fixed. We are going to describe the i + 1 –th step of our recursive main algorithm. Let δ_{i}:= degV (f_{1}, …, f_{i}) and δ_{i}^{∗} := deg^{∗}V (f_{1}, …, f_{i}) and recall that degf_{j} ≤ d holds for 1 ≤ j ≤ n. With these notations we have deg_{T} q_{i} = degq_{i} ≤ δ_{i}, deg_{T} q_{i}^{∗} = degq_{i}^{∗} ≤ δ_{i}^{∗}. In order to simplify notations we shall assume from now on that the polynomials q_{i} and q_{i}^{∗} have degree exactly δ_{i} and δ_{i}^{∗} respectively. This assumption does not restrict the generality of our arguments (compare Section 3). Let Γ_{i} be a division free straight–line program in k̄[Y_{0}, …, Y_{n−i}] which represents the coefficients of u_{i} and which evaluates ρ_{i} and the coefficients with respect to T of the polynomials v_{n−i+1}^{(i)}, …, v_{n}^{(i)} and of q_{i} in the affine, and of q_{i}^{∗} in the toric case. Denote by Λ_{i} and λ_{i} the size and depth of Γ_{i} respectively.

The core of our procedure is the following technical result :

Proposition 15 There exists an arithmetic network with parameters in k̄ of

• size i(dδ_{i}LΛ_{i})^{O(1)}

• depth O(log_{2}(dδ_{i}) + ℓ) + λ_{i}

which from Γ_{i} as input produces a linear change of variables Y_{0}, …, Y_{n} into new variables, say Y′_{0}, …, Y′_{n}, such that Y′_{0}, …, Y′_{n} are in Noether position with respect to the ideal J_{i+1} in the affine case and to J_{i+1}^{∗} in the toric case, the variables Y′_{0}, …, Y′_{n−i−1} being free.

Furthermore the network produces the coefficients of a linear form u_{i+1} in the ring k[Y′_{n−i}, …, Y′_{n}] and a division free straight–line program in k̄[Y′_{0}, …, Y′_{n−i−1}] which represents the polynomial ρ_{i+1} and the coefficients with respect to T of v_{n−i}^{(i+1)}, …, v_{n}^{(i+1)} ∈ k[Y′_{0}, …, Y′_{n−i−1}, T] and of q_{i+1} or q_{i+1}^{∗} ∈ k[Y′_{0}, …, Y′_{n−i−1}, T] , following the (affine or toric) case.

The size and depth of this straight–line program are i(L+Λ_{i})(dδ_{i})^{O(1)} and O(log_{2}(dδ_{i})+ ℓ)+λ_{i} respectively. The parameters of the arithmetic network and of the straight–line program it produces are contained in the field extension of k generated by the parameters of Γ_{i}.

We observe without proof that the algorithm underlying this procedure can be organized in such a way that it uses only linear algebra subroutines dealing with square matrices of size at most 2dδ_{i} (or 2dδ_{i}^{∗}).

We divide the i + 1 –th recursive step of our algorithm in three parts :

• recursive Noether normalization.

• recursive generation of a primitive element.

• cleaning extraneous irreducible components.

The first two parts are common for both the affine and the toric case. Only the third part distinguishes in some few technical points between the two cases.

Before giving the details of these three parts, let us recall the following procedure to compute resultants which is implicitly contained in [8] and [52] :

Lemma 16 Let J be an unmixed homogeneous radical ideal of k[X_{0}, …, X_{n}] and let us suppose that the canonical homomorphism

ϕ : k[X_{0}, …, X_{n−i}] ⟶ k[X_{0}, …, X_{n}]/J.

is an integral graded ring extension. Then, for an homogeneous polynomial g in the ring k[X_{0}, …, X_{n}] its minimal polynomial m_{g} ∈ k[X_{0}, …, X_{n−i}, T] has the form

T^{D} + a_{D−1}T^{D−1} + ⋯ + a_{0},

where D ≤ degJ and a_{j} ∈ k[X_{0}, …, X_{n−i}] is zero or a homogeneous polynomial of degree (D − j) · deg(g) .

The same conclusion remains true if we replace the minimal polynomial m_{g} by the characteristic polynomial χ_{g} of g. Moreover the minimal polynomial m_{g} is squarefree if ϕ is generically unramified and we have D ≤ degV (J) in this case.

Proof. Observe first that our assumptions on J imply that m_{g} and χ_{g} belong to k[X_{0}, …, X_{n−i}, T] .

Let J = ⋂_{j=1}^{N} Q_{j}, where the Q_{j} ’s are the homogeneous prime ideals of codimension

i associated to J. From our assumptions we obtain for 1 ≤ j ≤ N an integral ring extension :

ϕ_{j} : k[X_{0}, …, X_{n−i}] ↪ k[X_{0}, …, X_{n}]/Q_{j}

which is generically unramified if the same holds for ϕ. We consider the multiplication by the polynomial g modulo the ideal Q_{j} as a k[X_{0}, …, X_{n−i}] –linear map. In this sense we shall speak in future about “the homothety defined by multiplication by g modulo Q_{j} ”. The minimal polynomial m_{g}^{(j)} of this homothety verifies the conclusions of the lemma with respect to degrees (see [8], Remark 9 and its proof). Moreover ϕ_{j} generically unramified means that the corresponding finite field extension is separable. Therefore the minimal polynomial m_{g} is squarefree if ϕ is generically unramified. Since the minimal polynomial of the homothety defined by the multiplication by g modulo J is a product of some of the given m_{g}^{(1)}, …, m_{g}^{(N)} (without repetitions if ϕ is generically unramified), the first assertion of the lemma follows. The third one is a consequence of the fact that the polynomials m_{g}^{(1)}, …, m_{g}^{(N)} are irreducible and that J is radical. The second assertion follows from the observation that the irreducible factors of χ_{g} are the polynomials m_{g}^{(1)}, …, m_{g}^{(N)} .

Note that if g is not a zero divisor modulo J, the term a_{0} is a non–zero homogeneous polynomial of k[X_{0}, …, X_{n−i}] of degree D · deg(g) .

5.1.1 Recursive Noether Normalization.

Without loss of generality we describe just the affine case (the toric case follows simply by replacing J_{i} by J_{i}^{∗} and so on).

First we observe that ^{h}f_{i+1} is not a zero divisor modulo J_{i}. According to the notations of Lemma 16 above let m_{^{h}f_{i+1}} be the minimal polynomial of the homothety given modulo J_{i} by ^{h}f_{i+1} :

m_{^{h}f_{i+1}} = T^{D} + a_{D−1}T^{D−1} + ⋯ + a_{0}.

The coefficient a_{0} ∈ k[Y_{0}, …, Y_{n−i}] is a non-zero homogeneous polynomial of degree at most dδ_{i} and m_{^{h}f_{i+1}} is squarefree by Lemma 16.

In order to obtain a Noether normalization with respect to I_{i+1} = (^{h}f_{i+1}, J_{i}) (and hence with respect to J_{i+1} ) we have just to find a k –linear change of the variables Y_{0}, …, Y_{n−i} into new ones, say Y′_{0}, …, Y′_{n−i}, such that the (uniquely defined) polynomial A_{0}(Y′_{0}, …, Y′_{n−i}) ∈ k[Y′_{0}, …, Y′_{n−i}] = k[Y_{0}, …, Y_{n−i}] which satisfies the equality

A_{0}(Y′_{0}, …, Y′_{n−i}) = a_{0}(Y_{0}, …, Y_{n−i})

is monic in the variable Y′_{n−i}. We obtain this linear change of variables as follows :

First observe that modulo J_{i} the forms 1, u_{i}, …, u_{i}^{δ_{i}−1} represent a basis of the k(Y_{0}, …, Y_{n−i}) –vector space k(Y_{0}, …, Y_{n−i})[Y_{n−i+1}, …, Y_{n}]/(J_{i}) . By assumption the coefficients with respect to the variable T of the polynomials q_{i}, v_{n−i+1}^{(i)}, …, v_{n}^{(i)} ∈ k[Y_{0}, …, Y_{n−i}, T] as well as the polynomial ρ_{i} ∈ k[Y_{0}, …, Y_{n}] are given by the circuit Γ_{i}. This implies that we can write down directly the (homogeneous) entries of the companion matrix M_{i} ∈ k[Y_{0}, …, Y_{n−i}]^{δ_{i}×δ_{i}} of q_{i}. The matrix M_{i} describes the homothety defined by the multiplication by u_{i} in k(Y_{0}, …, Y_{n−i})[Y_{n−i+1}, …, Y_{n}]/(J_{i}) with respect to the basis given by the forms 1, u_{i}, …, u_{i}^{δ_{i}−1} . With respect to the same basis the homothety defined by the multiplication by ^{h}f_{i+1} has a matrix representation M_{^{h}f_{i+1}} which satisfies the equation :

ρ_{i}^{k}M_{^{h}f_{i+1}} = ^{h}f_{i+1}(Y_{0}, …, Y_{n−i}, v_{n−i+1}^{(i)}(M_{i}), …, v_{n}^{(i)}(M_{i}))

for some k ≤ d (in a slight abuse of notation we write ^{h}f_{i+1}(Y_{0}, …, Y_{n}) for the polynomial obtained from the original ^{h}f_{i+1}(X_{0}, …, X_{n}) by means of the change of variables from X_{0}, …, X_{n} to Y_{0}, …, Y_{n} and multiplying in this new expression submonomials in Y_{0}, …, Y_{n−i} by suitable powers of ρ_{i}). Observe that ρ_{i}^{k}M_{^{h}f_{i+1}} ∈ k[Y_{0}, …, Y_{n−i}]^{δ_{i}×δ_{i}} holds and that the entries are homogeneous polynomials. Therefore the entries of the matrix ρ_{i}^{k}M_{^{h}f_{i+1}} can be computed by an (ordinary) straight–line program in k[Y_{0}, …, Y_{n−i}] of length Lδ_{i}^{O(1)} and depth O(log_{2}δ_{i}) + ℓ from the coefficients of q_{i}, v_{n−i+1}^{(i)}, …, v_{n}^{(i)} and from ρ_{i}. This is simply done by applying the evaluation scheme for ^{h}f_{i+1} (which is given by the input) to suitable entries of the matrices v_{n−i+1}^{(i)}(M_{i}), …, v_{n}^{(i)}(M_{i}) which replace the variables Y_{n−i}, …, Y_{n}.

Next, we use Berkowitz’s well parallelizable and division free algorithm [5] in order to compute the (homogeneous) coefficients of the characteristic polynomial χ_{ρ_{i}^{k}^{h}f_{i+1}} ∈ k[Y_{0}, …, Y_{n−i}, T] of the homothety given by ρ_{i}^{k}^{h}f_{i+1} modulo J_{i}. The computation of the coefficients of χ_{ρ_{i}^{k}^{h}f_{i+1}} from the entries of ρ_{i}^{k}M_{^{h}f_{i+1}} requires an additional division free

and well parallelizable straight–line program in k[Y_{0}, …, Y_{n−i}] of size δ_{i}^{O(1)} .

Now taking into account our observations at the end of Section 4.1 we apply Lemma 11 in order to obtain the (homogeneous) coefficients with respect to T of a separable representation χ̃_{ρ_{i}^{k}^{h}f_{i+1}} ∈ k[Y_{0}, …, Y_{n−i}, T] of χ_{ρ_{i}^{k}^{h}f_{i+1}} . This separable representation is without loss of generality the minimal polynomial m_{ρ_{i}^{k}^{h}f_{i+1}} multiplied by some non– zero homogeneous θ ∈ k[Y_{0}, …, Y_{n−i}] . Observe that the coefficients of m_{ρ_{i}^{k}^{h}f_{i+1}} are homogeneous too. The computation of θ and the remaining coefficients of χ̃_{ρ_{i}^{k}^{h}f_{i+1}} = θ · m_{ρ_{i}^{k}^{h}f_{i+1}} requires one more division free and well parallelizable straight–line program

in k[Y_{0}, …, Y_{n−i}] of size δ_{i}^{O(1)} .

Putting everything together we obtain a division free straight–line program in

k̄[Y_{0}, …, Y_{n−i}]

of size Lδ_{i}^{O(1)} + Λ_{i} and depth O(log_{2}δ_{i}) + ℓ + λ_{i} which computes the homogeneous constant coefficient, say A ∈ k[Y_{0}, …, Y_{n−i}] , of θ · m_{ρ_{i}^{k}^{h}f_{i+1}} and the polynomial θ. We remark that A has degree at most (dδ_{i})^{O(1)} . By Lemma 16 this coefficient has the form A = θρ_{i}^{m}a_{0} for some m ≤ dδ_{i} and is therefore nonzero. Since m_{^{h}f_{i+1}} annihilates ^{h}f_{i+1} modulo J_{i} we conclude that a_{0} ∈ (^{h}f_{i+1}, J_{i}) holds in k[Y_{0}, …, Y_{n}] = k[X_{0}, …, X_{n}] . Since the polynomial A can be evaluated by a division free straight–line program in k̄[Y_{0}, …, Y_{n−i}] of size L(dδ_{i})^{O(1)} + Λ_{i} and depth O(log_{2}dδ_{i}) + ℓ + λ_{i}, there exists by Lemma 13 a correct test sequence of length (Lδ_{i}^{O(1)} + Λ_{i})^{3} in k^{n−i+1} for this complexity class. Because the polynomial A is nonzero we find in sequential time (L(dδ_{i})^{O(1)} + Λ_{i})^{4} and parallel time O(log_{2}dδ_{i}) + ℓ + λ_{i} a point γ = (γ_{0}, …, γ_{n−i}) ∈ k^{n−i+1} in this correct test sequence such that A(γ) ≠ 0 holds. Since A is homogeneous we may construct in the obvious way from the coordinates γ_{0}, …, γ_{n−i} of γ a linear change of the variables Y_{0}, …, Y_{n−i} into new ones, say Y′_{0}, …, Y′_{n−i}, such that the homogeneous polynomial A′ ∈ k[Y′_{0}, …, Y′_{n−i}] = k[Y_{0}, …, Y_{n−i}] given by the equation A′(Y′_{0}, …, Y′_{n−i}) = A(Y_{0}, …, Y_{n−i}) becomes monic in Y′_{n−i}. This implies that the homogeneous polynomial A_{0}(Y′_{0}, …, Y′_{n−i}):= a_{0}(Y_{0}, …, Y_{n−i}) is monic too in Y′_{n−i}.

Therefore, if we replace the variables Y_{0}, …, Y_{n} by the new variables

Y′_{0}, …, Y′_{n−i}, Y′_{n−i+1} := Y_{n−i+1}, …, Y′_{n}:= Y_{n}

we obtain a Noether normalization with respect to the ideal I_{i+1} = (^{h}f_{i+1}, J_{i}) and hence with respect to J_{i+1} .

In the next part of our algorithm we shall make use of the eliminating form a_{0} instead of the “accidental” polynomial A which comes from our specific algorithm. We consider a_{0} , A, θ and ρ_{i} as forms in the variables Y′_{0}, …, Y′_{n−i} which are related by the identity

a_{0} = \frac{A}{θρ_{i}^{k}} .

Let μ:= θρ_{i}^{k} and observe that μ is monic in Y′_{n−i}. The exponent k ≤ d is known and the forms A, θ and ρ_{i} (and hence μ = θρ_{i}^{k}) are represented in our algorithm by a division free straight–line program Σ in k̄[Y′_{0}, …, Y′_{n−i}] = k̄[Y_{0}, …, Y_{n−i}] which has size L(dδ_{i})^{O(1)} + Λ_{i} and depth O(log_{2}dδ_{i})) + ℓ + λ_{i}. The degrees of μ and A are of order (dδ_{i})^{O(1)} .

Using N:= max{degμ, degA} = (dδ_{i})^{O(1)} parallel organized calls to the procedure Σ we interpolate A and μ with respect to the variable Y′_{n−i} in N many distinct points of k and compute their coefficients with respect to the variable Y′_{n−i−1} (these coefficients are polynomials which belong to k[Y′_{0}, …, Y′_{n−i−1}] ). This can be achieved by a division free straight–line program in k̄[Y′_{0}, …, Y′_{n−i}] of size and depth (L + Λ_{i})(dδ_{i})^{O(1)} and O(log_{2}dδ_{i}) + ℓ + λ_{i} respectively. Since the square matrix with entries in k[Y′_{0}, …, Y′_{n−i}] which correspond to the division (with remainder) of A by μ in the principal ideal domain k(Y′_{0}, …, Y′_{n−i−1})[Y′_{n−i}] is unimodular and since the identity a_{0} = \frac{A}{μ} holds, we are able to compute the coefficients of the polynomial a_{0} with respect to Y′_{n−i} (and hence a_{0} itself) from the circuit Σ in sequential and parallel time (dδ_{i})^{O(1)} and O(log_{2}dδ_{i}) respectively. Therefore we may suppose that a_{0} (and its coefficients with respect to Y′_{n−i}) is given by a division free straight–line program in k̄[Y′_{0}, …, Y′_{n−i}] = k̄[Y_{0}, …, Y_{n−i}] of size and depth (L + Λ_{i})(dδ_{i})^{O(1)} and O(log_{2}dδ_{i}) + ℓ + λ_{i} respectively.

5.1.2 Recursive Generation of a Primitive Element.

The next recursive step is the computation of a primitive element u_{i+1} modulo J_{i+1} . We assume without loss of generality that the variables Y_{0}, …, Y_{n} are already in Noether position with respect to the ideal I_{i+1} = (^{h}f_{i+1}, J_{i}) (see “recursive Noether normalization”). So, we have the following integral ring extension

R := k[Y_{0}, …, Y_{n−i−1}] ↪ k[Y_{0}, …, Y_{n}]/(^{h}f_{i+1}, J_{i}) = k[Y_{0}, …, Y_{n}]/(I_{i+1})

Let us denote the fraction field of R by K (i.e. K := k(Y_{0}, …, Y_{n−i−1}) ). It is clear that I_{i+1} generates a zero dimensional ideal in K[Y_{n−i}, …, Y_{n}] . We are going to apply the method described in Section 4.3. For this purpose we introduce new variables, say T_{n−i}, …, T_{n}, and with respect to them for n − i ≤ j ≤ n the rings and fields R_{j} := R[T_{n−i}, …, T_{j−1}, T_{j+1}, …, T_{n}] and K_{j} := K(T_{n−i}, …, T_{j−1}, T_{j+1}, …, T_{n}) introduced in 4.3. For n − i ≤ j ≤ n we are going to construct polynomials h_{j} ∈ R[T] and g_{j} ∈ R_{j}[T] with the following properties :

• h_{j} ∈ R[T] is monic in T of degree at most dδ_{i} in T and the polynomial h_{j}(Y_{j}) belongs to the ideal I_{i+1}

• g_{j} ∈ R_{j}[T] is monic in T and has total degree at most dδ_{i}. The polynomial g_{j}(Z_{j}) belongs to the ideal K_{j} ⨂_{R} I_{i+1}

Our aim is to represent the coefficients of h_{j} and g_{j} with respect to T by an evaluation scheme.

With the notations and results of “recursive Noether normalization” there is already given an equation a_{0} ∈ R[Y_{n−i}] = k[Y_{0}, …, Y_{n−i}] for the integral dependence of Y_{n−i} over R modulo the ideal I_{i+1} . This polynomial a_{0} is given by a straight–line program in k̄ ⊗_{k} R[Y_{n−i}] = k̄[Y_{0}, …, Y_{n−i}] of length (L + Λ_{i})(dδ_{i})^{O(1)} and depth O(log_{2}(dδ_{i}) + ℓ) + λ_{i} and it has degree dδ_{i}. Moreover it is homogeneous with respect to the natural grading of R[Y_{n−i}] .

Fix n − i ≤ j ≤ n and consider the variable Y_{j} and the linear form Z_{j}:= T_{n−i}Y_{n−i} + ⋯+T_{j−1}Y_{j−1}+T_{j+1}Y_{j+1}+⋯+T_{n}Y_{n} ∈ R_{j}[Y_{n−i}, …, Y_{n}] in the variables Y_{n−i}, …, Y_{n} (see Section 4.3). To the homotheties given by the forms Y_{j} and Z_{j} in the δ_{i} –dimensional algebras K[Y_{n−i}, …, Y_{n}]/(J_{i}) and K_{j}[Y_{n−i}, …, Y_{n}]/(J_{i}) and to the bases of these algebras determined by 1, u_{i}, …, u_{i}^{δ_{i}−1} correspond matrices M_{Y_{j}} ∈ K^{δ_{i}×δ_{i}} and M_{Z_{j}} ∈ K_{j}^{δ_{i}×δ_{i}}. The characteristic polynomials of these matrices induce polynomials in the variables Y_{n−i}, Y_{j} and Y_{n−i}, Z_{j} respectively which have degree at most δ_{i} in these indeterminates. Since the variables Y_{0}, …, Y_{n} are in Noether position with respect to J_{i} the coefficients of these polynomials belong to R and R_{j} respectively. These coefficients are homogeneous elements of degree at most δ_{i} of their respective graded rings. Let us denote the polynomials introduced in this way as H_{j} ∈ R[Y_{n−i}, Y_{j}] and G_{j} ∈ R_{j}[Y_{n−i}, Z_{j}] . They have the following properties :

• H_{j} is monic in Y_{j} and belongs to the ideal J_{i}

• G_{j} is monic in Z_{j} and belongs to the ideal K_{j} ⊗_{R} J_{i}.

These polynomials can be computed from the results of the circuit Γ_{i} as in “recursive Noether normalization” by means of the division free and well parallelizable algorithm [5] in sequential time δ_{i}^{O(1)} . This means that their coefficients with respect to the variables Y_{j} and Z_{j} are given by division free straight–line programs in the rings k̄ ⊗_{k} R[Y_{n−i}] = k̄[Y_{0}, …, Y_{n−i}] and k̄ ⊗_{k} R_{j}[Y_{n−i}] = k̄[T_{n−i}, …, T_{j−1}, T_{j+1}, …, T_{n}, Y_{n−i}] and that these straight–line programs have length δ_{i}^{O(1)} + Λ_{i} and depth O(log_{2}δ_{i}) + λ_{i}. (Without going into details we remark here that one has to use the same type of subroutine to eliminate divisions by a certain polynomial which is monic in Y_{n−i} as we did at the end of “recursive Noether normalization” when computing a_{0} ).

For n−i ≤ j ≤ n we are now going to construct the announced polynomials h_{j} ∈ R[T] and g_{j} ∈ R_{j}[T] . For this purpose we need the coefficients with respect to Y_{n−i} of a_{0} and the coefficients with respect to Y_{n−i}, Y_{j} and Y_{n−i}, Z_{j} of H_{j} and G_{j}. This requires interpolation of these polynomials in dδ_{i} + 1 points of k which we have to substitute for the variable Y_{n−i} (recall that H_{j} and G_{j} are already given by their coefficients with respect to Y_{j} and Z_{j} respectively). For this interpolation we need (2i + 1)(dδ_{i} + 1) parallel organized calls to the whole procedure which originate a total sequential time cost of i(L + Λ_{i})(dδ_{i})^{O(1)} and a parallel time cost of O(log_{2}dδ_{i} + ℓ) + λ_{i}.

Thus the coefficients with respect to the variable Y_{n−i} of a_{0} and for n − i ≤ j ≤ n the coefficients with respect to Y_{n−i}, Y_{j} and Y_{n−i}, Z_{j} of the polynomials H_{j} and G_{j} are represented by division free straight–line programs in k̄ ⊗_{k} R = k̄[Y_{0}, …, Y_{n−i−1}] and k̄ ⊗_{k} R_{j} = k̄[T_{n−i}, …, T_{j−1}, T_{j+1}, …, T_{n}] which have length i(L + Λ_{i})(dδ_{i})^{O(1)} and depth O(log_{2}(dδ_{i}) + ℓ) + λ_{i}. Once these coefficients are given we are able to perform effectively computations in the graded k –algebras which for n − i ≤ j ≤ n are defined as follows :

• B_{j} := R[Y_{n−i}, Y_{j}]/(a_{0}, H_{j})

• C_{j} := R_{j}[Y_{n−i}, Z_{j}]/(a_{0}, G_{j}) .

Observe that B_{j} is a free R –module with basis represented by the set of monomials

{Y_{n−i}^{α}Y_{j}^{β} : 0 ≤ α < deg (a_{0}), 0 ≤ β < deg (H_{j})}

and that C_{j} is a free R_{j} –module with basis represented by the set of monomials

{Y_{n−i}^{α}Z_{j}^{β} : 0 ≤ α < deg (a_{0}), 0 ≤ β < deg (G_{j})}.

The ranks of the free modules B_{j} and C_{j} are therefore bounded by dδ_{i}^{2} . Since the coefficients of a_{0} with respect to Y_{n−i} and the coefficients of H_{j} with respect to Y_{n−i}, Y_{j} are given, we know effectively (with no extra cost) the multiplication tensor of B_{j}. In the same sense the multiplication tensor of C_{j} is available. From this data we compute the characteristic polynomial χ_{Y_{j}} ∈ R[T] of the homothety in B_{j} given by the multiplication by Y_{j} and the characteristic polynomial χ_{Z_{j}} ∈ R_{j}[T] of the homothety in C_{j} given by Z_{j}. We put h_{j} := χ_{Y_{j}} and g_{j} := χ_{Z_{j}} . One verifies immediately that h_{j} and g_{j} have the required properties (for this purpose observe that a_{0} ∈ I_{i+1} , H_{j} ∈ J_{i} ⊆ I_{i+1} and G_{j} ∈ K_{j} ⊗_{R} J_{i} ⊆ K_{j} ⊗_{R} I_{i+1} holds).

Applying Lemma 14 and the observations at the end of Section 4.1 we obtain a linear form u_{i+1} which is a primitive element for the ideal generated by I_{i+1} in K[Y_{n−i}, …, Y_{n}] , a homogeneous polynomial q ∈ R[T] and homogeneous polynomials ρ ∈ R and v_{n−i}, …, v_{n} ∈ R[T] such that the following holds : q is monic and separable in T (hence squarefree), q(u_{i+1}) belongs to the ideal \sqrt{I_{i+1}} , ρ is nonzero and for n − i ≤ j ≤ n we have ρY_{j} − v_{j}(u_{i+1}) ∈ \sqrt{I_{i+1}} . Observe that we may suppose without loss of generality that ρ is monic in one of its variables, say Y_{n−i−1} .

These items (and their homogeneous coefficients in R = k[Y_{0}, …, Y_{n−i−1}]) are represented by a division free straight– line program in k̄[Y_{0}, …, Y_{n−i−1}] whose length and depth are i(L + Λ_{i})(dδ_{i})^{O(1)} and O(log_{2}(idδ_{i}) + ℓ) + λ_{i} respectively.

5.1.3 Clearing Extraneous Irreducible Components.

In “recursive Noether normalization” we obtained a fairly explicit description of the projective variety defined by the ideal I_{i+1} and of the localization of this ideal in K[Y_{n−i} …, Y_{n}] . However this projective variety may contain irreducible components at infinity (extraneous components) or components which count in I_{i+1} (or its localization) with higher multiplicities than one.

The situation in the toric case is the same with “extraneous components at infinity” replaced by “extraneous components contained in the union of hyperplanes V ( ∏_{i=1}^{n} X_{i}) ”.

We show now how extraneous components and multiplicities which appear in a natural way when cutting by the hypersurfaces V (^{h}f_{1}), …, V (^{h}f_{n}) , can be cleared out during the process. Let us concentrate upon the affine case.

First recall that J_{i+1} is the intersection of all those homogeneous prime ideals of codimension i+1 which contain ^{h}f_{i+1} and J_{i} but do not contain X_{0} . We observe also that the (homogeneous) primes of codimension i + 1 of R[Y_{n−i}, …, Y_{n}] = k[Y_{0}, …, Y_{n}] which contain the ideal (^{h}f_{1}, …,^{h}f_{i+1}) but not X_{0} correspond to the primes in the localized ring K[Y_{n−i}, …, Y_{n}] which contain the ideal generated by I_{i+1} but not X_{0} . We are going now to determine the irreducible components at finite distance of the projective variety defined by ^{h}f_{1}, …,^{h}f_{i+1} (in other words defined by I_{i+1} ) doing computations in K[u_{i+1}] . These components characterize geometrically the ideal J_{i+1} . For 1 ≤ j ≤ i + 1 let us write F_{j} :=^{h} f_{j}(Y_{0}, …, Y_{n−i−1}, \frac{v_{n−i}(u_{i+1})}{ρ}, …, \frac{v_{n}(u_{i+1})}{ρ}) ∈ K[u_{i+1}] . Let h ∈ R[u_{i+1}] be a greatest common divisor of the polynomials F_{1}(u_{i+1}), …, F_{i+1}(u_{i+1}) and q(u_{i+1}) with respect to the principal domain K[u_{i+1}] .

Since q(u_{i+1}) is monic and separable in u_{i+1} we may suppose without loss of generality that the polynomial h is monic and separable too in u_{i+1} . Moreover we may suppose that h is homogeneous with respect to the grading of R[u_{i+1}] . The coefficients of the polynomial h with respect to the variable u_{i+1} can be computed from the coefficients of F_{1}, …, F_{i+1} , q ∈ K[u_{i+1}] by a well parallelizable and division free straight–line program of size (dδ_{i})^{O(1)} . This means that these coefficients can be computed by a division free straight–line program in k̄ ⊗_{k} R = k̄[Y_{0}, …, Y_{n−i}] of size i(L + Λ_{i})(dδ_{i})^{O(1)} and depth O(log_{2}(dδ_{i})+ℓ)+λ_{i} (here using the assumption that ρ is monic in Y_{n−i−1} , we apply again the same trick as at the end of “recursive Noether normalization” in order to eliminate division by ρ).

Observe now that the maximal ideals in K[Y_{n−i}, …, Y_{n}] which contain the polynomial h(u_{i+1}) and for n − i ≤ j ≤ n the polynomials ρY_{j} − v_{j}(u_{i+1}) , are in one to one correspondence with the codimension i + 1 prime ideals in R[Y_{n−i}, …, Y_{n}] which contain (^{h}f_{1}, …,^{h}f_{i+1}) . Moreover h(u_{i+1}) is squarefree.

Note that X_{0} ∈ k[X_{0}, …, X_{n}] = k[Y_{0}, …, Y_{n}] is a linear form in Y_{0}, …, Y_{n}. Substituting in this linear form for the variables Y_{n−i}, …, Y_{n} the polynomials

\frac{v_{n−i}(u_{i+1})}{ρ}, …, \frac{v_{n}(u_{i+1})}{ρ} ∈ K[u_{i+1}]

and clearing the denominator ρ we obtain a representation in R[u_{i+1}] of the residue class of ρX_{0} modulo the ideal generated by I_{i+1} in K[Y_{n−i}, …, Y_{n}] . Let G ∈ R[u_{i+1}] be this representation. Now we compute the greatest common divisor of G(u_{i+1}) and h(u_{i+1}) in the principal ideal domain K[u_{i+1}] . This greatest common divisor is represented by a squarefree polynomial h_{1} ∈ R[u_{i+1}] which divides h ∈ R[u_{i+1}] . Observe that h_{1} is monic in u_{i+1} and homogeneous with respect to the grading of R[u_{i+1}] . The maximal ideals of K[Y_{n−i}, …, Y_{n}] which contain h_{1}(u_{i+1}) and for n − i ≤ j ≤ n the polynomials ρY_{j} − v_{j}(u_{i+1}) , are in one to one correspondence with the codimension i + 1 prime ideals of R[Y_{n−i}, …, Y_{n}] which contain (X_{0},^{h}f_{i+1}, …,^{h}f_{n}) .

Now it is easy to see that the maximal ideals in K[Y_{n−i}, …, Y_{n}] which contain for n − i ≤ j ≤ n the polynomials ρY_{j} − v_{j}(u_{i+1}) and the homogeneous and monic in u_{i+1} polynomial

q_{i+1}(u_{i+1}):= \frac{h(u_{i+1})}{h_{1}(u_{i+1})}

correspond exactly to the codimension i + 1 prime ideals which contain the radical ideal J_{i+1} (these are also the associated primes of J_{i+1} ). Observe that q_{i+1} := q_{i+1}(T) is monic and separable with respect to the variable T . Finally the polynomials v_{n−i}^{(i+1)}, …, v_{n}^{(i+1)} are defined (and computed) as the remainders of the division in R[T] of v_{n−i}(T) …, v_{n}(T) by the monic in T polynomial q_{i+1}(T) (note that this leaves the ideal in question unchanged). In this way we obtain an explicit description of an isomorphism K[Y_{n−i}, …, Y_{n}]/(J_{i+1}) ≅ K[u_{i+1}]/(q_{i+1}(u_{i+1})) ≅ K[T]/(q_{i+1}(T)) as wanted. Since h_{1} is monic in u_{i+1} we are able to compute by the same trick as before q_{i+1} by a division free straight–line program. Because q_{i+1} is again monic in T the same argument applies to v_{n−i}^{(i+1)}, …, v_{n}^{(i+1)} . Finally we observe that ρ and the coefficients with respect to the variable T of q(T) and v_{n−i}^{(i+1)}(T), …, v_{n}^{(i+1)}(T) can be computed by a division free straight–line program Γ in k̄[Y_{0}, …, Y_{n−i−1}] of size i(L + Λ_{i})(dδ_{i})^{O(1)} and depth O(log_{2}(dδ_{i}) + ℓ) + λ_{i}. Since q_{i+1} is separable and monic with respect to T its discriminant (which we denote by ρ_{i+1} ) is nonzero and belongs to R = k[Y_{0}, …, Y_{n−i−1}] . Since it is possible to compute ρ_{i+1} by a well parallelizable straight–line program in R of size (dδ_{i})^{O(1)} we may suppose without loss of generality that the circuit Γ represents also the polynomial ρ_{i+1} .

We conclude this subsection with the remark that the toric case can be treated in exactly the same way replacing at the end of the construction for the affine case the linear form X_{0} by the homogeneous polynomial ∏_{i=0}^{n} X_{i}.

5.2 Proof of Theorems 1, 2 and 3

In this subsection we deduce from Lemma 5 and 7 and from Proposition 15 first Theorem 3 and then Theorem 1 and 2.

Proof of Theorem 3. Let assumptions and notations be the same as in the statement of Theorem 3 and as at the beginning of this section. The algorithm underlying the proof proceeds in n recursive steps.

Let us now show Theorem 3 (i) which deals with the affine case. In the first step of our algorithm we apply Proposition 15 just to the input straight–line program β and the input polynomials f_{1}, …, f_{n} in the following sense : we put formally i = 0 and assume Γ_{0} to be the empty circuit.

Suppose now 1 ≤ i < n and let us consider the (i + 1) –th step of our procedure. Let be given an arithmetic network N_{i} with parameters in k̄ which produces the input for the (i + 1) –th recursion step of our procedure, namely a division free straight–line program β_{i} in k̄[Y_{0}, …, Y_{n−i}] which evaluates ρ_{i} and the coefficients with respect to T of the polynomials q_{i}, v_{n−i+1}^{(i)}, …, v_{n}^{(i)} . Suppose also that β_{i} contains the information about the coefficients of the linear form u_{i} which for example may be stored as parameters of β_{i}. Assume inductively that the polynomial q_{i} is monic and separable with respect to the variable T and that ρ_{i} is its discriminant. Let L_{i} and ℓ_{i} be the nonscalar size and depth of N_{i} respectively. Note that the size and depth of the circuit β_{i} do not exceed L_{i} and ℓ_{i} respectively.

To the circuits β and β_{i}, the polynomials f_{1}, …, f_{i}, ρ_{i}, q_{i}, v_{n−i+1}^{(i)}, …, v_{n}^{(i)} and the k –linear form u_{i} we apply the compression algorithm underlying Lemma 5. We obtain a new division free straight–line program Γ_{i} in k̄[Y_{0}, …, Y_{n−i}] which represents the coefficients of u_{i}, the polynomial ρ_{i} and the coefficients with respect to T of q_{i} and v_{n−i+1}^{(i)}, …, v_{n}^{(i)} . From Lemma 5 we deduce that the circuit Γ_{i} has size and depth O((i^{5} + L)δ_{i}^{11}) and O((log_{2}i + ℓ)log_{2}δ_{i}) .

We apply now to the circuit β and Γ_{i}, the polynomials

f_{1}, …, f_{i+1}, ρ_{i}, q_{i}, v_{n−i+1}^{(i)}, …, v_{n}^{(i)}

and the k –linear form u_{i} the elimination procedure underlying Proposition 15. We obtain a linear change of the variables Y_{0}, …, Y_{n} of the i –th step into new variables Y′_{0}, …, Y′_{n} such that Y′_{0}, …, Y′_{n} are in Noether position with respect to the ideal J_{i+1} , the variables Y′_{0}, …, Y′_{n−i−1} being free. Moreover we obtain a new k –linear form u_{i+1} and new polynomials ρ_{i+1} ∈ k[Y′_{0}, …, Y′_{n−i−1}] and q_{i+1} , v_{n−i}^{(i+1)}, …, v_{n}^{(i+1)} ∈ k[Y′_{0}, …, Y′_{n−i−1}, T] . All these items are represented by a division free straight–line program β_{i+1} in k[Y′_{0}, …, …, Y′_{n−i−1}] which is generated by an arithmetic network N_{i+1} with parameters in k̄. From Proposition 15 we deduce that the size and depth of β_{i+1} are O(i(L + (i^{5} + L)δ_{i}^{11})(dδ_{i})^{O(1)}) = i^{6}L(dδ_{i})^{O(1)} and O((log_{2}(dδ_{i}) + ℓ) + (log_{2}i + ℓ)log_{2}δ_{i}) = O((log_{2}(id) + ℓ)log_{2}δ_{i}) .

Similarly the size L_{i+1} and the depth ℓ_{i+1} of N_{i} are (iLdδ_{i})^{O(1)}+L_{i} and O((log_{2}(id)+ ℓ)log_{2}δ_{i}) + ℓ_{i}.

Finally we obtain for i:= n − 1 the output of the algorithm underlying Theorem 3 (i) . This output consists in the coefficients of a nonzero linear form u ∈ k[X_{1}, …, X_{n}] and of one–variate polynomials q, v_{1}, …, v_{n} ∈ k[u] such that the following holds :

• degq = δ_{n}

• max{degv_{1}, …, degv_{n}} < δ_{n}

• (f_{1}, …, f_{n}) = (q, X_{1} − v_{1}, …, , X_{n} − v_{n}).

The output is represented by the arithmetic network N_{n} whose parameters belong to k̄ and whose size and depth are (nLdδ)^{O(1)} and O(n(log_{2}(nd) + ℓ)log_{2}δ) respectively.

The proof of Theorem 3 (ii) which deals with the toric case is completely analogous. One has just to replace in it the application of Lemma 7 by the application of Lemma 5 in the same sense. In order to avoid repetitive arguments we omit this proof.

From Theorem 3 (i) and (ii) we deduce now easily Theorem 1 and 2.

Proof of Theorem 1 and 2. Let us first concentrate upon the affine case, namely Theorem 1.

Let assumptions and notations be the same as in the statement of Theorem 1. Applying Theorem 3 (i) to this situation we obtain an arithmetic network N with parameters in k̄ which computes the coefficients of a k –linear form u and of polynomials q, v_{1}, …, v_{n} ∈ k[T] satisfying the following conditions :

(*) degq = δ_{n} and max{degv_{i} ; 1 ≤ i ≤ n} < δ_{n}

(**) (f_{1}, …, f_{n}) = (q(u), X_{1} − v_{1}(u), …, X_{n} − v_{n}(u))

The network N has size (ndδL)^{O(1)} and depth O(n(log_{2}(nd) + ℓ)log_{2}δ) .

Let H = α_{1}X_{1} + ⋯ + α_{n}X_{n} be the representation of the nonzero linear form H ∈ k[X_{1}, …, X_{n}] by its coefficients α_{1}, …, α_{n} ∈ k and let p be the characteristic (or minimal) polynomial of the k –linear endomorphism of k[T]/(q) induced by the polynomial α_{1}v_{1} + ⋯ + α_{n}v_{n} ∈ k[T] . We can compute the coefficients of p from the data α_{1}, …, α_{n}, q and v_{1}, …, v_{n} by a well parallelizable algorithm in sequential time δ_{n}^{O(1)} . Thus we may suppose without loss of generality that N computes also the coefficients of the monic polynomial p. The condition (**) above expresses an isomorphism between the k –algebras k[T]/(q) and k[X_{1}, …, X_{n}]/(f_{1}, …, f_{n}) . From the particular form of this isomorphism we infer that p is also the characteristic (or minimal) polynomial of the k –linear endomorphism of k[X_{1}, …, X_{n}]/(f_{1}, …, f_{n}) induced by the multiplication by H. This implies that p(H) ∈ (f_{1}, …, f_{n}) holds, whence the conclusion of Theorem 1.

Theorem 2 is deduced from Theorem 3 (ii) in almost textually the same manner.

Lemma 5 and Proposition 15 can be combined in the same way as in the proof of Theorem 3 (i) in order to obtain the following elimination result for reduced complete intersection ideals of positive dimension :

Proposition 17 Let f_{1}, …, f_{s} be polynomials which belong to k[X_{1}, …, X_{n}] . Suppose that f_{1}, …, f_{s} form a regular sequence in k[X_{1}, …, X_{n}] . For any 1 ≤ j ≤ s let δ_{j} := degV (f_{1}, …, f_{j}) be the geometric degree of the affine variety defined by the ideal (f_{1}, …, f_{j}) which we assume to be radical. Write r := n − s, δ := max{δ_{j} ; 1 ≤ j ≤ s} and d := max{degf_{j} ; 1 ≤ j ≤ s}. Suppose that the polynomials f_{1}, …, f_{s} are given by a division free straight–line program β in k[X_{1}, …, X_{n}] of length L and depth ℓ. Then there exists an arithmetic network with parameters in k̄ which has size (sdδL)^{O(1)} and depth O(s(log_{2}(sd) + ℓ)log_{2}δ) and which produces from the circuit β as input, the following items :

• a nonsingular matrix of k^{n×n} which is given by its coefficients and which transforms the variables X_{1}, …, X_{n} into new ones, say Y_{1}, …, Y_{n},

• a nonzero k –linear form u ∈ k[Y_{r+1}, …, Y_{n}] ,

• a division free straight–line program γ in k̄[Y_{1}, …, Y_{r}] which represents a nonzero polynomial ρ ∈ k[Y_{1}, …, Y_{r}] and the coefficients with respect to the variable u of certain polynomials q, v_{1}, …, v_{n} ∈ k[Y_{1}, …, Y_{r}, u] .

These items have the following properties :

i) the new variables Y_{1}, …, Y_{n} are in Noether position with respect to the ideal (f_{1}, …, f_{s}) , the variables Y_{1}, …, Y_{r} being free,

ii) the polynomial q is monic and separable in u and ρ is its discriminant,

iii) in the localized ring k[X_{1}, …, X_{n}]_{ρ} the following ideals are identical

(f_{1}, …, f_{s})_{ρ} = (q, ρX_{1} − v_{1}, …, ρX_{n} − v_{n})_{ρ},

iv) the polynomials q, ρ and v_{1}, …, v_{n} satisfy the degree conditions degq = deg_{u}q = δ_{s}, degρ ≤ δ_{s}^{3} , max{deg_{u}v_{j} ; 1 ≤ j ≤ n} < δ_{s} and max{degv_{j} ; 1 ≤ j ≤ n} ≤ 2δ_{s}^{3} ,

v) the length of the straight–line program γ is O((s^{5} +L)δ_{s}^{11}) = (sLδ)^{O(1)} and its depth is O((log_{2}s + ℓ)log_{2}δ_{s}) = O((log_{2}s + ℓ)log_{2}δ) .

We omit the proof of this proposition which is essentially the same as the proof of Theorem 3 (i) .

Of course Proposition 17 admits also a toric version with almost the same proof as Theorem 3 (ii) . We are going now to formulate a slightly more general statement in which

the rôle of the form ∏_{i=1}^{n} X_{i} is played by an arbitrary nonzero polynomial g ∈ k[X_{1}, …, X_{n}] .

We think this statement is interesting by its own because it says that our algorithms are able to “avoid” undesired points which are contained in a previously given hypersurface V (g) .

Let be given nonzero polynomials f_{1}, …, f_{s}, g ∈ k[X_{1}, …, X_{n}] with s ≤ n. We say that f_{1}, …, f_{s} form a secant family (“suite sécante”) which avoids the hypersurface V (g) if for any 1 ≤ j ≤ s the localization V (f_{1}, …, f_{j})_{g} is not empty and if for any irreducible component C of V (f_{1}, …, f_{j}) the following implication holds :

if C is not contained in the hypersurface V (g) then dimC = n − j.

Let 1 ≤ j ≤ s. We say that an irreducible component C of V (f_{1}, …, f_{j}) avoids the hypersurface V (g) if C is not contained in V (g) . The union of all irreducible components of V (f_{1}, …, f_{j}) which avoid the hypersurface V (g) is called the part of the affine variety V (f_{1}, …, f_{j}) which avoids the hypersurface V (g) and we denote this part by V′(f_{1}, …, f_{j}) . We write deg′V (f_{1}, …, f_{j}) for its geometric degree. Thus V′(f_{1}, …, f_{j}) is the Zariski closure of the locally closed subset V (f_{1}, …, f_{j})_{g} of A^{n} and we have deg′V (f_{1}, …, f_{j}) = degV′(f_{1}, …, f_{j}) . Moreover if f_{1}, …, f_{s} form a secant family which avoids the hypersurface V (g) then deg′V (f_{1}, …, f_{j}) > 0 holds for any 1 ≤ j ≤ s.

With these notions and notations we are now able to formulate our statement which generalizes Theorem 3 (ii) to positive dimension :

Proposition 18 Let f_{1}, …, f_{s} and g be polynomials of k[X_{1}, …, X_{n}] such that f_{1}, …, f_{s} form a secant family which avoids the hypersurface V (g) . For any 1 ≤ j ≤ s let δ′_{j} := deg′V (f_{1}, …, f_{j}) be the degree of the part of the affine variety V (f_{1}, …, f_{j}) which avoids the hypersurface V (g) and suppose that the localized ideal (f_{1}, …, f_{j})_{g} is radical. Write r := n − s, δ′ := max{δ′_{j} ; 1 ≤ j ≤ s} and d := max{degf_{j} ; 1 ≤ j ≤ s}. Assume that the polynomials f_{1}, …, f_{s} and g are given by a division free straight–line program β in k[X_{1}, …, X_{n}] of length L and depth ℓ. Then there exists an arithmetic network with parameters in k̄ which has size (sdδ′L)^{O(1)} and depth O(s(logsd + ℓ)log_{2}δ′) and which produces from the circuit β as input, the following items :

• a nonsingular matrix of k^{n×n} which is given by its coefficients and which transforms the variables X_{1}, …, X_{n} into new ones, say Y_{1}, …, Y_{n},

• a nonzero k –linear form u ∈ k[Y_{r+1}, …, Y_{n}] ,

• a division free straight–line program γ in k̄[Y_{1}, …, Y_{r}, u] which represents a nonzero polynomial ρ ∈ k[Y_{1}, …, Y_{r}] and the coefficients with respect to u of certain polynomials q, v_{1}, …, v_{n} ∈ k[Y_{1}, …, Y_{r}, u] .

These items have the following properties :

i) the new variables Y_{1}, …, Y_{n} are in Noether position with respect to V′(f_{1}, …, f_{s}) , the variables Y_{1}, …, Y_{r} being free,

ii) the polynomial q is monic and separable in u and ρ is its discriminant,

iii) in the localized ring k[X_{1}, …, X_{n}]_{ρ·g} the following ideals are identical

(f_{1}, …, f_{s})_{ρ·g} = (q, ρX_{1} − v_{1}, …, ρX_{n} − v_{n})_{ρ·g},

iv) the polynomials q, ρ and v_{1}, …, v_{n} satisfy the degree conditions degq = deg_{u}q = δ′_{s}, degρ ≤ 2δ_{s}^{′3} , max{deg_{u}v_{j} ; 1 ≤ j ≤ n} < δ′_{s} and max{degv_{j} ; 1 ≤ j ≤ n} ≤ 2δ_{s}^{′3}

v) the length of the straight–line program γ is O((s^{5} + L)δ_{s}^{′11}) = (sLδ′)^{O(1)} and its depth is O((log_{2}s + ℓ)log_{2}δ′_{s}) = O((log_{2}s + ℓ)log_{2}δ′) .

We omit the proof of this proposition which essentially the same as the proof of Theorem 3 (ii) with the form ∏_{i=1}^{n} X_{i} replaced by the polynomial g.

6 Division Theorems

In this section we explain how Proposition 17 can be applied in order to obtain refined complexity and degree bounds in the division theorems of [19], [40] and [52] (see also [26] and [41]). Let us first state our results.

Theorem 19 Let f_{1}, …, f_{s} and g be polynomials of k[X_{1}, …, X_{n}] such that f_{1}, …, f_{s} form a regular sequence and g belongs to the ideal (f_{1}, …, f_{s}) . For 1 ≤ j ≤ n denote by δ_{j} := degV (f_{1}, …, f_{j}) the geometric degree of the affine variety defined by the ideal (f_{1}, …, f_{j}) which we suppose to be radical. Write δ := max{δ_{j} ; 1 ≤ j ≤ s − 1} and d:= max{degf_{j} ; 1 ≤ j ≤ n}. Assume that the polynomials f_{1}, …, f_{s} and g are given by a division free straight–line program β in k[X_{1}, …, X_{n}] of length L and depth ℓ. Then there exists an arithmetic network with parameters in k̄ which has size (sdδL)^{O(1)} and depth O(s(log_{2}sd + ℓ)log_{2}δ) and which produces from the circuit β as input a division free straight–line program γ in k̄[X_{1}, …, X_{n}] such that γ represents certain polynomials p_{1}, …, p_{s} ∈ k[X_{1}, …, X_{n}] with the following properties :

i) g = p_{1}f_{1} + ⋯ + p_{s}f_{s}

ii) max{degp_{j} ; 1 ≤ j ≤ s} ≤ (2s^{2}d + max{d, degg})δ

Moreover the circuit γ has size (degg)^{2}(sdδL)^{O(1)} and depth O(s(log_{2}sd + ℓ)log_{2}δ) . Let us remark that allowing divisions in the circuit γ we may diminuish its size to (sdδL)^{O(1)} .

Let f_{1}, …, f_{s} be nonconstant polynomials representing an equation system of k[X_{1}, …, X_{n}] . Define polynomials g_{1}, …, g_{n} ∈ k[X_{1}, …, X_{n}] as follows : if the characteristic of k is zero, choose g_{1}, …, g_{n} as generic linear combinations of the polynomials f_{1}, …, f_{s} and if the characteristic is positive, choose g_{1}, …, g_{n} as generic linear combinations of the set of polynomials {X_{i}f_{j} ; 1 ≤ i ≤ n , 1 ≤ j ≤ s}. For 1 ≤ i ≤ n denote by δ_{i}:= degV (g_{1}, …, g_{n}) the geometric degree of the affine variety V (g_{1}, …, g_{i}) . Then we call δ:= max{δ_{i} ; 1 ≤ i ≤ n} the generic geometric degree of the equation system given by f_{1}, …, f_{s}. Observe that the generic geometric degree of the system f_{1}, …, f_{s} is positive even if f_{1}, …, f_{s} generate the trivial ideal.

With these notion we can state our next result, namely Theorem 20 (effective Nullstellensatz) Let f_{1}, …, f_{s} be polynomials of the ring k[X_{1}, …, X_{n}] which generate the trivial ideal. Let δ be the generic geometric degree of the equation system f_{1}, …, f_{s} and let d := max{degf_{j} ; 1 ≤ j ≤ s}. Suppose that the polynomials f_{1}, …, f_{s} are given by a division free straight–line program β in k[X_{1}, …, X_{n}] of length L and depth ℓ. Then there exists an arithmetic network with parameters in k̄ which has size (ndδL)^{O(1)} and depth O(n(lognd + ℓ)log_{2}δ) and which produces from the circuit β as input a division free straight–line program γ in k̄[X_{1}, …, X_{n}] such that γ represent certain polynomials p_{1}, …, p_{s} ∈ k[X_{1}, …, X_{n}] which have the following properties :

i) 1 = p_{1}f_{1} + ⋯ + p_{s}f_{s}

ii) max{degp_{j} ; 1 ≤ j ≤ s} ≤ 3n^{2}dδ

Moreover the circuit γ has size (ndδL)^{O(1)} and depth O(n(lognd + ℓ)log_{2}δ) .

If we replace in the statement of Theorem 19 and 20 the parameter δ by the Bézout estimations d^{s} and d^{n} respectively we obtain the worst case complexity bounds of [19], Théorème 5.1 and 5.2, [40] Theorem 1 and 2 and [52], Lemma 15 and 16, Theorem 19 and 24.

Let us now make some comments first on the degree and then on the complexity bounds of Theorem 19 and 20 and their proofs. The degree bounds in Theorem 19 (ii) and 20 (ii) are noteworth by their own. They are due to the paper [52] from which they follow immediately by performing the following modification in the proof of [52], Lemma 15 and 16 : every time when the Bézout inequality ([29], Theorem 1) is applied in order to produce a degree bound of d^{j}, this bound is replaced by the number δ_{j}, where 1 ≤ j ≤ s or 1 ≤ j ≤ n, following the context (see [53]).

We are now going to explain how the complexity bounds of Theorem 19 (i) and 20 (i) follow from Proposition 17. In order to make explanations easier we refer only to proofs in paper [19] and to the sequential complexity model (compare with [40] for considerations of nonscalar parallel complexity). We obtain a proof of Theorem 19 (i) and 20 (i) almost directly from the proof of [19] Théorème 5.1. and 5.2. if we perform systematically the following modifications in the paper [19] : Proposition 2.3.1. and Proposition principale 2.4.1. are replaced everywhere they are used in [19] by our Proposition 17. Moreover in all degree estimations, when the application of the Bézout inequality produces a d^{j} bound (for 1 ≤ j ≤ s or 1 ≤ j ≤ n), this bound is replaced by δ_{j}. With these modifications the proof of our Theorem 19 (i) and 20 (i) is almost textually the same as that of [19], Théorème 5.1 and 5.2. There is only one point where caution is necessary : the application of duality techniques in [19] is based on the simple minded decomposition formula for duality (3) in Section 3.2 of the same paper. The size of this decomposition may happen to be too big for our purpose here. In order to remedy this problem we have to use a different view of duality which is close to [52] and [53]. This will be contained in a forthcoming paper where complete and self contained proofs of Theorem 19 and 20 will be given.

For getting simultaneously with the complexity bounds also the degree estimations in Theorem 19 and 20 one has to adapt the algorithm underlying the proof of Theorem 19 (i) and 20 (i) to the particular constructions in [52] and [53].

7 Conclusions

This final section is devoted to the announcement of further complexity results which can be obtained by our method. We hope that these results, which are intermediary products of work still in progress, shed light on the possibilities and limitations of our approach.

First let us turn back to our discussion at the end of Section 3.

Remark 8 and Proposition 15 imply that our main results, namely Theorem 1, 2, 3, 19, 20 and Proposition 17, 18 remain true if we replace in their conclusions “arithmetic network with parameters in k̄ ” by “arithmetic network over k with factorization gates” and “straight–line program in k̄[X_{1}, …, X_{n}] ” by “straight–line program in k[X_{1}, …, X_{n}] ”. Parallel to this observation we may ask what happens to our algorithms when we try to transfer them to the bit complexity model (here we suppose that k is 0 Q or a finitely generated transcendental extension of 0 Q ). We announce here that our procedures allow perfect a modularization modulo suitably (randomly) chosen primes of not too big height. This implies that a suitably randomized version of our main complexity results remain valid in the bit model if we take into account the (bit) size of the rational parameters which appear in the input circuit β. Finally let us state just one application of our method to an elimination problem in semialgebraic geometry.

Let k be an ordered hilbertian field with factorization at moderate costs and let K be a real closure of k. Let k̄:= K̄:= K(i) with i^{2} = −1 be the corresponding algebraic closure of k and K. We consider the affine space A^{n}:= A^{n}(k̄) equipped with the Zariski topology whose closed sets are the k –definable algebraic subsets of k̄^{n}. Let W ⊆ A^{n} be a closed subset and let W = C_{1} ∪ ⋯ ∪ C_{s} be its decomposition in irreducible components with respect to this topology. Thus W and C_{1}, …, C_{s} are k− definable algebraic subsets of k̄^{n}. Let 1 ≤ j ≤ s and consider the irreducible component C_{j} of W . We call C_{j} a real component of W if the real variety C_{j} ∩ K^{n} contains a smooth point of C_{j}. Let

I = {j ∈ IN : 1 ≤ j ≤ s, where C_{j} is a real component of W }.

We call the affine variety W′′:= ⋃_{j∈I} C_{j} the real part of W and we define the real degree

of W as deg′′W:= degW′′ = ∑_{j∈I} degC_{j}. Observe that deg′′W = 0 holds if and only if the

real part W′′ of W is empty.

Let f be a nonconstant and squarefree polynomial of k[X_{1}, …, X_{n}] which defines a hypersurface W := V (f) of A^{n}. Let V := W ∩ K^{n} the real variety given by the polynomial f . Suppose that V is nonempty, bounded and smooth with regular equation f . Assume that the variables X_{1}, …, X_{n} are in generic position with respect to V and consider for any 0 ≤ i < n the polar variety of W corresponding to the linear space defined by the equations X_{1}, …, X_{i}. Denote by W_{i} this polar variety and consider the real variety V_{i} := W_{i} ∩ K^{n}. With these notions and notations it is not too difficult to deduce from the Weak Transversality Theorem (à la Sard–Thom) that for any 0 ≤ i < n the following facts are true :

• W_{0} = W ,

• W_{i} is a nonempty equidimensional affine subvariety of A^{n} which is smooth in all of its points which are smooth with respect to W , • the real part W′′_{i} of the polar variety W_{i} coincides with the Zariski closure of V_{i} in

A^{n},

• V_{i} is defined by the equations f, \frac{∂f}{∂X_{1}} , …, \frac{∂f}{∂X_{i}} ,

• for any i < j ≤ n the ideal

(f, \frac{∂f}{∂X_{1}} , …, \frac{∂f}{∂X_{i}} )_{\frac{∂f}{∂X_{j}}}

is radical.

Let us write δ′′_{i} := deg′′W_{i} for 0 ≤ i < n and δ′′ := max{δ′′_{i} ; 0 ≤ i < n} and d:= degf .

With these notations and assumptions we have the following complexity result :

Theorem 21 (in collaboration with B. Bank and R. Mandel) Suppose that the equation f is given by a division free straight–line program β in k[X_{1}, …, X_{n}] of length L and depth ℓ. Then there exists an arithmetic network in k with factorization gates which has size (ndδ′′L)^{O(1)} and depth O(n(log_{2}(nd) + ℓ)log_{2}δ′′) which from the circuit β as input produces the coefficients of a nonzero linear form u ∈ k[X_{1}, …, X_{n}] and of certain polynomials q, v_{1}, …, v_{n} ∈ k[u] . These polynomials have the following properties :

i) q is monic and squarefree and has degree δ′′_{n}. Moreover v_{1}, …, v_{n} satisfy the degree bound max{degv_{j} ; 1 ≤ j < n} < δ′′_{n}

ii) For each semialgebraically connected component C of V there exists a point ξ ∈ C and a field element τ ∈ K such that q(τ) = 0 and ξ = (v_{1}(τ), …, v_{n}(τ)) holds.

We observe here that the network computes only points ξ which are critical points of the projection map of V into K induced by the coordinate X_{n}.

Acknowledgments : We thank the unknown referee for his inspiring comments and his suggestions to improve the presentation of this paper.

References

[1] M.E. Alonso, E. Becker, M.-F. Roy, T. Wörmann : Zeroes, multiplicities and idempotents for zerodimensional systems, to appear in Proc. MEGA’94, Birkhäuser Progress in Mathematics.

[2] W. Baur, V. Strassen : The complexity of partial derivatives, Theoret. Comput. Sci. 22 (1982) 317-330.

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

[4] C. Berenstein and A. Yger : Une formule de Jacobi et ses conséquences, Ann Sci. E.N.S., 4^{ieme} série, 24 (1991) 363-377.

[5] S.J. Berkowitz : On computing the determinant in small parallel time using a small number of processors, Inf. Proc. Letters 18 (1984) 147–150.

[6] J. Briançon : Sur le degré des relations entre polynômes, C. R. Acad. Sci. Paris, Série I Math. 297 (1982) 553-556.

[7] D. W. Brownawell : Bounds for the degree in the Nullstellensatz, Annals of Math. 126 (1987) 577-591.

[8] L.Caniglia, A.Galligo and J.Heintz : Some new effectivity bounds in computational geometry, Proc. AAECC–6, T. Mora, ed., Springer LNCS 357(1989) 131–152.

[9] L. Caniglia, A. Galligo and J. Heintz : Borne simplement exponentielle pour les degrés dans le théorème des zéros sur un corps de caractéristique quelconque, C.R. Acad. Sci. Paris, Série I, Math. 307 (1988) 255-258.

[10] J. Canny : Some algebraic and geometric problems in PSPACE, Proc. 20-th Ann. ACM Symp. Theory of Computing (1988) 460-467.

[11] A.L. Chistov : Polynomial –time computation of the dimension of components of algebraic varieties in zero–characteristic, Preprint Université Paris Val de Marne.

[12] A.L. Chistov, D.Yu. Grigor’ev : Subexponential time solving systems of algebraic equations, LOMI Preprints E-9-83, E-10-83, Leningrad (1983).

[13] F. Cucker, M. Karpinski, P. Koiran, T. Lickteig, K. Werther : On real Turing machines that toss coins, manuscript University Bonn (1995)

[14] P. Dèbes : On the irreducibility of the polynomials P(t^{m},Y), Journal of Number Theory, vol. 42 (2) (1992) 141–157

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

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

[17] T.W. Dubé : A combinatorial proof of effective Nullstellensatz, J. Symb. Comp. 15 (1993) 277–296.

[18] D. Duval : Évaluation Dynamique et clôture algébrique en Axiom, Journal of Pure and Applied Algebra 99 (1995) 267–295.

[19] N. Fitchas, M. Giusti and F. Smietanski : Sur la complexité du théorème des zéros, in Approximation and Optimization in the Caribbean II, Proceedings of the Second International Conference on Approximation and Optimization, La Habana, 1993, M. Florenzano et al., eds., Approximation and Optimization, Peter Lang Verlag, Frankfurt (1995) 274–329.

[20] M. Fried : On the Sprindžuk–Weissauer approach to universal Hilbert subsets, Israel J. Math. 51 (4) (1985) 347–363.

[21] W. Fulton : Intersection Theory, Ergebnisse der Mathematik, 3 Folge Band 2, Springer Verlag (1984).

[22] C.B. García and W. I. Zangwill : Pathways to solutions, fixed points and equilibria, Prentice-Hall, N.J. (1981)

[23] J.von zur Gathen : Parallel arithmetic computations : a survey, Proc. 13-th Conf. MFCS. Springer LNCS 233(1986) 93–112.

[24] 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 Computational Algebraic Geometry and Commutative Algebra, Proceedings of the Cortona Conference on Computational Algebraic Geometry and Commutative Algebra, D. Eisenbud and L. Robbiano, eds., Symposia Matematica, vol. XXXIV, Istituto Nazionale di Alta Matematica, Cambridge University Press (1993).

[25] M. Giusti, J. Heintz, J.E. Morais, L.M. Pardo : When polynomial equation systems can be “solved” fast? in Proc. 11th International Symposium Applied Algebra, Algebraic Algorithms and Error– Correcting Codes, AAECC–11, Paris 1995, G. Cohen, M.Giusti and T. Mora, eds., Springer LNCS 948 (1995) 205–231.

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

[27] L. González Vega, G. Trujillo : Using symmetric functions to describe the solution of a zero– dimensional ideal, in Proc. 11th International Symposium Applied Algebra, Algebraic Algorithms and Error–Correcting Codes, AAECC-11, Paris 1995, G. Cohen, M. Giusti and T. Mora, eds., Springer LNCS 948 (1995) 232–247.

[28] K. Haegele, J.L. Montaña : Polynomial random test for the equivalence problem of integers given by arithmetic circuits. Manuscript Universidad de Cantabria (1995).

[29] J. Heintz : Fast quantifier elimination over algebraically closed fields, Theoret. Comp. Sci. 24 (1983) 239-277.

[30] J. Heintz : On the computational complexity of polynomials and bilinear mappings, in Proc. 5th International Conference Applied Algebra, Algebraic Algorithms and Error–Correcting Codes AAECC–5, Menorca 1987, L. Huguet and A. Poli, eds., Springer LNCS 356 (1989) 269–300.

[31] J. Heintz and J. Morgenstern : On the intrinsic complexity of elimination theory, J. of Complexity 9 (1993) 471–498.

[32] J. Heintz and C.P. Schnorr : Testing Polynomials which are easy to compute, Proc. 12th Ann. ACM Symp. on Computing (1980) 262–268; also in Logic and Algorithmic. An International Symposium held in Honour of Ernst Specker, Monographie No. 30 de l’Enseignement de Mathématiques, Genève (1982) 237–254.

[33] J. Heintz and M. Sieveking : Absolute primality of polynomials is decidable in random polynomial time in the number of the variables, 8th International Colloquium on Automata, Languages and Programming ICALP 81, Springer LNCS 115 (1981) 16–28.

[34] O. Ibarra, H. Moran : Probabilistic algorithms for deciding equivalence of straight–line programs, J. ACM 30, Vol. 1 (1983), 217–228 [35] B. Iversen. Generic Local Structures of the Morphisms in Commutative Algebra. Springer Lect. Notes

in Math. 310, Springer-Verlag (1973).

[36] J. Ja’ Ja’ : An introduction to parallel algorithms, Addison–Wesley (1992)

[37] E. Kaltofen : Greatest common divisors of polynomials given by straight line programs, J. ACM 35 (1) (1988) 234–264.

[38] E. Kaltofen : Factorization of polynomials given by straight–line programs, Randomness in Computation, Advances in Computing Research 5, S. Micali, ed., JAI Press Inc., Greenwich, CT. (1989) 375–412.

[39] J. Kollár : Sharp Effective Nullstllensatz, J. of A.M.S. 1 (1988) 963-975.

[40] T.Krick and L.M.Pardo : A Computational Method for Diophantine Approximation, to appear in Proc. MEGA’94, Birkhäuser Progress in Mathematics.

[41] T. Krick, L.M. Pardo : Une approche informatique pour l’approximation diophantienne, C. R. Acad. Sci. Paris, t. 318, Série I, no. 5 , (1994) 407–412.

[42] E. Kunz : Kähler Differentials, Advanced Lectures in Mathematics, Vieweg Verlag, Braunschweig/Wiesbaden (1986)

[43] Y.N. Lakshman, D. Lazard : On the complexity of zero–dimensional algebraic systems, Proc. MEGA’90, Carlo Traverso, ed., Prog. Math., vol. 94, Birkhäuser Boston (1991) 217–225.

[44] D. Lazard : Résolution des systèmes d’équations algébriques, Theor. Comp. Sci. 15 (1981) 77-110.

[45] A.K. Lenstra, H.W. Lenstra, L. Lovász : Factoring polynomials with rational coefficients, Math. Ann. 261 (1982) 515-534.

[46] F.S. Macaulay : The Algebraic Theory of Modular Systems, Cambridge University Press (1916)

[47] M. Moeller : Systems of algebraic equations solved by means of endomorphisms, in Proc. 10th International Conference Applied Algebra, Algebraic Algorithms and Error–Correcting Codes AAECC–10, Puerto Rico 1993, G. Cohen, T. Mora and O. Moreno, eds., Springer LNCS.

[48] J.L. Montaña and L.M. Pardo : Lower Bounds for Arithmetic Networks, AAECC, vol. 4 (1993), 1–24.

[49] J. Morgenstern : How to compute fast a function and all its derivatives, Prépublication No. 49, Université de Nice 1984.

[50] L.M. Pardo : How lower and upper complexity bounds meet in elimination theory, to appear in Proc. 11th International Symposium Applied Algebra, Algebraic Algorithms and Error–Correcting Codes, AAECC-11, Paris1995, Springer LNCS 948 (1995) 33–69.

[51] P. Philippon : Dénominateurs dans le théorème des zéros de Hilbert, Acta. Arith. 58 (1991) 1–25.

[52] J. Sabia and P. Solernó : Bounds for traces in complete intersections and degrees in the Nullstellensatz, in AAECC, vol. 6 (1995) 353–376.

[53] J. Sabia, P. Solernó : On intrinsic bounds in the Nullstellensatz, Manuscript Univ. de Buenos Aires (1995).

[54] A. Schönhage : On the power of random acces machines, in Proc. 6th International Conference on Automata, Languages and Programming, ICALP, Graz (1979) 520–529

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

[56] M. Shub, S. Smale : Complexity of Bezout’s theorem V : Polynomial time, Theoretical Comp. Sci. 133 (1994) 141–164.

[57] M. Shub, S. Smale : On the intractability of Hilbert’s Nullstellensatz and an algebraic version of NP ≠ P?, IBM Research Report, Yorktown Heights (1994)

[58] V.G. Sprindžuk : Diophantine equations involving unknown primes, Trudy MIANSSR 158 (1981) 180–196.

[59] V. Strassen : Algebraic Complexity Theory, Handbook of Theoretical Computer Science, ch. 11 (1990) 634–671.

[60] V. Strassen : Vermeidung von Divisionen, Crelle J. Reine Angew. Math. 264 (1973) 184-202.

[61] V. Strassen : Die Berechungskomplexität von elementarsymmetrischen Funktionen und von Interpolationskoffizienten, Numer. Math. 20 (1973) 238–251.

[62] M. Yasumoto : Nonstandard arithmetic and Hilbert’s irreducible sequences, manuscript.

[63] P. Zariski, O. Samuel : Commutative Algebra II, Graduate Texts in Math. 29, Springer Verlag (1960).

[64] R.E. Zippel : Probabilistic Algorithms for Sparse Polynomials, Springer LNCS 72 (1979) 216–226.