# 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

$\mathbb{C}[e_1,e_2,e_3,\dots]=\mathbb{C}[h_1,h_2,h_3,\dots]=\mathbb{C}[p_1,p_2,p_3,\dots].$

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

$\{\{\underbrace{1,\dots,1}_n,0,0,0,\dots\}\}$

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)$

and

$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\}\},$

where

$J_t = \sum\limits_{1 \leq s

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

$[C_\mu]f(\Xi_n),$

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 $r$th 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.