# 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

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 (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.