On Bounding the Betti Numbers and Computing the Euler Characteristic of Semi-Algebraic Sets

In this paper we prove new bounds on the sum of the Betti numbers of closed semi-algebraic sets and also give the first single exponential time algorithm for computing the Euler characteristic of arbitrary closed semi-algebraic sets. Given a closed semi-algebraic set S R ^k defined as the intersection of a real variety, Q=0, deg(Q)≤d, whose real dimension is k', with a set defined by a quantifier-free Boolean formula with no negations with atoms of the form P _i =0, P _i ≥ 0, P _i ≤ 0, deg(P _i ) ≤ d, 1≤ i≤ s, we prove that the sum of the Betti numbers of S is bounded by s ^k' (O(d)) ^k . This result generalizes the Oleinik—Petrovsky—Thom—Milnor bound in two directions. Firstly, our bound applies to arbitrary unions of basic closed semi-algebraic sets, not just for basic semi-algebraic sets. Secondly, the combinatorial part (the part depending on s ) in our bound, depends on the dimension of the variety rather than that of the ambient space. It also generalizes the result in 4] where a similar bound is proven for the number of connected components. We also prove that the sum of the Betti numbers of S is bounded by s ^k' 2 ^{O(k2 m4)} in case the total number of monomials occurring in the polynomials in is m. Using the tools developed for the above results, as well as some additional techniques, we give the first single exponential time algorithm for computing the Euler characteristic of arbitrary closed semi-algebraic sets. Received September 9, 1997, and in revised form March 18, 1998, and October 5, 1998.