Identities in character tables of Sn

By Alon Regev, Amitai Regev, and Doron Zeilberger

[With great assistance by Shalosh B. Ekhad]

.pdf   .ps   .tex

Written: July 13, 2015
[Appeared in J. of Difference Equations and its Applications 22(2016), no. 2, 272-279.
DOI:10.1080/10236198.2015.1081386 ]
In the classic "Concrete Math", by Graham, Patashnik and Knuth they state:

"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 is to indicate that a similar statement seems to hold for the character tables of the symmetric groups Sn. Just as important, it is a case-study in using a computer algebra system to prove deep identities, way beyond the ability of mere humans.

Added later: read the sequel,

Added Oct. 27, 2016: Christine Bessenrodt discovered (and proved) a lovely refinement

# Maple Package

Important: This article is accompanied by Maple package

• Sn, a Maple package that discovers, and helps prove neat identities regarding the character table entries of the Symmetric Group

# Sample Input and Output for the Maple package Sn

• If you want to see 134 propositions (complete with proofs!) stating closed form expressions, in n, for sums of the squares over the characters of the Symmetric Group , Sn,

Χλ(μ)

where λ ranges over all hook shapes with n cells, and where μ is a fixed partition, μ0 (whose smallest part is larger than 1) followed by n-|μ0| ones, for all such μ0, with |μ0| ≤ 14, the

input   yields the   output

• If you want to see 134 propositions (complete with proofs!) stating closed form expressions, in n, for sums of the squares over the characters of the Symmetric Group , Sn,

Χλ(μ)

where λ ranges over all shapes with at most TWO rows, with n cells, and where μ is a fixed partition, μ0 (whose smallest part is larger than 1) followed by n-|μ0| ones, for all such μ0, with |μ0| ≤ 14, the

input   yields the   output

• If you want to see 29 theorems (complete with (semi-rigorous) proofs) stating linear recurrences with polynomial coefficients, for the sequences given by sums of the squares over the characters of the Symmetric Group , Sn,

Χλ(μ)

where λ ranges over all shapes with at most THREE rows, with n cells, and where μ is a fixed partition, μ0 (whose smallest part is larger than 1) followed by n-|μ0| ones, for all such μ0, with |μ0| ≤ 9, the

input   yields the   output

• If you want to see 14 theorems (complete with (semi-rigorous) proofs) stating linear recurrences with polynomial coefficients, for the sequences given by (straight, non-squared) sums of characters of the Symmetric Group , Sn,

Χλ(μ)

where λ ranges over all shapes with at most THREE rows, with n cells, and where μ is a fixed partition, μ0 (whose smallest part is larger than 1) followed by n-|μ0| ones, for all such μ0, with |μ0| ≤ 7, the

input   yields the   output

• If you want to see 14 theorems (complete with (semi-rigorous) proofs) stating linear recurrences with polynomial coefficients, for the sequences given by (straight, non-squared) sums of characters of the Symmetric Group , Sn,

Χλ(μ)

where λ ranges over all shapes with at most FOUR rows, with n cells, and where μ is a fixed partition, μ0 (whose smallest part is larger than 1) followed by n-|μ0| ones, for all such μ0, with |μ0| ≤ 7, the

input   yields the   output

• If you want to see 7 theorems (complete with (semi-rigorous) proofs) stating linear recurrences with polynomial coefficients, for the sequences given by (straight, non-squared) sums of characters of the Symmetric Group , Sn,

Χλ(μ)

where λ ranges over all shapes with at most FIVE rows, with n cells, and where μ is a fixed partition, μ0 (whose smallest part is larger than 1) followed by n-|μ0| ones, for all such μ0, with |μ0| ≤ 5, the

input   yields the   output

Doron Zeilberger's List of Papers