\documentclass[12pt]{article}
\usepackage{e-jc}
\usepackage{amsthm,amsmath,amssymb}

\newcommand{\doi}[1]{\href{http://dx.doi.org/#1}{\texttt{doi:#1}}}
\newcommand{\arxiv}[1]{\href{http://arxiv.org/abs/#1}{\texttt{arXiv:#1}}}

\newcommand{\sgn}{\operatorname{sgn}}
\newcommand{\LL}{\ell\ell}
\newcommand{\N}{\mathbb{N}}
\newcommand{\gen}[1]{\langle #1 \rangle}

% declare theorem-like environments
\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{fact}[theorem]{Fact}
\newtheorem{observation}[theorem]{Observation}
\newtheorem{claim}[theorem]{Claim}

\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{open}[theorem]{Open Problem}
\newtheorem{problem}[theorem]{Problem}
\newtheorem{question}[theorem]{Question}

\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}
\newtheorem{note}[theorem]{Note}

 %%%%%%%%%%%%%%%%%%

\title{\bf
Coincidences between characters \\
to hook partitions and 2-part partitions\\
on families arising from 2-regular classes
}
\author{Christine Bessenrodt\\
\small Institute for Algebra, Number Theory and Discrete Mathematics\\
\small Leibniz Universit\"at Hannover\\[-0.8ex]
\small Hannover, Germany\\
\small\tt bessen@math.uni-hannover.de}


% \date{\dateline{submission date}{acceptance date}\\
% \small Mathematics Subject Classifications: comma separated list of
% MSC codes available from http://www.ams.org/mathscinet/freeTools.html}

\date{\dateline{November 9, 2016}{}\\
\small Mathematics Subject Classifications: 20C30, 05E10}

\begin{document}
\maketitle

\begin{abstract}
Strongly refining results by Regev, Regev and Zeilberger,
we prove surprising coincidences between
characters to 2-part partitions of size $n$
and characters to hook partitions of size $n+2$
on two related families obtained by extending
2-regular conjugacy classes.

 \bigskip\noindent \textbf{Keywords:} Symmetric groups, characters,
hooks, 2-part partitions.
\end{abstract}



\section{Introduction}

In a recent paper,
Alon Regev, Amitai Regev and Doron Zeilberger
\cite{RRZ}
studied sums of squares of character values for the symmetric groups.
They compared on the one hand such a sum to characters where the labelling partitions
had a restricted number of rows, and on the other hand such a sum to
characters labelled by hook partitions; their values were considered on related
conjugacy classes with ``many'' fixed points, and
surprising coincidences between the sums of their squares were found.
In a subsequent paper \cite{RZ}, these results were greatly generalized to
further families of conjugacy classes.
The proofs  are based on intricate computations with difference
operators and constant term identities for character values.

We have to introduce some notation before stating the
details of these results and then present our strong refinements.
A partition of a number $n\in \N_0$
is an (unordered) multiset of nonnegative integers
summing to $n$,
often written as a weakly decreasing sequence and omitting trailing zeros;
the nonzero integers in the partition are its parts.
For $n=0$, the only partition is the empty partition, denoted $(0)$.
We also use exponential notation and write $i^m$ for $m$ parts~$i$
in a partition.
For a partition $\alpha$ and some positive integers $a,b,c,\ldots$,
we write $(\alpha,a,b,c,\ldots)$ for the partition having the parts of
$\alpha$ together with the parts $a,b,c,\ldots$.
%
It is wellknown that the irreducible complex characters
of the symmetric group $S_n$ are canonically labelled by the partitions of $n$;
we refer to \cite{JK} for background on this.
We denote the irreducible character to the partition $\lambda$ by
$[\lambda]$; for explicit partitions, the parantheses are omitted.
The value of the character
$[\lambda]$
on the conjugacy class of elements of cycle type $\mu$  is denoted by $[\lambda](\mu)$. For $n=0$, we set $[0](0)=1$.


Using the notation of \cite{RRZ}, we set
$$
\psi^{(2)}_n(\mu)= \sum_{j=0}^{\lfloor n/2 \rfloor} [n-j,j](\mu)^2
$$
and
$$
\phi^{(2)}_n(\mu)= \sum_{j=1}^{n} [j,1^{n-j}](\mu)^2 \:.
$$
In \cite{RRZ}, they observed (and proved) the {\em remarkable identity}
$$
\psi^{(2)}_n(31^{n-3})= \frac 12 \phi^{(2)}_{n+2}(321^{n-3})
$$
and stated: {\em It may be interesting to find a `natural'
reason for this `coincidence'.}

In a subsequent paper \cite{RZ}, Amitai Regev and Doron Zeilberger
greatly generalized the identity above.
We quote their result which gives a wealth of surprising relations between characters to hook partitions and 2-part partitions.
\begin{theorem}\label{thm:RZ}
Let $\mu_0$ be a partition with odd parts $a_1\ge a_2 \ge \cdots \ge a_s\ge 3$
and the parts $2,2^2,\ldots,2^{t}$ for some $t\ge 0$.
Let $\hat\mu_0$ be the partition with the same
odd parts $a_1\ge a_2 \ge \cdots \ge a_s\ge 3$
and the part $2^{t+1}$.
Then for every $n\ge m=|\mu_0|$ we have
$$
\psi^{(2)}_n(\mu_0, 1^{n-m})= \frac 12 \phi^{(2)}_{n+2}(\hat\mu_0, 1^{n-m})\:.
$$
\end{theorem}

Here, we will explain these results by showing that a strong refinement
of this relation is true: we have indeed coincidences between the character
values themselves not just the sum of squares of the values!
More precisely, we will show:
\begin{theorem}\label{thm:main}
Let $\alpha$ be a partition with odd parts only.
Let $\mu=(\alpha,2,2^2,\ldots,2^{t})$ for some $t\ge 0$, $n=|\mu|$.
Let $\hat\mu=(\alpha,2^{t+1})$.
Then for any $j \in \{0,1,\ldots, n-j\}$ we have
$$
[n-j,j](\mu)= [n+2-j,1^j](\hat\mu)\:.
$$
\end{theorem}

\bigskip

Theorem~\ref{thm:RZ} is easily implied by this result.
We explain this using the notation in the theorem above.
As $\hat\mu$ is the cycle type for a class of odd permutations, we have
$$[n+2-j,1^j](\hat\mu)= - [j+1,1^{n+1-j}](\hat\mu)\:.$$
Note that for odd $n=2k+1$ we have
$[n+2-(k+1),1^{k+1}](\hat\mu) = [k+2,1^{k+1}](\hat\mu)=0$.

Hence we obtain in any case, using Theorem~\ref{thm:main},
$$
\sum_{j=0}^{\lfloor n/2 \rfloor} [n-j,j](\mu)^2
=
\sum_{j=0}^{\lfloor n/2 \rfloor} [n+2-j,1^j](\hat\mu)^2
=
\sum_{j=\lfloor n/2 \rfloor +1}^{n+1} [n+2-j,1^j](\hat\mu)^2
$$
and hence Theorem~\ref{thm:RZ} follows.

\section{Preliminaries}

We want to use an observation from the 2-modular representation theory of
the symmetric groups; we refer to the books by James and Kerber \cite{J,JK} and Olsson's Lecture Notes \cite{JO-LN} for more on the background.
Here, this will not imply that we work at characteristic~2,
but that we consider the restriction of the characters to 2-regular elements, i.e., those whose cycle type is a partition with odd parts only.

\smallskip

For two characters $\chi,\psi$ of $S_n$,
we write $\chi \equiv \psi$ if the
characters $\chi,\psi$ coincide on all 2-regular elements.

\smallskip

A crucial tool is a relation between characters to hook partitions and 2-part partitions on 2-regular elements.
We recall this observation here (see \cite[p.93]{J}).

Take $x\ge y\ge 0$. Then by the Littlewood-Richardson rule we have
$$
([x] \times [y])\uparrow^{S_{x+y}}
=[x+y]+[x+y-1,1]+\ldots+[x,y]
$$
and
$$
([x] \times [1^y])\uparrow^{S_{x+y}}
=[x+1,1^{y-1}]+[x,1^y] \:.
$$
Note that for $y=0$ this is also correct by interpreting a character
to a non-partition like $(x+2,1^{-1})$ as zero.

Clearly, the characters $[y]$ and $[1^y]$
coincide on all 2-regular elements as these are even permutations.
Hence we deduce
$$
[x+1,1^{y-1}]+[x,1^y]
\equiv
[x+y]+[x+y-1,1]+\ldots+[x,y]\:.
$$
Still using our convention from above and
$$
[x+2,1^{y-2}]+[x+1,1^{y-1}]
\equiv
[x+y]+[x+y-1,1]+\ldots+[x+1,y-1]
$$
we obtain the crucial relation
\begin{eqnarray}\label{eq:hooks2part}
[x,y]
\equiv
[x,1^y]-[x+2,1^{y-2}]
\:.
\end{eqnarray}


\medskip

We need some further preliminaries on a variation of $\beta$-numbers;
for some of the following we refer to \cite{JO-LN} for more on $\beta$-numbers.

In general, any finite set $X\subset \N_0$ is a $\beta$-set.
For a partition $\lambda$ of length $\ell$, the first column hook lengths
$h_{i1}=\lambda_i+\ell-i$, $i=1,\ldots,\ell$,
form a $\beta$-set $X_\lambda$ for $\lambda$.
Conversely, to $X=\{x_1>x_2>\ldots > x_m\}$ we associate the partition
$$\pi(X)= (x_1-(m-1),x_2-(m-2),\ldots,x_{m-1}-1,x_m)$$
where trailing zeros are ignored.

For $r\in \N$, the $r$-shift of a $\beta$-set $X$ is  $X^{+r}=\{x+r\mid x\in X\}\cup \{r-1,\ldots,0\}$.
Note that all shifts of $X$ have the same
associated partition; indeed, any partition corresponds to
a shift class of $\beta$-sets.

Considering $\beta$-sets instead of the partitions themselves
is useful for the process of hook removal, i.e.,
removing a rim hook belonging to a box in the diagram
of a partition $\lambda$ (or taking out the hook corresponding to a box and pushing the two remaining pieces together,
into partition shape).
Indeed, the removal of an  $h$-hook (i.e., a hook of length $h$) from $\lambda$ corresponds
to subtracting $h$ from one of the numbers $x\ge h$ in its $\beta$-set
$X_\lambda$ such that $x-h\not\in X_\lambda$ (see \cite{JO-LN}).

As we want to use $\beta$-numbers in the context of the Murnaghan-Nakayama formula,
we also want to keep track of the sign of the leg lengths of the hooks to be removed.
Instead of writing this out at each step, we will use a slight
variation of $\beta$-sets.
We will only use this here in the context of two-row partitions.

An ordered $\beta$-set $Z=((z_1,\ldots,z_m))$ is a sequence such that
the corresponding set is a $\beta$-set $X$ of size $m$;
the associated partition is $\pi(Z)=\pi(X)$.
The associated sign of the ordered $\beta$-set $Z$ is defined to be the sign of the permutation sorting the entries into decreasing order.
Then, when we start from the ordered version of $X_\lambda=\{x_1>x_2>\ldots > x_m\}$,
this being denoted by $Z_\lambda=((x_1,\ldots,x_m))$,
the subtraction of $h$ from $x_i$ (say) is recorded at position~$i$,
without reordering, and we obtain for the removal of the corresponding
hook $H$ from $\lambda$:
$Z=((x_1,\ldots,x_i-h,\ldots,x_m))$, with $\pi(Z)=\lambda/H$.
Denoting the leg length  of the hook $H$ by $\LL(H)$,
note that $(-1)^{\LL(H)}$ is the sign of $Z$.

We extend the notation for ordered $\beta$-sets a little further
when the sequences are of length~2,
and we define associated virtual characters.
We allow also formal expressions $((x,y))$ with $x$ or $y$ negative,
or with $x=y$; in these cases, we don't have associated partitions
and we define the associated virtual characters to be zero.
When the entries are different and nonnegative, we call the
ordered $\beta$-set proper.
In this case,
recalling how $\beta$-sets are associated with partitions, and keeping in mind that the ordered $\beta$-set also records a sign,
we are led to associate
virtual characters to ordered $\beta$-sets as follows:
$$
\text{the virtual character  to $((x,y))$ is } \quad
[[x,y]]= \left\{
\begin{array}{rl}
[x-1,y] & \text{if } x>y\ge 0\\
-[y-1,x] & \text{if } y>x\ge 0\\
\end{array}
\right. \:.
$$
By the relation observed in~(\ref{eq:hooks2part}),
we deduce for the restriction on 2-regular elements:
$$[[x,y]]\equiv
\left\{
\begin{array}{rl}
[x-1,1^y]-[x+1,1^{y-2}], & \text{if } x>y\ge 0\\
\- [y+1,1^{x-2}]-[y-1,1^x], & \text{if } y>x\ge 0\\
\end{array}
\right.
\:.
$$
The characters to a partition and its conjugate
have the same values on 2-regular elements,
thus in the second case
$$
[y+1,1^{x-2}]-[y-1,1^x] \equiv [x-1,1^{y}]-[x+1,1^{y-2}] \:,
$$
and hence for any nonnegative integers $x\neq y$ we obtain
\begin{eqnarray}\label{eq:hooks2partgen}
[[x,y]]\equiv
[x-1,1^y]-[x+1,1^{y-2}]
\:.
\end{eqnarray}
In fact, also for $x=y$ both sides are zero;
if $x$ or $y$ are negative, then also by our conventions both
sides are zero.
Hence relation (\ref{eq:hooks2partgen}) holds for all $x,y$.

Note in particular that when $x\in \{0,1\}$,
the positive term on the right hand side of~(\ref{eq:hooks2partgen}) disappears,
and when $y\in \{0,1\}$, then the negative term disappears, i.e.,
\begin{eqnarray*}\label{eq:hooks2partgen-special}
[[x,y]]\equiv
\left\{
\begin{array}{rl}
-[x+1,1^{y-2}] & \text{if } x\in \{0,1\}\\
\-[x-1,1^y] & \text{if } y\in \{0,1\}
\end{array}
\right.
\:.
\end{eqnarray*}

\section{Proof of Theorem~\ref{thm:main}}

We recall the set-up of the theorem.
Let $\alpha$ be a partition with odd parts only,
let $\mu=(\alpha,2,2^2,\ldots,2^{t})$ for some $t\ge 0$,
and let $\hat\mu=(\alpha,2^{t+1})$.
Set $n=|\mu|$. Then for any $j \in \{0,1,\ldots, \lfloor \frac n2 \rfloor\}$ we want
to show that
$$
[n-j,j](\mu)= [n+2-j,1^j](\hat\mu)\:.
$$

Applying the Murnaghan-Nakayama formula $t$ times we have
$$
[n-j,j](\mu)=
\sum_{H_1} \sum_{H_2} \cdots \sum_{H_t}
(-1)^{\sum_{j=1}^t \LL(H_j)}[(n-j,j)\setminus H_t\cdots \setminus H_2 \setminus H_1] (\alpha)
$$
where the $i^{\text{th}}$ sum
runs over the $2^i$-hooks $H_i$ of the partition  \hbox{$(n-j,j)\setminus H_t\cdots \setminus H_{i+1}$}, for
$i\in \{1,\ldots,t\}$,
computing this from the innermost to the outermost sum, starting with $2^t$-hooks $H_t$ of $(n-j,j)$.

Transferring this into the language of ordered $\beta$-sets and keeping our conventions on the associated virtual characters in mind, this becomes
\begin{eqnarray}\label{eq:value}
[n-j,j](\mu)=
\sum_{I\subseteq \{1,\ldots,t\}}
[[n+1-j-\sum_{i\in I} 2^i,j-\sum_{i\in I^c} 2^i]] (\alpha)
\end{eqnarray}
where $I^c=\{1,\ldots,t\}\setminus I$.
We note here that clearly the sign of every proper ordered $\beta$-set
$$((n+1-j-\sum_{i\in I} 2^i,j-\sum_{i\in I^c} 2^i))$$
is equal to the sign $(-1)^{\sum_{j=1}^t \LL(H_j)}$ coming from the removal
of the corresponding $t$ hooks.

Furthermore, we note that if $2^t,\ldots, 2^k$ have been subtracted from
$((n+1-j,j))$ and an ordered $\beta$-set $((x,x))$ is obtained
(which gives a zero character by definition), then continuing with further
subtractions will always produce
pairs of ordered $\beta$-sets $((x-a,x-b)), ((x-b,x-a))$ with cancelling pairs of
characters, so the total
contribution at the final level $t$ from such an intermediate term $((x,x))$  will
still be zero.

The $2^t$ ordered $\beta$-set labels appearing in the sum above are easily
determined, as any even number $2k \in\{ 0, \ldots , 2^{t+1}-2\}$ can uniquely be
written as
$2k=\sum_{i\in I} 2^i$ for a suitable subset
$I\subseteq \{1,\ldots,t\}$, and then
$\sum_{i\in I^c} 2^i = 2^{t+1}-2-2k$.
So with $m=2^{t+1}-2$ and $((u,v))=((n+1-j,j))$, in the sum above all labels
of the form
$((u-2k,v-m+2k))$,
$0 \le k \le 2^t-1$,
appear.
Note that, of course, some of these labels will give a zero character contribution.

Recalling that we want to evaluate the virtual characters appearing in the sum
in equation~(\ref{eq:value}) at the 2-regular element
of cycle type $\alpha$, we can then
apply relation~(\ref{eq:hooks2partgen}).

We discuss first the generic case
where we assume that $u=n+1-j$ and $v=j$ are both of size
at least $m=2^{t+1}-2$.
Here we obtain for the virtual character on the right hand side of
equation~(\ref{eq:value}):
\begin{eqnarray*}
\lefteqn{
\displaystyle
\sum_{I\subseteq \{1,\ldots,t\}}
[[n+1-j-\sum_{i\in I} 2^i,j-\sum_{i\in I^c} 2^i]]
} \\
&=&
\displaystyle
\sum_{k=0}^{2^t-1}
[[u-2k,v-m+2k]]
\\[7pt]
&\equiv &
\displaystyle
\sum_{k=0}^{2^t-1}
([u-2k-1,1^{v-m+2k}]-[u-2k+1,1^{v-m+2k-2}])
\\[7pt]
&=&
[u-m-1,1^{v}] - [u+1,1^{v-m-2}]
\\[7pt]
&=&
[n-m-j,1^{j}] - [n+2-j,1^{j-m-2}] \:.
\end{eqnarray*}
We point out that the telescoping above works because the structure of the set of labels fits well together with relation~(\ref{eq:hooks2part}); this is special for the
choice of the 2-powers in Theorem~\ref{thm:main}.

Remembering that $[\rho]=0$ if $\rho$ is not a partition,
we thus arrive at
$$
\begin{array}{rcl}
[n-j,j](\mu)
&=&
[n-m-j,1^{j}](\alpha)
- [n+2-j,1^{j-m-2}](\alpha)
\\[7pt]
&=&
[n+2-j,1^j](\alpha,2^{t+1}) =[n+2-j,1^j](\hat\mu)
\:.
\end{array}
$$
Thus the claim is proved in the generic case.

Now in the non-generic case,
first assume that $n+1-j=u< m=2^{t+1}-2$, say $u=\epsilon_u+2k_u$,
for some $0\le k_u<2^t-1$ and $\epsilon_u \in \{0,1\}$;
note that $u+v=n+1 > m$, so then $v> m-2k_u$.
Then the last possibly nonzero contribution in the sum comes
from the label $((\epsilon_u,v-m+2k_u))$,
for $k=k_u$.
As we have seen above, for this label we only get the negative
hook contribution which cancels with the previous term in the sum as before,
as long as such a term exists;
the critical case with no cancellation occurs only when
$v-m+2k_u=\epsilon_v\in \{0,1\}$.
Note that $v=j \leq n-j =u-1< m$, so an analogous symmetric
argument for the first possibly nonzero contribution in the sum
tells us that in the noncritical cases or in the critical case
with $\epsilon_u=\epsilon_v$,
we have
$$
\begin{array}{rcl}
[n-j,j](\mu)
=0=
[n+2-j,1^j](\alpha,2^{t+1})
\end{array}
\:.
$$
We still have to consider the critical case where
$v-m+2k_u=\epsilon_v\neq \epsilon_u$.
Here, we have only one nonzero contribution at level $t$,
from the ordered $\beta$-set $((\epsilon_u,\epsilon_v))$,
namely, $[0]$ when the $\beta$-set is $((1,0))$, i.e.,
$u=n+1-j$ is odd, and $-[0]$ when it is $((0,1))$, i.e.,
$u=n+1-j$ is even.
Furthermore, in the critical case we have
$2^{t+1}-2 =u+v-1=n$;
thus $\alpha=\emptyset$ and we obtain
\begin{eqnarray*}
[n-j,j](\mu)&=&[n-j,j](2,2^2,\ldots,2^t)\\[7pt]
&=&(-1)^{n-j}=(-1)^j\\[7pt]
&=&[n+2-j,1^j](2^{t+1})
=[n+2-j,1^j](\hat\mu)\:.
\end{eqnarray*}


Finally, if we are in a non-generic case
with $u \ge m=2^{t+1}-2$, but $j=v< m$, then the last term
of the virtual character
coming from the sum is still $[n-m-j,1^j]$
as in the generic case, but arguing as above
there will not be a negative contribution at the start, so
$$
\begin{array}{rcl}
[n-j,j](\mu)
=[n-j-m,1^{j}](\alpha) =
[n+2-j,1^j](\alpha,2^{t+1})
=[n+2-j,1^j](\hat\mu)\:.
\end{array}
$$
Hence we are now done in all cases.  $\Box$


\bigskip

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection*{Acknowledgements}
Thanks go to the referee for helpful suggestions and comments.


\begin{thebibliography}{10}

\bibitem{J}
G.~James,
\newblock The representation theory of the symmetric groups.
\newblock Springer Lecture Notes Math. 682 (1978).


\bibitem{JK}
G.~James, A.~Kerber,
\newblock The representation theory of the symmetric group.
Addison-Wesley, London, 1981.

\bibitem{JO-LN}
J.~B.~Olsson,
\newblock Combinatorics and representations of finite groups.
\newblock {\em Vorlesungen aus dem FB Mathematik der Univ. Essen}, Heft 20, 1993.
%  ({\it This book is freely available at Olsson's homepage })


\bibitem{RRZ}
Alon Regev, Amitai Regev, D.~Zeilberger,
\newblock Identities in character tables of $S_n$.
\newblock {\em Journal of Difference Equations and Applications},
22:2 (2016), 272--279.

\bibitem{RZ}
Amitai Regev, D.\ Zeilberger,
\newblock Surprising relations between sums-of-squares of characters
of the symmetric group over two-rowed shapes and over hook shapes.
\newblock {\em S\'eminaire Lotharingien de Combinatoire} 75 (2016), B75c.

\end{thebibliography}


\end{document}