These advanced notes develop combinatorial representation theory through the language of tableaux, words, and insertion algorithms. They are written as a sequel to earlier material on symmetric functions, tableaux, and basic representation theory, not as a first introduction to those subjects. The central goal is to show how partitions, Young tableaux, and permutation data encode representations of symmetric groups and then reappear in Hecke algebras, crystals, and canonical bases. The early chapters build the basic toolkit: tableaux and words lead naturally to the Robinson-Schensted-Knuth correspondence, which becomes a bridge between combinatorics and representation theory. From there, the course turns to Specht modules, Young symmetrizers, characters, branching rules, dimensions, and seminormal forms, giving concrete realizations of irreducible representations and their internal structure. Later chapters connect these ideas to Robinson-Schensted theory, crystal graphs of type A, and classical tableau dynamics such as jeu de taquin, promotion, and evacuation. The final part broadens the setting to Hecke algebras, $q$-deformations, Kazhdan-Lusztig theory, and canonical bases. Those chapters use more advanced representation-theoretic language, but the role of the notes is consistent throughout: track which tableau labels, local operators, and basis constructions survive as the ambient algebra changes. The notes assume prior exposure to finite group representations, modules over algebras, class functions, symmetric functions, tensor products, and the basic language of highest-weight representations. The later chapters also use standard vocabulary from crystals, quantum groups, Hecke algebras, and Kazhdan-Lusztig theory; when that vocabulary first enters, it is recalled only to the extent needed for the type $A$ tableau applications. # Introduction This opening chapter sets the agenda for the notes: we study representations whose bases, characters, and structure constants are controlled by tableaux and related combinatorial objects. The central example is the symmetric group $S_n$, but the course repeatedly moves between group representations, symmetric functions, insertion algorithms, crystals, and Hecke algebras. The point of the introduction is to fix the guiding questions and recall the vocabulary that will be used throughout, rather than to make the later advanced machinery self-contained. The preceding courses in algebraic combinatorics treated symmetric functions, Young diagrams, tableaux, and enumerative identities as objects in their own right. Here those objects acquire representation-theoretic meaning: a Schur function becomes a character shadow, a standard tableau becomes a basis vector, and an insertion algorithm becomes a way of seeing decomposition and symmetry. ## The Guiding Problem What does it mean for a representation to have a combinatorial model? In this course the answer is not just that dimensions are counted by familiar objects. We want bases indexed by tableaux, actions described by explicit local rules, characters encoded by symmetric functions, and structural operations reflected by operations on diagrams and words. [motivation] ### From Counting to Structure A typical enumerative identity says that two finite sets have the same size. Representation theory asks for more: if two vector spaces have the same dimension, is there a natural [linear map](/page/Linear%20Map) between them, or a group action that explains why the equality exists? Combinatorial representation theory sits between these viewpoints. It tries to replace a bare equality of numbers by a structured correspondence between bases, characters, and modules. ### Why the Symmetric Group Is Central The symmetric group $S_n$ is large enough to contain rich representation theory and rigid enough to admit concrete combinatorial models. Its irreducible representations over characteristic zero are indexed by partitions of $n$, the same objects that index Schur functions and Young diagrams. This shared indexing is the first sign of a deeper dictionary. ### Why Algorithms Matter Algorithms such as Schensted insertion and RSK do more than produce bijections. They organise words and permutations into shapes, and those shapes record representation-theoretic information. Chapters 1 and 2 make this slogan precise through insertion, plactic equivalence, and RSK; Chapters 3 through 6 connect the resulting tableaux to Specht modules; Chapters 7, 9, and 10 return to the same shapes through crystal operators and Hecke algebra cells. [/motivation] The motivation above points to a recurring task: replace an abstract [vector space](/page/Vector%20Space) by a basis that can be named and manipulated. To make that task precise, we begin with a broad definition of the kind of model we are trying to build. [definition: Combinatorial Representation Model] A combinatorial representation model for a representation $V$ of an algebraic object $A$ consists of a finite or [countable set](/page/Countable%20Set) $B$, a basis $(v_b)_{b \in B}$ of $V$, a representation homomorphism from $A$ or its acting algebra into $\operatorname{End}(V)$, and explicit combinatorial rules describing the corresponding endomorphisms on the basis elements $v_b$ for a chosen set of generators. [/definition] The definition packages the kind of information we seek: not merely a list of irreducibles, but a usable basis and an action. The first example shows this in the most familiar setting, where the indexing set is a finite set and the local rules are literal permutations of basis vectors. [example: Permutation Representation As A First Model] Let $V=\mathbb{C}\{1,\dots,n\}$ have basis $v_1,\dots,v_n$, and define the action of $\sigma\in S_n$ on basis vectors by $\sigma\cdot v_j=v_{\sigma(j)}$, extended linearly to all of $V$. This gives a representation because the identity permutation satisfies \begin{align*} \operatorname{id}\cdot v_j=v_{\operatorname{id}(j)}=v_j, \end{align*} and for $\sigma,\tau\in S_n$, \begin{align*} \sigma\cdot(\tau\cdot v_j)=\sigma\cdot v_{\tau(j)}=v_{\sigma(\tau(j))}=v_{(\sigma\tau)(j)}=(\sigma\tau)\cdot v_j. \end{align*} The indexing set is $B=\{1,\dots,n\}$, with basis vector $v_j$ attached to $j\in B$. For the adjacent transposition $s_i=(i,i+1)$, the rule is explicit: \begin{align*} s_i\cdot v_i=v_{i+1}, \end{align*} \begin{align*} s_i\cdot v_{i+1}=v_i, \end{align*} and if $j\neq i,i+1$, then \begin{align*} s_i\cdot v_j=v_j. \end{align*} Thus each generator acts by a local rule on the labelled basis: it swaps the two neighbouring labels $i$ and $i+1$ and leaves every other label fixed. This is the simplest form of a combinatorial representation model, where the action is read directly from a finite labelled set. [/example] Permutation representations are too simple to capture the full representation theory of $S_n$. This motivates the search for equally explicit models for irreducible representations and for operations such as induction, restriction, [tensor product](/page/Tensor%20Product), and deformation. ## The Symmetric Group Dictionary How do partitions, tableaux, and symmetric functions know about $S_n$-representations? The answer begins with the classification of irreducible complex representations of $S_n$, but the course is interested in the concrete models that make the classification computable. The first objects in the dictionary are partitions. We need them because they are the common labels for diagrams, Schur functions, conjugacy classes by cycle type, and irreducible representations. [definition: Partition] A partition of $n \in \mathbb{N}$ is a sequence $\lambda = (\lambda_1,\dots,\lambda_r)$ of positive integers such that $\lambda_1 \ge \cdots \ge \lambda_r$ and $\lambda_1 + \cdots + \lambda_r = n$. [/definition] A partition is a numerical object, but tableau combinatorics needs a shape whose boxes can be filled. This motivates turning the sequence $\lambda$ into a Young diagram. [definition: Young Diagram] The Young diagram of a partition $\lambda = (\lambda_1,\dots,\lambda_r)$ is the array of boxes with $\lambda_i$ boxes in row $i$, for $1 \le i \le r$, with rows left-justified. [/definition] The diagram turns a partition into a shape on which tableaux can live. Once boxes have positions, we can impose row and column conditions and use the resulting fillings as basis labels. [example: Standardness Cuts Down Fillings] For $\lambda=(3,2,1)$, the Young diagram has row lengths $3$, $2$, and $1$. Fill the first row with $1,2,4$, the second row with $3,5$, and the third row with $6$, all left-justified. The row inequalities are $1<2<4$ in the first row and $3<5$ in the second row. The column inequalities are $1<3<6$ in the first column and $2<5$ in the second column. Since the entries are exactly $1,2,3,4,5,6$ and each row and column increases, this filling is a standard Young tableau. Now keep the same shape and entries but put $1,6,3$ down the first column. The first column would have to increase from top to bottom, so it would need $1<6<3$. The inequality $6<3$ is false, equivalently $6>3$, so the filling is not standard even though it uses the correct shape and the correct set of entries. Thus the Young diagram supplies only the ambient shape; the row and column order conditions are the constraints that select the fillings usable as tableau basis labels. [/example] This example shows how a partition becomes a shape for basis labels, and it motivates the following theorem because we need to know that these partition labels cover all irreducible $S_n$-representations. Without this classification statement, tableaux would give examples of modules but not a full organising system for the representation theory of $S_n$. [quotetheorem:8427] In this course, the theorem is not treated as an isolated classification statement. The hypothesis that we work over $\mathbb{C}$ is essential for this clean form: characteristic-zero finite-group representation theory is semisimple, so irreducible characters and direct-sum decompositions behave as expected. In characteristic $2$, for instance, the sign representation of $S_3$ coincides with the identity representation because $-1=1$, so the partitions $(3)$ and $(1,1,1)$ no longer label distinct irreducibles. The theorem itself supplies labels, but it does not construct the modules, choose bases, or describe the matrices of permutations. Specht modules later fill that gap by building representatives from Young symmetrisers and then replacing the abstract label $\lambda$ by a tableau basis with explicit local rules. [example: Partitions Of Four And Dimension Checks] The partitions of $4$ are $(4)$, $(3,1)$, $(2,2)$, $(2,1,1)$, and $(1,1,1,1)$, so the classification theorem stated above predicts five irreducible complex representations of $S_4$, one for each shape. Using the *hook-length formula*, the dimension attached to a shape $\lambda$ is \begin{align*} f^\lambda=\frac{4!}{\prod_{b\in \lambda} h(b)}. \end{align*} For the five shapes, the hook-length products are \begin{align*} (4):\quad 4\cdot 3\cdot 2\cdot 1=24, \end{align*} \begin{align*} (3,1):\quad 4\cdot 2\cdot 1\cdot 1=8, \end{align*} \begin{align*} (2,2):\quad 3\cdot 2\cdot 2\cdot 1=12, \end{align*} \begin{align*} (2,1,1):\quad 4\cdot 1\cdot 2\cdot 1=8, \end{align*} \begin{align*} (1,1,1,1):\quad 4\cdot 3\cdot 2\cdot 1=24. \end{align*} Since $4!=24$, the corresponding dimensions are \begin{align*} \frac{24}{24}=1,\qquad \frac{24}{8}=3,\qquad \frac{24}{12}=2,\qquad \frac{24}{8}=3,\qquad \frac{24}{24}=1. \end{align*} These dimensions satisfy the finite-group dimension test for the regular representation: \begin{align*} 1^2+3^2+2^2+3^2+1^2=1+9+4+9+1=24=4!=|S_4|. \end{align*} Thus the five tableau counts are not just labels: their squared dimensions account exactly for the dimension of the regular representation of $S_4$. [/example] The example labels representations by partitions and verifies the dimension count, but it still leaves the character table as a list of values indexed by conjugacy classes. That format is poorly suited to the later operations of the course: induction, restriction, and decomposition need a language where multiplicities can be read from expansions. The Frobenius characteristic is introduced precisely to turn class functions of symmetric groups into symmetric functions, so that Schur expansions display irreducible multiplicities in the same tableau language that already indexed the modules. [definition: Frobenius Characteristic] Let $\operatorname{Class}(S_n)$ be the complex vector space of class functions on $S_n$, and let $\Lambda^n$ be the degree-$n$ homogeneous component of the ring of symmetric functions over $\mathbb{C}$. The Frobenius characteristic is the linear map $\operatorname{ch}: \operatorname{Class}(S_n) \to \Lambda^n$ defined by \begin{align*} \operatorname{ch}(\chi)=\frac{1}{n!}\sum_{\sigma \in S_n} \chi(\sigma) p_{\lambda(\sigma)}, \end{align*} where $\lambda(\sigma)$ is the cycle-type partition of $\sigma$ and $p_{\lambda}$ is the corresponding power-sum symmetric function. [/definition] This construction explains why Schur functions appear throughout the course, but the definition alone does not say which symmetric functions correspond to irreducible representations. Without that calibration, a Schur expansion would be only a formal expansion in a convenient basis, not representation-theoretic data. The next problem is therefore to identify the image of the irreducible character basis under the Frobenius characteristic. Since irreducible characters are the coordinates used to decompose representations, the useful normalization is the one that sends each irreducible character to the symmetric function basis already indexed by the same partition. The formal result below supplies exactly that calibration. [quotetheorem:8428] The course uses this theorem as a computational bridge. It is a degree-by-degree statement: class functions on $S_n$ land in the homogeneous component $\Lambda^n$, so representations of different symmetric groups must first be organised by size before their Frobenius characteristics can be compared. For example, the identity characters of $S_2$ and $S_3$ map to symmetric functions of degrees $2$ and $3$ respectively; treating their images as if they belonged to one fixed degree would lose the group size encoded by cycle type. The theorem also depends on complex character theory, since the input is a complex class function and the irreducible characters form the relevant [orthonormal basis](/page/Orthonormal%20Basis). The theorem translates decomposition into Schur expansion, but it does not construct the underlying modules or their bases; that construction enters through Specht modules and tableau combinatorics. ## Words, Insertion, and Tableaux Why should an algorithm on words reveal representation theory? The answer is that words carry both order information and multiplicity information, while tableaux impose a controlled normal form on that data. Insertion algorithms make this normal form canonical. Before defining tableaux, we need the raw input on which insertion algorithms operate. That input is a word: an ordered finite string of letters. [definition: Word] A word over an ordered alphabet $A$ is a finite sequence $w = w_1\cdots w_m$ with each $w_i \in A$. [/definition] Words are the raw combinatorial input for the first part of the course. To make words interact with symmetric functions, we need tableaux that allow repeated entries and record weights. [definition: Semistandard Young Tableau] A semistandard Young tableau of shape $\lambda$ with entries in $\mathbb{N}$ is a filling of the Young diagram of $\lambda$ by positive integers whose entries weakly increase along each row from left to right and strictly increase down each column. [/definition] Semistandard tableaux are the combinatorial objects counted by Schur functions. To connect directly with permutations and $S_n$-modules, we also need tableaux whose entries are exactly $1,\dots,n$. [definition: Standard Young Tableau] A standard Young tableau of size $n$ is a filling of a Young diagram with the entries $1,\dots,n$, each used exactly once, such that entries increase along each row from left to right and down each column. [/definition] The distinction between semistandard and standard tableaux will matter throughout. Semistandard tableaux are adapted to weights and symmetric functions, while standard tableaux are adapted to permutations and symmetric group modules. [example: A Standard Tableau And Its Reading Word] For the shape $(2,1)$, put $1$ and $2$ in the first row, with $3$ in the single box of the second row below $1$. The row condition holds because the only nontrivial row comparison is $1<2$. The column condition holds because the first column has entries $1$ above $3$, and $1<3$. The entries used are exactly $1,2,3$, each appearing once, so the filling is a standard Young tableau. With the row-reading convention "left to right along each row, from top row to bottom row," the first row contributes $1,2$ and the second row contributes $3$, so the row-reading word is $123$. With the column-reading convention "bottom to top within each column, from left column to right column," the first column contributes $3,1$ and the second column contributes $2$, so the word is $312$. With the convention "top to bottom within each column, from left column to right column," the first column contributes $1,3$ and the second column contributes $2$, so the word is $132$. Thus the same tableau can produce different words, and the reading convention must be fixed before using reading words in algebraic constructions. [/example] The first algorithmic landmark is Schensted insertion. Row insertion takes a new letter, places it into the first row in the position forced by the row order, and bumps the displaced entry into the next row; the process repeats until a new box is created. The following theorem records the fundamental correctness property needed before insertion can be used as a representation-theoretic normal form. [quotetheorem:8429] [citeproof:8429] The hypotheses are doing real work. The total order is needed so that the phrase "leftmost larger entry" is meaningful, and pairwise distinctness is what makes the final filling standard rather than semistandard. If repeated letters are allowed, the same row-insertion procedure can still produce a tableau-like object, but the conclusion must be changed because the entries cannot be exactly $1,\dots,m$ each used once. The theorem also does not yet describe the shape of the output or how much information about the original word is retained; those questions lead to longest increasing subsequences and to the full RSK correspondence, where a permutation is packaged into two tableaux of the same shape. ## Modules, Bases, and Local Rules How can a tableau basis carry an action of $S_n$? Since $S_n$ is generated by adjacent transpositions, it is enough to describe how each $s_i = (i,i+1)$ acts. The art is to choose a basis where those actions are controlled by the relative positions of $i$ and $i+1$ in a tableau. The next definition names the central module attached to a Young diagram. We introduce it here because it is the representation-theoretic object for which standard tableaux will become basis labels. [definition: Specht Module] For a partition $\lambda$ of $n$ and a fixed standard tableau $t$ of shape $\lambda$, let $R_t$ be the subgroup of $S_n$ preserving the rows of $t$ and let $C_t$ be the subgroup preserving the columns of $t$. The Young symmetrizer attached to $t$ is \begin{align*} e_t = \left(\sum_{\rho \in R_t}\rho\right)\left(\sum_{\kappa \in C_t}\operatorname{sgn}(\kappa)\kappa\right) \in \mathbb{C}S_n. \end{align*} The Specht module of shape $\lambda$ is the left $\mathbb{C}S_n$-module $S^\lambda = \mathbb{C}S_n e_t$. [/definition] Throughout this discussion, the row symmetrizer is written on the left and the column antisymmetrizer on the right. With the right-to-left composition convention used below, the column antisymmetrizer acts first. This fixes the order of multiplication for the examples below. Different choices of the standard tableau $t$ of the same shape give isomorphic Specht modules, so the notation records only the partition $\lambda$. Row symmetrisation and column antisymmetrisation are the two visible constraints: entries in a row are treated symmetrically, while entries in a column are treated with sign. To state the classification in its standard language, recall that a $\lambda$-tabloid is a tableau of shape $\lambda$ with the order within each row forgotten. The permutation module $M^\lambda$ is the complex vector space spanned by all $\lambda$-tabloids, with $S_n$ acting by permuting the entries. A polytabloid is the signed column alternation attached to a tableau inside this permutation module; the Specht module can equivalently be realised as the span of these polytabloids. With this notation in place, the classification theorem says that these tableau-built modules account for all irreducible complex representations of $S_n$. [quotetheorem:8430] [citeproof:8430] Specht modules give the first major instance of the course philosophy: a representation is understood through a basis indexed by tableaux. The field hypothesis matters here: over $\mathbb{C}$, [Maschke's theorem](/theorems/2409) makes finite-group representations semisimple, so irreducibles and characters give a complete decomposition theory. In positive characteristic, Specht modules still exist but need not be irreducible, and decomposing them leads to modular representation theory rather than the clean classification stated above. The theorem also identifies modules only up to isomorphism; the actual matrices for adjacent transpositions depend on the chosen tableau basis and conventions. The simplest Specht modules come from the two extreme Young diagrams, where the imposed symmetry is most visible. [example: The Two Extreme Specht Modules] For the row shape $(n)$, take the standard tableau $t$ with entries $1,2,\dots,n$ in its single row. Then every permutation preserves the unique row, so $R_t=S_n$, while only the identity preserves each one-box column, so $C_t=\{\operatorname{id}\}$. Hence the Young symmetrizer is \begin{align*} e_t=\sum_{\rho\in S_n}\rho. \end{align*} For any $\sigma\in S_n$, \begin{align*} \sigma e_t=\sum_{\rho\in S_n}\sigma\rho=\sum_{\pi\in S_n}\pi=e_t, \end{align*} where $\pi=\sigma\rho$ runs through all of $S_n$ as $\rho$ runs through all of $S_n$. If $a=\sum_{\sigma\in S_n}c_\sigma\sigma\in \mathbb{C}S_n$, then \begin{align*} a e_t=\sum_{\sigma\in S_n}c_\sigma\sigma e_t=\sum_{\sigma\in S_n}c_\sigma e_t=\left(\sum_{\sigma\in S_n}c_\sigma\right)e_t. \end{align*} Thus $\mathbb{C}S_n e_t=\mathbb{C}e_t$ is one-dimensional, and every $\sigma\in S_n$ acts by $\sigma e_t=e_t$, so this is the identity representation. For the column shape $(1,1,\dots,1)$, take the standard tableau $t$ with entries $1,2,\dots,n$ down the single column. Then $R_t=\{\operatorname{id}\}$ and $C_t=S_n$, so \begin{align*} e_t=\sum_{\kappa\in S_n}\operatorname{sgn}(\kappa)\kappa. \end{align*} For $\sigma\in S_n$, \begin{align*} \sigma e_t=\sum_{\kappa\in S_n}\operatorname{sgn}(\kappa)\sigma\kappa. \end{align*} Put $\pi=\sigma\kappa$, so $\kappa=\sigma^{-1}\pi$. Since $\operatorname{sgn}(\sigma^{-1})=\operatorname{sgn}(\sigma)$ and the sign is multiplicative, \begin{align*} \operatorname{sgn}(\kappa)=\operatorname{sgn}(\sigma^{-1}\pi)=\operatorname{sgn}(\sigma)\operatorname{sgn}(\pi). \end{align*} Therefore \begin{align*} \sigma e_t=\operatorname{sgn}(\sigma)\sum_{\pi\in S_n}\operatorname{sgn}(\pi)\pi=\operatorname{sgn}(\sigma)e_t. \end{align*} Again $\mathbb{C}S_n e_t=\mathbb{C}e_t$ is one-dimensional, and the action is exactly multiplication by $\operatorname{sgn}(\sigma)$. The single row imposes total symmetry, while the single column imposes total antisymmetry. [/example] ## Deformations and Canonical Structures Why does the same tableau combinatorics survive after replacing $S_n$ by a deformation? The later part of the course studies Hecke algebras and Kazhdan-Lusztig theory, where the group algebra is deformed but much of the cell and basis structure remains visible. To formulate the deformation, we replace adjacent transpositions by generators satisfying the same braid relations but a deformed quadratic relation. This gives the type $A$ Iwahori-Hecke algebra. [definition: Iwahori-Hecke Algebra Of Type A] The Iwahori-Hecke algebra $\mathcal{H}_n(q)$ of type $A_{n-1}$ over $\mathbb{C}(q)$ is the associative algebra generated by $T_1,\dots,T_{n-1}$ subject to the braid relations \begin{align*} T_iT_{i+1}T_i &= T_{i+1}T_iT_{i+1}, & T_iT_j &= T_jT_i \quad \text{if } |i-j|>1, \end{align*} and the quadratic relations \begin{align*} (T_i-q)(T_i+1)=0. \end{align*} [/definition] When $q=1$, the generators satisfy $T_i^2=1$, matching the adjacent transpositions in $S_n$. Thus the Hecke algebra is a deformation of the group algebra, and the course asks which combinatorial features persist under this deformation. [example: The Specialisation At q Equals One] Set $q=1$ in the quadratic relation for $\mathcal{H}_n(q)$. For each generator $T_i$ we get \begin{align*}(T_i-1)(T_i+1)=0.\end{align*} Expanding the left-hand side inside the associative algebra gives \begin{align*}(T_i-1)(T_i+1)=T_i^2+T_i-T_i-1=T_i^2-1.\end{align*} Therefore \begin{align*}T_i^2-1=0,\end{align*} so \begin{align*}T_i^2=1.\end{align*} The braid relations are unchanged under the substitution $q=1$: \begin{align*}T_iT_{i+1}T_i=T_{i+1}T_iT_{i+1}\end{align*} and, when $|i-j|>1$, \begin{align*}T_iT_j=T_jT_i.\end{align*} Thus, after specialisation at $q=1$, the generators $T_i$ satisfy the same quadratic and braid relations as the adjacent transpositions $s_i=(i,i+1)$ in $S_n$: namely $s_i^2=1$, $s_is_{i+1}s_i=s_{i+1}s_is_{i+1}$, and $s_is_j=s_js_i$ for $|i-j|>1$. Sending $T_i$ to $s_i$ therefore identifies the specialised Hecke algebra with the group algebra $\mathbb{C}S_n$. The parameter $q$ deforms only the quadratic relation, and at $q=1$ that deformation returns to the ordinary symmetric-group relation. [/example] The Hecke algebra example shows how deformation preserves generator relations at a special value, but later representation theory also needs a local combinatorial language for bases. This motivates the definition of crystal graphs, where basis elements are vertices and generator-like operations become coloured edges. [definition: Crystal Graph] For this course, a crystal graph is a coloured directed graph that records the raising and lowering moves of a highest-weight representation after the coefficients have been forgotten. It consists of a vertex set $B$, a finite colour set $I$, and partially defined maps \begin{align*} e_i, f_i : B \longrightarrow B \cup \{0\}, \qquad i \in I, \end{align*} together with a weight label $\operatorname{wt}(b)$ on each vertex and string-length functions $\varepsilon_i,\varphi_i$. The number $\varepsilon_i(b)$ counts how far $b$ can move by repeated $e_i$-steps, while $\varphi_i(b)$ counts how far it can move by repeated $f_i$-steps. Its directed edges are $b \xrightarrow{i} b'$ exactly when $f_i(b)=b'$. [/definition] Equivalently, the same directed edge records $e_i(b')=b$. The functions $\varepsilon_i$ and $\varphi_i$ measure how far a vertex can move along the $i$-string in the lowering and raising directions, so the graph is not merely a picture of arrows but a compressed record of the crystal axioms. Crystals give another kind of local combinatorial model. Instead of writing matrices for generators, we draw coloured arrows that record how basis elements move under raising and lowering operators. [example: Crystal Operators On Words] Throughout the course we use the Kashiwara word convention in which the $i$-signature is reduced by cancelling adjacent $-+$ pairs. Thus, for the word $112$, the reduced $1$-signature selects the letter prescribed by this $-+$ convention; any alternative convention that cancels $+-$ pairs is the opposite tensor-order convention and must be translated before comparing examples. Take words of length $3$ in the alphabet $\{1,2\}$. Use the following $1$-signature rule: mark each $1$ by $+$ and each $2$ by $-$, then cancel each adjacent $+-$ pair until no such pair remains. The operator $f_1$ changes the rightmost uncancelled $1$ into a $2$, and sends the word to $0$ if there is no uncancelled $1$. The operator $e_1$ changes the leftmost uncancelled $2$ into a $1$, and sends the word to $0$ if there is no uncancelled $2$. For example, the word $112$ has signature $++-$. Cancelling the second $+$ with the $-$ leaves the first $+$ uncancelled, so $f_1$ changes the first letter: \begin{align*} f_1(112)=212. \end{align*} For $212$, the signature is $-+-$. Cancelling the adjacent $+-$ in the last two positions leaves the first $-$ uncancelled, so \begin{align*} e_1(212)=112. \end{align*} Thus these two words are connected by a coloured crystal edge: \begin{align*} 112 \xrightarrow{1} 212. \end{align*} Starting from $111$, no cancellation occurs, and the rightmost uncancelled $1$ is the third letter, so \begin{align*} f_1(111)=112. \end{align*} Combining this with the computation above gives one component \begin{align*} 111 \xrightarrow{1} 112 \xrightarrow{1} 212. \end{align*} The vertex $111$ is highest-weight because there is no uncancelled $2$, hence $e_1(111)=0$. This small graph shows the guiding idea: the representation-theoretic structure is encoded by local moves on words, and decomposition is reflected by connected components with distinguished highest-weight vertices. [/example] ## How To Read The Course What should the reader track from chapter to chapter? The course repeatedly asks the same four questions in new settings: what are the basis objects, what are the local rules, what character or symmetric function records the module, and what structural theorem explains the resulting decomposition? [explanation: The Four Recurring Questions] For tableaux and insertion, the basis objects are words and tableaux, the local rules are insertion and Knuth moves, and the structural theorems are Schensted, Knuth, Greene, and RSK. For Specht modules, the basis objects are standard tableaux, the local rules come from adjacent transpositions and Young symmetrisers, and the structural theorem is the classification of irreducible $S_n$-modules. For crystals, the basis objects are vertices of a coloured graph, the local rules are crystal operators, and the structural results describe highest-weight components. For Hecke algebras and Kazhdan-Lusztig theory, the basis objects are algebra basis elements and cells, the local rules come from generators and canonical bases, and the structural results explain how deformed representation theory still remembers tableaux. [/explanation] The prerequisites are used in specific ways. Linear algebra supplies modules, bases, and decompositions; finite group representation theory supplies characters and irreducibility; symmetric functions supply Schur functions and the Frobenius characteristic; posets and Mobius inversion supply incidence-style reasoning that appears around cells and order structures. These topics also connect outward to geometry and physics: Schur functions occur in Schubert calculus, crystals model canonical bases and solvable lattice models, and Hecke algebras connect finite group combinatorics with braid groups and geometry of flag varieties. [remark: Characteristic Zero] Throughout these notes, representations of finite groups are taken over $\mathbb{C}$ unless another field is specified. This keeps the representation theory semisimple and allows characters to detect representations. [/remark] The next chapter begins with tableaux, words, and insertion. That choice reflects the course's method: before constructing the modules, we learn the combinatorial language that will later serve as their coordinate system. The introductory link between characters and representations has done its job: it tells us why we need a combinatorial model, but not yet how to build one. The next chapter supplies that model by introducing tableaux, words, insertion, and plactic equivalence as the language in which the rest of the course will be written. # 1. Tableaux, Words, and Insertion Building on the introductory dictionary between tableaux and representations, this chapter sets up the combinatorial language used throughout the course: Young tableaux, words, insertion, and the plactic [equivalence relation](/page/Equivalence%20Relation). The guiding question is how a finite word remembers the same representation-theoretic data as a tableau. Schensted insertion gives the first answer: it turns words into tableaux while preserving the increasing-subsequence information that later becomes the shape data in RSK, Specht modules, and crystals. ## Tableaux as Structured Words How can a filling of a Young diagram encode a word without losing the order constraints that make tableaux useful in representation theory? We begin by fixing the class of tableaux and the reading conventions that will be used by insertion algorithms. A partition gives the shape on which the entries sit. Before imposing any inequalities, we need a coordinate convention for the boxes so that phrases such as "same row" and "same column" have a fixed meaning. [definition: Young Diagram] Let $\lambda = (\lambda_1, \dots, \lambda_r)$ be a partition with $\lambda_1 \ge \cdots \ge \lambda_r > 0$. The Young diagram of shape $\lambda$ is the set of boxes $[\lambda] = \{(i,j) : 1 \le i \le r, 1 \le j \le \lambda_i\}$. Rows are indexed from top to bottom and columns from left to right. [/definition] The diagram records only the positions of boxes, not the data placed inside them. To connect diagrams with words, we now allow entries from an ordered alphabet and impose the monotonicity conditions that make row and column reading compatible with insertion. [definition: Semistandard Young Tableau] Let $A$ be a totally ordered alphabet. A semistandard Young tableau of shape $\lambda$ with entries in $A$ is a map $T:[\lambda] \to A$ such that entries weakly increase along rows and strictly increase down columns. Thus $T(i,j) \le T(i,j+1)$ and $T(i,j) < T(i+1,j)$ whenever both boxes involved belong to $[\lambda]$. [/definition] Semistandard tableaux are the right objects for Schur functions and crystals because multiplicities of letters matter. When the alphabet is finite and each symbol is used once, the same inequalities become the standard tableaux that will record insertion histories in the next chapter. [definition: Standard Young Tableau] A standard Young tableau of size $n$ is a semistandard Young tableau whose entries are exactly $1,2,\dots,n$, each appearing once. [/definition] Standard tableaux separate the shape from the order in which labels appear, while semistandard tableaux also remember content. A quick comparison of the two notions makes the row and column inequalities concrete before we turn tableaux back into words. [example: Semistandard And Standard Shapes] For the first filling, the shape is $(3,2,1)$ because the row lengths are $3$, $2$, and $1$. Its rows are \begin{align*} (1,1,3),\quad (2,3),\quad (4), \end{align*} and they are weakly increasing since $1\le 1\le 3$, $2\le 3$, and the one-entry row $(4)$ has no row comparison to check. The columns are \begin{align*} (1,2,4),\quad (1,3),\quad (3), \end{align*} and they are strictly increasing since $1<2<4$, $1<3$, and the one-entry column $(3)$ has no column comparison to check. Hence this filling is semistandard. For the second filling, the row lengths are again $3$, $2$, and $1$, so the shape is also $(3,2,1)$. Its entries are exactly $1,2,3,4,5,6$, each appearing once. The rows satisfy $1<3<6$ and $2<5$, so they are weakly increasing, and the columns are $(1,2,4)$, $(3,5)$, and $(6)$, with $1<2<4$ and $3<5$. Therefore this filling is a standard Young tableau of the same shape. [/example] The example shows that a tableau is more structured than a word, but insertion algorithms still take words as input. To compare a tableau with the word that might have produced it, the two-dimensional filling must be flattened in a way that respects the bottom-to-top order used by the plactic convention. The row word records this chosen flattening rather than treating all possible readings as interchangeable. [definition: Row Word] Let $A$ be a totally ordered alphabet and let $\operatorname{SSYT}(A)$ be the set of semistandard Young tableaux with entries in $A$. The row word map is the function $\operatorname{row}:\operatorname{SSYT}(A) \to A^*$ such that $\operatorname{row}(T)$ is obtained by reading each row of $T$ from left to right, starting with the bottom row and moving upward. [/definition] The row word gives one linear form of a tableau, but it does not directly expose the vertical strictness built into a semistandard filling. For the insertion theory, we also need a reading that foregrounds columns, because column comparisons control bumping behavior and give another word-level representative of the same tableau data. The column word is the flattening designed to record that vertical structure in a single word. [definition: Column Word] Let $A$ be a totally ordered alphabet and let $\operatorname{SSYT}(A)$ be the set of semistandard Young tableaux with entries in $A$. The column word map is the function $\operatorname{col}:\operatorname{SSYT}(A) \to A^*$ such that $\operatorname{col}(T)$ is obtained by reading each column of $T$ from bottom to top, starting with the leftmost column and moving rightward. [/definition] The two reading words of a tableau are usually not equal, so literal equality of words is too rigid. We need local transformations that preserve tableau data while allowing different readings of the same filling; these are the Knuth relations. [definition: Knuth Equivalence] Let $A$ be a totally ordered alphabet. Knuth equivalence is the equivalence relation $\equiv_K$ on words in $A$ generated by the relations $xzy \equiv_K zxy$ for $x \le y < z$ and $yxz \equiv_K yzx$ for $x < y \le z$, where $x,y,z \in A$ and the displayed triples may occur inside a longer word. [/definition] The inequalities in the two moves are asymmetric because rows allow equality but columns do not. At this point there are two different words attached to the same tableau, and it is not automatic that the local Knuth moves can pass between them. The next structural issue is whether the plactic quotient is independent of the chosen reading convention for a tableau. The needed consistency theorem says that the row and column readings of the same semistandard tableau determine the same Knuth class, so the quotient is remembering tableau data rather than an accidental choice of reading order. [quotetheorem:8431] [citeproof:8431] The theorem tells us that a tableau determines not just one word but a full equivalence class of words. The semistandard hypotheses are essential: the local Knuth moves use weak increase along rows and strict increase down columns, so an arbitrary filling need not have row and column readings in the same Knuth class. A concrete failure appears in shape $(2,2)$ with rows $(2,4)$ and $(3,1)$: the row word is $3124$ and the column word is $3214$, and the local comparisons around the lower-right box include $4>1$ rather than the inequality required for a Knuth move. The insertion test introduced below separates these two words, so this is not merely a failure of the proof strategy. The theorem also has a limitation: it shows that two particular readings of the same tableau agree in the plactic quotient, but it does not yet classify all words with that tableau. The next section proves that converse direction by constructing a tableau from a word and showing that the construction depends only on its Knuth class. ## Schensted Row Insertion and the Plactic Monoid Given a word $w = a_1\cdots a_n$, can we build a tableau letter by letter so that local Knuth moves do not change the final result? Row insertion answers this by inserting one letter into the first row, bumping larger letters down until the shape grows by one box. The algorithm starts with insertion into a single row. A naive append fails as soon as the row $(1,4)$ receives $2$, since $(1,4,2)$ is no longer weakly increasing. Sorting the row to $(1,2,4)$ also loses the information needed by the lower rows: the displaced $4$ is the entry that must continue downward so that column strictness can be restored. Choosing the leftmost entry strictly greater than the inserted letter is the local rule that preserves the row and sends the smallest possible displaced letter to the next row. [definition: Row Insertion Step] Let $A$ be a totally ordered alphabet. The row insertion step is the operation \begin{align*} \operatorname{ins}_{\mathrm{row}} : \{\text{weakly increasing rows in } A\} \times A \to \{\text{weakly increasing rows in } A\} \times (A \cup \{\varnothing\}) \end{align*} defined as follows. For a weakly increasing row $R=(r_1,\dots,r_m)$ and a letter $a \in A$, if no entry of $R$ is strictly greater than $a$, then $\operatorname{ins}_{\mathrm{row}}(R,a)=((r_1,\dots,r_m,a),\varnothing)$. Otherwise, for the leftmost index $j$ with $r_j>a$, \begin{align*} \operatorname{ins}_{\mathrm{row}}(R,a)=((r_1,\dots,r_{j-1},a,r_{j+1},\dots,r_m),r_j). \end{align*} [/definition] The leftmost replacement rule preserves weak increase in the row where the insertion occurs. To insert into a whole tableau, the bumped letter must then be treated as a new letter for the next row, so the local step is iterated down the diagram. [definition: Schensted Row Insertion] Let $A$ be a totally ordered alphabet and let $\operatorname{SSYT}(A)$ be the set of semistandard Young tableaux with entries in $A$. Schensted row insertion is the operation \begin{align*} \leftarrow : \operatorname{SSYT}(A) \times A \to \operatorname{SSYT}(A), \qquad (T,a) \mapsto T \leftarrow a. \end{align*} The tableau $T \leftarrow a$ is obtained by inserting $a$ into the first row using the row insertion step; whenever a letter is bumped, insert it into the next row by the same rule. If a bumped letter reaches a row where it is not replacing any entry, append it there, creating one new box. [/definition] A single insertion grows the tableau by one box and preserves the semistandard conditions. Since a word is a sequence of letters, we now iterate the insertion operation from left to right to define the tableau attached to the word. [definition: Insertion Tableau Of A Word] Let $A$ be a totally ordered alphabet and let $\operatorname{SSYT}(A)$ be the set of semistandard Young tableaux with entries in $A$. The insertion tableau map is the function $P:A^* \to \operatorname{SSYT}(A)$ defined recursively by $P(\varnothing)=\varnothing$ and $P(a_1\cdots a_i)=P(a_1\cdots a_{i-1}) \leftarrow a_i$ for every word $a_1\cdots a_i \in A^*$. [/definition] The construction is easiest to trust after seeing the bumping paths. The first required computation has repeated entries, so the output is semistandard rather than standard. [example: Insertion Tableau For 314253] Insert the letters of $314253$ from left to right, starting with the empty tableau $T_0=\varnothing$. Inserting $3$ into the empty first row appends it, so \begin{align*} T_1=(3). \end{align*} To insert $1$ into the first row $(3)$, the leftmost entry strictly greater than $1$ is $3$. Replace $3$ by $1$ and bump $3$ to the next row, where it appends: \begin{align*} T_2=(1)/(3). \end{align*} To insert $4$ into the first row $(1)$, no entry is strictly greater than $4$, so $4$ appends: \begin{align*} T_3=(1,4)/(3). \end{align*} To insert $2$ into the first row $(1,4)$, the leftmost entry strictly greater than $2$ is $4$. Replace $4$ by $2$, then insert the bumped $4$ into the second row $(3)$; since $3$ is not greater than $4$, the $4$ appends: \begin{align*} T_4=(1,2)/(3,4). \end{align*} To insert $5$ into the first row $(1,2)$, no entry is strictly greater than $5$, so $5$ appends: \begin{align*} T_5=(1,2,5)/(3,4). \end{align*} Finally, to insert $3$ into the first row $(1,2,5)$, the leftmost entry strictly greater than $3$ is $5$. Replace $5$ by $3$, then insert the bumped $5$ into the second row $(3,4)$; since neither $3$ nor $4$ is greater than $5$, the $5$ appends: \begin{align*} T_6=(1,2,3)/(3,4,5). \end{align*} Thus $P(314253)=T_6$ has shape $(3,3)$, with rows $(1,2,3)$ and $(3,4,5)$. Its columns are $(1,3)$, $(2,4)$, and $(3,5)$, and these are strictly increasing because $1<3$, $2<4$, and $3<5$, so the repeated letter $3$ is compatible with semistandardness because the two copies lie in different columns. [/example] The next computation is a permutation, so the final tableau is standard. It also illustrates that the shape is sensitive to the pattern of increasing subsequences rather than only to the multiset of letters. [example: Insertion Tableau For 241635] Insert the letters of $241635$ from left to right, starting with $T_0=\varnothing$. Inserting $2$ into the empty first row appends it, so \begin{align*} T_1=(2). \end{align*} To insert $4$ into the first row $(2)$, no entry is strictly greater than $4$, so $4$ appends: \begin{align*} T_2=(2,4). \end{align*} To insert $1$ into the first row $(2,4)$, the leftmost entry strictly greater than $1$ is $2$. Replace $2$ by $1$, and insert the bumped $2$ into the empty second row, where it appends: \begin{align*} T_3=(1,4)/(2). \end{align*} To insert $6$ into the first row $(1,4)$, neither $1$ nor $4$ is strictly greater than $6$, so $6$ appends: \begin{align*} T_4=(1,4,6)/(2). \end{align*} To insert $3$ into the first row $(1,4,6)$, the entry $1$ is not greater than $3$, while $4>3$, so the leftmost entry strictly greater than $3$ is $4$. Replace $4$ by $3$, and insert the bumped $4$ into the second row $(2)$; since $2$ is not greater than $4$, the $4$ appends: \begin{align*} T_5=(1,3,6)/(2,4). \end{align*} Finally insert $5$ into the first row $(1,3,6)$. The entries $1$ and $3$ are not greater than $5$, while $6>5$, so replace $6$ by $5$. Insert the bumped $6$ into the second row $(2,4)$; since neither $2$ nor $4$ is greater than $6$, the $6$ appends: \begin{align*} T_6=(1,3,5)/(2,4,6). \end{align*} Therefore $P(241635)=T_6$ has shape $(3,3)$. Its rows satisfy $1<3<5$ and $2<4<6$, and its columns are $(1,2)$, $(3,4)$, and $(5,6)$, with $1<2$, $3<4$, and $5<6$. The entries are exactly $1,2,3,4,5,6$, each used once, so the final tableau is standard. [/example] The two insertion examples show that different words can lead to structured tableaux through the same bumping mechanism. This raises the classification question for insertion: exactly which words have the same insertion tableau? The answer is the following theorem, which identifies equality of insertion tableaux with Knuth equivalence. [quotetheorem:8432] [citeproof:8432] The [Knuth equivalence theorem](/theorems/8432) converts the insertion algorithm into an algebraic presentation, but its hypotheses specify exactly which presentation is being used. The total order on the alphabet and the weak-row, strict-column insertion convention are necessary because the two Knuth relations encode those inequalities; changing to a column-insertion convention changes which weak and strict subsequence statistics appear later. The theorem does not say that two words with the same content are equivalent: for example, $12$ and $21$ use the same letters but have insertion tableaux of shapes $(2)$ and $(1,1)$. Its forward use is therefore precise: it identifies each plactic class, not each multiset of letters, with one semistandard tableau. Since words form a free monoid under concatenation, quotienting by exactly these insertion-invisible relations produces the monoid whose elements are tableaux; this motivates the plactic monoid. [definition: Plactic Monoid] Let $A$ be a totally ordered alphabet. The plactic monoid $\operatorname{Pl}(A)$ is the quotient of the free monoid $A^*$ by Knuth equivalence: $\operatorname{Pl}(A)=A^*/{\equiv_K}$. Multiplication is induced by concatenation of words. [/definition] The theorem identifies plactic classes with semistandard tableaux. Concatenation of words therefore becomes a tableau operation: insert the second word into the tableau of the first. [example: A Knuth Equivalent Pair] The words $132$ and $312$ differ by one Knuth move. In the relation $xzy \equiv_K zxy$ with $x \le y < z$, take $x=1$, $y=2$, and $z=3$; since $1 \le 2 < 3$, the word $xzy$ is $132$ and the word $zxy$ is $312$. Hence $132 \equiv_K 312$. Now compute the insertion tableaux. For $132$, inserting $1$ into the empty tableau gives $(1)$. Inserting $3$ into the first row $(1)$ appends, because $1$ is not strictly greater than $3$, so the tableau is $(1,3)$. Inserting $2$ into the first row $(1,3)$ replaces the leftmost entry strictly greater than $2$, namely $3$, giving first row $(1,2)$; the bumped $3$ appends to the empty second row. Thus \begin{align*} P(132)=(1,2)/(3). \end{align*} For $312$, inserting $3$ into the empty tableau gives $(3)$. Inserting $1$ into the first row $(3)$ replaces $3$, because $3>1$, and the bumped $3$ appends to the empty second row, giving $(1)/(3)$. Inserting $2$ into the first row $(1)$ appends, because $1$ is not strictly greater than $2$, so \begin{align*} P(312)=(1,2)/(3). \end{align*} Therefore the two different words $132$ and $312$ represent the same tableau element in the plactic monoid. [/example] ## Greene Invariants and Increasing Subsequences The shape of $P(w)$ is not an accident of the insertion procedure. It records extremal subsequence data of $w$, and this is the point at which tableaux begin to measure representation-theoretic structure. We first isolate the statistic in the first row. To state it, we need the subsequences whose maximum length will be measured by Schensted's theorem. [definition: Increasing Subsequence] Let $w=a_1\cdots a_n$ be a word in a totally ordered alphabet. An increasing subsequence of $w$ is a subsequence $a_{i_1}\cdots a_{i_k}$ with $1 \le i_1 < \cdots < i_k \le n$ and $a_{i_1} \le \cdots \le a_{i_k}$. [/definition] For permutations this agrees with the usual strict notion of longest increasing subsequence, because no letter repeats. For words with repeated letters, the weak inequality is the convention compatible with row insertion using the first entry strictly greater than the inserted letter. With the opposite semistandard convention, the corresponding subsequence statistic would be strict instead. The definition now gives a statistic attached directly to the input word, while insertion gives a shape attached to the output tableau. Schensted's theorem is needed to prove that these two pieces of data are the same: the first row of the insertion tableau measures the longest weakly increasing subsequence of the word. [quotetheorem:8433] [citeproof:8433] Schensted's theorem explains the first row of the insertion shape through one longest increasing subsequence, and the convention on weak increase is essential. If $w=11$, row insertion appends the second $1$, giving shape $(2)$; this matches a weakly increasing subsequence of length $2$, not a strictly increasing one. The theorem also has a limitation: it detects only the first row, so it cannot distinguish words whose longest increasing subsequences have the same length but whose lower-row structure differs. The examples above also have nonempty lower rows, so we need a definition that measures what can be captured by several disjoint increasing subsequences at once. [definition: Greene Invariant] Let $A$ be a totally ordered alphabet. For $r \ge 1$, the $r$th Greene invariant is the function $g_r:A^* \to \mathbb N \cup \{0\}$ such that $g_r(w)$ is the maximum total length of a union of $r$ pairwise disjoint increasing subsequences of $w$. [/definition] The Greene invariants extend the longest-increasing-subsequence statistic from one subsequence to $r$ disjoint subsequences. The remaining question is whether these word-level maxima really see the lower rows of the insertion tableau, rather than only giving unrelated combinatorial statistics. Greene's theorem supplies that missing comparison by matching the invariant $g_r(w)$ with the sum of the first $r$ row lengths of the insertion shape. [quotetheorem:8434] Greene's theorem is stated here as structural context for the row sums of the insertion shape. The disjointness condition is necessary: without it, the same long increasing subsequence could be counted repeatedly, making $g_r(w)$ equal to $r g_1(w)$ rather than a statistic of the first $r$ rows. For example, if $w=123$, allowing repeated use of positions would give a false value $6$ for two subsequences, while the tableau shape $(3)$ has $\lambda_1+\lambda_2=3$. The theorem is also bounded by the chosen row-insertion convention; with repeated letters, the increasing subsequences here are weakly increasing, matching the earlier definition. Schensted's theorem is the special case $r=1$. [example: Greene Invariants For A Shape] For $w=241635$, write the letters with their positions: \begin{align*} (1,2), (2,4), (3,1), (4,6), (5,3), (6,5). \end{align*} The subsequence in positions $1,2,4$ is $2,4,6$, and it is increasing because $2<4<6$, so $g_1(w)\ge 3$. From the computed insertion tableau $P(241635)$, the shape is $(3,3)$, and *Schensted Theorem* gives that the longest increasing subsequence has length $\lambda_1=3$. Hence $g_1(w)=3$. For $g_2(w)$, take the subsequence in positions $1,2,4$, namely $2,4,6$, and the subsequence in positions $3,5,6$, namely $1,3,5$. They are disjoint because their position sets are $\{1,2,4\}$ and $\{3,5,6\}$, and each is increasing since $2<4<6$ and $1<3<5$. Their total length is $3+3=6$, so $g_2(w)\ge 6$. Since $w$ has only six positions, any union of two disjoint subsequences has total length at most $6$. Therefore $g_2(w)=6$, matching the row sum $3+3$ of the shape $(3,3)$. [/example] This chapter leaves us with three equivalent ways to view the same object: a plactic class of words, a semistandard tableau, and a collection of increasing-subsequence invariants encoded by its shape. The next chapter adds the recording tableau, upgrading insertion into the full RSK bijection for permutations and matrices. By the end of Chapter 1, insertion has organized words into tableaux and plactic classes, but it still remembers only the insertion tableau. The next chapter adds the recording tableau, turning this local combinatorial process into the full RSK correspondence for permutations and matrices. # 2. The RSK Correspondence This chapter turns Schensted insertion from a way of processing a single word into a canonical encoding of a permutation. It assumes the preceding material on Young diagrams, semistandard and standard Young tableaux, and Schensted row insertion. The guiding problem is to retain enough information during insertion to reverse the process. The answer is to record not only the insertion tableau but also the moments at which new boxes are created, producing a pair of standard Young tableaux of the same shape. The correspondence is more than an algorithmic convenience. It converts statistics of permutations into shapes of Young diagrams, connects increasing subsequences with tableau shapes, and gives a combinatorial shadow of the [Cauchy identity for Schur functions](/theorems/5202). Chapters 3 and 4 use this bridge between words, tableaux, and symmetric functions when constructing Specht modules and interpreting their characters through the Frobenius characteristic. ## Recording Insertion for Permutations If Schensted insertion sends many words to the same insertion tableau, what extra data should be kept to make the process reversible for permutations? For a permutation, the letters are inserted in the order $1,2,\dots,n$, and each insertion adds exactly one box to the Young diagram. Recording the time at which each box appears gives a second standard tableau. [definition: Standard Young Tableau] A standard Young tableau of shape $\lambda \vdash n$ is a filling of the Young diagram of $\lambda$ with the entries $1,2,\dots,n$ such that entries increase strictly from left to right along each row and strictly from top to bottom down each column. [/definition] The two monotonicity conditions ensure that the entries remember a legal growth sequence of Young diagrams: the boxes labelled $1,\dots,k$ form a Young diagram for every $k$. The next definition is needed to package Schensted insertion together with exactly this growth record, so that a permutation produces both an insertion tableau and a recording tableau. [definition: RSK Correspondence for Permutations] For $n \ge 1$, the RSK correspondence for permutations is the map \begin{align*} \operatorname{RSK}:S_n \to \{(P,Q): P,Q \text{ are standard Young tableaux of the same shape } \lambda \vdash n\}. \end{align*} For $w=w_1w_2\cdots w_n \in S_n$, the image $\operatorname{RSK}(w)=(P(w),Q(w))$ is constructed as follows: insert $w_1,w_2,\dots,w_n$ successively by Schensted row insertion, let $P(w)$ be the final insertion tableau, and let $Q(w)$ be the tableau whose entry $i$ is placed in the new box created when $w_i$ is inserted. [/definition] The tableau $P(w)$ records the relative order structure of the letters, while $Q(w)$ records where the shape grew at each time. Since the input is a permutation, both tableaux are standard and have the same shape. [example: RSK for 351624] Let $w=351624$, so the letters are inserted in the order $3,5,1,6,2,4$. Insert $3$ into the empty tableau; it creates the first box, so \begin{align*} P_1=(3),\qquad Q_1=(1). \end{align*} Since $5>3$, inserting $5$ appends it to the first row: \begin{align*} P_2=(3,5),\qquad Q_2=(1,2). \end{align*} When $1$ is inserted into the row $(3,5)$, the leftmost entry larger than $1$ is $3$, so $1$ replaces $3$ and $3$ is bumped to a new second row: \begin{align*} P_3=(1,5)/(3),\qquad Q_3=(1,2)/(3). \end{align*} Next $6$ is larger than both entries in the first row $(1,5)$, so it appends to that row: \begin{align*} P_4=(1,5,6)/(3),\qquad Q_4=(1,2,4)/(3). \end{align*} When $2$ is inserted into $(1,5,6)$, the leftmost entry larger than $2$ is $5$, so the first row becomes $(1,2,6)$ and $5$ is bumped into the second row. Since $5>3$, it appends there: \begin{align*} P_5=(1,2,6)/(3,5),\qquad Q_5=(1,2,4)/(3,5). \end{align*} Finally, inserting $4$ into $(1,2,6)$ replaces $6$ by $4$, and the bumped entry $6$ appends to the second row $(3,5)$: \begin{align*} P_6=(1,2,4)/(3,5,6),\qquad Q_6=(1,2,4)/(3,5,6). \end{align*} Thus $P(w)=Q(w)$ in this example, and both tableaux have shape $(3,3)$. The first row has length $3$ and the first column has length $2$, so Schensted's theorem gives longest increasing subsequences of length $3$ and longest decreasing subsequences of length $2$. [/example] The coincidence $P(w)=Q(w)$ in this example is not typical; it reflects special symmetry in this particular permutation. The example also raises the central structural question: does the pair $(P(w),Q(w))$ always retain enough data to reconstruct $w$, and does every pair of standard tableaux of common shape arise in this way? [quotetheorem:8435] [citeproof:8435] The theorem depends essentially on the permutation hypothesis. Because each value $1,\dots,n$ is inserted exactly once and each time label appears exactly once, both $P(w)$ and $Q(w)$ are standard; if repeated letters are allowed, the insertion tableau need not be standard, and a different semistandard version is required. The theorem also does not say that the insertion tableau alone determines $w$: many permutations have the same $P$-tableau, and the recording tableau is precisely the missing inverse data. Thus the bijection is a statement about pairs of tableaux of common shape, not about a single canonical tableau attached to a permutation. A first numerical consequence is obtained by grouping permutations by their RSK shape. If $f^\lambda$ denotes the number of standard Young tableaux of shape $\lambda$, then the theorem partitions $S_n$ into $(f^\lambda)^2$ permutations of each shape $\lambda$. [example: Permutations of Shape (3,2,1)] For $\lambda=(3,2,1)$, the Young diagram has cells \begin{align*} (1,1),(1,2),(1,3),(2,1),(2,2),(3,1). \end{align*} The hook length of a cell is the number of cells weakly to its right in the same row plus the number of cells strictly below it in the same column. Thus the hook lengths are \begin{align*} h(1,1)=3+2=5,\quad h(1,2)=2+1=3,\quad h(1,3)=1+0=1,\quad h(2,1)=2+1=3,\quad h(2,2)=1+0=1,\quad h(3,1)=1+0=1. \end{align*} By the *Hook-Length Formula*, \begin{align*} f^{(3,2,1)}=\frac{6!}{5\cdot 3\cdot 1\cdot 3\cdot 1\cdot 1}. \end{align*} Since $6!=720$ and \begin{align*} 5\cdot 3\cdot 1\cdot 3\cdot 1\cdot 1=45, \end{align*} we get \begin{align*} f^{(3,2,1)}=\frac{720}{45}=16. \end{align*} By the *RSK Bijection Theorem*, permutations of RSK shape $(3,2,1)$ are in bijection with pairs $(P,Q)$ of standard Young tableaux of shape $(3,2,1)$. There are $16$ choices for $P$ and, independently, $16$ choices for $Q$, so the number of such permutations in $S_6$ is \begin{align*} 16\cdot 16=256. \end{align*} Thus the count comes from choosing the insertion tableau and recording tableau independently, both with common shape $(3,2,1)$. [/example] This counting result is the finite shadow of a symmetric-function identity. RSK sorts monomials by tableau shape, while Schur functions package semistandard tableaux of fixed shape. [quotetheorem:8436] In this course the identity is used as context rather than proved here. Its bijective proof is the matrix version of RSK: a nonnegative integer matrix is encoded by a pair of semistandard tableaux of common shape, with the row indices contributing the $x$-weight and the column indices contributing the $y$-weight. The formal [power series](/page/Power%20Series) interpretation matters because the product involves infinitely many factors; each monomial uses only finitely many variables and receives a well-defined coefficient. The identity does not assert numerical convergence unless separate analytic hypotheses such as absolute convergence are imposed. It also does not identify individual Schur functions with the whole product: it decomposes the product by the common shape of the two tableaux. ## Two-Line Arrays and Matrix RSK Permutations are the special case where every row and column index occurs once. The next problem is how to insert data with repeated letters, such as multisets of pairs or nonnegative integer matrices. Two-line arrays provide the input format that keeps the order of insertion compatible with semistandard recording. [definition: Two-Line Array] A two-line array is a finite sequence of columns $\binom{i_1}{j_1},\binom{i_2}{j_2},\dots,\binom{i_N}{j_N}$ ordered lexicographically: $i_1\le i_2\le\cdots\le i_N$, and whenever $i_k=i_{k+1}$, one has $j_k\le j_{k+1}$. [/definition] The lower row is inserted, while the upper row records which row index of the matrix caused the new box. The weak ordering in equal upper entries is what makes the recording tableau semistandard rather than standard. This prepares the matrix form by converting each matrix entry into a controlled number of ordered columns. [definition: Matrix RSK] Matrix RSK is the map \begin{align*} \operatorname{RSK}_{\mathrm{mat}}:\{\text{finitely supported matrices } A=(a_{ij}) \text{ with } a_{ij}\in \mathbb N\cup\{0\}\} \to \{(P,Q): P,Q \text{ are semistandard Young tableaux of the same shape}\}. \end{align*} For such a matrix $A$, form the two-line array containing $a_{ij}$ copies of the column $\binom{i}{j}$, ordered lexicographically. Matrix RSK applies row insertion to the lower row entries $j$ and records the corresponding upper row entries $i$ in the new boxes. [/definition] After the definition, the permutation case appears as the special case of a permutation matrix. In that case each upper entry and each lower entry appears once, so semistandard tableaux specialize to standard tableaux. [example: A Small Matrix Input] Consider the matrix with nonzero entries $a_{11}=1$, $a_{12}=1$, $a_{21}=1$, and $a_{23}=1$. Matrix RSK replaces these entries by one copy of $\binom{i}{j}$ for each unit in $a_{ij}$, ordered lexicographically by the top entry and then by the bottom entry. Thus the two-line array is \begin{align*}\binom{1}{1},\binom{1}{2},\binom{2}{1},\binom{2}{3}.\end{align*} We insert the lower row entries $1,2,1,3$ and record the corresponding upper row entries $1,1,2,2$ in the boxes created during insertion. First, inserting $1$ into the empty tableau creates one box, so \begin{align*}P_1=(1),\qquad Q_1=(1).\end{align*} Next, inserting $2$ into the first row $(1)$ appends it because $2>1$, and the new box is recorded with upper entry $1$: \begin{align*}P_2=(1,2),\qquad Q_2=(1,1).\end{align*} Now insert the next lower entry $1$ into the row $(1,2)$. The row-insertion rule bumps the leftmost entry strictly larger than $1$; that entry is $2$, so the first row becomes $(1,1)$ and the bumped entry $2$ is inserted into the empty second row. The new box is in the second row, and its recording entry is the corresponding upper entry $2$: \begin{align*}P_3=(1,1)/(2),\qquad Q_3=(1,1)/(2).\end{align*} Finally, inserting $3$ into the first row $(1,1)$ appends it because $3>1$ for both existing entries. The new box is the third box of the first row, and its recording entry is $2$: \begin{align*}P_4=(1,1,3)/(2),\qquad Q_4=(1,1,2)/(2).\end{align*} Thus the output is \begin{align*}P=(1,1,3)/(2),\qquad Q=(1,1,2)/(2),\end{align*} where the slash separates the first and second rows. Both tableaux have three boxes in the first row and one box in the second row, so their common shape is $(3,1)$. The repeated top entries $1,1$ and $2,2$ become repeated entries in the recording tableau, while the insertion tableau records the lower entries, namely the column indices of the original matrix. [/example] The matrix form is the version that interacts most directly with symmetric functions. Summing over all matrices gives the product side of the Cauchy identity, and sorting by the common RSK shape gives the Schur-function expansion. ## Symmetries of the Correspondence Once a permutation is encoded by two tableaux, natural operations on the permutation should have tableau-level descriptions. The most important first symmetry asks what happens when the permutation is inverted. Since inversion swaps positions and values, it should interchange the two roles played by $P$ and $Q$. [quotetheorem:8437] [citeproof:8437] This theorem explains why the recording tableau is not auxiliary bookkeeping; it carries the same kind of information as the insertion tableau, but for the inverse permutation. The statement is tied to the row-insertion convention used throughout the chapter: changing to a dual insertion convention changes which tableau operations represent inversion. The matrix explanation also shows the limitation of the theorem, since the swap comes from transposing the permutation matrix, so the clean statement applies to inversion rather than to arbitrary reorderings of the word. In later variants of RSK, similar-looking symmetries must always be checked against the chosen ordering of two-line arrays and the chosen insertion rule. [example: Inverting 351624] For $w=351624$, the entries mean \begin{align*} w_1=3,\; w_2=5,\; w_3=1,\; w_4=6,\; w_5=2,\; w_6=4. \end{align*} The inverse is determined by $w^{-1}_j=i$ exactly when $w_i=j$. Thus $w_3=1$ gives $w^{-1}_1=3$, $w_5=2$ gives $w^{-1}_2=5$, $w_1=3$ gives $w^{-1}_3=1$, $w_6=4$ gives $w^{-1}_4=6$, $w_2=5$ gives $w^{-1}_5=2$, and $w_4=6$ gives $w^{-1}_6=4$. Hence \begin{align*} w^{-1}=351624=w. \end{align*} From the earlier insertion computation, \begin{align*} P(w)=(1,2,4)/(3,5,6),\qquad Q(w)=(1,2,4)/(3,5,6). \end{align*} Therefore $P(w)=Q(w)$. By *Inverse Permutation Symmetry*, $P(w^{-1})=Q(w)$ and $Q(w^{-1})=P(w)$; since $w^{-1}=w$, these identities become \begin{align*} P(w)=Q(w),\qquad Q(w)=P(w). \end{align*} So this permutation is a fixed point of inversion, and its RSK pair is fixed by swapping the two tableaux. [/example] Other symmetries require more structure than inversion. Transposing tableaux and reversing words are related to variants of insertion, while Schutzenberger evacuation gives a deeper involution on standard tableaux. [definition: Evacuation] For a partition $\lambda \vdash n$, Schutzenberger evacuation is the map \begin{align*} \operatorname{evac}:\operatorname{SYT}(\lambda) \to \operatorname{SYT}(\lambda) \end{align*} defined by iterated jeu de taquin deletion, and satisfying $\operatorname{evac}\circ\operatorname{evac}=\operatorname{id}_{\operatorname{SYT}(\lambda)}$. [/definition] It can also be characterized by tableau symmetries induced by reversing suitable reading words. The definition is included as a preview because evacuation will reappear when crystals and duality enter the course. [remark: Symmetry Dictionary] Inversion of a permutation swaps $P$ and $Q$. Matrix transposition is the same symmetry in the matrix formulation. Reversal, complement, and inverse-reversal operations interact with tableau transposition and evacuation, but their precise forms depend on the chosen insertion convention. [/remark] The main lesson of the chapter is that RSK is not merely a method for finding longest increasing subsequences. It is a bijective coordinate system for permutations, matrices, and eventually representation-theoretic bases. The shape records coarse representation-theoretic type, while the two tableaux retain the fine combinatorial data needed for reconstruction and symmetry. RSK shows how a permutation can be encoded by a pair of tableaux together with the shape that measures its increasing and decreasing structure. That bijective viewpoint is the bridge to representation theory: the next chapter turns tableaux from an encoding device into the basis data for actual $S_n$-modules. # 3. Specht Modules and Young Symmetrizers This chapter turns the combinatorics of tableaux into actual representations of $S_n$. It uses the earlier material on partitions, Young diagrams, Schur functions, the Frobenius characteristic, and the basic language of finite-dimensional group representations. The guiding problem is to build modules whose bases are controlled by Young diagrams and whose characters match the Schur functions seen earlier through the Frobenius characteristic. The construction uses two competing symmetries of a tableau: symmetrising along rows and antisymmetrising down columns. Their interaction produces the Specht module $S^\lambda$, the fundamental irreducible representation attached to a partition $\lambda \vdash n$ over characteristic zero. ## Young Subgroups and Tableau Symmetries Given a Young diagram $\lambda \vdash n$, how can a filling of its boxes remember enough subgroup structure to define a representation? The answer is to let the rows and columns of a tableau determine two subgroups of $S_n$. Rows encode permutations that preserve horizontal positions as sets; columns encode permutations that preserve vertical positions as sets. These two subgroups give two elements of the group algebra with opposite symmetry types. [definition: Young Tableau Of Shape Lambda] Let $\lambda \vdash n$, and let $B(\lambda)$ be the set of boxes in the Young diagram of $\lambda$. A Young tableau $t$ of shape $\lambda$ is a bijection \begin{align*} t:B(\lambda)\longrightarrow \{1,\dots,n\}. \end{align*} [/definition] The tableau is not yet required to be standard; it is a labelled diagram used to locate the numbers $1,\dots,n$ in rows and columns. The symmetric group acts on such tableaux by permuting the entries, and the first calculation to make is which permutations preserve the row and column structure of a fixed filling. [example: Two Tableaux Of Shape Two One] For $\lambda=(2,1)$, write a tableau as rows separated by a semicolon, so $t=[1,2;3]$ means that $1$ and $2$ occupy the top row and $3$ occupies the single box below the first column. Thus the row sets of $t$ are $\{1,2\}$ and $\{3\}$, while the column sets are $\{1,3\}$ and $\{2\}$. The transposition $(23)$ acts on a tableau by replacing each label $i$ with $(23)(i)$. Hence \begin{align*} (23)(1)=1,\quad (23)(2)=3,\quad (23)(3)=2. \end{align*} Applying these replacements entry by entry gives \begin{align*} (23)[1,2;3]=[(23)(1),(23)(2);(23)(3)]=[1,3;2]. \end{align*} The Young diagram still has shape $(2,1)$, but the row and column sets have changed: the first row is now $\{1,3\}$ and the first column is now $\{1,2\}$. [/example] The preceding example shows that a tableau determines set partitions of $\{1,\dots,n\}$ by rows and columns. To make those set partitions act algebraically, we need the subgroups that move entries only within a single row or only within a single column. [definition: Row And Column Stabilizers] Let $t$ be a Young tableau of shape $\lambda \vdash n$. The row stabilizer $R_t \le S_n$ is the subgroup of permutations preserving each row of $t$ as a set. The column stabilizer $C_t \le S_n$ is the subgroup of permutations preserving each column of $t$ as a set. [/definition] The row stabilizer and column stabilizer depend on the labelling $t$, not only on $\lambda$. If $s=wt$ for $w \in S_n$, then $R_s=wR_tw^{-1}$ and $C_s=wC_tw^{-1}$. A concrete stabilizer computation shows what information these groups retain. [example: Stabilizers For Shape Two One] For $t=[1,2;3]$, the row sets are $\{1,2\}$ and $\{3\}$. A permutation lies in $R_t$ exactly when it sends each of these sets to itself. Thus $3$ must be fixed, while $1$ and $2$ may either both stay fixed or be exchanged. Hence the only possibilities are \begin{align*} R_t=\{e,(12)\}. \end{align*} The column sets are $\{1,3\}$ and $\{2\}$. A permutation lies in $C_t$ exactly when it sends each of these sets to itself. Thus $2$ must be fixed, while $1$ and $3$ may either both stay fixed or be exchanged. Hence \begin{align*} C_t=\{e,(13)\}. \end{align*} So the row stabilizer records the allowed symmetry inside the first row, and the column stabilizer records the allowed symmetry inside the first column. [/example] The stabilizers by themselves are still groups, not vectors or operators in a representation. To build a submodule of the group algebra, we need group-algebra elements that enforce row invariance and column sign changes. [definition: Row Symmetrizer And Column Antisymmetrizer] Let $t$ be a Young tableau of shape $\lambda \vdash n$. In the group algebra $\mathbb C[S_n]$, define \begin{align*} a_t = \sum_{r \in R_t} r, \qquad b_t = \sum_{c \in C_t} \operatorname{sgn}(c)c. \end{align*} The element $a_t$ is the row symmetrizer of $t$, and $b_t$ is the column antisymmetrizer of $t$. [/definition] These elements impose the two tableau symmetries separately: $a_t$ forgets order within rows, while $b_t$ changes sign under odd column permutations. The construction needs a single group-algebra generator carrying both constraints, so this motivates composing the two operators in a fixed order. Here $\mathbb C[S_n]$ denotes the group algebra: its elements are finite complex linear combinations of permutations in $S_n$, with multiplication extended linearly from permutation composition. From this point on, multiplication in $S_n$ and in $\mathbb C[S_n]$ is composition from right to left: $uv$ means first apply $v$, then apply $u$. The induced left action on tableaux satisfies $(uv)t=u(vt)$. [definition: Young Symmetrizer] Let $t$ be a Young tableau of shape $\lambda \vdash n$. The Young symmetrizer associated to $t$ is \begin{align*} c_t=a_tb_t \in \mathbb C[S_n]. \end{align*} [/definition] Some texts use $b_ta_t$ instead. The two conventions give isomorphic Specht modules after adjusting the side on which the group algebra acts, but this chapter fixes $c_t=a_tb_t$ and constructs left ideals. The construction works especially cleanly over $\mathbb C$, where the usual hook-length scalar is invertible and Young symmetrizers behave like projection data. In modular characteristic that normalization can fail, so the characteristic-zero hypothesis below is not cosmetic. We next use this element to build the module attached to $\lambda$. ## Specht Modules Inside The Group Algebra The main construction problem is now concrete: given $\lambda \vdash n$, which subspace of $\mathbb C[S_n]$ should be called the representation of shape $\lambda$? Since $S_n$ acts on $\mathbb C[S_n]$ by left multiplication, any left ideal is automatically an $S_n$-module. Young symmetrizers provide such left ideals with tableau-shaped symmetry built in. A left ideal means a subspace $I\subseteq \mathbb C[S_n]$ such that $xI\subseteq I$ for every $x\in \mathbb C[S_n]$; in particular, left multiplication by permutations makes $I$ an $S_n$-module. In this group-algebra construction we use the convention fixed above and used by the quoted construction theorem: for every tableau $u$, set $a_u=\sum_{\rho\in R_u}\rho$, set $b_u=\sum_{\kappa\in C_u}\operatorname{sgn}(\kappa)\kappa$, and write $c_u=a_ub_u$. [definition: Specht Module In The Group Algebra] Let $\lambda \vdash n$, and let $t$ be a Young tableau of shape $\lambda$. The Specht module of shape $\lambda$ is the left $\mathbb C[S_n]$-module \begin{align*} S^\lambda = \mathbb C[S_n]c_t \subset \mathbb C[S_n]. \end{align*} [/definition] The notation suppresses the tableau $t$, so the next issue is well-definedness. Since two tableaux of the same shape differ by relabelling, we need to know that relabelling only conjugates the construction and does not change the resulting representation. [quotetheorem:8438] [citeproof:8438] The fixed-shape hypothesis is essential: if $s$ and $t$ have different shapes, their row and column stabilizers have different orbit structures, so there is no relabelling $w$ with $s=wt$ and the conjugation argument has no starting point. A concrete failure occurs for $S_3$: the shapes $(3)$ and $(1,1,1)$ produce the identity-action and sign representations, which are not isomorphic because a transposition acts by $1$ on the first and by $-1$ on the second. The use of right multiplication is also structural. It commutes with the left $S_n$-action, so it gives a homomorphism of left modules; left multiplication by $w^{-1}$ would generally alter the given left action rather than intertwine it. This theorem proves that the auxiliary filling does not matter and gives an isomorphism class, not a canonical equality of subspaces inside $\mathbb C[S_n]$. It also does not prove irreducibility or that every irreducible has been found. The next question is how this representation sits inside the regular representation and why it is reasonable to expect all irreducibles to appear this way. For that, the course recalls the semisimplicity theorem for finite group representations. [quotetheorem:8439] For this course, Maschke's theorem is recalled from representation theory rather than reproved. The characteristic condition is necessary: for example, over a field $k$ of characteristic $p$, let $C_p=\langle g\rangle$ be the [cyclic group](/page/Cyclic%20Group) of order $p$. The group algebra $k[C_p]$ is not semisimple, since the element $g-1$ is nilpotent in $k[C_p]$ and the one-dimensional module on which $C_p$ acts as the identity has nonsplit extensions. Over $\mathbb C$, Maschke applies to $G=S_n$, so every submodule of the group algebra splits as a direct summand. This splitting makes Specht modules candidates for irreducible summands of the regular representation, but Maschke alone does not identify which summands are irreducible or distinguish the Specht modules from one another. The classification theorem supplies exactly that missing information in characteristic zero. [quotetheorem:8440] [citeproof:8440] This theorem is the structural endpoint of the characteristic-zero theory, and its hypotheses should not be suppressed. The inner-product argument uses complete reducibility and complex characters; in positive characteristic the same Specht modules still exist, but they can be reducible and need not form a complete list of simple modules. For instance, in characteristic $2$ the sign and identity-action representations of $S_n$ coincide, so the ordinary characteristic-zero separation by characters already breaks down. Modular representation theory refines the partition indexing by using $p$-regular partitions and decomposition numbers. Thus the theorem identifies the ordinary irreducible representations of $S_n$ and also marks which parts of the argument depend on characteristic zero. The next task is computational: Young symmetrizers define modules inside a large group algebra, while actual calculations require smaller, combinatorial bases. [example: The Specht Module Of Shape Two One] Let $t=[1,2;3]$. Its row stabilizer is $R_t=\{e,(12)\}$ and its column stabilizer is $C_t=\{e,(13)\}$, with $\operatorname{sgn}(e)=1$ and $\operatorname{sgn}((13))=-1$. Hence \begin{align*} a_t=e+(12). \end{align*} Also \begin{align*} b_t=e-(13). \end{align*} Multiplying in $\mathbb C[S_3]$, with composition from right to left, gives \begin{align*} c_t=a_tb_t=(e+(12))(e-(13)). \end{align*} Distributing the product gives \begin{align*} (e+(12))(e-(13))=ee-e(13)+(12)e-(12)(13). \end{align*} The first three products are $ee=e$, $e(13)=(13)$, and $(12)e=(12)$. For the last product, $(12)(13)$ sends $1$ to $3$, sends $3$ to $2$, and sends $2$ to $1$, so $(12)(13)=(132)$. Therefore \begin{align*} c_t=e+(12)-(13)-(132). \end{align*} By the *[Standard Polytabloid Basis Theorem](/theorems/8442)*, $S^{(2,1)}$ has a basis indexed by the standard tableaux of shape $(2,1)$. These are exactly $[1,2;3]$ and $[1,3;2]$: the remaining fillings either have the top row decreasing or the first column decreasing. Thus \begin{align*} \dim S^{(2,1)}=2. \end{align*} By *[Irreducibility And Completeness Of Specht Modules](/theorems/8430)*, the Specht modules for the three partitions of $3$ are the three irreducible complex representations of $S_3$. The shapes $(3)$ and $(1,1,1)$ give the one-dimensional identity-action and sign representations, respectively, so the two-dimensional module $S^{(2,1)}$ is the remaining irreducible, namely the standard two-dimensional representation of $S_3$. [/example] ## Polytabloids And The Standard Basis Problem The group algebra construction is canonical but too large for routine calculation. The next problem is to find explicit spanning vectors labelled by tableaux and then identify a basis among them. This leads from Young symmetrizers to tabloids and polytabloids. [definition: Tabloid] Let $\lambda \vdash n$. A tabloid of shape $\lambda$ is an equivalence class $\{t\}$ of Young tableaux of shape $\lambda$, where two tableaux are equivalent if each row contains the same set of entries. [/definition] A tabloid forgets the order within each row but remembers which numbers lie in each row. Since row symmetrizers already identify row permutations, this motivates using tabloids as the ambient basis for a smaller module. [definition: Permutation Module On Tabloids] Let $\lambda \vdash n$. The permutation module $M^\lambda$ is the complex vector space with basis the tabloids $\{t\}$ of shape $\lambda$, equipped with the $S_n$-action \begin{align*} S_n \times M^\lambda \longrightarrow M^\lambda, \qquad (w,\{t\}) \longmapsto \{wt\}. \end{align*} [/definition] The module $M^\lambda$ is induced from the one-dimensional identity-action representation of the row subgroup. To recover the alternating column behaviour of $b_t$, we need vectors in $M^\lambda$ formed by signed sums over column permutations. [definition: Polytabloid] Let $t$ be a Young tableau of shape $\lambda \vdash n$. The polytabloid associated to $t$ is \begin{align*} e_t=\sum_{c \in C_t}\operatorname{sgn}(c)\{ct\}\in M^\lambda. \end{align*} [/definition] The vector $e_t$ changes sign when two entries in a column are swapped, while row permutations do not change the tabloid. A comparison theorem is needed because computations will use polytabloids, but the Specht module was originally defined as a left ideal generated by $c_t$. The standard comparison result identifies these two models: if $E^\lambda$ is the span of all polytabloids of shape $\lambda$ inside $M^\lambda$, then $E^\lambda$ is an $S_n$-submodule and is isomorphic to the group-algebra Specht module $S^\lambda$ constructed above. We use this comparison as a structural fact rather than reproving it here. This realisation explains why ordinary tabloids are not enough: the full permutation module $M^\lambda$ usually contains extra constituents coming from row symmetry alone. For $\lambda=(2,1)$, the three-dimensional tabloid module contains a one-dimensional invariant line spanned by the sum of all tabloids, whereas the Specht module is the two-dimensional column-antisymmetrized part. This is a concrete failure of the tempting replacement "use $M^\lambda$ itself": it gives the wrong dimension and includes the identity-action summand. The fixed-shape ambient module is also part of the statement; a polytabloid of shape $(2,1)$ is a vector in $M^{(2,1)}$, not in the one-dimensional tabloid module $M^{(3)}$. Polytabloids remove the redundant symmetric direction by forcing the sign relation down each column. The comparison identifies the correct submodule, but it does not say that all polytabloids are independent or that a chosen list of them is minimal. The basis problem asks which polytabloids are enough and how to discard the redundant ones. The answer uses the increasing tableaux already familiar from RSK. [definition: Standard Young Tableau] A Young tableau is standard if its entries increase from left to right along every row and from top to bottom down every column. [/definition] Standard tableaux appeared in Chapter 2 as insertion and recording tableaux in RSK. Their second role is representation-theoretic: they count and label a basis of $S^\lambda$. The theorem below is what makes Specht modules genuinely computable. [quotetheorem:8442] [citeproof:8442] The standardness condition is essential rather than decorative. Nonstandard polytabloids belong to the same spanning world, but straightening rewrites them in terms of the standard ones, so using every polytabloid would give a redundant spanning set rather than a basis. The theorem solves the standard basis problem and gives $\dim S^\lambda=f^\lambda$, the number of standard Young tableaux of shape $\lambda$. It does not by itself compute the matrices of arbitrary permutations; those still require applying the permutation and straightening back to the standard basis. It also makes the connection with RSK visible: the same tableaux that index permutations by shape now index irreducible representation bases. [example: Polytabloids For Shape Two One] For $\lambda=(2,1)$, the standard tableaux are $t_1=[1,2;3]$ and $t_2=[1,3;2]$: the top row must increase, and the first column must increase, leaving exactly these two fillings. For $t_1=[1,2;3]$, the column sets are $\{1,3\}$ and $\{2\}$, so $C_{t_1}=\{e,(13)\}$. Since $\operatorname{sgn}(e)=1$ and $\operatorname{sgn}((13))=-1$, the definition of polytabloid gives \begin{align*} e_{t_1}=\operatorname{sgn}(e)\{et_1\}+\operatorname{sgn}((13))\{(13)t_1\}=\{[1,2;3]\}-\{[3,2;1]\}. \end{align*} For $t_2=[1,3;2]$, the column sets are $\{1,2\}$ and $\{3\}$, so $C_{t_2}=\{e,(12)\}$. Therefore \begin{align*} e_{t_2}=\operatorname{sgn}(e)\{et_2\}+\operatorname{sgn}((12))\{(12)t_2\}=\{[1,3;2]\}-\{[2,3;1]\}. \end{align*} By the *Standard Polytabloid Basis Theorem*, the standard polytabloids $e_{t_1}$ and $e_{t_2}$ form a basis of $S^{(2,1)}$. The hook lengths of the three boxes of shape $(2,1)$ are $3$, $1$, and $1$, so the hook-length formula gives \begin{align*} f^{(2,1)}=\frac{3!}{3\cdot 1\cdot 1}=2. \end{align*} Thus the basis has the expected two vectors, and $S^{(2,1)}$ is two-dimensional. [/example] The basis theorem turns representation matrices into combinatorics. We finish by computing the action of the adjacent transpositions $s_1=(12)$ and $s_2=(23)$ on the basis above. [example: Simple Transpositions On Shape Two One] Let \begin{align*} A=\{[1,2;3]\}, \qquad B=\{[1,3;2]\}, \qquad C=\{[2,3;1]\}. \end{align*} For the standard tableaux $t_1=[1,2;3]$ and $t_2=[1,3;2]$, the preceding polytabloid computation gives \begin{align*} v_1=e_{t_1}=A-C, \qquad v_2=e_{t_2}=B-C. \end{align*} We compute the action of $s_1=(12)$ and $s_2=(23)$ on this basis by applying each permutation to the labels in the tabloids. For $s_1=(12)$, applying $s_1$ to $[1,2;3]$ gives $[2,1;3]$, which has the same row sets as $[1,2;3]$, so $s_1A=A$. Also \begin{align*} s_1[1,3;2]=[2,3;1], \end{align*} so $s_1B=C$, and \begin{align*} s_1[2,3;1]=[1,3;2], \end{align*} so $s_1C=B$. Therefore \begin{align*} s_1v_1=s_1(A-C)=s_1A-s_1C=A-B. \end{align*} Since $v_1-v_2=(A-C)-(B-C)=A-B$, this gives \begin{align*} s_1v_1=v_1-v_2. \end{align*} Similarly, \begin{align*} s_1v_2=s_1(B-C)=s_1B-s_1C=C-B. \end{align*} Since $-v_2=-(B-C)=C-B$, we get \begin{align*} s_1v_2=-v_2. \end{align*} For $s_2=(23)$, applying $s_2$ to $[1,2;3]$ gives \begin{align*} s_2[1,2;3]=[1,3;2], \end{align*} so $s_2A=B$. Also \begin{align*} s_2[1,3;2]=[1,2;3], \end{align*} so $s_2B=A$, while \begin{align*} s_2[2,3;1]=[3,2;1], \end{align*} and $[3,2;1]$ has the same row sets as $[2,3;1]$, so $s_2C=C$. Hence \begin{align*} s_2v_1=s_2(A-C)=B-C=v_2. \end{align*} Likewise, \begin{align*} s_2v_2=s_2(B-C)=A-C=v_1. \end{align*} Thus, in the ordered basis $(v_1,v_2)$, the two operators are determined by \begin{align*} s_1v_1=v_1-v_2, \qquad s_1v_2=-v_2. \end{align*} So for arbitrary scalars $a,b\in \mathbb C$, \begin{align*} s_1(av_1+bv_2)=a(v_1-v_2)+b(-v_2)=av_1+(-a-b)v_2. \end{align*} Similarly, \begin{align*} s_2v_1=v_2, \qquad s_2v_2=v_1, \end{align*} so \begin{align*} s_2(av_1+bv_2)=av_2+bv_1=bv_1+av_2. \end{align*} These formulas satisfy the defining Coxeter relations for $S_3$. Indeed, \begin{align*} s_1(s_1(av_1+bv_2))=s_1(av_1+(-a-b)v_2)=av_1+(-a-(-a-b))v_2=av_1+bv_2. \end{align*} Also \begin{align*} s_2(s_2(av_1+bv_2))=s_2(bv_1+av_2)=av_1+bv_2. \end{align*} For the braid relation, \begin{align*} s_1s_2s_1(av_1+bv_2)=s_1s_2(av_1+(-a-b)v_2)=s_1((-a-b)v_1+av_2)=(-a-b)v_1+bv_2. \end{align*} On the other hand, \begin{align*} s_2s_1s_2(av_1+bv_2)=s_2s_1(bv_1+av_2)=s_2(bv_1+(-a-b)v_2)=(-a-b)v_1+bv_2. \end{align*} Therefore the computed operators give the two-dimensional Specht representation $S^{(2,1)}$, the standard two-dimensional representation of $S_3$. [/example] The chapter began with a tableau-dependent element of $\mathbb C[S_n]$ and ends with explicit operators on a standard tableau basis. The important pattern is that row symmetry, column antisymmetry, and straightening together convert the combinatorics of Young diagrams into the full characteristic-zero representation theory of the symmetric group. Specht modules and Young symmetrizers convert the combinatorics of partitions into concrete representations, but their structure still needs numerical invariants to be useful. The next chapter extracts those invariants through characters, branching, and dimension formulas, making the representation theory computable from tableaux data. # 4. Characters, Branching, and Dimensions After Chapter 3 constructed Specht modules and their standard polytabloid bases, this chapter turns the combinatorics of Young diagrams into numerical and character-theoretic information about those modules, continuing the course's passage from symmetric functions and tableaux to representations of symmetric groups. We assume the earlier construction of Specht modules $S^\lambda$ and the classification, over characteristic zero, of irreducible $S_n$-modules by partitions $\lambda$ of $n$. The guiding operation is local: compare a partition of $n$ with partitions of $n-1$ or $n+1$ obtained by removing or adding a single box. From this local movement we get the branching rules for restriction and induction, and then the hook-length formula gives the dimensions of the irreducible $S_n$-modules without constructing bases by hand. ## Moving Through Young's Lattice How does a representation indexed by a partition change when the underlying symmetric group loses or gains one letter? The indexing sets for irreducible representations of $S_n$ and $S_{n-1}$ are different, so the first task is to understand the combinatorial relation between partitions of adjacent sizes. Young diagrams organise this relation into a graded graph, usually called Young's lattice. [definition: Removable Box] Let $\lambda$ be a partition of $n$. A box $b$ in the Young diagram of $\lambda$ is removable if deleting $b$ leaves the Young diagram of a partition of $n-1$. [/definition] A removable box is necessarily at the end of its row and at the bottom of its column. Removing any other box would leave a gap, so the resulting set of boxes would no longer be left-justified. Restriction moves from size $n$ to size $n-1$, but induction moves in the opposite direction, so we also need the upward version of the same local operation. [definition: Addable Box] Let $\lambda$ be a partition of $n$. A box $b$ outside the Young diagram of $\lambda$ is addable if adjoining $b$ gives the Young diagram of a partition of $n+1$. [/definition] Addable and removable boxes are the local moves in the branching graph. They encode all possible adjacent partitions, so the representation-theoretic rules below will have no multiplicities larger than one. [example: Addable And Removable Boxes For Three Two] For $\lambda=(3,2)$, the Young diagram has row lengths $3$ and $2$. A removable box must be the last box of its row and have no box below it in the same column. In row $1$, the last box is in column $3$, and row $2$ has only two boxes, so deleting $(1,3)$ leaves row lengths $2$ and $2$, namely $(2,2)$. In row $2$, the last box is in column $2$, and there is no third row below it, so deleting $(2,2)$ leaves row lengths $3$ and $1$, namely $(3,1)$. An addable box must be placed so that the new row lengths are still weakly decreasing. Adding to row $1$ changes the row lengths from $(3,2)$ to $(4,2)$. Adding to row $2$ changes them to $(3,3)$, which is still a partition because $3\geq 3$. Adding a new third row gives $(3,2,1)$, and no other row can receive a box without creating a gap or violating weak decrease. Hence the adjacent-rank neighbours of $(3,2)$ are exactly \begin{align*} (2,2),\ (3,1),\ (4,2),\ (3,3),\ (3,2,1). \end{align*} [/example] This example shows the individual upward and downward moves around one partition. To state branching rules without listing partitions separately each time, we need a graph whose vertices are partitions and whose edges are precisely one-box additions. [definition: Young Graph] The Young graph has vertices all partitions. There is an edge $\mu \nearrow \lambda$ when $\lambda$ is obtained from $\mu$ by adding one addable box. [/definition] The Young graph packages the recursive structure of Specht modules. The next section states that restriction follows downward edges and induction follows upward edges. ## Restriction and Induction Along One Box What happens to the Specht module $S^\lambda$ when $S_{n-1}$ is embedded in $S_n$ as the subgroup permuting $\{1,\dots,n-1\}$? Since $S^\lambda$ is irreducible for $S_n$, its restriction need not remain irreducible. The branching rule says that the restriction decomposes as the direct sum of all Specht modules obtained by removing one box. [quotetheorem:8443] [citeproof:8443] This theorem is the representation-theoretic form of moving down Young's lattice. The characteristic-zero hypothesis is not cosmetic: it is what allows the filtration by positions of $n$ to split into a direct sum of irreducible Specht modules. In positive characteristic the same filtration can still be meaningful, but its quotients need not split off, Specht modules need not be irreducible, and the displayed formula should not be read as a decomposition into simple modules. The theorem also depends on the standard embedding $S_{n-1}\le S_n$; it describes forgetting the action of the letter $n$, not an arbitrary subgroup restriction. Since this embedding is fixed, the adjoint operation is induction from $S_{n-1}$ back to $S_n$, and the corresponding combinatorics is adding one box. [quotetheorem:8444] [citeproof:8444] The two formulas are dual descriptions of the same edges in Young's lattice. Restriction reads the graph downward; induction reads it upward. The direct-sum statement again uses semisimplicity over characteristic zero, since [Frobenius reciprocity](/theorems/2449) by itself computes multiplicities only after the relevant modules decompose into irreducibles. In modular representation theory the same addable boxes still indicate the expected Specht-filtration factors, but extensions between factors may remain, so the graph no longer gives a complete decomposition. The fixed embedding also matters here: inducing from a different copy of $S_{n-1}$ gives an isomorphic result only after conjugating the subgroup inside $S_n$. [example: Restricting The Specht Module Of Shape Three Two] For $\lambda=(3,2)$, the Young diagram has boxes in row $1$ at columns $1,2,3$ and in row $2$ at columns $1,2$. The removable boxes are exactly $(1,3)$ and $(2,2)$: deleting $(1,3)$ changes the row lengths to $(2,2)$, while deleting $(2,2)$ changes the row lengths to $(3,1)$. Thus the partitions $\mu$ with $\mu \nearrow (3,2)$ are precisely $(2,2)$ and $(3,1)$. Applying *[Young Branching Rule For Restriction](/theorems/8443)* with $n=5$ and $\lambda=(3,2)$ gives \begin{align*} \operatorname{Res}^{S_5}_{S_4} S^{(3,2)} \cong \bigoplus_{\mu \nearrow (3,2)} S^\mu. \end{align*} Substituting the two removable-box shapes into this sum gives \begin{align*} \bigoplus_{\mu \nearrow (3,2)} S^\mu = S^{(2,2)} \oplus S^{(3,1)}. \end{align*} Therefore \begin{align*} \operatorname{Res}^{S_5}_{S_4} S^{(3,2)} \cong S^{(2,2)} \oplus S^{(3,1)}. \end{align*} Each summand corresponds to one removable corner of $(3,2)$, so the restriction is multiplicity-free and no other partition of $4$ appears. [/example] Characters give another way to see why the same graph appears. For each $n$, the Frobenius characteristic is the linear map \begin{align*} \operatorname{ch}_n : \operatorname{Class}(S_n;\mathbb C) \to \Lambda^n_\mathbb C \end{align*} from complex-valued class functions on $S_n$ to the degree-$n$ component of the ring of symmetric functions, sending irreducible characters $\chi^\lambda$ to Schur functions $s_\lambda$. [remark: Frobenius Characteristic Bridge] Under the maps $\operatorname{ch}_n$, induction product corresponds to multiplication of symmetric functions and restriction is reflected by adjoint operators for the Hall [inner product](/page/Inner%20Product). The one-box branching rule matches the Pieri rule for multiplying by $s_{(1)}=h_1$. This is powerful because it says the same coefficients are being computed twice: once as representation-theoretic multiplicities and once as symmetric-function structure constants. In this chapter this correspondence is used as a bridge between earlier symmetric-function material and Specht-module branching, not as a construction of the irreducible modules. [/remark] This bridge explains why the same combinatorics was visible before representations entered the course. The next question is numerical: how many basis vectors, or standard tableaux, does each Specht module have? ## Hook Lengths and Specht Module Dimensions How can we compute $\dim S^\lambda$ without writing down the full polytabloid basis and its relations? Since standard tableaux index a natural basis after straightening, the dimension is the number $f^\lambda$ of standard Young tableaux of shape $\lambda$. The hook-length formula gives this number as a product over boxes. [definition: Hook Length] Let $\lambda$ be a partition and let $b$ be a box in its Young diagram. The hook of $b$ is the set consisting of $b$, the boxes strictly to the right of $b$ in the same row, and the boxes strictly below $b$ in the same column. The hook length $h(b)$ is the cardinality of this hook. [/definition] The hook length measures how much local freedom remains around a box. Larger hooks impose stronger ordering constraints in a standard tableau, and the product of all hook lengths gives the correction factor from $n!$ possible fillings to the increasing fillings. [quotetheorem:5213] [citeproof:5213] For Specht modules, the formula turns combinatorial data into representation dimensions, avoiding the unwieldy task of constructing all polytabloids and then quotienting by Garnir relations by hand. The characteristic-zero qualification in the dimension statement is used to identify these Specht modules with the irreducible representations in the semisimple representation category. The tableau count $f^\lambda$ itself is purely combinatorial and remains valid over any field, but over positive characteristic $S^\lambda$ may fail to be simple, so $f^\lambda$ is then the dimension of a Specht module rather than necessarily the dimension of an irreducible module. The formula also does not by itself describe character values or decomposition numbers; it gives only dimensions. It nevertheless gives a consistency check in characteristic zero: the sum of squared dimensions over all irreducibles of $S_n$ must equal $|S_n|=n!$. [example: Dimensions For Partitions Of Five] The partitions of $5$ are $(5)$, $(4,1)$, $(3,2)$, $(3,1,1)$, $(2,2,1)$, $(2,1,1,1)$, and $(1,1,1,1,1)$. We compute each dimension from the hook lengths using *Hook Length Formula*, namely $f^\lambda=5!/\prod_{b\in\lambda}h(b)$. For the one-row shape $(5)$, the hook lengths are $5,4,3,2,1$, so \begin{align*} \prod_{b\in(5)}h(b)=5\cdot4\cdot3\cdot2\cdot1=120. \end{align*} Thus \begin{align*} f^{(5)}=\frac{5!}{120}=\frac{120}{120}=1. \end{align*} For $(4,1)$, the hook lengths are $5,3,2,1,1$: the first box has three boxes to its right and one below it, while the remaining boxes have hooks of lengths $3,2,1,1$. Hence \begin{align*} \prod_{b\in(4,1)}h(b)=5\cdot3\cdot2\cdot1\cdot1=30. \end{align*} Thus \begin{align*} f^{(4,1)}=\frac{5!}{30}=\frac{120}{30}=4. \end{align*} For $(3,2)$, the hook lengths are $4,3,1,2,1$, so \begin{align*} \prod_{b\in(3,2)}h(b)=4\cdot3\cdot1\cdot2\cdot1=24. \end{align*} Thus \begin{align*} f^{(3,2)}=\frac{5!}{24}=\frac{120}{24}=5. \end{align*} For $(3,1,1)$, the hook lengths are $5,2,1,2,1$, so \begin{align*} \prod_{b\in(3,1,1)}h(b)=5\cdot2\cdot1\cdot2\cdot1=20. \end{align*} Thus \begin{align*} f^{(3,1,1)}=\frac{5!}{20}=\frac{120}{20}=6. \end{align*} For $(2,2,1)$, the hook lengths are $4,2,3,1,1$, so \begin{align*} \prod_{b\in(2,2,1)}h(b)=4\cdot2\cdot3\cdot1\cdot1=24. \end{align*} Thus \begin{align*} f^{(2,2,1)}=\frac{5!}{24}=\frac{120}{24}=5. \end{align*} For $(2,1,1,1)$, the hook lengths are $5,1,3,2,1$, so \begin{align*} \prod_{b\in(2,1,1,1)}h(b)=5\cdot1\cdot3\cdot2\cdot1=30. \end{align*} Thus \begin{align*} f^{(2,1,1,1)}=\frac{5!}{30}=\frac{120}{30}=4. \end{align*} For the one-column shape $(1,1,1,1,1)$, the hook lengths are $5,4,3,2,1$, so \begin{align*} \prod_{b\in(1,1,1,1,1)}h(b)=5\cdot4\cdot3\cdot2\cdot1=120. \end{align*} Thus \begin{align*} f^{(1,1,1,1,1)}=\frac{5!}{120}=\frac{120}{120}=1. \end{align*} The resulting dimensions are therefore $1,4,5,6,5,4,1$. Their squared sum is \begin{align*} 1^2+4^2+5^2+6^2+5^2+4^2+1^2=1+16+25+36+25+16+1=120. \end{align*} Since $5!=120$, these dimensions satisfy the expected identity $\sum_{\lambda\vdash 5}(\dim S^\lambda)^2=|S_5|$, matching the complete characteristic-zero list of irreducible $S_5$-modules. [/example] The symmetry of the table reflects conjugating partitions. Tensoring a Specht module with the sign representation sends $S^\lambda$ to $S^{\lambda'}$, so conjugate shapes have the same dimension. [remark: Dimension Symmetry Under Conjugation] If $\lambda'$ denotes the conjugate partition, then the multiset of hook lengths of $\lambda'$ is the same as the multiset of hook lengths of $\lambda$. Hence the hook-length formula gives $f^{\lambda'}=f^\lambda$. Representation-theoretically, this matches $S^{\lambda'}\cong S^\lambda\otimes \operatorname{sgn}$. [/remark] The chapter's main lesson is that the local geometry of Young diagrams controls both structural and numerical information. Removing and adding boxes give restriction and induction, while hook lengths compress the global count of standard tableaux into a product formula. These tools will be used repeatedly when the course moves from ordinary Specht modules to richer structures such as tableaux algorithms, crystals, and Hecke algebra representations. Once dimensions and branching rules are known, the remaining task is to understand how basis vectors transform under the generators of `S_n`. The next chapter does this by introducing seminormal forms and Jucys-Murphy elements, which diagonalize the tableau basis and make the branching picture explicit. # 5. Seminormal Forms and Jucys-Murphy Elements This chapter builds on the Specht modules and standard tableau bases of Chapter 3, together with the branching rule of Chapter 4 for restriction along \begin{align*} S_1 \subset S_2 \subset \cdots \subset S_n, \end{align*} and [Schur's lemma](/theorems/2414) over $\mathbb C$. It turns Specht modules from abstract quotients into modules with a highly computable basis. The guiding question is how the position of entries in a standard tableau records enough spectral data to recover the tableau and to control the adjacent transpositions. The answer is supplied by the Jucys-Murphy elements: a commuting family in the group algebra of $S_n$ whose eigenvalues are the contents of the boxes occupied by $1,\dots,n$. ## Contents of Boxes and Standard Tableau Bases Specht modules have bases indexed by standard tableaux, but a basis label is useful only if the representation can read it internally. The first problem is to attach numerical data to a tableau that behaves well under adding boxes one at a time. [definition: Content of a Box] Let $\lambda$ be a partition, and let $b$ be the box in row $i$ and column $j$ of the Young diagram of $\lambda$. The content of $b$ is \begin{align*} \operatorname{ct}(b) = j-i. \end{align*} [/definition] Contents measure diagonals of the Young diagram: boxes on the same northwest-to-southeast diagonal have the same content. This is the numerical datum that appears in the seminormal form, so we next attach it to entries of a tableau rather than just boxes. [definition: Content Sequence] Let $\lambda \vdash n$, and let $\operatorname{SYT}(\lambda)$ be the set of standard tableaux of shape $\lambda$. The content sequence map is \begin{align*} c: \operatorname{SYT}(\lambda) \longrightarrow \mathbb Z^n. \end{align*} For $T \in \operatorname{SYT}(\lambda)$ and $1 \le k \le n$, let $b_T(k)$ be the box containing $k$, and define \begin{align*} c(T) = (c_1(T),\dots,c_n(T)), \qquad c_k(T)=\operatorname{ct}(b_T(k)). \end{align*} [/definition] The content sequence records the order in which the boxes of the final Young diagram are added along the path of shapes \begin{align*} \varnothing = \lambda^{(0)} \subset \lambda^{(1)} \subset \cdots \subset \lambda^{(n)}=\lambda, \end{align*} where $\lambda^{(k)}$ is the shape occupied by $1,\dots,k$ in $T$. To use these numbers as spectral labels, we need to know that two different standard tableaux cannot produce the same list of contents. [quotetheorem:8445] [citeproof:8445] This theorem is the spectral reason the seminormal basis can be labelled by standard tableaux. The standardness hypothesis matters: if arbitrary fillings were allowed, the same list of occupied diagonal contents would not determine a legal path of Young diagrams, because entries could be placed in an order that violates row or column increase. For instance, in the shape $(2,1)$, put $1$ in the lower-left box, $2$ in the upper-left box, and $3$ in the upper-right box. Its ordered content sequence is $(-1,0,1)$, the same as the standard tableau with top row $1,3$ and lower-left entry $2$, but the filling is not standard because the first column decreases from $2$ to $1$. The common-size hypothesis also matters, since a shorter tableau can share an initial segment of a longer content sequence without being the same object. The theorem does not say that a multiset of contents determines a tableau; for shape $(2,1)$ the two standard tableaux have the same multiset $\{-1,0,1\}$ but different ordered content sequences. What it gives is precisely the uniqueness needed later: once the Jucys-Murphy operators supply the ordered eigenvalue list, a simultaneous eigenline has at most one tableau label. [example: Contents for Shape Two One] For the Young diagram of shape $(2,1)$, the upper-left box has row $1$ and column $1$, the upper-right box has row $1$ and column $2$, and the lower-left box has row $2$ and column $1$. By the definition of content, $\operatorname{ct}(b)=j-i$, so these three contents are \begin{align*} 1-1=0,\qquad 2-1=1,\qquad 1-2=-1. \end{align*} Let $T_1$ have top row $1,2$ and lower-left entry $3$. Then $1$ lies in the upper-left box, $2$ lies in the upper-right box, and $3$ lies in the lower-left box, hence \begin{align*} c_1(T_1)=0,\qquad c_2(T_1)=1,\qquad c_3(T_1)=-1. \end{align*} Therefore \begin{align*} c(T_1)=(0,1,-1). \end{align*} Let $T_2$ have top row $1,3$ and lower-left entry $2$. Then $1$ lies in the upper-left box, $2$ lies in the lower-left box, and $3$ lies in the upper-right box, hence \begin{align*} c_1(T_2)=0,\qquad c_2(T_2)=-1,\qquad c_3(T_2)=1. \end{align*} Therefore \begin{align*} c(T_2)=(0,-1,1). \end{align*} The two content sequences differ in their second and third entries, so these two standard tableaux of shape $(2,1)$ are separated by their ordered content sequences. [/example] ## Jucys-Murphy Elements as Commuting Operators The next question is how to produce the content sequence from the group algebra itself. We want elements of $\mathbb C[S_n]$ that commute with each other, act naturally under the chain $S_1 \subset S_2 \subset \cdots \subset S_n$, and detect where each new entry is added. [definition: Jucys-Murphy Element] For $1 \le k \le n$, the $k$-th Jucys-Murphy element in $\mathbb C[S_n]$ is \begin{align*} X_1=0, \qquad X_k=\sum_{i=1}^{k-1} (i\ k) \quad \text{for } 2\le k\le n. \end{align*} [/definition] The element $X_k$ is built from transpositions that move the newest letter $k$ past earlier letters. When $M$ is any $\mathbb C[S_n]$-module, $X_k$ acts on $M$ through the representation action of the group algebra, so the same symbol denotes both the algebra element and its induced linear operator. Its definition is compatible with the subgroup chain, since $X_k$ belongs to $\mathbb C[S_k]$ and is invariant under conjugation by $S_{k-1}$. The next issue is whether these elements can be diagonalized together; for that, commutativity is the essential algebraic input. [quotetheorem:8446] [citeproof:8446] Commutativity lets the $X_k$ be studied simultaneously on any semisimple $S_n$-module. The special triangular definition of $X_k$ is essential: arbitrary sums of transpositions need not commute, for instance $(1\ 2)(2\ 3) \ne (2\ 3)(1\ 2)$ in $S_3$. The theorem does not by itself prove diagonalizability or identify eigenvalues; it only supplies the commutative algebra whose spectrum can then be studied. Since we work over characteristic zero, the group algebra is semisimple, and the next task is to identify the scalars by which these commuting elements act on the branching lines of Specht modules. [remark: Gelfand-Tsetlin Viewpoint] The algebra generated by $X_1,\dots,X_n$ is the Gelfand-Tsetlin subalgebra for the subgroup chain $S_1 \subset S_2 \subset \cdots \subset S_n$. Its simultaneous eigenvectors are adapted to the multiplicity-free branching of Specht modules under restriction. [/remark] This viewpoint explains what remains to be computed: the scalar by which $X_k$ acts on the line corresponding to a step in the branching chain. Commutativity alone is not enough: a commuting family could have repeated eigenvalues, and then its eigenspaces would not remember which removable box was chosen. For example, the identity operator commutes with everything but separates no tableau labels at all. Restricting $S^\lambda$ to $S_{n-1}$ decomposes into Specht modules indexed by removing a single corner box from $\lambda$, so the desired scalar must distinguish the removed box rather than merely exist abstractly. [quotetheorem:8447] [citeproof:8447] The theorem turns contents into observable eigenvalues. The hypotheses are doing real work. In characteristic $2$, the regular module for $S_2$ has $X_2=(1\ 2)$ satisfying $(X_2-1)^2=0$, so $X_2$ is not diagonalizable on that module even though it has only the eigenvalue $1$. Thus the characteristic-zero semisimplicity used in the branching argument cannot be dropped. Replacing one Specht module by an arbitrary reducible module also changes the conclusion: on $S^\lambda\oplus S^\lambda$, every content eigenline appears twice, so the content data no longer singles out a one-dimensional line. The result also does not yet say how a group element such as an adjacent transposition acts; it only diagonalizes the commuting Jucys-Murphy family. Together with content separation, it prepares the one-dimensional tableau lines on which the seminormal formulas for the generators will be written. [example: Eigenvalues for a Tableau of Shape Three Two] Let $T$ have first row $1,2,5$ and second row $3,4$. The box containing $1$ is in row $1$ and column $1$, so its content is \begin{align*} c_1(T)=1-1=0. \end{align*} The box containing $2$ is in row $1$ and column $2$, so \begin{align*} c_2(T)=2-1=1. \end{align*} The box containing $3$ is in row $2$ and column $1$, so \begin{align*} c_3(T)=1-2=-1. \end{align*} The box containing $4$ is in row $2$ and column $2$, so \begin{align*} c_4(T)=2-2=0. \end{align*} The box containing $5$ is in row $1$ and column $3$, so \begin{align*} c_5(T)=3-1=2. \end{align*} Thus \begin{align*} c(T)=(0,1,-1,0,2). \end{align*} By *Content Eigenvalues*, each Jucys-Murphy element acts on the seminormal vector $v_T$ by the corresponding content: \begin{align*} X_1v_T=c_1(T)v_T=0v_T=0. \end{align*} Also, \begin{align*} X_2v_T=c_2(T)v_T=1v_T=v_T. \end{align*} For the third entry, \begin{align*} X_3v_T=c_3(T)v_T=(-1)v_T=-v_T. \end{align*} For the fourth entry, \begin{align*} X_4v_T=c_4(T)v_T=0v_T=0. \end{align*} For the fifth entry, \begin{align*} X_5v_T=c_5(T)v_T=2v_T. \end{align*} The ordered joint eigenvalue list is therefore $(0,1,-1,0,2)$, so the seminormal vector records exactly the contents of the boxes occupied by $1,2,3,4,5$ in this tableau. [/example] ## Young Seminormal Representation and Diagonalization by Contents The final problem is to determine how the adjacent transpositions $s_i=(i\ i+1)$ act in the content eigenbasis. Since $s_i$ only exchanges the labels $i$ and $i+1$, its action should involve at most the two tableaux $T$ and $s_iT$ when the exchanged filling remains standard. The adjacent transposition $s_i$ only interacts with the two boxes containing $i$ and $i+1$. To turn that geometric relation into a coefficient in a matrix, we need a signed measure of how far those boxes lie from one another along diagonals. This is the role of the axial distance. [definition: Axial Distance] Let $\lambda \vdash n$ and $1\le i<n$. The $i$-th axial distance map is \begin{align*} r_i: \operatorname{SYT}(\lambda) \longrightarrow \mathbb Z. \end{align*} For $T \in \operatorname{SYT}(\lambda)$, the axial distance between $i$ and $i+1$ is \begin{align*} r_i(T)=c_{i+1}(T)-c_i(T). \end{align*} [/definition] The value $r_i(T)$ measures the diagonal displacement between consecutive labels. Without this displacement, the generator formula would have no way to distinguish the row case, the column case, and the genuine two-tableau case. For instance, in shape $(2,1)$ the pair $(1,2)$ may be in the same row for one tableau and in the same column for the other, forcing eigenvalues $1$ and $-1$ for the same generator $s_1$. [remark: Seminormal Normalization] In a seminormal basis adapted to the Jucys-Murphy spectrum, the diagonal coefficient of $s_i$ on the basis vector indexed by $T$ is governed by $1/r_i(T)$. If $s_iT$ is not standard, there is no second basis vector in that adjacent-generator block, and the row and column cases give the familiar eigenvalues $1$ and $-1$. If $s_iT$ is standard, the two-dimensional block may be normalized in several equivalent ways; changing signs or phases of basis vectors changes the off-diagonal coefficients while leaving the representation unchanged. For that reason this discussion records the computational convention used below rather than treating a phase-dependent displayed formula as a separate theorem card. [/remark] The field and normalization hypotheses also matter. Orthogonal seminormal forms may require square roots, while modular characteristic can break the spectral construction before the adjacent-generator formula is reached. Even over $\mathbb C$, a phrase such as "positive square root" depends on the chosen real normalization of the orthogonal basis. The special row and column cases recover the ordinary Specht relations: adjacent entries in the same row give eigenvalue $1$, while adjacent entries in the same column give eigenvalue $-1$. The two-tableau case gives the computational block used below to build explicit generator matrices. [example: Seminormal Action on Shape Two One] Use the ordered basis $v_{T_1},v_{T_2}$ for $S^{(2,1)}$, where the earlier content computation gives \begin{align*} c(T_1)=(0,1,-1),\qquad c(T_2)=(0,-1,1). \end{align*} Thus the Jucys-Murphy eigenvalues on these basis vectors are these ordered triples, by *Content Eigenvalues*. For $s_1=(1\ 2)$, the tableau $T_1$ has entries $1$ and $2$ in the same row, so swapping them would put $2$ before $1$ in that row and would not be standard. Its axial distance is \begin{align*} r_1(T_1)=c_2(T_1)-c_1(T_1)=1-0=1. \end{align*} By the nonstandard case of the seminormal action formula, \begin{align*} s_1v_{T_1}=\frac{1}{r_1(T_1)}v_{T_1}=\frac{1}{1}v_{T_1}=v_{T_1}. \end{align*} For $T_2$, the entries $1$ and $2$ lie in the same column, so swapping them would put $2$ above $1$ in that column and would not be standard. Here \begin{align*} r_1(T_2)=c_2(T_2)-c_1(T_2)=(-1)-0=-1. \end{align*} Therefore \begin{align*} s_1v_{T_2}=\frac{1}{r_1(T_2)}v_{T_2}=\frac{1}{-1}v_{T_2}=-v_{T_2}. \end{align*} For $s_2=(2\ 3)$, swapping $2$ and $3$ sends $T_1$ to $T_2$ and sends $T_2$ to $T_1$. The axial distance for $T_1$ is \begin{align*} r_2(T_1)=c_3(T_1)-c_2(T_1)=(-1)-1=-2. \end{align*} Hence \begin{align*} \frac{1}{r_2(T_1)}=-\frac{1}{2},\qquad \sqrt{1-r_2(T_1)^{-2}}=\sqrt{1-(-2)^{-2}}=\sqrt{1-\frac{1}{4}}=\sqrt{\frac{3}{4}}=\frac{\sqrt{3}}{2}. \end{align*} By the standard two-tableau case of the seminormal action formula, \begin{align*} s_2v_{T_1}=-\frac{1}{2}v_{T_1}+\frac{\sqrt{3}}{2}v_{T_2}. \end{align*} Similarly, \begin{align*} r_2(T_2)=c_3(T_2)-c_2(T_2)=1-(-1)=2. \end{align*} Thus \begin{align*} \frac{1}{r_2(T_2)}=\frac{1}{2},\qquad \sqrt{1-r_2(T_2)^{-2}}=\sqrt{1-2^{-2}}=\sqrt{1-\frac{1}{4}}=\frac{\sqrt{3}}{2}. \end{align*} Therefore \begin{align*} s_2v_{T_2}=\frac{\sqrt{3}}{2}v_{T_1}+\frac{1}{2}v_{T_2}. \end{align*} In the ordered basis $(v_{T_1},v_{T_2})$, the columns recording $s_1v_{T_1}$ and $s_1v_{T_2}$ are $(1,0)$ and $(0,-1)$, while the columns recording $s_2v_{T_1}$ and $s_2v_{T_2}$ are $(-\frac{1}{2},\frac{\sqrt{3}}{2})$ and $(\frac{\sqrt{3}}{2},\frac{1}{2})$. This realizes the two-dimensional Specht module $S^{(2,1)}$ in a basis where $X_1,X_2,X_3$ are diagonal and the adjacent transpositions are recovered from the content differences. [/example] ## Consequences for Branching and Computation The seminormal form is not only a formula for generators; it gives an algorithmic model for all Specht modules. The remaining question is what structural information can be read directly from the Jucys-Murphy spectrum. [quotetheorem:8449] [citeproof:8449] This simple spectrum is the mechanism behind many tableau algorithms in representation theory. The restriction to a single Specht module is necessary: on $S^\lambda \oplus S^\lambda$, every simultaneous Jucys-Murphy eigenspace would have multiplicity two, even though the same content labels occur. The theorem also does not say that every operator on $S^\lambda$ is diagonal in the seminormal basis; adjacent transpositions usually mix the two tableau lines related by swapping $i$ and $i+1$. Operators or intertwiners compatible with the subgroup chain must respect the content labels, so their action is constrained by the combinatorics of standard tableaux and by the symmetric polynomials in the $X_k$ lying in the center. [remark: Why Contents Replace Characters Locally] Characters describe the trace of a group element on a whole module. Contents describe the eigenvalues of a commuting family on individual tableau lines. The two perspectives are compatible: central symmetric polynomials in the $X_k$ act by scalars on $S^\lambda$, while the individual $X_k$ refine that scalar action to the tableau basis. [/remark] A useful computational pattern is therefore: first diagonalize the Jucys-Murphy family using contents, then write the adjacent generators using the two-dimensional seminormal blocks. Since the adjacent transpositions generate $S_n$, this determines the representation. [example: Reconstructing Generator Matrices from Contents] For $S^{(2,1)}$, use the ordered seminormal basis $(v_{T_1},v_{T_2})$, with content labels \begin{align*} c(T_1)=(0,1,-1),\qquad c(T_2)=(0,-1,1). \end{align*} By *Content Eigenvalues*, $X_kv_T=c_k(T)v_T$. Therefore \begin{align*} X_1v_{T_1}=0v_{T_1},\qquad X_1v_{T_2}=0v_{T_2}. \end{align*} Thus $X_1$ is the diagonal operator with diagonal entries $0,0$. Similarly, \begin{align*} X_2v_{T_1}=1v_{T_1},\qquad X_2v_{T_2}=(-1)v_{T_2}, \end{align*} so $X_2$ has diagonal entries $1,-1$, and \begin{align*} X_3v_{T_1}=(-1)v_{T_1},\qquad X_3v_{T_2}=1v_{T_2}, \end{align*} so $X_3$ has diagonal entries $-1,1$. For $s_1=(1\ 2)$, the row-column cases from the seminormal action formula give \begin{align*} s_1v_{T_1}=v_{T_1},\qquad s_1v_{T_2}=-v_{T_2}. \end{align*} Hence the coordinate action of $s_1$ on a vector $av_{T_1}+bv_{T_2}$ is \begin{align*} s_1(av_{T_1}+bv_{T_2})=av_{T_1}-bv_{T_2}. \end{align*} For $s_2=(2\ 3)$, the two tableaux are exchanged by swapping $2$ and $3$. The axial distances are \begin{align*} r_2(T_1)=c_3(T_1)-c_2(T_1)=(-1)-1=-2 \end{align*} and \begin{align*} r_2(T_2)=c_3(T_2)-c_2(T_2)=1-(-1)=2. \end{align*} Thus the seminormal coefficients are \begin{align*} \frac{1}{r_2(T_1)}=-\frac{1}{2},\qquad \sqrt{1-r_2(T_1)^{-2}}=\sqrt{1-\frac{1}{4}}=\frac{\sqrt{3}}{2} \end{align*} and \begin{align*} \frac{1}{r_2(T_2)}=\frac{1}{2},\qquad \sqrt{1-r_2(T_2)^{-2}}=\sqrt{1-\frac{1}{4}}=\frac{\sqrt{3}}{2}. \end{align*} Therefore \begin{align*} s_2v_{T_1}=-\frac{1}{2}v_{T_1}+\frac{\sqrt{3}}{2}v_{T_2} \end{align*} and \begin{align*} s_2v_{T_2}=\frac{\sqrt{3}}{2}v_{T_1}+\frac{1}{2}v_{T_2}. \end{align*} Consequently, on a general vector $av_{T_1}+bv_{T_2}$, \begin{align*} s_2(av_{T_1}+bv_{T_2})=\left(-\frac{a}{2}+\frac{\sqrt{3}b}{2}\right)v_{T_1}+\left(\frac{\sqrt{3}a}{2}+\frac{b}{2}\right)v_{T_2}. \end{align*} The operators $s_1$ and $s_2$ determine the whole $S_3$-representation because the adjacent transpositions $(1\ 2)$ and $(2\ 3)$ generate $S_3$; the Jucys-Murphy operators are then recovered as the diagonal content operators in this same basis. [/example] Seminormal forms turn the abstract Specht-module story into formulas that can be read directly from tableau contents. With that machinery in place, the next chapter returns to RSK and shows how the same insertion combinatorics controls representation-theoretic decompositions of symmetric groups. # 6. Robinson-Schensted and Representation Theory This chapter connects the Robinson--Schensted correspondence with representation theory of the symmetric group. It assumes the earlier construction of standard Young tableaux, Specht modules for $S_n$, and the RSK correspondence for permutations. Earlier chapters built tableaux as combinatorial models for Specht modules; here the same tableaux explain the size and labelling of the regular representation of $S_n$. The guiding point is that RSK does not only count permutations: it separates insertion and recording data in a way that mirrors basis and multiplicity labels, though not literally as invariant spans in the original permutation basis. ## Cells from Insertion and Recording Tableaux How can a permutation remember enough tableau data to locate a copy of an irreducible representation? RSK assigns to each $w \in S_n$ a pair $(P(w), Q(w))$ of standard Young tableaux of the same shape. The insertion tableau records the Knuth-equivalence class of the word $w_1\cdots w_n$, while the recording tableau records the order in which boxes were created. [definition: RSK Shape] The RSK shape map is the function \begin{align*} \operatorname{sh}: S_n \longrightarrow \{\lambda : \lambda \vdash n\} \end{align*} defined by \begin{align*} \operatorname{sh}(w)=\operatorname{sh}(P(w)), \end{align*} where $\operatorname{RSK}(w)=(P(w),Q(w))$ and $\operatorname{sh}(P(w))=\operatorname{sh}(Q(w))$. [/definition] The shape is the coarsest datum in the correspondence, grouping together all permutations whose increasing subsequence structure has the same Young diagram. For representation theory this is still too coarse: in $S_3$, the identity has shape $(3)$, while a transposition has shape $(2,1)$, so shape cannot be preserved by arbitrary left multiplication in the permutation basis. What shape does provide is the correct dimension count for the isotypic component after passing to a representation-theoretic basis. This motivates keeping only $P(w)$ or only $Q(w)$ as a finer combinatorial partition of $S_n$, while remembering that cells are indexing devices here rather than literal invariant subspaces of the group basis. [definition: RSK Left and Right Cells] For a standard Young tableau $T$ of size $n$, define \begin{align*} L_T = \{w \in S_n : Q(w)=T\}. \end{align*} Define also \begin{align*} R_T = \{w \in S_n : P(w)=T\}. \end{align*} The sets $L_T$ are called RSK left cells, and the sets $R_T$ are called RSK right cells. [/definition] The convention reflects the group algebra action used below: left multiplication changes insertion data in a controlled representation-theoretic way, while recording data labels a copy of a Specht module. Since inverse permutations interchange the two rows of the permutation array, the first structural check is that the two cell notions are exchanged by inversion. [quotetheorem:8450] [citeproof:8450] This theorem uses the permutation hypothesis in an essential way: for a general word with repeated letters there is no inverse permutation, so the same symmetry statement is not even formulated without additional conventions. It does not say that left and right cells are invariant under left or right multiplication in $S_n$; it only identifies how the two tableau labels transform under inversion. The next example makes the definitions concrete in the first size where several non-hook shapes appear. [example: Cells in S Four] Consider $w=3142 \in S_4$, so the inserted word is $3,1,4,2$. Insert $3$: the insertion tableau has row $3$, and the recording tableau has row $1$. Insert $1$: since $1<3$, the entry $3$ is bumped from the first row, so $P$ has first row $1$ and second row $3$; the new box is in row $2$, column $1$, so $Q$ has first row $1$ and second row $2$. Insert $4$: since $4>1$, it is appended to the first row, giving first row $1,4$ and second row $3$ in $P$; the new box is in row $1$, column $2$, so $Q$ has first row $1,3$ and second row $2$. Insert $2$: in the first row $1,4$, the entry $4$ is the first entry larger than $2$, so $2$ replaces $4$ and $4$ is inserted into the second row; since $4>3$, it is appended there. Thus $P(w)$ has first row $1,2$ and second row $3,4$, while $Q(w)$ has first row $1,3$ and second row $2,4$. Both tableaux have shape $(2,2)$, so $\operatorname{sh}(w)=(2,2)$. By the definitions of right and left RSK cells, $w$ lies in the right cell labelled by the tableau with rows $1,2$ and $3,4$, and in the left cell labelled by the tableau with rows $1,3$ and $2,4$. To compute the inverse, the positions of $1,2,3,4$ in $3142$ are $2,4,1,3$, so $w^{-1}=2413$. The inverse symmetry theorem gives $P(w^{-1})=Q(w)$ and $Q(w^{-1})=P(w)$, so inversion exchanges the two cell labels in this example. [/example] Cells of fixed shape can now be counted without listing permutations. If $f_\lambda$ denotes the number of standard Young tableaux of shape $\lambda$, then there are $f_\lambda$ left cells and $f_\lambda$ right cells of shape $\lambda$, each of size $f_\lambda$. The next theorem records the exact count needed for comparison with the regular representation. [quotetheorem:8451] [citeproof:8451] The restriction to one fixed shape is necessary: if shapes are mixed, the count becomes a sum of several squares rather than a single square. For instance, in $S_3$ the shapes $(3)$, $(2,1)$, and $(1,1,1)$ contribute $1^2$, $2^2$, and $1^2$ permutations respectively, giving \begin{align*} 1^2+2^2+1^2=6 \end{align*} permutations in total. The theorem does not identify an invariant subspace of the left regular action in the permutation basis; left multiplication can move a permutation from one RSK shape to another. What it does provide is the same square pattern that appears in the regular representation decomposition, where irreducibles occur with multiplicity equal to their dimension. ## The Regular Representation by RSK Shape What does RSK know about the group algebra $\mathbb C[S_n]$? The group algebra carries commuting left and right actions of $S_n$: left multiplication by $g$ sends $e_w$ to $e_{gw}$, and right multiplication by $h$ sends $e_w$ to $e_{wh^{-1}}$. Decomposing $\mathbb C[S_n]$ as a bimodule reveals why pairs of tableaux occur. [definition: Regular Bimodule of S n] The regular bimodule of $S_n$ is $\mathbb C[S_n]$ with basis $\{e_w : w \in S_n\}$ and module action map \begin{align*} S_n \times S_n \longrightarrow GL(\mathbb C[S_n]) \end{align*} given by \begin{align*} (g,h)\cdot e_w=e_{gwh^{-1}}. \end{align*} [/definition] The left action alone gives the usual regular representation, while the right action records multiplicity spaces. To compare this with RSK, we first need the ordinary [irreducible decomposition](/theorems/2122) of the left regular representation. That decomposition fixes the target that the left-cell model must realize. [quotetheorem:8452] [citeproof:8452] The hypotheses here matter in two ways. Working over $\mathbb C$ is what makes Maschke's theorem immediately applicable; over a field whose characteristic divides $n!$, the group algebra need not be semisimple. The theorem also does not specify the summands as spans of particular permutations, so it should not be read as saying that RSK shape classes are stable under left multiplication. RSK supplies the matching combinatorics, while the actual invariant summands come from the semisimple decomposition or an equivalent system of matrix units. Combining the fixed-shape RSK count with the regular representation decomposition gives the guiding dictionary for this chapter. For a fixed partition $\lambda$, the permutations of RSK shape $\lambda$ are labelled by pairs of standard tableaux of shape $\lambda$, while the $\lambda$-isotypic component of the left regular representation has dimension $(f_\lambda)^2$ and can be arranged as a Specht factor together with a multiplicity space of dimension $f_\lambda$. This is a dimension-and-indexing dictionary, not an equality of the ordinary permutation basis with a Specht matrix-unit basis. For example, in $S_n$ the identity permutation has one-row RSK shape, but left multiplication by a transposition gives a permutation of shape $(n-1,1)$; therefore the span of fixed-shape permutations is not a left submodule in the ordinary permutation basis. RSK supplies the two tableau labels whose sizes match the basis and multiplicity labels in the regular representation, while the actual invariant summands come from the semisimple decomposition. [example: Shape Decomposition for S Four] For $S_4$, the partitions are $(4)$, $(3,1)$, $(2,2)$, $(2,1,1)$, and $(1,1,1,1)$. The numbers of standard Young tableaux of these shapes are $1,3,2,3,1$: the shapes $(4)$ and $(1,1,1,1)$ each have only one increasing filling; shape $(3,1)$ has the entry below the first box equal to $2$, $3$, or $4$; shape $(2,2)$ has the two fillings with rows $1,2$ and $3,4$, or rows $1,3$ and $2,4$; and shape $(2,1,1)$ is the transpose of shape $(3,1)$, so it also has $3$ fillings. Using the regular-representation decomposition, with multiplicity equal to the Specht-module dimension $f_\lambda$, we get \begin{align*} \mathbb C[S_4] \cong S^{(4)} \oplus (S^{(3,1)})^{\oplus 3} \oplus (S^{(2,2)})^{\oplus 2} \oplus (S^{(2,1,1)})^{\oplus 3} \oplus S^{(1,1,1,1)}. \end{align*} The dimension contribution of each isotypic piece is multiplicity times Specht dimension, so the five contributions are \begin{align*} 1\cdot 1=1. \end{align*} \begin{align*} 3\cdot 3=9. \end{align*} \begin{align*} 2\cdot 2=4. \end{align*} \begin{align*} 3\cdot 3=9. \end{align*} \begin{align*} 1\cdot 1=1. \end{align*} Adding them gives \begin{align*} 1+9+4+9+1=24. \end{align*} Since \begin{align*} |S_4|=4!=4\cdot 3\cdot 2\cdot 1=24, \end{align*} the decomposition has the correct total dimension. The same numbers also match the [RSK shape count](/theorems/8451), because the shape-$\lambda$ fibre has size $(f_\lambda)^2$, so the five shape fibres have sizes $1^2,3^2,2^2,3^2,1^2$. The three standard tableaux of shape $(3,1)$ should therefore be understood as multiplicity labels after decomposing the regular representation, not as three fixed permutation-basis spans stable under left multiplication. [/example] The regular representation is the most intrinsic representation of $S_n$. To see where the same Specht modules appear in a larger linear-algebraic setting, we next pass to tensor space. ## Tensor Space and the Schur-Weyl Shadow Why do tableaux also control tensor powers such as $(\mathbb C^d)^{\otimes n}$? Two groups act on this space: $GL_d(\mathbb C)$ changes the vectors in each tensor factor, while $S_n$ permutes tensor positions. These actions commute, so each side measures the multiplicities for the other. [definition: Tensor Space Actions] Let $V=\mathbb C^d$. The diagonal tensor representation is the homomorphism $\rho:GL_d(\mathbb C)\to GL(V^{\otimes n})$ given by \begin{align*} \rho(g)(v_1\otimes \cdots \otimes v_n)=gv_1\otimes \cdots \otimes gv_n. \end{align*} The left place-permutation representation is the homomorphism $\pi:S_n\to GL(V^{\otimes n})$ given by \begin{align*} \pi(w)(v_1\otimes \cdots \otimes v_n)=v_{w^{-1}(1)}\otimes \cdots \otimes v_{w^{-1}(n)}. \end{align*} [/definition] The two actions commute because changing each vector and permuting positions are independent operations. Once two actions commute, the natural question is whether each action accounts for all linear operators commuting with the other. The answer is the double centralizer statement, which is the structural reason a simultaneous decomposition exists. [quotetheorem:8453] This theorem is stated here as structural background. The bound $d \ge n$ ensures that the place-permutation representation of $S_n$ is faithful. When $d<n$, antisymmetrizing in $d+1$ tensor positions kills $V^{\otimes n}$, so the map $\mathbb C[S_n]\to \operatorname{End}_{\mathbb C}(V^{\otimes n})$ has a kernel; the centralizer statement should then be read in terms of the image algebra $B$, not as an identification of $B$ with the whole group algebra. The theorem does not by itself name the irreducible summands; it only says that the two commuting actions control each other's multiplicities. Since the $S_n$-side uses Specht modules, we need the corresponding irreducible objects for the $GL_d$-side before stating the decomposition. [definition: Schur Module] For a partition $\lambda$ with at most $d$ parts, the Schur module $\mathbb S_\lambda(\mathbb C^d)$ is the irreducible polynomial representation of $GL_d(\mathbb C)$ of highest weight $\lambda$. [/definition] Schur modules are the $GL_d$ counterparts of Specht modules, and their characters are Schur functions in $d$ variables. The next question is how the commuting $GL_d(\mathbb C)$- and $S_n$-actions decompose the whole tensor space at once. This motivates the [Schur-Weyl decomposition](/theorems/8454), where each partition labels one matched pair of irreducibles. [quotetheorem:8454] This result is not part of this chapter's main development; the course uses the statement as a template for the way tableaux organize simultaneous decompositions. The condition $\ell(\lambda)\le d$ is necessary: if $\lambda$ has more than $d$ rows, the corresponding alternating construction forces $d+1$ vectors in $\mathbb C^d$ to be linearly dependent, so $\mathbb S_\lambda(V)$ vanishes. The theorem does not say that every Specht module appears for every $d$; it says precisely which shapes survive in tensor space. [example: Decomposing C Two Tensor Cubed] Let $V=\mathbb C^2$ and $n=3$. The partitions of $3$ are $(3)$, $(2,1)$, and $(1,1,1)$, and the condition $\ell(\lambda)\le 2$ removes only $(1,1,1)$. Thus *Schur-Weyl Decomposition* gives \begin{align*} (\mathbb C^2)^{\otimes 3} \cong \mathbb S_{(3)}(\mathbb C^2)\otimes S_{(3)} \oplus \mathbb S_{(2,1)}(\mathbb C^2)\otimes S_{(2,1)}. \end{align*} The Schur module $\mathbb S_{(3)}(\mathbb C^2)$ is $\operatorname{Sym}^3(\mathbb C^2)$, with basis represented by the four degree-$3$ monomials $x^3,x^2y,xy^2,y^3$, so $\dim \mathbb S_{(3)}(\mathbb C^2)=4$. The Specht module $S_{(3)}$ is the trivial representation of $S_3$, so $\dim S_{(3)}=1$. For shape $(2,1)$, the Schur module $\mathbb S_{(2,1)}(\mathbb C^2)$ has highest weight $(2,1)$, equivalently $\det\otimes \mathbb C^2$, and tensoring by the one-dimensional determinant character does not change dimension; hence $\dim \mathbb S_{(2,1)}(\mathbb C^2)=2$. The Specht dimension is the number of standard tableaux of shape $(2,1)$, namely the two tableaux with rows $1,2$ above $3$ or rows $1,3$ above $2$, so $\dim S_{(2,1)}=2$. Taking dimensions of the two direct-sum terms gives \begin{align*} \dim\bigl(\mathbb S_{(3)}(\mathbb C^2)\otimes S_{(3)}\bigr)=4\cdot 1=4. \end{align*} \begin{align*} \dim\bigl(\mathbb S_{(2,1)}(\mathbb C^2)\otimes S_{(2,1)}\bigr)=2\cdot 2=4. \end{align*} Therefore \begin{align*} 4+4=8. \end{align*} On the other hand, \begin{align*} \dim\bigl((\mathbb C^2)^{\otimes 3}\bigr)=2^3=8. \end{align*} The two surviving Schur-Weyl summands therefore account for the full tensor space, while the missing shape $(1,1,1)$ is excluded exactly because it has three rows and $V$ has dimension $2$. [/example] This example shows the same pattern as the regular representation, but with a restriction on allowable shapes caused by the dimension $d$. In the regular representation every partition of $n$ appears with multiplicity $f_\lambda$; in tensor space, the multiplicity of $S_\lambda$ is instead the dimension of the Schur module $\mathbb S_\lambda(\mathbb C^d)$. The final remark records the common principle that will guide the later crystal and Hecke-algebra chapters. [remark: From RSK to Schur-Weyl] RSK, the regular representation, and Schur-Weyl duality all express the same organizing principle: tableaux separate basis data from multiplicity data. In $\mathbb C[S_n]$, the pair $(P,Q)$ consists of two standard tableaux of the same shape. In tensor space, semistandard tableaux of bounded height encode the $GL_d$ side, while standard tableaux encode the $S_n$ side. [/remark] The chapter therefore closes the first arc of the course. Insertion began as an algorithm on words, became a bijection for permutations, and now supplies the indexing system for irreducible pieces of natural representations. RSK has now appeared both as a bijection and as an organizing principle for irreducible pieces, so the course can widen its scope without changing its combinatorial vocabulary. The next chapter moves to crystal graphs of type A, where tableaux and words again encode representation theory, now for quantum-group modules rather than symmetric-group modules. # 7. Crystal Graphs of Type A Crystal graphs give a combinatorial shadow of representations of quantum groups, retaining enough structure to see weights, tensor products, and highest weight decompositions without choosing bases in a vector space. In type $A$, the vertices can be realised by words or by semistandard Young tableaux, and the arrows are controlled by Kashiwara operators. This chapter turns the tableau technology from earlier chapters into a representation-theoretic graph calculus and ends with the crystal form of the Littlewood--Richardson rule. ## Kashiwara Operators on Words and Semistandard Tableaux The first problem is to define raising and lowering operations on a word that behave like the Chevalley generators for $\mathfrak{sl}_n$, while remaining purely combinatorial. Since type $A_{n-1}$ has simple roots indexed by the adjacent pairs $(i,i+1)$, each operator should inspect only the letters $i$ and $i+1$ and ignore the rest of the alphabet. [definition: Type A Word Crystal] Let $n \ge 2$. The type $A_{n-1}$ word crystal of length $r$ has vertex set $\{1,\dots,n\}^r$. The weight of a word $w=w_1\cdots w_r$ is $\operatorname{wt}(w)=(m_1,\dots,m_n)$, where $m_j=|\{k : w_k=j\}|$. For each $i\in\{1,\dots,n-1\}$, the Kashiwara operators are partial maps \begin{align*} e_i,f_i : \{1,\dots,n\}^r \rightharpoonup \{1,\dots,n\}^r \end{align*} constructed by the $i$-signature rule. [/definition] To compute these partial maps, keep only the letters $i$ and $i+1$. Write a $+$ under every $i$ and a $-$ under every $i+1$, then repeatedly cancel adjacent $-+$ pairs among the remaining signs. The operator $f_i$ changes the letter corresponding to the rightmost uncancelled $+$ from $i$ to $i+1$; if there is no uncancelled $+$, then $f_i(w)$ is undefined. The operator $e_i$ changes the letter corresponding to the leftmost uncancelled $-$ from $i+1$ to $i$; if there is no uncancelled $-$, then $e_i(w)$ is undefined. [example: Kashiwara Operators on a Word] Take $w=213121$ and compute $e_1$ and $f_1$. For $i=1$, only the letters $1$ and $2$ matter. In the word \begin{align*} w=2\,1\,3\,1\,2\,1, \end{align*} these occur in original positions $1,2,4,5,6$, giving the subword \begin{align*} 2\,1\,1\,2\,1. \end{align*} The $1$-signature writes $+$ under each $1$ and $-$ under each $2$, so the signs attached to positions $1,2,4,5,6$ are \begin{align*} -\,+\,+\,-\,+. \end{align*} Now cancel adjacent $-+$ pairs among the remaining signs. The first two signs form a $-+$ pair, so the signs from original positions $1$ and $2$ cancel. The remaining signs, still in their original order, are \begin{align*} +\,-\,+, \end{align*} coming from original positions $4,5,6$. The signs from original positions $5$ and $6$ form another adjacent $-+$ pair, so they cancel. The reduced signature is therefore the single sign \begin{align*} +, \end{align*} coming from the letter $1$ in original position $4$. The operator $f_1$ changes the letter corresponding to the rightmost uncancelled $+$ from $1$ to $2$. Since the only uncancelled $+$ is at position $4$, we get \begin{align*} f_1(213121)=213221. \end{align*} The reduced signature has no uncancelled $-$, so there is no letter selected by $e_1$, and $e_1(213121)$ is undefined. This shows that, in this word, the $1$-string continues downward by changing the fourth letter but has no upward move. [/example] The example produces arrows, but a graph of operators is useful only if each coloured string can be followed in both directions. The next result verifies that the signature convention really builds reversible rank-one strings, so the directed edges encode a crystal rather than unrelated partial moves. [quotetheorem:8455] [citeproof:8455] The hypotheses matter in two ways. The operators are defined using a fixed adjacent pair $(i,i+1)$ and the specific convention that $-$ signs cancel with later $+$ signs; changing either convention changes which letter is selected and can break the displayed inverse relation if the inverse operator is not translated at the same time. For example, with the word $w=121$ and $i=1$, the convention in this chapter gives signs $+-+$, cancels the middle $-+$, and selects the first letter for $f_1$, so $f_1(w)=221$ and $e_1(221)=121$. If $f_1$ were instead computed by cancelling $+-$ pairs, while $e_1$ were still computed with the chapter's $-+$ cancellation rule, then $f_1(121)=122$ because the last $1$ is selected; applying the unchanged $e_1$ rule to $122$ selects the middle $2$ and returns $112$, not $121$. The theorem says only that each coloured edge is reversible when it exists, not that every vertex has both an incoming and an outgoing edge of each colour. Later, this local reversibility is what lets us view the operators as coloured strings in a graph and then transfer the same strings to tableaux, tensor products, and highest weight components. The word model is flexible, but tableaux are the natural vertices for irreducible type $A$ crystals. To transfer operators from words to tableaux, we need a reading convention that identifies a word position with a unique box. [definition: Tableau Crystal] Let $\lambda$ be a partition and let $\operatorname{SSYT}_n(\lambda)$ be the set of semistandard Young tableaux of shape $\lambda$ with entries in $\{1,\dots,n\}$. The weight of a tableau $T$ is the vector $\operatorname{wt}(T)=(m_1,\dots,m_n)$, where $m_j$ is the number of entries equal to $j$. For each $i\in\{1,\dots,n-1\}$, the Kashiwara operators are partial maps \begin{align*} e_i,f_i : \operatorname{SSYT}_n(\lambda) \rightharpoonup \operatorname{SSYT}_n(\lambda). \end{align*} They are obtained by applying the word operators to the column reading word of $T$. This word is formed by scanning the rightmost column first, then moving left column by column, and within each column reading from bottom to top. The selected sign is then transported back to the unique box that produced that letter, and only that tableau entry is changed. [/definition] Changing one entry in a tableau can break either row weak increase or column strict increase. The point of the signature rule is that it detects the unpaired letter whose change is compatible with the surrounding row and column inequalities. Thus the tableau model is not merely inherited from words by wishful notation: the reading convention and cancellation rule together make the operators land back in the same semistandard set. [remark: Stability under tableau crystal operators] For every semistandard tableau $T\in\operatorname{SSYT}_n(\lambda)$ and every $i\in\{1,\dots,n-1\}$, whenever the Kashiwara operator $e_i(T)$ or $f_i(T)$ is defined by the column-reading signature rule, the resulting filling is again a semistandard tableau of shape $\lambda$. In particular, the partial maps in the tableau crystal definition are genuine partial self-maps of $\operatorname{SSYT}_n(\lambda)$. [/remark] The bottom-to-top convention inside columns is part of the model, not a decorative choice. It is the convention under which the word signature selects entries compatibly with the row and column inequalities of semistandard tableaux. Starting from a filling that is not semistandard, or changing the reading convention without changing the signature rule, is a different setup. The stability statement above only supplies closure under one Kashiwara move; it does not classify the connected component. That limited closure is enough for the next stage, because it lets the word-crystal highest weight tests be applied directly to tableau vertices without leaving $\operatorname{SSYT}_n(\lambda)$. This tableau-crystal model allows us to compute directly on tableaux rather than returning to the ambient word crystal each time. A small shape already shows how the graph records both weight changes and semistandard constraints. [example: Operators on a Semistandard Tableau] Let $T$ be the semistandard tableau of shape $(2,1)$ with upper-left entry $1$, upper-right entry $2$, and lower-left entry $2$. With the fixed column reading convention, the right column is read first and contributes the upper-right entry $2$; then the first column is read from bottom to top and contributes $2,1$. Hence the column reading word is \begin{align*} \operatorname{col}(T)=2\,2\,1. \end{align*} For $i=1$, each $1$ contributes a $+$ sign and each $2$ contributes a $-$ sign, so the three letters of $2\,2\,1$ give \begin{align*} -\,-\,+. \end{align*} The adjacent $-+$ pair in the second and third positions cancels, because it comes from the lower-left $2$ followed later in the reading word by the upper-left $1$. After removing that pair, the reduced signature is \begin{align*} -. \end{align*} This remaining $-$ is attached to the first letter of the reading word, namely the upper-right entry $2$. Therefore $e_1$ changes that selected entry from $2$ to $1$, so $e_1(T)$ has top row entries $1,1$ and lower-left entry $2$. There is no uncancelled $+$ in the reduced signature, so $f_1(T)$ is undefined. The resulting tableau is still semistandard: its top row satisfies $1\le 1$, and its first column satisfies $1<2$. [/example] ## Highest Weight Elements and Connected Components Once the crystal graph has been built, the next question is how to read its representation-theoretic pieces. For finite-dimensional highest weight representations, every connected component should contain a distinguished source vertex killed by all raising operators. [definition: Highest Weight Element] Let $B$ be a type $A_{n-1}$ crystal with partial maps \begin{align*} e_i,f_i:B\rightharpoonup B \end{align*} for each $i\in\{1,\dots,n-1\}$. An element $b\in B$ is highest weight if $e_i(b)$ is undefined for every $i\in\{1,\dots,n-1\}$. [/definition] Highest weight elements are the combinatorial analogues of highest weight vectors. To find them without drawing the whole graph, we need a test that reads directly from a word. [quotetheorem:8457] [citeproof:8457] The hypothesis must be checked for every adjacent pair, not merely for the total weight. For instance, a word can contain at least as many letters equal to $1$ as letters equal to $2$ overall but still end with too many letters equal to $2$, producing an uncancelled $-$ and hence a raising operator. It must also be checked on every suffix, because the signature rule detects the first place, read from the right, where the running count for some adjacent pair becomes negative, not only the final content of the word. The criterion is limited to the chosen word reading and the type $A$ adjacent-pair operators; for tableaux, the word must be the column reading word fixed above. Its value is that highest weight detection becomes a local running-count test, and this is the form that reappears as the lattice-word condition in the Littlewood--Richardson rule after translating between reading conventions. [example: Highest Weight Tableaux of Shape (2,1)] Consider a semistandard tableau of shape $(2,1)$ with upper-left entry $a$, upper-right entry $b$, and lower-left entry $c$. Semistandardness means \begin{align*} a\le b \end{align*} and \begin{align*} a<c. \end{align*} With the fixed column reading convention, its word is \begin{align*} \operatorname{col}(T)=b\,c\,a. \end{align*} For a highest weight tableau, the suffix consisting only of the last letter $a$ must pass the ballot test for both adjacent pairs. If $a=2$, then this suffix has no letters equal to $1$ and one letter equal to $2$, so it fails the pair $(1,2)$. If $a=3$, then it has no letters equal to $2$ and one letter equal to $3$, so it fails the pair $(2,3)$. Hence $a=1$. Now the column inequality $a<c$ gives $1<c$, so $c$ is either $2$ or $3$. If $c=3$, then the suffix $c\,a=3\,1$ has no letters equal to $2$ and one letter equal to $3$, so it fails the pair $(2,3)$. Therefore $c=2$. It remains to choose $b$. Since $a=1$ and the row condition is $1\le b$, the possible values are $b=1,2,3$. If $b=2$, then the full reading word is $2\,2\,1$, whose total content has one letter equal to $1$ and two letters equal to $2$, so it fails the pair $(1,2)$. If $b=1$, the reading word is \begin{align*} 1\,2\,1, \end{align*} and its suffixes have contents $(1,0,0)$, $(1,1,0)$, and $(2,1,0)$, each satisfying the adjacent inequalities $m_1\ge m_2$ and $m_2\ge m_3$. If $b=3$, the reading word is \begin{align*} 3\,2\,1, \end{align*} and its suffixes have contents $(1,0,0)$, $(1,1,0)$, and $(1,1,1)$, which also satisfy those adjacent inequalities. By the *[Ballot Criterion for Highest Weight Words](/theorems/8457)*, these are exactly the highest weight tableaux of shape $(2,1)$ under this column reading convention. [/example] Finding individual sources is only the first step; representation theory asks what whole connected components those sources generate. A source count is meaningful only if each component behaves like a single irreducible highest weight object, with one source controlling the component and no extra local graph pathologies. The decomposition theorem is the result that justifies reading highest weight vertices as the summands of a crystal decomposition. [quotetheorem:8458] [citeproof:8458] Finiteness is needed so that repeated raising cannot continue indefinitely, while normality and tableau origin ensure that the connected components are genuine highest weight crystals rather than arbitrary coloured graphs with sources. The statement is a decomposition of crystals as coloured weighted graphs; it does not by itself construct a module, a basis, or an isomorphism of representations. Outside the normal highest weight setting, a component may have the wrong local rank-two behaviour or more than one source, so the same counting argument would not identify irreducible summands. A concrete failure is the connected coloured graph $a\xrightarrow{1}b\xleftarrow{2}c$: both $a$ and $c$ are killed by all raising operators, so the component has two sources and cannot be an irreducible highest weight crystal. Another failure is a coloured graph with two $1$-arrows $a\xrightarrow{1}b$ and $c\xrightarrow{1}b$; the operator $e_1$ at $b$ would have two possible values, so it is not a partial map and cannot satisfy the crystal axioms. In the rest of the chapter, this theorem converts the search for highest weight vertices in tensor products into multiplicities in Schur function and representation decompositions. ## Tensor Product Rule for Crystals The next problem is to model tensor products without returning to modules. A tensor product crystal has vertices that are pairs, or words of factors, but the subtle point is deciding which factor an operator should act on. [definition: Tensor Product Crystal] Let $B$ and $C$ be type $A_{n-1}$ crystals with finite $i$-strings for every $i\in\{1,\dots,n-1\}$. For an element $b$ of such a crystal, define its reduced abstract $i$-signature to be the word \begin{align*} \underbrace{+\cdots+}_{\varphi_i(b)\text{ signs}}\underbrace{-\cdots-}_{\varepsilon_i(b)\text{ signs}}, \end{align*} where $\varepsilon_i(b)=\max\{k\ge 0 : e_i^k(b) \text{ is defined}\}$ and $\varphi_i(b)=\max\{k\ge 0 : f_i^k(b) \text{ is defined}\}$. The tensor product crystal $B\otimes C$ has vertex set $B\times C$, written $b\otimes c$, and weight $\operatorname{wt}(b\otimes c)=\operatorname{wt}(b)+\operatorname{wt}(c)$. For each $i\in\{1,\dots,n-1\}$, the operators are partial maps \begin{align*} e_i,f_i : B\otimes C \rightharpoonup B\otimes C. \end{align*} They are defined by the tensor product signature rule: concatenate the reduced abstract $i$-signature of $b$ before that of $c$, cancel adjacent $-+$ pairs as in the word model, and apply the operator to the factor containing the selected uncancelled sign. If $f_i$ selects a $+$ in the $B$-signature, set $f_i(b\otimes c)=f_i(b)\otimes c$; if it selects a $+$ in the $C$-signature, set $f_i(b\otimes c)=b\otimes f_i(c)$. The operator $e_i$ is defined analogously using the selected uncancelled $-$. [/definition] This compact signature formulation is often the safest way to remember the rule, because it avoids convention clashes about inequalities involving string lengths. To state the same rule in the abstract language of crystals, we need numerical parameters measuring the two ends of each coloured string. [definition: String Parameters] Let $B$ be a type $A_{n-1}$ crystal whose $i$-strings are finite for every $i\in\{1,\dots,n-1\}$. For each $i\in\{1,\dots,n-1\}$, define maps $\varepsilon_i,\varphi_i:B\to\mathbb{Z}_{\ge 0}$ by \begin{align*} \varepsilon_i(b)&=\max\{k\ge 0 : e_i^k(b) \text{ is defined}\},& \varphi_i(b)&=\max\{k\ge 0 : f_i^k(b) \text{ is defined}\}. \end{align*} [/definition] The numbers $\varepsilon_i$ and $\varphi_i$ measure how far $b$ sits from the top and bottom of its $i$-string. In a tensor product, an operator cannot act on both factors at once, and the ambiguous case is decided by comparing the available upward capacity of one factor with the downward capacity of the other. To compute with tensor products, we therefore need a rule that converts these two string parameters into an actual choice of factor for $e_i$ and $f_i$. The tensor product rule supplies that choice and fixes the boundary cases where the two capacities are equal. [quotetheorem:8459] [citeproof:8459] The strict inequality for $f_i$ and the strict inequality for $e_i$ occur on opposite factors because $f_i$ looks for the rightmost surviving $+$, while $e_i$ looks for the leftmost surviving $-$. These inequalities depend on the order $b\otimes c$ and on the $-+$ signature convention fixed at the start of the chapter. For a concrete boundary case, take two vector-crystal elements $b=2$ and $c=1$ in type $A_1$. Then $\varepsilon_1(b)=1$ and $\varphi_1(c)=1$, so in the convention above the weak inequality sends $f_1$ to the left factor: $f_1(2\otimes 1)$ is undefined because $f_1(2)$ is undefined. If the factor order is reversed, the same underlying pair is written $1\otimes 2$; now $\varepsilon_1(1)=0$ and $\varphi_1(2)=0$, so the same displayed weak inequality sends $f_1$ to the left factor and gives $f_1(1\otimes 2)=2\otimes 2$. The tensor product has to be compared after translating the convention, not by copying the inequalities unchanged. This rule is the computational engine for the examples and for the Littlewood--Richardson theorem, because it identifies highest weight elements in tensor products without drawing the whole product graph. The rule is most concrete when every factor is the vector representation crystal. Tensoring three copies already shows how a simple word graph separates into irreducible components. [example: The Vector Crystal Tensor Cubed] Let $B_{\mathrm{vec}}=\{1,2,3\}$ be the vector representation crystal for type $A_2$, with arrows $1\xrightarrow{1}2\xrightarrow{2}3$. The tensor cube $B_{\mathrm{vec}}\otimes B_{\mathrm{vec}}\otimes B_{\mathrm{vec}}$ has vertices all words $xyz$ of length $3$ in the alphabet $\{1,2,3\}$, with tensor order read as word order in the signature rule. We determine the highest weight words using the *Ballot Criterion for Highest Weight Words*. For a highest weight word $xyz$, the one-letter suffix $z$ must satisfy the ballot inequalities for the adjacent pairs $(1,2)$ and $(2,3)$. If $z=2$, then the suffix has no letters equal to $1$ and one letter equal to $2$, so it fails $m_1\ge m_2$. If $z=3$, then it has no letters equal to $2$ and one letter equal to $3$, so it fails $m_2\ge m_3$. Hence $z=1$. Now consider the two-letter suffix $y1$. If $y=1$, its content is $(2,0,0)$, so $m_1\ge m_2$ and $m_2\ge m_3$. If $y=2$, its content is $(1,1,0)$, so again $m_1\ge m_2$ and $m_2\ge m_3$. If $y=3$, its content is $(1,0,1)$, so it fails $m_2\ge m_3$. Thus $y\in\{1,2\}$. There are now six possible words to test: \begin{align*} 111,\ 211,\ 311,\ 121,\ 221,\ 321. \end{align*} For $111$, the suffix contents are $(1,0,0)$, $(2,0,0)$, and $(3,0,0)$, so every suffix satisfies $m_1\ge m_2\ge m_3$. For $211$, the suffix contents are $(1,0,0)$, $(2,0,0)$, and $(2,1,0)$, so it is highest weight. For $311$, the full word has content $(2,0,1)$, which fails $m_2\ge m_3$, so it is not highest weight. For $121$, the suffix contents are $(1,0,0)$, $(1,1,0)$, and $(2,1,0)$, so it is highest weight. For $221$, the full word has content $(1,2,0)$, which fails $m_1\ge m_2$, so it is not highest weight. For $321$, the suffix contents are $(1,0,0)$, $(1,1,0)$, and $(1,1,1)$, so it is highest weight. Therefore the highest weight words are exactly \begin{align*} 111,\ 121,\ 211,\ 321. \end{align*} Their weights are \begin{align*} \operatorname{wt}(111)=(3,0,0),\quad \operatorname{wt}(121)=\operatorname{wt}(211)=(2,1,0),\quad \operatorname{wt}(321)=(1,1,1). \end{align*} By the *Highest Weight Decomposition of Type A Crystals*, each highest weight word gives one connected component of the corresponding highest weight shape. Hence \begin{align*} B_{\mathrm{vec}}^{\otimes 3}\cong B(3)\sqcup B(2,1)\sqcup B(2,1)\sqcup B(1,1,1). \end{align*} The two words $121$ and $211$ are the two distinct highest weight sources of weight $(2,1,0)$, so the component $B(2,1)$ occurs with multiplicity $2$. This matches the Schur--Weyl decomposition $V^{\otimes 3}\cong S^{3}V\otimes \operatorname{Sp}_{(3)}\oplus S^{(2,1)}V\otimes \operatorname{Sp}_{(2,1)}\oplus \Lambda^{3}V\otimes \operatorname{Sp}_{(1,1,1)}$: the hook lengths of the shape $(2,1)$ are $3,1,1$, so the hook-length formula gives $\dim \operatorname{Sp}_{(2,1)}=3!/(3\cdot 1\cdot 1)=2$. [/example] This continues the Schur-function viewpoint introduced through the Frobenius characteristic in Chapter 0 and used for Specht characters in Chapter 4: the tensor product graph is the combinatorial object behind multiplication of characters, and its character is the product $s_\lambda s_\mu$ of the corresponding Schur functions. The obstruction is size: drawing $B(\lambda)\otimes B(\mu)$ usually produces too many vertices to decompose by inspection, while the decomposition theorem says that only highest weight vertices have to be counted. The next theorem identifies those highest weight counts with the Littlewood--Richardson coefficients already familiar from Young tableau combinatorics. ## Skew Tableaux and the Crystal Littlewood--Richardson Count To make the Littlewood--Richardson endpoint explicit, we need to see how a highest weight element in a tensor product becomes a skew tableau. Fix a tableau $P\in\operatorname{SSYT}_n(\lambda)$ in the highest weight component $B(\lambda)$, and take $Q\in\operatorname{SSYT}_n(\mu)$. The tensor element $P\otimes Q$ is highest weight exactly when the signature rule on the combined reading word has no uncancelled $-$ for any adjacent pair. Under the tableau insertion or growth-diagram identification used earlier in the course, the second factor records the boxes added to $\lambda$ to produce a larger shape $\nu$. [definition: Littlewood-Richardson Tableau] Let $\lambda\subset\nu$ be partitions and let $\mu=(\mu_1,\dots,\mu_n)$ be a composition. A Littlewood--Richardson tableau of skew shape $\nu/\lambda$ and content $\mu$ is a semistandard filling of the boxes of $\nu/\lambda$ with entries in $\{1,\dots,n\}$ such that exactly $\mu_j$ boxes contain $j$ and the chosen reading word is ballot: for every suffix and every $i\in\{1,\dots,n-1\}$, the number of letters $i$ in that suffix is at least the number of letters $i+1$. [/definition] This definition is the skew-tableau version of the highest weight condition. The semistandard inequalities remember that the added boxes form a tableau, while the ballot condition says that the corresponding tensor vertex is killed by every $e_i$. The skew shape $\nu/\lambda$ records the final highest weight $\nu$ rather than only the content $\mu$ of the second factor. [example: The Product $s_{(2)}s_{(1)}$] The product $s_{(2)}s_{(1)}$ is controlled by Littlewood--Richardson tableaux with inner shape $\lambda=(2)$ and content $\mu=(1)$. Since $|\lambda|=2$ and $|\mu|=1$, every possible outer shape $\nu$ has size \begin{align*} |\nu|=|\lambda|+|\mu|=2+1=3. \end{align*} It must also contain the two boxes of $(2)$ in its first row, so the only way to obtain $\nu/\lambda$ is to add one box to the diagram of $(2)$. Adding the box to the first row gives row lengths \begin{align*} (2)+(1\text{ in row }1)=(3). \end{align*} Adding the box to the second row gives row lengths \begin{align*} (2)+(1\text{ in row }2)=(2,1). \end{align*} Adding it to a third row would give row lengths \begin{align*} (2,0,1), \end{align*} which is not a partition because the row lengths are not weakly decreasing: $0<1$. Thus the only candidate outer shapes are $\nu=(3)$ and $\nu=(2,1)$. For each of these two skew shapes, $\nu/\lambda$ consists of exactly one box. The content $\mu=(1)$ forces that single box to contain the entry $1$, so there is exactly one filling in each case. Its reading word is \begin{align*} 1. \end{align*} The only nonempty suffix is again $1$. For the adjacent pair $(1,2)$, this suffix has one letter equal to $1$ and no letters equal to $2$, so $1\ge 0$. For every adjacent pair $(i,i+1)$ with $i\ge 2$, it has no letters equal to $i$ and no letters equal to $i+1$, so $0\ge 0$. Hence the reading word is ballot in both cases. Therefore the Littlewood--Richardson coefficients are \begin{align*} c_{(2),(1)}^{(3)}=1,\quad c_{(2),(1)}^{(2,1)}=1, \end{align*} and all other coefficients are $0$. Hence \begin{align*} s_{(2)}s_{(1)}=s_{(3)}+s_{(2,1)}. \end{align*} Equivalently, the crystal tensor product has one component of highest weight $(3)$ and one component of highest weight $(2,1)$. The reusable pattern is: list the outer partitions $\nu$ containing $\lambda$ with $|\nu/\lambda|=|\mu|$, fill the skew boxes with content $\mu$, and keep exactly the fillings whose reading words are ballot. [/example] The explicit bijection can be summarised as follows. Start with a highest weight tensor element in $B(\lambda)\otimes B(\mu)$, regard the first factor as the fixed highest weight tableau of shape $\lambda$, and read the second factor as an ordered sequence of box additions. Insert those additions into the complement of $\lambda$ inside the final shape $\nu$; the labels record which entry of the second factor was used. The tensor element is highest weight precisely when this skew filling has ballot reading word, and the weight of the whole tensor element is $\nu$. Conversely, a Littlewood--Richardson tableau of shape $\nu/\lambda$ and content $\mu$ determines the sequence of crystal moves in the second factor and hence a highest weight vertex in $B(\lambda)\otimes B(\mu)$ of weight $\nu$. This bijective dictionary is the missing step between the preceding example and the full multiplication rule. The decomposition theorem has already reduced tensor product multiplicities to counting highest weight vertices; the skew-tableau translation identifies those vertices with the classical objects counted by $c_{\lambda\mu}^{\nu}$. The next theorem packages that identification, so the crystal calculation becomes a Schur function multiplication formula rather than a case-by-case graph decomposition. [quotetheorem:8460] The course uses this theorem as the point where the crystal and symmetric-function languages become interchangeable. Once the highest weight vertices in $B(\lambda)\otimes B(\mu)$ have been translated into Littlewood--Richardson tableaux, the same integers can be read either as tensor product multiplicities or as Schur multiplication coefficients. The hypotheses are part of the statement rather than cosmetic. The shapes $\lambda,\mu,\nu$ are partitions, the crystals are finite type $A$ highest weight crystals, and the ballot condition uses the column reading convention fixed earlier in the chapter. Changing the reading word changes which skew tableaux are recognised as highest weight unless the convention is translated at the same time. For example, in a single column with entries $1$ above $2$, the fixed bottom-to-top column word is $21$, so the suffix test detects the $2$ before the later $1$ and gives the intended type $A$ highest weight behaviour after the tableau convention is applied; reading the same column top-to-bottom gives $12$ and reverses the signature calculation for this local configuration. A second warning is that type $B$ and type $C$ crystals require extra letters and different local rules, so counting ordinary Littlewood--Richardson skew tableaux does not describe their tensor product multiplicities without replacing the model. Within the type $A$ convention, the theorem is the bridge between three languages: tensor product components of crystals, Schur function multiplication, and Littlewood--Richardson tableaux. In later representation-theoretic settings, the same philosophy survives in categorification, where crystal operators often record the shadow of exact functors on categories rather than moves on tableaux alone. [remark: Stembridge Local Axioms] Stembridge's local axioms characterise simply-laced highest weight crystals by local conditions on pairs of adjacent colours. In type $A$, they say that a coloured directed graph with compatible weights, finite strings, and prescribed rank-two interactions is forced to be a disjoint union of genuine highest weight crystals. These axioms justify recognising type $A$ crystals from local combinatorial data rather than reconstructing the representation. [/remark] Stembridge's theorem is quoted here as structure rather than proved. Its role in this course is diagnostic: when a graph built from tableaux satisfies the local axioms, the connected components are the expected irreducible type $A$ crystals. Crystal graphs retain the combinatorial skeleton of representations, but they emphasize local moves and tensor product structure rather than direct module constructions. That perspective prepares the next chapter, which studies jeu de taquin, promotion, and evacuation as tableau operations that interact with those same crystal symmetries. # 8. Jeu de Taquin, Promotion, and Evacuation These notes develop the tableau algorithms that sit behind the representation theory and symmetric-function combinatorics of the course. Earlier chapters introduced Young diagrams, standard tableaux, and insertion; this chapter turns from constructing tableaux from words to manipulating tableaux intrinsically. The guiding problem is how to move entries through a skew shape without changing the representation-theoretic object being encoded. Jeu de taquin gives a local sliding algorithm, rectification turns skew tableaux into ordinary tableaux, and Schutzenberger's promotion and evacuation package these slides into global symmetries. ## Slides, Rectification, and Skew Tableaux The first question is how a tableau of skew shape can be compared with an ordinary tableau. A skew tableau has missing boxes in the north-west corner, so there is no immediate row-insertion tableau attached to its entries alone. Jeu de taquin answers this by allowing the holes to move through the diagram while preserving the semistandard or standard order conditions. [definition: Skew Young Diagram] Let $\lambda$ and $\mu$ be partitions with $\mu_i \le \lambda_i$ for all $i$. The skew Young diagram $\lambda / \mu$ is the set of boxes in the Young diagram of $\lambda$ that are not in the Young diagram of $\mu$. [/definition] This definition separates the outer boundary from the inner boundary. To run sliding algorithms we also need an order-respecting labelling of the remaining boxes, because the local comparison between neighbouring entries is meaningful only when rows and columns carry the usual tableau order. [definition: Skew Standard Young Tableau] Let $\lambda / \mu$ be a skew Young diagram with $n$ boxes. A skew standard Young tableau of shape $\lambda / \mu$ is a filling of the boxes of $\lambda / \mu$ by $1,\dots,n$, each used once, such that entries increase from left to right along rows and from top to bottom down columns. [/definition] For semistandard tableaux the same sliding rule is used, but standard tableaux keep the notation lighter and are the main object in this chapter. The order conditions in the definition are designed to survive a local move of an empty box, and the next definition describes that elementary move. [definition: Jeu De Taquin Slide] Let $\operatorname{SYT}(\lambda / \mu)$ be the set of skew standard Young tableaux of shape $\lambda / \mu$. Define \begin{align*} \operatorname{SkewSYT}_n = \bigcup_{\substack{\mu \subseteq \lambda,\ |\lambda / \mu|=n}} \operatorname{SYT}(\lambda / \mu). \end{align*} Also define \begin{align*} \mathcal{D}_n = \bigcup_{\substack{\mu \subseteq \lambda,\ |\lambda / \mu|=n}} \{(T,c) : T \in \operatorname{SYT}(\lambda / \mu),\ c \text{ is an inner corner of } \mu \text{ adjacent to } \lambda / \mu\}. \end{align*} A jeu de taquin slide on $n$ entries is the map \begin{align*} \operatorname{jdt}_n: \mathcal{D}_n \to \operatorname{SkewSYT}_n \end{align*} obtained as follows. For $(T,c) \in \mathcal{D}_n$, place a hole in $c$, repeatedly exchange the hole with the smaller of the entries immediately to its right and immediately below it when such entries exist, and stop when neither such entry exists. The final hole is deleted from the outer boundary, so the output has $n$ filled boxes and has skew shape $\lambda' / \mu'$ for the new outer and inner boundaries determined by the slide path. [/definition] The choice of the smaller neighbouring entry is what preserves increasing rows and columns. If only one neighbour exists, the hole exchanges with that neighbour. [example: A Slide In Shape Three Two Over One] Consider the skew shape $(3,2)/(1)$ with boxes $(1,2),(1,3),(2,1),(2,2)$, filled by \begin{align*} T(1,2)=2,\quad T(1,3)=4,\quad T(2,1)=1,\quad T(2,2)=3. \end{align*} This is standard because the first row has $2<4$ and the second row has $1<3$; there are no vertical comparisons except $2<3$ in column $2$. Place the hole at the inner corner $(1,1)$. Its right neighbour is $T(1,2)=2$ and its lower neighbour is $T(2,1)=1$, so the jeu de taquin rule moves the smaller entry $1$ into the hole. The filled positions are then \begin{align*} (1,1)\mapsto 1,\quad (1,2)\mapsto 2,\quad (1,3)\mapsto 4,\quad (2,2)\mapsto 3, \end{align*} and the hole is at $(2,1)$. From $(2,1)$ there is no lower neighbour, and the only available right neighbour is the entry $3$ at $(2,2)$, so $3$ moves into the hole. The filled positions become \begin{align*} (1,1)\mapsto 1,\quad (1,2)\mapsto 2,\quad (1,3)\mapsto 4,\quad (2,1)\mapsto 3, \end{align*} with the hole now at $(2,2)$. The hole at $(2,2)$ has no right or lower neighbour inside the outer shape, so it is deleted from the outer boundary. The output has straight shape $(3,1)$, with first row $1,2,4$ and second row $3$; it is standard because $1<2<4$ along the first row and $1<3$ down the first column. The slide path $(1,1)\to(2,1)\to(2,2)$ shows explicitly how the inner indentation travels to an outer corner. [/example] A single slide only moves one hole, so it changes the inner boundary without yet producing an ordinary tableau. To compare skew tableaux with the straight tableaux used in Specht modules and RSK, we need to repeat slides until no inner shape remains; this motivates the rectification process. [definition: Rectification] Let \begin{align*} \operatorname{SYT}_n = \bigcup_{|\nu|=n} \operatorname{SYT}(\nu). \end{align*} The rectification relation is the subset \begin{align*} \operatorname{Rect}_n \subseteq \operatorname{SkewSYT}_n \times \operatorname{SYT}_n \end{align*} where $(T,U) \in \operatorname{Rect}_n$ if $U$ is obtained from $T$ by repeatedly applying jeu de taquin slides at inner corners until the shape is straight. A rectification of $T$ is such a tableau $U \in \operatorname{SYT}_n$. [/definition] The definition gives rectification the source $\operatorname{SkewSYT}_n$ and target $\operatorname{SYT}_n$, but it still allows many possible sequences of inner corners. For rectification to be usable in counting and in the [Littlewood-Richardson rule](/theorems/5183), those choices must not become extra data. The key point is confluence: all complete slide sequences from the same skew standard tableau have the same final straight tableau. [remark: Jeu de taquin confluence] For a skew standard tableau $T\in\operatorname{SkewSYT}_n$, every complete sequence of jeu de taquin slides that rectifies $T$ ends at the same straight standard tableau. Consequently rectification is a well-defined map \begin{align*} \operatorname{rect}:\operatorname{SkewSYT}_n\to\operatorname{SYT}_n. \end{align*} [/remark] Confluence makes rectification a well-defined map from skew tableaux to straight tableaux. The hypotheses matter: if the filling of $(3,2)/(1)$ has entries $4,1$ in the first row boxes $(1,2),(1,3)$ and entries $2,3$ in the second row boxes $(2,1),(2,2)$, then sliding into $(1,1)$ produces a filling of straight shape $(3,1)$ whose first row is $2,4,1$, so the output is not standard. Completeness also matters: stopping after only some available inner-corner slides leaves a skew tableau rather than an element of the target set $\operatorname{SYT}_n$. The theorem does not say that intermediate skew tableaux are independent of the chosen sequence; only the final rectified straight tableau is forced. This is the tableau-level mechanism behind the Littlewood-Richardson rule: skew objects can be sorted into ordinary highest-weight objects without choosing an arbitrary slide order. [example: Rectifying A Four-Box Skew Tableau] For the skew tableau of shape $(3,2)/(1)$, the filled boxes are \begin{align*} T(1,2)=2,\quad T(1,3)=4,\quad T(2,1)=1,\quad T(2,2)=3. \end{align*} The only box of the inner shape is $(1,1)$, so rectification starts by placing the hole at $(1,1)$. At $(1,1)$ the available neighbours are the right neighbour $(1,2)$ and the lower neighbour $(2,1)$, with entries \begin{align*} T(1,2)=2,\quad T(2,1)=1. \end{align*} Since $1<2$, the jeu de taquin rule moves $1$ into $(1,1)$. The hole is now at $(2,1)$, and the filled boxes are \begin{align*} (1,1)\mapsto 1,\quad (1,2)\mapsto 2,\quad (1,3)\mapsto 4,\quad (2,2)\mapsto 3. \end{align*} From $(2,1)$ there is no lower neighbour in the outer shape $(3,2)$, and the only right neighbour is $(2,2)$ with entry $3$, so $3$ moves into $(2,1)$. The filled boxes become \begin{align*} (1,1)\mapsto 1,\quad (1,2)\mapsto 2,\quad (1,3)\mapsto 4,\quad (2,1)\mapsto 3. \end{align*} The hole is now at $(2,2)$. There is no box $(2,3)$ and no box $(3,2)$ in the outer shape $(3,2)$, so the hole is deleted from the outer boundary. The remaining shape has boxes $(1,1),(1,2),(1,3),(2,1)$, hence shape $(3,1)$, with first row $1,2,4$ and second row $3$. This tableau is standard because $1<2<4$ along the first row and $1<3$ down the first column. Since the original inner shape had only the one box $(1,1)$, this single slide completes rectification; the slide path \begin{align*} (1,1)\to(2,1)\to(2,2) \end{align*} records exactly how the inner indentation moves to the outer boundary. [/example] ## Schutzenberger Involution and Evacuation Once rectification is available, a new question arises: what global symmetry of standard tableaux is obtained by repeatedly removing the smallest entry and rectifying the remainder? Schutzenberger's evacuation, previewed in Chapter 2 as an RSK symmetry, answers this question. It is an involution on standard tableaux that appears in RSK symmetries, dual equivalence, and the action of the longest element on type $A$ crystals. [definition: Evacuation] Let $\lambda$ be a partition with $n$ boxes, and let $\operatorname{SYT}(\lambda)$ denote the set of standard Young tableaux of shape $\lambda$. Evacuation is the map \begin{align*} \operatorname{evac}: \operatorname{SYT}(\lambda) \to \operatorname{SYT}(\lambda) \end{align*} which sends $T$ to the tableau $\operatorname{evac}(T)$ constructed as follows: repeatedly delete the entry $1$, apply jeu de taquin slides to rectify the remaining skew tableau, decrement all remaining entries by $1$, and record the final outer corners reached by these deletion-slide processes in reverse order as a new standard tableau. [/definition] Here the recorded box is the final outer corner reached by the deletion-slide path, not the original position of the entry $1$. The recording convention is part of the definition: the first final corner receives $n$, the next final corner receives $n-1$, and so on. This reversal is what turns the deletion process into an involution rather than merely a stripping algorithm. [example: Evacuation Of A Small Tableau] Let $T$ have entries \begin{align*} T(1,1)=1,\quad T(1,2)=2,\quad T(1,3)=5,\quad T(2,1)=3,\quad T(2,2)=4. \end{align*} We compute $\operatorname{evac}(T)$ by recording the outer corner reached at each deletion of $1$. First delete the entry $1$ from $(1,1)$. The right and lower neighbours are $2$ and $3$, and $2<3$, so $2$ moves into $(1,1)$ and the hole moves to $(1,2)$. Now the right and lower neighbours are $5$ and $4$, and $4<5$, so $4$ moves into $(1,2)$ and the hole moves to $(2,2)$. There is no box to the right of $(2,2)$ and no box below it, so the first recorded outer corner is $(2,2)$. Before decrementing, the remaining entries are \begin{align*} (1,1)\mapsto 2,\quad (1,2)\mapsto 4,\quad (1,3)\mapsto 5,\quad (2,1)\mapsto 3. \end{align*} Subtracting $1$ from each entry gives the tableau of shape $(3,1)$ with first row $1,3,4$ and second row $2$. Now delete the new $1$ from $(1,1)$. Its right and lower neighbours are $3$ and $2$, and $2<3$, so $2$ moves into $(1,1)$ and the hole moves to $(2,1)$. There is no box to the right of $(2,1)$ and no box below it, so the second recorded corner is $(2,1)$. The entries before decrementing are \begin{align*} (1,1)\mapsto 2,\quad (1,2)\mapsto 3,\quad (1,3)\mapsto 4. \end{align*} After subtracting $1$, the remaining tableau is the one-row tableau $1,2,3$. For the one-row tableau $1,2,3$, deleting $1$ leaves a hole at $(1,1)$; the only available neighbour is $2$ at $(1,2)$, so $2$ moves left, and then the only available neighbour is $3$ at $(1,3)$, so $3$ moves left. The third recorded corner is $(1,3)$, and decrementing leaves the one-row tableau $1,2$. Repeating the same one-row computation records $(1,2)$ and leaves the one-box tableau $1$. Deleting that final $1$ records $(1,1)$. Thus the recorded corners, in deletion order, are \begin{align*} (2,2),\ (2,1),\ (1,3),\ (1,2),\ (1,1). \end{align*} Evacuation fills these corners in reverse label order, so the entries placed are \begin{align*} (2,2)\mapsto 5,\quad (2,1)\mapsto 4,\quad (1,3)\mapsto 3,\quad (1,2)\mapsto 2,\quad (1,1)\mapsto 1. \end{align*} Therefore $\operatorname{evac}(T)$ has first row $1,2,3$ and second row $4,5$. The slide choices use comparisons among neighbouring entries, so evacuation is not just a geometric rotation of the diagram. [/example] The example shows evacuation as a long deletion history, but the definition does not by itself explain why this history should be reversible. The next theorem supplies the structural content: evacuation is the tableau symmetry that reverses the growth data underlying RSK, so applying it twice restores the original tableau. [quotetheorem:8461] [citeproof:8461] Evacuation is therefore a genuine symmetry, not only an algorithm. Standardness is important here because the deletion order is a total order and the recording tableau is forced to use each label exactly once. The theorem also does not say that evacuation is geometric rotation of the drawn Young diagram: in shape $(2,1)$, the tableau with first row $1,2$ and second row $3$ is sent to the tableau with first row $1,3$ and second row $2$, while rotating the diagram would not even preserve the Young-diagram orientation. For words with repeated letters, the insertion tableau in RSK is semistandard; the corresponding statement uses Schutzenberger's involution on semistandard tableaux with a fixed alphabet and a separately specified transformation of the recording tableau, so it is not the standard-tableau theorem stated above. In representation-theoretic language evacuation models the action of the longest Weyl group element on the crystal of standard tableaux of fixed shape. A small counterexample explains the reverse-complement hypothesis in the RSK statement. For $\pi=12$, RSK gives $P(\pi)=Q(\pi)$ equal to the one-row tableau $1,2$, whose evacuation is itself. Reversing the word alone gives $21$, whose insertion and recording tableaux both have shape $(1,1)$, so reversal alone cannot satisfy the displayed compatibility. Complementing alone also sends $12$ to $21$ and has the same failure. The paired reverse-complement operation is the transformation that matches the anti-diagonal reflection of the growth diagram. [remark: Shape Preservation] Evacuation preserves the shape of a standard tableau. The entries move through jeu de taquin slides, but the final recording tableau has the same Young diagram as the original tableau. [/remark] Evacuation also interacts tightly with another operation, promotion. Promotion removes the smallest entry but reinserts the missing label at the end instead of recording a whole evacuation history. ## Promotion on Rectangular Tableaux and Cyclic Sieving Preview The final question in the chapter is how far a local sliding algorithm can generate a global cyclic action. Promotion is defined for any standard tableau, but its strongest uniform behaviour occurs for rectangular shapes. This is the setting where cyclic sieving enters: the orbit structure of promotion is measured by a $q$-analogue of the hook-length formula. [definition: Promotion] Let $\lambda$ be a partition with $n$ boxes. Promotion is the map \begin{align*} \operatorname{pr}: \operatorname{SYT}(\lambda) \to \operatorname{SYT}(\lambda) \end{align*} which sends $T$ to the tableau $\operatorname{pr}(T)$ defined as follows: delete the entry $1$, apply jeu de taquin slides to rectify the remaining skew tableau, subtract $1$ from every remaining entry, and place $n$ in the final empty outer corner. [/definition] Promotion uses the same deletion-and-sliding motion as evacuation, but it performs a single cyclic relabelling step. The operation is bijective, with inverse obtained by the reverse slide starting from the box containing $n$. [example: Promotion On A Two By Three Rectangle] Take the $2 \times 3$ rectangular tableau $T$ of shape $(3,3)$ with entries \begin{align*} T(1,1)=1,\quad T(1,2)=2,\quad T(1,3)=4,\quad T(2,1)=3,\quad T(2,2)=5,\quad T(2,3)=6. \end{align*} To compute $\operatorname{pr}(T)$, delete the entry $1$ from $(1,1)$. The hole has right neighbour $T(1,2)=2$ and lower neighbour $T(2,1)=3$, and since $2<3$, the jeu de taquin rule moves $2$ into $(1,1)$. The hole is now at $(1,2)$, where the right and lower neighbours have entries $4$ and $5$; since $4<5$, the entry $4$ moves into $(1,2)$. The hole is now at $(1,3)$, and the only available lower neighbour is $T(2,3)=6$, so $6$ moves into $(1,3)$ and the final hole is at $(2,3)$. Before subtracting $1$, the filled boxes are \begin{align*} (1,1)\mapsto 2,\quad (1,2)\mapsto 4,\quad (1,3)\mapsto 6,\quad (2,1)\mapsto 3,\quad (2,2)\mapsto 5. \end{align*} Subtracting $1$ from these entries gives \begin{align*} (1,1)\mapsto 1,\quad (1,2)\mapsto 3,\quad (1,3)\mapsto 5,\quad (2,1)\mapsto 2,\quad (2,2)\mapsto 4. \end{align*} Promotion then places $6$ in the final empty box $(2,3)$, so $\operatorname{pr}(T)$ has first row $1,3,5$ and second row $2,4,6$. The set $\operatorname{SYT}(3,3)$ is finite. For the shape $(3,3)$, the hook lengths in the boxes $(1,1),(1,2),(1,3),(2,1),(2,2),(2,3)$ are \begin{align*} 4,\quad 3,\quad 2,\quad 3,\quad 2,\quad 1, \end{align*} because each hook length counts the chosen box, the boxes to its right, and the boxes below it. Thus the *Hook-Length Formula* gives \begin{align*} |\operatorname{SYT}(3,3)|=\frac{6!}{4\cdot 3\cdot 2\cdot 3\cdot 2\cdot 1}. \end{align*} Here $6!=720$ and \begin{align*} 4\cdot 3\cdot 2\cdot 3\cdot 2\cdot 1=144. \end{align*} Therefore \begin{align*} |\operatorname{SYT}(3,3)|=\frac{720}{144}=5. \end{align*} So repeated promotion stays inside a five-element set of standard tableaux, and the displayed computation gives the first step of that finite promotion orbit. [/example] A computed orbit suggests that promotion behaves like a rotation, while evacuation behaves like a reflection. To make that statement intrinsic, we need a relation that does not depend on a particular tableau or a drawn orbit; the promotion-evacuation identities give exactly that relation. [quotetheorem:8462] [citeproof:8462] The relation says that evacuation reflects promotion orbits. The hypotheses and ambient set matter: the same naive deletion rule is ambiguous on the semistandard row $1,1$, so the displayed identity is a statement about standard tableaux unless the operation is replaced by its crystal-theoretic analogue. The dihedral interpretation requires working on a finite promotion-stable set, such as $\operatorname{SYT}(\lambda)$ for a fixed finite shape; on an infinite family of tableaux there need not be a single finite orbit order to complete the dihedral presentation. The identity also does not determine the order of promotion. A concrete check is shape $(2,1)$: for the tableau with first row $1,2$ and second row $3$, promotion has order $2$, so $\operatorname{pr}^{3}(T) \ne T$ although evacuation still conjugates promotion to its inverse. The next issue is whether promotion has a predictable finite order on an important family of shapes. Rectangles are the family where the answer is uniform, which is why they are the entry point to cyclic sieving. [quotetheorem:8463] [citeproof:8463] This theorem is the bridge to cyclic sieving. The rectangular hypothesis is a real restriction, not a cosmetic assumption: for non-rectangular straight shapes, promotion still acts on the finite set $\operatorname{SYT}(\lambda)$, but its order is not uniformly controlled by the same rectangular growth-diagram argument. For example, in shape $(2,1)$ with tableau having first row $1,2$ and second row $3$, promotion swaps the two standard tableaux of that shape, so its order is $2$ while the comparable rectangular period would be absent. The theorem also does not claim that every divisor of $N$ occurs as an orbit size, only that the global action satisfies $\operatorname{pr}^{N}=\operatorname{id}$ on $a \times b$ rectangles. If $X$ is the set of standard tableaux of rectangular shape $(b^a)$ and $C=\langle \operatorname{pr}\rangle$ is the cyclic group generated by promotion, then fixed points of powers of promotion are predicted by evaluating a $q$-hook formula at $N$-th roots of unity. [remark: Cyclic Sieving Preview] The cyclic sieving phenomenon packages a finite set $X$, a cyclic action $C$, and a polynomial $X(q)$ such that the number of fixed points of each group element is obtained by evaluating $X(q)$ at a corresponding root of unity. For rectangular standard tableaux, $X(q)$ is the $q$-analogue of the hook-length enumeration, and the cyclic action is generated by promotion. [/remark] The chapter's main lesson is that jeu de taquin is more than a sorting algorithm. Its confluence makes rectification well-defined, its repeated deletion process gives Schutzenberger evacuation, and its cyclic version gives promotion, the operation that later connects tableaux with cyclic sieving and affine crystal symmetries. Jeu de taquin and its variants show that tableau algorithms can be dynamical as well as classificatory. The next chapter deforms the symmetric-group picture by introducing Hecke algebras, where the same combinatorics survives in a $q$-deformed setting. # 9. Hecke Algebras and $q$-Deformation Hecke algebras enter the course as a controlled way to deform the group algebra of the symmetric group without losing the combinatorics of reduced words, descents, tableaux, and cells. In Chapters 3 through 6, $S_n$ acted through permutations, Young symmetrizers, and Specht modules; here the same objects acquire a parameter $q$ and become modules over the type $A$ Hecke algebra $H_q(S_n)$. The point is not only to generalise $\mathbb C[S_n]$, but to explain why tableau combinatorics persists in settings such as finite groups of Lie type and Kazhdan-Lusztig theory. The chapter has three linked questions. First, how can the multiplication rules of $S_n$ be deformed while retaining a basis indexed by permutations? Second, how do Specht modules survive after replacing transpositions by Hecke generators? Third, what extra structure appears when the deformation parameter is allowed to interact with an involution $q \leftrightarrow q^{-1}$? ## Deforming the Symmetric Group Algebra What part of the symmetric group presentation should be changed if we want a parameter $q$ but still want basis elements indexed by permutations? The symmetric group $S_n$ is generated by the adjacent transpositions $s_i=(i,i+1)$ for $1\le i<n$, with braid relations and quadratic relations $s_i^2=e$. The Iwahori-Hecke algebra keeps the braid relations and replaces $s_i^2=e$ by a quadratic relation whose roots are $q$ and $-1$. [definition: Iwahori-Hecke Algebra of the Symmetric Group] Let $R=\mathbb Z[q,q^{-1}]$. The Iwahori-Hecke algebra $H_q(S_n)$ is the unital associative $R$-algebra generated by $T_1,\dots,T_{n-1}$ subject to the relations $T_iT_j=T_jT_i$ if $|i-j|>1$, $T_iT_{i+1}T_i=T_{i+1}T_iT_{i+1}$ if $1\le i<n-1$, and $(T_i-q)(T_i+1)=0$ if $1\le i<n$. [/definition] The first two relations are the same braid relations that describe reduced expressions in $S_n$. The final relation is the deformation: expanding it gives $T_i^2=(q-1)T_i+q$, so at $q=1$ the generator satisfies $T_i^2=1$. [example: The Rank One Hecke Algebra] For $S_2=\{e,s_1\}$, there is only one Hecke generator, so $H_q(S_2)$ is generated over $R=\mathbb Z[q,q^{-1}]$ by $1$ and $T_1$, subject to \begin{align*} (T_1-q)(T_1+1)=0. \end{align*} Expanding the left-hand side gives \begin{align*} (T_1-q)(T_1+1)=T_1^2+T_1-qT_1-q=T_1^2+(1-q)T_1-q. \end{align*} Thus the defining relation is equivalent to \begin{align*} T_1^2=(q-1)T_1+q. \end{align*} Every word in the generator is a power $T_1^m$. The relation reduces any power of degree at least $2$: for example, \begin{align*} T_1^3=T_1T_1^2=T_1((q-1)T_1+q)=(q-1)T_1^2+qT_1. \end{align*} Substituting $T_1^2=(q-1)T_1+q$ again gives \begin{align*} T_1^3=(q-1)((q-1)T_1+q)+qT_1=((q-1)^2+q)T_1+q(q-1). \end{align*} Repeating this reduction expresses every power $T_1^m$ as an $R$-linear combination of $1$ and $T_1$, so every element has the form $a+bT_1$ with $a,b\in R$. At $q=1$, the relation becomes \begin{align*} T_1^2=(1-1)T_1+1=1. \end{align*} Therefore the specialised multiplication has $T_1^2=1$, exactly like $s_1^2=e$ in the group algebra $\mathbb Z[S_2]$ under the identification $T_1\mapsto s_1$. [/example] The rank one example shows the deformation in its smallest possible form. To get a basis indexed by all permutations, we need to know that the element attached to a permutation does not depend on the chosen reduced expression. [definition: Hecke Word Element] For $w\in S_n$, choose a reduced expression $w=s_{i_1}\cdots s_{i_r}$. Define \begin{align*} T_w:=T_{i_1}\cdots T_{i_r}\in H_q(S_n). \end{align*} [/definition] Matsumoto's theorem for Coxeter groups implies that any two reduced expressions for $w$ are connected by braid moves. Since the Hecke generators satisfy the same braid relations, the element $T_w$ is well-defined. The next issue is whether these elements merely span a convenient submodule or whether they account for the whole algebra without hidden linear relations. [quotetheorem:8464] [citeproof:8464] This theorem is the algebraic reason that Hecke algebras are deformations rather than replacements. The hypotheses matter: the braid relations alone would identify reduced expressions but would not reduce non-reduced words, while the quadratic relation alone would not make different reduced expressions for the same permutation agree. If the quadratic relation were replaced by an unrelated higher-degree relation, words such as $T_i^2$ would not reduce back to a permutation-indexed basis in the same way, and hidden extra basis elements could appear. The theorem does not yet describe the multiplication table explicitly; it only says that the algebra is free with the expected labels. The next step is therefore to compute how the basis changes when we multiply by one simple generator. [quotetheorem:8465] [citeproof:8465] The formula should be read as the deformation of right multiplication in $S_n$. The assumption that the multiplier is a simple generator is essential: for a general element $T_v$, the product $T_wT_v$ must be computed by iterating this rule along a reduced expression for $v$, and several lower Bruhat terms may appear. The length dichotomy is also essential, because multiplying by a simple reflection changes length by exactly $1$; without that fact there would be no two-case formula. The theorem does not give a closed multiplication formula for arbitrary pairs $T_w,T_v$, but it supplies the local rule from which the full multiplication table and the later module actions are built. [example: Comparing Hecke and Group Multiplication] In $S_3$, take $w=s_1s_2$ and multiply on the right by $s_2$. Since $s_2^2=e$, the group product is \begin{align*} ws_2=s_1s_2s_2=s_1e=s_1. \end{align*} The word $s_1s_2$ is reduced, so $\ell(w)=2$, while $\ell(s_1)=1$. For the Hecke product, use $T_{s_1s_2}=T_1T_2$ and the quadratic relation $T_2^2=(q-1)T_2+q$: \begin{align*} T_{s_1s_2}T_2=T_1T_2T_2=T_1T_2^2. \end{align*} Substituting the quadratic relation gives \begin{align*} T_1T_2^2=T_1((q-1)T_2+q). \end{align*} By distributivity and centrality of the scalar $q\in R$, \begin{align*} T_1((q-1)T_2+q)=(q-1)T_1T_2+qT_1. \end{align*} Since $T_1T_2=T_{s_1s_2}$ and $T_1=T_{s_1}$, this becomes \begin{align*} T_{s_1s_2}T_2=qT_{s_1}+(q-1)T_{s_1s_2}. \end{align*} Thus the group algebra product collapses to $s_1$, while the Hecke product keeps an additional $(q-1)T_{s_1s_2}$ term. At the specialisation $q=1$, that extra term vanishes and the formula reduces to $T_{s_1s_2}T_2=T_{s_1}$, matching the group multiplication. [/example] ## The Algebra in Small Rank How much of the general theory is already visible in $S_3$? The algebra $H_q(S_3)$ has two generators, one braid relation, and two quadratic relations. It is the first case where reduced expressions are not unique, because $s_1s_2s_1=s_2s_1s_2$. [example: The Hecke Algebra of S Three] For $S_3$, the simple transpositions are $s_1=(1,2)$ and $s_2=(2,3)$, so $H_q(S_3)$ is generated by $T_1,T_2$ with \begin{align*} T_1^2=(q-1)T_1+q,\quad T_2^2=(q-1)T_2+q,\quad T_1T_2T_1=T_2T_1T_2. \end{align*} The six permutations of $S_3$ have reduced words \begin{align*} e,\quad s_1,\quad s_2,\quad s_1s_2,\quad s_2s_1,\quad s_1s_2s_1. \end{align*} Thus the corresponding standard basis elements are \begin{align*} 1,\quad T_1,\quad T_2,\quad T_1T_2,\quad T_2T_1,\quad T_1T_2T_1. \end{align*} The longest element also has the reduced expression $s_2s_1s_2$, and the braid relation gives \begin{align*} T_{s_1s_2s_1}=T_1T_2T_1=T_2T_1T_2=T_{s_2s_1s_2}. \end{align*} Now compute one product with a right descent. Since $s_1s_2s_1\cdot s_1=s_1s_2$ in $S_3$, multiplication by $s_1$ lowers length from $3$ to $2$. In the Hecke algebra, \begin{align*} (T_1T_2T_1)T_1=T_1T_2T_1^2. \end{align*} Substitute the quadratic relation for $T_1^2$: \begin{align*} T_1T_2T_1^2=T_1T_2((q-1)T_1+q). \end{align*} By distributivity and centrality of scalars in $R=\mathbb Z[q,q^{-1}]$, \begin{align*} T_1T_2((q-1)T_1+q)=(q-1)T_1T_2T_1+qT_1T_2. \end{align*} Therefore \begin{align*} T_1T_2T_1\cdot T_1=qT_1T_2+(q-1)T_1T_2T_1. \end{align*} This small-rank calculation shows both mechanisms at once: the braid relation identifies the two reduced words for the longest permutation, while the quadratic relation reduces non-reduced products back into the six-element standard basis. [/example] The $S_3$ calculation shows the two types of relation working together. Braid relations identify different reduced expressions, while the quadratic relation reduces non-reduced words back into the standard basis. [remark: Specialisation at q Equals One] The specialisation $H_q(S_n)\otimes_R \mathbb Z$, where $q$ acts as $1$, is naturally isomorphic to $\mathbb Z[S_n]$ by $T_i\mapsto s_i$. This is why many constructions for $S_n$ have Hecke analogues: the Hecke algebra is a flat deformation of the group algebra with the same standard basis labels. [/remark] Specialising $q$ at values other than $1$ can change representation-theoretic behaviour, especially over fields where $q$ is a root of unity. In this chapter we keep the generic picture, where the deformation is closest to the characteristic zero representation theory of $S_n$. ## Specht Modules Under $q$-Deformation Which part of the Specht module construction depends on the identity $s_i^2=e$, and which part only depends on the braid and length combinatorics? Classical Specht modules are built from Young tableaux and encode the irreducible representations of $S_n$ over characteristic zero. Ordinary Young symmetrizers cannot be copied unchanged, because the generators $T_i$ are not involutions and the signs used in column antisymmetrisation must be replaced by the two eigenvalues $q$ and $-1$. The Hecke version keeps the same indexing by partitions but replaces the action of adjacent transpositions by operators satisfying the Hecke relations. [definition: Hecke Specht Module] Let $\lambda\vdash n$ be a partition. A Hecke Specht module $S_q^\lambda$ is an $H_q(S_n)$-module over $R$ whose specialisation at $q=1$ is the ordinary Specht module $S^\lambda$ for $S_n$ and whose rank over $R$ is the number of standard Young tableaux of shape $\lambda$. [/definition] The construction can be realised through a chosen tableau model, such as Murphy's cellular basis or a deformation of polytabloids. For the purposes of this course, the important point is that the tableau indexing remains unchanged while the generator action is modified by $q$-dependent coefficients. [quotetheorem:8466] [citeproof:8466] This theorem is the representation-theoretic counterpart of the standard basis theorem. The extension to $\mathbb Q(q)$ is not cosmetic: at special values of $q$, especially roots of unity over a field, the Hecke algebra need not be semisimple and the Specht modules may fail to be simple. For example, over $\mathbb C$ with $q$ a primitive $e$-th root of unity and $2\le e\le n$, the type A Hecke algebra has nonzero radical, so the partition-indexed Specht modules no longer form a complete list of simple modules. The theorem also does not give an explicit matrix formula for each generator on a tableau basis; that depends on the chosen Specht model. What it does provide is the generic classification needed before discussing canonical bases, cells, and the effect of changing the parameter. [example: The Two Specht Modules for S Two] For $n=2$, the partitions are $(2)$ and $(1,1)$, and each has exactly one standard tableau, so the corresponding Hecke Specht modules are one-dimensional over $R=\mathbb Z[q,q^{-1}]$. On a one-dimensional module, the generator $T_1$ acts by multiplication by some scalar $c\in R$, and the quadratic relation forces \begin{align*} (c-q)(c+1)=0. \end{align*} For $S_q^{(2)}$, define $T_1$ to act by $q$. Then \begin{align*} (q-q)(q+1)=0\cdot(q+1)=0, \end{align*} so this action satisfies the defining relation. For $S_q^{(1,1)}$, define $T_1$ to act by $-1$. Then \begin{align*} ((-1)-q)((-1)+1)=(-1-q)\cdot 0=0, \end{align*} so this action also satisfies the defining relation. Thus the two one-dimensional actions are exactly the two scalar roots $q$ and $-1$ of the Hecke quadratic relation. At the specialisation $q=1$, the first action has $T_1$ acting by $1$, which is the identity representation of $S_2$, while the second action has $T_1$ acting by $-1$, which is the sign representation. [/example] The rank one case explains why the two roots in the quadratic relation are chosen as $q$ and $-1$. They deform the two one-dimensional representations of the subgroup generated by a simple reflection. [remark: Tableau Combinatorics Survives] In the generic Hecke setting, standard tableaux still index bases of Specht modules, and partitions still label simple modules. What changes is the action: adjacent swaps now carry coefficients depending on whether the swap preserves, raises, or lowers the tableau order in the chosen model. [/remark] The next structure refines this survival phenomenon. Instead of asking only for a basis indexed by permutations or tableaux, Kazhdan-Lusztig theory asks for a basis with positivity and symmetry properties that remember the deformation parameter. ## The Bar Involution and Kazhdan-Lusztig Basis What new basis becomes visible when the parameter $q$ is treated symmetrically with $q^{-1}$? The standard basis $\{T_w\}$ is well-suited to multiplication, but it is not invariant under the natural operation that reverses $q$ and inverts the Hecke generators; for instance $\overline{T_i}$ already contains both $T_i$ and $1$. Kazhdan-Lusztig theory constructs a new basis adapted to this symmetry. [definition: Bar Involution] The bar involution is the ring semilinear map \begin{align*} \overline{(-)}:H_q(S_n)\to H_q(S_n) \end{align*} determined by $\overline{q}=q^{-1}$, $\overline{T_i}=T_i^{-1}=q^{-1}T_i+(q^{-1}-1)$, and $\overline{ab}=\overline{a}\,\overline{b}$ for $a,b\in H_q(S_n)$ and $1\le i<n$. [/definition] The formula for $T_i^{-1}$ follows from the quadratic relation after solving for the inverse of $T_i$. This involution is compatible with reduced expressions, so it sends $T_w$ to $T_{w^{-1}}^{-1}$ up to the same semilinear convention. Once this symmetry is available, it is natural to ask for a permutation-indexed basis whose elements are fixed by it and whose lower terms are controlled by Bruhat order. [definition: Kazhdan-Lusztig Basis] Let $H_q(S_n)^{1/2}:=H_q(S_n)\otimes_{\mathbb Z[q,q^{-1}]}\mathbb Z[q^{1/2},q^{-1/2}]$. The Kazhdan-Lusztig basis is a basis $\{C_w : w\in S_n\}$ of $H_q(S_n)^{1/2}$ satisfying $\overline{C_w}=C_w$ and \begin{align*} C_w=q^{-\ell(w)/2}\sum_{y\le w} P_{y,w}(q)T_y, \end{align*} where $\le$ is Bruhat order, $P_{w,w}(q)=1$, and $P_{y,w}(q)$ satisfies the Kazhdan-Lusztig degree condition for $y<w$. [/definition] The displayed formula uses the square-root normalisation common in Kazhdan-Lusztig theory. The polynomials $P_{y,w}(q)$ are the Kazhdan-Lusztig polynomials, and the triangular condition says that $C_w$ is built from $T_w$ and terms indexed by smaller elements in Bruhat order. The next theorem is needed because these conditions are not automatic: it proves that the bar-invariant triangular basis actually exists and is unique. Existence and uniqueness of this bar-invariant triangular basis is a standard Kazhdan-Lusztig theorem, and the degree bounds are part of the normalization. The conditions play different roles: bar invariance enforces compatibility with $q\leftrightarrow q^{-1}$, while triangularity prevents the basis element labelled by $w$ from mixing with unrelated Bruhat strata. The result is existential rather than computational: it justifies speaking about Kazhdan-Lusztig polynomials, cells, and canonical transition coefficients after the standard Hecke deformation has been built. [example: The First Kazhdan-Lusztig Element] For $S_2$, write $s=s_1$, so the Bruhat order has $e<s$ and $T_e=1$. In the square-root extension of the Hecke algebra, consider \begin{align*} C_s=q^{-1/2}(T_s+1). \end{align*} The quadratic relation gives \begin{align*} T_s^2=(q-1)T_s+q. \end{align*} Hence \begin{align*} T_s^2-(q-1)T_s=q. \end{align*} Factoring the left side gives \begin{align*} T_s(T_s-(q-1))=q. \end{align*} Multiplying by $q^{-1}$ shows that \begin{align*} T_s^{-1}=q^{-1}T_s-q^{-1}(q-1)=q^{-1}T_s+(q^{-1}-1). \end{align*} Now apply the bar involution, using $\overline{q^{-1/2}}=q^{1/2}$ and $\overline{T_s}=T_s^{-1}$: \begin{align*} \overline{C_s}=q^{1/2}(T_s^{-1}+1). \end{align*} Substitute the displayed formula for $T_s^{-1}$: \begin{align*} \overline{C_s}=q^{1/2}(q^{-1}T_s+(q^{-1}-1)+1). \end{align*} The constant terms combine as $(q^{-1}-1)+1=q^{-1}$, so \begin{align*} \overline{C_s}=q^{1/2}(q^{-1}T_s+q^{-1}). \end{align*} Factoring out $q^{-1}$ gives \begin{align*} \overline{C_s}=q^{1/2}q^{-1}(T_s+1)=q^{-1/2}(T_s+1)=C_s. \end{align*} Thus $C_s$ is bar-invariant. Its expansion has leading term $q^{-1/2}T_s$ and one lower Bruhat term $q^{-1/2}T_e$, so this rank-one case shows explicitly how a Kazhdan-Lusztig basis element adds lower terms to a standard basis element in order to restore bar symmetry. [/example] The example reveals why the Kazhdan-Lusztig basis is not just another relabelling of the standard basis. It mixes permutations according to Bruhat order in a way governed by the deformation parameter. [explanation: Why Kazhdan-Lusztig Theory Belongs Here] The earlier parts of the course turned permutations into tableaux via RSK and then into representations via Specht modules. The Hecke algebra adds a parameter but keeps the permutation basis, the length function, and the tableau indexing of modules. Kazhdan-Lusztig theory adds a second layer: it uses the deformation to define canonical bases whose transition coefficients encode deep representation-theoretic information. In type A, this theory connects to cells, Robinson-Schensted shapes, and refined character theory. The leading lesson for combinatorial representation theory is that bases matter: the same algebra may have a standard basis for multiplication, a Specht-theoretic basis for modules, and a Kazhdan-Lusztig basis for canonical positivity and duality phenomena. [/explanation] The Hecke algebra and its bases show that the same representation-theoretic object can admit several compatible combinatorial models. That theme leads naturally to Kazhdan-Lusztig theory, where canonical bases and positivity refine the earlier tableau and insertion phenomena. # 10. Kazhdan-Lusztig Theory Overview After Chapter 9 introduced the Hecke algebra and its Kazhdan-Lusztig basis, Kazhdan-Lusztig theory enters the course at the point where the combinatorics of permutations, tableaux, and insertion begins to interact with canonical bases. The earlier chapters built concrete models for representations of $S_n$ using tableaux and symmetric functions; this chapter explains how the same tableaux also control the cell structure coming from the Hecke algebra. The main questions are how Bruhat order governs the recursive construction of Kazhdan-Lusztig polynomials, why positivity is a deep representation-theoretic fact, and how type $A$ cells recover the Robinson-Schensted correspondence. ## Bruhat Order, Reduced Words, and Cells The first problem is to put a partial order on a Coxeter group that remembers how reduced expressions contain smaller permutations. For $S_n$, this order can be read from inversions and rank conditions, so it is both algebraic and combinatorial. [definition: Coxeter Length And Reduced Word] Let $(W,S)$ be a Coxeter system. The Coxeter length function is the map \begin{align*} \ell:W\to \mathbb Z_{\ge 0} \end{align*} defined by letting $\ell(w)$ be the least integer $r \ge 0$ such that \begin{align*} w = s_1 s_2 \cdots s_r. \end{align*} Here each $s_i \in S$. A word $s_1 \cdots s_r$ with $r=\ell(w)$ is a reduced word for $w$. [/definition] Reduced words are not unique, but the length function is the grading that drives the Hecke algebra and its canonical basis. In $S_n$, with simple transpositions $s_i=(i,i+1)$, the length of $w$ is the number of inversions of $w$. [example: Reduced Words In S Three] In $S_3$, write permutations in one-line notation and compose from right to left. With $s_1=(1,2)=213$ and $s_2=(2,3)=132$, the word $s_1s_2s_1$ sends $1\mapsto 3$, $2\mapsto 2$, and $3\mapsto 1$, so \begin{align*} s_1s_2s_1=321. \end{align*} Similarly, $s_2s_1s_2$ sends $1\mapsto 3$, $2\mapsto 2$, and $3\mapsto 1$, so \begin{align*} s_2s_1s_2=321. \end{align*} The permutation $321$ has inversions $(1,2)$, $(1,3)$, and $(2,3)$, hence $\ell(321)=3$; since both displayed words have three simple reflections, they are reduced words for $321$. The permutation $312$ has inversions $(1,2)$ and $(1,3)$, hence $\ell(312)=2$. The product $s_2s_1$ sends $1\mapsto 3$, $2\mapsto 1$, and $3\mapsto 2$, so \begin{align*} s_2s_1=312. \end{align*} Now take subwords of the reduced word $s_1s_2s_1$. The empty subword gives $e$, the one-letter subwords give $s_1$ and $s_2$, the adjacent two-letter subwords give $s_1s_2$ and $s_2s_1$, and the full subword gives $s_1s_2s_1=321$. Thus the distinct elements obtained are \begin{align*} e,\ s_1,\ s_2,\ s_1s_2,\ s_2s_1,\ s_1s_2s_1. \end{align*} These are all six elements of $S_3$, so the longest element $321$ contains every element of $S_3$ through subwords of one reduced expression. [/example] The example shows that a reduced word contains many smaller elements as subwords, but it does not yet give a word-independent relation. Bruhat order is introduced to make this containment relation intrinsic. [definition: Bruhat Order] Let $(W,S)$ be a Coxeter system. For $y,w \in W$, write $y \le w$ in Bruhat order if some reduced word for $w$ contains a subword whose product is a reduced word for $y$. [/definition] This definition uses one reduced word for $w$, so the first structural question is whether the comparison depends on that choice. The subword criterion answers this and makes Bruhat intervals computable from any reduced expression. [quotetheorem:8468] [citeproof:8468] The reducedness hypotheses in the subword criterion are essential. If a nonreduced expression is allowed, repeated reflections can create misleading subwords: for instance $s_is_i=e$ contains the one-letter subword $s_i$, even though this expression represents $e$ and should not place $s_i$ below $e$ in Bruhat order. The Coxeter-system assumption is also doing work, because Matsumoto's theorem supplies the braid moves that make the relation independent of the chosen reduced word. What the criterion gives is membership in a Bruhat interval; it does not say that every subword has a distinct product, nor does it describe representation-theoretic cells. Bruhat order provides the indexing poset for Kazhdan-Lusztig polynomials. The cell structure needs more than order, though: it uses multiplication by the Kazhdan-Lusztig basis to group elements that generate the same pieces of a representation. [definition: Kazhdan-Lusztig Preorders And Cells] Let $\mathcal H(W)$ be the Hecke algebra of a Coxeter system $(W,S)$ over $\mathbb Z[q^{1/2},q^{-1/2}]$, and let $\{C_w : w\in W\}$ be its Kazhdan-Lusztig basis. Define preorders $\le_L$, $\le_R$, and $\le_{LR}$ on $W$ as follows. The relation $y \le_L w$ holds if $C_y$ occurs in $hC_w$ for some $h\in \mathcal H(W)$. The relation $y \le_R w$ holds if $C_y$ occurs in $C_wh$ for some $h\in \mathcal H(W)$. The relation $y\le_{LR}w$ is the preorder generated by $\le_L$ and $\le_R$. The equivalence classes for the associated equivalence relations are called left cells, right cells, and two-sided cells. [/definition] Cells should be thought of as the representation-theoretic shadow of the canonical basis. Left multiplication sees left cells, right multiplication sees right cells, and two-sided cells record the coarser blocks generated by both actions. [remark: Cells Versus Bruhat Intervals] Bruhat intervals are order-theoretic objects, while cells are representation-theoretic objects. The definition of cells uses the Kazhdan-Lusztig basis, so two elements may be close in Bruhat order but lie in different cells, or lie in the same cell without forming a small Bruhat interval. [/remark] ## Kazhdan-Lusztig Polynomials and Recursive Computation The second problem is to construct the canonical basis of the Hecke algebra in a way that can be computed from Bruhat order. Kazhdan-Lusztig polynomials are the transition coefficients from the standard basis to this canonical basis. [definition: Hecke Algebra Of A Coxeter System] Let $(W,S)$ be a Coxeter system. The Hecke algebra $\mathcal H(W)$ is the $\mathbb Z[q^{1/2},q^{-1/2}]$-algebra with basis $\{T_w : w\in W\}$ and multiplication determined by the following rules for $s\in S$ and $w\in W$. If $\ell(sw)>\ell(w)$, then \begin{align*} T_sT_w = T_{sw}. \end{align*} If $\ell(sw)<\ell(w)$, then \begin{align*} T_sT_w = qT_{sw}+(q-1)T_w. \end{align*} [/definition] The deformation parameter $q$ records how multiplication changes when a simple reflection shortens an element. To pass from this standard basis to the canonical basis, we need transition coefficients normalized by Bruhat triangularity; these coefficients are the Kazhdan-Lusztig polynomials. [definition: Kazhdan-Lusztig Polynomial] For $y,w\in W$, the Kazhdan-Lusztig polynomial $P_{y,w}(q)\in \mathbb Z[q]$ is defined by the expansion of the Kazhdan-Lusztig basis element $C_w$ in the standard basis: \begin{align*} C_w = q^{-\ell(w)/2}\sum_{y\le w} P_{y,w}(q)T_y. \end{align*} The normalization is $P_{w,w}(q)=1$ and $P_{y,w}(q)=0$ if $y\not\le w$. For $y<w$, the degree condition is \begin{align*} \deg P_{y,w}(q) \le \frac{\ell(w)-\ell(y)-1}{2}. \end{align*} [/definition] The degree bound is what makes the basis canonical: it selects one bar-invariant lift of each Bruhat element. The next question is computational, namely how to find these polynomials from shorter Bruhat intervals without first constructing the entire basis by hand. [quotetheorem:8469] [citeproof:8469] The descent condition $sw<w$ is what makes the recursion point downward in Bruhat order: multiplying $C_{sw}$ by $C_s$ then has the correct leading term for $C_w$. In $S_3$, for instance, if $w=s_1$ and we incorrectly choose $s=s_2$, then $sw=s_2s_1$ has length $2$ rather than $0$; the product $C_{s_2}C_{s_1}$ has leading term indexed by $s_2s_1$, not by $s_1$, so it cannot compute $P_{e,s_1}(q)$ from a smaller interval. The split between $sy<y$ and $sy>y$ is also necessary, because left multiplication by $s$ either transports the lower index directly or produces correction terms from intermediate elements. The theorem is a computational statement, not a positivity statement: the subtraction in the correction sum can hide cancellations, and the recurrence by itself does not explain why final coefficients should be nonnegative. This recursion is the practical engine of the theory. In small symmetric groups it often collapses to constant polynomials, so $S_3$ is a useful first computation before nonconstant examples appear in larger rank. [example: Kazhdan-Lusztig Polynomials In S Three] Let $W=S_3$ with generators $s_1,s_2$, and write \begin{align*} w_0=s_1s_2s_1. \end{align*} The reduced subwords of $s_1s_2s_1$ represent \begin{align*} e,\ s_1,\ s_2,\ s_1s_2,\ s_2s_1,\ s_1s_2s_1, \end{align*} so every element of $S_3$ lies below $w_0$ in Bruhat order. We compute the Kazhdan-Lusztig polynomials from the recursion, using the normalization \begin{align*} P_{x,x}(q)=1. \end{align*} First consider intervals of length difference $1$. For $w=s_i$ and $y=e$, choose $s=s_i$, so $sw=e$ and $sy=s_i>e$. The correction sum has no terms because there is no $z<e$, and $P_{s_i,e}(q)=0$ since $s_i\not\le e$. Hence \begin{align*} P_{e,s_i}(q)=qP_{s_i,e}(q)+P_{e,e}(q)=q\cdot 0+1=1. \end{align*} Next take $w=s_1s_2$ and choose the left descent $s=s_1$, so $sw=s_2$. For $y=e$, the terms with $z<sw=s_2$ are only $z=e$, and $s_1e=s_1>e$, so the correction sum is empty. Also $s_1\not\le s_2$, so \begin{align*} P_{e,s_1s_2}(q)=qP_{s_1,s_2}(q)+P_{e,s_2}(q)=q\cdot 0+1=1. \end{align*} For $y=s_1$, we have $s_1y=e<y$, so \begin{align*} P_{s_1,s_1s_2}(q)=P_{e,s_2}(q)=1. \end{align*} For $y=s_2$, we have $s_1s_2>s_2$, the correction sum is again empty, and \begin{align*} P_{s_2,s_1s_2}(q)=qP_{s_1s_2,s_2}(q)+P_{s_2,s_2}(q)=q\cdot 0+1=1. \end{align*} The same calculation with $s_1$ and $s_2$ interchanged gives \begin{align*} P_{e,s_2s_1}(q)=P_{s_1,s_2s_1}(q)=P_{s_2,s_2s_1}(q)=1. \end{align*} Now compute the interval below $w_0$. Choose $s=s_1$, so $sw_0=s_2s_1$. For $y=e$, the possible correction terms satisfy $z<s_2s_1$ and $s_1z<z$. Among $z=e,s_1,s_2$, only $z=s_1$ satisfies this, because $s_1s_1=e<s_1$. Since $P_{s_1,s_2s_1}(q)=1$, the coefficient $\mu(s_1,s_2s_1)$ is $1$. Therefore \begin{align*} P_{e,w_0}(q)=qP_{s_1,s_2s_1}(q)+P_{e,s_2s_1}(q)-qP_{e,s_1}(q)=q\cdot 1+1-q\cdot 1=1. \end{align*} For $y=s_1$, the first case of the recursion applies because $s_1s_1=e<s_1$, giving \begin{align*} P_{s_1,w_0}(q)=P_{e,s_2s_1}(q)=1. \end{align*} For $y=s_2$, the correction sum is empty, $s_1s_2\not\le s_2s_1$, and \begin{align*} P_{s_2,w_0}(q)=qP_{s_1s_2,s_2s_1}(q)+P_{s_2,s_2s_1}(q)=q\cdot 0+1=1. \end{align*} For $y=s_1s_2$, we have $s_1y=s_2<y$, so \begin{align*} P_{s_1s_2,w_0}(q)=P_{s_2,s_2s_1}(q)=1. \end{align*} For $y=s_2s_1$, the correction sum is empty and \begin{align*} P_{s_2s_1,w_0}(q)=qP_{w_0,s_2s_1}(q)+P_{s_2s_1,s_2s_1}(q)=q\cdot 0+1=1. \end{align*} Together with $P_{x,x}(q)=1$, this covers every comparable pair $y\le w$ in $S_3$. In particular, \begin{align*} P_{e,w_0}(q)=1. \end{align*} Thus $S_3$ is still too small to exhibit a nonconstant Kazhdan-Lusztig polynomial; those first appear in larger type $A$ examples. [/example] The example has no negative coefficients, but the recurrence itself contains subtraction terms and therefore does not explain why all coefficients should be nonnegative. This gap motivates the positivity theorem, which supplies the structural interpretation missing from the algorithm. [quotetheorem:8470] The standard geometric interpretation uses Schubert varieties in the flag variety: the coefficients of $P_{y,w}(q)$ are realized through the graded dimensions of local intersection cohomology groups attached to Schubert varieties. Categorical approaches give parallel interpretations through graded multiplicities in Hecke categories or category $\mathcal O$. [remark: What Positivity Adds] The recursion gives an algorithm, but positivity gives meaning. It says the coefficients count dimensions in a hidden representation-theoretic or geometric object, so cancellations in the recurrence conceal an underlying positive structure. [/remark] ## Type A Cells and the Relationship with RSK The final problem is to identify the cells in $S_n$ without doing recursive Hecke algebra calculations for every permutation. Type $A$ has a remarkable answer: the cell decomposition is governed by the same insertion and recording tableaux used earlier in RSK. [definition: RSK Tableaux Of A Permutation] For $n\ge 1$, the Robinson-Schensted-Knuth correspondence for permutations is the map \begin{align*} \operatorname{RSK}:S_n\to \bigsqcup_{\lambda\vdash n}\operatorname{SYT}(\lambda)\times \operatorname{SYT}(\lambda) \end{align*} defined by \begin{align*} \operatorname{RSK}(w)=(P(w),Q(w)) \end{align*} for $w\in S_n$, where the pair of standard Young tableaux is produced by row insertion applied to the word $w(1)w(2)\cdots w(n)$. The tableau $P(w)$ is the insertion tableau, and $Q(w)$ is the recording tableau. [/definition] The two tableaux record different sides of the permutation: the insertion tableau follows the values inserted, while the recording tableau follows the times at which boxes are created. Since Kazhdan-Lusztig cells are also defined by left and right multiplication, the natural question is whether these two-sided combinatorial records are the cell invariants. [quotetheorem:8471] [citeproof:8471] This theorem is the conceptual bridge from the earlier tableau chapters to Kazhdan-Lusztig theory. Its hypotheses are highly special: the statement uses $W=S_n$, the type $A$ Coxeter generators, and the ordinary RSK correspondence for permutations. For a general Coxeter group there need not be insertion and recording tableaux, so equality of tableaux is not available as a cell invariant. Even in type $A$, the theorem identifies cells rather than Bruhat intervals. For example, in $S_4$ the permutations $1243$, $1342$, and $2341$ have the same recording tableau of shape $(3,1)$, with entries $1,2,3$ across the first row and entry $4$ in the second row. They hence lie in the same left cell, while their Coxeter lengths are $1$, $2$, and $3$; the cell information is recording-tableau information, not the data of a small Bruhat interval. The two-sided cells are indexed by partitions of $n$, just as irreducible representations of $S_n$ are, and the individual left cells of a fixed shape are indexed by standard tableaux of that shape. [example: Left Cells Of S Four] By *Type A Cell Classification By RSK*, two permutations in $S_4$ lie in the same left cell exactly when they have the same recording tableau $Q(w)$. Thus each left cell is obtained by fixing a standard Young tableau $T$ with $4$ boxes and taking \begin{align*} \{w\in S_4:Q(w)=T\}. \end{align*} We count the possible recording tableaux by shape. For shape $(4)$, the entries must form the single row $1,2,3,4$, so there is $1$ left cell of shape $(4)$. For shape $(3,1)$, write the top row entries as $a<b<c$ and the lower entry as $d$ below $a$. Since entries increase along rows and columns, $a=1$. The entry $d$ can be $2$, $3$, or $4$, and after choosing $d$, the remaining two entries fill the positions $b<c$ in increasing order. Hence there are $3$ standard tableaux of shape $(3,1)$, giving $3$ left cells of that shape. For shape $(2,2)$, the two standard tableaux are the one with top row $1,2$ and bottom row $3,4$, and the one with top row $1,3$ and bottom row $2,4$. Thus there are $2$ left cells of shape $(2,2)$. By the same row-and-column increase condition, shape $(2,1,1)$ has $3$ standard tableaux, and shape $(1,1,1,1)$ has only the single column $1,2,3,4$. Therefore the shapes and numbers of left cells in $S_4$ are \begin{align*} (4):1,\quad (3,1):3,\quad (2,2):2,\quad (2,1,1):3,\quad (1,1,1,1):1. \end{align*} The unique tableau of shape $(4)$ is $Q(1234)$, so it gives the left cell containing $1234$. The unique tableau of shape $(1,1,1,1)$ is $Q(4321)$, so it gives the left cell containing $4321$. The three tableaux of shape $(3,1)$ give three distinct left cells, each consisting exactly of the permutations whose RSK recording tableau is that chosen tableau. [/example] For representation-theoretic use, the next question is not only which recording tableaux occur but how large the corresponding cell modules are. Fixing a recording tableau leaves exactly the insertion tableau free, so RSK turns cell size into a tableau-counting statement. [quotetheorem:8472] [citeproof:8472] This size formula is a useful check on the classification, but it depends on fixing a tableau inside a single RSK shape. If one fixes only the shape $\lambda$, both $P$ and $Q$ vary, giving $(f_\lambda)^2$ permutations rather than one cell of size $f_\lambda$. If one fixes a tableau shape that is not the common shape of $P(w)$ and $Q(w)$, there is no RSK fibre of the stated kind. Thus the hypothesis that $T$ is a standard Young tableau of shape $\lambda\vdash n$ is exactly what converts cell size into a single tableau-counting problem. Summing over all left cells gives \begin{align*} \sum_{\lambda\vdash n} (f_\lambda)^2 = n!, \end{align*} which is the usual RSK enumeration of permutations. [example: Cell Sizes In S Four] For $S_4$, compute $f_\lambda$ by counting standard Young tableaux of each shape $\lambda\vdash 4$. The shapes are \begin{align*} (4),\ (3,1),\ (2,2),\ (2,1,1),\ (1,1,1,1). \end{align*} For shape $(4)$, row-increasing forces the single row to be $1,2,3,4$, so $f_{(4)}=1$. For shape $(3,1)$, write the top row as $a<b<c$ and the lower entry below $a$ as $d$. The top-left entry must be $a=1$. Once $d$ is chosen from $\{2,3,4\}$, the remaining two entries fill $b<c$ in increasing order, so $f_{(3,1)}=3$. For shape $(2,2)$, write the rows as $a<b$ and $c<d$, with columns $a<c$ and $b<d$. Again $a=1$. If $b=2$, then $c=3$ and $d=4$. If $b=3$, then $c=2$ and $d=4$. If $b=4$, then $d$ would have to be greater than $4$, impossible. Hence $f_{(2,2)}=2$. Transposing tableaux gives a bijection from shape $(3,1)$ to shape $(2,1,1)$, so $f_{(2,1,1)}=3$. For shape $(1,1,1,1)$, column-increasing forces the single column to be $1,2,3,4$, so $f_{(1,1,1,1)}=1$. By *Size Of Type A Cells*, a left cell with fixed recording tableau of shape $\lambda$ has size $f_\lambda$. Therefore the left-cell sizes in $S_4$ are \begin{align*} 1,\ 3,\ 2,\ 3,\ 1 \end{align*} for the shapes $(4),(3,1),(2,2),(2,1,1),(1,1,1,1)$ respectively, and each shape contributes one left cell for each standard tableau of that shape. The total number of permutations is therefore \begin{align*} 1^2+3^2+2^2+3^2+1^2=1+9+4+9+1=24. \end{align*} This recovers all elements of $S_4$, since $|S_4|=4!=24$. [/example] The overview ends with a useful slogan for the rest of the course: Kazhdan-Lusztig theory replaces arbitrary bases by canonical bases, and in type $A$ the resulting cells are not mysterious new combinatorial objects. They are the insertion and recording classes already present in RSK, now interpreted through the Hecke algebra. Kazhdan-Lusztig theory reveals that the combinatorics of tableaux and permutations was already pointing toward canonical bases all along. The next chapter uses that insight to connect crystals, canonical bases, and tableau rules into a single framework. # 11. Canonical Bases and Crystals This chapter builds on the semistandard tableau crystals and Littlewood-Richardson rule of Chapter 7, the Hecke-algebra canonical-basis viewpoint of Chapters 9 and 10, and the earlier material on Schur functions and tensor products. It explains why tableaux and words are not isolated combinatorial devices, but shadows of bases in quantum group representations. The guiding question is how a representation with coefficients in a parameter $q$ can have a preferred basis whose limiting behaviour at $q=0$ becomes a directed coloured graph. In type $A$, that graph is the familiar world of semistandard tableaux, and the crystal operators are the combinatorial traces of the Chevalley generators. ## From Quantum Groups to Canonical Bases What extra structure is gained by deforming the enveloping algebra of a semisimple [Lie algebra](/page/Lie%20Algebra)? At $q=1$, an ordinary highest-weight module has many natural-looking weight bases, and a [change of basis](/page/Change%20Of%20Basis) inside a weight space can destroy any proposed positivity or compatibility with tensor products. The quantum deformation keeps track of powers of $q$, so bar-invariance and integral lattices can distinguish one normalization from all nearby deformations. The answer is therefore not only representation-theoretic; the deformation exposes bases with integrality, positivity, and compatibility with tensor products that are difficult to isolate in the undeformed setting. We use standard semisimple-Lie-algebra notation in this chapter. The set $I$ indexes the simple roots, and the Cartan matrix $(a_{ij})$ records their pairings. The positive integers $d_i$ symmetrize the matrix, so $d_i a_{ij}=d_j a_{ji}$, and $q_i=q^{d_i}$ is the corresponding deformation parameter for the $i$-th simple root. For $r\ge 0$, the divided power notation means \begin{align*} E_i^{(r)}=\frac{E_i^r}{[r]_{q_i}!},\qquad F_i^{(r)}=\frac{F_i^r}{[r]_{q_i}!}, \end{align*} where $[r]_{q_i}!$ is the product of the $q_i$-integers $[1]_{q_i},\dots,[r]_{q_i}$, with $[0]_{q_i}!=1$. [definition: Quantum Enveloping Algebra] Let $\mathfrak{g}$ be a complex semisimple Lie algebra with Cartan matrix $(a_{ij})_{i,j\in I}$ and symmetrizing integers $d_i$ such that $d_i a_{ij}=d_j a_{ji}$. Put $q_i=q^{d_i}$. The quantum enveloping algebra $U_q(\mathfrak{g})$ is the $\mathbb{Q}(q)$-algebra generated by $E_i,F_i,K_i,K_i^{-1}$ for $i \in I$, subject to \begin{align*} K_iK_i^{-1}=K_i^{-1}K_i=1,\qquad K_iK_j=K_jK_i, \end{align*} \begin{align*} K_iE_jK_i^{-1}=q_i^{a_{ij}}E_j,\qquad K_iF_jK_i^{-1}=q_i^{-a_{ij}}F_j, \end{align*} \begin{align*} E_iF_j-F_jE_i=\delta_{ij}\frac{K_i-K_i^{-1}}{q_i-q_i^{-1}}, \end{align*} and, for $i\ne j$, the quantum Serre relations \begin{align*} \sum_{r=0}^{1-a_{ij}}(-1)^r E_i^{(r)}E_jE_i^{(1-a_{ij}-r)}=0,\qquad \sum_{r=0}^{1-a_{ij}}(-1)^r F_i^{(r)}F_jF_i^{(1-a_{ij}-r)}=0, \end{align*} with divided powers as defined above. [/definition] The generators $E_i$ and $F_i$ deform the raising and lowering operators from ordinary highest-weight theory, while the $K_i$ record weights. The deformation is arranged so that, after a suitable specialization at $q=1$, one recovers the usual enveloping algebra $U(\mathfrak{g})$. [example: The Rank One Quantum Group] For $\mathfrak{g}=\mathfrak{sl}_2$, the algebra $U_q(\mathfrak{sl}_2)$ has generators $E,F,K,K^{-1}$. For $r\ge 1$, set \begin{align*} [r]_q=\frac{q^r-q^{-r}}{q-q^{-1}}. \end{align*} Multiplying numerator and denominator by $q^{r-1}$ gives \begin{align*} [r]_q=q^{r-1}+q^{r-3}+\cdots+q^{-(r-3)}+q^{-(r-1)}. \end{align*} The irreducible highest-weight module $V(n)$ has basis $v_0,v_1,\dots,v_n$, with $v_0$ highest weight, and we use the normalization \begin{align*} Fv_j=[j+1]_qv_{j+1}. \end{align*} \begin{align*} Ev_j=[n-j+1]_qv_{j-1}. \end{align*} \begin{align*} Kv_j=q^{n-2j}v_j, \end{align*} where $v_{-1}=v_{n+1}=0$. The $K$-action records the weight string explicitly: moving from $v_j$ to $v_{j+1}$ changes the exponent of $q$ from $n-2j$ to $n-2j-2$, so $F$ lowers the $\mathfrak{sl}_2$ weight by $2$, while $E$ raises it by $2$. These formulas satisfy the rank-one quantum relations on each basis vector. For the lowering operator, \begin{align*} KF K^{-1}v_j=K F(q^{-n+2j}v_j)=q^{-n+2j}[j+1]_qK v_{j+1}=q^{-2}[j+1]_qv_{j+1}=q^{-2}Fv_j. \end{align*} Similarly, \begin{align*} KEK^{-1}v_j=K E(q^{-n+2j}v_j)=q^{-n+2j}[n-j+1]_qK v_{j-1}=q^{2}[n-j+1]_qv_{j-1}=q^{2}Ev_j. \end{align*} For the commutator relation, first compute \begin{align*} EFv_j=E([j+1]_qv_{j+1})=[j+1]_q[n-j]_qv_j. \end{align*} Also \begin{align*} FEv_j=F([n-j+1]_qv_{j-1})=[n-j+1]_q[j]_qv_j. \end{align*} Using the definition of $[r]_q$, the coefficient difference is \begin{align*} [j+1]_q[n-j]_q-[n-j+1]_q[j]_q=\frac{(q^{j+1}-q^{-j-1})(q^{n-j}-q^{-n+j})-(q^{n-j+1}-q^{-n+j-1})(q^j-q^{-j})}{(q-q^{-1})^2}. \end{align*} Expanding the numerator gives \begin{align*} q^{n+1}-q^{2j+1-n}-q^{n-2j-1}+q^{-n-1}-q^{n+1}+q^{n-2j+1}+q^{2j-n-1}-q^{-n-1}. \end{align*} The first and fifth terms cancel, and the fourth and eighth terms cancel, leaving \begin{align*} q^{n-2j+1}-q^{n-2j-1}-q^{2j+1-n}+q^{2j-n-1}=(q-q^{-1})(q^{n-2j}-q^{-n+2j}). \end{align*} Therefore \begin{align*} (EF-FE)v_j=\frac{q^{n-2j}-q^{-n+2j}}{q-q^{-1}}v_j=\frac{K-K^{-1}}{q-q^{-1}}v_j. \end{align*} Thus $V(n)$ is still a single string $v_0\to v_1\to\cdots\to v_n$, but the arrows carry the $q$-integer coefficients $[j+1]_q$ and $[n-j+1]_q$; in the crystal limit the coefficients are discarded and the surviving data are the directed moves along this string. [/example] The rank one example suggests the central problem: among all possible bases of a module, find one whose transition coefficients, tensor product behaviour, and specialization properties are controlled by the quantum structure. A preferred basis must be distinguished by more than its weights, since many weight bases exist. The next ingredient is an involution that compares the $q$ and $q^{-1}$ worlds and makes a normalization condition meaningful. [definition: Bar Involution] Let $V$ be an integrable $U_q(\mathfrak{g})$-module over $\mathbb{Q}(q)$, and let $\overline{\phantom{x}}:U_q(\mathfrak{g})\to U_q(\mathfrak{g})$ be the algebra bar involution determined by $\overline{q}=q^{-1}$, $\overline{E_i}=E_i$, $\overline{F_i}=F_i$, and $\overline{K_i}=K_i^{-1}$. A bar involution on $V$ is a semilinear involution $\overline{\phantom{v}}:V\to V$ satisfying $\overline{qv}=q^{-1}\overline{v}$ and $\overline{xv}=\overline{x}\,\overline{v}$ for all $x\in U_q(\mathfrak{g})$ and $v\in V$. [/definition] The bar involution is the device that distinguishes a preferred quantum basis from an arbitrary deformation of a classical basis. It forces a symmetry between positive and negative powers of $q$. To turn that symmetry into an actual basis, we add an integral lattice and require a triangular leading term relative to a standard monomial or PBW-type basis. [definition: Canonical Basis] Let $V$ be an integrable highest-weight $U_q(\mathfrak{g})$-module equipped with a bar involution, an integral form $V_{\mathbb{Z}[q,q^{-1}]}$, an ordered reference basis $M$ inside that integral form, and a choice of positive part $q\mathbb{Z}[q]$ for triangular error terms. A canonical basis relative to this normalization data is a basis $G=\{G_m:m\in M\}$ of $V$ such that each $G_m$ lies in the integral form, is fixed by the bar involution, and has triangular expansion \begin{align*} G_m=m+\sum_{m'<m} a_{m,m'}m' \end{align*} with coefficients $a_{m,m'}\in q\mathbb{Z}[q]$ after expressing all terms in the chosen ordered reference basis. [/definition] The definition hides a major theorem: for the modules appearing in this course, such bases exist and are unique after the normalization data have been fixed. Once such a basis exists, the next question is why it matters combinatorially. The key representation-theoretic payoff is that natural products and decompositions have non-negative coefficients in this basis. In the finite-type canonical and global bases used here, the relevant multiplication and projection coefficients are non-negative Laurent polynomials after the standard normalization. In type $A$, the crystal limit turns tensor-product multiplicities into counts of highest-weight vertices, and those counts are the Littlewood--Richardson coefficients. This positivity discussion is structural context rather than a proof in the course. The hypotheses are part of the content: the positivity concerns a specific canonical or global basis, with its finite-type geometric construction and its bar-invariant integral normalization. It is not a statement about arbitrary bases of a quantum-group module, nor does it assert positivity for every symmetrizable Kac-Moody type or for every possible comultiplication normalization. Its role here is to explain why the combinatorial rules encountered earlier count objects rather than produce alternating sums, and to prepare for the crystal limit where those counts become highest-weight vertices. ## The Crystal Limit How can a basis survive after the parameter $q$ is sent to $0$? Individual matrix coefficients may vanish or blow up, so the correct object is not a vector-space basis over $\mathbb{Q}(q)$ but a lattice together with its reduction modulo $q$. The resulting structure remembers only the leading term of each raising and lowering operation. [definition: Crystal Lattice] Let $V$ be an integrable $U_q(\mathfrak{g})$-module, and let $\widetilde e_i,\widetilde f_i:V\to V$ be the Kashiwara operators defined from the $i$-string decomposition of $V$. A crystal lattice is an $A_0$-submodule $L \subset V$, where $A_0$ is the ring of rational functions regular at $q=0$, such that $V \cong \mathbb{Q}(q) \otimes_{A_0} L$ and the restrictions satisfy $\widetilde e_i|_L,\widetilde f_i|_L:L\to L$ for all $i \in I$. [/definition] The crystal lattice solves the problem of controlling what has a finite leading term at $q=0$. It still does not specify which residue classes should be the vertices of the limiting graph. This motivates the following definition, which adds a basis of $L/qL$ and requires the Kashiwara operators to act as partial maps on that basis. [definition: Crystal Basis] Let $V$ be an integrable $U_q(\mathfrak{g})$-module. A crystal basis is a pair $(L,B)$ where $L$ is a crystal lattice, $B$ is a $\mathbb{Q}$-basis of $L/qL$, and the induced partial maps $\widetilde e_i,\widetilde f_i:L/qL\to (L/qL)\cup\{0\}$ satisfy $\widetilde e_i B \subset B \cup \{0\}$, $\widetilde f_i B \subset B \cup \{0\}$, and $\widetilde f_i b=b'$ if and only if $\widetilde e_i b'=b$. [/definition] A crystal basis turns linear representation theory into a coloured directed graph. Vertices are basis elements, an $i$-coloured edge $b\to b'$ records $\widetilde f_i b=b'$, and the partial inverse property records that $\widetilde e_i$ reverses that edge. To compare such graphs across different modules, we need an intrinsic definition that records the same data without mentioning lattices or $q$. [definition: Abstract Crystal] Let $P$ be the weight lattice of a Cartan datum indexed by $I$, with simple roots $\alpha_i$ and simple coroots $h_i$. An abstract crystal consists of a set $B$, maps $\operatorname{wt}:B\to P$, $\varepsilon_i,\varphi_i:B\to \mathbb{Z}\cup\{-\infty\}$, and partial maps $e_i,f_i:B\to B\cup\{0\}$ for $i\in I$, satisfying the following axioms for all $b,b'\in B$ and $i\in I$: \begin{align*} \varphi_i(b)=\varepsilon_i(b)+\langle h_i,\operatorname{wt}(b)\rangle. \end{align*} If $e_i b\in B$, then \begin{align*} \operatorname{wt}(e_i b)=\operatorname{wt}(b)+\alpha_i,\qquad \varepsilon_i(e_i b)=\varepsilon_i(b)-1,\qquad \varphi_i(e_i b)=\varphi_i(b)+1. \end{align*} If $f_i b\in B$, then \begin{align*} \operatorname{wt}(f_i b)=\operatorname{wt}(b)-\alpha_i,\qquad \varepsilon_i(f_i b)=\varepsilon_i(b)+1,\qquad \varphi_i(f_i b)=\varphi_i(b)-1. \end{align*} The partial maps are inverse along each coloured string: \begin{align*} f_i b=b'\quad\text{if and only if}\quad e_i b'=b. \end{align*} If $\varphi_i(b)=-\infty$, then $e_i b=f_i b=0$. [/definition] The functions $\varepsilon_i$ and $\varphi_i$ measure how far a vertex can move along an $i$-string. They replace the actual coefficients of $E_i$ and $F_i$ with the length data needed for tensor products. The foundational question is whether the highest-weight modules in the course always admit such a graph model. [quotetheorem:8473] The integrability and highest-weight hypotheses are essential. If a module has no highest-weight vector, its crystal need not be generated from a single source vertex, and the uniqueness statement by highest weight no longer determines the graph. If integrability is dropped, the $i$-strings can fail to be finite, so the functions $\varepsilon_i$ and $\varphi_i$ no longer behave like finite string lengths. The theorem also does not classify arbitrary abstract crystals; it singles out the crystals that come from integrable highest-weight modules. This distinction matters below, because tensor product components and tableau models are recognized by finding highest-weight vertices inside graphs already known to be genuine crystals. [example: The Crystal of an Sl Two Module] For the irreducible $U_q(\mathfrak{sl}_2)$-module $V(n)$, choose crystal vertices $b_j$ to be the residue classes of the weight-string basis vectors $v_j$ for $0\le j\le n$. Since \begin{align*} Kv_j=q^{n-2j}v_j, \end{align*} the vertex $b_j$ has $\mathfrak{sl}_2$ weight $n-2j$. The Kashiwara operator $\widetilde f_1$ moves one step down the string, so \begin{align*} f_1(b_j)=b_{j+1}\quad\text{for }0\le j<n, \end{align*} and the string stops at the last basis vector: \begin{align*} f_1(b_n)=0. \end{align*} Similarly, $\widetilde e_1$ moves one step up the string, so \begin{align*} e_1(b_j)=b_{j-1}\quad\text{for }1\le j\le n, \end{align*} and \begin{align*} e_1(b_0)=0. \end{align*} Thus the whole crystal is the single coloured chain \begin{align*} b_0 \xrightarrow{1} b_1 \xrightarrow{1} \cdots \xrightarrow{1} b_n. \end{align*} At $b_j$, there are exactly $j$ possible upward moves and $n-j$ possible downward moves, so \begin{align*} \varepsilon_1(b_j)=j,\qquad \varphi_1(b_j)=n-j. \end{align*} These values satisfy the abstract crystal identity because \begin{align*} \varepsilon_1(b_j)+\operatorname{wt}(b_j)=j+(n-2j)=n-j=\varphi_1(b_j). \end{align*} The crystal therefore remembers the rank-one representation as a finite string: the $q$-integer coefficients in the module action disappear, while the allowed upward and downward moves remain. [/example] The rank one picture is the local model for every crystal. In higher rank, each colour $i$ gives an $\mathfrak{sl}_2$-string, and the interaction among colours carries the representation-theoretic content. ## Tensor Products of Crystals What happens to the crystal when two representations are tensored? At the vector-space level, tensor products involve coproduct formulas in $U_q(\mathfrak{g})$. At the crystal level, these formulas collapse to a rule deciding which tensor factor an operator acts on. [definition: Tensor Product Crystal] Let $B_1$ and $B_2$ be crystals with weight lattice $P$. Their tensor product is the set $B_1\otimes B_2=\{b_1\otimes b_2:b_1\in B_1, b_2\in B_2\}$. Its weight map is \begin{align*} \operatorname{wt}:B_1\otimes B_2\to P,\qquad \operatorname{wt}(b_1\otimes b_2)=\operatorname{wt}(b_1)+\operatorname{wt}(b_2). \end{align*} For each $i\in I$, its string functions are \begin{align*} \varepsilon_i(b_1\otimes b_2)&=\max\{\varepsilon_i(b_1),\,\varepsilon_i(b_2)-\langle h_i,\operatorname{wt}(b_1)\rangle\}. \end{align*} \begin{align*} \varphi_i(b_1\otimes b_2)&=\max\{\varphi_i(b_2),\,\varphi_i(b_1)+\langle h_i,\operatorname{wt}(b_2)\rangle\}. \end{align*} For each $i\in I$, the crystal operators are partial maps $e_i,f_i:B_1\otimes B_2\to (B_1\otimes B_2)\cup\{0\}$. For $f_i$, act on the first tensor factor when $\varphi_i(b_1)>\varepsilon_i(b_2)$ and on the second tensor factor when $\varphi_i(b_1)\le \varepsilon_i(b_2)$. For $e_i$, act on the first tensor factor when $\varphi_i(b_1)\ge \varepsilon_i(b_2)$ and on the second tensor factor when $\varphi_i(b_1)<\varepsilon_i(b_2)$. [/definition] The strict and weak inequalities differ in the two rules so that $e_i$ and $f_i$ remain partial inverses. This convention matches the reading order used below for type $A$ tableaux. With tensor products available, representation decomposition can be read from connected components of the crystal graph. [quotetheorem:8474] [citeproof:8474] This theorem turns decomposition of tensor products into graph search. Instead of diagonalizing operators or constructing intertwiners, we find vertices annihilated by all raising crystal operators. The decomposition hypothesis matters: outside a semisimple highest-weight setting, a tensor product may have extensions rather than a direct sum of irreducibles, and a crystal graph by itself does not record extension data. For instance, in modular representation theory for algebraic groups over a field of characteristic $p$, Weyl modules can have the same composition factors as a direct sum while sitting in a non-split extension; a crystal-like graph of weights and coloured moves would remember the factors but not the extension class. The integrability condition is also needed so that each colour breaks into finite strings with well-defined highest points. In the type $A$ applications below, these hypotheses are satisfied for the polynomial representations under discussion, so the graph search recovers the Littlewood-Richardson multiplicities. [example: Tensor Product for Sl Two] Let $B(1)=\{b_0,b_1\}$, with \begin{align*} \operatorname{wt}(b_0)=1,\qquad \operatorname{wt}(b_1)=-1,\qquad f_1(b_0)=b_1,\qquad f_1(b_1)=0. \end{align*} The tensor product $B(1)\otimes B(1)$ has the four vertices $b_0\otimes b_0$, $b_0\otimes b_1$, $b_1\otimes b_0$, and $b_1\otimes b_1$. Their weights are computed by adding weights: \begin{align*} \operatorname{wt}(b_0\otimes b_0)=1+1=2. \end{align*} \begin{align*} \operatorname{wt}(b_0\otimes b_1)=1+(-1)=0. \end{align*} \begin{align*} \operatorname{wt}(b_1\otimes b_0)=(-1)+1=0. \end{align*} \begin{align*} \operatorname{wt}(b_1\otimes b_1)=(-1)+(-1)=-2. \end{align*} For $B(1)$ we have $\varepsilon_1(b_0)=0$, $\varphi_1(b_0)=1$, $\varepsilon_1(b_1)=1$, and $\varphi_1(b_1)=0$. The tensor product rule gives \begin{align*} f_1(b_0\otimes b_0)=f_1(b_0)\otimes b_0=b_1\otimes b_0, \end{align*} because $\varphi_1(b_0)=1>\varepsilon_1(b_0)=0$. Next, \begin{align*} f_1(b_1\otimes b_0)=b_1\otimes f_1(b_0)=b_1\otimes b_1, \end{align*} because $\varphi_1(b_1)=0\le \varepsilon_1(b_0)=0$. Finally, \begin{align*} f_1(b_1\otimes b_1)=b_1\otimes f_1(b_1)=0, \end{align*} so these three vertices form the chain \begin{align*} b_0\otimes b_0 \xrightarrow{1} b_1\otimes b_0 \xrightarrow{1} b_1\otimes b_1. \end{align*} Its highest vertex has weight $2$, so this component is the crystal $B(2)$. The remaining vertex is $b_0\otimes b_1$. Since $\varphi_1(b_0)=1\le \varepsilon_1(b_1)=1$, the lowering rule acts on the second tensor factor: \begin{align*} f_1(b_0\otimes b_1)=b_0\otimes f_1(b_1)=0. \end{align*} Since $\varphi_1(b_0)=1\ge \varepsilon_1(b_1)=1$, the raising rule acts on the first tensor factor: \begin{align*} e_1(b_0\otimes b_1)=e_1(b_0)\otimes b_1=0. \end{align*} Thus $b_0\otimes b_1$ is an isolated highest-weight component of weight $0$, namely $B(0)$. Therefore \begin{align*} B(1)\otimes B(1)\cong B(2)\sqcup B(0), \end{align*} which is the crystal-level form of the representation decomposition $V(1)\otimes V(1)\cong V(2)\oplus V(0)$. [/example] The same principle is what Littlewood-Richardson theory does for type $A$, but crystals supply local operators and connected components rather than only the final multiplicities. ## Type A Tableaux as Crystals Why do semistandard tableaux appear in the representation theory of $GL_n$ and $\mathfrak{sl}_n$? Their entries encode weights, and the crystal operators modify entries by the smallest possible local move that preserves semistandardness. This section identifies the tableau model with the highest-weight crystals from the quantum group construction. [definition: Semistandard Tableau Crystal] Fix $n\ge 1$ and a partition $\lambda$ with at most $n$ parts. Let $B(\lambda)$ be the set of semistandard Young tableaux of shape $\lambda$ with entries in $\{1,\dots,n\}$. The weight map is \begin{align*} \operatorname{wt}:B(\lambda)\to \mathbb{Z}_{\ge 0}^{n},\qquad \operatorname{wt}(T)=(m_1,\dots,m_n), \end{align*} where $m_j$ is the number of entries equal to $j$ in $T$. [/definition] This definition gives the vertices and the weight function, but it does not yet explain the coloured edges. The missing data are the partial maps $e_i$ and $f_i$ that change a tableau by one simple root. A naive entry change is not enough: in a column containing $1$ above $2$, changing the upper $1$ to $2$ would violate strict increase down columns, while changing the wrong $2$ to $1$ can violate weak increase along a row. This motivates a signature rule: read the tableau as a word, cancel paired letters, and alter the unique unpaired entry selected by the rule. [definition: Type A Signature Rule] For $i\in\{1,\dots,n-1\}$, define partial maps $e_i,f_i:B(\lambda)\to B(\lambda)\cup\{0\}$ as follows. For a semistandard tableau $T\in B(\lambda)$, form the row reading word by reading rows from bottom to top and reading each row from left to right, then keep only the letters $i$ and $i+1$. Replace each $i$ by $+$ and each $i+1$ by $-$. Cancel adjacent $-+$ pairs until none remain. The value $f_i(T)$ is obtained by changing the entry corresponding to the rightmost uncancelled $+$ from $i$ to $i+1$, and is $0$ if no such $+$ exists. The value $e_i(T)$ is obtained by changing the entry corresponding to the leftmost uncancelled $-$ from $i+1$ to $i$, and is $0$ if no such $-$ exists. [/definition] The cancellation rule records the same competition between tensor factors as the abstract tensor product rule. Its main content is that the prescribed entry change preserves the semistandard tableau conditions. The next theorem states that this local rule gives the representation-theoretic crystal, not merely a graph that resembles one. [quotetheorem:8475] [citeproof:8475] This theorem is the bridge from quantum groups back to the combinatorics of the first lectures. It explains why the same tableaux that index Schur functions also carry raising and lowering operators. The hypotheses are not cosmetic: the fixed alphabet $\{1,\dots,n\}$ and the semistandard row-and-column conditions are what make the signature moves stay inside a highest-weight type $A$ crystal. If arbitrary fillings are allowed, changing the selected entry can break column-strictness or move outside the component generated by the highest-weight tableau. The statement is also type-specific; other Lie types have tableau-like models only after adding extra local rules, so the type $A$ signature convention should not be read as a universal crystal construction. [example: Crystal Operators on a Tableau] Let $T$ have top row $113$, middle row $23$, and bottom row $3$. Reading rows from bottom to top and left to right gives the word $3\,2\,3\,1\,1\,3$. Counting entries gives two letters equal to $1$, one letter equal to $2$, and three letters equal to $3$, so \begin{align*} \operatorname{wt}(T)=(2,1,3). \end{align*} For $i=1$, keep only the letters $1$ and $2$ in the row reading word: \begin{align*} 3\,2\,3\,1\,1\,3 \longmapsto 2\,1\,1. \end{align*} Replacing $1$ by $+$ and $2$ by $-$ gives \begin{align*} 2\,1\,1 \longmapsto -++. \end{align*} The adjacent pair formed by the first $-$ and the first $+$ cancels, leaving one uncancelled $+$ corresponding to the second $1$ in the top row. By the type $A$ signature rule, $f_1$ changes that selected $1$ to $2$. Hence $f_1(T)$ has top row $123$, middle row $23$, and bottom row $3$. Its rows are weakly increasing, and its columns satisfy $1<2<3$ in the first column and $2<3$ in the second column, so the result is semistandard. Its weight is \begin{align*} \operatorname{wt}(f_1(T))=(1,2,3). \end{align*} Since the reduced signature of $T$ has no uncancelled $-$, the same rule gives \begin{align*} e_1(T)=0. \end{align*} Now compute the signature of $f_1(T)$. Its row reading word is $3\,2\,3\,1\,2\,3$, so the $1,2$-subword is \begin{align*} 2\,1\,2. \end{align*} The corresponding signs are \begin{align*} 2\,1\,2 \longmapsto -+-. \end{align*} Cancelling the adjacent $-+$ leaves one uncancelled $-$, and that $-$ is attached to the entry just changed from $1$ to $2$. Therefore $e_1$ changes this $2$ back to $1$, so \begin{align*} e_1(f_1(T))=T. \end{align*} This example shows the partial inverse property of the crystal operators in a concrete tableau: the signature selects exactly the entry whose change can be reversed. [/example] The example illustrates how a global-looking operation on a tableau is computed from a word. The choice of reading word matters only because it fixes a convention compatible with tensor products and the plactic relations. [remark: Plactic Compatibility] The type $A$ crystal operators are compatible with Knuth equivalence: if two words have the same insertion tableau, then applying $e_i$ or $f_i$ to the words, when defined, gives words whose insertion tableaux agree with the result of applying the corresponding operator to the tableau. [/remark] This compatibility is why crystals fit naturally with RSK and the plactic monoid. The insertion tableau is not merely a shape invariant; it retains enough information to support the crystal operators. ## Global Bases and the Return from the Crystal After passing to $q=0$, how much information has been lost? The crystal graph has forgotten coefficients, but the global basis reconstructs canonical vectors whose leading terms are the crystal elements. This is the direction from combinatorics back to representation theory. [definition: Lower Global Basis] Let $(L,B)$ be the crystal basis of an integrable highest-weight module $V$. A lower global basis is the image of a map \begin{align*} G:B\to V \end{align*} such that the set $\{G(b):b\in B\}$ is a basis of $V$, each $G(b)$ is bar-invariant, and $G(b) \equiv b \pmod{qL}$ for every $b\in B$. [/definition] The congruence condition says that each global basis vector is the unique bar-invariant lift of a crystal basis element with the prescribed leading term. Thus the crystal is the mod $q$ shadow of a basis living over $\mathbb{Q}(q)$. The remaining structural statement is that this lifting process works for every highest-weight module considered here. [quotetheorem:8476] The course uses this theorem as the structural guarantee that the passage to a crystal has not discarded the distinguished basis forever. The global basis is the canonical way back from the combinatorial shadow to actual vectors in the quantum module, with each crystal element serving as the leading label of one preferred lift. The uniqueness depends on both pieces of data: the chosen crystal basis fixes the leading term modulo $qL$, while the bar involution fixes the lift among all vectors with that leading term. For example, in a rank-one string suppose a lift $G(b)$ lies in $L$ and $v\in L$ has nonzero residue in another weight space compatible with the lattice. Then $G(b)+qv$ has the same residue class as $G(b)$ modulo $qL$, so the residue condition by itself cannot select a single lift. Conversely, in the Laurent [polynomial ring](/page/Polynomial%20Ring) the element $1$ is bar-invariant, but $1+q$ has the same residue modulo $q$ and is not bar-invariant since its bar is $1+q^{-1}$; this is the elementary failure that the bar condition rules out. The theorem also does not say that a bare directed coloured graph reconstructs all quantum matrix coefficients. Two modules can have vertices labelled by the same crystal graph while differing in the $q$-dependent coefficients of a non-canonical basis. Rather, the theorem says that once the full canonical-basis structure is available, the graph labels the preferred global basis vectors, which is why the type $A$ component computations can be lifted back to Schur-positive representation statements. [example: Schur Positivity from Crystal Components] For type $A$, write the character of a crystal as \begin{align*} \operatorname{ch} B=\sum_{b\in B} x^{\operatorname{wt}(b)}. \end{align*} For tableau crystals, this agrees with the Schur [generating function](/page/Generating%20Function), so $\operatorname{ch} B(\lambda)=s_\lambda$ and $\operatorname{ch} B(\mu)=s_\mu$. Now compute the character of the tensor product. Since weights add in the tensor product crystal, \begin{align*} \operatorname{ch}(B(\lambda)\otimes B(\mu))=\sum_{b\in B(\lambda)}\sum_{c\in B(\mu)} x^{\operatorname{wt}(b)+\operatorname{wt}(c)}. \end{align*} For monomials, $x^{\operatorname{wt}(b)+\operatorname{wt}(c)}=x^{\operatorname{wt}(b)}x^{\operatorname{wt}(c)}$, hence \begin{align*} \operatorname{ch}(B(\lambda)\otimes B(\mu))=\left(\sum_{b\in B(\lambda)}x^{\operatorname{wt}(b)}\right)\left(\sum_{c\in B(\mu)}x^{\operatorname{wt}(c)}\right)=s_\lambda s_\mu. \end{align*} By *Crystal Decomposition Detects Representation Decomposition*, the connected components of $B(\lambda)\otimes B(\mu)$ are highest-weight crystals, and the components with highest weight $\nu$ are counted by the Littlewood-Richardson coefficient $c_{\lambda\mu}^{\nu}$. Therefore the same character is also \begin{align*} \operatorname{ch}(B(\lambda)\otimes B(\mu))=\sum_\nu c_{\lambda\mu}^{\nu}\operatorname{ch}B(\nu). \end{align*} Using $\operatorname{ch}B(\nu)=s_\nu$ for type $A$ tableau crystals gives \begin{align*} s_\lambda s_\mu=\sum_\nu c_{\lambda\mu}^{\nu}s_\nu. \end{align*} Thus Schur positivity is already present before taking characters: the nonnegative coefficient $c_{\lambda\mu}^{\nu}$ counts actual highest-weight connected components of the tensor product crystal. [/example] Canonical bases and crystals therefore give two complementary explanations for positivity. The global basis supplies a representation-theoretic basis with positive structural behaviour, while the crystal supplies a finite graph in which the same positivity is counted by highest-weight vertices. [explanation: What the Chapter Adds] The earlier chapters built tableaux from insertion, symmetric functions, and Specht-module combinatorics. This chapter places those objects inside the representation theory of quantum groups: tableaux become vertices of crystals, Knuth-compatible operators become Kashiwara operators, and Littlewood-Richardson coefficients become counts of highest-weight components. The advantage of the crystal viewpoint is that it keeps enough of the representation to compute decompositions while replacing linear algebra by local graph moves. This viewpoint also connects the course to neighbouring areas. Canonical bases are tied to geometry through quiver varieties, perverse sheaves, and total positivity, where positivity of coefficients reflects geometric positivity rather than a tableau accident. Crystals also appear in solvable lattice models and statistical mechanics as combinatorial shadows of quantum affine algebra representations. Thus the type $A$ tableau rules are a concrete entry point into a broader pattern: representation-theoretic bases often explain why enumerative formulas have positive integer coefficients. [/explanation] The course has now accumulated several complementary tableau models, each highlighting a different aspect of representation theory. The final chapter brings them together and explains how Young diagrams, insertion, crystals, Hecke algebras, and canonical bases all fit into one coherent picture of representations as combinatorial objects. # 12. Synthesis: Tableaux as Representation Models This final chapter synthesizes the type $A$ part of the course. Chapters 1 through 11 introduced Young diagrams, Specht modules, RSK, semistandard tableau crystals, Hecke algebras, canonical bases, and Kazhdan-Lusztig cells as separate constructions; here we compare the roles tableaux play in all of them. Throughout this synthesis, a representation of an algebra or group means a homomorphism from that algebra or group into linear transformations of a vector space; the acting algebra is the algebra whose elements act by those transformations. A class function on a finite group is a function constant on conjugacy classes. The group algebra $\mathbb{C}[G]$ is the complex vector space with basis $G$ and multiplication extended linearly from the group law. The ring of symmetric functions is the graded ring generated by symmetric polynomials in countably many variables; the power sums are $p_k=x_1^k+x_2^k+\cdots$, and Schur functions are the symmetric functions indexed by partitions and computed from semistandard tableaux. The goal is not to identify these objects as the same mathematical structure, but to record which labels, operations, and branching patterns are genuinely shared. ## Shapes as Common Invariants What is the same when a word is inserted by RSK, a Specht module is restricted, a crystal operator is applied, or a permutation is placed in a Kazhdan-Lusztig cell? In type $A$, the answer is not a single object but a stable pattern: the shape records the dominant highest-weight data, while the tableau records a basis-like or cell-like refinement. [definition: Partition Shape] A partition shape of size $n$ is a partition $\nu=(\nu_1,\nu_2,\dots)$ with $\nu_1\ge \nu_2\ge \dots \ge 0$ and $|\nu|=\sum_i \nu_i=n$. [/definition] The same Young diagram $\nu$ indexes several objects, but the indexing is not cosmetic. For $S_n$, it labels the irreducible Specht module $S^\nu$ over characteristic zero; for $GL_m$ or $\mathfrak{gl}_m$, it labels the polynomial highest weight representation of highest weight $\nu$ when $\ell(\nu)\le m$; for RSK, it is the common shape of insertion and recording tableaux. Since these appearances come from different constructions, the chapter uses the following dictionary as an organizing convention rather than as a new theorem. [remark: Type A Shape Dictionary] In characteristic zero, a partition shape $\nu$ of size $n$ simultaneously records the label of the Specht module $S^\nu$ for $S_n$, the common RSK shape of pairs of standard tableaux, and, when $\ell(\nu)\le m$, the highest weight of the corresponding polynomial representation of $GL_m$ or $\mathfrak{gl}_m$. Standard tableaux of shape $\nu$ then model Specht bases and left or right cell data, while semistandard tableaux of shape $\nu$ model highest-weight crystal vertices and branching data. These are parallel roles, not identifications of all the underlying objects. [/remark] The restrictions in the dictionary are part of the meaning. In positive characteristic the Specht modules need not be irreducible, and if $m<\ell(\nu)$ there is no nonzero polynomial $GL_m$ representation of highest weight $\nu$. The point is therefore not that tableaux are merely notation for modules; rather, tableaux provide concrete models for bases, cells, branching paths, and crystal vertices. [example: Shape Four One] For $\nu=(4,1)$, the Young diagram has four boxes in the first row and one box below the first box. The hook lengths are obtained box by box: the first box has $3$ boxes to its right and $1$ below it, so its hook length is $3+1+1=5$; the remaining boxes in the first row have hook lengths $2+0+1=3$, $1+0+1=2$, and $0+0+1=1$; the single box in the second row has hook length $0+0+1=1$. Hence the hook-length product is \begin{align*}5\cdot 3\cdot 2\cdot 1\cdot 1=30.\end{align*} By the *hook-length formula*, \begin{align*}|\operatorname{SYT}(4,1)|=\frac{5!}{5\cdot 3\cdot 2\cdot 1\cdot 1}=\frac{5\cdot 4\cdot 3\cdot 2\cdot 1}{30}=\frac{120}{30}=4.\end{align*} Thus the Specht module $S^{(4,1)}$ has dimension $4$. Under RSK, each permutation of shape $(4,1)$ corresponds to a pair $(P,Q)$ of standard tableaux of shape $(4,1)$, so the number of permutations in the two-sided cell of shape $(4,1)$ is \begin{align*}|\operatorname{SYT}(4,1)|\cdot |\operatorname{SYT}(4,1)|=4\cdot 4=16.\end{align*} The same four standard tableaux index the left cells and the right cells attached to this shape, while also indexing a natural tableau basis for the irreducible $S_5$-module $S^{(4,1)}$. Since $\ell(4,1)=2$, the semistandard tableaux of shape $(4,1)$ with entries in $\{1,\dots,m\}$ form the highest weight crystal $B_m(4,1)$ for $\mathfrak{gl}_m$ precisely when $m\ge 2$. [/example] The example shows how the same number appears in different roles. The square $|\operatorname{SYT}(\nu)|^2$ counts permutations of shape $\nu$, while $|\operatorname{SYT}(\nu)|$ counts the dimension of the irreducible $S_n$-module. ## Operations on Tableaux and Functors on Representations Once shapes are identified across the theories, the next question is how operations compare. A useful dictionary should not only match labels; it should translate movement in one model into a construction in another. [definition: Removable and Addable Box] Let $\nu$ be a partition. A removable box of $\nu$ is a box whose deletion leaves the Young diagram of a partition. An addable box of $\nu$ is a box whose addition leaves the Young diagram of a partition. [/definition] Removing and adding boxes are the combinatorial shadows of restriction and induction for symmetric groups. To use this slogan in calculations, we need the exact representation-theoretic statement: which Specht modules appear after restriction or induction, and with what multiplicity. [quotetheorem:8477] [citeproof:8477] This rule explains why standard tableaux appear as paths in Young's lattice. Building a standard tableau by inserting $1,2,\dots,n$ is the same as choosing a chain of partitions from $\varnothing$ to $\nu$, and this chain records successive branching choices. The characteristic-zero hypothesis is part of the statement: in characteristic $2$, for instance, the sign representation of $S_2$ coincides with the one-dimensional representation on which every group element acts as $1$, and the semisimple direct-sum interpretation of branching no longer describes all composition behaviour. The theorem also says nothing about crystal edges or semistandard tableaux, since those belong to highest weight representations of Lie algebras rather than to restriction from $S_n$ to $S_{n-1}$. The crystal model has its own local arrows, so the next question is how its branching differs from the one-box symmetric-group rule. [quotetheorem:8480] [citeproof:8480] The theorem gives a precise place where the tableau dictionary changes language. Symmetric-group restriction removes exactly one box because the rank changes from $S_n$ to $S_{n-1}$, while semistandard restriction removes all boxes filled by the largest letter and therefore permits a horizontal strip. The following example keeps both rules visible in the same shape. [example: Specht and Crystal Branching for Three One] Take the partition $\nu=(3,1)$ of $4$. Its Young diagram has boxes in positions $(1,1),(1,2),(1,3),(2,1)$. Removing $(1,3)$ leaves row lengths $(2,1)$, and removing $(2,1)$ leaves row lengths $(3)$; removing any other box would not leave a Young diagram of a partition. Thus, by *Branching Rule for Specht Modules*, \begin{align*}\operatorname{Res}^{S_4}_{S_3} S^{(3,1)} \cong S^{(3)}\oplus S^{(2,1)}.\end{align*} In tableau terms, the entry $4$ must lie in a removable box: if $4$ is in $(2,1)$, deleting that box leaves shape $(3)$, while if $4$ is in $(1,3)$, deleting that box leaves shape $(2,1)$. For the semistandard crystal $B_3(3,1)$ restricted from $\mathfrak{gl}_3$ to $\mathfrak{gl}_2$, *[Semistandard Branching and Interlacing](/theorems/8480)* requires \begin{align*}3\ge \mu_1\ge 1\ge \mu_2\ge 0.\end{align*} Since $\mu_1$ is an integer with $1\le \mu_1\le 3$, we have $\mu_1\in\{1,2,3\}$. Since $\mu_2$ is an integer with $0\le \mu_2\le 1$ and $\mu_1\ge \mu_2$, we have $\mu_2\in\{0,1\}$. Listing the resulting partitions gives \begin{align*}(3,1),(3,0),(2,1),(2,0),(1,1),(1,0).\end{align*} Dropping trailing zeroes, these are \begin{align*}(3,1),(3),(2,1),(2),(1,1),(1).\end{align*} Thus symmetric-group restriction removes exactly one outer corner, while this crystal restriction removes a horizontal strip, so the two branching rules agree on some shapes but are not the same rule. [/example] The comparison also clarifies the limits of the dictionary. A crystal edge is a local operator on a vertex, whereas restriction is a functor on a representation; they agree through the shape calculus but live in different mathematical categories. ## RSK, Plactic Classes, and Kazhdan-Lusztig Cells How does an insertion algorithm know about Hecke algebra cells? The bridge is that both RSK and Kazhdan-Lusztig theory group permutations by equivalence relations that preserve tableau data. [definition: Plactic Equivalence] Two words in the ordered alphabet $\{1,2,\dots,m\}$ are plactic equivalent if they are related by a finite sequence of Knuth relations $xzy\sim zxy$ for $x\le y<z$ and $yxz\sim yzx$ for $x<y\le z$. [/definition] Plactic equivalence is designed so that row insertion has a well-defined normal form. The insertion tableau is that normal form, while the recording tableau records how the word was built. This motivates the precise test for when two words represent the same plactic element. [quotetheorem:8478] [citeproof:8478] This theorem has a sharp limitation: plactic equivalence remembers the insertion tableau and forgets the recording tableau. For example, the permutations $213$ and $231$ have the same insertion tableau under RSK but different recording tableaux, so they lie in the same plactic class while remaining distinct as permutations with different construction histories. Thus plactic equivalence is suited to right-cell data, not to the full RSK pair. For permutations, the plactic class controls one side of the RSK data, while Kazhdan-Lusztig cells give a Hecke-algebraic version of the same partition. This raises the question of which tableau controls left cells, which controls right cells, and why only the shape survives for two-sided cells. The next theorem is needed because the left-right convention cannot be recovered from insertion shape alone. [quotetheorem:8479] [citeproof:8479] The theorem explains why the cell representation attached to a left cell has the same size as the Specht module of the corresponding shape. The hypotheses are specific to finite type $A$: in other Coxeter types, RSK tableaux are not available as a complete cell invariant, and in affine type the set of group elements is infinite. The result also does not identify a cell with a Specht module as a literal subspace of the group algebra; it identifies the tableau labels that control the corresponding cell representation. This distinction matters in later geometric and categorical settings, where cells survive but the combinatorial labels are replaced by components, sheaves, or canonical-basis elements. [example: Full Dictionary for Three One] For $\nu=(3,1)$, the Young diagram has three boxes in the first row and one box below the first box. The box $(1,1)$ has $2$ boxes to its right and $1$ box below it, so its hook length is $2+1+1=4$. The boxes $(1,2)$ and $(1,3)$ have hook lengths $1+0+1=2$ and $0+0+1=1$, and the box $(2,1)$ has hook length $0+0+1=1$. Hence the hook-length product is \begin{align*}4\cdot 2\cdot 1\cdot 1=8.\end{align*} By the *hook-length formula*, \begin{align*}|\operatorname{SYT}(3,1)|=\frac{4!}{4\cdot 2\cdot 1\cdot 1}=\frac{4\cdot 3\cdot 2\cdot 1}{8}=\frac{24}{8}=3.\end{align*} Thus the three standard tableaux of shape $(3,1)$ index a natural tableau basis of the Specht module $S^{(3,1)}$. By the *Type A Cell Tableau Dictionary*, right cells in the two-sided cell of shape $(3,1)$ are determined by insertion tableaux, and left cells are determined by recording tableaux. Since there are $3$ possible standard tableaux of shape $(3,1)$, this two-sided cell contains $3$ right cells and $3$ left cells. RSK assigns to each permutation of shape $(3,1)$ a pair $(P,Q)$ of standard tableaux of shape $(3,1)$, so the number of such permutations is \begin{align*}|\operatorname{SYT}(3,1)|\cdot |\operatorname{SYT}(3,1)|=3\cdot 3=9.\end{align*} On the crystal side, semistandard tableaux of shape $(3,1)$ with entries in $\{1,2,3\}$ form the vertices of the highest weight crystal $B_3(3,1)$. Its highest weight tableau has first row $1,1,1$ and second row $2$, because rows are weakly increasing, columns are strictly increasing, and the highest weight filling uses as many entries equal to $1$ as possible before placing a $2$ below the first $1$. For symmetric-group restriction, the removable boxes of $(3,1)$ are $(1,3)$ and $(2,1)$. Removing $(1,3)$ leaves $(2,1)$, while removing $(2,1)$ leaves $(3)$, so the Specht branching shapes are exactly $(3)$ and $(2,1)$. For restriction from $\mathfrak{gl}_3$ to $\mathfrak{gl}_2$, the *Semistandard Branching and Interlacing* rule instead requires \begin{align*}3\ge \mu_1\ge 1\ge \mu_2\ge 0.\end{align*} Thus $\mu_1\in\{1,2,3\}$ and $\mu_2\in\{0,1\}$, with $\mu_1\ge \mu_2$ automatically in all six cases. The possible partitions are \begin{align*}(3,1),(3,0),(2,1),(2,0),(1,1),(1,0).\end{align*} Dropping trailing zeroes gives \begin{align*}(3,1),(3),(2,1),(2),(1,1),(1).\end{align*} So the symmetric-group branching shapes $(3)$ and $(2,1)$ appear among the crystal branching shapes, but the crystal restriction also allows the horizontal-strip removals leading to $(3,1)$, $(2)$, $(1,1)$, and $(1)$. [/example] The partition $(3,1)$ is small enough that the whole dictionary can be checked by hand, but already displays every feature: basis labels, cell labels, insertion shape, highest weight, and branching edges. ## Tableau Dictionary for Type A Representations The course has used tableaux in several roles, so the final synthesis records what is being identified and what is only analogous. In finite type $A$, the same partitions and tableaux organize several compatible structures: semistandard tableaux label bases of polynomial $\mathfrak{gl}_m$ representations when the length condition is satisfied, standard tableaux index Specht-module combinatorics for symmetric groups in characteristic zero, insertion records shapes through Robinson--Schensted--Knuth, highest weight tableaux detect crystal components, and branching is controlled either by one-box removals or by horizontal strips depending on the representation-theoretic setting. This dictionary is the endpoint of the type $A$ part of the course. Its hypotheses exclude several tempting overextensions: if $m<\ell(\nu)$, the stated $\mathfrak{gl}_m$ highest weight model does not exist, and in positive characteristic Specht modules may have nonsemisimple behaviour. The final comparison also separates two branching rules rather than merging them; one-box removal belongs to symmetric groups, while horizontal strips belong to semistandard branching. Thus the dictionary records compatible labels and operations, not a canonical isomorphism between all the objects listed. [remark: What the Dictionary Does Not Say] The dictionary does not identify Specht modules with crystals as the same objects. Specht modules are linear representations of finite groups, crystals are combinatorial shadows of quantum group representations, and Kazhdan-Lusztig cells arise from Hecke algebra bases. The force of the dictionary is that their type $A$ indexing sets and elementary operations are synchronized. [/remark] The warning is useful because the next natural developments keep some parts of the dictionary and replace others. Affine type, geometry, and categorification all enlarge the setting in ways that make the type $A$ finite story a model rather than a final answer. ## Beyond the Finite Type A Story Which parts of the tableau dictionary persist outside finite type $A$, and which parts must be replaced? The answer depends on whether the extension is affine, geometric, or categorical. [explanation: Affine and Other Coxeter Types] For other finite Coxeter groups, Kazhdan-Lusztig cells still exist, but ordinary Young tableaux no longer classify all cells or irreducible representations. Domino tableaux, bitableaux, symbols, and other combinatorial objects appear in types $B$, $C$, and $D$, while affine type introduces infinitely many group elements and more elaborate cell structures. Affine Hecke algebras and affine symmetric groups retain insertion-like combinatorics in special cases, but the clean RSK statement becomes a family of more delicate correspondences. The main lesson is that cells are robust, while the tableau model is type-dependent. [/explanation] Geometric representation theory gives a second route beyond the finite story. Instead of beginning with tableaux, it often begins with varieties whose irreducible components, intersection cohomology complexes, or fixed points carry the desired combinatorics. [explanation: Geometric Realizations] Schubert varieties, Springer fibres, quiver varieties, and flag varieties provide geometric spaces whose topology realizes representations. Standard tableaux appear, for example, in the geometry of Springer fibres of type $A$, where irreducible components are indexed by standard tableaux of a fixed shape. Kazhdan-Lusztig polynomials arise as intersection cohomology invariants of Schubert varieties, explaining why the Hecke algebra basis has geometric positivity. From this viewpoint, the tableau dictionary is the visible combinatorial trace of deeper geometry. The shape records orbit or nilpotent data, while tableaux often index components, fixed points, or bases. [/explanation] Categorification gives a third route: it replaces vector spaces and modules by categories whose Grothendieck groups recover the original representations. This changes equalities of characters into equivalences or functors between categories. [explanation: Categorified Settings] In categorified representation theory, induction and restriction become exact functors, canonical bases become classes of indecomposable projectives or simple objects, and crystal operators can be realized by categorical functors. Khovanov-Lauda-Rouquier algebras, category $\mathcal O$, and Hecke categories all provide settings where the combinatorics of tableaux and cells is lifted to homological algebra. The type $A$ dictionary remains a guide: box moves suggest functors, cells suggest subquotient categories, and canonical bases suggest distinguished indecomposable objects. The replacement for a tableau is often a categorical object whose shadow in the Grothendieck group is a tableau-labelled basis vector. [/explanation] These extensions show why the finite type $A$ story is central. It is the setting where the combinatorics is concrete enough to compute and rich enough to predict the structures that appear later. [example: Comparing Three Extensions] Starting from the Specht module $S^{(3,1)}$, the common datum is the partition shape $(3,1)$: it has size $4$ and length $2$, so it labels a finite type $A$ symmetric-group representation, a standard-tableau shape, and a possible highest weight for $\mathfrak{gl}_m$ whenever $m\ge 2$. The affine route keeps the Hecke-algebra language but changes the ambient algebra from the finite Hecke algebra of $S_4$ to an affine Hecke algebra. In that setting, Kazhdan-Lusztig cells still make sense, but the finite statement “cells are classified by the RSK insertion and recording tableaux” is replaced by affine insertion or other type-dependent cell data when such a model is available. The geometric route keeps the same partition as orbit data. The partition $(3,1)$ records a nilpotent Jordan form with one Jordan block of size $3$ and one Jordan block of size $1$, so the associated nilpotent orbit has Jordan type $(3,1)$. The Springer fibre over such a nilpotent element is then studied through its irreducible components, and in type $A$ those components are indexed by standard tableaux of the same shape. The categorified route changes the object attached to $(3,1)$ from a single module to a category. Its Grothendieck group is the abelian group generated by isomorphism classes of objects modulo relations $[B]=[A]+[C]$ coming from short exact sequences $0\to A\to B\to C\to 0$. Under this passage, a categorical restriction functor gives a linear restriction operator on the Grothendieck group, so the box removal visible in the branching of $S^{(3,1)}$ becomes the shadow of a functor between categories. Thus the same shape $(3,1)$ remains the organizing datum in all three extensions, but the attached object changes: affine cells replace finite RSK cells, Springer-fibre components replace tableau basis vectors, and categorical objects replace vectors in a module. [/example] The chapter closes the course by turning computations into a working language. To use the dictionary effectively, first identify the shape, then decide whether the relevant refinement is a standard tableau, a semistandard tableau, a recording tableau, a cell, or a categorical basis object. The answer determines which operations are available and which representation-theoretic construction they model. This final tableau dictionary is a guide to usage, not a separate theorem: it records which model is appropriate after the relevant hypotheses and constructions have already been established. ## References Internal Androma notes that support the background and adjacent material include [Group Action](/page/Group%20Action), [Algebraic Combinatorics I: Symmetric Functions](/page/Algebraic%20Combinatorics%20I%3A%20Symmetric%20Functions), [Algebraic Combinatorics II: Posets and Lattices](/page/Algebraic%20Combinatorics%20II%3A%20Posets%20and%20Lattices), and [Cambridge II Representation Theory](/page/Cambridge%20II%20Representation%20Theory). - Fulton, *Young Tableaux*, for Young diagrams, tableaux, Schur functors, and the representation theory of symmetric and general linear groups. - Sagan, *The Symmetric Group*, for Specht modules, characters, RSK, and symmetric-group combinatorics. - Stanley, *Enumerative Combinatorics, Volume 2*, for symmetric functions, Schur functions, and tableau enumeration. - Kashiwara, *Crystal bases of modified quantized enveloping algebra*, for crystal bases and canonical-basis background. - Kazhdan and Lusztig, *Representations of Coxeter groups and Hecke algebras*, for Kazhdan-Lusztig bases and cells.