# 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_{ℓ},X_{1},…,X_{k}]$, with $deg_{Y}(Q)≤2$, $deg_{X}(Q)≤d$, $Q∈Q$, $#(Q)=m$, and $P⊂R[X_{1},…,X_{k}]$ with $deg_{X}(P)≤d$, $P∈P$, $#(P)=s$, and $S⊂R_{ℓ+k}$ a semi-algebraic set deﬁned by a Boolean formula without negations, with atoms $P=0$, $P≥0$, $P≤0$, $P∈P∪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 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 (Basu, 1999; Basu 2006). The complexity of the algorithm is bounded by $(ℓsmd)_{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