Refined bounds on the number of connected components of sign conditions on a variety (Q411399): Difference between revisions

Let \(R\) be a real closed field and let \(\{f_1,\dots,f_s,g_1,\dots,g_{\ell}\} \) be a finite subset of the polynomial ring \(R[{\mathtt x}_1,\dots,{\mathtt x}_k]\) in \(k\) indeterminates with coefficients in \(R\). Consider the algebraic subset \[ V:=\{x\in R^k:g_1(x)=0,\dots,g_{\ell}(x)=0\} \] of \(R^k\) and let \(k'\) be an upper bound of the dimension of \(V\). Let \[ d:=\max\{\deg(f_i):1\leq i\leq s\}\quad\quad d_0:=\max\{\deg(g_i):1\leq i\leq\ell\}. \] For every \(\varepsilon:=(\varepsilon_1,\dots,\varepsilon_s)\in\{-1,0,1\}^s\) let us denote \[ V_{\varepsilon}:=\{x\in V:\text{sign}(f_i(x))=\varepsilon_i,\quad\forall\, \, 1\leq i\leq s\}, \] where, for every \(t\in R\), \[ \text{sign}(t)=\begin{cases} 1& \text{if \(t>0\)} \\ 0& \text{if \(t=0\)}\\ -1& \text{if \(t<0\)} \end{cases}. \] The authors prove that the maximum number of semialgebraically connected components of the sets \(V_{\varepsilon}\), where \(\varepsilon\in\{-1,0,1\}^s\), is upperly bounded by \[ \sum_{j=0}^{k'}4^j\binom{s+1}{j}F_{d,d_0,k,k'}(j), \] where \[ F_{d,d_0,k,k'}(j)=\binom{k+1}{k-k'+j+1}(2d_0)^{k-k'}d^j\max\{2d_0,d\}^{k'-j}+2(k-j+1). \] In case \(d_0\ll d\) this bound is sharper than the best known bound in the case \(d=d_0\) \[ \sum_{1\leq j\leq k'}4^jd(2d-1)^{k-1} \] on the same number proved in [\textit{S. Basu, R. Pollack} and \textit{M.-F. Roy}, Proc. Am. Math. Soc. 133, No. 4, 965--974 (2005; Zbl 1080.14068)]. Notice that if \(R=\mathbb R\) is the field of real numbers, the notions of connected component and semialgebraically connected component of a semialgebraic set coincide. The problem of finding upper bounds for the number of connected components of a semialgebraic set is a classical one in semialgebraic geometry, and the article [\textit{R. Benedetti, R. Loeser} and \textit{J. J. Risler}, Discrete Comput. Geom. 6, No. 3, 191--209 (1991; Zbl 0743.14040)], which just concerns real algebraic sets, is pioneer in this field. Slightly later, the paper [\textit{D. Yu. Grigor'ev} and \textit{N. N. Vorobjov}, Comput. Complexity 2, No. 2, 133--186 (1992; Zbl 0900.68253)] provides the first results in the semialgebraic setting. After that many other results have been obtained, and it is worthwhile mentioning the much more recent paper [\textit{S. Basu} and \textit{M. Kettner}, Discrete Comput. Geom. 39, No. 4, 734--746 (2008; Zbl 1185.14051)]. As far as the reviewer recall, the article by Benedetti, Loeser and Risler is the first one that combines the knowledge of known formulae for Betti numbers of nonsingular complete intersections in complex projective spaces and Smith inequality to find upper bounds for the Betti numbers of semialgebraic sets, and this is the basis of the quoted work by S. Basu and M. Kettner and also for the paper under review. The article is very well written and it contains some nice applications. Among them let us quote that the authors improve the known better bound on the number of geometric permutations of \(n\) well-separated convex bodies in \(R^d\) induced by \(k\)-transversals.