On the time–space complexity of geometric elimination procedures

Joos Heintz^{1,2}  Guillermo Matera^{3,4}  Ariel Waissbein^{2}

1 Departamento de Matemáticas, Estadística y Computación, Facultad de Ciencias, Universidad de Cantabria, E–39071 Santander, España heintz@matesco.unican.es 2 Departamento de Matemáticas, Universidad de Buenos Aires, Ciudad Universitaria, Pab. I (1428) Buenos Aires, Argentina joos,awaissbe@dm.uba.ar 3 Laboratorio de Computación, Universidad Favaloro, Solís 453 (1078) Buenos Aires, Ar-

gentina gmatera@dm.uba.ar

4 Instituto de Desarrollo Humano, Univ. Nac. de Gral. Sarmiento, Roca 850 (1663) San Miguel, Buenos Aires, Argentina gmatera@ungs.edu.ar

Abstract

In [GHM^{+}98] and [GHH^{+}97] a new algorithmic concept was introduced for the symbolic solution of a zero dimensional complete intersection polynomial equation system satisfying a certain generic smoothness condition. The main innovative point of this algorithmic concept consists in the introduction of a new geometric invariant, called the degree of the input system, and the proof that the most common elimination problems have time complexity which is polynomial in this degree and the length of the input.

In this paper we apply this algorithmic concept in order to exhibit an elimination procedure whose space complexity is only quadratic and its time complexity is only cubic in the degree of the input system.

Research was partially supported by the following Argentinian, German and Spanish grants : UBA–CYT TW80, PIP CONICET 4571, ANPCYT PICT 03–00000–01593, DG-ICYT PB96–0671–C02–02, INF. 2/98/OG.

1 Introduction

The development of efficient algorithms for real–life purposes often requires the optimization of more than one resource at the same time. The two most significant resources for practical computing issues are memory space and running time. Generally, these two resources can not be minimized simultaneously (independently from each other), as they are linked by a time–space tradeoff function which is intrinsic to the problem treated. Our goal here is to analyze the intrinsic time–space complexity of multivariate polynomial elimination problems.

It is well known that algorithmic multivariate polynomial elimination faces serious complexity problems. As it was shown by E. Mayr and A. Meyer in [MM82], the typical algebraic elimination problems are computationally infeasible since they are EXPSPACE–complete (see also [May89], [KM96] and [Küh98]).

This fact is reflected by the complexity behaviour of the currently available software on the subject, mainly based on Gröbner basis computations (see [Buc85]). The typical symptoms which can be observed when confronting these software packages with realistically sized problems are out–of–memory errors.

This observation suggests to search for efficient geometric elimination procedures which may replace the known algebraic ones. This suggestion is also supported by the fact that all the most classical geometric elimination problems belong to the complexity class PSPACE (see [Can88], [CGH89], [DFGS91], [GH93], [MT97], [Mat97b]).

On the other hand the limitation to geometric problems and algorithms does not suffice to settle the practical complexity issue of elimination. This is due to the impossibility to design general purpose elimination algorithms with polynomial time (and space) behaviour which are based on the classical dense encoding of multivariate polynomials. A well-known example due to D. Lazard, T. Mora, W. Masser and P. Philippon (see [Bro87]) shows that exponential time behaviour is unavoidable while using dense representation of polynomials.

From these observations we infer the necessity of using alternative data structures for the representation of multivariate polynomials. One such possibility is the encoding by arithmetic circuits and their related evaluation schemes or straight–line programs (see [Par95]).

Although geometric elimination algorithms based on straight–line program (SLP) encoding of multivariate polynomials improve drastically the complexity behaviour of their forerunner based on dense encoding (see [GH93], [GHS93], [FGS95], [KP94] or [KP96]), the complexity issue remains still unsatisfactory. From the main result of [HMPW98] one deduces that any general purpose elimination algorithm based on SLP –encoding of polynomials must necessarily have an exponential time complexity behaviour on infinitely many examples, provided the SLP representing the input polynomials is treated as a black box by the algorithm.

This insight leads in [GHMP95], [GHM^{+}98], [GHH^{+}97] and [GHMP97] to the consideration of a new intrinsic geometric invariant, associated to the input equation system, namely its geometric degree (see also [Mat97a], [Mor97], [Häg98], [HMPS99], [HKP^{+}98]). The new outcome consists in the conclusion that elimination has polynomial time character in the (syntactical) size of the input equation system (given by a straight–line program program or in sparse representation) and the (geometric) degree of the input system. Of course, this degree may be of exponential size in the number of variables to be eliminated (it is bounded by the Bezout number of the input system), but in case that this degree is considerably smaller than the Bézout number, the new algorithmic concept introduced in [GHM^{+}98] and [GHH^{+}97] becomes of practical interest. The main outcome of the mentioned work is the observation that elimination polynomials have only “small” circuit complexity. In fact, such a polynomial can be evaluated by a straight–line program whose length is roughly of the same order as its degree, even if the polynomial under consideration contains many variables. By the way, the classical elimination procedure of Kronecker [Kro82] is reinvidicated by this work as the most powerful and efficient algorithm of all the times, although it received in the past a lot of negative criticism (see e.g. [Mac16], [Van30]).

This was the starting point for the ongoing work of the TERA^{1}(=Turbo Evaluation and Rapid Algorithms) group on highly performant algorithms and computer programs in order to design an efficient solver for polynomial equation and inequality systems over the complex and real numbers (see [BGHM97] for progress in the real case).

These pages will be devoted to the design of an elimination algorithm which realizes the algorithmic concepts developed in [GHM^{+}98] and [GHH^{+}97] from a time–space tradeoff point of view. At the beginning we deduce, based on a result of J. Ja’Ja’ [Ja’83], that the algorithmic concepts of [GHM^{+}98] and [GHH^{+}97] cannot be realized using sublinear space without causing a superpolynomial growth of the time–space tradeoff complexity.

Then, following Schönhage’s Golden rule number 1: Do care about the constants! [SGV94], we develop an elimination algorithm which has quadratic space and cubic time complexity bounds (in terms of the geometric degree of the input system). For this purpose we design a series of new algorithms for classical linear algebra tasks, for the manipulation of univariate polynomials and an effective Shape Lemma version which is particularly adapted to the special features of the main algorithm of [GHM^{+}98] and [GHH^{+}97].

1Europe: http://hilbert.matesco.unican.es/tera/ America: http://www.dm.uba.ar/tera/

1.1 Notations, assumptions and statement of the main result

Let X_{1}, …, X_{n} be indeterminates over the rational numbers Q and let Q[X_{1}, …, X_{n}] denote the ring of n–variate polynomials over Q . Let d be a natural number and let be given polynomials F_{1}, …, F_{n} ∈ Q [X_{1}, …, X_{n}] of degree at most d. Assume that F_{1}, …, F_{n} define a regular sequence in Q [X_{1}, …, X_{n}]. Assume also that for 1 ≤ r ≤ n − 1 the polynomials F_{1}, …, F_{r} span a radical ideal over Q [X_{1}, …, X_{n}] and denote by V_{r} the equidimensional algebraic variety V (F_{1}, …, F_{r}) defined by F_{1}, …, F_{r} in the complex n–dimensional affine space C^{n}. Finally we assume that there is given a division–free straight–line program in Q [X_{1}, …, X_{n}] evaluating the polynomials F_{1}, …, F_{n} in space S and time T .

In the sequel we shall consider algorithms which “solve” symbolically the (input) equation system F_{1} = 0, …, F_{n} = 0 over the complex numbers C. As in [GHM^{+}98] and [GHH^{+}97] we associate to the equation system F_{1} = 0, …, F_{n} = 0 a parameter δ, called the geometric degree of the system, which is defined as follows: for 1 ≤ r ≤ n let deg(V_{r}) denote the (geometric) degree of V_{r}, as introduced in [Hei83]. The geometric degree of F_{1} = 0, …, F_{n} = 0 is then defined as

δ := max_{1≤r≤n} deg(V_{r}).

In order to describe the geometric aspect of our procedure we need some more terminology, essentially borrowed from [GHH^{+}97]. Let 2 ≤ r ≤ n and let us consider the (n − r)–dimensional Q –definable closed affine subvariety V := V_{r} of C^{n}. A geometric solution of the algebraic variety V consists of the following items:

• a Q –linear change of variables, transforming the variables X_{1}, …, X_{n} into new ones, namely Y_{1}, …, Y_{n}, such that the linear map from C^{n} to C^{n−r} defined by the forms Y_{1}, …, Y_{n−r} induces a finite surjective morphism of affine varieties π : V → C^{n−r}. Such a transformation of variables is called a Noether normalization of the variety V and we say that the variables Y_{1}, …, Y_{n} are in Noether position with respect to V, the variables Y_{1}, …, Y_{n−r} being free. The given Noether normalization induces an integral ring extension R := Q [Y_{1}, …, Y_{n−r}] ⟶ Q [V] (where Q [V] denotes the coordinate ring of the variety V). Observe that Q [V] is a free R–module whose rank we denote by rank_{R}Q [V]. Notice that rank_{R}Q [V] ≤ deg V (see e.g. [GHS93]) and Q [V] = Q [X_{1}, …, X_{n}]/(F_{1}, …, F_{n}) holds.

• a Q –linear form U := λ_{n−r+1}Y_{n−r+1} + ⋯ + λ_{n}Y_{n} which induces a primitive element of the ring extension R ⟶ Q [V], i.e. an element u of the coordinate ring Q [V] whose (monic) minimal polynomial q ∈ R[T] over R satisfies the condition deg_{T} q = rank_{R}Q [V] (here T is a new indeterminate and deg_{T} q denotes the partial degree of th polynomial q ∈ R[T] = Q [Y_{1}, …, Y_{n−r}][T] with respect to the variable T). Observe here that we always have deg q = deg_{T} q ≤ deg V with deg q denoting the total degree of q.

• the minimal polynomial q of u over R.

• a generic “parametrization” of the variety V by the zeroes of q, given by polynomials of the form ρ_{n−r+1}^{(u)}Y_{n−r+1} − v_{n−r+1}^{(u)}(T), …, ρ_{n}^{(u)}Y_{n} − v_{n}^{(u)}(T) with ρ_{n−r+1}^{(u)}, …, ρ_{n}^{(u)} ∈ R \ {0} and v_{1}^{(u)}, …, v_{n}^{(u)} ∈ R[T]. We require that max{deg_{T} v_{n−r+1}^{(u)}, …, deg_{T} v_{n}^{(u)}} < deg_{T} (q) and ρ_{n−r+j}^{(u)}Y_{n−r+j} − v_{n−r+j}^{(u)}(T) ∈ I(V) holds for 1 ≤ j ≤ r (here I(V) denotes the vanishing ideal of V, namely I(V) = (F_{1}, …, F_{r})). Observe that this parametrization is unique up to scaling with nonzero elements of Q .

Let us remark here that this notion of “geometric solution” has a long history, which goes back at least to L. Kronecker [Kro82] (see also [Mac16], [Zar95]). One might consider [CG83] and [GM89] as early references where this notion was implicitly used for the first time in modern symbolic computation.

Given a Noether normalization of the variety V as before, we call a point P := (p_{1}, …, p_{n−r}) ∈ ZZ^{n−r} a lifting point of V if the finite surjective morphism π : V → C^{n−r} is unramified in P, i.e. if the equations F_{1} = 0, …, F_{n} = 0, Y_{1} = p_{1}, …, Y_{n−r} = p_{n−r} define the fiber π^{−1}(P) by transversal cuts. We call the zero–dimensional variety V_{P} := π^{−1}(P) the lifting fiber of the point P.

Assume now that there is given as before a geometric solution of the (n − r)– dimensional variety V and a lifting point P satisfying the condition ρ_{n−r+1}(P) ≠ 0, …, ρ_{n}(P) ≠ 0 and discr_{T} q(P) ≠ 0, where discr_{T} q denotes the discriminant of the polynomial q with respect to the variable T. Then the given geometric solution of the variety V induces a geometric solution of the lifting fiber V_{P}. The geometric solution of V_{P} is given by the linear form U, the polynomial q(P, T) ∈ Q[T] and the parametrization ρ_{n−r+1}(P)Y_{n−r+1} − v_{n−r+1}^{(u)}(P, T), …, ρ_{n}(P)Y_{n} − v_{n}^{(u)}(P, T) (observe that all these entities are well defined because Q [V] ≅ Q [X_{1}, …, X_{n}]/(F_{1}, …, F_{r}) is a free R–module and because of our requirement ρ_{n−r+1}(P) ≠ 0, …, ρ_{n}(P) ≠ 0). We call such a geometric solution of the variety V compatible with the lifting point P.

Let us denote by F_{1}(Y_{1}, …, Y_{n}), …, F_{n}(Y_{1}, …, Y_{n}) the elements of the polynomial ring Q [Y_{1}, …, Y_{n}] we obtain if we rewrite the polynomials F_{1}(X_{1}, …, X_{n}), …, F_{n}(X_{1}, …, X_{n}) in the variables Y_{1}, …, Y_{n}. Observe then that the unramifiedness of π in the lifting point P means that (F_{1}(P, Y_{n−r}, …, Y_{n}), …, F_{n}(P, Y_{n−r}, …, Y_{n})) is a radical ideal of Q [Y_{n−r+1}, …, Y_{n}] which is equivalent to saying that

Q [V_{P}] ≅ Q [Y_{n−r+1}, …, Y_{n}]/ (F_{1}(P, Y_{n−r}, …, Y_{n}), …, F_{n}(P, Y_{n−r}, …, Y_{n}))

holds.

The complexity of the procedure that we are going to design for the resolution of the system F_{1} = 0, …, F_{n} = 0 will be described in terms of the following syntactic and geometric parameters:

• n, the number of variables,

• d, the maximum of the degrees of the polynomials F_{1}, …, F_{n},

• S and T , the space and time complexity of the given straight–line program in Q [X_{1}, …, X_{n}] which evaluates the polynomials F_{1}, …, F_{n},

• the geometric degree δ of the input system F_{1} = 0, …, F_{n} = 0.

The algorithmic method proposed in [GHM^{+}98] and [GHH^{+}97] proceeds in n − 1 stages, computing at each stage 2 ≤ r ≤ n a suitable lifting point P^{(r)} ∈ ZZ^{n−r} and a geometric solution of the lifting fiber V_{P^{(r)}} := (V_{r})_{P^{(r)}} associated to the lifting point P^{(r)} and the variety V_{r}. Then a geometric solution of the variety V_{r} is (re)constructed from the lifting fiber V_{P^{(r)}} and the straight–line program representing the input polynomials F_{1}, …, F_{r}. For this purpose the idea of a division–free symbolic version of the Newton–Hensel algorithm is used. Then a Noether normalization of the variety V_{r+1} and a new lifting point P^{(r+1)} for V_{r+1} are determined. Finally a geometric solution of the lifting fiber V_{P^{(r+1)}} is computed.

In this paper we realize the general algorithmic ideas of [GHM^{+}98] and [GHH^{+}97] by exhibiting a practically efficient (implementable) algorithm computing the geometric solution of the variety V (F_{1}, …, F_{n}). For this purpose we introduce some modifications of the method of [GHM^{+}98] and [GHH^{+}97] and we develop a series of algorithms for linear algebra tasks, for the manipulation of univariate polynomials and a new effective version of the so called Shape Lemma (cf. [KFF88], [Can88] or [GM89]).

The first modification consists roughly speaking in the determination of a simultaneous Noether normalization of all the varieties V_{1}, …, V_{n} and a simultaneous a priori determination of the corresponding lifting points P^{(1)}, …, P^{(n−1)}. The main purpose of this first modification is to obtain for 2 ≤ r ≤ n a lifting fiber V_{P^{(r+1)}} with the following property: for any point (x_{1}, …, x_{n}) ∈ V_{P^{(r+1)}}, the variety V_{r} ∩ {X_{1} = x_{1}, …, X_{n−r} = x_{n−r}} does not meet the singular locus of V_{r}. This property is crucial in order to avoid the introduction of additional (extraneous) points while computing the geometric solution of the lifting fiber V_{P^{(r+1)}} from the geometric solution of V_{P^{(r)}}. The involuntary introduction of additional points in the procedure developed in [GHM^{+}98] and [GHH^{+}97] produces a quadratic growth of the code size of the polynomials which appear during the algorithm (with the consequent undesired effect on the time and space space complexity of the procedure).

A second modification of the algorithmic method designed in [GHM^{+}98] and [GHH^{+}97] consists in the development of an efficient subalgorithm which produces a geometric solution of the variety V_{r} from the geometric solution of the lifting fiber V_{P^{(r)}}. The symbolic Newton–Hensel algorithm used by this method requires to deal with very special matrices, which arise from the evaluation of a univariate polynomial on a Frobenius matrix. By means of simple duality techniques for univariate polynomials we obtain an efficient algorithm which computes the characteristic polynomial of such matrices, improving in this way considerably upon the time–space complexity of the main algorithm of [GHM^{+}98] and [GHH^{+}97].

Another important feature of the algorithmic method proposed by [GHM^{+}98] and [GHH^{+}97] is the use of a method — originally due to [KP96] — reducing the general problem of finding a Shape Lemma–like representation of a given zero–dimensional complete intersection variety to the case of an algebraic variety defined by only two polynomials in two separate variables. We revise this method, replacing the generalistic linear algebra tools applied in [KP96] by more specific ones based on the manipulation of univariate polynomials. In this way we obtain a significant reduction of the time–space complexity of the corresponding subalgorithm of [KP96].

Finally we focus our attention on the subalgorithm which computes a geometric solution of the lifting fiber V_{P^{(r+1)}} from a geometric solution of the lifting fiber V_{P^{(r)}}. The method used in [GHM^{+}98] and [GHH^{+}97] is divided in two stages. In the first stage a geometric solution of the variety V_{r} is obtained. Then a geometric solution of the intersection of the variety V_{r} with the hypersurface {F_{r+1} = 0} is computed. From this geometric solution one obtains a geometric solution of the lifting fiber V_{P^{(r+1)}} just by specializing the remaining free variables of the given geometric solution of V_{r} ∩ {F_{r+1} = 0} into the coordinates of the point P^{(r+1)}. In this paper we increase significantly the efficiency of this procedure reducing the task to the computation of a geometric solution of the intersection of the hypersurface {F_{r+1} = 0} with a suitably introduced curve W_{P^{(r+1)}} which is contained in the (n − r)–dimensional variety V_{r}. The technique of specializing the free variables is reminicent of a general method coming from theoretical computer science called deforestation (see [Wad90]), and is applied in [GHL^{+}98]. Our technique of lifting a projection from a zero–dimensional variety to a curve was independently discovered and applied in [GLS99].

In this way we obtain a quadratic–space and cubic–time procedure which computes the geometric solution of the given zero–dimensional algebraic variety V (F_{1}, …, F_{n}). More precisely, we obtain the following complexity result:

Theorem 1 Let notations and assumptions be as before. Then there exists a computation tree in Q [X_{1}, …, X_{n}] that computes a geometric solution of the algebraic variety V = V (F_{1}, …, F_{n}) using space O(Sdnδ^{2}) and time O((T dn^{2} + n^{5})δ^{3} log^{3} δ

log^{2} log δ).

In contrast to this result let us mention that a straightforward implementation of the algorithmic method proposed by [GHM^{+}98] and [GHH^{+}97] leads to an algorithm using space O(Sdnδ^{4}) and time O(T dn^{6}δ^{16}). Let us also remark that in the practical situations we have in mind, the quantity δ is expected to be much larger than the values of the parameters S, T and n. In this sense we are saying that our algorithm requires only quadratic space and cubic time.

The computational model we use in this paper is algebraic: we count operations at unit costs. One may argue that this is unrealistic. However, a practical implementation of the basic algorithmic ideas applied in this paper would necessarily rely on modular arithmetic. Nevertheless, for modular arithmetic our complexity model is suitable (compare the implementation work [GLS99]).

2 On time–space tradeoffs

The efficient representation of multivariate polynomials and rational functions is of central importance for geometric elimination procedures (cf. [Par95]). Here we discuss the representation of multivariate polynomials by arithmetic circuits (see e.g. [vzG86] or [vzG93]).

Let Q (X_{1}, …, X_{n}) denote the field of rational functions over Q in the variables X_{1}, …, X_{n}. An arithmetic circuit β in Q (X_{1}, …, X_{n}) is a directed acyclic graph (computation DAG for short), whose nodes have all bounded indegree of either 0 or 2. The nodes of indegree 0 are labeled by elements of Q ∪ {X_{1}, …, X_{n}} and the nodes of indegree 2 (called internal nodes) are labeled by one of the arithmetic operations addition subtraction, multiplication or division. The nodes of indegree 0 labeled by elements of {X_{1}, …, X_{n}} are called input nodes. The nodes of indegree 0 labeled by elements of Q are called parameter nodes. The elements of Q occurring in that way are called parameters of the arithmetic circuit β. Finally, some nodes of the arithmetic circuit β are labeled as output nodes (typically, the output nodes will be the nodes with out–degree 0). We denote the underlying computation DAG of β by Γ(β).

When starting from the input nodes and proceeding along the computation DAG, to each node ρ there corresponds in a natural way a rational function Q_{ρ} computed as the result of all previous steps. Let be given s distinct rational functions F_{1}, …, F_{s} ∈ Q (X_{1}, …, X_{n}) and an arithmetic circuit β in Q (X_{1}, …, X_{n}) with s output nodes. We say that F_{1}, …, F_{s} are represented by β if F_{1}, …, F_{s} are the rational functions associated to the output nodes of β.

In order to modelize the computation with arithmetic circuits, we introduce the notion of pebble game. A pebble game converts a given arithmetic circuit β into a sequential algorithm (also called straight–line program) and associates to β a natural time and a space measure. On the computation graph Γ(β) of the arithmetic circuit β we can play a pebble game subject to the following rules (see [Bor93]):

P1 any indegree 0 node of Γ(β) can be pebbled,

P2 if the predecessor nodes of a given node ρ of Γ(β) are both pebbled, then ρ can be pebbled by a new pebble or just by moving a pebble from one of the predecessor nodes to ρ,

P3 a pebble can always be removed from a pebbled node of Γ(β).

The pebble game finishes when all the output nodes of Γ(β) are pebbled. Observe that the computation graph Γ(β) does not determine a pebble game uniquely, i.e. different pebble games may be played on Γ(β).

We associate to a given pebble game on the computation graph Γ(β) the following complexity measures:

C1 a space measure given by the maximum number of pebbles used at any moment of the game,

C2 a time measure given by the number of pebble placements performed during the game following rules P1 and P2,

Any fixed pebble game on the computation graph Γ(β) defines a strategy of evaluation of β which we call a straight–line program. A straight–line program in Q (X_{1}, …, X_{n}) which computes rational functions F_{1}, …, F_{s} is a sequence β = (Q_{1}, …, Q_{r}) of elements of the field Q (X_{1}, …, X_{n}) with the following properties:

i) {F_{1}, …, F_{s}} ⊆ {Q_{1}, …, Q_{r}},

ii) for any 1 ≤ ρ ≤ r, the rational function Q_{ρ} belongs to Q ∪ {X_{1}, …, X_{n}} or there exist 1 ≤ ρ_{1}, ρ_{2} < ρ and an arithmetic operation op_{ρ} in {+, −, ∗, /} such that Q_{ρ} = Q_{ρ_{1}} op_{ρ} Q_{ρ_{2}} holds.

Straight–line programs have been extensively used to modelize algebraic computations (see for example [BM72], [Str90], [Sto89], [Hei89], [Par95], [BCA97]). Since the late seventies the relevance of this concept for multivariate polynomial elimination became more and more evident (see e.g. [GH93], [GHS93], [FGS95], [FG90], [KP96], [GHMP95], [GHM^{+}98], [GHH^{+}97], [BGHM97]).

Our model of computation is based on the concept of arithmetic circuits and straight–line programs. However, a model of computation consisting only of arithmetic circuits and straight–line programs is not be expressive enough for our purpose, namely, to describe a general geometric elimination procedure. Therefore our model of computation must include decisions and selections (subject to previous decisions). For this reason we shall consider arithmetic–boolean circuits (also called arithmetic networks) instead of arithmetic circuits and computation trees instead of straight–line programs. An arithmetic–boolean circuit is nothing but a DAG whose nodes are labeled either by arithmetic operations or by selections (pointing to other nodes) subject to equal–to–zero decisions. A pebble game on an arithmetic–boolean circuit gives rise to a computation tree, fixing thus a strategy of evaluation of the given arithmetic–boolean circuit. In other words, a computation tree is nothing but a straight–line program with branchings. The time and space of evaluation of a computation tree are defined analogously to the case of straight–line program (see. e.g. [vzG86], [vzG93] or [BCA97] for more details on the notion of arithmetic–boolean circuit and computation tree).

From now on we shall tacitly assume that our arithmetic–boolean circuits and computation trees in Q [X_{1}, …, X_{n}] contain only non–essential divisions (i.e. only divisions by nonzero elements of Q ).

Let us now briefly discuss the time–space tradeoff complexity of the procedures in [GHM^{+}98] and [GHH^{+}97]. These procedures are described by arithmetic–boolean circuits of size (ndδL)^{O(1)} and nonscalar depth O((log_{2} n+ℓ) log_{2} δ), where as before n is the number of variables, d is a degree bound for the input polynomials, δ is the (affine) degree of the input system and finally, L and ℓ are the size and nonscalar depth of an arithmetic circuit representing the input polynomials.

We first observe, that using a standard breadth–first search scheme for the evaluation of the arithmetic–boolean circuits described in [GHM^{+}98] and [GHH^{+}97], we obtain a computation tree using space and time (ndδL)^{O(1)}.

Similarly, using a depth–first search scheme as in [Bor77], we obtain a computation tree using space O((log_{2} n + ℓ) log_{2} δ)^{O(1)} and time Lnδ^{O(log_{2} n+ℓ)} for the same task (see [Mat97a]).

It would be desirable to combine the advantages of these two computation trees, namely, to construct a computation tree which uses only space O((log_{2} n + ℓ) log_{2} δ)^{O(1)} and time (ndδL)^{O(1)}. Unfortunately, there seems to be little hope for the simultaneous optimization of both space and time requirements up to this level.

The main algorithm of [GHM^{+}98] and [GHH^{+}97] relies heavily on linear algebra tasks such as computing the characteristic polynomial or the determinant of matrices of size δ ×δ. As shown in [vzG86] or [vzG93], these tasks are of equal computational difficulty as the iterated matrix product of δ matrices of size δ × δ. With respect to the latter task, the following result is known [Ja’83]:

Theorem 2 ([Ja’83], Theorem 5.3) Let A_{1}, …, A_{δ} be δ matrices in Q^{δ×δ}. Then the time T required to compute the product A_{1} ⋯ A_{δ} using space S verifies:

T = Ω (\frac{δ^{l+1}}{S^{l−2}} ) where l ≥ ⌈log δ⌉ + 2

From this theorem we deduce that using sublinear space algorithms (i.e. algorithms having for some constant c < 1 space complexity O(δ^{c})) in order to solve the linear algebra tasks posed by the main algorithm in [GHM^{+}98] and [GHH^{+}97] would produce an elimination procedure of superpolynomial δ^{O(log δ)} time complexity. Hence, sublinear space algorithms for linear algebra tasks do not yield an optimal time– space tradeoff for the mentioned algorithmic concept.

In view of this conclusion, we see that linear space is the most space efficient alternative for linear algebra tasks if practically feasible procedures have to be designed. In the following sections we are going to revise the critical parts (in terms of memory usage) of the main algorithm in [GHM^{+}98] and [GHH^{+}97] which uses linear algebra subroutines requiring nonlinear space. In this paper we replace these subroutines by linear space algorithms whose (polynomial) time complexity is as small as possible, i.e. asymptotically quadratic. Some more modifications of rather geometric nature of the main algorithm of [GHM^{+}98] and [GHH^{+}97] allow to reduce the exponent 4 of the space complexity of this algorithm to the exponent 2 announced in Theorem 1 (the simultaneous reduction of the time complexity is from exponent 16 to exponent 3).

3 Simultaneous Noether normalization

In this section we maintain the notations and assumptions introduced in the introduction. This section is devoted to the determination of a simultaneous Noether normalization of all varieties V_{1}, …, V_{n−1} and for any 2 ≤ r ≤ n−1 to the determination of a lifting point P^{(r)} such that the corresponding lifting fiber V_{P^{(r)}} has the following property: for any point P := (x_{1}, …, x_{n}) ∈ V_{P^{(r)}}, the lifting fiber of V_{r−1} defined by the point (x_{1}, …, x_{n−r−1}), namely V_{r−1} ∩ {X_{1} = x_{1}, …, X_{n−r+1} = x_{n−r+1}}, does not meet the singular locus of V_{r−1}. By a simultaneous Noether normalization we understand a linear change of variables given by a matrix A ∈ Q^{n×n} such that for any 1 ≤ r ≤ n the new variables Y_{1}, …, Y_{n} are in Noether position with respect to the variety V_{r}, i.e. such that the canonical homomorphism

Q [Y_{1}, …, Y_{n−r}] ↪ Q [Y_{1}, …, Y_{n}]/(F_{1}, …, F_{n−r})

represents an integral extension of Q –algebras.

Lemma 3 There exist polynomials F^{(1)}, …, F^{(n−1)} ∈ Q [X_{1}, …, X_{n}] such that for any 1 ≤ r ≤ n − 1 the following conditions are satisfied:

i) Sing(V_{r}) ⊆ W_{r} := V_{r} ∩ V (F^{(r)}).

ii) dim(W_{r} ∩ V_{r+1}) < dim(V_{r+1}).

iii) deg(F^{(r)}) ≤ r(d − 1).

iv) the coordinate function defined by F^{(r)} in Q [V_{r+1}] is not a zero divisor.

Proof.– Fix 1 ≤ r ≤ n − 1. For any 1 ≤ i ≤ n and any 1 ≤ i_{1} < ⋯ < i_{r} ≤ n, let

J_{i_{1},...,i_{r}} := det \frac{J(F_{1}, …, F_{r})}{∂(X_{i_{1}}, …, X_{i_{r}})} := det (\frac{∂F_{j}}{∂X_{i_{k}}} )_{1≤j,k≤r} be the Jacobian determinant of

F_{1}, …, F_{r} with respect to the variables X_{i_{1}}, …, X_{i_{r}}. From the Jacobian criterion (see e.g. [Eis95]) we deduce that

Sing(V_{r}) = \{\underline{x} ∈ V_{r}; J_{i_{1},...,i_{r}}(\underline{x}) = 0, ∀ 1 ≤ i_{1} < … < i_{r} ≤ n\}

holds. Moreover, from V_{r+1} ⊆ V_{r}, we infer

Sing(V_{r}) ∩ V_{r+1} = \{\underline{x} ∈ V_{r+1}; J_{i_{1},...,i_{r}}(\underline{x}) = 0, ∀ 1 ≤ i_{1} < … < i_{r} ≤ n\}.

Let V_{r+1} = ∪_{j∈J}C_{j} be the decomposition of V_{r+1} into irreducible components. By assumption V_{r+1} is equidimensional. Thus we have dim(C_{j}) = dim(V_{r+1}) for any j ∈ J. Our hypotheses imply dim (V_{r+1} ∩ Sing(V_{r})) < dim(V_{r+1}), which in turn implies that dim (Sing(V_{r}) ∩ V_{r+1}) < dim(V_{r+1}) = dim(C_{j}) holds for any j ∈ J. Therefore, for each j ∈ J there exists a point \underline{x_{j}} belonging to C_{j} but not to Sing(V_{r}).

Thus, for any j ∈ J one of the Jacobian determinants J_{i_{1},...,i_{r}}(\underline{x_{j}}) must be nonzero.

Let N_{r} := ( \begin{matrix}n \\ r \end{matrix} ) where ( \begin{matrix}n \\ r \end{matrix} ) denotes the combinatorial number \frac{n!}{(n−r)!r!}. We may

now choose a generic point (α_{i_{1},...,i_{r}})_{1≤i_{1}<...<i_{r}≤n} ∈ Q^{N_{r}} which satisfies the condition

∑_{1≤i_{1}<...<i_{r}≤n} α_{i_{1},...,i_{r}}J_{i_{1},...,i_{r}}(\underline{x_{i}}) ≠ 0 for any i ∈ I.  (1)

The polynomial F^{(r)} ∈ Q [X_{1}, …, X_{n}] is now defined as:

F^{(r)} := ∑_{1≤i_{1}<...<i_{r}≤n} α_{i_{1},...,i_{r}}J_{i_{1},...,i_{r}}(X_{1}, …, X_{n}).

From the Jacobian criterion we deduce Sing(V_{r}) ⊆ W_{r} := V_{r} ∩ V (F^{(r)}). Moreover, the hypersurface V (F^{(r)}) cuts properly each irreducible component of V_{r+1}. This implies that the dimension of the variety W_{r} ∩ V_{r+1} = V (F^{(r)}) ∩ V_{r+1} is strictly smaller than dim(V_{r+1}).

By construction the (total) degree of the polynomial F^{(r)} is bounded by r(d − 1) (observe that F^{(r)} is a Q–linear combination of the polynomials J_{i_{1},...,i_{r}} whose degrees are at most r(d − 1)).

From the fact that the variety V_{r+1} is equidimensional and from the inequality dim(V (F^{(r)}) ∩ V_{r+1}) < dim(V_{r+1}) we deduce that the coordinate function defined by F^{(r)} is not a zero divisor of Q [V_{r+1}].

In order to find the simultaneous Noether normalization we are looking for, we need a suitable genericity condition. The following lemma asserts the well known fact that a generic linear change of coordinates yields a Noether normalization. Moreover it gives an appropriate bound for the degree of a certain polynomial which expresses a corresponding genericity condition.

Lemma 4 ([Som98]) Let be given a regular sequence of polynomials f_{1}, …, f_{r} ∈ C[X_{1}, …, X_{n}]. And let W := V (f_{1}, …, f_{r}) ⊆ C^{n} be the algebraic variety defined by these polynomials. Then there exists a nonzero polynomial G in the indeterminates Λ_{i,j}, 1 ≤ i ≤ n − r, 1 ≤ j ≤ n, such that the following conditions are satisfied:

• for any n × (n − r) matrix λ := (λ_{i,j})_{1≤i≤n−r,1≤j≤n} ∈ Q ^{(n−r)×n} with G(λ) ≠ 0, the variables Y_{1} := ∑_{j=1}^{n} λ_{1,j}X_{j}, …, Y_{n−r} := ∑_{j=1}^{n} λ_{n−r,j}X_{n} define a finite morphism, mapping the variety W onto the affine space C^{n−r},

• for 1 ≤ i ≤ n−r the polynomial G satisfies the degree estimate deg_{Λ_{i,1},...,Λ_{i,n}}(G) ≤ deg W (here deg_{Λ_{i,1},...,Λ_{i,n}}(G) denotes the degree of G in the variables Λ_{i,1}, …, Λ_{i,n}).

Now we are ready to prove the main theorem of this section. This result asserts that the coefficients of the linear forms Y_{1}, …, Y_{n} and the coordinates of the lifting points P^{(r)} we are looking for can be randomly chosen in a suitable finite subset of ZZ with high probability of success.

Theorem 5 Let κ be a fixed natural number. There exist linear forms Y_{1} := ∑_{j=1}^{n} λ_{1,j}X_{j}, …, Y_{n} := ∑_{j=1}^{n} λ_{n,j}X_{j} of ZZ[X_{1}, …, X_{n}] and points P^{(r)} = (p_{1}^{(r)}, …, p_{n−r}^{(r)}) ∈ ZZ^{n−r} of (absolute) height at most 4κn^{3}d^{2}δ^{2} such that for 1 ≤ r ≤ n − 1 the following conditions are satisfied: i) the linear forms Y_{1}, …, Y_{n} are in Noether position with respect to any of the

varieties V_{1}, …, V_{n},

ii) the point P^{(r)} := (p_{1}^{(r)}, …, p_{n−r}^{(r)}) is a lifting point of V_{r}, i.e. the morphism π_{r} : V_{r} → C^{n−r} induced by the linear forms Y_{1}, …, Y_{n−r} is unramified in P^{(r)},

iii) r = n − 1 or π_{r}^{−1}(π_{r}(π_{r+1}^{−1}(P^{(r+1)}))) ⋂ Sing(V_{r}) = ∅,

iv) r = n − 1 or the π_{r}–fiber of any point in P ∈ π_{r}(π_{r+1}^{−1}(P^{(r+1)})) is smooth, i.e. for any point x ∈ π_{r}^{−1}(P) the condition

det (\frac{J(F_{1}, …, F_{r})}{∂(Y_{n−r+1}, …, Y_{n})}) (x) ≠ 0

is satisfied.

Furthermore, we can choose the coefficients of the linear forms Y_{1}, …, Y_{n} and the coordinates of the points P^{(r)} for 1 ≤ r ≤ n − 1 randomly and uniformly in the set

S := \{1, 2, …, 4κn^{3}d^{2}δ^{2}\} with a probability of success of at least (1 − \frac{1}{2κn})^{2n} > \frac{1}{2}.

Proof.– Let F^{(1)}, …, F^{(n−1)} be the polynomials of the statement of Lemma 3, defining for 1 ≤ r ≤ n − 1 the varieties W_{r} := V_{r} ∩ V (F^{(r)}). We recall that for any 1 ≤ r ≤ n − 1 Sing(V_{r}) ⊆ W_{r} and dim(W_{r} ∩ V_{r+1}) < dim(V_{r+1}) holds.

Let be given linear forms Y_{1}, …, Y_{n} ∈ Q [X_{1}, …, X_{n}] and points P^{(1)} ∈ ZZ^{n−1}, …, P^{(n−1)} ∈ ZZ^{1}. We show first the following assertion:

Fact The linear forms Y_{1}, …, Y_{n} and the points P^{(1)}, …, P^{(n−1)} satisfy conditions i),...,iv) of Theorem 5 if they satisfy for any 1 ≤ r ≤ n − 1 the following conditions:

(a) Y_{1}, …, Y_{n−r} induce a Noether normalization of both varieties W_{r−1} and V_{r},

(b) P^{(r)} := (p_{1}^{(r)}, …, p_{n−r}^{(r)}) is a lifting point of V_{r},

(c) r = n − 1 or π_{r+1}^{−1}(P^{(r+1)}) ∩ W_{r} = ∅,

(d) r = n−1 and Y_{1} separates the points of the (zero dimensional) variety W_{n−1} ∪ V_{n} or 1 ≤ r ≤ n − 2 and Y_{n−r} separates the points of the (zero dimensional) variety

(W_{r} ∪ V_{r+1}) ⋂{Y_{1} = p_{1}^{(r+1)}, …, Y_{n−r−1} = p_{n−r−1}^{(r+1)}}.

(e) r = n − 1 or the π_{r}–fiber of any point in P ∈ π_{r}(π_{r+1}^{−1}(P^{(r+1)})) is smooth, i.e. for any point x ∈ π_{r}^{−1}(P) the condition

det (\frac{J(F_{1}, …, F_{r})}{∂(Y_{n−r+1}, …, Y_{n})}) (x) ≠ 0

is satisfied.

In other words, we claim that the linear forms Y_{1}, …, Y_{n} and the points P^{(1)}, …, P^{(n−1)} satisfy the recursive conditions i), ii), iii) and iv) of Theorem 5 if for any 1 ≤ r ≤ n − 1 they satisfy only condition iv) and conditions (a), (b), (c) and (d) above.

Assume now that the linear forms Y_{1}, …, Y_{n} and the points P^{(1)}, …, P^{(n−1)} satisfy for any 1 ≤ r ≤ n − 1 conditions (a), (b), (c), (d) and (e) of the Fact. We first show that the linear forms Y_{1}, …, Y_{n} and the points P^{(1)}, …, P^{(n−1)} satisfy conditions i), ii) and iii) of Theorem 5.

Conditions i) and ii) of Theorem 5 are trivial consequences of conditions (a) and (b) above. Thus we may assume without loss of generality 1 ≤ r ≤ n − 2. It suffices to verify condition iii) of Theorem 5 in his case. In order to do this, we observe that the linear forms Y_{1}, …, Y_{n−r−1} induce a simultaneous Noether normalization of the varieties W_{r} and V_{r+1}. Thus

(W_{r} ∪ V_{r+1}) ⋂{Y_{1} = p_{1}^{(r+1)}, …, Y_{n−r−1} = p_{n−r−1}^{(r+1)}}

is a zero–dimensional variety. Condition (c) says that π_{r+1}^{−1}(P^{(r+1)}) ∩ W_{r} = ∅ holds. This means that the zero–dimensional varieties

{Y_{1} = p_{1}^{(r+1)}, …, Y_{n−r−1} = p_{n−r−1}^{(r+1)}} ⋂ W_{r}

and

{Y_{1} = p_{1}^{(r+1)}, …, Y_{n−r−1} = p_{n−r−1}^{(r+1)}} ⋂ V_{r+1}

have empty intersection.

Let x′ be an arbitrary point of π_{r}^{−1}(π_{r}(π_{r+1}^{−1}(P^{(r+1)}))). Then there exists a point x ∈ π_{r+1}^{−1}(P^{(r+1)}) such that π_{r}(x′) = π_{r}(x) holds. Hence Y_{n−r}(x) = Y_{n−r}(x′). Taking into account that, by definition, the point x′ belongs to the variety V_{r+1} and that, by condition (d), the linear form Y_{n−r} separates the points of (W_{r} ∪ V_{r+1}) ∩ {Y_{1} = p_{1}^{(r+1)}, …, Y_{n−r−1} = p_{n−r−1}^{(r+1)}}, we deduce from x′ ∈ V_{r+1} and Y_{n−r}(x) = Y_{n−r}(x′) that x′ ∉ W_{r} holds. Since x′ was arbitrary this means that

π_{r}^{−1}(π_{r}(π_{r+1}^{−1}(P^{(r+1)}))) ⋂ W_{r} = ∅

holds. By Lemma 3 we have Sing(V_{r}) ⊆ W_{r}. This implies now condition iii) of Theorem 5.

In view of the Fact we have just proved, for the purpose of showing Theorem 5, it suffices now to construct linear forms Y_{1}, …, Y_{n} and points P^{(1)}, …, P^{(n−1)} satisfying only conditions (a), (b), (c), (d) and (e) of the Fact.

Now we are going to explain how to choose linear forms Y_{1}, …, Y_{n} and points P^{(1)}, …, P^{(n−1)} satisfying conditions (a), (b), (c), (d) and (e) above.

The procedure which finds the linear forms Y_{1}, …, Y_{n} and the points P^{(1)}, …, P^{(n−1)} is top–down recursive, starting with the case r := n−1. We are going now to prepare the first recursive step of our argument. Let us start with the search for a suitable linear form Y_{1} = λ_{1,1}X_{1} + ⋯ + λ_{1,n}X_{n} ∈ Q [X_{1}, …, X_{n}] satisfying the following conditions which we denote by (I):

• Y_{1} separates points on the zero–dimensional variety V_{n} ∪ W_{n−1},

• Y_{1} defines a finite morphism, mapping the one–dimensional variety (curve) V_{n−1} ∪ W_{n−2} onto the affine space C^{1},

• Y_{1}, X_{2}, …, X_{n} are Q –linearly independent and hence they define a Noether normalization of both varieties W_{n−2} and V_{n−1}.

From the Bézout Inequality (see [Hei83] or [Ful84]) and Lemma 3 we deduce that, for 1 ≤ r ≤ n − 1, the variety W_{r} has (affine) degree at most r(d − 1)δ_{r}. Therefore, W_{r}∪V_{r+1} is an algebraic variety of degree at most D_{r} := δ_{r+1}+r(d−1)δ_{r}. By Lemma 4 there exist nonzero polynomials G^{(1)}, …, G^{(n−1)} of C[Λ_{i,j}; 1 ≤ i, j ≤ n] of degree at most nD_{r} such that, for 1 ≤ r ≤ n − 1, any n × (n − r)–matrix (λ_{i,j}) ∈ Q^{(n−r)×n} not being a zero of G^{(r)} yields the coefficients of linear forms Y_{1}, …, Y_{n−r} which induce a Noether normalization of the variety W_{r} ∪ V_{r+1}. Therefore, the polynomial G := ∏_{r=1}^{n−1} G^{(r)} has the property that any n × n–matrix (λ_{i,j}) ∈ Q^{n×n} not being a zero of G yields the coefficients of linear forms Y_{1}, …, Y_{n} which are in simultaneous Noether position with respect to all varieties W_{r} ∪ V_{r+1} where 1 ≤ r ≤ n − 1. We observe that the polynomial G has degree at most n^{2}δ.

For the moment let us consider G as a polynomial in the variables (Λ_{i,j}; 2 ≤ i ≤ n, 1 ≤ j ≤ n). Let us fix an arbitrary monomial in these variables and let us suppose that this monomial appears with a nonzero coefficient H_{1}^{(1)} of C[Λ_{1,j}; 1 ≤ j ≤ n] in G. Obviously we have deg(H_{1}^{(1)}) ≤ n^{2}δ. We observe that any n–tuple λ_{1} := (λ_{1,1}, …, λ_{1,n}) not being a zero of H_{1}^{(1)} yields the coefficients of a linear form Y_{1} such that Y_{1} induces a Noether normalization of the variety W_{n−2} ∪V_{n−1} (this is due to the fact that the polynomial we obtain specializing in G the variables Λ_{11}, …, Λ_{1n} into the values λ_{11}, …, λ_{1n} is a nonzero polynomial of C[Λ_{i,j}; 2 ≤ i ≤ n, 1 ≤ j ≤ n]).

Thus the polynomial H_{1}^{(1)} expresses a genericity condition for the coefficients of Y_{1} which assures that Y_{1} induces a Noether normalization of W_{n−2} ∪ V_{n−1}.

Since V_{n} ∪ W_{n−1} is a zero–dimensional variety containing at most D_{n} := δ_{n} + (n − 1)(d − 1)δ_{n−1} points, there exists a polynomial H_{2}^{(1)} of C[Λ_{1,1}, …, Λ_{1,n}] of degree \frac{D_{n}(D_{n}−1)}{2} ≤ (ndδ)^{2} which expresses a genericity condition for the coefficients λ_{1,1}, …, λ_{1,n} of the linear form Y_{1} assuring that Y_{1} separates the points of the variety V_{n} ∪ W_{n−1}.

Finally we observe that the variables Y_{1}, X_{2}, …, X_{n} are linearly independent if and only if λ_{1,1} ≠ 0. Therefore, H^{(1)} := H_{1}^{(1)}H_{2}^{(1)}Λ_{1,1} is a polynomial of degree at most 2n^{2}d^{2}δ^{2} which yields a genericity condition for the coefficients of the linear form Y_{1} assuring that the variables Y_{1}, X_{2}, …, X_{n} are a linear change of variables, that they are in Noether position with respect to W_{n−2} ∪V_{n−1} and that Y_{1} separates the points of V_{n} ∪ W_{n−1}. In particular, the nonvanishing of the polynomial H^{(1)} implies that the corresponding linear form Y_{1} satisfies the conditions (I) above.

Let S ⊂ ZZ be a finite subset of ZZ. Applying the well–known Zippel–Schwartz random test (see [Zip79], [Sch80] or [Zip93]) we find an n–tuple λ_{1} := (λ_{1,1}, …, λ_{1,n}) in S^{n} such that H^{(1)} does not vanishes on λ_{1}. The probability of success of this procedure is bounded from below by 1 − \frac{deg(H^{(1)})}{card(S)}. For this proof we shall choose the set S := {1, 2, …, 4κn^{3}d^{2}δ^{2}}. Let us write S̃ := {1, 2, …, 4κn^{3}d^{2}δ^{2}}^{n}. Then for a randomly chosen point λ_{1} ∈ S̃ we have H^{(1)}(λ_{1}) ≠ 0. The probability of success is at least 1 − \frac{1}{2κn}. Suppose from now on that we have found such a point λ_{1}, i.e. that the linear form Y_{1} is already given. Observe that following our choice, the linear form Y_{1} satisfies the conditions (I) above.

Next we proceed to find a point P^{(n−1)} ∈ ZZ satisfying the following conditions, which we denote by (II):

• P^{(n−1)} is a lifting point for V_{n−1}.

• π_{n−1}^{−1}(P^{(n−1)}) ∩ W_{n−2} = ∅.

Since (F_{1}, …, F_{n−1}) is a radical ideal of Q [X_{1}, …, X_{n}]we see that the finite dimensional Q (Y_{1})–algebra Q (Y_{1})[X_{2}, …, X_{n}]/(F_{1}, …, F_{s}) is unramified. This implies

that J_{n−1} := det\frac{J(F_{1}, …, F_{n−1})}{∂(X_{2}, …, X_{n})} corresponds to a unit in this algebra. Since the

variables Y_{1}, X_{2}, …, X_{n} are in Noether position with respect to the variety V_{n−1} = V (F_{1}, …, F_{n−1}) and F_{1}, …, F_{n−1} form a regular sequence in Q [Y_{1}, X_{2}, …, X_{n}] = Q [X_{1}, …, X_{n}] we deduce immediately that the coordinate function of Q [V_{n−1}] induced by J_{n−1} is not a zero divisor (see [Mor97], Proposition 18 for a detailed exposition of these standard arguments of commutative algebra). Let m_{J_{n−1}} ∈ Q [Y_{1}][T] be the minimal integral dependence relation satisfied by J_{n−1} in Q [V_{n−1}] and let μ^{(n−1)} ∈ Q [Y_{1}] be its (nonzero) constant term. As shown in [GHH^{+}97], any point P^{(n−1)} ∈ ZZ where μ^{(n−1)} does not vanish is a lifting point of V_{n−1}. Since J_{n−1} has degree at most (n − 1)(d − 1), we deduce from [SS96] that the polynomial μ^{(n−1)} has degree at most (n − 1)(d − 1)δ_{n−1} ≤ ndδ.

It follows by Lemma 3 that the coordinate function defined by F^{(n−2)} is not a zero divisor of Q [V_{n−1}]. Let m_{F^{(n−2)}} ∈ Q [Y_{1}][T] be the minimal integral dependence relation satisfied by F^{(n−2)} in Q [V_{n−1}] and let β^{(n−1)} ∈ Q [Y_{1}] be its (nonzero) constant term. Again we deduce from [SS96] that the polynomial β^{(n−1)} has degree at most (n − 2)(d − 1)δ_{n−1} ≤ ndδ. We claim that for any point P^{(n−1)} ∈ ZZ where the polynomial β^{(n−1)} does not vanish, the condition π_{n−1}^{−1}(P^{(n−1)})∩W_{n−2} = ∅ holds:

Assume at the contrary that there exists a point \underline{x} in the π_{n−1}–fiber of P^{(n−1)} such that \underline{x} ∈ W_{n−2} holds. Since the polynomial m_{F^{(n−2)}}(Y_{1}, F^{(n−2)}) belongs to the ideal (F_{1}, …, F_{n−1}), we have m_{F^{(n−2)}}(P^{(n−1)}, F^{(n−2)}(\underline{x})) = 0. The assumption \underline{x} ∈ W_{n−2} implies F^{(n−2)}(\underline{x}) = 0. Hence the constant term of m_{F^{(n−1)}}, namely β^{(n−1)}, vanishes on P^{(n−1)}. This contradicts choice of the point P^{(n−1)}.

The polynomial μ^{(n−1)}β^{(n−1)} expresses the genericity condition for the point P^{(n−1)} we need in order to satisfy the conditions (II) above. We observe that this polynomial has degree at most 2ndδ. Therefore, applying the Zippel–Schwartz test we may choose randomly a point P^{(n−1)} in the set S_{n−1} := {1, 2, …, 4κn^{2}dδ}. From the construction of the polynomial μ^{(n−1)}β^{(n−1)} we deduce that the linear form Y_{1} and the point P^{(n−1)} satisfies with probability at least 1 − \frac{1}{2κn} the conditions (I) and (II) above. Therefore a random choice of a linear form Y_{1} ∈ Q [X_{1}, …, X_{n}] and of a point P^{(n−1)} ∈ ZZ with coordinates in the sets S̃ and S_{n−1} respectively implies that Y_{1} and P^{(n−1)} satisfy with probability at least (1 − \frac{1}{2κn})^{2} the conditions (I) and (II) above.

Now, let 0 ≤ r ≤ n − 2 and let us assume that there are given linear forms Y_{1}, …, Y_{n−r−1} ∈ Q [X_{1}, …, X_{n}] and points P^{(n−1)} ∈ ZZ, …, P^{(r+1)} ∈ ZZ^{n−r−1} satisfying the following recursive conditions, which we denote by (A)_{r}:

• the linear forms Y_{1}, …, Y_{n−r−1} induce a simultaneous Noether normalization of the varieties W_{r} and V_{r+1},

• P^{(r+1)} is a lifting point of V_{r+1},

• π_{r+1}^{−1}(P^{(r+1)}) ∩ W_{r} = ∅,

• r = n−2 and Y_{1} separates the points of the zero–dimensional variety W_{n−1}∩V_{n} or 1 ≤ r ≤ n − 3 and Y_{n−r−1} separates the points of the zero–dimensional variety (W_{r+1} ∪ V_{r+2}) ∩ {Y_{1} = p_{1}^{(r+2)}, …, Y_{n−r−2} = p_{n−r−2}^{(r+2)}}, • the linear forms Y_{1}, …, Y_{n−r−1}, X_{n−r}, …, X_{n} are linearly independent,

• if 1 ≤ r ≤ n−3, let Y_{n−r}, …, Y_{n} be linear forms with indeterminate coefficients, i.e. for 0 ≤ i ≤ r let Y_{n−r+i} := Λ_{n−r+i,1}X_{1} + ⋯ + Λ_{n−r+i,n}X_{n}, where Λ_{n−r+i,j} are indeterminates for 0 ≤ i ≤ r and 1 ≤ j ≤ n. Then for any r+1 ≤ k ≤ n−2 and any point P ∈ π_{k}(π_{k+1}^{−1}(P^{(k+1)})), the rational function

Q_{k}^{(r+1)} := ∏_{P ∈π_{k}(π_{k+1}^{−1}(P^{(k+1)}))} ∏_{x∈π_{k}^{−1}(P)} det (\frac{J(F_{1}, …, F_{k})}{∂(Y_{n−k+1}, …, Y_{n})}) (x)

is a well defined nonzero element of the function field C(Λ_{n−r+i,j}; 0 ≤ i ≤ r, 1 ≤ j ≤ n), whose numerator and denominator have degree at most k(r + 1)δ^{2}.

Since the already chosen linear form Y_{1} and the point P^{(n−1)} satisfy conditions (I) and (II) above, one concludes easily that they also verify the conditions (A)_{n−2}. Thus, let 1 ≤ r ≤ n − 2 and let us assume as before that there are given linear forms Y_{1}, …, Y_{n−r−1} and points P^{(n−1)}, …, P^{(r+1)} satisfying the conditions (A)_{r}. We are going to exhibit a suitable genericity condition for a linear form Y_{n−r} ∈ Q [X_{1}, …, X_{n}] and for a point P^{(r)} ∈ ZZ^{n−r} which implies that the linear forms Y_{1}, …, Y_{n−r} and the points P^{(n−1)}, …, P^{(r)} satisfy the conditions (A)_{r−1}. For this purpose let us first find the coefficients of a linear form Y_{n−r} satisfying the following conditions, which we denote by (Γ)_{r}:

• Y_{1}, …, Y_{n−r} induce a simultaneous Noether normalization of the varieties W_{r−1} and V_{r},

• Y_{n−r} separates the points of the zero–dimensional variety (W_{r} ∪ V_{r+1}) ∩ {Y_{1} = p_{1}^{(r)}, …, Y_{n−r−1} = p_{n−r−1}^{(r)}},

• the linear forms Y_{1}, …, Y_{n−r−1}, X_{n−r}, …, X_{n} are linearly independent,

• for any r ≤ k ≤ n − 2, the rational function

Q_{k}^{(r)} := ∏_{P ∈π_{k}(π_{k+1}^{−1}(P^{(k+1)}))} ∏_{x∈π_{k}^{−1}(P)} det (\frac{J(F_{1}, …, F_{k})}{∂(Y_{n−k+1}, …, Y_{n})}) (x)

is a well defined nonzero element of C(Λ_{n−r+1+i,j}; 0 ≤ i ≤ r − 1, 1 ≤ j ≤ n) whose numerator and denominator have degree at most krδ^{2}.

Let Y_{1} := ∑_{j=1}^{n} λ_{1,j}X_{j}, …, Y_{n−r−1} := ∑_{j=1}^{n} λ_{n−r−1,j}X_{j}, let P^{(n−1)} := (p_{1}^{(n−1)}), …, P^{(r+1)} := (p_{1}^{(r+1)}, …, p_{n−r−1}^{(r+1)}) and let us consider again the polynomial G defined in the first recursive step of our argument. By induction hypothesis we may assume that G(λ_{i,j}, Λ_{h,l}; 1 ≤ i ≤ n − r − 1, n − r ≤ h ≤ n, 1 ≤ j, l ≤ n) is a nonzero polynomial of C[Λ_{h,l}; n − r ≤ h ≤ n, 1 ≤ l ≤ n]. As before, we fix arbitrarily a monomial in the variables (Λ_{h,l})_{n−r+1≤h≤n,1≤l≤n} occurring with a nonzero coefficient H_{1}^{(r)} ∈ C[Λ_{n−r,j}; 1 ≤ j ≤ n] in the polynomial G. This polynomial has degree at most n^{2}δ. We observe that any point λ_{n−r} := (λ_{n−r,1}, …, λ_{n−r,n}) ∈ ZZ^{n} where H_{1}^{(1)} does not vanish yields the coefficients of a linear form Y_{n−r} such that Y_{1}, …, Y_{n−r} induces a Noether normalization of the variety W_{r−1} ∪V_{r}. This follows from the fact that the polynomial

\begin{matrix}G(λ_{i,j}, Λ_{h,l}; 1 ≤ i ≤ n − r − 1; n − r ≤ h ≤ n; 1 ≤ j, l ≤ n) = \\ = ∏_{s=1}^{n−1} G^{(s)}(λ_{i,j}, Λ_{h,l}; 1 ≤ i ≤ n − r − 1, n − r ≤ h ≤ n − s, 1 ≤ j, l ≤ n) \end{matrix}

is a nonzero polynomial of C[Λ_{h,l}; n − r ≤ h ≤ n, 1 ≤ l ≤ n], which in turn implies G^{(r)}(λ_{i,j}; 1 ≤ i ≤ n−r −1, 1 ≤ j ≤ n) ≠ 0. Therefore the polynomial H_{1}^{(r)} expresses a genericity condition for the coefficients of Y_{n−r} which assures that the linear forms Y_{1}, …, Y_{n−r} induce a Noether normalization of the variety W_{r−1} ∪ V_{r}.

From Lemma 3 we deduce that W_{r} ∪ V_{r+1} is an equidimensional variety of dimension n − r − 1. We have seen before that the variety W_{r} ∪ V_{r+1} has degree at most D_{r} := δ_{r+1} + r(d − 1)δ_{r}. Since the linear forms Y_{1}, …, Y_{n−r−1} induce a Noether normalization of the variety W_{r} ∪ V_{r+1} we deduce that (W_{r} ∪ V_{r+1}) ∩ {Y_{1} = p_{1}^{(r+1)}, …, Y_{n−r−1} = p_{n−r−1}^{(r+1)}} is a zero dimensional variety having at most D_{r} points. Therefore, we can easily construct a polynomial H_{2}^{(r)} of C[Λ_{r,1}, …, Λ_{r,n}] of degree \frac{D_{r}(D_{r}−1)}{2} ≤ r^{2}d^{2}δ^{2} which expresses a genericity condition for the coefficients (λ_{r,1}, …, λ_{r,n}) of the linear form Y_{n−r} assuring that Y_{n−r} separates the points of the variety (W_{r} ∪ V_{r+1}) ∩ {Y_{1} = p_{1}^{(r+1)}, …, Y_{n−r−1} = p_{n−r−1}^{(r+1)}}.

Next we observe that the condition that the variables Y_{1}, …, Y_{n−r}, X_{n−r+1}, …, X_{n} are linearly independent is expressed by the determinant of the matrix given by the vectors of coefficients of Y_{1}, …, Y_{n−r}, X_{n−r+1}, …, X_{n}. This determinant is a linear form H_{3}^{(r)} in the coefficients of Y_{n−r}.

Finally, we proceed to discuss the genericity of the last condition (Γ)_{r}. We observe that for any point P ∈ π_{r+1}(π_{r+2}^{−1}(P^{(r+2)})), the π_{r+1}–fiber of P does not contain singular points of V_{r+1}. Therefore, for any x ∈ π_{r+1}^{−1}(P) the Jacobian matrix \frac{J(F_{1},...,F_{r+1})}{∂(X_{1},...,X_{n})}(x) has full rank r + 1. Applying the chain rule to the change of coordinates given by

( X_{1} ; X_{2} ; ⋮ ; X_{n} ) = A ( Y_{1} ; Y_{2} ; ⋮ ; Y_{n} ) := ( \begin{matrix}λ_{1,1} & … & λ_{1,n} \\ ⋮ & & ⋮ \\ λ_{n−r−1,1} & … & λ_{n−r−1,n} \\ Λ_{n−r,1} & … & Λ_{n−r,n} \\ ⋮ & & ⋮ \\ Λ_{n,1} & … & Λ_{n,n} \end{matrix} ) ( Y_{1} ; Y_{2} ; ⋮ ; Y_{n} )

we deduce that

\frac{J(F_{1}, …, F_{r})}{∂(Y_{1}, …, Y_{n})} = \frac{J(F_{1}, …, F_{r})}{∂(X_{1}, …, X_{n})} · A^{−1}

holds.

Since the matrix \frac{J(F_{1},...,F_{r+1})}{∂(X_{1},...,X_{n})}(x) has full rank r + 1 we see that the (r + 1) × (r + 1)– matrix:

\frac{J(F_{1}, …, F_{r+1})}{∂(X_{1}, …, X_{n})}(x) · Ã

is a nonsingular matrix with entries from C(Λ_{n−r+i,j}; 0 ≤ i ≤ r, 1 ≤ j ≤ n) (here Ã denotes the (n − r + 1) × (r + 1)–matrix formed by the last r + 1 columns of A^{−1}). Therefore the rational function

Q_{r}^{(r+1)} := ∏_{P ∈π_{r+1}(π_{r+2}^{−1}(P^{(r+2)}))} ∏_{x∈π_{r+1}^{−1}(P)} det (\frac{J(F_{1}, …, F_{r+1})}{∂(Y_{n−k+1}, …, Y_{n})})

is a well defined nonzero element of C(Λ_{n−r+i,j}; 0 ≤ i ≤ r, 1 ≤ j ≤ n). Observe that the degrees of its numerator and its denominator are at most by k(r + 1)δ^{2}.

Multiplying the rational functions Q_{r}^{(r+1)}, …, Q_{n}^{(r+1)} we obtain a rational function Q^{(r+1)} whose numerator and denominator have degree at most (r +1)^{2}δ^{2}. The product of the numerator and the denominator of this rational function is a polynomial Q̃^{(r+1)} of C[Λ_{n−r+i,j}; 0 ≤ i ≤ r, 1 ≤ j ≤ n] of degree at most 2(r + 1)^{2}δ^{2}. We consider the polynomial Q̃^{(r+1)} as a polynomial in Λ_{n−r+i,j}; 1 ≤ i ≤ r, 1 ≤ j ≤ n with coefficients in Q [Λ_{n−r,j}; 1 ≤ j ≤ n]. Let us fix an arbitrary monomial in the variables Λ_{n−r+i,j}; 1 ≤ i ≤ r, 1 ≤ j ≤ n which occurs with a nonzero coefficient H_{4}^{(r)} ∈ C[Λ_{n−r,j}; 1 ≤ j ≤ n] in Q̃^{(r+1)}. By construction we deduce that for any point (λ_{n−r,1}, …, λ_{n−r,n}) ∈ ZZ^{n} where the polynomial H_{4}^{(r)} does not vanish, the replacement of the variables Λ_{n−r,1}, …, Λ_{n−r,n} by λ_{n−r,1}, …, λ_{n−r,n} in the rational functions Q_{r}^{(r+1)}, …, Q_{n}^{(r+1)} yields well defined rational functions Q_{r}^{(r)}, …, Q_{n}^{(r)} satisfying the conditions above for our inductive step.

Therefore multiplying the polynomials H_{1}^{(r)}, H_{2}^{(r)}, H_{3}^{(r)} and H_{4}^{(r)} we obtain a polynomial H^{(r)} of degree at most n^{2}δ + r^{2}d^{2}δ^{2} + 1 + 2(r + 1)^{2}δ^{2} ≤ 2n^{2}d^{2}δ^{2} which yields a genericity condition on the coefficients of the linear form Y_{n−r} which assures that Y_{1}, …, Y_{n−r} satisfy the conditions (Γ)_{r}.

Applying again the Zippel–Schwartz test we see that we can choose with probability at least 1− \frac{1}{2κn} a point λ_{n−r} := (λ_{n−r,1}, ..., λ_{n−r,n}) of the set S̃ = \{1, 2, …, 4κn^{3}d^{2}δ^{2}\}^{n} such that H^{(r)}(λ_{n−r}) ≠ 0 holds. From the construction of the polynomial H^{(r)} we deduce that any point λ_{n−r} ∈ ZZ^{n} where H^{(r)} does not vanish yields the coefficients of a linear form Y_{n−r} satisfying the conditions (Γ)_{r}.

Assume that we have found the coefficients of such a linear form Y_{n−r}, we proceed now to search for the coordinates of a point P^{(r)} satisfying the following conditions, which we denote by (Ω)_{r}:

• P^{(r)} is a lifting point of V_{r}.

• π_{r}^{−1}(P^{(r)}) ∩ W_{r−1} = ∅.

Using the same argument as in the first step of our proof, we conclude that the coor-

dinate function defined by the Jacobian determinant J_{r} := det (\frac{J(F_{1}, …, F_{r})}{∂(X_{n−r+1} ⋯ X_{n})})

is not a zero divisor of Q [V_{n−1}]. Let m_{J_{r}} ∈ Q [Y_{1}, …, Y_{n−r}][T] be the minimal integral dependence relation satisfied by the coordinate function defined by J_{r} in Q [V_{r}], and let μ^{(r)} ∈ Q [Y_{1}, …, Y_{n−r}] be the (nonzero) constant term of m_{J_{r}}. As shown in [GHH^{+}97], any point P^{(r)} ∈ ZZ^{n−r} where μ^{(r)} does not vanish is a lifting point of V_{r}. Since J_{r} has degree at most r(d − 1), we deduce from [SS96] that the polynomial μ^{(r)} has degree at most r(d − 1)δ_{r} ≤ rdδ.

From Lemma 3 we deduce that the coordinate function defined by F^{(r−1)} is not a zero divisor of Q [V_{r}]. Let m_{F^{(r−1)}} ∈ Q [Y_{1}, …, Y_{n−r}][T] be the minimal integral dependence relation satisfied by the coordinate function defined by F^{(r−1)} in Q [V_{r}] and let β^{(r)} ∈ Q[Y_{1}, …, Y_{n−r}] be its (nonzero) constant term. We deduce from [SS96] that the polynomial β^{(r)} has degree at most (r−1)(d−1)δ_{r} ≤ rdδ. In a similar way as in the first step of our argument, we conclude that any point (p_{1}^{(r)}, …, p_{n−r}^{(r)}) ∈ ZZ^{n−r} where the polynomial β^{(r)} does not vanish satisfies the condition π_{r}^{−1}(p_{1}^{(r)}, …, p_{n−r}^{(r)})∩ W_{r−1} = ∅.

The polynomial μ^{(r)}β^{(r)} expresses a genericity condition which implies that the point P^{(r)} satisfies the conditions (Ω)_{r}. We observe that this polynomial has degree at most 2rdδ. Therefore, applying the Zippel–Schwartz test we may choose randomly a point P^{(r)} in the set S_{r} := {1, 2, …, 4κn^{2}dδ}^{n−r}. From the construction of the polynomial μ^{(r)}β^{(r)} we deduce that the point P^{(r)} satisfies with probability at least 1 − \frac{1}{2κn} the conditions (Ω)_{r}. Therefore a random choice of a linear form Y_{n−r} ∈ Q [X_{1}, …, X_{n}] and a point P^{(r)} ∈ ZZ^{n−r}, with coordinates in the sets S̃ and S_{r} respectively, implies that Y_{n−r} and P^{(r)} satisfy with probability at least (1 − \frac{1}{2κn})^{2} conditions (Γ)_{r} and (Ω)_{r} above. For such a choice it is now easy to see that the linear forms Y_{1}, …, Y_{n−r} and the points P^{(n−1)}, …, P^{(r)} satisfy the conditions (A)_{r−1}.

Recursively we are now able to generate the coefficients of n − 1 linear forms Y_{1}, …, Y_{n−1} ∈ Q [X_{1}, …, X_{n}] and for 1 ≤ r ≤ n − 1 the coordinates of n − 1 points P^{(r)} ∈ ZZ^{n−r} which satisfy the condition (A)_{0}. By the way, we have shown that the choice of these coefficients and coordinates may be done randomly in the set

S = \{1, 2, …, 4κn^{3}d^{2}δ^{2}\} with probability of success of at least (1 − \frac{1}{2κn})^{2n} > \frac{1}{2}.

Observe now that condition (A)_{0} is identified with conditions (a), (b), (c), (d) and (e) of the Fact shown at the beginning of the proof. From this Fact we deduce now immediately Theorem 5.

From now on we shall suppose that κ is fixed and that we have already chosen linear forms Y_{1}, …, Y_{n} ∈ ZZ[X_{1}, …, X_{n}] and points P^{(r)} = (p_{1}^{(r)}, …, p_{n−r}^{(r)}) ∈ ZZ^{n−r}, 1 ≤ r ≤ n−1, satisfying the conditions (i)–(iv) of Theorem 5 and having coordinates in S = {1, …, 4κn^{3}d^{2}δ^{2}}.

4 Algorithmic tools

In this section we are going to exhibit efficient algorithms for some specific geometric tasks. These tasks are crucial for the design of our main algorithm which computes a geometric solution of the algebraic variety V_{n} := V (F_{1}, …, F_{n}). Fix 1 ≤ r ≤ n−1. We are going to consider the following tasks:

• lifting of a projection: given a geometric solution of the lifting fiber V_{P^{(r)}} of the morphism π_{r} : V_{r} → C^{n−r} and a polynomial F ∈ Q [X_{1}, …, X_{n}], compute the minimal polynomial of F over Q [V_{r}],

• the following effective variant of the Shape Lemma: let K be a field of characteristic zero with algebraic closure \overline{K}. Let be given three nonconstant and square–free polynomials f, g, h ∈ K[T] by their coefficients and let be given a nonzero element α ∈ K. Suppose that the linear form αX + Y separates points of the zero–dimensional variety {(x, y) ∈ K̄^{2}; f(x) = 0, g(x) = 0} and that the variety W := {(x, y) ∈ K̄^{2}; f(x) = 0, g(x) = 0, h(αx + y) = 0} is nonempty. The task consists in the computation of a geometric solution of the zero–dimensional algebraic variety W.

• lifting of a zero–dimensional fiber: given a geometric solution of the lifting fiber V_{P^{(r)}} of the morphism π_{r} : V_{r} → C^{n−r}, compute a geometric solution of V_{r}, • computation of a projection: given a geometric solution of the lifting fiber

V_{P^{(r)}} of the morphism π_{r} : V_{r} → C^{n−r}, compute the minimal equation satisfied by the linear form Y_{n−r} over the lifting fiber V_{P^{(r+1)}} of the morphism π_{r+1} : V_{r+1} → C^{n−r−1}.

4.1 Newton–Hensel lifting of a projection

Fix again 1 ≤ r ≤ n − 1. In this subsection we shall develop an efficient algorithm for the following task:

Given a polynomial F ∈ Q [Y_{1}, …, Y_{n}], compute a polynomial q ∈ Q[Y_{1}, …, Y_{n−r}][T] such that the condition q(Y_{1}, …, Y_{n−r}, F) ∈ (F_{1}, …, F_{r}) holds.

This task is a fundamental problem for geometric elimination procedures and was considered by several authors (see for example [GH93], [KP96], [GHMP95], [GHM^{+}98], [GHH^{+}97], [Mor97]). Our approach is inspired by [GHH^{+}97], where an algorithm is described solving this task starting from a geometric solution of the lifting fiber V_{P^{(r)}} as input.

Let notations and assumptions be as before. Assume that there is given a geometric solution of the variety V_{r} and assume that this geometric solution is compatible with the given lifting point P^{(r)} ∈ ZZ^{n−r}. In view of the notation introduced in Section 1 let this geometric solution be given by the following items:

• a linear form U ∈ Q [Y_{n−r+1}, …, Y_{n}] inducing a primitive element u of the integral ring extension Q [Y_{n−r+1}, …, Y_{n}] ↪ Q [V_{r}] with minimal polynomial q(T) ∈ Q [Y_{1}, …, Y_{n−r}][T]

• primitive polynomials

ρ_{n−r+1}Y_{n−r+1} − v_{n−r+1}(T) , …, ρ_{n}Y_{n} − v_{n}(T)

with ρ_{n−r+1}, …, ρ_{n} being nonzero elements of Q [Y_{1}, …, Y_{n−r}] and v_{n−r+1}(T), …, v_{n}(T) belonging to Q [Y_{1}, …, Y_{n−r}][T]

These items satisfy by assumption the following conditions:

i) deg_{T} q = rank_{Q[Y_{1},...,Y_{n−r}]}Q [V_{r}]

ii) ρ_{n−r+1}Y_{n−r+1} − v_{n−r+1}(T), …, ρ_{n}Y_{n} − v_{n}(T) form a generic “parametrization” of the variety V_{r} by the zeroes of q(T) (see Section 1 for details)

iii) ρ_{n−r+1}(P^{(r)}) ≠ 0, …, ρ_{n}(P^{(r)}) ≠ 0 and discr_{T} q(P^{(r)}) ≠ 0 In order to simplify notations, we assume without loss of generality δ_{r} = deg_{T} q = rank_{Q[Y_{1},...,Y_{n−r}]}Q [V_{r}].

The given geometric solution of V_{r} induces a geometric solution of the lifting fiber V_{P^{(r)}}. This geometric solution is given by a primitive element u^{(r)} ∈ Q [V_{r}], namely the coordinate function defined by the linear form U, and by the polynomials

q^{(P^{(r)})}(T) := q(P^{(r)}, T)  in Q [T]
Y_{n−r+1} − v_{n−r+1}^{(P^{(r)})}(T) := Y_{n−r+1} − \frac{1}{ρ(P^{(r)})}v_{n−r+1}(P^{(r)}, T)
⋮  in Q [T]
Y_{n} − v_{n}^{(P^{(r)})}(T) := Y_{n} − \frac{1}{ρ(P^{(r)})}v_{n}(P^{(r)}, T)

with v_{n−r+1}^{(P^{(r)})}(T), …, v_{n}^{(P^{(r)})}(T) ∈ Q [T]. Here q^{(P^{(r)})}(T) is the minimal polynomial of the primitive element u^{(r)} in Q [V_{P^{(r)}}] and the polynomials Y_{n−r+1} − v_{n−r+1}^{(P^{(r)})}(T), …, Y_{n} − v_{n}^{(P^{(r)})}(T) parametrize the points of V_{P^{(r)}} by the zeroes of the polynomial q^{(P^{(r)})}(T). Denote by M ∈ Q^{δ_{r}×δ_{r}} the companion matrix of the polynomial q^{(P^{(r)})}(T). Considering F_{1}, …, F_{r} as polynomials in the variables Y_{n−r+1}, …, Y_{n} with coefficients in the polynomial ring Q [Y_{1}, …, Y_{n−r}] let us write

h_{0} := det ( \begin{matrix}\frac{∂F_{1}}{∂Y_{n−r+1}} & … & \frac{∂F_{1}}{∂Y_{n}} \\ ⋮ & & ⋮ \\ \frac{∂F_{r}}{∂Y_{n−r+1}} & … & \frac{∂F_{r}}{∂Y_{n}} \end{matrix} ) ·

Observing that the vanishing ideal I(V_{P^{(r)}}) of the lifting fiber V_{P^{(r)}} is generated in Q [Y_{n−r+1}, …, Y_{n}] by the polynomials F_{1}(P^{(r)}, Y_{n−r+1}, …, Y_{n}), …, F_{r}(P^{(r)}, Y_{n−r+1}, , …, Y_{n}) we easily deduce from conditions (i)–(iii) above that the rational δ_{r} × δ_{r} matrix h_{0}(P^{(r)}, v_{n−r+1}^{(P^{(r)})}, …, v_{n}^{(P^{(r)})}) is invertible.

The algorithm of [GHH^{+}97] relies on a symbolic iteration of the following Newton– Hensel operator:

N(Y_{n−r+1}, …, Y_{n})^{t} :=

= ( Y_{n−r+1} ; ⋮ ; Y_{n} ) − ( \begin{matrix}\frac{∂F_{1}}{∂Y_{n−r+1}} & ⋯ & \frac{∂F_{1}}{∂Y_{n}} \\ ⋮ & & ⋮ \\ \frac{∂F_{r}}{∂Y_{n−r+1}} & ⋯ & \frac{∂F_{r}}{∂Y_{n}} \end{matrix} )^{−1}· ( F_{1}(Y_{n−r+1}, …, Y_{n}) ; ⋮ ; F_{r}(Y_{n−r+1}, …, Y_{n}) ) .

N(Y_{n−r+1}, …, Y_{n})^{t} denotes the transposition of the row vector N(Y_{n−r+1}, …, Y_{n}) to the corresponding column vector. The approach of [GHH^{+}97] is based on the observation that any generic 0–dimensional fiber V_{P^{(r)}} provides all the information necessary to reconstruct a geometric solution of the positive dimensional variety V_{r}.

Let D be the total degree of F and let σ := ⌊log(Dδ_{r})⌋ + 1. Let us denote by (\frac{g_{n−r+1}}{h} , …, \frac{g_{n}}{h}) = N^{σ} the vector of rational functions \frac{g_{k}}{h} ∈ Q (Y_{1}, …, Y_{n−r})[Y_{n−r+1}, …, Y_{n}] obtained by iterating the Newton–Hensel operator σ times. Since the rational δ_{r} × δ_{r} matrix h_{0}(P^{(r)}, v_{n−r+1}^{(P^{(r)})}(M), …, v_{n}^{(P^{(r)})}(M)) is invertible, we may assume without loss of generality that the same holds for h(P^{(r)}, v_{n−r+1}^{(P^{(r)})}(M), …, v_{n}^{(P^{(r)})}(M)). Thus we see that the matrix h(v_{n−r+1}^{(P^{(r)})}(M), …, v_{n}^{(P^{(r)})}(M)), we obtain by the polynomial h(Y_{1}, …, Y_{n}) specializing the variables Y_{n−r+1}, …, Y_{n} into the rational δ_{r} × δ_{r} matrices v_{n−r+1}^{(P^{(r)})}(M), …, v_{n}^{(P^{(r)})}(M), is an invertible element of the matrix ring

Q [Y_{1}, …, Y_{n−r}]_{(Y_{1}−p_{1}^{(r)},...,Y_{n−r}−p_{n−r}^{(r)})}^{δ_{r}×δ_{r}}

and hence of the matrix rings Q (Y_{1}, …, Y_{n−r})^{δ_{r}×δ_{r}} and Q [[Y_{1} − p_{1}^{(r)}, …, Y_{n−r} − p_{n−r}^{(r)}]]^{δ_{r}×δ_{r}} (here Q [[Y_{1} − p_{1}^{(r)}, …, Y_{n−r} − p_{n−r}^{(r)}]] denotes the formal power series ring over Q in the variables Y_{1} −p_{1}^{(r)}, …, Y_{n−r} −p_{n−r}^{(r)} ). With all these notations we have the following result:

Theorem 6 ([GHH^{+}97], Lemma 29) Suppose that F (Y_{1}, …, Y_{n}) is a polynomial of Q [Y_{1}, …, Y_{n}] having degree at most D. Suppose that F is given by a straight– line program using space S and time T . The coordinate function of V_{r} defined by the polynomial F has monic minimal polynomial q_{F} (T) ∈ Q [Y_{1}, …, Y_{n−r}][T] with respect to the ring extension Q [Y_{1}, …, Y_{n−r}] ↪ Q [V_{r}]. For 1 ≤ k ≤ r let us introduce the following δ_{r} × δ_{r} matrix:

N_{n−r+k} := g_{n−r+k}(v_{n−r+1}^{(P^{(r)})}(M), …, v_{n}^{(P^{(r)})}(M)) · h(v_{n−r+1}^{(P^{(r)})}(M), …, v_{n}^{(P^{(r)})}(M))^{−1}.

(observe that N_{n−r+k} is an element of Q [Y_{1}, …, Y_{n−r}]_{(Y_{1}−p_{1}^{(r)},...,Y_{n−r}−p_{n−r}^{(r)})}^{δ_{r}×δ_{r}}) Finally,

let M_{F} := F (Y_{1}, …, Y_{n−r}, N_{n−r+1}, …, N_{n}) ∈ Q[Y_{1}, …, Y_{n−r}]_{(Y_{1}−p_{1}^{(r)},...,Y_{n−r}−p_{n−r}^{(r)})}^{δ_{r}×δ_{r}} and

let q̃_{F} (T) ∈ Q[Y_{1}, …, Y_{n−r}]_{(Y_{1}−p_{1}^{(r)},...,Y_{n−r}−p_{n−r}^{(r)})}[T] be the minimal polynomial of M_{F}. Suppose that deg_{T} q_{F} = deg_{T} q̃_{F} holds. Then we have that in

Q [Y_{1}, …, Y_{n−r}]_{(Y_{1}−p_{1}^{(r)},...,Y_{n−r}−p_{n−r}^{(r)})}[T]

(and hence in Q [[Y_{1} − p_{1}^{(r)}, …, Y_{n−r} − p_{n−r}^{(r)}]][T]) the polynomials q_{F} and q̃_{F} are congruent modulo the ideal (Y_{1} − p_{1}^{(r)}, …, Y_{n−r} − p_{n−r}^{(r)})^{Dδ_{r}+1}. In symbols we have:

q_{F} ≡ q̃_{F} modulo (Y_{1} − p_{1}^{(r)}, …, Y_{n−r} − p_{n−r}^{(r)})^{Dδ_{r}+1} .

By means of this theorem and of the estimation deg q_{F} ≤ Dδ_{r} ([SS96]) it is possible to design a computation tree which produces a straight–line program representing every coefficient of polynomial q_{F} (T) with respect to the variable T. This computation tree (and the corresponding straight–line program for the coefficients of q_{F} (T)) use space O(SrDδ_{r}^{3}) and time O(T r^{4}D^{2}δ_{r}^{6}).

Sketch of the construction of the computation tree: First we compute the Jacobian matrix

( \begin{matrix}\frac{∂F_{1}}{∂Y_{n−r+1}} & … & \frac{∂F_{1}}{∂Y_{n}} \\ ⋮ & & ⋮ \\ \frac{∂F_{r}}{∂Y_{n−r+1}} & … & \frac{∂F_{r}}{∂Y_{n}} \end{matrix} )

and its inverse using neither divisions nor branchings (by means, e.g., of the Samuelson algorithm [FF63]). Then, we compute the polynomials g_{n−r+1}, …, g_{n}, h without divisions by means of a suitable homogenization procedure (see [GHH^{+}97], Lemma 27). Afterwards, we evaluate the given parametrization polynomials v_{n−r+1}^{(P^{(r)})}(T), …, v_{n}^{(P^{(r)})}(T) in the companion matrix M. Now we substitute in the given straight– line program for the polynomial F (Y_{1}, …, Y_{n}) the input nodes Y_{n−r+1}, …, Y_{n} by the rational functions \frac{g_{n−r+1}}{h} , …, \frac{g_{n}}{h} and compute numerator and denominator of the resulting rational function F (Y_{1}, …, Y_{n−r}, \frac{g_{n−r+1}}{h} , …, \frac{g_{n}}{h}) separately. To this numerator and denominator we apply the same procedure as before, replacing the input nodes Y_{n−r+1}, …, Y_{n} by the matrices v_{n−r+1}^{(P^{(r)})}(M), …, v_{n}^{(P^{(r)})}(M). In this way we obtain now easily a straight–line program representation of the entries of the matrix M_{F}, dividing only by units in Q [Y_{1}, …, Y_{n−r}]_{(Y_{1}−p_{1}^{(r)},...,Y_{n−r}−p_{n−r}^{(r)})}. Then we represent each coefficient of the characteristic polynomial q̃_{F} (T) of the matrix M_{F} as the quotient of two polynomials, the denominator being a unit in Q [Y_{1}, …, Y_{n−r}]_{(Y_{1}−p_{1}^{(r)},...,Y_{n−r}−p_{n−r}^{(r)})}. These polynomials are given by division–free straight–line programs in Q [Y_{1}, …, Y_{n−r}] and we obtain these straight–line programs applying division free linear algebra routines ([FF63]) to the previously computed straight–line program representation of the entries of the matrix M_{F}. Applying to this numerator–denominator representation of each coefficient of q̃_{F} (T) the Vermeidung von Divisionen procedure [Str73], we obtain a division–free straight– line program in Q [Y_{1}, …, Y_{n−r}] which computes the coefficients of a polynomial of Q [Y_{1}, …, Y_{n−r}][T] which is in Q [[Y_{1} − p_{1}^{(r)}, …, Y_{n−r} − p_{n−r}^{(r)}]][T] congruent to q̃_{F} modulo the ideal (Y_{1} − p_{1}^{(r)}, …, Y_{n−r} − p_{n−r}^{(r)})^{Dδ_{r}+1}. From this polynomial it is now easy to read–off the coefficients of the coefficients of q_{F}.

Since the quantity δ_{r} may be large in many practical situations, the O(δ_{r}^{3}) space requirement for the evaluation of this computation tree seems to be prohibitive for an efficient implementation. Moreover we would also like to reduce the time requirement of O(δ_{r}^{6}) of this procedure, in order to increase the range of practical problems which can be treated by our algorithmic approach.

For this reason we are now going to develop several linear algebra procedures that profit from the fact that all the matrices we have to deal with are “structured” in some sense. This will allow us to reduce the time–space complexity of the subroutine we are considering here. We are now going to show that the geometric sub–problem under consideration can be solved in quadratic space and cubic time in δ_{r}.

4.1.1 Time–space economy in linear algebra

We start this subsection with the formulation of a preliminary result concerning modular computation with straight–line programs.

Lemma 7 Let R be the polynomial ring Q [Y_{1}, …, Y_{n−r}]and let K be its quotient field. Let be given polynomials q(T), f(T) and g(T) of R[T]. Assume that q(T) is separable and monic with respect to the variable T and let δ := deg_{T} q(T). Assume furthermore that q(T) and g(T) are coprime in K[T] and that there is given a division–free straight–line program β in R[T] which computes the coefficients of the polynomial q(T) with respect to the variable T and which evaluates the polynomials f(T) and g(T) with respect to all variables (including T) in space S and time T . Then there exists a division–free straight–line program in Q [Y_{1}, …, Y_{n−r}] = R computing a nonzero element α of R and the coefficients of a polynomial h(T) of R[T] with deg_{T} h ≤ δ − 1 such that in R[T] the condition g(T)h(T) ≡ αf(T) modulo q(T) is satisfied. This straight–line program uses space O(Sδ) and time O((T + δ)δ log δ log log δ) = O(T δ^{2} log log δ).

Proof.– First we compute the coefficients of the remainders of f(T) modulo q(T) and g(T) modulo q(T) of the division of f(T) and g(T) by q(T) and call them f̃(T) and g̃(T) respectively. For this purpose, we execute the straight–line program β performing polynomial arithmetic modulo q(T) in each step. Each intermediate result of the computation is a polynomial of R[T] of degree at most δ − 1, which we represent by a vector in R^{δ}.

We are now going to see how can β be transformed into a division–free straight–line program β̃ in Q[Y_{1}, …, Y_{n−r}] = R which computes the coefficients of f̃(T) and g̃(T) with respect to the variable T. This transformation is performed step by step along the straight–line program β. Each addition node of β is transformed in the most obvious way into δ addition nodes of β̃.

We are now going to describe the transformation of a multiplication node of β. Let u(T) and v(T) be intermediate results of β and let us suppose that the coefficients of u(T) modulo q(T) and v(T) modulo q(T) are already computed by the straight– line program β̃. We compute then the coefficients of the polynomial (u · v)(T) by means of a FFT–based algorithm (see [BP94]) and divide afterwards (u · v)(T) by q(T) using the Sieveking–Kung algorithm which is based on the inversion of formal power series (see [Sie72], [BM72] or [BP94]). This single transformation step can be performed in space O(δ) and time O(δ log δ log log δ).

This first part of the computation, which produces the coefficients of f̃(T) and g̃(T) with respect to the variable T, can therefore be performed in space O(Sδ) and time O(T δ log δ log log δ). Now suppose that the coefficients of f̃(T) and of g̃(T) are already computed. Observe that these coefficients can be stored in space O(δ).

Then, we apply the algorithms based on Hankel matrices of [Sen90] and [SL92] in order to produce a nonzero element α ∈ R and a polynomial h̃(T) ∈ R[T] which satisfy in R[T] the condition h̃(T)g̃(T) ≡ α modulo q(T). This can be done in additional space O(δ) and time O(δ^{2} log δ log log δ). Finally, multiplying f̃(T) and h̃(T) and dividing the result by q(T) in the same way as before, we obtain the coefficients of a polynomial h(T) ∈ R[T] which satisfies the requirements of the statement of Lemma 7. The complexity bounds of the lemma are obtained by adding up the complexities of the different steps of the algorithm just described.

Now we state the fundamental result of this subsection (compare [ABRW96] and [Rou96]).

Lemma 8 Let notations and assumptions be as in Lemma 7. Let M be the companion matrix of the polynomial q(T). Thus g(M) is a δ ×δ matrix with entries from R, which is invertible in the matrix ring K^{δ×δ}. Let N be the matrix N := f(M)g(M)^{−1}. Then there exists a straight–line program in Q [Y_{1}, …, Y_{n−r}] = R which computes in space O(Sδ) and time O((T + δ)δ log δ log log δ) = O(T δ^{2} log δ log log δ) the α^{δ}– multiples of the coefficients of the characteristic polynomial χ_{N}(Y) of N. In particular, these α^{δ}–multiples of the coefficients of χ_{N}(Y) are elements of R (here Y is a new variable).

Proof.– From Lemma 7 we deduce that h(M) = αf(M)g^{−1}(M) = αN holds and therefore the δ × δ matrix αN has entries from R.

The algorithm underlying the statement of Lemma 8 runs as follows: we compute first the traces of the matrices αN, …, (αN)^{δ} and use then the Newton Relations in order to produce the coefficients of the characteristic polynomial χ_{αN}(Y) of the matrix αN. Finally we compute the coefficients of the polynomial χ_{αN}(αY) which are in fact the α^{δ}–multiples of the coefficients of the polynomial χ_{N}(Y).

Let T be a new variable. In order to compute for 1 ≤ k ≤ δ the trace tr((αN)^{k}) of the matrix (αN)^{k} space–efficiently (i.e. avoiding the explicit computation of the matrices (αN)^{k} which requires space O(δ^{2})), we consider the decomposition into linear factors of the polynomial q(T) over an algebraic closure K̄ of the field K, namely the decomposition q(T) = ∏_{1≤i≤δ}(T − α_{j}) with α_{i} ∈ K̄.

We shall use the following expression for the derivative q′(T) := \frac{∂q(T)}{∂T} of the polynomial q(T):

q′(T) = ∑_{i=1}^{δ} ∏_{j≠i}(T − α_{j}) .

From the given decomposition of q(T) in linear factors we infer that in K̄[T] for any 1 ≤ i ≤ δ the congruence relation

T ∏_{j≠i}(T − α_{j}) ≡ α_{i} ∏_{j≠i}(T − α_{j}) modulo q(T)

holds. Summing up these congruence relations, we obtain

T ∑_{i=1}^{δ} ∏_{j≠i}(T − α_{j}) ≡ ∑_{i=1}^{δ} α_{i} ∏_{j≠i}(T − α_{j}) modulo q(T) .

This implies that for any polynomial p(T) ∈ R[T] the congruence relation

\begin{matrix}p(T)q′(T) = & p(T) ∑_{i=1}^{δ} ∏_{j≠i}(T − α_{j}) \\ ≡ & ∑_{i=1}^{δ} p(α_{i}) ∏_{j≠i}(T − α_{j}) modulo q(T) \end{matrix}  (2)

holds in R[T].

This means that tr(p(M)) = ∑_{1≤i≤δ} p(α_{i}) appears as the leading coefficient of the

remainder of the division of the polynomial (p · q′)(T) by the polynomial q(T).

In particular, we deduce from the congruence relation (2) that for any 1 ≤ k ≤ δ the value tr((αN)^{k}) = tr(h(M)^{k}) appears as the (δ − 1)–th coefficient of the remainder of the division of (h^{k}q′)(T) by q(T) (here h(T) is the polynomial of the statement of Lemma 7).

By assumption, the given straight–line program β produces the coefficients of the polynomial q(T) and therefore, without loss of generality, also the coefficients of the derivative q′(T). Now, applying Lemma 7, we compute in space O(Sδ) and time O((T + δ)δ log δ log log δ) the element α and the coefficients of the polynomial h(T) with respect to the variable T. At this moment we store only the element α ∈ R and the coefficients of q(T), of q′(T) modulo q(T) and of h(T). This can be done in space O(δ).

From these data we compute now in the same way as at the beginning of the proof the following items: first we compute the coefficients of the polynomial (h · q′)(T) modulo q(T) and store them for the next step, while we clear from our memory space the coefficients of q′(T). Next we compute from the coefficients of (h · q′)(T) modulo q(T), h(T) and q(T) the coefficients of (h^{2} · q′)(T) modulo q(T), while we from clear our memory space all coefficients of (h · q′)(T), except the (δ − 1)–th one. We proceed in this way during the δ steps, the successive computation of the coefficients of (h · q′)(T) modulo q(T) and (h^{2} · q′)(T) modulo q(T) being the first and second one. Let 1 < k ≤ δ. In the k–th step we compute the coefficients of (h^{k} · q′)(T) modulo q(T) from the coefficients of (h^{k−1} · q′)(T) modulo q(T). Then we clear from our memory space all coefficients of (h^{k−1} ·q′)(T) modulo q(T), except the (δ − 1)–th one. In case 1 < k < δ we proceed to compute then in the same way the coefficients of (h^{k+1} · q′)(T) modulo q(T).

During this procedure only the element α and the coefficients of the polynomials h(T), q(T) are stored permanently, while for 1 ≤ k ≤ δ the (δ − 1)–th coefficients of the polynomials (h^{k}q)(T) modulo q(T) are computed (and stored). As we have seen before, these coefficients are the elements tr((αN)), …, tr((αN)^{δ}). Obviously this procedure can be performed in additional space O(δ) and time O(δ^{2} log δ log log δ). From tr((αN)), …, tr((αN)^{δ}) we obtain the coefficients of χ_{αN}(T) in additional constant space and time O(δ) by means of the Newton Relations. The coefficients of χ_{αN}(αT) are now easily computed multiplying the coefficients of χ_{αN}(T) by suitable powers of α. Again this can be done in constant space and time O(δ). Summing up the complexities of all these steps, we see that our procedure yields a straight–line program for the desired output, which can be evaluated in space O(Sδ) and time O((T + δ)δ log δ log log δ) = O(T δ^{2} log δ log log δ).

4.1.2 The Newton–Hensel iteration

The just proved Lemma 8 is the key algorithmic result we are going to apply to the Newton–Hensel iteration procedure described at the beginning of this section. First of all, we establish a suitable version of the Vermeidung von Divisionen procedure of [Str73], with the following refined complexity bounds:

Lemma 9 Let F := {F_{0}, …, F_{m}} be a finite set of polynomials of Q [Y_{1}, …, Y_{n}] of degree at most δ, computed by a straight–line program β in space S and time T . Assume F_{0} ≠ 0 and that F_{0} divides F_{i} in Q [Y_{1}, …, Y_{n}] for any 1 ≤ i ≤ m. Then there exists a straight–line program that computes the polynomials

P_{1} := \frac{F_{1}}{F_{0}} , …, P_{m} := \frac{F_{m}}{F_{0}}

in space O(Sδ) and time O((T + log δ)δ log δ log log δ) = O(T δ log^{2} δ log log δ)

Proof.– This proof is an adaptation of an idea of [KP96]. Let be given an integer point γ := (γ_{1}, …, γ_{n}) ∈ ZZ^{n} such that ρ := F_{0}(γ) ≠ 0 holds (observe that, using the Zippel–Schwartz test, such a point can be found, e.g. in the hypercube [1, 2δ]^{n} ∩ZZ^{n}, at an average cost of space S and time 2T ).

For 1 ≤ i ≤ m, let us write G_{i}(Y_{1}, …, Y_{n}) := F_{i}(Y_{1} + γ_{1}, …, Y_{n} + γ_{n}) . One easily sees that the polynomial P_{i}(Y_{1} + γ_{1}, …, Y_{n} + γ_{n}) = \frac{F_{i}(Y_{1}+γ_{1},...,Y_{n}+γ_{n})}{F_{0}(Y_{1}+γ_{1},...,Y_{n}+γ_{n})} can be computed as the sum of the first δ + 1 homogeneous components of the polynomial \frac{G_{i}}{ρ} ∑_{k=0}^{δ} (\frac{ρ−G_{0}}{ρ} )^{k}. Note that this latter polynomial can be computed by means of a straight–line program in space O(S) and time O(T + log δ).

For the decomposition of a polynomial given by a straight–line program into its homogeneous components we follow an idea of [Mat97a], which reduces the task to polynomial arithmetic in Q [Y_{1}, …, Y_{n}][T] modulo T^{δ+1}. Applying FFT–based polynomial multiplication (see [BP94]), we obtain a straight–line program that performs the Vermeidung von Divisionen procedure using space O(Sδ) and time O((T + log δ)δ log δ log log δ)), just as claimed in the statement of Lemma 9.

We are going now to show a technical lemma which we need for our analysis of the Newton–Hensel iteration.

Lemma 10 Let R be the polynomial ring Q [Y_{1}, …, Y_{n−r}] and let K be its quotient field. Let β be a straight–line program in Q [Y_{1}, …, Y_{n−r}] = R that computes the coefficients of two univariate polynomials p(T), q(T) ∈ R[T] with q(T) ≠ 0 in space S and time T . Let u(T), v(T) be two coprime polynomials of K[T] and assume that \frac{p}{q} = \frac{v}{w} and deg_{T} u = δ and deg_{T} v ≤ δ holds and that u(T) is monic in T. Then, there exists a straight–line program in Q [Y_{1}, …, Y_{n−r}] = R that computes a nonzero element γ ∈ R and a γ–multiple of the coefficients of u in space O(S + δ) and time O(T + δ^{2} log δ log log δ).

Proof.– Using the Zippel–Schwartz test we may assume by the same argument as in the proof of Lemma 9 that there is given an element t of Q with q(t) ≠ 0. Let u(T) = T^{δ} + u_{δ−1}T^{δ−1} + ⋯ + u_{0} with u_{δ−1}, …, u_{0} ∈ K. Following [BP94, Remark 2.9.1] we consider the power series representation of the rational function

\frac{v((T −t)^{−1})}{(T −t)u((T −t)^{−1})} with respect to the variable (T − t), namely

\frac{v((T − t)^{−1})}{(T − t)u((T − t)^{−1})} = \frac{p((T − t)^{−1})}{(T − t)q((T − t)^{−1})} = ∑_{i=0}^{+∞} h_{i}(T − t)^{i}.  (3)

Then, by [BP94, Proposition 2.9.1], we have the following identity:

( \begin{matrix}h_{0} & h_{1} & … & h_{δ−1} \\ h_{1} & h_{2} & … & h_{δ} \\ ⋮ & ⋮ & & ⋮ \\ h_{δ−1} & h_{δ} & … & h_{2δ−2} \end{matrix} ) ( u_{0} ; u_{1} ; ⋮ ; u_{δ−1} ) = − ( h_{δ} ; h_{δ+1} ; ⋮ ; h_{2δ−1} )  (4)

Without loss of generality we may assume p ≠ 0 and hence (h_{0}, …, h_{2δ−1}) ≠ 0. Now we apply the algorithm of Sieveking–Kung in order to compute an element ρ ∈ R and an γ := ρ^{δ}–multiple of the first 2δ coefficients h_{0}, …, h_{2δ−1} of (3) in additional space O(δ) and time O(δ log^{2} δ log log δ). Notice that the solution (u_{0}, …, u_{δ−1}) of the linear equation system (4) does not change if we substitute the elements h_{0}, …, h_{2δ−1} by their nonzero multiples γh_{0}, …, γh_{2δ−1}. Since the matrix appearing in (4) is of Hankel type, we can solve the system (4) applying the technique of linear recurring sequences in additional space O(δ) and additional time O(δ^{2} log δ log log δ) (see e.g. [SL92]). In order to avoid divisions by elements of R we can modify slightly this classical algorithm and obtain as result a nonzero element γ of R such that γu_{0}, …, γu_{δ−1} are elements of R forming a solution of the system (4).

Let us now turn back to the situation at the beginning of this section. We retake the notation and the assumptions introduced at this place. We attack now the main task of this subsection by the design of an algorithm which performs σ = ⌊log(Dδ_{r})⌋ + 1 iterations of the Newton–Hensel operator space and time which are, roughly speaking, only quadratic and cubic in δ_{r}.

Theorem 11 Let notations and assumptions be as at the beginning of this section. The coefficients of the minimal polynomial q_{F} ∈ Q [Y_{1}, …, Y_{n−r}][T] satisfying the condition q_{F} (Y_{1}, …, Y_{n−r}, F) ∈ (F_{1}, …, F_{r}) can be computed from a given geometric solution of the lifting fiber V_{P^{(r)}} by a straight–line program in Q [Y_{1}, …, Y_{n−r}] using space O(SrDδ_{r}^{2}) and time O((T rD + r^{4})Dδ_{r}^{3} log^{3} δ_{r} log^{2} log δ_{r}).

Proof.– We follow the strategy of [GHH^{+}97] as outlined in the Introduction, using for this purpose the procedures described in the proofs of Lemma 8 and Lemma 9.

Using a linear space straight–line program version of Samuelson’s algorithm for the computation of the determinant (see [FF63] or [Abd97]), we first compute without divisions numerators g_{n−r+1}, …, g_{n} and a denominator h of the rational functions \frac{g_{n−r+1}}{h} , …, \frac{g_{n}}{h} which represent the σ = ⌊log(Dδ_{r})⌋ + 1 iterations of the Newton– Hensel operator. Following the general lines of [GHH^{+}97, Lemma 27] this can be done in space O(Sr) and time O((T r + r^{4}) log(Dδ_{r})).

Let us denote by g_{n−r+1}^{(r)}(T), …, g_{n}^{(r)}(T), h^{(r)}(T) the polynomials of Q[Y_{1}, …, Y_{n−r}][T] resulting from the specialization of the variables Y_{n−r+1}, …, Y_{n} occurring in the polynomials g_{n−r+1}, …, g_{n}, h into the “parametrizing” polynomials v_{n−r+1}^{(P^{(r)})}(T), …, v_{n}^{(P^{(r)})}(T) of the lifting fiber V_{P^{(r)}}. In Subsection 4.1 we have shown that the matrix h(v_{n−r+1}^{(P^{(r)})}(M), …, v_{n}^{(P^{(r)})}(M)), we obtain specializing in h(Y_{1}, …, Y_{n}) the variables Y_{n−r+1}, …, Y_{n} into the matrices v_{n−r+1}^{(P^{(r)})}(M), …, v_{n}^{(P^{(r)})}(M), represents an invertible element of the matrix ring Q [Y_{1}, …, Y_{n−r}]_{(Y_{1}−p_{1}^{(r)},...,Y_{n−r}−p_{n−r}^{(r)})}^{δ_{r}×δ_{r}} (recall that M denotes the companion matrix of the polynomial q^{(P^{(r)})}(T)). This implies that h^{(r)}(T) is a unit in Q [Y_{1}, …, Y_{n−r}]_{(Y_{1}−p_{1}^{(r)},...,Y_{n−r}−p_{n−r}^{(r)})}[T]/q^{(P^{(r)})}(T).

Now we consider in Q [Y_{1}, …, Y_{n−r}]_{(Y_{1}−p_{1}^{(r)},...,Y_{n−r}−p_{n−r}^{(r)})}[T] the rational function

f^{(r)} := F (Y_{1}, …, Y_{n−r}, \frac{g_{n−r+1}^{(r)}(T)}{h^{(r)}(T)}, …, \frac{g_{n}^{(r)}(T)}{h^{(r)}(T)})

modulo the polynomial q^{(P^{(r)})}(T). For this purpose, we compute the homogeneous decomposition

∑_{k=0}^{d} F_{k}(Y_{1}, …, Y_{n−r}, Y_{n−r+1}, …, Y_{n})

of F (Y_{1}, …, Y_{n}), which we consider as a polynomial in the variables Y_{n−r+1}, …, Y_{n} with coefficients from Q [Y_{1}, …, Y_{n−r}]. This decomposition can be computed by means of the procedure described in the proof of Lemma 9 using space O(SD) and time O(T D log D log log D). Considering in Q [Y_{1}, …, Y_{n−r}]_{(Y_{1}−p_{1}^{(r)},...,Y_{n−r}−p_{n−r}^{(r)})}[T] the following identities:

\begin{matrix}f^{(r)} = & F (Y_{1}, …, Y_{n−r}, \frac{g_{n−r+1}^{(r)}(T)}{h^{(r)}(T)}, …, \frac{g_{n}^{(r)}(T)}{h^{(r)}(T)}) \\ = & ∑_{k=0}^{D} F_{k} (Y_{1}, …, Y_{n−r}, \frac{g_{n−r+1}^{(r)}(T)}{h^{(r)}(T)}, …, \frac{g_{n}^{(r)}(T)}{h^{(r)}(T)}) \\ = & ∑_{k=0}^{D} \frac{F_{k} (Y_{1}, …, Y_{n−r}, g_{n−r+1}^{(r)}(T), …, g_{n}^{(r)}(T))}{(h^{(r)}(T))^{k}} \\ = & \frac{∑_{k=0}^{D} F_{k} (Y_{1}, …, Y_{n−r}, g_{n−r+1}^{(r)}(T), …, g_{n}^{(r)}(T)) (h^{(r)}(T))^{D−k}}{(h^{(r)}(T))^{D}} , \end{matrix}

we conclude that the numerator and denominator of the rational function f^{(r)} can be computed in space O(S(r + D)) and time O((T rD + r^{4}) log(Dδ_{r})) using only divisions by nonzero elements of Q .

Since by construction the polynomials h^{(r)}(T) and q^{(P^{(r)})}(T) are coprime in Q(Y_{1}, …, Y_{n−r})[T] we are able to apply the procedure described at the beginning of the proof of Lemma 7 in order to compute a polynomial f̃^{(r)}(T) ∈ Q [Y_{1}, …, Y_{n−r}][T] of degree in T at most δ_{r} −1 and an element α ∈ Q [Y_{1}, …, Y_{n−r}] satisfying in Q [Y_{1}, …, Y_{n−r}][T] the condition h^{(r)}(T)^{D}f^{(r)}(T) ≡ αg(T) modulo q^{(P^{(r)})}(T), with

g(T) := ∑_{1≤k≤D} F_{k}(Y_{1}, …, Y_{n−r}, g_{n−r+1}^{(r)}(T), …, g_{n}^{(r)}(T)) · h^{(r)}(T)^{D−k} .

Thus we have in Q [Y_{1}, …, Y_{n−r}]_{(Y_{1}−p_{1}^{(r)},...,Y_{n−r}−p_{n−r}^{(r)})}[T] the congruence relation

f̃^{(r)}(T) ≡ αf^{(r)}(T) modulo q^{(P^{(r)})}(T).

Since M is the companion matrix of the polynomial q^{(P^{(r)})}(T) this implies with the notations of Theorem 6:

\begin{matrix}f̃^{(r)}(M) = & αf^{(r)}(M) \\ = & αF (Y_{1}, …, Y_{n−r}, N_{n−r+1}, …, N_{n}) \\ = & αM_{F} \end{matrix} .

The polynomial f̃^{(r)}(T) and the element α can be computed by means of a straight– line program in space O(Sδ_{r}(r + D)) and time O((T rD + r^{4})δ_{r}^{2} log^{2} δ_{r} log log δ_{r}).

We have shown that αM_{F} = f̃^{(r)}(M) holds. Therefore using a similar procedure as in the proof of Lemma 8 we are able to compute α_{r}^{δ}–multiples of the coefficients of the characteristic polynomial χ(T) := χ_{M_{F}} (T) of M_{F} in space O(Sδ_{r}(r + D)) and

time O((T rD + r^{4})δ_{r}^{2} log^{2} δ_{r} log log δ_{r}). Thus, let us assume that the coefficients of the polynomial α^{δ}χ_{F} (T) are now computed.

Since the matrix M_{F} is diagonalizable it suffices to clear from the characteristic polynomial χ(T) of M_{F} the multiple factors in order to obtain the minimal polynomial q̃_{F} of M_{F} (recall the notations of Theorem 6). Therefore the monic numerator of the irreducible representation of the rational function \frac{χ(T)}{χ′(T)} = \frac{α^{δ}χ(T)}{α^{δ}χ′(T)} is in fact the minimal polynomial q̃_{F} (T) of the matrix M_{F}. Now, applying Lemma 10 to the rational function \frac{α^{δ}χ(T)}{α^{δ}χ′(T)} we compute an element γ ∈ R and a γ–multiple of the coefficients a_{0}, …, a_{deg(q_{F})} of the minimal polynomial q̃_{F} of M_{F}, such that γa_{0}, …, γa_{deg(q_{F})} are elements of R. This can be done in space O(Srδ_{r}) and time O((T rD + r^{4})δ_{r}^{2} log^{2} δ_{r} log log δ_{r}).

Taking into account the congruence relation

q_{F} ≡ q̃_{F} modulo (Y_{1} − p_{1}^{(r)}, …, Y_{n−r} − p_{n−r}^{(r)})^{Dδ_{r}}

in Q [Y_{1}, …, Y_{n−r}][T] (see Theorem 6) and the fact that deg q_{F} ≤ Dδ_{r} holds (see [SS96]), we deduce that for 1 ≤ k ≤ deg q_{F} the power series expansion of the k–th coefficient a_{k} of the polynomial q̃_{F} equals to the k–th coefficient of the polynomial q_{F}. Since the polynomials γa_{0}, …, γa_{deg(q_{F})}, γ ∈ Q [Y_{1}, …, Y_{n−r}] are already computed by a division–free straight–line program, we are finally able to compute the polynomials a_{0}, …, a_{deg(q_{F})} ∈ Q [Y_{1}, …, Y_{n−r}] by means of Lemma 9. This can be done in space O(SDrδ_{r}) and time O((T rD + r^{4})Dδ_{r}^{3} log^{3} δ_{r} log^{2} log δ_{r}).

Remark 12 In case r := n − 1, when the algebraic variety V_{r} = V_{n−1} is a curve, the algorithm underlying Theorem 11 outputs in fact the dense representation of the polynomial q_{F} (T) ∈ Q [Y_{1}, T].

Proof.– In case r := n − 1, when V_{r} = V_{n−1} has dimension one (i.e. V_{r} is a curve), we have a Noether normalization of the form Q [Y_{1}] ↪ Q [V_{n−1}]. We observe that the algorithm underlying the proof of Theorem 11 computes the elements γa_{0}, …, γa_{deg(q_{F})}, γ, which are in fact univariate polynomials of Q [Y_{1}]. Then the Vermeidung von Divisionen procedure computes the power series expansion of the rational expressions \frac{γa_{0}}{γ} , …, \frac{γa_{deg(q_{F})}}{γ} up to degree Dδ_{n−1}, producing thus the dense representation of the coefficients of the polynomial q_{F} (T) with respect to the variable T. Therefore, the algorithm underlying Theorem 11 outputs the dense representation of the polynomial q_{F} ∈ Q [Y_{1}, T].

We consider now a particular case of an application of Theorem 11 and Remark 12. This application will be used again in Subsection 5.1.

Remark 13 Let us consider the curve W_{P^{(r+1)}} := V_{r} ∩ {Y_{1} = p_{1}^{(r+1)}, …, Y_{n−r−1} = p_{n−r−1}^{(r+1)}} as a subvariety of C^{r+1}. Let ℓ ∈ Q [Y_{1}, …, Y_{n}] be a linear form such that ℓ, Y_{n−r+1}, …, Y_{n} are in Noether position with respect to the curve W_{P^{(r+1)}} and such that ℓ plays the rôle of the free variable. Assume that there is given an element a ∈ Q such that the variety V_{ℓ,a} := W_{P^{(r+1)}} ∩ {ℓ = a} is a lifting fiber of W_{P^{(r+1)}}. Assume furthermore that we have a geometric solution of the variety V_{ℓ,a}, given by polynomials q^{(ℓ,a)}, v_{n−r}^{(ℓ,a)}, …, v_{n}^{(ℓ,a)} ∈ Q [T], i.e. we assume that the following identity holds:

V_{ℓ,a} = {(v_{n−r}^{(ℓ)}(u), …, v_{n}^{(ℓ)}(u)) ∈ C^{r+1} : q^{(ℓ)}(u) = 0} .

Let be given a polynomial F ∈ Q [Y_{1}, …, Y_{n}] of total degree D by a straight–line program γ in Q [Y_{1}, …, Y_{n}]. Let f be the coordinate function induced by the polynomial F on the curve W_{P^{(r+1)}}. Then we can apply Theorem 11 in order to compute the projection of f along the “line” ℓ, i.e. the minimal (integral) dependence relation m_{F} ∈ Q [ℓ][T] satisfied by the coordinate function f. This can be done using as input the straight–line program γ computing F and the given geometric solution of V_{ℓ,a}. We shall call this procedure lifting the projection of F from V_{ℓ,a} to W_{P^{(r+1)}}.

Since W_{P^{(r+1)}} is a curve, we deduce from Remark 12 that the procedure of Theorem 11 outputs the dense representation of the polynomial m_{F} ∈ Q [ℓ, T].

The technique of lifting a projection from a zero–dimensional variety to a curve is fundamental for the main algorithm of this paper. This technique was independently discovered and applied in [GLS99].

4.2 An efficient Shape Lemma

This subsection will be devoted to the description of an efficient algorithm for the solution of the following task:

Let be given a natural number δ and let be given (by their coefficients) three nonconstant and separable polynomials f, g, h ∈ Q [T] of degree at most δ. Moreover, let be given a nonzero element α ∈ Q. Suppose that the linear form u(X, Y) := αX+Y separates the points of the zero–dimensional variety {(x, y) ∈ C^{2} : f(x) = 0, g(y) = 0} and that the variety W := {(x, y) ∈ C^{2} : f(x) = 0, g(y) = 0, h(αx + y) = 0} is nonempty. The task consists in the computation of a geometric solution of the zero–dimensional variety W.

In many elimination procedures this task appears for the special case h := 0, while the output is required to be the geometric solution of the variety W induced by the linear form u(X, Y) (see e.g. [GH93],[KP96]). In [KP96] for instance, this task is solved by linear algebra computations. From a practical point of view, this approach has the drawback of introducing additional (extraneous) points, producing in this way a quadratic growth of the size of the appearing matrices and hence also a quadratic overflow of the space and time complexity of the algorithm. In this way, the corresponding subroutine of the elimination procedure under consideration contributes with an additional quadratic growth to the overall complexity of the procedure.

In order to overcome this undesirable effect, we reformulate the original algorithmic task in the above indicated way: instead of considering zero–dimensional varieties given only by two polynomials f(X) and g(Y) in two separate variables and a linear form u(X, Y) as in [KP96], we introduce an additional condition given by the polynomial h(u(X, Y)), which eliminates the extraneous points.

In order to solve the task described above, it suffices to find only a polynomial v(T) ∈ Q [T] of degree at most δ − 1, such that X − v(h(X, Y)) vanishes on the whole variety W. Let us remark that the procedure of [KP96] computing such a polynomial v(T) requires space O(δ^{4}) and time O(δ^{8}), and this is unfeasible for our algorithmic aim. Therefore, we redesign the effective Shape Lemma version of [KP96] in such a way, that a quadratic complexity growth can be avoided. The following result represents the effective Shape lemma version we are going to use in the sequel (see Theorem 15 and Proposition 18 below).

Lemma 14 Let R be an integrally closed domain of characteristic zero which contains the field Q of rational numbers. Let K be the fraction field of R and let K̄ be an algebraic closure of K. Let W ⊂ K̄^{2} be a zero–dimensional variety and let δ := deg W = #W. Let f ∈ R[T] and g ∈ R[T] be two nonconstant and square– free polynomials of degree at most δ. Moreover, let be given a nonzero element α ∈ Q and assume that the linear form u := αX + Y separates the points of the variety W_{0} := {(x, y) ∈ K̄^{2} : f(x) = 0, g(y) = 0}. Finally let h ∈ R[T] be the minimal polynomial of the coordinate function of W induced by the linear form u. Assume that the polynomials f(T), g(T) and h(T) are given by their coefficients in R. Then there exists a nonzero element ρ ∈ R and a polynomial v(T) ∈ R[T] of degree strictly smaller than δ, such that ρX − v(u(X, Y)) vanishes on the whole variety W and such that ρ and the coefficients of v(T) can be computed by means of a essentially division–free straight–line program β in R using space O(δ^{2}) and time O(δ^{3} log^{2} δ log^{2} log δ).

Here we mean by “essentially division free” that β contains only divisions by nonzero elements of Q. Furthermore let us observe that the polynomial v(T) of the statement of Lemma 14 is uniquely determined up to scaling by nonzero elements of R. This means that there exists exactly one polynomial ṽ(T) ∈ K[T] of degree strictly smaller than δ with X − ṽ(u(X, Y)) vanishing on the whole variety W and that this polynomial is precisely ṽ(T) := \frac{1}{ρ}v(T). Proof of Lemma 14.– Let W := {γ_{1}, …, γ_{δ}} with γ_{i} = (α_{i}, β_{i}) ∈ K̄^{2} for 1 ≤ i ≤ δ. By assumption the polynomial h(u(X, Y)) vanishes on the whole variety W. Since u(X, Y) separates the points of the variety W_{0} (and hence those of W) and since deg h(T) = δ holds, we conclude h(T) = ∏_{1≤i≤δ}(T −u(γ_{i})). From the assumption that

the linear form u(X, Y) separates the points of the variety W and from δ = deg W one deduces easily the existence of a uniquely determined polynomial ṽ(T) ∈ K[T] of degree strictly less than δ with X − ṽ(u(X, Y)) vanishing on the whole variety W (this is the standard form of the Shape–Lemma, see e.g. [Kro82], [Mac16] and [GM89]).

Fix for the moment an arbitrary index 1 ≤ i ≤ δ. We show first the following statement: Claim: The greatest common divisor (gcd) of the polynomials f(X) and g(u(γ_{i}) − αX) of K̄[X] is the linear form X −ṽ(u(γ_{i})) (in symbols: X −ṽ(u(γ_{i})) = gcd(f(X), g(u(γ_{i}) − αX))).

Proof of the Claim.– Since the polynomial X−ṽ(u(X, Y)) vanishes on the variety W, we deduce from (α_{i}, β_{i}) = γ_{i} ∈ W the identity α_{i} − ṽ(u(γ_{i})) = α_{i} − v(u(α_{i}, β_{i})) = 0. Moreover we have f(α_{i}) = 0 and by u(γ_{i}) = αα_{i} +β_{i} also g(u(γ_{i})−αα_{i}) = g(β_{i}) = 0.

The identity α_{i} = ṽ(u(γ_{i})) implies now that ṽ(u(γ_{i})) is a common root of f(X) and g(u(γ_{i}) − αX). Therefore the linear form X − ṽ(u(γ_{i})) divides the greatest common divisor of these polynomials. In order to finish the proof of the Claim, it suffices to show that ṽ(u(γ_{i})) is the unique common root of f(X) and g(u(γ_{i}) − αX) (recall that f(X) is by assumption square–free).

Let μ ∈ K̄ be any common root of these polynomials. Then, the point γ̃ := (μ, u(γ_{i}) − αμ) belongs to the variety W_{0}, defined by the polynomials f(X) and g(Y). Since by assumption the linear form u(X, Y) = αX + Y separates the points of the variety W_{0} we deduce from the identity u(γ̃) = u(γ_{i}) that γ̃ = γ_{i} holds. This finishes the proof of the Claim.

From the statement of the Claim we deduce immediately that in K̄[T] the identity

\begin{matrix}h(T) = & ∏_{1≤i≤δ} (T − v(U(γ_{i}))) \\ = & ∏_{1≤i≤δ} gcd (f(T), g(U(γ_{i}) − αT)) \end{matrix}

holds.

This implies that the first principal subresultant P_{1}(u) ∈ K[u] of the Sylvester matrix of the polynomials f(T) and g(u − αT) does not vanish on any root of h(u) (here we treat the linear form u as an indeterminate). Therefore the residue class of P_{1}(u) in K[u]/(h(u)) is a unit.

Taking into account that the variety W is contained in the variety W_{0} (defined by f(X) and g(Y)), that the linear form u(X, Y) separates the points of W_{0} and that by definition h(T) is the minimal polynomial of the coordinate function of W induced by the linear form u, one sees easily that the variety W is definable by the equations f(X) = 0, g(Y) = 0, h(u(X, Y)) = 0. Let I := (f(X), g(Y), h(u(X, Y))) be the ideal generated by these polynomials in K[X, Y]. Since by assumption f(X) and g(Y) are square–free, I is radical and hence the vanishing ideal of the variety W.

Therefore the polynomial X − ṽ(u(X, Y)) belongs to the ideal I = (f(X), g(Y), h(u(X, Y))) (recall that this polynomial vanishes on the variety W). This implies that there exist polynomials r(X), s(X) of K[u]/(h(u))[X] such that in this polynomial ring the identity

X − ṽ(u) = r(X)f(X) + s(X)g(u − αX)  (5)

holds. Without loss of generality we may assume

deg_{X} r = deg_{X}(g(u − αX)) − 1 and deg_{X} s = deg_{X}(f(X)) − 1  (6)

Since the residue class of P_{1}(u) in K[u]/(h(u)) is a unit, the coefficients of r(X) and s(X) are uniquely determined by the identities (5) and (6).

If we are able to find polynomials r(X), s(X) ∈ K[u]/(h(u))[X] satisfying the identities (5) and (6) we obtain easily ṽ(u) as the constant term of the polynomial

r(X)f(X) + s(X)g(u − αX)

in K[u]/(h(u))[X].

In order to compute the Bezout identity (5) subject to condition (6) we use the algorithms of [SL92] or [Col67]. These algorithms return as output a multiple w(u) of the Bezout identity (5), namely a representation

w(u)X − v̂(u) = r̃(X)f(X) + s̃(X)g(u − αX),  (7)

with polynomials r̃, s̃ ∈ K[u]/(h(u))[X] having degree deg_{X}(g(u − αX)) − 1 and deg_{X}(f(X)) − 1 respectively and w(u), v̂(u) belonging to K[u]/(h(u)). Without loss of generality we may assume that w(u) and v̂(u) are polynomials in the variable u (i.e. elements of K[u]) which are reduced modulo h(u). If gcd (w(u), h(u)) = 1 holds, we can invert w(u) modulo h(u) in order to satisfy conditions (5) and (6) with w(u)ṽ(u) ≡ v̂(u) modulo h(u). If gcd (w(u), h(u)) is a nonconstant polynomial w_{1}(u) of K[u], we claim that w_{1}(T) divides v̂(T). Since the polynomial h(T) is separable and w_{1}(T) divides this polynomial, we conclude that w_{1}(T) is separable too. Thus, if w_{1}(T) does not divide v̂(T), there exists a root τ of w_{1}(T) with v̂(τ) ≠ 0. Since w_{1}(T) divides h(T) = ∏_{1≤i≤δ}(T − u(γ_{i})) there exists 1 ≤ i ≤ δ such that the root τ is of the form u(γ_{i}). Thus, we have w(u(γ_{i})) = 0 and v̂(u(γ_{i})) ≠ 0. Since u(γ_{i}) is a root of h(T) we may “specialize” in identity (7) the residue class of u modulo h(u) into the value u(γ_{i}). Doing this we deduce from (7) that the polynomials f(X) and g (u(γ_{i}) − αX) are coprime, which contradicts the statement of the Claim above. Thus w_{1}(T) = gcd(w(T), h(T)) divides v̂(T). This allows to compute the polynomial ṽ(u) of the identity (5) in an analogous way as before from

the polynomial \frac{v̂(u)}{w_{1}(u)}.

The computation of the polynomial ṽ(u) satisfying conditions (5) and (6) above can be done by O(δ^{2} log δ log log δ) arithmetic operations in K[u]/(h(u)) using space O(δ). Performing these arithmetic operations by FFT–based algorithms as in [BP94], we obtain a straight–line program β̃ in K (containing divisions) which computes the coefficients of the polynomial ṽ(T). Computing numerators and denominators in β̃ separately, we get an essentially division–free straight–line program β in R which computes a nonzero element ρ ∈ R and the coefficients of a polynomial v(T) ∈ R[T] of the same degree as ṽ(T) such that \frac{1}{ρ}v(T) = ṽ(T) holds. It is now clear that ρX − v(u(X, Y)) vanishes on the whole variety W, and that β has essentially the same space and time complexity as β̃. Thus β satisfies the requirements of Lemma 14.

4.3 Lifting of a zero–dimensional fiber

In this subsection we shall develop an algorithm which, given a geometric solution of the lifting fiber V_{P^{(r)}} as input, computes a geometric solution of the algebraic variety V_{r} as output. For this purpose we shall follow the strategy of [KP96], in combination with our tools developed in Subsections 4.1 and 4.2.

In the sequel we shall use the following notations and conventions: let be given the linear form U^{(r)} := λ_{n−r+1}^{(r)}Y_{n−r+1} + ⋯ + λ_{n}^{(r)}Y_{n} which induces a primitive element of V_{P^{(r)}} (and hence of the integral Q –algebra extension Q [Y_{1}, …, Y_{n−r}] ↪ Q [V_{r}]) and let be given the coefficients of the polynomials q^{(P^{(r)})}, v_{n−r+1}^{(P^{(r)})}, …, v_{n}^{(P^{(r)})} ∈ Q [T] introduced in Subsection 4.1 for the representation of a geometric solution of the lifting fiber V_{P^{(r)}}. Following [KP96], we define for 1 ≤ j ≤ r linear form Z_{j}^{(r)} := U^{(r)} −λ_{n−r+j}^{(r)}Y_{n−r+j} and denote by q̃_{j}^{(r)} ∈ Q[Y_{1}, …, Y_{n−r}][T] the minimal polynomial of the coordinate function of V_{r} induced by Z_{j}. Furthermore, let us denote by q^{(r)} and q_{1}^{(r)}, …, q_{r}^{(r)} ∈ Q [Y_{1}, …, Y_{n−r}][T] the minimal polynomials of the coordinate functions of V_{r} induced by the linear forms U^{(r)} and Y_{n−r+1}, …, Y_{n}. With the notations of Lemma 14 above, let R := Q [Y_{1}, …, Y_{n−r}], K := Q (Y_{1}, …, Y_{n−r}) and let K̄ be an algebraic closure of K. In the proof of Theorem 15 below we are going to apply for each 1 ≤ j ≤ r the algorithm underlying the statement Lemma 14 to the zero–dimensional algebraic variety W_{j}^{(r)} := {(y, z) ∈ K̄^{2} : q_{j}^{(r)}(y) = 0, q̃_{j}^{(r)}(z) = 0}.

Under the assumption that the coefficient vector of the linear form U^{(r)} satisfies a certain genericity condition, it was shown in [KP96, Proposition 29] that a Shape–Lemma–like representation of each algebraic variety W_{1}^{(r)}, …, W_{r}^{(r)} produces “parametrizing” polynomials ρ_{n−r+1}^{(r)}Y_{n−r+1} − v_{n−r+1}^{(r)}(T), …, ρ_{n}^{(r)}Y_{n} − v_{n}^{(r)}(T) of Q[Y_{1}, …, Y_{n−r}][T] required for a geometric solution of the variety V_{r} (here we use the coordinate function of V_{r} induced by the linear form U^{(r)} as a primitive element with minimal polynomial q^{(r)}(T)).

Therefore, the problem of computing a geometric solution of V_{r} is reduced to the following two tasks: the lifting of a projection (in the sense of Subsection 4.1) and the computation of a Shape–Lemma–like representation (in the sense of Subsection 4.2). These two tasks are solved in Theorem 11 and in Lemma 14. The next result will illustrate this idea.

Theorem 15 Let notations and assumptions be as before. In particular, let be given a linear form U^{(r)} ∈ Q [Y_{n−r+1}, …, Y_{n}] inducing a primitive element of the lifting fiber V_{P^{(r)}}. Then there exists a straight–line program in Q [Y_{1}, …, Y_{n−r}], computing from (the coefficients of) a given geometric solution of the lifting fiber V_{P^{(r)}} and the given linear form U^{(r)} the coefficients of a geometric solution of the algebraic variety V_{r}. This straight–line program uses space O(Srδ_{r}^{2}) and time O((T r^{2} + r^{5})δ_{r}^{3} log^{3} δ_{r} log^{2} log δ_{r}).

Proof.– Assume that there is given as before a geometric solution of the lifting fiber V_{P^{(r)}}. Applying Theorem 11 we are then able to compute the coefficients of the minimal integral dependence relations q^{(r)}(T), q_{1}^{(r)}(T), …, q_{r}^{(r)}(T), q̃_{1}^{(r)}(T), …, q̃_{r}^{(r)}(T) of the coordinate functions of V_{r} induced by the linear forms U^{(r)}, Y_{n−r+1}, …, Y_{n} and Z_{1}^{(r)}, …, Z_{r}^{(r)} . Then, for 1 ≤ j ≤ r, we apply Lemma 14 to the zero–dimensional variety W_{j}^{(r)} and the polynomials q^{(r)}, q_{j}^{(r)} and q̃_{j}^{(r)} in order to compute the coefficients of a polynomial having the form ρ_{n−r+j}^{(r)}Y_{n−r+j}−v_{n−r+j}^{(r)}(T) ∈ Q[Y_{1}, …, Y_{n−r}][T] with ρ_{n−r+j}^{(r)} ≠ 0 and deg_{T} v_{n−r+j}^{(r)}(T) < δ_{r}, such that U^{(r)}, q^{(r)}(T) and ρ_{n−r+1}^{(r)}Y_{n−r+1}− v_{n−r+1}^{(r)}(T), …, ρ_{n}^{(r)}Y_{n} − v_{n}^{(r)}(T) form a geometric solution of the variety V_{r}. From the complexity estimates of Theorem 11 and Lemma 14 we deduce now easily the complexity statement of Theorem 15.

Theorem 15 has its own interest. Unfortunately, in the sequel we shall not be able to apply Theorem 15 directly since we have no control over the coefficients ρ_{n−r+1}^{(r)}, …, ρ_{n}^{(r)} produced by the application of Lemma 14 in the proof of Theorem 15. Therefore, we shall only apply Lemma 14 and not Theorem 15 in the future.

4.4 Minimal equations: stepping downwards on the lifting fibers

In Subsection 4.1 we have already met the task of computing a minimal integral dependence relation in Q [Y_{1}, …, Y_{n−r}][T] for the coordinate function of V_{r} induced by a given polynomial F ∈ Q [Y_{1}, …, Y_{n}]. In the present subsection we describe an efficient algorithm for the following task:

Let 1 ≤ r < n. Given a geometric solution of the lifting fiber V_{P^{(r)}} of V_{r}, compute the coefficients of the minimal equation in Q [T] of the coordinate function of the lifting fiber V_{P^{(r+1)}} induced by the linear form Y_{n−r}.

Below we present two lemmas deducing finally from them Proposition 18 which says that, under the assumptions of Theorem 5, the coefficients of the minimal equation m_{Y_{n−r}} ∈ Q [T] of the coordinate function of V_{P^{(r+1)}} induced by the linear form Y_{n−r} can be computed by a straight–line program in space O(Srdδ_{r}^{2}) and time O((T dr + r^{4})dδ_{r}^{3} log^{3} δ_{r} log^{2} log δ_{r}).

Applying the Zippel–Schwartz test in the same way as in Section 3, we deduce from Theorem 5, that by a random choice of the coefficients λ_{n−r+1}^{(r)}, …, λ_{n}^{(r)}, the linear form U^{(r)} = λ_{n−r+1}^{(r)}Y_{n−r+1} + ⋯ + λ_{n}^{(r)}Y_{n} happens to separate the points of the π_{r} – fiber of the π_{r}–image of each point of the lifting fiber V_{P^{(r+1)}}. Assume from now on that the linear form U^{(r)} has this property.

Let us consider again the curve W_{P^{(r+1)}} := V_{r} ∩ {Y_{1} = p_{1}^{(r+1)}, …, Y_{n−r−1} = p_{n−r−1}^{(r+1)}} introduced in Remark 13 and observe that W_{P^{(r+1)}} is defined by the polynomials F_{1}(Y_{1}, …, Y_{n}), …, F_{r}(Y_{1}, …, Y_{n}), Y_{1} − p^{(r+1)}, …, Y_{n−r−1} − p_{n−r−1}^{(r+1)} which form a regular sequence in Q [Y_{1}, …, Y_{n}].

The variables Y_{1}, …, Y_{n} are in Noether position with respect to this complete intersection curve, the variable Y_{n−r} being free. Therefore the canonical homomorphism Q [Y_{n−r}] ↪ Q [W_{P^{(r+1)}}] represents an integral Q –algebra extension. Moreover Q [W_{P^{(r+1)}}] is a free Q [Y_{n−r}]–module of rank δ_{r}.

Let us denote by u^{(r)} and y_{n−r} the coordinate functions of the curve W_{P^{(r+1)}} induced by the linear forms U^{(r)} and Y_{n−r}. Let us fix for the moment an arbitrary point P = (p_{1}^{(r+1)}, …, p_{n−r−1}^{(r+1)}, α_{n−r}, …, α_{n}) ∈ C ^{n} of the (nonempty) lifting fiber π_{r+1}^{−1}(P^{(r+1)}) = V_{P^{(r+1)}}. Let us consider the fiber

\begin{matrix}π_{r}^{−1}(π_{r}(P))) = & π_{r}^{−1}((p_{1}^{(r+1)}, …, p_{n−r−1}^{(r+1)}, α_{n−r})) \\ = & V_{r} ∩ \{Y_{1} = p_{1}^{(r+1)}, …, Y_{n−r−1} = p_{n−r−1}^{(r+1)}, Y_{n−r} = α_{n−r}\} \end{matrix}

which is defined by the polynomials F_{1}(Y_{1}, …, Y_{n}), …, F_{r}(Y_{1}, …, Y_{n}), Y_{1} − p_{1}^{(r+1)}, …, Y_{n−r−1}−p_{n−r−1}^{(r+1)}, Y_{n−r}−α_{n−r} of C[Y_{1}, …, Y_{n}]. From Theorem 5 iv) we deduce that the Jacobian of these polynomials vanishes nowhere on π_{r}^{−1}(π_{r}(P)). This implies that the canonical C–algebra homomorphism

C[Y_{1}, …, Y_{n−r}]_{(Y_{1}−p_{1}^{(r+1)},...,Y_{n−r−1}−p_{n−r−1}^{(r+1)},Y_{n−r}−α_{n−r})} ⟶

⟶ C[Y_{1}, …, Y_{n−r}]_{(Y_{1}−p_{1}^{(r+1)},...,Y_{n−r−1}−p_{n−r−1}^{(r+1)},Y_{n−r}−α_{n−r})}[Y_{n−r+1}, …, Y_{n}]/(F_{1}, …, F_{r})

(8)

is unramified and hence étale (recall that C[Y_{1}, …, Y_{n}]/(F_{1}, …, F_{r}) is a free C[Y_{1}, …, Y_{n−r}]–module of rank δ_{r}). Therefore we conclude that #π_{r}^{−1}(π_{r}(P)) = δ_{r} holds.

Observe that the set π_{r}^{−1}(π_{r}(P)) is contained in the curve W_{P^{(r+1)}}, and that π_{r}^{−1}(π_{r}(P)) is the fiber of the finite morphism y_{n−r} : W_{P^{(r+1)}} → C^{1} in the point α_{n−r} ∈ C (in symbols: π_{r}^{−1}(π_{r}(P)) = y_{n−r}^{−1}(α_{n−r})). Recall, that by construction, the linear form U^{(r)} separates the δ_{r} points of the fiber y_{n−r}^{−1}(α_{n−r}) = π_{r}^{−1}(π_{r}(P)) and that Q [W_{P^{(r+1)}}] is a free Q [Y_{n−r}]–module of rank δ_{r}. This implies that u^{(r)} is a primitive element of the integral Q –algebra extension Q [Y_{n−r}] → Q [W_{P^{(r+1)}}].

Let, as in Subsection 4.3, the polynomial q^{(r)} ∈ Q [Y_{1}, …, Y_{n−r}][T] represent the minimal integral dependence relation of the coordinate function of V_{r} induced by the linear form U^{(r)} and let us denote by ρ^{(r)} ∈ Q [Y_{1}, …, Y_{n−r}] the discriminant of q^{(r)}(T) with respect to the variable T. Let q^{(r,P^{(r+1)})}(Y_{n−r}, T) := q^{(r)}(p_{1}^{(r+1)}, …, p_{n−r−1}^{(r+1)}, Y_{n−r}, T). Then the polynomial q^{(r,P^{(r+1)})} belongs to Q [Y_{n−r}][T] and represents the minimal integral dependence relation of the primitive element u^{(r)} ∈ Q [W_{P^{(r+1)}}] over Q [Y_{n−r}]. Observe deg q^{(r,P^{(r+1)})} = deg_{T} q^{(r,P^{(r+1)})} = δ_{r}.

Observe furthermore that the coordinate functions y_{n−r}, u^{(r)} ∈ Q [W_{P^{(r+1)}}] define a morphism of algebraic varieties which maps W_{P^{(r+1)}} onto the plane curve defined by the polynomial q^{(r,P^{(r+1)})}(Y_{n−r}, T). This morphism is finite and has a rational inverse which may be given by a geometric solution of the curve W_{P^{(r+1)}}, with the free variable Y_{n−r} and primitive element induced by the linear form U^{(r)}. In the proofs of the next two lemmas we shall make a purely mathematical use of a particular geometric solution of W_{P^{(r+1)}}, which we shall not compute.

Observe first that ρ^{(r,P^{(r+1)})}(Y_{n−r}) := ρ^{(r)}(p_{1}^{(r+1)}, …, p_{n−r−1}^{(r+1)}, Y_{n−r}) ∈ Q [Y_{n−r}] is the discriminant of the polynomial q^{(r,p^{(r+1)})}(Y_{n−r}, T) with respect to the variable T. Let us now consider (but not compute) polynomials v_{n−r+1}^{(r,P^{(r+1)})}, …, v_{n}^{(r,P^{(r+1)})} ∈ Q[Y_{n−r}, T] which are uniquely determined by the condition

\begin{matrix}(F_{1}(p_{1}^{(r+1)}, …, p_{n−r−1}^{(r+1)}, Y_{n−r}, …, Y_{n}), …, \\ F_{r}(p_{1}^{(r+1)}, …, p_{n−r−1}^{(r+1)}, Y_{n−r}, …, Y_{n}))_{ρ^{(r,P^{(r+1)})}(Y_{n−r})} \end{matrix}

= (q^{(r,p^{(r+1)})}(Y_{n−r}, U^{(r)}), ρ^{(r,P^{(r+1)})}(Y_{n−r})Y_{n−r+1} − v_{n−r+1}^{(r,P^{(r+1)})}(U^{(r)}), …

…, ρ^{(r,P^{(r+1)})}(Y_{n−r})Y_{n} − v_{n}^{(r,P^{(r+1)})}(U^{(r)}))_{ρ^{(r,P^{(r+1)})}(Y_{n−r})}  (9)

Thus, the linear form U^{(r)} and the polynomials ρ^{(r,P^{(r+1)})} ∈ Q[Y_{n−r}] and q^{(r,P^{(r+1)})}(T), v_{n−r+1}^{(r,P^{(r+1)})}(T), …, v_{n}^{(r,P^{(r+1)})}(T) ∈ Q [Y_{n−r}][T] represent a particular geometric solution of the curve W_{P^{(r+1)}} in the sense of the Introduction. This geometric solution induces in the most obvious way a “reduction” isomorphism which maps the “rational function Q (Y_{n−r})–algebra” Q (Y_{n−r}) ⊗_{Q[Y_{n−r}]} Q [W_{P^{(r+1)}}] of W_{P^{(r+1)}} onto the

“rational function Q (Y_{n−r})–algebra” Q (Y_{n−r})[T]/(q^{(r,P^{(r+1)})}(Y_{n−r}, T)) of the curve {q^{(r,P^{(r+1)})}(Y_{n−r}, T) = 0} contained in C^{2}. This isomorphism leaves the field Q(Y_{n−r}) fixed.

We are now going to analyze this isomorphism more closely. For any polynomial F ∈ Q [Y_{1}, …, Y_{n}] inducing a coordinate function φ of Q [W_{P^{(r+1)}}] let us write

F̂ := F (p_{1}^{(r+1)}, …, p_{n−r−1}^{(r+1)}, Y_{n−r}, \frac{v_{n−r−1}^{(r,P^{(r+1)})}(Y_{n−r}, T)}{ρ^{(r,P^{(r+1)})}(Y_{n−r})}, …, \frac{v_{n}^{(r,P^{(r+1)})}(Y_{n−r}, T)}{ρ^{(r,P^{(r+1)})}(Y_{n−r})}) ∈

∈ Q [Y_{n−r}]_{ρ^{(r,P^{(r+1)})}(Y_{n−r})}[T] and let us write φ̂ for the residue class of F̂ in

Q [Y_{n−r}]_{ρ^{(r,P^{(r+1)})}(Y_{n−r})}[T]/(q^{(r,P^{(r+1)})}(Y_{n−r}, T)). We observe that F̂(y_{n−r}, u^{(r)}) and

φ̂ define rational functions of the curves W_{P^{(r+1)}} and {q^{(r,P^{(r+1)})}(Y_{n−r}, T) = 0} respectively.

In the sequel we shall denote by φ_{r+1} the coordinate function of Q [W_{P^{(r+1)}}] induced by the polynomial F_{r+1} ∈ Q [Y_{1}, …, Y_{n}] and we shall write f_{r+1}(Y_{n−r}, T) := F̂_{r+1}(Y_{n−r}, T). Thus f_{r+1}(y_{n−r}, u^{(r+1)}) and φ̂_{r+1} define rational functions of the curves W_{P^{(r+1)}} and {q^{(r,P^{(r+1)})}(Y_{n−r}, T) = 0} respectively.

Let us observe

\begin{matrix}V_{P^{(r+1)}} = & V_{r+1} ∩ \{Y_{1} = p_{1}^{(r+1)}, …, Y_{n−r−1} = p_{n−r−1}^{(r+1)}\} \\ = & V_{r} ∩ \{F_{r+1}(Y_{1}, …, Y_{n}) = 0, Y_{1} = p_{1}^{(r+1)}, …, Y_{n−r−1} = p_{n−r−1}^{(r+1)}\} \\ = & W_{P^{(r+1)}} ∩ \{F_{r+1}(Y_{1}, …, Y_{n}) = 0\} . \end{matrix}

In particular V_{P^{(r+1)}} is a zero–dimensional variety contained in the curve W_{P^{(r+1)}} and the polynomials ρ^{(r)}(Y_{1}, …, Y_{n}) and ρ^{(r,P^{(r+1)})}(Y_{n−r}) induce the same coordinate function of V_{P^{(r+1)}}.

We are going to show that this coordinate function is a unit of Q[V_{P^{(r+1)}}] (this implies then that the rational function f_{r+1}(y_{n−r}, u^{(r)}) is well defined in all points of V_{P^{(r+1)}}). Assume on the contrary that there exists a point P = (p_{1}^{(r+1)}, …, p_{n−r−1}^{(r+1)}, α_{n−r}, …, α_{n}) ∈ V_{P^{(r+1)}} such that ρ^{(r)}(p_{1}^{(r+1)}, …, p_{n−r−1}^{(r+1)}, α_{n−r}) = ρ^{(r,P^{(r+1)})}(α_{n−r}) = 0 holds. Since ρ^{(r)} is the discriminant of the polynomial q^{(r)} ∈ Q [Y_{1}, …, Y_{n−r}][T] with respect to the variable T, we deduce that q^{(r)}(p_{1}^{(r+1)}, …, p_{n−r−1}^{(r+1)}, α_{n−r}, T) = q^{(r,P^{(r)})}(α_{n−r}, T) has a multiple root.

From (8) we deduce #π_{r}^{−1}((p_{1}^{(r+1)}, …, p_{n−r−1}^{(r+1)}, α_{n−r})) = #π_{r}^{−1}(π_{r}(P)) = δ_{r}. Moreover, by construction, the linear form U^{(r)} separates the δ_{r} points of π_{r}^{−1}(π_{r}(P)). Let π_{r}^{−1}(π_{r}(P)) = {γ_{1}, …, γ_{δ_{r}}}. Then we have #{U^{(r)}(γ_{1}), …, U^{(r)}(γ_{δ_{r}})} = δ_{r} and from (9) we deduce that q^{(r)}(p_{1}^{(r+1)}, …, p_{n−r−1}^{(r+1)}, α_{n−r}, U^{(r)}(γ_{j})) = q^{(r,P^{(r)})}(α_{n−r}, U^{(r)}(γ_{j})) = 0 holds for any 1 ≤ j ≤ δ_{r}. Moreover we have deg q^{(r,P^{(r+1)})}(α_{n−r}, T) = δ_{r}. Putting all this together, we see that q^{(r,P^{(r+1)})}(α_{n−r}, T) is a separable polynomial of C[T]. This contradicts the conclusion that q^{(r,P^{(r+1)})}(α_{n−r}, T) has a multiple root. Therefore the polynomial ρ^{(r,P^{(r+1)})}(Y_{n−r}) induces a unit of Q [V_{P^{(r+1)}}] and the rational function f_{r+1}(y_{n−r}, u^{(r)}) is well defined (and finite) in all points of V_{P^{(r+1)}}.

With these definitions, notions and notations we are now ready to expose the procedure which computes the minimal polynomial m_{Y_{n−r}} ∈ Q [Y_{n−r}] of the coordinate function of V_{P^{(r+1)}} induced by the variable Y_{n−r}. We show in Lemma 16 below that the polynomial

g(Y_{n−r}) := Res_{T} (q^{(r,P^{(r+1)})}(Y_{n−r}, T), (ρ^{(r,P^{(r+1)})})^{N}(Y_{n−r})f_{r+1}(Y_{n−r}, T))

vanishes on all roots of the minimal polynomial m_{Y_{n−r}}(Y_{n−r}) (where N denotes a suitable positive integer, not exceeding dδ_{r}, which satisfies the condition (ρ^{(r,P^{(r)})})^{N} f_{r+1}(Y_{n−r}, T) ∈ Q [Y_{n−r}, T]). Perhaps the polynomial g(Y_{n−r}) vanishes also on certain roots of ρ^{(r,P^{(r+1)})})(Y_{n−r}) and might have high degree. The exact relationship between the polynomials g(Y_{n−r}) and m_{Y_{n−r}}(Y_{n−r}) is clarified in Lemma 17 below. This lemma, which says that the square–free representation a(Y_{n−r}) ∈ Q [Y_{n−r}] of the roots of g(Y_{n−r}) satisfies the condition

m_{Y_{n−r}}(Y_{n−r}) = \frac{a(Y_{n−r})}{gcd (ρ^{(r,P^{(r+1)})}(Y_{n−r}), a(Y_{n−r}))} .

Lemma 16 Let m_{Y_{n−r}} ∈ Q[Y_{n−r}] be the minimal equation satisfied by the coordinate function of V_{P^{(r+1)}} induced by the variable Y_{n−r} and let g ∈ Q [Y_{n−r}] be defined as

g(Y_{n−r}) := Res_{T} (q^{(r,P^{(r+1)})}(Y_{n−r}, T), (ρ^{(r,P^{(r+1)})})^{N}(Y_{n−r})f_{r+1}(Y_{n−r}, T))

where N is a positive integer, not exceeding dδ_{r}, such that (ρ^{(r,P^{(r+1)})})^{N}(Y_{n−r}) f_{r+1}(Y_{n−r}, T) belongs to the polynomial ring Q [Y_{n−r}, T]. Then the polynomial g vanishes on all roots of the polynomial m_{Y_{n−r}}. Moreover the polynomials m_{Y_{n−r}} and ρ^{(r,P^{(r+1)})} are coprime and the roots of the polynomial g, where ρ^{(r,P^{(r+1)})} does not vanish, are also roots of the polynomial m_{Y_{n−r}}.

Proof.– Let α ∈ C be a root of g with ρ^{(r,P^{(r+1)})}(α) ≠ 0. Then f_{r+1}(α, T) is a well defined polynomial of C[T] and there exists a complex number u_{α} satisfying the conditions q^{(r,P^{(r+1)})}(α, u_{α}) = 0 and f_{r+1}(α, u_{α}) = 0.

For 1 ≤ j ≤ r let α_{n−r+j} := \frac{v_{n−r+j}^{(r,P^{(r+1)})}(α,u_{α})}{ρ^{(r,P^{(r+1)})}(α)}. We claim that the point

(P^{(r+1)}, α, α_{n−r+1}, …, α_{n}) = (p_{1}^{(r+1)}, …, p_{n−r−1}^{(r+1)}, α, α_{n−r+1}, …, α_{n})

belongs to the lifting fiber V_{P^{(r+1)}}.

Specializing in the right hand side of the identity (9) the “variables” U^{(r)}, Y_{n−r}, Y_{n−r−1}, …, Y_{n} into the values u_{α}, α, α_{n−r+1}, …, α_{n} and observing ρ^{(r,P^{(r+1)})}(α) ≠ 0 we deduce that F_{j}(P^{(r+1)}, α, α_{n−r+1}, …, α_{n}) = 0 holds for every 1 ≤ j ≤ r (here we use the fact that the affine curves W_{P^{(r+1)}} ∩ {ρ^{(r,P^{(r+1)})}(Y_{n−r}) ≠ 0} and {q^{(r,P^{(r+1)})}(Y_{n−r}) = 0, ρ^{(r,P^{(r+1)})}(Y_{n−r}) ≠ 0} are isomorphic, while the corresponding isomorphism is ideal–theoretically expressed by the identity (9)).

Therefore the point (P^{(r+1)}, α, α_{n−r+1}, …, α_{n}) belongs to the curve W_{P^{(r+1)}}. From the definition of f_{r+1}, namely f_{r+1}(Y_{n−r}, T) = F̂_{r+1}(Y_{n−r}, T) =

= F (p_{1}^{(r+1)}, …, p_{n−r−1}^{(r+1)}, Y_{n−r}, \frac{v_{n−r−1}^{(r,P^{(r+1)})}(Y_{n−r}, T)}{ρ^{(r,P^{(r+1)})}(Y_{n−r})}, …, \frac{v_{n}^{(r,P^{(r+1)})}(Y_{n−r}, T)}{ρ^{(r,P^{(r+1)})}(Y_{n−r})})

we deduce 0 = f_{r+1}(α, u_{α}) = F_{r+1}(P^{(r+1)}, α, α_{n−r+1}, …, α_{n}) and this finally implies that the point (P^{(r+1)}, α, α_{n−r+1}, …, α_{n}) belongs to the variety V_{P^{(r+1)}} = W_{P^{(r+1)}} ∩ {F_{r+1}(Y_{1}, …, Y_{n}) = 0}. From (P^{(r+1)}, α, α_{n−r+1}, …, α_{n}) ∈ V_{P^{(r+1)}} we deduce that m_{Y_{n−r}}(α) = 0 holds. Thus any root of the polynomial g, where ρ^{(r,P^{(r+1)})} does not vanish, is a root of m_{Y_{n−r}}.

Let now α ∈ C be a root of m_{Y_{n−r}} with ρ^{(r,P^{(r+1)})}(α) ≠ 0. Then there exist complex numbers α_{n−r+1}, …, α_{n} such that the point (P^{(r+1)}, α, α_{n−r+1}, …, α_{n}) belongs to the lifting fiber V_{P^{(r+1)}}. Consider u_{α} := U^{(r)}(α_{n−r+1}, …, α_{n}) = λ_{n−r_{1}}^{(r)}α_{n−r+1} + ⋯ + λ_{n}^{(r)}α_{n}. Using again identity (9) and observing ρ^{(r,P^{(r+1)})}(α) ≠ 0 we conclude that

q^{(r,P^{(r+1)})}(α, u_{α}) = 0 and that α_{n−r+j} = \frac{v_{j}^{(r,P^{(r+1)})}(α, u_{α})}{ρ^{(r,P^{(r+1)})}(α)} holds for any 1 ≤ j ≤ r. In

the same manner as before, we deduce from the definition of f_{r+1} that f_{r+1}(α, u_{α}) is well defined and that f_{r+1}(α, u_{α}) = F_{r+1}(P^{(r+1)}, α, α_{n−r+1}, …, α_{n}) = 0 holds (recall that (P^{(r+1)}, α, α_{n−r+1}, …, α_{n}) belongs to V_{P^{(r+1)}}). Thus u_{α} is a common root of q^{(r,P^{(r+1)})}(α, T) and ρ^{(r,P^{(r+1)})}(α)^{N}f_{r+1}(α, T). This implies g(α) = 0. Therefore any root of m_{Y_{n−r}}, where ρ^{(r,P^{(r+1)})} does not vanish, is a root of the polynomial g.

Finally recall that we have shown that the coordinate function of Q[V_{P^{(r+1)}}] induced by the polynomial ρ^{(r,P^{(r+1)})}(Y_{n−r}) is a unit of Q [V_{P^{(r+1)}}]. Thus ρ^{(r,P^{(r+1)})}(Y_{n−r}) vanishes nowhere on the lifting fiber V_{P^{(r+1)}}. In particular there is no root of m_{Y_{n−r}} where ρ^{(r,P^{(r+1)})} vanishes. This implies that m_{Y_{n−r}} and ρ^{(r,P^{(r+1)})} are coprime and therefore g vanishes on all roots of m_{Y_{n−r}}.

For the statement of the next Lemma we need the following considerations: we have seen before that the “rational function Q (Y_{n−r})–algebras” Q (Y_{n−r}) ⊗_{Q[Y_{n−r}]}

Q [W_{P^{(r+1)}}] and Q (Y_{n−r})[T]/(q^{(r,P^{(r+1)})}(Y_{n−r}, T)) are isomorphic. The canonical isomorphism of these algebras maps 1 ⊗ φ_{r+1} to φ̂_{r+1}, where φ_{r+1} is the coordinate function of W_{P^{(r+1)}} induced by the polynomial F_{r+1}(Y_{1}, …, Y_{n}) and φ̂_{r+1} is the residue class of f_{r+1} in Q (Y_{n−r})[T](q^{(r,P^{(r+1)})}(Y_{n−r}, T)).

The homothesies η_{F_{r+1}} and η_{f_{r+1}} defined by multiplication by φ_{r+1} and φ̂_{r+1} in the Q[Y_{n−r}]–algebra Q[W_{P^{(r+1)}}] and the Q(Y_{n−r})–algebra Q(Y_{n−r})[T](q^{(r,P^{(r+1)})}(Y_{n−r}, T)) have the same characteristic and minimal polynomials. We denote the minimal polynomial of η_{f_{r+1}} by m_{f_{r+1}}. The coefficients of the minimal polynomial m_{f_{r+1}} belong to Q [Y_{n−r}] and the total degree of m_{f_{r+1}} is bounded by dδ_{r} (see [SS96]). Let us denote by a(Y_{n−r}) ∈ Q [Y_{n−r}] the square–free representation of the roots of the constant term of m_{f_{r+1}} (with respect to the main variable) and observe that deg a(Y_{n−r}) ≤ dδ_{r} holds. Then we have the following result:

Lemma 17 With notations and assumptions introduced before, we have the identity:

m_{Y_{n−r}} = \frac{a(Y_{n−r})}{gcd (ρ^{(r,P^{(r+1)})}(Y_{n−r}), a(Y_{n−r}))} .

Proof.– Let g(Y_{n−r}) ∈ Q [Y_{n−r}] be the polynomial of Lemma 16 and let ã(Y_{n−r}) ∈ Q [Y_{n−r}]be the square–free representation of the roots of g(Y_{n−r}). By Lemma 16, the roots of g and of m_{Y_{n−r}}, which are not roots of ρ^{(r,P (r+1))}, coincide. Thus the polynomials ã and m_{Y_{n−r}} vanish on the same non–roots of ρ^{(r,P^{(r+1)})}.

On the other hand the polynomials m_{Y_{n−r}} and ρ^{(r,P^{(r+1)})} are coprime. Since m_{Y_{n−r}} is square–free we have therefore the identity

m_{Y_{n−r}}(Y_{n−r}) = \frac{ã(Y_{n−r})}{gcd (ρ^{(r,P^{(r+1)})}(Y_{n−r}), ã(Y_{n−r}))} .

From the definition of the polynomial g we deduce that in Q (Y_{n−r})[T] the identity

g(Y_{n−r}) = ρ^{(r,P^{(r+1)})}(Y_{n−r})^{Nδ_{r}}Res_{T} (q^{(r,P^{(r+1)})}(Y_{n−r}, T), f_{r+1}(Y_{n−r}, T))

holds.

Applying in the same way as in [GVRR97] Stickelberger’s Theorem, we see that \frac{g(Y_{n−r})}{ρ^{(r,P^{(r+1)})}(Y_{n−r})^{Nδr}} = Res_{T} (q^{(r,P^{(r+1)})}(Y_{n−r}, T), f_{r+1}(Y_{n−r}, T)) is in fact the constant term of the characteristic polynomial of the homothesy η_{f_{r+1}}. Since the homothesies η_{f_{r+1}} and η_{φ_{r+1}} have the same characteristic polynomial we deduce that \frac{g(Y_{n−r})}{ρ^{(r,P^{(r+1)})}(Y_{n−r})^{Nδr}} is a polynomial of Q[Y_{n−r}]. Since the constant terms of the characteristic and of the minimal polynomial of η_{f_{r+1}} (and of η_{φ_{r+1}}) have the same roots, we conclude that the polynomial a(Y_{n−r}) ∈ Q[Y_{n−r}] is the square–free representation of the roots of both of them. Taking into account that the polynomial \frac{g(Y_{n−r})}{ρ^{(r,P^{(r+1)})}(Y_{n−r})^{Nδr}} is the constant term of the characteristic polynomial of the homothesy η_{f_{r+1}} we deduce that the identity

\frac{a(Y_{n−r})}{gcd (ρ^{(r,P^{(r+1)})}(Y_{n−r}), a(Y_{n−r}))} = \frac{ã(Y_{n−r})}{gcd (ρ^{(r,P^{(r+1)})}(Y_{n−r}), ã(Y_{n−r}))} = m_{Y_{n−r}}(Y_{n−r})

holds. This implies the statement of the lemma.

We now exhibit an efficient procedure for the computation of the minimal polynomial m_{Y_{n−r}}.

Proposition 18 Let notations and assumptions be as before. Suppose that there is given a geometric solution of the lifting fiber V_{P^{(r)}}. Then it is possible to compute in space O(Srδ_{r}^{2}) and time O((T dr^{2} + r^{5})dδ_{r}^{3} log^{3} δ_{r} log^{3} log^{2} δ_{r}) the coefficients of the minimal polynomial m_{Y_{n−r}} of the coordinate function of V_{P^{(r+1)}} induced by the variable Y_{n−r}.

Proof.– First of all, we observe that the discriminant ρ^{(r,P^{(r+1)})}(Y_{n−r}) of the polynomial q^{(r,P^{(r+1)})}(Y_{n−r}, T) ∈ Q [Y_{n−r}][T] with respect to the variable T is a nonzero polynomial of Q [Y_{n−r}] of degree at most δ_{r}^{2}. Let κ be a fixed natural number. Applying the Zippel–Schwartz test in the same way we did in the proof of Theorem 5, we may choose an element η of the set {1, …, κδ^{2}} such that ρ^{(r,P^{(r+1)})}(η) ≠ 0 holds with probability of success at least 1 − \frac{1}{κ}.

It is clear that η is a lifting point of the curve W_{P^{(r+1)}} and that the zero–dimensional variety V_{Y_{n−r},η}^{(r+1)} := W_{P^{(r+1)}} ∩ {Y_{n−r} = η} is the lifting fiber of the lifting point η.

We have seen before that the coordinate function u^{(r)} of the curve W_{P^{(r+1)}}, induced by the linear form U^{(r)}, is a primitive element of the integral Q –algebra extension Q [Y_{n−r}] ↪ Q [W_{P^{(r+1)}}]. Since q^{(r,P^{(r+1)})}(Y_{n−r}, T) is the minimal integral dependence relation satisfied by u^{(r)} over Q [Y_{n−r}] and since ρ^{(r,P^{(r+1)})}(Y_{n−r}) is the discriminant of q^{(r,P^{(r+1)})} we deduce from ρ^{(r,P^{(r+1)})}(η) ≠ 0 that the coordinate function of the zero–dimensional variety V_{Y_{n−r},η}^{(r+1)}, induced by the linear form U^{(r)}, is also a primitive element of Q [V_{Y_{n−r},η}^{(r+1)}].

Observe that V_{Y_{n−r},η}^{(r+1)} = W_{P^{(r+1)}} ∩ {Y_{n−r} = η} is isomorphic to the zero–dimensional subvariety {F_{1}(P^{(r+1)}, η, Y_{n−r+1}, …, Y_{n}) = 0, …, F_{r}(P^{(r+1)}, η, Y_{n−r+1}, …, Y_{n}) = 0} of C^{n−r}. Observe also that q^{(r,P^{(r+1)})}(η, Y_{n−r}) is the minimal polynomial equation of V_{Y_{n−r},η}^{(r+1)} induced by the linear form U^{(r)}. Applying Theorem 11 to the linear forms U^{(r)}, Y_{n−r+1}, …, Y_{n}, Z_{1}^{(r)}, …, Z_{r}^{(r)} introduced in Subsections 4.3 and 4.4 we compute, as in the proof of Theorem 15, the coefficients of the minimal integral dependence relations q^{(r)}(T), q_{1}^{(r)}(T), …, q_{r}^{(r)}(T), q̃_{1}^{(r)}(T), …, q̃_{r}^{(r)}(T) of the coordinate functions of V_{r} induced by these linear forms. These polynomials belong to Q [Y_{1}, …, Y_{n−r}][T]. We specialize now in all these polynomials the variables Y_{1}, …, Y_{n−r} into the values p_{1}^{(r+1)}, …, p_{n−r−1}^{(r+1)}, η. In this way we obtain the polynomial

q^{(r)}(p_{1}^{(r+1)}, …, p_{n−r−1}^{(r+1)}, η, T) = q^{(r)}(P^{(r+1)}, η, T) = q^{(r,P^{(r+1)})}(η, T)

and certain polynomials q_{1}^{(r,P^{(r+1)})}(T) := q_{1}^{(r)}(p_{1}^{(r+1)}, …, p_{n−r−1}^{(r+1)}, η, T), …, q_{r}^{(r,P^{(r+1)})} (T) := q_{1}^{(r)}(p_{r}^{(r+1)}, …, p_{n−r−1}^{(r+1)}, η, T) and q̃_{1}^{(r,P^{(r+1)})}(T) := q̃_{1}^{(r)}(p_{1}^{(r+1)}, …, p_{n−r−1}^{(r+1)}, η, T), ..., q̃_{r}^{(r,P^{(r+1)})}(T) := q̃_{1}^{(r)}(p_{r}^{(r+1)}, …, p_{n−r−1}^{(r+1)}, η, T). All these polynomials belong to Q[T] and the polynomials q_{1}^{(r,P^{(r+1)})}, …, q_{r}^{(r,P^{(r+1)})} and q̃_{1}^{(r,P^{(r+1)})}, …, q̃_{r}^{(r,P^{(r+1)})} represent nontrivial equations satisfied by the coordinate functions of V_{Y_{n−r},η}^{(r+1)} induced by the linear forms Y_{n−r+1}, …, Y_{n} and Z_{1}^{(r)}, …, Z_{r}^{(r)}.

We have already shown that the coordinate function of V_{Y_{n−r},η}^{(r+1)} induced by the linear form U^{(r)} is a primitive element of Q [V_{Y_{n−r},η}^{(r+1)}] (thus U^{(r)} separates the elements of V_{Y_{n−r},η}^{(r+1)}) and that q^{(r,P^{(r+1)})}(T) is the minimal polynomial of this coordinate function.

As in the proof of Theorem 15 we apply now Lemma 14 to these data, obtaining thus a geometric solution of the zero–dimensional variety V_{Y_{n−r},η}^{(r+1)}. All this can be done in space O(Srδ_{r}^{2}) and time O((T r^{2} + r^{5})δ_{r}^{3} log^{2} δ_{r} log^{2} log δ_{r}).

Since we have at our disposal a geometric solution of the zero–dimensional variety V_{Y_{n−r},η}^{(r+1)}, we are now able to apply Theorem 11 to the lifting fiber V_{Y_{n−r},η}^{(r+1)} of the curve W_{P^{(r+1)}} and to the polynomial F_{r+1}. In this way we compute the coefficients of the minimal integral dependence relation satisfied over Q [Y_{n−r}] by the coordinate function φ_{r+1} of W_{P^{(r+1)}}, which is induced by the polynomial F_{r+1}. This can be done in additional space O(Sdδ_{r}^{2}) and in additional time O((T dr + r^{4})dδ_{r}^{3} log^{3} δ_{r} log^{2} log δ_{r}).

The minimal integral dependence relation over Q [Y_{n−r}] satisfied by φ_{r+1} is also the minimal polynomial over the field Q (Y_{n−r}) of the homothesy η_{φ_{r+1}}, of the rational function f_{r+1} ∈ Q (Y_{n−r})[T]/(q^{(r,P^{(r+1)})}(Y_{n−r}, T)) and of the homothesy η_{f_{r+1}}. We denote this minimal polynomial by m_{f_{r+1}}(T). Observe that the polynomial m_{f_{r+1}} belongs to Q [Y_{n−r}, T] and from Remark 12 we deduce that our algorithm computes in fact the dense representation of m_{f_{r+1}}. Moreover, we have deg m_{f_{r+1}} ≤ dδ_{r} (see [SS96]).

Therefore, the constant term b(Y_{n−r}) of the minimal polynomial m_{f_{r+1}} is a polynomial of Q [Y_{n−r}] of degree at most dδ_{r} given in dense representation. Applying e.g. the main procedure of [Kal94], we obtain the square–free representation a(Y_{n−r}) of the roots of the polynomial b(Y_{n−r}) in additional space O(dδ_{r}) and time O(dδ_{r} log(dδ_{r}) log log(dδ_{r})).

Now we compute from the already determined coefficients of the polynomial q^{(r,P^{(r+1)})}(T) ∈ Q [Y_{n−r}][T] its discriminant ρ^{(r,P^{(r+1)})} with respect to the variable T. This can be done by [SL92] in additional space O(dδ_{r}) and time O((dδ_{r})^{2} log δ_{r} log

log δ_{r}). By means of the procedure introduced at the beginning of the proof of Lemma 7 we compute the dense representation of the remainder c(Y_{n−r}) of the division of ρ^{(r,P^{(r+1)})}(Y_{n−r}) by the polynomial a(Y_{n−r}), which itself is given in its dense representation. This can be done using additional space O(dδ_{r}^{2}) and time O(dδ_{r}^{3} log^{2} δ_{r} log^{2} log δ_{r}).

Using the identity gcd(ρ^{(r,P^{(r+1)})}(Y_{n−r}), a(Y_{n−r})) = gcd(c(Y_{n−r}), a(Y_{n−r})) we com-

pute the dense representation of the polynomial gcd(ρ^{(r,P^{(r+1)})}(Y_{n−r}), a(Y_{n−r})) in additional space O(dδ_{r}) and time O(dδ_{r} log^{2} δ_{r} log log δ_{r}) (see [Kal94]). Finally we divide the polynomial a(Y_{n−r}) by gcd(ρ^{(r,P^{(r+1)})}(Y_{n−r}), a(Y_{n−r})) obtaining in this way the dense representation of the polynomial m_{Y_{n−r}} (see Lemma 17). Using the algorithm of Sieveking–Kung, this can be done in additional space O(dδ_{r}) and time O(dδ_{r} log^{2} δ_{r} log log δ_{r}). Adding up the complexities of every step in this algorithm we obtain the complexity estimate of Proposition 18.

5 The main algorithm

In this section we collect the algorithmic tools developed before and describe the main algorithm of this paper, concluding thus the proof of Theorem 1.

In the introduction of this paper we announced this algorithm as a recursive procedure which produces in n − 1 steps a geometric solution of the zero–dimensional variety V_{n} defined by the given polynomials F_{1}, …, F_{n} ∈ Q [X_{1}, …, X_{n}]. From now on we shall use freely all notations and assumptions introduced in the previous sections, and in particular those of Subsections 4.3 and 4.4.

Recall that we have already chosen linear forms Y_{1}, …, Y_{n} ∈ ZZ[X_{1}, …, X_{n}] and for each 1 ≤ r ≤ n − 1 a point P^{(r)} = (p_{1}^{(r)}, …, p_{n−r}^{(r)}) ∈ ZZ^{n−r} such that the conditions (i), (ii), (iii) and (iv) of Theorem 5 are satisfied. In particular, the linear forms Y_{1}, …, Y_{n} represent a simultaneous Noether normalization of the varieties V_{1}, …, V_{n} and for 1 ≤ r ≤ n − 1 the finite surjective morphism π_{r} : V_{r} → C^{n−r} induced by the linear forms Y_{1}, …, Y_{n−r} is unramified in the point P^{(r)}. In other words, P^{(r)} is a lifting point of the variety V_{r} with lifting fiber V_{P^{(r)}} := π_{r}^{−1}(P^{(r)}).

For the presentation of our main algorithm we shall focus our attention on its recursive character. Let us fix 1 ≤ r ≤ n − 1. In the next subsection we are going to describe the r–th step of our main algorithm. This step starts with a (previously computed) geometric solution of the lifting fiber V_{P^{(r)}} and produces a geometric solution of the next lifting fiber V_{P^{(r+1)}}.

5.1 The recursion

As before, let 1 ≤ r ≤ n − 1 be fixed. We suppose that there is given a geometric solution of the lifting fiber V_{P^{(r)}}. This geometric solution is represented by the (rational) coefficients of the univariate polynomials occurring in it. Our goal is to compute the coefficients of a geometric solution of the lifting fiber V_{P^{(r+1)}}.

For this purpose we consider again the curve

W_{P^{(r+1)}} = V_{r} ∩ {Y_{1} = p_{1}^{(r+1)}, …, Y_{n−r−1} = p_{n−r−1}^{(r+1)}}.

Recall that lifting any projection from a zero–dimensional variety to this curve produces a bivariate polynomial in dense representation (see Remark 13).

We sketch now how we compute from a given geometric solution of V_{P^{(r)}} a geometric solution of the lifting fiber V_{P^{(r+1)}}:

applying Proposition 18 we compute first the coefficients of the minimal polynomial m_{Y_{n−r}} of the coordinate function of W_{P^{(r+1)}} induced by the linear form Y_{n−r}. At this point we introduce two linear forms ℓ_{1} := α_{1}Y_{n−r} + U^{(r)} and ℓ_{2} := α_{2}Y_{n−r} + U^{(r)}, where α_{1} and α_{2} are suitably chosen nonzero integers. Modifying slightly the algorithm underlying Proposition 18 we compute the coefficients of the minimal polynomials m_{ℓ_{1}} and m_{ℓ_{2}} of the coordinate functions of W_{P^{(r+1)}} induced by the linear forms ℓ_{1} and ℓ_{2}. Interpreting the linear forms Y_{n−r} and U^{(r)} as indeterminates, we consider now the zero–dimensional variety

W := {m_{ℓ_{1}}(α_{1}Y_{n−r} + U^{(r)}) = 0, m_{ℓ_{2}}(α_{2}Y_{n−r} + U^{(r)}) = 0, m_{Y_{n−r}}(Y_{n−r}) = 0}

which is contained in the affine space C^{2}. The linear form ℓ_{1} = α_{1}Y_{n−r} + U^{(r)} separates the points of the variety W. Using ℓ_{1} as separating linear form, we apply now Lemma 14 to the variety W. In this way we obtain a suitable “parametrizing” polynomial v_{n−r}^{(P^{(r+1)})}(T) such that Y_{n−r} − v_{n−r}^{(P^{(r+1)})}(α_{1}Y_{n−r} + U^{(r)}) vanishes on the whole variety W. This polynomial is now used for the computation of a suitable birational morphism which maps the zero–dimensional variety W to the lifting fiber V_{P^{(r+1)}}. From the coordinates of this morphism we obtain a geometric solution of V_{P^{(r+1)}}.

We are now going to describe the details of the procedure sketched just before.

Let us consider the linear form Y_{n−r} + αU^{(r)}, where α is an integer which will be determined later. We claim that for a generic choice of the parameter α, the linear form Y_{n−r} + αU^{(r)} induces a finite morphism which maps the curve W_{P^{(r+1)}} onto the affine space C^{1}.

In order to prove this claim, let us consider the minimal polynomial q^{(r,P^{(r+1)})}(Y_{n−r}, T) ∈ Q [Y_{n−r}, T] of the element u^{(r)} of Q [W_{P^{(r+1)}}] (recall that u^{(r)} is the coordinate function of W_{P^{(r+1)}} induced by the linear form U^{(r)}). Let A be a new indeterminate and let L := Y_{n−r} + AT. Specializing in the polynomial q^{(r,P^{(r+1)})}(Y_{n−r}, T) the variable Y_{n−r} into the value L − AT we obtain a new polynomial q̂^{(r,P^{(r+1)})}(A, L, T) in the indeterminates A, L and T. This polynomial can be written as

q̂^{(r,P^{(r+1)})}(A, L, T) = c_{δ_{r},0}(A)T_{r}^{δ} + ⋯ + c_{0,δ_{r}}(A)L_{r}^{δ},

with c_{δ_{r},0}(A), …, c_{0,δ_{r}}(A) being elements of Q [A] (observe that this representation is possible because deg_{T} q̂^{(r,P^{(r+1)})} = deg q̂^{(r,P^{(r+1)})} = δ_{r} and because the expression L − AT is linear in L and T). Specializing again in q̂^{(r,P^{(r+1)})} the parameter A into the value zero, we obtain q^{(r,P^{(r+1)})}(L, T) which is a monic polynomial in the variable T of degree δ_{r}. This implies c_{δ_{r},0}(0) = 1 and therefore we have c_{δ_{r},0}(A) ≠ 0. Observe also that deg c_{δ_{r},0} ≤ δ_{r} holds.

Therefore, specializing the indeterminate A into any value α ∈ ZZ with c_{δ_{r},0}(α) ≠ 0, we obtain from q̂^{(r,P^{(r+1)})}(A, L, T) a new polynomial q̂^{(r,P^{(r+1)})}(α, L, T) ∈ Q [L, T] of partial degree δ_{r} in the variable T. We consider now the coordinate function ℓ = y_{n−r} + αu^{(r)} of the curve W_{P^{(r+1)}} and the subalgebra Q [ℓ] of Q [W_{P^{(r+1)}}]. From the identity q^{(r,P^{(r+1)})}(y_{n−r}, u^{(r)}) = 0 we deduce that in the Q–algebra Q[W_{P^{(r+1)}}] the identity q̂^{(r,P^{(r+1)})}(α, ℓ, u^{(r)}) = 0 holds. This means that in Q [W_{P^{(r+1)}}] the polynomial q̂^{(r,P^{(r+1)})}(α, ℓ, T) represents an integral dependence relation for the coordinate function u^{(r)} over the subalgebra Q[ℓ]. From the identities Q[W_{P^{(r+1)}}] = Q[y_{n−r}, u^{(r)}] and y_{n−r} = ℓ−αu^{(r)} we deduce now that Q[ℓ] ↪ Q[W_{P^{(r+1)}}] is an integral Q–algebra extension and therefore the morphism ℓ : W_{P^{(r+1)}} → C^{1} is finite and surjective.

We claim now that for a generic choice of the parameter α ∈ ZZ the linear form Y_{n−r} + αU^{(r)} induces a primitive element of the zero–dimensional variety V_{P^{(r+1)}}.

In order to show this claim, let us consider the linear form L̂ := Y_{n−r} + AU^{(r)} ∈

Q[A][X_{1}, …, X_{n}]. The polynomial P (A) = ∏_{{x^{(1)},x^{(2)}∈V_{P^{(r+1)}} \atop x^{(1)}≠x^{(2)}}} (L̂(x^{(1)}) − L̂x^{(2)})) belongs

to Q [A]. By construction, the linear form Y_{n−r} separates the points of the lifting fiber V_{P^{(r+1)}} (see Fact in the proof of Theorem 5). This implies P (0) ≠ 0. One sees now immediately that P is a nonzero polynomial of Q [A] of degree at most δ_{r+1}^{2} which expresses a genericity condition saying that for any α ∈ ZZ the linear form ℓ = Y_{n−r} + αU^{(r)} induces a primitive element of the lifting fiber V_{P^{(r+1)}}.

For an arbitrary integer α, let us write ℓ_{α} = Y_{n−r} + αU^{(r)} and m_{ℓ_{α}} for the minimal polynomial of the coordinate function of V_{P^{(r+1)}} induced by the linear form ℓ_{α}. Furthermore let us write ρ_{ℓ_{α}}^{(r,P^{(r+1)})} for the discriminant of the minimal polynomial q_{ℓ_{α}}^{(r,P^{(r+1)})}(ℓ_{α}, T) of the coordinate function u^{(r)} ∈ W_{P^{(r+1)}} over the Q –algebra Q [ℓ_{α}]. We finally claim that for a generic choice of the parameter α ∈ ZZ, the linear form ℓ := ℓ_{α} = Y_{n−r} + αU^{(r)} satisfies the condition:

gcd(ρ_{ℓ}^{(r,P^{(r+1)})}, m_{ℓ}) = 1.  (10)

In order to prove this claim, we consider again the linear form L̂ = Y_{n−r}+AT and the polynomial q̂^{(r,P^{(r+1)})}(A, L, T) introduced above. Let ρ_{L}(L, Λ) be the discriminant of the polynomial q̂^{(r,P^{(r+1)})}(A, L, T) with respect to the variable T. Specializing again in q̂^{(r,P^{(r+1)})}(A, L, T) the parameter A into the value zero, we obtain the polynomial q^{(r,P^{(r+1)})}(L, T) which is separable and monic. This implies ρ_{L}(0, L) ≠ 0. Moreover the total degree of ρ_{L} is bounded by δ_{r}^{2}. Let m_{L} ∈ Q[A][T] be the minimal polynomial of the image of the linear form Y_{n−r} +AU^{(r)} in the Q[A]–algebra Q[A]⊗Q Q[V_{P^{(r+1)}}]. One immediately verifies deg_{T} m_{L} ≤ δ_{r+1}. Let R(A) ∈ Q [A] be the resultant of the polynomials ρ_{L}(A, L) and m_{L}(A, L) with respect to the indeterminate L. From Lemma 16 we deduce R(0) ≠ 0. Therefore we have R(A) ≠ 0. Moreover, the estimates deg_{L} ρ_{L} ≤ δ_{r}^{2} and deg_{L} m_{L}(A, L) ≤ δ_{r+1} imply deg R ≤ δ_{r}^{2}δ_{r+1}. Therefore for any integer α satisfying R(α) ≠ 0 we see that the linear form ℓ := ℓ_{α} = Y_{n−r} + αU^{(r)} satisfies the condition (10).

We are now going to describe how we can find effectively an integer α ∈ ZZ which satisfies the genericity conditions of the three claims just proved. For this purpose we consider the polynomial H ∈ Q[A] defined by H(A) := c_{δ_{r},0}(A)P (A)R(A). One sees immediately that H ≠ 0 and deg H ≤ 2δ^{3} hold. Let κ be a fixed natural number as in Theorem 5. Applying the Zippel–Schwartz test we choose now randomly two distinct elements α_{1} and α_{2} of the set {1, …, 2κδ^{3}} satisfying the conditions H(α_{1}) ≠ 0 and H(α_{2}) ≠ 0. The probability of success is at least (1 − \frac{1}{κ})^{2}. We suppose from now on that such integers α_{1} and α_{2} are already found. Let ℓ_{1} := Y_{n−r} + α_{1}U^{(r)} and ℓ_{2} := Y_{n−r} + α_{2}U^{(r)}. Observe that the linear forms ℓ_{1} and ℓ_{2} have the properties formulated in the three claims just before.

Our next aim is to compute the coefficients of the minimal polynomials m_{Y_{n−r}}, m_{ℓ_{1}} and m_{ℓ_{2}} of the coordinate functions of the lifting fiber V_{P^{(r+1)}} induced by the linear forms Y_{n−r}, ℓ_{1} and ℓ_{2}. First we compute the coefficients of the minimal polynomial m_{Y_{n−r}} applying directly the procedure underlying Proposition 18.

For the computation of the coefficients of the minimal polynomials m_{ℓ_{1}} and m_{ℓ_{2}} we modify this procedure in the way we are going to explain now. Recall first the following notations:

by q^{(r,P^{(r+1)})} ∈ Q [Y_{n−r}][T] we denote the minimal polynomial of the coordinate function u^{(r)} ∈ Q [W_{P^{(r+1)}}] over the Q –algebra Q [Y_{n−r}] and by ρ^{(r,P^{(r+1)})} ∈ Q [Y_{n−r}] we denote the discriminant of q^{(r,P^{(r+1)})}(Y_{n−r}, T) with respect to the variable T. Moreover φ_{r+1} denotes the coordinate function of the curve W_{P^{(r+1)}} induced by the polynomial F_{r+1}. To the coordinate function φ_{r+1} ∈ Q [W_{P^{(r+1)}}] there corresponds an element f_{r+1} of the quotient algebra Q (Y_{n−r})[T]/ (q^{(r,P^{(r+1)})}(Y_{n−r}, T)) which has the same minimal polynomial over Q (Y_{n−r}) as the coordinate function φ_{r+1} over Q [Y_{n−r}]. This minimal polynomial belongs to Q [Y_{n−r}][T] and is denoted by m_{f_{r+1}}.

The procedure underlying Proposition 18 requires the computation of the dense representation of the minimal polynomials m_{f_{r+1}} and q^{(r,P^{(r+1)})} which belong to Q [Y_{n−r}][T].

Let us fixed 1 ≤ i ≤ 2. Observe that the minimal polynomial m_{f_{r+1}}^{(i)} ∈ Q [ℓ_{i}][T] of the coordinate function φ_{r+1} with respect to the integral Q –algebra extension Q [ℓ_{i}] ↪ Q [W_{P^{(r+1)}}] can be obtained from m_{f_{r+1}} in the following simple way :

m_{f_{r+1}}^{(i)}(ℓ_{i}, T) = m_{f_{r+1}}(ℓ_{i} − α_{i}T, T).

This identity implies that the coefficients of the constant term a^{(i)} ∈ Q [ℓ_{i}] (with respect to the variable T) of the minimal polynomial m_{f_{r+1}}^{(i)} can be determined from the (already computed) dense representation of the polynomial m_{f_{r+1}}. This can be done in additional time O(δ_{r+1}^{2}) using constant additional space.

In the same way, the minimal polynomial q_{ℓ_{i}} := q_{ℓ_{i}}^{(r,P^{(r+1)})} ∈ Q[ℓ_{i}, T] of the coordinate function u^{(r)} with respect to the Q –algebra extension Q [ℓ_{i}] ↪ Q [W_{P^{(r+1)}}] can be obtained by means of the identity :

q_{ℓ_{i}}(ℓ_{i}, T) = q^{(r,P^{(r+1)})}(ℓ_{i} − α_{i}T, T).

Let ρ_{i} := ρ_{ℓ_{i}}^{(r,P^{(r+1)})} ∈ Q[ℓ_{i}] be the discriminant of the polynomial q_{ℓ_{i}} ∈ Q[ℓ_{i}][T] with respect to the variable T. From the generic choice of the integer α_{i} and the third (and last) claim proved at the beginning of this subsection we deduce in the same manner as in Lemma 17 the identity:

m_{ℓ_{i}} = \frac{a^{(i)}}{gcd (a^{(i)}, ρ_{i})}.

Using the same argumentation as in the proof of Proposition 18 we deduce from this identity that the dense representation of the polynomials m_{ℓ_{1}} and m_{ℓ_{2}} can be computed in additional space O(Srδ_{r}^{2}) and time O ((T dr + r^{5})dδ_{r}^{3} log^{3} δ_{r} log^{2} log δ_{r}).

Consider now the zero–dimensional variety

W := {(λ, η) ∈ C^{2}; m_{ℓ_{2}}(λ) = 0, m_{Y_{n−r}}(η) = 0, m_{ℓ_{1}} (λ + (α_{1} − α_{2})η) = 0}

which is contained in the affine plane C^{2}.

Taking into account the identity ℓ_{1} = ℓ_{2} + (α_{1} − α_{2})Y_{n−r} we may consider ℓ_{1} as a linear form in the indeterminates ℓ_{2} and Y_{n−r}. Thus for any point (η, λ) ∈ C^{2} let ℓ_{1}(λ, η) := λ + (α_{1} − α_{2})η. In this sense, the linear form ℓ_{1} separates the points of the variety W.

Applying now Lemma 14 to the zero–dimensional variety W and the linear form ℓ_{1} we compute now from the dense representation of the polynomials m_{Y_{n−r}}, m_{ℓ_{2}} and m_{ℓ_{1}} the coefficients of a polynomial v_{n−r}^{(P^{(r+1)})} ∈ Q [T] of degree at most δ_{r+1} − 1, which satisfies for any point (λ, η) ∈ W the condition

η = v_{n−r}^{(P^{(r+1)})} (λ + (α_{1} − α_{2})η) = v_{n−r}^{(P^{(r+1)})} (ℓ_{1}(λ, η)) .

From [KP96, Proposition 29] we conclude now that the polynomial Y_{n−r}−v_{n−r}^{(P^{(r+1)})}(ℓ_{1}) vanishes on the whole lifting fiber V_{P^{(r+1)}}. The computation of the coefficients of the polynomial v_{n−r}^{(P^{(r+1)})} can be done in additional space O(δ_{r+1}^{2}) and time O(δ_{r+1}^{3} log^{2} δ_{r+1} log^{2} log δ_{r+1}).

Taking into account the estimation δ_{r+1} ≤ dδ_{r} and summing up all complexities we obtain the following result:

Lemma 19 Let notations and assumptions be as before. In particular suppose that there is given a geometric solution of the lifting fiber V_{P^{(r)}} and a linear form ℓ_{1} = Y_{n−r} + α_{1}U^{(r)}, where α_{1} is a sufficiently generic integer. Then it is possible to compute in space O(Srδ_{r}^{2}) and time O ((T dr + r^{5})dδ_{r}^{3} log^{3} δ_{r} log^{2} log δ_{r}) the following items:

• the coefficients of the minimal polynomial m_{ℓ_{1}} of the coordinate function of the lifting fiber V_{P^{(r+1)}} induced by the linear form ℓ_{1},

• the coefficients of a univariate polynomial v_{n−r}^{(P^{(r+1)})} ∈ Q [T] of degree at most δ_{r+1} −1 such that Y_{n−r} −v_{n−r}^{(P^{(r+1)})}(ℓ_{1}) vanishes on the whole lifting fiber V_{P^{(r+1)}}.

It remains now to compute the coefficients of certain suitable polynomials v_{n−r+1}^{(P^{(r+1)})}, …, v_{n}^{(P^{(r+1)})} of Q [T] having degree at most δ_{r+1} − 1, which, together with the polynomial v_{n−r}^{(P^{(r+1)})}, parametrize the lifting fiber V_{P^{(r+1)}} in terms of the linear form ℓ_{1} and its minimal polynomial m_{ℓ_{1}}. This is the content of the next result.

Theorem 20 Let notations and assumptions be in Lemma 19. Then it is possible to compute in space O(Sdrδ^{2}) and time O ((T dr^{2} + r^{5})δ^{3} log^{2} δ log^{2} log δ) the coefficients of certain (univariate) polynomials representing a geometric solution of the lifting fiber V_{P^{(r+1)}}.

Proof.– As in Theorem 5, let us fixed a natural number κ and let us fix an integer η such that η is a lifting point of the curve W_{P^{(r+1)}}. The corresponding lifting fiber is V_{Y_{n−r},η}^{(r+1)} := W_{P^{(r+1)}} ∩ {Y_{n−r} = η}. We have seen at the beginning of the proof of Proposition 18 that such an integer η can be chosen randomly in the set {1, …, κδ^{2}} with probability of success at least 1 − \frac{1}{κ}. Applying now Proposition 18 we compute the coefficients of the minimal polynomial m_{Y_{n−r}} of the coordinate function of V_{P^{(r+1)}} induced by the linear form Y_{n−r}. This can be done by means of a computation tree using space O(Srdδ_{r}^{2}) and time O ((T dr^{2} + r^{5})δ_{r}^{3} log^{2} δ_{r} log^{2} log δ_{r}).

Then we choose randomly two distinct elements α_{1} and α_{2} of the set {1, …, 2κδ^{3}}. Let ℓ_{1} := Y_{n−r} +α_{1}U^{(r)} and ℓ_{2} := Y_{n−r} +α_{2}U^{(r)}. With probability at least (1 − \frac{1}{κ})^{2} the linear forms ℓ_{1} and ℓ_{2} have the properties formulated in the three claims shown at the beginning of this subsection. Then we compute as in the proof of Lemma 19 the coefficients of the minimal polynomials m_{ℓ_{1}} and m_{ℓ_{2}} of the coordinate functions of the lifting fiber V_{P^{(r+1)}} induced by the linear forms ℓ_{1} and ℓ_{2} in. Moreover we compute for 1 ≤ i ≤ 2 the dense representation of q_{ℓ_{i}} ∈ Q [ℓ_{i}][T], which is the minimal polynomial of the coordinate function u^{(r)} of W_{P^{(r+1)}} over the Q –algebra Q [ℓ_{i}].

Now we use the already determined dense representation of the minimal polynomials m_{Y_{n−r}}, m_{ℓ_{1}} and m_{ℓ_{2}} in order to compute the coefficients of a polynomial v_{n−r}^{(P^{(r+1)})} ∈ Q [T] having degree at most δ_{r+1} − 1, such that Y_{n−r} − v_{n−r}^{(P^{(r+1)})}(ℓ_{1}) vanishes on the whole lifting fiber V_{P^{(r+1)}}. This can be done by means of a computation tree using space O(Srdδ_{r}^{2}) and time O ((T dr + r^{5})δ_{r}^{3} log^{2} δ_{r} log^{2} log δ_{r}).

Let us now introduce for 1 ≤ k ≤ r the linear form Z̃_{k}^{(r)} := \frac{1}{α_{1}} ℓ_{1} − λ_{n−r+k}^{(r)}Y_{n−r+k} and let us consider the integral Q –algebra extension Q [ℓ_{1}] ↪ Q [W_{P^{(r+1)}}]. Our aim is to compute for 1 ≤ k ≤ r the minimal polynomials f̃_{k}^{(r+1)} and g̃_{k}^{(r+1)} over Q [ℓ_{1}] of the coordinate functions of W_{P^{(r+1)}} induced by the linear forms Y_{n−r+k} and Z̃_{k}^{(r)}. For this purpose we compute first a geometric solution of an appropriate lifting fiber of the curve W_{P^{(r+1)}} and determine then the polynomials f̃_{k}^{(r+1)} and g̃_{k}^{(r+1)} by a suitable lifting process.

We start choosing randomly an element ξ in the set {1, …, κδ^{2}}. As at the beginning of the proof of Proposition 18 we conclude that with probability at least 1 − \frac{1}{κ} the finite morphism W_{P^{(r+1)}} → C^{1} defined by the linear form ℓ_{1} is unramified in the point ξ. Hence ξ is a lifting point of the curve W_{P^{(r+1)}} with lifting fiber V_{ℓ_{1},ξ}^{(r+1)} := W_{P^{(r+1)}} ∩ {ℓ_{1} = ξ}.

Now we proceed to compute the coefficients of certain suitable polynomials representing a geometric solution of the zero–dimensional variety V_{ℓ_{1},ξ}^{(r+1)}. Observe that the coordinate function of V_{ℓ_{1},ξ}^{(r+1)} induced by the linear form U^{(r)} is a primitive element Q [V_{ℓ_{1},ξ}^{(r+1)}] (compare with the argumentation at the beginning of the proof of Proposition 18).

Since in the Q –algebra Q [V_{ℓ_{1},ξ}^{(r+1)}] the identity q_{1}(ℓ_{1}, u^{(r)}) = 0 holds, the minimal polynomial of the coordinate function of V_{ℓ_{1},ξ}^{(r+1)} induced by the linear form U^{(r)} can be obtained just by specializing in the polynomial q_{ℓ_{1}} ∈ Q[ℓ_{1}][T] the variable ℓ_{1} into the value ξ. From the already computed dense representation of the polynomial q_{ℓ_{1}} we obtain therefore the minimal polynomial of the primitive element of Q [V_{ℓ_{1},ξ}^{(r+1)}] induced by the linear form U^{(r)}.

At the beginning of Subsection 4.3 we considered for each 1 ≤ k ≤ r the linear forms Y_{n−r+k} and Z_{k}^{(r)} := U^{(r)} − λ_{n−r+k}^{(r)}Y_{n−r+k}. In the same way as in the proof of Proposition 18 we compute first the minimal integral dependence relations q_{1}^{(r)}(T), …, q_{r}^{(r)}(T) and q̃_{1}^{(r)}, …, q̃_{r}^{(r)}(T) over Q [Y_{1}, …, Y_{n−r}] of the coordinate functions of V_{r} induced by the linear forms Y_{n−r+1}, …, Y_{n} and Z_{1}^{(r)}, …, Z_{r}^{(r)}. Then we specialize in these integral dependence relations the variables Y_{1}, …, Y_{n−r} into the values p_{1}^{(r+1)}, …, p_{n−r−1}^{(r+1)} and Y_{n−r} = ξ − α_{1}U^{(r)}. In this manner we obtain for any 1 ≤ k ≤ r two polynomials q_{k}^{(r,ξ)}(U^{(r)}, T) and q̃_{k}^{(r,ξ)}(U^{(r)}, T) which belong to Q[U^{(r)}][T] and which have the property that q_{k}^{(r,ξ)}(U^{(r)}, Y_{n−r+k}) and q̃_{k}^{(r,ξ)}(U^{(r)}, Z_{k}^{(r)}) vanish on the whole zero–dimensional variety V_{ℓ_{1},ξ}^{(r+1)}. We apply now Lemma 14 (in a slightly modified form) to the zero–dimensional variety defined in the affine plane C^{2} by the polynomials q_{k}^{(r,ξ)}(U^{(r)}, Y_{n−r+k}), q̃_{k}^{(r,ξ)}(U^{(r)}, Z_{k}^{(r)}) and q_{ℓ_{1}}(ξ, U^{(r)}) and to the (separating) linear form U^{(r)}. As output of the algorithm underlying Lemma 14 we obtain a the coefficients of a certain univariate polynomial ṽ_{n−r+k}^{(r,ξ)} ∈ Q [T] having degree at most δ_{r} − 1, such that Y_{n−r+k} − ṽ_{n−r+k}^{(r,ξ)}(U^{(r)}) vanishes on the whole variety V_{ℓ_{1},ξ}^{(r+1)}.

In the same way as in the proof of Proposition 18 we conclude that the coefficients of the (univariate) polynomials q_{1}(ξ, T) and ṽ_{n−r+1}^{(r,ξ)}(T), …, ṽ_{n}^{(r,ξ)}(T) can be computed in space O(Srdδ_{r}^{2}) and time O ((T dr^{2} + r^{5})δ_{r}^{3} log^{2} δ_{r} log^{2} log δ_{r}). These polynomials

represent a geometric solution of the zero–dimensional variety V_{ℓ_{1},ξ}^{(r+1)}.

Next we apply Theorem 15 in order to lift for each 1 ≤ k ≤ r the projections of the linear forms Y_{n−r+k} and Z̃_{k}^{(r)} = \frac{1}{α_{1}} ℓ_{1} −λ_{n−r+k}^{(r)}Y_{n−r+k} from the zero–dimensional variety V_{ℓ_{1},ξ}^{(r+1)} to the curve W_{P^{(r+1)}}. This lifting procedure computes the dense representation of the polynomials f̃_{k}^{(r+1)} and g̃_{k}^{(r+1)} which belong to Q[ℓ_{1}, T] (see Remark 13). It can be performed in space O(Srdδ_{r}^{2}) and time O ((T dr^{2} + r^{5})δ_{r}^{3} log^{2} δ_{r} log^{2} log δ_{r}).

Let 1 ≤ k ≤ r. We consider now the zero–dimensional subvariety of the affine plane C^{2} defined by the polynomials f̃_{k}^{(r+1)}(ℓ_{1}, Y_{n−r+k}), g̃_{k}^{(r+1)}(ℓ_{1}, Z̃_{k}^{(r)}) = g̃_{k}^{(r+1)}(\frac{1}{α_{1}} ℓ_{1} − λ_{n−r+k}^{(r)}Y_{n−r+k}) and m_{ℓ_{1}}(ℓ_{1}). Applying as before Lemma 14 in a slightly modified form to this zero–dimensional variety, we obtain the coefficients of a certain univariate polynomial v_{n−r+k}^{(P^{(r+1)})} ∈ Q [T] having degree at most δ_{r+1} − 1, such that Y_{n−r+k} − v_{n−r+k}^{(P^{(r+1)})}(ℓ_{1}) vanishes on the whole lifting fiber V_{P^{(r+1)}}. The coefficients of the polynomials v_{n−r+1}^{(P^{(r+1)})}, …, v_{n}^{(P^{(r+1)})} can be computed in additional space O(δ_{r+1}^{2}) and time O (δ_{r+1}^{3} log^{2} δ_{r+1} log^{2} log δ_{r+1}).

These polynomials and the already computed univariate polynomials v_{n−r}^{(P^{(r)})} and m_{ℓ_{1}} represent a geometric solution of the lifting fiber V_{P^{(r+1)}}.

Adding up the complexities of each step in the argument we obtain finally the complexity estimate of Theorem 20.

The proof of Theorem 20 makes precise the computational model in which our main algorithm works, namely the model of computation trees, whose correctness depends on the random choice of certain not too big integers. The computation tree underlying the proof of Theorem 20 is reliable with probability at least (1 − \frac{1}{κ})^{4}.

Applying Theorem 20 recursively, we obtain now easily a proof of Theorem 1.

Acknowledgments The authors thank to M. Giusti, G. Lecerf, T. Krick, L.M. Pardo and M. Sombra for their helpful commentaries about this paper.

References

[Abd97] J. Abdeljaoued. Algorithmes rapides pour le Calcul du Polynôme Caractéristique. PhD thesis, Université de Franche Compte, Besançon, France, 1997.

[ABRW96] 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, volume 142 of Progress in Mathematics, pages 1–15. Birkhäuser, 1996.

[BCA97] P. Bürgisser, M. Clausen, and M. Amin Shokrollahi. Algebraic Complexity Theory, volume 315 of Grundlehren der mathematischen Wissenschaften. Springer, 1997.

[BGHM97] B. Bank, M. Giusti, J. Heintz, and G. Mbakop. Polar varieties, real equation solving and data structures: The hypersurface case. J. of Complexity, 13(1):5–27, 1997.

[BM72] A. Borodin and J. Munro. The Computational Complexity of Algebraic and Numeric Problems. Elsevier, 1972.

[Bor77] A. Borodin. On relating time and space to size and depth. SIAM J. on Comp., 6:733–744, 1977.

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

[BP94] D. Bini and V. Pan. Polynomial and matrix computations. Progress in theoretical computer science. Birkhäuser Boston–Basel–Berlin, 1994.

[Bro87] D. W. Brownawell. Bounds for the degree in the Nullstellensatz. Annals of Math., 126:577–591, 1987.

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

[Can88] J. Canny. Some algebraic and geometric problems in PSPACE. In Proceedings 20th. ACM STOC, pages 460–467, 1988.

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

[CGH89] L. Caniglia, A. Galligo, and J. Heintz. Some new effectivity bounds in computational geometry. In T. Mora et al, editor, Applied Algebra, Algebraic Algorithms and Error Correcting Codes. Proceedings of AAECC-6, volume 357 of LNCS, pages 131–152. Springer, 1989.

[Col67] G.E. Collins. Subresultants and reduced polynomial sequences. Journal of the Association for Computing Machinery, 14:128–142, 1967.

[DFGS91] 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, 33:73–94, 1991.

[Eis95] D. Eisenbud. Commutative Algebra with a View Toward Algebraic Geometry. GTM 150. Springer, 1995.

[FF63] D.K. Faddeev and V.N. Faddeeva. Computational methods of linear algebra. W.H. Freeman, San Francisco, 1963.

[FG90] Noai Fitchas and A. Galligo. Nullstellensatz effectif et Conjecture de Serre (Théorème de Quillen-Suslin) pour le calcul formel. Math. Nachr., 149:231–253, 1990.

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

[Ful84] W. Fulton. Intersection Theory, volume 3 of Ergebnisse der Mathematik. Springer, 1984.

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

[GHH^{+}97] M. Giusti, K. Hägele, J. Heintz, J. E. Morais, J. L. Montaña, and L. M. Pardo. Lower bounds for diophantine approximation. In Proceedings of MEGA’96, volume 117,118, pages 277–317. Journal of Pure and Applied Algebra, 1997.

[GHL^{+}98] M. Giusti, K. Hägele, G. Lecerf, J. Marchand, and B. Salvy. The Projective Noether Maple Package: Computing the dimension of a projective variety. Submitted to Journal of Symbolic Computation, 1998,

(ftp://ftp.medicis.polytechnique.fr/pub/publications/lecerf/jsc98.ps).

[GHM^{+}98] 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, 124:101–146, 1998.

[GHMP95] 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, editors, Applied Algebra, Algebraic Algorithms and Error Correcting Codes, Proceedings AAECC-11, volume 948 of LNCS, pages 205–231. Springer, 1995.

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

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

[GLS99] M. Giusti, G. Lecerf, and B. Salvy. Work in progress, 1999.

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

[GVRR97] L. Gonzalez-Vega, F. Rouillier, and M.F. Roy. Symbolic recipes for polynomial system solving. In Some Tapas of Computer algebra. Springer Verlag, 1997.

[Häg98] K. Hägele. Intrinsic height estimates for the Nullstellensatz. PhD thesis, Universidad de Cantabria, Santander, Spain, 1998.

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

[Hei89] J. Heintz. On the computational complexity of polynomials and bilinear mappings. A survey. In Proceedings AAECC-5, volume 356 of LNCS, pages 269–300. Springer, 1989.

[HKP^{+}98] J. Heintz, T. Krick, S. Puddu, J. Sabia, and A. Waissbein. Deformation techniques for efficient polynomial equation solving. To appear in Journal of Complexity, 1998.

[HMPS99] K. Hägele, J. E. Morais, L. M. Pardo, and M. Sombra. On the intrinsic complexity of the arithmetic Nullstellensatz. To appear in Journal of Pure and Applied Algebra, 1999.

[HMPW98] J. Heintz, G. Matera, L.M. Pardo, and R. Wachenchauzer. The intrinsic complexity of parametric elimination methods. Electronic Journal of SADIO, 1(1):37–51, 1998.

[Ja’83] J. Ja’Ja’. Time–space tradeoffs for some algebraic problems. Journal of the Association for Computing Machinery, 30(3):657–667, 1983.

[Kal94] E. Kaltofen. Asymptotically fast solution of Toeplitz–like singular linear systems. In J. von zur Gathen and M. Giesbrecht, editors, Proceedings of the 1994 International Symposium on Symbolic and Algebraic Computation, ISSAC’94 (Oxford, July 20–22 1994), ACM Press, pages 297–304, New York, 1994. ACM.

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

[KM96] 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), volume 358 of ACM Press, pages 63–71, New York, 1996. ACM.

[KP94] T. Krick and L. M. Pardo. Une approche informatique pour l’ approximation diophantienne. C. R. Acad. Sci. Paris, 318(1):407–412, 1994.

[KP96] T. Krick and L. M. Pardo. A computational method for diophantine approximation. In L. González-Vega and T. Recio, editors, Algorithms in Algebraic Geometry and Applications. Proceedings of MEGA’94, volume 143 of Progress in Mathematics, pages 193–254. Birkhäuser Verlag, 1996.

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

[Küh98] K. Kühnle. Space optimal computation of normal forms of polynomials. PhD thesis, Technischen Universität München, München, Germany, 1998.

[Mac16] F. S. Macaulay. The Algebraic Theory of Modular Systems. Cambridge University Press, 1916.

[Mat97a] G. Matera. Sobre la complejidad en espacio y tiempo de la eliminación geométrica. PhD thesis, Universidad de Buenos Aires, Argentina, 1997.

[Mat97b] G. Matera. Some probabilistic algorithms for geometric elimination. Preprint 51 pages, 1997.

[May89] E. Mayr. Membership in polynomial ideals over Q is exponential space complete. In B. Monien et al, editor, 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, pages 400–406. Springer, 1989.

[MM82] E. Mayr and A. Meyer. The complexity of the word problem for commutative semigroups. Adv. in Math., 46:305–329, 1982.

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

[MT97] G. Matera and J. M. Turull Torres. The space complexity of elimination: Upper bounds. In F.Cucker and M.Shub, editors, Proceedings Foundations of Computational Mathematics (FOCM’97), pages 267–276. Springer, 1997.

[Par95] Luis M. Pardo. How lower and upper complexity bounds meet in elimination theory. In G. Cohen, H. Giusti, and T. Mora, editors, Applied Algebra, Algebraic Algorithms and Error Correcting Codes. Proceedings of AAECC-11, volume 948 of LNCS. Springer, 1995.

[Rou96] F. Rouillier. Algorithmes efficaces pour l’étude des zéros réels des systèmes polynomiaux. PhD thesis, Université de Rennes I, France, 1996.

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

[Sen90] J.R. Sendra. Algoritmos simbólicos de Hankel en álgebra computacional. PhD thesis, Universidad de Alcalá de Henares, Madrid, Spain, 1990.

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

[Sie72] M. Sieveking. An algorithm for division of power series. Computing, 10:153–156, 1972.

[SL92] R. Sendra and J. Llovet. An extended polynomial gcd algorithm using Hankel matrices. Journal of Symbolic Computation, 13:25–39, 1992.

[Som98] M. Sombra. Estimaciones para el Teorema de Ceros de Hilbert. PhD thesis, Universidad de Buenos Aires, Argentina, 1998.

[SS96] J. Sabia and P. Solernó. Bounds for traces in complete intersections and degrees in the Nullstellensatz. Applicable Algebra in Engineering Communications and Computing (AAECC Journal), 6:353–376, 1996.

[Sto89] Hans-Jörg Stoß. Lower bounds for the complexity of polynomials. Theo. Comp. Sci., 64:15–23, 1989.

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

[Str90] V. Strassen. Algebraic complexity theory. In Handbook of Theoretical Computer Science, chapter 11, pages 634–671. Elsevier, 1990.

[Van30] B. L. Van der Waerden. Moderne Algebra I. Berlin, 1930.

[vzG86] J. von zur Gathen. Parallel arithmetic computations: a survey. In B. Rovan J. Gruska and J. Wiedermann, editors, Proceedings of the 12th Symposium on Mathematical Foundations of Computer Science, volume 233 of LNCS, pages 93–112, Bratislava, Czechoslovakia, August 1986. Springer.

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

[Wad90] P. Wadler. Deforestation: transforming programs to eliminate trees. Theoretical Computer Science, 73:231–248, 1990. (Special issue of selected papers from 2nd. ESOP).

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

[Zip79] R. Zippel. Probabilistic algorithms for sparse polynomials. In Proceedings EUROSAM’ 79, volume 72 of LNCS, pages 216–226, 1979.

[Zip93] R. Zippel. Effective Polynomial Computation. ECS 241. Kluwer Academic Publishers, 1993.