# QSym over Sym has a stable basis

Aaron Lauve¹ and Sarah K Mason²†

¹Department of Mathematics
Texas A&M University
College Station, TX 778439

²Department of Mathematics
Wake Forest University
Winston-Salem, NC 27109

**Abstract.** We prove that the subset of quasisymmetric polynomials conjectured by Bergeron and Reutenauer to be a basis for the coinvariant space of quasisymmetric polynomials is indeed a basis. This provides the first constructive proof of the Garsia–Wallach result stating that quasisymmetric polynomials form a free module over symmetric polynomials and that the dimension of this module is $n!$.

**Résumé.** Nous prouvons que le sous-ensemble des polynômes quasisymétriques conjecturé par Bergeron et Reutenauer pour former une base pour l'espace coinvariant des polynômes quasisymétriques est en fait une base. Cela fournit la première preuve constructive du résultat de Garsia–Wallach indiquant que les polynômes quasisymétriques forment un module libre sur les polynômes symétriques et que la dimension de ce module est $n!$.

**Keywords:** quasisymmetric functions, symmetric functions, free modules, compositions, inverting compositions

## 1 Introduction

Quasisymmetric polynomials have held a special place in algebraic combinatorics since their introduction in [7]. They are the natural setting for many enumeration problems [16] as well as the development of Dehn–Somerville relations [1]. In addition, they are related in a natural way to Solomon’s descent algebra of the symmetric group [14]. In this paper, we follow [2, Chapter 11] and view them through the lens of invariant theory. Specifically, we consider the relationship between the two subrings $Sym_n \subseteq QSym_n \subseteq \mathbb{Q}[x]$ of symmetric and quasisymmetric polynomials in variables $x = x_n := \{x_1, x_2, \dots, x_n\}$. Let $J_n$ denote the ideal in $QSym_n$ generated by the elementary symmetric polynomials. In 2002, F. Bergeron and C. Reutenauer made a sequence of three successively finer conjectures concerning the quotient ring $QSym_n/J_n$. A. Garsia and N. Wallach were able to prove the first two in [6], but the third one remained open; we close it here (Corollary 6) with the help of a new basis for $QSym_n$ introduced in [8].

## Acknowledgements

We would like to thank François Bergeron for sharing the preceding story with us and encouraging us to write this paper. Our approach follows an idea that he proposed during CanaDAM 2009. We also gratefully acknowledge several beneficial discussions we had with Adriano Garsia, Christophe Reutenauer, and Frank Sottile.

<footnote>†Partially supported by NSF postdoctoral fellowship DMS-0603351.</footnote>
## 1.1 Motivating context

Recall that $Sym_n$ is the ring $\mathbb{Q}[\mathbf{x}]^{\mathfrak{S}_n}$ of invariants under the permutation action of $\mathfrak{S}_n$ on $\mathbf{x}$ and $\mathbb{Q}[\mathbf{x}]$. One of the crowning results in the invariant theory of $\mathfrak{S}_n$ is that the following true statements are equivalent:

(S1) $\mathbb{Q}[\mathbf{x}]^{\mathfrak{S}_n}$ is a polynomial ring, generated, say, by the elementary symmetric polynomials $\mathcal{E}_n = \{e_1(\mathbf{x}), \dots, e_n(\mathbf{x})\}$;

(S2) the ring $\mathbb{Q}[\mathbf{x}]$ is a free $\mathbb{Q}[\mathbf{x}]^{\mathfrak{S}_n}$-module;

(S3) the coinvariant space $\mathbb{Q}[\mathbf{x}]^{\mathfrak{S}_n} = \mathbb{Q}[\mathbf{x}]/(\mathcal{E}_n)$ has dimension $n!$ and is isomorphic to the regular representation of $\mathfrak{S}_n$.

See [11, §§17, 18] for details. Analogous statements hold on replacing $\mathfrak{S}_n$ by any pseudo-reflection group. Since all spaces in question are graded, we may add a fourth item to the list: the Hilbert series $H_q(\mathbb{Q}[\mathbf{x}]^{\mathfrak{S}_n}) = \sum_{k \ge 0} d_k q^k$, where $d_k$ records the dimension of the $k$th graded piece of $\mathbb{Q}[\mathbf{x}]^{\mathfrak{S}_n}$, satisfies

$$ (S4) \quad H_q(\mathbb{Q}[\mathbf{x}]^{\mathfrak{S}_n}) = H_q(\mathbb{Q}[\mathbf{x}]) / H_q(\mathbb{Q}[\mathbf{x}]^{\mathfrak{S}_n}). $$

Before we formulate the conjectures of Bergeron and Reutenauer, we recall another page in the story of $Sym_n$ and the quotient space $\mathbb{Q}[\mathbf{x}]/(\mathcal{E}_n)$. The ring homomorphism $\zeta$ from $\mathbb{Q}[\mathbf{x}_{n+1}]$ to $\mathbb{Q}[\mathbf{x}_n]$ induced by the mapping $x_{n+1} \mapsto 0$ respects the rings of invariants (that is, $\zeta: Sym_{n+1} \to Sym_n$ is a ring homomorphism). Moreover, $\zeta$ respects the fundamental bases of monomial ($m_\lambda$) and Schur ($s_\lambda$) symmetric polynomials of $Sym_n$, indexed by partitions $\lambda$ with at most $n$ parts. For example,

$$ \zeta(m_{\lambda}(\mathbf{x}_{n+1})) = \begin{cases} m_{\lambda}(\mathbf{x}_{n}), & \text{if } \lambda \text{ has at most } n \text{ parts,} \\ 0, & \text{otherwise.} \end{cases} $$

The stability of these bases plays a crucial role in representation theory [13]. Likewise, the associated stability of bases for the coinvariant spaces (e.g., of Schubert polynomials [4, 12, 15]) plays a role in the cohomology theory of flag varieties.

## 1.2 Bergeron–Reutenauer context

Given that $QSym_n$ is a polynomial ring [14] containing $Sym_n$, one might ask, by analogy with $\mathbb{Q}[\mathbf{x}]$, how $QSym_n$ looks as a module over $Sym_n$. This was the question investigated by Bergeron and Reutenauer [3]. (See also [2, §11.2].) They began by computing the quotient $P_n(q) := H_q(QSym_n)/H_q(Sym_n)$ by analogy with (S4). To everyone's surprise, the result was a polynomial in $q$ with nonnegative integer coefficients (so it could, conceivably, enumerate the graded space $QSym_n/J_n$). More astonishingly, sending $q$ to 1 gave $P_n(1) = n!$. This led to the following two conjectures, subsequently proven in [6]:

(Q1) The ring $QSym_n$ is a free module over $Sym_n$;

(Q2) The dimension of the “coinvariant space” $QSym_n/J_n$ is $n!$.

In their efforts to solve the conjectures above, Bergeron and Reutenauer introduced the notion of “pure and inverting” compositions $B_n$ with at most $n$ parts. These compositions have the favorable property of being $n$-stable in that $B_n \subseteq B_{n+1}$ and that $B_{n+1} \setminus B_n$ are the pure and inverting compositions with exactly
$n+1$ parts. They were able to show that the pure and inverting “quasi-monomials” $M_\beta$ (see Section 2) span $QSym_n/J_n$ and that they are $n!$ in number. However, the linear independence of these polynomials over $Sym_n$ remained open. Their final conjecture, which we prove in Corollary 6, is as follows:

(Q3) The set of quasi-monomials $\{M_\beta : \beta \in B_n\}$ is a basis for $QSym_n/J_n$.

The balance of this paper is organized as follows. In Section 2, we recount the details surrounding a new basis $\{S_\alpha\}$ for $QSym_n$ called the quasisymmetric Schur polynomials. These behave particularly well with respect to the $Sym_n$ action in the Schur basis. In Section 3, we give further details surrounding the “coinvariant space” $QSym_n/J_n$. These include a bijection between compositions $\alpha$ and pairs $(\lambda, \beta)$, with $\lambda$ a partition and $\beta$ a pure and inverting composition, that informs our main results. Section 4 contains these results—a proof of (Q3), but with the quasi-monomials $M_\beta$ replaced by the quasisymmetric Schur polynomials $S_\beta$. We conclude in Section 5 with some corollaries to the proof. These include (Q3), as originally stated, as well as a version of (Q1) and (Q3) over the integers.

## 2 Quasisymmetric polynomials

A polynomial in $n$ variables $x = \{x_1, x_2, \dots, x_n\}$ is said to be *quasisymmetric* if and only if for each composition $(\alpha_1, \alpha_2, \dots, \alpha_k)$, the monomial $x_1^{\alpha_1} x_2^{\alpha_2} \cdots x_k^{\alpha_k}$ has the same coefficient as $x_{i_1}^{\alpha_1} x_{i_2}^{\alpha_2} \cdots x_{i_k}^{\alpha_k}$ for all sequences $1 \le i_1 < i_2 < \cdots < i_k \le n$. For example, $x_1^2 x_2 + x_1^2 x_3 + x_2^2 x_3$ is a quasisymmetric polynomial in the variables $\{x_1, x_2, x_3\}$. The ring of quasisymmetric polynomials in $n$ variables is denoted $QSym_n$. (Note that every symmetric polynomial is quasisymmetric.)

It is easy to see that $QSym_n$ has a vector space basis given by the quasi-monomials

$$M_{\alpha}(\mathbf{x}) = \sum_{i_1 < \cdots < i_k} x_{i_1}^{\alpha_1} \cdots x_{i_k}^{\alpha_k},$$

for $\alpha = (\alpha_1, \dots, \alpha_k)$ running over all compositions with at most $n$ parts. It is less evident that $QSym_n$ is a ring, but see [10] for a formula for the product of two quasi-monomials. We write $l(\alpha) = k$ for the length (number of parts) of $\alpha$ in what follows. We return to the quasi-monomial basis in Section 5, but for the majority of the paper, we focus on the basis of “quasisymmetric Schur polynomials” as its known multiplicative properties assist in our proofs.

### 2.1 The basis of quasisymmetric Schur polynomials

A quasisymmetric Schur polynomial $S_\alpha$ is defined combinatorially through fillings of composition diagrams. Given a composition $\alpha = (\alpha_1, \alpha_2, \dots, \alpha_k)$, its associated diagram is constructed by placing $\alpha_i$ boxes, or cells, in the $i^{th}$ row from the top. (See Figure 1.) The cells are labeled using matrix notation; that is, the cell in the $j^{th}$ column of the $i^{th}$ row of the diagram is denoted $(i, j)$. We abuse notation by writing $\alpha$ to refer to the diagram for $\alpha$.

Given a composition diagram $\alpha = (\alpha_1, \alpha_2, \dots, \alpha_\ell)$ with largest part $m$, we define a *composition tableau* $T$ of shape $\alpha$ to be a filling of the cells $(i, j)$ of $\alpha$ with positive integers $T(i, j)$ such that

(CT1) entries in the rows of $T$ weakly decrease when read from left to right,

(CT2) entries in the leftmost column of $T$ strictly increase when read from top to bottom,
<figure><img src="image_1.png" /><figcaption>FIG. 1: The diagram associated to the composition (2, 4, 3, 2, 4)</figcaption></figure>

(CT3) entries satisfy the triple rule:

Let $(i, k)$ and $(j, k)$ be two cells in the same column so that $i < j$. If $\alpha_i \ge \alpha_j$ then either $T(j, k) < T(i, k)$ or $T(i, k-1) < T(j, k)$. If $\alpha_i < \alpha_j$ then either $T(j, k) < T(i, k)$ or $T(i, k) < T(j, k+1)$.

Assign a weight, $x^T$ to each composition tableau $T$ by letting $a_i$ be the number of times $i$ appears in $T$ and setting $x^T = \prod x_i^{a_i}$. The quasisymmetric Schur polynomial $S_\alpha$ corresponding to the composition $\alpha$ is defined by

$$S_\alpha(\mathbf{x}_n) = \sum_T x^T,$$

the sum being taken over all composition tableaux $T$ of shape $\alpha$ with entries chosen from $[n]$. (See Figure 2.) Each polynomial $S_\alpha$ is quasisymmetric and the collection $\{S_\alpha : l(\alpha) \le n\}$ forms a basis for $QSym_n$ [8].

<figure><img src="image_2.png" /><figcaption>FIG. 2: The composition tableaux encoded in the polynomial $S_{(3,1,2)}(\mathbf{x}_4) = x_1^3 x_2 x_3^2 + x_1^3 x_2 x_3 x_4 + x_1 x_2^2 x_3 x_4^2 + x_2^3 x_3 x_4^2$.</figcaption></figure>

## 2.2 Sym action in the Quasisymmetric Schur polynomial basis

We need several definitions in order to describe the multiplication rule for quasisymmetric Schur polynomials found in [9]. The reverse of a partition $\lambda$ is the composition $\lambda^*$ obtained by reversing the order of its parts. Symbolically, if $\lambda = (\lambda_1, \lambda_2, \dots, \lambda_k)$ then $\lambda^* = (\lambda_k, \dots, \lambda_2, \lambda_1)$. Let $\beta$ be a composition, let $\lambda$ be a partition, and let $\alpha$ be a composition obtained by adding $|\lambda|$ cells to $\beta$, possibly between adjacent rows of $\beta$. A filling of the cells of $\alpha$ is called a *Littlewood–Richardson composition tableau* of shape $\alpha/\beta$ if it satisfies the following rules:

(LR1) The $i^{th}$ row from the bottom of $\beta$ is filled with the entries $k + i$.

(LR2) The content of the appended cells is $\lambda^*$.

(LR3) The filling satisfies conditions (CT1) and (CT3) from Section 2.1.

(LR4) The entries in the appended cells, when read from top to bottom, column by column, from right to left, form a *reverse lattice word*. That is, one for which each prefix contains at least as many $i$'s as $(i-1)$'s for each $1 < i \le k$.
The following theorem provides a method for multiplying an arbitrary quasisymmetric Schur polynomial by an arbitrary Schur polynomial.

**Theorem 1 ([9]) In the expansion**

$$s_{\lambda}(\mathbf{x}) \cdot S_{\alpha}(\mathbf{x}) = \sum_{\gamma} C_{\lambda\alpha}^{\gamma} S_{\gamma}(\mathbf{x}), \qquad (1)$$

the coefficient $C_{\lambda\alpha}^{\gamma}$ is the number of Littlewood-Richardson composition tableaux of shape $\gamma/\alpha$ with content $\lambda^*$.

### 3 The coinvariant space for quasisymmetric polynomials

Let $B \subseteq A$ be two $\mathbb{Q}$-algebras with $A$ a free left module over $B$. This implies the existence of a subset $C \subseteq A$ with $A \simeq B \otimes C$ as vector spaces over $\mathbb{Q}$. In the classical setting of invariant theory (where $B$ is the subring of invariants for some group action on $A$), this set $C$ is identified as coset representatives for the quotient $A/(B_+)$, where $(B_+)$ is the ideal in $A$ generated by the positive part of the graded algebra $B = \bigoplus_{k \ge 0} B_k$.

Now suppose that $A$ and $B$ are graded rings. If $A$ is free over $B$, then the Hilbert series of $C$ is given as the quotient $H_q(A)/H_q(B)$. Let us try this with the choice $A = QSym_n$ and $B = Sym_n$. It is well-known that the Hilbert series for $QSym_n$ and $Sym_n$ are given by

$$H_q(QSym_n) = 1 + \frac{q}{1-q} + \cdots + \frac{q^n}{(1-q)^n} \qquad (2)$$

and

$$H_q(Sym_n) = \prod_{i=1}^{n} \frac{1}{1 - q^i}. \qquad (3)$$

Let $P_n(q) = \sum_{k \ge 0} p_k q^k$ denote the quotient of (2) by (3). It is easy to see that

$$P_n(q) = \prod_{i=1}^{n-1} (1 + q + \cdots + q^i) \sum_{i=0}^{n} q^i (1 - q)^{n-i},$$

and hence $P_n(1) = n!$. It is only slightly more difficult (see (0.13) in [6]) to show that $P_n(q)$ satisfies the recurrence relation

$$P_n(q) = P_{n-1}(q) + q^n ([n]_q! - P_{n-1}(q)), \qquad (4)$$

where $[n]_q!$ is the standard $q$-version of $n!$. Bergeron and Reutenauer use this recurrence to show that $p_k$ is a nonnegative integer for all $k \ge 0$ and to produce a set of compositions $B_n$ satisfying $p_k = \#\{\beta \in B_n : |\beta| = k\}$ for all $n$. In particular, $|B_n| = n!$.

Let $J_n$ be the ideal in $QSym_n$ generated by all symmetric polynomials with zero constant term and call $R_n := QSym_n/J_n$ the coinvariant space for quasisymmetric polynomials. From the above discussion, $R_n$ has dimension at most $n!$. If the set of quasi-monomials $\{M_{\beta} \in QSym_n : \beta \in B_n\}$ are linearly independent over $Sym_n$, then it has dimension exactly $n!$ and $QSym_n$ becomes a free $Sym_n$ module of the same dimension.
## 3.1 Destandardization of permutations

To produce a set $B_n$ of compositions indexing a proposed basis of $R_n$, first recognize the $[n]_q!$ in (4) as the Hilbert series for the classical coinvariant space $\mathbb{Q}[\mathbf{x}]/(\mathcal{E}_n)$ from (S3). The standard set of compositions indexing this space are the Artin monomials $\{x_1^{\alpha_1} \cdots x_n^{\alpha_n} : 0 \le \alpha_i \le n-i\}$, but these do not fit into the desired recurrence (4) with $n$-stability. In [5], Garsia developed an alternative set of monomials indexed by permutations. His “descent monomials” (actually, the “reversed” descent monomials, see [6, §6]) were chosen as the starting point for the recursive construction of the sets $B_n$. Here we give a description in terms of “destandardized permutations.”

In what follows, we view partitions and compositions as words in the alphabet $\mathbb{N} = \{0, 1, 2, \dots\}$. For example, we write $2543$ for the composition $(2, 5, 4, 3)$. The standardization $\text{st}(w)$ of a word $w$ of length $k$ is a permutation in $\mathfrak{S}_k$ obtained by first replacing (from left to right) the $\ell_1$ 1s in $w$ with the numbers $1, \dots, \ell_1$, then replacing (from left to right) the $\ell_2$ 2s in $w$ with the numbers $\ell_1+1, \dots, \ell_1+\ell_2$, and so on. For example, $\text{st}(121) = 132$ and $\text{st}(2543) = 1432$. The destandardization $\mathbf{d}(\sigma)$ of a permutation $\sigma \in \mathfrak{S}_k$ is the lexicographically least word $w \in \mathbb{P}^k$ satisfying $\text{st}(w) = \sigma$. For example, $\mathbf{d}(132) = 121$ and $\mathbf{d}(1432) = 1321$. Let $D_{(n)}$ denote the compositions $\{\mathbf{d}(\sigma) : \sigma \in \mathfrak{S}_n\}$. Finally, given $\mathbf{d}(\sigma) = (\alpha_1, \dots, \alpha_k)$, let $\mathbf{r}(\sigma)$ denote the vector difference $(\alpha_1, \dots, \alpha_k) - 1^k$ (leaving in place any zeros created in the process). For example, $\mathbf{r}(132) = 010$ and $\mathbf{r}(1432) = 0210$. Up to a relabelling, the weak compositions $\mathbf{r}(\sigma)$ are the ones introduced by Garsia in [5].

Bergeron and Reutenauer define their sets $B_n$ recursively in such a way that

$$ \bullet \ B_0 := \{0\}, $$

$$ \bullet \ 1^n + B_{n-1} \subseteq D_{(n)} \text{ and } D_{(n)} \text{ is disjoint from } B_{n-1}, \text{ and} $$

$$ \bullet \ B_n := B_{n-1} \cup D_{(n)} \setminus (1^n + B_{n-1}). $$

Here, $1^n + B_{n-1}$ denotes the vector sums $\{1^n + \mathbf{d} : \mathbf{d} \in B_{n-1}\}$. Note that the compositions in $D_{(n)}$ all have length $n$. Moreover, $1^{n+1} + D_{(n)} \subseteq D_{(n+1)}$. Indeed, if $\sigma = \sigma'1$ is a permutation in $\mathfrak{S}_{n+1}$ with suffix “1” in one-line notation, then $1^{n+1} + \mathbf{d}(\text{st}(\sigma')) = \mathbf{d}(\sigma)$. That (4) enumerates $B_n$ is immediate [6, Proposition 6.1]. We give the first few sets $B_n$ and $D_{(n)}$ in Figure 3.

<figure><img src="image_3.png" /><figcaption>FIG. 3: The sets $D_{(n)}$ and $B_n$ for small values of $n$. Compositions $1^n + B_{n-1}$ are underlined in $D_n$.</figcaption></figure>

## 3.2 Pure and inverting compositions

We now give an alternative description of the compositions in $B_n$ that will be easier to work with in what follows. Call a composition $\alpha$ inverting if and only if for each $i > 1$ there exists a pair of indices $s < t$
such that $\alpha_s = i$ and $\alpha_t = i - 1$. For example, 13112312 is inverting while 21123113 is not. Any composition $\alpha$ admits a unique factorization

$$ \alpha = \gamma k^{i_k} \cdots 2^{i_2} 1^{i_1}, \quad (i_j \ge 1) $$

such that $\gamma$ is a composition that does not contain any of the values from 1 to $k$, and $k$ is maximal (but possibly zero). We say $\alpha$ is pure if and only if this maximal $k$ is even. (Note that if the last part of a composition is not 1, then $k = 0$ and the composition is pure.) For example, 5435211 is pure with $k = 2$ while 3231 is impure since $k = 1$.

**Proposition 2 (Bergeron and Reutenauer)** *The set of inverting compositions of length $n$ is precisely $D_{(n)}$. The set of pure and inverting compositions of length at most $n$ is precisely $B_n$. □*

Let $C_{n,d}$ be the set of all compositions of $d$ into at most $n$ parts and set $\text{PB}_{n,d} := \{(\lambda, \beta) : \lambda$ a partition, $\beta \in B_n, |\lambda| + |\beta| = d$, and $l(\lambda) \le n, l(\beta) \le n\}$. We define a map $\phi: \text{PB}_{n,d} \to C_{n,d}$ as follows. Given an arbitrary element $(\lambda, \beta)$ be of $\text{PB}_{n,d}$, $\phi((\lambda, \beta))$ is the composition obtained by adding $\lambda_i$ to the $i^{th}$ largest part of $\beta$ for each $1 \le i \le l(\lambda)$, where if $\beta_j = \beta_k$ and $j < k$, then $\beta_j$ is considered smaller than $\beta_k$. If $l(\lambda) > l(\beta)$, append zeros after the last part to lengthen $\beta$ before applying $\phi$. (See Figure 4.)

$$ \begin{array}{c} \lambda = \ 1 \ 4 \ 2 \ 1 \ 1 \ 4 \ 5 \ 2 \ 4 \ 1 \ 1 \\ \beta = \ 2 \ 4 \ 3 \ 1 \ 1 \ 3 \ 4 \ 2 \ 3 \\ \hline \phi(\lambda, \beta) = \ 3 \ 8 \ 5 \ 2 \ 2 \ 7 \ 9 \ 4 \ 7 \ 1 \ 1 \end{array} $$

<caption>FIG. 4: An example of the map $\phi: \text{PB}_{13,49} \to C_{13,49}$.</caption>

**Proposition 3** *The map $\phi$ is a bijection between $\text{PB}_{n,d}$ and $C_{n,d}$*

**Proof:** We prove this by describing the inverse $\phi^{-1}$ algorithmically. Let $\alpha$ be an arbitrary composition in $C_{n,d}$ and set $(\lambda, \beta) := (\emptyset, \alpha)$.

1. If $\beta$ is pure and inverting, then $\phi^{-1}(\alpha) := (\lambda, \beta)$

2. If $\beta$ is impure and inverting, then set $\phi^{-1}(\alpha) := (\lambda + (1^n), \beta - (1^n))$.

3. If $\beta$ is not inverting, then let $j$ be the smallest part of $\beta$ such that there does not exist a pair of indices $s < t$ such that $\beta_s = j$ and $\beta_t = j - 1$. Let $m$ be the number of parts of $\beta$ which are greater than or equal to $j$. Replace $\beta$ by the composition obtained by subtracting 1 from each part greater than or equal to $j$ and replace $\lambda$ by the partition obtained by adding 1 to each of the first $m$ parts.

4. Repeat until $\phi^{-1}$ is obtained. That is, until Step (1) or (2) above is followed.

To see that $\phi\phi^{-1} = \mathbb{1}$, consider an arbitrary composition $\alpha$. If $\alpha$ is pure and inverting, then $\phi\phi^{-1}(\alpha) = \phi(\emptyset, \alpha) = \alpha$. If $\alpha$ is impure and inverting, then $\phi(\phi^{-1}(\alpha)) = \phi((1^{l(\alpha)}), \alpha - (1^{l(\alpha)})) = \alpha$. Consider therefore a composition $\alpha$ which is not inverting. Note that the largest entry in $\alpha$ is decreased at each iteration of the procedure. Therefore the largest entry in the partition records the number of times the largest entry in $\alpha$ is decreased. Similarly, for each $i \le l(\lambda)$, the $i^{th}$ largest entry in $\alpha$ is decreased by one
$\lambda_i$ times. This means that the $i^{th}$ largest part of $\alpha$ is obtained by adding $\lambda_i$ to the $i^{th}$ largest part of $\beta$ and therefore our procedure $\phi^{-1}$ inverts the map $\phi$. $\square$

Figure 5 illustrates the algorithmic description of $\phi^{-1}$ as introduced in the proof of Proposition 3 on $\alpha = 38522794711$.

<figure><img src="image_4.png" /><figcaption>FIG. 5: The map $\phi^{-1}: C_{13,49} \to PB_{13,49}$ applied to $\alpha = 38522794711$. Parts $j$ from Step 3 of the algorithm are marked with a double underscore.</figcaption></figure>

# 4 Main Results

Let $B_n$ be as in Section 3 and set $B_n := \{S_\beta : \beta \in B_n\}$. We prove the following.

**Theorem 4** The set $B_n$ is a basis for the $\mathrm{Sym}_n$-module $R_n$.

To prove this, we focus on the quasisymmetric polynomials $\mathrm{QSym}_{n,d}$ in $n$ variables of homogeneous degree $d$. Note that $\mathrm{QSym}_n = \bigoplus_{d \ge 0} \mathrm{QSym}_{n,d}$ and therefore if $\mathfrak{C}_{n,d}$ is a basis for $\mathrm{QSym}_{n,d}$, then the collection $\bigcup_{d \ge 0} \mathfrak{C}_{n,d}$ is a basis for $\overline{\mathrm{QSym}}_n$.

First, we introduce a useful term order. Each composition $\alpha$ can be rearranged to form a partition $\lambda(\alpha)$ by arranging the parts in weakly decreasing order. Recall the *lexicographic* order $\succeq$ on partitions of $n$, which states that $\lambda \succeq \mu$ if and only if the first nonzero entry in $\lambda - \mu$ is positive. For two compositions $\alpha$ and $\gamma$ of $n$, we say that $\alpha$ is larger then $\gamma$ in *revlex* order (written $\alpha \succ \gamma$) if and only if either

* $\lambda(\alpha) \succeq \lambda(\gamma)$, or

* $\lambda(\alpha) = \lambda(\gamma)$ and $\alpha$ is lexicographically larger than $\gamma$ when reading right to left.

For instance, we have

$$4 \succeq 13 \succeq 31 \succeq 22 \succeq 112 \succeq 121 \succeq 211 \succeq 1111.$$

*Remark:* Extend revlex to weak compositions of length at most $n$ by padding the beginning of $\alpha$ or $\gamma$ with zeros as necessary, so $l(\alpha) = l(\gamma) = n$. Viewing these as exponent vectors for monomials in $\mathbf{x}$ provides a term ordering on $\mathbb{Q}[\mathbf{x}]$. However, it is not good term ordering in the sense that it is not multiplicative: given exponent vectors $\alpha, \beta$, and $\gamma$ with $\alpha \succeq \gamma$, it is not necessarily the case that $\alpha + \beta \succeq \gamma + \beta$. This is no doubt the trouble encountered in [3] and [6] when trying to prove the Bergeron–Reutenauer conjecture (Q3). We circumvent this difficulty by working with the Schur polynomials $s_\lambda$ and the quasisymmetric
Schur polynomials $S_\alpha$. We consider leading polynomials $S_\gamma$ instead of leading monomials $x^\gamma$. The leading term $S_\gamma$ in a product $s_\lambda \cdot S_\alpha$ is readily found.

**Proof of Theorem 4:** We claim that the collection $\mathcal{C}_{n,d} = \{s_\lambda S_\beta : |\lambda| + |\beta| = d, l(\lambda) \le n, l(\beta) \le n, \text{ and } \beta \in B_n\}$ is a basis for $QSym_{n,d}$, which in turn implies that $B_n$ is a basis for $R_n$.

We define an ordering on $\mathcal{C}_{n,d}$ by using the map $\phi$ and the revlex ordering on compositions. Note that $\mathcal{C}_{n,d}$ is indexed by pairs $(\lambda, \beta)$, where $\lambda$ is a partition of some $k \le d$ and $\beta$ is a composition of $d-k$ which lies in $B_n$. We claim that the leading term in the quasisymmetric Schur polynomial expansion of $s_\lambda S_\beta$ is the polynomial $S_{\phi(\lambda,\beta)}$. To see this, recall that the terms of $s_\lambda S_\beta$ are given by Littlewood-Richardson composition tableaux of shape $\alpha/\beta$ and content $\lambda^*$, where $\alpha$ is an arbitrary composition shape obtained by appending $|\lambda|$ cells to the diagram of $\beta$ so that conditions (CT1) and (CT3) are satisfied.

To form the largest possible composition (in revlex order), one first appends as many cells as possible to the longest row of $\beta$. (Again, the lower of two equal rows is considered longer.) This new longest row must end in an $L := l(\lambda)$, since the reading word of the Littlewood-Richardson composition tableau must satisfy (LR4). No entry smaller than $L$ can appear to the left of $L$ in this row, since the row entries are weakly decreasing from left to right. Thus the maximum possible number of entries that could be added to the longest row of $\beta$ is $\lambda_1$. Similarly, the maximum possible number of entries that can be added to the second longest row of $\beta$ is $\lambda_2$ and so on. If $l(\lambda) > l(\beta)$, append the extra parts of $\lambda$ to end of $\beta$.

We must show that this largest possible shape is indeed the shape of a Littlewood-Richardson composition tableau obtained by adding cells with content $\lambda^*$ to the diagram of $\beta$. Place the entries of $\lambda^*$ into the new cells as described above, with the following exception. If two augmented rows have the same length and the corresponding parts of $\lambda^*$ are equal, then place the larger entries into the higher of the two rows.

Such a filling $T$ of shape $\alpha$ satisfies (CT1) by construction. To prove that the filling $S(\lambda, \beta)$ satisfies (CT3), consider an arbitrary pair of cells $(i, k)$ and $(j, k)$ in the same column. If $\alpha_i \ge \alpha_j$ then $\beta_i \ge \beta_j$, since the entries from $\lambda$ are appended to the rows of $\beta$ from largest row to smallest row. Therefore if $(i, k)$ is a cell in the diagram of $\beta$ then $T(j, k) < T(i, k) = T(i, k-1)$ regardless of whether or not $(j, k)$ is in the diagram of $\beta$. If $(i, k)$ is not in the diagram of $\beta$ then $(j, k)$ cannot be in the diagram of $\beta$ since $\beta_i \ge \beta_j$. Therefore $T(j, k) < T(i, k)$ since the smaller entry is placed into the shorter row, or the lower row if the rows have equal length.

If $\alpha_i < \alpha_j$ then $\beta_i \le \beta_j$. If $T(i, k) \le T(j, k)$ then $(i, k)$ is not in the diagram of $\beta$. If $(j, k+1)$ is in the diagram of $\beta$ then $T(i, k) < T(j, k+1)$ since the entries in the diagram of $\beta$ are larger than the appended entries. Otherwise the cell $(j, k+1)$ is filled with a larger entry than $(i, k)$ since the longer rows are filled with larger entries and $\alpha_j > \alpha_i$. Therefore the entries in $S(\lambda, \beta)$ satisfy (CT3).

To see that the reading word of such a filling satisfies (LR4), consider an entry $i$. We must show that an arbitrary prefix of the reading word contains at least as many $i$'s as $(i-1)$'s. Let $c_i$ be the rightmost column of $T$ containing the letter $i$ and let $c_{i-1}$ be the rightmost column of $T$ containing the letter $i-1$. If $c_i > c_{i-1}$ then every prefix will contain at least as many $i$'s as $(i-1)$'s since there will always be at least one $i$ appearing before any pairs $i, i-1$ in reading order. If $c_i = c_{i-1}$, then the entry $i$ will appear in a higher row than the entry $i-1$ and hence will be read first for each column containing both an $i$ and an $i-1$. Therefore the reading word is a reverse lattice word and hence the filling constructed above is indeed a Littlewood-Richardson composition tableau. The shape of this Littlewood-Richardson composition tableau corresponds to the largest composition appearing as an index of a quasisymmetric Schur polynomial in the expansion of $s_\lambda S_\beta$, so $S_{\phi(\lambda,\beta)}$ is indeed the leading term in this expansion. Since $\phi$ is a bijection, the entries in $\mathcal{C}_{n,d}$ span $QSym_{n,d}$ and are linearly independent. Therefore $\mathcal{C}_{n,d}$ is a basis
for $QSym_{n,d}$ and hence $B_n$ is a basis for the $Sym_n$-module $R_n$.

□

The transition matrix between the basis $\mathfrak{C}_{3,4}$ and the quasisymmetric Schur polynomial basis for $QSym_{3,4}$ is given in Table 1. Note that this is an upper unitriangular matrix. In fact, this is true in general and therefore the algebra $QSym_n(\mathbb{Z})$ is a free module over $Sym_n(\mathbb{Z})$. A basis is given by $\{s_\lambda S_\beta : \beta \in \Pi_n, l(\lambda) \le n, \text{ and } l(\beta) \le n\}$. Replacing $S_\beta$ by $M_\beta$ results in an alternative basis.

<table><caption>TAB. 1: The transition matrix for $n = 3, d = 4$.</caption><thead><tr><th></th><th>4</th><th>13</th><th>31</th><th>22</th><th>112</th><th>121</th><th>211</th></tr></thead><tbody><tr><th>$s_4$</th><td>1</td><td>.</td><td>.</td><td>.</td><td>.</td><td>.</td><td>.</td></tr><tr><th>$s_{31}$</th><td>.</td><td>1</td><td>1</td><td>.</td><td>.</td><td>.</td><td>.</td></tr><tr><th>$s_1 \cdot S_{21}$</th><td>.</td><td>.</td><td>1</td><td>1</td><td>.</td><td>.</td><td>1</td></tr><tr><th>$s_{22}$</th><td>.</td><td>.</td><td>.</td><td>1</td><td>.</td><td>.</td><td>.</td></tr><tr><th>$s_{211}$</th><td>.</td><td>.</td><td>.</td><td>.</td><td>1</td><td>.</td><td>.</td></tr><tr><th>$S_{121}$</th><td>.</td><td>.</td><td>.</td><td>.</td><td>.</td><td>1</td><td>.</td></tr><tr><th>$S_{211}$</th><td>.</td><td>.</td><td>.</td><td>.</td><td>.</td><td>.</td><td>1</td></tr></tbody></table>

# 5 Corollaries and applications

## 5.1 Closing the Bergeron–Reuteuaner conjecture

In [8, Theorem 6.1], it was shown that the polynomials $M_\gamma$ are related to the polynomials $S_\alpha$ as follows:

$$S_{\alpha} = \sum_{\gamma} K_{\alpha, \gamma} M_{\gamma}, \qquad (5)$$

where $K_{\alpha,\gamma}$ counts the number of composition tableaux $T$ of shape $\alpha$ and content $\gamma$.

**Lemma 5** In the expansion $M_\alpha = \sum_\gamma \tilde{K}_{\alpha,\gamma} S_\gamma$, if $\tilde{K}_{\alpha,\gamma} \neq 0$ then $\alpha \succeq \gamma$. Also, $\tilde{K}_{\alpha,\alpha} = 1$.

**Proof:** Theorem 6.1 and Proposition 6.7 in [8] reveal that the transition matrix $K = (K_{\alpha,\gamma})$ defined in (5) is upper-unitriangular with respect to $\succeq$. That is, $\alpha \prec \gamma$ implies $K_{\alpha,\gamma} = 0$ and $K_{\alpha,\alpha} = 1$. A closer analysis shows that, moreover, $K_{\alpha,\gamma} = 0$ when $\alpha \neq \gamma$ but $\lambda(\alpha) = \lambda(\gamma)$. The desired result for $\tilde{K} = K^{-1}$ follows readily from this fact. □

We are ready to prove Conjecture (Q3). Let $B_n$ and $R_n$ be as in Section 4.

**Corollary 6** The set $\{M_\beta : \beta \in B_n\}$ is a basis for the $Sym_n$-module $R_n$.

**Proof:** We show that the collection $\mathfrak{M}_{n,d} = \{s_\lambda M_\beta : |\lambda| + |\beta| = d, l(\lambda) \le n, l(\beta) \le n, \text{ and } \beta \in B_n\}$ is a basis for $QSym_{n,d}$, which in turn implies that $\{M_\beta : \beta \in B_n\}$ is a basis for $R_n$. We first claim that the leading term in the quasisymmetric Schur polynomial expansion of $s_\lambda M_\beta$ is indexed by the composition $\phi(\lambda, \beta)$. The corollary will easily follow.
Applying Lemma 5, we may write $s_{\lambda}M_{\beta}$ as

$$s_{\lambda}M_{\beta} = s_{\lambda}S_{\beta} + \sum_{\beta \succ \gamma} \tilde{K}_{\beta, \gamma} s_{\lambda}S_{\gamma}.$$

Given any composition $\gamma$, the leading term of $s_{\lambda}S_{\gamma}$ is indexed by $\phi(\lambda, \gamma)$. This follows by the reasoning used in the proof of Theorem 4. We prove the claim by showing that $\beta \succ \gamma \implies \phi(\lambda, \beta) \succ \phi(\lambda, \gamma)$.

Assume first that $\lambda(\beta) = \lambda(\gamma)$. Let $i$ be the greatest integer such that $\beta_i > \gamma_i$. The map $\phi$ adds $\lambda_j$ cells to $\beta_i$ and $\lambda_k$ cells to $\gamma_i$, where $\lambda_j \ge \lambda_k$. Therefore $\beta_i + \lambda_j > \gamma_i + \lambda_k$. Since the parts of $\phi(\lambda, \beta)$ and $\phi(\lambda, \gamma)$ are equal after part $i$, we have $\phi(\lambda, \beta) \succeq \phi(\lambda, \gamma)$.

Next assume that $\lambda(\beta) \succ \lambda(\gamma)$. Consider the smallest $i$ such that the $i^{th}$ largest part $\beta_j$ of $\beta$ is not equal to the $i^{th}$ largest part $\gamma_k$ of $\gamma$. The map $\phi$ adds $\lambda_i$ cells to $\beta_j$ and to $\gamma_k$, so that $\beta_j + \lambda_i > \gamma_k + \lambda_i$. Since the largest $i-1$ parts of $\phi(\lambda, \beta)$ and $\phi(\lambda, \gamma)$ are equal, we have $\lambda(\phi(\lambda, \beta)) \succ \lambda(\phi(\lambda, \gamma))$.

We now use the claim to complete the proof. Following the proof of Theorem 4, we arrange the products $s_{\lambda}M_{\beta}$ as row vectors written in the basis of quasisymmetric Schur polynomials. The claim shows that the corresponding matrix is upper-unitriangular. Thus $\mathfrak{M}_{n,d}$ forms a basis for $\mathcal{QSym}_{n,d}$, as desired. $\square$

## 5.2 Triangularity

It was shown in Section 4 that the transition matrix between the bases $\mathfrak{C}$ and $\{S_{\alpha}\}$ is triangular with respect to the revlex ordering. Here, we show that a stronger condition holds: it is triangular with respect to a natural partial ordering on compositions. Every composition $\alpha$ has a corresponding partition $\lambda(\alpha)$ obtained by arranging the parts of $\alpha$ in weakly decreasing order. A partition $\lambda$ is said to dominate a partition $\mu$ iff $\sum_{i=1}^k \lambda_i \ge \sum_{i=1}^k \mu_i$ for all $k$. Let $C_{\lambda, \beta}^{\alpha}$ be the coefficient of $S_{\alpha}$ in the expansion of the product $s_{\lambda}S_{\beta}$.

**Theorem 7** If $\lambda(\alpha)$ is not dominated by $\lambda(\phi(\lambda, \beta))$, then $C_{\lambda, \beta}^{\alpha} = 0$.

**Proof:** Let $(\lambda, \beta)$ be an arbitrary element of $\mathrm{PB}_{n,d}$ and let $\alpha$ be an arbitrary element of $C_{n,d}$. Set $\gamma := \phi(\lambda, \beta)$. If $\alpha \succeq \gamma$ then $C_{\lambda, \beta}^{\alpha} = 0$ (by the proof of Theorem 4) and we are done. Hence, assume that $\alpha \succeq \phi(\lambda, \beta) = \gamma$ and that $\lambda(\alpha)$ is not dominated by $\lambda(\gamma)$. Let $k$ be the smallest positive integer such that $\sum_{i=1}^k \lambda(\alpha)_i > \sum_{i=1}^k \lambda(\gamma)_i$. (Such an integer exists since $\lambda(\alpha)$ is not dominated by $\lambda(\gamma)$.) Therefore $\sum_{i=1}^k \lambda(\alpha)_i - \sum_{i=1}^k \lambda(\beta)_i > \sum_{i=1}^k \lambda(\gamma)_i - \sum_{i=1}^k \lambda(\beta)_i$ and there are more entries in the longest $k$ rows of $\alpha/\beta$ then there are in the longest $k$ rows of $\gamma/\beta$. This implies that there are more than $\sum_{i=1}^k \lambda_i$ entries from $\alpha/\beta$ contained in the longest $k$ rows of $\alpha$, since there are $\sum_{i=1}^k \lambda_i$ entries in the longest $k$ rows of $\gamma/\beta$. This implies that in a Littlewood-Richardson composition tableau of shape $\alpha/\beta$, the longest $k$ rows must contain an entry less than $L-k+1$ where $L = l(\lambda)$.

The rightmost entry in the $i^{th}$ longest row of $\alpha/\beta$ must be $L-i+1$ for otherwise the filling would not satisfy the reverse lattice condition. This means that the longest $k$ rows of $\alpha$ must contain only entries greater than or equal to $L-i+1$, which contradicts the assertion that an entry less than $L-k+1$ appears among the $k$ longest rows of $\alpha$. Therefore there is no such Littlewood-Richardson composition tableau of shape $\alpha$ and so $C_{\lambda, \beta}^{\alpha} = 0$. $\square$
References

[1] M. Aguiar, N. Bergeron, and F. Sottile. Combinatorial Hopf algebras and generalized Dehn-Sommerville relations. *Compos. Math.*, 142(1):1-30, 2006.

[2] F. Bergeron. *Algebraic combinatorics and coinvariant spaces*. CMS Treatises in Mathematics. Canadian Mathematical Society, Ottawa, ON, 2009.

[3] F. Bergeron and C. Reutenauer. The coinvariant space for quasisymmetric polynomials. *Unpublished manuscript*.

[4] S. Fomin and A. N. Kirillov. Combinatorial $B_n$-analogues of Schubert polynomials. *Trans. Amer. Math. Soc.*, 348(9):3591-3620, 1996.

[5] A. M. Garsia. Combinatorial methods in the theory of Cohen-Macaulay rings. *Adv. in Math.*, 38(3):229-266, 1980.

[6] A. M. Garsia and N. Wallach. Qsym over Sym is free. *J. Combin. Theory Ser. A*, 104(2):217-263, 2003.

[7] I. M. Gessel. Multipartite P-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.

[8] J. Haglund, K. Luoto, S. K. Mason, and S. van Willigenburg. Quasisymmetric Schur functions. *J. Combin. Theory Ser. A. to appear*, arXiv:0810.2489.

[9] J. Haglund, K. Luoto, S. K. Mason, and S. van Willigenburg. Refinements of the Littlewood-Richardson rule. *Trans. Amer. Math. Soc. to appear*, arXiv:0908.3540.

[10] M. Hazewinkel. Symmetric functions, noncommutative symmetric functions, and quasisymmetric functions. *Acta Applicandae Mathematicae*, 75(1):55-83, 2003.

[11] R. Kane. *Reflection groups and invariant theory*. CMS Books in Mathematics/Ouvrages de Mathématiques de la SMC, 5. Springer-Verlag, New York, 2001.

[12] A. Lascoux and M.-P. Schützenberger. Polynômes de Schubert. *C. R. Acad. Sci. Paris Sér. I Math.*, 294(13):447-450, 1982.

[13] I. G. Macdonald. *Symmetric functions and Hall polynomials*. Oxford Mathematical Monographs. The Clarendon Press Oxford University Press, New York, second edition, 1995.

[14] C. Malvenuto and C. Reutenauer. Duality between quasi-symmetric functions and the Solomon descent algebra. *J. Algebra*, 177(3):967-982, 1995.

[15] L. Manivel. *Symmetric functions, Schubert polynomials and degeneracy loci*, volume 6 of SMF/AMS Texts and Monographs. American Mathematical Society, Providence, RI, 2001. Translated from the 1998 French original by John R. Swallow, Cours Spécialisés [Specialized Courses], 3.

[16] R. P. Stanley. *Enumerative combinatorics. Vol. 2*, volume 62 of Cambridge Studies in Advanced Mathematics. Cambridge University Press, Cambridge, 1999.