Séminaire Lotharingien de Combinatoire 75 (2016), Article B75c

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 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, 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 [M, p. 114, Eq. (7.8)], 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 a 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 a 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 a 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 One-Line Encyclopedia of Integer Sequences [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 led 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 led 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), which 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 than the highest in μ_{0}. In symbols, we conjectured (and later proved [see below], alas, by purely human means) the following theorem.

Theorem. Let μ_{0} be a 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 a sequence of integers S, the symbol Sort(S) denotes that sequence sorted in non-increasing order.)

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

Lemma 1. If μ_{0} = (a_{1}, …, a_{r}), we have

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 us first spell out Equation (Chi) for the two-rowed case, m = 2. In that case, we may write λ = (n − j, j). With μ_{0} = (a_{1}, …, a_{r}), we have

χ^{(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 equivalently expressed in the form

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

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

4 Amitai Regev and Doron Zeilberger

Let us 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 the following auxiliary result. 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

\begin{matrix}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})}}{x^{n+1}} \\ · ∏_{j=1}^{t−1} (1 + x^{2^{j}})^{2} ∏_{j=1}^{r} (1 + x^{a_{j}})^{2}] . \end{matrix}

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

\begin{matrix}(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} . \end{matrix}

Hence,

\begin{matrix}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})}}{x^{n+1}} \\ · ∏_{j=0}^{t−1} (1 + x^{2^{j}})^{2} ∏_{j=1}^{r} (1 + x^{a_{j}})^{2}] . \end{matrix}

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

\begin{matrix}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}} ] . \end{matrix}

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 October 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, [RRZ] Alon Regev, Amitai Regev, and Doron Zeilberger, Identities in Character Tables of S_{n}, J.

Difference Equations and Applications,

 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. Email: 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. Email: zeilberg at math dot rutgers dot edu.