%Shifted Quasi-Symmetric Functions and the Hopf algebra of peak functions % % % Nantel Bergeron % Stefan Mykytiuk % Frank Sottile % Stephanie van Willigenburg % % \documentclass[12pt]{amsart} \usepackage{amsmath,amssymb, epsf} \newtheorem{theorem}{Theorem}[section] \newtheorem{proposition}[theorem]{Proposition} \newtheorem{definition}[theorem]{Definition} \newtheorem{corollary}[theorem]{Corollary} \newtheorem{lemma}[theorem]{Lemma} \newtheorem{conj}[theorem]{Conjecture} \newenvironment{conjecture}{\begin{conj}\rm}{\end{conj}} \newtheorem{example}[theorem]{Example} \newenvironment{remark}{\noindent\textbf{Remark}}{} \newcommand{\three}{\ensuremath{3^{(i)}}} \newcommand{\thetabh}{\ensuremath{\theta^{BH}}} \newcommand{\wbar}{\ensuremath{I(\tilde{\alpha})}} \newcommand{\W}{\ensuremath{{I(\alpha)}}} \newenvironment{resume}{\noindent\textsc{R\'esum\'e}. }{} \headheight=8pt \topmargin=0pt \textheight=624pt \textwidth=432pt \oddsidemargin=18pt \evensidemargin=18pt \parskip 0.1in \parindent 0pt \begin{document} \title[The Hopf algebra of peak functions]{Shifted Quasi-Symmetric Functions and the Hopf algebra of peak functions} \author[N.~Bergeron, S.~Mykytiuk, F.~Sottile, \and S.~van Willigenburg]{Nantel Bergeron \and Stefan Mykytiuk \and Frank Sottile \and Stephanie~van~Willigenburg} \address[Nantel Bergeron and Stefan Mykytiuk and Stephanie van Willigenburg] {Department of Mathematics and Statistics\\ York University\\ Toronto, Ontario M3J 1P3\\ CANADA} \address[Frank Sottile]{Department of Mathematics\\ University of Wisconsin\\ Van Vleck Hall\\ 480 Lincoln Drive\\ Madison, Wisconsin 53706-1388\\ USA} \email[Nantel Bergeron]{bergeron@mathstat.yorku.ca} \urladdr[Nantel Bergeron]{http://www.math.yorku.ca/bergeron} \email[Stefan Mykytiuk]{Mykytiuk@pascal.math.yorku.ca} \email[Frank Sottile]{sottile@math.wisc.edu} \urladdr[Frank Sottile]{http://www.math.wisc.edu/\~{}sottile} \email[Stephanie van Willigenburg]{steph@pascal.math.yorku.ca} \urladdr[Stephanie van Willigenburg]% {http://www-theory.dcs.st-and.ac.uk/\~{}stephvw} \date{\today} \thanks{Bergeron supported in part by NSERC} \thanks{Sottile supported in part by NSF grant DMS-9701755 and NSERC grant OGP0170279} \thanks{van Willigenburg is supported in part by the Leverhulme Trust} \subjclass{05E15, 05E05, 05A15, 16W30} \keywords{Pieri, graded operation, poset, quasi-symmetric functions} \maketitle \def\baselinestretch{.90} \begin{center} \begin{minipage}[t]{5in}\footnotesize {\sc Summary.} In his work on $P$-partitions, Stembridge defined the algebra of peak functions $\Pi$, which is both a subalgebra and a retraction of the algebra of quasi-symmetric functions. We show that $\Pi$ is closed under coproduct, and therefore a Hopf algebra, and describe the kernel of the retraction. Billey and Haiman, in their work on Schubert polynomials, also defined a new class of quasi-symmetric functions --- shifted quasi-symmetric functions --- and we show that $\Pi$ is strictly contained in the linear span $\Xi$ of shifted quasi-symmetric functions. We show that $\Xi$ is a coalgebra, and compute the rank of the $n$th graded component. \bigskip {\sc R\'esum\'e.} Dans ses travaux sur les P-partitions, Stembridge d\'efinit l'alg\`ebre $\Pi$ des fonctions de pics. Cette alg\`ebre peut \^etre vue comme une sous-alg\`ebre ou un quotient de l'alg\`ebre des fonctions quasi-sym\'etriques. Nous montrons ici que $\Pi$ est ferm\'ee sous le coproduit, et est donc une alg\`ebre de Hopf. Nous d\'ecrivons aussi le noyau du quotient ci-dessus. D'autre part, dans leurs travaux sur les polyn\^omes de Schubert, Billey et Haiman ont d\'efini une nouvelle classe de fonctions quasi-sym\'etriques: les fonctions quasi-sym\'etrique d\'ecal\'e. Nous montrons que $\Pi$ est strictement contenue dans l'espace lin\'eaire $\Xi$ des fonctions quasi-sym\'etrique gauchis. Puis nous montrons que $\Xi$ est une coalg\`ebre et calculons les dimensions des composantes de degr\'ee $n$. \end{minipage} \end{center} \def\baselinestretch{1.00} \section{Introduction} Schur $Q$ functions first arose in the study of projective representations of $S_n$ \cite{sch-ur}. Since then they have appeared in variety of contexts including the representations of Lie superalgebras \cite{serg-eev} and cohomology classes dual to Schubert cycles in isotropic Grassmanians \cite{joze-fiak,prag-acz}. While studying the duality between skew Schur $P$ and $Q$ functions and their connection to the Schubert calculus of isotropic flag manifolds, we were led to their quasi-symmetric analogues: the \emph{peak functions} of Stembridge \cite {stem-bridge}. We show that \emph{the linear span of peak functions is a Hopf algebra} (Theorem~\ref{peak-coalg}). We also show that these peak functions are contained in the strictly larger set of \emph{shifted quasi-symmetric functions} (Theorem~\ref{kw-thetabh}) introduced by Billey and Haiman \cite{billey-haiman}. We remark that the quasi-symmetric functions here are not any apparent specialization of the quasi-symmetric $q$-analogues of Hivert \cite{Hivert}. {}From extensive calculations, we believe that the set of all shifted quasi-symmetric functions form a Hopf algebra, but at present we can only show that: \emph{The set of all shifted quasi-symmetric functions forms a graded coalgebra whose $n$th graded component has rank $\pi_n$, where $\pi_n$ is given by the recurrence} \[ \pi_n=\pi_{n-1}+\pi_{n-2} +\pi_{n-4},\] \emph{with initial conditions $\pi_1=1$, $\pi_2=1$, $\pi_3=2$, $\pi_4=4$.} We shall prove this result (Theorems~\ref{sqs-coalg} and~\ref{graded-rank}) and in addition shall establish some other properties of these functions. A composition $\alpha =[\alpha_1,\alpha_2, \ldots ,\alpha_k]$ of a positive integer $n$ is an ordered list of positive integers whose sum is $n$. We denote this by $\alpha \vDash n$. We call the integers $\alpha_i$ the \textit{components} of $\alpha$, and denote the number of components in $\alpha$ by $k(\alpha)$. There exists a natural one-to-one correspondence between compositions of $n$ and subsets of $[n-1]$. If $A=\{ a_1,a_2,\ldots ,a_{k-1}\}\subset[n-1]$, where $a_11$, for $i>1$, by $[1,\beta_i-1]$. Thus the LHS of equation (\ref{delta-eq}) is equal to \begin{eqnarray} \sum_{\stackrel{ \stackrel{\mbox{\scriptsize$\beta\vDash n$}} {\mbox{\scriptsize$\beta^\ast\preccurlyeq\alpha$}}} {\mbox{\scriptsize$\beta=\gamma\cdot\delta$}}} 2^{k(\beta)} M_\gamma \otimes M_\delta &=&\sum_{\stackrel{\mbox{\scriptsize$\gamma\cdot\delta\vDash n$}}{(\gamma\cdot\delta)^\ast\preccurlyeq\alpha}} 2^{k(\gamma)}M_\gamma\otimes 2^{k(\delta)}M_\delta. \label{2delta-eq} \end{eqnarray} Let $2^{k(\gamma)}M_\gamma\otimes 2^{k(\delta)}M_\delta$ be a term of this sum, with $\gamma\vDash m$. This term can only appear in one summand on the RHS of equation (\ref{delta-eq}), namely $\theta_{\varepsilon\cdot a}\otimes \theta_{\phi(b\cdot\zeta)}$ with $\varepsilon\cdot a\vDash m$. To show that it does indeed appear, we need to prove that $\gamma^\ast \preccurlyeq \varepsilon\cdot a$ and $\delta^\ast \preccurlyeq \phi(b\cdot\zeta)$. Let $\delta^{\ast\ast}$ be the refinement of $\delta^\ast$ obtained by replacing the part $\delta_1$ by $[1,\delta_1-1]$ if $\delta_1>1$. We have that \[\gamma^\ast\cdot \delta^{\ast\ast}=(\gamma\cdot\delta)^\ast\preccurlyeq \varepsilon\cdot(a+b)\cdot\zeta ,\] which implies that $\gamma^\ast \preccurlyeq \varepsilon\cdot a$, and $\delta^{\ast\ast}\preccurlyeq b\cdot\zeta\preccurlyeq \phi(b\cdot \zeta)$. If $\delta_1=1$ then $\delta^\ast =\delta^{\ast\ast}\preccurlyeq\phi (b\cdot \zeta)$. However, if $\delta _1>1$ then there are two possible cases: either $\delta_1\leq b$, or $b=1$ and $\delta_1-1\leq\zeta_1$. In the former case $\delta^\ast \preccurlyeq b\cdot\zeta =\phi (b\cdot \zeta)$, while in the latter, $\delta _1\preccurlyeq 1+\zeta_1$, whence $\delta^\ast \preccurlyeq [1+\zeta_1,\zeta_2,\ldots ]= \phi ( b\cdot\zeta)$. Conversely, let $ 2^{k(\gamma)}M_\gamma\otimes 2^{k(\delta)} M_\delta$ be a term belonging to a tensor $\theta_{\varepsilon\cdot a}\otimes \theta_{\phi(b\cdot \zeta)}$ on the RHS of equation (\ref{delta-eq}). To show that it appears in equation (\ref{2delta-eq}) we must prove that $(\gamma\cdot \delta )^\ast\preccurlyeq \varepsilon\cdot (a+b)\cdot \zeta$. We have that $\gamma^\ast\preccurlyeq \varepsilon\cdot a$ and $\delta^\ast\preccurlyeq \phi(b\cdot \zeta)$, which imply that \[(\gamma\cdot \delta)^\ast= \gamma^\ast\cdot\delta^{\ast\ast}\preccurlyeq \gamma^\ast\cdot\delta^\ast \preccurlyeq \varepsilon\cdot a\cdot \phi(b\cdot \zeta).\] If $b>1$ then $$(\gamma\cdot\delta)^\ast\preccurlyeq \varepsilon\cdot a\cdot \phi(b\cdot \zeta)=\varepsilon\cdot a\cdot b\cdot \zeta\preccurlyeq \varepsilon\cdot (a+b)\cdot\zeta.$$ If $b=1$ then $\delta^\ast \preccurlyeq \phi(b\cdot\zeta)=[1+\zeta_1,\zeta_2,\ldots ]$ implies that \[\delta^{\ast\ast}=[1, \ldots ]\preccurlyeq [1,\zeta_1,\ldots ]=b\cdot \zeta .\] Therefore, \[(\gamma\cdot\delta)^\ast=\gamma^\ast\cdot\delta^{\ast\ast}\preccurlyeq \varepsilon\cdot a\cdot b\cdot\zeta\preccurlyeq \varepsilon\cdot (a+b)\cdot \zeta\] as desired. \end{proof} \section{The peak Hopf algebra} \begin{definition} For any composition $\alpha =[\alpha_1,\alpha_2,\ldots ,\alpha_k]$ we say that $\theta_\alpha$ is a \emph{peak function} if $\alpha_i = 1\Rightarrow i=k$.\end{definition} Observe that if $\theta_\alpha$ is a peak function and $\alpha\vDash n$, then $I(\alpha)\subset \{2,\ldots ,n-1\}$ such that no two $i$ in $I(\alpha)$ are consecutive. Let $\Pi^n$ be the $\mathbb{Z}$-module spanned by all peak functions $\theta _\alpha$, $\alpha\vDash n$, and let $\Pi=\oplus_{n\geq 0}\Pi^n$. This was studied by Stembridge \cite{stem-bridge} who showed that the peak functions are F-positive, are closed under product, and form a basis for $\Pi$, and so the rank of $\Pi^n$ is the $n$th Fibonacci number. In addition we also know the following about the \emph{algebra of peaks}, $\Pi$. \begin{theorem} $\Pi$ is closed under coproduct. \label{peak-coalg}\end{theorem} \begin{proof} If all components of a composition $\alpha$, except perhaps the last, are greater than $1$, then the same is true for all compositions $\varepsilon\cdot a$ and $\phi(b\cdot\zeta)$ appearing in the RHS of equation (\ref{delta-eq}). \end{proof} Let $\Theta$ be the $\mathbb{Z}$-linear map from $\Sigma $ to $\Pi $ defined by $\Theta(F_\alpha)=\theta_{\Lambda(\alpha)}$, where $\Lambda(\alpha)$ is the composition formed from $\alpha =[\alpha_1,\alpha_2,\ldots ,\alpha _k]$ by adding together adjacent components $\alpha_i ,\alpha_{i+1},\ldots , \alpha_{i+j}$ where $\alpha_{i+l}=1$ for $l=0,\ldots , j-1$, and either $\alpha_{i+j}\neq 1$, or $i+j=k$. \begin{example} If $\alpha=31125111$ then $\Lambda (\alpha)=3453$. \end{example} Stembridge \cite{stem-bridge} showed that $\Theta:\Sigma \rightarrow \Pi$ is a graded surjective ring homomorphism, and was an analogue of the retraction from the algebra of symmetric functions to Schur $Q$ functions. It is clear from our proof above that this morphism is in fact a Hopf homomorphism. We can describe the kernel of $\Theta$ as follows. \begin{lemma} The non-zero differences $F_\alpha-F_{\Lambda (\alpha)}$ form a basis of the kernel of $\Theta$. \end{lemma} \begin{proof} Each difference $F_\alpha -F_{\Lambda(\alpha)}$ is in the kernel of $\Theta$ as $\Theta(F_\alpha -F_{\Lambda(\alpha)})=0$ since $\Lambda(\Lambda(\alpha))=\Lambda(\alpha)$. In addition, the non-zero differences are linearly independent as they have different leading terms. Letting $f_n$ denote the $n$th Fibonacci number, there are $2^{n-1}-f_n$ such differences, and since \begin{eqnarray*} \dim\ker\Theta &=& \dim \Sigma^n - \dim \Pi^n\\ &=&2^{n-1} -f_n, \end{eqnarray*} our result follows. \end{proof} \section{The coalgebra of shifted quasi-symmetric functions} \begin{definition} For any composition $\alpha =[\alpha_1,\alpha_2,\ldots ,\alpha_k]\vDash n$ we say that $\theta_\alpha$ is a \emph{shifted quasi-symmetric function} (sqs-function) if $n\le 1$ or $\alpha_1> 1$.\end{definition} Observe that if $\theta_\alpha$ is an sqs-function and $\alpha\vDash n$, then $I(\alpha)\subset \{2,\ldots ,n-1\}$. For integers $n\geq 0$, let $\Xi^n$ be the $\mathbb{Z}$-module spanned by all sqs-functions $\theta_\alpha$, $\alpha\vDash n$, and let $\Xi=\oplus_{n\geq 0}\Xi^n$. \begin{theorem} $\Xi$ is closed under coproduct. \label{sqs-coalg} \end{theorem} \begin{proof} If the first component of a composition $\alpha$ is greater than $1$, then the same is true for all compositions $\varepsilon\cdot a$ and $\phi(b\cdot\zeta)$ appearing in the RHS of equation (\ref{delta-eq}). \end{proof} Unlike peak functions \cite{stem-bridge}, sqs-functions are not $F$-positive since $$\theta_{211}=F_{22}+ F_{112}+ 2F_{121}+ F_{211}- F_{1111}.$$ \begin{definition} For any composition, $\alpha\vDash n$, we define the complement $\alpha^c$ of $\alpha$ to be the composition for which $I(\alpha^c) = (I(\alpha))^c$, the set complement of $I(\alpha)$ in $[n-1]$. We define the graph $G(\alpha)$ of $\alpha$ to be the graph obtained from $$ \epsfxsize=1.8in\epsfbox{graphn.eps} $$ by removing the edge $(i,i+1)$ if and only if $i\in I(\alpha)$. \end{definition} Observe that $G(\alpha^c)$ contains the edge $(i,i+1)$ if and only if this edge is not contained in $G(\alpha)$. These graphs will be used later to simplify the proof of Theorem~\ref{kw-thetabh}. Let a \emph{word} of length $n$ be any $n$-tuple, $w_1w_2\ldots w_n$, and let a \emph{binary word} of length $n$ be a word $w_1w_2\ldots w_n$ wuch that $w_i\in \{ 0,1\}$ for all $i$. For $2\leq i\leq n-1$, let us denote by $\three $ the composition $ [1^ {i-2}, 3,1^{n-i-1}]$ of $n $. For some subset $S\subset \{2, \ldots ,n-1\}$, let us denote by $\bigwedge_{i\in S}\three$ the composition of $n$ for which $G(\bigwedge_{i\in S}\three)$ has an edge between vertices $i$ and $i+1$ if and only if an edge exists between vertices $i$ and $i+1$ in $G(\three)$ for some $i\in S$. \begin{example} Let $S=\{ 2,3\}\subset [3]$. Then $G(3^{(2)})$ is $$ \epsfxsize=1.55in\epsfbox{graph2.eps} $$ and $G(3^{(3)})$ is $$ \epsfxsize=1.55in\epsfbox{graph3.eps} $$ hence $G(\bigwedge_{i\in S}\three)$ is $$ \epsfxsize=1.55in\epsfbox{graph4.eps} $$ so $\bigwedge_{i\in S}\three$ is the composition $4$. \end{example} \begin{definition}\cite{billey-haiman} Let $\alpha$ be a composition of $n$. Let ${\mathcal A}(I(\alpha))$ denote the set of all sequences $j_1\leq j_2\leq\ldots \leq j_n$ in $\mathbb{N}$ such that we do not have $j_{i-1}=j_i=j_{i+1}$ for any $i\in I(\alpha)$. The \emph{shifted quasi-symmetric function} $\thetabh_\alpha$ is given by \[\thetabh_\alpha = \sum_{\stackrel{\mbox{\scriptsize$J=(j_1,\ldots, j_n)$}}{ \stackrel{\mbox{\scriptsize$j_1\leq\ldots\leq j_n$}}{ J\in{\mathcal A}(I(\alpha))}}} 2^{| j|}x_{j_1}\ldots x_{j_n},\]where $|j|$ denotes the number of distinct values $j_i$ in $J$.\label{bi-ha} \end{definition} \begin{theorem} For any sqs-function $\theta_\alpha$ we have that $\theta_\alpha=\thetabh _\alpha$.\label{kw-thetabh} \end{theorem} \begin{proof} For each $i\in \W\subset[n-1]$, $j_{i-1}=j_i=j_{i+1}$ is forbidden in any monomial \[ x_{j_1}x_{j_2}\ldots x_{j_i}\ldots x_{j_n}\] appearing as a summand of the function $\thetabh_\alpha$. This is equivalent to saying that $M_\beta$ is a summand of $\thetabh_\alpha$ if and only if $G(\three)\not\subset G(\beta)$ for all $i\in \W$. Therefore at least one of $i-1$ or $i$ must be the largest label of a vertex in a connected component in $G(\beta)$. Now when going from compositions of $n$ to subsets of $[n-1]$ we can do so using our graphs, $G$. All we have to do is list the label of the vertex that is the largest in each connect component, not listing $n$. We call these vertices the \emph{end-points}. We are now in a position to prove the equivalence of Definitions ~\ref{st-em} and ~\ref{bi-ha} for sqs-functions. The powers of 2 agree so we need only show that the indices of summation do too. To see this, take any sqs-function $\theta_\alpha$ and let $i\in\W$. Then $M_\beta$ is a summand in $\thetabh_\alpha$ if at least one of $i-1$ or $i$ is an end-point in $G(\beta)$. Therefore $i$ or $i-1$ belongs to $I(\beta)$, and $M_\beta$ is a summand of $\theta_\alpha$. Conversely, if $M_\beta $ is a summand of $\theta _\alpha$, then this implies that for each $i\in \W$, we have that $i-1$ or $i$ belongs to $I(\beta)$, so one of $i-1$ or $i$ is an end-point in $G(\beta)$, so $M_\beta$ is a summand of $\thetabh_\alpha$. \end{proof} \section{A basis for $\Xi$} \begin{definition} Let $\theta_\alpha$ be an sqs-function and $\alpha \vDash n$. We define an internal peak $i\in \W$ such that $i- 1,i+1\not\in \W$, and $i\in\{ 3,\ldots n-2\}$. \end{definition} \begin{remark} Observe that the occurrence of an internal peak in the $i$th position in $I(\alpha)=\{ w_1,w_2,\ldots\}$, where $w_1