\documentclass[twoside,12pt]{article}
\setlength{\textwidth}{16.5cm} \setlength{\textheight}{21.5cm}


\usepackage[all, 2cell, dvips]{xy}
\usepackage{latexsym,amsmath, amsfonts, graphics, epsf, epic}
\usepackage{amsthm}
\usepackage{amssymb}
\usepackage{amsopn}
\usepackage{amscd}
%\usepackage[vcentermath,enableskew]{youngtab}
\usepackage{color}


\topmargin -1cm \oddsidemargin -.2cm \evensidemargin -.2cm
\pagestyle{empty}


\theoremstyle{plain}
\newtheorem{thm}{Theorem}[section]
\newtheorem{cor}[thm]{Corollary}
\newtheorem{lem}[thm]{Lemma}
\newtheorem{prop}[thm]{Proposition}
\newtheorem{mlem}[thm]{Main Lemma}
\newtheorem{vnlem}[thm]{Von-Neumann's Lemma}
\newtheorem{defcor}[thm]{Definition/Corollary}
%
\theoremstyle{definition}
\newtheorem{rmk}[thm]{Remark}
\newtheorem{remark}[thm]{Remark}
\newtheorem{example}[thm]{Example}
\newtheorem{defn}[thm]{Definition}
\newtheorem{exc}{Exercise}
\newtheorem{conjecture}[thm]{Conjecture}



%11111111111111111
\font\sym=msam10
\def\Vdash{\hbox{\sym\char'015}}






\parindent=0pt % paragraph indentation
\usepackage{amssymb}
\newcommand{\ZZ}{\mathbb Z}
\newcommand{\NN}{\mathbb N}
\def\QQ{\mathbb{Q}}
\def\FF{\mathbb{F}}
\def\CC{\mathbb{C}}
\def\Om{\Omega}


\def\om{\omega}
\def\tr{\mbox{\rm tr}}
\def\sg{\sigma}
\def\LL{\cal L}
\def\BB{\cal B}
\def\AA{\cal A}
\def\D{{\cal D}}
\def\lm{\lambda}
\def\lam{\lambda}
\def\KK{\cal K}
\def\dim{\mbox{\rm dim }}
\def\ins{\mbox{\rm ins}}
\def\al{\alpha}
\def\tl{T_{\lambda}}
\def\gm{\gamma}
\def\tm{T_{\mu}}
\def\l.l.o.{\it l.l.o}
\def\E{\eta}
\def\ep{\epsilon}
\def\eps{\varepsilon}
\def\f{\varphi}
\def\p{\psi}
\def\A{{\cal A}}
\def\B{{\cal B}}
\def\K{{\cal K}}
\def\BE{{\cal E}}
\def\C{{\cal C}}
\def\O{{\cal O}}
\def\R{{\cal R}}

\def \SST{{semi-standard tableau~}}%99999999999999999


\def\ctr#1{\hfill{#1}\hfill}
\def\hten{\hskip 10pt}
\def\medno{\medskip\noindent}
\def\sksix{\noalign{\vskip 6pt}}
\def\sstyle{\scriptstyle}
\def\half{{1\over 2}}
\def\quart{{1\over 4}}
\def\ol{\overline}
\def\wtil{\widetilde}
\def\gam{\gamma}
\def\pr{^{\prime}}
\def\ofmu{(\mu)}
\def\ofnu{(\nu)}
\def\sig{\sigma}
\def\ofsig{(\sig)}
\font\amsy=msbm10
\def\rline{\hbox{\amsy\char'122}}
\def\zline{\hbox{\amsy\char'132}}
\font\diff=msbm10
\def\leneq{\hbox{\diff\char'010}}
\def\geneq{\hbox{\diff\char'011}}
\font\sdiff=msbm5
\def\sleneq{\hbox{\sdiff\char'010}}
\font\goth=eufm10
\def\gothA{\hbox{\goth A}}
\def\notexists{\hbox{$\exists$\hskip -5pt / }}
\def\rslash{\delimiter"26E30F }
\def\lan{\langle}
\def\ran{\rangle}
\def\chiup{\raise 2pt\hbox{$\chi$}}
\def\rmpar{\hbox{par}}
\def\card{\hbox{card}}


%Math Abbreviation


\DeclareMathOperator{\Hom}{Hom} \DeclareMathOperator{\End}{End}
\DeclareMathOperator{\sgn}{sgn}
%\DeclareMathOperator{\D}{Det}
\DeclareMathOperator{\Char}{char}
\DeclareMathOperator{\M}{\textsf{M}}
\DeclareMathOperator{\PW}{P^+(n,r)}
\DeclareMathOperator{\LW}{\Lambda^+}
\DeclareMathOperator{\W}{P^+(n,r)}


\def\GL{\mbox{\rm GL}}


\newcommand{\To}{\longrightarrow}
\newcommand{\id}{\rm{id}}
\DeclareMathOperator{\he}{\hat{e}}
\DeclareMathOperator{\hv}{\hat{v}}




\newcommand{\di}{\underline{i}}
\newcommand{\kk}{\underline{k}}
\newcommand{\db}{\underline{b}}
\newcommand{\da}{\underline{a}}
\newcommand{\jj}{\underline{j}}
\newcommand{\dk}{\underline{k}}
\newcommand{\dl}{\underline{l}}
\newcommand{\un}{\underline}
\newcommand{\ov}{\overline}
\newcommand{\ka}{{\kappa}}


\pagestyle{myheadings}


\newenvironment{pf}{\noindent \textit{Proof.}\,}{\hfill$\square$ \vskip5pt}




\title{Identities in character tables of $S_n$}
%{Sums of squares of some characters of $S_n$}

\author{Alon Regev, Amitai Rege and Doron Zeilberger \\
%Department of Mathematics,\\
%The Weizmann Institute of science,\\
%Rehovot, Israel\\
%e-mail: amitai.regev at weizmann.ac.il\\
}

%\thanks{}


%\date{\today}


\begin{document}



\maketitle



\section{New section added by DZ (INCOMPLETE!)}

It should be possible (hopefully) to prove the following theorem.

\begin{thm}\label{left1}

Let $\mu$ be {\it any} partition, and let $|\mu|$ be the sum of its parts. Then, for $n \geq |\mu|$, we have
$$
\sum_{\lambda\vdash n}(\chi^\lambda(\mu, 1^{n-|\mu|}))^2= C(\mu) (n-|\mu|)! \quad,
$$
where
$$
C(\mu):=\sum_{\lambda\vdash |\mu| }(\chi^\lambda(\mu))^2 \quad,
$$

\end{thm}

{\bf Sketch of Proof}
\bigskip
Recall that $f_{\lambda}$, the number of Standard Young Tableaux of shape $\lambda$, alias
$\chi^{\lambda}(1^n)$, satisfies two famous recurrences
$$
f_\lambda \, = \, \sum_{\lambda^{-}} f_{\lambda^{-}} \quad,
\eqno(GoingDown)
$$

where the sum is over all partitions $\lambda^{-}$ obtained by removing one cell from $\lambda$ (legally).
This recurrence is trivial combinatorially, but it should not be too hard to prove it directly,
either from representation theory, or via the fact at the very last line of p. 114 of
Macdonald's Second Ed., that $\chi^{\lambda}(\rho)$ is the coefficient of
$x^{\lambda + \delta}$ in $a_{\delta} p_{\rho}$.

It also follows (combinatorially from Robinson-Schenstead, but it is not too hard to prove it directly,
once again from the above fact), that, if $n=|\lambda|$, then
$$
(n+1)f_\lambda \, = \, \sum_{\lambda^{+}} f_{\lambda_{+}} \quad,
\eqno(GoingUp)
$$
where the sum is over all partitions $\lambda^{+}$ obtained by adding one cell to $\lambda$ (legally).


Let
$$ 
A_n:=\sum_{\lambda\vdash n}f_{\lambda}^2 
$$
Recall that one way to prove that $A_n=n!$
(w/o using R-S) is to note that, because of the Going Down Formula
$$ 
A_n = \sum_{\lambda\vdash n}f_{\lambda}^2 =
\sum_{\lambda\vdash n, \mu\vdash n-1}f_{\lambda} f_{\mu} 
$$
where the sum is over all pairs $\lambda,\mu$ such that $\lambda -\mu$ is one legal cell.
But this is the same, thanks to the Going Up formula, to $nA_{n-1}$. Indeed:
$$ 
n A_{n-1} = \sum_{\mu\vdash n-1} n f_{\mu}^2 =
\sum_{\mu\vdash n-1} (n f_{\mu}) f_{\mu} 
\sum_{\lambda\vdash n, \mu\vdash n-1}f_{\lambda} f_{\mu}  \quad ,
$$
with the same summation set.


To prove the theorem we note that the Going Down formula seems to hold for all $\mu$ ending in $1$

$$
\chi^{\lambda}(\mu) =\sum_{\lambda^{-}} \chi^{\lambda^{-}}(\mu') \quad ,
\eqno(GoingDownGeneral)
$$
where $\mu'$ is $\mu$ with the last part (that must be a $1$, by assumption) removed.

An analog of the Going Up formula seems to hold (see the Maple package {\tt SnCharacterTableMiracles}) for
any $\mu$, we have
$$
(N_1(\mu)+1) \,\, \chi^{\lambda}(\mu) =\sum_{\lambda^{+}} \chi^{\lambda^{+}}(\mu_1) \quad ,
\eqno(GoingUpGeneral)
$$
where $N_1(\mu)$ is the number of ones in $\mu$, and $\mu_1$ is the partition obtained from $\mu$ by appending a $1$.

The proof of the theorem now follows the same way.





\begin{thebibliography}{99}

\bibitem{graham}R.L. Graham,D.E. Knuth and O. Patashnik, Concrete Mathematics.

\bibitem{knuth} D.E. Knuth, The Art of Computer Programing, Vol. 3, Addison Wesley, Reading Mass. 1968.

\bibitem{macdonald} I.G. Macdonald, Symmetric Functions

\bibitem{online} The Online Encyclopedia of Integer Sequences.



\bibitem{stanley} R. Stanley, EC II










\end{thebibliography}

\end{document}



\newpage

 \subsubsection{Binomial preparations (following Stanley)}
 Recall that
 $$
 {n\choose k}=\frac{n!}{k_!(n-k)!}=\frac{1}{k!}n(n-1)\cdots (n-k+1).
 $$
 Given any $a$, we define
 $$
 {a\choose k}=\frac{1}{k!}a(a-1)\cdots (a-k+1),
 $$
 provided $k\in\mathbb{N}$. The binomial theorem becomes
 $$
 (1+x)^a=\sum_{k\ge 0}{a\choose k}x^k.
 $$
 \begin{example}
 We show here that
 $$
 (1-4x)^{-1/2}=\sum_{n\ge 0}{2n\choose n}x^n.
 $$

 Change $k$ to $n$ and let $a=-\frac{1}{2}$, then
 $$
 1/\sqrt{1-4x}=(1-4x)^{-1/2}=\sum_{n\ge 0}{{-1/2}\choose n}(-4x)^n.
 $$
 Calculate:
 $$
 {{-1/2}\choose n}(-4)^n=\frac{(-1/2)(-3/2)\cdots (-(2n-1)/2)\cdot(-4)^n}{n!}
 =\frac{2^n\cdot 1\cdot 3 \cdots (2n-1)}{n!}=\frac{(2n)!}{n!^2},
 $$
 which proves that indeed,
 $$
 (1-4x)^{-1/2}=\sum_{n\ge 0}{2n\choose n}x^n.
 $$
 Square both sides to deduce the identity
 $$
 \sum_{j\ge 0}^n{2j\choose j}{2n-2j\choose n-j}=4^n.
 $$

 \end{example}


\subsection{Generating function for the Catalan numbers (Following Wilf)}
Recall the $n$-th Catalan number $C_n=\frac{1}{n+1}{2n\choose n}$.
Let $C(x)=\sum_n C_n\cdot x^n$, the ordinary generating function
 for the Catalan numbers, then it is well known that
 $$
 C(x)=\sum_{k=0}^\infty C_kx^k =1+x+2x^2+5x^3+14x^4+42x^5+\cdots=\frac{1-\sqrt{1-4x}}{2}.
 $$

 %Let $C_n$ be the $n$-th Catalan number, then
 We briefly review the proof.
 The following recurrence is well known:
 $$
 C_n=\sum_k C_{k-1}C_{n-k}.
 $$
 Let $C(x)=\sum_kC_k\cdot x^k$, then the above recurrence implies that $C(x)-1=xC^2(x)$. From the quadratic equation
 $xC^2(x)-C(x)+1=0$ we get
 $$
 C(x)=\frac{1\pm\sqrt{1-4x}}{2x}\quad\mbox{hence}\quad C(x)=\frac{1-\sqrt{1-4x}}{2x},
 $$
 see [Wilf] for more details.

%LLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLL





The following proposition is known, but for the sake of completeness we include its proof here.
Let $\lm\vdash n$ with $\C_\lm\subseteq S_n$ the corresponding conjugacy class. Let $\chi$ be an
$S_n$ character and let $\sg\in \C_\lm$, then we write $\chi(\sg)=\chi(\lm$).
\begin{prop}\label{august.7}
Let  $\lm\vdash n$ then $\chi_{\f_{k,n}} (\lm)=k^{\ell(\lm)}$.
\end{prop}

\begin{proof}
Let $v_1,\ldots,v_k\in V$ be a basis of $V$, so
$\{v_{i_1}\otimes\cdots\otimes v_{i_n} \mid 1\le i_j\le n\}$ is a basis of $V^{\otimes n}$.
Let $\sg\in \C_\lm$ and calculate the matrix $M_\sg$ of $\f_{k,n}(\sg)$ with respect to that basis, then
$\chi_{\f_{k,n}}(\sg)=tr(M_\sg)$.
We may assume
that the disjoint cycle decomposition of $\sg$ is given by $\sg=\prod(r,r+1,\ldots,s-1,s)$. Denote
$\bar v=v_{i_1}\otimes\cdots\otimes v_{i_n}$, then correspondingly
$$
\bar v=\bigotimes (v_{i_r}\otimes v_{i_{r+1}}\otimes\cdots\otimes v_{i_s}).
$$
Now $\bar v$ contributes $1$ to $tr(M_\sg)$ if ${\f_{k,n}}(\sg)(\bar v)=\bar v$, and it contributes
zero if ${\f_{k,n}}(\sg)(\bar v)\ne\bar v$.
So count how many $\bar v$'s satisfy  ${\f_{k,n}}(\sg)(\bar v)=\bar v$: we have
$$
{\f_{k,n}}(\sg)(\bar v)=\bigoplus (v_{i_s}\otimes v_{i_r}\otimes v_{i_{r+1}}\otimes\cdots\otimes v_{i_{s-1}}).
$$
Therefore ${\f_{k,n}}(\sg)(\bar v)=\bar v$ if and only if for each cycle $(r,\ldots,s)$ of $\sg$,
$$
v_{i_r}=v_{i_{r+1}}=\cdots =v_{i_s} ~(\in\{v_1,\ldots,v_k\}).
$$
There are $k$ possibilities  for, say, $v_{i_r}$, (these are $v_1,\ldots,v_k$), hence there are $k^{\ell(\lm)}$ possibilities
for such $\bar v$, which implies that $tr (M_\sg)=k^{\ell(\lm)}$.
\end{proof}
1111111111111111111111111111111111111111111111111





\section{Some conjectures for $\phi_n^{(2)}(\mu)$ when $\mu_1\approx n$}

Recall our notation
$$
\phi_n^{(2)}(\mu)=\sum_{k=1}^n \left(   \chi^{(k,1^{n-k})} (\mu)    \right)^2.
$$
We begin with a general conjecture for $\mu_1\approx n$.

\begin{conjecture}
Let $\mu=\mu^{(n)}=(n-k,\nu^{(k)})$ where $k\ge 1$ is fixed, $n\to\infty$ and $\nu^{(k)}\vdash k$.
Then the corresponding sum is a constant, depending only on $\nu^{(k)}$.
\end{conjecture}

Observe that by the M-N rule, $\chi^{(k,1^{n-k})}(n)=\pm 1$. It follows that
$$
\sum_{k=1}^n \left(\chi^{(k,1^{n-k})}(n) \right)^2=n.
$$

We move to the next cases.
\begin{conjecture}
In the case $\mu=(n-1,1)$ we get
$$
\sum_{k=1}^n \left(\chi^{(k,1^{n-k})}(n-1,1) \right)^2=2.
$$
This was checked for $2\le n\le 10$.

\end{conjecture}

\begin{conjecture}
In the case $\mu=(n-2,1,1)$, or $\mu=(n-2,2)$, we get
$$
\sum_{k=1}^n \left(\chi^{(k,1^{n-k})}(n-2,1,1) \right)^2=\sum_{k=1}^n \left(\chi^{(k,1^{n-k})}(n-2,2) \right)^2=4.
$$
This was checked for $4\le n\le 10$.

\end{conjecture}


\begin{conjecture}
In the case $\mu=(n-3,3)$ we get
$$
\sum_{k=1}^n \left(\chi^{(k,1^{n-k})}(n-3,3) \right)^2=6.
$$
This was checked for $6\le n\le 10$.

\end{conjecture}



\begin{conjecture}
In the case $\mu=(n-3,2,1)$ we get
$$
\sum_{k=1}^n \left(\chi^{(k,1^{n-k})}(n-3,2,1) \right)^2=4.
$$
This was checked for $6\le n\le 10$.

\end{conjecture}
\begin{conjecture}
In the case $\mu=(n-3,1^3)$ we get
$$
\sum_{k=1}^n \left(\chi^{(k,1^{n-k})}(n-3,1^3) \right)^2=12.
$$
This was checked for $6\le n\le 10$.

\end{conjecture}

\medskip

With less evidence we have the following conjectures:
\begin{conjecture}
$$\sum{}^{(2)}(n-4,4)=8,~\sum{}^{(2)}(n-4,3,1)=4,~\sum{}^{(2)}(n-4,2,2)=8,~\sum{}^{(2)}(n-4,2,1,1)=8,$$
 and
$$\sum{}^{(2)}(n-4,1^4)=40.$$
This was checked for  $8\le n\le 10$.
\end{conjecture}



We summarize these conjectures with the evidence $ a\le n\le 10$.

\medskip

$\sum{}^{(2)}(n)=n$ ~~~~~~~~~~~~~~~~~~~$1\le n\le 10$


\medskip

$\sum{}^{(2)}(n-1,1)=2$~~~~~~~~~~~~$2\le n\le 10$


\medskip

$\sum{}^{(2)}(n-2,2)=4$~~~~~~~~~~~~$4\le n\le 10$

\medskip

$\sum{}^{(2)}(n-2,1^2)=4$~~~~~~~~~~~$4\le n\le 10$


\medskip

$\sum{}^{(2)}(n-3,3)=6$~~~~~~~~~~~~$6\le n\le 10$

\medskip

$\sum{}^{(2)}(n-3,2,1)=4$~~~~~~~~~~$6\le n\le 10$


\medskip

$\sum{}^{(2)}(n-3,1^3)=12$~~~~~~~~~~$6\le n\le 10$


\medskip

$\sum{}^{(2)}(n-4,4)=8$~~~~~~~~~~~~~$8\le n\le 10$

\medskip

$\sum{}^{(2)}(n-4,3,1)=4$~~~~~~~~~~~$8\le n\le 10$


\medskip

$\sum{}^{(2)}(n-4,2,2)=8$~~~~~~~~~~~$8\le n\le 10$

\medskip

$\sum{}^{(2)}(n-4,2,1^2)=8$~~~~~~~~~~$8\le n\le 10$


\medskip

$\sum{}^{(2)}(n-4,1^4)=40$~~~~~~~~~~~$8\le n\le 10$


%555555555555555555555555555555555555555555






