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

### Saugata Basu

Purdue University, West Lafayette, United States### Dmitrii V. Pasechnik

Nanyang Technological University, Singapore, Singapore### Marie-Françoise Roy

Université de Rennes I, France

## Abstract

Let *R* be a real closed ﬁeld, * Q* ⊂ R[

*Y_1 , . . . ,*(

*Y__l*,*X_1 , . . . ,*(*Xk*], with deg_Y*Q*) ≤ 2, deg_X*Q*) ≤

*d*,

*Q*∈

*, #(*

**Q***) =*

**Q***m*, and

*⊂ R[*

**P***X_1, . . . ,*(

*Xk*] with deg_X*P*) ≤

*d*,

*P*∈

*, #(*

**P***) =*

**P***s*, and

*S*⊂

*R__l*+

*k*a semi-algebraic set deﬁned by a Boolean formula without negations, with atoms

*P*= 0,

*P*≥ 0,

*P*≤ 0,

*P*∈

*∪*

**P***. We prove that the sum of the Betti numbers of*

**Q***S*is bounded by

*l_2 ( O(s + l + m)ld)k+2_m*.

This is a common generalization of previous results in [4] and [3] on bounding the Betti numbers of closed semi-algebraic sets deﬁned 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 [4, 9]. The complexity of the algorithm is bounded by (*lsmd*)*O*(*m*(*m*+*k*)).

## Cite this article

Saugata Basu, Dmitrii V. Pasechnik, Marie-Françoise Roy, Bounding the Betti numbers and computing the Euler–Poincaré characteristic of semi-algebraic sets deﬁned by partly quadratic systems of polynomials. J. Eur. Math. Soc. 12 (2010), no. 2, pp. 529–553

DOI 10.4171/JEMS/208