Polar Varieties, Real Equation Solving and Data Structures: The Hypersurface Case ^{∗}

B. Bank ^{1}, M. Giusti ^{2}, J. Heintz ^{3},

G. M. Mbakop ^{1}

July 14, 1997

Dedicated to Shmuel Winograd

This paper is published in
Journal of Complexity, Vol.  13, pages 5--27, 1997.

Abstract

In this paper we apply for the first time a new method for multivariate equation solving which was developed in [18], [19], [20] for complex root determination to the real case. Our main result concerns the problem of finding at least one representative point for each connected component of a real compact and smooth hypersurface.

The basic algorithm of [18], [19], [20] yields a new method for symbolically solving zero-dimensional polynomial equation systems over the complex numbers. One feature of central importance of this algorithm is the use of a problem–adapted data type represented by the data structures arithmetic network and straight-line program (arithmetic circuit). The algorithm finds the complex solutions of any affine zerodimensional equation system in non-uniform sequential time that is polynomial in the length of the input (given in straight–line program representation) and an adequately defined geometric degree of the equation system.

∗Research partially supported by the Spanish government grant DGICT, PB93-0472-C02-02 1Humboldt-Universität zu Berlin, Untern den Linden 6, D–10099 Berlin, Germany.

bank@mathematik.hu-berlin.de, mbakop@mathematik.hu-berlin.de 2GAGE, Centre de Mathématiques, École Polytechnique, F-91228 Palaiseau Cedex, France.

giusti@ariana.polytechnique.fr 3Dept. de Matemáticas, Estadística y Computación, Facultad de Ciencias, Universidad de Cantabria, E-39071 Santander, Spain. heintz@matsun1.unican.es

Replacing the notion of geometric degree of the given polynomial equation system by a suitably defined real (or complex) degree of certain polar varieties associated to the input equation of the real hypersurface under consideration, we are able to find for each connected component of the hypersurface a representative point (this point will be given in a suitable encoding). The input equation is supposed to be given by a straight-line program and the (sequential time) complexity of the algorithm is polynomial in the input length and the degree of the polar varieties mentioned above.

Keywords: Real polynomial equation solving, polar variety, geometric degree, straightline program, arithmetic network, complexity

1 Introduction

The present article is strongly related to the main complexity results and algorithms in [18], [19], [20]. Whereas the algorithms developed in these papers concern solving polynomial equation systems over the complex numbers, here we deal with the problem of real solving. More precisely, we consider the particular problem of finding real solutions of a single equation f(x) = 0, where f is an n–variate polynomial of degree d ≥ 2 over the rationals which is supposed to be a regular equation of a compact and smooth hypersurface of IR^{n}. Best known complexity bounds for this problem over the reals are of the form d^{O(n)}, counting arithmetic operations in lQ at unit cost (see [23], [22], [50], [26], [27], [28], [6], [41], [42], [1]).

Complex root finding methods cannot be applied directly to real polynomial equation solving just by looking at the complex interpretation of the input system. If we want to use a complex root finding method for a problem over the reals, some previous adaptation or preprocessing of the input data becomes necessary. In this paper we show that certain polar varieties associated to our input affine hypersurface possess specific geometric properties, which permits us to adapt the complex main algorithm designed in the papers [18], [19], [20] to the real case.

This algorithm is of intrinsic type, which means that it allows us to distinguish between semantical and syntactical properties of the input system in order to profit from both for an improvement of the complexity estimates compared with more ”classical” procedures (as e.g. [25], [44], [5], [30], [24], [34], [35], [10], [8], [14], [6], [17], [32], [31], [9]). The papers [18], [19] and [20] show that the geometric degree of the input system is associated with the intrinsic complexity of solving the system algorithmically when the complexity is measured in terms of the number of arithmetic operations in lQ. The paper [18] is based on the somewhat unrealistic complexity model in which certain FOR instructions executable in parallel count at unit cost. This drawback of the complexity model is corrected in the paper [19] at the price of introducing algebraic parameters in the straight–line programs and arithmetic networks occurring there. These algebraic parameters are finally eliminated in the paper [20], which contains a procedure satisfying our complexity requirement and is completely rational.

We show that the algorithmic method of the papers [18], [19] and [20] is also applicable to the problem of (real) root finding in the case of a compact and smooth hypersurface of IR^{n}, given by an n−variate polynomial f of degree d with rational coefficients which represents a regular equation of that hypersurface. It is possible to design an algorithm of intrinsic type using the same data structures as in [20], namely arithmetic networks and straight-line programs over lQ (the straight–line programs – which are supposed to be division–free – are used for the coding of input system, intermediate results and output). In the complexity estimates the notion of (geometric) degree of the input system of [18], [19], [20] has then to be replaced by the (complex or real) degree of the polar varieties which are associated to the input equation.

The basic computation model used in our algorithm will be that of an arithmetic network with parameters in lQ (compare with [20]). Our first complexity result is the following:

There is an arithmetic network of size (ndδL)^{O(1)} with parameters in the field of the rational numbers which finds at least one representative point in every connected component of a smooth compact hypersurface of IR^{n} given by a regular equation f ∈ lQ[X_{1}, …, X_{n}] of degree d ≥ 2. Here L denotes the size of a suitable straight-line program which represents the input of our procedure coding the input polynomial f. Moreover, δ denotes the maximal geometric degree of suitably defined polar varieties associated to the input equation f.

The network size (ndδL)^{O(1)} involves the maximal geometric degree of certain complex polar varieties associated to the equation f. The answer concerning the algorithmic problem is satisfactory. However, this is not the case with respect to the network size that measures the complexity of the underlying algorithm, because the size depends, besides n, d, and L, on the parameter δ, which is related to complex considerations rather than to real ones. Our second complexity result deals with a procedure showing a complexity that is polynomial only in a suitably defined real degree of the associated polar varieties instead of their geometric degree. The second complexity result relies on two algorithmic assumptions which are very strong in theory, but hopefully not so restrictive in practice. We assume now that a factorization procedure for univariate polynomials over lQ being ”polynomial” in a suitable sense (e.g. counting arithmetic operations in lQ at unit cost) is available and that we are able (also at polynomial cost) to localize regions where a given multivariate polynomial has ”many” real zeros (if there exist such regions). This second assumption may be replaced by the following more theoretical one (which, however, is simpler to formulate precisely): we suppose that we are able to decide in polynomial time whether a given multivariate polynomial has a real zero (however we do not suppose that we are able to exhibit such a zero if there exists one). We call an arithmetic network extended if it uses subroutines of these two types.

Let notations and assumptions be as before. Suppose furthermore that f represents a regular equation of a nonempty smooth and compact real hypersurface. Then there exists an extended arithmetic network which finds at least one representative point for each connected component of the real hypersurface given by f. The size of this arithmetic network is (ndδ^{∗}L)^{O(1)}, where δ^{∗} denotes the suitably defined maximal real degree of the polar varieties mentioned above.

Complexity results in a similar sense for the specific problem of numerical polynomial equation solving can be found in [49], following an approach initiated in [45], [46], [47], [48] (see also [12], [13]). In the same sense one might also want to mention [7] and [15] as representative contributions for the sparse viewpoint. For more details we refer the reader to [40] and [20] and the references cited therein.

2 Polar Varieties

As usual, let lQ, IR and lC denote the field of rational, real and complex numbers, respectively. The affine n–spaces over these fields are denoted by lQ^{n}, IR^{n} and lC^{n}, respectively. Further, let lC^{n} be endowed with the Zariski topology of lQ−definable algebraic sets, where a closed set consists of all common zeros of a finite number of polynomials with coefficients in lQ. Let W ⊂ lC^{n} be a closed subset with respect to this topology and let W = C_{1} ∪ ⋯ ∪ C_{s} be its decomposition into irreducible components with respect to the same topology. Thus W, C_{1}, …, C_{s} are algebraic subsets of lC^{n}. We call W equidimensional if all its irreducible components C_{1}, …, C_{s} have the same dimension.

In the following we need the notion of (geometric) degree of an affine algebraic variety. Let W be an equidimensional Zariski closed subset of lC^{n}. If W is zero–dimensional, the degree of W, denoted by degW, is defined as the cardinality of W (neither multiplicities nor points at infinity are counted). If W is of positive dimension r, then we consider the collection M of all (n − r)-dimensional affine linear subspaces, given as the solution set in lC^{n} of a linear equation system L_{1} = 0, …, L_{r} = 0 where for 1 ≤ k ≤ r the equation L_{k} is of the form L_{k} = ∑_{j=1}^{n} a_{kj}x_{j} + a_{k0} with a_{kj} being rational. Let M_{W} be the subcollection of M consisting of all affine linear spaces H ∈ M such that the affine variety H ∩ W satisfies H ∩ W ≠ ∅ and dim(H ∩ W) = 0. Then the geometric degree of W is defined as degW := max{deg(W ∩ H)|H ∈ M_{W} }.

For an arbitrary Zariski closed subset W of lC^{n}, let W = C_{1} ∪ ⋯ ∪ C_{s} be its decomposition into irreducible components. As in [24] we define its geometric degree as degW := degC_{1} + ⋯ + degC_{s}. Let W be a Zariski closed subset of lC^{n} of dimension n − i given by a regular sequence of polynomials f_{1}, …, f_{i} ∈ lQ[X_{1}, …, X_{n}].

Definition 1 For 1 ≤ j ≤ s, the irreducible component C_{j} is called a real component of W if the real variety C_{j} ∩ IR^{n} contains a smooth point of C_{j}. Let us write

I := {j ∈ IN|1 ≤ j ≤ s, C_{j} is a real component of W }.

Then the (complex) affine variety W^{∗} := ⋃_{j∈I} C_{j} is called the real part of W. We call deg^{∗}W :=

degW^{∗} = ∑_{j∈I} degC_{j} the real degree of the algebraic set W.

Remark 2 (i) deg^{∗}W = 0 holds if and only if the real part W^{∗} of W is empty.

(ii) Note that ”smooth point of C_{j}” in Definition 1 is somewhat ambiguous and should be interpreted following the context. Thus ”smooth point of C_{j}” may just mean that the tangent space of C_{j} is of dimension (n − i) at such a point, or, more restrictively, it may mean that the hypersurfaces defined by the polynomials f_{1}, …, f_{i} intersect transversally in such a point.

Proposition 3 Let f ∈ lQ[X_{1}, …, X_{n}] be a nonconstant and square-free polynomial and let W := {x ∈ lC^{n}|f(x) = 0} be the set of complex zeros of the equation f(x) = 0. Furthermore, consider for any fixed i, 0 ≤ i < n, the complex variety

W̃_{i} := \{x ∈ lC^{n}|f(x) = \frac{∂f(x)}{∂X_{1}} = ⋯ = \frac{∂f(x)}{∂X_{i}} = 0\}

(here W̃_{0} is understood to be W). Suppose that the variables X_{1}, …, X_{n} are in generic position with respect to f. Then any point of W̃_{i} being a smooth point of W is also a smooth point of W̃_{i}. More precisely, at any such point the Jacobian of the equation system f = \frac{∂f(x)}{∂X_{1}} = ⋯ = \frac{∂f(x)}{∂X_{i}} = 0 has maximal rank, i.e., the hypersurfaces defined by the polynomials f, \frac{∂f}{∂X_{1}} , …, \frac{∂f}{∂X_{i}} intersect transversally in this point.

Proof: Consider the nonsingular linear transformation x = A^{(i)}y, where the new variables are y = (Y_{1}, …, Y_{n}). Suppose that A^{(i)} is given in the form

( \begin{matrix}I_{i,i} & 0_{i,n−i} \\ (a_{kl})_{n−i,i} & I_{n−i,n−i} \end{matrix} )  (1)

where I_{i,i} and 0_{i,(n−i)} denote the i × i unit and the i × (n − i) zero matrix, respectively, and where a_{kl} are arbitrary complex numbers for i + 1 ≤ k ≤ n and 1 ≤ l ≤ i. Since the square matrix A^{(i)} has full rank, the transformation x = A^{(i)}y defines a linear change of coordinates. In the new coordinates, the variety W̃_{i} takes the form

W̃_{i}:=\{y ∈ lC^{n}|f(y)= \frac{∂f(y)}{∂Y_{1}} + ∑_{j=i+1}^{n}a_{j1} \frac{∂f(y)}{∂Y_{j}} =⋯= \frac{∂f(y)}{∂Y_{i}} + ∑_{j=i+1}^{n}a_{ji} \frac{∂f(y)}{∂Y_{j}} =0\} .

The coordinate transformation given by A^{(i)} induces a morphism of affine spaces Φ_{i} : lC^{n} × lC^{(n−i)i} ⟶ lC^{i+1} defined by

Φ_{i} (Y_{1}, …, Y_{i}, …, Y_{n}, a_{i+1,1}, …, a_{n,1}, …, a_{i+1,i}, …, a_{n,i}) =

(f, \frac{∂f}{∂Y_{1}} + ∑_{j=i+1}^{n} a_{j1} \frac{∂f}{∂Y_{j}} , …, \frac{∂f}{∂Y_{i}} + ∑_{j=i+1}^{n} a_{ji} \frac{∂f}{∂Y_{j}} ) .

For the moment let

α := (α_{1}, …, α_{n+(n−i)i}) := (Y_{1}, …, Y_{n}, a_{i+1,1}, …, a_{n,i}) ∈ lC^{n} × lC^{(n−i)i}

Then the Jacobian matrix J(Φ_{i})(α) of Φ_{i} in α is given by

J(Φ_{i})(α) = ( \begin{matrix}\frac{∂f}{∂Y_{1}} & ⋯ & \frac{∂f}{∂Y_{n}} & 0 & ⋯ & 0 & ⋯ & ⋯ & 0 \\ ∗ & ⋯ & ∗ & \frac{∂f}{∂Y_{i+1}} & ⋯ & \frac{∂f}{∂Y_{n}} & 0 ⋯ & ⋮ & 0 \\ ⋮ & & ⋮ & ... & ... & 0 & ⋯ & ... & 0 \\ ∗ & ⋯ & ∗ & 0 ⋯ & 0 ⋯ & ⋯ & \frac{∂f}{∂Y_{i+1}} & ⋯ & \frac{∂f}{∂Y_{n}} \end{matrix} ) (α)

Suppose that we are given a point α^{0} = (Y_{1}^{0}, …, Y_{n}^{0}, a_{i+1,1}^{0}, … a_{n,i}^{0}) which belongs to the fiber Φ_{i}^{−1}(0) and suppose that (Y_{1}^{0}, …, Y_{n}^{0}) is a point of the hypersurface W in which the equation f is regular (i.e., we suppose that not all partial derivatives of f vanish in that point). Let us consider the Zariski open neighbourhood U of (Y_{1}^{0}, …, Y_{n}^{0}) consisting of all points of lC^{n} in which at least one partial derivative of f does not vanish. We claim now that the restricted map

Φ_{i} : U × lC^{(n−i)i} ⟶ lC^{i+1}

is transversal to the origin 0 = (0, …, 0) of lC^{i+1}. In order to prove this assertion we consider an arbitrary point α = (Y_{1}, …, Y_{n}, a_{i+1,1}, …, a_{n,i}) of U × lC^{(n−i)i} which satisfies Φ_{i}(α) = 0. Thus (Y_{1}, …, Y_{n}) belongs to U ∩ W and is therefore a point of the hypersurface W in which the equation f is regular. Let us now show that the Jacobian matrix of Φ_{i} has maximal rank in α. If this is not the case, the partial derivatives \frac{∂f}{∂Y_{i+1}} , …, \frac{∂f}{∂Y_{n}} must vanish in the point (Y_{1}, …, Y_{n}). Then the relation Φ_{i}(α) = 0 implies that the derivatives \frac{∂f}{∂Y_{1}} , …, \frac{∂f}{∂Y_{i}} at the point (Y_{1}, …, Y_{n}) vanish, too.

This contradicts the fact that the equation f is regular in that point. Therefore the Jacobian matrix of Φ_{i} has maximal rank in α, which means that α is a regular point of Φ_{i}. Since α was an arbitrary point of Φ_{i}^{−1}(0) ∩ (U × lC^{(n−i)i}), our claim follows. Applying the algebraic– geometric form of the Weak Transversality Theorem of Thom-Sard (see e.g. [21]) to the diagram

Φ_{i}^{−1}(0) ∩ (U × lC^{(n−i)i}) ↪ lC^{n} × lC^{(n−i)i}
↘  ↓
lC^{(n−i)i}

one concludes that the set of all matrices (a_{kl})_{n−i,i} ∈ IR^{(n−i)i} for which transversality holds is Zariski dense in lC^{(n−i)i}. More precisely, the affine space lQ^{(n−i)i} contains a nonempty Zariski open set of matrices A^{(i)} such that the corresponding coordinate transformation (1) leads to the desired smoothness of W̃_{i} in points which are smooth in W. □

The proof of Proposition 3 could also be given using a linear transformation of the variables with a generic nonsingular n × n matrix instead of the generic one in ”triangular form” used here. However, our transformation is sufficiently generic to show Proposition 3 and exhibits the benefit that it invokes only ”sparse transformations” of the equations, which is necessary in the following.

Let f ∈ lQ[X_{1}, …, X_{n}] be a nonconstant square-free polynomial and let again W := {x ∈ lC^{n}|f(x) = 0} be the hypersurface defined by f. Let Δ ∈ lQ[X_{1}, …, X_{n}] be the polynomial Δ := ∑_{j=1}^{n} (\frac{∂f}{∂X_{j}} )^{2}. Consider the real variety V := W ∩ IR^{n} and suppose that:

• V is nonempty and bounded (and hence compact)

• the gradient of f is different from zero in all points of V (i.e., V is a smooth hypersurface in IR^{n} and f = 0 is its regular equation)

• the variables X_{1}, …, X_{n} are in generic position.

Under these assumptions the following problem adapted notion of polar variety is meaningful and remains consistent with the more general definition of the same concept (see e.g. [36]).

Definition 4 Let 0 ≤ i < n. Consider the linear subspace X^{i} of lC^{n} corresponding to the linear forms X_{i+1}, …, X_{n}, i.e., X^{i} := {x ∈ lC^{n}|X_{i+1}(x) = ⋯ = X_{n}(x) = 0}. Then the algebraic subvariety W_{i} of lC^{n} defined as the Zariski closure of the set

\{x ∈ lC^{n}|f(x) = \frac{∂f(x)}{∂X_{1}} = ⋯ = \frac{∂f(x)}{∂X_{i}} = 0, Δ(x) ≠ 0\}

is called the (complex) polar variety of W associated to the linear subspace X^{i} of lC^{n}. The respective real variety is denoted by V_{i} := W_{i} ∩ IR^{n} and called the real polar variety of V associated to the linear subspace X^{i} ∩ IR^{n} of IR^{n}. Here W_{0} is understood to be the Zariski closure of the set {x ∈ lC^{n}; f(x) = 0, Δ(x) ≠ 0} and V_{0} is understood to be V.

Remark 5 Since by assumption V is a nonempty compact hypersurface of IR^{n} and the variables X_{1}, …, X_{n} are in generic position, we deduce from Proposition 3 and general considerations on Lagrange multipliers (as e.g. in [26]) or Morse Theory (as e.g. in [38]) that the real polar variety V_{i} is nonempty and smooth for any 0 ≤ i < n. In particular, the complex variety W_{i} is not empty and the hypersurfaces of lC^{n} given by the polynomials f, \frac{∂f}{∂X_{1}} , …, \frac{∂f}{∂X_{i}} intersect transversally in some dense Zariski open subset of W_{i} (observe that any element of {x ∈ lC^{n}; f(x) = 0, Δ(x) ≠ 0} is a smooth point of W and apply Proposition 3).

Let us observe that the assumption V smooth implies that the polar variety V_{i} can be written as V_{i} = \{x ∈ IR^{n}; f(x) = \frac{∂f(x)}{∂X_{1}} = ⋯ \frac{∂f(x)}{∂X_{i}} = 0\} for any 0 ≤ i ≤ n.

Theorem 6 Let f ∈ lQ[X_{1}, …, X_{n}] be a nonconstant square-free polynomial and let Δ := ∑_{j=1}^{n} (\frac{∂f}{∂X_{j}} )^{2}. Let W := \{x ∈ lC^{n}|f(x) = 0\} be the hypersurface of lC^{n} given by the polynomial

f. Further, suppose that V := W ∩ IR^{n} is a nonempty, smooth and bounded hypersurface of IR^{n} with regular equation f. Assume that the variables X_{1}, …, X_{n} are in generic position. Finally, for any i, 0 ≤ i < n, let the complex polar variety W_{i} of W and the real polar variety V_{i} of V be defined as above. With these notations and assumptions we have :

• V_{0} ⊂ W_{0} ⊂ W, with W_{0} = W if and only if f and Δ are coprime,

• W_{i} is a nonempty equidimensional affine variety of dimension n − (i + 1) being smooth in all its points which are smooth points of W,

• the real part W_{i}^{∗} of the complex polar variety W_{i} coincides with the Zariski closure in lC^{n} of the real polar variety

V_{i} = \{x ∈ IR^{n}|f(x) = \frac{∂f(x)}{∂X_{1}} = ⋯ = \frac{∂f(x)}{∂X_{i}} = 0\} ,

• the ideal (f, \frac{∂f}{∂X_{1}} , …, \frac{∂f}{∂X_{i}} )_{Δ} is radical.

Proof: The first statement is obvious, because W_{0} is the union of all irreducible components of W on which Δ does not vanish identically.

We show now the second statement. Let 0 ≤ i < n be arbitrarily fixed. Then the polar variety W_{i} is nonempty by Remark 5. Moreover, the hypersurfaces of lC^{n} defined by the polynomials f, \frac{∂f}{∂X_{1}} , …, \frac{∂f}{∂X_{n−1}} intersect any irreducible component of W_{i} transversally in a nonempty Zariski open set. This implies that the algebraic variety W_{i} is a nonempty equidimensional variety of dimension n − (i + 1) and that the polynomials f, \frac{∂f}{∂X_{1}} , …, \frac{∂f}{∂X_{n−1}} form a regular sequence in the ring obtained by localizing lQ[X_{1}, …, X_{n}] by the polynomials which do not vanish identically on any irreducible component of W_{i}. More exactly, the polynomials f, \frac{∂f}{∂X_{1}} , …, \frac{∂f}{∂X_{i}} form a regular sequence in the localized ring lQ[X_{1}, …, X_{n}]_{Δ}. From Proposition 3 we deduce that W_{i} is smooth in all points which are smooth points of W and that the hypersurfaces of lC^{n} defined by the polynomials f, \frac{∂f}{∂X_{1}} , …, \frac{∂f}{∂X_{i}} intersect transversally in these points.

Let us show the third statement. The Zariski closure of V_{i} in lC^{n} is contained in W_{i}^{∗} (this is a simple consequence of the smoothness of V_{i}). One obtains the reverse inclusion as follows: let x^{∗} ∈ W_{i}^{∗} be an arbitrary point, and let C be an irreducible component of W_{i}^{∗} containing this point. Since C is a real component of W_{i} the set C ∩ IR^{n} is not empty and contained in W_{i}. The polar variety W_{i} is contained in the algebraic set W̃_{i} := \{x ∈ lC^{n}|f(x) = \frac{∂f(x)}{∂X_{1}} =

= ⋯ = \frac{∂f(x)}{∂X_{i}} = 0\}. Therefore, we have C ∩ V_{i} ≠ ∅. Moreover, the hypersurfaces of IR^{n} defined by the polynomials f, \frac{∂f}{∂X_{1}} , …, \frac{∂f}{∂X_{i}} cut out transversally a dense subset of C ∩ V_{i}. Thus we have

\begin{aligned}n − (i + 1) & = dim_{IR}(C ∩ V_{i}) = dim_{IR}R(C ∩ V_{i}) = \\ & = dim_{l C}R((C ∩ V_{i})′) ≤ dim_{l C}C = n − (i + 1). \end{aligned}

(Here R(C ∩ V_{i}) denotes the set of smooth points of C ∩ V_{i} and (C ∩ V_{i})′ denotes the complexification of C ∩ V_{i}.) Thus, dim_{l C}(C ∩ V_{i})′ = dim_{l C}C = n − (i + 1) and, hence, C = (C ∩ V_{i})′. Moreover, (C ∩ V_{i})′ is contained in the Zariski closure of V_{i} in lC^{n}, which implies that C is contained in the Zariski closure of V_{i} as well.

Finally, we show the last statement. Let us consider again the algebraic set

W̃_{i} := \{x ∈ lC^{n}|f(x) = \frac{∂f(x)}{∂X_{1}} = ⋯ = \frac{∂f(x)}{∂X_{i}} = 0\}

which contains the polar variety W_{i}. Let C′ be any irreducible component of W_{i}. Then C′ is also an irreducible component of W̃_{i}. Moreover, the polynomial Δ does not vanish identically on C′. By Remark 5 there exists now a smooth point x^{∗} of W̃_{i} which is contained in C′ and in which the hypersurfaces of lC^{n} given by the polynomials f, \frac{∂f}{∂X_{1}} , …, \frac{∂f}{∂X_{i}} intersect transversally.

Let x^{∗} = (X_{1}^{∗}, …, X_{n}^{∗}) ∈ lC^{n} be fixed in that way. Consider the local ring O_{_{W_{i}},x^{∗}} of the point x^{∗} in the variety W̃_{i} (i.e., O_{_{W_{i}},x^{∗}} is the ring of germs of rational functions of W̃_{i} that are defined in the point x^{∗}). Algebraically the local ring O_{_{W_{i}},x^{∗}} is obtained by dividing the polynomial ring lC[X_{1}, …, X_{n}] by the ideal (f, \frac{∂f}{∂X_{1}} , …, \frac{∂f}{∂X_{i}}), which defines W̃_{i} as an affine variety, and then localizing at the maximal ideal (X_{1} − X_{1}^{∗}, …, X_{n} − X_{n}^{∗}) of the point x^{∗} = (X_{1}^{∗}, …, X_{n}^{∗}). Using now standard arguments from commutative algebra and algebraic geometry (see e.g. [4]), one infers from the fact that the hypersurfaces of lC^{n} given by the polynomials f, \frac{∂f}{∂X_{1}} , …, \frac{∂f}{∂X_{i}} intersect transversally in x^{∗} the conclusion that O_{_{W_{i}},x^{∗}} is a regular local ring and, hence, an integral domain. The fact that O_{_{W_{i}},x^{∗}} is an integral domain implies that there exists a uniquely determined irreducible component of W̃_{i} which contains the smooth point x^{∗} (this holds true for the ordinary, lC−defined Zariski topology as well as for the lQ−defined one considered here). Therefore, the point x^{∗} is uniquely contained in the irreducible component C′ of W̃_{i} (and of W_{i}). Since the local ring O_{_{W_{i}},x^{∗}} is an integral domain, its zero ideal is prime. This implies that the polynomials f, \frac{∂f}{∂X_{1}} , …, \frac{∂f}{∂X_{i}} generate a prime ideal in the local ring lC[X_{1}, …, X_{n}]_{(X_{1}−X_{1}^{∗},...,X_{n}−X_{n}^{∗})}. Hence, the isolated primary component of the polynomial ideal (f, \frac{∂f}{∂X_{1}} , …, \frac{∂f}{∂X_{i}}) in lQ[X_{1}, …, X_{n}], which corresponds to the irreducible component C′, is itself a prime ideal. Since this is true for any irreducible component of W_{i} and since W_{i} is defined by discarding from W̃_{i} the irreducible components contained in the hypersurface of lC^{n} given by the polynomial Δ, we conclude that the ideal (f, \frac{∂f}{∂X_{1}} , …, \frac{∂f}{∂X_{i}})_{Δ} of lQ[X_{1}, …, X_{n}]_{Δ} is an intersection of prime ideals and, hence, is radical. This completes the proof of Theorem 6. □

Remark 7 Under the assumptions of Theorem 6, we observe that for any i, 0 ≤ i < n, the following inclusions hold among the different nonempty varieties introduced up to now, namely

V_{i} ⊂ V and V_{i} ⊂ W_{i}^{∗} ⊂ W_{i} ⊂ W̃_{i}.

Here V is the bounded and smooth real hypersurface we consider in this paper, W_{i} and V_{i} are the polar varieties introduced in Definition 4, W_{i}^{∗} is the real part of W_{i} according to Definition 1, and W̃_{i} is the complex affine variety introduced in the proof of Theorem 6. With respect to Theorem 6 our settings and assumptions imply that n − (i + 1) = dim_{l C}W_{i} = dim_{l C}W_{i}^{∗} = dim_{IR}V_{i} holds. By our smoothness assumption and the generic choice of the variables we have for the respective sets of smooth points the inclusions:

V_{i} = R(V_{i}) ⊂ R(W_{i}) ⊂ R(W̃_{i}) ⊂ R(W)

(Here W is the affine hypersurface W = {x ∈ lC^{n}|f(x) = 0} of lC^{n}.)

3 Algorithms and Complexity

The preceeding study of adapted polar varieties enables us to state our first complexity result:

Theorem 8 Let n, d, δ, L be natural numbers. Then there exists an arithmetic network N over lQ of size (ndδL)^{O(1)} with the following properties:

Let f ∈ lQ[X_{1}, …, X_{n}] be a nonconstant polynomial of degree at most d and suppose that f is given by a division–free straight–line program β in lQ[X_{1}, …, X_{n}] of length at most L.

Let Δ := ∑_{j=1}^{n} (\frac{∂f}{∂X_{j}} )^{2}, W := \{x ∈ lC^{n}|f(x) = 0\}, V := W ∩ IR^{n} = \{x ∈ IR^{n}|f(x) = 0\} and

suppose that the variables X_{1}, …, X_{n} are in ”sufficiently generic” position. For 0 ≤ i < n let W_{i} be the Zariski closure in lC^{n} of the set

\{x ∈ lC^{n}|f(x) = \frac{∂f(x)}{∂X_{1}} = ⋯ = \frac{∂f(x)}{∂X_{i}} = 0, Δ(x) ≠ 0\}

(thus W_{i} is the polar variety of W associated to the linear space X^{i} = {x ∈ lC^{n}|X_{i+1}(x) = ⋯ = X_{n}(x) = 0} according to Definition 4). Let δ_{i} := degW_{i} be the geometric degree of W_{i} and assume that δ ≥ max{δ_{i}|1 ≤ i < n} holds.

The algorithm represented by the arithmetic network N starts from the straight–line program β as input and decides first whether the complex algebraic variety W_{n−1} is zero–dimensional. If this is the case the network N produces a straight–line program of length (ndδL)^{O(1)} in lQ which represents the coefficients of n + 1 univariate polynomials q, p_{1}, …, p_{n} ∈ lQ[X_{n}] satisfying the following conditions:

1. deg(q) = δ_{n−1} = degW_{n−1}

2. max{deg(p_{i})|1 ≤ i ≤ n} < δ_{n−1}

3. W_{n−1} = {(p_{1}(u), …, p_{n}(u))|u ∈ lC, q(u) = 0}.

Moreover, the algorithm represented by the arithmetic network N decides whether the semialgebraic set W_{n−1} ∩ IR^{n} is nonempty. If this is the case the network N produces not more than δ_{n−1} sign sequences of {−1, 0, 1}^{δ_{n−1}} which codify the real zeros of q ”à la Thom” ([11]). In this way, N describes the nonempty finite set W_{n−1} ∩ IR^{n}.

¿From the output of this algorithm we may deduce the following information:

• If the complex variety W_{n−1} is not zero-dimensional or if W_{n−1} is zero-dimensional and W_{n−1} ∩ IR^{n} is empty we conclude that V is not a compact smooth hypersurface of IR^{n} with regular equation f.

• If V is a compact smooth hypersurface of IR^{n} with regular equation f, then W_{n−1} ∩IR^{n} is nonempty and contains for any connected component of V at least one point which the network N codifies à la Thom as a real zero of the polynomial q.

Remark 9 The hypothesis that the variables X_{1}, …, X_{n} are in ”sufficiently generic” position is not really restrictive since any lQ−linear coordinate change increases the length of the input straight-line program β only by an unessential additive term of O(n^{3}). Moreover, by [29] Theorem 4.4, any genericity condition which the algorithm might require can be satisfied by adding to the arithmetic network N an extra number of nodes which is polynomial in the input parameters n, d, δ, L.

Remark 10 From the Bézout Theorem we deduce the estimation max{δ_{i}|0 ≤ i < n} ≤ d(d−1)^{n−1} < d^{n}. Moreover f can always be evaluated by a division-free straight–line program in lQ[X_{1}, …, X_{n}] of length d^{n}. Thus fixing δ := d(d − 1)^{n−1} and L := d^{n} one is concerned with a worst case situation in which the statement of Theorem 8 just reproduces the main complexity results of [23], [22], [26], [27], [28], [6], [41], [42], [1] in case of a compact smooth hypersurface of IR^{n} given by a regular equation of degree d. The interest in Theorem 8 lies in the fact that δ may be much smaller than the ”Bézout number” d(d − 1)^{n−1} and L smaller than d^{n} in many concrete and interesting cases.

Proof of Theorem 8:

Since by [2] and [39] we may derive the straight-line program β representing the polynomial f in time linear in L, we may suppose without loss of generality that β represents also the polynomial Δ. Applying now the algorithm underlying [19] Proposition 18 together with the modifications introduced by [20] Theorem 28 (compare also [20] Theorem 16 and its proof), we find an arithmetic Network N′ with parameters in lQ of size (ndδL)^{O(1)} which decides whether the polynomials f, \frac{∂f}{∂X_{1}} , …, \frac{∂f}{∂X_{n−1}} form a secant family avoiding the hypersurface of lC^{n} defined by the polynomial Δ. This is exactly the case if W_{n−1} is zero-dimensional.

Suppose now that the polynomials (f, \frac{∂f}{∂X_{1}} , …, \frac{∂f}{∂X_{n−1}} ) form such a secant family. Then the arithmetic network N′ which we obtained before applying [19] Proposition 18 and [20] Theorem 28 to the input f, \frac{∂f}{∂X_{1}} , …, \frac{∂f}{∂X_{n−1}} and Δ produces a straight-line program in lQ which represents the coefficients of polynomials q, p_{1}, …, p_{n} ∈ lQ[X_{n}] characterizing the part W_{n−1} of the complex variety W̃_{n−1} := \{x ∈ lC^{n}|f(x) = \frac{∂f(x)}{∂X_{1}} = ⋯ = \frac{∂f(x)}{∂X_{n−1}} = 0\} which avoids the hypersurface {x ∈ lC^{n}|Δ(x) = 0}. More precisely, the output q, p_{1}, …, p_{n} of the network N′ satisfies the conditions (1), (2), (3) in the statement of Theorem 8.

Now applying for example the main (i.e., the only correct) algorithm of [3] (see also [43] for refinements) by adding suitable comparison gates for positiveness of rational numbers, we may extend N′ to an arithmetic network N of asymptotically the same size (ndδL)^{O(1)}, which decides whether the polynomial q has any real zero. Moreover, without loss of generality the arithmetic network N codifies any existing zeros of q à la Thom (see [11], [43]). From general considerations of Morse Theory (see e.g. [38]) or more elementarily from the results and techniques of [26], [28] one sees that in the case where f is a regular equation of a bounded smooth hypersurface V of IR^{n}, the arithmetic network N codifies for each connected component of V at least one representative point. This finishes the proof of Theorem 8. □

Roughly speaking the arithmetic network N of Theorem 8 decides whether a given polynomial f ∈ lQ[X_{1}, …, X_{n}] is a regular equation of a bounded (i.e., compact) smooth hypersurface V of IR^{n}. If this is the case N computes for any connected component of V at least one representative point. The size of N depends polynomially on the number of variables n, the degree d and the straight-line program complexity L of f and finally on the degree δ of certain complex polar varieties W_{i} associated to the equation f.

The nature of the answer the network N gives us about the algorithmic problem is satisfactory. However, this is not the case for the size of N, which measures the complexity of the underlying algorithm, since this complexity depends on the parameter δ being related rather to the complex considerations than to the real ones. We are going now to describe a procedure whose complexity is polynomial only in the real degree of the polar varieties W_{i} instead of their complex degree. The theoretical (not necessarily the practical) price we have to pay for this complexity improvement is relatively high:

• our new procedure does not decide any more whether the input polynomial is a regular equation of a bounded smooth hypersurface V of IR^{n}. We have to assume that this is already known. Therefore the new algorithm can only be used in order to solve the real equation f = 0, but not to decide its consistency (solving means here that the algorithm produces at least one representative point for each connected component of V).

• our new algorithm requires the support of the following two external subroutines whose theoretical complexity estimates are not really taken into account here although their practical complexity may be considered as ”polynomial”:

– the first subroutine we need is a factorization algorithm for univariate polynomials over lQ. In the bit complexity model the problem of factorizing univariate polynomials over lQ is known to be polynomial ([37]), whereas in the arithmetic model we are considering here this question is more intricate ([16]). In the extended complexity model we are going to consider, the cost of factorizing a univariate polynomial of degree D over lQ, (given by its coefficients) is accounted as D^{O(1)}.

– the second subroutine allows us to discard nonreal irreducible components of the occuring complex polar varieties. This second subroutine starts from a straightline program for a single polynomial in lQ[X_{1}, …, X_{n}] as input and decides whether this polynomial has a real zero (however without actually exhibiting it if there is one). Again this subroutine is taken into account at polynomial cost.

• We call an arithmetic network over lQ extended if it contains extra nodes corresponding to the first and second subroutine.

Fix for the moment the natural numbers n, d, δ^{∗} and L. We suppose that a division-free straight-line program β in lQ[X_{1}, …, X_{n}] of length at most L is given such that β represents a nonconstant polynomial f ∈ lQ[X_{1}, …, X_{n}] of degree at most d. Let again Δ := ∑_{j=1}^{n} (\frac{∂f}{∂X_{j}} )^{2}

and suppose that f is a regular equation of a (nonempty) bounded smooth hypersurface V of IR^{n}. Let W := {x ∈ lC^{n}; f(x) = 0} be the complex hypersurface of lC^{n} defined by the polynomial f and suppose that the variables X_{1}, …, X_{n} are in generic position. Fix 0 ≤ i < n arbitrarily. Let as in Definition 4 the complex variety W_{i} be the Zariski closure in lC^{n} of the set

\{x ∈ lC^{n}|f(x) = \frac{∂f(x)}{∂X_{1}} = ⋯ = \frac{∂f(x)}{∂X_{i}} = 0, Δ(x) ≠ 0\},

i.e., W_{i} is the polar variety of the complex hypersurface W associated to the linear subspace X^{i} := {x ∈ lC^{n}|X_{i+1}(x) = 0, …, X_{n}(x) = 0}.

Let V_{i} := W_{i} ∩ IR^{n} be the corresponding polar variety of the real hypersurface V. Let δ_{i}^{∗} be the real degree of the polar variety W_{i}, i.e., the geometric degree of W_{i}^{∗} (see Definition 1).

By Theorem 6 the quantity δ_{i}^{∗} is also the geometric degree of the Zariski closure in lC^{n} of the real variety V_{i}, i.e., of the complexification of V_{i}. Let r := n − (i + 1). Since the variables X_{1}, …, X_{n} are in generic position with respect to all our geometric data, they are also in Noether position with respect to the complex variety W_{i}, the variables X_{1}, …, X_{r} being free (see [18], [19] for details). Finally, suppose that δ^{∗} ≥ max{δ_{i}^{∗}|0 ≤ i < n} holds.

With these notations and assumptions, we have the following real version of [19] Proposition 17:

Lemma 11 Let n, d, δ^{∗}L be given natural numbers as before and fix 0 ≤ i < n and r := n − (i + 1). Then there exists an extended arithmetic network N with parameters in lQ of size (idδ^{∗}L)^{O(1)} which for any nonconstant polynomial f ∈ lQ[X_{1}, …, X_{n}] satisfying the assumptions above produces a division-free straight-line program β_{i} in lQ[X_{1}, …, X_{r}] such that β_{i} represents a nonzero polynomial ϱ ∈ lQ[X_{1}, …, X_{r}] and the coefficients with respect to X_{r+1} of certain polynomials q, p_{1}, …, p_{n} ∈ lQ[X_{1}, …, X_{r+1}] having the following properties:

(i) the polynomial q is monic and separable in X_{r+1}, and its degree satisfies degq = deg_{X_{r+1}}q = δ_{i}^{∗} = degW_{i}^{∗} ≤ δ^{∗},

(ii) the polynomial ϱ is the discriminant of q with respect to the variable X_{r+1} and its degree can be estimated as degϱ ≤ 2(δ_{i}^{∗})^{3},

(iii) the polynomials p_{1}, …, p_{n} satisfy the degree bounds

max{deg_{X_{r+1}}p_{k}|1 ≤ k ≤ n} < δ_{i}^{∗}, max{degp_{k}|1 ≤ k ≤ n} = 2(δ_{i}^{∗})^{3},

(iv) the ideal (q, ϱX_{1}−p_{1}, …, ϱX_{n}−p_{n})_{ϱ} generated by the polynomials q, ϱX_{1}−p_{1}, …, ϱX_{n}− p_{n} in the localization lQ[X_{1}, …, X_{n}]_{ϱ} is the vanishing ideal of the affine variety (W_{i}^{∗})_{ϱ} := {x ∈ W_{i}^{∗}|ϱ(x) ≠ 0}. Moreover, (W_{i}^{∗})_{ϱ} is a dense Zariski open subset of the complex variety W_{i}^{∗}.

(v) the length of the straight-line program β_{i} is of the order (idδ^{∗}L)^{O(1)}.

Proof: The proof of this lemma follows the general lines of the proof of Theorem 8 and is again based on the algorithm underlying [19] Proposition 17 together with the modifications introduced by [20] Theorem 28. By Theorem 8 above, we know that the polynomials f, \frac{∂f}{∂X_{1}} ,…, \frac{∂f}{∂X_{n−1}} form a secant family avoiding in lC^{n} the hypersurface defined by Δ, and therefore the algorithm of geometric solving due to [20], Section 3, is applicable. In particular, the lifting procedure involved there can be exploited for our purpose.

First we observe that by [2] and [39] we are able to derive the straight-line program β representing the input polynomial f at cost linear in L. Thus we may suppose without loss of generality that β represents both f and Δ.

We show Lemma 11 by the exhibition of a recursive procedure in 0 ≤ i < n under the assumption that the first and second subroutines as introduced before are available. First put i := 0 and let β_{0} be the straight-line program β which represents f and Δ. Since the variables X_{1}, …, X_{n} are in generic position, the polynomials f and Δ are monic with respect to the variable X_{n} and satisfy the conditions d ≥ degf = deg_{X_{n}}f and 2d ≥ degΔ = deg_{X_{n}}Δ.

Let R_{0} := lQ[X_{1}, …, X_{n−1}] and consider f and Δ as univariate polynomials in X_{n} with coefficients in R_{0}. Recall that they are monic. Interpolating them in 2d + 1 arbitrarily chosen distinct rational points, we obtain a division-free straight-line program in R_{0} = lQ[X_{1}, …, X_{n−1}] which represents the coefficients of f and Δ with respect to X_{n}. This straight-line program has length Ld^{O(1)}.

We apply now [19] Lemma 8 in order to obtain the greatest common divisor of f and Δ which is again a monic polynomial in R_{0}[X_{n}] which we may suppose to be given by a division-free straight-line program in R_{0} = lQ[X_{1}, …, X_{n−1}] representing its coefficients with respect to X_{n}. Dividing f by this greatest common divisor in R_{0}[X_{n}] as in the Noether normalization procedure in [19], we obtain a polynomial q̄ ∈ R_{0}[X_{n}] = lQ[X_{1}, …, X_{n}] whose coefficients with respect to the variable X_{n} are represented by a division-free straight-line program β̄_{1} in lQ[X_{1}, …, X_{n−1}]. The polynomial q̄ is monic in X_{n}, it is square-free and it is a divisor of f. Moreover we have that W_{0} = {x ∈ lC^{n}|q̄(x) = 0} and q̄ is the minimal polynomial of the hypersurface W_{0} of lC^{n}. The degree of the polynomial q̄ satisfies the condition degq̄ = deg_{X_{n}} q̄ = degW_{0}.

The straight-line program β̄_{1} which represents the coefficients of q̄ with respect to the variable X_{n} has length (dL)^{O(1)}. In order to finish the recursive construction for the case i := 0 it is sufficient to find the factor q of q̄ which defines the real part W_{0}^{∗} of W_{0}. For this purpose we consider the projection map lC^{n} → lC^{n−1} which maps each point of lC^{n} onto its first n − 1 coordinates. Since the variables X_{1}, …, X_{n} are in generic position, the projection map induces a finite surjective morphism π : W_{0} → lC^{n−1}. We choose a generic lifting point t = (t_{1}, …, t_{n−1}) ∈ lQ^{n−1} with rational coordinates t_{1}, …, t_{n−1} (this is here a generic point t ∈ lQ^{n−1} for the hypersurface W_{0} of the finite morphism π for which the zero-dimensional fibre π^{−1}(t), the lifting fibre, contains only smooth points of W_{0}, for more details see [20], Section 3). Observe that the irreducible components of W_{0} are the hypersurfaces of lC^{n} defined by the lQ-irreducible factors of q̄ which we denote by q_{1}, …, q_{s}.

Without loss of generality we may assume that for 1 ≤ m ≤ s the irreducible polynomials q_{1}, …, q_{m} define the real irreducible components of W_{0}. Thus it is clear that the factor q of q̄ we are looking for is q := q_{1} ⋯ q_{m}. It suffices therefore to find all irreducible factors q_{1}, …, q_{s} of q̄ and then to discard the factors q_{m+1}, …, q_{s}.

In order to find the polynomials q_{1}, …, q_{s}, we specialize the variables X_{1}, …, X_{n−1} into the coordinates t_{1},…, t_{n−1} of the rational point t ∈ lQ^{n−1}. We obtain thus the univariate polynomial q̄(t, X_{n}) := q̄(t_{1}, …, t_{n−1}, X_{n}) ∈ lQ[X_{n}] which decomposes into q̄(t, X_{n}) = q_{1}(t, X_{n}) ⋯ q_{s}(t, X_{n}) in lQ[X_{n}]. Since the lifting point t was chosen generically in lQ^{n−1}, Hilbert’s Irreducibility Theorem (see [33]) implies that the polynomials q_{1}(t, X_{n}),…,q_{s}(t, X_{n}) are irreducible over lQ. Specializing the variables X_{1}, …, X_{n−1} in the straight-line program β̄_{1} into the values t_{1}, …, t_{n−1} we obtain an arithmetic circuit in lQ which represents the coefficients of q̄(t, X_{n}). By a call to the first subroutine we obtain the coefficients of the polynomials q_{1}(t, X_{n}), …, q_{s}(t, X_{n}). Applying to these polynomials the lifting procedure which we are going to explain below in a slightly more general context, we find a divisionfree straight-line program in lQ[X_{1}, …, X_{n−1}] of size (dL)^{O(1)} which represents the coefficients of the polynomials q_{1}, …, q_{s} with respect to the variable X_{n}. In order to finish the case i = 0 we have to identify algorithmically the polynomials q_{1}, …, q_{m} that define the irreducible real components of W_{0} and, hence, those of W^{∗}. Then, the product q = q_{1} ⋯ q_{m} is easily obtained. Observe that q is the minimal polynomial of the hypersurface W_{0}. From the assumption that V = W ∩ IR^{n} is a smooth real hypersurface one deduces that V_{0} = W_{0}^{∗} ∩ IR^{n} = W_{0} ∩ IR^{n} holds. Since f is a regular equation of V and since the polynomials q̄ and q are factors of f, one sees immediately that q̄ and q are also regular equations of V. This implies that each of the polynomials q_{1}, …, q_{s} admitting a real zero x ∈ IR has a non-vanishing gradient in x. Thus, any polynomial of q_{1}, …, q_{s} admitting a real zero belongs to q_{1}, …, q_{m}. Hence, by a call to the second subroutine, we are able to find the polynomials q_{1}, …, q_{m}, and therefore the polynomial q = q_{1} ⋯ q_{m}. Now we extend the division-free straight-line program representing the polynomials q_{1}, …, q_{s} to a circuit in lQ[X_{1}, …, X_{n}] of size (dL)^{O(1)} which computes the polynomial q = q_{1} ⋯ q_{s}. Interpolating q in the variable X_{n} as before, this circuit provides a division-free straight-line program β_{1} in lQ[X_{1}, …, X_{n}] of size (dL)^{O(1)} which represents the coefficients of q with respect to the variable X_{n}. Without changing its order of complexity we extend β_{1} to a division-free circuit in lQ[X_{1}, …, X_{n−1}] that computes also the discriminant ϱ of q with respect to the variable X_{n} and the polynomials ϱX_{1}, …, ϱX_{n−1}. Let p_{1} := ϱX_{1}, …, p_{n−1} := ϱX_{n−1}, p_{n} := ϱX_{n} ∈ lQ[X_{1}, …, X_{n−1}, X_{n}]. One sees immediately that the polynomials ϱ ∈ lQ[X_{1}, …, X_{n−1}] and q, p_{1}, …, p_{n} ∈ lQ[X_{1}, …, X_{n−1}, X_{n}] satisfy the conditions (i) - (iv) of Lemma 11 for i = 0. Furthermore, β_{1} is a division-free straightline program in lQ[X_{1}, …, X_{n−1}] of size (dL)^{O(1)} which computes ϱ and the coefficients of q, p_{1}, …, p_{n} with respect to the variable X_{n}. By construction the output circuit β_{1} can be produced from the input circuit β by an extended arithmetic network over lQ of size (dL)^{O(1)}. This finishes the description of the first stage in our recursive procedure.

We consider now the case of 0 < i < n and set r := n − (i + 1). Suppose that there is given a division-free straight-line program β_{i−1} in lQ[X_{1}, …, X_{r+1}] of size Λ_{i−1} that represents a nonzero polynomial ϱ′ ∈ lQ[X_{1}, …, X_{r+1}] and the coefficients with respect to X_{r+2} of certain polynomials q′, p′_{1}, …, p′_{n} ∈ lQ[X_{1}, …, X_{r+1}, X_{r+2}]. These polynomials have the following properties: q′ is monic and separable in X_{r+2} and satisfies the degree condition degq′ = deg_{X_{r+2}}q′ = δ_{i−1}^{∗}, ϱ′ is the discriminant of q′ with respect to X_{r+2}, the polynomials p′_{1}, …, p′_{n} satisfy the degree bound max{deg_{X_{r+2}}p′_{k}|1 ≤ k ≤ n} < δ_{i−1}^{∗} and the ideal (q′, ϱ′X_{1}−p′_{1}, …, ϱ′X_{n}−p′_{n})_{ϱ′} of the localized ring lQ[X_{1}, …, X_{n}]_{ϱ} is the vanishing ideal of the affine variety (W_{i−1}^{∗})_{ϱ′}. Observe that (W_{i−1}^{∗})_{ϱ′} is a Zariski open dense subset of (W_{i−1}^{∗}). Let Z be the Zariski closure in lC^{n} of \{x ∈ W_{i−1}^{∗}|\frac{∂f(x)}{∂X_{i}} = 0, Δ(x) ≠ 0\}. We have that W_{i}^{∗} ⊂ Z ⊂ W_{i} and Z is at least the union of all real irreducible components of W_{i}. In particular, all irreducible components of Z are irreducible components of W_{i}. Moreover, we have degZ ≤ dδ_{i−1}^{∗}.

Now we apply the procedure underlying [19], Proposition 15, to the straight-line programs β_{i−1} and β representing the polynomials ϱ′, q′, p′_{1}, …, p′_{n} and \frac{∂f}{∂X_{i}} in order to produce an explicit description of the algebraic variety \{x ∈ W_{i−1}^{∗}|\frac{∂f(x)}{∂X_{i}} = 0\}. By means of the algorithm of [19], Subsection 5.1.3, we clear out the irreducible components of this variety contained in the hypersurface {x ∈ lC^{n}|Δ(x) = 0}. Finally, we obtain a division-free straight-line program μ̄ in lQ[X_{1}, …, X_{r}] of size i(L + Λ_{i−1})(dδ_{i−1}^{∗}) which represents a nonzero polynomial ϱ̄ ∈ lQ[X_{1}, …, X_{r}] and the coefficients with respect to X_{r+1} of certain polynomials q̄, p̄_{1}, …, p̄_{n} ∈ lQ[X_{1}, …, X_{r+1}]. The latter polynomials have the following properties: q̄ is monic and separable with respect to X_{r+1} and satisfies the degree condition degq̄ = deg_{X_{r+1}} q̄ = degZ, ϱ̄ is the discriminant of q̄ with respect to X_{r+1}, the polynomials p̄_{1}, …, p̄_{n} satisfy the degree bound max{deg_{X_{r+1}} p̄_{k}|1 ≤ k ≤ n} < degZ, and the ideal (q̄, ϱ̄X_{1} − p̄_{1}, …, ϱ̄X_{n} − p̄_{n})ϱ̄ of the localized ring lQ[X_{1}, …, X_{n}]ϱ̄ is the vanishing ideal of the affine variety Zϱ̄. Observe again that Zϱ̄ is a Zariski open dense subset of Z. By [19], Proposition 15 and Subsection 5.1.3, there exists an arithmetic network N_{i} with parameters in lQ which produces from the input circuits β_{i−1} and β the output circuit μ̄ and has size i(dδ_{i−1}^{∗}LΛ_{i−1})^{O(1)}. Let q_{1}, …, q_{s} ∈ lQ[X_{1}, …, X_{r+1}] be the lQ-irreducible factors of q̄. Since q̄ is monic and separable in X_{r+1}, we have q̄ = q_{1} ⋯ q_{s}. From the assumption that the variables X_{1}, …, X_{n} are in generic position we deduce that each irreducible component of the algebraic variety Z is represented by exactly one of the irreducible polynomials q_{1}, …, q_{s}. This means that Z has s irreducible components, say C_{1}, …, C_{s}, such that for 1 ≤ l ≤ s the irreducible component C_{l} is identical with the Zariski closure in lC^{n} of the set

{x = (X_{1}, …, X_{n}) ∈ lC^{n}| ϱ̄(X_{1}, …, X_{r})X_{1} − p̄_{1}(X_{1}, …, X_{r+1}) = 0,
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
ϱ̄(X_{1}, …, X_{r})X_{n} − p̄_{n}(X_{1}, …, X_{r+1}) = 0,
q_{l}(X_{1}, …, X_{r}) = 0, ϱ̄(X_{1}, …, X_{r}) ≠ 0}.

Now suppose that the real irreducible components of Z (and hence, the one of W_{i}) are represented in this way by the polynomials q_{1}, …, q_{m} and let q := q_{1} ⋯ q_{m}. The polynomial q is monic and separable in X_{r+1} and satisfies the degree condition degq = deg_{X_{r+1}}q = δ_{i}^{∗}. Moreover, we have W_{i}^{∗} = C_{1} ∪ … ∪ C_{m}.

Now we try to find a straight-line program μ whose length is of order (idδ_{i}^{∗}L)^{O(1)} (hence, independent of the length Λ_{i−1} of the circuit β_{i−1}) and which represents the coefficients of the polynomials q_{1}, …, q_{s} and, finally, the polynomial q. Adding to the arithmetic network N_{i} order of (idδ_{i}^{∗}LΛ_{i−1})^{O(1)} extra nodes we find as in the proof of [20], Proposition 30, a ”sufficiently generic” lifting point t = (t_{1}, …, t_{r}) ∈ lQ^{r} for the algebraic variety Z (see [20], Definition 19, for the notion of a lifting point). By the generic choice of the point t we deduce from Hilbert’s Irreducibility Theorem that q_{1}(t, X_{r+1}), …, q_{s}(t, X_{r+1}) are irreducible polynomials of lQ[X_{r+1}]. Thus the identity q̄(t, X_{r+1}) = q_{1}(t, X_{r+1}) ⋯ q_{s}(t, X_{r+1}) represents the decomposition of the polynomial q̄(t, X_{r+1}) ∈ lQ[X_{r+1}] into its irreducible factors. Specializing in the straight-line program μ̄ the variables X_{1}, …, X_{r} into the values t_{1}, …, t_{r} we obtain an arithmetic circuit in lQ that represents the coefficients of the univariate polynomial q̄(t, X_{r+1}). Adding some extra nodes to the arithmetric network, without changing its asymptotic size, we may suppose that N_{i} represents the nonzero rational number ϱ̄(t) and the coefficients of the univariate polynomials q̄(t, X_{r+1}), p̄_{1}(t, X_{r+1}), …, p̄_{n}(t, X_{r+1}). Observe that degq̄(t, X_{r+1}) = deg_{X_{r+1}} q̄ = degq̄ ≤ dδ_{i−1}^{∗} holds. Therefore we are able to find the irreducible factors q_{1}(t, X_{r+1}), …, q_{s}(t, X_{r+1}) of q̄(t, X_{r+1}) by a call to the first subroutine at a supplementary cost of (dδ_{i−1}^{∗})^{O(1)}. Adding to the arithmetic network N_{i}, without changing its asymptotical complexity, some extra nodes we may suppose that N_{i} represents for each 1 ≤ l ≤ s the rational number ϱ̄(t) and the coefficients of the polynomials q_{l}(t, X_{r+1}), p̄_{1}(t, X_{r+1}), …, p̄_{n}(t, X_{r+1}). Observe that N_{i} is now an extended arithmetic network. For a fixed l, 1 ≤ l ≤ s, the set C_{l} ∩({t}× lC^{n−r}) is the lifting fiber of the point t in the irreducible component C_{l} of Z.The polynomials q_{l}(t, X_{r+1}), \frac{1}{ϱ̄(t)} p̄_{1}(t, X_{r+1}), …, \frac{1}{ϱ̄(t)} p̄_{n}(t, X_{r+1}) represent a geometric solution of this lifting fiber. This means that the identity

C_{l} ∩ (\{t\} × lC^{n−r}) = \{(\frac{p̄_{1}(t, u)}{ϱ̄(t)}, …, \frac{p̄_{n}(t, u)}{ϱ̄(t)}) |u ∈ lC, q_{l}(t, u) = 0\}

holds.

Applying the algorithm underlying [20], Theorem 28, to the input β, t = (t_{1}, … t_{r}), ϱ̄(t), q_{l}(t, X_{r+1}), p̄_{1}(t, X_{r+1}), …, p̄_{n}(t, X_{r+1}) we obtain a division-free straight-line program in lQ[X_{1}, …, X_{r}] having a length of order (iddegC_{l}L)^{O(1)} representing the coefficients of the polynomial q_{l} with respect to X_{r+1}. Doing this for each l, 1 ≤ l ≤ s, again we have to add to the extended arithmetic network N_{i} some extra nodes which do not change its asymptotic size. Then we may suppose that N_{i} produces a division-free straight-line program in lQ[X_{1}, …, X_{r}] representing the coefficients of the polynomials q_{1}, … q_{s} with respect to the variable X_{r}. As in the case of i = 0 we discard by a call to the second subroutine the polynomials q_{m+1}, …, q_{s} which do not have any zero in IR^{n}. ¿From the remaining polynomials q_{1}, …, q_{s} we generate q = q_{1} ⋯ q_{s}. The additional costs of discarding q_{m+1}, …, q_{s} and producing q is of order (∑_{l=1}^{s} iddegC_{l}L)^{O(1)} = (iddegZL)^{O(1)} = (idδ_{i−1}^{∗}L)^{O(1)}. Thus, without loss of generality we may suppose that the extended arithmetic network N_{i} produces a divisionfree straight-line program in lQ[X_{1}, …, X_{r}] of size (∑_{l=1}^{s} iddegC_{l}L)^{O(1)} = (idδ_{i−1}^{∗}L)^{O(1)} which represents the coefficients of the polynomial q with respect to the variable X_{r}. We observe that the point t ∈ lQ^{r} is a lifting point of the algebraic variety W_{i}^{∗} = ∪_{l=1}^{s}C_{l}, too. Therefore, the lifting fiber of t in W_{i}^{∗} is given by the rational number ϱ̄(t) and the coefficients of the polynomials q(t, X_{r+1}) and p̄_{1}(t, X_{r+1}), …, p̄(t, X_{r+1}), which, in principle, have already been computed by the arithmetic network N_{i}. Again applying the procedure underlying [20], Theorem 28, to the input β, t = (t_{1}, …, t_{r}), ϱ̄(t), q(t, X_{r+1}), p̄_{1}(t, X_{r+1}), …, p̄_{n}(t, X_{r+1}) we obtain a division-free straight-line program β_{i} in lQ[X_{1}, …, X_{r}] of size Λ_{i} = (idδ_{i}^{∗}L)^{O(1)}. The straight-line program β_{i} represents a nonzero polynomial ϱ ∈ lQ[X_{1}, …, X_{r}] and the coefficients with respect to X_{r+1} of the polynomial q and certain other polynomials p_{1}, …, p_{n} of lQ[X_{1}, …, X_{r}, X_{r+1}] having the properties (i) - (iv) stated in Lemma 11. The extended arithmetic network N_{i} over lQ which produces this output β_{i} from the input β_{i−1} and β has size (idδ_{i−1}^{∗}LΛ_{i−1})^{O(1)}. Observe that the length Λ_{i} of the straight-line program β_{i} is independent of the length Λ_{i−1} of the input circuit β_{i−1}. More precisely, we have Λ_{i} = (idδ_{i}^{∗}L)^{O(1)}. Taking into account that δ_{i}^{∗} ≤ dδ_{i−1}^{∗} and Λ_{i−1} = ((i − 1)dδ_{i−1}^{∗}L)^{O(1)} holds we conclude that the size of the extended arithmetic network N_{i} which produces from the input circuits β_{i−1} and β the output circuits is of order (idδ_{i}^{∗}L)^{O(1)}. Concatenating the networks N_{1}, …, N_{i} we finally obtain an extended arithmetic network N over lQ which produces the straight-line program β_{i} from the input circuit β. The network N is of size (idδ^{∗}L)^{O(1)}. □

¿From Lemma 11 one now easily deduces our main result.

Theorem 12 Let n, d, δ^{∗}, L be natural numbers. Then there exists an extended arithmetic network N over lQ of size (ndδ^{∗}L)^{O(1)} with the following properties: Let f ∈ lQ[X_{1}, …, X_{n}] be a nonconstant polynomial of degree at most d and suppose that f is given by a division-free straight-line program β in lQ[X_{1}, …, X_{n}] of length at most L. Let Δ := ∑_{i=1}^{n} (\frac{∂f}{∂X_{i}} )^{2}, W := \{x ∈ lC^{n}|f(x) = 0\}, V := W ∩ IR^{n} = \{x ∈ IR^{n}|f(x) = 0\} and suppose that the variables X_{1}, …, X_{n} are in ” sufficiently generic” position. Furthermore, suppose that V is a (nonempty) bounded smooth hypersurface of IR^{n} with regular equation f. For 0 ≤ i ≤ n, let W_{i} be the Zariski closure of the set \{x ∈ lC^{n}|f(x) = \frac{∂f(x)}{∂X_{1}} = ⋯ = \frac{∂f(x)}{∂X_{i}} = 0, Δ(x) ≠ 0} and W_{i}^{∗} := W_{i} ∩ IR^{n}. Let δ_{i}^{∗} := deg^{∗}W_{i} := degW_{i}^{∗} be the real degree of the complex variety W_{i} and assume that δ^{∗} ≥ max{δ_{i}^{∗}|0 ≤ i < n} holds. The algorithm represented by the extended arithmetic network N starts from the straightline program β as input and produces a straight-line program in lQ of size (ndδ^{∗}L)^{O(1)}. This straight-line program represents the coefficients of n+1 univariate polynomials q, p_{1}, …, p_{n} ∈ lQ[X_{n}] satisfying the following conditions:

(i) degq = δ_{n−1}^{∗}

(ii) max{degp_{i}|1 ≤ i ≤ n} < δ_{n−1}^{∗}

(iii) Any connected component of the real hypersurface V has at least one point contained

in the set

P := {(p_{1}(u), …, p_{n}(u))|u ∈ IR, q(u) = 0}.

20 Real equation solving

Moreover, the extended algorithmic network N codifies each real zero u of the polynomial q (and hence, the elements of P) ” à la Thom”.

Proof: Just apply Lemma 11 setting i := n − 1. The remaining arguments are the same as in the proof of Theorem 8. □

References

[1] S. Basu, R. Pollack, M.-F. Roy: On the Combinatorial and Algebraic Complexity of Quantifier Elimination. Proc. 35th IEEE Symp. on Foundations of Computer Science (to appear)

[2] W. Baur, V. Strassen : The complexity of partial derivatives, Theoret. Comput. Sci. 22 (1982) 317-330.

[3] M. Ben-Or, D. Kozen, J. Reif: The complexity of elementary algebra and geometry, J. Comput. Syst. Sci. 32 (1986) 251-264

[4] M. Brodmann: Algebraische Geometrie, Birkhäuser Verlag. Basel-Boston-Berlin (1989)

[5] B. Buchberger, Ein algorithmisches Kriterium für die Lösbarkeit eines algebraischen Gleichungssystems, Aequationes math. 4 (1970) 371–383

[6] J. F. Canny: Some Algebraic and Geometric Computations in PSPACE, Proc. 20th ACM Symp. on Theory of Computing (1988) 460-467

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

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

[9] A. L. Chistov: Polynomial-time computation of the dimension of components of algebraic varieties in zerocharacteristic, Preprint Universtité Paris XII (1995)

[10] A. L. Chistov, D. J. Grigor’ev: Subexponential time solving systems of algebraic equations, LOMI Preprints E-9-83, E-10-83, Leningrad (1983)

[11] M. Coste, M.-F. Roy: Thom’s Lemma, the coding of real algebraic numbers and the computation of the topology of semialgebraic sets, J. Symbolic Comput. 5 (1988) 121-130

[12] J.-P. Dedieu, Estimations for the Separation Number of a Polynomial System, Preprint, Univ. Paul Sabatier, Toulouse (1995)

[13] J.-P. Dedieu, Approximate Solutions of Numerical Problems, Condition Number Analysis and Condition Number Theorems, Preprint, Univ. Paul Sabatier, Toulouse (1995)

[14] A. Dickenstein, N. Fitchas, M. Giusti, C. Sessa : The membership problem of unmixed ideals is solvable in single exponential time, Discrete Applied Mathematics 33 (1991) 73–94.

[15] I. Z. Emiris: On the Complexity of Sparse Elimination, ReportNo. UCB/CSD-94/840, Univ. of California (1994)

[16] J. von zur Gathen, G. Seroussi: Boolean circuits versus arithmetic circuits, Information and Computation 91 (1) (1991) 142-154

[17] M. Giusti, J. Heintz: La détermination des points isolés et de la dimension d’une variété algébrique peut se faire en temps polynomial, In Computational Algebraic Geometry and Commutative Algebra, Proceedings of the Cortona Conference on Computational Algebraic Geometry and Commutative Algebra, D. Eisenbud and L. Robbiano, eds., Symposia Matematica, vol. XXXIV, Istituto Nazionale di Alta Matematica, Cambridge University Press (1993).

[18] M. Giusti, J. Heintz, J.E. Morais, L.M. Pardo: When polynomial equation systems can be “solved” fast? in Proc. 11th International Symposium Applied Algebra, Algebraic Algorithms and Error–Correcting Codes, AAECC–11, Paris 1995, G. Cohen, M.Giusti and T. Mora, eds., Springer LNCS 948 (1995) 205–231.

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

[20] M. Giusti, J. Heintz, K. Hägele, J. E. Morais, J. L. Montaña, L. M. Pardo: Lower Bounds for Diophantine Approximations, Preprint Num. 4/1996, Departamento de Matemáticas, Estadistica y Computación, Universidad de Cabtabria, Espania, accepted for MEGA-Publications 1996.

[21] M. Golubitsky, V. Guillemin: Stable Mappings and their Singularities, Springer-Verlag, New York (1986)

[22] D. Grigor’ev: Complexity of deciding Tarski Algebra, J. Symbolic Comput. 3 (1987) 65-108

[23] D. Grigor’ev, N. Vorobjov: Solving Systems of Polynomial Inequalities in Subexponential Time, J. Symbolic Comput.5 (1988), 37-64.

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

[25] G. Hermann: Die Frage der endlich vielen Schritte in der Theorie der Polynomideale, Math. Ann. 95 (1926) 736–788.

[26] J. Heintz, M.–F. Roy, P. Solernó: On the complexity of semialgebraic sets, Proc. Information Processing 89 (IFIP 89) San Francisco 1989, G.X.Ritter, ed., North-Holland (1989) 293–298.

[27] J. Heintz, M.–F. Roy, P. Solernó: Complexité du principe de Tarski–Seidenberg, C. R. Acad. Sci. Paris, t. 309, Série I (1989) 825–830.

[28] J. Heintz, M–F. Roy and P. Solernó: Sur la complexité du principe de Tarski–Seidenberg, Bull. Soc. math. France, 118 (1990) 101–126.

[29] J. Heintz, C.P. Schnorr: Testing polynomials which are easy to compute, Proc. 12th Ann. ACM Symp. on Computing (1980) 262–268; also in Logic and Algorithmic. An International Symposium held in Honour of Ernst Specker, Monographie No. 30 de l’Enseignement de Mathématiques, Genève (1982) 237–254.

[30] J. Heintz, R. Wüthrich : An efficient quantifier elimination algorithm for algebraically closed fields of any characteristic, SIGSAM Bull., vol. 9 No. 4 (1975)

[31] T. Krick, L.M. Pardo: A Computational Method for Diophantine Approximation, in ”Algorithms in Algebraic Geometry and Applications, MEGA’94”, ( L. Gonzales-Vega and T. Recio, Eds.), Progress in Mathematics, Vol. 143, pp 193-254, Birkhäuser, Basel, 1996.

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

[33] S. Lang: Diophantine Geometry, Interscience Publishers John Wiley & Sons, New York, London (1962)

[34] D. Lazard: Algèbre linéaire sur K[X_{1}, …, X_{n}] et élimination, Bull. Soc. Math. France 105 (1977) 165–190

[35] D. Lazard : Résolution des systèmes d’équations algébriques, Theor. Comp. Sci. 15 (1981) 77–110.

[36] D. T. Lê, B. Teissier: Variétés polaires locales et classes de Chern des variétés singuliéres, Annals of Mathematics, 114, (1981), 457-491

[37] A. K. Lenstra, H. W. Lenstra Jr., L. Lovász: Factoring polynomials with rational coefficients, Math. Ann. 261 (1982) 534-543

[38] M. Milnor: On the Betti numbers of real algebraic varieties, Proc. Amer. Math. Soc. 15 (1964) 275-280

[39] J. Morgenstern : How to compute fast a function and all its derivatives, Prépublication No. 49, Université de Nice 1984.

[40] L.M. Pardo: How lower and upper complexity bounds meet in elimination theory, in Proc. 11th International Symposium Applied Algebra, Algebraic Algorithms and Error–Correcting Codes, AAECC–11, Paris 1995, G. Cohen, M.Giusti and T. Mora, eds., Springer LNCS 948 (1995) 33–69.

[41] J. Renegar: A faster PSPACE algorithm for the existential theory of the reals, Proc. 29th Annual IEEE Symposium on the Foundation of Computer Science (FOCS) (1988) 291-295

[42] J. Renegar: On the Computational Complexity and Geometry of the first Order theory of the Reals. J. of Symbolic Comput. (1992), 13(3) : 255-352

[43] M.-F. Roy, A. Szpirglas: Complexity of computation with real algebraic numbers, J. Symbolic Computat. 10 (1990) 39-51

Real equation solving 23

[44] A. Seidenberg: Constructions in Algebra, Transactions Amer. Math. Soc. 197 (1974) 273–313

[45] M. Shub, S. Smale: Complexity of Bezout’s theorem I: Geometric aspects, J. Amer. Math. Soc. 6 (1993), 459-501

[46] M. Shub, S. Smale: Complexity of Bezout’s theorem II: Volumes and probabilities, in Proceedings Effective Methods in Algebraic Geometry, MEGA’92 Nice, 1992, F. Eyssette and A. Galligo, eds. Progress in Mathematics, Vol. 109, Birkhäuser, Basel, (1993) 267-285

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

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

[49] M. Shub, S. Smale: Complexity of Bezout’s theorem V: Polynomial time, Theoretical Comp. Sci. 133 (1994)

[50] P. Solernó: Complejidad de conjuntos semialgebraicos. Thesis Univ. de Buenos Aires (1989)