Submitted by Mike Zabrocki
A representation of is a homomorphism from to . The value of is the dimension of the representation.
Up to isomorphism, there is one irreducible polynomial representation for each partition with the length of less or equal to . The character of that irreducible representation is the Schur function indexed by the partition . The dimension of that representation is the number of column strict tableaux of shape with entries in .
Since the permutation matrices are a natural subgroup of , when an irreducible representation is restricted from to it decomposes as a direct sum of irreducible representations.
The restriction problem is the following:
OPAC-020. Find a combinatorial description of the decomposition of the irreducible module indexed by the partition into symmetric group -irreducibles.
This problem has a very long history, but generally very few people publish partial progress or failed attempts so there is very little written about it after the 1980’s beyond special cases.
To determine how a irreducible decomposes into irreducibles we can use the character of the irreducible module and its evaluation at eigenvalues of permutation matrices . Let be a partition of and be the eigenvalues of a permutation matrix of cycle structure (up to reordering, this list only depends on the cycle structure).
If we evaluate the symmetric function at the eigenvalues , this is the value of the character at a permutation of cycle structure .
Representation theory provides a formula for the multiplicity for a symmetric group irreducible indexed by (where is a partition of and the character of this irreducible is denoted ). It is equal to
where the sum is over all partitions of .
Computing a few examples of this formula should indicate why it is not a particularly satisfactory answer beyond as a means of arriving at a numerical value. Littlewood [2, 9] showed in the 50’s that the multiplicity can be computed using the operation of plethysm:
This is an advance in the problem, but recasts the solution of one problem in terms of another for which we don’t have a combinatorial formula.
I first became interested in this problem in the early 2000’s because, from time to time, I would encounter a module for which a formula for the character was well known, but the symmetric group module structure was not. Then in 2016, Rosa Orellana and I  found a basis of the symmetric functions that are the the characters of the symmetric group as permutation matrices in the same way that the Schur functions are characters of . That, is there is a basis (and one could take the following formula as a definition of this basis) such that for all sufficiently large,
Then, for a partition of , we have .
For each partition , following symmetric function encodes all of the values of the symmetric group character of this representation:
where the sum is over all partitions of . An answer to the restriction problem would provide a Schur expansion of this expression as a symmetric function of degree . Note that if , then .
Programs for computing data are easily accessible in Sage [7, 8] through the ring of symmetric functions. For instance, the following code:
sage: s = SymmetricFunctions(QQ).schur()
s[2, 1, 1] + s[2, 2] + 4*s[3, 1] + 3*s
computes the Schur expansion of by evaluating the character at the eigenvalues of permutation matrices and computing the Schur expansion of that expression.
In the case when , we have the following, which should be a special case of what the answer might look like in general:
Proposition. (Reformulation of ; see Exercise 7.73 of ; MacMahon’s Master Theorem  can be used to derive this.) The coefficient of the Schur function in (where is a partition of ) is equal to the coefficient of in the Schur function evaluation .
 A. C. Aitken, On induced permutation matrices and the symmetric group, Proc. Edinburgh Math. Soc., 5 (1937), no. 1, 1–13. DOI: 10.1017/S0013091500008208
 D. E. Littlewood, Products and Plethysms of Characters with Orthogonal, Symplectic and Symmetric Groups, Canad. J. Math., 10 (1958), 17–32. DOI: 10.4153/CJM-1958-002-7
 I. G. Macdonald, Symmetric Functions and Hall Polynomials, 2nd Edition, Oxford University Press, 1995.
 P. A. MacMahon, Combinatory Analysis, Vol. 1, Cambridge, 1915.
 R. Orellana, M. Zabrocki, Characters of the symmetric group as symmetric functions, prepint (2016). arXiv:1605.06672
 B. Sagan, The symmetric group. Representations, combinatorial algorithms, and symmetric functions, 2nd edition, Graduate Text in Mathematics 203. Springer-Verlag, 2001.
 W. A. Stein et al. Sage Mathematics Software (Version 6.10), The Sage Development Team, http://www.sagemath.org , 2016.
 The Sage-Combinat community. Sage-Combinat: enhancing Sage as a toolbox for computer exploration in algebraic combinatorics, http://combinat.sagemath.org , 2008.
 T. Scharf, J. Y. Thibon, A Hopf-algebra approach to inner plethysm. Adv. in Math. 104 (1994), 30–58. DOI: 10.1006/aima.1994.1019
 R. Stanley, Enumerative Combinatorics, Vol. 2, Cambridge University Press, 1999.