Bounding the Betti numbers and computing the Euler–Poincaré characteristic of semi-algebraic sets defined 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 be a real closed field, , with , , , , and with , , , and a semi-algebraic set defined by a Boolean formula without negations, with atoms , , , . We prove that the sum of the Betti numbers of 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 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 .

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 defined by partly quadratic systems of polynomials. J. Eur. Math. Soc. 12 (2010), no. 2, pp. 529–553

DOI 10.4171/JEMS/208