# Effective Whitney Stratification of Real Algebraic Varieties

Martin Helmer  Department of Mathematics, North Carolina State University,
Raleigh, NC, USA<EMAIL_ADDRESS>and  Vidit Nanda  Mathematical Institute,
University of Oxford, Oxford, UK<EMAIL_ADDRESS>
###### Abstract.

We describe an algorithm to compute Whitney stratifications of real algebraic
varieties. The basic idea is to first stratify the complexified version of the
given real variety using conormal techniques, and then to show that the
resulting stratifications admit a description using only real polynomials.
This method also extends to stratification problems involving certain basic
semialgebraic sets as well as real algebraic maps. One of the map
stratification algorithms described here yields a new method for solving the
real root classification problem.

##  1\. Introduction

There is a strange dichotomy encountered in the computational study of
algebraic varieties and their defining ideals whenever one transitions between
real and complex coefficients. The fundamental workhorse for real varieties is
the cylindrical algebraic decomposition algorithm [3, 6, 7, 16, 43], which (in
the worst case) has a doubly exponential time complexity in the number of
variables. Similarly, computations with complex varieties rely heavily on
Gröbner basis algorithms [12, 17, 39], which once again have a doubly
exponential worst case time complexity. What sets the two scenarios apart is
the fact that Gröbner basis computation is much more straightforward to
implement, and moreover, it tends to be far more tractable in practice than
the worst-case complexity might suggest. Thus, although basic algorithms for
both real and complex varieties rely on doubly exponential techniques, there
have been numerous advances in the computational study of complex varieties
which remain elusive for real varieties.

Nevertheless, real varieties arise more naturally in applications than their
complex counterparts. Of special interest to us here is the real root
classification problem, which seeks to describe how the number of real roots
of a parametric polynomial system varies as a function of the parameters. This
problem plays an important role in several applied contexts, such as: chemical
reaction networks [14, 19], medical imaging [4], computer vision [18],
kinematics and robotics [10, 23], ordinary differential equations [9], and
quadrature domains [2]. However, the geometry of a real variety is not readily
revealed by its defining polynomials; for instance, every real variety is the
vanishing locus of a single polynomial, whereas the minimal number of defining
polynomials forms an important (and non-trivial) invariant for complex
varieties. As such, one often seeks methods to subdivide a given variety into
simpler regions which fit together coherently. And indeed, cylindrical
algebraic decomposition provides precisely such a subdivision into
contractible cells. One of our goals in this work is to outline what we view
as a key step in an alternative framework for studying broad classes of
applied and computational problems in real algebraic geometry.

### Whitney Stratifications

There are many advantages to obtaining a cell decomposition of a variety — it
becomes possible, for instance, to directly compute the Euler characteristic,
and (with a bit more work) the Betti numbers. On the other hand, cells, being
homeomorphic images of open balls, are rather rigid objects. Cylindrical
algebraic decomposition tends to be impractical on larger (or more
complicated) varieties precisely because one often has to perform many
subdivisions in order to obtain cells; similarly, the number of these cells
can also be doubly exponential relative to the number of variables [6]. A more
general and flexible paradigm is furnished by the stratifications introduced
by Whitney [42], which play an essential role in microlocal geometry and
stratified Morse theory [22, 31].

######  Definition 1.1.

A pair $(M,N)$ of smooth submanifolds of $\mathbb{R}^{n}$ satisfies Whitney’s
Condition (B) if the following property holds at every point $q\in N$. Given
any pair of sequences ${\left\\{{p_{k}}\right\\}}\subset M$ and
${\left\\{{q_{k}}\right\\}}\subset N$ with $\lim p_{k}=q=\lim q_{k}$, if the
limiting tangent space and the limiting secant line

$T:=\lim_{k\to\infty}T_{p_{k}}M\quad\text{and}\quad\ell:=\lim_{k\to\infty}[p_{k},q_{k}]$

both exist, then $\ell\subset T$.

A Whitney stratification of a subset $X\subset\mathbb{R}^{n}$ is any locally-
finite decomposition

$X=\coprod_{\alpha}M_{\alpha}$

into smooth, connected nonempty manifolds $M_{\alpha}\subset X$ called strata,
so that every pair $(M_{\alpha},M_{\beta})$ satisfies Condition (B). It is
known by foundational work of Lê and Teissier [33] that every (real or
complex) algebraic variety $X$ admits a Whitney stratification such that for
each dimension $i$ the union $X_{i}$ of all strata of dimension $\leq i$ forms
a subvariety. One may therefore identify any such stratification of a
$k$-dimensional variety $X$ with a flag

$X_{\bullet}=\big{(}\varnothing\subset X_{0}\subset X_{1}\subset\cdots\subset
X_{k-1}\subset X_{k}=X\big{)}$

Figure 1. The Whitney Umbrella.

of subvarieties, with the understanding that its $i$-strata are connected
components of $X_{i}-X_{i-1}$.

One key consequence of imposing Condition (B) on strata pairs is
equisingularity: small neighbourhoods in $X$ of two points lying in the same
stratum $M_{\alpha}$ are guaranteed to be homeomorphic to each other in a
stratum-preserving manner. Consider, for instance, the (real) Whitney Umbrella
from Figure 1. This is the variety $X\subset\mathbb{R}^{3}$ defined by
$x^{2}-y^{2}z=0$, whose singular locus is the (positive) $Z$-axis (depicted as
a purple line in the figure). If we take a small neighbourhood in $X$ of a
point $(0,0,z)$ lying on the $Z$-axis, then its topology changes depending on
whether $z$ is positive, negative or zero. Thus, the origin must constitute a
separate $0$-dimensional stratum in any Whitney stratification of $X$.

### This Paper

The main contribution of our work here is a suite of practical algorithms for
constructing Whitney stratifications of real algebraic varieties and related
objects. Our prior work [26]111The Arxiv version [26] cited here incorporates
both the original paper [27] and its subsequent correction [28] in one
document. describes an effective algorithm for constructing Whitney
stratifications of complex varieties; this algorithm relies on primary
decompositions of conormal fibers (and hence, on Gröbner basis computation).
In the introductory remarks to [26], we highlighted the lack of Gröbner basis
techniques over $\mathbb{R}$ as a primary obstacle to performing similar
stratifications for real algebraic varieties and semialgebraic sets. We
overcome this obstacle here by examining, for any real variety
$X\subset\mathbb{R}^{n}$, the corresponding complex variety $X(\mathbb{C})$ —
this is precisely the vanishing locus of $X$’s defining polynomials treated as
elements of the ring $\mathbb{C}[x_{1},\ldots,x_{n}]$.

Having constructed $X(\mathbb{C})$, we obtain an effective Whitney
stratification of $X$ via the following two steps:

  1. (1)

we show in Theorem 3.3 that if $X_{\bullet}(\mathbb{C})$ is any Whitney
stratification of $X(\mathbb{C})$ for which each $X_{i}(\mathbb{C})$ is
generated by real polynomials, then the corresponding real varieties $X_{i}$
form a valid Whitney stratification of $X$; and moreover,

  2. (2)

we show in Corollary 3.4 that if a complex variety $Y\subset\mathbb{C}^{n}$ is
generated by real polynomials, then running the algorithm of [26] on $Y$
produces a Whitney stratification $Y_{\bullet}$ for which each $Y_{i}$ is also
generated by real polynomials.

These two results open the door for stratifying real algebraic varieties via
effective complex techniques. Unlike other efforts in this direction (see for
instance [1] which stratifies hypersurfaces in $\mathbb{R}^{3}$), the
algorithm described here works in general for all dimensions. Moreover, the
same techniques also readily adapt to the more general setting of full
semialgebraic sets (see Definition 4.1).

Motivated by the real root classification problem, we are particularly
interested here in stratifying algebraic maps $f:X\to Y$ between real
varieties. This amounts to a pair of Whitney stratifications $X_{\bullet}$ of
$X$ and $Y_{\bullet}$ of $Y$ such that $f$ sends each stratum of $X_{\bullet}$
submersively to a stratum of $Y_{\bullet}$. If $f$ is a proper map (this
always holds if $X$ is compact, for instance), then it forms a stratified
fiber bundle with respect to $X_{\bullet}$ and $Y_{\bullet}$. In other words,
the restriction $f^{-1}(N)\twoheadrightarrow N$ is an ordinary fiber bundle
for each stratum $N\subset Y$. As a consequence, the homeomorphism type of the
fiber $f^{-1}(y)$ depends only on the stratum $N$ and is independent of the
choice of point $y\in N$. To compute such a stratification of $f$, we once
again proceed by first treating it as a complex algebraic map
$f_{\mathbb{C}}:X(\mathbb{C})\to Y(\mathbb{C})$ and then using algorithms from
[26]. We then show in Theorem 3.6 that the resulting stratifications of
$X(\mathbb{C})$ and $Y(\mathbb{C})$ consist of varieties defined by real
polynomials, and that the corresponding real varieties furnish the desired
stratification of $f$.

The stratified fiber bundle property yields a convenient shortcut when solving
the real root classification problem — it suffices to count the number of real
roots only at a single point in each stratum222See [24, 35, 40] for methods to
sample points from real varieties and semialgebraic sets, since the root count
remains constant at all points in the same stratum. Unfortunately, the
requirement that $f:X\to Y$ be proper fails quite often in cases of interest
for general algebraic maps. One exception to this rule is when $f$ is a
dominant morphism between varieties of the same dimension (see Definition
3.7); fortunately, the algebraic maps arising from the real root
classification problem are always of this type. For such a morphism $f$, we
are able to partially recreate the stratified fiber bundle property in Theorem
3.10 by carefully analysing and decomposing the locus of points at which $f$
fails to be proper. Before proceeding to the details and proofs, we will
illustrate how stratifying dominant maps helps with real root classification.

Figure 2. A stratification $Y_{\bullet}$ of the parameter space
$Y=\mathbb{R}^{2}$ and the resulting number of real roots for the system (1)
over each stratum.

######  Example 1.2.

Consider the parametric system of equations in $\mathbb{R}^{2}$ given by:

$x^{2}-y^{2}+b=-ax+x^{2}+by=0$ (1)

where we think of $a,b$ as real parameters and $x,y$ as real variables. For a
generic choice of parameters $(a,b)\in\mathbb{R}^{2}$, the resulting system in
$x,y$ has finitely many solutions. We seek to stratify the parameter space
$Y=\mathbb{R}^{2}$ consisting of all possible $(a,b)$ values in terms of the
number of real roots of (1). To this end, consider the $2$-dimensional variety
$X\subset\mathbb{R}^{4}$ given by the vanishing locus of
$\eqref{eq:R2Classification}$, and let $f:X\to Y$ be the dominant projection
map which sends $(x,y,a,b)$ to $(a,b)$. The Whitney stratification of $Y$
obtained as a result of stratifying $f$ is illustrated in Figure 2, with the
number of real roots depicted over each stratum.

### Roadmap

The rest of this paper is organised as follows. In Section 2 we summarise
relevant results and algorithms from [26] for stratifying complex varieties.
The only new material here lies entirely in Section 2.3, where we are able to
remove a genericity hypothesis for map stratifications. Section 3 is focused
on stratifying real varieties and algebraic morphisms between them; we treat
dominant morphisms separately in Section 3.3. Our task in Section 4 is to
similarly stratify basic closed semialgebraic sets whose inequality loci are
open subsets of the ambient space — these often arise in practical contexts
owing to boundedness or positivity constraints. Finally, Section 5 deals with
the real root classification problem from the perspective of dominant morphism
stratification.

### Acknowledgements

The material in this article is based upon work supported by the Air Force
Office of Scientific Research (AFOSR) under award number FA9550-22-1-0462,
managed by Dr. Frederick Leve; both MH and VN were partially supported by this
award and would like to gratefully acknowledge this support.

##  2\. Complex Stratifications

In this section we begin with a brief review of the stratification algorithms
for complex varieties and their morphisms. Section 2.1 and Section 2.2 are a
review of the results of [26], restated in a form better suited to the current
presentation. On the other hand, Section 2.3 is mostly new and makes a key
generalization of the map stratification algorithm of [26, Section 6]; it
allows us to drop the genericity requirement from [26, Definition 6.3], so
that the Thom-Boardman flag of the given polynomial map $f:X\to Y$ need not
intersect $X$ transversely333See [21, Chapter VI] for a detailed treatment of
Thom-Boardman flags.. Instead, we consider arbitrary polynomial maps $f:X\to
Y$ between complex affine varieties $X\subset\mathbb{C}^{n}$ and
$Y\subset\mathbb{C}^{m}$, and derive (in Lemma 2.6) an expression for the
locus of smooth points of $X$ where the rank of $f$’s Jacobian drops below its
generic value.

A central role in our generalisation is played by a new type of
stratification, which we have called Whitney-Thom-Boardman stratifications of
$X$ along $f$ (see Definition 2.7). Here the decomposition of $X$ into strata
is well behaved with respect to the Thom-Boardman singularities of $f$.

######  Remark 2.1.

The generalization to non-generic maps will be essential for the application
of map stratification to the real root classification problem, which we
describe below in Section 5; in the root classification context, all maps of
interest will be non-generic in the sense of [26, Definition 6.3].

###  2.1. Stratification of Complex Varieties

Consider a pure $k$-dimensional complex variety
$X=\mathbf{V}_{\mathbb{C}}(I_{X})\subset\mathbb{C}^{n}$ defined by a radical
ideal $I_{X}=\langle f_{1},\dots,f_{r}\rangle$ in
$\mathbb{C}[x_{1},\dots,x_{n}]$. Let $X_{\rm reg}$ denote the (open, dense)
manifold of smooth points in $X$ and let $X_{\rm Sing}=X-X_{\rm reg}$ be the
singular locus of $X$; recall $X_{\rm Sing}$ is a closed proper subvariety of
$X$. The conormal variety of $X$ is the subvariety of
$X\times(\mathbb{P}^{n-1})$ given by

${\rm\bf Con}(X)=\overline{\left\\{(p,\xi)\;|\;p\in X_{\rm reg}\text{ and
}T_{p}X_{\rm reg}\subset\xi^{\perp}\right\\}}.$

In other words, ${\bf Con}(X)$ is obtained by closing the set of pairs
$(p,\xi)$ consisting of points $p\in X_{\rm reg}$ and $\xi\in\mathbb{P}^{n-1}$
such that the inner product $\left\langle{\xi,v}\right\rangle$ is zero for all
$v\in T_{p}X_{\text{reg}}$. We note the later coordinate is taken to be
projecive as we identify all constant multiples of a particular unit direction
vector defining the normal to a plane. The conormal variety comes endowed with
a canonical projection map $\kappa_{X}:{\rm\bf Con}(X)\to X$ induced by the
coordinate projection $\mathbb{C}^{n}\times\mathbb{P}^{n-1}\to\mathbb{C}^{n}$.
Work in the ring $\mathbb{C}[x_{1},\dots,x_{n}][\xi_{1},\dots,\xi_{n}]$ and
set

$\mathscr{K}=\begin{bmatrix}\xi_{1}&\cdots&\xi_{n}\\\ \frac{\partial
f_{1}}{\partial x_{1}}&\cdots&\frac{\partial f_{1}}{\partial x_{n}}\\\
\vdots&\ddots&\vdots\\\ \frac{\partial f_{m}}{\partial
x_{1}}&\cdots&\frac{\partial f_{m}}{\partial x_{n}}\\\
\end{bmatrix}\quad\text{ and }\quad\mathscr{J}=\begin{bmatrix}\frac{\partial
f_{1}}{\partial x_{1}}&\cdots&\frac{\partial f_{1}}{\partial x_{n}}\\\
\vdots&\ddots&\vdots\\\ \frac{\partial f_{m}}{\partial
x_{1}}&\cdots&\frac{\partial f_{m}}{\partial x_{n}}\\\ \end{bmatrix}.$

The conormal variety ${\rm\bf Con}(X)=\mathbf{V}_{\mathbb{C}}(I_{{\rm\bf
Con}(X)})$ is defined by the radical ideal obtained via the saturation
$I_{{\rm\bf Con}(X)}=(I_{X}+K):J^{\infty}$ — here $K$ is the ideal generated
by all $(n-k+1)\times(n-k+1)$ minors of the matrix $\mathscr{K}$, while $J$ is
similarly defined by the $(n-k)\times(n-k)$ minors of the matrix
$\mathscr{J}$. Note that the singular locus $X_{\rm Sing}$ is precisely
$\mathbf{V}_{\mathbb{C}}(J)$. A definition of ideal saturation and a
discussion of how it is computed may be found in books such as [12, §4.4]. The
following result [26, Theorem 3.1] forms the basis for efficient Whitney
stratification of a given variety $X$. Recall that given an ideal $I$ its
associated primes are the radicals of the ideals appearing in a minimal
primary decomposition of $I$, see books such as [12, 38] for definitions and
see [13] for a survey of methods for the computation of associated primes of
an ideal via Gröbner basis.

######  Theorem 2.2.

Let $X\subset\mathbb{C}^{n}$ be a pure dimensional variety, let $Y\subset
X_{\rm Sing}=(X-X_{\rm reg})$ be a nonempty irreducible subvariety defined by
a radical ideal $I_{Y}$, and set
$I_{\kappa^{-1}_{X}(Y)}:=I_{\mathbf{Con}(X)}+I_{Y}$. Let
$\\{P_{1},\dots,P_{s}\\}$ be the associated primes of
$I_{{\kappa_{X}^{-1}(Y)}},$ let
$\sigma\subset{\left\\{{1,2,\ldots,s}\right\\}}$ be the set of indices $i$
with $\dim\kappa_{X}(\mathbf{V}_{\mathbb{C}}(P_{i}))<\dim Y$ and let

$A:=\left[\bigcup_{i\in\sigma}\kappa_{X}(\mathbf{V}_{\mathbb{C}}(P_{i}))\right]\cup
Y_{\rm sing}.$

Then the pair $(X_{\text{\rm reg}},Y-A)$ satisfies Condition (B).

Using this theorem it is shown in [26] that the WhitStrat algorithm below
correctly computes the Whitney stratification of the variety $X$ and is
guaranteed to terminate in finitely many steps.

| WhitStrat$(X)$
---|---
|  Input: A pure $k$-dimensional variety $X\subset\mathbb{P}^{n}$.
|  Output: A list of subvarieties $X_{\bullet}$ of $X$.
1 |  Set $X_{\bullet}:=(X_{k},X_{k-1},\ldots,X_{0}):=(X,\varnothing,\ldots,\varnothing)$
2 |  Compute $X_{\rm Sing}$ and $\mu:=\dim(X_{\rm Sing})$
3 |  For each irreducible component $Z$ of $X_{\text{sing}}$
4 |  Add $Z$ to $X_{\geq\dim Z}$
5 |  For each $d$ in $(\mu,\mu-1,\ldots,1,0)$
6 |  Set $X_{\bullet}:={\bf Merge}(X_{\bullet},{\bf Decompose}(\text{\rm Pure}_{d}(X_{d}),X))$
7 |  Set $X_{\bullet}:={\bf Merge}(X_{\bullet},{\bf WhitStrat}(\text{\rm Pure}_{d}({X_{d}})))$
8 |  Return $X_{\bullet}$

The WhitStrat function makes use of three subroutines (invoked in lines 6 and
7):

  1. (1)

$\text{\rm Pure}_{d}$ extracts the purely $d$-dimensional irreducible
components of the input variety; this is accomplished via prime decomposition
[13, 15].

  2. (2)

Let $V_{\bullet}$ and $W_{\bullet}$ be nested sequences of subvarieties of a
common variety, with the length $p$ of $V_{\bullet}$ larger than the length
$q$ of $W_{\bullet}$. Then Merge$(V_{\bullet},W_{\bullet})$ creates a new
sequence $U_{\bullet}$ of length $p$ via $U_{i}:=V_{i}\cup W_{\max(i,q)}$.

  3. (3)

Finally, the Decompose subroutine which is presented below. This sub routine
implements Theorem 2.2 by computing the dimension of the elimination ideal $K$
(Lines 4 and 5) arising from each primary component of
$J=I_{\kappa_{X}^{-1}(Y)}$ and noting those (Line 6) which have dimension less
than $Y$, hence explicitly constructing the subvarieties of $Y$ (not
necessarily contained in $Y_{\rm Sing}$) where Condition (B) fails with
respect to $X$.

| Decompose$(Y,X)$
---|---
|  Input: Projective varieties $Y\subset X$ in $\mathbb{P}^{n}$, with $d:=\dim
Y$.
|  Output: A list of subvarieties $Y_{\bullet}$ of $Y$.
1 |  Set $Y_{\bullet}:=(Y_{d},Y_{d-1},\ldots,Y_{0}):=(Y,\varnothing,\ldots,\varnothing)$
2 |  Set $J:=I_{\mathbf{Con}(X)}+I_{Y}$
3 |  For each primary component $Q$ of a primary decomposition of $J$
4 |  Set $K:=Q\cap\mathbb{C}[x]$
5 |  If $\dim\mathbf{V}_{\mathbb{C}}(K)<\dim Y$
6 |  Add $\mathbf{V}_{\mathbb{C}}(K)$ to $Y_{\geq\dim\mathbf{V}_{\mathbb{C}}(K)}$
7 |  Return $Y_{\bullet}$

###  2.2. Flag-Subordinate Stratifications

By a flag $\mathbf{F}_{\bullet}$ on a variety $X\subset\mathbb{C}^{n}$ we mean
any finite nested set of subvarieties of the form

$\varnothing=\mathbf{F}_{-1}X\subset\mathbf{F}_{0}X\subset\mathbf{F}_{1}X\subset\cdots\subset\mathbf{F}_{\ell-1}X\subset\mathbf{F}_{\ell}X=X.$

The integer $\ell$ is called the length of $\mathbf{F}_{\bullet}$. There are
no additional restrictions on the dimensions of the individual
$\mathbf{F}_{i}X$ and, in particular, we do not require successive differences
$\mathbf{F}_{i}X-\mathbf{F}_{i-1}X$ to be smooth manifolds or to satisfy
Condition (B).

######  Definition 2.3.

Let $X\subset\mathbb{C}^{n}$ be an affine variety and $\mathbf{F}_{\bullet}$ a
flag on $X$ of length $\ell$. A Whitney stratification $X_{\bullet}$ of $X$ is
subordinate to $\mathbf{F}_{\bullet}$ if for each stratum $S\subset X$ of
$X_{\bullet}$ there exists some $j=j(S)$ in
${\left\\{{0,\ldots,\ell}\right\\}}$ satisfying
$S\subset(\mathbf{F}_{j}X-\mathbf{F}_{j-1}X)$.

It is shown in [26, §5] that a flag subordinate stratification of a complex
algebraic variety can always be successfully computed using the algorithm
WhitStratFlag presented below.

| WhitStratFlag$(X,\mathbf{F}_{\bullet}X)$
---|---
|  Input: A pure $k$-dimensional variety $X\subset\mathbb{C}^{n}$ and a flag
$F_{\bullet}$ on $X$.
|  Output: A list of subvarieties $X_{\bullet}\subset X$.
1 |  Set $X_{\bullet}:=(X_{k},X_{k-1},\ldots,X_{0}):=(X,\varnothing,\ldots,\varnothing)$
2 |  Compute $X_{\rm Sing}$ and $\mu:=\dim(X_{\rm Sing})$
3 |  Set $X_{d}=X_{\rm Sing}$ for all $d$ in ${\left\\{{\mu,\mu+1,\ldots,k-1}\right\\}}$
4 |  Merge $X_{\bullet}$ with InducedFlag$(X_{\text{sing}},\mathbf{F}_{\bullet}X)$
5 |  For each $d$ in $(\mu,\mu-1,\ldots,1,0)$
6 |  Merge $X_{\bullet}$ with ${\bf DecomposeFlag}(X_{d},X,\mathbf{F}_{\bullet})$
7 |  Merge $X_{\bullet}$ with ${\bf WhitStratFlag}(X_{d},\mathbf{F}_{\bullet})$
8 |  Return $X_{\bullet}$

Our main motivation for considering flag subordinate stratification is to
develop algorithms to stratify algebraic maps between varieties. The required
subroutines ${\bf DecomposeFlag}$ and ${\bf InducedFlag}$ are included below.

The first subroutine, ${\bf DecomposeFlag}$, implements the criterion given in
Theorem 2.2 to detect subvarieties of the given variety $Y$ where Whitney’s
condition B fails with respect to $X$. The only change to ${\bf
DecomposeFlag}$ from to the standard ${\bf Decompose}$ subroutine above is
that rather than directly updating $Y_{\bullet}$ by merging the detected
subvariety $\mathbf{V}_{\mathbb{C}}(K)$ with the current $Y_{\bullet}$ we
first calculate the new flag induced by intersecting
$\mathbf{V}_{\mathbb{C}}(K)$ with $\mathbf{F}_{\bullet}X$, using the function
InducedFlag, and then update $Y_{\bullet}$ by merging the result with the
current $Y_{\bullet}$.

| DecomposeFlag$(Y,X,\mathbf{F}_{\bullet})$
---|---
|  Input: Varieties $Y\subset X\subset\mathbb{C}^{n}$ with $d:=\dim Y$ and a
flag $\mathbf{F}_{\bullet}$ on $X$.
|  Output: A list of subvarieties $Y_{\bullet}\subset Y$.
1 |  Set $Y_{\bullet}:=(Y_{d},Y_{d-1},\ldots,Y_{0}):=(\varnothing,\ldots,\varnothing)$
2 |  Set $J:=I_{\mathbf{Con}(X)}+I_{Y}$
3 |  For each primary component $Q$ of a primary decomposition of $J$
4 |  Set $K:=Q\cap\mathbb{C}[x]$
5 |  If $\dim\mathbf{V}_{\mathbb{C}}(K)<\dim Y$
6 |  Merge $Y_{\bullet}$ with InducedFlag$(\mathbf{V}_{\mathbb{C}}(K),\mathbf{F}_{\bullet}X)$
7 |  Return $Y_{\bullet}$

The second new subroutine is InducedFlag, as mentioned above this subroutine
computes the flag which is induced by the intersection of given flag
$\mathbf{F}_{\bullet}$ and subvariety $W$. In particular, InducedFlag
constructs a new flag with is a refinement of the input flag and contains all
the irreducible components arising from the intersection of the subvariety $W$
with varieties in the flag $\mathbf{F}_{\bullet}$.

| InducedFlag$(W,\mathbf{F}_{\bullet})$
---|---
|  Input: A subvariety $W\subset X\subset\mathbb{C}^{n}$ and a flag
$\mathbf{F}_{\bullet}$ on $X$ of length $\ell$.
|  Output: A flag $\mathbf{F}^{\prime}_{\bullet}$ on $W$ of length $\ell$.
1 |  Set $\mathbf{F}^{\prime}_{\bullet}W:=(\mathbf{F}^{\prime}_{\ell}W,\ldots,\mathbf{F}^{\prime}_{0}W):=(\varnothing,\ldots,\varnothing)$
2 |  For each irreducible component $V$ of $W$
3 |  Add $V$ to $\mathbf{F}^{\prime}_{i}W$ for all $\mathbf{F}^{\prime}_{i}$ where $V\subset\mathbf{F}^{\prime}_{i}$
4 |  For each $j$ with $\dim(\mathbf{F}_{j}X\cap V)<\dim V$
5 |  Add $V_{j}:=(\mathbf{F}_{j}X\cap V)$ to $\mathbf{F}^{\prime}_{i}W$ for all $\mathbf{F}^{\prime}_{i}$ where $V_{j}\subset\mathbf{F}^{\prime}_{i}$
6 |  Return $\mathbf{F}^{\prime}_{\bullet}W$

###  2.3. Stratifying Complex Algebraic Morphisms

Maps between Whitney stratified spaces are typically required to satisfy
additional criteria beyond smoothly sending strata to strata — see [5, Def
3.5.1] or [22, Part I, Ch 1.7] for instance.

######  Definition 2.4.

Let $\mathscr{X}_{\bullet}$ and $\mathscr{Y}_{\bullet}$ be Whitney
stratifications of topological spaces $\mathscr{X}$ and $\mathscr{Y}$. A
continuous function $\phi:\mathscr{X}\to\mathscr{Y}$ is stratified with
respect to $\mathscr{X}_{\bullet}$ and $\mathscr{Y}_{\bullet}$ if for each
stratum $M\subset\mathscr{X}$ there exists a a stratum $N\subset\mathscr{Y}$
satisfying two requirements:

  1. (1)

the image $\phi(M)$ is wholly contained in $N$; and moreover,

  2. (2)

the restricted map $\phi|_{M}:M\to N$ is a smooth submersion.444Explicitly,
its derivative $d(\phi|_{S})_{x}:T_{x}M\to T_{\phi(x)}N$ is surjective at each
point $x$ in $M$.

The pair $(\mathscr{X}_{\bullet},\mathscr{Y}_{\bullet})$ is called a
stratification of $\phi$.

######  Remark 2.5.

The second requirement of Definition 2.4 ensures the following crucial
property via Thom’s first isotopy lemma [37, Prop 11.1]. If $\phi$ is a proper
map – namely, if the inverse image of every compact subset of $Y$ is compact
in $X$ – then for every stratum $N\subset Y$, the restriction of $\phi$ forms
a locally trivial fiber bundle from $\phi^{-1}(N)$ to $N$.

Fix varieties $X\subset\mathbb{C}^{n}$ and $Y\subset\mathbb{C}^{m}$ along with
a polynomial map $f:\mathbb{C}^{n}\to\mathbb{C}^{m}$ that sends points of $X$
to points of $Y$. In [26, Section 6], we described an effective algorithm for
stratifying any $f:X\to Y$ whose Thom-Boardman flag555See [21, Chapter VI].
intersects $X$ transversely. Here we will describe a new modification which
circumvents this transversality requirement. The first step towards this goal
is the following result.

######  Lemma 2.6.

Let $G:={\left\\{{g_{1},g_{2},\ldots,g_{s}}\right\\}}$ be any set of
polynomials defining $X\subset\mathbb{C}^{n}$ which generate a radical ideal.
Consider, at each $x\in X$, the matrix of partial derivatives

$\mathbf{M}_{G}(x):=\begin{bmatrix}{\partial g_{1}}/{\partial
x_{1}}&\cdots&{\partial g_{s}}/{\partial x_{1}}\\\ \vdots&\ddots&\vdots\\\
{\partial g_{1}}/{\partial x_{n}}&\cdots&{\partial g_{s}}/{\partial x_{n}}\\\
\end{bmatrix}$

evaluated at $x$. For each $j$ in ${\left\\{{0,1,\ldots,\dim X}\right\\}}$,
let $V_{j}=V_{j}(X;f)$ be the subvariety of $\mathbb{C}^{n}$ generated by all
$j\times j$ minors of the augmented matrix
$\mathbf{A}(x):=\begin{bmatrix}\mathbf{M}_{G}(x)&\text{\bf J}f(x)^{\text{\sf
T}}\end{bmatrix}$. Writing $f^{*}:X_{\text{\rm reg}}\to\mathbb{C}^{m}$ for the
restriction of $f$ to the smooth points of $X$, we have

$\text{\rm rank }\text{\bf J}f^{*}(x)\leq i\quad\text{ if and only if }\quad
x\in V_{(n-\dim X)+(i+1)},$

for all $i$ in ${\left\\{{0,1,\ldots,\min(\dim X,m)}\right\\}}$.

###### Proof.

At each point $x\in X_{\text{reg}}$, the left block of $\mathbf{A}(x)$ equals
$\mathbf{M}_{G}(x)$, whose $s$ columns span the orthogonal complement of
$T_{x}X_{\text{reg}}$ in $\mathbb{C}^{n}$. Since this complement necessarily
has dimension $(n-\dim X)$ regardless of the chosen $x$, we obtain

$\text{rank }\textbf{A}(x)\geq n-\dim X.$

The right block, consisting of $\text{\bf J}f(x)^{\text{\sf T}}$, has columns
which span the coimage of $\text{\bf J}f(x)$, i.e., the orthogonal complement
of $\ker\text{\bf J}f(x)$ in $\mathbb{C}^{n}$. Thus, the following criteria
are equivalent:

  1. (1)

$\text{rank }\text{\bf J}f^{*}(x)=0$,

  2. (2)

the coimage of $\text{\bf J}f(x)$ is a subspace of the orthogonal complement
$T_{x}X_{\text{reg}}^{\perp}$,

  3. (3)

the columns of $\text{\bf J}f(x)^{\mathsf{T}}$ are spanned by those of
$\mathbf{M}_{G}(x)$,

  4. (4)

$\mathbf{A}(x)$ assumes its minimum possible rank of $n-\dim X$.

Similarly, $\text{rank }\text{\bf J}f^{*}(x)=i$ holds whenever $\text{rank
}\mathbf{A}(x)=(n-\dim X)+i$; this rank condition on $\mathbf{A}(x)$
corresponds to the vanishing of all minors of size $(n-\dim X)+i+1$, as
claimed above. ∎

In light of the preceding result, we will work with the rank flags of $f$
along various subvarieties of $X$; given such a subvariety $Z\subset X$, the
relevant flag is defined by

$\displaystyle\mathbf{R}_{i}Z:=Z\cap V_{n-\dim Z+i+1}(Z;f).$ (2)

Here $V_{\bullet}(Z;f)$ is given in the statement of Lemma 2.6, with $0\leq
i\leq\min(\dim Z,m)$. By construction, the Jacobian of the restriction
$f^{*}:Z_{\text{reg}}\to\mathbb{C}^{m}$ has rank $\leq i$ at a point $z\in
Z_{\text{reg}}$ if and only if $z$ lies in $\mathbf{R}_{i}Z$.

######  Definition 2.7.

A Whitney-Thom-Boardman (WTB) stratification of $X$ along the map
$f:\mathbb{C}^{n}\to\mathbb{C}^{m}$ is any pair
$(X_{\bullet},\mathbf{S}_{\bullet}X)$, where $X_{\bullet}$ is a Whitney
stratification of $X$ while $\mathbf{S}_{\bullet}X$ is a flag on $X$ such that
two conditions hold:

  1. (1)

$X_{\bullet}$ is subordinate to $\mathbf{S}_{\bullet}X$, and

  2. (2)

for each $X_{\bullet}$-stratum $M\subset X$, we have
$\mathbf{R}_{i}\overline{M}\subset\mathbf{S}_{i}X$ whenever $0\leq i\leq\dim
M$.

The first requirement of this definition forces $X_{\bullet}$ to depend on
$\mathbf{S}_{\bullet}X$ whereas the second requirement makes
$\mathbf{S}_{\bullet}X$ dependant on $X_{\bullet}$. We are therefore compelled
to construct both $X_{\bullet}$ and $\mathbf{S}_{\bullet}X$ simultaneously via
the algorithm described below. It will also be necessary in the sequel to
produce WTB stratifications $(X_{\bullet},\mathbf{S}_{\bullet}X)$ for which
$X_{\bullet}$ is subordinate to an auxiliary flag $\mathbf{F}_{\bullet}X$.
Setting $\mathbf{F}_{i}X=X$ for all $i$, we obtain a WTB stratification as
defined above. To simplify the presentation, we will denote this important
special case as WTBStrat$(X,f)$.

| WTBStratFlag$(X,f,\mathbf{F}_{\bullet}X)$
---|---
|  Input: $f:X\to\mathbb{C}^{m}$ algebraic map with $k:=\dim X$;
$F_{\bullet}X$ a flag on $X$.
|  Output: A pair of flags $(X_{\bullet},\mathbf{S}_{\bullet}X)$ on $X$.
1 |  Set $X_{\bullet}:=(X_{k},X_{k-1},\ldots,X_{0}):=(X,\varnothing,\ldots,\varnothing)$
2 |  Compute $\mathbf{R}_{\bullet}X$ using Lemma 2.6
3 |  Set $\mathbf{S}_{\bullet}X:=\mathbf{R}_{\bullet}X$
4 |  Compute $X_{\rm Sing}$ and $\mu:=\dim(X_{\rm Sing})$
5 |  Compute $\mathbf{R}_{\bullet}X_{\rm Sing}$ using Lemma 2.6
6 |  Set $X_{d}:=X_{\rm Sing}$ for all $d$ in ${\left\\{{\mu,\mu+1,\ldots,k-1}\right\\}}$
7 |  Set $\mathbf{S}_{\bullet}X:={\bf Merge}(\mathbf{F}_{\bullet}X,\mathbf{R}_{\bullet}X_{\rm Sing})$
8 |  Set $X_{\bullet}:={\bf Merge}(X_{\bullet},{\bf InducedFlag}(X_{\text{sing}},\mathbf{S}_{\bullet}X))$
9 |  For each $d$ in $(\mu,\mu-1,\ldots,1,0)$
10 |  Set $X_{\bullet}:={\bf Merge}(X_{\bullet},{\bf DecomposeFlag}(X_{d},X,\mathbf{S}_{\bullet}X))$
11 |  Set $X_{\bullet}:={\bf Merge}(X_{\bullet},{\bf WTBStratFlag}(X_{d},f,\mathbf{F}_{\bullet}X))$
12 |  Compute $\mathbf{R}_{\bullet}X_{d}$ using Lemma 2.6
13 |  Set $\mathbf{S}_{\bullet}X:={\bf Merge}(\mathbf{S}_{\bullet}X,\mathbf{R}_{\bullet}X_{d})$
14 |  Return $(X_{\bullet},\mathbf{S}_{\bullet}X)$

######  Theorem 2.8.

Let $X\subset\mathbb{C}^{n}$ be a pure dimensional complex algebraic variety,
$f:\mathbb{C}^{n}\to\mathbb{C}^{m}$ a polynomial map, and
$\mathbf{F}_{\bullet}X$ a flag on $X$. Then,

  1. (1)

${\bf WTBStratFlag}(X,f,\mathbf{F}_{\bullet}X)$ terminates,

  2. (2)

its output $(X_{\bullet},\mathbf{S}_{\bullet}X)$ is a WTB stratification of
$X$ along $f$, and

  3. (3)

the Whitney stratification $X_{\bullet}$ is subordinate to
$\mathbf{F}_{\bullet}X$.

###### Proof.

The termination of WTBStratFlag follows from noting that the recursive call in
Line 9 involves the variety $X_{d}$ of dimension at most $d$, with $d$
strictly smaller than $k=\dim X$. And the fact that $X_{\bullet}$ is a Whitney
stratification of $X$ follows from the correctness of the original WhitStrat
algorithm [26, Sec 4.4]. Moreover, since $\mathbf{F}_{\bullet}X$ is merged
into $\mathbf{S}_{\bullet}X$ via Line 7, verifying that $X_{\bullet}$ is
$\mathbf{F}_{\bullet}$-subordinate can be reduced to checking that it is
$\mathbf{S}_{\bullet}$-subordinate. Therefore, it suffices to confirm that the
output pair $(X_{\bullet},\mathbf{S}_{\bullet}X)$ satisfies the two
requirements of Definition 2.7. To this end, consider an $i$-dimensional
stratum $M$ of $X_{\bullet}$.

To verify requirement (1), note that $M$ may be uniquely written as
$Z-X_{i-1}$, where $Z\subset X_{i}$ is an irreducible component — in
particular, this $Z$ will appear as a $V$ in Line 3 of InducedFlag when it is
called with first input $X_{i}$. Let $j$ be the minimal index satisfying
$Z\subset\mathbf{S}_{j}X$. Then $\dim(Z\cap\mathbf{S}_{\ell}X)<i$ for every
$\ell<j$, and so $Z_{\ell}=Z\cap\mathbf{S}_{\ell}X$ is Added to $X_{\bullet}$
in Line 5 of the InducedFlag. Thus, $Z_{\ell}$ is contained in $X_{m}$ for
some $m<i$. Since $X_{m}\subset X_{i}$, it follows that

$M\cap(\mathbf{S}_{p}X-\mathbf{S}_{p-1}X)=\varnothing\text{ whenever }p<j.$

But since $M\subset\mathbf{S}_{j}X$ and $Z$ is irreducible, we have
$Z\subset\mathbf{S}_{j}X$, whence $Z\subset\mathbf{S}_{p}X$ for all $p\geq j$.
Thus, $M$ also has empty intersections with
$\mathbf{S}_{p}X-\mathbf{S}_{p-1}X$ for $p>j$, as desired. Turning now to
property (2) of Definition 2.7, we observe that $\mathbf{S}_{\bullet}X$ is
initialized to $\mathbf{R}_{\bullet}X$ in line 3 of WTBStrat. Subsequently,
$\mathbf{R}_{\bullet}X_{d}$ is merged into $\mathbf{S}_{\bullet}X$ for each
$d\leq\dim X_{\text{sing}}$. Thus, for every $i$-stratum $M\subset X$, we have
enforced that
$\mathbf{R}_{j}\overline{M}\subset\mathbf{R}_{j}X_{i}\subset\mathbf{S}_{j}X$
whenever $j\leq i$. ∎

Given a WTB stratification $(X_{\bullet},\mathbf{S}_{\bullet}X)$ of $X$ along
$f$, we construct a pushforward flag $\mathbf{B}_{\bullet}$ on the codomain
variety $Y$ as follows. Writing $\ell$ for the length of
$\mathbf{S}_{\bullet}$, define

$\displaystyle\mathbf{B}_{i}Y:=\begin{cases}f(\mathbf{S}_{i}X)&i\leq\ell\\\
Y&i=\ell+1\end{cases}.$ (3)

The map stratification algorithm described below first constructs a
$\mathbf{B}_{\bullet}$-subordinate stratification $Y^{\prime}_{\bullet}$ of
$Y$. It then constructs a WTB stratification
$(X^{\prime\prime}_{\bullet},\mathbf{S}^{\prime}_{\bullet}X)$ of $X$ along $f$
such that $X^{\prime\prime}_{\bullet}$ is subordinate to the flag
$\mathbf{F}_{i}X:=f^{-1}(Y_{i})$.

| WhitStratMap$(X,Y,f)$
---|---
|  Input: Pure dimensional varieties $X,Y$ and a any morphism $f:X\to Y$.
|  Output: Lists of subvarieties $X_{\bullet}\subset X$ and
$Y_{\bullet}\subset Y$.
1 |  Set $(X^{\prime\prime}_{\bullet},{\mathbf{S}^{\prime\prime}_{\bullet}}X):={\bf WTBStrat}(X,f)$
2 |  Set ${\mathbf{B}^{\prime}_{\bullet}}Y:=(\mathbf{B}^{\prime}_{k+2}Y,\ldots,\mathbf{B}^{\prime}_{0}Y):=(Y,\varnothing,\ldots,\varnothing)$
3 |  For each $j$ in $(0,1,\ldots,k)$
4 |  Set  $\mathbf{B}^{\prime}_{j}Y:=f(\mathbf{S}^{\prime\prime}_{j}X)$
5 |  Set $\mathbf{B}^{\prime}_{k+1}Y:=Y$
6 |  Set $Y^{\prime}_{\bullet}:={\bf WhitStratFlag}(Y,\mathbf{B}^{\prime}_{\bullet})$
7 |  For each $i$ in $(0,1,\ldots,\dim Y)$
8 |  Set $\mathbf{F}_{i}X:=f^{-1}(Y^{\prime}_{i})$
9 |  Set $(X^{\prime}_{\bullet},{\mathbf{S}^{\prime}_{\bullet}}X):={\bf WTBStratFlag}(X,f,\mathbf{F}_{\bullet})$
10 |  Set $(X_{\bullet},Y_{\bullet}):=$ Refine$(X^{\prime}_{\bullet},Y^{\prime}_{\bullet},f)$
11 |  Return $(X_{\bullet},Y_{\bullet})$

The final line invokes a Refine subroutine, which will be described later. We
first highlight a crucial property of the Whitney stratifications
$(X^{\prime}_{\bullet},Y^{\prime}_{\bullet})$ which are invoked in Line 10.

######  Proposition 2.9.

For every $X^{\prime}_{\bullet}$-stratum $M\subset X$ there exist a
$Y^{\prime}_{\bullet}$-stratum $N\subset Y$ satisfying $f(M)\subset N$.
Moreover, at each point $x\in M,$ the Jacobian $\text{\bf
J}f|_{M}(x):T_{x}M\to T_{f(x)}N$ of the restricted map $f|_{M}$ has maximal
rank:

${\rm rank}(\text{\bf J}f|_{M}(x))=\min(\dim M,\dim N).$

###### Proof.

Noting that of $X^{\prime}_{\bullet}$ is subordinate to the flag
$\mathbf{F}_{\bullet}$ by Line 9 of WhitStratMap, we know that for each
stratum $M$ of $X^{\prime}_{\bullet}$ there is a number $i:=i(M)$ satisfying
$M\subset(\mathbf{F}_{i}X-\mathbf{F}_{i-1}X)$. Now by Line 8, for any such
stratum we have $f(M)\subset(Y^{\prime}_{i}-Y^{\prime}_{i-1})$. By the
definition of a Whitney stratum we know that $M$ is connected, and so its
image under the continuous map $f$ must also be connected; thus there is a
unique stratum $N\subset(Y^{\prime}_{i}-Y^{\prime}_{i-1})$ of
$Y^{\prime}_{\bullet}$ satisfying $f(M)\subset N$, as claimed above. It
remains to establish that the Jacobian of $f|_{M}:M\to N$ has maximal rank at
every point of $x$.

By Line 6 of WhitStratMap, the stratification $Y^{\prime}_{\bullet}$ is
subordinate to the flag $\mathbf{B}^{\prime}_{\bullet}Y$; thus, there exists a
number $j:=j(N)$ satisfying
$N\subset(\mathbf{B}^{\prime}_{j}Y-\mathbf{B}^{\prime}_{j-1}Y)$. From Line 9,
we note that $\mathbf{B}^{\prime}_{\bullet}$ is the pushforward of
$\mathbf{S}^{\prime\prime}_{\bullet}$, so we obtain

$\displaystyle
f^{-1}(N)\subset\mathbf{S}^{\prime\prime}_{j}X-\mathbf{S}^{\prime\prime}_{j-1}X.$
(4)

Recall that $\mathbf{S}^{\prime\prime}_{j}X$ contains
$\mathbf{R}_{j}\overline{M}$ by the second requirement of 2.7 (and similarly
for $j-1$). Therefore, the restricted map
$f^{*}:\overline{M}_{\text{reg}}\to\mathbb{C}^{m}$ has Jacobian of constant
rank $\rho_{j}$ given by

$\displaystyle\rho_{j}:=\min(\dim M,m)-j.$ (5)

Since $M$ is an open subset of $\overline{M}_{\text{reg}}$, for each $x\in M$
we immediately have $\text{rank }\big{(}\text{\bf J}f^{*}(x)\big{)}=\rho_{j}.$
Let $\iota:N\hookrightarrow\mathbb{C}^{m}$ be the inclusion map, and recall
that $f|_{M}:M\to N$ denotes the restriction of $f$ to $M$, now viewed as a
smooth map to $N$ rather than to $\mathbb{C}^{m}$. Thus, $f^{*}=\iota\circ
f|_{M}$, and the following diagram of derivatives commutes by the chain rule:

$\textstyle{T_{x}M\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\text{\bf
J}f|_{M}(x)}$$\scriptstyle{\text{\bf
J}f^{*}(x)}$$\textstyle{T_{f(x)}N\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\text{\bf
J}\iota({f(x)})}$$\textstyle{\mathbb{C}^{m}}$

Since $\iota$ is an embedding, its Jacobian is injective, so in particular the
rank of $\text{\bf J}f|_{M}(x)$ also equals $\rho_{j}$. Thus, we immediately
have $\rho_{j}\leq\min(\dim M,\dim N)$ and it only remains to establish the
opposite inequality. There are two cases to consider —

  1. (1)

if $\dim M\leq\dim N$: Note that $\dim N\leq m$ holds by the fact that $N$ is
a submanifold of $\mathbb{C}^{m}$. Thus, we have $\dim M\leq\dim N\leq m$, and
so (5) gives $\rho_{j}=\dim M-j$ for some $j\geq 0$, whence $\rho_{j}\geq\dim
M$.

  2. (2)

if $\dim M>\dim N$: Since $\mathbf{B}^{\prime}_{\bullet}$ is the pushforward
of $\mathbf{S}^{\prime\prime}_{\bullet}$, we have
$\mathbf{B}_{k}Y=f(\mathbf{S}^{\prime\prime}_{k}X)$ for all $k$. And since
$\mathbf{S}^{\prime\prime}_{\bullet}X$ is part of a WTB stratification of $X$
along $f$ by Line 1, we know from Definition 2.7 that the Jacobian of $f$ has
constant rank $\rho_{k}$ on (the smooth part of) the difference
$\Delta_{k}:=\mathbf{S}^{\prime\prime}_{k}X-\mathbf{S}^{\prime\prime}_{k-1}X$.
By the implicit function theorem, we therefore have
$\rho_{k}=\dim\mathbf{B}_{k}Y$ at every $k$ for which
$\Delta_{k}\neq\varnothing$. Since the nonempty set $f^{-1}(N)$ lies in
$\Delta_{j}$ by (4), we therefore have
$\dim\mathbf{B}^{\prime}_{j}Y=\rho_{j}$. Finally, since $N$ is an open subset
of $f(\Delta_{j})=\mathbf{B}^{\prime}_{j}Y-\mathbf{B}^{\prime}_{j-1}Y$, we
obtain $\rho_{j}=\dim N$.

Thus, in both cases, $\rho_{j}$ equals $\min(\dim M,\dim N)$, and $\text{\bf
J}f|_{M}(x)$ has maximal rank. ∎

The stratifications $X^{\prime}_{\bullet}$ and $Y^{\prime}_{\bullet}$ obtained
after the conclusion of Line 9 of WhitStratMap do not generally satisfy the
requirements of Definition 2.4. In particular, the crucial Jacobian-
surjectivity requirement fails whenever $\dim M<\dim N$. As established above,
in this case the Jacobian is injective rather than surjective. To fix this
defect, we consider the set of problematic strata-pairs
$\mathscr{P}=\mathscr{P}(X^{\prime}_{\bullet},Y^{\prime}_{\bullet})$ given by:

$\mathscr{P}:={\left\\{{(M,N)\mid f(M)\subset N\text{ with }\dim M<\dim
N}\right\\}}.$

The Refine subroutine (which is invoked in Line 10 of WhitStratMap) fixes this
defect. We note that a similar subroutine also appears in [26]; the main
difference between the two Refine subroutines is that the new one calls
WTBStrat instead of WhitStrat.

| Refine$(X^{\prime}_{\bullet},Y^{\prime}_{\bullet},f)$
---|---
|  Input: Stratifications $X^{\prime}_{\bullet},Y^{\prime}_{\bullet}$ of pure
dimensional varieties $X$ and $Y$
| and a morphism $f:X\to Y$.
|  Output: Lists of subvarieties $X_{\bullet}\subset X$ and
$Y_{\bullet}\subset Y$.
1 |  For each  $(S,R)\in\mathscr{P}(X^{\prime}_{\bullet},Y^{\prime}_{\bullet})$ with $\dim R$ maximal
2 |  Set $Y^{+}_{\bullet}:=Y^{\prime}_{\bullet}$
3 |  Set $d:=\dim\overline{f(S)}$
4 |  Add $\overline{f(S)}$ to $Y^{+}_{\geq d}$
5 |  Merge $Y^{+}_{\bullet}$ with WhitStrat$(\text{\rm Pure}_{d}(Y^{\prime}_{d}))$
6 |  For each $\ell=(d,d-1,\ldots,1,0)$
7 |  For each  irreducible $W\subset\overline{Y^{+}_{\ell}-Y^{\prime}_{\ell}}$ and $S^{\prime}\in\mathfrak{S}_{\ell}(X^{\prime}_{\bullet})$
8 |  If  $Z\cap S^{\prime}\neq\varnothing$ for an irreducible $Z\subset f^{-1}(W)$
9 |  Set $r:=\dim Z$
10 |  Add $Z$ to $X^{\prime}_{\geq r}$
11 |  Merge $X^{\prime}_{\bullet}$ with WTBStrat$({\rm Pure}_{r}(X^{\prime}_{r}),f)$
12 |  Set $Y^{\prime}_{\bullet}=Y^{+}_{\bullet}$
13 |  Recompute $\mathscr{P}(X^{\prime}_{\bullet},Y^{\prime}_{\bullet})$
14 |  Return $(X^{\prime}_{\bullet},Y^{\prime}_{\bullet})$

From Theorem 2.8 and Proposition 2.9, we obtain Proposition 2.10 below, which
is analogous to [26, Proposition 6.7]. The novelty here lies in the fact that
the result below applies to arbitrary polynomial maps between affine complex
varieties, and does not impose any genericity requirements. The proof,
however, is essentially identical to that of [26, Proposition 6.7].

######  Proposition 2.10.

The Refine subroutine terminates, and its output $(X_{\bullet},Y_{\bullet})$
constitutes a valid stratification (as in Definition 2.4) of the polynomial
map $f:X\to Y$.

###### Proof.

In [26, Proposition 6.7] this result is obtained for generic mappings $f:X\to
Y$, as defined in [26, Definition 6.3], using the construction of the Refine
subroutine along with a result ([26, Proposition 6.6]) analogous to that of
Proposition 2.9 in the case of generic maps. The new Refine subroutine above
is identical to that in [26, Section 6] other than the new version uses
WTBStrat at Line 11, rather than WhitStrat. The argument is then identical to
that of [26, Proposition 6.7], except we employ the more general result of
Proposition 2.9 in place of [26, Proposition 6.6]. ∎

##  3\. Real Stratifications

Let $\mathbb{R}[x_{1},\ldots,x_{n}]$ be the ring of real polynomials in $n$
indeterminates, and fix a radical ideal $I$ of this ring. By definition, the
vanishing locus $X:=\mathbf{V}(I)$ constitutes a real algebraic subvariety of
$\mathbb{R}^{n}$. Since $\mathbb{R}[x_{1},\ldots,x_{n}]$ is a subring of
$\mathbb{C}[x_{1},\ldots,x_{n}]$, the ideal $I$ similarly defines a complex
algebraic subvariety $\mathbf{V}_{\mathbb{C}}(I)$ of $\mathbb{C}^{n}$, which
we will denote by $X(\mathbb{C})$. Let $X_{\rm reg}$ denote the manifold of
smooth points in $X$. In this section $\dim_{\mathbb{R}}(X)$ will denote the
dimension of manifold $X_{\rm reg}$ and $\dim_{\mathbb{C}}(X(\mathbb{C}))$
will denote the dimension of the manifold $(X(\mathbb{C}))_{\rm reg}$.

###  3.1. Real Varieties

Our immediate goal here is to show that certain Whitney stratifications of
$X(\mathbb{C})$ induce Whitney stratifications of $X$. We let
$\iota:\mathbb{R}^{n}\hookrightarrow\mathbb{C}^{n}$ be the embedding of real
points in complex Euclidean space.

######  Lemma 3.1.

Let $X\subset\mathbb{R}^{n}$ be a real algebraic variety.

  1. (1)

The embedding $\iota$ identifies $X$ with the real points of $X(\mathbb{C})$.

  2. (2)

Assume that $\dim_{\mathbb{R}}X$ equals $\dim_{\mathbb{C}}X(\mathbb{C})$. If
$\iota(p)$ is a smooth point of $X(\mathbb{C})$ for some $p\in X$, then $p$ is
a smooth point of $X$.

###### Proof.

The first assertion is a tautology. Turning to the second assertion, set
$d:=\dim_{\mathbb{C}}X(\mathbb{C})=\dim_{\mathbb{R}}X$. Since the roots of
real polynomials occur in complex conjugate pairs, the variety $X(\mathbb{C})$
is invariant under complex conjugation and $\iota(X)$ equals the fixed point
set of this conjugation. Noting that $\iota(p)$ is a smooth point by
assumption, the tangent space $T_{\iota(p)}X(\mathbb{C})$ exists and has
complex dimension $d$; this tangent space also inherits invariance under
complex conjugation. Thus, $T_{\iota(p)}X(\mathbb{C})$ is the complexification
of a real $d$-dimensional vector space $V$ whose elements consist of all real
tangent vectors at $\iota(p)$; this $V$ is evidently isomorphic to $T_{p}X$,
as desired. ∎

Every finite descending chain $I_{\bullet}$ of radical $R$-ideals

$I_{0}\rhd I_{1}\rhd\cdots\rhd I_{m}=I$

produces an ascending flag $X_{\bullet}:=\mathbf{V}(I_{\bullet})$ of
subvarieties of $X$:

$X_{0}\subset X_{1}\subset\cdots\subset X_{m}=X.$

The next result shows that successive differences of $X_{\bullet}$ inherit a
smooth manifold structure from the successive differences of
$X_{\bullet}(\mathbb{C})$.

######  Proposition 3.2.

Let $W\subset Z$ be a pair of real algebraic varieties in $\mathbb{R}^{n}$. If
the difference $Z(\mathbb{C})-W(\mathbb{C})$ is either empty or a smooth
$i$-dimensional complex manifold, then $M:=(Z-W)$ is either empty or a smooth
$i$-dimensional real manifold.

###### Proof.

There are two cases to consider — either the image $\iota(Z)$ lies entirely
within the singular locus $Z(\mathbb{C})_{\text{sing}}$, or there exists some
$p\in M$ with $\iota(p)\in Z(\mathbb{C})_{\text{reg}}$. In the first case,
since $Z(\mathbb{C})-W(\mathbb{C})$ is smooth, we know that
$Z(\mathbb{C})_{\text{sing}}$ lies entirely within $W(\mathbb{C})$ and hence
that $\iota(Z)\subset\iota(W)$; but since we have assumed $W\subset Z$, we
must have $W=Z$, whence $M$ is empty. On the other hand, let $p$ be a point in
$(Z-W)$ for which $\iota(p)$ is a smooth point of $Z(\mathbb{C})$. We may
safely assume that the generating ideal of $Z$ is prime in
$\mathbb{C}[x_{1},\ldots,x_{n}]$ by passing to the irreducible component which
contains $\iota(p)$. It now follows from [36, Theorem 12.6.1] or [24, Theorem
2.3] that $(Z-W)$ has dimension $i$. Finally, Lemma 3.1 ensures that $(Z-W)$
is a smooth real $i$-manifold. ∎

It follows from the above result that if $X_{\bullet}(\mathbb{C})$ is a
Whitney stratification of $X(\mathbb{C})$, then the successive differences of
$X_{\bullet}$ are either empty or smooth manifolds of the expected dimension.
We show below these successive differences also satisfy Condition (B).

######  Theorem 3.3.

Let $I_{\bullet}$ be a descending chain of radical ideals in
$\mathbb{R}[x_{1},\ldots,x_{n}]$. If the flag
$X_{\bullet}(\mathbb{C}):=\mathbf{V}_{\mathbb{C}}(I_{\bullet})$ constitutes a
Whitney stratification of $X(\mathbb{C})$, then the corresponding flag
$X_{\bullet}:=\mathbf{V}(I_{\bullet})$ yields a Whitney stratification of $X$.

###### Proof.

Consider a non-empty connected component $M\subset S_{i}$, and let $V\subset
X_{i}$ be the irreducible component which contains $M$. Similarly, let
$W\subset X_{i}(\mathbb{C})$ be the irreducible component which contains
$\iota(M)$ and define $M_{\mathbb{C}}:=W-X_{i-1}(\mathbb{C})$. We note that
$\iota(M)$ forms an open subset of $M_{\mathbb{C}}$, which must in turn by an
$i$-stratum of $X(\mathbb{C})$. Similarly, consider a nonempty connected
$N\subset S_{j}$ with $i>j$ and analogously define $N_{\mathbb{C}}\subset
X_{j}(\mathbb{C})$. We will show that the pair $(M,N)$ satisfies Condition
(B). To this end, consider a point $q\in N$ along with sequences
${\left\\{{p_{k}}\right\\}}\subset M$ and ${\left\\{{q_{k}}\right\\}}\subset
N$ which converge to $q$. Letting $\ell_{k}$ denote the secant line
$[p_{k},q_{k}]$ and $T_{k}$ the tangent plane $T_{p_{k}}M$, we assume further
that the limits $\ell=\lim\ell_{k}$ and $T=\lim T_{k}$ both exist.

Let $\ell_{k}(\mathbb{C})$ be the secant line $[\iota(p_{k}),\iota(q_{k})]$ in
$\mathbb{C}^{n}$ and $T_{k}(\mathbb{C})$ the tangent space
$T_{\iota(p_{k})}M_{\mathbb{C}}$. Since $\iota(p_{k})$ and $\iota(q_{k})$ are
real points for all $k$, the the linear equations defining both
$\ell_{k}(\mathbb{C})$ and $T_{k}(\mathbb{C})$ as varieties are exactly the
same as those defining $\ell_{k}$ and $T_{k}$, respectively. Thus, the limits
$\ell(\mathbb{C})$ and $T(\mathbb{C})$ both exist because the corresponding
real limits exist – one may view these as limits of real sequences inside a
complex Grassmannian – and they are defined by the same algebraic equations as
their counterparts $\ell$ and $T$. By definition of secant lines, the image
$\iota(w)$ of any $w\in\ell$ is a real point of $\ell(\mathbb{C})$. Since the
pair $(M_{\mathbb{C}},N_{\mathbb{C}})$ satisfies Condition (B) by assumption,
we know that $\ell(\mathbb{C})\subset T(\mathbb{C})$, whence $\iota(w)$ must
be a real point of $T(\mathbb{C})$. Since $\iota(M)$ is an open subset of
$M_{\mathbb{C}}$, we have
$T_{\iota(p_{k})}M_{\mathbb{C}}=T_{\iota(p_{k})}\iota(M)$ for all $k$; and by
the proof of Lemma 3.1, the real points of $T_{\iota(p_{k})}\iota(M)$ are
identified with $T_{q_{k}}N$. Thus, $\iota(T)$ contains all the real points of
$T(\mathbb{C})$, including $\iota(w)$. Since $\iota$ is injective, we have
$w\in T$ as desired. ∎

######  Corollary 3.4.

Let $X$ be an algebraic variety in $\mathbb{R}^{n}$. The WhitStrat algorithm
from Section 2.1, when applied to $X(\mathbb{C})$, produces a Whitney
stratification of $X$.

###### Proof.

The WhitStrat algorithm performs three types of operations: ideal addition,
Gröbner basis computation, and primary decomposition. Each of these operations
leaves the coefficient field of all intermediate polynomials unchanged. ∎

######  Remark 3.5.

A detailed complexity analysis of our Whitney stratification algorithm for
complex varieties is given in [26, Section 7]. The main cost in our
stratification algorithms for real varieties , both for maps and for spaces,
is the computation of Whitney stratifications of the associated complex
varieties. Hence the worst case complexity of all algorithms presented here is
roughly equivalent to that presented in [26, Section 7], that is to say the
complexity is roughly equivalent to that of Gröbner basis computation.

###  3.2. Real Algebraic Morphisms

Consider algebraic varieties $X\subset\mathbb{R}^{n}$ and
$Y\subset\mathbb{R}^{m}$, and let $f:X\to Y$ be an algebraic morphism. We
recall that this amounts to an $m$-tuple of real polynomials

$\Big{(}f_{1}(x_{1},\ldots,x_{n}),\leavevmode\nobreak\
f_{2}(x_{1},\ldots,x_{n}),\leavevmode\nobreak\ \ldots,\leavevmode\nobreak\
f_{m}(x_{1},\ldots,x_{n})\Big{)}$

whose evaluation at a point of $X$ yields a point of $Y$. Since each $f_{i}$
is automatically a complex polynomial, there is an evident morphism
$f_{\mathbb{C}}:X(\mathbb{C})\to Y(\mathbb{C})$ of complex algebraic
varieties. Let $I_{\bullet}$ and $J_{\bullet}$ be descending chains of radical
ideals in $\mathbb{R}[x_{1},\ldots,x_{n}]$ and
$\mathbb{R}[y_{1},\ldots,y_{m}]$ respectively so that
$X_{\bullet}(\mathbb{C}):=\mathbf{V}_{\mathbb{C}}(I_{\bullet})$ and
$Y_{\bullet}(\mathbb{C}):=\mathbf{V}_{\mathbb{C}}(J_{\bullet})$ constitute
Whitney stratifications of $X(\mathbb{C})$ and $Y(\mathbb{C})$ respectively.
It follows from Theorem 3.3 that $X_{\bullet}:=\mathbf{V}(I_{\bullet})$ is a
Whitney stratification of $X$ while $Y_{\bullet}:=\mathbf{V}(J_{\bullet})$ is
a Whitney stratification of $Y$.

######  Theorem 3.6.

If $f_{\mathbb{C}}$ is stratified with respect to $X_{\bullet}(\mathbb{C})$
and $Y_{\bullet}(\mathbb{C})$, then $f$ is stratified with respect to
$X_{\bullet}$ and $Y_{\bullet}$.

###### Proof.

Let $M\subset X$ be a nonempty connected component of the $i$-stratum
$X_{i}-X_{i-1}$, and let $M_{\mathbb{C}}$ be the $i$-stratum of
$X_{\bullet}(\mathbb{C})$ which contains $\iota(M)$. By definition, the image
$f_{\mathbb{C}}(M_{\mathbb{C}})$ contains $f(M)$ in its locus of real points.
Since $f_{\mathbb{C}}$ is stratified with respect to $X_{\bullet}(\mathbb{C})$
and $Y_{\bullet}(\mathbb{C})$, the first requirement of Definition 2.4
guarantees the existence of a single stratum $N_{\mathbb{C}}\subset Y$ which
contains $f_{\mathbb{C}}(M_{\mathbb{C}})$. Thus, $f(M)$ lies in the locus of
real points of $N_{\mathbb{C}}$. Letting $N$ denote the stratum of
$Y_{\bullet}$ corresponding to $N_{\mathbb{C}}$, we know that the real locus
of $N_{\mathbb{C}}$ equals $N$, whence we obtain $f(M)\subset N$ and it
remains to show that the restriction of $f$ to $M$ yields a submersion. Let
$x$ be any point of $M$, and note that $\iota(x)$ lies in $M_{\mathbb{C}}$.
Since $f_{\mathbb{C}}|_{M_{\mathbb{C}}}$ is a submersion, its Jacobian at
$\iota(x)$ is a surjective linear map from the tangent space to
$M_{\mathbb{C}}$ at $\iota(x)$ to the tangent space to $N_{\mathbb{C}}$ at
$f_{\mathbb{C}}\circ\iota(x)$. But by construction, $f_{\mathbb{C}}\circ\iota$
equals $f$. Thus, we have

$\text{rank}_{\mathbb{C}}\left(\text{\bf
J}f_{\mathbb{C}}|_{M_{\mathbb{C}}}(\iota(x))\right)=\dim_{\mathbb{C}}N_{\mathbb{C}}.$

To conclude the argument, we note that the derivative arising on the left side
of the above equality may be represented by the Jacobian matrix of $f$ at $x$,
and the rank of this matrix is preserved under field extension to
$\mathbb{C}$. On the other hand, by Proposition 3.2 we know that the complex
dimension of $N_{\mathbb{C}}$ equals the real dimension of $N$. Thus, our
equality becomes

$\text{rank}_{\mathbb{R}}\left(\text{\bf
J}f|_{M}(x)\right)=\dim_{\mathbb{R}}N,$

as desired. ∎

Assume that a morphism $f:X\to Y$ has been stratified as described in Theorem
3.6. It is readily checked that the image $f(\overline{M})$ of the closure of
a stratum $M\subset X$ is not an algebraic subvariety of $Y$ in general — the
best that one can expect is that $f(\overline{M})$ will be semialgebraic. It
is important to note, in the context of the above theorem, that we do not
obtain semialgebraic descriptions of such images.

###  3.3. Dominant Morphisms between Equidimensional Varieties

Let $X\subset\mathbb{K}^{n}$ and $Y\subset\mathbb{K}^{m}$ be algebraic
varieties defined by ideals $I_{X}$ and $I_{Y}$ over a field
$\mathbb{K}\in{\left\\{{\mathbb{R},\mathbb{C}}\right\\}}$. Let $\mathbb{K}[X]$
denote the coordinate ring $\mathbb{K}[x_{1},\ldots,x_{n}]/I_{X}$ and
similarly for $Y$; any morphism of varieties $f:X\to Y$ canonically induces a
contravariant ring homomorphism $f^{*}:\mathbb{K}[Y]\to\mathbb{K}[X]$.

######  Definition 3.7.

Let $f:X\to Y$ be a morphism of algebraic varieties over
$\mathbb{K}\in{\left\\{{\mathbb{R},\mathbb{C}}\right\\}}$.

  1. (1)

we say that $f$ is dominant if $f^{*}$ is a monomorphism (or equivalently, if
the image $f(X)$ is dense in $Y$).

  2. (2)

we say that $f$ is finite if it is dominant, and moreover, if $f^{*}$ gives
$\mathbb{K}[X]$ the structure of an integral extension of $\mathbb{K}[Y]$.

It is a classical result [25, Exercise II.4.1] that if $f:X\to Y$ is finite in
the above sense, then it is also a proper map for any field (see Remark 2.5
for the significance of this result in our context). Over
$\mathbb{K}=\mathbb{C}$, a dominant morphism is finite if and only if it is
proper.

Throughout this section, $f:X\to Y$ will denote a morphism between real
algebraic varieties of the same dimension $d$; we will further require that
the map $f_{\mathbb{C}}:X(\mathbb{C})\to Y(\mathbb{C})$ is dominant and that
$\dim_{\mathbb{C}}X(\mathbb{C})=\dim_{\mathbb{C}}Y(\mathbb{C})=d$.

######  Definition 3.8.

The Jelonek set of $f$ is the subset $\mathbf{Jel}(f)\subset Y(\mathbb{C})$
consisting of all points $y$ for which there exists a sequence
${\left\\{{x_{n}}\right\\}}\subset X(\mathbb{C})$ satisfying both

$\lim_{n\to\infty}|x_{n}|=\infty\quad\text{ and
}\quad\lim_{n\to\infty}f_{\mathbb{C}}(x_{n})=y.$

It is shown in [29] that $\mathbf{Jel}(f)$ is either empty or an algebraic
hypersurface of $Y(\mathbb{C})$; a Gröbner basis algorithm for computing the
Jelonek set is given in [41]. It follows from this algorithm that if the
Jelonek set is non-empty, then it is defined by a polynomial with real
coefficients. Finally, it is shown in [29] that $\mathbf{Jel}(f)$ is precisely
the locus of points at which $f$ fails to be finite. Thus, if we define

$V(\mathbb{C}):=\mathbf{Jel}(f)\quad\text{and}\quad
W(\mathbb{C}):=\overline{f^{-1}(V)},$

then the restriction of $f$ forms a proper map
$(X(\mathbb{C})-W(\mathbb{C}))\to(Y(\mathbb{C})-V(\mathbb{C}))$ — see [30,
Proposition 6.1] for details. Note that the polynomials defining
$V(\mathbb{C})$ and $W(\mathbb{C})$ are real; take $V$ to be the real zero set
of the polynomials defining $V(\mathbb{C})$, and similarly let $W$ be the real
zero set of the polynomials defining $W(\mathbb{C})$. It follows immediately
that the restriction of $f$ to the difference $(X-W)$ constitutes a proper map
to the difference $(Y-V)$.

######  Definition 3.9.

The Jelonek flag of $f:X\to Y$ is a pair $(W_{\bullet},V_{\bullet})$ of flags,
both of length $d=\dim X=\dim Y$:

$\displaystyle\emptyset=W_{-1}\subset W_{0}\subset\cdots\subset W_{d}=X$
$\displaystyle\emptyset=V_{-1}\subset V_{0}\subset\cdots\subset V_{d}=Y,$

defined via reverse-induction on $i\in{\left\\{{d-1,d-2,\ldots,1,0}\right\\}}$
as follows. Starting with $V_{d-1}$ as the real points of $\mathbf{Jel}(f)$,
we

  1. (1)

let $W_{i}$ be $\overline{f^{-1}(V_{i})}$, and

  2. (2)

let $V_{i-1}$ be the real points in $\mathbf{Jel}(f|_{W_{i}}:W_{i}\to V_{i})$.

By construction of the Jelonek flag, at each $i$ we have the following
alternative:

  1. (1)

if $V_{i}(\mathbb{C})$ is nonempty, then $\dim
V_{i}(\mathbb{C})=W_{i}(\mathbb{C})=i$ and the restriction of $f$ forms a
proper map ${(V_{i}-V_{i-1})\to(W_{i}-W_{i-1})}$; otherwise,

  2. (2)

if $V_{i}(\mathbb{C})$ is empty, then $f|_{W_{i}}:W_{i}\to V_{i}$ is not
dominant; on the other hand, $f|_{W_{i-1}}$ is dominant, but with $\dim
W_{i-1}(\mathbb{C})>\dim V_{i-1}(\mathbb{C})$.

######  Theorem 3.10.

Let $(W_{\bullet},V_{\bullet})$ be the Jelonek flag of $f:X\to Y$. Assume that
$X_{\bullet}$ is a Whitney stratification of $X$ subordinate $W_{\bullet}$ and
that $Y_{\bullet}$ is a Whitney stratification of $Y$ subordinate to
$V_{\bullet}$ such that $f$ is stratified with respect to $X_{\bullet}$ and
$Y_{\bullet}$ (in the sense of Definition 2.4). Whenever $\dim V_{i}=\dim
W_{i}$ holds, we have that for every $Y_{\bullet}$-stratum $R\subset Y$ with
$R\subset V_{i}-V_{i-1}$, the map $f|_{f^{-1}(R)}:f^{-1}(R)\to R$ is a locally
trivial fiber bundle.

###### Proof.

Since the stratification $Y_{\bullet}$ of $Y$ is subordinate to $V_{\bullet}$,
for each stratum $R\subset Y$ we have that $R\subset V_{i}-V_{i-1}$ for some
$i$, and also since $X_{\bullet}$ is subordinate to $W_{\bullet}$ we also have
$f^{-1}(R)\subset W_{i}-W_{i-1}$. If $\dim(V_{i})=\dim(W_{i})$ holds, then the
map $f:(W_{i}-W_{i-1})\to(V_{i}-V_{i-1})$ is proper. An appeal to the
semialgebraic version of Thom’s first isotopy lemma [11, Theorem 1] achieves
the desired result. ∎

##  4\. Full Semialgebraic Stratifications

A (basic, closed) semialgebraic set is any subset $B\subset\mathbb{R}^{n}$
which can be expressed as an intersection of the form $B:=X\cap C$ where $X$
is a real algebraic subvariety of $\mathbb{R}^{n}$, while the set $C$, called
an inequality locus, is given as follows:

$\displaystyle C:={\left\\{{x\in\mathbb{R}^{n}\mid g_{i}(x)\geq 0\text{ for
}0\leq i\leq k}\right\\}}.$ (6)

Here the $g_{i}$’s are a finite collection of polynomials in
$\mathbb{R}[x_{1},\ldots,x_{n}]$. By convention, when the number of
inequalities $k$ equals zero, we have $C=\mathbb{R}^{n}$. Thus, every
algebraic variety is automatically a semialgebraic set in the above sense. The
sets $X$ and $C$ are not uniquely determined for a given $B$ in general — we
may, for instance, safely remove any polynomial generator
$f:\mathbb{R}^{n}\to\mathbb{R}$ from the defining ideal of $X$ while adding
$f\geq 0$ and $-f\geq 0$ to the inequality locus. It is therefore customary to
omit $X$ entirely and simply define $B$ as the set of points which satisfy a
collection of polynomial inequalities. We find it convenient to write $B=X\cap
C$ here because this allows us to highlight a relevant sub-class of
semialgebraic sets.

######  Definition 4.1.

A semialgebraic set $B\subset\mathbb{R}^{n}$ is called full if it admits an
inequality locus $C$ of the form (6), with the additional requirement that its
subset

$C^{\circ}:={\left\\{{x\in\mathbb{R}^{n}\mid g_{i}(x)>0\text{ for }0\leq i\leq
k}\right\\}}$

is an $n$-dimensional smooth manifold whose closure equals $C$.

The following example highlights an important class of full semialgebraic sets
which arise in the Morse theoretic study of complex analytic varieties — see
[22, II.2].

######  Example 4.2.

Whitney showed in [42] that every complex analytic variety
$W\subset\mathbb{C}^{n}$ admits a Whitney stratification $W_{\bullet}$ where
each intermediate $W_{i}$ is a complex analytic subvariety. Associated to each
$i$-stratum $M\subset W_{i}-W_{i-1}$ is a stratified space
$\mathscr{L}=\mathscr{L}_{M}$, which is called the complex link of $M$ and
defined as follows. Consider a point $p\in M$ and let $A\subset\mathbb{C}^{n}$
be a generic $(n-i)$-dimensional affine subspace which intersects $W$
transversely at a point $p\in M$. Let $B_{\epsilon}(p)$ denote the disk
containing all points within a sufficiently small radius $\epsilon>0$ around
$p$ with respect to the standard euclidean distance in $\mathbb{C}^{n}$.
Finally, let $\pi:A\to\mathbb{C}$ be a generic linear form sending $p$ to
zero. For some positive $\delta\ll\epsilon$, one defines

$\mathscr{L}_{M}:=W\cap B_{\epsilon}(p)\cap{\left\\{{\pi=\delta}\right\\}}.$

The stratified homeomorphism type of $\mathscr{L}_{M}$ depends only on the
stratum $M$, and not on the auxiliary choices of $p,A,\epsilon,\pi$ and
$\delta$. Complex links provide normal Morse data for critical points of
stratified Morse functions $f:W\to\mathbb{R}$. Although such a
$\mathscr{L}_{M}$ will not be a complex (or even real) variety in general, it
is always a full semialgebraic subset of the affine space
${\left\\{{\pi=\delta}\right\\}}$. In particular, its inequality locus is the
disk $B_{\epsilon}(p)\cap{\left\\{{\pi=\delta}\right\\}}$.

Given such an inequality locus $C$ of a full semialgebraic set, we call
$C^{\circ}$ its interior and define its boundary as the difference

$\partial C:=C-C^{\circ}.$

This boundary is a semialgebraic subset of the real algebraic variety

$Y_{C}:=\mathbf{V}\left(\prod_{1}^{k}g_{i}\right).$ (7)

We adopt the usual convention that the product over the empty set equals $1$,
which forces $\partial C=Y_{C}=\varnothing$ when $k=0$.

######  Example 4.3.

Below is a toy example of a full semialgebraic set $B=X\cap C$ inside
$\mathbb{R}^{2}$. Here $X$ is the union of red parabolas $P_{1}$ and $P_{2}$
while $C$ is the region bounded by the black lines $L_{1},L_{2},L_{3}$ and the
black parabola $P_{3}$:

The interior $C^{\circ}$ has been shaded gray, so $B$ consists of that part of
$P_{1}\cup P_{2}$ which lies within the closure of the gray region. The
variety $Y_{C}$ is the union of curves $L_{1},L_{2},L_{3}$ and $P_{3}$. The
boundary $\partial C$ consists of the four highlighted points which lie on
this union of curves.

Our next result establishes that every full semialgebraic set $B=X\cap C$
inherits a Whitney stratification from Whitney stratifications of the real
algebraic varieties $X$ and $X\cap Y_{C}$. (We recall for the reader’s
convenience that flag-subordinate stratifications have been described in
Section 2.2).

######  Theorem 4.4.

Let $B=X\cap C$ be a full semialgebraic set, with $Y_{C}$ as in (7), and let
$X_{\bullet}$ be a Whitney stratification of $X$. If $Y_{\bullet}$ is a
Whitney stratification of $X\cap Y_{C}$ which is subordinate to the flag
$X_{\bullet}\cap Y_{C}$, then setting

$B_{i}:=(X_{i}\cup Y_{i})\cap C$

produces a Whitney stratification of $B$.

###### Proof.

Since $B$ is full, we know that the interior $C^{\circ}$ of its inequality
locus is a smooth open $n$-dimensional submanifold of $\mathbb{R}^{n}$.
Therefore, the intersections $X_{i}\cap C^{\circ}$ form a Whitney
stratification $X^{\prime}_{\bullet}$ of $X\cap C^{\circ}$. Let
$Y^{\prime}_{\bullet}$ be the subset of $Y_{\bullet}$-strata which intersect
$\partial C$. Since $C$ is the disjoint union of $C^{\circ}$ and $\partial C$,
it follows that the union of $X^{\prime}_{\bullet}$-strata and
$Y^{\prime}_{\bullet}$-strata partitions $B$. It remains to check that
Condition (B) holds for those strata pairs $(M,N)$ of this union for which $N$
intersects the closure of $M$. There are now three cases to consider, of which
the two easy ones are handled as follows:

  1. (1)

if both $M$ and $N$ are strata of $X^{\prime}_{\bullet}$, then Condition (B)
holds because both are full-dimensional open subsets of $X_{\bullet}$-strata
by construction, and $X_{\bullet}$ is assumed to be a Whitney stratification.

  2. (2)

if $M$ is a $Y^{\prime}_{\bullet}$-stratum, then the fact that $N$ intersects
the closure of $M$ forces $N$ to be contained in $X\cap\partial C$, since both
$X$ and $\partial C$ are closed subsets of $\mathbb{R}^{n}$. Thus, $N$ must
also be a $Y^{\prime}_{\bullet}$-stratum in which case Condition (B) holds
because $Y^{\prime}_{\bullet}$ is Whitney.

Turning now to the third case, assume that $M$ is an
$X^{\prime}_{\bullet}$-stratum and $N$ is a $Y^{\prime}_{\bullet}$-stratum. By
construction, $M$ must be (a connected component of) the intersection
$M_{*}\cap C^{\circ}$ for some $X_{\bullet}$-stratum $M_{*}$. Since
$C^{\circ}$ is $n$-dimensional, the tangent spaces $T_{x}M$ and $T_{x}M_{*}$
coincide for every $x$ in $M$. Fix a point $p\in N$, and let $N_{*}$ be the
unique $X_{\bullet}$-stratum containing $p$ in its interior. Since
$Y_{\bullet}$ is chosen subordinate to $X_{\bullet}\cap Y_{C}$, the
$Y_{\bullet}$-strata are refinements of $X_{\bullet}$-strata, so $N$ must be
obtained by removing some (possibly empty) set from $N^{*}\cap\partial C$. It
follows that $N$ is a subset of $N^{*}$ in a small ball around $p$. Finally,
$(M,N)$ must satisfy Condition (B) at $p$ because $(M_{*},N_{*})$ satisfy
Condition (B) at $p$. ∎

The stratifications obtained in Theorem 4.4 provide a complete description of
the flag $B_{i}$. Using the techniques of [24, 35, 40], one can perform
various fundamental algorithmic tasks involving such strata. These include
testing whether the $i$-stratum $B_{i}-B_{i-1}$ is empty for each $i$, and
sampling points from the non-empty strata.

######  Remark 4.5.

Using Theorem 4.4 in practice on a full semialgebraic set $B=X\cap C$ requires
constructing a stratification of the real variety $X\cap Y_{C}$; this is
somewhat unsatisfactory from an efficiency perspective, since $X$ and $Y_{C}$
may intersect far away from $B$ — returning to Example 4.3, note that both
$P_{1}$ and $P_{2}$ will intersect $L_{2}$ at points far from $B$. We are not
aware of any existing technique which can easily overcome such suboptimality.

##  5\. Solving the Real Root Classification Problem

As noted in the Introduction, the real root classification problem, that is
the problem of understanding how the number of real roots of a parametric
polynomial system depend on the parameters, appears in a wide variety of
applied contexts and as such has been extensively studied in computational
algebraic geometry. The most recent work in this area seems to be [34], which
develops specialized techniques to solve the root classification problem
without the appeal to a cylindrical algebraic decomposition algorithm. Some
other works in this area include [8, 9, 20, 32], all of which rely on the
computation of a cylindrical algebraic decomposition to some greater or lesser
degree; a detailed description of previous work on this problem is also given
in [34, §1.2].

In this section, as an application of the general purpose algebraic map
stratification methods we have developed in the previous Sections, we explore
how our computational stratification machinery can be used to solve the real
root classification problem. To this end, fix integers $m,n\geq 1$ and define
the subset

$P\subset\left(\mathbb{R}[c_{1},\ldots,c_{m}]\right)[x_{1},\ldots,x_{n}].$

consisting of all polynomials which have the form

$f(x,c)=\sum_{j=1}^{k}c_{j}\cdot x_{1}^{a_{1,j}}\cdots x_{n}^{a_{n,j}}+g(x),$

where $k\leq m$, ${\left\\{{a_{i,j}}\right\\}}$ is some $k\times n$ matrix of
non-negative integers and $g(x)$ is a polynomial in
$\mathbb{R}[x_{1},\dots,x_{n}]$.

######  Definition 5.1.

Consider polynomials $f_{1}(x,c),\dots,f_{n}(x,c)$ in $P$, and suppose that
the system

${\left\\{{f_{i}(x,c)=0\mid 1\leq i\leq n}\right\\}}$ (8)

has finitely many complex solutions in $\mathbb{C}^{n}$, for a generically
chosen parameter $c\in\mathbb{R}^{m}$. The real root classification problem
seeks a decomposition $\mathbb{R}^{m}=\coprod_{j}M_{j}$ so that either the
number of real solutions to ${\left\\{{f_{i}(x,c^{*})=0}\right\\}}$ is locally
constant across $c^{*}\in M_{j}$, or the system has infinitely many complex
solutions.

Henceforth, we treat the polynomials $f_{1},\dots,f_{n}$ in $P$ as polynomials
in $\mathbb{R}[x,c]$ and consider the variety
$X=\mathbf{V}(f_{1},\dots,f_{n})$ in $\mathbb{R}^{n}\times\mathbb{R}^{m}$.
Note that $\dim(X)=m$ by the assumption that for a fixed generic parameter
value the system (8) has finitely many complex solutions. Hence, if we take
$\pi:\mathbb{R}^{n}\times\mathbb{R}^{m}\to\mathbb{R}^{m}$ to be the coordinate
projection onto the last $m$ coordinates, then the resulting map
$\pi:X\to\mathbb{R}^{m}$ is dominant and $\dim(X)=m$. Thus, $\pi$ is a
dominant map between varities of the same dimension. Note that for a point
$q\in Y$ the fiber $\pi^{-1}(q)$ consists of a set of points of the form
$(x,q)$ in $\mathbb{R}^{n}\times\mathbb{R}^{m}$ where the $x$ values are
exactly the solutions in $\mathbb{R}^{n}$ to the system (8) for the choice of
parameters $c=q$; also note that for generic $q$ the set $\pi^{-1}(q)$ is
finite.

######  Theorem 5.2.

Set $Y=\mathbb{R}^{m}$ and consider the dominant projection map $\pi:X\to Y$
defined above. Let $(W_{\bullet},V_{\bullet})$ be the Jelonek flag of $\pi$.
If $(X_{\bullet}$, $Y_{\bullet})$ is a stratification of $\pi$ in the sense of
Definition 2.4, with $X_{\bullet}$ subordinate to $W_{\bullet}$ and
$Y_{\bullet}$ subordinate to $V_{\bullet}$, then for any $Y_{\bullet}$-stratum
$N$, we have that either the number of real points in $\pi^{-1}(q)$ is fixed
and independent of $q$ or $\pi^{-1}(q)$ has infinitely many complex points.

###### Proof.

Since $Y_{\bullet}$ is subordinate to $V_{\bullet}$ we have that
$N\subset(V_{i}-V_{i-1})$ for some $i$. There are two cases to consider:

  1. (1)

if $\pi:W_{i}\to V_{i}$ is dominant with $\dim(W_{i})>\dim(V_{i})$, then we
have $\dim(f^{-1}(Z))>\dim(Z)$ for any subvariety $Z\subset V_{i}$. Hence, for
any $q\in N$ the fiber $f^{-1}(q)$ consists of infinitely many complex points.

  2. (2)

if $\dim(V_{i})=\dim(W_{i})$, then the conclusion follows immediately from
Theorem 3.10 since the fibers are zero dimensional and the number of real
points is exactly the number of connected components of the fiber of the real
map.

Thus, any Jelonek-subordinate stratification of $\pi:X\to Y$ directly solves
the real root classification problem ∎

### An Example

We conclude with a standard example of real root classification arising from
dominant map stratification; a simpler example is given in the Introduction.

Consider the quadratic equation:

$ax^{2}+bx+c=0$ (9)

where we think of $a,b,c$ as real parameters. We wish to classify its real
solutions, to do this we consider the variety $X=\mathbf{V}(ax^{2}+bx+c)$ in
$\mathbb{R}^{4}$ and the projection map $\pi:\mathbb{R}^{4}\to\mathbb{R}^{3}$
onto $Y=\mathbb{R}^{3}$ specified by $(x,a,b,c)\mapsto(a,b,c)$. A
stratification of $\pi$ as in Theorem 5.2 is given by:

$X_{\bullet}=\mathbf{V}(ax^{2}+bx+c)\supset\left(\mathbf{V}(b^{2}-4ac,\,ax^{2}+bx+c)\cup\mathbf{V}\left(a,\,bx+c\right)\right)\supset\mathbf{V}(a,b,c)$

and

$Y_{\bullet}=\mathbb{R}^{3}\supset\left(\mathbf{V}(b^{2}-4ac)\cup\mathbf{V}(a)\right)\supset\mathbf{V}(a,b)\supset\mathbf{V}(a,b,c).$

The number of real solutions of $ax^{2}+bx+c=0$ is locally constant on every
stratum of $Y$.

Figure 3. The real surface $\mathbf{V}(b^{2}-4ac)\cup\mathbf{V}\left(a\right)$
bounding the connected components of $M_{3}$.

First consider the strata of dimension $3$ arising from
$M_{3}=\mathbb{R}^{3}-\left(\mathbf{V}(b^{2}-4ac)\cup\mathbf{V}\left(a\right)\right)$;
$M_{3}$ has 4 connected components, one representative point of each of these
is: $(-1,1,1)\in S_{1}$, $(-1,1,-1)\in S_{2}$, $(1,1,1)\in S_{3}$,
$(1,1,-1)\in S_{4}$. The boundary of the 4 connected components of $M_{3}$ is
illustrated below in Figure 3. Using the representative points we see that (9)
has two real solutions for all coefficients $(a,b,c)\in S_{1}$ and $(a,b,c)\in
S_{4}$, and no real solutions for $(a,b,c)\in S_{2}$ and for $(a,b,c)\in
S_{3}$. Note that our algorithm does not produce the semi-algebraic
description of the sets $S_{i}$, e.g. we do not compute that
$S_{1}=\\{(a,b,c)\in\mathbb{R}^{3}\;|\;b^{2}-4ac>0,\;a<0\\}$, even though in
this case it is easy to deduce from the description above. Instead we only
sample points from them and determine the number of solutions to the original
system in a given region of parameter space.

Next we consider the connected strata arising from
$M_{2}=\left(\mathbf{V}(b^{2}-4ac)\cup\mathbf{V}\left(a\right)\right)-\mathbf{V}(a,b)$,
this again has 4 connected components, two arising from
$\mathbf{V}(b^{2}-4ac)-\mathbf{V}(a,b)$, one of which has $c\geq 0$ and one
$c\leq 0$, and two from $\mathbf{V}(a)-\mathbf{V}(a,b)$, one representative
from each of these is: $(1,2,1)\in T_{1}$, $(-1,2,-1)\in T_{2}$, $(0,1,1)\in
T_{3}$, $(0,-1,1)\in T_{4}$. We see that (9) has one real solution for all
coefficients $(a,b,c)\in T_{i}$, for $i=1,\dots,4$.

Next we consider the connected strata arising from
$M_{1}=\mathbf{V}(a,b)-\mathbf{V}(a,b,c)$. This has two connected components,
one representative from each of these is: $(0,0,1)\in Z_{1}$, $(0,0,-1)\in
Z_{2}$ and (9) has no real solutions for all coefficients $(a,b,c)$ in both
$Z_{1}$ and $Z_{2}$.

Finally we have the closed stratum $\mathbf{V}(a,b,c)$ which is a single point
and the corresponding system (9) has infinitely many solutions.

## References

  * [1] L. Alberti, B. Mourrain, and J.-P. Técourt.  Isotopic triangulation of a real algebraic surface.  Journal of Symbolic Computation, 44(9):1291–1310, 2009.
  * [2] Y. Ameur, M. Helmer, and F. Tellander.  On the uniqueness problem for quadrature domains.  Computational Methods and Function Theory, 21(3):473–504, 2021\.
  * [3] D. S. Arnon, G. E. Collins, and S. McCallum.  Cylindrical algebraic decomposition I: The basic algorithm.  SIAM Journal on Computing, 13(4):865–877, 1984.
  * [4] B. Bonnard, J.-C. Faugère, A. Jacquemard, M. Safey El Din, and T. Verron.  Determinantal sets, singularities and application to optimal control in medical imagery.  In Proceedings of the ACM on International Symposium on Symbolic and Algebraic Computation, pages 103–110, 2016.
  * [5] J.-P. Brasselet, J. Seade, and T. Suwa.  Vector fields on singular varieties, volume 1987.  Springer Science & Business Media, 2009.
  * [6] C. W. Brown and J. H. Davenport.  The complexity of quantifier elimination and cylindrical algebraic decomposition.  In Proceedings of the 2007 international symposium on Symbolic and algebraic computation, pages 54–60, 2007.
  * [7] B. F. Caviness and J. R. Johnson.  Quantifier elimination and cylindrical algebraic decomposition.  Springer Science & Business Media, 2012.
  * [8] C. Chen, O. Golubitsky, F. Lemaire, M. M. Maza, and W. Pan.  Comprehensive triangular decomposition.  In Computer Algebra in Scientific Computing: 10th International Workshop, CASC 2007, Bonn, Germany, September 16-20, 2007. Proceedings 10, pages 73–101. Springer, 2007.
  * [9] C. Chen and M. M. Maza.  Semi-algebraic description of the equilibria of dynamical systems.  In Computer Algebra in Scientific Computing: 13th International Workshop, CASC 2011, Kassel, Germany, September 5-9, 2011. Proceedings 13, pages 101–125. Springer, 2011.
  * [10] S. Corvez and F. Rouillier.  Using computer algebra tools to classify serial manipulators.  In Automated Deduction in Geometry: 4th International Workshop, ADG 2002, Hagenberg Castle, Austria, September 4-6, 2002. Revised Papers 4, pages 31–43. Springer, 2004.
  * [11] M. Coste and M. Shiota.  Thom’s first isotopy lemma: a semialgebraic version, with uniform bound.  In Real Analytic and Algebraic Geometry: Proceedings of the International Conference, Trento (Italy), September 21-25, 1992, page 83. Walter de Gruyter, 1995.
  * [12] D. Cox, J. Little, and D. OShea.  Ideals, varieties, and algorithms: an introduction to computational algebraic geometry and commutative algebra.  Springer Science & Business Media, 2015.
  * [13] W. Decker, G.-M. Greuel, and G. Pfister.  Primary decomposition: algorithms and comparisons.  In Algorithmic algebra and number theory, pages 187–220. Springer, 1999.
  * [14] A. Dickenstein, M. P. Millán, A. Shiu, and X. Tang.  Multistationarity in structured reaction networks.  Bulletin of Mathematical Biology, 81:1527–1581, 2019.
  * [15] D. Eisenbud, C. Huneke, and W. Vasconcelos.  Direct methods for primary decomposition.  Inventiones mathematicae, 110(1):207–235, 1992.
  * [16] M. England and J. H. Davenport.  Experience with heuristics, benchmarks & standards for cylindrical algebraic decomposition.  In CEUR Workshop Proceedings, volume 1804, pages 24–31. CEUR-WS, 2016.
  * [17] J.-C. Faugere.  A new efficient algorithm for computing G röbner bases (F4).  Journal of pure and applied algebra, 139(1-3):61–88, 1999.
  * [18] J.-C. Faugère, G. Moroz, F. Rouillier, and M. S. El Din.  Classification of the perspective-three-point problem, discriminant variety and real solving polynomial systems of inequalities.  In Proceedings of the twenty-first international symposium on Symbolic and algebraic computation, pages 79–86, 2008.
  * [19] E. Feliu and M. Helmer.  Multistationarity and bistability for fewnomial chemical reaction networks.  Bulletin of Mathematical Biology, 81:1089–1121, 2019.
  * [20] J. Gerhard, D. J. Jeffrey, and G. Moroz.  A package for solving parametric polynomial systems.  ACM Communications in Computer Algebra, 43(3/4):61–72, 2010.
  * [21] M. Golubitsky and V. Guillemin.  Stable Mappings and their Singularities.  Number 14 in Graduate Texts in Mathematics. Springer, 1973.
  * [22] M. Goresky and R. MacPherson.  Stratified Morse Theory.  Springer-Verlag, 1988.
  * [23] S. A. Gutnik and V. A. Sarychev.  A symbolic study of the satellite dynamics subject to damping torques.  In Computer Algebra in Scientific Computing: 19th International Workshop, CASC 2017, Beijing, China, September 18-22, 2017, Proceedings 19, pages 167–182. Springer, 2017.
  * [24] K. Harris, J. D. Hauenstein, and A. Szanto.  Smooth points on semi-algebraic sets.  Journal of Symbolic Computation, 116:183–212, 2023.
  * [25] R. Hartshorne.  Varieties of small codimension in Projective space.  Bulletin of the American Mathematical Society, 80(6):1017–1032, 1974.
  * [26] M. Helmer and V. Nanda.  Conormal spaces and Whitney stratifications.  arXiv:2106.14555v4, 2022.
  * [27] M. Helmer and V. Nanda.  Conormal spaces and whitney stratifications.  Foundations of Computational Mathematics, pages 1–36, 2022.
  * [28] M. Helmer and V. Nanda.  Correction to: Conormal spaces and whitney stratifications.  Foundations of Computational Mathematics, pages 1–8, 2023.
  * [29] Z. Jelonek.  Testing sets for properness of polynomial mappings.  Mathematische Annalen, 315(1):1–35, 1999.
  * [30] Z. Jelonek.  Geometry of real polynomial mappings.  Mathematische Zeitschrift, 239(2):321–333, 2002.
  * [31] M. Kashiwara and P. Schapira.  Sheaves on Manifolds.  Number 292 in Grundlehren der math. Wiss. Springer-Verlag, 1990.
  * [32] D. Lazard and F. Rouillier.  Solving parametric polynomial systems.  Journal of Symbolic Computation, 42(6):636–667, 2007.
  * [33] D. T. Lê and B. Teissier.  Cycles évanescents, sections planes, et conditions de Whitney II.  Proceedings of Symposia in Pure Mathematics, 40:65–103, 1983.
  * [34] H. P. Le and M. S. El Din.  Solving parametric systems of polynomial equations over the reals through hermite matrices.  Journal of Symbolic Computation, 112:25–61, 2022.
  * [35] C. Le Guernic, F. Rouillier, and M. S. El Din.  Computing sampling points in a semi-algebraic set defined by non-strict inequalities, application to pattern-matching problems.  In EACA, Santander. Citeseer, 2004.
  * [36] M. Marshall.  Positive polynomials and sums of squares.  Number 146. American Mathematical Soc., 2008.
  * [37] J. Mather.  Notes on topological stability.  Bulletin of the American Mathematical Society, 49(4):475–506, 2012\.
  * [38] M. Michałek and B. Sturmfels.  Invitation to nonlinear algebra, volume 211.  American Mathematical Soc., 2021.
  * [39] H. M. Möller and F. Mora.  Upper and lower bounds for the degree of gröbner bases.  In International Symposium on Symbolic and Algebraic Manipulation, pages 172–183. Springer, 1984.
  * [40] M. Safey El Din and E. Schost.  Polar varieties and computation of one point in each connected component of a smooth real algebraic set.  In Proceedings of the 2003 international symposium on Symbolic and algebraic computation, pages 224–231, 2003.
  * [41] A. Stasica.  An effective description of the Jelonek set.  Journal of Pure and Applied Algebra, 169(2-3):321–326, 2002.
  * [42] H. Whitney.  Tangents to an analytic variety.  Annals of mathematics, pages 496–549, 1965.
  * [43] D. J. Wilson, R. J. Bradford, and J. H. Davenport.  Speeding up cylindrical algebraic decomposition by Gröbner bases.  In International Conference on Intelligent Computer Mathematics, pages 280–294. Springer, 2012.