Bounding the Betti numbers and computing the Euler-Poincaré characteristic of semi-algebraic sets defined by partly quadratic systems of polynomials (Q967467): Difference between revisions

The aim of this paper is to bound the Betti-numbers of semi-algebraic sets defined by polynomial inequalities, in which the dependence of the polynomials on a subset of the variables is at most quadratic. The main result is the following: Let \(R\) be a real closed field, \(P_1, \ldots, P_s, Q_1, \ldots, Q_m \in R[Y_1, \ldots, Y_{\ell}, X_1, \ldots, X_k]\) polynomials such that \[ \deg_Y(P_i) = 0, \; \deg_X(P_i) \leq d, \; \deg_Y(Q_j) \leq 2, \; \deg_X(Q_j) \leq d, \] and \(S \subset R^{k+\ell}\) a closed semi-algebraic set defined by a Boolean formula without negations, with atoms \(f=0\), \(f \geq 0\), \(f \leq 0\), where \(f \in \{P_1, \ldots, P_s, Q_1, \ldots, Q_m\}\). Then the sum of the Betti-numbers of \(S\), denoted by \(b(S)\), satisfies the inequality \[ b(S) \leq \ell^2 \left( \, O(s + \ell + m) \, ld \, \right)^{k + 2m}. \] The techniques used in this paper to find the tight bounds on the Betti numbers also allows to design an efficient algorithm for computing the Euler-Poincaré characteristic. This algorithm has better complexity than the ones known before. More precisely, the authors prove the existence of an algorithm to compute the Euler-Poincaré characteristic of a semi-algebraic set \(S\) as above whose complexity is bounded by \((\ell s m d)^{O (m(m+k))}\).