On the Betti numbers of sign conditions

Abstract:

Let $\mathrm {R}$ be a real closed field and let ${\mathcal Q}$ and ${\mathcal P}$ be finite subsets of $\mathrm {R}[X_1,\ldots ,X_k]$ such that the set ${\mathcal P}$ has $s$ elements, the algebraic set $Z$ defined by $\bigwedge _{Q \in {\mathcal Q}}Q=0$ has dimension $k’$ and the elements of${\mathcal Q}$ and ${\mathcal P}$ have degree at most $d$. For each $0 \leq i \leq k’,$ we denote the sum of the $i$-th Betti numbers over the realizations of all sign conditions of ${\mathcal P}$ on $Z$ by $b_i({\mathcal P},{\mathcal Q})$. We prove that \[ b_i({\mathcal P},{\mathcal Q}) \le \sum _{j=0}^{k’ - i} {s \choose j} 4^{j} d(2d-1)^{k-1}. \] This generalizes to all the higher Betti numbers the bound ${s \choose k’}O(d)^k$ on $b_0({\mathcal P},{\mathcal Q})$. We also prove, using similar methods, that the sum of the Betti numbers of the intersection of $Z$ with a closed semi-algebraic set, defined by a quantifier-free Boolean formula without negations with atoms of the form $P \geq 0$ or $P\leq 0$ for $P\in {\mathcal P}$, is bounded by \[ \sum _{i = 0}^{k’}\sum _{j = 0}^{k’ - i} {s \choose j} 6^{j} d(2d-1)^{k-1}, \] making the bound $s^{k’} O(d)^k$ more precise.