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 (resp., ) bounded by d (resp., d ₀). Let $V \subset {\textnormal {R}}^{k}$ be the real algebraic variety defined by the polynomials in 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 on V is bounded by where , 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 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 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).