Math 202C: Lecture 6

*** Problem in this lecture due April 19 at 23:59 ***

In Lecture 5, we constructed the polynomial algebra \mathcal{P}_n and the symmetric polynomial algebra \mathcal{S}_n. The basic combinatorial objects underlying these constructions are integer compositions and integer partitions. Let

\mathrm{Com}_n=\{\alpha=(\alpha_1,\dots,\alpha_n) \colon \alpha_i \in \mathbb{N}_0\}.

Then,

\mathrm{Com}_n = \bigsqcup\limits_{d=0}^\infty \mathrm{Com}_n^d

with

\mathrm{Com}_n^d=\{\alpha \in \mathrm{Com}_n \colon |\alpha|=d\},

where |\alpha|=\alpha_1+\dots+\alpha_n. Now we quantize, meaning that we replace \mathrm{Com}_n with the Hilbert space \mathcal{P}_n having orthonormal basis

|\alpha\rangle, \quad \alpha \in \mathrm{Com}_n.

The disjoint union decomposition of the infinite set \mathrm{Com}_n then becomes an orthogonal direct sum decomposition

\mathcal{P}_n = \bigoplus\limits_{d=0}^\infty \mathcal{P}_n^d

of the infinite-dimensional space \mathcal{P}_n into finite-dimensional subspaces

\mathcal{P}_n^d = \bigoplus\limits_{\alpha \in \mathrm{Com}_n^d} \mathbb{C}|\alpha\rangle.

Moreover, we have a natural notion of multiplication in \mathcal{P}_n defined by

|\alpha\rangle|\beta\rangle=|\alpha+\beta\rangle,

which has the feature that

|\alpha\rangle \in \mathcal{P}_n^c,\ |\beta\rangle \in \mathcal{P}_n^d \implies |\alpha+\beta\rangle \in \mathcal{P}_n^{c+d}.

On one hand, the infinite-dimensional algebra is similar to the convolution algebra of an abelian group: if

|v\rangle = \sum\limits_\alpha c_\alpha|\alpha\rangle \quad\text{and}\quad |w\rangle = \sum\limits_\beta d_\beta|\beta\rangle,

then

|v\rangle |w\rangle = \sum\limits_\gamma \left( \sum\limits_{\alpha+\beta=\gamma} c_\alpha d_\beta\right)|\gamma\rangle.

Indeed, \mathcal{P}_n is precisely the convolution algebra of finitely-supported functions on the infinite abelian monoid \mathrm{Com}_n. On the other hand, \mathcal{P}_n is something quite familiar and intuitive: the algebra of polynomials in n commuting variables. Indeed, under the identification

|\alpha\rangle \mapsto x^\alpha = x_1^{\alpha_1} \dots x_n^{\alpha_n},

we have

|v\rangle = \sum\limits_\alpha c_\alpha|\alpha\rangle = \sum\limits_\alpha c_\alpha x^\alpha = f(x_1,\dots,x_n).

In this sense, what the familiar algebra of polynomials in n commuting variables “really” is is the convolution algebra of the commutative monoid \mathrm{Com}_n.

The symmetric group S_n = \mathrm{Aut}\{1,\dots,n\} acts on \mathrm{Com}_n according to

\pi \cdot \alpha = (\alpha_{\pi(1)} \dots \alpha_{\pi(n)}),

and this permutation action respects the decomposition of \mathrm{Com}_n into finite-dimensional components \mathrm{Com}_n^d. This permutation action gives rise to a unitary representation (\mathcal{P}_n,\varphi_n) of S_n, where

\varphi_n \colon S_n \longrightarrow U(\mathcal{P}_n)

is the group homomorphism defined by

\varphi_n(\pi)|\alpha\rangle = |\alpha_{\pi(1)} \dots \alpha_{\pi(n)}\rangle.

Equivalently, thinking of \mathcal{P}_n as the algebra of polynomials in n variables this is

\varphi_n(\pi)f(x_1,\dots,x_n) = f(x_{\pi^{-1}(1)},\dots,x_{\pi^{-1}(n)}).

The algebra of symmetric polynomials in n variables is the space \mathcal{S}_n=\mathcal{P}_n^{S_n} of latex S_n$-invariant vectors in this unitary representation, i.e. polynomials with the property that

f(x_{\pi(1)},\dots,x_{\pi(n)}) = f(x_1,\dots,x_n), \quad \forall \pi \in S_n.

As explained in Lecture 5, it is not too difficult to construct a basis of \mathcal{S}_n. Indeed, one need only observe that orbits of the the action of S_n on \mathrm{Com}_n are naturally indexed by the set

\mathrm{Par}_n = \{\lambda \in \mathrm{Com}_n \colon \lambda_1 \geq \dots \geq \lambda_n\}.

For a fixed positive integer d, the set \mathrm{Par}_n^d=\mathrm{Par}_n \cap \mathrm{Com}_n^d may be identified with the set of partitions of d having at most n parts. Then, associated to each \lambda \in \mathrm{Par}_n^d is the corresponding orbit sum

m_\lambda(x_1,\dots,x_n) = \sum\limits_{\alpha \in \mathcal{O}_\lambda} x^\alpha,

and \{m_\lambda \colon \lambda \in \mathrm{Par}_n^d\} is an orthogonal basis of \mathcal{S}_n^d=\mathcal{S}_n \cap \mathcal{P}_n^d. This is the basis of monomial symmetric polynomials, which have the form

m_\lambda(x_1,\dots,x_n) = x_1^{\lambda_1} \dots x_n^{\lambda_n} + \text{symmetries}.

So while m_\lambda is not in general a monomial, it is a polynomial having the feature that any of its constituent monomials determines all the others.

Problem 6.1. Give necessary and sufficient conditions under which m_\lambda(x_1,\dots,x_n) actually is a monomial.

Because m_\lambda is not in general a monomial, it is not in general the case that

m_\lambda(x_1,\dots,x_n)m_\mu(x_1,\dots,x_n)=m_{\lambda+\mu}(x_1,\dots,x_n).

This is somewhat analogous to the fact that convolution of conjugacy classes in the center of the convolution algebra of a noncommutative group is determined by, but not the same as, multiplication of group elements. As in that context, the natural question is to compute the connection coefficients of the monomial basis of \mathcal{S}_n,

m_\lambda m_\mu = \sum\limits_{\nu \in \mathrm{Par}_n} c_{\lambda\mu\nu} m_\nu.

In support of this analogy, consider the following.

Problem 6.2. Show that for any \gamma \in \mathcal{O}_\nu, the coefficient of the monomial x^\gamma in the product m_\lambda(x_1,\dots,x_n)m_\mu(x_1,\dots,x_n) is

c_{\lambda\mu\nu} =|\{(\alpha,\beta) \in \mathcal{O}_\lambda \times \mathcal{O}_\nu \colon \alpha+\beta=\gamma\}|.

Taking the analogy to this natural conclusion, remember the a priori surprising fact the center of the convolution algebra, whose multiplication appears quite complicated in the class basis, is actually isomorphic to a pointwise function algebra. In particular, in the abelian case we have \mathcal{C}(G) \simeq \mathcal{F}(G).$

Theorem 6.1 (Newton). The algebra \mathcal{S}_n of symmetric polynomials in n variables is isomorphic to the algebra \mathcal{P}_n of polynomials in n variables.

Note that this is an infinite-dimensional phenomenon: the proper subalgebra \mathcal{S}_n of \mathcal{P}_n is isomorphic to the full algebra in which it resides. In particular, the isomorphism is definitely not the tautological inclusion.

Theorem 6.1. is called the fundamental theorem of symmetric polynomials, and as indicated above it is generally attributed to Newton. Among many other achievements, Newton laid the foundations for classical mechanics based on his theory of gravity, and developed a theory of optics which involved sticking a knitting needle into his own eye to demonstrate that color is an intrinsic property of light as opposed to an artifact of perception. Now that’s applied mathematics. Given that symmetric polynomials were good enough for Newton, it’s a bit hard to take complaints about our subject matter being “too pure” seriously. But ok, nowadays we’re doing data science, not physical science — why would you care about reconciling gravitation with quantum mechanics when you can make a living applying principal components analysis to an endless supply of large rectangular matrices?

From the data science perspective, Newton’s theorem says that the elementary symmetric polynomials form a universal coordinate system for polynomial features of unordered data. More precisely, his result is that \mathcal{S}_n=\mathbb{C}[x_1,\dots,x_n]^{S_n} is isomorphic to \mathcal{P}_n=\mathbb{C}[e_1,\dots,e_n], where

e_r(x_1,\dots,x_n) = \sum\limits_{\substack{I \subset [n] \\ |I|=r}} \prod\limits_{i \in I} x_i.

Here [n]=\{1,\dots,n\}, so e_r(x_1,\dots,x_n) is the zero polynomial for r>n. It is notationally convenient to define e_0(x_1,\dots,x_n) to be the constant polynomial 1. Then, for any partition \lambda, i.e. for any vector \lambda=(\lambda_1,\lambda_2,\lambda_3,\dots) from the set \mathrm{Par} of infinite integer vectors with weakly decreasing coordinate eventually equal to zero, we can extend the definition of the elementary symmetric polynomials by declaring

e_\lambda(x_1,\dots,x_n) = \prod\limits_{i=1}^\infty e_{\lambda_i}(x_1,\dots,x_n),

or equivalently

e_\lambda(x_1,\dots,x_n) = \prod\limits_{i=1}^{\ell(\lambda)}e_{\lambda_i}(x_1,\dots,x_n)

where \ell(\lambda) is the number of nonzero coordinates of \lambda. The condition required for this product to be nonzero is that \lambda_1 \leq n. Now, the set of partitions with largest part at most n is in bijection with the set of partitions with at most n parts via transposing Young diagrams, \lambda \mapsto \lambda^T. Thus, Newton’s theorem is equivalent to the following.

Theorem 6.2. For any d \in \mathbb{N}, the set \{e_\lambda(x_1,\dots,x_n) \colon \lambda^T \in \mathrm{Par}_n^d\} is a vector space basis of \mathcal{S}_n^d.

In Lecture 7, we will prove Theorem 6.2 by giving a combinatorial interpretation of the coefficients in the expansion

e_\lambda(x_1,\dots,x_n) = \sum\limits_{\lambda \in \mathrm{Par}_n^d} M_{\lambda\mu}m_\mu(x_1,\dots,x_n).

of the (extended) elementary symmetric polynomials e_\lambda in terms of the monomial symmetric polynomials m_\mu. In fact, the value of this computation extends beyond its immediate application to Newton’s theorem. Indeed, the expansion above is universal in the sense that it remains valid under any specialization, i.e. under any algebra homomorphism \Xi \colon \mathcal{S}_n \to \mathcal{A}. In particular, we have

e_\lambda(|J_1\rangle, \dots, |J_n\rangle) = \sum\limits_{\lambda \in \mathrm{Par}_n^d} M_{\lambda\mu}m_\mu(|J_1\rangle, \dots, |J_n\rangle),

where |J_1\rangle,\dots,|J_n\rangle are the Jucys-Murphy elements in the convolution algebra \mathcal{C}(S_n) of the symmetric group. Recall that we established the commutativity of the JM-elements by proving that they lie in the commutative subalgebra \mathcal{J}_n of \mathcal{C}(S_n) generated by

Z\mathcal{C}(S_1) \cup \dots \cup Z\mathcal{C}(S_n),

which we named the JM-subalgebra of \mathcal{C}(S_n). We then showed that

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

i.e. the levels of the symmetric group are precisely the elementary symmetric polynomials specialized on the JM-elements.

Next week, we shall see that essentially the same argument used to prove Newton’s theorem can be retooled to prove the apparently much more sophisticated result that |J_1\rangle,\dots,|J_n\rangle not only lie in the algebra \mathcal{J}_n, but in fact generate it. This will essentially complete Phase I of our development of the representation theory of the symmetric group. Phase II will be to show that \mathcal{J}_n has a completely different spectral interpretation as the so-called Gelfand-Tsetlin subalgebra of \mathcal{C}(S_n). As discovered by Okounkov and Vershik, the fact that the Jucys-Murphy and Gelfand-Tsetlin subalgebras of \mathcal{C}(S_n) are one and the same completely unlocks the representation theory of the symmetric groups.

For now, here is something concrete to think about.

Problem 6.3. Show that e_r(1,2,\dots,n-1) is equal to the number of permutations in S_n consisting of n-r disjoint cycles.

For context, recall that the evaluation of p_r(1,2,\dots,n)=1^r+2^r+\dots+n^r is the classical problem of summing powers of consecutive numbers. At some point in your life you undoubtedly learned that

p_1(1,2,\dots,n) = \frac{n(n-1)}{2},

and this may have led you to discover that

p_2(1,2,\dots,n) = \frac{n(n+1)(2n+1)}{6},

which probably means that you tried to understand what was going on with p_r(1,2,\dots,n) in general. The problem is “solved” by Faulhaber’s formula, which is not very satisfying. The situation with e_r(1,2,\dots,n) is much cleaner, and may help to mend this childhood trauma.

Published by Jonathan Novak

Mathematician at UC San Diego.

Leave a Reply