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

Let $\mathbb{R}$ be a real closed field, $$\mathcal{P}$,$\mathcal{Q}$ \subset \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^{\mathrm{\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 $$\text{displaylines}\sum _{j=0}^{k^{\mathrm{\prime }}}{4}^j\left(\genfrac{}{}{0px}{}{s+1}{j}\right)F_{d,d_0,k,k^{\mathrm{\prime }}}(j),$$ where $s=\text{card}\mathcal{P}$, and $$F_{d,d_0,k,k^{\mathrm{\prime }}}(j)=\left(\genfrac{}{}{0px}{}{k+1}{k-k^{\mathrm{\prime }}+j+1}\right)(2d_0{)}^{k-k^{\mathrm{\prime }}}{d}^j\max {2d_0,d}^{k^{\mathrm{\prime }}-j}+2(k-j+1)\mathrm{.}$$ In case $2d_0\le d$, the above bound can be written simply as $$\text{displaylines}\sum _{j=0}^{k^{\mathrm{\prime }}}\left(\genfrac{}{}{0px}{}{s+1}{j}\right)d^{k^{\mathrm{\prime }}}{d}_0^{k-k^{\mathrm{\prime }}}O(1{)}^k=(sd{)}^{k^{\mathrm{\prime }}}{d}_0^{k-k^{\mathrm{\prime }}}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^{\mathrm{\prime }}}\left(\genfrac{}{}{0px}{}{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.