Algorithmically distinguishing irreducible characters of the symmetric group (Q2662346)

The ordinary character theory of the symmetric group is very well understood: the characters (which are integer-valued) can be calculated using the famous Murnaghan-Nakayama rule. However, given two distinct irreducible characters \(\chi_\lambda\) and \(\chi_\mu\) (where \(\lambda\) and \(\mu\) are partitions of \(n\)) it is surprisingly difficult to exhibit a group element on which these characters take different values. The paper under review gives a polynomial-time algorithm to do this. This is done by solving a related oracle-based problem. One is given told that \(f\) is an irreducible character, and by repeatedly asking for values \(f(\pi)\) (where the later queries are allowed to depend on the results of earlier queries) one has to work out which irreducible character \(\chi_\lambda\) it is. It is shown that this problem can be solved with a number of queries which is polynomial in \(n\) (in fact, no more than \(O(n^{3/2})\)). The proof is via a careful argument using the Murnaghan-Nakayama rule. The basic idea is first to determine the principal hook lengths of \(\lambda\) (that is, the hook lengths \(h(r,r)\)) by querying values \(f(\pi)\) for \(\pi\) with a very long cycle. Then one must determine the leg-lengths of these hooks. It turns out that the most difficult part is to distinguish \(\lambda\) from a very similar partition called the \textit{doppelgänger} of \(\lambda\). Although the proof is long, the paper is very well written, and gives a nice introduction to character calculations for the symmetric group. It would have been nice to see some potential applications of these results, but nevertheless the paper is an enjoyable read.