ON THE EFFICIENCY OF EFFECTIVE NULLSTELLENSÄTZE

Marc Giusti, Joos Heintz and Juan Sabia

Abstract. Let k be an infinite and perfect field, x_{1}, …, x_{n} indeterminates over k and let f_{1}, …, f_{s} be polynomials in k[x_{1}, …, x_{n}] of degree bounded by a given number d, which satisfies d ≥ n. We prove an effective affine Nullstellensatz of the following particular form: For arbitrary given parameters d, s, n there exists a probabilistic (randomized) arithmetic network over k of size s^{O(1)} d^{O(n)} and depth O(n^{4} log^{2} sd) solving the following task: It decides whether the ideal generated by f_{1}, …, f_{s} in k[x_{1}, …, x_{n}] is trivial and, if this is the case, it produces a straight-line program of size s^{O(1)} d^{O(n)} and depth O(n^{4} log^{2} sd) in the function field k(x_{1}, …, x_{n}) which computes polynomials p_{1}, …, p_{s} of k[x_{1}, …, x_{n}] of degree d^{O(n^{2})} satisfying

1 = ∑_{1≤j≤s} p_{j}f_{j} .

Key words. Complexity; straight-line program; computer algebra; elimination theory; effective Nullstellensatz. Subject classification. 68C25.

1. Introduction

We first introduce some basic notions and notation (these are essentially the same as in Giusti & Heintz 1991a and Giusti & Heintz 1991b). Then we explain our main result.

1.1. Notation. Let k be an infinite, perfect field. We suppose k to be effective; this means that the arithmetic operations (addition, subtraction, multiplication, division) and basic equality checking (comparison) between elements of k are realizable by algorithms. If k has positive characteristic p we assume also that the extraction of p^{th} roots is effective.

Let \overline{k} be an algebraic closure of k. We denote by A^{n} = A^{n}(\overline{k}) the ndimensional affine space over \overline{k}, equipped with its Zariski topology and with its coordinate ring of polynomial functions. The affine algebraic varieties we are going to consider are closed subsets of A^{n}.

Let x_{1}, …, x_{n} be indeterminates over k. We denote the total degree of a polynomial f ∈ k[x_{1}, …, x_{n}] by deg f and its partial degree in x_{i}, for 1 ≤ i ≤ n, by deg_{x_{i}} f. We call f monic in x_{i} if deg_{x_{i}} f = deg f > 0 is satisfied.

In the remainder of the paper, let f_{1}, …, f_{s} be a finite family of nonconstant polynomials of k[x_{1}, …, x_{n}]. Let d be an integer larger that the maximum of n and all deg f_{j} (for j ranging from 1 to s). We denote the ideal generated by f_{1}, …, f_{s} in k[x_{1}, …, x_{n}] by (f_{1}, …, f_{s}), or simply by I. We use also the notation (f_{1}, …, f_{s}) for the ideal generated by f_{1}, …, f_{s} in extension rings, for example in k(x_{1}, …, x_{i})[x_{i+1}, …, x_{n}], where 1 ≤ i ≤ n.

We write V (f_{1}, …, f_{s}), V (I), {f_{1} = 0, …, f_{s} = 0} or simply V for the algebraic variety defined by f_{1}, …, f_{s} in A^{n}.

1.2. Complexity considerations. The algorithms we are going to consider accept as input arrays (vectors) of elements of k which represent s polynomials of k[x_{1}, …, x_{n}] of degree at most d in dense representation. (In the case k = Q, the algorithms may in principle also admit the bit-representation of polynomials. Nevertheless the proofs in the present paper will not deal with this aspect.) We shall always assume d ≥ n. The output may be of different nature: boolean values, integers between −1 and n (represented by vectors of boolean values), square n×n matrices with entries from k, or polynomials. The polynomials which occur as output are generally given by straight-line programs of size s^{O(1)} d^{O(n)} and have degree of order d^{O(n)} and sometimes of order d^{O(n^{2})} . We have also to consider the case of univariate polynomials satisfying the same degree bounds, which are given in dense representation and whose coefficients can be computed in sequential time s^{O(1)} d^{O(n)} . Thus we have to explain how we measure input and output size and which kind of algorithms we shall consider.

1.2.1. Input and output size. Let f_{1}, …, f_{s} be the family of polynomials of degree at most d introduced in 1.1. We shall consider this family as our standard input. We think of f_{1}, …, f_{s} as being represented by the array of their coefficients in dense representation. Thus the typical input to our algorithms is (generally large) vectors with entries from the base field k. The size of these vectors depends only on the parameters d, s and n.

There exists also the particularly important case of the rational base field k = Q. In this case the size of our input may also take into account the maximal bit length t of the coefficients of f_{1}, …, f_{s}.

The size of the input f_{1}, …, f_{s} is given by the space necessary to store all its coefficients. This storage space is determined by the parameters d, s,

n and, in the case of k = Q, by t. There are \binom{d + n}{n} monomials of degree

at most d in n letters. Since \binom{d + n}{n} ≤ e d^{n} = O(d^{n}) our input has size

O(s d^{n}) (or O(s d^{n} t) for k = Q and where size is measured in number of bits).

Throughout the paper we shall suppose d ≥ n. When our algorithms produce nonlinear polynomials as intermediate results or as final output, these polynomials will have degrees of order d^{O(n)} or d^{O(n^{2})} according to the context. The polynomials may be uni- or multivariate. They may contain no, one or several distinguished main variables. The univariate polynomials are represented in dense form by their coefficients. The multivariate polynomials without distinguished variables are given by straight-line programs of size s^{O(1)} d^{O(n)} . The multivariate polynomials with distinguished variables are represented in dense form by the array of their coefficients with respect to these variables. These coefficients are represented by straight-line programs in the polynomial ring (or function field) over the remaining variables.

We also have to consider some intrinsic geometrical invariants of the variety V given by f_{1}, …, f_{s}. Let

V = ⋃_{1≤k≤N} C_{k}

be the decomposition of V in irreducible components. We identify as usual the dimension dim C of an irreducible component C = C_{k}, for 1 ≤ k ≤ N, with the Krull dimension of its coordinate ring and its degree deg C with the number of points arising when we intersect C with dim C many generic affine hyperplanes of A^{n}. We define now the dimension of V by

dim V = max{dim C_{k}; 1 ≤ k ≤ N}

and its degree by

deg V = ∑_{1≤k≤N} deg C_{k} .

This rather unconventional notion of degree satisfies a Bézout Inequality which holds without any restriction on the type of intersection we may consider (see Heintz 1983).

1.2.2. Base fields extensions and arithmetic operations. All our algorithms rely on the following fundamental operations in the base field k, which we call arithmetic: selection of fixed elements of k (e.g., 0 or 1) as constant operations, addition, subtraction, multiplication, and eventually division or extraction of p^{th} roots if the characteristic p of k is positive. In general our algorithms do not include divisions, and their intermediate results are polynomials of degree d^{O(n)} in the coordinates of the input array of the algorithm.

Very often we shall be obliged to divide the indeterminates x_{1}, …, x_{n} into “parameters”, say x_{1}, …, x_{i}, and distinguished main variables, say x_{i+1}, …, x_{n}, for a given 1 ≤ i ≤ n. Our algorithms will then produce elements of k(x_{1}, …, x_{i})[x_{i+1}, …, x_{n}] which are considered as polynomials in the main variables x_{i+1}, …, x_{n} with coefficients in the extended base field k(x_{1}, …, x_{i}). After a suitable k -linear transformation of the main variables these polynomials will never contain more than two of them. Moreover, the degree of these polynomials will be of order d^{O(n)} or d^{O(n^{2})} according to the context. They will be represented (or at least representable) by straight-line programs in k(x_{1}, …, x_{i})[x_{i+1}, …, x_{n}] of size s^{O(1)} d^{O(n)} , whose eventually arising divisions can be executed in k(x_{1}, …, x_{i}). The parallel complexity of these straight-line programs will be in general O(n^{2} log^{2} sd) (in this sense they are “well-parallelizable”). Thus we may think of the polynomials produced by our algorithms as being given in dense representation with respect to the two main variables that actually occur. In this sense they can be given as an array of rational functions of k(x_{1}, …, x_{i}) (or of k[x_{1}, …, x_{i}] if no divisions are involved). These rational functions are represented as results of a generally well-parallelizable straight-line program in k(x_{1}, …, x_{i}) (or k[x_{1}, …, x_{i}]) of size s^{O(1)} d^{O(n)} .

All computations are based on well-parallelizable effective linear algebra without divisions in the spirit of the algorithms of Berkowitz (1984) and Mulmuley (1986). We run them first in the extended base field k(x_{1}, …, x_{i}) by means of straight-line programs and identity checking of intermediate results. This identity checking will be executed according to Heintz & Schnorr (1982), Theorem 4.4, in the actual base field k using s^{O(1)} d^{O(n)} arithmetic operations. This allows us to transfer the whole algorithm into k.

A last word has to be said on the extraction of p^{th} roots in the extended base field if the characteristic p of k is positive. First of all, extractions of p^{th} roots will appear only in subroutines with no effect on final results and the number of iterations of this process is bounded by an integer m, known a priori, of order O(n log d). Temporarily we may introduce new auxiliary indeterminates S_{1}, …, S_{i} and replace the parameters x_{1}, …, x_{i} by S_{1}^{p^{m}}, …, S_{i}^{p^{m}}. The algorithmic steps to be executed in k(x_{1}, …, x_{i}) are simulated in k(S_{1}, …, S_{i}), where the necessary extractions of p^{th} roots can be performed without asymptotic increase in the cost (here the assumption that k is perfect becomes crucial). Since the final outcome of the subroutine which requires extraction of p^{th} roots will be a k -linear transformation of the main variables x_{i+1}, …, x_{n}, the temporary introduction of the auxiliary parameters S_{1}, …, S_{i} has no influence on the global behavior of our algorithm, in particular on its output (see Giusti & Heintz 1991b, Sections 3.4.6 and 3.4.7 for this point).

For more details on the technique of algorithmic base field (and ring) extensions we refer the reader to Giusti & Heintz (1991b), Sections 1.2.2 and 1.2.3.

1.2.3. Algorithms and their complexity. Our algorithms will be represented by randomly generated families of arithmetic networks over k depending on the parameters d, s and n (see von zur Gathen 1986). These arithmetic networks are acyclic oriented graphs whose internal nodes are labelled by arithmetic operations of k (including the eventual extraction of p^{th} roots), by Boolean operations corresponding to propositional logic, and by selectors associated with equality checking of elements of k. The external nodes of the graph represent the inputs and the outputs of the network. The input is always elements of k and the output may be elements of k, Boolean values, or integers of limited range (represented by vectors of Boolean values). Straight-line programs are represented by arithmetic circuits, i.e., networks without any branching. They contain neither selectors nor (propositional) Boolean operations. For exact definitions and elementary properties of the notion of straight-line programs we refer to Strassen (1972), von zur Gathen (1986), Stoss (1989) or Heintz (1989).

Most of our arithmetic networks (and straight-line programs) will not contain any division. This is of particular importance for equality checking between intermediate results if these are polynomials given by straight-line programs. We shall perform this task by choosing a suitable “correct test sequence” of points with coordinates from k according to Heintz & Schnorr (1982), Theorem 4.4. Although the choice of such a correct test sequence could be done algorithmically, the costs of doing so would exceed the main complexity class considered in this paper. Therefore our algorithms will be non-uniform insofar as they depend on the choice of correct test sequences. On the other hand, the quoted Theorem 4.4 of Heintz & Schnorr (1982) allows us to randomly choose correct test sequences with a probability of failure which becomes arbitrarily small as the parameters s, d and n increase.

Therefore our algorithms can be uniformly randomized within the same order of (average) complexity. In doing so we encounter the following kind of probabilistic procedure which we call a randomized algorithm. A randomized algorithm has error probability bounded by some 0 ≤ ε < \frac{1}{2} when accepting an input and error probability zero when rejecting it (in our case we may choose ε = \frac{1}{262144} ). As far as our algorithms compute polynomials or rational functions the correctness of the output depends only on the correctness of previous and intermediate decisions made by probabilistic procedures and can be checked randomly. In this sense, we apply also the term randomized procedure to the computation of polynomials or rational functions. Thus our results are valid not only in the sense of the non-uniform complexity model, but also in the sense of probabilistic (randomized) algorithms (see Balcázar et al. 1988, Section 6.6 and Giusti & Heintz 1991b, Sections 1.2.3, 1.3 and 2.2 for more details).

In the case k = Q, each node of an arithmetic network corresponding to a fundamental operation in the base field Q may be replaced by a Boolean circuit which processes bits. Taking into account the growth of the coefficients of the polynomials which appear as intermediate results of our algorithms, we are convinced that our arithmetic networks may be transformed in a natural way into Boolean ones of the same order of complexity and that our results remain valid mutatis mutandis for the bit complexity model of algorithms represented by Boolean networks. However guessing that the proofs will be rather tedious we will not enter this subject here.

Our algorithms are families of arithmetic networks parametrized by d, s and n (or, in the case k = Q, families of Boolean networks parametrized by d, s, n and t).

We shall say that an algorithm is polynomial in the size of the input if the network corresponding to d, s, n (or d, s, n, t in the Boolean case) has size s^{O(1)} d^{O(n)} (or (st)^{O(1)} d^{O(n)} in the Boolean case). We call the algorithm well-parallelizable if the depth of the network is O(n^{2} log^{2} sd) (or O(n^{2} log^{2} std) in the Boolean case).

We refer to the size and depth of arithmetic and Boolean networks as their sequential and parallel time complexity respectively.

Our notion of polynomiality is with respect to the data structure we have chosen to represent the standard input f_{1}, …, f_{s} of all our algorithms: the dense representation of polynomials by their coefficients. Thus our input has size O(sd^{n}) (or O(std^{n}) in the Boolean case) and polynomiality in this size means sequential time complexity s^{O(1)} d^{O(n)} (or (st)^{O(1)} d^{O(n)} in the Boolean case). The notion “well-parallelizable” signifies that the parallel time complexity is of order log^{2} in the sequential time complexity of the algorithm.

From now on we shall restrict ourselves to the algebraic model of algorithms represented by families of arithmetic networks. Thus, as we said before, the bit complexity aspect will be discarded from our considerations. All our algorithms will be randomized procedures and will have sequential time complexity s^{O(1)} d^{O(n)} (see Balcázar et al. 1988, Section 6.6). In general they will be well-parallelizable. In their non-uniform version they will therefore satisfy the same time bounds (compare with Balcázar et al. 1988, Corollary 6.4). Most of our algorithms will be division-free. As far as they compute polynomials, the degrees will be of order d^{O(n)} or d^{O(n^{2})} .

We shall suppose that the non-uniform version of our algorithms is preprocessed by the choice of suitable correct test sequences and is in general well-parallelizable of deterministic time complexity s^{O(1)} d^{O(n)} . The preprocessing depends only on the parameters d, s and n (and not on the coefficients of the particular input f_{1}, …, f_{s}) and although it can be done algorithmically, its costs are not taken into account (for more details we refer to Giusti & Heintz 1991b, Sections 1.2.3 and 2.2).

However, as we mentioned before, the choice of correct test sequences may be performed randomly with a small failure probability. This fact implies the randomized version of our algorithms. Finally, let us remark that in (Dickenstein et al. 1991) there is a uniform and well-parallelizable counterpart of our algorithms of sequential time complexity s^{O(1)} d^{O(n^{2})} (and Turing complexity (st)^{O(1)} d^{O(n^{2})} in the case k = Q).

1.2.4. Algorithmic tools. Our complexity results are based on techniques of effective linear algebra which rely on well-parallelizable algorithms without divisions. A cornerstone of these techniques is Berkowitz’ well-parallelizable polynomial algorithm for computing all the coefficients of the characteristic polynomial of a square matrix over any domain (Berkowitz 1984). The coefficients of the characteristic polynomial are represented by a straight-line program without divisions. For computing the rank of an arbitrary linear equation system over any domain or for solving it in the fraction field of the domain we combine Berkowitz’ algorithm with a result of Mulmuley (1986) which allows us to express the rank of an arbitrary matrix over any domain by the multiplicity of zero in the characteristic polynomial of some associated square matrix.

Some subroutines of our algorithms also require the computation of the greatest common divisor of univariate polynomials whose coefficients are given by straight-line programs in some polynomial ring over k. We do this following the lines of Giusti & Heintz (1991a), Section 4.2.1, using subresultant techniques (see Brown 1971) in combination with Berkowitz’ algorithm. Only in these subroutines is the extraction of p^{th} roots relevant in case of positive characteristic p (compare with Giusti & Heintz 1991b, Section 2 and Section 1.2.2 of the present paper).

Our contribution relies in a crucial way on the algorithmic techniques and results of Giusti & Heintz (1991b). We summarize the principal ones:

Proposition A (Giusti & Heintz 1991b, Théorème 3.5 and Théorème 3.7.2) There exists a well-parallelizable randomized algorithm without divisions which computes in sequential time s^{O(1)} d^{O(n)} the following items:

(1) the dimension r = dim V of the algebraic variety defined by f_{1}, …, f_{s} in A^{n},

(2) a nonsingular n × n matrix M with entries from k such that the variables y_{1}, …, y_{n}, which we obtain by transforming x_{1}, …, x_{n} by means of M, are in Noether position with respect to V . (Recall from Giusti & Heintz 1991a, that the variables y_{1}, …, y_{n} are said to be in Noether position with respect to V if for each r < i ≤ n, where r = dim V , there exists a polynomial of k[y_{1}, …, y_{r}, y_{i}] which is monic in y_{i} and vanishes on V .)

Proposition B (Giusti & Heintz, 1991b, Section 3.4.7 and Lemma 3.6.1) Assume that I = (f_{1}, …, f_{s}) is a zero dimensional ideal (the zero dimensionality of I means that V = V (I) is a finite nonempty set). Let J be the radical ideal of I. Then there exists a well-parallelizable randomized algorithm without divisions which computes in sequential time s^{O(1)} d^{O(n)} the following items:

(1) a nonsingular n×n matrix M with entries from k which transforms x_{1}, …, x_{n} into new variables y_{1}, …, y_{n},

(2) a nonzero element α of k which is a polynomial of degree d^{O(n)} in the coefficients of f_{1}, …, f_{s} over a suitable finitely generated subring of k,

(3) sparse polynomials g_{1}, …, g_{n} in the variables y_{1}, …, y_{n} with coefficients in k such that these coefficients have the same properties as α with respect to the input f_{1}, …, f_{s}.

The element α and the polynomials g_{1}, …, g_{n} satisfy the following conditions:

(i) max{deg g_{i}; 1 ≤ i ≤ n} ≤ deg V ≤ d^{n}, (ii) the polynomials g_{1}, …, g_{n} form a regular sequence of

k[x_{1}, …, x_{n}] = k[y_{1}, …, y_{n}],

(iii) \frac{g_{1}}{α} , …, \frac{g_{n}}{α} is the reduced Groebner basis of J with respect to the lexicographic monomial ordering y_{1} < ⋯ < y_{n}.

In view of the well-known shape lemma (see Kobayashi et al. 1989) the condition (iii) may be restated as follows:

(iv) there exist polynomials r_{1}, …, r_{n} in k[y_{1}] having the same properties as α with respect to the input f_{1}, …, f_{s}, such that g_{1} = r_{1} , g_{2} = αy_{2} − r_{2}, …, g_{n} = αy_{n} − r_{n}. Moreover the polynomials g_{1}, …, g_{n} generate the ideal J.

Let us remark that in the case where s = n the algorithm of Proposition B becomes uniform, while remaining well-parallelizable and having sequential complexity d^{O(n)} . This fact has been used in the past by several authors but has never been stated explicitely in the present form (see Giusti & Heintz 1991b for extensive references). It follows by simple inspection of Proposition B.

For our applications of Propositions A and B it is important to observe that the entries of the matrix M can be chosen from any predetermined subset Γ of k of sufficiently large cardinality, namely of asymptotic order s^{O(1)} d^{O(n)} . In the same spirit, the element α and the coefficients of g_{1}, …, g_{n} are polynomials of degree d^{O(n)} in the coefficients of f_{1}, …, f_{s} over Ω[Γ], where Ω denotes the prime ring of k.

We would like to stress the probabilistic (randomized) character of Propositions A and B. In our formulation these propositions are somewhat stronger than their non-uniform counterparts (compare Balcázar et al. 1988, Section 6.6). We remark also that our actual presentation of the subject differs slightly from that of our earlier paper (Giusti & Heintz 1991b) where we emphasized the non-uniform aspect of the algorithms and where the probabilistic point of view is secondary although not omitted (see Section 2.2 of the quoted paper). However, the proofs of the non-uniform and the probabilistic versions of the statements in Giusti & Heintz (1991b) are textually the same. They rely on an iterated use of Heintz & Schnorr (1982), Theorem 4.4, whose formulation is of probabilistic nature.

2. The main result

We prove the following.

Theorem. Let k be a perfect and infinite field, x_{1}, …, x_{n} indeterminates over k, and f_{1}, …, f_{s} polynomials whose degrees are bounded by a given integer d satisfying d ≥ n. There exists a randomized algorithm of sequential time complexity s^{O(1)} d^{O(n)} and parallel time complexity O(n^{4} log^{2} sd) which decides the triviality of the ideal (f_{1}, …, f_{s}). If the ideal (f_{1}, …, f_{s}) is trivial, the algorithm produces a straight-line program of size s^{O(1)} d^{O(n)} and depth O(n^{4} log^{2} sd) in k(x_{1}, …, x_{n}) which computes polynomials p_{1}, …, p_{s} ∈ k[x_{1}, …, x_{n}] of degree d^{O(n^{2})} satisfying

1 = ∑_{1≤j≤s} p_{j}f_{j} .

This result completes the affine effective Nullstellensätze of Brownawell (1987), Caniglia, Galligo & Heintz (1989) (see also Caniglia, Galligo & Heintz 1988) and Kollár (1988).

For a survey of methods and achievements on this subject we refer the reader to (Teissier 1991) (see also Fitchas & Galligo 1990 and Caniglia et al. 1991 for elementary techniques and applications to Computer Science).

The theorem above was pointed out to us in 1988 as an open question by E. Kaltofen. It is motivated by the following problem: the affine effective Nullstellensatz in the version of (Kollár 1988) (see also Fitchas & Galligo 1990, Théorème 1) has for d ≥ 3 and n ≥ 2 the following form: the ideal (f_{1}, …, f_{s}) is trivial if and only if there exist polynomi-

als p_{1}, …, p_{s} ∈ k[x_{1}, …, x_{n}] such that 1 = ∑_{1≤j≤s} p_{j}f_{j} and max{deg p_{j}f_{j};

1 ≤ j ≤ s} ≤ d^{n}.

From a well-known example discovered by Mora-Lazard and independently by Masser-Philippon (see Brownawell 1987) we deduce that the single exponential degree bound d^{n} of this Nullstellensatz is asymptotically optimal.

If we use this theorem for the design of an algorithm which decides the triviality of the ideal (f_{1}, …, f_{s}) we obtain a uniform, well-parallelizable algorithm of sequential time complexity s^{O(1)} d^{O(n^{2})} . This is the kind of complexity result obtained by Dickenstein et al. (1991), which is still the best known uniform one on questions treated in loc. cit. including the problem of deciding whether a given polynomial equation system can be solved in an algebraically closed field.

The algorithm mentioned above not only decides whether the ideal (f_{1}, …, f_{s}) is trivial but produces also polynomials p_{1}, …, p_{s} ∈ k[x_{1}, …, x_{n}] of degree bounded by d^{n} which satisfy 1 = ∑_{1≤j≤s} p_{j}f_{j} if such a relation exists.

These polynomials are given in dense representation which is of size O(sd^{n^{2}}). This size cannot be reduced because of the example due to Mora-Lazard and Masser-Philippon. This means that the approach to the algorithmic triviality problem for polynomial ideals by means of Nullstellensätze from Commutative Algebra leads necessarily to complexity bounds which are singly exponential in the size of the input, which is of order O(sd^{n}).

The only way out of this dilemma is to renounce exhibition of the relation 1 = ∑_{1≤j≤s} p_{j}f_{j} if the ideal is trivial or to change the data structure

representing the polynomials p_{1}, …, p_{s}. The first alternative is treated in (Giusti & Heintz 1991b) by a well-parallelizable algorithm with a randomized (respectively non-uniform) sequential time complexity bound of order s^{O(1)} d^{O(n)} (see Section 1.2.4., Proposition A). The second one is the subject of the present paper: we represent p_{1}, …, p_{s} by a straight-line program of size s^{O(1)} d^{O(n)} in k(x_{1}, …, x_{n}) (this means that the size of the straight-line program representing the output p_{1}, …, p_{s} is polynomial in the size of the input f_{1}, …, f_{s}). The parallel complexity bound of O(n^{4} log^{2} sd) which we obtain in our main result (the theorem above) is the same as the one obtained using dense representation of polynomials and the best known degree bound of d^{n} for d ≥ 3 and n ≥ 2 in the effective affine Nullstellensatz of Commutative Algebra (see, e.g., Fitchas & Galligo 1990, Théorème 1). As we said before, this latter technique leads to a sequential complexity bound of s^{O(1)}d^{O(n^{2})} which is singly exponential in the size of the input.

Combining our main result with (Valiant et al. 1983, Theorem 2), we are able to improve the mentioned parallel complexity bound to O(n^{3} log^{2} d). However this procedure increases the (simultaneous) sequential complexity to s^{O(1)}d^{O(n^{2})} .

Unfortunately the polynomials p_{1}, …, p_{s} we obtain have degrees of order d^{O(n^{2})} and we are not able to lower this bound to d^{O(n)} by the techniques which we use in this paper. Consequently we are not able to eliminate the divisions in the straight-line program representing the polynomials. Moreover our algorithm has depth O(n^{4} log^{2} sd) and is therefore not well-parallelizable in the sense of Section 1.2.3.

Let us finally remark that after acceptance of the present paper we were able to answer to the affirmative the open question concerning degrees and divisions. However the proofs are based on different and much more involved techniques from Commutative Algebra and will be given elsewhere.

3. Proofs

3.1. Checking the triviality of the ideal (f_{1}, …, f_{s}) (f_{1}, …, f_{s}) (f_{1}, …, f_{s}). We maintain the notation and conventions introduced in 1.1. Throughout this section let f_{1}, …, f_{s} be a fixed family of polynomials of k[x_{1}, …, x_{n}] whose degrees are bounded by a given integer d satisfying d ≥ n. By means of Proposition A, we are able to decide by a well-parallelizable randomized algorithm in sequential time s^{O(1)} d^{O(n)} whether the polynomials f_{1}, …, f_{s} have no common zero in A^{n}. For the proof of our main result, the theorem of Section 2, it suffices therefore to suppose that f_{1}, …, f_{s} generate the trivial ideal of k[x_{1}, …, x_{n}]. We make this assumption for the rest of the paper.

3.2. Preparation of the input data. Let σ = (n + 1)s. We consider the family of polynomials

g_{1} = f_{1}, …, g_{s} = f_{s}
g_{s+1} = x_{1}f_{1}, …, g_{s+n} = x_{n}f_{1}
…
g_{(n+1)s−n+1} = x_{1}f_{s}, …, g_{σ} = g_{(n+1)s} = x_{n}f_{s}.

Observe that the degrees of g_{1}, …, g_{σ} are bounded by d + 1 and that g_{1}, …, g_{σ} generate the trivial ideal of k[x_{1}, …, x_{n}].

For 1 ≤ j ≤ s let U_{j} = A_{f_{j}}^{n} = {x ∈ A^{n}; f_{j}(x) ≠ 0} and let Φ_{j} : U_{j} → A^{σ−1} be the morphism of affine varieties defined by

Φ_{j}(x) := (\frac{g_{1}(x)}{f_{j}(x)}, …, \frac{g_{j−1}(x)}{f_{j}(x)}, \frac{g_{j+1}(x)}{f_{j}(x)}, …, \frac{g_{σ}(x)}{f_{j}(x)})

for x ∈ U_{j}.

By construction, Φ_{j} is unramified and the Zariski closure of its image is an irreducible subvariety of A^{σ−1} of dimension n. The finite family (U_{j})_{1≤j≤s} forms an open covering of A^{n}.

Let f′_{1}, …, f′_{n+1} be a family of generic k -linear combinations of g_{1}, …, g_{σ}. The degrees of the polynomials f′_{1}, …, f′_{n+1} are bounded by d + 1 and they generate the trivial ideal of k[x_{1}, …, x_{n}].

Now fix i, 0 ≤ i ≤ n − 1.

We analyze the ideal (f′_{1}, …, f′_{n−i}) by means of Bertini’s theorem and the geometric properties of the morphisms Φ_{j}, 1 ≤ j ≤ s.

Let us for the moment fix j, 1 ≤ j ≤ s. First observe that for each

1 ≤ u ≤ n + 1, the rational function \frac{f′_{u}}{f_{j}} is a generic affine k -linear combina-

tion of \frac{g_{1}}{f_{j}} , …, \frac{g_{j−1}}{f_{j}} , \frac{g_{j+1}}{f_{j}} , …, \frac{g_{σ}}{f_{j}} . We use Bertini’s Theorem in the version

of (Jouanolou 1983, Corollaire 6.7). Applied to our context it has the following form: the fact that Φ_{j} is an unramified morphism from the irreducible smooth affine variety U_{j} to the affine space A^{σ−1} having an n-dimensional image and being defined by the rational functions \frac{g_{1}}{f_{j}} , …, \frac{g_{j−1}}{f_{j}} , \frac{g_{j+1}}{f_{j}} , …, \frac{g_{σ}}{f_{j}} ,

implies that any set of at most n generic affine linear combinations of \frac{g_{1}}{f_{j}} , …, \frac{g_{j−1}}{f_{j}} , \frac{g_{j+1}}{f_{j}} , …, \frac{g_{σ}}{f_{j}} defines a (nonempty) smooth affine subvariety of

U_{j} and generates a (proper) radical ideal of the fraction ring k[x_{1}, …, x_{n}]_{f_{j}}.

Thus the rational functions \frac{f′_{1}}{f_{j}} , …, \frac{f′_{n−i}}{f_{j}} define a smooth subvariety of U_{j}

of dimension i and generate a radical ideal of k[x_{1}, …, x_{n}]_{f_{j}}. (In fact the variety is irreducible and the ideal is prime for 1 ≤ i ≤ n − 1.) Since the U_{j}, for 1 ≤ j ≤ s, form an open covering of A^{n} we conclude that the subvariety of A^{n} defined by f′_{1}, …, f′_{n−i} is smooth and of dimension i, and that the ideal (f′_{1}, …, f′_{n−i}) is radical for every 0 ≤ i ≤ n − 1. (We call an eventually reducible closed subvariety of A^{n} smooth if it is equidimensional and all its local rings are regular.) In particular f′_{1}, …, f′_{n} form a regular sequence of k[x_{1}, …, x_{n}].

For each 1 ≤ i ≤ n + 1 we introduce new indeterminates T_{1}^{(i)}, …, T_{σ}^{(i)} which we shall consider as computational parameters in the argument which follows (see Heintz & Giusti 1991b, Section 1.2.2 and Section 1.2.2 of the present paper for this technique).

Let R = k[T_{q}^{(i)}; 1 ≤ i ≤ n+1, 1 ≤ q ≤ σ] and let K be the fraction field of R. Let \overline{K} be an algebraic closure of K. For 1 ≤ i ≤ n + 1 we consider the polynomial F_{i} = T_{1}^{(i)}g_{1} + ⋯ + T_{σ}^{(i)}g_{σ} of R[x_{1}, …, x_{n}]. The degree of F_{i} in the main variables x_{1}, …, x_{n} is bounded by d + 1 and F_{i} is linear in the parameters T_{1}^{(i)}, …, T_{σ}^{(i)} .

From Bertini’s Theorem we deduce the following facts:

(a) the polynomials F_{1}, …, F_{n+1} have no common zeros in A^{n}(\overline{K}),

(b) for each 0 ≤ i ≤ n − 1 the polynomials F_{1}, …, F_{n−i} generate a radical ideal of K[x_{1}, …, x_{n}] and define a smooth subvariety of A^{n}(\overline{K}) of dimension i.

For 0 ≤ i ≤ n−1 let r_{i} = \binom{n − i}{i} and let Δ_{1}^{(n−i)}, …, Δ_{r_{i}}^{(n−i)} denote the

n − i minors of the Jacobian matrix of F_{1}, …, F_{n−i}. We have r_{i} ≤ n^{i} ≤ d^{i}, hence r_{i} is of order d^{n}. Δ_{1}^{(n−i)}, …, Δ_{r_{i}}^{(n−i)} are polynomials of R[x_{1}, …, x_{n}] whose degrees in the main variables x_{1}, …, x_{n} are bounded by (n − i)d and whose degrees in the parameters T_{q}^{(1)}, …, T_{q}^{(i)} , where 1 ≤ q ≤ σ, do not exceed n − i.

By means of the Jacobian criterion for smooth varieties we can restate property (b) as follows:

(c) the polynomials F_{1}, …, F_{n−i} define a subvariety of dimension i of A^{n}(\overline{K}), and the variety defined by F_{1}, …, F_{n−i}, Δ_{1}^{(n−i)}, …, Δ_{r_{i}}^{(n−i)} is empty.

We are now ready to construct the polynomials f′_{1}, …, f′_{n+1} algorithmically.

Lemma 3.2.1. Suppose that f_{1}, …, f_{s} generate the trivial ideal of k[x_{1}, …, x_{n}]. Then there exists a well-parallelizable randomized algorithm which constructs from the inputs f_{1}, …, f_{s} in sequential time s^{O(1)} d^{O(n)} polynomials f′_{1}, …, f′_{n+1} of k[x_{1}, …, x_{n}] of degree at most d + 1 having the following properties:

(1) the polynomials f′_{1}, …, f′_{n+1} generate the trivial ideal of k[x_{1}, …, x_{n}],

(2) for each 0 ≤ i ≤ n−1 the polynomials f′_{1}, …, f′_{n−i} generate a radical ideal of k[x_{1}, …, x_{n}] and define a smooth subvariety of A^{n} of dimension i,

(3) the polynomials f′_{1}, …, f′_{n+1} belong to the k -linear subspace of k[x_{1}, …, x_{n}] generated by the polynomials f_{1}, …, f_{s}, x_{1}f_{1}, …, x_{1}f_{s}, …, x_{n}f_{1}, …, x_{n}f_{s}.

Proof. We maintain the notation introduced above. For γ ∈ A^{(n+1)σ} we denote by f_{1}^{(γ)}, …, f_{n+1}^{(γ)} the polynomials which we obtain from F_{1}, …, F_{n+1} by substituting the parameters T_{q}^{(1)}, …, T_{q}^{(n+1)} , 1 ≤ q ≤ σ, with the coordinates of γ.

Our proof follows the arguments of (Giusti & Heintz 1991b, Section 3.7.2).

For each −1 ≤ i ≤ n − 1 we apply the algorithm of Section 1.2.4, Proposition A (1) to the polynomials F_{1}, …, F_{n−i} of R[x_{1}, …, x_{n}], and for each 0 ≤ i ≤ n − 1 we apply the same algorithm to the polynomials F_{1}, …, F_{n−i}, Δ_{1}^{(n−i)}, …, Δ_{r_{i}}^{(n−i)} . The whole procedure computes during its execution a family of nonzero elements Q_{1}, …, Q_{N} of R which are represented by a straight-line program without divisions of size v, where the integers N and v are of order s^{O(1)} d^{O(n)} . The intermediate results Q_{1}, …, Q_{N} are polynomials in the parameters T_{q}^{(1)}, …, T_{q}^{(n+1)} , 1 ≤ q ≤ σ, with coefficients in k and their degrees are bounded by d^{cn}, where c > 0 is a suitable constant. Without loss of generality we may assume that we have chosen only correct test sequences for the execution of the procedure. Under these circumstances the polynomials Q_{1}, …, Q_{N} satisfy the following condition: for any γ ∈ A^{(n+1)σ} such that Q_{1}(γ) ≠ 0, …, Q_{N}(γ) ≠ 0, the polynomials f_{1}^{(γ)}, …, f_{n+1}^{(γ)} have the properties (1), (2) and (3) of the lemma. This follows from the observations at the beginning of this section and the specific features of the algorithm that leads to Proposition A (see Giusti & Heintz 1991b for technical details).

Let Q = Q_{1} … Q_{N}. Without loss of generality we may assume that deg Q ≤ d^{cn} holds and that Q is computable by a straight-line program of size at most v.

Let Γ be any subset of k of cardinality #Γ = 2v(1 + d^{cn})^{2} and let m = 6(v + (n + 1)σ)(v + (n + 1)σ + 1). Obviously we have #Γ = s^{O(1)}d^{O(n)} and m = s^{O(1)}d^{O(n)} . Following (Heintz & Schnorr 1982, Theorem 4.4), there exists at least (#Γ)^{(n+1)σm}(1 − (#Γ)^{− \frac{m}{6}} ) correct test sequences of m points of Γ^{(n+1)σ} for the class of (n+1)σ -variate polynomials of degree bounded by d^{cn} which can be evaluated by straight-line programs of size at most v. Let us choose such a correct test sequence (γ_{1}, …, γ_{m}) of points of Γ^{(n+1)σ}. (This choice doesn’t depend on the input f_{1}, …, f_{s} but only on the parameters d, s and n and can be done randomly with a probability of failure of at

most (#Γ)^{− \frac{m}{6}} ≪ ε = \frac{1}{262144} < \frac{1}{2} , or alternatively by a preprocessing of the algorithm. See Section 1.2.3.)

We run the straight-line program without divisions which computes Q_{1}, …, Q_{N} for each γ_{ℓ}, 1 ≤ ℓ ≤ m. This can be done by a wellparallelizable algorithm using s^{O(1)}d^{O(n)} arithmetic operations in k. Since the nonzero polynomial Q = Q_{1} … Q_{N} can be evaluated by a straight-line program of size at most v and has degree bounded by d^{cn}, there exists a point γ = γ_{ℓ}, 1 ≤ ℓ ≤ m such that Q(γ) ≠ 0. Therefore we have Q_{1}(γ) ≠ 0, …, Q_{N}(γ) ≠ 0. We find the point γ in non-uniform sequential time s^{O(1)}d^{O(n)} using the well-parallelizable algorithm indicated above. The polynomials f′_{1} = f_{1}^{(γ)}, …, f′_{n+1} = f_{n+1}^{(γ)} satisfy the conditions (1), (2) and (3) of the lemma.

Notation and basic assumptions.

In view of Lemma 3.2.1, let us from now on always suppose that our input polynomials f_{1}, …, f_{s} satisfy the following conditions:

• s = n + 1

• f_{1}, …, f_{n+1} generate the trivial ideal of k[x_{1}, …, x_{n}]

• for each 0 ≤ i ≤ n − 1 the polynomials f_{1}, …, f_{n−i} generate a radical ideal of k[x_{1}, …, x_{n}] and define a smooth variety V_{i} = V (f_{1}, …, f_{n−i}) of dimension i.

Moreover, applying the algorithm that implies statement (2) of Proposition A of Section 1.2.4 to the input data f_{1}, …, f_{n+1} we shall from now on always suppose that • the variables x_{1}, …, x_{n} are in Noether position with respect to all vari-

eties V_{i}, for 0 ≤ i ≤ n − 1.

We call a family of polynomials f_{1}, …, f_{n+1} satisfying all these conditions a normalized input.

Let 0 ≤ i ≤ n − 1. We fix the following notation and definitions for the rest of this paper :

A_{i} = k[x_{1}, …, x_{i}] ; K_{i} = k(x_{1}, …, x_{i}) ;

ℑ_{i} is the ideal generated by f_{1}, …, f_{n−i} in A_{i}[x_{i+1}, …, x_{n}] =

k[x_{1}, …, x_{n}] ;

ℑ′_{i} is the ideal generated by f_{1}, …, f_{n−i} in K_{i}[x_{i+1}, …, x_{n}] =

k(x_{1}, …, x_{i})[x_{i+1}, …, x_{n}] ;
B_{i} = k[x_{1}, …, x_{n}]/ℑ_{i} and B′_{i} = K_{i}[x_{i+1}, …, x_{n}]/ℑ′_{i}.

Moreover let \overline{K_{i}} be an algebraic closure of K_{i}. Let V_{i} = V (ℑ_{i}) be the algebraic variety defined by f_{1}, …, f_{n−i} in A^{n} and let V′_{i} = V (ℑ′_{i}) be the algebraic variety defined by f_{1}, …, f_{n−i} in A^{n}(\overline{K_{i}}). From our assumptions it follows that V_{i} is smooth of dimension i, that V′_{i} is zero dimensional and that ℑ_{i} and ℑ′_{i} are radical ideals. Therefore the polynomials f_{1}, …, f_{n−i} form a regular sequence in the Cohen-Macaulay rings k[x_{1}, …, x_{n}] and K_{i}[x_{i+1}, …, x_{n}].

We consider B_{i} as an A_{i} -algebra and B′_{i} as a K_{i} -algebra. Since the variables x_{1}, …, x_{n} are in Noether position with respect to V_{i}, the algebra B_{i} is a finite A_{i} -module and B′_{i} is a finite dimensional K_{i} -vector space. The canonical homomorphisms A_{i} → B_{i} and K_{i} → B′_{i} are integral extensions. Since A_{i} is a polynomial algebra over the field k, the k -algebra A_{i} is a gaussian (factorial) domain and therefore integrally closed in its fraction field K_{i}. Let D_{i} = dim_{K_{i}} B′_{i}. Taking into account that the variables x_{1}, …, x_{n} are in Noether position with respect to V_{i} and that ℑ_{i} and ℑ′_{i} are radical ideals, one deduces easily from the different versions of the Bézout Inequality that D_{i} ≤ deg V_{i} ≤ d^{n−i} holds (see, e.g., Heintz 1983, Theorem 1, and Caniglia, Galligo & Heintz 1989, Proposition 5).

3.3. Some commutative algebra. The following lemma is well-known (see for example Rossi & Spangher 1991, Proposition 3.4). We give its proof for lack of suitable reference.

Lemma 3.3.1. Let 0 ≤ i ≤ n − 1 and let g_{1}, …, g_{n−i} be a sequence of polynomials of k[x_{1}, …, x_{n}] which define an algebraic variety V = {g_{1} = 0, …, g_{n−i} = 0} of dimension i. Suppose that x_{1}, …, x_{n} are in Noether position with respect to V . Let A = k[x_{1}, …, x_{i}] and consider the k -algebra B = k[x_{1}, …, x_{n}]/(g_{1}, …, g_{n−i}) as an A-module. Then B is free of finite positive rank.

Proof. We proceed by induction on i. For the case i = 0 we observe that A = k and that B = k[x_{1}, …, x_{n}]/(g_{1}, …, g_{n}) is a k -vector space of finite positive dimension. Hence B is a free A-module of finite positive rank. It suffices now to show the lemma for fixed 0 < i ≤ n − 1 supposing it true for i − 1.

Since dim V = i and since the variables x_{1}, …, x_{n} are in Noether position with respect to V the k -algebra B is a finite non-trivial A-module. Moreover A is a polynomial ring over the field k. Therefore, if B is a projective A-module, then B is free of finite positive rank by the Quillen-Suslin Theorem (Lam 1978, Chapter III, Theorem 1.8).

Therefore we show that B is projective.

First observe that \overline{k} ⊗_{k} A is a faithfully flat A-algebra. Thus \overline{k} ⊗_{k} B = (\overline{k}⊗_{k}A)⊗_{A}B is a projective \overline{k}⊗_{k}A-module if and only if B is a projective Amodule (Lam 1978, Chapter I, Proposition 2.15). Therefore we may suppose without loss of generality that k is algebraically closed.

Since B is a finite A-module it suffices to show that for any maximal ideal M of A the localized A_{M} -module B_{M} is free.

Let M be a maximal ideal of A = k[x_{1}, …, x_{i}]. Since k is by assumption algebraically closed there exist elements α_{1}, …, α_{i} of k such that M = (x_{1} − α_{1}, …, x_{i} − α_{i}). Without loss of generality we may assume α_{1} = ⋯ = α_{i} = 0. Thus M = (x_{1}, …, x_{i}). Since the variables x_{1}, …, x_{n} are in Noether position with respect to V = {g_{1} = 0, …, g_{n−i} = 0}, the variety V ∩ {x_{i} = 0} = {g_{1} = 0, …, g_{n−i} = 0, x_{i} = 0} is (i − 1)- dimensional and in particular nonempty. From this we conclude that the polynomials g_{1}, …, g_{n−i}, x_{i} satisfy the hypothesis of the lemma for i−1 and that they form a regular sequence in the Cohen-Macaulay ring k[x_{1}, …, x_{n}] (see Matsumura 1989, Theorem 17.7). Therefore x_{i}, seen as an element of B = k[x_{1}, …, x_{n}]/(g_{1}, …, g_{n−i}), is not a zero divisor.

Let \overline{A} = k[x_{1}, …, x_{i−1}] and \overline{B} = k[x_{1}, …, x_{n}]/(g_{1}, …, g_{n−i}, x_{i}). By our induction hypothesis \overline{B} is a free \overline{A}-module of finite rank. Let : B → \overline{B} be the canonical k -algebra homomorphism. This homomorphism induces on \overline{A} = k[x_{1}, …, x_{i−1}] the identity and maps M to the maximal ideal \overline{M} = (x_{1}, …, x_{i−1}) of \overline{A}. Let e_{1}, …, e_{N} be elements of B such that \overline{e_{1}}, …, \overline{e_{N}} form a basis of the free \overline{A}-module \overline{B}. Thus 1 ⊗ e_{1}, …, 1 ⊗ e_{N} generate the A/M-vector space

A/M ⊗_{A} B ≅ B/M ≅ \overline{B}/\overline{M} ≅ \overline{A}/\overline{M} ⊗_{A} \overline{B} .

Denote by e′_{1}, …, e′_{N} the images of e_{1}, …, e_{N} in B_{M} and by (\overline{e_{1}})′, …, (\overline{e_{N}})′ their images in \overline{B}\overline{M}. From Nakayama’s Lemma we conclude that e′_{1}, …, e′_{N} generate the A_{M} -module B_{M}. To finish the proof we are going to show that e′_{1}, …, e′_{N} form a free generator system.

Suppose on the contrary that there exists a nontrivial linear relation

(1)  a_{1}e′_{1} + ⋯ + a_{N}e′_{N} = 0

in B_{M}, where a_{1}, …, a_{N} are elements from A_{M}, not all zero. Without loss of generality we may assume a_{1}, …, a_{N} belong to A = k[x_{1}, …, x_{i}]. Dividing by a maximal power of x_{i} we obtain representations

a_{1} = x_{i}^{ℓ}a′_{1}, …, a_{N} = x_{i}^{ℓ}a′_{N} ,

where a′_{1}, …, a′_{N} are elements of A, not all divisible by x_{i}, and ℓ is a nonnegative integer. Thus we obtain from (1) the equality

x_{i}^{ℓ}(a′_{1}e′_{1} + ⋯ + a′_{N}e′_{N}) = 0

which holds in B_{M}. Since x_{i} is not a zero divisor of B we conclude

a′_{1}e′_{1} + ⋯ + a′_{N}e′_{N} = 0 .

Hence we may suppose without loss of generality that a_{1} is an element of A which is not divisible by x_{i}. Thus the relation (1) implies that

(2)  \overline{a_{1}}(\overline{e_{1}})′ + ⋯ + \overline{a_{N}}(\overline{e_{N}})′ = 0

holds in \overline{B}\overline{M} with \overline{a_{1}}, …, \overline{a_{N}} ∈ \overline{A}\overline{M}, \overline{a_{1}} ≠ 0.

Since \overline{e_{1}}, …, \overline{e_{N}} form a basis of the \overline{A}-module \overline{B}, the elements (\overline{e_{1}})′, …, \overline{e_{N}})′ of \overline{B}\overline{M} are linearly independent over \overline{A}\overline{M}. This contradicts the equality (2).

Let us maintain the notation and the assumptions introduced in Section 3.2.

From Lemma 3.3.1 we obtain Corollary 3.3.2. For any 0 ≤ i ≤ n − 1 the A_{i} -algebra B_{i} is a free A_{i} -module of positive rank D_{i} ≤ d^{n−i}.

(Recall A_{i} = k[x_{1}, …, x_{i}], B_{i} = k[x_{1}, …, x_{n}]/(f_{1}, …, f_{n−i}), D_{i} = dim_{K_{i}} B′_{i} = dim_{k(x_{1},...,x_{i})} k(x_{1}, …, x_{i})[x_{i+1}, …, x_{n}]/(f_{1}, …, f_{n−i})).

Proof. Let 0 ≤ i ≤ n − 1. By assumption (see Section 3.2) the polynomials f_{1}, …, f_{n−i} define an algebraic variety V_{i} of dimension i and x_{1}, …, x_{n} are in Noether position with respect to V_{i}. Therefore by Lemma 3.3.1 the A_{i} - algebra B_{i} is a free A_{i} -module of finite positive rank. Since K_{i} is the fraction field of A_{i} this rank is dim_{K_{i}} K_{i} ⊗_{A_{i}} B_{i} = dim_{K_{i}} B′_{i} = D_{i} ≤ deg V_{i} ≤ d^{n−i}.

Lemma 3.3.3. Let 0 ≤ i ≤ n − 1 and let f be a polynomial of k[x_{1}, …, x_{n}]. Multiplication by f induces on the D_{i} -dimensional K_{i} -vector space B′_{i} a linear endomorphism Φ. Let T be a new indeterminate and let χ_{f} ∈ K_{i}[T] be the characteristic polynomial of the linear endomorphism Φ. Let χ_{f} = T^{D_{i}} + φ_{D_{i}−1}T^{D_{i}−1} +⋯+φ_{0} with φ_{D_{i}−1}, …, φ_{0} ∈ K_{i}. Then φ_{D_{i}−1}, …, φ_{0} are elements of A_{i} whose degrees are bounded by i(deg V_{i})^{2} deg f ≤ id^{2(n−i)} deg f.

(Recall

\begin{aligned}A_{i} & = k[x_{1}, …, x_{i}] \\ K_{i} & = k(x_{1}, …, x_{i}) \\ B_{i} & = k[x_{1}, …, x_{n}]/(f_{1}, …, f_{n−i}) \\ B′_{i} & = K_{i}[x_{i+1}, …, x_{n}]/(f_{1}, …, f_{n−i}) \end{aligned}

and D_{i} ≤ deg V_{i} ≤ d^{n−i}.)

Proof. For the sake of notational simplicity let A = A_{i}, K = K_{i}, B = B_{i}, B′ = B′_{i}, ℑ = ℑ_{i}, V = V_{i} and D = D_{i}. Thus Φ is the K -linear endomorphism of B′ induced by f.

Since by Corollary 3.3.2 the A-module B is free we may consider a basis e_{1}, …, e_{D} of it. Let e′_{1}, …, e′_{D} be the corresponding basis of the K_{i} -vector space B′. Since the polynomial f induces an A-linear endomorphism of B, the matrix M_{f} of Φ with respect to the basis e′_{1}, …, e′_{D} of B′ has entries in the polynomial ring A. This implies that φ_{D−1}, …, φ_{0} are elements of A.

Now observe that \overline{k} ⊗_{k} K is a field (specifically the fraction field of the domain \overline{k} ⊗_{k} A) and that \overline{k} ⊗_{k} B′ is a D -dimensional \overline{k} ⊗_{k} K - vector space with basis 1 ⊗ e′_{1}, …, 1 ⊗ e′_{D}. The polynomial f induces a \overline{k} ⊗_{k} K -linear endomorphism of \overline{k} ⊗_{k} B′ whose matrix with respect to 1 ⊗ e′_{1}, …, 1 ⊗ e′_{D} is M_{f}. Therefore the characteristic polynomial of the linear endomorphism induced by f remains unchanged if we extend the base field k to the algebraically closed one \overline{k}. Moreover \overline{k} ⊗_{k} B is a free \overline{k} ⊗_{k} A-module of rank D on which f induces a \overline{k} ⊗_{k} Alinear endomorphism. We have \overline{k} ⊗_{k} B ≅ \overline{k}[x_{1}, …, x_{n}]/(f_{1}, …, f_{n−i}) and \overline{k} ⊗_{k} B′ ≅ \overline{k}(x_{1}, …, x_{i})[x_{i+1}, …, x_{n}]/(f_{1}, …, f_{n−i}). Furthermore the polynomials f_{1}, …, f_{n−i} generate radical ideals of \overline{k}[x_{1}, …, x_{n}] and \overline{k}(x_{1}, …, x_{i})[x_{i+1}, …, x_{n}].

Thus, for the rest of the proof, we may assume without loss of generality that k is algebraically closed.

Since ℑ = (f_{1}, …, f_{n−i}) is a radical ideal of k[x_{1}, …, x_{n}] defining a i-dimensional algebraic variety, it can be written uniquely as

ℑ = ℘_{1} ∩ … ∩ ℘_{r} ,

where ℘_{1}, …, ℘_{r} are prime ideals of k[x_{1}, …, x_{n}] of height n − i. The prime ideals ℘_{1}, …, ℘_{r} define the irreducible components C_{1}, …, C_{r} of the algebraic variety V which is given by ℑ. Observe that dim C_{1} = ⋯ = dim C_{r} = i.

Let us show the following claim: for any 1 ≤ ℓ ≤ r the ideals ℘_{ℓ} and ⋂_{j≠ℓ} ℘_{j} are coprime. In geometrical terms this means that C_{1}, …, C_{r} are the

connected components of V with respect to the Zariski topology.

Let x be any point of V and let M be the maximal ideal of k[x_{1}, …, x_{n}] defining x. Since the ideal ℑ is radical and since B = k[x_{1}, …, x_{n}]/ℑ, we see that B_{M} is the local ring of the point x. On the other hand the variety V is smooth. Therefore B_{M} is regular and hence a domain. This implies that M contains exactly one of the prime ideals ℘_{1}, …, ℘_{r}. Thus x is contained in exactly one irreducible component of V . Since these are connected and the point x was arbitrarily chosen our claim follows.

For 1 ≤ ℓ ≤ r let R_{ℓ} be the coordinate ring of C_{ℓ}. Thus R_{ℓ} ≅

k[x_{1}, …, x_{n}]/℘_{ℓ}. Since B = k[x_{1}, …, x_{n}]/ℑ = k[x_{1}, …, x_{n}]/ ⋂_{1≤ℓ≤r} ℘_{ℓ} and

all the ideals ℘_{ℓ} + ⋂_{j≠ℓ} ℘_{j}, 1 ≤ ℓ ≤ r, are trivial we deduce from the Chinese

Remainder Theorem that B and ∏_{1≤ℓ≤r} R_{ℓ} are isomorphic A-algebras.

Let 1 ≤ ℓ ≤ r. Since R_{ℓ} is a direct summand of B, it is a projective A-module and, by the Quillen-Suslin Theorem, even free. Let R′_{ℓ} be the local ring of the generic fibre of the canonical projection π_{ℓ} : C_{ℓ} → A^{i} induced by the variables x_{1}, …, x_{i}. In algebraic terms we may define R′_{ℓ} as

R′_{ℓ} = K ⊗_{A} R_{ℓ} ≅ k(x_{1}, …, x_{i}) ⊗_{k[x_{1},...,x_{i}]} ( k[x^{1}, …, x^{n}]/℘_{ℓ} ) .

The local ring R′_{ℓ} is a finite dimensional K -algebra of dimension m_{ℓ} = dim_{K} R′_{ℓ}. From the Bézout Inequality we deduce m_{ℓ} ≤ deg C_{ℓ}.

We denote by ψ_{ℓ} both the A-linear and the K -linear map induced by the multiplication by the polynomial f on R_{ℓ} and on R′_{ℓ}. Let T be a new indeterminate and let χ_{ψ_{ℓ}} = T^{m_{ℓ}} + γ_{m_{ℓ}−1}^{(ℓ)}T^{m_{ℓ}−1} + … + γ_{0}^{(ℓ)} where γ_{m_{ℓ}−1}^{(ℓ)}, …, γ_{0}^{(ℓ)} ∈ K is the characteristic polynomial of the K -linear map ψ_{ℓ}. Since ψ_{ℓ} is also a A-linear endomorphism of R_{ℓ} we have as before γ_{m_{ℓ}−1}^{(ℓ)}, …, γ_{0}^{(ℓ)} ∈ A. Observe that the K -linear map Φ acts on

B′ ≅ ∏_{1≤ℓ≤r} R′_{ℓ} diagonally. Thus χ_{f} = ∏_{1≤ℓ≤r} χ_{ψ_{ℓ}}.

We show the following claim: the degrees of the polynomials γ_{m_{ℓ}−1}^{(ℓ)}, …, γ_{0}^{(ℓ)} of A = k[x_{1}, …, x_{i}] are bounded by i(deg C_{ℓ})^{2} deg f.

Then deg V = ∑_{1≤ℓ≤r} deg C_{ℓ} implies that the degrees of the coeffi-

cients φ_{D−1}, …, φ_{0} of the characteristic polynomial χ_{f} are bounded by i(deg V)^{2} deg f, whence the assertion of Lemma 3.3.3.

For the rest of the proof fix 1 ≤ ℓ ≤ r.

In order to simplify notation let ℘ = ℘_{ℓ}, R = R_{ℓ}, R′ = R′_{ℓ}, C = C_{ℓ}, ψ = ψ_{ℓ}, M = M_{ℓ}, γ_{m−1} = γ_{m_{ℓ}−1}^{(ℓ)}, …, γ_{0} = γ_{0}^{(ℓ)} and χ_{ψ} = χ_{ψ_{ℓ}}.

We observe that the irreducible algebraic variety C is of dimension i and that the variables x_{1}, …, x_{n} are in Noether position with respect to C. The variables x_{1}, …, x_{i} induce a projection map π : C → A^{i} which is a finite surjective morphism of algebraic varieties. Therefore the coordinate ring R of C is an integral extension of A = k[x_{1}, …, x_{i}]. Moreover R′ is the fraction field of R and a finite extension of K = k(x_{1}, …, x_{i}). Thus we have the following embeddings of domains and fields:

\begin{aligned}A & ⊂ & R \\ ∩ & & ∩ \\ K & ⊂ & R′ \end{aligned}

Since R is isomorphic to k[x_{1}, …, x_{n}]/℘, to the polynomial f there corresponds an image, say g, in R which induces the A-linear (and K - linear) map ψ. The element g of R and the K -linear map ψ have the same minimal polynomial μ ∈ K[T]. Since A is integrally closed in its fraction field and g ∈ R is integral over A we have μ ∈ A[T]. Moreover μ is primitive and irreducible with respect to K[T]. Therefore μ is an irreducible polynomial of k[x_{1}, …, x_{i}, T] = A[T].

The minimal polynomial μ has the form

μ = T^{q} + μ_{q−1}T^{q−1} + ⋯ + μ_{0}

with μ_{q−1}, …, μ_{0} ∈ A = k[x_{1}, …, x_{i}]. Since R′ is a finite field extension of degree m, the characteristic polynomial of g, which coincides with χ_{ψ}, is a power of μ. Thus we have χ_{ψ} = μ^{h} with h ≤ m ≤ deg C.

We show now that the degrees of μ_{q−1}, …, μ_{0} are bounded by i deg C deg f. This implies that the degrees of the coefficients γ_{m−1}, …, γ_{0} of χ_{ψ} are bounded by i(deg C)^{2} deg f, and this was our claim.

Let y be any of the variables x_{1}, …, x_{i} appearing in the polynomial μ ∈ k[x_{1}, …, x_{i}, T]. We show that the partial degree deg_{y} μ of μ in y is bounded by deg f . deg C. Without loss of generality we may assume that μ really depends on y (i.e., y appears in one of the monomials of μ). For the sake of definiteness let us assume y = x_{1} . The isomorphism R ≅ k[x_{1}, …, x_{n}]/℘ induces a canonical k -algebra homomorphism : k[x_{1}, …, x_{n}] → R. We have g = \overline{f} and μ(\overline{y}, \overline{x_{2}}, …, \overline{x_{i}}, \overline{f}) = μ(\overline{x_{1}}, …, \overline{x_{i}}, g) = 0. Let Y be a new indeterminate. Since the polynomial μ is irreducible and depends on x_{1} , the elements \overline{x_{2}}, …, \overline{x_{i}}, \overline{f} of R are algebraically independent over k and μ(Y, \overline{x_{2}}, …, \overline{x_{i}}, \overline{f}) is the minimal polynomial of \overline{x}_{1} over k[\overline{x_{2}}, …, \overline{x_{i}}, \overline{f}]. Therefore deg_{x_{1}} μ is bounded by [R′ : k(\overline{x_{2}}, …, \overline{x_{i}}, \overline{f})], the degree of the finite field extension k(\overline{x_{2}}, …, \overline{x_{i}}, \overline{f}) ⊂ R′. (Observe that i = dim C is the transcendence degree of the field R′ over k.)

Consider the morphism of affine varieties θ : C → A^{i} defined by the global sections \overline{x_{2}}, …, \overline{x_{i}}, \overline{f} of C. Since these are algebraically independent over k, the morphism θ is dominant and its typical fibre is zero dimensional. Choose a point λ = (λ_{1}, …, λ_{i}) of A^{i} which satisfies dim θ^{−1}(λ) = 0. Thus \overline{x_{2}} −λ_{1}, …, \overline{x_{i}} −λ_{i−1}, \overline{f} −λ_{i} generate a proper ideal B of R whose factor ring R/B has Krull dimension zero. Taking into account that k(\overline{x_{2}} − λ_{1}, …, \overline{x_{i}} − λ_{i−1}, \overline{f} − λ_{i}) = k(\overline{x_{2}}, …, \overline{x_{i}}, \overline{f}), we conclude from Caniglia, Galligo & Heintz (1989), Proposition 5 that [R′ : k(\overline{x_{2}}, …, \overline{x_{i}}, \overline{f})] ≤ deg C . deg f holds. Thus we obtain deg_{y} μ = deg_{x_{1}} μ ≤ deg C . deg f.

Since y was any of the variables x_{1}, …, x_{i} appearing in μ we conclude that the partial degree of μ in x_{1}, …, x_{i} is bounded by i deg C deg f. This means that the degrees of μ_{q−1}, …, μ_{0} are bounded by i deg C deg f.

3.4. Straight-line programs and linear algebra over k[x_{1}, …, x_{i}] k[x_{1}, …, x_{i}] k[x_{1}, …, x_{i}]. During this section we shall keep fixed 1 ≤ i ≤ n − 1. Let us maintain the notation and conventions introduced in 3.1 and 3.2.

Let V = V_{i} be the smooth subvariety of A^{n} of dimension i defined by f_{1}, …, f_{n−i} and ℑ = ℑ_{i} and ℑ′ = ℑ′_{i} the ideals generated by f_{1}, …, f_{n−i} in k[x_{1}, …, x_{n}] and k(x_{1}, …, x_{i})[x_{i+1}, …, x_{n}]. By hypothesis the variables x_{1}, …, x_{n} are in Noether position with respect to V and the ideals ℑ and ℑ′ are radical. Let

A = A_{i} = k[x_{1}, …, x_{i}],
K = K_{i} = k(x_{1}, …, x_{i}),
B = B_{i} = k[x_{1}, …, x_{n}]/(f_{1}, …, f_{n−i}),
B′ = B′_{i} = k(x_{1}, …, x_{i})[x_{i+1}, …, x_{n}]/(f_{1}, …, f_{n−i}),
D = D_{i}.

From Corollary 3.3.2 we deduce that B is a free A-module of finite positive rank D. On the other hand B′ is a D -dimensional vector space over K. We have D ≤ deg V ≤ d^{n−i}.

Let : k[x_{1}, …, x_{n}] → B and : K[x_{i+1}, …, x_{n}] → B′ be the canonical homomorphisms.

Let us consider a polynomial g of k[x_{1}, …, x_{n}]. We denote by \overline{g} the images of g in B and in B′ as well as the A-linear endomorphism of B and the K -linear endomorphism of B′ induced by the multiplication by g. Let T be a new indeterminate. By χ_{g} we denote the characteristic polynomial of the K -linear endomorphism \overline{g} of B′. We consider χ_{g} as an element of K[T]. From Lemma 3.3.3 we deduce that in fact χ_{g} is a polynomial of A[T] = k[x_{1}, …, x_{i}, T] whose total degree does not exceed D+id^{2(n−i)} deg g. More precisely, the coefficients of χ_{g}, which are elements of k[x_{1}, …, x_{i}], have degree at most id^{2(n−i)} deg g.

If M is a D×D matrix with entries from K (in symbols: M ∈ K^{D×D}), we denote by χ_{M} its characteristic polynomial, which belongs to K[T]. We say that M ∈ K^{D×D} is given (or represented) by the straight-line program β in K if β computes all the entries of M. Let M ∈ A^{D×D}. We define deg M, the degree of M, as the maximum of the degrees of all entries of M. The characteristic polynomial χ_{M} belongs to A[T] in this case.

Lemma 3.4.1. Let M ∈ K^{D×D} be a D × D -matrix given by a straight-line program β in K of size L and depth ℓ. Then the coefficients of χ_{M} can be computed by a straight-line program β′ in K of size L + cD^{c} and depth ℓ + c log^{2} D, where c > 0 is a suitable constant not depending on the field K. Moreover β′ can be produced from β in (uniform) sequential time cD^{c} and parallel time c log^{2} D by a division-free arithmetic network over k.

Proof. The algorithm of Berkowitz (1984) computes the coefficients of χ_{M} from the entries of M by a division-free straight-line program of size cD^{c} and depth c log^{2} D, where c > 0 is a constant not depending on K. This implies the lemma.

Lemma 3.4.2. There exists a well-parallelizable randomized algorithm without divisions which computes in sequential time d^{O(n)} from the inputs f_{1}, …, f_{n−i} the following items:

• a non zero polynomial α of A = k[x_{1}, …, x_{i}],

• polynomials h_{1}, …, h_{D} of k[x_{1}, …, x_{n}],

• D × D matrices M_{i+1}, …, M_{n} of A^{D×D}, such that the degrees of α, h_{1}, …, h_{D} and M_{i+1}, …, M_{n} are of order d^{O(n)} , the residue classes \overline{h}_{1}, …, \overline{h}_{D} form a basis of the K -vector space B′, and M_{i+1}, …, M_{n} are the matrices of the K -linear endomorphisms α\overline{x}_{i+1}, …, α\overline{x}_{n} of B′ with respect to the basis \overline{h}_{1}, …, \overline{h}_{D}.

The algorithm represents the polynomial α and the entries of M_{i+1}, …, M_{n} by a division-free and well-parallelizable straight-line program of size d^{O(n)} .

Proof. We consider the indeterminates x_{1}, …, x_{i} as parameters and x_{i+1}, …, x_{n} as main variables (see Section 1.2.2). Thus we shall work in the polynomial algebra A[x_{i+1}, …, x_{n}] over the base ring A = k[x_{1}, …, x_{i}]. Recall that the fraction field of A is K = k(x_{1}, …, x_{i}) and that the ideal ℑ′, generated by the polynomials f_{1}, …, f_{n−i} in K[x_{i+1}, …, x_{n}], is zero dimensional and radical. Applying Proposition B of Section 1.2.4 to this situation one obtains a nonzero polynomial α of A = k[x_{1}, …, x_{i}], polynomials g_{i+1}, …, g_{n} of k[x_{1}, …, x_{n}], and n − i independent linear

forms y_{i+1}, …, y_{n} of k[x_{i+1}, …, x_{n}] such that \frac{g_{i+1}}{α} , …, \frac{g_{n}}{α} is the reduced

Groebner basis of ℑ′ with respect to the lexicographic monomial ordering y_{i+1} < ⋯ < y_{n} of K[y_{i+1}, …, y_{n}] = K[x_{i+1}, …, x_{n}]. The algorithm underlying Proposition B of Section 1.2.4 computes the polynomials α and g_{i+1}, …, g_{n} and the linear forms y_{i+1}, …, y_{n} from the input f_{1}, …, f_{n−i} by a (division-free) randomized (or uniform) arithmetic network over A of size d^{cn} and depth cn^{2} log^{2} d, where c > 0 is a suitable constant not depending on A. Let us observe that possible identity checking of elements of A which may occur during the execution of this algorithm can be performed by a randomized arithmetic network of size d^{cn} and depth cn^{2} log^{2} d over k by means of (Heintz & Schnorr 1982, Theorem 4.4; see Giusti & Heintz 1991b for details of this technique). This converts the arithmetic network over A into a randomized one over k of the same order of complexity.

We consider f_{1}, …, f_{n−i} as polynomials in the main variables x_{i+1}, …, x_{n}, and g_{i+1}, …, g_{n} as polynomials in y_{i+1}, …, y_{n} with coefficients in A = k[x_{1}, …, x_{i}].

Our algorithm presents the element α of A and the coefficients of g_{i+1}, …, g_{n} (which are also elements of A) by a division-free straight-line program in A = k[x_{1}, …, x_{i}] of size d^{cn} and depth cn^{2} log^{2} d. From these data it is now easy to find by means of (Heintz & Schnorr 1982, Theorem 4.4) a set of monomials h_{1}, …, h_{D} in y_{i+1}, …, y_{n} such that \overline{h}_{1}, …, \overline{h}_{D} form a basis of the D -dimensional K -vector space B′ = K[x_{i+1}, …, x_{n}]/ℑ′, as well as the matrices M_{i+1}, …, M_{n} of the K -linear endomorphisms α\overline{x}_{i+1}, …, α\overline{x}_{n} of B′ with respect to this basis. One verifies immediately that M_{i+1}, …, M_{n} are elements of A^{D×D} whose entries are represented by our algorithm by a division-free straight- line program in A = k[x_{1}, …, x_{i}] of size d^{cn} and depth cn^{2} log^{2} d.

For the remaining part of this section we think the polynomials h_{1}, …, h_{D} as being fixed. By Lemma 3.4.2 they can be found in sequential time s^{O(1)}d^{O(n)} by a well-parallelizable and division-free randomized algorithm, their degrees are of order d^{O(n)} , and \overline{h}_{1}, …, \overline{h}_{D} form a basis of the K -vector space B′.

Let g be a polynomial of k[x_{1}, …, x_{n}]. We denote by M_{g} the D × D matrix of the K -linear endomorphism \overline{g} of B′ with respect to the basis \overline{h}_{1}, …, \overline{h}_{D}. The matrix M_{g} belongs to K^{D×D} and may contain rational functions (elements of K \ A) among its entries. However, the characteristic polynomial χ_{Mg} is an element of A[T] = k[x_{1}, …, x_{i}, T], because χ_{Mg} = χ_{g} does not depend on the particular basis \overline{h}_{1}, …, \overline{h}_{D} of B′ and because \overline{g} is an A-linear endomorphism of the free A-module B. The coefficients of χ_{Mg} , which are polynomials of k[x_{1}, …, x_{i}], have degrees not exceeding the bound id^{2(n−i)} deg g. By Lemma 3.4.2 the matrices M_{x_{i+1}}, …, M_{x_{n}} can be found in sequential time d^{O(n)} by a well-parallelizable randomized algorithm. They are represented by a well-parallelizable straight-line program in K = k(x_{1}, …, x_{i}) of size d^{O(n)} . The map k[x_{1}, …, x_{n}] → K^{D×D}, which associates with each polynomial g of k[x_{1}, …, x_{n}] its matrix M_{g}, is a k - algebra homomorphism (this observation will be crucial in the next lemma).

Definition 3.4.3. Let β be a straight-line program in K[x_{i+1}, …, x_{n}] = k(x_{1}, …, x_{i})[x_{i+1}, …, x_{n}]. By the nonscalar complexity of β we refer to the number of essential multiplications (and divisions) of β, when K -linear operations (all additions/subtractions and all multiplications/divisions by elements of K) are free. In this sense β has a nonscalar size and a nonscalar depth.

Let L, ℓ, Λ, λ be natural numbers and let g be a polynomial of K[x_{i+1}, …, x_{n}]. We say that g has (simultaneously) sequential time complexity L, nonscalar sequential time complexity Λ, parallel time complexity ℓ and nonscalar parallel time complexity λ, if there exists a straight-line program β in K[x_{1}, …, x_{i}] containing only divisions by elements of K and having size L, nonscalar size Λ, depth ℓ and nonscalar depth λ, which computes g (see von zur Gathen 1986 and Strassen 1972 for details).

Lemma 3.4.4. Let g be a polynomial of k[x_{1}, …, x_{n}] which can be computed (evaluated) by a straight-line program β in k(x_{1}, …, x_{i})[x_{i+1}, …, x_{n}] of size L, nonscalar size Λ, depth ℓ and nonscalar depth λ (we suppose that β contains only divisions by elements of k(x_{1}, …, x_{i})).

Then the D × D matrix M_{g} can be represented by a straight-line program β′ in K = k(x_{1}, …, x_{i}) of size L + cΛ^{2}D^{3} + d^{cn} and depth ℓ + c(λ log D + n^{2} log^{2} d), where c > 0 is a constant not depending on K.

Furthermore, β′ can be produced from β in sequential time L+cΛ^{2}D^{3}+ d^{cn} and parallel time ℓ + c(λ log D + n^{2} log^{2} d) by means of a randomized arithmetic network over k. The circuit β′ can be extended to a straightline program in k(x_{1}, …, x_{i})[x_{i+1}, …, x_{n}] of the same size and depth which contains β and computes therefore g. The extended computation contains only divisions by elements of k(x_{1}, …, x_{i}) and has nonscalar size Λ and nonscalar depth λ.

Proof. Let β = (q_{1}, …, q_{L′}) where L′ ≥ L and q_{1}, …, q_{L′} are elements of k(x_{1}, …, x_{i})[x_{i+1}, …, x_{n}]. Without loss of generality we may assume g = q_{L′}. We consider the following sequence of D × D matrices over K:

β^{∗} = (Mq_{1}, …, Mq_{L′}) .

We interpret β^{∗} as a computation of M_{g} from the input M_{x_{i+1}}, …, M_{x_{n}} in the matrix algebra K^{D×D}. In this sense β^{∗} has size L, nonscalar size Λ, depth ℓ and nonscalar depth λ.

To the concatenation of β with the sequence of D×D matrices β^{∗} there corresponds a straight-line program β_{1} in k(x_{1}, …, x_{i}) which computes the entries of M_{g} from x_{1}, …, x_{i} and the entries of M_{x_{i+1}}, …, M_{x_{n}} as inputs.

Applying the most obvious algorithms for adding and multiplying D × D matrices we see that the size of β_{1} is bounded by L + cΛ^{2}D^{3} and the depth of β_{1} by ℓ + cλ log D, where c > 0 is a suitable constant not depending on K. (It follows from a standard argument in algebraic complexity theory that a computation of nonscalar complexity Λ can be normalized in such way that the new computation has size approximately Λ^{2} . Here we consider all operations, also the linear ones. However, in this complexity model constant operations requiring access to elements of the ground field are free. In our case the ground field is K = k(x_{1}, …, x_{i}) and the constants from K involved in our computation may be precalculated by a straight-line program of size L. Obviously the whole procedure can be parallelized. For details see (Stoss 1989.)

Now we concatenate β_{1} with the straight-line program β_{2} in k(x_{1}, …, x_{i}) which computes the D × D matrices M_{x_{i+1}}, …, M_{x_{n}} and which we obtain as a consequence of Lemma 3.4.2. The straight-line program β_{2} can be produced in sequential time d^{cn} and parallel time cn^{2} log^{2} d from the input f_{1}, …, f_{n−i} by a randomized algorithm. Moreover β_{2} has size d^{cn} and depth cn^{2} log^{2} d. (Here c > 0 is a sufficiently large constant.)

Let β′ be the straight-line program in k(x_{1}, …, x_{i}) which we obtain concatenating β_{1} and β_{2} . Thus β′ computes the entries of the D × D matrix M_{g} from the inputs x_{1}, …, x_{i} in sequential time L + cΛ^{2}D^{3} + d^{cn} and parallel time ℓ + c(λ log D + n^{2} log^{2} d). Within the same time bounds β′ can be produced from β by a randomized arithmetic network over k. From our construction it is evident that β′ can also be interpreted by a straight-line program in k(x_{1}, …, x_{i})[x_{i+1}, …, x_{n}] which contains the circuit β and has nonscalar size Λ and nonscalar depth λ.

The following proposition and its corollary provide a key tool for the proof of our main result.

Proposition 3.4.5. Let a, f, r be polynomials of k[x_{1}, …, x_{n}] such that \overline{r} = \overline{a}\overline{f} holds in B. Assume that \overline{f} is not a zero divisor of the A-algebra B. Suppose that a straight-line program β in k(x_{1}, …, x_{i})[x_{i+1}, …, x_{n}] of size L, nonscalar size Λ, depth ℓ and nonscalar depth λ which computes f and r is given. Suppose furthermore that β contains only divisions by elements of k(x_{1}, …, x_{i}). Let T be a new indeterminate and let χ_{a} = T^{D} +α_{D−1}T^{D−1}+ ⋯ + α_{0} be the characteristic polynomial of the K -linear endomorphism \overline{a} of B′. Then α_{D−1}, …, α_{0} are polynomials of A = k[x_{1}, …, x_{i}] of degree at most id^{2(n−i)} deg a which can be computed by a straight-line program β′ in k(x_{1}, …, x_{i}) of size L + cΛ^{2}D^{3} + d^{cn} and depth ℓ + c(λ log D + n^{2} log^{2} d), where c > 0 is a suitable constant not depending on K = k(x_{1}, …, x_{i}).

Furthermore β′ can be produced from β in sequential time L + cΛ^{2}D^{3} + d^{cn} and parallel time ℓ + c(λ log D + n^{2} log^{2} d) by means of a randomized arithmetic network over k. The circuit β′ can be extended to a straightline program in k(x_{1}, …, x_{i})[x_{i+1}, …, x_{n}] of the same size and depth which contains β and computes therefore f and r. The new computation contains only divisions by elements of k(x_{1}, …, x_{i}) and has nonscalar size Λ and nonscalar depth λ.

Proof. Let us first observe that by Lemma 3.3.3 the rational functions α_{D−1}, …, α_{0} of K = k(x_{1}, …, x_{i}) are in fact polynomials of k[x_{1}, …, x_{i}] of degree at most id^{2(n−i)} deg a.

Applying Lemma 3.4.4 to the computation β we obtain a computation β_{1} in k(x_{1}, …, x_{i}) of size L+cΛ^{2}D^{3}+d^{cn} and depth ℓ+c(λ log D+n^{2} log^{2} d) which evaluates the entries of the matrices M_{r} and M_{f}. (Here and in the sequel c > 0 is a suitable constant not depending on the field K = k(x_{1}, …, x_{i}).) Since \overline{f} is not a zero divisor of the A-algebra B, the corresponding K -endomorphism of B′ is invertible. This means that the matrix M_{f} ∈ K^{D×D} is regular. Moreover, according to lemma 3.4.4 the circuit β_{1} can be extended to a straight-line program in k(x_{1}, …, x_{i})[x_{i+1}, …, x_{n}] of the same size and depth which contains β. The extended straight-line program has nonscalar size Λ and nonscalar depth λ.

We compute first the entries of M_{f}^{−1} and then those of M_{a} = M_{r} · M_{f}^{−1} from the entries of M_{r} and M_{f} by a straight-line program β_{2} in k(x_{1}, …, x_{i}) of size cD^{5} and depth c log^{2} D (this is a consequence of the algorithm of Berkowitz ; see also von zur Gathen 1986, Theorem 5.2).

Finally we compute the polynomials α_{D−1}, …, α_{0} ∈ k[x_{1}, …, x_{i}], which are the coefficients of the characteristic polynomial χ_{a} = χ_{Ma} , from the entries of M_{a} by means of the algorithm (Berkowitz 1984). This is done by a (division-free) straight-line program β_{3} in k(x_{1}, …, x_{i}) of size cD^{5} and depth c log^{2} D.

Concatenating the straight-line programs β_{1}, β_{2} and β_{3} and taking into account that D ≤ d^{n} holds, we obtain a straight-line program β′ in k(x_{1}, …, x_{i}) of size L + cΛ^{2}D^{3} + d^{cn} and depth ℓ + c(λ log D + n^{2} log^{2} d) which computes the polynomials α_{D−1}, …, α_{0} .

By our argument it is evident that β′ can be produced from β in sequential time L+cΛ^{2}D^{3}+d^{cn} and parallel time ℓ+c(λ log D+n^{2} log^{2} d) by means of a randomized arithmetic network over k. By its construction β′ can be extended to a straight-line program in k(x_{1}, …, x_{i})[x_{i+1}, …, x_{n}] of the same size and depth which contains the circuit β. The extended straight-line program contains only divisions by elements of k(x_{1}, …, x_{i}) and has nonscalar size Λ and nonscalar depth λ.

Combining Proposition 3.4.5 with a local version of the effective Nullstellensatz due to L. Caniglia (see Caniglia 1989, or Caniglia et al. 1991) we obtain the following.

Corollary 3.4.6. Let f and r be polynomials of k[x_{1}, …, x_{n}] such that \overline{r} is divisible by \overline{f} in B. Assume that deg f ≤ d and that \overline{f} is not a zero divisor of B. Suppose that there is given a straight-line program β in k(x_{1}, …, x_{i})[x_{i+1}, …, x_{n}] of size L, nonscalar size Λ, depth ℓ and nonscalar depth λ, which computes the polynomial r. Suppose furthermore that β contains only divisions by elements of k(x_{1}, …, x_{i}). Then there exists a polynomial a of k[x_{1}, …, x_{n}] such that its degree satisfies

deg a ≤ i(d^{2(n−i)} deg r + d^{3(n−i)+1}) + D(d + deg r)

and such that

\overline{r}^{D} = \overline{a} \overline{f} holds in B .

Moreover the polynomial a can be computed by a straight-line program β′ in k(x_{1}, …, x_{i})[x_{i+1}, …, x_{n}] of size L + cΛ^{2}D^{3} + d^{cn}, nonscalar size Λ + 2D + d^{c(n−i)} , depth ℓ + c(λ log D + n^{2} log^{2} d) and nonscalar depth λ + 2 log D + c(n − i) log d, where c > 0 is a suitable constant not depending on k(x_{1}, …, x_{i})[x_{i+1}, …, x_{n}].

The straight-line program β′ contains only divisions by elements of k(x_{1}, …, x_{i}), and β′ can be produced from β in sequential time L+cΛ^{2}D^{3}+ d^{cn} and parallel time ℓ + c(λ log D + n^{2} log^{2} d) by means of a randomized arithmetic network over k. The computation β is a subroutine of the circuit β′.

Proof. Before starting the main argument of the proof let us make the following observation:

Since f is a polynomial of k[x_{1}, …, x_{n}] of degree at most d, it has in dense representation not more than ed^{n} coefficients. Therefore f can be evaluated by a division-free straight-line program β_{1} in k[x_{1}, …, x_{n}] (and hence in k(x_{1}, …, x_{i})[x_{i+1}, …, x_{n}]) of size d^{cn}, nonscalar size d^{c(n−i)} , depth cn log d and nonscalar depth c(n−i) log d, where c > 0 is a suitable constant not depending on k[x_{1}, …, x_{n}].

Suppose first that \overline{f} is a unit of B. Let T be a new indeterminate and let χ_{f} = T^{D} + φ_{D−1}T^{D−1} + ⋯ + φ_{0} be the characteristic polynomial of the K -linear endomorphism \overline{f} of B′. From Lemma 3.3.3 we deduce that φ_{D−1}, …, φ_{0} are polynomials of A = k[x_{1}, …, x_{i}] of degree at most id^{2(n−i)+1} . In particular the polynomial φ_{0} is the determinant of the Alinear invertible endomorphism \overline{f} of the free A-module B (see Corollary 3.3.2). Therefore φ_{0} is a unit of k[x_{1}, …, x_{i}]. This means that φ_{0} is a non-zero element of k. Let

q = ( − \frac{1}{φ_{0}} )(f^{D−1} + φ_{D−1}f^{D−2} + ⋯ + φ_{1}) .

We see that q is a polynomial of k[x_{1}, …, x_{n}] of degree at most id^{2(n−i)+1} + Dd. From Proposition 3.4.5 and the fact that D ≤ d^{n} holds, one deduces immediately that φ_{D−1}, …, φ_{0} can be evaluated by a straight-line program in k(x_{1}, …, x_{i}) of size d^{cn} and depth cn^{2} log^{2} d, where c > 0 is a suitable constant not depending on k(x_{1} …, x_{i}).

This implies that q can be computed by a straight-line program β^{∗} in k(x_{1}, …, x_{i})[x_{i+1}, …, x_{n}] of asymptotically the same size and depth (adapting the constant c > 0). The straight-line program β^{∗} contains only divisions by elements of k(x_{1}, …, x_{i}). The Theorem of Hamilton-Cayley implies that

(1)  \overline{f}^{D} + φ_{D−1}\overline{f}^{D−1} + ⋯ + φ_{0} = 0

holds in B. From (1) we deduce that the equality

(2)  \overline{f} \overline{q} = 1

holds in B.

Let a be the polynomial of k[x_{1}, …, x_{n}] given by a = r^{D}q. From (2) one concludes immediately that the equality

\overline{r}^{D} = \overline{a} \overline{f}

holds in B and that the degree of a satisfies

deg a ≤ id^{2(n−i)+1} + D(d + deg r)
≤ i(d^{2(n−i)} deg r + d^{3(n−i)+1}) + D(d + deg r) .

The polynomial a of k[x_{1}, …, x_{n}] can be evaluated by a straight-line program β′ in k(x_{1}, …, x_{i})[x_{i+1}, …, x_{n}] of size L + d^{cn} ≤ L + cΛ^{2}D^{3} + d^{cn}, nonscalar size Λ+2D+d^{c(n−i)} , depth ℓ+cn^{2} log^{2} d ≤ ℓ+c(λ log D+n^{2} log^{2} d) and nonscalar depth λ + 2 log D + c(n − i) log d, where c > 0 is a suitable constant not depending on k(x_{1}, …, x_{i})[x_{i+1}, …, x_{n}].

The straight-line program β′ executes only divisions in k(x_{1}, …, x_{i}) and β′ can be produced from β by a randomized arithmetic network over k in sequential time L + d^{cn} ≤ L + cΛ^{2}D^{3} + d^{cn} and parallel time ℓ + cn^{2} log^{2} d ≤ ℓ + c(λ log D + n^{2} log^{2} d). The circuit β′ contains β as a subroutine.

Suppose now that \overline{f} is not a unit of B. Thus the algebraic variety W = V ∩ \{f = 0\} is not empty. Since \overline{f} is not a divisor of zero in B the variety W is of dimension i − 1 ≥ 0. On the other hand W is the subvariety of A^{n} defined by the n−i+1 polynomials f_{1}, …, f_{n−i}, f. Taking into account that dim W = i − 1 holds, we deduce from Macaulay’s Theorem (see Matsumura 1989, Theorem 17.7) that f_{1}, …, f_{n−i}, f form a regular sequence in k[x_{1}, …, x_{n}]. Since B = k[x_{1}, …, x_{n}]/(f_{1}, …, f_{n−i}) and since \overline{f} divides \overline{r} in B we conclude that the polynomial r belongs to the ideal (f_{1}, …, f_{n−i}, f) of k[x_{1}, …, x_{n}].

Thus there exist polynomials q_{1}, …, q_{n−i} and q of k[x_{1}, …, x_{n}] which satisfy the equality

(3)  r = q_{1}f_{1} + ⋯ + q_{n−i}f_{n−i} + qf

and the degree bound

max{deg q_{1}f_{1}, …, deg q_{n−i}f_{n−i}, deg qf} ≤ deg r + (max{3, d})^{n−i+1}

(This is a consequence of the local version of the effective Nullstellensatz mentioned above. See Caniglia et al. 1991, Theorem 1.3 and Corollary 3.3, or Dickenstein et al. 1991, Theorem 5.1.)

Taking into account the basic assumption d ≥ n (see Section 1.2) and treating the case n = 2 separately one sees immediately that we may assume without loss of generality deg qf ≤ deg r + d^{n−i+1} .

On the other hand we deduce from the equality (3) that

(4)  \overline{r} = \overline{q} \overline{f}

holds in B. Let T be a new variable and let

χ_{q} = T^{D} + μ_{D−1}T^{D−1} + ⋯ + μ_{0}

be the characteristic polynomial of the K -linear endomorphism \overline{q} of B′.

From Proposition 3.4.5 we deduce that μ_{D−1}, …, μ_{0} are polynomials of k[x_{1}, …, x_{i}] of degree at most i(d^{2(n−i)} deg r + d^{3(n−i)+1}) which can be evaluated by a straight-line program β_{2} in k(x_{1}, …, x_{i}) of size L + cΛ^{2}D^{3} + d^{cn} and depth ℓ+c(λ log D+n^{2} log^{2} d), where c > 0 is a suitable constant not depending on k(x_{1}, …, x_{i}). Following the same proposition we may extend β_{2} to a straight-line program in k(x_{1}, …, x_{i})[x_{i+1}, …, x_{n}] of equal size and depth which contains the circuit β′ and therefore computes r. The extended straight-line program executes only divisions by elements of k(x_{1}, …, x_{i}) and has nonscalar size Λ and nonscalar depth λ.

From the Theorem of Hamilton-Cayley we conclude that the equality

(5)  \overline{q}^{D} + μ_{D−1}\overline{q}^{D−1} + ⋯ + μ_{0} = 0

holds in B. Combining (4) and (5) we obtain the equality

(6)  \overline{r}^{D} + μ_{D−1}\overline{f} \overline{r}^{D−1} + ⋯ + μ_{0}\overline{f}^{D} = 0

We consider the polynomial a = −(μ_{D−1}r^{D−1} + μ_{D−2}fr^{D−2} + ⋯ + μ_{0}f^{D−1}) of k[x_{1}, …, x_{n}]. From (6) we deduce that the equality

\overline{r}^{D} = \overline{a} \overline{f}

holds in B.

Moreover the degree of the polynomial a is bounded by i(d^{2(n−i)} deg r + d^{3(n−i)+1}) + D(d + deg r) and a can be computed from the input f, r and μ_{D−1}, …, μ_{0} by a division-free straight-line program β_{3} in k[x_{1}, …, x_{n}] of size 3D, nonscalar size 2D, depth 2+3 log D and nonscalar depth 1+2 log D.

Concatenating the straight-line programs β_{1}, β_{2} and β_{3} we obtain a straight-line program β′ in k(x_{1}, …, x_{i})[x_{i+1}, …, x_{n}] of size L + cΛ^{2}D^{3} + d^{cn}, nonscalar size Λ + 2D + d^{c(n−i)} , depth ℓ + c(λ log D + n^{2} log^{2} d) and nonscalar depth λ + 2 log D + c(n − i) log d, which computes the polynomial a of k[x_{1}, …, x_{n}]. (Here c > 0 is again a suitable constant not depending on k(x_{1}, …, x_{i})[x_{i+1}, …, x_{n}].) Moreover β′ contains only divisions by elements of k(x_{1}, …, x_{i}) and β′ can be produced from β by a randomized arithmetic network over k of size 2L+cΛ^{2}D^{3}+d^{cn} and depth 2ℓ+c(λ log D+n^{2} log^{2} d). The circuit β is a subroutine of β′ by construction.

3.5. Proof of the main result. In this section we shall maintain the following notation and conventions introduced in 3.2:

Let f_{1}, …, f_{n+1} be a family of polynomials of k[x_{1}, …, x_{n}] representing a normalized input for the algorithm we are going to design. Suppose that the degrees of f_{1}, …, f_{n+1} are bounded by a natural number d satisfying d ≥ n and that f_{1}, …, f_{n+1} generate the trivial ideal of k[x_{1}, …, x_{n}].

For any 0 ≤ i ≤ n − 1 we consider the following definitions:

A_{i} = k[x_{1}, …, x_{i}], K_{i} = k(x_{1}, …, x_{i}), ℑ_{i} and ℑ′_{i} are the ideals generated by f_{1}, …, f_{n−i} in k[x_{1}, …, x_{n}] and in K_{i}[x_{i+1}, …, x_{n}] respectively, B_{i} = k[x_{1}, …, x_{n}]/ℑ_{i}, B′_{i} = K_{i}[x_{i+1}, …, x_{n}]/ℑ′_{i}, D_{i} = dim_{K_{i}} B′_{i} and V_{i} = V (f_{1}, …, f_{n−i}) = V (ℑ_{i}), the closed subvariety of A^{n} defined by the polynomials f_{1}, …, f_{n−i}.

Furthermore let us assume that for 0 ≤ i ≤ n−1 the following conditions are satisfied:

• ℑ_{i} and ℑ′_{i} are radical ideals,

• V_{i} is a smooth algebraic variety of dimension i, and

• the variables x_{1}, …, x_{n} are in Noether position with respect to V_{i}.

For any 0 ≤ i ≤ n − 1 and for any polynomial g of k[x_{1}, …, x_{n}] we consider the canonical k -algebra homomorphisms : k[x_{1}, …, x_{n}] → B_{i} and : K[x_{i+1}, …, x_{n}] → B′_{i} and we denote by \overline{g} the image of g in B_{i} and in B′_{i} as well as the A_{i} -linear endomorphism of B_{i} and the K_{i} -linear endomorphism of B′_{i} induced by the multiplication by g.

With the above notation and assumptions we have shown in 3.2 that our main result, namely the theorem of Section 2, is a direct consequence of the following proposition.

Proposition 3.5.1. There exists a straight-line program β in k(x_{1}, …, x_{n}) of size d^{O(n)} and depth O(n^{4} log^{2} d) which computes polynomials p_{1}, …, p_{n+1} of k[x_{1}, …, x_{n}] of degree d^{O(n^{2})} such that

1 = p_{1}f_{1} + ⋯ + p_{n+1}f_{n+1} .

The straight-line program β can be produced in non-uniform sequential time d^{O(n)} and parallel time O(n^{4} log^{2} d) by a randomized arithmetic network over k.

Proof. Our proof relies on an iterative application of Corollary 3.4.6 and follows the lines of (Caniglia, Galligo & Heintz 1988, 1989).

For every 1 ≤ i ≤ n we construct recursively a straight-line program β^{(i)} in k(x_{1}, …, x_{i−1})[x_{i}, …, x_{n}] which contains only divisions by elements of k(x_{1}, …, x_{i−1}) and which computes polynomials a_{n+1}^{(i)}, …, a_{n−i+2}^{(i)} of k[x_{1}, …, x_{n}] such that

r_{i} = a_{n+1}^{(i)}f_{n+1} + ⋯ + a_{n−i+2}^{(i)}f_{n−i+2} − 1

belongs to the ideal ℑ_{i−1} = (f_{1}, …, f_{n−i+1}). The straight-line program β^{(i)} will be realized by a randomized arithmetic network over k of size, say, L_{i} and depth, say, ℓ_{i}. Without loss of generality we may assume that L_{i} and ℓ_{i} bound also the size and the depth of the straight-line program β^{(i)} . Furthermore let Λ_{i} be the nonscalar size and λ_{i} be the nonscalar depth of β^{(i)} and let d_{i} = max{deg a_{n+1}^{(i)}, …, deg a_{n−i+2}^{(i)}}. For 1 ≤ i < n the quantities L_{i}, Λ_{i}, ℓ_{i}, λ_{i} and d_{i} will satisfy the following recursion formulas:

(1)  L_{1} ≤ d^{cn} ,  L_{i+1} ≤ L_{i} + cΛ_{i}^{2}D_{i}^{3} + d^{cn}
(2)  Λ_{1} ≤ 2D_{1} + 1 ,  Λ_{i+1} ≤ Λ_{i} + (3i + 2)D_{i} + d^{c(n−i)}
(3)  ℓ_{1} ≤ cn^{2} log^{2} d , ℓ_{i+1} ≤ ℓ_{i} + c(λ_{i} log D_{i} + n^{2} log^{2} d)
(4) λ_{1} ≤ 2 log D_{1} , λ_{i+1} ≤ λ_{i} + 6 log D_{i} + cn log d
(5)  d_{1} ≤ (D_{1} + 1)d , d_{i+1} ≤ i(d^{2(n−i)}d_{i} + d^{3(n−i)+1}) + D_{i}(d + d_{i})

(here c > 0 is a suitable constant not depending on k(x_{1}, …, x_{i})[x_{i+1}, …, x_{n}] and 1 ≤ i < n). Taking into account that d ≥ n and that D_{i} ≤ d^{n−i} ≤ d^{n} holds for any 0 ≤ i ≤ n we can make the conclusions which follow now.

From (2) and (4) it follows that for 1 ≤ i ≤ n,

(6)

Λ_{i} ≤ (2d^{n−1} + 1) + ∑_{1≤i≤n}(3i + 7)d^{n−i} + ∑_{1≤i≤n} d^{c(n−i)} ≤ d^{c′n}
λ_{i} ≤ cn^{2} log d + 8 ∑_{1≤i≤n} log D_{i} ≤ c′n^{2} log d ,

where c′ > 0 is a suitable constant.

From (1), (3) and (6) we obtain for 1 ≤ i < n:

(7) L_{i+1} ≤ L_{i} + cd^{2c′n}D_{i}^{3} + d^{cn} ≤ L_{i} + d^{c′′n}

ℓ_{i+1} ≤ ℓ_{i} + c(c′n^{2} log d log D_{i} + n^{2} log^{2} d) ≤ ℓ_{i} + c′′n^{3} log^{2} d ,

where c′′ > 0 is a suitable constant.

From (1), (3) and (7) we conclude for 1 ≤ i ≤ n:

(8) L_{i} ≤ d^{cn} + nd^{c′′n} ≤ d^{c′′′n}

ℓ_{i} ≤ cn^{2} log^{2} d + c′′n^{4} log^{2} d ≤ c′′′n^{4} log^{2} d ,

where c′′′ > 0 is a suitable constant.

Thus (8) implies

(9)  \begin{aligned}L_{n} & = d^{O(n)} \\ ℓ_{n} & = O(n^{4} log^{2} d) . \end{aligned}

In a similar way one concludes

(10)  d_{n} = d^{O(n^{2})} .

Let us first consider the case i = 1.

We have ℑ_{i−1} = ℑ_{0} = (f_{1}, …, f_{n}). Thus ℑ_{i−1} is an ideal of k[x_{1}, …, x_{n}] of height n which defines a zero-dimensional subvariety of A^{n}, namely V_{i−1} = V_{0} = V (f_{1}, …, f_{n}). Moreover f_{n+1} does not vanish on any point of V_{i−1} . This means that \overline{f}_{n+1} is a unit of B_{i} = B_{1} = k[x_{1}, …, x_{n}]/(f_{1}, …, f_{n}). In particular \overline{f}_{n+1} is not a zero divisor of B_{1} and divides the unit element 1 of B_{1} . Therefore by Corollary 3.4.6 there exists a polynomial of k[x_{1}, …, x_{n}], say a_{n+1}^{(1)} , of degree d_{1} ≤ (D_{1} + 1)d such that 1 = \overline{a}_{n+1}^{(1)}\overline{f}_{n+1} holds in B_{1} . This means that r_{1} = a_{n+1}^{(1)}f_{n+1} − 1 belongs to ℑ_{0} = (f_{1}, …, f_{n}). Moreover the polynomial a_{n+1}^{(1)} can be evaluated by a straight-line program β^{(1)} in k[x_{1}, …, x_{n}] of size L_{1} ≤ d^{cn}, nonscalar size Λ_{1} ≤ 2D_{1} + 1, depth ℓ_{1} ≤ cn^{2} log^{2} d and nonscalar depth λ_{1} ≤ 2 log D_{1} , where c > 0 is a suitable constant not depending on k[x_{1}, …, x_{n}]. The straight-line program β^{(1)} contains only divisions by elements of k, and β^{(1)} can be produced in non-uniform sequential time L_{1} and parallel time ℓ_{1} by a randomized arithmetic network over k.

Now suppose that 1 ≤ i < n and that there is given a straight-line program β^{(i)} in k(x_{1}, …, x_{i−1})[x_{i}, …, x_{n}] which contains only divisions by elements of k(x_{1}, …, x_{i−1}) and which computes polynomials a_{n+1}^{(i)}, …, a_{n−i+2}^{(i)} of k[x_{1}, …, x_{n}] such that

r_{i} = a_{n+1}^{(i)}f_{n+1} + ⋯ + a_{n−i+2}^{(i)}f_{n−i+2} − 1

belongs to the ideal ℑ_{i−1} = (f_{1}, …, f_{n−i+1}).

Let L_{i} be the size, Λ_{i} the nonscalar size, ℓ_{i} the depth and λ_{i} the nonscalar depth of β^{(i)} and let d_{i} = max{deg a_{n+1}^{(i)}, …, deg a_{n−i+2}^{(i)}}. Suppose that β^{(i)} can be produced by a randomized arithmetic network over k of size L_{i} and depth ℓ_{i}. First we observe that r_{i} can be computed by a straight-line program β′ in k(x_{1}, …, x_{i−1})[x_{i}, …, x_{n}] of size L_{i} + 2i + d^{cn}, nonscalar size Λ_{i} + i + d^{c(n−i)} , depth ℓ_{i} + log i + cn log d and nonscalar depth λ_{i} + c(n − i) log d. The straight-line program β′ contains only divisions by elements of k(x_{1}, …, x_{i−1}) and contains β^{(i)} as a subroutine.

The polynomial r_{i} belongs to the ideal ℑ_{i−1} = (f_{1}, …, f_{n−i}, f_{n−i+1}). Therefore \overline{f}_{n−i+1} divides \overline{r}_{i} in the A_{i} -algebra B_{i} = k[x_{1}, …, x_{n}] /(f_{1}, …, f_{n−i}). On the other hand the variety V_{i−1} = V (ℑ_{i−1}) = V (f_{1}, …, f_{n−i+1}) is a nonempty (i − 1)-dimensional closed subset of the affine space A^{n}. Hence by Macaulay’s Theorem (Matsumura 1989, Theorem 17.7), the family f_{1}, …, f_{n−i}, f_{n−i+1} forms a regular sequence of the polynomial algebra k[x_{1}, …, x_{n}]. This implies that \overline{f}_{n−i+1} is not a zero divisor of B_{i}. Thus again by Corollary 3.4.6 we conclude that there exists a polynomial a of k[x_{1}, …, x_{n}] such that

deg a ≤ i(d^{2(n−i)}d_{i} + d^{3(n−i)+1}) + D_{i}(d + d_{i})

which satisfies

(11)  \overline{r}_{i}^{D_{i}} = \overline{a} \overline{f}_{n−i+1}

in B_{i}. Moreover the polynomial a can be evaluated by a straight-line program β′′ in k(x_{1}, …, x_{i})[x_{i+1}, …, x_{n}] of size L_{i} + cΛ_{i}^{2}D_{i}^{3} + d^{cn}, nonscalar size Λ_{i} + 2D_{i} + d^{c(n−i)} , depth ℓ_{i} + c(λ_{i} log D_{i} + n^{2} log^{2} d), and nonscalar depth λ_{i} + 2 log D_{i} + c(n − i) log d.

The straight-line program β′′ executes only divisions by elements of k(x_{1}, …, x_{i}) and can be produced from β^{(i)} by a randomized arithmetic network over k of size L_{i} + cΛ_{i}^{2}D_{i}^{3} + d^{cn} and depth ℓ_{i} + c(λ_{i} log D_{i} + n^{2} log^{2} d). (Here c > 0 is again a suitable constant not depending on k(x_{1}, …, x_{i})[x_{i+1}, …, x_{n}] and 1 ≤ i < n.) The circuit β′′ contains the computation β′ and hence β^{(i)} as a subroutine. Therefore β′′ computes also the polynomials a_{n+1}^{(i)}, …, a_{n−i+2}^{(i)} .

From (11) we conclude that the polynomial

r = r_{i}^{D_{i}} − af_{n−i+1}

belongs to the ideal ℑ_{i} = (f_{1}, …, f_{n−i}).

Since r_{i} = a_{n+1}^{(i)}f_{n+1} + ⋯ + a_{n−i+2}^{(i)}f_{n−i+2} − 1, where a_{n+1}^{(i)}, …, a_{n−i+2}^{(i)} are polynomials of k[x_{1}, …, x_{n}] of degree at most d_{i} which can be evaluated by the straight-line program β^{(i)} , we conclude that r = r_{i}^{D_{i}} − af_{n−i+1} has the form

r = a_{n+1}f_{n+1} + ⋯ + a_{n−i+2}f_{n−i+2} − af_{n−i+1} + (−1)^{D_{i}} ,

where a_{n+1}, …, a_{n−i+2} are polynomials of k[x_{1}, …, x_{n}] of degree at most D_{i}d_{i}. Moreover it is possible to compute them from f_{n+1}, …, f_{n−i+2} and a_{n+1}^{(i)}, …, a_{n+i−2}^{(i)} by a division-free straight-line program β′′′ in k[x_{1}, …, x_{n}] of size 4iD_{i}, nonscalar size 3iD_{i}, depth 5 log D_{i} + 2, and nonscalar depth 4 log D_{i} + 1. If D_{i} is odd let

a_{n+1}^{(i+1)} = a_{n+1}, …, a_{n−i+2}^{(i+1)} = a_{n−i+2}, a_{n−i+1}^{(i+1)} = −a ;

if D_{i} is even let

a_{n+1}^{(i+1)} = −a_{n+1}, …, a_{n−i+2}^{(i+1)} = a_{n−i+2}, a_{n−i+1}^{(i+1)} = a .

In either case

r_{i+1} = a_{n+1}^{(i+1)}f_{n+1} + ⋯ + a_{n−i+1}^{(i+1)}f_{n−i+1} − 1

belongs to ℑ_{i} = (f_{1}, …, f_{n−i}) and the degrees of a_{n+1}^{(i+1)}, …, a_{n−i+1}^{(i+1)} are bounded by the quantity

i(d^{2(n−i)}d_{i} + d^{3(n−i)+1}) + D_{i}(d + d_{i}) .

Therefore we have d_{i+1} ≤ i(d^{2(n−i)}d_{i} + d^{3(n−i)+1}) + D_{i}(d + d_{i}). Concatenating β′′ and β′′′ we obtain a straight-line program β^{(i+1)} in k(x_{1}, …, x_{i})[x_{i+1}, …, x_{n}] which contains only divisions by elements in k(x_{1}, …, x_{i}) and which computes the polynomials a_{n+1}^{(i+1)}, …, a_{n−i+1}^{(i+1)} of k[x_{1}, …, x_{n}]. The straight-line program β^{(i+1)} has size L_{i+1} ≤ L_{i} + cΛ_{i}^{2}D_{i}^{3} + d^{cn}, nonscalar size Λ_{i+1} ≤ Λ_{i} + (3i + 2)D_{i} + d^{c(n−i)} , depth ℓ_{i+1} ≤ ℓ_{i} + c(λ_{i} log D_{i} + n^{2} log^{2} d), and nonscalar depth λ_{i+1} ≤ λ_{i} + 6 log D_{i} + cn log d, where c > 0 is a suitable constant not depending on k(x_{1}, …, x_{i})[x_{i+1}, …, x_{n}] and 1 ≤ i < n. Moreover β^{(i+1)} can be realized by a randomized arithmetic network over k of size L_{i+1} and depth ℓ_{i+1} .

In particular β^{(n)} is a straight-line program in k(x_{1}, …, x_{n−1})[x_{n}] (and hence in k(x_{1}, …, x_{n})) of size L_{n} = d^{O(n)} and depth ℓ_{n} = O(n^{4} log^{2} d) which computes polynomials a_{n+1}^{(n)}, …, a_{2}^{(n)} of k[x_{1}, …, x_{n}] of degree d^{O(n^{2})} such that r_{n} = a_{n+1}^{(n)}f_{n+1} +⋯+a_{2}^{(n)}f_{2} −1 is divisible by f_{1} in k[x_{2}, …, x_{n}].

Let p_{1} = \frac{r_{n}}{f_{1}} , p_{2} = a_{2}^{(n)}, …, p_{n+1} = a_{n+1}^{(n)} . Then p_{1}, …, p_{n+1} are

polynomials of k[x_{1}, …, x_{n}] of degree d^{O(n^{2})} which can be computed by a straight-line program in k(x_{1}, …, x_{n}) of size d^{O(n)} and depth O(n^{4} log^{2} d). Moreover p_{1}, …, p_{n+1} satisfy the condition

1 = p_{1}f_{1} + ⋯ + p_{n+1}f_{n+1} .

Our main result, the theorem of Section 2, is now an immediate consequence of Proposition 3.5.1 and Lemma 3.2.1.

Acknowledgements

This work was jointly supported by the following projects:

GDR MEDICIS (Mathématiques Effectives, Développements Informatiques, Calcul, Ingénierie et Systèmes) and GDR-PRC Mathématiques et Informatique, France.

The authors wish to thank Joachim von zur Gathen (University of Toronto) and Guillermo Moreno (École Polytechnique, Palaiseau) for their help in bringing this paper to its present form.

References

J. L. Balcázar, J. Díaz, and J. Gabarró, Structural Complexity I, EATCS Monographs on Theoretical Computer Science 11, Springer, 1988.

S. J. Berkowitz, On computing the determinant in small parallel time using a small number of processors, Inform. Process. Lett. 18 (1984), 147–150.

W. S. Brown, On Euclid’s algorithm and the computation of polynomial greatest common divisors, J. ACM 18 (1971), 478–504.

D. Brownawell, Bounds for the degrees in the Nullstellensatz, Ann. of Math. (Second Series) 126 (1987), 577–591.

L. Caniglia, Complejidad de algoritmos en geometría computacional, Doctoral Thesis, Universidad de Buenos Aires, 1989.

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

L. Caniglia, A. Galligo, and J. Heintz, Some new effectivity bounds in computational geometry, in Applied Algebra, Algebraic Algorithms and Error-Correcting Codes, Proc. 6th Intern. Conf. AAECC-6, Rome 1988, T. Mora, ed., Springer LN Comput. Sci. 357 (1989), 131–151.

L. Caniglia, J.A. Guccione, and J.J. Guccione, Local membership problems for polynomial ideals, in Effective Methods in Algebraic Geometry, Proc. Intern. Conf. MEGA 90,Castiglioncello 1990, T. Mora and C. Traverso, eds., Progress in Mathematics 94, Birkhäuser (1991), 31–45.

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, Special issue 7th Intern. Conf. Applied Algebra, Algebraic Algorithms and Error-Correcting Codes AAECC– 7,Toulouse 1989. N. Fitchas and A. Galligo, Nullstellensatz effectif et Conjecture de Serre (Théorème de Quillen-Suslin) pour le Calcul Formel, Math. Nachr. 149 (1990), 231–253. J. von zur Gathen, Parallel arithmetic computations: a survey, in Proc. 13th Symp. MFCS 1986, Springer LN Comput. Sci. 233 (1986), 93–112. M. Giusti and J. Heintz, Algorithmes — disons rapides — pour la décomposition d’une variété algébrique en composantes irréductibles et équidimensionelles, in Effective Methods in Algebraic Geometry, Proc. Intern. Conf. MEGA 90, Castiglioncello 1990, T. Mora and C. Traverso, eds., Progress in Mathematics 94, Birkhäuser (1991a), 169–193. M. Giusti and J. Heintz, La détermination des points isolés et de la dimension d’une variété algébrique peut se faire en temps polynomial, Manuscript, Centre de Mathématiques, École Polytechnique, Palaiseau (1991b). To appear in Proc. Intern. Meeting on Commutative Algebra, Cortona, Cambridge University Press, 1991. J. Heintz, Definability and fast quantifier elimination over algebraically closed fields, Theoret. Comput. Sci. 24 (1983), 239–277; Russian translation in: Kybernetičeskij Sbornik, Novaja Serija, Vyp. 22, Mir Moskva (1985), 113–158. J. Heintz, On the computational complexity of polynomials and bilinear mappings. A survey, in Applied Algebra, Algebraic Algorithms and Error-Correcting Codes, 5th Intern. Conf. AAECC-5, Menorca 1987, L. Huguet and A. Poli, eds., Springer LN Comput. Sci. 356 (1989), 269–300. J. Heintz and C.P. Schnorr, Testing polynomials which are easy to compute, in Logic and Algorithmic. An International Symposium held in Honour of Ernst Specker, Monographie de l’Enseignement Mathématique, Genève 1982, 237–254; also published in 12th Annual ACM Symp. Theory of Computing (1980), 262–268. J.P. Jouanolou, Théorèmes de Bertini et applications, Progress in Mathematics 42, Birkhäuser 1983. H. Kobayashi, S. Moritsugu and R.W. Hogan, On solving systems of algebraic equations, in Proc. Intern. Symp. on Symbolic and Algebraic Computation, ISSAC 88, Rome 1988, P. Gianni, ed., Springer LN Comp. Sci. 358 (1989).

J. Kollár, Sharp effective Nullstellensatz, J. Amer. Math. Soc. 1 (1988), 963–975.

T.Y. Lam, Serre’s Conjecture. Springer LN Math. 635 (1978).

H. Matsumura, Commutative ring theory, Cambridge Studies in Advanced Mathematics 8, Cambridge University Press, Cambridge 1989.

K. Mulmuley, A fast parallel algorithm to compute the rank of a matrix over an arbitrary field, Combinatorica 7(1987), 101-104.

F. Rossi and W. Spangher, Some effective methods in the openness of loci for Cohen-Macaulay and Gorenstein properties, in Effective Methods in Algebraic Geometry, Proc. Intern. Conf. MEGA 90, Castiglioncello 1990, T. Mora and C. Traverso, eds., Progress in Mathematics 94, Birkhäuser (1990), 441–455.

H.-J. Stoss, On the representation of rational functions of bounded complexity, Theoret. Comput. Sci. 64 (1989), 1–13.

V. Strassen, Berechnung und Programm I, Acta Inform. 1 (1972), 320–334.

B. Teissier, Résultats récents d’algèbre commutative effective, in Séminaire Bourbaki, Volume 1989/90, Exposé 718, novembre 1989, Astérisque 189–190 (1991), 107–131.

L.G. Valiant, S. Skyum, S. Berkowitz and C. Rackoff, Fast parallel computation of polynomials using few processors, SIAM J. Comput. 12 (1983), 641–644.

Marc Giusti  Joos Heintz
Groupe “Aleph et Géode”,  Departamento de Matemáticas,
Centre de Mathématiques,  Estadística y Computación
École Polytechnique,  Universidad de Cantabria
F–91128 Palaiseau Cedex, France  39071 Santander, Spain

giusti@ariana.polytechnique.fr   heintz@ccucvx.unican.es

Juan Sabia Departamento de Matemática, FCEyN Univ. Buenos Aires Ciudad Universitaria, Pab. I 1428 Buenos Aires, Argentina

willie@mate.edu.ar