Half-baked: systematic, elementary “Russian” proof of the hook length formula (HLF)

This is mostly a condensed version of the corner-recursive proof of HLF from http://www.combinatorics.org/ojs/index.php/eljc/article/view/v15i1r45 in “Russian notation” (as opposed to English or French notation; IMO this clarifies the proof), with some commentary. (See also http://mathoverflow.net/q/168851/25123 for what may be a generalization, though I’m not familiar with it myself.)

To-do: compare with representation theory proof.

Link for self: Stanley’s generating function proof (Wikipedia mentions “reverse plane partitions”—the point seems to be that by considering more general labelings than 1,2,\dots,|\lambda|, one can extract enough structure for a nice generating function), Theorem 17 of http://pfeinsil.math.siu.edu/MATH/MatrixTree/gessel-determinants_paths_and_plane_partitions.pdf

hook length blog picture

Russian notation, with the slopes of the rim edges (up or down) labeled as in the diagram for \lambda = 7+7+4+4+2+0+0+\dots, clarifies the additive-combinatorial nature of hook lengths: hook lengths are given by the differences between the half-integers indexing the upward and downward “ends” of a hook (see also Section 2 of http://arxiv.org/abs/1507.04290v4 for exposition on application to so-called “core partitions”). From cursory googling it seems considering “negative hook lengths” along these lines can be useful (see http://www.math.ucsd.edu/~fan/mypaps/fanpap/10hook.pdf).

Anyways, given a partition \lambda, it is natural in the context of hooks (illuminates factorial-like structure) and HLF (in view of out-corner-removal recursion) to keep track of the “in-corners” y_0,\dots,y_m and “out-corners” x_1,\dots,x_m ordered as a sequence y_0<x_0<y_1<x_1<\dots<x_m<y_m (see diagram). For instance, the product of hook lengths is \prod_{1\le i\le j\le m} \prod_{u+0.5\in (x_j,y_j)}\prod_{v+0.5\in (y_{i-1},x_i)} (u-v). (Note that this formula holds for any sequence y_0 \le x_0\le y_1\le x_1\le \dots\le x_m\le y_m whose x_i contain all out-corners and y_j contain all in-corners.) Removing an out-corner essentially corresponds to replacing some < x_i < with the sub-sequence \le x_i -1 < x_i < x_i + 1 \le. (We have an additional relation \sum x_i = \sum y_j from the placement of the vertex of the partition at the origin, but this is unimportant as our problem is invariant under horizontal translation.)

Idle question for self: Is there a nice generating function in these coordinates? Connection to core partition coordinates?

Now, we induct/recurse based on the following observation: any labeling (i.e. standard Young tableau on \lambda) has maximal number n = |\lambda| on some “out-corner” of \lambda. (The out-corners can also be thought of as “rim hooks” of length 1, where “rim hooks” are hooks whose removal leaves a smaller partition remaining.)

Thus, by looking at the set of hook lengths under removal of out-corners, it suffices, after some telescoping cancellation (note that every hook either changes by length 0 or 1, and most change by 0, i.e. stay the same; from core partitions perspective, think of corners as 1-rim-hooks), to prove that |\lambda| = -\sum_{\ell=1}^{m} \prod_{j=0}^{m} (x_\ell - y_j) \prod_{j\ne \ell}(x_\ell - x_j)^{-1}.

However, by decomposing into rectangular cells as in the diagram, one has |\lambda| = \sum_{1\le i\le j\le m} (y_j - x_j)(x_i - y_{i-1}). (This is quadratic in the position coordinates x_i,y_j, as expected.)

It is, however, true algebraically that \sum_{\ell=1}^{m} \prod_{j=0}^{m} (x_\ell - y_j) \prod_{j\ne \ell}(x_\ell - x_j)^{-1} = \sum_{1\le i\le j\le m} (x_j - y_j)(x_i - y_{i-1}). This follows from the general identity \sum_{i=1}^{m} P(x_i)\prod_{j\ne i}(x_i - x_j) = [X^{m-1}]R(X) for any polynomial P, where R is the remainder P\mod{\prod_{i=1}^{m} (X - x_i)} (a possibly-zero polynomial of degree at most m-1), which itself follows from either finite differences with arbitrary (in particular, not necessarily equal) steps—induct on m—or Lagrange interpolation—look at the “leading” (i.e. X^{m-1}) coefficient of \sum_i P(x_i) \prod_{j\ne i}(X - x_j)(x_i - x_j)^{-1} = R(X)—or partial fractions—decompose \frac{1}{R(X)}, and compare power series of both sides. (This is, incidentally, related to the theory of the different ideal in algebraic number theory: see Problem 1 at http://math.mit.edu/classes/18.785/2015fa/ProblemSet6.pdf for instance.)

For the application, just take P(X) = \prod_{j=0}^{m} (X - y_j), whose quotient mod \prod_{i=1}^{m} (X-x_i) is X - (\sum y_j - \sum x_i); then [X^{m-1}]R(X) is easily computed by Vieta’s formulas, as desired.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s