Identities in character tables of S_{n}

Alon Regev, Amitai Rege and Doron Zeilberger

July 28, 2014

1 New section added by DZ (INCOMPLETE!)

It should be possible (hopefully) to prove the following theorem.

Theorem 1.1. Let μ be any partition, and let |μ| be the sum of its parts. Then, for n ≥ |μ|, we have

∑_{λ⊢n}(χ^{λ}(μ, 1^{n−|μ|}))^{2} = C(μ)(n − |μ|)! ,

where

C(μ) := ∑_{λ⊢|μ|}(χ^{λ}(μ))^{2} ,

Sketch of Proof Recall that f_{λ}, the number of Standard Young Tableaux of shape λ, alias

χ^{λ}(1^{n}), satisfies two famous recurrences

f_{λ} = ∑_{λ^{−}} f_{λ^{−}} ,  (GoingDown)

where the sum is over all partitions λ^{−} obtained by removing one cell from λ (legally). This recurrence is trivial combinatorially, but it should not be too hard to prove it directly, either from representation theory, or via the fact at the very last line of p. 114 of Macdonald’s Second Ed., that χ^{λ}(ρ) is the coefficient of x^{λ+δ} in a_{δ}p_{ρ}. It also follows (combinatorially from Robinson-Schenstead, but it is not too hard to prove it directly, once again from the above fact), that, if n = |λ|, then

(n + 1)f_{λ} = ∑_{λ^{+}} f_{λ_{+}} ,  (GoingUp)

where the sum is over all partitions λ^{+} obtained by adding one cell to λ (legally). Let

A_{n} := ∑_{λ⊢n} f_{λ}^{2}

Recall that one way to prove that A_{n} = n! (w/o using R-S) is to note that, because of the Going Down Formula

A_{n} = ∑_{λ⊢n} f_{λ}^{2} = ∑_{λ⊢n,μ⊢n−1} f_{λ}f_{μ}

where the sum is over all pairs λ, μ such that λ − μ is one legal cell. But this is the same, thanks to the Going Up formula, to nA_{n−1}. Indeed:

nA_{n−1} = ∑_{μ⊢n−1} nf_{μ}^{2} = ∑_{μ⊢n−1}(nf_{μ})f_{μ} ∑_{λ⊢n,μ⊢n−1} f_{λ}f_{μ} ,

with the same summation set. To prove the theorem we note that the Going Down formula seems to hold for all μ ending in 1

χ^{λ}(μ) = ∑_{λ^{−}} χ^{λ^{−}}(μ′) ,  (GoingDownGeneral)

where μ′ is μ with the last part (that must be a 1, by assumption) removed. An analog of the Going Up formula seems to hold (see the Maple package SnCharacterTableMiracles) for any μ, we have

(N_{1}(μ) + 1) χ^{λ}(μ) = ∑_{λ^{+}} χ^{λ^{+}}(μ_{1}) ,  (GoingUpGeneral)

where N_{1}(μ) is the number of ones in μ, and μ_{1} is the partition obtained from μ by appending a 1. The proof of the theorem now follows the same way.

References

[1] R.L. Graham,D.E. Knuth and O. Patashnik, Concrete Mathematics.

[2] D.E. Knuth, The Art of Computer Programing, Vol. 3, Addison Wesley, Reading Mass. 1968.

[3] I.G. Macdonald, Symmetric Functions

[4] The Online Encyclopedia of Integer Sequences.

[5] R. Stanley, EC II