Bounding the Betti numbers and computing the Euler–Poincaré characteristic of semi-algebraic sets defined by partly quadratic systems of polynomials

Abstract

Let $\mathrm{R}$ be a real closed field, $\mathcal{Q}\subset \mathbb{R}[Y_1,\dots ,Y_{\ell },X_1,\dots ,X_k]$, with ${\mathrm{deg}}_Y(Q)\le 2$, ${\mathrm{deg}}_X(Q)\le d$, $Q\in \mathcal{Q}$, $\#(\mathcal{Q})=m$, and $\mathcal{P}\subset \mathrm{R}[X_1,\dots ,X_k]$ with ${\mathrm{deg}}_X(P)\le d$, $P\in \mathcal{P}$, $\#(\mathcal{P})=s$, and $S\subset {\mathrm{R}}^{\ell +k}$ a semi-algebraic set defined by a Boolean formula without negations, with atoms $P=0$, $P\ge 0$, $P\le 0$, $P\in \mathcal{P}\cup \mathcal{Q}$. We prove that the sum of the Betti numbers of $S$ is bounded by

This is a common generalization of previous results in (Basu, 1999) and (Barvinok, 1997) on bounding the Betti numbers of closed semi-algebraic sets defined by polynomials of degree $d$ and 2, respectively. We also describe an algorithm for computing the Euler–Poincaré characteristic of such sets, e generalizing similar algorithms described in (Basu, 1999; Basu 2006). The complexity of the algorithm is bounded by $(\ell smd{)}^{O(m(m+k))}$.