Vandermonde Varieties, Mirrored Spaces, and the Cohomology of Symmetric Semi-algebraic Sets

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,\ldots ,X_k]^{\mathfrak {S}_k}_{\le d}\), 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 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 zeroth 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 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.

1. The theorem in [29] is not stated using the language of non-Archimedean extensions and Puiseux series but it is easy to translate it into the form stated here.

We thank the anonymous referees for many suggestions that helped us improve the paper. In particular, we are grateful to one of the referees for pointing out an error in the proof of Proposition 3 (which also caused Algorithm 1 to be erroneous) in the previous version of this paper.

We also thank the Institut Henri Poincaré in Paris for hosting us during the period when this work was conceived.

Authors and Affiliations

1. Department of Mathematics, Purdue University, West Lafayette, IN, 47906, USA

   Saugata Basu

2. Department of Mathematics and Statistics, UiT The Arctic University of Norway, 9037, Tromsö, Norway

   Cordian Riener

Corresponding author

Correspondence to Saugata Basu.

Communicated by Peter Bürgisser.

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Basu was partially supported by NSF Grants CCF-1618918, DMS-1620271 and CCF-1910441. Riener was supported by TFS Grant 17_matte_CR.

Appendix A.

This section is divided into two subsections. The first subsection consists of fairly standard material on representation theory of finite groups, and in the second subsection we discuss the representation theory of the symmetric groups. We chose to include this in order to make the paper reasonably self-contained. A standard reference for this material for this material is Serre’s classic book [42]. However, in Serre’s book the field of scalars is taken (in most parts) to be algebraically closed. Since we consider representations over \(\mathbb {Q}\), we refer the reader to the book [37] for the basic results listed below.

1.1 A.1. A Quick Digest of Representation Theory of Finite Groups

In this paper we only consider group representations over the field \(\mathbb {Q}\). So all vector spaces in the following are finite-dimensional \(\mathbb {Q}\)-vector spaces and all groups are finite.

Definition 13

(Representations of a group G). A representation of a group G is a group homomorphism \(\rho :G \rightarrow \mathrm {GL}(V)\) for some vector space V. The representation \(\rho \) induces a left action of the group G on the vector space V, by \(g \cdot v = \rho (g)(v), v \in V\), making V into a left G-module. We will use the language of representations and modules interchangeably.

We call \(\dim _\mathbb {Q}V\) the dimension of the representation \(\rho \).

Definition 14

(Morphism of representations). Given two representations \(\rho _1: G \rightarrow \mathrm {GL}(V_1), \rho _2: G \rightarrow \mathrm {GL}(V_2)\), a homomorphism \(T: V_1 \rightarrow V_2\) is a morphism of G-modules (or equivalently, an intertwining operator) if it satisfies,

for all \(g \in G, v_1 \in V_1\).

The representations \(\rho _1,\rho _2\) are equivalent if there exists a morphism of G-modules \(T:V_1 \rightarrow V_2\) which is an isomorphism.

Two canonically defined examples will play an important role.

1. (A)

   The one-dimensional representation, corresponding to the constant homomorphism \(G \rightarrow \mathrm {Id}_V\), where V is a one-dimensional vector space is called the trivial representation of G (denoted \(1_{G}\)).

2. (B)

   Let \(A = \mathbb {Q}[G]\) denote the group algebra of G. Then, A has a natural structure of a left G-module. The corresponding representation is called the regular representation of G. The dimension of the regular representation of G is clearly equal to the order of the group G.

Definition 15

(Direct sums and tensor products of representations \(\cdot \oplus \cdot , \cdot \otimes \cdot , \cdot \boxtimes \cdot \)). Given two representations \(\rho _1:G \rightarrow V_1, \rho _2:G \rightarrow V_2\):

1. (A)

   One defines the representation \(\rho _1\oplus \rho _2:G \rightarrow \mathrm {GL}(V_1 \oplus V_2)\) by \((\rho _1\oplus \rho _2)(g)(v_1\oplus v_2) = \rho _1(g)(v_1) \oplus \rho _2(g)(v_2)\).

2. (B)

   Similarly the representation \(\rho _1\otimes \rho _2: G \rightarrow \mathrm {GL}(V_1 \otimes _\mathbb {Q}V_2)\) is defined by \((\rho _1 \otimes \rho _2)(g)(v_1 \otimes v_2) = \rho _1(g)(v_1) \otimes \rho _2(g)(v_2)\).

Given two representations \(\rho _1:G_1 \rightarrow \mathrm {GL}(V_1), \rho _2:G_2 \rightarrow \mathrm {GL}(V_2)\), we define a representation \(\rho _1 \boxtimes \rho _2: G_1 \times G_2 \rightarrow \mathrm {GL}(V_1\otimes _\mathbb {Q}V_2)\) of the direct product group \(G_1 \times G_2\) by

Definition 16

(Irreducible representations). A representation \(\rho :G \rightarrow \mathrm {GL}(V)\) is irreducible if V does not contain a nonzero proper sub-representation (i.e., a nonzero proper subspace \(W \subset V\) which is closed under \(\rho (g)\) for every \(g \in G\)).

Lemma 5

(Schur’s Lemma). [37, Corollary on page 151] Let \(\rho _1:G \rightarrow V_1, \rho _2:G \rightarrow V_2\) be two irreducible representations, and \(T:V_1\rightarrow V_2\) an intertwining operator. Then T is either 0 or an isomorphism.

Definition 17

Let \(\alpha \) be an isomorphism class of irreducible representations of a finite group G and let M be a finite-dimensional G-module. Let \(M^\alpha \) denote the sum of all submodules of M isomorphic to \(\alpha \). We call \(M^\alpha \) to be the isotypic component of M of type \(\alpha \).

With the same notation as in Definition 17:

Theorem 9

(Isotypic decomposition). [37, Theorem, Section 2.3] The isotypic components give a direct sum decomposition of M.

Moreover, Lemma 5 (Schur’s Lemma) implies the following.

Theorem 10

Suppose that M and N are two finite-dimensional G-module, \(\alpha \) an isomorphism class of irreducible G-modules and \(f:M \rightarrow N\) a morphism of G-modules. Then, there is a commutative diagram of G-module homomorphisms

where the vertical arrows are canonical projections.

Finally, with the same hypothesis as Definition 17:

Proposition 12

[37, Section 2.1, Corollaries 1,2] Each \(M^\alpha \) is (non-canonically) isomorphic to the direct sum of \(m_\alpha \) copies of the irreducible representation of type \(\alpha \) for some \(m_\alpha \ge 0\).

Definition 18

(Multiplicity). We will call the non-negative integer \(m_\alpha \) that appears in Proposition 12 to be the multiplicity of \(\alpha \) in M, and denote

It follows from Theorem 10 that \(\mathrm {mult}_\alpha (M)\) is well defined.

It is obvious that a representation of a group G restricts to a representation of any subgroup of G. It is less obvious how to lift a representation of a subgroup of G to a representation of G itself. There is in fact a canonically defined lift which is referred to as the induced representation. The notion of induced representations is used in Lemma 1 in the paper.

The construction of the induced representation is best stated in the language of modules. Let \(H \subset G\) be a subgroup of G, and let \(\rho :H \rightarrow V\) be a representation of H. Then V is naturally a left \(\mathbb {Q}[H]\)-module and \(\mathbb {Q}[G]\) a right \(\mathbb {Q}[H]\)-module.

Definition 19

(Induced representation). We denote by \(\mathrm {ind}_{H}^{G} V\) the left G-module \(\mathbb {Q}[G] \otimes _{\mathbb {Q}[H]} V\) (called the induced representation of V on G).

1.2 A.2. Representation Theory of Symmetric Groups

In this paper we are concerned with the representations of the symmetric groups \(\mathfrak {S}_k\) and certain subgroups of the symmetric groups. We state below the main definitions and results related to this very classical topic.

Notation 20

(Partitions and compositions). We denote by \(\mathrm {Par}(k)\) the set of partitions of k, where each partition \(\lambda \in \mathrm {Par}(k)\) (also denoted \(\lambda \vdash k\)) is a tuple \((\lambda _{1} , \lambda _{2} , \ldots , \lambda _{\ell })\), with \(\lambda _{1} \ge \lambda _{2} \ge \cdots \ge \lambda _{\ell } \ge 1\), and \(\lambda _{1} + \lambda _{2} + \cdots + \lambda _{\ell } =k\). We call \(\ell \) the length of the partition \(\lambda \), and denote \(\mathrm {length}(\lambda ) = \ell \).

A tuple \((\lambda _{1} , \lambda _{2} , \ldots , \lambda _{\ell })\), with \(\lambda _{1} + \lambda _{2} + \cdots + \lambda _{\ell } =k\) (but not necessarily non-increasing) will be called a composition, and we still call \(\ell \) the length of the composition \(\lambda \), and denote \(\mathrm {length}(\lambda ) = \ell \). The set of all compositions of k will be denoted by \(\mathrm {Comp}(k)\).

Notation 21

(Transpose of a partition). For a partition \(\lambda =(\lambda _1,\ldots ,\lambda _\ell ) \vdash k\), we will denote by \(^{t}\lambda \) the transpose of \(\lambda \). More precisely, \(^{t}\lambda = (^{t}\lambda _1, \ldots ,^{t}\lambda _{\tilde{\ell }})\), where \(^{t}\lambda _j = \mathrm {card}(\{i \mid \lambda _i \ge j \})\), and \(\tilde{\ell } = \lambda _1\).

Definition 20

(Young diagrams). Partitions are often identified with Young diagrams. We follow the English convention and associate the partition \(\lambda = (\lambda _1,\lambda _2,\ldots )\) with the Young diagram with its i-th row consisting of \(\lambda _i\) boxes. Thus, the Young diagram corresponding to the partition \(\lambda = (3,2)\) is

the Young diagram associated to its transpose, \(^{t}\lambda = (2,2,1)\), is

(note that the Young diagram of \(^{t}\lambda \) is obtained by reflecting the Young diagram of \(\lambda \) about its diagonal). Thus, for any partition \(\lambda \), \(\mathrm {length}(\lambda )\) (respectively \(\mathrm {length}(^t \lambda )\)) equals the number of rows (respectively columns) of the Young diagram of \(\lambda \) (respectively \(^t\lambda \)).

Definition 21

(Young’s tableau). A tableau on a given Young diagram corresponding to a partition \(\lambda \vdash k\) is a filling of its squares with \(1,\ldots , k\) (with no repetitions).

The representation theory of the symmetric groups, \(\mathfrak {S}_k\), is a classical subject (see, for example, [25] for details) and it is well known that the irreducible representations (Specht modules) of \(\mathfrak {S}_k\) are indexed by partitions of k.

These are defined as follows.

Definition 22

(Specht modules). Let \(A = \mathbb {Q}[\mathfrak {S}_k]\) be the group algebra of \(\mathfrak {S}_k\). Then A is a \(\mathbb {Q}\)-vector space of dimension k! and left multiplication by elements of \(\mathfrak {S}_k\) makes A into a \(\mathfrak {S}_k\)-module (usually referred to as the regular representation of the group \(\mathfrak {S}_k\)).

For \(\lambda \vdash k\), fix a tableau T on the Young diagram of \(\lambda \). Let \(P_\lambda \subset \mathfrak {S}_k\) be the set of permutations that stabilizes the rows of the tableau T, and similarly \(Q_\lambda \subset \mathfrak {S}_k\) be the set of permutations that fixes the columns of T.

Let

Then the left ideal \(A c_\lambda \) of A is an irreducible \(\mathfrak {S}_k\)-module, and we denote it \(\mathbb {S}^\lambda \) (the Specht module corresponding to \(\lambda \)). It is easy to check that for \(\lambda = (k)\), \(\mathbb {S}^{(k)}\) is isomorphic to the one-dimensional trivial representation which we will also denote by \(1_{\mathfrak {S}_k}\), and for \(\lambda = (1,\ldots ,1)\) (often denoted by \(1^k\)), the Specht module \(\mathbb {S}^{(1^k)}\) is isomorphic to the one-dimensional sign representation which we will also denote by \(\mathbf {sign}_k\).

Definition 23

(Hook lengths). Let \(B(\lambda )\) denote the set of boxes in the Young diagram (cf. Definition 20) corresponding to a partition \(\lambda \vdash k\). For a box \(b \in B(\lambda )\), the length of the hook of b, denoted \(h_b\) is the number of boxes strictly to the right and below b plus 1.

The following classical formula (due to Frobenius) gives the dimension of the representation \(\mathbb {S}^{\lambda }\) in terms of the hook lengths of the partition \(\lambda \).

Reprints and permissions