%% if you are submitting an initial manuscript then you should have submission as an option here
%% if you are submitting a revised manuscript then you should have revision as an option here
%% otherwise options taken by the article class will be accepted
\documentclass[final]{FPSAC2022}
%% but DO NOT pass any options (or change anything else anywhere) which alters page size / layout / font size etc

%% note that the class file already loads {amsmath, amsthm, amssymb}
%\documentclass[11pt]{amsart}
%\usepackage[latin1]{inputenc}
%\usepackage{amsmath}
%\usepackage{fancyhdr}
%\usepackage{amsfonts}
%\usepackage{amssymb,amsbsy,amsthm}
%\usepackage{hyperref}
\usepackage{color}
%\usepackage{authblk}
%\usepackage{blkarray}
%\usepackage{array}
%\usepackage{multirow}
%\usepackage[T1]{fontenc}
\usepackage[enableskew,vcentermath]{youngtab}
%\usepackage{ytableau}
%\ytableausetup{notabloids}
%\ytableausetup{centertableaux}
\usepackage{tikz}

\newcommand\coolover[2]{\mathrlap{\smash{\overbrace{\phantom{%
					\begin{matrix} #2 \end{matrix}}}^{\mbox{$#1$}}}}#2}

\newcommand\coolunder[2]{\mathrlap{\smash{\underbrace{\phantom{%
					\begin{matrix} #2 \end{matrix}}}_{\mbox{$#1$}}}}#2}

\newcommand\coolleftbrace[2]{%
	#1\left\{\vphantom{\begin{matrix} #2 \end{matrix}}\right.}

\newcommand\coolrightbrace[2]{%
	\left.\vphantom{\begin{matrix} #2 \end{matrix}}\right\}#1}

\newcommand{\Q}{\mathcal Q}
\newcommand{\f}{\mathcal F}
\newcommand{\TTT}{\mathcal T}
\newcommand{\symm}{S}
\newcommand{\C}{\mathcal C}
\newcommand{\A}{\mathcal A}

\def\n{\mathcal{N}}
\def\m#1{\mathcal{N}_{#1}}
\def\p{(\textnormal{mod}\ p)}
\def\x#1{(\textnormal{mod}\ x^{#1})}
\def\F{\mathbb{F}_{p}}
\def\b{\overline{n}}

\DeclareMathOperator\Des{Des}
\DeclareMathOperator\des{des}
\DeclareMathOperator\cDes{cDes}
\DeclareMathOperator\CDes{CDes}
\DeclareMathOperator\maj{maj}
%\DeclareMathOperator\cdes{cdes}
%\DeclareMathOperator\Irr{Irr}
\DeclareMathOperator\sgn{sgn}
\def\CC{{\mathbb C}}
\def\KK{{\mathbb K}}
\def\LL{{\mathbb L}}
\def\NN{{\mathbb N}}
\def\PP{{\mathbb P}}
\def\QQ{{\mathbb Q}}
\def\ZZ{{\mathbb Z}}
\def\RR{{\mathbb R}}
\def\kk{{\mathbf k}}

\newcommand{\cyc}{{\operatorname{cyc}}}

\newcommand\comp[2]{\alpha{(#2,#1)}}
\newcommand\ccomp[2]{\alpha^\cyc{(#2,#1)}}

\newcommand{\cs}{\widetilde s}

\newcommand{\ch}{{\operatorname{ch}}}

%\newtheorem*{nms}{Conjecture}
%\newtheorem{thm}{Theorem}[section]
%\newtheorem{obs}{Observation}
%\newtheorem{cl}{Claim}{thm}
%\newtheorem*{prob}{Problem}
%\newtheorem{case}{\color{red}Case}
%\newtheorem{lem}[thm]{Lemma}
%\newtheorem*{gno}{Generalization of the observations}
%\newtheorem{defn}{Definition}%[section]
%\newtheorem*{ques}{Question}
%\newtheorem*{aim}{Aim}
%\newtheorem*{prf}{Proof}
%\newtheorem{cor}[thm]{Corollary}
%\newtheorem*{nota}{Notation}
%\theoremstyle{definition}
%\newtheorem{rem}{Remark}

\def\SYT{{\rm SYT}}

\theoremstyle{plain}
%\newtheorem{thm}{Theorem}[section]
\newtheorem{theorem}{Theorem}[section]
\newtheorem{proposition}[theorem]{Proposition}
%\newtheorem{prop}[thm]{Proposition}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{problem}[theorem]{Problem}
\newtheorem{question}[theorem]{Question}
\newtheorem{observation}[theorem]{Observation}
\newtheorem{obs}[theorem]{Observation}
\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{defn}[theorem]{Definition}
\theoremstyle{remark}
\newtheorem{example}[theorem]{Example}
\newtheorem{examples}[theorem]{Examples}
\newtheorem{remark}[theorem]{Remark}

\newcommand{\card}[1]{\ensuremath{\left|#1\right|}}

\newcommand{\todo}[1]{\vspace{5 mm}\par \noindent
	\marginpar{\textsc{ToDo}} \framebox{\begin{minipage}[c]{0.9
				\textwidth}
			#1 \end{minipage}}\vspace{5 mm}\par}
			
\renewcommand{\labelenumi}{\arabic{enumi}.}

\usepackage[backend=bibtex]{biblatex}
\addbibresource{AHR_Lie_FPSAC22_bibfile.bib}

%\begin{document}
	
\title[Higher Lie Characters and Cyclic Descents on Conjugacy Classes]
{Higher Lie Characters and Cyclic Descent Extension on Conjugacy Classes}

%% define your authors in the usual way
%% use \addressmark{1}, \addressmark{2} etc for the institutions, and use \thanks{} for contact details
%\author[Optional shorter names]{Longer names me\thanks{\href{mailto:hello@world.c}{hello@world.c}. Longer names me was partially supported by Grant 2017.11.14.$\partial$\;supp.}\addressmark{1}, \and you\addressmark{2}}

%% then use \addressmark to match authors to institutions here
%\address{\addressmark{1}Department of This, University of That, There \\ \addressmark{2}School of Something, University of Something Else, Somewhere}

\author[R.~M.~Adin, P.~Heged\"us, and Y.~Roichman]{%
	Ron M.\ Adin\thanks{\href{mailto:radin@math.biu.ac.il}{radin@math.biu.ac.il}. 
	Partially supported by the Israel Science Foundation grant no.\ 1970/18 and by an MIT-Israel MISTI grant.}\addressmark{1}, 
%
	P\'al Heged\"us\thanks{\href{mailto:hegedus.pal@renyi.hu}{hegedus.pal@renyi.hu}. 
	Partially supported by Hungarian National Research, Development and Innovation Office (NKFIH) grant no.\ 138596 and by a Bar-Ilan University visiting grant.}\addressmark{2}, \and 
%	
	Yuval Roichman\thanks{\href{mailto:yuvalr@math.biu.ac.il}{yuvalr@math.biu.ac.il}. 
	Partially supported by the Israel Science Foundation grant no.\ 1970/18 and by an MIT-Israel MISTI grant.}\addressmark{3}
}

\address{%
	\addressmark{1}%
	Department of Mathematics, Bar-Ilan University, 
	Ramat-Gan 52900, Israel \\ 
	\addressmark{2}%
	R\'enyi Alfr\'ed Institute of Mathematics, Re\'altanoda utca 13-15, H-1053, Budapest, Hungary
	\addressmark{2}%
	Department of Mathematics, Bar-Ilan University, 
	Ramat-Gan 52900, Israel
}


%{\bf Abstract.} 	
\abstract{
A now-classical cyclic extension of the descent set of a permutation has been introduced by Klyachko and Cellini.
Following a recent axiomatic approach to this notion, it is natural to ask which sets of permutations admit such a (not necessarily classical) extension. 
The main result of this paper is
a complete answer in the case of conjugacy classes of permutations.
It is shown that the conjugacy class of cycle type $\lambda$ 
has such an extension if and only if 
$\lambda$ is not of the form $(r^s)$ for some square-free $r$.
The proof involves a detailed study of hook constituents in
higher Lie characters.}
%\end{abstract}

%{\bf Keywords}: 
\keywords{cyclic descent, conjugacy class, symmetric group, %hook constituent,
higher Lie character}
	
%% put the date of submission here
\received{November 25, 2021}

%% leave this blank until submitting a revised version
\revised{March 30, 2022}

%\date{Nov 4, 2021}
		
%\maketitle	

\begin{document}

\maketitle
	

%{\bf MSC}: 05E10, 05E05, 20B30, 20C30
	

%\tableofcontents
	
	
\section{Introduction}
%%%%%%%%%%%%%%%%%%%%%%

%\subsection{Background and main result}%\ \\

	Permutations, as well as standard Young tableaux, are equipped with a well-established notion of descent
	set. A cyclic extension of this concept was 
	%Cyclic descents were 
	introduced in the study of Lie algebras~\cite{Klyachko} and 
	descent algebras~\cite{Cellini}. 
	Surprising connections of the cyclic descent notion to a variety of mathematical areas were found later.
	%see \textit{e.g.} for 

\smallskip

The {\em descent set} of a permutation $\pi = [\pi_1, \ldots, \pi_n]$ in the symmetric group $\symm_n$ on $n$ letters is
\[
%{\rm{DES}}
\Des(\pi) := \{1 \le i \le n-1 \,:\, \pi_i > \pi_{i+1} \}
\quad \subseteq [n-1],
\]
where $[m]:=\{1,2,\ldots,m\}$.  
%For example, $\Des([2,1,4,5,3])=\{1,4\}$. 
%The notion of descent set, for permutations as well as for standard Young tableaux, is classical. 
Cellini~\cite{Cellini} introduced a natural notion of {\em cyclic descent set}: 
%\begin{equation}\label{e.cellini}
\[
%\CDes
\CDes(\pi) := \{1 \leq i \leq n \,:\, \pi_i > \pi_{i+1} \}
\quad \subseteq [n],
\]
%\end{equation}
with the convention $\pi_{n+1}:=\pi_1$.  
%For example, $\CDes([2,1,4,5,3])=\{1,4,5\}$.
The more restricted notion of cyclic descent number had been used previously by Klyachko~\cite{Klyachko}.
This cyclic descent set was further studied by Dilks, Petersen and Stembridge~\cite{DPS} and others.
%It has the following important properties.
%Consider the %two 
%$\ZZ$-action, on $\symm_n$ %and on the power set of $[n]$, 
%in which the generator $p$ of $\ZZ$ acts by 
%\[
%\begin{array}{rcl}
%[\pi_1,\pi_2,\ldots,\pi_{n-1},\pi_n]&\overset{p}{\longmapsto}&
%[\pi_n,\pi_1,\pi_2,\ldots,\pi_{n-1}]. %\\
%\{i_1,\ldots,i_k\}&\overset{p}{\longmapsto}&\{i_1+1,\ldots,i_k+1\} \bmod{n}.
%\end{array}
%\]

%\smallskip
	
There exists an established notion of descent set for standard Young tableaux (SYT),
%		There is an established notion of descent set for $\SYT(\lambda/\mu)$
		%\begin{equation}\label{def:Des_SYT}
		\[
		\Des(T) := \{1 \le i \le n-1 \,:\,
		i+1 \text{ appears in a lower row of }T\text{ than }i\}, 
		\]
		%\end{equation} 
		but it has no obvious cyclic analogue. 
In a breakthrough work, Rhoades~\cite{Rhoades} defined a notion of cyclic descent set for standard Young tableaux of rectangular shape.
%\todo{Add a pa regarding importance of cyclic descent notion}
The properties common to Cellini's definition (for permutations) and Rhoades' construction (for SYT) appeared in other combinatorial settings as well~\cite{PPR, Pechenik, ER}. %, AER}.
This led to an abstract definition~\cite{ARR}, as follows.
%
%A generalization of this notion to arbitrary combinatorial sets, which carry a descent set map, was introduced in~\cite{ARR}.
%
%To extend the cyclic descent set notion to standard Young tableaux and other combinatorial sets one needs the axiomatic definition.	
%
	
\begin{definition}\label{def:cDes}\cite{ARR}
Let $\TTT$ be a finite set, equipped with a map (called {\em descent map}) %is any map
$\Des \colon \TTT \longrightarrow 2^{[n-1]}$. 
Let ${\rm sh} \colon 2^{[n]} \longrightarrow 2^{[n]}$ be the mapping on subsets of $[n]$ induced by the cyclic shift $i \mapsto i + 1 \pmod n$ of elements $i \in [n]$.
A {\em cyclic extension} of $\Des$ is
a pair $(\cDes,p)$, where 
$\cDes \colon \TTT \longrightarrow 2^{[n]}$ is a map 
and $p \colon \TTT \longrightarrow \TTT$ is a bijection,
satisfying the following axioms:  for all $T$ in  $\TTT$,
\[
\begin{array}{rl}
\text{(extension)}   & \cDes(T) \cap [n-1] = \Des(T),\\
\text{(equivariance)}& \cDes(p(T))  = {\rm sh}(\cDes(T)),\\
\text{(non-Escher)}  & \varnothing \subsetneq \cDes(T) \subsetneq [n].\\
\end{array}
\]
\end{definition}
	
%Let us begin by formalizing the concept of a cyclic extension.

	
The term ``non-Escher'' refers to M.\ C.\ Escher's drawing ``Ascending and Descending'', which illustrates the impossibility
of the cases $\CDes(\pi) = \varnothing$ and $\CDes(\pi) = [n]$ for permutations $\pi \in S_n$.

%\begin{remark}
		
		For connections of cyclic descents to 
		Kazhdan--Lusztig theory see~\cite{Rhoades}; for topological aspects and connections to the  
		Steinberg torus see~\cite{DPS}; for twisted Sch\"utzenberger promotion see~\cite{Rhoades, Huang}; for cyclic quasi-symmetric functions and Schur-positivity see~\cite{AGRR};	for Postnikov's toric Schur functions see~\cite{ARR}.
		The goal of this paper is to determine which conjugacy classes of the symmetric group carry a cyclic descent extension.
%\end{remark}

\bigskip
	
Cellini's cyclic descent set, denoted $\CDes$, is a special case of a cyclic descent extension, denoted in general $\cDes$, as attested by the following observation. 
		
\begin{observation}
Let $\Des$ and $\CDes$ denote the classical descent set and Cellini's cyclic descent set on permutations, respectively.
Let $p \colon S_n \rightarrow S_n$ be the rotation 
\[
\begin{array}{rcl}
[\pi_1,\pi_2,\ldots,\pi_{n-1},\pi_n]&\overset{p}{\longmapsto}&
[\pi_n,\pi_1,\pi_2,\ldots,\pi_{n-1}]. %\\
%\{i_1,\ldots,i_k\}&\overset{p}{\longmapsto}&\{i_1+1,\ldots,i_k+1\} \bmod{n}.
\end{array}
\]
Then the pair $(\CDes,p)$ is a cyclic descent extension  of $\Des$  %$\rm{DES}$ 
on $S_n$ in the sense of Definition~\ref{def:cDes}.
\end{observation}
	
	%See also~\cite{???}.
%\smallskip

Unlike the full symmetric group, for many conjugacy classes,   
%the image of Cellini's cyclic descent map is not closed under cyclic rotation modulo $n$, hence cannot be used to prove the existence of a cyclic descent extension;
Cellini's definition does not provide a cyclic extension.
%, see Section~\ref{sec:Cellini} below.

%\begin{proposition}
%	For every conjugacy class of $k$-cycles, except of $2$-cycles in $S_3$ and $3$-cycles in $S_4$, Cellini's cyclic descent map 
%	is not is closed under cyclic rotation modulo $n$.
%\end{proposition}
	


\begin{example}
%\todo{Insert example(s)}
Consider the conjugacy class of 4-cycles in $S_4$,
\[
\C_{(4)}=\{2341, 2413, 3142, 3421, 4123, 4312\}.
\]
Cellini's cyclic descent sets are
\[
\{3\}, \{2,4\}, \{1,3\}, \{2,3\}, \{1\}, \{1,2\},
\]
respectively; this family is not closed under cyclic rotation.
On the other hand, redefining the cyclic descent sets to be
\[
\cDes(2341)=\{3,4\},\ \cDes(2413)=\{2,4\},
\  \cDes(3142)=\{1,3\}, 
\]
\[
\cDes(3421)=\{2,3\},\ \cDes(4123)=\{1,4\},\ \cDes(4312)=\{1,2\}
\]
and defining the map $p$ by
\[
2341 \rightarrow 4123 \rightarrow 4312 \rightarrow 3421 \rightarrow 2341
\]
and
\[
3142 \rightarrow 2413 \rightarrow 3142,
\]
the pair $(\cDes,p)$ does determine a cyclic extension of $\Des$ on this conjugacy class.
\end{example}

	

	
	
The goal of this paper is to show that most conjugacy classes in $S_n$ carry a cyclic descent extension.
%	characterize the conjugacy classes in the symmetric group $S_n$, which carry a cyclic descent extension. 
%Our main result is the following full characterization. 
In fact, we obtain a full characterization.

\smallskip

Recall that an integer is \emph{square-free} if no prime square divides it; in particular, $1$ is square-free. Our main result is 
%\subsection{Main Results}\ \\
	
\begin{theorem}\label{thm:main}
%For a partition $\lambda$ of $n$ l
Let $\lambda$ be a partition of $n$, and let
$\C_\lambda \subseteq S_n$ be the corresponding conjugacy class. % of cycle type $\lambda$.
The descent map %{\rm{DES}}  
$\Des$ 
%\todo{Sh: This should be `Des' as in its definition on top of p2.}
on $\C_\lambda$  has a cyclic extension $(\cDes,p)$ if and only if 
%There exists a cyclic descent extension on $\C_\lambda$ if and only if 
$\lambda$ is not of the form $(r^s)$ for some square-free $r$.
\end{theorem}
	
%\medskip
	
%\todo{Suggestion: The exceptional conjugacy classes $\lambda = (r^s)$ for $r$ square-free are henceforth called \emph{stretched}. In their exceptional property they correspond to the connected ribbons of Theorem~\ref{conj1}.}

The proof of Theorem~\ref{thm:main} is non-constructive and   
%applies a
%%a %cyclic analogue of a
%remarkable theorem of  Gessel and Reutenauer
%%~\cite[Theorem 2.1]{GR}, %  Theorem~\ref{thm:GR}
%%\cite[Theorem 2.1]{GR}, 
%which describes the fiber sizes of the descent set map on conjugacy classes as scalar products %of characters 
%%symmetric functions
%(Theorem~\ref{thm:GR} below), and 
involves a detailed study of the hook constituents in higher Lie characters.
In the rest of this extended abstract we describe the proof method. For 
a detailed full version see~\cite{AHR}.


\acknowledgements{
%The second author is grateful for the hospitality of Bar-Ilan University during his Sabbatical leave.
Special thanks are due to Jan Saxl, whose personality influenced the development of this paper. % in many ways. 
%; in particular, the paper is inspired by the  
%ingenious use of a higher Lie character in~\cite{Saxletal}.
Thanks also %to Ron Adin %, Jonathan Bloom  %and Sergi Elizalde 
%for extensive discussions and 
%Thanks also 
to Eli Bagno, Jonathan Bloom, Sergi Elizalde, 
Vic Reiner, Richard Stanley, Sheila Sundaram and Josh Swanson for their comments.
}


\section{Higher Lie characters} 

%\todo{Recall definition of wreath product $\ZZ_r\wr S_n$ and its basic representation theory}

%\begin{definition}\label{def:higher}
For a partition $\lambda$ of $n$, let $\C_\lambda$ be the conjugacy class consisting of all the permutations in $S_n$ of cycle type $\lambda$,
and let $\chi^\lambda$ denote the irreducible $S_n$-character corresponding to $\lambda$.
Let $Z_\lambda$ be the centralizer of a permutation in $\C_\lambda$ (defined up to conjugacy). 
If $k_i$ denotes the number of parts of $\lambda$ equal to $i$, then $Z_\lambda$ is isomorphic to the direct	product $\times_{i=1}^n \ZZ_i\wr S_{k_i}$.
Here and in the rest of the paper $\ZZ_i$ denotes the cyclic group of order $i$.
%Consider the following linear character of $Z_\lambda$:
%denoted by $\omega$
	
%	\begin{definition}\label{def:psi}
For each $i$, let $\omega_i$ be the linear character on $\ZZ_i\wr S_{k_i}$ indexed by the
$i$-tuple of partitions $(\emptyset, (k_i), \emptyset,
\dots,\emptyset)$. 
In other words, letting $\zeta$ be a primitive irreducible character on the cyclic group $\ZZ_i$, extend it to the wreath product $\ZZ_i\wr S_{k_i}$ so that it is homogeneous on the base subgroup $\ZZ_i^{k_i}$ and trivial on the wreathing subgroup $S_{k_i}$. Denote this extension by $\omega_i$.
Now let
\[
\omega^\lambda := \bigotimes_{i=1}^n \omega_i,
\]
a linear character on $Z_\lambda$. 
Define the corresponding {\em higher Lie character} to be the induced character
\[
\psi^\lambda := \omega^\lambda\uparrow_{Z_\lambda}^{S_n}.
\]
%\end{definition}

The study of higher Lie %module/
characters can be traced back %essentially 
to Schur~\cite{schur}. % and Thrall~\cite{thrall}. 
An old problem of Thrall~\cite{thrall} 
%can be recast, using Gessel's {\em necklace bijection} \cite{Gessel-Reutenauer}, as follows; 
is to provide an explicit combinatorial interpretation of the 
%	The 
multiplicities of the irreducible characters in the higher Lie character,
%were described combinatorially,
see also~\cite[Exercise 7.89(i)]{EC2}.
Only partial results are known: the case $\lambda = (n)$ was solved by Kra\'{s}kiewicz and Weyman~\cite{KraskiewiczWeyman};
D\'esarm\'enien and Wachs~\cite{DesarmenienWachs} resolved a coarser version of Thrall's problem %, with this explicit expansion
for the sum of higher Lie characters over all  %fine
derangements, see also~\cite{ReinerWebb}. 
The best result so far is
Schocker's expansion~\cite[Theorem~3.1]{schocker}, which however involves signs and rational coefficients. 
For recent discussions see, \textit{e.g.}, \cite{ %Reiner, 
	AS, Sundaram}.

A remarkable theorem of  Gessel and Reutenauer~\cite[Theorem 2.1]{GR} 
%~\cite[Theorem 2.1]{GR}, %  Theorem~\ref{thm:GR}
%%\cite[Theorem 2.1]{GR}, 
applies higher Lie characters to describe the fiber sizes of the descent set map on conjugacy classes.  
%as scalar products of character
%As a result, 
It follows that 
higher Lie characters can be used to prove the existence of cyclic descent extensions 
as explained below. 


%	Partial results were given by Kraskiewicz and Weyman~\cite{KraskiewiczWeyman}
%by M.\ Schocker~\cite[Theorem~3.1]{schocker}.
	
%\bigskip

%A remarkable theorem of  Gessel and Reutenauer~\cite[Theorem 2.1]{GR}
%%~\cite[Theorem 2.1]{GR}, %  Theorem~\ref{thm:GR}
%%\cite[Theorem 2.1]{GR}, 
%describes the fiber sizes of the descent set map on conjugacy classes 
%as scalar products of characters, as follows:
%%	using higher Lie characters with the Frobenius image of ribbon Schur function.
%%Gessel and Reutenauer~\cite{GR} proved that the fiber sizes of the descent map 
%%over conjugacy classes
%%satisfy
%%may be described using higher Lie characters as follows.
%\[
%|\{\pi \in \C_\lambda :\ \Des(\pi)=J\}|
%= \langle \psi^\lambda, \chi^J \rangle
%\qquad (\text{for all } \lambda \vdash n,\, J \subseteq [n-1]), 
%\]
%where 
%%$\psi^\lambda$ is the higher Lie character indexed by $\lambda$ and 
%$\chi^J$ is the image, under the Frobenius characteristic map, of the ribbon Schur function indexed by $J$; 
%see Section~\ref{sec:background} for more details.

%%character of the generalized Specht module of a certain connected ribbon shape.

%There is a cyclic analogue. If the conjugacy class $\C_\lambda$ carries a cyclic descent extension
%then the fiber sizes of the cyclic descent map are given by
%% presented in Section~\ref{sec:background} ??, states
%\[
%|\{\pi \in \C_\lambda :\ \cDes(\pi)=J\}|
%= \langle \psi^\lambda, \chi_\cyc^J \rangle
%\qquad (\text{for all } \lambda \vdash n,\, J \subseteq [n]), 
%\]
%where $\chi_\cyc^J$ is 
%the image, under the Frobenius characteristic map, of a  certain affine ribbon Schur function;
%see %Section~\ref{sec:background} for more details.
%Theorem~\ref{thm:main22} below.

\section{The hook-multiplicity generating function}

Recall the standard notation $s_\lambda$ for the Schur function indexed by a partition $\lambda$, and $\f_{n,D}$ for the fundamental quasi-symmetric function indexed by a subset $D\subseteq [n-1]$
	\[
	\f_{n,D}({\bf x}) := \sum_{\substack{i_1\le i_2 \le \ldots \le i_n \\ {i_j < i_{j+1} \text{ if } j \in D}}} 
	x_{i_1} x_{i_2} \cdots x_{i_n}.
	\]
%see Definition~\ref{def:fundamental_QSF}.
	A symmetric function is called {\em Schur-positive} if all the
	coefficients in its expansion in the basis of Schur functions are non-negative. 
A subset $\A\subseteq S_n$ is {\em Schur-positive} 
if the
associated quasi-symmetric function
\[
\Q(\A):=\sum\limits_{a\in \A}\f_{n,\Des(a)},
\]
is symmetric and Schur-positive.

For an integer $0 \le k<n$ and a Schur-positive subset $\A \subseteq S_n$ denote
\[
m_{k,\A} := \langle \Q(\A), s_{(n-k,1^k)} \rangle,
\]
where $s_{(n-k,1^k)}$ is the Schur function indexed by the hook partition $(n-k,1^k)$.

First we prove the following key lemma, which provides an algebraic criterion for the existence of a cyclic descent extension. 

\begin{lemma}\label{lem:21}
A Schur-positive set $\A\subseteq S_n$ has a cyclic descent extension if and only if 
the following two conditions hold:
\[
\begin{array}{rl}
	\text{\rm (divisibility)}   & 
	\text{the polynomial }
	\sum_{k=0}^{n-1} m_{k,\A} x^k
	%= (1+x)\sum_{k=0}^{n-2} d_k x^k ,\\
	\text{ is divisible by } 1+x; \\
	\text{\rm (non-negativity)} & 
	%d_k\ge 0 \qquad (\text{for all } k).\\
	\text{the quotient has non-negative coefficients.}
\end{array}
\]
\end{lemma}		

%See Lemma~\ref{lem:2}  below.

%\medskip

By the %a remarkable theorem of 
Gessel-Reutenauer theorem, %~\cite{GR}, 
for every 
%partition $\lambda$ 
conjugacy class $\C_\lambda$ 
the quasi-symmetric function %of the conjugacy class $\C_\lambda$, 
$\Q(\C_\lambda)$ is the Frobenius image of the higher Lie character $\psi^\lambda$, thus  $\C_\lambda$ is  Schur-positive.  
%see Theorem~\ref{thm:GR22} below.


For a partition $\lambda \vdash n$ denote
%\begin{equation}
\[
m_{k,\lambda} := m_{k,\C_\lambda}
= \langle \Q(\C_\lambda), s_{(n-k,1^k)} \rangle
= \langle \psi^\lambda, \chi^{(n-k,1^k)} \rangle
\qquad (0 \le k \le n-1)
\]
and
\[
M_\lambda(x):=\sum\limits_{k=0}^{n-1}m_{k,\lambda}x^k,
%=\sum\limits_{k=0}^{n-1}\langle \psi^\lambda, \chi^{(n-k,1^k}\rangle x^k
%where 
%\[
%m_{k,\lambda}:=\langle \psi^\lambda, \chi^{(n-k,1^k}\rangle
\]
the hook-multiplicity generating function of the higher Lie character $\psi^\lambda$.

%\end{equation}
In order to prove Theorem~\ref{thm:main}, we will show first that  
for conjugacy classes of cycle type $\lambda$, 
%the hook-multiplicity generating function of the higher Lie character $\psi^\lambda$,
the hook-multiplicity generating function $M_\lambda(x)$ is divisible by $1+x$ 
if and only if $\lambda \ne (r^s)$ for any square-free integer $r$. 
%, see Section~\ref{sec:divisibility}. 
Then we will show that the coefficients of the quotient  $M_\lambda(x)/(1+x)$ are non-negative, whenever $\lambda\ne (r^s)$ for any square-free $r$.
%, see Sections~\ref{sec:distinct}-\ref{sec:Witt}. 


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

	
\section{Divisibility of the hook generating  function}\label{sec:divisibility}	
	
%	For a Schur-positive set $\A\subseteq S_n$ 
%	 there exists a non-virtual $S_n$-representation $\phi$,
%	such that
%	\[
%	\ch (\phi)=\sum\limits_{a\in \A} \f_{n,\Des(a)},
%	\]
%where $\ch$	the Frobenius characteristic map.

%\medskip	

%In this section we prove 

\begin{proposition}\label{prop:divisibility} 
	The hook-multiplicity generating function of the higher Lie character $\psi^\lambda$
	\[
	M_\lambda(x):=\sum\limits_{k=0}^{n-1}m_{k,\lambda}x^k
	%=\sum\limits_{k=0}^{n-1}\langle \psi^\lambda, \chi^{(n-k,1^k}\rangle x^k,
	\]
	%where 
	%\[
	%m_{k,\lambda}:=\langle \psi^\lambda, \chi^{(n-k,1^k}\rangle
	%\]
	is divisible by $1+x$ 
	if and only if $\lambda \ne (r^s)$ for any square-free integer $r$.
\end{proposition}

This divisibility condition is proved using an explicit evaluation of the higher Lie character on $n$-cycles. By the Murnaghan--Nakayama rule~\cite[Lemma 4.10.3]{Sagan},


\begin{lemma}\label{lem:div}
For every $S_n$-character $\phi$, 
the hook-multiplicity generating function 
\[
M_\phi(x):=\sum\limits_{k=0}^{n-1} %m_k 
\langle \phi,\chi^{(n-k,1^k)}\rangle
x^k
\]
is divisible by $1+x$ if and only if 
the value of $\phi$ on an $n$-cycle is zero: $\phi_{(n)}=0$. 
\end{lemma}

%\begin{proof}
%%First, recall that %for $0\le k<n$ %recall the notation
%%\[
%%m_k:=\langle \Q(\A), s_{(n-k,1^k)}\rangle=\langle \phi,\chi^{(n-k,1^k)}\rangle \qquad %%(0\le k<n).
%%\]
%    By~\cite[Lemma 4.10.3]{Sagan},  
%    %the Murnaghan-Nakayama rule [reference???], 
%%     the following character evaluation of the irreducible characters at  $n$-cycles % %holds. For 
%for every partition $\lambda\vdash n$      %be a partition of $n$. 
%    \[
%    \chi^\lambda_{(n)}=\begin{cases} (-1)^k,&\text{ if }  \lambda=(n-k,1^k);\\
%		0,&\text{ otherwise }.\\
%		\end{cases}
%   \]
%    Thus   
%   \[
%    \phi_{(n)}=\sum\limits_{\lambda\vdash n} \langle \phi,\chi^\lambda\rangle \chi^\lambda_{(n)}=
%    \sum\limits_{k=0}^{n-1}\langle \phi,\chi^{(n-k,1^k)}\rangle \chi^{(n-k,1^k)}_{(n)}=
%    \sum\limits_{k=0}^{n-1} m_k\cdot (-1)^k= M_\phi(-1),
%    \]
%    which equals zero if and only if $1+x$ divides $ M_\phi(x)$, 
%    completing the proof.
%\end{proof}
	
%	For $\mu = (r^s)$ let 


Letting $\phi=\psi^\mu$, the higher Lie character indexed by the partition $\mu$, reduces Proposition~\ref{prop:divisibility} to the following 
%.  %conclude 
%Frobenius pre-image of quasi-symmetric function $\Q(\C_\mu)$
% we conclude 
%We need the following 
%well-known 
character evaluation. 

%\todo{Is Proposition~\ref{lem:char_eval_cycles} known?
%Is the case $\mu=(n)$ known?}

Recall the M\"obius function $\mu(d)$, which is equal to the sum of the primitive $d$-th roots of $1$. If $d$ has a prime square divisor then $\mu(d)=0$; 
otherwise, $d$ is a product of $k$ distinct primes and $\mu(d)=(-1)^k$. The following lemma is equivalent to a   combinatorial identity due to Garsia, see Proposition~\ref{prop:equiv_Garsia} below.  A direct algebraic %self-contained 
proof is given in~\cite{AHR}.

\begin{lemma}\label{lem:char_eval_cycles}
For $\lambda\vdash n$
\begin{equation}\label{eq:char_eval_cycles}
\psi^\lambda_{(n)}=\begin{cases} \mu(r),&\text{ if }  \lambda = (r^s);\\
		0,&\text{ otherwise },\\
		\end{cases}
\end{equation}
where $\mu(r)$ is the M\"obius function.
\end{lemma}



\begin{proof}[Proof of Proposition~\ref{prop:divisibility}.]
	By Lemma~\ref{lem:div}, % together with Theorem~\ref{thm:GR22},
	$1+x$ divides the hook-multiplicity generating function of the higher Lie character $\psi^\lambda$ 
	%$\ch^{-1}(\Q(\C_\mu))=\psi^\mu$
if and only if $\psi^\lambda_{(n)}=0$.
Lemma~\ref{lem:char_eval_cycles} completes the proof.
\end{proof}


%We deduce

%\begin{corollary}\label{cor:only if}
%\begin{itemize}
%\item[1.]    
%If a partition $\mu\vdash n$ is equal to $(r^s)$ for some square-free $r$ then the descent set map on the conjugacy class $\C_\mu$ does not carry a cyclic descent extension.
%\item[2.] 
%If a partition $\mu\vdash n$ is not equal to $(r^s)$ for any square-free $r$ then $1+x$ divides the hook-multiplicity generating function $M_\mu(x)$. 
%In this case, the descent set map on the conjugacy class $\C_\mu$ carries a cyclic descent extension if and only if 
%the quotient $M_\mu(x)/(1+x)$ has non-negative coefficients.
%\end{itemize}
%\end{corollary}


In the following sections we will prove the non-negativity of the coefficients of the quotient $\frac{M_\lambda(x)}{1+x}$ 
for partitions $\lambda$ which are not equal to $(r^s)$ for any square-free $r$.
%: $n$-cycles will be considered in Section~\ref{sec:cycles}, 
%$\mu = (r^s)$ with non square-free $r$ and $s>1$ will be considered in Section~\ref{sec:Witt} (this is the most difficult case).
%Partitions $\mu$ with distinct parts will be considered using a different more combinatorial approach.  




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

%\section{Non-negativity}

\section{Non-negativity: the case of more than one cycle length}
\label{sec:distinct}





Consider, first, the case of conjugacy classes with more than one cycle length. This is the easiest case to handle.
In that case, we apply a factorization of the associated higher Lie character $\psi^\lambda$ to prove
\begin{lemma}\label{lem:distinct}
	Let $\lambda=(r^s)\sqcup \mu$ be a partition of $n$,
	where $n > rs$ and $\mu$ is a partition of $n-rs$ with no part equal to $r$. 
	Then
	\begin{equation}
	\frac{M_\lambda(x)}{1+x} = M_{(r^s)}(x)M_\mu(x).    
	\end{equation}
	and its coefficients are thus non-negative.
\end{lemma}	



The core of the proof of Theorem~\ref{thm:main} is %thus 
the case $\lambda = (r^s)$.
%\medskip
%Here we use the following algebraic criterion for the existence of a cyclic descent extension.



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

\section{ Non-negativity: the $n$-cycle case}\label{sec:cycles}


%\subsection{Outline}\label{sec:outline}

	 
%	 \begin{proof}[Proof of Corollary~\ref{prop:CDE_cycles}.]
%	     	 By Proposition~\ref{prop:divisibility}, the hook-multiplicity generating function of the higher Lie character $\psi^{n)}$,
%	 $M_{(n)}(x)$,  is divisible by $1+x$
%if and only if $n$ is not square-free. Combining this with  Lemma~\ref{lem:2} , %Proposition~\ref{prop:divisibility}
%	  Proposition~\ref{prop:cycles_nonnegativity} completes the proof. 
%	 \end{proof}
	 
%	 	For %the whole section 
%these sections 

	
		%The $r=2$ case is inherent in \cite{Saxletal}.
	
		%\ 
%In this section we prove Theorem~\ref{main_hook-alternating2}.   
%%		\medskip
%%			%The proof of Theorem~\ref{main_hook-alternating2} will occupy the whole section.
%		Here is an outline of the proof.
%%		%of  Theorem~\ref{main_hook-alternating}.2 captures Sections~\ref{sec:e}-{sec:nn}.
		

		 %the nonnegativity condition when $s=1$. 

%Combining this with Lemma~\ref{lem:2}  and proposition~\ref{prop:divisibility}, implies 
%the existence of cyclic descent extension for the conjugacy class of $n$-cycles $\C_{(n)}$ when $n$ is not square-free. 

%	\subsection{Formulas for inner product}\label{sec:e}


\subsection{A variant of the Witt transform}\label{sec:Witt-subsec}
%In this subsection we present a variant of the Witt transform,
%which will be used to prove non-negativity in Sections ~\ref{sec:unimodality} and~\ref{sec:Witt}.
        The greatest common divisor of two integers $i,j$ is denoted by $(i,j)$. Recall the M\"obius function $\mu(d)$. 
        We shall use here $r$ instead of $n$, with an eye to the sequel.
        %, the sum of the primitive $d$-th roots of $1$. If $d$ has a prime square divisor then $\mu(d)=0$. Otherwise, $d$ is a product of $k$ distinct primes and $\mu(d)=(-1)^k$.
    

 
%Recall the notation $e_k:=e_{k,\psi^{(n)}}$ from~\eqref{e_k_interpretation1}.
    
    \begin{proposition}\label{prop:e_i_formuli1}
    For every $0\le j\le r$
    \begin{equation}\label{eq:Sundaram}
    %f_j =e_j=
    \langle \psi^{(r)}, \chi^{(1^{j})\oplus (r-j)}\rangle= \sum_{d|(r,j)} \frac{\mu(d)(-1)^{j+j/d}}{r} \binom{r/d}{j/d} 
    \qquad (0\le j\le r). \end{equation}
   % thus non-negative.
    \end{proposition}

\begin{remark}\label{rem:e=s}
% \begin{itemize}
%     \item[1.]    
     Proposition~\ref{prop:e_i_formuli1}
      is not new,  
%	It follows, for example, from~\cite[Theorem 3.1]{ET}. 
     %is essentially known. It 
%It follows from 
 %   a well known result of Kra\'skiewicz and Weyman~\cite{KraskiewiczWeyman} (Lemma~\ref{lem:Kra-Wey} below).
%%    see Section~\ref{remarks_on_s=1}.
 %   A symmetric functions proof which applies~\cite[Lemma 2.7]{Sundaram_Adv} was presented by Sheila Sundaram. %~\cite{Sundaram_personal}. 
 %   An alternate proof follows from~\cite[Theorem 3.1]{ET}. %see Remark~\ref{rem:ET}.
    %discussion in  Section~\ref{remarks_on_s=1}. 
   	see Section~\ref{sec:final} below. 
   	%below for a discussion.
%     \item[2.]  
%     Proposition~\ref{prop:e_i_formuli1} 
Also, it is a special
     case of Proposition~\ref{prop:e_i_formuli} below at $s=1$. 
% \end{itemize}
\end{remark}
 
\smallskip

%\begin{definition}\label{def:f}
%	Define 
Denote 
	\begin{equation}\label{eq-def:f}
	f_j := \langle \psi^{(r)}, \chi^{(1^{j})\oplus (r-j)}\rangle
	%\sum_{d|(r,j)} \frac{\mu(d)(-1)^{j+j/d}}{r} \binom{r/d}{j/d} 
	\qquad (0\le j\le r)
	\end{equation}
%\end{definition}
%
%\begin{remark}\label{rem:f_values}
%	By definition, $f_1=1$ for all $r$ and
%	\[
%	f_0 = \begin{cases} 
%	1,&\text{ if }  r=1;\\
%	0,&\text{ if } r>1.\\
%	\end{cases}
%	\]
%	%It is known that, for all $j$, $f_j$ is a non-negative integer.
%\end{remark}
%
 %  \subsection{Variant of the Witt transform}\label{sec:Witt-subsec}
%	Let us collect the $f_j$ multiplicities into a polynomial
and
	\begin{equation*}
	F(x)=f_0+f_1x+f_2x^2+\cdots f_{r-1}x^{r-1}+f_rx^r.
	\end{equation*}
	%Then
	%, as in the proof of Proposition~\ref{prop:k-subsets mod r},
	%\begin{equation}\label{F}F(x)=\sum_{d|r}\frac{\mu(d)}{r} (1-(-x)^d)^{r/d}.
	%\end{equation}
%	
It is easy to see that $f_0 = m_{0,(r)}$, $f_r = m_{r-1,(r)}$ and
\[
f_j = m_{j-1,(r)} + m_{j,(r)}
\qquad (1 \le j \le r-1),
\]
so that $F(x) = (1+x)M_{(r)}(x)$.
Also, by Proposition~\ref{prop:e_i_formuli1},
	
	\begin{equation}\begin{split}\label{F}F(x)&=\sum_j x^j\sum_{d|(r,j)}\frac{\mu(d)(-1)^{\frac{j(d+1)}{d}}}{r} \binom{r/d}{j/d} =\sum_{d|r}\frac{\mu(d)}{r}\sum_{k=0}^{r/d}(-1)^{k(d+1)} \binom{r/d}{k}x^{k d}\\
	&=\sum_{d|r}\frac{\mu(d)}{r} (1-(-x)^d)^{r/d}.
	\end{split}\end{equation}
	
	Recall from \cite{Moree} that the $r$-th Witt transform of a polynomial $p(x)$ is defined by 
	\[
	\mathcal{W}_p^{(r)}(x)=\frac{1}{r}\sum_{d|r}\mu(d)p(x^d)^{r/d}.
	\] 
	In our case put $p(x)=1-x$ to get $F(x)=\mathcal{W}_p^{(r)}(-x)$. The proofs of Theorem~4 and Lemma~1 of \cite{Moree} could have been used to prove that the coefficients of $F(x)$ are non-negative integers. However, this property of $f_i$ also follows from its interpretation as an inner product of two characters.
	
	%Although monotonicity and signs of coefficients of Witt transforms are of a general concern, our results do not follow from them. We need non-negativity \emph{after} we divide by $(1+x)^2$. However, our methods are of similar flavor and might be applied in more general contexts.
	We want to prove that the polynomial $M_{(r)}(x)/(1+x) = F(x)/(1+x)^2$ has non-negative coefficients. 
%	\bigskip

\subsection{Unimodality}\label{sec:unimodality}
	
	A sequence $a_0,\ldots,a_n$ of real numbers is called \emph{unimodal} if there exists an index $0\le i_0\le n$ such that the sequence is weakly increasing $(a_i\leq a_{i+1})$ for $i< i_0$ and weakly decreasing $(a_i\geq a_{i+1})$ for $i\geq i_0$.
	
%	This notion is relevant for us for the following standard observation. 
	
\begin{observation}\label{obs:unimodal}
Let $a(x) = a_0 + a_1 x + \ldots + a_n x^n$ be a polynomial with real, non-negative and unimodal coefficients.
Assume that $1+x$ divides $a(x)$, and let $b(x) := a(x)/(1+x)$.
Then the coefficients of $b(x)$ are non-negative.
\end{observation}%
	
	%	To prove Proposition~\ref{prop:cycles_nonnegativity} recall the notation~\eqref{e_k_interpretation1} and Equation~\eqref{eq:alternating}.
		%\[
		%m_{k,\mu}:=\langle \psi^{\mu}, \chi^{(n-k,1^k)}\rangle.
		%\]
		The explicit description of the coefficients of $(1+x)M_{(n)}(x)$ 
		%inner product  $e_{k,\psi^{(n)}}$ 
		%\[
		%e_{k,(n)}=m_{k,(n)}+m_{k-1,(n)},
		%\]
		given in Proposition~\ref{prop:e_i_formuli1}, 
		combined with %a variant of the Witt transform presented in
		Equation~\eqref{F}, 
		%Section~\ref{sec:Witt-subsec}, 
	is applied %in Section~\ref{sec:unimodality} 
	to prove the following. % unimodality phenomenon. 
		%of the sequence $m_1, m_2,\dots, m_{n-1}$ in the case of the full cycle, that is when $s=1$.
		
		\begin{proposition}\label{prop:s=1_unimodal}
			%For $s = 1$, 
			For every positive integer $n$ 
			the sequence $m_{0,(n)}, m_{1,(n)},\dots, m_{n-1,(n)}$ is unimodal.
		\end{proposition}
		%See Proposition~\ref{prop:s=1_unimodal}. 
		%	 By Observation~\ref{obs:unimodal}, 
%		It will be shown that this unimodality phenomenon 
		%implies the non-negativity of the coefficients of $M_{(n)}(x)/(1+x)$, completing
		%completes the proof of 

For a detailed proof, see~\cite{AHR}. 
%By Observation~\ref{obs:unimodal}, Proposition~\ref{prop:s=1_unimodal} 
%		implies Proposition~\ref{prop:cycles_nonnegativity}.
%\begin{remark}
%	We conjecture that Proposition~\ref{prop:s=1_unimodal} remains true for arbitrary 
%	partition $\mu \vdash n$, in particular for every partition  $(r^s) \vdash n$ with any   
%	$s\ge 1$, see Conjecture~\ref{conj:unimodal}.
%	%\bigskip
%\end{remark}
%We conclude 
 
   By Lemmas~\ref{prop:divisibility} and~\ref{lem:div},  %Corollary~\ref{cor:only if}
    if $n$ is not square-free then
   $1+x$ divides $M_{(n)}(x)$. 
 %  In this section %we consider the case $\mu:=(n)$. 
  % we prove 
%By Observation~\ref{obs:unimodal}, Proposition~\ref{prop:s=1_unimodal} implies   
   
   \begin{proposition}\label{prop:cycles_nonnegativity}
   	If $n$ is not square-free then the coefficients of $M_{(n)}(x)/(1+x)$ are non-negative.
   \end{proposition}
 
 \begin{proof} %[Proof of Proposition~\ref{prop:cycles_nonnegativity}.]
 	Combine Proposition~\ref{prop:s=1_unimodal} with   Observation~\ref{obs:unimodal}.
 \end{proof}
   
   
%   \begin{corollary}\label{prop:CDE_cycles}
%   	The conjugacy class of $n$-cycles $\C_{(n)}$ carries a cyclic descent extension if and only if $n$ is not square-free.
%   \end{corollary}



\section{Non-negativity: the case of cycle type $(r^s)$}
%{Proof of Theorem~\ref{main_hook-alternating2}}
\label{sec:Witt}

%\subsection{Outline}
%	unimodality of the sequence $m_1,m_2,\dots$ at $s=1$.		
In this section we consider the case $\mu = (r^s)$. 
We fix $r$, while $s$ and hence $n=rs$ vary. 
%The arguments below also work for the trivial case $r=1$.
		

 %, see \eqref{e_k_interpretation} below.
		

	
%	\subsection{Characters}\label{sec:e}
%	\subsection{Formulas for inner products}\label{sec:e}
	As in the previous section, instead of the hook-multiplicities 
	$m_{k,s}=\langle \psi^{(r^s)}, \chi^{(n-k,1^k)}\rangle$, 
	it will be easier to work with their consecutive sums
	$e_k = e_{k,s} := m_{k,s} + m_{k-1,s}$, 
	which also have an inner product interpretation.
%\medskip
For given $i$, $r$ and $s$, let
\begin{equation}\label{def:restr_part}
P_{r,s}(i) := 
\{\gamma=(\gamma_1,\ldots,\gamma_s) \mid
\sum_{\ell=1}^s \gamma_\ell=i,\, r\geq \gamma_1\geq\gamma_2\geq\cdots\geq\gamma_s\geq0\}
\end{equation}
denote the set of all partitions of $i$ into at most $s$ parts, each of size at most $r$. 
Denote the multiplicity of $j$ in $\gamma \in P_{r,s}(i)$ by 
$k_j(\gamma) := |\{1 \leq \ell \leq s \mid \gamma_\ell=j\}|$.
	
			\begin{figure}
		    \begin{tikzpicture}[scale=0.5]
		    \draw[step=1,thin] (0,0) grid (6,5);
		    \draw [very thick] (0,0)--(0,5)--(5,5)--(5,4)--(3,4)--(3,2)--(2,2)--(2,1)--(0,1);
		    \end{tikzpicture}
		    \caption{$\gamma = (5,3,3,2,0)$ in $P_{6,5}(13)$. The multiplicities of the parts are $k_1(\gamma) = 0$, $k_2(\gamma) = 1$, $k_3(\gamma) = 2$, $k_4(\gamma) = 0$, $k_5(\gamma) = 1$, and $k_6(\gamma) = 0$.% corresponding to a double $(S_5\wr S_6,S_{13}\times S_{17})$-coset
		    }
		    \label{fig:subpart}
		\end{figure}
	
%\begin{example}
%Let $r=6$, $s=5$ and $i=13$. 
%Then $\gamma=(5,3,3,2,0)\in P_{6,5}(13)$ is a partition of $13$ with $6$ non-negative %parts, each of size at most $6$; see Figure~\ref{fig:subpart}. 
%The multiplicities of the parts are $k_1(\gamma) = 0$, $k_2(\gamma) = 1$, $k_3(\gamma) = 2$, $k_4(\gamma) = 0$, $k_5(\gamma) = 1$, and $k_6(\gamma) = 0$.
%\end{example}

\noindent   
The main result of this section is the following extension of Proposition~\ref{prop:e_i_formuli1} to $s\ge 1$.

\begin{proposition}\label{prop:e_i_formuli}
%\todo{partitions, not compositions!}
For every $s\geq 1$ and $i\geq 0$ we have
\begin{align*}
e_i = \langle \psi^{(r^s)}, \chi^{(1^i)\oplus(n-i)}
%(\varepsilon_{S_i}\times1_{S_{n-i}})\uparrow^{S_n}
\rangle 
&= \sum_{\gamma\in P_{r,s}(i)} \prod_{j \ge 0}
%\binom{f_j\;+(k_j(\gamma)-1)\delta_{2|j}}{k_j(\gamma)}\\
(-1)^{(j+1)k_j(\gamma)} \binom{(-1)^{j+1} f_j}{k_j(\gamma)}\\
&= \sum_{\substack{k_0, \dots, k_r \ge 0 \\ \sum_j k_j = s \\ \sum_j jk_j = i}} \prod_{j = 0}^{r}
%\binom{f_j\;+(k_j-1)\delta_{2|j}}{k_j}.
(-1)^{(j+1)k_j} \binom{(-1)^{j+1} f_j}{k_j}.
\end{align*}
		
%\[\sum_{\substack{\sum k_j=s\\ \sum jk_j=i}}\prod_j \binom{f_j\;+(k_j-1)\delta_{2|j}}{k_j}.
%\]
In particular, for $s=1$ we have $e_i=f_i$.
\end{proposition}
	

%\subsection{A product formula}\label{sec:prod}
	
We derive a formal power series product form of Proposition~\ref{prop:e_i_formuli}. %For small $r$ it enables us to determine explicitly the coefficients $e_i$ hence the $m_i$ for arbitrary $s$.

\begin{corollary}\label{power_series_form}
Let $E(x,y)=E_r(x,y)$ denote the formal power series in which the coefficient of $x^i y^s$ is $e_{i,s}=\langle%\phi^{S_n}
\psi^{(r^s)}, \chi^{(1^i)\oplus(n-i)}
%(\varepsilon_{S_i}\times 1_{S_{n-i}})\uparrow^{S_n}
\rangle$. 
Then
\begin{align}\label{compact}
E(x,y)=\prod_{j=0}^{r} (1 - (-x)^j y)^{(-1)^{j+1}f_j}.
%=\exp\left(\sum_{j=1}^\infty \frac{F(-(-x)^j)}{j}y^j\right).
\end{align}
\end{corollary}
	

%\subsection{Non-negativity}\label{sec:nn}
		
%Now we are ready to prove Theorem~\ref{main_hook-alternating2}.
%it remains to show the following.  
%which is the last claim of Theorem~\ref{main_hook-alternating2}.

%	\begin{proposition}\label{prop:nonneg_coeffs}
%	    If %$\mu(r)=0$
%	    $r$ is not square-free then the coefficients of
%	    \[\frac{E(x,y)-1}{(1+x)^2}\] 
%	    are all non-negative.
%    \end{proposition}



For a fixed positive integer $r$, we consider the formal power series
$M_r(x,y) := \sum_{i,s} m^{(r)}_{i,s} x^i y^s$, 
where $m^{(r)}_{i,s}:=\langle \psi^{(r^s)},  \chi^{(rs-i,1^i)}\rangle$.
% is the multiplicity of the hook character $\chi^{(rs-i,1^i)}$ in the higher Lie character $\psi^{(r^s)}$. 





\begin{theorem}\label{main_hook-alternating2}
	If $r$ is not square-free then the polynomial 
	\[\frac{M_r(x,y)}{1+x}\] 
	has non-negative integer coefficients.
\end{theorem}





	
	\begin{proof} %[Proof of Theorem~\ref{main_hook-alternating2}.]
	 Recall the notation $F(x):=\sum\limits_j f_jx^j$.
	 We may write $F(x)=(1+x)^2\sum_{i}g_i x^i$, where, by
	 Proposition~\ref{prop:cycles_nonnegativity},
	 the coefficients $g_i=\sum_{i\leq j} (-1)^{i-j}m_j$ are
	 non-negative.
	 
	 Equation~\eqref{compact} can be rewritten in terms of the $g_i$'s.
	 \begin{equation}\label{eq:factors}
	 	E(x,y)= \prod_{i\geq 0} \left(
	 	\frac{(1 - (-x)^{i} y)(1 - (-x)^{i+2} y)}{(1 - (-x)^{i+1} y)^2}
	 	\right)^{(-1)^{i+1}
	 		g_i}.
	 \end{equation}
	 It suffices to show that all the factors in \eqref{eq:factors}
	 are of the form
	 $1+(1+x)^2p(x,y)$, with $p(x,y)$ a power series with non-negative
	 coefficients. This
	 can be achieved by separate arguments for even and odd indices $i$.	
	\end{proof}


Now we are ready to prove the main theorem.

\begin{proof}[Proof of Theorem~\ref{thm:main}.]
	Combine Lemma~\ref{lem:21} with Proposition~\ref{prop:divisibility}, 
	Lemma~\ref{lem:distinct} 
	and Theorem~\ref{main_hook-alternating2}. 
\end{proof}


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

\section{Final remarks and open problems}\label{sec:final}



%\bigskip
%\section{Combinatorial identities and open problems}\label{remarks_on_s=1}
%In this subsection it will be shown that Lemma~\ref{lem:char_eval_cycles} and Proposition~\ref{prop:e_i_formuli1} are intimately related 
%%equivalent to  
%to 
%remarkable 
%we recall two 
%well-known combinatorial identities.
%\medskip
Recall the major index of a permutation $\pi\in S_n$, 
$\maj(\pi):=\sum\limits_{i\in \Des(\pi)}i$. 
Let $\zeta$ be a primitive $n$-th root of unity. The following identity was proved by Garsia~\cite[Equation 5.8]{Garsia}. 
\begin{equation}\label{eq:Garsia}
\sum\limits_{\pi\in \C_\lambda}\zeta^{\maj(\pi)}=
\begin{cases} \mu(r) &\text{if }  \lambda = (r^s),\\
		0 &\text{otherwise,}\\
		\end{cases}
\qquad (\text{for all } \lambda\vdash n),
\end{equation}
where $\mu(r)$ is the M\"obius function. A purely combinatorial proof was given in~\cite{Wachs} by Wachs. By~\cite[Lemma 3.4]{Stembridge}, we have the following result.

\begin{proposition}\label{prop:equiv_Garsia}
  For every partition $\lambda\vdash n$,     
%      \begin{equation}
$\psi^\lambda_{(n)} = \sum\limits_{\pi \in \C_\lambda} \zeta^{\maj(\pi)}$.  %\qquad(\text{for all } \mu\vdash n),
%\end{equation}
\end{proposition}

\begin{corollary}
     Equation~\eqref{eq:char_eval_cycles} %above 
    is equivalent to Equation~\eqref{eq:Garsia}.
\end{corollary}

\medskip

%    \begin{remark}\label{rem:ET}
    	Proposition~\ref{prop:e_i_formuli1} %at $s=1$ %is essentially equivalent to well known results.
    	%  is not new.
    	%  For example, by Gessel-Reutenauer Theorem (Theorem~\ref{thm:GR}) together with
    	%Observation~\ref{lem:1}, %Equation~\eqref{eq:ET} 
    	%is equivalent to Proposition~\ref{prop:e_i_formuli} at $s=1$ 
    	is equivalent to the following equation
    	%  \begin{equation}\label{eq:ET}
    	\[
    	|\{\pi\in C_{(n)}: \ \Des(\pi)=[j]\}|=\frac{1}{n}\sum\limits_{d|n} \mu(d) (-1)^{j-[\frac{j}{d}]}\binom{n-1}{j-1}
    	%\cdot |\pi\in S_n:\ \Des(\pi)=[j]\}|  
    	\qquad (0\le j <n),        
    	\]
    	%\end{equation}
    	which is an immediate consequence of
    	%a recent result of Elizalde and Troyka
    	~\cite[ Theorem 3.1]{ET}.  
        	%  	Proposition~\ref{prop:e_i_formuli} at $s=1$ may be deduced from~\cite[ Theorem 3.1]{ET}
    	%\cite[Theorem 2.1]{GR}
    	%	implies 
    	%	\[	e_j=f_j=
    	%	\]
    	%The case $s=1$ seems to be known (and classical?).  
    	%	This result is not new. 	It follows, for example, from~\cite[ Theorem 3.1]{ET}.
    	%\footnote{
    	An older proof was presented to us by Sheila Sundaram,  %~\cite{Sundaram_personal},  
    	deducing 
    	Proposition~\ref{prop:e_i_formuli1} 
    	%as a consequence of 
    	from~\cite[Lemma 2.7]{Sundaram_Adv}. 
%Finally, 
By the Kra\'skiewicz--Weyman Theorem~\cite[Theorem 8.4]{Garsia}, 
	
\begin{proposition}\label{lem:Kra-Wey}
%	Letting $\omega$ denote a primitive character of $\ZZ_n\leq S_n$,
%	%and let $\chi^k=\chi^{(n-k,1^k)}$ denote the irreducible character of $S_n$ associated %to $(n-k,1^k)$, the hook partition with leg-length $k\leq n-1$. Then 
For every $0\leq k\leq n$, the multiplicity 
$m_k = \langle \psi^{(n)},\chi^{(n-k,1^k)} \rangle$ 
is equal to the cardinality of the set
\[%A_{k,n,1}=
\{1 \le a_1 < a_2 < \cdots <a_k \le n-1 \mid \sum_{i=1}^k a_i \equiv 1 \!\!\!\!\pmod{n}\}.\]
\end{proposition}
	
%\begin{proof}
%Denoting by $\binom{[n-1]}{k}$ the set of all $k$-subsets in $[n-1]$, 
%the map $\Des: \SYT(n-k,1^k) \rightarrow \binom{[n-1]}{k}$ is a bijection.
%The major index of a tableau is the sum of the elements of its descent set.
%\end{proof}
	
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
	
%Consider the following combinatorial identity.
%\begin{proposition}
%For every $0 \le k \le n$,
%\begin{equation}\label{eq:equivalence_KW}
%|\{1 \le a_1 < a_2 < \cdots <a_k \le n \mid \sum_{i=1}^k a_i\equiv 1 \!\!\!\!\pmod{n}\}| %= \sum_{d|(n,k)} \frac{\mu(d)(-1)^{k+k/d}}{n} \binom{n/d}{k/d}.
%\end{equation}	    
%\end{proposition}

	
%In light of  Corollary~\ref{lem:Kra-Wey} one observes that 
%\begin{observation}\label{prop:equiv_f_KW}
\begin{corollary} %\label{lem:Kra-Wey}
	Proposition~\ref{prop:e_i_formuli1}
	is equivalent to the following identity: %~\eqref{eq:equivalence_KW}.	
	For every $0 \le k \le n$,
%	\begin{equation} \label{eq:equivalence_KW}
\[
	|\{1 \le a_1 < a_2 < \cdots <a_k \le n \mid \sum_{i=1}^k a_i\equiv 1 \!\!\!\!\pmod{n}\}| = \sum_{d|(n,k)} \frac{\mu(d)(-1)^{k+k/d}}{n} \binom{n/d}{k/d}.
\]
\end{corollary}
%	\end{equation}
%	\end{observation}
	




%\begin{remark}
%Noting that Proposition~\ref{prop:e_i_formuli1} is a special case of Proposition~\ref{prop:e_i_formuli} at $s=1$, one concludes that
%Equation~\eqref{eq:equivalence_KW} is a consequence of the latter.
%\end{remark}
	
	%In Proposition~\ref{prop:e_i_formuli} we proved that for $s=1$ $m_k+m_{k-1}=e_k=f_k$. Now we give a quick direct proof that Lemma~\ref{lem:Kra-Wey} and our definition of agree. % in Proposition~\ref{prop:k-subsets mod r}.

    It remains a challenge to find such a direct link between Schocker's general description of the multiplicity and our version in Proposition~\ref{prop:e_i_formuli}.



%   \todo{Regarding Proposition~\ref{prop:e_i_formuli1}, 
 %   this nonnegativity result is not new.
 %       As noted by Sheila Sundaram, it follows from~\cite[Lemma 2.7]{Sundaram_Adv} that thus non-negative.
 %       }



\medskip	

%\section{Open problems}\label{sec:open}


Our proof of Theorem~\ref{thm:main} is not constructive.

%\todo{Expand}

\begin{problem} 
Find %a constructive proof of Theorem~\ref{thm:main}, via
an explicit combinatorial description of a cyclic descent extension
on conjugacy classes of cycle type $\lambda$, not equal to $(r^s)$ for any square-free $r$.
\end{problem}

%\bigskip



%\bigskip

%\todo{YR: The following pa and conjecture is a duplication with introduction, where the conjecture was stated for all partitions $\mu\vdash n$.}

%{sec:unimodality}
	

	
	%\emph{unimodal} if there exists a middle index $0\le i_0\le n$ such that the sequence is increasing $a_i\leq a_{i+1}$ for $i< i_0$ and decreasing $a_i\geq a_{i+1}$ for $i\geq i_0$.


%where $\omega_r^{S_n}=???$. % and $\chi^{(n-k,1^k)}=???$.
By Proposition~\ref{prop:s=1_unimodal}, the \emph{hook-multiplicity sequence} $m_{0,(n)}, \ldots, m_{n-1,(n)}$ is unimodal.  
%in the case of the full cycle, that is, when $s=1$. 
%We conjecture that it is unimodal for all partitions $\mu\vdash n$.  %(Conjecture~\ref{conj:unimodal}).
%Computer experiments support the following conjecture.

%The following conjecture  
% was verified for all partitions of size $n\le 15$ 
% and for all partitions of rectangular shape $(r^s)$ for $r\leq 40,\,s\leq 5$. 
 
%% For a partition $\lambda \vdash n$ let
%%     \[
%%Finally, r
%Recall the notation $m_{k,\lambda}:=\langle \psi^\lambda, \chi^{(n-k,1^k)}\rangle$.
% %   \]
    \begin{conjecture}\label{conj:unimodal}
    For every partition $\lambda \vdash n$, the hook-multiplicity sequence   
    $(m_{0,\lambda},\ldots,m_{n-1,\lambda})$ 
    is unimodal.
    \end{conjecture}
    
% The conjecture was verified for all partitions of size $n\le 15$ 
% and for all partitions of rectangular shape $(r^s)$ for $r\leq 40,\,s\leq 5$.   
    
%  \smallskip

%More open problems and conjectures may be found in the full version paper~\cite{AHR}.

%\acknowledgements{\lipsum[20]}

%% if you use biblatex then this generates the bibliography
%% if you use some other method then remove this and do it your own way
\printbibliography

\end{document}

