# The immaculate basis of the non-commutative symmetric functions (Extended Abstract)

Chris Berg<fnref n="2" />

Nantel Bergeron<fnref n="1" />,<fnref n="3" />

Franco Saliola<fnref n="2" />

Luis Serrano<fnref n="2" />

Mike Zabrocki<fnref n="1" />,<fnref n="3" />

**Abstract** We introduce a new basis of the non-commutative symmetric functions whose elements have Schur functions as their commutative images. Dually, we build a basis of the quasi-symmetric functions which expand positively in the fundamental quasi-symmetric functions and decompose Schur functions according to a signed combinatorial formula.

**Résumé.** Nous introduisons une nouvelle base des fonctions symétriques non commutatives dont les images commutatives sont des fonctions de Schur. Nous construisons la base duale des fonctions quasi-symétriques qui s'expriment de façon positive en fonction de la base fondamental et décomposer les fonctions de Schur.

**Keywords:** non-commutative symmetric functions, quasi-symmetric functions, tableaux, Schur functions

## 1 Introduction

The Schur functions $s_\lambda$ are indexed by integer partitions and form an additive basis for the algebra of symmetric functions Sym. Schur functions play an important role throughout mathematics, in particular in algebraic geometry (as representatives of Schubert classes for the Grassmannian) and representation theory (they are the characters of the irreducible representations of the general linear group). Another important basis for Sym is the (complete) homogeneous symmetric functions $h_\lambda$.

The algebras of non-commutative symmetric functions NSym and quasi-symmetric functions QSym are dual Hopf algebras. These algebras have been of great importance to algebraic combinatorics. As seen in [ABS], they are universal in the category of combinatorial Hopf algebras. They also represent the Grothendieck rings for the projective and finite dimensional representation theory of the 0-Hecke algebra [KT]. An important basis for NSym is formed by the (complete) homogeneous non-commutative symmetric functions $H_\alpha$, indexed by compositions. The forgetful map $\chi: NSym \to Sym$ maps the homogeneous non-commutative symmetric functions to their symmetric counterparts (see (1)).

The main goal of this abstract is to define and outline the properties of a new basis, the *immaculate basis* $\mathfrak{G}_\alpha$ of NSym, which emulates the role of the Schur functions. This new basis projects onto the

<footnote n="1">¹ Fields Institute, Toronto, ON, Canada</footnote>

<footnote n="2">²Laboratoire de combinatoire et d'informatique mathématique, Université du Québec à Montréal, Montréal, QC, Canada</footnote>

<footnote n="3">³ York University, Toronto, ON, Canada</footnote>
Schur basis under the forgetful map and it shares many of the same properties and constructions of the classical basis of Schur functions of Sym. More specifically:

**Bernstein operators.** One way to construct Schur functions is by iterating the Bernstein row adding operator, which acts on Schur functions by adding a row to the corresponding Ferrers shape. These operators can be described in an algebraic way, which we deform in order to obtain a non-commutative Bernstein operator. This deformed operator now acts on immaculate functions by adding a row to the corresponding composition. Thus, a repeated iteration of these operators will build the immaculate functions, as in Definition 3.3.

**Pieri rule.** The product of a Schur function and a homogeneous symmetric function corresponding to a partition with only one part can be expressed, via the classical Pieri rule, as a multiplicity-free sum over a specific set of Schur functions. More specifically, this sum is over all ways to add a *horizontal strip* to the original shape. In Theorem 3.5 we show that in a similar way, the product of an immaculate function and a homogeneous non-commutative symmetric function corresponding to a composition with only one part can be expressed as a multiplicity-free sum of immaculate functions. This sum is over all ways to add an analog of a horizontal strip for composition shapes.

**Immaculate tableaux and the immaculate Kostka matrix.** By iterating the Pieri rule, one can obtain an expansion of the homogeneous symmetric functions in terms of Schur functions, where each coefficient is a *Kostka number*, or number of semistandard Young tableaux of a specified shape and content. In a similar fashion, we introduce *immaculate tableaux*, and by iterating the immaculate Pieri rule, one obtains an expansion of the homogeneous non-commutative functions in terms of the immaculate functions, where each coefficient is the number of immaculate semistandard tableaux of a specified shape and content (Theorem 3.10).

**Positive expansion for ribbons.** Another important basis of NSym is formed by *ribbon noncommutative functions* $R_\alpha$. In Theorem 3.15 we expand the Ribbon functions positively in terms of immaculate functions, indexed by certain descent sets on standard immaculate tableaux.

Moreover, the immaculate basis gives rise to a dual basis in the quasi-symmetric function algebra. The *dual immaculate basis* also shares interesting properties with the Schur basis. In particular, by duality arguments, one is able to express the dual immaculate basis in terms of other known bases of QSym.

**Jacobi-Trudi determinant formula.** The Schur functions can be expanded in terms of the homogeneous symmetric functions by the use of the Jacobi-Trudi determinant. By considering a non-commutative version of this determinant, we expand the immaculate functions in terms of the homogeneous non-commutative symmetric functions, thus obtaining a lifting of the Jacobi-Trudi formula in NSym, as in Theorem 3.17.

**Generating series of immaculate tableaux and monomial expansion.** The most well known construction for a Schur function is by its expression as a generating series over the set of semistandard Young tableaux, and thus, as a positive sum of monomial (quasi-)symmetric functions. In Theorem 3.21 we express the dual immaculate functions as a generating series over the set of semistandard immaculate tableaux, and thus, as a positive sum of monomial quasi-symmetric functions.

**Positive fundamental expansion.** The Schur functions can also be expressed as a positive sum of fundamental quasi-symmetric functions, by considering descents on standard Young tableaux. By a duality argument, in Theorem 3.22, we express the dual immaculate functions as a positive sum of fundamental quasi-symmetric functions, by considering descents on standard immaculate tableaux.

**Expansion of Schur functions.** In Theorem 3.23, we show that the Schur functions expand in the dual immaculate basis via signed combinatorics developed in [ELW].
**Littlewood-Richardson rule.** In the classical case, the product of two Schur functions can be expressed as a sum of Schur functions, where each coefficient is a *Littlewood-Richardson number*, namely, the number of *Yamanouchi tableaux* of a certain skew shape. Although the product of any two immaculate functions is not in general immaculate positive, we give a combinatorial formula for the coefficients in the product of any immaculate function with an immaculate function corresponding to a partition as the positive sum of immaculate functions, where each coefficient counts the number of *immaculate Yamanouchi tableaux* of a certain skew shape, thus obtaining an analogue of the Littlewood-Richardson rule (Theorem 3.25).

**Murnaghan-Nakayama rule.** The product of a Schur function and a power sum can be expressed as a sum over Schur functions, over the set of shapes that are obtained by adding a ribbon to the original Ferrers shape. In NSym, an analogue of the power sums basis $\Psi_\alpha$, was defined in [GKLLRT]. In Theorem 3.27 we express the product of an immaculate function and a noncommutative power sum $\Psi_n$.

**Indecomposable modules.** There exists a collection of indecomposable modules for the 0-Hecke algebra with the property that the module indexed by the composition $\alpha$ has the dual immaculate function indexed by $\alpha$ as its characteristic. In the interest of space, we will not pursue this below, but refer the reader to [BBSSZ2].

This text is an extended abstract of the preprints [BBSSZ1], [BBSSZ2] and [BBSSZ3], where complete proofs can be found.

**Remark 1.1** *Although our basis of NSym is similar to the dual basis of quasi-symmetric Schur functions of [HLMvW] (whose properties were developed in [BLvW]), they are in fact different bases.*

## 1.1 Acknowledgments

This work is supported in part by CRC and NSERC. It is partially the result of a working session at the Algebraic Combinatorics Seminar at the Fields Institute with the active participation of C. Benedetti, Z. Chen, H. Heglin, and D. Mazur. In addition, the authors would like to thank F. Hivert, J. Huang, J. Remmel, N. Thiéry and M. Yip for lively discussions.

This research was facilitated by computer exploration using the open-source mathematical software *Sage* [sage] and its algebraic combinatorics features developed by the *Sage-Combinat* community [sage-combinat].

# 2 Background

## 2.1 Compositions and combinatorics

A *partition* of a non-negative integer $n$ is a sequence $\lambda = (\lambda_1, \lambda_2, \dots, \lambda_m)$ of non-negative integers satisfying $\lambda_1 \ge \lambda_2 \ge \dots \ge \lambda_m$, and is denoted $\lambda \vdash n$. Partitions are of particular importance to algebraic combinatorics; among other things, partitions of $n$ index a basis for the symmetric functions of degree $n$, $\text{Sym}_n$, and the character ring for the representations of the symmetric group. These concepts are intimately connected; we assume the reader is well versed in this area (see for instance [Sagan] for background details).

A *composition* of a non-negative integer $n$ is a list $\alpha = [\alpha_1, \alpha_2, \dots, \alpha_m]$ of positive integers which sum to $n$, written $\alpha = n$. The entries $\alpha_i$ of the composition are referred to as the parts of the composition. The size of the composition is the sum of the parts and will be denoted $|\alpha| := n$. The length of the composition
is the number of parts and will be denoted $\ell(\alpha) := m$. In this paper we study dual graded Hopf algebras whose bases at level $n$ are indexed by compositions of $n$.

Compositions of $n$ correspond to subsets of $\{1, 2, \dots, n-1\}$. We will follow the convention of identifying $\alpha = [\alpha_1, \alpha_2, \dots, \alpha_m]$ with the subset $D(\alpha) = \{\alpha_1, \alpha_1+\alpha_2, \alpha_1+\alpha_2+\alpha_3, \dots, \alpha_1+\alpha_2+\dots+\alpha_{m-1}\}$.

If $\alpha$ and $\beta$ are both compositions of $n$, say that $\alpha \le \beta$ in refinement order if $D(\beta) \subseteq D(\alpha)$. For instance, $[1, 1, 2, 1, 3, 2, 1, 4, 2] \le [4, 4, 2, 7]$, since $D([1, 1, 2, 1, 3, 2, 1, 4, 2]) = \{1, 2, 4, 5, 8, 10, 11, 15\}$ and $D([4, 4, 2, 7]) = \{4, 8, 10\}$.

We introduce a new notion which will arise in our Pieri rule (Theorem 3.5); we say that $\alpha \subset_i \beta$ if:

1. $|\beta| = |\alpha| + i,$

2. $\alpha_j \le \beta_j$ for all $1 \le j \le \ell(\alpha),$

3. $\ell(\beta) \le \ell(\alpha) + 1.$

For a composition $\alpha = [\alpha_1, \alpha_2, \dots, \alpha_\ell]$ and a positive integer $m$, we let $[m, \alpha]$ denote the composition $[m, \alpha_1, \alpha_2, \dots, \alpha_\ell]$.

## 2.2 Schur functions and creation operators

We let $h_i$ and $e_i$ denote the complete homogeneous and elementary symmetric functions of degree $i$ respectively. We next define a Schur function indexed by an arbitrary sequence of integers. The resulting family of symmetric functions indexed by partitions $\lambda$ are the usual Schur basis of the symmetric functions.

**Definition 2.1** For an arbitrary integer tuple $\alpha = (\alpha_1, \alpha_2, \dots, \alpha_\ell) \in \mathbb{Z}^\ell$, we define

$$s_\alpha := \det \begin{bmatrix} h_{\alpha_1} & h_{\alpha_1+1} & \cdots & h_{\alpha_1+\ell-1} \\ h_{\alpha_2-1} & h_{\alpha_2} & \cdots & h_{\alpha_2+\ell-2} \\ \vdots & \vdots & \ddots & \vdots \\ h_{\alpha_\ell-\ell+1} & h_{\alpha_\ell-\ell+2} & \cdots & h_{\alpha_\ell} \end{bmatrix} = \det |h_{\alpha_i+j-i}|_{1\le i,j\le \ell}$$

where we use the convention that $h_0 = 1$ and $h_{-m} = 0$ for $m > 0$.

With this definition, switching two adjacent rows of the defining matrix has the effect of changing the sign of the determinant. It is also equal to the Schur function indexed by a different integer tuple:

$$s_{\alpha_1, \alpha_2, \dots, \alpha_r, \alpha_{r+1}, \dots, \alpha_\ell} = -s_{\alpha_1, \alpha_2, \dots, \alpha_{r+1}-1, \alpha_r+1, \dots, \alpha_\ell}.$$

**Proposition 2.2** If $\alpha$ is a composition of $n$ with length equal to $k$, then $s_\alpha = 0$ if and only if there exists $i, j \in \{1, 2, \dots, k\}$ with $i \ne j$ such that $\alpha_i - i = \alpha_j - j$. If $s_\alpha \ne 0$, then there is a unique permutation $\sigma$ such that $(\alpha_{\sigma_1} + 1 - \sigma_1, \alpha_{\sigma_2} + 2 - \sigma_2, \dots, \alpha_{\sigma_k} + k - \sigma_k)$ is a partition. In this case,

$$s_{\alpha} = (-1)^{\sigma} s_{\alpha_{\sigma_1}+1-\sigma_1, \alpha_{\sigma_2}+2-\sigma_2, \dots, \alpha_{\sigma_k}+k-\sigma_k}.$$
Sym is a self dual Hopf algebra. It has a pairing (the Hall scalar product) defined by

$$ \langle h_{\lambda}, m_{\mu} \rangle = \langle s_{\lambda}, s_{\mu} \rangle = \delta_{\lambda,\mu}. $$

An element $f \in \text{Sym}$ gives rise to an operator $f^{\perp} : \text{Sym} \to \text{Sym}$ according to the relation:

$$ \langle fg, h \rangle = \langle g, f^{\perp}h \rangle \quad \text{for all } g, h \in \text{Sym}. $$

We define a “creation” operator $\mathbf{B}_m : \text{Sym}_n \to \text{Sym}_{m+n}$ by:

$$ \mathbf{B}_m := \sum_{i \ge 0} (-1)^i h_{m+i} e_i^{\perp}. $$

The following theorem, which states that creation operators construct Schur functions, will become one of the motivations for our new basis of NSym (see Definition 3.3).

**Theorem 2.3 (Bernstein [Ze, pg 69-70])** For all sequences of $\alpha \in \mathbb{Z}^m$,

$$ s_{\alpha} = \mathbf{B}_{\alpha_1} \mathbf{B}_{\alpha_2} \cdots \mathbf{B}_{\alpha_m} (1). $$

## 2.3 Non-commutative symmetric functions

The algebra NSym is a non-commutative analogue of Sym that arises by considering an algebra with one non-commutative generator at each positive degree. In addition to the relationship with the symmetric functions, this algebra has links to Solomon's descent algebra in type A [MR], the algebra of quasi-symmetric functions [MR], and representation theory of the type A Hecke algebra at $q = 0$ [KT], and connections to the theory of combinatorial Hopf algebras [ABS]. While we will follow the foundational results and definitions of references such as [GKLLRT, MR], we have chosen to use notation here which is suggestive of analogous results in Sym.

We define NSym as the algebra with generators $\{H_1, H_2, \dots\}$ and no relations. Each generator $H_i$ is defined to be of degree $i$, giving NSym the structure of a graded algebra. We let NSym$_n$ denote the graded component of NSym of degree $n$. A basis for NSym$_n$ are the complete homogeneous functions $\{H_{\alpha} := H_{\alpha_1} H_{\alpha_2} \cdots H_{\alpha_m}\}_{\alpha \vdash n}$ indexed by compositions of $n$. To make this convention consistent, some formulas will use expressions that have $H$ indexed by tuples of integers and we use the convention that $H_0 = 1$ and $H_{-r} = 0$ for $r > 0$.

There exists a map (sometimes referred to as the forgetful map) which we shall also denote $\chi : \text{NSym} \to \text{Sym}$ defined by sending the basis element $H_{\alpha}$ to the complete homogeneous symmetric function

$$ \chi(H_{\alpha}) := h_{\alpha_1} h_{\alpha_2} \cdots h_{\alpha_{\ell(\alpha)}} \in \text{Sym} \quad (1) $$

and extend this map to all of NSym linearly.

Similar to the study of Sym and the ring of characters for the symmetric groups, the ring of non-commutative symmetric functions of degree $n$ is isomorphic to the Grothendieck ring of projective representations of the 0-Hecke algebra. We refer the reader to [KT] for details. The element of NSym which corresponds to the projective representation indexed by $\alpha$ is here denoted $R_{\alpha}$. The collection of $R_{\alpha}$ are a basis of NSym, usually called the *ribbon basis* of NSym. They are defined through their expansion in the complete homogeneous basis:

$$ R_{\alpha} = \sum_{\beta \ge \alpha} (-1)^{\ell(\alpha) - \ell(\beta)} H_{\beta}, \quad \text{or equivalently, } H_{\alpha} = \sum_{\beta \ge \alpha} R_{\beta}. $$

NSym has a coproduct structure, which we will not explain in the interest of space.
## 2.4 Quasi-symmetric functions

The algebra of quasi-symmetric functions, QSym, was introduced in [Ges] (see also subsequent references such as [GR, Sta84]) and this algebra has become a useful tool for algebraic combinatorics since it is dual to NSym as a Hopf algebra and contains Sym as a subalgebra.

As with the algebra NSym, the graded component QSym$_n$ is indexed by compositions of $n$. The algebra is most readily realized within the ring of power series of bounded degree $Q[x_1, x_2, \dots]$, and the monomial quasi-symmetric function indexed by a composition $\alpha$ is defined as

$$M_{\alpha} = \sum_{i_1 < i_2 < \dots < i_m} x_{i_1}^{\alpha_1} x_{i_2}^{\alpha_2} \cdots x_{i_m}^{\alpha_m} \qquad (2)$$

QSym is defined as the algebra with the monomial quasi-symmetric functions as a basis.

We view Sym as a subalgebra of QSym. In fact, the quasi-symmetric monomial functions decompose the usual monomial symmetric functions $m_{\lambda} \in \text{Sym}$:

$$m_{\lambda} = \sum_{\text{sort}(\alpha)=\lambda} M_{\alpha}.$$

Similar to NSym, the algebra QSym is isomorphic to the Grothendieck ring of finite-dimensional representations of the 0-Hecke algebra. The irreducible representations of the 0-Hecke algebra form a basis for this ring, and under this isomorphism the irreducible representation indexed by $\alpha$ is identified with an element of QSym, the fundamental quasi-symmetric function, denoted $F_{\alpha}$. The $F_{\alpha}$, for $\alpha \models n$, form a basis of QSym$_n$, and are defined by their expansion in the monomial quasi-symmetric basis:

$$F_{\alpha} = \sum_{\beta \le \alpha} M_{\beta}.$$

## 2.5 Identities relating non-commutative / quasi-symmetric functions

The algebras QSym and NSym form graded dual Hopf algebras. The monomial basis of QSym is dual in this context to the complete homogeneous basis of NSym, and the fundamental basis of QSym is dual to the ribbon basis of NSym. NSym and QSym have a pairing $\langle \cdot, \cdot \rangle : \text{NSym} \times \text{QSym} \to \mathbb{Q}$, defined under this duality as either $\langle H_{\alpha}, M_{\beta} \rangle = \delta_{\alpha, \beta}$, or $\langle R_{\alpha}, F_{\beta} \rangle = \delta_{\alpha, \beta}$.

We will generalize the operation which is dual to multiplication by a quasi-symmetric function using this pairing. For $F, G \in \text{QSym}$, let $F^{\perp}$ be the operator which acts on elements $H \in \text{NSym}$ according to the relation $\langle H, FG \rangle = \langle F^{\perp}H, G \rangle$.

# 3 A new basis for NSym

We are now ready to introduce our new basis of NSym. These functions were discovered while playing with a non-commutative analogue of the Jacobi-Trudi identity (see Theorem 3.17). They may also be defined as the unique functions in NSym which satisfy a right-Pieri rule (see Theorem 3.5).

## 3.1 Non-commutative immaculate functions

**Definition 3.1** We define the non-commutative Bernstein operators $\mathbb{B}_m$ as:

$$\mathbb{B}_m = \sum_{i \ge 0} (-1)^i H_{m+i} F_{1^i}.$$
Using the non-commutative Bernstein operators, we can inductively build functions using creation operators similar to Bernstein's formula (Theorem 2.3) for the Schur functions.

**Remark 3.2** Under the identification of Sym inside QSym, the generator $e_i$ of Sym is precisely the function $F_{1^i}$ appearing above.

**Definition 3.3** For any $\alpha = (\alpha_1, \alpha_2, \dots, \alpha_m) \in \mathbb{Z}^m$, the immaculate function $\mathfrak{S}_\alpha \in \text{NSym}$ is defined as the composition of the operators

$$ \mathfrak{S}_{\alpha} = \mathbb{B}_{\alpha_1} \mathbb{B}_{\alpha_2} \cdots \mathbb{B}_{\alpha_m} (1). $$

Calculations in the next subsection will show that the elements $\{\mathfrak{S}_\alpha\}_{\alpha|=n}$ form a basis for $\text{NSym}_n$.

**Example 3.4** For $a, b > 0$, $\alpha = (a)$ has only one part, and $\mathfrak{S}_a$ is just the complete homogeneous generator $H_a$. If $\alpha = (a, b)$ consists of two parts, then $\mathfrak{S}_{ab} = \mathbb{B}_a(H_b) = H_a H_b - H_{a+1} H_{b-1}$.

## 3.2 The right-Pieri rule for the immaculate basis

**Theorem 3.5** For a composition $\alpha$, the $\mathfrak{S}_\alpha$ satisfy a multiplicity free right-Pieri rule for multiplication by $H_s$:

$$ \mathfrak{S}_{\alpha} H_s = \sum_{\alpha \subseteq \beta} \mathfrak{S}_{\beta}. $$

where the notation $\subseteq$ is introduced in Section 2.1.

**Remark 3.6** Products of the form $H_m \mathfrak{S}_\alpha$ do not have as nice an expression as $\mathfrak{S}_\alpha H_m$ because they generally have negative signs in their expansion and there is no obvious containment of resulting compositions. For example,

$$ H_1 \mathfrak{S}_{13} = \mathfrak{S}_{113} - \mathfrak{S}_{221} - \mathfrak{S}_{32}. $$

**Example 3.7** The expansion of $\mathfrak{S}_{23}$ multiplied on the right by $H_3$ is done below.

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

## 3.3 Relationship to the classical bases of NSym

We will now develop some relations between the classical bases of NSym and the immaculate basis.
### 3.3.1 Immaculate tableaux

**Definition 3.8** Let $\alpha$ and $\beta$ be compositions. An immaculate tableau of shape $\alpha$ and content $\beta$ is a labelling of the boxes of the diagram of $\alpha$ by positive integers in such a way that:

1. the number of boxes labelled by $i$ is $\beta_i$;

2. the sequence of entries in each row, from left to right, is weakly increasing;

3. the sequence of entries in the first column, from top to bottom, is strictly increasing.

An immaculate tableau is said to be standard if it has content $1^{|\alpha|}$.

Let $K_{\alpha,\beta}$ denote the number of immaculate tableaux of shape $\alpha$ and content $\beta$.

We re-iterate that besides the first column, there is no relation on other columns of an immaculate tableau. Standard immaculate tableaux of size $n$ are in bijection with set partitions of $\{1, 2, \dots, n\}$ by ordering the parts in the partition by minimal elements, as was pointed out to us in a discussion with M. Yip.

**Example 3.9** There are five immaculate tableau of shape $[4, 2, 3]$ and content $[3, 1, 2, 3]$:

<table><tr><td>1</td><td>1</td><td>1</td><td>3</td></tr><tr><td>2</td><td>3</td><td></td><td></td></tr><tr><td>4</td><td>4</td><td>4</td><td></td></tr></table>

<table><tr><td>1</td><td>1</td><td>1</td><td>3</td></tr><tr><td>2</td><td>4</td><td></td><td></td></tr><tr><td>3</td><td>4</td><td>4</td><td></td></tr></table>

<table><tr><td>1</td><td>1</td><td>1</td><td>4</td></tr><tr><td>2</td><td>3</td><td></td><td></td></tr><tr><td>3</td><td>4</td><td>4</td><td></td></tr></table>

<table><tr><td>1</td><td>1</td><td>1</td><td>4</td></tr><tr><td>2</td><td>4</td><td></td><td></td></tr><tr><td>3</td><td>3</td><td>4</td><td></td></tr></table>

<table><tr><td>1</td><td>1</td><td>1</td><td>2</td></tr><tr><td>3</td><td>3</td><td></td><td></td></tr><tr><td>4</td><td>4</td><td>4</td><td></td></tr></table>

### 3.3.2 Expansion of the homogeneous basis

**Theorem 3.10** The complete homogeneous basis $H_\alpha$ has a positive, uni-triangular expansion in the immaculate basis. Specifically,

$$H_{\beta} = \sum_{\alpha \ge \text{lex} \beta} K_{\alpha, \beta} \mathfrak{G}_{\alpha},$$

where $K_{\alpha,\beta}$ is the number of immaculate tableaux of shape $\alpha$ and content $\beta$.

**Example 3.11** Continuing from Example 3.9, we see that $H_{3123} = \dots + 5\mathfrak{G}_{423} + \dots$.

**Corollary 3.12** The $\{\mathfrak{G}_\alpha : \alpha \vdash n\}$ form a basis of $NSym_n$.

### 3.3.3 Expansion of the ribbon basis

We will expand the ribbon functions in the immaculate basis. We first need the notion of a descent.

**Definition 3.13** We say that a standard immaculate tableau $T$ has a descent in position $i$ if $(i+1)$ is in a row strictly lower than $i$. The descent composition of $T$, $D(T)$, is the composition of the size of $T$ that corresponds to the subset containing all descent positions.

**Example 3.14** The standard immaculate tableau below has descents in positions $\{2, 5, 11\}$. The descent composition of $S$ is then $[2, 3, 6, 7]$.

$$S = \left( \begin{array}{c|cccc|c} 1 & 2 & 4 & 5 & 10 & 11 \\ \hline 3 & 6 & 7 & 8 & 9 & \\ \hline 12 & 13 & 14 & 15 & 16 & 17 & 18 \end{array} \right)$$
Let $L_{\alpha,\beta}$ denote the number of standard immaculate tableaux of shape $\alpha$ and descent composition $\beta$.

**Theorem 3.15** The ribbon function $R_{\beta}$ has a positive expansion in the immaculate basis. Specifically

$$R_{\beta} = \sum_{\alpha \ge \ell \beta} L_{\alpha, \beta} \mathfrak{S}_{\alpha}.$$

**Example 3.16** There are eight standard immaculate tableaux with descent composition $[2, 2, 2]$, giving the expansion of $R_{222}$ into the immaculate basis.

$$R_{222} = \mathfrak{S}_{222} + \mathfrak{S}_{231} + \mathfrak{S}_{312} + 2\mathfrak{S}_{321} + \mathfrak{S}_{33} + \mathfrak{S}_{411} + \mathfrak{S}_{42}$$

## 3.4 Jacobi-Trudi rule for NSym

Another compelling reason to study the immaculate functions is that they also have an expansion in the $H_{\alpha}$ basis that makes them a clear analogue of the Jacobi-Trudi rule of Definition 2.1.

**Theorem 3.17** For a composition $\alpha = [\alpha_1, \alpha_2, \dots, \alpha_m]$:

$$\mathfrak{S}_{\alpha} = \sum_{\sigma \in S_m} (-1)^{\sigma} H_{\alpha_1 + \sigma_1 - 1, \alpha_2 + \sigma_2 - 2, \dots, \alpha_m + \sigma_m - m}. \qquad (3)$$

**Remark 3.18** This sum is a non-commutative analogue of the determinant of the following matrix:

$$\begin{bmatrix}
H_{\alpha_1} & H_{\alpha_1+1} & \cdots & H_{\alpha_1+\ell-1} \\
H_{\alpha_2-1} & H_{\alpha_2} & \cdots & H_{\alpha_2+\ell-2} \\
\vdots & \vdots & \ddots & \vdots \\
H_{\alpha_{\ell-\ell+1}} & H_{\alpha_{\ell-\ell+2}} & \cdots & H_{\alpha_{\ell}}
\end{bmatrix}$$

where we have used the convention that $H_0 = 1$ and $H_{-m} = 0$ for $m > 0$. The non-commutative analogue of the determinant corresponds to expanding this matrix about the first row and multiplying those elements on the left.

**Remark 3.19** One might ask why one would naturally expand about the first row rather than, say, the first column or the last row. What we considered to be the natural analogue of expanding about the first column however is not a basis; the matrix corresponding to $\alpha = (1, 2)$ would be 0 under this analogue.

Of course, the original reason for considering this definition is the property that they are a lift of the symmetric function corresponding to the Jacobi-Trudi matrix.

**Corollary 3.20** $\chi(\mathfrak{S}_{\alpha}) = s_{\alpha}$.
## 3.5 The dual immaculate basis

Every basis $X_\alpha$ of $NSym_n$ gives rise to a basis $Y_\beta$ of $QSym_n$ defined by duality; $Y_\beta$ is the unique basis satisfying $\langle X_\alpha, Y_\beta \rangle = \delta_{\alpha,\beta}$. The dual basis to the immaculate basis of $NSym$, denoted $\mathfrak{S}_\alpha^*$, have positive expansions in the monomial and fundamental bases of $QSym$. Furthermore, they decompose the usual Schur functions of $Sym$ (see Theorem 3.23).

**Theorem 3.21** The dual immaculate functions $\mathfrak{S}_\alpha^*$ are monomial positive. Specifically they expand as

$$ \mathfrak{S}_\alpha^* = \sum_{\beta \le \ell \alpha} K_{\alpha, \beta} M_\beta. $$

**Theorem 3.22** The dual immaculate functions $\mathfrak{S}_\alpha^*$ are fundamental positive. Specifically they expand as

$$ \mathfrak{S}_\alpha^* = \sum_{\beta \le \ell \alpha} L_{\alpha, \beta} F_\beta. $$

Duality will also yield an explicit expansion of Schur functions into the dual immaculate basis.

**Theorem 3.23** The Schur function $s_\lambda$, with $\ell(\lambda) = k$ expands into the dual immaculate basis as follows:

$$ s_\lambda = \sum_{\sigma \in S_k} (-1)^\sigma \mathfrak{S}_{\lambda_{\sigma_1} + 1 - \sigma_1, \lambda_{\sigma_2} + 2 - \sigma_2, \dots, \lambda_{\sigma_k} + k - \sigma_k}^* $$

where the sum is over permutations $\sigma$ such that $\lambda_{\sigma_i} + i - \sigma_i > 0$ for all $i \in \{1, 2, \dots, k\}$.

**Example 3.24** Let $\lambda = (2, 2, 2, 1)$. Then $s_\lambda$ decomposes as:

$$ s_{2221} = \mathfrak{S}_{2221}^* - \mathfrak{S}_{1321}^* - \mathfrak{S}_{2131}^* + \mathfrak{S}_{1141}^*, $$

since only the permutations $\sigma \in \{1234, 2134, 1324, 2314\}$ contribute to the sum in the expansion of $s_{2221}$. There are potentially 24 terms in this sum, but for the partition $(2, 2, 2, 1)$ it is easy to reason that $\sigma_4 = 4$ and $\sigma_1 < 3$.

These combinatorics arise in the paper of Egge, Loehr and Warrington [ELW] when they describe how to obtain a Schur expansion given a quasi-symmetric fundamental expansion. In their language, the terms in this sum correspond to “special rim hook tableau”.

## 3.6 The Littlewood-Richardson rule for immaculate functions

We prove here that the product $\mathfrak{S}_\alpha \mathfrak{S}_\lambda$ expands positively in the immaculate basis, expanding the notion of a Yamanouchi tableau. Recall that a Yamanouchi word is a word $w$ such that every left prefix of $w$ contains at least as many occurrences of $i$ as $i + 1$, for all $i \ge 1$. The content of $w$ is the composition whose $i$-th part is the number of occurrences of $i$.

For partitions $\alpha$ and $\beta$ with $\alpha_i \ge \beta_i$ for all $i$, denote a skew composition shape $\alpha//\beta$ by the shape one obtains by superimposing the bottom left boxes of $\alpha$ and $\beta$, and removing the boxes in $\beta$. We denote an immaculate skew tableau of shape $\alpha//\beta$ as a filling of this shape, satisfying the rules in Definition 3.8. We denote the reading word of a skew immaculate tableau $T$ as the word obtained by reading its entries from right to left in each row, starting from the top row and moving down.
**Theorem 3.25** For a composition $\alpha$ and a partition $\lambda$, the coefficients $c_{\alpha, \lambda}^{\beta}$ appearing in

$$ \mathfrak{S}_{\alpha} \mathfrak{S}_{\lambda} = \sum_{\beta} c_{\alpha, \lambda}^{\beta} \mathfrak{S}_{\beta}, $$

are non-negative integers. In particular, $c_{\alpha, \lambda}^{\beta}$ is the number of skew immaculate tableaux of shape $\alpha//\beta$, such that the reading word is a Yamanouchi word of content $\lambda$.

**Example 3.26** We give an example with $\alpha = [1, 2]$ and $\lambda = [2, 1]$.

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

## 3.7 The Murnaghan-Nakayama rule for immaculate functions

A non-commutative lifting $\Psi_{\alpha}$ of the power sum basis elements was given in [GKLLRT]. We now state our version of the Murnaghan-Nakayama rule for immaculate functions.

**Theorem 3.27** For a composition $\alpha$ and a positive integer $k$,

$$ \mathfrak{S}_{\alpha} \Psi_k = \sum_{j=1}^{\ell(\alpha)} \mathfrak{S}_{[\alpha_1, \alpha_2, \dots, \alpha_j + k, \dots, \alpha_{\ell(\alpha)}]} + \sum_{j=0}^{k-1} \mathfrak{S}_{[\alpha, 0, \dots, 0, k]} $$

In other words, the sum is over all ways to add $k$ to one of the parts of the composition obtained by padding $\alpha$ with $k$ zeroes at the end.

**Example 3.28** One may check that

$$ \mathfrak{S}_{132} \Psi_3 = \mathfrak{S}_{432} + \mathfrak{S}_{162} + \mathfrak{S}_{135} + \mathfrak{S}_{1323} + \mathfrak{S}_{13203} + \mathfrak{S}_{132003}. $$

**Remark 3.29** The nicest form of the Murnaghan-Nakayama rule involves weak compositions (possibly allowing zero as an entry) rather than compositions. There is a signed version of the rule which uses only compositions. In the interest of space, we must omit this rule. It will appear in [BBSSZ3].

## References

[ABS] M. Aguiar, N. Bergeron, and F. Sottile, *Combinatorial Hopf Algebras and generalized Dehn–Sommerville relations*, Compositio Math., 142 (2006) 1–30.
[BBSSZ1] C. Berg, N. Bergeron, F. Saliola, L. Serrano, and M. Zabrocki, *A lift of the Schur and Hall-Littlewood bases to non-commutative symmetric functions*, arXiv:1208.5191, to appear, Canadian Journal of Mathematics, doi:10.4153/CJM-2013-013-0.

[BBSSZ2] C. Berg, N. Bergeron, F. Saliola, L. Serrano, and M. Zabrocki, *Indecomposable modules for the dual immaculate basis of quasi-symmetric functions*, arXiv:1304.1224.

[BBSSZ3] C. Berg, N. Bergeron, F. Saliola, L. Serrano, and M. Zabrocki, *Multiplicative structures of the immaculate basis of non-commutative symmetric functions*, in preparation.

[BLvW] C. Bessenrodt, K. Luoto, and S. van Willigenburg, *Skew quasi-symmetric Schur functions and non-commutative Schur functions*, Adv. Math., 226-5 (2011) 4492-4532.

[ELW] E. Egge, N. Loehr, G. Warrington, *From quasi-symmetric expansions to Schur expansions via a modified inverse Kostka matrix*, European J. Combin., 31-8 (2010) 2014-2027.

[Ges] I. 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.

[GKLLRT] I. Gelfand, D. Krob, A. Lascoux, B. Leclerc, V. Retakh, and J.-Y. Thibon, *Noncommutative symmetric functions*, Adv. Math., 112-2 (1995) 218-348.

[GR] I. Gessel and C. Reutenauer, *Counting permutations with given cycle structure and descent set*, J. Combin. Theory Ser. A, 64-2 (1993) 189-215.

[HLMvW] J. Haglund, K. Luoto, S. Mason, and S. van Willigenburg, *Quasi-symmetric Schur functions*, J. Combin. Theory Ser. A, 118-2 (2011) 463-490.

[KT] D. Krob, J.-Y. Thibon, *non-commutative symmetric functions IV: Quantum linear groups and Hecke algebras at $q=0$*, J. of Algebraic Combinatorics 6 (1997) 339-376.

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

[Sagan] B. Sagan, *The Symmetric Group: Representations, Combinatorial Algorithms, and Symmetric Functions*, 2nd edition, Springer-Verlag, New York, 2001.

[sage] W. A. Stein et al. *Sage Mathematics Software (Version 4.3.3)*, The Sage Development Team, 2010, http://www.sagemath.org.

[sage-combinat] The Sage-Combinat community. *Sage-Combinat: enhancing Sage as a toolbox for computer exploration in algebraic combinatorics*, http://combinat.sagemath.org, 2008.

[Sta84] R. Stanley, *On the number of reduced decompositions of elements of Coxeter groups*, European J. Combin., 5-4 (1984) 359-372.

[Ze] A. V. Zelevinsky, *Representations of finite classical groups: a Hopf algebra approach*, Springer Lecture Notes, **869**.