Past exam of the representation Theory of Symmetric Groups course of the University of Oxford

Source paper: FOI request thread. The cover identifies Representation Theory of Symmetric Groups, C2.1b, Tuesday 14 June 2011, 2.30pm to 4.00pm. Its three readable pages are original private-bundle pages 408–410. The characteristic-two scope of question 2 and the RSK premise in question 3 are addressed explicitly in the solutions.

The Murnaghan–Nakayama rule computes an irreducible character on a permutation with a specified cycle of length $r$ byHere the leg length is one less than the number of occupied rows, and iteration ends at the empty partition with character value one. Conjugating a partition twists its character by the sign character:For a transposition, remove a rim domino and evaluate the remaining character at the identity of $S_3$. The three possible remaining shapes $(3),(2,1),(1^3)$ have degrees $1,2,1$ by the hook formula. For $(5)$ the single removable horizontal domino leaves $(3)$, giving one. For $(4,1)$ the only rim domino leaves $(2,1)$, giving two. For $(3,2)$ the removable bottom-row domino leaves $(3)$, giving one. For $(3,1,1)$, a horizontal domino leaves $(1^3)$ and a vertical domino leaves $(3)$; their contributions are $1-1=0$. The conjugate-partition identity gives the remaining three values with reversed sign.

The Hook-length formula is ${\chi }_{\lambda }(1)=5!/{\prod }_{u\in [\lambda ]}h(u)$. Both requested columns are thereforeAs a check, the squared degrees sum to $1+16+25+36+25+16+1=120=|S_5|$. The transposition column above was obtained from rim-hook removal and conjugation, independently of permutation characters.

Use the question's indexing convention: $m_{\lambda ,\mu }$ is the multiplicity of the irreducible Specht module $S_{\mathbb{C}}^{\mu }$ in the permutation module $M_{\mathbb{C}}^{\lambda }$. In notation for semistandard-tableau Kostka numbers this is often written $K_{\mu \lambda }$, with the indices reversed.

Let $S_{\lambda }=S_{{\lambda }_1}\times S_{{\lambda }_2}\times \cdots$ be the Young subgroup. The permutation character isand ${\xi }^{\lambda }(g)$ counts the $\lambda$-tabloids fixed by $g$. Equivalently it counts ordered partitions into labelled rows of the prescribed sizes, each row invariant under $g$. Character inner products and Frobenius reciprocity give the purely character-theoretic computationThe characters of symmetric groups are real-valued, so no conjugation is needed in the displayed subgroup average.

For $\lambda =(2,1^3)$, the Young subgroup has two elements, the identity and one transposition. Thus $m_{(2,1^3),\mu }=({\chi }_{\mu }(1)+{\chi }_{\mu }((12)))/2$, and part (a) givesThe resulting dimension is $1+3\cdot 4+3\cdot 5+3\cdot 6+2\cdot 5+4=60=5!/2$, the dimension of the permutation module.

This is the character average for Kostka numbers.

The Young subgroup for $(1^n)$ is trivial. Hence $M_{\mathbb{C}}^{(1^n)}$ is the regular representation of $S_n$. The subgroup-average formula reduces toThis is the usual multiplicity of an irreducible representation in the regular representation.

The permutation module $M_F^{\mu }$ is the $F$-vector space with the $\mu$-tabloids as basis, with $S_n$ acting by permuting their entries. For a tableau $t$ with column stabilizer $C_t$, its polytabloid isThe Specht module $S_F^{\mu }$ is the submodule of $M_F^{\mu }$ spanned by these polytabloids, equivalently generated by any one $e_t$ under the group action.

The standard basis theorem states thatis an $F$-basis of $S_F^{\mu }$ in every characteristic. Its dimension is the number of standard tableaux of shape $\mu$; in the hook shape used below the basis is exactly the displayed $e_{1ij}$ with $2\le i<j\le n$.

Put $W=S_F^{(n-2,1,1)}$ and let $H\cong S_{n-1}$ be the subgroup fixing one. For $\tau =(r,s)\in H$, let $u=\min \{\tau (i),\tau (j)\}$ and $v=\max \{\tau (i),\tau (j)\}$. Permuting a tableau's entries and then ordering its first column givesThe underlying basis element is $e_{1ij}$ exactly when $\tau$ preserves the unordered pair $\{i,j\}$: either $\{r,s\}=\{i,j\}$, giving the minus sign, or the two pairs are disjoint, giving the plus sign.

If $p\ne 2$, invariance of $x$ under $(i,j)$ forces its $e_{1ij}$ coefficient to satisfy $a_{ij}=-a_{ij}$, because no other basis vector is sent to that basis vector. Thus every coefficient vanishes. Consequently $W^H=0$, and in particular $W^{S_n}=0$, so there is no nonzero homomorphism from the trivial module. Any homomorphism $M_F^{(n-1,1)}\to W$ is determined by the image of its tabloid with singleton row $\{1\}$. That image is fixed by $H$ and is zero, making the whole homomorphism zero.

The printed vanishing assertion is false in characteristic two. Signs then coincide, so $H$ permutes the basis indexed by unordered pairs from $\{2,\dots ,n\}$. This action is transitive, andThe vector is nonzero by standard-basis independence. It also gives a nonzero map from the permutation module: send the singleton-row basis vector indexed by $r$ to $g_{r}v$, where $g_r(1)=r$. This is well defined because two choices of $g_r$ differ by an element of $H$, and it is $S_n$-equivariant by construction. Thus the claimed vanishing of permutation-module homomorphisms fails for every $n\ge 4$ in characteristic two.

The full-group fixed space can be determined explicitly. Denote a hook tabloid by $[a,b]$, recording its second- and third-row entries. In characteristic two, $e_{1ij}$ is the sum of the six tabloids using ordered pairs from $\{1,i,j\}$. In $v$, a tabloid whose two recorded entries both differ from one appears once; a tabloid using one appears $n-2$ times. Hence for odd $n$, $v$ is the sum of all hook tabloids and is fixed by $S_n$. For even $n$, it is the sum of precisely the tabloids avoiding one and is moved by $(1,2)$. Since every full-group fixed vector already lies in $Fv$, the corrected dimensions areThus even the trivial-module vanishing fails for odd $n$ in characteristic two; for example $n=5$ gives the explicit nonzero invariant $v$. These corrected fixed spaces allow the valid later conclusions to be proved in all characteristics.

The corrected parity dependence is described by fixed vectors in a hook Specht module in characteristic two.

Identify $M=M_F^{(n-1,1)}$ with $F^n$, whose basis vectors record the singleton row. PutIf the characteristic does not divide $n$, then $M=T\oplus U$, and $U$ is simple. If it divides $n$, then $0<T<U<M$ is the submodule chain, with $T$ and $M/U$ trivial and $U/T$ simple of dimension $n-2$. In both cases there are no additional submodules: any vector with unequal coordinates yields a nonzero multiple of $e_i-e_j$ by subtracting its image under $(i,j)$, and the orbit of such a difference spans $U$. A submodule containing no nonconstant vector is contained in $T$.

Now suppose $p\nmid n$. When $p\ne 2$, part (b)'s valid vanishing ${\mathrm{Hom}}_{S_n}(M,W)=0$ implies ${\mathrm{Hom}}_{S_n}(U,W)=0$: extend a putative map using the projection $M\to U$.

When $p=2$, the assumption $p\nmid n$ makes $n$ odd. The corrected calculation in part (b) says every map $M\to W$ sends its singleton-row basis vectors to the same multiple of the globally invariant vector $v$. Hence it kills the augmentation submodule $U$. Extending a map $U\to W$ along the direct-sum projection again makes it zero. Thus, despite the characteristic-two error in the earlier claim, the requested conclusion remains valid:

The structural input is the submodule lattice of the standard symmetric-group permutation module.

If $p\nmid n$, the preceding part says $U=S_F^{(n-1,1)}$ is simple and has no nonzero homomorphism into $W$. Its only nonzero simple quotient is itself, so $W$ cannot contain a submodule isomorphic to such a quotient.

If $p\mid n$, use the given nonzero homomorphism $\varphi :U\to W$. The submodule chain shows that $T$ is the unique maximal proper submodule of $U$ and $U/T$ is simple. Moreover ${\mathrm{Hom}}_{S_n}(T,W)=0$: for odd characteristic this follows from part (b), and in characteristic two the divisibility condition makes $n$ even, where the corrected fixed-space calculation also gives zero. Thus $\varphi$ kills $T$ and descends to a nonzero map $U/T\to W$. Simplicity makes this map injective.

Its image is the required simple submodule, provingIn the divisible case the quotient is explicitly $U/T$, of dimension $n-2$. The argument uses the supplied existence of $\varphi$ and only the fixed-space vanishing that remains valid in that case.

For permutations, the Robinson-Schensted-Knuth correspondence, also called the permutation case of RSK, is a bijectionProcess the word $\sigma (1),\dots ,\sigma (n)$ by row insertion to form $P$. To insert a new entry $a$, replace the leftmost entry of the first row larger than $a$ and bump that displaced entry into the next row by the same rule. If a row has no larger entry, append $a$ at its end and stop. Exactly one outer-corner cell is added. Record the current insertion time in that new cell of $Q$.

Rows stay increasing by the choice of the leftmost larger entry. The inequalities between successive bumped entries and the entries above them preserve increasing columns. Successive shapes are Young diagrams, so the recording labels also increase across rows and down columns. Reverse insertion at the corner labelled $n$ in $Q$ recovers the last input entry; repeating it recovers the full permutation, proving bijectivity. The more general RSK correspondence extends this construction to suitable two-line arrays and semistandard tableaux.

Write $\lambda =(a,b)$ with $a\ge b>0$. If the removed corner is in the first row, it must be its last cell, with $a>b$. Remove that entry and output it as $v$; all remaining row and column inequalities persist, and the shape is $(a-1,b)$.

If the corner is the last cell of the second row, remove its value $c$. In the first row find the rightmost entry $d<c$, replace it by $c$, and output $v=d$. Such an entry exists: the first-row cell above the removed corner has smaller value than $c$. The chosen position is therefore at least column $b$.

The new first-row entry exceeds all entries to its left, while every entry to its right is larger than $c$ by the rightmost-choice rule. After deleting the lower corner, no second-row cell remains below the changed position, since that row now has length $b-1$. Thus all column inequalities remain valid too. The resulting shape is $(a,b-1)$, omitting a zero part if $b=1$.The entries remain distinct and increasing along rows and columns, but the missing label is the ejected $v$, not necessarily the original corner value. The resulting tableau is therefore standard on its remaining ordered entry set, the generalized-standard convention in the question.

Let $a$ be the single entry in the second row of $P$. It lies in $\{2,\dots ,n\}$; the first row is all the other entries in increasing order. Consider the adjacent transposition $\sigma =(a-1,a)$, whose word isThe first $a-1$ entries append in increasing order to the first row. At insertion time $a$, the value $a-1$ bumps $a$ into the second row, creating its only cell. Every later entry appends to the first row. Thus the insertion tableau has second-row entry $a$ and all other entries in the first row, precisely $P$.

The recording tableau also has second-row entry $a$, the time of the unique bump, and all other time labels in increasing first-row order. It too is $P$. Bijectivity of the correspondence therefore givesThis includes $n=2,a=2$. It identifies the actual permutation without needing a general theorem about involutions.

This is RSK of an adjacent transposition.

Track the first row after any prefix of the input permutation. Its $j$th entry is the smallest possible final value of an increasing subsequence of length $j$ in that prefix. This minimum-tail invariant follows inductively from the row-insertion update.

Indeed, when a new value $z$ replaces the first first-row entry larger than it, at position $r$, the previous entry in position $r-1$ is smaller than $z$ when $r>1$. An increasing subsequence ending there can be extended by $z$, so $z$ supplies a new attainable tail of length $r$. It improves the old length-$r$ minimum. The minima for shorter lengths were already smaller than $z$ and remain unchanged; a longer subsequence ending at $z$ is impossible because its previous tail would have to be smaller than $z$, contradicting the choice of $r$. If no first-row entry exceeds $z$, it appends and creates a new longest subsequence. This proves the invariant at every step.

In particular, the number of first-row cells is the maximum increasing-subsequence length. At the final tableau it is ${\lambda }_1$, soThis proves the required nonextension assertion, even without requiring the first-row tuple itself to occur as a subsequence.

That occurrence is not automatic for a general permutation. For example the word $2,4,3,1$ gives $P$ with rows $(1,3),(2),(4)$. Its first-row tuple $(1,3)$ is not a subsequence of the word, because one occurs after three. The first row collects minimum tails for different subsequence lengths; those tails need not come from one common subsequence. If the source's premise is read as an additional hypothesis that the tuple does occur, the preceding maximum-length proof establishes its claimed maximality directly.

The invariant is the first row of RSK as a minimum-tail table.