JournalsjemsVol. 12 , No. 2DOI 10.4171/jems/208

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
Bounding the Betti numbers and computing the Euler–Poincaré characteristic of semi-algebraic sets defined by partly quadratic systems of polynomials cover

Abstract

Let R be a real closed field, Q ⊂ R[Y_1 , . . . , Y__l, X_1 , . . . , Xk], with deg_Y(Q) ≤ 2, deg_X(Q) ≤ d, QQ, #(Q) = m, and P ⊂ R[X_1, . . . , Xk] with deg_X(P) ≤ d, PP, #(P) = s, and SR__l+k a semi-algebraic set defined by a Boolean formula without negations, with atoms P = 0, P ≥ 0, P ≤ 0, PPQ. We prove that the sum of the Betti numbers of 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 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 [4, 9]. The complexity of the algorithm is bounded by (lsmd)O(m(m+k)).