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

Abstract

Let $\mathbb{R}$ be a real closed field, $\mathcal{P},\mathcal{Q}\subset \mathbb{R}[X_1,...,X_k]$ finite subsets of polynomials, with the degrees of the polynomials in $\mathcal{P}$ (resp. $\mathcal{Q}$) bounded by $d$ (resp. $d_0$). Let $V\subset {\mathbb{R}}^k$ be the real algebraic variety defined by the polynomials in $\mathcal{Q}$ and suppose that the real dimension of $V$ is bounded by $k^{\prime }$. We prove that the number of semi-algebraically connected components of the realizations of all realizable sign conditions of the family $\mathcal{P}$ on $V$ is bounded by $$ \displaylines{\sum_{j=0}^{k'}4^j{s +1\choose j}F_{d,d_0,k,k'}(j),}$$ where $s = \card \; \mathcal{P}$, and $$F_{d,d_0,k,k^{\prime }}(j)=\left(\genfrac{}{}{0ex}{}{k+1}{k-k^{\prime }+j+1}\right)(2d_0{)}^{k-k^{\prime }}{d}^j\max {2d_0,d}^{k^{\prime }-j}+2(k-j+1).$$ In case $2d_0\le 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\ll d$) the best known bound of $$\sum _{1\le j\le k^{\prime }}\left(\genfrac{}{}{0ex}{}{s}{j}\right)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 $\mathcal{P}$ that appears in the new bound is motivated by several applications in discrete geometry.

Bound made more precise and references added. Final version to appear in Discrete and Computational Geometry