MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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 ?

share|cite|improve this question
up vote 11 down vote accepted

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.

share|cite|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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