Chapter 29: Symmetric Functions and Young Tableaux

Why does a tableau shape determine a hook-length count?

Five tasks have precedence constraints arranged in two left-aligned rows of lengths three and two. A task must follow every task to its left and above it. How many schedules respect these constraints? Number each task by its position in the schedule. The resulting filling increases along rows and down columns: it is a standard Young tableau of shape $(3,2)$. This translates a scheduling problem into counting linear extensions of a finite partially ordered set.

Here is the chapter foundation in miniature. A partition is a decreasing sequence of positive row lengths. Its diagram uses English convention: the longest row is at the top, and columns run downward. A standard tableau uses $1,\ldots,n$ once each and increases in both directions. A semistandard tableau allows repetitions, with weakly increasing rows and strictly increasing columns. Its weight is the product of variables corresponding to its entries; summing these weights defines the Schur function $s_\lambda$. The one-row functions satisfy $s_{(r)}=h_r$, where $h_r$ sums all weakly increasing words of length $r$.

Three established tools will support the final investigation. The hook-length formula counts standard tableaux; row insertion sends a permutation to two standard tableaux of the same shape; and the one-box Pieri rule says that $s_\lambda s_{(1)}$ is the sum of $s_\nu$ over diagrams obtained by adding one corner cell. The optional sections supply deeper definitions, proofs, and connections. Completing their advanced arguments is not required for the foundation investigation.

29.1 Integer partitions and dominance order

Optional extension; not required to complete the chapter foundation. Dominance measures how concentrated a partition's mass is in its early rows. It will control which lower terms may occur in Schur functions and their deformations.

Write $\lambda\vdash n$ when $\lambda=(\lambda_1,\ldots,\lambda_\ell)$, $\lambda_1\geq\cdots\geq\lambda_\ell\gt0$, and $\lvert\lambda\rvert=\sum_i\lambda_i=n$. Pad with zeros whenever comparing lengths. Define

$$ D_\lambda=\{(i,j):1\leq i\leq\ell,\ 1\leq j\leq\lambda_i\},\qquad \lambda'_j=\#\{i:\lambda_i\geq j\}. $$

The conjugate partition $\lambda'$ records column lengths. Diagram containment, $\mu\subseteq\lambda$, means $\mu_i\leq\lambda_i$ for every $i$. Dominance compares partitions of the same size:

$$ \lambda\unrhd\mu\quad\Longleftrightarrow\quad \sum_{i=1}^r\lambda_i\geq\sum_{i=1}^r\mu_i\text{ for every }r\geq1. $$

Write $\mu\lhd\lambda$ for strict dominance. Reflexivity and transitivity follow from the prefix inequalities. If both directions hold, every prefix sum agrees, so successive differences give $\lambda_i=\mu_i$: antisymmetry follows. This is a partial order, not generally a total order.

Solved example. For $(3,2)$ and $(3,1,1)$, prefix sums are respectively $(3,5,5)$ and $(3,4,5)$; hence $(3,2)\unrhd(3,1,1)$. Their conjugates are $(2,2,1)$ and $(3,1,1)$, with the dominance direction reversed. In general conjugation reverses dominance. One route to this fact uses

$$ \sum_{j=1}^k\lambda'_j=\sum_i\min(\lambda_i,k), $$

and the equivalent characterization of majorization by the sums $\sum_i(\lambda_i-k)_+$. The equivalence is a short convexity argument; this is a proof route, with that lemma omitted.

Containment and dominance answer different questions. For equal sizes, containment forces equality, while dominance permits many distinct shapes. Moving a cell from a later row to an earlier row, when the result remains a partition, increases dominance. This supplies useful intuition, though checking prefix sums remains the reliable test.

Exercise. Compare $(4,1,1)$ and $(3,3)$, and explain what their comparison means for an algorithm that processes partitions in dominance order. Hint: Check the first two prefixes. Solution: The first prefixes are $4\gt3$; the second are $5\lt6$. Neither partition dominates the other. An algorithm must choose a total order extending the partial order, or retain a dependency graph; it cannot assume that every pair is comparable.

29.2 Standard and semistandard Young tableaux

Optional extension; not required to complete the chapter foundation. A diagram specifies positions; a tableau specifies labels subject to local inequalities. Those inequalities turn monomials into combinatorial objects.

A standard tableau of shape $\lambda\vdash n$ is a bijective filling $T:D_\lambda\to\{1,\ldots,n\}$ with $T(i,j)\lt T(i,j+1)$ and $T(i,j)\lt T(i+1,j)$ whenever the indicated cells exist. Let $f^\lambda$ denote its count. A semistandard tableau with alphabet $\{1,\ldots,N\}$ has positive entries, weak rows, and strict columns. Its content is $\mu=(\mu_1,\ldots,\mu_N)$, where $\mu_a$ counts entries equal to $a$, and its monomial is $x^T=\prod_a x_a^{\mu_a}$. When the content itself is a partition, the count is the Kostka number $K_{\lambda\mu}$.

For partition content, $K_{\lambda\mu}\neq0$ exactly when $\lambda\unrhd\mu$. Here is the necessary direction. Strict columns imply that an entry in row $i$ is at least $i$. Consequently all entries at most $r$ lie in the first $r$ rows, so $\mu_1+\cdots+\mu_r\leq\lambda_1+\cdots+\lambda_r$. Sufficiency requires a construction, for example an inductive placement of horizontal strips with prescribed sizes; that construction is omitted. In particular, the row-constant filling proves $K_{\lambda\lambda}=1$: all $\lambda_1$ ones must occupy the first row, then all $\lambda_2$ twos the second row, and so on.

A standard tableau also encodes a saturated chain in Young's lattice: the cells with entries at most $k$ form a partition $\lambda^{(k)}$, and one cell is added at each step. Conversely label the newly added cell by $k$. This is a bijection, proving that $f^\lambda$ counts such chains.

Exercise. Find all semistandard tableaux of shape $(2,2)$ with content $(2,2)$ on alphabet $\{1,2\}$. Hint: Each column has two different entries. Solution: Both columns must have $1$ above $2$, so the only filling is $[1,1]/[2,2]$. Its content and both row inequalities hold; the count is one. Content $(3,1)$ is impossible because three ones cannot fit in the first row, consistent with the failure of $(2,2)\unrhd(3,1)$.

29.3 Hook-length formula

Optional extension; not required to complete the chapter foundation. For a straight partition diagram $\lambda\vdash n$, define arm and leg lengths by $a(i,j)=\lambda_i-j$ and $l(i,j)=\lambda'_j-i$. The hook length is

$$ h(i,j)=a(i,j)+l(i,j)+1,\qquad f^\lambda=\frac{n!}{\prod_{(i,j)\in D_\lambda}h(i,j)}. $$

This theorem concerns standard tableaux of a straight shape. Skew diagrams do not generally obey the same single-product formula. The numerator counts unrestricted bijective labelings; the denominator corrects their precedence constraints in a highly structured way, rather than assigning independent probabilities to hooks.

Here is an algebraic proof using the last-label recurrence. Fix $L\geq\ell(\lambda)$, pad $\lambda$ with zeros, and put $b_i=\lambda_i+L-i$. These are strictly decreasing nonnegative integers. Define

$$ G(\lambda)=n!\frac{\prod_{i\lt j}(b_i-b_j)}{\prod_i b_i!}. $$

In the empty diagram, $b_i=L-i$, and numerator and denominator agree, so $G(\varnothing)=1$. Removing a corner in row $i$ reduces $b_i$ by one. For a legal removal the ratio is

$$ \frac{G(\lambda-\varepsilon_i)}{G(\lambda)} =\frac{b_i}{n}\prod_{j\neq i}\frac{b_i-b_j-1}{b_i-b_j} =\frac{b_i c_i}{n}, \qquad c_i=\prod_{j\neq i}\frac{b_i-b_j-1}{b_i-b_j}. $$

An illegal removal contributes zero to $b_ic_i$: either $b_i=0$, or $b_i-b_{i+1}=1$ makes a numerator vanish. To sum the ratios, use the rational function

$$ R(z)=\prod_{j=1}^L\frac{z-b_j-1}{z-b_j} =1-\sum_{i=1}^L\frac{c_i}{z-b_i}. $$

The equality follows by comparing its simple-pole residues and its value at infinity. Directly expanding the product gives the coefficient of $z^{-2}$ as $\binom L2-\sum_i b_i$. Expanding the partial fractions gives $-\sum_i b_i c_i$. Since $\sum_i b_i=n+\binom L2$, we obtain $\sum_i b_ic_i=n$. Thus $G(\lambda)$ is the sum of $G$ over all corner removals.

In every standard tableau the entry $n$ occupies a corner. Removing it gives a tableau of the smaller shape, and every smaller tableau extends uniquely. Hence $f^\lambda$ has exactly the same recurrence and initial value as $G$, proving $f^\lambda=G(\lambda)$ by induction.

To identify the denominator, the hook lengths in row $i$ are precisely the integers $1,\ldots,b_i$ except $b_i-b_j$ for $j\gt i$. One can check this by tracing the row's hooks as the column height drops: each lower row boundary skips its corresponding difference. Multiplying the row identity gives

$$ \prod_{(i,j)\in D_\lambda}h(i,j) =\frac{\prod_i b_i!}{\prod_{i\lt j}(b_i-b_j)}. $$

This completes the hook-length proof. For $(3,2)$, choose $L=2$, so $b=(4,2)$ and $G=5!(4-2)/(4!2!)=5$.

The diagram labels every cell by its hook length. Orange marks the hook based at $(1,2)$: its own cell, the cell to its right, and the cell below it. The red outline singles out the base cell. The highlighted hook has exactly three cells.

Exercise. Compute $f^{(3,1)}$ in two ways. Hint: Its hooks have lengths $4,2,1,1$, and its removable corners leave shapes $(2,1)$ and $(3)$. Solution: The product is eight, so $f^{(3,1)}=24/8=3$. The recurrence gives $f^{(2,1)}+f^{(3)}=2+1=3$. These checks exercise both the product and its combinatorial boundary condition.

29.4 Monomial, elementary, and complete homogeneous symmetric functions

Optional extension; not required to complete the chapter foundation. Work first with symmetric polynomials in $N$ commuting variables over $\mathbb Q$. Setting $x_N=0$ produces compatible families of bounded degree; the resulting graded ring of symmetric functions is $\Lambda_{\mathbb Q}$. Its degree-$n$ component has dimension equal to the number of partitions of $n$. Infinite sums below mean degreewise stable families, not numerical convergence statements.

The monomial function $m_\lambda$ sums distinct monomials whose positive exponents are the parts of $\lambda$. The elementary function $e_r$ selects distinct variable indices, while the complete homogeneous function $h_r$ allows repetitions:

$$ e_r=\sum_{i_1\lt\cdots\lt i_r}x_{i_1}\cdots x_{i_r},\qquad h_r=\sum_{i_1\leq\cdots\leq i_r}x_{i_1}\cdots x_{i_r}. $$

Set $e_0=h_0=1$ and $h_r=0$ for $r\lt0$. For a partition define $e_\lambda=\prod_i e_{\lambda_i}$ and $h_\lambda=\prod_i h_{\lambda_i}$. Each of $\{m_\lambda\}$, $\{e_\lambda\}$, and $\{h_\lambda\}$ is a homogeneous basis. For the elementary basis, the fundamental theorem of symmetric polynomials gives the generators $e_1,e_2,\ldots$ without algebraic relations in the stable ring. The complete basis follows from the inverse-series identity below.

Choosing whether a variable is present gives a two-term factor; choosing its multiplicity gives a geometric series. Therefore

$$ E(u)=\sum_{r\geq0}e_ru^r=\prod_i(1+x_i u),\qquad H(u)=\sum_{r\geq0}h_ru^r=\prod_i(1-x_i u)^{-1},\qquad E(-u)H(u)=1. $$

Solved example. In degree two, $e_2=m_{(1,1)}$, $h_2=m_{(2)}+m_{(1,1)}$, and $h_1^2=m_{(2)}+2m_{(1,1)}$. Hence $h_2=h_1^2-e_2$. In three variables,

$$ h_2=x_1^2+x_2^2+x_3^2+x_1x_2+x_1x_3+x_2x_3. $$

The exponent pattern $(2)$ has three distinct realizations; $(1,1)$ also has three. Summing over all permutations of the exponent vector without removing duplicates would incorrectly count each mixed monomial twice.

The coefficient of $u^r$ in the inverse-series identity is $\sum_{j=0}^r(-1)^j e_jh_{r-j}=0$ for $r\geq1$. This supplies exact conversion formulas and a useful symbolic validation method.

Exercise. Express $h_3$ in $e_1,e_2,e_3$. Hint: Use the coefficient of $u^3$, and substitute the degree-two identity. Solution: $h_3-e_1h_2+e_2h_1-e_3=0$, so $h_3=e_1^3-2e_1e_2+e_3$. At three variables all equal to one this gives $27-18+1=10$, the number $\binom{3+3-1}{3}$ of weakly increasing triples from a three-letter alphabet.

29.5 Power sums and Schur functions

Optional extension; not required to complete the chapter foundation. Power sums isolate cycle lengths; Schur functions isolate tableau shapes. They will become two coordinate systems for character theory.

Define $p_r=\sum_i x_i^r$ and $p_\lambda=\prod_i p_{\lambda_i}$. Over $\mathbb Q$ these form a basis. Taking the formal logarithm of $H(u)$ proves

$$ H(u)=\exp\left(\sum_{r\geq1}\frac{p_r u^r}{r}\right),\qquad n h_n=\sum_{r=1}^n p_r h_{n-r}. $$

The second equation follows by differentiating and comparing coefficients. Thus $h_2=(p_1^2+p_2)/2$ and $h_3=(p_1^3+3p_1p_2+2p_3)/6$. The rational coefficient field matters here; the power sums do not constitute an integral basis of $\Lambda_{\mathbb Z}$.

Define $s_\lambda(x_1,\ldots,x_N)=\sum_T x^T$, summing semistandard tableaux on $\{1,\ldots,N\}$. These stable polynomials are symmetric. A combinatorial proof pairs entries $a,a+1$ occurring together in a column, freezes those pairs, and exchanges the counts of the remaining entries in each row. This Bender–Knuth involution exchanges their total multiplicities while preserving the tableau inequalities. Since adjacent swaps generate variable permutations, symmetry follows. Verifying preservation at paired/unpaired boundaries is the local lemma behind this proof sketch.

Collecting monomials by exponent pattern yields

$$ s_\lambda=\sum_{\mu\vdash n}K_{\lambda\mu}m_\mu =m_\lambda+\sum_{\mu\lhd\lambda}K_{\lambda\mu}m_\mu. $$

The dominance and diagonal facts from 29.2 make the transition matrix unitriangular, so Schur functions form a basis. Their determinantal expression is the Jacobi–Trudi identity:

$$ s_\lambda=\det\bigl(h_{\lambda_i-i+j}\bigr)_{1\leq i,j\leq L},\qquad L\geq\ell(\lambda). $$

Proof mechanism, with a path-model lemma omitted. Encode each $h_r$ by weighted weakly increasing lattice paths. Expand the determinant as signed path families. At the first intersection, switch the two path tails; weight is preserved and sign reverses. The remaining nonintersecting families encode semistandard tableaux. This explains the cancellation, but a full proof also specifies starts, ends, and the path-to-tableau map.

Solved example. The determinant for $(2,1)$ is $h_2h_1-h_3$, giving

$$ s_{(2,1)}=\frac{p_1^3-p_3}{3}=m_{(2,1)}+2m_{(1,1,1)}. $$

Indeed $p_1^3$ has coefficients $1,3,6$ on exponent patterns $(3),(2,1),(1,1,1)$; subtracting $p_3$ removes the first pattern and dividing by three gives $1,2$ on the other two. This recovers the tableau enumeration without relying on a numerical substitution.

Exercise. Compute $s_{(2,2)}$ in the $h$ basis and evaluate it at two variables equal to one. Hint: Use a two-by-two determinant and $h_r(1,1)=r+1$. Solution: $s_{(2,2)}=h_2^2-h_1h_3$, so the value is $3^2-2\cdot4=1$. The unique tableau is $[1,1]/[2,2]$; this independently checks the determinant.

29.6 Robinson–Schensted–Knuth correspondence

Optional extension; not required to complete the chapter foundation. Row insertion records how local comparisons reorganize a sequence. Its output separates value information from the history of cell creation.

To insert $a$ into a semistandard tableau, find the leftmost entry strictly greater than $a$ in the first row. Replace it with $a$ and insert the displaced entry into the next row. If no entry is greater, append $a$ and stop. Continue until one new corner cell appears. Strictly greater is essential: equal values remain in a weakly increasing row. The row-bumping lemma guarantees preservation of strict columns and the partition shape. It also says that inserting a weakly larger value next produces a new cell strictly farther to the right; its proof follows the successive bump positions through the rows.

For a permutation $w=w_1\cdots w_n$, start with empty $P,Q$. Insert $w_k$ into $P$ and put $k$ in the newly created cell of $Q$. Both are standard and have the same shape. The full RSK correspondence uses a nonnegative integer matrix $A=(a_{ij})$: form $a_{ij}$ copies of the pair $(i,j)$, sorted lexicographically by $i$ then $j$. Insert the bottom entry $j$ into $P$ and record the top entry $i$ in $Q$. Both tableaux are semistandard; $P$ has content given by column sums of $A$, and $Q$ by row sums. Equal top entries produce a horizontal strip by the bumping lemma, making the repeated entries of $Q$ column-strict.

Solved trace. For $w=31425$, use the row notation introduced earlier.

At step four, $2$ bumps $4$, which appends after $3$ in the second row. All columns remain strict. To reverse the last step, remove the cell labeled $5$ in $Q$ and the corresponding $5$ in $P$. To reverse step four, remove the $4$ from the second row of $P$, replace the rightmost entry strictly less than $4$ in the row above (namely $2$), and output $2$. Continuing reverse insertion recovers $3,1,4,2,5$ in chronological order. For general biwords, remove a largest entry of $Q$, choosing the rightmost cell among equal largest entries, and reverse-bump through $P$. This gives a genuine inverse, so RSK is a bijection; details are developed in Knuth's original paper.

For permutations, the first row length is the length of a longest increasing subsequence, and the first column length is the length of a longest decreasing subsequence. The first claim follows from tracking, at each prefix, the least attainable final values of increasing subsequences of each length: insertion replaces the first final value greater than the new letter. The column claim is the companion Schensted theorem; its general proof is omitted. Here $1,2,5$ is increasing of length three, while the prefix tracking rules out length four.

Exercise. Run matrix RSK on $A=\begin{pmatrix}1&1\\1&0\end{pmatrix}$. Hint: The biword has top row $1,1,2$ and bottom row $1,2,1$. Solution: The insertion sequence gives $[1]$, then $[1,2]$, then $[1,1]/[2]$. The recording tableau is also $[1,1]/[2]$. Both contents are $(2,1)$, matching the respective column and row sums. Reverse the cell with recording label $2$ first to recover the pair $(2,1)$.

29.7 Pieri and Littlewood–Richardson rules

Optional extension; not required to complete the chapter foundation. Schur multiplication adds boxes, with multiplicities determined by admissible skew fillings. A skew diagram $\nu/\lambda$ is the set difference $D_\nu\setminus D_\lambda$, requiring $\lambda\subseteq\nu$.

A horizontal strip has at most one cell in each column; a vertical strip has at most one in each row. The Pieri identities are

$$ s_\lambda h_r=\sum_{\nu:\,\nu/\lambda\text{ horizontal }r\text{-strip}}s_\nu, \qquad s_\lambda e_r=\sum_{\nu:\,\nu/\lambda\text{ vertical }r\text{-strip}}s_\nu. $$

For the first identity, insert a weakly increasing word of length $r$ into a tableau of shape $\lambda$. The bumping lemma places the new cells in different columns. Reverse insertion from rightmost new cell to leftmost recovers the word and the original tableau. This is a weight-preserving bijection, proving the identity. The second follows by the involution $\omega$ on symmetric functions with $\omega(h_r)=e_r$ and $\omega(s_\lambda)=s_{\lambda'}$; the latter property follows from dual Jacobi–Trudi.

Solved example. Adding one box to $(2)$ gives only $(3)$ and $(2,1)$, so $s_{(2)}s_{(1)}=s_{(3)}+s_{(2,1)}$. In the $h$ basis it is $h_2h_1=h_3+(h_2h_1-h_3)$. This establishes the identity for all numbers of variables. Adding a horizontal two-strip to $(2)$ gives $(4),(3,1),(2,2)$, so $s_{(2)}^2=s_{(4)}+s_{(3,1)}+s_{(2,2)}$.

More generally,

$$ s_\lambda s_\mu=\sum_\nu c_{\lambda\mu}^{\nu}s_\nu. $$

The Littlewood–Richardson rule counts semistandard skew tableaux of shape $\nu/\lambda$ and content $\mu$ whose reading word, read right to left along rows from top to bottom, is a lattice word. In every prefix, the number of $i$'s must be at least the number of $(i+1)$'s, for each $i\geq1$. These are counts of tableaux, so the coefficients are nonnegative integers. The general proof uses insertion or jeu de taquin and is omitted; the Pieri argument above proves its one-row case directly.

For $\lambda=\mu=(2,1)$ and $\nu=(3,2,1)$, the skew cells are $(1,3),(2,2),(3,1)$. They share no row or column, so there are no adjacency inequalities. Content $(2,1)$ requires two ones and one two. Of the words $112,121,211$, exactly the first two satisfy the prefix condition. Thus $c_{(2,1),(2,1)}^{(3,2,1)}=2$: multiplicities need not be one.

Exercise. Compute $s_{(1,1)}s_{(1)}$ and check it in two variables. Hint: Add one box to a two-cell column. Solution: The shapes are $(2,1)$ and $(1,1,1)$, giving $s_{(2,1)}+s_{(1,1,1)}$. In two variables the second term vanishes, while the first is $x_1^2x_2+x_1x_2^2=x_1x_2(x_1+x_2)$. Vanishing after specialization is consistent with the stable identity, but a two-variable check alone could not detect the column-of-three term.

29.8 Symmetric-group characters

Optional extension; not required to complete the chapter foundation. Sections 30.1 and 30.2 are recommended later background for representations and characters, not entry requirements. The bridge needed here is short: a complex representation assigns matrices $\rho(g)$ to group elements, respecting multiplication; its character is the trace $\chi(g)=\operatorname{tr}\rho(g)$. An irreducible representation has no proper nonzero invariant subspace. For a full treatment beyond this bridge, see Macdonald, Chapter I, §7 and Appendix A.

Conjugacy classes of $S_n$ are indexed by cycle-type partitions $\mu$. If $m_r(\mu)$ is the number of parts equal to $r$, put $z_\mu=\prod_r r^{m_r(\mu)}m_r(\mu)!$. A permutation of type $\mu$ has centralizer order $z_\mu$, hence class size $n!/z_\mu$. Irreducible complex representations are indexed by partitions $\lambda\vdash n$; their Specht modules have dimension $f^\lambda$. This classification is an established representation-theoretic theorem, not a consequence of simply counting partitions.

The Frobenius characteristic of a class function is

$$ \operatorname{ch}(\chi)=\sum_{\mu\vdash n}\frac{\chi(\mu)}{z_\mu}p_\mu, \qquad \operatorname{ch}(\chi^\lambda)=s_\lambda. $$

Thus the coefficient of $p_\mu$ in $s_\lambda$, multiplied by $z_\mu$, is a character value. Notice the distinction between the ordinary product of symmetric functions, corresponding to induction from $S_a\times S_b$ to $S_{a+b}$, and pointwise multiplication of characters of a fixed $S_n$, corresponding to tensor products. Littlewood–Richardson coefficients describe the first operation.

Solved example. The three conjugacy types of $S_3$ have $z$ values $6,2,3$ and class sizes $1,3,2$.

The middle representation can be realized as the plane of vectors with coordinate sum zero inside the permutation representation on $\mathbb C^3$. The latter trace equals the number of fixed coordinates; remove its one-dimensional constant subspace to obtain $2,0,-1$. Its characteristic is $(2/6)p_1^3-(1/3)p_3=s_{(2,1)}$, matching 29.5. The hook formula gives the dimension two independently.

An application is decomposition of tensor state spaces under permutation symmetry. The Schur–Weyl theorem, with its proof omitted here, decomposes $(\mathbb C^N)^{\otimes n}$ into factors indexed by $\lambda$, pairing a general-linear-group module of dimension $s_\lambda(1^N)$ with a Specht module of dimension $f^\lambda$. For $N=n=3$, the dimension check is $27=10\cdot1+8\cdot2+1\cdot1$. This organizes repeated symmetry types in multilinear algebra and quantum state calculations.

Exercise. Check the norm of the middle character and interpret the earlier one-box product as induction. Hint: Weight the squares by class sizes. Solution: Its squared norm is $(1\cdot4+3\cdot0+2\cdot1)/6=1$. Inducing the trivial representation of $S_2\times S_1$ to $S_3$ gives the permutation action on three cosets. Its characteristic is $s_{(2)}s_{(1)}=s_{(3)}+s_{(2,1)}$, with dimensions $3=1+2$.

29.9 Hall inner product and Cauchy identities

Optional extension; not required to complete the chapter foundation. Orthogonality makes coefficient extraction intrinsic. Work in $\Lambda_{\mathbb Q}$ with the symmetric bilinear Hall inner product defined by

$$ \langle p_\lambda,p_\mu\rangle=\delta_{\lambda\mu}z_\lambda. $$

Distinct degrees are orthogonal. Over real coefficients this is positive definite, since $z_\lambda\gt0$. Over complex coefficients this displayed definition is bilinear; a positive Hermitian form would additionally conjugate one argument.

For independent finite alphabets $x,y$, interpreted formally degree by degree, the Cauchy identities are

$$ \prod_{i,j}(1-x_i y_j)^{-1} =\sum_\lambda s_\lambda(x)s_\lambda(y) =\sum_\lambda\frac{p_\lambda(x)p_\lambda(y)}{z_\lambda}, $$

$$ \prod_{i,j}(1+x_i y_j) =\sum_\lambda s_\lambda(x)s_{\lambda'}(y). $$

Proof mechanism. Expanding each geometric factor in the first product enumerates nonnegative integer matrices $A$, with weight $\prod_{i,j}(x_i y_j)^{a_{ij}}$. Matrix RSK converts them into pairs of semistandard tableaux of a common shape. Recording entries carry the $x$ weight and insertion entries the $y$ weight, giving the Schur sum. Taking the formal logarithm of the product gives $\sum_{r\geq1}p_r(x)p_r(y)/r$; expanding its exponential gives the power-sum sum, since each multiplicity contributes the factorial in $z_\lambda$. This proves the first identity by two independent expansions. Applying $\omega$ in the $y$ alphabet, where $\omega(p_r)=(-1)^{r-1}p_r$, gives the second.

The power-sum kernel reproduces any symmetric function under pairing in the $x$ variables. Write it instead in its Schur expansion and pair it with $s_\mu(x)$. Independence of the $s_\lambda(y)$ implies $\langle s_\lambda,s_\mu\rangle=\delta_{\lambda\mu}$. This derives orthonormality without assuming it in advance. Consequently $c_{\lambda\mu}^{\nu}=\langle s_\lambda s_\mu,s_\nu\rangle$.

Solved example. The common bidegree-two part of the Cauchy kernel is

$$ s_{(2)}(x)s_{(2)}(y)+s_{(1,1)}(x)s_{(1,1)}(y) =\frac{p_1(x)^2p_1(y)^2+p_2(x)p_2(y)}2. $$

Use $s_{(2)}=(p_1^2+p_2)/2$ and $s_{(1,1)}=(p_1^2-p_2)/2$: the mixed terms cancel. For the norm of $s_{(2,1)}=(p_1^3-p_3)/3$, the values $z_{(1,1,1)}=6$ and $z_{(3)}=3$ give $(6+3)/9=1$. Its pairing with $s_{(3)}=(p_1^3+3p_1p_2+2p_3)/6$ is $(6-6)/18=0$.

Exercise. Show that the degree-$n$ component of the Cauchy kernel has the reproducing property for $p_\mu$ with $\mu\vdash n$. Hint: Only one power-sum summand survives. Solution: Pairing in $x$ gives $z_\mu p_\mu(y)/z_\mu=p_\mu(y)$. Linearity proves reproduction for every degree-$n$ function. As a separate check, $\langle p_2,p_1^2\rangle=0$ and $\langle p_2,p_2\rangle=2$.

29.10 Hall–Littlewood, Jack, and Macdonald polynomials

Optional research specialization; not required to complete the chapter foundation. Deforming the inner product changes an orthogonal basis while preserving its leading monomials and dominance restrictions. Use the monic $P$ normalization throughout; it differs from the dual $Q$, integral $J$, and modified $\widetilde H$ normalizations.

For algebraically independent $q,t$, work over $\mathbb Q(q,t)$ and define

$$ \langle p_\lambda,p_\mu\rangle_{q,t} =\delta_{\lambda\mu}z_\lambda \prod_{i=1}^{\ell(\lambda)}\frac{1-q^{\lambda_i}}{1-t^{\lambda_i}}. $$

The Macdonald functions are characterized by

$$ P_\lambda(x;q,t)=m_\lambda+\sum_{\mu\lhd\lambda}u_{\lambda\mu}(q,t)m_\mu, \qquad \langle P_\lambda,P_\mu\rangle_{q,t}=0\quad(\lambda\neq\mu). $$

Existence with dominance triangularity is a theorem, not an automatic consequence of ordinary Gram–Schmidt on any total order. Proof sketch; prerequisites omitted: a commuting family of triangular, self-adjoint Macdonald difference operators has distinct generic eigenvalues and produces this basis. Uniqueness follows by induction and orthogonality. Operator construction and its self-adjointness proof are beyond this chapter. The definitions and specializations are established in Macdonald, Chapter VI, §§4 and 10.

The following specializations use the same monic convention:

The limits concern coefficients; when $\alpha$ is a noninteger real number one may take $0\lt t\lt1$. Hall–Littlewood at $t=0$ gives Schur, and its coefficientwise limit at $t=1$ gives $m_\lambda$. Its scalar product is singular at $t=1$, so that limit is not an orthogonality assertion at the singular endpoint. Jack at $\alpha=1$ gives Schur. Generic parameter definitions also allow formal rational coefficients, but specialized parameters must avoid uncancelled poles.

Solved derivation in degree two. Dominance gives $(2)\unrhd(1,1)$; hence $P_{(1,1)}=m_{(1,1)}$ and $P_{(2)}=m_{(2)}+c\,m_{(1,1)}$. Put $A=(1-q)/(1-t)$ and $B=(1-q^2)/(1-t^2)$. Since $m_{(2)}=p_2$ and $m_{(1,1)}=(p_1^2-p_2)/2$, orthogonality of the power sums gives

$$ \langle m_{(2)},m_{(1,1)}\rangle_{q,t}=-B,\qquad \langle m_{(1,1)},m_{(1,1)}\rangle_{q,t}=\frac{A^2+B}{2}. $$

Solving $-B+c(A^2+B)/2=0$ yields the exact result

$$ P_{(2)}(x;q,t)=m_{(2)}+ \frac{(1-t)(1+q)}{1-qt}m_{(1,1)}. $$

This is a complete calculation, not a proof sketch. Setting $q=0$ gives $P_{(2)}^{\mathrm{HL}}=m_{(2)}+(1-t)m_{(1,1)}$. For Jack, $A\to\alpha$ and $B\to\alpha$, so $c\to2/(\alpha+1)$. On the diagonal $q=t$ the generic coefficient simplifies to one, recovering $s_{(2)}$. For $q=1/2,t=1/3$, it is $6/5$, an exact rational check.

One instructive product is

$$ P_{(1)}^2=P_{(2)}+ \left(2-\frac{(1-t)(1+q)}{1-qt}\right)P_{(1,1)}. $$

Its Hall–Littlewood coefficient on $P_{(1,1)}$ is $1+t$; its Jack coefficient is $2\alpha/(\alpha+1)$. Setting $q=t$ recovers the one-box Schur coefficient one. The formulas exhibit parameter-dependent multiplication, not unchanged Littlewood–Richardson counts.

Established results and research context. The historical Macdonald positivity conjecture is a theorem: the modified functions $\widetilde H_\mu$ have Schur coefficients in $\mathbb N[q,t]$. Haiman's primary proof realizes those coefficients through geometry and representations; Hilbert schemes and the relevant graded modules are omitted prerequisites. This positivity statement concerns modified $\widetilde H$, not the monic $P$ coefficients just computed. Haglund–Haiman–Loehr prove a filling formula for modified Macdonald polynomials. Their statistic definitions and proof are omitted here; neither result is being presented as open. No unverified current open problem is required for this chapter.

Exercise. Specialize the product to Jack parameter $\alpha=2$ and to Hall–Littlewood parameter $t=1/2$. Hint: First compute the coefficient $c$ in each monic basis. Solution: Jack gives $c=2/3$ and $P_{(1)}^2=P_{(2)}^{(2)}+(4/3)P_{(1,1)}^{(2)}$. Hall–Littlewood gives $c=1/2$ and $P_{(1)}^2=P_{(2)}^{\mathrm{HL}}+(3/2)P_{(1,1)}^{\mathrm{HL}}$. Both identities follow by expanding in $m_{(2)},m_{(1,1)}$. Different rational coefficients reflect different bases, not fractional tableau counts.

Run RSK and verify a symmetric-function multiplication rule

The investigation connects an algorithm, a counting formula, and a polynomial identity. Its foundation track uses the definitions and three tools given in the opening section; the parameter-deformation task and further theory are optional extensions. Record the distinction between an exhaustive finite check, a symbolic proof of one identity, and a proof of a general theorem.

Worked solutions and assessment guide. The warm-up answers are $5!/24=5$ and $(3,2)\unrhd(3,1,1)$; the opening card gives the full five-element list. Award calculation credit only when the cell hooks and prefix sums are shown. RSK ends with $P=[1,2,5]/[3,4]$ and $Q=[1,3,5]/[2,4]$; reverse outputs are $5,2,4,1,3$, which reverse to the original input. The first-row histories are $[3]$, $[1]$, $[1,4]$, $[1,2]$, and $[1,2,5]$. Their lengths certify LIS length three by the least-tail invariant, and $1,2,5$ witnesses attainment.

For the proof problem, $s_{(2)}=h_2$, $s_{(1)}=h_1$, and $s_{(3)}=h_3$, so the determinant immediately gives the identity. The independent bijection is completely explicit. If $c\geq b$, insertion appends, giving the row $[a,b,c]$ of shape $(3)$. If $c\lt a$, it bumps $a$ and gives $[c,b]/[a]$. If $a\leq c\lt b$, it bumps $b$ and gives $[a,c]/[b]$. Both latter outputs have shape $(2,1)$ and satisfy weak rows and a strict first column.

Conversely, for a tableau $[u,v]/[w]$ with $u\leq v$ and $u\lt w$, reverse-insert $w$: if $v\lt w$, replace $v$ by $w$ and output $v$; otherwise replace $u$ by $w$ and output $u$. The resulting two-cell row is weakly increasing. A three-cell row reverses by removing its last letter. These are inverse maps and preserve the multiset of letters, hence every monomial weight. This proves the identity without relying on the full Littlewood–Richardson theorem.

The expected finite histogram is:

The counts sum to 24. In general the RSK bijection proves $n!=\sum_{\lambda\vdash n}(f^\lambda)^2$, because pairs of standard tableaux of shape $\lambda$ number $(f^\lambda)^2$. The displayed histogram is a small instance, not the general proof.

For the three-variable polynomial check, $h_2h_1$ has coefficients $1,2,3$ on each monomial of exponent patterns $(3),(2,1),(1,1,1)$ respectively. The Schur summands have coefficients $1,1,1$ for $s_{(3)}$ and $0,1,2$ for $s_{(2,1)}$, giving the same dictionary. Their evaluations at all ones are $18=10+8$; use this as a secondary check after coefficient comparison. Credit for the exploration requires the actual enumeration method or complete table, not just the expected totals.

The optional deformation task shows exactly why dominance belongs here: only the dominated shape $(1,1)$ may correct the leading term $m_{(2)}$. Orthogonality determines its coefficient, and changing that coefficient changes the product expansion. Hall–Littlewood, Jack, and Macdonald families retain the partition indexing and triangular structure while enriching their weights; ordinary tableau multiplicities reappear at the Schur specializations.

As an application, a sequence of ranked observations can be analyzed for its longest increasing subsequence without checking all subsequences. Maintaining the first insertion row uses binary search to update the least possible tail at each length, giving an $O(n\log n)$ LIS algorithm for distinct values. For $31425$, the increasing signal has length three. Full RSK additionally records the shape and inverse history, while the scheduling interpretation at the beginning uses $f^\lambda$ to count admissible orders. These are concrete uses of tableau structure; numerical experiments become mathematical conclusions only within the scope of their validation.