Refined Bounds on the Number of Connected Components of Sign Conditions on a Variety

Let \({\textnormal {R}}\) be a real closed field, \(\mathcal{P},\mathcal{Q} \subset {\textnormal {R}}X_{1},\ldots,X_{k}]\) finite subsets of polynomials, with the degrees of the polynomials in \(\mathcal{P}\) (resp., \(\mathcal{Q}\)) bounded by d (resp., d ₀). Let \(V \subset {\textnormal {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′. 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

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

where \(s = \operatorname {card}\mathcal{P}\), and

$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 2d ₀≤d, the above bound can be written simply as

$\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 Matousek 2011). Our result improves in certain cases (when d ₀?d) the best known bound of

$\sum_{1 \leq j \leq k'}\binom{s}{j} 4^{j} d(2d-1)^{k-1}$

on the same number proved in Basu et al. (Proc. Am. Math. Soc. 133(4):965–974, 2005) in the case d=d ₀.

The distinction between the bound d ₀ 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 (Guth and Katz in arXiv:1011.4105v1 math.CO], 2011; Kaplan et al. in arXiv:1107.1077v1 math.CO], 2011; Solymosi and Tao in arXiv:1103.2926v2 math.CO], 2011; Zahl in arXiv:1104.4987v3 math.CO], 2011).