# Quasisymmetric Schur functions and modules of the 0-Hecke algebra

Vasu V. Tewari* and Stephanie J. van Willigenburg†

University of British Columbia, Vancouver, Canada

**Abstract** We define a 0-Hecke action on composition tableaux, and then use it to derive 0-Hecke modules whose quasisymmetric characteristic is a quasisymmetric Schur function. We then relate the modules to the weak Bruhat order and use them to derive a new basis for quasisymmetric functions. We also classify those modules that are tableau-cyclic and likewise indecomposable. Finally, we develop a restriction rule that reflects the coproduct of quasisymmetric Schur functions.

**Résumé** Nous définissons une action 0-Hecke sur les tableaux de composition, et ensuite nous l'utilisons pour dériver les modules 0-Hecke dont la caractéristique quasi-symétrique est une fonction de Schur quasi-symétrique. Nous mettons les modules en relation avec l'ordre de Bruhat faible et les utilisons pour dériver une nouvelle base pour les fonctions quasi-symétriques. Nous classons aussi ces modules qui sont tableau-cycliques et aussi indécomposable. Enfin, nous développons une règle de restriction qui reflète le coproduit des fonctions de Schur quasi-symétriques.

**Keywords:** 0-Hecke algebra, combinatorial representation theory, composition tableaux, quasisymmetric functions, Schur functions, weak Bruhat order

## 1 Introduction

Quasisymmetric functions were first defined by Gessel [Ges84] in the 1980s as weight enumerators for labelled posets. Since then, the Hopf algebra of quasisymmetric functions, QSym, has arisen in a variety of contexts including the study of Lie representations, riffle shuffles, random walks, and the representation theory of Hecke algebras. Furthermore, QSym contains the Hopf algebra of symmetric functions, Sym, as a subalgebra, which is a central object of study in algebraic combinatorics due in no small part to its basis of Schur functions that arise, for example, in the representation theory of the symmetric group, as generating functions for Young tableaux, and in Schubert calculus.

Recently a new basis for QSym was discovered, which arises through the combinatorics of Macdonald polynomials and reflects many properties of Schur functions. These functions were called quasisymmetric Schur functions and properties reflected include that they yield quasisymmetric Kostka numbers; exhibit quasisymmetric Pieri rules and a quasisymmetric Littlewood-Richarsdon rule. They were also key

<footnote>*Email: vasu@math.ubc.ca.</footnote>

<footnote>†Email: steph@math.ubc.ca. Both authors were supported in part by the National Sciences and Engineering Research Council of Canada.</footnote>
to resolving the conjecture that QSym over Sym has a stable basis, and have motivated the search for
other Schur-like bases of QSym such as row-strict quasisymmetric functions. These details and more on
quasisymmetric Schur functions, including full citations for all of the above, can be found in [LMvW13].

In this extended abstract we fill an important gap in the literature on quasisymmetric Schur functions by
providing a representation theoretic interpretation for them, that is, we show how quasisymmetric Schur
functions arise naturally in the representation theory of the 0-Hecke algebra. More precisely, we

* define a 0-Hecke action and use it to construct 0-Hecke modules whose quasisymmetric characteristic is a quasisymmetric Schur function (Theorem 6.2),

• classify those 0-Hecke modules that are tableau-cyclic (Proposition 9.2),

* determine that our 0-Hecke modules are indecomposable if and only if they are tableau-cyclic (Theorem 9.3),

* show that orbits generated by certain tableaux under our 0-Hecke action are isomorphic to subintervals of the weak Bruhat order on the symmetric group (Theorem 7.8),

* discover a natural set of 0-Hecke modules that give rise to a new basis for QSym, called the canonical basis (Proposition 8.2),

• establish restriction rules that reflect the coproduct of quasisymmetric Schur functions (Theorem 10.1).

Further avenues could include determining which subintervals of the Bruhat order arise, or determining
properties of the canonical basis.

Due to space constraints we will not include any proofs, although we will often very briefly indicate
the proof techniques involved, for the interested reader.

2 Background

2.1 *Composition diagrams and composition tableaux*

We define a *composition* $\alpha = (\alpha_1, \dots, \alpha_k)$ of $n$, denoted by $\alpha \vdash n$, to be an ordered list of positive integers whose sum is $n$. For convenience we define the empty composition $\emptyset$ to be the unique composition of 0. We call the $\alpha_i$ for $1 \le i \le k$ the *parts of* $\alpha$, call $k = l(\alpha)$ the *length of* $\alpha$ and call $n = |\alpha|$ the *size of* $\alpha$.

There exists a natural bijection between compositions of $n$ and subsets of $[n-1]$ that can be described
as follows. Given $S = \{i_1 < \cdots < i_k\} \subseteq [n-1]$, we associate to it the composition $\alpha = (i_1, i_2 - i_1, \ldots, n-i_k)$.
We will refer to $\alpha$ as $\text{comp}(S)$. Conversely, given a composition $\alpha = (\alpha_1, \ldots, \alpha_k) \vdash n$,
we associate to it the subset of $[n-1]$ given by $\{\alpha_1, \alpha_1+\alpha_2, \ldots, \alpha_1+\cdots+\alpha_{k-1}\}$. We will denote this
subset by $\text{set}(\alpha)$.

Given a composition $\alpha = (\alpha_1, \dots, \alpha_k)$, we define its *reverse composition diagram*, also denoted by $\alpha$, to be the array of left-justified cells with $\alpha_i$ cells in row $i$ from the top. A cell is said to be in row $i$ if it is in the $i$-th row from the top, and in column $j$ if it is in the $j$-th column from the left, shortened to position $(i, j)$.
**Example 2.1** The composition $\alpha = (3, 4, 2, 3)$ has set($\alpha$) = $\{3, 7, 9\} \subset [11]$. The reverse composition diagram of $\alpha$ is below.

<figure><img src="image_1.png" /></figure>

**Definition 2.2** The reverse composition poset ($\mathcal{L}_c$, $<_c$) is the poset consisting of all compositions in which $\alpha = (\alpha_1, \dots, \alpha_l)$ is covered by

1. $(1, \alpha_1, \dots, \alpha_l)$, that is, the composition obtained by prefixing a part of size 1 to $\alpha$.

2. $(\alpha_1, \dots, \alpha_k + 1, \dots, \alpha_l)$, provided that $\alpha_i \neq \alpha_k$ for all $i < k$, that is, the composition obtained by adding 1 to a part of $\alpha$ as long as that part is the leftmost part of that size.

Let $\alpha, \beta$ be two reverse composition diagrams such that $\beta <_c \alpha$. Then we define the skew reverse composition shape $\alpha \parallel \beta$ to be the array of cells of $\alpha$

$$ \alpha \parallel \beta = \{(i, j) \in \alpha \mid (i, j) \text{ not in subdiagram } \beta\} $$

when $\beta$ is placed in the bottom left corner of $\alpha$. We refer to $\beta$ as the *inner shape* and to $\alpha$ as the *outer shape*. The size of $\alpha \parallel \beta$ is $|\alpha \parallel \beta| = |\alpha| - |\beta|$. Also $\alpha \parallel \emptyset$ is simply the reverse composition diagram $\alpha$. Hence, we write $\alpha$ instead of $\alpha \parallel \emptyset$ and say it is of *straight shape*.

**Example 2.3** The inner shape is denoted by cells filled with a •.

<figure><img src="image_2.png" /></figure>

$$ \alpha \parallel \beta = (3, 2, 1, 4, 4) \parallel (1, 3, 2) $$

We will now use the reverse composition poset to define standard reverse composition tableaux.

**Definition 2.4** Let $\alpha^0, \alpha^n$ be compositions such that $\alpha^0 <_c \alpha^n$ in $\mathcal{L}_c$, and $\alpha^n$ contains $n$ more cells than $\alpha^0$. Consider a saturated chain of $n + 1$ elements in $\mathcal{L}_c$

$$ \alpha^0 \leq_c \alpha^1 \leq_c \alpha^2 \leq_c \dots \leq_c \alpha^n. $$

Let $\tau$ be the filling of the cells of the skew reverse composition shape $\alpha^n \parallel \alpha^0$ such that the number $n-i+1$ appears in the cell in $\tau$ that exists in $\alpha^i$ but not $\alpha^{i-1}$. Then we say $\tau$ is a standard reverse composition tableau (SRCT) of shape $\alpha^n \parallel \alpha^0$, and denote the set of all SRCTs of shape $\alpha^n \parallel \alpha^0$ by $\text{SRCT}(\alpha^n \parallel \alpha^0)$.
The descent set of an SRCT $\tau$ of size $n$, denoted by $\text{Des}(\tau)$, is

$$ \text{Des}(\tau) = \{i \mid i+1 \text{ appears weakly right of } i\} \subseteq [n-1] $$

and the corresponding descent composition of $\tau$ is $\text{comp}(\tau) = \text{comp}(\text{Des}(\tau))$. Given a composition $\alpha = (\alpha_1, \dots, \alpha_k)$, the canonical tableau of shape $\alpha$, denoted by $\tau_\alpha$, is the unique SRCT of shape $\alpha$ and $\text{comp}(\tau_\alpha) = (\alpha_1, \dots, \alpha_k)$. In $\tau_\alpha$ the first row is filled with $\alpha_1, \dots, 2, 1$ and row $i$ for $2 \le i \le l(\alpha)$ is filled with

$$ x + \alpha_i, \dots, x + 2, x + 1 $$

where $x = \alpha_1 + \dots + \alpha_{i-1}$.

**Example 2.5** The saturated chain in $\mathcal{L}_c$

$$ \emptyset \leq_c (1) \leq_c (1, 1) \leq_c (2, 1) \leq_c (3, 1) \leq_c (3, 2) \\ \leq_c (1, 3, 2) \leq_c (1, 1, 3, 2) \leq_c (1, 1, 4, 2) \leq_c (2, 1, 4, 2) $$

yields the following SRCT $\tau$ with $\text{Des}(\tau) = \{1, 3, 4, 5, 8\}$. Also shown is $\tau_{(2,1,4,2)}$.

$$ \tau = \begin{array}{c|c} 3 & 1 \\ \hline 4 & \\ 8 & 7 \ 6 \ 2 \\ \hline 9 & 5 \end{array} $$

$$ \tau_{(2,1,4,2)} = \begin{array}{c|c} 2 & 1 \\ \hline 3 & \\ 7 & 6 \ 5 \ 4 \\ \hline 9 & 8 \end{array} $$

## 2.2 Quasisymmetric functions and quasisymmetric Schur functions

We now define two families of functions that are indexed by compositions.

**Definition 2.6** Let $\alpha \vdash n$ be a composition. Then the fundamental quasisymmetric function $F_\alpha$ is defined by $F_\emptyset = 1$ and

$$ F_{\alpha} = \sum x_{i_1} \cdots x_{i_n} $$

where the sum is over all $n$-tuples $(i_1, \dots, i_n)$ of positive integers satisfying

$$ 1 \le i_1 \le \cdots \le i_n \quad \text{and} \quad i_j < i_{j+1} \quad \text{if } j \in \text{set}(\alpha). $$

**Example 2.7** We have $F_{(1,2)} = x_1^2 x_2 + x_1^2 x_3 + x_1^2 x_4 + x_2^2 x_3 + \dots + x_1 x_2 x_3 + x_1 x_2 x_4 + \dots$.

With this in mind, the Hopf algebra of quasisymmetric functions is defined to be the graded sub-Hopf algebra of $\mathbb{C}[[x_1, x_2, \dots]]$

$$ \mathrm{QSym} = \bigoplus_{n \ge 0} \mathrm{QSym}^n $$

where

$$ \mathrm{QSym}^n = \operatorname{span}\{F_\alpha \mid \alpha \vdash n\} = \operatorname{span}\{S_\alpha \mid \alpha \vdash n\} $$

and the latter basis, which will be central to what remains, is defined as follows.
**Definition 2.8** Given a skew reverse composition shape $\alpha \parallel \beta$, we define the skew quasisymmetric Schur function $S_{\alpha \parallel \beta}$ to be

$$S_{\alpha \parallel \beta} = \sum_{\tau \in \text{SRCT}(\alpha \parallel \beta)} F_{\text{comp}(\tau)}$$

and when $\beta = \emptyset$ we call $S_{\alpha}$ a quasisymmetric Schur function.

**Example 2.9** $S_{(1,2)} = F_{(1,2)}$ from the SRCT $\begin{bmatrix} 1 \\ 3 & 2 \end{bmatrix}$.

# 3 The 0-Hecke algebra

Consider the symmetric group $\mathfrak{S}_n$ for any positive integer $n$. It is generated by the adjacent transpositions $s_i = (i, i+1)$ for $1 \le i \le n-1$ that satisfy the following relations.

$$ \begin{aligned} s_i^2 &= 1 \quad \text{for } 1 \le i \le n-1 \\ s_i s_{i+1} s_i &= s_{i+1} s_i s_{i+1} \quad \text{for } 1 \le i \le n-2 \\ s_i s_j &= s_j s_i \quad \text{if } |i-j| \ge 2 \end{aligned} $$

In the first relation above, the 1 stands for the identity permutation.

Given a permutation $\sigma \in \mathfrak{S}_n$, we can write it as a product of adjacent transpositions. An expression which uses the minimal number of adjacent transpositions is called a reduced word for $\sigma$. It turns out the number of adjacent transpositions occurring in any reduced word for $\sigma$ is the same. This allows us to define a length function, $l$, on $\mathfrak{S}_n$ by letting $l(\sigma) = \text{number of adjacent transpositions in any reduced word for } \sigma$. The 0-Hecke algebra $H_n(0)$ is the $\mathbb{C}$-algebra generated by the elements $T_1, \dots, T_{n-1}$ subject to the following relations similar to those of $\mathfrak{S}_n$.

$$ \begin{aligned} T_i^2 &= T_i \quad \text{for } 1 \le i \le n-1 \\ T_i T_{i+1} T_i &= T_{i+1} T_i T_{i+1} \quad \text{for } 1 \le i \le n-2 \\ T_i T_j &= T_j T_i \quad \text{if } |i-j| \ge 2 \end{aligned} $$

Suppose a permutation $\sigma \in \mathfrak{S}_n$ has a reduced word of the form $s_{i_1} \cdots s_{i_p}$. Then we define an element $T_{\sigma} \in H_n(0)$ as follows.

$$T_{\sigma} = T_{i_1} \cdots T_{i_p}$$

The defining relations of $H_n(0)$ imply that $T_{\sigma}$ is independent of the choice of reduced word. Moreover, it turns out that the set $\{T_{\sigma} | \sigma \in \mathfrak{S}_n\}$ is a linear basis for $H_n(0)$. Thus, the dimension of $H_n(0)$ is $n!$.

## 3.1 Representations of $H_n(0)$

Let $\mathcal{R}(H_n(0))$ denote the $\mathbb{Z}$-span of the isomorphism classes of finite dimensional representations of $H_n(0)$. The isomorphism class corresponding to an $H_n(0)$-module $M$ will be denoted by $[M]$. The Grothendieck group $\mathcal{G}_0(H_n(0))$ is the quotient of $\mathcal{R}(H_n(0))$ modulo the relations $[M] = [M'] + [M'']$
whenever there exists a short exact sequence $0 \to M' \to M \to M'' \to 0$. The irreducible representations of $H_n(0)$ form a basis for $\mathcal{G}_0(H_n(0))$. Let

$$ \mathcal{G} = \bigoplus_{n \ge 0} \mathcal{G}_0(H_n(0)). $$

According to [Nor79], there are $2^{n-1}$ distinct irreducible representations of $H_n(0)$. They are naturally indexed by compositions of $n$. Let $\mathbf{F}_\alpha$ denote the 1-dimensional $\mathbb{C}$-vector space corresponding to the composition $\alpha \models n$, spanned by a vector $v_\alpha$. Let $J \subseteq [n-1]$ be set($\alpha$). Next, we define an action of the generators $T_i$ of $H_n(0)$ as follows.

$$ T_i(v_\alpha) = \begin{cases} 0 & i \in J \\ v_\alpha & i \notin J \end{cases} $$

Then $\mathbf{F}_\alpha$ is an irreducible 1-dimensional $H_n(0)$-representation.

In [DKLT96] they define a linear map

$$ \mathrm{ch}: \begin{array}{ccc} \mathcal{G} & \to & \mathrm{QSym} \\ [\mathbf{F}_\alpha] & \mapsto & \mathcal{F}_\alpha. \end{array} $$

Given an $H_n(0)$-module $M$, $\mathrm{ch}([M])$ is said to be the *quasisymmetric characteristic* of $M$. It is clear from the definition of the Grothendieck group that every time we have a short exact sequence of $H_n(0)$-modules, say $0 \to M' \to M \to M'' \to 0$, then

$$ \mathrm{ch}([M]) = \mathrm{ch}([M']) + \mathrm{ch}([M']), $$

which will be useful later.

# 4 A 0-Hecke action on SRCTs

In order to define an action on SRCTs we first need the concept of attacking.

**Definition 4.1** Given $\tau \in \mathrm{SRCT}(\alpha)$ for some composition $\alpha \models n$, and a positive integer $i$ such that $1 \le i \le n-1$, we say that $i$ and $i+1$ are attacking if either

1. $i$ and $i+1$ are in the same column in $\tau$, or

2. $i$ and $i+1$ are in adjacent columns in $\tau$, with $i+1$ positioned strictly southeast of $i$.

Let $\tau \in \mathrm{SRCT}(\alpha)$ where $\alpha \models n$. Given a positive integer $i$ satisfying $1 \le i \le n-1$, let $s_i(\tau)$ denote the filling obtained by interchanging the positions of entries $i$ and $i+1$ in $\tau$.

Given $\tau \in \mathrm{SRCT}(\alpha)$, define operators $\pi_i$ for $1 \le i \le n-1$ as follows.

$$ \pi_i(\tau) = \begin{cases} \tau & i \notin \mathrm{Des}(\tau) \\ 0 & i \in \mathrm{Des}(\tau), i \text{ and } i+1 \text{ attacking} \\ s_i(\tau) & i \in \mathrm{Des}(\tau), i \text{ and } i+1 \text{ non-attacking} \end{cases} $$

Using combinatorics on words we can establish the following important fact.
**Lemma 4.2** If $\alpha \vdash n$, $\tau \in \text{SRCT}(\alpha)$ and $i \in \text{Des}(\tau)$ such that $i$ and $i+1$ are non-attacking, then $s_i(\tau) \in \text{SRCT}(\alpha)$.

**Example 4.3** Let $\tau$ be the SRCT of shape $(3, 4, 2, 3)$ shown below.

<table><tr><td>5</td><td>4</td><td>2</td></tr><tr><td>9</td><td>7</td><td>6</td><td>3</td></tr><tr><td>10</td><td>1</td><td></td></tr><tr><td>12</td><td>11</td><td>8</td></tr></table>

Then $\text{Des}(\tau) = \{1, 2, 5, 7, 9, 10\}$. Thus, for all $1 \le i \le 11$ such that $i \notin \text{Des}(\tau)$, we have that $\pi_i(\tau) = \tau$. Notice further that 2, 7, 9 and 10 are attacking descents. Hence if $i = 2, 7, 9$ or $10$, we have that $\pi_i(\tau) = 0$. Finally, we have that $\pi_1(\tau)$ and $\pi_5(\tau)$ are as below.

$$ \pi_1(\tau) = \begin{array}{c|ccc} 5 & 4 & 1 \\ \hline 9 & 7 & 6 \\ \hline 10 & 2 & \\ \hline 12 & 11 & 8 \end{array} $$

$$ \pi_5(\tau) = \begin{array}{c|ccc} 6 & 4 & 2 \\ \hline 9 & 7 & 5 \\ \hline 10 & 1 & \\ \hline 12 & 11 & 8 \end{array} $$

Additionally, the relations satisfied by the 0-Hecke algebra are also satisfied by these operators $\pi_i$. The proof involves an intricate case analysis of the action of $\pi_i$ on an SRCT $\tau$ depending on whether or not $i \in \text{Des}(\tau)$.

**Proposition 4.4** 1. For $1 \le i \le n-1$, we have $\pi_i^2 = \pi_i$.

2. For $1 \le i \le n-2$, we have $\pi_i\pi_{i+1}\pi_i = \pi_{i+1}\pi_i\pi_{i+1}$.

3. For $1 \le i, j \le n-1$ such that $|i-j| \ge 2$, we have $\pi_i\pi_j = \pi_j\pi_i$.

# 5 The partial order ≲_α

Since the operators $\{\pi_i\}_{i=1}^{n-1}$, which we will now term *flips* for convenience, satisfy the same relations as the 0-Hecke algebra, we can associate a well-defined linear operator $\pi_\sigma$ with any permutation $\sigma \in \mathfrak{S}_n$, as in Section 3. We will use these operators to define a new partial order on SRCTs of the same shape. But before that, we need some definitions and results.

**Definition 5.1** Let $\tau$ be an SRCT of shape $\alpha$ whose largest part is $\alpha_{max}$, and let the entries in column $i$ for $1 \le i \le \alpha_{max}$ read from top to bottom be some word $w^i$. We define the column word of $\tau$, denoted by $\text{col}_{\tau}$ to be the word

$$ w^1 w^2 \cdots w^{\alpha_{max}}. $$

We will think of the column word as a permutation written in single line notation.

Let $\alpha \vdash n$ and $\tau_1 \in \text{SRCT}(\alpha)$ be such that $i \in \text{Des}(\tau_1)$. Suppose further that $i$ is a non-attacking descent in $\tau_1$. Let $\pi_i(\tau_1) = \tau_2$. Then $s_i\text{col}_{\tau_1} = \text{col}_{\tau_2}$ where $s_i = (i, i+1)$ is the transposition in $\mathfrak{S}_n$ interchanging $i$ and $i+1$.
**Lemma 5.2** Let $\tau_2$ be obtained by a sequence of flips starting from $\tau_1$. Let $s_{i_1} \cdots s_{i_p}$ be a reduced word for $\mathrm{col}_{\tau_2}(\mathrm{col}_{\tau_1})^{-1}$. Then $\pi_{i_1} \cdots \pi_{i_p}(\tau_1) = \tau_2$.

We can also say something about column words as permutations.

**Lemma 5.3** Let $\alpha \vdash n$ and $\tau_1 \in \mathrm{SRCT}(\alpha)$ be such that $i \in \mathrm{Des}(\tau_1)$. Suppose further that $i$ is a non-attacking descent in $\tau_1$. If $\pi_i(\tau_1) = \tau_2$, then $l(\mathrm{col}_{\tau_1}) + 1 = l(\mathrm{col}_{\tau_2})$.

From the above lemmas it follows that if we can reach an SRCT $\tau_2$ starting from $\tau_1$ via a sequence of flips, where $\tau_2 \neq \tau_1$, then there does not exist a sequence of flips that takes $\tau_2$ to $\tau_1$. Now we are in position to define a new partial order on SRCTs of the same shape.

**Definition 5.4** Let $\tau_1$ and $\tau_2$ be elements of $\mathrm{SRCT}(\alpha)$ where $\alpha \vdash n$. Define a partial order $\preceq_{\alpha}$ on $\mathrm{SRCT}(\alpha)$ by $\tau_1 \preceq_{\alpha} \tau_2$ if and only if there exists a permutation $\sigma \in \mathfrak{S}_n$ such that $\pi_{\sigma}(\tau_1) = \tau_2$.

The reflexivity and transitivity of $\preceq_{\alpha}$ are immediate from the definition. The anti-symmetricity follows from the remark preceding the above definition. Thus, $\preceq_{\alpha}$ is indeed a partial order.

# 6 0-Hecke modules from SRCTs

In this section, we will define an $H_n(0)$-module indexed by a composition $\alpha \vdash n$ whose quasisymmetric characteristic is the quasisymmetric Schur function $S_{\alpha}$. First, extend the partial order $\preceq_{\alpha}$ on $\mathrm{SRCT}(\alpha)$ to an arbitrary total order on $\mathrm{SRCT}(\alpha)$. We will call this total order $\preceq_{\alpha}^t$. Let the elements of $\mathrm{SRCT}(\alpha)$ under this total order be $\{\tau_1 \preceq_{\alpha}^t \cdots \preceq_{\alpha}^t \tau_m\}$.

Let $\mathcal{V}_{\tau_i}$ be the $\mathbb{C}$-linear span of SRCTs that are greater than or equal to an SRCT $\tau_i$ under the total order $\preceq_{\alpha}^t$. Notice that the definition of $\preceq_{\alpha}$ implies that $\pi_{\sigma}\mathcal{V}_{\tau_i} \subseteq \mathcal{V}_{\tau_i}$ for any $\sigma \in \mathfrak{S}_n$. This observation combined with the fact that the operators $\{\pi_i\}_{i=1}^{n-1}$ satisfy the same relations as the 0-Hecke algebra, by Proposition 4.4, gives the following result.

**Lemma 6.1** $\mathcal{V}_{\tau_i}$ is an $H_n(0)$-module.

Define $\mathcal{V}_{\tau_{m+1}}$ to be the trivial 0 module. Consider the following filtration of $H_n(0)$-modules.

$$ \mathcal{V}_{\tau_{m+1}} \subset \mathcal{V}_{\tau_m} \subset \cdots \subset \mathcal{V}_{\tau_2} \subset \mathcal{V}_{\tau_1} \quad (1) $$

Then, the quotient modules $\mathcal{V}_{\tau_{i-1}}/\mathcal{V}_{\tau_i}$ for $2 \le i \le m+1$ are 1-dimensional $H_n(0)$-modules spanned by $\tau_{i-1}$. Furthermore, they are irreducible modules. We can identify which $H_n(0)$-module they are by looking at the action of $\pi_j$ on $\mathcal{V}_{\tau_{i-1}}/\mathcal{V}_{\tau_i}$ for $1 \le j \le n-1$. We have

$$ \pi_j(\tau_{i-1}) = \begin{cases} 0 & j \in \mathrm{Des}(\tau_{i-1}) \\ \tau_{i-1} & \text{otherwise.} \end{cases} \quad (2) $$

Thus, as an $H_n(0)$-representation, $\mathcal{V}_{\tau_{i-1}}/\mathcal{V}_{\tau_i}$ is isomorphic to the irreducible representation $\mathbf{F}_{\beta}$ where $\beta$ is the composition corresponding to the descent set $\mathrm{Des}(\tau_{i-1})$. Thus, by Subsection 3.1

$$ \mathrm{ch}([\mathcal{V}_{\tau_i}/\mathcal{V}_{\tau_{i-1}}]) = F_{\beta}. \quad (3) $$
From this it follows that

$$
\begin{align*}
ch([V_{\tau_1}]) &= \sum_{i=2}^{m+1} ch([V_{\tau_{i-1}}/V_{\tau_i}]) \\
&= \sum_{i=2}^{m+1} F_{\text{comp}}(\tau_{i-1}) \\
&= S_{\alpha}. \tag{4}
\end{align*}
$$

Thus, we have established the following.

**Theorem 6.2** $V_{\tau_1}$ is an $H_n(0)$-module whose quasisymmetric characteristic is the quasisymmetric Schur function $S_{\alpha}$, where $\alpha$ is the shape of the SRCT $\tau_1$.

Henceforth, this $H_n(0)$-module will be denoted by $S_\alpha$, that is $S_\alpha := V_{\tau_1}$ and

$ch([S_{\alpha}]) = S_{\alpha}.$

7 Source and sink tableaux, and the weak Bruhat order

In this section we will introduce an equivalence relation, related to standardization, with many applica-
tions. As usual, we fix α to be a composition of n.

**Definition 7.1** Given a word $w = w_1 \cdots w_n$ such that $w_1, \dots, w_n$ are distinct positive integers, we say that the standardization of $w$ is the permutation $\sigma \in \mathfrak{S}_n$ such that $\sigma(i) < \sigma(j)$ if and only if $w_i < w_j$ for $1 \le i, j \le n$.

**Definition 7.2** Let $\tau$ be an SRCT of shape $\alpha$ whose largest part is $\alpha_{max}$, and let the entries in column $i$ for $1 \le i \le \alpha_{max}$ read from top to bottom be some word $w^i$. Then we say the standardized $i$-th column word of $\tau$, denoted by $\text{st}_i(\tau)$ is the standardization of $w^i$.

Furthermore, we define the standardized column word of $\tau$, denoted by $\text{st}(\tau)$ to be the word

$$
\mathrm{st}(\tau) = \mathrm{st}_1(\tau) \mathrm{st}_2(\tau) \cdots \mathrm{st}_{\alpha_{\mathrm{max}}}(\tau).
$$

With the definition of standardized column word in hand, we will define a natural equivalence relation on SRCT(α) given a composition α ⊢ n. Define τ₁ ~ α τ₂ if and only if st(τ₁) = st(τ₂). Suppose the equivalence classes with respect to the aforementioned equivalence relation are E₁, E₂, ..., Eₖ. Let Sα,Eᵢ denote the C-linear span of all SRCTs in Eᵢ for i = 1, ..., k. Then we get the following isomorphism of vector spaces

$$
\mathbf{S}_{\alpha} \cong \bigoplus_{i=1}^{k} \mathbf{S}_{\alpha, E_i}
$$

since the equivalence classes are disjoint and their union is SRCT(α). This isomorphism is actually an
isomorphism of $H_n(0)$-modules, as the following lemma implies immediately. The lemma itself follows
from the fact that flips do not change the standardized column word.

**Lemma 7.3** For all *i* such that 1 ≤ *i* ≤ *n* − 1, we have that *π*<sub>*i*</sub>(*S*<sub>*α*,*E*<sub>*j*</sub>) ⊆ *S*<sub>*α*,*E*<sub>*j*</sub> for any 1 ≤ *j* ≤ *k*.
Next, we discuss two important classes of SRCTs that will form special representatives of each equiv-
ality class.

**Definition 7.4** Let $\alpha \models n$. An SRCT $\tau$ of shape $\alpha$ is said to be a source tableau if it satisfies the condition that for every $i \notin \text{Des}(\tau)$ and satisfying $i \neq n$, we have that $i+1$ lies to the immediate left of $i$. Meanwhile $\tau$ is said to be a sink tableau if it satisfies the condition that for every $i \in \text{Des}(\tau)$, we have that $i$ and $i+1$ are attacking.

**Example 7.5** Let $\alpha = (4, 3, 2, 3)$. We list an example each of a source tableau (left) and sink tableau (right) of shape $\alpha$.

<figure><img src="image_3.png" /></figure>

The motivation for these names is immediate from the following lemma that is straightforward to derive
from the definitions.

**Lemma 7.6** Let $\alpha \models n$. Then $\tau_1 \in \text{SRCT}(\alpha)$ is a source tableau if and only if there does not exist an SRCT $\tau_2 \neq \tau_1$ such that $\pi_i(\tau_2) = \tau_1$ for some positive integer $i$. However, $\tau_1 \in \text{SRCT}(\alpha)$ is a sink tableau if and only if there does not exist an SRCT $\tau_2 \neq \tau_1$ such that $\pi_i(\tau_1) = \tau_2$ for some positive integer $i$.

Using an extensive analysis on SRCTs and the position of the entry 1, we can show that in every
equivalence class $E$, there exists a unique source tableau, $\tau_{0,E}$, and a unique sink tableau, $\tau_{1,E}$. Thus,
the number of source tableaux, number of sink tableaux, and number of equivalence classes under the
equivalence relation $\sim_\alpha$ are all equal.

We can then use these as ingredients to prove the following proposition.

**Proposition 7.7** Let $\tau_{0,E}$ be the unique source tableau in an equivalence class $E$. Then $S_{\alpha,E}$ is a cyclic $H_n(0)$-module with generator $\tau_{0,E}$. In particular, any tableau in $E$ can be obtained by applying a sequence of flips to $\tau_{0,E}$.

Since flips do not change the standardized column word, we know that two SRCTs $\tau_1$ and $\tau_2$ satisfying $\text{st}(\tau_1) \neq \text{st}(\tau_2)$ are incomparable under the partial order $\preceq_\alpha$ by definition. Hence, we will focus our attention on the partial order $\preceq_\alpha$ restricted to all tableaux belonging to the same equivalence class under $\sim_\alpha$.

**Theorem 7.8** Let $E$ be an equivalence class of SRCT($\alpha$) under the equivalence relation $\sim_\alpha$. Then the poset $(E, \preceq_\alpha)$ has the structure of a graded lattice and is isomorphic to the subinterval $[\text{col}_{\tau_{0,E}}, \text{col}_{\tau_{1,E}}]$ under the weak Bruhat order on $\mathfrak{S}_n$.

# 8 The canonical basis

Recall that given any composition $\alpha$, we denote the unique SRCT of shape $\alpha$ and descent composition $\alpha$ by $\tau_\alpha$, called the canonical tableau of shape $\alpha$. In this section we discover a new basis for QSym arising from the orbit of each canonical tableau. For the purpose of this section, the orbit of the canonical tableau of shape $\alpha \models n$ will be referred to as $E_\alpha$. Repeating our argument from Section 6 gives us the expansion
of the quasisymmetric characteristic of the $H_n(0)$-module $S_{\alpha, E_\alpha}$ in terms of fundamental quasisymmetric functions as follows.

$$ch([S_{\alpha, E_{\alpha}}]) = \sum_{\tau \in E_{\alpha}} F_{\mathrm{comp}(\tau)} := C_{\alpha}$$

We will refer to the above quasisymmetric functions as canonical quasisymmetric functions.

**Example 8.1** Let $\alpha = (4, 3, 3)$. Then $E_\alpha$ consists of the following SRCTs.

<figure><img src="image_4.png" /></figure>

In the list above, the leftmost tableau is the source tableau while the rightmost tableau is the sink tableau, and the descents are marked in red. Thus, we calculate the canonical quasisymmetric function $C_{(4,3,3)}$ to be

$$C_{(4,3,3)} = F_{(4,3,3)} + F_{(4,2,2,2)} + F_{(3,2,2,3)} + F_{(3,2,1,2,2)}.$$

The following can be proved using a total order on compositions and studying transition matrices of QSym.

**Proposition 8.2** The set of canonical quasisymmetric functions $\{C_\alpha | \alpha \vdash n\}$ forms a $\mathbb{Z}$-basis for QSym$^n$.

Moreover we can prove the following.

**Proposition 8.3** The set of $H_n(0)$-modules $\{S_{\alpha, E_\alpha} | \alpha \vdash n\}$ is a set of pairwise non-isomorphic indecomposable modules.

# 9 Classification of cyclic modules and indecomposable modules

In this section, we will classify all compositions $\alpha \vdash n$ so that the corresponding $H_n(0)$-module $S_\alpha$ is cyclically generated by a single SRCT, termed tableau-cyclic, and use this to classify all compositions $\alpha \vdash n$ so that the corresponding $H_n(0)$-module $S_\alpha$ is indecomposable. We call a composition $\alpha = (\alpha_1, \dots, \alpha_s)$ simple if it satisfies the following condition.

* If $\alpha_i \ge \alpha_j \ge 2$ and $i < j$, then there exists a $k$ satisfying $i < k < j$ and $\alpha_k = \alpha_j - 1$.

**Example 9.1** The compositions $(2, 5, 6)$ and $(4, 1, 2, 3, 4)$ are simple, whereas $(2, 2)$, $(3, 1, 3)$ and $(5, 1, 2, 4)$ are not.

The next proposition is established by proving that $\alpha$ is a simple composition if and only if for all $\tau \in \mathrm{SRCT}(\alpha)$ the entries increase in each column form top to bottom, and then finding the number of equivalence classes that arise under $\sim_\alpha$.

**Proposition 9.2** $S_\alpha$ is a tableau-cyclic $H_n(0)$-module if and only if $\alpha$ is a simple composition of $n$.

The proposition above allows us to identify those $S_\alpha$ that are indecomposable, using classical representation theoretic techniques.

**Theorem 9.3** $S_\alpha$ is an indecomposable $H_n(0)$-module if and only if $\alpha$ is a simple composition of $n$.
# 10 Restriction rules and skew quasisymmetric Schur functions

Using the methods from the previous sections, we can obtain an $H_i(0)$-module indexed by a skew reverse composition shape $\alpha \parallel \beta$ with $i$ cells, whose quasisymmetric characteristic is the quasisymmetric skew Schur function $S_{\alpha \parallel \beta}$. We will denote this $H_i(0)$-module by $S_{\alpha \parallel \beta}$.

For $0 \le i \le n$, let $H_{i,n-i}(0)$ denote the subalgebra of $H_n(0)$ generated by

$$ \{\pi_1, \dots, \pi_{i-1}, \pi_{i+1}, \dots, \pi_{n-1}\}. $$

This subalgebra is actually isomorphic to $H_i(0) \otimes H_{n-i}(0)$. The isomorphism is obtained by mapping the generator $\pi_j$ of $H_{i,n-i}(0)$ where $1 \le j \le n-1$ and $j \ne i$ as follows.

$$ \pi_j \mapsto \begin{cases} \pi_j \otimes 1 & 1 \le j < i \\ 1 \otimes \pi_{j-i} & j > i \end{cases} \qquad (5) $$

Here, 1 denotes the unit of the 0-Hecke algebra.

Let $\alpha \vdash n$. Let $S_\alpha \downarrow_{H_{i,n-i}(0)}^{H_n(0)}$ denote $S_\alpha$ viewed as an $H_{i,n-i}(0)$-module. The isomorphism above allows us to think of $S_\alpha$ as an $H_i(0) \otimes H_{n-i}(0)$-module. Given $\tau \in \text{SRCT}(\alpha)$, let $\tau_{\le i}$ denote the SRCT comprising of all cells whose entries are $\le i$. Furthermore, let $\tau_{> i}$ denote the SRCT of straight shape comprising of all cells whose entries are $> i$ that have had $i$ subtracted from each entry.

We can use this as a key ingredient to prove the following theorem, which reflects the coproduct formula for quasisymmetric Schur functions, say [LMvW13, Theorem 5.3.8 and Corollary 5.3.9].

**Theorem 10.1** The following is an isomorphism of $H_i(0) \otimes H_{n-i}(0)$-modules.

$$ S_{\alpha} \downarrow_{H_{i,n-i}(0)}^{H_n(0)} \cong \bigoplus_{\substack{\beta \vdash n-i \\ \beta < c \alpha}} S_{\alpha \parallel \beta} \otimes S_{\beta} $$

# Acknowledgements

The authors would like to thank Vic Reiner and Jia Huang for helpful conversations, and the referees for thoughtful comments.

# References

[DKLT96] G. Duchamp, D. Krob, B. Leclerc, and J.-Y. Thibon. Fonctions quasi-symétriques, fonctions symétriques non commutatives et algèbres de Hecke à $q = 0$. C. R. Acad. Sci. Paris, 322:107–112, 1996.

[Ges84] I. Gessel. Multipartite P-partitions and inner products of skew Schur functions. Contemp. Math., 34:289–301, 1984.

[LMvW13] K. Luoto, S. Mykytiuk, and S. van Willigenburg. An introduction to quasisymmetric Schur functions: Hopf algebras, quasisymmetric functions and Young composition tableaux. Springer, 2013.

[Nor79] P. Norton. 0-Hecke algebras. J. Aust. Math. Soc., 27:337–357, 1979.