\documentclass[ALCO,published]{cedram}
\usepackage{latexsym,tikz,hyperref,shuffle}
\DeclareMathOperator{\des}{des}
\DeclareMathOperator{\Des}{Des}
\DeclareMathOperator{\cdes}{cdes}
\DeclareMathOperator{\cDes}{cDes}
\DeclareMathOperator{\Pk}{Pk}
\DeclareMathOperator{\pk}{pk}
\DeclareMathOperator{\cPk}{cPk}
\DeclareMathOperator{\cpk}{cpk}
\DeclareMathOperator{\tor}{tor}
\DeclareMathOperator{\cyc}{cyc}
\DeclareMathOperator{\cQSym}{cQSym}
\DeclareMathOperator{\QSym}{QSym}
\DeclareMathOperator{\sym}{Sym}
\DeclareMathOperator{\Comp}{Comp}
\DeclareMathOperator{\cComp}{cComp}
\DeclareMathOperator{\Asc}{Asc}
\DeclareMathOperator{\st}{st}
\usetikzlibrary{arrows.meta}
\newcommand{\sbe}{\subseteq}
\newcommand{\al}{\alpha}
\newcommand{\be}{\beta}
\newcommand{\cA}{\mathcal{A}}
\newcommand{\cM}{\mathcal{M}}
\newcommand{\mch}[2]{
\left.\mathchoice
{\left(\kern-0.48em\binom{#1}{#2}\kern-0.48em\right)}
{\big(\kern-0.30em\binom{\smash{#1}}{\smash{#2}}\kern-0.30em\big)}
{\left(\kern-0.30em\binom{\smash{#1}}{\smash{#2}}\kern-0.30em\right)}
{\left(\kern-0.30em\binom{\smash{#1}}{\smash{#2}}\kern-0.30em\right)}
\right.}
\allowdisplaybreaks
\title
{Enriched toric $[\vec{D}]$-partitions}
\author[\initial{J.} \middlename{} Liang]{\firstname{Jinting} \middlename{} \lastname{Liang}}
\address{Michigan State University\\
Department of Mathematics\\
619 Red Cedar Road\\
C212 Wells Hall\\
East Lansing\\
MI 48824-1027 (USA)}
\email{liangj26@msu.edu}
\keywords{Cyclic peak, cyclic permutation, cyclic quasi-symmetric function, enriched $P$-partition, toric poset, order polynomial}
\subjclass{05A05, 05E05, 06A11}
\datepublished{2024-01-08}
\begin{document}
\begin{abstract}
This paper develops the theory of enriched toric $[\vec{D}]$-partitions. Whereas Stembridge's enriched $P$-partitions give rise to the peak algebra which is a subring of the ring of quasi-symmetric functions $\mathrm{QSym}$, our enriched toric $[\vec{D}]$-partitions generate the cyclic peak algebra which is a subring of the ring of cyclic quasi-symmetric functions $\mathrm{cQSym}$. In the same manner as the peak set of linear permutations appears when considering enriched $P$-partitions, the cyclic peak set of cyclic permutations plays an important role in our theory. The associated order polynomial is discussed based on this framework.
\end{abstract}
\maketitle
\section{Introduction}
Denote by $\mathbb{N}$ and $\mathbb{P}$ the set of nonnegative integers
and positive integers respectively.
For $m,n\in\mathbb{N}$, define $[m,n]=\{m,m+1,\ldots,n\}$ and write $[n]=[1,n]$ when $m=1$. A {\em linear permutation} of a set $A\subset \mathbb{P}$
is an arrangement $w=w_1w_2\dots w_n$ of elements in $A$ where each element is used exactly once.
In this case, we call $n$ the {\em length} of $w$, written as $\#w=|w|=n$. Let $\mathcal{S}_n$ be the symmetric group on $[n]$ viewed as the set of linear permutations of $[n]$.
A {\em linear permutation statistic} is a function whose domain is the set of all linear permutations. For a linear permutation $w=w_1w_2\dots w_n$, a {\em descent} of $w$ is a position~$i$
such that $w_i>w_{i+1}$. The {\em descent set} $\Des$ is defined by
\[
\Des w=\{i\mid \text{$i$ is a descent of $w$}\}\sbe[n-1].
\]
The {\em descent number} of $w$ is $\des w:=|\Des w|$. A {\em peak} of $w$ is a position $i$ such that $w_{i-1}w_{i+1}$. The {\em peak set} $\Pk$ is defined by
\[
\Pk w=\{i\mid \text{$i$ is a peak of $w$}\}\sbe[2,n-1].
\]
The {\em peak number} is $\pk w:=|\Pk w|$.
Quasi-symmetric functions first appeared implicitly as generating functions in Richard Stanley's theory of $P$-partitions~\cite{MR0332509},
and then were explicitly studied by Ira M. Gessel~\cite{MR777705}. To be more precise, for a finite poset $P$, the set of $P$-partitions can be partitioned according to the linear extensions of $P$, where each subset corresponds to a fundamental quasi-symmetric function indexed by the descent set of that linear permutation. The ring $\QSym$ of quasi-symmetric functions was further developed, see~\cite{MR1982883,MR3810249,MR1897637} for some related articles.
It found applications in enumerative combinatorics, representation theory and algebraic geometry~\cite{MR1794711,MR2196760,MR3203651}. In the same vein, Stembridge's work~\cite{S:epp} on enriched $P$-partitions gave rise to the algebra of peaks $\Pi$, a graded subring of $\QSym$, which is closely related to the peak set.
For a linear permutation $w=w_1w_2\dots w_n$, we define the corresponding {\em cyclic permutation} $[w]$ to be the set of rotations of $w$, that is,
\[
[w]=\{w_1w_2\dots w_n, \hspace{7pt} w_2\dots w_nw_1,\hspace{7pt}\ldots,\hspace{7pt} w_nw_1\dots w_{n-1}\}.
\]
Let $[\mathcal{S}_n]$ denote the set of cyclic permutations on $[n]$.
The {\em cyclic descent set} $\cDes$ of a linear permutation $w$ is defined by
\[
\cDes w=\{i\mid \text{$w_i>w_{i+1}$ where the subscripts are taken modulo $n$} \}\sbe[n].
\]
This leads to the {\em cyclic descent set} of a cyclic permutation
\[
\cDes[w]=\{\{ \cDes\sigma\mid\sigma\in[w] \}\},
\]
where the double curly brackets denote a multiset. The multiplicity comes into play since $\cDes$ may have the same value on different representatives $\sigma$ in $[w]$. In fact, one can regard the cyclic permutation statistic $\cDes$ as an analogue of $\Des$ in the linear setting. Similarly, if we define the {\em cyclic peak set} $\cPk$ of a linear permutation $w$ by
\[
\cPk w=\{i\mid \text{$w_{i-1}w_{i+1}$ where the subscripts are taken modulo $n$} \}\sbe[n],
\]
then the cyclic counterpart of $\Pk$, the {\em cyclic peak set} $\cPk$ of a cyclic permutation, is defined as
\[
\cPk[w]=\{\{ \cPk\sigma\mid\sigma\in[w] \}\}.
\]
\begin{exam}\label{ex:set}
Consider the permutation $w=3124$ on $[4]$, then
\[
\Des w=\{1\},\;\cDes w=\{1,4\},\;\Pk w=\emptyset,\;\cPk w=\{4\}.
\]
\end{exam}
\begin{rema}\label{remark: cPk[w]}
By definition, $\cDes[w]$ carries the information for all representatives in~$[w]$. Moreover, $\cDes w$ together with $|w|$ will be sufficient to determine $\cDes[w]$.
In fact, $\cDes[w]$ is simply the multiset of all cyclic shifts of $\cDes w$ in $[n]$ where $n=|w|$, namely,
\[
\cDes[w]=\{\{\,i+\cDes w\mid i\in[n] \,\}\}.
\]
Here $i+\cDes w$ is the set defined by (\ref{eq:i+E}).
Similarly, $\cPk[w]$ can be entirely determined by $\cPk w$ and $|w|$.
\end{rema}
\begin{exam}
Consider the permutation $w=1423$ and the corresponding cyclic permutation $[w]=\{1423,3142,2314,4231\}$, we have
\[
\cDes [w]=\cPk[w]=\{\{\,\{2,4\},\{1,3\},\{2,4\},\{1,3\}\,\}\}.
\]
Noting that $\cDes w=\cPk w=\{2,4\}$, one can easily check that the previous remark does hold.
\end{exam}
In the work~\cite{agrr:cqf} of Adin, Gessel, Reiner, and Roichman, the ring $\cQSym$ of cyclic quasi-symmetric functions was introduced from toric $P$-partition enumerators, in which case the cyclic descent set $\cDes$ plays an important role. The authors also asked for a cyclic version of the algebra of peaks, to which question we will give an answer in this paper.
This article is devoted to the study of enriched toric $[\vec{D}]$-partitions. By the end, we will construct an algebra of cyclic peaks in $\cQSym$ analogous to the algebra of peaks. The rest of this paper is structured as follows. In the next section, we recall definitions of various terms such as quasi-symmetric functions and cyclic quasi-symmetric functions, with several concrete examples provided. Section~\ref{ep} introduces enriched $\vec{D}$-partitions in terms of directed acyclic graphs (DAGs). In section~\ref{etp}, we define enriched toric $[\vec{D}]$-partitions and develop some of their properties. Section~\ref{we} will review the weight enumerators of enriched $\vec{D}$-partitions defined by Stembridge and discuss the cyclic analogues for enriched toric $[\vec{D}]$-partitions. The weight enumerators corresponding to different cyclic peak sets generate a subring of $\cQSym$ which we call the algebra of cyclic peaks. We also compute the order polynomial of enriched toric $[\vec{D}]$-partitions.
\section{Basic definitions and results}\label{bd}
\subsection{Sets and compositions}
We will use $\leq$ with no subscript to denote the ordinary total order on $\mathbb{Z}$, the set of integers. For $n\in\mathbb{P}$, let $2^{[n]}$ denote the set of all subsets of $[n]$, and let $2^{[n]}_0$ be the set of all nonempty subsets of $[n]$. Denote by $\Comp_n$ the set of all compositions of $n$ and write $\alpha\vDash n$ for $\alpha\in\Comp_n$. Define a {\em cyclic shift} of a subset $E\sbe[n]$ in $[n]$ to be a set of the form
\begin{equation}\label{eq:i+E}
i+E=\{\text{$i+e$ (mod n)}\mid e\in E\}.
\end{equation}
Note that sometimes we will use $E+i$ as well for the same concept. While using a negative shift, the reader should be careful to distinguish between $E-i$ and the set difference $E-\{i\}=E\setminus \{i\}$.
A {\em cyclic shift} of a composition $\alpha=(\alpha_1,\alpha_2,\ldots,\alpha_m)$ is a composition of the form
\[
(\alpha_k,\ldots,\alpha_m,\alpha_1,\ldots,\alpha_{k-1})
\]
for some $k\in[m]$.
We adopt the notations from \cite{agrr:cqf} and denote by $c2^{[n]}_0$ (respectively, $\cComp_n$) the set of equivalence classes of elements of $2^{[n]}_0$ (respectively, $\Comp_n$) under cyclic shifts.
Here we recall two natural bijections which will play important roles when indexing two particular bases of (cyclic) quasi-symmetric functions.
The first natural bijection is between $2^{[n-1]}$ and $\Comp_n$. The map~$\Phi:2^{[n-1]} \to\Comp_n$ is defined by
\begin{equation}\label{eq:Phi}
\Phi(E):=(e_1-e_0,e_2-e_1,\ldots,e_k-e_{k-1},e_{k+1}-e_k)
\end{equation}
for any given $E=\{e_10$ implies $ij$.
\end{enumerate}
Denote by $\mathcal{E}(\vec{D})$ the set of all enriched $\vec{D}$-partitions $f$.
\end{defi}
\begin{rema}
\hfill
\begin{enumerate}
\item In this definition we are using two order structures on the domain $[n]$: the order $\to$ induced by DAG ${\vec{D}}$ and the ordinary total order $\leq$ on integers in (b) and (c). Both of them will impose restrictions on the possible choices for~$f$. As for the range $\mathbb{P'}$, we also use two order structures: the total order $\preceq$ defined by Stembridge in (a) and the usual order $\leq$ on the integers in (b) and (c).
\item If $\vec{D}=w$ is a total linear order, the structure of the set of enriched $w$-partitions is quite simple:
\begin{equation}\label{eq:enriched}
\begin{array}{rl}
\mathcal{E}(w)=\{\,f:[n]\to \mathbb{P'} ~| & f(w_1)\preceq\cdots\preceq f(w_n), \\
& f(w_i)=f(w_{i+1})>0 \Rightarrow i\notin \Des(w),\\
& f(w_i)=f(w_{i+1})<0 \Rightarrow i\in \Des(w)\,\}.\\
\end{array}
\end{equation}
\end{enumerate}
\end{rema}
The following fundamental lemma is a straightforward analogue of Stembridge \cite[Lemma 2.1]{S:epp}.
\begin{lemma} [Fundamental lemma of enriched $\vec{D}$-partitions]
\label{FLEDP}
For any DAG $\vec{D}$ with vertex set $[n]$, one has a decomposition of $\mathcal{E}(\vec{D})$ as the following disjoint union:
$$\mathcal{E}(\vec{D})=\bigsqcup_{w\in \mathcal{L}(\vec{D})}\mathcal{E}(w).$$
\end{lemma}
\begin{proof}
Given an enriched $\vec{D}$-partition $f$. First we arrange the elements of $[n]$ in a weakly increasing order of $f$-values with respect to the total order $\preceq$ on the range. Then if some elements in $[n]$ have the same $f$-value $-k$ (respectively, $+k$) for some positive integer $k$, we arrange them in a decreasing (respectively, increasing) order with respect to the usual order $\leq$ on the domain. The resulting permutation $w$ is unique with $f\in\mathcal{E}(w)$, and $w$ linearly extends $\vec{D}$. On the other hand, for $w\in \mathcal{L}(\vec{D})$, every enriched $w$-partition is also an enriched $\vec{D}$-partition. Therefore the conclusion follows.
\end{proof}
\begin{exam}
Returning to Example \ref{DAG on [4]}, since $\mathcal{L}(\vec{D}_3)=\{2431,2413\}$,
by the Fundamental Lemma,
$\mathcal{E}(\vec{D}_3)=\mathcal{E}(2431)\uplus \mathcal{E}(2413)$.
\end{exam}
\section{Enriched toric \texorpdfstring{$[\vec{D}]$}{[D]}-partitions for toric DAGs}\label{etp}
In this section, we review the toric DAGs and toric posets as cyclic analogues of DAGs and posets. Then we define enriched toric $[\vec{D}]$-partitions and develop some of their properties. The concept of toric poset was originally defined and studied by Develin, Macauley and Reiner in \cite{Dmr:tpo}. Here we follow the presentation from Adin, Gessel, Reiner and Roichman \cite{agrr:cqf}.
Just like a linear permutation has a corresponding cyclic permutation as the equivalence class under the equivalence of rotation,
for a DAG, we will define an equivalence relation and consider the equivalence class to be the corresponding toric DAG. It turns out that if $w$ is a linear extension of the DAG $\vec{D}$, then $[w]$ is a toric extension of the corresponding toric DAG $[\vec{D}]$.
A DAG $\vec{D}$ on $[n]$ has $i_0\in[n]$ as a {\em source} (respectively, {\em sink}) if $\vec{D}$ does not contain $j\to i_0$ (respectively, $i_0\to j$) for any $j\in[n]$. Suppose $i_0$ is a source or a sink in $\vec{D}$, we say $\vec{D}'$ is obtained from $\vec{D}$ by a {\em flip} at $i_0$ if $\vec{D}'$ is obtained by reversing all arrows containing $i_0$. We define the equivalence relation $\equiv$ on DAGs as follows:
$\vec{D}'\equiv\vec{D}$ if and only if $\vec{D}'$ is obtained from $\vec{D}$ by a sequence of flips.
A {\em toric} DAG is the equivalence class $[\vec{D}]$ of a DAG $\vec{D}$.
In particular, if $\vec{D}=w=w_1 w_2\ldots w_n$ is a total linear order, the next proposition claims that the corresponding toric DAG $[\vec{D}]$ can be identified with the cyclic permutation $[w]$.
\begin{prop}[\protect{\cite[Proposition 4.2]{Dmr:tpo}}]\label{prop:cp}
If $\vec{D}=w$ is a total linear order with~$w=w_1\ldots w_n$, then there is a bijection between toric DAG $[\vec{D}]$ and cyclic permutation~$[w]$.
\end{prop}
\begin{exam}
The total linear order $\vec{D}_1=2431$ from Example \ref{DAG on [4]} has a corresponding toric DAG $[\vec{D}_1]$:
\begin{center}
\begin{tikzpicture}[scale=1.1, yshift=10in]
\draw[-{Stealth[scale=1.0]}] (0.2,0.2) -- (1.8,1.8);
\draw[-{Stealth[scale=1.0]}] (0,0.2) -- (0,1.8);
\draw[-{Stealth[scale=1.0]}] (0.2,0) -- (1.8,0) node[pos=.5, below=6pt] {$\vec{D}_1=2431$};
\draw[-{Stealth[scale=1.0]}] (2,0.2) -- (2,1.8);
\draw[-{Stealth[scale=1.0]}] (1.8,0.2) -- (0.2,1.8);
\draw[-{Stealth[scale=1.0]}] (1.8,2) -- (0.2,2);
\foreach \Point/\PointLabel in {(0,0)/2, (2,0)/4, (2,2)/3, (0,2)/1}
\draw[fill=black] \Point circle (0) node {$\PointLabel$};
\end{tikzpicture}
\hspace{0.5in}
\begin{tikzpicture}[scale=1.1]
\draw[-{Stealth[scale=1.0]}] (0.2,0.2) -- (1.8,1.8);
\draw[-{Stealth[scale=1.0]}] (0,1.8) -- (0,0.2);
\draw[-{Stealth[scale=1.0]}] (0.2,0) -- (1.8,0) node[pos=.5, below=6pt] {$\vec{D}_1'=1243$};
\draw[-{Stealth[scale=1.0]}] (2,0.2) -- (2,1.8);
\draw[-{Stealth[scale=1.0]}] (0.2,1.8) -- (1.8,0.2);
\draw[-{Stealth[scale=1.0]}] (0.2,2)--(1.8,2) ;
\foreach \Point/\PointLabel in {(0,0)/2, (2,0)/4, (2,2)/3, (0,2)/1}
\draw[fill=black] \Point circle (0) node {$\PointLabel$};
\end{tikzpicture}
\hspace{0.5in}
\begin{tikzpicture}[scale=1.1]
\draw[-{Stealth[scale=1.0]}](1.8,1.8) -- (0.2,0.2);
\draw[-{Stealth[scale=1.0]}] (0,1.8) -- (0,0.2);
\draw[-{Stealth[scale=1.0]}] (0.2,0) -- (1.8,0) node[pos=.5, below=6pt] {$\vec{D}_1''=3124$};
\draw[-{Stealth[scale=1.0]}] (2,1.8) -- (2,0.2);
\draw[-{Stealth[scale=1.0]}] (1.8,2) -- (0.2,2);
\draw[-{Stealth[scale=1.0]}] (0.2,1.8) -- (1.8,0.2);
\foreach \Point/\PointLabel in {(0,0)/2, (2,0)/4, (2,2)/3, (0,2)/1}
\draw[fill=black] \Point circle (0) node {$\PointLabel$};
\end{tikzpicture}
\hspace{0.5in}
\begin{tikzpicture}[scale=1.1]
\draw[-{Stealth[scale=1.0]}](1.8,1.8) -- (0.2,0.2);
\draw[-{Stealth[scale=1.0]}] (0,1.8) -- (0,0.2);
\draw[-{Stealth[scale=1.0]}] (1.8,0)-- (0.2,0) node[pos=.5, below=6pt] {$\vec{D}_1'''=4312$};
\draw[-{Stealth[scale=1.0]}] (2,0.2) -- (2,1.8);
\draw[-{Stealth[scale=1.0]}] (1.8,2) -- (0.2,2);
\draw[-{Stealth[scale=1.0]}] (1.8,0.2) -- (0.2,1.8);
\foreach \Point/\PointLabel in {(0,0)/2, (2,0)/4, (2,2)/3, (0,2)/1}
\draw[fill=black] \Point circle (0) node {$\PointLabel$};
\end{tikzpicture}
\end{center}
They can be obtained by a sequence of flips:
$$
\vec{D}_1\xrightarrow{\text{flip at 1}}\vec{D}_1'\xrightarrow{\text{flip at 3}}\vec{D}_1''\xrightarrow{\text{flip at 4}}\vec{D}_1'''\xrightarrow{\text{flip at 2}}\vec{D}_1.
$$
Therefore, $[\vec{D}_1]$ can be identified with $[2431]=\{\,2431,1243,3124,4312\,\}$.
\end{exam}
As transitivity turns a DAG into a poset, we now introduce the definition of toric transitivity for a DAG, which will turn the corresponding toric DAG into a toric poset.
A DAG $\vec{D}$ with vertex set $[n]$ is {\em toric transitive} if the existence of a directed path $i_1\to i_2\to\dots\to i_k$ and $i_1\to i_k$ implies the existence of $i_a\to i_b$ in $\vec{D}$ for all $1\leq a**0$ we assign the weight $x_k$ to both $f$-values $k$ and $-k$.
\end{defi}
As a direct consequence of the Fundamental Lemma~\ref{FLECDP}, one has
\begin{equation}\label{eq:cyclic enumerator decomp}
\Delta_{[\vec{D}]}^{\cyc}=\sum_{[ w]\in\mathcal{L}^{\tor}([\vec{D}])}\Delta_{[w]}^{\cyc}.
\end{equation}
Therefore, it suffices to discuss $\Delta_{[w]}^{\cyc}$ for cyclic permutations $[w]$. It follows from the formula \eqref{e-KK} that $\Delta_{[w]}^{\cyc}$ can be expressed in terms of the weight enumerators $\{\Delta_v\}$ as
\begin{equation}\label{e-Dsum}
\Delta_{[w]}^{\cyc}=\sum_{v\in[w]}\Delta_v.
\end{equation}
Moreover, $\Delta_{[w]}^{\cyc}$ has the following expression.
\begin{prop}\label{prop:crucial}
For any given cyclic permutation $[w]$ of length $n$, we have
\begin{equation}\label{eq:depend on cPk}
\Delta_{[w]}^{cyc}=\sum_{\substack{E\subseteq[n]:\\[4pt]\cPk(w)\sbe E\cup(E+1)}}2^{|E|}M_{n,E}^{cyc},
\end{equation}
with $E+1$ defined by~\eqref{eq:i+E}.
The sum is independent of the choice of representative $w$ of $[w]$.
\end{prop}
\begin{proof}
The independence of the choice of representatives is a result of the following two observations:
\begin{enumerate}
\item[(a)] If $E$ and $E'$ only differ by a cyclic shift, one has $|E|=|E'|$ and $M_{n,E}^{cyc}=M_{n,E'}^{cyc}$.
\item[(b)] For two representatives $w$ and $w'$ of $[w]$,
\[
\{E\subseteq[n]:\cPk(w)\sbe E\cup(E+1)\}=\{E'\sbe[n]:\cPk(w')\sbe E'\cup(E'+1)\}+i,
\]
for some $i\in[n]$, namely, the two sets only differ by a cyclic shift.
\end{enumerate}
Now fix a representative $w$ of $[w]$. We rewrite both sides of equation~\eqref{eq:depend on cPk} as follows:
\begin{equation}\label{eq:alpha_E}
\mathrm{RHS}\overset{(i)}{=}\sum_{\substack{F\sbe[n]:\\[4pt]\cPk(w)\sbe F\cup(F+1)}}2^{|F|}\sum_{f\in F} M_{n,(F-f)\cap[n-1]}\overset{(ii)}{=}\sum_{E\sbe[n-1]}2^{|E|+1}\alpha_E M_{n,E}
\end{equation}
where $\alpha_E=\#A_E$, with
$$A_E=\{(F,f): f\in F\sbe[n]\text{ with } \cPk(w)\sbe F\cup(F+1),\;E=(F-f)\cap[n-1]\}.$$
Here equality $(i)$ is a result of applying equation~\eqref{eq:monomial to cyclic monomial} to move from cyclic monomial to monomial quasi-symmetric functions, while equality $(ii)$ is obtained by calculating the coefficient of $M_{n,E}$. It is noted that in equality $(ii)$, for each pair $(F,f)\in A_E$, we have $n\in F-f$.
As a result, $E=(F-f)\cap[n-1]=(F-f)\setminus \{n\}$. Therefore their cardinalities satisfy $|F|=|E|+1$.
\begin{equation}\label{eq:beta_E}
\begin{split}
\mathrm{LHS} &\overset{(i)'} {=}\sum_{v\in[w]}\Delta_v\\
& \overset{(ii)'}{=}\sum_{v\in[w]}\sum_{\substack{E\sbe[n-1]:\\[4pt] \Pk(v)\sbe E\cup(E+1)}}2^{|E|+1}M_{n,E}\\[2pt]
&\overset{(iii)'}{=}\sum_{E\sbe[n-1]}\beta_E 2^{|E|+1}M_{n,E}
\end{split}
\end{equation}
where $\beta_E=\#B_E$ with $$B_E=\{i\in[n]: (\cPk w-i)\cap[2,n-1]\sbe E\cup(E+1)\}.$$
Equality $(i)'$ follows from equation~\eqref{e-Dsum}. Equality $(ii)'$ is obtained by applying equation~\eqref{eq:M_E expansion} to express the weight enumerator $\Delta_v$ in terms of monomial quasi-symmetric functions.
Equality $(iii)'$ follows from the observation
\[
\{\{\,\Pk(v):v\in[w]\,\}\}=\{\{\,(\cPk w-i)\cap[2,n-1]:i\in[n]\,\}\}.
\]
By comparing equations~\eqref{eq:alpha_E} and \eqref{eq:beta_E}, it suffices to prove that $\alpha_E=\beta_E$ for every $E\sbe[n-1]$, or equivalently, to construct a bijection between $A_E$ and $B_E$.
Set $\theta_E:A_E\to B_E$ as $\theta_E(F,f)=f$. To prove that this map is well-defined, it suffices to show that for each $(F,f)\in A_E$, we have $f\in B_E$. It follows from the definition of $A_E$ that $F-f=E\cup\{n\}$. Applying the operation on both sides of the inclusion $\cPk(w)\sbe F\cup(F+1)$, we get
$$\cPk(w)-f\sbe (F-f)\cup(F-f+1)=E\cup(E+1)\cup\{1,n\}.$$
Hence $(\cPk w-f)\cap[2,n-1]\sbe E\cup(E+1)$ and $f\in B_E$.
Conversely, define $\sigma_E:B_E\to A_E$ by $\sigma_E(f)=(\,(E+f)\cup\{f\},f\,)$. One can similarly check that this map is well-defined.
It is straightforward to verify that $\theta_E$ and $\sigma_E$ are inverse to each other, hence we get a bijection between $A_E$ and $B_E$. This finishes the proof.
\end{proof}
\begin{rema}
As a direct corollary of the above proposition, $\Delta_{[\vec{D}]}^{\cyc}$ is a homogeneous cyclic quasi-symmetric function of degree $n$, and that $\Delta_{[w]}^{\cyc}$ depends only on $\cPk[w]$, or equivalently (by Remark~\ref{remark: cPk[w]}) on $\cPk w$ for any representative $w$.
\end{rema}
\begin{exam}
Let $w=1243$ so that $[w]=\{1243,3124,4312,2431\}$ and $\cPk(w)=\{3\}$; $\pi=1324$, $[\pi]=\{1324,4132,2413,3241\}$ and $\cPk(\pi)=\{2,4\}$.
To use Proposition~\ref{prop:crucial} for calculation, we first need all possible choices of $E\subseteq[4]$ satisfying $\{3\}=\cPk w\sbe E\cup(E+1)$, which are
{\small \begin{gather*}
\{1,2,3,4\},\{1,2,3\},\{1,2,4\},\{1,3,4\},\{2,3,4\}, \{1,2\},\{1,3\},\{2,3\},\{2,4\},\{3,4\},\{2\},\{3\},
\end{gather*} }
with corresponding monomial cyclic quasi-symmetric functions
\[ \arraycolsep=1.4pt\def\arraystretch{1.4}
\begin{array}{ccl}
M^{cyc}_{(1,1,1,1)} &=&M^{cyc}_{4,\{1,2,3,4\}}, \\[1ex]
M^{cyc}_{(2,1,1)} &=& M^{cyc}_{4,\{1,2,3\}}=M^{cyc}_{4,\{1,2,4\}}=M^{cyc}_{4,\{1,3,4\}}=M^{cyc}_{4,\{2,3,4\}}, \\[1ex]
M^{cyc}_{(3,1)} &=&M^{cyc}_{4,\{1,2\}}=M^{cyc}_{4,\{2,3\}}=M^{cyc}_{4,\{3,4\}}, \\[1ex]
M^{cyc}_{(2,2)} &=&M^{cyc}_{4,\{1,3\}}=M^{cyc}_{4,\{2,4\}}, \\[1ex]
M^{cyc}_{(4)} &=&M^{cyc}_{4,\{2\}}=M^{cyc}_{4,\{3\}}. \\
\end{array}
\]
Applying equation~\eqref{eq:depend on cPk}, we have
\[
\Delta_{[w]}^{cyc}
=2^4M^{cyc}_{(1,1,1,1)}+4\cdot 2^3M^{cyc}_{(2,1,1)}+3\cdot 2^2M^{cyc}_{(3,1)}+2\cdot 2^2M^{cyc}_{(2,2)}+2\cdot 2M^{cyc}_{(4)}.
\]
Similarly for $\pi$, all possible choices of $E\subseteq[4]$ satisfying $\{2,4\}=\cPk \pi\sbe E\cup(E+1)$ are as follows:
\begin{equation*}
\{1,2,3,4\},\{1,2,3\},\{1,2,4\},\{1,3,4\},\{2,3,4\},\{1,3\},\{1,4\},\{2,3\},\{2,4\},
\end{equation*}
hence by equation~\eqref{eq:depend on cPk},
\[
\Delta_{[\pi]}^{cyc}
= 2^4M^{cyc}_{(1,1,1,1)}+4\cdot 2^3M^{cyc}_{(2,1,1)}+2\cdot 2^2M^{cyc}_{(3,1)}+2\cdot 2^2M^{cyc}_{(2,2)}.
\]
It follows from the calculation above that
\[
\Delta_{[w]}^{cyc}+\Delta_{[\pi]}^{cyc}=2\cdot 2^4M^{cyc}_{(1,1,1,1)}+8\cdot 2^3M^{cyc}_{(2,1,1)}+5\cdot 2^2M^{cyc}_{(3,1)}+4\cdot 2^2M^{cyc}_{(2,2)}+2\cdot 2M^{cyc}_{(4)},
\]
which is exactly what we obtained in Example~\ref{ex:enumerate toric}.
\end{exam}
\subsection{Algebra of cyclic peaks}\label{sec:alcp}
We say $S$ is a {\em cyclic peak set in $[n]$} if there exists some $w\in\mathcal{S}_n$ with $\cPk w=S$. It follows from Proposition~\ref{prop:crucial} that, for any cyclic peak set $S$ in $[n]$, we can define an associated cyclic quasi-symmetric function by
\begin{equation*}
K^{\cyc}_{n,S}:=\Delta^{\cyc}_{[w]},
\end{equation*}
for any permutation $w$ with $\cPk w=S$. One can observe that $\Delta^{\cyc}_{[w]}=K^{\cyc}_{n,\cPk w}$ and rewrite equation~\eqref{eq:cyclic enumerator decomp} as
\[
\Delta^{\cyc}_{[\vec{D}]}=\sum_{[w]\in \mathcal{L}^{\tor}([\vec{D}])}K^{\cyc}_{n,\cPk w}.
\]
Moreover, it follows from formula \eqref{e-KK} that $K^{\cyc}_{n,S}$ can be expressed in terms of the quasi-symmetric functions $\{K_{n,T}\}$ as
\[
K^{\cyc}_{n,S}=\sum_{\sigma\in[w]} K_{n,\Pk\sigma},
\]
where $\cPk w=S$.
Let $\Lambda_n$ denote the vector space of cyclic quasi-symmetric functions spanned by~$K^{\cyc}_{n,S}$ where $S$ ranges over cyclic peak sets in $[n]$, and set $\Lambda=\oplus_{n\geq 0}\Lambda_n$. We will show that~$\Lambda$ is an algebra by proving that the product of $K^{\cyc}_{n,U}$ and $K^{\cyc}_{n,T}$ is a linear combination of $K^{\cyc}_{n,S}$'s. We call $\Lambda$ the {\em algebra of cyclic peaks}.
\begin{lemma}
The $K^{\cyc}_{n,S}$ are linearly independent, where $S$ are, up to cyclic shift, distinct cyclic peak sets.
\end{lemma}
\begin{proof}
For this proof, we totally order the subsets of $[n-1]$,
first by cardinality, then by the lexicographic order. We therefore have
\[
\emptyset\lhd\{1\}\lhd\{2\}\lhd\cdots\lhd\{n-1\}\lhd\{1,2\}\lhd\{1,3\}\lhd\cdots\lhd\{1,n-1\}\lhd\{2,3\}\lhd\{2,4\}\lhd\cdots.
\]
One can similarly order the compositions of $n$ as
\[
(n)\lhd(1,n-1)\lhd(2,n-2)\lhd\cdots\lhd(1,1,n-2)\lhd(1,2,n-3)\lhd\cdots\lhd(1,n-2,1)\lhd\cdots.
\]
Noting that $K^{\cyc}_{n,S}=K^{\cyc}_{n,S'}$ if the sets $S$ and $S'$ only differ by a cyclic shift, we will always assume the index set $S$ to be the least among all its cyclic shifts.
It is not hard to see that $\psi(S)$ is also the least composition among all its cyclic shifts, where $\psi$ is defined by equation \eqref{eq:psi}.
We now show that the matrix of $\{K^{\cyc}_{n,S}\}$ with respect to the basis $\{M^{\cyc}_{n,L}\}$ has full rank.
Then the linear independence of $\{K^{\cyc}_{n,S}\}$ will follow immediately from the fact that the monomial cyclic quasi-symmetric functions form a basis of $\cQSym$.
Let us fix $n$ and suppose $\{S_1\lhd S_2\lhd\ldots\lhd S_m\}$ is the set of all distinct cyclic peak sets in $[n]$. Given a $K^{\cyc}_{n,S}$, suppose $|S|=k$ and $S=\{1=s_1j$, or equivalently, the term $M^{\cyc}_{n,f(S_j)}$ does not appear in the expression of $K^{\cyc}_{n,S_i}$ if $S_j\lhd S_i$.
Suppose towards a contradiction that $A_{i,j}\neq0$ for some $i>j$. It then follows from Proposition~\ref{prop:crucial}
that there exists some $E\subseteq[n]$ such that
\[
S_i\subseteq E\cup(E+1)\quad \text{and}\quad M^{\cyc}_{n,f(S_j)}=M^{\cyc}_{n,E}.
\]
Since $S_i$ is a cyclic peak set, $e$ and $e+1$ cannot be in $S_i$ at the same time. It then follows from the assumption $S_i\subseteq E\cup(E+1)$ that $|E|\geq |S_i|$. The condition $i>j$ implies $S_i\rhd S_j$, hence $|S_i|\geq |S_j|=|f(S_j)|=|E|$. Therefore, we only need to consider the cases when $S_i$ and $S_j$ have the same cardinality.
Suppose
\[
\psi(S_i)=(\alpha_1,\al_2,\ldots,\al_k),\quad \psi(S_j)=(\be_1,\be_2,\ldots,\be_k),\quad \psi(E)=(\be_1',\be_2',\ldots,\be_k').
\]
Then $\psi(E)=(\be_1',\be_2',\ldots,\be_k')$ is a cyclic shift of
\[
\psi(f(S_j))=(\be_1-1,\be_2,\ldots,\be_{k-1},\be_k+1).\]
Assume
\[
(\be_q',\be_{q+1}',\ldots,\be_{q-1}')=(\be_1-1,\be_2,\ldots,\be_{k-1},\be_k+1),
\]
for some $q\in[k]$. Since $S_i\subseteq E\cup(E+1)$, $|S_i|=|E|$, and $S_i$ does not have cyclically consecutive elements, each $a\in S_i$ corresponds to a unique $a'\in E$ where $a'$ equals either $a$ or $a-1$ (considered modulo $n$). A crucial observation therefore follows:
\begin{equation}\label{inequ3}
\text{$|(\al_r+\cdots+\al_s)-(\be_r'+\cdots+\be_s')|\leq 1$\quad for $r,s\in[k]$.}
\end{equation}
In particular,
\[\al_1\leq\al_q\leq\be_q'+1=(\be_1-1)+1=\be_1,\]
where the first inequality comes from the fact that $S_i$ is the least among its cyclic shifts, and the second one follows from~\eqref{inequ3} by taking $r=s=q$.
Note that $S_j\lhd S_i$ implies $\psi(S_j)\lhd\psi(S_i)$, so $\be_1\leq \al_1$. Thus, necessarily,
\[\al_1=\al_q=\be_q'+1=\be_1.\]
It then follows from the inequality \eqref{inequ3} that for any $r\in[k-1]$,
\[
\al_q+\cdots+\al_{q+r}\leq \be_q'+\cdots+\be_{q+r}'+1=\be_1+\cdots+\be_{1+r}+\delta_{1+r,k},
\]
where $\delta_{1+r,k}=1$ if $1+r=k$ and $0$ otherwise.
If $\al_{q+r}=\be_{1+r}$ for every $r\in[k-2]$, then $\psi(S_i)$ is a cyclic shift of $\psi(S_j)$,
which contradicts our assumption $S_i\rhd S_j$.
Now assume that $t\in[k-2]$ is the smallest index such that $\al_{q+t}\neq \be_{1+t}$. Then necessarily $\al_{q+t}<\be_{1+t}$, and
\[
(\al_{q},\dots,\al_{q+t})\lhd(\be_1,\dots,\be_{1+t}).
\]
Combined with the inequality $(\al_1,\ldots,\al_{1+t})\unlhd(\al_{q},\ldots,\al_{q+t})$, as $(\al_1,\ldots,\al_k)$ is the least among all its cyclic shifts, one has
\[
(\al_1,\ldots,\al_{1+t})\lhd(\be_1,\ldots,\be_{1+t}).
\]
This implies that $\psi(S_i)\lhd\psi(S_j)$, which is a contradiction to the assumption $S_i\rhd S_j$.
Moreover, it is not hard to see that $A_{i,i}\neq 0$ as $S_i\subseteq f(S_i)\cup(f(S_i)+1)$, therefore the diagonal entries are nonzero.
This proves the claim, hence the lemma.
\end{proof}
Define {\em the union of digraphs} $\vec{D}\biguplus\vec{E}$ to be the digraph with vertices $V(\vec{D})\cup V(\vec{E})$ and arcs $A(\vec{D})\cup A(\vec{E})$. The next result follows easily from the definition.
\begin{prop}
If $\vec{D}$ and $\vec{E}$ are two DAGs on disjoint subsets of $\mathbb{P}$, then
\begin{equation}\label{eq:joint union of DAGs}
\Delta^{\cyc}_{[\vec{D}\biguplus\vec{E}]}=\Delta^{\cyc}_{[\vec{D}]}\cdot\Delta^{\cyc}_{[\vec{E}]}.
\end{equation}
\end{prop}
The proposition above yields a combinatorial proof that $\Lambda$ is an algebra.
\begin{prop}
$\Lambda$ is a graded subring of $\cQSym$.
\end{prop}
\begin{proof}
As a subspace of $\cQSym$, $\Lambda$ naturally inherits the addition and multiplication operations from $\cQSym$.
To show that $\Lambda$ is closed under multiplication, let $K^{\cyc}_{n,U}\in\Lambda_m$ and $K^{\cyc}_{n,T}\in\Lambda_n$, where~$U$ and~$T$ are cyclic peak sets in $[m]$ and $[n]$ respectively. That is to say, there exist~$\pi\in\mathcal{S}_m$ and~$w\in\mathcal{S}_n$ such that $\cPk\pi=U,\;\cPk w=T$. For the purpose of constructing two corresponding disjoint DAGs, we standardize $w=w_1w_2\ldots w_n\in\mathcal{S}_n$ to $\{m+1,m+2,\ldots,m+n\}$, that is, construct $w'=w'_1w_2'\ldots w_n'$ where $w_i'=w_i+m$ for $i\in[n]$. As a consequence of equation~\eqref{eq:joint union of DAGs}, we have
\begin{equation}
K^{\cyc}_{n,U}\cdot K^{\cyc}_{n,T}=\Delta^{\cyc}_{[\pi]}\cdot\Delta^{\cyc}_{[w']}=\Delta^{\cyc}_{[\pi\biguplus w']}=\sum_{\sigma\in \mathcal{L}^{\tor}([\pi\biguplus w'])}K^{\cyc}_{n,\cPk \sigma}.
\end{equation}
This completes the proof.
\end{proof}
In terms of another basis of $\cQSym$, the fundamental cyclic quasi-symmetric functions, $K^{\cyc}_{n,S}$ has the following expansion.
\begin{prop}\label{expand K in F}
For any cyclic peak set $S$ in $[n]$, we have
\[
2^{-|S|}K^{\cyc}_{n,S}=\sum_{\substack{E\subseteq[n]:\\[2pt]S\sbe E\triangle (E+1)}}F^{cyc}_{n,E},
\]
where $\triangle$ denotes symmetric difference.
\end{prop}
\begin{proof}
Since $F^{cyc}_{n,E}=\sum_{F\supseteq E} M^{cyc}_{n,F}$, the coefficient of $M^{cyc}_{n,F}$ on the right-hand side of the above expansion is $\left|\{E\subseteq F: S\sbe E\triangle (E+1)\}\right|$.
To count this set, we need the following observations. For each $k\in S\sbe E\triangle (E+1)$, exactly one of $k-1$ and $k$ is in $E$. It follows from $E\sbe F$ that at least one of $k-1$ and $k$ is in $F$.
So one has the following two cases:
\begin{enumerate}
\item[(1)] If both $k,k-1\in F$, then $E$ must contain exactly one of $k$ or $k-1$.
\item[(2)] If only one of $k,k-1\in F$, then $E$ must contain this element.
\end{enumerate}
Note that the restrictions above only involve two adjacent numbers.
Also notice that if $k\in F$ but neither $k$ nor $k+1$ is in $S$, then $k$ is free to be in $E$ or not. Denote
\begin{align*}
S_1&=\{k\in S\mid \text{both $k,k-1$ are in $F$}\},\\
S_2&=\{k\in S\mid k\in E,k-1\notin F\},\\
S_3&=\{k\in S\mid k\notin E,k-1\in F\}.
\end{align*}
Then we have a set partition
$S=S_1\cup S_2\cup S_3$. Therefore if we denote $s_i=\#S_i$ for $i\in\{1,2,3\}$, we have $|S|=s_1+s_2+s_3$.
Denote now
\[
T=\{k\in F\mid \text{none of $k,k+1$ is in $S$}\}.
\]
By the definition of a peak set, numbers in $S$ are not adjacent. Hence we have the following partition of $F$ into disjoint sets:
\[
F=S_1\cup(S_1-1)\cup S_2\cup (S_3-1)\cup T.
\]
It follows that $|F|=2s_1+s_2+s_3+t$ with $t=|T|$. Hence, the number of choices for~$E$ is
\[
2^{s_1+t}=2^{s_1+|F|-2s_1-s_2-s_3}=2^{|F|-(s_1+s_2+s_3)}=2^{|F|-|S|}.
\]
So we have
\[
\sum\limits_{\substack{E\subseteq[n]:\\[2pt]S\sbe E\triangle(E+1)}}F^{cyc}_{n,E}=\sum\limits_{\substack{F\subseteq[n]:\\[2pt]S\sbe F\cup(F+1)}}2^{|F|-|S|}M^{cyc}_{n,F}.
\]
By equation~\eqref{eq:depend on cPk}, this quantity is $2^{-|S|}K^{cyc}_{n,S}$.
\end{proof}
\subsection{Order polynomials \texorpdfstring{$\Omega^{\cyc}([\vec{D}],m)$}{}}\label{sec:op}
Given a DAG $\vec{D}$, we can define the {\em order polynomial of enriched $\vec{D}$-partitions}, $\Omega(\vec{D},m)$, by
\[
\Omega(\vec{D},m)=\Delta_{\vec{D}}(1^m),
\]
where $\Delta_{\vec{D}}(1^m)$ means that we set $x_1=\cdots =x_m=1$, and $x_k=0$ for $k>m$. In fact, $\Omega(\vec{D},m)$ counts the number of enriched $\vec{D}$-partitions with absolute value at most $m$.
Stembridge computed the corresponding generating function as follows:
\begin{thm}[\protect{\cite[Theorem 4.1]{S:epp}}]\label{t-opstem}
For a given $w\in\mathcal{S}_n$, one has
\begin{equation}\label{eq:WEEP}
\sum_m\Omega(w,m)t^m=\frac{1}{2}\left(\frac{1+t}{1-t}\right)^{n+1}\left(\frac{4t}{(1+t)^2}\right)^{1+\pk w}.
\end{equation}
\end{thm}
It is not hard to see that $\Omega(\vec{D},t)$ is indeed a polynomial in $t$.
If $\vec{D}$ has vertex set~$V$ and $|V|=n$, then
\[
\Omega(\vec{D},m)=\sum_{k=1}^{n}c_k\binom{m}{k},
\]
where $c_k$ denotes the number of $f\in \mathcal{E}(\vec{D})$ such that $\{|f(x)|\colon x\in V\}=[k]$. For any fixed $k$, $\binom{m}{k}$ is a polynomial in $m$ of degree $k$. Since $c_k$ and $n$ are constants, it follows that the summation is also a polynomial in $m$. This verifies that $\Omega([\vec{D}],t)$ is a polynomial.
Similarly, we define the {\em order polynomial of enriched toric $[\vec{D}]$-partitions}, $\Omega^{\cyc}([\vec{D}],m)$, by
\[
\Omega^{\cyc}([\vec{D}],m)=\Delta^{\cyc}_{[\vec{D}]}(1^m).
\]
The following result is the toric analogue of formula \eqref{eq:WEEP}.
\begin{prop}\label{op}
Given $w\in \mathcal{S}_n$, then
\begin{equation}\label{e-Ocyc}
\sum_m\Omega^{\cyc}([w],m)t^m=\left(\frac{4t}{(1+t)^2}\right)^{\cpk w}\left(\frac{1+t}{1-t}\right)^{n-1}\left(\cpk w+\frac{2nt}{(1-t)^2}\right).
\end{equation}
This right side of the equation does not depend on the choice of representative $w$, as they all have the same cyclic peak number.
\end{prop}
\begin{proof}
By the definition of order polynomial,
\begin{align*}
\sum_m\Omega^{\cyc}([w],m)t^m &=\sum_m\Delta^{\cyc}_{[w]}(1^m)t^m\\
&=\sum_m\sum_{v\in[w]}\Delta_{v}(1^m)t^m\\
&=\sum_{v\in[w]}\sum_m\Delta_{v}(1^m)t^m\\
&=\sum_{v\in[w]}\sum_m\Omega(v,m)t^m\\
&=\sum_{v\in[w]}\frac{1}{2}\left(\frac{1+t}{1-t}\right)^{n+1}\left(\frac{4t}{(1+t)^2}\right)^{1+\pk v},
\end{align*}
where the last equality is obtained by applying \eqref{eq:WEEP}.
Observe that each representative of $[w]$ will either start with a cyclic peak, end with a cyclic peak, or none of the two ends are cyclic peaks, which will yield peak number $\cpk w-1$, $\cpk w-1$ or $\cpk w$ respectively. The number of those representatives with a cyclic peak at one end is $2\cpk w$. It follows that
\begin{align*}
\sum_m\Omega^{\cyc}([w],m)t^m
&=\frac{2\cpk w}{2}\left(\frac{1+t}{1-t}\right)^{n+1}\left(\frac{4t}{(1+t)^2}\right)^{\cpk w}\\
&\qquad\qquad\quad+\frac{n-2\cpk w}{2}\left(\frac{1+t}{1-t}\right)^{n+1}\left(\frac{4t}{(1+t)^2}\right)^{1+\cpk w}\\
&=\left(\frac{4t}{(1+t)^2}\right)^{\cpk w}\left(\frac{1+t}{1-t}\right)^{n-1}\left(\cpk w +\frac{2nt}{(1-t)^2}\right).
\end{align*}
This completes the proof.
\end{proof}
Notice that by taking the coefficient of $t^m$ on both sides of equation \eqref{e-Ocyc}, one can get an expression for the order polynomial of enriched $\vec{D}$-partitions $\Omega^{\cyc}([w],m)$ in an algebraic manner. It would be desirable to derive $\Omega^{\cyc}([w],m)$ combinatorially. For this purpose, we first give a combinatorial proof of a formula for $\Omega(w,m)$. We define the $(w,m)$-marking for a permutation $w$ and a positive integer $m$, and show that each $(w,m)$-marking corresponds to exactly $2^{2\pk +1}$ enriched $w$-partitions with absolute value at most $m$.
Suppose $w\in\mathcal{S}_n$, $m\in\mathbb{P}$. One can naturally extend $w=w_1\ldots w_n$ to $w'=w_0 w_1\ldots w_n w_{n+1}$ where $w_0=w_{n+1}=\infty$. Let $R_1$
be the longest decreasing initial factor of $w'$.
Now let $v$ denote $w'$ with $R_1$ deleted, and let $R_2$ be the longest increasing initial factor of $v$. Continue in this way, alternating between decreasing and increasing factors to get a factorization of $w'$. We call the factors {\em runs} and the corresponding indices {\em run indices}. We denote by $I_j$ the set of run indices corresponding to a factor set $R_j$. Note that any extension $w'$ will start with a decreasing run and end with an increasing run, which implies that the number of runs is always even.
Take $$w=\begin{array}{cccccc}
1&2&3&4&5&6 \\
\textbf{1}&4&{\bf3}&{\bf2}&5&6
\end{array}$$ as an example. The corresponding natural extension
$$w'=\begin{array}{cccccccc}
0&1&2&3&4&5&6&7 \\
\textbf{$\infty$}&\textbf{1}&4&{\bf3}&{\bf2}&5&6&\text{$\infty$}
\end{array}$$
has four runs
\[
R_1=\infty1,\;R_2=4,\; R_3=32,\;R_4=56\infty,
\]
where the decreasing runs are in bold, and the corresponding set of run indices are
\[
I_1=\{0,1\},\,\;I_2=\{2\},\; I_3=\{3,4\},\;I_4=\{5,6,7\}.
\]
Suppose that the permutation $w'$ has $r$ runs. We have the following observations:
\begin{enumerate}
\item The parity of $i$ indicates the type of the run $R_i$. If $i$ is even, then $R_i$ is increasing. If $i$ is odd, then $R_i$ is decreasing.
\item The total number of runs $r$ is closely related to the peak number $\pk w$:
$$r=2\pk w+2.$$
\end{enumerate}
We now decorate permutations with bars and marks. Bars can be inserted between adjacent columns in the two-line notation (including the space before the first column and the space after the last), whereas a column of $w$ with index $i\in[n]$ can be marked if and only if $i,i+1\in I_j$ for some $j$; in other words, if $i$ and $i+1$ are in the same run index set. There can be multiple bars between two adjacent columns and we count them with multiplicity, while each column can be marked at most once. We will denote by $\cM_w$
the set of indices of the columns that can be marked,
\[
\cM_w:=\{i\in[n]\mid \text{ $i,i+1\in I_j$ for some $j$}\}.
\]
We note that for a given $w$, the cardinality of the complement of the set $\cM_w$ in $[n]$ is $2\pk w+1$. Equivalently, one has $|\cM_w|=n-2\pk w-1$.
\begin{defi}[\text{$(w,m)$-marking}]
Suppose that $w$ is a linear permutation and $m$ is a positive integer. A {\em $(w,m)$-marking} is a marking of $w$ using $b$ bars and $d$ marked columns, satisfying that $b+d=m-1-\pk w$.
\end{defi}
\begin{exam}\label{ex:markings}
If we set $w=143256$ as before, and take $m=5$, then a $(w,5)$-marking has $b$ bars and $d$ marked columns, such that $b+d=3$. Two $(w,5)$-markings are provided as follows. Both have two bars and one marked column, where the marked column is in blue.
$$\begin{array}{cc||cccc}
1&2&3&4&\textcolor{blue}{\bf5}&6 \\
1&4&3&2&\textcolor{blue}{\bf5}&6
\end{array}\qquad\qquad
\begin{array}{cc|cccc|}
1&2&\textcolor{blue}{\bf3}&4&5&6 \\
1&4&\textcolor{blue}{\bf3}&2&5&6
\end{array}
$$
\end{exam}
\begin{prop}\label{p-orderpoly}
For a given $w\in\mathcal{S}_n$, one has
\begin{equation}\label{eq:OPEDP}
\Omega(w,m)=2^{2\pk w+1}\sum_{k=0}^{m-1-\pk w}\mch{n+1}{k} \binom{n-2\pk w-1}{m-1-\pk w-k},
\end{equation}
where $\mch{n+1}{k}$ denotes the number of multisets on $[n+1]$ with cardinality $k$.
\end{prop}
\begin{proof}
It is clear by definition that the number of possible choices for $(w,m)$-markings is
\[
\sum_{b+d=m-1-\pk w} \hspace{-3pt} \mch{n+1}{b} \binom{n-2\pk w-1}{d} = \hspace{-10pt} \sum_{k=0}^{m-1-\pk w} \hspace{-3pt} \mch{n+1}{k} \binom{n-2\pk w-1}{m-1-\pk w-k}.
\]
Therefore, it suffices to construct a $2^{2\pk w+1}$-to-one map from the set of enriched $w$-partitions with absolute value at most $m$ to the set of all $(w,m)$-markings.
Given an enriched $w$-partition $f$ with absolute value at most $m$, we can inductively associate to it a unique $(w,m)$-marking as follows:
We first determine, for each $k\in \cM_w$, whether column $k$ gets marked. Suppose $k\in I_i$ for some $i\in[r]$. We mark column $k$ if and only if $\delta_k+\gamma_k=1$ where
$$
\delta_k:=\delta\,(\text{$i$ is even and $f(w_{k})<0$}),\qquad \gamma_k:=\delta\,(\text{$i$ is odd and $f(w_{k})>0$}).
$$
Here the {\em Kronecker function} on a statement $R$ is defined by
\[
\delta(R)=\begin{cases}
1 & \text{if $R$ is true},\\
0 & \text{if $R$ is false}.
\end{cases}.
\]
As for the placement of bars, we start by putting $|f(w_1)|-1$ bars before the first column. Inductively, suppose that $k\in I_i$ for some $k\in[2,n]$, $i\in[r]$ and we have already constructed the markings and bars on and before the $(k-1)$st column. Then the number of marks and bars strictly before the $k$th column is constructed to be
\begin{equation}
\label{mb}
|f(w_{k})|-\lceil i/2\rceil -\delta_k.
\end{equation}
Finally we add bars after the last column so that the total number of marks and bars is $m-\pk w-1$. In this manner, we can inductively define a unique $(w,m)$-marking for $f$.
We must verify that the constructed marking is indeed a $(w,m)$-marking. Firstly we will verify that \eqref{mb} is a weakly increasing function of $k$, and strictly increasing from the $k$th to the $(k+1)$st term if column $k$ is marked.
In other words, if $k\in I_i$ and $k+1\in I_j$, it suffices to show that
\[
|f(w_{k})|-\lceil i/2\rceil -\delta_{k}\leq |f(w_{k+1})|-\lceil j/2\rceil -\delta_{k+1},
\]
for all $k$, and that
\[
|f(w_{k})|-\lceil i/2\rceil -\delta_{k}< |f(w_{k+1})|-\lceil j/2\rceil -\delta_{k+1},
\]
if column $k$ is marked. Notice that
\[(\delta_{k}+\gamma_{k})\cdot\delta(k\in \cM_w)=1\]
if column $k$ is marked and $0$ otherwise. Hence it suffices to show that
\begin{equation}\label{inequ}
|f(w_{k})|-\lceil i/2\rceil -\delta_{k}+(\delta_{k}+\gamma_{k})\cdot\delta(k\in \cM_w)\leq |f(w_{k+1})|-\lceil j/2\rceil -\delta_{k+1}.
\end{equation}
By the definition of enriched $P$-partitions, we have
\begin{equation}\label{reduced inequ}
|f(w_{k})|\leq |f(w_{k+1})|.
\end{equation}
Let us consider the following cases:
\begin{enumerate}
\item[(a)] If $j=i$, it follows that $k\in \cM_w$. Hence inequality \eqref{inequ} simplifies to
\[
|f(w_{k})|+\gamma_{k}\leq |f(w_{k+1})|-\delta_{k+1}.
\]
If $i$ is even, then $\gamma_{k}=0$ and $w_{k}w_{k+1}$, $\lceil i/2\rceil+1=\lceil (i+1)/2\rceil$ and $j$ is odd, hence $\delta_{k+1}=0$. Therefore one only needs to prove
\[
|f(w_{k})|-\delta_{k}\leq |f(w_{k+1})| -1.
\]
The inequality clearly holds when $\delta_{k}=1$, so it suffices to consider the case when $\delta_{k}=0$. In this case, $f(w_{k})>0$, hence by the definition of enriched $P$-partitions, or equivalently $|f(w_{k+1})|\geq |f(w_{k})|+1$, proves~\eqref{inequ}. The case when $i$ is odd is similar and left to the reader.
\end{enumerate}
Secondly, one also needs to check that it is possible to add bars (possibly $0$) after the last column so that the total number of marks and bars is $m-\pk w-1$. In other words, the number of bars we add after the $n$th column is nonnegative. Notice that $\lceil \frac{i}{2}\rceil-1$ counts the number of peaks before the $k$-th column. Since $n\in I_r$, this implies that $\lceil \frac{r}{2}\rceil=\pk w+1$. By~\eqref{mb}
the total number of bars and marked columns before the~$n$th column is $|f(w_n)|-\pk w-1-\delta_n$.
Together with the fact that the~$n$th column is marked if and only if $\delta_n+\gamma_n=1$ and $n\in \cM_w$, the total number of bars that should be added after the~$n$th column is
\begin{align*}
& m-\pk w-1-(|f(w_n)|-\pk w-1-\delta_n)-(\delta_n+\gamma_n)\cdot\delta(n\in \cM_w)\\
=&\, m-|f(w_n)|+\delta_n-(\delta_n+\gamma_n)\cdot\delta(n\in \cM_w).
\end{align*}
Hence the nonnegativity condition becomes
\[
m-|f(w_n)|+\delta_n-(\delta_n+\gamma_n)\cdot\delta(n\in \cM_w)\geq 0,
\]
or equivalently,
\begin{equation}\label{inequ2}
m-|f(w_n)|\geq(\delta_n+\gamma_n)\cdot\delta(n\in \cM_w)- \delta_n.
\end{equation}
By assumption $f$ has absolute value at most $m$, hence $m-|f(w_n)|\geq 0$. Therefore, one only needs to check that the inequality holds when $(\delta_n+\gamma_n)\cdot\delta(n\in \cM_w)- \delta_n=1$, namely $\delta_n+\gamma_n=1$, $\delta(n\in \cM_w)=1$ and $\delta_n=0$, or equivalently, $n\in I_i$ where $i$ is odd, $f(w_n)>0$ and $n\in \cM_w$. This is a contradiction since $n+1$ must be in a run where the index is even by definition, which implies that $n$ and $n+1$ cannot be in the same run index set, hence $n\notin \cM_w$. This completes the proof of inequality~\eqref{inequ2}.
It therefore follows that the marking we constructed is indeed a $(w,m)$-marking.
Now we need to show that for a given $(w,m)$-marking, there are $2^{2\pk w+1}$ different associated functions. From the above construction we notice that for each $k\in \cM_w$, $f(w_k)$ is uniquely determined. More precisely, whether column $k$ gets marked determines $\delta_k$ and $\gamma_k$ as $k$ determines the parity of $i$, hence the sign of $f(w_k)$ is determined by the definitions of $\delta_k$ and $\gamma_k$.
Suppose $k\in I_i$. The number of marks and bars strictly before the $k$th column determines the value $ |f(w_{k})|-\lceil i/2\rceil -\delta_k$, therefore it determines~$f(w_{k})$ as well. The only ambiguity is about $f(w_k)$ for $k\notin \cM_w$. As the number of marks and bars strictly before the $k$th column fixes the value $L= |f(w_{k})|-\lceil i/2\rceil -\delta_k$, there are two possible choices of the value $f(w_k)$ for each $k\notin \cM_w$: if $i$ is even, then either $f(w_k)=-(L+\lceil i/2\rceil+1)$ or $f(w_k)=L+\lceil i/2\rceil$; if $i$ is odd, then either $f(w_k)=L+\lceil i/2\rceil$ or $f(w_k)=-(L+\lceil i/2\rceil)$.
It follows that there are $2^{2\pk w+1}$ different functions corresponding to a given $(w,m)$-marking.
\end{proof}
\begin{exam}
Consider again the permutation $w=143256$, and an enriched $w$-partition $f$ defined as follows:
\[
f(1)=1,\;f(4)=-2,\;f(3)=-4,\;f(2)=-4,\;f(5)=-5,\;f(6)=5.
\]
The corresponding marking is the first one in Example~\ref{ex:markings}.
\end{exam}
We now give a combinatorial derivation of the order polynomial $\Omega^{\cyc}([w],m)$ by using Proposition~\ref{p-orderpoly}, which was also proved combinatorially.
\begin{coro}
For a given $[w]\in[\mathcal{S}_n]$, one has
\begin{align*}
\Omega^{\cyc}([w],m)&=(n-2\cpk w)\cdot2^{2\cpk w+1}\sum_{k=0}^{m-1-\cpk w} \mch{n+1}{k} \binom{n-2\cpk w-1}{m-1-\cpk w-k}\\
&\qquad+\cpk w\cdot2^{2\cpk w}\sum_{k=0}^{m-\cpk w} \mch{n+1}{k} \binom{n-2\cpk w+1}{m-\cpk w-k}.
\end{align*}
This right side of the equation does not depend on the choice of representative $w$, as they all have the same cyclic peak number.
\end{coro}
\begin{proof}
Notice that any representative $w'$ of $[w]$ satisfies $\pk w'=\cpk [w]-1$ if $w'$ starts or ends with a cyclic peak, and $\pk w'=\cpk[w]$ otherwise. Among the $n$ representatives of $[w]$, there are $2\cpk [w]$ with a cyclic peak at one end. Therefore, applying equation~\eqref{e-Dsum} we have
\[
\Omega^{\cyc}([w],m)=\Delta^{\cyc}_{[w]}(1^m)=\sum_{v\in[w]}\Delta_v(1^m)=\sum_{v\in[w]}\Omega(v,m),
\]
and by the previous observation and Proposition~\ref{p-orderpoly}, one has
{\small \begin{align*}
\sum_{v\in[w]}\Omega(v,m)&=\sum_{v\in[w]}2^{2\pk v+1}\sum_{k=0}^{m-1-\pk v}\mch{n+1}{k} \binom{n-2\pk v-1}{m-1-\pk v-k}\\
&=(n-2\cpk[w])\cdot 2^{2\cpk [w]+1}\sum_{k=0}^{m-1-\cpk [w]}\mch{n+1}{k} \binom{n-2\cpk [w]-1}{m-1-\cpk [w]-k}\\
&\; +2\cpk[w]\cdot2^{2(\cpk [w]-1)+1} \hspace{-5pt} \sum_{k=0}^{m-1-(\cpk [w]-1)} \hspace{-5pt} \mch{n+1}{k} \binom{n-2(\cpk [w]-1)-1}{m-1-(\cpk [w]-1)-k}\\
&=(n-2\cpk w)\cdot2^{2\cpk w+1}\sum_{k=0}^{m-1-\cpk w}\mch{n+1}{k} \binom{n-2\cpk w-1}{m-1-\cpk w-k}\\
&\;+\cpk w\cdot2^{2\cpk w}\sum_{k=0}^{m-\cpk w}\mch{n+1}{k} \binom{n-2\cpk w+1}{m-\cpk w-k}
\end{align*} }
The conclusion follows immediately.
\end{proof}
We note that the generating function of order polynomials in Proposition~\ref{op} can also be deduced from the corollary above. Explicitly,
\begin{align*}
\sum_m\Omega^{\cyc}([w],m)t^m &=(n-2\cpk w)\cdot 2^{2\cpk w+1}\,\frac{(1+t)^{n-2\cpk w-1}}{(1-t)^{n+1}}\,t^{\cpk w+1}\\
&\quad +\cpk w\cdot 2^{2\cpk w}\,\frac{(1+t)^{n-2\cpk w+1}}{(1-t)^{n+1}}\,t^{\cpk w}\\
&=\left(\frac{4t}{(1+t)^2}\right)^{\cpk w}\left(\frac{1+t}{1-t}\right)^{n+1}\left((n-2\cpk w)\cdot\frac{2t}{(1+t)^2}+\cpk w\right)\\
&=\left(\frac{4t}{(1+t)^2}\right)^{\cpk w}\left(\frac{1+t}{1-t}\right)^{n-1}\left(\cpk w+\frac{2nt}{(1-t)^2}\right).
\end{align*}
\subsection{The shuffle algebra of the peak number}\label{sec:sa}
In \cite{MR3810249}, Gessel and Zhuang discussed shuffle-compatible permutation statistics in terms of shuffle algebras. In Theorem 4.8, they proved that the peak number $\pk$ is shuffle compatible and also characterized its shuffle algebra $\cA_{\pk}$. It turns out that Proposition~\ref{p-orderpoly} gives another characterization of $\cA_{\pk}$. Before we state and prove the theorem, we review some definitions and results from~\cite{MR3810249}.
Suppose $\pi$ and $\sigma$ are two disjoint permutations of lengths $m$ and $n$ respectively. Then the {\em shuffle set} of $\pi$ and $\sigma$ is
\[
\pi\shuffle\sigma=\{\tau: \text{$|\tau|=m+n$, $\pi$ and $\sigma$ are subsequences of $\tau$} \}.
\]
A statistic $\st$ is {\em \textup{(}linear\textup{)} shuffle compatible} if for disjoint permutations $\pi$ and $\sigma$, the multiset $\{\{\,\st(\tau):\tau\in\pi\shuffle\sigma\, \}\}$ only depends on $\st(\pi)$, $\st(\sigma)$, $|\pi|$ and $|\sigma|$.
Every linear permutation statistic $\st$ induces an equivalence relation on permutations. More precisely, two permutations $\pi$ and $\sigma$ are $\st$-equivalent if $\st(\pi)=\st(\sigma)$ and $|\pi|=|\sigma|$, and the {\em $\st$-equivalence class of $\pi$} is denoted by $[\pi]_{\st}$. Moreover, if $\st$ is shuffle compatible, one can associate to $\st$ a $\mathbb{Q}$-algebra as follows: first we associate to $\st$ a $\mathbb{Q}$-vector space by taking the $\st$-equivalence classes as a basis, then define multiplication by
\[
[\pi]_{\st}[\sigma]_{\st}=\sum_{\tau\in \pi\shuffle\sigma}[\tau]_{\st}.
\]
Here the shuffle-compatibility of $\st$ guarantees that the above multiplication is well-defined. In this case, we call the resulting algebra the {\em shuffle algebra of $\st$} and denote it by $\cA_{\st}$.
We recall the characterization of the peak shuffle algebra $\cA_{\pk}$ from~\cite{MR3810249}:
\begin{thm}[\protect{\cite[Theorem 4.8 (b)]{MR3810249}}]
The linear map on $\cA_{\pk}$ defined by
\[
[\pi]_{\pk}\mapsto \begin{cases}\displaystyle\frac{2^{2\pk \pi+1}t^{\pk\pi+1}(1+t)^{|\pi|-2\pk\pi-1} }{ (1-t)^{|\pi|+1}}x^{|\pi|},& \text{if $|\pi|\geq 1$};\\[6pt]\displaystyle \frac{1}{1-t}, &\text{if $|\pi|=0$,}\end{cases}
\]
is a $\mathbb{Q}$-algebra isomorphism from $\cA_{\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\geq 1,\,0\leq j\leq\lfloor\frac{n-1}{2}\rfloor}
\]
a subalgebra of $\mathbb{Q}[[t\ast]][x]$, where multiplication of formal power series in $t$ is by Hadamard product.
\end{thm}
Now we give another characterization of $\cA_{\pk}$ which follows from our Proposition~\ref{p-orderpoly}.
\begin{thm}
The linear map on $\cA_{\pk}$ defined by
\[
[\pi]_{\pk}\mapsto 2^{2\pk \pi+1}\sum_{k=0}^{m-1-\pk \pi} \mch{|\pi|+1}{k} \binom{|\pi|-2\pk \pi-1}{m-1-\pk \pi-k}x^{|\pi|}
\]
is a $\mathbb{Q}$-algebra isomorphism from $\cA_{\pk}$ to the span of
\[
\left\{1\right\}\bigcup\left\{2^{2j+1}\sum_{k=0}^{m-1-j} \mch{n+1}{k} \binom{n-2j-1}{m-1-j-k}x^{n} \right\}_{n\geq 1,\,0\leq j\leq\lfloor\frac{n-1}{2}\rfloor}
\]
a subalgebra of $\mathbb{Q}[x]^{\mathbb{N}}$, the algebra of functions $\mathbb{N}\to\mathbb{Q}[x]$ in the non-negative integer value $m$, with pointwise addition and multiplication.
\end{thm}
\begin{proof}
Define a map $\kappa_m:\QSym\to \mathbb{Q}[x]$ by
\[
\kappa_m(F_{n,L})=K_{n,\Pk(L)}(1^m)x^n,
\]
linearly extended to all of $\QSym$.
The following equation, \cite[Equation (3.1)]{S:epp},
\[
K_{n,\Pk\pi}\cdot K_{n,\Pk\sigma}=\sum_{\tau\in\pi\shuffle\sigma}K_{n,\Pk\tau},
\]
implies that $\kappa_m$ is a $\mathbb{Q}$-algebra homomorphism.
The map that takes $F_{n,L}$ to the function $\theta_{n,L}: m\mapsto \kappa_m(F_{n,L})$ is therefore a homomorphism from $\QSym$ to $\mathbb{Q}[x]^{\mathbb{N}}$. It follows from Proposition~\ref{p-orderpoly} that
\[
\kappa_m(F_{n,L})=2^{2\pk (L)+1}\sum_{k=0}^{m-1-\pk (L)} \mch{n+1}{k} \binom{n-2\pk (L)-1}{m-1-\pk (L)-k}x^n.
\]
Moreover, from Theorem~\ref{t-opstem} one has
\begin{align*}
&\sum_{m=0}^{\infty}2^{2\pk (L)+1}\sum_{k=0}^{m-1-\pk (L)} \mch{n+1}{k} \binom{n-2\pk (L)-1}{m-1-\pk (L)-k}t^m\\
= &\,\frac{1}{2}\left(\frac{1+t}{1-t}\right)^{n+1}\left(\frac{4t}{(1+t)^2}\right)^{1+\pk(L)}
\end{align*}
which is the generating function of $\theta_{n,L}$ and only depends on $n$ and $\pk L$. For a fixed $n$, these functions are clearly linearly independent for sets $L$ with distinct peak numbers. The result follows immediately from~\cite[Theorem 4.3]{MR3810249}.
\end{proof}
\longthanks{I wish to thank Bruce Sagan for many helpful corrections as well as Yan Zhuang for suggesting the characterization of the shuffle algebra $\cA_{\pk}$ .}
\bibliographystyle{mersenne-plain}
\bibliography{ALCO_Liang_796}
\end{document}**