Bounding the equivariant Betti numbers and computing the generalized Euler-Poincaré characteristic of symmetric semi-algebraic sets.
Saugata Basu, Cordian Riener · arXiv (Cornell University) · 2013
Let R be a real closed field. The problem of obtaining tight bounds on the Betti numbers of semi-algebraic subsets of R k in terms of the number and degrees of the defining polynomials has been an important problem in real algebraic geometry with the first results due to Oleĭnik and Petrovskiĭ, Thom and Milnor. These bounds are all exponential in the number of variables k. Motivated by several applications in real algebraic geometry, as well as in theoretical computer science, where such bounds have found applications, we consider in this paper the problem of bounding the equivariant Betti numbers of symmetric algebraic and semialgebraic subsets of R k. We obtain several asymptotically tight upper bounds. In particular, we prove that if S ⊂ R k is a semi-algebraic subset defined by a finite set of s symmetric polynomials of degree at most d, then the sum of the Sk-equivariant Betti numbers of S with coefficients in Q is bounded by (skd) O(d). Unlike the classical bounds on the ordinary Betti numbers of real algebraic varieties and semi-algebraic sets, the above bound is polynomial in k when the degrees of the defining polynomials are bounded by a constant. As an application we improve the best known bound on the ordinary Betti numbers of the projection of a compact semi-algebraic set improving for any fixed degree the best previously known bound for this problem due to Gabrielov, Vorobjov and Zell. As another application of our methods we obtain polynomial time (for fixed degrees) algorithms for computing the generalized Euler-Poincaré characteristic of semi-algebraic sets defined by symmetric polynomials. This is in contrast to the best complexity of the known algorithms for the same problem in the nonsymmetric situation, which is singly exponential. This singly exponential complexity for the latter problem is unlikely to be improved because of hardness result (#P-hardness) coming from discrete complexity theory.