IDENTITIES In CHARACTER TABLES Of S_{n}

Alon REGEV, Amitai REGEV, and Doron ZEILBERGER

Abstract: We use the algebra of difference operators to study sums of squares (and other powers) of the characters of the symmetric group, χ^{λ}(μ), when the sum is restricted over shapes, λ, with a fixed number of rows, and for hook shapes, and μ has ‘mostly’ ones. We prove that such sums are always P-recursive, i.e., satisfy a linear difference equation with polynomial coefficients. For the special case of two rows, and for hook-shapes, we prove that these sums are in fact closed-form, and we present algorithms, complete with rigorous proofs, for finding these expressions.This article is accompanied

by a Maple package, Sn (available from http://www.math.rutgers.edu/~zeilberg/tokhniot/Sn),
and a webpage, http://www.math.rutgers.edu/~zeilberg/mamarim/mamarimhtml/sn.html, with

links to extensive output, containing rigorously-proved explicit formulas for many cases.

Introduction

The notion of group character, introduced by Frobenius, is a fundamental one in representation theory, and among all groups, the symmetric group, S_{n}, is the most fundamental one. The entries of the character tables of the symmetric group may be defined in numerous ways, but for our purposes, we will use the following definition, that does not require any knowledge of ‘advanced’ algebra, high-school algebra suffices!

Recall that the Constant Term of a Laurent polynomial in (x_{1}, …, x_{m}) is the free term, i.e. the coefficient of x_{1}^{0} ⋯ x_{m}^{0}. For example

CT_{x_{1},x_{2}}(x_{1}^{−3}x_{2} + x_{1}x_{2}^{−2} + 5) = 5 .

Recall that a partition (alias shape) of an integer n, with m parts (alias rows), is a non-increasing sequence of positive integers

λ = (λ_{1}, …, λ_{m}) ,

where λ_{1} ≥ λ_{2} ≥ … ≥ λ_{m} > 0, and λ_{1} + … + λ_{m} = n.

If λ = (λ_{1}, …, λ_{m}) and μ = (μ_{1}, …, μ_{r}) are partitions of n with m and r parts, respectively, then it easily follows from (7.8) (p. 114) in [M], that the characters, χ^{λ}(μ), of the symmetric group, S_{n}, may be obtained by the constant term expression

χ^{λ}(μ) = CT_{x_{1},...,x_{m}} \frac{∏_{1≤i<j≤m}(1 − \frac{x_{j}}{x_{i}}) ∏_{j=1}^{r} (∑_{i=1}^{m} x_{i}^{μ_{j}})}{∏_{i=1}^{m} x_{i}^{λ_{i}}} .  (Chi)

It is well-known (e.g. [M], p. 119, bottom line) that, writing μ in frequency notation, μ = 1^{a_{1}}2^{a_{2}} … n^{a_{n}}, we have the following beautiful identity:

∑_{λ⊢n} χ^{λ}(μ)^{2} = ∏_{i=1}^{n} i^{a_{i}}a_{i}! .

The most famous special case is when μ = 1^{n}, that becomes (since χ^{λ}(1^{n}) = f_{λ}, the number of Standard Young Tableaux of shape λ), the identity:

∑_{λ⊢n} f_{λ}^{2} = n! ,

that has a lovely combinatorial proof using the celebrated Robinson-Schensted correspondence ([Ro][Sc]). A bijective proof of the former, more general, identity was given by Dennis White ([Wh]).

If one restricts the latter sum to go over partitions with at most a fixed number of parts, then one gets many sequences of combinatorial interest. Most notably, for a fixed r ≥ 1,

a^{(r)}(n) := ∑_{{λ⊢n \atop length(λ)≤r}} f_{λ}^{2} ,

is the number of permutations of length n that do not contain an increasing subsequence of length r + 1. The sequences a^{(r)}(n) are (as of July 8, 2015) in [Sl] for r ≤ 11. Note that a^{(2)}(n) is the super-famous sequence A000108, of Catalan numbers, C_{n} := \frac{1}{n+1} \binom{2n}{n}.

In [Z1] it was proved that, for any fixed r, the sequence a^{(r)}(n) is P -recursive (alias holonomic), i.e. satisfies a linear difference equation (alias linear recurrence equation) with polynomial coefficients. We should also mention that Ira Gessel ([Ge]) famously discovered a lovely determinant formula for the generating functions in terms of Bessel functions.

The analogous sequences, for the straight sums (without the squares),

b^{(r)}(n) := ∑_{{λ⊢n \atop length(λ)≤r}} f_{λ} ,

are also of combinatorial interest, counting the number of involutions of length n avoiding an increasing subsequence of length r + 1. It is well known, and easy to prove, that b^{(2)}(n) = \binom{n}{⌊n/2⌋}, that is sequence A001405 in [Sl]. Much deeper is the result, first proved in [Re], that b^{(3)}(n) are the Motzkin numbers, A001006 (see [Z2] for another proof and for a generalization). The sequence b^{(4)}(n), A005817, is even nicer, given in terms of Catalan numbers, b^{(4)}(n) = C_{⌊n/2+1/2⌋}C_{⌊n/2+1⌋}, as first proved by Dominique Gouyou-Beauchamps ([Go]). b^{(5)}(n) is A049401, while b^{(6)}(n) is A007579. See also [BFK].

Recall ([Z1]) that a discrete function a(n) of a single variable is called holonomic (or P -recursive) if it satisfies a homogeneous linear recurrence (alias difference) equation with polynomial coefficients, i.e. there exists an integer L and polynomials p_{0}(n), …, p_{L}(n), such that

∑_{i=0}^{L} p_{i}(n)a(n + i) = 0 , (n ≥ 0) .

A discrete function of several variables a(n_{1}, …, n_{m}) is holonomic if it satisfies such a recurrence in each of its variables, n_{1}, …, n_{m} and the coefficients are polynomials in all of them, and the system is non-degenerate. It was proved in [Z1] that if you sum such a holonomic discrete function over some of its arguments, you get yet-another holonomic function in the surviving variables.

As mentioned in [Z1], the reason that a^{(r)}(n) and b^{(r)}(n) (and more generally, sums of powers f_{λ}^{s}, where s is any positive integer), for any specific, r, are P -recursive in n is that the summand, f_{λ} = f(λ_{1}, …, λ_{r}), and hence any of its powers, is holonomic in its arguments, and hence the (r −1)-fold multisum is guaranteed to be holonomic in the ‘surviving’ discrete variable n. Furthermore, thanks to the hook-length formula ([Wi]), or equivalently the Young-Frobenius formula, the summand f(λ_{1}, …, λ_{r}) can be expressed as

f(λ_{1}, …, λ_{r}) = \frac{∏_{1≤i<j≤r}(λ_{j} − λ_{i} + j − i)(∑_{i=1}^{r} λ_{i})!}{∏_{i=1}^{r}(λ_{i} + r − i)!} .

In addition, thanks to [AZ], there are effective algorithms for finding these recurrences, implemented in the Maple package

http://www.math.rutgers.edu/~zeilberg/tokhniot/MultiZeilberger .

However, it is much more efficient to derive these recurrences by generating sufficiently many terms, and then guessing the linear recurrence, that we know for sure exists, by undetermined coefficients. These recurrences can be proved fully rigorously, if desired, but since they are definitely true, we do not bother to waste time on this.

More generally, one can consider such sums where the shape λ belongs to a “meta-hook” with k rows and l columns, in other words, the analogous sums (see [BR] and [EZ]) where one sums f_{λ} (or its square, or any positive integer power), over all shapes, that do not contain the celll (k +1, l+1). Such a shape is determined by k + l parameters, the lengths of the k largest rows and the lengths of the l largest columns, and, once again, using the Hook Length Formula, one can express f_{λ} as a closed-form expression in these k + l discrete parameters, and the above observations about the resulting sequences, for each fixed (k, l), being holonomic, still apply.

Character Sums for μ ‘Close’ to 1^{n}

For any partition λ, let |λ| be its sum, in other words, the integer that is being partitioned.

As we noted above, f_{λ} equals χ^{λ}(1^{n}). The first purpose of the present paper is merely to observe, that an analogous argument still applies if one replaces μ = 1^{n} by μ = μ_{0}1^{n−|μ_{0}|}, for any fixed partition μ_{0} (with smallest part at least 2), the analogous sums with f_{λ} replaced by χ^{λ}(μ_{0}1^{n−|μ_{0}|}) are also guaranteed to be holonomic. This follows from Eq. (Chi), that spells out to be, writing μ_{0} = (a_{1}, …, a_{k}) (a_{k} ≥ 2).

χ^{λ}(μ_{0}1^{n−|μ_{0}|}) = CT_{x_{1},...,x_{m}} \frac{∏_{1≤i<j≤m}(1 − \frac{x_{j}}{x_{i}}) ∏_{j=1}^{k} (∑_{i=1}^{m} x_{i}^{a_{j}}) · (∑_{i=1}^{m} x_{i})^{n−a_{1}−...−a_{k}}}{∏_{i=1}^{m} x_{i}^{λ_{i}}} .

(Chi0)

Expanding

∏_{1≤i<j≤m}(1 − \frac{x_{j}}{x_{i}}) ∏_{j=1}^{k} (∑_{i=1}^{m} x_{i}^{a_{j}}) ,

we get, for fixed m, k, and μ_{0} = (a_{1}, …, a_{k}), a finite sum of monomials, and collecting the contributions of each, we get a finite linear combination of shifts of the multinomial coefficient (λ_{1} + … + λ_{m})!/(λ_{1}! ⋯ λ_{m}!), and it is easy to see that the result is a rational function times the latter (with ‘nice’ denominator), and hence closed-form.

The analogous argument for sums over shapes contained in a meta-hook H(k, l) is slightly more complicated, and is omitted.

The second purpose of the present paper is to observe that, for the special cases of shapes with at most 2 rows, defining

ψ^{(2)}(μ) := ∑_{j=0}^{⌊n/2⌋} χ^{(n−j,j)}(μ)^{2} ,

for any fixed partition μ_{0} (with smallest part ≥ 2), there is a closed-form expression for ψ^{(2)}(μ_{0}1^{n−|μ_{0}|}), of the form

ψ^{(2)}(μ_{0}1^{n−|μ_{0}|}) = R_{μ_{0}}(n)\binom{2n}{n} ,

for some rational function R_{μ_{0}}(n). The reason is that in the two-rowed case, χ^{(n−j,j)}(μ_{0}1^{n−μ0}) can be expressed (thanks to Eq. (Chi)) as a linear combination of shifts of the binomial coefficients \binom{n}{j}, and squaring it and expanding, gives (possibly many, but still finitely-many) expressions of the form

∑_{j=0}^{⌊n/2⌋} \binom{n − α}{j − β}\binom{n − α′}{j − β′} , (α + α′ = |μ_{0}|) ,

each of which (after symmetrizing in order to make the summations range over all −∞ < j < ∞ [with the usual convention that \binom{a}{b} is 0 if a < b and if b < 0]) is summable by the Vandermonde-Chu convolution

∑_{j} \binom{n − α}{j − β}\binom{n − α′}{j − β′} = \binom{2n − α − α′}{n + β′ − α′ − β},

each of which is a multiple of \binom{2n}{n} by a certain rational function, and adding these finitely (but possibly numerous) terms, still adds up to a certain rational function times \binom{2n}{n}.

Analogously, for shapes inside the (1, 1)-meta hook

ϕ^{(2)}(μ) := ∑_{j=1}^{n} χ^{(j,1^{n−j})}(μ)^{2} ,

since χ^{(j,1^{n−j})}(1^{n}) = \binom{n−1}{j−1} (as follows easily from (Chi) specialized to this case), χ^{(j,1^{n−j})}(μ_{0}1^{n−|μ_{0}|}) can be expressed as a finite linear combinations of \binom{n−1−α}{j−1−β}, once again we get a finite linear combination of Vandermonde-Chu convolutions, each of them being a multiple of \binom{2n−2}{n−1} by a certain rational function (equivalently, we can use \binom{2n}{n}, as above, but it is more natural to use the former as the “base”, since it is the answer for μ = 1^{n}, i.e. where μ_{0} is the empty partition). In fact, in this case we can get nice explicit expressions for the generation functions (recall that μ_{0} = (a_{1}, …, a_{r}))

F_{n;(a_{1},...,a_{r})}(x) := ∑_{j=1}^{n} χ^{(j,1^{n−j})}(μ_{0}1^{n−|μ_{0}|}) x^{j} = x(1 + x)^{n−1−|μ_{0}|} ∏_{i=1}^{r}(x^{a_{i}} − (−1)^{a_{i}}) .

Hence

ϕ^{(2)}(μ_{0}1^{n−|μ_{0}|}) = ∑_{j=1}^{n} χ^{(j,1^{n−j})}(μ_{0}1^{n−|μ_{0}|})^{2}

is the constant term of

F_{n;(a_{1},...,a_{r})}(x) · F_{n;(a_{1},...,a_{r})}(x^{−1}) =

x(1 + x)^{n−1−a_{1}−...−a_{r}} ( ∏_{i=1}^{r}(x^{a_{i}} − (−1)^{a_{i}}) ) · x^{−1}(1 + x^{−1})^{n−1−a_{1}−...−a_{r}} ( ∏_{i=1}^{r}(x^{−a_{i}} − (−1)^{a_{i}}) ) .

= \frac{(1 + x)^{2n−2−2|μ_{0}|}}{x^{n−1−|μ_{0}|}} · Q(x) ,

where Q(x) is the symmetric Laurent polynomial

Q(x) = ∏_{i=1}^{r}(x^{a_{i}} − (−1)^{a_{i}})(x^{−a_{i}} − (−1)^{a_{i}}) .

Expanding Q(x) as a sum of monomials and extracting the respective coefficients, we get a linear combination of terms of the form \binom{2(n−1−|μ_{0}|)}{n−1−|μ_{0}|−j}, that obviously simplifies to a rational function times \binom{2n−2}{n−1}. [This is implemented in procedure Phi2 in the Maple package Sn]. Implementation Everything discussed here is implemented in the Maple package Sn, available from the front of the present paper

http://www.math.rutgers.edu/~zeilberg/mamarim/mamarimhtml/sn.html ,

where one can find several sample input and output files, that readers are welcome to extend. Some Output I. Explicit Expressions for ϕ_{n}^{(2)}(μ_{0}1^{n−|μ_{0}|}) The classical case is well-known, and easy.

ϕ_{n}^{(2)}(1^{n}) = \binom{2n − 2}{n − 1} .

We also have

ϕ_{n}^{(2)}(21^{n−2}) = \frac{1}{2n − 3}\binom{2n − 2}{n − 1} (= 2C_{n−2}) ,

ϕ_{n}^{(2)}(221^{n−4}) = \frac{3}{(2 n − 3) (2 n − 5)}\binom{2n − 2}{n − 1} .

More generally, for r ≥ 0, we have:

ϕ_{n}^{(2)}(2^{r}1^{n−2r}) = \frac{(2r)!(2n − 2r − 2)!}{r!(n − 1)!(n − r − 1)!} .

Also

ϕ_{n}^{(2)}(31^{n−3}) = \frac{n^{2} − 7 n + 18}{4 (2 n − 3) (2 n − 5)}\binom{2n − 2}{n − 1} ,

ϕ_{n}^{(2)}(41^{n−4}) = \frac{n^{2} − 9 n + 23}{(2 n − 3) (2 n − 5) (2 n − 7)}\binom{2n − 2}{n − 1} ,

ϕ_{n}^{(2)}(51^{n−5}) = \frac{n^{4} − 22 n^{3} + 239 n^{2} − 1298n + 2760}{16 (2 n − 3) (2 n − 5) (2 n − 7) (2 n − 9)}\binom{2n − 2}{n − 1} ,

ϕ_{n}^{(2)}(321^{n−5}) = \frac{n^{2} − 15 n + 74}{4 (2 n − 3) (2 n − 5) (2 n − 7)}\binom{2n − 2}{n − 1} .

For all the (proved!) explicit expressions for ϕ_{n}^{(2)}(μ_{0}1^{n−|μ_{0}|}), with |μ_{0}| ≤ 14 (and, of course, the smallest part of μ_{0} larger than one) (135 cases altogether), see the output file:

http://www.math.rutgers.edu/~zeilberg/tokhniot/oSn1 .

II. Explicit Expressions for ψ_{n}^{(2)}(μ_{0}1^{n−|μ_{0}|}) The classical case is well-known, and easy.

ψ_{n}^{(2)}(1^{n}) = \frac{1}{n + 1}\binom{2n}{n} (= C_{n}) .

We have:

ψ_{n}^{(2)}(21^{n−2}) = \frac{9 − 5 n + n^{2}}{(2 n − 1) (2 n − 3) (n + 1)}\binom{2n}{n} ,

ψ_{n}^{(2)}(31^{n−3}) = \frac{48 − 11 n + n^{2}}{4 (2 n − 1) (2 n − 3) (n + 1)}\binom{2n}{n} ,

Note the remarkable (proved!) identity:

ψ_{n}^{(2)}(31^{n−3}) = \frac{1}{2}ϕ_{n+2}^{(2)}(321^{n−3}) .

It may be interesting to find a ‘natural’ reason for this ‘coincidence’.

We also have:

ψ_{n}^{(2)}(41^{n−4}) = \frac{2100 − 1354 n + 299 n^{2} − 26 n^{3} + n^{4}}{4 (2 n − 1) (2 n − 3) (2 n − 5) (2 n − 7) (n + 1)}\binom{2n}{n} ,

ψ_{n}^{(2)}(221^{n−4}) = \frac{525 − 316 n + 89 n^{2} − 14 n^{3} + n^{4}}{(2 n − 1) (2 n − 3) (2 n − 5) (2 n − 7) (n + 1)}\binom{2n}{n} ,

ψ_{n}^{(2)}(51^{n−5}) = \frac{10080 − 4342 n + 659 n^{2} − 38 n^{3} + n^{4}}{16 (2 n − 1) (2 n − 3) (2 n − 5) (2 n − 7) (n + 1)}\binom{2n}{n} ,

ψ_{n}^{(2)}(321^{n−5}) = \frac{2520 − 1045 n + 194 n^{2} − 20 n^{3} + n^{4}}{4 (2 n − 1) (2 n − 3) (2 n − 5) (2 n − 7) (n + 1)}\binom{2n}{n} .

For all the (proved!) explicit expressions for ψ_{n}^{(2)}(μ_{0}1^{n−|μ_{0}|}), with |μ_{0}| ≤ 14 (and, of course, the smallest part of μ_{0} larger than one) (135 cases altogether), see the output file:

http://www.math.rutgers.edu/~zeilberg/tokhniot/oSn2 .

Sums over shapes with more rows For three and more rows, the sums are no longer closed-form, but, as we mentioned above, they always satisfy a linear recurrence (alias difference) equation with polynomial coefficients, see the output files linked to in the above-mentioned webpage of this article. Conclusion On page 155 of [GPK] it says: “The numbers in Pascal’s triangle satisfy, practically speaking, infinitely many identities, so it is not too surprising that we can find some surprising relationships by looking closely.” The aim of this note was to indicate that a similar statement seems to hold for the character tables of the symmetric groups Sn. Just as importantly, it was a case-study in using a computer algebra system to prove deep identities, way beyond the ability of mere humans.

Acknowledgment We thank Richard Stanley, Dennis Stanton, and John Stembridge for useful information. Special thanks go to Shalosh B. Ekhad, for its extensive, very reliable, computations. References

[AZ] M. Apagodu and D. Zeilberger, Multi-Variable Zeilberger and Almkvist-Zeilberger algorithms and the sharpening of Wilf-Zeilberger theory, Adv. Appl. Math. 37 (2006),(Special issue in honor of A. Regev), 139-152;

http://www.math.rutgers.edu/~zeilberg/mamarim/mamarimhtml/multiZ.html .

[BR] A. Berele and A. Regev, Asymptotics of Young tableaux in the (k, l) hook, in: “Groups, Algebras, and Applications” (C.P. Milies, ed.), Contemporary Mathematics 537 (2011), 71-84. See

also: http://arxiv.org/abs/1007.3833 .

[BFK] F. Bergeron, L. Favreau and D. Krob, Conjectures on the enumeration of tableaux of bounded height, Discrete Math 139 (1995), 463-468.

[EZ] S. B. Ekhad and A. Regev, Refined asymptotics and explicit recurrences for the numbers of Young tableaux in the (k, l) hook for k + l ≤ 5 , Personal Journal of Shalosh B. Ekhad and Doron Zeilberger; July 28, 2010;

http://www.math.rutgers.edu/~zeilberg/mamarim/mamarimhtml/hooker.html .

[Ge] I. Gessel, Symmetric functions and P-recursiveness, Journal of Combinatorial Theory Series A

53 (1990), 257-285; http://people.brandeis.edu/~gessel/homepage/papers/dfin.pdf .

[Go] D. Gouyou-Beauchamps, Chemins sous-diagonaux et tableaux de Young, in: “Combinatoire énumérative (Montréal 1985, G. Labelle and P. Leroux, eds.)”, Lect. Notes Math. 1234, 112-125, Springer, 1986.

[GKP] R.L. Graham, D.E. Knuth and O. Patashnik, “Concrete Mathematics”, 1st. ed., Addison-Wesley, 1989.

[M] I. G. Macdonald, “Symmetric Functions and Hall Polynomials”, 2nd ed., Clarendon Press, Oxford, 1995.

[Re] A. Regev, Asymptotic values for degrees associated with strips of Young diagrams, Advances in Mathematics 41 (1981), 115-136.

[Ro] G. de B. Robinson, On the representations of S_{n}, Amer. J. Math. 60 (1938), 745-760.

[Sc] C. E. Schensted, Largest increasing and decreasing subsequences, Canad. J. Math 13 (1961), 179-191.

[Sl] N.J.A. Sloane, The On-Line Encyclopedia of Integer Sequences; http://oeis.org .

[Wh] D. White, A bijection proving orthogonality of the characters of Sn, Adv. in Math. 50 (1983), 160 - 186.

[Wi] The Wikipedia Foundation, Hook Length Formula;

http://en.wikipedia.org/wiki/Hook length formula .

[Z1] D. Zeilberger, A holonomic systems approach to special functions identities, J. Comput. Appl. Math. 32 (1990), 321 - 368;

http://www.math.rutgers.edu/~zeilberg/mamarim/mamarimPDF/holonomic.pdf .

[Z2] D. Zeilberger, The number of ways of walking in x_{1} ≥ … ≥ x_{k} ≥ 0 for n days, starting and ending at the origin, where at each day you may either stay in place or move one unit in any direction, equals the number of n-cell standard Young tableaux with ≤ 2k +1 rows, Personal Journal of Shalosh B. Ekhad and Doron Zeilberger, Dec. 6, 2007;

http://www.math.rutgers.edu/~zeilberg/mamarim/mamarimhtml/lazy.html .

Alon Regev, 1108 Post Dr., Rockford, IL 61108, USA; regevalon at yahoo dot com .

Amitai Regev, Department of Pure Mathematics, Weizmann Institute of Science, Rehovot 76100, Israel ; amitai dot regev at weizmann dot ac dot il .

Doron Zeilberger, Department of Mathematics, Rutgers University (New Brunswick), Hill Center-Busch Campus, 110 Frelinghuysen Rd., Piscataway, NJ 08854-8019, USA. zeilberg at math dot rutgers dot edu .

July 13, 2015.