Computer package for representation theory of the symmetric group - MathOverflow

Computer package for representation theory of the symmetric group

2012-05-11T20:29:27Z

Is there a computer algebra package in which I can compute the following for representations of a specific symmetric group (e.g. $S_7$):

(1) $V \otimes W$

(2) $S_\lambda V$, where $S_\lambda$ is a Schur functor, or even just $\wedge^s V$,

where $V$ and $W$ are input as sums of irreducible representations, i.e. by partitions with coefficients, and output in the same format?

Answer by Wouter Meeussen for Computer package for representation theory of the symmetric group

2012-05-11T20:56:01Z

If you have access to Mathematica, then the functions in http://users.telenet.be/Wouter.Meeussen/ToolBox.nb might be of use.

Answer by Alexander Woo for Computer package for representation theory of the symmetric group

2012-05-11T21:04:11Z

The combinatorics package in Sage should do these things, at least if you are just interested in the decompositions into irreducibles and not actual matrices.

Answer by Alexander Woo for Computer package for representation theory of the symmetric group

2012-05-11T21:05:11Z

Another answer: John Stembridge's Maple code for dealing with Weyl groups may also have something along these lines.

Answer by Mark Wildon for Computer package for representation theory of the symmetric group

2012-05-11T21:06:32Z

Magma can be used to do (1) by taking products of characters, and (2) using the function 'Symmetrization', provided $|\lambda| \le 6$. In either case the output will be a character $\chi$ of a symmetric group. You can then write a short function that calculates all the inner products of $\chi$ with irreducible characters to get the answer in the form you want. The function 'SymmetricCharacter' returns the irreducible character labelled by a given partition.

Edit: Gap also has most of the required functions built-in. To generate the irreducible characters of $S_7$ use 'Irr(SymmetricGroup(7))'. You can then add and multiply characters to get the character of the tensor product of two representations of $S_7$. Then 'Symmetrizations(Irr(SymmetricGroup(7)),s)' computes $S_\lambda \chi$ for all irreducible characters of $S_7$ and all partitions $\lambda$ of $s$. This took almost no time to run, even for $s=10$, a case Magma fails on.

I'm not sure if Gap provides any way to determine the partition labelling an irreducible character of $S_n$. Before 'SymmetricCharacter' was introduced in Magma, I used some code of my own to identify the labelling partition, by first looking at the degree (using the hook-formula), and then resolving any ambiguities using classical formulae for the values of symmetric group characters on cycles of short length. Please send me an email if you'd like more details.

Answer by Natalie for Computer package for representation theory of the symmetric group

2012-05-11T21:20:32Z

You could try GAP. This is far from being elegant, just if you are very desperate ;-)

gap> g := SymmetricGroup(7);;

gap> regmod := RegularModule(g,GF(19));;

//This not elegant: I chose GF(11) to make the group ring semisimple (as if working over a field of characteristic 0. This is necessary here, as GAP uses the MeatAxe which needs finite fields). Moreover it would be better to get the simple constituents from another source than the regular module as the regular module soon gets too large in dimension. Maybe one could consider an action of $g$ on cosets of a subgroup where your simples of interest occur as composition factors. Ask for more details if you are interested. For $g=S_7$ this is too large to handle. So I take the natural PermutationModule, which has two constituents, a module of dimension 1 and a module of dimension 6.//

gap> permod := PermutationGModule(g,GF(11));;

gap> comps := MTX.CompositionFactors(permod);

[ rec( field := GF(11), isMTXModule := true, dimension := 1, generators := [ [ [ Z(11)^0 ] ], [ [ Z(11)^0 ] ] ], smashMeataxe := rec( algebraElement := [ [ [ 1, 2 ], [ 3, 1 ] ], [ Z(11)^0, Z(11)^0, Z(11)^9, Z(11) ] ], algebraElementMatrix := [ [ Z(11)^5 ] ], characteristicPolynomial := x_1+Z(11)^0, charpolFactors := x_1+Z(11)^0, nullspaceVector := [ Z(11)^0 ], ndimFlag := 1 ), IsIrreducible := true ), rec( field := GF(11), isMTXModule := true, dimension := 6, generators := [ < immutable compressed matrix 6x6 over GF(11) >, < immutable compressed matrix 6x6 over GF(11) > ], smashMeataxe := rec( algebraElement := [ [ [ 2, 1 ], [ 2, 3 ] ], [ Z(11)^6, Z(11)^9, Z(11)^8, Z(11) ] ], algebraElementMatrix := < immutable compressed matrix 6x6 over GF( 11) >, characteristicPolynomial := x_1^6+Z(11)^6*x_1^5+Z(11)^7*x_1^3+Z(11)^3*x_1^2+Z(11)^4*x_1+Z(11)^8, charpolFactors := x_1-Z(11)^0, nullspaceVector := [ Z(11), Z(11)^8, Z(11)^5, Z(11)^3, Z(11)^7, Z(11)^0 ], ndimFlag := 1 ), IsIrreducible := true ) ]

gap> c1 := comps[1];;

gap> c2 := comps[2];;

gap> TensorProductGModule(c1,c2);

rec( field := GF(19), isMTXModule := true, dimension := 6, generators := [ < immutable compressed matrix 6x6 over GF(19) >, < immutable compressed matrix 6x6 over GF(19) > ] ) gap>

From this point on you can do whatever MTX in GAP allows you to do with modules. See also http://www.gap-system.org/Manuals/doc/htm/ref/CHAP067.htm#SSEC002.2 for more information on GAP.

Answer by Ira Gessel for Computer package for representation theory of the symmetric group

2012-05-16T22:10:14Z

If I understand correctly, you can do the computation with symmetric functions using the operation of inner plethysm, which bears the same relationship to the internal, or Kronecker, product on symmetric functions that ordinary plethysm bears to ordinary multiplication of symmetric functions (and also makes the ring of symmetric functions with the internal product into a $\lambda$-ring). Inner plethysm is not as well known as it should be (I don't think it's mentioned in Macdonald's book), but the formulas for computing it aren't complicated:

Using, for simplicity, the notation $f[g]$ for this operation, it's determined by the following:

(1) for fixed $g$, the map $f\mapsto f[g]$ is a homorphism.

(2) For a partition $\lambda$ of $n$ and an integer $k$, let $\lambda^k$ denote the cycle type of the $k$th power of a permutation with cycle type $\lambda$. Then $$ p_k\left[\sum_{\lambda\vdash n}a_{\lambda}\frac{p_{\lambda}}{z_\lambda}\right] =\sum_{\lambda\vdash n}a_{\lambda^k}\frac{p_{\lambda}}{z_\lambda} $$ I don't think that inner plethysm is implemented in John Stembridge's SF package, but it will easily express Schur functions in terms of power sum symmetric functions and vice-versa, and computing inner plethysms with power sum symmetric functions isn't hard; if you know Maple, essentially all you need to do is write a function to compute $\lambda^k$. Then to compute the characteristic of $S_\lambda V$, all you need to do is compute the inner plethysm $s_\lambda[\text{ch } V]$.

Answer by John Wiltshire-Gordon for Computer package for representation theory of the symmetric group

2012-05-17T01:32:38Z

Here is the GAP code I use to do these computations:

SchurFunctorOfCharacter:=function(char,p)
  local n,t,c;
  if p=[] then
       return TrivialCharacter(UnderlyingCharacterTable(char));
  fi;
  n:=Sum(p);
  t:=CharacterTable("Symmetric",n);
  c:=List(CharacterParameters(t),u->u[2]);
  return Symmetrizations([char],n)[Position(c,p)];
  end;;
CharacterFromPartition:=function(table,p)
  local c;
  c:=List(CharacterParameters(table),u->u[2]);
  return Irr(table)[Position(c,p)];
  end;;
DecomposeCharacter:=char->List(Irr(UnderlyingCharacterTable(char)),x->ScalarProduct(x,char));;
t:=CharacterTable("Symmetric",7);;
chi:=CharacterFromPartition(t,[3,3,1]);;
DecomposeCharacter(SchurFunctorOfCharacter(chi,[1,1,1]));

This code computes the character table of $S_7$, finds the character corresponding to the partition $3+3+1$, and applies the Schur functor corresponding to the partition $1+1+1$ (otherwise known as $\wedge^3$). Here is the result:

[ 0, 1, 2, 4, 6, 9, 7, 4, 7, 9, 4, 2, 4, 1, 1 ]

These are the multiplicities of the irreducible constituents of our character. The ordering on partitions is lexicographic. For example, to determine the meaning of the $6$, just take the fifth partition of $7$:

Partitions(7)[5];

The output shows that the coefficient $6$ appears before the L-shaped partition $3+1+1+1+1$:

[3,1,1,1,1]