# How to recover partition from its multiset of hook lengths?

One of the invariants associated to a partition is its multiset of hook lengths. For instance, as shown here, the partition (5,4,1) has hook lengths {1,1,1,2,3,3,4,5,5,7}. Is there a good way to go backwards (up to conjugation, of course)? An actual algorithm that does not involve brute forcing through a bunch of possibilities, and would give me one (or all) of the possible partitions?

What about the decision problem "Is this multiset the multiset of hook lengths of a partition?" For instance, for {1, 1, 1, 2, 3, 3, 4, 4, 5, 7, 8, 10} the answer is no, but I can only come up with very ad hoc ways to show that.

-
The hook length formula, discussed further down the wikipedia page you linked, provides one systematic check that rules out your example. If we have a partition of $n$, the product of the hook lengths must divide $n!$, which is clearly false in your example. –  Paul Johnson Sep 14 '10 at 13:21
How so? In this case the product of purported hook lengths is 806400, which does divide 12!. The purported dimension of the associated character of $S_12$ would then be 594 (indeed an integer), which does not occur as the dimension of an irreducible representation. So this is indeed another way to rule it out, but it does require to know the dimensions of all those representations (and even then, other examples could be constructed where such a test fails). –  Paul-Olivier Dehaye Sep 14 '10 at 15:06
Indeed, that's embarassing. Mentally divided by 10! instead of just 10. –  Paul Johnson Sep 15 '10 at 10:02
For the record, another ad hoc way I have to exclude {1, 1, 1, 2, 3, 3, 4, 4, 5, 7, 8, 10} is as follows. Only 2 cells are not in the first hook and they thus have hook lengths 1 and 2. 8 has to be next to 10, either aligned with the 2,1 we just placed or not. Both choices quickly lead to contradiction, as we now know exactly how long the arm based at 8 is. –  Paul-Olivier Dehaye Sep 15 '10 at 16:24

the same hook length multiset can be shared by arbitrarily many partitions, see http://plms.oxfordjournals.org/cgi/reprint/96/1/26.pdf and the references there.

-
True. This is something I suspected, and thanks for the link. So it does make an algorithm appear unlikely, as its task would be much harder. It doesn't help for the decision problem question, though... –  Paul-Olivier Dehaye Sep 14 '10 at 12:04
See also arxiv.org/abs/0709.0897 for a free version. –  Igor Pak Sep 14 '10 at 16:20

I wanted to at least give a systematic way to show your given multiset is not a set of hook lengths after my flubbed comment. So: taking the $n$ quotients of a partition gives us a constraint on its possible hook lengths.

In particular, take the set of all hook lengths that are divisible by $n$, and then divide each of them by $n$. This new set of numbers will be the set of hook lengths of the $n$ different partitions that are its $n$-quotients.

If your multiset came from a partition, then together its two 2-quotients would have hook lengths 1,2,2,4,5, which can't be the hook lengths of two partitions.

Alternatively, since 5 of the hook lengths were divisible by 2, together the two 2-quotients will be a partition of 5, and when translated back to the original partition will account for 10 of the 12. Therefore, the 2-core must have had size 2. But the 2-cores are exactly the staircase positions, and so 2 isn't a 2-core.

I wish I had a good source for explaining cores and quotients. I think of them by translating through the Maya diagrams , as in Figure 5 on Page 49 of this paper. Maybe The description here helps, too.

As far as an algorithm to construct the possible partitions with a given hook length set thinking in terms of Maya diagrams and possibly cores and quotients could possibly provide a useful way to control the searching and branching.

I can imagine an algorithm that starts by immediately taking just the even hook lengths and dividing them all by 2, to find the hook-lengths of the 2-quotients. Then we can find the 2-core if it exists. There would now be a lot of branching: we have to distribute the hook-lengths of the 2-quotients over all possible splittings. But once we've chosen a splitting, we can recursively call our program again on the 2-quotients, which will be much smaller partitions.

When it reaches the end, you then have to glue the original partition back together from the core and quotient and check whether the parition has the right hook lengths -- this seems quite expensive.

I make no claims that this algorithm is any good -- I don't know whether the division helps compared to the branching. But as someone who hasn't programmed much the recursion seems relatively easy to code.

-
Yes. this is the "very ad hoc" ways I was referring in my original post. Actually, the argument does not require branching if you take k=4, since you then have the multiset {1,1,2} which is supposed to be the union of 4 partitions. Since I know what those are (empty, empty, [1], ([2] or $[2]^t$)) and I know the core as well (empty), I "only" have 2 * 4! /2 possiblities to check, corresponding to the different orderings of the quotients. The hooks have to satisfy tremendous divisibility conditions, and it is precisely to clarify this that I am asking the question... –  Paul-Olivier Dehaye Sep 15 '10 at 16:03

One condition on hooks that hasn't been mentioned yet is that $$h_{(1,1)} + h_{(i,j)} = h_{(i,1)} + h_{(1,j)}.$$ (and similarly, based at other points).

When $i<>1$ and $j<>1$, this means that the cells $(1,1)$ and $(i,j)$ in that property are corners of a (unique) square, whose other two corners are the other two points.

Since 10+4 is not expressible as the sum of any two of the other given hook lengths in my negative example, we know that 4 and 4 are on the same line as 10 (not that suprising given the large size of first hook length 10 compared to the size 12, but could be useful for bigger partitions).

-