On a real analogue of Bezout inequality and the number of connected components of sign conditions

Abstract

Let $\mathrm{R}$ be a real closed field and $Q_1,\dots ,Q_{\ell }\in \mathrm{R}[X_1,\dots ,X_k]$ such that for each $i,1\le i\le \ell$, $\mathrm{deg}(Q_i)\le d_i$. For $1\le i\le \ell$, denote by ${\mathcal{Q}}_i=\{Q_1,\dots ,Q_i\}$, $V_i$ the real variety defined by ${\mathcal{Q}}_i$, and $k_i$ an upper bound on the real dimension of $V_i$ (by convention $V_0={\mathrm{R}}^k$ and $k_0=k$). Suppose also that \[ 2 \leq d_1 \leq d_2 \leq \frac{1}{k + 1} d_3 \leq \frac{1}{(k + 1)^2} d_4 \leq \cdots \leq \frac{1}{(k + 1)^{\ell - 3}} d_{\ell - 1} \leq \frac{1}{(k + 1)^{\ell - 2}} d_{\ell}, \] and that $\ell \le k$. We prove that the number of semi-algebraically connected components of $V_{\ell }$ is bounded by \[ O (k)^{2 k} \left(\prod_{1 \leq j < \ell} d_j^{k_{j - 1} - k_j} \right) d_{\ell}^{k_{\ell - 1}}. \] This bound can be seen as a weak extension of the classical Bezout inequality (which holds only over algebraically closed fields and is false over real closed fields) to varieties defined over real closed fields. Additionally, if $\mathcal{P}\subset \mathrm{R}[X_1,\dots ,X_k]$ is a finite family of polynomials with $\mathrm{deg}(P)\le d$ for all $P\in \mathcal{P}$, $\mathrm{card}(\mathcal{P})=s$, and $d_{\ell }\le \frac{1}{k+1}d$, we prove that the number of semi-algebraically connected components of the realizations of all realizable sign conditions of the family $\mathcal{P}$ restricted to $V_{\ell }$ is bounded by \[ O (k)^{2 k} (s d)^{k_{\ell}} \left(\prod_{1 \leq j \leq \ell} d_j^{k_{j - 1} - k_j} \right). \]

34 pages, 7 figures. Final version to appear in Proc. London Math. Soc

Cited by in corpus (2)

• Distinct distances on algebraic curves in the plane
• Multilevel polynomial partitions and simplified range searching