On my last trip through the Phantom Tollbooth, I met up with my old
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 irreducible characters of the symmetric
group are, 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 some fixed integer n, shown
in red here, and outputs an integer according to a certain rule.
There is a whole family of these irreducible characters, and they
are indexed by partitions lambda of n. The Mathemagician had a whole
warehouse full of these machines, and they were all carefully labeled
in green. But alas, some vandal had come in and ripped all the
labels off these irreducible characters, so he was no longer able
to distinguish one of them from another. So he asked me and my
co-author, Jennifer Paulhus, for some help in restoring these missing
labels.

Now this problem is not that hard in theory---at least if you know
the value of n, which I'm always going to assume you do know---because
in principle, you could just go through all possible input partitions
mu, tabulate the outputs, and then compare the results against your
favorite computer algebra package, and restore the labels that way.
That works, but it's very inefficient, because first of all, there
are a whole lot of input values you can try---a constant to the
root n, in fact---and then it's also true that for a lot of those
input values, it takes a long time for the answer to pop out. It
has high computational complexity. So what you really 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 for me to tell you a little
bit more about that, I have to say more about what irreducible
characters are.  Irreducible characters can be computed in terms
of these combinatorial gadgets called "border-strip tableaux." A
border-strip tableau is a Young diagram filled with integers that
weakly increase across rows and weakly increase down columns, and
such that for each integer, the boxes containing that particular
integer form what's called a "border strip." A border strip is a
connected set of boxes such that the rightmost box in each row is
directly beneath the leftmost box in the row above it. So for
example, the rightmost 2 in row 2 is directly beneath the leftmost
2 in row 1.

The Murnaghan-Nakayama rule tells you that the irreducible character
indexed by lambda, evaluated at mu, is given by some 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 this is an empty sum, and the character value is zero. That
is important. So for example, let's take n = 8, and let's take as
our input value mu = (8), meaning the partition with one part of
size 8. If you think about it for a moment, for most shapes lambda,
you just can't fit a border strip of length 8 inside it.  It's just
too big---unless lambda is a hook. If lambda is a hook, then the
character value is plus or minus 1; but if it's not a hook then
you're going to get an empty sum and it's going to be zero.  That's
kind of nice! So you can tell just from one input value whether or
not lambda is a hook.

If lambda is not a hook, then you can try the input (7,1), and by
similar reasoning, you can show that you're going to get zero unless
the length of the longest hook is at least 7. More generally, there
is a Proposition that if you try the sequence of inputs (n), (n-1,1),
(n-2,1,1), and so forth, then the first nonzero character value you
get in that sequence tells you the length of the largest hook.
That's the first step in our algorithm.

I'm not going to go through the whole algorithm, but just to give
you a sketch, there's a forward pass and a backward pass. In the
forward pass, we use ideas similar to the ones I've just described
to recover the principal hook lengths of lambda one at a time,
starting from the outside and going in. (A principal hook just
means that the corner of the hook lies on the main diagonal of the
Young diagram.) Once you've got the principal hook lengths, that's
a lot of information, but it doesn't tell you everything because
it still doesn't tell you for each hook, how many boxes are in the
arm versus how many are in the leg.  So there's a second pass where
we recover the arm lengths and leg lengths, starting 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 inputs, which is a lot better
than a constant to the root n. That's not actually the end of the
story; there's been an improvement by my colleague Alex Miller at
the Center for Communications Research.  Using a bit more character
theory than we did, he was able to reduce the number of inputs to
n.  Again, these values are easy-to-compute values of the characters.
And even that's not the end of the story, because n is almost
certainly not optimal.  As far as I know, the true minimum number
could be as low as log n or maybe even a constant.  If you think
about the hook-length formula or hook-length formulas for skew
shapes, you might think that you could possibly get close to a
constant number. I don't know how to prove that, but I hope some
of you will be tempted to try to improve on our results, so that
the next time the Mathemagician has this vandal, we'll be able to
solve his problem even faster!