A Computational Method for Diophantine Approximation

Teresa Krick^{∗}

Departamento de Matemática Universidad de Buenos Aires 1428 Buenos Aires, Argentina

krick@mate.dm.uba.ar

Luis M. Pardo^{†}

Departamento de Matemática Universidad de Cantabria 39071 Santander, Spain

pardo@ccucvx.unican.es

                     This paper is published in
         Algorithms in Algebraic Geometry and Applications.
       Volume 143 of Progress in Mathematics, pages 193--254.
                      Birkhäuser Verlag, 1996.

Abstract. We present a new method, based on computational elements as non-scalar straight line programs, complexity of elimination and computational commutative algebra, that provides bounds of optimal order for the height of polynomials arising in Bezout identity and membership problems in complete intersections. The method also discusses simulations of both computational problems by probabilistic polynomial Turing machines.

Keywords. Non-scalar straight line program, Effective Nullstellensatz, membership problem in complete intersections, height of integer numbers and points, probabilistic Turing machines.

∗Partially supported by UBACYT and CONICET (Argentina)

†*********Partially supported by DGICyT PB 92–0498–C02–01, PB93–0472–C02–02 and “POSSO”, ESPRIT-BRA 6846.

Contents

1 Introduction 3

2 Non-scalar Straight Line Programs 9 2.1 Basic notations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 2.2 Some technical lemmas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 2.3 Some useful bounds . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14

3 Questors and Vermeidung von Divisionen 16 3.1 Questors or correct test sequences . . . . . . . . . . . . . . . . . . . . . . . 16 3.2 Vermeidung von Divisionen . . . . . . . . . . . . . . . . . . . . . . . . . . . 19

4 Isolated Points 21 4.1 The case of projective dimension zero . . . . . . . . . . . . . . . . . . . . . 22 4.2 As many equations as unknowns . . . . . . . . . . . . . . . . . . . . . . . . 24 4.3 Separating points of two univariate polynomials . . . . . . . . . . . . . . . . 25 4.4 The case of two variables . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 4.5 Describing the isolated zeros of n n-variate polynomials . . . . . . . . . . . 29 4.6 The primitive element for a reduced complete intersection . . . . . . . . . . 30 4.7 Height of isolated points of affine varieties . . . . . . . . . . . . . . . . . . . 31 4.8 Triviality test based on isolated points . . . . . . . . . . . . . . . . . . . . . 33

5 Division in Reduced Complete Intersections 34 5.1 Notations and assumptions . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 5.2 The division theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 5.3 Basic general trace theory . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 5.4 Computing matrices of homothesies . . . . . . . . . . . . . . . . . . . . . . 38

6 Preparation of the Input Data 41 6.1 Bertini’s theorem. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 6.2 Simultaneous Noether normalization . . . . . . . . . . . . . . . . . . . . . . 46

7 Nullstellensatz and Membership Problem 48 7.1 Describing the output polynomials . . . . . . . . . . . . . . . . . . . . . . . 48 7.2 A probabilistic Turing machine . . . . . . . . . . . . . . . . . . . . . . . . . 52

8 References 53

1 Introduction

The procedures to solve algebraic geometry elimination problems have usually been designed from the point of view of commutative algebra. For instance, let us consider the problem of deciding whether a given system of polynomial equalities has a solution. This means that we have to eliminate a single block of quantifiers in a formula with polynomial equations. More precisely, let ZZ be the ring of integer numbers, 0 Q the field of rationals and C the field of complex numbers. Assume your are given (input) polynomials f_{1}, …, f_{s} ∈ ZZ[X_{1}, …, X_{n}] and you want to decide whether the following formula holds :

∃x_{1} ∈ C, …, ∃x_{n} ∈ C :  f_{1}(x_{1}, …, x_{n}) = 0, …, f_{s}(x_{1}, …, x_{s}) = 0  (1)

By means of Hilbert’s Nullstellensatz this question can be reduced to the following problem in terms of ideals : Decide whether the integer 1 belongs to the ideal generated by f_{1}, …, f_{s} in 0 Q[X_{1}, …, X_{n}] , i.e. decide whether there exist polynomials g_{1}, …, g_{s} ∈ 0 Q[X_{1}, …, X_{n}] such that the following identity holds :

1 = g_{1}f_{1} + ⋯ + g_{s}f_{s}  (2)

Thus, an Effective Nullstellensatz solves the following two problems :

• Decision Problem : Decide whether there exist polynomials g_{i} ’s such that equality (2) holds.

• Representation Problem : In the affirmative case, compute polynomials g_{i} ’s such that equality (2) holds.

In this form, the previous elimination problem is transformed in a particular case of the general Membership Problem to polynomial ideals of ideal theory (or commutative algebra). This more general problem can be stated in the following terms : given polynomial inputs f_{1}, …, f_{s} and g in ZZ[X_{1}, …, X_{n}] the problem ask for the following two issues :

• Decision Problem : Decide whether g belongs to the ideal generated by the polynomials f_{1}, …, f_{s} in the ring 0 Q[X_{1}, …, X_{n}] .

• Representation Problem : In the affirmative case, find polynomials g_{1}, …, g_{s} ∈

0 Q[X_{1}, …, X_{n}] such that

g = g_{1}f_{1} + ⋯ + g_{s}f_{s}.

The complexity of the Membership Problem was characterized by E.Mayr and A.Meyer in [42] and [43]. They showed that this problem is exponential space complete (EXPSPACE– complete). As an immediate consequence the time to solve it is at least exponential (and probably doubly exponential) and this lower bound cannot be improved because of the Time and Space Hierarchy Theorems. Therefore, the general problem of ideal membership is placed out of the scope of any tractable (theoretical or practical) complexity class.

Nevertheless, the Effective Nullstellensatz has a particular feature ( g = 1 and its geometrical meaning). This suggests that an adapted specific procedure might solve this problem within a much lower complexity. In these pages we’ll show that polynomial upper bounds (for time and space) can be obtained for this problem by means of probabilistic algorithms.

Clearing denominators in the identity (2), one can reformulate the problem as the computation of a non–zero integer a ∈ ZZ − {0} and integer polynomials g_{1}, …, g_{s} ∈ ZZ[X_{1}, …, X_{n}] such that the following equality holds :

a = g_{1}f_{1} + ⋯ + g_{s}f_{s}  (3)

After some preprocessing (see Section 6), the effective Nullstellensatz can be reinterpreted as a particular case of the Membership Problem in a Complete Intersection Ideal, i.e. decide whether a polynomial g belongs to the ideal generated by f_{1}, …, f_{s} in 0 Q[X_{1}, …, X_{n}] (Decision Problem) and if the answer is affirmative compute an integer a ∈ ZZ − {0} and integer polynomials g_{1}, …, g_{s} such that a g = g_{1}f_{1} + ⋯ g_{s}f_{s} (Representation Problem) in the particular case where f_{1}, …, f_{s}, g ∈ ZZ[X_{1}, …, X_{n}] (s ≤ n + 1) verify the conditions :

• (f_{1}, …, f_{s−1}) is a proper ideal of dimension n − s + 1 .

• The polynomial f_{s} is not a zero divisor in 0 Q[X_{1} …, X_{n}]/(f_{1}, …, f_{s−1}) .

Both problems (Effective Nullstellensatz and Membership in Complete Intersections) have a similar treatment as we shall see in the forthcoming pages.

From the point of view of Turing machine complexity, it is commonly accepted that the space in a Turing machine is measured as the space used by the working tapes. In some sense, this is CPU space, while the space required by input and output tapes is an “external memory” requirement. Nevertheless, this last amount of space gives an immediate lower bound for the sequential time of the procedure. In particular, exponential space encoding of outputs imply exponential time lower bounds. Hence, any improvement of the complexity of the geometric problems demands an encoding of the output polynomials in, at least, polynomial space.

Most of the complexity analysis of Effective Nullstellensatz naïvely consider dense representations both for the input and the output polynomials. This simply means that one writes all the coefficients (integer or rational numbers) of all monomials of the f_{i} ’s and the g_{i} ’s. Let us define the (absolute) height of an integer polynomial as the maximum of the absolute values of its coefficients (then the binary size of an integer number is the logarithm of its height). Assume that d is an upper bound for the degree of the polynomial inputs f_{i} ’s and that η is an upper bound for the height of their coefficients. Finally, recall that the number of monomials of an n –variate polynomial of degree d is assymptotically d^{n}. Hence, the input length is of order s d^{n} log_{2} η.

The studies of complexity of the Effective Nullstellensatz were focused on the estimation of upper bounds for the degrees and heights of the output polynomials a ∈ ZZ and g_{1}, …, g_{s} ∈ ZZ[X_{1}, …, X_{n}] in terms of s, d and η.

A first bound for the degree of the g_{i} ’s was obtained in 1926 as a consequence of the work of G.Hermann ([31]). Later on, D.W.Masser and G.Wüsholz ([47]) extended transcendency proofs of A.Gel’fond ([21] and [49]). Using the methods of [31], they obtained upper bounds for the height of a and the polynomials g_{1}, …, g_{s}. Both results lead to bounds of order d^{2^{n}} for the degrees and d^{2^{n}} log_{2} η for the binary size of a and for the coefficients of the g_{i} ’s, which is far from being tractable.

The bounds for the degrees of the polynomials g_{1}, …, g_{s} were successively improved in [10], [12] and [34] to deg f_{i}g_{i} ≤ max{3, d}^{n}. A well–known example of Mora–Lazard– Masser–Philippon shows that this bound for the degree is essentially optimal.

These estimations reduce the Effective Nullstellensatz to the resolution of a linear system of equations by comparision of coefficients in the identity (3). The linear system contains as many variables as monomials of degree at most max{3, d}^{n} (while a is simply the determinant of a maximal minor of the system matrix). This leads to an exponential number of coefficients in the dense representation ( sd^{n^{2}} ) of binary size d^{O(n^{2})} log_{2} η^{O(1)} . As observed in [12], by transforming Berkowitz algorithm for the determinant in boolean circuits and transforming the paralell time in sequential space (cf. [6]), this gives poly– logarithmic bounds (n log_{2} d)^{O(1)} for the working space. Nevertheless, this procedure still requires dense representation of polynomial outputs, i.e. an amount of exponential space in “external memory” is required ( d^{O(n^{2})} ) and, in particular, this yields to an exponential lower bound ( d^{O(n^{2})} ) for the sequential time with respect to the input size.

In the realm of transcendental number theory and diophantine approximation, it was still interesting to get more precise bounds for the height of the output polynomials. A typical application of these bounds are Liouville estimations (cf. [39]) : lower bounds for the absolute value of multivariate integer polynomials when evaluated at algebraic points). In [2] and [3], C.Berenstein and A.Yger obtained a division theorem in terms of complex integrals which implies the following precise bound for the heights in identity (3) :

max{log_{2} ht(a), log_{2} ht(g_{i})} ≤ κ(n)d^{8n+3}(log_{2} η + d log_{2} d)

(where κ(n) is an effective constant depending only on n).

As in the case of the degree bounds, these bounds for the height are optimal as shows the following simple example for η ∈ ZZ − {0} :

f_{1} := X_{1} − η , f_{2} := X_{2} − X_{1}^{d} , …, f_{n} := X_{n} − X_{n−1}^{d} , f_{n+1} := X_{n}.

Since f_{1}, ⋯, f_{s} don’t share any complex zero they satisfy identity (3). Specializing this equation in the integer point (η, η^{d}, …, η^{d^{n−1}}) ∈ ZZ^{n} one immediately remarks that log_{2} ht(a) ≥ d^{n−1} log_{2} |η |.

This optimal bound suggests an improvement : one still has an exponential number of coefficients, but the size of each one of them is polynomial in the input length. Nevertheless, it does not solve all the difficulties and some other alternatives have to be considered when dealing with the effective Nullstellensatz since no advance in terms of complexity can be expected while keeping the underlying dense encoding of polynomials.

One of the possible alternatives might be the sparse representation of polynomials : one encodes only the non–zero coefficients both of the input and of the output polynomials. However, this approach presents many difficulties since it is still not known whether the output polynomials in the Nullstellesatz have few monomials of small height coefficients. For instance, if we consider the complete intersection ideal generated by (X − 1) in 0 Q[X] and the polynomial X^{n} − 1 which is a sparse polynomial in this ideal, the output polynomial is X^{n−1} + X^{n−2} + ⋯ + X + 1 which is no more sparse. On the other hand, “sparsity” is very unstable when dealing with geometric problems (for instance, a linear change of coordinates transforms sparse polynomials into polynomials with many non–zero coefficients).

Another alternative to improve the algorithmic resolution of Nullstellensatz is described in [23], [24] and [18]. These papers introduce the encoding of polynomials by means of straight line programs (a natural idea coming from algebraic complexity theory and semi– numerical algorithms). A straight line program consists on a description of the evaluation scheme one chooses in order to evaluate a given polynomial at a concrete point, using the arithmetic operations +, −, × and eventually / and some fixed integer constants (that we call parameters). For instance, to “write” the determinant polynomial of an indeterminate matrix of order n would require n! places, while to evaluate its specialization can be performed in O(n^{3}) arithmetic steps.

By a dimension argument, one can easily show that most polynomials of degree D in n variables require D^{n} arithmetic operations to be evaluated. However, in their work the authors show that even if the output and the intermediate polynomials in the Effective Nullstellensatz are of degree d^{O(n)} , their evaluation schemes are also of order d^{O(n)} (instead of the expectable d^{O(n^{2})} ). The authors also present an algorithm to obtain these polynomial outputs.

These papers are a first step to improvements, since the exponential lower bound does not hold in these conditions. Nevertheless, there were still some problems when a Turing machine has to simulate the procedure the authors describe.

In order to understand these problems, we need to introduce here the representation of a straight line program by means of a (directed acyclic) graph, and the complexity parameters we consider will be essentially the size L of the graph (corresponding to the sequential time of the evaluation), its depth ℓ (the paralell time) and the maximum η of the heights of the integer parameters introduced along the graph.

Proposition 15 below shows then that the growing of the intermediate values obtained when applying a straight line program to an integer point depends only polynomially on the size L of the graph and on the height η of the parameters while it is doubly exponential on the depth ℓ.

In [23] and [18] the authors encode intermediate and output polynomials by straight line programs of size d^{O(n)} and depth O(n^{2} log_{2}^{2} d) . This last bound could imply that they are manipulating integer numbers of exponential binary size d^{O(n^{2})} . Since arithmetic operations between integer numbers of exponential length require exponential time, these procedures risk to be still exponential (even if they are polynomial in the algebraic complexity model). However if one succeeds to control the depth of the graphs (together with the height of the parameters), it would be possible to encode the output polynomials in polynomial space d^{O(n)} . Moreover controlled bounds for the heights of the outputs are also interesting because of their applications to transcendental number theory and diophantine approximation.

In the present paper, we reconsider these questions introducing the encoding of polynomials by means of (division free) non-scalar straight line programs. This scheme has the following features :

• Linear operations are taken for free.

• No division is allowed.

Our main goal here is to control the non-scalar depth (below O(n log_{2} d) ) and the height of the parameters of non-scalar straight line programs arising in both problems. We are able to show the following result in terms of non-scalar straight line programs :

Theorem 1 (Effective Nullstellensatz) Let f_{1}, …, f_{s} be polynomials in ZZ[X_{1}, …, X_{n}] of degree and (absolute) height bounded by d ≥ n and η respectively, which don’t share any zero in C^{n}. Then there exist a non-scalar straight line program of size sd^{O(n)} , depth O(n log_{2} d) and integer parameters of absolute height max{d^{O(n)}, η} which evaluates an integer number a ∈ ZZ − {0} and polynomials g_{1}, …, g_{s} ∈ ZZ[X_{1}, …, X_{n}] such that :

a = g_{1}f_{1} + ⋯ + g_{s}f_{s}.

Similarly, we deal with the membership problem in complete intersection ideals. We obtain the following result (which proof is similar to the previous one) :

Theorem 2 (Membership problem in a complete intersection) Let f_{1}, …, f_{r} (r ≤ n) and g be polynomials in ZZ[X_{1}, …, X_{n}] of degree and height bounded by d ≥ n and η respectively. Assume that (f_{1}, …, f_{r}) is a proper ideal in 0 Q[X_{1}, …, X_{n}] of dimension n − r and that g ∈ (f_{1}, …, f_{r}) holds. Then, there exists a non-scalar straight line program of size d^{O(n)} , depth O(r log_{2} d) and integer parameters of height max{d^{O(n)}, η} which evaluates an integer a ∈ ZZ − {0} and polynomials g_{1}, …, g_{r} ∈ ZZ[X_{1}, …, X_{n}] such that :

a g = g_{1}f_{1} + ⋯ + g_{r}f_{r}.

As we mentionned before, Proposition 15 shows that the growing of the intermediate values in a non-scalar straight line program is polynomial in the size of the graph and the height of the parameters and doubly exponential on the depth. For the particular non-scalar straight line programs we are considering in these two statements, the evaluation at an integer point can be simulated by a Turing machine using time and space bounded by d^{O(n)} . This is due to the controlled depth of the graph and heights of the parameters. Hence, using our analysis of correct test sequences for the non-scalar model (Section 3 below) and checking the intermediate polynomials we can design in Subsection 7.2 (following the notations of [1, Chapter 6]) a probabilistic Turing machine which shows that :

Corollary 3 The Effective Nullstellensatz and the Membership Problem to Complete Intersection Ideals are in the BPP–class of bounded error probabilistic polynomial time machines, i.e. there is a probablistic Turing machine that solves both problems within time polynomial in the dense representation of the input polynomials. In particular, both problems can be solved in polynomial space counting also “external memory” requirements.

Theorems 1 and 2 have also consequences of a more mathematical nature. First of all, combining Theorem 1 with the estimations of Proposition 15 we recover for the effective Nullstellensatz the bounds for the degrees of [10],[12], and [34] and the bounds for the heights of [2] and [3] (simultaneously with the property of “quick” evaluation of [18]) :

Corollary 4 Let f_{1}, …, f_{s} be polynomials in ZZ[X_{1}, …, X_{n}] of degree and (absolute) height bounded by d ≥ n and η respectively, which don’t share any zero in C^{n}. Then there exist an integer a ∈ ZZ−{0} and polynomials g_{1}, …, g_{s} ∈ ZZ[X_{1}, …, X_{n}] such that :

• deg g_{i} = d^{O(n)} (1 ≤ i ≤ s)

• max{log_{2} ht(a), log_{2} ht(g_{1}), …, log_{2} ht(g_{s})} = d^{O(n)} max{log_{2} η, log_{2} s}

In [16], M.Elkadi obtained bounds for the degrees and the heights of the polynomials arising in the membership problem to Complete Intersections. This author uses a slight modification of the arguments of [2] and [3]. We independently obtain similar results as a consequence of the two theorems above :

Corollary 5 Let f_{1}, …, f_{r} (r ≤ n) and g be polynomials in ZZ[X_{1}, …, X_{n}] of degree and height bounded by d ≥ n and η respectively. Assume that (f_{1}, …, f_{r}) is a proper ideal in 0 Q[X_{1}, …, X_{n}] of dimension n − r and that g ∈ (f_{1}, …, f_{r}) holds. Then there exist an integer a ∈ ZZ−{0} and polynomials g_{1}, …, g_{r} ∈ ZZ[X_{1}, …, X_{n}] such that :

• deg g_{i} = d^{O(r)} (1 ≤ i ≤ r)

• max{log_{2} ht(a), log_{2} ht(g_{1}), …, log_{2} ht(g_{r})} = d^{O(r)}n log_{2}(η)

One can also apply the bounds arising in the straight line programs to the analysis of the height of varieties. In particular, the results of Section 4 on the isolated points of affine algebraic varieties lead to a bound for the heights which is essentially the same that follows from [7].

Corollary 6 Let f_{1}, …, f_{r} (r ≤ n) and g be polynomials in ZZ[X_{1}, …, X_{n}] of degree and height bounded by d ≥ n and η respectively, and let V denote the algebraic affine variety of C^{n} defined by :

V := {f_{1} = 0, …, f_{s} = 0}

Then V has at most d^{n} isolated points whose heights verify :

log_{2} ht(P) = d^{O(n)}(log_{2} s + log_{2} η)

In particular, applying straightforward the bounds for the complex solutions of an integer polynomial we obtain the following Corollary :

Corollary 7 With the same notations, the coordinates of every isolated point (x_{1}, …, x_{n}) ∈ C^{n} of the algebraic set V = {f_{1} = 0, …, f_{s} = 0} verify :

\frac{1}{d^{Ω(n)}(log_{2} s + log_{2} η)} ≤ log_{2} | x_{i} |≤ d^{O(n)}(log_{2} s + log_{2} η)

We conclude this introduction observing that the results suggest the existence of some trade–off between complexity analysis, encoding of polynomials as straight line programs and bounds in diophantine approximation and number theory. We hope that this trade–off could be improved in forthcoming works on the subject.

2 Non-scalar Straight Line Programs

2.1 Basic notations

This section is devoted to introduce a geometric model for polynomial evaluation. Each polynomial P (X_{1}, …, X_{n}) ∈ ZZ[X_{1}, …, X_{n}] has a dense representation of the form :

P (X_{1} …, X_{n}) = ∑_{|μ|≤deg(P)} P^{μ} X_{1}^{μ_{1}} … X_{n}^{μ_{n}}

where deg(P) denotes the total degree of P , μ := (μ_{1}, …, μ_{n}) ∈ IN_{0}^{n} is a multi-index, |μ|:= μ_{1} + ⋯ + μ_{n} is its length and P^{μ} is an integer. We define the (absolute) height of P as the maximal absolute value of all its coefficients :

ht(P) := max{| P^{μ} |:| μ |≤ deg(P)}

Similarly, for a finite falmily F ⊂ ZZ , we define ht(F) as the maximal absolute value of all its elements. In the sequel we shall work with the complexity model of non-scalar straight line programs (see for instance [27], [55] or [46]) : a non-scalar straight line program is a device which evaluates (and hence represents) a given polynomial of ZZ[X_{1}, …, X_{n}] taking ZZ− linear operations for free. We shall tacitly assume that our straight line programs do not contain any division. We shall represent a straight line program for the evaluation of a polynomial P ∈ ZZ[X_{1}, …, X_{n}] by a directed acyclic graph G whose nodes are labelled gates which perform arithmetical operations. Therefore we identify the nodes of G with the corresponding gates. The graph G disposes of n + 1 particular nodes labelled by the variables X_{1}, …, X_{n} and the constant 1 . These nodes are called the input gates of G. We define the depth of a gate ν of our graph as the length of the largest path which joins ν with some input gate. Let us denote the gates of the directed acyclic graph by pairs of integer numbers (i, j) , where i represents the depth of the gate and j is the corresponding value of an arbitrary numbering imposed to the set of gates of depth i (this encoding can be seen, for instance, in [45]).

Definition 8 A division-free non-scalar straight line program with inputs X_{1}, …, X_{n} is a pair Γ := (G, Q) , where G is a directed acyclic graph, with n + 1 input gates, unbounded fan-in, and Q is a function that assigns to every gate (i, j) one of the following instructions:

\begin{matrix}i = 0 : & Q_{0,1} := 1 , Q_{0,2} := X_{1} , …, Q_{0,n+1} := X_{n} \\ 1 ≤ i ≤ ℓ : & Q_{i,j} := (∑_{r≤i−1,1≤s≤L_{r}} A_{i,j}^{r,s} Q_{r,s}) · (∑_{r′≤i−1,1≤s′≤L_{r′}} B_{i,j}^{r′,s′} Q_{r′,s′}) \end{matrix}

Here, A_{i,j}^{r,s}, B_{i,j}^{r′,s′} are indeterminates over ZZ called the parameters introduced in Γ . The size of the straight line program Γ is L(Γ) = L_{0} + … + L_{ℓ} (where L_{0} := n + 1 ) and its depth ℓ(Γ) = ℓ (these notions coincide to the notions of size and depth of the underlying computation graph).

Let us mention that in our notation the subindices of the parameters A_{i,j}^{r,s} and B_{i,j}^{r′,s′} represent the gate of the multiplication they are assigned and the superindices correspond to the previous result they involve in the multiplication. We abbreviate \underline{A} = (A_{i,j}^{r,s}) and \underline{B} = (B_{i,j}^{r′,s′}) . Semantically speaking the straight line program Γ defines an evaluation algorithm of the polynomials (intermediate results):

Q_{i,j} = ∑_{|μ|≤2^{i}} Q_{i,j}^{μ}(\underline{A}, \underline{B}) X_{1}^{μ_{1}} … X_{n}^{μ_{n}}  (4)

Here, each coefficient Q_{i,j}^{μ}(\underline{A}, \underline{B}) belongs to the polynomial ring ZZ[\underline{A}, \underline{B}] . The result Q_{i,j} has degree at most 2^{i} with respect to the variables X_{1}, …, X_{n}. We obtain a specialization in ZZ of the non-scalar straight line program Γ substituting the parameter sets \underline{A} and \underline{B} by integers \underline{α} = (α_{i,j}^{r,s}) and \underline{β} = (β_{i,j}^{r′,s′}) (we insist on the fact that α_{i,j}^{r,s}, β_{i,j}^{r′,s′} belong to ZZ ). A specialization \underline{A} → \underline{α}, \underline{B} → \underline{β} of the parameters of Γ induces a straight line program (computation) in ZZ[X_{1}, …, X_{n}] in the most obvious way. The intermediate results of this specialized straight line program γ are the polynomials of the form Q_{i,j}(\underline{α}, \underline{β}, X_{1}, …, X_{n}) . In this sense we shall say that a given polynomial P ∈ ZZ[X_{1}, …, X_{n}] is evaluable, or computable, by (a specialization of) the straight line program Γ if there exists a specialization \underline{A} ⟶ \underline{α}, \underline{B} ⟶ \underline{β} of the parameters of Γ such that for some gate (i, j) the following equality holds :

P (X_{1}, …, X_{n}) = Q_{i,j}(\underline{α}, \underline{β}, X_{1}, …, X_{n})  (5)

Taking into account the representation of (4) we can rewrite identity (5) as :

P^{μ} = Q_{i,j}^{μ}(\underline{α}, \underline{β})

for all μ with | μ |≤ 2^{i} and P^{μ} = 0 for | μ | 2^{i} . Finally, for η a positive number we say that a specialization \underline{A} ⟶ \underline{α}, \underline{B} ⟶ \underline{β} has height at most η or equivalently that P ∈ ZZ[X_{1}, …, X_{n}] is computable by a straight line program Γ with parameters of height η if ht(\underline{α}) ≤ η and ht(\underline{β}) ≤ η hold. We will also say that an integer α ∈ ZZ is computable by a non-scalar straight line program Γ when it is considered as an element of ZZ[X] .

2.2 Some technical lemmas

Most basic examples of straight line programs belong to the field of linear algebra. We overview some of them under the scope of non-scalar measure. For instance, next proposition describes the bounds naturally arising from Berkowitz computation of determinant and characteristic polynomial (cf. [4]) :

Proposition 9 (Berkowitz, 1986) Let R be a ring. There is a non-scalar straight line program of size O(n^{5}) , depth O(log_{2} n) and parameters in {−1, 0, 1} which computes from the entries of every matrix A ∈ M_{n}(R) the coefficients of its characteristic polynomial and, in particular, its determinant det(A) .

Proof.– We only need to follow the proof of [4]. Assume you are given a matrix in M_{n}(R) :

A = ( \begin{matrix}a_{1 1} & … & a_{1 n} \\ ⋮ & ... & ⋮ \\ a_{n 1} & … & a_{n n} \end{matrix} )

For every m ∈ {1, …, n − 1} let us define the matrices :

\begin{aligned}M_{m} : & = & ( \begin{matrix}a_{m+1 m+1} & … & a_{m+1 n} \\ ⋮ & ... & ⋮ \\ a_{n m+1} & … & a_{n n} \end{matrix} ) \\ R_{m} : & = & ( a_{m m+1} … a_{m n}) \\ S_{m} : & = & ^{t} ( a_{m+1 m} … a_{n m}) \end{aligned}

Now we define the lower (n − m + 1) × (n − m) triangular Toeplitz matrix C_{m} :

(C_{m})_{i j} := \{ \begin{matrix}−1 & if i = j \\ a_{m m} & if i = j + 1 \\ −R_{m} M_{m}^{k−1} S_{m} & if i = j + k (k1) \\ 0 & otherwise \end{matrix}

Finally, let us denote the characteristic polynomial of A by:

X_{A}(T) := det(A − T.Id) = ∑_{k=0}^{n} p_{k} T^{k}

In [4] it is shown that :

( p_{0} ; ⋮ ; p_{n} ) = ∏_{m=1}^{n} C_{m}

Therefore we can compute the coefficients of X_{A} by means of the following straight line program :

• For every m ∈ {1, …, n − 1} , we compute in parallel gates the coordinates of all the powers M_{m}^{i} for i = 0, …, n. For each m, this computation can be done straight-forward in size O(n^{4}) and non-scalar depth log_{2} n + 2 , with parameters in {0, 1}. This gives a total size of O(n^{5}) and the same non-scalar depth log_{2} n + 2 .

• Now, for each m and each i, we compute −R_{m} M_{m}^{i} S_{m}. We can perform this computation in additionnal size O(n^{3}) and non-scalar depth 3 . Thus, to compute all −R_{m} M_{m}^{i} S_{m} requires additionnal size O(n^{5}) and non-scalar depth 3 .

• Finally we compute the product ∏_{m=1}^{n} C_{m}. This can be done in additionnal size O(n^{4}) and non-scalar depth log_{2} n + 2 .

The announced bounds are obtained adding all these amounts.

As a consequence of this Proposition we can show the following estimations for non-scalar straight line programs computing gcd’s and squarefree decompositions.

Lemma 10 Let R be an integral domain and f, g ∈ R[X] be two univariate polynomials of degree bounded by D. Then there is a non-scalar straight line program Γ of length O(D^{6}) , depth O(log_{2} D) and parameters in {−1, 0, 1} which, from the coefficients of f and g, computes the coefficients of a greatest common divisor in R[X] of these polynomials. These coefficients are integer polynomials in the coefficients of f and g of degree bounded by 2D.

Proof.– We follow here a scheme of [5] or [20]. Set f := f_{d}X^{d} + … + f_{0} and g := g_{e}X_{e} + … + g_{0} , where 0 ≤ e ≤ d ≤ D ( f_{d} g_{e} ≠ 0 ). For 0 ≤ i ≤ e consider the (d + e − 2i)− square submatrix P_{i} of the Sylvester matrix of (f, g) which consists on the first (e − i) columns of f ’s, the first (d − i) columns of g ’s , and the first (d + e − 2i) rows. Then, for 0 ≤ i ≤ e, compute det (P_{i}) and choose the minimal value k such that det (P_{k}) ≠ 0 . This will be the degree of the desired gcd(f, g) . Now compute the last column (y_{e−k−1}, …, y_{0}, z_{d−k−1}, …, z_{0}) of the adjoint matrix of P_{k}. The polynomial (y_{e−k−1}X^{e−k−1} + … + y_{0})f + (z_{d−k−1}X^{d−k−1} + … + z_{0})g is the desired (non-nul scalar multiple of) gcd(f, g) .

Lemma 11 Let R be an integral domain and f_{1}, …, f_{s} ∈ R[X] be univariate polynomials of degree bounded by D. Then there is a non-scalar straight line program Γ of length O(s^{5}D^{6}) , depth O(log_{2}(sD)) and parameters in {−1, 0, 1} which computes from the coefficients of f_{1}, …, f_{s} the coefficients of a greatest common divisor gcd(f_{1}, …, f_{s}) ∈ R[X] of these polynomials; these coefficients are integer polynomials in the coefficients of f_{1}, …, f_{s} of degree bounded by 2D + 1 .

Proof.– We also follow [20] : we need to determine h ∈ R[X] \ {0} of minimal degree such that :

h = r_{1}f_{1} + … + r_{s}f_{s}, deg(s_{i}) ≤ D (1 ≤ i ≤ s)

Setting f_{i} := ∑ f_{ij}X^{j} and r_{i} := ∑ r_{ij}X^{j}, it is enough to consider the consistency of the linear systems describing the condition “ ∑ r_{i}f_{i} is monic of degree k (≤ D) ”, which are given by the equations:

∑_{{1≤i≤D \atop 0≤j≤m}} r_{ij}f_{i m−j} = \{ \begin{matrix}0 & for k < m < 2D \\ 1 & for m = k \end{matrix}

Thus there are D+1 systems of 2D−k equations in s(D+1) variables, whose consistency depends on analysis of ranks. Once detected the degree d of gcd(f_{1}, …, f_{s}) , we solve it in R using the adjoint and the determinant of an invertible square submatrix of maximal order.

Lemma 12 Let R be an integral domain and f ∈ R[X] be an univariate polynomial of degree bounded by D. Then there is a non-scalar straight line program Γ verifying : i) Γ computes from the coefficients of f an element θ ∈ R and the coefficients of a

squarefree polynomial f^{∗} ∈ R[X] associated to f , i.e. :

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

(where f′ denotes the derivative of f )

ii) The element θ and the coefficients of f^{∗} are integer polynomials in the coefficients of f of degree bounded by 2D(D + 1) .

iii) The size of Γ is of order O(D^{6}) , the depht is O(log_{2} D) and the parameters introduced in Γ are {−1, 0, 1, …, D}.

Proof.– First compute the coefficients of f′, then apply Lemma 10 to compute the (scalar multiple of) gcd(f, f′) , and finally solve the linear system determined by the relation :

f = gcd(f, f′).f^{∗}

(the value θ is simply a maximal minor of the coefficient matrix).

Another useful technique is to know how to evaluate the homogeneous components of a polynomial given by a non-scalar straight line program :

Lemma 13 Suppose that a polynomial P := ∑ P^{μ} X_{1}^{μ_{1}} … X_{n}^{μ_{n}} ∈ ZZ[X_{1}, …, X_{n}] is computable by a non-scalar straight line program Γ with inputs X_{1}, …, X_{n}, of size L, depth ℓ and parameters in F ⊂ ZZ , and fix δ ∈ IN . Then there is a straight line program Γ′ which computes all the homogeneous components of P of degree at most δ, such that L(Γ′) = (δ + 1)^{2} L, ℓ(Γ′) = 2ℓ and F(Γ′) = F.

Proof.– The straight line program Γ′ computes all the homogeneous components of the intermediate polynomials Q_{i,j} in Γ . We will replace the original straight line program Γ by a new one which is obtained “decomposing” each step of Γ as follows :

• for i = 1 the homogeneous components of each Q_{1,j} can be computed in size 5 and depth 2, using the parameters in F (for instance if Q_{11} = (A_{0} + A_{1}X_{1} + … + A_{n}X_{n}) (B_{0} +B_{1}X_{1} +…+B_{n}X_{n}) , one computes in a first step A_{0}B_{0} , (A_{1}X_{1} +…+ A_{n}X_{n}) (B_{1}X_{1} +…+B_{n}X_{n}) , A_{0} (B_{1}X_{1} +…+B_{n}X_{n}) and B_{0} (A_{1}X_{1} +…+A_{n}X_{n}) and in the next one A_{0} (B_{1}X_{1} + … + B_{n}X_{n}) + B_{0} (A_{1}X_{1} + … + A_{n}X_{n}) ).

• for i0 : suppose that the homogeneous components of all Q_{r,s}, r < i, of degree ≤ δ are computed. We use the following simple observation to compute the homogeneous components Q_{i,j}^{(t)} of degree t ≤ δ of Q_{i,j} : if in Γ , Q_{i,j} was obtained by means of the formula

Q_{i,j} := ( ∑_{r,s} A_{i,j}^{r,s} Q_{r,s}) . ( ∑_{r′,s′} B_{i,j}^{r′,s′} Q_{r′,s′})

then

Q_{i,j}^{(t)} := ∑_{t_{1}+t_{2}=t} (∑_{r,s} A_{i,j}^{r,s} Q_{r,s}^{(t_{1})}) . (∑_{r′,s′} B_{i,j}^{r′,s′} Q_{r′,s′}^{(t_{2})})

for the same parameters (\underline{A}, \underline{B}) . So, in order to get \{Q_{(i,j)}^{(t)}, t < δ \}, we compute

for each t at most (δ + 1) products (∑_{r,s} A_{i,j}^{r,s} Q_{r,s}^{(t_{1})}) . (∑_{r′,s′} B_{i,j}^{r′,s′} Q_{r′,s′}^{(t_{2})}) and add them in a new step. Thus there are in total (δ + 1)^{2} nodes for each Q_{i,j}, and we obtain : L(Γ′) = (δ + 1)^{2} L, ℓ(Γ′) = 2 ℓ and F(Γ′) = F.

2.3 Some useful bounds

We are in conditions to show some bounds arising from the encoding of polynomials by non-scalar straight line programs. First of all, we can easily bound by 2L(L − (n + 1)) the number of parameters used by a non-scalar straight line program Γ of size L in n variables. We can also bound the degrees of the polynomials Q_{i,j}^{μ} (of Formula 4) as elements in ZZ[\underline{A}, \underline{B}] :

Lemma 14 Given a non-scalar straight line program Γ , the degree of all polynomials Q_{i,j}^{μ} ∈ ZZ[\underline{A}, \underline{B}] is 2^{i+1} − 2 (independently from μ and j).

Proof.– First of all, it is clear that the degree of Q_{i,j}^{μ} does not depend on j in a given step i. Denote by d(i, μ) the degree of such polynomials. Then Definition 8 implies that :

Q_{i,j}^{μ} = ∑_{μ_{1}+μ_{2}=μ} ( ∑_{0≤r≤i−1,1≤s≤L_{r}} A_{i,j}^{r,s} Q_{r,s}^{μ_{1}}(\underline{A}, \underline{B})) . ( ∑_{0≤r′≤i−1,1≤s′≤L_{r′}} A_{i,j}^{r′,s′} Q_{r′,s′}^{μ_{2}}(\underline{A}, \underline{B}))

(6)

Thus we get the following relation :

d(i, μ) = max_{μ_{1}+μ_{2}=μ} {max_{1≤r≤i−1}(d(r, μ_{1}) + 1) + max_{1≤r′≤i−1}(d(r′, μ_{2}) + 1)}

Now we proceed by induction on i :

• For i = 1 , d(i, μ) = 2 and it is independent from μ.

• For i1 , by hypothesis d(r, μ_{1}) = 2^{r+1} − 2 and d(r′, μ_{2}) = 2^{r′+1} − 2 for r, r′ ≤ i − 1 and | μ_{1} |≤ 2^{r}, | μ_{2} |≤ 2^{r′}. Therefore

d(i, μ) = max_{μ_{1}+μ_{2}=μ} {max_{1≤r≤i−1}(2^{r+1} − 1) + max_{1≤r′≤i−1}(2^{r′+1} − 1)} = 2 (2^{i}−1)

and the proof is complete.

Next Proposition estimates the height of a polynomial given by a non-scalar straight line program. Observe that this bound depends doubly exponentially only on the depth of the graph, while it is polynomial on its size and on the height of the parameters.

Proposition 15 A specialization \underline{A} ⟶ \underline{α}, \underline{B} ⟶ \underline{β} of height η on a straight line program Γ of size L and depth ℓ produces the following bound for the height of the evaluated polynomials :

ht(Q_{i,j}(\underline{α}, \underline{β})) ≤ ∑_{0≤|μ|≤2^{i}} | Q_{i,j}^{μ}(\underline{α}, \underline{β}) | ≤ (Lη)^{2^{i+1}−2} .

Proof.– Let us consider the polynomials Q_{i,j}(| \underline{α} |, | \underline{β} |, X_{1}, …, X_{n}) , obtained specializing the parameters in Γ according to :

A_{i,j}^{r,s} ⟼|α_{i,j}^{r,s} |
B_{i,j}^{r′,s′} ⟼|β_{i,j}^{r′,s′} |

As the polynomials Q_{i,j}^{μ}(\underline{A}, \underline{B}) have positive coefficients, we have

| Q_{i,j}^{μ}(\underline{α}, \underline{β}) |≤ Q_{i,j}^{μ}(|\underline{α}|, |\underline{β} |)

and

∑_{0≤μ≤2^{i}} | Q_{i,j}^{μ}(\underline{α}, \underline{β}) |≤ ∑_{0≤μ≤2^{i}} Q_{i,j}^{μ}(|\underline{α}|, |\underline{β} |) = Q_{i,j}(|\underline{α}|, |\underline{β} |, 1, …, 1)

Now let us define :

w(r) := max\{Q_{r,s}(| \underline{α} |, | \underline{β} |, 1, …, 1) : 1 ≤ s ≤ L_{r}\}

Hence, we follow the relations stated from the straight line program Γ to have :

Q_{i,j}(| \underline{α} |, | \underline{β} |, \underline{1}) ≤ (∑_{r,s} | α_{i,j}^{r,s} | Q_{r,s}(| \underline{α} |, | \underline{β} |, \underline{1})) (∑_{r′,s′} | β_{i,j}^{r′,s′} | Q_{r′,s′}(| \underline{α} |, | \underline{β} |, \underline{1})) .

which yields to the following recursion rule :

w(i) ≤ L^{2}η^{2} (w(i − 1))^{2}

Finally since w(1) ≤ (Lη)^{2} one easily infers the desired bound.

Remark 16 Let P ∈ ZZ[X_{1}, …, X_{n}] be a polynomial which can be evaluated by a nonscalar straight line program Γ of size L, depth ℓ and parameters of height η. Let x := (x_{1}, …, x_{n}) ∈ ZZ^{n} be a point of height at most h. Then, there exists a deterministic Turing machine that outputs P (x) ∈ ZZ in time L^{2}2^{O(ℓ)}(log_{2} L + log_{2} η + log_{2} h) . (We have to make 2L sums and one product for every gate of Γ , each of these operations being between integer numbers of binary size bounded by 2^{2ℓ}(log_{2} L + log_{2} η + log_{2} h) .)

******

Remark 17 The previous upper bounds for the height of polynomials are also useful for studies of lower bounds for polynomial evaluation. An example are Pochhammer (also called Wilkinson) polynomials. They are defined by the following rule:

P_{d}(T) := \binom{T − 1}{d}d! = (T − 1) ⋯ (T − d)

These polynomials arise in a natural way from the effective Nullstellensatz (cf. also [52] or [28]). Consider the following system of polynomial equations in the variables X_{1}, …, X_{n}, T :

X_{1}^{2} − X_{1} = 0, …, X_{n}^{2} − X_{n} = 0, ∑_{i=1}^{n} 2^{i−1}X_{i} = T

The formula equivalent to the property that this system has some solution is given by the Pochhammer polynomial for d = 2^{n} − 1 :

P_{2^{n}−1}(T) := ∏_{i=1}^{2^{n}−1}(T − i)

Because of our bounds of the height of P_{2^{n}−1} and using Stirling formula for estimating the factorial, we know that these polynomials are “hard to compute” in the following sense: If a straight line program evaluates P_{2^{n}−1} in optimal depth n, and with parameters in C with module smaller than \frac{1}{2}2^{\frac{n}{3}} , the non-scalar size required by of these polynomials is greater than 2^{\frac{n}{3}} .*********

3 Questors and Vermeidung von Divisionen

3.1 Questors or correct test sequences

One of the resources used in [18], [23] and [24] are the questors (correct test sequences) as points determining simpler probabilistic or non-uniform algorithms for elimination in commutative algebra. They keep inside all the gestions and distribution of resources required by this kind of algorihtms. This section is essentially devoted to state that the maximal height of a questor set in characteristic zero depends only on the depth under the non-scalar model. We will later apply this property to analyze the points, in the avoiding division method of Strassen in [54] (cf. also [18]). For the analysis of the height of questors we follow similar steps to those in [29]. First, we associate to a fixed generic non-scalar straight line program Γ with exactly one output node Q_{ℓ} := Q_{ℓ,1} a regular morphism Φ that describes from the parameters (\underline{A}, \underline{B}) the polynomial it evaluates by specialization, i.e.

Φ : (\underline{A}, \underline{B}) ⟼ (Q_{ℓ}^{μ}(\underline{A}, \underline{B}))_{|μ|≤2^{ℓ}} .

We analyze this morphism following similar arguments of those in [30]. As always, L is the size of Γ , ℓ is its depth and n is the number of variables. Then, the image set Im Φ has irreducible Zariski closure that we shall denote by W (Γ) . Hence, the dimension of W (Γ) is at most 2L(L − (n + 1)) (i.e. at most the number of parameters in Γ ). Recall that the degree of an irreducible algebraic set V of dimension d is defined as the maximal cardinal of finite intersections of V with d generic linear hyperplanes. We can state now the following lemma, which is essentially [30, Lemma 1] :

Lemma 18 The irreducible algebraic set W (Γ) is 0 Q− definible and :

deg W (Γ) ≤ (2^{ℓ+1} − 2)^{2L(L−(n+1))}.

Proof.– We follow the same argument than [30, Lemma 1] : assume D := dim W (Γ) ; since W (Γ) is irreducible, there exist hyperplanes H_{1}, …, H_{D} which intersect W (Γ) in exactly deg W (Γ) points. Moreover we can assume that they intersect W (Γ) in Im Φ (cf. [51] or [26]).

Now, we observe that from the bounds on deg Q_{ℓ}^{μ} (cf. Lemma 14) it follows that Φ^{−1}(H_{1}), …, Φ^{−1}(H_{D}) are hypersurfaces of degree bounded by (2^{ℓ+1} − 2) . Define

C := {C : C is an irreducible component of Φ^{−1}(H_{1}) ∩ … ∩ Φ^{−1}(H_{D}) }

Bezout inequality of [26] implies that :

♯C ≤ ∑_{C∈C} deg C ≤ ∏_{i=1}^{D} deg Φ^{−1}(H_{i}) ≤ (2^{ℓ+1} − 2)^{D}

Finally Φ maps the elements of C onto the points of W (Γ) ∩ H_{1} ∩ … ∩ H_{D}. Therefore deg W (Γ) ≤ ♯C as wanted.

Now we are in conditions to deal with questors (correct test sequences) for polynomials.

Definition 19 Given a set F ⊂ ZZ[X_{∞}, …, X_{\}] (which contains the null polynomial) we say that a finite set Q ⊂ ZZ^{n} is a questor (or a correct test sequence) for F iff for all P ∈ F the following holds :

P |_{Q}= 0 ⟹ P ≡ 0 .

The following proposition, translated to our context from [29] is crucial for us :

Proposition 20 Under the above notations, let u := (2^{ℓ+1} −2) (2^{ℓ} +1)^{2} and t := 6L (L− (n + 1)) . Then, in \{1, …, u\}^{n} there are at least u^{nt}(1 − u^{− \frac{t}{6}} ) correct test sequences of length t for W (Γ) .

In the proof, we will make use of some results of [26] which rely on a notion of the degree of an arbitrary (non necessarily irreducible) variety introduced there, useful for our complexity purposes : the degree of a variety V , deg V , is defined as the sum of the degrees of its irreducible components.

Proof.– The proof follows the arguments of [29] : We define the algebraic subset E(Γ, t) ∈ C^{nt+N} by the conditions :

(\underline{a}_{1}, …, \underline{a}_{t}, P) ∈ E(Γ, t) ⟺ P ∈ W (Γ) and P (\underline{a}_{i}) = 0 (1 ≤ i ≤ t)

(here each \underline{a}_{t} is a point of C^{n} and we identify P with its vector of N coefficients in W (Γ) ). Therefore the algebraic set E(Γ, t) is defined by the equations defining W (Γ) and the following equations of degree 2^{ℓ} + 1 :

∑_{|μ|≤2^{ℓ}} Z_{μ}.X_{1j}^{μ_{1}} … X_{nj}^{μ_{n}} = 0 (1 ≤ j ≤ t)

From Bezout’s inequality (cf. [26]) and Lemma 18 :

deg E(Γ, t) ≤ deg W (Γ) (2^{ℓ} + 1)^{t} ≤ (2^{ℓ+1} − 2)^{\frac{t}{3}} (2^{ℓ} + 1)^{t}

Now we have the two canonical projections :

π_{1} : E(Γ, t) ⟶ C^{nt} and π_{2} : E(Γ, t) ⟶ C^{N}

Let C_{j}, j ∈ J, be all those irreducible components of E(Γ, t) such that π_{2}(C_{j}) contains some point representing a polynomial P ≢ 0 . Thus, π_{1}(∪_{j∈J}C_{j}) ⊂ C^{nt} is the set of all incorrect questors for E(Γ, t) . We can bound the cardinality of π_{1}(∪_{j∈J}C_{j}) ∩ {1, …, u}^{nt} as in [29] but with the bounds of Lemma 18. First of all, Krull dimension of π_{2}^{−1}(P) is (n − 1)t and the theorem of dimension of fibers implies that :

dim π_{2}^{−1}(P) ≥ dim C_{j} − dim W (Γ)

Therefore dim C_{j} ≤ (n − \frac{2}{3})t. Now applying [29, Prop. 2.3] we have :

♯ (π_{1}(∪C_{j}) ∩ {1, …, u}^{nt}) ≤ deg ((∪C_{j}) ∩ {1, …, u}^{nt})
≤ deg(∪C_{j})u^{(n− \frac{2}{3} )t}
≤ (2^{ℓ+1} − 2)^{\frac{t}{3}} (2^{ℓ} + 1)^{t} u^{(n− \frac{2}{3} )t}
≤ u^{nt} u^{− \frac{t}{6}}

since u := (2^{ℓ+1} − 2) (2^{ℓ} + 1)^{2} . Thus, there are u^{nt} − u^{nt} u^{− \frac{t}{6}} = u^{nt}(1 − u^{− \frac{t}{6}} ) correct test sequences of length t in {1, …, u}^{n}, which ends the proof of the statement.

Let us consider now the algebraic set W (n, ℓ, L) defined as the union of all W (Γ) , where Γ is a non-scalar straight line program of size bounded by L, depth bounded by ℓ which computes n− variate polynomials. Then, Proposition 20 above allows us to obtain the following bounds on questors for W (n, ℓ, L) :

Corollary 21 For n, ℓ, L ∈ IN , L ≥ n + 1 , let :

u := (2^{ℓ+1} − 2) (2^{ℓ} + 1)^{2}  and  t := 6 (ℓL)^{2}

Then the set \{1, …, u\}^{n} ⊂ ZZ^{n} contains at least u^{nt} (1 − u^{− \frac{t}{6}} ) correct test sequences of length t for W (n, ℓ, L) . (Therefore it contains at least one correct test sequence of this length.)

Proof.– Given n, ℓ, L we can design a non-scalar straight line program Γ_{0} that has L gates at every level, excepting for the input gates (depth 0 ) and the output gate (depth ℓ) . Then, every non-scalar straight line program of size L, depth ℓ can be modelized as a subgraph of Γ_{0} . Then, W (n, ℓ, L) is a subvariety of W (Γ_{0}) . We conclude observing that the depth of Γ_{0} is ℓ and its size is at most ℓL.

The previous bounds combined with those of Proposition 15 will allow us to determine a probabilistic polynomial time algorithm that tests whether a polynomial given by a nonscalar straight line program evaluates the zero polynomial. First of all, observe that a non-scalar straight line program of size L, depth ℓ and parameters of height η can be encoded in binary size L^{O(1)} log_{2} η. Then, we can design the following algorithm :

• Input : a non-scalar straight line program Γ

• Guess a questor set Q of {1, …, u}^{nt}, for u and t as in the Corollary above.

• For every point P ∈ Q, eval Γ at P .

• Accept if and only if Γ(P) = 0 , for all P .

This algorithm verifies the following :

Corollary 22 Let c be a fixed constant. There exists a probabilistic algorithm running in time L^{O(1)} log_{2} η^{O(1)} which decides whether a polynomial in ZZ[X_{1}, …, X_{n}] described by means of a non-scalar straight line program of size L, depth ℓ ≤ c log_{2}L and parameters η is null. The error probability of the algorithm is bounded by \frac{1}{u^{t}} , where u := (2^{ℓ+1} − 2) (2^{ℓ} + 1)^{2} and t := 6 (ℓL)^{2} . Hence the problem of deciding wheher a polynomial is null or not belongs to the bounded probability polynomial time class of complexity BPP (cf. [1, Chapter 6] for notations).

Proof.– Observe that the algorithm uses only sequences of t points in {1, …, u}^{n}. The probability that one of such guesses is a correct test sequence is at least (1 − u^{\frac{t}{6}} ) ≥ \frac{1}{2} . This simply says that the previous step describes a bounded probability Turing machine. The encoding of the input is given by the list of gates, every gate being given as a list (i, j, \underline{α}_{i,j}, \underline{β}_{i,j}) where the lists \underline{α}_{i,j}, \underline{β}_{i,j} are the parameters introduced at the gate (i, j) . Hence, simply reading the input one decides whether non-scalar straight line program has depth bounded by c log_{2} L. To evaluate the straight line program at a point P ∈ Q requires O(L^{2}) multiplications by a parameter and additions, and one multiplication by an integer number for each gate. The height of the parameters is η. The bounds of Proposition 15 imply that the precomputed integers can be encoded in binary size 2^{2ℓ}(log_{2} L+log_{2} η+log_{2} u) . Now since log_{2} u = O(ℓ) we can simulate these additions and products in sequential time 2^{O(ℓ)}(log_{2} L+log_{2} η)^{O(1)} , i.e in polynomial time in the input size L^{O(1)} log_{2} η (since ℓ = O(log_{2} L) ). Hence, the evaluation time is polynomial in the input size. Finally, the whole procedure takes polynomial time and space since the number of iterations of the previous step is bounded by t := 6 (ℓL)^{2} .

3.2 Vermeidung von Divisionen

Corollary 21 allows to apply, within our complexity bounds requirements, Strassen’s procedure of Vermeidung von Divisionen (cf. [54]) :

Proposition 23 (Strassen, 1973) Let Γ be a non-scalar straight line program of size L, depth ℓ and parameters of height η that computes {f_{0}, …, f_{m}} ⊆ ZZ[X_{1}, …, X_{n}] . Assume that f_{0} ≠ 0 and that f_{0}|f_{i} in ZZ[X_{1}, …, X_{n}] for all i, 1 ≤ i ≤ m. Then, there is a non-scalar straight line program Γ′ verifying :

i) Γ′ computes polynomials {P_{1}, …, P_{m}} in ZZ[X_{1}, …, X_{n}] and an integer θ ∈ ZZ − {0} such that

P_{i} := θ \frac{f_{i}}{f_{0}} (1 ≤ i ≤ m)

ii) Γ′ has size of order O(2^{2ℓ}(L + n + 2^{ℓ} + m)) , depth of order O(ℓ) and parameters of height max{η, u}, where u := (2^{ℓ+1} − 2)(2^{ℓ} + 1)^{2} .

In particular, we can bound the height of θ by :

| θ |≤ (L max{η, u})^{(2^{ℓ+1}−2)(2^{ℓ}+1)}

Proof.– Since the polynomial f_{0} can be evaluated by means of Γ of size L and depth ℓ, if we set u := (2^{ℓ+1} − 2) (2^{ℓ} + 1)^{2} there exists (γ_{1}, …, γ_{n}) ∈ ZZ^{n} of height bounded by u such that ρ := f_{0}(γ_{1}, …, γ_{n}) ≠ 0 (cf. Cor. 21). We define the following polynomials

F_{i}(X_{1}, …, X_{n}) := f_{i}(X_{1} + γ_{1}, …, X_{n} + γ_{n})

(such that F_{0}(0, …, 0) := f_{0}(γ_{1}, …, γ_{n}) ≠ 0) , and Q := ρ − F_{0} . The polynomials F_{0}, …, F_{m}, Q ∈ ZZ[X_{1}, …, X_{n}] , and ρ ∈ ZZ can be computed by a straight line program of size 2L + n + 1 and depth ℓ + 2 , using integer parameters of height at most max{η, u}. Finally set θ := ρ^{2^{ℓ}+1} . Thus :

\frac{θ F_{i}}{F_{0}} = \frac{θ F_{i}}{ρ − Q} = \frac{ρ^{2^{ℓ}} F_{i}}{1 − \frac{Q}{ρ}} = (∑_{k=0}^{2^{ℓ}} ρ^{2^{ℓ}−k}Q^{k} + ∑_{k=2^{ℓ+1}}^{∞} ρ^{k−2^{ℓ}}Q^{k}) F_{i}.

Since \frac{θ F_{i}}{F_{0}} is a polynomial in ZZ[X_{1}, …, X_{n}] of degree bounded by 2^{ℓ} (for f_{i} is evaluable by Γ of depth ℓ), and Q^{i} is of order at least i in 0, we can conclude that \frac{θ F_{i}}{F_{0}} depends only on the homogeneous components of degree ≤ 2^{ℓ} of (∑_{k=0}^{2^{ℓ}} ρ^{2^{ℓ}−k}Q^{k}) F_{i} (which itself belongs to ZZ[X_{1}, …, X_{n}] ). As in the proof of Proposition 9 we compute in additional size 2^{ℓ+1}+2 , depth ℓ+1 , and the same set of parameters, the powers ρ, …, ρ^{2^{ℓ}} and {Q, …, Q^{2^{ℓ}}}. Afterwards we compute the sum ∑_{k=0}^{2^{ℓ}} ρ^{2^{ℓ}−k}Q^{k} in additional size 2^{ℓ} and depth 1, and we finish multiplying the result by F_{i}. Therefore we can compute all the polynomials (∑_{k=0}^{2^{ℓ}} ρ^{2^{ℓ}−k}Q^{k}) F_{i} in total size O(L + n + m + 2^{ℓ+1}) and depth O(ℓ) , with same bounds on integer parameters. Finally, applying Lemma 13 we compute and sum all the homogeneous components of degree bounded by 2^{ℓ} of this polynomial : this can be done in size O(2^{2ℓ} (L+n+m+2^{ℓ})) , and depth O(ℓ) . We conclude the proof computing the polynomials

P_{i} := θ \frac{f_{i}}{f_{0}} = θ \frac{F_{i}(X_{1} − γ_{1}, …, X_{n} − γ_{n})}{F_{0}(X_{1} − γ_{1}, …, X_{n} − γ_{n})}

in additional size n and depth 1. The bound for |θ| is only a consequence of the bound for ρ := F_{0}(0) of Lemma 15

4 Isolated Points

In [23] the authors developped a procedure to determine the isolated points of an affine algebraic set given by a system of equations. This method is central for our purposes for two main reasons : it is primordial for the determination of a basis of a reduced complete intersection in terms of a primitive element, and it also provides sufficient polynomial conditions of good degree to check the trivility (and dimension) of an ideal. Moreover the analysis of the procedure under the scope of non-scalar straight line programs allows to obtain upper bounds for the heights of the isolated points of a variety.

For the whole section we set R := ZZ[Y_{1}, …, Y_{r}] a polynomial ring, and IK denotes an algebraic closure of the fraction field K of R. We want to describe the isolated points of an algebraic set V ⊆ IK^{n} given by polynomial equations f_{1} = 0, …, f_{s} = 0 , where f_{i} ∈ R[X_{1}, …, X_{n}] are polynomials of degree at most d. The analysis based on [23] we develop in this section will provide a primitive element, i.e. a linear form γ that distinguishes the isolated points of V (i.e. γ(P) ≠ γ(Q) for every two different isolated points P, Q ∈ V ). In the case s = n and the ideal (f_{1}, …, f_{n}) is radical of dimension r in 0 Q[Z_{1}, …, Z_{r}, X_{1}, …, X_{n}] , this linear form γ and its powers will generate the K− vector space K[X_{1}, …, X_{n}]/(f_{1}, …, f_{n}). More precisely, the main result of this section is the following :

Theorem 24 Let (f_{1}, …, f_{n}) ⊂ R[X_{1}, …, X_{n}] be a reduced complete intersection ideal generated by polynomials of degree (in \underline{X}) bounded by d ≥ n. Let V be the variety in IK^{n} defined by these polynomials. Then, there exists a linear form γ := γ_{1}X_{1} + ⋯ + γ_{n}X_{n} ∈ ZZ[X_{1}, …, X_{n}] , an element θ ∈ R, univariate polynomials v_{i} (1 ≤ i ≤ n) and p in R[Z] such that the following holds :

i) The linear form γ separates the zeros of V , and p(γ) ∈ (f_{1}, …, f_{n}) .

The minimal integral equation of γ over R is \frac{1}{α}p(Z) (where α is the leading coefficient of p).

ii) θX_{i} − v_{i}(γ) ∈ (f_{1}, …, f_{n}) (1 ≤ i ≤ n) .

iii) deg p ≤ d^{n} , deg v_{i} ≤ d^{n} (1 ≤ i ≤ n)

iv) ht(γ_{i}) = d^{O(n)} (1 ≤ i ≤ n)

v) Both θ and the coefficients of the v_{i} ’s and p are integer polynomials in the coefficients of {f_{1}, …, f_{n}} and they can be evaluated from them by a non-scalar straight line program within size of order d^{O(n)} , depth of order O(n log_{2} d) and parameters in ZZ of height bounded by d^{O(n)} .

The technical tools for the proof of this result are mainly divided in three steps. First, given a linear form γ, we need to determine an equation p which annihilates it on the isolated zeros of the variety. This is done reducing to the case where the isolated points are locally complete intersection, which is itself performed by an homotopic reduction to a projective 0− dimensional case. Next, to determine a primitive element, one generically chooses a candidate for the linear form γ, and then selects concrete parameters for the generic equations, by analyzing all posible two variables cases. Once the primitive element has been chosen, we parametrize the variables as in the Shape Lemma. Finally the minimal equation of the primitive element allows to determine completely the isolated points and the basis of the K− vector space K[X_{1}, …, X_{n}]/(f_{1}, …, f_{n}) .

4.1 The case of projective dimension zero

In this subsection we analyze dependence equations of linear forms over 0 -dimensional homogeneous ideals without zeros at infinity.

Proposition 25 Let g_{1}, …, g_{n} ⊂ R[X_{0}, …, X_{n}] be homogeneous polynomials of degree d+1 which generate an (homogeneous) ideal J ⊂ k[X_{0}, …, X_{n}] without zeros at infinity, i.e. at the projective hyperplane {X_{0} = 0} in the n -dimensional projective space over IK . Then, for every linear form γ := γ_{0}X_{0} + ⋯ + γ_{n}X_{n} (≠ X_{0}) ∈ R[X_{0}, …, X_{n}] , there exists a polynomial Δ(X_{0}, Z) ∈ R[X_{0}, Z] , monic in the variable Z (up to a constant in R), such that the following properties hold :

i) Δ(X_{0}, γ) ∈ J .

ii) deg Δ(X_{0}, Z) ≤ (d + 1)^{n}.

iii) The coefficients of Δ(X_{0}, Z) are integer polynomials in the coefficients of {g_{1}, …, g_{n}} of degree of order O(n^{n} d^{3n}) , and in the coefficients of γ of degree of order O(d^{n}) .

iv) The coefficients of Δ(X_{0}, Z) can be computed from the coefficients of g_{i} ’s and γ by a non-scalar straight line program of size of order (nd)^{O(n)} , depth at most O(n (log_{2} n + log_{2} d)) and parameters in {−1, 0, 1} ⊆ ZZ .

v) The polynomial Δ(X_{0}, Z) can be computed by a non-scalar straight line program of the same characteristics.

Proof.– In [23] the authors apply the results of [40] or [9] in order to be in a context where Cayley-Hamilton theorem holds. Applying for example [40] we observe that the graded IK− algebra

A := IK[X_{0}, …, X_{n}]/J = A_{0} + A_{1} + ... + A_{s} + ...

satisfies the following two facts :

• its Hilbert regularity is bounded by N := n(d + 1) + 1 − n = nd + 1 . This says that for all s ≥ N the IK -vector spaces A_{s} are isomorphic, of rank D bounded by their degree, which are themselves bounded by (d + 1)^{n}.

• The fact that the ideal J doesn’t define any point at the hyperplane X_{0} = 0 implies that for all s ≥ N the homothesy induced by X_{0}

η_{X_{0}} : A_{s} ⟶ A_{s+1}

is an isomorphism.

Thus, the linear mapping

φ := (η_{X_{0}} )^{−1}η_{γ} : A_{N} ⟶ A_{N}

is an endomorphism of the IK -vector space A_{N} , and Cayley-Hamilton theorem implies that its characteristic polynomial P (T) is a non–zero polynomial which annihilates him, i.e. P (φ) = η_{P ( \frac{γ}{X_{O}} )} vanishes, and so does ηD_{X_{0}} P (φ) .

As X_{0} is not a zero–divisor in A, the non–zero polynomial Q(X_{0}, Z) := X_{0}^{D}P (\frac{Z}{X_{0}} ) verifies that Q(X_{0}, γ) vanishes in A (and Q(X_{0}, Z) is monic in Z up to a constant of K). Essentially we only need now to compute the polynomial Q(X_{0}, Z) = det(X_{0}M_{φ} − Z Id) by means of the matrix M_{φ} in a basis B of A_{N} . In fact, we will compute a slightly different polynomial Δ(X_{0}, Z) with the same property, but in R[X_{0}, Z] , i.e. without denominators. For this purpose, we will compute monomial bases B and B′ of A_{N} and A_{N+1} respectively, and the matrices M_{X_{0}} and M_{γ} of the homothesies η_{X_{0}} and η_{γ} in these bases. In order to get the bases B and B′ let us denote by F_{s} := {m_{1}, …, m_{r_{s}}} the set of all mononomials of degree s in the variables X_{0}, …, X_{n} (where r_{s} := \binom{s+n}{n}). We construct first a matrix P ∈ M_{n r_{(N−d−1)}×r_{N}} (R) of relations of the monomials in F_{N} modulo J_{N} (the relations are obtained multiplying the monomials of degree N − (d + 1) by the polynomials g_{i} ’s, thus the entries of the matrix correspond to coefficients of the g_{i} ’s). If we triangularize P in K, we obtain a matrix \overline{P} which allows to extract a subfamily B := {e_{1}, …, e_{D}} ⊂ F_{N} which is a monomial basis of A_{N} (given by the “parameter” columns in the triangularization). In fact, we observe that it is enough to compute a square submatrix of maximal rank of P : the basis will be determined by the remainder columns. Similarly, we compute a square submatrix of maximal rank \overline{Q} of the matrix Q of relations in A_{N+1} . In this way we extract a monomial basis B′ := {e′_{1}, …, e′_{D}} ⊂ F_{N+1} of A_{N+1} , and its remainder set {v′_{1}, …, v′_{t}} := F_{N+1} \ B′. Moreover, we obtain an element λ := det \overline{Q} ∈ R and a matrix B ∈ M_{t×D}(R) (given by the remainder columns of Adj(\overline{Q}) Q) such that

λ ( v′_{1} ; ⋮ ; v′_{t} ) = B ( e′_{1} ; ⋮ ; e′_{D} ) .

The bases B and B′ and the matrix B are obtained by computing first the matrices of relations, and then a square submatrix of maximal rank : we choose first a maximal number of independent rows computing their rank, in nr_{N−d} steps and applications of Berkowitz algorithm (Proposition 9), using for instance that in our case rk( A)=rk( A.^{t}A) and computing its characteristic polynomial; afterwards we proceed with the columns. We compute the element λ and the matrices M_{λX_{0}}, M_{λγ} also applying Proposition 9. Now we are able to describe the matrix M_{λX_{0}} = λM_{X_{0}} : for every e_{i} ∈ B, λX_{0}e_{k} ∈ A_{N+1} is either a monomial of the form λe′_{j} or a monomial λv′_{k}. In the first case the corresponding column of λM_{X_{0}} is a vector with all coordinates equal to zero excepting one where λ occurs. In the second case, this column is simply a row of the matrix B. (Note that M_{λX_{0}} ∈ M_{D}(R) .) Analogously, we obtain the matrix M_{λγ} = ∑_{i=0}^{n} γ_{i}λM_{X_{i}} ∈ M_{D}(R) .

Now, instead of computing Q(X_{0}, Z) = det(X_{0}M_{φ} − Z Id) = det(X_{0}(M_{X_{0}})^{−1}M_{γ} − Z Id) , it would be enough to compute the polynomial λ^{D} det(M_{λX_{0}})Q(X_{0}, Z) = det(X_{0}M_{λγ} − ZM_{λX_{0}}) ∈ R[X_{0}, Z] which verifies all what we need ( Δ ≠ 0 since M_{X_{0}} is invertible, and Δ(X_{0}, γ) ∈ J holds). However, as we are interested in computing the coefficients of this polynomial (and not only the whole polynomial) we need to view it as a characteristic polynomial. That’s why we will compute a multiple of it :

Δ(X_{0}, Z) = det(M_{λX_{0}})^{D−1} det(X_{0}M_{λγ} − ZM_{λX_{0}}) ∈ R[X_{0}, Z]

which has the same properties. We shall in fact compute the characteristic polynomial X of the matrix Adj(M_{λX_{0}})M_{λγ}, since if X := ∑ p_{j}Y^{j}, then Δ(X_{0}, Z) = ∑ p_{j}det(M_{λX_{0}})^{j}Z^{j}X_{0}^{D−j}. (Note that : Δ(X_{0}, Z) = det(X_{0}Adj(M_{λX_{0}})M_{λγ} − det(M_{λX_{0}})Z Id).) The bound for deg Δ is clear from the size of the matrices involved. Also λ and det(M_{λX_{0}}) are integer polynomials in the entries of Q and B, i.e. the coefficients of the g_{i} ’s, of degree ≤ r_{N} ≤ e(N + n)^{n}, and the same occurs with the entries of B. So that the degree of the coefficients of Δ in the coefficients of g_{i} are of order O(D r_{N}) . (For the bound in the coefficients of γ observe that these appear only linearly in M_{λγ}.) The bounds for the straight line program are clear since we only apply a controlled number of repetitions of Proposition 9.

4.2 As many equations as unknowns

Proposition 25 above allows us to consider the case were isolated points are locally complete intersections, i.e. as many equations as unknowns : the method relies on reducing the given polynomials f_{1}, …, f_{n} to the zero-dimensional projective case by homothopy techniques. These techniques are classical in numerical analysis (cf. [19]) and were also used in computer algebra in [13], [25] or [23].

Lemma 26 Let f_{1}, …, f_{n} ⊂ R[X_{1}, …, X_{n}] be polynomials of degree d ≥ n, and let γ ∈ R[X_{1}, …, X_{n}] be a (non–zero) linear form. Then, there exists a polynomial p ∈ R[Z] , monic in the variable Z (up to a constant in R), such that the following properties hold :

i) p(γ) vanishes on the isolated points in IK^{n} of {f_{1} = 0, …, f_{n} = 0}.

ii) deg p(Z) ≤ (d + 1)^{n}.

iii) The coefficients of p(Z) are integer polynomials in the coefficients of {f_{1}, …, f_{n}} of degree of order d^{O(n)} , and in the coefficients of γ of order O(d^{n}) .

iv) The coefficients of p(Z) are evaluated from the coefficients of the f_{i} ’s and γ by a non-scalar straight line program Γ of size d^{O(n)} , depth O(n log_{2} d) and parameters in {−1, 0, 1}.

Proof.– We follow here the arguments of [23, Section 3].

Let {F_{1}, …, F_{n}} be the homogenizations of the polynomials {f_{1}, …, f_{n}} with respect to the variable X_{0} . We introduce a new variable ε that we further use either as parameter or as variable, and we define the following polynomials in R[ε, X_{0}, X_{1}, …, X_{n}] :

g_{i} := X_{0} F_{i} + ε X_{i}^{1+deg f_{i}} (1 ≤ i ≤ n)

These polynomials are homogeneous of degree d + 1 as polynomials in IK(ε)[X_{0}, …, X_{n}] . Let IK_{ε} be the algebraic closure of IK(ε) . In these conditions, it is well–known that the ideal (g_{1}, …, g_{n}) ⊂ IK_{ε}[X_{0}, …, X_{n}] is a zero-dimensional ideal without zeros at infinity in IP_{n}(IK_{ε}) (see for instance [23, Section 3.3] for a geometrical proof). Applying Lemma 25 above for the (homogeneous) linear form γ we can compute the coefficients (p_{0}, …, p_{D}) of the polynomial

Δ(X_{0}, Z) = ∑_{j=1}^{D} p_{j}(ε)Z^{j}X_{0}^{D−j} ∈ R[ε][X_{0}, Z]

by means of an adequate non-scalar straight line program (as the straight line program contains no divisions, it is clear that p_{j}(ε) are polynomials in ε). Reducing Δ(X_{0}, Z) dividing it by the greatest common power of ε of its content, we define

Δ′(ε, X_{0}, Z) := ∑_{j=1}^{D} p′_{j}(ε)Z^{j}X_{0}^{D−j}

In [23, Proposition 3.3.4] it is shown that the polynomial

p(Z) := Δ_{1}(0, 1, Z) := ∑_{j=1}^{D} p′_{j}(0)Z^{j}

is the desired polynomial, and assertion i) is proved. Assertions ii) and iii) follow directly from the construction of the polynomial p. From a non-scalar straight line program that evaluates a polynomial q := a_{k}ε^{k} +…+a_{n}ε^{n} (n ≥ k, a_{k} ≠ 0) one can easily describe a (division-free) non-scalar straight line program that evaluates the polynomial q′ := a_{k} + … + a_{n}ε^{n−k}, within similar bounds for height, depth and height of the parameters. This shows assertion iv) and concludes the proof.

4.3 Separating points of two univariate polynomials

We need to introduce here some few notations : Let T_{1}, …, T_{n} be new variables. For each i, 1 ≤ i ≤ n, we define the ring

R_{i} := R[T_{1}, …, T_{i−1}, T_{i+1}, …, T_{n}].

We denote by K_{i} its quotient field and by IK_{i} an algebraic closure of it. We also denote by K_{T} the quotient field of the ring R[T_{1}, …, T_{n}] and by IK_{T} an algebraic closure of it.

Lemma 27 Let p ∈ R_{i}[Z] be a non-constant polynomial of degree (in Z) bounded by D, whose coefficients in R_{i} are of degree bounded by δ, and let q ∈ R[Z] be a non–zero polynomial of degree bounded also by D. For every t := (t_{1}, …, t_{n}) ∈ IK^{n} define the algebraic set

V_{t} := {(x, y) ∈ IK^{2} : q(x) = 0, p_{t}(y) = 0}

(where p_{t} denotes to specialize in the coefficients of p the variables T by t). Then there exists a non–zero polynomial F (T_{1}, …, T_{n}) ∈ R[T_{1}, …, T_{n}] of degree bounded by δ D^{O(1)} such that F (t_{1}, …, t_{n}) ≠ 0 implies that the linear form t_{i}X + Y separates the points of V_{t}. (If the coefficients of p and q in the polynomial ring R are also of degree bounded by δ, the degrees of the coefficients of F in R are of the same order.)

Proof.– We are looking for a polynomial F ∈ R[T_{1}, …, T_{n}] such that for all t ∈ IK^{n} the conditions F (t) ≠ 0, q(x_{1}) = q(x_{2}) = 0, p_{t}(y_{1}) = p_{t}(y_{2}) = 0 imply that t_{i}x_{1} + y_{1} ≠ t_{i}x_{2} + y_{2} . For this purpose we introduce the new variables X_{1}, X_{2}, Y_{1}, Y_{2} and the ideals I_{1} := (q(X_{1}), q(X_{2})) , I_{2} := (p(Y_{1}), p(Y_{2})) in K_{T} [X_{1}, X_{2}] and K_{T} [Y_{1}, Y_{2}] respectively. Let α ∈ R and β ∈ R_{i} ⊆ R_{T} be the respective leading coefficients of q and p. We now consider the homothesies :

η_{α(X_{1}−X_{2})} : K_{T} [X_{1}, X_{2}]/I_{1} ⟶ K_{T} [X_{1}, X_{2}]/I_{1}
η_{β(Y_{1}−Y_{2})} : K_{T} [Y_{1}, Y_{2}]/I_{2} ⟶ K_{T} [Y_{1}, Y_{2}]/I_{2}

The matrices of the homothesies η_{α(X_{1}−X_{2})} and η_{β(Y_{1}−Y_{2})} in the natural monomial bases of both residue rings are of order M bounded by D^{2} and their coordinates are given respectively by coefficients of q and p. We compute the characteristic polynomials of both homothesies :

H(Z_{1}) := X_{α(X_{1}−X_{2})} = Z_{1}^{M} + a_{M−1}Z_{1}^{M−1} + ⋯ + a_{m}Z_{1}^{m} ∈ R[Z_{1}] (a_{m} ≠ 0)
G(Z_{2}) := X_{β(Y_{1}−Y_{2})} = Z_{2}^{M} + b_{M−1}Z_{2}^{M−1} + ⋯ + b_{m′}Z_{2}^{m′} ∈ R_{i}[Z_{2}] (b_{m′} ≠ 0)

(Observe that the coefficients of G are polynomials in T of degree bounded by δD^{2} , and that the same bounds arise for the coefficients of H and G if R is a polynomial ring and the coefficients in R of p and q are also of degree bounded by δ.) The case m = M , i.e. the homothesy η_{α(X_{1}−X_{2})} is nilpotent, means that q(x_{1}) = q(x_{2}) ⟹ x_{1} = x_{2} , and we can obviously take F := 1 (since q(x_{1}) = q(x_{2}) = 0, p_{t}(y_{1}) = p_{t}(y_{2}) = 0 and t_{i}x_{1} + y_{1} = t_{i}x_{2} + y_{2} would imply (x_{1}, y_{1}) = (x_{2}, y_{2}) ). Analogously, in the case m′ = M , the polynomial F = T_{i} is the obvious solution. Thus, we shall assume m, m′ < M ≤ D^{2} and we define :

H′(Z_{1}) := \frac{H(Z_{1})}{Z_{1}^{m}}  ,  G′(Z_{2}) := \frac{G(Z_{2})}{Z_{2}^{m′}}

and the non-trivial ideal J := (H′, G′) they define in K_{T} [Z_{1}, Z_{2}] . The matrices of the homothesies η_{Z_{1}} and η_{Z_{2}} in the natural monomial basis of the residue ring K_{T} [Z_{1}, Z_{2}]/J are of order ≤ D^{4} and their coefficients are easy to determine : for instance the matrix of η_{Z_{1}} is constituted of M −m′ diagonal blocks, each of one being the (invertible) compagnion matrix of H′. The matrix of η_{Z_{2}} is the same modulo a change of order in the basis. Then, they belong to R_{i} and have degree at most δD^{2} . (If we are interested in the degrees of these coefficients as polynomials in R, the bound which appears is 2δD^{2} .) Finally we consider the matrix M_{T_{i}Z_{1}+Z_{2}} of the homothesy η_{(T_{i}Z_{1}+Z_{2})} in the same basis : its coordinates are polynomials in R[T_{1}, …, T_{n}] of degree bounded by δD^{2} + 1 ( 2δD^{2} + 1 taking into account the degrees in R), and we define :

F (T_{1}, …, T_{n}) := β T_{i} det(M_{T_{i}Z_{1}+Z_{2}})

which is a non–zero polynomial since the coefficient of T_{i}^{1} corresponds essentially to the determinant of the matrix of η_{Z_{2}} , which is invertible. We claim that this polynomial verifies the required conditions : The condition det(M_{t_{i}Z_{1}+Z_{2}}) ≠ 0 implies that the linear form t_{i}Z_{1} + Z_{2} is not a zero divisor in the zero dimensional residue ring IK_{t}[Z_{1}, Z_{2}]/J_{t}, and thus doesn’t belong to any prime (= maximal) ideal associated to J_{t}. On the other hand, if (x_{1}, y_{1}) ≠ (x_{2}, y_{2}) ∈ V_{t}, then q(x_{1}) = q(x_{2}) = 0, p_{t}(y_{1}) = p_{t}(y_{2}) = 0 , and therefore, as H(η_{α(X_{1}−X_{2})}) = 0, G(η_{β(t)(Y_{1}−Y_{2})}) = 0 in the residue rings and α ≠ 0, β(t) ≠ 0 , we can conclude that H(x_{1} − x_{2}) = G(y_{1} − y_{2}) = 0 (with x_{1} − x_{2} ≠ 0 or y_{1} − y_{2} ≠ 0 ). If x_{1} = x_{2} or y_{1} = y_{2} , as t_{i} ≠ 0 it is clear that t_{i}x_{1} + y_{1} ≠ t_{i}x_{2} + y_{2} . Otherwise, H′(x_{1} − x_{2}) = 0 and G′(y_{1} − y_{2}) = 0 , which finally implies that t_{i}(x_{1} − x_{2}) + (y_{1} − y_{2}) ≠ 0 (since (x_{1} − x_{2}, y_{1} − y_{2}) determines a maximal prime of J_{t}).

4.4 The case of two variables

We are going to present here an effective “straight line program” version of the well-known “shape lemma” for a particular case in two variables we will use in the sequel. We recall here its proof only because we need to take care of the growing of the coefficients when we perform this change of basis.

Lemma 28 Let p(Y), q(X) be two univariate squarefree polynomials with coefficients in R, and denote by J := (p(Y), q(X)) ⊂ K[X, Y] the ideal they generate. Set D := deg p. deg q. Let γ := Y + αX ( α ∈ ZZ fixed) be a linear form which separates the zeros of J in IK^{2} . Then there exist two univariate polynomials u, v ∈ R[Z] and a non–zero element θ ∈ R such that :

i) J = (u(γ), θX − v(γ)) ⊂ K[X, γ] .

ii) deg(u) = D.

iii) deg(v) ≤ D − 1

iv) The coefficients of u are polynomials in the coefficients of p and q of degree bounded by 4D; θ and the coefficients of v are polynomials in the coefficients of q and p of degrees bounded by 2D^{2} . v) The coefficients of u are evaluable by a non-scalar straight line program with inputs

the coefficients of p and q of size O(D^{12}) and non-scalar depth 6 log_{2} D+12 , using {−1, 0, 1, α} as set of parameters.

vi) θ and the coefficients of v are evaluable by a non-scalar straight line program with the same inputs of size O(D^{10}) , depth 6 log_{2} D+11 and the same set of parameters.

Proof.– The ideal J is a radical zero-dimensional ideal which defines D := deg p. deg q isolated points. Also the K− vector space K[X, Y]/J admits the basis

B := {X^{i}Y^{j} : 0 ≤ i < deg q, 0 ≤ j < deg p}.

Since J is a radical ideal and the linear form γ separates all the zeros of J , it is easy to verify that the minimal polynomial of γ in K[X, Y]/J over K coincides with the characteristic polynomial X_{γ} of the homothesy η_{γ} induced by γ, so that γ is a primitive element of the K− extension K[X, Y]/J (which defines the basis 1, γ, …, γ^{D−1} ). Now, in order to avoid denominators in K, we shall compute a slightly different characteristic polynomial u : let α and β denote the leading coefficients of q and p respectively, and set ρ := α β. We define :

u(Z) := ρ^{D}X_{γ}(Z) = det(M_{ργ} − ρZId) = det(αM_{βY} + αβM_{αX} − αβZId)

(where M_{∗} denotes the matrix of the homothesy induced by ∗ in the basis B). It is immediate that u ∈ R[Z] is a polynomial of degree D such that u(γ) ∈ J (since u(η_{γ}) = η_{u(γ)} = 0 , and we can apply it to the first element of the basis, 1). Moreover, the coefficients of u are polynomials in the coefficients of q and p of degree 4D. Finally, in order to compute θ ∈ R and v ∈ R[γ] such that J = (u(γ), θX − v(γ)) ∈ k[X, γ] , we observe that there exists an invertible matrix P ∈ M_{D}(R) verifying :

( 1 ; ργ ; ⋮ ; (ργ)^{D−1} ) = P ( 1 ; X ; ⋮ ; X^{deg q−1}Y^{deg p−1} ) .

Therefore, (det P)X = v(γ) (mod J) , where v is a polynomial of degree bounded by D − 1 which comes from a row of the matrix Adj(P) . We set θ := det P . Observing that the matrix P can be obtained as the first columns of the matrices (M_{ργ})^{k}, 0 ≤ k < D, it is clear that θ and the coefficients of v are polynomials in the coefficients of q and p of degree 2D^{2} . Now, since the ideal (u(γ), θX − v(γ)) is a radical ideal contained in the radical zerodimensional ideal I ⊂ K[X, γ] which defines exactly the same points, we conclude that modulo the linear change of variables, J = (u(γ), θX − v(γ)) . Now we are going to produce the straight line program required in items 5 and 6. We will compute the coefficients of u by means of the coefficients of the characteristic polynomial of the matrix M_{ργ} in the basis B (if X_{ργ}(Z) = ∑ a_{k}Z^{k}, then u(Z) = ∑(ρ^{k}a_{k})Z^{k}). First we compute the coordinates of the matrix M_{ργ} by means of a straight line program of length O(D^{2}) and depth 2, using α ∈ ZZ as a parameter. Then Berkowitz algorithm gives a straight line program of length O(D^{5}) and depth O(log_{2} D) to compute the coefficients of u, with the same parameter. In order to produce a straight line program which computes θ and the coefficients of v, we need to compute the matrix P , i.e. the powers of the matrix M_{ργ}. This can be done in length O(D^{4}) and depth O(log_{2} D) . Afterwards we compute Adj(P) (given by minors of the matrix P ) and det P in length O(D^{6}) and depth O(log_{2} D) .

4.5 Describing the isolated zeros of n n-variate polynomials

Now we are in conditions to show the following result, which describes the isolated zeros of a variety in the case where there are as many equations as unknowns.

Proposition 29 Let f_{1}, …, f_{n} ∈ R[X_{1}, …, X_{n}] be polynomials of degree (in \underline{X}) bounded by d ≥ n. Let V ∈ IK^{n} denote the variety defined by these polynomials. Then there exists a linear form γ := γ_{1}X_{1} + ⋯ + γ_{n}X_{n} ∈ ZZ[X_{1}, …, X_{n}] , an element θ ∈ R and univariate polynomials v_{i} ∈ R[Z] (1 ≤ i ≤ n) such that the following holds :

i) The linear form γ separates the isolated zeros of V .

ii) The coordinates x := (x_{1}, …, x_{n}) of the isolated zeros of V verify the equations : θx_{i} = v_{i}(γ(x)) (1 ≤ i ≤ n) .

iii) deg v_{i} = d^{O(n)} (1 ≤ i ≤ n)

iv) ht(γ_{i}) = d^{O(n)} (1 ≤ i ≤ n)

v) Both θ and the coefficients of the v_{i} ’s are integer polynomials in the coefficients of {f_{1}, …, f_{n}} of degree bounded by d^{O(n)} and they can be evaluated from them by a non-scalar straight line program within size of order d^{O(n)} , depth of order O(n log_{2} d) and parameters in ZZ of height bounded by d^{O(n)} .

Proof.– We consider the generic elements Y := T_{1}X_{1} + … + T_{n}X_{n} and Y_{i} := Y − T_{i}X_{i} (1 ≤ i ≤ n) in the ring R[T_{1}, …, T_{n}][X_{1}, …, X_{n}] . Applying Lemma 26 above to the linear forms Y_{i}, X_{i} (1 ≤ i ≤ n) we can find nonconstant polynomials p_{i} ∈ R_{i}[Z], q_{i} ∈ R[Z] (1 ≤ i ≤ n) of degree O(d^{n}) such that p_{i}(Y_{i}), q_{i}(X_{i}) vanish on the isolated zeros of the system f_{1} = 0, …, f_{n} = 0 in IK_{T}^{n} . Also the coefficients of p_{i} are integer polynomials in T_{1}, …, T_{n} of degree O(d^{n}) , and in the coefficients of f_{1}, …, f_{n} of degree d^{O(n)} . Fix i, 1 ≤ i ≤ n : by Lemma 27 applied to p_{i}(Y_{i}), q_{i}(X_{i}) there exists a non–zero polynomial F_{i} ∈ R[T_{1}, …, T_{n}] of degree bounded by d^{O(n)} such that F_{i}(t_{1}, …, t_{n}) ≠ 0 implies that the linear form Y_{i} + t_{i}X_{i} := t_{1}X_{1} + … + t_{n}X_{n} separates the solutions of {p_{i}(t, y_{i}) = 0, q_{i}(x_{i}) = 0}. The non–zero polynomial F := ∏_{i=1}^{n} F_{i} ∈ R[T_{1}, …, T_{n}] is of degree bounded by d^{O(n)} . An adequate specialization of the variables of the polynomial ring R allows to obtain a non-zero polynomial F^{∗} ∈ ZZ[T_{1}, …, T_{n}] , of degree of the same order, which thus can be evaluated by means of a straight line program over ZZ of depth O(n log_{2} d) . Corollary 21 implies that there exists (γ_{1}, …, γ_{n}) ∈ ZZ^{n} of height of order d^{O(n)} such that F^{∗}(γ_{1}, …, γ_{n}) ≠ 0 , and therefore F (γ_{1}, …, γ_{n}) ≠ 0 as wanted.

We conclude that the linear form γ := γ_{1}X_{1} + … + γ_{n}X_{n} separates the solutions in IK^{2} of the n systems :

p_{i}(γ_{1}, …, γ_{n}, Y_{i}) = 0 , q_{i}(X_{i}) = 0 (1 ≤ i ≤ n)

and in particular separates the isolated zeros of the system {f_{1} = 0, …, f_{n} = 0} in IK^{n}. Recall that the polynomials p_{i}(Y_{i}), q_{i}(X_{i}) are polynomials in the coefficients of f_{1}, …, f_{n} and in T_{1}, …, T_{n} of degree d^{O(n)} , which can be computed from them by a non-scalar straight line program of size d^{O(n)} , depth O(n log_{2} d) and parameters in {−1, 0, 1, γ_{1}, …, γ_{n}}. To reduce them as in Lemma 12 in order to obtain the squarefree polynomials p_{i}^{∗}, q_{i}^{∗} doesn’t modify essentially size, depth and parameters. Finally we apply Lemma 28 to J := (p_{i}^{∗}(γ_{1}, …, γ_{n}, Y_{i}), q_{i}^{∗}(X_{i})) ∈ IK^{2} and the linear form Y_{i} +γ_{i}X_{i} to compute θ_{i} ∈ R and the coefficients of v′_{i} ∈ R[Z] such that θ_{i}X_{i} −v′_{i}(γ) ∈ J , i.e. vanish on the isolated zeros of f_{1}, …, f_{n}. We conclude the proof setting θ := ∏_{i=1}^{n} θ_{i} and v_{i} := (∏_{j≠i} θ_{j})v′_{i}.

4.6 The primitive element for a reduced complete intersection

The previous proposition is the key to obtain the main result of this section, Theorem 24, that we state again for the commodity of the reader :

Theorem 24 Let (f_{1}, …, f_{n}) ⊂ R[X_{1}, …, X_{n}] be a reduced complete intersection ideal generated by polynomials of degree (in \underline{X}) bounded by d ≥ n. Let V be the variety in IK^{n} defined by these polynomials. Then there exists a linear form γ := γ_{1}X_{1} + ⋯ + γ_{n}X_{n} ∈ ZZ[X_{1}, …, X_{n}] , an element θ ∈ R, univariate polynomials v_{i} (1 ≤ i ≤ n) and p in R[Z] such that the following holds :

i) The linear form γ separates the zeros of V , and p(γ) ∈ (f_{1}, …, f_{n}) .

The minimal integral equation of γ over R is \frac{1}{α}p(Z) (where α is the leading coefficient of p).

ii) θX_{i} − v_{i}(γ) ∈ (f_{1}, …, f_{n}) (1 ≤ i ≤ n) .

iii) deg p ≤ d^{n} , deg v_{i} ≤ d^{n} (1 ≤ i ≤ n)

iv) ht(γ_{i}) = d^{O(n)} (1 ≤ i ≤ n)

v) Both θ and the coefficients of the v_{i} ’s and p are integer polynomials in the coefficients of {f_{1}, …, f_{n}} and they can be evaluated from them by a non-scalar straight line program within size of order d^{O(n)} , depth of order O(n log_{2} d) and parameters in ZZ of height bounded by d^{O(n)} .

Proof.– We apply Proposition 29 to compute the element θ ∈ R and the polynomials v_{i} ∈ R[Z] : since by hypothesis the ideal J := (f_{1}, …, f_{n}) is radical, we have θ X_{i}−v_{i}(γ) ∈ J , and that deg v_{i} ≤ deg V ≤ d^{n}.

Moreover, defining

F_{i}(Z) := θ^{d}f_{i}(\frac{1}{θ}v_{1}(Z), …, \frac{1}{θ}v_{n}(Z))

we observe that F_{i}(γ) ≡ f_{i}(X_{1}, …, X_{n}) (mod J) (1 ≤ i ≤ n) . Now consider a greatest common divisor p ∈ R[Z] of F_{1}, …, F_{n} and let us see that p verifies the required conditions : The polynomial p is (a non–zero scalar multiple of) the minimal polynomial of γ modulo J , and coincides with the characteristic polynomial of the homothesy η_{γ} since both polynomials have the same degree (for J is a zero-dimensional radical ideal and γ separates its points). Therefore Bezout’s inequality (cf. [26]) implies that deg p ≤ d^{n}. This shows items 1 and 3. We are going now to compute such a polynomial p. First we will compute the coefficients of the F_{i} ’s from the coefficients of f_{1}, …, f_{n}. (In fact we will compute slightly different polynomials G_{i} in order to keep all the operations in R.) Fix i, and suppose

f_{i} := ∑_{|μ|≤d} a_{μ}X_{1}^{μ_{1}} … X_{n}^{μ_{n}} (1 ≤ i ≤ n)

then :

F_{i}(Z) := ∑_{0≤j≤δ} a_{j}X^{j} = ∑_{|μ|≤d} θ^{d−|μ|}a_{μ}v_{1}(Z)^{μ_{1}} … v_{n}(Z)^{μ_{n}}.

As deg v_{j} = d^{O(n)} (1 ≤ j ≤ n) we observe that δ := deg F_{i} = d^{O(n)} also (in fact we can take d^{3n}). Now we interpolate in {0, …, δ} by means of a Vandermonde matrix A to evaluate the coefficients of F_{i} :

( \begin{matrix}1 & 0 & 0 & … & 0 \\ 1 & 1 & 1 & … & 1 \\ 1 & 2 & 2^{2} & … & 2^{δ} \\ ⋮ & ⋮ & ⋮ & … & ⋮ \\ 1 & δ & δ^{2} & … & δ^{δ} \end{matrix} ) ( a_{0} ; a_{1} ; a_{2} ; ⋮ ; a_{δ} ) = ( F_{i}(0) ; F_{i}(1) ; F_{i}(2) ; ⋮ ; F_{i}(δ) )

We define G_{i} := (det A)F_{i} and we compute the coefficients of G_{i} by means of the adjoint matrix of A. This can be done for all i, 1 ≤ i ≤ n, in size d^{O(n)} , depth O(n log_{d}) and parameters of height of order d^{O(n)} (compute first the entries of A, det A and Adj(A) , simultaneously evaluate θ^{j} and v_{j}(0)^{k}, …, v_{j}(δ)^{k} to finally compute F_{i}^{∗}). We conclude computing as in Lemma 11 a greatest common divisor p of G_{1}, …, G_{s}.

4.7 Height of isolated points of affine varieties

We are now in conditions to show the bounds for the height of the isolated points of an affine algebraic variety V := {f_{1} = 0, …, f_{s} = 0} ⊆ C^{n}, where the polynomials f_{i} ∈ ZZ[X_{1}, …, X_{n}] have degree and height bounded by d and η respectively.

Corollary 6 Let f_{1}, …, f_{r} (r ≤ n) and g be polynomials in ZZ[X_{1}, …, X_{n}] of degree and height bounded by d ≥ n and η respectively, and let V denote the algebraic affine variety of C^{n} defined by :

V := {f_{1} = 0, …, f_{s} = 0}

Then V has at most d^{n} isolated points whose heights verify :

log_{2} ht(P) ≤ d^{O(n)}(log_{2} s + log_{2} η)

Proof.– First of all following the same analysis of [26], it is posible to find non-negative integers λ_{i j} of height at most d^{n}, such that the isolated points of V are some of the isolated points of the algebraic set W determined by the equations :

{ F_{1}(X_{1}, …, X_{n}) := λ_{1 1}f_{1}(X_{1}, …, X_{n}) + ⋯ + λ_{1 s}f_{s}(X_{1}, …, X_{n}) ; ⋮ ; F_{n}(X_{1}, …, X_{n}) := λ_{n 1}f_{1}(X_{1}, …, X_{n}) + ⋯ + λ_{n s}f_{s}(X_{1}, …, X_{n})

The isolated points of W are a locally complete intersection so there exist polynomials q_{i}(X_{i}) of degree bounded by d^{n} such that for every such an isolated point P = (x_{1}, …, x_{n}) ∈ W q_{i}(x_{i}) = 0 holds. These polynomials q_{i} have integer coefficients, which can be obtained by means of a non-scalar straight line program of size sd^{O(n)} , depth O(n log_{2} d) and parameters of height d^{n} in the coefficients of the f_{i} ’s. Thus, we conclude that for each i :

ht(q_{i}) = (s η)^{d^{O(n)}}

Now let K be an algebraic number field and M_{K} a proper set of absolute values over K. As in [38] the height of an affine point P := (x_{1}, …, x_{n}) ∈ K^{n} is defined in terms of the projective point (y_{0} : …: y_{n}) = (1 : x_{1} : …: x_{n}) ∈ P_{n}(K) :

ht(P) := ∏_{ν∈M_{K}} sup_{i} ∥y_{i}∥_{ν}

We have the following inequalities :

ht(P) ≤ ∏_{ν∈M_{K}} sup_{i} max{1, ∥x_{i}∥_{ν}}

≤ ∏_{i=1}^{n} ∏_{ν∈M_{K}} max{1, ∥x_{i}∥_{ν}}

As observed in [38] the last term is exactly the measure of the minimal polynomial of x_{i} over the integers. Since the measure of univariate polynomials is a multiplicative function, combining with Landau’s inequality (cf. [37]) we have :

ht(P) ≤ ∏_{i=1}^{n} M(q_{i}) ≤ ∏_{i=1}^{n} ∥q_{i}∥_{2} ≤ ∏_{i=1}^{n} d^{n}ht(q_{i})

Therefore

log_{2} ht(P) = d^{O(n)}(log_{2} s + log_{2} η)

as desired (and in our conditions there are at most d^{n} isolated points P ).

4.8 Triviality test based on isolated points

As in [23, Théorème 3.5] one can design a probabilistic procedure that tests whether an ideal (f_{1}, …, f_{s}) is the trivial ideal in 0 Q[X_{1}, …, X_{n}] . In fact the algorithm determines the dimension of the variety V = {f_{1} = 0, …, f_{s} = 0}. The method is based on the following fact : if the algebraic set V has dimension r, there are generic linear forms γ_{1}, …, γ_{r} such that the variety V_{r} given by :

V_{r} = {f_{1} = 0, …, f_{r} = 0, γ_{1} = 0, …, γ_{r} = 0}

is of dimension 0 and r is maximal with this property. The procedure of [23] is based on the following scheme :

• Guess non–deterministically a list Q of t = d^{O(n)}s^{O(1)} non–negative integers of ZZ^{n(n+1)+n} of height at most d^{O(n)} log_{2} s^{O(1)} (as in Corollary 21). This guess Q will be a candidate for a questor set in all steps of the procedure.

• For all 1 ≤ r ≤ n, introduce an r × (n + 1) matrix of variables M = (T_{i j}) and the

linear mappings :

γ_{i} := T_{i 1}X_{i} + ⋯ + T_{i n}X_{n} + T_{i n+1}

• Next introduce a new list S_{1}, …, S_{n} of variables the polynomials F_{i} of [22], defined as :

F_{i} : = f_{1} + S_{i} f_{2} + S_{i}^{2} f_{3} + ⋯ + S_{i}^{s−1} f_{s} + S_{i}^{s} γ_{1} + ⋯ + S_{i}^{s+r−1} γ_{r}

• Choose concrete values in Q and determine concrete polynomials F_{1}, …, F_{n}. For each selection, let W_{r} be the algebraic subset of C^{n} given by F_{1} = 0, …, F_{n} = 0 . The isolated points of V_{r} are isolated points of some of the W_{r} because this property holds generically (cf. [23]).

• For the same selection of constants, applying Proposition 29, we can obtain a linear form γ that separates the isolated points of W_{r} (if there is any). Moreover, we can obtain polynomials p, v_{1}, …, v_{n} and a constant θ, evaluable by non-scalar straight line programs as in Proposition 29, such that p(γ) and θX_{i} − v_{i}(γ) vanishes on the isolated points of W_{r}.

• Finally, for the polynomials f_{1}, …, f_{s}, γ_{1}, …, γ_{r} we can substitute the variables X_{i} by \frac{1}{θ}v_{i}(γ) and, multiplying by the accurate power of θ, we obtain some univariate polynomials p(Z), G_{1}(Z), …, G_{s}(Z), L_{1}(Z), …, L_{r}(Z) . The solutions of the equations they define determine the isolated points of V_{r}.

• If for every choice in Q, the gcd of the polynomials p(Z) , G_{i} ’s and L_{i} ’s is 1 and if Q is a correct test sequence, we conclude that V_{r} contains no isolated point.

• Computing the maximal r such that V_{r} contains isolated points, we obtain the dimension of V and, in particular, we know whether V is empty or not.

This procedure tests non–zero equality (and hence requires evaluation) of non-scalar straight line programs of size sd^{O(n)} , depth O(n log_{2} d + log_{2} s) and uses parameters in Q of controlled height. The evaluation can be simulated by a Turing machine as in Corollary 22. The correct acceptation depends on the quality of Q as questor set. Again by Corollary 21, we can conclude :

Corollary 30 There is a bounded error probablistic Turing machine which decides whether an ideal described by generators f_{1}, …, f_{s} ∈ ZZ[X_{1}, …, X_{n}] of degree d and height η is trivial or not in time s^{O(1)}d^{O(n)} log_{2} η^{O(1)} . The error probability is bounded by \frac{1}{u^{t/6}} , where u = d^{O(n)} and t = d^{O(n)} . Hence the problem of deciding the triviality of such an ideal belongs to the bounded probability polynomial time class of complexity BPP (cf. [1, Chapter 6] for notations).

5 Division in Reduced Complete Intersections

In this section we state a crucial step for the description and computation of the wanted output polynomials in the Effective Nullstellensatz and the Membership Problem : a division theorem which considers the problem of computing the quotient of a division in a ring which is a reduced complete intersection. This quotient will be technically the result of the action of a matrix whose entries can be computed by a non-scalar straight line program of appropriate size, depth and parameters. The computation of this matrix instead of the computation of the concrete quotient will be essential for us in order to obtain the right heights for the output polynomials in the two mentionned results. The main ingredient for the division theorem is a duality technique based on the existence of traces for Gorenstein algebras.

5.1 Notations and assumptions

Throughout this section we shall maintain the following notations and assumptions :

• n and r are non-negative integers with 1 ≤ r ≤ n, R := ZZ[X_{1}, …, X_{n−r}] , A := 0 Q[X_{1}, …, X_{n−r}] and K := 0 Q(X_{1}, …, X_{n−r}) .

• f_{1}, …, f_{r} are polynomials in ZZ[X_{1}, …, X_{n}] of degree and height bounded by d ≥ n and η rspectively, which define a reduced complete intersection ideal J in 0 Q[X_{1}, …, X_{n}] , and such that the following extension is integral

0 Q[X_{1}, …, X_{n−r}] ↪ B := 0 Q[X_{1}, …, X_{n}]/J

• B denotes the factor ring 0 Q[X_{1}, …, X_{n}]/J . For any polynomial h ∈ 0 Q[X_{1}, …, X_{n}] we denote by \overline{h} its class in B; also deg^{o}h will be its degree in the free variables X_{1}, …, X_{n−r} and deg^{∗}h its degree in the variables X_{n−r+1}, …, X_{n}.

Let us observe that under these assumptions K ⊗_{A} B is a reduced 0–dimensional K – algebra.

5.2 The division theorem

Theorem 31 Under the assumptions 5.1, let f, g ∈ ZZ[X_{1}, …, X_{n}] , deg f ≤ d, ht(f) ≤ η, be polynomials such that \overline{f} is not a zero divisor and that \overline{f} | \overline{g} in B. Then there exist a polynomial q ∈ R[X_{n−r+1}, …, X_{n}] and an element ξ ∈ R such that :

i) ξg ≡ qf (mod J) and ξ|q in 0 Q[X_{1}, …, X_{n}] .

ii) deg^{∗}q ≤ r (d − 1) .

iii) max{deg^{o}q, deg^{o}ξ} = deg^{o}g + (1 + deg^{∗}g)d^{O(r)}

iv) max{log_{2} ht(q), log_{2} ht(ξ)} = d^{O(r)} deg g^{O}(1) max{log_{2} η, log_{2}(ht(g))}.

This result will be an inmediate consequence of the more technical following result :

Lemma 32 Under the assumptions 5.1, let f, g ∈ ZZ[X_{1}, …, X_{n}] , deg f ≤ d, be polynomials such that \overline{f} is not a zero divisor and that \overline{f} | \overline{g} in B. Then there exist a matrix Q with coefficients in R and an element ξ ∈ R such that if q ∈ R[X_{n−r+1}, …, X_{n}] denotes the polynomial whose coefficients are obtained applying Q to the coefficients of g (in adequate bases of monomials) :

i) ξg ≡ qf (mod J) and ξ|q in 0 Q[X_{1}, …, X_{n}] .

ii) deg^{∗}q ≤ r (d − 1)

iii) The coefficients of Q and ξ are integer polynomials in the coefficients in R of f_{1}, …, f_{r} and f and can be computed from them by a non-scalar straight line program of size d^{O(r)} + O(deg^{∗}g) , depth O(r log_{2} d + log_{2}(deg^{∗}g)) and parameters in ZZ of height bounded by d^{O(r)} .

The proof of this result is mainly inspired on the developments of [18]. Technically, we represent the polynomials by the matrix of the homothesies (or multiplication) they define on the K− vector space K⊗_{A}B. Then, instead of computing the matrix of a trace through the computation of a dual basis as in [18], we perform the division procedure by means of adjoint matrices and polynomials as in [48, Lemmas 9 and 15].

of multiplication is a consequence of the computation of a basis of K ⊗_{A} B, in terms of a primitive element chosen as in Section 4. Moreover, the equations defining the primitive element are essential to compute this matrix of multiplication. The computation of the trace in this Gorenstein algebra will be done by computing a pseudo–jacobian determinant (the element of the duality) as in [35, Example F.19 and Corollary F.10]. We begin by recalling the basic facts on trace theory we need. (We thank [48] from where we textually borrowed main part of Paragraph 5.3 below.)

5.3 Basic general trace theory

The definition of the trace. We consider the ring B as an A -algebra and we denote by B^{∗} the dual space Hom_{A}(B, A) . The A -module B^{∗} admits a natural structure of B -module in the following way : for any pair (b, β) in B × B^{∗} the product b.β is the A -linear application of B^{∗} defined by (b.β)(x) := β(bx) , for each x in B. Our assumptions about A and B allow to show that the B -modules B and B^{∗} are isomorphic (see [35, Example F.19 and Corollary F.10]) and therefore B^{∗} can be generated by a single element. A generator σ of B^{∗} is called a trace of B over A. Under our hypothesis we have the additional property that B is a finite free A -module whose rank will be denoted by D (cf. [24]). Fix for the moment a basis of this module; each element b ∈ B defines, by multiplication, a square matrix M_{b} ∈ A^{D×D}. If we denote by trace (M_{b}) the trace of the matrix M_{b}, the application b ↦ trace(M_{b}) defines (independently of the basis of B) an element of B^{∗} called the usual trace and denoted by Tr . Unfortunately the usual trace is not always a generator of B^{∗} (in other words the usual trace is not necessarily a trace).

The trace associated to a regular sequence. Let us consider now the ring B ⊗_{A} B which is both an A− algebra and a B− bialgebra (with right and left multiplications). Let μ : B ⊗_{A} B → B be the morphism of A -algebras (or B -bialgebras) defined by μ(b ⊗ b′) := bb′. Denote by K the kernel of μ. It is easy to show that K is the ideal generated by all the elements b ⊗ 1 − 1 ⊗ b, where b ranges over B (see for example [32, Proposition 1.3]). From the fact that Ann_{B⊗_{A}B}(K)(b ⊗ 1 − 1 ⊗ b) = 0 for all b ∈ B, one infers that the induced structures of right and left B -modules over Ann_{B⊗_{A}B}(K) coincide. In other words, if ∑_{i} b_{i} ⊗ b′_{i} belongs to Ann_{B⊗_{A}B}(K) and b is an element of the ring B we have : ∑_{i} bb_{i} ⊗ b′_{i} = ∑_{i} b_{i} ⊗ bb′_{i}. Moreover it is possible to show that Ann_{B⊗_{A}B}(K) is a cyclic B -module ([35, Corollary F.10]). Let us consider the application Φ : B ⊗_{A} B → Hom_{A}(B^{∗}, B) defined by

Φ(∑_{i} b_{i} ⊗ b′_{i})(β) := ∑_{i} b_{i} β(b′_{i}),

where b_{i}, b′_{i} ∈ B and β ∈ B^{∗}. Since B is free as A− module, Φ is an isomorphism that identifies Ann_{B⊗_{A}B}(K) and Hom_{B}(B^{∗}, B) . For each generator Δ := ∑_{m} a_{m} ⊗ b_{m} of the B -module Ann_{B⊗_{A}B}(K) the element Φ(Δ) is a generator of Hom_{B}(B^{∗}, B) and then there exists a uniquely determinated σ_{Δ} ∈ B^{∗} such that Φ(Δ)(σ_{Δ}) = 1 . One deduces immediately that σ_{Δ} is a trace for B (which is called the trace associated to Δ ). From the definitions of Φ, Δ and σ_{Δ} we have the following “trace formula” for all b ∈ B :

b = ∑_{1≤m≤M} σ_{Δ}(b b_{m}) a_{m}.  (7)

In particular, we observe that a_{1}, …, a_{M} is a system of generators of the A -module B. By means of the element Δ it is possible to obtain a relation between the trace σ_{Δ} and the “usual trace” Tr; more precisely (see [35, Corollary F.12]) :

μ(Δ).σ_{Δ} = Tr  (8)

In terms of elements of B this formula says that for all b ∈ B the equality σ_{Δ}(μ(Δ)b) = Tr(b) holds. In the case of reduced complete intersections rings B, there is a classical procedure to determine an element Δ generating Ann_{B⊗_{A}B}(K) as B− module. This method, known by Jacobi, can also be seen in [35, Corollary E.19 and Example F.19] :

Now let us introduce new variables Y_{n−r+1}, …, Y_{n}. For every polynomial f ∈ 0 Q[X_{1}, …, X_{n}] we consider the polynomial f^{(Y)} obtained by replacing the variables X_{j} by Y_{j} for n − r + 1 ≤ j ≤ n. Hence, we have the canonical isomorphism of A -algebras :

B ⊗_{A} B ≅ A[X_{n−r+1}, …, X_{n}, Y_{n−r+1}, …, Y_{n}]/(f_{1}, …, f_{r}, f_{1}^{(Y)}, …, f_{r}^{(Y)})  (9)

The polynomials f^{(Y)} − f belong to the ideal (Y_{j} − X_{j}, n − r + 1 ≤ j ≤ n) . Then there exist polynomials l_{ij} such that the following equalities hold for 1 ≤ i ≤ r :

f_{i}^{(Y)} − f_{i} := ∑_{1≤j≤r} l_{ij} . (Y_{n−r+j} − X_{n−r+j})  (10)

Since both sequences are regular of the same length (and maximal) the class of the jacobian determinant Δ = det(l_{ij}) in B ⊗_{A} B generates Ann_{B⊗_{A}B}(K) by means of the identification (9). This jacobian (or pseudo–jacobian) determinant can be easily computed in terms of nonscalar straight line programs. First of all the polynomials l_{ij} can be computed in the following way :

f_{i}^{(Y)} − f_{i} := ∑_{j=n−r+1}^{n} (f_{i}(X_{1}, …, X_{j−1}, Y_{j}, …, Y_{n}) − f_{i}(X_{1}, …, X_{j}, Y_{j+1}, …, Y_{n})) ,

therefore

l_{ij} = (f_{i}(X_{1}, …, X_{j−1}, Y_{j}, …, Y_{n}) − f_{i}(X_{1}, …, X_{j}, Y_{j+1}, …, Y_{n})) /(Y_{j} − X_{j}).

Thus, setting

f_{i} := ∑_{|μ|≤d} a_{iμ}X_{1}^{μ_{1}} ⋯ X_{n}^{μ_{n}}

we conclude that for all 1 ≤ i ≤ r and n − r + 1 ≤ j ≤ n :

l_{ij} = ∑_{|μ|≤d} a_{iμ}X_{1}^{μ_{1}} … X_{j−1}^{μ_{j−1}}Y_{j+1}^{μ_{j+1}} … Y_{n}^{μ_{n}} (\frac{Y_{j}^{μ_{j}} − X_{j}^{μ_{j}}}{Y_{j} − X_{j}} )

= ∑_{|μ|≤d} (a_{iμ}X_{1}^{μ_{1}} … X_{j−1}^{μ_{j−1}}Y_{j+1}^{μ_{j+1}} … Y_{n}^{μ_{n}} . ∑_{k=0}^{μ_{j}−1} Y_{j}^{k}X_{j}^{(μ_{j}−1)−k})

(which defines a non-scalar straight line program of size d^{O(r)} , depth O(r log_{2} d) and parameters in {−1, 0, 1}).

We conclude computing the polynomial Δ = det(l_{ij}) ∈ R[X_{n−r+1}, …, X_{n}, Y_{n−r+1}, …, Y_{n}] by means of Berkowitz algorithm (Proposition 9). The polynomial Δ , of degree r(d − 1) , is then computable by means of a non-scalar straight line program of size d^{O(r)} , depth O(log_{2} d) using only the coefficients of the f_{i} ’s as parameters.

Finally interpolation allows us to compute the coefficients α_{μ} in R of Δ :

Lemma 33 There is a non-scalar straight line program Γ which computes from the coefficients of f_{1}, …, f_{r} an element α ∈ ZZ \ \{0\} and α′_{μ} ∈ R such that α_{μ} = \frac{α′_{μ}}{α} (and α|α′_{μ} in R). The size of Γ is of order d^{O(r)} , its depth of order ℓ(Γ) = O(r log_{2} d) and the parameters introduced in Γ are of height bounded by d^{O(1)} .

In other words, we have (see also [18, §3.4]) :

Proposition 34 There exist polynomials a_{m}, b_{m} (1 ≤ M ≤ (r d)^{2r}) in ZZ[X_{1}, …, X_{n}] satisfying deg(a_{m}) + deg(b_{m}) ≤ r(d − 1) ( 1 ≤ m ≤ M ) such that ∑_{m} \overline{a}_{m} ⊗ \overline{b}_{m} is a generator of Ann_{B⊗_{A}B}(K) and \overline{Δ} = ∑_{m} \overline{a}_{m} \overline{b}_{m} . The coefficients of a_{m} are integer polynomials in the coefficients of the f_{i} ’s and can be computed from them by a straight line program of size d^{O(r)} , depth O(r log_{2} d) and parameters of height d^{O(1)} . The polynomials b_{m} are simply monomials X_{n−r+1}^{μ_{n−r+1}} … X_{n}^{μ_{n}}.

Proof.– If det(l_{ij}) = ∑ α_{μ}X_{n−r+1}^{μ_{n−r+1}} … X_{n}^{μ_{n}}Y_{n−r+1}^{μ′_{n−r+1}} … Y_{n}^{μ′_{n}} we write

a_{μ} := αα_{μ}X_{n−r+1}^{μ_{n−r+1}} … X_{n}^{μ_{n}}  and  b_{μ} := X_{n−r+1}^{μ′_{n−r+1}} … X_{n}^{μ′_{n}}

(where α comes from the previous lemma).

Definition 35 The trace associated to the generator of Ann_{B⊗_{A}B}(K) introduced in Proposition 34 will be called the trace associated to the regular sequence f_{1}, …, f_{r} and we will denote it by σ_{Δ} or by σ if there is no ambiguity.

Let us observe that in this case relation (8) gives

\overline{Δ}.σ = Tr  (11)

5.4 Computing matrices of homothesies

Under Assumptions 5.1 and from Theorem 24 we can assume that are given :

• A linear form γ := γ_{n−r+1}X_{n−r+1} +…+γ_{n}X_{n} ∈ ZZ[X_{n−r+1}, …, X_{n}] of height d^{O(r)} such that \overline{γ} is a primitive element of the zero-dimensional K− algebra K ⊗_{A} B of rank D ≤ d^{r} (thus B := \{1, …, \overline{γ}^{D−1}\} is a basis of K ⊗_{A} B).

• A polynomial p ∈ R[Z] of degree D − 1 ≤ d^{r} such that p(γ) ∈ J

• Elements θ ∈ R and v_{j} ∈ R[Z] (n − r + 1 ≤ j ≤ n) of degree bounded by d^{r} such that θX_{j} − v_{j}(γ) ∈ J (n − r + 1 ≤ j ≤ n) .

• The degrees of p, θ and v_{j} (n − r + 1 ≤ j ≤ n) in the variables X_{1}, …, X_{n−r} is bounded by d^{O(r)} .

Under these conditions, we have

Lemma 36 Set τ := α^{D}θ, where α is the leading coefficient of p. There is a non-scalar straight line program which computes from the coefficients of p and v_{j} (n − r + 1 ≤ j ≤ n) and from θ the coordinates (in R) of the matrices M_{τγ} and M_{τX_{j}} (n − r + 1 ≤ j ≤ n) . The straight line program has size of order d^{O(r)} , depth O(r log_{2} d) and parameters {−1, 0, 1}.

Proof.– Observe that the matrix M_{αγ} has coordinates in R given by the coefficients of p. From M_{αγ} we can compute :

M_{τX_{j}} = α^{D}M_{θX_{j}} = α^{D}v_{j}(\frac{1}{α}M_{αγ}).

To do this, set v_{j} := ∑_{k=0}^{D} b_{jk}Z^{k} and define V_{j} := ∑_{k=0}^{D}(α^{D−k}b_{jk})Z^{k}. Then, we have :

M_{τX_{j}} = V_{j}(M_{αγ})

To compute the powers {1, α, …, α^{D}} requires size D + 1 and depth log_{2} D + 1 . Simultaneously we can compute the matrix M_{αγ} adding size O(D^{2}) . In additional depth 1 and size r(D + 1) + 1 we compute the products α^{D−k}b_{jk} and τ . Next in size O(D^{4}) and depth log_{2} D + 2 , we compute all powers {M_{αγ}^{k} : k = 0, …, D}. For every j, n − r + 1 ≤ j ≤ n, we compute in additional size O(D^{3}) and non-scalar depth 2 the matrix v_{j}(M_{αγ}) , which implies a total size O(r D^{3}) = d^{O(r)} and the same depth.

This lemma allows us to compute the matrix M_{h} for any polynomial h ∈ R[X_{n−r+1}, …, X_{n}] . It is crucial for us to observe here that if deg^{∗}h is fixed, then the computation of M_{h} is linear in the coefficients of h :

Lemma 37 Under the same assumptions of Lemma 36, let h ∈ R[X_{n−r+1}, …, X_{n}] and let N := deg^{∗}h and τ := α^{D}θ (where α is the leading coefficient of p). Then, there is a non-scalar straight line program which computes from the coefficients of h, p, v_{j} (n−r+1 ≤ j ≤ n) and from θ the coefficients of the matrix M_{τ^{N} h}. The straight line program has size d^{O(r)} + O(deg^{∗}h) , depth O(r log_{2} d + log_{2}(deg^{∗}h)) and parameters {−1, 0, 1} in ZZ .

Proof.– Set h := ∑_{|μ|≤N} a_{μ}X_{n−r+1}^{μ_{n−r+1}} … X_{n}^{μ_{n}}. Then

M_{τ^{N} h} := ∑_{|μ|≤N} a_{μ} τ^{N−|μ|} M_{τX_{n−r+1}}^{μ_{n−r+1}} … M_{τX_{n}}^{μ_{n}}

The bounds for the size and depth of the straight line program which design the coordinates of the matrix M_{τ^{N} h} are then straightforward.

Let us recall now that we have a trace σ associated to the regular sequence f_{1}, …, f_{r} (which is a generator of the B− module B^{∗}) such that for all h ∈ B, σ(Δh) = Tr(h) holds.

Proof of Lemma 32.– The condition that f is not a zero-divisor in B implies that if X_{f} := T^{D} + α_{D−1}T^{D−1} + … + α_{0} ∈ A[T] is the characteristic polynomial of the homothesy η_{f} (which belongs effectively to A[T] , see [48, Corollary 2]) then α_{0} = (−1)^{D} det η_{f} is a non-zero element of A. Therefore, if we define

f^{∗} := f^{D−1} + α_{D−1}f^{D−2} + … + α_{2}f + α_{1}.

we observe that \overline{f} \overline{f^{∗}} = (−1)^{D+1}α_{0} in B. Now, the condition \overline{f}|\overline{g} in B implies there exists q_{1} ∈ 0 Q[X_{1}, …, X_{n}] such that g ≡ q_{1} f (mod J) , and therefore g f^{∗} ≡ (−1)^{D+1}α_{0}q_{1} (mod J) . We would like to define simply q := f^{∗} g and ξ = (−1)^{D+1}α_{0} but unfortunately this definition doesn’t agree with our requirements on degrees and with the fact that everything must belong to ZZ[X_{1}, …, X_{n}] . However we are going to keep essentially this idea in mind and to use the trace formula to reduce the degree of q : From Formula 7, f^{∗} g = ∑_{1≤m≤M} σ(f^{∗} g b_{m}) a_{m} and from Relation 11, \overline{Δ} σ = Tr , therefore if we define Δ^{∗} analogously as f^{∗}, we have :

(Δ^{∗}Δ)f^{∗} g = ∑_{1≤m≤M} Tr(Δ^{∗}f^{∗} g b_{m}) a_{m}

Now we need to multiply all polynomials by factors in R in order to keep all the computations in R[X_{n−r+1}, …, X_{n}] . Let N be a bound for deg^{∗}f , deg^{∗}Δ , deg^{∗}b_{m} and deg^{∗}g, and set f′ := τ^{N}f , Δ′ := τ^{N}Δ , g′ := τ^{N}g and b′_{m} := τ^{N}b_{m} (recall that τ is defined as in Lemma 36). Observe that :

– M_{f′}, M_{Δ′}, M_{g′}, and M_{b′_{m}} have their coefficients in R

– f′^{∗} = τ^{N (D−1)}f^{∗} and M_{f′}^{∗} = (−1)^{D+1}Adj(M_{f′}) (analogously for Δ′). We define :

q := ∑_{1≤m≤M} Tr(Δ′^{∗}f′^{∗} g′ b′_{m}) a_{m} = ∑_{1≤m≤M} Tr(Adj(M_{Δ′})Adj(M_{f′}) M_{g′} M_{b′}_{m}) a_{m}

and

ξ := (Δ′^{∗}Δ′)(f′^{∗}f′) = det M_{Δ′} det M_{f′}

The bound on deg^{∗}q is then clear from the definition. The matrix Q appears from the fact that if deg^{∗}g is fixed the coefficients of M_{g′} are linear (and uniform) in the coefficients of g (see Proposition above) and so do the coefficients of Adj(M_{Δ′})Adj(M_{f′}) M_{g′} M_{b′}_{m}; we conclude observing that the trace is also linear and combining with the coefficients of the a_{m} ’s.

Finally it is clear that ξ | q in 0 Q[X_{1}, …, X_{n}] since g′ ≡ q_{1}f′ (mod J) implies that

Tr(Δ′^{∗}f′^{∗} g′ b′_{m}) = Tr(Δ′^{∗}f′^{∗} f′ q_{1} b′_{m})
= f′^{∗} f′σ(Δ′Δ′^{∗}q_{1}b′_{m})
= (Δ^{′∗}Δ′)(f′^{∗} f′)σ(q_{1}b′_{m})

(where all equalities are true polynomial equalities since every term belongs to A and A ∩ I = J = (0) ).

Proof of Theorem 31.– From the straight line program which computes ξ and the matrix Q in R from the coefficients of f_{1}, …, f_{r} and f we construct a straight line program which evaluates ξ and q from the variables X_{1}, …, X_{n} simply using as parameters the coefficients of f_{1}, …, f_{r}, f, g as follows : We precompute the coefficients in R of f_{1}, …, f_{r}, f (which are of degree bounded by d) and of g (of degree deg^{o}g) in size O(d^{n−r}+deg^{o}g^{n−r}) , non-scalar depth max{log_{2} d, log_{2}(deg^{o}g)} and parameters max{η, ht(g)}. We also precompute all powers X_{n−r+1}^{α_{n−r+1}} … X_{n}^{α_{n}} with |α| ≤ deg^{∗}q. Then we multiply the coefficients of the matrix Q by the coefficients in R of g and at the end combine the result with the corresponding powers of X_{n−r+1}, …, X_{n} computed above. We conclude applying Proposition 15.

6 Preparation of the Input Data

This section is devoted to two preprocessing techniques : Bertini’s theorem and Noether normalization.

6.1 Bertini’s theorem.

An essential technique used to prepare our polynomials is given by Bertini’s theorem. Let f_{1}, …, f_{r} ∈ ZZ[X_{1}, …, X_{n}] . We shall analyze two cases :

i) The ideal (f_{1}, …, f_{r}) is the trivial ideal in 0 Q[X_{1}, …, X_{n}] ( r arbitrary).

ii) r ≤ n and (f_{1}, …, f_{r}) is a proper ideal of dimension n − r.

For the first case we can make as in [26] or [12] a reduction to at most n + 1 equations but having some additional properties :

Lemma 38 (see also [48, Proposition 18] and [15, Proposition 1.2]) Let f_{1}, …, f_{r} be polynomials with integer coefficients, of degree bounded by d, such that 1 ∈ (f_{1}, …, f_{r}) in 0 Q[X_{1}, …, X_{n}] . Then there exist t ≤ n and an integer matrix :

Q = ( \begin{matrix}λ_{1 1} & ⋯ & λ_{1 r} \\ ⋮ & & ⋮ \\ λ_{t+1 1} & ⋯ & λ_{t+1 r} \end{matrix} )

such that if f′_{i} := λ_{i 1}f_{1} + ⋯ + λ_{i r}f_{r} (1 ≤ i ≤ t + 1) , the following properties hold :

• 1 ∈ (f′_{1}, …, f′_{t+1}) .

• f′_{1}, …, f′_{j−1}, f′_{j+1}, …, f′_{t+1} is a regular sequence for all index j, 1 ≤ j ≤ t + 1 .

• ht(Q) ≤ (d + 1)^{n}.

Proof.– We proceed inductively constructing polynomials {f′_{1}, …, f′_{k}} such that :

• Either (f′_{1}, …, f′_{k}) = (1) or dim (f′_{1}, …, f′_{k}) = n − k.

• For all S := {j_{1}, …, j_{s}} ⊂ {1, …, k} of cardinal strictly less than k, the ideal J_{S} := (f′_{j_{1}}, …, f′_{j_{s}}) has dimension n − s (we suppose here j_{1} < j_{2} < … < j_{s}).

• The linear combinations f′_{1}, …, f′_{k} are obtained using parameters of height bounded by (d + 1)^{n}.

For k = 1 , either some of the f_{i} ’s is a unit in 0 Q or we take f′_{1} := f_{1} . Suppose now that f′_{1}, …, f′_{k} are constructed. If they verify that 1 ∈ (f′_{1}, …, f′_{k}) we conclude t := k − 1 . Otherwise for every S ⊆ {1, …, k}, the variety V_{S} ∈ C^{n} defined by the ideal J_{S} := (f′_{j}, j ∈ S) is equidimensional. Denote by C_{S} the set of all irreducible components of V_{S}, and for every C ∈ C_{S} choose a point x_{C} ∈ C. Now let us define the polynomial :

F (T_{1}, …, T_{r}) := ∏_{S⊆{1,...,k}} ∏_{C∈C_{S}}(T_{1}f_{1}(x_{C}) + ⋯ + T_{r}f_{r}(x_{C}))

Since 1 ∈ (f_{1}, …, f_{r}) , Bezout inequality implies that F is a non–zero polynomial of degree at most (d + 1)^{k}. Thus there exist non–negative integers λ_{1}, …, λ_{r} of absolute height at most (d + 1)^{k} such that F (λ_{1}, …, λ_{r}) ≠ 0 . We define f′_{k+1} := λ_{1}f_{1} + ⋯ + λ_{r}f_{r}. By construction, f′_{k+1} is not a zero divisor modulo J_{S}, for all S ⊆ {1, …, k}. We have the two following possibilities :

• 1 ∉ (f′_{1}, …, f′_{k+1}) : in this case the ideals J_{S} + (f′_{k+1}) are all proper ideals of dimension n − ♯(S) (and (f′_{1}, …, f′_{k}) is of dimension n − k by hypothesis) and we continue with our inductive procedure.

• 1 ∈ (f′_{1}, …, f′_{k+1}) . Then there exists S of minimal cardinality t such that 1 ∈ J_{S} + (f′_{k+1}) .

The ideal J_{S} + (f′_{k+1}) verifies our requirements.

Therefore both cases (i) and (ii) can be reduced to the following Proposition :

Proposition 39 Let f_{1}, …, f_{r} ∈ ZZ[X_{1}, …, X_{n}] (r ≤ n + 1) be polynomials of degree bounded by d ≥ n such that one of the two following conditions is satisfied :

• 1 ∈ (f_{1}, …, f_{r}) and f_{1}, …, f_{j−1}, f_{j+1}, …, f_{r} is a regular sequence for all j, 1 ≤ j ≤ r.

• r ≤ n and (f_{1}, …, f_{r}) is an ideal of dimension n − r.

Then there exists a matrix Q ∈ M_{(r−1)×r}(ZZ) of height d^{O(n)} such that the polynomials :

( f′_{1} ; ⋮ ; f′_{r−1} ) = Q ( f_{1} ; ⋮ ; f_{r} )

verify :

i) (f′_{1}, …, f′_{r−1}, f_{r}) = (f_{1}, …, f_{r})

ii) f′_{1}, …, f′_{r−1} is a regular sequence.

iii) For all k, 1 ≤ k ≤ r − 1 , (f′_{1}, …, f′_{k}) defines a radical ideal in 0 Q[X_{1}, …, X_{n}] .

Proof.– For all j, 1 ≤ j ≤ r, we define

U_{j} := {x ∈ C^{r} : f_{j}(x) ≠ 0}

and the morphism :

\begin{aligned}Φ_{j} : & U_{j} & ⟶ & C^{r−1} \\ & x & ⟼ & (\frac{f_{1}(x)}{f_{j}(x)}, …, \frac{f_{j−1}(x)}{f_{j}(x)}, \frac{f_{j+1}(x)}{f_{j}(x)}, …, \frac{f_{r}(x)}{f_{j}(x)}) \end{aligned}

If (f_{1}, …, f_{r}) is a proper ideal of dimension n − r, it is shown in [36] that {f_{1}, …, f_{r}} is an independent set in C[X_{1}, …, X_{n}] and there is no nonzero homogeneous polynomial F ∈ C[Y_{1}, …, Y_{r}] such that F (f_{1}, …, f_{r}) = 0 . This simply implies that Im(Φ_{j}) is a constructible subset of C^{r−1} of dimension r − 1 . On the other hand, if f_{1}, …, f_{r} verifies the first condition, for every j (1 ≤ j ≤ r) the ideal (f_{1}, …, f_{j−1}, f_{j+1}, …, f_{r}) has dimension n−(r−1) and f_{j} is not a zero divisor over it. This implies that the sequence f_{1}, …, f_{j−1}, f_{j+1}, …, f_{r} defines an ideal of dimension n − (r − 1) in C[U_{j}] := C[X_{1}, …, X_{n}]_{f_{j}} . Now, applying the Theorem on the dimension of the Fibers to Φ_{j} we can conclude that the image Im(Φ_{j}) is a constructible subset of C^{r−1} of dimension r − 1 . Therefore in both cases the morphisms Φ_{j} are dominant and we can apply Bertini’s Theorem in the characteristic zero case (cf. [33, corollary 6.7]). Thus there is a Zariski open subset in the space of matrices Q = (λ_{i j}) ∈ M_{(r−1)×r}(C) such that

{ f′_{1} := λ_{1 1}f_{1} + ⋯ + λ_{1 r}f_{r} ; ⋮ ; f′_{r−1} := λ_{r−1 1}f_{1} + ⋯ + λ_{r−1 r}f_{r}

verify that for all j, 1 ≤ j ≤ r, (f′_{1}, …, f′_{r−1}) is a regular sequence which defines a radical ideal in C[U_{j}] (moreover, the same assertion is true for (f′_{1}, …, f′_{k}) for all k, 1 ≤ k ≤ r − 1 ). We now intersect this Zariski open set of matrices with the (r − 1) open sets defined by the following polynomial conditions :

det(λ_{i j})_{1≤i,j≤k} ≠ 0 (1 ≤ k ≤ r − 1)

We claim that f′_{1}, …, f′_{r−1} verify the desired conditions :

(i) The condition on the determinant of order r − 1 implies that (f_{1}, …, f_{r−1}, f_{r}) = (f′_{1}, …, f′_{r−1}, f_{r}) . (ii) We will show that f′_{1}, …, f′_{r−1} is a regular sequence by induction :

– f′_{1} ≠ 0 .

– 1 < k ≤ r−2 : (f′_{1}, …, f′_{k−1}) is a regular sequence by hypothesis. Let (f′_{1}, …, f′_{k−1}) = ⋂ Q_{t} be the primary decomposition of the ideal (where for all t, dim Q_{t} = n − (k − 1) by the hypothesis of regularity). Now suppose that f′_{1}, …, f′_{k} is not a regular sequence : thus f′_{k} is either a zero-divisor modulo (f′_{1}, …, f′_{k−1}) or the ideal (f′_{1}, …, f′_{k}) is the trivial one. The second case cannot hold since the extension of this ideal to every localization C[U_{j}] is a proper ideal. This means that there exists a prime ideal P associated to (f′_{1}, …, f′_{k−1}) such that f′_{k} ∈ P. Therefore there should exist an index j ≥ k+1 such that f_{j} ∉ P since otherwise P would contain the ideal (f′_{1}, …, f′_{k}, f_{k+1}, …, f_{r}) ; and by the hypothesis on the determinant of order k, this would imply that (f_{1}, …, f_{r}) ⊂ P. This leads to the contradiction n − (k − 1) = dim P ≤ dim (f_{1}, …, f_{r}) = n − r or − 1 . Finally let j ≥ k+1 be such that f_{j} ∉ P : the extension of the ideal P to the localization C[U_{j} is therefore also an associated prime ideal of (f′_{1}, …, f′_{k−1}) ⊂ C[U_{j}] , and this implies that f′_{k} ∈ P is a zero-divisor in C[U_{j}]/(f′_{1}, …, f′_{k−1}) which contradicts the fact that f′_{1}, …, f′_{k} is a regular sequence in C[U_{j}] . We conclude that f′_{1}, …, f′_{k} must be a regular sequence. (iii) Now let us verify that (f′_{1}, …, f′_{k}) is a radical ideal, 1 ≤ k ≤ r − 1 : Suppose that g ∈ rad(f′_{1}, …, f′_{k}) , i.e. there exists N such that g^{N} ∈ (f′_{1}, …, f′_{k}) . We can view this property in C[U_{k+1}], …, C[U_{r}] , where it is a radical ideal, i.e. for M big enough, g f_{k+1}^{M}, …, g f_{r}^{M} ∈ (f′_{1}, …, f′_{k}) . Now if g ∉ (f′_{1}, …, f′_{k}) , it means that f_{k+1}, …, f_{r} belong all to the same prime ideal P associated to (f′_{1}, …, f′_{k}) , and we conclude as before.

Now, we are going to see how to determine the integers λ_{i j} ∈ ZZ of the matrix Q. Let us introduce some new variables T_{i j}, 1 ≤ i ≤ r − 1, 1 ≤ j ≤ r, and consider the polynomial ring R := ZZ[T_{i j}] , its quotient field K and an algebraic closure IK . Since Bertini holds generically, the polynomials in R[X_{1}, …, X_{n}] defined as

F_{i} := T_{i 1}f_{1} + ⋯ + T_{i r}f_{r} (1 ≤ i ≤ r − 1)

verify that for every 1 ≤ k ≤ r − 1 the ideal (F_{1}, …, F_{k}) is smooth of dimension n − k in K[X_{1}, …, X_{n}]_{f_{j}} for all 1 ≤ j ≤ r, and the same result is true for almost every specialization T_{i j} ⟶ λ_{i j}. Our aim is to determine deterministically integer values λ_{i j} (1 ≤ i ≤ r − 1, 1 ≤ j ≤ r) such that the polynomials F_{i} obtained specializing T_{i j} in λ_{i j} verify this smoothness property, simultaneously with the conditions det(λ_{i j})_{1≤i,j≤k} ≠ 0 (1 ≤ k ≤ r − 1) .

Let J_{k} = (\frac{∂F_{i}}{∂X_{j}}) denote the jacobian matrix of the (F_{1}, …, F_{k}) ’s and let Δ_{1}^{(k)}, …, Δ_{s_{k}}^{(k)} denote its k × k minors.

We recall the following jacobian criterion (see [41, Theorem 30.3 and proof]) : O is a regular local ring and f_{1}, …, f_{r} ∈ O are such that the conditions (f_{1}, …, f_{r}) ≠ (1) and (f_{1}, …, f_{r}, Δ_{1}, …, Δ_{s}) = (1) hold (where Δ_{j} denote the maximal minors of the jacobian matrix of the f_{i} ’s). Then O/(f_{1}, …, f_{r}) is a regular ring. This criterion shows that the smoothness property of (F_{1}, …, F_{k}) (1 ≤ k ≤ r − 1) is guaranteed when for every 1 ≤ k ≤ r − 1, 1 ≤ j ≤ r the following two conditions (in terms of triviality of ideals) hold :

• The ideal (F_{1}, …, F_{k}) is not the trivial ideal in K[X_{1}, …, X_{n}]_{f_{j}} .

• The ideal ((F_{1}, …, F_{k}, Δ_{1}^{(k)}, …, Δ_{s_{k}}^{(k)}) is the trivial ideal in K[X_{1}, …, X_{n}]_{f_{j}}

(Note that the regularity condition of F_{1}, …, F_{r−1} in K[X_{1}, …, X_{n}]_{f_{j}} cannot be recovered simply from the regularity in the localizations at maximal ideals containing (F_{1}, …, F_{r−1}) : that’s the reason why we have to ask the conditions for 1 ≤ k ≤ r − 1 .) Let Y denote a new variable. We can restate these conditions as :

i) The ideal (F_{1}, …, F_{r}, 1 − Y f_{j}) is not the trivial ideal in K[X_{1}, …, X_{n}, Y] .

ii) For every k, 1 ≤ k ≤ r − 1, the ideal (F_{1}, …, F_{k}, Δ_{1}^{(k)}, …, Δ_{s_{k}}^{(k)}, 1 − Y f_{j}) is the trivial ideal in K[X_{1}, …, X_{n}, Y] .

*************** Finally, we analyze conditions, on the λ_{i,j} ’s, that suffice to have properties i) and ii) above. This can be obtained from the triviality test as in [23]. For the first condition, there is an arithmetic network N of size d^{O(n)} , including polynomials in Q[T_{i,j}] of degree d^{O(n)} , evaluating a formula equivalent to the property “the ideal (F_{1}, …, F_{r}, 1 − Y f_{j}) is not the trivial ideal in K[X_{1}, …, X_{n}, Y] ”. This property holds generically on the variables T_{i,j}. This genericity implies that the formula evaluated by the network must contain an open conjunction, i.e. a conjunction of the kind:

G_{1}(T_{i,j}) ≠ 0 ∧ ⋯ ∧ G_{R}(T_{i,j}) ≠ 0

where the degree of the G_{j} ’s is d^{O(n)} and R is of order d^{O(n)} . On the other hand, the same method applies to get an arihtmetic network N′_{k}, of size d^{O(n)} and containing polynomials of degree d^{O(n)} in the variables T_{i,j}, that evaluates a formula eauivalent to the property “the ideal (F_{1}, …, F_{k}, Δ_{1}^{(k)}, …, Δ_{s_{k}}^{(k)}, 1 − Y f_{j}) is the trivial ideal in K[X_{1}, …, X_{n}, Y] ”. Again, since this holds generically on the T_{i,j} ’s, for every k, 1 ≤ k ≤ r − 1 , the network N′_{k} contains an open conjunction:

H_{1}^{(k)}(T_{i,j})⊥ = 0 ∧ ⋯ ∧ H_{R_{k}}^{(k)}(T_{i,j}) ≠ 0

Again, R_{k} is of order d^{O(n)} and these polynomials have degree at most d^{O(n)} . Combining all these conjunctions, we obtain a single polynomial G(T_{i,j}) (the product of all of them) whose degree is d^{O(n)} and the condition:

G(T_{i,j}) ≠ 0

implies the wanted properties. Finding values λ_{i,j} ∈ ZZ which do not annhilate G, we have found the linear combinations for which the proposition holds. The height of these integers λ_{i,j} is then bounded by d^{O(n)} as wanted.

Finally we apply a strategy as in Section 4.8 (where we study the triviality of the ideals introducing generic linear forms) in order to find a matrix Q verifying the announced bounds. *************************

6.2 Simultaneous Noether normalization

We will use our analysis on questor sets and the sequential method described in [14] to obtain a simultaneous Noether normalization for a regular sequence f_{1}, …, f_{r} of polynomials in ZZ[X_{1}, …, X_{n}] . This simultaneous normalization is performed by a linear change of variables given by an upper triangular matrix Q ∈ M_{n}(ZZ) such that the new variables {X′_{1}, …, X′_{n}} are in Noether position with respect to the regular sequence, i.e. for every 1 ≤ i ≤ r,

0 Q[X′_{1}, …, X′_{n−i}] ↪ 0 Q[X′_{1}, …, X′_{n}]/(f_{1}, …, f_{i})

is an integral ring extension.

Proposition 40 Let f_{1}, …, f_{r} ∈ ZZ[X_{1}, …, X_{n}] be polynomials of degree bounded by d defining a regular sequence in 0 Q[X_{1}, …, X_{n}] . Then there exists an upper triangular matrix Q ∈ M_{n}(ZZ) such that (up to a reorder of the variables) the variables :

( X_{1} ; ⋮ ; X_{n} ) = Q ( X′_{1} ; ⋮ ; X′_{n} )

are in Noether position with respect to the given regular sequence. The height of the matrix Q is of order d^{O(n)} . In the particular case where all the ideals (f_{1}, …, f_{i}), 1 ≤ i ≤ r, are radical ideals, the bound for ht(Q) can be restricted to d^{O(r)} .

Proof.– Here we apply essentially the analysis of [14], where the Noether normalization of an ideal is constructed inductively. Let us denote by V_{i} the zero set of the ideal (f_{1}, …, f_{i}) (1 ≤ i ≤ r) in C^{n}. Without loss of generality, since f_{1}, …, f_{r} is a regular sequence, we can reorder the variables X_{1}, …, X_{n} in such a way that they are independent with respect to the ideals (f_{1}, …, f_{r}) , (f_{1}, …, f_{r−1}) , …, (f_{1}) (i.e. 0 Q[X_{1}, …, X_{n−r}]∩(f_{1}, …, f_{r}) = (0), …, 0 Q[X_{1}, …, X_{n−1}]∩ (f_{1}) = (0) ). For every i and every j ∈ {1, …, i−1} we consider the mapping π_{ij} : C^{n} → C^{n−i+1} given by the projection onto the coordinates (x_{1}, …, x_{n−i}, x_{n−j}) . The image of V_{i} by π_{ij} is an hypersurface given as the zero set of a non-nul polynomial p_{ij} ∈ C[X_{1}, …, X_{n−i}, X_{n−j}] of degree bounded by deg(V_{i}) , i.e. bounded by d^{i} (cf. [26, Remark 4]). This means that there exists N ∈ IN big enough such that π_{ij}^{N} ∈ (f_{1}, …, f_{i}) . Effective Nullstellensatz ([10],[12], [34] and [17]) says now that we can choose N ≤ max{3, d}^{n} (in the particular case where (f_{1}, …, f_{i}) is radical we take N = 1 ). In this way we show that there exists a non-nul polynomial g_{ij} ∈ (f_{1}, …, f_{i}) ∩ 0 Q[X_{1}, …, X_{n−i}, X_{n−j}] of degree bounded by d^{n+i} ( d^{i} in the radical case). We are looking for new variables X′_{1}, …, X′_{n} such that :

• X′_{n−r+1}, …, X′_{n} are integer with respect to X′_{1}, …, X′_{n−r} modulo (f′_{1}, …, f′_{r}) (where f′_{j} denote the new polynomial obtained performing the change of variables),

• X′_{n−r+2}, …, X′_{n} are integer with respect to X′_{1}, …, X′_{n−r}, X′_{n−r+1} modulo (f′_{1}, …, f′_{r−1})

⋮

• and finally X′_{n} is integer with respect to X′_{1}, …, X′_{n−1} modulo (f′_{1})

We proceed inductively, and construct the matrix Q column by column, by introducing at every step a change of coordinates.

– First step : we consider the dependent variable X_{n−r+1} with respect to X_{1}, …, X_{n−r} : there is a non-nul polynomial g_{1} ∈ 0 Q[X_{1}, …, X_{n−r}, X_{n−r+1}] which belongs to (f_{1}, …, f_{r}) . Let G_{1} be the (non nul) homogeneous component of maximal degree of g_{1} (observe that G_{1}(X_{1}, …, X_{n−r}, 1) ≠ 0 ). The polynomial G_{1} has degree bounded by d^{n+r} and can be trivially evaluated by a non-scalar straight line program of depth O((n + r) log_{2} d) , and so does G_{1}(X_{1}, …, X_{n−r}, 1) . Therefore we can apply Corollary 21 (about the height of questor sets) to affirm that there exist integers λ_{1}^{(1)}, …, λ_{n−r}^{(1)} ∈ ZZ of height of order O(d^{3(n+r)}) such that :

G_{1}(λ_{1}^{(1)}, …, λ_{n−r}^{(1)}, 1) ≠ 0

We make the following change of variables :

X_{i} := \{ \begin{matrix}X_{i}^{(1)} + λ_{i}^{(1)}X_{n−r+1}^{(1)} & for i = 1, …, n − r \\ X_{i}^{(1)} & for i = n − r + 1, …, n \end{matrix}

This change verifies that g_{1}(X_{1}, …, X_{n−r+1}) =: g_{1}^{(1)}(X_{1}^{(1)}, …, X_{n−r+1}^{(1)}) is monic in X_{n−r+1}^{(1)} , since its principal coefficient in X_{n−r+1}^{(1)} is exactly G_{1}(λ_{1}^{(1)}, …, λ_{n−r}^{(1)}, 1) . Thus X_{n−r+1}^{(1)} is integral with respect to X_{1}^{(1)}, …, X_{n−r}^{(1)} modulo (f_{1}^{(1)}, …, f_{r}^{(1)}) . (This first change of variables corresponds to an identity matrix unless for the first n − r elements of the column n − r + 1 which correspond to λ_{j}^{(1)} .)

Observe that in this procedure the degrees of the new polynomials f_{1}^{(1)}, …, f_{r}^{(1)} which define the ideal didn’t change.

– Second step : Because of the assumptions on the order of the variables, and the independence of X_{1}^{(1)}, …, X_{n−r}^{(1)} , there exist (as in the first step) non-nul polynomials g_{2} ∈ 0 Q[X_{1}^{(1)}, …, X_{n−r+2}^{(1)}] ∩ (f_{1}^{(1)}, …, f_{r−1}^{(1)}) and h_{2} ∈ 0 Q[X_{1}^{(1)}, …, X_{n−r}^{(1)}, X_{n−r+2}^{(1)}] ∩ (f_{1}^{(1)}, …, f_{r}^{(1)}) . Let G_{2} and H_{2} be the homogeneous components of maximal degree of g_{2} and h_{2} respectively, and consider the polynomial

G := G_{2}(X_{1}^{(1)}, …, X_{n−r+1}^{(1)}, 1).H_{2}(X_{1}^{(1)}, …, X_{n−r}^{(1)}, 1)

This polynomial is evaluable by a straight line program of length log_{2}(2 d^{n+r}) . As in the first step, there exist integers λ_{1}^{(2)}, …, λ_{n−r+1}^{(2)} ∈ ZZ of height of order O(d^{3(n+r)}) such that :

G_{2}(λ_{1}^{(2)}, …, λ_{n−r+1}^{(2)}, 1) ≠ 0 and H_{2}(λ_{1}^{(2)}, …, X_{n−r}^{(2)}, 1) ≠ 0

And we make the change of variables :

X_{i}^{(1)} := \{ \begin{matrix}X_{i}^{(2)} + λ_{i}^{(2)}X_{n−r+2}^{(2)} & for i = 1, …, n − r + 1 \\ X_{i}^{(2)} & for i = n − r + 2, …, n \end{matrix}

Thus the polynomial g_{2}^{(2)}(X_{1}^{(2)}, …, X_{n−r+2}^{(2)}) := g_{2}(X_{1}^{(1)}, …, X_{n−r+2}^{(1)}) is monic in X_{n−r+2}^{(2)} , i.e. X_{n−r+2}^{(2)} is integral with respect to X_{1}^{(2)}, …, X_{n−r+1}^{(2)} modulo (f_{1}^{(2)}, …, f_{r−1}^{(2)}) . Similarly h_{2}^{(2)}(X_{1}^{(2)}, …, X_{n−r}^{(2)}, X_{n−r+2}^{(2)}) is monic in X_{n−r+2}^{(2)} , i.e. X_{n−r+2}^{(2)} is integral with respect to X_{1}^{(2)}, …, X_{n−r}^{(2)} modulo (f_{1}^{(2)}, …, f_{r}^{(2)}) . Finally, by a transitive argument, we conclude that X_{n−r+1}^{(2)} is also integral with respect to X_{1}^{(2)}, …, X_{n−r}^{(2)} modulo (f_{1}^{(2)}, …, f_{r}^{(2)}) . The proof continues by induction, repeating the same arguments. (In the worst case we have to deal with r polynomials of degree d^{n+r}.) We obtain finally the upper triangular matrix obtained filling its last r columns with the respective λ_{i}^{(j)} .

7 Nullstellensatz and Membership Problem

7.1 Describing the output polynomials

Finally we are able to show our two main results, Theorem 1 and 2, already stated in the introduction. The first one concerns effective Nullstellensatz :

Theorem 1 (Effective Nullstellensatz) Let f_{1}, …, f_{s} be polynomials in ZZ[X_{1}, …, X_{n}] of degree and height bounded by d ≥ n and η respectively, which don’t share any zero in C^{n}. Then there exists a straight line program of size s d^{O(n)} , depth O(n log_{2} d) and parameters of order max{d^{O(n)}, η} which computes an integer a ∈ ZZ − {0} and polynomials g_{1}, …, g_{s} ∈ ZZ[X_{1}, …, X_{n}] such that :

a = g_{1}f_{1} + ⋯ + g_{s}f_{s}.

This Theorem admits straight forward the following Corollary, simply applying Proposition 15 which relates degrees of polynomials and heights of coefficients with the size, depth and parameters of the corresponding straight line program :

Corollary 4 Let f_{1}, …, f_{s} be polynomials in ZZ[X_{1}, …, X_{n}] of degree and height bounded by d ≥ n and η respectively, which don’t share any zero in C^{n}. Then there exist an integer a ∈ ZZ−{0} and polynomials g_{1}, …, g_{s} ∈ ZZ[X_{1}, …, X_{n}] such that :

• a = g_{1}f_{1} + ⋯ + g_{s}f_{s}

• deg g_{i} = d^{O(n)} (1 ≤ i ≤ s)

• max{log_{2} ht(a), log_{2} ht(g_{1}), …, log_{2} ht(g_{s})} = d^{O(n)} max{log_{2}(η), log_{2} s}

Next result deals with membership and representation problem for an ideal (f_{1}, …, f_{r}), r ≤ n of dimension exactly n − r :

Theorem 2 (Membership problem) Let f_{1}, …, f_{r} (r ≤ n) and g be polynomials in ZZ[X_{1}, …, X_{n}] of degree and height bounded by d ≥ n and η respectively. Assume that (f_{1}, …, f_{r}) is a proper ideal in 0 Q[X_{1}, …, X_{n}] of dimension n − r and that g ∈ (f_{1}, …, f_{r}) holds. Then there exists a straight line program of size d^{O(n)} , depth O(r log_{2} d) and parameters of order max{d^{O(n)}, η} which computes an integer a ∈ ZZ−{0} and polynomials g_{1}, …, g_{r} ∈ ZZ[X_{1}, …, X_{n}] such that :

a g = g_{1}f_{1} + ⋯ + g_{r}f_{r}.

Corollary 5 Let f_{1}, …, f_{r} (r ≤ n) and g be polynomials in ZZ[X_{1}, …, X_{n}] of degree and height bounded by d ≥ n and η respectively. Assume that (f_{1}, …, f_{r}) is a proper ideal in 0 Q[X_{1}, …, X_{n}] of dimension n − r and that g ∈ (f_{1}, …, f_{r}) holds. Then there exist an integer a ∈ ZZ−{0} and polynomials g_{1}, …, g_{r} ∈ ZZ[X_{1}, …, X_{n}] such that :

• a g = g_{1}f_{1} + ⋯ + g_{r}f_{r}

• deg g_{i} = d^{O(r)} (1 ≤ i ≤ r)

• max{log_{2} ht(a), log_{2} ht(g_{1}), …, log_{2} ht(g_{r})} = d^{O(r)}n log_{2}(η)

The proof of the two results is similar : it starts with the preparation of the input polynomials (Section 6) in order to apply recursively the Division Lemma (Lemma 32). Here we are going to treat first the proof of Theorem 2, and at the end of the proof we will sketch briefly the different steps of the proof of the Nullstellensatz.

Proof.– (Membership Problem) First of all we prepare our input polynomials f_{1}, …, f_{r} applying Proposition 39 (Bertini theorem) to f_{1}, …, f_{r} and Proposition 40 (simultaneous Noether normalization) to the obtained f_{1}, …, f_{r−1} which are all radical ideals. We also call f_{1}, …, f_{r} the output of this procedure. For all i, 0 ≤ i ≤ r − 1 , set

J_{i} := (f_{1}, …, f_{i})
R_{i} := ZZ[X_{1}, …, X_{n−i}]
A_{i} := 0 Q[X_{1}, …, X_{n−i}]
B_{i} := A_{i}[X_{n−i+1}, …, X_{n}]/J_{i}

Our preliminar input preparation insures that for all i, 0 ≤ i ≤ r − 1 , A_{i} ↪ B_{i} is in Noether position and that J_{i} is a reduced complete intersection ideal. The mathematical idea to perform the division is straight forward and will suggest the computational treatment; we apply the Division Theorem (Thm 31) as follows :

• f_{r} | g (mod J_{r−1}) implies that we can compute ξ_{r} ∈ R_{r−1} and q_{r} ∈ R_{r−1}[X_{n−r+2}, …, X_{n}] such that ξ_{r} | q_{r} in 0 Q[X_{1}, …, X_{n}] and ξ_{r}g ≡ q_{r}f_{r} (mod J_{r−1})

This means that ξ_{r} (g − \frac{q_{r}}{ξ_{r}} f_{r}) ∈ J_{r−1} which is an equidimensional ideal of dimension n − (r − 1) which doesn’t meet R_{r−1} . Therefore g − \frac{q_{r}}{ξ_{r}} f_{r} ∈ J_{r−1} , i.e. f_{r−1} | g − \frac{q_{r}}{ξ_{r}} f_{r} (mod J_{r−2}) . In other words,

ξ_{r}f_{r−1} | ξ_{r}g − q_{r}f_{r} (mod J_{r−2})

• Now set g_{r−1} := ξ_{r}g − q_{r}f_{r} and divide it by ξ_{r}f_{r−1} . We can compute ξ_{r−1} ∈ R_{r−2} and q_{r−1} ∈ R_{r−2}[X_{n}−r+3, …, X_{n}] such that ξ_{r−1}g_{r−1} ≡ q_{r−1}ξ_{r}f_{r−1} (mod J_{r−2}) .

• Recursively we obtain

ξ_{1} … ξ_{r}g = q_{1}ξ_{2} … ξ_{r} f_{1} + ξ_{1}q_{2}ξ_{3} … ξ_{r} f_{2} + ⋯ + ξ_{1} … ξ_{r−1}q_{r} f_{r}

(where for all i, ξ_{i} | q_{i} in 0 Q[X_{1}, …, X_{n}] )

and we conclude by one division, keeping denominators in ZZ at the left side of the equality. Unfortunately this simple procedure is not allowed for our purpose since it leads to a straight line program of depth essentially O(n^{2} log_{2} d) , due to the fact that each q_{i} (which can be computed in depth O(n log_{2} d) ) depends recursively on q_{i+1} . This procedure would yield to bounds of order d^{O(n^{2})} for the logarithmic height of the g_{i} ’s. We will use here our more technical Lemma 32 : the crucial point for us is that it constructs a matrix Q which applied linearly on the coefficients of the dividend g gives the coefficients of the quotient q, and this depending only on deg^{∗} g and on the coefficients of the f_{i} ’s. Set :

g_{r} := g
g_{r−1} := ξ_{r}g_{r} − q_{r}f_{r}
g_{r−2} := ξ_{r−1}g_{r−1} − ξ_{r}q_{r−1}f_{r−1}
⋮
g_{r−i} := ξ_{r−i+1}g_{r−i+1} − ξ_{r−i+2} … ξ_{r}q_{r−i+1}f_{r−i+1}
⋮
g_{1} := ξ_{2}g_{2} − ξ_{3} … ξ_{r}q_{2}f_{2}

Observe that the fact that R_{r−i} ⊂ R_{r−i−1} implies that each q_{r−i}, g_{r−i} viewed as a polynomial with coefficients in R_{r−i−1} verifies that deg^{∗} q_{r−i} ≤ (r − 1)d and deg^{∗} g_{r−i} ≤ rd. In the sequel, we denote by (h)_{k} the vector of coefficients of a polynomial h viewed as a polynomial in R_{k}[X_{n−k+1}, …, X_{n}] . Now we compute independently from g_{1}, …, g_{r} the following items :

• All the coefficients in R_{0}, …, R_{r−1} of the polynomials f_{1}, …, f_{r}, and the coefficients in R_{r−1} of the polynomial g (in size O(d^{n}) , depth O(log_{2} d) and parameters of height bounded by η).

• All the values ξ_{j} ∈ R_{j−1} and all the matrices Q_{j} ∈ R_{j−1}[X_{n−j+2}, …, X_{n}] which verify that Q_{j}((g_{j})_{j−1}) = ((q_{j})_{j−1}) (in size d^{O(r)} , depth O(r log_{2} d) and parameters of height d^{O(r)} ).

• Matrices T_{j} (1 ≤ j ≤ r) which transform the coefficients of a polynomial h ∈ R_{j−1}[X_{n−j+2}, …, X_{n}] of degree bounded by (r − 1)d on the coefficients of the polynomial f_{j}h of degree ≤ rd (Size d^{O(r)} and depth O(log_{2} d) )

• Matrices B_{j} (1 ≤ j ≤ r) which transform the coefficients in R_{j−1} of a polynomial h of degree rd on its coefficients when viewed as a polynomial with coefficients in R_{j−2} . (Here B_{1} will denote the identity matrix.) (Same size and depth)

All these computations can then be performed by means of a straight line program of size d^{O(n)} , depth O(r log_{2} d) and parameters of height max{d^{O(r)}, η}, and observe that the obtained value d^{O(n)} for the size comes only from a precomputation of the coefficients of the input polynomials in the rings R_{i}.

We have :

•  (g_{r−1})_{r−2} = B_{r}(ξ_{r}g_{r} − f_{r}q_{r})_{r−1}
= (B_{r}(ξ_{r}Id − T_{r}Q_{r})) (g_{r})_{r−1}
•  (g_{r−2})_{r−3} = B_{r−1}(ξ_{r−1}g_{r−1} − ξ_{r}f_{r−1}q_{r−1})_{r−2}
= (B_{r−1}(ξ_{r−1}Id − ξ_{r}T_{r−1}Q_{r−1})) (g_{r−1})_{r−2}
= (B_{r−1}(ξ_{r−1}Id − ξ_{r}T_{r−1}Q_{r−1})) (B_{r}(ξ_{r}Id − T_{r}Q_{r})) (g_{r})_{r−1}
etc.

Thus if we define for 1 ≤ j ≤ r :

N_{j} := B_{j}(ξ_{j}Id − ξ_{j+1} … ξ_{r}T_{j}Q_{j})

we obtain :

(g_{j})_{j−1} = (N_{j+1} … N_{r})(g_{r})_{r−1}

This fact allows to compute independently all the coefficients of the polynomials g_{j} ∈ R_{j−1}[X_{n−j+2}, …, X_{n}] , as a product of matrices applied to (g)_{r−1} . Finally for each g_{j} we compute (q_{j})_{j−1} = Q_{j}((g_{j})_{j−1}) . Without changing essentially size, depht and height of the parameters, as in the proof of the Division Lemma 32, we construct a straight line program which evaluates from the variables X_{1}, …, X_{n} the polynomials ξ_{1}, …, ξ_{r}, q_{1}, …, q_{r}. We obtain

ξ_{1} … ξ_{r}g = q_{1}ξ_{2} … ξ_{r} f_{1} + ξ_{1}q_{2}ξ_{3} … ξ_{r} f_{2} + ⋯ + ξ_{1} … ξ_{r−1}q_{r} f_{r}

(where for all i, ξ_{i} | q_{i} in 0 Q[X_{1}, …, X_{n}] ), and we conclude applying Proposition 23 (Vermeidung von Divisionen) in order to obtain a ∈ ZZ and g′_{1}, …, g′_{r} ∈ ZZ[X_{1}, …, X_{n}] such that

ag = g′_{1}f_{1} + ⋯ + g′_{r}f_{r}.

The last step of the proof consists on recovering the expression of the original input polynomials from f_{1}, …, f_{r}, by means of the inverses of the matrices of Lemmas 39 and 40. This procedure adds size n, one step depth and parameters of height d^{O(r)} . (It also slightly modifies the constant a multiplying it by the determinant of the concerned matrices.) Therefore the total size of our straight line program is of order d^{O(n)} , its depth is O(r log_{2} d) and the parameters are of height max{d^{O(r)}, η}.

(Nullstellensatz) The only difference is that our Bertini preparation allows to suppose that our input polynomials are f_{1}, …, f_{r+1} with r ≤ n, where for all i ≤ r, (f_{1}, …, f_{i}) are reduced complete intersection ideals and f_{r+1} is not a zero-divisor modulo (f_{1}, …, f_{r}) . We begin the algorithm setting g := 1 .

7.2 A probabilistic Turing machine

We end this work describing briefly a probabilistic Turing machine that solves the effective Nullstellensatz problem (the one for the Membership problem being analogous). We follow the model of [1, Chapter 6].

Corollary 3 The Effective Nullstellensatz and the Membership Problem to Complete Intersection Ideals are in the BPP–class of bounded error probabilistic polynomial time machines, i.e. there is a probablistic Turing machine that solves both problems within time polynomial in the dense representation of the input polynomials. In particular, both problems can be solved in polynomial space counting also “external memory” requirements.

Proof.– The probabilistic Turing machine makes a guessing of a list Q of t = d^{O(n)} non– negative integer vectors of height u = d^{O(n)} (which reprensents a candidate for a correct test sequence as in Corollary 21. The probability of error for the procedure is bounded by \frac{1}{u^{t/6}} as a consequence of the bounds in Corollary 21. Then the Turing machine tests the triviality of our ideal as in 4.8. If the ideal is trivial, it proceeds as in subsection refbert to determine the parameters for Bertini’s theorem. These parameters are chosen from Q. As observed there, the parameters are chosen by means of some triviality tests of simple ideals. Now it proceeds as in [23] with generic linear changes of coordinates to get simultaneous Noether normalization. The parameters for the linear change of coordinates are again obained from Q. They are less precise than those obtained in Subsection 6.2 but they also can be obtained in polynomial time. The method described in Section 4 allows to obtain from Q a primitive element for every Noether extension and to determine the bases of the extensions. Following the steps in Section 5 it describes the matrices for the division in the reduced complete intersections.

Finally it performs as in subsection 7.1 above the iterated matrix product and applies the avoiding division method to obtain the encoding of the output.

Observe that there are only some steps where the Turing machine makes use of the guessing. In these steps if no concrete candidate is acceptable, the machine rejects the input. Hence, the probability of error is simply the probability that Q is not a correct test sequence. Since the binary size of all intermediate results never increases over d^{O(n)} (cf. Proposition 15), the whole procedure runs in polynomial time and Corollary 3 is shown.

Aknowledgments

We are indebted to Joos Heintz for having strongly inspirated this work, and to Pablo Solernó for many helpful suggestions. The first author also thanks the members of the Mathematic Department of the University of Cantabria (Santander) for their hospitality during april’94, when last details of this paper were discussed.

8 References

References

[1] J.L. Balcazar, J.L. Díaz and J. Gabarró. “Structural Complexity I”, EATCS Mon. on Theor. Comp. Sci. 11, Springer ( 1988 ).

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

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

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

[5] A. Borodin, J. von zur Gathen and J. Hopcroft. “Fast parallel matrix and gcd computations”, Proc. 23th Annual Symp. FOCS ( 1982 ) 65–71.

[6] A. Borodin.“Relating Size and Depth to Time and Space”.

[7] J.-B. Bost, H. Gillet and C. Soulé. “Un analogue arithmétique du théorème de Bézout”, C.R. Acad. Sci. Paris, t. 312, Série I ( 1991 ) 845–848.

[8] J.-B. Bost, H. Gillet and C. Soulé. “Heights of projective varieties and positive Green forms”, Manuscrit I.H.E.S. ( 1993 ).

[9] J. Briançon.“On Euclid’s algorihtm and the computation of polynomial greatest common divisors”, J. ACM 18 (1971) 478–504.

[10] D. W. Brownawell. “Bounds for the degree in the Nullstellensatz”, Annals of Math. 126 ( 1987 ) 577–591.

[11] D.W. Brownawell. “Local Diophantine Nullstellen inequalities”, J. Amer. Math. Soc. 1 ( 1988 ) 311–322.

[12] 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, t. 307 Série I ( 1988 ) 255–258.

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

[14] A. Dickenstein, N. Fitchas, M. Giusti and C. Sessa. “The membership problem for unmixed polynomial ideals is solvable in single exponential time”, Discrete Appl. Math. 33 ( 1991 ) 73–94.

[15] A. Dickenstein, C. Sessa. “Résidus de formes méromorphes et cohomologie modérée”, Géométrie Complexe, Prépublication Université Paris 7 ( 1994 ).

[16] M. Elkadi. “Bornes pour le degré et les hauteurs dans le problème de division”, to appear in Michigan Math. J. ( 1993 ).

[17] N. Fitchas and A. Galligo.“Nullstellensatz effectif et conjecture de Srre (théorème de Quillen-Suslin) pour le Calcul Formal”, Math. Nach. 149 ( 1990 ) 231–253.

[18] N. Fitchas, M. Giusti and F. Smietanski. “Sur la complexité du théorème des zéros”, Manuscript Ecole Polytechnique ( 1993 ).

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

[20] J. von zur Gathen. “ Parallel algorithms for algebraic problems”, Proc. 13–th Conf. MFCS. Springer LN Comp. Sci. 233 ( 1986 ) 93–112.

[21] A.O. Gel’fond. Transcendental and Algebraic Numbers, New York : Dover ( 1960 ).

[22] M. Giusti and J. Heintz. “ Algorithmes –disons rapides– pour la décomposition d’une variété algébrique en composantes irréductibles et équidimensionelles”, Progress in Math. 94, T.Mora and C.Traverso Eds., Birkhäuser ( 1991 ) 169–193.

[23] M. Giusti and J. Heintz. “La détermination des points isolés et de la dimension d’une varieté algébrique peut se faire en temps polynomial”, to appear in Proc. Int. Meeting on Commutative Algebra, Cortona ( 1991 ).

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

[25] D.Iu. Grigor’ev and N.N. Vorobjov.“Solving systems of polynomial inequalities in subexponential time”, J. Symb. Comp. 5 (1988) 37–64.

[26] J. Heintz. “Fast quantifier elimination over algebraically closed fields”, Theoret. Comp. Sci. 24 ( 1983 ) 239–277.

[27] J. Heintz. “On the computational complexity of polynomials and bilinear mappings”, Proc. AAECC–5, Springer LNCS 356 ( 1989 ) 269–300.

[28] J. Heintz and J. Morgenstern. “On the intrinsic complexity of elimination theory”. J. of Complexity 9 ( 1993 ) 471–498.

[29] J. Heintz and C.P. Schnorr. “Testing Polynomials wich are easy to compute”, Proc. 12th Ann. ACM Symp. on Computing ( 1980 ) 262–268.

[30] J. Heintz and M. Sieveking. “Lower Bounds for polynomials with algebraic coefficients”, Theoret. Comp. Sci. 11 ( 1980 ) 321–330.

[31] G. Hermann.“Die Frage der endlich vielen Schritte in der Theorie der Polynomideale”, Math. Ann. 95 ( 1926 ) 736–788.

[32] B. Iversen. Generic Local Structures in Commutative Algebra, Lect. Notes in Math. 310, Springer-Verlag ( 1973 ).

[33] J. P. Jouanolou. Théorèmes de Bertini et applications, Progress in Math. 42, Birkhäuser ( 1983 ).

[34] J. Kollár. “Sharp Effective Nullstllensatz”, J. of A.M.S. 1 ( 1988 ) 963–975.

[35] E. Kunz. Kähler Differentials, Advanced Lectures in Math., Vieweg- Verlag ( 1986 ).

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

[37] E. Landau. “Sur quelques théorèmes de M. Petrovic relatifs aux zéros des fonctions analytiques”, Bull. S.M.F., t. 33 ( 1905 ) 251–261.

[38] S. Lang.Fundamentals of Diophantine Geometry, Springer-Verlag ( 1983 ).

[39] S. Lang. Transcendental Number Theory,

[40] D. Lazard. “Résolution des systèmes d’équations algébriques”, Theor. Comp. Sci. 15 ( 1981 ) 77–110.

[41] H. Matsumura. Commutative Ring Theory, Cambridge University Press ( 1986 ).

[42] E. Mayr. “Membership problem to polynomial ideals is exponential space complete”,

[43] E. Mayr and A. Meyer. “The complexity of the word problem for commutative semigroups ”, Advances in Math. 46 ( 1982 ) 305–329.

[44] M. Mignotte. Mathématiques pour le Cacul Formel, Presses Univ. de France ( 1989 ).

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

[46] J.L. Montaña, L.M. Pardo and T. Recio. “The non–scalar model of complexity in Computational semialgebraic geometry”, Progress in Mathematics 94, T.Mora and C.Traverso eds., Birkhäuser ( 1991 ) 346–362.

[47] D. W. Masser and G. Wüstholz. “Fields of large transcendence degree generated by values of elliptic functions”, Invent. Math. 72 ( 1971 ) 407–463.

[48] J. Sabia and P. Solernó. “Bounds for traces in complete intersections and degrees in the Nullstellensatz”, to appear in AAECC Journal ( 1993 ).

[49] T. Schneider. Einführung in die transzendenten Zahlen, Springer-Verlag, Berlin ( 1957 ).

[50] C.P. Schnorr. “Improved lower bounds on the number of multiplications/divisions which are necessary to evaluate polynomials”, Theor. Comp. Sci. 7 ( 1978 ) 251–261.

[51] I.R. Shafarevich. “Basic Algebraic Geometry”. Springer-Verlag.

[52] M. Shub and S. Smale. “On the intractability of Hilbert’s Nullstellensatz and an algebraic version of P=NP?”. IBM Research Report 19624 (86196) 1994 .

[53] V. Strassen. “Polynomials with rational coefficients which are hard to compute”, SIAM J. Comput. 3 ( 1974 ) 128–149.

[54] V. Strassen. “Vermeidung von divisionen”, Crelle J. Reine Angew. Math. 264 ( 1973 ) 184–202.

[55] V. Strassen. “Algebraic Complexity Theory”, Hand Book of Theoretical Computer Science, ch. 11 ( 1990 ) 634–671.