Probabilistic Algorithms for Geometric Elimination

Guillermo Matera^{1} ^{2} ^{⋆}

1 Laboratorio de Computación, Universidad Favaloro Solís 453 (1078) Buenos Aires, Argentina

2 Instituto de Desarrollo Humano, Universidad Nacional de General Sarmiento

Roca 850 (1663) San Miguel, Argentina

                     gmatera@ungs.edu.ar
               This paper is published in
Applicable Algebra in Engineering, Communication and Computing
                9(6), 1999, pp.463-521.

Abstract. We develop probabilistic algorithms that solve problems of geometric elimination theory using small memory resources. These algorithms are obtained by means of the adaptation of a general transformation due to A. Borodin which converts uniform boolean circuit depth into sequential (Turing machine) space. The boolean circuits themselves are developed using techniques based on the computation of a primitive element of a suitable zero–dimensional algebra and diophantine considerations. Our algorithms improve considerably the space requirements of the elimination algorithms based on rewriting techniques (Gröbner solving), having simultaneously a time performance of the same kind of them.

Keywords. Probabilistic algorithms, elimination theory, boolean circuits, arithmetic circuits.

1 Introduction

We use standard notions and notations for boolean complexity models and boolean complexity classes as can be found in [4], [3] or [63]. We recall that the classes NC^{i} are defined as the set of O(log^{i} n)–uniform families of boolean circuits of polynomial size and depth O(log^{i} n) with bounded fan-in. A family of boolean circuit is called S(n)–space uniform if its standard encoding can be built using deterministic space S(n).

We will also use the model of division–free arithmetic circuits (see e.g. [22],

[23] or [1]). Let R be a ring. An arithmetic circuit β over R is a directed acyclic graph (dag for short) Γ (β), where all nodes have bounded indegree of either 0 or 2. The nodes of indegree 0 representing input nodes are labeled by indeterminates

⋆ Work partially supported by the following Argentinian grants: UBACYT TW80, PIP CONICET 4571, ANPCYT PICT 03–00000-01593.

X_{1}, …, X_{n}, the nodes of indegree 0 representing parameter nodes are labeled by elements of R and the nodes of indegree 2 (called internal nodes) are labeled by arithmetic operations. The elements of R occurring in parameter node are called parameters of the arithmetic circuit β. Finally, nodes with out–degree 0 are called output nodes.

An arithmetic circuit β is called division–free if it contains no divisions. We define the size of a division–free arithmetic circuit β as the number of internal nodes occurring in β. The depth of β is defined as the length of the longest path which joins an input node with an output node. A node ρ of β is nonscalar if it has the following property: the node ρ has indegree 2, the arithmetic operation of ρ is a multiplication and predecessor nodes of ρ are not parameter nodes. The nonscalar depth of β is defined as the length of the longest path joining an input node with an output node when only nonscalar nodes are considered.

In the sequel we are going to use a general argument due to A. Borodin [7] (see also [21]), which allows to turn uniform boolean circuit depth (parallel time) into sequential space. This argument allows us to re–interpret the property of well parallelizability of a boolean function as the use of a very small amount of working space in the scope of sequential computing. Moreover, Borodin’s argument is constructive, so that given a family of boolean circuits in NC^{i} and an algorithm which witnesses its uniformity, we are going to use this argument for the transformation of the given data into an equivalent sequential algorithm which works in space O(log^{i} n).

Our intention is to adapt this idea to the context of geometric elimination theory. The first systematic attempts in this direction were made in [53] and [52] (see also [54] and [47] in the context of algebraic elimination theory), where deterministic algorithms were designed for the resolution of selected problems of geometric elimination. These algorithms, although very efficient with respect to the management of memory space, have the drawback of a poor time performance. This unsuitable behaviour with respect to running time makes prohibitive the practical applicability of these algorithms. In order to speed up the computations we are going to introduce randomness in our procedures.

The central idea of the method of [53] consists in the reduction of elimination problems to linear algebra computations. These reductions rely on suitable versions of effective Nullstellensätze (cf. [35] or [58]). Unfortunately, the matrices occurring in these reductions have exponential size, mainly due to the syntactical aspect of the kind of problems under consideration. By this syntactical aspect we refer to the codification of multivariate polynomials which represent the basic objects of the language.

Taking into account that an n–variate polynomial of degree d has ( \begin{matrix}d + n \\ n \end{matrix} )

distinct monomials (this quantity can be estimated as O(d^{n})), we see that the usual dense or sparse codification of polynomials (i.e. the representation of polynomials by means of the vector of all or all nonzero coefficients) implies an exponential behaviour of such a data structure. In order to avoid this exponential behaviour we are going to introduce an alternative codification of intermediate and final results by means of arithmetic circuits. The fact that the polynomials which occur in our procedures are “special” in some sense will allow us to take advantage of this codification.

The codification of polynomials by means of arithmetic circuits has the disadvantage of its nonuniqueness. We use probabilistic tests for the verification of identities of polynomials given by arithmetic circuits. Such probabilistic tests consist in the evaluation of the two polynomials under consideration in some points chosen at random in a suitable set. Throughout this work we are going to consider two alternative test methods: the Schwartz–Zippel test (see e.g. [37], Corollary 2.1; see also [60], [64], [41], [38]) and the Heintz–Schnorr test (see e.g. [36], Theorem 4.4; [45], Corollary 19 or [58]).

An important point of our algorithmic method is the representation of algebraic varieties by means of primitive element techniques. The idea — which is originally due to Kronecker [46] and has been applied in several papers such as [2], [11], [13], [14], [24], [26], [28], [29], [30], [43], [45], [49], [51], [56] — consists in finding a “pseudo–parameterization” of the variety under consideration which, at the same time, provides valuable algebraic information. This pseudo–parameterization is given by a curve parameterized by a primitive element u (which is a linear form that separates points) together with a polynomial condition on u in order to determine which of the points of this curve belongs to the variety under consideration.

The information we obtain from such a representation is applied systematically in order to solve the following geometric elimination problems: the decision of the consistency of a given system of polynomial equations, the membership problem for complete intersection ideals, the computation of a Bézout identity in the case of inconsistent polynomial equation systems, the reduction of a given polynomial modulo a given complete intersection ideal, and the determination of the dimension of a given algebraic variety. As a further application we obtain an algorithmic version of Quillen–Suslin theorem that requires —for the first time— only polynomial space.

Let us also mention that we apply a particular method of size reduction to the matrices occurring during our procedures. This method of reduction relies on arguments on the regularity of the Hilbert function of a suitable graduate ring as in [51], [9] or [28] (see also [61]) or the division modulo a complete intersection ideal by means of a trace formula as in [20] or [45] (see also [2], [5], [12] and [59]).

Applying all these tools we build arithmetic circuits which have certain nodes that are generated randomly. Then we translate these arithmetic circuits into boolean circuits following a general method which allows an efficient translation and show the uniformity of the families of boolean circuits obtained in this way. For this purpose we prove a “Macro expansion lemma” which allows us to simplify considerably the discussion on the uniformity of the families of boolean circuits we obtain. Finally we apply Borodin’s argument in order to get sequential algorithms with small space requirements and improved time performance with respect to those of [53]. The random integers we use in our procedures are generated at the beginning of the execution of the algorithm and fully stored in memory space.

We describe our algorithms in the model of bounded error probabilistic Turing machines (see e.g. [4]). They work in space O(n^{4} log^{2}(shd)) and in time

(shd)^{O(n^{2} log(shd))}, where s in the number of input polynomials, n is the number of variables they contain and d and h are upper bounds for their degree and logarithmic height respectively (with logarithmic height we refer to the maximal binary size of the coefficients of the polynomials involved). These bounds improve

considerably the (simultaneous) O(n^{4} log^{2}(shd)) space and (shd)^{O(n^{4} log(shd))} time bounds of [53], and the (shd)^{O(n^{2})} space and (shd)^{O(n^{2})} time bounds of the algorithms based on Gröbner basis computations (see [25], [44], [17] and [55]).

Let us mention in this context that the probabilistic (hsd^{n})^{O(1)} space and (hsd^{n})^{O(1)} time bounds of the algorithms of [45] and the probabilistic (nhδη)^{O(log n)} space and (nhδη)^{O(log n)} time bounds of the algorithms of [29], [26], [57] and [31] (here δ and η are geometric parameters that can be estimated, in worst case, by d^{n} and hd^{n} respectively) have a better time performance than our procedures but require much more space than ours.

Let us also mention the O(n^{2} log^{2}(hδηd)) space and (hηδd)^{O(n^{2} log(hδηd))} time bounds of [52] that, although worse than ours in worst case, may be of practical interest for special well suited input polynomial equation systems.

2 On arithmetic and boolean circuits

The elimination problems we are considering here can be naturally described by division–free arithmetic circuits. Borodin’s argument demands a translation process of these arithmetic circuits into their boolean counterparts, once a bound for the size of the integers occurring as inputs in the arithmetic circuits has been fixed.

The control of the logarithmic height of the integers occurring in our arithmetic circuits is unavoidable for the sake of an efficient translation. In order to perform this control we are going to pay special attention to the nonscalar depth of our arithmetic circuits, that is, the depth of essential multiplications. As shown in [45], there is a close relation between the nonscalar depth and the logarithmic height of the output, while restricting the arithmetic circuits to integer inputs and constants.

The translation process from arithmetic circuits to boolean circuits can be described roughly as a “macro expansion” procedure, in which every arithmetic operation is replaced by a boolean circuit that performs the arithmetic operation on integer numbers of prescribed logarithmic height. In order to achieve efficiency in this process we implement the addition of several integers by means of carry save adder circuits (see e.g. [63]).

Another important point is the uniformity of the families of boolean circuits under consideration. This condition is unavoidable to keep the requirements of memory space within reasonable limits. In the sequel we are going to discuss the uniformity of the arithmetic circuits we develop rather than the uniformity of the boolean circuits we obtain after the translation. As we will show in Lemma 1 our translation procedure maps uniform families of arithmetic circuits into uniform families of boolean circuits.

Furthermore, the discussion of the uniformity of our families of arithmetic circuits can be simplified further by allowing the introduction of “arithmetic macros”, whose uniformity is known. For this purpose we have to deal with circuits over ZZ with unbounded fan–in and unbounded fan–out, which we are going to call generalized arithmetic circuit.

Definition 1. A generalized arithmetic circuit β over ZZ is a directed acyclic graph (dag for short) Γ (β) whose nodes are labeled. The nodes of Γ (β) of indegree 0 are labeled either by indeterminates X_{1}, …, X_{n} (the input nodes) or by elements of ZZ (the parameter nodes). The remaining nodes are labeled by a fixed set of polynomial maps with integer coefficients Φ_{1}, …, Φ_{r}. The nodes with out–degree 0 are called output nodes.

For 1 ≤ i ≤ r we define the size of β in Φ_{i} as the number of nodes labeled by Φ_{i} occurring in β. The depth of β in Φ_{i} is defined as the highest number of occurrences of nodes labeled by Φ_{i} in a path joining an input node with an output node.

We assume that the nodes of a generalized arithmetic circuit with n input nodes are numbered in such a way that the input nodes are numbered from 1 to n. The standard encoding of a generalized arithmetic circuit C is a list having one entry for every node appearing in the dag associated to C in the following way:

• every node labeled by an integer m is encoded by (ρ, m), where ρ denotes the node number.

• every node labeled by a polynomial map is encoded by (ρ, op, ρ_{1}, …, ρ_{r}), where ρ denotes the node number, op identifies the polynomial map and ρ_{j} is a pair indicating the node number and coordinate whose output is the j–th input of ρ.

A family of generalized arithmetic circuits is a sequence of generalized arithmetic circuits {C_{n}}_{n∈IN} together with a sequence of finite sets of polynomials maps {Φ_{1}^{(n)}, …, Φ_{r_{n}}^{(n)}}_{n∈IN} , such that the circuit C_{n} has n^{O(1)} input nodes and its nodes are labeled by the polynomial maps Φ_{1}^{(n)}, …, Φ_{r_{n}}^{(n)}. A family of generalized arithmetic circuits {C_{n}}_{n∈IN} is called uniform in space S(n) if there exists a deterministic Turing machine M such that, on input n, computes the standard encoding of the circuit C_{n} using space S(n).

The main result of this section, Lemma 1, is the key tool which allows us to give a systematic treatment of the uniformity question of the algorithms which we are going to develop throughout this contribution. Lemma 1 shows that a family of generalized arithmetic circuits which is uniform in small space, whose nodes are labeled by a sequence of polynomial maps which is uniform in small space has an efficient boolean translation. In order to prove this result we need to introduce some terminology.

Let C be a generalized arithmetic circuit over ZZ with n inputs and let h be a fixed positive integer. We say that a boolean circuit D is associated to C at logarithmic height h if the circuit D computes, given the binary representation of n integers m_{1}, …, m_{n} of h bits as input, the binary representation of the output of C on input (m_{1}, …, m_{n}). Given a family of generalized arithmetic circuits {C_{n}}_{n∈IN} and a sequence {h_{n}}_{n∈IN} , we say that a family of boolean circuits {D_{n}}_{n∈IN} is associated to {C_{n}}_{n∈IN} at logarithmic height {h_{n}}_{n∈IN} if for any n ∈ IN the circuit D_{n} is associated to C_{n} at logarithmic height h_{n}. Now we can state the main result of this section:

Lemma 1 ((Macro expansion lemma)). Let {C_{n}^{(1)}}_{n∈IN} , …, {C_{n}^{(r)}}_{n∈IN} be families of division–free arithmetic circuits of size Λ_{1}(n), …, Λ_{r}(n) and nonscalar depth λ_{1}(n), …, λ_{r}(n) respectively. Assume that the families {C_{n}^{(1)}}_{n∈IN} , …, {C_{n}^{(r)}}_{n∈IN} use parameters of logarithmic height bounded by {η_{1}^{(n)}}_{n∈IN} , …, {η_{r}^{(n)}}_{n∈IN} , respectively and that they are uniform in space S̃_{1}(n), …, S̃_{r}(n) respectively. For 1 ≤ k ≤ r we denote by Φ_{n}^{(k)} the polynomial map computed by the arithmetic circuit C_{n}^{(k)}. Assume further that for any sequence {(h_{1}^{(n)}, …, h_{r}^{(n)})}_{n∈IN} ⊆ (ZZ^{+})^{r} there exist families of boolean circuits {C_{n}^{(1)}(h_{1}^{(n)})}_{n∈IN} , …, {C_{n}^{(r)}(h_{r}^{(n)})}_{n∈IN} associated to {C_{n}^{(1)}}_{n∈IN} , …, {C_{n}^{(r)}}_{n∈IN} at logarithmic height {(h_{1}^{(n)}, …, h_{r}^{(n)})}_{n∈IN} with size L_{1}(n, h_{1}^{(n)}), …, L_{r}(n, h_{r}^{(n)}) and depth ℓ_{1}(n, h_{1}^{(n)}), …, ℓ_{r}(n, h_{r}^{(n)}), which are uniform in space S_{1}(n, h_{1}^{(n)}), …, S_{r}(n, h_{r}^{(n)}) respectively. Let {C_{n}}_{n∈IN} be a family of generalized arithmetic circuits using parameters of logarithmic height bounded by {η_{n}}_{n∈IN} which is uniform in space S(n). Assume that the nodes of the circuit C_{n} are labeled by Φ_{1}^{(n)}, …, Φ_{r}^{(n)} and that C_{n} has size Γ_{i}(n) and depth γ_{i}(n) in Φ_{i}^{(n)} for 1 ≤ i ≤ r. Then, for any sequence {h_{n}}_{n∈IN} ⊆ ZZ^{+} there exists a family of boolean circuits {C_{n}(h_{n})}_{n∈IN} associated to {C_{n}}_{n∈IN} at logarithmic height {h_{n}}_{n∈IN} with size ∑_{k=1}^{r} ∑ Γ_{i}(n)L_{i}(n, H_{n}) and depth ∑_{i=1}^{r} γ_{i}(n)ℓ_{i}(n, H_{n}) which is uniform in space ∑_{i=1}^{r} (S̃_{i}(n) + S_{i}(n, H_{n})) + S(n) + log ( ∑_{i=1}^{r} Γ_{i}(n)L_{i}(n, H_{n})) + log H_{n}, where H_{n} denotes the number

H_{n} = 2^{1+∑_{i=1}^{r} λ_{i}(n)γ_{i}(n)}( log ( ∑_{i=1}^{r} Γ_{i}(n)Λ_{i}(n)) + max_{i}{η_{i}^{(n)}, η_{n}} + h_{n}).

Proof. The construction of the family of boolean circuits {C_{n}(h_{n})}_{n∈IN} can be seen as a macro expansion procedure. This macro expansion follows three basic rules: first, every input node ρ of C_{n} is replaced by h_{n} input nodes of C_{n}(h_{n}) representing the h_{n} binary digits of the integer corresponding to the node ρ. Secondly, every node of C_{n} labeled by an integer parameter α is replaced by η_{n} nodes of C_{n}(h_{n}) labeled by the binary digits of α. Finally, every occurrence of a node ρ of C_{n} labeled by C_{n}^{(i)} is replaced in C_{n}(h_{n}) by a boolean circuit C_{n}^{(i)}(H_{n}^{(ρ)}) that computes the binary representation of the output of C_{n}^{(i)} on integer numbers with logarithmic height H_{n}^{(ρ)}. We choose H_{n}^{(ρ)} as the worst– case logarithmic height of the inputs of the node ρ under consideration when the inputs of C_{n} are integers of logarithmic height bounded by h_{n}.

In order to compute the number H_{n}^{(ρ)} we observe that, if the circuit C_{n} applies Γ_{i}^{(ρ)}(n) times the morphism Φ_{i}^{(n)} with depth γ_{i}^{(ρ)}(n) for 1 ≤ i ≤ r to compute the result of the node ρ, applying [45], Proposition 15 we see that the num-

ber H_{n}^{(ρ)} can be bounded by 2^{1+∑_{i=1}^{r} λ_{i}(n)γ_{i}^{(ρ)}(n)}( log ( ∑_{i=1}^{r} Λ_{i}(n)Γ_{i}^{(ρ)}(n)) +

max_{i}{η_{i}^{(n)}, η_{n}} + h_{n}). Note that the circuit C_{n} can be executed by performing

∑_{i=1}^{r} Λ_{i}(n)Γ_{i}(n) arithmetic operations with nonscalar depth at most ∑_{i=1}^{r} λ_{i}(n)γ_{i}(n), which implies that for every node ρ of C_{n} the number H_{n}^{(ρ)} is bounded by

H_{n} := 2^{1+∑_{i=1}^{r} λ_{i}(n)γ_{i}(n)}( log ( ∑_{i=1}^{r} Λ_{i}^{(ρ)}(n)Γ_{i}^{(ρ)}(n)) + max_{i}{η_{i}^{(n)}, η_{n}} + h_{n}).

Therefore, the macro expansion procedure yields a boolean circuit C_{n}(h_{n}) associated to C_{n} at logarithmic height h_{n} whose size is bounded by ∑_{i=1}^{r} Γ_{i}(n)L_{i}(n, H_{n}) and its depth is at most ∑_{i=1}^{r} γ_{i}(n)ℓ_{i}(n, H_{n}).

There remains to prove the uniformity of the family of boolean circuits {C_{n}(h_{n})}_{n∈IN} . The hypotheses of Lemma 1 imply that there exist deterministic Turing machines M, M_{1}, M̃_{1}, …, M_{r}, M̃_{r} working in space S(n), S_{1}(n, h), S̃_{1}(n), …, S̃_{r}(n), S_{r}(n, h) such that, given a tuple (n, h) as input, they compute the standard encoding of the circuits C_{n}, C_{n}^{(1)}(h), C_{n}^{(1)}, …, C_{n}^{(r)}(h), C_{n}^{(r)} respectively. We are going to construct a deterministic Turing machine N such that, given a tuple (n, h_{n}) as input, it computes the standard encoding of C_{n}(h) working in space ∑_{i=1}^{r} (S̃_{i}(n) + S_{i}(n, H_{n})) + S(n) + log ( ∑_{i=1}^{r} Γ_{i}(n)L_{i}(n, H_{n})) + log H_{n}.

First of all, the machine N call the machines M, M̃_{1}, …, M̃_{r} to compute the numbers max_{i}{η_{i}^{(n)}, η_{n}} by simple inspection of the standard encoding of the arithmetic circuits C_{n}, C_{n}^{(1)}, …, C_{n}^{(r)}.

Then N computes the standard encoding of the circuit C_{n}(h_{n}) in the following way: N calls the machine M which generates the standard encoding of C_{n} node by node. N stores in memory space a counter for the number of the next node of C_{n}(h_{n}) to be generated. Every time that the machine M generates an input node of C_{n} N generates h_{n} input nodes of C_{n}(h_{n}). Similarly N generates η nodes of C_{n}(h_{n}) for any node of C_{n} labeled by a parameter. Finally, when a node ρ of C_{n} labeled by C_{n}^{(i)} is found, N computes the numbers ∑_{i=1}^{r} λ_{i}(n)γ_{i}^{(ρ)}(n) and ∑_{i=1}^{r} Λ_{i}(n)Γ_{i}^{(ρ)}(n). For this purpose N computes γ_{i}^{(ρ)}, Γ_{i}^{(ρ)} for 1 ≤ i ≤ r by a depth–first search on the dag associated to C_{n} and λ_{i}(n), Λ_{i}(n) by a simple inspection of the dag associated to C_{n}^{(i)} for 1 ≤ i ≤ r. Then N calls the machine M_{1} on input (n, H_{n}^{(ρ)}) which generates the standard encoding of the boolean subcircuit of C_{n}(h_{n}) corresponding to the node ρ of C_{n}. The working space required by N is obtained by adding the working space of the machines M, M_{1}, M̃_{1}, …, M_{r}, M̃_{r}, the space required to compute and store the number H_{n} and the space necessary for the counter of the number of the next node of the boolean circuit C_{n}(h_{n}) to be generated. Therefore, we have that the machine N has working space ∑_{i=1}^{r} (S̃_{i}(n) + S_{i}(n, H_{n})) + S(n) + log ( ∑_{i=1}^{r} Γ_{i}(n)L_{i}(n, H_{n})) + log H_{n}.

2.1 Uniform linear algebra algorithms

The algorithms which we are going to develop throughout this contribution rely strongly on linear algebra calculations. Therefore, the uniformity of the families of boolean circuits which we are going to develop is closely related to the uniformity of the linear algebra circuits we use. Although several linear algebra algorithms are announced to be space–uniform, no proof of such statements is explicitly shown (see e.g. [6] or [8]).

This section is devoted to review the linear algebra algorithms we need, giving simple proofs of their space–uniformity based on our Macro expansion lemma. These linear algebra algorithms are generally well–known and have been chosen taking into account their space–uniformity and low nonscalar depth rather than the number of arithmetic operations they perform (a similar point of view of ours is followed in [33], [53] and [52]). The only exceptions are the resolution of linear equation systems (Lemma 8) where some additional care is taken in order to avoid branchings in the computation and the computation of the characteristic polynomial (Lemma 5) because the hypotheses of the Macro expansion lemma do not apply.

Lemma 2. There exists a family of boolean circuits {C_{n}(h)}_{n∈IN} which computes the inner product ∑_{i=1}^{n} x_{i}y_{i} of two vectors (x_{1}, …, x_{n}) and (y_{1}, …, y_{n}) of ZZ^{n} of logarithmic height bounded by h with size O(n^{3}h^{2}) and depth O( log(nh)), which is uniform in space O( log(nh)).

Proof. We can describe a generalized arithmetic circuit C_{n} computing the inner product ∑_{i=1}^{n} x_{i}y_{i} by using two basic operations: the product of two integers and the addition of n integers. As it is well known (see for example [42] or [63]) there exists a family of boolean circuits that computes the product of two integers of logarithmic height h with size O(h^{2}) and depth O(log h) which is uniform in space O(log h). Using the well–known three–for–two trick (see e.g. [63]) we obtain a family of boolean circuit computing the addition of n integers of logarithmic height h with size O(n(h + log n)^{2}) and depth O( log(nh)) which is uniform in space O( log(nh)). Observe that C_{n} performs n products with depth 1 and one addition of n integers. Applying the Macro expansion lemma using the product of two integers and the addition of n integers as polynomial maps yields a family of boolean circuits of size O(n^{3}h^{2}) and depth O( log(nh)) which is uniform in space O( log(nh)).

Lemma 3. There exist a family of boolean circuits computing the product of an (m × n) integer matrix by an (n × p) integer matrix of logarithmic height h with size O(n^{3}mph^{2} log^{2} n) and depth O( log(nmph)), which is uniform in space O( log(nmph)).

Proof. We can easily describe a circuit computing a matrix product in terms of inner product. Taking into account that we have to perform mp inner products of n–dimensional vectors, the statement of Lemma 3 follows easily from the bounds of Lemma 2 and the Macro expansion lemma.

Lemma 4. There exist a family of boolean circuits computing the powers A^{2}, A^{3} …, A^{k_{n}} of a given (n × n) integer matrix A of logarithmic height h of size O(k_{n}^{2}n^{5}h^{2} log^{4}(nk_{n})) and depth O( log(k_{n}) log(k_{n}nh)) which is uniform in space O( log(nk_{n}h)).

Proof. The computation of the powers A^{2}, …, A^{k_{n}} can be organized in a tree with k_{n} nodes and depth log k_{n}. In the l–th level of the tree we compute A^{2^{l}+1}, …, A^{2^{l+1}} multiplying the matrices A, A^{2}, …, A^{2^{l}} by A^{2^{l}}. Therefore the computation of A^{2}, …, A^{k_{n}} can be easily described in space O(log k_{n}) in terms of matrix product. Taking into account that 2^{log k_{n}}(log n + h) is an upper bound for the logarithmic height of the integers appearing during the whole computation, the application of the bounds of the Macro expansion lemma and Lemma 3 yields a family of boolean circuits which satisfies the statement of Lemma 4.

Lemma 5. There exist a family of boolean circuits computing the characteristic polynomial of a given (n × n) integer matrix A of logarithmic height h with size n^{O(1)}h^{2} and depth O( log(n) log(nh)), which is uniform in space O( log(nh)).

Proof. We compute the characteristic polynomial by using Berkowitz’s algorithm [6]. Let A := (a_{ij}) be an n × n matrix. For 1 ≤ k ≤ n, we define R_{k} = (a_{k,k+1}, …, a_{k,n}), S_{k} = (a_{k+1,k}, …, a_{n,k}), and for 2 ≤ k ≤ n

M_{k} = ( \begin{matrix}a_{k,k} & ⋯ & a_{k,n} \\ ⋮ & ... & ⋮ \\ a_{n,k} & ⋯ & a_{n,n} \end{matrix} )

Further, we define the lower triangular matrix C_{k} of (n − k + 1) × (n − k) by c_{i,j}^{k} = −1 if i = j, c_{i,j}^{k} = a_{k,k} if i = j +1, and c_{i,j}^{k} = −R_{k} ·M_{k}^{i−j−2} ·S_{k} if i−j ≥ 2. Then we have the equality (p_{0}, p_{1}, …, p_{n})^{t} = ∏_{1≤k≤n} C_{k} where (p_{0}, p_{1}, …, p_{n}) are the coefficients of the characteristic polynomial of A.

Therefore, a family of boolean circuit computing the characteristic polynomial of A can be obtained in the following way: in a first step we compute simultaneously all (M_{k})^{j}’s for 0 ≤ k ≤ n and 0 ≤ j ≤ n − k − 2. From Lemma 4 we deduce that this part has size O( ∑_{k=1}^{n} k^{7}h^{2} log^{4}(k)) = O(n^{8}h^{2} log^{4} n) and depth O( log(n) log(nh)), and the resulting integers have logarithmic height O(nh log n).

In the second step we first compute the product (M_{k})^{j} · S_{k} for 0 ≤ k ≤ n and 0 ≤ j ≤ n − k − 2 in parallel and then, using this results, we compute R_{k} · (M_{k})^{j} · S_{k} for each k, j in parallel. Applying Lemma 3 we conclude that this step has size O(n^{6}h^{2} log^{4} n) and depth O( log(nh)).

Finally we compute the coefficients of the characteristic polynomial of A by the formula (p_{0}, p_{1}, …, p_{n})^{t} = ∏_{1≤k≤n} C_{k}. We perform this stage by means of a tree of matrix products. Taking into account that there are n products of matrices of logarithmic height bounded by O(nh log n), we conclude that this step can be performed with size O(n^{9}h^{2} log^{6}(n)) and depth O( log(n) log(nh)).

Adding the complexities obtained in each step we obtain a family of boolean circuits of size n^{O(1)}h^{2} and depth O( log(n) log(nh)) computing the characteristic polynomial of A.

Now we show that this family is uniform in space O( log(nh)). From Lemma 3 we have that there exists a deterministic Turing machine M^{(1)} such that on input (m, n, p, h) M^{(1)} computes the standard encoding of boolean circuit computing the product of an (m × n)–matrix by an (n × p)–matrix of logarithmic height h using space O( log(nmph)). Similarly, from Lemma 4 we have that there exists a deterministic Turing machine M^{(2)} such that on input (n, k, h) M^{(2)} computes the standard encoding of boolean circuit computing the powers A^{2}, …, A^{k} of an (n × n)–matrix of logarithmic height h.

A deterministic Turing machine M that computes the standard encoding of the family of boolean circuits described above can be constructed in the following way: M starts calling M^{(2)} on input (n − 1, n − 3, h), …, (4, 2, h) to produce the standard encoding of the computation of M_{1}^{2}, …, M_{1}^{n−3}, , …, M_{n−4}^{2}, modifying the output of M^{(2)} in such a way that the input of these matrix powering are the proper submatrices of the input matrix. Then M calls the machine M^{(1)} n − 2 times on input (n − 1, n − 1, 1, nh log n), n − 3 times on input (n − 2, n − 2, 1, nh log n), and so on, to produce the standard encoding of M_{1}^{2}S_{1}, …, M_{1}^{n−3}S_{1}, , …, M_{n−4}S_{n−4}, M_{n−4}^{2}S_{n−4}, M_{n−3}S_{n−3}. Similarly the standard encoding of the computation of the R_{k}M_{k}^{j}S_{k}’s products is produced.

Finally, a repeated calling to M^{(2)} on input (n + 1, n, n_{1}, O(nh log n)), …, produces the standard encoding of the product of the matrices C_{1} ⋯ C_{n}. Taking into account that all the matrices appearing in the procedure have size at most (n + 1) × n and that the logarithmic height of the integers occurring during the procedure is bounded by O(nh log n), we conclude that the machine M works in space O( log(nh)).

Lemma 6. There exist a family of boolean circuits computing the rank of a given (n × m) integer matrix A of logarithmic height h with size n^{O(1)}h^{2} log^{2} m and depth O( log(n) log(nmh)), which is uniform in space O( log(nmh)).

Proof. Let B := A · A^{t}. As it is well–known n − rk(A) equals the multiplicity of zero in the characteristic polynomial of B. This consideration yields an algorithm for the computation of the rank of an integer matrix.

Therefore, we compute the rank of A in the following way: first we compute the matrix B = A·A^{t}. Then we compute the coefficients (p_{0}, …, p_{n}) of the characteristic polynomial of B. Finally, we compute the number rk(A) = max{i; 1 ≤ i ≤ n ∧ p_{i} ≠ 0} from the boolean encoding of the p_{i}’s. For this sake, we design subcircuits “p_{i} = 0” and “p_{i} ≠ 0”, which have the same boolean value of truth as the quoted statement. Suppose that p_{i} = (p_{i_{s}}, …, p_{i_{0}}) is the boolean representation of p_{i}. Then p_{i} = 0 if and only if all its digits are zero, i.e. if and only if p_{i_{s}} ∨ ⋯ ∨ p_{i_{0}} = 0. Therefore, the operator ¬(p_{i_{s}} ∨ ⋯ ∨ p_{i_{0}}) has the same value of truth that p_{i} = 0, and the same is true for p_{i_{s}} ∨ ⋯ ∨ p_{i_{0}} and p_{i} ≠ 0. Then, for every 1 ≤ i ≤ n we compute “p_{0} = 0∧p_{1} = 0∧⋯∧p_{i} ≠ 0” by means of a tree of conjunctions of the previously constructed subcircuits. Finally, given a natural number i such that 1 ≤ i ≤ n with boolean representation i = (i_{s}, …, i_{0}), we define ĩ = (ĩ_{s}, …, ĩ_{0}) by ĩ_{k} := (p_{0} = 0 ∧ p_{1} = 0 ∧ ⋯ ∧ p_{i} ≠ 0) ∧ i_{k}, which returns the k-th digit of i if and only if the affirmation p_{0} = 0 ∧ p_{1} = 0 ∧ ⋯ ∧ p_{i} ≠ 0 is true and 0 otherwise. Therefore, the disjunction ⋁_{1≤i≤n} ĩ_{k} outputs the k-th digit of max{i; 1 ≤ i ≤ n ∧ p_{i} ≠ 0}.

The computation of the matrix B and its characteristic polynomial has size n^{O(1)}h^{2} log^{2} m and depth O( log(n) log(nmh)). The computation of the rank of A from the coefficients of the characteristic polynomial has size O(n^{3}h) and depth O( log(n) log(nmh)). Therefore, we have a family of boolean circuits of size n^{O(1)}h^{2} log^{2} m and depth O( log(n) log(nmh)) which computes the rank of an integer matrix.

There remains to prove the uniformity of this family. The computation of the matrix B and its characteristic polynomial consists of a matrix product and the computation of a characteristic polynomial. Therefore, applying the Macro expansion lemma and Lemmata 3 and 5 we obtain a deterministic Turing machine working in space O( log(nmh)) which computes the standard encoding of the computation of B and its characteristic polynomial. The remaining part can be easily described using space O( log(nmh)).

Lemma 7. There exists a family of boolean circuits computing the adjoint matrix of an (n × n) integer matrix A of logarithmic height h with size n^{O(1)}h^{2} and depth O( log n log(nh)), which is uniform in space O( log(nh)).

Proof. Let B := Adj(A) be the adjoint matrix of an integer (n × n)–matrix A. Let χ(T) := T^{n} + p_{n−1}T^{n−1} + ⋯ + p_{1}T + p_{0} be the characteristic polynomial of A. Then we have that

B = −A^{n−1} − p_{n−1}A^{n−2} − ⋯ − p_{1}I_{n×n}  (1)

(here I_{n×n} denotes the n × n–identity matrix).

Therefore, from equation (1) we deduce an algorithm to compute the adjoint matrix of A. This algorithm computes the matrices A^{2}, …, A^{n−1}, the coefficients of the characteristic polynomial of A and then it performs the linear combination of the matrices I_{n×n}, A, A^{2}, …, A^{n−1} indicated in equation (1). We apply Lemmata 4 and 5 to compute the matrices A^{2}, …, A^{n−1} and the coefficients of the characteristic polynomial of A. Then we compute the matrices −A^{n−1}, −p_{n−1}A^{n−2}, …, −p_{1}I_{n×n} and we add these matrices using the three– for–two trick. As a consequence of the bounds of Lemmata 4 and 5 we conclude that there exists a family of boolean circuits computing the adjoint matrix of size n^{O(1)}h^{2} and depth O( log(n) log(nh)).

In order to prove the uniformity of the algorithm described above we apply the Macro expansion lemma with matrix powering, computation of the characteristic polynomial, product of two integers and addition of n integers as arithmetic macros. We observe that the multiplications and additions required to compute the linear combination of equation (1) involve integers of logarithmic height O(nh log n). Therefore, from the bounds of Lemmata 4 and 5 and the fact that the product of two integers and the addition of n integers of logarithmic height O(nh log n) are uniform in space O( log(nh)), we conclude that the algorithm for the computation of the adjoint matrix described above is uniform in space O( log(nh)).

Lemma 8. There exists a family of boolean circuits of size n^{O(1)}h^{2} and depth O( log n log(nh)) which is uniform in space O( log(nh)) such that it checks whether there exists a solution of a given linear equation system A · X = b (here A is integer (n × m)–matrix of logarithmic height h, X is a (m × 1)–vector of unknowns and b an integer (n × 1)–vector of logarithmic height h), and, if this is the case, it computes numerators and denominators of a particular solution of the system.

Proof. The idea is to reduce our problem to the resolution of a system with a nonsingular square matrix. The second system is then solved applying just Cramer’s rule.

The reduction of the problem is done by an algorithm which finds a nonsingular square submatrix of maximal rank of A. Let us denote this submatrix by Ã. Deleting from b all the entries which do not correspond to rows of Ã we obtain a column vector b̃ and deleting from X all entries which do not correspond to the columns of Ã we obtain a new column vector X̃ of unknowns.

Solving now the reduced nonsingular square system of linear equations Ã·X̃ = b̃ we obtain easily a solution of the original system A · X = b.

Therefore, we just need to find a square submatrix Ã of A with maximal rank. Let us denote by A_{i} the i-th row of A. We compute (in parallel) rk(A_{1}, …, A_{i}) for i = 1, …, n. Every time when rk(A_{1}, …, A_{i−1}) < rk(A_{1}, …, A_{i}) occurs, we keep the index i. These indices are indicated in a vector R = (r_{1}, …, r_{n}) ∈ {0, 1}^{n} as the nonzero entries of R and correspond to the rows which will occur in our matrix Ã. Similarly we compute a vector S = (s_{1}, …, s_{n}) ∈ {0, 1}^{m} whose nonzero entries correspond to the columns which we choose to build Ã. The procedure to compute the vector R requires the computation of the rank of n submatrices of the matrix A and the comparison of the last digits of the numbers rk(A_{1}, …, A_{i−1}) and rk(A_{1}, …, A_{i}) for 1 ≤ i ≤ n (since rk(A_{1}, …, A_{i}) is either rk(A_{1}, …, A_{i−1}) or rk(A_{1}, …, A_{i−1}) + 1). Therefore, it can be performed with size n^{O(1)}h^{2} log^{2} m and depth O( log(n) log(nmh)). We compute the vector S in the same way with size n^{O(1)}h^{2} log^{2} m and depth O( log(n) log(nmh)).

Assume that n ≥ m (the other case can be solved in a similar way). We multiply the input matrix A at right by an (m × n)–matrix with all its entries zero except for its diagonal which is given by the vector S. Then we multiply the resulting matrix and the vector b at left by a diagonal (n × n)–matrix whose diagonal is given by the vector R. The resulting matrix B is an (n × n)–matrix with the same entries as A whenever they correspond to the rows and columns we have chosen to form Ã and zero otherwise. Similarly, the vector c obtained in this way has the same entries as b whenever they correspond to the coordinates we have chosen to form b̃ and zero otherwise.

Let r_{i_{1}}, …, r_{i_{k}} and s_{j_{1}}, …, s_{j_{k}} denote the zero coordinates of R and S (where S is an n–dimensional vector whose last n − m coordinates are zero). We define the (n × n) matrix B̃ which has as only nonzero entries those corresponding to (r_{i_{1}}, s_{i_{1}}), …, (r_{i_{k}}, s_{i_{k}}), which are define to be 1. Adding this matrix to B we obtain a nonsingular (n × n)–matrix C having the property that the first m coordinates of the solution the linear equation system C · Y = c is a particular solution of the linear equation system A · X = b. We compute the solution of the linear equation system C · Y = c as Y = \frac{1}{det(C)}Adj(C) · c.

Applying Lemmata 6, 7 and 3 we see that the whole procedure can be executed by means of a family of boolean circuits of size n^{O(1)}h^{2} and depth O( log n log(nh)).

Now we show the uniformity of the family of boolean circuits described above. From Lemma 6 we have that there exists a deterministic Turing machine M_{1} such that, on input (n, m, h), computes the standard encoding of a family of boolean circuits computing the rank of an (n × m) integer matrix of logarithmic height h.

The deterministic machine M which computes the standard encoding of the family of boolean circuits solving a linear equation system calls M_{1} on input (n, 1, h), (n, 2, h), …, (n, m, h) to produce the standard encoding of a boolean circuit computing the rank of the matrices (A_{1}), (A_{1}, A_{2}), …, (A_{1}, …, A_{m}) = A. Similarly, M produces the standard encoding of a boolean circuit computing the rank of the matrices (A^{(1)}), (A^{(1)}|A^{(2)}), …, (A^{(1)}| … |A^{(m)}) = A (here A^{(i)} denotes the i–th column of A) by calling to M_{1} on input (1, m, h), (2, m, h), …, (n, m, h). Then M produces the standard encoding of the subcircuit computing the vectors R and S and the matrix C with space O( log(nh)). The remaining part of the circuit can be described in terms of matrix products and computation of the adjoint matrix. Therefore, applying Lemmata 3 and 7 and the Macro expansion lemma the statement in Lemma 8 follows.

On the basis of these linear algebra algorithms we are going to build the basic algorithms we need. These algorithms are concerned with the manipulation of univariate polynomials and arithmetic circuits. We start with the consideration of the manipulation of univariate polynomials.

2.2 Manipulation of univariate polynomials

Let R be the polynomial ring ZZ[X_{1}, …, X_{n}], K := Q (X_{1}, …, X_{n}) its quotient field and let T be an indeterminate over K. During this subsection we will be concerned with algebraic manipulations with univariate polynomials f, g ∈ R[T]. All these manipulations will be well–parallelizable (see [4] or [63]) and will contain no divisions by elements of R (this is important since divisions by elements of R may cause serious problems while evaluating the variables X_{1}, …, X_{n} in some concrete point of ZZ^{n}).

The first problem to be consider, assuming that g|f holds in K[T] is the computation of a polynomial of K[T] which represents the quotient \frac{f}{g}.

Lemma 9. Let {C_{n,d,e,h}}_{n,d,e,h∈IN} be a family of boolean circuits which evaluates polynomials f_{0}, …, f_{d}, g_{0}, …, g_{e} of ZZ[X_{1}, …, X_{n}] on integers of logarithmic height h. Let L := L(n, d, e, h) and ℓ := ℓ(n, d, e, h) be the size and depth of C_{n,d,e,h} respectively, and assume that the family {C_{n,d,e,h}}_{n,d,e,h∈IN} is uniform in space S := S(n, d, e, h). Let H := H(n, d, e, h) the worst–case logarithmic height of the output of C_{n,d,e,h}. Let f := f_{d}T^{d} + ⋯ + f_{0} and let g := g_{e}T^{e} + ⋯ + g_{0}. Assume that d ≥ e holds and that g divides f over Q (X_{1}, …, X_{n})[T]. Then, there exists a family of boolean circuits of size L + d^{O(1)}H^{2} and depth O(ℓ + log(d) log(dh)) computing a ZZ[X_{1}, …, X_{n}]–multiple of the polynomial of Q (X_{1}, …, X_{n})[T] representing the quotient \frac{f}{g}, which is uniform in space S + O( log(dHL)).

Proof. Considering the polynomial h := \frac{f}{g} with indeterminate coefficients, the condition f = gh can be translated into a linear equation system which is obtained by means of the comparison of the coefficients of f and gh corresponding to the same monomials. This linear system has d equations and d − e + 1 unknowns and has the following form:

( \begin{matrix}g_{e} \\ g_{e−1} & ... \\ ⋮ & ... & g_{e} \\ g_{0} & & g_{e−1} \\ & ... & ⋮ \\ & & g_{0} \end{matrix} ) ( h_{e−d} ; ⋮ ; h_{0} ) = ( f_{d} ; f_{d−1} ; ⋮ ; f_{0} )  (2)

We apply the Macro expansion lemma using the polynomial maps defined by the polynomials f_{0}, …, f_{d}, g_{0}, …, g_{e} and the particular solution of the system (2) obtained by the application of Lemma 8. Taking into account that the coefficients of the matrix of the system (2) has logarithmic height H we conclude that we have a family of boolean circuits computing numerators and denominators of a particular solution of the system (2) of size L + d^{O(1)}H^{2} and depth O(ℓ + log(d) log(dh)), which is uniform in space S + O( log(dH) + log(L + dH)), as stated.

Let us now discuss the problem of the computation of the greatest common divisor of f and g.

Lemma 10. Let {C_{n,d,e,h}}_{n,d,e,h∈IN} be a family of boolean circuits which evaluates polynomials f_{0}, …, f_{d}, g_{0}, …, g_{e} of ZZ[X_{1}, …, X_{n}] on integers of logarithmic height h. Let L := L(n, d, e, h) and ℓ := ℓ(n, d, e, h) be the size and depth of C_{n,d,e,h} respectively, and assume that the family {C_{n,d,e,h}}_{n,d,e,h∈IN} is uniform in space S := S(n, d, e, h). Let H := H(n, d, e, h) the worst–case logarithmic height of the output of C_{n,d,e,h}. Assume that d ≥ e. Let f = f_{d}T^{d} + ⋯ + f_{0} and let g = g_{e}T^{e} + ⋯ + g_{0}. Then, there exists a family of boolean circuits of size L + d^{O(1)}H^{2} and depth O(ℓ + log(d) log(dh)) computing a ZZ[X_{1}, …, X_{n}]– multiple of the greatest common divisor of f and g over Q(X_{1}, …, X_{n})[T], which is uniform in space S + O( log(dHL)).

Proof. We apply techniques based on subresultants (see [15], [10]) in the version of [8]: it turns out that the minimal natural number j such that the j–th principal submatrix P_{j}(f, g) of the Sylvester matrix is nonsingular equals the degree of gcd(f, g) (see Theorem 2.3 in [22]). Furthermore, the last column of the inverse matrix of P_{j}(f, g) provides the coefficients of polynomials r and s such that the equality gcd(f, g) = rf + sg holds.

Following the ideas of Lemma 8, instead of computing the last column of P_{j}(f, g)^{−1} we compute the last column of the matrix Adj(P_{j}(f, g)) which yields a det(P_{j}(f, g))–multiple of the greatest common divisor of f and g.

Therefore, we compute in parallel c_{0} := det(P_{0}(f, g)), …, c_{e} := det(P_{e}(f, g)). Then we compute the boolean formulas “c_{0} = 0”, …, “c_{e} = 0” which have the same value of truth as the quoted statement, with the same idea as in the proof of Lemma 6. From these formulas we obtain the least natural number j such that c_{j} is nonzero evaluating the boolean formulas d_{i} := (c_{0} = 0) ∨ ⋯ ∨ (c_{i−1} = 0) ∨ (c_{i} ≠ 0) for 1 ≤ i ≤ e. Then we compute the last column of the matrix d_{i}Adj(P_{i}(f, g)) for 1 ≤ i ≤ e, obtaining thus coefficients of some polynomials r_{i}, s_{i} which are nonzero if and only if i = j. Finally, we compute the polynomial gcd(f, g) = ∑_{i=0}^{e} r_{i}f + s_{i}g = r_{j}f + s_{j}g. Taking into account that the matrices P_{i}(f, g) and Adj(P_{i}(f, g)) have logarithmic height H and O(dH) respectively, we obtain a family of boolean circuits of size L + H^{2}d^{O(1)} and depth ℓ + O( log(n) log(nH)). The products r_{i}f, s_{i}g for 0 ≤ i ≤ e can be thought as matrix–vector products.

To prove the uniformity of the family of boolean circuits we first construct the standard encoding of the family of boolean circuits which evaluates the polynomials f_{0}, …, f_{d}, g_{0}, …, g_{e} with space S. The mapping which produces the matrices P_{i}(f, g) from f_{0}, …, f_{d}, g_{0}, …, g_{e} can be described easily in space O(log d). Then we call the machine which witnesses the uniformity of the computation of the determinant on input (d + e, H), …, (d − e, H) to construct the standard encoding of the computation of the determinants of the matrices P_{(}f, g), …, P_{e}(f, g) using space O( log(dH)). The standard encoding of the formulas for d_{i} requires space O(log d). Then we construct the standard encoding of the computation of the last columns of the matrices Adj(P_{i}(f, g)) with additional space O( log(dH)) and finally use O( log(dH)) space to describe the computation of the polynomial gcd(f, g) = ∑_{i=0}^{e} r_{i}f +s_{i}g. During all these computations we use a counter to know the number of the next node to be generated which requires O( log(L + dH)) cells of working space. Therefore, we need space S + O( log(dH)) + O( log(L + dH)) to compute the standard encoding of the whole circuit.

The last problem concerning manipulations with univariate polynomials is the determination of a separable representation of f, that is, a polynomial g ∈ K[T] that has the same zeros as f over the algebraic closure \overline{K} of K and is squarefree.

Lemma 11. Let {C_{n,d,h}}_{n,d,h∈IN} be a family of boolean circuits which evaluates polynomials f_{0}, …, f_{d} of ZZ[X_{1}, …, X_{n}] on integers of logarithmic height h. Let L := L(n, d, h) and ℓ := ℓ(n, d, h) be the size and depth of C_{n,d,h} respectively, and assume that the family {C_{n,d,h}}_{n,d,h∈IN} is uniform in space S := S(n, d, h). Let H := H(n, d, h) the worst–case logarithmic height of the output of C_{n,d,h}. Let f = f_{d}T^{d} + ⋯ + f_{0}. Then, there exists a family of boolean circuits of size L+d^{O(1)}H^{2} and depth O(ℓ+log(d) log(dh)) computing a ZZ[X_{1}, …, X_{n}]–multiple of the separable representation g = \frac{f}{gcd(f,f′)}, which is uniform in space S + O( log(dHL)).

Proof. Since Q(X_{1}, …, X_{n}) has characteristic zero, we observe that the polynomial g = \frac{f}{gcd(f,f′)} verifies the required conditions, where f′ denotes the derivative of f with respect to T (notice that the coefficients of f′ can be computed immediately from the coefficients of f). Applying the Macro expansion lemma using the polynomial maps defined by the polynomials f_{0}, …, f_{d}, g_{0}, …, g_{e} and the computation of the greatest common divisor and quotient given by the application of Lemmata 10 and 9 we obtain a family of boolean circuits of size L + d^{O(1)}H^{2} and depth O(ℓ+log(d) log(dh)) computing a ZZ[X_{1}, …, X_{n}]–multiple of the separable representation g = \frac{f}{gcd(f,f′)}, which is uniform in space S + O( log(dHL)).

2.3 Manipulation of arithmetic circuits

During this subsection F will denote a polynomial in R := ZZ [X_{1}, …, X_{n}] of degree at most d given by an arithmetic circuit β of size L and nonscalar depth ℓ. Let again be K := Q (X_{1}, …, X_{n}) and let T be an indeterminate over K.

Different tasks concerning the manipulation of arithmetic circuits are considered in this subsection. As we will see later on, all these manipulations have a uniform structure and only depend on the degree of the input polynomial F. This observation will allows us to conclude that these manipulations are uniform.

We first consider the problem of the interpolation of F with respect to one variable:

Lemma 12. Let {C_{n,d,h}}_{n,d,h∈IN} be a family of boolean circuits which evaluates a polynomial F of ZZ[X_{1}, …, X_{n}] of degree d on integers of logarithmic height h. Let L_{h} := L(n, d, h) and ℓ_{h} := ℓ(n, d, h) be the size and depth of C_{n,d,h} respectively, and assume that the family {C_{n,d,h}}_{n,d,h∈IN} is uniform in space S_{h} := S(n, d, h). Let H_{h} := H(n, d, h) the worst–case logarithmic height of the output of C_{n,d,e,h}. Then, there exists a family of boolean circuits computing the dense representation of F with respect to X_{n} with size L_{max{h,log d}}+d^{O(1)}H_{max{h,log d}} and depth ℓ_{max{h,log d}}+O( log(d) log(dH_{max{h,log d}})), which is uniform in space S_{max{h,log d}} + O( log(dH_{max{h,log d}}L_{max{h,log d}})).

Proof. Since deg(F) = d, in particular deg_{X_{n}}(F) ≤ d, and therefore we can find the dense representation of F with respect to the variable X_{n} by interpolation in d + 1 points of Q . We write F = f_{0} + f_{1}X_{n} + ⋯ + f_{d}X_{n}^{d} where f_{0}, …, f_{d} are polynomials of ZZ[X_{1}, …, X_{n−1}]. Choosing the interpolation points 0, …, d we have:

( \begin{matrix}1 & 0 & … & 0 \\ 1 & 1 & … & 1 \\ ⋮ & ⋮ & & ⋮ \\ 1 & d & … & d^{d} \end{matrix} ) ( f_{0} ; f_{1} ; ⋮ ; f_{d} ) = ( F (X_{1}, …, X_{n−1}, 0) ; F (X_{1}, …, X_{n−1}, 1) ; ⋮ ; F (X_{1}, …, X_{n−1}, d) )  (3)

Therefore solving the system (3) yields the the coefficients of F with respect to X_{n}.

The computation is performed by computing the polynomials F (X_{1}, …, X_{n−1}, 0), F (X_{1}, …, X_{n−1}, 1), …, F (X_{1}, …, X_{n−1}, d) in parallel, constructing the Vandermonde matrix of (3) and solving the system (3). Finally we perform d + 1 (exact) divisions of the solutions of the system (3) given by the application of Lemma 8 by the determinant of the matrix of the system (3). Applying the Macro expansion lemma using as arithmetic macros the computation of F, the resolution of a linear equation system and the exact division of integers, we obtain a family of boolean circuits of size L_{max{h,log d}} + d^{O(1)}H_{max{h,log d}} and depth ℓ_{max{h,log d}}+O( log(d) log(dH_{max{h,log d}})), which is uniform in space S_{max{h,log d}} + O( log(dH_{max{h,log d}}) + log(L_{max{h,log d}} + d^{O(1)}H_{max{h,log d}})).

We now consider the decomposition of F in homogeneous components, that is, the computation of polynomials F_{0}, …, F_{d} ∈ R with the following properties:

• F = ∑_{k=0}^{d} F_{k}

• For k = 0, …, d, the polynomial F_{k} is zero or homogeneous of degree k.

Lemma 13. Let {C_{n,d,h}}_{n,d,h∈IN} be a family of boolean circuits which evaluates a polynomial F of ZZ[X_{1}, …, X_{n}] of degree d on integers of logarithmic height h. Let L_{h} := L(n, d, h) and ℓ_{h} := ℓ(n, d, h) be the size and depth of C_{n,d,h} respectively, and assume that the family {C_{n,d,h}}_{n,d,h∈IN} is uniform in space S_{h} := S(n, d, h). Let H_{h} := H(n, d, h) be the worst–case logarithmic height of the output of C_{n,d,h}. Then, there exists a family of boolean circuits computing the homogeneous components of F with size L_{max{h,log d}} + d^{O(1)}H_{max{h,log d}} and depth ℓ_{max{h,log d}} + O( log(d) log(dH_{max{h,log d}})), which is uniform in space

S_{max{h,log d}} + O( log (dH_{max{h,log d}}L_{max{h,log d}})).

Proof. Since F (T X_{1}, …, T X_{n}) = ∑_{k=0}^{d} T^{k}F_{k}(X_{1}, …, X_{n}), the problem can be reduced to an interpolation with respect to the variable T.

Therefore, we can apply the Macro expansion lemma with the computation of the polynomial F and interpolation as arithmetic macros. From the bounds of Lemma 12 we deduce the statement of Lemma 13.

Our last problem concerning the manipulation of arithmetic circuits is that of avoiding divisions in arithmetic circuits. Let F_{0}, …, F_{m} be polynomials of R such that F_{0} is nonzero and that F_{0} divides F_{k} in Q [X_{1}, …, X_{n}] for k = 1, …, m.

The problem consists in computing the polynomials \frac{F_{1}}{F_{0}} , …, \frac{F_{m}}{F_{0}} by means of an arithmetic circuit without divisions by nonconstant polynomials of R. For this sake we are going to use the well–known procedure Vermeidung von Divisionen [62] in the version of [45] which allows to control the height of the parameters involved.

Lemma 14. Let {C_{n,m,d,h}}_{n,m,d,h∈IN} be a family of boolean circuits which evaluates polynomials F_{0}, …, F_{m} of ZZ[X_{1}, …, X_{n}] of degree d on integers of logarithmic height h. Let L_{h} := L(n, m, d, h) and ℓ_{h} := ℓ(n, m, d, h) be the size and depth of C_{n,m,d,h} respectively, and assume that the family {C_{n,m,d,h}}_{n,m,d,h∈IN} is uniform in space S_{h} := S(n, m, d, h). Let H_{h} := H(n, m, d, h) be the worst–case logarithmic height of the output of C_{n,m,d,h}. Suppose further that F_{0} is nonzero and that F_{0} divides F_{k} in Q [X_{1}, …, X_{n}] for k = 1, …, m.

Then, there exists a family of boolean circuits which, on input C_{n,m,d,h} and an n–tuple γ ∈ ZZ^{n} of logarithmic height h_{1} such that F_{0}(γ) ≠ 0, computes a nonzero integer θ ∈ ZZ and polynomials P_{1}, …, P_{m} ∈ ZZ[X_{1}, …, X_{n}] such that P_{k} = θ \frac{F_{k}}{F_{0}} holds for k = 1, …, m. This family of boolean circuits has size L_{N} +(mndH_{N})^{O(1)} and depth ℓ_{N} +O( log(d) log(dH_{N})), and is uniform in space S_{N} + O( log(dH_{N}L_{N})), where N := max{h, h_{1}, log d}.

Proof. Let γ = (γ_{1}, …, γ_{n}) ∈ ZZ^{n} be the n–tuple of the statement of Lemma 14. Let ρ := F_{0}(γ) and let G_{0}, …, G_{m} be the polynomials defined by G_{k}(X_{1}, …, X_{n}) = F_{k}(X_{1} + γ_{1}, …, X_{n} + γ_{n}). Let Q := ρ − G_{0} and θ := ρ^{d+1}. Then, it holds true that \frac{θG_{k}}{G_{0}} equals the sum of all the homogeneous components of degree bounded by d of the polynomial Q_{k} := (∑_{i=0}^{d} ρ^{d−i}Q^{i})G_{k} (see [62]).

We observe that the polynomials Q_{1}, …, Q_{m} have degree bounded by d^{2} + d and can be computed by a family of boolean circuits of size L_{max{h,h_{1}}+1} + mn(dH_{max{h,h_{1}}+1})^{O(1)} and depth O(ℓ_{max{h,h_{1}}+1} + log(d) log(dH_{max{h,h_{1}}+1}), which is uniform in space S_{max{h,h_{1}}+1} + O( log(ndH_{max{h,h_{1}}+1})).

Applying the Macro expansion lemma and Lemma 13 we obtain a family of boolean circuits which computes the polynomials \frac{θG_{k}}{G_{0}} for 1 ≤ k ≤ m with size O(L_{N} + mnd^{O(1)}H_{N})) and depth ℓ_{N} + O( log(d) log(dH_{N})) which is uniform in space O(S_{N} + log(nmdH_{N}L_{N})).

In order to conclude, we only have to notice that the identity

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

holds, and that P_{1}, …, P_{m} are polynomials belonging to ZZ[X_{1}, …, X_{n}] which can be computed by a family of boolean circuits which satisfies the statement of the lemma.

3 The resolution of polynomial equation systems: primitive element techniques

Let F_{1}, …, F_{s} be polynomials in Q [X_{1}, …, X_{n}] that define an equidimensional algebraic variety

V := {(x_{1}, …, x_{n}) ∈ C^{n}; F_{1}(x_{1}, …, x_{n}) = ⋯ = F_{s}(x_{1}, …, x_{n}) = 0}

Since we are concerned with geometric elimination, our problems are referred to the variety V rather than to the polynomials F_{1}, …, F_{s} themselves. A common strategy is to reduce the computational problems to the 0–dimensional case (i.e. to the case where V is nonempty and finite), because in this case there exist methods that allow us important reductions of the complexity of the algorithms. In this section we are therefore going to assume that V is zero–dimensional.

As it is well–known, the cardinality δ of V equals the dimension of the finite dimensional Q –vector space

B := Q [X_{1}, …, X_{n}]/\sqrt{(F_{1}, …, F_{s})}

where \sqrt{(F_{1}, …, F_{s})} denotes the radical of the ideal (F_{1}, …, F_{s}) generated by F_{1}, …, F_{s} over Q [X_{1}, …, X_{n}].

A central point is the description of this Q –algebra B by means of some elements which, at the same time, provide a useful “pseudo–parameterization” of V. For this aim, we observe that any linear form U ∈ ZZ[X_{1}, …, X_{n}] that separates the points of the variety V (i.e., U satisfies U(x) ≠ U(y) for any pair of distinct points x, y ∈ V) yields a basis of B in the following way: being u the image of U in B, the set of all the powers {1, u, …, u^{δ−1}} forms such a basis. If this is the case, we call u (and also the linear form U) a primitive element of B (see [24], [43] or [26] for details).

From a primitive element u we obtain a representation of B as the quotient of Q [T] modulo certain principal ideal (the ideal generated by the minimal polynomial of u). More precisely we have the following situation :

Let m_{u} ∈ ZZ[T] be the minimal primitive polynomial of u and observe that m_{u} has degree δ. Then there exists a nonzero integer ρ and polynomials v_{1}, …, v_{n} ∈ ZZ[T] of degree strictly less than δ such that in Q [X_{1}, …, X_{n}] the identity:

(F_{1}, …, F_{s}) = (m_{u}(U), ρX_{1} − v_{1}(U), …, ρX_{n} − v_{n}(U))

holds (by the way the polynomials v_{1}, …, v_{n} are uniquely determined up to scaling). With this notation we have the following identities between Q–algebras:

B = Q [X_{1}, …, X_{n}]/(m_{u}(U), ρX_{1} − v_{1}(U), …, ρX_{n} − v_{n}(U)) ≅ Q [T]/(m_{u}(T)).

The multiplication tensor of B can be easily obtained as follows: let M be the companion matrix of the polynomial m_{u} and let M_{X_{i}} be the matrix of the homothesy induced by X_{i} in B with respect to the basis {1, u, …, u^{δ−1}} for 1 ≤ i ≤ n. Then we have M_{X_{i}} := ρ^{−1}v_{i}(M).

Notice that the curve c(T) := (v_{1}(T), …, v_{n}(T)) contains all the points of V and that the roots of m_{u}(T) are the values of the parameter T which yield the points of this curve which belong to V. This is what we mean by a “pseudo– parameterization” of V.

Properly translated, these notions can be applied to the more general case of equidimensional varieties of positive dimension. First, it is possible to perform a linear change of variables (X_{1}, …, X_{n}) → (Y_{1}, …, Y_{n}) such that the new variables Y_{1}, …, Y_{n−r} are free with respect to V and that the following extension of commutative rings, namely

R := Q [Y_{1}, …, Y_{n−r}] ⟶ Q [Y_{1}, …, Y_{n}]/\sqrt{(F_{1}, …, F_{s})} =: B

is integral. Such a linear change of variables is called a Noether normalization and we shall say that the variables Y_{1}, …, Y_{n} are in Noether position with respect to the variety V (see e.g. [28] for details).

It is clear that the Q–algebra B is reduced. Furthermore, B is a free R–module of finite rank (cf. [32]). In such case, an element u ∈ B is said a primitive element of the ring extension R ⊆ B if it is the image of a linear form and if the degree of the minimal polynomial m_{u} of u equals the rank of B as R–module.

Let K be the quotient field of R and B′ = K ⊗_{R} B. An element u ∈ B is a primitive element of B if and only if, for δ := rank_{R}B = dim_{K}B′, the set {1, u, …, u^{δ−1}} is a basis of the K–vector space B′.

For the aim of this paper it will not be necessary to describe the R–algebra B explicitly. In fact a suitable description of the K–algebra B′ suffices. The K–algebra B′ is characterized by the following items:

• a basis of the K–vector space B′

• for n − r + 1 ≤ i ≤ n, the matrix M_{X_{i}} of the homothesy η_{X_{i}} : B′ → B′ induced by the multiplication by X_{i} in B′ with respect to the given basis (these matrices describe the multiplication tensor of the K-algebra B′ and hence, of the R–algebra B)

These items are what we define as a geometric solution of the variety V (cf. [26]). The basis of B′ is obtained from a suitable primitive element of B.

In this paper, the primitive element u ∈ B will be chosen as the image in B of a generic linear form in the variables X_{n−r+1}, …, X_{n} with coefficients in ZZ, that is, u will be the image of a linear form U = λ_{n−r+1}X_{n−r+1} + ⋯ + λ_{n}X_{n}, with λ_{i} ∈ ZZ for n − r + 1 ≤ i ≤ n. Being T a new indeterminate, the minimal polynomial m_{u}(T) of u as element of the R–algebra B (or equivalently as element of the K–algebra B′) will always be a monic polynomial of Q [X_{1}, …, X_{n−r}, T] (this is a consequence of the basic assumption that the variables X_{1}, …, X_{n} are in Noether position with respect to V). This minimal polynomial will always be chosen as an element of the ring ZZ[X_{1}, …, X_{n−r}, T] = R[T].

Finally, since by assumption {1, u, …, u^{δ−1}} is a basis of the K–vector space B′, there exist for n − r + 1 ≤ i ≤ n polynomials v_{i}^{(u)} ∈ R[T] and nonzero elements ρ_{i}^{(u)} ∈ R such that ρ_{i}^{(u)}X_{i} − v_{i}^{(u)}(U) belongs to the extension ideal \sqrt{F_{1}, …, F_{s}}^{(K)} of \sqrt{F_{1}, …, F_{s}} in K[X_{n−r+1}, …, X_{n}]. In particular, we have the following identity between ideals of K[X_{n−r+1}, …, X_{n}]:

\sqrt{(F_{1}, …, F_{s})}^{(K)} = (m_{u}(U), ρ_{1}^{(u)}X_{r+1} − v_{r+1}^{(u)}(U), …, ρ_{n}^{(u)}X_{n} − v_{n}^{(u)}(U))

Furthermore, if M is the companion matrix of the homothesy η_{u} with respect to the basis {1, u, …, u^{D−1}}, the matrices M_{X_{n−r+1}}, …, M_{X_{n}} which characterize the multiplication tensor of the K–algebra B′ (or equivalently of the R–algebra B) are obtained from the identity:

ρ_{i}^{(u)} · M_{X_{i}} = v_{i}^{(u)}(M)

for n − r + 1 ≤ i ≤ n.

3.1 The construction of a primitive element

We develop in this subsection the tools we need in the construction of a primitive element u (and the pseudo–parameterization associated to it). This is done following the ideas of [45], with the additional aim to prove the uniformity of the underlying algorithms.

First, we are going to treat the particular case of a variety defined by two polynomials in two separated variables.

Lemma 15. Let {C_{m,δ_{1},δ_{2},h}}_{m,δ_{1},δ_{2},h∈IN} be a family of boolean circuits which evaluates polynomials f_{0}, …, f_{δ_{1}}, g_{0}, …, g_{δ_{2}} of ZZ[Y_{1}, …, Y_{m}] on integers of logarithmic height h. Let L_{h} := L(m, δ_{1}, δ_{2}, h) and ℓ_{h} := ℓ(m, δ_{1}, δ_{2}, h) be the size and depth of C_{m,δ_{1},δ_{2},h}, and assume that the family {C_{m,δ_{1},δ_{2},h}}_{m,δ_{1},δ_{2},h∈IN} is uniform in space S_{h} := S(m, δ_{1}, δ_{2}, h). Let H_{h} := H(m, δ_{1}, δ_{2}, h) be the worst– case logarithmic height of the output of C_{m,δ_{1},δ_{2},h}.

Let R := ZZ[Y_{1}, …, Y_{m}], K := Q (Y_{1}, …, Y_{m}) and let \overline{K} be the algebraic closure of K. Let F (X) := f_{0} + ⋯ + f_{δ_{1}}X^{δ_{1}} and G(Y) := g_{0} + ⋯ + g_{δ_{2}}Y^{δ_{2}} be polynomials which are squarefree in K[X, Y], let I := (F (X), G(Y)) be the ideal generated by F (X) and G(Y) in K[X, Y] and let W ⊂ \overline{K}^{2} be the zero– dimensional variety defined by F (X) and G(Y). Let U := αX + Y be a linear form that represents a primitive element of the K–algebra B := K[X, Y]/I and let δ := δ_{1} · δ_{2}.

Then, there exists a family of boolean circuits with size L_{h} +(δh_{1}H_{h})^{O(1)} and depth ℓ_{h}+O( log(δ) log(δh_{1}H_{h})), which is uniform in space S_{h}+O( log(δH_{h}L_{h})) such that, given an integer α of logarithmic height h_{1} such that αX + Y is a primitive element of B, computes on integers of logarithmic height h the coefficients in ZZ[Y_{1}, …, Y_{m}] of polynomials q, v_{1}, v_{2} ∈ ZZ[Y_{1}, …, Y_{m}][T] and an element ρ ∈ ZZ[Y_{1}, …, Y_{m}] with the following properties:

• deg(q) = δ and max{deg(v_{1}), deg(v_{2})} < δ.

• (q(U), ρX − v_{1}(U), ρY − v_{2}(U)) ⊆ I Proof. We follow the ideas of [45, Lemma 26]. It is clear that B is a K–vector space of dimension δ and that the image in B of the set

B := {X^{i}Y^{j}/0 ≤ i < δ_{1}, 0 ≤ j < δ_{2}}

defines a basis as K–vector space of B.

For the sake of definiteness let us fix the lexicographical order on the set B. Then the matrices M_{X}, M_{Y} ∈ K^{δ×δ} of the homothesies η_{X} and η_{Y} of the K–algebra B with respect to the basis B can be obtained directly from the coefficients of F and G. Let u be the image of the linear form U in the K–algebra B and denote by M_{u} the matrix of the homothesy η_{u} induced by multiplication by u in B with respect to the basis B. Observe that the identity M_{u} = α · M_{X} + M_{Y} holds. Notice that, being a, b ∈ R the leading coefficients of F and G respectively, the matrix abM_{u} has all its entries in R.

By the Cayley–Hamilton theorem, the characteristic polynomial χ ∈ k[T] of the matrix M_{u} annihilates u over B. Since deg(χ) = δ holds, we have that χ is the minimal polynomial of u over B. Define q(T) := χ_{abM_{u}}(abT) and observe that (ab)^{δ}χ_{M_{u}}(T) = χ_{abM_{u}}(abT) = q(T) holds. Thus we have q(T) ∈ R[T] and in particular q(U) ∈ I. Moreover the coefficients of q can be computed by a division–free arithmetic circuit in R of size δ^{O(1)} and nonscalar depth O(log δ).

In order to find the element ρ ∈ R and the polynomials v_{1}, v_{2} ∈ R[T] of the statement of the lemma, we observe that

B′ := {1, u, …, u^{δ−1}}

is a K–vector space basis of B, and that there exists a nonsingular matrix M ∈ K^{δ×δ} such that modulo I the following congruence relation holds:

( 1 ; U ; U^{2} ; ⋮ ; U^{δ−1} ) ≡ M · ( 1 ; X ; Y ; ⋮ ; X^{deg(F)−1}Y^{deg(G)−1} ) .

Multiplying both sides of this congruence relation by the adjoint matrix Adj(M) of M, we conclude:

Adj(M) · ( 1 ; U ; U^{2} ; ⋮ ; U^{δ−1} ) ≡ det(M) · ( 1 ; X ; Y ; ⋮ ; X^{deg(F)−1}Y^{deg(G)−1} )

Since the i–th column of the matrix M can be obtained as the first column of the matrix (M_{u})^{i} for i = 0, …, δ − 1, we see that (ab)^{δ}M has all its entries in R. Thus (ab)^{δ^{2}}Adj(M) = (ab)^{δ}Adj((ab)^{δ}M) has its entries in R and (ab)^{δ^{2}} ·det(M) belongs to R. Let ρ := (ab)^{δ^{2}−δ} · det(M) and let v_{1}(T), v_{2}(T) be the polynomials of R[T] of degree less than δ whose coefficient vectors are obtained from the second and third row of (ab)^{δ}Adj((ab)^{δ}M) respectively. Then the degree of v_{1}, v_{2} is strictly less than δ and modulo the ideal I we have the following congruences:

\begin{matrix}ρ · X ≡ v_{1}(U) \\ ρ · Y ≡ v_{2}(U). \end{matrix}

We now analyze the underlying algorithm, in order to prove that it can be performed by a family of boolean circuits whose size, depth and space– uniformity satisfy the statement of the lemma. For this purpose we apply the Macro expansion lemma using the polynomial maps defined by the polynomials f_{0}, …, f_{δ_{1}}, g_{0}, …, g_{δ_{2}}, the integer product, the matrix product of (δ × δ)– matrices, the coefficients of the characteristic polynomial of a (δ × δ)–matrix and the adjoint matrix of a (δ × δ)–matrix. The algorithm described above computes the polynomials f_{0}, …, f_{δ_{1}}, g_{0}, …, g_{δ_{2}} and computes the matrices abM_{X}, abM_{Y} and abM_{u}. We observe that the matrices aM_{X} and aM_{Y} can be obtained by a simple mapping from the polynomials f_{0}, …, f_{δ_{1}}, g_{0}, …, g_{δ_{2}} using space O(log d). We also observe that the entries of the matrices abM_{X} and abM_{Y} are polynomials of ZZ[Y_{1}, …, Y_{m}] with worst–case logarithmic height O(H_{h}) on integers of logarithmic height h.

Then we compute the matrix abM_{u} and the coefficients of its characteristic polynomial using Lemma 5. An inner product between the vector formed by the coefficients of this characteristic polynomial and the vector (1, ab, (ab)^{2}, …, (ab)^{δ}) yields the coefficients of the polynomial χ_{abM_{u}}(abT), which have worst–case logarithmic height O(δh_{1}H_{h}) on integers of logarithmic height h.

Then we obtain the columns of the matrix (ab)^{δ}M by computing the first column of the matrices (ab)^{δ−1}abM_{u}, (ab)^{δ−2}(abM_{u})^{2}, …, (abM_{u})^{δ}. Finally we compute ρ = det((ab)^{δ}M) and the second and third row of the matrix (ab)^{δ} Adj((ab)^{δ}M). Notice that M has logarithmic height O(δh_{1}H_{h}) on integers of logarithmic height h. Therefore, combining the Macro expansion lemma with Lemmata 3, 4, 5 and 7 we obtain a family of boolean circuits satisfying the statement of the lemma.

Now we are going to reduce the general case of an equidimensional variety to the case of two polynomials in two separated variables. We assume now that we have a procedure that determines, given a linear form U, a polynomial p that annihilates U on the given zero–dimensional variety V under consideration (in the next section we are going treat the problem how to find such a polynomial p).

For the rest of this subsection we will use the following notation: R will denote a polynomial ring ZZ[Y_{1}, …, Y_{m}] with quotient field K and \overline{K} will denote the algebraic closure of K. Likewise, we will consider polynomials F_{1}, …, F_{s} ∈ R[X_{1}, …, X_{n}] that define a zero–dimensional variety V over \overline{K}^{n} of cardinality δ and generate a radical ideal I in K[X_{1}, …, X_{n}].

Let T_{1}, …, T_{n} be new indeterminates. We shall denote by Z_{j} the linear form Z_{j} := T_{1}X_{1} + ⋯ + T_{j−1}X_{j−1} + T_{j+1}X_{j+1} + ⋯ + T_{n}X_{n} for j = 1, …, n and by I_{T} the ideal generated by F_{1}, …, F_{s} in \overline{K}(T_{1}, …, T_{n})[X_{1}, …, X_{n}]. We shall use the following result:

Lemma 16 (([45]; Lemma 25)). Let be given the following items:

• for every j = 1, …, n, a polynomial G_{j} ∈ R[T], squarefree in K[T], of degree deg(G_{j}) ≤ δ such that G_{j}(X_{j}) belongs to I.

• for every j = 1, …, n, a polynomial H_{j} ∈ R[T_{1}, …, T_{n}][T], squarefree in K(T_{1}, …, T_{n})[T] and monic in T except for factors in R, of degree deg_{T} (H_{j}) ≤ δ, such that H_{j}(Z_{j}) belongs to I_{T}

Then, there exists an arithmetic circuit β of size O(nδ^{O(1)}) and nonscalar depth O( log(nδ)) that computes a polynomial Q ∈ R[T_{1}, …, T_{n}] which verifies the following property: for every n-tuple (λ_{1}, …, λ_{n}) ∈ R^{n} such that F (λ_{1}, …, λ_{n}) ≠ 0 holds, the linear form U := λ_{1}X_{1} + ⋯, λ_{n}X_{n} is a primitive element of V.

From Lemma 16 and the Schwartz–Zippel test we obtain the coefficients (λ_{1}, …, λ_{n}) ∈ ZZ^{n} of a linear form which constitutes a primitive element for the variety V defined by the polynomials F_{1}, …, F_{s}. In the following lemma we describe how we obtain a geometric solution of the equidimensional variety V which is defined by the polynomials F_{1}, …, F_{s}.

Lemma 17. Let notations and assumptions be as in Lemma 16. Let {C_{m,n,δ,h}}_{m,n,δ,h∈IN} be a family of boolean circuits which evaluates the coefficients in R[T_{1}, …, T_{n}] of the polynomials G_{1}, …, G_{n}, H_{1}, …, H_{n} on integers of logarithmic height h. Let L_{h} := L(m, n, δ, h) and ℓ_{h} := ℓ(m, n, δ, h) be the size and depth of C_{m,n,δ,h} respectively, and assume that the family {C_{m,n,δ,h}}_{m,n,δ,h∈IN} is uniform in space S_{h} := S(m, n, δ, h). Let H_{h} := H(m, n, δ, h) be the worst–case logarithmic height of the output of C_{m,n,δ,h}.

Assume further that we are given an n–tuple (λ_{1}, …, λ_{n}) of ZZ^{n} of logarithmic height h_{1} such that the linear form U := λ_{1}X_{1} + ⋯ + λ_{n}X_{n} is a primitive element of the algebraic variety V and that the variables X_{1}, …, X_{n} are in Noether position. Then there exists a family of boolean circuits with size L_{max{h,h_{1}}} + (nδh_{1}H_{max{h,h_{1}}})^{O(1)} and depth ℓ_{max{h,h_{1}}} + O( log(δ) log(nδh_{1}H_{max{h,h_{1}}})), which is uniform in space S_{max{h,h_{1}}} +O( log(nδh_{1}H_{max{h,h_{1}}}L_{max{h,h_{1}}})) such that, given the integers λ_{1}, …, λ_{n} computes on integers of logarithmic height h elements ρ_{1}, …, ρ_{n} ∈ R and the coefficients in R of polynomials q, v_{1}, …, v_{n} ∈ R[T] with the following properties:

• deg_{T} (q) = δ and q(U) ∈ I

• for every i = 1, …, n we have deg_{T} (v_{i}) < δ and ρ_{i}X_{i} − v_{i}(U) ∈ I

Proof. Following [45, Proposition 27], let Z_{j}(λ) := λ_{1}X_{1} + ⋯ + λ̂_{j}X_{j} + ⋯ + λ_{n}X_{n}. By replacing the variables (T_{1}, …, T_{n}) by (λ_{1}, …, λ_{n}) in the polynomials H_{1}, …, H_{n} we obtain polynomials h_{1}(T) := H_{1}(λ_{1}, …, λ_{n}, T), …, h_{n}(T) := H_{n}(λ_{1}, …, λ_{n}, T) in R[T] such that h_{j}(Z_{j}(λ)) ∈ I holds. Observe that the coefficients with respect to T of the polynomials h_{1}, …, h_{n} can be computed by a family of boolean circuits of size L_{max{h,h_{1}}} and depth ℓ_{max{h,h_{1}}} which is uniform in space S_{max{h,h_{1}}}.

Since the linear form U represents a primitive element of V, we see that U separates the points of the set \{G_{j}(X_{j}) = 0, h_{j}(Z_{j}(λ)) = 0\} ⊂ \overline{K}^{2}. In order to apply Lemma 15 we compute a square–free representation h̃_{j}(T) of h_{j}(T) for 1 ≤ j ≤ n. Applying Lemma 11 we see that the polynomials h̃_{1}, …, h̃_{n} can be computed by a family of boolean circuits with size L_{max{h,h_{1}}}+nδ^{O(1)}H_{max{h,h_{1}}} and depth O(ℓ_{max{h,h_{1}}} + log(δ) log(δH_{max{h,h_{1}}})) which is uniform in space S_{max{h,h_{1}}} + O( log(nδH_{max{h,h_{1}}}L_{max{h,h_{1}}})).

Applying for each 1 ≤ j ≤ n Lemma 15 to the K–algebra k[X_{j}, Z_{j}(λ)]/(G_{j}(X_{j}), h̃_{j}(Z_{j}(λ))) with U = λ_{j}X_{j} +Z_{j}(λ) as primitive element, we obtain elements ρ_{j} ∈ R and polynomials v_{j} ∈ R[T] that verify the condition

ρ_{j}X_{j} − v_{j}(U) ∈ (G_{j}(X_{j}), h_{j}(Z_{j}(λ))) ⊂ I

Applying the Macro expansion lemma and Lemma 15 we conclude that all these computations can be performed by a family of boolean circuits with size L_{max{h,h_{1}}} + nh_{1}(δH_{max{h,h_{1}}})^{O(1)} and depth ℓ_{max{h,h_{1}}} + O( log(δ) log(δh_{1}H_{max{h,h_{1}}})), which is uniform in space S_{max{h,h_{1}}} + O( log(nδh_{1}H_{max{h,h_{1}}}L_{max{h,h_{1}}})).

3.2 The computation of the isolated points of a variety

Let R := ZZ[Y_{1}, …, Y_{m}] be a polynomial ring, let K := Q (Y_{1}, …, Y_{m}) be the quotient field of R and let \overline{K} be the algebraic closure of K. Let be given polynomials F_{1}, …, F_{s} in R[X_{1}, …, X_{n}] and let V ⊂ \overline{K}^{n} be the algebraic variety defined as the set of common zeroes of these polynomials.

In this subsection we are going to compute the isolated points of the variety V. This is a necessary preliminary step for the determination of the multiplication tensor of a reduced complete intersection and allows also to compute the dimension of the variety V.

As we have seen in the previous subsection, we need to develop a procedure which computes, for a given linear form U ∈ R[X_{1}, …, X_{n}], a polynomial p ∈ R[T] that annihilates U on the isolated points of V.

First we deal with the case where the isolated points of V are locally complete intersection.

Lemma 18. Let {C_{m,n,d,h}}_{m,n,d,h∈IN} be a family of boolean circuits which evaluates the coefficients in R of polynomials F_{1}, …, F_{n} of R[X_{1}, …, X_{n}] of degree d and the coefficients λ_{1}, …, λ_{n} ∈ R of a linear form U := λ_{1}X_{1} + ⋯ + λ_{n}X_{n} on integers of logarithmic height bounded by h. Assume further that these coefficients have degree bounded by d. Let L_{h} := L(m, n, d, h) and ℓ_{h} := ℓ(m, n, d, h) be the size and depth of C_{m,n,d,h} respectively, and assume that the family {C_{m,n,d,h}}_{m,n,d,h∈IN} is uniform in space S_{h} := S(m, n, d, h).

Let H_{h} := H(m, n, d, h) be the worst–case logarithmic height of the output of C_{m,n,d,h}.

Let (F_{1}, …, F_{n}) denote the ideal generated by F_{1}, …, F_{n} over R[X_{1}, …, X_{n}] and let V be the algebraic variety defined by F_{1}, …, F_{n} in \overline{K}^{n}. Then, there exists a family of boolean circuits which, given random integers γ_{ε}, γ_{0}, …, γ_{n}, γ_{T} of logarithmic height N := O(n log(nd)), computes the coefficients of a polynomial p ∈ R[T] such that p(U) vanishes on the isolated points of the variety V. This family of boolean circuits has size L_{max{N,h}}+((nd)^{n}H_{max{N,h}})^{O(1)}, depth O(ℓ_{max{N,h}}+n^{2} log(nd) log(ndH_{max{N,h}})) and is uniform in space S_{max{N,h}}+ O(n log(ndH_{max{N,h}}L_{max{N,h}}).

Proof. Following e.g. [28], we produce a homotopic deformation of the given equation system in order to reduce the problem to the zero–dimensional projective case. For this purpose, we introduce new indeterminates X_{0} and ε, and consider for 1 ≤ i ≤ n the polynomials

G_{i} := X_{0}^{h}F_{i} + εX_{i}^{1+deg(F_{i})}

(here ^{h}F_{i} denotes the homogenization of F_{i} with respect to the homogenization variable X_{0}). As elements of R [ε][X_{0}, …, X_{n}], the polynomials G_{1}, …, G_{n} are homogeneous and define a zero–dimensional subvariety of IP^{n}(\overline{K (ε)}) [28, Lemme 3.3.3]. The dense representation of G_{1}, …, G_{n} is obtained directly from that of F_{1}, …, F_{n}.

We apply now arguments on the regularity of the Hilbert function of the graduated ring

A := \overline{K (ε)}[X_{0}, …, X_{n}]/(G_{1}, …, G_{n}) = A_{0} ⊕ A_{1} ⊕ ⋯ ⊕ A_{j} ⊕ ⋯

Let us notice the following facts (see [51] or [9]):

• Let N := nd. Then A_{N} and A_{N+1} are finite dimensional \overline{K (ε)}–vector spaces of the same dimension, say D, with D ≤ (d + 1)^{n}.

• Since the ideal (G_{1}, …, G_{n}) does not have any zero in the hyperplane X_{0} = 0, the homothesy η_{X_{0}} : A_{N} ⟶ A_{N+1} is an isomorphism.

We consider the endomorphism:

ϕ := η_{X_{0}}^{−1}η_{u} : A_{N} ⟶ A_{N}

where u is the image of U in A. By the theorem of Cayley–Hamilton, the characteristic polynomial P (T) of ϕ verifies P (ϕ) ≡ 0, and hence so does η_{X_{0}}^{D}P (ϕ). Since

X_{0} is not a zero divisor of A, the nonzero polynomial P̃(X_{0}, T) := X_{0}^{D}P (\frac{T}{X_{0}} ) =

det(X_{0}M_{ϕ}−T ·Id) has the property that P̃(X_{0}, U) belongs to the ideal generated by G_{1}, …, G_{n} in \overline{K (ε)}[X_{0}, …, X_{n}] (here M_{ϕ} denotes the matrix of the linear endomorphism ϕ with respect to a suitable \overline{K (ε)}–vector space basis of A_{N}).

In order to compute the polynomial P̃(X_{0}, T), it is necessary to compute first the matrices M_{X_{0}} and M_{U} of the homothesies η_{X_{0}} and η_{U} in some suitable basis B and B′ of A_{N} and A_{N+1} respectively. For this purpose we shall follow [45].

Let F_{s} := {m_{1}, …, m_{r_{s}}} be the set of all monomials of degree s in the vari-

ables X_{0}, …, X_{n} (recall that r_{s} = ( \begin{matrix}s + n \\ n \end{matrix} ) holds). Multiplying all the mono-

mials of degree N − (1 + deg(F_{i})) by the polynomial G_{i} for 1 ≤ i ≤ n, we obtain the matrix Q_{1} ∈ R[ε]^{r_{n−(d+1)}×r_{N}} of the relations of the monomials in F_{N} modulo I_{N}. Computing a square submatrix Q̃_{1} of Q_{1} of maximal rank we obtain a monomial basis of A_{N}: we consider the subset B := {e_{1}, …, e_{D}} of F_{N} in which the monomials e_{j} correspond to the columns of Q_{1} not chosen to form Q̃_{1}.

Similarly, we compute a square submatrix of maximal rank Q̃_{2} of the matrix Q_{2} of relations in A_{N+1}. Then we extract a monomial basis B′ := {e′_{1}, …, e′_{D}} ⊆ F_{N+1} of A_{N+1}, and its remainder set {v′_{1}, …, v′_{t}} := F_{N+1} \ B′. Moreover, we obtain an element α := det(Q̃_{2}) ∈ R and a matrix B ∈ R^{t×D}, given by the remaining columns of Adj(Q̃_{2})Q_{2}, such that

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

holds.

Now we are able to compute for 1 ≤ i ≤ n matrices M_{αX_{i}} = αM_{X_{i}}, where M_{αX_{i}} and M_{X_{i}} represent the matrices of the \overline{K (ε)}–algebra morphisms η_{αX_{i}} : A_{N} → A_{N+1} and η_{X_{i}} : A_{N} → A_{N+1} defined by multiplication of the elements of A_{N} by αX_{i} and X_{i} respectively with respect to the basis B and B′. For any e_{i} ∈ B, the element αX_{i}e_{i} ∈ A_{N+1} is either a monomial of the form αe′_{j} or a monomial of the form αv′_{j}. In the first case the corresponding column of M_{αX_{i}} is a vector with all its coordinates zero except for its j–th column where α occurs. In the second case this column is simply the j–th row of the matrix B. In this way we compute easily the matrices M_{αX_{0}} and M_{αu} = ∑_{i=0}^{n} λ_{i}M_{αX_{i}}.

In order to avoid divisions in the computation of the polynomial P̃(X_{0}, T), we compute the following multiple Δ(ε, X_{0}, T) of it in R [ε][X_{0}, T]:

Δ(ε, X_{0}, T) = ∑_{j=1}^{D} p_{j}(ε)T^{j}X_{0}^{D−j} := det(M_{λX_{0}})^{D}P̃(X_{0}, T) =

= α^{D}det(M_{αX_{0}})^{D}P̃(X_{0}, T) = det(X_{0}Adj(M_{αX_{0}})M_{αu} − det(M_{αX_{0}})T · Id)

Dividing the polynomial Δ(ε, X_{0}, T) by the greatest possible power of ε, we obtain a new polynomial Δ_{1}(ε, X_{0}, T) such that p(T) := Δ_{1}(0, 1, T) is the polynomial we are looking for [28, Proposition 3.3.4].

We observe that the whole procedure manipulates matrices whose entries are polynomials in the variables Y_{1}, …, Y_{m}, ε of degree bounded by (nd)^{O(n)}. This follows from the hypothesis on the degree of the coefficients of the polynomials F_{1}, …, F_{n}, U and the size of the matrices involved. Therefore, from Schwartz–Zippel test we deduce that there exist integer parameters γ, γ_{1}, …, γ_{n} of logarithmic height O(n log(nd)) such that, applying the strategy of Lemma 8 to compute submatrices of maximal rank of the matrices P (γ_{ε}, γ_{1}, …, γ_{n}) and Q(γ_{ε}, γ_{1}, …, γ_{n}) (here P (γ_{ε}, γ_{1}, …, γ_{n}) and Q(γ_{ε}, γ_{1}, …, γ_{n}) denote the integer matrices obtained by the evaluation of the entries of the matrices P and Q in ε = γ_{ε}, Y_{1} = γ_{1}, …, Y_{m} = γ_{m}) also yields submatrices P̃, Q̃ of maximal rank of the matrices P, Q. We assume that our input parameters γ_{ε}, γ_{1}, …, γ_{n} satisfy this property.

We now analyze the algorithm to prove that it can be performed by a family of boolean circuits whose size, depth and space–uniformity satisfy the statement of the lemma. Notice that the dense representation of the polynomials G_{1}, …, G_{n} can be computed by family of boolean circuits of size L_{h} + O(d^{n}H_{h}) and depth O(ℓ_{h} + n log(dH_{h})), which is uniform in space S_{h} + n log(dH_{h}).

The mapping computing the entries p_{ij}, q_{ij} of the matrices P, Q from the coefficients of the polynomials G_{1}, …, G_{n} can be easily described in space O(n log(nd)), because it only requires to manipulate the monomials in n + 1 variables of degree at most r_{N+1} = nd + 1, which form a \overline{K (ε)}–vector space of dimension (nd)^{O(n)}. We evaluate the entries of the matrices P, Q in ε = γ_{ε}, Y_{1} = γ_{1}, …, Y_{m} = γ_{m} and determine which rows and columns of P and Q are chosen to form the submatrices P̃ and Q̃ of maximal rank. For this purpose we apply the ideas of Lemma 8 to the matrices P (γ_{ε}, γ_{1}, …, γ_{n}) and Q(γ_{ε}, γ_{1}, …, γ_{n}). The family of boolean circuits which performs these operations has size L_{N} + ((nd)^{n}H_{N})^{O(1)}, depth O(ℓ_{N} + n^{2} log(nd) log(ndH_{N})) and is uniform in space S_{N} + O(n log(ndH_{N}L_{N})).

Once we have computed the rows and columns of P and Q chosen to form the submatrices P̃ and Q̃, we obtain the matrices P̃ and Q̃. We now apply the Macro expansion lemma using the polynomial maps defined by the entries of the matrices P̃ and Q̃ and the computation of the determinant, adjoint matrix and matrix product of ((d + 1)^{n} × (d + 1)^{n})–matrices to prove that there exists a family of boolean circuits computing the matrix B with size L_{max{N,h}} +

((nd)^{n}H_{max{N,h}})^{O(1)}, depth O(ℓ_{max{N,h}} + n^{2} log(nd) log(ndH_{max{N,h}})) and is uniform in space S_{max{N,h}} + O(n log(ndH_{max{N,h}}L_{max{N,h}})). We observe that the entries of the matrix B have worst–case logarithmic height (d^{n}H_{h})^{O(1)} on integers of logarithmic height h.

The mapping which computes the matrices M_{αX_{0}}, …, M_{αX_{n}} from the entries of the matrix B can be easily described in space (nd)^{O(n)}. Applying again the Macro expansion lemma using this mapping and the computation of adjoint matrix and determinant as polynomial maps we obtain a family of boolean circuits computing the polynomial Λ(ε, X_{0}, T) with size L_{max{N,h}}+

+((nd)^{n}H_{max{N,h}})^{O(1)}, depth O(ℓ_{max{N,h}}+n^{2} log(nd) log(ndH_{max{N,h}})) and is uniform in space S_{max{N,h}} + O(n log(ndH_{max{N,h}}L_{max{N,h}})). The coefficients of the polynomial Λ(ε, X_{0}, T) have worst–case logarithmic height (d^{n}H_{h})^{O(1)} on integers of logarithmic height h.

In order to determine the greatest power of ε which divides the polynomial Λ(ε, X_{0}, T) we observe that Λ(ε, X_{0}, T) is a polynomial of degree at most (nd)^{O(n)} and hence its coefficients with respect to ε are polynomials of ZZ[X_{0}, Y_{1}, …, Y_{m}, T] of degree at most (nd)^{O(n)}. Therefore applying Schwartz–Zippel test we see that there exist integers (γ_{0}, γ_{1}, …, γ_{n}, γ_{T}) of logarithmic height O(n log(nd)) such that any coefficient p of the dense representation of Λ(ε, X_{0}, T) with respect to ε is the polynomial zero if and only the evaluation p(γ_{0}, γ_{1}, …, γ_{n}, γ_{T}) of p in X_{0} = γ_{0}, Y_{1} = γ_{1}, …, Y_{n} = γ_{n}, T = γ_{T} equals zero. We assume that the input parameters γ_{0}, γ_{1}, …, γ_{n}, γ_{T} satisfy this property.

Then we interpolate the polynomial with Λ(ε, X_{0}, T) respect to ε and evaluate the coefficients in X_{0} = γ_{0}, Y_{1} = γ_{1}, …, Y_{n} = γ_{n}, T = γ_{T} to determine which is the least nonzero coefficient. From the bounds of Lemma 12 we deduce the complexity bounds of the statement of Lemma 18.

We remark that the algorithm of Lemma 18 requires the manipulation of matrices of size (nd)^{O(n)} × (nd)^{O(n)}, instead of the d^{O(n^{2})} × d^{O(n^{2})}–matrices considered in [53].

Now we are in conditions to treat the general problem of the determination of the isolated points of a given algebraic variety.

Proposition 1. Let {C_{m,n,s,d,h}}_{m,n,s,d,h∈IN} be a family of boolean circuits which evaluates the coefficients in R of polynomials F_{1}, …, F_{s} of R[X_{1}, …, X_{n}] of degree d on integers of logarithmic height bounded by h. Assume further that these coefficients have degree bounded d. Let L_{h} := L(m, n, s, d, h) and ℓ_{h} := ℓ(m, n, s, d, h) be the size and depth of C_{m,n,s,d,h} respectively, and assume that the family {C_{m,n,s,d,h}}_{m,n,s,d,h∈IN} is uniform in space S_{h} := S(m, n, s, d, h). Let H_{h} := H(m, n, s, d, h) be the worst–case logarithmic height of the output of C_{m,n,s,d,h}.

Let V ⊂ \overline{K}^{n} be the algebraic variety defined by the polynomials F_{1}, …, F_{s}.

Then, there exists a family of boolean circuits which, given random integers γ_{ε}, γ_{0}, …, γ_{n}, γ_{T} , γ̃_{1}, …, γ̃_{n}, λ_{1}, …, λ_{n} of logarithmic height N := O(n log(nsd)), computes the coefficients of a geometric solution of a zero–dimensional variety containing the isolated points of V. This family of boolean circuit has size L_{max{N,h}} + (s(nd)^{n}H_{max{N,h}})^{O(1)}, depth O(ℓ_{max{N,h}} + n^{2} log(nd) log(nsd H_{max{N,h}})) and is uniform in space S_{max{N,h}} + O(n log(nsdH_{max{N,h}} L_{max{N,h}})).

Proof. First of all we replace the variety V by another variety containing between its isolated points all the isolated points of V and such that this new variety is given by n equations. In this sense, for a given n–tuple γ̃ := (γ̃_{1}, …, γ̃_{n}) ∈ ZZ^{n} we define for i = 1, …, n the following n polynomials:

Fγ̃_{i} := F_{1} + γ̃_{i}F_{2} + ⋯ + γ̃_{i}^{s−1}F_{s}

From [28, Lemme 3.4.1] it follows that there exists a polynomial Q(T_{1}, …, T_{n}) of degree bounded by sd^{n} such that for any n–tuple γ̃ ∈ ZZ^{n} with Q(γ̃_{1}, …, γ̃_{n}) ≠ 0 the variety V^{(γ̃)} defined by Fγ̃_{1}, …, Fγ̃_{n} contains all the isolated points of V as isolated points. Hence, any polynomial P ∈ R[T] that annihilates a given linear form U over the isolated points of V^{(γ̃)} annihilates U over the isolated points of V.

Therefore applying Schwartz–Zippel test we deduce that there exists an integer n–tuple (γ̃_{1}, …, γ̃_{n}) of logarithmic height bounded by O(n log(sd)) which does not annihilate Q. We assume that our input parameters γ̃_{1}, …, γ̃_{n} satisfy this property.

In order to compute the polynomials Fγ̃_{1}, …, Fγ̃_{n} we first compute the numbers γ̃_{i}^{j} for 1 ≤ i ≤ n and 1 ≤ j ≤ s. The coefficient corresponding to a monomial, say m, of Fγ̃_{i} is computed as the inner product of the vector of the coefficients of F_{1}, …, F_{s} corresponding to m with the vector (1, γ̃_{1}, …, γ̃_{1}^{s−1}). We observe that the resulting coefficients have logarithmic height bounded by H_{h} + O(sn log(sd)).

From Lemma 16 and the Schwartz–Zippel test we see that there exist integers λ_{1}, …, λ_{n} of logarithmic height O(n log(nd)) such that the linear form U := λ_{1}X_{1} + ⋯ + λ_{n}X_{n} separates the isolated points of V. We assume that our input parameters λ_{1}, …, λ_{n} satisfy this property.

Then we apply Lemma 18 in order to produce polynomials that annihilate the linear forms X_{1}, …, X_{n}, Z_{j} := λ_{1}X_{1}+⋯+λ̂_{j}X_{j}+⋯+λ_{n}X_{n} for j = 1, …, n and Z := λ_{1}X_{1} + ⋯ + λ_{n}X_{n} on the isolated points of V. Let us observe that the coefficients of the computed polynomials have logarithmic height bounded by (sd^{n}H_{h})^{O(1)}. Finally we apply Lemma 17 in order to produce a geometric solution of the isolated points of V.

Let us analyze the size, depth and space–uniformity of the algorithm we have just described. For this purpose we apply the Macro expansion lemma using the polynomial maps defined by the coefficients of the polynomials Fγ̃_{1}, …, Fγ̃_{n} and the maps given by the application of Lemma 18 and Lemma 17. From the bounds of Lemmata 18 and 17 we deduce that the whole procedure can be performed by means of a family of boolean circuits with size L_{max{N,h}} +

(s(nd)^{n}H_{max{N,h}})^{O(1)} and depth O(ℓ_{max{N,h}}+n^{2} log(nd) log(nsdH_{max{N,h}})) which is uniform in space S_{max{N,h}} + O(n log(nsdH_{max{N,h}}L_{max{N,h}}).

4 The division modulo a reduced complete intersection ideal

In this section, following the development made in [45], we treat a crucial problem for the algorithmic division modulo a given polynomial ideal: the computation of the quotient of two polynomials modulo a radical complete intersection ideal.

This quotient will be the result of the action of a matrix whose entries can be computed in suitable nonscalar depth. The computation of this matrix will be essential in order to obtain the complexity bounds we are looking for.

The main ingredient for our division theorem is a duality theory based on the existence of traces in Gorenstein algebras, whose basic facts we explain below. For proofs we refer to [48], Appendices E and F.

4.1 General trace theory

Let R be a polynomial ring ZZ[T_{1}, …, T_{m}], let K be its quotient field and let R[X_{1}, …, X_{n}] be the polynomial ring in n variables with coefficients in R. Let F_{1}, …, F_{n} be a regular sequence of polynomials in R[X_{1}, …, X_{n}] of degree at most d in the variables X_{1}, …, X_{n}, generating a radical ideal (F_{1}, …, F_{n}).

We consider the R–algebra B given as the quotient of R[X_{1}, …, X_{n}] for this ideal:

B := R[X_{1}, …, X_{n}]/(F_{1}, …, F_{n})

We assume that the ring extension R → B represents a Noether normalization of the variety V (F_{1}, …, F_{n}) defined by the polynomials F_{1}, …, F_{n} in a suitable affine space. Thus, B is a free R–module of rank bounded by the degree of the variety V (F_{1}, …, F_{n}). Furthermore, the R–algebra B is Gorenstein and the following statements are based on this fact.

We consider B^{∗} := Hom_{R}(B, R) with the B–module structure defined by means of the scalar product

B × B^{∗} ⟶ B^{∗}

that associates to each (b, τ) in B × B^{∗} the R–linear morphism b · τ : B ⟶ R defined by (b · τ)(x) := τ(bx) for every element x ∈ B.

Since the R–algebra B is Gorenstein, its dual B^{∗} is a free B–module of rank 1. Any element σ of B^{∗} that generates B^{∗} as B–module is called a trace of B. There exist two relevant elements of B^{∗} which are denoted Tr and σ. The first one, Tr, is called the canonical trace of B and is defined in the following way: given an element b ∈ B, let us denote by η_{b} : B ⟶ B the homothesy induced by the multiplication by b. The image T r(b) by T r is defined as the ordinary trace of the endomorphism η_{b} of B (notice that this definition makes sense since B is a free R–module). In order to introduce σ (which will be called a trace of B), we need some additional notations. For any element G ∈ R[X_{1}, …, X_{n}] we denote by \overline{G} its image in B, i.e. the residue class of G modulo the ideal (F_{1}, …, F_{n}). Let Y_{1}, …, Y_{n} be new variables and let Y := (Y_{1}, …, Y_{n}). Let 1 ≤ j ≤ n and let F_{j}^{(Y)} := F_{j}(Y_{1}, …, Y_{n}) be the polynomial of R[Y_{1}, …, Y_{n}] obtained substituting in F_{j} the variables X_{1}, …, X_{n} by Y_{1}, …, Y_{n}. We consider the polynomial

F_{j}^{(Y)} − F_{j} = ∑_{k=1}^{n} l_{jk}(Y_{k} − X_{k}) ∈ R[X_{1}, …, X_{n}, Y_{1}, …, Y_{n}]  (4)

where the l_{jk} are polynomials belonging to R[X_{1}, …, X_{n}, Y_{1}, …, Y_{n}] of total degree bounded by (d − 1) (observe that the l_{jk}’s are not uniquely determined by the sequence F_{1}, …, F_{n}). We consider now the determinant Δ of the matrix (l_{jk})_{1≤j,k≤n} which can be written (non uniquely) as

Δ = ∑_{m} a_{m}(X_{1}, …, X_{n})b_{m}(Y_{1}, …, Y_{n}) ∈ R[X_{1}, …, X_{n}, Y_{1}, …, Y_{n}],

where the a_{m}’s are elements of R[X_{1}, …, X_{n}] and the b_{m}’s are elements of R[Y_{1}, …, Y_{n}]. The polynomial Δ is called a pseudo–jacobian determinant of the regular sequence F_{1}, …, F_{n}. Observe that the polynomials a_{m} and b_{m} can be chosen having degree bounded by n(d − 1) in the variables X_{1}, …, X_{n} and Y_{1}, …, Y_{n} respectively.

Let c_{m} ∈ R[X_{1}, …, X_{n}] be the polynomial obtained substituting the variables Y_{1}, …, Y_{n} by X_{1}, …, X_{n} in b_{m}. If \overline{J} is the residue class of the Jacobian determinant J(F_{1}, …, F_{n}) in B we have the following identity:

\overline{J} = ∑_{m} \overline{a}_{m} · \overline{c}_{m}

Since the ideal (F_{1}, …, F_{n}) is radical we see that \overline{J} is not a zero divisor of B. Furthermore, the image of the polynomial Δ in the residue class ring R[X_{1}, …, X_{n}, Y_{1}, …, Y_{n}] modulo the ideal (F_{1}, …, F_{n}, F_{1}^{(Y)}, …, F_{n}^{(Y)}) is independent of the particular choice of the matrix (l_{kj})_{1≤k,j≤n}. This justifies the name “pseudo–jacobian” for the polynomial Δ. With these notations there exists a unique trace σ ∈ B^{∗} such that the following identity holds in B:

\overline{1} = ∑_{m} σ(\overline{a}_{m}) · \overline{c}_{m}

The main property of the trace σ is known as the “trace formula” (“Tate’s trace formula” of [48, Appendix F] or [39] being special case of it). The trace formula is the following statement: for any G ∈ R[X_{1}, …, X_{n}] the identity

\overline{G} = ∑_{m} σ(\overline{G} · \overline{a}_{m}) · \overline{c}_{m}  (5)

holds true in B. Notice that the polynomial ∑_{m} σ(\overline{G} · \overline{a}_{m}) · c_{m} ∈ R[X_{1}, …, X_{n}] of the identity (5) has degree in the variables X_{1}, …, X_{n} bounded by n(d − 1).

We shall apply this trace formula in order to solve the lifting problem:

given a polynomial G ∈ R[X_{1}, …, X_{n}], find a polynomial G_{1} ∈ R[X_{1}, …, X_{n}] of degree in the variables X_{1}, …, X_{n} bounded by n(d − 1), such that \overline{G}_{1} = \overline{G} holds in B.

As one sees easily, the trace formula (5) solves this problem since it allows us to choose for G_{1} the polynomial

G_{1} := ∑_{m} σ(\overline{G} · \overline{a}_{m}) · c_{m}.  (6)

By means of the element Δ it is possible to describe the relation between the trace σ just introduced and the canonical trace Tr (see [48], Corollary E.19 and example F.19), namely:

\overline{J} · σ = T r  (7)

4.2 The computation of the matrix that performs the division

Under the assumptions made in the previous subsection, we deduce from Proposition 1 that we may assume that we are given a geometric solution for the K–algebra K ⊗_{R} B. This means that we dispose over the following items:

• a linear form U := λ_{1}X_{1} + ⋯ + λ_{n}X_{n} ∈ ZZ[X_{1}, …, X_{n}] such that u := \overline{U} is a primitive element for K ⊗_{R} B.

• a polynomial p ∈ R[T] of degree bounded by d^{n} such that p(U) belongs to the ideal (F_{1}, …, F_{n}).

• a nonzero element ρ ∈ R and polynomials v_{1}, …, v_{n} ∈ R[T] of degree bounded by d^{n} such that for any 1 ≤ j ≤ n ρX_{j} − v_{j}(U) belongs to (F_{1}, …, F_{n}).

We can now state the main result of this section:

Proposition 2. Let notations and assumptions be as above. Let {C_{m,n,d,h}}_{m,n,d,h∈IN} be a family of boolean circuits which evaluates the coefficients in R of polynomials F_{1}, …, F_{n}, F of R[X_{1}, …, X_{n}] of degree d on integers of logarithmic height bounded by h. Assume further that this family of boolean circuits also computes the coefficients in R of polynomials p, u, ρ, v_{1}, …, v_{n} which form the geometric solution for the K–algebra K ⊗_{R} B mentioned above. Let L_{h} := L(m, n, d, h) and ℓ_{h} := ℓ(m, n, d, h) be the size and depth of C_{m,n,d,h} respectively, and assume that the family {C_{m,n,d,h}}_{m,n,d,h∈IN} is uniform in space S_{h} := S(m, n, d, h). Let H_{h} := H(m, n, d, h) be the worst–case logarithmic height of the output of C_{m,n,d,h}.

Assume that \overline{F} is not a zero divisor in B. Let G ∈ R[X_{1}, …, X_{n}] be a polynomial of degree d^{O(n)} such that \overline{F} divides \overline{G} in B. Then, there exists a family of boolean circuits which, given the degree of G, computes the entries in R of a matrix A and an element θ ∈ R on integers of logarithmic height h such that if Q ∈ R[X_{1}, …, X_{n}] denotes the polynomial whose coefficients are obtained applying A to the coefficients of \overline{G} with respect to a suitable monomial basis of the R–algebra B, then the following conditions are satisfied:

i) \overline{θG} = \overline{QF} ii) The degree of Q with respect to the variables X_{1}, …, X_{n} is bounded by n(d−

1).

This family of boolean circuits has size L_{max{h_{1},h}} + (d^{n}H_{max{h_{1},h}})^{O(1)}, depth ℓ_{max{h_{1},h}} + O(n^{2} log(d) log(dH_{max{h_{1},h}})) and is uniform in space S_{max{h_{1},h}} +O(n log(dH_{max{h_{1},h}})), where h_{1} = O(n log(nd)).

Proof. Following [45], let χ_{F} := T^{D} + a_{D−1}T^{D−1} + ⋯ + a_{0} ∈ K[T] be the characteristic polynomial of the homothesy η_{F}. Define

F^{∗} := F^{D−1} + a_{D−1}F^{D−2} + ⋯ + a_{2}F + a_{1}

and notice that \overline{F} \overline{F^{∗}} = (−1)^{D+1}a_{0} holds. Since \overline{F} is not a zero divisor of B we have a_{0} ≠ 0. Therefore let us call F^{∗} the pseudo inverse of F in B.

From Formula (5) we deduce that \overline{F^{∗}G} = ∑_{m} σ(\overline{F^{∗}G}·\overline{a}_{m})·\overline{c}_{m} and following Formula (7) we have \overline{J}σ = T r. Let us define J^{∗} in a similar way to F^{∗} as the pseudo inverse of J in B (notice that by assumption \overline{J} is not a zero divisor of B). With this notation we have:

\overline{(J^{∗}J)F^{∗}G} = ∑_{m} T r(\overline{J^{∗}F^{∗}G}\overline{a}_{m})\overline{c}_{m}

In order to keep all the computations in R[X_{1}, …, X_{n}] we define τ := α^{D}ρ, where α is the leading coefficient of p, and N as the maximum of the degrees of F, J, a_{m} and G. Setting F′ := τ^{N}F, J′ := τ^{N}J, a′_{m} := τ^{N}a_{m} and G′ := τ^{N}G, we see that the matrices M_{F′} , M_{J′} , M_{a′_{m}} , M_{G′} corresponding to the homothesies η_{F′} , η_{J′} , η_{a′_{m}} , η_{G′} in K ⊗_{R} B with respect to the basis {1, u, …, u^{D−1}} (given by the primitive element u of K ⊗_{R} B) have all their entries in R.

Observe also that F^{′∗} = τ^{N(D−1)}F^{∗} and M_{F^{′∗}} = (−1)^{D+1}Adj(M_{F′}) holds. Then we have that \overline{J}′ is not a zero divisor of B and that the identity

(J^{′∗}J′)F^{′∗}G′ = ∑_{m} T r(J^{′∗}F^{′∗}G′a′_{m})b_{m}

holds.

In consequence, defining

Q := ∑_{m} T r(J^{′∗}F^{′∗}G′a′_{m})c_{m} = ∑_{m} T r(Adj(M_{J′})Adj(M_{F′})M_{G′}M_{a′_{m}})b_{m} (8)

and

θ := (J^{′∗}J′)(F^{′∗}F′) = det(M_{J′})det(M_{F′})

we obtain the polynomials Q and θ required.

The matrix A can easily be extracted from the formula that defines the polynomial Q as follows: observe that by Formula (5) we may assume without loss of generality that the degree of G with respect to the variables X_{1}, …, X_{n} is bounded by n(d − 1) (using the fact that the trace is R–linear). Then the entries of M_{G′} depend R–linearly on the coefficient vector of G and so do the coefficients of Adj(M_{Δ′})Adj(M_{F′})M_{G′}M_{a′_{m}}. Taking into account that the canonical trace is R–linear we see that the polynomial T r(Adj(M_{J′})Adj(M_{F′})M_{G′}M_{a′_{m}}) can be expressed as an R–linear combination of the coefficients of G. Finally, combining this expression with the coefficients of b_{m} with respect to the variables X_{1}, …, X_{n} shows that the coefficients of Q depend R–linearly on the coefficient vector of G.

Let us observe that the polynomials θ and Q have been constructed in such a way that θ divides the polynomial Q in R[X_{1}, …, X_{n}]. To prove this statement we observe that there exists Q_{1} ∈ R[X_{1}, …, X_{n}] such that G ≡ Q_{1}F holds modulo (F_{1}, …, F_{n})). This implies that

\begin{aligned}T r(J^{′∗}F^{′∗}G′a′_{m}) & = & T r(J^{′∗}F^{′∗}F′Q_{1}a′_{m}) = \\ = F^{′∗}F′σ(J′J^{′∗}Q_{1}a′_{m}) & = & (J^{′∗}J′)(F^{′∗}F′)σ(Q_{1}a′_{m}) \end{aligned}

holds.

We now analyze the size, depth, and space–uniformity of the algorithm that computes the matrix A of Proposition 2. Let n, m, d be fixed and let us denote L_{h} := L(n, m, d, h), ℓ_{h} := ℓ(n, m, d, h) and H_{h} := H(n, m, d, h). First of all we observe that the dense representation of the polynomials l_{kj} that occur in Equation (4) can be computed using space O(n log d). For example, using the following simple identity:

X_{1}^{α_{1}}···X_{n}^{α_{n}}−Y_{1}^{α_{1}}···Y_{n}^{α_{n}} = ∑_{i=1}^{n}(X_{i}−Y_{i}) ∑_{j=0}^{α_{i}−1} Y_{1}^{α_{1}}···Y_{i−1}^{α_{i−1}}X_{i}^{j}Y_{i}^{α_{i}−1−j}X_{i+1}^{α_{i+1}}···X_{n}^{α_{n}}

we deduce that all the coefficients appearing in the dense representation of every l_{kj} can be described as a sum of some suitably chosen coefficients of the polynomials F_{j} and that this description can be made in space O(n log d). The additions required can be computed, using the three–for–two trick that we have mentioned in Lemma 2, by means of a family of boolean circuits with size L_{h}+O(d^{n}H_{h}) and depth ℓ_{h} + O(n log(dH_{h})), which is uniform in space O(S_{h} + n log(dH_{h}L_{h})). We observe that the polynomials computed have logarithmic height H_{h} + O(n log d) on integers of logarithmic height h. Then we compute the determinant of the matrix (l_{kj}) and the dense representation of the polynomials Λ, a_{m}, b_{m} by a process of recursive interpolation applying Lemma 12.

In a similar way we compute the jacobian J and its dense representation. First we compute the polynomials \frac{∂F_{i}}{∂X_{j}} on integers of logarithmic height h_{1} := O(n log(nd)) from the dense representation of F_{1}, …, F_{n}. Notice that the resulting integers have logarithmic height O(n log(d)H_{h_{1}}) and that the computation can be performed by means of a family of boolean circuits with size L_{h} + (d^{n}H_{h_{1}})^{O(1)} and depth ℓ_{h} + O(n log(n) log(ndH_{h_{1}})), which is uniform in space S_{h} + O( log(ndH_{h_{1}})). Then we compute the determinant of the jacobian matrix and finally we compute the dense representation of J by a process of recursive interpolation applying Lemma 12. The resulting integers have logarithmic height O(nd log(dH_{max{h_{1},h}}))^{O(1)} and the computation can be performed by means of a family of boolean circuits with size L_{max{h_{1},h}} + (d^{n}H_{max{h_{1},h}})^{O(1)} and depth ℓ_{max{h_{1},h}}+O(n log(n) log(ndH_{max{h_{1},h}})), which is uniform in space S_{max{h_{1},h}} + O( log(ndH_{max{h_{1},h}})).

Then we compute the matrices M_{F′}, M_{J′}, M_{a′_{m}} and M_{G′} of the homothesies η_{F′}, η_{J′}, η_{a′_{m}} and η_{G′} induced by the multiplication by F′, J′, a′_{m} and G′ respectively. These matrices have the form M_{τ^{N} H} where H is a given polynomial H ∈ R[X_{1}, …, X_{n}] of degree with respect to the variables X_{1}, …, X_{n} bounded by N. The polynomial H is given by its dense representation H := ∑_{|μ|≤N} a_{μ}X_{1}^{μ_{1}} ⋯ X_{n}^{μ_{n}} with a_{μ} ∈ R. From the identity:

M_{τ^{N} H} = ∑_{|μ|≤N} a_{μ}τ^{N−|μ|}M_{τX_{1}}^{μ_{1}} ⋯ M_{τX_{n}}^{μ_{n}}  (9)

we deduce that the computation of M_{τ^{N} H} can be reduced to matrix computations.

In order to compute the matrices M_{τX_{i}} for 1 ≤ i ≤ n we observe that M_{τX_{i}} = α^{D}v_{i}(\frac{1}{α}M_{αu}), where M_{αu} is the matrix which is obtained by multiplying the companion matrix of the polynomial \frac{1}{α}p by α. Therefore, if v_{i}(T) := ∑_{k=0}^{D} b_{ki}T^{k} we define V_{i}(T) := ∑_{k=0}^{D} b_{ki}α^{D−k}T^{k}. Then we have that M_{τX_{i}} = V_{i}(M_{αu}). The mapping which yields the entries of the matrix M_{αu} from the coefficients of the polynomial p can be easily described in space O(n log d). Then we compute the matrices M_{τX_{i}} for 1 ≤ i ≤ n in the following way: we first compute the matrices M_{αu}^{2}, …, M_{αu}^{D} applying Lemma 4, then we compute α^{2}, …, α^{D} with D multiplications in depth O(log D). Finally we compute simultaneously the product b_{ki}α^{D−k} for 1 ≤ k ≤ D and 1 ≤ i ≤ n and the matrices M_{τX_{i}} for 1 ≤ i ≤ n as some suitable linear combinations of the matrices I, …, M_{αu}^{D}. We observe that the products b_{ki}α^{D−k} and the entries of the matrices M_{αu}^{k} have logarithmic height bounded by O(d^{n}H_{h})^{O(1)}. Therefore, combining the Macro expansion lemma with Lemma 4 we deduce there exists a family of boolean circuits computing the matrices M_{τX_{i}} for 1 ≤ i ≤ n with size L_{h} + (d^{n}H_{h})^{O(1)} and depth ℓ_{h} +O(n^{2} log(d) log(dH_{h})), which is uniform in space S_{h} +O(n log(dH_{h})). Notice that the entries of the matrices M_{τX_{i}} have logarithmic height bounded by (d^{n}H_{h})^{O(1)}.

Then we compute the matrices M_{F′}, M_{J′}, M_{a′_{m}} using equation (9), the matrices Adj(M_{J′}), Adj(M_{F′}) and θ = det(M_{J′})det(M_{F′}). Let G′ = ∑_{|μ|≤N} g_{μ} X_{1}^{μ_{1}} ⋯ X_{n}^{μ_{n}}. In order to compute the matrix A of the statement of the proposition we observe that, since the canonical trace is R–linear, we have that

T r(Adj(M_{J′}), Adj(M_{F′})M_{G′}M_{a_{m}}) = ∑_{|μ|≤N} c_{μ}g_{μ}  (10)

holds, where the coefficients c_{μ} are given by the formula:

c_{μ} := τ^{N−|μ|}T r(Adj(M_{J′}), Adj(M_{F′})M_{τX_{1}}^{μ_{1}} ⋯ M_{τX_{n}}^{μ_{n}}).

Observe that the polynomials c_{μ} have logarithmic height (d^{n}H_{max{h_{1},h}})^{O(1)} on integers of logarithmic height h. Therefore, applying the Macro expansion lemma and Lemmata 3, 4 and 7 we obtain a family of boolean circuits computing the polynomials c_{μ} with size L_{max{h_{1},h}} + (d^{n}H_{max{h_{1},h}})^{O(1)} and depth ℓ_{max{h_{1},h}}+O(n^{2} log(d) log(dH_{max{h_{1},h}}), which is uniform in space S_{max{h_{1},h}}+ O(n log(dH_{max{h_{1},h}})).

Let b_{m} := ∑_{|μ̃|≤nd} b(m) ; μ̃Xμ̃_{1} ; 1 ⋯ Xμ̃_{n} ; n. Then applying equations (8) and (10) we have that

Q = ∑_{m} T r(Adj(M_{J′})Adj(M_{F′})M_{G′}M_{a′_{m}})b_{m}
= ∑_{m} ∑μ̃(∑_{μ} c_{μ}g_{μ})b(m) ; μ̃Xμ̃_{1} ; 1 ⋯ Xμ̃_{n} ; n
= ∑μ̃ ( ∑_{m} b(m) ; μ̃(∑_{μ} c_{μ}g_{μ}))Xμ̃_{1} ; 1 ⋯ Xμ̃_{n} ; n
= ∑μ̃ ( ∑_{μ} ((∑_{m} b(m) ; μ̃)c_{μ})g_{μ})Xμ̃_{1} ; 1 ⋯ Xμ̃_{n} ; n

holds. Therefore, the entry (μ̃, μ) of the matrix A is given by (∑_{m} b(m) ; μ̃)c_{μ}. These entries can be computed by a family of boolean circuits whose size, depth and space–uniformity satisfies the statement of the proposition.

5 Applications to geometric elimination problems

In this section we apply the techniques developed in the previous sections to concrete elimination problems. We are going to study the consistency problem for polynomial equation systems and the representation of the unity 1 in case that the system under consideration does not have any solution (the effective Nullstellensatz problem), the membership of a polynomial to a complete intersection ideal and the corresponding representation problem and an algorithmic version of Quillen–Suslin Theorem.

5.1 The consistency of polynomial equation systems and the effective Nullstellensatz

Let F_{1}, …, F_{s} be polynomials in ZZ[X_{1}, …, X_{n}] of degrees bounded by d and logarithmic height bounded by h. The problems we are going to solve in this subsection are the following:

i) Decide whether the system defined by F_{1}, …, F_{s} is inconsistent, that is, whether the algebraic variety V ⊂ C^{n} that consists of the common zeros of F_{1}, …, F_{s} is empty.

ii) If this is the case, find a representation of the unity 1 as follows:

1 = P_{1}F_{1} + ⋯ + P_{s}F_{s}

where the polynomials P_{1}, …, P_{s} belong to Q [X_{1}, …, X_{n}].

Let r be the dimension of V and let V = V_{r} ∪ ⋯ ∪ V_{0} be the decomposition of V in equidimensional components, where V_{i} is empty or an equidimensional variety of dimension i for i = 0, …, r.

Let 0 ≤ i ≤ r and suppose that V_{i} is nonempty. As proved in [34], if we choose i generic hyperplanes H_{1}^{(i)}, …, H_{i}^{(i)}, the following conditions are satisfied:

i) V_{i} ∩ H_{1}^{(i)} ∩ ⋯ ∩ H_{i}^{(i)} is a zero–dimensional variety of cardinality deg(V_{i}). ii) V_{j} ∩ H_{1}^{(i)} ∩ ⋯ ∩ H_{i}^{(i)} = ∅ if j < i. iii) V_{j} ∩H_{1}^{(i)} ∩⋯∩H_{i}^{(i)} is an equidimensional variety of dimension j −i if j > i.

Hence, the isolated points of the variety V ∩H_{1}^{(i)} ∩⋯∩H_{i}^{(i)} are the points of V_{i} ∩ H_{1}^{(i)} ∩ ⋯ ∩ H_{i}^{(i)}. Thus, by deciding whether the variety V ∩ H_{1}^{(i)} ∩ ⋯ ∩ H_{i}^{(i)} has a positive number of isolated points one determines if V_{i} is empty or not. The greatest i such that V_{i} is not empty gives us the dimension of V and in case that V_{i} is empty for i = 0, …, n we have that V is empty.

In order to decide algorithmically the emptiness of the varieties V_{i} we need a bound on the degree of the polynomials which represent the condition of genericity required for the coefficients of the hyperplanes H_{1}^{(i)}, …, H_{i}^{(i)}. In this direction, we have the following result:

Lemma 19. There exist a polynomial P_{i} ∈ ZZ[A_{jk}, B_{j}; 1 ≤ j ≤ i, 1 ≤ k ≤ n] which is computable by an arithmetic circuit of nonscalar depth O(n^{2} log d), and which has the following property: any vector γ ∈ ZZ^{n(i+1)} with P_{i}(γ) ≠ 0 yields the coefficients of i hyperplanes satisfying conditions i), ii) and iii) above.

Proof. From [27] we deduce that each component V_{i} can be described as the set of common zeros of certain polynomials G_{1}^{(i)}, …, G_{t_{i}}^{(i)} in ZZ[X_{1}, …, X_{n}] of degree bounded by d^{n}. We introduce new variables A_{jk}, B_{j} for 1 ≤ j ≤ i and 1 ≤ k ≤ n and denote by H_{j}^{(i)} the following generic hyperplane:

H_{j}^{(i)} := ∑_{k=1}^{n} A_{jk}X_{k} + B_{j}

for k = 1, …, j.

Following [34] there exists a nonempty Zariski open subset of C^{n(i+1)} with the following property: the hyperplanes obtained by specializing the variables A_{jk}, B_{j} in the coordinates of any point of this Zariski open set intersect V_{i} in deg(V_{i}) points. Hence, the variety W consisting of the solutions in \overline{C[A_{jk}, B_{j}; 1 ≤ j ≤ i, 1 ≤ k ≤ n]}^{n} of the system

G_{1}^{(i)} = 0, …, G_{t_{i}}^{(i)} = 0, H_{1}^{(i)} = 0, …, H_{i}^{(i)} = 0

is zero–dimensional and consists of deg(V_{i}) points. From Section 3 we deduce the existence of a well–parallelizable arithmetic circuit of nonscalar O(n^{2} log d) that computes the coefficients in ZZ[A_{jk}, B_{j}; 1 ≤ j ≤ i, 1 ≤ k ≤ n] of the following polynomials:

• a linear form U ∈ ZZ[X_{1}, …, X_{n}], and

• a polynomial p ∈ ZZ[A_{jk}, B_{j}; 1 ≤ j ≤ i, 1 ≤ k ≤ n][T] of degree deg(V_{i})

such that U separates the points of W and p is the primitive minimal polynomial that annihilates U over W.

Let γ be a vector of ZZ^{n(i+1)} such that if we replace the variables A_{jk}, B_{j} by γ in p, the resulting polynomial of ZZ[T] is squarefree and has degree deg(V_{i}). Then the hyperplanes obtained from γ intersect V_{i} in exactly deg(V_{i}) points. Hence, we impose to the coefficients of the hyperplanes H_{1}^{(i)}, …, H_{i}^{(i)} the condition of not annihilating the leading coefficient α of p and the discriminant Δ ∈ ZZ[A_{jk}, B_{j}; 1 ≤ j ≤ i, 1 ≤ k ≤ n] of p. The product of both polynomials, the generic condition we are looking for, can be computed with nonscalar depth O(n^{2} log d) (here the computation of Δ relies on subresultant techniques as in [8]).

Now we are going to introduce a condition of genericity for the coefficients of the hyperplanes H_{1}^{(i)}, …, H_{i}^{(i)} which guarantees that condition ii) is fulfilled. For this purpose, we use a diophantine version of the effective Nullstellensatz. Since generically the intersection (V_{i−1}∪⋯∪V_{0})∩(H_{1}^{(i)}∪…∪H_{i}^{(i)}) is empty, the same happens when the situation is considered in \overline{C[A_{jk}, B_{j}; 1 ≤ j ≤ i, 1 ≤ k ≤ n]}^{n}. Applying the effective Nullstellensatz in the version of [45], we deduce the existence of a nonzero polynomial a ∈ ZZ[A_{jk}, B_{j}; 1 ≤ j ≤ i, 1 ≤ k ≤ n], computable by means of an arithmetic circuit of nonscalar depth O(n^{2} log d), that belongs to the ideal generated by the polynomials which define V_{i−1} ∪ ⋯ ∪ V_{0} and H_{1}^{(i)}, …, H_{i}^{(i)}.

Any evaluation of the variables A_{jk}, B_{j} in a vector γ ∈ ZZ^{n(i+1)} such that a(γ) ≠ 0 guarantees that the linear variety defined by the intersection of the hyperplanes H_{1}^{(i)}(γ), …, H_{i}^{(i)}(γ) does not intersect V_{i−1} ∪ ⋯ ∪ V_{0}. Thus, the condition of genericity we are looking for is the non vanishing of the polynomial a.

Let j > i. It remains to satisfy the third condition, namely that W_{j} := V_{j} ∩ H_{1}^{(i)} ∩ … ∩ H_{i}^{(i)} does not contain isolated points. Using the same arguments as before, we consider the situation over \overline{C[A_{jk}, B_{j}; 1 ≤ j ≤ i, 1 ≤ k ≤ n]}^{n}. In the same way as in Section 3 we construct an arithmetic circuit of nonscalar depth O(n^{2} log d) which represents a geometric solution of a suitable zero–dimensional variety W̃_{j} that contains the isolated points of W_{j}. Let U_{1} ∈ ZZ[X_{1}, …, X_{n}] be the linear form given by this geometric solution and let p_{1} ∈ ZZ[A_{jk}, B_{j}; 1 ≤ j ≤ i, 1 ≤ k ≤ n][T] be the minimal polynomial of U_{1}. Since the variety W_{j} does not have isolated points, the intersection of the variety W̃_{j} with the variety W_{j} must be empty. In order to check this condition we replace the variables X_{1}, …, X_{n} in the polynomials which define W_{j} by the parameterizations obtained in the geometric solution of W̃_{j}. In this way we obtain some polynomials belonging to ZZ[A_{jk}, B_{j}; 1 ≤ j ≤ i, 1 ≤ k ≤ n][T] with the property that their greatest common divisor with p(T) equals the unity 1.

Following the strategy of Lemma 10, we compute a polynomial b in ZZ[A_{jk}, B_{j}; 1 ≤ j ≤ i, 1 ≤ k ≤ n] which can be written as an arithmetical expression of the involved polynomials. Any point γ ∈ ZZ^{n(i+1)} such that b(γ) ≠ 0 yields the coefficients of some hyperplanes H_{1}^{(i)}, …, H_{i}^{(i)} such that the corresponding intersection W_{j} ∩ W̃_{j} is empty. Hence, the polynomial b represents the remaining condition of genericity.

Finally, multiplying these O(n) conditions of genericity we obtain a polynomial P_{i} ∈ ZZ[A_{jk}, B_{j}; 1 ≤ j ≤ i, 1 ≤ k ≤ n], computable with nonscalar depth O(n^{2} log d), which verifies that any vector γ ∈ ZZ^{n(i+1)} such that P_{i}(γ) ≠ 0 yields the coefficients of i hyperplanes satisfying all the required conditions.

Now we can solve the consistency problem for polynomial equation systems:

Theorem 1. There exists a probabilistic Turing machine M which, on input the dense representation of polynomials F_{1}, …, F_{s} of degree d and logarithmic height h, computes the dimension of the algebraic variety V := V (F_{1}, …, F_{s}) ⊆ C^{n}

using space O(n^{4} log(nd) log(nsdh)) and time (nd)^{O(n^{2} log(nsdh))}.

Proof. As we have mentioned before, the computation of the dimension can be easily reduced to determine whether the algebraic variety V ∩ H_{1}^{(i)} ∩ ⋯ ∩ H_{i}^{(i)} has isolated points for 1 ≤ i ≤ n, where the hyperplanes H_{1}^{(i)}, …, H_{i}^{(i)} satisfy the requirements of Lemma 19. For this purpose, applying Proposition 1 with R = ZZ we compute a geometric solution of a zero–dimensional W_{i} containing the isolated points of V ∩ H_{1}^{(i)} ∩ ⋯ ∩ H_{i}^{(i)}. Then we replace the parameterizations of the geometric solution of W_{i} in the equations that define the variety V ∩ H_{1}^{(i)} ∩⋯∩H_{i}^{(i)} and obtain some univariate polynomials whose greatest common divisor, say g_{i}(u), equals the unity 1 if and only if there are no isolated points of V ∩ H_{1}^{(i)} ∩ ⋯ ∩ H_{i}^{(i)} (see e.g. [11]).

We observe that a nonzero ZZ–multiple of the polynomial g_{i}(u) can be computed by a family of boolean circuits with size (sh(nd)^{n})^{O(1)} and depth O(n^{2} log(nd) log(nsdh)), which is uniform in space O(n^{2} log(nsdh)). This can be proved combining the Macro expansion lemma, Proposition 1 and Lemma 10.

Combining [45, Lemma 14] with Lemma 19, we see that for 1 ≤ i ≤ n the polynomial P_{i} in the statement of Lemma 19 has degree bounded by d^{cn^{2}}, where c is a suitable constant not depending neither on d nor n. Therefore, applying Schwartz–Zippel test we deduce that a random choice of an (ni)–tuple on integers in the set {1, …, d^{(c+1)n^{2}}}^{ni} does not annihilate the polynomial P_{i} with probability at least 1 − \frac{1}{d^{n^{3}}} .

The probabilistic Turing machine M in the statement of the theorem starts guessing an integer (ni)–tuple γ^{(i)} in the set {1, …, d^{(c+1)n^{2}}}^{ni} for 1 ≤ i ≤ n. The vector γ^{(i)} provide the coefficients of i hyperplanes H_{1}^{(i)}, ⋯, H_{i}^{(i)} of logarithmic height O(n^{2} log n log d) that verify Conditions i), ii) and iii) of Lemma 19 with probability at least 1− \frac{1}{d^{n^{3}}} . The vectors γ^{(1)}, …, γ^{(n)} are stored in working space.

Then the machine M decides for 1 ≤ i ≤ n the existence of isolated points of the algebraic variety V ∩ H_{1}^{(i)} ∩ ⋯ ∩ H_{i}^{(i)} for 1 ≤ i ≤ n. For this purpose, we have that there exists a deterministic Turing machine M_{1} computing the standard encoding of a boolean circuit C which computes a nonzero integer multiple of the polynomial g_{i}(u) which equals the unity 1 if and only if the variety V ∩ H_{1}^{(i)} ∩ ⋯ ∩ H_{i}^{(i)} does not have isolated points.

In our case the coefficients of the polynomials F_{1}, …, F_{s}, H_{1}^{(i)}, …, H_{i}^{(i)} which are the inputs of the boolean circuit C are available either from the input in the case of F_{1}, …, F_{s} or from working space in the case of H_{1}^{(i)}, …, H_{i}^{(i)}. The 3n + 3 integer parameters required to apply Proposition 1 are obtained as a consequence of the application of Schwartz–Zippel test. Therefore, they are randomly chosen in a set {1, …, (nsd)^{c′n}}^{3n+3} with probability of success at least 1 − \frac{1}{(nsd)^{3n^{2}}} and stored in working space. We recall that the circuit C has size (sh(nd))^{O(1)} and depth O(n^{2} log(nd) log(nsdh) and the machine M_{1} requires space O(n log(nsdh)) to compute its standard encoding.

Then the machine M applies Borodin’s argument to evaluate the circuit C. It evaluates the circuit C by following a standard “depth first” traversal of the graph of C and generating the standard encoding of every node of the graph of C by a call to the machine M_{1}. A stack of depth O(n^{2} log(nd) log(nsd)) is used to keep track of the path from the current output bit of the circuit to the node which is being evaluated. For every cell of the stack to have size O(1), a special encoding of the path is used in such a way that at every step in the computation, the stack is seen as a string on the alphabet {0, 1, ℓ}. This string encodes the choice of the path at every level (node) between its left and right input. At the same time the result of the evaluation of the left subcircuit is stored, if the right subcircuit is being traversed. In this way, the machine M deterministically evaluates the circuit C using only additional space O(n^{2} log(nd) log(nsdh)) and

time (nsdh)^{O(n^{2} log(nd))}.

Assuming now that V is the empty set we solve the effective Nullstellensatz problem.

Theorem 2. There exists a probabilistic Turing machine using space O(n^{3}

log(nh) log(nsdhh_{1})) and time (nd)^{O(n^{2} log(sndhh_{1}))} which, on input the dense representation of polynomials F_{1}, …, F_{s} of degree d and logarithmic height h, computes an integer a and polynomials P_{1}, …, P_{s} ∈ ZZ[X_{1}, …, X_{n}] (on integers of logarithmic height h_{1}) such that the following identity holds:

a = P_{1}F_{1} + ⋯ P_{s}F_{s}.

Proof. First of all, we perform a preprocessing of our polynomial data. For this purpose let us observe that there exist a natural number t ≤ n and (t+1)–linear combinations of F_{1}, …, F_{s}, say F′_{1}, …, F′_{t+1}, with the following properties:

• V (F′_{1}, …, F′_{t+1}) = V (F_{1}, …, F_{s}).

• F′_{1}, …, F′_{i} form a regular sequence for i = 1, …, t.

• (F′_{1}, …, F′_{i}) is a radical ideal of Q [X_{1}, …, X_{n}] for every i = 1, …, t

• the coefficients λ_{ij} occurring in the linear combinations that define the polynomials F′_{1}, …, F′_{t+1} verify the condition |λ_{ij}| ≤ d^{n} and can be chosen at random from the set {1, …, d^{2n}}^{n} with probability of success greater than 1 − \frac{1}{d^{n^{2}}} .

This is achieved by means of a combination of Schwartz–Zippel test and an effective version of Bertini Theorem (cf. [40]) in the version of [45].

Furthermore, there exists a linear change of coordinates

(X_{1}, …, X_{n}) → (Y_{1}, …, Y_{n})

such that the variables Y_{1}, …, Y_{n} are in Noether position with respect to the variety V_{i} := V (F′_{1}, …, F′_{i}) for i = 1, …, t. Applying the arguments of [16] or [45], we deduce that the entries of the matrix that performs this linear change of variables can be generated by means of the Schwartz–Zippel test in such a way that their logarithmic height is of order d^{O(n)}.

The problem of finding a polynomial combination of F_{1}, …, F_{s} that equals the unity 1 will be solved by means of Proposition 2. This is done by performing divisions modulo suitable complete intersection ideals.

The idea is the following: since F′_{t+1} divides the unity 1 modulo the ideal (F′_{1}, …, F′_{t}), it is possible to compute by means of Proposition 2 an element θ_{t+1} of the polynomial ring R_{t} := Q [Y_{1}, …, Y_{n−t}] and a polynomial Q_{t+1} ∈ Q [Y_{1}, …, Y_{n}] of degree bounded by nd such that θ_{t+1} divides Q_{t+1} and such that the condition

θ_{t+1} · 1 ≡ Q_{t+1}F′_{t+1} modulo (F′_{1}, …, F′_{t})

is satisfied.

This means that θ_{t+1}(1 − F′_{t+1} \frac{Q_{t+1}}{θ_{t+1}} ) belongs to (F′_{1}, …, F′_{t}), which is an equidimensional ideal of dimension n−t intersecting the polynomial ring R_{t} only in zero. Therefore 1−F′_{t+1} \frac{Q_{t+1}}{θ_{t+1}} belongs to the ideal (F′_{1}, …, F′_{t}). Hence F′_{t} divides

1 − F′_{t+1} \frac{Q_{t+1}}{θ_{t+1}} modulo (F′_{1}, …, F′_{t−1}), which in turn implies that θ_{t+1}F′_{t} divides the polynomial θ_{t+1} · 1 − Q_{t+1}F′_{t+1} which belongs to the ideal (F′_{1}, …, F′_{t−1}).

Now we divide the polynomial θ_{t+1} ·1−Q_{t+1}F′_{t+1} by θ_{t+1}F′_{t} modulo the ideal (F′_{1}, …, F′_{t−1}). In this way we obtain an element θ_{t} of the polynomial ring R_{t−1} := Q [Y_{1}, ..., Y_{n−t+1}] and a polynomial Q_{t} ∈ Q [Y_{1}, …, Y_{n}] of degree bounded by nd such that θ_{t} divides Q_{t} in R_{t−1} and such that

θ_{t}θ_{t+1} · 1 − θ_{t}Q_{t+1}F′_{t+1} − Q_{t}θ_{t+1}F′_{t} ∈ (F′_{1}, …, F′_{t−1})

holds.

Applying this argument recursively, we compute polynomials θ_{1}, …, θ_{t+1}, Q_{1}, …, Q_{t+1} of Q [Y_{1}, …, Y_{n}], such that the following conditions are satisfied for 1 ≤ i ≤ t + 1:

• the polynomial θ_{i} belongs to R_{i−1} := Q [Y_{1}, …, Y_{n−i−1}].

• the polynomial Q_{i} belongs to R_{i−1}[Y_{n−i}, …, Y_{n}] and its degree in Y_{n−i}, …, Y_{n} is bounded by nd.

• θ_{i} divides Q_{i} in Q [Y_{1}, …, Y_{n}].

• The polynomial θ_{t−i} ⋯ θ_{t+1} ·1−Q_{t−i} ⋯ θ_{t+1}F′_{t−i} −⋯−θ_{t−i} ⋯ θ_{t}Q_{t+1}F′_{t+1} belongs to the ideal (F′_{1}, …, F′_{t−i−1})

As a consequence, at the end of the last recursive step we obtain the identity:

θ_{1} ⋯ θ_{t+1}·1 = Q_{1}θ_{2} ⋯ θ_{t+1}F_{1}+θ_{1}Q_{2}θ_{3} ⋯ θ_{t+1}F_{1}+⋯+θ_{1} ⋯ θ_{t}Q_{t+1}F_{t+1} (11)

where each θ_{i} divides Q_{i} in Q[Y_{1}, …, Y_{n}]. Thus, applying Lemma 14, we are able to compute without divisions a nonzero integer a and polynomials P_{1}, …, P_{t+1} ∈ ZZ[Y_{1}, …, Y_{n}] such that P_{i} = a\frac{Q_{i}}{θ_{i}} for i = 1, …, t + 1.

Substituting this identity in (11) we obtain a representation:

a = P′_{1}F′_{1} + ⋯ + P′_{t+1}F′_{t+1}.  (12)

Taking into account equation (12) and the fact that F′_{i} = ∑_{j=1}^{s} λ_{ij}F_{j} for 1 ≤ i ≤ t + 1, we obtain the representation we are looking for:

a = P_{1}F_{1} + ⋯ + P_{s}F_{s}  (13)

where the polynomial P_{i} is defined as P_{i} := ∑_{i=1}^{t+1} λ_{ij}P′_{i} for 1 ≤ i ≤ s.

Let us analyze the size, depth and space–uniformity of the family of boolean circuits which computes the polynomials Q_{i+1} and θ_{i+1}. These polynomials are obtained by a division modulo the ideal (F′_{1}, …, F′_{i}), which is viewed as a zero–dimensional ideal of R_{i}[Y_{n−i+1}, …, Y_{n}]. This requires the computation of a geometric solution of the variety defined by F′_{1}, …, F′_{i} considered as zero– dimensional varieties over \overline{C(Y_{1}, …, Y_{n−i})}^{i}, which is obtained applying Proposition 1. For this purpose, we observe that the coefficients in R_{i} of the polynomials F′_{1}, …, F′_{i} can be computed on integers of logarithmic height h_{1} from the dense representation of F_{1}, …, F_{s} and the coefficients of the matrices of the preprocessings mentioned above by means of a family of boolean circuits with size s^{3}d^{O(n)}(hh_{1})^{2} and depth O(n log dshh_{1}) which is uniform in space O(n log dshh_{1}). We remark that the resulting integers have logarithmic height bounded by h + dh_{1} + O(n log sd).

Notice that the polynomials F′_{1}, …, F′_{i} define a zero–dimensional variety and that this variety is defined by as many equations as unknowns. Therefore applying Proposition 1 we obtain a family of boolean circuits computing a geometric solution of the variety defined by F′_{1}, …, F′_{i} over \overline{C(Y_{1}, …, Y_{n−i})}^{i} with size (shh_{1}(nd)^{n})^{O(1)} and depth O(n^{2} log(nd) log(ndshh_{1})) which is uniform in space O(n^{2} log dshh_{1}). We observe that the resulting integers have logarithmic height bounded by (sd^{n}hh_{1})^{O(1)}.

The procedure for the computation of Q_{i+1} and θ_{i+1} depends recursively on the computation of Q_{i+2} and θ_{i+2}. In order to parallelize this procedure, we observe that Proposition 2 allows to compute a matrix A^{(i)} which applied linearly on the coefficients of the dividend G_{i+1} := θ_{i+2} ⋯ θ_{t+1} ·1−θ_{i+2} ⋯ θ_{t}Q_{t+1}F′_{t+1} − ⋯ − Q_{i+2} ⋯ θ_{t+1}F′_{i+2} gives the coefficients of the quotient Q_{i+1}, and this depending only on the degree of the dividend G_{i+1} and on the coefficients of the polynomials F′_{1}, …, F′_{i+1}. We also observe that the fact that R_{i} ⊆ R_{i+1} implies that the polynomials G_{i+k}, Q_{i+k} viewed as polynomials with coefficients in R_{i} verifies that deg_{Y_{n−i+1},...,Y_{n}} G_{i+k} ≤ (n−1)d and deg_{Y_{n−i+1},...,Y_{n}} Q_{i+k} ≤ (n−1)d.

Following [45] we compute independently of G_{i+1}, …, G_{t+1} the following items:

• All the coefficients in R_{i}, …, R_{t+1} of the polynomials F′_{1}, …, F′_{t+1}. As we have mentioned before there exists a family of boolean computing these coefficients on integers of logarithmic height h_{1} with size s^{3}d^{O(n)}(hh_{1})^{2} and depth O(n log dshh_{1}) which is uniform in space O(n log dshh_{1}). We remark that the resulting integers have logarithmic height bounded by h + dh_{1} + O(n log sd).

• The value θ_{j} ∈ R_{j−1} and the matrix A^{(j)} with entries in R_{j−1}[Y_{n−j+2}, …, Y_{n}] given by the application of Proposition 2 for i+2 ≤ j ≤ t+1. From Proposition 2 we see that there exists a family of boolean circuits computing these items on integers of logarithmic height h_{1} with size (shh_{1}(nd)^{n})^{O(1)} and depth O(n^{2} log(nd) log(ndshh_{1})) which is uniform in space O(n^{2} log ndshh_{1}). We remark that the resulting integers have logarithmic height bounded by (sd^{n}hh_{1})^{O(1)}.

• Matrices T_{j} for i+1 ≤ j ≤ t+1 which transform the coefficients of a polynomial P ∈ R_{j_{1}}[Y_{n−j+2}, …, Y_{n}] of degree bounded by (n−1)d which has worst– case logarithmic height H(j, h_{1}) on integers of logarithmic height h_{1}, on the coefficients of the polynomial F_{j}P of degree at most nd on integers of logarithmic height h_{1}. Applying Lemma 2 we see that this can be done by means of a family of boolean circuits of size (nshh_{1}H(j, h_{1})d^{n})O(1) and depth O(n log dshh_{1}H(j, h_{1})) which is uniform in space O(n log dshh_{1}H(j, h_{1})).

• Matrices B_{j} for i + 1 ≤ j ≤ t + 1 which transform the coefficients in R_{j−1} of a polynomial P ∈ R_{j_{1}}[Y_{n−j+2}, …, Y_{n}] of degree bounded by nd which has worst–case logarithmic height H(j, h_{1}) on integers of logarithmic height h_{1} on its coefficients when viewed as a polynomial with coefficients in R_{j−2} on integers of logarithmic height h_{1}. Applying Lemma 12 we see that this can be done by means of a family of boolean circuits of

size (shh_{1}H(j, O(n log d))(nd)^{n})^{O(1)} and depth O(n^{2} log(nd) log(ndshh_{1}

H(j, O(n log d))) which is uniform in space O(n log(ndshh_{1}H(j, O(n log d))).

If we define for i+1 ≤ j ≤ t+1 the matrix N_{j} := B_{j}(θ_{j}Id−θ_{j+1} ⋯ θ_{t+1}T_{j}Q_{j}), we have that the coefficients of the polynomial Q_{i+1} in R_{i} can be obtained by multiplying the matrix N_{i+2} ⋯ N_{t+1} by the coefficient vector of the polynomial 1 viewed as a polynomial of R_{t}. Therefore, applying Lemma 3 we conclude that the coefficients of the polynomials Q_{i+1} and θ_{i+1} can be computed by a family of boolean circuits of size (shh_{1}(nd)^{n})^{O(1)} and depth O(n^{2} log(nd) log(ndshh_{1})) which is uniform in space O(n^{2} log ndshh_{1}). We remark that the resulting integers have logarithmic height bounded by (sd^{n}hh_{1})^{O(1)}.

Then we apply Lemma 14 to obtain a family of boolean circuits of the same size, depth and space–uniformity as above computing the integer a and the polynomials P′_{1}, …, P′_{t+1} of equation (12). Finally, we obtain the polynomials P_{1}, …, P_{s} of equation (13) by computing the linear combinations P_{j} = ∑_{i=1}^{t+1} λ_{ij}P′_{i} for 1 ≤ j ≤ s.

Now we can describe the probabilistic Turing machine M which solves the effective Nullstellensatz problem. This machine M starts guessing the O(n^{2}) integer parameters of logarithmic height O(n log(nsd)) required to perform the preprocessing given by the effective versions of Bertini Theorem and Noether normalization and to apply Propositions 1 and 2 and Lemma 14. Since all these parameters are obtained by applying Schwartz–Zippel test, with the same idea as in the proof of Theorem 1 we can conclude that they can be randomly chosen with probability of success ≫ \frac{1}{2}. These parameters are stored in working space.

Then we evaluate the boolean circuit C which computes the integer a and the polynomials P_{1}, …, P_{s} of equation (13) on input the dense representation of the polynomials F_{1}, …, F_{s}. Recall that the circuit C has size (shh_{1}(nd)^{n})^{O(1)} and depth O(n^{2} log(nd) log(ndshh_{1})), and that there exists a deterministic Turing machine M_{1} computing the standard encoding of C using space O(n^{2} log ndshh_{1}).

Then the machine M evaluates the circuit C following Borodin’s argument in the same way as in the proof of Theorem 1. Therefore, the machine M deterministically evaluates the circuit C using additional space O(n^{2} log(nd) log(nsdhh_{1}))

and time (nd)^{O(n^{2} log(nsdhh_{1}))}.

5.2 The membership and representation problems in the case of complete intersection ideals

Let F, F_{1}, …, F_{t} be polynomials in ZZ[X_{1}, …, X_{n}] such that F_{1}, …, F_{t} form a regular sequence in Q [X_{1}, …, X_{n}]. We assume that the polynomials F_{1}, …, F_{t} and F have degree and logarithmic height bounded by some constants d and h respectively.

The problem we are going to deal with is the decision about the membership of F to the ideal generated by F_{1}, …, F_{t} and its representation in this ideal. That is, we want to determine whether F belongs to the ideal generated by F_{1}, …, F_{t} in Q [X_{1}, …, X_{n}] and, if this is the case, to find polynomials P_{1}, …, P_{t} ∈ ZZ[X_{1}, …, X_{n}] such that the following identity holds:

F = P_{1}F_{1} + ⋯ + P_{t}F_{t}

Theorem 3. There exists a probabilistic Turing machine which, on input the dense representation of polynomials F, F_{1}, …, F_{t} of degree d and logarithmic height h such that F_{1}, …, F_{t} generate a complete intersection ideal, solves the membership and representation problems using space O(n^{3} log(nd) log(ndhh_{1}))

and time (nd)^{O(n^{2} log(ndhh_{1}))}.

Proof. First we produce a change of variables (X_{1}, …, X_{n}) → (Y_{1}, …, Y_{n}) such the variables Y_{1}, …, Y_{n} are in Noether position with respect to the variety V (F_{1}, …, F_{i}) for 1 ≤ i ≤ t. Applying the arguments of [16] or [45], we deduce that the entries of the matrix that performs this linear change of variables can be generated by means of the Schwartz–Zippel test in such a way that their logarithmic height is of order d^{O(n)}.

We study first the membership problem. We observe that F ∈ (F_{1}, …, F_{t}) if and only if the homothesy defined by F in B := Q [Y_{1}, …, Y_{n}]/(F_{1}, …, F_{t}) is the zero endomorphism.

Let R := Q [Y_{1}, …, Y_{n−t}] and let K be the quotient field of R. Applying Proposition 1 we obtain a family of boolean circuits of size (hh_{1}(nd)^{n})^{O(1)} and depth O(n^{2} log(nd) log(ndhh_{1})), which is uniform in space O(n^{2} log dhh_{1}) computing the following polynomials of integers of logarithmic height h_{1}:

• a linear form U := λ_{1}Y_{1} + ⋯ + λ_{n}Y_{n} ∈ ZZ[Y_{1}, …, Y_{n}] such that u := \overline{U} is a primitive element for K ⊗_{R} B.

• a polynomial p ∈ R[T] of degree D bounded by d^{n} such that p(U) belongs to the ideal (F_{1}, …, F_{t}).

• a nonzero element ρ ∈ R and polynomials v_{1}, …, v_{n} ∈ R[T] of degree bounded by D − 1 such that for any 1 ≤ j ≤ n ρY_{j} − v_{j}(U) belongs to (F_{1}, …, F_{t}).

We observe that the resulting integers have logarithmic height bounded by (d^{n}hh_{1})^{O(1)}.

Following the ideas of the proof of Proposition 2 we define τ := α^{D}ρ where α is the leading coefficient of p and compute the matrix M_{F′} of the homothesy by F′ := τ^{d}F with a family of boolean circuits of size (hh_{1}(nd)^{n})^{O(1)} and depth O(n^{2} log(nd) log(ndhh_{1})), which is uniform in space O(n^{2} log dhh_{1}). We remark that the resulting integers have logarithmic height bounded by (d^{n}hh_{1})^{O(1)}. Finally, applying Lemma 6 we obtain a family of boolean circuits computing the rank of this matrix whose size, depth and space–uniformity are the same as above.

Now we can describe the probabilistic Turing machine M which solves the membership problem for complete intersection ideals. This machine M starts guessing the O(n^{2}) integer parameters of logarithmic height O(n log(nd)) required to perform the preprocessing given by the Noether normalization, the application of Proposition 1 and Lemma 6. Since all these parameters are obtained by applying Schwartz–Zippel test, we can conclude that they can be randomly chosen with probability of success ≫ \frac{1}{2}. These parameters are stored in working space.

Then we evaluate the boolean circuit C which computes the rank of the matrix M_{F′} on input the dense representation of the polynomials F, F_{1}, …, F_{t}. Recall that the circuit C has size (hh_{1}(nd)^{n})^{O(1)} and depth O(n^{2} log(nd) log(ndhh_{1})), and that there exists a deterministic Turing machine M_{1} computing the standard encoding of C using space O(n^{2} log dhh_{1}).

Then the machine M evaluates the circuit C following Borodin’s argument in the same way as in the proof of Theorem 1. Therefore, the machine M deterministically evaluates the circuit C using additional space O(n^{2} log(nd) log(ndhh_{1})

and time (nd)^{O(n^{2} log(ndhh_{1}))}. Finally M outputs 1 (=true) if and only if the rank of M_{F′} equals zero.

Once the membership of F to the ideal (F_{1}, …, F_{t}) has been established, the representation of F is performed by the procedure described in the proof of Theorem 2, starting with F instead of the polynomial 1. Therefore, from the bounds of Theorem 2 we deduce the statement in the theorem.

5.3 An effective version of Quillen–Suslin Theorem

A matrix F of ZZ[X_{1}, …, X_{n}]^{r×s} with s ≥ r is called unimodular if the ideal generated in Q [X_{1}, …, X_{n}] by all its minors of size r × r is the trivial ideal Q [X_{1}, …, X_{n}].

Let F := (F_{ij}(X_{1}, …, X_{n}))_{1≤i≤r,1≤j≤s} be a unimodular matrix of

ZZ[X_{1}, …, X_{n}]^{r×s}. Let us denote by deg(F) the maximal degree of all its entries and let d = 1+deg(F). From the Quillen–Suslin theorem (see [50]) we deduce the existence of a unimodular matrix M of size s × s such that F M = [I_{r}, 0] holds, where [I_{r}, 0] denotes the r × s–matrix obtained by adding to the r × r–identity matrix I_{r} s − r zero columns. The problem consists in finding such a matrix M.

Theorem 4. There exists a probabilistic Turing machine which, on input the dense representation of polynomials F_{ij} for 1 ≤ i ≤ r, 1 ≤ j ≤ s of degree d and logarithmic height h such that the matrix F := (F_{ij}(X_{1}, …, X_{n}))_{1≤i≤r,1≤j≤s}

is a unimodular matrix of ZZ[X_{1}, …, X_{n}]^{r×s}, computes a unimodular matrix M of size s × s such that F M = [I_{r}, 0] holds. This Turing machine uses space

O(n^{4} log(rnd) log(sndhh_{1})) and time (sndhh_{1})^{O(n^{2} log(rnd))}.

Proof. The procedure performed in order to compute M is divided in n steps, where n unimodular matrices M_{1}, …, M_{n} of sizes s × s are constructed such that for any 1 ≤ i ≤ n the following condition is satisfied:

F · M_{n} ⋯ M_{i+1} = (F_{ij}(X_{1}, …, X_{i}, 0, …, 0))_{1≤i≤r,1≤j≤s}.

Since the matrix F · M_{1} ⋯ M_{n} is unimodular and has its entries in Q , by means of a standard triangularization procedure the latter can be reduced to the form [I_{r}, 0]. If M_{0} is the (unimodular) matrix that performs this triangularization, M := M_{n} ⋯ M_{0} is the matrix we are looking for.

Let us remark that the matrices (F_{ij}(X_{1}, …, X_{i}, 0, …, 0))_{1≤i≤r,1≤j≤s} can

be produced simultaneously from the input. Hence the computation of the matrices M_{0}, …, M_{n} can be performed in parallel.

Following the scheme proposed in [18] (see also [19]), the procedure for the computation of each matrix M_{i} is divided in four steps. In order to simplify the notations, we will only describe the computation of M_{n}.

In the first step, we construct a sequence c_{1}, …, c_{N} of polynomials of degree bounded by (rd)^{2} such that the following conditions are satisfied:

• 1 ∈ (c_{1}, …, c_{N})

• For every k ∈ {1, …, N}, there exists a nonsingular matrix Λ_{k} ∈ GL_{s}(Q ) such that

c_{k} = Res(det[F_{1}^{(k)}, …, F_{r}^{(k)}], det[F_{1}^{(k)}, …, F_{r−1}^{(k)}, F_{r+1}^{(k)}])

holds. Here F_{1}^{(k)}, …, F_{r+1}^{(k)} are the columns of the matrix F^{(k)} := F · Λ_{k}.

The matrices Λ_{k} have the following form:

Λ_{k} = ( \begin{matrix}1 \\ α_{1} & 1 \\ α_{1}β_{1} & α_{2} \\ α_{1}β_{1}^{2} & α_{2}β_{2} & ... \\ ⋮ & ⋮ & & 1 \\ & & & α_{r−1} & 1 \\ & & & α_{r−1}β_{r−1} & 0 & 1 \\ ⋮ & ⋮ & & ⋮ & ⋮ & α_{r} \\ . & . & . \\ α_{1}β_{1}^{s−2} & α_{2}β_{2}^{s−3} & … & α_{r−1}β_{r−1}^{s−r} & 0 & α_{r}^{s−r−1} & … & 1 \end{matrix} )  (14)

where α_{1}, …, α_{r}, β_{1}, …, β_{r−1} are suitable integers.

The key point is that the polynomials c_{1}, …, c_{N} must generate the trivial ideal. The problem is therefore to find a short sequence (α_{1}^{(k)}, …, α_{r}^{(k)}, β_{1}^{(k)}, …, β_{r−1}^{(k)})_{k=1,...,N} of (2r − 1)–tuples of integers of small logarithmic height such that the algebraic variety defined by the polynomials c_{1}, …, c_{N} is empty.

We consider indeterminates S_{1}, …, S_{r}, T_{1}, …, T_{r−1} and the matrix Λ ∈ ZZ[S_{i}, T_{j}; 1 ≤ i ≤ r, 1 ≤ j ≤ r − 1] obtained by replacing each α_{i} by S_{i} and each β_{j} by T_{j} in the matrix Λ_{k} of (14).

Likewise, we define:

• F′ := [F′_{1}, …, F′_{r+1}] = F · Λ

• D′_{1} := det[F′_{1}, …, F′_{r}]

• D′_{2} := det[F′_{1}, …, F′_{r−1}, F′_{r+1}]

• c := Res_{X_{n}}(D′_{1}, D′_{2})

Applying [18, Proposition 5.6] we see that for every x ∈ C^{n} there exists a vector (α, β) ∈ IN^{2r−1} such that c(x, α, β) ≠ 0 holds. Thus c(x, S_{1}, …, S_{r}, T_{1}, …, T_{r−1}) is a nonzero polynomial of ZZ[S_{i}, T_{j}; 1 ≤ i ≤ r, 1 ≤ j ≤ r − 1] for every x ∈ C^{n}. Furthermore, c(x, S_{1}, …, S_{r}, T_{1}, …, T_{r−1}) can be computed by means of an arithmetic circuit of size O(s^{3}r^{4}(rd)^{2n}) and nonscalar depth O(n log(sd)). Applying the Heintz–Schnorr test we deduce the existence of a correct test sequence of N := O(s^{7}(rd)^{5n}) elements (α^{(k)}, β^{(k)}) ∈ {1, …, m}^{2r−1} for k = 1, …, N, with m := (sd)^{O(n)}, such that for every x ∈ C^{n} there exists an index k ∈ {1, …, N} with c(x, α^{(k)}, β^{(k)}) ≠ 0. Moreover, such a correct test sequence can be generated randomly with probability of success at least 1 − m^{\frac{N}{6}} ≫ \frac{1}{2}.

Let c_{k} := c(X_{1}, …, X_{n}, α^{(k)}, β^{(k)}) for k = 1, …, N. One sees easily that the polynomials c_{1}, …, c_{N} have degree bounded by (rd)^{2} and that their computation requires only the computation of the determinant of O(s^{7}(rd)^{5n}) polynomial r × r–matrices.

In the second step we construct a representation

X_{n} = a_{1}c_{1} + ⋯ + a_{N}c_{N}

of the variable X_{n} in the ideal generated by the polynomials c_{1}, …, c_{N} following the ideas of Subsection 5.1.

In the third step we compute N unimodular matrices M_{n}^{(1)}, …, M_{n}^{(N)} of Q [X_{1}, …, X_{n}]^{s×s} such that, defining for k = 1, …, N the polynomial b_{k} := ∑_{h=1}^{k} a_{h}c_{h}, the following identity holds:

F^{(k)}(b_{k})M_{n}^{(k)} = F^{(k)}(b_{k−1}).  (15)

Here we write F^{(k)} := F · Λ_{k} and F^{(k)}(b_{k}) for the matrix obtained from F^{(k)} by replacing the variable X_{n} by b_{k}.

From identity (15) we deduce that the matrix E_{k} := Λ_{k} · M^{(k)} · Λ_{k}^{−1} satisfies the following property:

F (b_{k})E_{k} = F (b_{k−1})  (16)

Since we have c_{k} = Res_{X_{n}}(D_{1}^{(k)}, D_{2}^{(k)}), there exist polynomials g_{k}, h_{k} ∈ Q [X_{1}, …, X_{n}] such that

c_{k} = g_{k} · D_{1}^{(k)} + h_{k} · D_{2}^{(k)}  (17)

holds. Observing that the polynomial c_{k} does not depend on X_{n}, we deduce that

c_{k} = g_{k}(b_{k}) · D_{1}^{(k)}(b_{k}) + h_{k}(b_{k}) · D_{2}^{(k)}(b_{k})  (18)

holds.

Let F_{j}^{(k)} denote the j–th column of the matrix F^{(k)}. From the proof of [18, Lemma 4.5 ] and the fact that the congruence relation b_{k} ≡ b_{k−1} modulo c_{k} · Q [X_{1}, …, X_{n}] holds, we deduce by means of the Taylor expansion of the entries of F_{j}^{(k)} the existence of a column vector G_{j}^{(k)} ∈ Q [X_{1}, …, X_{n}]^{r×1} which satisfies the condition

F_{j}^{(k)}(b_{k}) − F_{j}^{(k)}(b_{k−1}) = c_{k}G_{j}^{(k)}.  (19)

Combining (18) and (19) we obtain the following identity:

F_{j}^{(k)}(b_{k}) − F_{j}^{(k)}(b_{k−1}) = D_{1}^{(k)}(g_{k}(b_{k})G_{j}^{(k)}) + D_{2}^{(k)}(h_{k}(b_{k})G_{j}^{(k)}).  (20)

Let B_{1}^{(k)} and B_{2}^{(k)} be the following matrices:

B_{1}^{(k)} := Adj[F_{1}^{(k)}(b_{k}), …, F_{r}^{(k)}(b_{k})]  (21)
B_{2}^{(k)} := Adj[F_{1}^{(k)}(b_{k}), …, F_{r−1}^{(k)}(b_{k}), F_{r+1}^{(k)}(b_{k})]  (22)

Then we have the following identities:

D_{1}^{(k)}(b_{k})g_{k}(b_{k})G_{j}^{(k)} = [F_{1}^{(k)}(b_{k}), …, F_{r}^{(k)}(b_{k})]B_{1}^{(k)}g_{k}(b_{k})G_{j}^{(k)} := ∑_{j=1}^{r} η_{j}F_{j}^{(k)}(b_{k})

\begin{matrix}D_{2}^{(k)}(b_{k})h_{k}(b_{k})G_{j}^{(k)} = [F_{1}^{(k)}(b_{k}), …, F_{r−1}^{(k)}(b_{k}), F_{r+1}^{(k)}(b_{k})]B_{2}^{(k)}h_{k}(b_{k})G_{j}^{(k)} \\ := ∑_{j≠r} η̃_{j}F_{j}^{(k)}(b_{k}) \end{matrix}

where (η_{1}, ..., η_{r})^{t}:= B_{1}^{(k)}g_{k}(b_{k})G_{j}^{(k)} and (η̃_{1}, ..., η̃_{r−1}, η̃_{r+1})^{t}:= B_{2}^{(k)}h_{k}(b_{k})G_{j}^{(k)}. Applying these identities to (20) we obtain the following equation for j = r + 2, …, s:

F_{j}^{(k)}(b_{k}) − F_{j}^{(k)}(b_{k−1}) = (η_{1} + η̃_{1})F_{1}^{(k)}(b_{k}) + ⋯ + η_{r}F_{r}^{(k)}(b_{k}) + η̃_{r+1}F_{r+1}^{(k)}(b_{k})

From these equations we construct a unimodular matrix M̃^{(k)} such that

F^{(k)}(b_{k})M̃^{(k)} = [F_{1}^{(k)}(b_{k}), …, F_{r+1}^{(k)}(b_{k}), F_{r+2}^{(k)}(b_{k−1}), …, F_{s}^{(k)}(b_{k−1})]

holds.

In order to finish the construction of the matrix M^{(k)}, we define the following (r + 1) × (r + 1) unimodular matrix T^{(k)}:

\begin{matrix}T^{(k)} := \frac{1}{c_{k}} Adj ( \begin{matrix}F_{1}^{(k)}(b_{k}) & … & F_{r}^{(k)}(b_{k}) & F_{r+1}^{(k)}(b_{k}) \\ 0 & … & −h_{k}(b_{k}) & g_{k}(b_{k}) \end{matrix} ) · \\ · ( \begin{matrix}F_{1}^{(k)}(b_{k−1}) & … & F_{r}^{(k)}(b_{k−1}) & F_{r+1}^{(k)}(b_{k−1}) \\ 0 & … & −h_{k}(b_{k−1}) & g_{k}(b_{k−1}) \end{matrix} ) \end{matrix}

Then, M^{(k)} := M̃^{(k)} · (T^{(k)} ⊕ I_{s−r−1}) is the matrix we are looking for.

Finally in the fourth step we compute the product M_{n} := ∏_{k=1}^{N} E_{k} = ∏_{k=1}^{N} Λ_{k}M^{(k)}Λ_{k}^{−1}. From the identities:

F = F (X_{n}) = F (b_{N})
F (b_{N})E_{n} = F (b_{N−1})
⋮
F (b_{1})E_{1} = F (b_{0}) = F (0)

we deduce that the matrix M_{n} satisfies the required conditions.

After n parallel steps like the one described above, we obtain an algorithm which computes the matrix M we are looking for.

We now analyze the algorithm described above in order to prove that it can be performed by a family of boolean circuits with size (shh_{1}(rnd)^{n})^{O(1)} and depth O(n^{2} log(rnd) log(sndhh_{1})), which is uniform in space O(n^{2} log ndshh_{1}). We assume that we are given the dense representation of the polynomials (F_{ij})_{1≤i≤r,1≤j≤s} and a sequence of (α^{(k)}, β^{(k)})_{1≤k≤N} of (2r − 1)–tuples of integers of logarithmic height bounded by O(n log sd) which define a correct test sequence in the sense of Heintz–Schnorr of length N := (s(rd)^{n})^{O(1)} elements.

We first observe that there exists a family of boolean circuits computing the polynomials F_{ij} on integers of logarithmic height h_{1} with size rs(hh_{1}d^{n})^{O(1)} and depth O((n + log d) log dhh_{1}), which is uniform in space O(n log dhh_{1}). We remark that the resulting integers have logarithmic height O(h + dh_{1} + n log d).

We also compute the matrices Λ_{k} for 1 ≤ k ≤ N by means of a family of boolean circuits of size (sn(rd)^{n} log d)^{O(1)} and depth O( log(s) log(snd)), which is uniform in space O(n log sdn). The resulting integers have logarithmic height O(sn log sd).

Then we compute the matrix product F^{(k)} = [F_{1}^{(k)}, …, F_{r+1}^{(k)}] := F · Λ_{k}, the determinants D_{1}^{(k)} := det[F_{1}^{(k)}, …, F_{r}^{(k)}] and D_{2}^{(k)} := det[F_{1}^{(k)}, …, F_{r−1}^{(k)}, F_{r+1}^{(k)}] and the resultant c_{k} := Res_{X_{n}}(D_{1}^{(k)}, D_{2}^{(k)}) for 1 ≤ k ≤ N. Taking into account that the entries of the matrix F^{(k)} have logarithmic height O(h + dh_{1} + sn log sd), the polynomials D_{1}^{(k)}, D_{2}^{(k)} have degree (rd)^{2} and logarithmic height O(rh + rdh_{1} + rsn log sd) on integers of logarithmic height h_{1}, and that the coefficients which result from the interpolation of D_{1}^{(k)}, D_{2}^{(k)} with respect to X_{n} have logarithmic height (sdhh_{1}n)^{O(1)} on integers of logarithmic height h_{1}, combining the Macro expansion lemma with Lemmata 3, 5 and 12 we deduce that there exists a family of boolean circuits computing the polynomial c_{k} for 1 ≤ k ≤ N on integers of logarithmic height h_{1} with size shh_{1}(rd)^{O(n)} and depth O( log(rd) log(sndhh_{1})), which is uniform in space O(n log sndhh_{1}). These polynomials have logarithmic height (sdhh_{1}n)^{O(1)} on integers of logarithmic height h_{1}.

Applying the ideas of the proof of Theorem 2 we obtain a family of boolean circuits computing polynomials a_{1}, …, a_{N} ∈ ZZ[X_{1}, …, X_{N}] on integers of logarithmic height h_{1} and a nonzero integer γ such that the following equation holds:

γX_{n} = a_{1}c_{1} + ⋯ a_{N}c_{N}

This family of boolean circuits has size (shh_{1}(rnd)^{n})^{O(1)} and depth O(n^{2} log(rnd) log(sndhh_{1})) and is uniform in space O(n^{2} log ndshh_{1}). We remark that the re-

sulting integers have logarithmic height bounded by (shh_{1}(rd)^{n})^{O(1)}.

Then we compute the matrix M_{n}^{(k)} of equation (15) for 1 ≤ k ≤ N. For this purpose we first compute the polynomials g_{k}, h_{k} of equation (17) applying the ideas of Lemma 10 and then we evaluate them in X_{n} = b_{k} applying Lemma 2. Then we compute the vectors G_{j}^{(k)} of equation (19) and the matrices B_{1}^{(k)}, B_{2}^{(k)} of equations (21) and (22) for 1 ≤ k ≤ N, applying Lemma 7. We compute the product B_{1}^{(k)}g_{k}(b_{k})G_{j}^{(k)} and B_{2}^{(k)}h_{k}(b_{k})G_{j}^{(k)} for 1 ≤ k ≤ N applying Lemma 3, the matrix T^{(k)} for 1 ≤ k ≤ N applying Lemmata 7 and 3 and finally the matrix M_{n}^{(k)} we are looking for. We observe that the integers involved in these computations have logarithmic height bounded by (shh_{1}(rd)^{n})^{O(1)}. Therefore, combining the Macro expansion lemma with Lemmata 10, 2, 7 and 3 we obtain a family of boolean circuits computing the matrix M_{n}^{(k)} for 1 ≤ k ≤ N with size (shh_{1}(rnd)^{n})^{O(1)} and depth O(n^{2} log(rnd) log(sndhh_{1})), which is uniform in space O(n^{2} log ndshh_{1}).

Finally, a combination of Lemmata 7 and 3 yields a family of boolean circuits computing the matrix M_{n} with size, depth and space–uniformity as above. A final multiplication of the matrices M_{n}, …, M_{0} yields the unimodular matrix M we are looking for. As a consequence of the bounds for the complexity of the computation of the matrices M_{0}, …, M_{n}, we deduce that there exists a family of boolean circuits computing the matrix M with size (shh_{1}(rnd)^{n})^{O(1)} and depth O(n^{2} log(rnd) log(sndhh_{1})), which is uniform in space O(n^{2} log ndshh_{1}).

Now we can describe the probabilistic Turing machine T of the statement of the theorem. This machine T starts guessing the O(n^{2}) integer parameters of logarithmic height O(n^{2} log(nsd)) required to apply the ideas of Theorem 2. Since all these parameters are obtained by applying Schwartz–Zippel test, we can conclude that they can be randomly chosen with probability of success ≫ \frac{1}{2}. These parameters are stored in working space.

Then we evaluate the boolean circuit C which computes the matrix M on input the dense representation of the polynomials F_{ij} for 1 ≤ i ≤ r, 1 ≤ j ≤ s. Recall that the circuit C has size (shh_{1}(rnd)^{n})^{O(1)} and depth O(n^{2} log(rnd) log(sndhh_{1})), and that there exists a deterministic Turing machine M_{1} computing the standard encoding of C using space O(n^{2} log ndshh_{1}).

Then the machine M evaluates the circuit C following Borodin’s argument in the same way as in the proof of Theorem 1. Therefore, the machine M deterministically evaluates the circuit C using only additional space O(n^{2} log(rnd)

log(sndhh_{1})) and time (sndhh_{1})^{O(n^{2} log(rnd))}.

References

1. M. Aldaz, J. Heintz, G. Matera, J. L. Montaña, and L. M. Pardo. Time-Space Tradeoffs in algebraic complexity theory. To appear in Journal of Complexity,

1999. http://hilbert.matesco.unican.es/tera/pub97.html

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

3. J. Balcázar, J. Díaz, and J. Gabarró. Structural complexity II , vol. 22 of EATCS. Springer, 1990.

4. J. L. Balcázar, J. Díaz, and J. Gabarró. Structural complexity I , vol. 11 of EATCS. Springer, 1988.

5. E. Becker, J. P. Cardinal, M. F. Roy, and Z. Szafraniec. Multivariate Bezoutians, Kronecker symbol and Eisenbud-Levine formula. In Algorithms in Algebraic Geometry and Applications. Proceedings of MEGA’94 , vol. 142 of Progress in Mathematics, pp. 79–104. Birkhäuser, 1996.

6. S. J. Berkowitz. On Computing the determinant in small parallel time using a small number of processors. Information Processing Letters, vol. 18:pp. 147–150, 1984.

7. A. Borodin. On Relating Time and Space to Size and Depth. SIAM J. on Comp., vol. 6:pp. 733–744, 1977.

8. A. Borodin, J. von zur Gathen, and J. Hopcroft. Fast parallel matrix and gcd computations. In Proceedings 23rd. Ann. Symp. FOCS, pp. 65–71. 1982.

9. J. Briancon. Sur le degré des relations entre polynomes. C. R. Acad. Sc. Paris, vol. 297:pp. 553–556, 1982.

10. W. Brown and J. Traub. On Euclid’s algorithm and the theory of subresultants. Journal of the Association for Computing Machinery, vol. 18:pp. 505–514, 1971.

11. J. Canny. Some algebraic and geometric problems in PSPACE. In Proceedings 20th. ACM STOC , pp. 460–467. 1988.

12. J. P. Cardinal. Dualité et algorithmes itératives pour la solution des systéms polynomiaux. Ph.D. thesis, Université de Rennes I, France, 1993.

13. A. L. Chistov. Polynomial time computation of the dimension of components of algebraic varieties in zero-characteristic. Preprint Université Paris Val de Marne.

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

15. G. Collins. Subresultants and reduced polynomial sequences. Journal of the Association for Computing Machinery, vol. 14:pp. 128–142, 1967.

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

17. T. W. Dubé. The structure of polynomial ideals and Gröbner bases. SIAM Journal on Computing, vol. 19 (4):pp. 750–775, August 1990.

18. N. Fitchas. Algorithmic aspects of Suslin’s solution of Serre’s Conjecture. Computational Complexity, vol. 3:pp. 31–55, 1993.

19. N. Fitchas and A. Galligo. Nullstellensatz effectif et Conjecture de Serre (Théorème de Quillen-Suslin) pour le Calcul Formel. Math. Nachr., vol. 149:pp. 231–253, 1990.

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

21. S. Fortune and J. Wyllis. Parallelism in random access machines. In Proceedings of the 10th Ann. ACM Symposium on Theory of Computing, pp. 114–118. ACM, ACM Press, New York, 1978.

22. J. von zur Gathen. Parallel arithmetic computations: a survey. In B. R. J. Gruska and J. Wiedermann, eds., Proceedings of the 12th Symposium on Mathematical Foundations of Computer Science, vol. 233 of LNCS, pp. 93–112. Springer, Bratislava, Czechoslovakia, August 1986.

23. J. von zur Gathen. Parallel Linear Algebra. In J. H. Reif, ed., Synthesis of Parallel Algorithms. Morgan Kaufmann, 1993.

24. P. Gianni and T. Mora. Algebraic Solution of systems of polynomial equations using Gröbner bases. In Proceedings AAECC-5 , vol. 356 of LNCS, pp. 247–257. Springer, 1989.

25. M. Giusti. Some effectivity problems in polynomial ideal theory. In J. Fitch, ed., Proceedings of the 3rd International Symposium on Symbolic and Algebraic Computation EUROSAM 84 (Cambridge, England, July 9-11, 1984), vol. 174 of LNCS, pp. 159–171. ACM SIGSAM, SAME, Springer-Verlag, Berlin-Heidelberg-New York-London-Paris-Tokyo-Hong Kong, 1984.

26. M. Giusti, K. Hägele, J. Heintz, J. E. Morais, J. L. Montaña, and L. M. Pardo. Lower Bounds for Diophantine Approximation. In Proceedings of MEGA’96 , vol. 117,118, pp. 277–317. Journal of Pure and Applied Algebra, 1997.

27. 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 T. Mora and C. Traverso, eds., Proceedings of MEGA’90 , vol. 94 of Progress in Mathematics, pp. 169–194. Birkhäuser, 1991.

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

29. M. Giusti, J. Heintz, J. E. Morais, J. Morgenstern, and L. M. Pardo. Straight–Line Programs In Geometric Elimination Theory. Journal of Pure and Applied Algebra, vol. 124:pp. 101–146, 1998.

30. M. Giusti, J. Heintz, J. E. Morais, and L. M. Pardo. When Polynomial Equation Systems can be solved fast ? In G. Cohen, H. Giusti, and T. Mora, eds., Applied Algebra, Algebraic Algorithms and Error Correcting Codes, Proceedings AAECC-11 , vol. 948 of LNCS, pp. 205–231. Springer, 1995.

31. M. Giusti, J. Heintz, J. E. Morais, and L. M. Pardo. Le rôle des structures de données dans les problèmes d’élimination. Comptes Rendus de l’Academie de Sciences de Paris, vol. 325:pp. 1223–1228, 1997.

32. M. Giusti, J. Heintz, and J. Sabia. On the Efficiency of effective Nullstellensätze. Computational Complexity, vol. 3:pp. 56–95, 1993.

33. A. Grosso, N. Herrera, G. Matera, M. E. Stefanoni, and J. M. Turull. Un algoritmo para el cálculo del rango de matrices enteras en espacio polilogarítmico. In Proceedings 25th Jornadas Argentinas de Informática e Investigación Operativa,

JAIIO’96 . 1996. http://hilbert.matesco.unican.es/tera/pub96.html.

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

35. J. Heintz and J. Morgenstern. On the intrinsic complexity of elimination theory. J. of Complexity, vol. 9:pp. 471–498, 1993.

36. J. Heintz and C. P. Schnorr. Testing Polynomials which are easy to compute. In Logic and Algorithmic, vol. 30 of Monographie de l’Enseignement Mathématique, pp. 237–254. 1982.

37. O. H. Ibarra and S. Moran. Equivalence of Straight-line Programs. Journal of the ACM , vol. 30:pp. 217–228, 1983.

38. O. H. Ibarra, S. Moran, and L. E. Rosier. Probabilistic Algorithms and Straightline Programs for some rank decision problems. Information Processing Letters, vol. 12 (5):pp. 227–232, 1981.

39. B. Iversen. Generic local structure of the morphisms in Commutative Algebra, vol. 310 of LNM . Springer, 1973.

40. J. P. Jouanolou. Théorèmes de Bertini et applications. Progress in Mathematics. Birkhäuser Verlag, 1983.

41. E. Kaltofen. Greatest Common Divisors of Polynomials Given by Straight-Line Programs. Journal of the ACM , vol. 35 (1):pp. 231–264, January 1988.

42. R. Karp and V. Ramachandran. Parallel algorithms for shared–memory machines. In Handbook of Theoretical Computer Science, pp. 871–941. Elsevier Science Publishers, 1990.

43. H. Kobayashi, T. Fujise, and A. Furukawa. Solving systems of algebraic equations by general elimination method. J. of Symb. Comp., vol. 5:pp. 303–320, 1988.

44. T. Krick and A. Logar. Membership Problems, Representation problems and the Computation of the Radical for one-dimensional Ideals. In T. Mora and C. Traverso, eds., Effective Methods in Algebraic Geometry, vol. 94 of Progress in Mathematics, pp. 203–216. Birkhäuser, 1991.

45. T. Krick and L. M. Pardo. A Computational Method for Diophantine Approximation. In L. González-Vega and T. Recio, eds., Algorithms in Algebraic Geometry and Applications. Proceedings of MEGA’94 , vol. 143 of Progress in Mathematics, pp. 193–254. Birkhäuser Verlag, 1996.

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

47. K. Kühnle and E. Mayr. Exponential space computation of Gröbner bases. In Proceedings of the 1996 International Symposium on Symbolic and Algebraic Computation, ISSAC’96 (Zürich, 24–26 July 1996), vol. 358 of ACM Press, pp. 63–71. ACM, New York, 1996.

48. E. Kunz. Kähler Differentials. Advanced Lectures in Mathematics. Vieweg Verlag, 1986.

49. Y. N. Lakshman and D. Lazard. On the complexity of zero-dimensional algebraic systems. In Effective methods in algebraic geometry, vol. 94 of Progress in Mathematics, pp. 217–225. Birkhäuser, 1991.

50. T. Y. Lam. Serre’s Conjecture, vol. 635 of LNM . Springer, 1978.

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

52. G. Matera. Sobre la complejidad en espacio y tiempo de la eliminación geométrica. Ph.D. thesis, Universidad de Buenos Aires, Argentina, 1997.

53. G. Matera and J. M. T. Torres. The Space Complexity of Elimination: Upper Bounds. In F.Cucker and M.Shub, eds., Proceedings Foundations of Computational Mathematics (FOCM’97), pp. 267–276. Springer, 1997.

54. E. Mayr. Membership in Polynomial Ideals over Q is Exponential Space Complete. In B. Monien et al, ed., Proceedings of the 6th Annual Symposium on Theoretical Aspects of Computer Science (STACS’89), Paderborn (FRG) 1989 , number 349 in Lecture Notes in Computer Science, pp. 400–406. Springer, 1989.

55. E. Mayr. Some complexity results for polynomial ideals. Journal of Complexity 13, 303–325 (1997).

56. M. Moeller. Systems of algebraic equations solved by means of endomorphisms. In Proceedings of AAECC-10 , volume 673 of LNCS, 43–56. Springer, 1993.

57. J. E. Morais. Resolución eficaz de sistemas de ecuaciones polinomiales. Ph.D. thesis, Universidad de Cantabria, Santander, Spain, 1997.

58. L. M. Pardo. How lower and upper complexity bounds meet in elimination theory. In G. Cohen, H. Giusti, and T. Mora, eds., Applied Algebra, Algebraic Algorithms and Error Correcting Codes. Proceedings of AAECC-11 , vol. 948 of LNCS. Springer, 1995.

59. J. Sabia and P. Solernó. Bounds for Traces in Complete Intersections and Degrees in the Nullstellensatz. Applicable Algebra in Engineering Communications and Computing (AAECC Journal), vol. 6:pp. 353–376, 1996.

60. J. T. Schwartz. Fast Probabilistic Algorithms for Verification of Polynomial Identities. Journal of the ACM , vol. 27 (4):pp. 701–717, October 1980.

61. M. Sombra. Bounds for the Hilbert function of polynomial ideal and for the degrees in the Nullstellensatz. In Proceedings of MEGA’96 . Journal of Pure and Applied Algebra 117,118, 565–599 (1997).

62. V. Strassen. Vermeidung von Divisionen. Crelle J. Reine Angew. Math,, vol. 264:pp. 182–202, 1973.

63. I. Wegener. The complexity of boolean functions. Series in Computer Science. Wiley-Teubner, 1987.

64. R. Zippel. Probabilistic algorithms for sparse polynomials. In Proceedings EU-ROSAM’ 79 , vol. 72 of LNCS, pp. 216–226. 1979.