Proving interesting theorems about S_n using its character table. - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-19T12:55:53Z http://mathoverflow.net/feeds/question/47952 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/47952/proving-interesting-theorems-about-s-n-using-its-character-table Proving interesting theorems about S_n using its character table. trew 2010-12-01T21:56:50Z 2010-12-02T06:43:54Z <p>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 ?</p> http://mathoverflow.net/questions/47952/proving-interesting-theorems-about-s-n-using-its-character-table/47953#47953 Answer by M.Z. for Proving interesting theorems about S_n using its character table. M.Z. 2010-12-01T22:12:58Z 2010-12-01T22:12:58Z <p>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!)</p> http://mathoverflow.net/questions/47952/proving-interesting-theorems-about-s-n-using-its-character-table/47995#47995 Answer by Ken Fan for Proving interesting theorems about S_n using its character table. Ken Fan 2010-12-02T03:58:06Z 2010-12-02T05:11:12Z <p>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.</p> <p>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 <code>$\chi ( \pi ) = \frac{\# S_n}{\# C_\pi}$</code>, 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.</p> http://mathoverflow.net/questions/47952/proving-interesting-theorems-about-s-n-using-its-character-table/48003#48003 Answer by Alex Bartel for Proving interesting theorems about S_n using its character table. Alex Bartel 2010-12-02T05:23:44Z 2010-12-02T05:23:44Z <p>In an answer to <a href="http://mathoverflow.net/questions/41784/roots-of-permutations/41788#41788" rel="nofollow">an earlier question</a>, I showed how to prove that the square root counting function <code>$r_2: S_n\rightarrow \mathbb{N},\;g\mapsto \#\{h\in S_n|h^2=g\}$</code> 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$.</p> http://mathoverflow.net/questions/47952/proving-interesting-theorems-about-s-n-using-its-character-table/48005#48005 Answer by Anatoly Preygel for Proving interesting theorems about S_n using its character table. Anatoly Preygel 2010-12-02T06:43:54Z 2010-12-02T06:43:54Z <p>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:</p> <p>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)!$$ <strong>Claim:</strong> $$\prod_{\lambda \vdash n} A(\lambda) = \prod_{\lambda \vdash n} B(\lambda)$$</p> <p>The character-theoretic proof proceeds as follows:</p> <ol> <li>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)}$$</li> <li>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)$$</li> <li>$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}$.</li> <li>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)$.</li> <li>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.</li> </ol> <p>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.</p>