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

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 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].sub.1], ..., [[alpha].sub.k]) of n, denoted by [alpha] [??] n, to be an ordered list of positive integers whose sum is n. For convenience we define the empty composition 0 to be the unique composition of 0. We call the [[alpha].sub.i] for 1 [less than or equal to] i [less than or equal to] k the parts of [alpha], call k = l([alpha]) the length of [alpha] and call n = [absolute value of [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.sub.1] < ... < [i.sub.k]} [subset or equal to] [n - 1], we associate to it the composition [alpha] = ([i.sub.1], [i.sub.2] - [i.sub.1], ..., n - [i.sub.k]). We will refer to [alpha] as comp(S). Conversely, given a composition [alpha] = ([[alpha].sub.1], ..., [a.sub.k]) [??] n, we associate to it the subset of [n - 1] given by {[[alpha].sub.1], [[alpha].sub.1] + [[alpha].sub.2], ..., [[alpha].sub.1] + ... + [[alpha].sub.k-1]}. We will denote this subset by set ([alpha]).

Given a composition [alpha] = ([[alpha].sub.1], ..., [[alpha].sub.k]), we define its reverse composition diagram, also denoted by [alpha], to be the array of left-justified cells with [[alpha].sub.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.

Definition 2.2 The reverse composition poset ([L.sub.c], [<.sub.c]) is the poset consisting of all compositions in which [alpha] = ([[alpha].sub.1], ..., [[alpha].sub.l]) is covered by

1. (1, [[alpha].sub.1], ..., [[alpha].sub.l]), that is, the composition obtained by prefixing a part of size 1 to [alpha].

2. ([[alpha].sub.1], ..., [[alpha].sub.k] + 1, ..., [[alpha].sub.l]), provided that [[alpha].sub.i] [not equal to] [[alpha].sub.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] [<.sub.c] [alpha]. Then we define the skew reverse composition shape [alpha]//[beta] to be the array of cells of [alpha]

[alpha]//[beta] = {(i,j) [member of] [alpha] | (i,j) 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]//[beta] is [absolute value of [alpha]//[beta]] = [absolute value of [alpha]] - [absolute value of [beta]]. Also [alpha]//0 is simply the reverse composition diagram [alpha]. Hence, we write [alpha] instead of [alpha]//0 and say it is of straight shape.

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

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

Definition 2.4 Let [[alpha].sup.0], [[alpha].sup.n] be compositions such that [[alpha].sup.0] [<.sub.c] [[alpha].sup.n] in [L.sub.c], and [[alpha].sup.n] contains n more cells than [[alpha].sup.0]. Consider a saturated chain of n + 1 elements in [L.sub.c]

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Let [tau] be the filling of the cells of the skew reverse composition shape [[alpha].sup.n]//[[alpha].sup.0] such that the number n - i + 1 appears in the cell in [tau] that exists in [[alpha].sup.i] but not [[alpha].sup.i-1]. Then we say [tau] is a standard reverse composition tableau (SRCT) of shape [[alpha].sup.n]//[[alpha].sup.0], and denote the set of all SRCTs of shape [[alpha].sup.n]//[ [alpha].sup.0] by SRCT([[alpha].sup.n]//[[alpha].sup.0]).

The descent set of an SRCT [tau] of size n, denoted by Des([tau]), is

Des([tau]) = {i | i + 1 appears weakly right of i} [subset or equal to] [n - 1]

and the corresponding descent composition of [tau] is comp([tau]) = comp(Des([tau])). Given a composition [alpha] = ([[alpha].sub.1], ..., [[alpha].sub.k]), the canonical tableau of shape [alpha], denoted by [[tau].sub.[alpha]], is the unique SRCT of shape [alpha] and comp([[tau].sub.[alpha]]) = ([[alpha].sub.1], ..., [[alpha].sub.k]). In [[tau].sub.[alpha]] the first row is filled with [[alpha].sub.1], ..., 2, 1 and row i for 2 [less than or equal to] i [less than or equal to] l([alpha]) is filled with

x + [[alpha].sub.i], ..., x + 2, x + 1

where x = [[alpha].sub.1] + ... + [[alpha].sub.i-1].

Example 2.5 The saturated chain in [L.sub.c]

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

yields the following SRCT [tau] with Des([tau]) = {1,3,4,5,8}. Also shown is [[tau].sub.(2,1,4,2)].

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

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] [??] n be a composition. Then the fundamental quasisymmetric function [F.sub.[alpha]] is defined by [F.sub.0] = 1 and

where the sum is over all n-tuples ([i.sub.1], ..., [i.sub.n]) of positive integers satisfying

1 [less than or equal to] [i.sub.1] [less than or equal to] ... [less than or equal to] [i.sub.n] and [i.sub.j] < [i.sub.j+1] if j [member of] set([alpha]).

Example 2.7 We have [F.sub.(1,2)] = [x.sup.1.sub.1][x.sup.2.sub.2] + [x.sup.1.sub.1][x.sup.2.sub.3] + [x.sup.1.sub.1][x.sup.2.sub.4] + [x.sup.1.sub.2][x.sup.2.sub.3] + ... + [x.sub.1][x.sub.2][x.sub.3] + [x.sub.1][x.sub.2][x.sub.4] + ....

With this in mind, the Hopf algebra of quasisymmetric functions is defined to be the graded sub-Hopf algebra of C[[[x.sub.1], [x.sub.2], ...]]

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

where

[QSym.sup.n] = span{[F.sub.[alpha]] | [alpha] [??] n} = span{[S.sub.[alpha]] | [alpha] [??] 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]//[beta], we define the skew quasisymmetric Schur function [S.sub.[alpha]//[beta]] to be

[S.sub.[alpha]//[beta]] = [summation over(tau][member of]SRCT([alpha]//[beta])][F.sub.comp([tau])]

and when [beta] = 0 we call [S.sub.[alpha]] a quasisymmetric Schur function.

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

3 The 0-Hecke algebra

Consider the symmetric group [G.sub.n] for any positive integer n. It is generated by the adjacent transpositions [s.sub.i] = (i, i + 1) for 1 [less than or equal to] i [less than or equal to] n - 1 that satisfy the following relations.

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

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

Given a permutation [sigma] [member of] [G.sub.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 [G.sub.n] by letting l([sigma]) = number of adjacent transpositions in any reduced word for [sigma]. The 0-Hecke algebra [H.sub.n](0) is the C-algebra generated by the elements [T.sub.1], ..., [T.sub.n- 1] subject to the following relations similar to those of [G.sub.n].

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Suppose a permutation [sigma] [member of] [G.sub.n] has a reduced word of the form [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Then we define an element [T.sub.[sigma]] [member of] [H.sub.n](0) as follows.

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

The defining relations of [H.sub.n](0) imply that [T.sub.[sigma]] is independent of the choice of reduced word. Moreover, it turns out that the set {[T.sub.[sigma]] | [sigma] [member of] [G.sub.n]} is a linear basis for [H.sub.n](0). Thus, the dimension of [H.sub.n](0) is n!.

3.1 Representations of [H.sub.n](0)

Let R([H.sub.n](0)) denote the Z-span of the isomorphism classes of finite dimensional representations of [H.sub.n](0). The isomorphism class corresponding to an [H.sub.n](0)-module M will be denoted by [M]. The Grothendieck group [G.sub.0]([H.sub.n](0)) is the quotient of R([H.sub.n](0)) modulo the relations [M] = [M'] + [M"] whenever there exists a short exact sequence 0 [right arrow] M' [right arrow] M [right arrow] M" [right arrow] 0. The irreducible representations of [H.sub.n](0) form a basis for [G.sub.0]([H.sub.n](0)). Let

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

According to [Nor79], there are [2.sup.n-1] distinct irreducible representations of [H.sub.n](0). They are naturally indexed by compositions of n. Let [F.sub.[alpha]] denote the 1-dimensional C-vector space corresponding to the composition [alpha] [??] n, spanned by a vector [v.sub.[alpha]]. Let J [subset or equal to] [n - 1] be set([alpha]). Next, we define an action of the generators [T.sub.i] of [H.sub.n](0) as follows.

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Then [F.sub.[alpha]] is an irreducible 1-dimensional [H.sub.n](0)-representation.

In [DKLT96] they define a linear map

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Given an [H.sub.n](0)-module M, ch([M]) is said to be the quasisymmetrc characteristic of M. It is clear from the definition of the Grothendieck group that every time we have a short exact sequence of [H.sub.n](0)-modules, say 0 [right arrow] M' [right arrow] M [right arrow] M" [right arrow] 0, then

ch([M ]) = ch([M']) + 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] [member of] SRCT([alpha]) for some composition [alpha] [??] n, and a positive integer i such that 1 [less than or equal to] i [less than or equal to] 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] [member of] SRCT([alpha]) where [alpha] [??] n. Given a positive integer i satisfying 1 [less than or equal to] i [less than or equal to] n - 1, let [s.sub.i]([tau]) denote the filling obtained by interchanging the positions of entries i and i + 1 in [tau].

Given [tau] [member of] SRCT([alpha]), define operators [[pi].sub.i] for 1 [less than or equal to] i [less than or equal to] n - 1 as follows.

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Using combinatorics on words we can establish the following important fact.

Lemma 4.2 If [alpha] [??] n, [tau] [member of] SRCT([alpha]) and i [member of] Des([tau]) such that i and i + 1 are non-attacking, then [s.sub.i]([tau]) [member of] SRCT([alpha]).

Example 4.3 Let [tau] be the SRCT of shape (3,4,2,3) shown below.

Then Des([tau]) = {1,2,5,7,9,10}. Thus, for all 1 [less than or equal to] i [less than or equal to] 11 such that i [not member of] Des([tau]), we have that [[pi].sub.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].sub.i]([tau]) = 0. Finally, we have that [[pi].sub.1]([tau]) and [[pi].sub.5]([tau]) are as below.

Additionally, the relations satisfied by the 0-Hecke algebra are also satisfied by these operators [[pi].sub.i]. The proof involves an intricate case analysis of the action of [[pi].sub.i] on an SRCT [tau] depending on whether or not i [member of] Des([tau]).

Proposition 4.4 1. For 1 [less than or equal to] i [less than or equal to] n - 1, we have [[pi].sup.2.sub.i] = [[pi].sub.i].

2. For 1 [less than or equal to] i [less than or equal to] n - 2, we have [[pi].sub.i][[pi].sub.i+1][[pi].sub.i] = [[pi].sub.i+1][[pi].sub.i][[pi].sub.i+1].

3. For 1 [less than or equal to] i,j [less than or equal to] n - 1 such that [absolute value of (i - j)] [greater than or equal to] 2, we have [[pi].sub.i][[pi].sub.j] = [[pi].sub.j][[pi].sub.i].

5 The partial order [[??].sub.[alpha]]

Since the operators [{[[pi].sub.i]}.sup.n-1.sub.i=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].sub.[sigma]] with any permutation [sigma] [member of] [G.sub.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].sub.max], and let the entries in column i for 1 [less than or equal to] i [less than or equal to] [[alpha].sub.max] read from top to bottom be some word [w.sup.i]. We define the column word of [tau], denoted by [col.sub.[tau]] to be the word

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

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

Let [alpha] [??] n and [[tau].sub.1] [member of] SRCT([alpha]) be such that i [member of] Des([[tau].sub.1]). Suppose further that i is a non-attacking descent in [[tau].sub.1]. Let [[pi].sub.i]([[tau].sub.1]) = [[tau].sub.2]. Then [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] where [s.sub.i] = (i, i + 1) is the transposition in [G.sub.n] interchanging i and i + 1.

Lemma 5.2 Let [[tau].sub.2] be obtained by a sequence of flips starting from [[tau].sub.1]. Let [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] be a reduced word for [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

We can also say something about column words as permutations.

Lemma 5.3 Let [alpha] [??] n and [[tau].sub.1] [member of] SRCT([alpha]) be such that i [member of] Des([[tau].sub.1]). Suppose further that i is a non-attacking descent in [[tau].sub.1]. If [[pi].sub.i]([[tau].sub.1]) = [[tau].sub.2], then [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

From the above lemmas it follows that if we can reach an SRCT [[tau].sub.2] starting from [[tau].sub.1] via a sequence of flips, where [[tau].sub.2] [not equal to] [[tau].sub.1], then there does not exist a sequence of flips that takes [[tau].sub.2] to [[tau].sub.1]. Now we are in position to define a new partial order on SRCTs of the same shape.

Definition 5.4 Let [[tau].sub.1] and [[tau].sub.2] be elements of SRCT([alpha]) where [alpha] [??] n. Define a partial order [[??].sub.[alpha]] on SRCT([alpha]) by [[tau].sub.1] [[??].sub.a] [[tau].sub.2] if and only if there exists a permutation [sigma] [member of] [G.sub.n] such that [[pi].sub.[sigma]]([[tau].sub.1]) = [[tau].sub.2].

The reflexivity and transitivity of [[??].sub.[alpha]] are immediate from the definition. The anti-symmetricity follows from the remark preceding the above definition. Thus, [[??].sub.[alpha]] is indeed a partial order.

6 0-Hecke modules from SRCTs

In this section, we will define an [H.sub.n](0)-module indexed by a composition [alpha] [??] n whose quasisymmetric characteristic is the quasisymmetric Schur function [S.sub.[alpha]]. First, extend the partial order [[??].sub.[alpha]] on SRCT([alpha]) to an arbitrary total order on SRCT([alpha]). We will call this total order [[??].sup.t.sub.[alpha]]. Let the elements of SRCT([alpha]) under this total order be {[[tau].sub.1] [[??].sup.t.sub.[alpha]] ... [[??].sup.t.sub.[alpha]] [[tau].sub.m]}.

Let [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] be the C-linear span of SRCTs that are greater than or equal to an SRCT [[tau].sub.i] under the total order [[??].sup.t.sub.[alpha]]. Notice that the definition of [[??].sub.[alpha]] implies that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] for any [sigma] [member of] [G.sub.n]. This observation combined with the fact that the operators [{[[pi].sub.i]}.sup.n-1.sub.i=1] satisfy the same relations as the 0-Hecke algebra, by Proposition 4.4, gives the following result.

Lemma 6.1 [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is an [H.sub.n](0)-module.

Define [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] to be the trivial 0 module. Consider the following filtration of [H.sub.n](0)-modules.

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (1)

Then, the quotient modules [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] for 2 [less than or equal to] i [less than or equal to] m + 1 are 1-dimensional [H.sub.n](0)-modules spanned by [[tau].sub.i-1]. Furthermore, they are irreducible modules. We can identify which [H.sub.n](0)-module they are by looking at the action of [[pi].sub.j] on [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] for 1 [less than or equal to] j [less than or equal to] n - 1. We have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (2)

Thus, as an [H.sub.n](0)-representation, [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is isomorphic to the irreducible representation [F.sub.[beta]] where [beta] is the composition corresponding to the descent set Des([[tau].sub.i-1]). Thus, by Subsection 3.1

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (3)

From this it follows that

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (4)

Thus, we have established the following.

Theorem 6.2 [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is an [H.sub.n](0)-module whose quasisymmetric characteristic is the quasisymmetric Schur function [S.sub.[alpha]], where [alpha] is the shape of the SRCT [[tau].sub.1].

Henceforth, this [H.sub.n](0)-module will be denoted by [S.sub.[alpha]], that is [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and

ch([[S.sub.[alpha]]]) = [S.sub.[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 applications. As usual, we fix [alpha] to be a composition of n.

Definition 7.1 Given a word w = [w.sub.1] ... [w.sub.n] such that [w.sub.1], ..., [w.sub.n] are distinct positive integers, we say that the standardization of w is the permutation [sigma] [member of] [G.sub.n] such that [sigma](i) < [sigma](j) if and only if [w.sub.i] < [w.sub.j] for 1 [less than or equal to] i, j [less than or equal to] n.

Definition 7.2 Let [tau] be an SRCT of shape [alpha] whose largest part is [[alpha].sub.max], and let the entries in column i for 1 [less than or equal to] i [less than or equal to] [[alpha].sub.max] read from top to bottom be some word [w.sup.i]. Then we say the standardized i-th column word of [tau], denoted by [st.sub.i]([tau]) is the standardization of [w.sup.i].

Furthermore, we define the standardized column word of [tau], denoted by st([tau]) to be the word

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

With the definition of standardized column word in hand, we will define a natural equivalence relation on SRCT([alpha]) given a composition [alpha] [??] n. Define [[tau].sub.1] [~.sub.[alpha]] [[tau].sub.2] if and only if st([[tau].sub.1]) = st([[tau].sub.2]). Suppose the equivalence classes with respect to the aforementioned equivalence relation are [E.sub.1], [E.sub.2], ..., [E.sub.k]. Let [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] denote the C-linear span of all SRCTs in [E.sub.i] for i = 1, ..., k. Then we get the following isomorphism of vector spaces

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

since the equivalence classes are disjoint and their union is SRCT(a). This isomorphism is actually an isomorphism of [H.sub.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 [less than or equal to] i [less than or equal to] n - 1, we have that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] for any 1 [less than or equal to] j [less than or equal to] k.

Next, we discuss two important classes of SRCTs that will form special representatives of each equivalence class.

Definition 7.4 Let [alpha] [??] n. An SRCT [tau] of shape [alpha] is said to be a source tableau if it satisfies the condition that for every i [not member of] Des([tau]) and satisfying i [not equal to] 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 [member of] 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].

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

Lemma 7.6 Let [alpha] [??] n. Then [[tau].sub.1] [member of] SRCT([alpha]) is a source tableau if and only if there does not exist an SRCT [[tau].sub.2] [not equal to] [[tau].sub.1] such that [[pi].sub.i]([[tau].sub.2]) = [[tau].sub.1] for some positive integer i. However, [[tau].sub.1] [member of] SRCT([alpha]) is a sink tableau if and only if there does not exist an SRCT [[tau].sub.2] [not equal to] [[tau].sub.1] such that [[pi].sub.i]([[tau].sub.1]) = [[tau].sub.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].sub.0,E], and a unique sink tableau, [[tau].sub.1,E]. Thus, the number of source tableaux, number of sink tableaux, and number of equivalence classes under the equivalence relation [~.sub.[alpha]] are all equal.

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

Proposition 7.7 Let [[tau].sub.0,E] be the unique source tableau in an equivalence class E. Then [S.sub.[alpha],E] is a cyclic [H.sub.n](0)-module with generator [[tau].sub.0,E]. In particular, any tableau in E can be obtained by applying a sequence of flips to [[tau].sub.0,E].

Since flips do not change the standardized column word, we know that two SRCTs [[tau].sub.1] and [[tau].sub.2] satisfying st([[tau].sub.1]) = st([[tau].sub.2]) are incomparable under the partial order [[??].sub.[alpha]] by definition. Hence, we will focus our attention on the partial order [[??].sub.[alpha]] restricted to all tableaux belonging to the same equivalence class under [~.sub.[alpha]].

Theorem 7.8 Let E be an equivalence class of SRCT([alpha]) under the equivalence relation [~.sub.[alpha]]. Then the poset (E, [[??].sub.[alpha]]) has the structure of a graded lattice and is isomorphic to the subinterval [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] under the weak Bruhat order on [G.sub.n].

8 The canonical basis

Recall that given any composition [alpha], we denote the unique SRCT of shape [alpha] and descent composition a by [[tau].sub.[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] [??] n will be referred to as [E.sub. [alpha]]. Repeating our argument from Section 6 gives us the expansion of the quasisymmetric characteristic of the [H.sub.n](0)-module [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] in terms of fundamental quasisymmetric functions as follows.

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

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

Example 8.1 Let [alpha] = (4,3,3). Then Ea consists of the following SRCTs.

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.sub.(4,3,3)] to be

[C.sub.(4,3,3)] = [F.sub.(4,3,3)] + [F.sub.(4,2,2,2)] + [F.sub.(3,2,2,3)] + [F.sub.(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.sub.[alpha]] | [alpha] [??] n} forms a Z-basis for [QSym.sup.n].

Moreover we can prove the following.

Proposition 8.3 The set of [H.sub.n](0)-modules [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] 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] [??] n so that the corresponding [H.sub.n](0)-module [S.sub.[alpha]] is cyclically generated by a single SRCT, termed tableau-cyclic, and use this to classify all compositions [alpha] [??] n so that the corresponding [H.sub.n](0)-module [S.sub.[alpha]] is indecomposable. We call a composition [alpha] = ([[alpha].sub.1], ..., [[alpha].sub.s]) simple if it satisfies the following condition.

* If [[alpha].sub.i] [greater than or equal to] [[alpha].sub.j] [greater than or equal to] 2 and i < j, then there exists a k satisfying i < k < j and [[alpha].sub.k] = [[alpha].sub.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] [member of] SRCT([alpha]) the entries increase in each column form top to bottom, and then finding the number of equivalence classes that arise under [~.sub.[alpha]].

Proposition 9.2 [S.sub.[alpha]] is a tableau-cyclic [H.sub.n](0)-module if and only if [alpha] is a simple composition of n.

The proposition above allows us to identify those [S.sub.[alpha]] that are indecomposable, using classical representation theoretic techniques.

Theorem 9.3 [S.sub.[alpha]] is an indecomposable [H.sub.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.sub.i](0)-module indexed by a skew reverse composition shape [alpha]//[beta] with i cells, whose quasisymmetric characteristic is the quasisymmetric skew Schur function [S.sub.[alpha]//[beta]]. We will denote this [H.sub.i](0)-module by [S.sub.[alpha]//[beta]].

For 0 [less than or equal to] i [less than or equal to] n, let [H.sub.i,n-i](0) denote the subalgebra of [H.sub.n](0) generated by

{[[pi].sub.1], ..., [[pi].sub.i-1], [[pi].sub.i+1], ..., [[pi].sub.n-1]}.

This subalgebra is actually isomorphic to [H.sub.i](0) [cross product] [H.sub.n-i](0). The isomorphism is obtained by mapping the generator [[pi].sub.j] of [H.sub.i,n-i](0) where 1 [less than or equal to] j [less than or equal to] n - 1 and j [not equal to] i as follows.

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (5)

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

Let [alpha] [??] n. Let [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] denote [S.sub.[alpha]] viewed as an [H.sub.i,n-i](0)-module. The isomorphism above allows us to think of [S.sub.[alpha]] as an [H.sub.i](0) [cross product] [H.sub.n-i](0)-module. Given [tau] [member of] SRCT([alpha]), let [[tau].sub.[less than or equal to]i] denote the SRCT comprising of all cells whose entries are [less than or equal to] i. Furthermore, let [[tau].sub.>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.sub.i](0) [cross product] [H.sub.n-i](0)-modules.

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

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-symetriques, fonctions symetriques non commutatives et algebres de Hecke a 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.

Vasu V. Tewari * and Stephanie J. van Willigenburg ([dagger])

University of British Columbia, Vancouver, Canada

* Email: vasu@math.ubc.ca.

([dagger]) Email: steph@math.ubc.ca. Both authors were supported in part by the National Sciences and Engineering Research Council of Canada.