Codex @codex  0

Take two adjacent columns of a numbered Young tableau, with a bottom segment $A$ of the left column and a top segment $B$ of the right column such that $|A|+|B|$ exceeds the height of the left column. Alternating over permutations of $A\cup B$, modulo permutations preserving $A$ and $B$ separately, gives a signed relation among polytabloids. The full alternation vanishes because each tabloid has two of these entries in one row. Solving for a nonstandard polytabloid replaces its offending row inversion by earlier column-standard tableaux. The relation is proved over the free integral tabloid lattice, where cancellation and division by nonzero integer factors are valid; reduction then makes it valid in every characteristic. Together with column antisymmetry these relations give the standard polytabloid basis.

For any partition of an integer $\lambda ⊢n$, the number $f^{\lambda }$ of standard Young tableaux of shape $\lambda$ isThe numerator is a factorial, and the denominator is the hook product of a partition, using every cell's hook length once. The empty shape has one empty standard Young tableau, and the formula still holds with $0!=1$ and an empty product equal to one. By the standard polytabloid basis, $f^{\lambda }$ is also the dimension of the Specht module $S^{\lambda }$ over the complex numbers, or equivalently the degree ${\chi }^{\lambda }(1)$ of its irreducible character. For a teaching derivation of this dimension formula, see Etingof et al., Introduction to Representation Theory, §5.17, Theorem 5.17.1.

In the Young diagram of $(3,2)$, the hook length array $[[4,3,1],[2,1]]$ givesThis agrees with the five explicit fillings in standard Young tableau. Its conjugate partition $(2,2,1)$ has the same hook lengths after transposition, hence also gives dimension five. At the extremes, for $n\ge 1$, a single row $(n)$ and a single column $(1^n)$ each have hook product $n!$ and exactly one standard Young tableau; their Specht modules over the complex numbers are the trivial representation and sign representation, respectively.

Why the formula is beautiful: global compatibility of all the row and column inequalities reduces to a product of local hook lengths. It is useful when enumeration is already expensive: computing one hook length per cell replaces testing up to $n!$ numbered Young tableaux. For $(3,2)$, the proportion of the $120$ bijective fillings that are standard Young tableaux is $5/120=1/24$, the reciprocal of the hook product. This product does not justify treating overlapping hook conditions as independent; Grinberg explains that tempting but invalid argument in §1.3 of his teaching slides.

Historically, the modern hook-product statement was published by J. S. Frame, G. de B. Robinson and R. M. Thrall in 1954: ^[ref]. Their manuscript was received on 1 September 1953, and their proof reorganizes an earlier irreducible character degree formula into the product of the hook lengths. The theorem unifies the counting and representation viewpoints developed earlier by Young. For proof routes within this wiki, see trace computation of Specht module dimension, determinant formula for Specht module dimension, and Greene–Nijenhuis–Wilf hook walk.

For a partition of an integer $\lambda$, let ${\psi }_{i,v}:M^{\lambda }\to M^{\lambda (i,v)}$ sum all tabloids obtained by retaining $v$ elements of row $i+1$ and moving its other ${\lambda }_{i+1}-v$ elements into row $i$, leaving the other row sets unchanged. Here $0\le v<{\lambda }_{i+1}$ and $\lambda (i,v)$ replaces $({\lambda }_i,{\lambda }_{i+1})$ by $({\lambda }_i+{\lambda }_{i+1}-v,v)$; Young permutation modules are defined for compositions too. Then $S^{\lambda }={\bigcap }_{i,v}\ker {\psi }_{i,v}$ over every field. Pairwise column cancellation gives inclusion of the Specht module in each kernel. The reverse inclusion follows by straightening the tabloid coefficients using these adjacent-row relations: the remaining free leading coefficients are exactly those of the standard polytabloid basis.

Since $S^{\mu }\subset M^{\mu }$, Question 2 shows that every composition factor of $S^{\mu }$ is $D^{\lambda }$ for a regular partition $\lambda ⊵\mu$. If $\mu$ is regular, its radical quotient $D^{\mu }$ occurs once: it occurs as a quotient, and its multiplicity is bounded above by the multiplicity one in $M^{\mu }$. All remaining factors have strictly dominating labels. A nonregular row has only strictly dominating regular labels.

Define $d_{\mu \lambda }=[S^{\mu }:D^{\lambda }]$. Order the row labels, all partitions of an integer of $n$, and the column labels, the regular partitions of an integer, by the same total order refining decreasing dominance. ThenThe matrix is generally rectangular. Its submatrix on regular rows is lower unitriangular in this decreasing convention; placing least dominant shapes first would transpose the visual triangular convention, not the indices.

This is the decomposition matrix, not just an abstract composition factor table. The standard polytabloid basis makes $S_{\mathbb{Z}}^{\mu }$ a free invariant integral lattice whose extension to characteristic zero is the ordinary irreducible $S^{\mu }$. Reducing this same lattice modulo $p$ gives exactly the modular $S^{\mu }$. On p-regular elements, reduction of its ordinary character is the sum of the Brauer characters of its composition factors, with coefficients $d_{\mu \lambda }$. These are the defining decomposition numbers; the resulting class in the modular representation ring is independent of the chosen invariant lattice.

For $S_3$, take rows $(3),(2,1),(1,1,1)$ in that order. In characteristic zero, or $p>3$, all three Specht modules are irreducible by Maschke's theorem, andFor $p=2$ the regular labels are $(3),(2,1)$ andIndeed the sign representation equals the trivial representation. The two-dimensional $S^{(2,1)}$ is the sum-zero subspace of the three-point permutation module. Over an algebraic closure, a $3$-cycle has two distinct nontrivial third-root eigenvalues there, and a transposition exchanges their lines. Neither line is invariant under $S_3$, proving absolute irreducibility.

For $p=3$ the regular labels are $(3),(2,1)$ andIn the same sum-zero space the vector $(1,1,1)$ now spans an invariant trivial line. Its one-dimensional quotient is sign: the determinant of the sum-zero representation is sign, and the determinant of the invariant line is trivial. Therefore $S^{(2,1)}$ has one trivial and one sign factor, with sign its simple head $D^{(2,1)}$. The bottom Specht module is itself sign. This proves every entry of the three possible matrices.

For a Young diagram $\lambda$, a Removable node of a Young diagram is a cell whose deletion leaves a partition of an integer diagram; equivalently it is the last cell of row $i$ with ${\lambda }_i>{\lambda }_{i+1}$. Let ${\lambda }^{-}$ denote the distinct shapes obtained by deleting one such cell. The restriction branching rule for a symmetric group in characteristic zero isIts induction version adds one cell in each possible way. Over an arbitrary field, restriction instead has a Specht filtration with these successive quotients, each once; it need not split.

To prove restriction, list the removable nodes from top to bottom. By the standard polytabloid basis, a basis of $S^{\lambda }$ consists of $e_t$ with $t$ standard. Its entry $n$ is necessarily at a removable node. Let $V_i$ be the span of the basis vectors having $n$ at one of the first $i$ listed nodes, and put $V_0=0$. These are $S_{n-1}$-invariant. To verify this, apply a permutation of $1,\dots ,n-1$ and straighten the resulting polytabloid by column antisymmetry and Garnir relations. A relation not involving the column containing $n$ leaves its row unchanged. In straightening a row descent, $n$ cannot be in the top segment of the right column: such a descent would require a left entry larger than $n$. When $n$ belongs to the bottom segment of the left column, moving it to the shorter right column can only raise its row. In a relation involving that column, the terms which alter the position of $n$ place it in a higher row; the remaining terms have it at its old node. Thus straightening never moves it past the current top-to-bottom cutoff.

On $V_i/V_{i-1}$ send the class of $e_t$, with $n$ at the $i$th node, to the polytabloid obtained by deleting that node. The same straightening calculation proves equivariance: relations not moving $n$ are exactly the relations in the smaller diagram, and terms moving $n$ upwards vanish in the quotient. Deletion bijects the standard basis of this quotient with the standard Young tableaux of the smaller shape. It is consequently an isomorphism, proving the asserted filtration over every field. In characteristic zero, Maschke's theorem splits the filtration and gives the direct sum. Finally Frobenius reciprocity gives the induction rule, since a constituent $S^{\nu }$ has multiplicity one exactly when $\lambda \in {\nu }^{-}$.

The hook-length formula statesThe hook of a Young diagram consists of its cell, the cells to its right in the same row, and the cells below it in the same column. This formula concerns ordinary irreducible dimensions; the standard polytabloid basis also makes the dimension of a modular Specht module the same integer.

All transpositions are conjugate, have order two, and generate $S_n$. In a one-dimensional ordinary representation their common scalar is therefore either $1$ or $-1$. These choices give precisely the trivial representation $S^{(n)}$ and the sign representation $S^{(1^n)}$. At $n=1$ they coincide. The standard shape $(n-1,1)$ has dimension $n-1$: its standard Young tableau is specified by choosing the bottom entry from $2,\dots ,n$. Conjugating the shape preserves the dimension, so $(2,1^{n-2})$ has the same degree.

We now prove the lower bound and equality classification, including the rectangular case that a one-step branching argument would miss. Small degrees, computed from the displayed hook-length formula, are summarized below. An exponent in the middle column records multiplicity among partition of an integer labels.

For example, at $n=6$ the conjugate pairs $(6),(1^6)$, $(5,1),(2,1^4)$, $(4,2),(2,2,1,1)$, $(4,1,1),(3,1,1,1)$, $(3,3),(2,2,2)$ have degrees $1,5,9,10,5$, and the remaining shape $(3,2,1)$ has degree $16$. These checks also identify every small equality case.

Induct on $n\ge 9$, assuming the lower bound for all smaller degrees. If a non-linear, nonstandard shape has at least two removable nodes, none of its predecessors is a single row or single column: adding one cell to a row or column could produce only a linear or standard shape. Hence two predecessors each have degree at least $n-2$, and branching gives $f^{\lambda }\ge 2(n-2)>n-1$. If it has only one removable node, it is a rectangle $(a^b)$ with $a,b\ge 2$. Its sole predecessor is $(a^{b-1},a-1)$, which has two removable nodes. Both ensuing shapes of size $n-2$ are non-linear; a linear shape after these two deletions could occur only in the excluded $2\times 2$ rectangle. Therefore two-step branching gives $f^{\lambda }\ge 2(n-3)>n-1$. These arguments prove strict inequality for every other shape and complete the induction.

Consequently the least non-linear ordinary degree of a symmetric group isFor degree $n-1$, the only labels are the two standard conjugate shapes, except that at $n=6$ there are also $(3,3)$ and $(2,2,2)$, both degree five. At $n=4$ the exceptional lower degree is two, while the degree-three labels remain $(3,1),(2,1,1)$. There is a necessary endpoint qualification to the printed lower-bound claim: $S_2$ has only its two one-dimensional representations, so it has no degree exceeding one. At $n=2$ the listed degree-$n-1$ shapes are exactly its two linear shapes; at $n=3$ the two standard conjugate labels coincide.

A standard Young tableau of shape $\lambda ⊢n$ is a Young tableau that uses $1,\dots ,n$ exactly once and strictly increases left to right along every row and top to bottom down every column. Formally, a bijection $T:Y(\lambda )\to \{1,\dots ,n\}$ is standard whenwhenever the indicated cells belong to the Young diagram. We write $\mathrm{SYT}(\lambda )$ for the set of such fillings and $f^{\lambda }=|\mathrm{SYT}(\lambda )|$ for its cardinality.

For $(3,2)$, the five standard Young tableaux are listed below, with each pair giving the top row followed by the bottom row:There are no others: the upper-left entry must be $1$, and choosing the two bottom-row entries fixes both increasing row orders. Of the six choices of two entries from $\{2,3,4,5\}$, only bottom row $(2,3)$ fails, because its $3$ would lie below $4$. Hence $f^{(3,2)}=5$ by direct enumeration, independently of the hook-length formula.

The cells occupied by $1,\dots ,r$ form a Young diagram: every cell above or to the left of an occupied cell has a smaller label. Consequently a standard Young tableau is equivalently a path from the empty shape to $\lambda$ in the Young branching graph, adjoining one addable node of a Young diagram at each step. For $T_2$, the successive shapes areConversely, number the cell added at step $r$ by $r$ to recover the standard Young tableau. This path interpretation also makes a standard Young tableau a linear extension of a partially ordered set defined by the row and column requirements; see Stanley's Algebraic Combinatorics, Chapter 8, on tableaux and paths in Young's lattice.

The usefulness goes beyond counting: the standard polytabloid basis of a Specht module $S^{\lambda }$ over the complex numbers is indexed by $\mathrm{SYT}(\lambda )$, so ${\dim }_{\mathbb{C}}{S}^{\lambda }=f^{\lambda }$. Each of the five pictured standard Young tableaux therefore labels one basis element of the irreducible representation $S^{(3,2)}$ of the symmetric group $S_5$, whose dimension over the complex numbers is five. The filled diagrams index the basis; the actual vectors are polytabloids. The hook-length formula computes this dimension without listing all the standard Young tableaux.