Polar Varieties and Computation of one Point in each Connected Component of a Smooth Real Algebraic Set

Mohab Safey El Din

LIP6, Universit� e Paris 6 75005 Paris, France

Mohab.Safey@lip6.fr

� Eric Schost

STIX, � Ecole polytechnique, 91128 Palaiseau, France

Eric.Schost@polytechnique.fr

ABSTRACT

Let f_{1}, …, f_{s} be polynomials in ℚ[X_{1}, …, X_{n}] that generate a radical ideal and let V be their complex zeroset. Suppose that V is smooth and equidimensional; then we show that computing suitable sections of the polar varieties associated to generic projections of V gives at least one point in each connected component of V ∩ ℝ^{n}. We deduce an algorithm that extends that of Bank, Giusti, Heintz and Mbakop to non-compact situations. Its arithmetic complexity is polynomial in the complexity of evaluation of the input system, an intrinsic algebraic quantity and a combinatorial quantity.

Categories and Subject Descriptors

G.m [Mathematics of computing]: Miscellaneous; F.2.2 [Theory of Computation]: Analysis of algorithms and problem complexity—Non numerical algorithms and problems: Geometrical problems and computation

General Terms

Algorithms

Keywords

Polynomial system solving, real solutions, complexity

1. INTRODUCTION

Let V be a smooth and equidimensional complex algebraic variety. This paper is devoted to design an algorithm computing at least one point in each connected component of V ∩ ℝ^{n}. This is a question of importance, since it is for instance one of the basic subroutines used to study semi-algebraic sets, a question which occurs frequently in real-life applications.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for pro�t or commercial advantage and that copies bear this notice and the full citation on the �rst page. To copy otherwise, to republish, to post on servers or to redistribute to lists, requires prior speci�c permission and/or a fee. ISSAC’03, August 3�6, 2003, Philadelphia, Pennsylvania, USA. Copyright 2003 ACM 1-58113-641-2/03/0008 ...$5.00.

In [3, 4], Bank, Giusti, Heintz and Mbakop treat this problem, respectively in the case of complex hypersur-

faces and complete intersections, with compact, smooth real part. To this effect, they use the notion of polar varieties, going back to Poncelet, which we now recall.

The polar varieties are the critical loci of a family of projections defined on V. The last of these polar varieties describes the critical points of the projection on a line, so it has dimension zero, in generic enough coordinates. Furthermore, if V ∩ ℝ^{n} is compact, then any projection on a line has a critical point on each connected component of V ∩ ℝ^{n}. Thus, the last polar variety has dimension zero and gives one point on each connected component of V ∩ ℝ^{n}.

In [3, 4], a local description of the polar varieties by means of regular, reduced sequences enabled to use the elimination techniques of [11, 10, 9, 12] to treat this question with good complexity: the algorithms of [3, 4] have polynomial complexity in an intrinsic geometric degree, the complexity of evaluation of the input system and a combinatorial quantity.

In this paper, we propose an algorithm extending these ideas to smooth varieties, dropping the compactness assumption. We show that in this case, studying suitable zero-dimensional sections of the polar varieties enables to obtain one point on each connected component of V ∩ ℝ^{n}.

Unfortunately, we can no longer use the local description of the polar varieties mentioned above, so our algorithms require stronger elimination techniques. Namely, we use the results of [19, 18, 17], that gives an algorithm with good complexity for zero-dimensional polynomial system solving, without the assumptions of regularity or reducedness.

We deduce an algorithm with a polynomial complexity in the complexity of evaluation of the input system, a quantity bounding the algebraic degrees of some intermediate varieties met during the computation, and a combinatorial quantity. The study of its practical behavior is left to a future work.

Notations and basic de�nitions. All along this arti-

cle, we consider algebraic subsets of ℂ^{n} and real algebraic sets in ℝ^{n}, for some given n. Let f_{1}, …, f_{s} be polynomials in ℚ[X_{1}, …, X_{n}], let V be their complex zero-set and d its dimension. We assume that the polynomials f_{1}, …, f_{s} define a radical ideal and that V is equidimensional and smooth.

For i in 1, …, d, denote by π_{i} the canonical projection

\begin{matrix}ℂ^{n} & → & ℂ^{i} \\ (x_{1}, …, x_{n}) & ↦ & (x_{1}, …, x_{i}). \end{matrix}

We denote by π_{i} its restriction to a map ℝ^{n} → ℝ^{i} and by J the Jacobian matrix of f_{1}, …, f_{s} with respect to X_{n}, …, X_{1} (so as to simplify the subsequent notation):

J = [ \begin{matrix}\frac{∂f_{1}}{∂X_{n}} & ⋯ & \frac{∂f_{1}}{∂X_{1}} \\ ⋮ & & ⋮ \\ \frac{∂f_{s}}{∂X_{n}} & ⋯ & \frac{∂f_{s}}{∂X_{1}} \end{matrix} ] .

We now describe the critical loci of π_{1}, …, π_{d} on V by means of suitable minors of this matrix.

First, for i = d + 1, we define Δ_{n−d} as ⟨f_{1}, …, f_{s}⟩. Then for i = 1, …, d, Δ_{n−i+1} is the ideal generated by f_{1}, …, f_{s} and all minors of size n−d in J built upon the columns 1, …, n − i (that is, using the derivatives with respect to variables X_{i+1}, …, X_{n}). Note that Δ_{n−i+1} is generated by

S_{i} := ( \begin{matrix}s \\ n − d \end{matrix} ) ( \begin{matrix}n − i \\ n − d \end{matrix} )

minors. The i-th polar variety W_{n−i+1} is then defined as the zero-set of Δ_{n−i+1}; in particular, W_{n−d} = V.

Since the ideal ⟨f_{1}, …, f_{s}⟩ is radical and V is equidimensional and smooth, the points in W_{n−i+1} are the critical points of the restriction of π_{i} to V, for i ≤ d. After a generic change of variables, W_{n−i+1} is expected to have codimension n − i + 1 for all i, which accounts for the indexation we used.

Changes of variables. In what follows, we repeatedly use linear changes of variables, so we introduce dedicated notations.

For f ∈ ℚ[X_{1}, …, X_{n}] and A ∈ GL_{n}(ℂ), f(AX) is the polynomial obtained by applying the change of variables A to f. For simplicity, we also write f^{A} = f(AX).

For i ∈ {1, …, d + 1}, the ideal Δ_{n−i+1}^{A} is defined by the polynomials f_{1}^{A}, …, f_{s}^{A} and all minors of size n − d from the first n − i columns of their Jacobian matrix. The polar variety associated to this ideal is denoted by W_{n−i+1}^{A}, so as to make the dependence with respect to A explicit. For consistency, we denote by V^{A} = W_{n−d}^{A} the zero-set of f_{1}^{A}, …, f_{s}^{A}.

Geometric results. Following [3, 4], to compute one point in each connected component of V ∩ ℝ^{n}, we may compute the last polar variety W_{n}, which describes the critical points of the projection on the X_{1}-axis, restricted to V.

Unfortunately, this might not answer the question if V ∩ ℝ^{n} is not compact, since there might be connected components without critical points. In this situation, an answer will come from the study of the images of the connected components of V ∩ ℝ^{n} by the projections π_{1}, …, π_{d}.

To inspect these images, we want to ensure closedness properties. Recall that a map f : A ⊂ ℂ^{n} → ℂ^{i} is proper at b ∈ ℂ^{i} if there exists a neighborhood O of b such that f^{−1}(\overline{O}) is compact, where \overline{O} denotes the closure of O for the strong topology. If f is proper everywhere on its image, we say simply that f is proper; then f is closed for the strong topology.

We are interested in properness properties of the projections π_{i} restricted to our family of polar varieties. Such properties might not hold in the initial coordinates, so we will perform linear changes of coordinates to get back to this favorable situation. We will thus denote by P(A) the following assertion: for i ∈ {1, …, d+ 1}, the restriction of π_{i−1} to W_{n−i+1}^{A} is proper. By convention, for i = 1, in what follows, this means that W_{n}^{A} has dimension zero. An important part of this article is then devoted to prove that P(A) holds for generic A.

Theorem 1 There exists a non-empty Zariski-open set Γ in GL_{n}(ℂ) such that for A in Γ, P(A) holds.

Under this condition, the following theorem enables to compute one point on each connected component of V ∩ ℝ^{n}. Indeed, if the matrix A in Theorem 2 below is in GL_{n}(ℚ), then the connected components of V^{A} ∩ ℝ^{n} are in trivial bijection with those of V ∩ ℝ^{n}.

Theorems 1 and 2 can be considered as our main contributions. They extend the properties used in notably [3, 4], where it was enough to consider the last polar variety W_{n}^{A}, due to the compactness assumption.

Theorem 2 Let A ∈ GL_{n}(ℂ) be such that P(A) holds. Let p_{d} = (x_{1}, …, x_{d}) be any point in ℝ^{d}. For j ∈ {1, …, d − 1}, define p_{j} = (x_{1}, …, x_{j}) ∈ ℝ^{i}. For j = 0, formally define π_{0}^{−1}(p_{0}) as ℂ^{n}.

Then, the algebraic sets W_{n−j}^{A} ∩ π_{j}^{−1}(p_{j}), for j ∈ {0, …, d}, are either empty or zero-dimensional. Their reunion meets every connected component of V^{A} ∩ ℝ^{n}.

Complexity issues. On the basis of Theorem 2, we propose an algorithm to compute one point on each connected component of V ∩ ℝ^{n}. We simply proceed by solving all zero-dimensional systems described in Theorem 2. Their solutions will be represented by a family of geometric resolution. In this article, we define a geometric resolution of a zero-dimensional set Z ⊂ ℂ^{n} defined over ℚ as the data of a linear form u separating the points in Z and polynomials Q, Q_{1}, …, Q_{n} in ℚ[T] such that the relations

Q(u) = 0, { X_{1} = Q_{1}(u), ; ⋮ ; X_{n} = Q_{n}(u),

form a description of the points in Z.

To state our complexity result, we need to define an important algebraic quantity associated to f_{1}, …, f_{s}, denoted by δ. To this effect, we describe more precisely the systems defining the polar varieties.

Let A be a matrix in GL_{n}(ℂ). Recall that S_{i} denotes the number of minors necessary to define the ideal Δ_{n−i+1}^{A}, 1 ≤ i ≤ d + 1. For i = 1, …, d + 1, we denote by M_{i,1}^{A}, …, M_{i,S_{i}}^{A} the ordered sequence of these minors. Due to the definition of the ideals Δ_{n−i+1}^{A}, we are free to assume that these sequences are ordered such that M_{i,1}^{A}, …, M_{i,S_{i}}^{A} is a prefix of M_{j,1}^{A}, …, M_{j,S_{j}}^{A} for i ≥ j. Thus M_{1,1}^{A}, …, M_{1,S_{1}}^{A} is the longest of these sequences.

Let us now consider the long ordered sequence

G^{A} = f_{1}^{A}, …, f_{s}^{A}, M_{1,1}^{A}, …, M_{1,S_{1}}^{A}.

Given any prefix subsequence G of G^{A}, define the quantity δ_{G}^{A} as the sum of the algebraic degrees of the irreducible components of the variety defined by G. We define δ^{A} as the maximum of all δ_{G}^{A}, and δ as the supremum of all δ^{A} for A in GL_{n}(ℚ) such that P(A) holds.

A definition of algebraic degree can be found in [19]. If f_{1}, …, f_{s} are of degree bounded by D, then δ is bounded by n(D(n − d))^{n} [19, page 4].

We can now state our complexity result. We denote by M(x) the number of operations necessary to multiplying polynomials of degree x. The notation f ∈ O_{log} (x) means that f ∈ O(x log(x)^{a}), for some constant a.

Theorem 3 Let f_{1}, …, f_{s} be polynomials of degree bounded by D in ℚ[X_{1}, …, X_{n}], given by a Straight-Line Program of length L. Suppose that ⟨f_{1}, …, f_{s}⟩ is a radical, equidimensional ideal and that V = V (f_{1}, …, f_{s}) ⊂ ℂ^{n} is smooth of dimension d.

There exists a probabilistic algorithm computing a family of geometric resolutions, the reunion of whose real zeros contains at least one point in each connected component of V ∩ ℝ^{n}. In case of success, its complexity is within

O_{log} (Ln^{10}S_{1}(s + S_{1})M (D(n − d)δ)^{3})

arithmetic operations.

The probabilistic aspects come from putting the system in general position, and also appear during the execution of the algorithm of [19]. From Theorem 1, the probability of success depends on the choice of points outside proper Zariski-closed sets.

Our complexity result is similar to that of [3, 4, 5], and in that it depends on the evaluation properties of the input system, a combinatorial number (here denoted by S_{1}) and a suitable intrinsic quantity (here denoted by δ). We did not use the local description of polar varieties by regular sequences from [3, 4], whence the intricate definition of our quantity δ.

A complexity result of the same spirit, but in a somehow different formulation for arbitrary non-compact, smooth, real complete intersection varieties was independently obtained in [5] by a substantially different method.

Related works. In [13, 14, 15, 6, 7, 8], the authors consider arbitrary real algebraic sets, and reduce to the study of smooth and compact real algebraic hypersurfaces, via sums of squares and infinitesimal deformations. Then, the zero-dimensional critical locus of a projection on a well-chosen line is studied. This yields algorithms with complexities simply exponential in the number of variables; no mention of intrinsic quantities is made.

In [21, 2, 22, 23], the problem is treated with a view toward practical efficiency. To deal with non-compact situations, the authors of [21, 2, 22] compute the critical points of the square of the distance to a given point, whereas in [23] we study the set of non properness of a family of projections. No complexity estimates are given.

In this article, we represent the solutions of a zerodimensional polynomial system by means of geometric resolutions. This notion appeared in the series of articles [11, 9, 10, 12], see further references therein. For the similar notion of Rational Univariate Representation and its use in real geometry, we refer to [1, 20, 21].

Organization of the paper. The three remaining sec-

tions are devoted to prove respectively Theorems 1, 2 and 3.

2. PROPERNESS PROPERTIES

This section is devoted to prove that in generic coordinates, all polar varieties satisfy a properness property. This is the content of Theorem 1, which we now restate. There exists a Zariski-open set Γ in GL_{n}(ℂ) such that for A in Γ and i ∈ {1, …, d + 1}, the restriction of the projection π_{i−1} to the polar variety W_{n−i+1}^{A} associated to the polynomials f_{1}^{A}, …, f_{s}^{A} is proper.

The intuition is the following. Through an inductive reasoning, consider that we have found coordinates ensuring a proper projection for W_{n−i}^{A}. In these coordinates, the restriction of π_{i−1} to W_{n−i+1}^{A} may not be proper; then an arbitrary small change of the variables X_{1}, …, X_{i} will not alter W_{n−i+1}^{A}, but will restore the properness of π_{i−1}.

To obtain the existence of the Zariski-open set Γ, we must nevertheless adopt an algebraic point of view. The notion of properness of a projection is strongly related to that of Noether normalization, so we will actually prove that all polar varieties satisfy a Noether normalization statement. Many ideas used below, notably that of examining an incremental intersection process, originate from [11, 10, 9]. In what follows, for r ≤ n, X_{≤r} denotes X_{1}, …, X_{r}, and X denotes X_{1}, …, X_{n}.

2.1 Strategy of proof

Proving Theorem 1 requires to handle generic linear changes of variables. Let thus 𝔄 be a n × n matrix whose entries are new indeterminates (𝔄_{i,j})_{1≤i,j≤n}. We mimic the definitions of the introduction for this “generic” change of variables.

For k ∈ {1, …, s}, define f_{k}^{𝔄} ∈ ℚ(𝔄_{i,j})[X] as f_{k}^{𝔄} = f_{k}(𝔄X). For i ≤ d + 1, we define the ideal Δ_{n−i+1}^{𝔄} similarly to Δ_{n−i+1}^{A} above, that is, using the polynomials f_{k}^{𝔄} and all minors of size n − d from the first n − i columns of their Jacobian matrix. Then W_{n−i+1}^{𝔄} is the zero-set of Δ_{n−i+1}^{𝔄}. Thus W_{n−i+1}^{𝔄} is the polar varieties associated to the “generic” change of variables 𝔄.

Subsection 2.2 is devoted to introduce some technical notation. Then in Subsection 2.3 we prove that the ideals Δ_{n−i+1}^{𝔄} satisfy a Noether normalization property:

Proposition 1 Let i ∈ {1, …, d + 1}, let P be one of the prime components of the radical of the ideal Δ_{n−i+1}^{𝔄}, and let r be its dimension. Then r is at most i − 1 and the extension ℚ(𝔄_{i,j})[X_{≤r}] → ℚ(𝔄_{i,j})[X]/P is integral.

In Subsection 2.4 we show how this property specializes. We use the notation relative to changes of variables, that was defined in the introduction.

Proposition 2 There exists a Zariski open set Γ in GL_{n}(ℂ) such that for A in Γ, the following holds. Let i ∈ {1, …, d+1}, let P^{A} be one of the prime components of the radical of Δ_{n−i+1}^{A}, and r its dimension. Then r is at most i − 1 and ℂ[X_{≤r}] → ℂ[X]/P^{A} is integral.

In Subsection 2.5, we will conclude the proof of Theorem 1 by using a result of [16] to relate the properness property and the above normalization result:

Proposition 3 Let A be in GL_{n}(ℂ) and i ∈ {1, …, d+ 1}. The following assertions are equivalent.

• For every prime component P^{A} of the radical of Δ_{n−i+1}^{A}, the following holds. Let r be the dimension of P^{A}; then r is at most i − 1 and ℂ[X_{≤r}] → ℂ[X]/P^{A} is integral.

• The restriction of π_{i−1} to W_{n−i+1}^{A} is proper.

2.2 Preliminaries

The above propositions rely on the properties of some ring extensions. For the sake of shortness, we introduce the following notation related to these extensions. Let k be a field; given an ideal I ⊂ k[X], we denote by Q(I) the following property: Let P be a prime ideal appearing in the prime decomposition of \sqrt{I}, and r its dimension. Then k[X_{≤r}] → k[X]/P is integral.

For instance, Proposition 1 can then be rephrased as: the ideal Δ_{n−i+1}^{𝔄} satisfies property Q, and has dimension at most i − 1. The following result will be useful to prove that proposition; the proof is immediate.

Lemma 1 Suppose that I is equidimensional of dimension r and that k[X_{≤r}] → k[X]/I is an integral ring extension. Then I satisfies property Q.

2.3 Proof of Proposition 1

We prove the property of Proposition 1 by decreasing induction on i = d + 1, …, 1. Let us first settle the case i = d + 1. Then the ideal Δ_{n−d}^{𝔄} is generated by the polynomials f_{1}^{𝔄}, …, f_{s}^{𝔄} = f_{1}(𝔄X), …, f_{s}(𝔄X). Thus the validity of assertion P_{d+1} follows from the Noether Normalization Theorem.

Let us now assume that the property holds for index i+1, and prove it for index i. We first establish property Q(Δ_{n−i+1}^{𝔄}), then prove the dimension property.

Preliminaries. By definition, Δ_{n−i+1}^{𝔄} is obtained by adjoining some suitable minors of the Jacobian matrix of f_{1}^{𝔄}, …, f_{s}^{𝔄} to the ideal Δ_{n−i}^{𝔄}. Denote by M_{1}^{𝔄}, …, M_{N}^{𝔄} these minors. Proving property Q(Δ_{n−i+1}^{𝔄}) will follow from seeing this intersection process incrementally.

For j = 1, …, N, let Δ_{n−i+1,j}^{𝔄} be the ideal Δ_{n−i}^{𝔄} + (M_{1}^{𝔄}, …, M_{j}^{𝔄}) and define Δ_{n−i+1,0}^{𝔄} = Δ_{n−i}^{𝔄}. Thus, Q(Δ_{n−i+1,0}^{𝔄}) holds, and we want to establish property Q(Δ_{n−i+1,N}^{𝔄}). Thus to conclude, it is enough to prove that Q(Δ_{n−i+1,j}^{𝔄}) implies Q(Δ_{n−i+1,j+1}^{𝔄}), for j ∈ {0, …, N − 1}.

Since i and j are fixed, we simplify the notation by letting Δ = Δ_{n−i+1,j}^{𝔄}, Δ′ = Δ_{n−i+1,j+1}^{𝔄} and M = M_{j+1}^{𝔄}, so that Δ′ = Δ + M. Then Δ satisfies property Q and we want to show that it is also the case for Δ′. We first perform some immediate simplifications.

Let ∩_{ℓ≤L}P_{ℓ} be the prime decomposition of \sqrt{Δ}, for some integer L. Then the prime components of \sqrt{Δ′} are the reunion of the prime components of \sqrt{P_{ℓ} + M}, for ℓ ≤ L, so it is enough to prove that for every ℓ such that P_{ℓ} + M ≠ (1), P_{ℓ} + M satisfies property Q. By assumption, P_{ℓ} has dimension ≤ i for all ℓ; for fixed r ≤ i, we partition the set {1, …, L} as follows:

• ℓ belongs to L^{+} if dim P_{ℓ} = r and P_{ℓ} contains M.

• ℓ belongs to L^{−} if dim P_{ℓ} = r, P_{ℓ} does not contain M and P_{ℓ} + M ≠ (1).

• ℓ belongs to S if dim P_{ℓ} = r, P_{ℓ} does not contain M and P_{ℓ} + M = (1).

• ℓ belongs to R if dim P_{ℓ} ≠ r.

It is enough to prove that Q(P_{ℓ} + M) holds for ℓ in L^{+} ∪ L^{−}, since letting r vary will conclude the proof.

If M belongs to P_{ℓ}, the ideal P_{ℓ} + M coincides with P_{ℓ} and the assumption hypothesis concludes; thus we need only consider ℓ in L^{−}. In this situation, by Krull’s Principal Ideal Theorem, and since P_{ℓ} is prime, P_{ℓ}+M is equidimensional of dimension r − 1. Thus by Lemma 1, it is enough to prove that the extension

ℚ(𝔄_{i,j})[X_{≤r−1}] → ℚ(𝔄_{i,j})[X]/(P_{ℓ} + M)

is integral for ℓ ∈ L^{−}.

The auxiliary polynomials α_{ℓ}. By assumption, the

extension ℚ(𝔄_{i,j})[X_{≤_{r}}] → A_{ℓ} := ℚ(𝔄_{i,j})[X]/P_{ℓ} is an integral ring extension for ℓ in L^{+} ∪ L^{−} ∪ S. Thus we need only prove that for ℓ ∈ L^{−}, P_{ℓ} + M contains a monic polynomial in ℚ(𝔄_{i,j})[X_{≤r−1}][X_{r}]. By Quillen-Suslin’s Theorem, A_{ℓ} is a free ℚ(𝔄_{i,j})[X_{≤r}]- module. Let χ_{ℓ} be the characteristic polynomial of the multiplication by M in A_{ℓ}, seen as a free module, and α_{ℓ} ∈ ℚ(𝔄_{i,j})[X_{≤r}] its constant term. For ℓ ∈ L^{−}, the image of M is a non-zero divisor in A_{ℓ}, so α_{ℓ} is not zero, and P_{ℓ} + M ≠ (1) so α_{ℓ} is not constant. Cayley-Hamilton’s Theorem implies that α_{ℓ} belongs to the ideal P_{ℓ} + M. It is thus enough to prove that α_{ℓ} is monic in X_{r} to prove Q(Δ_{n−i+1}^{𝔄}).

Introduction of a change of variables. Let B be a

matrix in GL_{n}(ℚ) of the form

B = [ \begin{matrix}B′ & 0 \\ 0 & I_{n−r} \end{matrix} ] ,

such that B′ is square of size r, I_{n−r} is the n−r identity matrix and α_{ℓ}(BX) is monic in X_{r} for all ℓ in L^{−}. For the construction of such a matrix, we refer to [11, 9, 10].

We use the change of variables B in two different ways to conclude.

• If P is an ideal in ℚ(𝔄_{i,j})[X], we denote by P^{B} the ideal {f(BX), f ∈ P }; if P is prime, P^{B} is prime of the same dimension. We then have the decomposition \sqrt{Δ^{B}} = ∩_{ℓ≤L}P_{ℓ}^{B}. Let ℓ ∈ L^{+} ∪ L^{−} ∪ S. We claim that the constant term of the characteristic polynomial of the multiplication by M(BX) modulo P_{ℓ}^{B} is α_{ℓ}(BX). Indeed, let {G_{1}, …, G_{D}} be a basis of the free ℚ(𝔄_{i,j})[X_{≤r}]-module A_{ℓ}. The linear change of variables B affects only the first r variables, so {G_{1}(BX), …, G_{D}(BX)} is a ℚ(𝔄_{i,j})[X_{≤r}]-basis of ℚ(𝔄_{i,j})[X]/P_{ℓ}^{B}; our assertion follows.

• Let (ℭ_{i,j})_{1≤i,j≤n} be the entries of the matrix 𝔄B; thus all ℭ_{i,j} are linear forms in the entries of 𝔄 with rational coefficients. Given a polynomial f in ℚ(𝔄_{i,j})[X], we denote by Subs_{ℭ}(f) ∈ ℚ(𝔄_{i,j})[X] the polynomial f where each variable 𝔄_{i,j} is substituted by the linear form ℭ_{i,j}. If P is an ideal in ℚ(𝔄_{i,j})[X], we denote by P^{ℭ} the ideal {Subs_{ℭ}(f), f ∈ P }. As above, if P is prime, P^{ℭ} is prime of the same dimension and we have the equality \sqrt{Δ^{ℭ}} = ∩_{ℓ≤L}P_{ℓ}^{ℭ}. Let ℓ ∈ L^{+} ∪ L^{−} ∪ S. Using the same argumentation as above, we see that the constant term of the characteristic polynomial of the multiplication by Subs_{ℭ}(M) modulo P_{ℓ}^{ℭ} is Subs_{ℭ}(α_{ℓ}).

Two useful equalities. We now prove that Δ^{B} = Δ^{ℭ}

and M(BX) = Subs_{ℭ}(M). Recall that the polynomials f_{1}^{𝔄}, …, f_{s}^{𝔄} together with some minors of their Jacobian matrix generate the ideal Δ. We need not be more precise on these minors, and simply denote them by M_{1}^{𝔄}, …, M_{Q}^{𝔄}. To prove the above equalities, it is enough to prove that if f is any of the polynomials f_{1}^{𝔄}, …, f_{s}^{𝔄}, M_{1}^{𝔄}, …, M_{Q}^{𝔄}, M, the equality f(BX) = Subs_{ℭ}(f) holds.

Consider first the polynomials f_{k}^{𝔄}. They are defined by f_{k}^{𝔄} = f_{k}(𝔄X), from which we deduce Subs_{ℭ}(f_{k}^{𝔄}) = f_{k}(ℭX) = f_{k}(𝔄BX) = f_{k}^{𝔄}(BX) for k ≤ s, as requested.

We now turn to the minors M_{1}^{𝔄}, …, M_{Q}^{𝔄} and M. They are defined using the first n − i columns of the Jacobian matrix of the polynomials f_{k}^{𝔄}, i.e., with partial derivatives of these polynomials with respect to the variables X_{i+1}, …, X_{n}. It is then enough to prove that (∂f_{k}^{𝔄}/∂X_{j})(BX) = Subs_{ℭ}(∂f_{k}^{𝔄}/∂X_{j}) for k ≤ s and j > i. But this is an immediate consequence of the definition of the polynomials f_{k}^{𝔄}, and of the fact that the change of variables B acts trivially on the variables X_{i+1}, …, X_{n} since r ≤ i.

Proof of property Q(Δ_{n−i+1}^{𝔄}). The equality Δ^{B} = Δ^{ℭ} implies ∩_{ℓ≤L}P_{ℓ}^{B} = ∩_{ℓ≤L}P_{ℓ}^{ℭ}, and uniqueness of the prime decomposition yields

{P_{ℓ}^{B}, ℓ ∈ L} = {P_{ℓ}^{ℭ}, ℓ ∈ L}.

Since dim P_{ℓ}^{B} = dim P_{ℓ}^{ℭ} = dim P_{ℓ} for all ℓ, we deduce

{P_{ℓ}^{B}, ℓ ∈ L^{+} ∪ L^{−} ∪ S} = {P_{ℓ}^{ℭ}, ℓ ∈ L^{+} ∪ L^{−} ∪ S}.

Let ℓ in L^{−}. By the last equality, there exists ℓ′ in L^{+} ∪ L^{−} ∪ S, such that P_{ℓ}^{ℭ} = P_{ℓ′}^{B}. Since M^{B} = Subs_{ℭ}(M), the characteristic polynomial of Subs_{ℭ}(M) modulo P_{ℓ}^{ℭ} is the characteristic polynomial of M^{B} modulo P_{ℓ′}^{B}, so Subs_{ℭ}(α_{ℓ}) = α_{ℓ′}(BX) by the above discussion. Since α_{ℓ} is neither zero nor constant, α_{ℓ′} is neither zero nor constant, so ℓ′ ∈ L^{−}. Thus α_{ℓ′}(BX) = Subs_{ℭ}(α_{ℓ}) is monic in X_{r}, and so is α_{ℓ}.

Conclusion. It only remains to prove that W_{n−i+1}^{𝔄} has dimension at most i−1. Let 𝔎 be an algebraic closure of ℚ(𝔄_{i,j}) and Π_{i} the canonical projection 𝔎^{n} → 𝔎^{i}. Due to our definitions, W_{n−d}^{𝔄} ⊂ 𝔎^{n} is smooth and equidimensional, and W_{n−i+1}^{𝔄} is the critical locus of Π_{i} on W_{n−d}^{𝔄} for i ≤ d.

We deduce that for i ≤ d, W_{n−i+1}^{𝔄} is contained in the reunion of (i) the singular locus of W_{n−i}^{𝔄} and (ii) the critical locus of the restriction of π_{i} to the regular locus of W_{n−i}^{𝔄}. It is thus enough to prove that this last object has dimension at most i − 1.

Let us write the irreducible decomposition of W_{n−i}^{𝔄} as ∪_{ℓ≤L}Z_{ℓ}. By the induction assumption, all Z_{ℓ} have dimension at most i; it is thus enough to consider the components of dimension i to conclude. The induction statement asserts that the restriction of π_{i} to any of these components is a finite map. Then the conclusion follows from the algebraic Bertini-Sard Theorem [24].

2.4 Proof of Proposition 2

Fix i ∈ {1, …, d + 1}, and consider the ideal Δ_{n−i+1}^{𝔄}. Since i is fixed, we write Δ = Δ_{n−i+1}^{𝔄}. Let (P_{ℓ})_{ℓ≤L} be the prime components of \sqrt{Δ} in ℚ(𝔄_{i,j})[X], so that \sqrt{Δ} = ∩_{ℓ≤L}\sqrt{P_{ℓ}}, and let G_{ℓ,1}, …, G_{ℓ,N_{ℓ}} ∈ ℚ(𝔄_{i,j})[X] be some generators of P_{ℓ}.

There is a Zariski-open subset Γ of GL_{n}(ℂ) such that for A in Γ, the entries of Γ cancel none of the denominators of the coefficients of G_{ℓ,i}, for ℓ ≤ L and i ≤ N_{ℓ}. Then we denote by G_{ℓ,i}^{A} the polynomial in ℂ[X] obtained by evaluating all coefficients of G_{ℓ,i} at the entries of A, and by Q_{ℓ}^{A} the ideal generated by G_{ℓ,1}^{A}, …, G_{ℓ,N_{ℓ}}^{A}.

Remark: The letter P is used for prime ideals; we do not claim that (G_{ℓ,1}^{A}, …, G_{ℓ,N_{ℓ}}^{A}) remains prime, this is why we use the letter Q.

To prove Proposition 2, we proceed as follows. We first prove that the equality \sqrt{Δ^{A}} = ∩_{ℓ≤L}\sqrt{Q_{ℓ}^{A}} holds for all A in Γ. In a second time we prove that every ideal Q_{ℓ}^{A} satisfies property Q and is equidimensional of dimension at most i − 1. Even if Q_{ℓ}^{A} is not prime, this is enough to prove Proposition 2. Proving these results may require to remove strict Zariski-closed sets from Γ.

First Step: \sqrt{Δ^{A}} = ∩_{ℓ≤L}\sqrt{Q_{ℓ}^{A}}. Let f_{1}^{𝔄}, …, f_{s}^{𝔄} and M_{1}^{𝔄}, …, M_{N}^{𝔄} be the polynomials generating the ideal Δ. By definition, for ℓ ≤ L, all these polynomials belong to P_{ℓ}, which can be expressed by a series of equalities in ℚ(𝔄_{i,j})[X] giving them as a combination of G_{ℓ,1}, …, G_{ℓ,N_{ℓ}}. In all these equalities, the indeterminates 𝔄_{i,j} can be replaced by the entries of any matrix A ∈ Γ, yielding equalities in ℂ[X]. Thus, for A in Γ, Δ^{A} ⊂ ∩_{ℓ}Q_{ℓ}^{A}, whence \sqrt{Δ^{A}} ⊂ ∩_{ℓ}\sqrt{Q_{ℓ}^{A}}.

Conversely, let us form the products G_{1,i_{1}} ⋯ G_{L,i_{L}}, for all possible multi-indices i = (i_{1}, …, i_{L}). All these products belong to the radical of Δ, so there exists N ∈ ℕ such that every (G_{1,i_{1}} ⋯ G_{L,i_{L}})^{N} ∈ Δ. Then every product (G_{1,i_{1}}^{A} ⋯ G_{L,i_{L}}^{A})^{N} belongs to Δ^{A} for all A ∈ Γ, whence (Q_{1}^{A} ⋯ Q_{L}^{A})^{N} ⊂ Δ^{A}. Taking radicals yields ∩_{ℓ}\sqrt{Q_{ℓ}^{A}} ⊂ \sqrt{Δ^{A}}.

Second Step: Properties of Q_{ℓ}^{A}. Let ℓ ≤ L and r_{ℓ} the

dimension of P_{ℓ}. Up to removing a Zariski-closed subset from Γ, we claim that Q_{ℓ}^{A} is equidimensional of dimension r_{ℓ} too. As quick way to see this, remark that an equidimensional decomposition can be performed by an algorithm without factorization. Then for A in a suitable Zariski-open set, the execution over ℂ[X] for the polynomials defining Q_{ℓ}^{A} is the trace of the execution in ℚ(𝔄_{i,j})[X] for the polynomials defining P_{ℓ}, which is assumed to give an equidimensional result of dimension r_{ℓ}.

To conclude, it is thus enough to prove property Q for Q_{ℓ}^{A}. By Proposition 1, for ℓ ≤ L and i ∈ {r_{ℓ} + 1, …, n} there exists a polynomial m_{i} ∈ ℚ(𝔄_{i,j})[X_{≤r_{ℓ}}][T] such that m_{i}(X_{i}) belongs to P_{ℓ}. Again, after removing the Zariski-closed subset from Γ that is defined by the denominators appearing in the underlying equalities, we deduce that ℂ[X_{≤r_{ℓ}}] → ℂ[X]/Q_{ℓ}^{A} is integral for A ∈ Γ. We deduce that Q_{ℓ}^{A} satisfies property Q by Lemma 1.

2.5 Proving properness

We finish the proof of Theorem 1 by proving Prop. 3. Let A be in GL_{n}(ℂ) and i ∈ {2, …, d + 1} (case i = 1 is trivial).

Let (P_{ℓ}^{A})_{ℓ≤L} be the prime components of Δ_{n−i+1}^{A} and (r_{ℓ})_{ℓ≤L} their dimensions. The restriction of π_{i−1} to W_{n−i+1}^{A} is proper if and only if all its restrictions to the zero-sets V (P_{ℓ}^{A}) are proper. Thus to conclude, we prove that the restriction of π_{i−1} to V (P_{ℓ}^{A}) is proper if and only if the extension ℂ[X_{≤r_{ℓ}}] → ℂ[X]/P_{ℓ}^{A} is integral and r_{ℓ} ≤ i − 1, for ℓ ≤ L.

For j ∈ {r_{ℓ} + 1, …, n}, let m_{j} ∈ ℂ(X_{≤r_{ℓ}})[T] be the monic minimal polynomial of X_{j} in the algebraic field extension ℂ(X_{≤r_{ℓ}}) → 𝔣𝔯𝔞𝔠(ℂ[X]/P_{ℓ}^{A}). Lemma 3.10 in [16] states that the set of non-properness for the restriction of π_{r_{ℓ}} to V (P_{ℓ}^{A}) is the reunion of the zero-sets of the denominators of the coefficients of the polynomials m_{j}. Thus the restriction of π_{r_{ℓ}} to V (P_{ℓ}^{A}) is proper if and only if the extension ℂ[X_{≤r_{ℓ}}] → ℂ[X]/P_{ℓ}^{A} is integral.

Then, the restriction of π_{i−1} to V (P_{ℓ}^{A}) is proper if and only if the restriction of π_{r_{ℓ}} to V (P_{ℓ}^{A}) is proper and r_{ℓ} ≤ i − 1. This concludes the proof.

Remark: Dimension of �bers. From [24, Chapter

1.5.3], all fibers of the restriction of π_{r_{ℓ}} to V (P_{ℓ}) are finite, for ℓ ≤ L. Since r_{ℓ} ≤ i − 1, we deduce that all fibers of the restriction of π_{i−1} to W_{n−i+1}^{A} have finite cardinality. This proves the first statement of Theorem 2.

3. PROOF OF THEOREM 2

We now investigate the relation between the polar varieties of f_{1}, …, f_{s} and the connected components of V ∩ ℝ^{n}. Namely, we conclude the proof of Theorem 2: Let A ∈ GL_{n}(ℂ) be such that P(A) holds. Let p_{d} = (x_{1}, …, x_{d}) be any point in ℝ^{d}. For j ∈ {1, …, d − 1}, define p_{j} = (x_{1}, …, x_{j}) ∈ ℝ^{i}, and π_{0}^{−1}(p_{0}) = ℂ^{n}. Then the algebraic sets W_{n−j}^{A} ∩ π_{j}^{−1}(p_{j}), j ∈ {0, …, d}, are either empty or zero-dimensional. Their reunion meets every connected component of V^{A} ∩ ℝ^{n}.

Since the matrix A is fixed once and for all in this section, there is no need to systematically make explicit mention of it. Thus, in all the rest of this section, we simply write W_{n−i+1} and V instead of W_{n−i+1}^{A} and V^{A}. Our hypothesis will simply be denoted by P: for all i in 1, …, d+1, the restriction of π_{i−1} to W_{n−i+1} is proper. In what follows, we first prove a geometric result on the frontier of the projections of the connected components of V ∩ ℝ^{n}, then conclude the proof of Theorem 2. The frontier of A ⊂ ℝ^{i} is the closure of A minus the interior of A (for the strong topology). We use the fact that for A, B ⊂ ℝ^{i}, if A is connected and meets both B and its complementary, then A meets the frontier of B.

Proposition 4 Let D be a connected component of V ∩ ℝ^{n}. For i in 1, …, d, the frontier of π_{i}(D) ⊂ ℝ^{i} is included in π_{i}(W_{n−i+1} ∩ D).

Proof. Let us denote this property by 𝔔_{i}. We prove it by decreasing induction on i = d, …, 1. First, we prove 𝔔_{d}. Let x ∈ ℝ^{d} be in the frontier of π_{d}(D). By assumption P, the restriction of π_{d} to V ∩ ℝ^{n} is proper, so x is in the image π_{d}(D). Thus, since V ∩ ℝ^{n} is smooth, from the implicit function theorem, there exists a critical point y ∈ D of π_{d} restricted to V such that π_{d}(y) = x. This proves 𝔔_{d}.

We now assume 𝔔_{i+1}, and prove 𝔔_{i}. Let thus x ∈ ℝ^{i} be in the frontier of π_{i}(D) ⊂ ℝ^{i}. It is enough to prove that x is in π_{i}(D): as in the previous paragraph, the implicit function theorem then proves that x is a critical point of the restriction of π_{i} to D, which gives property 𝔔_{i}.

Thus, we prove that x is in π_{i}(D). Let φ be the projection φ : ℝ^{i+1} → ℝ^{i} that maps (x_{1}, …, x_{i+1}) to (x_{1}, …, x_{i}); for r > 0, we denote by B_{r} ⊂ ℝ^{i} the closed ball centered at x of radius r, and by C_{r} ⊂ ℝ^{i+1} the preimage φ^{−1}(B_{r}), which is a cylinder.

By definition, for r > 0, π_{i}^{−1}(B_{r}) meets D, so C_{r} meets π_{i+1}(D). On the other hand, since x is in the frontier of π_{i}(D), there exists a point in B_{r} that is not π_{i}(D), so there exists a point in C_{r} that is not in π_{i+1}(D). We deduce that for r > 0, C_{r} meets the frontier of π_{i+1}(D).

By induction hypothesis, there exists y_{r} ∈ W_{n−i} ∩ D such that π_{i+1}(y_{r}) ∈ C_{r}. Applying φ, we deduce that π_{i}(y_{r}) ∈ B_{r}. Since this holds for all r > 0, x is in the closure of π_{i}(W_{n−i} ∩ D). By assumption P, the restriction of π_{i} to W_{n−i} ∩D is proper, so π_{i}(W_{n−i} ∩D) is closed. Thus x is in π_{i}(W_{n−i} ∩ D) ⊂ π_{i}(D). □

Now, we are ready to prove Theorem 2. Let p_{d} = (x_{1}, …, x_{d}) be an arbitrary point in ℝ^{d}, and let p_{j} = (x_{1}, …, x_{j}) for j = 1, …, d − 1. Let D be a connected component of V ∩ ℝ^{n}. We will prove that there exists j_{0} ∈ {0, …, d} such that π_{j}^{−1}(p_{j_{0}}) ∩ W_{n−j_{0}} meets D, with the convention that π_{0}^{−1}(p_{0}) = ℂ^{n}.

For j = 0, …, d − 1, we denote by C_{j} ⊂ ℝ^{j+1} the cylinder {p_{j}} × ℝ built above p_{j} (we take C_{0} = ℝ); note that p_{j+1} belongs to C_{j} by definition.

Consider the subset J ⊂ {0, …, d − 1} such that j ∈ J if and only if C_{j} intersects the frontier of π_{j+1}(D), at a point denoted by x_{j+1}. First, suppose that J is not empty. Then, by Proposition 4, for j_{0} ∈ J, x_{j_{0}+1} belongs to π_{j_{0}+1}(W_{n−j_{0}} ∩ D), so p_{j_{0}} belongs to π_{j_{0}}(W_{n−j_{0}} ∩ D), which concludes the proof.

Now, suppose that J is empty. We shall show below that this implies that for all j ∈ {0, …, d − 1}, C_{j} is included in π_{j+1}(D). For the moment, suppose that it is true. Then for index d − 1, this yields that C_{d−1} is contained in π_{d}(D). Since p_{d} is in C_{d−1}, p_{d} is in π_{d}(D), and we take j_{0} = d (recall that W_{n−d} = V).

It remains to show that, under the assumption that J is empty, for all j ∈ {0, …, d − 1}, C_{j} is included in π_{j+1}(D). We proceed by induction on j. First take j = 0. By assumption, the frontier of π_{1}(D) is empty, so π_{1}(D) = ℝ = C_{0}, as requested. Now, suppose that C_{j−1} is contained in π_{j}(D); in particular, p_{j} belongs to π_{j}(D), so C_{j} meets π_{j+1}(D). Since J is empty, C_{j} does not intersect the frontier of π_{j+1}(D), so C_{j} is contained in π_{j+1}(D). This ends the proof.

4. PROOF OF THEOREM 3

We finally present our algorithm. It takes as input f_{1}, …, f_{s} in ℚ[X_{1}, …, X_{n}] that generate an equidimensional and radical ideal of dimension d, whose zeroset V is smooth. It returns a set of geometric resolutions describing zero-dimensional sets, whose reunion intersects every connected component of V ∩ ℝ^{n}. We suppose that f_{1}, …, f_{s} have degree bounded by D and are given by a Straight-Line Program of size L.

The first step of the algorithm applies a randomly chosen change of variables A with rational coefficients to the input system. As usually, denote by f_{1}^{A}, …, f_{s}^{A} the polynomials we obtain. Then we choose an arbitrary point p_{d} = (x_{1}, …, x_{d}) in ℚ^{d} and compute geometric resolutions of the zero-dimensional sets W_{n−i+1}^{A}∩ π_{i−1}^{−1}(p_{i−1}), for i ∈ {1, …, d + 1}. Correctness follows from Theorem 2, as soon as A satisfies property P defined in the introduction.

To estimate the complexity of the process, we use the following result adapted from [19]. The notations used here are defined in the introduction.

Theorem 4 [19] Let g_{1}, …, g_{S} be polynomials of degree bounded by D in ℚ[X_{1}, …, X_{n}], represented by a Straight-Line Program of length L and defining a zerodimensional variety. There exists an algorithm computing a geometric resolution of V (g_{1}, …, g_{S}) whose arithmetic complexity is:

O_{log} (Sn^{4}(nL + n^{4})M(D𝔡))^{3}

where 𝔡 is the maximum of the sums of the algebraic degrees of the irreducible components of the intermediate varieties defined by g_{1}, …, g_{i} for i in 1, …, S.

As a shorthand, in what follows, we refer to the quantity 𝔡 above as the algebraic degree of g_{1}, …, g_{S}.

To prove Theorem 3, we must describe the systems we use to define the zero-dimensional sets W_{n−i+1}^{A} ∩ π_{i−1}^{−1}(p_{i−1}). We freely make use of the notation M_{i,j}^{A} defined in the introduction, and adopt the same ordering convention. Then W_{n−i+1}^{A} ∩ π_{i−1}^{−1}(p_{i−1}) is defined by

f_{1}^{A}, …, f_{s}^{A}, M_{i,1}^{A}, …, M_{i,S_{i}}^{A},

where X_{1}, …, X_{i} are specialized at p_{1}, …, p_{i}.

All polynomials in these systems have degree at most D(n − d). Due to the application of the change of variables A, the polynomials f_{k}^{A} can be evaluated within L+n^{2} operations. Using Baur-Strassen’s and Berkowitz’ algorithms, any Jacobian minor involved in the above systems can be evaluated in (n−d)^{4}(L+n^{2}) operations. Since S_{i} ≤ 3DS_{1} for all i, any of the above systems can be evaluated within O(S_{1}n^{4}(L + n^{2})) operations.

To apply Theorem 4, we relate the algebraic degrees of the above systems to the quantity δ defined in the introduction. This is actually straightforward. Specializing variables only lowers the algebraic degree. Using our ordering convention, we deduce that the algebraic degrees of all the systems we solve are bounded by that of

f_{1}^{A}, …, f_{s}^{A}, M_{1,1}^{A}, …, M_{1,S_{1}}^{A}.

By definition, this quantity is bounded by δ.

The proof of Theorem 3 follows immediately. First we plug the above data into the complexity estimate of Theorem 4, and perform slight simplifications. We finally restore the initial coordinates; the cost is negligible [19].

5. REFERENCES

[1] M. E. Alonso, E. Becker, M.-F. Roy, and T. Wörmann. Zeroes, multiplicities and idempotents for zerodimensional systems. In Proceedings MEGA’94, volume 142 of Progress in Mathematics, pages 1–15. Birkhäuser, 1996.

[2] P. Aubry, F. Rouillier, and M. Safey El Din. Real solving for positive dimensional systems. Journal of Symbolic Computation, 34(6):543–560, 2002.

[3] B. Bank, M. Giusti, J. Heintz, and G.-M.

Mbakop. Polar varieties and efficient real equation solving: the hypersurface case. Journal of Complexity, 13(1):5–27, 1997.

[4] B. Bank, M. Giusti, J. Heintz, and G.-M. Mbakop. Polar varieties and efficient real elimination. Mathematische Zeitschrift, 238(1):115–144, 2001.

[5] B. Bank, M. Giusti, J. Heintz, and L.-M. Pardo. The light is polar. Unpublished manuscript, 2003.

[6] S. Basu. Algorithms in semi-algebraic geometry. PhD thesis, New-York University, 1996.

[7] S. Basu, R. Pollack, and M.-F. Roy. On the combinatorial and algebraic complexity of quantifier elimination. Journal of ACM, 43(6):1002–1045, 1996.

[8] S. Basu, R. Pollack, and M.-F. Roy. A new algorithm to find a point in every cell defined by a family of polynomials. In Quantifier elimination and cylindrical algebraic decomposition. Springer-Verlag, 1998.

[9] M. Giusti, K. Hägele, J. Heintz, J.-E Morais, J.-L. Montaña, and L.-M. Pardo. Lower bounds for Diophantine approximation. In Proceedings of MEGA’96, number 117, 118 in Journal of Pure and Applied Algebra, pages 277–317, 1997.

[10] M. Giusti, J. Heintz, J.-E. Morais, J. Morgenstern, and L.-M. Pardo. Straight-line programs in geometric elimination theory. Journal of Pure and Applied Algebra, 124:101–146, 1998.

[11] M. Giusti, J. Heintz, J.-E. Morais, and L.-M. Pardo. When polynomial equation systems can be solved fast? In Proceedings of AAECC-11, volume 948 of LNCS, pages 205–231. Springer, 1995.

[12] M. Giusti, G. Lecerf, and B. Salvy. A Gröbner free alternative for polynomial system solving. Journal of Complexity, 17(1):154–211, 2001.

[13] D. Grigoriev and N. Vorobjov. Solving systems of polynomials inequalities in subexponential time. Journal of Symbolic Computation, 5:37–64, 1988.

[14] J. Heintz, M.-F. Roy, and P. Solernò. On the complexity of semi-algebraic sets. In Proceedings IFIP’89 San Francisco, North-Holland, 1989.

[15] J. Heintz, M.-F. Roy, and P. Solernò. On the theoretical and practical complexity of the existential theory of the reals. The Computer Journal, 36(5):427–431, 1993.

[16] Z. Jelonek. Testing sets for properness of polynomial mappings. Mathematische Annalen, 315(1):1–35, 1999.

[17] G. Jeronimo, T. Krick, J. Sabia, and M. Sombra. The computational complexity of the Chow form. Technical report Institut de mathématiques de Jussieu, 2003.

[18] G. Jeronimo, and J. Sabia. Effective equidimensional decomposition of affine varieties. Journal of Pure and Applied Algebra, 169(2-3):229-248, 2002.

[19] G. Lecerf. Computing the equidimensional decomposition of an algebraic closed set by means of lifting fibers. To appear in Journal of Complexity, 2003.

[20] F. Rouillier. Solving zero-dimensional systems through the Rational Univariate Representation. AAECC Journal, 9(5):433–461, 1999.

[21] F. Rouillier, M.-F. Roy, and M. Safey El Din. Finding at least one point in each connected component of a real algebraic set defined by a single equation. Journal of Complexity, 16:716–750, 2000.

[22] M. Safey El Din. Résolution réelle des systèmes polynomiaux de dimension positive. PhD thesis, Université Paris 6, January 2001.

[23] M. Safey El Din and É. Schost. Properness defects of projections and computation of one point in each connected component of a real algebraic set. Technical report, RR INRIA, 2002.

[24] I. Shafarevich. Basic Algebraic Geometry 1. Springer Verlag, 1977.