On the equivariant Betti numbers of symmetric definable sets: vanishing, bounds and algorithms

DOI10.1007/S00029-018-0401-7MaRDI QIDQ1783975zbMATH OpenOpenAlexFDO

Authors Saugata Basu, Cordian Riener

Publication date 21 September 2018

Published in Selecta Mathematica. New Series (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1610.04946

zbMATH Keywords

Betti numberscomputational complexityequivariant cohomologysymmetric semi-algebraic sets

Mathematics Subject Classification ID

Classical real and complex (co)homology in algebraic geometry (14F25) Semialgebraic sets and related spaces (14P10) Symbolic computation and algebraic computation (68W30)

Abstract: Let $mathrmR$ 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}^{lfloord/2floor-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<dlls,k$. This bound is tight up to a factor depending only on $d$. These results significantly improve upon those obtained previously 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 $mathrmR$. 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.

Recommendations

• Bounding the equivariant Betti numbers of symmetric semi-algebraic sets
• Vandermonde varieties, mirrored spaces, and the cohomology of symmetric semi-algebraic sets
• Efficient algorithms for computing the Euler-Poincaré characteristic of symmetric semi-algebraic sets
• scientific article; zbMATH DE number 1256759
• On the isotypic decomposition of cohomology modules of symmetric semi-algebraic sets: polynomial bounds on multiplicities

Cites work

• A theorem on the escape from the space of hyperbolic polynomials
• Algorithms in real algebraic geometry
• Approximation of definable sets by compact families, and upper bounds on homotopy and homology
• Betti number bounds, applications and algorithms
• Bounding the equivariant Betti numbers of symmetric semi-algebraic sets
• Combinatorial complexity in o-minimal geometry
• Efficient algorithms for computing the Euler-Poincaré characteristic of symmetric semi-algebraic sets
• scientific article; zbMATH DE number 1264799 (Why is no real title available?)
• scientific article; zbMATH DE number 1160037 (Why is no real title available?)
• scientific article; zbMATH DE number 3223507 (Why is no real title available?)
• scientific article; zbMATH DE number 3235051 (Why is no real title available?)
• scientific article; zbMATH DE number 3053541 (Why is no real title available?)
• Hyperbolic polynomials and Vandermonde mappings
• Inequalities defining orbit spaces
• Moments of random variables and the equivariant Morse lemma
• Multi-degree bounds on the Betti numbers of real varieties and semi-algebraic sets and applications
• On a theory of computation and complexity over the real numbers: 𝑁𝑃- completeness, recursive functions and universal machines
• On the Piano Movers problem. II: General techniques for computing topological properties of real algebraic manifolds
• On the Betti Numbers of Real Varieties
• On the geometric properties of Vandermonde's mapping and on the problem of moments

Cited in

(6)

• Vandermonde varieties, mirrored spaces, and the cohomology of symmetric semi-algebraic sets
• Bounding the equivariant Betti numbers of symmetric semi-algebraic sets
• On the isotypic decomposition of cohomology modules of symmetric semi-algebraic sets: polynomial bounds on multiplicities
• Real root finding for equivariant semi-algebraic systems
• Connectivity in symmetric semi-algebraic sets
• Deciding connectivity in symmetric semi-algebraic sets

This page was built for publication: On the equivariant Betti numbers of symmetric definable sets: vanishing, bounds and algorithms

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1783975)