Peter Bürgisser

Felipe Cucker
email: macucker@cityu.edu.hk

Computing the Homology of Basic Semialgebraic Sets in Weak Exponential Time

Keywords: CCS Concepts:, Theory of computation → Computational geometry;, Computing methodologies → Hybrid symbolic-numeric methods Semialgebraic geometry, homology, algorithm ACM Reference Format:

INTRODUCTION

Semialgebraic sets (that is, subsets of Euclidean spaces defined by polynomial equations and inequalities with real coefficients) come in a wide variety of shapes and this raises the problem of describing a given specimen, from the most primitive features, such as emptiness, dimension, or number of connected components, to finer ones, such as roadmaps, Euler-Poincaré characteristic, Betti numbers, or torsion coefficients.

The Cylindrical Algebraic Decomposition (CAD) introduced by Collins [START_REF] Collins | Quantifier elimination for real closed fields by cylindrical algebraic deccomposition[END_REF] and Wüthrich [START_REF] Wüthrich | Ein Entscheidungsverfahren für die Theorie der reell-abgeschlossenen Körper[END_REF] in the 1970's provided algorithms to compute these features that worked within time (sD) 2 O(n) where s is the number of defining equations, D a bound on their degree and n the dimension of the ambient space. Subsequently, a substantial effort was devoted to design algorithms for these problems with single exponential algebraic complexity bounds [4, and references therein], that is, bounds of the form (sD) n O (1) . Such algorithms have been found for deciding emptiness [START_REF] Basu | On the combinatorial and algebraic complexity of quantifier elimination[END_REF][START_REF] Yu | Solving Systems of Polynomial Inequalities in Subexponential Time[END_REF][START_REF] Renegar | On the Computational Complexity and Geometry of the First-order Theory of the Reals. Part I[END_REF], for counting connected components [START_REF] Basu | Computing roadmaps of semi-algebraic sets on a variety[END_REF][START_REF] Canny | Computing roadmaps of general semi-algebraic sets[END_REF][START_REF] Canny | Finding connected components of a semialgebraic set in subexponential time[END_REF][START_REF] Yu | Counting connected components of a semialgebraic set in subexponential time[END_REF][START_REF] Heintz | Single exponential path finding in semi-algebraic sets. II. The general case[END_REF], computing the dimension [START_REF] Basu | Computing the Dimension of a Semi-Algebraic Set[END_REF][START_REF] Koiran | The real dimension problem is NP R -complete[END_REF], the Euler-Poincaré characteristic [START_REF] Basu | On Bounding the Betti Numbers and Computing the Euler Characteristic of Semi-Algebraic Sets[END_REF], the first few Betti numbers [START_REF] Basu | Computing the First Few Betti Numbers of Semi-Algebraic Sets in Single Exponential Time[END_REF], the top few Betti numbers [START_REF] Basu | Computing the top Betti numbers of semialgebraic sets defined by quadratic inequalities in polynomial time[END_REF] and roadmaps (embedded curves with certain topological properties) [START_REF] Basu | A Baby Step-Giant Step Roadmap Algorithm for General Algebraic Sets[END_REF][START_REF] Canny | Computing Roadmaps of General Semi-Algebraic Sets[END_REF][START_REF] Safey | A Nearly Optimal Algorithm for Deciding Connectivity Queries in Smooth and Bounded Real Algebraic Sets[END_REF].

As of today, however, no single exponential algorithm is known for the computation of the whole sequence of the homology groups (Betti numbers and torsion coefficients). For complex smooth projective varieties, Scheiblechner [START_REF] Scheiblechner | Castelnuovo-Mumford regularity and computing the de Rham cohomology of smooth projective varieties[END_REF] has been able to provide an algorithm computing the Betti numbers (but not the torsion coefficients) in single exponential time relying on the algebraic De Rham cohomology. The same author provided a lower bound for this problem (assuming integer coefficients) in [START_REF] Scheiblechner | On the complexity of deciding connectedness and computing Betti numbers of a complex algebraic variety[END_REF], where the problem is shown to be PSpace-hard.

Another line of research, that has developed independently of the results just mentioned, focuses on the complexity and the geometry of numerical algorithms [18, and references therein]. The characteristic feature of these algorithms is the use of approximations and successive refinements. For most problems, a set of numerically ill-posed data can be identified, for which arbitrarily small perturbations may produce qualitative errors in the result of the computation. Iterative numerical algorithms may run forever on ill-posed data, and may take increasingly long running time as data become close to ill-posed. The running time is therefore not bounded by a function on the input size only and the usual worst-case analysis is irrelevant. An alternate form of analysis, championed by Smale [START_REF] Smale | Complexity theory and Numerical Analysis[END_REF] and going back to [START_REF] Hestenes | Methods of conjugate gradients for solving linear systems[END_REF], bounds the running time of an algorithm in terms of the size of the input and a condition number, usually related to, or bounded by, the inverse to the distance of the data at hand to the set of ill-posed data.

Then, the most common way to gauge the complexity of a numerical algorithm is to endow the space of data with a probability measure, usually the standard Gaussian, and to analyze the algorithm's cost in probabilistic terms. More often than not, this analysis results in a bound on the expectation of the cost, that is, in an average-case analysis. But recently, Amelunxen and Lotz [START_REF] Amelunxen | Average-case complexity without the black swans[END_REF] introduced a new way of measuring complexity. They noticed that a number of algorithms that are known to be efficient in practice have nonetheless a large, or even infinite, average-case complexity. One of the reasons they identified for this discrepancy is the exponentially fast vanishing measure of an exceptional set of inputs on which the algorithm runs in superpolynomial time when the dimension grows. A prototype of this phenomenon is the behavior of the power method to compute a dominant eigenpair of a symmetric matrix. This algorithm is considered efficient in practice, yet it has been shown that the expectation of the number of iterations performed by the power method, for matrices drawn from the orthogonal ensemble, is infinite [START_REF] Kostlan | Complexity theory of numerical linear algebra[END_REF]. Amelunxen and Lotz show that, conditioned to exclude a set of exponentially small measure, this expectation is O(n 2 ) for n × n matrices. The moral of the story is that the power method is efficient in practice because it is so in theory if we disregard a vanishingly small set of outliers. This conditional expectation, in the terminology of [START_REF] Amelunxen | Average-case complexity without the black swans[END_REF], shows a weak average polynomial cost for the power method. More generally, we will talk about a complexity bound being weak when this bound holds out of a set of exponentially small measure.

Several problems related to semialgebraic sets have been studied from the numerical point of view we just described, such as deciding emptiness [START_REF] Cucker | Complexity Estimates depending on Condition and round-off error[END_REF], counting real solutions of zero-dimensional systems [START_REF] Cucker | A numerical algorithm for zero counting. I: Complexity and accuracy[END_REF], or computing the homology groups of real projective sets [START_REF] Cucker | Computing the Homology of Real Projective Sets[END_REF]. Our main result follows this stream.

Main result. A basic semialgebraic set is a subset of a Euclidean space R n given by a system of equalities and inequalities of the form

f 1 (x) = • • • = f q (x
) = 0 and д 1 (x) ≻ 0, . . . , д s (x) ≻ 0 [START_REF] Amelunxen | Average-case complexity without the black swans[END_REF] where F = (f 1 , . . . , f q ) and G = (д 1 , . . . , д s ) are tuples of polynomials with real coefficients and the expression д(x) ≻ 0 stands for either д(x) ⩾ 0 or д(x) > 0 (we use this notation to emphasize the fact, that will become clear in §4. 1.4, that our main result does not depend on whether the inequalities in (1) are strict). Let W (F, G) denote the solution set of the semialgebraic system [START_REF] Amelunxen | Average-case complexity without the black swans[END_REF]. For a vector d = (d 1 , . . . , d q+s ) of q + s positive integers, we denote by P d (or P d [q ; s] to emphasize the number of components) the linear space of the (q + s)-tuples of real polynomials in n variables of degree at most d 1 , . . . , d q+s , respectively. Let D denote the maximum of the d i . We will assume that D ⩾ 2 because a set defined by degree 1 polynomials is convex and its homology Computing the Homology of Basic Semialgebraic Sets 5:3 is trivial. Let N denote the dimension of P d , that is,

N = q+s i=1 n + d i n . (2)
This is the size of the semialgebraic system (1), as it is the number of real coefficients necessary to determine it. We endow P d with the Weyl inner product and its induced norm, see §4.1. We further endow P d with the standard Gaussian measure given by the density (2π

) -N 2 exp -∥(F ,G) ∥ 2 2
(we note, however, that we could equivalently work with the uniform distribution on the unit sphere in P d ). Finally, we distinguish a subset Σ aff * of P d [q ; s] of ill-posed data (see §4.1.5 for a precise definition). Pairs (F, G) on this set are those for which the Zariski closure in R n of one of the algebraic sets defining the boundary of W (F, G) is not smooth. We will see that Σ aff * is a hypersurface in P d [q ; s] and hence has measure zero.

The complexity model we consider is the usual Blum-Shub-Smale model [START_REF] Blum | On a Theory of Computation and Complexity over the Real Numbers: NP-Completeness, Recursive Functions and Universal Machines[END_REF] extended (as often) with the ability to compute square roots. What we call "numerical algorithm" is a machine in this model. Theorem 1.1. There is a numerical algorithm Homology that, given a system (F, G) ∈ P d with q ⩽ n equalities and s inequalities, computes the homology groups of W (F, G). Moreover, the number of arithmetic operations in R performed by Homology on input (F, G), denoted cost(F, G), satisfies

(i) cost(F, G) = (s + n)Dδ -1 O(n 2 )
where δ is the distance of

1 ∥(F ,G) ∥ (F, G) to Σ aff * . Furthermore, if (F, G) is drawn from the Gaussian measure on P d , then (ii) cost(F, G) ⩽ (s + n)D O(n 3 ) with probability at least 1 -(s + n)D -n (iii) cost(F, G) ⩽ 2 O(N 2 ) with probability at least 1 -2 -N .
The algorithm is numerically stable. Nota bene. The notation O will always be understood with respect to N . For example, the bound cost(F, G)

⩽ (s + n)Dδ -1 O(n 3 )
rewords as cost(F, G) ⩽ (s + n)Dδ -1 Cn 3 for some C > 0 as soon as N is large enough, even if some of the parameters s, n or D are fixed.

Point (ii) above does not imply, strictly speaking, weak exponential time because for given n, q, s and d, the measure of the exceptional set is bounded by (s + n)D -n and this may not be exponentially small in the input size N (for instance, when n is fixed and D and s grow). But Point (iii) shows exactly what we can call weak exponential complexity: out of an exponentially small set in the space of data the cost of the latter is bounded by a single exponential function on the input size.

It is difficult to compare our algorithm with previous ones: because of its numeric nature, it only deals with the generic case, at positive distance from ill-posed problems, and its worst-case complexity is unbounded. Nevertheless, it compares favorably with the doubly exponential worstcase bound obtained from the CAD. The latter is reached on generic inputs, whereas we show a single exponential worst-case complexity outside a vanishingly small subset. Another difference with previous works is the fact that our results are valid only for polynomials with real coefficients as our proofs use some analytical techniques. This is in contrast with, for instance, the work by Basu [START_REF] Basu | Computing the First Few Betti Numbers of Semi-Algebraic Sets in Single Exponential Time[END_REF][START_REF] Basu | Computing the top Betti numbers of semialgebraic sets defined by quadratic inequalities in polynomial time[END_REF] where the results are valid for semialgebraic sets defined over arbitrary real closed fields.

In this work, we approach the topology of a set by approximating it by a union of Euclidean balls in the ambient space, as initiated in the field of topological data analysis [32, e.g.]. Following ideas in [START_REF] Chazal | A Sampling Theory for Compact Sets in Euclidean Space[END_REF][START_REF] Niyogi | Finding the Homology of Submanifolds with High Confidence from Random Samples[END_REF], for the coverings, we choose a union of balls of sufficiently small radius to which we can apply the Nerve Theorem. In constrast, previous work by Basu et al. [START_REF] Basu | Computing the First Few Betti Numbers of Semi-Algebraic Sets in Single Exponential Time[END_REF][START_REF] Basu | Computing the First Betti Number and the Connected Components of Semi-Algebraic Sets[END_REF][START_REF] Basu | Computing the first Betti number of a semi-algebraic set[END_REF], with a more algebraic flavor, approaches the topology from inside by computing covering by contractible subsets of the original set.

Lastly, we note that all the ingredients in algorithm Homology easily parallelize. Doing so, we obtain a parallel algorithm working in weak parallel polynomial complexity: out of an exponentially small set in the space of data the parallel cost of the algorithm is bounded by a polynomial function on the input size. The PSpace-hardness result by Scheiblechner [START_REF] Scheiblechner | On the complexity of deciding connectedness and computing Betti numbers of a complex algebraic variety[END_REF] mentioned above (together with the classical equivalence between space and parallel time [START_REF] Borodin | On relating time and space to size and depth[END_REF]) suggests that further complexity improvements are limited as they are unlikely to be below parallel polynomial time.

Overview. This article follows some algorithmic ideas (grid methods, theory of point estimates) introduced by Cucker and Smale [START_REF] Cucker | Complexity Estimates depending on Condition and round-off error[END_REF] and extended by Cucker et al. [START_REF] Cucker | A numerical algorithm for zero counting. I: Complexity and accuracy[END_REF][START_REF] Cucker | Computing the Homology of Real Projective Sets[END_REF]. In particular, an algorithm for computing the homology of a real algebraic subset of S n (defined with only equalities, as opposed to semialgebraic sets) has been studied in [START_REF] Cucker | Computing the Homology of Real Projective Sets[END_REF]. The spirit and the statement of our main result is very close to this previous work but the methods are substantially renewed. There is a significant overlap with [START_REF] Cucker | Computing the Homology of Real Projective Sets[END_REF] where we felt that the theory could be simplified ( §3.3 and §4.1.2), but the specificity of the semialgebraic case called for the application of different tools, such as the reach ( §2), continuous Newton method ( §3.2), or the relaxation of semialgebraic inequalities ( §4.2).

Besides, the numerical stability of the algorithm in Theorem 1.1 will not be discussed here. The precise meaning of this stability and its proof are a straightforward variation of the arguments detailed in [28, §7] which in turn are based on those in [START_REF] Cucker | A numerical algorithm for zero counting. I: Complexity and accuracy[END_REF][START_REF] Cucker | Complexity Estimates depending on Condition and round-off error[END_REF].

Our method relies on several quantities reflecting corresponding aspects of the conditioning of a semialgebraic system. The first one is the reach. This is a measure of curvature for sets without the structure of a manifold. The second one measures how much the solution set of a semialgebraic system is affected by small relaxations of the equalities and inequalities of the system. The third one is the condition number κ * which reflects the distance of a semialgebraic system to the closest ill-posed system. The facts that κ * bounds the other two measures and that we can compute it efficiently are cornerstones of our algorithm. In a number of respects, this condition number is a natural extension of the first instances of this notion, for systems of linear equations, introduced by Turing [START_REF] Turing | Rounding-off errors in matrix processes[END_REF] and von Neumann and Goldstine [START_REF] Neumann | Numerical inverting matrices of high order[END_REF].

Sections 2, 3 and 4 study all these notions. They decrease in the generality of the context (closed sets, analytic sets, and semialgebraic sets, respectively) but increase on the computational use of the results.

In a few words, to compute the homology group of an arbitrary basic semialgebraic set W , we first reduce to the case of a closed semialgebraic subset S of a sphere S n . Then we gather a finite set X of points in S n that is sufficiently dense and retain only the points that are close enough to S. A point is close enough to S if it satisfies the defining equations and inequalities of S up to some ε. Extending a theorem of Niyogi, Smale and Weinberger [START_REF] Niyogi | Finding the homology of submanifolds with high confidence from random samples[END_REF], we argue that this finite set of close enough points is sufficient to compute the homology of S. The condition number κ * acts as a master parameter: it controls the meaning of "sufficiently dense" and "close enough" and, beyond that, the total complexity of the algorithm and the required precision to run it.

Besides the main result, this work features several notable contributions. First, an extension to sets with positive reach of the Niyogi-Smale-Weinberger theorem about the computation of the homotopy type of a set via an approximation with a finite set (Theorem 2.8). Second, a continuous analogue of Shub and Smale's α-Theorem in which Newton's iteration is replaced with Newton's flow (Theorem 3.1). Third, an inequality relating the reach and the γ -number at a point of a real analytic set (Theorem 3.3). This strenghtens and simplifies a result of Cucker, Krick and Shub [START_REF] Cucker | Computing the Homology of Real Projective Sets[END_REF]. Four, a theory of the conditioning of a semialgebraic system relating the distance to the closest ill-posed problem to the sensitivity of the solution set to small relaxations of the equalities and inequalities of the system (Theorem 4. [START_REF] Canny | Computing roadmaps of general semi-algebraic sets[END_REF]. This is reminiscent of the Eckhart-Young theorem for linear systems.

APPROXIMATION OF SETS WITH POSITIVE REACH

The reach of a closed subset of a Euclidean space E is a notion introduced by Federer [START_REF] Federer | Curvature Measures[END_REF] to quantify the curvature of objects without the structure of a manifold. We establish a few useful properties of the reach and we use this notion to extend a theorem of Niyogi, Smale and Weinberger [START_REF] Niyogi | Finding the homology of submanifolds with high confidence from random samples[END_REF] that gives a criterion to compute the topology of a compact subset of an Euclidean space by means of a finite covering of balls with the same radius (Theorem 2.8). It will play a fundamental role in our arguments.

Measures of curvature

For a nonempty subset W ⊆ E and x ∈ E, we denote by d W (x) := inf p ∈W ∥x -p ∥ the distance of x to W . We note that the function

d W : E → R is 1-Lipschitz continuous, that is, |d W (x) -d W (y)| ⩽ ∥x -y∥ for all x, y ∈ E.
Definition 2.1. Let W ⊆ E be a nonempty closed subset. The medial axis of W is defined as the closure of the set

∆ W := {x ∈ E | ∃p, q ∈ W , p q and ∥x -p ∥ = ∥x -q∥ = d W (x)} .
The reach (or local feature size) of W at a point p ∈ W is defined as τ (W , p) d ∆ W (p). The (global) reach of W is defined as τ (W ) inf p ∈W τ (W , p). We also set τ (∅) := +∞.

Note that τ (W ) is also given by inf x ∈∆ W d W (x). We can also characterize τ (W ) as the supremum of all ε such that for every x ∈ E with d W (x) < ε, there exists a unique point p ∈ W with ∥x -p ∥ = d W (x). We shall denote this unique point by π W (x). This gives a map π W : T (W ) → W , where

T (W ) := x ∈ E | d W (x) < τ (W )} denotes the open neighborhood of W with radius τ (W ).
When W is a smooth submanifold of E, the reach of W can be characterized in terms of the normal bundle of W as follows. Let N ε (W )

:= {(x, v) ∈ W × E | v ⊥ T x W , ∥v ∥ < ε}
denote the open normal bundle of W with radius ε. The reach τ (W ) is the supremum of all ε such that the map

N ε (W ) → T (W ), (x, v) → x + v, is injective [48]. Proposition 2.2. If τ (W ) > 0, then π W : T (W ) → W is continuous and the map T (W ) × [0, 1] → T (W ), (x, t) -→ tπ W (x) + (1 -t)x
is a deformation retract of T (W ) onto W .

Proof. Concerning the continuity of π W , let (x k ) k ⩾0 be a sequence in T (W ) converging to some x ∈ T (W ). We have

∥π W (x k ) -x ∥ ⩽ ∥π W (x k ) -x k ∥ + ∥x k -x ∥ = d W (x k ) + ∥x k -x ∥ ⩽ d W (x) + 2∥x k -x ∥,
where we used the Lipschitz continuity of d W for the last inequality. Hence the sequence π W (x k ) is bounded. Let y ∈ W be a limit point of π W (x k ). The above inequality implies that ∥y -x ∥ ⩽ d W (x), hence y = π W (x). Thus π W (x) is the only limit point of the sequence π W (x k ) and therefore,

lim k→∞ π W (x k ) = π W (x).
The second claim is obvious. □

We will use the following well-known fact.

Lemma 2.3. Assume there is an open neighborhood U of π W (x), x ∈ E, such that W ∩ U is a smooth submanifold of E. Then π W (x) -x is normal to the tangent space of W at π W (x). □

The main result of this section is a lower bound on the reach of an intersection W ∩ V in terms of the reach of W and the reach of the intersection of W with the boundary ∂V of V . Theorem 2.4. For closed subsets V ,W of E we have τ (W ∩ V ) ⩾ min(τ (W ), τ (W ∩ ∂V )).

For the proof, we introduce an auxiliary notion. Let W ⊆ E be a closed subset and p ∈ W . Moreover, consider u ∈ E with ∥u ∥ = 1. It is easy to see that {t ⩾ 0 | d W (p + tu) = t } is an interval containing 0. We are interested in those directions u, where this interval has positive length and define the reach τ (W , p, u) of W at p along direction u as the length of this interval, that is,

τ (W , p, u) sup {t ⩾ 0 | d W (p + tu) = t } .
We note that π W (p + tu) = p for any 0 ⩽ t < τ (W , p, u). For example, we have

τ (R n + , 0, u) > 0 iff u is in the normal cone of R n + at 0, that is, u i ⩽ 0 for all i. In this case, τ (R n + , 0, u) = ∞.
The next lemma is a slight variation of a result by Federer [START_REF] Federer | Curvature Measures[END_REF]. Lemma 2.5. Let W ⊆ E be a closed subset, p ∈ W , and u ∈ E be a unit vector such that τ (W , p, u) is positive. Then we have τ (W , p) ⩽ τ (W , p, u). [START_REF] Federer | Curvature Measures[END_REF]Theorem 4.8(6)] states that under this assumption, the point

Proof. The assertion is trivial if

τ (W , p, u) = ∞. So assume that 0 < τ (W , p, u) < ∞. Federer, in
x := p + τ (W , p, u)u lies in the closure of ∆ W . Therefore τ (W , p) ⩽ ∥x -p ∥ = τ (W , p, u). □
Proof of Theorem 2.4. Let x ∈ ∆ W ∩V and p and q be distinct points in

W ∩ V such that d W ∩V (x) = ∥x -p ∥ = ∥x -q∥. It is sufficient to prove that ∥x -p ∥ ⩾ min(τ (W ), τ (W ∩ ∂V )), (3)
since the assertion then follows by taking the infimum of ∥x -p ∥ over x ∈ ∆ W ∩V .

If both p and q lie in ∂V , then x ∈ ∆ W ∩∂V and ∥x -p

∥ = d W ∩V (x) = d W ∩∂V (x) ⩾ τ (W ∩ ∂V ), which implies (3).
So we may assume that one of p and q, say p, does not lie on ∂V , that is, p is an interior point of V . Consider the unit vector u :=

x -p ∥x -p ∥ (note that x p). We first observe that τ (W ∩ V , p, u) ⩽ ∥x -p ∥, because of the presence of the point q, see Figure 1

. Moreover, τ (W ∩ V , p, u) > 0 since d W (x) = ∥x -p ∥ > 0.
From this we can we deduce that τ (W , p, u) > 0. Indeed, the sets W and W ∩V coincide on a neighborhood of p, hence the distance functions d W and d W ∩V coincide for points on the segment [p, x] that are sufficiently close to p. Using Lemma 2.5, we then obtain

τ (W ) ⩽ τ (W , p) ⩽ τ (W , p, u) ⩽ ∥x -p ∥,
which shows (3) and completes the proof. □

We can extend Theorem 2.4 to the intersections of several closed subsets.

Corollary 2.6. For closed subsets V 1 , . . . , V s and W of E we have Proof. The case s = 1 is covered by Theorem 2.4. In general, we argue by induction on s, τ

τ (W ∩ V 1 ∩ • • • ∩ V s ) ⩾ min I ⊆ {1,...,s } τ W ∩ i ∈I ∂V i . J.
(W ∩ V 1 ∩ • • • ∩ V s+1 ) ⩾ min τ (W ∩ V 1 ∩ • • • ∩ V s ), τ (W ∩ V 1 ∩ • • • ∩ V s ∩ ∂V s+1 ) ⩾ min min I ⊆ {1,...,s } τ W ∩ i ∈I ∂V i , min I ⊆ {1,...,s } τ W ∩ ∂V s+1 ∩ i ∈I ∂V i = min I ⊆ {1,...,s+1} τ W ∩ i ∈I ∂V i ,
where we have applied Theorem 2.4 and twice the induction hypothesis. □

We conclude with a relation between the reach of a subset of the unit sphere S(E) := {x ∈ E | ∥x ∥ = 1} and the reach of the cone over it. Lemma 2.7. Let V ⊆ S(E) be closed and V = R • V be the closed cone in E spanned by V . For any p ∈ V , we have τ (V , p) ⩾ min{τ ( V , p), 1}.

Proof. We may assume that E equals the span of V because the reach of a subset remains unchanged after restriction to a subspace that contains this subset. It follows from this assumption that, for all x ∈ E, π V (x) = 0 if and only if x = 0.

Elementary geometry shows that for all x ∈ E, whenever π V (x) is well-defined and not zero, then π V (x) is well-defined and

π V (x) = π V (x) ∥π V (x)∥ . Now let p ∈ V . Recall that the reach τ (V , p) is the supremum of all r > 0 such that π V is well-defined on B(p, r ).
Consider any r < min{τ ( V , p), 1} and let x ∈ B(p, r ). As r < 1 we have x 0, and as r < τ ( V , p), we have that π V (x) is well-defined and not zero (as x 0). Which, as we noted above, implies that π V (x) is well-defined. This shows that π V is well-defined on all of B(p, r ) for all r < min{τ ( V , p), 1}, from where the claim follows. □

An extension of the Niyogi-Smale-Weinberger theorem

Again, we work in a Euclidean vector space E. By the (open) neighborhood of radius r ⩾ 0 around a nonempty set S ⊆ E we understand the set

U(S, r ) p ∈ E | d S (p) < r .
Niyogi, Smale and Weinberger [START_REF] Niyogi | Finding the homology of submanifolds with high confidence from random samples[END_REF]Prop. 7.1] gave an answer to the following question: given a compact submanifold S ⊆ E, a finite set X ⊂ E and ε > 0, which conditions do we need to ensure that S is a deformation retract of U(X, ε)?

In what follows, we observe their arguments extend to any compact subsets S, X provided S has positive reach τ (S). The proof is a variation of the original proof. A much more general extension [START_REF] Chazal | A Sampling Theory for Compact Sets in Euclidean Space[END_REF] of the Niyogi-Smale-Weinberger theorem includes our, with slightly worse constants and, naturally, at the cost of a more involved proof. 1The Hausdorff distance between two nonempty closed subsets A, B ⊆ E is defined as

d H (A, B) max sup a ∈A d B (a), sup b ∈B d A (b) .
Theorem 2.8. Let S and X be nonempty compact subsets of E. The set S is a deformation retract of U(X, ε) for any ε such that

3 d H (S, X) < ε < 1 2 τ (S). Proof. For any x ∈ U(X, ε) we have d(x, S) ⩽ d(x, X) + d H (X, S) < 4 3 ε < τ (S), hence U(X, ε) ⊆ T (S). This shows that the map U(X, ε) × [0, 1] → E, (x, t) -→ (1 -t)x + tπ S (x)
is well-defined. The map is also continuous (Proposition 2.2). It remains to prove that its image is included in U(X, ε), that is, for any

v ∈ U(X, ε) the line segment [v, π S (v)] is included in U(X, ε).
The argument involves seven points depicted in Figure 2. Let v ∈ U(X, ε) and p π S (v). By definition, there is some x ∈ X such that ∥v -x ∥ < ε. If ∥p -x ∥ < ε, then the line segment [v, p] is entirely included in the ball of radius ε around x, which is a part of U(X, ε), and we are done. So we assume that ∥p -x ∥ ⩾ ε. Let u be the unique point in

[v, p] such that ∥u -x ∥ = ε. The line segment [v, u) being included in the ball B(x, ε) ⊆ U(X, ε), it only remains to check that [u, p] is also included in U(X, ε).
Let r 1 3 ε. Also, let ℓ be the open half-line starting from p and passing through v and w be the unique point in ℓ such that ∥w -p ∥ = 6r . Our assumption states that 6r = 2ε < τ (S). Also, as p = π S (v), we have τ S, p, w -p ∥w -p ∥ > 0. By Lemma 2.5, we obtain τ (S) ⩽ τ (S, p) ⩽ τ S, p, w -p ∥w -p ∥ , and therefore 6r < τ S, p, w -p ∥w -p ∥ . This implies that π S (w) = p and d S (w) = ∥w -p ∥ = 6r . Let q π S (x). We first note that ∥x -q∥ ⩽ r because d S (x) ⩽ d H (X, S) < r by our assumption. Next we have ∥w -

x ∥ ⩾ ∥w -q∥ -∥q -x ∥ ⩾ 5r, (4) because ∥w -q∥ ⩾ d S (w) = 6r .
Since d H (X, S) ⩽ r , there is a point y ∈ X such that ∥y -p ∥ ⩽ r . To conclude the proof, it is enough to prove that [u, p] ⊆ B(y, ε); since ∥y -p ∥ ⩽ r < ε, it is sufficient to check that ∥y -u ∥ < ε. By the triangle inequality,

∥y -u ∥ ⩽ ∥y -p ∥ + ∥p -u ∥ ⩽ r + ∥w -p ∥ -∥w -u ∥ = 7r -∥w -u ∥. (5)
Furthermore, the triangle (xuv) has an acute angle at u, because u is on a sphere of center x and v lies inside this sphere; the same holds true for the triangle (xuw) because u, v and w are on the same line, in this order (cf. Figure 2). It follows that ∥w -u

∥ 2 ⩾ ∥w -x ∥ 2 -∥x -u ∥ 2 > (5r ) 2 -ε 2 ,
where we used (4) for the second inequality. Therefore, with [START_REF] Basu | Computing the top Betti numbers of semialgebraic sets defined by quadratic inequalities in polynomial time[END_REF],

∥y -u ∥ < 7r - √ 25r 2 -ε 2 = 3r = ε, (6)
which concludes the proof. □

SHUB-SMALE THEORY AND EXTENSIONS

We recall the definition and basic properties of quantities (α, β and γ numbers) introduced by Shub and Smale to study the complexity of numerical methods for solving polynomial systems. We prove two results. First, an analogue of the α-Theorem for the continuous Newton method, where a continuous Newton's flow replaces the discrete sequence obtained with Newton's iteration. Second, an inequality relating the reach and the γ -number. It strengthens and simplifies a result of Cucker, Krick and Shub [START_REF] Cucker | Computing the Homology of Real Projective Sets[END_REF], for it is pointwise whereas the latter is only global.

Measures of proximity

Let E be a Euclidean space and F : E → R m be an analytic map such that m ⩽ dim E. It is wellknown that, under certain conditions, the (Moore-Penrose) Newton iteration with initial point x 0 , given by

x k +1 := x k -DF (x k ) † F (x k ) (7)
is well-defined for all k ⩾ 0 and converges quadratically fast to a zero ζ of F . In this case, we say that x 0 is an approximate zero of F with associated zero ζ (see [START_REF] Bürgisser | Condition. Grundlehren der mathematischen Wissenschaften[END_REF]Def. 15.1] for the formal definition). Here DF (x) † : R m → E is the Moore-Penrose inverse of the full-rank matrix DF (x) (we say that ( 7) is undefined if it is not of full rank).

An obvious question is whether we can, for a given x 0 , ensure the convergence of Newton's iteration. That is, whether we can check that x 0 is an approximate zero of f . An answer to this question was provided by Smale [START_REF] Smale | Newton's Method Estimates from Data at One Point[END_REF] for the zero-dimensional case (m = dim E) and extended by Shub and Smale [START_REF] Shub | Complexity of Bézout's Theorem IV: probability of success; extensions[END_REF] to the underdetermined case (m < dim E). They defined the quantities (all norms are the spectral one)

γ (F, x) sup k ⩾2 1 k ! DF (x) † D k F (x) 1 k -1 , β(F, x) DF (x) † F (x) , α(F, x) γ (F, x)β(F, x), (8)
and proved that there exists a universal constant α • , around 1 8 , such that if α(F, x 0 ) < α • then x 0 is an approximate zero of F . The quantities β and γ are not without meaning themselves. Clearly, β(F, x) is the length of the Newton step at x. Also, in the zero-dimensional case, Smale's γ -Theorem shows that, for a zero ζ of F , all points on the ball around ζ with radius 3- √ 7

2γ (F ,ζ ) are approximate zeros of F .

Continuous α-theory

While the Shub-Smale theory focuses primarily on the discrete iteration [START_REF] Basu | Computing roadmaps of semi-algebraic sets on a variety[END_REF], the numbers α and β also give quantitative information on the convergence of the continuous analogue of Newton's iteration. To the best of our knowledge, this has never been highlighted before.

We consider again a point x 0 in E such that DF (x 0 ) is surjective. We define x t with the following system of ordinary differential equations, for t in the maximal domain of solution containing 0,

x t = -DF (x t ) † F (x t ), (9)
where x t denotes d dt x t . We also denote α t α(F, x t ) and β t and γ t accordingly. It may be that γ t (and thus α t ) is not differentiable everywhere. However, γ t is at least locally Lipschitz continuous (cf. Lemma 3.2), which implies absolute continuity and, in turn, that γ t is differentiable almost everywhere and that γ t -γ 0 = ∫ t 0 γ t dt [START_REF] Natanson | Theory of Functions of a Real Variable[END_REF]IX §4]. This regularity is good enough for our purposes. In all our arguments below, at a point t where γ t is not differentiable, an inequality like γ t ⩽ 5γ 2 t β t actually means lim sup

ε →0 γ t +ε -γ t ε ⩽ 5γ 2 t β t .
The domain of definition Ω of the differential equation is the open set of all x ∈ E such that DF (x) is surjective. Theorem 3.1. If α 0 < 1 13 , then x t is defined for all t ⩾ 0 and (i)

F (x t ) = F (x 0 )e -t ; (ii) ∥x t -x 0 ∥ ⩽ 2β 0 (1 -e -t ); (iii) x t converges when t → ∞.
Lemma 3.2. For all t ⩾ 0 where x t is defined, we have (i)

∥ x t ∥ = β t , (ii) γ t ⩽ 5γ 2 t β t , (iii) t → γ t is locally Lipschitz, (iv) β t ⩽ -β t + 3γ t β 2 t , and (v) α t ⩽ -α t + 8α 2 t .
Proof. (i) It follows from [START_REF] Basu | Computing the Dimension of a Semi-Algebraic Set[END_REF].

Computing the Homology of Basic Semialgebraic Sets 5:11

(ii) Let y = x t +ε for some small positive ε.

Let u = ∥x -y∥γ t = γ t ∥ x t ∥ε + O(ε 2 ). By [30, Lemme 131], γ (F, y) -γ (F, x t ) ⩽ 1 (1 -u)(1 -4u + 2u 2 ) -1 γ (F, x t ) = 5uγ t + O(ε 2 ), so that γ t +ε -γ t ⩽ 5γ 2 t ∥ x t ∥ε + O(ε 2
). With the equality ∥ x t ∥ = β t , this gives the claim when taking the limit for ε → 0.

(iii) This follows from (ii).

(iv

)
d dt A † = -A † AA † + P(A † A) T A † .
This formula derives from the equality A † = A T (AA T ) -1 which holds because A is surjective.

Using that DF (x)DF (x) † = id E and given the differential equation ( 9) for x t , we check that, for any t ∈ I ,

d dt F (x t ) = DF (x t )( x t ) = -DF (x t )DF (x t ) † F (x t ) = -F (x t ).
(10) Using this equality we deduce that

B = A † d dt F (x) + d dt A † F (x) = -A † F (x) + -A † AA † + P(A † A) T A † F (x) = -B + -DF (x) † D 2 F (x)( x) + P(DF (x) † D 2 F (x)( x)) T B.
Let C denote the operator inside the square brackets. Since the two terms in C have orthogonal images, we easily obtain

∥C ∥ ⩽ √ 2 ∥DF (x) † D 2 F (x)( x)∥ ⩽ 2 √ 2γ ∥ x ∥ < 3γ β . Since β t = 1 β t ⟨ B t , B t ⟩, we obtain item (iv). (v) From the previous inequalities, α t = γ t β t + γ t β t ⩽ 8γ 2 t β 2 t -γ t β t , which is exactly the claim. □
Proof of Theorem 3.1. Let I = [0, τ ) be the maximum domain of solution of the differential equation ( 9) with the fixed initial condition x 0 . We will shortly see that τ = ∞.

By Equation [START_REF] Basu | Computing the first Betti number of a semi-algebraic set[END_REF] we have that, for any t ∈ I , d dt F (x t ) = -F (x t ). This gives the first claim. After some calculation, using Lemma 3.2(v), we check that d dt e -t α t ⩾ -8e -t . It follows that for t ∈ I ,

α t ⩽ α 0 e -t 1 -8α 0 . ( 11
)
After some calculation, using Lemma 3.2(iv), we obtain that d dt log β t ⩽ -1 + 3α t , and therefore, for t ∈ I ,

β t ⩽ β 0 exp 3α 0 1-8α 0 -t ⩽ 2β 0 e -t , (12)
where we used that α 0 ⩽ 1 13 for the second inequality. Using Lemma 3.2(i), we compute that -d dt 1 γ t ⩽ 5β t , and it follows with (11) that for t ∈ I ,

γ t ⩽ γ 0 1 -10β 0 γ 0 ⩽ 13 3 γ 0 . (13)
By Inequality [START_REF] Björner | Topological methods[END_REF] and Lemma 3.2(i), ∥ x t ∥ = β t is bounded for t ∈ I . Therefore, if the interval I = [0, τ ) is bounded, then x t approaches, as t → τ , a point y in the complement of Ω, the domain of definition of the differential equation [15, IV.5, Th. 2]. Therefore, γ 0 ∥y -x ∥ ⩽ 2β 0 γ 0 = 2α 0 < 1-1 2 √ 2, and [30, Lemme 123] implies that DF (y) is surjective, which contradicts y Ω. We have thus shown that τ = ∞.

Next, with Lemma 3.2(i), it follows that, for t ∈ I ,

∥x t -x 0 ∥ ⩽ ∫ t 0 ∥ x s ∥ds ⩽ 2β 0 (1 -e -t ).
which is the second claim. Similarly, Equation [START_REF] Björner | Topological methods[END_REF] shows that the integral ∫ ∞ 0 x s ds is absolutely convergent, therefore x t has a limit when t → ∞. □

An inequality relating the reach and the γ -number

We keep assuming that E is a Euclidean space and F : E → R m an analytic map, with m ⩽ dim E.

We will prove the following local inequality, which is a refinement of a result first proved by Cucker, Krick and Shub [START_REF] Cucker | Computing the Homology of Real Projective Sets[END_REF]. The proof is also much simpler. Proof of Theorem 3.3. We fix p ∈ M such that γ (p) < ∞. Since τ (p) = inf u ∈∆ M ∥u -p ∥, it is enough to prove that γ (p)∥u -p ∥ ⩾ 1 14 for any given u ∈ ∆ M . To shorten notation, we write γ (p) for γ (F, p).

Let u ∈ ∆ M . By definition, there exist distinct points x and y in M such that d M (u) = ∥u -x ∥ = ∥u -y∥. Using the triangle inequality (three times) we see that max(∥x -y∥, ∥p -x ∥, ∥p -y∥) ⩽ 2∥u -p ∥.

Therefore, denoting

η := γ (p) max(∥x -y∥, ∥p -x ∥, ∥p -y∥),

we obtain γ (p)∥u -p ∥ ⩾ 1 2 η. If η ⩾ 1 7
, then we are done, so we can assume that η < 1 7 .

Computing the Homology of Basic Semialgebraic Sets

5:13

Let B ⊆ E be the ball of center p and radius η/γ (p) (in particular x, y ∈ B). Since η ⩽ 1 7 , γ is bounded on B by Kγ (p), where K [START_REF] Dedieu | Points Fixes, Zéros et La Méthode de Newton[END_REF]Lemme 131]. In particular, γ (x) and γ (y) are finite, so that x and y are regular points of M.

1 (1-η)(1-4η+2η 2 )
We now give a lower and an upper bound for ∥π x (u -y)∥. Let y ′ = x + π x (y -x). By Lemma 2.3, the vector ux is normal to M at x, that is π x (u -x) = 0; thus π x (u -y) = xy ′ , and then we have the lower bound ∥x -y∥ -∥y -y ′ ∥ ⩽ ∥π x (u -y)∥.

Similarly, the vector uy is normal to M at y, that is π y (u -y) = 0; hence the upper bound

∥π x (u -y)∥ = ∥π x (u -y) -π y (u -y)∥ ⩽ ∥π x -π y ∥ • ∥u -y∥.
Combined with [START_REF] Borodin | On relating time and space to size and depth[END_REF], we obtain

∥x -y∥ -∥y -y ′ ∥ ⩽ ∥π x -π y ∥ ∥u -y∥. (15)
Further, we aim at bounding ∥y -y ′ ∥. By definition of y ′ , using that F (x) = F (y) = 0, and expanding F (y) into a power series at x, we can write

y -y ′ = DF (x) † DF (x)(y -x) -DF (x) † F (y) = DF (x) † DF (x)(y -x) -DF (x) † k ⩾0 1 k ! D k F (x)(y -x, . . . , y -x) = - k ⩾2 1 k ! DF (x) † D k F (x)(y -x, . . . , y -x). Hence ∥y -y ′ ∥ ⩽ k ⩾2 1 k ! DF (x) † D k F (x) ∥y -x ∥ k ⩽ ∥y -x ∥ k⩾2 γ (x)∥y -x ∥ k -1 = γ (x)∥x -y∥ 2 1 -γ (x)∥x -y∥ ⩽ Kη 1 -Kη ∥x -y∥, (16)
the last inequality following from γ (x)∥x -y∥ ⩽ Kγ (p)∥x -y∥ ⩽ Kη and the monotonicity of the function t → t/(1 -t).

Lastly, we bound ∥π x -π y ∥. By Proposition 3.4, we can upper bound

∥π x -π y ∥ ⩽ sup z ∈[x ,y] ∥Dπ (z)∥ • ∥x -y∥ ⩽ sup z ∈[x ,y] 2γ (z) • ∥x -y∥ ⩽ 2Kγ (p)∥x -y∥. (17)
Combining ( 15), ( 16) and ( 17), we obtain

1 - ηK 1 -ηK ∥x -y∥ ⩽ 2Kγ (p)∥x -y ∥ ∥u -y∥.
Dividing by the nonzero ∥x -y∥ and noting ∥u -y∥ ⩽ ∥u -p ∥, this implies

1 14 ⩽ 1 2K 1 - ηK 1 -ηK ⩽ γ (p)∥u -p ∥,
where the left-hand inequality is easily checked numerically. □

CONDITION NUMBER OF SEMIALGEBRAIC SYSTEMS

We focus now on semialgebraic sets, and more specifically, on spherical semialgebraic sets S(F, G) given by homogeneous semialgebraic systems (F, G); cf. [START_REF] Canny | Finding connected components of a semialgebraic set in subexponential time[END_REF]. We do so since, eventually (see §5.3 below), we will reduce the computation of the homology of semialgebraic sets and its complexity analysis to the same tasks for the spherical case. We define a condition number κ * for homogeneous semialgebraic systems and relate it to three different measures of conditioning: the distance to the closest ill-posed system in the space of semialgebraic systems (Theorem 4.10); the reach of the set S(F, G) (Theorem 4.12); and the sensitivity of S(F, G) to small relaxations of the equalities and inequalities of the system (F, G) (Theorem 4.19). We also bound the degree of the hypersurface of ill-posed systems (Proposition 4.20). We finally give a notion of condition number for affine semialgebraic systems that is based on the one for the homogeneous case.

Measures of condition

4.1.1 The µ numbers. To a degree pattern d = (d 1 , . . . , d q ) we associate the linear space

H d [q] of the polynomial systems F = (f 1 , . . . , f q ) where f i ∈ R[X 0 , X 1 , . . . , X n ] is homogeneous of degree d i . Let D = max 1⩽i⩽q d i . We endow H d [q]
with a Euclidean inner product, the Weyl inner product, defined as follows. For homogeneous polynomials h = |a |=d h a X a and h ′ = |a |=d h ′ a X a in R[X 0 , . . . , X n ], where we write a = (a 0 , . . . , a n ) ∈ N n+1 and |a| a 0

+ • • • + a n , we define ⟨h, h ′ ⟩ |a |=d d a -1 h a h ′ a ,
where d a d ! a 0 !a 1 !...a n ! is the multinomial coefficient. For any q-tuples of homogeneous polynomials F, F ′ ∈ H d [q] with degree pattern d, say F = (f 1 , . . . , f q ) and F ′ = (f ′ 1 , . . . , f ′ q ), we define

⟨F, F ′ ⟩ q j=1 ⟨f j , f ′ j ⟩.
In other words, the Weyl inner product is a dot product with respect to a specifically weighted monomial basis. Its raison d'être is the fact that it is invariant under orthogonal transformations of the homogeneous variables (X 0 , . . . , X n ). That is, that for any orthogonal transformation u : R n+1 → R n+1 and any F ∈ H d [q], we have ∥F ∥ = ∥F • u ∥. In all of what follows, all occurrences of norms in spaces H d [q] refer to the norm induced by the Weyl inner product. For a point x ∈ R n+1 and a system F ∈ H d [q], let DF (x) denote the derivative of F at x, which is a linear map R n+1 → R q . We also define the diagonal normalization matrix

∆ √ d 1 . . . d q .
The condition number µ norm (F, x) of F ∈ H d [q] at x ∈ S n has been well studied [START_REF] Shub | Complexity of Bézout's Theorem I: geometric aspects[END_REF][START_REF] Shub | Complexity of Bézout's Theorem II: volumes and probabilities[END_REF][START_REF] Shub | Complexity of Bézout's Theorem III: condition number and packing[END_REF][START_REF] Shub | Complexity of Bézout's Theorem V: polynomial time[END_REF][START_REF] Shub | Complexity of Bézout's Theorem IV: probability of success; extensions[END_REF], see also [START_REF] Bürgisser | Condition. Grundlehren der mathematischen Wissenschaften[END_REF]. We define it as ∞ when the derivative DF (x) of F at x is not surjective, and otherwise as

µ norm (F, x) ∥F ∥ DF (x) † ∆ , (18)
where the norm ∥DF (x) † ∆∥ is the spectral norm. We also define the following variant of µ norm , more specific to homogeneous systems,

µ proj (F, x) µ norm (F | T x , x) = ∥F ∥ DF (x)| † T x ∆ ,
where T x = {x } ⊥ and T x x + T x . (The number µ norm (F | T x , x) is well-defined after identifying T x with R n .)

The following inequality is a useful result from the Shub-Smale theory [58, Lemma 2.1(b)].

Proposition 4.1. Let F ∈ H d [q] and x ∈ R n+1 be a zero of F . Then

γ (F, x) ⩽ 1 2 D 3 2 µ norm (F, x). □ 4.1.2
The κ number. The numbers µ norm (F, x) and µ proj (F, x) measure the sensitivity of the zero x of F when F is slightly perturbed. They are consequently useful at a zero, or near a zero, of the system F . To deal with points in S n far away from the zeros of F , in particular to understand how much F needs to be perturbed to make such a point a zero, a more global notion of conditioning is needed. The following is (modulo replacing µ norm by µ proj ) the condition measure introduced in [START_REF] Cucker | Approximate zeros and condition numbers[END_REF] (see also [18, §19] and [START_REF] Cucker | A numerical algorithm for zero counting. I: Complexity and accuracy[END_REF][START_REF] Cucker | A numerical algorithm for zero counting. II: Distance to ill-posedness and smoothed analysis[END_REF]).

Definition 4.2. The real homogeneous condition number of

F ∈ H d [q] at x ∈ S n is κ(F, x) 1 µ proj (F, x) 2 + ∥F (x)∥ 2 ∥F ∥ 2 -1/2
, where we use the conventions ∞ -1 := 0, 0 -1 := ∞, and κ(0, x) := ∞. We further define κ(F ) max x ∈S n κ(F, x).

If q > n (that is, if the system F is overdetermined) then DF (x)| T x cannot be surjective and κ(F, x) = ∥F ∥ ∥F (x ) ∥ for all x ∈ S n . Thus, κ(F ) < ∞ if and only if F has no zeros in S n . The special case F (x) = 0 is worth highlighting. Lemma 4.3. For any F ∈ H d [q] and x ∈ S n , if F (x) = 0, then κ(F, x) = µ proj (F, x) = µ norm (F, x).

Proof. The first equality follows from the definition of κ. For the second, recall that the pseudoinverse DF (x) † is the inverse of DF (x) restricted as a map (ker DF (x)) ⊥ → R q . If F (x) = 0, then DF (x)(x) = 0, by homogeneity, therefore the orthogonal complement of the kernel of DF (x) is included in T x . It follows that DF (x)| † T x = DF (x) † and then µ proj (F, x) = µ norm (F, x). □ For x ∈ S n , let Σ x be the set of all F ∈ H d [q] such that κ(F, x) = ∞, that is F (x) = 0 and DF (x)| T x is not surjective. The set of ill-posed algebraic systems is defined as Σ

x ∈S n Σ x . It is the set of all F ∈ H d [q] such that κ(F ) = ∞. We have Σ = F ∈ H d [q] | ∃x ∈ S n F (x) = 0 and DF (x)| T x is not surjective . ( 19
)
The set Σ is semialgebraic and invariant under scaling of each of the q components. Note that in the case q > n, the set Σ x just consists of the F ∈ H d [q] such F (x) = 0, and Σ equals the set of F ∈ H d [q] that possess a real zero in S n .

Theorem 4.4. For any nonzero F ∈ H d [q] and any x ∈ S n ,

κ(F, x) = ∥F ∥ d(F, Σ x ) and κ(F ) = ∥F ∥ d(F, Σ)
,

where the distance d(F, •) is defined via the norm induced by the Weyl inner product.

Proof. The assertion is obvious in the case q > n. We therefore assume q ⩽ n. The special case q = n is Prop. 19.6 in [START_REF] Bürgisser | Condition. Grundlehren der mathematischen Wissenschaften[END_REF]. One can check that the same proof works in the case q ⩽ n. □ Corollary 4.5. For any F ∈ H d [q] and any x ∈ S n , κ(F, x) ⩾ 1.

Proof. Since 0 ∈ Σ x , this follows directly from Theorem 4.4. □ Remark 4.6. Proposition 6.1 in [START_REF] Cucker | Computing the Homology of Real Projective Sets[END_REF] shows that for the condition number κ norm (F, x) defined as in Definition 4.2 above, but with µ proj replaced by µ norm , we have

∥F ∥ √ 2 d(F, Σ x ) ⩽ κ norm (F, x) ⩽ ∥F ∥ d(F, Σ x )
.

This shows that there is no essential difference between κ and κ norm : they are the same up to a factor of at most √ 2. It also shows that, for all x ∈ S n , µ norm (F, x) ⩽ µ proj (F, x). So the bound in Proposition 4.1 holds with µ proj (F, x) as well.

However, a bound on µ proj in terms of µ norm is not possible. Indeed, take f 1 (x, y, z) := x + y and f 2 (x, y, z) := y 2 + z 2 + xy. Further, take e 0 := (1, 0, 0). Then DF (e 0 ) =

1 1 0 0 1 0 , DF (e 0 ) |e ⊥ 0 = 1 0 1 0 ,
where the left-hand matrix is of full rank, but the right-hand matrix is rank deficient. Hence µ norm (F, e 0 ) < ∞, but µ proj (F, e 0 ) = ∞. We introduced µ proj in our development because it allows for sharper statements and easier proofs.

Proposition 4.7. For F ∈ H d [q], the map S n → R, x → κ(F, x) -1 is D-Lipschitz continuous with respect to the Riemannian metric on S n .

Proof. Let x, y ∈ S n . Let u ∈ O(n + 1) be the rotation that maps x to y and that is the identity on {x, y} ⊥ . By the invariance of Weyl's inner product under the action of O(n + 1),

d(F, Σ y ) = d(F • u, Σ x ).
Since the function д → d(д, Σ x ) is 1-Lipschitz, we obtain with Theorem 4.4 that

∥F ∥ 1 κ(F, x) - 1 κ(F, y) = |d(F, Σ x ) -d(F, Σ y )| = |d(F, Σ x ) -d(F • u, Σ x )| ⩽ ∥F -F • u ∥.
We conclude the proof with the next lemma. □ Lemma 4.8. For any F ∈ H d [q] and any x, y ∈ S n , ∥F -

F • u ∥ ⩽ D ∥F ∥d S (x, y),
where u ∈ O(n + 1) is the unique rotation that maps x to y and leaves invariant {x, y} ⊥ .

Proof. We first notice that

∥F -F • u ∥ 2 = i ∥ f i -f i • u ∥ 2
so it is enough to prove the claim when q = 1. We prove a corresponding, more general statement over C and, to this end, we consider the space of complex homogeneous coefficients of degree d endowed with Weyl's Hermitian inner product. The latter is invariant under the action of the unitary group U (n + 1), therefore, without loss of generality, we may assume that the matrix of u is the diagonal matrix diag(e iθ , e -iθ , 1, . . . ), where θ = d S (x, y). We write f = |a |=d c a X a and then

f -f • u = |a |=d 1 -e i(a 0 -a 1 )θ c a X a . Since 1 -e i(a 0 -a 1 )θ ⩽ |(a 0 -a 1 )θ | ⩽ D θ,
we obtain the claim. □ 4.1.3 Condition number of homogeneous semialgebraic systems. We consider (closed) homogeneous semialgebraic systems, i.e., systems of the form f 1 (x) = 0, . . . , f q (x) = 0 and д 1 (x) ⩾ 0, . . . , д s (x) ⩾ 0, [START_REF] Canny | Finding connected components of a semialgebraic set in subexponential time[END_REF] where the f i and the д j are homogeneous polynomials in R[X 0 , X 1 , . . . , X n ]. The system is an element (F, G) ∈ H d [q ; s]. The set of solutions x ∈ S n of system [START_REF] Canny | Finding connected components of a semialgebraic set in subexponential time[END_REF], which we will denote by S(F, G), is a spherical basic semialgebraic set. Needless to say, we do allow for the possibility of having q = 0 or s = 0. This corresponds with systems having only inequalities (resp. only equalities).

To a homogeneous semialgebraic system (F, G) we associate a condition number κ * (F, G) as follows. For a subtuple L = (д j 1 , . . . , д j ℓ ) of G, let F L denote the system obtained from F by appending the polynomials from L, that is,

F L f 1 , . . . , f q , д j 1 , . . . , д j ℓ ∈ H d [q + ℓ]
(where now d denotes the appropriate degree pattern in N q+ℓ ). Abusing notation, we will frequently use set notations L ⊆ G or д ∈ G to denote subtuples or coefficients of G.

Definition 4.9.

Let q ⩽ n + 1, (F, G) ∈ H d [q ; s].
The condition number of the homogeneous semialgebraic system (F, G) is defined as

κ * (F, G) max L ⊆G q+ |L |⩽n+1 κ F L .
We define Σ * as the set of all (F, G)

∈ H d [q ; s] such that κ * (F, G) = ∞.
Clearly, Σ * is semialgebraic and invariant under scaling of the q + s components. Theorem 4.10. For any nonzero ψ

= (F, G) ∈ H d [q ; s], κ * (ψ ) ⩽ ∥ψ ∥ d(ψ , Σ * ) .
Proof. For a subset L of the indices {1, . . . , s}, let p L :

H d [q ; s] → H d [q + |L|] be the projec- tion (F, G) → F L . Clearly Σ * = ∪ L p -1 L (Σ L )
, where Σ L is the set of ill-posed data in the appropriate space

H d [q + |L|]. In particular d(ψ , Σ * ) ⩽ d(p L (ψ ), Σ L ). Then, by Theorem 4.4, κ * (F, G) = max L ⊆G q+ |L |⩽n+1 ∥F L ∥ d(F L , Σ L ) ⩽ ∥ψ ∥ d(ψ , Σ * )
. □ Note that we do not define condition for the very overdetermined case q > n + 1, but it is important to include the overdetermined case q + |L| = n + 1 in the definition of κ * (F, G). To see why, consider the case of three polynomials f , д 1 , д 2 around a point x ∈ S 2 as in Figure 3.

This system is ill-posed as arbitrarily small perturbations of (f , G) may result in an empty intersection around x, and hence, a different topology of S(f , G). But none of the condition numbers κ(f , д 1 ) and κ(f , д 2 ) capture this fact as x is a well-posed zero for both systems. The following lemma is related to this matter. Lemma 4.11. Let (F, G) be a homogeneous semialgebraic system with κ * (F, G) < ∞. For any L ⊆ G such that |L| ⩾ n + 1 -q, the set S(F L , ∅) is empty. 3 The shaded area is where д 1 ⩾ 0 and д 2 ⩾ 0. Locally, the only solution point is the intersection

f = 0 д 1 = 0 д 2 = 0 x Fig.
{x } of f = д 1 = д 2 = 0.
Proof. We choose

L ′ ⊆ L such that |L ′ | = n+1-q. Because of the dimensions involved, DF L ′ (x)| T x cannot be surjective, thus κ(F L ′ , x) = ∥F L ′ ∥/∥F L ′ (x)∥ for any x ∈ S n . Moreover κ(F L ′ ) ⩽ κ * (F, G) < ∞, by definition of κ * . Therefore F L ′
has no zero on S. In particular S(F L , ∅), the zero set of F L , is empty.

□

We elaborate on Theorem 3.3, relating γ and τ , to obtain the following result that relates κ * and τ . It gives a computational handle on τ which is otherwise hard to get. Theorem 4.12. For any homogeneous semialgebraic system (F, G) defining a semialgebraic set S S(F, G)

⊆ S n , if κ * (F, G) < ∞, then D 3 2 τ (S) κ * (F, G) ⩾ 1 7 .
Proof. We first study the case where G = ∅. Let S ⊆ R n+1 be the cone over S, that is, the zero set of F in R n+1 . For any x ∈ S, τ (S, x) ⩾ min(1, τ ( S, x)), by Lemma 2.7. Therefore,

τ (S) = min x ∈S τ (S, x) ⩾ min 1, min x ∈S τ ( S, x) .
Using also that κ(F, x) ⩾ 1 (Corollary 4.5), we obtain that

τ (S)κ(F ) ⩾ min 1, min x ∈S τ ( S, x)κ(F, x) . (21)
Recall from Lemma 4.3 that κ(F, x) = µ proj (F, x) = µ norm (F, x) for all x ∈ S. Combining this with Proposition 4.1, we obtain that D 3 2 κ(F, x) ⩾ 2γ (F, x) for all x ∈ S. We conclude that

D 3 2 min x ∈S τ ( S, x)κ(F, x) ⩾ min x ∈S 2τ ( S, x)γ (F, x) ⩾ 1 7 ,
where we have applied Theorem 3.3 to S for the right-hand side inequality. Combining this with (21), we obtain D 3 2 τ (S)κ(f ) ⩾ 1 7 . We turn now to the general case S S(F, G) ⊆ S n . For д ∈ G we define P д {x ∈ S n | д(x) ⩾ 0} and W S(F, ∅) so that S = W ∩ ∩ д ∈G P д . We claim that for any L ⊆ G,

W ∩ д ∈L ∂P д = S(F L , ∅). (22)
Computing the Homology of Basic Semialgebraic Sets

5:19

The left-to-right inclusion is clear since ∂P д is contained in the zero set of д. Conversely, let x ∈ S(F L , ∅) (in particular, q + |L| ⩽ n, by Lemma 4.11). The derivative DF L (x) is surjective, because κ(F L , x) < ∞. In particular, for any д ∈ L, Dд(x) 0 and since д(x) = 0 it follows that the sign of д changes around x. Thus x ∈ ∂P д and Equation ( 22) follows. Theorem 2.6 implies that

τ (S) ⩾ min L ⊆G τ W ∩ д ∈L ∂P д = min L ⊆G τ S F L , ∅ . (23)
It suffices to take the minimum over the L ⊆ G such that q + |L| ⩽ n + 1 because S(F L , ∅) = ∅ for larger L. We obtain from the case G = ∅ above,

7 D 3 2 τ (S) ⩾ min L 7 D 3 2 τ (S(F L , ∅)) ⩾ 1 max L κ(F L ) = 1 κ * (F, G) ,
which completes the proof. □ 4.1.4 Strict inequalities. We prove here that replacing inequalities д i (x) ⩾ 0 by strict inequalities д i (x) > 0 in the definition (20) of a spherical basic set S(F, G) does not change its homotopy type, provided κ * (F, G) < ∞.

The argument is based on a general reasoning in topology. Recall that a closed subset B of a topological space X is called collared in X if there exists a homeomorphism h :

[0, 1) × B → V onto an open neighborhood V of B in X such that h(0, b) = b for all b ∈ B. Lemma 4.13. If B ⊆ X is collared in X and X \ B ⊆ X ′ ⊆ X , then X ′ and X are homotopically equivalent.
Proof. Let τ : V → [0, 1] and u : V → B denote the components of the inverse of h, so that h(τ (x), u(x)) = x for any x ∈ V . We define the map ϕ : [0, 1] × X → X by

ϕ t (x) := h(t, u(x)) if x ∈ V and τ (x) < t, x otherwise.
The idea is that ϕ t pushes X increasingly far away from B as t increases. It is easy to verify that ϕ is continuous, ϕ 0 = id X , ϕ t (x) = x for x ∈ X \ V , and ϕ 1 (X ) = X \ V . In other words, ϕ t : X → X defines a deformation retraction of X to X \ V . Moreover, we have ϕ t (X ′ ) ⊆ X ′ , since ϕ t (X ′ ) ⊆ X \ B ⊆ X ′ for t > 0. In addition, X \ V ⊆ ϕ t (X ′ ) ⊆ X \ V . Therefore, the restrictions of ϕ t define a deformation retraction of X ′ to X \ V . We conclude that X ′ and X are homotopically equivalent. □

We apply this now to basic semialgebraic sets.

Proposition 4.14. Let (F, G) ∈ H d [q ; s] be such that κ * (F, G) < ∞. Put S := S(F, G), let r ⩽ s, and let S ′ ⊆ S be the solution set in S n of the semialgebraic system

f 1 = • • • = f q = 0, д 1 ⩾ 0, . . . , д r ⩾ 0 and д r +1 > 0, . . . , д s > 0.
Moreover, let ∂S denote the boundary of S in S(F, ∅). Then S \ ∂S ⊆ S ′ , ∂S is collared in S, and S ′ is homotopically equivalent to S.

Proof. Let x ∈ S and L ⊆ G be maximal such that F L (x) = 0. Note, this implies |L| ⩽ nq. Since µ proj (F L , x) = κ(F L , x) < ∞, the derivatives at x of the components of F L are linearly independent. Therefore, the components of F L are part of some regular system of parameters (f 1 , . . . , f q , v 1 , . . . , v n-q ) of S n at x such that S is defined locally around x by

f 1 = • • • = f q = 0 and v 1 ⩾ 0, . . . , v |L | ⩾ 0,
and ∂S is defined locally around x by additional requiring v j (x) = 0 for some j ⩽ |L|. Therefore, if

x ∂S, we must have v i (x) > 0 for all i, and hence д j (x) > 0 for all j. This shows the first assertion S \ ∂S ⊆ S ′ . This reasoning also proves that locally around x, the set S is diffeomorphic to some (-1, 1) a ×[0, 1) b with a, b ∈ N. Therefore, ∂S is locally collared in S. By Brown's Collaring Theorem [START_REF] Brown | Locally Flat Imbeddings of Topological Manifolds[END_REF][START_REF] Connelly | A New Proof of Brown's Collaring Theorem[END_REF], ∂S is collared in S, which proves the second assertion. The third assertion follows by applying Lemma 4.13 to X = S, B = ∂S and X ′ = S ′ . □ 4.1.5 Condition number of affine semialgebraic systems. We now consider basic semialgebraic subsets of R n , rather than S n . Given a degree pattern d = (d 1 , . . . , d q+s ), the homogeneization of polynomials (with respect to that pattern) yields an isomorphism of linear spaces

P d [q ; s] → H d [q ; s], ψ = (F, G) → ψ h = (F h , G h ),
where F h denotes the homogeneization of F with homogeneizing variable X 0 . The Weyl inner product on H d [q ; s] induces an inner product on P d [q ; s] such that the above map is isometric.

H : P d [q ; s] → H (d ,1) [q ; s + 1], ψ → (ψ h , ∥ψ h ∥X 0 ), (24)
that is, the system H (F, G) is the homogeneization of (F, G) to which we add the inequality X 0 ⩾ 0 with a suitable coefficient. For ψ ∈ P d [q ; s], we define κ aff * (ψ ) κ * (H (ψ )) and call Σ aff * H -1 (Σ * ) the set of ill-posed affine semialgebraic systems.

By construction, ∥H (ψ )∥ 2 = 2∥ψ ∥ 2 . We note that Σ aff * is a semialgebraic set in P d [q ; s] that is invariant under scaling of each of the q + s components. .

Proof. Fix ψ ∈ P d [q ; s] and put r := ∥ψ ∥ > 0. Further, assume Φ ∈ H d ,1 [q ; s + 1] is an element of Σ * that minimizes the distance to H (ψ ). Theorem 4.10 implies that

κ aff * (ψ ) = κ * (H (ψ )) ⩽ ∥H (ψ )∥ ∥H (ψ ) -Φ∥ . ( 25
)
We write Φ = (Φ 1 , λ), where Φ 1 ∈ H d [q ; s] and λ ∈ H 1 [START_REF] Amelunxen | Average-case complexity without the black swans[END_REF]. We may assume that λ 0: otherwise, we can replace Φ with Φ ′ (0, rX 0 ), which is an element of Σ * that is at least as close to

H (ψ ) = (ψ h , rX 0 ) as Φ, since ∥H (ψ ) -Φ ′ ∥ = r ⩽ ∥H (ψ ) -Φ∥.
Since Σ * is invariant under the scaling of each component, the minimality of Φ implies that λ and rX 0 -λ are orthogonal, that the angle α between λ and X 0 satisfies α ⩽ π /2, and, as a consequence, that

α ⩽ π 2 sin α ⩽ π 2 ∥r X 0 -λ ∥ r . ( 26
)
Let u ∈ O(n + 1) be the rotation that leaves {X 0 , λ} ⊥ invariant and such that λ

• u = ∥λ∥X 0 . Then Φ • u = (Φ 1 • u, λ • u) ∈ Σ * since Σ * is invariant under the action of O(n + 1). If we write Φ 1 • u = φ h with φ ∈ P d [q ; s], then H (φ) = (φ h , ∥φ h ∥X 0 ) lies in Σ * ,
since Σ * is invariant under the scaling of its last component and λ 0. We therefore obtain,

d(ψ , Σ aff * ) ⩽ ∥ψ -φ ∥ = ∥ψ h -φ h ∥ ⩽ ∥ψ h -ψ h • u ∥ + ∥ψ h • u -Φ 1 • u ∥ = ∥ψ h -ψ h • u ∥ + ∥ψ h -Φ 1 ∥.
Computing the Homology of Basic Semialgebraic Sets

5:21

By Lemma 4.8 and Inequality [START_REF] Cucker | A numerical algorithm for zero counting. I: Complexity and accuracy[END_REF], we obtain that

∥ψ h -ψ h • u ∥ ⩽ αDr ⩽ π 2 D ∥rX 0 -λ∥.
Since ∥rX 0 -λ∥ and ∥ψ h -Φ 1 ∥ are both bounded by ∥H (ψ ) -Φ∥, we get

d(ψ , Σ aff * ) ⩽ π 2 D + 1 ∥H (ψ ) -Φ∥ = π 2 D + 1 √ 2 ∥ψ ∥ ∥H (ψ ) -Φ∥ ∥H (ψ )∥ .
We conclude with Inequality [START_REF] Cucker | Approximate zeros and condition numbers[END_REF]. □

Neighbourhoods of spherical basic semialgebraic sets

The goal of this section is to compare two natural ways of defining neighborhoods of a spherical semialgebraic set S(F, G): by relaxing the arguments of the polynomials in F and G (the common, tube-like neighborhood), or by relaxing their values. For a subset A ⊆ S n we denote by

U S (A, r ) {x ∈ S | d S (x, A) < r }
the open r -neighborhood of A with respect to the geodesic distance d S on the sphere S n . Also, for a homogeneous system (F, G) ∈ H d [q ; s] and r > 0, we define the r -relaxation of S(F, G):

Approx(F, G, r ) {x ∈ S n | ∀f ∈ F | f (x)| < ∥ f ∥r and ∀д ∈ G д(x) > -∥д∥r } .
It is clear that S(F, G) ⊆ Approx(F, G, r ) for any r > 0. It is easy to see that Approx(F, G, r ) converges to S with respect to the Hausdorff distance, when r → 0. The next two results quantify more precisely this behaviour in terms of the condition number κ * (F, G). Recall, D denotes the maximum degree of the components of F and G.

Proposition 4.17. For any r > 0,

U S S(F, G), D -1 2 r ⊆ Approx(F, G, r ).
Proof. For any homogeneous polynomial h of degree d and any x, y ∈ S n ,

|h(x) -h(y)| ⩽ √ d ∥h∥ d S (x, y).
(This is shown in [START_REF] Bürgisser | Condition. Grundlehren der mathematischen Wissenschaften[END_REF]Lemma 19.22]. The additional hypothesis d S (x, y) < 1/ √ 2 there can be easily removed by splitting the path from x to y in smaller segments.) Hence, for any x ∈ S and y ∈ S n such that d S (x, y)

< 1 √ D r , any f ∈ F and д ∈ G, we have | f (y)| ⩽ r ∥ f ∥ and д(y) > д(x) -r ∥д∥ ⩾ -r ∥д∥. □ Lemma 4.18. Let H ⊆ L ⊆ G be such that |H | = n -q + 1, and 0 < r < 1 κ(F H ) . Then Approx(F L , G \ L, r ) = ∅.
Proof. Since κ(F H ) < ∞ we have S(F H , ∅) = ∅, by Lemma 4.11. Assume there is a point x ∈ Approx(F L , G \ L, r ). Then, as H ⊆ L we have that |h(x)| ⩽ r ∥h∥ for all h ∈ F H and it follows that

1 κ(F H ) ⩽ 1 κ(F H , x) = ∥F H (x)∥ ∥F H ∥ ⩽ r .
This is in contradiction with the hypothesis on r and hence Approx(F L , G \ L, r ) is empty. □ Theorem 4.19. Let q ⩽ n + 1. For any positive number r < 13D Proof. We will abbreviate S S(F, G) and κ * κ * (F, G). The proof is by induction on the difference ℓ := nq + 1 between the number of variables and the number of equations. Before dealing with the basis of the induction, we note that the assumption on r implies that κ * < ∞.

If ℓ = 0, then κ(F ) = κ * < ∞ and, because of our hypothesis, r < 1 κ * . We deduce from Lemma 4.18, with L = H = ∅ that Approx(F, G, r ) = ∅. The desired inclusion is therefore trivially true. Now we assume ℓ > 0, i.e., q ⩽ n, and consider a point x ∈ Approx(F, G, r ). It is enough to show that d S (x, S) < 3κ * r .

To do so, we focus on the set of inequalities

L := д ∈ G | |д(x)| < r ∥д∥ .
By construction, we have x ∈ Approx(F L , G \ L, r ), and moreover д(x) ⩾ r ∥д∥ > 0 for all д ∈ G \ L.

We further note that |L| ⩽ nq, otherwise there would exist H ⊆ L with |H | = nq + 1 and, we would use again Lemma 4.18 to deduce that Approx(F, G, r ) = ∅, in contradiction with the fact that x ∈ Approx(F, G, r ). We next divide by cases.

Case 1: L ∅. As |F L | ⩽ n + 1 we may apply the induction hypothesis to the larger set F L of equations and the smaller set G \ L of inequalities; note that κ * (F L , G \ L) ⩽ κ * (F, G) so the hypothesis on r is still true for (F L , G \ L). The induction hypothesis yields

Approx(F L , G \ L, r ) ⊆ U S S(F L , G \ L), 3κ * (F L , G \ L)r ⊆ U S (S, 3κ * r ) .
Hence we obtain [START_REF] Cucker | A numerical algorithm for zero counting. II: Distance to ill-posedness and smoothed analysis[END_REF] and are done in this case.

Case 2: L = ∅. We put u ∥F (x)∥/∥F ∥. Then u ⩽ r since x ∈ Approx(F, G, r ). Moreover, κ * u ⩽ κ * r < 1 13 by assumption. By definition, κ(F, x) 2 ⩾ 1 µ proj (F, x) -2 + u 2 ⩾ 1 2 min µ proj (F, x) 2 , u -2 .
This minimum equals µ proj (F, x) 2 since κ * u ⩽ 1 13 , so we get

√ 2 κ * ⩾ √ 2 κ(F ) ⩾ √ 2 κ(F, x) ⩾ µ proj (F, x) = µ norm ( F, x),
where F F | T x denotes the restriction of F to the affine space T x . From the inequality above, Proposition 4.1, and u < r , it follows that

α( F, x) ⩽ 1 2 D 3 2 µ norm ( F, x) 2 u ⩽ D 3 2 κ 2 * r, β( F, x) ⩽ µ norm ( F, x)u ⩽ √ 2κ * r . (28)
From the assumption on r , we get α( F, x) ⩽ 1 13 , which makes possible the application of Theorem 3.1. We also note that β( F, x) < 1 13 . As in §3.2, we define x t in the affine space T x by the system of differential equations

x t = -D F (x t ) † F (x t ), x 0 = x .
Note that x t 0 for all t ⩾ 0 as ∥z ∥ ⩾ 1 for all z ∈ T x . We define y t x t /∥x t ∥ ∈ S n . By Theorem 3.1, there is a limit point x ∞ ∈ T x , which is a zero of F , and which satisfies ∥x ∞ -x ∥ < 2β( F, x). In particular, y ∞ is a zero of F and

d S (y ∞ , x) ⩽ ∥x ∞ -x ∥ ⩽ 2β( F, x) ⩽ 2 √ 2κ * r < 3κ * r,
where we used [START_REF] Cucker | Computing the Homology of Real Projective Sets[END_REF] for the second inequality. If д(y ∞ ) ⩾ 0 for all д ∈ G, then y ∞ ∈ S and d S (x, S) ⩽ d S (x, y ∞ ), hence [START_REF] Cucker | A numerical algorithm for zero counting. II: Distance to ill-posedness and smoothed analysis[END_REF] and we are done.

Computing the Homology of Basic Semialgebraic Sets

5:23

So suppose that д(y ∞ ) < 0 for some д ∈ G and let s > 0 be the smallest real number such that д(y s ) = 0 for some д ∈ G. By construction, the set H {д ∈ G | д(y s ) = 0} is nonempty and element of G \ H is positive at y s . Also, for every f ∈ F ,

| f (y s )| = | f (x s )| ∥x s ∥ deg f ⩽ | f (x s )| = | f (x)|e -s ⩽ ∥ f ∥re -s
where the second equality is due to Theorem 3.1(i). Therefore, y s ∈ Approx(F H , G \ H, re -s ).

Using again Lemma 4.18 we deduce that |H | < n -q + 1 = ℓ. We can therefore apply the induction hypothesis to the larger set F H of equations and the smaller set G \ H of inequalities; note that re -s < r and κ * (F H , G \ H ) ⩽ κ * . Thus we obtain

Approx(F H , G \ H, re -s ) ⊆ U S S(F H , G \ H ), 3κ * (F H , G \ H )r ⊆ U S (S, 3κ * r ) , the latter because S(F H , G \ H ) ⊆ S and κ * (F H , G \ H ) ⩽ κ * . We conclude that d S (y s , S) < 3κ * re -s . Also, by Theorem 3.1(ii), d S (y s , x) ⩽ ∥x s -x ∥ ⩽ 2β( F, x)(1 -e -s ) < 2 √ 2κ * r (1 -e -s ),
the last inequality by [START_REF] Cucker | Computing the Homology of Real Projective Sets[END_REF]. We finally deduce that

d S (x, S) ⩽ d S (x, y s ) + d S (y s , S) < 2 √ 2(1 -e -s ) + 3e -s κ * r < 3κ * r,
which shows [START_REF] Cucker | A numerical algorithm for zero counting. II: Distance to ill-posedness and smoothed analysis[END_REF] and finishes the proof. □

The geometry of ill-posedness

In order to analyze the set Σ ⊆ H d [q] of ill-posed inputs, cf. ( 19), we first study its complex version, defined as

Σ C := F ∈ H C d [q]
| ∃x ∈ P n F (x) = 0, rank DF (x) |T x < q . Here P n denotes the complex projective space of dimension n. Note that because of Euler's formula [18, (16.3)] we have

Σ C := F ∈ H C d [q] | ∃x ∈ P n F (x) = 0, rank DF (x) < q . In the special case q = n + 1, we have Σ C := {F ∈ H C d [n + 1] | ∃x ∈ P n F (x) = 0}.
It is well known that this is the zero set of the multivariate resultant, which is an irreducible polynomial with integer coefficients and degree n+1 i=1 k i d k [35, §13.1], which is at most (n + 1)D n . An extension of this result to the case q ⩽ n appears in [START_REF] Cucker | Computing the Homology of Real Projective Sets[END_REF]Proposition 5.3]. We further generalize this result to q ⩽ n + 1, slightly improving the bound in passing. Proposition 4.20. For any q ⩽ n + 1, the variety Σ C ⊆ H C d [q] is a hypersurface defined by an irreducible polynomial with integer coefficients of degree at most n2 n D n .

Proof. We abbreviate H := H C d [q] and first assume q ⩽ n. Consider the incidence variety

Σ C (F, x, v) ∈ H × (C n+1 \ {0}) × (C q \ {0}) F (x) = 0 and v T • DF (x) = 0 . (29)
The projection Σ C → (C n+1 \ {0}) × (C q \ {0}), (F, x, v) → (x, v) is surjective. Moreover, the fibers are linear subspaces of H of codimension n + q This implies that Σ C is irreducible [53, §6.3, Thm. 8] and dim Σ C = (n + 1) + q + dim H -nq = dim H + 1. The image of the projection Σ C → H, (F, x, v) → F equals Σ C , which is therefore irreducible. Moreover, since the fibers of this projection are generically of dimension 2, it follows that dim

Σ C = dim Σ C -2 = dim H -1. Hence
Σ C is indeed an irreducible hypersurface in H . That its defining equation has integer coefficients follows from elimination theory [45, §2.C] and the fact that Σ C is defined by polynomials with integer coefficients. For bounding the degree, we consider a variant of Σ C in a product of projective spaces. More specifically, we consider the variety S of all (F, x, u) ∈ P(H ) × P n × P q-1 , which are solutions of the multihomogeneous equations

         f i (x) = 0 for 1 ⩽ i ⩽ q, q i=1 u i x D-d i 0 ∂ f i ∂x j (x) for 1 ⩽ j ⩽ n. (30)
We note that the projection (F, x, u) → F maps S ∩ {X 0 0} to Σ C and hits all F ∈ Σ C except those in a lower dimensional subvariety.

We take now hyperplanes H 1 , . . . , H N -1 ⊆ H in general position, where N := dim P(H ). Let us denote by H k the inverse image of H k under the projection (F, x, u) → F . Then we have deg

Σ C = |H 1 ∩ . . . ∩ H N -1 ∩ Σ C | ⩽ | H 1 ∩ . . . ∩ H N -1 ∩ S | =: M. ( 31
)
The number M of intersections points on the right-hand side can be computed with the multiprojective Bézout's theorem, see e.

For this, note that the equations for H k have the multidegree (1, 0, 0), and the equations in [START_REF] Dedieu | Points Fixes, Zéros et La Méthode de Newton[END_REF] have the multidegree (1, d i , 0) and (1, D -1, 1) with respect to (the coefficients of) F , x, and u, respectively. The coefficient M can be bounded as M ⩽ q n q -1 D q-1 D n-q+1 + n n -1 q -1 D q D n-q ⩽ n2 n D n .

Indeed, when expanding [START_REF] Edelsbrunner | Three-Dimensional Alpha Shapes[END_REF], the left-hand contribution arises from selecting a in exactly one of the q factors in the left product and selecting c in exactly q -1 among the n factors of the right product. The right-hand contribution arises from selecting a in exactly one of the n factors in the right product and selecting c in exactly q -1 among the remaining n -1 factors of the right product.

In the case q = n + 1 we consider the incidence variety S := {(F, x) | F (x) = 0} ⊆ P(H ) × P n and argue similarly. In particular, the multiprojective Bézout's theorem implies that deg Σ C equals the coefficient of the monomial ab n in the product n+1 i=1 (a + d i b). This leads to the well known formula deg Σ C = i k i d i . Since this is bounded by (n + 1)D n , the degree bound in this case follows as well.

□

The weaker bound deg Σ C ⩽ D q+n , which is good enough for our purpose, can be obtained with a significantly simpler argument. Let X G r ∩ Approx(F, G, D 1 2 r ) and ε 5Dk * r , that is, the finite set and the real number output by the algorithm. We will now prove that U(X, ε) is homotopically equivalent to S. By Theorem 2.8, it is enough to prove the inequalities 3d H (X, S) < ε <

1 2 τ (S). (36)
The second inequality follows from Inequalities (34), [START_REF] Israel | Discriminants, Resultants, and Multidimensional Determinants[END_REF] and Theorem 4.12: Concerning the inequality 3d H (X, S) < ε, let x ∈ S. Because of [START_REF] Edelsbrunner | Incremental Topological Flipping Works for Regular Triangulations[END_REF], there is some y ∈ G r with d S (x, y) < r . Hence y lies in Approx(F, G, D where we used D ⩾ 2 for the last inequality. Thus we have shown that d H (X, S) < 1 3 ε. This concludes the proof of (36) and of the homotopy equivalence.

ε = 5Dk * r < 5
Lastly, we deal with the complexity analysis. We can approximate κ(F L , x) within a factor of 2 in O(N + n 3 ) operations [43, §2.5] and this is enough for our needs. For simplicity, we will do as if we could compute κ exactly.

The repeat loop performs O(log(Dκ * )) iterations. Each iteration can be done in O(|G r |M(N +n 3 )) operations, where M = n+1-q i=0 s i ⩽ (s + 1) n+1-q . Moreover, |X| ⩽ |G r | = (nDκ * ) O(n) and N + n 3 = (nD) O(n) . Therefore, the total number of operations is bounded by (s + n)Dκ * O(n) . □

Homology of a union of balls

Once in the possession of a pair (X, ε) such that S is a deformation retract of U(X, ε), the computation of the homology groups of S is a known process. One computes the nerve N of the covering {B(x, ε) | x ∈ X} (this is a simplicial complex whose elements are the subsets N of X such that ∩ x ∈N B(x, ε) is not empty) and from it, its homology groups H k (N ). Since the intersections of any collection of balls is convex, the Nerve Theorem [e.g. 12, Thm. 10.7]

Fig. 1

 1 Fig.1Illustration of the inequality τ (W , p, u) ⩽ ∥x -p ∥: A point x ′ beyond x on the half-line from p to x is closer to q than to p.

Fig. 2

 2 Fig. 2 Schematic view of the proof of Theorem 2.8

Theorem 3 . 3 .Proposition 3 . 4 .

 3334 Let M ⊆ E be the zero set of the analytic map F : E → R m and p ∈ M. Then we have τ (M, p)γ (F, p) ⩾1 14 if γ (F, p) < ∞. For p ∈ E such that rank DF (p) = m, let π p : E → E denote the orthogonal projection onto the kernel of DF (p), that is, π p = id E -DF (p) † DF (p). Note that if γ (F, p) < ∞ then locally around p, M is a smooth manifold and ker DF (p) is the tangent space T p M at p. The derivative of the rational map π : E → End(E), p → π p at p ∈ E has an operator norm bounded by 2γ (F, p). Here End(E) is endowed with the spectral norm. Proof. Let p ∈ M. The derivative of π at p, Dπ (p) : E → End(E), evaluated at p ∈ E yields [36, Cor. 4.2], Dπ (p)( p) = -DF (p) † • D 2 F (p)( p) • π p -(DF (p) † • D 2 F (p)( p) • π p ) T .Since 1 2 DF (p) † D 2 F (p) ⩽ γ (F, p), by the definition (8) of γ (F, p), it follows that ∥Dπ (p)∥ ⩽ 4γ (F, p). We obtain the sharper bound 2γ (F, p) by observing that ∥A + A T ∥ = ∥A∥ for any map A ∈ End(E) such that A 2 = 0, which holds forA = DF (p) † D 2 F (p)( p) π p . □It is worth noting that the derivative Dπ (p) is an incarnation of the second fundamental form B p : T p M × T p M → T p M ⊥ of M at p and one can see that ∥Dπ (p)∥ = ∥B p ∥. Proposition 3.4 means that the norm of the second fundamental form of M at p, a classical measure of curvature in differential geometry, is bounded by 2γ (F, p). This is related to[START_REF] Niyogi | Finding the homology of submanifolds with high confidence from random samples[END_REF] Prop. 6.1], where this norm is upper bounded by 1/τ (M).

Definition 4 . 15 .

 415 Let (d, 1) := (d 1 , . . . , d q+s , 1) ∈ N q+s+1 be the degree pattern obtained from d by appending 1. Consider the scaled homogeneization map

Proposition 4 . 16 .

 416 For any nonzero ψ ∈ P d [q ; s],κ aff * (ψ ) ⩽ 4D ∥ψ ∥ d(ψ , Σ aff * )

3 2 κ 2 * - 1

 31 we have Approx(F, G, r ) ⊆ U S (S(F, G), 3κ * r ).

  g. [53, §4.2.1][44]. According to this, M equals the coefficient of the monomial a N b n c q-1 in the product (a, b, c are formal variables) (D -1)b + c).

1 -* 1 -.

 11 From (29) we obtain with Bézout's Inequality deg Σ C ⩽ D q • D n [17, §8.2]. (Note that on an open subset we only need n equations out of v T • DF (x) = 0.) We conclude that deg Σ C ⩽ deg Σ C ⩽ D q+n [17, Lemma 8.32].Corollary 4.21. The set Σ * ⊆ H d [q ; s] of ill-posed homogeneous systems is included in the zero set of a nonzero polynomial with integer coefficients of degree at most n2 n (s + 1) n+1 D n . The same holds true for the set Σ aff * ⊆ P d [q ; s] of ill-posed affine systems.We will first show that κ * ⩽ (1+ 1 100 )k * .(35)Let L ⊆ G and y ∈ S n be such that κ * = κ(F L ) = κ(F L , y). Because of (33) there is some x ∈ G r such that d S (x, y) < r , and κ(F L , x) ⩽ k * by the definition of k * . Since the map x → 1/κ(F L , x) is D-Lipschitz continuous (Proposition 4.7), we have κ * = κ(F L , y) ⩽ κ(F L , x) Dκ(F L , x)r ⩽ k Dk * r as D ⩾ 2 and k * ⩾ 1, and Inequality (35) follows.

1 2 r 2 * 1 2

 221 ), by Proposition 4.17. Thus y ∈ X and d(x, X) < d S (x, y) < r < 1 3 ε. Next, let x ∈ X. Then, x ∈ Approx(F, r < 1 the last by Inequality[START_REF] Federer | Curvature Measures[END_REF]. Hence, Theorem 4.19 applies and shows that d(x, S) ⩽ d S (x, S) ⩽ 3κ * D

Cn 2 , 2 ⩽

 22 ensures that H k (N ) ≃ H k (U(X, ε)) ≃ H k (S) is cost(ψ ) = (s + n)D ∥ψ ∥ d(ψ , Σ aff * )for some C > 0. By Theorem 5.3 and Corollary 4.21,Prob cost(ψ ) ⩾ (s + n)Dt Cn 11n2 n (s + 1) n+1 D n N t = ((s + n)D) O(n) t ,where N dim P d [q ; s] ⩽ (s + n)(D + 1) n . We obtain Theorem 1.1(ii) with t = ((s + n)D) cn and Theorem 1.1(iii) with t = 2 c N , for some c large enough. For the latter, we use that(s + n)D O(n) =2 O(N ) and that n 2 = O(N ). □

  Let A t DF (x t ), B t A † t F (x t ), and P t := id E -A † t A t (the orthogonal projection on ker A t ). Then A t = D 2 F (x t )( x t ) and (we drop the index t)[START_REF] Golub | The Differentiation of Pseudo-Inverses and Nonlinear Least Squares Problems Whose Variables Separate[END_REF] Thm. 4.3]

J. ACM, Vol. 66, No. 1, Article 5. Publication date: December 2018.

We thank Théo Lacombe and a referee for raising this point. J. ACM, Vol. 66, No. 1, Article 5. Publication date: December

2 k 2 * r < 1.(34)J. ACM, Vol.

66, No. 1, Article 5. Publication date: December 2018.

ACKNOWLEDGMENTS

We are grateful to Josué Tonelli-Cueto and Mohab Safey El Din for helpful discussions, to Teresa Krick for her careful reading, and to Théo Lacombe and the referees for relevant remarks.

This work has been supported by the Einstein Foundation, Berlin, by the DFG research grant no. BU 1371/2-2, and by the Research Grants Council of the Hong Kong SAR project no. CityU-11202017.

Algorithm 1 Covering

Input. A homogeneous semialgebraic system (F, G) ∈ H d [q ; s] with q ⩽ n. Precondition. κ * (F, G) is finite. Output. A finite subset X of S n and an ε > 0. Postcondition. U(X, ε) is homotopically equivalent to S(F, G).

) and the real number ε := 5Dk * r end function Proof. For a subset L = {i 1 , . . . , i ℓ } of {1, . . . , s}, let p L be the projection

By definition of Σ * and κ * , Σ * is the union of the sets p -1 L (Σ L ) for all L with q + |L| ⩽ n + 1, where Σ L is the appropriate set of ill-posed data in H d [q + ℓ]. The number of such subsets L is at most (s + 1) n+1-q and we conclude with the fact that, for each of them,

] and the latter is the set of real zeros of a polynomial of degree n2 n D n by Proposition 4.20.

To settle the affine case, note that the scaled homogeneization map [START_REF] Connelly | A New Proof of Brown's Collaring Theorem[END_REF] has the structure H : R N → R N × R, a → (a, ∥a∥) and that Σ * is scale invariant. By definition, Σ aff * = H -1 (Σ * ). Suppose that the polynomial P vanishes on Σ * and let P(a, t) = i P i (a)t i be its decomposition into homogeneous parts. Then each P i vanishes on H -1 (Σ * ). □

ALGORITHMS

The covering algorithm

The main stepping stone towards computing the homology groups of a spherical semialgebraic set S is the computation of a finite set X and a real ε > 0 such that S is homotopically equivalent to U ε (X). We will do so using Theorems 2.8 and 4.19 in conjunction. For 0 < r < 1 we define G r as the image in S n under the map y →

We easily check that

where

Proposition 5.1. On input F and G, Algorithm Covering outputs a finite set X and an ε > 0 such that U(X, ε) is homotopically equivalent to S(F, G). Moreover, the computation performs

arithmetic operations, where s = |G | and κ * = κ * (F, G), and the number |X| of points in X is (nDκ * ) O(n) .

Proof. Let κ * κ * (F, G), S S(F, G) and let r and k * be the values of the corresponding variables after the repeat loop terminates in Algorithm Covering. By design,

Algorithm 2 Homology

Input. A semialgebraic system (F, G) ∈ P d [q + s] with q ⩽ n. Output. The homology groups of the set

N ← the nerve of U(X, ε) return the homology groups of N end function the last because S is a deformation retract of U(X, ε).

The process is described in detail in of [28, §4] where the proof for the following result can be found (see also [START_REF] Edelsbrunner | The Union of Balls and Its Dual Shape[END_REF][START_REF] Edelsbrunner | Incremental Topological Flipping Works for Regular Triangulations[END_REF] for improved algorithms for computing the nerve of a covering). Proposition 5.2. Given a finite set X ⊆ R n+1 and a positive real number ε, one can compute the homology of ∪ x ∈X B(x, ε) with |X| O(n) operations. □

Homology of affine semialgebraic sets

A pair (F, G) ∈ P d [q ; s] defines a basic semialgebraic set W (F, G) ⊆ R n as in [START_REF] Amelunxen | Average-case complexity without the black swans[END_REF] which is diffeomorphic to the subset of S n defined by F h = 0, G h ≻ 0 and X 0 > 0. As in §4.1.5, let H (F, G) ∈ H (d ,1) [q ; s + 1] denote this system of homogeneous polynomials (with X 0 > 0 replaced by ∥(F, G)∥X 0 > 0, which does not change the solution set). Proposition 4.14 tells us that, unless this system is ill-posed, we may replace X 0 > 0 with X 0 ⩾ 0 and any д > 0 with д ⩾ 0 without changing the homology of the solution set. In other words, if κ aff * (F, G) < ∞, then the spherical set S(H (F, G)) is homotopically equivalent to W (F, G).

Based on the tools introduced above, we may compute the homology of W (F, G), assuming that κ aff * (F, G) < ∞, by computing the nerve of a suitable covering of S(H (F, G)) obtained with Algorithm covering. This leads to Algorithm homology below whose analysis will prove Theorem 1.1.

Proof of Theorem 1.1 (i). By Proposition 5.1, the cost of computing the covering X is bounded by (s +n)Dκ aff * ) O(n) , where κ aff * κ aff * (F, G), and |X| = (nDκ aff * ) O(n) . By Proposition 5.2, the cost of computing the nerve N and its homology groups is |X| O(n) . Hence, the total cost of the algorithm is bounded by (s + n)Dκ aff * ) O(n 2 ) . Together with Proposition 4.16, this leads to the conclusion. □

The probabilistic analysis is based on the following result by Bürgisser and Cucker [18, Theorem 21.1] and follows a line of similar results that rely on the same ideas. We will be consequently brief. We rephrased the statement in terms of the isotropic Gaussian distribution instead of the uniform distribution on the sphere. The scale invariance of the statement makes both formulations equivalent. Theorem 5.3. Let Σ ⊆ R p+1 be contained in a real algebraic hypersurface, given as the zero set of a homogeneous polynomial of degree d and let a ∈ R p+1 be a centered isotropic Gaussian random variable. Then for all t ⩾ (2d + 1)p, Prob ∥a∥ d(a, Σ) ⩾ t ⩽ 11dp t . □

Proof of Theorem 1.1 (ii) and (iii). Let ψ = (F, G) ∈ P d [q ; s] be a centered isotropic Gaussian random variable. By Theorem 1.1 (i), the number of operations performed by algorithm Homology