8
$\begingroup$

The symmetric group $S_n$ acts on $\mathbb C^n$ by permuting the coordinates. In this case the ring of invariants is generated by elementary symmetric polynomials in n-variables. Now consider the regular representation of $S_n$, the basis of this vector space is indexed by the elements of $S_n$. Then what are the generators for the ring of invariants ? Is there a reference where the generators are given explicitly ? What are the degrees of the generators ?

$\endgroup$
12
$\begingroup$

To the best of my knowledge this is an open problem. In fact, there is strong evidence that the problem is very hard indeed: Consider the action of $S_n$ on the "two-sets," i.e., on the subsets of $\{1,\ldots,n\}$ of two elements. It is easy to see that this is a subrepresentation of the regular representation. So if generating invariants for the regular representation are known, then these map to generating invariants for the action on the two-sets, so they are also known. But such invariants have only been canclulated for $n \le 5$.

The invariants for the action on two-sets are interesting because they provide a way to decide the graph isomorphism problem. So this provides further evidence for the hardness of the problem: If there were an easy way of giving generating invariants for the regular representation, there would also be an easy way to decide the graph isomorphism problem.

You can find some background on this in Chapter 5 of the book "Computational Invariant Theory" by Harm Derksen and Gregor Kemper.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.