Consider the generating functions
These are respectively known as the degree elementary, complete, and power sum symmetric functions over the alphabet . Note that they are not actually functions, but rather elements of the algebra of formal power series over The “fundamental theorem of symmetric function theory” asserts that these series all generate the same subalgebra of .
Theorem (Newton): We have
The subalgebra of generated by any of the above three fundamental families is called the algebra of symmetric functions, and typically denoted or if the alphabet needs to be specified. This algebra has a lot of internal structure which expresses itself in combinatorially interesting ways. To see some of this, you might try expressing the elementary symmetric functions in terms of the power sums, as Newton did.
Definition 1: A specialization of is an algebra homomorphism from to a commutative -algebra
In practice, specializations typically occur as families of substitutions. Here is a very simple example. For any we have a specialization
i.e. by substituting the numerical value for each of the variables (or any other specified set of variables), and substituting the numerical value for the rest. It is natural to identify the homomorphism with the numerical multiset
and write rather than to reflect the substitution.
Problem 1: Explicitly compute
Another interesting numerical specialization arises from taking
For this numerical substitution we have
which is a sum people have been thinking about since antiquity. In particular, there are various formulas for this sum, many of which involve the Bernoulli numbers. In order to evaluate and one may proceed rather differently as follows. Let be a new variable, and consider the generating functions
which are elements of the algebra of formal power series in the single variable , with coefficients in . These generating functions may be explicitly evaluated without too much effort.
Problem 2: Show that
From Problem 2, we immediately get the identities
from which one can conclude that and are in fact Stirling numbers.
We can repackage the the content of Lecture 13 as the study of a certain family of specializations
where is the center of the group algebra These specializations are defined using the substitution multiset
are the Jucys-Murphy elements in The natural basis of is the conjugacy class basis,
so understanding the JM specialization of means being able to compute
the coefficient of a given conjugacy class in the specialization of a given symmetric function What we saw in Lecture 13 is that for certain this problem has a combinatorial interpretation as counting certain walks in the Cayley graph of as generated by the conjugacy class of transpositions.
Consider first the elementary symmetric functions What we saw in Lecture 12 is that
is the number of -step strictly monotone walks from the identity permutation to any permutation of cycle type Moreover, we were able to solve the class expansion problem for the elementary symmetric polynomials explicitly:
with the sum on the right being exactly the identity-centered sphere of radius in or equivalently the th level of the Cayley graph. Equivalently, for the generating function
which is the generating function for permutations by norm.
For the complete symmetric functions we found that
is the number of -step weakly monotone walks from the identity permutation to any permutation of cycle type . We did not give an exact formula for this number, and indeed no such formula is known. However, we can make some progress using another remarkable aspect of the JM elements, namely their interaction with the representation theory of
We know that, for any the specialization is a central element in the group algebra Thus, by Schur’s lemma, acts in any irreducible representation of as a scalar operator, i.e. we have
with a scalar and the identity operator. It turns out that the eigenvalue can be expressed in terms of a remarkable numerical specialization of
Definition 2: Given a Young diagram and a cell the content of is its column index minus its row index. The content alphabet of is the multiset of the contents of its cells,
Theorem (Jucys): The eigenvalue of acting in is the specialization of on the content alphabet of
In fact, Jucys proved a more general result which implies the above: he showed that for any of the elements the Young basis of is an eigenbasis of the operator and
where is the content of the cell containing in the standard Young tableau
In particular, the Jucys’ result enables us to obtain a formula for the generating function enumerating monotone walks from the identity permutation to any permutation of cycle type in terms of the characters of
Theorem (Matsumoto-Novak): We have
where denotes the hook length of the cell
For certain choices of , the sum on the right simplifies considerably and explicit formulas for follow. For example, in the case where , we may use the fact that the character of a full cycle vanishes in any representation for which is not a hook diagram, and is either when is a hook. This leads to an explicit formula for the number of monotone walks of arbitrary length from the identity to a full cycle in Understanding all of this requires only Math 202B knowledge, and the details are in the paper referenced above.