CYCLIC SHUFFLE-COMPATIBILITY, CYCLIC PERMUTATION STATISTICS, CYCLIC
QUASISYMMETRIC FUNCTIONS AND TORIC PARTITIONS

By

Jinting Liang

A DISSERTATION

Submitted to
Michigan State University
in partial fulfillment of the requirements
for the degree of

Mathematics—Doctor of Philosophy

2024

ABSTRACT

A permutation statistic st is said to be shuffle-compatible if the distribution of st over the set of

shuffles of two disjoint permutations 𝜋 and 𝜎 depends only on st 𝜋, st 𝜎, and the lengths of 𝜋 and

𝜎. Shuffle-compatibility is implicit in Stanley’s early work on 𝑃-partitions, and was first explicitly

studied by Gessel and Zhuang, who developed an algebraic framework for shuffle-compatibility

centered around their notion of the shuffle algebra of a shuffle-compatible statistic. One of the places

where shuffles are useful is in describing the product in the algebra of quasisymmetric functions.

Recently Adin, Gessel, Reiner, and Roichman defined an algebra of cyclic quasisymmetric functions

where a cyclic version of shuffling comes into play.

This dissertation focuses on the study of cyclic shuffle-compatibility. We began by showing

a result called the “lifting lemma,” which allows one (under certain nice conditions) to prove

that a cyclic statistic is cyclic shuffle-compatible from the shuffle-compatibility of a related linear

statistic. This lifting lemma can be used to prove the cyclic shuffle-compatibility of all four

statistics cDes, cdes, cPk, and cpk. We then developed an algebraic framework for cyclic shuffle-

compatibility centered around the notion of cyclic shuffle algebra of a cyclic shuffle-compatible

statistic. Using this theory, we provide explicit descriptions for the cyclic shuffle algebras of

various cyclic permutation statistics, which in turn gives algebraic proofs for their cyclic shuffle-

compatibility.

In particular, we developed the theory of enriched toric [ (cid:174)𝐷]-partitions, which

provides a characterization of the cyclic shuffle algebra of cPk.

ACKNOWLEDGEMENTS

First and foremost, I would like to thank my advisor, Dr. Bruce Sagan, for all of his guidance and

support throughout my Ph.D studies. This thesis would not have been possible without his endless

patience and unwavering support. His patience and mentorship have been instrumental in shaping

my academic journey, introducing me to the realm of combinatorics and serving as an exemplary

role model in the field of mathematics. I am profoundly grateful for his efficiency and mathematical

rigor as a collaborator.

I also wish to express my sincere appreciation to the members of my dissertation committee:

Dr. Michael Shapiro, Dr. Linhui Shen, and Dr. Jeanne Wald, for their exceptional guidance and

dedication in mentoring me over the years.

I would love to thank the following friends, without whom I would not have made it through

my PhD degree: Rachel Domagalski for sharing her precious experience and always supporting

me from the audience when I gave talks; Quinn Minnich for the in-depth discussions during those

challenging graduate courses; Jamie Kimble for introducing me to the world of crochet and being

the best study buddy; Samara Chamoun for reminding me the beauty of life, sharing our struggles

during this journey and for being honest and warmhearted to this whole world. To Shitan, your

steadfast support has been a guiding light in my darkest moments and I was fortunate to have your

support no matter what. You are always the pillar of my strength.

It has been an amazing experience to work in this department where everyone, especially

women in math, cares deeply for each other and is dedicated to create a sense of belonging for this

community. Heartfelt appreciation goes to Tsveta Sendova and Andy Krause for understanding and

providing us with the greatest flexibility of teaching. I am thankful for my years spent with this

family, for everything we shared, every chance we had to grow.

Lastly, to my parents, I am and will always be eternally grateful for your unconditional love,

support, and the freedom you’ve granted me in pursuing my career path.

Thank you to everyone who has played a part in my journey. Your contributions have been

invaluable. I will take the best of them with me and lead by their example wherever I go.

iii

TABLE OF CONTENTS

CHAPTER 1

INTRODUCTION . . . . . . . . . . . . . . . . . . . . . . . . . . . .

.
1.1 Linear Permutations, Statistics, and Shuffles . . . . . . . . . . . . . . . . . . .
.
1.2 Cyclic Permutations, Cyclic Statistics, and Cyclic Shuffles
.
1.3 Outline

. . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . .

.

.

.

.

.

.

.

.

1
1
3
6

CHAPTER 2

PRELIMINARIES . . . . . . . . . . . . . . . . . . . . . . . . . . . .

8
2.1 Sets and Compositions
8
2.2 Quasisymmetric Functions QSym . . . . . . . . . . . . . . . . . . . . . . . . 10
2.3 Cyclic Quasisymmetric Functions cQSym . . . . . . . . . . . . . . . . . . . . 12

.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

CHAPTER 3

3.1 The Lifting Lemma .
.
3.2 Applications . .

CYCLIC SHUFFLE-COMPATIBILITY: COMBINATORIALLY . . . . 16
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21

. .

CHAPTER 4

CYCLIC SHUFFLE-COMPATIBILITY: ALGEBRAICALLY . . . . .

. 25
4.1 Cyclic Shuffle Algebras . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
. . . . . . . . . . . . . . 34
4.2 Shuffle-compatibility and Quasisymmetric Functions
4.3 Characterizations of Cyclic Shuffle Algebras . . . . . . . . . . . . . . . . . . . 38
4.4 Cyclic Permutation Statistics Induced by Linear Permutation Statistics . . . . . 47

CHAPTER 5

ENRICHED TORIC [ (cid:174)𝐷]-PARTITIONS . . . . . . . . . . . . . . . . . . 61
5.1 Enriched Partitions on Posets . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
5.2 Enriched Partitions for Toric DAGs . . . . . . . . . . . . . . . . . . . . . . . . 71
5.3 Shuffle-compatibility Revisited . . . . . . . . . . . . . . . . . . . . . . . . . . 87

BIBLIOGRAPHY .

. .

.

.

.

.

.

.

.

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90

iv

CHAPTER 1

INTRODUCTION

Denote by N and P the set of nonnegative integers and positive integers respectively. For 𝑚, 𝑛 ∈ N,

define [𝑚, 𝑛] = {𝑚, 𝑚 + 1, . . . , 𝑛} and, as an abbreviation, we write [𝑛] = [1, 𝑛] when 𝑚 = 1.

1.1 Linear Permutations, Statistics, and Shuffles

A linear permutation of a finite set 𝐴 ⊂ P is an arrangement 𝜋 = 𝜋1𝜋2 . . . 𝜋𝑛 of elements in 𝐴

where each element is used exactly once. In this case, 𝑛 is called the length of 𝜋, and we write it

as #𝜋 = |𝜋| = 𝑛. The hash symbol and absolute value sign will also be used for the cardinality of a

set. We let

For example,

𝐿 ( 𝐴) = {𝜋 | 𝜋 is a linear permutation of 𝐴}.

𝐿 ({1, 4, 6}) = {146, 164, 416, 461, 614, 641}.

In particular, let 𝔖𝑛 be the symmetric group on [𝑛] viewed as linear permutations of [𝑛]. We

will often drop the descriptor “linear” if it is clear from context that we are referring to linear

permutations, but it will be useful later to distinguish from cyclic permutations.

A (linear) permutation statistic is a function whose domain is the set of all linear permutations.

There are several classical permutation statistics that we mainly concern with: the descent set Des,

the descent number des, the peak set Pk, the peak number pk and the major index maj.

For a linear permutation 𝜋 = 𝜋1𝜋2 . . . 𝜋𝑛, a descent of 𝜋 is a position 𝑖 such that 𝜋𝑖 > 𝜋𝑖+1. The

descent set Des is defined by

Des 𝜋 = {𝑖 | 𝑖 is a descent of 𝜋} ⊆ [𝑛 − 1].

The descent number of 𝜋 is des 𝜋 := | Des 𝜋|. A peak of 𝜋 is a position 𝑖 such that 𝜋𝑖−1 < 𝜋𝑖 > 𝜋𝑖+1.

The peak set Pk is defined by

Pk 𝜋 = {𝑖 | 𝑖 is a peak of 𝜋} ⊆ [2, 𝑛 − 1].

1

The peak number is pk 𝜋 := | Pk 𝜋|. The major index

maj 𝜋 =

∑︁

𝑖

𝑖∈Des 𝜋

is the sum of its descents.

We will often need to evaluate a statistic st on a set of permutations Π. So we define the

distribution of st over Π to be

st Π = {{st 𝜋 | 𝜋 ∈ Π}}.

Note that this is a set with multiplicity since st may evaluate to the same thing on various members

of Π. We will sometimes use exponents to denote multiplicities where, as usual, no exponent

means multiplicity 1. For example,

des 𝔖3 = {{0, 14, 2}}

meaning that among the six permutations in 𝔖3, only 123 has no descents, only 321 has two

descents and the other four all have one descent.

If 𝜋 ∈ 𝐿( 𝐴) and 𝜎 ∈ 𝐿(𝐵) where 𝐴 ∩ 𝐵 = ∅ then these permutations have shuffle set

𝜋 (cid:1) 𝜎 = {𝜏 ∈ 𝐿( 𝐴 ⊎ 𝐵) | 𝜋, 𝜎 are subwords of 𝜏}

where a subwords of a permutation 𝜏 is a subsequence of (not necessarily consecutive) elements

of 𝜏. For instance,

64 (cid:1) 25 = {6425, 6245, 6254, 2564, 2645, 2654}.

All of the statistics defined above have a remarkable property related to shuffles, called “shuffle-

compatibility”. A permutation statistic st is shuffle-compatible if for all quadruples 𝜋, 𝜋′, 𝜎, 𝜎′

with st 𝜋 = st 𝜋′, st 𝜎 = st 𝜎′, |𝜋| = |𝜋′|, and |𝜎| = |𝜎′| we have

st(𝜋 (cid:1) 𝜎) = st(𝜋′ (cid:1) 𝜎′),

that is, the distribution of st on a set of shuffles depends only on the values of st on the permutations

being shuffled and their lengths.

2

Shuffle-compatibility dates back to the early work of Stanley, as the shuffle-compatibility of the

descent set, descent number, and major index are implicit consequences of the theory of 𝑃-partitions

[Sta72]. Likewise, Stembridge’s work on enriched 𝑃-partitions implies that the peak set and

peak number are shuffle-compatible. Gessel and Zhuang coined the term “shuffle-compatibility”

and initiated the study of shuffle-compatibility per se in 2018; in [GZ18], they developed an

algebraic framework for shuffle-compatibility centered around the notion of the shuffle algebra

of a shuffle-compatible permutation statistic, which is well-defined if and only if the statistic is

shuffle-compatible and whose multiplication encodes the distribution of the statistic over sets of

shuffles.

Gessel’s [Ges84] quasisymmetric functions serve as natural generating functions for 𝑃-partitions.

And for a special family of statistics called “descent statistics”, Gessel and Zhuang used quasisym-

metric functions to characterize shuffle algebras and prove shuffle-compatibility results.

Given two linear permutation statistics st1 and st2, we say that st1 is a refinement of st2 if for

all permutations 𝜋 and 𝜎 of the same length, st1 [𝜋] = st1 [𝜎] implies st2 [𝜋] = st2 [𝜎]; when this

is true, we also say that st2 is a coarsening of st1. A permutation statistic st is a descent statistic if

Des 𝜋 = Des 𝜎 and |𝜋| = |𝜎| implies st 𝜋 = st 𝜎. Alternatively, a descent statistic is a coarsening

of descent set. Note that Des itself, des, Pk, and pk are all descent statistics.

One of Gessel and Zhuang’s main results is a necessary and sufficient condition for shuffle-

compatibility of descent statistics which implies that the shuffle algebra of any shuffle-compatible

descent statistic is isomorphic to a quotient algebra of the algebra of quasisymmetric functions.

1.2 Cyclic Permutations, Cyclic Statistics, and Cyclic Shuffles

Recently Adin, Gessel, Reiner, and Roichman [AGRR21] introduced a cyclic version of qua-

sisymmetric functions with a corresponding cyclic shuffle operation. For a linear permutation

𝜋 = 𝜋1𝜋2 . . . 𝜋𝑛, we define the corresponding cyclic permutation [𝜋] to be the set of rotations of 𝜋,

that is,

[𝜋] = {𝜋1𝜋2 . . . 𝜋𝑛, 𝜋2 . . . 𝜋𝑛𝜋1,

. . . , 𝜋𝑛𝜋1 . . . 𝜋𝑛−1}.

3

For example,

[2856] = {2856, 8562, 5628, 6285}.

Let [𝔖𝑛] denote the set of cyclic permutations on [𝑛]. The length of a cyclic permutation [𝜋]

refers to the length of 𝜋, which makes sense because all linear permutation representatives of [𝜋]

have the same length. We let

𝐶 ( 𝐴) = {[𝜋] | [𝜋] is a cyclic permutation of 𝐴}.

For instance,

𝐶 ({2, 3, 5, 8}) = {[2358], [2385], [2538], [2583], [2835], [2853]}.

A cyclic permutation statistic is any function cst whose domain is cyclic permutations. We can

lift the linear permutation statistics we have introduced to the cyclic realm as follows.

The cyclic descent set cDes of a linear permutation 𝜋 is defined by

cDes 𝜋 = {𝑖 | 𝜋𝑖 > 𝜋𝑖+1 where the subscripts are taken modulo 𝑛} ⊆ [𝑛].

Also define the cyclic descent number

cdes 𝜋 := | cDes 𝜋|.

This leads to the cyclic descent set of a cyclic permutation

cDes[𝜋] = {{cDes 𝜎 | 𝜎 ∈ [𝜋]}},

which is a multiset. The multiplicity comes into play since cDes may have the same value on

different representatives 𝜎 in [𝜋]. Now we can define the cyclic descent number

cdes[𝜋] := cdes 𝜋.

This is well-defined since all elements of [𝜋] have the same number of cyclic descents. For example

if 𝜋 = 3728, then we have cDes 𝜋 = {2, 4} and cdes 𝜋 = 2 which extend to cyclic permutations as

cDes[3728] = {{cDes 3728, cDes 7283, cDes 2837, cDes 8372}} = {{ {1, 3}2, {2, 4}2 }},

4

and cdes[3728] = 2. Similarly, if we define the cyclic peak set cPk of a linear permutation 𝜋 by

cPk 𝜋 = {𝑖 | 𝜋𝑖−1 < 𝜋𝑖 > 𝜋𝑖+1 where the subscripts are taken modulo 𝑛} ⊆ [𝑛],

and the cyclic peak number

cpk 𝜋 := | cPk 𝜋|.

Then the cyclic counterpart of Pk, the cyclic peak set cPk of a cyclic permutation is defined as

and the cyclic peak number

cPk[𝜋] = {{cPk 𝜎 | 𝜎 ∈ [𝜋]}},

cpk[𝜋] := cpk 𝜋.

Remark 1.2.1. By definition, cDes[𝜋] carries the information for all representatives in [𝜋]. More-

over, cDes 𝜋 together with |𝜋| will be sufficient to determine cDes[𝜋]. In fact, cDes[𝜋] is simply

collecting all cyclic shifts of cDes 𝜋 in [𝑛] where 𝑛 = |𝜋|, namely,

cDes[𝜋] = {{ 𝑖 + cDes 𝜋 | 𝑖 ∈ [𝑛] }}.

Here 𝑖 + cDes 𝜋 is the set defined by (2.1.1). Similarly, cPk[𝜋] can be entirely determined by cPk 𝜋

and |𝜋|.

On the other hand, finding a suitable cyclic analogue of the major index statistic is challenging;

we will address this in Section 4.4.3.

Given two cyclic permutation statistics cst1 and cst2, we say that cst1 is a refinement of cst2 if for

all cyclic permutations [𝜋] and [𝜎] of the same length, cst1 [𝜋] = cst1 [𝜎] implies cst2 [𝜋] = cst2 [𝜎];

when this is true, we also say that cst2 is a coarsening of cst1. A cyclic permutations statistic cst

is a cyclic descent statistic if cst is a coarensing of cDes. Alternatively, cst is a cyclic permutation

statistic if cDes[𝜋] = cDes[𝜎] and |𝜋| = |𝜎| implies cst[𝜋] = cst[𝜎]. We note that all four of our

cyclic statistics are cyclic descent statistics.

The definitions for shuffles follow the same pattern already established. Given [𝜋] ∈ 𝐶 ( 𝐴) and

[𝜎] ∈ 𝐶 (𝐵) where 𝐴 ∩ 𝐵 = ∅, we define their cyclic shuffle set to be

[𝜋] (cid:1) [𝜎] = {[𝜏] | 𝜏 = 𝜋′ (cid:1) 𝜎′ where 𝜋′ ∈ [𝜋] and 𝜎′ ∈ [𝜎]}.

5

To illustrate,

[14] (cid:1) [23] = {[1234], [1243], [1324], [1342], [1423], [1432]}.

(1.2.1)

We call a cyclic permutation statistic cst cyclic shuffle-compatible if for all quadruples [𝜋], [𝜋′],

[𝜎], [𝜎′] with cst[𝜋] = cst[𝜋′], cst[𝜎] = cst[𝜎′], |𝜋| = |𝜋′|, and |𝜎| = |𝜎′| we have

cst([𝜋] (cid:1) [𝜎]) = cst( [𝜋′] (cid:1) [𝜎′]).

The first results in cyclic shuffle-compatibility were implicit in the work of Adin et al. [AGRR21],

which introduced toric [ (cid:174)𝐷]-partitions (a toric poset analogue of 𝑃-partitions) and cyclic quasisym-

metric functions (which are natural generating functions for toric [ (cid:174)𝐷]-partitions). In particular,

Adin et al. established a multiplication formula for fundamental cyclic quasisymmetric functions

which implies that the cyclic descent set cDes is cyclic shuffle-compatible, and they also proved

the formula

∑︁

𝑞cdes 𝜏 = (1 − 𝑞) |𝜋|+|𝜎|

[𝜏]∈[𝜋](cid:1)[𝜎]

∞
∑︁

𝑘=0

(cid:18)𝑘 + |𝜋| − cdes 𝜋 − 1
|𝜋| − 1

(cid:19) (cid:18)𝑘 + |𝜎| − cdes 𝜎 − 1
|𝜎| − 1

(cid:19)

𝑘𝑞𝑘

which implies that the cyclic descent number cdes is cyclic shuffle-compatible.

1.3 Outline

This dissertation is devoted to the study of cyclic shuffle-compatibility, featuring on its correla-

tions with cyclic permutations and cyclic quasisymmetric functions. In the next chapter, we recall

some basic concepts such as quasisymmetric functions and cyclic quasisymmetric functions, with

several concrete examples provided.

In Chapter 3 we study cyclic shuffle-compatibility through purely combinatorial means.

In

particular, we show how one can lift shuffle-compatibility results for linear permutations to cyclic

ones. We then apply this result to cyclic descents and cyclic peaks. This chapter contains materials

from Domagalski, Liang, Minnich, Sagan, Schmidt, and Sietsema [DLM+21].

In chapter 4, we define the cyclic shuffle algebra of a cyclic shuffle-compatible statistic, and

develop an algebraic framework for cyclic shuffle-compatibility in which the role of quasisymmetric

6

functions is replaced by the cyclic quasisymmetric functions recently introduced by Adin, Gessel,

Reiner, and Roichman. We use our theory to provide explicit descriptions for the cyclic shuffle

algebras of various cyclic permutation statistics, which in turn gives algebraic proofs for their cyclic

shuffle-compatibility. This chapter contains materials from Liang, Sagan, and Zhuang [LSZ23].

Chapter 5 develops the theory of enriched toric [ (cid:174)𝐷]-partitions. Whereas Stembridge’s enriched

𝑃-partitions give rises to the peak algebra which is a subring of the ring of quasisymmetric functions

QSym, our enriched toric [ (cid:174)𝐷]-partitions will generate the cyclic peak algebra which is a subring of

cyclic quasisymmetric functions cQSym. In the same manner as the peak set of linear permutations

appears when considering enriched 𝑃-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.

7

CHAPTER 2

PRELIMINARIES

In this chapter, we provide the necessary background for this dissertation.

In Section 2.1, we

review the relations between sets and compositions which will be useful to index bases of (cyclic)

quasisymmetric functions in later sections.

In Section 2.2 and Section 2.3, we provide a terse

introduction of quasisymmetric functions and cyclic quasisymmetric functions respectively.

2.1 Sets and Compositions

For 𝑛 ∈ P, let 2[𝑛] denote the set of all subsets of [𝑛], and 2[𝑛]

0 be the set of all nonempty subsets
of [𝑛]. A composition of 𝑛 is a tuple of positive integers that sum to 𝑛. Denote by Comp𝑛 the set

of all compositions of 𝑛 and write 𝛼 ⊨ 𝑛 for 𝛼 ∈ Comp𝑛.

Definition 2.1.1 (Cyclic shift of a set). Define a cyclic shift of a subset 𝐸 ⊆ [𝑛] in [𝑛] to be a set

of the form

𝑖 + 𝐸 = {𝑖 + 𝑒 (mod 𝑛) | 𝑒 ∈ 𝐸 } ⊆ [𝑛].

(2.1.1)

For example if 𝐸 = {2, 4, 5} ⊆ [6], then 3 + 𝐸 = {1, 2, 5}. Note that sometimes we will use 𝐸 + 𝑖 as

well for the same concept. While using a negative shift, the reader should be careful to distinguish

between 𝐸 − 𝑖 and the set difference 𝐸 − {𝑖} = 𝐸 \ {𝑖}. We usually use [𝑆] to denote the equivalence

class of 𝑆 under cyclic shifts.

Definition 2.1.2 (Cyclic shift of a composition). A cyclic shift of a composition 𝛼 = (𝛼1, 𝛼2, . . . , 𝛼𝑚)

is a composition of the form

for some 𝑘 ∈ [𝑚].

(𝛼𝑘 , . . . , 𝛼𝑚, 𝛼1, . . . , 𝛼𝑘−1)

Definition 2.1.3 (Cyclic composition). A cyclic composition of 𝑛 is then the equivalence class of

a composition of 𝑛 under cyclic shift.

For example,

[2, 1, 3] = {(2, 1, 3), (1, 3, 2), (3, 2, 1)}

8

and

[1, 2, 1, 2] = {(1, 2, 1, 2), (2, 1, 2, 1)}

are both cyclic compositions. By convention, we will also allow the empty set ∅ to be a cyclic
composition. Furthermore, we adopt the notations from [AGRR21] and denote by 𝑐2[𝑛]
0
tively, cComp𝑛) the set of equivalence classes of elements of 2[𝑛]

(respectively, Comp𝑛) under

(respec-

0

cyclic shifts. In another word, cComp𝑛 is the set of cyclic compositions of 𝑛.

Now we recall two natural bijections which will play important roles when indexing two

particular bases of (cyclic) quasisymmetric functions.

The first natural bijection is between 2[𝑛−1] and Comp𝑛. The map Φ : 2[𝑛−1] → Comp𝑛 is

defined by

Φ(𝐸) := (𝑒1 − 𝑒0, 𝑒2 − 𝑒1, . . . , 𝑒𝑘 − 𝑒𝑘−1, 𝑒𝑘+1 − 𝑒𝑘 )

(2.1.2)

for any given 𝐸 = {𝑒1 < 𝑒2 < · · · < 𝑒𝑘 } ⊆ [𝑛 − 1] with 𝑒0 = 0 and 𝑒𝑘+1 = 𝑛, where the inverse

map is

Φ−1(𝛼) = {𝛼1, 𝛼1 + 𝛼2, . . . , 𝛼1 + 𝛼2 + · · · + 𝛼𝑘 }

for any 𝛼 = (𝛼1, . . . , 𝛼𝑘+1) ⊨ 𝑛. For example, 𝑛 = 6 and 𝐸 = {3, 5}, then Φ(𝐸) = (3, 2, 1) and

Φ−1(3, 2, 1) = {3, 5} = 𝐸.

Another bijection is between 𝑐2[𝑛]
0

map 𝜓 : 2[𝑛]
0

→ Comp𝑛 defined by

and cComp𝑛, for the sake of which we need to consider the

𝜓(𝐸) := (𝑒2 − 𝑒1, . . . , 𝑒𝑘 − 𝑒𝑘−1, 𝑒1 − 𝑒𝑘 + 𝑛)

(2.1.3)

where 𝐸 = {𝑒1 < 𝑒2 < · · · < 𝑒𝑘 } ⊆ [𝑛]. Notice that if 𝐸′ is a cyclic shift of 𝐸 in [𝑛], then 𝜓(𝐸′)
is also a cyclic shift of 𝜓(𝐸). Therefore 𝜓 induces a map Ψ : 𝑐2[𝑛]
0

→ cComp𝑛. Moreover, it is

straightforward to check that the induced map Ψ is bijective.

Definition 2.1.4 (Non-Escher). Let us call 𝑆 a non-Escher1 subset of [𝑛] if 𝑆 is the cyclic descent

set of some linear permutation of length 𝑛.

1We borrow the term “non-Escher” from [AGRR21] and other recent works on cyclic descent extensions. As

explained there, this term is a reference to M. C. Escher’s painting “Ascending and Descending”.

9

When 𝑛 = 0 or 𝑛 = 1, only the empty set is non-Escher, and when 𝑛 ≥ 2, all subsets of [𝑛] are

non-Escher except for the empty set and [𝑛] itself. We associate to each non-Escher subset 𝑆 ⊆ [𝑛]

a composition cComp 𝑆 defined by

cComp 𝑆 (cid:66)






(𝑠2 − 𝑠1, . . . , 𝑠 𝑗 − 𝑠 𝑗−1, 𝑛 − 𝑠 𝑗 + 𝑠1),

if 𝑛 ≥ 2,

(1),

∅,

if 𝑛 = 1,

if 𝑛 = 0.

It is easy to see that if 𝑆′ is a cyclic shift of 𝑆, then cComp 𝑆′ is a cyclic shift of cComp 𝑆. So we

can let cComp[𝑆] be the cyclic composition defined by

cComp[𝑆] (cid:66) [cComp 𝑆].

We say that a cyclic composition is non-Escher if it is an image of this induced map cComp, and

one can check that cComp is a bijection from equivalence classes of non-Escher subsets of [𝑛]

under cyclic shift to non-Escher cyclic compositions of 𝑛.

Definition 2.1.5 (Cyclic descent composition). If 𝑆 is the cyclic descent set of a linear permutation

𝜋, then we call cComp[𝑆] the cyclic descent composition of the cyclic permutation [𝜋]. We denote

the cyclic descent composition of [𝜋] simply as cComp[𝜋].

For example, take 𝜋 = 179624. Then 𝜋 has cyclic descent set 𝑆 = {3, 4, 6}, so the cyclic descent

composition of [𝜋] is cComp[𝑆] = [1, 2, 3], which we also denote by cComp[𝜋].

2.2 Quasisymmetric Functions QSym

Definition 2.2.1 (Quasisymmetric function). A quasisymmetric function is a formal power series

𝑓 ∈ Q[[𝑥1, 𝑥2, . . .]] such that for any sequence of positive integers 𝑎 = (𝑎1, 𝑎2, . . . , 𝑎𝑠), and two

increasing sequences 𝑖1 < 𝑖2 < · · · < 𝑖𝑠 and 𝑗1 < 𝑗2 < · · · < 𝑗𝑠 of positive integers,

[𝑥𝑎1
𝑖1

𝑥𝑎2
𝑖2

. . . 𝑥𝑎𝑠
𝑖𝑠

] 𝑓 = [𝑥𝑎1
𝑗1

𝑥𝑎2
𝑗2

. . . 𝑥𝑎𝑠
𝑗𝑠

] 𝑓 ,

where [𝑥𝑎1
𝑖1

𝑥𝑎2
𝑖2

. . . 𝑥𝑎𝑠
𝑖𝑠

] 𝑓 denotes the coefficient of monomial 𝑥𝑎1
𝑖1

𝑥𝑎2
𝑖2

. . . 𝑥𝑎𝑠
𝑖𝑠

in the expression of 𝑓 .

10

Let QSym𝑛 be the set of all quasisymmetric functions which are homogeneous of degree 𝑛, and

QSym = ⊕𝑛≥0 QSym𝑛. Two bases of QSym are particularly important to our work: monomial

quasisymmetric functions 𝑀𝐿 and fundamental quasisymmetric functions 𝐹𝐿.

Definition 2.2.2 (Monomial quasisymmetric functions). Given a composition 𝛼 = (𝛼1, 𝛼2, . . . , 𝛼𝑠) ⊨

𝑛, the associated monomial quasisymmetric function indexed by 𝛼 is

𝑀𝛼 =

∑︁

𝑖1<𝑖2<···<𝑖𝑠

𝑥𝛼1
𝑖1

𝑥𝛼2
𝑖2

. . . 𝑥𝛼𝑠
𝑖𝑠

.

It is clear that {𝑀𝛼}𝛼⊨𝑛 form a basis of QSym𝑛. From the natural bijection Φ : 2[𝑛−1] → Comp𝑛

defined by (2.1.2), we can also index the monomial quasisymmetric functions by subsets 𝐸 ⊆ [𝑛−1],

and define 𝑀𝑛,𝐸 := 𝑀Φ(𝐸).

The fundamental quasisymmetric functions form another important basis of QSym.

Definition 2.2.3 (Fundamental quasisymmetric function). The fundamental quasisymmetric func-

tion indexed by 𝐸 ⊆ [𝑛 − 1] is

𝐹𝑛,𝐸 =

∑︁

𝑥𝑖1

𝑥𝑖2

. . . 𝑥𝑖𝑛 .

𝑖1≤···≤𝑖𝑛
𝑖𝑘 <𝑖𝑘+1 if 𝑘 ∈ 𝐸

Similarly, we can define 𝐹𝛼 := 𝐹Φ−1 (𝛼) indexed by compositions.

The relation between monomial and fundamental quasisymmetric functions is simple:

𝐹𝑛,𝐸 =

𝑀𝑛,𝐿.

∑︁

𝐿⊇𝐸

(2.2.1)

By the principle of inclusion and exclusion, 𝑀𝑛,𝐸 can be expressed as a linear combination of the

𝐹𝑛,𝐿, from which we can tell that {𝐹𝑛,𝐿 }𝐿⊆[𝑛−1] spans QSym𝑛. By checking the cardinality of both

sets {𝐹𝑛,𝐿 }𝐿⊆[𝑛−1] and {𝑀𝑛,𝐸 }𝐸 ⊆[𝑛−1], it follows that {𝐹𝑛,𝐿 }𝐿⊆[𝑛−1] is indeed a basis of QSym𝑛.

Example 2.2.4. Consider 𝐸 = {1, 3}, by definition we have

𝐹4,{1,3} =

∑︁

𝑥𝑖1

𝑥𝑖2

𝑥𝑖3

𝑥𝑖4 =

∑︁

𝑥𝑖1

𝑥𝑖2

𝑥𝑖3

𝑥𝑖4 +

𝑖1<𝑖2≤𝑖3<𝑖4

𝑖1<𝑖2<𝑖3<𝑖4

∑︁

𝑖1<𝑖2<𝑖4

𝑥𝑖1

𝑥2
𝑖2

.

𝑥𝑖4

11

There are only two choices for a set 𝐿 satisfying that 𝐸 ⊆ 𝐿 ⊆ [3]: {1, 3} or {1, 2, 3}. Since

Φ({1, 3}) = (1, 2, 1), Φ({1, 2, 3}) = (1, 1, 1, 1) , we get

𝑀4,{1,3} = 𝑀(1,2,1) =

∑︁

𝑖1<𝑖2<𝑖3

𝑥𝑖1

𝑥2
𝑖2

𝑥𝑖3

, 𝑀4,{1,2,3} = 𝑀(1,1,1,1) =

∑︁

𝑖1<𝑖2<𝑖3<𝑖4

𝑥𝑖1

𝑥𝑖2

𝑥𝑖3

𝑥𝑖4

.

The calculation above verifies that 𝐹4,{1,3} = 𝑀4,{1,3} + 𝑀4,{1,2,3} = (cid:205)

𝐿⊇{1,3}

𝑀4,𝐿.

2.3 Cyclic Quasisymmetric Functions cQSym

In this subsection, we recall from [AGRR21] the theory of cyclic quasisymmetric functions.

Definition 2.3.1 (Cyclic quasisymmetric functions). A cyclic quasisymmetric function is a formal

power series 𝑓 ∈ Q[[𝑥1, 𝑥2, . . .]] such that for any sequence of positive integers 𝑎 = (𝑎1, 𝑎2, . . . , 𝑎𝑠),

a cyclic shift (𝑎′
1

, 𝑎′
2

, . . . , 𝑎′

𝑠) of 𝑎, and two increasing sequences 𝑖1 < 𝑖2 < · · · < 𝑖𝑠 and 𝑗1 < 𝑗2 <

· · · < 𝑗𝑠 of positive integers,

[𝑥𝑎1
𝑖1

𝑥𝑎2
𝑖2

. . . 𝑥𝑎𝑠
𝑖𝑠

] 𝑓 = [𝑥𝑎′
1
𝑗1

𝑥𝑎′
2
𝑗2

. . . 𝑥𝑎′
𝑠
𝑗𝑠

] 𝑓 ,

namely the coefficients of 𝑥𝑎1
𝑖1

𝑥𝑎2
𝑖2

. . . 𝑥𝑎𝑠

𝑖𝑠 and 𝑥𝑎′
1
𝑗1

𝑥𝑎′
2
𝑗2

. . . 𝑥𝑎′

𝑠

𝑗𝑠 in 𝑓 are equal.

Denote by cQSym𝑛 the set of all cyclic quasisymmetric functions which are homogeneous of degree

𝑛, and cQSym = ⊕𝑛≥0 cQSym𝑛.

Remark 2.3.2. It is clear that there exists a strict inclusion relation Sym ⊊ cQSym ⊊ QSym,

where Sym = ⊕𝑛≥0𝔖𝑛 is the algebra of symmetric functions.

We have the following cyclic analogues of the concepts of monomial (fundamental) quasisym-

metric functions.

Definition 2.3.3 (Monomial cyclic quasisymmetric function).

Given a composition 𝛼 = (𝛼1, 𝛼2, . . . , 𝛼𝑠) ⊨ 𝑛, the associated monomial cyclic quasisymmetric

function indexed by 𝛼 is

𝑀 cyc

𝛼 =

𝑠
∑︁

𝑖=1

𝑀(𝛼𝑖,𝛼𝑖+1,...,𝛼𝑖−1),

12

Table 2.1 Monomial cyclic quasisymmetric functions indexed by compositions of 4

𝛼 ⊨ 4
(4)
(1,3) or (3,1)
(2, 2)

(1, 1, 1, 1)

𝑀 cyc
𝛼
𝑀(4) = 𝑀4,∅
𝑀(1,3) + 𝑀(3,1) = 𝑀4,{1} + 𝑀4,{3}
2𝑀(2,2) = 2𝑀4,{2}

4𝑀(1,1,1,1) = 4𝑀4,{1,2,3}

(1,1,2) or (1,2,1) or (2,1,1) 𝑀(1,1,2) + 𝑀(1,2,1) + 𝑀(2,1,1) = 𝑀4,{1,2} + 𝑀4,{1,3} + 𝑀4,{2,3}

where the indices are interpreted modulo 𝑠, meaning 𝛼 𝑗 = 𝛼 𝑗+𝑠. In other words, 𝑀 cyc
𝛼

sums over

all monomial quasisymmetric functions indexed by cyclic shifts of 𝛼. Therefore it is clear that

𝑀 cyc

𝛼 = 𝑀 cyc
𝛼′

if 𝛼 and 𝛼′ only differ by a cyclic shift.

We can also index the monomial cyclic quasisymmetric function by sets. For a nonempty

𝐸 ⊆ [𝑛], define 𝑀 cyc

𝑛,𝐸 := 𝑀 cyc

𝜓(𝐸) via the map 𝜓 : 2[𝑛]

0

→ Comp𝑛 defined by (2.1.3), and set

𝑀 cyc

𝑛,∅ := 0. Similarly it can be shown that 𝑀 cyc
The following result gives the expression of monomial cyclic quasisymmetric functions in terms

𝑛,𝐸 ′ if 𝐸′ is a cyclic shift of 𝐸.

𝑛,𝐸 = 𝑀 cyc

of monimial quasisymmetric functions.

Lemma 2.3.4 ([AGRR21] Lemma 2.5, monomial to cyclic monomial). For any subset 𝐸 ⊆ [𝑛]

where the set 𝐸 − 𝑒 is defined as (2.1.1).

𝑀 cyc

𝑛,𝐸 =

∑︁

𝑒∈𝐸

𝑀𝑛,(𝐸−𝑒)∩[𝑛−1],

(2.3.1)

□

Example 2.3.5. Table 2.1 computes all monomial cyclic quasisymmetric function indexed by

compositions of 4, in terms of monomial quasisymmetric functions.

For the natural desire of establishing a similar relation as the one between monomial and

fundamental quasisymmetric functions given by (2.2.1) in our cyclic situation, define

Definition 2.3.6 (Fundamental cyclic quasisymmetric function). The fundamental cyclic quasisym-

metric function indexed by 𝐸 ⊆ [𝑛] is

𝐹cyc
𝑛,𝐸 :=

𝑀 cyc
𝑛,𝐿 .

∑︁

𝐿⊇𝐸

13

(2.3.2)

Example 2.3.7. Consider 𝑛 = 4 and 𝐸 = {1, 3}. By definition

𝐹cyc
4,{1,3} =

∑︁

𝑀 cyc
4,𝐿

𝐿⊇{1,3}
4,{1,3} + 𝑀 cyc
(2,2) + 𝑀 cyc

4,{1,2,3} + 𝑀 cyc
(1,1,2) + 𝑀 cyc

(𝑖)
= 𝑀 cyc

(𝑖𝑖)
= 𝑀 cyc

(2,1,1) + 𝑀 cyc
2𝑀(2,2) + 2 (cid:0)𝑀(1,1,2) + 𝑀(1,2,1) + 𝑀(2,1,1))(cid:1) + 4𝑀(1,1,1,1)

(1,1,1,1)

(𝑖𝑖𝑖)
=

4,{1,3,4} + 𝑀 cyc

4,{1,2,3,4}

= 2

∑︁

𝑖1<𝑖2

𝑥2
𝑖1

𝑥2
𝑖2

∑︁

𝑖1<𝑖2<𝑖3
∑︁

+ 2

+ 4

(𝑥𝑖1

𝑥𝑖2

𝑥2
𝑖3

+ 𝑥𝑖1

𝑥2
𝑖2

𝑥𝑖3 + 𝑥2
𝑖1

𝑥𝑖2

𝑥𝑖3)

𝑥𝑖1

𝑥𝑖2

𝑥𝑖3

𝑥𝑖4

.

𝑖1<𝑖2<𝑖3<𝑖4

Equality (𝑖) follows from the fact that the choices for 𝐿 ⊇ {1, 3} in [4] are {1, 3}, {1, 2, 3}, {1, 3, 4}

and {1, 2, 3, 4}. Equality (𝑖𝑖) is obtained by changing indices under the map 𝜓 defined by (2.1.3),

equality (𝑖𝑖𝑖) is from Table 2.1.

The following transition from fundamental to cyclic fundamental quasisymmetric functions

should come without surprise.

Lemma 2.3.8 ([AGRR21, Proposition 2.15], fundamental to cyclic fundamental). For any subset

𝐸 ⊆ [𝑛],

with set 𝐸 − 𝑖 defined by (2.1.1).

Remark 2.3.9.

𝐹cyc
𝑛,𝐸 =

∑︁

𝑖∈[𝑛]

𝐹𝑛,(𝐸−𝑖)∩[𝑛−1],

□

1. It follows directly from Lemma 2.3.8 that 𝐹cyc

𝑛,𝐸 = 𝐹cyc

𝑛,𝐸 ′ if 𝐸′ is a cyclic shift of 𝐸.

2. Clearly the set {𝑀 cyc

𝑛,𝐸 : 𝐸 ∈ 𝑐2[𝑛]

0

monomial of degree 𝑛 appears in 𝑀 cyc

} spans cQSym𝑛 and is linearly independent, as each
𝑛,𝐸 : 𝐸 ∈ 𝑐2[𝑛]
𝑛,𝐸 for exactly one 𝐸 ∈ 𝑐2[𝑛]

0 . Hence {𝑀 cyc

}

0

14

is a basis of cQSym𝑛. Applying the principle of inclusion and exclusion on (2.3.2) we have

𝑀 cyc

𝑛,𝐸 =

∑︁

𝐿⊇𝐸

(−1) |𝐿\𝐸 | 𝐹cyc
𝑛,𝐿 ,

which implies that {𝐹cyc
dimension of vector space cQSym𝑛 is #𝑐2[𝑛]

𝑛,𝐸 : 𝐸 ∈ 𝑐2[𝑛]

0

} also spans cQSym𝑛; together with the fact that the

0 , {𝐹cyc

𝑛,𝐸 : 𝐸 ∈ 𝑐2[𝑛]

0

} is also a basis of cQSym𝑛.

15

CHAPTER 3

CYCLIC SHUFFLE-COMPATIBILITY: COMBINATORIALLY

In this chapter we will provide a general method for proving cyclic shuffle-compatibility results as

corollaries of linear ones. We note that in this chapter we will be using the set

𝐸 + 𝑖 = {𝑒 + 𝑖 | 𝑒 ∈ 𝐸 },

(3.0.1)

which is different from the set 𝐸 + 𝑖 defined in equation (2.1.1).

3.1 The Lifting Lemma

Definition 3.1.1 (Standardization). Suppose 𝐴, 𝐵 ⊂ P with | 𝐴| = |𝐵| = 𝑛 and 𝜋 = 𝜋1𝜋2 . . . 𝜋𝑛 ∈

𝐿 ( 𝐴). The standardization of 𝜋 to 𝐵 is

std𝐵 𝜋 = 𝑓 (𝜋1) 𝑓 (𝜋2) . . . 𝑓 (𝜋𝑛) ∈ 𝐿 (𝐵)

where 𝑓 : 𝐴 → 𝐵 is the unique order-preserving bijection between 𝐴 and 𝐵. If 𝐵 = [𝑛] then we

write just std 𝜋 for std[𝑛] 𝜋 and call this the standardization of 𝜋.

For example, if 𝐴 = {1, 4, 5, 8} and 𝐵 = {2, 3, 6, 9}, then std𝐵 (5481) = 6392. Standardization for

cyclic permutations is defined in the analogous manner.

We first prove a result about cyclic descent statistics which is a cyclic analogue of one in the

linear case [BJS20].

Lemma 3.1.2. Let cst be a cyclic descent statistic. For any four cyclic permutations [𝜋], [𝜋′], [𝜎],

[𝜎′] such that

we have

std[𝜋] = std[𝜋′]

and

std[𝜎] = std[𝜎′]

cst([𝜋] (cid:1) [𝜎]) = cst( [𝜋′] (cid:1) [𝜎′]).

Proof. Since cst is a cyclic descent statistic, its values only depends on the relative order of adjacent

elements. So it suffices to prove the case when

[𝜋] ⊎ [𝜎] = [𝜋′] ⊎ [𝜎′] = [𝑚 + 𝑛]

16

where 𝑚 = |𝜋| = |𝜋′| and 𝑛 = |𝜎| = |𝜎′|. For simplicity, let 𝐴 = [𝑚] and 𝐵 = [𝑛] + 𝑚.

We claim that it suffices to find, for any 𝜋 and 𝜎 as in the previous paragraph, a cst-preserving

bijection

[𝜋] (cid:1) [𝜎] → std𝐴 [𝜋] (cid:1) std𝐵 [𝜎].

From this map and the hypothesis of the lemma we have

cst([𝜋] (cid:1) [𝜎]) = cst(std𝐴 [𝜋] (cid:1) std𝐵 [𝜎]) = cst(std𝐴 [𝜋′] (cid:1) std𝐵 [𝜎′]) = cst( [𝜋′] (cid:1) [𝜎′]).

We will show the existence of this bijection by induction on the size of the set of what we will

call out-of-order pairs

𝑂 = {(𝑖, 𝑗) ∈ 𝜋 × 𝜎 | 𝑖 > 𝑗 }.

If #𝑂 = 0 then [𝜋] ∈ 𝐶 ( 𝐴) and [𝜎] ∈ 𝐶 (𝐵). It follows that [𝜋] = std𝐴 [𝜋] and [𝜎] = std𝐵 [𝜎] so

the identity map will do.

For the induction step, let #𝑂 > 0. Then there must be a pair (𝑖, 𝑖 − 1) ∈ 𝑂. Let 𝜋′′ = (𝑖 − 1, 𝑖)𝜋

and 𝜎′′ = (𝑖 − 1, 𝑖)𝜎 where (𝑖 − 1, 𝑖) is the transposition which exchanges 𝑖 − 1 and 𝑖. We will be

done if we can construct a cst preserving bijection

𝑇𝑖 : [𝜋] (cid:1) [𝜎] → [𝜋′′] (cid:1) [𝜎′′].

This is because 𝜋′′, 𝜎′′ have fewer out-of-order pairs and so, by induction, there is a cst-preserving

bijection [𝜋′′] (cid:1) [𝜎′′] → std𝐴 [𝜋′′] (cid:1) std𝐵 [𝜎′′] which, when composed with 𝑇𝑖, will finish the

construction.

Define 𝑇𝑖 by

𝑇𝑖 [𝜏] =





[(𝑖 − 1, 𝑖)𝜏]

if 𝑖 − 1, 𝑖 are not cyclically adjacent in [𝜏],

[𝜏]

else.

We must first check that 𝑇𝑖 is well defined in that 𝑇𝑖 [𝜏] ∈ [𝜋′′] (cid:1) [𝜎′′]. This is true if 𝑖 − 1 and

𝑖 are not cyclically adjacent since 𝑖 − 1 and 𝑖 have been swapped in all three cyclic permutations

involved. If they are adjacent then the relative order of the elements of [𝜏] corresponding to [𝜋]

17

and [𝜋′′] are the same, and similarly for [𝜎] and [𝜎′′]. So leaving [𝜏] fixed again gives a shuffle

in the range.

Finally, we need to verify that 𝑇𝑖 is cst preserving. Since cst is a cyclic descent statistic, it

suffices to show that 𝑇𝑖 is cDes preserving. Certainly this is true of [𝜏] is fixed. And if it is not,

then 𝑖 − 1, 𝑖 are not cyclically adjacent in [𝜏]. But switching 𝑖 − 1 and 𝑖 could only change a cyclic

descent into a cyclic ascent or vice-versa if these two elements were adjacent. So in this case

cDes[(𝑖 − 1, 𝑖)𝜏] = cDes[𝜏] and we are done.

□

Example 3.1.3. As an example of the map 𝑇𝑖, consider the shuffle set in (1.2.1). Here we can take

𝑖 = 4 since 4 ∈ 14 and 3 ∈ 23. For [𝜏] = [1342] we have 3 and 4 cyclically adjacent so

𝑇4 [1342] = [1342] ∈ [13] (cid:1) [24]

as desired. On the other hand, in [1324] the 3 and 4 are not cyclically adjacent so

𝑇4 [1324] = [1423].

Note that [1423] ∈ [13] (cid:1) [24] and

cDes[1423] = {{ {1, 2}, {2, 3}, {3, 4}, {1, 4} }} = cDes[1324].

We can use the previous lemma to drastically cut down on the number of cases which need

to be checked to obtain cyclic shuffle-compatibility. In particular, the component permutations in

the shuffles to be considered can be on consecutive intervals of integers. And one can keep one

component of the shuffle constant while the other varies.

Corollary 3.1.4. Suppose that cst is cyclic descent statistic. The following are equivalent.

(a) The cyclic statistic cst is cyclic shuffle-compatible.

(b) If cst( [𝜋]) = cst([𝜋′]) where [𝜋], [𝜋′] ∈ 𝐶 [𝑚] and [𝜎] ∈ 𝐶 ( [𝑛] + 𝑚) for some 𝑚, 𝑛 ∈ N

then

cst([𝜋] (cid:1) [𝜎]) = cst( [𝜋′] (cid:1) [𝜎]).

18

(c) If cst( [𝜎]) = cst([𝜎′]) where [𝜎], [𝜎′] ∈ 𝐶 ( [𝑛] + 𝑚) and [𝜋] ∈ 𝐶 [𝑚] for some 𝑚, 𝑛 ∈ N

then

cst([𝜋] (cid:1) [𝜎]) = cst( [𝜋] (cid:1) [𝜎′]).

Proof. We will prove the equivalence of (a) and (b) since the equivalence of (a) and (c) is similar.

Clearly (a) implies (b). For the converse, let 𝜋, 𝜋′, 𝜎, 𝜎′ be any four permutations satisfying the

hypothesis of the cyclic shuffle-compatible definition and let 𝑚 = |𝜋| = |𝜋′|, 𝑛 = |𝜎| = |𝜎′|.

Also let 𝐴 = [𝑚], 𝐵 = [𝑛] + 𝑚, 𝐴′ = [𝑚] + 𝑛, and 𝐵′ = [𝑛]. Then, using Lemma 3.1.2 and (b)

alternately

cst([𝜋] (cid:1) [𝜎]) = cst(std𝐴 [𝜋] (cid:1) std𝐵 [𝜎])

= cst(std𝐴 [𝜋′] (cid:1) std𝐵 [𝜎])

= cst(std𝐴′ [𝜋′] (cid:1) std𝐵′ [𝜎])

= cst(std𝐴′ [𝜋′] (cid:1) std𝐵′ [𝜎′])

= cst( [𝜋′] (cid:1) [𝜎′])

which is what we wished to prove.

□

In order to prove the Lifting Lemma, we will need to define two functions.

Definition 3.1.5 (Splitting map). For 𝑖 ∈ [𝑛] we construct the splitting map 𝑆𝑖 : 𝐶 [𝑛] → 𝐿 [𝑛] as

follows. If [𝜋] ∈ 𝐶 [𝑛] then let 𝑆𝑖 [𝜋] be the unique linear permutation in [𝜋] which starts with 𝑖.

For example,

𝑆3 [45132] = 32451.

Definition 3.1.6 (Maximum removal map). Define the maximum removal map 𝑀 : 𝐶 [𝑛] →

𝐿 [𝑛 − 1] by first applying 𝑆𝑛 to [𝜋] and then removing the initial 𝑛.

To illustrate

𝑀 [45132] = 1324.

19

Note that 𝑀 is a bijection. We similarly define 𝑀 : 𝐶 ( [𝑛] + 𝑚) → 𝐿 ( [𝑛 − 1] + 𝑚) using 𝑚 + 𝑛 in

place of 𝑛, as in

𝑀 [67354] = 3546.

Finally, we say that 𝑦 is between 𝑥 and 𝑧 in [𝜋] if this is true of any linear permutation in [𝜋]

where 𝑥 occurs to the left of 𝑧. If [𝜋] ∈ 𝐶 [𝑚], 𝑖 ∈ [𝑚], and [𝜎] ∈ 𝐶 ( [𝑛] + 𝑚) define

[𝜋] (cid:1)𝑖 [𝜎] = {[𝜏] ∈ [𝜋] (cid:1) [𝜎] | only elements of 𝜎 are between 𝑚 + 𝑛 and 𝑖 in [𝜏]}.

For example,

with

and

[12] (cid:1) [34] = {[1234], [1243], [1324], [1423], [1342], [1432]}

[12] (cid:1)1 [34] = {[1234], [1243], [1324]}

[12] (cid:1)2 [34] = {[1423], [1342], [1432]}.

Clearly [𝜋] (cid:1) [𝜎] is the disjoint union of the [𝜋] (cid:1)𝑖 [𝜎] for 𝑖 ∈ [𝑚].

Lemma 3.1.7 (Lifting Lemma). Let cst be a cyclic descent statistic and st be a shuffle-compatible

linear descent statistic such that the following conditions hold.

(a) For any [𝜏], [𝜏′] of the same length

st(𝑀 [𝜏]) = st(𝑀 [𝜏′])

implies

cst[𝜏] = cst[𝜏′].

(b) Given any [𝜋], [𝜋′] ∈ 𝐶 [𝑚] such that cst[𝜋] = cst[𝜋′], there exists a bijection 𝑓 : [𝑚] → [𝑚]

such that for all 𝑖 and 𝑗 = 𝑓 (𝑖)

Then cst is cyclic shuffle-compatible.

st(𝑆𝑖 [𝜋]) = st(𝑆 𝑗 [𝜋′]).

20

Proof. By Corollary 3.1.4, it suffices to show that if [𝜋], [𝜋′] are as given in (b) and 𝜎 ∈ 𝐶 ( [𝑛] + 𝑚)

then cst([𝜋] (cid:1) [𝜎]) = cst([𝜋′] (cid:1) [𝜎]). The remarks preceding the lemma show that this reduces

to proving

for all 𝑖 ∈ [𝑚] and 𝑗 = 𝑓 (𝑖).

cst([𝜋] (cid:1)𝑖 [𝜎]) = cst( [𝜋′] (cid:1) 𝑗 [𝜎])

(3.1.1)

It follows that st(𝑆𝑖 [𝜋]) = st(𝑆 𝑗 [𝜋′]) by (b). So, since st is shuffle compatible, we have

st(𝑆𝑖 [𝜋] (cid:1) 𝜎′) = st(𝑆 𝑗 [𝜋′] (cid:1) 𝜎′) where 𝜎′ = 𝑀 [𝜎]. Thus there is an st-preserving bijection

𝜃 : 𝑆𝑖 [𝜋] (cid:1) 𝜎′ → 𝑆 𝑗 [𝜋′] (cid:1) 𝜎′.

This gives rise to a map

𝜃′ : [𝜋] (cid:1)𝑖 [𝜎]

𝑀

→ 𝑆𝑖 [𝜋] (cid:1) 𝜎′ 𝜃

→ 𝑆 𝑗 [𝜋′] (cid:1) 𝜎′ 𝑀 −1

→ [𝜋′] (cid:1) 𝑗 [𝜎]

Since this is a bijection, to show (3.1.1) it suffices to prove that 𝜃′ is cst-preserving. So take

[𝜏] ∈ [𝜋] (cid:1)𝑖 [𝜎] and [𝜏′] = 𝜃′[𝜏]. Then 𝑀 [𝜏′] = 𝜃 ◦ 𝑀 [𝜏]. Since 𝜃 is st preserving, we have

st 𝑀 [𝜏′] = st 𝑀 [𝜏]. But then hypothesis (a) implies that cst[𝜏] = cst[𝜏′] which is what we wished

to prove.

3.2 Applications

□

The hypotheses in the Lifting Lemma may seem strange at first glance, yet they can be quite

easy to verify, making it a useful tool. We will see four instances of this by proving the cyclic

shuffle-compatibility of cyclic statistics cDes, cdes, cPk and cpk using its aid.

Theorem 3.2.1. The cyclic statistic cDes is cyclic shuffle-compatible.

Proof. We will verify the hypotheses of Lemma 3.1.7 using st = Des. For (a), suppose that

|𝜏| = |𝜏′| = 𝑛 and

Des(𝑀 [𝜏]) = Des(𝑀 [𝜏′]).

(3.2.1)

Let us assume that 𝜏, 𝜏′ were chosen from their cyclic equivalence class so that 𝜏1 = max 𝜏 and

similarly for 𝜏′. Then 𝑀 [𝜏] = 𝜏2𝜏3 . . . 𝜏𝑛. And by the choice of 𝜏1 we see that

Des 𝜏 = {1} ⊎ (Des 𝑀 [𝜏] + 1).

(3.2.2)

21

Since the same statement holds with 𝜏′ in place of 𝜏 and (3.2.1) holds, we have Des 𝜏 = Des 𝜏′.

But Des 𝜏 is one set in the multiset cDes[𝜏], and the others are gotten by adding each 𝑖 ∈ [𝑛] to all

elements of Des 𝜏 modulo 𝑛. The same being true of cDes[𝜏′] shows that cDes[𝜏] = cDes[𝜏′] as

desired.

For (b), we are given [𝜋], [𝜋′] ∈ 𝐶 [𝑚] with cDes[𝜋] = cDes[𝜋′] and must construct the

necessary bijection. From this assumption, we can choose 𝜋 and 𝜋′ such that

cDes 𝜋 = cDes 𝜋′ = 𝐴.

(3.2.3)

for some set 𝐴. Define 𝑓 : [𝑚] → [𝑚] by 𝑓 (𝜋𝑘 ) = 𝜋′

𝑘 for all 𝑘 ∈ [𝑚]. Let 𝑖 = 𝜋𝑘 and 𝑗 = 𝜋′

𝑘 . To

show that Des(𝑆𝑖 [𝜋]) = Des(𝑆 𝑗 [𝜋′]) there are two cases depending on whether 𝑘 − 1 ∈ 𝐴 or not,

where 𝑘 − 1 is taken modulo 𝑚.

If 𝑘 − 1 ∉ 𝐴 then 𝜋𝑘 , 𝜋′

𝑘 are not the second elements in cyclic descents of their respective

permutations. From this and equation (3.2.3) it follows that

Des(𝑆𝑖 [𝜋]) = 𝐴 − 𝑘 + 1 = Des(𝑆 𝑗 [𝜋′]).

If 𝑘 − 1 ∈ 𝐴 then the same equalities hold with 𝐴 replaced by 𝐴′ which is 𝐴 with 𝑘 − 1 removed.

The completes the proof of (b) and of the theorem.

□

Theorem 3.2.2. The cyclic statistic cdes is cyclic shuffle-compatible.

Proof. We proceed as in the previous proof with st = des. For (a) we assume des(𝑀 [𝜏]) =

des(𝑀 [𝜏′]). But from equation (3.2.2) we see that des 𝜏 = des(𝑀 [𝜏]) − 1 and the same is true

for 𝜏′. Combining this with our initial assumption gives des 𝜏 = des 𝜏′. But 𝜏, 𝜏′ begin with their

largest element so that

cdes[𝜏] = des 𝜏 = des 𝜏′ = cdes[𝜏′]

which is what we wished to show.

To prove (b), we are given cdes[𝜋] = cdes[𝜋′]. As in the preceding paragraph, choose 𝜋, 𝜋′ to

begin with their largest elements so that cdes[𝜋] = des 𝜋 and similarly for 𝜋′. Since des 𝜋 = des 𝜋′

there is a bijection 𝜃 : Des 𝜋 → Des 𝜋′. Extend this map to 𝜃 : [𝑚] → [𝑚] by using any bijection

22

between the complements of Des 𝜋 and Des 𝜋′. The proof that 𝜃 has the desired property is now

similar to that for Des and so is left to the reader.

□

Theorem 3.2.3. The cyclic statistic cPk is cyclic shuffle-compatible.

Proof. This proof parallels the one for cDes, so we will only mention the highlights. For (a) one

sees that Pk 𝜏 = Pk 𝑀 [𝜏] + 1 since 𝜏1 = max 𝜏 is not a peak in 𝜏 and is removed in 𝑀 [𝜏]. But this

still implies that Pk 𝜏 = Pk 𝜏′ and the rest of this part of the demonstration goes through.

For (b), the map 𝜃 is constructed in exactly the same way using 𝐴 = cPk 𝜋 = cPk 𝜋′. The

only difference with the remaining part of the proof is that there are two subcases when 𝑘 − 1 ∉ 𝐴

depending on whether 𝑘 − 2 ∈ 𝐴 or not. If 𝑘 − 2 ∈ 𝐴 then one loses the peak which was at 𝜋𝑘−2 in

𝑆𝑖 [𝜋]. On the other hand, the peak set stays the same modulo rotation if 𝑘 − 2 ∉ 𝐴. But since the

analogous statements hold for 𝜋′, the manipulations in these subcases are as before.

□

The proof of the next result is based on the proof of Theorem 3.2.3 in much the same way that

the demonstrations of Theorems 3.2.1 and 3.2.2 are related. So the details are left to the reader.

Theorem 3.2.4. The cyclic statistic cpk is cyclic shuffle-compatible.

□

Lest it appear that cyclic shuffle-compatibility follows exactly the same lines as the linear case,

let us point out a place where they differ.

Definition 3.2.5. A birun of 𝜋 is a maximal monotone factor (subsequence of consecutive elements).

Let bru 𝜋 be the number of biruns of 𝜋.

For example, bru 125346 = 3 because of the biruns 125, 53, and 346. It is easy to see [GZ18] that

the birun statistic is not linearly shuffle-compatible. A cyclic birun of [𝜋] is defined in the obvious

manner and denoted cbru[𝜋]. Returning to our example, cbru[125346] = 4 because of the biruns

above and 61.

Theorem 3.2.6. The cyclic statistic cbru is cyclic shuffle-compatible.

23

Proof. Clearly cyclic biruns always begin at a cyclic peak and end at a cyclic valley, or vice-versa.

So cbru[𝜋] = 2 cpk[𝜋] and the result follows from Theorem 3.2.4.

□

24

CHAPTER 4

CYCLIC SHUFFLE-COMPATIBILITY: ALGEBRAICALLY

In Section 4.1, we review Gessel and Zhuang’s definition of the shuffle algebra of a shuffle-

compatible permutation statistic, and then we define the cyclic shuffle algebra of a cyclic shuffle-

compatible statistic. We prove several general results about cyclic shuffle-compatibility via cyclic

shuffle algebras, including a result (Theorem 4.1.13) allowing one to construct cyclic shuffle algebras

from linear ones.

In Section 4.2, we review the role of quasisymmetric functions in the theory of (linear) shuffle-

compatibility, and then we develop an analogous theory concerning cyclic quasisymmetric functions

and cyclic shuffle-compatibility. We use Theorem 4.1.13 to construct the non-Escher subalgebra

cQSym− of cyclic quasisymmetric functions from the algebra QSym of quasisymmetric functions,

which gives another proof that cDes is cyclic shuffle-compatible and shows that the cyclic shuffle

algebra of cDes is isomorphic to cQSym−. We then give a necessary and sufficient condition

for cyclic shuffle-compatibility of cyclic descent statistics which implies that the cyclic shuffle

algebra of any cyclic shuffle-compatible cyclic descent statistic is isomorphic to a quotient algebra

of cQSym−.

In Section 4.3, we use the theory developed in Section 4.2 to give explicit descriptions of the

cyclic shuffle algebras of the statistics cPk, cpk cdes, and (cpk, cdes) which in turn yields algebraic

proofs for their cyclic shuffle-compatibility.

In Section 4.4, we define a family of multiset-valued cyclic statistics induced from linear

statistics, and investigate cyclic shuffle-compatibility for some of these statistics. This approach

yields a definition of a cyclic major index which is different from the one proposed earlier by Ji

and Zhang [JZ22]; unfortunately, neither of these cyclic major index statistics are cyclic shuffle-

compatible.

4.1 Cyclic Shuffle Algebras

At the heart of Gessel and Zhuang’s algebraic framework for shuffle-compatibility is the notion

of a shuffle algebra. In this section, we review the definition of the shuffle algebra of a shuffle-

25

compatible (linear) permutation statistic, define a cyclic analogue of shuffle algebras for cyclic

shuffle-compatible statistics, and prove several general results about cyclic shuffle-compatibility

through cyclic shuffle algebras, including one that can be used to construct cyclic shuffle algebras

from shuffle algebras of linear permutation statistics.

4.1.1 Definitions

Definition 4.1.1 (st-equivalent). Let st be a linear permutation statistic. We say that 𝜋 and 𝜎 are

st-equivalent if st 𝜋 = st 𝜎 and |𝜋| = |𝜎|.

In this way, every permutation statistic induces an equivalence relation on permutations, and we

write the st-equivalence class of 𝜋 as 𝜋st. Let Ast denote the Q-vector space consisting of formal

linear combinations of st-equivalence classes of permutations.

If st is shuffle-compatible, then we can turn Ast into a Q-algebra by endowing it with the

multiplication

𝜋st𝜎st =

∑︁

𝜏st

𝜏∈𝜋(cid:1)𝜎

for any disjoint representatives 𝜋 ∈ 𝜋st and 𝜎 ∈ 𝜎st; this multiplication is well-defined (i.e., the

choice of 𝜋 and 𝜎 does not matter) precisely when st is shuffle compatible. The Q-algebra Ast is

called the (linear) shuffle algebra of st. Observe that Ast is graded by length, that is, 𝜋st belongs to

the 𝑛th homogeneous component of Ast if 𝜋 has length 𝑛.

Our definition of cyclic shuffle algebras will be analogous to that of linear ones.

Definition 4.1.2 (cst-equivalent). Let cst be a cyclic permutation statistic. Then the cyclic per-

mutations [𝜋] and [𝜎] are called cst-equivalent if cst[𝜋] = cst[𝜎] and |𝜋| = |𝜎|, and we use the

notation [𝜋]cst to denote the cst-equivalence class of the cyclic permutation [𝜋].

We associate to cst a Q-vector space Acyc

cst by taking as a basis the set of all cst-equivalence classes

of permutations, and then we give this vector space a multiplication by defining

[𝜋]cst [𝜎]cst =

∑︁

[𝜏]cst

[𝜏]∈[𝜋](cid:1)[𝜎]

26

for any disjoint 𝜋 and 𝜎 with [𝜋] ∈ [𝜋]cst and [𝜎] ∈ [𝜎]cst; this multiplication is well-defined if
and only if cst is cyclic shuffle-compatible. The resulting Q-algebra Acyc

cst is called the cyclic shuffle

algebra of cst, and is also graded by length.

4.1.2 Two General Results on Cyclic Shuffle Algebras

We now give two general results on cyclic shuffle algebras, which are analogous to Theorems

3.2 and 3.3 of [GZ18] on linear shuffle algebras. We provide proofs for completeness, although

they follow in essentially the same way as the proofs of the corresponding results in [GZ18].

Theorem 4.1.3. Suppose that cst1 is cyclic shuffle-compatible and is a refinement of cst2. Let 𝐴 be

a Q-algebra with basis {𝑣𝛼} indexed by cst2-equivalence classes 𝛼, and suppose that there exists
a Q-algebra homomorphism 𝜙 : Acyc
cst1

→ 𝐴 such that for every cst1-equivalence class 𝛽, we have

𝜙(𝛽) = 𝑣𝛼 where 𝛼 is the cst2-equivalence class containing 𝛽. Then cst2 is cyclic shuffle-compatible
and the map 𝑣𝛼 ↦→ 𝛼 extends by linearity to an isomorphism from 𝐴 to Acyc
cst2

.

Proof. It suffices to show that for any disjoint 𝜋 and 𝜎, we have

To that end, we have

𝑣 [𝜋]cst2

𝑣 [𝜎]cst2

=

∑︁

[𝜏]∈[𝜋](cid:1)[𝜎]

𝑣 [𝜏]cst2

.

𝑣 [𝜋]cst2

𝑣 [𝜎]cst2

= 𝜙( [𝜋]cst1)𝜙( [𝜎]cst1)

= 𝜙( [𝜋]cst1 [𝜎]cst1)

(cid:32)

= 𝜙

∑︁

(cid:33)

[𝜏]cst1

[𝜏]∈[𝜋](cid:1)[𝜎]
∑︁

𝑣 [𝜏]cst2

,

[𝜏]∈[𝜋](cid:1)[𝜎]

=

which completes the proof.

□

We say that cst1 and cst2 are equivalent if cst1 is a simultaneously a refinement and a coarsening

of cst2, that is, if for all cyclic permutations [𝜋] and [𝜎] of the same length, cst1 [𝜋] = cst1 [𝜎]

implies cst2 [𝜋] = cst2 [𝜎] and vice versa.

27

Theorem 4.1.4. Let cst1 and cst2 be equivalent statistics. If cst1 is shuffle-compatible with cyclic
, then cst2 is also cyclic shuffle-compatible with cyclic shuffle algebra Acyc
shuffle algebra Acyc
cst1
cst2
isomorphic to Acyc
cst1

.

Proof. Because equivalent statistics have the same equivalence classes on cyclic permutations, we

know that Acyc
cst1

and Acyc
cst2

have the same basis elements. Since cst1 and cst2 are equivalent, we have

[𝜋]st2 [𝜎]st2 = [𝜋]st1 [𝜎]st1 =

∑︁

[𝜏]st1 =

∑︁

[𝜏]st2

,

[𝜏]∈[𝜋](cid:1)[𝜎]

[𝜏]∈[𝜋](cid:1)[𝜎]

which proves the result.

□

4.1.3 Symmetries and Cyclic Shuffle Algebras

Many permutation statistics—both linear and cyclic—are related via various symmetries,

such as reversal, complementation, and reverse-complementation. For a linear permutation
𝜋 = 𝜋1𝜋2 · · · 𝜋𝑛 ∈ 𝔖𝑛, we define the reversal 𝜋𝑟 of 𝜋 by 𝜋𝑟 (cid:66) 𝜋𝑛𝜋𝑛−1 · · · 𝜋1, the complement
𝜋𝑐 of 𝜋 to be the permutation obtained by (simultaneously) replacing the 𝑖th smallest letter in

𝜋 with the 𝑖th largest letter in 𝜋 for all 1 ≤ 𝑖 ≤ 𝑛, and the reverse-complement 𝜋𝑟𝑐 of 𝜋 by

𝜋𝑟𝑐 (cid:66) (𝜋𝑟)𝑐 = (𝜋𝑐)𝑟. For example, given 𝜋 = 318269, we have 𝜋𝑟 = 962813, 𝜋𝑐 = 692831, and

𝜋𝑟𝑐 = 138296.

More generally, let 𝑓 be an involution on linear permutations which preserves the length, i.e.,

| 𝑓 (𝜋)| = |𝜋| for all 𝜋. We shall write 𝜋 𝑓 in place of 𝑓 (𝜋). For a set Π of permutations, let

Π 𝑓 (cid:66) { 𝜋 𝑓 : 𝜋 ∈ Π },

so 𝑓 induces an involution on sets of permutations as well. In particular, this lets us define [𝜋] 𝑓

for a cyclic permutation [𝜋]. Going further, if 𝐶 is a set of cyclic permutations, then

𝐶 𝑓 (cid:66) { [𝜋] 𝑓 : [𝜋] ∈ 𝐶 }.

Following Gessel and Zhuang [GZ18],

Definition 4.1.5 (Shuffle-compatibility-preserving). We say that 𝑓 is shuffle-compatibility-preserving

if for any pair of disjoint permutations 𝜋 and 𝜎, there exist disjoint permutations ˆ𝜋 and ˆ𝜎 with the

same relative order as 𝜋 and 𝜎, respectively, such that (𝜋(cid:1)𝜎) 𝑓 = ˆ𝜋 𝑓 (cid:1) ˆ𝜎 𝑓 and ( ˆ𝜋(cid:1) ˆ𝜎) 𝑓 = 𝜋 𝑓 (cid:1)𝜎 𝑓 .

28

This definition implies that 𝜋 𝑓 and 𝜎 𝑓 are disjoint, and similarly with ˆ𝜋 𝑓 and ˆ𝜎 𝑓 .

Definition 4.1.6 ( 𝑓 -equivalent). Two linear permutation statistics st1 and st2 are called 𝑓 -equivalent
if st1 ◦ 𝑓 is equivalent to st2—that is, st1 𝜋 𝑓 = st1 𝜎 𝑓 if and only if st2 𝜋 = st2 𝜎. In other words, st1
and st2 are 𝑓 -equivalent if and only if (𝜋 𝑓 )st1 = (𝜋st2) 𝑓 for all 𝜋.

It is easy to see that, if st1 𝜋 𝑓 = st2 𝜋 for all 𝜋, then st1 and st2 are 𝑓 -equivalent (although this is not

a necessary condition).

Example 4.1.7. For example, the peak set Pk is 𝑐-equivalent to the valley set Val defined in the

following way. We call 𝑖 ∈ {2, 3, . . . , 𝑛 − 1} a valley of 𝜋 ∈ 𝔖𝑛 if 𝜋𝑖−1 > 𝜋𝑖 < 𝜋𝑖+1, and we let

Val 𝜋 be the set of valleys of 𝜋. We also define val 𝜋 to be the number of valleys of 𝜋; then, pk and

val are 𝑐-equivalent as well.

Despite its name,

𝑓 -equivalence is not an equivalence relation (although it is symmetric).

However, it turns out that if the statistics involved are shuffle-compatible, then 𝑓 -equivalences

induce isomorphisms on the corresponding shuffle algebras. This idea is expressed in the following

theorem of Gessel and Zhuang.

Theorem 4.1.8 ([GZ18] Theorem 3.5). Let 𝑓 be shuffle-compatibility-preserving, and suppose that

st1 and st2 are 𝑓 -equivalent (linear) permutation statistics. If st1 is shuffle-compatible with shuffle
algebra Ast1, then st2 is also shuffle-compatible, and the linear map defined by 𝜋st1 ↦→ 𝜋 𝑓
Q-algebra isomorphism between their shuffle algebras Ast1 and Ast2.

is a

st2

Gessel and Zhuang proved that reversal, complementation, and reverse-complementation are all

shuffle-compatibility-preserving. Thus, they were able to use Theorem 4.1.8 to prove a collection

of shuffle-compatibility results for statistics that are 𝑟-, 𝑐-, or 𝑟𝑐-equivalent to another statistic

whose shuffle-compatibility had already been established. For example, it follows from the shuffle-

compatibility of the peak set Pk that the valley set Val is shuffle-compatible with shuffle algebra

AVal isomorphic to APk.

Moving onto the cyclic setting, we call 𝑓 rotation-preserving if [𝜋] 𝑓 = [𝜋 𝑓 ] for all 𝜋.

29

Lemma 4.1.9. If 𝑓 is shuffle-compatibility-preserving and rotation-preserving, then for any pair of

disjoint permutations 𝜋 and 𝜎, there exist disjoint permutations ˆ𝜋 and ˆ𝜎 with the same relative order

as 𝜋 and 𝜎, respectively, for which ([𝜋] (cid:1) [𝜎]) 𝑓 = [ ˆ𝜋 𝑓 ] (cid:1) [ ˆ𝜎 𝑓 ] and ( [ ˆ𝜋] (cid:1) [ ˆ𝜎]) 𝑓 = [𝜋 𝑓 ] (cid:1) [𝜎 𝑓 ].

Proof. Let [𝜏] ∈ [𝜋] (cid:1) [𝜎], so that 𝜏 ∈ ¯𝜋 (cid:1) ¯𝜎 for some ¯𝜋 ∈ [𝜋] and ¯𝜎 ∈ [𝜎], and thus

𝜏 𝑓 ∈ ( ¯𝜋 (cid:1) ¯𝜎) 𝑓 . Since 𝑓 is shuffle-compatibility-preserving, we have that 𝜏 𝑓 ∈ ˆ¯𝜋 𝑓 (cid:1) ˆ¯𝜎 𝑓 where

ˆ¯𝜋 and ˆ¯𝜎 are disjoint permutations with the same relative order as ¯𝜋 and ¯𝜎, respectively. Since

¯𝜋 is a rotation of 𝜋 and ˆ¯𝜋 has the same relative order as ¯𝜋, it follows that ˆ¯𝜋 is a rotation of a

permutation ˆ𝜋 with the same relative order as 𝜋, and similarly ˆ¯𝜎 is a rotation of a permutation

ˆ𝜎 with the same relative order as 𝜎. Clearly, ˆ𝜋 and ˆ𝜎 are disjoint because ˆ¯𝜋 and ˆ¯𝜎 are disjoint.

Because 𝑓 is rotation-preserving, ˆ¯𝜋 ∈ [ ˆ𝜋] and ˆ¯𝜎 ∈ [ ˆ𝜎] imply ˆ¯𝜋 𝑓 ∈ [ ˆ𝜋 𝑓 ] and ˆ¯𝜎 ∈ [ ˆ𝜎 𝑓 ]. Therefore,

𝜏 𝑓 ∈ ˆ¯𝜋 𝑓 (cid:1) ˆ¯𝜎 𝑓 implies [𝜏] 𝑓 = [𝜏 𝑓 ] ∈ [ ˆ𝜋 𝑓 ] (cid:1) [ ˆ𝜎 𝑓 ].

We have shown that ([𝜋] (cid:1) [𝜎]) 𝑓 is a subset of [ ˆ𝜋 𝑓 ] (cid:1) [ ˆ𝜎 𝑓 ], but since these two sets have the

same cardinality, they are in fact equal. We omit the proof of ( [ ˆ𝜋] (cid:1) [ ˆ𝜎]) 𝑓 = [𝜋 𝑓 ] (cid:1) [𝜎 𝑓 ] as it is

similar.

□

Lemma 4.1.10. Reversal, complementation, and reverse-complementation are all rotation-preserving.

Proof. Let 𝜋 = 𝜋1𝜋2 · · · 𝜋𝑛 be a (linear) permutation. We have

[𝜋]𝑟 = {𝜋1𝜋2 · · · 𝜋𝑛, 𝜋𝑛𝜋1 · · · 𝜋𝑛−1, . . . , 𝜋2 · · · 𝜋𝑛𝜋1}𝑟

= {𝜋𝑛 · · · 𝜋2𝜋1, 𝜋𝑛−1 · · · 𝜋1𝜋𝑛, . . . , 𝜋1𝜋𝑛 · · · 𝜋2}

= [𝜋𝑟],

so reversal is rotation-preserving. Moreover, it is clear that taking the complement of the per-

mutation 𝜋𝑖+1 · · · 𝜋𝑛𝜋1 · · · 𝜋𝑖 (obtained by rotating the last 𝑛 − 𝑖 letters of 𝜋 to the front) yields
the same result as first taking the complement of 𝜋 and then rotating the last 𝑛 − 𝑖 letters of 𝜋𝑐

to the front, so complementation is rotation-preserving. Lastly, since we have established that

[𝜋𝑐] = [𝜋]𝑐 for all permutations 𝜋, we can replace 𝜋 by 𝜋𝑟 to obtain [𝜋𝑟𝑐] = [𝜋𝑟]𝑐 = [𝜋]𝑟𝑐, so

reverse-complementation is rotation-preserving as well.

□

30

In analogy with 𝑓 -equivalence of linear permutation statistics, let us call two cyclic permutation
statistics cst1 and cst2 𝑓 -equivalent if cst1 ◦ 𝑓 is equivalent to cst2, or equivalently, if [𝜋 𝑓 ]cst1 =
([𝜋]cst2) 𝑓 . The following is a cyclic version of Theorem 4.1.8.

Theorem 4.1.11. Let 𝑓 be shuffle-compatibility-preserving and rotation-preserving, and let cst1

and cst2 be 𝑓 -equivalent cyclic permutation statistics. If cst1 is cyclic shuffle-compatible, then cst2
isomorphic to Acyc
is cyclic shuffle-compatible with Acyc
cst1
cst2

.

Proof. Let [𝜋] and [ ˜𝜋] be cyclic permutations in the same cst2-equivalence class, and similarly

with [𝜎] and [ ˜𝜎], such that 𝜋 and 𝜎 are disjoint and ˜𝜋 and ˜𝜎 are disjoint. We know from

Lemma 4.1.9 that there exist permutations ˆ𝜋, ˆ𝜎, ˆ˜𝜋, and ˆ˜𝜎—having the same relative order as 𝜋, 𝜎,

˜𝜋, and ˜𝜎, respectively—satisfying ([𝜋] (cid:1) [𝜎]) 𝑓 = [ ˆ𝜋 𝑓 ] (cid:1) [ ˆ𝜎 𝑓 ], ( [ ˆ𝜋] (cid:1) [ ˆ𝜎]) 𝑓 = [𝜋 𝑓 ] (cid:1) [𝜎 𝑓 ],

([ ˜𝜋] (cid:1) [ ˜𝜎]) 𝑓 = [ ˆ˜𝜋 𝑓 ] (cid:1) [ ˆ˜𝜎 𝑓 ], and ([ ˆ˜𝜋] (cid:1) [ ˆ˜𝜎]) 𝑓 = [ ˜𝜋 𝑓 ] (cid:1) [ ˜𝜎 𝑓 ].

Because ˆ𝜋 and ˆ˜𝜋 have the same relative order as 𝜋 and ˜𝜋, respectively, we have

[ ˆ𝜋]cst2 = [𝜋]cst2 = [ ˜𝜋]cst2 = [ ˆ˜𝜋]cst2

.

Then, because cst1 and cst2 are 𝑓 -equivalent, we have

[ ˆ𝜋 𝑓 ]cst1 = ([ ˆ𝜋]cst2) 𝑓 = ( [ ˆ˜𝜋]cst2) 𝑓 = [ ˆ˜𝜋 𝑓 ]cst1

,

so [ ˆ𝜋 𝑓 ] and [ ˆ˜𝜋 𝑓 ] are cst1-equivalent. The same reasoning shows that [ ˆ𝜎 𝑓 ] and [ ˆ˜𝜎 𝑓 ] are also

cst1-equivalent.

By cyclic shuffle-compatibility of cst1, we have the multiset equality

{{ cst1 [𝜏] : [𝜏] ∈ [ ˆ𝜋 𝑓 ] (cid:1) [ ˆ𝜎 𝑓 ] }} = {{ cst1 [𝜏] : [𝜏] ∈ [ ˆ˜𝜋 𝑓 ] (cid:1) [ ˆ˜𝜎 𝑓 ] }},

which—by 𝑓 -equivalence of cst1 and cst2—is equivalent to

{{ cst2 [𝜏 𝑓 ] : [𝜏] ∈ [ ˆ𝜋 𝑓 ] (cid:1) [ ˆ𝜎 𝑓 ] }} = {{ cst2 [𝜏 𝑓 ] : [𝜏] ∈ [ ˆ˜𝜋 𝑓 ] (cid:1) [ ˆ˜𝜎 𝑓 ] }},

which is in turn equivalent to

{{ cst2 [𝜏] : [𝜏] 𝑓 ∈ [ ˆ𝜋 𝑓 ] (cid:1) [ ˆ𝜎 𝑓 ] }} = {{ cst2 [𝜏] : [𝜏] 𝑓 ∈ [ ˆ˜𝜋 𝑓 ] (cid:1) [ ˆ˜𝜎 𝑓 ] }}

31

because 𝑓

is rotation-preserving. Since ( [𝜋] (cid:1) [𝜎]) 𝑓 = [ ˆ𝜋 𝑓 ] (cid:1) [ ˆ𝜎 𝑓 ] and ( [ ˜𝜋] (cid:1) [ ˜𝜎]) 𝑓 =

[ ˆ˜𝜋 𝑓 ] (cid:1) [ ˆ˜𝜎 𝑓 ], we have

{{ cst2 [𝜏] : [𝜏] ∈ [𝜋] (cid:1) [𝜎] }} = {{ cst2 [𝜏] : [𝜏] ∈ [ ˜𝜋] (cid:1) [ ˜𝜎] }},

which shows that cst2 is cyclic shuffle-compatible.

It remains to prove that Acyc
cst2
by [𝜋]cst2 ↦→ [𝜋 𝑓 ]cst1. Observe that

is isomorphic to Acyc
cst1

. Define the linear map 𝜆 : Acyc
cst2

→ Acyc
cst1

∑︁

[𝜏]cst2 =

∑︁

[𝜏]cst2

[𝜏]∈[𝜋](cid:1)[𝜎]

[𝜏]∈[ ˆ𝜋](cid:1)[ ˆ𝜎]

because cst2 is cyclic shuffle-compatible, and thus we have

𝜆([𝜋]cst2 [𝜎]cst2) = 𝜆

(cid:16) ∑︁

[𝜏]∈[𝜋](cid:1)[𝜎]

(cid:16) ∑︁

= 𝜆

(cid:17)

(cid:17)

[𝜏]cst2

[𝜏]cst2

[𝜏]∈[ ˆ𝜋](cid:1)[ ˆ𝜎]
∑︁

[𝜏 𝑓 ]cst1

[𝜏]∈[ ˆ𝜋](cid:1)[ ˆ𝜎]
∑︁

[𝜏] 𝑓 ∈[ ˆ𝜋](cid:1)[ ˆ𝜎]
∑︁

[𝜏]cst1

[𝜏]cst1

=

=

=

[𝜏]∈[𝜋 𝑓 ](cid:1)[𝜎 𝑓 ]
= [𝜋 𝑓 ]cst1 [𝜎 𝑓 ]cst1

= 𝜆( [𝜋]cst2)𝜆( [𝜎]cst2).

Hence, 𝜆 is a Q-algebra isomorphism from Acyc
cst2

to Acyc
cst1

.

□

Corollary 4.1.12. Suppose that the cyclic permutation statistics cst1 and cst2 are 𝑟-equivalent,

𝑐-equivalent, or 𝑟𝑐-equivalent.

If cst1 is cyclic shuffle-compatible, then cst2 is cyclic shuffle-

compatible with cyclic shuffle algebra Acyc
cst2

isomorphic to Acyc
cst1

.

4.1.4 Constructing Cyclic Shuffle Algebras from Linear Ones

The following theorem—one of the main results of this paper—allows us to construct cyclic

shuffle algebras from shuffle algebras of shuffle-compatible (linear) permutation statistics.

32

Theorem 4.1.13. Let cst be a cyclic permutation statistic and let st be a shuffle-compatible (linear)

permutation statistic. Given a cyclic permutation [𝜋], let

𝑣 [𝜋] =

∑︁

¯𝜋∈[𝜋]

¯𝜋st ∈ Ast.

Suppose that 𝑣 [𝜋] = 𝑣 [𝜎] whenever [𝜋] and [𝜎] are cst-equivalent, and that {𝑣 [𝜋] } (ranging over

all cst-equivalence classes) is linearly independent. Then cst is cyclic shuffle-compatible and the
map 𝜓cst : Acyc

cst → Ast given by

𝜓cst( [𝜋]cst) = 𝑣 [𝜋]

extends linearly to a Q-algebra isomorphism from Acyc

cst to the span of {𝑣 [𝜋] }, a subalgebra of Ast.

Proof. Since 𝑣 [𝜋] = 𝑣 [𝜎] whenever [𝜋] and [𝜎] are cst-equivalent, we know that 𝜓cst is a well-
defined linear map on Acyc

cst . (We do not yet know whether Acyc

is an algebra; here we are only

cst

considering Acyc
map 𝜓cst is a vector space isomorphism from Acyc

cst as a vector space.) Furthermore, because {𝑣 [𝜋] } is linearly independent, the linear

cst to a subspace of Ast.

To show that cst is cyclic shuffle-compatible, we show that

[𝜋]cst [𝜎]cst =

∑︁

[𝜏]cst

[𝜏]∈[𝜋](cid:1)[𝜎]

is a well-defined multiplication in Acyc

cst . Let [𝜋′], [𝜋′′] ∈ [𝜋]cst and let [𝜎′], [𝜎′′] ∈ [𝜎]cst, where

𝜋′ and 𝜎′ are disjoint and so are 𝜋′′ and 𝜎′′. Then
(cid:33)

(cid:32)

𝜓cst

and similarly

∑︁

[𝜏]cst

=

∑︁

𝑣 [𝜏]

[𝜏]∈[𝜋′](cid:1)[𝜎′]

[𝜏]∈[𝜋′](cid:1)[𝜎′]
∑︁

∑︁

¯𝜏st

[𝜏]∈[𝜋′](cid:1)[𝜎′]
∑︁

∑︁

¯𝜏∈[𝜏]
∑︁

¯𝜋∈[𝜋′]

¯𝜎∈[𝜎′]

¯𝜏∈ ¯𝜋(cid:1) ¯𝜎

¯𝜏st

=

=

= 𝑣 [𝜋′]𝑣 [𝜎′]

(cid:32)

𝜓cst

∑︁

[𝜏]∈[𝜋′′](cid:1)[𝜎′′]

(cid:33)

[𝜏]cst

= 𝑣 [𝜋′′]𝑣 [𝜎′′] .

33

Since [𝜋′] and [𝜋′′] are cst-equivalent and similarly with [𝜎′] and [𝜎′′], we have

(cid:32)

𝜓cst

∑︁

[𝜏]∈[𝜋′](cid:1)[𝜎′]

(cid:33)

[𝜏]cst

= 𝑣 [𝜋′]𝑣 [𝜎′] = 𝑣 [𝜋′′]𝑣 [𝜎′′] = 𝜓cst

(cid:32)

∑︁

(cid:33)

[𝜏]cst

[𝜏]∈[𝜋′′](cid:1)[𝜎′′]

and thus

∑︁

[𝜏]cst =

∑︁

[𝜏]cst

[𝜏]∈[𝜋′](cid:1)[𝜎′]

[𝜏]∈[𝜋′′](cid:1)[𝜎′′]

due to injectivity of 𝜓cst. We have shown that the multiplication of the cyclic shuffle algebra Acyc
cst

is well-defined, and therefore cst is shuffle-compatible.

Finally, we have

𝜓cst([𝜋]cst [𝜎]cst) = 𝜓cst

(cid:32)

∑︁

(cid:33)

[𝜏]cst

[𝜏]∈[𝜋](cid:1)[𝜎]

= 𝑣 [𝜋]𝑣 [𝜎]

= 𝜓cst( [𝜋]cst)𝜓cst( [𝜎]cst),

so 𝜓cst is a Q-algebra isomorphism from Acyc

cst to the span of {𝑣 [𝜋] }.

□

4.2 Shuffle-compatibility and Quasisymmetric Functions

The focus of this section is the relationship between cyclic shuffle-compatibility and cyclic

quasisymmetric functions.

4.2.1 Backgrounds

First we recall that in the linear case, the product of two quasisymmetric functions is again

quasisymmetric. The multiplication rule for the fundamental basis is given by the following

theorem, which can be proved using 𝑃-partitions; see [Sta24, Exercise 7.93].

Theorem 4.2.1. Let 𝑚 and 𝑛 be non-negative integers, and let 𝐴 ⊆ [𝑚 − 1] and 𝐵 ⊆ [𝑛 − 1]. Then

𝐹𝑚,𝐴𝐹𝑛,𝐵 =

∑︁

𝜏∈𝜋(cid:1)𝜎

𝐹𝑚+𝑛,Des 𝜏

where 𝜋 is any permutation of length 𝑚 with descent set 𝐴 and 𝜎 is any permutation (disjoint from

𝜋) of length 𝑛 with descent set 𝐵.

34

It follows directly from this theorem that the descent set shuffle algebra ADes is isomorphic to

QSym; this is of [GZ18, Corollary 4.2].

Recall the definition of non-Escher sets from Definition 2.1.4. Let cQSym− denote the span

of {𝐹cyc

𝑛,[𝑆] } over all 𝑛 ≥ 0 and all equivalence classes [𝑆] of non-Escher subsets 𝑆 ⊆ [𝑛]. The
following theorem, proven by Adin et al. [AGRR21, Theorem 3.22], gives a multiplication rule for

the fundamental cyclic quasisymmetric functions in cQSym−, which also implies that the cyclic

descent set cDes is cyclic shuffle-compatible and has cyclic shuffle algebra isomorphic to cQSym−.

Theorem 4.2.2. Let 𝑚 and 𝑛 be non-negative integers, and let 𝐴 ⊆ [𝑚] and 𝐵 ⊆ [𝑛] be non-Escher

subsets. Then

𝐹cyc

𝑚,[ 𝐴]

𝐹cyc
𝑛,[𝐵] =

∑︁

𝐹cyc

𝑚+𝑛,cDes[𝜏]

(4.2.1)

[𝜏]∈[𝜋](cid:1)[𝜎]
where [𝜋] is any cyclic permutation of length 𝑚 with cyclic descent set [ 𝐴] and [𝜎] is any cyclic

permutation (with 𝜎 disjoint from 𝜋) of length 𝑛 with cyclic descent set [𝐵].

Adin et al. proved Theorem 4.2.2 using toric [ (cid:174)𝐷]-partitions; we now supply an alternative proof

using Theorem 4.1.13.

Proof. We know that the descent set Des is shuffle-compatible and its shuffle algebra ADes

is isomorphic to the algebra of quasisymmetric functions, QSym, through the isomorphism

𝜙Des(𝜋Des) = 𝐹|𝜋|,Des(𝜋). Then, using the notation of Theorem 4.1.13, we have

𝜙Des(𝑣 [𝜋]) = 𝜙Des

(cid:16) ∑︁

(cid:17)

=

¯𝜋Des

¯𝜋∈[𝜋]

∑︁

𝑖∈[𝑛]

𝐹𝑛,(cDes 𝜋+𝑖)∩[𝑛−1] = 𝐹cyc

𝑛,cDes[𝜋]

where 𝑛 = |𝜋|. If [𝜋] and [𝜎] are cDes-equivalent, then both 𝜙Des(𝑣 [𝜋]) and 𝜙Des(𝑣 [𝜎]) are equal to
𝐹cyc
𝑛,[𝑆] where 𝑛 = |𝜋| = |𝜎| and [𝑆] = cDes[𝜋] = cDes[𝜎], so 𝑣 [𝜋] = 𝑣 [𝜎]. The linear independence
of the 𝐹cyc
𝑛,[𝑆] can be established by showing that the monomial cyclic quasisymmetric functions

are linearly independent and expressing each 𝐹cyc

𝑛,[𝑆] in terms of monomial cyclic quasisymmetric

functions; see [AGRR21, Section 2] for details. Theorem 4.1.13 implies that cDes is cyclic shuffle-

compatible and that Acyc

cDes is isomorphic to cQSym− via the isomorphism [𝜋]cDes ↦→ 𝐹cyc

|𝜋|,cDes[𝜋],
□

from which the multiplication rule (4.2.1) follows.

35

As a direct consequence of Theorem 4.2.2, we have that cQSym− is a graded Q-subalgebra of

QSym. Adin et al. also show that the span of

{𝐹cyc
0,∅

, 𝐹cyc
1,∅

, 𝐹cyc

1,{1}} ∪ {𝐹cyc

𝑛,[𝑆] }𝑛≥2, ∅≠𝑆⊆[𝑛],

denoted cQSym, is a graded Q-subalgebra of QSym, although this result is less relevant to cyclic

shuffle-compatibility. Thus we have the subalgebra relations

cQSym− ⊆ cQSym ⊆ QSym,

and cQSym− is called the non-Escher subalgebra of cQSym.

Before moving on, let us explicitly state the cyclic shuffle-compatibility of cDes as a corollary

of the preceding theorem.

Corollary 4.2.3 (Cyclic shuffle-compatibility of cDes). The cyclic descent set cDes is cyclic

shuffle-compatible, and the linear map on Acyc

cDes defined by [𝜋]cDes ↦→ 𝐹cyc

|𝜋|,cDes[𝜋] is a Q-algebra

isomorphism from Acyc

cDes to cQSym−.

4.2.2 A General Cyclic Shuffle-compatibility Criterion for Cyclic Descent Statistics

The theorem below is [GZ18, Theorem 4.3], which provides a necessary and sufficient condition

for shuffle-compatibility of descent statistics in terms of quasisymmetric functions, and implies that

the shuffle algebra of any shuffle-compatible descent statistic is a quotient algebra of QSym.

Theorem 4.2.4. A descent statistic st is shuffle-compatible if and only if there exists a Q-algebra

homomorphism 𝜙st : QSym → 𝐴, where 𝐴 is a Q-algebra with basis {𝑢𝛼} indexed by st-equivalence

classes 𝛼 of compositions, such that 𝜙st(𝐹𝐿) = 𝑢𝛼 whenever 𝐿 ∈ 𝛼. In this case, the linear map on

Ast defined by

𝜋st ↦→ 𝑢𝛼,

where Comp 𝜋 ∈ 𝛼, is a Q-algebra isomorphism from Ast to 𝐴.

We now prove our main result of this section: a cyclic analogue of Theorem 4.2.4.

36

Theorem 4.2.5. A cyclic descent statistic cst is cyclic shuffle-compatible if and only if there exists a

Q-algebra homomorphism 𝜙cst : cQSym− → 𝐴, where 𝐴 is a Q-algebra with basis {𝑣𝛼} indexed by
cst-equivalence classes 𝛼 of non-Escher cyclic compositions, such that 𝜙cst(𝐹cyc
[𝐿] ) = 𝑣𝛼 whenever
[𝐿] ∈ 𝛼. In this case, the linear map on Acyc

cst defined by

[𝜋]cst ↦→ 𝑣𝛼,

where cComp[𝜋] ∈ 𝛼, is a Q-algebra isomorphism from Acyc

cst to 𝐴.

Proof. Suppose that the cyclic descent statistic cst is cyclic shuffle-compatible. Let 𝐴 = Acyc

cst be

the cyclic shuffle algebra of cst, and let 𝑣𝛼 = [𝜋]cst for any [𝜋] satisfying cComp[𝜋] ∈ 𝛼, so that

𝑣 𝛽𝑣𝛾 =

𝑐𝛼
𝛽,𝛾𝑣𝛼

∑︁

𝛼

where 𝑐𝛼

𝛽,𝛾 is the number of cyclic permutations with cyclic descent composition in 𝛼 that are

obtained as a cyclic shuffle of two disjoint cyclic permutations, one with cyclic descent composition

in 𝛽 and the other with cyclic descent composition in 𝛾. Observe that 𝑐𝛼

𝛽,𝛾 = (cid:205)

[𝐿]∈𝛼 𝑐𝐿

𝐽,𝐾 for any

choice of [𝐽] ∈ 𝛽 and [𝐾] ∈ 𝛾, where 𝑐𝐿

𝐽,𝐾 is the number of cyclic permutations with cyclic descent

composition [𝐿] that are obtained as a cyclic shuffle of two disjoint cyclic permutations, one with

cyclic descent composition [𝐽] and the other with cyclic descent composition [𝐾].

Define the linear map 𝜙cst : cQSym− → 𝐴 by 𝜙cst(𝐹cyc

[𝐿] ) = 𝑣𝛼 for [𝐿] ∈ 𝛼. Then any [𝐽] ∈ 𝛽

and [𝐾] ∈ 𝛾 satisfy

𝜙cst(𝐹cyc
[𝐽]

𝐹cyc
[𝐾]) = 𝜙cst

(cid:16) ∑︁

[𝐿]
∑︁

(cid:17)

𝑐𝐿
𝐽,𝐾 𝐹cyc
[𝐿]

𝑐𝐿
𝐽,𝐾 𝑣𝛼

=

=

∑︁

𝛼

[𝐿]∈𝛼

𝑐𝛼
𝛽,𝛾𝑣𝛼

∑︁

𝛼

= 𝑣 𝛽𝑣𝛾

= 𝜙cst(𝐹cyc

[𝐽] )𝜙cst(𝐹cyc
[𝐾]),

so 𝜙cst is a Q-algebra homomorphism, thus completing one direction of the proof.

37

The converse follows from Theorem 4.1.3, where we take cst1 to be cDes (which is cyclic

shuffle-compatible by Corollary 4.2.3) and cst2 to be cst.

□

Corollary 4.2.6. If cst is a cyclic shuffle-compatible descent statistic, then Acyc

cst is isomorphic to a

quotient algebra of cQSym−.

To conclude this section, we state a special case of Theorem 4.2.5 in which the homomor-

phism 𝜙cst is given in terms of the homomorphism 𝜙st of a related (linear) descent statistic; c.f.

Theorem 4.1.13. We will use this theorem to prove cyclic shuffle-compatibility results for cyclic

analogues of shuffle-compatible descent statistics.

Theorem 4.2.7. Let cst be a cyclic descent statistic and let st be a shuffle-compatible (linear)

descent statistic, so that there exists a Q-algebra homomorphism 𝜙st : QSym → 𝐴 satisfying the

conditions in Theorem 4.2.4. Define the Q-algebra homomorphism 𝜙cst : cQSym− → 𝐴 by

𝜙cst(𝐹cyc

𝑛,𝑆 ) =

∑︁

𝑖∈[𝑛]

𝜙st(𝐹𝑛,𝑆+𝑖).

𝑛,𝑆 ) = 𝜙cst(𝐹cyc

Suppose that 𝜙cst(𝐹cyc
𝑛,𝑇 ) whenever cComp[𝑆] and cComp[𝑇] are cst-equivalent cyclic
compositions—so that we can write 𝜙cst(𝐹cyc
𝑛,𝑆 ) = 𝑣𝛼 whenever cComp[𝑆] ∈ 𝛼—and suppose that
{𝑣𝛼} is linearly independent. Then cst is cyclic shuffle-compatible and the linear map on Acyc
cst

defined by

[𝜋]cst ↦→ 𝑣𝛼,

where cComp[𝜋] ∈ 𝛼, is a Q-algebra isomorphism from Acyc

cst to the span of {𝑣𝛼}, a subalgebra of

𝐴.

4.3 Characterizations of Cyclic Shuffle Algebras

Our next goal is to use the theory developed in the previous section to give explicit descriptions

of cyclic shuffle algebras. First, we will characterize the cyclic shuffle algebras of cPk, (cpk, cdes),

cpk, and cdes. This yields new proofs for the cyclic shuffle-compatibility of the statistics cPk, cpk,

and cdes, as well as the first proof for (cpk, cdes).

38

4.3.1 The Cyclic Descent Number and Cyclic Peak Number

When we characterize the (cpk, cdes) cyclic shuffle algebra, we shall need to determine all

values that the (cpk, cdes) statistic can take, which we can do with the help of two lemmas. The

first of these lemmas is Proposition 2.5 of [GZ18], so we omit its proof.

Lemma 4.3.1. Let 𝑛 ≥ 1.

(a) If 𝜋 ∈ 𝔖𝑛, then 0 ≤ pk 𝜋 ≤ ⌊(𝑛 − 1)/2⌋ and pk 𝜋 ≤ des 𝜋 ≤ 𝑛 − pk 𝜋 − 1.

(b) If 𝑗 and 𝑘 are integers satisfying 0 ≤ 𝑗 ≤ ⌊(𝑛 − 1)/2⌋ and 𝑗 ≤ 𝑘 ≤ 𝑛 − 𝑗 − 1, then there

exists 𝜋 ∈ 𝔖𝑛 with pk 𝜋 = 𝑗 and des 𝜋 = 𝑘.

Lemma 4.3.2. Let 𝑛 ≥ 2.

If 𝜋 ∈ 𝔖𝑛−1 and 𝑚 is greater than the largest letter of 𝜋, then

cpk[𝜋𝑚] = pk 𝜋 + 1 and cdes[𝜋𝑚] = des 𝜋 + 1, where 𝜋𝑚 is the permutation in 𝔖𝑛 obtained by

appending the letter 𝑚 to 𝜋.

Proof. Every peak of 𝜋 is a cyclic peak of 𝜋𝑚, and every cyclic peak of 𝜋𝑚 is either 𝑚 or a peak

of 𝜋. The same relationship is true for descents of 𝜋 and cyclic descents of 𝜋𝑚.

□

Corollary 4.3.3. Let 𝑛 ≥ 2.

(a) If 𝜋 ∈ 𝔖𝑛, then 1 ≤ cpk 𝜋 ≤ ⌊𝑛/2⌋ and cpk 𝜋 ≤ cdes 𝜋 ≤ 𝑛 − cpk 𝜋.

(b) If 𝑗 and 𝑘 are integers satisfying 1 ≤ 𝑗 ≤ ⌊𝑛/2⌋ and 𝑗 ≤ 𝑘 ≤ 𝑛 − 𝑗, then there exists 𝜋 ∈ 𝔖𝑛

with cpk 𝜋 = 𝑗 and cdes 𝜋 = 𝑘.

Proof. Fix 𝜋 ∈ 𝔖𝑛. Let 𝑚 be the largest letter of 𝜋, let ¯𝜋 be the unique representative of [𝜋] which

ends with 𝑚, and let 𝜋′ be the permutation of length 𝑛 − 1 obtained from ¯𝜋 upon removing its last

letter 𝑚. Applying Lemma 4.3.2, we obtain

cpk 𝜋 = cpk[ ¯𝜋] = pk 𝜋′ + 1

and

cdes 𝜋 = cdes[ ¯𝜋] = des 𝜋′ + 1.

Then part (a) follows from these equations and Lemma 4.3.1 (a).

39

To prove part (b), let 𝑗 and 𝑘 be integers in the specified ranges. By Lemma 4.3.1 (b), we

know there exists a permutation 𝜋′ ∈ 𝔖𝑛−1 with pk 𝜋′ = 𝑗 − 1 and des 𝜋′ = 𝑘 − 1. Let 𝑚 ∈ P be

greater than the largest letter of 𝜋′; then it follows from Lemma 4.3.2 that 𝜋𝑚 is a permutation in

𝔖𝑛 satisfying cpk 𝜋 = 𝑗 and cdes 𝜋 = 𝑘.

□

4.3.2 The Cyclic Shuffle Algebra of cPk

We will construct the cyclic shuffle algebra Acyc

cPk from the linear shuffle algebra APk. The latter
is known to be isomorphic to a subalgebra Π of QSym—introduced by Stembridge [Ste97]—called

the algebra of peaks, which is spanned by the peak quasisymmetric functions 𝐾𝑛,𝑆 where 𝑛 ranges

over all non-negative integers and 𝑆 over all possible peak sets of permutations in 𝔖𝑛. We won’t

need the precise definition of 𝐾𝑛,𝑆 here, only that the isomorphism from APk to Π sends 𝜋Pk to

𝐾|𝜋|,Pk 𝜋. We state this fact in the following theorem, which appears as Theorem 4.7 of [GZ18].

(For a detailed description of the algebra of peaks, see Section 5.1.)

Theorem 4.3.4 (Shuffle-compatibility of Pk). The peak set Pk is shuffle-compatible, and the linear

map on APk defined by 𝜋Pk ↦→ 𝐾|𝜋|,Pk 𝜋 is a Q-algebra isomorphism from APk to Π.

The analogue of Stembridge’s quasisymmetric peak functions in the cyclic setting are the cyclic

peak quasisymmetric functions 𝐾 cyc

the cyclic peak functions 𝐾 cyc

𝑛,𝑆 which will be discussed in Section 5.2.4. Here, we shall define
𝑛,𝑆 in terms of the 𝐾𝑛,𝑆. For brevity, let us say that 𝑆 is a cyclic peak set
of [𝑛] if 𝑆 is the cyclic peak set of some permutation of length 𝑛. Then, if 𝑆 is a cyclic peak set of

[𝑛], let

𝐾 cyc
𝑛,𝑆

(cid:66) ∑︁
𝑖∈[𝑛]

𝐾𝑛,(𝑆+𝑖)\{1,𝑛} =

∑︁

¯𝜋∈[𝜋]

𝐾𝑛,Pk ¯𝜋

where 𝜋 is any permutation in 𝔖𝑛 with cyclic peak set 𝑆. We can also write 𝐾 cyc
𝑛,[𝑆]

(cid:66) 𝐾 cyc

𝑛,𝑆 since

the 𝐾 cyc

𝑛,𝑆 are invariant under cyclic shift.

The following theorem gives a multiplication rule for the 𝐾 cyc

𝑛,[𝑆], which implies that cPk is cyclic

shuffle-compatible. This provides another proof different from the bijective one in Theorem 3.2.3.

40

Theorem 4.3.5. Let 𝑚 and 𝑛 be non-negative integers, let 𝐴 be a cyclic peak set of [𝑚], and let 𝐵

be a cyclic peak set of [𝑛]. Then

𝐾 cyc

𝑚,[ 𝐴]

𝐾 cyc

𝑛,[𝐵] =

∑︁

[𝜏]∈[𝜋](cid:1)[𝜎]

𝐾 cyc

𝑚+𝑛,cPk[𝜏]

(4.3.1)

where [𝜋] is any cyclic permutation of length 𝑚 with cyclic peak set [ 𝐴] and [𝜎] is any cyclic

permutation (with 𝜎 disjoint from 𝜋) of length 𝑛 with cyclic peak set [𝐵].

Proof. First, we take 𝜙Pk : QSym → Π to be the composition of the map 𝐹𝐿 ↦→ 𝜋Pk with the

map 𝜋Pk ↦→ 𝐾|𝜋|,Pk 𝜋 from Theorem 4.3.4 where 𝜋 is any permutation with Pk 𝜋 = Pk 𝐿; then 𝜙Pk

satisfies the conditions in Theorem 4.2.4.

Let 𝑆 be a non-Escher subset of [𝑛], and let [𝑃] be the cyclic peak set of any cyclic permutation

[𝜋] of length 𝑛 with cyclic descent set [𝑆]. Note that the sets 𝑆 + 𝑖 where 𝑖 ranges from 1 to 𝑛 are

precisely the descent sets of the 𝑛 linear permutations in [𝜋]. Hence, we have

𝜙cPk(𝐹cyc

𝑛,𝑆 ) =

∑︁

𝑖∈[𝑛]

𝜙Pk(𝐹𝑛,𝑆+𝑖) =

∑︁

¯𝜋∈[𝜋]

𝜙Pk(𝐹𝑛,Des ¯𝜋) =

∑︁

¯𝜋∈[𝜋]

𝐾𝑛,Pk ¯𝜋 = 𝐾 cyc
𝑛,[𝑃]

.

Clearly, 𝜙cPk(𝐹cyc
and we know that the 𝐾 cyc

𝑛,𝑆 ) depends only on the cPk-equivalence class of the cyclic composition cComp[𝑆],

cPk is cyclic shuffle-compatible and that Acyc

𝑛,[𝑃] are linearly independent. Applying Theorem 4.2.7, we conclude that
cPk is isomorphic to Λ via the isomorphism [𝜋]cPk ↦→
□

𝐾 cyc

|𝜋|,cPk[𝜋], from which the multiplication rule (4.3.1) follows.

Corollary 4.3.6 (Cyclic shuffle-compatibility of cPk). The cyclic peak set cPk is cyclic shuffle-
cPk defined by [𝜋]cPk ↦→ 𝐾 cyc

|𝜋|,cPk[𝜋] is a Q-algebra isomorphism

compatible, and the linear map on Acyc

from Acyc

cPk to Λ.

4.3.3 The Cyclic Shuffle Algebra of (cpk, cdes)

We will now use Theorem 4.2.7 to construct the cyclic shuffle algebra Acyc

(cpk,cdes) from the
linear shuffle algebra A(pk,des). We begin by recalling the following result about A(pk,des), which is

Theorem 5.9 of Gessel and Zhuang [GZ18]. Below, we will use the notation Q[[𝑡∗]] to denote the

41

Q-algebra of formal power series in 𝑡 where the multiplication is given by the Hadamard product ∗,

defined by

𝑎𝑛𝑡𝑛(cid:17)

∗

(cid:16) ∞
∑︁

𝑛=0

(cid:16) ∞
∑︁

𝑛=0

𝑏𝑛𝑡𝑛(cid:17) (cid:66)

∞
∑︁

𝑛=0

𝑎𝑛𝑏𝑛𝑡𝑛.

Theorem 4.3.7 (Shuffle-compatibility of (pk, des)).

(a) The pair (pk, des) is shuffle-compatible.

(b) Let

𝑢(pk,des)
𝑛, 𝑗,𝑘

=

𝑡 𝑗+1(𝑦 + 𝑡) 𝑘− 𝑗 (1 + 𝑦𝑡)𝑛− 𝑗−𝑘−1(1 + 𝑦)2 𝑗+1
(1 − 𝑡)𝑛+1

𝑥𝑛.

Then the linear map on A(pk,des) defined by

𝜋(pk,des) ↦→

𝑢(pk,des)
|𝜋|,pk 𝜋,des 𝜋

,

if |𝜋| ≥ 1,

1/(1 − 𝑡),

if |𝜋| = 0,





is a Q-algebra isomorphism from A(pk,des) to the span of

(cid:27) (cid:216)

(cid:26) 1
1 − 𝑡

{𝑢(pk,des)
𝑛, 𝑗,𝑘

,

}𝑛≥1,
0≤ 𝑗 ≤⌊(𝑛−1)/2⌋,
𝑗 ≤𝑘 ≤𝑛− 𝑗−1,

a subalgebra of Q[[𝑡∗]] [𝑥, 𝑦].

We note that, in the definition of 𝑢(pk,des)

𝑛, 𝑗,𝑘

, all products should be interpreted as ordinary

multiplication; the Hadamard product in 𝑡 is only used when multiplying elements in the span of
the 𝑢(pk,des)
𝑛, 𝑗,𝑘

. The same is true in Theorems 4.3.8, 4.3.9, and 4.3.10 presented later in this section.

Theorem 4.3.8 (Cyclic shuffle-compatibility of (cpk, cdes)).

(a) The pair (cpk, cdes) is cyclic shuffle-compatible.

42

(b) Let

𝑣 (cpk,cdes)
𝑛, 𝑗,𝑘

= 𝑗𝑢(pk,des)

𝑛, 𝑗−1,𝑘 + 𝑗𝑢(pk,des)
𝑛, 𝑗−1,𝑘−1

+ (𝑘 − 𝑗)𝑢(pk,des)
𝑛, 𝑗,𝑘−1

+ (𝑛 − 𝑗 − 𝑘)𝑢(pk,des)

𝑛, 𝑗,𝑘

= [ 𝑗 (𝑦 + 𝑡)(1 + 𝑦𝑡) (1 + 𝑦 + 𝑡 + 𝑦𝑡)

+ ((𝑘 − 𝑗) (1 + 𝑦𝑡) + (𝑛 − 𝑗 − 𝑘) (𝑦 + 𝑡))𝑡 (1 + 𝑦)2]

×

𝑡 𝑗 (𝑦 + 𝑡) 𝑘− 𝑗−1(1 + 𝑦𝑡)𝑛− 𝑗−𝑘−1(1 + 𝑦)2 𝑗−1
(1 − 𝑡)𝑛+1

𝑥𝑛.

Then the linear map on Acyc

(cpk,cdes) defined by




is a Q-algebra homomorphism from Acyc
(cpk,cdes) to the span of

𝑣 (cpk,cdes)
|𝜋|,cpk[𝜋],cdes[𝜋]

[𝜋] (cpk,cdes) ↦→

1/(1 − 𝑡),

,

if |𝜋| ≥ 1,

if |𝜋| = 0,

(cid:26) 1
1 − 𝑡

,

𝑡 (1 + 𝑦)
(1 − 𝑡)2

𝑥

(cid:27) (cid:216)

{𝑣 (cpk,cdes)
𝑛, 𝑗,𝑘

}𝑛≥2, 1≤ 𝑗 ≤⌊𝑛/2⌋, 𝑗 ≤𝑘 ≤𝑛− 𝑗 ,

a subalgebra of Q[[𝑡∗]] [𝑥, 𝑦].

(c) For all 𝑛 ≥ 2, the 𝑛th homogeneous component of Acyc

(cpk,cdes) has dimension (cid:4)𝑛2/4(cid:5).

Proof. We shall apply Theorem 4.2.7 using st = (pk, des). In doing so, we take 𝜙(pk,des) to be

the composition of the map 𝐹𝐿 ↦→ 𝜋(pk,des) with the map from Theorem 4.3.7 (b), where 𝜋 is any

permutation with pk 𝜋 = pk 𝐿 and des 𝜋 = des 𝐿.

Let 𝜋 be a permutation of length 𝑛 ≥ 2 with cyclic descent set 𝑆, and let 𝑗 = cpk[𝜋] and

𝑘 = cdes[𝜋] (which only depend on 𝑆 and not the specific choice of 𝜋). Let us consider the 𝑛 linear

permutations in [𝜋], whose descent sets are given by 𝑆 + 𝑖 where 𝑖 ranges from 1 to 𝑛. Among these

𝑛 permutations, the following hold:

• Exactly 𝑗 of these permutations have cpk[𝜋] − 1 peaks and cdes[𝜋] descents, which are those

that have a cyclic peak in the first position.

• Exactly 𝑗 of these permutations have cpk[𝜋] − 1 peaks and cdes[𝜋] − 1 descents, which are

those that have a cyclic peak in the last position.

43

• Exactly 𝑘 − 𝑗 of these permutations have cpk[𝜋] peaks and cdes[𝜋] − 1 descents, which are

those that have a cyclic descent in the last position which is not a cyclic peak.

• The remaining 𝑛 − 𝑗 − 𝑘 permutations have cpk[𝜋] peaks and cdes[𝜋] descents.

Therefore, we have

𝜙(cpk,cdes) (𝐹cyc

𝑛,𝑆 ) =

∑︁

𝜙(pk,des) (𝐹𝑛,𝑆+𝑖)

𝑖∈[𝑛]
= 𝑗𝑢(pk,des)

𝑛, 𝑗−1,𝑘 + 𝑗𝑢(pk,des)
𝑛, 𝑗−1,𝑘−1
.

= 𝑣 (cpk,cdes)
𝑛, 𝑗,𝑘

+ (𝑘 − 𝑗)𝑢(pk,des)
𝑛, 𝑗,𝑘−1

+ (𝑛 − 𝑗 − 𝑘)𝑢(pk,des)

𝑛, 𝑗,𝑘

For 𝑛 = 0 and 𝑛 = 1, we have

𝜙(cpk,cdes) (𝐹cyc

0,∅ ) =

1
1 − 𝑡

and 𝜙(cpk,cdes) (𝐹cyc

1,∅ ) =

𝑡 (1 + 𝑦)
(1 − 𝑡)2

𝑥.

Clearly, 𝜙(cpk,cdes) (𝐹cyc

𝑛,𝑆 ) depends only on the (cpk, cdes)-equivalence class of cComp[𝑆].

To prove linear independence, let us order monomials in the variables 𝑡 and 𝑦 lexicographically

by the exponent of 𝑡 followed by the exponent of 𝑦, that is, 𝑡𝑎 𝑦𝑏 > 𝑡𝑐 𝑦𝑑 if and only if either 𝑎 > 𝑐,

or if 𝑎 = 𝑐 and 𝑏 > 𝑑. Since Corollary 4.3.3 implies 𝑗 ≥ 1, it is readily verified that the least
monomial in (1 − 𝑡)𝑛+1𝑣 (cpk,cdes)

𝑛, 𝑗,𝑘

/𝑥𝑛 is 𝑡 𝑗 𝑦𝑘− 𝑗 ; thus
(cid:26) (1 − 𝑡)𝑛+1
𝑥𝑛

𝑣 (cpk,cdes)
𝑛, 𝑗,𝑘

(cid:27)

1≤ 𝑗 ≤⌊𝑛/2⌋
𝑗 ≤𝑘 ≤𝑛− 𝑗

is linearly independent for each 𝑛 ≥ 2, and this in turn implies that

(cid:26) 1
1 − 𝑡

,

𝑡 (1 + 𝑦)
(1 − 𝑡)2

𝑥

(cid:27) (cid:216)

{𝑣 (cpk,cdes)
𝑛, 𝑗,𝑘

} 𝑛≥2

1≤ 𝑗 ≤⌊𝑛/2⌋
𝑗 ≤𝑘 ≤𝑛− 𝑗

is linearly independent. Corollary 4.3.3 ensures that we have the correct limits on 𝑗 and 𝑘, so we

can use Theorem 4.2.7 to conclude that parts (a) and (b) hold.

From Corollary 4.3.3, we know that for 𝑛 ≥ 2, the number of (cpk, cdes)-equivalence classes

of cyclic permutations of length 𝑛 is

⌊𝑛/2⌋
∑︁

𝑗=1

((𝑛 − 𝑗) − 𝑗 + 1) =

⌊𝑛/2⌋
∑︁

𝑗=1

(𝑛 − 2 𝑗 + 1),

and it is straightforward to show that this is equal to (cid:4)𝑛2/4(cid:5). Thus, part (c) follows.

□

44

4.3.4 The Cyclic Shuffle Algebras of cpk and cdes

Next, we use our characterization of the cyclic shuffle algebra Acyc

(cpk,cdes) along with Theo-

rem 4.1.3 to characterize Acyc

cpk and Acyc

cdes, which also provides an alternative proof for the cyclic

shuffle-compatibility of cpk and cdes.

In the theorems below, we use the notation Q[𝑥]N to denote the algebra of functions N → Q[𝑥]
(cid:1)𝑥 + 𝑝3—which we write
(cid:1)(cid:1)

in the non-negative integer variable 𝑝. For example, the map 𝑝 ↦→ (cid:0) 𝑝
2
simply as (cid:0) 𝑝
2

(cid:1)𝑥 + 𝑝3 for brevity—is an element of Q[𝑥]N. Moreover, in Theorem 4.3.9 below, (cid:0)(cid:0)𝑛
𝑘

is the number of 𝑘-element multisubsets of [𝑛].

Theorem 4.3.9 (Cyclic shuffle-compatibility of cpk).

(a) The cyclic peak number cpk is cyclic shuffle-compatible.

(b) The linear map on Acyc

cpk defined by

[𝜋]cpk ↦→
(cpk[𝜋] (1 + 𝑡)2 + 2(|𝜋| − 2 cpk[𝜋])𝑡) (4𝑡)cpk[𝜋] (1 + 𝑡) |𝜋|−2 cpk[𝜋]−1
(1 − 𝑡) |𝜋|+1

1/(1 − 𝑡),

𝑥 |𝜋|,

if |𝜋| ≥ 1,

if |𝜋| = 0,





is a Q-algebra isomorphism from Acyc

cpk to the span of

(cid:26) 1
1 − 𝑡

,

𝑡𝑥
(1 − 𝑡)2

(cid:27) (cid:216) (cid:26) ( 𝑗 (1 + 𝑡)2 + 2(𝑛 − 2 𝑗)𝑡) (4𝑡) 𝑗 (1 + 𝑡)𝑛−2 𝑗−1

(1 − 𝑡)𝑛+1

(cid:27)

𝑥𝑛

,

𝑛≥2,
1≤ 𝑗 ≤⌊𝑛/2⌋

a subalgebra of Q[[𝑡∗]] [𝑥].

(c) For all 𝑛 ≥ 2, the 𝑛th homogeneous component of Acyc

cpk has dimension ⌊𝑛/2⌋.

Proof. Let 𝜙 : Acyc

(cpk,cdes) → Q[[𝑡∗]] [𝑥] be the composition of the map from Theorem 4.3.8 (b)

and the 𝑦 = 1 evaluation map. Since

𝑣 (cpk,cdes)
𝑛, 𝑗,𝑘

(cid:12)
(cid:12)
(cid:12)𝑦=1

=

( 𝑗 (1 + 𝑡)2 + 2(𝑛 − 2 𝑗)𝑡) (4𝑡) 𝑗 (1 + 𝑡)𝑛−2 𝑗−1
(1 − 𝑡)𝑛+1

𝑥𝑛

for all 𝑛 ≥ 1, we see that 𝜙 is precisely the map in part (b) of this theorem. Note that 𝑣 (cpk,cdes)
depends only on 𝑛 and 𝑗, so the 𝑣 (cpk,cdes)

|𝑦=1 correspond to cpk-equivalence classes. Furthermore,

|𝑦=1

𝑛, 𝑗,𝑘

𝑛, 𝑗,𝑘

45

it is straightforward to verify that the 𝑣 (cpk,cdes)

𝑛, 𝑗,𝑘

|𝑦=1 are linearly independent, so we may apply

Theorem 4.1.3 to complete the proof.

□

Theorem 4.3.10 (Cyclic shuffle-compatibility of cdes).

(a) The cyclic descent number cdes is cyclic shuffle-compatible.

(b) The linear map on Acyc

cdes defined by
cdes[𝜋]𝑡cdes[𝜋] + (|𝜋| − cdes[𝜋])𝑡cdes[𝜋]+1

(1 − 𝑡) |𝜋|+1


is a Q-algebra isomorphism from Acyc

[𝜋]cdes ↦→

1/(1 − 𝑡),

𝑥 |𝜋|,

if |𝜋| ≥ 1,

if |𝜋| = 0,

(cid:26) 1
1 − 𝑡

,

𝑡𝑥
(1 − 𝑡)2

a subalgebra of Q[[𝑡∗]] [𝑥].

cdes to the span of
(cid:27) (cid:216) (cid:26) 𝑘𝑡 𝑘 + (𝑛 − 𝑘)𝑡 𝑘+1

(1 − 𝑡)𝑛+1

(cid:27)

𝑥𝑛

,

𝑛≥2,
1≤𝑘 ≤𝑛−1

(c) The linear map on Acyc

cdes defined by




1,

[𝜋]cdes ↦→

(cid:18)𝑝 + |𝜋| − cdes[𝜋] − 1
|𝜋| − 1

(cid:19)

𝑝𝑥 |𝜋|,

if |𝜋| ≥ 1,

if |𝜋| = 0,

is a Q-algebra isomorphism from Acyc

cdes to the span of
(cid:216) (cid:26)(cid:18)𝑝 + 𝑛 − 𝑘 − 1
(cid:19)

𝑛 − 1

𝑝𝑥𝑛

(cid:27)

,

𝑛≥2,
1≤𝑘 ≤𝑛−1

{1, 𝑝𝑥}

a subalgebra of Q[𝑥]N.

(d) For all 𝑛 ≥ 2, the 𝑛th homogeneous component of Acyc

cdes has dimension 𝑛 − 1.

Proof. The proofs for parts (a), (b), and (d) follow in the same way as in for Theorem 4.3.9, except

that we evaluate at 𝑦 = 0 as opposed to 𝑦 = 1. Part (c) follows from part (b) and the identity

𝑘𝑡 𝑘 + (𝑛 − 𝑘)𝑡 𝑘+1
(1 − 𝑡)𝑛+1

=

∞
∑︁

𝑝=0

(cid:18)𝑝 + 𝑛 − 𝑘 − 1
𝑛 − 1

(cid:19)

𝑝𝑡 𝑝,

which was established in [AGRR21, Lemma 5.8].

□

46

4.4 Cyclic Permutation Statistics Induced by Linear Permutation Statistics

Recall that the cyclic permutation statistics cDes and cPk are defined by

cDes[𝜋] (cid:66) {{ cDes ¯𝜋 : ¯𝜋 ∈ [𝜋] }}

and

cPk[𝜋] (cid:66) {{ cPk ¯𝜋 : ¯𝜋 ∈ [𝜋] }}.

In other words, cDes[𝜋] is simply the distribution of the linear permutation statistic cDes over all

linear permutations in [𝜋], and similarly with cPk[𝜋]. In fact, any linear permutation statistic st

induces a multiset-valued cyclic permutation statistic (which we also denote st by a slight abuse of

notation) if we let

st[𝜋] (cid:66) {{ st ¯𝜋 : ¯𝜋 ∈ [𝜋] }}.

In this section, we study these multiset-valued cyclic statistics induced from various linear permu-

tation statistics.

4.4.1 The Cyclic Statistics Des, des, Pk, and pk

To begin, we note that the cyclic statistics induced from the linear statistics Des, des, Pk, and

pk are equivalent to cDes, cdes, cPk, and cpk, respectively.

Lemma 4.4.1. The cyclic permutation statistics Des and cDes are equivalent.

Proof. Let 𝜋 ∈ 𝔖𝑛. For any ¯𝜋 ∈ [𝜋], we have Des ¯𝜋 = cDes ¯𝜋\{𝑛} if 𝑛 ∈ cDes ¯𝜋 and Des ¯𝜋 =

cDes ¯𝜋 otherwise. Therefore, we can obtain Des[𝜋] from cDes[𝜋] by removing every 𝑛 from the

cyclic descent sets in cDes[𝜋], and we can obtain cDes[𝜋] from Des[𝜋] by adding 𝑛 to each descent

set in Des[𝜋] with one fewer element than the others.

□

Lemma 4.4.2. The cyclic permutation statistics des and cdes are equivalent.

Proof. Let 𝜋 ∈ 𝔖𝑛. For any ¯𝜋 ∈ [𝜋], we have des ¯𝜋 = cdes[𝜋] −1 if 𝑛 ∈ cDes ¯𝜋 and des ¯𝜋 = cdes[𝜋]

otherwise. The unique permutation in [𝜋] beginning with its largest letter does not have 𝑛 as a

cyclic descent, so we can determine cdes[𝜋] from the multiset des[𝜋] by taking the largest value

in des[𝜋].

47

Conversely, among the 𝑛 rotations of 𝜋, there are exactly cdes[𝜋] permutations with a cyclic

descent in the last position; this implies that des[𝜋] is the multiset with cdes[𝜋] copies of cdes[𝜋] −1

and 𝑛 − cdes[𝜋] copies of cdes[𝜋], so we can determine des[𝜋] from cdes[𝜋] as well.

□

Lemma 4.4.3. The cyclic permutation statistics Pk and cPk are equivalent.

Proof. Let 𝜋 ∈ 𝔖𝑛. For any ¯𝜋 ∈ [𝜋], we have Pk ¯𝜋 = cPk ¯𝜋\{1} if 1 ∈ cPk ¯𝜋, Pk ¯𝜋 = cPk ¯𝜋\{𝑛} if

𝑛 ∈ cPk ¯𝜋, and Pk ¯𝜋 = cPk ¯𝜋 otherwise. (Note that cPk ¯𝜋 cannot simultaneously contain 1 and 𝑛.)

Hence, we can obtain Pk[𝜋] from cPk[𝜋] by removing every 1 and 𝑛 from the cyclic peak sets in

cPk[𝜋].

Conversely, suppose that we are given Pk[𝜋] and wish to recover cPk[𝜋]. Let 𝑖 ∈ [𝑛] be

arbitrary. Notice that, among all 𝑛 representatives of [𝜋], the index of 𝜋𝑖 spans the entire range

{1, 2, . . . , 𝑛}. If 𝑖 is a cyclic peak of 𝜋 in particular, this means that the index of 𝜋𝑖 will be a peak of

all 𝑛 representatives of [𝜋] except for the linear permutation beginning with 𝜋𝑖 and the one ending

with 𝜋𝑖; hence, if one adds up pk ¯𝜋 over all ¯𝜋 ∈ [𝜋], then each of these 𝜋𝑖 will contribute 𝑛 − 2 to the

summation. It follows that the sum of the sizes of all peak sets in Pk[𝜋] is equal to (𝑛 − 2) cpk[𝜋];

in other words, we can determine cpk[𝜋] from Pk[𝜋].

It remains to show that we can recover

cPk[𝜋] from cpk[𝜋] and Pk[𝜋]. To do so, we divide into two cases:

• Case 1: Suppose that there exists a peak set Pk ¯𝜋 in Pk[𝜋] with cpk[𝜋] elements. Then

Pk ¯𝜋 = cPk ¯𝜋, and we can recover the entire multiset cPk[𝜋] by taking all 𝑛 cyclic shifts of

Pk ¯𝜋.

• Case 2: Suppose instead that all peak sets in Pk[𝜋] have cpk[𝜋] − 1 elements. Then,

every linear permutation in [𝜋] has either 1 or 𝑛 as a cyclic peak. In general, among the 𝑛

representatives of [𝜋], there are exactly 2 cpk[𝜋] of them with a cyclic peak at one end. This

means that 2 cpk[𝜋] = 𝑛, and since cyclic peak sets cannot contain two consecutive indices,

it follows that every cyclic peak set in cPk[𝜋] is of the form {1, 3, . . . , 𝑛 − 1} or {2, 4, . . . , 𝑛}.

More precisely, we must have

cPk[𝜋] = {{ {1, 3, . . . , 𝑛 − 1}𝑛/2, {2, 4, . . . , 𝑛}𝑛/2 }}.

48

Since cPk[𝜋] can be recovered from Pk[𝜋] in both cases, we are done.

□

Lemma 4.4.4. The cyclic permutation statistics pk and cpk are equivalent.

Proof. Let 𝜋 ∈ 𝔖𝑛. As shown in the proof of Lemma 4.4.3, the sum of the sizes of all peak sets

in Pk[𝜋] is equal to (𝑛 − 2) cpk[𝜋], but this is the same as the sum of all elements of the multiset

pk[𝜋]. Thus, cpk[𝜋] can be determined from pk[𝜋].

For the converse, we use the observation (also used in the proof of Lemma 4.4.3) that among the

𝑛 representatives of a cyclic permutation [𝜋], there are exactly 2 cpk[𝜋] of them with a cyclic peak

at one end. This implies that the multiset pk[𝜋] has 2 cpk[𝜋] copies of cpk[𝜋] − 1 and 𝑛 − 2 cpk[𝜋]

copies of cpk[𝜋]. Hence, cpk[𝜋] completely determines pk[𝜋].

□

Since cDes, cdes, cPk, and cpk are cyclic shuffle-compatible, it follows from these equivalences

and Theorem 4.1.4 that the cyclic statistics Des, des, Pk, and pk are as well.

Theorem 4.4.5 (Cyclic shuffle-compatibility of Des, des, Pk, and pk). The cyclic statistics Des,

des, Pk, and pk are cyclic shuffle-compatible, and we have the Q-algebra isomorphisms

Acyc
Des

(cid:27) Acyc
cDes

, Acyc
des

(cid:27) Acyc
cdes

, Acyc
Pk

(cid:27) Acyc
cPk

,

and Acyc
pk

(cid:27) Acyc
cpk

.

4.4.2 Symmetries Revisited

Let

𝑓 be a length-preserving involution on permutations that is both shuffle-compatibility-

preserving and rotation-preserving.

In Section 4.1.3, we proved that if the cyclic permutation

statistics cst1 and cst2 are 𝑓 -equivalent and if cst1 is cyclic shuffle-compatible, then cst2 is also

cyclic shuffle-compatible with cyclic shuffle algebra isomorphic to that of cst1. We now show that

𝑓 -equivalence of two linear permutation statistics induces 𝑓 -equivalence of their induced cyclic

statistics.

Lemma 4.4.6. Let 𝑓 be rotation-preserving. If st1 and st2 are 𝑓 -equivalent linear permutation

statistics, then their induced cyclic permutation statistics st1 and st2 are 𝑓 -equivalent.

49

Proof. Since st1 and st2 are 𝑓 -equivalent linear permutation statistics, we have st1 𝜋 𝑓 = st1 𝜎 𝑓 if
and only if st2 𝜋 = st2 𝜎. Suppose that st2 [𝜋] = st2 [𝜎]. Then, there is a bijective correspondence
𝑔 : [𝜋] → [𝜎] satisfying st2 ¯𝜋 = st2 𝑔( ¯𝜋) for all ¯𝜋 ∈ [𝜋], so st1 ¯𝜋 𝑓 = st1 𝑔( ¯𝜋) 𝑓 for all ¯𝜋 ∈ [𝜋].
Because 𝑓 is rotation-preserving, the permutations ¯𝜋 𝑓 and 𝑔( ¯𝜋) 𝑓 over all ¯𝜋 ∈ [𝜋] are precisely the
rotations of 𝜋 𝑓 and 𝜎 𝑓 , respectively. Thus, we have st1 [𝜋 𝑓 ] = st1 [𝜎 𝑓 ]. The converse follows from
similar reasoning, so we have st1 [𝜋 𝑓 ] = st1 [𝜎 𝑓 ] if and only if st2 [𝜋] = st2 [𝜎]—in other words,
□
the cyclic permutation statistics st1 and st2 are 𝑓 -equivalent.

Theorem 4.4.7. Let

𝑓 be shuffle-compatibility-preserving and rotation-preserving, and let st1

and st2 be 𝑓 -equivalent linear permutation statistics. If the induced cyclic statistic st1 is cyclic
shuffle-compatible, then the induced cyclic statistic st2 is also cyclic shuffle-compatible and Acyc
st2
is isomorphic to Acyc
st1

.

Proof. This is an immediate consequence of Theorem 4.1.11 and Lemma 4.4.6.

□

Corollary 4.4.8. Suppose that the linear permutation statistics st1 and st2 are 𝑟-equivalent, 𝑐-

equivalent, or 𝑟𝑐-equivalent. If the induced cyclic statistic st1 is cyclic shuffle-compatible, then the
induced cyclic statistic st2 is also cyclic shuffle-compatible and its cyclic shuffle algebra Acyc
st2
isomorphic to Acyc
st1

is

.

Given 𝜋 ∈ 𝔖𝑛, recall that the valley set Val statistic is defined by

Val 𝜋 (cid:66) { 𝑖 ∈ [𝑛] : 𝜋𝑖−1 > 𝜋𝑖 < 𝜋𝑖+1, },

and let us also define the cyclic valley set cVal by

cVal 𝜋 (cid:66) { 𝑖 ∈ [𝑛] : 𝜋𝑖−1 > 𝜋𝑖 < 𝜋𝑖+1 where 𝑖 is considered modulo 𝑛 }.

As a sample application of Corollary 4.4.8, observe that Val is 𝑐-equivalent to Pk (as linear

permutation statistics) and similarly with cVal and cPk. Combining this with Lemma 4.4.3, we

immediately obtain the following.

50

Theorem 4.4.9 (Cyclic shuffle-compatibility of Val and cVal). The cyclic statistics Val and cVal

are cyclic shuffle-compatible, and we have the Q-algebra isomorphisms

Acyc
Val

(cid:27) Acyc
Pk

(cid:27) Acyc
cPk

(cid:27) Acyc
cVal

.

4.4.3 Cyclic Major Index

A natural question to ask is whether there is a nice cyclic analogue of the major index. This

question was raised in [AGRR21]. One first needs to explain what one means by “nice."

If 𝜋 ∈ 𝔖𝑚 and 𝜎 ∈ 𝔖𝑛, then

|𝜋 (cid:1) 𝜎| =

(cid:19)

(cid:18)𝑚 + 𝑛
𝑚

.

From Stanley’s theory of 𝑃-partitions [Sta72], one gets the 𝑞-analogue

𝑞maj 𝜏 = 𝑞maj 𝜋+maj 𝜎

(cid:21)

(cid:20)𝑚 + 𝑛
𝑚

∑︁

𝜏∈𝜋(cid:1)𝜎

(4.4.1)

where (cid:2)𝑚+𝑛
𝑚

(cid:3) is a 𝑞-binomial coefficient. Note that (4.4.1) implies that maj is shuffle-compatible.

It can be shown that

|[𝜋] (cid:1) [𝜎]| = (𝑚 + 𝑛 − 1)

(cid:18)𝑚 + 𝑛 − 2
𝑚 − 1

(cid:19)

,

so one could ask that the cyclic major index give a 𝑞-analogue of this identity, similar to (4.4.1), or

at least for the cyclic major index to be cyclic shuffle-compatible.

Stanley also refined Equation (4.4.1) as follows. Let

𝜋 (cid:1)𝑘 𝜎 = { 𝜏 ∈ 𝜋 (cid:1) 𝜎 : des 𝜏 = 𝑘 }.

If des 𝜋 = 𝑖 and des 𝜎 = 𝑗, then

∑︁

𝜏∈𝜋(cid:1)𝑘 𝜎

𝑞maj 𝜏 = 𝑞maj 𝜋+maj 𝜎+(𝑘−𝑖)(𝑘− 𝑗)

(cid:20)𝑚 − 𝑗 + 𝑖
𝑘 − 𝑗

(cid:21) (cid:20)𝑛 − 𝑖 + 𝑗
𝑘 − 𝑖

(cid:21)

;

(4.4.2)

in particular, this implies that (des, maj) is shuffle-compatible, and so we would like a cmaj statistic

for which cmaj and (cdes, cmaj) are both cyclic shuffle-compatible.

In [AGRR21], Adin et al. computed the cardinality of

[𝜋] (cid:1)𝑘 [𝜎] = { [𝜏] ∈ [𝜋] (cid:1) [𝜎] : cdes[𝜏] = 𝑘 }

51

which inspired Ji and Zhang [JZ22] to define a cmaj statistic which gives a 𝑞-analogue of this

count. They proved a generating function formula analogous to (4.4.2), but unfortunately, the

formula does not simplify into single product, and one could hope for a different cyclic major index

whose generating function would do so. Furthermore, their formula does not actually show that

their (cdes, cmaj) is cyclic shuffle-compatible; in fact, neither of their cmaj and (cdes, cmaj) are

cyclic shuffle-compatible.

Each of the cyclic statistics cDes, cdes, cPk, and cpk is (or is equivalent to) a multiset-valued

cyclic statistic induced by a corresponding linear permutation statistic, so a natural alternative

definition for a cyclic major index would be to define cmaj first on linear permutations and then

consider the multiset-valued statistic induced by the linear cmaj. To that end, given a linear

permutation 𝜋, let

cmaj 𝜋 (cid:66) ∑︁
𝑘 ∈cDes 𝜋

𝑘.

Unfortunately, the induced statistics cmaj and (cdes, cmaj) are not cyclic shuffle-compatible.

As a counterexample, take 𝜋 = 1 4 7 6 9 10 8 2 5 3, 𝜎 = 1 3 5 4 7 6 9 10 8 2, and 𝜌 = 11. Then

cdes[𝜋] = cdes[𝜎] = 5 and cmaj[𝜋] = cmaj[𝜎] = {{20, 254, 304, 35}}, but cmaj( [𝜋] (cid:1) [𝜌]) ≠

cmaj([𝜎] (cid:1) [𝜌]). For instance, the multiset {{22, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35}} is an ele-

ment of cmaj([𝜋] (cid:1) [𝜌]) but not cmaj( [𝜎] (cid:1) [𝜌]).

Another option is to consider the cyclic statistic induced by the usual major index maj, as

opposed to cmaj. Even if cmaj and (cdes, cmaj) are not cyclic shuffle-compatible, it’s conceivable

that maj and (des, maj) are. It turns out that maj is equivalent to cmaj and similarly with (des, maj)

and (cdes, cmaj), so by Theorem 4.1.4, neither maj nor (des, maj) are cyclic shuffle-compatible.

Lemma 4.4.10. The cyclic permutation statistics (des, maj) and (cdes, cmaj) are equivalent.

Proof. Fix a cyclic permutation [𝜋] = {𝜋 = 𝜋(1), 𝜋(2), . . . , 𝜋(𝑛) } of length 𝑛 where, for each 𝑖 ∈ [𝑛],

𝜋(𝑖+1) is obtained from 𝜋(𝑖) by rotating its last element to the front of the permutation and 𝑖 is taken

52

modulo 𝑛. We claim that, for all 𝑖 ∈ [𝑛],

cmaj 𝜋(𝑖+1) =





cmaj 𝜋(𝑖) + cdes[𝜋] − 𝑛,

if 𝑛 ∈ cDes 𝜋(𝑖),

cmaj 𝜋(𝑖) + cdes[𝜋],

if 𝑛 ∉ cDes 𝜋(𝑖).

(4.4.3)

To prove (4.4.3), first assume that 𝑛 ∈ cDes 𝜋(𝑖), and let 𝑘 = cdes[𝜋]. Then

cDes 𝜋(𝑖) = { 𝑗1 < 𝑗2 < · · · < 𝑗𝑘 = 𝑛}

whereas

So

cDes 𝜋(𝑖+1) = {1 < 𝑗1 + 1 < 𝑗2 + 1 < · · · < 𝑗𝑘−1 + 1}.

cmaj 𝜋(𝑖) − cmaj 𝜋(𝑖+1) = 𝑛 − 𝑘,

which is equivalent to the first case of (4.4.3). The second case is proven using a similar computation.

Observe that Equation (4.4.3) is equivalent to

cmaj 𝜋(𝑖+1) = maj 𝜋(𝑖) + cdes[𝜋],

(4.4.4)

which allows us to determine cmaj[𝜋] from maj[𝜋] and cdes[𝜋]. Moreover, cdes[𝜋] can be

determined from des[𝜋] by Lemma 4.4.2, so (cdes, cmaj) [𝜋] can be determined from (des, maj) [𝜋].

Conversely, we can use (4.4.4) to determine maj[𝜋] from cmaj[𝜋] and cdes[𝜋], and des[𝜋] can

be determined from cdes[𝜋] by Lemma 4.4.2; altogether, this means that we can also determine

(des, maj) [𝜋] from (cdes, cmaj) [𝜋].

□

Lemma 4.4.11. The cyclic permutation statistics maj and cmaj are equivalent.

Proof. Let 𝜋 ∈ 𝔖𝑛. We first claim that cdes[𝜋] can be determined either from maj[𝜋] or from

cmaj[𝜋]. Fix 𝑖 ∈ cDes 𝜋. Among all 𝑛 representatives of [𝜋], the index of 𝜋𝑖 spans the entire

range {1, 2, . . . , 𝑛}. Hence, if one adds up maj ¯𝜋 over all ¯𝜋 ∈ [𝜋], then 𝜋𝑖 will contribute
1 + 2 + · · · + (𝑛 − 1) = (cid:0)𝑛
(cid:1) to the summation. Similarly, in taking the sum of all cmaj ¯𝜋, each 𝜋𝑖 will
2
contribute 1 + 2 + · · · + 𝑛 = (cid:0)𝑛+1
(cid:1). Thus, the sum of all elements of the multiset maj[𝜋] is equal
2

53

to (cid:0)𝑛
2

(cid:1) cdes[𝜋] and the sum of all elements of cmaj[𝜋] is equal to (cid:0)𝑛+1
2

(cid:1) cdes[𝜋], and it follows that

cdes[𝜋] can be determined from maj[𝜋] or cmaj[𝜋].

Now we are ready to prove the equivalence between maj and cmaj. For one direction, maj[𝜋]

completely determines cdes[𝜋] and hence determines des[𝜋] by Lemma 4.4.2. Furthermore,

maj[𝜋] and des[𝜋] together determine (cdes, cmaj) [𝜋] by Lemma 4.4.10, so cmaj[𝜋] can be

determined from maj[𝜋]. One can similarly prove the other direction using the above claim and

Lemma 4.4.10.

□

Definition 4.4.12 (Comajor index). The comajor index comaj, defined by

comaj 𝜋 (cid:66) ∑︁
𝑘∈Des 𝜋

(𝑛 − 𝑘)

for 𝜋 ∈ 𝔖𝑛, is a classical variation of the major index statistic.

Because the linear permutation statistics maj and comaj are 𝑟𝑐-equivalent and the induced cyclic

statistic maj is not cyclic shuffle-compatible, it follows from Corollary 4.4.8 that the induced cyclic

statistic comaj is not cyclic shuffle-compatible either.

Definition 4.4.13 (Cyclic comajor index). Define the cyclic comajor index ccomaj by

ccomaj 𝜋 (cid:66) ∑︁
𝑘 ∈cDes 𝜋

(𝑛 − 𝑘)

for 𝜋 ∈ 𝔖𝑛.

It follows similarly that the induced cyclic statistics ccomaj, (des, comaj), and (cdes, ccomaj) are

not cyclic shuffle-compatible either.

Perhaps surprisingly, adding just a little bit of structure to our cmaj statistic gives a statistic

which is equivalent to cDes. As in the proof of Lemma 4.4.10, given 𝜋 ∈ 𝔖𝑛, let us write

[𝜋] = {𝜋 = 𝜋(1), 𝜋(2), . . . , 𝜋(𝑛) }

where 𝜋(𝑖+1) is obtained from 𝜋(𝑖) by rotating its last element to the front of the permutation and 𝑖

is taken modulo 𝑛.

54

Definition 4.4.14 (Ordered cyclic major index). Define the ordered cyclic major index of [𝜋] to be

the cyclic word

ocmaj[𝜋] (cid:66) [cmaj 𝜋(1), cmaj 𝜋(2), . . . , cmaj 𝜋(𝑛)],

i.e., the equivalence class of the sequence (cmaj 𝜋(1), cmaj 𝜋(2), . . . , cmaj 𝜋(𝑛)) under cyclic shift.

Theorem 4.4.15. The cyclic permutation statistics cDes and ocmaj are equivalent.

Proof. Let us assume throughout this proof that 𝑛 ≥ 2, as the cases 𝑛 = 0 and 𝑛 = 1 are trivial.

To see that cDes is a refinement of ocmaj, suppose cDes[𝜋] = cDes[𝜎] where 𝜋 and 𝜎 have the

same length 𝑛. So, we can write [𝜎] = {𝜎 (1), 𝜎(2), . . . , 𝜎 (𝑛) } where cDes 𝜋(𝑖) = cDes 𝜎 (𝑖) for all

𝑖 ∈ [𝑛]. It follows that

cmaj 𝜋(𝑖) =

∑︁

𝑘 =

∑︁

𝑘 = cmaj 𝜎 (𝑖)

𝑘∈cDes 𝜋 (𝑖)

𝑘 ∈cDes 𝜎 (𝑖)

for all 𝑖, so ocmaj[𝜋] = ocmaj[𝜎].

For the converse, it is sufficient to show that the cyclic descent composition cComp[𝜋] can be

reconstructed from ocmaj[𝜋]. First, recall Equation (4.4.3):

cmaj 𝜋(𝑖+1) =





cmaj 𝜋(𝑖) + cdes[𝜋] − 𝑛,

if 𝑛 ∈ cDes 𝜋(𝑖),

cmaj 𝜋(𝑖) + cdes[𝜋],

if 𝑛 ∉ cDes 𝜋(𝑖).

Since 𝑛 ≥ 2, we have 1 ≤ cdes[𝜋] ≤ 𝑛 − 1, and together with the above equation, we have that

𝑛 ∈ cDes 𝜋(𝑖) if and only if cmaj 𝜋(𝑖) > cmaj 𝜋(𝑖+1). A similar argument shows that we can never

have cmaj 𝜋(𝑖) = cmaj 𝜋(𝑖+1).

Now, suppose we are given ocmaj[𝜋] = [𝑚1, 𝑚2, . . . , 𝑚𝑛] where 𝑚𝑖 = cmaj 𝜋(𝑖). Let 𝑠 and 𝑡 be

two consecutive cyclic descents of ocmaj[𝜋], i.e.,

𝑚𝑠 > 𝑚𝑠+1 < 𝑚𝑠+2 < · · · < 𝑚𝑡 > 𝑚𝑡+1

where subscripts are considered modulo 𝑛 as usual. From the previous paragraph, it follows that

𝑛 is in both cDes 𝜋(𝑠) and cDes 𝜋(𝑡), and that the penultimate descent in cDes 𝜋(𝑠) becomes the

descent 𝑛 ∈ cDes 𝜋(𝑡) with 𝑛 never being a descent for any of the intermediate cyclic descent sets.

55

So 𝑡 − 𝑠 (modulo 𝑛) is a part of the cyclic composition cComp[𝜋]. Therefore, all the parts of

cComp[𝜋] can be determined, and their order will be the same as that induced by the consecutive

cyclic descents in ocmaj[𝜋]. Thus we have reconstructed cComp[𝜋] from ocmaj[𝜋], completing

the proof.

□

Corollary 4.4.16 (Cyclic shuffle-compatibility of ocmaj). The ordered cyclic major index ocmaj is

cyclic shuffle-compatible, and its cyclic shuffle algebra Acyc

ocmaj is isomorphic to Acyc
cDes.

Of course, one could wonder if the unordered multiset of cmaj values is also equivalent to cDes

for cyclic permutations, but this is not the case. Indeed, if the cyclic permutation statistics cmaj

and cDes were equivalent, then the cyclic shuffle-compatibility of cDes would imply that cmaj is

cyclic shuffle-compatible as well, which we know to be false.

4.4.4 Other Descent Statistics

To conclude this section, let us consider the cyclic permutation statistics induced by the following

linear descent statistics:

• The valley number val, which we defined earlier to be the number of valleys of a permutation.

• The double descent set Ddes and the double descent number ddes. We call 𝑖 ∈ {2, 3, . . . , 𝑛−1}

a double descent of 𝜋 ∈ 𝔖𝑛 if 𝜋𝑖−1 > 𝜋𝑖 > 𝜋𝑖+1. Then Ddes 𝜋 is the set of double descents of

𝜋, and ddes 𝜋 the number of double descents of 𝜋.

• The left peak set Lpk and the left peak number lpk. We call 𝑖 ∈ [𝑛 − 1] a left peak of 𝜋 ∈ 𝔖𝑛

if 𝑖 is a peak of 𝜋, or if 𝑖 = 1 and 𝜋1 > 𝜋2. Then Lpk 𝜋 is the set of left peaks of 𝜋, and lpk 𝜋

the number of left peaks of 𝜋.

• The right peak set Rpk and the right peak number rpk. We call 𝑖 ∈ {2, 3, . . . , 𝑛} a right peak

of 𝜋 ∈ 𝔖𝑛 if 𝑖 is a peak of 𝜋, or if 𝑖 = 𝑛 and 𝜋𝑛−1 < 𝜋𝑛. Then Rpk 𝜋 is the set of right peaks

of 𝜋, and rpk 𝜋 the number of right peaks of 𝜋.

56

• The exterior peak set Epk and the exterior peak number epk. We call 𝑖 ∈ [𝑛] an exterior

peak of 𝜋 ∈ 𝔖𝑛 if 𝑖 is a left peak or right peak of 𝜋. Then Epk 𝜋 is the set of exterior peaks

of 𝜋, and epk 𝜋 the number of exterior peaks of 𝜋.

• The number of biruns bru and the number of up-down runs udr. Recall that s birun of 𝜋 is a

maximal consecutive monotone subsequence of 𝜋; an up-down run of 𝜋 is a birun of 𝜋, or

the first letter 𝜋1 of 𝜋 if 𝜋1 > 𝜋2. Then bru 𝜋 and udr 𝜋 are the number of biruns and the

number of up-down runs, respectively, of 𝜋.

For example, take 𝜋 = 713942658. Then we have val 𝜋 = 3, Ddes 𝜋 = {5}, ddes 𝜋 = 1, Lpk 𝜋 =

{1, 4, 7}, lpk 𝜋 = 3, Rpk 𝜋 = {4, 7, 9}, rpk 𝜋 = 3, Epk 𝜋 = {1, 4, 7, 9}, epk 𝜋 = 4, bru 𝜋 = 6, and

udr 𝜋 = 7.

Aside from Ddes, ddes, and bru, all of the above statistics (as linear permutation statistics)

are shuffle-compatible. Also, because these are all descent statistics, each of the induced cyclic

statistics are cyclic descent statistics. Indeed, if we are given cDes[𝜋] and the length of 𝜋, then we

can determine Des[𝜋] by Lemma 4.4.1, and we can then use the descent sets in Des[𝜋] to obtain

the multiset st[𝜋] for any descent statistic st.

Let us begin by examining the double descent statistics Ddes and ddes. Since neither Ddes

nor ddes are shuffle-compatible as linear permutation statistics, it is perhaps unsurprising that their

induced cyclic statistics are not cyclic shuffle-compatible. As a counterexample, let 𝜋 = 1234,

𝜎 = 1324, and 𝜌 = 5. Then both Ddes[𝜋] = Ddes[𝜎] and ddes[𝜋] = ddes[𝜎], but we have

Ddes([𝜋] (cid:1) [𝜌]) ≠ Ddes([𝜎] (cid:1) [𝜌]) and ddes( [𝜋] (cid:1) [𝜌]) ≠ ddes( [𝜎] (cid:1) [𝜌]). For instance,

{{∅5}} appears three times in Ddes([𝜋] (cid:1) [𝜌]) but only twice in Ddes( [𝜎] (cid:1) [𝜌]), and accordingly

{{05}} appears three times in ddes([𝜋] (cid:1) [𝜌]) but only twice in ddes( [𝜎] (cid:1) [𝜌]).

While the linear statistic bru is not shuffle-compatible, in Theorem 3.2.6 we defined the cyclic

statistic cbru which gives the number of cyclic biruns—maximal consecutive monotone cyclic

subsequences—is cyclic shuffle-compatible as it is precisely twice the number of cyclic peaks.

Theorem 4.4.17 (Cyclic shuffle-compatibility of cbru and (cbru, cdes)). The cyclic statistics cbru

57

and (cbru, cdes) are cyclic shuffle-compatible, and we have the Q-algebra isomorphisms

Acyc
cbru

(cid:27) Acyc
cpk

and Acyc

(cbru,cdes)

(cid:27) Acyc

(cpk,cdes)

.

Because des and cdes are equivalent as cyclic permutation statistics and similarly with pk and

cpk, one might expect the cyclic statistics bru and cbru to be equivalent as well, but this is not the

case because bru is not actually cyclic shuffle-compatible. For instance, consider 𝜋 = 25673489,

𝜎 = 24567389, and 𝜌 = 1. Then bru[𝜋] = bru[𝜎], but the multiset {{54, 64, 7}} appears four times

in bru([𝜋] (cid:1) [𝜌]) but only twice in bru( [𝜎] (cid:1) [𝜌]). One can also use the same permutations 𝜋,

𝜎, and 𝜌 to show that (bru, des) is not cyclic shuffle-compatible.

Even though the linear statistics Lpk and Epk are shuffle-compatible, their induced cyclic

statistics are not cyclic shuffle-compatible. As a counterexample, take

𝜋 = 11 6 3 7 1 4 12 10 2 9 6 8,

𝜎 = 13,

𝜋′ = 13 7 2 9 5 3 10 4 8 12 6 11, and

𝜎′ = 1.

Then we have Lpk[𝜋] = Lpk[𝜋′], Lpk[𝜎] = Lpk[𝜎′], Epk[𝜋] = Epk[𝜋′], and Epk[𝜎] = Epk[𝜎′],

yet Lpk([𝜋] (cid:1) [𝜎]) ≠ Lpk([𝜋′] (cid:1) [𝜎′]) and Epk( [𝜋] (cid:1) [𝜎]) ≠ Epk( [𝜋′] (cid:1) [𝜎′]) as the multiset

{{ {1, 5, 8, 11}, {2, 6, 9, 12}, {3, 7, 10}, {1, 4, 8, 11}, {2, 5, 9, 12}, {1, 3, 6, 10},

{1, 4, 7, 11}, {2, 5, 8, 12}, {3, 6, 9}, {1, 4, 7, 10}, {2, 5, 8, 11}, {1, 3, 6, 9, 12}, {1, 4, 7, 10} }}

belongs to Lpk([𝜋] (cid:1) [𝜎]) but not Lpk( [𝜋′] (cid:1) [𝜎′]), and the multiset

{{ {1, 4, 7, 10}, {1, 4, 8, 11}, {2, 5, 8, 11}, {2, 5, 8, 12}, {2, 5, 9, 12},

{2, 6, 9, 12}, {3, 6, 9, 13}, {3, 7, 10, 13}, {1, 3, 6, 9, 12},

{1, 3, 6, 10, 13}, {1, 4, 7, 10, 13}, {1, 4, 7, 11, 13}, {1, 5, 8, 11, 13} }}

belongs to Epk([𝜋] (cid:1) [𝜎]) but not Epk( [𝜋′] (cid:1) [𝜎′]).

The left peak number lpk, number of up-down runs udr, and the pairs (lpk, des) and (udr, des)

are also shuffle-compatible linear statistics whose induced cyclic statistics are not cyclic shuffle-

compatible. For example, take 𝜋 = 87516439, 𝜎 = 53187649, and 𝜌 = 2. Then (lpk, des) [𝜋] =

58

(lpk, des) [𝜎] and (udr, des) [𝜋] = (udr, des) [𝜎] (and thus lpk[𝜋] = lpk[𝜎] and udr[𝜋] = udr[𝜎]).

However:

• {{(3, 5)6, (3, 6)3}} is in (lpk, des) ([𝜋] (cid:1) [𝜌]) but not (lpk, des) ([𝜎] (cid:1) [𝜌]),

• {{(6, 5)3, (6, 6)3, (7, 5)3}} is in (udr, des) ([𝜋] (cid:1) [𝜌]) but not (udr, des) ([𝜎] (cid:1) [𝜌]),

• {{39}} is in lpk([𝜋] (cid:1) [𝜌]) but not lpk( [𝜎] (cid:1) [𝜌]),

• and {{66, 73}} is in udr([𝜋] (cid:1) [𝜌]) but not udr( [𝜎] (cid:1) [𝜌]).

Observe that Rpk is 𝑟-equivalent to Lpk and rpk is 𝑟-equivalent to lpk. Hence, by Corollary 4.4.8,

neither Rpk nor rpk are cyclic shuffle-compatible. One can also define “left”, “right”, and “exterior”

versions of the valley set and valley number; by similar symmetry arguments, none of these are

cyclic shuffle-compatible either.

In contrast, the exterior peak number epk and the pair (epk, des) are cyclic shuffle-compatible

because they are equivalent to cpk and (cpk, cdes), respectively. To prove these equivalences, we

will also need to consider the cyclic valley number statistic cval: we say that 𝑖 ∈ [𝑛] is a cyclic

valley of 𝜋 ∈ 𝔖𝑛 if 𝜋𝑖−1 > 𝜋𝑖 < 𝜋𝑖+1 with the indices considered modulo 𝑛, and cval[𝜋] is defined to

be the number of cyclic valleys of any permutation in [𝜋]. Equivalently, cval[𝜋] is the cardinality

of the cyclic valley set cVal[𝜋] defined in Section 4.4.2.

Lemma 4.4.18. The cyclic permutation statistics val and cval are equivalent.

Proof. We have val[𝜋] = pk[𝜋𝑐] for all 𝜋—that is, val and pk are 𝑐-equivalent—and similarly with

cval and cpk. By Lemma 4.4.4, pk and cpk are equivalent, so the same is true of val and cval. □

Lemma 4.4.19. For any cyclic permutation [𝜋], we have cval[𝜋] = cpk[𝜋].

Proof. Each cyclic birun starts with a cyclic peak and ends with a cyclic valley or vice-versa. So

2 cpk[𝜋] = cbru[𝜋] = 2 cval[𝜋].

□

Lemma 4.4.20. The cyclic permutation statistics epk and cpk are equivalent.

59

Proof. For any linear permutation 𝜋, we have epk 𝜋 = val 𝜋 + 1 [GZ18, Lemma 2.1 (e)], so epk and

val are equivalent as linear permutation statistics and thus as cyclic permutation statistics. (We can

obtain val[𝜋] from epk[𝜋] by subtracting 1 from each element in the multiset, and epk[𝜋] from

val[𝜋] by adding 1 to each element.) Moreover, val is equivalent to cval (Lemma 4.4.18) which is

in turn equivalent to cpk (Lemma 4.4.19); hence, epk is equivalent to cpk.

□

Theorem 4.4.21 (Cyclic shuffle-compatibility of val, cval, epk, (val, des), (cval, cdes), and

(epk, des)). The cyclic statistics val, cval, epk, (val, des), (cval, cdes), and (epk, des) are cyclic

shuffle-compatible, and we have the Q-algebra isomorphisms

Acyc
val

(cid:27) Acyc
cval

(cid:27) Acyc
epk

(cid:27) Acyc
cpk

and Acyc

(val,des)

(cid:27) Acyc

(cval,cdes)

(cid:27) Acyc

(epk,des)

(cid:27) Acyc

(cpk,cdes)

.

Proof. The cyclic shuffle-compatibility of val, cval, and epk, and the corresponding isomorphisms,

follow from the cyclic shuffle-compatibility of cpk and the equivalences between these four statistics.

Furthermore, (val, des) is equivalent to (cpk, cdes) because val is equivalent to cpk and des

is equivalent to cdes, and similarly (cval, cdes) and (epk, des) are equivalent to (cpk, cdes) as

well. Because (cpk, cdes) is cyclic shuffle-compatible, the results for (val, des), (cval, cdes), and

(epk, des) follow.

□

Finally, we provide counterexamples showing that neither (Pk, Val) nor (pk, val) are cyclic

shuffle-compatible. Let 𝜋 = 214, 𝜎 = 536, 𝜋′ = 123, and 𝜎′ = 546. Then (Pk, Val) [𝜋] =

(Pk, Val) [𝜋′] and (Pk, Val) [𝜎] = (Pk, Val) [𝜎′], which imply (pk, val) [𝜋] = (pk, val) [𝜋′] and

(pk, val) [𝜎] = (pk, val) [𝜎′] as well. However,

{{ (∅, ∅), (∅, {5}), ({2}, ∅), ({3}, {2}), ({4}, {3}), ({5}, {4}) }}

is an element of (Pk, Val)([𝜋] (cid:1) [𝜎]) but not (Pk, Val) ([𝜋′] (cid:1) [𝜎′]), and

{{ (0, 0), (0, 1), (1, 0), (1, 1)3 }}

is an element of (pk, val)([𝜋] (cid:1) [𝜎]) but not (pk, val) ([𝜋′] (cid:1) [𝜎′]).

60

CHAPTER 5

ENRICHED TORIC [ (cid:174)𝐷]-PARTITIONS

In section 5.1 we introduce enriched (cid:174)𝐷-partitions in terms of directed acyclic graphs (DAGs), and

review the weight enumerators of enriched (cid:174)𝐷-partitions from Stembridge. Section 5.2 will focus

on defining enriched toric [ (cid:174)𝐷]-partitions and developing some of their properties. In particular,

the weight enumerators corresponding to different cyclic peak sets generate a subring of cQSym

and we call it the algebra of cyclic peaks. We also compute the order polynomial of enriched toric

[ (cid:174)𝐷]-partitions. In section 5.3, we further discuss the implication on cyclic shuffle-compatibility

from the order polynomial in previous section. In this chapter, we will use ≤ with no subscript to

denote the ordinary total order on Z, the set of integers.

5.1 Enriched Partitions on Posets

In [Ste97], Stembridge defined enriched 𝑃-partitions for a poset 𝑃. In contrast to having P with

the ordinary order ≤ as the range for ordinary 𝑃-partitions, enriched 𝑃-partitions are obtained by

imposing another total order on the range, P′, which is the set of nonzero integers with an unusual

order. We review the basic theory from Stembridge and naturally extend enriched 𝑃-partitions to

enriched (cid:174)𝐷-partitions where (cid:174)𝐷 is a directed acyclic graph which is not necessarily transitive.

5.1.1 DAGs and Posets

A directed acyclic graph (DAG) is a digraph with no directed cycles. Suppose (cid:174)𝐷 is a DAG with

vertex set [𝑛]. A DAG (cid:174)𝐷 is transitive if 𝑖 → 𝑗 and 𝑗 → 𝑘 implies 𝑖 → 𝑘 for 𝑖, 𝑗, 𝑘 ∈ [𝑛]. If (cid:174)𝑃 is a

transitive DAG, it will naturally induce a partial order < (cid:174)𝑃 on the vertex set [𝑛], defined so that for
two vertices 𝑖 and 𝑗, one has 𝑖 < (cid:174)𝑃 𝑗 if and only if 𝑖 → 𝑗 in (cid:174)𝑃; in that case, we also use (cid:174)𝑃 to denote

this poset.

In general, we can associate a partial order with any DAG (cid:174)𝐷. For this purpose, define the

transitive closure (cid:174)𝑃 of (cid:174)𝐷 as the directed graph obtained from (cid:174)𝐷 by adding in 𝑖 → 𝑘 if one has

both 𝑖 → 𝑗 and 𝑗 → 𝑘 in (cid:174)𝐷. Such (cid:174)𝑃 is unique. Moreover, it is straightforward to verify that the

transitive closure (cid:174)𝑃 is both acyclic and transitive. This implies that (cid:174)𝑃 is actually a transitive DAG,

61

hence has a partial order structure. We will maintain the use → for the relation between vertices in

a general DAG (cid:174)𝐷, while using the partial order ≤ (cid:174)𝑃 on a poset (cid:174)𝑃.

Definition 5.1.1 (Total linear order). A poset (cid:174)𝑃 is a total linear order if it is a complete DAG, i.e.,

there is a directed edge between every pair of vertices in (cid:174)𝑃.

There is a bijection between the set of total linear orders (cid:174)𝑃 on the vertex set [𝑛] and 𝔖𝑛. For a

total linear order (cid:174)𝑃 on [𝑛], there exists a unique directed path 𝜋1 → 𝜋2 → · · · → 𝜋𝑛 in (cid:174)𝑃, hence
(cid:174)𝑃 can be identified with the permutation 𝜋 = 𝜋1𝜋2 . . . 𝜋𝑛 ∈ 𝔖𝑛. Conversely, given a permutation
𝜋 = 𝜋1𝜋2 . . . 𝜋𝑛 ∈ 𝔖𝑛, we can construct a DAG (cid:174)𝑃 by putting arrows 𝜋𝑖 → 𝜋 𝑗 for all 1 ≤ 𝑖 < 𝑗 ≤ 𝑛
on the vertex set [𝑛], and it is easy to check that the resulting DAG (cid:174)𝑃 is actually a total linear order.

In this case, we usually use a permutation 𝜋 to denote the corresponding total linear order (cid:174)𝑃.

For two DAGs (cid:174)𝐷1 and (cid:174)𝐷2 on the same vertex set [𝑛], we say (cid:174)𝐷2 extends (cid:174)𝐷1 if (cid:174)𝐷1 is a
subgraph of (cid:174)𝐷2, written as (cid:174)𝐷1 ⊆ (cid:174)𝐷2. If, furthermore, (cid:174)𝐷2 is a total linear order corresponding to
the permutation 𝜋 ∈ 𝔖𝑛, we also say that 𝜋 linearly extends (cid:174)𝐷1. Denote by L ( (cid:174)𝐷) the set of all
permutations 𝜋 ∈ 𝔖𝑛 which linearly extend (cid:174)𝐷.

Example 5.1.2. Here are several DAGs on the vertex set [4] = {1, 2, 3, 4}.

1

2

3

4

1

2

3

4

1

2

(cid:174)𝐷1 = 2431

(cid:174)𝐷2 = 2413

(cid:174)𝐷3

3

4

Note that (cid:174)𝐷1 is the total linear order with permutation 2431, (cid:174)𝐷2 is the total linear order for 2413.
Both (cid:174)𝐷1 and (cid:174)𝐷2 extend (cid:174)𝐷3, hence 2431 and 2413 linearly extend (cid:174)𝐷3. Moreover, (cid:174)𝐷1 and (cid:174)𝐷2 are
the only total linear orders which extend (cid:174)𝐷3, therefore L ( (cid:174)𝐷3) = {2431, 2413}.

62

5.1.2 Enriched (cid:174)𝐷-partition

Now we are in a good position to define enriched (cid:174)𝐷-partitions for a DAG (cid:174)𝐷. Stembridge originally

defined the enriched 𝑃-partitions when 𝑃 is a poset. This definition can be easily extended to the

cases when (cid:174)𝐷 is simply a DAG, as the definition does not rely on the transitivity of 𝑃.

Stembridge defines P′ to be the set of nonzero integers, totally ordered as

−1 ≺ 1 ≺ −2 ≺ 2 ≺ −3 ≺ 3 ≺ · · · .

Definition 5.1.3 (Enriched (cid:174)𝐷-partition). Let (cid:174)𝐷 be a DAG on [𝑛]. An enriched (cid:174)𝐷-partition is a

function 𝑓 : [𝑛] → P′ such that for all 𝑖 → 𝑗 in (cid:174)𝐷,

(a) 𝑓 (𝑖) ⪯ 𝑓 ( 𝑗),

(b) 𝑓 (𝑖) = 𝑓 ( 𝑗) > 0 implies 𝑖 < 𝑗,

(c) 𝑓 (𝑖) = 𝑓 ( 𝑗) < 0 implies 𝑖 > 𝑗.

Denote by E ( (cid:174)𝐷) the set of all enriched (cid:174)𝐷-partitions 𝑓 .

Remark 5.1.4.

1. In this definition we are using two order structures on the domain [𝑛]: the order → induced

by DAG (cid:174)𝐷 and the ordinary total order ≤ on integers in (b) and (c). Both of them will

impose restrictions on the possible choices for 𝑓 . As for the range P′, we also use two order

structures: the total order ⪯ defined by Stembridge in (a) and the usual order ≤ on the integers

in (b) and (c).

2. If (cid:174)𝐷 = 𝜋 is a total linear order, the structure of the set of enriched 𝜋-partitions is quite simple:

E (𝜋) = { 𝑓 : [𝑛] → P′ |

𝑓 (𝜋1) ⪯ · · · ⪯ 𝑓 (𝜋𝑛),

𝑓 (𝜋𝑖) = 𝑓 (𝜋𝑖+1) > 0 ⇒ 𝑖 ∉ Des(𝜋),

(5.1.1)

𝑓 (𝜋𝑖) = 𝑓 (𝜋𝑖+1) < 0 ⇒ 𝑖 ∈ Des(𝜋) }.

The following fundamental lemma is a straightforward analogue of Stembridge [Ste97, Lemma

2.1].

63

Lemma 5.1.5 (Fundamental lemma of enriched (cid:174)𝐷-partitions). For any DAG (cid:174)𝐷 with vertex set [𝑛],

one has a decomposition of E ( (cid:174)𝐷) as the following disjoint union:

E ( (cid:174)𝐷) =

(cid:196)

E (𝜋).

𝜋∈L ( (cid:174)𝐷)

Proof. Given an enriched (cid:174)𝐷-partition 𝑓 . First we arrange the elements of [𝑛] in a weakly increasing

order of 𝑓 -values with respect to the total order ⪯ on the range. Then if some elements in [𝑛]

have the same 𝑓 -value −𝑘 (respectively, +𝑘) for some positive integer 𝑘, we arrange them in a

decreasing (respectively, increasing) order with respect to the usual order ≤ on the domain. The

resulting permutation 𝜋 is unique with 𝑓 ∈ E (𝜋), and 𝜋 linearly extends (cid:174)𝐷. On the other hand, for

𝜋 ∈ L ( (cid:174)𝐷), every enriched 𝜋-partition is also an enriched (cid:174)𝐷-partition. Therefore the conclusion

follows.

□

Example 5.1.6. Returning to Example 5.1.2, L ( (cid:174)𝐷3) = {2431, 2413}, hence by Lemma 5.1.5,
E ( (cid:174)𝐷3) = E (2431) ⊎ E (2413).

5.1.3 Weight Enumerators

Suppose (cid:174)𝐷 is a DAG on [𝑛]. Define the weight enumerator for enriched (cid:174)𝐷-partitions to be the

formal power series

Δ (cid:174)𝐷 :=

∑︁

(cid:214)

𝑥| 𝑓 (𝑖)|,

𝑓 ∈E ( (cid:174)𝐷)

𝑖∈[𝑛]

where E ( (cid:174)𝐷) is the set of enriched (cid:174)𝐷-partitions. By the Fundamental Lemma 5.1.5, one has

Δ (cid:174)𝐷 =

∑︁

Δ𝜋.

𝜋∈L ( (cid:174)𝐷)

(5.1.2)

It is clear from equation (5.1.1) that Δ𝜋 is a homogeneous quasisymmetric function. More generally,

Δ (cid:174)𝐷 is a homogeneous quasisymmetric function in QSym.

It also follows from equation (5.1.1) that the weight enumerator Δ𝜋 depends only on the descent

set Des 𝜋. A less obvious but important observation, that Δ𝜋 depends only on the peak set Pk 𝜋,

will follow directly from the following proposition, proved by Stembridge in [Ste97].

64

Proposition 5.1.7 ([Ste97, Proposition 2.2]). As a quasisymmetric function, Δ𝜋 has the following

expansion in terms of monomial quasisymmetric functions:

Δ𝜋 =

∑︁

2|𝐸 |+1𝑀𝑛,𝐸 ,

𝐸 ⊆[𝑛−1] :
Pk 𝜋⊆𝐸∪(𝐸+1)

where the set 𝐸 + 1 is defined by (2.1.1).

(5.1.3)

□

As a counterpart, the weight enumerator Δ𝜋 also has an expansion in terms of another basis:

the fundamental quasisymmetric functions.

Proposition 5.1.8 ([Ste97, Proposition 3.5]). As a quasi-symmetric function, Δ𝜋 has the following

expansion in terms of fundamental quasisymmetric functions:

Δ𝜋 = 2pk 𝜋+1

∑︁

𝐹𝑛,𝐷 .

𝐷⊆[𝑛−1] : Pk 𝜋⊆𝐷△(𝐷+1)

Here △ denotes symmetric difference, that is, 𝐷△𝐸 = (𝐷 ∪ 𝐸) \ (𝐷 ∩ 𝐸).

Definition 5.1.9 (Peak set). A subset 𝑆 ⊆ [𝑛] is a peak set in [𝑛] if Pk 𝜋 = 𝑆 for some 𝜋 ∈ S𝑛.

For any peak set 𝑆 in [𝑛], from the above proposition we can define an associated quasisymmetric

function by

𝐾𝑛,𝑆 := Δ𝜋,

where 𝜋 is any permutation with peak set 𝑆.

It follows that Δ𝜋 = 𝐾𝑛,Pk 𝜋 and one can rewrite

equation (5.1.2) as

Δ (cid:174)𝐷 =

∑︁

𝐾𝑛,Pk 𝜋.

𝜋∈L ( (cid:174)𝐷)

Let Π𝑛 denote the space of quasisymmetric functions spanned by 𝐾𝑛,𝑆, taken over all peak sets

in [𝑛], and set Π = ⊕𝑛≥0Π𝑛. In [Ste97] Stembridge referred to Π as the algebra of peaks, and

proved that Π is a graded subring of QSym.

65

5.1.4 Order Polynomial

Given a DAG (cid:174)𝐷, we can define the order polynomial of enriched (cid:174)𝐷-partitions, Ω( (cid:174)𝐷, 𝑚), by

Ω( (cid:174)𝐷, 𝑚) = Δ (cid:174)𝐷 (1𝑚),

where Δ (cid:174)𝐷 (1𝑚) means that we set 𝑥1 = · · · = 𝑥𝑚 = 1, and 𝑥𝑘 = 0 for 𝑘 > 𝑚. In fact, Ω( (cid:174)𝐷, 𝑚) counts
the number of enriched (cid:174)𝐷-partitions with absolute value at most 𝑚.

Stembridge computed the corresponding generating function as follows:

Theorem 5.1.10 ([Ste97, Theorem 4.1]). For a given 𝜋 ∈ S𝑛, one has

Ω(𝜋, 𝑚)𝑡𝑚 =

∑︁

𝑚

(cid:18) 1 + 𝑡
1 − 𝑡

1
2

(cid:19) 𝑛+1 (cid:18)

(cid:19) 1+pk 𝜋

.

4𝑡
(1 + 𝑡)2

(5.1.4)

It is not hard to see that Ω( (cid:174)𝐷, 𝑡) is indeed a polynomial in 𝑡. If (cid:174)𝐷 has vertex set 𝑉 and |𝑉 | = 𝑛,

then

Ω( (cid:174)𝐷, 𝑚) =

𝑛
∑︁

𝑘=1

𝑐𝑘

(cid:19)

,

(cid:18)𝑚
𝑘

where 𝑐𝑘 denotes the number of 𝑓 ∈ E ( (cid:174)𝐷) such that {| 𝑓 (𝑥)| : 𝑥 ∈ 𝑉 } = [𝑘]. For any fixed 𝑘, (cid:0)𝑚
𝑘

(cid:1)

is a polynomial in 𝑚 of degree 𝑘. Since 𝑐𝑘 and 𝑛 are constants, it follows that the summation is

also a polynomial in 𝑚. This verifies that Ω( [ (cid:174)𝐷], 𝑡) is a polynomial.

Clearly, one can get a formula for Ω(𝜋, 𝑚) by taking the coefficient of 𝑡𝑚 on both sides of

equation (5.1.4). Here we provide a combinatorial explanation for this formula of Ω(𝜋, 𝑚). We

define the (𝜋, 𝑚)-marking for a permutation 𝜋 and a positive integer 𝑚, and show that each (𝜋, 𝑚)-

marking corresponds to exactly 22 pk 𝜋+1 enriched 𝜋-partitions with absolute value at most 𝑚.

Suppose 𝜋 ∈ S𝑛, 𝑚 ∈ P. One can naturally extend 𝜋 = 𝜋1 . . . 𝜋𝑛 to 𝜋′ = 𝜋0𝜋1 . . . 𝜋𝑛𝜋𝑛+1 where

𝜋0 = 𝜋𝑛+1 = ∞. Let 𝑅1 be the longest decreasing initial factor of 𝜋′. Now let 𝜏 denote 𝜋′ with 𝑅1

deleted, and let 𝑅2 be the longest increasing initial factor of 𝜏. Continue in this way, alternating

between decreasing and increasing factors to get a factorization of 𝜋′. We call the factors runs and

the corresponding indices run indices. We denote by 𝐼 𝑗 the set of run indices corresponding to a

factor set 𝑅 𝑗 . Note that any extension 𝜋′ will start with a decreasing run and end with an increasing

run, which implies that the number of runs is always even.

66

Take

𝜋 =

1 2 3 4 5 6

1 4 3 2 5 6

as an example. The corresponding natural extension

has four runs

𝜋′ =

0

1 2 3 4 5 6

7

∞ 1 4 3 2 5 6 ∞

𝑅1 = ∞1, 𝑅2 = 4, 𝑅3 = 32, 𝑅4 = 56∞,

where the decreasing runs are in bold, and the corresponding set of run indices are

𝐼1 = {0, 1}, 𝐼2 = {2}, 𝐼3 = {3, 4}, 𝐼4 = {5, 6, 7}.

Suppose that the permutation 𝜋′ has 𝑟 runs. We have the following observations:

1. The parity of 𝑖 indicates the type of the run 𝑅𝑖. If 𝑖 is even, then 𝑅𝑖 is increasing. If 𝑖 is odd,

then 𝑅𝑖 is decreasing.

2. The total number of runs 𝑟 is closely related to the peak number pk 𝜋:

𝑟 = 2 pk 𝜋 + 2.

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 𝜋 with index 𝑖 ∈ [𝑛] can be marked if and only if 𝑖, 𝑖 + 1 ∈ 𝐼 𝑗 for some

𝑗; in other words, if 𝑖 and 𝑖 + 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 M𝜋 the set of indices of the columns that can be marked,

M𝜋 := {𝑖 ∈ [𝑛] | 𝑖, 𝑖 + 1 ∈ 𝐼 𝑗 for some 𝑗 }.

We note that for a given 𝜋, the cardinality of the complement of the set M𝜋 in [𝑛] is 2 pk 𝜋 + 1.

Equivalently, one has |M𝜋 | = 𝑛 − 2 pk 𝜋 − 1.

67

1 2
1 4

3 4 5 6
3 2 5 6

1 2 3 4 5 6
1 4 3 2 5 6

Figure 5.1 Two examples of (𝜋, 5)-markings

Definition 5.1.11 ((𝜋, 𝑚)-marking). Suppose that 𝜋 is a linear permutation and 𝑚 is a positive

integer. A (𝜋, 𝑚)-marking is a marking of 𝜋 using 𝑏 bars and 𝑑 marked columns, satisfying that

𝑏 + 𝑑 = 𝑚 − 1 − pk 𝜋.

Example 5.1.12. If we set 𝜋 = 143256 as before, and take 𝑚 = 5, then a (𝜋, 5)-marking has 𝑏 bars

and 𝑑 marked columns, such that 𝑏 + 𝑑 = 3. Two (𝜋, 5)-markings are provided in Figure 5.1.12.

Both have two bars and one marked column, where the marked column is in blue.

Proposition 5.1.13. For a given 𝜋 ∈ 𝔖𝑛, one has

Ω(𝜋, 𝑚) = 22 pk 𝜋+1

𝑚−1−pk 𝜋
∑︁

(cid:18)(cid:18)𝑛 + 1
𝑘

(cid:19)(cid:19) (cid:18) 𝑛 − 2 pk 𝜋 − 1
𝑚 − 1 − pk 𝜋 − 𝑘

(cid:19)

,

(5.1.5)

𝑘=0
(cid:1)) denotes the number of multisets on [𝑛 + 1] with cardinality 𝑘.

where ( (cid:0)𝑛+1
𝑘

Proof. It is clear by definition that the number of possible choices for (𝜋, 𝑚)-markings is

∑︁

𝑏+𝑑=𝑚−1−pk 𝜋

(cid:18) (cid:18)𝑛 + 1
𝑏

(cid:19) (cid:19) (cid:18)𝑛 − 2 pk 𝜋 − 1

(cid:19)

𝑑

𝑚−1−pk 𝜋
∑︁

=

𝑘=0

(cid:18)(cid:18)𝑛 + 1
𝑘

(cid:19)(cid:19) (cid:18) 𝑛 − 2 pk 𝜋 − 1
𝑚 − 1 − pk 𝜋 − 𝑘

(cid:19)

.

Therefore, it suffices to construct a 22 pk 𝜋+1-to-one map from the set of enriched 𝜋-partitions with

absolute value at most 𝑚 to the set of all (𝜋, 𝑚)-markings.

Given an enriched 𝜋-partition 𝑓 with absolute value at most 𝑚, we can inductively associate to

it a unique (𝜋, 𝑚)-marking as follows: We first determine, for each 𝑘 ∈ M𝜋, whether column 𝑘

gets marked. Suppose 𝑘 ∈ 𝐼𝑖 for some 𝑖 ∈ [𝑟]. We mark column 𝑘 if and only if 𝛿𝑘 + 𝛾𝑘 = 1 where

𝛿𝑘 := 𝛿 (𝑖 is even and 𝑓 (𝜋𝑘 ) < 0),

𝛾𝑘 := 𝛿 (𝑖 is odd and 𝑓 (𝜋𝑘 ) > 0).

Here the Kronecker function on a statement 𝑅 is defined by

𝛿(𝑅) =

1

0





if 𝑅 is true,

.

if 𝑅 is false.

68

As for the placement of bars, we start by putting | 𝑓 (𝜋1)| − 1 bars before the first column.

Inductively, suppose that 𝑘 ∈ 𝐼𝑖 for some 𝑘 ∈ [2, 𝑛], 𝑖 ∈ [𝑟] and we have already constructed the

markings and bars on and before the (𝑘 − 1)st column. Then the number of marks and bars strictly

before the 𝑘th column is constructed to be

| 𝑓 (𝜋𝑘 )| − ⌈𝑖/2⌉ − 𝛿𝑘 .

(5.1.6)

Finally we add bars after the last column so that the total number of marks and bars is 𝑚 − pk 𝜋 − 1.

In this manner, we can inductively define a unique (𝜋, 𝑚)-marking for 𝑓 .

We must verify that the constructed marking is indeed a (𝜋, 𝑚)-marking. Firstly we will verify

that (5.1.6) is a weakly increasing function of 𝑘, and strictly increasing from the 𝑘th to the (𝑘 + 1)st

term if column 𝑘 is marked. In other words, if 𝑘 ∈ 𝐼𝑖 and 𝑘 + 1 ∈ 𝐼 𝑗 , it suffices to show that

| 𝑓 (𝜋𝑘 )| − ⌈𝑖/2⌉ − 𝛿𝑘 ≤ | 𝑓 (𝜋𝑘+1)| − ⌈ 𝑗/2⌉ − 𝛿𝑘+1,

for all 𝑘, and that

| 𝑓 (𝜋𝑘 )| − ⌈𝑖/2⌉ − 𝛿𝑘 < | 𝑓 (𝜋𝑘+1)| − ⌈ 𝑗/2⌉ − 𝛿𝑘+1,

if column 𝑘 is marked. Notice that

(𝛿𝑘 + 𝛾𝑘 ) · 𝛿(𝑘 ∈ M𝜋) = 1

if column 𝑘 is marked and 0 otherwise. Hence it suffices to show that

| 𝑓 (𝜋𝑘 )| − ⌈𝑖/2⌉ − 𝛿𝑘 + (𝛿𝑘 + 𝛾𝑘 ) · 𝛿(𝑘 ∈ M𝜋) ≤ | 𝑓 (𝜋𝑘+1)| − ⌈ 𝑗/2⌉ − 𝛿𝑘+1.

(5.1.7)

By the definition of enriched 𝑃-partitions, we have

| 𝑓 (𝜋𝑘 )| ≤ | 𝑓 (𝜋𝑘+1)|.

(5.1.8)

Let us consider the following cases:

(a) If 𝑗 = 𝑖, it follows that 𝑘 ∈ M𝜋. Hence inequality (5.1.7) simplifies to

| 𝑓 (𝜋𝑘 )| + 𝛾𝑘 ≤ | 𝑓 (𝜋𝑘+1)| − 𝛿𝑘+1.

69

If 𝑖 is even, then 𝛾𝑘 = 0 and 𝜋𝑘 < 𝜋𝑘+1. By inequality (5.1.8), one only needs to consider

whether the inequality holds when 𝛿𝑘+1 = 1, which implies 𝑓 (𝜋𝑘+1) < 0. It follows from

the definition of enriched 𝑃-partitions that 𝑓 (𝜋𝑘 ) ⪯ 𝑓 (𝜋𝑘+1), namely | 𝑓 (𝜋𝑘 )| < | 𝑓 (𝜋𝑘+1)| or

𝑓 (𝜋𝑘 ) = 𝑓 (𝜋𝑘+1) < 0, but the second possibility contradicts 𝜋𝑘 < 𝜋𝑘+1. This proves (5.1.7)

in this case. The proof is similar when 𝑖 is odd.

(b) If 𝑗 = 𝑖 + 1, then 𝑘 ∉ M𝜋. Inequality (5.1.7) reduces to

| 𝑓 (𝜋𝑘 )| − ⌈𝑖/2⌉ − 𝛿𝑘 ≤ | 𝑓 (𝜋𝑘+1)| − ⌈(𝑖 + 1)/2⌉ − 𝛿𝑘+1.

If 𝑖 is even, then 𝜋𝑘 > 𝜋𝑘+1, ⌈𝑖/2⌉ + 1 = ⌈(𝑖 + 1)/2⌉ and 𝑗 is odd, hence 𝛿𝑘+1 = 0. Therefore

one only needs to prove

| 𝑓 (𝜋𝑘 )| − 𝛿𝑘 ≤ | 𝑓 (𝜋𝑘+1)| − 1.

The inequality clearly holds when 𝛿𝑘 = 1, so it suffices to consider the case when 𝛿𝑘 = 0.

In this case, 𝑓 (𝜋𝑘 ) > 0, hence by the definition of enriched 𝑃-partitions, or equivalently

| 𝑓 (𝜋𝑘+1)| ≥ | 𝑓 (𝜋𝑘 )| + 1, proves (5.1.7). The case when 𝑖 is odd is similar and left to the

reader.

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 𝑚 − pk 𝜋 − 1. In other words, the number of bars we
add after the 𝑛th column is nonnegative. Notice that ⌈ 𝑖
the 𝑘-th column. Since 𝑛 ∈ 𝐼𝑟, this implies that ⌈ 𝑟

2⌉ − 1 counts the number of peaks before
2⌉ = pk 𝜋 + 1. By (5.1.6) the total number of
bars and marked columns before the 𝑛th column is | 𝑓 (𝜋𝑛)| − pk 𝜋 − 1 − 𝛿𝑛. Together with the fact

that the 𝑛th column is marked if and only if 𝛿𝑛 + 𝛾𝑛 = 1 and 𝑛 ∈ M𝜋, the total number of bars that

should be added after the 𝑛th column is

𝑚 − pk 𝜋 − 1 − (| 𝑓 (𝜋𝑛)| − pk 𝜋 − 1 − 𝛿𝑛) − (𝛿𝑛 + 𝛾𝑛) · 𝛿(𝑛 ∈ M𝜋)

= 𝑚 − | 𝑓 (𝜋𝑛)| + 𝛿𝑛 − (𝛿𝑛 + 𝛾𝑛) · 𝛿(𝑛 ∈ M𝜋).

Hence the nonnegativity condition becomes

𝑚 − | 𝑓 (𝜋𝑛)| + 𝛿𝑛 − (𝛿𝑛 + 𝛾𝑛) · 𝛿(𝑛 ∈ M𝜋) ≥ 0,

70

or equivalently,

𝑚 − | 𝑓 (𝜋𝑛)| ≥ (𝛿𝑛 + 𝛾𝑛) · 𝛿(𝑛 ∈ M𝜋) − 𝛿𝑛.

(5.1.9)

By assumption 𝑓 has absolute value at most 𝑚, hence 𝑚 − | 𝑓 (𝜋𝑛)| ≥ 0. Therefore, one only

needs to check that the inequality holds when (𝛿𝑛 + 𝛾𝑛) · 𝛿(𝑛 ∈ M𝜋) − 𝛿𝑛 = 1, namely 𝛿𝑛 + 𝛾𝑛 = 1,

𝛿(𝑛 ∈ M𝜋) = 1 and 𝛿𝑛 = 0, or equivalently, 𝑛 ∈ 𝐼𝑖 where 𝑖 is odd, 𝑓 (𝜋𝑛) > 0 and 𝑛 ∈ M𝜋. This is

a contradiction since 𝑛 + 1 must be in a run where the index is even by definition, which implies

that 𝑛 and 𝑛 + 1 cannot be in the same run index set, hence 𝑛 ∉ M𝜋. This completes the proof of

inequality (5.1.9). It therefore follows that the marking we constructed is indeed a (𝜋, 𝑚)-marking.

Now we need to show that for a given (𝜋, 𝑚)-marking, there are 22 pk 𝜋+1 different associated

functions. From the above construction we notice that for each 𝑘 ∈ M𝜋,

𝑓 (𝜋𝑘 ) is uniquely

determined. More precisely, whether column 𝑘 gets marked determines 𝛿𝑘 and 𝛾𝑘 as 𝑘 determines

the parity of 𝑖, hence the sign of 𝑓 (𝜋𝑘 ) is determined by the definitions of 𝛿𝑘 and 𝛾𝑘 . Suppose

𝑘 ∈ 𝐼𝑖. The number of marks and bars strictly before the 𝑘th column determines the value

| 𝑓 (𝜋𝑘 )| − ⌈𝑖/2⌉ − 𝛿𝑘 , therefore it determines 𝑓 (𝜋𝑘 ) as well. The only ambiguity is about 𝑓 (𝜋𝑘 )

for 𝑘 ∉ M𝜋. As the number of marks and bars strictly before the 𝑘th column fixes the value

𝐿 = | 𝑓 (𝜋𝑘 )| − ⌈𝑖/2⌉ − 𝛿𝑘 , there are two possible choices of the value 𝑓 (𝜋𝑘 ) for each 𝑘 ∉ M𝜋:

if 𝑖 is even, then either 𝑓 (𝜋𝑘 ) = −(𝐿 + ⌈𝑖/2⌉ + 1) or 𝑓 (𝜋𝑘 ) = 𝐿 + ⌈𝑖/2⌉; if 𝑖 is odd, then either

𝑓 (𝜋𝑘 ) = 𝐿 + ⌈𝑖/2⌉ or 𝑓 (𝜋𝑘 ) = −(𝐿 + ⌈𝑖/2⌉). It follows that there are 22 pk 𝜋+1 different functions

corresponding to a given (𝜋, 𝑚)-marking.

□

Example 5.1.14. Consider the permutation 𝜋 = 143256, and an example of enriched 𝜋-partitions

𝑓 is defined as follows:

𝑓 (1) = 1,

𝑓 (4) = −2,

𝑓 (3) = −4,

𝑓 (2) = −4,

𝑓 (5) = −5,

𝑓 (6) = 5.

The corresponding marking is the first one in the Figure 5.1.12.

5.2 Enriched Partitions for Toric DAGs

In this section, we review the toric DAGs and toric posets as cyclic analogues of DAGs and

posets. Then we define enriched toric [ (cid:174)𝐷]-partitions and develop some of their properties. The

71

concept of toric poset was originally defined and studied by Develin, Macauley and Reiner in

[DMR16]. Here we follow the presentation from Adin, Gessel, Reiner and Roichman [AGRR21].

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 𝜋 is a linear extension

of the DAG (cid:174)𝐷, then [𝜋] is a toric extension of the corresponding toric DAG [ (cid:174)𝐷].

5.2.1 Toric DAGs and Toric Posets

A DAG (cid:174)𝐷 on [𝑛] has 𝑖0 ∈ [𝑛] as a source (respectively, sink) if (cid:174)𝐷 does not contain 𝑗 → 𝑖0
(respectively, 𝑖0 → 𝑗) for any 𝑗 ∈ [𝑛]. Suppose 𝑖0 is a source or a sink in (cid:174)𝐷, we say (cid:174)𝐷′ is
obtained from (cid:174)𝐷 by a flip at 𝑖0 if (cid:174)𝐷′ is obtained by reversing all arrows containing 𝑖0. We define
the equivalence relation ≡ on DAGs as follows: (cid:174)𝐷′ ≡ (cid:174)𝐷 if and only if (cid:174)𝐷′ is obtained from (cid:174)𝐷 by a

sequence of flips. A toric DAG is the equivalence class [ (cid:174)𝐷] of a DAG (cid:174)𝐷.

In particular, if (cid:174)𝐷 = 𝜋 = 𝜋1𝜋2 . . . 𝜋𝑛 is a total linear order, the next proposition claims that the

corresponding toric DAG [ (cid:174)𝐷] can be identified with the cyclic permutation [𝜋].

Proposition 5.2.1 ([DMR16, Proposition 4.2]). If (cid:174)𝐷 = 𝜋 is a total linear order with 𝜋 = 𝜋1 . . . 𝜋𝑛,
then there is a bijection between toric DAG [ (cid:174)𝐷] and cyclic permutation [𝜋].

□

Example 5.2.2. The total linear order (cid:174)𝐷1 = 2431 from Example 5.1.2 has a corresponding toric
DAG [ (cid:174)𝐷1]:

3

4

1

2

1

2

(cid:174)𝐷1 = 2431

3

4

1

2

3

4

1

2

3

4

(cid:174)𝐷′

1 = 1243

(cid:174)𝐷′′

1 = 3124

(cid:174)𝐷′′′

1 = 4312

They can be obtained by a sequence of flips:

(cid:174)𝐷1

flip at 1
−−−−−→ (cid:174)𝐷′
1

flip at 3
−−−−−→ (cid:174)𝐷′′
1

flip at 4
−−−−−→ (cid:174)𝐷′′′
1

flip at 2
−−−−−→ (cid:174)𝐷1.

Therefore it is easy to see that [ (cid:174)𝐷1] can be identified with [2431] = { 2431, 1243, 3124, 4312 }.

72

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 (cid:174)𝐷 with vertex set [𝑛] is toric transitive if the existence of a directed path 𝑖1 → 𝑖2 →

· · · → 𝑖𝑘 and 𝑖1 → 𝑖𝑘 implies the existence of 𝑖𝑎 → 𝑖𝑏 in (cid:174)𝐷 for all 1 ≤ 𝑎 < 𝑏 ≤ 𝑘.

Definition 5.2.3 (Toric poset). A toric DAG [ (cid:174)𝐷] is a toric poset if (cid:174)𝐷′ is toric transitive for some

(cid:174)𝐷′ ∈ [ (cid:174)𝐷], or equivalently from [AGRR21, Proposition 3.10] , for all representatives (cid:174)𝐷′.

In this paper, we adopt the definition of toric posets from [AGRR21], which is not quite the same

as it was originally defined in [DMR16], but they are essentially equivalent by [DMR16, Theorem

1.4].

Definition 5.2.4 (Total cyclic order). A toric poset is a total cyclic order if one (or equivalently, all,

according to Proposition 5.2.1) representative is a total linear order.

In this case, we usually use the corresponding cyclic permutation [𝜋] to denote the total cyclic

order [ (cid:174)𝐷].

exist (cid:174)𝐷′

𝑖 ∈ [ (cid:174)𝐷𝑖] for 𝑖 = 1, 2 such that (cid:174)𝐷′

For two toric DAGs [ (cid:174)𝐷1], [ (cid:174)𝐷2] on the same vertex set [𝑛], we say [ (cid:174)𝐷2] extends [ (cid:174)𝐷1] if there
1. If, furthermore, [ (cid:174)𝐷2] is a total cyclic order
corresponding to the cyclic permutation [𝜋], we also say that [𝜋] torically extends [ (cid:174)𝐷1]. Let
Ltor([ (cid:174)𝐷]) denote the set of cyclic permutations [𝜋] which torically extend [ (cid:174)𝐷].

2 extends (cid:174)𝐷′

Example 5.2.5. In Example 5.1.2, both [ (cid:174)𝐷1] = [2431] and [ (cid:174)𝐷2] = [2413] torically extend [ (cid:174)𝐷3].
Moreover, they are the only total cyclic orders that torically extend [ (cid:174)𝐷3], namely Ltor( [ (cid:174)𝐷3]) =

{[2431], [2413]}.

In fact, Figure 5.2 lists all representatives of [ (cid:174)𝐷3], and it is straightforward to check that every

total linear order linearly extending some DAG in [ (cid:174)𝐷3] is in either [2431] or [2413].

5.2.2 Enriched Toric [ (cid:174)𝐷]-Partition

Definition 5.2.6 (Enriched toric [ (cid:174)𝐷]-partition). An enriched toric [ (cid:174)𝐷]-partition is a function 𝑓 :

[𝑛] → P′ which is an enriched (cid:174)𝐷′-partition for at least one DAG (cid:174)𝐷′ in [ (cid:174)𝐷]. Let Etor( [ (cid:174)𝐷]) denote

73

1

2

(cid:174)𝐷3

3

4

1

2

1

2

(cid:174)𝐷′
3

3

4

3

4

1

2

1

2

3

4

(cid:174)𝐷′′
3

3

4

(cid:174)𝐷′′′
3

(cid:174)𝐷′′′′
3

Figure 5.2 All representatives of [ (cid:174)𝐷3]

the set of all enriched toric [ (cid:174)𝐷]-partitions.

If [ (cid:174)𝐷] = [𝜋] is a total cyclic order, the set of enriched toric [𝜋]-partitions is the union of the

set of enriched 𝜋′-partitions for all representatives 𝜋′ of [𝜋]:

Etor( [𝜋]) =

E (𝜋′).

(cid:216)

𝜋′∈[𝜋]

(5.2.1)

As in the linear case, we have the following fundamental lemma for the decomposition of

enriched toric [ (cid:174)𝐷]-partitions. The proof is analogous to [AGRR21, Lemma 3.15].

Lemma 5.2.7 (Fundamental lemma of enriched toric [ (cid:174)𝐷]-partitions). For a DAG (cid:174)𝐷, the set of all

enriched toric [ (cid:174)𝐷]-partitions is a disjoint union of the set of enriched toric [𝜋]-partitions of all

toric extensions [𝜋] of [ (cid:174)𝐷]:

Etor([ (cid:174)𝐷]) =

(cid:196)

E𝑡𝑜𝑟 ( [𝜋]).

[𝜋]∈Ltor ([ (cid:174)𝐷])

Proof. By the definition of Etor([ (cid:174)𝐷]), one has

Etor( [ (cid:174)𝐷]) =

(cid:216)

E ( (cid:174)𝐷′).

(cid:174)𝐷′∈[ (cid:174)𝐷]

74

In particular when [ (cid:174)𝐷] = [𝜋] is a total cyclic order, it follows from Proposition 5.2.1 that,

Hence,

Etor( [𝜋]) =

E (𝜋′).

(cid:216)

𝜋′∈[𝜋]

Etor([ (cid:174)𝐷]) =

(cid:216)

E ( (cid:174)𝐷′)

(cid:174)𝐷′∈[ (cid:174)𝐷]
(cid:216)

(𝑖)
=

(cid:216)

E (𝜋′)

(cid:174)𝐷′∈[ (cid:174)𝐷]

𝜋′∈L ( (cid:174)𝐷′)

(𝑖𝑖)
=

=

(cid:216)

(cid:216)

E (𝜋′)

𝜋′∈[𝜋]

[𝜋]∈Ltor ([ (cid:174)𝐷])
(cid:216)

Etor( [𝜋]).

[𝜋]∈Ltor ([ (cid:174)𝐷])

To justify these steps, first note that equality (𝑖) follows from Lemma 5.1.5.

As for equality (𝑖𝑖), it suffices to show that 𝜋′ ∈ L ( (cid:174)𝐷′) for some (cid:174)𝐷′ ∈ [ (cid:174)𝐷] if and only if 𝜋′ ∈ [𝜋]

for some [𝜋] ∈ Ltor([ (cid:174)𝐷]). For the forward direction, if 𝜋′ ∈ L ( (cid:174)𝐷′) for some (cid:174)𝐷′ ∈ [ (cid:174)𝐷], then [𝜋′]

torically extends [ (cid:174)𝐷′] = [ (cid:174)𝐷]. While for the reverse implication, given 𝜋′ ∈ [𝜋] ∈ Ltor( [ (cid:174)𝐷]), pick

(cid:174)𝐷′′ ∈ [ (cid:174)𝐷] and 𝜋′′ ∈ [𝜋] with 𝜋′′ linearly extending (cid:174)𝐷′′, then [𝜋′′] = [𝜋′] = [𝜋]. It follows that

there exists a sequence of flips which takes 𝜋′′ to 𝜋′. Now applying the same sequence of flips to

(cid:174)𝐷′′ will result in some (cid:174)𝐷′. One then has (cid:174)𝐷′ ∈ [ (cid:174)𝐷′′] = [ (cid:174)𝐷] and 𝜋′ ∈ L ( (cid:174)𝐷′) as desired.

The assertion of disjointness follows directly from the fact that every function 𝑓 : [𝑛] → P′ has

a unique linear permutation 𝜋 ∈ S𝑛 such that 𝑓 is also an enriched 𝜋-partition, hence an enriched

toric [𝜋]-partition. Such a linear permutation 𝜋 can be similarly constructed as in the proof of

Lemma 5.1.5, so the details are omitted. This completes the proof.

□

5.2.3 Weight Enumerator

Definition 5.2.8 (Weight enumerator). For a given toric poset [ (cid:174)𝐷] with vertex set [𝑛], we define

the weight enumerator for enriched toric [ (cid:174)𝐷]-partitions by the formal power series

Δcyc
[ (cid:174)𝐷]

:=

∑︁

(cid:214)

𝑥| 𝑓 (𝑖)|.

𝑓 ∈Etor ([ (cid:174)𝐷])

𝑖∈[𝑛]

75

Namely, for integer 𝑘 > 0 we assign the weight 𝑥𝑘 to both 𝑓 -values 𝑘 and −𝑘.

As a direct consequence of the Fundamental Lemma 5.2.7, one has

Δcyc
[ (cid:174)𝐷]

=

∑︁

Δcyc
[𝜋]

.

[𝜋]∈Ltor ([ (cid:174)𝐷])

(5.2.2)

Therefore, it suffices to discuss Δcyc

[𝜋] for cyclic permutations [𝜋]. It follows from the formula (5.2.1)

that Δcyc

[𝜋] can be expressed in terms of the weight enumerators {Δ𝜏} as

Δcyc

[𝜋] =

∑︁

Δ𝜏.

𝜏∈[𝜋]

Moreover, Δcyc

[𝜋] has the following expression.

Proposition 5.2.9. For any given cyclic permutation [𝜋] of length 𝑛, we have

Δ

𝑐𝑦𝑐
[𝜋] =

∑︁

2|𝐸 | 𝑀 𝑐𝑦𝑐
𝑛,𝐸 ,

𝐸 ⊆[𝑛]:
cPk(𝜋)⊆𝐸∪(𝐸+1)

(5.2.3)

(5.2.4)

with 𝐸 + 1 defined by (2.1.1). The sum is independent of the choice of representative 𝜋 of [𝜋].

Proof. The independence of the choice of representatives is a result of the following two observa-

tions:

(a) If 𝐸 and 𝐸′ only differ by a cyclic shift, one has |𝐸 | = |𝐸′| and 𝑀 𝑐𝑦𝑐

𝑛,𝐸 = 𝑀 𝑐𝑦𝑐
𝑛,𝐸 ′.

(b) For two representatives 𝜋 and 𝜋′ of [𝜋],

{𝐸 ⊆ [𝑛] : cPk(𝜋) ⊆ 𝐸 ∪ (𝐸 + 1)} = {𝐸′ ⊆ [𝑛] : cPk(𝜋′) ⊆ 𝐸′ ∪ (𝐸′ + 1)} + 𝑖,

for some 𝑖 ∈ [𝑛], namely, the two sets only differ by a cyclic shift.

Now fix a representative 𝜋 of [𝜋]. We rewrite both sides of equation (5.2.4) as follows:

RHS

(𝑖)
=

∑︁

𝐹⊆[𝑛]:
cPk(𝜋)⊆𝐹∪(𝐹+1)

2|𝐹 | ∑︁
𝑓 ∈𝐹

𝑀𝑛,(𝐹− 𝑓 )∩[𝑛−1]

(𝑖𝑖)
=

∑︁

2|𝐸 |+1𝛼𝐸 𝑀𝑛,𝐸

(5.2.5)

𝐸 ⊆[𝑛−1]

76

where 𝛼𝐸 = #𝐴𝐸 , with

𝐴𝐸 = {(𝐹, 𝑓 ) : 𝑓 ∈ 𝐹 ⊆ [𝑛] with cPk(𝜋) ⊆ 𝐹 ∪ (𝐹 + 1), 𝐸 = (𝐹 − 𝑓 ) ∩ [𝑛 − 1]}.

Here equality (𝑖) is a result of applying equation (2.3.1) to move from cyclic monomial to monomial

quasisymmetric functions, while equality (𝑖𝑖) is obtained by calculating the coefficient of 𝑀𝑛,𝐸 .

It is noted that in equality (𝑖𝑖), for each pair (𝐹, 𝑓 ) ∈ 𝐴𝐸 , we have 𝑛 ∈ 𝐹 − 𝑓 . As a result,

𝐸 = (𝐹 − 𝑓 ) ∩ [𝑛 − 1] = (𝐹 − 𝑓 ) \ {𝑛}. Therefore their cardinalities satisfy |𝐹 | = |𝐸 | + 1.

LHS

(𝑖)′
=

∑︁

Δ𝜏

(𝑖𝑖)′
=

𝜏∈[𝜋]
∑︁

𝜏∈[𝜋]

∑︁

2|𝐸 |+1𝑀𝑛,𝐸

𝐸 ⊆[𝑛−1]:
Pk(𝜏)⊆𝐸∪(𝐸+1)

(𝑖𝑖𝑖)′
=

∑︁

𝛽𝐸 2|𝐸 |+1𝑀𝑛,𝐸

𝐸 ⊆[𝑛−1]

(5.2.6)

where 𝛽𝐸 = #𝐵𝐸 with

𝐵𝐸 = {𝑖 ∈ [𝑛] : (cPk 𝜋 − 𝑖) ∩ [2, 𝑛 − 1] ⊆ 𝐸 ∪ (𝐸 + 1)}.

Equality (𝑖)′ follows from equation (5.2.3). Equality (𝑖𝑖)′ is obtained by applying equation (5.1.3)

to express the weight enumerator Δ𝜏 in terms of monomial quasisymmetric functions.

Equality (𝑖𝑖𝑖)′ follows from the observation

{{ Pk(𝜏) : 𝜏 ∈ [𝜋] }} = {{ (cPk 𝜋 − 𝑖) ∩ [2, 𝑛 − 1] : 𝑖 ∈ [𝑛] }}.

By comparing equations (5.2.5) and (5.2.6), it suffices to prove that 𝛼𝐸 = 𝛽𝐸 for every 𝐸 ⊆

[𝑛 − 1], or equivalently, to construct a bijection between 𝐴𝐸 and 𝐵𝐸 .

Set 𝜃𝐸 : 𝐴𝐸 → 𝐵𝐸 as 𝜃𝐸 (𝐹, 𝑓 ) = 𝑓 . To prove that this map is well-defined, it suffices to

show that for each (𝐹, 𝑓 ) ∈ 𝐴𝐸 , we have 𝑓 ∈ 𝐵𝐸 .

It follows from the definition of 𝐴𝐸 that

𝐹 − 𝑓 = 𝐸 ∪ {𝑛}. Applying the operation on both sides of the inclusion cPk(𝜋) ⊆ 𝐹 ∪ (𝐹 + 1), we

get

cPk(𝜋) − 𝑓 ⊆ (𝐹 − 𝑓 ) ∪ (𝐹 − 𝑓 + 1) = 𝐸 ∪ (𝐸 + 1) ∪ {1, 𝑛}.

77

Hence (cPk 𝜋 − 𝑓 ) ∩ [2, 𝑛 − 1] ⊆ 𝐸 ∪ (𝐸 + 1) and 𝑓 ∈ 𝐵𝐸 .

Conversely, define 𝜎𝐸 : 𝐵𝐸 → 𝐴𝐸 by 𝜎𝐸 ( 𝑓 ) = ( (𝐸 + 𝑓 ) ∪ { 𝑓 }, 𝑓 ). One can similarly check

that this map is well-defined.

It is straightforward to verify that 𝜃𝐸 and 𝜎𝐸 are inverse to each other, hence we get a bijection

between 𝐴𝐸 and 𝐵𝐸 . This finishes the proof.

□

Remark 5.2.10. As a direct corollary of the above proposition, Δcyc
[ (cid:174)𝐷]

is a homogeneous cyclic

quasi-symmetric function of degree 𝑛, and that Δcyc

[𝜋] depends only on cPk[𝜋], or equivalently (by

Remark 1.2.1) on cPk 𝜋 for any representative 𝜋.

Example 5.2.11. Let 𝜏 = 1243 so that [𝜏] = {1243, 3124, 4312, 2431} and cPk(𝜏) = {3}; 𝜋 =

1324, [𝜋] = {1324, 4132, 2413, 3241} and cPk(𝜋) = {2, 4}.

To use Proposition 5.2.9 for calculation, we first need all possible choices of 𝐸 ⊆ [4] satisfying

{3} = cPk 𝜏 ⊆ 𝐸 ∪ (𝐸 + 1), which are

{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},

with corresponding monomial cyclic quasisymmetric functions

(1,1,1,1) = 𝑀 𝑐𝑦𝑐
𝑀 𝑐𝑦𝑐

4,{1,2,3,4}

,

(2,1,1) = 𝑀 𝑐𝑦𝑐
𝑀 𝑐𝑦𝑐

4,{1,2,3} = 𝑀 𝑐𝑦𝑐

4,{1,2,4} = 𝑀 𝑐𝑦𝑐

4,{1,3,4} = 𝑀 𝑐𝑦𝑐

4,{2,3,4}

,

(3,1) = 𝑀 𝑐𝑦𝑐
𝑀 𝑐𝑦𝑐

4,{1,2} = 𝑀 𝑐𝑦𝑐

4,{2,3} = 𝑀 𝑐𝑦𝑐

4,{3,4}

,

(2,2) = 𝑀 𝑐𝑦𝑐
𝑀 𝑐𝑦𝑐

4,{1,3} = 𝑀 𝑐𝑦𝑐

4,{2,4}

,

𝑀 𝑐𝑦𝑐
(4)

= 𝑀 𝑐𝑦𝑐

4,{2} = 𝑀 𝑐𝑦𝑐

4,{3}

.

Applying equation (5.2.4), we have

Δ

𝑐𝑦𝑐

[𝜏] = 24𝑀 𝑐𝑦𝑐

(1,1,1,1) + 4 · 23𝑀 𝑐𝑦𝑐

(2,1,1) + 3 · 22𝑀 𝑐𝑦𝑐

(3,1) + 2 · 22𝑀 𝑐𝑦𝑐

(2,2) + 2 · 2𝑀 𝑐𝑦𝑐

(4)

.

78

Similarly for 𝜋, all possible choices of 𝐸 ⊆ [4] satisfying {2, 4} = cPk 𝜋 ⊆ 𝐸 ∪ (𝐸 + 1) are as

follows:

{1, 2, 3, 4}, {1, 2, 3}, {1, 2, 4}, {1, 3, 4}, {2, 3, 4}, {1, 3}, {1, 4}, {2, 3}, {2, 4},

hence by equation (5.2.4),

Δ

𝑐𝑦𝑐

[𝜋] = 24𝑀 𝑐𝑦𝑐

(1,1,1,1) + 4 · 23𝑀 𝑐𝑦𝑐

(2,1,1) + 2 · 22𝑀 𝑐𝑦𝑐

(3,1) + 2 · 22𝑀 𝑐𝑦𝑐

(2,2)

.

It follows from the calculation above that

Δ

𝑐𝑦𝑐
[𝜏] + Δ

𝑐𝑦𝑐

[𝜋] = 2 · 24𝑀 𝑐𝑦𝑐

(1,1,1,1) + 8 · 23𝑀 𝑐𝑦𝑐

(2,1,1) + 5 · 22𝑀 𝑐𝑦𝑐

(3,1) + 4 · 22𝑀 𝑐𝑦𝑐

(2,2) + 2 · 2𝑀 𝑐𝑦𝑐

(4)

.

5.2.4 Algebra of Cyclic Peaks

Recall from Section 4.3.2 that 𝑆 is a cyclic peak set in [𝑛] if there exists some 𝜋 ∈ 𝔖𝑛 with

cPk 𝜋 = 𝑆. It follows from Proposition 5.2.9 that, for any cyclic peak set 𝑆 in [𝑛], we can define an

associated cyclic quasisymmetric function by

𝑛,𝑆 := Δcyc
𝐾 cyc
[𝜋]

,

for any permutation 𝜋 with cPk 𝜋 = 𝑆. One can observe that Δcyc

[𝜋] = 𝐾 cyc

𝑛,cPk 𝜋 and rewrite equa-

tion (5.2.2) as

Δcyc
[ (cid:174)𝐷]

=

∑︁

𝐾 cyc

𝑛,cPk 𝜋

.

[𝜋]∈Ltor ([ (cid:174)𝐷])

Moreover, it follows from formula (5.2.1) that 𝐾 cyc

𝑛,𝑆 can be expressed in terms of the quasisymmetric

functions {𝐾𝑛,𝑇 } as

where cPk 𝜋 = 𝑆.

𝐾 cyc

𝑛,𝑆 =

∑︁

¯𝜋∈[𝜋]

𝐾𝑛,Pk ¯𝜋,

Let Λ𝑛 denote the vector space of cyclic quasisymmetric functions spanned by 𝐾 cyc

𝑛,𝑆 where 𝑆
ranges over cyclic peak sets in [𝑛], and set Λ = ⊕𝑛≥0Λ𝑛. We will show that Λ is an algebra by
proving that the product of 𝐾 cyc

𝑛,𝑇 is a linear combination of 𝐾 cyc

𝑛,𝑆 ’s. We call Λ the algebra

𝑛,𝑈 and 𝐾 cyc

of cyclic peaks.

79

Lemma 5.2.12. The 𝐾 cyc

𝑛,𝑆 are linearly independent, where 𝑆 are, up to cyclic shift, distinct cyclic

peak sets.

Proof. For this proof, we totally order the subsets of [𝑛 − 1], first by cardinality, then by the

lexicographic order. We therefore have

∅ (cid:1) {1} (cid:1) {2} (cid:1) · · · (cid:1) {𝑛 − 1} (cid:1) {1, 2} (cid:1) {1, 3} (cid:1) · · · (cid:1) {1, 𝑛 − 1} (cid:1) {2, 3} (cid:1) {2, 4} (cid:1) · · · .

One can similarly order the compositions of 𝑛 as

(𝑛) (cid:1) (1, 𝑛 − 1) (cid:1) (2, 𝑛 − 2) (cid:1) · · · (cid:1) (1, 1, 𝑛 − 2) (cid:1) (1, 2, 𝑛 − 3) (cid:1) · · · (cid:1) (1, 𝑛 − 2, 1) (cid:1) · · · .

Noting that 𝐾 cyc

𝑛,𝑆′ if the sets 𝑆 and 𝑆′ only differ by a cyclic shift, we will always assume
the index set 𝑆 to be the least among all its cyclic shifts. It is not hard to see that 𝜓(𝑆) is also the

𝑛,𝑆 = 𝐾 cyc

least composition among all its cyclic shifts, where 𝜓 is defined by equation (2.1.3).

We now show that the matrix of {𝐾 cyc

𝑛,𝑆 } with respect to the basis {𝑀 cyc

𝑛,𝐿 } has full rank. Then

the linear independence of {𝐾 cyc

𝑛,𝑆 } will follow immediately from the fact that the monomial cyclic

quasi-symmetric functions form a basis of cQSym.

Let us fix 𝑛 and suppose {𝑆1 (cid:1) 𝑆2 (cid:1) . . . (cid:1) 𝑆𝑚} is the set of all distinct cyclic peak sets in [𝑛].

Given a 𝐾 cyc

𝑛,𝑆 , suppose |𝑆| = 𝑘 and 𝑆 = {1 = 𝑠1 < 𝑠2 < . . . < 𝑠𝑘 } for some 𝑛 ≥ 2 and 𝑘 ≥ 1. Here

all indices are taken modulo 𝑘 unless otherwise noted. To each 𝐾 cyc

𝑆 we associate a corresponding

monomial quasi-symmetric function by 𝐹 (𝐾 cyc

𝑛,𝑆 ) = 𝑀 cyc

𝑛, 𝑓 (𝑆), where

𝑓 (𝑆) = {𝑠1, 𝑠2 − 1, . . . , 𝑠𝑘 − 1}.

Since 𝑆 is a cyclic peak set, elements in 𝑓 (𝑆) are distinct. So 𝑓 (𝑆) is a set and 𝑓 is well-defined.

If one denotes 𝜓(𝑆) by (𝛼1, 𝛼2, . . . , 𝛼𝑘 ), then

𝜓( 𝑓 (𝑆)) = (𝛼1 − 1, 𝛼2, . . . , 𝛼𝑘−1, 𝛼𝑘 + 1).

Also notice that the assumption of 𝑆 being the least among its cyclic shifts (in particular, 𝛼1 =
min{𝛼𝑖}𝑛

𝑖=1) ensures that 𝑓 (𝑆) is also the least among all its cyclic shifts.

It follows that 𝑓

is

injective.

80

Claim: Consider the matrix of {𝐾 cyc

𝑛,𝑆 } with respect to the basis {𝑀 cyc

𝑛,𝐸 }. The square submatrix with

columns restricted to {𝑀 cyc

𝑛, 𝑓 (𝑆) } is upper triangular with nonzero diagonal entries. In particular, it

is invertible.

Let 𝐴𝑖, 𝑗 denote the coefficient of 𝑀 cyc

𝑛,𝑆𝑖 in terms of monomial cyclic
quasi-symmetric functions and set 𝐴 = ( 𝐴𝑖, 𝑗 ) to be the 𝑚 × 𝑚 matrix that we need to consider. To

𝑛, 𝑓 (𝑆 𝑗 ) in the expression of 𝐾 cyc

prove that 𝐴 is an upper triangular matrix, it suffices to show that 𝐴𝑖, 𝑗 = 0 if 𝑖 > 𝑗, or equivalently,

the term 𝑀 cyc

𝑛, 𝑓 (𝑆 𝑗 ) does not appear in the expression of 𝐾 cyc

𝑛,𝑆𝑖 if 𝑆 𝑗 (cid:1) 𝑆𝑖.

Suppose towards a contradiction that 𝐴𝑖, 𝑗 ≠ 0 for some 𝑖 > 𝑗. It then follows from Proposi-

tion 5.2.9 that there exists some 𝐸 ⊆ [𝑛] such that

𝑆𝑖 ⊆ 𝐸 ∪ (𝐸 + 1)

and 𝑀 cyc

𝑛, 𝑓 (𝑆 𝑗 ) = 𝑀 cyc
𝑛,𝐸 .

Since 𝑆𝑖 is a cyclic peak set, 𝑒 and 𝑒 + 1 cannot be in 𝑆𝑖 at the same time. It then follows from

the assumption 𝑆𝑖 ⊆ 𝐸 ∪ (𝐸 + 1) that |𝐸 | ≥ |𝑆𝑖 |. The condition 𝑖 > 𝑗 implies 𝑆𝑖 (cid:3) 𝑆 𝑗 , hence

|𝑆𝑖 | ≥ |𝑆 𝑗 | = | 𝑓 (𝑆 𝑗 )| = |𝐸 |. Therefore, we only need to consider the cases when 𝑆𝑖 and 𝑆 𝑗 have the

same cardinality.

Suppose

𝜓(𝑆𝑖) = (𝛼1, 𝛼2, . . . , 𝛼𝑘 ), 𝜓(𝑆 𝑗 ) = (𝛽1, 𝛽2, . . . , 𝛽𝑘 ), 𝜓(𝐸) = (𝛽′
1

, 𝛽′
2

, . . . , 𝛽′

𝑘 ).

Then 𝜓(𝐸) = (𝛽′
1

, 𝛽′
2

, . . . , 𝛽′

𝑘 ) is a cyclic shift of

𝜓( 𝑓 (𝑆 𝑗 )) = (𝛽1 − 1, 𝛽2, . . . , 𝛽𝑘−1, 𝛽𝑘 + 1).

Assume

(𝛽′

𝑞, 𝛽′

𝑞+1

, . . . , 𝛽′

𝑞−1) = (𝛽1 − 1, 𝛽2, . . . , 𝛽𝑘−1, 𝛽𝑘 + 1),

for some 𝑞 ∈ [𝑘]. Since 𝑆𝑖 ⊆ 𝐸 ∪ (𝐸 + 1), |𝑆𝑖 | = |𝐸 |, and 𝑆𝑖 does not have cyclically consecutive

elements, each 𝑎 ∈ 𝑆𝑖 corresponds to a unique 𝑎′ ∈ 𝐸 where 𝑎′ equals either 𝑎 or 𝑎 − 1 (considered

modulo 𝑛). A crucial observation therefore follows:

|(𝛼𝑟 + · · · + 𝛼𝑠) − (𝛽′

𝑟 + · · · + 𝛽′

𝑠)| ≤ 1

for 𝑟, 𝑠 ∈ [𝑘].

(5.2.7)

81

In particular,

𝛼1 ≤ 𝛼𝑞 ≤ 𝛽′

𝑞 + 1 = (𝛽1 − 1) + 1 = 𝛽1,

where the first inequality comes from the fact that 𝑆𝑖 is the least among its cyclic shifts, and the

second one follows from (5.2.7) by taking 𝑟 = 𝑠 = 𝑞. Note that 𝑆 𝑗 (cid:1) 𝑆𝑖 implies 𝜓(𝑆 𝑗 ) (cid:1) 𝜓(𝑆𝑖), so

𝛽1 ≤ 𝛼1. Thus, necessarily,

𝛼1 = 𝛼𝑞 = 𝛽′

𝑞 + 1 = 𝛽1.

It then follows from the inequality (5.2.7) that for any 𝑟 ∈ [𝑘 − 1],

𝛼𝑞 + · · · + 𝛼𝑞+𝑟 ≤ 𝛽′

𝑞 + · · · + 𝛽′

𝑞+𝑟 + 1 = 𝛽1 + · · · + 𝛽1+𝑟 + 𝛿1+𝑟,𝑘 ,

where 𝛿1+𝑟,𝑘 = 1 if 1 + 𝑟 = 𝑘 and 0 otherwise.

If 𝛼𝑞+𝑟 = 𝛽1+𝑟 for every 𝑟 ∈ [𝑘 − 2], then 𝜓(𝑆𝑖) is a cyclic shift of 𝜓(𝑆 𝑗 ), which contradicts our

assumption 𝑆𝑖 (cid:3) 𝑆 𝑗 . Now assume that 𝑡 ∈ [𝑘 − 2] is the smallest index such that 𝛼𝑞+𝑡 ≠ 𝛽1+𝑡. Then

necessarily 𝛼𝑞+𝑡 < 𝛽1+𝑡, and

(𝛼𝑞, . . . , 𝛼𝑞+𝑡) (cid:1) (𝛽1, . . . , 𝛽1+𝑡).

Combined with the inequality (𝛼1, . . . , 𝛼1+𝑡) (cid:2) (𝛼𝑞, . . . , 𝛼𝑞+𝑡), as (𝛼1, . . . , 𝛼𝑘 ) is the least among

all its cyclic shifts, one has

(𝛼1, . . . , 𝛼1+𝑡) (cid:1) (𝛽1, . . . , 𝛽1+𝑡).

This implies that 𝜓(𝑆𝑖) (cid:1) 𝜓(𝑆 𝑗 ), which is a contradiction to the assumption 𝑆𝑖 (cid:3) 𝑆 𝑗 . Moreover, it is

not hard to see that 𝐴𝑖,𝑖 ≠ 0 as 𝑆𝑖 ⊆ 𝑓 (𝑆𝑖) ∪ ( 𝑓 (𝑆𝑖) + 1), therefore the diagonal entries are nonzero.

This proves the claim, hence the lemma.

□

Define the union of digraphs (cid:174)𝐷 (cid:210) (cid:174)𝐸 to be the digraph with vertices 𝑉 ( (cid:174)𝐷) ∪ 𝑉 ( (cid:174)𝐸) and arcs

𝐴( (cid:174)𝐷) ∪ 𝐴( (cid:174)𝐸). The next result follows easily from the definition.

Proposition 5.2.13. If (cid:174)𝐷 and (cid:174)𝐸 are two DAGs on disjoint subsets of P, then

Δcyc

[ (cid:174)𝐷 (cid:210) (cid:174)𝐸]

= Δcyc
[ (cid:174)𝐷]

· Δcyc
[ (cid:174)𝐸]

.

(5.2.8)

82

The proposition above yields a combinatorial proof that Λ is an algebra.

Proposition 5.2.14. Λ is a graded subring of cQSym.

Proof. As a subspace of cQSym, Λ naturally inherits the addition and multiplication operations

from cQSym.

To show that Λ is closed under multiplication, take 𝐾 cyc

𝑛,𝑇 ∈ Λ𝑛, where 𝑈 and
𝑇 are cyclic peak sets in [𝑚] and [𝑛] respectively, namely, there exist 𝜋 ∈ 𝔖𝑚 and 𝜏 ∈ 𝔖𝑛 such

𝑛,𝑈 ∈ Λ𝑚 and 𝐾 cyc

that cPk 𝜋 = 𝑈, cPk 𝜏 = 𝑇. For the purpose of constructing two corresponding disjoint DAGs, we

standardize 𝜏 = 𝜏1𝜏2 . . . 𝜏𝑛 ∈ 𝔖𝑛 to {𝑚 + 1, 𝑚 + 2, . . . , 𝑚 + 𝑛}, that is, construct 𝜏′ = 𝜏′
1

𝜏′
2

. . . 𝜏′
𝑛

where 𝜏′

𝑖 = 𝜏𝑖 + 𝑚 for 𝑖 ∈ [𝑛]. As a consequence of equation (5.2.8), we have

𝑛,𝑈 · 𝐾 cyc
𝐾 cyc

𝑛,𝑇 = Δcyc

[𝜋] · Δcyc

[𝜏′] = Δcyc

[𝜋 (cid:210) 𝜏′] =

This completes the proof.

∑︁

𝜎∈Ltor ([𝜋 (cid:210) 𝜏′])

𝐾 cyc

𝑛,cPk 𝜎

.

(5.2.9)

□

It follows from the Proposition 5.2.14 that the theory of enriched toric [ (cid:174)𝐷]-partitions can be used to

supply an alternative proof for the cyclic shuffle-compatibility of cPk, aside from the Theorem 3.2.3

in combinatorial means and Theorem 4.3.5 using cyclic shuffle algebras.

In terms of another basis of cQSym, the fundamental cyclic quasisymmetric functions, 𝐾 cyc
𝑛,𝑆

has the following expansion.

Proposition 5.2.15. For any cyclic peak set 𝑆 in [𝑛], we have

2−|𝑆|𝐾 cyc

𝑛,𝑆 =

∑︁

𝐹cyc
𝑛,𝐸 ,

𝐸 ⊆[𝑛]:
𝑆⊆𝐸△(𝐸+1)

where △ denotes symmetric difference.

Proof. Since 𝐹cyc

𝑛,𝐸 = (cid:205)𝐹⊇𝐸 𝑀 cyc

𝑛,𝐹, the coefficient of 𝑀 cyc

𝑛,𝐹 on the right-hand side of the above

expansion is |{𝐸 ⊆ 𝐹 : 𝑆 ⊆ 𝐸△(𝐸 + 1)}|.

To count this set, we need the following observations. For each 𝑘 ∈ 𝑆 ⊆ 𝐸△(𝐸 + 1), exactly

one of 𝑘 − 1 and 𝑘 is in 𝐸. It follows from 𝐸 ⊆ 𝐹 that at least one of 𝑘 − 1 and 𝑘 is in 𝐹. So one

has the following two cases:

83

(1) If both 𝑘, 𝑘 − 1 ∈ 𝐹, then 𝐸 must contain exactly one of 𝑘 or 𝑘 − 1.

(2) If only one of 𝑘, 𝑘 − 1 ∈ 𝐹, then 𝐸 must contain this element.

Note that the restrictions above only involve two adjacent numbers.

Also notice that if 𝑘 ∈ 𝐹 but neither 𝑘 nor 𝑘 + 1 is in 𝑆, then 𝑘 is free to be in 𝐸 or not. Denote

𝑆1 = {𝑘 ∈ 𝑆 | both 𝑘, 𝑘 − 1 are in 𝐹},

𝑆2 = {𝑘 ∈ 𝑆 | 𝑘 ∈ 𝐸, 𝑘 − 1 ∉ 𝐹},

𝑆3 = {𝑘 ∈ 𝑆 | 𝑘 ∉ 𝐸, 𝑘 − 1 ∈ 𝐹}.

Then we have a set partition 𝑆 = 𝑆1 ∪ 𝑆2 ∪ 𝑆3. Therefore if we denote 𝑠𝑖 = #𝑆𝑖 for 𝑖 ∈ {1, 2, 3}, we

have |𝑆| = 𝑠1 + 𝑠2 + 𝑠3.

Denote now

𝑇 = {𝑘 ∈ 𝐹 | none of 𝑘, 𝑘 + 1 is in 𝑆}.

By the definition of a peak set, numbers in 𝑆 are not adjacent. Hence we have the following partition

of 𝐹 into disjoint sets:

𝐹 = 𝑆1 ∪ (𝑆1 − 1) ∪ 𝑆2 ∪ (𝑆3 − 1) ∪ 𝑇 .

It follows that |𝐹 | = 2𝑠1 + 𝑠2 + 𝑠3 + 𝑡 with 𝑡 = |𝑇 |. Hence, the number of choices for 𝐸 is

So we have

2𝑠1+𝑡 = 2𝑠1+|𝐹 |−2𝑠1−𝑠2−𝑠3 = 2|𝐹 |−(𝑠1+𝑠2+𝑠3) = 2|𝐹 |−|𝑆|.

∑︁

𝐹𝑐𝑦𝑐
𝑛,𝐸 =

∑︁

2|𝐹 |−|𝑆| 𝑀 𝑐𝑦𝑐
𝑛,𝐹 .

𝐸 ⊆[𝑛]:
𝑆⊆𝐸△(𝐸+1)

𝐹⊆[𝑛]:
𝑆⊆𝐹∪(𝐹+1)

By equation (5.2.4), this quantity is 2−|𝑆|𝐾 𝑐𝑦𝑐
𝑛,𝑆 .

□

5.2.5 Order Polynomials

Definition 5.2.16 (Order polynomial). Define the order polynomial of enriched toric [ (cid:174)𝐷]-partitions,

Ωcyc([ (cid:174)𝐷], 𝑚), by

Ωcyc( [ (cid:174)𝐷], 𝑚) = Δcyc
[ (cid:174)𝐷]

(1𝑚).

84

The following result is the toric analogue of formula (5.1.4).

Proposition 5.2.17. Given 𝜋 ∈ 𝔖𝑛, then

Ωcyc([𝜋], 𝑚)𝑡𝑚 =

∑︁

𝑚

(cid:18)

4𝑡
(1 + 𝑡)2

(cid:19) cpk 𝜋 (cid:18) 1 + 𝑡
1 − 𝑡

(cid:19) 𝑛−1 (cid:18)

cpk 𝜋 +

2𝑛𝑡
(1 − 𝑡)2

(cid:19)

.

(5.2.10)

This right side of the equation does not depend on the choice of representative 𝜋, as they all have

the same cyclic peak number.

Proof. By the definition of order polynomial,

Ωcyc([𝜋], 𝑚)𝑡𝑚 =

∑︁

𝑚

=

=

=

=

[𝜋] (1𝑚)𝑡𝑚
Δcyc

∑︁

Δ𝜏 (1𝑚)𝑡𝑚

∑︁

𝑚
∑︁

𝑚

𝜏∈[𝜋]
∑︁

∑︁

𝜏∈[𝜋]
∑︁

𝑚

∑︁

𝜏∈[𝜋]

𝑚

Δ𝜏 (1𝑚)𝑡𝑚

Ω(𝜏, 𝑚)𝑡𝑚

(cid:18) 1 + 𝑡
1 − 𝑡

1
2

∑︁

𝜏∈[𝜋]

(cid:19) 𝑛+1 (cid:18)

(cid:19) 1+pk 𝜏

,

4𝑡
(1 + 𝑡)2

where the last equality is obtained by applying (5.1.4).

Observe that each representative of [𝜋] 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 𝜋 − 1, cpk 𝜋 − 1

or cpk 𝜋 respectively. The number of those representatives with a cyclic peak at one end is 2 cpk 𝜋.

It follows that

Ωcyc([𝜋], 𝑚)𝑡𝑚 =

∑︁

𝑚

2 cpk 𝜋
2

(cid:18) 1 + 𝑡
1 − 𝑡

(cid:19) 𝑛+1 (cid:18)

(cid:19) cpk 𝜋

4𝑡
(1 + 𝑡)2

+

𝑛 − 2 cpk 𝜋
2

(cid:18) 1 + 𝑡
1 − 𝑡

(cid:19) 𝑛+1 (cid:18)

(cid:19) 1+cpk 𝜋

4𝑡
(1 + 𝑡)2
(cid:19)
2𝑛𝑡
(1 − 𝑡)2

.

□

(cid:18)

4𝑡
(1 + 𝑡)2

(cid:19) cpk 𝜋 (cid:18) 1 + 𝑡
1 − 𝑡

=

(cid:19) 𝑛−1 (cid:18)

cpk 𝜋 +

This completes the proof.

85

We note that by taking the coefficient of 𝑡𝑚 on both sides of equation (5.2.10), one can get an

expression for the order polynomial of enriched toric [ (cid:174)𝐷]-partitions Ωcyc( [𝜋], 𝑚) in an algebraic

manner. It would be desirable to derive Ωcyc( [𝜋], 𝑚) combinatorially.

We now give a totally combinatorial derivation of the order polynomial Ωcyc( [𝜋], 𝑚) by using

the Proposition 5.1.13, which is also proved in a combinatorial way.

Corollary 5.2.18. For a given [𝜋] ∈ [𝔖𝑛], one has

Ωcyc([𝜋], 𝑚) = (𝑛 − 2 cpk 𝜋) · 22 cpk 𝜋+1

𝑚−1−cpk 𝜋
∑︁

(cid:18)(cid:18)𝑛 + 1
𝑘

(cid:19)(cid:19) (cid:18) 𝑛 − 2 cpk 𝜋 − 1
𝑚 − 1 − cpk 𝜋 − 𝑘

(cid:19)

+ cpk 𝜋 · 22 cpk 𝜋

𝑚−cpk 𝜋
∑︁

𝑘=0

𝑘=0
(cid:18)(cid:18)𝑛 + 1
𝑘

(cid:19)(cid:19) (cid:18)𝑛 − 2 cpk 𝜋 + 1
𝑚 − cpk 𝜋 − 𝑘

(cid:19)

.

This right side of the equation does not depend on the choice of representative 𝜋, as they all have

the same cyclic peak number.

Proof. Notice that any representative 𝜋′ of [𝜋] satisfies pk 𝜋′ = cpk[𝜋] − 1 if 𝜋′ starts or ends with

a cyclic peak. Otherwise, pk 𝜋′ = cpk[𝜋]. Among the 𝑛 representatives of [𝜋], there are 2 cpk[𝜋]

of them with a peak element at one end. Therefore, applying equation (5.2.3) we have

Ωcyc([𝜋], 𝑚) = Δcyc

[𝜋] (1𝑚) =

Δ𝜏 (1𝑚) =

∑︁

𝜏∈[𝜋]

∑︁

𝜏∈[𝜋]

Ω(𝜏, 𝑚),

and by the previous observation and the Proposition 5.1.13, one has

Ω(𝜏, 𝑚) =

∑︁

𝜏∈[𝜋]

22 pk 𝜏+1

∑︁

𝜏∈[𝜋]

𝑚−1−pk 𝜏
∑︁

𝑘=0

(cid:18)(cid:18)𝑛 + 1
𝑘

(cid:19)(cid:19) (cid:18) 𝑛 − 2 pk 𝜏 − 1
𝑚 − 1 − pk 𝜏 − 𝑘

(cid:19)

= (𝑛 − 2 cpk[𝜋]) · 22 cpk[𝜋]+1

𝑚−1−cpk[𝜋]
∑︁

(cid:18)(cid:18)𝑛 + 1
𝑘

(cid:19)(cid:19) (cid:18) 𝑛 − 2 cpk[𝜋] − 1
𝑚 − 1 − cpk[𝜋] − 𝑘

(cid:19)

+ 2 cpk[𝜋] · 22(cpk[𝜋]−1)+1

𝑘=0
𝑚−1−(cpk[𝜋]−1)
∑︁

𝑘=0

(cid:18)(cid:18)𝑛 + 1
𝑘

(cid:19)(cid:19) (cid:18) 𝑛 − 2(cpk[𝜋] − 1) − 1
𝑚 − 1 − (cpk[𝜋] − 1) − 𝑘

(cid:19)

= (𝑛 − 2 cpk 𝜋) · 22 cpk 𝜋+1

𝑚−1−cpk 𝜋
∑︁

(cid:18)(cid:18)𝑛 + 1
𝑘

(cid:19)(cid:19) (cid:18) 𝑛 − 2 cpk 𝜋 − 1
𝑚 − 1 − cpk 𝜋 − 𝑘

(cid:19)

+ cpk 𝜋 · 22 cpk 𝜋

𝑚−cpk 𝜋
∑︁

𝑘=0

𝑘=0
(cid:18)(cid:18)𝑛 + 1
𝑘

(cid:19)(cid:19) (cid:18)𝑛 − 2 cpk 𝜋 + 1
𝑚 − cpk 𝜋 − 𝑘

(cid:19)

The conclusion follows immediately.

□

86

We note that the generating function of order polynomials in Proposition 5.2.17 can also be

deduced from the corollary above. More precisely,

Ωcyc([𝜋], 𝑚)𝑡𝑚 = (𝑛 − 2 cpk 𝜋) · 22 cpk 𝜋+1 (1 + 𝑡)𝑛−2 cpk 𝜋−1

(1 − 𝑡)𝑛+1

∑︁

𝑚

𝑡cpk 𝜋+1

𝑡cpk 𝜋

(1 − 𝑡)𝑛+1
(cid:19) 𝑛+1 (cid:18)

+ cpk 𝜋 · 22 cpk 𝜋 (1 + 𝑡)𝑛−2 cpk 𝜋+1
(cid:19) cpk 𝜋 (cid:18) 1 + 𝑡
(cid:18)
1 − 𝑡
(cid:19) cpk 𝜋 (cid:18) 1 + 𝑡
1 − 𝑡

4𝑡
(1 + 𝑡)2
4𝑡
(1 + 𝑡)2

(cid:19) 𝑛−1 (cid:18)

(cid:18)

cpk 𝜋 +

=

=

(𝑛 − 2 cpk 𝜋) ·

2𝑛𝑡
(1 − 𝑡)2

2𝑡
(1 + 𝑡)2
(cid:19)

.

(cid:19)

+ cpk 𝜋

5.3 Shuffle-compatibility Revisited

In this section, we will use the order polynomials for both peaks and cyclic peaks to provide

another characterization of the shuffle algebra Apk and the cyclic shuffle algebra Acyc

cpk. First recall

from [GZ18]:

Theorem 5.3.1 ([GZ18, Theorem 4.8 (b)]). The linear map on Apk defined by

22 pk 𝜋+1𝑡pk 𝜋+1(1 + 𝑡) |𝜋|−2 pk 𝜋−1
(1 − 𝑡) |𝜋|+1



is a Q-algebra isomorphism from Apk to the span of

1
1 − 𝑡

𝜋pk ↦→



,

𝑥 |𝜋|,

if |𝜋| ≥ 1;

if |𝜋| = 0,

(cid:26) 1
1 − 𝑡

(cid:27) (cid:216) (cid:26) 22 𝑗+1𝑡 𝑗+1(1 + 𝑡)𝑛−2 𝑗−1

(1 − 𝑡)𝑛+1

(cid:27)

𝑥𝑛

𝑛≥1, 0≤ 𝑗 ≤⌊ 𝑛−1
2 ⌋

a subalgebra of Q[[𝑡∗]] [𝑥], where multiplication of formal power series in 𝑡 is by Hadamard

product.

□

Now we give another characterization of Apk which follows from our Proposition 5.1.13.

Theorem 5.3.2. The linear map on Apk defined by

𝜋pk ↦→ 22 pk 𝜋+1

𝑚−1−pk 𝜋
∑︁

𝑘=0

(cid:18)(cid:18)|𝜋| + 1
𝑘

(cid:19)(cid:19) (cid:18) |𝜋| − 2 pk 𝜋 − 1
𝑚 − 1 − pk 𝜋 − 𝑘

(cid:19)

𝑥 |𝜋|

87

is a Q-algebra isomorphism from Apk to the span of

(cid:40)

(cid:216)

22 𝑗+1

{1}

𝑚−1− 𝑗
∑︁

𝑘=0

(cid:18)(cid:18)𝑛 + 1
𝑘

(cid:19)(cid:19) (cid:18) 𝑛 − 2 𝑗 − 1
𝑚 − 1 − 𝑗 − 𝑘

(cid:19)

𝑥𝑛

(cid:41)

𝑛≥1, 0≤ 𝑗 ≤⌊ 𝑛−1
2 ⌋

a subalgebra of Q[𝑥]N, the algebra of functions N → Q[𝑥] in the non-negative integer value 𝑚.

Proof. Define a map 𝜅𝑚 : QSym → Q[𝑥] by

𝜅𝑚 (𝐹𝐿) = 𝐾Pk(𝐿) (1𝑚)𝑥𝑛,

linearly extended to all of QSym. The following equation, [Ste97, Equation (3.1)],

𝐾Pk 𝜋 · 𝐾Pk 𝜎 =

∑︁

𝜏∈𝜋(cid:1)𝜎

𝐾Pk 𝜏,

implies that 𝜅𝑚 is a Q-algebra homomorphism. The map that takes 𝐹𝐿 to the function 𝜃 𝐿 : 𝑚 ↦→

𝜅𝑚 (𝐹𝐿) is therefore a homomorphism from QSym to Q[𝑥]N. It follows from Proposition 5.1.13

that

𝜅𝑚 (𝐹𝐿) = 22 pk(𝐿)+1

𝑚−1−pk(𝐿)
∑︁

𝑘=0

(cid:18)(cid:18)𝑛 + 1
𝑘

(cid:19)(cid:19) (cid:18) 𝑛 − 2 pk(𝐿) − 1
𝑚 − 1 − pk(𝐿) − 𝑘

(cid:19)

𝑥𝑛.

Moreover, from Theorem 5.1.10 one has

∞
∑︁

𝑚=0

22 pk(𝐿)+1

𝑚−1−pk(𝐿)
∑︁

𝑘=0

(cid:18) (cid:18)𝑛 + 1
𝑘

(cid:19) (cid:19) (cid:18) 𝑛 − 2 pk(𝐿) − 1
𝑚 − 1 − pk(𝐿) − 𝑘

(cid:19)

𝑡𝑚 =

(cid:18) 1 + 𝑡
1 − 𝑡

1
2

(cid:19) 𝑛+1 (cid:18)

(cid:19) 1+pk(𝐿)

,

4𝑡
(1 + 𝑡)2

which is the generating function of 𝜃 𝐿 and only depends on 𝑛 and pk 𝐿. They are clearly lin-

early independent for 𝐿 with distinct peak numbers. The result then follows immediately from

Theorem 4.2.4.

□

The following theorem append to Theorem 4.3.9 in a different flavor.

Theorem 5.3.3. Let

𝑛, 𝑗 = 𝑗4 𝑗
𝑤cpk

𝑝− 𝑗
∑︁

𝑘=0

(cid:18) (cid:18)𝑛 + 1
𝑘

(cid:19) (cid:19) (cid:18)𝑛 − 2 𝑗 + 1
𝑝 − 𝑗 − 𝑘

(cid:19)

𝑥𝑛

+ 2(𝑛 − 2 𝑗)4 𝑗

𝑝−1− 𝑗
∑︁

𝑘=0

(cid:18)(cid:18)𝑛 + 1
𝑘

(cid:19)(cid:19) (cid:18) 𝑛 − 2 𝑗 − 1
𝑝 − 𝑗 − 𝑘 − 1

(cid:19)

𝑥𝑛.

88

Then the linear map on Acyc

cpk defined by

[𝜋]cpk ↦→

𝑤cpk

|𝜋|,cpk[𝜋]

,

if |𝜋| ≥ 1,

1,

if |𝜋| = 0,





is a Q-algebra isomorphism from Acyc

cpk to the span of

{1} ∪ {𝑤cpk

𝑛, 𝑗 }𝑛≥1,

1≤ 𝑗 ≤⌊𝑛/2⌋

,

a subalgebra of Q[𝑥]N.

Proof. It follows from Theorem 4.3.9 (b) and the identity

∞
∑︁

𝑝=0

𝑤cpk

|𝜋|,cpk[𝜋]

𝑡 𝑝 =

=

(cid:18)

(cid:19) |𝜋|−1 (cid:18)

(cid:19) cpk[𝜋] (cid:18) 1 + 𝑡
1 − 𝑡

4𝑡
(1 + 𝑡)2
(cpk[𝜋] (1 + 𝑡)2 + 2(|𝜋| − 2 cpk[𝜋])𝑡) (4𝑡)cpk[𝜋] (1 + 𝑡) |𝜋|−2 cpk[𝜋]−1
(1 − 𝑡) |𝜋|+1

2 |𝜋| 𝑡
(1 − 𝑡)2

cpk[𝜋] +

𝑥 |𝜋|

(cid:19)

where the first equality follows from Proposition 5.2.17 and Corollary 5.2.18.

𝑥 |𝜋|,

□

For convenience, we always assume the label set to be [𝑛]. However, the definitions of (toric)

DAGs and (toric) posets can be extended to any finite subsets of P as the set of labels, with all

consequent conclusions continuing to hold.

89

BIBLIOGRAPHY

[AGRR21] Ron M. Adin, Ira M. Gessel, Victor Reiner, and Yuval Roichman. Cyclic quasi-

symmetric functions. Israel J. Math., 243(1):437–500, 2021.

[BJS20]

Duff Baker-Jarvis and Bruce E. Sagan. Bijective proofs of shuffle compatibility results.
Adv. in Appl. Math., 113:101973, 29, 2020.

[DLM+21] Rachel Domagalski, Jinting Liang, Quinn Minnich, Bruce E. Sagan, Jamie Schmidt,
and Alexander Sietsema. Cyclic shuffle compatibility. Sém. Lothar. Combin., 85:Art.
B85d, 11, [2020–2021].

[DMR16] Mike Develin, Matthew Macauley, and Victor Reiner. Toric partial orders. Trans. Amer.

Math. Soc., 368(4):2263–2287, 2016.

[Ges84]

[GZ18]

[JZ22]

Ira M. Gessel. Multipartite 𝑃-partitions and inner products of skew Schur functions.
In Combinatorics and algebra (Boulder, Colo., 1983), volume 34 of Contemp. Math.,
pages 289–317. Amer. Math. Soc., Providence, RI, 1984.

Ira M. Gessel and Yan Zhuang. Shuffle-compatible permutation statistics. Adv. Math.,
332:85–141, 2018.

Kathy Q. Ji and Dax T. X. Zhang. A cyclic analogue of Stanley’s shuffling theorem.
Electron. J. Combin., 29(4):Paper No. 4.20, 8 pp., 2022.

[LSZ23]

Jinting Liang, Bruce E. Sagan, and Yan Zhuang. Cyclic shuffle-compatibility and cyclic
quasisymmetric functions. Sém. Lothar. Combin., 89B:Art. 41, 12, 2023.

[Sta72]

[Sta24]

Richard P. Stanley. Ordered structures and partitions. Memoirs of the American
Mathematical Society, No. 119. American Mathematical Society, Providence, R.I.,
1972.

Richard P. Stanley. Enumerative combinatorics. Vol. 2, volume 208 of Cambridge
Studies in Advanced Mathematics. Cambridge University Press, Cambridge, second
edition, [2024] ©2024. With an appendix by Sergey Fomin.

[Ste97]

John R. Stembridge. Enriched 𝑃-partitions. Trans. Amer. Math. Soc., 349(2):763–788,
1997.

90