LOWER BOUNDS FOR DIOPHANTINE APPROXIMATIONS^{1}

M. Giusti

GAGE, Centre de Mathématiques. École Polytechnique. F-91128 Palaiseau Cedex. France

J. Heintz, K. Hägele, J. E. Morais, L. M. Pardo

Departamento de Matemáticas, Estadística y Computación, Facultad de Ciencias, Universidad de Cantabria, E-39071 Santander, Spain

J. L. Montaña

Departamento de Matemática e Informática, Campus de Arrosadía, Universidad Pública de Navarra, E-31006 Pamplona, Spain

                    This paper is published in
Journal of Pure and Applied Algebra, Vol. 117,118 pages 277--317, 1997.

We introduce a subexponential algorithm for geometric solving of multivariate polynomial equation systems whose bit complexity depends mainly on intrinsic geometric invariants of the solution set. ¿From this algorithm, we derive a new procedure for the decision of consistency of polynomial equation systems whose bit complexity is subexponential, too. As a byproduct, we analyze the division of a polynomial modulo a reduced complete intersection ideal and from this, we obtain an intrinsic lower bound for the logarithmic height of diophantine approximations to a given solution of a zero–dimensional polynomial equation system. This result represents a multivariate version of Liouville’s classical theorem on approximation of algebraic numbers by rationals. A special feature of our procedures is their polynomial character with respect to the mentioned geometric invariants when instead of bit operations only arithmetic operations are counted at unit cost. Technically our paper relies on the use of straight–line programs as a data structure for the encoding of polynomials, on a new symbolic application of Newton’s algorithm to the Implicit Function Theorem and on a special, basis independent trace formula for affine Gorenstein algebras.

Preprint submitted to Elsevier Preprint 17 July 1997

1991 Math. Subj. Class.: 68Q25, 14Q15, 11J68

1 Introduction

The present pages represent a continuation of [25,26,44]. These papers concern the design of algorithms of intrinsic type to solve systems of polynomial equations. Solving is then applied to decide consistency of systems of polynomial equations. By “intrinsic type” we mean algorithms which are able to distinguish between the semantical and the syntactical character of the input system in order to profit from both for the improvement of the complexity estimates.

With respect to bit complexity we show how the time necessary to solve a given polynomial equation system is related to the affine degree and the (affine) logarithmic height of the corresponding diophantine variety. In this sense, the results of [25] and [26] show already that the (affine) degree of an input system is associated with the complexity when measured in terms of number of arithmetic operations. However, there are still some drawbacks to this approach.

The first one is that the algorithms developed in [26] require iterative calls to the procedure and that the algorithms in [25] rely on the use of algebraic numbers. Thus in the case of [25] the algorithms are not “rational” although their inputs and outputs are.

A second drawback concerns the modeling used to measure complexity. The quantity of arithmetic operations of an algorithm does not explain sufficiently what happens when we are using it on a “real life” computer. Years of experience show that models of bit complexity (Turing machines, random access machines or equivalent models) represent more realistic patterns for practical computing. In this sense a study of bit complexity of the intrinsic complexity of the algorithms of [25] and [26] becomes necessary.

In the present paper we deal with both disadvantages of the algorithms in [25] and [26], giving practicable solutions (cf. also Section 3 below). First, our new algorithm is completely rational. It does not require any constants other than those in the field of coefficients of the input system. Secondly, to improve the bit complexity estimates, we introduce a suitable notion of height of affine diophantine varieties which is inspired by the corresponding notion

1 Research was partially supported by the following French, Spanish and Argentinian grants : GDR CNRS 1026 MEDICIS, DGCYT PB93-0472-C02-02, UBACYT-EX-001 and PID CONICET 3949/92.

introduced for projective varieties in [5,9,21,42,43,45–48]. As shown in Section 2, our notion of height is strongly related to the bit complexity of geometric elimination procedures of any kind.

Our notion of height combined with a new algorithmic interpretation of duality theory for complete intersection ideals yields a new Liouville estimate (cf. Sections 7 and 4 below). Liouville estimates can be applied to get lower time bounds for the numerical analysis approach to solving systems of polynomial equations. In particular, we show the practical inefficiency of both floating point and binary encoding for rational approximation of zero–dimensional multivariate polynomial equation systems even in the algorithmically well suited cases.

To illustrate these introductory observations, let us first consider the following two problems:

Problem 1 Let be given a sequence of n integer polynomials of degree at most 3, with coefficients in {0, 1}, using three variables each:

p_{1}(X_{1,1}, X_{1,2}, X_{1,3}), …, p_{n}(X_{n,1}, X_{n,2}, X_{n,3})

Decide whether the following system of polynomial equations has a solution:

X_{1,k}^{2}−X_{1,k} = 0, …, X_{n,k}^{2}−X_{n,k} = 0, Y_{1}^{2}−Y_{1} = 0, …, Y_{3n}^{2}−Y_{3n} = 0 1 ≤ k ≤ 3

∏_{i=1}^{n} p_{i}(X_{i,1}, X_{i,2}, X_{i,3}) − (1 + ∑_{j=1}^{3n} Y_{j}2^{j}) = 0

Problem 2 Given in decimal representation an integer k ∈ IN and the polynomials:

X_{1}^{2} − X_{1} = 0, …, X_{n}^{2} − X_{n} = 0

k − (X_{1} + 2X_{2} + ⋯ + 2^{n−1}X_{n}) = 0

Decide whether this system has a solution.

Both problems have a similar “syntactical form” (i.e. they look very similar, as a consistency question for “syntactically easy” polynomial equation systems). However, they possess completely different “semantical” characters : the first problem is a translation of a well–known NP–complete problem (3satisfiability, for short 3SAT), while the second one just concerns the binary encoding of k with n bits (if there exists such an encoding). This means that the second system is consistent if and only if k may be encoded using at most n binary digits (cf. [31,44]). Traditional symbolic procedures deal with both problems using in each case the same generalistic treatment. However these two problems demand for different algorithms that may profit from their different semantical features. The construction of algorithms which are able to distinguish between equation systems which are semantically well suited and such which are not is the main goal of our paper. We shall also consider the question of consistency of polynomial equation systems in the following terms:

Problem 3 (Effective Nullstellensatz) Given a sequence of polynomials f_{1}, …, f_{s} ∈ ZZ[X_{1}, …, X_{n}], decide whether the affine algebraic variety

V (f_{1}, …, f_{s}) := {x ∈ C^{n} : f_{1}(x) = ⋯ = f_{s}(x) = 0}

is empty or not.

As both Problems 1 and 2 above can be written as special cases of this more general Problem 3, we have to find a way to distinguish (within the context of Problem 3) between the different levels of difficulty Problems 1 and 2 represent. To design algorithms which solve this problem taking care of the special features of the particular instance of the input system, we need two major geometric invariants: the affine degree and the affine height of the system (cf. Section 2.2 below). Assuming these two notions we are going to show in this paper the following result:

Theorem 4 There exists a bounded error probability Turing machine which solves the following task: given polynomials f_{1}, …, f_{n+1} ∈ ZZ[X_{1}, …, X_{n}] of degree at most 2 and of (logarithmic) height h, the Turing machine decides whether the variety V (f_{1}, …, f_{n+1}) is empty or not. Moreover, if δ is the intrinsic (affine) degree of the system and η is the intrinsic (logarithmic) height of the system, the Turing machine answers in (bit) time

(nhδη)^{O(log_{2}n)}

using a total amount of arithmetic operations in Q of

(nδ)^{O(1)}.

Our algorithm first solves a suitable polynomial equation system and then uses this information for the consistency test of the original system f_{1}, …, f_{n+1}.

Solving is done inductively. In order to explain the procedure let us assume that the polynomials f_{1}, …, f_{n} form a regular sequence, each ideal (f_{1}, …, f_{i}), 1 ≤ i ≤ n, being radical. Then the algorithm proceeds in n steps, solving at each stage 1 ≤ i ≤ n the system f_{1} = 0, …, f_{i} = 0.

The corresponding intermediate algebraic varieties are obtained by a lifting process from special zero-dimensional varieties which we call the lifting fibers. The lifting process is based on a division-free symbolic version of the Newton-Hensel algorithm and represents a algorithmic version of the Implicit Function Theorem. In this way, the procedure constructs the lifting fiber of step i + 1 from the lifting fiber of step i. Each inductive step includes two cleaning phases : one is performed to throw away extraneous projective components (mainly those at infinity) and a second one reduces the size of the representation of the integers which appear during the process. This second cleaning phase is included to avoid uncontrolled growth of integer coefficients of intermediate polynomials.

Finally we show how the following two computational problems are related: the division problem in the Nullstellensatz and the numerical analysis approach for the resolution of systems of multivariate polynomial equations.

Problem 5 (Division Problem in the Effective Nullstellensatz) Let be given polynomials f_{1}, …, f_{s} ∈ ZZ[X_{1}, …, X_{n}] without any common zeroes (i.e. the polynomials satisfy the condition V (f_{1}, …, f_{s}) = ∅). Compute a non-zero integer a ∈ ZZ, and polynomials g_{1}, …, g_{s} ∈ ZZ[X_{1}, …, X_{n}] such that

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

holds.

Problem 6 (Numerical Analysis Approach) Given a real number ε > 0 and a regular sequence of polynomials f_{1}, …, f_{n}∈ ZZ[X_{1}, …, X_{n}] of degree at most d defining a zero-dimensional affine variety V := V (f_{1}, …, f_{n}), compute for any point α ∈ V an approximation a ∈ C^{n} at level ε > 0, i.e. find by an effective procedure a point a ∈ C^{n} such that

||a − α|| < ε

holds.

At first glance Problems 5 and 6 seem to be unrelated. However we shall see how the solution of Problem 5 provides lower bounds for any solution of Problem 6. We shall state this observation in terms of Liouville estimates.

In order to understand the relation between Problems 5 and 6, let us observe that in the context of Problem 6 any approximation a computer may output is necessarily rational (i.e. such an approximation must be a point a belonging to Q [i]^{n}). Such an output is assumed to be encoded in binary (i.e. by the binary expansion of denominators and numerators of the coordinates of a).

In the past the division problem in the Nullstellensatz was studied in both number theory and computer science simultaneously. The first results mainly established upper bounds for the degree ([10,13,12,33]) and height ([3,4]) of the polynomials g_{1}, …, g_{s} appearing in Problem 5. The complexity study in ([22,34,35]) yields optimal upper bounds for both invariants (see also [19]) and can be applied to derive Liouville estimates in the following sense (cf. also Subsection 2.5 below):

A Liouville estimate is a lower bound for the binary length (the logarithmic height) of the numerators and denominators of the coordinates of a in terms of the variety V, the point α and the real number ε in the statement of Problem 6 above. The following Theorem 7 gives such a Liouville estimate.

Let us introduce the following notions and notations: let V ⊂ C^{n} be a zerodimensional diophantine variety not intersecting Q [i]^{n} and let α be a point of V. Let ε > 0 be a real number. We call a point a = (\frac{a_{1}}{q_{1}} , …, \frac{a_{n}}{q_{n}}) ∈ Q [i]^{n} a rational approximation of α at level ε > 0, if

||α − a|| < ε

holds. (Here ||·|| denotes the norm associated with the usual hermitian product in C^{n}).

A regular sequence f_{1}, …, f_{n} ∈ ZZ[X_{1}, …, X_{n}] is said to be smooth if for any 1 ≤ i ≤ n the Jacobian J(f_{1}, …, f_{i}) is not a zero-divisor modulo the ideal (f_{1}, …, f_{i}). Observe that for a smooth regular sequence the ideals (f_{1}, …, f_{i}) are always radical.

Theorem 7 There exists a universal constant C with the following property: given a smooth regular sequence of polynomials f_{1}, …, f_{n} ∈ ZZ[X_{1}, …, X_{n}] of degree at most d and of logarithmic height at most h. Furthermore let be given a point a ∈ Q [i]^{n} and a real number 0 < ε ≤ 1. Suppose that the variety V := V (f_{1}, …, f_{n}) verifies the following conditions :

– V ∩ Q [i]^{n} = ∅.

– there exists a point α ∈ V such that

||a − α|| < ε ≤ 1

holds. Then we have for any denominator q of a the following inequality :

\frac{−log_{2}ε}{(ndδ)^{C}} − (h + η) ≤ log_{2}q,

where δ denotes the degree and η the (affine) logarithmic height of V.

PROOF. According to Proposition 20 below we have:

\frac{ε^{−1}}{|g_{n+1}(α)|(2||α|| + 1)} ≤ q^{2}.

Thus, we look for upper bounds for ||α|| and |g_{n+1}(α)|. First, from Proposition 14 below we deduce :

(2||α|| + 1) ≤ \sqrt{n}δ2^{δη}.

On the other hand, combining Theorem 21 and Lemma 23 below we conclude:

log_{2}|g_{n+1}(α)| ≤ (ndδ)^{O(1)}(h + η + log_{2}q).

¿From these two upper bounds we easily deduce the bounds of the Theorem. □

We observe that for n = 1 Theorem 7 represents just a restatement of Liouville’s classical result with somewhat coarser bounds (compare e.g. [50, Kapitel I, Satz 1]).

The height estimates in [3,4,19,34] and [35], combined with the methods described in subsection 2.5 below (Proposition 20) produce Liouville bounds that relate the syntactical description of V as given by the input, the approximation ε and the height of the denominator of a. In fact, these estimates yield the inequality :

−log_{2}ε ≤ d^{O(n)}hlog_{2}q (1)

On the other hand: degree and height of the solution set represent reasonable lower time bounds for the numerical analysis approach to polynomial equation solving by rational point approximation. Exponential degrees and exponential height produce exponential lower time bounds for numerical methods of polynomial equation solving (cf. [44]).

A lower bound like inequality (1) above, i.e. a lower bound for log_{2}q, represents a lower bound for the output length and therefore a lower time bound for numerical methods of polynomial system solving. The results of [2–4,8,9,19,34,35,46– 48] imply that an approximation level of ε := 2^{−d^{O(n)}} is sufficient in order to characterize (and to distinguish adequately) the solutions of the variety V in Problem 5. On the other hand the examples of [39, Chapitre 4, Proposition 12] and [29], [30, Exemple 3] show that even in case of semantically and syntactically “easy” systems such an approximation level may be necessary. Therefore it becomes reasonable to fix an approximation level for numerical solving of ε := 2^{−d^{n}}, where d^{n} represents the Bézout number of the input system. Under this assumption, inequality (1) becomes meaningless and more precise lower bounds are required.

However an exponential lower time bound for numerical solving is implicitly contained in the following corollary to Theorem 7:

Corollary 8 Given a smooth regular sequence f_{1}, …, f_{n} ∈ ZZ[X_{1}, …, X_{n}], and points α ∈ V, a ∈ Q [i]^{n} verifying the conditions of Theorem 7 above, let ε > 0 be a level of approximation such that −log_{2}ε = d^{n} (where d^{n} represents the Bézout number of the system). Then we have

\frac{d^{n}}{(ndδ)^{C}} − (h + η) ≤ log_{2}q,

where C is a suitable universal constant as in Theorem 7. In particular, for systems of “small” degree and height, the output length for numerical solving methods is necessarily exponential in the number of variables.

For instance, we may consider the following smooth regular sequence of quadratic polynomials:

X_{1}^{2} + X_{1} + 1, X_{2} − X_{1}^{2}, …, X_{n} − X_{n−1}^{2}

This sequence defines a zero-dimensional variety with just two points (the degree of the variety is 2) of small height (the height is 1). Thus, for a level of approximation ε > 0 with −log_{2}ε = 2^{n}, the lower bound obtained from inequality (1) says just:

2^{n} ≤ 2^{O(n)}log_{2}q,

whereas the lower bound from Corollary 8 states that every rational approximation of level ε of any solution of this system has exponential binary length. Thus, the main consequence of this corollary is that both binary and floating point encoding of numbers in Q[i] are not efficient for reaching the appropriate level of approximation. An alternative encoding is therefore required.

Another way out of this dilemma may consist in the following approach initiated in [51] and further developed in [52–55,17,18]. Instead of approximating rationally (or similarly by floating point arithmetic) the solutions of the zero– dimensional input system f_{1}, …, f_{n}up to the appropriate approximation level ε = 2^{−d^{n}}, we just try to find approximate zeroes (in the sense of [55]) of the system, i.e. we try to find points a ∈ Q [i]^{n} from which a suitable version of Newton’s algorithm converges quadratically to a true zero of the system.

2 Notions, notations and Results

We are going to study the consistency question of Problem 3 (i.e. the decisional problem in the effective Nullstellensatz) only when the input system of polynomial equations f_{1}, …, f_{r} ∈ ZZ[X_{1}, …, X_{n}] verifies the conditions:

– r ≤ n + 1,

– the sequence f_{1}, …, f_{r−1} is a smooth regular sequence

These two additional conditions are not really restrictive. As shown in [22,24,27,34,35] an effective version of Bertini’s Theorem allows to reduce a general input system f_{1}, …, f_{s} ∈ ZZ[X_{1}, …, X_{n}] to such a system. We just have to find generic ZZ-linear combinations of the input polynomials such that these linear combinations contain only coefficients in ZZ of logarithmic height O(n·log_{2}d), where n is the number of variables and d is an upper bound for the degrees of the input polynomials. Under the assumption of this preprocessing we may suppose without loss of generality that our input equations satisfy the following conditions:

– the ideals (f_{1}, …, f_{i}) are radical, 1 ≤ i ≤ r − 1,

– for 1 ≤ i ≤ r − 1 the varieties V_{i} = V (f_{1}, …, f_{i}) are complete intersection affine varieties of dimension n − i.

Notation 1 Given R ⊂ B an extension of a commutative ring (which converts B into a R-algebra), and an element b ∈ B, we denote by η_{b} : B ⟶ B the R-linear endomorphism induced by the multiplication of the elements of B by b (in the following we shall call such a linear map a homothety). If B is a free R-module of finite rank, we denote by M_{b} the matrix of the homothety η_{b} and by χ_{b} ∈ R[T] the characteristic polynomial of η_{b}. Moreover, if R is a unique factorization domain, we shall denote by m_{b} the primitive minimal polynomial of η_{b}. Observe that χ_{b} and m_{b} are monic polynomials of R[T], which for short we will call characteristic and minimal polynomial of b, respectively.

In order to decide whether (f_{1}, …, f_{r}) represents the trivial ideal we just need to compute the following items:

– A linear change of coordinates (X_{1}, …, X_{n}) ⟶ (Y_{1}, …, Y_{n}) such that the following Q -algebra homomorphism represents a Noether normalization of the variety V (f_{1}, …, f_{r−1}), with the variables Y_{1}, …, Y_{n−r+1} being free:

R := Q [Y_{1}, …, Y_{n−r+1}] ⟶ Q [Y_{1}, …, Y_{n}]/(f_{1}, …, f_{r−1}) =: B.

Observe that this means that B is an integral extension of R.

– the matrix M_{f_{r}} of the homothety η_{f_{r}} with respect to an appropriate Rmodule basis.

Suppose that such a Noether normalization is available. Then the Q -algebra homomorphism R → B is injective and B is a free R-module of rank at most deg V_{r−1} (cf. [27,28]). Under this assumption the ideal (f_{1}, …, f_{r}) is trivial if and only if the matrix M_{f_{r}} is unimodular what means that the determinant of M_{f_{r}} is non zero and belongs to Q .

This comment shows how the original Problem 3 of testing consistency of polynomial equation systems can be reduced to the problem of solving polynomial equation systems in a very specific geometric sense. In the next subsection we are going to explain what exactly we mean by this, namely geometric solving.

2.1 Geometric Solving

The previous considerations reduce the search for a consistency test for the polynomial equation system f_{1} = 0, …, f_{r} = 0, namely Problem 3, to the problem of computing a Noether normalization of the variety V (f_{1}, …, f_{r−1}) and the matrix M_{f_{r}} of the homothety η_{f_{r}} with respect to a suitable R-module basis. Assume that X_{1}, …, X_{n}are already in Noether position with respect to the variety V (f_{1}, …, f_{r−1}), the variables X_{1}, …, X_{n−r+1} being free. Then we consider the following integral ring extension

R := Q [X_{1}, …, X_{n−r+1}] ⟶ Q [X_{1}, …, X_{n}]/(f_{1}, …, f_{r−1}) =: B.

Our assumptions on f_{1}, …, f_{r−1} imply that B is a reduced algebra and a finite free R-module. We are now going to explain what we mean by “geometric solving” or “geometric solution”. First we need the following notion of primitive element of B:

Definition 9 Let R be a ring of polynomials over Q and R ⊆ B an integral ring extension such that B is reduced and B is a free R-module of finite rank. An element u ∈ B is called a primitive element of the ring extension R ⊆ B if the degree of the minimal polynomial m_{u} of u equals the rank of B as free R-module, i.e. if

deg m_{u} = rank_{R} B

holds.

Let K be the quotient field of R and B′ = K ⊗_{R} B be the localization of B by the non-zero elements of R. An element u ∈ B is a primitive element of B if and only if for D := rank_{R}B = dim_{K}B′ the set {1, u, …, u^{D−1}} represents a K -vectorspace basis of B′.

The computation of the matrix M_{f_{r}} is a consequence of the following “generic point” description of the K -algebra B′: this algebra is characterized by the following items (which our algorithm will compute):

– a K -vectorspace basis of B′

– for n − r + 2 ≤ i ≤ n the matrices M_{X_{i}} of the homotheties η_{X_{i}} : B ⟶ B with respect to the given basis (these matrices describe the multiplication tensor of the K-algebra B′ and hence also of the R-algebra B)

We then obtain the matrix M_{f_{r}} by substituting for the variables X_{n−r+2}, …, X_{n} appearing in the polynomial f_{r}(X_{1}, …, X_{n}) the matrices M_{X_{n−r+2}}, …, M_{X_{n}}. (In the sequel we shall write for short M_{f_{r}} = f_{r}(M_{X_{n−r+2}}, …, M_{X_{n}}) for this substitution, interpreting f_{r} as an element of the polynomial ring R[X_{n−r+2}, …, X_{n}]).

In this sense, geometric solving means just computing both a basis of the Kalgebra B′ and the matrices M_{X_{n−r+1}}, …, M_{X_{n}}. This is done making use of a suitable primitive element of B.

In the context of this paper, the primitive element u ∈ B will always be chosen as the image in B of a generic ZZ-linear form of the variables X_{n−r+2}, …, X_{n}. In particular, we may assume that u is the image of a linear form U = λ_{n−r+2}X_{n−r+2} + ⋯ + λ_{n}X_{n}, with λ_{i} ∈ ZZ for n − r + 2 ≤ i ≤ n. Let T be a new indeterminate. The minimal polynomial m_{u}(T) of u as an element of the R-algebra B (or equivalently as an element of the K -algebra B′) will be a monic polynomial in Q [X_{1}, …, X_{n−r+1}, T] = Q ⊗_{ZZ} R[T].

We shall shall choose this minimal polynomial as an element of the ring ZZ[X_{1}, …, X_{n−r+1}, T] = R[T]. In the sequel we shall pay special attention to the case r = n + 1, where we have R = ZZ, K = Q and where m_{u} is a polynomial of ZZ[T] of positive degree (the polynomial m_{u} is then trivially monic over Q [T] since we may divide it by its leading coefficient, which is a nonzero integer). Discarding the content (the maximum common divisor) of the coefficients of m_{u}, we may replace the minimal polynomial m_{u} by its primitive counterpart which we shall always denote by q_{u}. Similarly, for the case r ≤ n, we shall replace the minimal polynomial m_{u} ∈ ZZ[X_{1}, …, X_{n−r+1}, T] = R[T] by some “cleaner” (however not necessarily primitive) version q_{u}.

Finally, as {1, u, …, u^{D−1}} is a basis of the K -vector space B′, for n − r + 2 ≤ i ≤ n there are polynomials v_{i}^{(u)} ∈ R[T] and non-zero elements ρ_{i}^{(u)} ∈ R such that ρ_{i}^{(u)}X_{i} − v_{i}^{(u)}(U) belongs to the ideal (f_{1}, …, f_{r−1}) in K [X_{n−r+2}, …, X_{n}]. In particular, we have the following identity between ideals of K [X_{n−r+2}, …, X_{n}]:

(f_{1}, …, f_{r−1}) = (q_{u}(U), ρ_{n−r+2}^{(u)}X_{n−r+2} − v_{n−r+2}^{(u)}(U), …, ρ_{n}^{(u)}X_{n} − v_{n}^{(u)}(U)).

Moreover, if M denotes the companion matrix of the homothety η_{u} with respect to the basis {1, u, …, u^{D−1}}, the matrices M_{X_{n−r+2}}, …, M_{X_{n}} characterizing the multiplication tensor of the R-algebra B (or equivalently of the K-algebra B′) are given by the formula

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

for n − r + 2 ≤ i ≤ n. To simplify notations we shall often omit the superindex (u) when refering to these polynomials. After these explanations we shall assume without loss of generality that we have s := n + 1 in the statement of Problems 3 and 5. Consequently we restrict the meaning of “geometric solving” to the case where we have given as input polynomials f_{1}, …, f_{n} ∈ ZZ[X_{1}, …, X_{n}] forming a regular sequence in Q [X_{1}, …, X_{n}](we shall say in the future for short that f_{1}, …, f_{n} ∈ ZZ[X_{1}, …, X_{n}] is a regular sequence). With these conventions “geometric solving” means the following:

Definition 10 An algorithm for geometric solving is a procedure which from a smooth regular sequence f_{1}, …, f_{n} ∈ ZZ[X_{1}, …, X_{n}] as input produces:

– a primitive element u of the ring extension Q ⟶ Q[X_{1}, …, X_{n}]/(f_{1}, …, f_{n}) represented by a ZZ-linear form U = λ_{1}X_{1} + ⋯ + λ_{n}X_{n}

– the primitive minimal polynomial q_{u} ∈ ZZ[T] – the parametrizations of the variety V (f_{1}, …, f_{n}) by the zeroes of q_{u}, namely

the (unique) primitive polynomials ρ_{1}^{(u)}X_{1} − v_{1}^{(u)}(T), …, ρ_{n}^{(u)}X_{n} − v_{n}^{(u)}(T) with ρ_{1}^{(u)}, …, ρ_{n}^{(u)} non-zero integers and v_{1}^{(u)}, …, v_{n}^{(u)} ∈ ZZ[T] which satisfy the conditions max{deg v_{1}^{(u)}, …, deg v_{n}^{(u)}} < deg q_{u} and (f_{1}, …, f_{n}) = (q_{u}(U), ρ_{1}^{(u)}X_{1} − v_{1}^{(u)}(U), …, ρ_{n}^{(u)}X_{n} − v_{n}^{(u)}(U)) in Q[X_{1}, …, X_{n}]. Moreover, the non-zero integer ρ := ∏_{i=1}^{n} ρ_{i} ∈ ZZ, called a discriminant of the input system, is a multiple of the discriminant of q_{u}.

In the sequel we shall refer to the polynomials U = λ_{1}X_{1} + ⋯ + λ_{n}X_{n} ∈ ZZ[X_{1}, …, X_{n}] (with image u in Q [X_{1}, …, X_{n}]/(f_{1}, …, f_{n})), q_{u}(T), v_{1}^{(u)}(T), …, v_{n}^{(u)}(T) ∈ ZZ[T] and ρ_{1}^{(u)}, …, ρ_{n}^{(u)} ∈ ZZ as geometric solution of the equation system f_{1} = 0, …, f_{n} = 0.

Let us remark here that this notion of “geometric solving” has a long history, which unfortunately we can not give here in full detail for mere lack of space. One might consider [15] and [23] as early references where this notion was implicitly used for the first time in complexity theory.

2.2 Intrinsic Parameters

We said in the introduction that we are interested in algorithms for geometric solving which are able to profit from “good” geometrical properties which an input system of polynomial equations might possess. This makes it necessary to precise what such “good” geometrical properties may be and how to find measures for them. Therefore, we are going to define two geometric invariants in this subsection that will arise as parameters of the complexity of our procedures: the (affine) degree and the (affine) logarithmic height of complete intersection varieties. The notion of degree has been taken directly from [28], while our notion of height is strongly inspired by the corresponding notion developed for projective varieties in [42,43,45–48].

Let us first recall the notion of degree of an affine algebraic variety. We begin by defining the degree of a zero-dimensional variety and then we extend this notion to positive dimensional complete intersection algebraic varieties.

To fix notations, let V ⊆ C^{n} be an algebraic subset (variety) given as the set of common zeroes in C^{n} of a smooth regular sequence of polynomials f_{1}, …, f_{i} ∈ ZZ[X_{1}, …, X_{n}] of degree at most d. If V is zero-dimensional (i.e. if i = n) the degree of V is defined as the number of points of V (points at infinity are not counted in this definition). In the general case (when dim V = n − i ≥ 1 holds) let us consider the class D of all affine linear subspaces of C^{n} of dimension i (defined as the set of solutions in C^{n} of a linear equation system L_{1} = 0, …, L_{n−i} = 0 where L_{k} = a_{k1}X_{1} + ⋯ + a_{kn}X_{n} + a_{k0} is an affine linear polynomial with coefficients a_{kj} ∈ ZZ for 1 ≤ k ≤ n − i and 0 ≤ j ≤ n). Let D_{V} be the subclass of D of all these affine linear spaces H ∈ D such that H ∩ V is a zero-dimensional variety.

Definition 11 Let notations and assumptions be as before. The degree of V is defined as the maximum of the degrees of the intersections of V with affine linear spaces belonging to D_{V}. We denote the degree of V by deg V.

As observed in [28], this definition of the degree never yields infinity, but gives always a natural number. Our definition is equivalent to the following one: Consider all linear changes of coordinates in C^{n} defined by non-singular matrices with integer entries, i.e. linear changes of the type

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

where Y_{k} = a_{k1}X_{1} + ⋯ + a_{kn}X_{n} is a linear form with integer coefficients for 1 ≤ k ≤ n. Any generic linear change of coordinates induces an integral ring extension as follows:

Q [Y_{1}, …, Y_{n−i}] ⟶ Q [Y_{1}, …, Y_{n}]/(f_{1}, …, f_{i}) = Q [V].

It turns out that the ring Q [V] is a free Q [Y_{1}, …, Y_{n−i}]-module of finite rank (cf. [27] for instance). This rank is the same for any generic linear coordinate change and it equals the degree of the variety V.

In order to define the height of an affine diophantine variety, we also consider first the zero-dimensional case and then the case of positive dimension.

To start with let us first say what we mean by the (logarithmic) height of an integer, a vector of integers, a matrix over ZZ and a polynomial with integer coefficients. Let a ∈ ZZ be an integer, then the height of a is defined as ht(a) := max{log_{2}|a|, 1}. It is obvious that the height measures the bit length of a. On the other hand we shall see soon that this simple notion of height of an integer has a natural extension to algebraic varieties where it plays the role of “arithmetic degree” (see [9,5,21,34,35,46–48]). The main outcome of this paper will be the reinterpretation of the notion of height for algebraic varieties as a measure for the bit complexity of an elimination procedure. In this sense, our contribution justifies a posteriori Northcott’s terminology of “complexity” for the height of an algebraic variety [57].

For a vector of integer numbers α := (a_{1}, …, a_{n}) ∈ ZZ^{n}, we define the height ht(α) as the maximum of the heights of its coordinates. For a matrix A ∈ M_{n}(ZZ) with integer entries, its height ht(A) is defined as the height of A as vector. Similarly, we define the height of a polynomial f ∈ ZZ[X_{1}, …, X_{n}] as the height of the vector of its coefficients.

Definition 12 Given a zero-dimensional diophantine algebraic variety V ⊆ C^{n} and a linear form U = λ_{1}X_{1} + ⋯ + λ_{n}X_{n} with integer coefficients representing a primitive element u of the ring extension Q ⟶ Q [V], we define the height of V with respect to U as the maximum of the heights of the polynomials q_{u}(T), ρ_{1}^{(u)}X_{1} − v_{1}^{(u)}(T), …, ρ_{n}^{(u)}X_{n} − v_{n}^{(u)}(T) (see Definition 10) and denote this height by ht(V; U).

In our first approach to find a suitable notion of height for algebraic varieties we define the height of the given zero-dimensional variety V as the function ht_{V} : IN ⟶ IN which associates to any natural number c ∈ IN the value ht_{V} (c) := max{ht(V; U) : ht(U) ≤ c} if the ring extension Q ⟶ Q [V] has a primitive element of height at most c and which associates to c the value 1 if no such primitive element exists.

This notion of height is related to the hermitian norm and the denominator of the points of the variety V. In order to explain this relation, let us introduce the following notations :

Taking into account that the zero-dimensional variety V is contained in C^{n}, we define the norm ||V || as:

||V || := max{||α|| : α ∈ V }.

Furthermore, a natural number d ∈ IN is called a denominator of V if all elements in the set

d · V := {d · α : α ∈ V }

have algebraic integers as coordinates. The smallest denominator of V will be called the denominator of V and denoted by d_{V}.

With these notations we are able to state the following height estimation for zero-dimensional varieties:

Lemma 13 There exists a universal constant κ > 0 such that for any zerodimensional diophantine subvariety V of C^{n} and any c ∈ IN the following inequality holds:

ht_{V} (c) ≤ δ^{κ}(c + log_{2}(nd_{V} ||V ||)).

(This means the function ht_{V} is of order ht_{V} (c) = δ^{O(1)} (c + log_{2}(nd_{V} ||V ||))).

PROOF. Let V ⊂ C^{n} be a zero-dimensional diophantine variety of degree δ ∈ IN. The inequality is trivial for ht_{V} (c) = 1. Therefore we may suppose without loss of generality that the ring extension Q ⟶ Q[V] has a primitive element u which is the image of a linear form U = λ_{1}X_{1} + ⋯ + λ_{n}X_{n} ∈ ZZ[X_{1}, …, X_{n}] of height at most c. We just show the inequality:

2^{ht(q_{u}(T))} ≤ (2^{c+1}nd_{V} ||V ||)^{δ}

and leave the corresponding inequalities for ρ_{1}^{(u)}X_{1} − v_{1}^{(u)}(T), …, ρ_{n}^{(u)}X_{n} − v_{n}^{(u)}(T)) to the reader. Since d_{V} is a denominator for V and U has integer coordinates, d_{V} is also a denominator for the set of algebraic numbers u(V) contained in C. Therefore, if α_{1}, …, α_{δ} ∈ C^{n} are the points of V and if T is a new indeterminate, the polynomial

f(T) := ∏_{i=1}^{δ} (T − d_{V} u(α_{i}))

has integer coefficients, i.e. f(T) belongs to ZZ[T]. Moreover, the polynomial f(d_{V} T) vanishes on the set u(V). Since f and q_{u} have the same degree δ and since q_{u} is the primitive minimal polynomial of the image u of U in Q [V], the vanishing of f(d_{V} T) on u(V) implies the existence of a non-zero integer b ∈ ZZ such that f(T) = bq_{u}(T) holds. Taking into account |b| ≥ 1 and that the coefficients of f are elementary symmetric functions in the points of the set d_{V} · u(V) ⊂ C we deduce the following inequalities:

2^{ht(q_{u})} ≤ 2^{ht(f)} ≤ (2d_{V} ||u(V)||)^{δ} ≤ (2d_{V})^{δ}(n2^{c})^{δ}||V ||^{δ} ≤ (2^{c+1}nd_{V} ||V ||)^{δ}.

□

Again, let V be a zero-dimensional diophantine subvariety of C^{n} of degree δ. We estimate now the quantities d_{V} and ||V ||.

Proposition 14 Let c ∈ IN be a natural number such that the ring extension Q ⟶ Q[V] has a primitive element u := λ_{1}X_{1} + ⋯ + λ_{n}X_{n} ∈ ZZ[X_{1}, …, X_{n}] of height at most c. Then d_{V} and ||V || can be estimated as follows:

d_{V} ≤ |a_{δ}^{δ−1} ∏_{i=1}^{n} ρ_{i}^{(u)}|,

where a_{δ} is the leading coefficient of q_{u}(T) and ∏_{i=1}^{n} ρ_{i}^{(u)} is the discriminant obtained from the polynomials in Definition 10. It follows that V has denominators of height O((n + δ)ht_{V} (c)).

ii) the norm ||V || of V satisfies

||V || ≤ \sqrt{n}δ2^{δht_{V} (c)}.

PROOF. The integer |a_{δ}| is a denominator of the set u(V) because it is the leading coefficient of the polynomial q_{u}(T) which defines u(V). Since the polynomials ρ_{1}^{(u)}X_{1} − v_{1}^{(u)}(T), …, ρ_{n}^{(u)}X_{n} − v_{n}^{(u)}(T) “parametrize” the variety V in function of the zeroes of q_{u}(T), i.e. in function of the set u(V), we deduce that |a_{δ}^{δ−1} ∏_{i=1}^{n} ρ_{i}^{(u)}| is a denominator of V (notice that the degree of the polynomials v_{1}^{(u)}(T), …, v_{n}^{(u)}(T) is bounded by δ − 1).

¿From [39, Chapitre IV, Théorème 2 (ii)] one deduces :

||u(V)|| ≤ 2^{ht_{V} (c)}.

Thus, for α = (α_{1}, …, α_{n}) ∈ V and 1 ≤ k ≤ n we have:

|α_{k}| = |ρ_{k}^{(u)}|^{−1}|v_{k}^{(u)}(u(α))|.

Since ρ_{k}^{(u)} is an integer and v_{k}(T) is a polynomial of degree at most δ − 1 and of standard height at most 2^{ht_{V} (c)}, we conclude :

|α_{k}| ≤ δ2^{ht_{V} (c)}||u(V)||^{δ−1} ≤ δ2^{δht_{V} (c)}.

This implies

||V || := max\{||α|| : α ∈ V \} ≤ \sqrt{n}δ2^{δht_{V} (c)}.

Remark 1 The height is strongly related with complexity issues in polynomial equation solving. In fact, given a regular sequence of polynomials f_{1}, …, f_{n} ∈ ZZ[X_{1}, …, X_{n}] defining a zero-dimensional diophantine variety V, we have an upper bound for the length of the output of any algorithm which solves the system f_{1} = 0, …, f_{n} = 0 geometrically, namely:

(n + 1)deg V ht_{V} (c).

Here we assume tacitly that the output is given by a linear form representing a primitive element of the ring extension Q ⟶ Q [V] and by polynomials as in Definition 10 and that these polynomials are given in dense and their coefficients in bit representation.

It is also possible to give an upper bound for the height of zero-dimensional complete intersection varieties in terms of purely syntactical properties of its defining equations. This is the content of what follows, namely a weak form of the so-called arithmetical Bézout theorem ([3,4,8,9,19,46–48,34,35]).

Proposition 15 Let f_{1}, …, f_{n} ∈ ZZ[X_{1}, …, X_{n}] be polynomials of degree at most d and of height at most h. Suppose they define a zero-dimensional variety V := V (f_{1}, …, f_{n}). Then the function ht_{V} can be estimated as follows: for any c ∈ IN we have

ht_{V} (c) = d^{O(n)} · h · c.

Proposition 15 is an immediate consequence of [34]. Under the same assumptions as in Remark 1, namely that any algorithm which solves a given zerodimensional complete intersection polynomial equation system returns a primitive element and polynomials as in Definition 10, we can state the following obvious lower bound for the bit length of the output (again we suppose that the output polynomials as in Definition 10 are given in dense and their coefficients in bit representation):

Proposition 16 Let f_{1}, …, f_{n} ∈ ZZ[X_{1}, …, X_{n}] be a regular sequence defining a zero-dimensional diophantine variety V = V (f_{1}, …, f_{n}). Let η := min{ht(V; u) : u is a primitive element of the ring extension Q ⟶ Q[V]}. Then, the bit time–complexity of any algorithm solving f_{1} = 0, …, f_{n} = 0 geometrically is at least:

max{deg V, η}.

Let us now consider the case of diophantine complete intersection variety V of positive dimension. Let 1 ≤ i < n and let be given a smooth regular sequence of polynomials f_{1}, …, f_{i} ∈ ZZ[X_{1}, …, X_{n}] defining a (n − i)-dimensional diophantine complete intersection variety V. Let N_{V} be the class of all linear coordinate changes:

( Y_{1} ; ⋮ ; Y_{n} ) = ( \begin{matrix}a_{1,1} & ⋯ & a_{1,n} \\ ⋮ & & ⋮ \\ a_{n,1} & ⋯ & a_{n,n} \end{matrix} ) × ( X_{1} ; ⋮ ; X_{n} ),

such that the matrix A = (a_{ij})_{1≤i,j≤n} has integer entries (i.e. A ∈ M_{n}(ZZ), where M_{n}(ZZ) denotes the ring of n × n matrices of ZZ), A is non-singular and such that the ring extension

Q [Y_{1}, …, Y_{n−i}] ⟶ Q [Y_{1}, …, Y_{n}]/(f_{1}, …, f_{i}) = Q [V] (2)

is integral. The linear coordinate change given by the matrix A induces a finite morphism of affine varieties π : V ⟶ C^{n−i}. We consider for any linear form U = λ_{n−i+1}X_{n−i+1} + ⋯ + λ_{n}X_{n} with integer coefficients such that its image u in Q [V] is a primitive element of the ring extension above, the class F_{u} of all those points a ∈ ZZ^{n−i} which have unramified π-fiber and for which the image of u in the coordinate ring Q [V_{a}] of the fiber V_{a} := π^{−1}({a}) remains a primitive element of the ring extension Q ⟶ Q [V_{a}].

In a more down-to-earth language this means that we ask all the elements of V_{a} = π^{−1}(a) to be smooth points of V and the number deg V_{a} of elements of V_{a} to be equal to the rank of the free Q [Y_{1}, …, Y_{n−i}]-module Q [V]. Furthermore we ask the linear form U to generate a primitive element of the ring extension Q ⟶ Q [V_{a}]. (Observe that everything comes together since the smoothness of the elements of V_{a} implies that the zero-dimensional Q -algebra Q [V_{a}] is reduced.) Maintaining these notations we model our notion of height of algebraic varieties by means of the following function:

Definition 17 Given V a complete intersection diophantine variety as before, a linear change of coordinates A ∈ N_{V}, a linear form U ∈ ZZ[Y_{n−i+1}, …, Y_{n}] whose image u in Q [V] is a primitive element of the integral ring extension (2) and given a point a ∈ F_{u}, we define the height of V with respect to the triple (A, U, a) as:

ht(V; (A, U, a)) := ht(V_{a}; U).

Our first approximation to the notion of height of a diophantine complete intersection variety is given by the function ht_{V} : IN ⟶ IN which associates to any natural number c ∈ IN the value ht_{V} (c) := max{ht(V; (A, U, a)) | ht(A, U, a) ≤ c} if the triple (A, U, a) satisfies the assumptions of this definition, and which associates to c the value 1 if not.

2.3 Straight–line Programs

In the previous subsections we discussed the mathematical form and syntactical encoding of the output of the algorithm for geometric solving we are going to exhibit. However we also need a suitable encoding for input and intermediate results of our algorithm. As mathematical objects our inputs are polynomials with integer coefficients f ∈ ZZ[X_{1}, …, X_{n}]. These polynomials can be written as lists of monomials and this yields the first two possible encodings for input and intermediate results: dense and sparse encoding. Thus, if d is the degree of f and if h is an upper bound for its height, the length of f under dense encoding is

h · \binom{d + n}{n} = h · \binom{d + n}{d}.

Let us remark that the binomial coefficients appearing in this expression are polynomial in the number of variables in the case of “small” degree polynomials (e.g. the length of the dense encoding of f is h · \binom{n+2}{2} ≃ h · n^{2} if the degree of f is at most 2). Analogously the length of the dense encoding of f is polynomial in d for d >> n.

Alternatively, our input polynomial f may be given by representing just all its non-zero coefficients: this is the sparse encoding of the polynomial f. Then, if h is a bound of the height, d the degree and N the number of monomials with non-zero coefficients of f, the length of the sparse encoding of f becomes

h · N · n · log_{2}d.

However, in many practical applications our input polynomials may be given as programs. This is for instance the approach in the encoding of the inputs of the version of the 3SAT problem (Problem 1) we stated in the introduction. In the sequel we shall mainly restrict ourselves to the straight–line program encoding of polynomials in the following sense:

Definition 18 A generic straight–line program Γ′ over ZZ is a pair Γ′ = (G, Q), where G is a directed acyclic graph and Q is an assignment of instructions to the gates (i.e. vertices) of the graph. G contains n + 1 gates of indegree 0 which are Q-labeled by the variables X_{1}, …, X_{n}and by the constant 1 ∈ ZZ. They are called the input gates of Γ′. We define the depth of a gate ν of the graph G as the length of the longest path joining ν and some input gate. Let us denote the gates of the directed acyclic graph G by pairs of integer numbers (i, j), where i represents the depth of the gate and j is the corresponding value of an arbitrary numbering imposed on the set of gates of depth i (this encoding can be seen in [26,34,40,41,44]). Associated to the intermediate gate (i, j) we have the following operation:

Q_{i,j} := ( ∑_{0≤r≤i−1} A_{i,j}^{rs}Q_{rs}) · ( ∑_{0≤r′≤i−1} B_{i,j}^{r′s′}Q_{r′s′}),

where A_{i,j}^{rs}, B_{i,j}^{r′s′} are indeterminates called parameters of Γ′ and Q_{rs}, Q_{r′s′} are precomputed values corresponding to the gates (r, s) and (r′, s′).

We denote by Ā = (A_{ij}^{rs}), B̄ = (B_{ij}^{r′s′}) the list of all parameters in the straight– line program Γ′. The intermediate results Q_{ij} of Γ′ are therefore polynomials belonging to ZZ[Ā, B̄, X_{1}, …, X_{n}] and Γ′ represents a procedure which evaluates them. A (finite) set of polynomials f_{1}, …, f_{s} ∈ ZZ[X_{1}, …, X_{n}] is said to be evaluated by a straight–line program of generic type Γ′ with parameters in a set F ⊆ ZZ if specializing the coordinates of the parameters Ā and B̄ in Γ′ to values in F, there exist gates (i_{1}, j_{1}), …, (i_{s}, j_{s}) of Γ′ such that

f_{k} = Q_{i_{k}j_{k}}(ā, b̄, X_{1}, …, X_{n})

holds for 1 ≤ k ≤ s. Specializing in the indicated way the parameters of Γ′ into values of F we obtain a copy Γ of the directed acyclic graph G underlying the generic straight–line program Γ′ and of its instruction assignment Q. We call this copy Γ a straight–line program (of generic type Γ′) in ZZ[X_{1}, …, X_{n}] with parameters in F. The gates of Γ correspond to polynomials belonging to ZZ[X_{1}, …, X_{n}]. These polynomials are obtained from the intermediate results Q_{ij} of Γ′ by specializing adequately the parameters from which the depend. We shall call these polynomials the intermediate results of the straight–line program Γ. Furthermore the polynomials f_{1}, …, f_{s} are called (final) results or outputs of Γ. Alternatively, we shall say that f_{1}, …, f_{s} are represented, computed or evaluated by Γ.

The current complexity measures for the generic straight–line program Γ′ are:

– the size of Γ′ = the size of the graph G

– the non-scalar depth (Γ′) = the depth of the graph G

The size and non-scalar depth of the specialized straight–line program Γ are analogously defined. Additionally, for any straight–line program Γ in ZZ[X_{1}, …, X_{n}] with parameters in F ⊆ ZZ, we call the the maximum of the heights of the elements in F the height of the parameters of Γ or, for short, the height of Γ. The encoding of a polynomial f ∈ ZZ[X_{1}, …, X_{n}] by a straight–line program Γ in ZZ[X_{1}, …, X_{n}] with parameters of height h has (bit) length

2(L^{2}h + Llog_{2}L).

Note that the notion of straight–line program encoding covers as well the both notions of dense and sparse encoding of polynomials. This can be seen as follows: a polynomial of degree at most d and height at most h, given in dense encoding, can be evaluated by a straight–line program of size O(d\binom{d+n}{n}) and non-scalar depth O(log_{2}d) with parameters of height at most h. Similarly, if a polynomial f ∈ ZZ[X_{1}, …, X_{n}] has degree at most d, height h and N non-zero coefficients, it can be evaluated by a straight–line program of size O(d · N) and non-scalar depth O(log_{2}d) with parameters of height at most h.

2.4 Complexity of geometric solving

Now that the notions of geometric solving, degree and height of polynomial equation systems and straight–line programs and its distinct complexity measures have been introduced, we are able to state our main result, namely the following Theorem 19. This theorem represents our principal contribution to the solution of Problem 3 in Section 1.

Theorem 19 There exists a bounded error probabilistic Turing machine that from a smooth regular sequence f_{1}, …, f_{n} ∈ ZZ[X_{1}, …, X_{n}] outputs a linear form U ∈ ZZ[X_{1}, …, X_{n}] representing a primitive element u of the ring extension Q ⟶ Q[V], where V := V (f_{1}, …, f_{n}) is the algebraic variety defined by f_{1}, …, f_{n}, and polynomials of the form q_{u}(T), ρ_{1}^{(u)}X_{1} − v_{1}^{(u)}(T), …, ρ_{n}^{(u)}X_{n} − v_{n}^{(u)}(T) with ρ_{1}^{(u)}, …, ρ_{n}^{(u)} non-zero integers and q_{u}, v_{1}^{(u)}, …, v_{n}^{(u)} ∈ ZZ[T] such that these polynomials represent a geometric solution of the equation system f_{1} = 0, …, f_{n} = 0 (see Definition 10). The Turing machine finds this solution in time (counting the number of bit operations executed)

(ndhLδη)^{O(log_{2}n+ℓ)}

using only

(ndLδ)^{O(1)}

arithmetic operations in ZZ at unit cost. We assume that the polynomials f_{1}, …, f_{n}have degree at most d and that they are given by a straight–line program of size L and non-scalar depth ℓ with parameters of height at most h. The quantity δ defined by δ := max{deg V (f_{1}, …, f_{i}) : 1 ≤ i ≤ n} is the degree of the system f_{1} = 0, …, f_{n} = 0. Finally the quantity η is the height of the system f_{1} = 0, …, f_{n} = 0 defined as η := max{ht_{V_{i}}(c_{3}((log_{2}n+ℓ)·log_{2}δ)) : 1 ≤ i ≤ n} where c_{3} > 0 is a suitable universal constant independent of the specific input f_{1}, …, f_{n} (or even its size).

Theorem 19 follows from the description of the algorithm given in Section 3 below. Theorem 4 above follows immediately from Theorem 19 above by putting d := 2, L := n^{2}, ℓ := 2. Let us remark here that Theorem 19 improves and extends the main result of [25] and [26] to the bit complexity model. It sheds also new light on the main complexity outcome of the papers [55,20,11].

2.5 A Division Step in the Nullstellensatz

In this subsection we show how Nullstellensatz bounds imply Liouville estimates. This establishs a close connection between Problems 5 and 6 in the Introduction. Let us recall the assumptions in the statement of Theorem 7.

There is given a smooth regular sequence of polynomials f_{1}, …, f_{n} ∈ ZZ[X_{1}, …, X_{n}] of degree at most d and of height at most h, defining a zerodimensional affine variety V := V (f_{1}, …, f_{n}) ⊆ C^{n}. Moreover there is given a point α = (α_{1}, …, α_{n}) ∈ V and a real number 0 < ε ≤ 1. Finally, we assume that V ∩ Q [i]^{n} = ∅ holds. By a well-chosen linear change of coordinates we may assume without loss of generality V ∩ (Q [i] × C^{n−1}) = ∅. It is sufficient to show that the algebraic number α_{1} is hard to approximate in the sense of the conclusion of Theorem 7. For this purpose consider integers p ∈ ZZ[i] and q ∈ IN such that \frac{p}{q} is an approximation at level ε to the algebraic number α_{1}.

We introduce the following polynomial :

f_{n+1} := (qX_{1} − p)(qX_{1} − p̄)

(here p̄ stands for the complex conjugate of p). The assumption V ∩ (Q [i] × C^{n−1}) = ∅ implies that the sequence of polynomials f_{1}, …, f_{n+1} has no common zero in C^{n}. Therefore there exists a non-zero integer b ∈ ZZ and polynomials g_{1}, …, g_{n+1} ∈ ZZ[X_{1}, …, X_{n}] such that the following Bézout identity holds :

b = g_{1}f_{1} + ⋯ + g_{n+1}f_{n+1}.

Evaluating this identity at the point α ∈ V we obtain :

1 ≤ |b| = |g_{n+1}(α)| · |qα_{1} − p| · |qα_{1} − p̄|.

This yields the following estimate:

Proposition 20 With assumptions and notations as before, for any rational approximation a := (p_{1}/q, …, p_{n}/q) ∈ Q [i]^{n} at level ε to the point α ∈ V we have the inequality :

\frac{1}{|g_{n+1}(α)|q^{2}} ≤ ||a − α||(|α_{1}| + |\frac{p_{1}}{q} |).

In particular, for ||a − α|| < ε ≤ 1, we obtain the estimation :

\frac{ε^{−1}}{|g_{n+1}(α)|(2||α|| + 1)} ≤ q^{2}.

(Here p_{1}, …, p_{n} ∈ ZZ[i] are Gaussian integers and q ∈ IN is a natural number.)

¿From the second inequality we deduce that it is sufficient to bound the values of ||α|| and |g_{n+1}(α)| in order to obtain a Liouville estimate for the rational approximation a of the point α. Note that the bounds for ||α|| and |g_{n+1}(α)| which can be easily deduced from the known Nullstellensätze (as e.g. in [3,4,34]) would be insufficient for our purpose (proving Theorem 7) as they imply only a unspecific general estimate, namely

\frac{−log_{2}ε}{d^{Cn}h} < log_{2}|q|

for a suitable constant C > 0. A Liouville estimate of this type does not take into account the specific properties of the variety V expressed through its degree and height. The more specific bounds for ||α|| and |g_{n+1}(α)| as required for the proof of Theorem 7 by means of Proposition 20 are an immediate consequence of the following result:

Theorem 21 Let f_{1}, …, f_{n}, f_{n+1} ∈ ZZ[X_{1}, …, X_{n}] polynomials having no common zero in C^{n} and verifying the following assumptions:

– there exists a straight–line program of size L and non-scalar depth ℓ with parameters of height h that evaluates the polynomials f_{1}, …, f_{n}, f_{n+1}

– the degrees of the polynomials f_{1}, …, f_{n+1} are bounded by d and h′ is an upper bound for their heights

Let us furthermore assume that f_{1}, …, f_{n} form a smooth regular sequence which defines a zero-dimensional affine algebraic variety V = V (f_{1}, …, f_{n}). We also consider the following quantities:

– δ := deg(V)

– η := min ht(V) (i.e. η is the minimal value of ht_{V} distinct from 1)

Then there exists a straight–line program of size L(ndδ)^{O(1)} and non-scalar depth of order O(log_{2}n + log_{2}d + log_{2}δ + ℓ) with parameters of height at most O(max{h, h′, η, log_{2}n, ℓ}) which evaluates a non-zero integer a ∈ ZZ and a polynomial g_{n+1} ∈ ZZ[X_{1}, …, X_{n}] such that

a − g_{n+1} · f_{n+1}

belongs to the ideal (f_{1}, …, f_{n})generated by f_{1}, …, f_{n}in ZZ[X_{1}, …, X_{n}].

The proof of this theorem will follow from the description of the algorithm given in Section 4 below. Applying Theorem 21 and Lemma 23 below, we obtain a more precise upper bound for the value |g_{n+1}(α)|. From this bound together with Proposition 14 and 20 we then deduce easily Theorem 7.

3 An algorithm for Geometric Solving

The aim of this section is to establish a proof for Theorem 19. We describe an algorithm which implies Theorem 19. This algorithm works inductively on the codimension of the varieties V_{i} := V (f_{1}, …, f_{i}), 1 ≤ i ≤ n, and our main goal is to describe this recursion.

Recall that our input is a smooth regular sequence f_{1}, …, f_{n} ∈ ZZ[X_{1}, …, X_{n}] of degree at most d. We assume that this input is encoded by a straight–line program Γ of size L and non–scalar depth ℓ with parameters of height at most h that evaluates the polynomials f_{1}, …, f_{n}. Our algorithm computes a geometric solution of the zero-dimensional algebraic variety V := V (f_{1}, …, f_{n}) ⊆ C^{n}. In order to describe for 1 ≤ i ≤ n the i-th recursive step of our algorithm, we shall refer to the intermediate complete intersection algebraic varieties as V_{i} := V (f_{1}, …, f_{i}) and introduce the following parameters:

– δ_{i} := deg(V_{i}),

– δ := max{δ_{i} : 1 ≤ i ≤ n},

– η_{i} := ht_{V_{i}}(C), where C is a suitably chosen natural number of order O((log_{2}n + ℓ)log_{2}δ), such that Q [V_{i}] has a primitive element of height C with respect to a suitable Noether position of V_{i}.

– η := max{η_{i} : 1 ≤ i ≤ n}.

As a byproduct of our algorithm, we shall obtain geometric solutions of the algebraic varieties V_{i}. In fact, our algorithm computes for every 1 ≤ i ≤ n a ZZ-linear change of coordinates

(X_{1}, …, X_{n}) ⟶ (Y_{1}^{(i)}, …, Y_{n}^{(i)}),

such that the ring extension

R_{i} := Q [Y_{1}^{(i)}, …, Y_{n−i}^{(i)}] ⟶ B_{i} := Q [Y_{1}^{(i)}, …, Y_{n}^{(i)}]/(f_{1}, …, f_{i}) = Q [V_{i}]

is integral. The R_{i}-module B_{i} is a free module of rank D_{i} ≤ δ_{i}. Let us denote by π_{i} : V_{i} ⟶ C^{n−i} the projection on the first n − i coordinates of (Y_{1}^{(i)}, …, Y_{n}^{(i)}). The morphism π_{i} of affine varieties is finite.

Definition 22 Let assumptions and notations be as before. A lifting point for W := V_{i} of the finite morphism π_{i} is a point P = (p_{1}, …, p_{n−i}) ∈ ZZ^{n−i} with the following properties:

– the zero-dimensional fiber W_{P} := π_{i}^{−1}(P) has degree (i.e. cardinality) equal to the rank of B_{i} as free R_{i}-module (this means deg(W_{P}) = D_{i})

– the fiber W_{P} contains only smooth points. (This is equivalent to saying that the Jacobian matrix of the polynomials we obtain from f_{1}(Y_{1}^{(i)}, …, Y_{n}^{(i)}), …, f_{i}(Y_{1}^{(i)}, …, Y_{n}^{(i)}) by substituting for Y_{1}^{(i)}, …, Y_{n−i}^{(i)} the coordinates p_{1}, …, p_{n−i} of P is regular at every point of the fiber W_{P}.)

If P ∈ ZZ^{n−i} is a lifting point of the morphism π_{i} we will call its fiber W_{P} a lifting fiber of W = V_{i}. Observe that the elements of a lifting fiber of π_{i} are smooth points of W.

The lifting fibers W_{P} have the property that a geometric solution of the variety V_{i} can be reconstructed from the projection π_{i} and any geometric solution of the equations of such a fiber, (see Subsection 3.2 below). Our algorithm will choose for each 1 ≤ i ≤ n a suitable lifting point P_{i} ∈ ZZ^{n−i} of the morphism π_{i}. In the sequel we shall denote the lifting fiber of this point by V_{P_{i}}.

The following Section 3 is divided into two well–distinguished parts, namely:

i) Subsection 3.2, treating “lifting by a symbolic Newton method”, where we show how it is possible to reconstruct a geometric solution of the equations f_{1}, …, f_{i} from the lifting fiber V_{P_{i}}.

ii) Subsection 3.3, where we show how to find a linear coordinate change

(X_{1}, …, X_{n}) ⟶ (Y_{1}^{(i)}, …, Y_{n}^{(i)}), the lifting point P_{i} and a geometric solution of the equations of the lifting fiber V_{P_{i}}.

The i-th recursive step of our algorithm consists of the computation of the new variables Y_{1}^{(i+1)}, …, Y_{n}^{(i+1)}, the point P_{i+1} and a geometric solution of its fiber V_{P_{i+1}} from the data Y_{1}^{(i)}, …, Y_{n}^{(i)}, P_{i} and V_{P_{i}}.

Let us conclude this subsection with the following remark: let 1 ≤ i ≤ n and consider the lifting fiber V_{P_{i}}. Since the degree of V_{P_{i}} equals D_{i} = rank_{R_{i}}(B_{i}), any ZZ-linear form U_{i} := λ_{n−i+1}Y_{n−i+1}^{(i)} + ⋯ + λ_{n}Y_{n}^{(i)} which separates the points of V_{P_{i}} represents not only a primitive element of the ring extension Q ⟶ Q [V_{P_{i}}] but also a primitive element of the integral ring extension R_{i} ⊆ B_{i} (which we will denote by u_{i}). Our algorithm will compute a geometric solution of both V_{i} and V_{P_{i}} using such a linear form U_{i}.

Let us observe that the bit length of our geometric solution of the equations of V_{P_{i}} will be bounded by the quantity

(i + 1)(δ_{i} + 2)η_{i}.

3.1 Elementary operations and bounds for straight–line programs

In this subsection we collect some elementary facts about straight–line programs. We start with an estimate for the degree and height of a polynomial given by a straight–line program. In order to state our result with sufficient generality, let us observe that the notion of height makes sense mutatis mutandi for polynomials over any domain equipped with an absolute value.

Lemma 23 ([34]) Let R be a ring equipped with an absolute value |·| : R ⟶ IR. Suppose f ∈ R[X_{1}, …, X_{n}] is a polynomial which can be evaluated by a straight–line program Γ in R[X_{1}, …, X_{n}] of size L and non-scalar depth ℓ with parameters of height h. Let H > 0 be a real number and let α = (α_{1}, …, α_{n}) be a point in R^{n} such that log_{2}|α_{i}| ≤ H holds for 1 ≤ i ≤ n. Then f and f(α) satisfy the following estimations:

– deg(f) ≤ 2^{ℓ}

– ht(f) ≤ (2^{ℓ+1} − 1) · (h + log_{2}L)

– log_{2}|f(α)| ≤ (2^{ℓ+1} − 1) · (max{h, H} + log_{2}L)

One of the main ingredients used in our procedure below is the efficient computation of the coefficients of the characteristic polynomial of a matrix. We shall use for this task Berkowitz’ division-free and well parallelizable algorithm [6] (compare also [16] and [7] for historical predecessors of this algorithm). This is the content of the next lemma.

Lemma 24 ([6,34]) Let R be a domain. There exists a straight–line program of size N^{O(1)} and non-scalar depth O(log_{2}N) with parameters in {−1, 0, 1} that from the entries of any N × N input matrix over R computes all coefficients of the characteristic polynomial of the given matrix.

We use this algorithm not only for the computation of the characteristic polynomial of a given matrix but also for the computation of the greatest common divisor of two given univariate polynomials with coefficients in a unique factorization domain (this task can be reduced to solving a suitable linear equation system corresponding to the Bézout identity over the ground domain. See [34] for details).

The following result is an immediate consequence of the formal rules of derivation:

Lemma 25 Let R be a domain. For a given a finite set of polynomials f_{1}, …, f_{s} of R[X_{1}, …, X_{n}] which can be evaluated by a straight–line program β in R[X_{1}, …, X_{n}] of size L and non-scalar depth ℓ, there exists a straight–line program in R[X_{1}, …, X_{n}] of size (2n + 1)L and non-scalar depth ℓ + 1 with the same parameters as β which evaluates f_{1}, …, f_{s} and all the first partial derivatives:

\{\frac{∂f_{i}}{∂X_{j}} : 1 ≤ i ≤ s, 1 ≤ j ≤ n\}.

Combining this lemma with Lemma 24, one concludes: let f_{1}, …, f_{n} be a family of polynomials of R[X_{1}, …, X_{n}] which can be evaluated by a straight– line program β of size L and non-scalar depth ℓ. Then there exists a straight– line program in R[X_{1}, …, X_{n}] of size n^{O(1)}L and non-scalar depth O(ℓ+log_{2}n) with the same parameters as β which evaluates the Jacobian determinant:

J(f_{1}, …, f_{n}) := det(\frac{∂f_{i}}{∂X_{j}})_{1≤i,j≤n}.

In some exceptional cases the straight–line programs we are going to consider might contain divisions as operations. Since we are only interested in division-free straight–line programs, the following “Vermeidung von Divisionen” technique due to V. Strassen [58] becomes crucial:

Proposition 26 ([34], [58]) Let Γ be a (division-free) straight–line program in ZZ[X_{1}, …, X_{n}] of size L and depth ℓ with parameters of height h that computes a finite set of polynomials f_{0}, …, f_{m} of ZZ[X_{1}, …, X_{n}]. Assume that f_{0} ≠ 0 holds and that f_{0} divides f_{i} in ZZ[X_{1}, …, X_{n}] for any 1 ≤ i ≤ m. Then there exists a (again division-free) straight–line program Γ′ in ZZ[X_{1}, …, X_{n}] with the following properties:

i) Γ′ computes polynomials P_{1}, …, P_{m} of ZZ[X_{1}, …, X_{n}] and a non-zero integer θ such that for any 1 ≤ i ≤ m holds

P_{i} = θ\frac{f_{i}}{f_{0}} .

ii) Γ′ has size of order O(2^{2ℓ}(L + n + 2^{ℓ} + m)), depth of order O(ℓ) and its parameters have height of order max{h, O(ℓ)}.

Moreover, the height of θ is of order:

2^{O(ℓ)}(max{h, ℓ} + log_{2}L).

The proof of this proposition is based on the computation of the homogeneous components of a polynomial given by a straight–line program. This proof also provides an algorithm computing the homogenization of a polynomial given by a straight–line program. This is the content of the next lemma.

Lemma 27 ([34]) Suppose that we are given a polynomial P := ∑ P^{μ} X_{1}^{μ_{1}} … X_{n}^{μ_{n}} in ZZ[X_{1}, …, X_{n}] which can be evaluated by a straight line program Γ of size L and depth ℓ with parameters in a given set F ⊂ ZZ. Let be given a natural number D. Then there exists a straight line program Γ′ in ZZ[X_{1}, …, X_{n}] which computes all the homogeneous components of P having the following properties: Γ′ uses parameters from F, has size (D + 1)^{2}L and non-scalar depth 2ℓ.

In Section 4 we shall work with a specific polynomial which we call the pseudojacobian determinant of a given regular sequence. We introduce now this polynomial and say how it can be evaluated. Let R be a domain containing Q. Let K be the field of fractions of R and let f_{1}, …, f_{n} ∈ R[X_{1}, …, X_{n}] be a regular sequence in K[X_{1}, …, X_{n}]. Furthermore, let Y_{1}, …, Y_{n} be new variables. We write Y = (Y_{1}, …, Y_{n}). Fix 1 ≤ j ≤ n. By f_{j}^{(Y)} := f_{j}(Y_{1}, …, Y_{n}) we denote the polynomial derived from f_{j} by substituting the variables X_{1}, …, X_{n} by Y_{1}, …, Y_{n}. In the polynomial ring R[Y_{1}, …, Y_{n}, X_{1}, …, X_{n}] we decompose the polynomial f_{j}^{(Y)} − f_{j} in the following (non-unique) way:

f_{j}^{(Y)} − f_{j} = ∑_{k=1}^{n} l_{k,j}(Y_{k} − X_{k}),

with l_{k,j} ∈ R[Y_{1}, …, Y_{n}, X_{1}, …, X_{n}]. Let us consider the determinant Δ of the matrix A = (l_{k,j})_{1≤k,j≤n}, namely:

Δ := det(A).

This determinant is called the pseudo-jacobian determinant of the regular sequence of polynomials f_{1}, …, f_{n}. If d is a bound for the degrees of f_{1}, …, f_{n}and these polynomials are given by a straight–line program β of size L and nonscalar depth ℓ, then there is a straight–line program β′ of size (nd)^{O(1)}L and non-scalar depth O(log_{2}n + ℓ) which evaluates the pseudo-jacobian determinant Δ. The straight–line program β′ uses apart from the same parameters as β only parameters of ZZ of height O(log_{2}d).

We shall also consider the execution of straight–line programs in matrix rings. The situations where we apply these considerations will be of the following type: Let R be a domain. Suppose that there is given a polynomial g ∈ R[X_{1}, …, X_{n}] by a straight–line program β in R[X_{1}, …, X_{n}] of size L and non-scalar depth ℓ. Suppose also that there are given n commuting D × D matrices M_{1}, …, M_{n} over R. In such a situation the entries of the matrix g(M_{1}, …, M_{n}) can be computed from the entries of of M_{1}, …, M_{n} and the parameters of β by a straight–line program β′ in R of size D^{O(1)}L and non-scalar depth O(ℓ). The new parameters of β′ are just the values 0, 1 (see [27] for details).

Another important aspect of our main algorithm is its probabilistic (or alternatively its non-uniform) character. This is the content of the next definition and proposition.

Definition 28 Let be given a set of polynomials W ⊆ ZZ[X_{1}, …, X_{n}]. A finite set Q ⊆ ZZ^{n} is called a correct test sequence (or questor set) for W if for any polynomial f belonging to W the following implication holds:

f(x) = 0 for all x ∈ Q implies f = 0.

Denote by W(n, L, ℓ) the class of all polynomials of ZZ[X_{1}, …, X_{n}] which can be evaluated by straight–line programs of size at most L and of non-scalar depth at most ℓ. The following result says that for the class W(n, L, ℓ) exist many correct test sequences of moderate length.

Proposition 29 ([32,34]) Let be given natural numbers n, ℓ, L with L ≥ n+1 and consider the following quantities:

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

Then the finite set \{1, …, u\}^{nt} ⊂ ZZ^{nt} contains at least u^{nt} (1 − u^{− \frac{t}{6}} ) correct test sequences of length t for W(n, L, ℓ). In particular the set of correct test sequences for W(n, L, ℓ) of length t containing only test points from {1, …, u}^{n} is not empty.

¿From Lemma 23 we deduce the following complexity estimate:

Let f ∈ ZZ[X_{1}, …, X_{n}] be a polynomial given by a straight–line program of size L and non-scalar depth ℓ with parameters of height h. Let α ∈ ZZ^{n} be a point of height h′ given in bit representation. Then there exists a (deterministic) ordinary Turing machine which computes the bit representation of the value f(α) in time (2^{ℓ}Lmax{h, h′})^{O(1)}.

In the next subsection we shall make use of a problem adapted version of the Hensel-Newton iteration. We are now going to describe a suitable division-free symbolic form of this procedure.

Let R be a polynomial ring over Q , let K be its field of fractions and let f_{1}, …, f_{n} ∈ R[X_{1}, …, X_{n}] be polynomials of degree at most d. Suppose that f_{1}, …, f_{n} are given by a (division-free) straight–line program β of size L and non–scalar depth ℓ. Let us also assume that the Jacobian matrix D(f) := D(f_{1}, …, f_{n}) := (\frac{∂f_{i}}{∂X_{j}} )_{1≤i,j≤n} of the polynomials f_{1}, …, f_{n} is regular. We consider now the following Newton–Hensel operator:

N_{f}(X_{1}, …, X_{n}) := ( X_{1} ; ⋮ ; X_{n} ) − D(f)^{−1} ( f_{1}(X_{1}, …, X_{n}) ; ⋮ ; f_{n}(X_{1}, …, X_{n}) ) . (3)

This operator is given as a vector of n rational functions of K(X_{1}, …, X_{n}). This is also true for the k-th iteration of this operator, which we denote by N_{f}^{k}. For any k ∈ IN there exist numerators (g_{1}^{(k)}, …, g_{n}^{(k)}) ∈ R[X_{1}, …, X_{n}] and a non-zero denominator h^{(k)} ∈ R[X_{1}, …, X_{n}] such that N_{f}^{k} can be written as:

N_{f}^{k} = (\frac{g_{1}^{(k)}}{h^{(k)}} , …, \frac{g_{n}^{(k)}}{h^{(k)}} ) ∈ K(X_{1}, …, X_{n})^{n}.

The next lemma gives a description of a division-free straight–line program in R[X_{1}, …, X_{n}] that evaluates numerators and denominators for N_{f}^{k}.

Lemma 30 Let notations and assumptions be as before. Let k be a natural number. There exists a straight–line program in R[X_{1}, …, X_{n}] of size O(kd^{2}n^{7}L) and non-scalar depth O((log_{2}n + ℓ)k) with the same parameters as β which evaluates numerators g_{1}^{(k)}, …, g_{n}^{(k)} and a (non-zero) denominator h^{(k)} for the k-fold iteration N_{f}^{k} of the Newton-Hensel operator N_{f}.

PROOF. Let A(f) = (a_{ij})_{1≤i,j≤n} be the transposed matrix of the adjoint matrix of D(f). Both A(f) and the Jacobian determinant J(f) := det(D(f)) can be evaluated by a straight–line program of size O(n^{5} +nL) and non–scalar depth O(log_{2}n + ℓ), as it can be seen just by combining Lemmata 24 and 25.

We can write the operator N_{f} as

N_{f} = \frac{J(f) ( X_{1} ; ⋮ ; X_{n} ) − A(f) ( f_{1}(X_{1}, …, X_{n}) ; ⋮ ; f_{n}(X_{1}, …, X_{n}) )}{J(f)}. (4)

The entries a_{ij} of the matrix A(f) are polynomials of the ring R[X_{1}, …, X_{n}] having degree at most (n − 1)(d − 1). Moreover, the Jacobian determinant J(f) is a polynomial of R[X_{1}, …, X_{n}] having degree at most n(d − 1). For 1 ≤ i ≤ n we consider

g_{i} := J(f)X_{i} − ∑_{j=1}^{n} a_{i,j}f_{j}.

All polynomials appearing on the right hand side of the definition of g_{i} as summands have degree bounded by ν := nd + 1. Thus the degree of any g_{i} is bounded by ν. Let ^{h}g_{i}(X_{0}, X_{1}, …, X_{n}) ∈ R[X_{0}, …, X_{n}] be the homogenization of g_{i} by a new variable X_{0} and let ^{h}J(f)(X_{0}, X_{1}, …, X_{n}) ∈ R[X_{0}, …, X_{n}] be the homogenization of the Jacobian determinant J(f) by X_{0}.

We introduce now the following homogeneous polynomials (forms):

– G_{i}(X_{0}, …, X_{n}) := X_{0}^{ν−deg(g_{i})}(^{h}g_{i}),

– H(X_{0}, …, X_{n}) := X_{0}^{ν−deg(J(f))}(^{h}J(f)).

According to Lemma 27, there exists a division-free straight–line program in R[X_{1}, …, X_{n}] of size O(d^{2}(n^{7}+n^{3}L)) and non–scalar depth O(log_{2}n+ℓ) which evaluates the forms G_{1}, …, G_{n}, H. We now define recursively the following polynomials:

– for k = 1, 1 ≤ i ≤ n let g_{i}^{(1)} := G_{i}(1, X_{1}, …, X_{n}), h^{(1)} := H(1, X_{1}, …, X_{n}),

– for k ≥ 2, 1 ≤ i ≤ n let g_{i}^{(k)} := G_{i}(h^{(k−1)}, g_{1}^{(k−1)}, …, g_{n}^{(k−1)}), h^{(k)} := H(h^{(k−1)}, g_{1}^{(k−1)}, …, g_{n}^{(k−1)}).

It is easy to see that these polynomials g_{1}^{(k)}, …, g_{n}^{(k)} are numerators and that the polynomial h^{(k)} is a denominator of the iterated Newton-Hensel operator N_{f}^{k}. A straight–line program evaluating them is obtained by iterating k times the straight–line program which computes G_{1}, …, G_{n} and H. No new parameters are introduced by this procedure. Putting all this together we obtain the complexity bounds in the statement of Lemma 30. □

3.2 Lifting fibers by the symbolic Newton-Hensel algorithm

The idea of using a symbolic adaptation of Newton–Hensel iteration for lifting fibers was introduced in [25]. For technical reasons, in this paper it was necessary to use algebraic parameters for the lifting process. We present here a new version of this lifting algorithm in which the use of algebraic numbers is replaced by a certain matrix with integer entries. The whole procedure therefore becomes completely rational. The new lifting process is described in the statement of the next theorem and its proof.

Let notations and assumptions be as the same as at the beginning of this section. We fix 1 ≤ i ≤ n and assume for the sake of notational simplicity that the variables X_{1}, …, X_{n}are already in Noether position with respect to the variety V_{i}, the variables X_{1}, …, X_{n−i} being free. We suppose that the lifting point P_{i}, the coordinates of the ZZ-linear form U_{i} and a geometric solution for the equations of the lifting fiber V_{P_{i}} are explicitly given. With these conventions we state the main result of this subsection as follows:

Theorem 31 There exists a (division-free) straight–line program Γ_{i} in the polynomial ring ZZ[X_{1}, …, X_{n−i}, U_{i}] of size (idδ_{i}L)^{O(1)} and non-scalar depth O((log_{2}i + ℓ)log_{2}δ_{i}) using as parameters

– the coordinates of P_{i}

– the integers appearing in the geometric solution of the equations of the lifting fiber V_{P_{i}} and

– the parameters of the input program Γ

such that the straight–line program Γ_{i} computes

– the minimal polynomial q_{i} ∈ ZZ[X_{1}, …, X_{n−i}, U_{i}] of the primitive element u_{i} of the ring extension Q[X_{1}, …, X_{n−i}] ⟶ Q[V_{i}] = Q[X_{1}, …, X_{n}]/(f_{1}, …, f_{i}),

– polynomials ρ_{n−i+1}^{(i)}, …, ρ_{n}^{(i)} ∈ ZZ[X_{1}, …, X_{n−i}], ρ := ∏_{k=n−i+1}^{n} ρ_{k}^{(i)} and poly-

nomials v_{r+1}^{(i)}, …, v_{n}^{(i)} ∈ ZZ[X_{1}, …, X_{n−i}, U_{i}] with max{deg_{U_{i}}v_{j}^{(i)} ; r < j ≤ n} < δ_{i} such that

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

holds. Without loss of generality we may assume that Γ_{i} represents the coefficients of the polynomials q_{i} and v_{r+1}^{(i)}, …, v_{n}^{(i)} with respect to U_{i}.

PROOF. Under our hypotheses, namely that X_{1}, …, X_{n}are in Noether position with respect to the variety V_{i}, the variables X_{1}, …, X_{n−i} being free, we have the following integral ring extension of reduced rings:

R_{i} := Q [X_{1}, …, X_{n−i}] ⟶ B_{i} := Q [X_{1}, …, X_{n}]/(f_{1}, …, f_{i}).

Let P_{i} = (p_{1}, …, p_{n−i}) ∈ ZZ^{n−i} be a lifting point of the morphism π_{i} and let V_{P_{i}} = π_{i}^{−1}(P_{i}) be its lifting fiber. We have deg V_{P_{i}} = D_{i} = rank_{R_{i}}B_{i} ≤ deg V_{i} = δ_{i}. Let U_{i} = λ_{n−i+1}X_{n−i+1} +⋯+λ_{n}X_{n}∈ ZZ[X_{n−i+1}, …, X_{n}] generate a primitive element of the ring extension Q ⟶ Q [V_{P_{i}}] (i.e. U_{i} separates the points of V_{P_{i}}). The minimal polynomial of the image of U_{i} in B_{i} has degree at least the cardinality of the set U_{i}(V_{P_{i}}). Since the linear form U_{i} separates the points of V_{P_{i}}, this cardinality is deg V_{P_{i}} = rank_{R_{i}}B_{i}. We conclude that U_{i} generates also a primitive element of the ring extension R_{i} ⟶ B_{i}.

In the sequel we denote the primitive element generated by the linear form U_{i} in the ring extensions Q ⟶ Q [V_{P_{i}}] and R_{i} ⟶ B_{i} by the same letter u_{i}.

By hypothesis the following data is given explicitly (i.e. by the bit representation of their coefficients):

– the primitive minimal equation q ∈ ZZ[T] of the primitive element u_{i} of Q [V_{P_{i}}],

– the parametrization of V_{P_{i}} by the zeroes of q, given by the equations

X_{1} − p_{1} = 0, …, X_{n−i} − p_{n−i} = 0, q(T) = 0,
ρ_{n−i+1}X_{n−i+1} − v_{n−i+1}(T) = 0, …, ρ_{n}X_{n} − v_{n}(T) = 0,

where v_{n−i+1}, …, v_{n} are polynomials of ZZ[T] of degree strictly less than D_{i} = deg q and ρ_{n−i+1}, …, ρ_{n} are non-zero integers. Check again Definition 10 to see that the polynomials ρ_{n−i+1}X_{n−i+1}−v_{n−i+1}(T), …, ρ_{n}X_{n}−v_{n}(T) are assumed to be primitive.

Let a ∈ ZZ be the leading coefficient of q.

We consider now f_{1}, …, f_{i} as polynomials in the variables X_{n−i+1}, …, X_{n}, i.e. as elements of the polynomial ring R_{i}[X_{n−i+1}, …, X_{n}]. Let f := (f_{1}, …, f_{i}) and let

D(f) := (\frac{∂f_{k}}{∂X_{j}} )_{{1≤k≤i \atop n−i+1≤j≤n}}

be the corresponding Jacobian matrix of f (with respect to the variables X_{n−i+1}, …, X_{n}). Recall that the Newton operator with respect to these variables is defined as

N_{f} = ( X_{n−i+1} ; ⋮ ; X_{n} ) − D(f)^{−1} ( f_{1} ; ⋮ ; f_{i} ) .

Let κ be a natural number. Using Lemma 30, we deduce the existence of numerators g_{n−i+1}, …, g_{n} and a non-zero denominator h in the polynomial ring R_{i}[X_{n−i+1}, …, X_{n}] such that the following κ-fold iterated Newton operator has the form:

N_{f}^{κ} = ( ⋮_{\frac{g_{n}}{h}}^{\frac{g_{n−i+1}}{h}} ) .

Now, let M_{X_{n−i+1}}, …, M_{X_{n}} be the matrices describing the multiplication tensor of the Q -algebra Q [V_{P_{i}}] (recall that by assumption a geometric solution of the polynomial equation system defining V_{P_{i}} is given and that therefore the matrices M_{X_{n−i+1}}, …, M_{X_{n}} are known).

Let M denote the companion matrix of the polynomial a^{−1}q(T) ∈ Q [T]. Let n − i + 1 ≤ j ≤ n. The following identity is immediate:

ρ_{j}M_{X_{j}} = v_{j}(M).

Moreover the matrices ρ_{j}a^{D_{i}−1}M_{X_{j}} have integer entries. Let κ := ⌈1 + log_{2}δ_{i}⌉ and note that κ ≥ 1 + log_{2}D_{i} holds. Our straight–line program Γ_{i} will execute κ Newton steps in a subroutine which we are going to explain now: Let us consider the following column vector of matrices N_{n−i+1}, …, N_{n} with entries in Q (X_{1}, …, X_{n−i}):

( N_{n−i+1} ; ⋮ ; N_{n} ) := N_{f}^{κ}(\underline{M}) = ( ⋮_{\frac{g_{n}(X_{1},...,X_{n−i},\underline{M})}{h(X_{1},...,X_{n−i},\underline{M})}}^{\frac{g_{n−i+1}(X_{1},...,X_{n−i},\underline{M})}{h(X_{1},...,X_{n−i},\underline{M})}} ) ,

where \underline{M} = (M_{X_{n−i+1}}, …, M_{X_{n}}) and g_{n−i+1}, …, g_{n} are the numerator and h the denominator polynomial of Lemma 30. Finally, let us consider the matrix

M := U_{i}(N_{n−i+1}, …, N_{n}) = λ_{n−i+1}N_{n−i+1} + ⋯ + λ_{n}N_{n}.

This matrix is a matrix whose entries are rational functions of Q(X_{1}, …, X_{n−i}). From the fact that P_{i} = (p_{1}, …, p_{n−i}) is a lifting point and from the proof of Lemma 30 one deduces easily that in fact the entries of M belong to the local ring

R_{P_{i}} := (R_{i})_{(X_{1}−p_{1},...,X_{n−i}−p_{n−i})} = Q [X_{1}, …, X_{n−i}]_{(X_{1}−p_{1},...,X_{n−i}−p_{n−i})}.

Let T be a new variable. With these notations and assumptions we have the following result:

Lemma 32 Let χ ∈ Q (X_{1}, …, X_{n−i})[T] be the characteristic polynomial of M and m_{u_{i}} ∈ R_{i}[T] the minimal integral equation of the primitive element

u_{i} of B_{i} over R_{i}. Let χ(T) = T^{D_{i}} + ∑_{k=0}^{D_{i}−1} a_{k}T^{k} and m_{u_{i}} = T^{D_{i}} + ∑_{k=0}^{D_{i}−1} b_{k}T^{k}

with a_{k}, b_{k} ∈ Q (X_{1}, …, X_{n−i}) for 0 ≤ k ≤ D_{i} − 1. Then all these coefficients satisfy the condition ord_{P_{i}}(a_{k} − b_{k}) ≥ δ_{i} + 1, where ord_{P_{i}} denotes the usual order function (additive valuation) of the local ring R_{P_{i}}.

PROOF. Let V_{P_{i}} = {ξ_{1}, …, ξ_{D_{i}}} and fix 1 ≤ l ≤ D_{i}. Let ζ_{l}:= U_{i}(ξ_{l}). Because of the hypothesis made on the lifting fiber V_{P_{i}} and from Hensel’s Lemma (which represents a symbolic version of the Implicit Function Theorem) we deduce that there exist formal power series R_{n−i+1}^{(l)}, …, R_{n}^{(l)} ∈ C[[X_{1} − p_{1}, …, X_{n−i} − p_{n−i}]] with R_{n−i+1}^{(l)}(P_{i}) = ξ_{n−i+1}^{(l)}, …, R_{n}^{(l)}(P_{i}) = ξ_{n}^{(l)} such that for R^{(l)} := (X_{1} − p_{1}, …, X_{n−i} − p_{n−i}, R_{n−i+1}^{(l)}, …, R_{n}^{(l)}) the identities

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

hold in C[[X_{1} − p_{1}, …, X_{n−i} − p_{n−i}]]. Let u^{(l)} := U_{i}(R^{(l)}) = λ_{n−i+1}R_{n−i+1}^{(l)} + ⋯ + λ_{n}R_{n}^{(l)}. As shown in [25], the minimal polynomial m_{u_{i}} of the primitive element u_{i} verifies in C[[X_{1} − p_{1}, …, X_{n−i} − p_{n−i}]][T] the identity

m_{u_{i}} = ∏_{1≤l≤D_{i}}(T − u^{(l)}). (6)

Let us now consider the construction above which produces the matrix M ∈ (R_{P_{i}})^{D_{i}×D_{i}} starting with the matrix M ∈ Q ^{D_{i}×D_{i}} (recall that M is the companion matrix of the polynomial a^{−1}q(T) ∈ Q [T]). The same construction transforms the D_{i} distinct eigenvalues of the diagonalizable matrix M, namely the values ζ_{l} = U_{i}(ξ_{l}), 1 ≤ l ≤ D_{i}, into eigenvalues of M. (Observe that by construction M is a rational function of the matrix M and therefore the same rational function applied to any eigenvalue of M produces an eigenvalue of M). As shown in [25], in this way we obtain D_{i} distinct rational functions ũ^{(l)} ∈ C(X_{1}, …, X_{n−i}), which are eigenvalues of M. Moreover these rational functions are all defined in the point P_{i} (this means that ũ^{(l)} ∈ C[X_{1}, …, X_{n−i}]_{(X_{1}−p_{1},...,X_{n−i}−p_{n−i})} holds). For 1 ≤ l ≤ D_{i} the rational functions ũ^{(l)} can therefore be interpreted as elements of the power series ring C[[X_{1} − p_{1}, …, X_{n−i} − p_{n−i}]] and they satisfy in this ring the condition

u^{(l)} − ũ^{(l)} ∈ (X_{1} − p_{1}, …, X_{n−i} − p_{n−i})^{δ_{i}+1}. (7)

(For a proof of these congruence relations see [25]).

Let us now consider the characteristic polynomial χ of the matrix M. Since the coefficients of M belong to R_{P_{i}} = Q [X_{1}, …, X_{n−i}]_{(X_{1}−p_{1},...,X_{n−i}−p_{n−i})}, the coefficients of χ do so too. Therefore χ can be interpreted as a polynomial in the variable T with coefficients in the power series ring Q[[X_{1} −p_{1}, …, X_{n−i} − p_{n−i}]]. From the fact that the rational functions ũ^{(1)}, …, ũ^{(D_{i})} represent D_{i} distinct eigenvalues of M we deduce that

χ(T) = ∏_{1≤l≤D_{i}}(T − ũ^{(l)}) (8)

holds. Let σ_{k} denote the k–th elementary symmetric function in D_{i} arguments. The identity (8) implies that for 0 ≤ k ≤ D_{i} − 1 we can write the coefficient a_{k} of χ(T) as a_{k} = (−1)^{D_{i}−k}σ_{k}(ũ^{(1)}, …, ũ^{(D_{i})}). ¿From the identity (6) we deduce that the k-th coefficient b_{k} of the polynomial m_{u_{i}} satisfies b_{k} = (−1)^{D_{i}−k}σ_{k}(u^{(1)}, …, u^{(D_{i})}). From the congruence relations (7) and the identities (6) and (8) we conclude now that for 0 ≤ k ≤ D_{i} − 1 the congruence relations

a_{k} − b_{k} ∈ (X_{1} − p_{1}, …, X_{n−i} − p_{n−i})^{δ_{i}+1} (9)

hold in Q [[X_{1} − p_{1}, …, X_{n−i} − p_{n−i}]]. This proves the lemma. □

We continue now the proof of Theorem 31. In order to see how to evaluate the coefficients of χ, let us consider θ := det(h(\underline{M})) ∈ R_{i} and the matrix

M_{1} := θM.

This matrix M_{1} has entries in R_{i}. Now we have the identities

det(T · Id_{D_{i}} − M) = det(T · Id_{D_{i}} − θ^{−1}M_{1}) = θ^{−D_{i}}det((θT)Id_{D_{i}} − M_{1}).

Let ϕ(T) = T^{D_{i}} + ϕ_{D_{i}−1}T^{D_{i}−1} + ⋯ + ϕ_{0} ∈ R_{i}[T] be the characteristic polynomial of M_{1}. From the identities above we deduce that for 0 ≤ k ≤ D_{i} − 1 the k-th coefficient of χ can be written as

a_{k} = \frac{θ^{k}Φ_{k}}{θ^{D_{i}}} .

Executing κ = ⌈1 + log_{2}δ_{i}⌉ steps in the Newton iteration (as given at the beginning of this proof) to produce the entries of the matrix M, θ, M and finally M_{1} (in this order) and applying Lemma 24 we produce a straight– line program Γ′_{i} in Q (X_{1}, …, X_{n−i}) of non-scalar size O(log_{2}δ_{i}d^{3}i^{6}L) and non-scalar depth O((log_{2}i + ℓ)log_{2}δ_{i}) using as parameters those given by the statement of Theorem 31 such that Γ′_{i} evaluates the family of polynomials 1, θ, …, θ^{D_{i}}, ϕ_{0}, …, ϕ_{D_{i}−1} ∈ R_{i}.

Now, applying Strassen’s Vermeidung von Divisionen technique (Proposition 23) we obtain a division-free straight–line program Γ′′_{i} in Q [X_{1}, …, X_{n−i}] of size (idδ_{i}L)^{O(1)}, non-scalar depth O((log_{2}i + ℓ)log_{2}δ_{i}) using as parameters the coordinates p_{1}, …, p_{n−i} of P_{i}, the coefficients of the linear change of coordinates for the Noether normalization for V_{i}, the rational numbers appearing as coefficients in the geometric solution of the lifting fiber V_{P_{i}} and the parameters of Γ such that Γ′′_{i} evaluates for each 0 ≤ k ≤ D_{i} − 1 the expansion of a_{k} in Q[[X_{1} − p_{1}, …, X_{n−i} − p_{n−i}]] up to terms of degree of order δ_{i} + 1. Taking into account the congruence relations (9) we see that the division–free straight–line program Γ′′_{i} evaluates polynomials g_{0}, …, g_{D_{i}−1} ∈ Q [X_{1}, …, X_{n−i}] such that

b_{k} − g_{k} ∈ (X_{1} − p_{1}, …, X_{n−i} − p_{n−i})^{δ_{i}+1}

holds in Q [[X_{1} − p_{1}, …, X_{n−i} − p_{n−i}]] for any 0 ≤ k ≤ D_{i} − 1. ¿From [25] we deduce that the degrees of the coefficients b_{k} of the minimal polynomial m_{u_{i}} ∈ R_{i}[T] do not exceed δ_{i}. Putting all this together, we conclude that

b_{k} = g_{k}

holds for any 0 ≤ k ≤ D_{i} − 1. This means that the division-free straight– line program Γ′′_{i} computes the coefficients of the polynomial q_{i} := m_{u_{i}} ∈ Q [X_{1}, …, X_{r}, U_{i}] = R_{i}[U_{i}].

In order to compute the parametrizations v_{n−i+1}^{(i)}, …, v_{n}^{(i)} ∈ Q[X_{1}, …, X_{n−i}, T] we have to use the same kind of techniques (namely truncated Newton–Hensel iteration) combined with the arguments developed in [34] and applied in [25] and [26]. Let us be more exact:

Let n − i + 1 ≤ k ≤ n, let Z_{k} be a generic linear combination of the variables X_{k} and U_{i} (one may use a new indeterminate for that) and let m_{X_{k}} ∈ R_{i}[X_{k}] and m_{Z_{k}} ∈ R_{i}[Z_{k}] be the minimal polynomials of the R_{i}- linear endomorphisms given by the images of X_{k} and Z_{k} in the R_{i}-algebra B_{i} = Q [V_{i}] = Q [X_{1}, …, X_{n}]/(f_{1}, …, f_{i}). The polynomials m_{X_{k}} and m_{Z_{k}} are monic and hence squarefree. We compute the coefficients of the polynomials m_{X_{k}} ∈ R_{i}[X_{k}] and m_{Z_{k}} ∈ R_{i}[Z_{k}] in the same way as before the coefficients of q_{i} = m_{u_{i}}. So, we have two monic squarefree polynomials m_{X_{k}} ∈ R_{i}[X_{k}] and m_{Z_{k}} ∈ R_{i}[Z_{k}]. Taking into account that by the choice of Z_{k} the variable U_{i} is a generic linear combination of X_{k} and Z_{k} and therefore separates the associated primes of the ideal (m_{X_{k}}, m_{Z_{k}}) in R_{i}[X_{k}, Z_{k}] = R_{i}[X_{k}, U_{i}] we can apply directly Lemma 26 in [34] in order to obtain the parametrization associated to the variable X_{k}. Doing the same for each of the variables involved, namely the variables X_{n−i+1}, …, X_{n}, and putting together the corresponding straight–line programs, we obtain a procedure and a straight–line program Γ_{i} of the desired complexity which computes the output of Theorem 31. □

3.3 The recursion

Proposition 33 There exists a division-free arithmetic network of non-scalar size (idδ_{i}L)^{O(1)} and non-scalar depth O((log_{2}i + ℓ)log_{2}δ_{i}) using parameters of logarithmic height bounded by max{h, η_{i}, O((log_{2}i + ℓ)log_{2}δ_{i})} which takes as input

– a Noether normalization for the variety V_{i},

– a lifting point P_{i} and

– a geometric solution of the lifting fiber V_{P_{i}}

and produces as output

– a linear change of variables (X_{1}, …, X_{n}) ⟶ (Y_{1}^{(i+1)}, …, Y_{n}^{(i+1)}) such that the new variables Y_{1}^{(i+1)}, …, Y_{n}^{(i+1)} are in Noether position with respect to V_{i+1},

– a lifting point P_{i+1} for V_{i+1} and

– a geometric solution for the lifting fiber V_{P_{i+1}}.

PROOF. The construction of the arithmetic network proceeds in three stages. In the first stage we apply the algorithm underlying Theorem 31. In the second stage we intersect algorithmically the variety V_{i} with the hypersurfcae V (f_{i+1}) in order to produce first a Noether normalization of the variables with respect to the variety V_{i+1} = V_{i} ∩ V (f_{i+1}). Then we produce a linear form U_{i+1} representing a primitive element u_{i+1} of the integral ring extension R_{i+1} ⟶ B_{i+1} and a straight–line program representing polynomials analogous to the one in the conclusion of Theorem 31. For this purpose we use the algorithm underlying the proof of Proposition 14 in [25]. The only point we have to take care of is that we are working now over the ground field Q and that we have to take into account the heights of the parameters of Q we introduce in this straight–line program.

We remark that the straight–line program in question has non-scalar size (idδ_{i}L)^{O(1)} and non-scalar depth O(log_{2}(dδ_{i}) + ℓ) with parameters of logarithmic height bounded by O(log_{2}(dδ_{i}) + ℓ). In the third and final stage we consider the polynomial

J(f_{1} …, f_{i+1}) := det (\frac{∂f_{k}}{∂X_{j}} )_{{1≤k≤i+1 \atop n−i≤j≤n}} ,

which is a nonzero divisor modulo the ideal I_{i+1} = (f_{1}, …, f_{i+1}). Let us observe that the polynomial J(f_{1} …, f_{i+1}) can be evaluated by a division-free straight– line program of length O((i + 1)^{5} + L) and depth O(log_{2}(i + 1) + ℓ).

Let μ ∈ Q [X_{1}, …, X_{n−i−1}] be the constant term of the characteristic polynomial of the homothety given by J := J(f_{1}, …, f_{i+1}) modulo I_{i+1}. Since J represents a nonzero divisor modulo I_{i+1} we conclude that μ does not vanish. Furthermore we observe that μ can be evaluated by a division-free straight–line program in Q [X_{1}, …, X_{n−i−1}] of length (iδ_{i}L)^{O(1)} and depth O(log_{2}dδ_{i} + (log_{2}i + ℓ)log_{2}δ_{i}) = O((log_{2}i + ℓ)log_{2}δ_{i}), and so does the product ρ · μ, where ρ = ∏_{n−i+1}^{n} ρ_{j}^{(i)} is defined as in the statement of Theorem 31.

Using a correct test sequence (see [32]) we are able to find in sequential time (iδL)^{O(1)} and parallel time O((log_{2}i + ℓ)log_{2}δ_{i}) a rational point P_{i+1} ∈ ZZ^{n−i−1} of logarithmic height bounded by O((log_{2}i + ℓ)log_{2}δ_{i}) which satisfies (ρ · μ)(P_{i+1}) ≠ 0. Clearly, P_{i+1} is a lifting point for the variety V_{i+1}. In order to obtain a geometric solution of V_{P_{i+1}} with primitive element u_{i+1} induced by the linear form U_{i+1} we have to specialize in the point P_{i+1} the polynomials obtained as output of the second stage (see [25, Section 3]). By this specialization we obtain the binary representation of the coefficients of certain univariate polynomials in U_{i+1} which represent a geometric solution of the fiber V_{P_{i+1}}. Nevertheless it might happen that the height of these coefficients is excessive. In order to control the height of these polynomials we make them primitive. This requires some integer greatest common divisor (gcd) computations which do not modify the asymptotic time complexity of our algorithm. □

4 Lifting Residues and Division modulo a Complete Intersection Ideal

This section is dedicated to the proof of Theorem 21. The outcome is a new trace formula for Gorenstein algebras given by complete intersection ideals. This trace formula does not make reference anymore to a given monomial basis of the algebra. Our trace formula represents an expression which is “easy-to-evaluate”.

4.1 Trace and Duality

Trace formulas appear in several recent papers treating problems in algorithmic elimination theory. Some of these papers use a trace formula in order to compute a quotient appearing as the result of a division of a given polynomial modulo a given complete intersection ideal (see [22,34]). Other papers use trace formulas in order to design algorithms for geometric (or algebraic) solving of zero-dimensional Gorenstein algebras given by complete intersection ideals ([1,2,14]). The paper [49] uses a trace formula to obtain an upper bound for the degrees in the Nullstellensatz.

However, all these applications of trace formulas require the use of some generating family of monomials of bounded degree which generate the given Gorenstein algebra as a vector space over a suitable field. As a consequence, such trace formulas provide just syntactical complexity or degree bounds and in particular no intrinsic upper complexity bound (as e.g. in Theorem 21) can be obtained in this way. In this subsection we introduce an alternative trace formula in order to obtain maximum benefit from the geometrically and algebraically well suited features of Gorenstein algebras. Let us start with a sketch of the trace theory. For proofs we refer to [37], Appendices E and F.

Let R be a ring of polynomials over a given ground field (for our discussion the ground field may be assumed to be Q ). Let K be the quotient field of R and let R[X_{1}, …, X_{n}] be the ring of n-variate polynomials with coefficients in R. Let f_{1}, …, f_{n} be a smooth regular sequence of polynomials in the ring R[X_{1}, …, X_{n}] of degree at most d in the variables X_{1}, …, X_{n} generating a radical ideal denoted by (f_{1}, …, f_{n}).

Consider now the R-algebra B given as the quotient of R[X_{1}, …, X_{n}] by this ideal:

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

We assume that the morphism R → B is an integral ring extension representing a Noether normalization of the variety V (f_{1}, …, f_{n}) defined by the polynomials f_{1}, …, f_{n} in a suitable affine space. Thus, B is a free R-module of rank bounded by the degree of the variety V (f_{1}, …, f_{n}) (this estimation is very coarse but sufficient for our purpose).

Moreover, the R-algebra B is Gorenstein and the following statements are based on this fact.

We consider B^{∗} := Hom_{R}(B, R) as a B-module by the scalar product

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

which associates to any (b, τ) in B × B^{∗} the R-linear map b · τ : B ⟶ R defined by (b · τ)(x) := τ(bx) for any element x of B.

Since the R-algebra B is Gorenstein, its dual B^{∗} is a free B-module of rank one. Any element σ of B^{∗} which generates B^{∗} as B-module is called a trace of B. There are two relevant elements of B^{∗} that we denote by Tr and σ. The first one, Tr, is called the standard trace of B and it is defined in the following way: given b ∈ B, let η_{b} : B ⟶ B the R-linear map defined by multiplying by b any given element of B. The image Tr(b) under the map Tr is defined as the ordinary trace of the endomorphism η_{b} of B (note that this definition makes sense since B is a free R-module). In order to introduce σ (which will be a trace of B in the above sense), we need some additional notations. For any element g ∈ R[X_{1}, …, X_{n}] we denote by ḡ its image in B, i.e. the residue class of g modulo the ideal (f_{1}, …, f_{n}). Let Y_{1}, …, Y_{n} be new variables and let Y := (Y_{1}, …, Y_{n}). Let 1 ≤ j ≤ n and let f_{j}^{Y} := f_{j}(Y_{1}, …, Y_{n}) be the polynomial of R[Y_{1}, …, Y_{n}] obtained by substituting in f_{j} the variables X_{1}, …, X_{n} by Y_{1}, …, Y_{n}. Let us consider the polynomial

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

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

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

with the a_{m} being elements of R[X_{1}, …, X_{n}] and the b_{m} elements of R[Y_{1}, …, Y_{n}].

(Observe that it will not be necessary to find the polynomials a_{m} and b_{m} alegbraically, we need just their existence for our argumentation.) The polynomial Δ is called a pseudo-jacobian determinant of the regular sequence (f_{1}, …, f_{n}). Observe that the polynomials a_{m} and b_{m} can (and will) be chosen to have degrees bounded by n(d − 1) in the variables X_{1}, …, X_{n} and Y_{1}, …, Y_{n} respectively. Let c_{m} ∈ R[X_{1}, …, X_{n}] be the polynomial we obtain by substituting in b_{m} the variables Y_{1}, …, Y_{n} by X_{1}, …, X_{n}. For J̄ the class of the Jacobian determinant J(f_{1}, …, f_{n}) in B we have the identity

J̄ = ∑_{m} ā_{m} · c̄_{m}.

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

¯1 = ∑_{m} σ(ā_{m}) · c̄_{m}.

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

ḡ = ∑_{m} σ(ḡ · ā_{m}) · c̄_{m} (10)

holds true in B. Let us observe that the polynomial ∑_{m} σ(ḡ · ā_{m}) · c_{m} ∈ R[X_{1}, …, X_{n}] underlying the identity (10) is of degree at most n(d − 1) in the variables X_{1}, …, X_{n}.

The main use of this trace formula consists in solving the following problem:

Problem 34 (Lifting of a residual class) Given  a  polynomial

g ∈ R[X_{1}, …, X_{n}] of arbitrary degree in X_{1}, …, X_{n}, find a polynomial g_{1} ∈ R[X_{1}, …, X_{n}] of degree at most n(d−1) in the variables X_{1}, …, X_{n} such that ḡ_{1} = ḡ holds in B.

As we have seen before, the trace formula (10) solves Problem 34 since it allows us to choose for g_{1} the polynomial

g_{1} := ∑_{m} σ(ḡ · ā_{m}) · c_{m}. (11)

However, defining the polynomial g_{1} by the formula (11) inhibits us from taking advantage of any special “semantical” features of the R-algebra B: one “a priori” needs all monomials of degree at most n(d − 1) for the description of the polynomials c_{m} (and a_{m}). Therefore, we replace the trace formula (10) by the following alternative one:

Proposition 35 (Trace Formula) With the same notations as before, let us consider the free R[X_{1}, …, X_{n}]-module B[X_{1}, …, X_{n}] given by extending scalars of B (this means we consider the tensor product B[X_{1}, …, X_{n}] := B⊗_{R} R[X_{1}, …, X_{n}]) and let us also consider the polynomial Δ_{1} ∈ R[X_{1}, …, X_{n}] given by:

Δ_{1} := ∑_{m} ā_{m} · c_{m} ∈ B[X_{1}, …, X_{n}].

Then for any g ∈ R[X_{1}, …, X_{n}] the following identity holds true in R[X_{1}, …, X_{n}]:

∑_{m} σ(ḡ · ā_{m}) · c_{m} = T̃r(J̄^{−1}ḡ · Δ_{1}).

(Here T̃r := Tr ⊗ Id_{R[X_{1},...,X_{n}]} : B[X_{1}, …, X_{n}] ⟶ R[X_{1}, …, X_{n}] is the standard trace obtained from the standard trace Tr : B ⟶ R by extending scalars).

PROOF. Let Tr : B ⟶ R be the standard trace of the free R-module B. Let us recall from [37, Appendix F] that for any g ∈ R[X_{1}, …, X_{n}] the identity

Tr(J̄^{−1}ḡ) = σ(ḡ)

holds. From the R[Y_{1}, …, Y_{n}]-linearity of the map T̃r : B[Y_{1}, …, Y_{n}] ⟶ R[Y_{1}, …, Y_{n}] we deduce that any g ∈ R[X_{1}, …, X_{n}] satisfies the identities

T̃r(J̄^{−1}ḡΔ_{1}(Y_{1}, …, Y_{n})) = ∑_{m} T̃r(J̄^{−1}ḡā_{m} · b_{m}) = ∑_{m} T̃r(J̄^{−1}ḡā_{m}) · b_{m}.

In other words we have in R[Y_{1}, …, Y_{n}]

T̃r(J̄^{−1}ḡΔ_{1}(Y_{1}, …, Y_{n})) = ∑_{m} σ(ḡ · ā_{m}) · b_{m}

for any g ∈ R[X_{1}, …, X_{n}]. Replacing in this identity the variables Y_{1}, …, Y_{n} by X_{1}, …, X_{n} we obtain the desired formula

T̃r(J̄^{−1}ḡΔ_{1}) = ∑_{m} σ(ḡ · a_{m}) · c_{m} . □

One sees easily that for any h ∈ R[X_{1}, …, X_{n}, Y_{1}, …, Y_{n}], T̃r(h̄) is simply the standard trace of the image h̄ of h in the R[Y_{1}, …, Y_{n}]-module B[Y_{1}, …, Y_{n}]. This observation together with Proposition 35 represents our basic tool for the evaluation of formula (11) and hence for the solution of Problem 34. This is the content of the following considerations.

Let us consider the K -algebra B′ = K ⊗_{R} B obtained by localizing B in the non-zero elements of R. Fix a basis of the finite dimensional K -vectorspace B′. Let M_{X_{1}}, …, M_{X_{n}} be the matrices of the homotheties η_{X_{i}} : B′ ⟶ B′ with respect to the given basis of B′ and let Tr denote the function which associates to a given matrix its usual trace. With these conventions let g_{1} be defined as

g_{1} := Tr(J(f_{1}, …, f_{n})(M_{X_{1}}, …, M_{X_{n}})^{−1} · g(M_{X_{1}}, …, M_{X_{n}})
·Δ(M_{X_{1}}, …, M_{X_{n}}, X_{1}, …, X_{n})).  (12)

One easily verifies that g_{1} belongs to R[X_{1}, …, X_{n}] and that ḡ_{1} = ḡ holds in B.

4.2 A Division Step

The lifting process presented in the last subsection is now applied to compute the quotient of two polynomials modulo a reduced complete intersection ideal. More precisely, let us consider a polynomial f ∈ R[X_{1}, …, X_{n}] which is not a zero-divisor in B and another polynomial g ∈ R[X_{1}, …, X_{n}] such that the residue class f̄divides the residue class ḡ in B. The following proposition shows how we can compute a lifting quotient q ∈ R[X_{1}, …, X_{n}] for the division of ḡ by f̄ in B.

Proposition 36 (Division Step) Let notations and assumptions be the same as in the previous subsection and let D be the rank of B as free R-module. Let be given the following items as input:

– a straight–line program Γ′ of size L and depth ℓ representing the polynomials f, g and f_{1}, …, f_{n}.

– the matrices M_{X_{1}}, …, M_{X_{n}} describing the multiplication tensor of B with respect to the given basis of B′ = K ⊗_{R} B.

Suppose that f̄ is a non-zero divisor of B̄ and that f̄ divides ḡ in B. Then there exists a division-free straight–line program Γ in K[X_{1}, …, X_{n}] of size L(ndD)^{O(1)} and non-scalar depth O(ℓ + log_{2}D + log_{2}n) which computes from the entries of the matrices M_{X_{1}}, …, M_{X_{n}} and the parameters of Γ′ a non-zero element θ of R, and a polynomial q of R[X_{1}, …, X_{n}] such that θ divides q in R[X_{1}, …, X_{n}] and such that q̄f̄ = θ̄ḡ holds in B.

PROOF. In order to prove this result, let us observe that any basis of B as free R-module induces a basis of B[Y_{1}, …, Y_{n}] as free R[Y_{1}, …, Y_{n}]-module. Moreover if M_{X_{i}} is the matrix of the multiplication by X̄_{i} in B with respect to a given basis, M_{X_{i}} represents as well the multiplication by X̄_{i} in B[Y_{1}, …, Y_{n}] with respect to the same basis. Next, since the polynomials f and J(f_{1}, …, f_{n}) are not zero-divisors modulo (f_{1}, …, f_{n}), the following matrices are non-singular:

F_{1} := f(M_{X_{1}}, …, M_{X_{n}}),

J_{1} := det(\frac{∂f_{i}}{∂X_{j}})_{1≤i,j≤n}(M_{X_{1}}, …, M_{X_{n}}).

Finally, let us denote by G_{1} and Δ_{1} the following two matrices:

G_{1} := g(M_{X_{1}}, …, M_{X_{n}}),

and

Δ_{1} := Δ(M_{X_{1}}, …, M_{X_{n}}, Y_{1}, …, Y_{n}),

where Δ is the pseudojacobian determinant of f_{1}, …, f_{n}. Let us remark that the matrices F_{1}, J_{1} and G_{1} have entries in K while Δ_{1} has entries in K [Y_{1}, …, Y_{n}]. From formula (12) of the previous subsection we deduce that q_{1} := Tr(J_{1}^{−1} · F_{1}^{−1} · G_{1} · Δ_{1}(X_{1}, …, X_{n})) is a polynomial of R[X_{1}, …, X_{n}] which satisfies in B the identity q̄_{1}f̄ = ḡ (by Tr we denote here the ususal trace of matrices).

Finally, let us transpose the adjoint matrices of F_{1} and J_{1}:

F_{2} := ^{t}Adj(F_{1}), and J_{2} := ^{t}Adj(J_{1}).

The quotient q ∈ R[X_{1}, …, X_{n}] and the non-zero constant θ ∈ R we are looking for are given as follows:

– q := Tr(F_{2} · J_{2} · G_{1} · Δ_{1}(X_{1}, …, X_{n}))

– θ := det(F_{2}) · det(J_{2})

Clearly, the polynomial q_{1} is the quotient of \frac{q}{θ}, while q̄f̄ = θ̄ḡ holds in B. Moreover q can be computed by a division-free straight–line program Γ in K[X_{1}, …, X_{n}] from the entries of M_{X_{1}}, …, M_{X_{n}} and the parameters of Γ′ (note that for the computation of q_{1} we need divisions). The complexity bounds in the statement of Proposition 36 follow by reconstruction of the programs evaluating f, g, J(f_{1}, …, f_{n}), Δ and the determinants involved (cf. Subsection 3.1 above).

Proof of Theorem 21

In order to prove Theorem 21 we follow the algorithm underlying the proof of Proposition 36. We just have to add just some comments concerning the matrices M_{X_{1}}, …, M_{X_{n}}. Let us consider a linear form λ_{1}X_{1} + ⋯ + λ_{n}X_{n} (with λ_{i} ∈ ZZ) inducing a primitive element u of the zero-dimensional Q - algebra Q [X_{1}, …, X_{n}]/(f_{1}, …, f_{n}). In this case R will be the field Q . Let q_{u} ∈ ZZ[T] be the minimal polynomial of u and ρ_{1}X_{1}−v_{1}(T), …, ρ_{n}X_{n}−v_{n}(T) the parametrizations of the variety with respect to this primitive element. Let α be the leading coefficient of q_{u} and ρ = ∏_{i=1}^{n} ρ_{i} a discriminant. Then the companion matrix of q_{u} has the form

α^{−1}M,

where M is a matrix with integer entries. Now, the matrices describing the multiplication tensor of Q [X_{1}, …, X_{n}]/(f_{1}, …, f_{n}) can be written as

M_{X_{i}} = ρ_{i}^{−1} · v_{i}(α^{−1}M)

for 1 ≤ i ≤ n. Taking g = 1 and f = f_{n+1} in Proposition 36 we obtain θ ∈ Q , θ ≠ 0 and q ∈ Q [X_{1}, …, X_{n}] such that

θ · 1 − q · f_{n+1} ∈ (f_{1}, …, f_{n})

holds. Finally, multiplying by appropriate powers of α and ρ we obtain a non-zero integer a and a polynomial g_{n+1} of the form

a := α^{N}ρ^{M} · θ ∈ ZZ g_{n+1} := α^{N}ρ^{M}q ∈ ZZ[X_{1}, …, X_{n}],

such that a−g_{n+1}f_{n+1} ∈ (f_{1}, …, f_{n}) holds. The bounds of the Theorem 21 are then obtained from the bounds of Proposition 36. The bounds for the height of the parameters are obtained choosing an appropriate primitive element u such that q_{u} and the parametrizations have height equal to the minimal height of the diophantine variety V := V (f_{1}, …, f_{n}). □

Acknowledgement

L. M. Pardo wants to thank the École Polytechnique X for the invitation and hospitality during his stay in the Fall of 1995, when this paper was conceived.

References

[1] M. E. Alonso, E. Becker, M.-F. Roy, T. Wörmann: Zeroes, multiplicities and idempotents for zerodimensional systems, in: L. González-Vega and T. Recio, Eds., Proc. Algorithms in Algebraic Geometry and Applications, MEGA’94 Santander, 1994, Progress in Mathematics Vol. 142 (Birkhäuser, Basel, 1996) 1-15.

[2] E. Becker, J.P. Cardinal, M.-F. Roy, Z. Szafraniec: Multivariate Bezoutians, Kronecker symbol and Eisenbud–Levine formula, in: L. González-Vega and T. Recio, Eds., Proc. Algorithms in Algebraic Geometry and Applications, MEGA’94 Santander, 1994, Progress in Mathematics Vol. 142 (Birkhäuser, Basel, 1996) 79–104.

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

[4] C. Berenstein, A. Yger: Une formule de Jacobi et ses conséquences, Ann Sci.

E.N.S., 4ième série, 24 (1991) 363-377.

[5] C. Berenstein, A. Yger: Green currents and analytic continuation, preprint,

Univ. of Maryland, (1995)

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

[7] A. Borodin, J. von zur Gathen, J. Hopcroft: Fast parallel matrix and GCD computations, Inf. Control 52 (1982) 241-256

[8] J.-B. Bost, H. Gillet, C. Soulé: Un analogue arithmétique du théorème de

Bézout, C.R. Acad. Sci. Paris, Série I, Math. 312, (1991) 845-848.

[9] J.-B. Bost, H. Gillet, C. Soulé: Heights of projective varieties and positive Green

forms, Manuscript IHES, (1993).

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

[11] J. F. Canny, I.Z. Emiris: Efficient Incremental Algorithms for the Sparse Resultant and the Mixed Volume, Preprint (1995)

[12] L. Caniglia, A. Galligo, J. Heintz: Borne simplement exponentielle pour les degrés dans le théorème des zéros sur un corps de caractéristique quelconque,

C.R. Acad. Sci. Paris, Série I, Math. 307 (1988) 255-258.

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

[14] J.P. Cardinal: Dualité et algorithmes itératives pour la solution des systèmes polynomiaux, Thèse, U. de Rennes I (1993).

[15] A.L. Chistov, D.J. Grigor’ev: Subexponential time solving systems of algebraic

equations, LOMI Preprints E-9-83, E-10-83, Leningrad (1983)

[16] L. Csanky: Fast parallel matrix inversion algorithms, SIAM J. Comp. 5 (1976) 618-623

[17] J.-P. Dedieu, Estimations for the Separation Number of a Polynomial System,

Preprint, Univ. Paul Sabatier, Toulouse (1995)

[18] J.-P. Dedieu, Approximate Solutions of Numerical Problems, Condition Number Analysis and Condition Number Theorems, Preprint, Univ. Paul Sabatier,

Toulouse (1995)

[19] M. Elkadi. “Bornes pour le degré et les hauteurs dans le problème de division”,

in Michigan Math. J. 40 (1993) 609-618

[20] I. Z. Emiris: On the Complexity of Sparse Elimination, ReportNo. UCB/CSD-

94/840, Univ. of California (1994)

[21] G. Faltings, Diophantine approximation on abelian varieties, Ann. of Math., 133 (1991), 549-576

[22] N. Fitchas, M. Giusti, F. Smietanski: Sur la complexité du théorème des zéros,

in Approximation and Optimization in the Caribbean II, Proceedings of the Second International Conference on Approximation and Optimization,

La Habana, 1993, M. Florenzano et al., eds., Approximation and Optimization, Peter Lang Verlag, Frankfurt (1995) 274–329.

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

[24] M. Giusti, J. Heintz: La détermination des points isolés et de la dimension d’une variété algébrique peut se faire en temps polynomial, In Computational

Algebraic Geometry and Commutative Algebra, Proceedings of the Cortona

Conference on Computational Algebraic Geometry and Commutative Algebra, D. Eisenbud and L. Robbiano, eds., Symposia Matematica, vol. XXXIV, Istituto Nazionale di Alta Matematica, Cambridge University Press (1993).

[25] M. Giusti, J. Heintz, J.E. Morais, J. Morgenstern, L.M. Pardo: Straight–line Programs in Geometric Elimination Theory, to appear in Journal of Pure and

Applied Algebra

[26] M. Giusti, J. Heintz, J.E. Morais, L.M. Pardo: When polynomial equation

systems can be “solved” fast? in Proc. 11th International Symposium Applied Algebra, Algebraic Algorithms and Error–Correcting Codes, AAECC–11,

Paris 1995, G. Cohen, M.Giusti and T. Mora, eds., Springer LNCS 948 (1995) 205–231.

[27] M. Giusti, J. Heintz, J. Sabia: On the efficiency of effective Nullstellensätze,

Computational Complexity 3 (1993) 56–95.

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

[29] J. Heintz, T. Krick, A. Slissenko, P. Solernó: “Searching for a shortest path surrounding semi–algebraic obstacles in the plane” (in russian): Teorija složnosti vyčislenij, 5, Zapiski naučnyh seminarov LOMI (Leningrad branch of the Mathematical Institute Steklov), Nauka, Leningrad, vol. 192, (1991), 163-173

[30] J. Heintz, T. Krick, A. Slissenko, P. Solernó. “Une borne inférieure pour la construction des chemins polygonaux dans IR^{n}, Preprint, Univ. de Limoges, (1992)

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

[32] J. Heintz, C.P. Schnorr: Testing polynomials which are easy to compute,

Proc. 12th Ann. ACM Symp. on Computing (1980) 262–268; also in Logic and Algorithmic. An International Symposium held in Honour of Ernst

Specker, Monographie No. 30 de l’Enseignement de Mathématiques, Genève (1982) 237–254.

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

[34] T. Krick, L.M. Pardo: A Computational Method for Diophantine Approximation, in: L. González-Vega and T. Recio, Eds., Proc. Algorithms in Algebraic Geometry and Applications, MEGA’94 Santander, 1994, Progress in Mathematics Vol. 142 (Birkhäuser, Basel, 1996) 193-254.

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

[36] T. Krick, J. Sabia, P. Solernó: On Intrinsic Bounds in the Nullstellensatz, Appl. Algebra Eng. Commun. Comput. (AAECC J.) 8 (1997) 125-134.

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

[38] B. Iversen: Generic local structure of the morphisms in Commutative

Algebra, Springer LNM 310 (1973)

[39] M. Mignotte: Mathématiques pour le Calcul Formel, Presses Universitaires de France (1989).

[40] J.L. Montaña, J.E. Morais, L.M. Pardo: Lower Bounds for Arithmetic

Networks II: Sum of Betti numbers, Applicable Algebra in Engineering Communications and Computing (AAECC Journal), vol. 7, No. 1 (1996)

41-51.

[41] J.L. Montaña, L.M. Pardo: Lower Bounds for Arithmetic Networks, Applicable

Algebra in Engineering Communications and Computing (AAECC

Journal), vol. 4 (1993), 1–24.

[42] Yu. V. Nesterenko: Estimates for the order of zero o functions of a certain class and applications in the theory of transcendental numbers Math. USSR Izvestija, vol.11, No. 2 (1977) 239–270.

[43] Yu. V. Nesterenko: On a measure of the algebraic independence of the values of certain functions, Math. USSR Sbornik 56 (1987) 545– 567.

[44] L.M. Pardo: How lower and upper complexity bounds meet in elimination

theory, in Proc. 11th International Symposium Applied Algebra, Algebraic Algorithms and Error–Correcting Codes, AAECC–11, Paris 1995, G. Cohen,

M.Giusti and T. Mora, eds., Springer LNCS 948 (1995) 33–69.

[45] P. Philippon: Critères pour l’indépendence algébrique, Pub. Math. de l’IHFS 64 (1987) 5–52.

[46] P. Philippon: Sur des hauteurs alternatives, I, Math. Ann. 289 (1991) 255–283.

[47] P. Philippon: Sur des hauteurs alternatives, II, Ann. Inst. Fourier, Grenoble, vol. 44 No. 2 (1994) 1043–1065.

[48] P. Philippon: Sur des hauteurs alternatives, III, J. Math. Pures Appl. 74 (1995) 345-365.

[49] J. Sabia, P. Solernó: Bounds for traces in complete intersections and degrees

in the Nullstellensatz, Applicable Algebra in Engineering Communications and Computing (AAECC Journal), vol. 6 (1996) 353–376.

[50] T. Schneider, Einführung in die Theorie der transzendenten Funktionen,

Springer Verlag, Berlin (1957)

[51] M. Shub, S. Smale: Complexity of Bezout’s theorem I: Geometric aspects, J.

Amer. Math. Soc. 6 (1993), 459-501

[52] M. Shub, S. Smale: Complexity of Bezout’s theorem II: Volumes and

probabilities, in Proceedings Effective Methods in Algebraic Geometry,

MEGA’92 Nice, 1992, F. Eyssette and A. Galligo, eds. Progress in Mathematics, Vol. 109, Birkhäuser, Basel, (1993) 267-285

[53] M. Shub, S. Smale: Complexity of Bezout’s theorem III: Condition number and packing, J. of Complexity 9 (1993) 4-14

[54] M. Shub, S. Smale: Complexity of Bezout’s theorem IV: Probability of Success, Extensions, SIAM J. Numer. Anal. to appear

[55] M. Shub, S. Smale: Complexity of Bezout’s theorem V: Polynomial time,

Theoretical Comp. Sci. 133 (1994)

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

[57] C. Soulé: Personal communication (1994)

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