Quantitative curve selection lemma (Q2114147)

The Curve Selection Lemma in real algebraic geometry, proved by Lojasiewicz, states that given a semi-algebraic set \(S \subseteq R^k\), where \(R\) is a real closed field (typically real numbers), and a point \(x\) in the closure of \(S\), there exists a semi-algebraic path starting at \(x\) and entering in \(S\). Curve selection lemma is a fundamental result in semi-algebraic geometry and has many applications. The quantitative version of the curve selection lemma had been initiated by \textit{Z. Jelonek} and \textit{K. Kurdyka} [Math. Z. 276, No. 1--2, 557--570 (2014; Zbl 1288.14044)]. The current article presents a new approach towards a quantitative version of curve selection lemma, giving a new algorithm to construct the paths in the lemma. This work improves earlier complexity bounds (in Jelonek and Kurdyka's work) on constructing the paths in the curve selection lemma. In order to describe the semi-algebraic paths in the curve selection lemma, the authors use Rational Univariate Representation (RUR), introduced by Rouilier. Using RUR allows defining the degree of a description of the paths via the degrees of the polynomials that appear in RUR. Degree bounds on RUR are then used for analysing the complexity of computing the semi-algebraic paths. In fact, the authors prove a theorem, called Construction of Little Paths, which is stronger than the quantitative curve selection lemma. An algorithm is presented for the construction of little paths theorem, that is similar to an algorithm for computing realization of sign conditions, described in the authors' book, Algorithms in Real Algebraic Geometry. The algorithm not only constructs the paths in the quantitative curve selection lemma, but also checks for realization of sign conditions on the points of the paths. The quantitative curve selection lemma is then an immediate corollary of the construction of little paths theorem. The article ends with two interesting consequences of the quantitative curve selection lemma proved in this article: Firstly, the exponential degree of the Zariski closure of the little paths constructed in the article, improves the complexity bound in Jelonek and Kurdyka's work. Secondly, the real isolated points in a semi-algebraic set can be computed with an exponential complexity bound. The latter leads to an algorithm to test whether a given semi-algebraic set is zero-dimensional. In the special case of algebraic sets, zero-dimensionality test presented in the current paper provides a simpler method, improving an existing complexity bound.