Refined bounds on the number of connected components of sign conditions on a variety

Abstract: Let

R

be a real closed field,

m a t h c a l P, m a t h c a l Q s u b s e t R [X_{1}, ..., X_{k}]

finite subsets of polynomials, with the degrees of the polynomials in

m a t h c a l P

(resp.

m a t h c a l Q

) bounded by

d

(resp.

d_{0}

). Let

V s u b s e t R^{k}

be the real algebraic variety defined by the polynomials in

m a t h c a l Q

and suppose that the real dimension of

V

is bounded by

k^{'}

. We prove that the number of semi-algebraically connected components of the realizations of all realizable sign conditions of the family

m a t h c a l P

on

V

is bounded by

displaylines{sum_{j=0}^{k'}4^j{s +1choose j}F_{d,d_0,k,k'}(j),}

where

s = c a r d; m a t h c a l P

, and

F_{d,d_0,k,k'}(j)= extstyle�inom{k+1}{k-k'+j+1} ;(2d_0)^{k-k'}d^j; max{2d_0,d}^{k'-j} +2(k-j+1) .

In case

2 d_{0} l e q d

, the above bound can be written simply as

displaylines{sum_{j = 0}^{k'} {s+1 choose j}d^{k'} d_0^{k-k'} O(1)^{k} = (sd)^{k'} d_0^{k-k'} O(1)^k}

(in this form the bound was suggested by J. Matousek. Our result improves in certain cases (when

d_{0} l l d

) the best known bound of

sum_{1 leq j leq k'} �inom{s}{j} 4^{j} d(2d-1)^{k-1}

on the same number proved earlier in the case

d = d_{0}

. The distinction between the bound

d_{0}

on the degrees of the polynomials defining the variety

V

and the bound

d

on the degrees of the polynomials in

m a t h c a l P

that appears in the new bound is motivated by several applications in discrete geometry.

Review text

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.

Recommendations

Cites work

Cited in

(38)

This page was built for publication: Refined bounds on the number of connected components of sign conditions on a variety

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q411399)