1. Introduction
In [
Reference Chow and Paulhus1
], T. Y. Chow and J. Paulhus raised the following question. How can you quickly identify an irreducible character
$\chi$
of
$S_n$
by querying its values
$\chi(g)$
in order to determine the partition
$\lambda$
such that
$\chi=\chi_\lambda$
? We call this the character identification problem. They were interested in the number of queries required to identify
$\chi$
, and they gave an algorithmic solution where the number of queries is polynomial in n.
In Section 3 of this paper we give a different solution to the character identification problem. We show that any irreducible character of
$S_n$
can be identified from at most n values. We introduce, for any character
$\chi$
of
$S_n$
, a symbol. If
$\chi$
is irreducible, then the symbol is the Frobenius symbol of a partition
$\lambda$
and
$\chi=\chi_\lambda$
. If the symbol is not a Frobenius symbol of a partition of n, then the character is not irreducible. The symbol is inexpensive to compute and relies on only a small number of values, each of which can be computed quickly even for very large n if
$\chi$
is irreducible.
In Section 5 we consider what might at first seem to be a much more difficult problem. Let
$\chi_1,\chi_2,\ldots,\chi_{p_n}$
and
$g_1^{S_n},g_2^{S_n},\ldots,g_{p_n}^{S_n}$
be the irreducible characters and conjugacy classes of
$S_n$
, written in some order, and let T be the character table of
$S_n$
with respect to these orderings, so
$T=[\chi_i(g_j)]_{1\leq i,\,j\leq p_n}$
. If all of the entries of T are covered up and you are allowed to uncover one entry at a time, then how do you quickly identify the characters
$\chi_i$
and classes
$g_j^{S_n}$
? We give an algorithmic solution to this problem and we show that if u(n) denotes the fraction of the character table that needs to be uncovered in order to identify all of the indexing characters and classes, then
$u(n)=O( n^2 \exp({-}2\pi\sqrt{n/6}))$
as
$n\to\infty$
.
2. Notation
By a partition
$\lambda$
of a positive integer n, we shall mean an integer sequence
$(\lambda_1,\lambda_2,\ldots,\lambda_{\ell(\lambda)})$
such that
$\lambda_1\geq \lambda_2\geq \ldots\geq \lambda_{\ell(\lambda)} \gt 0$
and
$\lambda_1+\lambda_2+\ldots+\lambda_{\ell(\lambda)}=n$
. Associated to
$\lambda$
is the usual partition
$\lambda'$
with parts
$\lambda'_i=|\{k\,{:}\,\lambda_k\geq i\}|$
,
$1\leq i\leq \lambda_1$
. The number of partitions of n is denoted
$p_n$
and is asymptotic to
$\frac{1}{4n\sqrt{3}}{\exp}\big(\frac{2\pi}{\sqrt{6}}\sqrt{n}\big)$
.
Identifying a partition
$\lambda$
with its diagram of boxes b, we also identify a box b with its location (i, j). Let
$\mathfrak k(\lambda)=\max(\{i\,{:}\,(i,i)\in\lambda\}\cup\{0\})$
. Associated to each box
$b=(i,j)\in \lambda$
is the content
$c(b)=j-i$
, the hook
\[\mathfrak H_{(i,\ j)}(\lambda)=\{(i,u)\,{:}\,j\leq u\leq \lambda_i\}\cup\{(v,j)\,{:}\,i\leq v\leq \lambda'_j\},\]
the length of the hook
$\mathfrak h_{(i,\ j)}(\lambda)=|\mathfrak H_{(i,\ j)}(\lambda)|$
, and the partition
\[\lambda(i,j)=\{(u,v)\in \lambda \,{:}\, u\geq i \text{ and } v\geq j\}.\]
The principal hooks and their lengths are denoted
\[\mathfrak H_i(\lambda)=\mathfrak H_{(i,\,i)}(\lambda),\quad {\mathfrak h_i(\lambda)=\mathfrak h_{(i,\,i)}(\lambda)},\quad i=1,2,\ldots,\mathfrak k(\lambda).\]
For
$1\leq i\leq \mathfrak k(\lambda)$
, let
$\mathfrak{a}_i(\lambda)=\lambda_i-i$ and $\mathfrak{b}_i(\lambda)=\lambda'_i-i$
, so
$\mathfrak{a}_i(\lambda)+\mathfrak{b}_i(\lambda)+1=\mathfrak{h}_i(\lambda)$
, and let
$\mathfrak{c}_i(\lambda)=\sum_{b\in\lambda(i,\,i)} c(b)$
. Let
\begin{align*}\mathfrak{a}(\lambda)&=(\mathfrak{a}_1(\lambda),\mathfrak{a}_2(\lambda),\ldots,\mathfrak{a}_{\mathfrak k(\lambda)}(\lambda)),&\quad\mathfrak{b}(\lambda)&=(\mathfrak{b}_1(\lambda),\mathfrak{b}_2(\lambda),\ldots,\mathfrak{b}_{\mathfrak k(\lambda)}(\lambda)),\\ \mathfrak{c}(\lambda)&=(\mathfrak{c}_1(\lambda),\mathfrak{c}_2(\lambda),\ldots,\mathfrak{c}_{\mathfrak k(\lambda)}(\lambda)),&\mathfrak{h}(\lambda)&=(\mathfrak{h}_1(\lambda),\mathfrak{h}_2(\lambda),\ldots,\mathfrak{h}_{\mathfrak k(\lambda)}(\lambda)).\end{align*}
Given two integer sequences
$a=(a_1,a_2,\ldots,a_k)$
and
$b=(b_1,b_2,\ldots,b_k)$
, we write
${(a\mid b)}=(a_1,a_2,\ldots,a_k\mid b_1,b_2,\ldots,b_k)$
. If
\begin{equation} a_1 \gt a_2 \gt \ldots \gt a_k\geq 0,\quad b_1 \gt b_2 \gt \ldots \gt b_k\geq 0,\end{equation}
then
$(a\mid b)$
is Frobenius’s notation, called the Frobenius symbol, for the unique partition
$\lambda$
of
$\sum_{i=1}^k (a_i+b_i+1)$
such that
$\lambda_i=a_i+i$
and
$\lambda'_i=b_i+i$
for
$1\leq i\leq k$
. If (2·1) does not hold, then
$(a\mid b)$
is not the Frobenius symbol of a partition.
If
$\lambda$
and
$\mu$
are partitions of
$n \gt 0$
, then
$\chi_\lambda$
denotes the irreducible character of
$S_n$
associated with
$\lambda$
in the usual way, and
$\chi_\lambda(\mu)$
denotes the value
$\chi_\lambda(g)$
for any g with cycle type
$\mu$
, meaning the parts of
$\mu$
are the periods of the various cycles of g.
In Section 3 we use square brackets for partitions in order to emphasise that the following convention is in play. If
$\chi$
is a character of
$S_n$
and
$\nu=(\nu_1,\nu_2,\ldots,\nu_l)$
is a partition of
$k\leq n$
, then by
$\chi([\nu_1,\nu_2,\ldots,\nu_l])$
we mean
$\chi((\nu_1,\nu_2,\ldots,\nu_l,1,1,\ldots,1))$
with
$n-k$
appended 1’s.
3. Identifying characters
In Definition 3·5 we associate to any character
$\chi$
a symbol
$(\mathfrak a(\chi)\mid\mathfrak b(\chi))$
, and in Theorem 3·6 we show that if
$\chi\in\mathrm{Irr}(S_n)$
, then the symbol is the Frobenius symbol of the partition
$\lambda$
such that
$\chi=\chi_\lambda$
. Important for us will be the result of Frobenius [Reference Frobenius2, Equation (16)] that for any
$\chi_\lambda\in\mathrm{Irr}(S_n)$
,
\begin{equation} \mathfrak c_1(\lambda)=\frac{\binom{n}{2}\chi_{\lambda}((1\, 2))}{\chi_\lambda(1)},\end{equation}
where we take
$\chi_{\lambda}((1\, 2))=0$
if
$n=1$
. See [Reference Miller8, Theorem 3·1] for a more general result.
Definition 3·1. For any character
$\chi$
of
$S_n$
, we define sequences
\[{\mathfrak h(\chi)=(\mathfrak h_1(\chi),\mathfrak h_2(\chi),\ldots,\mathfrak h_{\mathfrak k(\chi)}(\chi))},\quad {\mathfrak d(\chi)=(\mathfrak d_1(\chi),\mathfrak d_2(\chi),\ldots,\mathfrak d_{\mathfrak k(\chi)+1}(\chi))}\]
recursively as follows.
-
(1)
$\mathfrak d_1(\chi)=\chi(1)$
and
$\mathfrak d_2(\chi)=\chi([\mathfrak h_1(\chi)])$
, where
$\mathfrak h_1(\chi)$
is the first element in the sequence
$n_1\,{:\!=}\,n,n_1-1,\ldots,1$
such that
$\chi([\mathfrak h_1(\chi)])\neq 0$
. -
(2) Given
$\mathfrak h_1(\chi),\mathfrak h_2(\chi),\ldots,\mathfrak h_{u-1}(\chi)$
and
$\mathfrak d_1(\chi),\mathfrak d_2(\chi),\ldots,\mathfrak d_u(\chi)$
with
$u\geq 2$
,-
(a) if
$\sum_{i=1}^{u-1} \mathfrak h_i(\chi)=n$
or
$\mathfrak h_{u-1}(\chi)\leq 2$
, then
$\mathfrak k(\chi)=u-1$
; -
(b) if
$\sum_{i=1}^{u-1} \mathfrak h_i(\chi) \lt n$
and
$\mathfrak h_{u-1}(\chi) \gt 2$
, then
${n_u= \min\{\mathfrak h_{u-1}(\chi)-2,n_{u-1}-\mathfrak h_{u-1}(\chi)\}}$
,
$\mathfrak h_u(\chi)$
is the first element in the sequence
$n_u,n_u-1,n_u-2,\ldots, 1$
such that
${\chi([\mathfrak h_1(\chi),\mathfrak h_2(\chi),\ldots, \mathfrak h_u(\chi)])\neq 0}$
, and
$\mathfrak d_{u+1}(\chi)=\chi([\mathfrak h_1(\chi),\mathfrak h_2(\chi),\ldots, \mathfrak h_u(\chi)])$
.
-
Lemma 3·2.
If
$\chi=\chi_\lambda\in\mathrm{Irr}(S_n)$
, then
\[\mathfrak k(\chi)=\mathfrak k(\lambda),\quad \mathfrak h_i(\chi)=\mathfrak h_i(\lambda),\quad \mathfrak d_i(\chi)=\pm\chi_{\lambda(i,\,i)}(1),\quad i=1,2,\ldots,\mathfrak k(\chi).\]
Proof. This is by the Murnaghan–Nakayama rule, since for any nonempty partition
$\nu$
, the hook
$\mathfrak H_{(1,1)}(\nu)$
has more boxes than any other hook
$\mathfrak H_b(\nu)$
,
$b\neq(1,1)$
, and it has at least two more boxes than any other principal hook
$\mathfrak H_{(j,\,j)}(\nu)$
,
$2\leq j\leq\mathfrak k(\nu)$
.
Definition 3·3. For any character
$\chi$
of
$S_n$
, let
$\mathfrak c(\chi)=(\mathfrak c_1(\chi),\mathfrak c_2(\chi),\ldots,\mathfrak c_{\mathfrak k(\chi)}(\chi))$
,
\[ \mathfrak c_i(\chi)= \frac{\binom{n-\sum_{j=1}^{i-1}\mathfrak h_j(\chi)}{2}\chi([\mathfrak h_1(\chi),\mathfrak h_2(\chi),\ldots, \mathfrak h_{i-1}(\chi) ,2])}{\mathfrak d_i(\chi)},\quad i=1,2,\ldots,\mathfrak k(\chi), \]
with the convention that
$\mathfrak c_{\mathfrak k(\chi)}(\chi)=0$
if
$\mathfrak h_{\mathfrak k(\chi)}(\chi)=1$
.
Lemma 3·4.
If
$\chi=\chi_\lambda\in\mathrm{Irr}(S_n)$
, then
$\mathfrak c(\chi)=\mathfrak c(\lambda)$
.
Definition 3·5. For any character
$\chi$
of
$S_n$
, we define
$\mathfrak a(\chi)=(\mathfrak a_1(\chi),\mathfrak a_2(\chi),\ldots,\mathfrak a_{\mathfrak k(\chi)}(\chi))$
recursively as follows.
-
(1)
$\mathfrak a_{\mathfrak k(\chi)}(\chi)=\frac{1}{\mathfrak h_{\mathfrak k(\chi)}(\chi)}(\mathfrak c_{\mathfrak k(\chi)}(\chi)+\binom{\mathfrak h_{\mathfrak k(\chi)}(\chi)}{2})$
. -
(2) For
$i=\mathfrak k(\chi)-1,\mathfrak k(\chi)-2,\ldots, 1$
,
\[ \begin{split}\mathfrak a_i(\chi) = \mathfrak a_{i+1}(\chi)&+\frac{1}{\mathfrak h_i(\chi)}\left[\mathfrak c_i(\chi)-\mathfrak c_{i+1}(\chi) -\binom{\mathfrak a_{i+1}(\chi)+1}{2}+\binom{\mathfrak h_{i+1}(\chi)-\mathfrak a_{i+1}(\chi)}{2}\right.\\ &\ \ \left.+\binom{\mathfrak h_i(\chi)-\mathfrak h_{i+1}(\chi)}{2}+ (\mathfrak h_{i+1}(\chi)-\mathfrak a_{i+1}(\chi)-1)(\mathfrak h_i(\chi)-\mathfrak h_{i+1}(\chi))\right]. \end{split} \]
We define
$\mathfrak b(\chi)=(\mathfrak b_1(\chi),\mathfrak b_2(\chi),\ldots,\mathfrak b_{\mathfrak k(\chi)}(\chi))$
, where
$\mathfrak b_i(\chi)=\mathfrak h_i(\chi)-\mathfrak a_i(\chi)-1$
.
Theorem 3·6.
If
$\chi\in\mathrm{Irr}(S_n)$
, then
$(\mathfrak a(\chi)\mid \mathfrak b(\chi))$
is the Frobenius symbol of a partition
$\lambda$
and
$\chi=\chi_\lambda$
.
Proof. Suppose
$\chi=\chi_\lambda\in\mathrm{Irr}(S_n)$
. The assertion is then
${(\mathfrak a(\chi)\mid \mathfrak b(\chi))=(\mathfrak a(\lambda)\mid \mathfrak b(\lambda))}$
. By Lemma 3·2,
$\mathfrak h(\chi)=\mathfrak h(\lambda)$
, so the claim reduces to
$\mathfrak a(\chi)=\mathfrak a(\lambda)$
.
Let (I) and (II) denote the statements obtained by replacing
$\chi$
by
$\lambda$
everywhere in parts (1) and (2) of Definition 3·5. Since
$\mathfrak h(\chi)=\mathfrak h(\lambda)$
and
$\mathfrak c(\chi)=\mathfrak c(\lambda)$
by Lemmas 3·2 and 3·4, we have that if (I) and (II) both hold, then
$\mathfrak a(\chi)=\mathfrak a(\lambda)$
.
For (I), we have
\[\mathfrak c_{\mathfrak k(\lambda)}(\lambda) =\binom{\mathfrak a_{\mathfrak k(\lambda)}(\lambda)+1}{2}-\binom{\mathfrak h_{\mathfrak k(\lambda)}(\lambda)-\mathfrak a_{\mathfrak k(\lambda)}(\lambda)}{2} =\mathfrak a_{\mathfrak k(\lambda)}(\lambda) \mathfrak h_{\mathfrak k(\lambda)}(\lambda) -\binom{\mathfrak h_{\mathfrak k(\lambda)}(\lambda)}{2}.\]
For (II), we have
\[ \mathfrak c_i(\lambda)-\mathfrak c_{i+1}(\lambda)=\sum_{b\in \mathfrak H_i(\lambda)}c(b) = \sum_{b\in \mathfrak H_{i+1}(\lambda)}c(b) +\sum_{{b\in \mathfrak H_i(\lambda)}\atop{c(b) \gt \mathfrak a_{i+1}(\lambda)}}c(b) +\sum_{{b\in \mathfrak H_i(\lambda)}\atop{c(b) \lt -\mathfrak b_{i+1}(\lambda)}}c(b). \]
So, with
$s=\mathfrak a_i(\lambda)-\mathfrak a_{i+1}(\lambda)$
and
$t=\mathfrak b_i(\lambda)-\mathfrak b_{i+1}(\lambda)$
,
\begin{equation} \begin{split} \mathfrak c_i(\lambda) = \mathfrak c_{i+1}(\lambda) +\binom{\mathfrak a_{i+1}(\lambda)+1}{2}&-\binom{\mathfrak b_{i+1}(\lambda)+1}{2}\\ &\!\!\!\!\!\!\!\!+ \binom{s+1}{2} + s \mathfrak a_{i+1}(\lambda) - \binom{t+1}{2} -t \mathfrak b_{i+1}(\lambda).\\[-25pt] \end{split} \end{equation}
Now
$t=\mathfrak h_i(\lambda)-\mathfrak h_{i+1}(\lambda)-s$
, so
\[\binom{s+1}{2}-\binom{t+1}{2}=(1+\mathfrak h_i(\lambda)-\mathfrak h_{i+1}(\lambda))s-\binom{\mathfrak h_i(\lambda)-\mathfrak h_{i+1}(\lambda)+1}{2}.\]
Further substituting elsewhere in (3·2) the relations
$s=\mathfrak a_i(\lambda)-\mathfrak a_{i+1}(\lambda)$
,
$t=(\mathfrak h_i(\lambda)-\mathfrak h_{i+1}(\lambda))-(\mathfrak a_i(\lambda)-\mathfrak a_{i+1}(\lambda))$
, and
$\mathfrak b_{i+1}(\lambda)=\mathfrak h_{i+1}(\lambda)-\mathfrak a_{i+1}(\lambda)-1$
, so that both sides of (3·2) are entirely in terms of
$\mathfrak a_l(\lambda)$
’s,
$\mathfrak h_l(\lambda)$
’s, and
$\mathfrak c_l(\lambda)$
’s, and then solving for
$\mathfrak a_{i+1}(\lambda)$
, we obtain (II).
Corollary 3·7.
If
$\chi$
is a character of
$S_n$
and
$(\mathfrak a(\chi)\mid\mathfrak b(\chi))$
is not the Frobenius symbol of a partition of n, then
$\chi$
is not irreducible.
Proof. This follows from Theorem 3·6.
Proposition 3·8.
$(\mathfrak a(\chi)\mid\mathfrak b(\chi))$
requires
$\leq n$
values
$\chi(g)$
for any character
$\chi$
of
$S_n$
.
Proof. If
$\mathfrak h_{\mathfrak k(\chi)}(\chi)\geq 2$
, then the number of values
$\chi(g)$
that go into
$\mathfrak h(\chi)$
and
$\mathfrak d(\chi)$
is
\[1+(n-\mathfrak h_1(\chi)+1)+\sum_{i=1}^{\mathfrak k(\chi)-1}(\mathfrak h_i(\chi)-\mathfrak h_{i+1}(\chi)-1) =n-\mathfrak h_{\mathfrak k(\chi)}(\chi)-\mathfrak k(\chi)+3.\]
If
$\mathfrak h_{\mathfrak k(\chi)}(\chi) \lt 2$
, then
$\mathfrak h(\chi)$
and
$\mathfrak d(\chi)$
together use
$n-\mathfrak h_{\mathfrak k(\chi)}(\chi)-\mathfrak k(\chi)+2$
queries, since after querying
$\chi([\mathfrak h_1(\chi),\mathfrak h_2(\chi),\ldots,\mathfrak h_{\mathfrak k(\chi)-1}(\chi),2])=0$
, it follows that
$\mathfrak h_{\mathfrak k(\chi)}(\chi)=1$
and
$\mathfrak d_{\mathfrak k(\chi)}(\chi)=\mathfrak d_{\mathfrak k(\chi)-1}(\chi)$
, i.e.
$\mathfrak d_{\mathfrak k(\chi)}(\chi)$
was already queried earlier in the algorithm.
If
$\mathfrak h_{\mathfrak k(\chi)}(\chi) \gt 2$
, then
$\mathfrak c(\chi)$
uses
$\mathfrak k(\chi)$
additional queries. If
$\mathfrak h_{\mathfrak k(\chi)}(\chi)\leq 2$
, then
$\mathfrak c(\chi)$
uses
$\mathfrak k(\chi)-1$
queries, since
$\mathfrak c_{\mathfrak k(\chi)}(\chi)=0$
if
$\mathfrak h_{\mathfrak k(\chi)}(\chi)=1$
, and the values that go into
$\mathfrak c_{\mathfrak k(\chi)}(\chi)$
were already queried for
$\mathfrak d(\chi)$
if
$\mathfrak h_{\mathfrak k(\chi)}(\chi)=2$
.
So if
$q(\chi)$
denotes the number of queries to construct
$(\mathfrak a(\chi)\mid \mathfrak b(\chi))$
, then
\begin{equation} q(\chi)=\begin{cases} n-\mathfrak h_{\mathfrak k(\chi)}(\chi)+3 & \text{if $\mathfrak h_{\mathfrak k(\chi)}(\chi)\geq 3$,}\\ n & \text{if $\mathfrak h_{\mathfrak k(\chi)}(\chi)\leq 2$.} \end{cases} \end{equation}
Remark 3·9. For
$\chi\in\mathrm{Irr}(S_n)$
, all of the queried values
$\chi(g)$
that go into computing
${(\mathfrak a(\chi)\mid\mathfrak b(\chi))}$
are trivial to compute even if n is very large, since each is either trivially zero in the sense of [
Reference Miller and Scheinerman9
] (for the
$\mathfrak h_i(\chi)$
’s), can be quickly computed by using the so-called hook-length formula [
Reference James and Kerber3, Reference Macdonald4
] (the
$\mathfrak d_i(\chi)$
’s), or can be quickly computed using the formula given by Definition 3·3 and Lemma 3·4 (the
$\mathfrak c_i(\chi)$
’s).
4. Identifying classes
We now deal with the natural problem of determining a class
$g^{S_n}$
from a set of values
${\chi_\lambda(g)}$
. The solution is given by the following well-known lemmas. Let
\[ \xi_{n,k}=\chi_{(n-k,1,1,\ldots,1)}\in\mathrm{Irr}(S_n),\quad k=0,1,2,\ldots,n-1.\]
If V is an
$S_n$
-module, let
$\chi_V$
denote the character afforded by V. Given a partition
$\lambda$
of n, let
$V_\lambda$
denote the
$S_n$
-module affording
$\chi_\lambda\in \mathrm{Irr}(S_n)$
.
Lemma 4·1.
$\xi_{n,k}=\chi_{\wedge^k V_{(n-1,1)}}$
for
$k=0,1,2,\ldots,n-1$
.
Proof. This follows by induction on n and the branching rule. The case
$n=1$
is clear. Assuming the claim for a fixed
$n\geq 1$
and considering the next case, certainly
$\wedge^kV_{(n,1)}=V_{(n+1)}$
if
$k=0$
. If
$1\leq k\leq n$
, then as
$S_n$
-modules,
\[\wedge^k V_{(n,1)}\cong \wedge^k(V_{(n)}\oplus V_{(n-1,1)}) \cong \wedge^{k-1} V_{(n-1,1)}\oplus \wedge^{k} V_{(n-1,1)},\]
and by hypothesis the right-hand side is isomorphic to
$V_{(n-k+1,1,1,\ldots,1)}\oplus V_{(n-k,1,1,\ldots,1)}$
if
${k\neq n}$
, and
$V_{(n-k+1,1,1,\ldots,1)}$
if
$k=n$
. By the branching rule again, this implies that, as
$S_{n+1}$
-modules,
$\wedge^k V_{(n,1)}\cong V_{(n+1-k,1,1,\ldots,1)}$
for
$k=0,1,\ldots,{n+1}$
.
Lemma 4·2.
For any partition
$\nu$
of n,
\[(X-1)\sum_{k=0}^{n-1} ({-}1)^k\xi_{n,k}(\nu) X^{n-1-k}=\prod_{k=1}^{\ell(\nu)}(X^{\nu_k}-1).\]
In particular,
$\nu$
is determined by the values
$\xi_{n,n-1}(\nu),\xi_{n,n-2}(\nu),\ldots,\xi_{n,n-\lfloor\frac{n}{2}\rfloor}(\nu)$
.
Proof. Let
$p(X)=\det(X-gI)$
for an element g with cycle type
$\nu$
under the permutation representation
$V=\mathbb C^n$
given by
$\sigma\mapsto (\delta_{i\sigma(j)})_{i,\,j}$
, so
${p(X)=\prod_{k=1}^{\ell(\nu)} (X^{\nu_k}-1)}$
. Decomposing V as
$V_{(n)}\oplus V_{(n-1,1)}$
and denoting the eigenvalues of g on
$V_{(n-1,1)}$
by
$\zeta_1,\zeta_2,\ldots,\zeta_{n-1}$
, then
\[\frac{p(X)}{X-1} = \prod_{k=1}^{n-1}(X-\zeta_k) = \sum_{k=0}^{n-1} ({-}1)^k \chi_{\wedge^kV_{(n-1,1)}}(g) X^{n-1-k}=\sum_{k=0}^{n-1}({-}1)^k\xi_{n,k}(\nu)X^{n-1-k},\]
where the last equality is by Lemma 4·1.
5. Identifying both characters and classes
Throughout this section, by character table of
$S_n$
we shall mean the table
\[[\chi_i(g_j)]_{1\leq i,\,j\leq p_n}\]
for some arbitrary but fixed ordering of the irreducible characters
$\chi_1,\chi_2,\ldots,\chi_{p_n}$
and classes
$g_1^{S_n},g_2^{S_n},\ldots,g_{p_n}^{S_n}$
. The object is to identify the characters and classes by successively querying entries
$T_{ij}$
(i.e., querying the function
$(i,j)\mapsto T_{ij}$
), which is possible only if
$n\neq 4,6$
by inspection.Footnote
1
In more visual terms, all of the entries of T are covered up and the object is to identify the characters
$\chi_i$
and classes
$g_j^{S_n}$
by successively uncovering various entries
$T_{ij}$
.
We start with two well-known facts in Lemmas 5·1 and 5·2.
Lemma 5·1.
If
$n\neq4$
and
$\chi\in\mathrm{Irr}(S_n)$
with
$\chi(1) \gt 1$
, then
$\chi(1) \gt |\chi(g)|$
for
$g\neq 1$
.
Proof. See for example [Reference Miller7, Lemma 2·5].
Lemma 5·2.
If
$n\neq 6$
and
$\chi_\lambda\in\mathrm{Irr}(S_n)$
with
$\chi_\lambda(1) \gt 1$
, then
$\chi_\lambda(1)\geq n-1$
with equality if and only if
$\lambda\in\{(n-1,1),(2,1,1,\ldots,1)\}$
.
Proof. This follows by induction on n and the branching rule.
Lemma 5·3.
If
$\lambda$
is a partition of
$n\geq 4$
, then
$\lambda=(n-k,1,1,\ldots,1)$
for some k if and only if
$\chi_{\lambda}(1)=4\chi_\lambda((1\, 2\, 3))-3\chi_\lambda((1\,2)(3\,4))$
.
Proof. By the branching rule,
$\lambda=(n-k,1,1,\ldots,1)$
for some k if and only if
$\langle {\rm Res}_{S_4}\chi_\lambda,\chi_{(2,2)}\rangle=0$
, i.e. if and only if
$\chi_{\lambda}(1)=4\chi_\lambda((1\, 2\, 3))-3\chi_\lambda((1\,2)(3\,4))$
.
Proposition 5·4.
If
$n\neq 4,6$
and all of the entries of the
$S_n$
character table
${T=[\chi_i(g_j)]_{1\leq i,\,j\leq p_n}}$
are covered up, then the row positions of the characters
\[\xi_k=\chi_{(n-k,1,1,\ldots,1)}\in\mathrm{Irr}(S_n),\quad 0\leq k\leq n-1,\]
can be determined by uncovering at most
$7p_n+n$
entries.
Proof. The object is to determine, among the
$p_n$
rows of the character table T, the positions
$i_j$
of the characters
$\xi_j=\chi_{(n-j,1,1,\ldots,1)}\in\mathrm{Irr}(S_n)$
with
$0\leq j\leq n-1$
. Along the way it will be important to determine, among the
$p_n$
columns, the positions a, b, c, d of the classes
$1^{S_n},(1\, 2)^{S_n},(1\, 2\, 3)^{S_n},(1\,2)(3\,4)^{S_n}$
. We may assume
$n \gt 6$
by inspection, since
$p_n^2 \lt 7p_n+n$
for
$n\leq 5$
.
Step 1. Determine the column a corresponding to the identity element. This can be done with
$\leq 3p_n$
moves by first uncovering an entire row of entries for some nonlinear irreducible character. This requires at most
$3p_n$
moves because there are exactly two linear characters. By Lemma 5·1, the row for any nonlinear character contains a unique largest entry in position a.
Step 2. Uncover the entries in column a to reveal all of the character degrees
$\chi(1)$
, and then locate the pair of row indices
$S=\{r \lt s\}=\{i_1,i_{n-2}\}$
that correspond to the unique characters
$\xi_1,\xi_{n-2}$
of degree
$n-1$
. There are exactly two such characters by Lemma 5·2. The cost of uncovering column a is
$\leq p_n-1$
queries.
Step 3. Uncover new entries in row r until there is one entry with absolute value
$n-3$
, one entry with absolute value
$n-4$
, and two entries with absolute value
$n-5$
. This is possible because, for any partition
$\mu$
of n,
\begin{equation} \xi_1(\mu)=({-}1)^{n-\ell(\mu)}\xi_{n-2}(\mu)=|\{i\,{:}\,\mu_i=1\}|-1. \end{equation}
Denote by
$j_1,j_2,j_3,j_4$
the positions of these entries in row r, with
$j_1$
corresponding to the entry with absolute value
$n-3$
, and
$j_2$
corresponding to the entry with absolute value
$n-4$
. From these entries and (5·1) we immediately determine
$i_1,i_{n-1},b,c,d$
. We have
$b=j_1$
,
$c=j_2$
,
\[ i_1=\begin{cases} r & \text{if $\chi_r(g_{j_1})$ is positive,}\\ s & \text{otherwise,} \end{cases} \]
$i_{n-1}$
is the single element of
$S\smallsetminus \{i_1\}$
, and
\[ d=\begin{cases} j_3 & \text{if $\chi_{i_{n-1}}(g_{j_3})$ is positive,}\\ j_4 & \text{otherwise.} \end{cases} \]
This step requires uncovering
$\leq p_n-1$
new entries.
Step 4. Use Lemma 5·3 to construct the set of desired positions
$I=\{i_0,i_1,\ldots,i_{n-1}\}$
by starting with
$I=\emptyset$
and successively going through the rows
$i=1,2,\ldots$
and including an index i in I if
$\chi_i(g_a)=4\chi_i(g_c)-3\chi_i(g_d)$
, until
$|I|=n$
. This requires uncovering at most
$2p_n-2$
new entries.
Step 5. Let
$f(i)={\binom{n}{2}\chi_i(g_b)}/{\chi_i(g_a)}$
, so if
$\chi_i=\chi_\lambda$
, then
$f(i)=\mathfrak c_1(\lambda)$
by (3·1). We then obtain the desired sequence
$i_0,i_1,\ldots,i_{n-1}$
from the set
$I=\{i_0,i_1,\ldots,i_{n-1}\}$
by using the fact that
$f(i_0) \gt f(i_1) \gt \ldots \gt f(i_{n-1})$
. Computing these
$f(i_j)$
’s requires at most
$n-2$
additional entries
$\chi_{i_j}(g_b)$
be uncovered.
Theorem 5·5.
If
$n\neq 4,6$
and the entries of the
$S_n$
character table
$[\chi_i(g_j)]_{1\leq i,\,j\leq p_n}$
are covered up, then:
-
(1) the classes
$g_j^{S_n}$
can be determined by uncovering at most
$\lfloor \frac{n}{2}\rfloor p_n+7p_n+n$
entries; -
(2) the characters
$\chi_i$
can be identified by uncovering at most
$np_n$
additional entries.
Proof. The first part follows from Lemma 4·2 and Proposition 5·4. The second part follows from the first part, since once the classes
$g_j^{S_n}$
are known, each character
$\chi_i$
can be identified by uncovering at most n additional entries by Theorem 3·6 and the query calculation in Proposition 3·8.
Theorem 5·6.
For
$n\neq 4,6$
, if the entries of the
$S_n$
character table
$[\chi_i(g_j)]_{1\leq i,\,j\leq p_n}$
are covered up and u(n) denotes the fraction of the character table that needs to be uncovered in order to identify all of the indexing characters
$\chi_i$
and classes
$g_j^{S_n}$
, then
\[u(n)=O(n/p_n)=O( n^2 \exp(-2\pi\sqrt{n/6})).\]
Proof. This follows from Theorem 5·5.
Remark 5·7. There are two alternative approaches that one might try for discovering the positions of the hook-shaped characters in Proposition 5·4, but both of these approaches come with difficulties. It is natural to try using either the column indexed by
$1^{S_n}$
or the column indexed by
$(1\, 2\, \ldots\, n)^{S_n}$
. The trouble with the identity column is that in general there can be many characters with the same degree. In fact, for any positive integer k, and for sufficiently large n, there exist k irreducible characters of
$S_n$
with the same degree. (Interestingly, there seems to be an unexplored dual version of this result where character degrees are replaced by class sizes.) However, it seems to be the case that the set of hook-shaped characters can indeed be identified using degrees. At least experimentally, with the exception of
$n=6,12,15,24,35$
, it seems to be the case that the characters
$\chi_{(n-k,1,1,\ldots,1)}\in\mathrm{Irr}(S_n)$
,
$0\leq k\leq n-1$
, are the only irreducible characters
$\chi$
of
$S_n$
such that
$\chi(1)\in\{\binom{n-1}{k}\,{:}\,0\leq k\leq n-1\}$
. It would be interesting to know if there are only a finite number of exceptional cases. Regarding the column for
$(1\, 2\, \ldots\, n)^{S_n}$
, the problem here is that there are multiple so-called “sign classes,” i.e. classes
$g^{S_n}$
such that
$\chi(g)\in\{0,1,-1\}$
for all
$\chi\in\mathrm{Irr}(S_n)$
. Nevertheless, with the exception of only a few special cases for small n, the column
$(1\, 2\, \ldots\, n)^{S_n}$
can be identified by additionally considering the number of nonzero entries. I will omit the proof of the following lemma.
Lemma 5·8.
Let
$\mu$
be a partition of n. Then the following are equivalent.
-
(i)
$\chi_\lambda(\mu)\in\{0,1,-1\}$
for all
$\lambda$
and
$\sum_{\nu}|\chi_\nu(\mu)|^2=n$
. -
(ii)
$\mu=(n)$
,
$\mu=(3,2,1)$
,
$\mu=(2,1,1)$
, or
$\mu=(1,1)$
.
So the problem of quickly locating the column indexed by
$(1\, 2\, \ldots\, n)^{S_n}$
reduces to quickly locating a column with the right number of
$\pm 1$
’s and then 0’s elsewhere. But the fraction of the character table covered by 0’s and
$\pm 1$
’s is not yet understood. The result of [
Reference Peluse and Soundararajan10
] shows that the fraction of the table covered by
$\pm 1$
’s tends to 0 as
$n\to\infty$
. The limiting behaviour for the fraction of the table covered by 0’s is not known, see [
Reference Miller5, Reference Miller6, Reference Miller and Scheinerman9
].
