%% LyX 2.2.2 created this file.  For more info, see http://www.lyx.org/.
%% Do not edit unless you really know what you are doing.
\documentclass[finalversion,english]{FPSAC2018}
\articlenumber{5}

\usepackage[T1]{fontenc}
\usepackage[latin9]{inputenc}
\usepackage{geometry}
\setcounter{secnumdepth}{3}
\setcounter{tocdepth}{3}
\usepackage{mathtools}
\usepackage{amsmath}
\usepackage{amsthm}
\usepackage{amssymb}

\makeatletter
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Textclass specific LaTeX commands.
\theoremstyle{plain}
\newtheorem{thm}{\protect\theoremname}[section]
  \theoremstyle{plain}
  \newtheorem{cor}[thm]{\protect\corollaryname}
  \theoremstyle{plain}
  \newtheorem{conjecture}[thm]{\protect\conjecturename}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% User specified LaTeX commands.
\usepackage{microtype}

\DeclareMathOperator{\Des}{Des}
\DeclareMathOperator{\pk}{pk}
\DeclareMathOperator{\lpk}{lpk}
\DeclareMathOperator{\Comp}{Comp}
\DeclareMathOperator{\udr}{udr}
\DeclareMathOperator{\des}{des}
\DeclareMathOperator{\st}{st}
\DeclareMathOperator{\val}{val}
\DeclareMathOperator{\maj}{maj}
\DeclareMathOperator{\Pk}{Pk}
\DeclareMathOperator{\Lpk}{Lpk}
\DeclareMathOperator{\Epk}{Epk}
\DeclareMathOperator{\QSym}{QSym}

%% 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

%% 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}


%% define your title in the usual way
\title[Shuffle-compatible descent statistics and quotients of
quasisymmetric functions]{Shuffle-compatible descent statistics\\
and quotients of quasisymmetric functions}

%% define your authors in the usual way
%% use \addressmark{1}, \addressmark{2} etc for the institutions, and use \thanks{} for contact details
\author{Ira M.
Gessel\thanks{\href{mailto:gessel@brandeis.edu}{gessel@brandeis.edu}.
Supported by a grant from the Simons Foundation (\#427060, Ira
Gessel).}\addressmark{1} \and Yan
Zhuang\thanks{\href{mailto:yazhuang@davidson.edu}{yazhuang@davidson.edu}}\addressmark{2}}

%% then use \addressmark to match authors to institutions here
\address{\addressmark{1}Department of Mathematics, Brandeis University\\
\addressmark{2}Department of Mathematics and Computer Science, Davidson
College}

%% put the date of submission here
\received{November 3, 2017}

%% leave this blank until submitting a revised version
\revised{March 29, 2018}

%% put your English abstract here, or comment this out if you don't have one yet
%% please don't use custom commands in your abstract / resume, as these will be displayed online
%% likewise for citations -- please don't use \cite, and instead write out your citation as something like (author year)
\abstract{We study shuffle-compatible permutation statistics: permutation statistics $\st$ with the property that the 
distribution of $\st$ over all shuffles of two permutations $\pi$ and $\sigma$ is completely determined by $\st(\pi)$, 
$\st(\sigma)$, and the lengths of $\pi$ and $\sigma$. We develop a theory of shuffle-compatibility for descent 
statistics---permutation statistics that depend only on the descent set and length---and its connections to $P$-partitions, 
quasisymmetric functions, and noncommutative symmetric functions.}

%% put your French abstract here, or comment this out if you don't have one
%\resume{\lipsum[2]}

%% put your keywords here, or comment this out if you don't have them yet
\keywords{permutation statistics, shuffles, descents, $P$-partitions, quasisymmetric functions, noncommutative symmetric functions}


\let\originalleft\left
\let\originalright\right
\renewcommand{\left}{\mathopen{}\mathclose\bgroup\originalleft}
\renewcommand{\right}{\aftergroup\egroup\originalright}

\makeatother

\usepackage{babel}
  \providecommand{\conjecturename}{Conjecture}
  \providecommand{\corollaryname}{Corollary}
\providecommand{\theoremname}{Theorem}


\usepackage[backend=bibtex]{biblatex}
\addbibresource{05-Gessel-Zhuang.bib}
\begin{document}


\maketitle
\setcounter{footnote}{0}

\section{Introduction}

We say that $\pi=\pi_{1}\pi_{2}\cdots\pi_{n}$ is a \textit{permutation}
of \textit{length} $n$ (or an $n$-\textit{permutation}) if it is
a sequence of $n$ distinct letters\textemdash not necessarily from
1 to $n$\textemdash in $\mathbb{P}$, the set of positive integers.
For example, $\pi=47381$ is a permutation of length 5. Let $\mathfrak{P}_{n}$
denote the set of all permutations of length $n$, and let $\left|\pi\right|$
denote the length of a permutation $\pi$.

A \textit{permutation statistic} (or \textit{statistic}) $\st$ is
a function defined on permutations such that $\st(\pi)=\st(\sigma)$
whenever $\pi$ and $\sigma$ are permutations with the same relative
order. Three classical examples of permutation statistics are the
descent set $\Des$, the descent number $\des$, and the major index
$\maj$. We say that $i\in[n-1]$ is a \textit{descent} of $\pi\in\mathfrak{P}_{n}$
if $\pi_{i}>\pi_{i+1}$. Then the \textit{descent set} 
\[
\Des(\pi)\coloneqq\{\,i\in[n-1]\mid\pi_{i}>\pi_{i+1}\,\}
\]
of $\pi$ is the set of its descents, the \textit{descent number}
\[
\des(\pi)\coloneqq\left|\Des(\pi)\right|
\]
is its number of descents, and the \textit{major index} 
\[
\maj(\pi)\coloneqq\sum_{k\in\Des(\pi)}k
\]
is the sum of its descents.

Let $\pi\in\mathfrak{P}_{m}$ and $\sigma\in\mathfrak{P}_{n}$ be
\textit{disjoint} permutations, that is, permutations with no letters
in common. We say that $\tau\in\mathfrak{P}_{m+n}$ is a \textit{shuffle}
of $\pi$ and $\sigma$ if both $\pi$ and $\sigma$ are subsequences
of $\tau$. The set of shuffles of $\pi$ and $\sigma$ is denoted
$S(\pi,\sigma)$. For example, $S(53,16)=\{5316,5136,5163,1653,1536,1563\}$.
It is easy to see that the number of permutations in $S(\pi,\sigma)$
is ${m+n \choose m}$.

Richard Stanley's theory of $P$-partitions \cite{Stanley1972} implies
that the descent set statistic has a remarkable property related to
shuffles: for any disjoint permutations $\pi$ and $\sigma$, the
multiset $\{\,\Des(\tau)\mid\tau\in S(\pi,\sigma)\,\}$ encoding the
distribution of $\Des$ over all shuffles of $\pi$ and $\sigma$
depends only on $\Des(\pi)$, $\Des(\sigma)$, and the lengths of
$\pi$ and $\sigma$ \cite[Exercise 3.161]{Stanley2011}. That is,
if $\pi$ and $\pi^{\prime}$ are permutations of the same length
with the same descent set, and similarly with $\sigma$ and $\sigma^{\prime}$,
then the number of permutations in $S(\pi,\sigma)$ with any given
descent set is the same as the number of permutations in $S(\pi^{\prime},\sigma^{\prime})$
with that descent set.

In fact, this property is not unique to the descent set. A result
called ``Stanley's shuffling theorem'', which is a special case of
Proposition 12.6 in Stanley's memoir on $P$-partitions \cite{Stanley1972},
implies that the distribution of each of the statistics $\des$, $\maj$,
and $(\des,\maj)$ over the set of shuffles of two disjoint permutations
depends only on the value of the statistic over the two permutations
being shuffled and the lengths of these two permutations. Furthermore,
it is a direct consequence of John Stembridge's ``enriched $P$-partitions''
\cite{Stembridge1997} that the peak set $\Pk$ has this property,
and a direct consequence of Kyle Petersen's \cite{Petersen2007} ``left
enriched $P$-partitions'' that the left peak set $\Lpk$ has this
property.

We call this property ``shuffle-compatibility''. More precisely, we
say that a permutation statistic $\st$ is \textit{shuffle-compatible}
if for any disjoint permutations $\pi$ and $\sigma$, the multiset
$\{\,\st(\tau)\mid\tau\in S(\pi,\sigma)\,\}$ depends only on $\st(\pi)$,
$\st(\sigma)$, $\left|\pi\right|$, and $\left|\sigma\right|$. Hence,
$\Des$, $\des$, $\maj$, $(\des,\maj)$, $\Pk$, and $\Lpk$ are
examples of shuffle-compatible permutation statistics.

This extended abstract is a summary of the recent paper \cite{Gessel2017},
which presents the first in-depth investigation of shuffle-compatibility
and focuses in particular on the shuffle-compatibility of ``descent
statistics'': permutation statistics that depend only on the descent
set and length of a permutation. In Section 2, we introduce some preliminary
notions from the theory of descent statistics and define the ``shuffle
algebra'' of a shuffle-compatible permutation statistic $\st$, whose
multiplication encodes the distribution of $\st$ over shuffles of
permutations (or more precisely, equivalence classes of permutations
induced by the statistic $\st$). In Section 3, we give a shuffle-compatibility
criterion which implies that the shuffle algebra of any shuffle-compatible
descent statistic is isomorphic to a quotient of the algebra $\QSym$
of quasisymmetric functions, and also a ``dual'' shuffle-compatibility
criterion exploiting the duality between $\QSym$ and the coalgebra
$\mathbf{Sym}$ of noncommutative symmetric functions. These are used
to establish the shuffle-compatibility of a number of well-known descent
statistics and to give explicit descriptions of their shuffle algebras;
we present three of these algebras in Section 4. Finally, we state
several open problems surrounding the notion of shuffle-compatibility
in Section 5.

Before proceeding, we note that there is another class of algebras
that are related to permutations and their descent sets. If $\st$
is a function defined on the $n$th symmetric group $\mathfrak{S}_{n}$,
we may consider the elements 
\[
K_{\alpha}=\sum_{\substack{\pi\in\mathfrak{S}_{n}\\
\st(\pi)=\alpha
}
}\pi
\]
in the group algebra of $\mathfrak{S}_{n}$, where $\alpha$ ranges
over the image of $\st$. Louis Solomon \cite{Solomon1976} proved
that if $\st$ is the descent set, then the $K_{\alpha}$ span a subalgebra
of the group algebra of $\mathfrak{S}_{n}$, called the \textit{descent
algebra} of $\mathfrak{S}_{n}$. Several other descent statistics
are known to give subalgebras of the descent algebra \cite{Aguiar2004,Doyle2008,Josuat-Verges2016,Loday1989,Nyman2003,Petersen2007,Schocker2005};
these statistics have the property that given values $\alpha$ and
$\beta$ of $\st$ and a permutation $\tau\in\mathfrak{S}_{n}$, the
number of pairs $(\pi,\sigma)$ of permutations in $\mathfrak{S}_{n}$
with $\st(\pi)=\alpha$, $\st(\alpha)=\beta$, and $\pi\sigma=\tau$
depends only on $\st(\tau)$. Hence, our theory of shuffle-compatible
descent statistics can be interpreted as an analogue of Solomon's
descent theory for statistics compatible under the shuffle product
(as opposed to the ordinary product).

\section{Preliminary definitions and results}

\subsection{Descent compositions and descent statistics}

Given a subset $S\subseteq[n-1]$ with elements $s_{1}<s_{2}<\cdots<s_{j}$,
let $\Comp(S)$ be the composition $(s_{1},s_{2}-s_{1},\dots,s_{j}-s_{j-1},n-s_{j})$
of $n$, and given a composition $L=(L_{1},L_{2},\dots,L_{k})$, let
$\Des(L)\coloneqq\{L_{1},L_{1}+L_{2},\dots,L_{1}+\cdots+L_{k-1}\}$
be the corresponding subset of $[n-1]$. Then, $\Comp$ and $\Des$
are inverse bijections. If $\pi\in\mathfrak{P}_{n}$ has descent set
$S\subseteq[n-1]$, then we call $\Comp(S)$ the \textit{descent composition}
of $\pi$, which we also denote by $\Comp(\pi)$. Conversely, if $\pi$
has descent composition $L$, then its descent set $\Des(\pi)$ is
$\Des(L)$.

A permutation statistic $\st$ is called a \textit{descent statistic}
if it depends only on the descent composition, that is, if $\Comp(\pi)=\Comp(\sigma)$
implies $\st(\pi)=\st(\sigma)$ for any two permutations $\pi$ and
$\sigma$. Equivalently, $\st$ is a descent statistic if it depends
only on the descent set and length of a permutation. We saw four examples
of descent statistics in the introduction: the descent set $\Des$,
descent number $\des$, major index $\maj$, and the joint statistic
$(\des,\maj)$. The following are some additional descent statistics
that we consider in our investigation of shuffle-compatibility:
\begin{itemize}
\item The peak set $\Pk$ and peak number $\pk$. We say that $i$ (where
$2\leq i\leq n-1$) is a \textit{peak} of $\pi\in\mathfrak{P}_{n}$
if $\pi_{i-1}<\pi_{i}>\pi_{i+1}$. The \textit{peak set} $\Pk(\pi)$
of $\pi$ is defined to be the set of peaks of $\pi$, and the \textit{peak
number} $\pk(\pi)$ of $\pi$ is defined to be $\pk(\pi)\coloneqq\left|\Pk(\pi)\right|.$
\item The left peak set $\Lpk$ and left peak number $\lpk$. We say that
$i\in[n-1]$ is a \textit{left peak} of $\pi\in\mathfrak{P}_{n}$
if $i$ is a peak of $\pi$ or if $i=1$ and $i$ is a descent of
$\pi$. The \textit{left peak set} $\Lpk(\pi)$ of $\pi$ is defined
to be the set of left peaks of $\pi$, and the \textit{left peak number}
$\lpk(\pi)$ of $\pi$ is defined to be $\lpk(\pi)\coloneqq\left|\Lpk(\pi)\right|.$
\item The number $\udr$ of up-down runs. An \textit{up-down run} of $\pi\in\mathfrak{P}_{n}$
is either a maximal monotone consecutive subsequence or $\pi_{1}$
when $\pi_{1}>\pi_{2}$. For example, the up-down runs of $\pi=871542$
are $8$, $871$, $15$, and $542$, so $\udr(\pi)=4$.
\item Ordered tuples of descent statistics, such as $(\pk,\des)$, $(\lpk,\des)$,
and so on.
\end{itemize}

\subsection{Shuffle algebras}

Every permutation statistic $\st$ induces an equivalence relation
on permutations; we say that permutations $\pi$ and $\sigma$ are
$\st$-\textit{equivalent} if $\st(\pi)=\st(\sigma)$ and $\left|\pi\right|=\left|\sigma\right|$.
We write the $\st$-equivalence class of $\pi$ as $[\pi]_{\st}$.
For a shuffle-compatible statistic $\st$, we can then associate to
$\st$ a $\mathbb{Q}$-algebra in the following way. First, associate
to $\st$ a $\mathbb{Q}$-vector space by taking as a basis the $\st$-equivalence
classes of permutations. We give this vector space a multiplication
by taking 
\[
[\pi]_{\st}[\sigma]_{\st}=\sum_{\tau\in S(\pi,\sigma)}[\tau]_{\st},
\]
which is well-defined (i.e., the choice of $\pi$ and $\sigma$ does
not matter) because $\st$ is shuffle-compatible. Conversely, if such
a multiplication is well-defined, then $\st$ is shuffle-compatible.
We denote the resulting algebra ${\cal A}_{\st}$ and call it the
\textit{shuffle algebra} of $\st$. Observe that ${\cal A}_{\st}$
is graded, and $[\pi]_{\st}$ belongs to the $n$th homogeneous component
of ${\cal A}_{\st}$ if $\pi$ has length $n$.

As a preliminary example, the following theorem gives a description
of the major index shuffle algebra, which we prove in \cite{Gessel2017}
using a formula arising from Stanley's theory of $P$-partitions \cite{Stanley1972}.
Recall that the $n$th $q$-factorial $[n]_{q}!$ is defined by 
\[
[n]_{q}!\coloneqq(1+q)(1+q+q^{2})\cdots(1+q+\cdots+q^{n-1}).
\]

\begin{thm}
\label{t-majsc} The map given by
\[
[\pi]_{\maj}\mapsto\frac{q^{\maj(\pi)}}{[\left|\pi\right|]_{q}!}x^{\left|\pi\right|}
\]
is a $\mathbb{Q}$-algebra isomorphism from ${\cal A}_{\maj}$ to
the span of 
\[
\left\{ \frac{q^{j}}{[n]_{q}!}x^{n}\right\} _{n\geq1,\:0\leq j\leq{n \choose 2}},
\]
a subalgebra of $\mathbb{Q}[[q]][x]$.
\end{thm}
For descent statistics $\st$, not only does $\st$ induce a equivalence
relation on permutations, but it also induces a equivalence relation
on compositions because permutations with the same descent composition
are necessarily $\st$-equivalent. Thus, we can regard the shuffle
algebra of a descent statistic $\st$ as consisting of $\st$-equivalence
classes of compositions rather than permutations, and we will do this
when presenting our theory of shuffle-compatible descent statistics
in Section 3.

We say that $\st_1$ is a \textit{refinement} of $\st_2$ if for all permutations $\pi$ and $\sigma$ of the same length, $\st_1(\pi) = \st_1(\sigma)$ implies $\st_2(\pi) = \st_2(\sigma)$. For example, the statistics of which the descent set is a refinement  are exactly what we call descent statistics.

\begin{thm} \label{t-quots} Suppose that $\st_1$ is shuffle-compatible and is a refinement of $\st_2$. Let $A$ be  a $\mathbb{Q}$-algebra with basis $\{u_{\alpha}\}$ indexed by $\st_2$-equivalence classes $\alpha$, and suppose that there exists a $\mathbb{Q}$-algebra homomorphism $\phi\colon \mathcal{A}_{\st_1}\to A$ such that for every $\st_1$-equivalence class $\beta$, we have $\phi(\beta) = u_\alpha$ where $\alpha$ is the $\st_2$-equivalence class containing $\beta$. Then $\st_2$ is shuffle-compatible and the map $u_\alpha\mapsto\alpha$ extends by linearity to an isomorphism from $A$ to ${\cal A}_{\st_2}$. \end{thm}

\section{Theory of shuffle-compatible descent statistics}

\subsection{Quasisymmetric functions}

Let us review some basic definitions and results surrounding quasisymmetric
functions. A formal power series $f\in\mathbb{Q}[[x_{1},x_{2},\dots]]$
in countably many commuting variables $x_{1},x_{2},\dots$ of bounded
degree is called a \textit{quasisymmetric function} if for any $a_{1},a_{2},\dots,a_{k}\in\mathbb{P}$,
$i_{1}<i_{2}<\cdots<i_{k}$, and $j_{1}<j_{2}<\cdots<j_{k}$, we have
\[
[x_{i_{1}}^{a_{1}}x_{i_{2}}^{a_{2}}\cdots x_{i_{k}}^{a_{k}}]\,f=[x_{j_{1}}^{a_{1}}x_{j_{2}}^{a_{2}}\cdots x_{j_{k}}^{a_{k}}]\,f.
\]

Let $\QSym_{n}$ be the set of quasisymmetric functions homogeneous
of degree $n$. Then $\QSym_{n}$ is a $\mathbb{Q}$-vector space
and is known to have dimension equal to $2^{n-1}$, the number of
compositions of $n$. The most important basis of $\QSym_{n}$ for
our purposes is the basis of \textit{fundamental quasisymmetric functions}
$\{F_{L}\}_{L\vDash n}$ given by 
\[
F_{L}\coloneqq\sum_{\substack{i_{1}\leq i_{2}\leq\cdots\leq i_{n}\\
i_{j}<i_{j+1}\,\mathrm{if}\,j\in\Des(L)
}
}x_{i_{1}}x_{i_{2}}\cdots x_{i_{n}}.
\]
If $f\in\QSym_{m}$ and $g\in\QSym_{n}$, then $fg\in\QSym_{m+n}$.
Thus $\QSym\coloneqq\bigoplus_{n=0}^{\infty}\QSym_{n}$ is a graded
$\mathbb{Q}$-algebra called the \textit{algebra of quasisymmetric
functions} with coefficients in $\mathbb{Q}$, a subalgebra of $\mathbb{Q}[[x_{1},x_{2},\dots]]$.
Motivated by Richard Stanley's theory of $P$-partitions, the first
author introduced quasisymmetric functions in \cite{Gessel1984} and
developed the basic algebraic properties of $\QSym$. Further properties
of $\QSym$ and connections with many topics of study in combinatorics
and algebra were developed in the subsequent decades. In particular,
$\QSym$ is a Hopf algebra and is the terminal object in the category
of combinatorial Hopf algebras in the sense of Aguiar\textendash Bergeron\textendash Sottile
\cite{Aguiar2006}.

Using $P$-partitions, one can show that the multiplication rule for
the fundamental basis is given by
\begin{equation}
F_{J}F_{K}=\sum_{L}c_{J,K}^{L}F_{L}.\label{e-fundmult}
\end{equation}
where $c_{J,K}^{L}$ is the number of permutations with descent composition
$L$ among the shuffles of a permutation with descent composition
$J$ and one with descent composition $K$; see \cite[Exercise 7.93]{Stanley2001}.
This implies that $\QSym$ is isomorphic to the descent set shuffle
algebra ${\cal A}_{\Des}$ with the fundamental basis corresponding
to the basis of $\Des$-equivalence classes.

Later, John Stembridge \cite{Stembridge1997} introduced a variant
of the notion of $P$-partitions called ``enriched $P$-partitions'',
which is closely related to the combinatorics of peaks. Using enriched
$P$-partitions, Stembridge defined the peak quasisymmetric functions
$\{K_{n,\Lambda}\}$ which are indexed by peak sets $\Lambda$ of
$n$-permutations. These peak functions multiply by a rule similar
to Equation (\ref{e-fundmult}) but with the role of descent compositions
(equivalently, descent sets) replaced with peak sets, which shows
that the peak set $\Pk$ is shuffle-compatible with shuffle algebra
${\cal A}_{\Pk}$ isomorphic to the span of the peak functions, called
the \textit{algebra of peaks}. 

In a similar vein, Kyle Petersen \cite{Petersen2007} introduced ``left
enriched $P$-partitions'' which play an analogous role to enriched
$P$-partitions but for left peaks; it follows from Petersen's work
that the left peak set $\Lpk$ is shuffle-compatible and that the
shuffle algebra ${\cal A}_{\Lpk}$ is isomorphic to Petersen's \textit{algebra
of left peaks}. The shuffle-compatibility of the left peak set also
follows from the work of Aguiar, Bergeron, and Nyman \cite{Aguiar2004},
which showed the existence of the coalgebra dual to ${\cal A}_{\Lpk}$.

Both Stembridge's algebra of peaks and Petersen's algebra of left
peaks can be realized as quotients of $\QSym$. In fact, this is true
in general for shuffle algebras of shuffle-compatible descent statistics.
The following is one of our central results.
\begin{thm}
\label{t-scqsym} A descent statistic $\st$ is shuffle-compatible
if and only if there exists a $\mathbb{Q}$-algebra homomorphism $\phi_{\st}:\QSym\rightarrow A$,
where $A$ is a $\mathbb{Q}$-algebra with basis $\{u_{\alpha}\}$
indexed by $\st$-equivalence classes $\alpha$ of compositions, such
that $\phi_{\st}(F_{L})=u_{\alpha}$ whenever $L\in\alpha$. In this
case, the map given by 
\[
[\pi]_{\st}\mapsto u_{\alpha},
\]
where $\Comp(\pi)\in\alpha$, is a $\mathbb{Q}$-algebra isomorphism
from ${\cal A}_{\st}$ to $A$.
\end{thm}
One direction of this theorem follows immediately from Theorem \ref{t-quots};
we omit the proof of the other direction.
\begin{cor}
The shuffle algebra of any shuffle-compatible descent statistic is
isomorphic to a quotient algebra of $\QSym$.
\end{cor}

\subsection{Noncommutative symmetric functions}

Let $\mathbb{Q}\langle\langle X_{1},X_{2},\dots\rangle\rangle$ be
the $\mathbb{Q}$-algebra of formal power series in countably many
noncommuting variables $X_{1},X_{2},\dots$. Consider the elements
\[
\mathbf{r}_{L}\coloneqq\sum_{i_{1},\dots,i_{n}}X_{i_{1}}X_{i_{2}}\cdots X_{i_{n}}
\]
of $\mathbb{Q}\langle\langle X_{1},X_{2},\dots\rangle\rangle$, where
the sum is over all $i_{1},\dots,i_{n}$ satisfying 
\[
\underset{L_{1}}{\underbrace{i_{1}\leq\cdots\leq i_{L_{1}}}}>\underset{L_{2}}{\underbrace{i_{L_{1}+1}\leq\cdots\leq i_{L_{1}+L_{2}}}}>\cdots>\underset{L_{k}}{\underbrace{i_{L_{1}+\cdots+L_{k-1}+1}\leq\cdots\leq i_{n}}}
\]
for $L=(L_{1},L_{2},\dots,L_{k})$. These $\mathbf{r}_{L}$ are called
\textit{ribbon functions}; they are linearly independent and generate
a subalgebra $\mathbf{Sym}$ of $\mathbb{Q}\langle\langle X_{1},X_{2},\dots\rangle\rangle$
called the \textit{algebra of noncommutative symmetric functions}
with coefficients in $\mathbb{Q}$. The algebra $\mathbf{Sym}$ is
graded and decomposes as $\mathbf{Sym}\coloneqq\bigoplus_{n=0}^{\infty}\mathbf{Sym}_{n}$
where $\mathbf{Sym}_{n}$ is the vector space with basis $\{\mathbf{r}_{L}\}_{L\vDash n}$.

The study of $\mathbf{Sym}$ was initiated by Gelfand et al.\,\cite{ncsf1},
who showed that $\mathbf{Sym}$ is also a Hopf algebra and is in fact
the graded dual of the Hopf algebra $\QSym$ of quasisymmetric functions.
In particular, the ribbon basis of $\mathbf{Sym}$ is dual to the
fundamental basis of $\QSym$, which means that the structure constants
for the comultiplication of the $\mathbf{r}_{L}$ are precisely the
structure constants for the multiplication of the $F_{L}$. In other
words, we have
\[
\Delta\mathbf{r}_{L}=\sum_{J,K}c_{J,K}^{L}\mathbf{r}_{J}\otimes\mathbf{r}_{K}
\]
where $\Delta$ denotes the comultiplication of $\mathbf{Sym}$ and
the $c_{J,K}^{L}$ are the same as in Equation (\ref{e-fundmult}).
This duality gives rise to the following shuffle-compatibility criterion,
which can be seen as a dual version of Theorem \ref{t-scqsym}.
\begin{thm}
\label{t-rib} Let $\st$ be a descent statistic. For each $\st$-equivalence
class $\alpha$ of compositions, let $\mathbf{r}_{\alpha}^{\st}\coloneqq\sum_{L\in\alpha}\mathbf{r}_{L}$.
Then $\st$ is shuffle-compatible if and only if for every equivalence
class $\alpha$, there exist constants $c_{\beta,\gamma}^{\alpha}$
for which 
\[
\Delta\mathbf{r}_{\alpha}^{\st}=\sum_{\beta,\gamma}c_{\beta,\gamma}^{\alpha}\mathbf{r}_{\beta}^{\st}\otimes\mathbf{r}_{\gamma}^{\st},
\]
that is, the $\mathbf{r}_{\alpha}^{\st}$ span a subcoalgebra of $\mathbf{Sym}$.
\end{thm}
When the $\mathbf{r}_{\alpha}^{\st}$ span a subcoalgebra of $\mathbf{Sym}$,
this coalgebra is the graded dual of the shuffle algebra ${\cal A}_{\st}$,
so the $c_{\beta,\gamma}^{\alpha}$ are the structure constants for
${\cal A}_{\st}$. While Theorem \ref{t-scqsym} tells us that we
can prove the shuffle-compatibility of a descent statistic by constructing
suitable quotients of $\QSym$, Theorem \ref{t-rib} tells us that
we could, alternatively, construct suitable subcoalgebras of $\mathbf{Sym}$,
and this is often easier. Moreover, because it is straightforward
to compute coproducts of noncommutative symmetric functions, Theorem
\ref{t-rib} is useful for showing that a descent statistic is not
shuffle-compatible and for conjecturing that a statistic is shuffle-compatible,
which is not the case for Theorem \ref{t-scqsym}.

Theorem \ref{t-rib} does not give us a way to explicitly describe
the dual algebra ${\cal A}_{\st}$, but this can be done with the
help of a theorem involving the notion of grouplike noncommutative
symmetric functions which is proven using Theorem \ref{t-rib}. We
omit the theorem here, but it appears as Theorem 5.8 of \cite{Gessel2017}.

\section{Explicit descriptions of shuffle algebras}

\subsection{The \texorpdfstring{$(\pk,\des)$}{(pk, des)} shuffle algebra}

So far, we know that $\Des$, $\Pk$, and $\Lpk$ are shuffle-compatible
and we have identified their shuffle algebras. We also know that the
statistics $\des$, $\maj$, and $(\des,\maj)$ are shuffle-compatible;
Theorem \ref{t-majsc} characterizes the shuffle algebra of $\maj$,
and characterizations of the shuffle algebras of $\des$ and $(\des,\maj)$
can be found in our paper \cite{Gessel2017}. 

In \cite{Gessel2017}, we also characterize using quasisymmetric functions
and noncommutative symmetric functions the shuffle algebras of the
statistics $\pk$, $(\pk,\des)$, $\lpk$, $(\lpk,\des)$, $\udr$,
and $(\udr,\des)$, thus showing that all of these statistics are
shuffle-compatible. In this extended abstract, we focus our attention
on the $(\pk,\des)$, $\pk$, and $\des$ shuffle algebras. 

We begin with our result for ${\cal A}_{(\pk,\des)}$, which we prove
in \cite{Gessel2017} using noncommutative symmetric functions. The
operation of \textit{Hadamard product} $*$ on formal power series
in $t$ is defined by 
\[
\Big(\sum_{n=0}^{\infty}a_{n}t^{n}\Big)*\Big(\sum_{n=0}^{\infty}b_{n}t^{n}\Big)\coloneqq\sum_{n=0}^{\infty}a_{n}b_{n}t^{n}.
\]

\begin{thm}[Shuffle-compatibility of $(\pk,\des)$]
 \label{t-pkdessc} \leavevmode
\begin{itemize}
\item [\normalfont{(a)}] The map given by%\vspace{-10bp}
\begin{multline*}
\hspace{-25bp}[\pi]_{(\pk,\des)}\mapsto\vphantom{\frac{dx}{dt}}\\
\hspace{-25bp}\begin{cases}
{\displaystyle \frac{t^{\pk(\pi)+1}(y+t)^{\des(\pi)-\pk(\pi)}(1+yt)^{\left|\pi\right|-\pk(\pi)-\des(\pi)-1}(1+y)^{2\pk(\pi)+1}}{(1-t)^{\left|\pi\right|+1}}x^{\left|\pi\right|}}, & \text{if }\left|\pi\right|\geq1,\\
1/(1-t), & \text{if }\left|\pi\right|=0,
\end{cases}
\end{multline*}
is a $\mathbb{Q}$-algebra isomorphism from ${\cal A}_{(\pk,\des)}$
to the span of 
\[
\left\{ \frac{1}{1-t}\right\} \bigcup\left\{ \frac{t^{j+1}(y+t)^{k-j}(1+yt)^{n-j-k-1}(1+y)^{2j+1}}{(1-t)^{n+1}}x^{n}\right\} _{\substack{n\geq1,\hphantom{...................}\\
0\leq j\leq\left\lfloor (n-1)/2\right\rfloor ,\\
j\leq k\leq n-j-1\hphantom{......}
}
},
\]
a subalgebra of $\mathbb{Q}[[t]][x,y]$ where multiplication is the
Hadamard product in $t$.
\item [\normalfont{(b)}] The $(\pk,\des)$ shuffle algebra $\mathcal{A}_{(\pk,\des)}$
is isomorphic to the span of 
\[
\{1\}\cup\{p^{n-j}(1+y)^{n}(1-y)^{n-2k}x^{n}\}_{n\geq1,0\leq j\leq n-1,0\leq k\leq\left\lfloor j/2\right\rfloor },
\]
a subalgebra of $\mathbb{Q}[p,x,y]$.
\end{itemize}
\end{thm}
As a simple application of Theorem \ref{t-pkdessc}, let us consider
shuffling a permutation $\pi\in\mathfrak{P}_{n}$ with $j$ peaks
and $k$ descents with a permutation $\sigma\in\mathfrak{P}_{1}$
(i.e., a single letter). Let 
\[
u_{n,j,k}\coloneqq\frac{t^{j+1}(y+t)^{k-j}(1+yt)^{n-j-k-1}(1+y)^{2j+1}}{(1-t)^{n+1}}x^{n},
\]
the basis element of ${\cal A}_{(\pk,\des)}$ corresponding to the
$(\pk,\des)$-equivalence class of permutations with $j$ peaks and
$k$ descents. To count permutations in $S(\pi,\sigma)$ by peaks
and descents, we need to expand the Hadamard product $u_{n,j,k}*u_{1,1,1}$
as a linear combination of $u_{n+1,j^{\prime},k^{\prime}}$ for $0\leq j^{\prime}\leq\left\lfloor n/2\right\rfloor $
and $j^{\prime}\leq k^{\prime}\leq n-j^{\prime}$. We have 
\[
u_{1,0,0}=\frac{(1+y)t}{(1-t)^{2}}x=(1+y)x\sum_{m=0}^{\infty}mt^{m}.
\]
Thus for any power series $f(t)$, we have 
\[
f(t)*u_{1,0,0}=(1+y)xtf^{\prime}(t),
\]
which can be used to derive the formula 
\begin{multline*}
u_{n,j,k}*u_{1,0,0}=(j+1)u_{n+1,j,k}+(j+1)u_{n+1,j,k+1}\\
+(k-j)u_{n+1,j+1,k}+(n-j-k-1)u_{n+1,j+1,k+1}.
\end{multline*}
Thus, among the $n+1$ shuffles of $\pi$ and $\sigma$, $j+1$ have
$j$ peaks and $k$ descents, $j+1$ have $j$ peaks and $k+1$ descents,
$k-j$ have $j+1$ peaks and $k$ descents, and $n-j-k-1$ have $j+1$
peaks and $k+1$ descents. This can be proven using a simple combinatorial
argument if the single letter of $\sigma$ is greater than or smaller
than all of the letters of $\pi$, but it is not so easy in general.

\subsection{The \texorpdfstring{$\pk$}{pk} and \texorpdfstring{$\des$}{des} shuffle algebras}

Next, we state our results for the shuffle algebras ${\cal A}_{\pk}$
and ${\cal A}_{\des}$. Both ${\cal A}_{\pk}$ and ${\cal A}_{\des}$
are homomorphic images of ${\cal A}_{(\pk,\des)}$ obtained by setting
$y=1$ and $y=0$, respectively. In fact, Theorems \ref{t-pksc} and
\ref{t-dessc} presented below can be derived from Theorem \ref{t-pkdessc}
using Theorem \ref{t-quots} and these homomorphisms. An alternative
approach is to use Theorem \ref{t-scqsym} along with a specialization
of Stembridge's peak quasisymmetric functions obtained via enriched
$P$-partitions (for Theorem \ref{t-pksc}) or an analogous specialization
of the fundamental quasisymmetric functions (for Theorem \ref{t-dessc}).
\begin{thm}[Shuffle-compatibility of the peak number]
\label{t-pksc} \leavevmode
\begin{itemize}
\item [\normalfont{(a)}] The map given by
\[
[\pi]_{\pk}\mapsto\begin{cases}
{\displaystyle \frac{2^{2\pk(\pi)+1}t^{\pk(\pi)+1}(1+t)^{\left|\pi\right|-2\pk(\pi)-1}}{(1-t)^{\left|\pi\right|+1}}x^{\left|\pi\right|}}, & \text{if }\left|\pi\right|\geq1,\\
1/(1-t), & \text{if }\left|\pi\right|=0,
\end{cases}
\]
is a $\mathbb{Q}$-algebra isomorphism from ${\cal A}_{\pk}$ to the
span of 
\[
\left\{ \frac{1}{1-t}\right\} \bigcup\left\{ \frac{2^{2j+1}t^{j+1}(1+t)^{n-2j-1}}{(1-t)^{n+1}}x^{n}\right\} _{n\geq1,\:0\leq j\leq\left\lfloor \frac{n-1}{2}\right\rfloor },
\]
a subalgebra of $\mathbb{Q}[[t]][x]$ where multiplication is the
Hadamard product in $t$.
\item [\normalfont{(b)}] The $\pk$ shuffle algebra ${\cal A}_{\pk}$ is
isomorphic to the span of 
\[
\{1\}\cup\{p^{j}x^{n}\}_{n\geq1,\:1\leq j\leq n,\:j\equiv n\,(\mathrm{mod}\,2)},
\]
a subalgebra of $\mathbb{Q}[p,x]$.
\end{itemize}
\end{thm}
%
\begin{thm}[Shuffle-compatibility of the descent number]
\label{t-dessc} \leavevmode
\begin{itemize}
\item [\normalfont{(a)}] The map given by
\[
[\pi]_{\des}\mapsto\begin{cases}
{\displaystyle \frac{t^{\des(\pi)+1}}{(1-t)^{\left|\pi\right|+1}}x^{\left|\pi\right|}}, & \text{if }\left|\pi\right|\geq1,\\
1/(1-t), & \text{if }\left|\pi\right|=0,
\end{cases}
\]
is a $\mathbb{Q}$-algebra isomorphism from ${\cal A}_{\des}$ to
the span of 
\[
\left\{ \frac{1}{1-t}\right\} \bigcup\left\{ \frac{t^{j+1}}{(1-t)^{n+1}}x^{n}\right\} _{n\geq1,\:0\leq j\leq n-1},
\]
a subalgebra of $\mathbb{Q}[[t]][x]$ where multiplication is the
Hadamard product in $t$.
\item [\normalfont{(b)}] The map given by
\[
[\pi]_{\des}\mapsto\begin{cases}
{\displaystyle {p-\des(\pi)+\left|\pi\right|-1 \choose \left|\pi\right|}x^{\left|\pi\right|}}, & \text{if }\left|\pi\right|\geq1,\\
1, & \text{if }\left|\pi\right|=0,
\end{cases}
\]
is a $\mathbb{Q}$-algebra isomorphism from ${\cal A}_{\des}$ to
the span of 
\[
\{1\}\bigcup\left\{ {p-j+n-1 \choose n}x^{n}\right\} _{n\geq1,\:0\leq j\leq n-1},
\]
a subalgebra of $\mathbb{Q}[p,x]$.
\item [\normalfont{(c)}] The $\des$ shuffle algebra ${\cal A}_{\des}$
is isomorphic to the span of 
\[
\{1\}\cup\{p^{j}x^{n}\}_{n\geq1,\:1\leq j\leq n},
\]
a subalgebra of $\mathbb{Q}[p,x]$.
\end{itemize}
\end{thm}

\section{Open problems}

We now state a couple permutation statistics that we conjecture to
be shuffle-compatible.
\begin{conjecture}
\label{c-scconj} The descent statistics $(\udr,\pk)$, and $(\udr,\pk,\des)$
are shuffle-compatible.
\end{conjecture}
Define the \textit{exterior peak set} $\Epk$ by
\[
\Epk(\pi)\coloneqq\begin{cases}
\Lpk(\pi), & \mbox{if }n-1\in\Des(\pi)\\
\Lpk(\pi)\cup\{n\}, & \mbox{otherwise},
\end{cases}
\]
for $\pi\in\mathfrak{P}_{n}$. In a previous version of \cite{Gessel2017},
we conjectured that $\Epk$ is shuffle-compatible; this has been verified
by Darij Grinberg \cite{Grinberg2017} using a $P$-partition argument.
Prior to this, Grinberg had shown that $\QSym$ is a ``dendriform
algebra'' \cite{Grinberg2017a}, an algebra whose multiplication can
be split into a ``left multiplication'' and a ``right multiplication''
satisfying certain axioms. With the shuffle-compatibility of $\Epk$,
Grinberg proved that ${\cal A}_{\Epk}$ is a dendriform quotient of
$\QSym$. Other statistics that Grinberg has shown to define dendriform
quotients of $\QSym$ include $\des$, $(\des,\maj)$, and $\Lpk$.
On the other hand, $\maj$ and $\Pk$ do not have this property. In
addition to investigating whether the statistics stated in Conjecture
\ref{c-scconj} are in fact shuffle-compatible, it is also an open
problem to determine which other shuffle-compatible descent statistics
define dendriform quotients of $\QSym$.

%Finally, we present the following conjecture.
%\begin{conjecture}
%Every shuffle-compatible permutation statistic is a descent statistic.
%\end{conjecture}
\acknowledgements{We thank Bruce Sagan and an anonymous referee for providing extensive feedback on a preliminary version of our paper \cite{Gessel2017}; Marcelo Aguiar, Sami Assaf, Darij Grinberg, and Kyle Petersen for helpful discussions on this project; and another anonymous referee for their suggestions which improved the presentation of this extended abstract.}

\printbibliography
\end{document}
