Stability of Kronecker products of irreducible characters of the symmetric group

Ernesto Vallejo^{1}

Instituto de Matemáticas Universidad Nacional Autónoma de México Area de la Inv. Cient. 04510 México, D.F. e-mail: evallejo@matem.unam.mx

Abstract

F. Murnaghan observed a long time ago that the computation of the decompositon of the Kronecker product χ^{(n−a,λ_{2},...)} ⊗ χ^{(n−b,μ_{2},...)} into irreducibles depends only on \overline{λ} = (λ_{2}, …) and \overline{μ} = (μ_{2}, …), but not on n. In this note we prove a similar result: given three partitions λ, μ, ν of n we obtain a lower bound on n, depending on \overline{λ}, \overline{μ}, \overline{ν}, for the stability of the multiplicity c(λ, μ, ν) of χ^{ν} in χ^{λ} ⊗ χ^{μ}. Our proof if purely combinatorial. It uses a description of the c(λ, μ, ν)’s in terms of signed special rim hook tabloids and Littlewood-Richardson multitableaux.

1 Introduction.

Let χ^{λ} denote the irreducible compex character of the symmetric group S(n) corresponding to the partition λ. For any three partitions λ, μ, ν of n we denote by

c(λ, μ, ν) := ⟨χ^{λ} ⊗ χ^{μ}, χ^{ν}⟩  (1)

the multiplicity of χ^{ν} in the Kroncecker product χ^{λ} ⊗ χ^{μ}.

F. Murnaghan observed in [5] that the computation of the decompositon of the Kronecker product χ^{(n−a,λ_{2},...)} ⊗ χ^{(n−b,μ_{2},...)} into irreducibles depends only on \overline{λ} = (λ_{2}, …) and \overline{μ} = (μ_{2}, …), but not on n. He gave fifty eight formulas for decompositions of Kronecker products corresponding to the simplest choices of \overline{λ} and \overline{μ}. In fact, his formulas are valid for arbitrary n only if one follows some rules to restore and discard disordered partitions appearing in them, see comment on [5, p.762]. In this note we prove a similar result: given three partitions λ, μ, ν of n we obtain a lower bound on n, depending on λ, μ, ν, for the stability of the coefficients c(λ, μ, ν).

More precisely. Let \overline{λ} = (λ_{2}, …, λ_{p}), \overline{μ} = (μ_{2}, …, μ_{q}), \overline{ν} = (ν_{2}, …, ν_{r}) be partitions of positive integers a, b, c respectively. For each n ≥ a + λ_{2} we consider the partition of n, λ(n) := (n − a, λ_{2}, …, λ_{p}). Similarly we define μ(n), and ν(n). Then we have

1Supported by DGAPA, UNAM IN103397

Main Theorem. If \overline{ν} has one part and \overline{λ} = \overline{μ}, let m = max\{λ_{2}+a+c, 2c\}; otherwise let m = max{λ_{2} + a + c − 1, μ_{2} + b + c − 1, 2c}. Then for all n ≥ m

c (λ(n), μ(n), ν(n)) = c (λ(m), μ(m), ν(m)) .

We note that m is not symmetric on λ, μ, ν, but c(λ, μ, ν) is. Therefore we may have three different choices for m and we choose the smallest of the three. For example, consider partitions (1), (2, 1), (2, 1). If we set \overline{λ} = (1), \overline{μ} = (2, 1), \overline{ν} = (2, 1), then a = 1, b = 3, c = 3 and m = max\{4, 7, 6\} = 7. However, if we set \overline{λ} = (2, 1), \overline{μ} = (2, 1), \overline{ν} = (1), then a = 3, b = 3, c = 1 and m = max\{6, 2\} = 6, and we get a sharper lower bound. This is the best possible, since c ((3, 2, 1), (3, 2, 1), (5, 1)) = 2 and c ((2, 2, 1), (2, 2, 1), (4, 1)) = 1.

We also note that the theorem does not always produce the best lower bound. For the partitions (3, 2), (2, 2, 1), (2, 2) the lower bound given by the theorem is 11. However, using SYMMETRICA, we obtained

c((4, 3, 2), (4, 2, 2, 1), (5, 2, 2)) = 12
c((5, 3, 2), (5, 2, 2, 1), (6, 2, 2)) = 16
c((6, 3, 2), (6, 2, 2, 1), (7, 2, 2)) = 16,

which shows that the best lower bound is 10.

The rest of this note is devoted to the proof of the theorem.

2 Notation, definitions and known results

In this section we fix the notation and record some definitions and results that will be used in the proof of the theorem.

Let λ be a partition of n, in symbols λ ⊢ n. We denote by |λ| the sum of its parts, and by λ′ its conjugate. We say that μ is contained in λ, in symbols μ ⊆ λ, if μ_{i} ≤ λ_{i} for all i. We use the notation λ ⊵ μ to indicate that λ is greater or equal than μ in the dominance order. We denote by P(n) the diagram lattice, that is the set of partitions of n together with the dominance order, see [1, 3, 4, 6].

Let H be a subgroup of a group G. If χ is a character of H we denote by Ind_{H}^{G}(χ) the induction character of χ. For any vector π = (π_{1}, …, π_{t}) of non-negative integers such that π_{1} + ⋯ + π_{t} = n, let S(π) denote a Young subgroup of S(n) corresponding to π.

We denote by χ^{λ} the irreducible character of S(n) associated to λ, and by ϕ^{λ} = Ind_{S(λ)}^{S(n)}(1_{λ}) the permutation character associated to λ. They are related by the Young’s rule

ϕ^{μ} = ∑_{λ⊵μ}K_{λμ} χ^{λ},  (2)

where K_{λμ} is a Kostka number, that is, the number of semistandard tableaux of shape λ and content μ, see [3, 2.8.5], [6, §2.11].

We will deal with two kinds of products of characters: Let l, m be non-negative integers, and let n = l + m. Let χ_{1} be a character of S(l), χ_{2} be a character of S(m), then

(i) χ_{1} × χ_{2} denotes the character of S(l) × S(m) given by χ_{1} × χ_{2}(σ, τ) = χ_{1}(σ)χ_{2}(τ).

(ii) χ_{1} ⊗ χ_{2} denotes, if l = m, the Kronecker product of χ_{1} and χ_{2}, that is, the character of S(l) defined by χ_{1} ⊗ χ_{2}(σ) = χ_{1}(σ)χ_{2}(σ).

If T is a tableau (a skew diagram filled with positive integers) there is a word w(T) associated to T given by reading the numbers of T from right to left, in succesive rows, starting with the top row. Let π = (π_{1}, …, π_{t}) be a vector of positive integers such that π_{1} + ⋯ + π_{t} = n. Let ρ(i) ⊢ π_{i}, 1 ≤ i ≤ t. A sequence T = (T_{1}, …, T_{t}) of tableaux is called a Littlewood-Richardson multitableau of shape λ, content (ρ(1), …, ρ(t)) and type π if

(i) There exists a sequence of partitions

0 = λ(0) ⊂ λ(1) ⊂ ⋯ ⊂ λ(t) = λ

such that |λ(i)/λ(i − 1)| = π_{i} for all 1 ≤ i ≤ t, and

(ii) for all 1 ≤ i ≤ t, T_{i} is a semistandard tableau of shape λ(i)/λ(i − 1) and content ρ(i) such that w(T_{i}) is a lattice permutation, see [3, 2.8.13], [4, I.9], [6, §4.9].

For each partition λ of n let c_{(ρ(1),...,ρ(t))}^{λ} denote the number of Littlewood-Richardson multitableaux of shape λ and content (ρ(1), …, ρ(t)). It follows by induction from the Littlewood-Richardson rule that

Ind_{S(π)}^{S(n)} (χ^{ρ(1)} × ⋯ × χ^{ρ(t)}) = ∑_{λ⊢n} c_{(ρ(1),...,ρ(t))}^{λ}χ^{λ}.

Let

lr(λ, μ; π) := ⟨χ^{λ} ⊗ χ^{μ}, ϕ^{π}⟩,  (3)

then it follows from the Frobenius reciprocity theorem that

lr(λ, μ; π) = ∑_{ρ(1)⊢π_{1},...,ρ(t)⊢π_{t}} c_{(ρ(1),...,ρ(t))}^{λ} c_{(ρ(1),...,ρ(t))}^{μ}.

That is, lr(λ, μ; π) is the number of pairs (S, T) of Littlewood-Richardson multitableaux of shape (λ, μ), same content, and type π.

Let K_{n} = (K_{λμ}) be the Kostka matrix with rows and columns arranged in reverse lexicographical order, and let K_{n}^{−1} = (K_{λμ}^{(−1)}) denote its inverse, see [4, I.6.5]. Then it follows from the Young rule (2) that

χ^{ν} = ∑_{π⊵ν} K_{π ν}^{(−1)}ϕ^{π}.  (4)

Therefore from (1), (4) and (3) we obtain

2.1 Proposition

c(λ, μ, ν) = ∑_{π⊵ν}K_{π ν}^{(−1)} lr(λ, μ; π).

□

This formula gives, together with a result of Eg̃eciog̃lu and Remmel [2] (see Theorem 3.2), a combinatorial description of the numbers c(λ, μ, ν). We will use it to get the stability of c(λ, μ, ν) from the stability of K_{π ν}^{(−1)} and lr(λ, μ; π).

3 Proof of the main theorem

Let P(n) denote the diagram lattice, that is, the lattice of partitions of n ordered under the dominance order, see [1, 3, 4, 6]. For each partition ν of n, let I_{ν} denote the interval {π ⊢ n | ν ⊴ π ⊴ (n)} in P(n).

3.1 Lemma. Let n ≥ 2c. Then the intervals I_{ν(n)} and I_{ν(2c)} are isomorphic as posets.

Proof. For π = (π_{1}, …, π_{t}) ∈ I_{ν(n)} we define π̃ := (π_{1} − (n − 2c), π_{2}, …, π_{t}). It follows from the inequality π ⊵ ν(n) that π̃ is in I_{ν(2c)}. One can then easily verify that the map π ↦ π̃ is a poset isomorphism from I_{ν(n)} to I_{ν(2c)}. □

In fact 2c is the best lower bound: Choose \overline{ν} be any partition of c with more than one part. Then ν(2c) and ν(2c − 1) are well defined partitions, but I_{ν(2c)} ≅ I̸_{ν(2c−1)}, because the partition (c, c) ∈ I_{ν(2c)} has no corresponding partition in I_{ν(2c−1)}.

Next we prove a stability property for the numbers K_{λ μ}^{(−1)}. For this we use a combinatorial interpretation of these numbers due to Eg̃eciog̃lu and Remmel [2]. Recall that a special rim hook tabloid T of shape μ and type λ is a filling of the Ferrers’ diagram of μ with rim hooks of sizes {λ_{1}, …, λ_{p}} such that each rim hook is special, that means, each rim hook has at least one box in the first column. The sign of a rim hook H is (−1)^{ht(H)−1}, where ht(H) denotes, as usual, the height of the rim hook. And the sign of T is defined as the product of the signs of the rim hooks of T, see [2, Section 2], [4, Ex. I.6.4] for details. Then

3.2 Theorem. (Eg̃eciog̃lu, Remmel [2])

K_{λ μ}^{(−1)} = ∑_{T} sign(T),

where the sum is over all special rim hook tabloids of type λ and shape μ.

From this we get the following two corollaries

3.3 Corollary. Let \overline{ν} = (ν_{2}, …, ν_{r}) ⊢ c, and n ≥ 2c. Then for all α(n), β(n) in I_{ν(n)} one has

K_{α(n) β(n)}^{(−1)} = K_{α(2c) β(2c)}^{(−1)}.

Proof. A sign preserving bijection between the set of special rim hook tabloids T of type α(2c) and shape β(2c) and the set of special rim hook tabloids T̂ of type α(n) and shape β(n) is established in the following way: Let H be the rim hook in T which contains the last box from the first row. Then H is of maximal length among the rim hooks in T. Let Ĥ be the rim hook obtained from H by adding n − 2c boxes at the end of the first row, and let T̂ be obtained from T by substituting H by Ĥ. Since H is of maximal length, then T̂ is a rim hook tabloid of type α(n). Clearly it has shape β(n) and sign(T) = sign(T̂). □

Another proof follows from [4, Ex. I.6.3].

3.4 Corollary. Let \overline{π} = (π_{2}, …, π_{t}) ⊢ c, and suppose r > 2. Then

K_{π(2c) ν(2c)}^{(−1)} = K_{\overline{π} \overline{ν}}^{(−1)}.
□

Since the sum of the entries of any column of the inverse Kostka matrix (with the obvious exception of the first one) is zero, then it follows

3.5 Corollary. Let m = 2c, and suppose r > 2. Then

∑_{π(m)⊵ν(m), π(m)_{1}=c}K_{π(m) ν(m)}^{(−1)} = 0.

□

Let denote LR(λ(n), μ(n); ν(n)) the set of pairs (S, T) of Littlewood-Richardson multitableaux of shape (λ(n), μ(n)), same content and type ν(n).

3.6 Lemma. Let m = max{λ_{2} + a, μ_{2} + b, ν_{2} + c}. Then for all n ≥ m there is an injective map

Φ : LR(λ(m), μ(m); ν(m)) ⟶ LR(λ(n), μ(n); ν(n)).

Proof. Let (S, T) ∈ LR(λ(m), μ(m); ν(m)). Let Ŝ be obtained from S by adding n − m 1’s at the end of the first row of S_{1}, and shifting n − m places to the right the remaining 1’s belonging to the tableaux S_{2}, … S_{r}. Let T̂ be defined in a similar way. Then (Ŝ, T̂) belongs to LR(λ(n), μ(n); ν(n)), and the map Φ(S, T) := (Ŝ, T̂) is injective.

□

3.7 Proposition. Let m = max\{λ_{2} + a + c − 1, μ_{2} + b + c − 1, ν_{2} + c\} if \overline{λ} ≠ \overline{μ}, and m = max\{λ_{2} + a + c, ν_{2} + c\} if \overline{λ} = \overline{μ}. Then for all n ≥ m

lr(λ(n), μ(n); ν(n)) = lr(λ(m), μ(m); ν(m)).

Proof. We show that under our hypothesis, we can define a map

Ψ : LR(λ(n), μ(n); ν(n)) ⟶ LR(λ(m), μ(m); ν(m))

inverse to Φ. Let (S, T) be in LR(λ(n), μ(n); ν(n)), and let (ρ(1), …, ρ(r)) be the common content of S and T. We define ρ̃(1) := (ρ(1)_{1} − (n − m), ρ(1)_{2}, …, ρ(1)_{u}), where u is the length of ρ(1). Note that ρ(1) ⊆ λ(n) and that |λ(n)/ρ(1)| = c. Then, if \overline{λ} = \overline{μ}, we have that ρ(1)_{1} ≥ λ(n)_{1} − c = n − a − c ≥ n − m + λ_{2}. And, if \overline{λ} ≠ \overline{μ}, we have that ρ(1)_{1} ≥ λ(n)_{1} − (c − 1) = n − a − (c − 1) ≥ n − m + λ_{2}. Therefore, in both cases, ρ(1)_{1} − (n − m) ≥ λ_{2} ≥ ρ(1)_{2}, and ρ̃(1) is a partition of m − c = ν(m)_{1}. Let S̃ be obtained from S by deleting the first (n − m) 1’s in the first row and shifting to the left the remaining numbers n − m places. In this way S̃ is a multitableau of shape λ(m), content (ρ̃(1), ρ(2), …, ρ(r)) and type ν(m). Moreover, since ρ(1)_{1} − (n − m) ≥ λ_{2}, S̃ is a Littlewood-Richardson multitableau. We define in a similar way a Littlewood-Richardson multitableau T̃ of shape μ(m), same content as S̃ and type ν(m). It is straightforward to check that the map (S, T) ↦ (S̃, T̃) yields the inverse of Φ. □

3.8 Corollary. Let m be defined as in Proposition 3.7. Let π(m) = (m−e, π_{2}, …, π_{t}) be in I_{ν(m)}. Then for all n ≥ m

lr (λ(n), μ(n); π(n)) = lr (λ(m), μ(m); π(m)) .
□

The main theorem now follows from Proposition 2.1, Corollaries 3.3 and 3.8, either if \overline{λ} ≠ \overline{μ}, or if \overline{λ} = \overline{μ} and r = 2. It remains to prove it in the case \overline{λ} = \overline{μ} and r > 2.

3.9 Lemma. Let m = max{λ_{2} + a + c − 1, 2c}, π(m) = (m − c, π_{2}, …, π_{t}) be in I_{ν(m)}, and suppose r > 2. Then for all n > m

lr(λ(n), λ(n); π(n)) = lr(λ(m), λ(m); π(m)) + 1.

Proof. Let (S, T) be in LR(λ(n), λ(n); π(n)), and let (ρ(1), …, ρ(t)) be the common content of S and T. Then, as in the proof of Proposition 3.7, we have that ρ(1)_{1} ≥ n − a − c. If ρ(1)_{1} > n − a − c, then ρ(1)_{1} ≥ n − a − (c − 1) ≥ n − m + λ_{2}. Again, as in the proof of Proposition 3.7, there exists (S̃, T̃) ∈ LR(λ(m), λ(m); π(m)), such that Φ(S̃, T̃) = (S, T). If ρ(1)_{1} = n − a − c, then λ(n)/ρ(1) = (c). In this situation, there is exactly one Littlewood-Richardson multitableau R of shape λ(n) and type π(n). It has content (λ(n)/(c), (π_{2}), …, (π_{t})). Therefore the pair (R, R) is the only one in LR(λ(n), λ(n); π(n)) which is not in the image of Φ. The claim follows. □

3.10 Corollary. Let m = max{λ_{2} + a + c − 1, 2c}, and suppose r > 2. Then for all n > m

c(λ(n), λ(n), ν(n)) = c(λ(m), λ(m), ν(m)).

Proof. By Proposition 2.1 it is enough to prove

∑_{π(n)⊵ν(n)}K_{π(n) ν(n)}^{(−1)} lr(λ(n), λ(n); π(n)) = ∑_{π(m)⊵ν(m)}K_{π(m) ν(m)}^{(−1)} lr(λ(m), λ(m); π(m)).

Note that if π(n) = (n − e, π_{2}, …, π_{t}) and e < c, then by Proposition 3.7

lr(λ(n), λ(n); π(n)) = lr(λ(m), λ(m); π(m)),

and if e = c, then by Lemma 3.9

lr(λ(n), λ(n); π(n)) = lr(λ(m), λ(m); π(m)) + 1.

The claim now follows from Corollaries 3.3 and 3.5. □

References

[1] T. Brylawski, The lattice of integer partitions, Discrete Math. 6 (1973), 201-219.

[2] Ö. Eg̃eciog̃lu and J.B. Remmel. A combinatorial interpretation of the inverse Kostka matrix, Linear and Multilinear Algebra 26 (1990), 59-84.

[3] G.D. James and A. Kerber, The representation theory of the symmetric group, Encyclopedia of mathematics and its applications, Vol. 16, Addison-Wesley, Reading, Massachusetts, 1981.

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

[5] F.D. Murnaghan, The analysis of the Kronecker product of irreducible representations of the symmetric group, Amer. J. Math. 60 (1938), 761-784.

[6] B.E. Sagan, The symmetric group, Wadsworth & Brooks/Cole, Pacific Grove, California, 1991.