Abstract
Let \(\mathrm {R}\) be a real closed field. We prove that for any fixed d, the equivariant rational cohomology groups of closed symmetric semi-algebraic subsets of \(\mathrm {R}^k\) defined by polynomials of degrees bounded by d vanishes in dimensions d and larger. This vanishing result is tight. Using a new geometric approach we also prove an upper bound of \(d^{O(d)} s^d k^{\lfloor d/2 \rfloor -1} \) on the equivariant Betti numbers of closed symmetric semi-algebraic subsets of \(\mathrm {R}^k\) defined by quantifier-free formulas involving s symmetric polynomials of degrees bounded by d, where \(1 < d \ll s,k\). This bound is tight up to a factor depending only on d. These results significantly improve upon those obtained previously in Basu and Riener (Adv Math 305:803–855, 2017) which were proved using different techniques. Our new methods are quite general, and also yield bounds on the equivariant Betti numbers of certain special classes of symmetric definable sets (definable sets symmetrized by pulling back under symmetric polynomial maps of fixed degree) in arbitrary o-minimal structures over \(\mathrm {R}\). Finally, we utilize our new approach to obtain an algorithm with polynomially bounded complexity for computing these equivariant Betti numbers. In contrast, the problem of computing the ordinary Betti numbers of (not necessarily symmetric) semi-algebraic sets is considered to be an intractable problem, and all known algorithms for this problem have doubly exponential complexity.
Similar content being viewed by others
References
Arnold, V.I.: Hyperbolic polynomials and Vandermonde mappings. Funktsional. Anal. i Prilozhen. 20(2), 52–53 (1986)
Basu, S.: Combinatorial complexity in o-minimal geometry. Proc. Lond. Math. Soc. (3) 100, 405–428 (2010). (an extended abstract appears in the Proceedings of the ACM Symposium on the Theory of Computing, 2007)
Basu, S., Pollack, R., Roy, M.-F.: Betti Number Bounds, Applications and Algorithms, Current Trends in Combinatorial and Computational Geometry: Papers from the Special Program at MSRI. MSRI Publications, vol. 52, pp. 87–97. Cambridge University Press (2005)
Basu, S., Pollack, R., Roy, M.-F.: Algorithms in Real Algebraic Geometry, Algorithms and Computation in Mathematics, vol. 10, 2nd edn. Springer, Berlin (2006)
Basu, S., Riener, C.: On the isotypic decomposition of cohomology modules of symmetric semi-algebraic sets: polynomial bounds on multiplicities, ArXiv e-prints (2015)
Basu, S., Riener, C.: Bounding the equivariant Betti numbers of symmetric semi-algebraic sets. Adv. Math. 305, 803–855 (2017)
Basu, S., Riener, C.: Efficient algorithms for computing the Euler-Poincaré characteristic of symmetric semi-algebraic sets. Ordered Algebraic Structures and Related Topics, Contemporary Mathematics, vol. 697, pp. 51–79. American Mathematical Society, Providence, RI (2017)
Basu, S., Rizzie, A.: Multi-degree bounds on the betti numbers of real varieties and semi-algebraic sets and applications. Discrete Comput. Geom. (2017)
Blum, L., Shub, M., Smale, S.: On a theory of computation and complexity over the real numbers: NP-completeness, recursive functions and universal machines. Bull. Amer. Math. Soc. (N.S.) 21(1), 1–46 (1989)
Bröcker, L.: On symmetric semialgebraic sets and orbit spaces. Banach Cent. Publ. 44(1), 37–50 (1998)
Coste, M.: An introduction to o-minimal geometry, Istituti Editoriali e Poligrafici Internazionali, Pisa, 2000: Dip. Mat. Univ, Pisa, Dottorato di Ricerca in Matematica
Gabrielov, A., Vorobjov, N.: Approximation of definable sets by compact families, and upper bounds on homotopy and homology. J. Lond. Math. Soc. (2) 80(1), 35–54 (2009)
Givental, A.: Moments of random variables and the equivariant morse lemma. Rus. Math. Surv. 42(2), 275–276 (1987)
Kostov, V.P.: On the geometric properties of vandermonde’s mapping and on the problem of moments. Proc. R. Soc. Edinb. Sect. A Math. 112(3–4), 203–211 (1989)
Meguerditchian, Ivan: A theorem on the escape from the space of hyperbolic polynomials. Math. Z. 211(3), 449–460 (1992)
Milnor, J.: On the Betti numbers of real varieties. Proc. Am. Math. Soc. 15, 275–280 (1964)
Petrovskiĭ, I.G., Oleĭnik, O.A.: On the topology of real algebraic surfaces. Izvestiya Akad. Nauk SSSR. Ser. Mat. 13, 389–402 (1949)
Procesi, C., Schwarz, G.: Inequalities defining orbit spaces. Invent. Math. 81(3), 539–554 (1985)
Reif, J.H.: Complexity of the mover’s problem and generalizations, Proceedings of the 20th Annual Symposium on Foundations of Computer Science (Washington, DC, USA), SFCS ’79, IEEE Computer Society, pp. 421–427 (1979)
Schwartz, J., Sharir, M.: On the piano movers’ problem ii. General techniques for computing topological properties of real algebraic manifolds. Adv. Appl. Math. 4, 298–351 (1983)
Spanier, E.H.: Algebraic Topology. McGraw-Hill Book Co., New York (1966)
Thom, R.: Sur l’homologie des variétés algébriques réelles, Differential and Combinatorial Topology (A Symposium in Honor of Marston Morse), pp. 255–265. Princeton University Press, Princeton, NJ (1965)
van den Dries, L.: Tame Topology and o-Minimal Structures, London Mathematical Society Lecture Note Series, vol. 248. Cambridge University Press, Cambridge (1998)
Acknowledgements
The research presented in this article was initiated during a stay of the authors at Fields Institute as part of the Thematic Program on Computer Algebra and the authors would like to thank the organizers of this event.
Author information
Authors and Affiliations
Corresponding author
Additional information
Basu was also partially supported by NSF Grants CCF-1618918 and DMS-1620271.
Rights and permissions
About this article
Cite this article
Basu, S., Riener, C. On the equivariant Betti numbers of symmetric definable sets: vanishing, bounds and algorithms. Sel. Math. New Ser. 24, 3241–3281 (2018). https://doi.org/10.1007/s00029-018-0401-7
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00029-018-0401-7