POLAR VARIETIES AND EFFICIENT REAL ELIMINATION

B. BANK, M. GIUSTI, J. HEINTZ, AND G. M. MBAKOP

Dedicated to Steve Smale

Abstract. Let S_{0} be a smooth and compact real variety given by a reduced regular sequence of polynomials f_{1}, …, f_{p}. This paper is devoted to the algorithmic problem of finding efficiently a representative point for each connected component of S_{0} . For this purpose we exhibit explicit polynomial equations that describe the generic polar varieties of S_{0} . This leads to a procedure which solves our algorithmic problem in time that is polynomial in the (extrinsic) description length of the input equations f_{1}, …, f_{p} and in a suitably introduced, intrinsic geometric parameter, called the degree of the real interpretation of the given equation system f_{1}, …, f_{p}.

Keywords: Real polynomial equation solving, polar variety, geometric degree, arithmetic circuit, arithmetic network, complexity.

1. Introduction

The core of this paper consists in the exhibition of a system of canonical equations which describe locally the generic polar varieties of a given semialgebraic complete intersection manifold S_{0} contained in the real n –dimensional affine space IR^{n}. This purely mathematical description of the polar varieties allows the design of a new type of efficient algorithm (with intrinsic complexity bounds), which computes, in case that S_{0} is smooth and compact, at least one representative point for each connected component of S_{0} (the algorithm returns each such point in a suitable symbolic codification). This new algorithm (and, in particular, its complexity) is the main practical outcome of the present paper. Let us now briefly describe our results. Suppose that the real variety S_{0} is compact and given by polynomial equations of the following form:

f_{1}(X_{1}, …, X_{n}) = ⋯ = f_{p}(X_{1}, …, X_{n}) = 0,

where p, n ∈ IN, p ≤ n and f_{1}, …, f_{p} belong to the polynomial ring Q[X_{1}, …, X_{n}] in the indeterminates X_{1}, …, X_{n} over the rational numbers Q . Let d be a given natural number and assume that for 1 ≤ k ≤ p the total degree deg f_{k} of the polynomial f_{k} is bounded by d. Moreover, we suppose that the polynomials f_{1}, …, f_{p} form a regular sequence in Q [X_{1}, …, X_{n}] and that they are given by a division-free arithmetic circuit of size L that evaluates them in any given point of the real (or complex) n –dimensional affine space IR^{n} (or C^{n}). Further, we assume that the Jacobian J(f_{1}, …, f_{p}) of the equation system f_{1} = ⋯ = f_{p} = 0 has maximal rank in any point of S_{0} (thus, implicitly, we assume that S_{0} is smooth). Let W_{0} := V (f_{1}, …, f_{p}) denote the (complex) algebraic variety defined by the polynomials f_{1}, …, f_{p} in the affine space C^{n}. We denote the singular locus of W_{0} by SingW_{0} . Moreover, let us suppose that the variables X_{1}, …, X_{n} are in generic position with respect to the equation system f_{1}, …, f_{p}. For 1 ≤ i ≤ n − p let W_{i} be the i –th formal (complex) polar variety associated with W_{0} (and the variables X_{p+i}, …, X_{n}).

Research partially supported by the following German, French, Spanish and Argentinian grants:

BA 1257/4-1 (DFG), ARG 018/98 INF (BMBF), UMS 658, ECOS A99E06, DGICYT PB96-0671-C02-02, ANPCyT 03-00000-01593, UBACYT TW 80 and PIP CONICET 4571/96. The first two authors wish to thank the MSRI at Berkeley for its hospitality during their stay, fall 1998.

Further, let us denote the real counterpart of W_{i} by S_{i} := W_{i} ∩ IR^{n}. We call S_{i} the i –th formal real polar variety associated with the real semialgebraic variety S_{0} (and the variables X_{p+i}, …, X_{n}) . It turns out that the (locally) closed sets W_{i} \ SingW_{0} and S_{i} are either empty or complex, or real manifolds of dimension n − (p + i) . Moreover, for 1 ≤ i ≤ n − p, one sees easily that

W̃_{i} := \overline{W_{i} \ SingW_{0}}

is the i –th polar variety (in the usual sense) associated with W_{0} and the variables X_{p+i}, …, X_{n} (here, \overline{W_{i} \ SingW_{0}} denotes the Q-Zariski closure in C^{n} of the quasi– affine variety W_{i} \ SingW_{0} ). For a precise definition of the notion of formal polar varieties and of polar varieties in the usual sense we refer to Section 2. Suppose that the real variety S_{0} is non–empty and satisfies our assumptions. In Theorem 10 of this paper we show that every real polar variety S_{i} = W_{i} ∩ IR^{n}, 1 ≤ i ≤ n − p, is a non–empty, smooth manifold of dimension n − p − i containing at least one point of each connected component of the real variety S_{0} . In particular, the real variety S_{n−p} is a finite set containing at least one representative point of each connected component of S_{0} . Under the same assumptions we show in Theorem 8 that for 1 ≤ i ≤ n−p the quasi– affine variety W_{i}\SingW_{0} is a locally complete intersection that satisfies the Jacobian criterion. More precisely, the quasi–affine variety W_{i} \ SingW_{0} is a smooth manifold of codimension p + i that can be described locally by certain regular sequences consisting of the polynomials f_{1}, …, f_{p} and i many well–determined p –minors of the Jacobian J(f_{1}, …, f_{p}) of the f_{1}, …, f_{p}. In particular, the quasi–affine variety W_{n−p} \ SingW_{0} is zero-dimensional, whence W̃_{n−p} = W_{n−p} \ SingW_{0} . Thus W̃_{n−p} is a zero-dimensional complex variety that contains a representative point of each connected component of the real variety S_{0} . The practical outcome of Theorem 8 and Theorem 10 consists in the design of an efficient algorithm (with intrinsic complexity bounds), which adapts the elimination procedure for complex algebraic varieties developed in [30] and [31] to the real case. Under the additional assumption that, for 1 ≤ k ≤ p, the intermediate ideal (f_{1}, …, f_{k}) generated by f_{1}, …, f_{k} in Q [X_{1}, …, X_{n}] is radical, we shall apply this procedure to the p\binom{n}{p−1} well–determined equation systems of Theorem 8, which

describe the zero-dimensional algebraic variety W̃_{n−p} = W_{n−p} \ SingW_{0} locally. In order to find at least one representative point for every connected component of the real variety S_{0} , we have just to run the procedure of [30] and [31] on all these equation systems. Counting arithmetic operations in Q at unit costs, this can be done in sequential time

\binom{n}{p − 1}L(ndδ)^{O(1)},

where δ is the following geometric (and therefore, intrinsic) invariant:

δ := max\{max\{deg \overline{V (f_{1}, …, f_{k}) \ SingW_{0}}|1 ≤ k ≤ p\},
max{deg W̃_{i}|1 ≤ i ≤ n − p}}

(here, deg \overline{V (f_{1}, …, f_{k}) \ W_{0}} and deg W̃_{i} denote the geometric degree in the sense of [37] of the corresponding algebraic varieties). This is the content of Theorem 11 below. For any 1 ≤ k ≤ p and any 1 ≤ i ≤ n − p the quantity δ bounds the degree of the algebraic variety \overline{V (f_{1}, …, f_{k}) \ SingW_{0}} and of the i –th polar variety W̃_{i} = \overline{W_{i} \ SingW_{0}} . In [30] and [31] the quantity max{deg V (f_{1}, …, f_{i})|1 ≤ i ≤ p} is called the geometric degree (of the complex interpretation) of the equation system f_{1}, …, f_{p}. In analogy to this terminology, we shall call δ the geometric degree of the real interpretation of the equation system f_{1}, …, f_{p}. In view of the complexity result above we shall understand the parameter δ as an intrinsic measure for the size of the real interpretation of the given polynomial equation system. In order to make our complexity result more transparent we are going now to exhibit, in terms of extrinsic parameters, some estimations for the intrinsic system degree δ. Let us write d_{1} := deg f_{1}, …, d_{p} := deg f_{p} and let D := d_{1} ⋯ d_{p} denote the classical Bézout number of the polynomial system f_{1}, …, f_{p}. Then we have the following degree estimations for the complex algebraic variety W_{0} = V (f_{1}, …, f_{p})

deg \overline{S_{0}} ≤ deg W_{0} ≤ D ≤ d^{p},

\overline{S_{0}} denotes again the Q-Zariski closure in C^{n} of the real variety S_{0} . On the other hand, we conclude from Theorem 8 that, for every i, 1 ≤ i ≤ n−p, the polar variety W̃_{i} is defined by the initial system f_{1}, …, f_{p} and certain p –minors of the Jacobian J(f_{1}, …, f_{p}) . Let us denote the maximum degree of these p –minors by c_{i}. It turns out that for, any 1 ≤ i ≤ n − p, the polar variety W̃_{i} is a codimension one subvariety of W̃_{i−1} . Now one sees easily that the quantity D_{i} := D c_{1} ⋯ c_{i} represents a reasonable ”Bézout number” of the variety W̃_{i} and that this Bézout number satisfies the estimate deg W̃_{i} ≤ D_{i}. Putting all this together, we deduce the following estimate for the intrinsic system degree δ:

δ ≤ D_{n−p} = Dc_{1} ⋯ c_{n−p}.

Observing that for any i, 1 ≤ i ≤ n − p, the inequality c_{i} ≤ d_{1} + ⋯ + d_{p} − p holds, we find the estimations:

δ ≤ D(d_{1} + ⋯ + d_{p} − p)^{n−p} ≤ d^{p}(pd − p)^{n−p} < p^{n−p}d^{n}.

In conclusion, our new real algorithm has a time complexity that is, in worst case, polynomial in the ”Bézout number” Dc_{1} ⋯ c_{n−p} of the zero–dimensional polar variety W̃_{n−p}.

Our complexity bound \binom{n}{p−1}L(ndδ)^{O(1)} depends on the intrinsic (geometric, semantic) parameter δ and on the extrinsic (algebraic) parameters d and n in a polynomial manner, and it depends on the syntactic parameter L only linearly. In this sense one may consider our complexity bound as intrinsic. Our real algorithm promises therefore to be practically applicable to special equation systems with low value for the intrinsic parameter δ.

On the other hand, even in worst case our algorithm improves upon the known d^{O(n)} – time procedures for the algorithmic problem under consideration, also in their most efficient versions [4], [5] (see also [3], [12], [19], [39], [40], [41], [59], [60], [14], [13]). However, this distinction does not become apparent when we measure complexities simply in terms of d and n (all mentioned algorithms have worst–case complexities of type d^{O(n)} ), but it becomes clearly visible when we use the ”Bézout number” just introduced as complexity parameter. Only our new algorithm is polynomial in this quantity. On the other hand, we are only able to reach our goal of algorithmic efficiency by means of a strict limitation to a purely geometric point of view. For the moment there is no hope that any of the standard questions of real algebra (e.g. finding generators for the real radical of a polynomial ideal or the formulation of an effective real Nullstellensatz) can be solved within the complexity framework of this paper (compare [52], [7] and [8]).

Our (algorithmic and mathematical) methods and results represent a non–obvious generalization of the main outcome of [1], where an intrinsic type algorithm was designed for the problem of finding at least one representative point in each connected component of a real, compact hypersurface given by an n –variate, smooth polynomial equation f of degree d ≥ 2 with rational coefficients (such that f represents a regular equation of that hypersurface). This is the particular case of codimension p = 1 of the present paper, and our setting leads to the complexity bound L(ndδ)^{O(1)} proved in [1].

2. Polar Varieties

2.1. Notations, Notions and General Assumptions. Let X_{1}, …, X_{n} be indeterminates (or variables) over the rational numbers Q and let polynomials f_{1}, …, f_{p} ∈ Q[X_{1}, …, X_{n}] with 1 ≤ p ≤ n be given. Let C^{n} and IR^{n} denote the n –dimensional affine space over the complex and the real numbers, respectively. We think C^{n} to be equipped with the Q -Zariski topology, whereas, on IR^{n}, we consider the strong topology. For any subset U ⊂ C^{n} we denote its Q -Zariski–closure by \overline{U}. By X := (X_{1}, …, X_{n}) we denote the vector of variables X_{1}, …, X_{n} and by x := (x_{1}, …, x_{n}) any point of the affine space C^{n} or IR^{n}. We suppose that the polynomials f_{1}, …, f_{p} form a reduced regular sequence in Q [X_{1}, …, X_{n}] . The Jacobian of these polynomials is denoted by

J(f_{1}, …, f_{p}) := [\frac{∂f_{k}}{∂X_{j}} ]\begin{matrix}1≤k≤p \\ 1≤j≤n \end{matrix} .

For any point x ∈ C^{n} we write

J(f_{1}, …, f_{p})(x) := [\frac{∂f_{k}}{∂X_{j}} (x)]\begin{matrix}1≤k≤p \\ 1≤j≤n \end{matrix}

for the Jacobian of the polynomials f_{1}, …, f_{p} at x. The common complex zeros of the polynomials f_{1}, …, f_{p} form an affine, Q-definable subvariety of C^{n}, which we denote by

W_{0} := V (f_{1}, …, f_{p}) := {x ∈ C^{n}|f_{1}(x) = … = f_{p}(x) = 0}.

A point x ∈ W_{0} = V (f_{1}, …, f_{p}) is said to be smooth (in W_{0} ) if the rank of the Jacobian of f_{1}, …, f_{p} in x satisfies the condition rk J(f_{1}, …, f_{p})(x) = p. Otherwise x is called a singular point of W_{0} . By SingW_{0} we denote the set of all singular points of W_{0} .

Remark 1. If x ∈ W_{0} is smooth, then the hypersurfaces defined by the polynomials f_{1}, …, f_{p} intersect transversally at the point x.

Definition 2. For every i, 1 ≤ i ≤ n − p, let Δ_{i} denote the set of all common complex zeros of all p -minors of the Jacobian J(f_{1}, …, f_{p}) corresponding to the columns {1, …, p + i − 1}. In other words, Δ_{i} is the determinantal variety defined by all p-minors of the submatrix J_{1}^{p+i−1}(f_{1}, …, f_{p}) determined by the columns {1, …, p + i − 1} of the Jacobian J(f_{1}, …, f_{p}) . We introduce the affine variety

W_{i} := W_{0} ∩ Δ_{i}

associated with the linear subspace of C^{n}, namely

X^{p+i−1} := {x ∈ C^{n}|X_{p+i}(x) = … = X_{n}(x) = 0}

and call W_{i} the i –th formal polar variety of W_{0} . By

W̃_{i} := \overline{W_{i} \ SingW_{0}}

we denote the i –th polar variety (in the usual sense) of the variety W_{0} .

Remark 3. • The index i reflects the expected codimension of the formal polar variety W_{i} in W_{0} . With respect to the ambient space C^{n}, one has always codim W_{i} ≥ p + i.

• According to our notation, the common zeros of all p –minors of the Jacobian J(f_{1}, …, f_{p}) form the determinantal variety Δ_{n−p+1} . Obviously, we have Sing W_{0} = W_{0} ∩ Δ_{n−p+1} = W_{n−p+1} .

• The formal polar varieties W_{i}, 1 ≤ i ≤ n − p, form a decreasing sequence. In particular, we have W_{0} ⊃ W_{1} ⊃ ⋯ ⊃ W_{i} ⊃ ⋯ ⊃ W_{n−p} ⊃ W_{n−p+1} = Sing W_{0} .

The concept of polar variety goes back to J.–V. Poncelet. Its development has a long history: Let us mention among others the contributions of F. Severi, J. A. Todd, S. Kleiman, R. Piene, D. T. Lê, B. Teissier, J.–P. Henry, M. Merle ... (see e.g. [58] and the references quoted there).

2.2. Local Description of the Determinantal Varieties. In this subsection we develop a succinct local description of the determinantal varieties Δ_{i}, 1 ≤ i ≤ n − p. The following general Exchange Lemma will be our main tool for this description (this lemma is used in a similar form in [32]). It describes an exchange relation between certain minors of a given matrix . Let A be a given (p×n) -matrix with entries a_{ij} from an arbitrary commutative ring. Let l and k be any natural numbers with l ≤ n and k ≤ min{p, l}. Furthermore, let I_{k} := (i_{1}, …, i_{k}) be an ordered sequence of k different elements from the finite set of natural numbers {1, …, l} and let M_{A} (I_{k}) := M_{A}(i_{1}, …, i_{k}) denote the k - minor of the matrix A built up by the first k rows and the columns i_{1}, …, i_{k}. If it is clear by the context what is the matrix A, we shall just write M(i_{1}, …, i_{k}) := M (I_{k}) := M_{A} (I_{k}) .

Lemma 4 (Exchange Lemma). As before let a matrix A and natural numbers l and k be given, as well as two intersecting index sets I_{k} = (i_{1}, …, i_{k}) and I_{k−1} = (j_{1}, …, j_{k−1}) . Then, for suitable numbers ε_{j} ∈ {1, −1} with j ∈ I_{k} \ I_{k−1} we have the following identity:

(∗) M (I_{k−1}) M (I_{k}) = ∑_{j∈I_{k}\I_{k−1}} ε_{j} M (I_{k} \ {j}) M (I_{k−1} ∪ {j}) .

Proof Consider the following ((2k − 1) × (2k − 1)) -matrix L with entries from the given matrix A:

L := [ \begin{matrix}& L_{1}(I_{k}) \\ O & ⋮ \\ & L_{k−1}(I_{k}) \\ L_{1}(I_{k−1}) & L_{1}(I_{k}) \\ ⋮ & ⋮ \\ L_{k}(I_{k−1}) & L_{k}(I_{k}) \end{matrix} ] .

Here, for any 1 ≤ j ≤ k, L_{j} (I_{k}) denotes the row vector of length k that we obtain selecting, from the j –th row of the matrix A, the k elements placed in the columns I_{k} = (i_{1}, …, i_{k}) . Similarly, L_{j} (I_{k−1}) is obtained from the j –th row of A selecting the k − 1 elements placed in the columns I_{k−1} = (j_{1}, …, j_{k−1}) . Now it is not difficult to verify the identity (∗) by calculating the determinant det L of the quadratic matrix L via Laplace expansion in two different ways. First, by expansion of det L according to the first k − 1 columns of L, we obtain the left–hand side of (∗) , disregarding the sign. Expansion of det L according to the first k − 1 rows of L leads to the right–hand side of (∗) . This implies the identity (∗) for an appropriate choice of the signs ε_{j}, with j ∈ I_{k} \ I_{k−1} . □

Let m ∈ Q [X_{1}, …, X_{n}] denote the (p − 1) –minor of the Jacobian J(f_{1}, …, f_{p}) given by the first (p − 1) rows and columns, i.e., let

m := det [\frac{∂f_{k}}{∂X_{j}} ]\begin{matrix}1≤k≤p−1 \\ 1≤j≤p−1 \end{matrix} .

We consider the determinantal variety Δ_{i} outside of the hypersurface

V (m) := {x ∈ C^{n} | m(x) = 0}

and denote this localization by (Δ_{i})_{m}, i.e., we set

(Δ_{i})_{m} := Δ_{i} \ V (m).

¿From now on, for 1 ≤ i_{1} ≤ ⋯ ≤ i_{p} ≤ n, let us denote by

M(i_{1}, …, i_{p})

the polynomial in Q[X_{1}, …, X_{n}] defined as the p –minor of the Jacobian J(f_{1}, …, f_{p}) built up by its p rows and the columns i_{1}, …, i_{p}. As before, we denote by

M(i_{1}, …, i_{p})(x)

the specialization of M(i_{1}, …, i_{p}) in a given point x ∈ C^{n}.

Proposition 5. Let 1 ≤ i ≤ n − p be arbitrarily fixed, and let m be the (p − 1) – minor defined above. Then the determinantal variety Δ_{i} is locally (i.e., outside of the hypersurface V (m) ) described by the i polynomials

M(1, …, p − 1, p), M(1, …, p − 1, p + 1), …, M(1, …, p − 1, p + i − 1).

In other words, we have

(Δ_{i})_{m} := {x ∈ C^{n}| m(x) ≠ 0, M(1, …, p − 1, s)(x) = 0, s ∈ {p, …, p + i − 1}},

where M(1, …, p−1, s) denotes, as above, the p –minor of the Jacobian J(f_{1}, …, f_{p}) built up by the first p − 1 columns and the s –th column.

Proof It suffices to show that

(Δ_{i})_{m} ⊃ {x ∈ C^{n}| m(x) ≠ 0, M(1, …, p − 1, s) = 0, s ∈ {p, …, p + i − 1}}

holds. Let x^{∗} ∈ C ^{n} be any point satisfying the conditions m(x^{∗}) ≠ 0 and M(1, …, p − 1, s)(x^{∗}) = 0 for every s ∈ {p, …, p + i − 1}. We have to verify that

M(i_{1}, …, i_{p})(x^{∗}) = 0

holds for all ordered p –tuples (i_{1}, …, i_{p}) of elements of {1, …, p + i − 1}. Applying the Exchange Lemma to m = M(1, …, p − 1) and M(i_{1}, …, i_{p}) , we deduce the identity

m(x^{∗})M(i_{1}, …, i_{p})(x^{∗}) =

∑_{j∈{i_{1},... ,i_{p}}\{1,... ,p−1}} ε_{j} M ({i_{1}, …, i_{p}} \ {j}) (x^{∗})M(1, …, p − 1, j)(x^{∗})

for suitable numbers ε_{j} ∈ {1, −1} with j ∈ {i_{1}, …, i_{p}}\{1, …, p−1}. By assumption we have m(x^{∗}) ≠ 0 and M(1, …, p − 1, j)(x^{∗}) = 0 for all j ∈ {p, …, p + i − 1}. This implies that x^{∗} belongs to the set (Δ_{i})_{m}.

□

Notation 6. In the sequel we shall simply write M_{j} for the p – minor M(1, …, p− 1, j) given by the first p−1 columns of J(f_{1}, …, f_{p}) and the column j ∈ {p, …, n} .

Remark 7. • Proposition 5 implies that the codimension of Δ_{i} outside of the

hypersurface V (m) is at most i.

• Proposition 5 holds also for the determinantal variety Δ_{n−p+1} that defines the singular locus Sing W_{0} = W_{n−p+1} of the variety W_{0} . Hence, for any point x^{∗} ∈ C^{n} satisfying the condition m(x^{∗}) ≠ 0 and the n − p + 1 equations

M_{j}(x^{∗}) = 0, j ∈ {p, …, n},

the Jacobian J(f_{1}, …, f_{p})(x^{∗}) becomes singular.

• Replacing the previously chosen (p − 1) -minor m by any other (p − 1) -minor of the Jacobian J(f_{1}, …, f_{p}) , the statement of Proposition 5 remains true mutatis mutandis.

2.3. Local Description of the Formal Polar Varieties. The aim of this subsection is to show the following fact: Let the variables X_{1}, …, X_{n} be in generic position with respect to the polynomials f_{1}, …, f_{p}, and let m̃ be any (p − 1) –minor of the Jacobian J(f_{1}, …, f_{p}) . In this subsection we are going to show that any formal polar variety W_{i}, 1 ≤ i ≤ n − p, is a smooth complete intersection variety outside of the closed set SingW_{0} ∪ V (m̃) . Moreover, we shall exhibit a reduced regular sequence describing this variety outside of SingW_{0} ∪ V (m̃) . As in the previous subsection, let m ∈ Q [X_{1}, …, X_{n}] denote the (p − 1) –minor of the Jacobian J(f_{1}, …, f_{p}) built up by the first (p − 1) rows and columns. Let Y_{1}, …, Y_{n} be new variables and let Y := (Y_{1}, …, Y_{n}) . For any linear coordinate transformation X = AY , with A being a regular (n × n) –matrix, we define the polynomials

G_{1}(Y) := f_{1}(AY), …, G_{p}(Y) := f_{p}(AY).

The Jacobian of G_{1}, …, G_{p} has the form

J(G_{1}, …, G_{p}) := [\frac{∂G_{k}}{∂Y_{j}} ]\begin{matrix}1≤k≤p \\ 1≤j≤n \end{matrix} = J(f_{1}, …, f_{p})A.

Using a similar notation as before, we denote by

M̃(i_{1}, …, i_{p})

the p –minor of the new Jacobian J(G_{1}, …, G_{p}) that corresponds to the columns 1 ≤ i_{1} < ⋯ < i_{p} ≤ n. Moreover, we denote by M̃_{j} the p – minor M̃(1, …, p−1, j) determined by the fixed first p − 1 columns of J(G_{1}, …, G_{p}) and the column j ∈ {p, …, n}.

For p ≤ r, t ≤ n let Z_{r,t} be a new indeterminate. Using the following regular (n − p + 1) × (n − p + 1) –parameter matrix

Z := [ \begin{matrix}1 & 0 & & 0 & & & ⋯ & 0 \\ Z_{p+1,p} & 1 \\ ⋮ & ⋮ & ... & & O & & & ⋮ \\ Z_{p+i−1,p} & Z_{p+i−1,p+1} & ⋯ & 1 \\ Z_{p+i,p} & Z_{p+i,p+1} & ⋯ & Z_{p+i,p+i−1} & 1 \\ ⋮ & ⋮ & & ⋮ & ⋮ & ... & & 0 \\ Z_{n,p} & Z_{n,p+1} & ⋯ & Z_{n,p+i−1} & Z_{n,p+i} & Z_{n,p+i+1} & ⋯ & 1 \end{matrix} ] ,

we construct an (n × n) –coordinate transformation matrix A := A(Z) , which will enable us to prove the statement at the beginning of this subsection.

For the moment, let us fix an index 1 ≤ i ≤ n − p. We consider the formal polar variety W_{i} outside of the hypersurface V (m) . Corresponding to our choice of i, the matrix Z may be subdivided into submatrices as follows:

Z = [ \begin{matrix}Z_{1}^{(i)} & O_{i,n−p−i+1} \\ Z^{(i)} & Z_{2}^{(i)} \end{matrix} ] .

Here the matrix Z^{(i)} is defined as

Z^{(i)} := [ \begin{matrix}Z_{p+i,p} & … & Z_{p+i,p+i−1} \\ … & … & … \\ Z_{np} & … & Z_{n,p+i−1} \end{matrix} ] ,

and Z_{1}^{(i)} and Z_{2}^{(i)} denote the quadratic lower triangular matrices bordering Z^{(i)} in Z, and O_{i,n−p−i+1} is the i × (n − p − i + 1) zero matrix. Let

A := A(Z) := [ \begin{matrix}I_{p−1} & O_{p−1,i} & O_{p−1,n−p−i+1} \\ O_{i,p−1} & Z_{1}^{(i)} & O_{i,n−p−i+1} \\ O_{n−p−i+1,p−1} & Z^{(i)} & Z_{2}^{(i)} \end{matrix} ] .

Here the submatrices I_{r} and O_{r,s} are unit or zero matrices, respectively, of corresponding size, and Z^{(i)}, Z_{1}^{(i)}, and Z_{2}^{(i)} are the submatrices of the parameter matrix Z introduced before. Thus, A is a regular, parameter dependent (n×n) –coordinate transformation matrix. Like the matrix Z, the matrix A contains

s := \frac{(n − p)(n − p + 1)}{2}

parameters Z_{r,t} which we may specialize into any point z of the affine space C^{s}. For such a point z ∈ C^{s} we denote the corresponding specialized matrices by A(z) , Z_{1}^{(i)}(z), Z_{2}^{(i)}(z) and Z^{(i)}(z) . We consider now the coordinate transformation given by X = AY with A = A(Z) and calculate the Jacobian J(G_{1}, …, G_{p}) with respect to the new polynomials G_{1}, …, G_{p} . Recall that the coordinate transformation matrix A depends on our previous choice of the index 1 ≤ i ≤ n − p. According to the structure of the coordinate transformation matrix A = A(Z) we subdivide the Jacobian J(f_{1}, …, f_{p}) into three submatrices

J(f_{1}, …, f_{p}) = [ U V W ] ,

with

U := [\frac{∂f_{k}}{∂X_{j}} ]\begin{matrix}1≤k≤p \\ 1≤j≤p−1 \end{matrix} , V := [\frac{∂f_{k}}{∂X_{j}} ]\begin{matrix}1≤k≤p \\ p≤j≤p+i−1 \end{matrix} , W := [\frac{∂f_{k}}{∂X_{j}} ]\begin{matrix}1≤k≤p \\ p+i≤j≤n \end{matrix} .

¿From the identity J(G_{1}, …, G_{p}) = J(f_{1}, …, f_{p}) A we deduce that our new Jacobian is of the form:

J(G_{1}, …, G_{p}) = [\frac{∂G_{k}}{∂Y_{j}} ]\begin{matrix}1≤k≤p \\ 1≤j≤n \end{matrix} = [U V Z_{1}^{(i)} + W Z^{(i)} W Z_{2}^{(i)}] .

We are interested in a local description of the i –th formal polar variety W_{i} = W_{0}∩Δ_{i} outside of the hypersurface V (m) , where m is the fixed upper left (p − 1) – minor of the Jacobian J(f_{1}, …, f_{p}) (and also of its submatrix U). Since the coordinate transformation X = AY leaves the submatrix U unchanged, the (p − 1) –minor m remains fixed under this transformation. ¿From Proposition 5 we know that the localized determinantal variety (Δ_{i})_{m} is described by the i equations

M_{p} = 0, …, M_{p+i−1} = 0,

and by the condition m ≠ 0 . The p – minors M_{p}, …, M_{p+i−1} defining these equations are built up by the submatrix [ U V] of the Jacobian J(f_{1}, …, f_{p}) . Under the coordinate transformation A(Z) the matrix [ U V] is changed into the submatrix

[ U V Z_{1}^{(i)} + W Z^{(i)}]

of the Jacobian J(G_{1}, …, G_{p}) and the p –minors M_{p}, …, M_{p+i−1} are changed into the p – minors

M̃_{p}, …, M̃_{p+i−1}

of the matrix [ U V Z_{1}^{(i)} + W Z^{(i)}]. This implies the matrix identity

(∗∗) [M̃_{p}, …, M̃_{p+i−1}] = [M_{p}, …, M_{p+i−1}] Z_{1}^{(i)} + [M_{p+i}, …, M_{n}] Z^{(i)}.

For the previously chosen index 1 ≤ i ≤ n − p, the coordinate transformation X = A(Z)Y induces the following morphism of affine spaces:

Φ_{i} : C^{n} × C^{s} → C^{p} × C^{i},

defined by

(x, z) ⟼ Φ_{i}(x, z) := ( f_{1}(x), …, f_{p}(x), M̃_{p}(x, z), …, M̃_{p+i−1}(x, z) ) .

Consider an arbitrary point z ∈ C^{s}. We denote by Δ_{i}^{z} the determinantal subvariety of C ^{n} defined by all p –minors of the matrix [ U V Z_{1}^{(i)}(z) + W Z^{(i)}(z)] (which is a submatrix of the new Jacobian obtained by specializing the coefficients of the polynomials G_{1}, …, G_{p} into the point z ∈ C^{s}). Writing W_{i}^{z} := W_{0} ∩ Δ_{i}^{z}, one sees immediately that the zero fiber Φ_{i}^{−1}(0) of the morphism Φ_{i} contains the set

(W_{i}^{z})_{m} := W_{0} ∩ (Δ_{i}^{z})_{m}.

In other words, for any arbitrarily chosen point z ∈ C^{s}, the zero fiber Φ_{i}^{−1}(0) of the morphism Φ_{i} contains the transformed formal polar variety W_{i}^{z}, localized in the hypersurface V (m) and expressed in the old coordinates.

We are going now to analyze the rank of the Jacobian of the morphism Φ_{i} in an arbitrary point (x, z) ∈ C^{n} × C^{s} with x ∈ (W_{i}^{z})_{m}. Using the subdivision of the parameter matrix Z into the parts Z^{(i)}, Z_{1}^{(i)} and Z_{2}^{(i)} , the Jacobian J(Φ_{i}) of the morphism Φ_{i} can be written symbolically as

J(Φ_{i}) = [\frac{∂Φ_{i}}{∂X} \frac{∂Φ_{i}}{∂Z^{(i)}} \frac{∂Φ_{i}}{∂Z_{1}^{(i)}} \frac{∂Φ_{i}}{∂Z_{2}^{(i)}} ] .

We have

[\frac{∂Φ_{i}}{∂X} \frac{∂Φ_{i}}{∂Z^{(i)}} ] =

= [\begin{matrix}J(f_{1}, …, f_{p}) & O_{p,n−p−i+1} & ⋯ & O_{p,n−p−i+1} \\ ∗ & [\frac{∂M̃_{p}}{∂Z_{p+i,p}} , …, \frac{∂M̃_{p}}{∂Z_{np}} ] & ⋯ & O_{1,n−p−i+1} \\ ⋮ & ⋮ & ... & ⋮ \\ ∗ & O_{1,n−p−i+1} & ⋯ & [\frac{∂M̃_{p+i−1}}{∂Z_{p+i,p+i−1}} , …, \frac{∂M̃_{p+i−1}}{∂Z_{n,p+i−1}} ] \end{matrix}] ,

where the columns correspond to the partial derivatives of Φ_{i} with respect to the variables

X_{1}, …, X_{n}, Z_{p+i,p}, …, Z_{n,p}, …, Z_{p+i,p+i−1}, …, Z_{n,p+i−1}

(in this order). The entries O_{r,t} denote here zero matrices of corresponding size and the row matrices labeled by ” ∗ ” represent the partial derivatives with respect to the variables X_{1}, …, X_{n} of the minors M̃_{p}, …, M̃_{p+i−1} . These row matrices will be irrelevant for our considerations.

Furthermore, the third submatrix [\frac{∂Φ_{i}}{∂Z_{1}^{(i)}} ] of J(Φ_{i}) can be written as

[\begin{matrix}O_{p,i−1} & O_{p,i−2} & ⋯ & 0 \\ [\frac{∂M̃_{p}}{∂Z_{p+1,p}} , …, \frac{∂M̃_{p}}{∂Z_{p+i−1,p}} ] & O_{1,i−2} & ⋯ & 0 \\ O_{1,i−1} & [\frac{∂M̃_{p+1}}{∂Z_{p+2,p+1}} , …, \frac{∂M̃_{p}}{∂Z_{p+i−1,p+1}} ] & ⋯ & 0 \\ ⋮ & ⋮ & ... & ⋮ \\ O_{1,i−1} & O_{1,i−2} & ⋯ & [\frac{∂M̃_{p+i−1}}{∂Z_{p+i−1,p+i−2}} ] \\ O_{1,i−1} & O_{1,i−2} & ⋯ & 0 \end{matrix}]

and the last submatrix [\frac{∂Φ_{i}}{∂Z_{2}^{(i)}} ] of J(Φ_{i}) is a zero matrix since the p – minors

M̃_{p}, …, M̃_{p+i−1} are indepedent of the parameters Z_{r,t} occurring in the submatrix Z_{2}^{(i)} of the coordinate transformation matrix A(Z) . Therefore, the Jacobian J(Φ_{i}) is of full rank p + i wherever the submatrix

J̃(Φ_{i}) := [\frac{∂Φ_{i}}{∂X} \frac{∂Φ_{i}}{∂Z^{(i)}} ]

is of full rank p + i. On the other hand, considering the i row matrices contained in J̃(Φ_{i}) for p ≤ j ≤ p + i − 1

[\frac{∂M̃_{j}}{∂Z_{p+i,j}} , …, \frac{∂M̃_{j}}{∂Z_{n,j}} ] ,

we see that the representation (∗∗) of the transformed p –minors M̃_{j} implies the identity

[\frac{∂M̃_{j}}{∂Z_{p+i,j}} , …, \frac{∂M̃_{j}}{∂Z_{n,j}} ] = [ M_{p+i}, …, M_{n}] .

Thus, we obtain the representation

J̃(Φ_{i}) = [\begin{matrix}J(f_{1}, …, f_{p}) & O_{p,n−p−i+1} & ⋯ & O_{p,n−p−i+1} \\ ∗ & [M_{p+i}, …, M_{n}] & ⋯ & O_{1,n−p−i+1} \\ ⋮ & ⋮ & ... & ⋮ \\ ∗ & O_{1,n−p−i+1} & ⋯ & [M_{p+i}, …, M_{n}] \end{matrix}] .

Since all entries of the submatrix J̃(Φ_{i}) of the Jacobian J(Φ_{i}) belong to the polynomial ring Q [X_{1}, …, X_{n}] , we see that the rank of the matrix J(Φ_{i}) in a given point (x, z) ∈ C^{n} × C^{s} with x ∈ (W_{i}^{z})_{m} depends only on the choice of x. According to our localization outside of the hypersurface V (m) , let us consider an arbitrary smooth point x̃ of W_{0} = V (f_{1}, …, f_{p}) satisfying the condition m(x̃) ≠ 0 . Suppose that the submatrix J̃(Φ_{i})(x̃) is not of full rank, i.e., that

rk J̃(Φ_{i})(x̃) < p + i

holds. This latter inequality is valid if and only if all p -minors M_{p+i}, …, M_{n} of the Jacobian J(f_{1}, …, f_{p}) vanish at x̃. Let z̃ ∈ C^{s} be any parameter point such that the pair (x̃, z̃) belongs to the fiber Φ_{i}^{−1}(0) of the morphism Φ_{i}. Since the p -minors M̃_{p}, …, M̃_{p+i−1} of the transformed Jacobian J(G_{1}, …, G_{p}) must vanish at (x̃, z̃), we deduce from (∗∗) that

[0, …, 0] = [M_{p}(x̃), …, M_{p+i−1}(x̃)] Z_{1}^{(i)}(z̃)

holds (here Z_{1}^{(i)}(z̃) denotes again the matrix obtained by specializing the entries of Z_{1}^{(i)} into the corresponding coordinates of the point z̃ ∈ C^{s}). Because of the lower triangular form of the regular matrix Z_{1}^{(i)} , the latter matrix equation holds if and only if the conditions

M_{p+i−1}(x̃) = ⋯ = M_{p}(x̃) = 0.

are satisfyied. Therefore, our assumptions on x̃ and z̃ imply m(x̃) ≠ 0 and M_{p}(x̃) = ⋯ = M_{n}(x̃) = 0. However, by Remark 7 this means that the Jacobian J(f_{1}, …, f_{p})(x̃) is singular. Hence, x̃ is not a smooth point of W_{0} , i.e., x̃ ∈ Sing W_{0} , which contradicts our assumption on x̃. Now, suppose that we are given a point (x̄, z) ∈ C^{n} × C^{s} that belongs to the fiber Φ_{i}^{−1}(0) . Then x̄ belongs to W_{0} . Further, suppose that x̄ is a smooth point of W_{0} outside of the hypersurface V (m) . Let us consider the Zariski–open neighbourhood Ũ of x̄ consisting of all points x ∈ C^{n} with m(x) ≠ 0 and rk J(f_{1}, …, f_{p}) = p, i.e., we consider

Ũ := C^{n} \ (Sing W_{0} ∪ V (m)) .

We are going to show that the restricted morphism

Φ_{i} : Ũ × C^{s} → C^{p} × C^{i}

is transversal to the origin 0 ∈ C^{p} × C^{i}. In order to see this, consider an arbitrary point (x, z) of Ũ × C^{s} that satisfies the equation Φ_{i}(x, z) = 0 . Thus, x belongs to Ũ ∩ W_{0} and is, therefore, a smooth point of W_{0} , which is outside of the hypersurface V (m) . By the preceding considerations on the rank of the Jacobian J(Φ_{i}) it is clear that J(Φ_{i}) has the maximal rank p + i at (x, z) . This means that (x, z) is a regular point of Φ_{i}. Since (x, z) was an arbitrary point of Φ_{i}^{−1}(0) ∩ (Ũ × C^{s}) , the claimed transversality has been shown. Now, applying the Weak–Transversality–Theorem of Thom–Sard (see e.g. [22]) to the diagram

Φ_{i}^{−1}(0) ∩ (Ũ × C^{s}) ↪ C^{n} × C^{s}
↘  ↓
C^{s}

one concludes that there is a residual dense set Ω_{i} of parameters z ∈ C^{s} for which transversality holds. This implies that, for every fixed z ∈ Ω_{i}, the transformed and localized formal polar variety

W_{i}^{z} \ (Sing W_{0} ∪ V (m))

is either empty or a smooth variety of codimension p+i. This variety can be described locally by the polynomials

(∗ ∗ ∗) f_{1}(X), …, f_{p}(X), M̃_{p}(X, z), …, M̃_{p+i−1}(X, z)

that form a regular sequence outside of SingW_{0} ∪ V (m) . Up to now, our considerations concerned only the change of coordinates for an arbitrarily fixed 1 ≤ i ≤ n − p. However, Ω := ⋂_{i=1}^{n−p} Ω_{i} is a dense residual parameter set in C^{s} from which we can choose a simultaneous change of coordinates for all 1 ≤ i ≤ n − p. For every choice z ∈ Ω and 1 ≤ i ≤ n − p the transformed formal polar variety W_{i}^{z} is, outside of the closed set SingW_{0} ∪ V (m) , a smooth complete intersection variety described by the (local) regular sequence (∗ ∗ ∗) . One sees now easily that the affine space IR^{s} contains a non–empty residual dense set of parameters z such that the conclusions above apply to the coordinate transformation X = A(z)Y . Moreover, z can be chosen from Q^{s}. Taking into account Proposition 5 and Remark 7, we deduce the following result from our argumentation:

Theorem 8. Let W_{0} = V (f_{1}, …, f_{p}) be a reduced complete intersection variety given by polynomials f_{1}, …, f_{p} in Q [X_{1}, …, X_{n}] and suppose that the variables X_{1}, …, X_{n} are in generic position with respect to f_{1}, …, f_{p}. Further, let m be the upper left (p − 1) –minor of the Jacobian J(f_{1}, …, f_{p}) . Then, every formal polar variety W_{i}, 1 ≤ i ≤ n − p, localized with respect to the closed set SingW_{0} ∪ V (m) , is either empty or a smooth variety of codimension p + i that can be decribed by the equations

f_{1}, …, f_{p}, M_{p}, …, M_{p+i−1},

where M_{j}, p ≤ j ≤ p + i − 1, is the p – minor of the Jacobian J(f_{1}, …, f_{p}) given by the columns 1, …, p − 1, j. Then the polynomials

f_{1}, …, f_{p}, M_{p}, …, M_{p+i−1}

form a regular sequence outside of SingW_{0} ∪ V (m) .

Remark 9. Taking into account that the argumentation on the localization with respect to the fixed (p − 1) -minor m remains valid mutatis mutandis for any other (p − 1) -minor m̃ of the Jacobian J(f_{1}, …, f_{p}) , Theorem 8 can be restated for any fixed (p − 1) –minor just by reordering of columns and rows of the Jacobian J(f_{1}, …, f_{p}) .

2.4. Existence of Real Points in the Polar Varieties. Let f_{1}, …, f_{p} be a reduced regular sequence in Q [X_{1}, …, X_{n}] and let again W_{0} := V (f_{1}, …, f_{p}) be the affine variety defined by f_{1}, …, f_{p}. Consider the real variety S_{0} := W_{0} ∩ IR^{n} and suppose that

(i) S_{0} is nonempty and bounded (and hence compact), (ii) the Jacobian J(f_{1}, …, f_{p})(x) is of maximal rank in all points x of S_{0} (i.e., S_{0}

is a smooth subvariety of IR^{n} given by the reduced regular sequence f_{1}, …, f_{p}), (iii) the variables X_{1}, …, X_{n} are in generic position with respect to the polynomials

f_{1}, …, f_{p}. Further, let C be any connected component of the compact set S_{0} , and let b := (a_{1}, …, a_{p−1}, a_{p}, …, a_{n−1}, a_{n}) ∈ C be a locally maximal point of the last coordinate X_{n} in the non–empty compact set C ⊂ S_{0} . Without loss of generality we may assume that the upper left (p − 1) –minor m of the Jacobian J(f_{1}, …, f_{p}) does not vanish in b (by our assumptions there must be a (p − 1) –minor of J(f_{1}, …, f_{p}) not vanishing at b). In any local parametrization of S_{0} at b the variable X_{n} cannot be an independent variable, since X_{n} attains a local maximum in b ( a_{n} is this local maximum). Hence, without loss of generality we may assume that the local parametrization of S_{0} in b has the following form: there exists an open set U ⊂ IR^{n−p} containing the point a := (a_{p}, …, a_{n−1}) , and a continuously differentiable function

φ : U → IR^{p} , φ := (φ_{1}, …, φ_{p−1}, φ_{n})

such that

x_{1} = φ_{1}(x_{p}, …, x_{n−1}), …, x_{p−1} = φ_{p−1}(x_{p}, …, x_{n−1}),
x_{n} = φ_{n}(x_{p}, …, x_{n−1})

holds for any x = (x_{p}, …, x_{n−1}) ∈ U. With respect to this local parametrization, the polynomials f_{k}, 1 ≤ k ≤ p, induce real valued functions of the form:

f̃_{k}(X_{p}, …, X_{n−1}) :=
f_{k}(φ_{1}(X_{p}, …, X_{n−1}), …, φ_{p−1}(X_{p}, …, X_{n−1}),
X_{p}, …, X_{n−1}, φ_{n}(X_{p}, …, X_{n−1})).

For every 1 ≤ k ≤ p, and every p ≤ j ≤ n − 1, one has the identity

\frac{∂f̃_{k}}{∂X_{j}} = \frac{∂f_{k}}{∂X_{j}} + \frac{∂f_{k}}{∂X_{1}} \frac{∂φ_{1}}{∂X_{j}} + ⋯ + \frac{∂f_{k}}{∂X_{p−1}} \frac{∂φ_{p−1}}{∂X_{j}} + \frac{∂f_{k}}{∂X_{n}} \frac{∂φ_{n}}{∂X_{j}} = 0 (1)

in the open set U. Considering the (p × p) –matrix

B := [\begin{matrix}\frac{∂f_{1}}{∂X_{1}} & & … & & & \frac{∂f_{1}}{∂X_{p−1}} & & & \frac{∂f_{1}}{∂X_{n}} \\ . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . \\ \frac{∂f_{p}}{∂X_{1}} & & … & & & \frac{∂f_{p}}{∂X_{p−1}} & & & \frac{∂f_{p}}{∂X_{n}} \end{matrix}] ,

and observing that B is regular in U, we obtain from (1) that

− det B(x) [ \frac{∂φ_{1}}{∂X_{j}} ; ⋮ ; \frac{∂φ_{p−1}}{∂X_{j}} ; \frac{∂φ_{n}}{∂X_{j}} ] = (Adj B)(x) [ \frac{∂f_{1}}{∂X_{j}} (x) ; ⋮ ; \frac{∂f_{p−1}}{∂X_{j}} (x) ; \frac{∂f_{p}}{∂X_{j}} (x)] (2)

holds for any x ∈ U (here Adj B denotes the adjoint matrix of the matrix B). As b is a locally maximal point of X_{n}, we have that

\frac{∂φ_{n}}{∂X_{j}} (a) = 0

holds for every p ≤ j ≤ n − 1 . Thus, equation (2) implies

B(n, 1) (b) \frac{∂f_{1}}{∂X_{j}} (b) + ⋯ + B(n, p) (b) \frac{∂f_{p}}{∂X_{j}} (b) = 0 (3)

for every p ≤ j ≤ n − 1 (here for 1 ≤ k ≤ p we denote the entry of the adjoint matrix Adj B at the cross point of the k –th column and the last row by B(n, k) ). Taking into account the particular form of the matrix B, the equation system (3) means that

det [\begin{matrix}\frac{∂f_{1}}{∂X_{1}} (b) & & & … & & & \frac{∂f_{1}}{∂X_{p−1}} (b) & & & \frac{∂f_{1}}{∂X_{j}} (b) \\ . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . \\ \frac{∂f_{p}}{∂X_{1}} (b) & & & … & & & \frac{∂f_{p}}{∂X_{p−1}} (b) & & & \frac{∂f_{p}}{∂X_{j}} (b) \end{matrix}] = 0 (4)

holds for every p ≤ j ≤ n − 1 . Using our notations for the p –minors of the Jacobian J(f_{1}, …, f_{p}) , we reinterprete now the equations (4) as

M_{p} (b) = … = M_{n−1} (b) = 0.

Since m(b) ≠ 0 holds by assumption, Proposition 5 implies that b belongs to the localized determinantal variety (Δ_{n−p})_{m}. Therefore, we have b ∈ W_{0} ∩ (Δ_{n−p})_{m}, i.e., the last formal polar variety W_{n−p} contains the point b. On the other hand, b is a nonsingular point of W_{0} and belongs therefore to W̃_{n−p} = \overline{W_{n−p} \ SingW_{0}} . Thus W̃_{n−p} is a non–empty set of dimension zero that contains the real point b of the arbitrarily chosen connected component C of the real variety S_{0} . In particular, b ∈ W̃_{n−p} ∩ IR^{n} ⊂ W_{i} ∩ IR^{n} = S_{i} holds for any 1 ≤ i ≤ n − p.

These considerations imply the following result:

Theorem 10. Let W_{0} := V (f_{1}, …, f_{p}) be as in Theorem 8. If the real variety S_{0} := W_{0} ∩ IR^{n} is non–empty, bounded and smooth, and if the variables X_{1}, …, X_{n} are in generic position with respect to f_{1}, …, f_{p}, then every real formal polar variety S_{i} = W_{i}∩IR^{n}, 1 ≤ i ≤ n−p, is a non–empty, smooth manifold of dimension n−(p+i) and contains at least one representative point of each connected component of the real variety S_{0} .

3. Real Equation Solving

The geometric results of Section 2 allow us to design a new efficient procedure that finds at least one representative point in each connected component of a given smooth, compact, real complete intersection variety. This procedure will be formulated in the algorithmic (complexity) model of (divisionfree) arithmetic circuits and networks (arithmetic-boolean circuits) over the rational numbers Q . Roughly speaking, a division-free arithmetic circuit β over Q is an algorithmic device that supports a step by step evaluation of certain (output) polynomials belonging to Q [X_{1}, …, X_{n}] , say f_{1}, …, f_{p}. Each step of β corresponds either to an input from X_{1}, …, X_{n}, to a constant (circuit parameter) from Q or to an arithmetic operation (addition/subtraction or multiplication). We represent the circuit β by a labelled directed acyclic graph (dag). The size of this dag measures the sequential time requirements of the evaluation of the output polynomials f_{1}, …, f_{p} performed by the circuit β.

A (division-free) arithmetic network over Q is nothing else but an arithmetic circuit that additionally contains decision gates comparing rational values or checking their equality, and selector gates depending on these decision gates. Arithmetic circuits and networks represent non–uniform algorithms, and the complexity of executing a single arithmetic operation is always counted at unit cost. Nevertheless, by means of well known standard procedures our algorithms will always be transposable to the uniform random bit model and they will be practically implementable as well. All this can be done in the spirit of the general asymptotic complexity bounds stated in Theorem 11 below. Let us also remark that the depth of an arithmetic circuit (or network) measures the parallel time of its evaluation, whereas its size allows an alternative interpretation as ”number of processors”. In this context we would like to emphasize the particular importance of counting only nonscalar arithmetic operations (i.e.,only essential multiplications), taking Q -linear operations (in particular, additions/subtractions) for cost–free. This leads to the notion of nonscalar size and depth of a given arithmetic circuit or network β. It can be easily seen that the nonscalar size determines essentially the total size of β (which takes into account all operations) and that the nonscalar depth dominates the degree and height of the intermediate results of β. An arithmetic circuit (or network) becomes a sequential algorithm when we play a so–called pebble game on it. By means of pebble games we are able to introduce a natural space measure in our algorithmic model and along with this, a new, more subtle sequential time measure. If we play a pebble game on a given arithmetic circuit, we obtain a so–called straight line program (slp). In the same way we obtain a computation tree from a given arithmetic network. For more details on our complexity model we refer to [11], [25], [26], [45], [53], [38] and especially to [33] (where also the implementation aspect is treated). In the next Theorem 11 we are going to consider families of polynomials f_{1}, …, f_{p} belonging to Q [X_{1}, …, X_{n}] , for which we arrange the following assumptions and notations:

(i) f_{1}, …, f_{p} form a regular sequence in Q [X_{1}, …, X_{n}] , (ii) for every 1 ≤ k ≤ p the ideal (f_{1}, …, f_{k}) generated by f_{1}, …, f_{k} in

Q [X_{1}, …, X_{n}] is radical and defines a subvariety of C^{n} of dimension n − k that we denote by V_{k} := V (f_{1}, …, f_{k}) .

(iii) the variables X_{1}, …, X_{n} are in generic position with respect to the polynomials

f_{1}, …, f_{p}. Let W_{0} := {x ∈ C^{n}|f_{1}(x) = ⋯ = f_{p}(x) = 0} and denote by SingW_{0} the singular locus of W_{0} . For 1 ≤ i ≤ n − p let W_{i} be the i –th formal polar variety associated with W_{0} and the variables X_{p+i}, …, X_{n}, and let W̃_{i} := \overline{W_{i} \ SingW_{0}} be the i –th polar variety of W_{0} in the usual sense (see Section 2 for precise definitions). Further, for 1 ≤ k ≤ p we shall write Ṽ_{k} := \overline{V_{k} \ SingW_{0}} . We call

δ := max{max{deg Ṽ_{k}|1 ≤ k ≤ p}, max{deg W̃_{i}|1 ≤ i ≤ n − p}}

the degree (of the real interpretation) of the polynomial equation system f_{1}, …, f_{p}. Finally, let us make the following assumption:

(iv) the specialized Jacobian J(f_{1}, …, f_{p})(x) has maximal rank in any point x of S_{0} := W_{0} ∩ IR^{n} = {x ∈ IR^{n}|f_{1}(x) = ⋯ = f_{p}(x) = 0} and S_{0} is a bounded semialgebraic set (hence, S_{0} is empty or a smooth, compact real manifold of dimension n − p; see Section 2 for details).

Theorem 11. Let n, p, d, δ, L and ℓ be natural numbers with d ≥ 2 and p ≤ n. There exists an arithmetic network N over Q of size \binom{n}{p−1}L(ndδ)^{O(1)} and nonscalar depth O(n(log nd + ℓ) log δ) with the following property: Let f_{1}, …, f_{p} be a family of n –variate polynomials of a degree at most d and assume that f_{1}, …, f_{p} are given by a division–free arithmetic circuit β in Q [X_{1}, …, X_{n}] of size L and nonscalar depth ℓ. Suppose that the polynomials f_{1}, …, f_{p} satisfy the conditions (i), (ii), (iii) and (iv) above. Further, suppose that the degree of the real interpretation of the polynomial system f_{1}, …, f_{p} is bounded by δ (let us now freely use the notations just introduced before). The algorithm represented by the arithmetic network N starts from the circuit β as input and decides first whether the complex variety W̃_{n−p} is empty. If this is not the case, then W̃_{n−p} is a zero–dimensional complex variety and the network N produces an arithmetic circuit in Q of asymptotically the same size and nonscalar depth as N , which represents the coefficients of n+1 univariate polynomials q, p_{1}, …, p_{n} ∈ Q[X_{n}] satisfying the following conditions:

deg q = # W̃_{n−p},
max{deg p_{k}|1 ≤ k ≤ n} < deg q,
W̃_{n−p} = {(p_{1}(u), …, p_{n}(u))|u ∈ C, q(u) = 0}.

Moreover, the algorithm represented by the arithmetic network N decides whether the set W̃_{n−p}∩IR^{n} is empty. If this is not the case, then N produces at most # W̃_{n−p} ≤ δ sign sequences belonging to the set {−1, 0, 1} such that these sign sequences encode the real zeros of the polynomial q ”à la Thom” ([18]). In this way N describes the finite, non–empty set W̃_{n−p} ∩ IR^{n}, which contains at least one representative point for each connected component of the real variety S_{0} = {x ∈ IR^{n}|f_{1}(x) = ⋯ = f_{p}(x) = 0}.

Proof We shall freely use the notations of Section 2. Any selection of indices 1 ≤ i_{1} < ⋯ < i_{p} ≤ n and 1 ≤ j, k ≤ p determines a p – minor M(i_{1}, …, i_{p}) and a (p − 1) – minor m(i_{1}, …, i_{p}; j, k) of the Jacobian J(f_{1}, …, f_{p}) in the following way: M(i_{1}, …, i_{p}) is the determinant of the (p×p) – submatrix of J(f_{1}, …, f_{p}) with columns i_{1}, …, i_{p}, and m(i_{1}, …, i_{p}; j, k) is the determinant of the matrix obtained from the former one deleting the row number j and the column number i_{k}. There are p^{2}\binom{n}{p} such possible selections. Let us fix one of them, say i_{1} := 1, …, i_{p} := p; j := p, k := p. Then, using the notations of Section 2, we have m(i_{1}, …, i_{p}; j, k) = m, M(i_{1}, …, i_{p}) = M_{p}. Let us abbreviate g := mM_{p}. ¿From our assumptions on f_{1}, …, f_{p} and Theorem 8 and Theorem 10 of Section 2 we deduce the following facts: For any 1 ≤ i ≤ n − p the polynomials f_{1}, …, f_{p}, M_{p}, …, M_{p+i−1} have degree at most pd. They generate the trivial ideal or form a regular sequence in the localized Q -algebra Q [X_{1}, …, X_{n}]_{g}. In either case the ideal generated by f_{1}, …, f_{p}, M_{p}, …, M_{p+i−1} in Q [X_{1}, …, X_{n}]_{g} is radical and defines a complex variety that is empty or of degree

deg(\overline{W_{i} \ V (g)}) ≤ deg(\overline{W_{i} \ SingW_{0}}) = deg W̃_{i} ≤ δ.

Moreover, by assumption, the polynomials f_{1}, …, f_{p} form a regular sequence in Q [X_{1}, …, X_{n}]_{g} and for each 1 ≤ k ≤ p the ideal generated by f_{1}, …, f_{k} in Q [X_{1}, …, X_{n}]_{g} is radical and defines a complex variety of degree

deg \overline{V_{k} \ V (g)} ≤ deg Ṽ_{k} ≤ δ.

One sees easily that the polynomials f_{1}, …, f_{p}, M_{p}, …, M_{n−1} and g can be evaluated by a division–free arithmetic circuit of size O(L + n^{5}) and nonscalar depth O(log n + ℓ) . Applying now, for each 1 ≤ i ≤ n − p, the algorithm underlying [30], Proposition 18 in its rational version [31], Theorem 19 to the system

f_{1} = 0, …, f_{p} = 0, M_{p} = 0, …, M_{p+i−1} = 0, g ≠ 0

we are able to check whether the particular system

f_{1} = 0, …, f_{p} = 0, M_{p} = 0, …, M_{n−1} = 0, g ≠ 0

has a solution in C^{n}. If this is the case, then this system defines a zero–dimensional algebraic set, namely W_{n−p} \ V (g) , and the algorithm produces an arithmetic circuit γ̄ in Q that represents the coefficients of n+1 univariate polynomials q̄, p̄_{1}, …, p̄_{n} ∈ Q [X_{n}] satisfying the following conditions:

deg q̄ = # (W_{n−p} \ V (g)),
max{deg p̄_{k}|1 ≤ k ≤ n} < deg q̄,
W_{n−p} \ V (g) = {(p̄_{1}(u), …, p̄_{n}(u))|u ∈ C, q̄(u) = 0}.

The algorithm is represented by an arithmetic network of size L(ndδ)^{O(1)} and nonscalar depth O(n(log nd+ℓ) log δ) , and the circuit γ̄ has asymptotically the same size and nonscalar depth. Running this procedure for each selection 1 ≤ i_{1} < ⋯ < i_{p} ≤ n and 1 ≤ j, k ≤ p we obtain an arithmetic network N_{0} of size p^{2}\binom{n}{p}L(ndδ)^{O(1)} = \binom{n}{p−1}L(ndδ)^{O(1)} and nonscalar depth O(n(log nd + ℓ) log δ) , which decides whether

W̃_{n−p} = W_{n−p} \ SingW_{0} is empty. Suppose that this is not the case. Then N_{0} describes locally the variety W̃_{n−p}, which is now zero-dimensional. Each local description of W̃_{n−p} contains an arithmetic circuit representation of the coefficients of the minimal polynomial of the variable X_{n} with respect to the corresponding local piece of W̃_{n−p} . Moreover, one easily obtains the same type of information for any linear form X_{i} + X_{n} and any variable X_{i} with 1 ≤ i < n. One multiplies now all minimal polynomials of the variable X_{n} obtained in this way. Making this product squarefree (see e.g [45], Lemma 12) one obtains the polynomial q of the statement of Theorem 11. Doing the same thing for the minimal polynomials of each linear form X_{i} + X_{n} and each variable X_{i} with 1 ≤ i < n, yields by means of [45], Lemma 26, the polynomials p_{1}, …, p_{n} of the statement of Theorem 11. All this can be done by means of an arithmetic network N_{1} , which extends N_{0} and has asympotically the same size and nonscalar depth. The final arithmetic network N is now obtained from N_{1} in the same way as in the proof [1], Theorem 8. □

Remark 12. (i) Using the refined algorithmic techniques of [38] or [33] it is not too difficult to see that for inputs f_{1}, …, f_{p} represented by straight–line programs of length T and space S the arithmetic network N can be converted into an algebraic computation tree which solves the algorithmic problem of Theorem 11 in time O((T dn^{2} + n^{5})δ^{3} log^{3} δ log^{2} log δ) and space O(Sdnδ^{2}) .

(ii) The smooth, compact hypersurface case (with p := 1 ) of Theorem 11 corresponds

exactly to [1], Theorem 8. (iii) Let J(f_{1}, …, f_{p})^{T} denote the transposed matrix of the Jacobian

J(f_{1}, …, f_{p}) of the polynomials f_{1}, …, f_{p} in the statement of Theorem 11 and let

D := det J(f_{1}, …, f_{p})J(f_{1}, …, f_{p})^{T} .

¿From the well–known Cauchy–Binet formula one deduces easily that, with the notations of Section 2, the identity

D = ∑_{1≤i_{1}<···<i_{p}≤n} det^{2} M(i_{1}, …, i_{p})

holds. Replacing now, in the statement and the proof of Theorem 11 for 1 ≤ i ≤ n − p, the polar variety W̃_{i} by Ŵ_{i} := \overline{W_{i} \ V (D)} and the parameter δ by

δ̂:= max{max{deg Ṽ_{k}|1 ≤ k ≤ p}, max{deg Ŵ_{i}|1 ≤ i ≤ n − p}}

one obtains a somewhat improved complexity result, since δ̂ ≤ δ holds.

Let us now suppose that the polynomials f_{1}, …, f_{p} ∈ Q[X_{1}, …, X_{n}] satisfy the conditions (i), (ii), (iii), (iv) above. Unfortunately, the complexity parameter δ of Theorem 11 is strongly related to the complex degrees of the polar varieties W̃_{1}, …, W̃_{n−p} of W_{0} = {x ∈ C^{n}|f_{1}(x) = ⋯ = f_{p}(x) = 0} and not to their real degrees. Under some additional algorithmic assumptions, which we are going to explain below, we may replace the complexity parameter δ by a smaller one that measures only the real degrees of the polar varieties W̃_{1}, …, W̃_{n−p}. We shall call this new complexity parameter the real degree of the equation system f_{1}, …, f_{p} and denote it by δ^{∗}. Let 1 ≤ k ≤ p and let us consider the decomposition of the intermediate variety Ṽ_{k} into irreducible components with respect to the Q -Zariski topology of C^{n} say Ṽ_{k} = C_{1} ∪ ⋯ ∪ C_{s}. We call an irreducible component C_{r}, 1 ≤ r ≤ s, real if C_{r} ∩ IR^{n} contains a smooth point of C_{r}. The union of all real irreducible components of Ṽ_{k} is called the real part of Ṽ_{k} and denoted by V_{k}^{∗}. We call deg V_{k}^{∗} the real degree of the intermediate variety Ṽ_{k}. Similarly, we introduce for every 1 ≤ i ≤ n − p the real part W_{i}^{∗} of the polar variety W̃_{i} and its real degree deg W_{i}^{∗}. Finally, we define the real degree of the equation system f_{1}, …, f_{p} as

δ^{∗} := max{max{deg V_{k}^{∗}|1 ≤ k ≤ p}, max{deg W_{i}^{∗}|1 ≤ i ≤ n − p}}.

Now, we are going to restate the main outcome of Theorem 11 in terms of the new complexity parameter δ^{∗}. For this purpose we have to include the following two subroutines in our algorithmic model:

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

• the second subroutine allows us to discard non-real irreducible components of the occurring complex polar varieties. This second subroutine starts from a straightline program for a single polynomial in Q [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 Q extended if it contains extra nodes corresponding to the first and second subroutine. Modifying our algorithmic model in this way, we are able to formulate the following complexity result, which generalizes [1], Theorem 12 and improves the complexity outcome of our previous Theorem 11.

Remark 13. Let n, p, d, δ^{∗}, L and ℓ be natural numbers with d ≥ 2 and p ≤ n. There exists an extended arithmetic network N^{∗} over Q of size \binom{n}{p−1}L(ndδ^{∗})^{O(1)} with the following property: Let f_{1}, …, f_{p} be a family of n –variate polynomials of a degree at most d and assume that f_{1}, …, f_{p} are given by a division–free arithmetic circuit β in Q[X_{1}, …, X_{n}] of size L. Suppose that the polynomials f_{1}, …, f_{p} satisfy the conditions (i), (ii), (iii), and (iv) contained in the formulation of Theorem 11. Let us now freely use the notations introduced in the present section. Assume that the real variety S_{0} = {x ∈ IR^{n}|f_{1}(x) = ⋯ = f_{p}(x) = 0} is not empty and that the real degree of the polynomial system f_{1}, …, f_{p} is bounded by δ^{∗}. The algorithm represented by the arithmetic network N^{∗} starts from the circuit β as input and decides first whether the complex variety W_{n−p}^{∗} is empty. If this is not the case, then W_{n−p}^{∗} is a zero–dimensional complex variety and the network N^{∗} produces an arithmetic circuit in Q of asymptotically the same size as N^{∗},which represents the coefficients of n + 1 univariate polynomials q^{∗}, p_{1}^{∗}, …, p_{n}^{∗} ∈ Q [X_{n}] satisfying the conditions

deg q^{∗} = # W_{n−p}^{∗},
max{deg p_{k}^{∗}|1 ≤ k ≤ n} < deg q^{∗},
W_{n−p}^{∗} = {(p_{1}^{∗}(u), …, p_{n}^{∗}(u))|u ∈ C, q^{∗}(u) = 0}.

Each over Q irreducible component of the complex variety W_{n−p}^{∗} contains at least one real point characterized by an irreducible factor of the polynomial q^{∗}. The algorithm represented by the network N^{∗} returns all these points in a codification ”à la Thom”. Moreover, the non–empty set W_{n−p}^{∗} ∩ IR^{n} contains at least one representative point for each connected component of the real variety S_{0} .

The proof of this remark is a straight–forward adaptation of the arguments of the proof of [1], Theorem 12 (which treats only the hypersurface case with p := 1 ) to the arguments of Theorem 11 above. Therefore, we omit this proof.

References

[1] Bank, B.; Giusti, M.; Heintz, J.; Mbakop, G.M. Polar varieties, real equation solving and data structures: The hypersurface case. J. Complexity 13, No.1, 5-27, (1997), Best Paper Award J. Complexity 1997

[2] Bank, B.; Giusti, M.; Heintz, J.; Mandel, R.; Mbakop, G. M.: Polar Varieties and Efficient Real Equation Solving: The Hypersurface Case. Proceedings of the 3rd Conference Approximation and Optimization in the Caribbean, in: Aportaciones Matemáticas, Mexican Society of Mathematics, J. Bustamante, M. A. Jimenez et al.(eds.) (1998)

[3] A. I. Barvinok: Feasibility testing for systems of real quadratic equations, Manuscript, Royal Institute of Technology, Stockholm (1991)

[4] S. Basu, R. Pollack, M.-F. Roy: On the Combinatorial and Algebraic Complexity of Quantifier Elimination. J.ACM 43, No. 6, 1002-1045,(1996)

[5] S. Basu, R. Pollack, M.-F. Roy: Complexity of computing semi-algebraic descriptions of the connected components of a semialgebraic set. Proceedings of ISSAC ’98, Gloor, Oliver (ed.), Rostock, Germany, August 13–15, 1998. New York, NY: ACM Press. 25-29 (1998).

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

[7] E. Becker, R. Neuhaus: Computation of real radicals of polynomial ideals. Computanial algebraic geometry (Nice 1992), 1–20, Progr. Math. 109, Birkhäuser Boston, Boston MA, (1993)

[8] E. Becker, J. Schmidt: On the real Nullstellensatz. Algorithmic algebra and number theory (Heidelberg, 1997), 173–185, Springer Berlin (1999)

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

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

[11] P. Bürgisser, M. Clausen, M. A. Shokrollahi Algebraic complexity theory. With the collaboration of Thomas Lickteig. Grundlehren der Mathematischen Wissenschaften. 315. Berlin: Springer. XXIII, 618 (1997)

[12] L. Blum, F. Cucker, M. Shub, S. Smale, Complexity and real computation. Foreword by Richard M. Karp. New York, NY: Springer. XVI, 453 p. (1997)

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

[14] J. F. Canny, I. Z. Emiris: Efficient Incremental Algorithms for the Sparse Resultant and the Mixed Volume, J. Symb. Comput. 20, No.2, 117-149 (1995)

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

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

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

[18] 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, 121-130 (1988)

[19] F. Cucker, S. Smale: Complexity estimates depending on condition and round-of error, Bilardi, Gianfranco (ed.) et al., Algorithms - ESA ’98. 6th annual European symposium, Venice, Italy, August 24–26, 1998. Proceedings. Berlin: Springer. Lect. Notes Comput. Sci. 1461, 115-126 (1998).

[20] J.-P. Dedieu, Estimations for the Separation Number of a Polynomial System, J. Symbolic Comp. 24, 683-693 (1997)

[21] J.-P. Dedieu, Approximate Solutions of Numerical Problems, Condition Number Analysis and Condition Number Theorems, Lectures in Applied Mathematics, Vol. 32, 263-283 (1996)

[22] M. Demazure, Catastrophes et bifurcations, Ellipses, Paris (1989)

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

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

[25] J. von zur Gathen: Parallel arithmetic computations: A survey. Mathematical foundations of computer science, Proc. 12th Symp., Bratislava/Czech. 1986, Lect. Notes Comput. Sci. 233, 93-112 (1986). MSC 1991

[26] J. von zur Gathen: Parallel linear algebra. In J. Reif, editor Synthesis of parallel algorithmns. Morgan Kaufmann (1993)

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

[28] 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).

[29] 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, 205–231 (1995)

[30] M. Giusti, J. Heintz, J.E. Morais, J. Morgenstern, L.M. Pardo: Straight–line programs in Geometric Elimination Theory, J. Pure Appl. Algebra, 124, No.1-3, 101-146 (1998)

[31] M. Giusti, J. Heintz, K. Hägele, J. E. Morais, J. L. Montaña, L. M. Pardo: Lower Bounds for Diophantine Approximations, J. Pure and Applied Alg.,117 & 118, 277–317 (1997)

[32] M. Giusti, J.P. Henry: Minorations de nombres de Milnor, Bull. Soc. Math. Fr.,108, 17-45 (1980)

[33] M. Giusti, G. Lecerf, B. Salvy: A Gröbner Free Alternative for Polynomial System Solving, submitted to J. of Complexity (1999)

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

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

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

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

[38] J. Heintz, G. Matera, A. Waissbein: On the time–space complexity of geometric elimination procedures, submitted to AAECC (1999)

[39] 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.

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

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

[42] 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, 237–254 (1982)

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

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

[45] 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, 143, 193-254, Birkhäuser, Basel, (1996)

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

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

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

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

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

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

[52] H. Lombardi: Une borne sur les degrés pour les Théorèmes des zéros réel effectif. in M. Coste, L. Mahé and M.–F. Roy (eds) Real Algebraic Geometry, Rennes 1991, Lecture Notes in Mathematics, Vol. 1524, pp 323–345, Springer Berlin, (1992)

[53] G. Matera: Probabilistic algorithms for geometric elimination. Appl. Algebra Eng. Commun. Comput. 9, No.6, 463-520 (1999)

[54] G. M. Mbakop: Effiziente Lösung reller polynomialer Gleichungssysteme. Dissertaion, Math.– Nat. Fak.II, Humboldt–Universität zu Berlin (1999)

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

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

[57] 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, 33–69 (1995)

[58] R. Piene: Polar classes of singular varieties, Ann. scient. Éc. Norm. Sup. 4. série, t. 11, 247-276 (1978)

[59] 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), 291-295, (1988)

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

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

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

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

[64] 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 [65] M. Shub, S. Smale: Complexity of Bezout’s theorem III: Condition number and packing, J.

of Complexity , 9, 4-14, (1993)

[66] M. Shub, S. Smale: Complexity of Bezout’s theorem IV: Probability of Success, Extensions, SIAM J. Numer. Anal., 33, No.1, 128-148 (1996)

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

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

B. Bank, Institut für Mathematik, Humboldt-Universität zu Berlin, Germany

E-mail address: bank@mathematik.hu-berlin.de

M. Giusti, UMS MEDICIS, Laboratoire GAGE, École Polytechnique, Palaiseau, France

E-mail address: giusti@gage.polytechnique.fr

J. Heintz Departamento de Matemáticas, Estadística y Computación, Facultad de Ciencias, Universidad de Cantabria, Santander, Spain

E-mail address: heintz@matesco.unican.es

Departamento de Matemática, Universidad de Buenos Aires, Argentina

E-mail address: joos@mate.dm.uba.ar

G. M. Mbakop, Institut für Mathematik, Humboldt-Universität zu Berlin, Germany

E-mail address: mbakop@mathematik.hu-berlin.de