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

Let \(R\) be a real closed field, \(D\) an ordered subdomain in \(R\) and \(\mathcal{P}\) a family of symmetric polynomials in \(k\) variables of degree \(\leq d\) over \(D\). The algorithmic problem of computing Betti numbers of arbitrary semi-algebraic subsets of \(R^k\) is well-studied and has applications in the theory of computational complexity and in robot motion planning. Betti numbers of semi-algebraic subsets of \(R^k\) satisfy a singly exponential (in \(k\)) complexity; singly exponential dependence on \(k\) of the bound is unavoidable. The authors prove that for each fixed \(\ell\), \(d\geq 0\), there exists an algorithm that takes as input a quantifier-free first-order formula \(\Phi\) with atoms \(P=0\), \(P>0\), \(P<0\) with \(P\in \mathcal{P}\), 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 \(D\)) is bounded by a polynomial in \(k\) and card(\(\mathcal{P}\)) (for fixed \(d\) and \(\ell\)). This result contrasts with the PSPACE-hardness of the problem of computing just the zeroth Betti number (i.e., the number of semi-algebraically connected components) in the general case for \(d\geq 2\) (taking the ordered domain \(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. The authors prove that the Specht modules corresponding to partitions having long lengths cannot occur 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.