Kronecker’s and Newton’s approaches to solving : A first comparison^{1}

D. Castro^{2}, K. Hägele^{3}, J. E. Morais^{4}, L. M. Pardo^{2}

December 16, 1999

Abstract

These pages are a first attempt to compare the efficiency of symbolic and numerical analysis procedures that solve systems of multivariate polynomial equations. In particular, we compare Kronecker’s solution (from the symbolic approach) with approximate zero theory (introduced by S. Smale as a foundation of numerical analysis). For this purpose we show upper and lower bounds of the bit length of approximate zeros. We also introduce efficient procedures that transform local Kronecker solutions into approximate zeros and conversely. As an application of our study we exhibit an efficient procedure to compute splitting field and Lagrange resolvent of univariate polynomial equations. We remark that this procedure is obtained by a convenient combination of both approaches (numeric and symbolic) to multivariate polynomial solving.

Keywords. Kronecker’s solution, Newton operator, approximate zero, straight–line programs, height of diophantine varieties, degree of algebraic varieties, Turing machine complexity.

1: Research was partially supported by the Spanish grant : PB96–0671–C02–02 and the project “Complejidad y Estructuras de Datos en Cálculo Simbólico”, Gobierno de Navarra, Spain, 1999.

2: Departamento de Matemáticas, Estadística y Computación.

Facultad de Ciencias, Universidad de Cantabria, E-39071 Santander, Spain 3: Department of Computer Science, Trinity College, University of Dublin, Ireland 4: Departamento de Matemática e Informática, Campus de Arrosadía.

Universidad Pública de Navarra, E-31006 Pamplona, Spain

Contents

1 Introduction and statement of main results 3

2 Basic notions and Statements of the main Results 5 2.1 Newton’s approach to solving . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 2.2 Kronecker’s approach to solving . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 2.3 Application : Computation of splitting field and Lagrange resolvent . . . . . . . . 15

3 Fundamental tools 16

3.1 Heights and norms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 3.1.1 Multivariate polynomials . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 3.1.2 Absolute values over number fields . . . . . . . . . . . . . . . . . . . . . . . 17 3.1.3 Height of affine points . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 3.1.4 Norms of affine points and linear operators . . . . . . . . . . . . . . . . . . 21

4 Newton’s approach to solving : On the bit length of approximate zeros 23 4.1 Eckardt & Young Theorem. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 4.2 Approximate zero theory : Lower bounds for the bit length of approximate zeros. . 25

4.2.1 Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 4.3 Approximate zero theory : Upper bounds for the bit length of approximate zeros . 34

5 Kronecker’s approach to solving 38 5.1 An improvement of the Witness Theorem . . . . . . . . . . . . . . . . . . . . . . . 39 5.2 Factoring polynomials given by straight–line programs. . . . . . . . . . . . . . . . . 44 5.3 Computing binary encodings of suitable approximations . . . . . . . . . . . . . . . 48 5.4 From Kronecker’s to Newton’s solution . . . . . . . . . . . . . . . . . . . . . . . . . 50 5.5 From Newton’s to Kronecker’s solution . . . . . . . . . . . . . . . . . . . . . . . . . 55

6 Application : Splitting field and Lagrange resolvent 58

1 Introduction and statement of main results

Let K be a number field containing the field of Gaussian rationals ℚ[i] ⊆ K. In these pages we are mainly interested in the computation of K−rational points of zero–dimensional algebraic varieties given by systems of multivariate polynomial equations. Namely, let f_{1}, …, f_{s} ∈ ℤ[X_{1}, …, X_{n}] be a sequence of multivariate polynomials with integer coefficients. Let V (f_{1}, …, f_{s}) ⊆ ℂ^{n} be the complex algebraic variety of their common zeros, i.e.

V (f_{1}, …, f_{s}) := {x ∈ ℂ^{n} : f_{i}(x) = 0, 1 ≤ i ≤ s}.

For sake of simplicity, let us assume that V (f_{1}, …, f_{s}) is a finite set (i.e. a zero–dimensional algebraic variety). The set of K−rational points in V (f_{1}, …, f_{s}) is the set of common zeros of the system f_{1}, …, f_{s} whose coordinates lie in K^{n}, namely

V_{K}(f_{1}, …, f_{s}) := {x ∈ K^{n} : f_{1}(x) = ⋯ = f_{s}(x) = 0}.

The goal of these pages will be to discuss several aspects of procedures performing the following task : Assume that the field K is fixed. Given the sequence f_{1}, …, f_{s}, compute all K−rational points in V_{K}(f_{1}, …, f_{s}) (or eventually all K−rational points in V_{K}(f_{1}, …, f_{s}) of bounded height). Note that the assumption on the field K is not very restrictive : For every zero ζ ∈ V (f_{1}, …, f_{s}), there exists a minimal number field ℚ(ζ) containing all the coordinates of ζ. This field is usually called the residue class fields of the proyective point

(1 : ζ_{1}, …, ζ_{n}) ∈ ℙ_{n}(K),

where ζ := (ζ_{1}, …, ζ_{n}) (cf. [Lan97]). We also denote by ht(ζ) the logarithmic Weil’s height of the proyective point (1 : ζ_{1}, …, ζ_{n}) ∈ ℙ_{n}(K) (cf. [Lan83]). The degree of the field extension ℚ(ζ) over ℚ can also be denoted by deg(ζ). In the sequel, the degree [K : ℚ] may be replaced by deg(ζ), and the results will equally hold. For our study, we consider a precomputation task which prepares the input F := (f_{1}, …, f_{s}), before we study the desired K−rational points. Procedures performing this precomputation task are usually called multivariate polynomial system solvers applied to the input F. The output of such polynomial system solvers is called the solution of the system F. Observe that all usual notions of solution of F will yield a description of the variety V (f_{1}, …, f_{s}) (cf. also [CGH^{+}99]). Here, we consider two (conceptually different) notions which define what a solution of the system F should be : coming from different fields, the notions are related to a symbolic/geometric and a numerical analysis/diophantine approximation context : Kronecker’s geometric solution and Newton’s approximate zero solution. Thus, our study includes a comparative study of both approaches with regard to the basic problem described above. It must be said that our study is not intended to be either complete or definitive. It just tries to point out some similarities and differences between both approaches to solving that yield some statements and some open questions of interest. In this sense, we have tried to write down as many comments as possible to clarify (as much as we can) the relations between both approaches to solving. Moreover, we have tried to put both approaches under the same hypotheses. This means that our input system of multivariate polynomials F := (f_{1}, …, f_{s}) is well–suited for the application of either Kronecker’s or Newton’s approach to solving. Therefore we will assume the following hypotheses :

i) The number of equations equals the number of variables (i.e. s = n above)

ii) The variety V (f_{1}, …, f_{n}) is zero–dimensional and contains exactly D points, i.e. the degree of V (f_{1}, …, f_{n}) (in the sense of [Hei83]) is exactly D. iii) The K−rational points in V_{K}(f_{1}, …, f_{n}) are smooth with respect to the system F :=

(f_{1}, …, f_{n}), i.e. for every ζ ∈ V_{K}(f_{1}, …, f_{n}), the jacobian matrix

DF (ζ) := (\frac{∂f_{i}}{∂X_{j}} (ζ))_{1≤i,j≤n}

is a non–singular matrix (i.e. DF (ζ) ∈ GL(n, K)).

iv) The sequence f_{1}, …, f_{n} ∈ ℤ[X_{1}, …, f_{n}] is a reduced regular sequence, i.e. for every i, 1 ≤ i ≤ n − 1, the ideals (f_{1}, …, f_{i}) are radical ideals of codimension i in ℚ[X_{1}, …, X_{n}].

v) The degrees of the input polynomials satisfy deg(f_{i}) ≤ 2, for 1 ≤ i ≤ n.

It must be said that constraints i) and iv) are not relevant for Kronecker’s approach to solving. Applying the iterative version of Bertini’s Theorem (as described in [Mor97, Häg98, HMPS] or [GS99]) we can easily reduce the over–determined input system to a system satisfying properties i) and iv). Anyway, we prefer to keep these hypotheses to simplify exposition, notations, and – hopefully – reading. Constraint v) is included just to simplify the exposition of the main statements below. The body of the paper contains the corresponding estimates for arbitrary upper degree bound of the input polynomials. The main results of this paper can be resumed in the following two Main Theorems. Let us recall that a sufficient condition for an approximate zero of an input system F := (f_{1}, …, f_{n}) is usually given either as the γ–Theorem (cf. [Sma81, Kim88, BCSS98b]) or as the α–Theorem (cf. [Sma81, BCSS98b]). The first Main Theorem a lower time bound for the computation of a single approximate zero satisfying either γ or α–Theorem.

Main Theorem 1 The computation of a single approximate zero in ℚ[i]^{n} satisfying either the γ– or the α–Theorem for a given input system F := (f_{1}, …, f_{n}) ∈ (ℤ[X_{1}, …, X_{n}])^{n} requires at least exponential running time when using either binary, floating point or continous fraction encoding for the points in ℚ[i]^{n}. In other words, computing approximate zeros using any of these encodings is in

EXT IME \ ∪_{s∈ω(2^{n})}DT IMES(s),

where the “small ω” notation is the standard one in Calculus.

The first statement follows since we are able to exhibit examples of input systems F := (f_{1}, …, f_{n}) and zeros ζ ∈ V (f_{1}, …, f_{n}) such that any approximate zero ζ has at least exponential bit length in any of these three encodings. In fact, we show three different techniques to show lower bounds for the bit length of approximate zeros. These three techniques are stated in detail in Theorem 6 and Proposition 7 below. The proofs of these statements are shown in Section 4 below. One of these techniques is based on the use of Eckardt & Young’s Theorem both in the archimedian and non–archimedian case. Here we also introduce a proof for the Eckardt & Young Theorem in the non–archimedian case (see Theorem 5 below) Concrete examples are described in Section 4 below. In spite of this lower bound, we also give an existential statement containing an upper bound for the bit length of approximate zeros which is linear in deg(ζ) · ht(ζ) (cf. Theorem 8 below). The second main result of these pages shows that approximate zeros are a compressed encoding of the residue class fields of the actual zero. Namely, we show the following Theorem.

Main Theorem 2 Approximate zeros and Kronecker’s description of the residue class field of an actual zero are computationally equivalent. More precisely, we show : i) There exists a bounded error probability Turing machine M_{1} that performs the following task :

Given a system of multivariate polynomial equations F := (f_{1}, …, f_{n}) satisfying hypotheses i) to v) above, and given an approximate zero z ∈ ℚ[i]^{n} of the system F with associated zero ζ ∈ V (f_{1}, …, f_{n}), the machine M_{1} outputs a Kronecker’s description of the residue class fields of the point ζ ∈ K^{n}. The running time of the machine M_{1} is polynomial in the following quantities :

n h ht(z)ht(ζ) deg(ζ),

where n is the number of variables, h is the logarithm of the maximum of the absolute values of the coefficients of the polynomial in the list F, ht(z) is the logarithmic Weil height of the approximate zero, and ht(ζ) and deg(ζ) are as above.

ii) There exists a bounded error probability polynomial time Turing machine M_{2} that performs the following task :

Given a system of multivariate polynomial equations F := (f_{1}, …, f_{n}) satisfying hypotheses i) to v) above, and given a Kronecker’s description of the residue class field K(ζ) of an actual zero ζ ∈ V (f_{1}, …, f_{n}), the machine M_{2} outputs for every conjugate ζ′ ∈ ℂ^{n} of ζ an approximate zero z′ ∈ ℚ[i]^{n} for the system F with associated zero ζ′.

The running time of machine M_{2} is polynomially bounded in terms of the following quantities

n ht(ζ) deg(ζ).

This second main statement is shown as Theorems 15 and 16 below. In fact, Theorem 16 shows how to compute approximate zeros for actual zeros of bounded height using Kronecker’s approach to solving (as in [GHMP95, Par95, GHH^{+}97, Mor97, GHM^{+}98]). In terms of worst–case complexity estimates, Corollary 17 shows a simply exponential time procedure to compute approximate zeros in either binary, continuous fraction or floating point encoding. In fact, the lower bounds in Main Theorem 1 show that the procedure described in Theorem 16 is optimal in terms of worst–case complexity estimates (cf. Corollary 17). We apply this comparison to exhibit a procedure that computes Lagrange resolvents and splitting fields of univariate polynomials in time which depends polynomially on the output length (i.e. it is essentially optimal). This paper is structured as follows. First of all, in Section 2 below, we introduce the main notions and notations and thus we can give precise statements of the technical results that imply Main Theorems 1 and 2 above. Readers interested only in the main technical results and not interested in proofs may stop their reading at the end of this Section. For all those readers interested in proofs, the rest of the paper is devoted to show the statements described in this Section 2. As we have used different notions coming from different fields and different approaches, and we want to make our pages as readable as possible, we have included a section on fundamental tools, where all notions are introduced and some elementary and technical Lemmata are shown. The well–read reader might want to skip this section and go directly to the body of the paper. Section 4 is devoted to establish the proofs for the results concerning upper and lower bounds for the bit length of approximate zeros satisfying the γ–Theorem. In Section 5, the relation between approximate zeros and Kronecker’s description is studied. Finally, Section 6 gives the proof for our statement about the computation of splitting field and the Lagrange resolvent.

2 Basic notions and Statements of the main Results

In this Section we introduce the essential notions which are going to be used in the rest of the paper. We also state the technical results implying Main Theorem 1 and Theorem 2 above for input systems of polynomial equations satisfying hypotheses i) to iv) above, more general statements are given in the body of the paper. This Section is divided into three Subsections :

i) Newton’s approach to solving.

Here, we show upper and lower bounds for the bit length of approximate zeros.

ii) Kronecker’s approach to solving.

This recalls Kronecker’s approach to solving and shows the main statements which relate Kronecker’s and Newton’s approaches to solving by means of an algorithm based on the L^{3} (or LLL) reduction procedure (as introduced in [LLL82b] and used in [KLL84, Len84]).

iii) Application: Computation of splitting field and Lagrange resolvent.

Finally we exhibit an algorithm that combines both approaches to compute efficiently the splitting field of a univariate polynomial equation as well as the corresponding Lagrange resolvent.

2.1 Newton’s approach to solving

Let M_{K} be a proper class of absolute values on the number field K in the sense of [Lan83]. For every ν ∈ M_{K} we have an absolute value | · |_{ν} : K ⟶ ℝ. The class M_{K} is chosen such that it satisfies Weil’s product formula with respect to well-defined multiplicities. We denote by S ⊆ M_{K} the set of sub–indices ν ∈ M_{K} such that the absolute value | · |_{ν} is archimedean and, consequently, by M_{K} \ S the class of sub–indices ν ∈ M_{K} such that | · |_{ν} is non–archimedean. For every ν ∈ M_{K}, we shall denote by K_{ν} the completion of K with respect to the absolute value | · |_{ν}. We also denote by | · |_{ν} : K_{ν} ⟶ ℝ the corresponding extension of | · |_{ν} to the completion K_{ν}. Let ζ ∈ V_{K}(f_{1}, …, f_{n}) be a smooth K−rational point of the zero–dimensional complex algebraic variety V (f_{1}, …, f_{n}). We are interested in approximating ζ using iterations of the Newton operator. Therefore, we introduce the Newton operator of system F as the following list of rational mappings :

N_{F} (X_{1}, …, X_{n}) := ( X_{1} ; ⋮ ; X_{n} ) − Df(X_{1}, …, X_{n})^{−1} ( f_{1}(X_{1}, …, X_{n}) ; ⋮ ; f_{n}(X_{1}, …, X_{n}) ) .

An approximate zero z in K^{n} for the system F with associated zero ζ ∈ V_{K}(f_{1}, …, f_{n}) with respect to the absolute value | · |_{ν} is a point such that the sequence of iterates of the Newton operator is well–defined and converges quadratically to ζ. Roughly speaking, an approximate zero z ∈ K^{n} with associated zero ζ ∈ K^{n} is a point which lies in the quadratic basin of attraction of the actual zero ζ with respect to the Newton operator N_{F}. Formally, we define approximate zeros as follows :

Definition 3 [Sma81] Let F := (f_{1}, …, f_{n}) be a system of multivariate polynomials with integer coefficients : f_{i} ∈ ℤ[X_{1}, …, X_{n}] for 1 ≤ i ≤ n. Let ν ∈ M_{K} define an absolute value | · |_{ν} : K ⟶ ℝ. Let ζ ∈ V_{K}(f_{1}, …, f_{n}) be a smooth K−rational point (i.e. DF (ζ) ∈ GL(n, K)). Let z := (z_{1}, …, z_{n}) ∈ K^{n} be an affine point. We say that z is an approximate zero of the system F with associated zero ζ ∈ K^{n} with respect to the absolute value |·|_{ν}, if the following properties hold :

• DF (z) ∈ GL(n, K) is a non–singular matrix.

• The following sequence is well–defined :

z_{1} := N_{F} (z) ∈ K^{n}, and z_{k} := N_{F} (z_{k−1}) for k ≥ 2.

• For every k ∈ ℕ, k ≥ 1, the following inequality holds :

∥z_{k} − ζ∥_{ν} ≤ \frac{1}{2^{2^{k−1}}} ∥z − ζ∥_{ν},

where ∥ · ∥_{ν} : K_{ν} ⟶ ℝ is the corresponding norm associated to the absolute value | · |_{ν} (cf. Subsection 3.1.4 below for more details).

From a computational point of view, we want to compute approximate zeros of smooth K−rational points and we want to write them over a finite alphabet. In particular for every smooth K−rational zero ζ ∈ V_{K}(f_{1}, …, f_{n}) and every absolute value ν ∈ M_{K}, we consider a subfield L of K, such that the completion L_{ν} of L with respect to the absolute value | · |_{ν} contains the entries of ζ, namely ζ ∈ L_{ν}^{n}. Thus, we look for approximate zeros z ∈ L^{n} with associated zero ζ ∈ L_{ν}^{n}. Let us observe that if the absolute value | · |_{ν} is archimedean, we may fix L to be L := ℚ[i]. Moreover, we are interested in the heights of approximate zeros z ∈ L^{n} with actual zeros ζ ∈ L_{ν}^{n}. In the case where L = ℚ[i], the height of a point z ∈ ℚ[i]^{n} essentially equals its bit length (i.e. the number of tape cells in a Turing machine required to write down the list of digits describing z). In the sequel, we shall therefore identify the logarithmic height ht(z) and its bit length. A first relevant task consists in stating conditions which are sufficient for verifying the property of being an approximate zero. This is achieved by means of a local condition based on a quantity (called γ), which is essentially yielded by the Lipschitz constant appearing in the inverse mapping Theorem (cf. [Dem89], Ch. 1, for instance). These ideas were introduced by S. Smale in the early eighties (cf. [Sma81]) and deeply developped in the series of papers written with M. Shub (c.f. [SS85, SS86, SS93a, SS93b, SS93c, SS94a, SS94b], see also [Kim88]). With the same notations as above, let ν ∈ M_{K} be an absolute value on the field K. We define the quantity γ :

γ_{ν}(F, ζ) := sup_{k≥2} ∥\frac{(DF (ζ))^{−1}(D^{(k)}F (ζ))}{k!}∥ν^{\frac{1}{k−1}} ,

where the norm is considered as the norm with respect to the absolute value | · |_{ν} of the multilinear operator

DF (ζ)^{−1}D^{(k)}F (ζ) : (K_{ν}^{n})^{k} ⟶ K_{ν}^{n}.

This quantity yields a locally sufficient condition for having an approximate zero. This statement is known as the γ−Theorem and it holds equally true for archimedean and non–archimedean absolute values.

Theorem 4 (γ−Theorem) With the same notations and assumptions as before, let F := (f_{1}, …, f_{n}) be a sequence of multivariate polynomials with coefficients in K. Let ζ ∈ V_{K}(f_{1}, …, f_{n}) be a smooth K−rational zero (i.e. DF (ζ) ∈ GL(n, K) is a non–singular matrix). Let | · |_{ν} : K ⟶ ℝ_{+} be an absolute value on K. For every z ∈ K^{n} satisfying the inequality :

∥ζ − z∥_{ν}γ_{ν}(F, ζ) ≤ \frac{3 − \sqrt{7}}{2}

holds : z is an approximate zero of the system F with associated zero ζ with respect to the absolute value | · |_{ν}.

The proof of this statement follows step by step the proof of the usual γ−Theorems (cf. the compiled version in [BCSS98b]) so we omit the proof here. To establish upper and lower bounds for the bit length of approximate zeros, we have established several technical statements. One of them is an extension of the well–known Eckardt & Young Theorem [EY36] to the non–archimedean case : Let ν ∈ M_{K} be an absolute value over K and K_{ν} the completion of K with respect to the absolute value | · |_{ν}. Let us denote by Σ_{ν} ⊆ M_{n}(K_{ν}) the variety of singular n × n matrices with entries in K_{ν}. Similarly, let Σ be the subset of Σ_{ν} of all singular n × n matrices with entries in K. Finally, let

d_{ν}^{(F)} : M_{n}(K_{ν}) × M_{n}(K_{ν}) ⟶ ℝ_{+}

be the Frobenius (also called Hilbert–Weil) metric on M_{n}(K_{ν}) with respect to the absolute value | · |_{ν} (cf. Subsection 4.1 below). Then, the following Theorem holds :

Theorem 5 (Eckardt & Young) Let ν ∈ M_{K} be an absolute value. For every non–singular n × n matrix A ∈ GL(n, K), the following equality holds :

d_{ν}^{(F)}(A, Σ) = d_{ν}^{(F)}(A, Σ_{ν}) = inf\{d_{ν}^{(F)}(A, M) : M ∈ Σ\} = \frac{1}{∥A^{−1}∥_{ν}} .

For every multivariate polynomial f ∈ ℤ[X_{1}, …, X_{n}] with integer coefficients, we define its logarithmic height ht(f) as the logarithm of the maximum of the absolute values of its coefficients. This notion introduced, we have the following statement which shows lower bounds for the bit length of approximate zeros.

Theorem 6 (Lower Bounds) Let f_{1}, …, f_{n} ∈ ℤ[X_{1}, …, X_{n}] be a sequence of multivariate polynomials. Let us assume that the following properties hold :

i) max{deg(f_{i}) : 1 ≤ i ≤ n} = 2 ,

ii) ht(f_{i}) ≤ h for 1 ≤ i ≤ n.

Let ζ ∈ V_{K}(f_{1}, …, f_{n}) be a smooth K−rational point of the system F := (f_{1}, …, f_{n}). Let | · |_{ν} : K ⟶ ℝ_{+} be an absolute value defined on K, and let L ⊆ K be a number field such that ζ ∈ L_{ν}^{n}. Then, for every z ∈ L^{n}, z ≠ ζ satisfying :

||z − ζ||_{ν}γ_{ν}(F, ζ) ≤ \frac{3 − \sqrt{7}}{2},

the following inequality holds :

ht(z) ≥ \frac{1}{3[L : ℚ]} (log γ_{ν}(F, ζ) − [L : ℚ] (5 log n + 2h) − 3) .

Using Theorem 5 above, the following inequality also holds :

ht(z) ≥ \frac{1}{3[L : ℚ]} (log d_{ν}^{(F)}(DF (ζ)^{−1}, Σ_{ν}) − [L : ℚ] (7 log n + 3h) − 5) .

Moreover, in the case where L = ℚ[i] is the field of Gaussian rationals, the two previous lower bounds may be rewritten as :

ht(z) ≥ \frac{1}{6} (log γ_{ν}(F, ζ) − (10 log n + 4h + 3)) , and

ht(z) ≥ \frac{1}{6} (log d_{ν}^{(F)}(DF (ζ)^{−1}, Σ_{ν}) − (14 log n + 6h + 5)) .

Let us observe that the “negative terms” in the previous lower bounds are linear in the input length (i.e. the bit length of the input system F := (f_{1}, …, f_{n})), whereas the “positive part” depends semantically on the smooth K−rational solution ζ ∈ V_{K}(f_{1}, …, f_{n}). Last, but not least, we may also show a few lower bounds for the average height of approximate zeros associated to a ℚ−definable irreducible component of the solution variety V (f_{1}, …, f_{n}). To this end, we introduce some additional notations. Let f_{1}, …, f_{n} ∈ ℤ[X_{1}, …, X_{n}] be a sequence of multivariate polynomials satisfying hypotheses i) to v) above. Let ζ ∈ K^{n} be a smooth K−rational zero of the system F := (f_{1}, …, f_{n}). Let V := V (f_{1}, …, f_{n}) ⊂ ℂ^{n} be the algebraic variety given as the common zeros of the polynomials f_{1}, …, f_{n}. Let V_{ζ} ⊆ V be the ℚ−definable irreducible component of V that contains ζ . Let us observe that ℚ[V_{ζ}] is a finite extension of ℚ. In fact, ℚ[V_{ζ}] = ℚ(ζ) is the residue class field of the actual zero ζ, and

D := deg(ζ) = deg(V_{ζ}).

Let us assume V_{ζ} := {ζ_{1}, …, ζ_{D}}, the set of all conjugates ζ′ ∈ ℂ^{n} of the affine point ζ ∈ K^{n}. Let ∥ · ∥ : K^{n} ⟶ ℝ be the standard hermitian norm induced in K^{n} by the inclusion i : K ↪ ℂ. A sequence of points z := (z_{1}, …, z_{D}) ∈ ℚ[i]^{nD} is said to be an approximate zero of the system F with associated variety V_{ζ} that satisfies the γ−Theorem, if for every i, 1 ≤ i ≤ D, the following holds :

∥z_{i} − ζ_{i}∥ ≤ \frac{3 − \sqrt{7}}{2γ(F, ζ_{i})},

where γ(F, ζ_{i}) is the quantity associated with the hermitian norm ∥ · ∥. For every given approximate zero z := (z_{1}, …, z_{D}) ∈ ℚ[i]^{nD} of the system F with associated variety V_{ζ}, the average height (also the average bit length) of z is defined in the following terms

ht_{av}(z) := \frac{1}{D} ∑_{i=1}^{D} ht(z_{i}).

Finally, let us denote by ℤ_{K} ⊂ K the ring of algebraic integers of the number field K. Then, we have the following lower bound for the average bit length of approximate zeros with associated variety V_{ζ} :

Proposition 7 With the previous notations, let ζ ∈ V_{K}(f_{1}, …, f_{n}) be a smooth K−rational with entries in ℤ_{K}, i.e. ζ ∈ ℤ_{K}^{n}. Let us also assume that for every archimedean absolute value | · |_{ν} (i. e. ν ∈ S), the following holds :

3∥ζ∥_{ν}γ_{ν}(F, ζ) ≥ 3 − \sqrt{7}.

Then the average height of any approximate zero z ∈ ℚ[i]^{nD} of the system F with associated variety V_{ζ} that satisfies the γ–Theorem, also satisfies the following inequality :

ht_{av}(z) ≥ \frac{1}{2} [ht(ζ) − (\frac{1}{2} log n + log 2)] .

Theorem 6 and Proposition 7 imply Main Theorem 1 as stated at the introduction. In fact, in Section 4.2 below we exhibit three concrete examples (one corresponding to each of the three techniques described in Theorem 6 and Proposition 7) of approximate zeros that requiere exponential bit length. These lower bounds suggest that a central point of interest should be to study the bit length of approximate zeros satisfying the γ−Theorem. In order to shed some light in this direction, we prove the following statements :

Theorem 8 (Upper Bounds) Let f_{1}, …, f_{n} ∈ ℤ[X_{1}, …, X_{n}] be polynomials with integer coefficients. Let us assume that the following properties hold :

• max{deg(f_{i}) : 1 ≤ i ≤ n} ≤ 2, and

• ht(f_{i}) ≤ h for 1 ≤ i ≤ n.

Let ζ ∈ V_{K}(f_{1}, …, f_{n}) be a smooth K−rational point. Let | · |_{ν} : K ⟶ ℝ_{+} be an absolute value on K. Then, the following inequality holds :

log γ_{ν}(F, ζ) ≤ 3[K : ℚ]n (n^{2} + 4 log n + h + ht(ζ) + 3) .

In particular, we show the following estimate for the bit length of approximate zeros in ℚ[i]^{n} :

Corollary 9 (Upper bound on the bit length of approximate zeros) With the same assumptions and notations as in Theorem 8 above, let ζ ∈ V_{K}(f_{1}, …, f_{n}) be a smooth K−rational zero, and let | · |_{ν} be an absolute value on K. Let L ⊆ K be a number field such that ζ ∈ L_{ν}^{n}. Then there exist approximate zeros z ∈ L^{n} of the system F := (f_{1}, …, f_{n}) with approximate zero ζ with respect to the absolute value | · |_{ν}, such that the logarithmic height ht(z) of z is at most linear in the following quantities :

\frac{1}{[L : ℚ]} log |Δ_{L}| + [K : ℚ]n (n^{2} + h + nht(ζ)) ,

where |Δ_{L}| is the absolute value of the discriminant of the field L. Moreover, in the case where L = ℚ[i] (for instance, if |·|_{ν} is archimedean), there exist approximate zeros z ∈ ℚ[i]^{n} for the system F with associated zero ζ with respect to |·|_{ν} such that their bit lengths are at most linear in the following quantity :

[K : ℚ]n (n^{2} + h + nht(ζ)), in other words :
ht(z) ≤ O ([K : ℚ]n (n^{2} + h + nht(ζ))) .

Let us observe, that these two upper bounds above (i.e. Theorem 8 and Corollary 9) depend mainly on the input length : the dimension of the ambient space n and the height of the input polynomials h, and on two parameters which in turn depend on the actual zero to approximate : the degree [K : ℚ] of any field containing the residue class field of the actual zero and the logarithmic height ht(ζ) of the particular zero. These two quantities are bounded respectively by the geometric Bézout inequality (cf. [Hei83] or [Ful84, Vog84]) and the arithmetic Bézout inequality (cf. [BGS93, Phi91, Phi94, Phi95] or [KP94, KP96, Som98, Häg98, HMPS], for instance). Moreover, combining these two upper bounds (Theorem 8 and Corollary 9) with the previously shown lower bounds and several examples described in Subsection 4.2, we may conclude that the upper bounds shown in Theorem 8 and Corollary 9 are optimal. On the other hand, the γ−Theorem above has some aesthetic consequences which we may explain in terms of the existence of a universal radius of convergence independent of the absolute value under consideration. To this end, we recall the well–known Implicit Function Theorem for complete noetherian local rings in the following terms :

Theorem 10 (Non–archimedean quadratic basin of attraction) Let F := (f_{1}, …, f_{n}) ∈ ℤ[X_{1}, …, X_{n}]^{n} be a system of multivariate polynomials satisfying the hypotheses of Theorem 8 above. Let ν ∈ M_{K} define a non–archimedean absolute value | · |_{ν} on K. Let us also assume that the restriction

| · |_{ν} : ℚ ⟶ ℝ_{+}

defines a p−adic absolute value, where p ∈ ℕ is a prime number. Let ζ ∈ K^{n} be a smooth K−rational zero of the system which lies in the closed unit sphere of K^{n}, i.e.

ζ ∈ B_{ν}(0, 1) := {x ∈ K^{n} : ∥x∥_{ν} ≤ 1}.

Let us finally assume that | det DF (ζ)|_{ν} = 1. Then, for every z ∈ B_{ν}(0, 1) satisfying

∥z − ζ∥_{ν} ≤ \frac{1}{p}

holds : z is an approximate zero of the system F with associated zero ζ with respect to the absolute value | · |_{ν}.

This statement is nothing but the usual Hensel Lemma in local algebra (cf. [ZS58, Mor97], for instance). However, this statement has a drawback : The radius of the basin of attraction centered at ζ depends on the concrete absolute value | · |_{ν}. The proof of Theorem 8 above also shows that there exists a universal radius, which depends only on the system F and the smooth K−rational zero, but does not depend on any particular absolute value. To prove this claim, let us introduce quantity γ̃(F, ζ) as follows : With the same notations and assumptions as above, we define the universal quantity

γ̃(F, ζ) := ( ∏_{ν∈M_{K}} max\{1, γ_{ν}(F, ζ)\}^{n_{ν}} )^{\frac{1}{[K:ℚ]}} .

The same steps as in the proof of Theorem 8 above show that this quantity is well–defined and finite. Moreover, it does not depend on any particular absolute value under consideration. Thus, we may conclude the following Theorem :

Corollary 11 (Universal γ−Theorem) With the same notations and assumptions as in Theorem 6, for every z ∈ ℚ[i]^{n} and every absolute value | · |_{ν} satisfying the following inequality

∥z − ζ∥_{ν} γ̃(F, ζ) ≤ \frac{3 − \sqrt{7}}{2}

holds : z is an approximate zero for the system F with associated zero ζ and with respect to the absolute value ν ∈ M_{K}.

Let us point out that the existence of such a universal quantity does not imply the existence of a universal quadratic basin of attraction independent of the absolute value under consideration (cf. Subsection 4.3 below). In fact, we show the following statement :

Corollary 12 Let F := (f_{1}, …, f_{n}) be a sequence of multivariate polynomials with integer coefficients satisfying our hypotheses i) to v) above. Let ζ ∈ V_{K}(f_{1}, …, f_{n}) be a smooth K−rational zero. The only point z ∈ K^{n} that satisfies the universal γ−Theorem near γ for all absolute values in M_{K} is z = ζ. Namely, for every z ∈ K^{n} satisfying the following inequality for every ν ∈ M_{k}

∥z − ζ∥_{ν} ≤ \frac{3 − \sqrt{7}}{2γ̃(F, ζ)}

holds z = ζ.

2.2 Kronecker’s approach to solving

In [Kro82], Kronecker introduced a notion of solution of unmixed complex algebraic varieties, which we are going to reproduce here. Let f_{1}, …, f_{i} ∈ ℤ[X_{1}, …, X_{n}] be a sequence of polynomials defining a radical ideal (f_{1}, …, f_{i}) of codimension i in ℂ[X_{1}, …, X_{n}]. Let V := V (f_{1}, …, f_{i}) ⊆ ℂ^{n} be the complex algebraic variety of codimension i given by the common zeros of the f_{i}. A solution of V is a birational isomorphism of V with some complex algebraic hypersurface in a space of adequate dimension. Technically, this is is expressed as follows. First of all, let us assume that the variables X_{1}, …, X_{n} are in Noether position with respect to the variety V, i.e. we assume that the following is an integral ring extension :

ℚ[X_{1}, …, X_{n−i}] ↪ ℚ[X_{1}, …, X_{n}]/(f_{1}, …, f_{i}).

Let u := λ_{n−i+1}X_{n−i+1} + ⋯ + λ_{n}X_{n} ∈ ℚ[X_{1}, …, X_{n}] be a linear form in the dependent variables {X_{n−i+1}, …, X_{n}}. Thus we have a linear projection

U : ℂ^{n} ⟶ ℂ^{n−i+1} : (x_{1}, …, x_{n}) ⟼ (x_{1}, …, x_{n−i}, u(x_{1}, …, x_{n})) .

Let us also consider the restriction U |_{V} : V ⟶ ℂ^{n−i+1}. The linear form u is called a primitive element, if and only if the projection U |_{V} defines a birational isomorphism of V with some complex hypersurface H_{u} in ℂ^{n−i+1} with minimal equation χ_{u} ∈ ℚ[X_{1}, …, X_{n−i}, T]. Then, a Kronecker solution of variety V consists of a description of the primitive element u, the hypersurface H_{u} through the minimal equation χ_{u}, and a description of the inverse of the birational isomorphism, i.e. (U |_{V})^{−1}. Formally, this list of items can be described as follows :

• The list of variables in Noether position X_{1}, …, X_{n} (which implies a description of the dimension of V).

• The primitive element u := λ_{n−i+1}X_{n−i+1} + ⋯ + λ_{n}X_{n} given by its coefficients in ℤ.

• The minimal equation of the hypersurface H_{u}, namely

χ_{u} ∈ ℤ[X_{1}, …, X_{n−i}, T].

• A description of (U |_{V})^{−1}. This description is given by the following list :

– A non–zero polynomial ρ ∈ ℤ[X_{1}, …, X_{n−i}].

– A list of polynomials v_{j} ∈ ℤ[X_{1}, …, X_{n−i}, T], n − i + 1 ≤ j ≤ n, such that the degrees with respect to variable T satisfy deg_{T} (v_{j}) ≤ deg_{T} (χ_{u}) for every j, n − i + 1 ≤ j ≤ n.

such that the following holds

(U |_{V})^{−1}(x, t) = (x_{1}, …, x_{n−i}, ρ^{−1}(x)v_{n−i+1}(x, t), …, ρ^{−1}(x)v_{n}(x, t)) ,

where x := (x_{1}, …, x_{n−i}) ∈ ℂ^{n−i} and t ∈ ℂ.

Let us assume that V (f_{1}, …, f_{n}) ⊂ ℂ^{n} is a finite set. A Kronecker description of the residue class field K(ζ) of the actual zero ζ ∈ V_{K}(f_{1}, …, f_{n}) is a Kronecker description of the ℚ–irreducible component V_{ζ} of V (f_{1}, …, f_{n}) that contains ζ. Kronecker conceived an iterative procedure to solve multivariate systems of equations F := (f_{1}, …, f_{n}) defining zero–dimensional complex varieties, which can be described in the following terms : First, you start with system (f_{1}) and you “solve” the unmixed variety of codimension 1, V (f_{1}) ⊆ ℂ^{n}. Then you proceed iteratively : From Kronecker’s solution of the variety V (f_{1}, …, f_{i}) you eliminate the new equation f_{i+1} to obtain a Kronecker solution of the “next” variety V (f_{1}, …, f_{i+1}). Proceed until you reach i = n. This iterative procedure has two main drawbacks, which can be explained in the following terms :

• First of all, the space problem arising with the representation of the intermediate polynomials. The polynomials χ_{u}, ρ and v_{j} are polynomials of high degree (eventually of degree 2^{i}) involving several variables. Thus, to represent them, one has to handle all their coefficients, which amounts to the following quantities

\binom{2^{i} + n − i + 1}{n − i + 1},

which for i := n/2 amounts to more than 2^{n^{2}/4} coefficients of great bit length.

• Secondly, Kronecker’s iterative procedure introduces a nesting of interpolation procedures required for the iterative process and the linear change of coordinates required by each computation of a Noether normalisation. This nesting of interpolation procedures is difficult to avoid and increases the run time complexity.

Therefore, the procedure was forgotten by contemporary mathematicians and hardly mentioned in the literature of algebraic geometry. Macaulay quotes Kronecker’s procedure in [Mac16] and so does König in [Kön03]. But both thought that this procedure would require excessive run time to be efficient, and so it was progressively forgotten. Traces of this procedure can be found spread over the algebraic geometry literature without giving the required relevance to it. For example, Kronecker’s notion of solution was used by O. Zariski in [Zar95] to define a notion of dimension for algebraic varieties, claiming that it was also used in the same form by Severi and others. In 1995, two works rediscovered Kronecker’s approach to solving without previous knowledge of it’s existing ancestors. These two works [GHMP95, Par95] were able to overcome the first drawback (space problem of representation) of the previous methods. The technical trick was the use of a data structure coming from semi–numerical modeling : straight–line programs. This idea of representing polynomials by programs evaluating them goes back to previous work of the same research group (such as [GH93, FGS95, KP94] or [KP96]). Moreover, these ideas were the natural continuation of the ideas previously developped in [GH91]. To overcome the second drawback (Nesting), the authors introduced a method based on Newton’s method applied in a non–archimedean context (the approximate zeros in the corresponding non– archimedean basin of attraction were called Lifting Fibers in [GHH^{+}97]). This result was obtained in the two papers [GHH^{+}97, GHM^{+}98]. The key trick to avoid the nesting of interpolation procedures is based on Hensel’s Lemma (also Implicit Mapping Theorem). Perhaps, the following statement could help explain the relations existing between Hensel’s Lemma and Approximate Zero Theory. To this end, let us introduce some more notations. Let f_{1}, …, f_{r} ∈ ℂ[X_{1}, …, X_{n}] be a sequence of polynomials defining a radical ideal of codimension r in ℂ[X_{1}, …, X_{n}]. Let us assume that the variables X_{1}, …, X_{n} are in Noether position with respect to the ideal I := (f_{1}, …, f_{r}), i.e. assume that the following ring extension is integral

ℂ[X_{1}, …, X_{n−r}] ↪ ℂ[X_{1}, …, X_{n}]/I.

Let P := (p_{1}, …, p_{n−r}) ∈ ℂ^{n−r} be an affine point, let O_{P} be the ring of formal power series at P, and let M_{P} be the field of fractions of O_{P}. Then, the following is finite ring extension

M_{P} ↪ B := M_{P} [X_{n−r+1}, …, X_{n}]/(f_{1}, …, f_{r}),

and B is a zero–dimensional M_{P} −algebra. Thus, it makes sense to look for approximate zeros of the solutions in M_{P}^{r} of the system of polynomial equations F := (f_{1}, …, f_{r}). The following statement about Hensel’s Lemma explains the connections existing between Kronecker’s solution and Approximate Zero Theory.

Theorem 13 (Hensel’s Lemma) With the same assumptions and notations as above, let ζ ∈ M_{P}^{r} be a solution of the system F. Let ∥ · ∥ : M_{P}^{r} ⟶ ℝ be the usual non–archimedean norm in M_{P}^{r}. Let ℂ(X_{1}, …, X_{n−r}) be the field of rational functions. Then, for every z ∈ ℂ(X_{1}, …, X_{n−r})^{r}, if ∥z∥ ≤ 1, and

∥z − ζ∥ < \frac{1}{2},

then z is an approximate zero for the system F := (f_{1}, …, f_{r}) with associated zero ζ ∈ M_{P}^{r}.

Unfortunately, those two works [GHH^{+}97, GHM^{+}98] introduced (for the Lifting Fibers) run time requirements which depend on the heights of the intermediate varieties (in the sense of [BGS93, Phi91, Phi94, Phi95, Som98]). This drawback was finally overcome in the paper [GHMP97], where integer numbers were represented by straight–line programs and the following result established :

Theorem 14 [GHMP97] There exists a bounded error probability Turing machine M which performs the following task : Given a system of multivariate polynomial equations F := (f_{1}, …, f_{n}), satisfying the following properties • deg(f_{i}) ≤ 2 and ht(f_{i}) ≤ h for 1 ≤ i ≤ n,

• the ideals (f_{1}, …, f_{i}) are radical ideals of codimension i in the ring ℚ[X_{1}, …, X_{n}] for 1 ≤ i ≤ n − 1,

• the variety V (f_{1}, …, f_{n}) ⊆ ℂ^{n} is a zero–dimensional complex algebraic variety,

the machine M outputs a Kronecker solution of the variety V (f_{1}, …, f_{n}). The running time of the machine M is polynomial in the following quantities

δ(F) n h,

where δ is the maximum of the degrees of the intermediate varieties (in the sense of [Hei83]), namely

δ(F) := max{deg(V (f_{1}, …, f_{i})) : 1 ≤ i ≤ n − 1}.

It must be said that the coefficients of the polynomials involved in a Kronecker solution of the variety V (f_{1}, …, f_{n}) are given by straight–line programs that evaluate integer numbers. However, the complexity estimates for the Turing machine M are independent from the height. Our attempt in these pages is to compare this approach to solving developped by Kronecker to that of Newton as described in the previous Subsection. Moreover, we observe that approximate zeros are succinct encodings of the residue class field of the actual zero. In more precise terms we show the following statement :

Theorem 15 (From Approximate Zeros to Geometric Solution) With the same assumptions as in Theorem 14 above, there exists a bounded error probability Turing machine M, such that taking as input the binary encoding of an approximate zero z ∈ ℚ[i] of the system F with associated zero ζ ∈ V_{K}(f_{1}, …, f_{n}) for an archimedean absolute value | · |_{ν} (where ν ∈ S), M outputs a Kronecker’s description of the residue class field of ζ (i.e. a Kronecker’s description of the ℚ−irreducible component V_{ζ} of V (f_{1}, …, f_{n}) that contains the actual zero ζ. Moreover, the running time of this probabilistic Turing machine is polynomial in the following quantities

deg(ζ) (n h ht(z)ht(ζ)) ,

where deg(ζ) : [ℚ(ζ) : ℚ] is the degree over ℚ of the residue class field of the actual zero.

The key idea for the proof of this Theorem is the use of the L^{3} (or LLL) reduction algorithm as described in Subsection 5.5 below. Let us observe that this Theorem proves claim i) of Main Theorem 2. Conversely, as approximate zeros may depend on the height of the actual zero they approximate, we could be interested in the computation of approximate zeros for actual zeros of small (bounded) height.

Theorem 16 (From Kronecker’s solution to Newton’s solution) There exists a bounded error probability Turing machine M which performs the following task : Given a sequence of polynomial equations F := (f_{1}, …, f_{n}) of degree at most 2 and height at most h, and given a positive integer number H ∈ ℕ in binary encoding, the machine M outputs approximate zeros for the archimedean absolute value | · | : K ⟶ ℝ induced on K by the inclusion i : K ↪ ℂ for all those zeros ζ ∈ V_{K}(f_{1}, …, f_{n}), whose logarithmic height is at most H, i.e.

ht(ζ) ≤ H.

The running time of M is polynomial in the following quantities :

(n h δ(F)) + (D n h H),

where the notations are the same as in Theorem 14 before.

Let us observe that there exists a universal constant c > 0 such that ∀ζ ∈ V (f_{1}, …, f_{n})

ht(ζ) ≤ 2^{cn}h.

In particular, Theorem 16 above implies the following Corollary :

Corollary 17 There exists a bounded error probability Turing machine M that from input F := (f_{1}, …, f_{n}) satisfying hypotheses i) to v) from the Introduction, outputs approximate zeros for all smooth zeros ζ ∈ V (f_{1}, …, f_{n}) in binary encoding. The running time of M is simply exponential.

A proof of this statement is given in Subsection 5.4 below, based again on an application of the L^{3} reduction algorithm. Within the proof of this Theorem we include a proof of claim ii) of Main Theorem 2. Let Vol(F) be the normalized volume of the Newton polytope of the set

{X_{1}, …, X_{n}, M(F)},

where M(F) is the set of all monomials occuring in the polynomials f_{1}, …, f_{n} (cf. [Ber75, Kus76, Stu96]). As δ(F) ≤ Vol(F), we obviously conclude the following Corollary for the sparse case.

Corollary 18 (Sparse case) There exists a bounded error probability Turing machine M which performs the following task : Given a sequence of polynomial equations F := (f_{1}, …, f_{n}) of degree at most d and height at most h, and given a positive integer number H ∈ ℕ in binary encoding, the machine M outputs approximate zeros for the archimedean absolute value | · | : K ⟶ ℝ induced on K by the inclusion i : K ↪ ℂ for all those zeros ζ ∈ V_{K}(f_{1}, …, f_{n}), whose logarithmic height is at most H, i.e.

ht(ζ) ≤ H.

The running time of M is polynomial in the following quantities :

(n d h ♯M(F)Vol(F)) + (D n h H),

where the notations are the same as in Theorem 14 before.

2.3 Application : Computation of splitting field and Lagrange resolvent

Combining both Kronecker’s and Newton’s approach to solving, we exhibit an efficient procedure for computing the splitting field and the Lagrange resolvent of an irreducible monic univariate polynomial f ∈ ℚ[X] of degree d. Let us recall that the splitting field of f is the minimal number field K(f) containing the field of rational numbers ℚ and all roots of f (i.e. the minimal number field where f splits completely, also called the normal closure of the equation f = 0). This normal closure K(f) is nothing but the Galois field of f and it satisfies

[K(f) : ℚ] = ♯ (Gal_{ℚ}(f)) ,

where Gal_{ℚ}(f) is the Galois group of the polynomial f. The splitting field of f can be identified with an irreducible component of the zero–dimensional algebra (known as the universal decomposition algebra)

A := ℚ[X_{1}, …, X_{d}]/(σ_{0} − a_{0}, …, σ_{d−1} − a_{d−1}),

where σ_{0}, …, σ_{d−1} are the elementary symmetric functions and f is written as f(X) := a_{0} +a_{1}X + ⋯ + a_{d−1}X^{d−1} + X^{d}. Let us also observe that the Lagrange resolvent is nothing but the Chow (or Cayley) elimination polynomial of the zero–dimensional residue algebra A/𝔪, where 𝔪 is a wellchosen maximal ideal of A. Therefore, we can also show the following Theorem as a consequence of the comparison between Newton’s and Kronecker’s approach to solving :

Theorem 19 (Splitting Field and Lagrange Resolvent) There exists a probabilistic Turing machine, which for every given univariate polynomial f ∈ ℤ[X] of degree at most d and logarithmic height at most h computes the following items :

i) Approximate zeros in ℚ[i] of all zeros of f,

ii) a geometric description of the splitting field K(f) of the polynomial f, and

iii) the Lagrange resolvent of the equation f = 0.

The running time of M is polynomial in the following quantities :

♯ (Gal_{ℚ}(f)) (d h) .

3 Fundamental tools

3.1 Heights and norms

3.1.1 Multivariate polynomials

A multivariate polynomial over a field K is a syntactic mathematical object whose existence is due to the systematic study of a certain class of semantical objects : the polynomial functions

f : K^{n} ⟶ K.

Thus, in a polynomial we may observe two aspects : the syntactical and the semantical. Years of tradition in the systematic study of polynomial functions have established a convention of representing polynomials by their monomial expansions. Therefore a relevant part of the mathematical studies has tried to relate both aspects. Several different estimates have been used just to connect the syntactical representation and the semantical geometric object, for instance, relating the degree of a polynomial and the degrees of the hypersurfaces given as the fibers f^{−1}({0}). Let us give here the notation used for the dense monomial encoding : Let ⟨·, ·⟩ denote the standard hermitian product on the field of complex numbers ℂ. For every complex number a ∈ ℂ, we denote by |a| := \sqrt{⟨a, a⟩} its absolute value. Each multivariate complex polynomial P ∈ ℂ[X_{1}, …, X_{n}] has a dense representation of the form :

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

where d := deg(P) denotes the total degree of P, μ := (μ_{1}, …, μ_{n}) ∈ ℕ^{n} is a multi–index, |μ| := μ_{1} + ⋯ + μ_{n} is its length and the P_{μ} are coefficients in ℂ. Whereas the degree is an outstanding syntactical invariant for the geometry of the hypersurface defined by a polynomial, other metric measures are required when diophantine properties are studied. We define the (standard) weight of a complex polynomial P ∈ ℂ[X_{1}, …, X_{n}] as :

W T (P) := ∑_{|μ|≤d} |P_{μ}|.

To simplify some expressions we often use the following notation : Given \underline{X} := (X_{1}, …, X_{n}) a list of variables and \underline{μ} := (μ_{1}, …, μ_{n}) ∈ ℕ^{n} a multi–index, we write \underline{X}\underline{μ} to denote

\underline{X}\underline{μ} := X_{1}^{μ_{1}} ⋯ X_{n}^{μ_{n}}.

3.1.2 Absolute values over number fields

We resume here in a very concise form the language and notation used for absolute values over number fields. For an introduction refer to e.g. [Lan83, Chapter 1], whereas a more complete exposition of the theory of absolute values can be found in Artin’s Algebraic Numbers and Algebraic Functions [Art51] or [McC76]. Let 𝕂 be the algebraic closure of a number field K. Let | · |_{ν} : K ⟶ ℝ_{+} be an absolute value defined on the number field K. By K_{ν} we denote the completion of K with respect to this absolute value | · |_{ν} and by 𝕂_{ν} we denote the algebraic closure of K_{ν}. For sake of simplicity, we also denote by | · |_{ν} : K_{ν} ⟶ ℝ_{+} the (unique) extension to K_{ν} of the absolute value | · |_{ν} defined on K. We also assume that for archimedean | · |_{ν} the algebraic closure 𝕂_{ν} is included in ℂ. Finally, we denote by n_{ν} the degree of K_{ν} over the completion of ℚ with respect to the absolute value | · |_{ν} : ℚ ⟶ ℝ. Following [Lan83], let M_{K} be a proper set of absolute values of K. We assume that M_{K} has been chosen such that it satisfies Weil’s product formula with multiplicities n_{ν} : For all x ∈ K \ {0} holds

\frac{1}{[K : ℚ]} ∑_{ν∈M_{K}} n_{ν} log |x|_{ν} = 0  (1)

where log stands for the natural logarithm, cf. [Lan83, Chapter 2]. Let us recall that by [Lan83, Proposition 4.3], for any given absolute value w on ℚ and all absolute values ν extending w to K, the following holds :

∑_{ν|w} n_{ν} = [K : ℚ].  (2)

Observe that the proper set of absolute values M_{K} has only a finite number of archimedean absolute values (precisely the independent extensions of the ordinary archimedean value on ℚ to K induced by the non–isomorphic embeddings of K into ℂ, see below). Let us recall that for archimedean valuations, i.e. ν ∈ S, the absolute value | · |_{ν} is defined in the following terms : for every ν ∈ S, there exists an associated embedding σ_{ν} : K ⟶ ℂ, such that for all a ∈ K holds

|a| := |σ_{ν}(a)|,

where | · | stands for the usual absolute value in ℂ. For archimedean valuations ν ∈ S, given a polynomial P in K[X_{1}, …, X_{n}], we denote by σ_{ν}(P) the polynomial in ℂ[X_{1}, …, X_{n}] given by

σ_{ν}(P) := ∑_{|μ|≤d} σ_{ν}(P_{μ}) X_{1}^{μ_{1}} ⋯ X_{n}^{μ_{n}}.

Now, for all valuations ν ∈ M_{K}, we define the (logarithmic) height of P with respect to the absolute value | · |_{ν} as the logarithm of the maximum of the absolute values of the coefficients of P with respect to | · |_{ν}, i.e.

ht_{ν}(P) := max_{|μ|≤d}{log |P_{μ}|_{ν}}.

Similarly, for every affine point \underline{x} := (x_{0}, …, x_{n}) ∈ K^{n+1} and for every ν ∈ M_{K} we may define the height of \underline{x} with respect to the absolute value | · |_{ν} as

ht_{ν}(\underline{x}) := max\{log |x_{i}|_{ν} : 0 ≤ i ≤ n\}

Finally, we define in the same way for a finite set F ⊆ K the (logarithmic) height of F with respect to the absolute value | · |_{ν} as

ht_{ν}(F) := max{log |a|_{ν} : a ∈ F}.

Let us observe that all these notions of height depend on the absolute value | · |_{ν} and on the field extension ℚ ⊆ K. Later on (in Subsection 3.1.3 below), we discuss a notion of height independent of the absolute value and the field extension under consideration : Weil’s height. For archimedean absolute values we define the weight of P with respect to the absolute value | · |_{ν} as the sum of the absolute values of the coefficients of P, i.e. for a polynomial P ∈ K[X_{1}, …, X_{n}] as

wt_{ν}(P) := log ( ∑_{|μ|≤d} |P_{μ}|_{ν} ) .

Let us remark that wt_{ν}(P) = wt(σ_{ν}(P)) holds. Moreover, if P ∈ K[X_{1}, …, X_{n}] is a polynomial of degree at most d, the following relations hold :

ht_{ν}(P) ≤ wt_{ν}(P) ≤ log \binom{d + n}{n} + ht_{ν}(P).

3.1.3 Height of affine points

The measures we have chosen for the estimation of degrees and heights in our complexity study have a double aspect : geometric and diophantine. The geometric aspect refers to properties coming from algebraic geometry. Typically we may consider degrees of polynomials, number of monomials or the cardinality of zero–dimensional solution sets given by systems of multivariate polynomial equations. The diophantine aspect is more concerned with metric properties of the polynomials and the solution sets. Both Nesterenko and Philippon considered in their works the Chow form or elimination polynomial for the introduction of a notion of height for unmixed varieties. Furthermore, Philippon used the Mahler measure for the definition of an invariant height for projective varieties over the algebraic closure of ℚ by considering local height functions on the Chow form of the variety. We start with the standard definition for the height of a projective point (cf. [Lan83]). Given a projective point \underline{x} := (x_{0} : x_{1} : …: x_{n}) ∈ ℙ^{n}(K) with coordinates in the number field K, we define the logarithmic height of the projective point \underline{x} (or simply the height) as :

ht(\underline{x}) := \frac{1}{[K : ℚ]} ( ∑_{ν∈M_{K}} n_{ν}ht_{ν}(\underline{x})) ,

which does not depend on the number field K under consideration. For any affine point \underline{x} := (x_{1}, …, x_{n}) ∈ K^{n}, we define its affine logarithmic height as the height of the projective point (1 : x_{1} : …: x_{n}) ∈ ℙ^{n}(K), i.e.

ht(x) := ht(1 : x_{1} : …: x_{n}) := \frac{1}{[K : ℚ]} ( ∑_{ν∈M_{K}} n_{ν} max\{0, ht_{ν}(\underline{x})\})

This notion of logarithmic height of an affine point is not so far from computational terms. Let us assume K := ℚ[i] as number field and \underline{x} ∈ ℚ[i]^{n} a point in the corresponding affine space. The point \underline{x} := (x_{1}, …, x_{n}) can also be seen as a list of objects that may be represented by digits on a tape of a Turing machine (cf. [BDG88] for more details). The bit length of \underline{x} is understood as the amount of tape cells of the Turing machine required to keep written numerators and denominators of the coordinates of the list \underline{x}. Let us denote by ℓ(\underline{x}) this bit length. An elementary argument shows the following inequalities relating bit length and height :

ht(\underline{x}) ≤ ℓ(\underline{x}) ≤ 4nht(\underline{x}).

In the sequel we use either bit length or height to refer to these essentially equivalent notions for affine points in ℚ[i]^{n}.

Given a finite set F := {b_{i} : 1 ≤ i ≤ M} ⊆ K, we can associate the affine point in K^{M} whose coordinates are the elements of F. Then, the height of F will be defined as the height of this affine point, namely :

ht(F) := ht(b_{1}, …, b_{M}).

Let us observe that if the finite set F consists of just one point F = {α} ⊂ K, the height ht(F) gives the usual notion of logarithmic height of the algebraic number α ∈ K. This notion of logarithmic height verifies the conditions a) to e) of Proposition 4 of Chapter 7 of [BCSS98b] in logarithmic form, namely :

Lemma 20 Let x, y ∈ K be two complex algebraic numbers. With the previous notations, the following inequalities hold :

i) ht(a) = log |a| ∀a ∈ ℤ, ht(x) = ht(−x) = ht(x^{−1}) ∀x ∈ K \ {0},

ii) ht(x + y) ≤ ht(x) + ht(y) + log 2,

iii) ht(x^{k}) = kht(x),

iv) ht(x + y) ≥ ht(x) − (ht(y) + log 2), and

v) ht(xy) ≥ ht(x) − ht(y) for y ≠ 0.

vi) For every absolute value ν ∈ M_{K} and x ∈ K \ {0} the following holds

−[K : ℚ]ht(x) ≤ log |x|_{ν} ≤ [K : ℚ]ht(x).

It is not always wise to use these properties in the obvious inductive form or to apply them as a recursive tool. For instance, the following Lemma shows how to bound the height of the sum of algebraic numbers.

Lemma 21 Given x_{1}, …, x_{n} ∈ K algebraic numbers, we have:

ht(∑_{i=1}^{n} x_{i}) ≤ log n + ht(x_{1}, …, x_{n}).

Proof.– Let \underline{x} := (x_{1}, …, x_{n}) ∈ K^{n} be the corresponding affine point. We have

ht(∑_{i=1}^{n} x_{i}) = \frac{1}{[K : ℚ]} ( ∑_{ν∈M_{K}} n_{ν} max\{0, log |∑_{i=1}^{n} x_{i}|_{ν}\}) .

Now, we discuss separately archimedean and non–archimedean absolute values to obtain the following inequality :

ht(∑_{i=1}^{n} x_{i}) ≤ \frac{1}{[K : ℚ]} (∑_{ν∈S} n_{ν} max\{0, log n + ht_{ν}(\underline{x})\}) +

\frac{1}{[K : ℚ]} ( ∑_{ν∈M_{K}\S} n_{ν} max\{0, ht_{ν}(\underline{x})\}) ≤

≤ \frac{1}{[K : ℚ]} (∑_{ν∈S} n_{ν} log n) + \frac{1}{[K : ℚ]} ( ∑_{ν∈M_{K}} n_{ν} max\{0, ht_{ν}(\underline{x})\})

By Identity 2 above, we easily conclude ht(∑_{i=1}^{n} x_{i}) ≤ log n + ht(\underline{x}) as desired.

For multivariate polynomials P ∈ K[X_{1}, …, X_{n}] of degree at most d, we can identify the polynomial P with the affine point \overline{P} ∈ K^{M}, whose coordinates are the coefficients of P. Let M be the combinatorial number :

M := \binom{d + n}{n},

then, the height of P is defined as the height of the affine point \overline{P} ∈ K^{M}. This yields the following identity

ht(P) := ht(\overline{P}) = \frac{1}{[K : ℚ]} ( ∑_{ν∈M_{K}} n_{ν} max\{0, ht_{ν}(P)\}) .

Another useful notion is that of absolute logarithmic weight, which is also independent of the field extension. For every polynomial P ∈ K[X_{1}, …, X_{n}], we define its weight in the following terms :

• Archimedean weight :

wt_{a}(P) := \frac{1}{[K : ℚ]} (∑_{ν∈S} n_{ν} max\{0, wt_{ν}(P)\}) ,

• Non–archimedean weight :

wt_{na}(P) := \frac{1}{[K : ℚ]} ( ∑_{ν∈M_{K}\S} n_{ν} max\{0, ht_{ν}(P)\}) ,

• Weight :

wt(P) := wt_{a}(P) + wt_{na}(P).

Let us observe that, if P ∈ ℤ[X_{1}, …, X_{n}] is a polynomial with integer coefficients, this notion of height agrees with the logarithm of the standard weight, i.e.

wt(P) = log W T (P).

These notions of height and weight have many relevant applications and properties. Let us shortly point out some relevant facts concerning univariate polynomials.

Lemma 22 Let P = ∑_{k=0}^{d} a_{k}X^{k} ∈ K[X] be a univariate polynomial and x ∈ K an algebraic number. Then holds :

ht(P (x)) ≤ log(d + 1) + ht(P) + dht(x).

Proof.– Let us define the affine points \underline{a} := (a_{0}, a_{1}, …, a_{d}) ∈ K^{d+1} and \underline{A} := (a_{0}, a_{1}x, …, a_{d}x^{d}) ∈ K^{d+1}. Then, we may apply the previous Lemma 21 to obtain

ht(P (α)) ≤ log(d + 1) + ht(\underline{A}).

Now, for every ν ∈ M_{K} we have the following obvious inequality

max\{0, ht_{ν}(\underline{A})\} ≤ max\{0, ht_{ν}(\underline{a})\} + d max\{0, log |x|_{ν}\}.

This yields the following upper bound :

ht(\underline{A}) ≤ ht(\underline{a}) + dht(x) ≤ ht(P) + dht(x),

which proves the Lemma.

Lemma 23 (A lower bound) Given P = ∑_{k=0}^{d} a_{d}X^{d} ∈ K[X] an univariate polynomial, and x ∈ K, we have:

ht(P (x)) ≥ ht(x) − (log d + 2ht(P) + log 2)

Proof.– This proof follows the same strategy as the proof in [BCSS98b], modified by the bounds described in the two Lemmata 21,22 above.

An obvious consequence of the previous Lemma is the following estimate for the height of the zeros of a univariate polynomial.

Corollary 24 Given P = ∑_{k=0}^{d} a_{d}X^{d} ∈ K[X], and ζ ∈ K such that P (ζ) = 0. Then, we have

ht(ζ) ≤ (log d + 2ht(P) + log 2) .

It seems convenient to recall the reader the following, simpler estimate :

Lemma 25 Let \underline{x} ∈ K^{n} and \underline{y} ∈ K^{m} be two points in two affine spaces, we have

ht(\underline{x}, \underline{y}) ≤ ht(\underline{x}) + ht(\underline{y}).

3.1.4 Norms of affine points and linear operators

For the purposes of our study, we are interested in the normed vector space K^{n} endowed with the norms induced by the absolute values in M_{K}. Let ν ∈ M_{K} an absolute value and | · |_{ν} : K ⟶ ℝ_{+} the absolute value function. We can endow K^{n} with a norm ∥ · ∥_{ν} : K^{n} ⟶ ℝ_{+} in the following way :

• If | · |_{ν} is archimedean (i.e. ν ∈ S), we define ∥v∥_{ν} := \sqrt{∑_{i=1}^{n} |z_{i}|_{ν}^{2}}.

• Otherwise (i.e. if ν ∈ M_{K} \ S), we define ∥v∥_{ν} := max_{i=1}^{n} |z_{i}|_{ν}.

Let K_{ν} be the completion of K with respect to the absolute value | · |_{ν}. According to the previous rules, we may also define the (unique) extensions to K_{ν} and K_{ν}^{n} of the previous functions defined on K. In other words, we also use | · |_{ν} and ∥ · ∥_{ν} to denote the mappings

| · |_{ν} : K_{ν} ⟶ ℝ_{+} and ∥ · ∥_{ν} : K_{ν}^{n} ⟶ ℝ_{+}.

Thus, we may introduce the standard notions of norm for linear and multilinear operators over K_{ν}−vector spaces : Let us assume that A : K_{ν}^{n} ⟶ K_{ν}^{n} is a linear mapping. As usual, we define the norm ∥A∥_{ν} of the n × n matrix A ∈ M_{n}(K_{ν}) in the following terms :

∥A∥_{ν} := sup{∥A(v)∥_{ν} : v ∈ K_{ν}^{n} , ∥v∥_{ν} ≤ 1}.

Given a multilinear operator

A : (K_{ν}^{n})^{m} ⟶ K_{ν}^{n},

we define its norm in a straight forward way as :

∥A∥_{ν} := sup{∥A(v_{1}, …, v_{m})∥_{ν} : v_{i} ∈ K_{ν}^{n}, ∥v_{i}∥_{ν} ≤ 1, ∀i, 1 ≤ i ≤ m}.

Let us also introduce the Frobenius or Hilbert–Weil norm ∥ · ∥_{ν}^{(F)} on M_{n}(K_{ν}), associated to the absolute value ν ∈ M_{K}. First of all, let us assume that | · |_{ν} is archimedean. Let σ_{ν} : K_{ν} ⟶ ℂ the embedding of the completion of K into the field of complex numbers. For every square matrix A ∈ M_{n}(K_{ν}) we define its Frobenius norm in the following terms :

∥A∥_{ν}^{(F)} := \sqrt{Tr(A_{ν}^{∗}A_{ν})} = \sqrt{∑_{i,j=1}^{n} |a_{ij}|_{ν}^{2}},

where Tr stands for the standard trace of a square matrix, A_{ν} := σ_{ν}(A) ∈ M_{n}(ℂ) and A_{ν}^{∗} is the transposed conjugate matrix of A_{ν}. On the other hand, if |·|_{ν} is non–archimedean and A := (a_{i,j})_{i,j} ∈ M_{n}(K_{ν}), we define the Frobenius norm of A with respect to the non–archimedean absolute value | · |_{ν} in the following terms :

∥A∥_{ν}^{(F)} := max{|a_{i,j}|_{ν} : 1 ≤ i, j ≤ n}.

Let us consider in M_{n}(K_{ν}) the subgroup GL(n, K_{ν}) of all non–singular n×n matrices with entries in K_{ν}. Similarly, we denote by GL(n, K) the subgroup of GL(n, K_{ν}) of all non–singular n × n matrices with entries in the number field K. According to our notation introduced before, we define the algebraic varieties Σ_{ν} ⊆ M_{n}(K_{ν}) and Σ ⊆ M_{n}(K) of n × n singular matrices respectively in the following terms :

Σ_{ν} := M_{n}(K_{ν}) \ GL(n, K_{ν}) and Σ := M_{n}(K) \ GL(n, K).

These notions of norms of linear and multilinear operators verify the obvious usual properties. Let us point out just those used in the sequel.

Lemma 26 Let ν ∈ M_{K} be an absolute value on K. Let A := (a_{i,j})_{i,j} ∈ M_{n}(K_{ν}) be a square matrix and let B : (K_{ν}^{n})^{m} ⟶ K_{ν}^{n} a multilinear operator. Let J denote a suitable set of indices for B, i.e. B := (b_{j})_{j∈J} are the entries of B. The following properties hold :

i) (cf. [Cia82], for instance) For archimedean | · |_{ν} holds

∥A∥_{ν} ≤ ∥A∥_{ν}^{(F)} ≤ \sqrt{n}∥A∥_{ν}.

ii) (cf. [Tyl94]) For non–archimedean | · |_{ν} holds the equality ∥A∥_{ν} = ∥A∥_{ν}^{(F)}.

iii) Moreover, if A and B have entries in the number field K, they can be seen as points of the affine spaces K^{n^{2}} and K^{m^{n}}, respectively. Thus, the following inequalities hold :

log ∥A∥_{ν} ≤ log ∥A∥_{ν}^{(F)} ≤ log n + ht_{ν}(A) ≤ log n + [K : ℚ] max{ht(a_{i,j}) : 1 ≤ i, j ≤ n},

log ∥B∥_{ν} ≤ (m + 1) log n + [K : ℚ] max{ht(b_{j}) : j ∈ J}.

iv) For every ν ∈ M_{K}, these notions of norm behave as expected with respect to matrix products,

i.e.

∥AB∥_{ν} ≤ ∥A∥_{ν}∥B∥_{ν}

v) In particular, if A is a non–singular A ∈ GL(n, K_{ν})), the following inequalities hold :

∥A^{−1}B∥_{ν} ≥ \frac{∥B∥_{ν}}{∥A∥_{ν}} , and ∥A^{−1}∥_{ν} ≤ \frac{∥A∥_{ν}^{n−1}}{| det(A)|_{ν}} .

vi) If the matrix A is non–singular, then for every square matrix C ∈ M_{n}(K_{ν}) holds :

If ∥A − C∥_{ν} < \frac{1}{∥A^{−1}∥_{ν}} then this implies C ∈ GL(n, K_{ν}).

We relate norms, height and weight for images of polynomial mappings in the following Lemma :

Lemma 27 Let F : K^{n} ⟶ K^{m} a polynomial mapping, where m ≥ n. Let us assume that F := (f_{1}, …, f_{m}), where f_{i} ∈ K[X_{1}, …, X_{n}] is a polynomial of degree at most d such that

wt(f_{i}) ≤ w, ∀i, 1 ≤ i ≤ m.

Let x := (x_{1}, …, x_{n}) ∈ K^{n} be an affine point. The following inequalities hold :

i) ht(F (x)) ≤ w + dht(x).

ii) Let DF (x) : K_{ν}^{n} ⟶ K_{ν}^{m} be the tangent mapping given by the jacobian matrix of F at x. Then holds :

log ∥DF (x)∥_{ν} ≤ log(mnd) + (d − 1)ht_{ν}(x) + max{wt_{ν}(f_{i}) : 1 ≤ i ≤ m},

as well as the upper bound

log ∥DF (x)∥_{ν} ≤ log(mnd) + [K : ℚ] (w + (d − 1)ht(x)) .

iii) (Liouville lower bound) For every ν ∈ M_{K}, the following holds :

log ∥F (x)∥_{ν} ≥ −[K : ℚ] (w + dht(x)) .

Proof.– Claim i) follows by a strategy similar to that introduced in the proof of Lemma 22. The only difference consists in replacing the height by the weight when discussing archimedean absolute values. Claim ii) uses the following chain of inequalities :

∥DF (x)∥_{ν} ≤ ∥DF (x)∥_{ν}^{(F)} ≤ log(nm) + log max\{|\frac{∂f_{i}}{∂X_{j}} (x)|_{ν} : 1 ≤ i ≤ m, 1 ≤ j ≤ m\}.

Finally, we just have to observe that log |\frac{∂f_{i}}{∂X_{j}} (x)|_{ν} ≤ log d + wt_{ν}(f_{i}) + (d − 1)ht_{ν}(x). The rest

follows then from the relations between local and logarithmic weights and heights. To prove Claim iii), we argue in the following way : Let us assume that f_{i}(\underline{x}) ≠ 0. In this case, we have

ht(f_{i}(\underline{x})^{−1}) = ht(f_{i}(\underline{x})).

Moreover, the following inequality holds :

\frac{1}{[K : ℚ]} log |f_{i}(\underline{x})|_{ν}^{−1} ≤ \frac{1}{[K : ℚ]} ( ∑_{ν∈M_{K}} n_{ν} max\{0, log |f_{i}(\underline{x})|_{ν}^{−1}\}) = ht(f_{i}(\underline{x})).

Using the upper bound of Claim i), we conclude the following inequality :

\frac{1}{[K : ℚ]} log |f_{i}(\underline{x})|_{ν}^{−1} ≤ ht(f_{i}(\underline{x})) ≤ w + dht(\underline{x}).

Hence, the following holds : log ∥F (\underline{x})∥_{ν} ≥ log |f_{i}(\underline{x})|_{ν} ≥ −[K : ℚ] (w + dht(\underline{x})).

4 Newton’s approach to solving : On the bit length of approximate zeros

In this Section we shall prove the main statements concerning approximate zeros given in the Introduction. The Section is divided into three Subsections : The first is devoted to a proof of the Eckardt & Young Theorem for non–archimedean absolute values, the second and third show respectively lower and upper bounds for the bit length of approximate zeros.

4.1 Eckardt & Young Theorem.

First of all, we show Theorem 5 from Section 2. To this end, we quickly recall some of the notation : Let us consider in M_{n}(K_{ν}) the subgroup GL(n, K_{ν}) of all non–singular n×n matrices with entries in K_{ν}. Similarly, we denote by GL(n, K) the subgroup of GL(n, K_{ν}) of all non–singular n × n matrices with entries in the number field K. We define the algebraic varieties Σ_{ν} ⊆ M_{n}(K_{ν}) and Σ ⊆ M_{n}(K) of n × n singular matrices respectively as

Σ_{ν} := M_{n}(K_{ν}) \ GL(n, K_{ν}), and Σ := M_{n}(K) \ GL(n, K).

Let us also recall that d_{ν}^{(F)} is the Frobenius (also Hilbert–Weil) metric on M_{n}(K_{ν}). Then, the following holds :

Theorem 28 (Eckardt & Young) Let ν ∈ M_{K} be an absolute value. For every non–singular n × n matrix A ∈ GL(n, K), the following equality holds :

d_{ν}^{(F)}(A, Σ) = d_{ν}^{(F)}(A, Σ_{ν}) = inf\{d_{ν}^{(F)}(A, M) : M ∈ Σ\} = \frac{1}{∥A^{−1}∥_{ν}} .

Proof.– Let us start by assuming that | · |_{ν} is an archimedean absolute value. The proofs of [EY36, BCSS98a] establish the following identity :

d_{ν}^{(F)}(A, Σ_{ν}) = \frac{1}{∥A^{−1}∥_{ν}} .

Now, since Σ is dense in Σ_{ν} for the Frobenius norm, the statement follows for the archimedean case. Let us assume now that ν ∈ M_{K} \ S defines a non–archimedean absolute value | · |_{ν}, and that A = (a_{i,j})_{i,j} ∈ GL(n, K) is a non–singular matrix. Let A_{i,j} be the minor of matrix A obtained by suppressing row i and column j. Thus, from Claim ii) of Lemma 26, we conclude the following identity :

\frac{1}{∥A^{−1}∥_{ν}} = min \{|\frac{det(A)}{A_{i,j}} |_{ν} : A_{i,j} ≠ 0\} .

Without loss of generality, we may assume that this minimum is reached at A_{1,1}, i.e. we assume that the following identity holds :

\frac{1}{∥A^{−1}∥_{ν}} = |\frac{det(A)}{A_{1,1}} |_{ν} .

Let us consider the following (n − 1) × (n − 1) system of linear equations :

X_{2}a_{2,2} + … + X_{n}a_{2,n} = a_{2,1}
⋮  ⋮ ⋮  (3)
X_{2}a_{n,2} + … + X_{n}a_{n,n} = a_{n,1}

As the minor A_{1,1} is non–zero, this system of equations has a unique solution, which we shall denote by (λ_{2}, …, λ_{n}) ∈ K_{ν}^{n−1}. Using Cramer’s rule, we can determine the values λ_{i}, for every i, 2 ≤ i ≤ n in the following terms :

λ_{i} := \frac{(−1)^{i}A_{1,i}}{A_{1,1}} ∈ K.

Now we define the n × n square matrix M as

M := ( \begin{matrix}m_{1,1} & ⋯ & m_{1,n} \\ ⋮ & & ⋮ \\ m_{n,1} & ⋯ & m_{n,n} \end{matrix} ) ∈ M_{n}(K),

whose entries are given by the following rules :

• For every j ≠ 1, we define m_{i,j} := a_{i,j} ∈ K.

• For every i, 1 ≤ i ≤ n, we define m_{i,1} := ∑_{j=2}^{n} λ_{i}a_{i,j}.

Obviously, the matrix M is singular and its entries are in K (i.e. M ∈ Σ). Moreover, we have

A − M := ( \begin{matrix}c_{1,1} & 0 & ⋯ & 0 \\ 0 & 0 & ⋯ & 0 \\ ⋮ & & & ⋮ \\ 0 & 0 & ⋯ & 0 \end{matrix} ) , where c_{1,1} = a_{1,1} − ∑_{i=2}^{n} λ_{i}a_{1,i}.

Using the identity that relates the values λ_{i} and the minors of the matrix A, one easily concludes that

c_{1,1} = a_{1,1} − \frac{1}{A_{1,1}} ∑_{i=2}^{n}(−1)^{i}a_{1,i}A_{1,i} = \frac{det(A)}{A_{1,1}}.

Thus, we conclude the following inequality :

d_{ν}^{(F)}(A, Σ) ≤ ∥A − M∥_{ν}^{(F)} = |\frac{det(A)}{A_{1,1}} |_{ν} = \frac{1}{∥A^{−1}∥_{ν}}

On the other hand, Claim v) of Lemma 26 shows that

d_{ν}^{(F)}(A, Σ) ≥ d_{ν}^{(F)}(A, Σ_{ν}) ≥ \frac{1}{∥A^{−1}∥_{ν}}

and therefore the proof is concluded for the non–archimedean case, too.

4.2 Approximate zero theory : Lower bounds for the bit length of approximate zeros.

Following the notations and assumptions of Subsection 2.1, we state a few more technical details, which will be used in the proofs of our statements concerning approximate zero theory. Introduced by S. Smale as a basic ingredient to study the complexity of Gauss’ proof of the Fundamental Theorem of Algebra (cf. [Sma81, BCSS98a] and the references therein), the notion of approximate zero has evolved to become a new foundation for numerical analysis. Previously, there had been several deep studies of the univariate case ([Sma81, Sma85, Sma86a, Sma86b, Ren87, SS86, SS85]), where the notion was successfully extended by M. Shub and S. Smale to the multivariate case (cf. [SS93a, SS93b, SS93c, SS96, SS94b]). Recent advances within this school have been obtained by J.P. Dedieu ([Ded96, Ded97c, Ded97b, Ded97a, DSa, DSb, DS98]), G. Malajovich ([Mal93, Mal94, Mal95]), J.C. Yakoubsohn ([Yak95b, Yak95a] and M.H. Kim [Kim85, Kim88, Kim89]). A useful technical tool to prove the γ–Theorem 4 is the following Proposition :

Proposition 29 With the same notations and assumptions as in Theorem 4, let us assume that

u := ∥z − ζ∥_{ν}γ_{ν}(F, ζ) ≤ \frac{3 − \sqrt{7}}{2} < 1 − \frac{\sqrt{2}}{2}.

Then DF (z) ∈ GL(n, K) is a non–singular matrix, and the following inequality holds :

∥DF (z)^{−1}DF (ζ)∥_{ν} ≤ \frac{(1 − u)^{2}}{ψ(u)} ,

where ψ(u) := 2u^{2} − 4u + 1.

Let us observe two facts concerning the γ−neighbourhood of an isolated smooth zero ζ ∈ V_{K}(f_{1}, …, f_{n}) : First, any smooth zero ζ ∈ V_{K}(f_{1}, …, f_{n}) is a fixed point of the Newton operator. Second, singular zeros ζ′ ∈ V_{K}(f_{1}, …, f_{n}) satisfy DF (F, ζ′) ∉ GL(n, K). Thus, no other zero ζ′ ∈ V_{K}(f_{1}, …, f_{n}) lies in the γ_{ν}−neighbourhood of ζ. In other words, the following inequality holds for every ζ′ ∈ V_{K}(f_{1}, …, f_{n}), ζ′ ≠ ζ :

∥ζ − ζ′∥_{ν}γ_{ν}(F, ζ) ≥ \frac{3 − \sqrt{7}}{2}.

In fact, defining sep_{ν}(F, K) as the minimum “separating” distance of any two K−rational zeros with respect to the absolute value ν ∈ M_{K}, we have

sep_{ν}(F, K) ≥ \frac{3 − \sqrt{7}}{2γ_{ν}(F, ζ)}.  (4)

Using the identity established in Eckardt & Young Theorem 5, we can show the following lower bound for γ_{ν}(F, ζ) :

Proposition 30 Let f_{1}, …, f_{n} ∈ ℤ[X_{1}, …, X_{n}] be a sequence of multivariate polynomials. Let us assume that the following holds :

• d = max{deg(f_{i}) : 1 ≤ i ≤ n} ≥ 2,

• ht(f_{i}) ≤ h, wt(f_{i}) ≤ w, 1 ≤ i ≤ n.

Let ζ ∈ V_{K}(f_{1}, …, f_{n}) be a smooth K−rational point with respect to the system of polynomials F := (f_{1}, …, f_{n}). Then, with the same notations as before, the following inequality holds :

log γ_{ν}(F, ζ) ≥ \frac{log d_{ν}^{(F)}(DF (ζ)^{−1}, Σ)}{d − 1} − (\frac{h}{d − 1} + 2 log d).

Proof.– Using Claim v) of Lemma 26, we have the following inequality :

γ_{ν}(F, ζ)^{d−1} ≥ \frac{∥\frac{D^{(d)}F (ζ)}{d!}∥_{ν}}{∥DF (ζ)∥_{ν}} .

From Theorem 5 we obviously conclude

\frac{1}{∥DF (ζ)∥_{ν}} = d_{ν}^{(F)}(DF (ζ)^{−1}, Σ).

On the other hand D^{(d)}F (ζ) is a multilinear operator whose entries do not depend on ζ. Moreover, since d = max{deg(f_{i}) : 1 ≤ i ≤ n}, we are sure that this multilinear operator is not identically zero. Let us use the following notation for the dense encoding of the polynomials f_{1}, …, f_{n} :

f_{i} := ∑_{|μ|≤d} a_{μ}^{(i)}\underline{X}^{μ},

where μ ∈ ℕ^{n} are multi–indices. Now, there exists some μ := (μ_{1}, …, μ_{n}) ∈ ℕ^{n}, such that |μ| = d, and some i ∈ ℕ, 1 ≤ i ≤ n, such that a_{μ}^{(i)} ≠ 0. Then, the following inequality holds :

∥\frac{D^{(d)}F (ζ)}{d!}∥_{ν} ≥ ∥\frac{μ_{1}! ⋯ μ_{n}!}{d!}∥_{ν}|a_{μ}^{(i)}|_{ν}.

As the polynomials f_{1}, …, f_{n} have integer coefficients, we know that the following also holds :

log ∥\frac{D^{(d)}F (ζ)}{d!}∥_{ν} ≥ −(d log d + h) ≥ −(d log d + w).

Thus, we conclude log γ_{ν}(F, ζ) ≥ \frac{log d_{ν}^{(F)}(DF (ζ)^{−1}, Σ)}{d − 1} − (\frac{d log d}{d − 1} + \frac{h}{d − 1}).

To prove Theorem 6 we establish the following Theorem and then derive Theorem 6 :

Theorem 31 Let f_{1}, …, f_{n} ∈ ℤ[X_{1}, …, X_{n}] be a sequence of multivariate polynomials. Let us asume that the following properties hold

• d = max{deg(f_{i}) : 1 ≤ i ≤ n} ≥ 2,

• wt(f_{i}) ≤ w, 1 ≤ i ≤ n.

Let ζ ∈ V_{K}(f_{1}, …, f_{n}) be a smooth K−rational point of the system F := (f_{1}, …, f_{n}). Let | · |_{ν} : K ⟶ ℝ_{+} be an absolute value defined on K, and let L ⊆ K be a number field such that ζ ∈ L_{ν}^{n}. Then, for every z ∈ L^{n}, z ≠ ζ satisfying

||z − ζ||_{ν}γ_{ν}(F, ζ) ≤ \frac{3 − \sqrt{7}}{2},

the following inequality holds :

ht(z) ≥ \frac{1}{2d − 1} (\frac{log γ_{ν}(F, ζ) − log(n^{2}d) − 2}{[L : ℚ]} − 2w) .

With the same assumptions also holds :

ht(z) ≥ \frac{1}{2d − 1} (\frac{log d_{ν}^{(F)}(DF (ζ)^{−1}, Σ_{ν}) − (d − 1)(log(n^{2}d^{3}) + 2)}{(d − 1)[L : ℚ]} − 3w) .

Moreover, in the case where L = ℚ[i] is the field of Gaussian rationals, the two previous lower bounds can be rewritten as :

ht(z) ≥ \frac{1}{2d − 1} (\frac{log γ_{ν}(F, ζ) − log(n^{2}d) − 2}{2} − 2w) and

ht(z) ≥ \frac{1}{2d − 1} (\frac{log d_{ν}^{(F)}(DF (ζ)^{−1}, Σ_{ν}) − (d − 1)(log(n^{2}d^{3}) + 2)}{2(d − 1)} − 3w) .

Proof.– Let us consider the Taylor expansion of F at ζ :

F (z) = ∑_{k=1}^{d} \frac{D^{(k)}F (ζ)(z − ζ)^{k}}{k!} .

The following inequality holds :

∥F (z)∥_{ν} = ∥DF (z)DF (z)^{−1}DF (ζ) ∑_{k=1}^{d} \frac{DF (ζ)^{−1}DF^{(k)}(ζ)(z − ζ)^{k}}{k!} ∥_{ν}

≤ ∥DF (z)∥_{ν}∥DF (z)^{−1}DF (ζ)∥_{ν} · (∑_{k=1}^{d}(γ_{ν}(F, ζ)∥z − ζ∥_{ν})^{k−1}) ∥ζ − z∥_{ν}

Defining u := ∥ζ − z∥_{ν}γ_{ν}(F, ζ) and ψ(u) := 2u^{2} − 4u + 1, from Proposition 29 above (cf. also Lemma 2 in [BCSS98a, p. 146] ), we conclude the following inequality :

∥F (z)∥_{ν} ≤ ∥DF (z)∥_{ν} \frac{(1 − u)u}{ψ(u)γ_{ν}(F, ζ)}.

Since \frac{(1−u)u}{ψ(u)} is increasing in the closed interval [0, \frac{3−\sqrt{7}}{2}], we have

∥F (z)∥_{ν} ≤ ∥DF (z)∥_{ν} \frac{c_{1}}{γ_{ν}(F, ζ)},

where c_{1} = \frac{4}{\sqrt{7} − 1}. By Claim iii) of Lemma 27, the following holds :

log ∥F (z)∥_{ν} ≥ −[L : ℚ](w + dht(z)),

whereas by Claim ii) of Lemma 27, we conclude that

log ∥DF (z)∥_{ν} ≤ log(n^{2}d) + [L : ℚ] ((d − 1)ht(z) + w) .

Thus, we obtain :

−[L : ℚ](w + dht(z)) ≤ log(n^{2}d) + [L : ℚ] ((d − 1)ht(z) + w) + log c_{1} − log γ_{ν}(F, ζ).

Hence we conclude :

log γ_{ν}(F, ζ) − log(n^{2}d) − 2 − 2[L : ℚ]w ≤ (2d − 1)[L : ℚ]ht(z), and

ht(z) ≥ \frac{1}{2d − 1} (\frac{log γ_{ν}(F, ζ) − log(n^{2}d) − 2}{[L : ℚ]} − 2w) .

In particular, in the case where L = ℚ[i] is the field of Gaussian rationals, we can conclude the following lower bound :

ht(z) ≥ \frac{1}{2d − 1} (\frac{log γ_{ν}(F, ζ) − log(n^{2}d) − 2}{2} − 2w) .

On the other hand, using Proposition 30, and noting that the logarithmic height of the polynomials f_{1}, …, f_{n} is bounded by the logarithmic weight, from this lower bound one easily concludes the following inequality :

ht(z) ≥ \frac{1}{2d − 1} (\frac{log d_{ν}^{(F)}(DF (ζ)^{−1}, Σ_{ν}) − (d − 1)(log(n^{2}d^{3}) + 2)}{(d − 1)[L : ℚ]} − 3w) .

In the case of L = ℚ[i], this yields the following lower bound :

ht(z) ≥ \frac{1}{2d − 1} (\frac{log d_{ν}^{(F)}(DF (ζ)^{−1}, Σ_{ν}) − (d − 1)(log(n^{2}d^{3}) + 2)}{2(d − 1)} − 3w) .

Let us remark that in these lower bounds the “positive part” is essentially log γ(F, ζ), whereas the “negative part” is always bounded by the input length. This result helps interpreting our observations on the first example given Subsection 4.2.1 below. In particular, we can conclude the validity of Theorem 6 by noting that the weight of a multivariate polynomial with integer coefficients of degree at most 2 is easily bounded in terms of its logarithmic height, namely :

wt(f_{i}) ≤ 2 log n + ht(f_{i})

It is worth observing that the same techniques also allow us to establish interesting results on the lower bound for sparse polynomials systems. This can be done in the following way :

Corollary 32 Let f_{1}, …, f_{n} ∈ ℤ[X_{1}, …, X_{n}] be a sequence of multivariate polynomials. Let us assume that the following properties hold :

• d = max{deg(f_{i}) : 1 ≤ i ≤ n} ≥ 2,

• ht(f_{i}) ≤ w, 1 ≤ i ≤ n,

• The polynomials f_{1}, …, f_{n} have at most M non–zero coefficients.

Let ζ ∈ V_{K}(f_{1}, …, f_{n}) be a smooth K−rational point of the system F := (f_{1}, …, f_{n}). Let | · |_{ν} : K ⟶ ℝ_{+} be an absolute value defined on K, and let L ⊆ K be a number field such that ζ ∈ L_{ν}^{n}. Then, for every z ∈ L^{n}, z ≠ ζ satisfying

||z − ζ||_{ν}γ_{ν}(F, ζ) ≤ \frac{3 − \sqrt{7}}{2},

the following inequality holds :

ht(z) ≥ \frac{1}{2d − 1} (\frac{log γ_{ν}(F, ζ) − log(n^{2}d) − 2}{[L : ℚ]} − 2(log M + h)) .

With the same assumptions also holds

ht(z) ≥ \frac{1}{2d − 1} (\frac{log d_{ν}^{(F)}(DF (ζ)^{−1}, Σ_{ν}) − (d − 1)(log(n^{2}d^{3}) + 2)}{(d − 1)[L : ℚ]} − 3(log M + h)) .

Moreover, in the case where L = ℚ[i] is the field of Gaussian rationals, the two previous lower bounds may be rewritten as :

ht(z) ≥ \frac{1}{2d − 1} (\frac{log γ_{ν}(F, ζ) − log(n^{2}d) − 2}{2} − 2(log M + h)) , and

ht(z) ≥ \frac{1}{2d − 1} (\frac{log d_{ν}^{(F)}(DF (ζ)^{−1}, Σ_{ν}) − (d − 1)(log(n^{2}d^{3}) + 2)}{2(d − 1)} − 3(log M + h)) .

Now we will show Proposition 7. Let us recall that statement :

Proposition 33 With the notations and assumptions introduced in Section 2, let F := (f_{1}, …, f_{n}) be a sequence of n−variate polynomials with integer coefficients defining a zero–dimensional algebraic variety V (f_{1}, …, f_{n}), and let ζ ∈ V_{K}(f_{1}, …, f_{n}) ∩ ℤ_{K}^{n} be a smooth K−rational point whose entries are algebraic integers. Let us also assume that for every archimedean absolute value | · |_{ν} (i. e. ν ∈ S), the following holds :

3∥ζ∥_{ν}γ_{ν}(F, ζ) ≥ 3 − \sqrt{7}.

Then the average height of any approximate zero z ∈ ℚ[i]^{nD} of the system F with associated variety V_{ζ} that satisfies the γ–Theorem, also satisfies the following inequality :

ht_{av}(z) ≥ \frac{1}{2} [ht(ζ) − (\frac{1}{2} log n + log 2)] .

Proof.– Let us denote by V_{ζ} ⊆ V (f_{1}, …, f_{n}) the ℚ−definable irreducible component of V (f_{1}, …, f_{n}) containing ζ. Let D := deg(V_{ζ}) and V_{ζ} := {ζ_{1}, …, ζ_{D}}. Let us write z := (z_{1}, …, z_{D}) ∈ ℚ[i]^{nD}, such that for every i, 1 ≤ i ≤ D, the following inequalities hold :

∥z_{i} − ζ_{i}∥ ≤ \frac{3 − \sqrt{7}}{2γ(F, ζ_{i})},

where ∥ · ∥ : K^{n} ⟶ ℝ is the standard hermitian norm induced by the inclusion ι : K ↪ ℂ. Thus, we conclude that for every i, 1 ≤ i ≤ D, the following inequality holds :

∥z_{i}∥ ≥ ∥ζ_{i}∥ − \frac{3 − \sqrt{7}}{2γ(F, ζ_{i})}.

Without loss of generality, let us assume that K = K(ζ) = K(V_{ζ}), and let D := [K : ℚ]. Let us also consider the class of all ℚ− embeddings of K in ℂ, i.e. σ_{1}, …, σ_{D} : K ↪ ℂ. In a slight abuse of notation, we also use σ_{1}, …, σ_{D} to denote the corresponding embeddings of the affine space K^{n} in ℂ^{n}, namely

σ_{1}, …, σ_{D} : K^{n} ↪ ℂ^{n}.

Thus, we have V_{ζ} := {σ_{1}(ζ), …, σ_{D}(ζ)}, and we may conclude that for every i, 1 ≤ i ≤ D, the following inequality holds :

∥z_{i}∥ ≥ ∥σ_{i}(ζ)∥ − \frac{3 − \sqrt{7}}{2γ(F, σ_{i}(ζ))}.  (5)

Moreover, for every i, 1 ≤ i ≤ D, there exists an archimedean absolute value ν_{i} ∈ S, such that the following two equalities hold :

• ∥ζ_{i}∥ = ∥σ_{i}(ζ)∥ = ∥ζ∥_{ν_{i}},

• γ(F, ζ_{i}) = γ(F, σ_{i}(ζ)) = γ_{ν_{i}}(F, ζ).

Our hypothesis on ζ would obviously imply for every i, 1 ≤ i ≤ D the following inequality :

∥ζ_{i}∥ − \frac{3 − \sqrt{7}}{2γ(F, ζ_{i})} ≥ \frac{1}{2}∥ζ∥_{ν_{i}}.

Thus, we conclude that for every i, 1 ≤ i ≤ D holds :

∥z_{i}∥ ≥ \frac{1}{2}∥ζ∥_{ν_{i}}.

Let us denote z_{i} := (z_{i,1}, …, z_{i,n}) ∈ ℚ[i]^{n} for every i, 1 ≤ i ≤ D. Then, we may conclude the following inequality :

\sqrt{n} max\{1, |z_{i,1}|, …, |z_{i,n}|\} ≥ \frac{1}{2}∥ζ∥_{ν_{i}},

which implies that for every i, 1 ≤ i ≤ D holds :

log (\sqrt{n} max\{1, |z_{i,1}|, …, |z_{i,n}|\}) ≥ ht_{ν_{i}}(ζ) − log 2.  (6)

This implies 2ht(z_{i})+ \frac{1}{2} log n ≥ ht_{ν_{i}}(ζ)−log 2. Adding all these quantities, we obtain the following inequality :

2 (∑_{i=1}^{D} ht(z_{i})) ≥ (∑_{i=1}^{D} ht_{ν_{i}}(ζ)) − D (\frac{1}{2} log n + log 2) ,

or equivalently, the following inequality :

2 (∑_{i=1}^{D} ht(z_{i})) ≥ (∑_{ν∈S} n_{ν}ht(ζ)) − D (\frac{1}{2} log n + log 2) .

Finally, since D = [K : ℚ] and ζ ∈ ℤ_{K}^{n}, we conclude that

ht_{av}(z) ≥ \frac{1}{2} [ht(ζ) − (\frac{1}{2} log n + log 2)] ,

as desired.

In order to illustrate the meaning of this lower bound, we give here a few Corollaries.

Corollary 34 With the same notations as in Proposition 33, let ζ ∈ ℤ_{K}^{n} ∩ V_{K}(f_{1}, …, f_{n}) be a smooth K−rational zero of the system F := (f_{1}, …, f_{n}) and let us assume that for every archimedean absolute value | · |_{ν} : K ⟶ ℝ (i. e. for every ν ∈ S), the following holds :

γ_{ν}(F, ζ) ≥ \frac{3 − \sqrt{7}}{2}.

Then the average height of any approximate zero z ∈ ℚ[i]^{nD} of the system F with associated variety V_{ζ} that satisfies the γ–Theorem, also satisfies the following inequality :

ht_{av}(z) ≥ \frac{1}{2} [ht(ζ) − (\frac{1}{2} log n + log 2)] .

Proof.– Using the same notations and steps as in the proof of the Proposition 33, we obtain the following inequalities for every i, 1 ≤ i ≤ D (cf. inequality 5) :

∥z_{i}∥ ≥ ∥ζ∥_{ν_{i}} − \frac{3 − \sqrt{7}}{2γ_{ν_{i}}(F, ζ)}.

Now, provided that ∥ζ∥_{ν_{i}} ≥ 1, since γ_{ν_{i}}(F, ζ) ≥ \frac{3−\sqrt{7}}{2}, we conclude that :

3∥ζ∥_{ν_{i}} ≥ 3 − \sqrt{7}.

Hence,

∥z_{i}∥ ≥ ∥ζ∥_{ν_{i}} − \frac{3 − \sqrt{7}}{2γ_{ν_{i}}(F, ζ)} ≥ \frac{1}{2}∥ζ∥_{ν_{i}}.

In this case, we may conclude (as in inequality 6 above) the following inequality :

log (\sqrt{n} max\{1, |z_{i,1}|, …, |z_{i,n}|\}) ≥ ht_{ν_{i}}(ζ) − log 2.

Otherwise, if ∥ζ∥_{ν_{i}} ≤ 1, the following inequality obviously holds :

log (\sqrt{n} max\{1, |z_{i,1}|, …, |z_{i,n}|\}) ≥ ht_{ν_{i}}(ζ) − log 2.

Thus, to complete the proof, one proceeds as in the proof of Proposition 7.

Moreover, the previous techniques show how to deform a given system of multivariate polynomials by means of a single additional equation of low degree in such a way that the average bit length of the new system is essentially greater than the height of the particular zero you want to approximate.

Corollary 35 Let F := (f_{1}, …, f_{n}) be a system of multivariate polynomials with integer coefficients satisfying the hypotheses i) to v) of Section 1. Let ζ = (ζ_{1}, …, ζ_{n}) ∈ ℤ_{K}^{n+1} ∩ V_{K}(f_{1}, …, f_{n}) be a smooth K−rational zero whose coordinates are algebraic integers. Let us now define the system of polynomial equations in n + 1 variables :

G := (g_{1}, …, g_{n+1}) ∈ (ℤ[X_{1}, …, X_{n+1}])^{n+1} ,

given by the following rules :

• g_{i} := f_{i} ∈ ℤ[X_{1}, …, X_{n+1}] for every i, 1 ≤ i ≤ n,

• g_{n+1} := (X_{n+1} − X_{n}) (X_{n+1} − (X_{n} + 1)) .

Let ζ′ ∈ V_{K}(g_{1}, …, g_{n+1}) ∩ ℤ_{K}^{n+1} be the affine point given by

ζ′ := (ζ_{1}, …, ζ_{n}, ζ_{n}) ∈ ℤ_{K}^{n+1}.

Let V_{ζ′} ⊆ V (g_{1}, …, g_{n+1}) be the ℚ−definable irreducible component of V (g_{1}, …, g_{n+1}) containing ζ′. Then the average height of any approximate zero z ∈ ℚ[i]^{(n+1)D} of the system F with associated variety V_{ζ′} that satisfies the γ–Theorem, also satisfies the following inequality :

ht_{av}(z) ≥ \frac{1}{2} [ht(ζ) − (\frac{1}{2} log(n + 1) + log 2)] .

Proof.– Let us consider the two affine points in V (g_{1}, …, g_{n+1}) ∩ ℤ_{K}^{n+1} given by

ζ′ := (ζ_{1}, …, ζ_{n}, ζ_{n}) ∈ ℤ_{K}^{n+1}, and ζ” := (ζ_{1}, …, ζ_{n}, ζ_{n+1}) ∈ ℤ_{K}^{n+1}.

We make use of Inequality 4 to conclude that for every archimedean absolute value ν ∈ M_{K}, the following holds :

1 = ∥ζ′ − ζ”∥_{ν} ≥ \frac{3 − \sqrt{7}}{2γ_{ν}(G, ζ′)}.

In particular, we conclude that for every archimedean absolute value ν ∈ S holds :

γ_{ν}(G, ζ′) ≥ \frac{3 − \sqrt{7}}{2}.

Now, let us assume D := deg(V_{ζ′}) = [K : ℚ] and V_{ζ′} := {ζ′_{1}, …, ζ′_{D}}. Let σ_{1}, …, σ_{D} : K ↪ ℂ be the set of ℚ−embeddings of K in ℂ and let us denote accordingly σ_{1}, …, σ_{D} : K^{n} ↪ ℂ^{n}. Then V_{ζ′} := {σ_{1}(ζ′), …, σ_{D}(ζ′)}, and for every i, 1 ≤ i ≤ D, there exists ν_{i} ∈ S such that :

• ∥ζ′_{i}∥ = ∥σ_{i}(ζ′)∥ = ∥ζ′∥_{ν_{i}} and

• γ(F, ζ′_{i}) = γ(F, σ_{i}(ζ′)) = γ_{ν_{i}}(F, ζ′).

Now, if ∥ζ′∥_{ν_{i}} ≥ 1, we obviously have

3∥ζ′∥_{ν_{i}}γ_{ν_{i}}(F, ζ′) ≥ 3 (\frac{3 − \sqrt{7}}{2}) ≥ 3 − \sqrt{7}.

Following the same steps as in the proof of Proposition 7 above, we may conclude that the following inequality holds for ∥ζ′∥_{ν_{i}} ≥ 1 (recall Inequality 6) :

log (\sqrt{n + 1} max\{1, |z_{i,1}|, …, |z_{i,n+1}|\}) ≥ ht_{ν_{i}}(ζ′) − log 2 = ht_{ν_{i}}(ζ) − log 2.

On the other hand, the same inequality also holds for ∥ζ′∥_{ν_{i}} ≤ 1. Thus, we proceed again as in the proof of Proposition 7.

4.2.1 Examples

The following examples illustrate how the previous lower bounds for the bit length of approximate zeros apply. We start with an example inspired by a classical univariate example due to M. Mignotte (cf. [Mig89]) :

Example 1 (Using log γ as in Theorem 31) Let us consider the system of multivariate polynomials F := (f_{1}, …, f_{n+1}) given by the following rules :

• f_{1} := X_{1} − 2,

• f_{i} := X_{i} − X_{i−1}^{2} for every i, 2 ≤ i ≤ n − 1,

• f_{n} := X_{n+1} − X_{n}^{2},

• f_{n+1} := X_{n+1}X_{n} − 2(X_{n−1}X_{n} − 1)^{2}.

This system F has three solutions in ℂ^{n+1}, where two of them, say ζ_{1}, ζ_{2} ∈ ℝ^{n+1}, satisfy the following inequality :

∥ζ_{1} − ζ_{2}∥ ≤ \frac{2}{2^{\frac{5·2^{n−2}}{2}}} ≤ \frac{2}{2^{2^{n−1}}} .

Thus, using Inequality 4 we may conclude :

\frac{2}{2^{2^{n−1}}} ≥ ∥ζ_{1} − ζ_{2}∥ ≥ \frac{3 − \sqrt{7}}{2γ(F, ζ_{i})}.

By the first lower bound given in Theorem 31, we conclude that for all approximate zeros z_{1}, z_{2} ∈ ℚ[i]^{n+1} of the system F associated to ζ_{1}, ζ_{2} respectively and satisfying the corresponding γ−Theorem, the following holds :

ht(z_{i}) ≥ \frac{1}{6} (log γ(F, ζ_{i}) − 2 log(n + 1)) − O(1) ≥ \frac{1}{6} (2^{n−1} − 2 log(n + 1)) − O(1).

and that they require exponential bit length, both for binary or continuous fraction encodings. Floating point encoding also requires an exponential number of digits. Let us observe that alternative examples with low separation between the roots can be easily obtained without using Mignotte’s example. Consider for example the following system F := (f_{1}, …, f_{n}) given by :

• f_{1} := 2X_{1} − 1,

• f_{i} := X_{i} − X_{i−1}^{2}, for every i, 2 ≤ i ≤ n − 1,

• f_{n} := X_{n}(X_{n} − X_{n−1}).

This system has two distinct solutions ζ_{1} ≠ ζ_{2} at a distance ∥ζ_{1} − ζ_{2}∥ ≤ \frac{1}{2^{2^{n−2}}} , and the same lower bound applies.

Example 2 (Using log d^{(F)}(DF (ζ)^{−1}, Σ) as in Theorem 31) Let us consider the system of multivariate polynomial equations F := (f_{1}, …, f_{n+1}) given by the following rules :

• f_{1} := X_{n+1}(2X_{1} − 1),

• f_{i} := X_{n+1}(X_{i} − X_{i−1}^{2}), for every i, 2 ≤ i ≤ n,

• f_{n+1} := X_{n+1}^{2} − X_{n}^{2}.

We consider the solution of this system given by :

ζ := (\frac{1}{2}, \frac{1}{2^{2}} , …, \frac{1}{2^{2^{n−1}}} , \frac{1}{2^{2^{n−1}}} ) .

Thus, we consider the jacobian matrix of the system F at ζ, i.e.

DF (ζ) := (\frac{∂f_{i}}{∂X_{j}} (ζ))_{1≤i,j≤n+1} .

The entries of this non–singular matrix are given by the following rules :

If j = i ≤ n,  \frac{∂f_{i}}{∂X_{j}} (ζ) = \frac{1}{2^{2^{n−1}}} ,
if 1 ≤ j = i − 1, i ≤ n, \frac{∂f_{i}}{∂X_{j}} (ζ) = \frac{−2}{2^{2^{n−1}+2^{j−1}}} ,
if j = n, i = n + 1,  \frac{∂f_{n+1}}{∂X_{n}} (ζ) = \frac{−2}{2^{2^{n−1}}} ,
if j = i = n + 1,  \frac{∂f_{n+1}}{∂X_{n+1}} (ζ) = \frac{2}{2^{2^{n−1}}} ,
and otherwise  \frac{∂f_{i}}{∂X_{j}} (ζ) = 0.

We conclude that : ∥DF (ζ)∥ ≤ ∥DF (ζ)∥^{(F)} ≤ \frac{2(n + 1)^{2}}{2^{2^{n−1}}} .

Thus holds : \frac{2^{2^{n−1}}}{2(n + 1)^{2}} ≤ \frac{1}{∥DF (ζ)∥} = d^{(F)}(DF (ζ^{−1}, Σ).

Now, using the lower bound shown in Theorem 31 with d = 3, w = log 3 and n = n+1, we conclude that for every z ∈ ℚ[i]^{n+1} satisfying the γ−Theorem with associated zero ζ, the following inequality holds :

ht(z) ≥ \frac{1}{20} (2^{n−1} − 6 log(n + 1)) − 2.

As mentioned in the Introduction, the same comments also show the validity of Main Theorem 1.

Example 3 (Using Proposition 7 or Corollary 35) Consider the following sequence of multivariate polynomials F := (f_{1}, …, f_{n+1}) given by the following rules :

• f_{1} := X_{1} − 2,

• f_{i} := X_{i} − X_{i−1}^{2}, for every i, 2 ≤ i ≤ n,

• f_{n+1} := (X_{n+1} − X_{n}) (X_{n+1} − (X_{n} + 1)).

This system has two solutions ζ_{1}, ζ_{2} ∈ ℤ^{n+1}, which can be described as follows :

ζ_{1} := (2, 2^{2}, …, 2^{2^{n−1}}, 2^{2^{n−1}}) ∈ ℤ^{n+1} and ζ_{2} := (2, 2^{2}, …, 2^{2^{n−1}}, 1 + 2^{2^{n−1}}) .

By Inequality 4, we may conclude that for i = 1, 2 holds :

1 := ∥ζ_{1} − ζ_{2}∥ ≥ \frac{3 − \sqrt{7}}{2γ(F, ζ_{i})}.

In particular, since 3∥ζ_{i}∥γ(F, ζ_{i}) ≥ 3 − \sqrt{7}, we may apply either Corollary 35 or Proposition 7 to conclude that for every z_{1}, z_{2} ∈ ℚ[i]^{n+1} satisfying the γ−Theorem with associated zero ζ_{1} and ζ_{2} respectively, the following holds :

ht(z_{i}) ≥ \frac{1}{2} [2^{n−1} − log(n + 1) − log 2] .

Again, Main Theorem 1 follow from this example.

4.3 Approximate zero theory : Upper bounds for the bit length of approximate zeros

Here we show the statements of the Introduction concerning upper bounds for the bit length of approximate zeros. We start with the following statement and then show Theorem 8 of Section 2.

Theorem 36 (Upper bounds for γ(F, ζ)) Let f_{1}, …, f_{n} ∈ ℤ[X_{1}, …, X_{n}] be polynomials with integer coefficients. Let us assume that the following properties hold

• d := max{deg(f_{i}) : 1 ≤ i ≤ n},

• wt(f_{i}) ≤ w, 1 ≤ i ≤ n.

Let ζ ∈ V_{K}(f_{1}, …, f_{n}) be a smooth K−rational point. Let | · |_{ν} : K ⟶ ℝ_{+} be an absolute value on K. Thus, the following inequality holds :

log γ_{ν}(F, ζ) ≤ [K : ℚ](t + 1) (t^{2} + 8 log t + 2w + tht(ζ)) ,

where t := max{d, n} ≥ 2.

Proof.– First of all, using Claim iv) of Lemma 26, the following inequality holds :

γ_{ν}(F, ζ) ≤ max_{k≥2} (∥(DF (ζ))^{−1}∥_{ν} ∥\frac{D^{(k)}F (ζ)}{k!}∥_{ν})^{\frac{1}{k−1}} .

By Claim v) of Lemma 26, the following holds :

∥DF (ζ)^{−1}∥_{ν} = \frac{1}{d_{ν}^{(F)}(DF (ζ, Σ)} ≤ \frac{∥DF (ζ)∥_{ν}^{n−1}}{| det(DF (ζ)|_{ν}} .

By Claim iii) of Lemma 27, we obtain :

log | det(DF (ζ))|_{ν} ≥ −[K : ℚ]n (log n + ht(DF (ζ))) .

Now, using Lemma 25, we have :

ht(DF (ζ)) ≤ n^{2} + max\{ht (\frac{∂f_{i}}{∂X_{j}} (ζ)) : 1 ≤ i, j ≤ n\}.

Thus, we may use Claim i) of Lemma 27 to conclude :

max\{ht (\frac{∂f_{i}}{∂X_{j}} (ζ)) : 1 ≤ i, j ≤ n\} ≤ w + log d + (d − 1)ht(ζ).

This chain of inequalities yields :

− log | det(DF (ζ)|_{ν} ≤ [K : ℚ]n (n^{2} + log n + w + log d + (d − 1)ht(ζ)) .

On the other hand, using Claim ii) of Lemma 27, we have :

log ∥DF (ζ)∥_{ν} ≤ log(n^{2}d) + [K : ℚ] (w + (d − 1)ht(ζ)) .

Moreover, using Claim iii) of Lemma 26, we obtain :

log ∥\frac{D^{(k)}F (ζ)}{k!}∥_{ν} ≤ (k + 1) log n

+[K : ℚ] max\{ht (\frac{1}{k!} \frac{∂^{|μ|}f_{i}}{∂\underline{X}^{μ}} (ζ)) : μ ∈ ℕ^{n}, |μ| = k, 1 ≤ i ≤ n\}.

Now, using Claim i) of Lemma 27, we conclude that for every multi–index μ ∈ ℕ^{n}, |μ| = 1 and for every i, 1 ≤ i ≤ n, the following holds :

ht (\frac{1}{k!} \frac{∂^{|μ|}f_{i}}{∂\underline{X}^{μ}} (ζ)) ≤ k log k + d log d + w + (d − 1)ht(ζ).

Thus, adding all these quantities, we obtain :

log ∥\frac{D^{(k)}F (ζ)}{k!}∥_{ν} ≤ [K : ℚ] (2(d + 1) log n + 2d log d + w + (d − 1)ht(ζ)) .

Thus, taking t := max{d, n} ≥ 2, we conclude :

log γ_{ν}(F, ζ) ≤ ([K : ℚ] (4(t + 1) log t + w + (t − 1)ht(ζ)) − log d_{ν}^{(F)}(DF (ζ)^{−1}, Σ))) .

Finally, combining all upper bounds above, we may conclude :

log γ_{ν}(F, ζ) ≤ [K : ℚ](t + 1) (t^{2} + 8 log t + 2w + tht(ζ)) .

Theorem 37 (Lower bounds for γ) With the same assumptions and notations as in Theorem 36 above, the following holds :

log γ_{ν}(F, ζ) ≥ − (\frac{3}{d − 1}) [K : ℚ](log n + w + d^{2}(ht(ζ))).

Proof.– First of all, the following obvious inequality holds :

γ_{ν}(F, ζ) ≥ \frac{∥D^{(d)}F (ζ)∥ν^{\frac{1}{d−1}}}{∥DF (ζ)∥ν^{\frac{1}{d−1}}} .

From Lemma 27, Claim ii) the following holds :

−\frac{1}{d − 1} log ∥DF (ζ)∥ ≥ \frac{−1}{d − 1} log(n^{2}d) + [K : ℚ](w + (d − 1)ht(ζ)).

From Lemma 27, Claim iii) we also have :

log ∥D^{(d)}F (ζ)∥ ≥ −[K : ℚ](d log d + w + dht(ζ))

Combining both inequalities we conclude the inequality claimed above.

Remark 38 Using [BCSS98a, Proposition 3, p. 50] the previous upper and lower bounds may also be written in the terms of the height of the approximate zero. With the same notations and assumptions as in Theorem 36 let z ∈ ℚ[i]^{n} be an approximate zero of system F satisfying the following inequality :

∥z − ζ∥_{ν} ≤ \frac{3 − \sqrt{7}}{2γ_{ν}(F, ζ)}

First of all, the following two inequalities hold :

log γ_{ν}(F, z) ≤ ((t + 1) (t^{2} + 8 log t + 2w + tht(z))) ,

log γ_{ν}(F, z) ≥ − (\frac{3}{d − 1}) 2(log n + w + d^{2}(ht(z)))

where t := max{d, n} ≥ 2. Now, we apply [BCSS98a, Proposition 3, p. 50] to conclude :

log γ_{ν}(F, ζ) ≤ c log γ_{ν}(F, z) ≤ c′ log γ_{ν}(F, ζ),

where c, c′ > 0 are universal constants. In particular, we also conclude the following lower bound for the height of the approximate zero :

ht(z) ≥ Ω (\frac{log γ_{ν}(F, ζ) − (t + 1)(t^{2} + 8 log t + 2w)}{t(t + 1)}) .

Let us observe the analogies between this lower bound and those stated in Theorem 6.

Once again, we can conclude the validity of Theorem 8 as given in the Introduction, since it is a particular case of the Theorem above. Now we are in condition to show Corollary 9 of Section 2. Let us recall that statement :

Corollary 39 (Upper bound on the bit length of approximate zeros) With the same assumptions and notations as in Theorem 8, let ζ ∈ V_{K}(f_{1}, …, f_{n}) be a smooth K−rational zero, and let | · |_{ν} be an absolute value on K. Let L ⊆ K be a number field such that ζ ∈ L_{ν}^{n}. Then there exist approximate zeros z ∈ L^{n} of the system F := (f_{1}, …, f_{n}) with approximate zero ζ with respect to the absolute value | · |_{ν}, such that the logarithmic height ht(z) of z is at most linear in the following quantities :

\frac{1}{[L : ℚ]} log |Δ_{L}| + [K : ℚ]t (t^{2} + w + tht(ζ)) ,

where w is an upper bound for the logarithmic weight of the polynomials f_{1}, …, f_{n}, t := max{d, n}, and |Δ_{L}| is the absolute value of the discriminant of the field L. Moreover, in the case where L = ℚ[i] (for instance, if |·|_{ν} is archimedean), there exist approximate zeros z ∈ ℚ[i]^{n} for the system F with associated zero ζ with respect to | · |_{ν}, such that their bit length is at most linear in the following quantity :

[K : ℚ]t (t^{2} + w + tht(ζ)) ,

in other words :

ht(z) ≤ c_{1}[K : ℚ]t (t^{2} + w + tht(ζ)) .

where c_{1} > 0 is a small universal constant.

This statement follows immediately from the upper bounds for γ_{ν}(F, ζ) described in Theorem 36 above, together with the following two statements on the classical Dirichlet Theorem. The first statement is an extension of the classical Dirichlet Theorem to the case of archimedean absolute values (cf. [Sch80, Cas97] for instance) :

Theorem 40 (Archimedean Dirichlet Theorem, 1842) Suppose given n·m real numbers α_{ij} (1 ≤ i ≤ n, 1 ≤ j ≤ m) and that Q > 1 is an integer. Then, there exist integers q_{1}, …, q_{m}, p_{1}, …, p_{n} with :

1 ≤ max(|q_{1}|, …, |q_{m}|) < Q^{\frac{n}{m}} ,

|α_{i1}q_{1} + … + α_{im}q_{m} − p_{i}| ≤ \frac{1}{Q} (1 ≤ i ≤ n).

On the other hand, for non–archimedean absolute values, we made use of the following statement. A proof can be found in [BVdPV96] or [Tyl94].

Theorem 41 (Non–archimedean Dirichlet Theorem) Let K be a number field and ν ∈ M_{K}\ S a non–archimedean absolute value defined on K. Let ζ ∈ K_{ν} be a point in the completion of K with respect to | · |_{ν}. Then, for every τ ∈ K_{ν} , 1 ≤ |τ|_{ν}, there exists z ∈ K, such that the following holds :

i) ht(z) ≤ \frac{1}{2[K : ℚ]} log |Δ_{L}| + log |τ|_{ν} + log c,

ii) |ζ − z|_{ν} ≤ \frac{|Δ_{K}|^{\frac{1}{2[H : ℚ]}} e^{c+ht(ζ)}}{|τ|_{ν}} .

Thus, taking either sufficiently big denominators (for the archimedean case) or τ such that |τ|_{ν} is big enough (for the non–archimedean case), Corollary 9 follows. To conclude the statements claimed at the Introduction, let us say that the Universal γ−Theorem (Corollary 11 stated at the Introduction) follows obviously as a consequence of Theorem 4 and the universal condition number is well–defined as a consequence of Theorem 36 above. Finally, we have to prove Corollary 12. We recall that statement from Section 2 :

Corollary 42 Let F := (f_{1}, …, f_{n}) be a sequence of multivariate polynomials with integer coefficients satisfying hypotheses i) to v) stated in the Introduction. Let ζ ∈ V_{K}(f_{1}, …, f_{n}) a smooth K−rational zero. The only point z ∈ K^{n} which satisfies the Universal γ−Theorem near γ for all absolute values in M_{K} is z = ζ. Namely, for every z ∈ K^{n} satisfying for every ν ∈ M_{k} the following inequality

∥z − ζ∥_{ν} ≤ \frac{3 − \sqrt{7}}{2γ̃(F, ζ)}

holds z = ζ.

Proof.– First, let us consider z ∈ K^{n}, such that for every absolute value ν ∈ M_{K} holds :

∥z − ζ∥_{ν} ≤ \frac{3 − \sqrt{7}}{2γ̃(F, ζ)}.

As γ̃(F, ζ) ≥ 1, we easily conclude that for all non–archimedean absolute values ν ∈ M_{K} \ S holds ∥z − ζ∥_{ν} ≤ 1. In particular, the coordinates of the affine point z − ζ are algebraic integers in K, i.e. z − ζ ∈ ℤ_{K}^{n}. On the other hand, for archimedean absolute values holds ∥z − ζ∥_{ν} ≤ 1, and hence, we obtain :

e^{ht(z−ζ)} ≤ (∏_{ν∈S} ∥z − ζ∥_{ν}^{n_{ν}} )^{\frac{1}{[K : ℚ]}} < 1.

This last condition can only be satisfied if z − ζ = 0 ∈ K^{n}, and thus the claim follows.

5 Kronecker’s approach to solving

In this Section we prove Theorems 15 and 16 as stated in the Introduction. To this end, we have divided this Section into three main parts.

• An improvement of the Witness Theorem. In this Subsection we introduce some standard notations concerning straight–line programs encoding of multivariate polynomials. We also show an improvement of the Witness Theorem of [BCSS98b, BCSS98a] using parallel complexity estimates.

• From Kronecker’s to Newton’s solution. In this Subsection we show Theorem 16. In fact, using the main statement of [GHMP95, Par95, GHM^{+}98, GHH^{+}97, GHMP97], this Theorem is established by exhibiting a procedure that transforms a Kronecker description of a solution variety into a list of approximates zeros of bounded height.

• From Newton’s to Kronecker’s solution. In this Subsection we show Theorem 15, exhibiting a procedure that transforms approximate zeros into a Kronecker description of a certain ℚ–definable irreducible component of a solution variety.

5.1 An improvement of the Witness Theorem

In the sequel we will work with the complexity model of non–scalar straight–line programs (see for instance [Hei89, Str90, Par95, MPR91] or [KP96]) : a non–scalar straight–line program is a structure which evaluates (and hence represents) a given polynomial of K[X_{1}, …, X_{n}], taking K–linear operations for free.

Remark 43 We shall tacitly assume that our straight–line programs do not contain any divisions.

We represent a straight–line program for the evaluation of a polynomial P ∈ K[X_{1}, …, X_{n}] by a directed acyclic graph G whose nodes are labeled gates which perform arithmetical operations. Therefore we identify the nodes of G with the corresponding gates. The graph G disposes of n + 1 particular nodes labelled by the variables X_{1}, …, X_{n} and the constant 1. These nodes are called the input gates of G. We define the depth of a gate ν of our graph as the length of the longest path which joins ν with some input gate. Let us denote the gates of the directed acyclic graph by pairs of integer numbers (i, j), where i represents the depth of the gate and j is the corresponding value of an arbitrary numbering imposed to the set of gates of depth i (this notation for the analysis of parallel complexity has been inspired by [MP93] and [MMP96]).

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

i = 0 : Q_{0,1} := 1 , Q_{0,2} := X_{1} , …, Q_{0,n+1} := X_{n}

1 ≤ i ≤ ℓ : Q_{i,j} := ( ∑_{{r≤i−1 \atop 1≤s≤Lr}} A_{i,j}^{r,s} Q_{r,s}) · ( ∑_{{r′≤i−1 \atop 1≤s′≤L_{r′}}} B_{i,j}^{r′,s′} Q_{r′,s′})

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

Observe that the rather complicated notation in Definition 44 (non–scalar straight–line program ) arises from the fact that a single non–scalar node in the graph represents the total of all scalar (i.e. K–linear) operations contributing to this node. Let us mention that in our notation the sub–indices i, j of the parameters A_{i,j}^{r,s} and B_{i,j}^{r′,s′} represent the gate of the multiplication they are assigned to and the super–indices r, s correspond to the previous result they involve in the multiplication. We abbreviate \underline{A} = (A_{i,j}^{r,s}) and \underline{B} = (B_{i,j}^{r′,s′}). Semantically speaking the straight–line program Γ defines an evaluation algorithm of the polynomials (intermediate results) :

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

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

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

Taking into account the representation of (7) we can rewrite Identity (8) as :

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

for all μ with |μ| ≤ 2^{i} and P_{μ} = 0 for |μ| > 2^{i}. Let us remark that the degree of such a polynomial P = Q_{i,j}(\underline{α}, \underline{β}, X_{1}, …, X_{n}) is generically equal to 2^{i} in the space of parameters. Finally, we say that P ∈ K[X_{1}, …, X_{n}] is computable by a straight–line program Γ with parameters in the finite set F := {α_{ij}^{rs}, β_{ij}^{r′s′}}. Here we resume how these notions and the logarithmic height (Subsection 3.1.3) relate, by establishing bounds for polynomials given by straight–line programs using the different notions of height. First of all, we can easily bound the number of parameters used by a non–scalar straight–line program Γ of size L in n variables by 2L(L − (n + 1)). The following Lemma relates the notions of height and weight with the notions of size, non–scalar depth and height of the parameters used in a straight–line program.

Lemma 45 ([HMPS]) Let Γ be a non–scalar straight–line program over K of size L, non–scalar depth ℓ and parameters in a finite set F ⊆ K that evaluates a polynomial P ∈ K[X_{1}, …, X_{n}]. Then, we have the following inequality.

ht(P) ≤ wt(P) ≤ (2^{ℓ+1} − 2)(log L + ht(F)).

Moreover, for a given \underline{x} = (x_{1}, …, x_{n}) ∈ K^{n} we have the following upper bound:

ht(P (\underline{x})) ≤ (2^{ℓ+1} − 2) (log L + ht(F) + ht(\underline{x})) .

We start with the proof of an improvement of the Witness Theorem of [BCSS98b] and [BCSS98a]. A witness is a point where any non–zero polynomial will not vanish. The main problem will be given a non–zero polynomial, show explicitely a witness. This can be performed by a procedure based on repeated squaring (Kronecker’s scheme). In fact, this idea of using an explicit witness by repeated squaring for zero tests of polynomials goes back to Kronecker and can also be found in [HS82]. Here we discuss the effect of the depth, using some of the statements described in Subsections 3.1.3 and the Lemma 45 above.

Definition 46 A witness for a polynomial P ∈ K[X_{1}, …, X_{n}] is a point \underline{ω} ∈ K^{n} such that P (\underline{ω}) = 0 implies P = 0.

In other words, a witness is a point \underline{ω} ∈ K^{n} from the set of K–rational points V_{K}(P) of the hypersurface V (P) (if any). There exist several methods for finding such a point, here we insist on the idea of explicit exhibition of such a witness in terms of the complexity of the given polynomial P.

Theorem 47 (Theorem Witness) Let P ∈ K[X_{1}, …, X_{n}] be a non–zero polynomial evaluable by a non–scalar straight–line program Γ of size L, non–scalar depth ℓ and parameters in F ⊆ K. Let ω_{0} ∈ K be such that the following holds :

ht(ω_{0}) ≥ max{log 2, ht(F)}.

Let N ∈ ℕ be a non–negative integer such that

log N > log(ℓ + 1) + (ℓ + 2)(log 2) (log log(4L)) .

Let us define recursively the following sequence of algebraic numbers (Kronecker’s scheme) :

ω_{1} = ω_{0}^{N},

and for every i, 2 ≤ i ≤ n, let us define

ω_{i} = ω_{i−1}^{N}.

Then, the point \underline{ω} := (ω_{1}, …, ω_{n}) ∈ K^{n} is a witness for P (i.e. P (\underline{ω}) ≠ 0).

Proof.– Before giving the arguments (very close to those in [HS82] and [BCSS98a]), we have to introduce some additional notations. Let Γ be a non–scalar straight–line program of size L, depth ℓ with input variables \underline{X} := (X_{1}, …, X_{n}). Let P ∈ K[X_{1}, …, X_{n}] be a polynomial evaluable by the straight–line program Γ with parameters in F ⊆ K. Let us also assume the following dense encoding for P :

P := ∑_{\underline{μ}} P\underline{μ} \underline{X}\underline{μ}.

For every 0 ≤ j ≤ n and every affine point \underline{ω} := (ω_{1}, …, ω_{n}) ∈ K^{n}, we consider the polynomials

P (j) ; \underline{ω} := ∑_{\underline{μ}∈ℕ^{n}} P\underline{μ} ω_{1}^{μ_{1}} ⋯ ω_{j}^{μ_{j}} X_{j+1}^{μ_{j+1}} ⋯ X_{n}^{μ_{n}} ∈ K[X_{j+1}, …, X_{n}],

where P\underline{μ} ∈ K. Let us observe that P (0) ; \underline{ω} = P ∈ K[X_{1}, …, X_{n}], whereas P (n) ; \underline{ω} = P (\underline{ω}) ∈ K. We

shall apply induction on n, starting from P (0) ; \underline{ω} and ending at P (n) ; \underline{ω}. In order to perform this inductive argument we need a list of polynomials to go from step j to step j + 1. Roughly speaking, this list of polynomials are the coefficients of P (j) ; \underline{ω} as element in K[X_{j+1}][X_{j+2}, … X_{n}]. More precisely, for every 0 ≤ j < n, every \underline{ω} ∈ K^{n} and every multi–index \underline{α} := (α_{j+1}, …, α_{n}) ∈ ℕ^{n−j} we introduce the following univariate polynomials :

P_{\underline{α},\underline{ω}}^{(j,j+1)} := ∑_{\underline{μ}∈ℕ^{n}} P\underline{μ} ω_{1}^{μ_{1}} ⋯ ω_{j}^{μ_{j}} X_{j+1}^{α_{j+1}} ∈ K[X_{j+1}].

The following identity relates polynomials P_{\underline{α},\underline{ω}}^{(j,j+1)} and polynomials P (j) ; \underline{ω} :

P (j) ; \underline{ω} = ∑_{\underline{α}∈ℕ^{n−j}} P_{\underline{α},\underline{ω}}^{(j,j+1)}(X_{j+1})X_{j+2}^{α_{j+2}} ⋯ X_{n}^{α_{n}}.

Moreover, as the coefficients in K of P_{\underline{α},\underline{ω}}^{(j,j+1)} are some of the coefficients in K of P (j) ; \underline{ω} we obviously conclude from Lemma 45 the following inequalities :

ht(P_{\underline{α},\underline{ω}}^{(j,j+1)}) ≤ ht(P (j) ; \underline{ω}) ≤ (2^{ℓ+1} − 1) (log L + ht(F) + ht(ω_{1}, …, ω_{j})) .

We are now in condition to prove Theorem 47 by an inductive argument on the number n of variables involved. This proof is strongly based on the following Lemma. With the previous notations and assumptions, let ω_{0} ∈ K be such that

ht(ω_{0}) ≥ max{log 2, ht(F)}.

Let us recursively define the following algebraic numbers

ω_{1} := ω_{0}^{N} and ω_{j+1} := ω_{j}^{N}, for every j, 2 ≤ j ≤ n − 1,

where N ∈ ℕ verifies the following inequality N > ((ℓ + 1) + 2^{ℓ+2} log(4L)) . Finally, let \underline{ω} ∈ K^{n} be the affine point \underline{ω} := (ω_{1}, …, ω_{n}) ∈ K^{n}.

Lemma 48 With the previous notations, for every j, 0 ≤ j < n, and for every multi–index \underline{α} ∈ ℕ^{n−j}, if P_{\underline{α},\underline{ω}}^{(j,j+1)} ∈ K[X_{j+1}] is a non–zero polynomial, then holds :

P_{\underline{α},\underline{ω}}^{(j,j+1)}(ω_{j+1}) ≠ 0.

Assuming that this Lemma is true, the proof of Theorem 47 runs as follows. If P := P (0) ; \underline{ω} ∈ K[X_{1}, …, X_{n}] is a non–zero polynomial, then there exists some non–zero coefficient P_{\underline{α},\underline{ω}}^{(0,1)} ∈ K[X_{1}], which is a non–zero univariate polynomial. Then, by the Claim above, we have P_{\underline{α},\underline{ω}}^{(0,1)}(ω_{1}) ≠ 0. Thus, the polynomial P (1) ; \underline{ω} ∈ K[X_{2}, …, X_{n}] has as coefficients the list

P (1) ; \underline{ω} = ∑_{\underline{α}} P_{\underline{α},\underline{ω}}^{(0,1)}(ω_{1})X_{2}^{α_{2}} ⋯ X_{n}^{α_{n}}.

In particular, the polynomial P (1) ; \underline{ω} is a non–zero polynomial and it has a non–zero coefficient

P_{\underline{α},\underline{ω}}^{(1,2)} ∈ K[X_{2}].

The same argument, using the Lemma above, shows that P (2) ; \underline{ω} ∈ K[X_{3}, …, X_{n}] is a non–zero polynomial. Inductively, we obtain P (\underline{ω}) := P (n) ; \underline{ω} ∈ K as a non–zero polynomial and the statement claimed is proved.

Thus, to conclude the proof, we will have to prove Lemma 48 introduced above.

Proof.– [of Lemma 48] First of all, we recall the following inequalities.

• N > ((ℓ + 1) + 2^{ℓ+2} log(4L))

• ht(P_{\underline{α},\underline{ω}}^{(j,j+1)}) ≤ ht(P (j) ; \underline{ω}) ≤ (2^{ℓ+1} − 1) (log L + ht(F) + ht(ω_{1}, …, ω_{j}))

• For every ν ∈ M_{K} holds max{0, log |ω_{1}|_{ν}, …, log |ω_{j}|_{ν}} = max{0, log |ω_{j}|_{ν}}.

• Thus, we have ht(ω_{1}, …, ω_{j}) ≤ ht(ω_{j}).

Hence, we conclude that ht(F) + ht(ω_{1}, …, ω_{j}) ≤ 2ht(ω_{j}), and by Lemma 45, we conclude the following inequality :

ht(P_{\underline{α},\underline{ω}}^{(j,j+1)}) ≤ ht(P (j) ; \underline{ω}) ≤ (2^{ℓ+1} − 2) (log L + 2ht(ω_{j})) .

Moreover, we have the following inequality : log deg(P_{\underline{α},\underline{ω}}^{(j,j+1)}) ≤ ℓ log 2 ≤ ℓht(ω_{j}). By virtue of Corollary 24, if P_{\underline{α},\underline{ω}}^{(j,j+1)} ≠ 0, the following inequality holds for every ζ ∈ K satisfying P_{\underline{α},\underline{ω}}^{(j,j+1)}(ζ) = 0 :

ht(ζ) ≤ ((ℓ + 1) + 2^{ℓ+2} log(4L)) ht(ω_{j}) < Nht(ω_{j}) = ht(ω_{j+1}).

In particular, if P_{\underline{α},\underline{ω}}^{(j,j+1)} is not the zero polynomial, we have as desired :

P_{\underline{α},\underline{ω}}^{(j,j+1)}(ω_{j+1}) ≠ 0.

Now, as a final comment to conclude the proof : The lower bound of the statement of Theorem 47 above, log_{2} N > log_{2}(ℓ + 1) + (ℓ + 2)(log 2) (log log(4L)) obviously implies the lower bound used to prove Lemma 48, i.e. N > ((ℓ + 1) + 2^{ℓ+2} log(4L)) .

In order to transform Theorem 47 above into a deterministic procedure, we just have to observe that the number of parameters used by a non–scalar straight–line program Γ of size L is at most 2L^{2}. Thus, we conclude the following Corollary :

Corollary 49 Let P ∈ K[X_{1}, …, X_{n}] be a non–zero polynomial evaluable by a non–scalar straight– line program Γ of size L, non–scalar depth ℓ and parameters in F := {x_{1}, …, x_{r}} ⊆ K. Let ω_{−1} ∈ K be such that

ht(ω_{−1}) := max{log 2, ht(x_{1}), …, ht(x_{r})}.

Let us define ω_{0} ∈ K as ω_{0} := ω_{−1}^{2L^{2}}. Let N ∈ ℕ be a non–negative integer such that

log N > log(ℓ + 1) + (ℓ + 2)(log 2) (log log(4L)) .

Let us define recursively the following sequence of algebraic numbers (Kronecker’s scheme) :

ω_{1} = ω_{0}^{N},

and for every i, 2 ≤ i ≤ n, let us define ω_{i} = ω_{i−1}^{N}. Then, the point \underline{ω} := (ω_{1}, …, ω_{n}) ∈ K^{n} is a witness for P (i.e. P (\underline{ω}) ≠ 0).

Remark 50

i) The procedure described in Corollary 49 above for choosing ω_{−1} can be improved in several obvious cases. For instance, if K = ℚ and F ⊆ ℤ, the same assertion holds taking ω_{0} = ω_{−1}.

ii) Theorem 47 above is an improvement of the previous established requirements for N. In [BCSS98b, BCSS98a] the authors showed a lower bound for N of the order :

log N > 4nL^{2} + 4L,

which is less sharp than log N > log(ℓ + 1) + (ℓ + 2)(log 2) (log log(4L)).

iii) The general dense case. For generically many polynomials P ∈ K[X_{1}, …, X_{n}] of degree at most d, the optimal straight–line program is of size

L = \binom{d + n}{n}

and non–scalar depth of order ℓ = log d + O(1). The parameters of this straight–line program are the coefficients of P. Our Theorem 47 says that there exists a (small) universal constant c_{2} > 1, such that the requirement for selecting the non– negative integer N in Kronecker’s scheme is just the one described by the following inequality :

log N > c_{2}n log^{2} d.

Previous requirements were of order log N > 4n\binom{d + n}{n}^{2} + 4\binom{d + n}{n}. iv) The sparse/fewnomial case. Let us assume the our polynomial P ∈ K[X_{1}, …, X_{n}] has

very few terms with non–zero coefficients (i.e. P is sparse as much as it is a fewnomial). Let us assume that P has degree at most d and also that at most M of its terms have non– zero coefficients. Among the fewnomials of this class the (generically) optimal non–scalar straight–line program that evaluates P has size of order L = c_{3}Md (where c_{3} > 0 is a universal constant), and depth log_{2} d + O(1). Once again, the parameters are the non–zero coefficients of the non–zero terms of P. Thus, Theorem 47 above says that there exists a (small) universal constant c_{3} > 1, such that the only requirement for selecting the non– negative integer N in Kronecker’s scheme is the following one :

log N > c_{3} log d (log log d + log log M) .

Previous estimates were of order log N > 4n (c_{3}Md)^{2} + 4c_{3}Md.

5.2 Factoring polynomials given by straight–line programs.

Factoring univariate polynomials given by straight–line program encoding has been subject of research since the eighties. An excellent reference list can be found in the works of E. Kaltofen ([Kal90, Kal92]). However, we have not found any reference related to the subject described above : computing just those irreducible factors of “a priori” bounded height. Thus, we have to develop this subject here. We establish the following technical statement :

Theorem 51 There exists a bounded error probabilistic Turing machine M that performs the following task : Given as input for M :

• a univariate polynomial f ∈ ℤ[T] with integer coefficients given by straight–line program encoding, and

• a positive integer number H ∈ ℕ given in binary encoding,

the output of M is a list of irreducible polynomials {f_{1}, …, f_{s}} ⊂ ℤ[T], such that the following holds :

• ∏_{i=1}^{s} f_{i} divides f,

• wt(f_{i}) ≤ log_{2}(d + 1) + H for every i, 1 ≤ i ≤ s, and

• for every irreducible factor g of f, the following holds : either wt(g) > H or g ∈ {f_{1}, …, f_{s}}.

The running time of M is polynomial in :

d L H η,

where d = deg(f), L is the size of the straight–line program Γ that evaluates the coefficients of f, and η is an upper bound for the bit length of the integer parameters used by Γ.

The proof of this Theorem is divided into four main tasks which are essentially the usual four steps in any univariate polynomial factoring procedure :

1) Choosing a ”good” prime number,

2) efficient factoring modulo this prime number,

3) Newton–Hensel lifting, and

4) a modified L^{3} basis reduction algorithm.

Now we proceed to describe these four tasks. The notations introduced above will be used in the remaining parts of this description.

Task 1: Choosing a “good” prime number

Lemma 52 There exists a bounded error probability Turing machine M_{1} that performs the following task. The input of M_{1} is a polynomial f ∈ ℤ[T] given as in Theorem 51 above. The output of M_{1} is a prime number p ∈ ℕ, such that the following properties hold :

• the leading coefficient of f is non–zero in ℤ/pℤ, and

• the polynomial f̄ ∈ ℤ/pℤ[T] obtained from f by taking residues module p is squarefree.

The running time of M_{1} is polynomial in the following quantities :

d L η,

where d = deg(f), L is the length of the straight–line program Γ encoding the coefficients of f, and η is an upper bound of the logarithmic height of the parameters used by Γ.

Proof.– This Lemma follows by an strategy similar to that used in [IM83]. More precisely, we combine the Prime Number Theorem (cf. [Ros94], for instance) with the upper bounds shown in Lemma 45. First of all, let us write f as f = a_{d}T^{d} + … + a_{0}, where a_{i} ∈ ℤ for every i, 0 ≤ i ≤ d. Let us assume that the straight–line program Γ that evaluates a_{0}, …, a_{d} ∈ ℤ has size L, depth ℓ, and the parameters used by Γ are of logarithmic height at most η. Let us define the following integer number

τ := a_{d}disc_{T} (f) ∈ ℤ \ {0},

where disc_{T} (f) is the discriminant of f. From Lemma 45 we conclude

ht(disc_{T} (f)) ≤ d(log d + (2^{ℓ+1} − 2)(log L + η)).

Now, let N ∈ ℕ be a positive integer number such that

d(log d + 2(2^{ℓ+1} − 2)(log L + η)) < N2^{N}.

Thus, the machine M_{1} proceeds as follows :

• First of all, M_{1} chooses at random 4N disjoint lists L_{1}, …, L_{4N} of integer numbers between 2^{N} and 2^{2N}. We assume that each list L_{i} contains 4N different integer numbers.

• Then, M_{1} uses a probabilistic primality test running in polynomial time (cf. [AH92, AM93, SG86, Mor90, Mor91], for instance) to detect a prime number p_{i} ∈ L_{i} for every i, 1 ≤ i ≤ 4N (if any).

• Then, M_{1} takes the list ℙ = {p_{1}, …, p_{4N}} and looks for some prime number p ∈ ℙ, such that

τ mod p ≠ 0.

This last task is performed by using the straight–line program Γ that evaluates a_{d} and the obvious straight–line program Γ′ that evaluates disc_{T} (f).

The error probability of this procedure is at most (1 − \frac{1}{2N} )^{8N} < \frac{1}{e^{4}} < \frac{1}{2}.

Task 2: Efficient factoring module a prime number It is well–known that Berlekamp’s factoring procedure in ℤ/pℤ[T] is deterministic, but its running time depends polynomially on the prime number p, and hence exponentially on the bit length of p. To avoid this drawback, P. Camion, D. Cantor and H. Zassenhauss ([CZ81, Cam, Cam83], for instance) have developped a probabilistic factoring procedure for polynomials f ∈ ℤ/pℤ[X] whose running time depends polynomially on deg(f) and the bit length of the prime number p. This method yields the following technical statement :

Lemma 53 With the same assumptions as in Theorem 51 above, there exists a bounded error probabilistic Turing machine M_{2} that performs the following task: The input of M_{2} are polynomials f ∈ ℤ[T] as given in Theorem 51 above. The output of M_{2} is a prime number p ∈ ℤ as in Lemma 52 above and a list of polynomials

{f_{1}, …, f_{s}} ∈ ℤ/pℤ[T],

such that every f_{i} ∈ ℤ/pℤ[T] is an irreducible univariate polynomial for every i, 1 ≤ i ≤ s and

f̄ = ∏_{i=1}^{s} f_{i},

where f̄ ∈ ℤ/pℤ[T] is the univariate squarefree polynomial obtained by taking residues modulo p of the coefficients of f. The running time of M_{2} is polynomial in the following quantities :

d L η,

where d, L and η are as in Theorem 51 above.

Task 3 and 4: Newton–Hensel lifting and L^{3} basis reduction From the output of the Turing machine M_{2} of Lemma 53 above, we perform a Newton–Hensel lifting of each of the irreducible factors f_{i} ∈ ℤ/pℤ[T] of f̄ ∈ ℤ/pℤ[T] until we reach the bounds which allow us to apply the L^{3} reduction procedure of [LLL82a]. However, the original bounds in [LLL82a] depend on the weight of the input polynomial f ∈ ℤ[T]. Since we are not interested in computing all irreducible factors of f in ℚ[T], but just a few of them (those of weight bounded by H), we explain how the main statement of [LLL82a] can be modified for our purposes. The same proof of [LLL82a] yields our statement : For every positive integer number k ≥ 1, we denote by ℤ/p^{k}ℤ the residue ring of integers modulo p^{k}. For every integer number a ∈ ℤ, we denote by ā^{p} ∈ 𝔽_{p} and ā^{p^{k}} ∈ ℤ/p^{k}ℤ the residual classes modulo p and p^{k} respectively. For every univariate polynomial g with integer coefficients

g = a_{m}X^{m} + … + a_{1}X + a_{0}

we denote by ḡ^{p} ∈ 𝔽_{p}[X] and ḡ^{p^{k}} ∈ ℤ/p^{k}ℤ[X] the polynomials obtained respectively as : ḡ^{p} := ā_{m}^{p}X^{m} + … + ā_{1}^{p}X + ā_{0}^{p} ∈ 𝔽_{p}[X], and ḡ^{p^{k}} := ā_{m}^{p^{k}}X^{m} + … + ā_{1}^{p^{k}}X + ā_{0}^{p^{k}} ∈ ℤ/p^{k}ℤ. In the sequel we shall omit the superscripts ^{p} and ^{p^{k}} where no confusion may occur. From now on, let f ∈ ℤ[X] be a squarefree univariate polynomial with integer coefficients. Let p ∈ ℕ be a prime number and let us assume that f̄ ∈ 𝔽_{p}[X] is also squarefree and that

deg(f) := deg(f̄) = d.

Let us observe, that under these conditions f̄^{p^{k}} ∈ ℤ/p^{k}ℤ[X] is also squarefree and for every k ≥ 1 holds :

deg(f) = deg(f̄^{p^{k}}).

Let h ∈ ℤ[X] be a polynomial of degree r ≥ 0 such that the following holds :

• the leading coefficient of h is 1,

• h̄ divides f̄ in ℤ/p^{k}ℤ[X], and

• h̄ is an irreducible polynomial in 𝔽_{p}[X].

Proposition 54 [LLL82a] With the previous notations and assumptions, there exists one and only one irreducible factor h_{0} ∈ ℤ[X] of f (in ℤ[X]) such that h̄ divides h̄_{0} in 𝔽_{p}[X].

Now, we may define the following lattice (which depends only on h, p^{k} and m ∈ ℕ, ≤ m ≤ d):

L_{r,m}(h) := {g ∈ ℤ[X] : deg(g) ≤ m, h̄ divides ḡ in ℤ/p^{k}ℤ[X]}

Finally, for every polynomial g ∈ ℤ[X], given as g = a_{m}X^{m} + … + a_{1}X + a_{0}, we shall denote the norm of g as :

∥g∥ := (a_{m}^{2} + … + a_{1}^{2} + a_{0}^{2})^{\frac{1}{2}} .

Let us observe that ∥g∥ ≤ W T (g) ≤ (d + 1)∥g∥. The following Theorem essentially states that the main statement in [LLL82b] depends principally on ∥h_{0}∥ and not on ∥f∥.

Theorem 55 With the same notations and conventions as before, let b_{1}, …, b_{m+1} be a L^{3}–reduced basis of the lattice L_{r,m}(h). Let us also assume that

p^{kr} ≥ 2^{\frac{dm}{2}} 2^{dm}∥h_{0}∥^{m+d}.

Thus, h_{0} ∈ L_{r,m}(h) if and only if ∥b_{1}∥ ≤ (\frac{p^{kr}}{∥h_{0}∥^{m}} )^{\frac{1}{d}} .

Moreover, let t ∈ {1, …, m + 1} be the maximal integer number such that :

∥b_{j}∥ ≤ (\frac{p^{kr}}{∥h_{0}∥^{m}} )^{\frac{1}{d}} for every i, 1 ≤ j ≤ t.

Then, deg(h_{0}) = m + 1 − t and h_{0} = gcd(b_{1}, …, b_{t}).

The proof of this Theorem follows step by step as that of Proposition 2.13 in [LLL82b].

Now, we can show Theorem 51:

Proof.– [of Theorem 51] The machine M of Theorem 51 can be described as follows : First of all, we apply the machine M_{2} of Lemma 53 (which contains M_{1}) and yield the following list of items as output :

• a prime number p ∈ ℤ as in Lemma 53 above, and

• a list of polynomials {f_{1}, …, f_{s}} ⊂ ℤ/pℤ[T], such that every f_{i} ∈ ℤ/pℤ[T] is an irreducible univariate polynomial for every i, 1 ≤ i ≤ s and

f̄ = ∏_{i=1}^{s} f_{i}.

For every h ∈ {f_{1}, …, f_{s}}, the machine applies a Hensel Lifting procedure log_{2} k times (as in [PZ89], for instance) to obtain a univariate polynomial h_{i} ∈ ℤ[X] satisfying :

• the leading coefficient of h, is 1 (and agrees with that of h), • h̄ and h̄_{1} agree in 𝔽_{p}[X], and

• h̄_{1} divides f̄ in ℤ/p^{k}ℤ[X].

The number k has been chosen such that holds : p^{kr} ≥ 2^{\frac{d^{2}}{2}} 2^{d^{2}}2^{2dH}. Now, let h_{0} ∈ ℤ[X] be the unique irreducible factor of f determined by Proposition 54. Let r be the degree of h_{1} and for every m, r ≤ m ≤ d, let b_{1}^{(m)}, …, b_{m+1}^{(m)} be a L^{3}–reduced basis of the lattice L_{r,m}(h_{1}).

Now, if ∥b_{1}^{(m)}∥ < (\frac{p^{kr}}{2^{mH}} )^{\frac{1}{d}}, for some m, r ≤ m ≤ d, we conclude

• h_{0} ∈ L_{r,m}(h_{1}), and

• log_{2} ∥h_{0}∥ ≤ H (which, in particular, implies wt(h_{0}) ≤ log_{2}(d + 1) + H).

Conversely, if ∥b_{1}^{(m)}∥ ≥ (\frac{p^{kr}}{2^{mH}} )^{\frac{1}{d}} for every m, r ≤ m ≤ d, we conclude that wt(h_{0}) > H, and we

do not compute this irreducible factor. Thus, we proceed by computing h_{0} according to the strategy described by Theorem 55 above.

5.3 Computing binary encodings of suitable approximations

In the spite of the fast convergence of Newton’s method, the bit length (i.e. the height) of the results obtained after several iterations may grow much faster than desirable. That is why we have to truncate the intermediate results obtained and this is the goal of the following statement :

Theorem 56 (Efficient Diophantine Approximation) There exists a Turing machine M, which performs the following task : The input of M is the following list :

i) A list F := (f_{1}, …, f_{n}) of polynomials with integer coefficients of degree at most d and (logarithmic) weight at most w given by a division–free non–scalar straight–line program Γ of length L and depth ℓ and parameters in {−1, 0, 1}.

ii) The binary encoding of a point z ∈ ℚ[i]^{n} which is an approximate zero of the system F := (f_{1}, …, f_{n}) with associated zero ζ ∈ V_{K}(f_{1}, …, f_{n}) with respect to the standard archimedean absolute value | · | : K → ℝ induced by the standard inclusion i : K ↪ ℂ satisfying the γ–Theorem, namely

γ(F, ζ)∥z − ζ∥ ≤ \frac{3 − \sqrt{7}}{2}.

iii) A positive rational ϵ ∈ ℚ, ϵ < 1.

The machine M outputs the binary encoding of an approximation z̄ ∈ ℚ[i]^{n}, such that

∥z̄ − ζ∥ ≤ ϵ.

The (logarithmic) height of z̄ satisfies the following inequality :

ht(z̄) ≤ (n d w ht(z)(− log_{2} ϵ))^{c_{4}}

where c_{4} > 0 is a universal constant. The running time of M is polynomial in the following quantities :

n d L w ht(z) (− log_{2} ϵ).

The proof of this statement will make use of several technical procedures which we are going to state now.

Rational Reconstruction of Newton Iteration.

Lemma 57 With the same notations and assumptions as in Theorem 56 above, there exists a universal constant c_{5} > 0 such that the following holds : for every z ∈ ℚ[i]^{n} :

ht(N_{F} (z)) ≤ (d n w)^{c_{5}}ht(z).

Due to the straight–line program encoding of the polynomials f_{1}, …, f_{n}, we have to use the following Lemma which gives a well-suited version of Newton operator for this encoding.

Lemma 58 [GHH^{+}97, Mor97] Let f_{1}, …, f_{n} ∈ ℤ[X_{1}, …, X_{n}] be polynomials as in Theorem 63. Then, there exists a straight–line program of length O(d^{2}n^{7}L) and non-scalar depth O(log_{2} n + ℓ) which using the same parameters, computes the numerators g_{1}, …, g_{n} and a non–zero denominator h for N_{F} (X_{1}, …, X_{n})ℤ(X_{1}, …, X_{n}).

In order to obtain the binary encoding of N_{F} (z), we use the following Lemma (as given in [HM97]) which is suitable for our particular straight–line program encoding of N_{F}. It is based on a rational reconstruction procedure due to J. Dixon (see [Dix82] or [Häg98, HM97] for details).

Lemma 59 [HM97] There exists a Turing machine which, taking as input the straight–line program of N_{F} (z_{1}, …, z_{n}), outputs in time polynomial in

d n w ht(z) L

a reduced binary encoding of N_{F} (z_{1}, …, z_{n}) (i.e. numerators and denominators have no common factors).

Effective Dirichlet Theorem. The first relevant statement is the following effective version of Dirichlet’s Theorem due to [LLL82a].

Theorem 60 (Effective Dirichlet Theorem) There exists a polynomial–time algorithm that, given a positive integer n and rational numbers a_{1}, …, a_{n}, ϵ satisfying 0 < ϵ < 1, finds integers p_{1}, …, p_{n}, q satisfying

|p_{i} − qa_{i}| ≤ ϵ for 1 ≤ i ≤ n, and 1 ≤ q ≤ \frac{2^{n(n+1)/4}}{ϵ^{2n}} .

Proof.– [of Theorem 56] Let us denote by EDT (z, ϵ) the result of applying the Effective Dirichlet Theorem above to the point z and the rational number ϵ. Let us recursively define the following sequence of points in ℚ[i] :

z^{(1)} := N_{F} (z), and z̄^{(1)} := EDT (z^{(1)}, ϵ/4)

and for k ≥ 2,

z^{(k)} := N_{F} (z̄^{(k−1)}), and z̄^{(k)} := EDT (z^{(k)}, ϵ/4).

Now, we have : ∥z̄^{(k)} − ζ∥ < ∥z^{(k)} − ζ∥ + \frac{ϵ}{4}. On the other hand, the following holds :

∥z^{(k)} − ζ∥ ≤ \frac{1}{2}∥z̄^{(k−1)} − ζ∥.

From the previous inequalities we conclude :

∥z̄^{(k)} − ζ∥ ≤ \frac{1}{2^{k}} ∥ζ − z∥ + ∑_{i=0}^{k−1} \frac{ϵ}{2^{i+2}} .

In order to estimate ∥ζ − z∥, we apply Remark 38 to conclude :

log ∥ζ − z∥ ≤ c (\frac{3}{d − 1}) 2(log n + w + d^{2}(ht(z))) + 1,

where c is a small universal constant c > 0. Therefore the following inequality holds :

∥z̄^{(k)} − ζ∥ ≤ \frac{1}{2^{k}} 2^{c(log n+w+d^{2}ht(z)} + \frac{ϵ}{2}.

Thus, taking k ∈ ℕ such that k > (− log_{2} ϵ)c(log n + w + d^{2}ht(z)), the proof concludes.

Let us observe that the procedure described in the previous Theorem is essentially optimal due to the lower bound given in [GHH^{+}97].

5.4 From Kronecker’s to Newton’s solution

In this Subsection we prove Theorem 16 as stated in the Introduction. That statement is merely a consequence of the following Theorem we are going to show here.

Theorem 61 (From Kronecker’s solution to Newton’s solution) There exists a bounded error probability Turing machine M which performs the following task : Given as input a positive integer H ∈ ℕ in binary encoding and a sequence F of multivariate polynomials with integer coefficients F := (f_{1}, …, f_{n}) with f_{1}, …, f_{n} ∈ ℤ[X_{1}, …, X_{n}] satisfying :

• the polynomials f_{1}, …, f_{n} are of degree at most d and (logarithmic) weight at most w,

• the sequence f_{1}, …, f_{n} is given by a division–free non–scalar straight–line program Γ of length L, non–scalar depth ℓ and parameters in {−1, 0, 1}, and

• the sequence f_{1}, …, f_{n} ∈ ℤ[X_{1}, …, X_{n}] is a smooth regular sequence,

the machine M outputs approximate zeros with respect to the archimedean absolute value |·| : K → ℝ induced on K by the canonical inclusion i : K ↪ ℂ for all those zeros ζ ∈ V_{K}(f_{1}, …, f_{n}), whose (logarithmic) height is at most H, i.e.

ht(ζ) ≤ H.

The running time of M is polynomial in the following quantities

(n d δ(F) L w) + (n d D H [K : ℚ]),

where δ(F) := max{deg V (f_{1}, …, f_{i}) : 1 ≤ i ≤ n} and D := deg V (f_{1}, …, f_{n}).

Proof.– This statement follows by giving a procedure that transforms a Kronecker description of the solution variety into a list of approximate zeros of bounded height. First of all, let us recall how to relate ℚ–definable irreducible components of bounded height and irreducible factors of bounded height of the minimal equation of the primitive element χ_{u} of the Kronecker solution. A ℚ–definable complex variety is an algebraic subset V ⊂ ℂ^{n}, such that there exist polynomials f_{1}, …, f_{s} ∈ ℤ[X_{1}, …, X_{n}] with integer coefficients, such that

V = \{\underline{x} ∈ ℂ^{n} : f_{1}(\underline{x}) = 0, …, f_{s}(\underline{x}) = 0\}.

In particular, under our hypotheses the solution variety V (f_{1}, …, f_{n}) ⊂ C^{n} is ℚ–definable. A ℚ– definable algebraic subset V ⊂ ℂ^{n} is said to be ℚ–definable irreducible if for any two ℚ–definable algebraic subsets V_{1}, V_{2} ⊂ ℂ^{n}, the following holds :

V ⊂ V_{1} ∪ V_{2} ⇒ [V ⊂ V_{1}] ∨ [V ⊂ V_{2}].

In particular, the usual method shows that every ℚ–definable algebraic subset V ⊂ ℂ^{n} has a unique minimal description as a finite union of ℚ–definable irreducible algebraic subsets V_{1}, …, V_{s} ⊂ ℂ^{n}. Namely,

V = V_{1} ∪ … ∪ V_{s}.

These ℚ–definable irreducible subsets V_{1}, …, V_{s} are called the ℚ–definable irreducible components of V. Let us observe that if V ⊂ C^{n} is zero–dimensional (i.e. if V is a finite set) and if

V = V_{1} ∪ … ∪ V_{s}

is the decomposition of V into ℚ–definable irreducible components, then this is a partition of V. Namely, V_{i} ∩ V_{j} = ∅ for every i ≠ j. Let us assume now that K is a number field and that ζ ∈ V_{K}(f_{1}, …, f_{n}) is a K–rational point of a zero–dimensional algebraic subset V (f_{1}, …, f_{n}) ⊂ ℂ^{n}. Then, there exists a unique ℚ–definable irreducible component V_{ζ} ⊂ ℂ^{n} containing ζ. This unique ℚ–definable irreducible component of V_{ζ} is the residue class field of the actual zero, i.e.

ℚ[V_{ζ}] = ℚ(ζ).

Moreover, as ζ ∈ K^{n}, we easily conclude the following inequality :

deg V_{ζ} = deg(ζ) = #V_{ζ} ≤ [K : ℚ].

Let f_{1}, …, f_{n} ∈ ℤ[X_{1}, …, X_{n}] be a sequence of polynomials defining a zero–dimensional ℚ– definable affine algebraic variety V := V (f_{1}, …, f_{n}) := \{\underline{x} : f_{1}(\underline{x}) = 0, …, f_{n}(\underline{x}) = 0\}. Let us assume that the ideal (f_{1}, …, f_{n}) is a radical ideal in ℚ[X_{1}, …, X_{n}]. In particular all points in V are smooth. As defined in the Introduction, a Kronecker solution of V (f_{1}, …, f_{n}) is the following list of items :

• The list of variables in Noether position X_{1}, …, X_{n}.

• The primitive element u := λ_{1}X_{1} + ⋯ + λ_{n}X_{n} given by its coefficients in ℤ. Let us recall that the linear form u is a primitive element u if and only if the polynomial mapping :

U : ℂ^{n} ⟶ ℂ : (x_{1}, …, x_{n}) ↦ u(x_{1}, …, x_{n})

defines a birational isomorphism between V (f_{1}, …, f_{n}) and a hypersurface H_{u} ⊂ ℂ (i.e. the set of roots of a univariate polynomials χ_{u} ∈ ℤ[T]).

• The minimal equation of the hypersurface H_{u}, namely χ_{u} ∈ ℤ[T].

• A description of (U |_{V})^{−1}. This description is given by the following list :

– a non–zero integer number ρ ∈ ℤ,

– a list of polynomials v_{j} ∈ ℤ[T], 1 ≤ j ≤ n, such that deg(v_{j}) ≤ deg(χ_{u}) for every j, 1 ≤ j ≤ n,

and such that the following holds for every t ∈ H_{u} :

(U |_{V})^{−1}(t) := (ρ^{−1}v_{1}(t), …, ρ^{−1}v_{n}(t)) .

In particular, the birational isomorphism U : V ⊂ ℂ^{n} → H_{u} ⊂ ℂ defines a biregular isomorphism that identifies the ℚ–definable irreducible components of V and the ℚ–definable irreducible components of H_{u}. Moreover, the ℚ–definable irreducible components of H_{u} are completely determined by the prime factors of the univariate polynomial χ_{u} ∈ ℤ[T]. This is explained in the following Lemma, whose elementary proof we omit.

Lemma 62 With the previous notations and assumptions, let ζ := (ζ_{1}, …, ζ_{n}) ∈ V_{K}(f_{1}, …, f_{n}) be a smooth K–rational zero of the system V = (f_{1}, …, f_{n}). Let V_{ζ} ⊂ V (f_{1}, …, f_{n}) be the ℚ– definable irreducible component of V (f_{1}, …, f_{n}) containing ζ. Then the following properties hold :

• #V_{ζ} = deg V_{ζ} ≤ [K : ℚ],

• there exists a unique prime factor g ∈ ℚ[T] of χ_{u} ∈ ℤ[T] such that :

– g ∈ ℤ[T] is a primitive polynomial,

– g vanishes on U(V_{ζ}),

– g has a zero in K,

– ht(g) ≤ [K : ℚ](ht(ζ) + ht(u)).

Moreover, there exists a non–zero integer ρ̄ ∈ ℤ \ {0} and polynomials w_{1}, …, w_{n}, such that the following holds :

• the (logarithmic) height of ρ̄,w_{1}, …, w_{n} is at most polynomial in

[K : ℚ] deg(g)[ht(ζ) + ht(u)]n,

• deg(w_{i}) ≤ deg(g) − 1 for all i, 1 ≤ i ≤ n, and

• V_{ζ} := {(ρ̄^{−1}w_{1}(t), …, ρ̄^{−1}w_{n}(t)) : t ∈ ℂ and g(t) = 0}.

This univariate polynomial g is obviously the minimal polynomial over ℚ of the algebraic number :

u(ζ) := u_{1}ζ_{1} + … + u_{n}ζ_{n}.

The polynomials w_{1}, …, w_{n} ∈ ℤ[T] and the non–zero integer ρ̄ ∈ ℤ\{0} introduced in the previous Lemma are given by the following rule. Let q_{1}, …, q_{n} ∈ ℚ[T] be the remainders of the division of ρ^{−1}v_{i}(T) by g(T), i.e. q_{i} := rem(ρ^{−1}v_{i}, g) for every i, 1 ≤ i ≤ n. Then, taking a minimal non–zero integer ρ̄ ∈ ℤ \ {0}, such that ρ̄q_{i} ∈ ℤ[T] for all i, 1 ≤ i ≤ n and defining w_{i} := ρ̄q_{i} ∈ ℤ[T] for every i, 1 ≤ i ≤ n, we obtain the desired polynomials. In conclusion, to determine the list of smooth K–rational zeros of the system F of height bounded by H, we may determine the irreducible factors of χ_{u} such that

• K contains a root of g, and

• ht(g) ≤ [K : ℚ](H + ht(u)).

Thus, to prove Theorem 16, we start by using Theorem 14 (cf. [GHMP97]) as stated in the Introduction. Let us recall that the output of the procedure described in Theorem 14 is a Kronecker solution of the variety V (f_{1}, …, f_{n}) with the following properties :

• the coefficients of the primitive element u have height at most cn log_{2} d,

• the coefficients of the polynomials χ_{u}, v_{1}, …, v_{n} ∈ ℤ[T] and the non–zero integer number ρ ∈ ℤ \ {0} are given by a straight–line program Γ satisfying the following properties :

– size of Γ ≤ (ndδ)^{c_{6}}L,

– non–scalar depth of Γ ≤ n^{c}(log_{2} δ + ℓ + log_{2} d),

– the parameters used by Γ are in {−1, 0, 1} ⊂ ℤ,

where c_{6} > 0 is some some “small” universal constant.

In order to conclude Theorem 16 from this data, we proceed as follows :

Task 1.- Computing irreducible factors of χ_{u} of bounded height Using the method described in Subsection 5.2 above, we compute all irreducible factors of χ_{u} of height bounded by

[K : ℚ](H + ht(u)).

Let us observe that these factors are given by their coefficient lists and that the coefficients are given by their binary encoding.

Task 2.- Selecting factors with some zero in K We make use of the factoring procedures described in [Lan85, LM85] or [Len83]. Thus, from the output of Task 1, we choose just those factors g of χ_{u} satisfying :

• g has a root in K, and

• ht(g) ≤ [K : ℚ](H + ht(u)).

Let us observe that the running time required to perform this task is polynomial in c(K)[K : ℚ](H + ht(u))D, where D is the degree of the solution variety V, and c(K) is the height of the field K. As the field K is fixed in our considerations, we will omit this quantity from now on.

Task 3.-Computing irreducible components of bounded height Let F := {g_{1}, …, g_{s}} ⊂ ℤ[T] be the output of Task 2, i.e. a list of irreducible factors of χ_{u} of bounded height having a root in K. Now, for every g ∈ F, we apply the following procedure : Let C(g) be the companion matrix of g. For every i, 1 ≤ i ≤ n, let us introduce the matrices

M_{i} := ρ^{−1}v_{i}(C(g)).

Let q_{1}, …, q_{n} ∈ ℤ[T] be the characteristic polynomials of the matrices M_{1}, …, M_{n}. Let ζ ∈ V_{K}(f_{1}, …, f_{n}) be a smooth zero and V_{ζ} ⊂ V_{K}(f_{1}, …, f_{n}) the ℚ–definable irreducible component of V_{K}(f_{1}, …, f_{n}) that contains ζ. Let us assume that V_{ζ} is identified with the irreducible factor g of χ_{u} according to the rules described in Lemma 62 above. Let us finally assume ζ := (ζ_{1}, …, ζ_{n}). Then, we obviously have the following property : For every i, 1 ≤ i ≤ n, the minimal polynomial of the matrix M_{i} is the minimal polynomial of ζ_{i} over ℚ, and the characteristic polynomial of M_{i} is a power of the minimal polynomial of ζ_{i} ∈ K over ℚ. Now, we proceed as follows. Applying the factoring procedure described in Subsection 5.2 above, we verify for every i, 1 ≤ i ≤ n, whether the polynomial q_{i} has any irreducible factor (the only one if any) of height at most H. In the affirmative case, we have

ht(ζ_{i}) ≤ (log_{2}(d + 1) + H)[K : ℚ] and ht(ζ) ≤ n(log_{2}(d + 1) + H)[K : ℚ].

Thus, we select all those irreducible factors g of the list F above, such that

• ht(ζ) ≤ n(log_{2}(d + 1) + H)[K : ℚ],

• ht(g) ≤ [K : ℚ](H + ht(u)), and

• K contains a root of g.

This can be done in time polynomial in the quantities :

[K : ℚ] n d L δ H.

Task 4.- Computing bounded height parametrizations Let F_{1} := {g_{1}, …, g_{s_{1}}} be the output of Task 3. Now, for every g ∈ F_{1} we perform the following task. Using the technical tool described in [Dix82] (cf. also [Häg98, HM97]) and Lemma 62, we may compute

• a non–zero integer ρ̄ ∈ ℤ \ {0} and

• univariate polynomials w_{1}, …, w_{n} ∈ ℤ[T],

such that the following holds :

i) ht(ρ̄), ht(w_{1}), …, ht(w_{n}) are bounded by a polynomial in the quantities [K : ℚ]nd deg(g)H,

ii) deg(W_{i}) ≤ deg(g) − 1 for all i, 1 ≤ i ≤ n.

iii) Let ζ ∈ V_{K}(f_{1}, …, f_{n}) be the smooth K–rational zero of the system F associated to the irreducible factor g according to Lemma 62 above. Let V_{ζ} be the ℚ–definable irreducible component of V_{K}(f_{1}, …, f_{n}) that contains ζ. Then, the following is a biregular isomorphism :

U|_{V_{ζ}} : V_{ζ} ⊂ ℂ^{n} → {t ∈ ℂ : g(t) = 0} and (U|_{V_{ζ}})^{−1} := (ρ̄^{−1}w_{1}(t), …, ρ̄^{−1}w_{n}(t)).

Task 5.- Computing approximate zeros of univariate polynomials For this task, we consider the univariate polynomial with integer coefficients

f(T) := ∏_{g∈F} g ∈ ℤ[T],

where F_{1} is the output of Task 3. Thus, we compute approximate zeros of the univariate polynomial f. This can be done by means of any of the procedures described for instance in [BCSS98a, Ren87, Sch86, Sch81, Sma81, Sma86a]. The running time of any of these procedures is polynomial in

n [K : ℚ] D H.

Task 6.- Computing approximate zeros in the multivariate case Now, we recall the proof of Theorem 8 from Subsection 4.3, to conclude that for every smooth K–rational zero ζ ∈ V_{K}(f_{1}, …, f_{n}) the following holds :

log_{2} γ(F, ζ) ≤ (nd)^{3}[K : ℚ](h + ht(ζ)).

Now, let F_{1} := {g_{1}, …, g_{s_{1}}} be the list of irreducible factors of χ_{u} computed after Task 3. For every g ∈ F_{1}, we apply :

i) Task 4 to compute the parametrization of bounded height,

i.e. ρ̄ ∈ ℤ \ {0} and w_{1}, …, w_{n} ∈ ℤ[T].

ii) Task 5 to compute for every zero of g an approximate zero.

Let us assume ζ ∈ V_{K}(f_{1}, …, f_{n}) be the smooth K–rational zero associated to g according to the rules of Lemma 62 above. Let V_{ζ} be the ℚ–definable irreducible component of V (f_{1}, …, f_{n}) containing ζ. Next, let z ∈ ℚ[i] be an approximate zero of u(ζ) computed by applying Task 5 to g. For sake of simplicity we may assume that |u(ζ) − z| < 1 and that the height of z is polynomial in the following quantities : ht(g)ht(ζ)[K : ℚ] n d.

Finally, let us observe that ζ := (ρ̄^{−1}w_{1}(u(ζ)), …, ρ̄^{−1}w_{n}(u(ζ))) and for every x ∈ ℚ[i], the following inequality holds :

∥ζ − (ρ̄^{−1}w_{1}(x), …, ρ̄^{−1}w_{n}(x))∥ ≤ n2^{wt(w_{i})}∥x − u(ζ)∥.

Then, we may apply the procedure described in Subsection 5.3 to compute a point x ∈ ℚ[i] satisfying

∥x − u(ζ)∥ < ϵ,

where ϵ satisfies n2^{wt(w_{i})}ϵ < \frac{3−\sqrt{7}}{2γ(F,ζ)}. Using the previous bounds, we observe that there exists a universal constant c_{7} > 0 such that if log_{2} ϵ < ([K : ℚ]ndHw)^{c_{7}} holds, then the point z̄ ∈ ℚ[i]^{n} given by z̄:= (ρ̄^{−1}w_{1}(x), …, ρ̄^{−1}w_{n}(x)) is an approximate zero of the system F with associated ζ, i.e.

∥z̄ − ζ∥ < \frac{3 − \sqrt{7}}{2γ(F, ζ)}.

The running time of this task is polynomial in the following quantities :

[K : ℚ] n d w H log_{2} ϵ,

and the bounds above also show that log_{2} ϵ is polynomially bounded in the same quantities.

5.5 From Newton’s to Kronecker’s solution

In this Subsection we show Theorem 15 of the Introduction as a consequence of the following Theorem :

Theorem 63 (From Approximate Zeros to Geometric Solution) There exists a bounded error probability Turing machine M which performs the following task : Suppose given as input a sequence F := (f_{1}, …, f_{n}) of multivariate polynomial with integer coefficients of degree at most d and (logarithmic) weight at most w satisfying the following properties :

• the polynomials f_{1}, …, f_{n} are given by a division–free non–scalar straight–line program Γ of length L, non–scalar depth ℓ and parameters in {−1, 0, 1},

• the sequence f_{1}, …, f_{n} ∈ ℤ[X_{1}, …, X_{n}] is a smooth regular sequence,

and a point z ∈ ℚ[i]^{n} in binary encoding which is an approximate zero of the system F associated to some smooth K–rational zero ζ ∈ V_{K}(f_{1}, …, f_{n}) with respect to the archimedean absolute value |˙| : K → ℝ induced on K by the standard inclusion i : K ↪ ℂ. Let us also assume that z satisfies the γ–Theorem, namely

∥ζ − z∥ ≤ \frac{3 − \sqrt{7}}{2γ(F, ζ)}.

Then M outputs a Kronecker description of the residue class field ℚ(ζ) of the actual zero (i.e. a Kronecker description of the ℚ–definable irreducible component V_{ζ} of V_{K}(f_{1}, …, f_{n}) that contains ζ ∈ V_{ζ}. The running time of M is polynomial in the following quantities :

w n d L ht(ζ) deg(V_{ζ})ht(z).

Proof.– The proof combines a method of reconstruction of minimal equations from diophantine approximations (cf. [KLL84, KLL88]) with a technical tool introduced in [KP94, KP96]. Let us introduced new variables T_{1}, …, T_{n}. We denote by K_{T} the quotient field of the ring ℤ[T_{1}, …, T_{n}] and by 𝕂_{T} an algebraic closure of it. Let U := T_{1}X_{1} + … + T_{n}X_{n} ∈ ℤ[T_{1}, …, T_{n}, X_{1}, …, T_{n}] be a generic projection. Let V_{ζ} ⊂ V (f_{1}, …, f_{n}) be the ℚ–definable irreducible component of V (f_{1}, …, f_{n}) containing the smooth K–rational zero ζ ∈ V_{K}(f_{1}, …, f_{n}). The Chow polynomial of V_{ζ} is the homogeneous polynomial of degree deg(V_{ζ}) given by the following identity :

χ_{U,ζ}(T_{1}, …, T_{n}, Z) := ∏_{α∈V_{ζ}}(Z − (T_{1}α_{1} + … + T_{n}α_{n})),

where α := (α_{1}, …, α_{n}) runs over all complex points in V_{ζ}. For every t := (t_{1}, …, t_{n}) ∈ ℤ^{n} and for every i, 1 ≤ i ≤ n we introduce the following polynomials :

p_{i}(t, Z) := χ_{U,ζ}(T_{1}, …, T_{i−1}, 0, T_{i+1}, …, T_{n}, Z) and

q_{i} := χ_{U}(0, …,^{i)} 1, …, 0, T) = ∏_{α∈V_{ζ}}(Z − α_{i}).

Finally, we introduce for every i, 1 ≤ i ≤ n, and every t := (t_{1}, …, t_{n}) ∈ ℤ^{n} the following family of planar algebraic sets :

V_{i}(t) := {(x, y) ∈ 𝕂^{2} : q_{i}(x) = 0, p_{i}(t, y) = 0}.

Now, we have the following two statement :

Lemma 64 [KP94, KP96] With the same notations and assumptions as above, there exists a multivariate polynomial F ∈ ℤ[T_{1}, …, T_{n}] of degree at most n deg(V_{ζ})^{2}, such that the following holds : For every t := (t_{1}, …, t_{n}) ∈ ℤ^{n} satisfying F (t_{1}, …, t_{n}) ≠ 0 holds : for every i, 1 ≤ i ≤ n, the linear form u_{i} := X + t_{i}Y is a primitive element of the residue ring

ℚ[X, Y]/\sqrt{p_{i}(t, X), q_{i}(Y)},

where √ stands for the radical of this ideal.

Moreover, the polynomial F can be computed from the coefficients of the polynomials p_{i}(t, X) and q_{i}(Y) in time polynomial in the following quantities :

ht(t) deg(V_{ζ}) n ht(ζ).

Let us observe that for every t := (t_{1}, …, t_{n}) ∈ ℤ^{n} satisfying F (t) ≠ 0 the following linear form

U := t_{1}X_{1} + … + t_{n}X_{n} ∈ ℤ[X_{1}, …, X_{n}]

is a primitive element of the residue ring

ℚ[V_{ζ}] := ℚ[X_{1}, …, X_{n}]/I(V_{ζ}), where I(V_{ζ}) := {g ∈ ℚ[X_{1}, …, X_{n}] : g|_{V_{ζ}} ≡ 0}.

Now, to find a point t ∈ ℤ^{n} that satisfies F (t) ≠ 0, we can make use of any of the so–called probabilistic zero test for polynomials. We may apply for instance the following Lemma, due to [Sch79, Zip79].

Lemma 65 (Zippel–Schwartz) Let F ∈ ℤ[T_{1}, …, T_{n}] be as above and let

A := {1, …, (n deg(V_{ζ})^{c_{8}}}^{n} ⊂ ℤ^{n}

be a subset of integers of low height (where c_{8} > 0 is a suitable universal constant). Then, choosing (at random) a point t ∈ A, the probability that F (t) = 0 is strictly less than \frac{1}{2}.

Now we can exhibit a procedure which proves the claims made in Theorem 63. First of all, let us choose at random a sequence of integer numbers t := (t_{1}, …, t_{n}) ∈ ℤ^{n}, such that

|t_{i}| ≤ (n deg(V_{ζ}))^{c_{8}}, for all i, 1 ≤ i ≤ n,

where c_{8} > 0 is the universal constant of Lemma 65 above. For every i, 1 ≤ i ≤ n, let us define the following algebraic numbers :

α_{i} := t_{1}ζ_{1} + … + t_{i−1}ζ_{i−1} + t_{i+1}ζ_{i+1} + … + t_{n}ζ_{n} and β_{i} := ζ_{i},

where ζ := (ζ_{1}, …, ζ_{n}) ∈ K^{n} is the actual smooth K–rational zero. Now, we apply the method described in Subsection 5.3 above to compute an approximate zero z̄ ∈ ℚ[i]^{n} of the system F with associated zero ζ, such that the following holds :

∥z̄ − ζ∥ ≤ ϵ^{−1}.

Let us write z̄ := (z_{1}, …, z_{n}) ∈ ℚ[i]^{n}. For every i, 1 ≤ i ≤ n, we define the following Gaussian rationals

x_{i} := t_{1}z_{1} + … + t_{i−1}z_{i−1} + t_{i+1}z_{i+1} + … + t_{n}z_{n} and y_{i} := z_{i}.

Then, we have ∥x_{i} − α_{i}∥ ≤ n(n deg(V_{ζ}))_{8}^{c}ϵ^{−1} and ∥y_{i} − β_{i}∥ ≤ ϵ^{−1}. Now, choosing ϵ ∈ ℕ, ϵ > 1 such that log_{2} ϵ > [(10 + c_{8})d deg(V_{ζ})^{2}(n + ht(ζ))], we conclude

∥x_{i} − α_{i}∥ ≤ \frac{1}{2^{9 deg(α_{i})^{2}ht(α_{i})}} and ∥y_{i} − β_{i}∥ ≤ \frac{1}{2^{9 deg(β_{i})^{2}ht(β_{i})}} .

Then, we apply the procedure described in the following Theorem (see [KLL84] for details) :

Theorem 66 Let α ∈ ℂ be an algebraic number of (logarithmic) height ht(α) and degree d := [ℚ(α) : ℚ] and let ᾱ ∈ ℚ[i] be an approximation such that :

|α − ᾱ| < 2^{−2d^{2}+3d+4dh}.

Then, there exists a polynomial time algorithm which, taking as input the approximation ᾱ, computes the minimal polynomial of α.

Thus, we have computed for every i, 1 ≤ i ≤ n, the following univariate polynomials :

• p_{i}(X) ∈ ℤ[X], the minimal polynomial of α_{i} over ℚ , and

• q_{i}(Y) ∈ ℤ[Y], the minimal polynomial of β_{i} over ℚ.

We apply a similar procedure to compute the minimal polynomial p(Z) ∈ ℚ[Z] of the algebraic number

u := t_{1}ζ_{1} + … t_{n}ζ_{n} ∈ K.

Next, we test whether for every i, 1 ≤ i ≤ n, the linear form X + t_{i}Y is a primitive element of the residue ring

ℚ[X, Y]/\sqrt{p_{i}(X), q_{i}(Y)}.

In the affirmative case, we apply the following Lemma, otherwise, we choose a different point t ∈ ℤ^{n}.

Lemma 67 [KP96, KP94] With the previous notations and assumptions, there exists a procedure that computes the following items :

i) A non–zero integer ρ ∈ ℤ, and

ii) univariate polynomials v_{1}, …, v_{n} ∈ ℤ[T], such that for every i, 1 ≤ i ≤ n holds :

ρY − v_{i}(X + Z_{i}Y) ∈ \sqrt{(p_{i}, q_{i})} in ℚ[X, Y].

The running time of this procedure is polynomial in the following quantities

ht(t) max{deg(p_{i}), deg(q_{i})} max{ht(p_{i}), ht(q_{i})}.

Finally, let us define the linear form u := t_{1}X_{1} + … + t_{n}X_{n} ∈ ℚ[X_{1}, …, X_{n}] and the ideal I := (p(u), ρX_{1} − v_{1}(u), …, ρX_{n} − v_{n}(u)) ⊂ ℚ[X_{1}, …, X_{n}]. The procedure outputs the above list if and only if I ⊂ (f_{1}, …, f_{n}). This inclusion can be tested by the following equivalence :

I ⊂ (f_{1}, …, f_{n}) if and only if p|f_{i}(ρ^{−1}v_{1}(u), …, ρ^{−1}v_{n}(u)), ∀i, 1 ≤ i ≤ n.

The output is obviously the Kronecker encoding of the ℚ–definable irreducible component of V containing ζ.

6 Application : Splitting field and Lagrange resolvent

Let f := a_{d}X^{d} + ⋯ + a_{0} ∈ ℤ[X] be a squarefree univariate polynomial of degree d with integer coefficients. As f is square free, we obviously have α_{i} ≠ α_{j} for all i, j, 1 ≤ i, j ≤ d and i ≠ j. Let α_{1}, …, α_{d} ∈ ℂ be the complex roots of the polynomial f. We obviously have the following identity :

f(X) = a_{d} ∏_{i=1}^{d}(X − α_{i}) ∈ ℤ[X].

Let σ_{0}, …, σ_{d−1} ∈ ℤ[X_{1}, …, X_{d}] be the elementary symmetric functions, i.e. the polynomial mappings satisfying the following identities :

σ_{i}(α_{1}, …, α_{d}) = a_{d}^{−1}a_{i}, ∀i, 0 ≤ i ≤ d − 1.

The normal closure of f (also called the splitting field of f) is the smallest number field K(f) ⊆ ℂ that contains all complex roots of f, i.e. the following holds :

K(f) = ℚ(α_{1}, …, α_{d}).

The Galois group of f is the group Gal_{ℚ}(f) of all field automorphism τ : K(f) → K(f) such that its restriction to ℚ is the identity. The order of the Galois group Gal_{ℚ}(f) agrees with the dimension of K(f) as a ℚ−vectorspace, i.e. ♯Gal_{ℚ}(f) = [K(f) : ℚ]. The Cayley–Lagrange resolvent of the polynomial f is a multivariate homogeneous polynomial which rational coefficients that represents both the Galois group Gal_{ℚ}(f) and the normal closure K(f). Namely, the Cayley–Lagrange resolvent is a polynomial LAG_{f}(T_{1}, …, T_{d}, Z) ∈ ℚ[T_{1}, …, T_{d}, Z] of degree [K(f) : ℚ] given by the following identity :

LAG_{f}(T_{1}, …, T_{d}, Z) := ∏_{τ∈Gal_{ℚ}(f)}(Z − (T_{1}τ(α_{1}) + ⋯ + T_{d}τ(α_{d})), τ ∈ Gal_{ℚ}(f).

The polynomial LAG_{f}(T_{1}, …, T_{d}, Z) is homogeneous and a monic polynomial with respect to the variable Z. The total degree of LAG_{f}(T_{1}, …, T_{d}, Z) is the order of the Galois group Gal_{ℚ}(f). The classical Lagrange resolvent is simply the univariate polynomial :

γ(Z) := LAG_{f}(1, α, …, α^{d−1}, Z),

where α is a root of unity. The Cayley–Lagrange resolvent satisfies the following additional property, which explains why LAG_{f} characterizes K(f).

Proposition 68 With the same assumptions and notations as above, let D(T_{1}, …, T_{d}) ∈ ℚ[T_{1}, …, T_{d}] be the discriminant of LAG_{f} with respect to the variable Z. Then, for every \underline{t} := (t_{1}, …, t_{d}) ∈ ℤ^{d} satisfying D(\underline{t}) ≠ 0, the following holds :

• The algebraic number θ := t_{1}α_{1} + … + t_{d}α_{d} is a primitive element of K(f) over ℚ, i.e. K(f) = ℚ(θ).

• The univariate polynomial p(Z) := LAG_{f}(t_{1}, …, t_{d}, Z) ∈ ℤ[Z] satisfies K(f) := ℚ[Z]/p(Z).

In fact, using an strategy similar to that of [KP96] and Lemma 67 we may compute from the Cayley–Lagrange resolvent both a primitive element θ of K(f) and a description of the roots α_{1}, …, α_{d} in terms of θ in time polynomial in [K(f) : ℚ]h. There is a more geometrical approach to the notion of Cayley–Lagrange resolvent. Let us consider the following zero–dimensional algebra (called the universal Resolution Algebra, cf. [Duc97]) :

U(f) := ℚ[X_{1}, …, X_{d}]/I(f),

where I(f) is the zero–dimensional ideal generated by the polynomials I(f) := (F_{0}, …, F_{d−1}) where F_{0}, …, F_{d−1} are given by the following identity :

F_{i} := σ_{i}(X_{1}, …, X_{d}) − a_{d}^{−1}a_{0} ∈ ℚ[X_{1}, …, X_{n}] for every i, 0 ≤ i ≤ d − 1.

Let V_{f} := V (F_{0}, …, F_{d−1}) ⊂ ℂ^{d} be the set of all common zeros of the system of equations F_{0} = 0, …, F_{d−1} = 0. The algebraic set V_{f} is ℚ–definable. Let us consider a ℚ–definable irreducible component W ⊂ V_{f} of V_{f}. We denote by CC_{W} (T_{1}, …, T_{d}, Z) ∈ ℚ[T_{1}, …, T_{d}, Z] the Cayley–Chow polynomial of the algebraic variety W. Namely, the following identity holds :

CC_{W} (T_{1}, …, T_{d}, Z) := ∏_{α∈W}(Z − (T_{1}α_{1} + … + T_{n}α_{n})),

where α := (α_{1}, …, α_{d}) ∈ ℂ^{n}. Then, the following Proposition holds :

Proposition 69 With the same assumptions and notations as above, for every ℚ–definable irreducible component W of V_{f}, the following holds :

LAG_{f}(T_{1}, …, T_{d}, Z) = CC_{W} (T_{1}, …, T_{d}, Z)

In particular, deg W = ♯Gal_{ℚ}(f) = [K(f) : ℚ].

Let us observe that a Kronecker description of any ℚ–definable irreducible component of V_{f} immediately yields both the Cayley–Lagrange resolvent LAG_{f}(T_{1}, …, T_{d}, Z) and a full description (via a primitive element) of the normal closure K(f). Now, we introduce a new collection of multivariate polynomial equations in ℚ[X_{1}, …, X_{d}] :

g_{i}(X_{1}, …, X_{d}) := f(X_{i}), for every i, 1 ≤ i ≤ d.

Let us consider now the zero–dimensional algebra : B(f) := ℚ[X_{1}, …, X_{d}]/(g_{1}, …, g_{d}). Let V′_{f} ⊂ ℂ^{d} be the ℚ–definable algebraic set formed by all common complex zeros of the system of equations :

g_{1} = 0, …, g_{d} = 0.

Then, the following statement holds :

Lemma 70 Let ζ := (ζ_{1}, …, ζ_{d}) ∈ V′_{f} be a complex point such that ζ_{i} ≠ ζ_{j}, ∀i ≠ j, 1 ≤ i, j ≤ d. Let V_{ζ} ⊂ V′_{f} be the ℚ–definable irreducible component of V′_{f} containing ζ. Then, V_{ζ} is also a ℚ–definable irreducible component of V_{f}.

In particular, we conclude that LAG_{f}(T_{1}, …, T_{d}, Z) and a primitive element of K(f) can be easily computed from a Kronecker’s description of any ℚ–definable irreducible component V_{ζ} of V′_{f}, where

ζ := (ζ_{1}, …, ζ_{d}) ∈ V′_{f} ⊂ ℂ^{d} and ζ_{i} ≠ ζ_{j} for all i ≠ j.

Moreover, we obviously have

deg V_{ζ} = [K(f) : ℚ] = ♯Gal_{ℚ}(f) and ht(ζ) ≤ log(d + 1) + h.

Thus, applying the methods and techniques described in Subsection 5.5 above, we conclude that both the Cayley-Lagrange resolvent of f over ℚ and a description of K(f) by a primitive element can be computed from an approximate zero z ∈ ℚ[i]^{d} of the system G with associated zero ζ := (ζ_{1}, …, ζ_{d}) ∈ V′_{f}, such that

ζ_{i} ≠ ζ_{j}, for all i ≠ j.

The running time of this procedure is polynomial in

d h ♯Gal_{ℚ}(f).

Now, we have the following statement.

Lemma 71 With the same assumptions and notations as above, let ζ = (ζ_{1}, …, ζ_{d}) ∈ V′_{f} be a zero of the system G. Then, for every \underline{z} := (z_{1}, …, z_{d}) ∈ ℚ[i]^{d}, the following are equivalent properties :

i) For every i, 1 ≤ i ≤ d, z_{i} is an approximate zero of f with associated zero ζ_{i} ∈ ℂ.

ii) The point \underline{z} ∈ ℚ[i]^{d} is an approximate zero of G with associated zero ζ := (ζ_{1}, …, ζ_{d}).

Proof.– This is an obvious fact since the Newton operator N_{G} splits as a direct sum of the univariate Newton operators N_{g_{1}}, …, N_{g_{d}}. Namely, the following holds :

N_{G}(\underline{x}) := ( \begin{matrix}N_{g_{1}}(x_{1}) & ⋯ & 0 \\ ⋮ & ... & ⋮ \\ 0 & ⋯ & N_{g_{d}}(x_{d}) \end{matrix} )

for every \underline{x} := (x_{1}, …, x_{d}) ∈ ℂ^{d}.

Thus, the Cayley–Lagrange resolvent of f over ℚ and the splitting field K(f) can be computed just by computing a list \underline{z} := (z_{1}, …, z_{d}) ∈ ℚ[i]^{d} of Gauss rationals, such that the following two properties hold :

• For every i, 1 ≤ i ≤ d, z_{i} is an approximate zero of f with associated zero ζ_{i} ∈ ℂ.

• For every i, j, 1 ≤ i, j ≤ d, i ≠ j, ζ_{i} ≠ ζ_{j}.

This task can be performed in time polynomial in the degree d and the (logarithmic) weight wt(f) of f. Applying the method described in Subsection 5.5, Theorem 63, the next Theorem follows.

Theorem 72 There exists a bounded error probability Turing machine M that performs the following task : Given as input a squarefree univariate polynomial f := a_{d}X^{d}+, …, +a_{0} ∈ ℤ[X] with integer coefficients, of degree d and height at most h, the machine M outputs :

i) a description of the normal closure of f over ℚ, K(f), and

ii) the Cayley–Lagrange resolvent of f over ℚ.

The running time of M is polynomial in the following quantities :

d h ♯Gal_{ℚ}(f).

References

[AH92] Leonard M. Adleman and Ming-Deh A. Huang. Primality testing and abelian varieties over finite fields. Springer-Verlag, Berlin, 1992.

[AM93] A. O. L. Atkin and F. Morain. Elliptic curves and primality proving. Math. Comp., 61(203):29–68, 1993.

[Art51] Emil Artin. Algebraic numbers and algebraic functions. I. Institute for Mathematics and Mechanics, New York University, New York, 1951.

[BCSS98a] Lenore Blum, Felipe Cucker, Michael Shub, and Steve Smale. Complexity and real computation. Springer-Verlag, New York, 1998. With a foreword by Richard M. Karp.

[BCSS98b] Lenore Blum, Felipe Cucker, Mike Shub, and Steve Smale. Algebraic setting for the problem P ≠ NP. preprint, 20 pages, 1998.

[BDG88] J. L. Balcázar, J. Díaz, and J. Gabarró. Structural complexity I, volume 11 of EATCS. Springer, 1988.

[Ber75] D. N. Bernstein. The number of roots of a system of equations. Funkts. Anal. Pril., 9:1–4, 1975.

[BGS93] J.-B. Bost, H. Gillet, and C. Soulé. Heights of projective varieties and positive green forms. Manuscript I.H.E.S., 1993.

[BVdPV96] E. Bombieri, A. J. Van der Poorten, and J. D. Vaaler. Effective measures of irrationality for cubic extensions of number fields. Ann. Scuola Norm. Sup. Pisa Cl. Sci. (4), 23(2):211–248, 1996.

[Cam] Paul Camion. Factorisation des polynômes de f_{q}[X]. Rev. CETHEDEC Cahier, 1981(2):5–21 (1982).

[Cam83] Paul F. Camion. Improving an algorithm for factoring polynomials over a finite field and constructing large irreducible polynomials. IEEE Trans. Inform. Theory, 29(3):378–385, 1983.

[Cas97] J. W. S. Cassels. An introduction to the geometry of numbers. Springer-Verlag, Berlin, 1997. Corrected reprint of the 1971 edition.

[CGH^{+}99] D. Castro, M. Giusti, J. Heintz, G. Matera, and L. M. Pardo. Data structures and smooth interpolation procedures in elimination theory. Manuscript, 1999.

[Cia82] Philippe G. Ciarlet. Introduction à l’analyse numérique matricielle et à l’optimisation. Masson, Paris, 1982.

[CZ81] David G. Cantor and Hans Zassenhaus. A new algorithm for factoring polynomials over finite fields. Math. Comp., 36(154):587–592, 1981.

[Ded96] Jean-Pierre Dedieu. Approximate solutions of numerical problems, condition number analysis and condition number theorem. In The mathematics of numerical analysis (Park City, UT, 1995), pages 263–283. Amer. Math. Soc., Providence, RI, 1996.

[Ded97a] Jean-Pierre Dedieu. Condition number analysis for sparse polynomial systems. In Foundations of computational mathematics (Rio de Janeiro, 1997), pages 75–101. Springer, Berlin, 1997.

[Ded97b] Jean-Pierre Dedieu. Condition operators, condition numbers, and condition number theorem for the generalized eigenvalue problem. Linear Algebra Appl., 263:1–24, 1997.

[Ded97c] Jean-Pierre Dedieu. Estimations for the separation number of a polynomial system. J. Symbolic Comput., 24(6):683–693, 1997.

[Dem89] Demazure. Catastrophes et Bifurcations. Ellipses–X École Polytechnique, 1989.

[Dix82] J. Dixon. Exact solution of linear equations using p-adic expansions. Numer. Math., 40:137–141, 1982.

[DSa] J. P. Dedieu and M. Shub. Newton’s method for overdetermined systems of equations. Math. Comp.

[DSb] Jean-Pierre Dedieu and Mike Shub. On simple double zeros and badly conditioned zeros of analytic functions of n variables. Math. Comp., page 0 (electronic).

[DS98] Jean-Pierre Dedieu and Steve Smale. Some lower bounds for the complexity of continuation methods. J. Complexity, 14(4):454–465, 1998.

[Duc97] L. Ducos. Effectivité en Thréorie de Galois. Sous-resultants. PhD thesis, Université de Poitiers, 1997.

[EY36] C. Eckardt and G. Young. The approximation of one matrix by another of lower rank. Psichometruka, 1:211–218, 1936.

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

[Ful84] W. Fulton. Intersection Theory. Number 3 in Ergebnisse der Mathematik. Springer, 2 edition, 1984.

[GH91] M. Giusti and J. Heintz. Algorithmes - disons rapides - pour la décomposition d’ une variété algébrique en composantes irréductibles et équidimensionelles. In T. Mora and C. Traverso, editors, Proceedings of MEGA’90, volume 94 of Progress in Mathematics, pages 169–194. Birkhäuser, 1991.

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

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

[GHM^{+}98] M. Giusti, J. Heintz, J. E. Morais, J. Morgenstern, and L. M. Pardo. Straight–line programs in geometric elimination theory. J. of Pure and App. Algebra, 124:101–146, 1998.

[GHMP95] M. Giusti, J. Heintz, J. E. Morais, and L. M. Pardo. When polynomial equation systems can be solved fast ? In G. Cohen, H. Giusti, and T. Mora, editors, Applied Algebra, Algebraic Algorithms and Error Correcting Codes, Proceedings AAECC-11, volume 948 of LNCS, pages 205–231. Springer, 1995.

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

[GS99] M. Giusti and E. Schost. Solving some over–determined systems. To appear in Proc. ISSAC, 1999.

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

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

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

[HM97] K. Hägele and J. L. Montaña. Polynomial random test for the equivalence problem of integers given by arithmetic circuits. Preprint 4/97 Depto. Matemáticas, Universidad de Cantabria, Santander, Spain, January 1997.

[HMPS] K. Hägele, J.E. Morais, L.M. Pardo, and M. Sombra. On the intrinsic complexity of arithmetic nullstellensatz. To appear in J. of Pure and App. Algebra.

[HS82] J. Heintz and C. P. Schnorr. Testing polynomials which are easy to compute. In Logic and Algorithmic, volume 30 of Monographie de l’Enseignement Mathématique, pages 237–254, 1982.

[IM83] O. H. Ibarra and S. Moran. Equivalence of straight-line programs. Journal of the ACM, 30:217–228, 1983.

[Kal90] Erich Kaltofen. Polynomial factorization 1982–1986. In Computers in mathematics (Stanford, CA, 1986), pages 285–309. Dekker, New York, 1990.

[Kal92] Erich Kaltofen. Polynomial factorization 1987–1991. In I. Simon, editor, Proceedings of the 1st Latin American Symposium on Theoretical Informatics LATIN ’92 (São Paulo, Brazil, April 1992), volume 583 of LNCS, pages 294–313, Berlin-Heidelberg-New York-London-Paris-Tokyo-Hong Kong, 1992. Springer-Verlag.

[Kim85] Myong-Hi Kim. Computational complexity of the Euler type algorithms for the roots of complez polynomials. PhD thesis, The City University of New York, 1985.

[Kim88] Myong-Hi Kim. On approximate zeros and rootfinding algorithms for a complex polynomial. Math. Comp., 51(184):707–719, 1988.

[Kim89] Myong-Hi Kim. Topological complexity of a root finding algorithm. J. Complexity, 5(3):331–344, 1989.

[KLL84] R. Kannan, A. K. Lenstra, and L. Lovasz. Polynomial factorization and nonrandomness of bits of algebraic and some transcendental numbers. In Proceedings of the 16th Ann. ACM Symposium on Theory of Computing (Washington, D.C.), pages 191–200, New York, 1984. ACM, ACM Press.

[KLL88] R. Kannan, A. K. Lenstra, and L. Lovász. Polynomial factorization and nonrandomness of bits of algebraic and some transcendental numbers. Math. Comp., 50(181):235– 250, 1988.

[Kön03] J. König. Einleitung in die allgemeine Theorie der algebraischen Grözen. Druck und Verlag von B.G. Teubner,Leipzig., 1903.

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

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

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

[Kus76] A. G. Kushnirenko. Newton polytopes and the bezout theorem. Funkts. Anal. Pril., 10(3), 1976.

[Lan83] S. Lang. Fundamentals of Diophantine Geometry. Springer, 1983.

[Lan85] S. Landau. Factoring polynomials over algebraic number fields. SIAM J. Comp., 14:184–195, 1985.

[Lan97] S. Lang. Survey of diophantine geometry. Springer–Verlag, 1997.

[Len83] A. K. Lenstra. Factoring polynomials over algebraic number fields. In Computer algebra (London, 1983), pages 245–254. Springer, Berlin, 1983.

[Len84] A. K. Lenstra. Polynomial factorization by root approximation. In John Fitch, editor, Proceedings of the 3rd International Symposium on Symbolic and Algebraic Computation EUROSAM 84 (Cambridge, England, July 9-11, 1984), volume 174 of LNCS, pages 272–276, Berlin-Heidelberg-New York-London-Paris-Tokyo-Hong Kong, 1984. ACM SIGSAM, SAME, Springer-Verlag.

[LLL82a] A. K. Lenstra, H. W. Lenstra, and L. Lovasz. Factoring polynomials with rational coefficients. Technical Report 82-05, Mathematics Dept., University of Amsterdam, 1982.

[LLL82b] A. K. Lenstra, H. W. Lenstra, Jr., and L. Lovász. Factoring polynomials with rational coefficients. Mathematische Ann., 261:513–534, 1982.

[LM85] S. Landau and G. L. Miller. Solvability by radicals is in polynomial time. J. Comp. System Sci., 30:179–208, 1985.

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

[Mal93] G. Malajovich. On the Complexity of Path-Following Newton Algorithms for Solving Systems of Polynomial Equations with Integer Coeficients. PhD thesis, University of California at Berkeley, U.S.A., 1993.

[Mal94] G. Malajovich. On generalized newton algorithms: quadratic convergence, pathfollowing and error analysis. Theoretical Computer Science, 133:65–84, 1994.

[Mal95] G. Malajovich. Worst possible condition number of polynomial systems. preprint 17 pages, 1995.

[McC76] P. J. McCarthy. Algebraic Extensions of Fields. Chelsea Publishing Comp., New York, 1976.

[Mig89] Maurice Mignotte. Mathématiques pour le calcul formel. Presses Universitaires de France, Paris, 1989.

[MMP96] J. L. Montaña, J. E. Morais, and L. M. Pardo. Lower bounds for arithmetic networks II: Sum of betti numbers. Applicable Algebra in Engineering Communications and Computing, 7:41–51, 1996.

[Mor90] Morain. Distributed primality proving and the primality of (2^{3}539 + 1)/3. In EURO-CRYPT: Advances in Cryptology: Proceedings of EUROCRYPT, 1990.

[Mor91] François Morain. Elliptic curves, primality proving and some titanic primes. Astérisque, (198-200):245–251 (1992), 1991. Journées Arithmétiques, 1989 (Luminy, 1989).

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

[MP93] J. L. Montaña and L. M. Pardo. Lower bounds for arithmetic networks. In Applied Algebra, Algebraic Algorithms and Error Correcting Codes, Proceedings of AAECC-4, pages 1–24. Springer, 1993.

[MPR91] J. L. Montaña, L. M. Pardo, and T. Recio. The non-scalar model of complexity in computational geometry. In C. Traverso and T. Mora, editors, Effective Methods in Algebraic Geometry, Proceedings of MEGA’90, volume 94 of Progress in Mathematics, pages 347–361. Birkhäuser, 1991.

[Par95] L. M. Pardo. How lower and upper complexity bounds meet in elimination theory. In G. Cohen, H. Giusti, and T. Mora, editors, Applied algebra, algebraic algorithms and error-correcting codes (Paris, 1995), volume 948 of Lecture Notes in Computer Science, pages 33–69. Springer, Berlin, 1995.

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

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

[Phi95] P. Philippon. Sur des hauteurs alternatives, III. J. Math. Pures Appl., 74:345–365, 1995.

[PZ89] M. Pohst and H. Zassenhaus. Algorithmic algebraic number theory. Cambridge University Press, Cambridge, 1989.

[Ren87] James Renegar. On the worst-case arithmetic complexity of approximating zeros of polynomials. Journal of Complexity, 3(2):90–113, June 1987.

[Ros94] H. E. Rose. A course in number theory. The Clarendon Press Oxford University Press, New York, second edition, 1994.

[Sch79] J. T. Schwartz. Probabilistic algorithms for verification of polynomial identities. In ISSAC ’79: Proceedings of Int’l. Symp. on Symbolic and Algebraic Computation, volume 72 of Lecture Notes in Computer Science. Springer-Verlag, 1979.

[Sch80] W. M. Schmidt. Diophantine Approximation. Springer Verlag, New York, 1980.

[Sch81] Arnold Schönhage. The fundamental theorem of algebra in terms of computational complexity. Preliminary report, Mathematisches Institut der Universität Tübingen, 1981.

[Sch86] Arnold Schönhage. Equation solving in terms of computational complexity. In Proceedings of the International Congress of Mathematicians, volume 3, page 40, 1986.

[SG86] J. Kilian S. Goldwasser. Almost all primes can be quickly certified. In 18th Annual ACM Symp. on Theory of Computing, pages 316–329, 1986.

[Sma81] S. Smale. The fundamental theorem of algebra and complexity theory. Bulletin of the Amer. Math. Soc., (4):1–36, 1981.

[Sma85] S. Smale. On the efficiency of algorithms of analysis. Bull. of the AMS, 13(2):87–121, 1985.

[Sma86a] S. Smale. Algorithms for solving equations. In Proceedings of the International Congress of Mathematicians, pages 172–195, Berkeley, California, USA, 1986.

[Sma86b] S. Smale. Newton’s method estimates from data at one point. Springer, 1986.

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

[SS85] M. Shub and S. Smale. Computational complexity: on the geometry of polynomials and a theory of cost. I. Ann Sci. École Norm. Sup., 18:107–142, 1985.

[SS86] M. Shub and S. Smale. Computational complexity: on the geometry of polynomials and a theory of cost. II. SIAM Journal on Computing, 15(1):145–161, 1986.

[SS93a] M. Shub and S. Smale. Complexity of Bézout’s theorem I: Geometric aspects. J. of the AMS, 6(2):459–501, 1993.

[SS93b] M. Shub and S. Smale. Complexity of Bézout’s theorem II: Volumes and probabilities. In Proceeding effective methods in Algebraic Geometry, volume 109 of Progress in Mathematics, pages 267–285. MEGA ’92, Niece, Birkhäuser, 1993.

[SS93c] M. Shub and S. Smale. Complexity of Bézout’s theorem III: Condition number and packing. J. of Complexity, 9:4–14, 1993.

[SS94a] M. Shub and S. Smale. Complexity of Bézout’s theorem IV: Probability of success, extensions. SIAM J. of Numer. Anal., to appear, 1994.

[SS94b] M. Shub and S. Smale. Complexity of Bézout’s theorem V: Polynomial time. Theor. Comp. Sci., 133:141–164, 1994.

[SS96] Michael Shub and Steve Smale. Complexity of Bezout’s theorem. IV. probability of success and extensions. SIAM Journal on Numerical Analysis, 33(1):128–148, February 1996.

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

[Stu96] B. Sturmfels. Gröbner bases and Convex Polytopes, volume 8 of University Lecture Series. American Mathematical Society, 1996.

[Tyl94] S. Tyler. The Lagrange Spectrum in Projective Space over a Local Field. PhD thesis, University of Texas at Austin, 1994.

[Vog84] W. Vogel. Results on Bézout’s Theorem. Tata Institute of Fundamental Research. Springer, 1984.

[Yak95a] Jean-Claude Yakoubsohn. Une constante universelle pour la convergence de la méthode de Newton. C. R. Acad. Sci. Paris Sér. I Math., 320(3):385–390, 1995.

[Yak95b] Jean-Claude Yakoubsohn. A universal constant for the convergence of Newton’s method and an application to the classical homotopy method. Numer. Algorithms, 9(3-4):223–244, 1995.

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

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

[ZS58] Oscar Zariski and Pierre Samuel. Commutative Algebra, volume 1. D. Van Nostrand Co., Inc., Princeton, 1958. with the co-operation of I. S. Cohen.