25
$\begingroup$

Consider a Young diagram $\lambda = (\lambda_1,\ldots,\lambda_\ell)$. For a square $(i,j) \in \lambda$, define hook numbers $h_{ij} = \lambda_i + \lambda_j' -i - j +1$ and complementary hook numbers $q_{ij} = i + j -1$. Let $$H(\lambda) = \prod_{(i,j) \in \lambda} h_{ij} \,, \qquad Q(\lambda) = \prod_{(i,j) \in \lambda} q_{ij}\,. $$

Question: Is there an elementary proof of the following inequality: $$H(\lambda) \le Q(\lambda), $$ where the inequality becomes the equality only for rectangular shapes.

For example, when $\lambda = (3,2,1)$ we have $$H(\lambda)=5\cdot 3 \cdot 3 \cdot 1\cdot 1 \cdot 1 = 45, \qquad Q(\lambda)=1\cdot 2 \cdot 2 \cdot 3\cdot 3 \cdot 3 = 108. $$ Let me mention that $$\sum_{(i,j) \in \lambda} h_{ij} = \sum_{(i,j) \in \lambda} q_{ij}, $$ so somehow this says that $q_{ij}$ are more evenly distributed than $h_{ij}$.

Note: this inequality is a corollary of the results in our recent paper. The proof of the main result is algebraic and quite involved.

P.S. Originally posted on MSE since I thought this might be an easy exercise. Now I don't.

UPDATE (July 8, 2015): Petrov's elegant proof gives a stronger result. In particular, it proves what I suggested above, that the variance of complementary hooks $(q_{ij})$ is smaller than that of the usual hooks $(h_{ij})$. To see this, take $\varphi = x^2$ and use $Var(X) = E[X^2] - E[X]^2$.

Note also, as explained in the comments, the proof shows the hook numbers majorize the complementary hooks, when both are ordered from largest to smallest. For the example above: $5 \ge 3,$ $5+3\ge 3+3$, etc. This is quite remarkable and perhaps even counterintuitive.

SECOND UPDATE: We just wrote a paper on the subject with a different proof.

$\endgroup$
  • 2
    $\begingroup$ Is it true that the array $(h)$ majorates $(q)$, then the inequality would follow from Karamata inequality for the concave function $\log$? $\endgroup$ – Fedor Petrov Jul 7 '16 at 4:40
  • $\begingroup$ @Fёdor: This is a nice idea. While I don't have a counterexample, there is no natural ordering on squares of $\lambda$, so I sort of doubt that. $\endgroup$ – Igor Pak Jul 7 '16 at 5:48
  • $\begingroup$ $k$ squares with minimal complimentary hooks form a Young subdiagram of $\lambda$ situated in first few diagonals (we may choose them so, at least). and what we want is to find $k$ squares in $\lambda$ with at most as large sum of hooks. Maybe, some clever rearrangements work. $\endgroup$ – Fedor Petrov Jul 7 '16 at 6:17
  • 2
    $\begingroup$ It seems to me like the majorization inequality should hold for trees as well (and maybe other classes of posets) but I haven't been able to adapt Fedor's proof. As far as the weaker statement that the moments of the sequence of hooks are greater than the moments of the complementary hooks, that has a simple combinatorial proof for young diagrams and trees alike. $\endgroup$ – Gjergji Zaimi Jan 8 '17 at 19:10
  • 1
    $\begingroup$ I am fascinated by this phenomenon and I'm glad you figured out he case of trees as well. For a general poset $P$ we can define the hook lengths as the exponents in the denominator of the generating function of its P-partitions, and the contents as the same but for the dual poset. It seems like hooks will majorize contents whenever $P$ is a D-complete poset (and maybe more), and this seems to signal that this story might also have a commutative algebra analog. $\endgroup$ – Gjergji Zaimi Mar 31 at 18:05
16
$\begingroup$

Not sure, please check carefully. (Well, now more sure and the argument is more direct.)

I claim that the array $(h)$ majorates the array $(q)$, that is, $\sum \varphi (h_{ij})\geqslant \sum \varphi(q_{ij})$ for any convex function $\varphi$, in particular for $-\log$, that is your inequality.

Denote the hook lengths of the first (largest) column by $0<c_1<c_2<\dots<c_m$. Then the hooks in $i$-th row, which contains $c_i-i+1$ squares, are all numbers from 1 to $c_i$ except $c_i-c_1$, $c_i-c_2$, $\dots$, $c_i-c_{i-1}$ (this elementary claim is well-known, it shows the equivalence of Frobenius and the hook length formulae.) That is, $$ A:=\sum \varphi(h_{ij})=\sum_i \bigl(\varphi(1)+\ldots+\varphi(c_i)\bigr)-\sum_{i<j} \varphi(c_j-c_i). $$ Clearly $$ B:=\sum \varphi(q_{ij})=\sum_i \bigl(\varphi(m-i+1)+\ldots+\varphi(c_i+m-2i+1)\bigr). $$

For $i<j$, we have: $$ \varphi(j-i)+\varphi(c_j-i+1)\geqslant \varphi(c_j-c_i)+\varphi(c_i+j-2i+1), $$ since for $c_j=c_i+j-i$ the equality takes place, and the difference of two sides increases as a function of $c_j\in [c_i+j-i,+\infty)$. Summing up these inequalities over all pairs $i<j$ we get the desired inequality $A-B\geqslant 0$.

If $\varphi$ is strictly convex, then all inequalities are sharp only for a rectangle.

$\endgroup$
  • $\begingroup$ I am slightly confused by the "array $(h)$ majorates array $(q)$" implication. Is it standard that if the inequality holds for all $\varphi$, then there is an ordering? $\endgroup$ – Igor Pak Jul 8 '16 at 2:19
  • 3
    $\begingroup$ Karamata's inequality (for any convex functions $\varphi$) is known to be a criterion of majorization. Just apply it to the convex functions $\max(x-T,0)$ with all $T$. I think, it must be written explicitly in standard references like Marshall-Olkin. en.m.wikipedia.org/wiki/Karamata%27s_inequality $\endgroup$ – Fedor Petrov Jul 8 '16 at 6:51
  • 3
    $\begingroup$ ++ Another beautiful inequality proof by Fedor! $\endgroup$ – Suvrit Jul 8 '16 at 13:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.