Math 202C: Lecture 14

Let us begin with a very brief overview of symmetric function theory. Let X=\{x_1,x_2,x_3,\dots\} be a countable set of commuting indeterminates, referred to as an alphabet. Given r \in \mathbb{N}, let \mathrm{Fun}(r,\mathbb{N}) denote the set of functions

i \colon \{1,\dots,r\} \longrightarrow \mathbb{N}.

Consider the generating functions

e_r = \sum\limits_{\substack{i \in \mathrm{Fun}(r,\mathbb{N}) \\ i \text{ strictly increasing}}} \prod\limits_{q=1}^r x_{i(q)},

h_r = \sum\limits_{\substack{i \in \mathrm{Fun}(r,\mathbb{N}) \\ i \text{ weakly increasing}}} \prod\limits_{q=1}^r x_{I(q)},

p_r = \sum\limits_{\substack{i \in \mathrm{Fun}(r,\mathbb{N}) \\ i \text{ constant}}} \prod\limits_{q=1}^r x_{I(r)}.

These are respectively known as the degree r elementary, complete, and power sum symmetric functions over the alphabet X. Note that they are not actually functions, but rather elements of the algebra \mathbb{C}[[x_1,x_2,x_3,\dots]] of formal power series over X. The “fundamental theorem of symmetric function theory” asserts that these series all generate the same subalgebra of \mathbb{C}[[x_1,x_2,x_3,\dots]].

Theorem (Newton): We have


The subalgebra of \mathbb{C}[[x_1,x_2,x_3,\dots]] generated by any of the above three fundamental families is called the algebra of symmetric functions, and typically denoted \Lambda or \Lambda[X] 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 \Lambda is an algebra homomorphism from \Lambda to a commutative \mathbb{C}-algebra \mathbf{A}.

In practice, specializations typically occur as families of substitutions. Here is a very simple example. For any n \in \mathbb{N}, we have a specialization

\Xi_n \colon \Lambda \to \mathbb{C}

defined by

\Xi_n(f) = f(\underbrace{1,\dots,1}_n,0,0,0,\dots),

i.e. by substituting the numerical value 1 for each of the variables x_1,\dots,x_n (or any other specified set of n variables), and substituting the numerical value 0 for the rest. It is natural to identify the homomorphism \Xi_n with the numerical multiset


and write f(\Xi_n) rather than \Xi_n(f) to reflect the substitution.

Problem 1: Explicitly compute e_r(\Xi_n),h_r(\Xi_n),p_r(\Xi_n).

Another interesting numerical specialization arises from taking

\Xi_n = \{\{1,\dots,n,0,0,0,\dots\}\}.

For this numerical substitution we have

p_r(\Xi_n) = 1^r + 2^r + \dots +n^r,

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 e_r(\Xi_n) and h_r(\Xi_n), one may proceed rather differently as follows. Let t be a new variable, and consider the generating functions

E(t) = 1 + \sum\limits_{r=1}^\infty e_r t^r \quad\text{ and }\quad H(t) = 1 + \sum\limits_{r=1}^\infty h_rt^r,

which are elements of \Lambda[[t]], the algebra of formal power series in the single variable t, with coefficients in \Lambda. These generating functions may be explicitly evaluated without too much effort.

Problem 2: Show that

E(t) = \prod\limits_{t=1}^\infty (1+tx_i) \quad\text{ and }\quad H(t) = \prod\limits_{t=1}^\infty \frac{1}{1-tx_i}.

From Problem 2, we immediately get the identities

1+\sum\limits_{d=1}^\infty e_r(\Xi_n)t^r = (1+t)(1+2t) \dots(1+nt)


1+\sum\limits_{d=1}^\infty h_r(\Xi_n)t^r = \frac{1}{(1+t)(1+2t) \dots(1+nt)},

from which one can conclude that e_r(\Xi_n) and h_r(\Xi_n) are in fact Stirling numbers.

We can repackage the the content of Lecture 13 as the study of a certain family of specializations

\Lambda \longrightarrow \mathcal{Z}(n),

where \mathcal{Z}(n) is the center of the group algebra \mathbb{C}\mathrm{S}(n). These specializations are defined using the substitution multiset

\Xi_n =\{\{J_1,\dots,J_n,0,0,0,\dots\}\},


J_t = \sum\limits_{1 \leq s<t \leq n} (s\ t), \quad 1 \leq t \leq n,

are the Jucys-Murphy elements in \mathbb{C}\mathrm{S}(n). The natural basis of \mathcal{Z}(n) is the conjugacy class basis,

\{C_\mu \colon \mu \vdash n\},

so understanding the JM specialization of \Lambda means being able to compute


the coefficient of a given conjugacy class C_\mu \in \mathcal{Z}(n) in the specialization of a given symmetric function f \in \Lambda. What we saw in Lecture 13 is that for certain f, this problem has a combinatorial interpretation as counting certain walks in the Cayley graph of \mathrm{S}(n) as generated by the conjugacy class of transpositions.

Consider first the elementary symmetric functions e_r. What we saw in Lecture 12 is that

[C_\mu]e_r(\Xi_N) = E^r(\mu)

is the number of r-step strictly monotone walks from the identity permutation to any permutation \pi of cycle type \mu. Moreover, we were able to solve the class expansion problem for the elementary symmetric polynomials explicitly:

e_r(\Xi_n) = \sum\limits_{\substack{\mu \vdash n \\ \ell(\mu)=n-r}} C_\mu,

with the sum on the right being exactly the identity-centered sphere L_r of radius r in \mathrm{S}(n), or equivalently the rth level of the Cayley graph. Equivalently, for the generating function

E(t) = 1 + \sum\limits_{r=1}^\infty e_r(\Xi_n)t^r,

we have

E(t) = \sum\limits_{\pi \in \mathrm{S}(n)} t^{|\pi|} \pi,

which is the generating function for permutations by norm.

For the complete symmetric functions h_r, we found that

[C_\mu]h_r(\Xi_n) = H^r(\mu)

is the number of r-step weakly monotone walks from the identity permutation to any permutation \pi of cycle type \mu. 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 \mathrm{S}(n).

We know that, for any f \in \Lambda, the specialization f(\Xi_n) is a central element in the group algebra \mathbb{C}\mathrm{S}(n). Thus, by Schur’s lemma, f(\Xi_n) acts in any irreducible representation (\mathbf{V}^\lambda,R^\lambda) of \mathbb{C}\mathrm{S}(n) as a scalar operator, i.e. we have

R^\lambda(f(\Xi_n)) = \omega_f(\lambda) I_{\mathbf{V}^\lambda},

with \omega_f(\lambda) \in \mathbb{C} a scalar and I_{\mathbf{V}^\lambda} \in \mathrm{End} \mathbf{V}^\lambda the identity operator. It turns out that the eigenvalue \omega_f(\lambda) can be expressed in terms of a remarkable numerical specialization of \Lambda.

Definition 2: Given a Young diagram \lambda and a cell \Box \in \lambda, the content c(\Box) of \Box is its column index minus its row index. The content alphabet C(\lambda) of \lambda is the multiset of the contents of its cells,

C(\lambda) = \{\{ c(\Box) \colon \Box \in \lambda\}\}.

Theorem (Jucys): The eigenvalue of f(\Xi_n) acting in \mathbf{V}^\lambda is the specialization of f on the content alphabet of \lambda,

\omega_f(\lambda) = f(C(\lambda)).

In fact, Jucys proved a more general result which implies the above: he showed that for any of the elements J_k, the Young basis \mathbf{e}_T of \mathbf{V}^\lambda is an eigenbasis of the operator R^\lambda(J_k), and

R^\lambda(J_k)\mathbf{e}_T = c_T(k) \mathbf{e}_T,

where c_T(k) is the content of the cell containing k in the standard Young tableau T.

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 \pi \in \mathrm{S}(n) of cycle type \mu \vdash n in terms of the characters of \mathrm{S}(n).

Theorem (Matsumoto-Novak): We have

1+\sum\limits_{r=1}^\infty H^r(\mu) t^r = \sum\limits_{\lambda \vdash n} \frac{\chi^\lambda_\mu}{\prod_{\Box \in \lambda} h(\Box)(1+tc(\Box))},

where h(\Box) denotes the hook length of the cell \Box \in \lambda.

For certain choices of \mu, the sum on the right simplifies considerably and explicit formulas for H^r(\mu) follow. For example, in the case where \mu=(n), we may use the fact that the character of a full cycle vanishes in any representation \mathbf{V}^\lambda for which \lambda is not a hook diagram, and is either pm 1 when \lambda 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 \mathrm{S}(n). Understanding all of this requires only Math 202B knowledge, and the details are in the paper referenced above.

Leave a Reply