On the Reeb Spaces of Definable Maps

We prove that the Reeb space of a proper definable map \(f:X \rightarrow Y\) in an arbitrary o-minimal expansion of a real closed field is realizable as a proper definable quotient. This result can be seen as an o-minimal analog of Stein factorization of proper morphisms in algebraic geometry. We also show that the Betti numbers of the Reeb space of f can be arbitrarily large compared to those of X, unlike in the special case of Reeb graphs of manifolds. Nevertheless, in the special case when \(f:X \rightarrow Y\) is a semi-algebraic map and X is closed and bounded, we prove a singly exponential upper bound on the Betti numbers of the Reeb space of f in terms of the number and degrees of the polynomials defining X, Y, and f.

Authors and Affiliations

1. Department of Mathematics, Purdue University, West Lafayette, IN, 47906, USA

   Saugata Basu, Nathanael Cox & Sarah Percival

Corresponding author

Correspondence to Saugata Basu.

Conflict of interest and data sharing

On behalf of all authors, the corresponding author states that there is no conflict of interest. Data sharing not applicable to this article as no datasets were generated or analyzed during the current study.

Editor in Charge: Kenneth Clarkson

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

S. Basu was partially supported by NSF grants CCF-1618918 and DMS-1620271. N. Cox and S. Percival were partially supported by NSF grant DMS-1620271.

Appendix

This section is devoted to the proof of Proposition 5.6. For the convenience of the reader we first recall the proposition.

Proposition

Let \(\mathrm {R}\) be a real closed field. Let \(\mathcal {P} \subset \mathrm {R}[X_1,\ldots ,X_k,Y_1,\ldots ,Y_\ell ]\) be a finite set of polynomials with degrees bounded by d and with \(\mathrm {card}(\mathcal {P}) =s\), and let \(S \subset \mathrm {R}^{k} \times \mathrm {R}^\ell \) be a bounded \(\mathcal {P}\)-closed semi-algebraic set. Then there exists a finite set of polynomials, \(\mathcal {Q} \subset \mathrm {R}[Y_1,\ldots ,Y_\ell ]\), with

such that for each \(\sigma \in {{\,\mathrm{SIGN}\,}}(\mathcal {Q})\), \(C \in \mathrm {Cc}({\mathcal {R}}(\sigma ,\mathrm {R}^\ell ))\), \(\mathbf {y}\in C\), and \(D \in \mathrm {Cc}(S_C)\), \(D_\mathbf {y}\in \mathrm {Cc}(S_\mathbf {y})\).

The rest of this section is devoted to the proof of Proposition 5.6. Since the proof is technical and relies on several intermediate results from algorithmic semi-algebraic geometry we first sketch an outline of the proof for the benefit of the reader.

1.1 A.1  Outline of the Proof of Proposition 5.6

The core idea behind the proof comes from [4] where a singly exponential upper bound is proved on the number of homotopy types of the fibers of a semi-algebraic map. We explain this idea informally below.

Given \(S\subset \mathrm {R}^{k+\ell }\) a \(\mathcal {P}\)-closed and bounded semi-algebraic set, \(\pi _Y:\mathrm {R}^{k+\ell } \rightarrow \mathrm {R}^\ell \) the projection map onto the last \(\ell \)-coordinates, we first introduce infinitesimal elements \(\bar{\varepsilon }=({\varepsilon }_1,\dots ,{\varepsilon }_s)\) (where \(s=\mathrm {card}(\mathcal {P})\)), and define a semi-algebraic subset, \(S^\star (\bar{\varepsilon }) \subset \mathrm {R}{\langle }\bar{\varepsilon }{\rangle }^{k+\ell }\) which is infinitesimally larger than S. We prove (see Lemma A.26) that for each \(\mathbf {y}\in \mathrm {R}^\ell \), the extension of the fiber, \(S_\mathbf {y}=S\cap \pi _Y^{-1}(\mathbf {y})\cap \mathrm {R}^\ell \), to \(\mathrm {R}{\langle }\bar{\varepsilon }{\rangle }\) (see Definition A.3 below for the definition of extension) is a semi-algebraic deformation retract of the fiber \(S^\star (\bar{\varepsilon })_\mathbf {y}=S^\star (\bar{\varepsilon })\cap \pi _Y^{-1}(\mathbf {y})\)—and in particular, these two sets fibers are semi-algebraically homotopy equivalent. (The field \(\mathrm {R}{\langle }\bar{\varepsilon }{\rangle }\) is a real closed extension of \(\mathrm {R}\) consisting of algebraic Puiseux series with coefficients in \(\mathrm {R}\) and is defined below in Sect. 1.) It is important to note that in order to obtain the semi-algebraic homotopy equivalence between the the extension of the fiber \(S_\mathbf {y}\) to \(\mathrm {R}{\langle }\bar{\varepsilon }{\rangle }\) and \(S^\star (\bar{\varepsilon })_\mathbf {y}\), we need the fact that all the coordinates of \(\mathbf {y}\) belong to \(\mathrm {R}\) (rather than \(\mathrm {R}{\langle }\bar{\varepsilon }{\rangle }\setminus \mathrm {R}\)). Note that \(\mathrm {R}\) is a subfield of \(\mathrm {R}{\langle }\bar{\varepsilon }{\rangle }\), and there is thus a natural inclusion of \(\mathrm {R}^\ell \) into \(\mathrm {R}{\langle }\bar{\varepsilon }{\rangle }^\ell \) as well.

Next, we identify a semi-algebraic subset \(G(\bar{\varepsilon }) \subset \mathrm {R}{\langle }\bar{\varepsilon }{\rangle }^{\ell }\) (cf. Definition A.19) of codimension at least one in \(\mathrm {R}{\langle }\bar{\varepsilon }{\rangle }^\ell \), consisting of the critical values of the projection map restricted to the various algebraic sets defined by the polynomials defining \(S^\star (\bar{\varepsilon })\). We prove (Lemma A.20) that the map \(\pi _Y\) restricted to the set \(\pi _Y^{-1}(\mathrm {R}{\langle }\bar{\varepsilon }{\rangle }^\ell \setminus G(\bar{\varepsilon })) \cap S^\star (\bar{\varepsilon })\) is a locally trivial semi-algebraic fibration (see Sect. 1 for the definition of semi-algebraic fibrations). We also observe that \(G(\bar{\varepsilon }) \cap \mathrm {R}^\ell \) is empty and hence \(\mathrm {R}^\ell \subset \mathrm {R}{\langle }\bar{\varepsilon }{\rangle }^\ell \setminus G(\bar{\varepsilon })\).

Moreover, for each \(C \in \mathrm {Cc}(\mathrm {R}{\langle }\bar{\varepsilon }{\rangle }^\ell \setminus G(\bar{\varepsilon }))\), \(C \cap \mathrm {R}^\ell \) is a semi-algebraic subset of \(\mathrm {R}^\ell \). If the projection map \(\pi _Y\) restricted to \(\pi _Y^{-1}(C) \cap S^\star (\bar{\varepsilon })\) is a trivial semi-algebraic fibration (not just a locally trivial one), then we would be done at this point, because we could take \(\mathcal {Q}\subset \mathrm {R}[Y_1,\ldots ,Y_\ell ]\) to be a finite set of polynomials such that the semi-algebraic sets

are all \(\mathcal {Q}\)-semi-algebraic sets. (It follows from certain preliminary results (Propositions 5.5 and A.8) that such a set \(\mathcal {Q}\) exists satisfying the singly exponential estimates in Proposition 5.6.)

In order to arrive at the desired situation (i.e., to have a trivial semi-algebraic fibration instead of just a locally trivial one) we need an additional step of covering the complement of \(G(\bar{\varepsilon })\) using semi-algebraically contractible sets noting that a locally trivial semi-algebraic fibration over a contractible semi-algebraic set is automatically trivial (see Proposition A.11). We use a result from [6] which gives an algorithm for constructing a cover of a given semi-algebraic set by contractible ones (see Proposition A.6) whose complexity is bounded singly exponentially. This introduces some additional technicalities since we need to consider an infinitesimal thickening of \(G(\bar{\varepsilon })\) before taking a cover by contractible semi-algebraic sets of its complement and this is explained in the proof.

One important technical detail is that we need to keep track of the dependence of each polynomial appearing in the definition of the cover on the various infinitesimals introduced in the course of the construction. It is important that each such polynomial depends on at most polynomially many of these infinitesimals and the degrees of the polynomials in the infinitesimals are bounded singly exponentially (cf. parts (c) and (d) of Lemma A.23). This is crucial for ensuring the singly exponential bounds on the set of polynomials \(\mathcal {Q}\) that is produced at the end.

1.2 A.2  Preliminaries

Before proving Proposition 5.6 we need a few preliminary results.

1.2.1 A.2.1  Real Closed Extensions and Puiseux Series

We will need some properties of Puiseux series with coefficients in a real closed field. We refer the reader to [6] for further details.

Notation A.1

For \(\mathrm {R}\) a real closed field we denote by \(\mathrm {R}{\langle }{\varepsilon }{\rangle }\) the real closed field of algebraic Puiseux series in \({\varepsilon }\) with coefficients in \(\mathrm {R}\). We use the notation \(\mathrm {R}\langle {\varepsilon }_{1}, \ldots , {\varepsilon }_{m} \rangle \) to denote the real closed field \(\mathrm {R}\langle {\varepsilon }_{1}\rangle \langle {\varepsilon }_{2}\rangle \ldots \langle {\varepsilon }_{m}\rangle \). Note that in the unique ordering of the field \(\mathrm {R}\langle {\varepsilon }_{1},\ldots , {\varepsilon }_{m}\rangle \), \(0<{\varepsilon }_{m} \ll {\varepsilon }_{m-1}\ll \ldots \ll {\varepsilon }_{1} \ll 1\).

Notation A.2

For elements \(x \in \mathrm {R}\langle {\varepsilon }\rangle \) which are bounded over \(\mathrm {R}\) we denote by \(\lim _{{\varepsilon }} x\) to be the image in \(\mathrm {R}\) under the usual map that sets \({\varepsilon }\) to 0 in the Puiseux series x. If \(\bar{\varepsilon }=({\varepsilon }_1,\ldots ,{\varepsilon }_m)\), and \(x \in \mathrm {R}\langle \bar{\varepsilon }\rangle \) bounded over \(\mathrm {R}\), then we will denote

Definition A.3

If \(\mathrm {R}'\) is a real closed extension of a real closed field \(\mathrm {R}\), and \(S\subset \mathrm {R}^{k}\) is a semi-algebraic set defined by a first-order formula with coefficients in \(\mathrm {R}\), then we will denote by \(\mathrm{Ext}(S, \mathrm {R}') \subset \mathrm {R}'^{k}\) the semi-algebraic subset of \(\mathrm {R}'^{k}\) defined by the same formula. It is well known that \(\mathrm{Ext}(S, \mathrm {R}')\) does not depend on the choice of the formula defining S [6].

For \(\phi \) a \(\mathcal P\)-closed formula, with \(\mathcal P=\{P_1,\ldots ,P_s\}\), we will denote by \(\phi ^\star (\bar{\delta })\) the formula obtained from \(\phi \) by replacing any occurrence of \(P_{i} \ge 0\) with \(P_i\ge -\delta _i\), and any occurrence of \(P_{i} \le 0\) with \(P_{i} \le \delta _i\), for each i, \(1\le i\le s\).

Lemma A.4

Let \(\mathrm {R}\) be a real closed field and \(R\in \mathrm {R}\) with \(R > 0\). The semi-algebraic set \(\mathrm{Ext}{({\mathcal {R}}(\phi ,\mathrm {R}^k) \cap [-R,R]^k, \mathrm {R}{\langle }\bar{\delta }{\rangle })}\) is semi-algebraically homotopy equivalent to \({\mathcal {R}}(\phi ^\star (\bar{\delta }), \mathrm {R}{\langle }\bar{\delta }{\rangle }^k)\cap [-R,R]^k\).

1.2.2 A.2.2  Covering by Semi-Algebraic Contractible Sets

As explained in the outline we will need an auxiliary result on covering of semi-algebraic sets by contractible ones with singly exponential complexity. In order to state this result we first need the notion of being in strong general position.

Definition A.5

Let \(\mathrm {R}\) be a real closed field and \(\mathcal P\subset \mathrm {R}[X_1,\dots ,X_{k}]\) be a finite set. We say that the family \(\mathcal P\) is in \(\ell \)-general position, if no more than \(\ell \) polynomials belonging to \(\mathcal {P}\) have a zero in \(\mathrm {R}^k\). The family \(\mathcal P\) is in strong \(\ell \)-general position if moreover any \(\ell \) polynomials belonging to \(\mathcal {P}\) have at most a finite number of zeros in \(\mathrm {R}^{k}\).

We will use the following proposition which follows from the correctness and complexity analysis of Algorithm 16.14 (Covering by Contractible Sets) in [6].

Proposition A.6

Let \(\mathrm {R}\) be a real closed field and \(\mathrm {D} \subset \mathrm {R}\) and ordered domain. There exists an algorithm that takes as input

1. (i)

   a finite set of s polynomials \(\mathcal {G}= \{G_1,\ldots ,G_t \} \subset \mathrm {D}[\bar{\varepsilon },\bar{\delta }][Y_1,\ldots ,Y_\ell ]\), where \(\bar{\varepsilon }= ({\varepsilon }_1,\ldots ,{\varepsilon }_s)\), \(\bar{\delta }= (\delta _1,\ldots ,\delta _t)\), in strong \(\ell \)-general position on \(\mathrm {R}{\langle }\bar{\varepsilon },\bar{\delta }{\rangle }^\ell \), and such that each polynomial in \(\mathcal {G}\) depends on at most \(k+\ell \) of the \({\varepsilon }_i\)’s and at most one of the \(\delta _i\)’s;

2. (ii)

   a \(\mathcal {G}\)-closed formula \(\psi \);

3. (iii)

   \(R > 0\), \(R \in \mathrm {D}\);

and outputs

1. (a)

   a finite set of polynomials \(\mathcal {H} \subset \mathrm {D}[\bar{\varepsilon },\bar{\delta },\bar{\zeta }][Y_1,\ldots ,Y_\ell ]\), \(\bar{\zeta }= (\zeta _1,\ldots ,\zeta _{2 \mathrm {card}(\mathcal {H})})\);

2. (b)

   a tuple of \(\mathcal {H}\)-formulas \((\theta _\alpha )_{\alpha \in I}\) such that each \({\mathcal {R}}(\theta _\alpha ,\mathrm {R}{\langle }\bar{\varepsilon },\bar{\delta },\bar{\zeta }{\rangle },^\ell )\), \(\alpha \in I\), is a closed semi-algebraically contractible set; and

3. (c)

   \(\displaystyle \bigcup _{\alpha \in I}{\mathcal {R}}(\theta _\alpha ,\mathrm {R}{\langle }\bar{\varepsilon },\bar{\delta },\bar{\zeta }{\rangle }^\ell ) = {\mathcal {R}}(\psi ,\mathrm {R}{\langle }\bar{\varepsilon },\bar{\delta },\bar{\zeta }{\rangle }^\ell )\cap [-R,R]^{\ell }\).

Moreover,

where \(D = \max _{1 \le i \le t} \deg (G_i)\). Moreover, each polynomial appearing in \(\mathcal {H}\) depends on at most \((k+\ell ) (\ell +1)^2\) of \({\varepsilon }_i\)’s, at most \((\ell +1)^2\) of the \(\delta _i\)’s, and on at most one of the \(\zeta _i\)’s.

Remark A.7

Note that the last claim in Proposition A.6, namely that each polynomial appearing in any of the formulas \(\theta _\alpha \) depends on at most \((k+\ell )(\ell +1)^2\) of \({\varepsilon }_i\)’s, at most \((\ell +1)^2\) of the \(\delta _i\)’s and on at most one of the \(\zeta _i\)’s, does not appear explicitly in [6], but is evident on a close examination of the algorithm. It is also reflected in the fact that the combinatorial part (i.e., the part depending on \(\mathrm {card}(\mathcal {G})\)) of the complexity of [6, Algorithm 16.14] is bounded by \(\mathrm {card}(\mathcal {G})^{(\ell +1)^2}\). This is because [6, Algorithm 16.14] has a “local property”, namely that all computations involve at most a small number (in this case \((\ell +1)^2\)) polynomials in the input at a time.

1.2.3 A.2.3  Effective Quantifier Elimination

We will also need the following effective bound on the complexity of eliminating one block of existential quantifiers in the theory of real closed fields. It is a direct consequence of [6, Thm. 14.16].

Proposition A.8

Let \(\mathrm {R}\) be a real closed field, \(\mathrm {D} \subset \mathrm {R}\) an ordered domain, \(\mathcal {Q} \subset \mathrm {D}[{\varepsilon }_1,\ldots ,{\varepsilon }_m][X_1,\ldots ,X_k,Y_1,\ldots ,Y_\ell ]\) a finite set of polynomials, and \(\psi \) a \(\mathcal {Q}\)-formula. Suppose that the degrees of the polynomials in \(\mathcal {Q}\) in \({\varepsilon }_h, X_i, Y_j\) for \(1 \le h \le m\), \(1\le i \le k\), \(1\le j \le \ell \), are all bounded by D. Then, there exists a finite set of polynomials \(\mathcal {G} \subset \mathrm {D}[{\varepsilon }_1,\ldots ,{\varepsilon }_m][Y_1,\ldots ,Y_\ell ]\), and a \(\mathcal {G}\)-formula \(\theta \) satisfying the following conditions:

1. (a)

   \(\displaystyle \mathrm {card}(\mathcal {G}) = ({\mathrm {card}(\mathcal {Q})}D)^{O((k+1)(\ell +1))}\);

2. (b)

   \(\displaystyle \max _{G \in \mathcal {G}, 1\le i \le m, 1 \le j \le \ell }\bigl (\deg _{{\varepsilon }_i}(G),\deg _{Y_j}(G)\bigr ) = D^{O(k)}\);

3. (c)

   \(\displaystyle {\mathcal {R}}(\theta ,\mathrm {R}{\langle }\bar{\varepsilon }{\rangle }^\ell )=\pi _Y({\mathcal {R}}(\psi ,\mathrm {R}{\langle }\bar{\varepsilon }{\rangle }^{k+\ell }))\).

1.2.4 A.2.4  Trivial and Locally Trivial Semi-Algebraic Fibrations

As explained in the outline we will also need the notion of trivial and locally trivial semi-algebraic fibrations.

Definition A.9

Let \(\mathrm {R}\) be a real closed field. Let \(p:E \rightarrow B\) be a semi-algebraic map. We say that p is a trivial semi-algebraic fibration if there exists \(b \in B\) and a semi-algebraic homeomorphism \(h:E \rightarrow p^{-1}(b) \times B\), such that the following diagram commutes:

(here \(\pi \) is the projection to the second factor). We say that the map p is a locally trivial semi-algebraic fibration if there exists a finite covering \((U_i)_{i \in I}\) of B by semi-algebraic subsets which are open in B, such that for each \(i \in I\), \(p|_{p^{-1}(B_i)}\) is a semi-algebraic trivial fibration.

Definition A.10

(pull-back of a semi-algebraic locally trivial fibration under a semi-algebraic map) Let \(p:E\rightarrow B\) be a locally trivial semi-algebraic fibration, and \(f:B'\rightarrow B\) be a continuous semi-algebraic map. Then the map \(f^*p:E\times _BB'\rightarrow B'\), \((e,b')\mapsto b'\), is again a semi-algebraic locally trivial fibration (called the pull-back of p under f).

The main property of semi-algebraic fibrations that we will need is the following.

Proposition A.11

Let \(p:E \rightarrow B\) be a locally trivial semi-algebraic fibration. Suppose \(B'\) is a semi-algebraically contractible subset of B and \(B''\) any semi-algebraic subset of \(B'\). Then \(p|_{p^{-1}(B'')}\) is a trivial semi-algebraic fibration.

Proposition A.11 is a corollary of the following more general proposition.

Proposition A.12

Let \(p:E \rightarrow B\) be a locally trivial semi-algebraic fibration, and let \(f,g:B'\rightarrow B\) be two continuous semi-algebraic maps which are semi-algebraically homotopic. The, \(f^*p\) and \(g^*p\) are isomorphic as locally trivial semi-algebraic fibrations.

Proof

The corresponding statement in the category of topological spaces and maps appear in [1, Thm. 4.6.4] with the extra assumption that \(B'\) is paracompact. We do not give a complete proof of Proposition A.12 here but just indicate the modifications needed in the proof of [1, Thm. 4.6.4] to carry it over to the semi-algebraic setting over an arbitrary real closed field \(\mathrm {R}\).

The key result used in the proof of Theorem 4.6.4 in [1] is Proposition 4.6.3, whose statement is reproduced below using the notation of the current paper.

Let \(p:E \rightarrow B \times [0,1]\) be a locally trivial fibration, where B is a paracompact space. Let \(r:B \times [0,1] \rightarrow B \times [0,1]\) be the retraction \(r(b,t)=(b,1)\). Then, p is isomorphic to \(r^*p\).

We will need the following semi-algebraic version of the above statement, namely:

Claim A.13

Let \(p:E \rightarrow B \times [0,1]\) be a locally trivial semi-algebraic fibration. Let \(r:B' \times [0,1] \rightarrow B \times [0,1]\) be the retraction defined by \(r(b,t) = (b,1)\). Then, p is isomorphic to \(r^*p\).

All the modifications needed are in the proof of the above claim. In the proof of [1, Prop. 4.6.3] replace the open cover \((U_\alpha )_{\alpha \in \Lambda }\) of B (which is assumed to be only locally finite using the paracompactness of B) by a finite open cover of \((U_i)_{i\in I}\) of the semi-algebraic set B such that p restricted to each \(U_\alpha \times [0,1]\) is a trivial semi-algebraic fibration. Such a finite cover exists if p is a locally trivial semi-algebraic fibration. Next, replace the partition of unity \(\{\eta _\alpha \}_{\alpha \in \Lambda }\) subordinate to the partition \((U_\alpha )_{\alpha \in \Lambda }\) by a a semi-algebraic partition of unity \(\{\eta _i\}_{i \in I}\) subordinate to the (finite) cover \((U_i)_{i\in I}\) which is known to exist (see [8, Lem. 12.7.3]). These two modifications to the proof of [1, Prop. 4.6.3] produce a proof of Claim A.13. Proposition A.12 now follows from Claim A.13 in exactly the same way as Theorem 4.6.4 is deduced from Proposition 4.6.3 in [1]. \(\square \)

Proof of Proposition A.11

First observe that it is obvious that the restriction of a trivial semi-algebraic fibration \(p':E'\rightarrow B'\) to to a semi-algebraic subset \(B'' \subset B'\) is again a trivial semi-algebraic fibration. Let \(p':E' \rightarrow B'\) be the restriction of the locally trivial semi-algebraic fibration p to \(B'\). Now since \(B'\) is assumed to semi-algebraically contractible, there exists a semi-algebraic homotopy between \(f= \mathrm {id}_{B'}\) and a constant map \(g:B' \rightarrow B'\). We obtain that \(p' \cong f^*p' \cong g^* p'\), where the first isomorphism is due to the fact that f is the identity map, and the second isomorphism is a consequence of Proposition A.12 and the fact that f and g are homotopic. Now since \(g^*p'\) is the pull-back of \(p'\) under a constant map, it is clearly a trivial semi-algebraic fibration. Finally, the observation at the beginning of the proof implies that \(p'\) restricted to \(B'' \subset B'\) is also trivial. \(\square \)

1.3 A.3  Proof of Proposition 5.6

For the rest of this section we fix a real closed field \(\mathrm {R}\), a finite set of polynomials

as well as a \(\mathcal {P}\)-closed formula \(\phi \). We denote \(S = {\mathcal {R}}(\phi ,\mathrm {R}^{k+\ell })\).

Notation A.14

For \(\bar{{\varepsilon }} = ({\varepsilon }_1,\ldots ,{\varepsilon }_{s})\), we denote by \(\phi ^{\star ,c} (\bar{{\varepsilon }})\), the \(\mathcal {P}^\star (\bar{{\varepsilon }})\)-closed formula obtained by replacing each occurrence of \(P_i \ge 0\) in \(\phi \) by \(P_i + {\varepsilon }_i \ge 0\) (resp. \(P_i \le 0\) in \(\phi \) by \(P_i - {\varepsilon }_i \le 0\)) for \(1 \le i \le s\), where

Observe that

is a \(\mathcal {P}^\star (\bar{{\varepsilon }})\)-closed semi-algebraic set.

Remark A.15

We will use a few results whose proofs can be found in [4]. These results are stated in [4] not using the language of Puiseux extensions but rather with the \({\varepsilon }_i\)’s occurring in the statement as small enough positive elements of the ground field \(\mathrm {R}\). However, the statements in [4] imply the corresponding statements of the current paper in terms of Puiseux series by an application of a standard argument using the Tarski–Seidenberg transfer principle.

More precisely, the following fact which is a consequence of the Tarski–Seidenberg transfer principle will be used repeatedly. If \(\phi (T)\) is a first order formula with constants in a real closed field \(\mathrm {R}\), then the first order sentence

is true over \(\mathrm {R}\) if and only if the sentence \(\phi ({\varepsilon })\) is true over \(\mathrm {R}{\langle }{\varepsilon }{\rangle }\).

In order to see this observe that \({\mathcal {R}}(\phi (T),\mathrm {R})\) is a semi-algebraic subset of \(\mathrm {R}\) which contains an interval \((0,t_0)\) for some \(t_0 > 0\). Then by the Tarski–Seidenberg transfer principle, \((0,t_0)\subset {\mathcal {R}}(\phi (T),\mathrm {R}{\langle }{\varepsilon }{\rangle })\) as well. Now, since \({\varepsilon }\) is positive and smaller than all positive elements of \(\mathrm {R}\) in the unique ordering of the real closed field \(\mathrm {R}{\langle }{\varepsilon }{\rangle }\), \(0<{\varepsilon }<t_0\), and so \({\varepsilon }\in {\mathcal {R}}(\phi (T),\mathrm {R}{\langle }{\varepsilon }{\rangle })\). Hence, \(\phi ({\varepsilon })\) is true over \(\mathrm {R}{\langle }{\varepsilon }{\rangle }\).

Lemma A.16

For each \(\mathcal {Q} \subset \mathcal {P}^\star (\bar{\varepsilon })\), \(\mathrm {Z}(\mathcal {Q},\mathrm {R}{\langle }\bar{\varepsilon }{\rangle }^{k+\ell })\) is either empty or is a non-singular \((k+\ell -\mathrm {card}(\mathcal {Q}))\)-dimensional real variety such that at every point

the \((\mathrm {card}(\mathcal {Q}) \times (k+\ell ))\)-Jacobian matrix,

has the maximal possible rank.

Proof

See the proof of [4, Lem. 3.3] and use Remark A.15. \(\square \)

Lemma A.17

For each \(\mathcal {Q} \subset \mathcal {P}^\star (\bar{\varepsilon })\), and \(\mathbf {y}\in \mathrm {R}^\ell \), \(\mathrm {Z}(\mathcal {Q}(\,{\cdot }\,,\mathbf {y}),\mathrm {R}{\langle }\bar{\varepsilon }{\rangle }^{k})\) is either empty or is a non-singular \((k-\mathrm {card}(\mathcal {Q}))\)-dimensional real variety such that at every point

the \((\mathrm {card}(\mathcal {Q}) \times k)\)-Jacobian matrix,

has the maximal possible rank.

Proof

Similar to the proof of Lemma A.16. \(\square \)

Notation A.18

[critical points and critical values] For \(\mathcal {Q} \subset \mathcal {P}^\star (\bar{\varepsilon })\), we denote by \(\mathrm {Crit}(\mathcal {Q})\) the subset of \(\mathrm {Z}(\mathcal {Q},\mathrm {R}{\langle }\bar{\varepsilon }{\rangle }^{k+\ell })\) at which the Jacobian matrix,

is not of the maximal possible rank. We denote \(\mathrm {crit}(\mathcal {Q}) = \pi _Y(\mathrm {Crit}(\mathcal {Q}))\).

Definition A.19

Let

Lemma A.20

Let

Then, the map \(\pi _Y|_{\widehat{S}}\) is a locally trivial semi-algebraic fibration.

Proof

See the proof of [4, Lem. 3.8] and use Remark A.15. \(\square \)

Lemma A.21

There is a finite set of polynomials \(\mathcal {G} \{G_1,\ldots ,G_t \} \subset \mathrm {R}[\bar{\varepsilon }][Y_1,\ldots ,Y_\ell ]\), and a \(\mathcal {G}\)-formula \(\psi \) satisfying the following.

1. (a)

   \(\displaystyle G(\bar{\varepsilon }) = {\mathcal {R}}(\psi ,\mathrm {R}{\langle }\bar{\varepsilon }{\rangle }^\ell )\),

2. (b)

   \(\displaystyle \mathrm {card}(\mathcal {G}) \le (k s d)^{O(k\ell )}\),

3. (c)

   \(\displaystyle \max _{1 \le i \le t}\bigl (\deg _{\bar{Y}}(G_i), \deg _{\bar{\varepsilon }}\deg (G_i)\bigr ) \le d^{O(k\ell )}\).

4. (d)

   Moreover, each polynomial in \(\mathcal {G}\) depends on at most \(k+\ell \) of the \({\varepsilon }_i\)’s.

Proof

For each subset \(\mathcal {Q}\subset \mathcal {P}^\star (\bar{\varepsilon })\) with \(0< \mathrm {card}(\mathcal {Q}) \le k\), use Proposition A.8 to obtain a set of polynomials \(\mathcal G_{1,\mathcal Q}\subset \mathrm {R}[\bar{\varepsilon }][Y_1,\dots ,Y_\ell ]\) such that \(\mathrm {crit}(\mathcal {Q})\) is a \(\mathcal {G}_{1,\mathcal {Q}}\)-semi-algebraic set defined by a \(\mathcal {G}_{1,\mathcal {Q}}\)-formula \(\psi _{1,\mathcal {Q}}\). For each subset \(\mathcal Q\subset \mathcal P^\star (\bar{\varepsilon })\) with \(k<\mathrm {card}(\mathcal {Q}) \le k+\ell \), use Proposition A.8 to obtain a set of polynomials \(\mathcal G_{2,\mathcal Q}\subset \mathrm {R}[\bar{\varepsilon }][Y_1,\dots ,Y_\ell ]\) such that \(\pi _Y(\mathrm {Z}(\mathcal {Q},\mathrm {R}{\langle }\bar{\varepsilon }{\rangle }^\ell ))\) is a \(\mathcal {G}_{2,\mathcal {Q}}\)-semi-algebraic set defined by a \(\mathcal {G}_{2,\mathcal {Q}}\)-formula \(\psi _{2,\mathcal {Q}}\). Let

and

Then

Observe that each of the sets \(\mathcal {G}_{i,\mathcal {Q}}\), where \(i=1,2\) and \(\mathcal {Q} \subset \mathcal {P}^*(\bar{\varepsilon })\), depends on at most \(k+\ell \) of the \({\varepsilon }_i\)’s. Moreover, using (b) and (c) of Proposition A.8 we can assume that

(where \(s = \mathrm {card}(\mathcal {P})\) and \(d = \max _{P \in \mathcal {P}} \deg (P)\)). \(\square \)

Without loss of generality we can assume that

for some subset \(\Sigma \subset {{\,\mathrm{SIGN}\,}}(\mathcal {G})\), where for \(\sigma \in \Sigma \), \(\psi _\sigma \) is the formula defined by

where \(\sigma _i\) equals \(>,<,0\) according to \(\sigma (G_i) = 1,-1,0\), respectively.

Denote by \(\psi ^{\star ,o}(\bar{\varepsilon },\bar{\delta })\), the \(\mathcal {G}^\star (\bar{\varepsilon },\bar{\delta })\)-open formula obtained by replacing each occurrence of \(G_i=0\) in \(\psi \) by \((G_i-\delta _i<0)\wedge (G_i+\delta _i>0)\), \(G_i>0\) in \(\psi \) by \(G_i+\delta _i>0\), and each occurrence of \(G_i<0\) by \(G_i - \delta _i < 0\), for \(1 \le i \le t\), where

Let

Then

is a \(\mathcal {G}^\star (\bar{\varepsilon },\bar{\delta })\)-closed semi-algebraic set.

Lemma A.22

The set \(\mathcal {G}^\star (\bar{\varepsilon },\bar{\delta })\) is in strong \(\ell \)-general position over \(\mathrm {R}{\langle }\bar{\varepsilon },\bar{\delta }{\rangle }^\ell \).

Proof

Similar to the proof of Lemma A.16. \(\square \)

Lemma A.23

For each \(R>0\), \(R\in \mathrm {R}\), there exists a finite set of polynomials \(\mathcal H\subset \mathrm {R}[\bar{\varepsilon },\bar{\delta },\bar{\zeta }][Y_1,\ldots ,Y_\ell ]\), where \(\bar{\zeta }= (\zeta _1,\ldots ,\zeta _{2\mathrm {card}(\mathcal {H})})\), and a tuple of \((C_\alpha )_{I \in \alpha }\) of \(\mathcal {H}\)-closed semi-algebraic sets satisfying the following.

1. (a)

   Each \(C_\alpha \) is an \(\mathcal {H}\)-semi-algebraic set which is moreover semi-algebraically contractible.

2. (b)

   \(\displaystyle \bigcup _{\alpha \in I} C_\alpha = G^{+,o}(\bar{\varepsilon },\bar{\delta })^c\cap [-R,R]^\ell \).

3. (c)

   \(\displaystyle \mathrm {card}(I), \mathrm {card}(\mathcal {H})\,{\le }\,(s d)^{k^{O(\ell )}}\); \(\displaystyle \deg _{\bar{Y}}(H), \deg _{\bar{{\varepsilon }}}(H), \deg _{\bar{\delta }}(H), \deg _{\bar{\zeta }}(H)\,{\le }\, d^{k^{O(\ell )}}\).

4. (d)

   Moreover, each polynomial in \(\mathcal {H}\) depends on at most \((k+\ell )(\ell +1)^2\) of \({\varepsilon }_i\)’s, at most \((\ell +1)^2\) of the \(\delta _i\)’s and on at most one of the \(\zeta _i\)’s.

Proof

Use Lemma A.21 and Proposition A.6. \(\square \)

Since the semi-algebraic set \(S = {\mathcal {R}}(\phi ,\mathrm {R}^{k+\ell })\) is assumed to be bounded over \(\mathrm {R}\), there exists \(R \in \mathrm {R}\), \(R > 0\), such that \(S \subset [-R,R]^{k+\ell }\). We fix \(R > 0\), such that \(S \subset [-R,R]^{k+\ell }\) in what follows. We also fix the cover \((C_\alpha )_{\alpha \in I}\) and the finite family of polynomials \(\mathcal {H} \subset \mathrm {R}[\bar{\varepsilon },\bar{\delta },\bar{\zeta }][Y_1,\ldots ,Y_\ell ]\) given by Lemma A.23.

Lemma A.24

For each \(\sigma \in {{\,\mathrm{SIGN}\,}}(\mathcal {H})\), such that \({\mathcal {R}}(\sigma ,\mathrm {R}{\langle }\bar{\varepsilon },\bar{\delta },\bar{\zeta }{\rangle }^\ell ) \subset C_\alpha \) for some \(\alpha \in I\), let

Then the map \(\pi _Y|_{S_\sigma }\) is a trivial semi-algebraic fibration.

Proof

Follows from Lemma A.20 and Proposition A.11 noting that the semi-algebraic set \(C_\alpha \) is semi-algebraically contractible using part (a) of Lemma A.23. \(\square \)

Using the same notation as above we have:

Lemma A.25

1. (a)

   \(\displaystyle \mathrm {R}^\ell \cap [-R,R]^\ell \,\subset \!\bigcup _{\begin{array}{c} \sigma \in {{\,\mathrm{SIGN}\,}}(\mathcal {H})\\ {\mathcal {R}}(\sigma ) \subset \bigcup _{\alpha \in I} C_\alpha \end{array}}\!\!\!{\mathcal {R}}(\sigma ,\mathrm {R}{\langle }\bar{\varepsilon },\bar{\delta },\bar{\zeta }{\rangle }^\ell )\).

2. (b)

   There exists a finite set of polynomials, \(\mathcal {Q} \subset \mathrm {R}[Y_1,\ldots ,Y_\ell ]\), with degrees and cardinality bounded by \((sd)^{(k+\ell )^{O(1)}}\), such that for each \(\sigma \in {{\,\mathrm{SIGN}\,}}(\mathcal {Q})\), there exists \(\alpha \in I\) such that \({\mathcal {R}}(\sigma ,\mathrm {R}^\ell ) \subset C_\alpha \).

Proof

First we prove (a). It follows from the property guaranteed by (b) of Lemma A.23 that for each \(\alpha \in I\),

So it suffices to prove that \(G^{+,o}(\bar{\varepsilon },\bar{\delta })\cap [-R,R]^\ell \cap \mathrm {R}^\ell = \emptyset \). Since, \(\lim _{\bar{\delta }} G^{+,o}(\bar{\varepsilon },\bar{\delta }) \cap [-R,R]^\ell = G(\bar{\varepsilon })\cap [-R,R]^\ell \), in order to prove that \(G^{+,o}(\bar{\varepsilon },\bar{\delta }) \cap [-R,R]^\ell \cap \mathrm {R}^\ell = \emptyset \), it is enough to show that \(G(\bar{\varepsilon })\cap [-R,R]^\ell \cap \mathrm {R}^\ell = \emptyset \). Suppose there exists \(\mathbf {y}\in G(\bar{\varepsilon }) \cap [-R,R]^\ell \cap \mathrm {R}^\ell \). Then there are two cases:

1. Case 1

   There is \(\mathcal {Q} \subset \mathcal {P}^\star (\bar{\varepsilon })\), \(0<\mathrm {card}(\mathcal {Q}) \le k\), such that \(\mathbf {y}\in \mathrm {crit}(\mathcal {Q})\). But this would imply that there exists \((\mathbf {x},\mathbf {y}) \in \mathrm {R}{\langle }\bar{\varepsilon }{\rangle }^{k+\ell }\) such that the rank of the corresponding Jacobian matrix

   $$\begin{aligned}\biggl (\frac{\partial P}{\partial X_i}\biggr )_{\begin{array}{c} P \in \mathcal {Q} \\ 1\le i \le k \end{array}}\end{aligned}$$

   at the point \((\mathbf {x},\mathbf {y})\) is not full, which contradicts Lemma A.17.

2. Case 2

   There is \(\mathcal {Q}\subset \mathcal {P}^\star (\bar{\varepsilon })\), \(k<\mathrm {card}(\mathcal {Q})\le k+\ell \), such that \(\mathbf {y}\in \pi _Y(\mathrm {Z}(\mathcal {Q},\mathrm {R}{\langle }\bar{\varepsilon }{\rangle }^{k+\ell }))\). But since \(\mathrm {card}(\mathcal {Q})>k\), and \(\mathbf {y}\in \mathrm {R}^\ell \), by Lemma A.17, \(\mathrm {Z}(\mathcal {Q}(\,{\cdot }\,,\mathbf {y}), \mathrm {R}{\langle }\bar{\varepsilon }{\rangle }^k) = \emptyset \), which is a contradiction.

We turn to the proof of (b). Let \(\eta = (\bar{\varepsilon },\bar{\delta },\bar{\zeta })\). For each \(H \in \mathcal {H}\), write

where \(\alpha \in \mathbb {N}^{|\bar{\varepsilon }|+|\bar{\delta }|+|\bar{\zeta }|}\) is a multi-index exponent, and each \(H_\alpha \in \mathrm {R}[Y_1,\ldots ,Y_\ell ]\). Denote by \(\mathrm {Supp}(H)=\{\alpha | H_\alpha \ne 0\}\). It follows from the bounds on the set \(\mathcal {H}\) stated in parts (c) and (d) of Lemma A.23 that \(\mathrm {card}(\mathrm {Supp}(H)) \le (s d)^{(k +\ell )^{O(1)}}\). Let

It follows from the definition of the ordering of the real closed field \(\mathrm {R}{\langle }\eta {\rangle }\) (cf. Notation A.1), that for any \(\mathbf {y}\in \mathrm {R}^\ell \), and \(H \in \mathcal {H}\), \({\textbf { sign}}(H(\mathbf {y}))\) is determined by the tuple of signs \((\!{\textbf { sign}}(H_\alpha (\mathbf {y})))_{\alpha \in \mathrm {Supp}(H)}\). It is now easy to see that \(\mathcal {Q}\) satisfies the claimed properties. \(\square \)

Lemma A.26

Let \(\mathbf {y}\in \mathrm {R}^\ell \). Then, there exists a semi-algebraic deformation retraction \(S^\star (\bar{\varepsilon })_\mathbf {y}\rightarrow \mathrm{Ext}(S_\mathbf {y},\mathrm {R}{\langle }\bar{\varepsilon }{\rangle })\). In particular, \(\mathrm{Ext}(S_\mathbf {y}, \mathrm {R}{\langle }\bar{\varepsilon }{\rangle })\) is semi-algebraically homotopy equivalent to \(S^\star (\bar{\varepsilon })_\mathbf {y}\).

Proof

This is a consequence of [6, Lem. 16.17] noting that the set \(S^\star (\bar{\varepsilon })_\mathbf {y}\) is bounded over \(\mathrm {R}\). \(\square \)

Proof of Proposition 5.6

Let \(\mathcal {Q}\) be as in Lemma A.25, and let \(\sigma \in {{\,\mathrm{SIGN}\,}}(\mathcal {Q})\), such that \({\mathcal {R}}(\sigma ,\mathrm {R}^\ell ) \subset C_\alpha \) for some \(\alpha \in I\) (following the same notation as in Lemma A.25). Let \(C \in \mathrm {Cc}({\mathcal {R}}(\sigma ,\mathrm {R}^\ell ))\). Now, let \(D_1^\alpha , \ldots , D_N^\alpha \subset \mathrm {R}{\langle }\bar{\varepsilon },\bar{\delta }{\rangle }^\ell \) be the elements of \(\mathrm {Cc}(D_\alpha )\) where \(D_\alpha = \pi _Y^{-1}(C_\alpha ) \cap \mathrm{Ext}(S^\star (\bar{\varepsilon }) \cap [-R,R]^{k+\ell },\mathrm {R}{\langle }\bar{\varepsilon },\bar{\delta }{\rangle })\). The proposition will follow from the following two claims. \(\square \)

Claim A.27

\(\bigl (\lim _{\bar{\varepsilon },\bar{\delta }} D_\alpha \bigr )_C=S_C\).

Claim A.28

\(\bigl (\lim _{\bar{\varepsilon },\bar{\delta }}D_\alpha ^i\bigr )_C\), \(i =1,\ldots , N\), are the semi-algebraically connected components of \(S_C\).

Proof of Claim A.27

First observe that since \(S^{\star ,c}(\bar{\varepsilon })\cap [-R,R]^{k+\ell }\) is bounded over \(\mathrm {R}\), so is \(D_\alpha \). Also, it is clear that \(S_C\subset \bigl (\lim _{\bar{\varepsilon },\bar{\delta }} D_\alpha \bigr )_C\). To prove the reverse inclusion, let \((\mathbf {x},\mathbf {y})\in \bigl (\lim _{\bar{\varepsilon },\bar{\delta }}D_\alpha \bigr )_C\). Then, there exists \((\tilde{\mathbf {x}},\tilde{\mathbf {y}})\in D_\alpha \), such that

Since \(S^{\star ,c}(\bar{\varepsilon })\cap [-R,R]^{k+\ell }\) (cf. (A.1)) is a closed semi-algebraic subset of \(\mathrm {R}{\langle }\bar{\varepsilon }{\rangle }^{k+\ell }\) bounded over \(\mathrm {R}\), it follows that

This implies

Finally, it follows from

that

\(\square \)

Proof of Claim A.28

Using Claim A.27 it suffices to prove that for each i, \(1 \le i \le N\), \(\bigl (\lim _{\bar{\varepsilon },\bar{\delta }}D_\alpha ^i\bigr )_C\) is semi-algebraically connected, and for \(1 \le i < j \le N\),

In order to prove that \(\bigl (\lim _{\bar{\varepsilon },\bar{\delta }}D_\alpha ^i\bigr )_C \) is semi-algebraically connected, let

Let \(\gamma :[0,1] \rightarrow C\) be a semi-algebraic path, with \(\gamma (0) = \mathbf {y}\), \(\gamma (1) = \mathbf {y}'\) (which exists since C is semi-algebraically connected). First observe, that since \(\mathbf {y},\mathbf {y}' \in C \subset \mathrm {R}^\ell \), it follows from Lemma A.26, that \(\mathbf {x},\mathbf {x}' \in D^i_\alpha \). Then, using Lemma A.24, there exists a lift of \(\mathrm{Ext}(\gamma ,\mathrm {R}{\langle }\bar{\varepsilon },\bar{\delta }{\rangle })\) to a semi-algebraic path,

Then

is a semi-algebraic path connecting \((\mathbf {x},\mathbf {y})\) to \((\mathbf {x}',\mathbf {y}')\) with image in \(\bigl (\lim _{\bar{\varepsilon },\bar{\delta }}D_\alpha ^i\bigr )_C\), proving that \(\bigl (\lim _{\bar{\varepsilon },\bar{\delta }}D_\alpha ^i\bigr )_C\) is semi-algebraically connected.

We now prove that for \(1 \le i < j \le N\), (A.2) holds. Suppose that

Using Lemma A.26 and the fact that \(\mathbf {y}\in C \subset \mathrm {R}^\ell \), this would imply that \((\mathbf {x},\mathbf {y}) \in D^i_\alpha \cap D^j_\alpha \). But this is impossible, since \(D^i_\alpha \) and \(D^j_\alpha \) are distinct semi-algebraically connected components of \(D_\alpha \). The proposition now follows from Claim A.28. \(\square \)

Reprints and permissions