Math 202C: Lecture 10

Let $G=(S,T)$ be a finite connected simple graph with vertex set $S=\{\pi,\rho,\sigma,\dots\}$ and edge set $T$ . We pass to the Hilbert space $\mathcal{F}(S)$ with orthonormal basis $|\pi\rangle,|\rho\rangle,|\sigma\rangle,\dots$ and consider the selfadjoint operators

$L_r|\rho\rangle = \sum\limits_{\substack{\sigma \in S \\ \mathrm{d}(\rho,\sigma)=r}} |\sigma\rangle, \quad r \geq 0,$

which encode the entire metric structure of $G$ . We have that $L_r$ is the zero operator for all $r$ which exceed the diameter of $G,$ while the nonzero operators $\{L_0,L_1,\dots,L_{\mathrm{diam}(G)}\}$ form an orthogonal set in $\mathrm{End}\mathcal{C}(S)$ with respect to the Hilbert-Schmidt scalar product. However, not much is known about the subalgebra $\mathcal{L}(G)$ of $\mathrm{End}\mathcal{F}(S)$ generated by the selfadjoint operators $L_r.$

If $G=(S,T)$ is the Cayley graph of a finite group $S$ corresponding to a symmetric set of generators $T \subseteq S,$ we are in a more favorable situation because the operator $L_r$ is the image of an element of the convolution algebra $\mathcal{C}(S),$ namely

$|L_r\rangle= \sum\limits_{|\pi|=r} |\pi\rangle,$

in the regular representation. Because the regular representation is faithful, we can view $\mathcal{L}(G)$ as the subalgebra of $\mathcal{C}(S)$ generated by the selfadjoint elements $|L_r\rangle,$ and leverage the group structure of $S$ to help us understand the situation. For example, if $S$ is an abelian group we automatically get that $\mathcal{L}(G)$ is a commutative algebra.

Problem 10.1. Let $G_n=(S_n,T_n)$ be the Cayley graph corresponding to the cyclic group $S_n=\{g^0,g^1,\dots,g^{n-1}\}$ of order $n$ with generating set $T_n=\{g,g^{-1}\}.$ This graph is easy to picture: it is a cycle on $n$ vertices. Show that

$\mathcal{L}(G_n) = \left\{\sum\limits_{k=0}^{n-1} a_k|g^k\rangle \colon a_k=a_{-k}\right\},$

and compute the dimension of this commutative algebra.

Now let us consider the Cayley graph $G_n=(S_n,T_n)$ of the symmetric group $S_n=\mathrm{Aut}\{1,\dots,n\}$ as generated by the conjugacy class of transpositions, $T_n=\{(st) \colon 1 \leq s<t \leq n\}.$ This is a nonabelian group, and yet the operators $L_0,L_1,L_2,\dots$ commute. This is a consequence of the fact that the elements

$|L_r\rangle= \sum\limits_{\substack{\mu \vdash n \\ \ell(\mu)=n-r}}|C_\mu\rangle,$

where $C_\mu \subseteq S_n$ denotes the conjugacy class of permutations of cycle type $\mu$ , belong to the center $\mathcal{Z}_n$ of $\mathcal{C}(S_n)$ . Thus, the sphere sums $|L_r\rangle$ generate a subalgebra $\mathcal{L}_n$ of $\mathcal{Z}_n$ . In fact, we have the following classical result of Farahat-Higman.

Theorem 10.1. $\mathcal{L}_n=\mathcal{Z}_n.$

In this lecture we will prove Theorem 10.1, or at least explain why it is true. Our starting point is the first main result of Math 202C, namely that

$|L_r\rangle=e_r(|J_1\rangle,\dots,|J_n\rangle)$

where $|J_1\rangle,\dots,|J_n\rangle \in \mathcal{C}(S_n)$ are the Jucys-Murphy elements and $e_r(x_1,\dots,x_n)$ is the elementary symmetric polynomial of degree $r$ . This together with the second main result in Math 202C so far, the fundamental theorem of symmetric polynomials, gives us a specialization

$\Xi_n \colon \mathcal{S}_n \longrightarrow \mathcal{Z}_n$

of the algebra $\mathcal{S}_n=\mathbb{C}[x_1,\dots,x_n]^{S_n}$ of symmetric polynomials defined by

$\Xi_n(f(x_1,\dots,x_n))=f(|J_1\rangle,\dots,|J_n\rangle).$

The image of $\mathcal{S}_n$ under $\Xi_n$ is exactly $\mathcal{L}_n,$ so that Theorem 10.1 is equivalent to the following.

Theorem 10.2. $\Xi_n$ is surjective.

Problem 10.1. Carefully explain the equivalence between Theorems 10.1 and 10.2.

In order to prove Theorem 10.2, we would ideally like to explicitly construct a family $f_\mu(x_1,\dots,x_n)$ of symmetric polynomials indexed by partitions $\mu \vdash n$ such that

$f_\mu(|J_1\rangle,\dots,|J_n\rangle)=C_\mu.$

In fact, we know how to do this in three cases: the polynomials

$f_{(1,1,\dots, 1)}:=e_0,\ f_{(2,1,\dots,1)}:=e_1, \quad f_{(n)}:=e_{n-1}$

map to the conjugacy classes

$|C_{(1,1,\dots,1)}\rangle,\ |C_{(2,1,\dots,1)}\rangle,\ |C_{(n)}\rangle$

under $\Xi_n.$

Next, we would like to construct symmetric polynomials $f_{(3,1,\dots,1)}$ and $f_{(2,2,1,\dots,1)}$ such that

$f_{(3,1,\dots,1)}(|J_1\rangle,\dots,|J_n\rangle)=|C_{(3,1,\dots,1)}\rangle$

and

$f_{(2,2,1,\dots,1)}(|J_1\rangle,\dots,|J_n\rangle) = |C_{(2,2,1,\dots,1)}\rangle.$

However, at present we only know that

$e_2(|J_1\rangle,\dots,|J_n\rangle)=|L_2\rangle=|C_{(3,1,\dots,1)}\rangle+|C_{(2,2,1,\dots,1)}\rangle.$

Before going any further, let us note that the standard labeling $C_\mu$ of conjugacy classes in $S_n$ is not ideal for our purposes. Instead, it is much better to define the reduced cycle-type of a permutation $\pi \in C_\mu$ to be the partition $\nu$ obtained by subtracting $1$ from each part of $\mu.$ Then, the decomposition of the levels $L_r$ of the Cayley graph becomes

$|L_r\rangle = \sum\limits_{\nu \vdash r} C_\nu(n),$

where $C_\nu(n)$ is the conjugacy class of permutations in $S_n$ of reduced cycle type $\nu.$ In this language, the data we have so far is

$e_0(\Xi_n) = C_0(n),\ e_1(\Xi_n) = C_1(\Xi_n),\ e_{n-1}=C_{n-1}(n).$

It is definitely not the case that $e_r(\Xi_n)=C_r(n)$ — what is actually true is that

$e_r(\Xi_n) = |L_r(n)\rangle, \quad 0 \leq r \leq n,$

and the three data points above are precisely those in which a single level actually is a conjugacy class.

Now let us come back to the first unknown case of our problem: we know that

$e_2(\Xi_n)=|C_2(n)\rangle + |C_{11}(n)\rangle,$

but we do not yet know that each of the summands in this expression can be expressed as a symmetric polynomial in the JM-elements. The space $\mathcal{S}_n^2$ of homogeneous degree $2$ symmetric polynomial in $n$ variables is two-dimensional, with monomial basis

$m_2(x_1,\dots,x_n) = p_2(x_1,\dots,x_n) = \sum\limits_{1 \leq I \leq n} x_i^2,\\ m_{11}(x_1,\dots,x_n)=e_2(x_1,\dots,x_n)=\sum\limits_{1 \leq i <j \leq n}x_ix_j.$

We already know what $m_{11}(\Xi_n)=e_2(\Xi_n)$ is, so it remains to calculate

$m_2(\Xi_n)=p_2(\Xi_n)=\sum\limits_{1 \leq t \leq n} |J_t\rangle^2.$

Now,

$|J_t\rangle^2 = \sum\limits_{s_1,s_2<t} |s_1t\rangle |s_2t\rangle=\sum\limits_{s<t} |st\rangle|st\rangle+\sum\limits_{s_1\neq s_2<t}|s_1t\rangle|s_2t\rangle.$

The first sum is just $t-1$ copies of $|st\rangle|st\rangle=|\iota\rangle,$ giving a net contribution of

$\sum\limits_{1 \leq t \leq n}(t-1)|\iota\rangle={n \choose 2}C_0(n).$

$\sum\limits_{1 \leq t \leq n}\sum\limits_{s_1\neq s_2<t}|s_1t\rangle|s_2t\rangle=|C_2(n)\rangle.$

We thus have a system of two linear equations,

$m_{11}(\Xi_n) = |C_{11}(n)\rangle+|C_2(n)\rangle \\ m_2(\Xi_n) = |C_2(n)\rangle+{n \choose 2}|C_0(n)\rangle.$

The second equation gives us

$|C_2(n)\rangle=m_2(\Xi_n)-{n \choose 2}m_0(\Xi_n),$

which is a symmetric polynomial in the JM-elements, and substituting this into the first equation and solving we get

$|C_{11}(n)\rangle=m_{11}(\Xi_n)-m_2(\Xi_n)+{n \choose 2}m_0(\Xi_n)$ ,

so that we have successfully expressed each of the conjugacy classes $C_\nu(n)$ of $S_n$ of reduced cycle type $\nu\vdash 2$ as a symmetric polynomial in the JM-elements.

For level $L_3$ in $S_n,$ the class expansion of the monomial symmetric polynomials $m_\lambda(\Xi_n)$ of degree three is

$m_3(\Xi_n) = C_3(n) + (2n-3)C_1(n) \\ m_{21}(\Xi_n) = C_{21}(n)+3C_3(n)+\left({n \choose 2}-1\right)C_1(n) \\ m_{111}(\Xi_n) = C_{111}(n)+C_{21}(n)+C_3(n),$

which modulo levels $L_0,L_1,L_2$ becomes

$\tilde{m}_3(\Xi_n) =C_3(n) \\ \tilde{m}_{21}(\Xi_n) =C_{21}(n)+3C_3(n) \\ \tilde{m}_{111}(\Xi_n) =C_{111}(n)+C_{21}(n)+C_3(n).$

If we order the partitions of $3$ as $3 < 21 < 111,$ this is the triangular system

$\begin{bmatrix} \tilde{m}_3(\Xi_n) \\ \tilde{m}_{21}(\Xi_n) \\ \tilde{m}_{111}(\Xi_n) \end{bmatrix} = \begin{bmatrix} 1 & 0 & 0 \\ 3 & 1 & 0 \\ 1 & 1 & 1 \end{bmatrix} \begin{bmatrix} C_3(n) \\ C_{21}(n) \\ C_{111}(n) \end{bmatrix}.$

These computations can, to some extent, be performed in full generality. The result which comes out of the attempt to do so is the following fairly explicit description of the images of all monomial symmetric polynomials under the JM-specialization $\Xi_n$ .

Theorem 10.2. For each level $0 \leq r \leq n-1$ of the Cayley graph $G_n=(S_n,T_n)$ , not only do we have $e_r(\Xi_n) = |L_r\rangle,$ but in fact for every partition $\lambda \vdash r$ there holds a class expansion

$m_\lambda(\Xi_n) = \sum\limits_{|nu|\leq |\lambda|}L^\lambda_\nu(n)C_\nu(n)$ ,

in which the coefficients $L^\lambda_\nu(n)$ are polynomials in $n$ . In fact, $L^\lambda_\nu(n)$ is independent of $n$ for $|\lambda|=|\nu|=r,$ and modulo lower levels $L_0,L_1,\dots,L_{r-1}$ , we have