% THIS DOCUMENT IS WRITTEN IN LATEX 2e
%
% TO FIND THE TITLE:  search for the command \title using your word 
% processor
%
\documentclass[12pt,reqno]{amsart}
\usepackage{amssymb,amsthm,amsmath,amsfonts,latexsym,tikz,hyperref,shuffle}
%\usepackage[notref, notcite]{showkeys}
\usepackage[hmargin=1in,vmargin=1in]{geometry}

%\setlength{\topmargin}{.1in}
%\setlength{\textheight}{8in}
%\setlength{\textwidth}{5.8in}
%\setlength{\evensidemargin}{.4in}
%\setlength{\oddsidemargin}{.4in}


\newtheorem{thm}{Theorem}[section]
\newtheorem{prop}[thm]{Proposition}
\newtheorem{cor}[thm]{Corollary}
\newtheorem{lem}[thm]{Lemma}
\newtheorem{conj}[thm]{Conjecture}
\newtheorem{exa}[thm]{Example}
\newtheorem{question}[thm]{Question}

\newcommand{\tre}{\textcolor{red}}
\newcommand{\shu}{\shuffle}

\DeclareMathOperator{\St}{St}
\DeclareMathOperator{\Pk}{Pk}
\DeclareMathOperator{\pk}{pk}
\DeclareMathOperator{\QSym}{QSym}
\DeclareMathOperator{\cDes}{cDes}
\DeclareMathOperator{\cdes}{cdes}
\DeclareMathOperator{\cPk}{cPk}
\DeclareMathOperator{\cpk}{cpk}
\DeclareMathOperator{\cSt}{cSt}
\DeclareMathOperator{\std}{std}
\DeclareMathOperator{\bru}{bru}
\DeclareMathOperator{\cbru}{cbru}

\newcommand{\ben}{\begin{enumerate}}
\newcommand{\een}{\end{enumerate}}
\newcommand{\ble}{\begin{lem}}
\newcommand{\ele}{\end{lem}}
\newcommand{\bth}{\begin{thm}}
\renewcommand{\eth}{\end{thm}}
\newcommand{\bpr}{\begin{prop}}
\newcommand{\epr}{\end{prop}}
\newcommand{\bco}{\begin{cor}}
\newcommand{\eco}{\end{cor}}
\newcommand{\bcon}{\begin{conj}}
\newcommand{\econ}{\end{conj}}
\newcommand{\bde}{\begin{defn}}
\newcommand{\ede}{\end{defn}}
\newcommand{\bex}{\begin{exa}}
\newcommand{\eex}{\end{exa}}
\newcommand{\barr}{\begin{array}}
\newcommand{\earr}{\end{array}}
\newcommand{\btab}{\begin{tabular}}
\newcommand{\etab}{\end{tabular}}
\newcommand{\beq}{\begin{equation}}
\newcommand{\eeq}{\end{equation}}
\newcommand{\bea}{\begin{eqnarray*}}
\newcommand{\eea}{\end{eqnarray*}}
\newcommand{\bal}{\begin{align*}}
\newcommand{\bce}{\begin{center}}
\newcommand{\ece}{\end{center}}
\newcommand{\bpi}{\begin{picture}}
\newcommand{\epi}{\end{picture}}
\newcommand{\bpp}{\begin{picture}}
\newcommand{\epp}{\end{picture}}
\newcommand{\bfi}{\begin{figure} \begin{center}}
\newcommand{\efi}{\end{center} \end{figure}}
\newcommand{\bprf}{\begin{proof}}
\newcommand{\eprf}{\end{proof}\medskip}
\newcommand{\capt}{\caption}
\newcommand{\bsl}{\begin{slide}{}}
\newcommand{\esl}{\end{slide}}
\newcommand{\bfr}{\begin{frame}}
\newcommand{\efr}{\end{frame}}

\newcommand{\fti}[1]{\frametitle{#1}}

\newcommand{\pscb}[1]{\pscirclebox{#1}}

%\newcommand{\ch}{\choose}
\newcommand{\bib}{thebibliography}
\newcommand{\comp}{\models}
\newcommand{\pf}{{\bf Proof.\hspace{5pt}}}
%\newcommand{\prf}{{\bf Proof\hspace{7pt}}}
%\newcommand{\qed}{\rule{1ex}{1ex}}
\newcommand{\hqed}{\hfill \qed}
\newcommand{\hqedm}{\hfill \qed \medskip}
\newcommand{\Qed}{\rule{1ex}{1ex} \medskip}
\newcommand{\qqed}{\qquad\rule{1ex}{1ex}}
\newcommand{\Qqed}{\qquad\rule{1ex}{1ex}\medskip}
\newcommand{\eqed}[1]{$\textcolor{white}{\qed}\hfill{\dil#1}\hfill\qed$}
\newcommand{\eqqed}[1]{$\rule{1ex}{0ex}\hfill{\dil#1}\hfill\qed$}
%\newcommand{\mc}[3]{\multicolumn{#1}{#2}{#3}}
%\newcommand{\Mc}[1]{\multicolumn{#1}{c}{}}
%\newcommand{\mc}[2]{\multicolumn{#1}{#2}}
\newcommand{\ul}{\underline}
\newcommand{\ol}{\overline}
\newcommand{\hor}{\mbox{--}}
\newcommand{\hs}[1]{\hspace{#1}}
\newcommand{\hso}[1]{\hspace{-1pt}}
\newcommand{\vs}[1]{\vspace{#1}}
\newcommand{\qmq}[1]{\quad\mbox{#1}\quad}
\newcommand{\ssk}{\smallskip}
\newcommand{\msk}{\mediumskip}
\newcommand{\bsk}{\bigskip}
\newcommand{\rp}[2]{\rule{#1pt}{#2pt}}
\newcommand{\str}[1]{\rule{#1pt}{0pt}}
%\newcommand{\st}[1]{\rule{#1}{0pt}}
\newcommand{\mbl}[1]{\makebox(0,0)[l]{#1}}
\newcommand{\mbr}[1]{\makebox(0,0)[r]{#1}}
\newcommand{\mbt}[1]{\makebox(0,0)[t]{#1}}
\newcommand{\mbb}[1]{\makebox(0,0)[b]{#1}}
\newcommand{\mbc}[1]{\makebox(0,0){#1}}
\newcommand\mar[1]{\marginpar{\raggedleft#1}}
\newcommand{\pmo}[2]{\put(#1){\makebox(0,0){#2}}}
%\newcommand{\new}[1]{\ensuremath{\blacktriangleright}#1\ensuremath{\blacktriangleleft}}
\newcommand{\emp}{\emptyset}
\newcommand{\indu}{\uparrow}
\newcommand{\rest}{\downarrow}
\newcommand{\sm}{\hspace{-2pt}\setminus\hspace{-2pt}}
\newcommand{\sbs}{\subset}
\newcommand{\sbe}{\subseteq}
\newcommand{\sps}{\supset}
\newcommand{\spe}{\supseteq}
\newcommand{\setm}{\setminus}
\newcommand{\asy}{\thicksim}
\newcommand{\dle}{<\hspace{-6pt}\cdot}
\newcommand{\dge}{\cdot\hspace{-6pt}>}
\newcommand{\lec}{\lessdot}
\newcommand{\grc}{\gtrdot}
\newcommand{\iso}{\cong}
%\newcommand{\con}{\equiv}
\newcommand{\Cong}{\equiv}
\newcommand{\conm}[1]{\stackrel{#1}{\equiv}}

\newcommand{\widevec}{\overrightarrow}
%makes a wide arrow over stuff if have \overrightarrow{stuff} 
\newcommand{\alh}{\hat{\al}}
\newcommand{\Ch}{\hat{C}}
\newcommand{\eh}{\hat{e}}
\newcommand{\Gh}{\hat{G}}
\newcommand{\ih}{\hat{\imath}}
\newcommand{\jh}{\hat{\jmath}}
\newcommand{\gh}{\hat{g}}
\newcommand{\mh}{\hat{0}}
\newcommand{\Mh}{\hat{1}}
\newcommand{\Dh}{\hat{D}}
\newcommand{\lah}{\hat{\la}}
\newcommand{\zh}{\hat{0}}
\newcommand{\oh}{\hat{1}}
\newcommand{\Ph}{\hat{P}}
\newcommand{\ph}{\hat{p}}
\newcommand{\Pih}{\hat{\Pi}}
\newcommand{\bbPh}{\hat{\bbP}}
\newcommand{\Qh}{\hat{Q}}
\newcommand{\Sh}{\hat{S}}
\newcommand{\lh}{\hat{l}}
\newcommand{\xh}{\hat{x}}
\newcommand{\Yh}{\hat{Y}}
\newcommand{\ptn}{\vdash}
\newcommand{\cpn}{\models}
\newcommand{\lt}{\lhd}
\newcommand{\gt}{\rhd}
\newcommand{\lte}{\unlhd}
\newcommand{\gte}{\unrhd}
\newcommand{\jn}{\vee}
\newcommand{\Jn}{\bigvee}
\newcommand{\mt}{\wedge}
\newcommand{\Mt}{\bigwedge}
\newcommand{\bdy}{\partial}
\newcommand{\sd}{\bigtriangleup}
\newcommand{\case}[4]{\left\{\barr{ll}#1&\mbox{#2}\\#3&\mbox{#4}\earr\right.}
\newcommand{\fl}[1]{\lfloor #1 \rfloor}
\newcommand{\ce}[1]{\lceil #1 \rceil}
\newcommand{\flf}[2]{\left\lfloor\frac{#1}{#2}\right\rfloor}
\newcommand{\cef}[2]{\left\lceil\frac{#1}{#2}\right\rceil}
\newcommand{\gau}[2]{\left[ \barr{c} #1 \\ #2 \earr \right]}
\newcommand{\gauss}[2]{\genfrac{[}{]}{0pt}{}{#1}{#2}} 
\newcommand{\setc}[2]{\{left{#1}\ :\ #2\}}
\newcommand{\setl}[2]{\{left{#1}\ |\ #2\}}
\newcommand{\qst}{$q$-Stirling numbers}
\newcommand{\qbi}{$q$-binomial coefficients}
\newcommand{\del}{\nabla}
\newcommand{\pde}[2]{\frac{\partial#1}{\partial#2}}
\newcommand{\spd}[2]{\frac{\partial^2\hspace{-2pt}#1}{\partial#2^2}}
\newcommand{\ode}[2]{\ds\frac{d#1}{d#2}}
\def\<{\langle}
\def\>{\rangle}
\newcommand{\fall}[2]{\langle{#1}\rangle_{#2}}
\newcommand{\nor}[1]{\parallel{#1}\parallel}
\newcommand{\ipr}[2]{\langle{#1},{#2}\rangle}
\newcommand{\spn}[1]{\langle{#1}\rangle}
%\newcommand{\lb}{\left\{}
%\newcommand{\rb}{\right\}}
\newcommand{\ree}[1]{(\ref{#1})}
\newcommand{\rpl}{$\longleftarrow$}

\newcommand{\ra}{\rightarrow}
\newcommand{\Ra}{\Rightarrow}
\newcommand{\lta}{\leftarrow}
\newcommand{\rla}{\leftrightarrow}
\newcommand{\lra}{\longrightarrow}
\newcommand{\lla}{\longleftarrow}
\newcommand{\Lra}{\Longrightarrow}
\newcommand{\llra}{\longleftrightarrow}
\newcommand{\Llra}{\Longleftrightarrow}
\newcommand{\ve}[1]{\stackrel{\ra}{#1}}


\newcommand{\al}{\alpha}
\newcommand{\be}{\beta}
\newcommand{\ga}{\gamma}
\newcommand{\de}{\delta}
\newcommand{\ep}{\epsilon}
\newcommand{\vep}{\varepsilon}
\newcommand{\io}{\iota}
\newcommand{\ka}{\kappa}
\newcommand{\la}{\lambda}
\newcommand{\mut}{\tilde{\mu}}
\newcommand{\om}{\omega}
\newcommand{\Phit}{\tilde{\Phi}}
\newcommand{\Psit}{\tilde{\Psi}}
\newcommand{\rhot}{\tilde{\rho}}
\newcommand{\si}{\sigma}
\renewcommand{\th}{\theta}
%       NOTE THAT \th HAS BEEN RENEWCOMMANDed
\newcommand{\ze}{\zeta}
\newcommand{\Al}{\Alpha}
\newcommand{\Ga}{\Gamma}
\newcommand{\De}{\Delta}
\newcommand{\Ep}{\epsilon}
\newcommand{\La}{\Lambda}
\newcommand{\Om}{\Omega}
\newcommand{\Si}{\Sigma}
\newcommand{\Th}{\Theta}
\newcommand{\Ze}{\Zeta}


\newcommand{\0}{{\bf 0}}
\newcommand{\1}{{\bf 1}}
\newcommand{\2}{{\bf 2}}
\newcommand{\3}{{\bf 3}}
\newcommand{\4}{{\bf 4}}
\newcommand{\5}{{\bf 5}}
\newcommand{\6}{{\bf 6}}
\newcommand{\7}{{\bf 7}}
\newcommand{\8}{{\bf 8}}
\newcommand{\9}{{\bf 9}}
\newcommand{\ba}{{\bf a}}
\newcommand{\bb}{{\bf b}}
\newcommand{\bc}{{\bf c}}
\newcommand{\bd}{{\bf d}}
\newcommand{\bfe}{{\bf e}}
\newcommand{\bff}{{\bf f}}
\newcommand{\bg}{{\bf g}}
\newcommand{\bh}{{\bf h}}
\newcommand{\bi}{{\bf i}}
\newcommand{\bj}{{\bf j}}
\newcommand{\bk}{{\bf k}}
\newcommand{\bl}{{\bf l}}
\newcommand{\bm}{{\bf m}}
\newcommand{\bn}{{\bf n}}
\newcommand{\bp}{{\bf p}}
\newcommand{\bq}{{\bf q}}
\newcommand{\br}{{\bf r}}
\newcommand{\bs}{{\bf s}}
\newcommand{\bt}{{\bf t}}
\newcommand{\bu}{{\bf u}}
\newcommand{\bv}{{\bf v}}
\newcommand{\bw}{{\bf w}}
\newcommand{\bx}{{\bf x}}
\newcommand{\by}{{\bf y}}
\newcommand{\bz}{{\bf z}}
\newcommand{\bA}{{\bf A}}
\newcommand{\bB}{{\bf B}}
\newcommand{\bC}{{\bf C}}
\newcommand{\bE}{{\bf E}}
\newcommand{\bF}{{\bf F}}
\newcommand{\bG}{{\bf G}}
\newcommand{\bH}{{\bf H}}
\newcommand{\bN}{{\bf N}}
\newcommand{\bP}{{\bf P}}
\newcommand{\bQ}{{\bf Q}}
\newcommand{\bR}{{\bf R}}
\newcommand{\bS}{{\bf S}}
\newcommand{\bT}{{\bf T}}
\newcommand{\bV}{{\bf V}}
\newcommand{\bX}{{\bf X}}
\newcommand{\bXh}{\hat{{\bf X}}}
\newcommand{\bZ}{{\bf Z}}
\newcommand{\bep}{{\bf \ep}}
\newcommand{\bcdot}{{\bf \cdot}}
\newcommand{\bmpl}{
\hspace{2pt}
\begin{pspicture}(.3,.3)
\psline[linewidth=1.5pt,arrows=cc-cc](.15,0)(.15,.3)
\psline[linewidth=1.5pt,arrows=cc-cc](0,.15)(.3,.15)
\end{pspicture}
\hspace{2pt}
}
\newcommand{\bmmi}{
\hspace{2pt}
\begin{pspicture}(.3,.3)
\psline[linewidth=1.5pt,arrows=cc-cc](0,.15)(.3,.15)
\end{pspicture}
\hspace{2pt}
}
\newcommand{\bma}{\mbox{\boldmath $a$}}
\newcommand{\bmb}{\mbox{\boldmath $b$}}
\newcommand{\bmk}{\mbox{\boldmath $k$}}
\newcommand{\bml}{\mbox{\boldmath $l$}}
\newcommand{\bmn}{\mbox{\boldmath $n$}}
\newcommand{\bbC}{{\mathbb C}}
\newcommand{\bbF}{{\mathbb F}}
\newcommand{\bbM}{{\mathbb M}}
\newcommand{\bbN}{{\mathbb N}}
\newcommand{\bbP}{{\mathbb P}}
\newcommand{\bbQ}{{\mathbb Q}}
\newcommand{\bbR}{{\mathbb R}}
\newcommand{\bbS}{{\mathbb S}}
\newcommand{\bbZ}{{\mathbb Z}}
\newcommand{\cA}{{\cal A}}
\newcommand{\cAB}{{\cal AB}}
\newcommand{\cAD}{{\cal AD}}
\newcommand{\cB}{{\cal B}}
\newcommand{\cBC}{{\cal BC}}
\newcommand{\cC}{{\cal C}}
\newcommand{\cD}{{\cal D}}
\newcommand{\cDB}{{\cal DB}}
\newcommand{\cE}{{\cal E}}
\newcommand{\cF}{{\cal F}}
\newcommand{\cG}{{\cal G}}
\newcommand{\cH}{{\cal H}}
\newcommand{\cI}{{\cal I}}
\newcommand{\cIF}{{\cal IF}}
\newcommand{\cJ}{{\cal J}}
\newcommand{\cK}{{\cal K}}
\newcommand{\cL}{{\cal L}}
\newcommand{\cm}{{\cal m}}
\newcommand{\cM}{{\cal M}}
\newcommand{\cN}{{\cal N}}
\newcommand{\cNBC}{{\cal NBC}}
\newcommand{\cO}{{\cal O}}
\newcommand{\cP}{{\cal P}}
\newcommand{\cPD}{{\cal PD}}
\newcommand{\cR}{{\cal R}}
\newcommand{\cRF}{{\cal RF}}
\newcommand{\cS}{{\cal S}}
\newcommand{\cT}{{\cal T}}
\newcommand{\cTb}{\ol{\cal T}}
\newcommand{\cV}{{\cal V}}
\newcommand{\cW}{{\cal W}}
\newcommand{\cX}{{\cal X}}
\newcommand{\cY}{{\cal Y}}
\newcommand{\cZ}{{\cal Z}}

\newcommand{\df}{\dot{f}}
\newcommand{\dF}{\dot{F}}
\newcommand{\fg}{{\mathfrak g}}
\newcommand{\fG}{{\mathfrak G}}
\newcommand{\fgt}{\tilde{\mathfrak g}}
\newcommand{\fgl}{{\mathfrak gl}}
\newcommand{\fL}{{\mathfrak L}}
\newcommand{\fS}{{\mathfrak S}}
\newcommand{\fsl}{{\mathfrak sl}}
\newcommand{\at}{\tilde{a}}
\newcommand{\ct}{\tilde{c}}
\newcommand{\dt}{\tilde{d}}
\newcommand{\pt}{\tilde{p}}
\newcommand{\Bt}{\tilde{B}}
\newcommand{\Gt}{\tilde{G}}
\newcommand{\Ht}{\tilde{H}}
\newcommand{\Kt}{\tilde{K}}
\newcommand{\Nt}{\tilde{N}}
%\newcommand{\St}{\tilde{S}}
\newcommand{\Xt}{\tilde{X}}
\newcommand{\alt}{\tilde{\alpha}}
\newcommand{\bet}{\tilde{\beta}}
\newcommand{\rht}{\tilde{\rho}}
\newcommand{\Pit}{\tilde{\Pi}}
\newcommand{\tal}{\tilde{\alpha}}
\newcommand{\tbe}{\tilde{\beta}}
\newcommand{\tPi}{\tilde{\Pi}}
\newcommand{\ab}{\ol{a}}
\newcommand{\Ab}{\ol{A}}
\newcommand{\Bb}{\ol{B}}
\newcommand{\cb}{\ol{c}}
\newcommand{\Cb}{{\ol{C}}}
\newcommand{\db}{\ol{d}}
\newcommand{\Db}{\ol{D}}
\newcommand{\eb}{\ol{e}}
\newcommand{\Eb}{\ol{E}}
\newcommand{\fb}{\ol{f}}
\newcommand{\Fb}{\ol{F}}
\newcommand{\Gb}{\ol{G}}
\newcommand{\Hb}{\ol{H}}
\newcommand{\ib}{\ol{\imath}}
\newcommand{\Ib}{\ol{I}}
\newcommand{\jb}{\ol{\jmath}}
\newcommand{\Jb}{\ol{J}}
\newcommand{\kb}{\ol{k}}
\newcommand{\Kb}{\ol{K}}
\newcommand{\nb}{\ol{n}}
\newcommand{\pb}{\ol{p}}
\newcommand{\Pb}{\ol{P}}
\newcommand{\Phib}{\ol{\Phi}}
\newcommand{\Qb}{\ol{Q}}
\newcommand{\rb}{\ol{r}}
\newcommand{\Rb}{\ol{R}}
\newcommand{\Sb}{\ol{S}}
\newcommand{\tb}{\ol{t}}
\newcommand{\Tb}{\ol{T}}
\newcommand{\Ub}{\ol{U}}
\newcommand{\Wb}{\ol{W}}
\newcommand{\xb}{\ol{x}}
\newcommand{\Xb}{\ol{X}}
\newcommand{\yb}{\ol{y}}
\newcommand{\Yb}{\ol{Y}}
\newcommand{\zb}{\ol{z}}
\newcommand{\Zb}{\ol{Z}}
\newcommand{\pib}{\ol{\pi}}
\newcommand{\sib}{\ol{\si}}
\newcommand{\degb}{\ol{\deg}}
\newcommand{\vj}{\vec{\jmath}}
\newcommand{\vr}{\vec{r}}
\newcommand{\vv}{\vec{v}}
\newcommand{\vw}{\vec{w}}
\newcommand{\ttab}{\{t\}}
\newcommand{\stab}{\{s\}}


\DeclareMathOperator{\Age}{Age}
\DeclareMathOperator{\Aut}{Aut}
\DeclareMathOperator{\Av}{Av}
\DeclareMathOperator{\abl}{al}
\DeclareMathOperator{\asc}{asc}
\DeclareMathOperator{\BC}{BC}
\DeclareMathOperator{\capa}{cap}
\DeclareMathOperator{\codim}{codim}
\DeclareMathOperator{\ch}{ch}
%Commented out \ch for choose
\DeclareMathOperator{\col}{col}
\DeclareMathOperator{\ctt}{ct}
\DeclareMathOperator{\Der}{Der}
\DeclareMathOperator{\des}{des}
\DeclareMathOperator{\Des}{Des}
\DeclareMathOperator{\Det}{Det}
\DeclareMathOperator{\diag}{diag}
\DeclareMathOperator{\Diag}{Diag}
\DeclareMathOperator{\diam}{diam}
\DeclareMathOperator{\End}{End}
\DeclareMathOperator{\ev}{ev}
\DeclareMathOperator{\eval}{eval}
\DeclareMathOperator{\Eval}{Eval}
\DeclareMathOperator{\FPF}{FPF}
\DeclareMathOperator{\Frac}{Frac}
\DeclareMathOperator{\gen}{gen}
\DeclareMathOperator{\GL}{GL}
\DeclareMathOperator{\Harm}{Harm}
\DeclareMathOperator{\Hom}{Hom}
\DeclareMathOperator{\id}{id}
\DeclareMathOperator{\im}{im}
\DeclareMathOperator{\imaj}{imaj}
\DeclareMathOperator{\inc}{inc}
\DeclareMathOperator{\Ind}{Ind}
\DeclareMathOperator{\inter}{int}
\DeclareMathOperator{\Inter}{Int}
\DeclareMathOperator{\inv}{inv}
\DeclareMathOperator{\Inv}{Inv}
\DeclareMathOperator{\lcm}{lcm}
\DeclareMathOperator{\LHS}{LHS}
\DeclareMathOperator{\Mat}{Mat}
\DeclareMathOperator{\maj}{maj}
\DeclareMathOperator{\mdeg}{mdeg}
\DeclareMathOperator{\Mod}{mod}
\DeclareMathOperator{\NBB}{NBB}
\DeclareMathOperator{\nin}{nin}
\DeclareMathOperator{\Nin}{Nin}
\DeclareMathOperator{\nul}{nul}
\DeclareMathOperator{\nullity}{nullity}
\DeclareMathOperator{\NSym}{{\bf NSym}}
\DeclareMathOperator{\od}{od}
\DeclareMathOperator{\ord}{ord}
\DeclareMathOperator{\per}{per}
\DeclareMathOperator{\Pete}{Pete}
\DeclareMathOperator{\pfa}{pf}
\DeclareMathOperator{\Pm}{pm}
\DeclareMathOperator{\PM}{PM}
\DeclareMathOperator{\Pol}{Pol}
\DeclareMathOperator{\rad}{rad}
\DeclareMathOperator{\RHS}{RHS}
\DeclareMathOperator{\rk}{rk}
\DeclareMathOperator{\rank}{rank}
\DeclareMathOperator{\reg}{reg}
\DeclareMathOperator{\rlm}{rlm}
\DeclareMathOperator{\row}{row}
\DeclareMathOperator{\sdiam}{sdiam}
\DeclareMathOperator{\sgn}{sgn}
\DeclareMathOperator{\sign}{sign}
\DeclareMathOperator{\sh}{sh}
\DeclareMathOperator{\slack}{slack}
\DeclareMathOperator{\spa}{span}
\DeclareMathOperator{\st}{st}
\DeclareMathOperator{\summ}{sum}
\DeclareMathOperator{\Supp}{Supp}
\DeclareMathOperator{\sus}{susp}
\DeclareMathOperator{\Sym}{{\bf Sym}}
\DeclareMathOperator{\SYT}{SYT}
\DeclareMathOperator{\tang}{tang}
\DeclareMathOperator{\tr}{tr}
\DeclareMathOperator{\tri}{tri}
\DeclareMathOperator{\wed}{wedge}
\DeclareMathOperator{\wt}{wt}







\newcommand{\new}[1]{\vs{5pt}\ensuremath{\blacktriangleright}#1\ensuremath{\blacktriangleleft}\vs{5pt}}
\newcommand{\bul}{\bullet}
\newcommand{\dil}{\displaystyle}
\newcommand{\dsum}{\dil\sum}
\newcommand{\dint}{\dil\int}
%\newcommand{\dfrac}{\dil\frac}
\newcommand{\scl}{\scriptstyle}
\newcommand{\ssl}{\scriptscriptstyle}
\newcommand{\foz}{\footnotesize}
\newcommand{\scz}{\scriptsize}
\newcommand{\cho}{\choose}

\newcommand{\Schu}{Sch\"utzenberger}
\newcommand{\aim}{Adv.\ in Math.\/}
\newcommand{\bams}{Bull.\ Amer.\ Math.\ Soc.\/}
\newcommand{\cjm}{Canad.\ J. Math.\/}
\newcommand{\dm}{Discrete Math.\/}
\newcommand{\dmj}{Duke Math.\ J.\/}
\newcommand{\ejc}{European J. Combin.\/}
\newcommand{\jaa}{J. Algebra\/}
\newcommand{\jac}{J. Algebraic Combin.\/}
\newcommand{\jas}{J. Algorithms\/}
\newcommand{\jams}{J. Amer.\ Math.\ Soc.\/}
\newcommand{\jct}{J. Combin.\ Theory\/}
\newcommand{\jcta}{J. Combin.\ Theory Ser. A\/}
\newcommand{\jctb}{J. Combin.\ Theory Ser. B\/}
\newcommand{\jgt}{J. Graph Theory\/}
\newcommand{\jram}{J. Reine Angew.\ Math.\/}
\newcommand{\pjm}{Pacific J. Math.\/}
\newcommand{\pams}{Proc.\ Amer.\ Math.\ Soc.\/}
\newcommand{\plms}{Proc.\ London Math.\ Soc.\/}
\newcommand{\tams}{Trans.\ Amer.\ Math.\ Soc.\/}
\newcommand{\pja}{Proc.\ Japan Acad.\ Ser.\ A  Math\/}
\newcommand{\sv}{Springer-Verlag Lecture Notes in Math.\/}
\newcommand{\crgs}{Combinatoire et Repr\'{e}sentation du 
    Groupe Sym\'{e}trique, Strasbourg 1976, D. Foata ed.}
\newcommand{\caup}{Cambridge University Press}
\newcommand{\oup}{Oxford University Press} 
\newcommand{\pr}{preprint}
\newcommand{\ip}{in preparation}
\newcommand{\ds}{\displaystyle}



\begin{document}

\newbox\Adr
\setbox\Adr\vbox{
\centerline{\sc Rachel Domagalski}
\centerline{\small Department of Mathematics, Michigan State University,}
\centerline{\small East Lansing, MI 48824-1027, USA, {\tt domagal9@msu.edu}}
\vskip6pt
\centerline{\sc Jinting Liang}
\centerline{\small Department of Mathematics, Michigan State University,}
\centerline{\small East Lansing, MI 48824-1027, USA, {\tt liangj26@msu.edu}}
\vskip6pt
\centerline{\sc Quinn Minnich}
\centerline{\small Department of Mathematics, Michigan State University,}
\centerline{\small East Lansing, MI 48824-1027, USA, {\tt minnichq@msu.edu}}
\vskip6pt
\centerline{\sc Bruce E. Sagan}
\centerline{\small Department of Mathematics, Michigan State University,}
\centerline{\small East Lansing, MI 48824-1027, USA, {\tt bsagan@msu.edu}}
\vskip6pt
\centerline{\sc Jamie Schmidt}
\centerline{\small Department of Mathematics, Michigan State University,}
\centerline{\small East Lansing, MI 48824-1027, USA, {\tt schmi710@msu.edu}}
\vskip6pt
\centerline{\sc Alexander Sietsema}
\centerline{\small Department of Mathematics, Michigan State University,}
\centerline{\small East Lansing, MI 48824-1027, USA, {\tt sietsem6@msu.edu}}
}

\title{Cyclic shuffle compatibility}
\author[R. Domagalski, J. Liang, Q. Minnich, B. E. Sagan, J. Schmidt
and A. Sietsema]{\box\Adr}


\catcode`\@=11
\@namedef{subjclassname@2020}{%
  \textup{2020} Mathematics Subject Classification}
\catcode`\@=12

\date{}
\keywords{cyclic permutation, descent, peak, shuffle compatible}
\subjclass[2020]{Primary 05A05; Secondary  05A19}

\begin{abstract}
Consider a permutation $\pi$ to be any finite list of distinct positive integers.  
A statistic is a function $\St$ whose domain is all permutations.
Let $\pi\shu\si$ be the set of shuffles of two disjoint permutations $\pi$  and $\si$.
We say that $\St$ is shuffle compatible if the distribution of $\St$ over $\pi\shu\si$ depends only on $\St(\pi)$, $\St(\si)$, and the lengths of $\pi$ and $\si$.  This notion is implicit in Stanley's work on $P$-partitions and was first explicitly studied by Gessel and Zhuang.
One of the places where shuffles are useful is in describing the product in the algebra of quasisymmetric functions.  Recently Adin, Gessel, Reiner, and Roichman defined an algebra of cyclic quasisymmetric functions where a cyclic version of shuffling comes into play.  The purpose of this paper is to define and study cyclic shuffle compatibility.  In particular, we show how one can lift shuffle compatibility results for (linear) permutations to cyclic ones.  We then apply this result to cyclic descents and cyclic peaks.  We also discuss the problem of finding a cyclic analogue of the major index.
\end{abstract}

\maketitle

\thispagestyle{myheadings}
\font\rms=cmr8 
\font\its=cmti8 
\font\bfs=cmbx8

\markright{\its S\'eminaire Lotharingien de
Combinatoire \bfs 85 \rms (2021), Article~B85d\hfill}
\def\thepage{}

\section{Introduction}

Let $\bbN$ and $\bbP$ be the nonnegative and positive integers, respectively.  If $n\in\bbN$ then let $[n]=\{1,2,\ldots,n\}$.  Given a finite $A\sbe\bbP$ then a {\em linear permutation} of $A$ is a linear arrangement $\pi=\pi_1\pi_2\ldots\pi_n$ of the elements of $A$.  We let 
$$
L(A) = \{\pi \mid \text{$\pi$ is a linear permutation of $A$}\}.
$$
We often drop ``linear" if it is understood from context.  For example,
$$
L(\{1,3,6\})=\{ 136, 163, 316, 361, 613, 631\}.
$$
If $\pi=\pi_1\pi_2\ldots\pi_n$ then $n$ is called the {\em length} of $\pi$, written $\#\pi=|\pi|=n$.  The hash symbol and absolute value sign will also be used for the cardinality of a set.  In fact, we will often treat permutations as sets if no problem will result and write things such as $x\in\pi$ in place of the more cumbersome $\pi_i=x$ for some $i$.

%First page headline in AmS-LaTeX for S\'eminaire Lotharingien de Combinatoire
%--restoring the headers and pagenumbering
\pagenumbering{arabic}
\addtocounter{page}{1}
\markboth{\SMALL R. DOMAGALSKI, J. LIANG, Q. MINNICH, B. E. SAGAN, J. SCHMIDT
AND  A. SIETSEMA}
{\SMALL CYCLIC SHUFFLE COMPATIBILITY}

A {\em (linear) permutation statistic} is a function $\St$ whose domain is all linear permutations.  There are four statistics which will concern us here.  A permutation $\pi=\pi_1\pi_2\ldots\pi_n$
has {\em descent set}
$$
\Des\pi=\{i \mid \pi_i>\pi_{i+1}\},
$$
{\em descent number}
$$
\des\pi=\#\Des\pi,
$$
{\em peak set}
$$
\Pk\pi=\{i \mid \pi_{i-1}<\pi_i>\pi_{i+1}\},
$$
and {\em peak number}
$$
\pk\pi =\#\Pk\pi.
$$
To illustrate, if $\pi=4218596$ then $\Des\pi=\{1,2,4,6\}$,
$\des\pi=4$, $\Pk\pi=\{4,6\}$, and $\pk\pi=2$.  We will be particularly concerned with a particular type of statistic which is determined by the descent set in the following sense.  Statistic $\St$ is a {\em descent statistic} if  $\Des\pi=\Des\si$ and $\#\pi=\#\si$ implies $\St\pi=\St\si$.  Note that $\Des$ itself, $\des$, $\Pk$, and $\pk$ are all descent statistics.  A statistic which is not a descent statistic would be $\St\pi=\pi_1$ for nonempty $\pi$ and $\St\emp=0$.  We will often need to evaluate a statistic $\St$ on a set of permutations $\Pi$.  So we define the {\em distribution} of $\St$ over $\Pi$ to be
$$
\St\Pi=\{\{\St\pi \mid \pi\in\Pi\}\}.
$$
Note that this is a set with multiplicity since $\St$ may evaluate to the same thing on various members of $\Pi$.  We will sometimes use exponents to denote multiplicities where, as usual, no exponent means multiplicity $1$.  For example
$$
\des\{123, 132, 312, 321\} =
\{\{0, 1, 1, 2\}\} = \{\{ 0, 1^2, 2\}\}.
$$
We will also need to combine functions on permutations and statistics.  If $\Pi$ and $\Pi'$ are sets of permutations and $\St$ is a statistic, then a function $f:\Pi\ra\Pi'$ is {\em $\St$-preserving} if $$
\St f(\pi) = \St\pi
$$
for all $\pi\in\Pi$.

If $\pi\in L(A)$ and $\si\in L(B)$ where $A\cap B=\emp$ then these permutations have {\em shuffle set}
$$
\pi\shu\si =\{ \tau\in  L(A\uplus B) \mid
\text{$\pi,\si$ are subwords of $\tau$}\}
$$
where a subwords of a permutation $\tau$  is a subsequence of (not necessarily consecutive) elements of $\tau$.  For example,
\begin{equation}
\label{25s73}
 25\shu 73 = \{2573, 2753, 2735, 7253, 7235, 7325\}.   
\end{equation}
Whenever we write the shuffle of two permutations, we will tacitly assume that they are from disjoint sets.

An important use of the shuffle set is in computing the product of two fundamental quasisymmetric functions in the algebra $\QSym$ of quasisymmetric functions.  More information about $\QSym$ can be found in the texts of Luoto, Mykytiuk, and van Willigenburg~\cite{lmv:iqs}, Sagan~\cite{sag:aoc}, or Stanley~\cite{sta:ec2}.  In order to prove that this product formula is well defined, one needs shuffle compatibility.  Roughly speaking, a statistic $\St$ is shuffle compatible if the distribution of $\St$ over $\pi\shu\si$ depends only on $\St\pi$, $\St\si$, and the lengths $\#\pi$ and $\#\si$.  To be precise, $\St$ is {\em shuffle compatible} if for all quadruples $\pi,\pi',\si,\si'$ with $\St\pi=\St\pi'$, $\St\si=\St\si'$, $\#\pi=\#\pi'$, and $\#\si=\#\si'$ we have
$$
\St(\pi\shu\si) = \St(\pi'\shu\si').
$$
For example, from equation~\eqref{25s73} it is easy to see that
$$
\des(25\shu 73)=\{\{1^3,2^3\}\}
$$
The reader can check that this is also the distribution $\des(12\shu 43)$ which is because $\des$ is shuffle compatible.
Shuffle compatibility is implicit in Stanley's theory of $P$-partitions~\cite{sta:osp} and he proved a result implying the shuffle compatibility of $\des$.  Gessel and Zhuang~\cite{gz:sps} were the first to define the concept explicitly and prove many shuffle compatibility results, including those for the other three statistics defined previously.
\begin{thm}
The statistics
$$
\Des, \des, \Pk, \pk
$$
are all shuffle compatible.\hqed
\end{thm}
\noindent Other work on shuffle compatibility has been done by 
Baker-Jarvis and Sagan~\cite{bs:bps}, by O{\u{g}}uz~\cite{ogu:ces}, and by
Grinberg~\cite{gri:sps}.

Recently Adin, Gessel, Reiner, and Roichman~\cite{agrr:cqf} introduced a cyclic version of quasisymmetric functions with a corresponding cyclic shuffle operation.  A linear permutation $\pi=\pi_1\pi_2\ldots\pi_n$ has a corresponding {\em cyclic permutation} $[\pi]$ which is the set of all its rotations, namely
$$
[\pi]=\{\pi_1\pi_2\ldots,\pi_n,\
\pi_2\ldots,\pi_n\pi_1,\
\ldots,\
\pi_n\pi_1\ldots\pi_{n-1}\}.
$$
For example
$$
[3725]=\{3725, 7253, 2537, 5372\}
$$
so that 
$$
[3725]=[7253]=[2537]=[5372].
$$
The reader should bear in mind the difference between the notation $[n]$ for an interval of integers and $[\pi]$ for a cyclic permutation.
We let
$$
C(A) = \{[\pi] \mid \text{$[\pi]$ is a cyclic permutation of $A$}\}.
$$
To illustrate
$$
C(\{2,3,5,7\})=\{[2357], [2375], [2537], [2735], [2573], [2753]\}.
$$

We can lift the linear permutation statistics we have introduced to the cyclic realm as follows.  Define the {\em cyclic descent set} and {\em cyclic descent number} for a linear permutation $\pi=\pi_1\pi_2\ldots\pi_n$ to be
$$
\cDes\pi =\{i\in[n] \mid 
\text{$\pi_i>\pi_{i+1}$ where $i$ is taken modulo $n$}\}
$$
and
$$
\cdes\pi=\#\cDes\pi,
$$
respectively.
Returning to $\pi=4218596$ we have $\cDes\pi=\{1,2,4,6,7\}$ and $\cdes\pi=5$.  Now  a cyclic permutation $[\pi]$ will have {\em cyclic descent set}
$$
\cDes[\pi]=\{\{\cDes\si \mid \si\in[\pi]\}\}.
$$
Notice that this is a multiset since two different $\si$ can have the same cyclic descent set.  Also define the {\em cyclic descent number}
$$
\cdes[\pi]=\cdes\pi.
$$
Note that this is well defined since all elements of $[\pi]$ have the same number of cyclic descents.  To illustrate
$$
\cDes[3725] =\{\{\cDes 3725, \cDes 7253, \cDes 2537, \cDes 5372\}\}
=\{\{\ \{1,3\}^2,\ \{2,4\}^2\ \}\}
$$
and $\cdes[3725]=2$.  An important point later will be that if $S$ is one of the sets in $\cDes[\pi]$ then all of the other member sets can be obtained by adding $i$ to the elements of $S$ modulo $n=\#\pi$ as $i$ runs over $[n]$. 

We deal with peaks in a similar manner, defining the {\em cyclic peak set} and {\em cyclic peak number} in the linear case by
$$
\cPk\pi =\{i\in[n] \mid 
\text{$\pi_{i-1}<\pi_i>\pi_{i+1}$ where $i$ is taken modulo $n$}\}
$$
and
$$
\cpk\pi=\#\cpk\pi,
$$
respectively.  For $\pi=4218593$ we have $\cPk\pi=\{1,4,6\}$ and $\cpk\pi=3$.  The extension to cyclic permutations is as expected
$$
\cPk[\pi]=\{\{\cPk\si \mid \si\in[\pi]\}\}
$$
and
$$
\cpk[\pi]=\cpk\pi.
$$
In general, a {\em cyclic permutation statistic} is any function $\cSt$ whose domain is cyclic permutations.  And $\cSt$ is a {\em cyclic descent statistic}
if  $\cDes[\pi]=\cDes[\si]$ and $\#\pi=\#\si$ implies $\cSt[\pi]=\cSt[\si]$.  All four of our cyclic statistics are cyclic descent statistics.
Functions preserving cyclic permutation statistics are defined in the obvious way.

The definitions for shuffles follow the same pattern already established.
Given $[\pi]\in C(A)$ and $[\si]\in C(B)$ where $A\cap B=\emp$ we define their {\em cyclic shuffle set} to be
$$
[\pi]\shu[\si] =\{[\tau]\in C(A\uplus B) \mid
\text{$[\pi],[\si]$ are circular subwords of $[\tau]$}\}.
$$
Alternatively, there are rotations $\pi'$ and $\si'$ of $\pi$ and $\si$, respectively, which are both linear subwords of $\tau$.  To illustrate,
\begin{equation}
\label{13s24}
[13]\shu [24] = \{[1324], [1342], [1234], [1432], [1243], [1423]\}.    
\end{equation}
Call a cyclic permutation statistic $\cSt$ {\em cyclic shuffle compatible}
if for all quadruples $[\pi]$, $[\pi']$, $[\si]$, $[\si']$ with $\cSt[\pi]=\cSt[\pi']$, $\cSt[\si]=\cSt[\si']$, $\#\pi=\#\pi'$, and $\#\si=\#\si'$ we have
$$
\cSt([\pi]\shu[\si]) = \cSt([\pi']\shu[\si']).
$$
The aim of the present work is to study this concept.  In particular, we will prove the following theorem.
\begin{thm}
\label{cSt}
The statistics
$$
\cDes, \cdes, \cPk, \cpk
$$
are all cyclic shuffle compatible.
\end{thm}

The rest of this paper is structured as follows.
Rather than proving each of the cases of Theorem~\ref{cSt} in an ad hoc manner, we will develop a method for lifting linear shuffle compatibility results to cyclic ones.  This will be done in the next section.  Then in Section~\ref{a} we will apply our Lifting Lemma to each of the four statistics in turn.  Finally, we will end with a section of comments and a future direction for research.


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

\section{The Lifting Lemma}
\label{llSec}

In this section we will provide a general method for proving cyclic shuffle compatibility results as corollaries of linear ones.  We will first set some notation. 
In the notations like $C(A)$ and $L(A)$ we will often drop the parentheses if they would cause double delimiters.  For example $L[n]$ is all the linear permutations of $[n]$.

If $A\sbs\bbP$ and $n\in\bbN$ then let
$$
A+n = \{a+n \mid a\in A\}.
$$
In particular,
$$
[m]+n = \{n+1,n+2,\ldots,n+m\}.
$$
We will also need to add integers to sets modulo some $m\in\bbP$.  So if $A\sbe[m]$ then define
$$
A+n\ (\Mod m) =\{a+n\ (\Mod m) \mid a\in A\}
$$
where the representatives are chosen to be in $[m]$.  For example
if $A=\{2,4,5\}$ and $m=6$ then
$$
A+3 = \{5,7,8\}
$$
and
$$
A+3\ (\Mod 6) = \{1,2,5\}.
$$


We will also need the notion of standardization.  Suppose $A,B\sbs\bbP$  with $\#A=\#B=n$ and 
$\pi=\pi_1\pi_2\ldots\pi_n\in L(A)$.  The {\em standardization of $\pi$ to $B$} is 
$$
\std_B \pi=f(\pi_1) f(\pi_2)\ldots f(\pi_n)\in L(B)
$$
where $f:A\ra B$ is the unique order-preserving bijection between $A$ and $B$.  To illustrate, if $A=\{2,4,6,7\}$ and $B=\{1,3,8,9\}$ then
$\std_B(4762) = 3981$.  If $B=[n]$ then we write just $\std \pi$ for $\std_{[n]} \pi$ and call this the {\em standardization} of $\pi$.  Standardization for cyclic permutations is defined in the analogous manner.  For example, $\std [79254] = [45132]$.

We first prove a result about cyclic descent statistics which is a cyclic analogue of one in the linear case~\cite{bs:bps}.
\begin{lem}
\label{cStLem}
Let $\cSt$ be a cyclic descent statistic.  For any four cyclic permutations $[\pi]$, $[\pi']$, $[\si]$, $[\si']$ such that 
$$
\std[\pi]=\std[\pi'] \qmq{and} \std[\si]=\std[\si']
$$
we have
$$
\cSt([\pi]\shu[\si]) = \cSt([\pi']\shu[\si']).
$$
\end{lem}
\begin{proof}
Since $\cSt$ is a cyclic descent statistic, its values only depend on the relative order of adjacent elements.  So it suffices to prove the case when
$$
[\pi]\uplus[\si] = [\pi']\uplus[\si'] = [m+n]
$$
where $m=\#\pi=\#\pi'$ and $n=\#\si=\#\si'$.  For simplicity, let $A=[m]$ and $B=[n]+m$.

We claim that it suffices to find, for any $\pi$ and $\si$ as in the previous paragraph, a $\cSt$-preserving bijection
$$
[\pi]\shu[\si] \ra\std_A[\pi]\shu\std_B[\si].
$$
For from this map and the hypothesis of the lemma we have
$$
\cSt([\pi]\shu[\si]) =\cSt(\std_A[\pi]\shu\std_B[\si])
=\cSt(\std_A[\pi']\shu\std_B[\si'])= \cSt([\pi']\shu[\si']).
$$

We will show the existence of this bijection by induction on the size of the set of what we will call out-of-order pairs
$$
O=\{(i,j) \in \pi\times \si \mid i>j\}. 
$$
If $\#O=0$ then $[\pi]\in C(A)$ and $[\si]\in C(B)$.  It follows that
$[\pi]=\std_A[\pi]$ and $[\si]=\st_B[\si]$ so the identity map will do.

For the induction step, let $\#O>0$.  Then there must be a pair $(i,i-1)\in O$.  Let $\pi''=(i-1,i)\pi$ and $\si''=(i-1,i)\si$ where $(i-1,i)$ is the transposition which exchanges $i-1$ and $i$.
We will be done if we can construct a $\cSt$ preserving bijection
$$
T_i:[\pi]\shu[\si] \ra [\pi'']\shu[\si''].
$$
This is because $\pi'',\si''$ have fewer out-of-order pairs and so, by induction, there is a $\cSt$-preserving bijection
$[\pi'']\shu[\si''] \ra\std_A[\pi'']\shu\std_B[\si'']$ which, when composed with $T_i$, will finish the construction.

Define $T_i$ by
$$
T_i[\tau]=
\begin{cases}
[(i-1,i)\tau] &\text{if $i-1,i$ are not cyclically adjacent in $[\tau]$,}\\
[\tau]  & \text{else.}
\end{cases}
$$
We must first check that $T_i$ is well defined in that $T_i[\tau]\in[\pi'']\shu[\si'']$.  This is true if $i-1$ and $i$ are not cyclically adjacent since $i-1$ and $i$ have been swapped in all three cyclic permutations involved.  If they are adjacent then the relative order of the elements of $[\tau]$ corresponding to $[\pi]$ and $[\pi'']$ are the same, and similarly for $[\si]$ and $[\si'']$.  So leaving $[\tau]$ fixed again gives a shuffle in the range.

Finally, we need to verify that $T_i$ is $\cSt$ preserving.  Since $\cSt$ is a descent statistic, it suffices to show that $T_i$ is $\cDes$ preserving.  Certainly this is true if $[\tau]$ is fixed.  And if it is not, then $i-1,i$ are not cyclically adjacent in $[\tau]$.  But switching $i-1$ and $i$ could only change a cyclic descent into a cyclic ascent or vice-versa if these two elements were adjacent.  So in this case $\cDes[(i-1,i)\tau]=\cDes[\tau]$ and we are done.
\end{proof}

As an example of the map $T_i$, consider the shuffle set in~\eqref{13s24}.  Here we can take $i=3$ since $3\in 13$ and $2\in 24$.  For $[\tau]=[1324]$ we have $2$ and $3$ cyclically adjacent so
$$
T_3[1324]=[1324]\in[12]\shu[34]
$$
as desired.  On the other hand, in $[1342]$ the $2$ and $3$ are not cyclically adjacent so
$$
T_3[1342]=[1243].
$$
Note that $[1243]\in[12]\shu[34]$ and 
$$
\cDes [1243] = \{\{\ \{1,2\},\ \{2,3\},\ \{3,4\},\ \{1,4\}\ \}\}
=\cDes [1342].
$$

We can use the previous lemma to drastically cut down on the number of cases which need to be checked to obtain cyclic shuffle compatibility.  In particular, the component permutations in the shuffles to be considered can be on consecutive intervals of integers.  And one can keep one component of the shuffle constant while the other varies.  
\begin{cor}
\label{cStCor}
Suppose that $\cSt$ is  cyclic descent statistic.  The following are equivalent.
\begin{enumerate}
    \item[(a)]  The statistic $\cSt$ is cyclic shuffle compatible.
    \item[(b)]  If $\cSt([\pi])=\cSt([\pi'])$ where $[\pi],[\pi']\in C[m]$ and
    $[\si]\in C([n]+m)$ for some $m,n\in\bbN$ then
    $$
    \cSt([\pi]\shu[\si]) =\cSt([\pi']\shu [\si]).
    $$
    \item[(c)] If $\cSt([\si])=\cSt([\si'])$ where $[\si],[\si']\in C([n]+m)$ and
    $[\pi]\in C[m]$ for some $m,n\in\bbN$ then
    $$
    \cSt([\pi]\shu[\si]) =\cSt([\pi]\shu [\si']).
    $$ 
\end{enumerate}
\end{cor}
\begin{proof}
We will prove the equivalence of (a) and (b) since the equivalence of (a) and (c) is similar.  Clearly (a) implies (b).  For the converse, let $\pi,\pi',\si,\si'$ be any four permutations satisfying the hypothesis of the cyclic shuffle compatible definition and let $m=\#\pi=\#\pi'$, $n=\#\si=\#\si'$.  Also let
$A=[m]$, $B=[n]+m$, $A'=[m]+n$, and $B'=[n]$.  Then, using Lemma~\ref{cStLem} and (b) alternately
\begin{align*}
 \cSt([\pi]\shu[\si])
&=\cSt(\std_A[\pi] \shu \std_B[\si])\\ 
&=\cSt(\std_A[\pi'] \shu \std_B[\si])\\
&=\cSt(\std_{A'}[\pi'] \shu \std_{B'}[\si])\\
&=\cSt(\std_{A'}[\pi'] \shu \std_{B'}[\si'])\\
&= \cSt([\pi']\shu[\si'])
\end{align*}
which is what we wished to prove.
\end{proof}

In order to prove the Lifting Lemma, we will need to define two functions.
For $i\in[n]$ we construct the {\em splitting map} $S_i:C[n]\ra L[n]$ as follows.  If $[\pi]\in C[n]$ then let $S_i[\pi]$ be the unique linear permutation in $[\pi]$ which starts with $i$.  For example,
$$
S_3[45132] = 32451.
$$

Also define the {\em maximum removal} map $M:C[n]\ra L[n-1]$ by first applying $S_n$ to $[\pi]$ and then removing the initial $n$.  To illustrate
$$
M[45132] = 1324.
$$
Note that $M$ is a bijection.  We similarly define
$M:C([n]+m)\ra L([n-1]+m)$ using $m+n$ in place of $n$, as in
$$
M[67354] = 3546.
$$

Finally, we say that $y$ is {\em between} $x$ and $z$ in $[\pi]$ if this is true of any linear permutation in $[\pi]$ where $x$ occurs to the left of $z$.
If $[\pi]\in C[m]$, $i\in[m]$, and $[\si]\in C([n]+m)$ define
$$
[\pi]\shu_i [\si] = \{[\tau]\in [\pi]\shu [\si] \mid \text{only elements of $\si$ are between $m+n$ and $i$ in $[\tau]$}\}.
$$
For example,
$$
[12]\shu[34] = 
\{[1234], [1243], [1324], [1423], [1342], [1432]\}
$$
with
$$
[12]\shu_1 [34] = 
\{[1234], [1243], [1324]\} 
$$
and
$$
[12]\shu_2 [34] = \{[1423], [1342], [1432]\}.
$$
Note that $[\pi]\shu [\si]$ is the disjoint union of the 
$[\pi]\shu_i [\si]$ for $i\in[m]$ since we can decompose the full shuffle set by finding the first element $i\in[m]$ that one encounters cyclically after $m+n$.

\begin{lem}[\sc Lifting Lemma]
\label{ll}
Let $\cSt$ be a cyclic descent statistic and $\St$ be a shuffle compatible linear descent statistic such that the following conditions hold.
\begin{enumerate}
    \item[(a)] For any $[\tau],[\tau']$ of the same length
    $$
    \St(M[\tau])=\St(M[\tau']) \qmq{implies} \cSt[\tau]=\cSt[\tau'].
    $$
    \item[(b)] Given any $[\pi],[\pi']\in C[m]$ such that $\cSt[\pi]=\cSt[\pi']$, there exists a bijection $f:[m]\ra[m]$ such that for all $i$ and $j=f(i)$
    $$
    \St(S_i[\pi]) = \St(S_j[\pi']).
    $$
\end{enumerate}
Then $\cSt$ is cyclic shuffle compatible.
\end{lem}
\begin{proof}
By Corollary~\ref{cStCor}, it suffices to show that if $[\pi],[\pi']$ are as given in (b) and $\si\in C([n]+m)$ then $\cSt([\pi]\shu[\si]) =\cSt([\pi']\shu [\si])$.  The remarks preceding the lemma show that this reduces to proving
\begin{equation}
\label{shu_i}
   \cSt([\pi]\shu_i [\si]) =\cSt([\pi']\shu_j [\si]) 
\end{equation}
for all $i\in[m]$ and $j=f(i)$.

It follows that $\St(S_i[\pi]) = \St(S_j[\pi'])$ by (b).  So, since $\St$ is shuffle compatible, we have
$\St(S_i[\pi]\shu \si') = \St(S_j[\pi']\shu \si')$
where $\si'=M[\si]$.  Thus there is an $\St$-preserving bijection
$$
\th:S_i[\pi]\shu \si' \ra S_j[\pi']\shu \si'.
$$
This gives rise to a map
$$
\th':[\pi]\shu_i [\si]
\stackrel{M}{\ra} S_i[\pi]\shu \si'
\stackrel{\th}{\ra} S_j[\pi']\shu \si'
\stackrel{M^{-1}}{\ra} [\pi']\shu_j [\si]
$$
Since this is a bijection, to show~\eqref{shu_i} it suffices to 
prove that $\th'$ is $\cSt$-preserving.  So
take $[\tau]\in [\pi]\shu_i [\si]$ and $[\tau']=\th'[\tau]$.
Then $M[\tau'] = \th\circ M[\tau]$.  Since $\th$ is $\St$ preserving, we have $\St M[\tau'] = \St M[\tau]$.  But then hypothesis (a) implies that $\cSt[\tau]=\cSt[\tau']$ which is what we wished to prove.
\end{proof}


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

\section{Applications}
\label{a}

The hypotheses in the Lifting Lemma may seem strange at first glance.  But they can be quite easy to verify, making it a useful tool.  We will see four instances of this by proving Theorem~\ref{cSt} using its aid.

\begin{thm}
\label{cDes}
The statistic $\cDes$ is cyclic shuffle compatible.
\end{thm}
\begin{proof}
We will verify the hypotheses of Lemma~\ref{ll} using $\St=\Des$.  For (a), suppose that $\#\tau=\#\tau'=n$ and 
\begin{equation}
\label{Des=}  
\Des(M[\tau])=\Des(M[\tau']).
\end{equation}
Let us assume that $\tau,\tau'$ were chosen from their cyclic equivalence class so that $\tau_1=\max\tau$ and similarly for $\tau'$.  Then $M[\tau]=\tau_2\tau_3\ldots\tau_n$.  And by the choice of $\tau_1$ we see that
\begin{equation}
\label{U1}  
\Des\tau=\{1\}\uplus(\Des M[\tau]+1).
\end{equation}
  Since the same statement holds with $\tau'$ in place of $\tau$ and~\eqref{Des=} holds, we have
$\Des\tau=\Des\tau'$.  But $\Des\tau$ is one set in the multiset $\cDes[\tau]$, and the others are gotten by adding each $i\in[n]$ to all elements of $\Des\tau$ modulo $n$.  The same being true of $\cDes[\tau']$ shows that
$\cDes[\tau]=\cDes[\tau']$ as desired.

For (b), we are given $[\pi],[\pi']\in C[m]$ with $\cDes[\pi]=\cDes[\pi']$ and must construct the necessary bijection.  From this assumption, we can choose $\pi$ and $\pi'$ such that 
\begin{equation}
\label{cDes=}
\cDes\pi=\cDes\pi'=A.   
\end{equation}
for some set $A$.  Define $f:[m]\ra[m]$ by
$f(\pi_k)=\pi_k'$ for all $k\in[m]$.  Let $i=\pi_k$ and $j=\pi_k'$.  To show that $\Des(S_i[\pi])=\Des(S_j[\pi'])$ there are two cases depending on whether $k-1\in A$ or not, where $k-1$ is taken modulo $m$. 

If $k-1\not\in A$ then $\pi_k,\pi_k'$ are not the second elements in cyclic descents of their respective  permutations.  From this and equation~\eqref{cDes=} it follows that
$$
\Des(S_i[\pi]) = A - k + 1\ (\Mod m) = \Des(S_j[\pi']).
$$
If $k-1\in A$ then the same equalities hold with $A$ replaced by $A'$ which is $A$ with $k-1$ removed.  The completes the proof of (b) and of the theorem.
\end{proof}

\begin{thm}
\label{cdes}
The statistic $\cdes$ is cyclic shuffle compatible.
\end{thm}
\begin{proof}
We proceed as in the previous proof with $\St=\des$.  For (a) we  assume $\des(M[\tau])=\des(M[\tau'])$.  But from equation~\eqref{U1} we see that $\des\tau=\des(M[\tau]) - 1$ and the same is true for $\tau'$.   Combining this with our initial assumption gives $\des\tau=\des\tau'$.  But $\tau,\tau'$ begin with their largest element so that
$$
\cdes[\tau]=\des\tau=\des\tau'=\cdes[\tau']
$$
which is what we wished to show.

To prove (b), we are given $\cdes[\pi]=\cdes[\pi']$.  As in the preceding paragraph, choose $\pi,\pi'$ to begin with their largest elements so that $\cdes[\pi]=\des\pi$ and similarly for $\pi'$.  Since $\des\pi=\des\pi'$ there is a bijection $\th:\Des\pi\ra\Des\pi'$.  Extend this map to $\th:[m]\ra[m]$ by using any bijection between the complements of $\Des\pi$ and $\Des\pi'$.  The proof that $\th$ has the desired property is now similar to that for $\Des$ and so is left to the reader.
\end{proof}

\begin{thm}
\label{cPk}
The statistic $\cPk$ is cyclic shuffle compatible.
\end{thm}
\begin{proof}
This proof parallels the one for $\cDes$, so we will only mention the highlights.  For (a) one sees that $\Pk\tau = \Pk M[\tau]+1$ since $\tau_1=\max\tau$ is not a peak in $\tau$ and is removed in $M[\tau]$.  But this still implies that $\Pk\tau=\Pk\tau'$ and the rest of this part of the demonstration goes through.

For (b), the map $\th$ is constructed in exactly the same way using 
$A=\cPk\pi=\cPk\pi'$.  The only difference with the remaining part of the proof is that there are two subcases when $k-1\not\in A$ depending on whether $k-2\in A$ or not.  If $k-2\in A$ then one loses the peak which was at $\pi_{k-2}$ in $S_i[\pi]$.  On the other hand, the peak set stays the same modulo rotation if $k-2\not\in A$.  But since the analogous statements hold for $\pi'$, the manipulations in these subcases are as before.
\end{proof}

The proof of the next result is based on the proof of Theorem~\ref{cPk} in much the same way that the demonstrations of Theorems~\ref{cDes} and~\ref{cdes} are related.  So the details are left to the reader.
\begin{thm}
\label{cpk}
The statistic $\cpk$ is cyclic shuffle compatible.\hqed
\end{thm}

Lest it appear that cyclic shuffle compatibility follows exactly the same lines as the linear case, let us point out a place where they differ.  
Define a {\em factor} of $\pi$ to be a subsequence of consecutive elements.
A {\em birun} of $\pi$ is a maximal monotone factor.
Let $\bru\pi$ be the number of biruns of $\pi$.  For example,
$\bru 125346= 3$ because of the biruns $125$, $53$, and $346$.
It is easy to see~\cite{gz:sps} that the birun statistic is not linearly
shuffle compatible.
A {\em cyclic birun} of $[\pi]$ is defined in the obvious manner and denoted $\cbru[\pi]$.  Returning to our example,
$\cbru [125346]= 4$ because of the biruns above and $61$.
\begin{thm}
The statistic $\cbru$ is cyclic shuffle compatible.
\end{thm}
\begin{proof}
Clearly cyclic biruns always begin  at a cyclic peak and end at a cyclic valley, or vice-versa.  So $\cbru[\pi]=2\cpk[\pi]$ and the result follows from 
Theorem~\ref{cpk}.
\end{proof}

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

\section{Remarks and an open question}
\label{roq}

\subsection{Cyclic pattern avoidance and statistics}

We say that $[\si]\in C[n]$ {\em contains the pattern} $[\pi]\in C[m]$ if there is some subsequence $[\si']$ of $[\si]$ such that $\std[\si']=[\pi]$.  Otherwise $[\si]$ {\em avoids} $[\pi]$.  For any set $[\Pi]$ of cyclic permutations we let
$$
\Av_n[\Pi]=\{[\si]\in C[n] \mid 
\text{$[\si]$ avoids $[\pi]$ for all $[\pi]\in[\Pi]$}\}.
$$
Callan calculated $\#\Av_n[\Pi]$ when $[\Pi]$ consists of a single element of $C[4]$.  Gray, Lanning, and Wang then contributed work on cyclic packing of patterns~\cite{GLW:pcc1} and patterns in colored cyclic permutations~\cite{GLW:pcc2}.  Most recently, the authors of this article determined $\#\Av_n[\Pi]$ for all 
$[\Pi]\sbe C[4]$.  They also calculated the generating function
$$
D_n([\Pi];q) =\sum_{[\si]\in\Av_n[\Pi]} q^{\cdes[\si]}.
$$
for the same sets of patterns.

\subsection{Cyclic maj?}

One famous linear statistic which we have not discussed so far is the {\em major index} of $\pi$ which is
$$
\maj\pi=\sum_{i\in\Des\pi} i.
$$
 Stanley's theory of $P$-partitions~\cite{sta:osp} shows that
 if $\#\pi=m$ and $\#\si=n$ then
$$
\sum_{\tau\in\pi\shu\si} q^{\maj\tau}
=q^{\maj\pi+\maj\si}\gauss{m+n}{m}_q
$$
where the last factor is a $q$ binomial coefficient.  Note that this is a $q$-analogue of the fact that $\#(\pi\shu\si)=\binom{m+n}{m}$.

It is easy to see that
\begin{equation}
\label{ShuCard}
  \#([\pi]\shu[\si]) = (m+n-1) \binom{m+n-2}{m-1}.  
\end{equation}
Indeed, write each $[\tau]$ in the shuffle so that it starts with  $\pi_1$.  Then there are $m+n-1$ more slots to be filled and $m-1$ of them must be for the elements $\pi_2\pi_3\ldots\pi_m$ in that order.  The remaining slots can be filled with any of the $n$ rotations of $\si$ for a total of $n\binom{m+n-1}{m-1}$ choices.  This is equivalent to the formula above.  In~\cite{agrr:cqf} the following question was raised.
\begin{question}
Is there a cyclic analogue of $\maj$ which has nice properties such as giving a $q$-analogue of equation~\eqref{ShuCard}?
\end{question}
More generally, one could try to find shuffle compatible cyclic analogues of other linear statistics. 


%\bibliographystyle{plain}

%\nocite{*}
%\bibliographystyle{abbrvnat}

\nocite{*}
\bibliographystyle{alpha}

\newcommand{\etalchar}[1]{$^{#1}$}
\begin{thebibliography}{LMvW13}

\bibitem[AGRR20]{agrr:cqf}
Ron~M. Adin, Ira~M. Gessel, Victor Reiner, and Yuval Roichman.
\newblock Cyclic quasi-symmetric functions.
\newblock {\em Israel J. Math.}, 243(1):437--500, 2021.

\bibitem[BJS20]{bs:bps}
Duff Baker-Jarvis and Bruce~E. Sagan.
\newblock Bijective proofs of shuffle compatibility results.
\newblock {\em Adv. Appl. Math.}, 113:101973, 29, 2020.

\bibitem[Cal]{cal:pac}
David Callan.
\newblock Pattern avoidance in circular permutations.
\newblock See preprint at {\texttt{arXiv:0210014}}.

\bibitem[DLM{\etalchar{+}}]{dlmsss:cpca}
Rachel Domagalski, Jinting Liang, Quinn Minnich, Bruce Sagan, Jamie Schmidt,
  and Alexander Sietsema.
\newblock Cyclic pattern containment and avoidance.
\newblock See preprint at {\texttt{arXiv:2106.02534}}.

\bibitem[GLW18]{GLW:pcc1}
Daniel Gray, Charles Lanning, and Hua Wang.
\newblock Pattern containment in circular permutations.
\newblock {\em Integers}, 18B:Paper No. A4, 13, 2018.

\bibitem[GLW19]{GLW:pcc2}
Daniel Gray, Charles Lanning, and Hua Wang.
\newblock Patterns in colored circular permutations.
\newblock {\em Involve}, 12(1):157--169, 2019.

\bibitem[Gri18]{gri:sps}
Darij Grinberg.
\newblock Shuffle-compatible permutation statistics {II}: the exterior peak
  set.
\newblock {\em Electron. J. Combin.}, 25(4):Paper No. 4.17, 61, 2018.

\bibitem[GZ18]{gz:sps}
Ira~M. Gessel and Yan Zhuang.
\newblock Shuffle-compatible permutation statistics.
\newblock {\em Adv. Math.}, 332:85--141, 2018.

\bibitem[LMvW13]{lmv:iqs}
Kurt Luoto, Stefan Mykytiuk, and Stephanie van Willigenburg.
\newblock {\em An introduction to quasisymmetric {S}chur functions,
Hopf algebras, quasisymmetric functions, and Young composition
  tableaux}.
\newblock SpringerBriefs in Mathematics. Springer, New York, 2013.

\bibitem[O{\u{g}}u]{ogu:ces}
Ezgi~Kantarc{\i} O{\u{g}}uz.
\newblock A counter example to the shuffle compatibility conjecture.
\newblock Preprint {\texttt{arXiv:1807.01398}}.

\bibitem[Sag20]{sag:aoc}
Bruce~E. Sagan.
\newblock {\em Combinatorics: {T}he art of counting}, volume 210 of {\em
  Graduate Studies in Mathematics}.
\newblock American Mathematical Society, Providence, R.I., 2020.

\bibitem[Sta72]{sta:osp}
Richard~P. Stanley.
\newblock {\em Ordered structures and partitions}.
\newblock Memoirs of the American Mathematical Society, No.~119.
\newblock American Mathematical Society, Providence, R.I., 1972.

\bibitem[Sta99]{sta:ec2}
Richard~P. Stanley.
\newblock {\em Enumerative combinatorics. {V}ol.~2}, volume~62 of {\em
  Cambridge Studies in Advanced Mathematics}.
\newblock Cambridge University Press, Cambridge, 1999.

\end{thebibliography}





\end{document}
