Chapter 30: Representation-Theoretic Combinatorics

How do tableaux encode irreducible symmetric-group representations?

A partition can label a representation, and standard tableaux can label its basis. But a list of tableaux is not yet a representation: we must specify how permutations act, prove the group relations, and establish irreducibility. The question in this chapter is how combinatorial structure supports those algebraic claims.

For the foundation, work over $\mathbb C$ with finite-dimensional vector spaces. A representation of a group $G$ is a homomorphism $\rho:G\to\operatorname{GL}(V)$; thus $\rho(gh)=\rho(g)\rho(h)$. A subspace is invariant if every $\rho(g)$ preserves it. A representation is irreducible if its only invariant subspaces are zero and the whole space. Its character is $\chi_V(g)=\operatorname{tr}\rho(g)$. Restricting to a subgroup keeps the vector space but allows fewer operators, which can reveal a decomposition into smaller representations.

Here are the established tools needed for the final foundation investigation. Over $\mathbb C$, irreducible representations of $S_n$ are the Specht modules $S^\lambda$, indexed by partitions $\lambda\vdash n$; their dimensions are the standard-tableau counts $f^\lambda$. Restriction to $S_{n-1}$, the subgroup fixing $n$, contains one copy of $S^\mu$ for each shape obtained by removing one corner from $\lambda$. These are representation-theoretic theorems, rather than conclusions from dimension counts alone. The optional sections explain constructions, hypotheses, and further connections.

30.1 Representations of finite groups

Optional extension; not required to complete the chapter foundation. Group actions on finite sets become linear actions by taking the vector space with that set as a basis. These permutation representations are accessible starting points, but their invariant subspaces carry the finer structure.

A morphism between representations $V,W$ is an intertwiner $T:V\to W$ satisfying $T\rho_V(g)=\rho_W(g)T$. A decomposition $V=U\oplus W$ must have invariant summands. Maschke's theorem says that every finite-dimensional complex representation of a finite group is a direct sum of irreducibles. More generally, this holds over a field in which $\lvert G\rvert$ is invertible.

Proof. Given an invariant subspace $U\subseteq V$, choose any linear projection $p:V\to U$ with $p|_U=I$. Average its conjugates:

$$ \overline p=\frac1{\lvert G\rvert}\sum_{g\in G}\rho(g)p\rho(g)^{-1}. $$

Each summand maps into $U$ and fixes $U$, so the same is true of $\overline p$. Reindexing the sum proves that it commutes with every group operator. Therefore $\ker\overline p$ is invariant and $V=U\oplus\ker\overline p$. Induction on dimension finishes the proof. Averaging an arbitrary positive Hermitian form similarly makes every finite-group representation unitary.

Schur's lemma says that an intertwiner between irreducibles is either zero or an isomorphism, and an endomorphism of a complex irreducible is scalar. The first claim follows because kernel and image are invariant; for the second, subtract an eigenvalue times the identity and use the nonzero kernel. Character orthogonality then gives the multiplicity formula

$$ \langle\chi_V,\chi_U\rangle_G =\frac1{\lvert G\rvert}\sum_{g\in G}\chi_V(g)\overline{\chi_U(g)} =\dim\operatorname{Hom}_G(U,V) $$

when $U$ is irreducible. One proof averages the conjugation action on $\operatorname{Hom}_{\mathbb C}(U,V)$: its projection onto the invariant maps has trace equal to that inner product. Thus a nonzero complex representation is irreducible exactly when its character norm is one.

Solved example. In the permutation action of $S_3$ on $\mathbb C^3$, the invariant line $L=\mathbb C(1,1,1)$ has projection $P=(1/3)J$, where every entry of $J$ is one. The complement is the zero-sum plane $W$. A permutation's trace is its number of fixed coordinates, so $\chi_{\mathbb C^3}=(3,1,0)$ on the three conjugacy types. Subtracting the trivial character gives $\chi_W=(2,0,-1)$. Its norm is $(4+3\cdot0+2\cdot1)/6=1$, a second proof of irreducibility.

Exercise. Show why the complement argument fails for the swap action of $S_2$ on $\mathbb F_2^2$. Hint: Find its invariant lines. Solution: A stable one-dimensional line must be an eigenline of the swap matrix. Over $\mathbb F_2$ its only eigenvalue is one, and its only eigenline is $\mathbb F_2(1,1)$. There is no invariant complementary line. The averaging factor $1/2$ is undefined, and the characteristic-zero conclusion is false in this example.

30.2 Irreducible representations of symmetric groups

Optional extension; not required to complete the chapter foundation. A permutation's cycle lengths give a partition, and a Specht module's diagram gives another partition. They index the columns and rows, respectively, of a character table; they are different roles for the same combinatorial set.

For cycle type $\mu$, let $m_r(\mu)$ count its parts equal to $r$ and define $z_\mu=\prod_r r^{m_r(\mu)}m_r(\mu)!$. Its conjugacy class has size $n!/z_\mu$. The classification theorem states that $\{S^\lambda:\lambda\vdash n\}$ is a complete, pairwise nonisomorphic list of complex irreducibles, with

$$ \dim S^\lambda=f^\lambda =\frac{n!}{\prod_{c\in\lambda}h(c)}. $$

The standard-basis theorem for Specht modules gives the first equality; Chapter 29 supplies the hook-length count. Completeness and irreducibility require the module construction and its straightening theory, not just the hook product. The regular representation decomposes with multiplicity $\dim S^\lambda$, implying $n!=\sum_\lambda(f^\lambda)^2$. The RSK bijection gives a separate combinatorial proof of that numerical identity.

The Frobenius characteristic packages the character into a symmetric function:

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

For the middle row this is $(p_1^3-p_3)/3=s_{(2,1)}$. Character values are recovered from power-sum coefficients, whereas tableau weights supply monomial coefficients. This is why the choice of symmetric-function basis matters.

Exercise. Determine the irreducible dimensions for $S_4$ and check completeness numerically. Hint: Its partitions are $(4),(3,1),(2,2),(2,1,1),(1,1,1,1)$. Solution: Hook products are $24,8,12,8,24$, giving dimensions $1,3,2,3,1$. Their squared sum is $1+9+4+9+1=24$. This verifies a consequence of the classification theorem; by itself, a list of numbers would not construct the irreducibles.

30.3 Specht modules and Young symmetrizers

Optional extension; not required to complete the chapter foundation. Row symmetry and column antisymmetry turn fillings into vectors satisfying linear relations. We use English diagrams and multiply permutations by composition, with the rightmost factor acting first.

A $\lambda$-tableau $t$ is a bijective filling by $1,\ldots,n$, without requiring increasing entries. Its tabloid $\{t\}$ remembers which labels occupy each row, forgetting their order within that row. The permutation module $M^\lambda$ has all tabloids as a basis, with $g\{t\}=\{gt\}$. Let $R_t,C_t$ be the subgroups preserving each row set and each column set of $t$. Define the polytabloid

$$ e_t=\sum_{c\in C_t}\operatorname{sgn}(c)\{ct\},\qquad S^\lambda=\operatorname{span}\{e_t:t\text{ a }\lambda\text{-tableau}\}\subseteq M^\lambda. $$

Because $gC_tg^{-1}=C_{gt}$, we have $ge_t=e_{gt}$; hence this span is invariant. The standard polytabloids, indexed by standard tableaux, form a basis. Its proof uses column antisymmetry and Garnir relations to straighten nonstandard fillings, then proves independence. That straightening proof and the general irreducibility theorem are omitted; the small example below is complete.

In the group algebra $\mathbb C[S_n]$, put

$$ a_t=\sum_{r\in R_t}r,\qquad b_t=\sum_{c\in C_t}\operatorname{sgn}(c)c,\qquad y_t=b_ta_t. $$

This convention applies row symmetrization first and column antisymmetrization second. The Young-symmetrizer theorem gives $y_t^2=H_\lambda y_t$ with $H_\lambda=\prod_{c\in\lambda}h(c)$. Thus $y_t/H_\lambda$ is an idempotent, and the left ideal $\mathbb C[S_n]y_t$ realizes the corresponding irreducible. This idempotent need not be central. Reversing the order gives another conventional realization; formulas must specify which order is being used.

Solved example. For $t=[1,2]/[3]$, $R_t=\{1,(12)\}$ and $C_t=\{1,(13)\}$. Therefore

$$ y_t=(1-(13))(1+(12))=1+(12)-(13)-(123). $$

Here $(13)(12)=(123)$, as one checks on each of the three labels. Expanding in the six-element group algebra gives $y_t^2=3y_t$, and three is exactly the hook product of $(2,1)$.

Let $v_k$ be the tabloid whose bottom row contains $k$. Then $e_t=v_3-v_1$. The other standard tableau gives $e_2=v_2-v_1$; write $e_1=v_3-v_1$. Every polytabloid is a difference of two $v_k$, so the Specht space is their two-dimensional zero-sum subspace. In this ordered basis,

$$ \rho((12))=\begin{pmatrix}1&0\\-1&-1\end{pmatrix},\qquad \rho((23))=\begin{pmatrix}0&1\\1&0\end{pmatrix}. $$

Indeed $(12)e_1=e_1-e_2$, $(12)e_2=-e_2$, and $(23)$ exchanges $e_1,e_2$. These matrices have the same character $2,0,-1$ as the opening action, so the representations are isomorphic. A different basis changes matrices, not the representation type.

The diagram displays the actual three-cell tableau, its row and column groups, and the signed tabloid difference. Solid row shading identifies the row set; the outlined first column identifies the column set. The subtraction is a linear combination, not a negative number of tableaux.

Exercise. Construct the Specht module for $(1,1,1)$. Hint: Each row is a singleton, and the single column contains all labels. Solution: The polytabloid is $\sum_{g\in S_3}\operatorname{sgn}(g)\{gt\}$. Applying $h$ multiplies it by $\operatorname{sgn}(h)$ after reindexing. All polytabloids are scalar multiples of it, so the module is one-dimensional sign. In the group algebra the antisymmetrizer squares to $6$ times itself, matching the hook product six.

30.4 Branching rules

Optional extension; not required to complete the chapter foundation. Branching changes the group acting on a fixed vector space. Its graph records multiplicities of irreducible summands, while tableaux record paths through that graph.

Embed $S_{n-1}$ in $S_n$ by fixing $n$. Over $\mathbb C$, the branching theorem states

$$ \operatorname{Res}^{S_n}_{S_{n-1}}S^\lambda \cong\bigoplus_{\mu:\,\lambda/\mu\text{ one corner}}S^\mu, $$

$$ \operatorname{Ind}^{S_{n+1}}_{S_n}S^\lambda \cong\bigoplus_{\nu:\,\nu/\lambda\text{ one corner}}S^\nu. $$

Every allowed edge has multiplicity one. The general restriction proof constructs a filtration ordered by the position of $n$ in standard polytabloids; the subquotients are smaller Specht modules, and Maschke's theorem splits the filtration. It is not enough to group tableaux and assume their spans are invariant in an arbitrary basis. Induction follows by Frobenius reciprocity: an induced module and a restricted module have the same intertwiner multiplicities in opposite directions.

Solved example. The removable corners of $(3,1)$ are $(1,3)$ and $(2,1)$, producing $(2,1)$ and $(3)$, so

$$ \operatorname{Res}^{S_4}_{S_3}S^{(3,1)}\cong S^{(2,1)}\oplus S^{(3)}. $$

The dimension check is $3=2+1$. There are three standard tableaux: $[1,2,3]/[4]$, $[1,2,4]/[3]$, $[1,3,4]/[2]$. The first places $4$ in the bottom corner and gives a tableau of $(3)$ after deletion; the other two give $(2,1)$. This proves the dimension recurrence combinatorially. The module decomposition still uses the branching theorem or the explicit invariant-space proof in the final investigation.

Repeated restriction counts paths in Young's lattice. For $S^{(3,1)}$ restricted to $S_2$, the path through $(3)$ contributes $(2)$ once; the path through $(2,1)$ contributes $(2)$ and $(1,1)$ once each. Hence the result is $2S^{(2)}\oplus S^{(1,1)}$. Multiplicity-free single steps can therefore create multiplicities after several steps.

Exercise. Induce $S^{(2,1)}$ from $S_3$ to $S_4$. Hint: List all addable cells and check the subgroup index. Solution: The shapes are $(3,1),(2,2),(2,1,1)$, with dimensions $3,2,3$. Their sum eight equals $[S_4:S_3]\dim S^{(2,1)}=4\cdot2$. Under Frobenius characteristic this is precisely $s_{(2,1)}s_{(1)}=s_{(3,1)}+s_{(2,2)}+s_{(2,1,1)}$, the one-box Pieri identity.

30.5 Schur–Weyl duality

Optional extension; not required to complete the chapter foundation. Two different symmetries act on tensor space: a linear transformation acts in every tensor factor, while a permutation rearranges the factors. Their commuting actions explain why the same partitions occur in symmetric-group and general-linear-group representation theory.

Let $V=\mathbb C^N$. On $V^{\otimes n}$ use

$$ g(v_1\otimes\cdots\otimes v_n)=gv_1\otimes\cdots\otimes gv_n, $$

$$ \sigma(v_1\otimes\cdots\otimes v_n) =v_{\sigma^{-1}(1)}\otimes\cdots\otimes v_{\sigma^{-1}(n)}. $$

The inverse makes this a left action. These actions commute, since applying $g$ to every factor is independent of their order. Schur–Weyl duality asserts the decomposition

$$ V^{\otimes n}\cong \bigoplus_{\lambda\vdash n,\,\ell(\lambda)\leq N} \mathbb S_\lambda(V)\otimes S^\lambda, $$

where $\mathbb S_\lambda(V)$ is the irreducible polynomial $\operatorname{GL}_N$ module of highest weight $\lambda$. The two image algebras are mutual centralizers. The theorem refers to their images; when $N\lt n$, the symmetric-group algebra action may have a kernel. The proof uses the double-centralizer theorem and polynomial representation theory, omitted prerequisites.

Semistandard tableaux index weights of $\mathbb S_\lambda(V)$, whose character on a diagonal matrix is $s_\lambda(x_1,\ldots,x_N)$. Standard tableaux index the multiplicity factor $S^\lambda$. Consequently

$$ \dim\mathbb S_\lambda(\mathbb C^N) =s_\lambda(1^N)=\prod_{(i,j)\in\lambda}\frac{N+j-i}{h(i,j)}. $$

Solved example. Take $N=2,n=3$. Only $(3)$ and $(2,1)$ occur. Their general-linear-group dimensions are four and two; their Specht dimensions are one and two. Thus $8=4\cdot1+2\cdot2$. The three-cell column does not occur because a strict column cannot be filled from a two-letter alphabet; equivalently $\bigwedge^3\mathbb C^2=0$. For $(2,1)$ the hook-content product is $(2/3)\cdot3\cdot1=2$.

For $n=2$ the decomposition can be constructed directly: the factor-swap involution $\tau$ has projections $(I+\tau)/2$ and $(I-\tau)/2$, with images $\operatorname{Sym}^2V$ and $\bigwedge^2V$. This fully proves that small case and shows the simultaneous symmetries concretely.

Exercise. Check the dimension formula for $N=n=3$. Hint: The shapes are $(3),(2,1),(1,1,1)$. Solution: The general-linear-group dimensions are $10,8,1$, and the Specht dimensions are $1,2,1$, so $27=10+16+1$. Symmetry-adapted tensor decompositions are useful for organizing identical-particle state spaces and multilinear computations; the dimension check verifies the bookkeeping, while Schur–Weyl duality supplies the actual decomposition.

30.6 Crystal bases and combinatorial representation theory

Optional research specialization; not required to complete the chapter foundation. Crystals record weight changes by colored edges after a controlled limit of a quantum-group representation. They encode more than dimensions, but they do not retain all matrix coefficients of the original action.

For type $A_{N-1}$, let $\varepsilon_a$ be the coordinate weights and $\alpha_i=\varepsilon_i-\varepsilon_{i+1}$ for $1\leq i\lt N$. A tableau's weight is $\operatorname{wt}(T)=\sum_a m_a(T)\varepsilon_a$. A crystal has partial operators $\widetilde e_i,\widetilde f_i$; an arrow $T\xrightarrow{i}T'$ means $T'=\widetilde f_iT$, with weight $\operatorname{wt}(T')=\operatorname{wt}(T)-\alpha_i$. A missing result is denoted $\mathbf0$, which is not a vertex.

The established type-A model for the irreducible highest-weight crystal $B(\lambda)$ is the set of semistandard tableaux of shape $\lambda$ on $\{1,\ldots,N\}$. Fix this reading convention: read columns from right to left, and each column from top to bottom. For color $i$, discard other entries, replace $i$ by $+$ and $i+1$ by $-$, and repeatedly cancel adjacent $+-$ pairs. The survivors have all minus signs before all plus signs. Change the entry corresponding to the leftmost surviving plus from $i$ to $i+1$ for $\widetilde f_i$; change the rightmost surviving minus from $i+1$ to $i$ for $\widetilde e_i$. If the required sign is absent, the result is $\mathbf0$. Other reading conventions require corresponding operator rules.

Solved example. For shape $(2)$ and alphabet $\{1,2\}$, the three vertices and color-one edges are

$$ [1,1]\xrightarrow{1}[1,2]\xrightarrow{1}[2,2]. $$

The reading words are $11,21,22$, with signatures $++,-+,--$. The first lowering changes the right-hand one, and the second changes the left-hand one, preserving the weak row. The weights are $(2,0),(1,1),(0,2)$, and their monomials sum to $x_1^2+x_1x_2+x_2^2=s_{(2)}(x_1,x_2)$. For the column $[1]/[2]$, the word $12$ cancels completely: both color-one operators vanish. This is the one-dimensional determinant representation of $\operatorname{GL}_2$, and becomes trivial upon restriction to $\mathfrak{sl}_2$. It is a different module from the three-vertex row crystal.

Define $\epsilon_i(T)=\max\{r:\widetilde e_i^rT\neq\mathbf0\}$ and $\phi_i(T)=\max\{r:\widetilde f_i^rT\neq\mathbf0\}$. Along a valid crystal string,

$$ \phi_i(T)-\epsilon_i(T)=m_i(T)-m_{i+1}(T),\qquad \widetilde e_iT'=T\Longleftrightarrow\widetilde f_iT=T'. $$

The highest-weight tableau has entry $i$ throughout row $i$ and is annihilated by all raising operators. Its monomial is $x^\lambda$. Weight multiplicities count vertices of each weight, recovering Kostka numbers and the Schur character.

Established theorem and omitted proof. Kashiwara's existence theorem constructs crystal bases for integrable highest-weight modules over suitable quantized enveloping algebras; a crystal basis involves a lattice regular at $q=0$ and a compatible basis of its quotient. The tableau realization in finite type A is an established model, not an arbitrary graph justified only by matching its character. See Kashiwara's original crystal-base paper and Kashiwara–Nakashima's classical-type models. Quantum-group relations, the lattice construction, and its identification with these combinatorial operators are omitted prerequisites. No open-status claim is needed here.

Exercise. On alphabet $\{1,2,3\}$, compute $\widetilde f_1[1,2]$, $\widetilde f_2[1,2]$, and $\widetilde e_2[1,2]$. Hint: The reading word is $21$. Solution: For color one the signature is $-+$, so lowering changes the left-hand $1$ and gives $[2,2]$. For color two the sole relevant entry is the right-hand $2$, a plus sign, giving $[1,3]$. There is no $3$, hence $\widetilde e_2[1,2]=\mathbf0$. Each nonzero output has the required weight difference.

30.7 Root systems and Weyl groups

Optional extension; not required to complete the chapter foundation. Roots supply the directions of crystal edges; reflections in those directions supply the Weyl symmetry. The geometric and combinatorial uses agree after their conventions are fixed.

A finite reduced crystallographic root system $\Phi$ lies in a real Euclidean space $E$, spans it, contains no zero vector, and satisfies $s_\alpha(\Phi)=\Phi$, $\Phi\cap\mathbb R\alpha=\{\alpha,-\alpha\}$, and $2(\beta,\alpha)/(\alpha,\alpha)\in\mathbb Z$ for all roots. The reflection is

$$ s_\alpha(x)=x-\frac{2(x,\alpha)}{(\alpha,\alpha)}\alpha. $$

The Weyl group is generated by these reflections. A choice of simple roots $\alpha_1,\ldots,\alpha_r$ determines positive roots and the dominant chamber. Set $\alpha_i^\vee=2\alpha_i/(\alpha_i,\alpha_i)$; a weight $\eta$ is dominant integral when $\langle\eta,\alpha_i^\vee\rangle$ is a nonnegative integer for every $i$. The Cartan matrix has entries $a_{ij}=\langle\alpha_j,\alpha_i^\vee\rangle$.

Solved example. Type $A_2$ uses $E=\{x\in\mathbb R^3:x_1+x_2+x_3=0\}$ and roots $\varepsilon_i-\varepsilon_j$ for $i\neq j$. Take $\alpha_1=(1,-1,0)$ and $\alpha_2=(0,1,-1)$. Each has squared length two; their inner product is minus one. Thus

$$ (a_{ij})=\begin{pmatrix}2&-1\\-1&2\end{pmatrix}. $$

Substituting $\alpha_1$ into the reflection formula exchanges $x_1,x_2$; $s_{\alpha_2}$ exchanges $x_2,x_3$. Therefore the Weyl group is $S_3$. The positive roots are $\alpha_1,\alpha_2,\alpha_1+\alpha_2$; the dominant chamber is $x_1\geq x_2\geq x_3$ within $E$.

For $\operatorname{GL}_N$, partitions give dominant polynomial weights $(\lambda_1,\ldots,\lambda_N)$. Restriction to $\mathfrak{sl}_N$ remembers the differences $\lambda_i-\lambda_{i+1}$. Adding the same integer to every part twists by a determinant power for $\operatorname{GL}_N$ but leaves the $\mathfrak{sl}_N$ highest weight unchanged. This explains the determinant crystal in 30.6.

Exercise. Reflect $\alpha_2$ in $\alpha_1$ and reflect $\alpha_1+\alpha_2$ in $\alpha_2$. Hint: Use the inner products above. Solution: $s_{\alpha_1}(\alpha_2)=\alpha_2+\alpha_1$; the inner product of $\alpha_1+\alpha_2$ with $\alpha_2$ is one, giving $s_{\alpha_2}(\alpha_1+\alpha_2)=\alpha_1$. Both outputs are roots, verifying closure for these instances.

30.8 Coxeter groups and Bruhat order

Optional extension; not required to complete the chapter foundation. Simple reflections generate a group with short local relations, while Bruhat order compares elements by the subwords of their shortest expressions. This is the order used to make Hecke-algebra bases triangular.

A Coxeter system $(W,S)$ has generators $s\in S$ with relations $s^2=1$ and $(st)^{m_{st}}=1$ when $m_{st}$ is finite, with $m_{st}=m_{ts}\geq2$ for distinct generators. Its length $\ell(w)$ is the least number of generators in an expression for $w$. An expression of that length is reduced. In $S_n$, $s_i=(i,i+1)$, adjacent generators satisfy a braid relation of length three, and generators farther apart commute. For a one-line permutation $w$, length is its inversion count.

The Bruhat subword theorem states that $x\leq w$ exactly when a reduced expression for $w$ contains a reduced expression for $x$ as a subsequence. This condition can be tested using any fixed reduced expression for $w$; that independence is a theorem. A subsequence need not occupy consecutive positions. Right weak order instead requires a reduced expression for $x$ as a prefix, so the two orders differ.

Solved example. In $S_3$, write $s=s_1$, $t=s_2$ and use rightmost-first composition.

For example, both single letters are subwords of $st$. Also $s\leq ts$ by its final letter, but $s$ is not below $ts$ in right weak order: the latter has no reduced expression beginning with $s$. The braid relation joins the two length-three expressions for the longest element.

One can enumerate the interval below $w$ by multiplying all subwords of one reduced word and discarding duplicates. Different subwords can yield the same group element; their count is not the size of the interval. For $w=sts$, the eight position subsets yield six distinct elements, since the empty word and the subword using the two $s$ positions both give identity.

Exercise. Compute the Bruhat interval below $st$ and compare the lengths of $st$ and $ts$. Hint: There are four subwords of $st$. Solution: The interval is $\{1,s,t,st\}$. Both $st$ and $ts$ have length two, but they are distinct and incomparable in Bruhat order: comparable elements of equal length must be equal. Length alone does not determine order.

30.9 Kazhdan–Lusztig polynomials

Optional research specialization; not required to complete the chapter foundation. Kazhdan–Lusztig polynomials are coefficients of a distinguished basis in a deformation of the group algebra. Their algebraic definition works without assuming a geometric interpretation.

Fix a Coxeter system and the equal-parameter Hecke algebra over $\mathbb Z[v,v^{-1}]$. Its standard basis $H_w$ has multiplication

$$ H_sH_w=\begin{cases} H_{sw},&\ell(sw)=\ell(w)+1,\\ H_{sw}+(v-v^{-1})H_w,&\ell(sw)=\ell(w)-1. \end{cases} $$

In particular $H_s^2=1+(v-v^{-1})H_s$. The bar involution sends $v$ to $v^{-1}$ and $H_w$ to $H_{w^{-1}}^{-1}$. The canonical basis $C_w$ is characterized by bar invariance and

$$ C_w=H_w+\sum_{x\lt w}a_{x,w}(v)H_x,\qquad a_{x,w}(v)\in v^{-1}\mathbb Z[v^{-1}]. $$

With this normalization define $q=v^2$ and

$$ C_w=\sum_{x\leq w}v^{\ell(x)-\ell(w)}P_{x,w}(v^2)H_x. $$

Then $P_{w,w}=1$, $P_{x,w}=0$ for $x\nleq w$, and for $x\lt w$, $\deg P_{x,w}\leq(\ell(w)-\ell(x)-1)/2$. The existence, uniqueness, and polynomial properties belong to the canonical-basis theorem in Kazhdan–Lusztig's original paper.

A constructive algorithm is worth separating from the theorem. Write $w=su$ with $\ell(u)=\ell(w)-1$. Multiply $C_sC_u$, where $C_s=H_s+v^{-1}$. Process lower elements in decreasing length. If the current coefficient of $H_x$ has nonnegative powers, subtract $b_x(v)C_x$, where $b_x$ is the bar-invariant Laurent polynomial with the same nonnegative part: keep the constant term and reflect every positive-degree term to its negative degree. The result remains bar-invariant, preserves the leading term, and has only strictly negative lower coefficients. Previously constructed $C_x$ make this a finite triangular procedure. Canonical-basis uniqueness identifies the output; the general theorem supplies Bruhat support and the stated degree bound.

Solved examples. In $S_3$, expansion gives

$$ C_{sts}=C_sC_tC_s-C_s =H_{sts}+v^{-1}(H_{st}+H_{ts})+v^{-2}(H_s+H_t)+v^{-3}H_1. $$

Thus all $P_{x,sts}$ are one. This small example does not imply that all Kazhdan–Lusztig polynomials are constant.

A first nonconstant example in $S_4$ is $w=3412=s_2s_1s_3s_2$, of length four. Expand $C_{s_2}C_{s_1}C_{s_3}C_{s_2}$. Its standard-basis coefficients are:

Every lower coefficient has strictly negative powers, and each factor is bar-invariant; hence this product already equals $C_w$. Its identity coefficient is $v^{-4}(1+v^2)$, so $P_{1,3412}(q)=1+q$. The bound permits degree one since the length difference is four. Exact Laurent arithmetic verifies all entries in this table.

Established results and scope. Nonnegative coefficients for ordinary equal-parameter Kazhdan–Lusztig polynomials of arbitrary Coxeter systems are a theorem of Elias–Williamson. Their proof establishes Soergel's conjecture using Hodge theory for bimodules; those prerequisites are omitted. In Weyl-group settings, geometry relates these coefficients to local intersection cohomology of Schubert varieties. That geometric identification is an additional theorem, not a meaning forced by an arbitrary colored graph. Unequal parameters and modular variants require their own hypotheses; the equal-parameter theorem is not a blanket claim about every variant. No historical conjecture just mentioned is presented as open.

Exercise. Compute $C_{st}$ and its polynomials in $S_3$. Hint: Multiply $H_s+v^{-1}$ and $H_t+v^{-1}$. Solution: $C_{st}=H_{st}+v^{-1}(H_s+H_t)+v^{-2}H_1$. The product is bar-invariant and triangular, so $P_{1,st}=P_{s,st}=P_{t,st}=P_{st,st}=1$. Elements outside the four-element interval have coefficient zero.

30.10 Combinatorial categorification

Optional research specialization; not required to complete the chapter foundation. Categorification replaces numbers or algebraic operators by objects, functors, and morphisms whose passage to a Grothendieck group recovers the original algebra. Drawing a branching graph is useful, but a categorification also requires the underlying categories and maps.

For an abelian category $\mathcal C$, its Grothendieck group $K_0(\mathcal C)$ is generated by object classes $[M]$, with $[B]=[A]+[C]$ for every short exact sequence $0\to A\to B\to C\to0$. An exact functor induces an additive map on $K_0$. For an additive category one may instead use the split Grothendieck group, imposing only direct-sum relations. Which version is intended matters when the category is not semisimple. A monoidal product can induce ring multiplication; grading shifts can make the group a module over Laurent polynomials.

Solved elementary example. Finite-dimensional graded complex vector spaces have

$$ K_0\cong\mathbb Z[v,v^{-1}],\qquad [M]=\sum_d\dim(M_d)v^d. $$

Here a one-dimensional object concentrated in degree one represents $v$, and tensor product adds degrees. An object with one basis vector in degree zero and one in degree two has class $1+v^2$. Its tensor square has graded dimensions $1,2,1$ in degrees $0,2,4$, so class $(1+v^2)^2$. This categorifies a polynomial calculation. It does not identify that object with the geometric object giving $P_{1,3412}(v^2)$ merely because the same polynomial occurs.

A stronger example uses $\mathcal C_n=\operatorname{Rep}_{\mathbb C}(S_n)$. Let $F_n=\operatorname{Ind}_{S_n}^{S_{n+1}}$ and $E_n=\operatorname{Res}_{S_{n-1}}^{S_n}$, with $E_0=0$. For $n\geq1$ there is a natural functor isomorphism

$$ E_{n+1}F_n\cong F_{n-1}E_n\oplus\operatorname{Id}_{\mathcal C_n}. $$

Proof mechanism. Mackey decomposition uses the two double cosets of $S_n$ in $S_{n+1}$. The identity double coset contributes the identity functor. A representative exchanging $n$ and $n+1$ has subgroup intersection $S_{n-1}$, contributing induction after restriction. The corresponding group-algebra bimodule decomposition makes the isomorphism natural, rather than a pointwise coincidence of dimensions. This supplies the categorical relation; full Mackey theory is omitted.

On $\bigoplus_nK_0(\mathcal C_n)$, write $U=[F]$ and $D=[E]$. Decategorification gives $DU-UD=I$. In the irreducible basis, branching makes $U$ add a box and $D$ remove a box. Thus Young's lattice supports a differential-poset relation whose coefficients now have an explicit functorial source.

For $V=S^{(2,1)}$ in degree three, the exact decompositions are

$$ E_4F_3V\cong S^{(3)}\oplus3S^{(2,1)}\oplus S^{(1,1,1)}, $$

$$ F_2E_3V\cong S^{(3)}\oplus2S^{(2,1)}\oplus S^{(1,1,1)}. $$

The dimensions are eight and six; their difference is $\dim V=2$. More strongly, the difference of their Grothendieck classes is exactly $[V]$, and Mackey decomposition supplies the natural functor isomorphism behind it.

Established research results; omitted prerequisites. Khovanov–Lauda I and II construct diagrammatic algebras whose categories of graded projective modules categorify the negative half of suitable quantum groups, extending to general Cartan data. Their split Grothendieck groups and induction/restriction operations must be matched to the relevant integral algebra, rather than only to a dimension sequence. Quiver Hecke relations and the identification theorem are omitted. Khovanov's Heisenberg graphical calculus develops an additive monoidal category with an integral Heisenberg algebra inside its Grothendieck ring; containment is not being upgraded here to an unsupported equality. These are proved constructions, not open conjectures. A fuller categorical action also specifies natural transformations and their coherence relations; the branching matrices alone omit that information.

Exercise. Verify $DU-UD=I$ on the shape $(2)$. Hint: Adding gives $(3)$ and $(2,1)$; removing gives $(1)$. Solution: $DU(2)=2(2)+(1,1)$, while $UD(2)=(2)+(1,1)$. Their difference is $(2)$. This proves one basis-vector calculation. Mackey's functor isomorphism proves the relation for all modules in the tower.

Compute a branching example and separate combinatorial models from representation-theoretic claims

The investigation follows one shape through counting, an explicit invariant decomposition, and an optional functor calculation. The foundation uses the representation definitions and branching tools from the opening section. Research extensions are optional, and no advanced existence theorem must be reproved to complete the core tasks.

Worked solutions. The three tableaux are $[1,2,3]/[4]$, $[1,2,4]/[3]$, and $[1,3,4]/[2]$. The hooks are $4,2,1$ in the top row and $1$ below, so $f^{(3,1)}=24/8=3$. Removing $4$ produces $(3)$ once and $(2,1)$ twice at the level of tableau counts. Representation branching contains one copy of each of these modules, of dimensions one and two; confusing these two kinds of multiplicity loses the meaning of the rule.

The one-step restriction is $S^{(3)}\oplus S^{(2,1)}$. The two-step restriction is $2S^{(2)}\oplus S^{(1,1)}$, with total dimension $2+1=3$. The repeated $(2)$ comes from two different paths, not two removable corners at a single step.

For the direct proof, every permutation of the first three coordinates fixes $\ell=(1,1,1,-3)$ and preserves $U$. Since the fourth coordinate of a nonzero multiple of $\ell$ is nonzero, $L\cap U=0$. For $x\in W_4$, put $a=-x_4/3$; then $x-a\ell$ has fourth coordinate zero and its first three coordinates sum to zero. Thus $x\in U+L$ and $W_4=U\oplus L$. The action on $U$ is the irreducible zero-sum plane from the opening card. Hence this proves the module decomposition, independently of only counting its basis labels.

The adapted generator matrices are

$$ \rho((12))=\begin{pmatrix}-1&1&0\\0&1&0\\0&0&1\end{pmatrix},\qquad \rho((23))=\begin{pmatrix}1&0&0\\1&-1&0\\0&0&1\end{pmatrix}. $$

Their upper-left blocks are the opening matrices, and their last coordinate is fixed. They square to identity and their product has order three. These exact block forms supply the requested invariant-space check.

For the character exploration, the permutation action on $\mathbb C^4$ has trace equal to the number of fixed coordinates; subtract its constant line to obtain the character on $W_4$.

All columns agree with the direct proof. At the next restriction, $(12)$ has eigenvalues $-1,1,1$, yielding one sign and two trivial summands for $S_2$. For assessment, the proof marks require an invariant-space argument and direct sum, not just the table. The exploration marks require exact checks or an exhaustive class table and a clear statement of scope.

The categorical extension uses precisely the same finite-group representations, but regards them as objects in categories and induction/restriction as functors. On $S^{(2,1)}$, the two path-counting results are $[(3)]+3[(2,1)]+[(1,1,1)]$ and $[(3)]+2[(2,1)]+[(1,1,1)]$. Their difference is $[(2,1)]$. This is the Grothendieck-group calculation; the natural Mackey isomorphism explains its lift to functors. A graph with those edges supplies the coefficients but not the morphisms, adjunctions, or natural transformations of a richer categorical action.

A practical application is decomposing linear models with interchangeable components. Four coordinate signals can be separated into a mean and a zero-sum contrast space. If only the first three components are interchangeable, $U$ captures their internal contrasts, while $L$ measures their common level against the fourth component. Any linear operator on $W_4$ commuting with this $S_3$ action acts by a scalar on each of these two inequivalent irreducible summands, by Schur's lemma. This reduces the possible operator structure and makes the role of symmetry precise. Matching dimensions suggests a useful organization; invariant subspaces and intertwiners justify it.