%snII.tex: Surprising Relations Between Sums-Of-Squares of Characters of the Symmetric Group Over Two-Rowed Shapes and Over Hook Shapes 
%%a Plain TeX file by Alon Regev, Amitai Regev, and Doron Zeilberger (x pages)

%begin macros
\def\L{{\cal L}}
%\baselineskip=14pt
\parskip=10pt
\def\halmos{\hbox{\vrule height0.15cm width0.01cm\vbox{\hrule height
  0.01cm width0.2cm \vskip0.15cm \hrule height 0.01cm width0.2cm}\vrule
  height0.15cm width 0.01cm}}
\font\eightrm=cmr8 
\font\eighti=cmmi8 
\font\eightsy=cmsy8 
\font\eightbf=cmbx8 
\font\eighttt=cmtt8 
\font\eightit=cmti8 
\font\eightsl=cmsl8 
\font\eightex=cmex8 
\font\eightsmc=cmcsc8 
\font\tensmc=cmcsc10
\let\smc\tensmc
\font\sixrm=cmr6
\font\sixi=cmmi6
\font\sixsy=cmsy6
\font\sixbf=cmbx6
\font\sixex=cmex6
\font\fiveex=cmex5 
\magnification=1200
\hsize15.6truecm
\def\P{{\cal P}}
\def\Q{{\cal Q}}
\def\1{{\overline{1}}}
\def\2{{\overline{2}}}
\def\CT{\hbox{\rm CT}}
\def\Coeff{\hbox{\rm Coeff}}
\def\Sort{\hbox{\rm Sort}}
\parindent=0pt
\overfullrule=0in
\def\Tilde{\char126\relax}
\def\frac#1#2{{#1 \over #2}}
%\headline={\rm  \ifodd\pageno  \RightHead  \else  \LeftHead  \fi}
%\def\RightHead{\centerline{
%Title
%}}
%\def\LeftHead{ \centerline{Doron Zeilberger}}
%end macros
\leavevmode

\vskip.5cm
\centerline
{\bf  Surprising Relations} 
\centerline
{\bf 
Between Sums-Of-Squares of Characters of the Symmetric Group }
\centerline
{\bf Over Two-Rowed Shapes and Over Hook Shapes }
\bigskip
\centerline
{\it By Amitai REGEV and Doron ZEILBERGER}


\def\eightpoint{
\def\rm{\fam0\eightrm}%
\textfont0=\eightrm \scriptfont0=\sixrm \scriptscriptfont0=\fiverm
\textfont1=\eighti \scriptfont1=\sixi \scriptscriptfont1=\fiverm
\textfont2=\eightsy \scriptfont2=\sixsy \scriptscriptfont2=\fivesy
\textfont3=\eightex \scriptfont3=\sixex \scriptscriptfont3=\fiveex
\textfont\itfam=\eightit \def\it{\fam\itfam\eightit}%
\textfont\slfam=\eightsl \def\sl{\fam\slfam\eightsl}%
\textfont\ttfam=\eighttt \def\tt{\fam\ttfam\eighttt}%
\textfont\bffam=\eightbf \scriptfont\bffam=\sixbf
\scriptscriptfont\bffam=\fivebf \def\bf{\fam\bffam\eightbf}%
\let\smc\eightsmc
%\tt \ttglue=.5em plus .25em minus .15em
%\let\rm\eightrm
%\let\bf\eightbf
%\let\it\eightit
%\let\mus\eightmus
\normalbaselineskip9.6pt
\setbox\strutbox=\hbox{\vrule height7pt depth2pt width0pt}%
\let\sc\sixrm \normalbaselines
\rm}

\vskip.5cm
{
\leftskip1.5cm\rightskip1.5cm
\eightpoint
{\eightsmc Abstract.} In a recent article, we noted (and proved) that the sum of the squares of the characters of the symmetric group,
$\chi^{\lambda}(\mu)$,
over all shapes $\lambda$ with two rows and $n$ cells and $\mu=31^{n-3}$, equals, surprisingly, to
1/2 of that sum-of-squares taken over all hook shapes  with $n+2$ cells and with $\mu= 321^{n-3}$.
In the present note, we show that this is only the tip of a huge iceberg! We will prove that, if
$\mu$ consists of odd parts and (a possibly empty) string of {\it consecutive} powers of $2$, namely $2,4, \dots, 2^{t-1}$ for $t \geq 1$, then
the sum of  $\chi^{\lambda}(\mu)^{2}$ over all two-rowed shapes $\lambda$  with $n$ cells equals exactly $\frac{1}{2}$ times
the analogous sum of $\chi^{\lambda}(\mu')^{2}$ over all shapes $\lambda$ of {\it hook shape} with $n+2$ cells, 
where $\mu'$ is the partition obtained from $\mu$ by retaining all odd parts but replacing the string
$2,4, \dots, 2^{t-1}$ by $2^t$.
\par}

%First page headline in LaTeX for S\'eminaire Lotharingien de Combinatoire
%--first part
\font\rms=cmr8 
\font\its=cmti8
\font\bfs=cmbx8
\headline={\its S\'eminaire Lotharingien de
Combinatoire \bfs 75 \rms (2016), Article~B75c\hfill}
\footline={\hfil}
\vskip.5cm

Recall that the {\it constant term} of a {\it Laurent polynomial} in $(x_1, \dots, x_m)$ is the free term, i.e.,
the coefficient of $x_1^0 \cdots x_m^0$. For example,
$$
\CT_{x_1,x_2} (x_1^{-3}x_2+x_1x_2^{-2}+5)=  5   .
$$
Recall that a {\it partition} (alias {\it shape}) of an integer $n$, with $m$ {\it parts} (alias {\it rows}),
is a non-increasing sequence of positive integers
$$
\lambda= (\lambda_1, \dots, \lambda_m),
$$
where $\lambda_1 \geq \lambda_2 \geq \cdots \geq \lambda_m >0$ and $\lambda_1 + \cdots + \lambda_m=n$.

If $\lambda=(\lambda_1, \dots, \lambda_m)$ and $\mu=(\mu_1, \dots, \mu_r)$ are partitions of $n$ with $m$ and $r$ parts,
respectively, then it easily follows from [M,
p.~114, Eq.~(7.8)], that
the {\it characters}, $\chi^{\lambda}(\mu)$,  of the {\it symmetric group}, $S_n$, may be obtained
via the {\it constant term} expression
$$
\chi^{\lambda}(\mu) \, = \,
\CT_{x_1, \dots , x_m} \,
\frac
{\prod_{1 \leq i < j \leq m} (1-\frac{x_j}{x_i}) \prod_{j=1}^r \left ( \sum_{i=1}^{m} x_i^{\mu_j} 
\right )}
{\prod_{i=1}^{m} x_i^{\lambda_i}} 
   .
\eqno(Chi)
$$
As usual, for a partition $\mu$, $|\mu|$ denotes the sum of its parts, in other words, the integer that is
being partitioned.

In [RRZ] we considered  two quantities. Let $\mu_0$ be a partition with smallest part $\geq 2$.
The first quantity, that we will call henceforth
$A(\mu_0)(n)$, is the following  sum-of-squares over two-rowed
shapes~$\lambda$:  
$$
A(\mu_0)(n):= \, \sum_{j=0}^{\lfloor n/2 \rfloor} \chi^{(n-j,j)}( \mu_0 1^{n-|\mu_0|})^2  .
$$
(Note that in [RRZ] this quantity was denoted by $\psi^{(2)}(\mu_0
1^{n-|\mu_0|})$.) 

The second quantity was the sum-of-squares over {\it hook-shapes}
$$
B(\mu_0)(n):= \, \sum_{j=1}^{n} \chi^{(j,1^{n-j})}( \mu_0 1^{n-|\mu_0|} )^2 .
$$
(Note that in [RRZ] this quantity was denoted by $\phi^{(2)}(\mu_0
1^{n-|\mu_0|})$.) 

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

\headline={\eightsmc 
\ifodd\pageno  
\hfill Sums-Of-Squares of Characters of the Symmetric Group \hfill  \folio 
\else
\folio \hfill Amitai Regev and Doron Zeilberger\hfill  \fi}%
%

Unless $\mu_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 {\it
remarkable} identity 
$$
A(3)(n)=\frac{1}{2} B(3,2)(n+2)  .
$$
This led to the following natural question:

{\leftskip1cm\rightskip1cm\it
Are there other partitions, $\mu_0$, such that there exists a partition, $\mu'_0$ with
$|\mu'_0|=|\mu_0|+2$, such that the ratio $A(\mu_0)(n)/B(\mu'_0)(n+2)$
is a constant?\par}

This led us to write a new procedure in the Maple package
$$
\hbox{\tt
http://www.math.rutgers.edu/\~{}zeilberg/tokhniot/Sn.txt}
$$
that accompanies [RRZ], 
called  {\tt SeferNisim(K,N0)}, which searched for such pairs
$[\mu_0,\mu'_0$].  
We then used our {\it human}  ability for {\it pattern recognition} to notice that  all the successful pairs 
(we went up to $|\mu_0| \leq 20$) turned out to be such that  $\mu_0$ either consisted of only odd parts, and then $\mu'_0$ was
$\mu_0$ with $2$ appended, or, more generally, $\mu_0$ consisted of odd parts together with a string of {\it consecutive}
powers of $2$ (starting with $2$), and $\mu'_0$ was obtained from $\mu_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 $\mu_0$. In symbols, 
we conjectured (and later proved [see below], {\it alas}, by purely
human means) the following theorem.

{\bf Theorem.} {\it Let $\mu_0$ be a partition of the form
$$
\mu_0 =\Sort([a_1, \dots, a_s, 2,2^2, \dots, 2^{t-1}]) ,
$$
where
$$
a_1 \geq a_2 \geq \cdots \geq a_s \geq 3 
$$
are all\/ {\bf odd} and $t \geq 1$. 
{\rm(}If $t=1$ then $\mu_0$ only consists of odd parts.{\rm)}
Define
$$
\mu'_0 =\Sort([a_1, \dots, a_s, 2^t]) .
$$
Then, for every $n \geq |\mu_0|$, we have
$$
A(\mu_0)(n) = \frac{1}{2} B(\mu'_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
{\bf constant-term} expression for 
$B(\mu_0)(n)$ from [RRZ].

{\bf Lemma 1.} {\it If $\mu_0=(a_1, \dots, a_r)$, we have
$$
B(\mu_0)(n)= \Coeff_{x^0}
\left [ 
\frac{(1+x)^{2n-2 -2(a_1 + \cdots + a_r) }}{x^{n-1}} \cdot \prod_{i=1}^{r} (x^{a_i} -(-1)^{a_i}) (1 - (-1)^{a_i}x^{a_i} ) 
\right ]  .
$$}%


We need an analogous constant-term expression  for $A(\mu_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 $\lambda=(n-j,j)$.
With $\mu_0=(a_1, \dots, a_r)$, we have
$$
\chi^{(n-j,j)}(\mu_0 1^{n-|\mu_0|}) \, = \,
\CT_{x_1, x_2} \,
\frac
{ (1-\frac{x_2}{x_1})  (x_1 + x_2)^{n-a_1- \cdots -a_r}  \prod_{i=1}^r \left ( x_1^{a_i} + x_2^{a_i} \right )}
{x_1^{n-j} x_2^{j}}    .
\eqno(Chi2)
$$
This can be rewritten as
$$
\chi^{(n-j,j)}(\mu_0 1^{n-|\mu_0|}) \, = \,
\CT_{x_1, x_2} \,
\frac
{ (1-\frac{x_2}{x_1})  (1 + \frac{x_2}{x_1})^{n-a_1- \cdots -a_r}  \prod_{i=1}^r \left ( 1+ (\frac{x_2}{x_1})^{a_j} \right )}
{(\frac{x_2}{x_1})^j }    .
\eqno(Chi2')
$$
Since the {\it constant-termand} is of the form
$P(\frac{x_2}{x_1})\big/(\frac{x_2}{x_1})^j$, for some {\it
single-variable} polynomial $P(x)$, the 
above can be equivalently expressed in the form
$$
\chi^{(n-j,j)}(\mu_0 1^{n-|\mu_0|}) \, = \,
\Coeff_{x^0} \,
\frac
{ (1-x)  (1 + x)^{n-a_1- \cdots -a_r}  \prod_{i=1}^r \left ( 1+ x^{a_i} \right )}
{x^j }    .
\eqno(Chi2'')
$$

Note that the left-hand side is {\it utter nonsense} if $j > \frac{n}{2}$, but the right-hand side makes perfect sense. It is easy to see that,
defining $\chi^{(n-j,j)}(\mu_0 1^{n-|\mu_0|})$ by the right-hand side for  $j > \frac{n}{2}$, we get
$$
\chi^{(n-j,j)}(\mu_0 1^{n-|\mu_0|}) \, = \, - \chi^{(j,n-j)}(\mu_0 1^{n-|\mu_0|})  .
$$ 

Let us denote the numerator of the constant-termand of $(Chi'')$,
namely 
$$
(1-x)  (1 + x)^{n-a_1- \cdots -a_r}  \prod_{i=1}^r \left ( 1+ x^{a_i} \right )  ,
$$
by $P(x)$. Then
Equation~$(Chi2'')$ can be also rewritten as a {\it generating function},
$$
P(x)=\sum_{j=0}^{n} \chi^{(n-j,j)}(\mu_0 1^{n-|\mu_0|}) \, x^j  .
$$
Since for any polynomial of a single variable, $P(x)=\sum_{j=0}^{n}
c_j x^j$, we have 
$$
\sum_{j=0}^{n} c_j^2 = \Coeff_{x^0}\!\! \left [ P(x) P(x^{-1}) \right ]  ,
$$
we get
$$
\eqalign{
\sum_{j=0}^{n}  \chi^{(n-j,j)}(\mu_0 1^{n-|\mu_0|}&)^2 
=
\Coeff_{x^0} \!\!
\left [ \left ( (1-x)  (1 + x)^{n-a_1- \cdots
-a_r}  \prod_{j=1}^r \left ( 1+ x^{a_j} \right ) \right )\right. \cr
&\kern1.5cm
\left.
\cdot
\left ( (1-x^{-1})  (1 + x^{-1})^{n-a_1- \cdots
-a_r}  \prod_{j=1}^r \left ( 1+ x^{-a_j} \right ) \right ) 
\right ]  \cr
&=
-\Coeff_{x^0}
\left [
\frac{ (1-x)^2  (1 + x)^{ 2(n-a_1- \cdots -a_r)}  \prod_{j=1}^r \left
( 1+ x^{a_j} \right )^2 } 
{x^{n+1}} \, \right ]  .
}
$$
But since, by symmetry,
$$
\sum_{j=0}^{\lfloor \frac{n}{2} \rfloor }  \chi^{(n-j,j)}(\mu_0 1^{n-|\mu_0|})^2 = 
\frac{1}{2} \sum_{j=0}^{n}  \chi^{(n-j,j)}(\mu_0 1^{n-|\mu_0|})^2  ,
$$
we have the following auxiliary result.

{\bf Lemma 2.} {\it Let $\mu_0=(a_1, \dots, a_r)$ be a partition with
smallest part larger than one. Then 
$$
A(\mu_0)(n)=
-\frac{1}{2} \, \Coeff_{x^0} \left [
\frac{(1-x)^2  (1 + x)^{2(n-a_1- \cdots -a_r)}  \prod_{j=1}^r \left ( 1+ x^{a_j} \right )^2 }
{x^{n+1}} \right ]  .
$$}%


We are now ready to prove the theorem. If $\mu_0=\Sort (a_1, \dots, a_r, 2, \dots , 2^{t-1})$, then
$$
\eqalign{
A(\mu_0)(n)=
- \frac{1}{2} \, \Coeff_{x^0} \!\!&\left [
\frac{(1-x)^2  (1 + x)^{2(n-a_1- \cdots -a_r-2-2^2- \cdots 2^{t-1})}  
 }
{x^{n+1}}\right.\cr
&\kern4cm
\left.
\cdot
\prod_{j=1}^{t-1} \left ( 1+ x^{2^j} \right )^2
\prod_{j=1}^r \left ( 1+ x^{a_j} \right )^2 
 \right ]  .}
$$
But, transferring a factor of $(1+x)^2$ from the second factor to the
product,\break   $\prod_{j=1}^{t-1} \left ( 1+ x^{2^j} \right )^2$, 
we have
$$
\eqalign{
 (1 + x)^{2(n-a_1- \cdots -a_r-2-2^2- \cdots 2^{t-1})} &
 \prod_{j=1}^{t-1} \left ( 1+ x^{2^j} \right )^2\cr
&\kern-.5cm
=
(1 + x)^{2(n-a_1- \cdots -a_r-1-2-2^2- \cdots 2^{t-1})}  \prod_{j=0}^{t-1} \left ( 1+ x^{2^j} \right )^2  .}
$$
Hence,
$$
\eqalign{
A(\mu_0)(n)=
- \frac{1}{2} \, \Coeff_{x^0} \!\!&\left [
\frac{(1-x)^2  (1 + x)^{2(n-a_1- \cdots -a_r-1-2-2^2- \cdots 2^{t-1})}  
 }
{x^{n+1}}\right.\cr
&\kern4cm
\left.
\cdot
\prod_{j=0}^{t-1} \left ( 1+ x^{2^j} \right )^2
\prod_{j=1}^r \left ( 1+ x^{a_j} \right )^2 
 \right ]  .}
$$
By Euler's good-old $(1-x)\prod_{j=0}^{t-1}(1+x^{2^j})=1-x^{2^t}$,
we conclude
$$
\eqalign{
A(&\mu_0)(n)\cr
&=
-\, \frac{1}{2} \, \Coeff_{x^0} \left [
\frac{(1-x^{2^t})^2  (1 + x)^{2(n-a_1- \cdots -a_r-1-2-2^2- \cdots 2^{t-1})}  \prod_{j=1}^r \left ( 1+ x^{a_j} \right )^2 }
{x^{n+1}} \right ]  .}
$$
On the other hand, since $\mu'_0=\Sort(a_1, \dots, a_r, 2^t)$, and all the $a_i$'s are odd, we have
$$
B(\mu'_0)(n+2)= - \Coeff_{x^0}
\left [ 
\frac{(1+x)^{2n+2 -2(a_1 + \cdots + a_r+2^t) }}{x^{n+1}} \cdot (x^{2^t}-1)^2 \cdot \prod_{j=1}^{r} (x^{a_j} +1)^2 
\right ]  .
$$
This completes the proof, since $-(1+2+ 2^2+  \cdots +2^{t-1} ) = 1-2^t$  . \halmos 

\bigskip
{\bf  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.

\bigskip
\centerline{\smc References}

\parskip4pt
\eightpoint
\hangindent20pt
\hangafter1
[M] I. G. Macdonald, {\it Symmetric Functions and Hall Polynomials},
2nd ed., Clarendon Press, Oxford, 1995. 

\hangindent20pt
\hangafter1
[RRZ] Alon Regev, Amitai Regev, and Doron Zeilberger,
 {\it Identities in Character Tables of $S_n$}, J. Difference Equations and Applications, \hfill\break
{\tt http://www.math.rutgers.edu/\~{}zeilberg/mamarim/mamarimhtml/sn.html}  .

\hangindent20pt
\hangafter1
[S] Neil Sloane, {\it The On-Line Encyclopedia of Integer Sequences}, {\tt http://oeis.org}  .

\vskip1cm
\leftskip.5cm\rightskip.5cm
\smc
Amitai Regev, Department of Pure Mathematics, Weizmann Institute of Science, Rehovot 76100, Israel.
Email: {\tt amitai dot regev at weizmann dot ac dot il}.
\smallskip
Doron Zeilberger, Department of Mathematics, Rutgers University
(New\break  Bruns\-wick), Hill Center-Busch Campus, 110 Frelinghuysen
Rd., Piscataway, NJ 08854-8019, USA. 
Email: {\tt zeilberg at math dot rutgers dot edu}.

%Oct. 20, 2015.

\end










