Vandermonde varieties, mirrored spaces, and the cohomology of symmetric semi-algebraic sets

Abstract

Let $\mathrm{R}$ be a real closed field. We prove that for each fixed $\ell ,d\ge 0$, there exists an algorithm that takes as input a quantifier-free first order formula $\Phi$ with atoms $P=0,P>0,P<0\text{ with }P\in \mathcal{P}\subset \mathrm{D}[X_1,\dots ,X_k{]}_{\le d}^{{\mathfrak{S}}_k}$, where $\mathrm{D}$ is an ordered domain contained in $\mathrm{R}$, and computes the ranks of the first $(\ell +1)$ cohomology groups, of the symmetric semi-algebraic set defined by $\Phi$. The complexity of this algorithm (measured by the number of arithmetic operations in $\mathrm{D}$) is bounded by a \emph{polynomial} in $k$ and $\mathrm{card}(\mathcal{P})$ (for fixed $d$ and $\ell$). This result contrasts with the $\mathbf{PSPACE}$-hardness of the problem of computing just the zero-th Betti number (i.e. the number of semi-algebraically connected components) in the general case for $d\ge 2$ (taking the ordered domain $\mathrm{D}$ to be equal to $\mathbb{Z}$). The above algorithmic result is built on new representation theoretic results on the cohomology of symmetric semi-algebraic sets. We prove that the Specht modules corresponding to partitions having long lengths cannot occur with positive multiplicity in the isotypic decompositions of low dimensional cohomology modules of closed semi-algebraic sets defined by symmetric polynomials having small degrees. This result generalizes prior results obtained by the authors giving restrictions on such partitions in terms of their ranks, and is the key technical tool in the design of the algorithm mentioned in the previous paragraph.

58 pages. Final version published in Found. Comput. Math

References in corpus (5)

• Computing the homology of basic semialgebraic sets in weak exponential time
• Computing the Top Betti Numbers of Semi-algebraic Sets Defined by Quadratic Inequalities in Polynomial Time
• Computing the Homology of Semialgebraic Sets. II: General formulas
• Computing the Homology of Semialgebraic Sets I: Lax Formulas
• Efficient algorithms for computing the Euler-Poincaré characteristic of symmetric semi-algebraic sets

Cited by in corpus (1)

• Faster real root decision algorithm for symmetric polynomials