Asymptotics of Young Diagrams and Hook Numbers

Amitai Regev^{∗} Department of Theoretical Mathematics The Weizmann Institute of Science Rehovot 76100, Israel and Department of Mathematics The Pennsylvania State University University Park, PA 16802, U.S.A.

Anatoly Vershik^{†} St. Petersburg branch of the Mathematics Institute of the Russian Academy of Science Fontanka 27 St. Petersburg, 191011 Russia and The Institute for Advanced Studies of the Hebrew University Givat Ram Jerusalem, Israel

Submitted: August 22, 1997; Accepted: September 21, 1997

Abstract: Asymptotic calculations are applied to study the degrees of certain sequences of characters of symmetric groups. Starting with a given partition μ, we deduce several skew diagrams which are related to μ. To each such skew diagram there corresponds the product of its hook numbers. By asymptotic methods we obtain some unexpected arithmetic properties between these products. The authors do not know ”finite”, nonasymptotic proofs of these results. The problem appeared in the study of the hook formula for various kinds of Young diagrams. The proofs are based on properties of shifted Schur functions, due to Okounkov and Olshanski. The theory of these functions arose from the asymptotic theory of Vershik and Kerov of the representations of the symmetric groups.

∗ Work partially supported by N.S.F. Grant No.DMS-94-01197.

† Partially supported by Grant INTAS 94-3420 and Russian Fund 96-01-00676 §1. Introduction and the main results Asymptotic calculations are applied to study the degrees of certain sequences

of characters of symmetric groups S_{n}, n → ∞. We obtain some unexpected arithmetic properties of the set of the hook numbers for some special families of (fixed) skew-Young diagrams (Theorem 1.2). The problem appeared in the study of the hook formula for various kinds of Young diagrams. The proof of 1.2 is based on the properties of shifted Schur functions [Ok.Ol] which appeared in the asymptotic theory of the representation theory of the symmetric groups in [Ver.Ker]. The authors do not know a “finite” proof of the theorem.

Given a partition μ, we describe in 1.1 - a construction of certain skew diagrams which are derived from μ: these are SQ(μ), SR(μ), SR(μ′), R and D_{μ} below. Next, one fills these skew diagrams with their corresponding hook numbers [Mac, page 10]. Theorem 1.2, which is the main result here, gives some divisibility properties of the products of these hook numbers.

We remark again that even though the statement of theorem 1.2 has nothing to do with asymptotics, its proof does use asymptotic methods. It should be interesting to find an “asymptotic free” proof of theorem 1.2.

We start with

1.1: A Construction: Given a partition (= diagram) μ, let D_{μ}^{∗} denote the double reflection of μ. For example, if μ = (4, 2, 1) then

D_{μ} = \begin{matrix}x & x & x & x \\ x & x \\ x \end{matrix}  and  D_{μ}^{∗} = \begin{aligned}& & & x \\ & & x & x \\ x & x & x & x \end{aligned} .

Recall that μ′_{1} = ℓ(μ) is the number of nonzero parts of μ. Complete D_{μ}^{∗} to the μ_{1} × μ′_{1} rectangle R(μ), then draw D_{μ}^{∗} on top and on the left of R. Finally, erase the first D_{μ}^{∗}. Denote the resulting skew diagram by SQ(μ). For example, with μ = (4, 2, 1) we get

the electronic journal of combinatorics 4 (1997), #R22 3

A_{2}

↘  x
x x
x x x x
SQ(4, 2, 1) =  A_{1}
↘  x x x x
x x x x

↖ x x x x A

We subdivide SQ(μ) into the three areas A, A_{1} and A_{2}: A = R − D_{μ}^{∗}, A_{1} is the D_{μ}^{∗} on the left of R and A_{2} is the D_{μ}^{∗} on top of R. Denote SR(μ) = A_{1} ∪ A, the “shifted rectangle”.

Clearly, |A ∪ A_{1}| = |A ∪ A_{2}| = |R|, |A_{1}| = |A_{2}| = |μ|, so |SQ(μ)| = |R| + |μ|. Now, fill SQ(μ), SR(μ), R and μ with their hook numbers. For example, when μ = (4, 2, 1)

3

4 2
6 5 3 1
SQ(4, 2, 1) :
6 4 3 1
5 4 2 1
4 3 2 1

SR(4, 2, 1) :  6 4 3 1 5 4 2 1 4 3 2 1

R(4, 2, 1) :  6  5  4  3 5  4  3  2 4  3  2  1

and

(4, 2, 1) :  6  4  2  1 3  1 1

Thus, for example, ∏_{x∈(4,2,1)} h(x) = 1^{3} · 2 · 3 · 4 · 6 = 144.

Note that the hook numbers in SR(μ) are the same as those in the area A_{1}∪A of SQ(μ).

As usual, μ′_{1} = ℓ(μ) is the number of nonzero parts of μ. Recall that s_{μ}(x_{1}, x_{2}, ⋯) is the corresponding Schur function, and s_{μ} \underbrace{(1, ⋯, 1)}_{μ′_{1}} is the number

of (semi-standard, i.e. rows weakly and column strictly increasing) tableaux of shape μ, filled with elements from \{1, 2, ⋯, μ′_{1}\} [Mac]. Similarly for s_{μ′} \underbrace{(1, ⋯, 1)}_{μ_{1}}.

1.2 Theorem: Let μ be a partition. With the above construction of SQ(μ) = A ∪ A_{1} ∪ A_{2} and R, we have

(1)  ( ∏_{x∈R} h(x)) / ( ∏_{x∈A_{1}∪A} h(x)) = s_{μ}(\underbrace{1, ⋯, 1}_{μ′_{1}}).

In particular, ∏_{x∈A_{1}∪A} h(x) divides ∏_{x∈R} h(x). [Note that A∪A_{1} ⊂ SQ(μ), and for x ∈ A_{1} ∪ A, h(x) is the corresponding hook number in x ∈ SQ(μ)].

(1’) Similarly,

( ∏_{x∈R} h(x)) / ( ∏_{x∈A_{2}∪A} h(x)) = s_{μ′}(\underbrace{1, ⋯, 1}_{μ_{1}}).

(2)  ∏_{x∈SQ(μ)} h(x) = ( ∏_{x∈R} h(x)) · ( ∏_{x∈μ} h(x)) .

We conjecture that a statement much stronger than 1.2.2 holds, namely: the two multisets {h(x) | x ∈ SQ(μ)} and {h(x) | x ∈ R} ∪ {h(x) | x ∈ μ} are equal.

Theorem 1.2.1 is an obvious consequence of the following “asymptotic” theorem.

1.3. Theorem: Let μ = (μ_{1}, ⋯, μ_{k}), be a partition. Let n = kℓ,

μ_{1} ≤ ℓ → ∞, and denote λ = λ(ℓ) = (ℓ^{k}). Then

(a)  lim_{ℓ→∞} \frac{d_{λ/μ}}{d_{λ}} = (\frac{1}{k} )^{|μ|} · s_{μ}(\underbrace{1, ⋯, 1}_{k})

and

(b)  lim_{ℓ→∞} \frac{d_{λ/μ}}{d_{λ}} = (\frac{1}{k} )^{|μ|} · ( ∏_{x∈R(μ_{1},μ′_{1})} h(x)) / ( ∏_{x∈A_{1}∪A} h(x)) .

Theorem 1.2.1’ follows from 1.2.1 by conjugation.

Theorem 1.2.2 is a consequence of the following “asymptotic” theorem 1.4. Theorem: Let μ be a fixed partition. Let μ_{1} ≤ ℓ → ∞,

μ′_{1} ≤ m → ∞, n = ℓm and λ = λ(ℓ, m) = (ℓ^{m}). Then

(a)  lim_{ℓ,m→∞} \frac{d_{λ/μ}}{d_{λ}} = \frac{1}{∏_{x∈μ} h(x)} .

(b)  lim_{ℓ,m→∞} \frac{d_{λ/μ}}{d_{λ}} = ( ∏_{x∈R} h(x)) / ( ∏_{x∈SQ(μ)} h(x)) .

In this note we apply the following main tools:

a) The theory of symmetric functions [Mac]. In particular, we apply the hook formula

d_{λ} = \frac{|λ|!}{∏_{x∈λ} h(x)}

and I.3, Example 4, page 45 in [Mac].

b) The Okounkov-Olshanski [Ok.Ol] theory of “shifted symmetric functions”. In particular, we apply formula (0.14) of [Ok.Ol]: Let μ ⊢ k, λ ⊢ n, k ≤ n, μ ⊂ λ, then

\frac{d_{λ/μ}}{d_{λ}} = \frac{s_{μ}^{∗}(λ)}{n(n − 1) ⋯ (n − k + 1)} .

Here s_{μ}^{∗}(x) is the “shifted Schur function” [Ok.Ol]; one of its key properties is that s_{μ}^{∗}(x) = s_{μ}(x)+ lower terms, where s_{μ}(x) is the ordinary Schur function.

We remark that the paper [Ok.Ol] was influenced by the work of Vershik and Kerov on the asymptotic theory of the representations of the symmetric groups. See for example [Ver.Ker], in which the characters of the infinite symmetric group are found from limits involving ordinary Schur functions. See also the introduction of [Ok.Ol].

§2. Here we prove theorem 1.3 which, as noted before, implies 1.2.1 (and 1.2.1’).

2.1. The proof of theorem 1.3.

\frac{d_{λ(ℓ)/μ}}{d_{λ(ℓ)}} = \frac{s_{μ}^{∗}(λ_{1}(ℓ), ⋯, λ_{k}(ℓ))}{n(n − 1) ⋯ (n − |μ| + 1)} ,

where n = |λ| = kℓ. Since ℓ → ∞, n(n − 1) ⋯ (n − |μ| + 1) ≃ (kℓ)^{|μ|}. Also,

s_{μ}^{∗}(λ) = s_{μ}(λ) + (lower terms in n),

hence

s_{μ}^{∗}(λ) ≃ s_{μ}(λ) = s_{μ} \underbrace{(ℓ, ⋯, ℓ)}_{k} .

Recall that for two sequences a_{n}, b_{n} of real numbers, a_{n} ≃ b_{n} means that lim_{n→∞} \frac{a_{n}}{b_{n}} = 1.

Since s_{μ}(x) is homogeneous of degree |μ|,

s_{μ}(λ) = ℓ^{|μ|} · s_{μ}(\underbrace{1, ⋯, 1}_{k}) .

The proof now follows easily.

2.2. The proof of theorem 1.3.b: Since λ is a rectangle, hence d_{λ/μ} = d_{η}, where η is the double reflection of λ/μ. Denote by μ̃ = D_{μ}^{∗} the double reflection of μ. Thus

η  ℓ  D_{μ}^{∗}

To calculate d_{λ} and d_{η} by the hook formula, fill λ = λ(ℓ) and η with their respective hook numbers. In both, examine the i^{th} row from the bottom - with their respective hook numbers. Divide η into B_{1} and B_{2} as follows: Notice that B_{1} = SR(μ) of 1.1. Note also that the hook numbers in B_{1} are those in SR(μ), and they are independent of ℓ.

Examine the hook numbers in B_{2}. In the i^{th} row (from bottom), these are μ_{1} + i, μ_{1} + i + 1, ⋯, ℓ + i − 1 − μ_{i}, consecutive integers.

We also divide λ(ℓ) into two rectangles:

B_{1} B_{2}  D_{μ}^{∗} ℓ  \overbrace{μ_{1}} \overbrace{μ_{1}}

\overbrace{μ_{1}} λ(ℓ)  R_{1} ℓ R_{2}

Again, the hook numbers in R_{1} are independent of ℓ, and those in the i^{th} row (from bottom) of R_{2} are μ_{1} + i, μ_{1} + i + 1, ⋯, ℓ + i − 1, again consecutive integers.

By the “hook” formula, the left hand side of 1.3.b is

\frac{d_{λ(ℓ)/μ}}{d_{λ(ℓ)}} = \frac{d_{η}}{d_{λ(ℓ)}} = [\frac{(n − |μ|)!}{∏_{x∈η} h(x)}] / [\frac{n!}{∏_{x∈λ(ℓ)} h(x)}]

= \frac{(n − |μ|)!}{n!} · [\frac{∏_{x∈λ(ℓ)} h(x)}{∏_{x∈η} h(x)}]

where n = kℓ. Since ℓ → ∞,

\frac{(n − |μ|)!}{n!} ≃ (\frac{1}{n})^{|μ|} = (\frac{1}{kℓ})^{|μ|} .

Now

\frac{∏_{x∈λ(ℓ)} h(x)}{∏_{x∈η} h(x)} = [\frac{∏_{x∈R_{1}} h(x)}{∏_{x∈B_{1}} h(x)}] · [\frac{∏_{x∈R_{2}} h(x)}{∏_{x∈B_{2}} h(x)}] = α · β.

Note that the right hand side of 1.3.b is (\frac{1}{k})^{|μ|} · α.

We calculate β:

∏_{x∈R_{2}} h(x) = ∏_{i=1}^{μ′_{1}}[(μ_{1} + i)(μ_{1} + i + 1) ⋯ (ℓ + i − 1)],

∏_{x∈B_{2}} h(x) = ∏_{i=1}^{μ′_{1}}[(μ_{1} + i)(μ_{1} + i + 1) ⋯ (ℓ + i − 1 − μ_{i})],

thus

β = ∏_{i=1}^{μ′_{1}}[(ℓ + i − μ_{i})(ℓ + i − μ_{i} + 1) ⋯ (ℓ + i − 1)] ≃ ℓ^{|μ|},

(since ℓ → ∞).

Hence,

lim_{ℓ→∞} \frac{d_{λ(ℓ)/μ}}{d_{λ(ℓ)}} = (\frac{1}{k} )^{|μ|} · α

and the proof is complete.

§3. Here we prove theorem 1.4 which, as noted before, implies theorem 1.2.2. 3.1. The proof of 1.4.a: Let λ = λ(ℓ, m) = (ℓ^{m}), ℓ, m → ∞. We show

first that s_{μ}^{∗}(λ) ≃ s_{μ}(λ), as follows: By [Ok.Ol.(0.9)],

\begin{aligned}e_{r}^{∗}(λ) & = ∑_{i≤i_{1}<···<i_{r}≤m} (ℓ + r − 1)(ℓ + r − 2) ⋯ ℓ = \\ & = (ℓ + r − 1)(ℓ + r − 2) ⋯ ℓ · \binom{m}{r} ≃ \frac{ℓ^{r}m^{r}}{r!} . \end{aligned}

Similarly, e_{r}(λ) ≃ \frac{ℓ^{r}m^{r}}{r!} .

Let ∅ be given as in [Ok.Ol.§13]. By [Ok.Ol.(13.8)] it easily follows that for any u and r,

∅^{−u}e_{r}^{∗}(λ) ≃ e_{r}^{∗}(λ) ≃ e_{r}(λ).

Applying the Jacobi Trudi formulas for s_{μ}(λ) —(Mac. I, (3.5), page 41] and for s_{μ}^{∗}(λ) [Ok.Ol.(13.10)], it clearly follows that s_{μ}^{∗}(λ) ≃ s_{μ}(λ). Now in 2.1, here

\frac{d_{λ(ℓ,m)/μ}}{d_{λ(ℓ,m)}} = \frac{s_{μ}^{∗}(λ_{1}(ℓ, m), ⋯, λ_{m+k}(ℓ, m))}{n(n − 1) ⋯ (n − |μ| + 1)}

where

n = ℓm.

Here

s_{μ}^{∗}(λ(ℓ, m)) ≃ s_{μ}(λ(ℓ, m)) = ℓ^{|μ|}s_{μ}(\underbrace{1, ⋯, 1}_{m}).

Thus

\frac{d_{λ(ℓ,m)/μ}}{d_{λ(ℓ,m)}} ≃ (\frac{1}{n})^{|μ|} · s_{μ}(\underbrace{1, ⋯, 1}_{m}) = (\frac{1}{m})^{|μ|} · ∏_{x∈μ} \frac{m + c(x)}{h(x)} ,

([Mac, pg. 45, Ex 4]) where c(x) is the content of x ∈ μ. Since m → ∞, m+c(x) ≃ m for all x ∈ μ, and the proof follows.

3.2. The proof of 1.4.b: Choose ℓ, m large so that μ ⊂ λ(ℓ, m). Let η be the double reflection of λ(ℓ, m)/μ, so d_{λ(ℓ,m)/μ} = d_{η}, then calculate d_{η} by the hook formula. To analyze the hook numbers in η, we subdivide η into the areas A_{1,η}, ⋯, A_{4,η} as shown below: i.e., D_{μ}^{∗} is drawn at the bottom-right of the ℓ × m rectangle. We then follow 1.1 and construct A_{4,η} = SQ(μ). Now A_{1,η} is the (ℓ − μ_{1}) × (m − μ′_{1}) rectangle, and this determines A_{2,η} and A_{3,η}.

We also split the ℓ × m rectangle λ = λ(ℓ, m) accordingly:

η : m  ℓ A_{1,η}  A_{3,η} A_{2,η}  A_{4,η} D_{μ}^{∗} \}μ′_{1} \overbrace{μ_{1}}

A_{1,λ(ℓ,m)} A_{2,λ(ℓ,m)}  A_{3,λ(ℓ,m)} A_{4,λ(ℓ,m)} \}μ′_{1} \overbrace{μ_{1}}

Since λ(ℓ, m) ⊢ ℓm and η ⊢ ℓm − |μ|,

\frac{d_{η}}{d_{λ(ℓ,m)}} ≃ (\frac{1}{ℓm})^{|μ|} · \frac{∏_{x∈λ(ℓ,m)} h_{λ(ℓ,m)}(x)}{∏_{x∈η} h_{η}(x)}.

Now, h_{λ(ℓ,m)}(x) = h_{η}(x) for x ∈ A_{1,η} = A_{1,λ(ℓ,m)}. As in 2.3

\frac{∏_{x∈A_{2,λ(ℓ,m)}} h_{λ(ℓ,m)}(x)}{∏_{x∈A_{2,η}} h_{η}(x)} ≃ ℓ^{|μ|}.

Similarly (or, by conjugation),

\frac{∏_{x∈A_{3,λ}} h_{λ(ℓ,m)}(x)}{∏_{x∈A_{3,η}} h_{η}(x)} = m^{|μ|} .

After cancellations we have

\frac{d_{η}}{d_{λ}} ≃ \frac{∏_{x∈A_{4,λ}} h_{λ(ℓ,m)}(x)}{∏_{x∈A_{4,η}} h_{η}(x)} = \frac{∏_{x∈R(μ_{1},μ′_{1})} h(x)}{∏_{x∈SQ(μ)} h(x)}

and the proof is complete.

References

[Ok.Ol] Okounkov A. and Olshanski G., Shifted Schur functions, preprint.

[Mac] Macdonald I.G., Symmetric functions and Hall polynomials, Oxford University Press, 2nd edition 1995.

[Ver.Ker] Vershik A.M. and Kerov, S.V., Asymptotic Theory of characters of the symmetric group, Funct. Anal. Appl. 15 (1981) 246-255.

email addresses: regev@wisdom.weizmann.ac.il, vershik@pdmi.ras.ru