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

In this post (specifically in Section 4) we give a proof of the classification of finitely generated (f.g.) modules ${M}$ over a Dedekind domain ${A}$ avoiding the notion of projective modules. (Instead we rely on pure submodules, which give a slightly more transparent/natural/direct approach to the classification problem at hand, at the expense of the greater generality afforded by the projective module approach. Along the way we also explain why these approaches are really not so different after all.)
We gradually build up from the more familiar special cases when ${A}$ is a principal ideal domain (PID) or even just a field. Along the way we discuss some relevant abstractions, such as the splitting lemma (Section 2).