Algorithmically distinguishing irreducible characters of the symmetric group

Abstract

Suppose that ${\chi }_{\lambda }$ and ${\chi }_{\mu }$ are distinct irreducible characters of the symmetric group $S_n$. We give an algorithm that, in time polynomial in $n$, constructs $\pi \in S_n$ such that ${\chi }_{\lambda }(\pi )$ is provably different from ${\chi }_{\mu }(\pi )$. In fact, we show a little more. Suppose $f={\chi }_{\lambda }$ for some irreducible character ${\chi }_{\lambda }$ of $S_n$, but we do not know $\lambda$, and we are given only oracle access to $f$. We give an algorithm that determines $\lambda$, using a number of queries to $f$ that is polynomial in $n$. Each query can be computed in time polynomial in $n$ by someone who knows $\lambda$.

34 pages, 31 figures