PROOF OF A CONJECTURE ON MULTISETS OF HOOK NUMBERS

Amitai REGEV^{1} and Doron ZEILBERGER^{2}

The notion of hook number was originally defined for the cells of the Young diagram

D(a) := {(i, j) | 1 ≤ j ≤ k , 1 ≤ i ≤ a_{k−j+1}}

of a partition a = (a_{1}, …, a_{k}). The hook number, h(x), of a cell x = (i, j) is simply the number of cells (i′, j′) that belong to D(a), and for which either i′ = i and j′ ≤ j, or j′ = j and i′ ≥ i. However, the notion of hook-number makes sense for the cells of any finite subset of the set of fundamental cells of the two-dimensional square lattice. Since the multiset of hook lengths is obviously translation-invariant, we will assume that all our subsets of cells have their bottom-left cell placed at (1, 1), as in the definition of D(a) above.

The first author and Anatoly Vershik([RV]) defined another set, SQ(a), of unit-cells associated with a partition a = (a_{1}, …, a_{k}), defined by

SQ(a) := {(i, j) | 1 ≤ j ≤ k , a_{1} − a_{j} + 1 ≤ i ≤ 2a_{1} − a_{j}} ⋃
{(i, j) | k + 1 ≤ j ≤ 2k , 2a_{1} − a_{j−k} + 1 ≤ i ≤ 2a_{1}} ,

and the k × a_{1} rectangle:

R(a) := {(i, j) | 1 ≤ j ≤ k, 1 ≤ i ≤ a_{1}} .

Using algebraic and asymptotic methods, Regev and Vershik[RV] proved the identity

∏_{x∈SQ(a)} h(x) = ∏_{x∈D(a)} h(x) ∏_{x∈R(a)} h(x) ,

that emerged as a bonus from two distinct limit formulas for the same quantity. They conjectured the stronger multiset identity

{h(x) | x ∈ SQ(a)} = {h(x) | x ∈ D(a)} ⋃ {h(x) | x ∈ R(a)} .  (∗)

In this note we prove (∗), by only using elementary and finite considerations. This also gives a ”finite”, non-asymptotic proof of Theorem 1.2.2 of [RV]. However, ours is a non-bijective proof. Using Garsia and Milne’s celebrated Involution Principle, it should be possible to bijectify our proof, but it would still be interesting to find some cannonical bijection between these two multisets.

1 Department of Mathematics, Pennsylvania State University, University Park, PA 16802, USA; and Department

of Theoretical Mathematics, The Weizmann Institute of Science, Rehovot 76100, Israel; regev@math.psu.edu ; Supported in part by N.S.F. Grant No. DMS-94-01197.

2 Department of Mathematics, Temple University, Philadelphia, PA 19122, USA. zeilberg@math.temple.edu ;

http://www.math.temple.edu/~zeilberg. Supported in part by N.S.F. Grant No. DMS-95-00646.

For any integers m and n, the discrete interval {i | m ≤ i ≤ n} will be denoted by [m, n].

Denote the multiset on the left of (∗) by F_{k}(a_{1}, …, a_{k}), and the multiset on the right of (∗) by G_{k}(a_{1}, …, a_{k}). The proof of the identity would follow by induction from the following identities

F_{k}(a_{1}, …, a_{k}) − F_{k}(a_{1} − 1, …, a_{k} − 1) = {a_{i} + k − i | 1 ≤ i ≤ k} ∪ [a_{1}, a_{1} + k − 1] , (F 1)

F_{k}(a_{1}, …, a_{k−1}, 0) − F_{k−1}(a_{1}, …, a_{k−1}) = [k, a_{1} + k − 1] ,  (F 2)
G_{k}(a_{1}, …, a_{k}) − G_{k}(a_{1} − 1, …, a_{k} − 1) = {a_{i} + k − i | 1 ≤ i ≤ k} ∪ [a_{1}, a_{1} + k − 1] , (G1)
G_{k}(a_{1}, …, a_{k−1}, 0) − G_{k−1}(a_{1}, …, a_{k−1}) = [k, a_{1} + k − 1] .  (G2)

Indeed, since, trivially, F_{0}() = G_{0}(), and (F 1) and (G1) imply that

F_{k}(a_{1}, …, a_{k}) − F_{k}(a_{1} − 1, …, a_{k} − 1) = G_{k}(a_{1}, …, a_{k}) − G_{k}(a_{1} − 1, …, a_{k} − 1) ,

while (F 2) and (G2) imply

F_{k}(a_{1}, …, a_{k−1}, 0) − F_{k−1}(a_{1}, …, a_{k−1}) = G_{k}(a_{1}, …, a_{k−1}, 0) − G_{k−1}(a_{1}, …, a_{k−1}) ,

we would be done.

Now (G1) and (G2) are both easy. As for (G1), when passing from (a_{1}, …, a_{k}) to (a_{1}−1, …, a_{k}−1), the leftmost column is chopped off. Since it is leftmost, its removal does not affect the hook numbers of the remaining cells, and the hook numbers of the cells of that chopped leftmost column are {a_{1} + k − 1, a_{2} + k − 2, …, a_{k}}. Similarly the lost hook numbers in the rectangle R(a) are {a_{1}, a_{1} + 1, …, a_{1} + k − 1}.

As for (G2), passing from (a_{1}, …, a_{k−1}, 0) to (a_{1}, …, a_{k−1}), D(a) is not affected at all, while R(a) loses its top row, containing the hook numbers {k, k + 1, …, k + a_{1} − 1}.

We will next prove (F 1). It is readily seen that the hook numbers in each of the 2k rows of SQ(a) can be split into a union of discrete intervals, on each of which the discrete function x → h(x) is ‘continuous’. It can easily be seen that

F_{k}(a_{1}, …, a_{k}) = ⋃_{i=1}^{4} H_{i} where H_{i} = {h_{SQ(a)}(x) | x ∈ A_{i}} ,

where the A_{i}’s are subareas of SQ(a), given by the figure below:

3 The reader can verify that

H_{1} = ⋃_{i=1}^{k}[a_{1} − a_{i} + i, a_{1} + i − 1]

H_{2} = ⋃_{i=2}^{k} ⋃_{j=2}^{i}[ a_{j} − a_{i} + i − j + 1 , a_{j−1} − a_{i} + i − j]

H_{3} = ⋃_{i=1}^{k−1} ⋃_{j=i+1}^{k}[ a_{j} + i + k − j + 1 , a_{j−1} + i + k − j]

and

H_{4} = ⋃_{i=1}^{k}[i, a_{k} + i − 1] .

Thus,

F_{k}(a_{1}, …, a_{k}) = ⋃_{i=1}^{k}[ a_{1} − a_{i} + i , a_{1} + i − 1] ∪ ⋃_{i=2}^{k} ⋃_{j=2}^{i}[ a_{j} − a_{i} + i − j + 1 , a_{j−1} − a_{i} + i − j]

⋃_{i=1}^{k}[i, a_{k} + i − 1] ∪ ⋃_{i=1}^{k−1} ⋃_{j=i+1}^{k}[ a_{j} + i + k − j + 1 , a_{j−1} + i + k − j] .

Hence

F_{k}(a_{1}, …, a_{k}) − F_{k}(a_{1} − 1, …, a_{k} − 1) = [ a_{1} , a_{1} + k − 1 ] ∪ [ a_{k} , a_{k} + k − 1]∪

⋃_{i=1}^{k−1} ⋃_{j=i+1}^{k}{a_{j−1} + i + k − j} − ⋃_{i=1}^{k−1} ⋃_{j=i+1}^{k}{a_{j} + i + k − j} .

By changing the ‘indices of union’ i ← i + 1 , j ← j + 1 , in the first double union above we have:

F_{k}(a_{1}, …, a_{k}) − F_{k}(a_{1} − 1, …, a_{k} − 1) = [ a_{1} , a_{1} + k − 1] ∪ [ a_{k} , a_{k} + k − 1]∪

⋃_{i=0}^{k−2} ⋃_{j=i+1}^{k−1}{a_{j} + i + k − j} − ⋃_{i=1}^{k−1} ⋃_{j=i+1}^{k}{a_{j} + i + k − j} =

[ a_{1} , a_{1} + k − 1 ] ∪ [ a_{k} , a_{k} + k − 1] ∪ ⋃_{j=1}^{k−1}{a_{j} + k − j} − ⋃_{i=1}^{k−1}{a_{k} + i} =

[ a_{1} , a_{1} + k − 1 ] ∪ [ a_{k} , a_{k} + k − 1 ] ∪ ⋃_{j=1}^{k−1}{a_{j} + k − j} − [ a_{k} + 1 , a_{k} + k − 1 ] =

[ a_{1} , a_{1} + k − 1 ] ∪ {a_{k}} ∪ ⋃_{j=1}^{k−1}{a_{j} + k − j} = [ a_{1} , a_{1} + k − 1 ] ∪ {a_{j} + k − j | 1 ≤ j ≤ k} .

To conclude we must prove (F 2). The effect of having F_{k}(a_{1}, ..., a_{k−1}, 0) instead of F_{k−1}(a_{1}, ..., a_{k−1}) is to add a new cell on top of each of the right k columns, with its corresponding hook number: the rest of the hook numbers are the same in both diagrams. It is easy to verify that these additional hook numbers are {k, k + 1, ..., a_{1} + k − 1}.

REFERENCE

[RV] A. Regev and A. Vershik, Asymptotics of Young diagrams and hook numbers, Elect. J. Comb. 4(1) (1997), R22.