
 
 
%%%%%plain TeX file of regver.tex a paper by  A. Regev and D. Zeilberger%%%

\input epsf.sty 
%begin macros
\def\C{{\cal C}}
\def\L{{\cal L}}
\def\M{{\cal M}}
\baselineskip=14pt
\parskip=10pt
\def\Tilde{\char126\relax}
\def\halmos{\hbox{\vrule height0.15cm width0.01cm\vbox{\hrule height
 0.01cm width0.2cm \vskip0.15cm \hrule height 0.01cm width0.2cm}\vrule
 height0.15cm width 0.01cm}}
\font\eightrm=cmr8 \font\sixrm=cmr6 
\font\eighttt=cmtt8
\magnification=\magstephalf
\def\lheading#1{\bigbreak \noindent {\bf#1} 
}
\parindent=0pt
\overfullrule=0in
%end macros
\bf
\centerline{PROOF OF A 
CONJECTURE ON
MULTISETS OF HOOK NUMBERS }
\medskip
\it
\centerline{ 
Amitai REGEV\footnote{$^1$}
{\baselineskip=9pt
\eightrm  \raggedright
Department of Mathematics, Pennsylvania State University,
University Park, PA 16802, USA; and
Department of Theoretical Mathematics, The Weizmann Institute
of Science, Rehovot 76100, Israel;
{\baselineskip=9pt
\eighttt regev@math.psu.edu ; 
}Supported in part by N.S.F. Grant No. DMS-94-01197.}
and Doron ZEILBERGER\footnote{$^2$}
{\baselineskip=9pt
\eightrm  \raggedright
Department of Mathematics, Temple University,
Philadelphia, PA 19122, USA.
{\baselineskip=9pt
\eighttt zeilberg@math.temple.edu ; 
\break http://www.math.temple.edu/\Tilde 
zeilberg. }
Supported in part by N.S.F. Grant No. DMS-95-00646.
}    }
\medskip
\rm
 
The notion of {\it hook number} was originally
defined for the cells of the Young diagram 
$$
D(a) \, := \,
\{ (i,j) \, \,\,\vert\,\, \, 1 \leq j \leq k \, , \, 1 \leq i \leq a_{k-j+1} \}
$$
of a partition $a=(a_1 , \dots, 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' \leq j$, or $j'=j$ and $i' \geq 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, \dots , a_k)$,
defined by
$$
SQ(a):=
\{ (i,j) \, \,\,\vert\,\, \, 1 \leq j \leq k
\,\,, \,\, a_1 -a_j+1 \leq i \leq 2 a_1 -a_j \}
\bigcup
$$
$$
\{ (i,j) \, \,\,\vert\,\, \, k+1 \leq j \leq 2k \,\,, \,\,2a_1 -a_{j-k}+1 
\leq i \leq 2 a_1 \} \quad ,
$$
and the $ k \times a_1$ rectangle:
$$
R(a):=
\{ (i,j) \, \,\,\vert\,\, \, 1 \leq j \leq k, 1 \leq i \leq  a_1 \} \quad .
$$
 
Using algebraic and asymptotic methods, Regev and Vershik[RV]
proved the identity
$$
\prod_{x \in SQ(a)} h(x) =\prod_{x \in D(a)} h(x) \prod_{x \in R(a)} h(x) 
\quad , 
$$
that emerged as
a bonus from two distinct limit formulas for the same quantity.
They conjectured the stronger {\it multiset identity}
$$
\{h(x) \, \,\,\vert\,\, \, x \in SQ(a)\}  =
\{h(x) \, \,\,\vert\,\, \, x \in D(a)\} 
\,\, \bigcup \,\, \{ h(x) \, \,\,\vert\,\,\,  x \in R(a)\}  \quad .
\eqno(*)
$$
 
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 {\it Involution Principle}, it should be possible
to {\it bijectify} our proof, but
it would still be interesting to 
find some {\it cannonical} bijection between these two multisets. 
 
For any integers $m$ and $n$,
the discrete interval $\{ i \,\,\vert\,\, m \leq i \leq n \}$ will be
denoted by $[m,n]$.
 
Denote the multiset on the left of $(*)$ by
$F_k (a_1 , \dots , a_k)$, and the multiset on the right of $(*)$
by $G_k (a_1 , \dots , a_k)$. The proof of the identity would follow
by induction from the following identities
$$
F_k(a_1 , \dots , a_k) - F_k(a_1 -1 , \dots , a_k -1) =
\{ a_i +k-i \,\,\vert\,\, 1 \leq i \leq k \} \cup [a_1,a_1+k-1] \quad ,
\eqno(F1)
$$
$$
F_k(a_1 , \dots , a_{k-1},0) - F_{k-1}(a_1  , \dots , a_{k-1}) =
[k,a_1+k-1] \quad ,
\eqno(F2)
$$
$$
G_k(a_1 , \dots , a_k) - G_k(a_1 -1 , \dots , a_k -1) =
\{ a_i +k-i \,\,\vert\,\, 1 \leq i \leq k \} \cup [a_1,a_1+k-1] \quad ,
\eqno(G1) 
$$
$$
G_k(a_1 , \dots , a_{k-1},0) - G_{k-1}(a_1  , \dots , a_{k-1}) =
[k,a_1+k-1] \quad .
\eqno(G2)
$$
 
Indeed, since, trivially, $F_0()=G_0()$, and $(F1)$ and $(G1)$ imply that
$$
F_k(a_1 , \dots , a_{k}) - F_{k}(a_1-1  , \dots , a_{k}-1) =
G_k(a_1 , \dots , a_{k}) - G_{k}(a_1-1  , \dots , a_{k}-1)  \quad ,
$$
while $(F2)$ and $(G2)$ imply
$$
F_k(a_1 , \dots , a_{k-1},0) - F_{k-1}(a_1  , \dots , a_{k-1}) =
G_k(a_1 , \dots , a_{k-1},0) - G_{k-1}(a_1  , \dots , a_{k-1}) \quad ,
$$
we would be done.
 
 
Now $(G1)$ and $(G2)$ are both easy. 
As for $(G1)$, when passing from
$(a_1 , \dots , a_k)$ to $(a_1-1 , \dots , 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 , \dots , a_k \}$. Similarly the
lost hook numbers in the rectangle $R(a)$ are
$\{ a_1, a_1+1 , \dots, a_1+k-1 \}$. 
 
As for $(G2)$, passing from $(a_1, \dots , a_{k-1}, 0)$
to $(a_1, \dots , a_{k-1})$, $D(a)$ is not affected at all,
while $R(a)$ loses its top row, containing the hook numbers
$\{ k, k+1, \dots , k+a_1-1 \}$.
 
We will next prove $(F1)$. 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 \rightarrow h(x)$ is `continuous'.  It can easily be seen that
%
$$ F_k(a_1,\ldots,a_k)=\bigcup^4_{i=1}H_i~~{\rm where}~~
H_i=\{h_{SQ(a)}(x)~\vert~x\in A_i\}~, $$
%
where the $A_i$'s are subareas of $SQ(a)$, given by the figure below:
\medskip
%
\centerline{\epsffile{doron.eps}}
%
\medskip
%
The reader can verify that
%
$$ H_1=\bigcup^k_{i=1}[a_1-a_i+i,a_1+i-1] $$
%
$$ H_2=\bigcup_{i=2}^{k} \bigcup_{j=2}^{i} 
[\, a_j -a_i+i-j+1 \,\,, \,\,a_{j-1}-a_i+i-j] $$
%
$$ H_3=\bigcup_{i=1}^{k-1} \bigcup_{j=i+1}^{k} 
[\, a_j+i+k-j+1 \,\,, \,\,a_{j-1}+i+k-j] $$
%
and
%
$$ H_4=\bigcup_{i=1}^{k} [i, a_k+i-1]~. $$
%
Thus,
%
$$ F_k(a_1, \dots , a_k)=
\bigcup_{i=1}^{k} [\, a_1 -a_i+i \,\,,\,\, a_1+i-1]
\cup \bigcup_{i=2}^{k} \bigcup_{j=2}^{i} 
[\, a_j -a_i+i-j+1 \,\,, \,\,a_{j-1}-a_i+i-j]
$$
$$
\bigcup_{i=1}^{k} [i, a_k+i-1]
\cup \bigcup_{i=1}^{k-1} \bigcup_{j=i+1}^{k} 
[\, a_j+i+k-j+1 \,\,, \,\,a_{j-1}+i+k-j \,] \quad.
$$
\eject 
Hence
$$
F_k(a_1 , \dots , a_k) - F_k(a_1 -1 , \dots , a_k -1) =
[\, a_1 \,\, , \,\, a_1+k-1 \,] \cup [ \, a_k \,\, ,  \,\, a_k+k-1] 
\cup
$$
$$
\bigcup_{i=1}^{k-1} \bigcup_{j=i+1}^{k} 
\{ a_{j-1}+i+k-j \} -
\bigcup_{i=1}^{k-1} \bigcup_{j=i+1}^{k} 
\{ a_{j}+i+k-j \} \quad .
$$
By changing the `indices of union' $i \leftarrow i+1\,$, 
$\,j \leftarrow j+1\,$,
in the first double union above we have:
$$
F_k(a_1 , \dots , a_k) - F_k(a_1 -1 , \dots , a_k -1) =
[ \, a_1 \, \, , \,\, a_1+k-1] \cup [ \, a_k \,\, , \,\, a_k+k-1] 
\cup
$$
$$
\bigcup_{i=0}^{k-2} \bigcup_{j=i+1}^{k-1} 
\{ a_{j}+i+k-j \} -
\bigcup_{i=1}^{k-1} \bigcup_{j=i+1}^{k} 
\{ a_{j}+i+k-j \} \quad =
$$
$$
[\, a_1 \,\, , \,\, a_1+k-1 \, ] \cup [ \, a_k \,\, , \,\, a_k+k-1] 
\cup
\bigcup_{j=1}^{k-1} 
\{ a_{j}+k-j \} -
\bigcup_{i=1}^{k-1} 
\{ a_{k}+i \} \quad =
$$
$$
[\, a_1 \,\, , \,\, a_1+k-1 \, ] \cup [\, a_k \,\, , \,\, a_k+k-1 \,] 
\cup
\bigcup_{j=1}^{k-1} 
\{ a_{j}+k-j \} -
[\, a_k+1 \,\, , \,\, a_k+k-1 \,]
=
$$
$$
[\, a_1  \,\, , \,\, a_1+k-1 \, ] \cup \{a_k\} 
\cup
\bigcup_{j=1}^{k-1} 
\{ a_{j}+k-j \} 
=
[\, a_1 \,\, , \,\, a_1+k-1 \, ] 
\cup
\{ a_{j}+k-j \,\,\vert\,\, 1 \leq j \leq k \}  \quad. \halmos
$$
 
To conclude we must prove $(F2)$. 
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 \}$.
 
{\bf REFERENCE}
 
[RV] A. Regev and A. Vershik, {\it Asymptotics
of Young diagrams and hook numbers},
Elect. J. Comb. {\bf 4(1)} (1997), R22.
 
 
 
\bye
 
 
 
 
 
 
 



