Surprising Relations Between Sums-Of-Squares of Characters of the Symmetric Group Over Two-Rowed Shapes and Over Hook Shapes

By Amitai REGEV and Doron ZEILBERGER

Abstract: In a recent article, we noted (and proved) that the sum of the squares of the characters of the symmetric group, χ^{λ}(μ), over all shapes λ with two rows and n cells and μ = 31^{n−3}, equals, surprisingly, to 1/2 of that sum-of-squares taken over all hook shapes with n + 2 cells and with μ = 321^{n−3}. In the present note, we show that this is only the tip of a huge iceberg! We will prove that if μ consists of odd parts and (a possibly empty) string of consecutive powers of 2, namely 2, 4, …, 2^{t−1} for t ≥ 1, then the the sum of χ^{λ}(μ)^{2} over all two-rowed shapes λ with n cells, equals exactly \frac{1}{2} times the analogous sum of χ^{λ}(μ′)^{2} over all shapes λ of hook shape with n + 2 cells, and where μ′ is the partition obtained from μ by retaining all odd parts, but replacing the string 2, 4, …, 2^{t−1} by 2^{t}.

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 via 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)

As usual, for any partition μ, |μ| denotes the sum of its parts, in other words, the integer that is being partitioned.

In [RRZ] we considered two quantities. Let μ_{0} be any partition with smallest part ≥ 2. The first quantity, that we will call henceforth A(μ_{0})(n), is the following sum-of-squares over two-rowed shapes λ:

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

[Note that in [RRZ] this quantity was denoted by ψ^{(2)}(μ_{0}1^{n−|μ_{0}|}). ] The second quantity was the sum-of-squares over hook-shapes

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

[Note that in [RRZ] this quantity was denoted by ϕ^{(2)}(μ_{0}1^{n−|μ_{0}|}).]

In [RRZ] we developed algorithms for discovering (and then proving) closed-form expressions for these quantities, for any given (specific) finite partition μ_{0} with smallest part larger than one. In fact we proved that each such expression is always a multiple of \binom{2n}{n} by a certain rational function of n that depends on μ_{0}.

Unless μ_{0} is very small, these rational functions turn out to be very complicated, but, inspired by the OEIS([S]), Alon Regev noted (and then it was proved in [RRZ]) the remarkable identity

A(3)(n) = \frac{1}{2}B(3, 2)(n + 2) .

This lead to the following natural question:

Are there other partitions, μ_{0}, such that there exists a partition, μ′_{0} with |μ′_{0}| = |μ_{0}| + 2, such that the ratio A(μ_{0})(n)/B(μ′_{0})(n + 2) is a constant?

This lead us to write a new procedure in the Maple package

http://www.math.rutgers.edu/~zeilberg/tokhniot/Sn.txt , that accompanies [RRZ],

called SeferNisim(K,N0), that searched for such pairs [μ_{0}, μ′_{0}]. We then used our human ability for pattern recognition to notice that all the successful pairs (we went up to |μ_{0}| ≤ 20) turned out to be such that μ_{0} either consisted of only odd parts, and then μ′_{0} was μ_{0} with 2 appended, or, more generally μ_{0} consisted of odd parts together with a string of consecutive powers of 2 (starting with 2), and μ′_{0} was obtained from μ_{0} by retaining all the odd parts but replacing the string of powers of 2 by a single power of 2, one higher then the highest in μ_{0}. In symbols, we conjectured, (and later proved [see below], alas, by purely human means) the following:

Theorem: Let μ_{0} be any partition of the form

μ_{0} = Sort([a_{1}, …, a_{s}, 2, 2^{2}, …, 2^{t−1}]) ,

where

a_{1} ≥ a_{2} ≥ … ≥ a_{s} ≥ 3 ,

are all odd, and t ≥ 1 (if t = 1 then μ_{0} only consists of odd parts). Define

μ′_{0} = Sort([a_{1}, …, a_{s}, 2^{t}]) .

Then, for every n ≥ |μ_{0}|, we have

A(μ_{0})(n) = \frac{1}{2}B(μ′_{0})(n + 2) .

(For any sequence of integers, S, Sort(S) denotes that sequence sorted in non-increasing order.)

In order to prove our theorem we need to first recall, from [RRZ], the following constant-term expression for B(μ_{0})(n).

Lemma 1: Let μ_{0} = (a_{1}, …, a_{r})

B(μ_{0})(n) = Coeff_{x^{0}} [\frac{(1 + x)^{2n−2−2(a_{1}+...+a_{r})}}{x^{n−1}} · ∏_{i=1}^{r}(x^{a_{i}} − (−1)^{a_{i}})(1 − (−1)^{a_{i}}x^{a_{i}})] .

We need an analogous constant-term expression for A(μ_{0})(n). To that end, let’s first spell-out Equation (Chi) for the two-rowed case, m = 2, so that we can write λ = (n − j, j). We have, writing μ_{0} = (a_{1}, …, a_{r}),

χ^{(n−j,j)}(μ_{0}1^{n−|μ_{0}|}) = CT_{x_{1},x_{2}} \frac{(1 − \frac{x_{2}}{x_{1}} )(x_{1} + x_{2})^{n−a_{1}−...−a_{r}} ∏_{i=1}^{r} (x_{1}^{a_{i}} + x_{2}^{a_{i}})}{x_{1}^{n−j}x_{2}^{j}} .  (Chi2)

This can be rewritten as

χ^{(n−j,j)}(μ_{0}1^{n−|μ_{0}|}) = CT_{x_{1},x_{2}} \frac{(1 − \frac{x_{2}}{x_{1}} )(1 + \frac{x_{2}}{x_{1}} )^{n−a_{1}−...−a_{r}} ∏_{i=1}^{r} (1 + (\frac{x_{2}}{x_{1}} )^{a_{j}})}{(\frac{x_{2}}{x_{1}} )^{j}} .  (Chi2′)

Since the constant-termand is of the form P (\frac{x_{2}}{x_{1}} )/(\frac{x_{2}}{x_{1}} )^{j} for some single-variable polynomial P (x), the above can be rewritten, as

χ^{(n−j,j)}(μ_{0}1^{n−|μ_{0}|}) = Coeff_{x^{0}} \frac{(1 − x)(1 + x)^{n−a_{1}−...−a_{r}} ∏_{i=1}^{r} (1 + x^{a_{i}})}{x^{j}} .  (Chi2′′)

Note that the left side is utter nonsense if j > \frac{n}{2}, but the right side makes perfect sense. It is easy to see that defining χ^{(n−j,j)}(μ_{0}1^{n−|μ_{0}|}) by the right side for j > \frac{n}{2}, we get

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

Let’s denote the numerator of the constant-termand of (Chi′′), namely

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

by P (x), then equation (Chi2′′) can be also rewritten as a generating function.

P (x) = ∑_{j=0}^{n} χ^{(n−j,j)}(μ_{0}1^{n−|μ_{0}|}) x^{j} .

Since for any polynomial of a single variable, P (x) = ∑_{j=0}^{n} c_{j}x^{j}, we have

∑_{j=0}^{n} c_{j}^{2} = Coeff_{x^{0}} [P (x)P (x^{−1})] ,

we get

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

Coeff_{x^{0}} [((1 − x)(1 + x)^{n−a_{1}−...−a_{r}} ∏_{j=1}^{r} (1 + x^{a_{j}})) · ((1 − x^{−1})(1 + x^{−1})^{n−a_{1}−...−a_{r}} ∏_{j=1}^{r} (1 + x^{−a_{j}}))] .

= −Coeff_{x^{0}} [\frac{(1 − x)^{2}(1 + x)^{2(n−a_{1}−...−a_{r})} ∏_{j=1}^{r} (1 + x^{a_{j}})^{2}}{x^{n+1}} ] .

But since, by symmetry,

∑_{j=0}^{⌊ \frac{n}{2} ⌋} χ^{(n−j,j)}(μ_{0}1^{n−|μ_{0}|})^{2} = \frac{1}{2} ∑_{j=0}^{n} χ^{(n−j,j)}(μ_{0}1^{n−|μ_{0}|})^{2} ,

we have Lemma 2: Let μ_{0} = (a_{1}, …, a_{r}) be a partition with smallest part larger than one, then

A(μ_{0})(n) = −\frac{1}{2} Coeff_{x^{0}} [\frac{(1 − x)^{2}(1 + x)^{2(n−a_{1}−...−a_{r})} ∏_{j=1}^{r} (1 + x^{a_{j}})^{2}}{x^{n+1}} ] .

We are now ready to prove the theorem. If μ_{0} = Sort(a_{1}, …, a_{r}, 2, …, 2^{t−1}) then

A(μ_{0})(n) = −\frac{1}{2} Coeff_{x^{0}} [\frac{(1 − x)^{2}(1 + x)^{2(n−a_{1}−...−a_{r}−2−2^{2}−...2^{t−1})} ∏_{j=1}^{t−1} (1 + x^{2^{j}})^{2} ∏_{j=1}^{r} (1 + x^{a_{j}})^{2}}{x^{n+1}} ] .

But (transferring a factor of (1 + x)^{2} from the second factor to the product, ∏_{j=1}^{t−1} (1 + x^{2^{j}})^{2}), we have

(1+x)^{2(n−a_{1}−...−a_{r}−2−2^{2}−...2^{t−1})} ∏_{j=1}^{t−1} (1 + x^{2^{j}})^{2} = (1+x)^{2(n−a_{1}−...−a_{r}−1−2−2^{2}−...2^{t−1})} ∏_{j=0}^{t−1} (1 + x^{2^{j}})^{2} .

Hence,

A(μ_{0})(n) = −\frac{1}{2} Coeff_{x^{0}} [\frac{(1 − x)^{2}(1 + x)^{2(n−a_{1}−...−a_{r}−1−2−2^{2}−...2^{t−1})} ∏_{j=0}^{t−1} (1 + x^{2^{j}})^{2} ∏_{j=1}^{r} (1 + x^{a_{j}})^{2}}{x^{n+1}} ] .

By Euler’s good-old (1 − x) ∏_{j=0}^{t−1}(1 + x^{2^{j}}) = 1 − x^{2^{t}}. Hence

A(μ_{0})(n) = − \frac{1}{2} Coeff_{x^{0}} [\frac{(1 − x^{2^{t}})^{2}(1 + x)^{2(n−a_{1}−...−a_{r}−1−2−2^{2}−...2^{t−1})} ∏_{j=1}^{r} (1 + x^{a_{j}})^{2}}{x^{n+1}} ] .

On the other hand, since μ′_{0} = Sort(a_{1}, …, a_{r}, 2^{t}), and all the a_{i}’s are odd, we have

B(μ′_{0})(n + 2) = −Coeff_{x^{0}} [\frac{(1 + x)^{2n+2−2(a_{1}+...+a_{r}+2^{t})}}{x^{n+1}} · (x^{2^{t}} − 1)^{2} · ∏_{j=1}^{r}(x^{a_{j}} + 1)^{2}] .

This completes the proof, since −(1 + 2 + 2^{2} + … + 2^{t−1}) = 1 − 2^{t} .

Acknowledgment

The research for this work was done while the second-named author visited the Faculty of Mathematics at the Weizmann Institute of Science, during the week of Oct. 5-9, 2015. He wishes to thank the Weizmann Institute for its hospitality, and its dedicated stuff, most notably Gizel Maimon.

References

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

[RRZ] Alon Regev, Amitai Regev, and Doron Zeilberger, Identities in Character Tables of S_{n}, J. Difference Equations and Applications, DOI: 10.1080/10236198.2015.1081386, published online 11 Sep 2015, volume and page tbd.

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

[S] Neil Sloane, The On-Line Encyclopedia of Integer Sequences, http://oeis.org .

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 .

Oct. 20, 2015.