\documentclass{beamer}
\usepackage{amsmath}
\usepackage{bookman}
\usetheme{Madrid}

\title{Lecture 4-19: Hook formula and symmetric functions}
\date{April 19, 2024}
\begin{document}
\begin{frame}
\titlepage
\end{frame}
\begin{frame}
\vskip .1in
Whole books are written and whole courses devoted to the representations of the symmetric group; while I cannot go into depth on this topic, there are couple of additional topics that I would like to mention.  I will give a beautiful formula for the number of standard tableaux of a fixed shape and give an inkling of the many connections between the symmetric group and symmetric polynomials.
\end{frame}
\begin{frame}
\vskip .1in
Given a Young diagram, each box in it corresponds to a \alert{hook}, consisting of itself and all boxes either directly below it or directly to its right; its \alert{length} is the number of boxes in it.  For example, starting with the partition $\lambda=(3,2,1)$, I have labelled each box in the corresponding Young diagram by the length of its hook below.
\[
\begin{matrix} 5&3&1\\3&1& \\1& &\end{matrix}
\]
Then we have 
\begin{alertblock}{Hook length formula}
If $n=|\lambda|$, then the number of standard tableaux of shape $\lambda$ equals $n!$ divided by the product of the hook lengths in the Young diagram of $\lambda$.
\end{alertblock}
\noindent Thus for example we have $\dim S^{(3,2,1)} = \frac {6!} {5\cdot3\cdot1\cdot3\cdot1} = 16$.
\end{frame}
\begin{frame}
Many proofs of this result have been given since the original one in 1954 by Frame, Robinson, and Thrall, which used the representation theory of $S_n$ in prime characteristic.  A straightforward proof by induction is given in Fulton's book, together with a heuristic argument which can be converted to a rigorous probabilistic proof.  More recently Pak and others have given a geometric proof, by computing the $n$-dimensional volume of a certain polytope.
\end{frame}
\begin{frame}
\vskip .1in
It turns out that the representations of $S_n$ as $n$ varies fit together in a beautiful way.  To see how this works, let $R_n$ be the free $\mathbb Z$-module spanned by the irreducible characters of $S_n$.  Make the direct sum $R=\bigoplus\limits_{n=0}^\infty R_n$ into a graded ring by decreeing that the product $\chi\circ\mu$ of the irreducible characters $\chi,\mu$ of $S_m,S_n$, respectively, be the induced character Ind$_{S_m\times S_n}^{S_{m+n}} \chi\times\mu$ of $S_{m+n}$, where $\chi\times\mu$ is regarded as a character of the direct product $S_m\times S_n$ via $\chi\times\mu(g,h) = \chi(g)\mu(h)$ and $S_m\times S_n$ is embedded in $S_{m+n}$ in the obvious way.  A straightforward argument using the transitivity of induction (Proposition 14 in DF, p. 898) shows that multiplication in $R$ is associative and commutative.   
\end{frame}
\begin{frame}
\vskip .1in
The ring $R$ then turns out to be isomorphic to a well-known ring $\Lambda$ arising in a different context.  Recall that a polynomial $p\in\mathbb Z[x_1,\ldots,x_n]$ is called \alert{symmetric} if it remains unchanged when the variables are permuted:  $p(x_1,\ldots,x_n) = p(x_{\sigma(1)},\ldots,x_{\sigma(n)}$ for all $\sigma\in S_n$.  Note that $p$ is symmetric if and only if the sum $h_i$ of its monomial terms of degree $i$ is symmetric for all $i$.  A \alert{symmetric function} $p=(p_1,p_2,\ldots)$ is then a tuple of symmetric polynomials $p_i$ in $x_1,\ldots,x_i$, such that $p_j(x_1,\ldots,x_i,0\ldots,0) = p_i(x_1,\ldots,x_i)$ for all indices $i,j$ with $i<j$.  For example, $p=(p_1,p_2,\ldots)$ has this property if we set $p_i=x_1+\ldots+x_i$.  It is clear that the sum and product of symmetric functions are symmetric.  Thus $\Lambda=\bigoplus\limits_{n=0}^\infty\Lambda_n$ has the structure of a commutative graded ring, where $\Lambda_n$ denotes the set of homogeneous symmetric functions of degree $n$.
\end{frame}
\begin{frame}
\vskip .1in
To any partition $\lambda$ one can attach a symmetric function, as follows.  We first broaden the definition of Young tableau, now declaring any filling of the boxes in a Young diagram by positive integers to be such a tableau.  We say that the tableau $T$ is \alert{semistandard} if the numbers in the boxes increase weakly across the rows but strictly down the columns.   For every semistandard tableau $T$ denote by $x^T$ (the {\sl weight} of $T$) the monomial $x_1^{a_1}\ldots x_m^{a_m}$, where the exponent $a_i$ counts the number of times $i$ appears in $T$.  Then the Schur polynomial $s_{\lambda,m}$ in $m$ variables is defined to be the sum $\sum_T x^T$ as $T$ runs over the semistandard tableaux using only the numbers 1 through m (but not necessarily all of them). 
\end{frame}
\begin{frame}
\vskip .1in
For example, if $\lambda$ has a single part $n$, then $s_{\lambda,m}$ is the \alert{$n$th complete symmetric polynomial} $h_n(x_1,\ldots,x_m)$, equal to the sum of all monomials in $x_1,\ldots,x_m$ of total degree $n$.  If instead $\lambda =(1,\ldots,1)$ with $n$ ones, then $s_{\lambda,m}$ equals $e_n(x_1,\ldots,x_m)$, the \alert{$n$th elementary symmetric polynomial in $x_1,\ldots,x_m$}, equal to the sum of all products of $n$ distinct variables among the $x_i$; note that $e_n(x_1,\ldots,x_m)=0$ if $m<n$.
\end{frame}
\begin{frame}
\vskip .1in
We further have $s_{(2,1),1}=0$, since there are no semistandard tableaux of shape $(2,1)$ using only the number 1, while $s_{(2,1),2} = x_1^2x_2+x_1x_2^2$.  The coefficient of $x_1x_2x_3$ in $s_{(2,1),3}$ is 2, since there are two standard tableaux of shape $(2,1)$.  As indicated by (but certainly not obvious from) the examples so far, it turns out that \alert{$s_{\lambda,i}$ is symmetric for every $\lambda$ and $i$}, whence $s_\lambda=(s_{\lambda,1},s_{\lambda,2},\ldots)$ is a symmetric function, called the \alert{Schur function} $s_\lambda$ corresponding to $\lambda$.  
\end{frame}
\begin{frame}
\vskip .1in
The connection between characters of $S_n$ and symmetric functions is then established by the following fundamental result.
\begin{alertblock}{Theorem: Fulton, Chapter 7}
The graded rings $R$ and $\Lambda$ are isomorphic by the map sending the character $\chi_\lambda$ of the Specht module $S^\lambda$ (lying in $R_n$) to $s_\lambda\in\Lambda_n$.
\end{alertblock}
\end{frame}
\begin{frame}
\vskip .1in
This result is particularly remarkable since most of the tableaux $T$ involved in the definition of $s_\lambda$ are not standard and play no role in the definition of $S^\lambda$.   The theorem mostly has to do with the representation theory of the infinite group $GL_n(\mathbb C)$, which involves semistandard tableaux in a crucial way.  The connection to $S_n$ amounts to a side benefit.
\end{frame}
\begin{frame}
\vskip .1in
By working with semistandard tableaux one can deduce the following restriction formula for representations of $S_n$.
\begin{alertblock}{Theorem:  restriction formula}
Given a partition $\lambda$of $n$, the restriction of the Specht module $S^\lambda$ to $S_{n-1}$ as the sum $\sum S^{\lambda'}$ as $\lambda'$ runs through the partitions whose diagrams are obtained from that of $\lambda$ by deleting one box.  In particular, this restriction is irreducible if and only if the diagram of $\lambda$ is a rectangle (all rows have the same length).
\end{alertblock}
\end{frame}
\begin{frame}
\vskip .1in
If one restricts $S^\lambda$ to $S_{n-1}$, then to $S_{n-2}$, and so on, all the way to $S_1$, one obtains the sum of $f^\lambda=\dim S^\lambda$ copies of the trivial representation.  So $f^\lambda$ equals the number of ways to reduce the diagram $D_\lambda$ of $\lambda$ to a single box by removing one box at a time, making sure that resulting shape is always a diagram.  Now the boxes that can be removed from $D_\lambda$ at the first step are exactly those which can be filled by the largest number $n$ in a standard tableau of shape $\lambda$, and similarly for the boxes that can be removed at the subsequent steps.
\end{frame}
\begin{frame}
In this way we recover the earlier result that \alert{$\dim S^\lambda$ equals the number of standard tableaux of shape $\lambda$}.  We conclude with the induction analogue of the restriction formula:  \alert{the representation induced  from $S_n$ to $S_{n+1}$ by $S^\lambda$ is the sum $\sum S^{\lambda"}$ as $\lambda"$ runs over the partitions whose diagrams are obtained from $D_\lambda$ by adding one box, possibly forming a new row by itself}.
\end{frame}
\end{document}