# Proving interesting theorems about S_n using its character table.

Hi, i wonder if there are interesting proofs about $S_n$ (group theoretic or not) using its character table. Using the Murnaghan-Nakayama rule you can for example prove that for $n>4$ $A_n$ is the only normal subgroup of $S_n$ because there are no nonlinear characters $x$ and $g$(not 1) in $S_n$ with $x(g)=x(1)$, since $x(1)>x(g)$ . Do you know any other nontrivial theorems about $S_n$ with a proof using its charactertable ?

-

In an answer to an earlier question, I showed how to prove that the square root counting function $r_2: S_n\rightarrow \mathbb{N},\;g\mapsto \#\{h\in S_n|h^2=g\}$ assumes its maximum at the identity, using the representation theory of $S_n$. Admittedly, you need to know slightly more than the character table. You need to be able to compute the Frobenius-Schur indicators of the characters, so you need to know how the conjugacy classes multiply. Alternatively, you just need to know that all representations are defined over $\mathbb{R}$, which you prove along to way to computing the character table anyway. In a comment to my answer, Richard Stanley remarks that, also using the representation theory of $S_n$, you can generalise this to the $k$-th root counting function for any positive integer $k$. In an answer to the same question, Alon Amit remarks on possible generalisations to solving other polynomial equations in the elements of $S_n$.

-

I'm not sure if you will consider this nontrivial, but from the character table you can very quickly show that the number of conjugacy classes of even permutations is always greater than or equal to the number of conjugacy classes of odd permutations.

One just applies the general fact that the sum of the entries in any row of a character table (not weighted by the size of the conjugacy class) is a nonnegative integer (because the character $\chi ( \pi ) = \frac{\# S_n}{\# C_\pi}$, where $C_\pi$ is the set of conjugates of the permutation $\pi$, corresponds to an actual representation, namely, take a vector space with basis $\{ e_\pi \mid \pi \in S_n\}$ and define $g(e_\pi) = e_{g \pi g^{-1}}$ for $g \in S_n$) to the sign character.

-
The displayed equation isn't showing properly, so I fixed it. Why change it back? Or is there some strange behavior here? –  Charles Rezk Dec 2 '10 at 4:26
I mean, strange MathJax TeX behavior ... –  Charles Rezk Dec 2 '10 at 4:27
Oh sorry...I missed your fix before I changed it back...I was struggling to get it to display properly...if you have a chance, please refix it! Thanks so much! –  Ken Fan Dec 2 '10 at 4:33

The following is not strictly speaking something that can be read off from the character table. However, it is an elementary combinatorial identity about partitions which one can deduce from understanding the character theory of symmetric groups well enough, and looking at the character table does play a central role:

For $\lambda \vdash n$ a partition of $n$ (i.e., $n = 1 \lambda_1 + 2 \lambda_2 + \cdots + n \lambda_n$) define $$A(\lambda) = \prod_{i=1}^{n} n^{\lambda_n}, \qquad B(\lambda) = \prod_{i=1}^{n} (\lambda_n)!$$ Claim: $$\prod_{\lambda \vdash n} A(\lambda) = \prod_{\lambda \vdash n} B(\lambda)$$

The character-theoretic proof proceeds as follows:

1. For an element in the conjugacy class of $S_n$ indexed by the partition $\lambda$, it's centralizer has cardinality $A(\lambda) B(\lambda)$, i.e., the number of elements in the conjugacy class is $$\frac{n!}{A(\lambda) B(\lambda)}$$
2. Take the character matrix $M$. The orthogonality relations tells us that a suitable rescaling of the character matrix is orthogonal, so has $\det = \pm 1$. From this, together with 1 to find the scaling factors for the columns, we obtain $$(\det M)^2 = \prod_{\lambda} A(\lambda) B(\lambda)$$
3. $M$ relates two bases for the spaces of class-functions: The characters of irreps (indexed in the Schur ordering by partitions), and the delta functions on conjugacy classes (indexed obviously by partitions). For symmetric groups, there is a third nice basis: For $\lambda \vdash n$, let $$S_\lambda = \prod_{i=1}^{n} S_i^{\lambda_i}$$ and consider the characters of the induced reps $Ind_{S_\lambda}^{S_n} \mathbb{C}$.
4. Consider the change of basis matrix relating characters of induced reps and the delta functions on conjugacy classes: Easy character theory shows that it is triangular with diagonal entries equal to $B(\lambda)$.
5. Consider the change of basis matrix relating characters of induces reps and characters of irreps: Knowing how character theory for symmetric groups works over $\mathbb{Z}$ (i.e., that both span integrally), we can show that it has determinant $\pm 1$. More precisely, knowing the character theory well enough we can show that the change of basis matrix between them is upper triangular with ones on the diagonal.

Putting together 2, 4, 5 we obtain $$\det(M)^2 = \prod_{\lambda \vdash n} A(\lambda) B(\lambda) = \left(\prod_{\lambda \vdash n} B(\lambda)\right)^2$$ and so the claimed identity.

-
Your notation for partitions is not the standard one: you denote by $\lambda_i$ the number of all $i$'s in the partition, while usually it means the $i$-th part. Just noting this down for future readers... –  darij grinberg Dec 2 '10 at 10:54

Because all the entries in the character table are integers and not just algebraic integers, you get that a proof that every permutation $\sigma$ of order $n$ is conjugate to all $\sigma^j$ for $j$ coprime to $n$. (Of course, one usually uses this in the opposite direction, to deduce that all entries are integers!)

-
thank you!does someone know if you need to use that result to prove Murnaghan-Nakayama,which also gives you that the character table entries are integers?I think so. –  trew Dec 1 '10 at 22:22