On my last trip through the Phantom Tollbooth, I paid a visit to
my good friend, the Mathemagician. The first words out of his mouth
were not, "Hi, Tim! How are you doing?" but "Somebody has ripped
all the labels off of my irreducible characters of the symmetric
group!" Now, if you don't know what an irreducible character of the
symmetric group is, then you should run, not walk, to your nearest
copy of EC2, and read up about it. (And if you didn't recognize my
allusion to the Phantom Tollbooth, then that's another book you
should read.)
But for now, just think of an irreducible character as a machine
that takes as input a partition mu of a fixed integer n, as shown
in red, and outputs an integer according to a certain rule. There
is a whole family of such machines, and they are indexed by partitions
lambda of the same integer n. The Mathemagician had a whole warehouse
full of these machines, and they were all carefully labeled, as
shown in green. But alas, some vandal had broken into the warehouse,
and ripped all the labels off the machines, so that the Mathemagician
could no longer tell them apart. So he asked me and my co-author,
Jennifer Paulhus, for help restoring the labels.
Now, in principle, this is not that hard a problem, at least if you
know the value of n, which I'm always going to assume you do know.
In the worst case, you can simply try every possible input mu,
tabulate the outputs, and compare the results against your favorite
computer algebra package. This works, but it's very inefficient,
because first of all, there are a whole lot of inputs to try---a
constant to the root n, in fact---and secondly, for some of the
inputs, you have a wait a long time for the output to pop out. The
computational complexity is high. Ideally, what you want is an
efficient algorithm, that uses as few inputs as possible, and has
low computational complexity.
The good news is that Jennifer and I were able to solve the
Mathemagician's problem. But in order to tell you more about what
we did, I have to tell you more about irreducible characters.
Irreducible characters can be computed in terms of combinatorial
gadgets called "border-strip tableaux." A border-strip tableau is
a Young diagram filled with positive integers that increase weakly
across the rows and increase weakly down the columns, with the
property that for each integer, the set of boxes containing that
integer form something called a "border strip." A border strip is
a connected set of boxes such that the rightmost box in each row
lies directly beneath the leftmost box in the row above it. So for
example, the rightmost 2 in the second row lies directly beneath
the leftmost 2 in the first row.
The Murnaghan-Nakayama rule says that the irreducible chaacter
indexed by lambda, evaluated at mu, is a certain signed sum over
all border-strip tableaux of shape lambda and type mu. "Type mu"
just means that the parts of mu give the lengths of the border
strips. Don't worry about the sign; what I want to emphasize is
if there are no border-strip tableaux of shape lambda and type mu,
then the sum is an empty sum, and the character value is zero. This
is important. So for example, let's take n = 8, and let's let
mu = (8), the partition with a single part of size 8. If you think
about it for a moment, you can see that for most shapes lambda, you
simply can't fit a border strip of length 8 inside it. It's too
big---unless lambda is a hook. If lambda is a hook, then the
character value at 8 is plus or minus 1; otherwise, the character
value is zero. That's nice! Just by taking the single input value
mu = (8), we can determine whether lambda is a hook.
If lambda is not a hook, then we can try the input value (7,1),
and by similar reasoning, we see that the character value is zero
unless the longest hook length of lambda is at least 7. More
generally, if we take the sequence of input values (n), (n-1,1),
(n-2,1,1), and so on, then the first time we hit a nonzero value
gives us the largest hook length of lambda. That's the first step
of the algorithm.
I'm not going to go through the whole algorithm, but in outline,
it has two phases. In the forward pass, we use ideas similar to the
ones I've just described to recover the lengths of the principal
hooks of lambda, from the outside in. (A principal hook just means
that the corner of the hook lies on the main diagonal of the Young
diagram.) But just knowing the principal hook lengths isn't the
whole story, because it doesn't tell you how many boxes are on the
arm versus the leg. So in the backward pass, we recover the arm
lengths, working from the inside out. This part of the algorithm
is complicated to describe in words, and it takes up most of our
paper, but fortunately, it has low computational complexity.
Anyway, our main result is that this algorithm works, and in the
worst case it takes only about n^1.5 input values, which is a lot
less than a constant to the root n. But that's not the end of
the story, because very recently, Alex Miller, a colleague of mine
at the Center for Communications Research, has improved our result.
Using a bit more character theory, he has reduced the number of
inputs to n. And even that's probably not optimal. As far as I know,
the true minimum could be log n or even a constant, perhaps using
the hook-length formula for skew shapes or something. I hope that
some of you will be tempted to work on this problem and improve on
our results, so that the next time the Mathemagician faces this
problem, we'll be able to solve it even faster!