Fomin-Greene Monoids and Pieri Operations

Abstract

We explore monoids generated by operators on certain infinite partial orders. Our starting point is the work of Fomin and Greene on monoids satisfying the relations $(\mathbf{u}_{r} + \mathbf{u}_{r+1})\mathbf{u}_{r+1}\mathbf{u}_{r} = \mathbf{u}_{r+1}\mathbf{u}_{r}(\mathbf{u}_{r} + \mathbf{u}_{r+1})$ and $\mathbf{u}_{r}\mathbf{u}_{t} = \mathbf{u}_{t}\mathbf{u}_{r}$ if | r − t | > 1. Given such a monoid, the non-commutative functions in the variables u are shown to commute. Symmetric functions in these operators often encode interesting structure constants. Our aim is to introduce similar results for more general monoids not satisfying the relations of Fomin and Greene. This paper is an extension of a talk by the second author at the workshop on algebraic monoids, group embeddings and algebraic combinatorics at The Fields Institute in 2012.

1 Introduction

In their work on the plactic monoid, Lascoux and Schützenberger [22] constructed the Schur functions in terms of noncommutative variables satisfying only Knuth relations. It was subsequently discovered that symmetric functions can be constructed using different monoid algebras, for example the nil-plactic monoid, the nil-coxeter monoid or the H _n (0) algebra. A uniform understanding of these constructions can be found in the seminal work of Fomin and Greene [15].

One of the main advantages of the work of Fomin and Green is that it shows the Schur positivity of certain generating functions defined on those monoid algebras. This is a central problem in algebraic combinatorics and we still have several open problems of this kind. The theory in [15] works very well for the problems it is set to solve, but it also has its limitations.

Here we want to show that this quest of understanding symmetric functions inside a monoid algebra is very alive and new results are still underway and needed. In this presentation, very close to the approach of Fomin and Greene, we look at monoids generated by operators acting on an infinite poset. We show that a certain space of functions on the monoid algebra of operators is isomorphic to symmetric functions (or a subspace of symmetric functions). These subspaces are obtained via Pieri operators as defined in [10]. The posets we consider are very often produced from a combinatorial Hopf algebra as defined in [1, 11]. Unlike the theory in [15], we are not guaranteed to have Schur positivity. Even when the object in question is Schur positive the rule of Fomin and Greene is not applicable. One has to develop new techniques to deal with this. It has been done in some cases, but it is still open in others.

We keep this paper as a talk, like a story. We introduce the results as they come from the examples. In the first part, Sect. 2, we look at a classical example. Next, in Sect. 3, we look at less known examples and constructions which are unrelated to [15]. We then look at what can be done in the future in Sect. 4.

2 A Classical Example

2.1 Operators on the Young Lattice

We start by a classical construction of Schur functions inspired by [14]. A partition of an integer n is a sequence of integers $\lambda = (\lambda _{1},\lambda _{2},\ldots,\lambda _{\ell})$ such that $n =\lambda _{1} +\lambda _{2} + \cdots +\lambda _{\ell}$ and $\lambda _{1} \geq \lambda _{2} \geq \cdots \geq \lambda _{\ell} > 0$. When λ is a partition of n we denote it by $\lambda \vdash n$, the number of parts of λ will be denoted by $\ell(\lambda ) =\ell$ and its size by | λ |  = n. The diagram of a partition λ, denoted λ as well, is the subset of $\mathbb{Z} \times \mathbb{Z}$ given by $\lambda =\big\{ (i,j): 1 \leq j \leq \ell,\ 1 \leq i \leq \lambda _{j}\big\}$. We draw this by putting a unit box with coordinates (i, j) in the bottom left corner. For example the partition λ = (4, 2, 1) is depicted by

The Young lattice $\mathcal{Y}$ consists of all partitions $\lambda \vdash n \geq 0$, ordered by inclusion of diagrams. The empty partition is the unique partition for n = 0. An inclusion $\mu \subset \lambda$ is a cover if and only if $\mu \cup \{(i,j)\} =\lambda$ for a unique cell (i, j). We will label such a cover by an edge labeled by c _i, j  = j − i:

$$\displaystyle{\mu \ \stackrel{c_{i,j}}{\longrightarrow }\ \lambda }$$

We can draw the lower part of this poset as

Consider the free $\mathbb{Z}$-module $\mathbb{Z}\mathcal{Y}$ spanned by all partitions of n ≥ 0. We define linear operators u _r for each $r \in \mathbb{Z}$ as follows

$$\displaystyle{ \begin{array}{rcl} \mathbf{u}_{r}: \ \mathbb{Z}\mathcal{Y}&\longrightarrow &\quad \mathbb{Z}\mathcal{Y}, \\ \mu \quad &\longmapsto &\ \ \left \{\begin{array}{ll} \lambda &\mbox{ if }\mu \ \stackrel{r}{\longrightarrow }\ \lambda \mbox{ in }\mathcal{Y} \\ 0&\mbox{ otherwise.} \end{array} \right. \end{array} }$$

(1)

For example

We are interested in the monoid $\mathcal{M}\langle \mathbf{u}_{r}\rangle$ generated by the operators u _r for $r \in \mathbb{Z}$ and the zero operator 0. By the nature of these operators, it is not very hard to see that they satisfy the following relations:

$$\displaystyle{ \begin{array}{rcrclcll} (1)&& \mathbf{u}_{r}^{2} & =&\mathbf{0} && \\ (2)&&\mathbf{u}_{r}\mathbf{u}_{r+1}\mathbf{u}_{r} = \mathbf{u}_{r+1}\mathbf{u}_{r}\mathbf{u}_{r+1} & =&\mathbf{0} && \\ (3)&& \mathbf{u}_{r}\mathbf{u}_{t}& =&\mathbf{u}_{t}\mathbf{u}_{r}&&\mbox{ if $\vert r - t\vert > 1$}.\\ \end{array} }$$

(2)

These relations can be understood graphically. The first relation states that once we add a cell in a given diagonal, if we try to add a second cell in the same diagonal we will not get a partition:

. The second relation states that if we add two consecutive cells in a row (or column) and if we try to add a third cell in the same diagonal as the first added cell we will not get a partition:

The third relation states that we can add two cells independently in diagonals that are far from each other:

Proposition 1.

$\mathcal{M}\langle \mathbf{u}_{r}\rangle$ is the monoid freely generated by the $\mathbf{u}_{r}$ for $r \in \mathbb{Z}$ and 0 modulo the relations  (2) .

This is a consequence of a more general theorem and it can be shown using some very well known facts about the symmetric group and the combinatorics of partitions. However to our knowledge this statement is not mentioned as such in the literature. To see that the relations (2) generate all the relations of the monoid $\mathcal{M}\langle \mathbf{u}_{r}\rangle$ requires a deeper understanding of the relations. We will sketch a proof here. Recall that the symmetric group is generated by simple reflections s _r satisfying the braid relations:

$$\displaystyle{ \begin{array}{rcrclcll} (1)&& s_{r}^{2} & =&Id && \\ (2)&&s_{r}s_{r+1}s_{r}& =&s_{r+1}s_{r}s_{r+1} & & \\ (3)&& s_{r}s_{t}& =&s_{t}s_{r} &&\mbox{ if $\vert r - t\vert > 1$}.\\ \end{array} }$$

(3)

For a permutation w, the length ℓ(w) is the minimal number of generators s _r necessary to express w as a product of generators. If $w = s_{i_{1}}s_{i_{2}}\cdots s_{\ell(w)}$, then we say that the word $s_{i_{1}}s_{i_{2}}\cdots s_{\ell(w)}$ is a reduced word for w. There is a small abuse of notation here: a reduced word is an element of the free monoid generated by the s _r ’s. Here, we are studying the equivalence classes of words modulo the relations (3). It is a well known fact that any two reduced words for a given permutation w are connected together using only (2) and (3) of the relations (3). Moreover, if a word $s_{i_{1}}s_{i_{2}}\cdots s_{k}$ is not reduced, then at least one instance of the relation (1) of (3) will be used to reduce it (see [16]). The set of equivalence classes of words that do not have any occurrence of $s_{r}s_{r+1}s_{r}$ are in bijection with 321-avoiding permutation(s). These are permutations w with no i < j < k such that w(i) > w(j) > w(k) (see [29]).

Consider now the infinite group $\mathit{S}_{\mathbb{Z}}$ of permutations of $\mathbb{Z}$ with only finitely many non-fixed points. This is the group generated by the simple reflections s _r for $r \in \mathbb{Z}$ subject to the relations in (3). For $w \in \mathit{S}_{\mathbb{Z}}$ we define the operator

$$\displaystyle{\mathbf{u}_{w} = \mathbf{u}_{i_{1}}\mathbf{u}_{i_{2}}\cdots \mathbf{u}_{i_{\ell(w)}}}$$

where $s_{i_{1}}s_{i_{2}}\cdots s_{\ell(w)}$ is any reduced word for w. Comparing the relations (3) with the relations (2) we see that this is a well defined operator. Moreover, if w is not 321-avoiding, then relation (2) of (2) gives $\mathbf{u}_{w} = 0$ and if $s_{i_{1}}s_{i_{2}}\cdots s_{k}$ is not a reduced word, then $\mathbf{u}_{i_{1}}\mathbf{u}_{i_{2}}\cdots \mathbf{u}_{i_{k}} = 0$. In order to show that the relations (2) generate all the relations of $\mathcal{M}\langle \mathbf{u}_{r}\rangle$ it is enough to prove that

Lemma 1.

• (a) For each $w \in \mathit{S}_{\mathbb{Z}}$ 321-avoiding, we have u _w ≠ 0,

• (b) For $w,w^{{\prime}}\in \mathit{S}_{\mathbb{Z}}$ 321-avoiding, we have that w ≠ w ^′ implies $\mathbf{u}_{w}\neq \mathbf{u}_{w^{{\prime}}}$ .

This will indeed show that the map from the free monoid generated by the u _r ’s modulo the relations (2) to $\mathcal{M}\langle \mathbf{u}_{r}\rangle$ has no kernel and is surjective. These results are known in some different form (see [12, 30]) and are not trivial. We will provide a proof here in this context for completeness.

Let us start with the lattice $\mathcal{Y}$ and its labelled covers. It is possible to encode this lattice and its covers with a subset of the 321-avoiding permutation(s) in $\mathit{S}_{\mathbb{Z}}$. Given a partition λ, add the two positive x-y axis. We put the numbers …, −3, −2, −1, 0 for every vertical step from infinity on the y-axis following the border of the partition. We put the numbers 1, 2, 3, … one on each horizontal step from left to right. The example below describes this procedure better for λ = (3, 1),

When we read the entries on the y-axis, then the outer boundary of λ followed by the x-axis, we obtain a 321-avoiding permutation $v(\lambda ) \in \mathit{S}_{\mathbb{Z}}$ (the entries on the axis are fixed points). In the example above we get

$$\displaystyle{v(\lambda ) = (\cdots \,,-3,-2,1,-1,2,3,0,4,5,\cdots \,).}$$

If we have a cover $\mu \stackrel{r}{\longrightarrow }\lambda$, then the entry v(μ)(r) ≤ 0 < v(μ)(r + 1). Adding a box on the diagonal of content r has the effect of interchanging these two entries in v(μ). We have shown the following:

Lemma 2.

$$\displaystyle{\mu \stackrel{r}{\longrightarrow }\lambda \qquad \Rightarrow\qquad v(\lambda ) = v(\mu )s_{r}\quad { and }\quad \ell(v(\lambda )) =\ell (v(\mu )) + 1.}$$

This lemma allows us to show Lemma 1 (b) if we know that u _w ≠ 0. Indeed, if u _w (μ) = λ, then the above lemma gives us that v(λ) = v(μ)w. Hence if w ≠ w ^′, then $v(\mu )w\neq v(\mu )w^{{\prime}}$ and $\mathbf{u}_{w}\neq \mathbf{u}_{w^{{\prime}}}$.

Now, in order to prove Lemma 1 (a) we need to construct a partition μ such that u _w (μ) = λ ≠ 0 for each 321-avoiding $w \in \mathit{S}_{\mathbb{Z}}$. When $\mu \subseteq \lambda$, we say that the diagram λ∕μ obtained by removing the cells of μ from λ is a skew diagram. For $w \in \mathit{S}_{\mathbb{Z}}$ that is 321-avoiding, we construct recursively on the length ℓ(w) a skew diagram λ∕μ such that u _w (μ) = λ. Moreover, if we read the content of the cells of λ∕μ, row by row, from left to right, starting at the bottom, then we get a sequence of integers $(j_{1},j_{2},\ldots,j_{k})$ such that $s_{j_{1}}s_{j_{2}}\cdots s_{j_{k}}$ is a reduced word for w. Finally, if (i, j) ∈ μ and (i + 1, j) ∉ μ and (i, j + 1) ∉ μ, then either (i + 1, j) ∈ λ or (i, j + 1) ∈ λ (see Example 1 below).

If ℓ(w) = 0, then the result is immediate as λ∕μ = ∅∕∅ does the trick. We assume that for all 321-avoiding permutations such that ℓ(w) < ℓ we can construct λ∕μ as above. Let $w = s_{i_{1}}s_{i_{2}}\cdots s_{i_{\ell}}$ be a reduced expression for a 321-avoiding permutation of length $\ell(w) =\ell$. By induction hypothesis we assume we have constructed λ∕μ for $w^{{\prime}} = s_{i_{1}}s_{i_{2}}\cdots s_{i_{\ell-1}}$. We can moreover assume that $(i_{1},i_{2},\ldots,i_{\ell-1})$ is the sequence of contents we read from λ∕μ. We consider a cell on the diagonal of content d = i _ℓ sliding from infinity downward and stop at (i, j) = (i, i + d) the first contact of either μ, λ∕μ or one of the x-y-axes. We claim that

$$\displaystyle{\mbox{ if $(i - 1,j - 1) \in \lambda /\mu $, then both $(i - 1,j) \in \lambda /\mu $ and $(i,j - 1) \in \lambda /\mu $.}}$$

In the sequence $(i_{1},i_{2},\ldots,i_{\ell-1})$, let k be such that $(i_{k},i_{k+1},\ldots,i_{\ell})$ are the contents of the cells in rows i + 1 and up in λ∕μ. Since no cell of λ∕μ is in column j and up in row i and up, we have that $i_{k^{{\prime}}} < j - i - 1 = d - 1$ for all $k \leq k^{{\prime}}\leq \ell-1$. This means that $s_{i_{k^{{\prime}}}}$ and s _d commute for all $k \leq k^{{\prime}}\leq \ell-1$. We have that

$$\displaystyle{ s_{i_{1}}s_{i_{2}}\cdots s_{i_{\ell}} = s_{i_{1}}s_{i_{2}}\cdots s_{d}s_{i_{k}}\cdots s_{i_{\ell-1}}. }$$

(4)

Now suppose (i, j − 1) ∉ λ∕μ. This means that s _d commutes with all s _c where c is the content of cells in row i of λ∕μ and all cells of content e in row i − 1 and column j ^′ > j + 1. We depict this as follows

where the dark cell corresponds to the added cell in position (i, j) of content d. Since the cell $(i,j - 1)\not\in \lambda /\mu$ all cells in row i have content c < d − 1. The cells in row i − 1 and column j ^′ > j have content e > d + 1. If $(i,j - 1)\not\in \lambda /\mu$, then we get $s_{d}s_{d}$ in the reduced expression of w, a contradiction. If in addition (i − 1, j) ∈ λ∕μ, then we get $s_{d}s_{d+1}s_{d}$ which contradicts the fact that w is 321-avoiding. Hence we must have that (i, j − 1) ∈ λ∕μ. Now if we assume that (i − 1, j) ∉ λ∕μ and (i, j − 1) ∈ λ∕μ the picture is now

The cell in position (i − 1, j − 1) has content d. All cells in row i and column j ^′ < j − 1 have content c < d − 1. This time we can move the reflection s _d corresponding to the cell in position (i − 1, j − 1) to pass the s _c in row i up to s _d−1 s _d . Again we get a contradiction as $s_{d}s_{d-1}s_{d}$ cannot occur in the reduced word of a 321-avoiding permutation w. This concludes the case when (i − 1, j − 1) ∈ λ∕μ. In this case we simply add the cell (i, j) to λ and not to μ. The diagram $(\lambda \cup (i,j))/\mu$ is a skew shape with all the desired properties and the right hand side of (4) is the reduced word of w that we read from this diagram.

We now consider the case where (i − 1, j − 1) ∈ μ or falls outside the first quadrant. If both (i − 1, j) ∈ λ∕μ and (i, j − 1) ∈ λ∕μ, then again the diagram $(\lambda \cup (i,j))/\mu$ is a skew shape with all the desired properties and the right hand side of (4) is the reduced word of w that we read from this diagram. By induction hypothesis, it is not the case that both $(i - 1,j)\not\in \lambda /\mu$ and $(i,j - 1)\not\in \lambda /\mu$. If (i − 1, j) ∈ λ∕μ and $(i,j - 1)\not\in \lambda /\mu$, then we move all the boxes of λ∕μ in row r ≥ i up each diagonal by 1 unit. This increases the size of λ and μ proportionally but keeps the relative shape of λ∕μ invariant along the diagonal lines. We then add the box (i, j) to lambda and add all the boxes (i ^′, j) for i ^′ < i to both λ and μ. Graphically we have

The case where $(i - 1,j)\not\in \lambda /\mu$ and (i, j − 1) ∈ λ∕μ is exactly transposed, interchanging the roles of row and column. In any case we obtain the desired skew shape $\lambda ^{{\prime}}/\mu ^{{\prime}}$ such that $\mathbf{u}_{w}(\mu ^{{\prime}}) =\lambda ^{{\prime}}\neq 0$.

Example 1.

Let us illustrate the induction procedure involved in the proof of Lemma 1 (a). Start with $w = s_{3}s_{-3}s_{4}s_{2}$ and its skew shape as illustrated on the left hand side of the figure below. The induction step tells us that the operator $\mathbf{u}_{ws_{0}}$ is not zero since $\mathbf{u}_{ws_0}(\mu)=\lambda$ where μ = (6, 4, 4, 3, 1) and λ = (6, 6, 5, 4, 2):

2.2 Pieri Operators on Young Lattice and Symmetric Functions

In the previous section, we obtained a very good understanding of the noncommutative monoid $\mathcal{M}\langle \mathbf{u}_{r}\rangle$. We now introduce a commutative algebra $\mathbf{B}\langle H_{k}\rangle$ that is isomorphic to the (Hopf) algebra of symmetric functions Sym. The algebra $\mathbf{B}\langle H_{k}\rangle$ is generated by certain homogeneous series H _k in the elements of $\mathcal{M}\langle \mathbf{u}_{r}\rangle$. This is using the Pieri operators theory as developed in [10] related to the multiplication of symmetric functions (see [25]).

There are several combinatorial Hopf algebras of interest for our study. As it turns out, $\mathcal{Y}$ is intimately related to Sym. The space of symmetric functions is well known to have different bases indexed by partitions. We refer the reader to [25, 27] for more details about our presentation of Sym. We use the standard notation for the common bases of Sym: h _λ for complete homogeneous; e _λ for elementary; m _λ for monomial; and s _λ for Schur functions. For simplicity, we let h _i and e _i denote the corresponding generators indexed by the partition (i).

There is a correspondence between the representation theory of all symmetric groups and symmetric functions. The multiplication and comultiplication in Sym corresponds to some induction and restriction of representations. In this identification, Schur functions encode irreducible representations. In particular we must have that the coefficients $C_{\lambda,\mu }^{\nu }$ in

$$\displaystyle{ s_{\lambda }s_{\mu } =\sum _{v}C_{\lambda,\mu }^{\nu }s_{\nu } }$$

(5)

are non-negative integers. They count the multiplicity of an irreducible in certain induced representations. This shows the nonnegativity of the constants $C_{\lambda,\mu }^{\nu }$ but does not give us a combinatorial formula for them. One is interested in a positive combinatorial rule to describe these numbers. This combinatorial rule is classically known as the Littlewood-Richardson rule. A particular case of this rule is Pieri rule that describes the multiplication by h _k :

$$\displaystyle{s_{\lambda }h_{k} =\sum _{\nu /\lambda \mbox{ a $k$-row strip}}s_{\nu }}$$

where a k-row strip is a diagram with k cells in distinct columns. In terms of the lattice $\mathcal{Y}$ we have the following characterization of k-row strip.

Lemma 3.

ν∕λ is a k-row strip if and only if there is a strictly increasing path of length k in $\mathcal{Y}$ from λ to ν. Moreover, if such a path exists from λ to ν, then it is unique.

Proof.

If ν∕λ is a k-row strip, then we can add the cells of ν∕λ to λ one by one from left to right. Since the cells are in distinct columns, they are in distinct diagonals as well. Adding them from left to right will give us the desired strictly increasing path from λ to ν. Conversely, if we have a strictly increasing path from λ to ν, then the cells of ν∕λ are in distinct diagonals. Assume two cells of ν∕λ are in the same column as pictured bellow

The cell A has content strictly smaller than the content of the cell B. In the path from λ to ν the cell A would be added before the cell B. But this is a contradiction since when the cell A is added without cell B this would not be a partition. Hence, ν∕λ is a k-row strip. □ 

This allows us to reconstruct the multiplication by h _k using operators on $\mathcal{Y}$. Let

$$\displaystyle{H_{k} =\sum _{i_{1}<i_{2}<\cdots <i_{k}}\mathbf{u}_{i_{k}}\cdots \mathbf{u}_{i_{2}}\mathbf{u}_{i_{1}}.}$$

This is an infinite series of operators of degree k in $\mathcal{M}\langle \mathbf{u}_{r}\rangle$. In view of Lemma 1, no term in the series H _k vanishes. If one fixes λ, there are only finitely many paths of length k from λ in $\mathcal{Y}$. This means that $H_{k}: \mathbb{Z}\mathcal{Y}\rightarrow \mathbb{Z}\mathcal{Y}$ is a well defined operator.

Proposition 2.

$$\displaystyle{H_{k} =\sum _{\ell(\zeta )=k}\mathbf{u}_{\zeta },}$$

where ζ runs over all permutations such that its disjoint cycle decomposition $\zeta = C_{1}C_{2}\cdots C_{s}$ has only cycles of the form $C_{i} = (a + b,\ldots,a + 1,a)$ for some $a,b \in \mathbb{Z}$ and b > 0.

Proof.

It suffices to show that

$$\displaystyle{\mathbf{u}_{i_{k}}\cdots \mathbf{u}_{i_{2}}\mathbf{u}_{i_{1}} = \mathbf{u}_{\zeta }}$$

with $i_{1} < i_{2} <\ldots < i_{k}$ if and only if ζ decomposes into disjoint cycles of the form (a + b, …, a + 1, a). The disjoint cycles of $\zeta = s_{i_{k}}\cdots s_{i_{2}}s_{i_{1}}$ for $i_{1} < i_{2} <\ldots < i_{k}$ correspond to the consecutive segments $s_{a+b}\cdots s_{a+1}s_{a} = (a + b,\ldots,a + 1,a)$.

Using Lemma 3

$$\displaystyle{H_{k}(\lambda ) =\sum _{\nu /\lambda \mbox{ a $k$-row strip}}\nu \quad \quad \;\Longleftrightarrow\;\quad \quad s_{\lambda }h_{k} =\sum _{\nu /\lambda \mbox{ a $k$-row strip}}s_{\nu }\,.}$$

This implies that

$$\displaystyle{H_{b}H_{a}(\lambda ) =\sum _{\nu }d_{\lambda,(a,b)}^{\nu }\nu \qquad \qquad \;\Longleftrightarrow\;\qquad \qquad s_{\lambda }h_{ a}h_{b} =\sum _{\nu }d_{\lambda,(a,b)}^{\nu }s_{\nu }\,.}$$

In particular, for all λ we have $H_{b}H_{a}(\lambda ) = H_{a}H_{b}(\lambda )$ since $h_{a}h_{b} = h_{b}h_{a}$. Again the result below is derived from very classical results.

Theorem 1.

The algebra $\mathbf{B}\langle H_{k}\rangle$ spanned by $\{H_{1},H_{2},H_{3},\ldots \}$ is isomorphic to Sym.

Proof.

We have seen above that $H_{b}H_{a}(\lambda ) = H_{a}H_{b}(\lambda )$, but to see that the product of series $H_{b}H_{a} = H_{a}H_{b}$ requires a little bit more argument. As we multiply $H_{a}H_{b}$ and $H_{b}H_{a}$, some terms will go to zero and others will survive. The terms that survive in $H_{a}H_{b}$ are of the form

$$\displaystyle{\mathbf{u}_{w} = \mathbf{u}_{i_{1}}\mathbf{u}_{i_{2}}\cdots \mathbf{u}_{i_{a}}\mathbf{u}_{j_{1}}\mathbf{u}_{j_{2}}\cdots \mathbf{u}_{j_{b}}}$$

where w is 321-avoiding, $i_{1} < i_{2} < \cdots < i_{a}$ and $j_{1} < j_{2} < \cdots < j_{b}$. Showing that $H_{a}H_{b} = H_{b}H_{a}$ requires the construction of a bijection between the possible reduced expressions of $w = s_{i_{1}}\cdots s_{i_{a}}s_{j_{1}}\cdots s_{j_{b}}$ and the ones of the form $w = s_{j_{1}^{{\prime}}}\cdots s_{j_{b}^{{\prime}}}s_{i_{1}^{{\prime}}}\cdots s_{i_{b}^{{\prime}}}$ where $i_{1}^{{\prime}} < i_{2}^{{\prime}} < \cdots < i_{a}^{{\prime}}$ and $j_{1}^{{\prime}} < j_{2}^{{\prime}} < \cdots < j_{b}^{{\prime}}$. This is done in [29] and in [9] using jeu-de-taquin. We then have that $\big\{H_{\mu } = H_{\mu _{1}}H_{\mu _{2}}\cdots H_{\mu _{1}}:\mu \mbox{ partition}\big\}$ spans $\mathbf{B}\langle H_{k}\rangle$. To see that the H _μ are linearly independent, it suffices to remark that

$$\displaystyle{H_{\mu }(\varnothing ) =\mu }$$

hence they have distinct values on ∅. □ 

Remark 1.

Theorem 1 follows easily from the more general Theorem 1.1 of [15]. The approach of Fomin and Greene has the advantage that one does not need to have all the relations of the u _r . It is enough to show that they satisfy the relations:

$$\displaystyle{ \begin{array}{rcrclcll} (1)&& \mathbf{u}_{r}\mathbf{u}_{t}& =&\mathbf{u}_{t}\mathbf{u}_{r} &&\mbox{ if $\vert r - t\vert > 1$}, \\ (2)&&(\mathbf{u}_{r} + \mathbf{u}_{r+1})\mathbf{u}_{r+1}\mathbf{u}_{r}& =&\mathbf{u}_{r+1}\mathbf{u}_{r}(\mathbf{u}_{r} + \mathbf{u}_{r+1})&&\end{array} }$$

(6)

It is clear that our operators u _r satisfy the relations (6). In later sections we will give examples where Fomin and Greene theory is not applicable.

2.3 NSym and QSym

For the theory of Pieri operators as developed in [10] we need to introduce two graded dual Hopf algebras. First, the algebra of non-commutative symmetric functions Nsym is a non-commutative analogue of Sym that arises by considering an algebra with one non-commutative generator at each positive degree. We define Nsym as the algebra with generators $\{\mathbf{h}_{1},\mathbf{h}_{2},\ldots \}$ 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 is given by the set of complete homogeneous functions $\{\mathbf{h}_{\alpha }:= \mathbf{h}_{\alpha _{1}}\mathbf{h}_{\alpha _{2}}\cdots \mathbf{h}_{\alpha _{m}}\}_{\alpha \vDash n}$ indexed by compositions α of n.

We have the projection morphism $\chi: Nsym \rightarrow Sym$ defined by sending the basis element h _α to the complete homogeneous symmetric function

$$\displaystyle{\chi (\mathbf{h}_{\alpha }):= h_{\alpha _{1}}h_{\alpha _{2}}\cdots h_{\alpha _{\ell(\alpha )}}}$$

and extended linearly to all of $Nsym$. A second basis of NSym is given by the R _α , usually called the ribbon basis. For this, given a composition $\alpha = (\alpha _{1},\cdots \,,\alpha _{m}) \vDash n$ we denote its length m by ℓ(α). The ribbon basis R _α are defined by

$$\displaystyle{ R_{\alpha } =\sum _{\beta \geq \alpha }(-1)^{\ell(\alpha )-\ell(\beta )}\mathbf{h}_{\beta }, \text{or equivalently} \mathbf{h}_{\alpha } =\sum _{\beta \geq \alpha }R_{\beta } }$$

(7)

where α ≤ β if α is finer than β.

The product expansion follows easily from the non-commutative product on the generators

$$\displaystyle{\mathbf{h}_{\alpha }\mathbf{h}_{\beta } = \mathbf{h}_{\alpha _{1},\ldots \alpha _{\ell(\alpha )},\beta _{1},\ldots \beta _{\ell(\beta )}}.}$$

Nsym has a coalgebra structure, which is defined on the generators by

$$\displaystyle{\varDelta (\mathbf{h}_{j}) =\sum _{ i=0}^{j}\mathbf{h}_{ i} \otimes \mathbf{h}_{j-i}.}$$

This determines the action of the coproduct on the basis h _α since the coproduct is an algebra morphism with respect to the product.

Second, the Hopf algebra of quasi-symmetric functions, Qsym is dual to Nsym and contains Sym as a subalgebra. The graded component Qsym _n is indexed by compositions of n. This algebra is most readily realized within the ring of power series of bounded degree $\mathbb{Q}[\![x_{1},x_{2},\ldots ]\!]$. The monomial quasi-symmetric function indexed by a composition α is defined as

$$\displaystyle{ M_{\alpha } =\sum _{i_{1}<i_{2}<\cdots <i_{m}}x_{i_{1}}^{\alpha _{1} }x_{i_{2}}^{\alpha _{2} }\cdots x_{i_{m}}^{\alpha _{m} }. }$$

(8)

The algebra of quasi-symmetric functions, Qsym, can then be defined as the algebra with the monomial quasi-symmetric functions as a basis, whose multiplication is inherited as a subalgebra of $\mathbb{Q}[\![x_{1},x_{2},\ldots ]\!]$. We define the coproduct on this basis as:

$$\displaystyle{\varDelta (M_{\alpha }) =\sum _{S\subset \{1,2,\ldots,\ell(\alpha )\}}M_{\alpha _{S}} \otimes M_{\alpha _{S^{c}}},}$$

where if $S =\{ i_{1} < i_{2} < \cdots < i_{\vert S\vert }\}$, then $\alpha _{S} = (\alpha _{i_{1}},\alpha _{i_{2}},\ldots,\alpha _{i_{\vert S\vert }})$.

We view Sym as a subalgebra of Qsym. In fact, the usual monomial symmetric functions m _λ  ∈ Sym expand positively in the quasi-symmetric monomial functions:

$$\displaystyle{m_{\lambda } =\sum _{sort(\alpha )=\lambda }M_{\alpha },}$$

where sort(α) is the partition obtained by organizing the parts of α from the largest to the smallest.

The fundamental quasi-symmetric functions, denoted by F _α form another basis of Qsym _n and are defined by their expansion in the monomial quasi-symmetric basis:

$$\displaystyle{F_{\alpha } =\sum _{\beta \leq \alpha }M_{\beta }.}$$

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: Nsym \times Qsym \rightarrow \mathbb{Q}$, defined under this duality as either $\langle \mathbf{h}_{\alpha },M_{\beta }\rangle =\delta _{\alpha,\beta }$, or $\langle R_{\alpha },F_{\beta }\rangle =\delta _{\alpha,\beta }$.

2.4 Skew Function K _[λ, ν]

Associated to any $\lambda \subseteq \nu$ in $\mathcal{Y}$, we construct a quasisymmetric function K _[λ, ν] following the notion of Pieri operators as developed in [10]. Let $\langle \lambda,\mu \rangle =\delta _{\lambda,\mu }$ define a scalar product on $\mathbb{Z}\mathcal{Y}$. Using the operators H _k on $\mathbb{Z}\mathcal{Y}$ we can define

$$\displaystyle{K_{[\lambda,\nu ]} =\sum _{\alpha }\langle H_{\alpha }(\lambda ),\nu \rangle M_{\alpha }.}$$

In view of the commutation relation $H_{a}H_{b} = H_{b}H_{a}$, the function $K_{[\lambda,\nu ]}$ is not only quasisymmetric but symmetric as well. Indeed since $H_{\alpha } = H_{sort(\alpha )}$ and since $m_{\lambda } =\sum\nolimits_{sort(\alpha )=\lambda }M_{\alpha }$, we have that

$$\displaystyle{K_{[\lambda,\nu ]} =\sum _{\mu }\langle H_{\mu }(\lambda ),\nu \rangle m_{\mu }}$$

is symmetric. We are interested in knowing the coefficients of K _[λ, ν] when expanded in different bases. We remark that we have an action of NSym on $\mathbb{Z}\mathcal{Y}$ given by $\mathbf{h}_{\alpha }.\lambda = H_{\alpha }(\lambda )$. In this case the action factors through the projection χ: NSym → Sym. As observed earlier, the basis h _α of NSym is dual to the basis M _α of QSym. A straightforward computation shows that

$$\displaystyle{K_{[\lambda,\nu ]} =\sum _{\alpha }\langle \mathbf{h}_{\alpha }.\lambda,\nu \rangle M_{\alpha } =\sum _{\alpha }\langle \mathbf{x}_{\alpha }.\lambda,\nu \rangle Y _{\alpha },}$$

for any dual bases x _α and Y _α of NSym and QSym respectively. We thus have that

Theorem 2.

$$\displaystyle{K_{[\lambda,\nu ]} =\sum _{\alpha }\langle R_{\alpha }.\lambda,\nu \rangle F_{\alpha } =\sum _{\mu }C_{\lambda,\mu }^{\nu }s_{\mu }}$$

where C _λ,μ ^ν is given in  (5) . Moreover for $\alpha = (\alpha _{1},\ldots,\alpha _{k})$ a composition of n, we have that $\langle R_{\alpha }.\lambda,\nu \rangle$ counts the number of paths in $\mathcal{Y}$ from λ to ν with labels $i_{1},i_{2},\ldots,i_{n}$ such that $i_{r} > i_{r+1}$ if and only if $r \in D(\alpha ) =\{\alpha _{1},\alpha _{1} +\alpha _{2},\ldots,n -\alpha _{k}\}$ .

Proof.

The first equality follows from duality between the R _α and the F _α . For the second equality, from the definition of H _k we remark that for

$$\displaystyle{K_{[\lambda,\nu ]} =\sum _{\mu }\langle H_{\mu }(\lambda ),\nu \rangle m_{\mu }}$$

the coefficient $\langle H_{\mu }(\lambda ),\nu \rangle = d_{\lambda,\mu }^{\nu }$ is the coefficient of s _ν in the product $s_{\lambda }h_{\mu }$. In Sym, the bases h _μ and m _μ are dual and the basis s _μ is self dual. Hence the coefficient of s _μ in K _[λ, ν] is the same as the coefficient of s _ν in $s_{\lambda }s_{\mu }$.

The fact that $\langle R_{\alpha }.\lambda,\nu \rangle$ counts the paths as described follows from a simple inclusion-exclusion argument and the fact that by definition $\langle \mathbf{h}_{\alpha }.\lambda,\nu \rangle$ counts the paths in $\mathcal{Y}$ from λ to ν with labels $i_{1},i_{2},\ldots,i_{n}$ such that $i_{r} > i_{r+1}$ only if $r \in D(\alpha ) =\{\alpha _{1},\alpha _{1} +\alpha _{2},\ldots,n -\alpha _{k}\}$. □ 

Remark 2.

The function K _[λ, ν] in Theorem 2 is the well known skew-Schur function s _ν∕λ . It is denoted F _ν∕λ by Fomin and Greene in [15]. Theorem 1.2 of [15] shows that the coefficients $C_{\lambda,\mu }^{\nu }$ are positive and count paths in $\mathcal{Y}$ satisfying a precise rule. This is a very powerful method that works for any monoid of operators u _r satisfying the relations (6). Several classical examples are solved by this theory which gives a method to understand the coefficients we are interested in. This includes the weak order of the symmetric group and the Stanley symmetric function F _w∕u originally defined in [29]. There are many new situations where Fomin and Greene theory cannot be applied and we will give some examples of this in the next sections.

3 Schubert vs Schur

We present an example of a monoid that does not satisfy Fomin and Greene’s conditions, yet it is interesting and still yields some symmetry and positivity. In this example, which is taken from the theory of Schubert polynomials (see [7, 23, 24]), positivity results are highly non-trivial. We consider operators on the infinite symmetric group defined from Monk’s rule. From these operators one defines Pieri operators that mimic the multiplication of Schubert polynomials by symmetric functions. Symmetry follows from the commutativity of multiplication and positivity follows from geometry. A combinatorial proof of positivity is much harder to obtain and was only recently achieved in [4] using the techniques of [2].

Let $u \in \mathcal{S}_{\infty }:=\bigcup _{n\geq 0}\mathcal{S}_{n}$ be an infinite permutation where all but a finite number of positive integers are fixed. Schubert polynomials $\mathfrak{S}_{u}$ are indexed by such permutations [23, 24]. These polynomials form a homogeneous basis of the polynomial ring $\mathbb{Z}[x_{1},x_{2},\ldots ]$ in countably many variables. The coefficients $c_{u,v}^{w}$ in

$$\displaystyle{ \mathfrak{S}_{u}\mathfrak{S}_{v} =\sum _{w}c_{u,v}^{w}\mathfrak{S}_{ w}, }$$

(9)

are known to be positive from geometry.

3.1 Operators on the r-Bruhat Order

We now define operators on the r-Bruhat order on $\mathcal{S}_{\infty }$. Let ℓ(w) be the length of a permutation $w \in \mathcal{S}_{\infty }$. We define the r-Bruhat order <  _r by its covers. Given permutations $u,w \in \mathcal{S}_{\infty }$, we say that $u \lessdot _{r}w$ if $\ell(u) + 1 =\ell (w)$ and u ⁻¹ w = (i, j), where (i, j) is a reflection with i ≤ r < j.

For 0 < a < b, let u _ab denote the operator on $\mathbb{Z}\mathit{S}_{\infty }$ defined by

$$\displaystyle{ \begin{array}{rcl} \mathbf{u}_{ab}: \ \mathbb{Z}\mathit{S}_{\infty }&\longrightarrow &\quad \mathbb{Z}\mathit{S}_{\infty }, \\ u\quad &\longmapsto &\ \ \left \{\begin{array}{ll} (a,b)u&\mbox{ if }u \lessdot _{r}(a,b)u, \\ 0 &\mbox{ otherwise.} \end{array} \right. \end{array}}$$

(10)

We have shown in [8] that these operators satisfy the following relations:

$$\displaystyle{ \begin{array}{clrclll} (1)&&\mathbf{u}_{bc}\mathbf{u}_{cd}\mathbf{u}_{ac}& \equiv &\mathbf{u}_{bd}\mathbf{u}_{ab}\mathbf{u}_{bc}, &&\mbox{ if $a < b < c < d$}, \\ (2)&&\mathbf{u}_{ac}\mathbf{u}_{cd}\mathbf{u}_{bc}& \equiv &\mathbf{u}_{bc}\mathbf{u}_{ab}\mathbf{u}_{bd}, &&\mbox{ if $a < b < c < d$}, \\ (3)&& \mathbf{u}_{ab}\mathbf{u}_{cd}& \equiv &\mathbf{u}_{cd}\mathbf{u}_{ab}, &&\mbox{ if $b < c$ or $a < c < d < b$}, \\ (4)&& \mathbf{u}_{ac}\mathbf{u}_{bd}& \equiv &\mathbf{u}_{bd}\mathbf{u}_{ac}\ \equiv \ \mathbf{0}, &&\mbox{ if $a \leq b < c \leq d$}, \\ (5)&&\mathbf{u}_{bc}\mathbf{u}_{ab}\mathbf{u}_{bc}& \equiv &\mathbf{u}_{ab}\mathbf{u}_{bc}\mathbf{u}_{ab}\ \equiv \ \mathbf{0},&&\mbox{ if $a < b < c$}.\end{array} }$$

(11)

The 0 in relations (4) and (5) mean(s) that no chain in any r-Bruhat order can contain such a sequence of transpositions. On the other hand, relations (1), (2) and (3) are complete and transitively connect any two chains in a given interval [u, w] _r . It is interesting to notice that the relations are independent of r. This is a fact noticed in [7]: a nonempty interval [u, w] _r in the r-Bruhat order is isomorphic to a nonempty interval $[x,y]_{r^{{\prime}}}$ in an r ^′-Bruhat order as long as $wu^{-1} = yx^{-1}$. It is important to remark that if one fixes r, there are in fact more relations than (11). We will clarify this after Proposition 3. For the moment we assume that the operator u _ab acts on the disjoint union of all r-Bruhat orders for r > 0. Let $\mathcal{M}\langle \mathbf{u}_{ab}\rangle$ be the monoid generated by the 0 operator and all operators u _ab for a < b. A consequence of [8] is the following proposition.

Proposition 3.

$\mathcal{M}\langle \mathbf{u}_{ab}\rangle$ is the monoid freely generated by the u _ab for $0 < a < b \in \mathbb{Z}$ and 0 modulo the relations  (11) .

Remark 3.

When we specify a chain $\mathbf{u}_{a_{n}b_{n}}\cdots \mathbf{u}_{a_{2}b_{2}}\mathbf{u}_{a_{1}b_{1}}$ in the interval [u, w] _r , it is understood that this is the actual sequence $(\mathbf{u}_{a_{n}b_{n}},\ldots,\mathbf{u}_{a_{2}b_{2}},\mathbf{u}_{a_{1}b_{1}})$ of operators we are referring to. This is a slight abuse of notation but it simplifies notation and the context will make it clear. □ 

In fact we can say much more about the monoid $\mathcal{M}\langle \mathbf{u}_{ab}\rangle$. Given any $\zeta \in \mathit{S}_{\infty }$ we produce a chain in a nonempty interval [u, w] _r for some r as follows. Let $up(\zeta ) =\{ a:\zeta ^{-1}(a) < a\}$. This is a finite set and we can set r =  | up(ζ) | . To construct w, we sort the elements in $up(\zeta ) =\{ i_{1} < i_{2} < \cdots < i_{r}\}$ and its complement $up^{c}(\zeta ) = \mathbb{Z}_{>0}\setminus up(\zeta ) =\{ j_{1} < j_{2} <\ldots \}$. Next, we put $w = [i_{1},i_{2},\ldots,i_{r},j_{1},j_{2},\ldots ] \in \mathit{S}_{\infty }$ and then we let u = ζ ⁻¹ w. Notice that u, w and r constructed this way depend on ζ. From [7, 8], we have that [u, w] _r is non-empty and now we want to construct a chain in [u, w] _r . This is done recursively as follows: let

$$\displaystyle\begin{array}{rcl} a_{1}& =& u(i_{1})\text{ where }i_{1} =\max \{ i \leq r: u(i) < w(i)\}\text{and } {}\\ b_{1}& =& u(j_{1})\text{ where }j_{1} =\min \{ j >\ r: u(j) >\ u(i_{1}) \geq w(j)\} {}\\ \end{array}$$

then $\mathbf{u}_{a_{n}b_{n}}\cdots \mathbf{u}_{a_{2}b_{2}}\mathbf{u}_{a_{1}b_{1}}$ is a chain in [u, w] _r for any chain $\mathbf{u}_{a_{n}b_{n}}\cdots \mathbf{u}_{a_{2}b_{2}}$ in $[(a_{1},b_{1})u,w]_{r}$. Here we have that all the other possible chains in the interval [u, w] _r are obtained from the chain $\mathbf{u}_{a_{n}b_{n}}\cdots \mathbf{u}_{a_{2}b_{2}}\mathbf{u}_{a_{1}b_{1}}$ by sequences of transformations given in Eq. (11). This means that the operator $\mathbf{u}_{\zeta } = \mathbf{u}_{a_{n}b_{n}}\cdots \mathbf{u}_{a_{2}b_{2}}\mathbf{u}_{a_{1}b_{1}}$ is well defined, non zero for any r ^′ ≥ r and if ζ ≠ ζ ^′ then $\mathbf{u}_{\zeta }\neq \mathbf{u}_{\zeta ^{{\prime}}}$. For a fix r,

$$\displaystyle{\mathbf{u}_{\zeta }(u) = \left \{\begin{array}{ll} \zeta u&\mbox{ if }u < _{r}\zeta u, \\ 0 &\mbox{ otherwise.} \end{array} \right.}$$

Example 2.

Consider ζ = [3, 6, 2, 5, 4, 1, …] where all other values are fixed. We have that up(ζ) = { 3, 5, 6} and $up^{c}(\zeta ) =\{ 1,2,4,\ldots \}$. In this case, r = 3, w = [3, 5, 6, 1, 2, 4, …] and u = [1, 4, 2, 6, 3, 5, …]. The recursive procedure above produces the chain $\mathbf{u}_{23}\mathbf{u}_{12}\mathbf{u}_{45}\mathbf{u}_{26}$ in [u, v]₃. We get all other chains by using the relations (11):

$$\displaystyle{ \begin{array}{cccc} \mathbf{u}_{23}\mathbf{u}_{12}\mathbf{u}_{45}\mathbf{u}_{26},&\mathbf{u}_{23}\mathbf{u}_{12}\mathbf{u}_{26}\mathbf{u}_{45},&\mathbf{u}_{23}\mathbf{u}_{45}\mathbf{u}_{12}\mathbf{u}_{26},&\mathbf{u}_{45}\mathbf{u}_{23}\mathbf{u}_{12}\mathbf{u}_{26},\\ \mathbf{u}_{ 45}\mathbf{u}_{13}\mathbf{u}_{36}\mathbf{u}_{23},&\mathbf{u}_{13}\mathbf{u}_{45}\mathbf{u}_{36}\mathbf{u}_{23},&\mathbf{u}_{13}\mathbf{u}_{36}\mathbf{u}_{45}\mathbf{u}_{23},&\mathbf{u}_{13}\mathbf{u}_{36}\mathbf{u}_{23}\mathbf{u}_{45}.\end{array} }$$

(12)

The interval obtained in this case is

Since u <  _r ζ u in this case, we have u _ζ (u) = ζ u ≠ 0 for this r. Now for any r ^′ ≥ r, we can build $w^{{\prime}} = [3,5,6,7,8,\ldots,7 + r^{{\prime}}- r,1,2,4,\ldots ]$, $u^{{\prime}} = [1,4,2,7,8,\ldots,7 + r^{{\prime}}- r,6,3,5,\ldots ]$ by adding fixed points of ζ = wu ⁻¹ before the position r ^′. In this way we construct a permutation u ^′ such that $u^{{\prime}} < _{r^{{\prime}}}\zeta u^{{\prime}}$ and $\mathbf{u}_{\zeta }(u^{{\prime}}) =\zeta u^{{\prime}}\neq 0$ for any r ^′ ≥ r.

The above discussion shows the following corollary:

Corollary 1.

The monoid $\mathcal{M}\langle \mathbf{u}_{ab}\rangle$ is precisely

$$\displaystyle{\mathcal{M}\langle \mathbf{u}_{ab}\rangle =\big\{ \mathbf{u}_{\zeta }:\zeta \in \mathcal{S}_{\infty }\big\}\cup \big\{\mathbf{0}\big\}.}$$

Moreover, if we let $\mathcal{M}_{r}\langle \mathbf{u}_{ab}\rangle$ be the monoid generated by the operator u _ab acting on r-Bruhat order for a fixed r, we have

$$\displaystyle{\mathcal{M}_{r}\langle \mathbf{u}_{ab}\rangle =\big\{ \mathbf{u}_{\zeta }:\zeta \in \mathcal{S}_{\infty },\ \vert up(\zeta )\vert \leq r\big\} \cup \big\{\mathbf{0}\big\}.}$$

Here the multiplication in $\mathcal{M}\langle \mathbf{u}_{ab}\rangle$ is given by $\mathbf{u}_{\zeta }\mathbf{u}_{\eta } = \mathbf{u}_{\zeta \eta }$ if η u <  _r ζ η u for some u and r, and is 0 otherwise.

3.2 Pieri Operators on r-Bruhat Order

We now introduce some Pieri operators related to the operators u _ab . These Pieri operators are defined in such a way that they mimic the multiplication of a Schubert polynomial by the homogeneous symmetric polynomial $h_{k}(x_{1},\ldots,x_{r})$.

A permutation $v \in \mathcal{S}_{\infty }$ such that $v(1) < v(2) < \cdots < v(r)$ and $v(r + 1) < v(r + 2) < \cdots$ is called r-grassmannian. Any partition $\lambda =\lambda _{1} \geq \lambda _{2} \geq \cdots \geq \lambda _{r} \geq 0$ with at most r non-zero parts defines a unique r-grassmannian permutation

$$\displaystyle{v(\lambda,r) = [\lambda _{r} + 1,\lambda _{r-1} + 2,\ldots,\lambda _{1} + r,v(r + 1),\ldots ],}$$

where v(r + 1) < v(r + 2) < ⋯ are the positive integers not in $\{\lambda _{r} + 1,\lambda _{r-1} + 2,\ldots,\lambda _{1} + r\}$. As seen in [23, 24], for any such partition λ we have that the Schur polynomial $S_{\lambda }(x_{1},x_{2},\ldots,x_{r})$ is equal to the Schubert polynomial

$$\displaystyle{\mathfrak{S}_{v(\lambda,r)} = S_{\lambda }(x_{1},x_{2},\ldots,x_{r}).}$$

In particular, the homogeneous polynomial $h_{k}(x_{1},\ldots,x_{r})$ is the Schubert polynomial $\mathfrak{S}_{v((k),r)}$. The multiplication of an arbitrary Schubert polynomial by $h_{k}(x_{1},\ldots,x_{r})$ is known as the Pieri formula for Schubert polynomials. It was originally stated as a theorem by Lascoux and Schützenberger [23] with a very brief outline of a proof. Sottile later proved this formula geometrically and clarified the history for us [28]. Using the operators u _ab on the r-Bruhat order, this can be stated as follows.

$$\displaystyle{ \mathfrak{S}_{u}h_{k}(x_{1},\ldots,x_{r}) = \mathfrak{S}_{u}\mathfrak{S}_{v((k),r)} =\sum _{w}\mathfrak{S}_{w}, }$$

(13)

where the sum is over all w >  _r u such that $\mathbf{u}_{a_{k}b_{k}}\cdots \mathbf{u}_{a_{2}b_{2}}\mathbf{u}_{a_{1}b_{1}}(u) = w$ for some $b_{1} < b_{2} < \cdots < b_{k}$. It is known (see [7, 8]) that in such interval [u, w] _r , there must be a chain from u to w that is increasing in the sense that $\mathbf{u}_{a_{k}b_{k}}\cdots \mathbf{u}_{a_{2}b_{2}}\mathbf{u}_{a_{1}b_{1}}(u) = w$ with $b_{1} < b_{2} < \cdots < b_{k}$. Such a chain, when it exists, is unique among all saturated chains in [u, w] _r .

We now introduce series H _k similar to Sect. 2.2 that will commute with each other and encode the Pieri formula for Schubert polynomials. Let

$$\displaystyle{ H_{k} =\sum _{{ b_{1}<b_{2}<\cdots <b_{k} \atop a_{i}<b_{i}} }\mathbf{u}_{a_{k}b_{k}}\cdots \mathbf{u}_{a_{2}b_{2}}\mathbf{u}_{a_{1}b_{1}}. }$$

(14)

Many of the terms in this sum are zero, the non-zero terms have a very special form. In [23], we see that it is important to look at the disjoint decomposition of ζ into disjoint cycles. In the next proposition we describe the u _ζ appearing in H _k and the structure of the disjoint cycles. For $\zeta \in \mathcal{S}_{\infty }$, let $\zeta = C_{1}C_{2}\cdots C_{s}$ be the decomposition of ζ in disjoint non-trivial cycles. There are only finitely many non-fixed points, so only finitely many non-trivial cycles. Given a cycle $C = (c_{1},c_{2},\ldots,c_{m})$, we say that C is increasing if $c_{m} < c_{m-1} < \cdots < c_{1}$. Given two disjoint increasing cycles $C = (c_{1},c_{2},\ldots,c_{m})$ and $C^{{\prime}} = (c_{1}^{{\prime}},c_{2}^{{\prime}},\ldots,c_{n}^{{\prime}})$ we say that they are totally disjoint if any of the following happens

• 1. $[c_{m},c_{1}] \cap [c_{n}^{{\prime}},c_{1}^{{\prime}}] = \varnothing$, or

• 2. $[c_{m},c_{1}] \cap \{ c_{1}^{{\prime}},c_{2}^{{\prime}},\ldots,c_{n}^{{\prime}}\} = \varnothing$, or

• 3. $[c_{n}^{{\prime}},c_{1}^{{\prime}}] \cap \{ c_{1},c_{2},\ldots,c_{m}\} = \varnothing$.

In case (1), the two cycles have support in disjoint intervals. In cases (2) and (3), If the intervals intersect, their intersection must fall between two successive elements in the support of the other cycles. For $C = (c_{1},c_{2},\ldots,c_{m})$ let | ​ | C | ​ |  = m − 1. For $\zeta = C_{1}C_{2}\cdots C_{s}$ a product of totally disjoint increasing cycles such that $k =\sum \nolimits_{ i=1}^{s}\vert \!\vert C_{i}\vert \!\vert$, we say that ζ is k-increasing.

Proposition 4.

$$\displaystyle{H_{k} =\sum _{\zeta }\mathbf{u}_{\zeta },}$$

where ζ runs over k-increasing permutations.

Proof.

We proceed by induction on k. The result is clear for k = 1. Assume the result is true for any non-zero product $\mathbf{u}_{\zeta ^{{\prime}}} = \mathbf{u}_{a_{k-1}b_{k-1}}\cdots \mathbf{u}_{a_{2}b_{2}}\mathbf{u}_{a_{1}b_{1}}$ such that $b_{1} < b_{2} <\ldots < b_{k-1}$. We assume that $\mathbf{u}_{\zeta ^{{\prime}}} = \mathbf{u}_{C_{1}}\mathbf{u}_{C_{2}}\cdots \mathbf{u}_{C_{s}}$ where $\zeta = C_{1}C_{2}\cdots C_{s}$ are totally disjoint increasing cycles. For $C = (c_{1},c_{2},\ldots,c_{m})$, an increasing cycle, we have $\mathbf{u}_{C} = \mathbf{u}_{c_{2}c_{1}}\mathbf{u}_{c_{3}c_{2}}\cdots \mathbf{u}_{c_{m}c_{m-1}}$. A careful analysis of the relation (11) shows that for totally disjoint increasing cycles $C_{1}C_{2}\cdots C_{s}$, the operators $\mathbf{u}_{C_{i}}$ and $\mathbf{u}_{C_{j}}$ commute for i ≠ j. We will assume that a _k−1 and b _k−1 belong to the cycle C ₁.

We investigate what happens when we perform a non-zero product $\mathbf{u}_{a_{k}b_{k}}\mathbf{u}_{\zeta ^{{\prime}}}$ where $b_{k} > b_{k-1}$. If $a_{k} > b_{k-1}$, then $(b_{k},a_{k})$ is a new increasing cycle totally disjoint from any cycle of $\zeta ^{{\prime}}$. If $a_{k} = b_{k-1}$, then $a_{k},b_{k}$ increases the cycle C ₁ of ζ ^′ and is still totally disjoint from the other cycles of ζ ^′.

If $a_{k} < b_{k-1}$, then from (11)–(4) we must have $a_{k} < a_{k-1}$ and the operators $\mathbf{u}_{a_{k}b_{k}}\mathbf{u}_{a_{k-1}b_{k-1}}\neq \mathbf{0}$ commute. Let $C_{1} = (c_{1},c_{2},\ldots,c_{m})$ and recall that we have $b_{k-1} = c_{1}$ and $a_{k-1} = c_{2}$. We have $\mathbf{u}_{C_{1}} = \mathbf{u}_{c_{2}c_{1}}\mathbf{u}_{c_{3}c_{2}}\cdots \mathbf{u}_{c_{m}c_{m-1}}$ and $b_{k} > b_{k-1} = c_{1} > c_{i}$ for all i. Since $a_{k} < a_{k-1} = c_{2}$, then $\mathbf{u}_{a_{k}b_{k}}\mathbf{u}_{c_{3}c_{2}}\neq \mathbf{0}$ implies $a_{k} < c_{3}$ and $\mathbf{u}_{a_{k}b_{k}}\mathbf{u}_{c_{3}c_{2}}$ commutes. Continuing this process, we find that $\mathbf{u}_{a_{k}b_{k}}\mathbf{u}_{C_{1}} = \mathbf{u}_{C_{1}}\mathbf{u}_{a_{k}b_{k}}\neq \mathbf{0}$ and $a_{k} < c_{m} < c_{1} < b_{k}$. This means C ₁ and $(b_{k},a_{k})$ are totally disjoint increasing cycles. We have

$$\displaystyle{\mathbf{u}_{a_{k}b_{k}}\mathbf{u}_{\zeta ^{{\prime}}} = \mathbf{u}_{C_{1}}\mathbf{u}_{a_{k}b_{k}}\mathbf{u}_{C_{2}}\cdots \mathbf{u}_{C_{s}}.}$$

From the induction hypothesis, the result holds for $\mathbf{u}_{a_{k}b_{k}}\mathbf{u}_{C_{2}}\cdots \mathbf{u}_{C_{s}}$ and decomposes into totally disjoint increasing cycles. Moreover C ₁ will be totally disjoint from the cycles of $(b_{k}a_{k})C_{2}\cdots C_{s}$.

As in Corollary 1, the expression in Proposition 4 is valid as long as we consider all possible r-Bruhat orders for r > 1. If we fix r, then most of the u _ζ in H _k will act as zero on the r-Bruhat order. For a fixed r, we see that $H_{k}: \mathbb{Z}\mathcal{S}_{\infty }\rightarrow \mathbb{Z}\mathcal{S}_{\infty }$ is a well defined operator on the r-Bruhat order. From Corollary 1, for a fixed r,

$$\displaystyle{H_{k} =\sum _{{ \zeta \mbox{ is $k$-increasing} \atop \vert up(\zeta )\vert \leq r} }\mathbf{u}_{\zeta }.}$$

By definition of H _k and Eq. (13), we have

$$\displaystyle{H_{k}(w) =\!\!\!\!\sum \nolimits_{wu^{-1}\mbox{ $k$-increasing}}\!\!\!\!u\quad \quad \;\Longleftrightarrow\;\quad \quad \mathfrak{S}_{w}h_{k}(x_{1},\ldots,x_{r}) =\!\!\!\!\sum \nolimits_{wu^{-1}\mbox{ $k$-increasing}}\!\!\!\!\mathfrak{S}_{u}\,.}$$

This implies that

$$\displaystyle{ \begin{array}{lr} H_{b}H_{a}(w) =\sum _{\nu }d_{w,(a,b)}^{u}u& \\ \qquad \qquad \;\Longleftrightarrow\; &\mathfrak{S}_{w}h_{a}(x_{1},\ldots,x_{r})h_{b}(x_{1},\ldots,x_{r}) =\sum _{u}d_{w,(a,b)}^{u}\mathfrak{S}_{u}\,.\\ \end{array} }$$

(15)

In particular, for all w we have $H_{b}H_{a}(w) = H_{a}H_{b}(w)$ since $h_{a}h_{b} = h_{b}h_{a}$. The result below is not as well known as Theorem 1.

Theorem 3.

The algebra $\mathbf{B}\langle H_{k}\rangle$ spanned by $\{H_{1},H_{2},H_{3},\ldots \}$ as operators on the r-Bruhat order for r > 0 is isomorphic to Sym.

Proof.

As we multiply $H_{a}H_{b}$ and $H_{b}H_{a}$, some terms will go to zero and others will survive. The terms that survive in $H_{a}H_{b}$ are of the form

$$\displaystyle{\mathbf{u}_{w} = \mathbf{u}_{\zeta }\mathbf{u}_{\eta }}$$

where ζ is a-increasing and η is b-increasing. Let $d_{(a,b)}^{w}$ be the coefficient of $\mathbf{u}_{w}$ in $H_{a}H_{b}$. From Corollary 1, for any $w \in \mathcal{S}_{\infty }$ we can find u and an r > 0 such that u _w (u) = v ≠ 0. So $d_{(a,b)}^{w}$ is the coefficient of v in $H_{a}H_{b}(u)$. From (15), for all w, we have

$$\displaystyle{d_{(a,b)}^{w} = \mbox{ Coeff of $v$ in $H_{ a}H_{b}(u)$} = \mbox{ Coeff of $v$ in $H_{b}H_{a}(u)$} = d_{(b,a)}^{w}.}$$

Hence $H_{a}H_{b} = H_{b}H_{a}$.

The algebra $\mathbf{B}\langle H_{k}\rangle$ is clearly spanned by $H_{\lambda } = H_{\lambda _{1}}\cdots H_{\lambda _{\ell}}$ where λ runs over all partitions. To show the isomorphism with Sym, we only need to show that the H _λ are linearly independent. Let $r \geq \ell (\lambda )$. Using (15), we have that $H_{\lambda }(Id) =\sum \nolimits_{\mu }d_{\lambda }^{\mu }v_{\mu }$ where v _μ is the unique grassmannian permutation defined by v(v _μ , r) = μ and the $d_{\lambda }^{\mu }$ satisfy

$$\displaystyle{h_{\lambda }(x_{1},\ldots,x_{r}) =\sum \nolimits_{\mu }d_{\lambda }^{\mu }s_{\mu }(x_{1},\ldots,x_{r}).}$$

If we have a finite linear combination $\varPhi =\sum\nolimits_{\lambda }c_{\lambda }H_{\lambda }$, then for $r \geq \max \{\ell (\lambda ): c_{\lambda }\neq 0\}$ we have that Φ(Id) corresponds to the symmetric function $\sum\nolimits_{\lambda }c_{\lambda }h_{\lambda }$. This is zero if and only if all c _λ  = 0. □ 

As in Sect. 2.4, let $\langle v,w\rangle =\delta _{v,w}$ define a scalar product on $\mathbb{Z}\mathcal{S}_{\infty }$. For a fixed r > 0 and u <  _r w, we define the quasisymmetric function

$$\displaystyle{ K_{[u,w]_{r}} =\sum _{\alpha }\langle H_{\alpha }(u),w\rangle M_{\alpha }. }$$

(16)

As before, since $H_{a}H_{b} = H_{b}H_{a}$, the function $K_{[u,w]_{r}}$ is in fact a symmetric function. As shown in [9, 10], we have the following theorem:

Theorem 4.

$$\displaystyle{K_{[u,w]_{r}} =\sum _{\alpha }\langle R_{\alpha }(u),w\rangle F_{\alpha } =\sum _{\mu }c_{u,v(\mu,r)}^{w}s_{\mu }\,,}$$

where $c_{u,v(\mu,r)}^{w}$ are defined in  (9) . Moreover for α a composition of n we have that $\langle R_{\alpha }(u),w\rangle$ counts the number of paths in the r-Bruhat order $\mathcal{S}_{\infty }$ from u to w of the form $\mathbf{u}_{a_{n}b_{n}}\cdots \mathbf{u}_{a_{2}b_{2}}\mathbf{u}_{a_{1}b_{1}}$ where $b_{i} > b_{i+1}$ if and only if i ∈ D(α).

Example 3.

Using the chains in (12) and Theorem 4 we can compute the quasisymmetric function associated to this interval and we get

$$\displaystyle{\begin{array}{rcl} K_{[142635,356124]_{3}} & =&F_{13} + F_{121} + F_{22} + F_{112} + F_{121} + F_{31} + F_{211} + F_{22} \\ & =&S_{31} + S_{22} + S_{211}.\end{array} }$$

Remark 4.

The monoid generated by the operators u _ab does not satisfy relations that resemble (6), hence we cannot use the work of Fomin and Greene to conclude that $K_{[u,w]_{r}}$ is symmetric nor deduce a combinatorial rule for constructing the coefficient $c_{u,v(\mu,r)}^{w}$ in $K_{[u,w]_{r}}$. In fact all known attempts to give such a rule so far have failed. In the next section we outline how it is shown combinatorially in [1] that the coefficients are positive (without giving an explicit rule in all cases) using techniques developed by [2].

3.3 Combinatorial Proof of Positivity of $c_{u,v(\mu,r)}^{w}$

Let Comp _n denote the set of compositions of n. Given a finite family of objects $\mathcal{C}$ and a function $\alpha: \mathcal{C}\rightarrow Comp_{n}$ we can define a quasisymmetric function as follows

$$\displaystyle{K_{\mathcal{C}} =\sum _{x\in \mathcal{C}}F_{\alpha (x)}\,.}$$

The function $K_{[u,w]_{r}}$ of Theorem 4 is clearly of this form. In that case $\mathcal{C}$ is the set of saturated chains $\mathbf{u}_{a_{n}b_{n}}\cdots \mathbf{u}_{a_{2}b_{2}}\mathbf{u}_{a_{1}b_{1}}$ in the interval [u, w] _r and $\alpha =\alpha (\mathbf{u}_{a_{n}b_{n}}\cdots \mathbf{u}_{a_{2}b_{2}}\mathbf{u}_{a_{1}b_{1}})$ is the unique composition where $b_{i} > b_{i+1}$ if and only if i ∈ D(α).

Assaf [2] develops new combinatorial techniques to show that quasisymmetric functions of the form $K_{\mathcal{C}}$ are symmetric with a positive expansion in terms of Schur functions. To this end one must construct partially commuting involutions $\phi _{i}: \mathcal{C}\rightarrow \mathcal{C}$ for 1 < i < n satisfying a set of axioms. When $\mathcal{C}$ consists of words (or saturated chains), the involutions ϕ _i can be viewed as an analogue of the dual Knuth relations. In [1] we have defined such involution ϕ _i on the set of chains of [u, w] _r . Given a chain $x = \mathbf{u}_{a_{n}b_{n}}\cdots \mathbf{u}_{a_{2}b_{2}}\mathbf{u}_{a_{1}b_{1}}$, the involution ϕ _i will only affect the three entries $\mathbf{u}_{a_{i+1}b_{i+1}}\mathbf{u}_{a_{i}b_{i}}\mathbf{u}_{a_{i-1}b_{i-1}}$. We set ϕ _i (x) = x if and only if $\big\vert D(\alpha (x)) \cap \{ i - 1,i\}\big\vert \neq 1$. When $\big\vert D(\alpha (x)) \cap \{ i - 1,i\}\big\vert = 1$, the entries $\mathbf{u}_{a_{i+1}b_{i+1}}\mathbf{u}_{a_{i}b_{i}}\mathbf{u}_{a_{i-1}b_{i-1}}$ of x can be one of twelve cases. To define ϕ _i , we match the twelves cases as follows:

• (A) $\mathbf{u}_{\gamma c}\mathbf{u}_{\alpha a}\mathbf{u}_{\beta b} \leftrightarrow \mathbf{u}_{\alpha a}\mathbf{u}_{\gamma c}\mathbf{u}_{\beta b}$,

  $\mathbf{u}_{\beta b}\mathbf{u}_{\alpha a}\mathbf{u}_{\gamma c} \leftrightarrow \mathbf{u}_{\beta b}\mathbf{u}_{\gamma c}\mathbf{u}_{\alpha a}$, if $\{a,\alpha \}\cap \{c,\gamma \}= \varnothing$ and a < b < c,

• (B) $\mathbf{u}_{bc}\mathbf{u}_{ab}\mathbf{u}_{bd} \leftrightarrow \mathbf{u}_{ac}\mathbf{u}_{cd}\mathbf{u}_{bc}$,

  $\mathbf{u}_{bd}\mathbf{u}_{ab}\mathbf{u}_{bc} \leftrightarrow \mathbf{u}_{bc}\mathbf{u}_{cd}\mathbf{u}_{ac}$, if a < b < c < d,

• (C) $\mathbf{u}_{\beta b}\mathbf{u}_{\alpha a}\mathbf{u}_{ac} \leftrightarrow \mathbf{u}_{\alpha a}\mathbf{u}_{ac}\mathbf{u}_{\beta b}$,

  $\mathbf{u}_{ac}\mathbf{u}_{\alpha a}\mathbf{u}_{\beta b} \leftrightarrow \mathbf{u}_{\beta b}\mathbf{u}_{ac}\mathbf{u}_{\alpha a}$, if $\{\alpha,a,c\} \cap \{ b,\beta \}= \varnothing$ and a < b < c.

This matching is completely determined by the relations in (11). We see them as the analogue of the dual Knuth relations for this problem. Instead of using the relation (11) one can investigate the free monoid spanned by the u _ab modulo the dual Knuth relations above. Under certain axioms described in [1, 2], the component of the equivalent classes of these relations will be combinatorially symmetric and Schur positive. To our knowledge this is the best we can do so far, and is the best generalization of the work of Fomin and Greene.

4 k-Schur Functions

In this section we present a monoid of operators for which much less is known but that is expected to behave as in Sect. 3. This monoid is related to the so-called k-Schur functions [18, 21]. This time we will define operators on the Bruhat order of the k-affine symmetric group. The operators we define will be related to the multiplication of dual k-Schur functions. There are still many open questions in this case, but we will present our program and we believe that it can be solved in the same spirit as in Sect. 3. There is another order one may consider on the k-affine symmetric group, namely the weak order. The operators corresponding to the weak order are related to the multiplication of k-Schur functions, but we will discuss only briefly the difficulties which arise in this situation.

The k-Schur functions were originally defined combinatorially in terms of k-atoms, and conjecturally provide a positive decomposition of the Macdonald polynomials [21]. These functions have several definitions and it is conjectural that they are equivalent (see [18]). In this paper we will adopt the definition given by the k-Pieri rule and k-tableaux (see [18, 20]) since this gives us a relation with the homology and cohomology of the affine grassmannians and we therefore get positivity in their structure constants.

Different objects index k-Schur functions: 0-grassmannian in k-affine permutations, k + 1-cores, k-bounded partitions. Originally (as in [21]), k-Schur functions were indexed by k-bounded partitions $\lambda = (\lambda _{1},\lambda _{2},\ldots,\lambda _{\ell})$ where λ ₁ ≤ k. These partitions are in bijection with k + 1-cores (see [19]). By definition, k + 1-cores are integer partitions $\mu = (\mu _{1},\mu _{2},\ldots,\mu _{m})$ with no hook of length k + 1. To close the loop, in [13] it is shown that k + 1-cores are in bijection with 0−grassmannian permutations in the k-affine symmetric group (see [6, 18]).

4.1 Affine Symmetric Group

The k-affine symmetric group $W =\tilde{ A}_{k}$ is generated by reflections s _i for i ∈ { 0, 1, …, k}, subject to the relations:

$$\displaystyle{s_{i}^{2} = 1;\qquad s_{ i}s_{i+1}s_{i} = s_{i+1}s_{i}s_{i+1};\qquad s_{i}s_{j} = s_{j}s_{i}\ \text{ if }i - j\neq \pm 1,}$$

where i − j and i + 1 are understood to be taken modulo k + 1. Let w ∈ W and denote its length by ℓ(w), given by the minimal number of generators needed to write a reduced expression for w. We let W ₀ denote the parabolic subgroup obtained from W by removing the generator s ₀. This is naturally isomorphic to the symmetric group S _k+1. For more details on the affine symmetric group see [13].

Let u ∈ W be an affine permutation. This permutation can be represented using window notation. That is, u can be seen as a bijection from $\mathbb{Z}$ to $\mathbb{Z}$, so that if u _i is the image of the integer i under u, then it can be seen as a sequence:

$$\displaystyle{u = \cdots \vert u_{-k}\;\cdots \;u_{-1}\;u_{0}\mathop{\underbrace{ \vert u_{1}\;u_{2}\;\cdots \;u_{k+1}\vert }}\limits _{\text{main window}}u_{k+2}\;u_{k+3}\;\cdots \;u_{2k+2}\vert \cdots }$$

Moreover, u satisfies the property that $u_{i+k+1} = u_{i} + k + 1$ for all i, and the sum of the entries in the main window $u_{1} + u_{2} + \cdots + u_{k+1} ={ k + 2\choose 2}$. Notice that in view of the first property, u is completely determined by the entries in the main window. In this notation, the generator u = s _i is the permutation such that u _i+m(k+1) = i + 1 + m(k + 1) and $u_{i+1+m(k+1)} = i + m(k + 1)$ for all m, and u _j  = j for all other values. The multiplication uw of permutations u, w in W is the usual composition given by $(uw)_{i} = u_{w_{i}}$. In view of this, the parabolic subgroup W ₀ corresponds to the u ∈ W such that the numbers {1, 2, …, k + 1} appear in the main window.

Now, let W ⁰ denote the set of minimal length coset representatives of W∕W ₀. In this paper we take right coset representatives, although left coset representatives could be taken as well. The set of permutations in W ⁰ are the affine grassmannian permutations of W, or 0-grassmannians for short.

Definition 1.

The affine 0-grassmannians W ⁰ are the permutations u ∈ W such that the numbers 1, 2, …, k + 1 appear from left to right in the sequence u.

Example 4.

Let k = 4 and

$$\displaystyle{u = \cdot \cdot \cdot \vert \bar{3}\;\bar{2}\;1\;\bar{5}\;\bar{1}\mathop{\underbrace{\vert 2\;3\;6\;\bar{0}\;4\vert }}\limits _{\text{main window}}7\;8\;11\;5\;9\vert \cdot \cdot \cdot }$$

where $\bar{i}$ stands for − i. By convention we say that 0 is negative. This permutation u is 0-grassmannian and it corresponds to the 5-core μ = (4, 1, 1). The correspondence is easy to see from the window notation. We just need to read the sequence of entries of u, drawing a vertical step down for each negative entry, and an horizontal step right for each positive entry. The result is the diagram of μ:

4.2 k-Schur Functions and Weak Order

As previously mentioned, 0-grassmannian permutations index k-Schur functions, which we denote by $S_{u}^{(k)}$ for some u ∈ W ⁰.

Given u ∈ W, we say that $u \lessdot _{w}us_{i}$ is a cover for the weak order if $\ell(us_{i}) =\ell (u) + 1$. The weak order on W is the transitive closure of these covers. We can define operators

$$\displaystyle{ \begin{array}{rcl} \mathbf{s}_{i}: \ \mathbb{Z}W^{0} & \longrightarrow & \quad \mathbb{Z}W^{0}, \\ u\quad &\longmapsto &\ \ \left \{\begin{array}{ll} us_{i}&\mbox{ if }u \lessdot _{w}us_{i} \\ 0 &\mbox{ otherwise}\end{array} \right.\end{array} }$$

(17)

on the weak order of W restricted to W ⁰. The definition and multiplication of k-Schur functions is based on the operators s _i so it is worthwhile to study the monoid they generate. As we will see in Example 5 there are difficulties with the behavior of this case which make it very difficult at this point to understand its combinatorics. For this reason, we will quickly turn our attention to the dual k-Schur after Example 5.

The Pieri rule for k-Schur functions is described by certain chains in the weak order of W restricted to W ⁰. This result is given in [17, 18, 20]. A saturated chain $w = \mathbf{s}_{i_{m}}\cdots \mathbf{s}_{i_{2}}\mathbf{s}_{i_{1}}(u)$ in an interval [u, w] _w of the weak order restricted to W ⁰ gives us a sequence of labels $(i_{1},i_{2},\ldots,i_{m})$. We say that the sequence $(i_{1},i_{2},\ldots,i_{m})$ is cyclically increasing if $i_{1},i_{2},\ldots,i_{m}$ lies clockwise on a clock with hours 0, 1, …, k and if the $\min \big\{j: 0 \leq j \leq k;\ j\notin \{i_{1},i_{2},\ldots,i_{m}\}\big\}$ lies between i _m and i ₁. In particular we must have 1 ≤ m ≤ k. Now, to express the Pieri rule, we first remark that for 1 ≤ m ≤ k, the homogeneous symmetric function h _m corresponds to the k-Schur function $S_{v(m)}^{(k)}$ where v(m) is a 0-grassmannian whose main window is given by $\vert 2\;\cdots \;m\;\bar{0}\;m + 1\;\cdots \;k\;k + 2\vert$. Then, the multiplication of a k-Schur function $S_{u}^{(k)}$ by a homogeneous symmetric function h _m is given by

$$\displaystyle{ S_{u}^{(k)}h_{ m}:=\ \sum _{{ (i_{1},i_{2},\ldots,i_{m})\text{ cyclically increasing } \atop \mathbf{s}_{i_{m}}\cdots \mathbf{s}_{i_{2}}\mathbf{s}_{i_{1}}(u)\neq 0} }S_{\mathbf{s}_{i_{ m}}\cdots \mathbf{s}_{i_{ 2}}\mathbf{s}_{i_{ 1}}(u)}^{(k)}. }$$

(18)

Iterating Eq. (18) one can easily see that

$$\displaystyle{ h_{\lambda } =\ \sum _{u}\mathrm{K}_{\lambda,u}S_{u}^{(k)} }$$

(19)

is a triangular relation [20]. One way to define k-Schur functions is to start with Eq. (18) as a rule, and define them as follows.

Definition 2.

The k-Schur functions are the unique symmetric functions $S_{u}^{(k)}$ obtained by inverting the matrix $[\mathrm{K}_{\lambda,u}]$ obtained from (19) above.

It is clear that we can define a Pieri operator

$$\displaystyle{H_{m} =\sum _{(i_{ 1},i_{2},\ldots,i_{m})\text{ cyclically increasing }}\mathbf{s}_{i_{m}}\cdots \mathbf{s}_{i_{2}}\mathbf{s}_{i_{1}}\,,}$$

for 1 ≤ m ≤ k. Again we can show that $H_{a}H_{b} = H_{b}H_{a}$ and define $K_{[u,w]_{w}}$ using the original definition. The example below shows the main problems we have with this function.

Example 5.

Let k = 2 and $u = \vert \bar{0}\;2\;4\vert$. We consider the interval [u, w] _w in the weak order restricted to W ⁰, where $w = \vert \bar{3}\;4\;5\vert$. This interval is a single chain $w = \mathbf{s}_{0}\mathbf{s}_{2}\mathbf{s}_{1}(u)$. In this case, we remark that

$$\displaystyle{\langle H_{1}H_{1}H_{1}(u),w\rangle =\langle H_{1}H_{2}(u),w\rangle =\langle H_{2}H_{1}(u),w\rangle = 1}$$

are the only nonzero entries in $K_{[u,w]_{w}}$ and we get

$$\displaystyle{\begin{array}{rcl} K_{[u,w]_{w}} & =&M_{111} + M_{21} + M_{12} \\ & =&F_{12} + F_{21} - F_{111} \\ & =&S_{21} - S_{111}. \end{array} }$$

This small example shows some of the behavior of the (quasi)symmetric function $K_{[u,w]_{w}}$ for the weak order of W. In general, it is neither F-positive nor Schur positive. Although, these functions contain some information about the structure constants, it is not enough to fully understand them combinatorially. In particular, these functions lack some of the properties needed to use the theory developed in [2]. The functions $K_{[u,w]_{w}}$ were first defined in [10, 26] but the combinatorial expansion in terms of Schur functions is still open.

4.3 Dual k-Schur Functions

Recall that $Sym = \mathbb{Z}[h_{1},h_{2},\ldots ]$ is the Hopf algebra of symmetric functions. The space of k-Schur functions Sym _(k) can be seen as a subalgebra of Sym spanned by $\mathbb{Z}[h_{1},h_{2},\ldots,h_{k}]$. In fact, it is a Hopf subalgebra whose comultiplication defined in the homogeneous basis is given by

$$\displaystyle{\varDelta (h_{m}) =\sum _{ i=0}^{m}h_{ i} \otimes h_{m-i}}$$

and extended algebraically. The degree map is given by $\deg (h_{m}) = m$. The space Sym is a self dual Hopf algebra where the Schur functions S _λ form a self dual basis under the pairing $\langle h_{\lambda },m_{\mu }\rangle =\delta _{\lambda,\mu }$.

The map dual to the inclusion $Sym_{(k)}\hookrightarrow Sym$, is a projection $Sym \rightarrow \!\!\!\!\!\rightarrow Sym^{(k)}$, where $Sym^{(k)} = Sym_{(k)}^{{\ast}}$ is the graded dual of $Sym_{(k)}$. It can be checked that the kernel of this projection is the linear span of $\{m_{\lambda }:\lambda _{1} > k\}$, hence

$$\displaystyle{Sym^{(k)}\ \mathop{\cong}\ Sym\big/\langle m_{\lambda }:\lambda _{ 1} > k\rangle \,.}$$

The graded dual basis to $S_{u}^{(k)}$ will be denoted here by $\mathfrak{S}_{u}^{(k)} = S_{u}^{(k){\ast}}$ which are also known as the affine Stanley symmetric functions. The multiplication of the dual k-Schur $\mathfrak{S}_{u}^{(k)}$ is described in terms of operator on the affine Bruhat order, as we will see in the next section.

4.4 Affine Bruhat Order

For b − a ≤ k, let t _a, b be the transposition in W such that for all $m \in \mathbb{Z}$, it transposes a + m(k + 1) and b + m(k + 1). The affine Bruhat order is given by its covering relation. Namely, for u ∈ W, we have $u \lessdot ut_{a,b}$ is a cover in the affine Bruhat order if $\ell(ut_{a,b}) =\ell (u) + 1$.

Proposition 5 (see [13]).

For u ∈ W and b − a ≤ k, we have that $u \lessdot ut_{a,b}$ is a cover in the Bruhat order if and only if u(a) < u(b) and for all a < i < b we have u(i) < u(a) or u(i) > u(b).

Notice that if $a^{{\prime}} = a + m(k + 1)$ and b ^′ = b + m(k + 1) then $t_{a^{{\prime}},b^{{\prime}}} = t_{a,b}$, therefore, many different choices of a and b give the same covering as long as they satisfy the conditions of the proposition. The affine 0-Bruhat order arises as a suborder of the Bruhat order. We define it by its covers. For u ∈ W, we get a covering $u \lessdot _{0}ut_{a,b}$ if there exists a transposition t _a, b satisfying Proposition 5 and also u(a) ≤ 0 < u(b). As previously noted, a transposition $t_{a^{{\prime}},b^{{\prime}}}$ satisfying the same conditions as t _a, b gives the same affine Bruhat covering relation as long as $a^{{\prime}}\equiv a$, $b^{{\prime}}\equiv b$ modulo k + 1. In view of this, we introduce operators on the affine 0-Bruhat order restricted to W ⁰. To keep track of the distinct a, b such that $u \lessdot _{0}ut_{a,b}$ is an affine 0-Bruhat covering for a given u. For any b − a ≤ k, let

$$\displaystyle{ \begin{array}{rcl} \mathbf{t}_{ab}: \ \mathbb{Z}W^{0} & \longrightarrow & \quad \mathbb{Z}W^{0}, \\ u\quad &\longmapsto &\ \ \left \{\begin{array}{ll} ut_{a,b}&\mbox{ if }u \lessdot ut_{a,b}\mbox{ and }u(a) \leq 0 < u(b) \\ 0 &\mbox{ otherwise.} \end{array} \right. \end{array} }$$

(20)

We write these operators as acting on the right: u t _ab . Remark now that if u t _ab ≠ 0, then $u\mathbf{t}_{ab} = u\mathbf{t}_{a^{{\prime}},b^{{\prime}}}\neq 0$ for only finitely many values of m with a ^′ = a + m(k + 1) and b ^′ = b + m(k + 1). To see this, it is enough to notice that there exists m such that u(a + m(k + 1)) ≥ 0 and m ^′ such that u(b + m ^′(k + 1)) < 0.

Example 6.

In Fig. 1 below, we have the interval $[\vert \bar{6}\,8\,3\,\bar{1}\,4\,13\vert,\vert 8\,\bar{6}\,\bar{2}\,9\,13\,\bar{1}\vert ]$ in the affine 0-Bruhat graph: In this example we see that there are three operators from $u = \vert \bar{6}\,8\,3\,\bar{1}\,4\,13\vert$ to $w = \vert 8\,\bar{6}\,3\,\bar{1}\,13\,4\vert$. We have $u\mathbf{t}_{\bar{5}\bar{4}} = u\mathbf{t}_{12} = u\mathbf{t}_{78} = w$ labeled by $\bar{4},2,8$, respectively. All other operators evaluate to 0. For example $u\mathbf{t}_{\overline{11}\,\overline{10}} = 0$.

When restricted to 0-grassmannian permutations, the affine 0-Bruhat order behaves well, as shown in the next lemma whose proof (for left coset) can be consulted in [18, Prop. 2.6]. Therefore, our operators t _ab are well defined.

Lemma 4.

If u t _ab = w and u ∈ W ⁰, then we have that w ∈ W ⁰ .

Fig. 1

The interval $[\vert \bar{6}\,8\,3\,\bar{1}\,4\,13\vert,\vert 8\,\bar{6}\,\bar{2}\,9\,13\,\bar{1}\vert ]$

At this point, there are a few questions we would like to answer regarding the monoid $\mathcal{M}\langle \mathbf{t}_{ab}\rangle$ generated by the operators t _ab . The main questions are:

• (I) Can we describe all the relations satisfied by the operators t _ab (as in Proposition 3)?

• (II) Is there a combinatorial object that characterizes all the elements of $\mathcal{M}\langle \mathbf{t}_{ab}\rangle$ (as in Corollary 1)?

• (III) Can we define Pieri operators H _k related to the multiplication $\mathfrak{S}_{u}h_{m}$?

• (IV) Can we find a good expression for H _k as in Proposition 4?

• (V) Is the algebra spanned by the H _k isomorphic Sym _(k) (as in Theorem 1)?

• (VI) What is the analogue of Theorem 4?

• (VII) Can we show combinatorially the positivity of the structure constants in the product $\mathfrak{S}_{u}h_{m}$ as done in Sect. 3.3?

We have some partial answers to question (I) that we will discuss next. Questions (II) and (IV) seem very difficult at this point and are still open. Questions (III), (V) and (VI) are done in the literature (see [5, 17]), although (V) is not stated as it is here. We are in the process of solving question (VII); this involves analyzing 3, 4, 5, and 6-tuples of the operators t _ab . The number of possibilities are much greater than the situation in Sect. 3.3 and will be available in subsequent work.

4.5 Relations of the Operators t _ab

The purpose of this section is to understand some of the relations satisfied by the t _ab operators restricted to W ⁰. Our main goal at this point is not to understand all the defining relations, but to find enough that will allow us to answer question (VII). Answering question (II) is a very worthwhile project for future work. Most of the relations we present here were given and proven in [5]. The relations depend on the following data: for t _ab we need to consider $a,b,\overline{a},\overline{b}$ where $\overline{a}$ and $\overline{b}$ are the residue modulo k + 1 of a and b respectively. Remark that $\overline{a}\neq \overline{b}$ since b − a < k + 1. Let u ∈ W ⁰. Lemma 4 implies that, if non-zero, u t _ab and $u\mathbf{t}_{ab}\mathbf{t}_{cd}$ are both in W ⁰. The different relations satisfied by the operators t _ab and t _cd depend on the relation among $\overline{a},\overline{b},\overline{c},\overline{d}$. For this reason it is useful to visualize these operators as follows.

Above the permutation u, the operator t _ab is represented by drawing a bold line connecting positions a, b and repeating this pattern to the left and to the right in all positions congruent to a, b modulo k + 1. Next we apply t _cd to the resulting permutation, drawing a bold line connecting positions c, d and repeating that pattern modulo k + 1. The importance of visualizing not only the bold line but the dotted ones as well, relies on the fact that even if in the diagram, the line representing t _ab does not intersect the line representing t _cd , their “virtual” copies (or dotted copies) might intersect and this will determine the commutation relation satisfied by these operators. Therefore, it will be important to consider the pattern produced by these two operators in the main window.

With these definitions in mind we present some of the relations satisfied by the t operators restricted to W ⁰ (there are less relations if we consider all of W).

(A) :

$\mathbf{t}_{ab}\mathbf{t}_{cd} \equiv \mathbf{t}_{cd}\mathbf{t}_{ab}$ if $\overline{a},\overline{b},\overline{c},\overline{d}$ are distinct.

(B1) :

$\mathbf{t}_{ab}\mathbf{t}_{cd} \equiv \mathbf{t}_{cd}\mathbf{t}_{ab} \equiv 0$ if ($a \leq c < b \leq d$) or (b = c and d − a > k + 1).

(B2) :

$\mathbf{t}_{ab}\mathbf{t}_{cd} \equiv 0$ if ($\overline{a} = \overline{c}$ and b ≤ d) or ($\overline{b} = \overline{d}$ and c ≤ a).

(B3) :

$\mathbf{t}_{ab}\mathbf{t}_{cd} \equiv 0$ if ($\overline{b} = \overline{c}$ or $\overline{a} = \overline{d}$) and (d − c + b − a > k + 1).

There are more possible zeros than what we present in (B). If the numbers a, b, c, d are not distinct, then we must have b = c or d = a. If b = c, then d − a ≤ k + 1 in view of (B). Similarly if d = a then b − c ≤ k + 1.

(C) :

$\mathbf{t}_{ab}\mathbf{t}_{bd} = \mathbf{t}_{ab}\mathbf{t}_{b-k-1,a}$ if d − a = k + 1,

if d − a < k + 1 then there is no relation between $\mathbf{t}_{ab}\mathbf{t}_{bd}$ and $\mathbf{t}_{bd}\mathbf{t}_{ab}$. Now we look at the cases $\mathbf{t}_{ab}\mathbf{t}_{cd}$ where a, b, c, d are distinct but some equalities exists between $\overline{a},\overline{b}$ and $\overline{c},\overline{d}$. By symmetry of the relation we will assume that b < d, which (excluding (B)) implies that a < b < c < d.

(D) :

$\mathbf{t}_{ab}\mathbf{t}_{cd} = \mathbf{t}_{d-k-1,c}\mathbf{t}_{b-k-1,a}$ if $\overline{b} = \overline{c}$,  $\overline{d} = \overline{a}$ and (b − a) + (d − c) = k + 1.

All the relations above are local. This means that if $\mathbf{t}_{ab}\mathbf{t}_{cd} = \mathbf{t}_{c^{{\prime}}d^{{\prime}}}\mathbf{t}_{a^{{\prime}}b^{{\prime}}}$, then | a ^′− a | , | b ^′− b | , | c ^′− c | and | d ^′− d | are strictly less than k + 1. For example, in (D) we have | b − k − 1 − a | , | a − b | , | d − k − 1 − c | and | c − d | which are strictly less than k + 1.

Remark 5.

The relations we care about in this paper and its sequel are all local. There are some relations that are not local:

$$\displaystyle{\mathbf{t}_{ab}\mathbf{t}_{cd} = \mathbf{t}_{a-k-1,b-k-1}\mathbf{t}_{cd} = \mathbf{t}_{a+k+1,b+k+1}\mathbf{t}_{cd},}$$

if c < a < b < d. The full description of the relations of the operators t is rather complicated. It would take too much space here and are not all understood.

We now consider some more relations of length three:

(E1) :

$\mathbf{t}_{bc}\mathbf{t}_{cd}\mathbf{t}_{ac} \equiv \mathbf{t}_{bd}\mathbf{t}_{ab}\mathbf{t}_{bc}$ if a < b < c < d,

(E2) :

$\mathbf{t}_{ac}\mathbf{t}_{cd}\mathbf{t}_{bc} \equiv \mathbf{t}_{bc}\mathbf{t}_{ab}\mathbf{t}_{bd}$ if a < b < c < d.

additionally we have

(F) :

$\mathbf{t}_{bc}\mathbf{t}_{ab}\mathbf{t}_{bc} \equiv \mathbf{t}_{ab}\mathbf{t}_{bc}\mathbf{t}_{ab} \equiv \ \mathbf{0}$ if a < b < c and c − a < k + 1.

Remark 6.

If we fix a permutation u we can derive more relations of length 2. Let r =  | b − a | + | d − c | :

• (X1) $u\mathbf{t}_{ab}\mathbf{t}_{cd} = u\mathbf{t}_{d,c+r}\mathbf{t}_{b-r,a}$ ​if r < k + 1, $\overline{d} = \overline{a}$, u(c) ≤ 0 and u(d) ≤ 0,

• (X2) $u\mathbf{t}_{ab}\mathbf{t}_{cd} = u\mathbf{t}_{cd}\mathbf{t}_{b-r,b}$ if r < k + 1, $\overline{d} = \overline{a}$ and u(d) > 0,

• (X3) $u\mathbf{t}_{ab}\mathbf{t}_{cd} = u\mathbf{t}_{d-r,d}\mathbf{t}_{ab}$ ​ ​if r < k + 1, $\overline{b} = \overline{c}$ and u(a + r) ≤ 0,

• (X4) $u\mathbf{t}_{ab}\mathbf{t}_{cd} = u\mathbf{t}_{d-r,c}\mathbf{t}_{b,a+r}$ ​if r < k + 1, $\overline{b} = \overline{c}$, u(b) > 0 and u(a + r) > 0,

• (X5) $u\mathbf{t}_{ab}\mathbf{t}_{cd} = u\mathbf{t}_{cd}\mathbf{t}_{a,b+c-d}$ ​if $\overline{b} = \overline{d}$, b − a > d − c and u(d − b + a) > 0,

• (X6) $u\mathbf{t}_{ab}\mathbf{t}_{cd} = u\mathbf{t}_{c,d-b+a}\mathbf{t}_{a,b}$ ​ ​​if $\overline{b} = \overline{d}$, b − a < d − c and u(a) ≤ 0.

In the (X) relations, the conditions we impose on u are minimal to assure that both sides of the equality are non-zero. These conditions are not given by the definition of the operators t _ab . For example in (X1), the left hand side is non-zero regardless of the value of u(d) but to guarantee that the right hand side is non-zero, we must have u(d) ≤ 0. This shows that as operators $\mathbf{t}_{ab}\mathbf{t}_{cd}\neq \mathbf{t}_{d,c+r}\mathbf{t}_{b-r,a}$.

4.6 Multiplication of Dual k-Schur

For dual k-Schur functions $\mathfrak{S}_{u}^{(k)}$, the analogue of the Pieri formula (18) is given by

$$\displaystyle{ \mathfrak{S}_{u}^{(k)}h_{ m}:=\ \sum _{{ u\mathbf{t}_{a_{1}b_{1}}\cdots \mathbf{t}_{a_{m}b_{m}}\neq 0 \atop b_{1}<b_{2}<\cdots <b_{m}} }\mathfrak{S}_{u\mathbf{t}_{a_{ 1}b_{1}}\cdots \mathbf{t}_{a_{m}b_{m}}}^{(k)}, }$$

(21)

where the sum is over all increasing paths $b_{1} < b_{2} < \cdots < b_{m}$ starting at u [18]. Since the Pieri formula is encoded by increasing composition of operators in the affine 0-Bruhat order restricted to W ⁰, we can define Pieri operators similar to Eq. (14) using increasing composition of operators t _ab . We can then define a Pieri operator

$$\displaystyle{ H_{m} =\sum _{{ b_{1}<b_{2}<\cdots <b_{k} \atop a_{i}<b_{i}} }\mathbf{t}_{a_{1}b_{1}}\mathbf{t}_{a_{2}b_{2}}\cdots \mathbf{t}_{a_{m}b_{m}}. }$$

(22)

Many terms in this sum may be zero. At this point we do not have a good description of the terms that survive or how to express the non-zero terms as in Proposition 4. The definition of the operator H _m in this case allows us to see that

By definition of H _k and Eq. (21), we have

$$\displaystyle{ \begin{array}{lr} wH_{b}H_{a} =\sum\nolimits_{\nu }d_{w,(a,b)}^{u}u& \\ \qquad \qquad \;\Longleftrightarrow\; &\mathfrak{S}_{w}h_{a}h_{b} =\sum\nolimits_{u}d_{w,(a,b)}^{u}\mathfrak{S}_{u}\,.\\ \end{array} }$$

(23)

In particular, for all w we have $H_{b}H_{a}(w) = H_{a}H_{b}(w)$ since $h_{a}h_{b} = h_{b}h_{a}$.

Theorem 5.

The algebra $\mathbf{B}\langle H_{k}\rangle$ spanned by $\{H_{1},H_{2},\ldots,H_{k}\}$ as operators on the k-affine Bruhat order restricted to W ⁰ is isomorphic to Sym _(k) .

Proof.

As we multiply $H_{m}H_{n}$ and $H_{n}H_{m}$, some terms go to zero and others survive. The terms that survive in $H_{m}H_{m}$ are of the form

$$\displaystyle{\omega = \mathbf{t}_{a_{1}b_{1}}\mathbf{t}_{a_{2}b_{2}}\cdots \mathbf{t}_{a_{m}b_{m}}\mathbf{t}_{c_{1}d_{1}}\mathbf{t}_{c_{2}c_{2}}\cdots \mathbf{t}_{a_{n}b_{n}}.}$$

where $b_{1} < b_{2} <\ldots < b_{k}$ and $d_{1} < d_{2} <\ldots < d_{n}$. Let $d_{(a,b)}^{\omega }$ be the coefficient of ω in $H_{m}H_{n}$. Since ω ≠ 0, there is a u ∈ W ⁰ such that uω = v ≠ 0. As before, for all ω, we have

$$\displaystyle{d_{(a,b)}^{\omega } = \mbox{ Coeff of $v$ in $H_{ a}H_{b}(u)$} = \mbox{ Coeff of $v$ in $H_{b}H_{a}(u)$} = d_{(b,a)}^{\omega }.}$$

Hence $H_{a}H_{b} = H_{b}H_{a}$.

The algebra $\mathbf{B}\langle H_{k}\rangle$ is clearly spanned by $H_{\lambda } = H_{\lambda _{1}}\cdots H_{\lambda _{\ell}}$ where λ runs over all partitions. Again, we only need to show that the H _λ ’s are linearly independent. Using the definition of the H _m , we have that $\mathrm{Id}H_{\lambda } =\sum\nolimits_{\mu }d_{\lambda }^{\mu }v_{\mu }$ where v _μ is the unique 0-grassmannian permutation with shape μ and the $d_{\lambda }^{\mu }$ satisfy

$$\displaystyle{h_{\lambda }(x_{1},\ldots,x_{r}) =\sum _{\mu }d_{\lambda }^{\mu }s_{\mu }(x_{1},\ldots,x_{r}).}$$

As we have seen in the proof of Theorem 3 this implies the linear independence of the H _λ . □ 

As in Sect. 2.4, let $\langle v,w\rangle =\delta _{v,w}$ define a scalar product on $\mathbb{Z}W^{0}$. For a u < w in the 0-Bruhat order, we define the quasisymmetric function

$$\displaystyle{ K_{[u,w]} =\sum _{\alpha }\langle uH_{\alpha },w\rangle M_{\alpha }. }$$

(24)

Again, since $H_{a}H_{b} = H_{b}H_{a}$, the function K _[u, w] is in fact a symmetric function. As shown in [5, 10]

Theorem 6.

$$\displaystyle{K_{[u,w]} =\sum _{\alpha }\langle uR_{\alpha },w\rangle F_{\alpha } =\sum _{\mu }c_{u,\mu }^{w}s_{\mu }\,,}$$

where $c_{u,\mu }^{w}$ are defined by

$$\displaystyle{\mathfrak{S}_{u}^{(k)}s_{\mu } =\sum _{ w}c_{u,\mu }^{w}\mathfrak{S}_{ w}^{(k)}\,.}$$

Moreover for α a composition of n, we have that $\langle uR_{\alpha },w\rangle$ count the number of compositions $\omega = \mathbf{t}_{a_{1}b_{2}}\mathbf{t}_{a_{2}b_{2}}\cdots \mathbf{t}_{a_{m}b_{m}}$ such that uω = w and $b_{i} > b_{i+1}$ if and only if i ∈ D(α).

Example 7.

Considering the interval $[u,w] = [\vert \bar{6}\,8\,3\,\bar{1}\,4\,13\vert,\vert 8\,\bar{6}\,\bar{2}\,9\,13\,\bar{1}\vert ]$ from Example 6. The total number of composition of operators is 240. In this case

$$\displaystyle{K_{[u,w]} = 9F_{1111} +30F_{112} +51F_{121} +30F_{13} +30F_{211} +51F_{22} +30F_{31} +9F_{4}}$$

is symmetric and the expansion in term of Schur functions is positive

$$\displaystyle{K_{[u,w]} = 9S_{4} + 30S_{31} + 21S_{22} + 30S_{211} + 9S_{1111}\,.}$$

4.7 Comments on the Combinatorial Proof of the Positivity of $c_{u,\mu}^w$

If one considers an interval [u, w] of rank 3 and computes K _[u, w], then by Theorem 24 the coefficient of F ₂₁ and F ₁₂ must be the same in K _[u, w]. This means that every time we have a descent followed by an ascent in a chain, we must have another chain with an ascent followed by a descent. This should be reflected in relations like (X) and could depend on u. To achieve a result similar to [1] for K _[u, w], one needs first to build a full set of relations of length 3 that pairs every ascent-descent type to a descent-ascent. This cannot be done independently from u. The purpose of this will be to define Dual-Knuth operations on the maximal chains in intervals [u, w]n in order to construct dual graphs as in [2].

We give here a partial list of the relations of length 3 that would be the analogue for dual k-Schur of (A)–(B)–(C) in Sect. 3.3. The complete full list of 3-relations needed is too long for this survey. In future work, we will need to show that the corresponding ϕ _i n defined by those relations satisfy the axioms of [2]. This is a long analysis that will appear in subsequent work. This will show that the monoid defined by the t _ab n behaves like the monoid of Sect. 3, even if it does not satisfy the Fomin and Greene’s hypothesis. This shows that these monoids are worthwhile to investigate.

We have already listed some of the relations satisfied by triplets of operators t _ab nn. Relations (A),(E1),(E2),(F) resemble the relations listed in (11). However, as noted before in the case of the operators t _ab , more relations can be derived making the analysis of relations much more complex than the u _ab n operators.

$$\displaystyle{ \begin{array}{clrclll} (1a)&& \mathbf{t}_{ab}\mathbf{t}_{cd}\mathbf{t}_{ec}& \equiv &\mathbf{t}_{ec}\mathbf{t}_{a,b-\vert c-e\vert }\mathbf{t}_{ed}, &&\mbox{ if $a < b < e < c < d$ and $\bar{a} =\bar{ d} <\bar{ e} <\bar{ b} =\bar{ c}$} \\ (1b) && \mathbf{t}_{ab}\mathbf{t}_{cd}\mathbf{t}_{ec}& \equiv &\mathbf{t}_{\bar{d}c}\mathbf{t}_{\bar{b}a}\mathbf{t}_{ec}, &&\mbox{ if $a < b < e < c < d$ and $\bar{a} =\bar{ d} =\bar{ e},\,\bar{b} =\bar{ c}$} \\ (1c) &&\mathbf{t}_{ab}\mathbf{t}_{cd}\mathbf{t}_{ef}& \equiv &\mathbf{t}_{ef}\mathbf{t}_{ab}\mathbf{t}_{cd}, &&\mbox{ if $a < b < c < e < f < d$ and $\bar{a} =\bar{ d},\,\bar{b} =\bar{ c}$} \\ (1d)&& \mathbf{t}_{ab}\mathbf{t}_{bc}\mathbf{t}_{db}& \equiv &\mathbf{t}_{db}\mathbf{t}_{ad}\mathbf{t}_{dc}, &&\mbox{ if $a < d < b < c$ and $\bar{a} =\bar{ c}$} \\ (1e) && \mathbf{t}_{ab}\mathbf{t}_{bc}\mathbf{t}_{db}& \equiv &\mathbf{t}_{ab}\mathbf{t}_{b-m,c-m}\mathbf{t}_{db},&&\mbox{ if $a = d < b < c$ and $\bar{a} =\bar{ c},\,m = k + 1$}\\ \end{array} }$$

In analogy with relations (X1)–(X6), let us list more relations that depend on the permutation u we apply them to. Let r =  | d − c | + | b − a |  < k + 1

$$\displaystyle{ \begin{array}{cllclll} (2a)&u\mathbf{t}_{ab}\mathbf{t}_{cd}\mathbf{t}_{ef} \equiv u\mathbf{t}_{d,c+s}\mathbf{t}_{b-s,a}\mathbf{t}_{ef}, &\mbox{ if $a < b < e < f \leq c < d$, $\bar{a} =\bar{ d},\,u(c) \leq 0,$} \\ & &\qquad u(d) \leq 0 \\ (2b) &u\mathbf{t}_{ab}\mathbf{t}_{cd}\mathbf{t}_{ef} \equiv u\mathbf{t}_{cd}\mathbf{t}_{b-r,b}\mathbf{t}_{ef}, &\mbox{ if $a < b < e < f \leq c < d$, $\bar{a} =\bar{ d},\,u(d) >\ 0$} \\ (3a)&u\mathbf{t}_{ab}\mathbf{t}_{cd}\mathbf{t}_{ef} \equiv u\mathbf{t}_{d-r,c}\mathbf{t}_{b,a+r}\mathbf{t}_{ef}, &\mbox{ if $a < b < e < f \leq c < d$,$\bar{b} =\bar{ c}$, $\bar{e} \geq \bar{ d},$} \\ & &\qquad u(a + r) >\ u(b) > 0 \\ (3b) &u\mathbf{t}_{ab}\mathbf{t}_{cd}\mathbf{t}_{ef} \equiv u\mathbf{t}_{d-r,d}\mathbf{t}_{ab}\mathbf{t}_{ef}, &\mbox{ if $a < b < e < f \leq c < d$, $\bar{b} =\bar{ c}$,\, $\bar{e} \geq \bar{ d},$} \\ & &\qquad u(a + r) \leq 0 \\ (4a)&u\mathbf{t}_{ab}\mathbf{t}_{cd}\mathbf{t}_{eb} \equiv u\mathbf{t}_{eb}\mathbf{t}_{ae}\mathbf{t}_{c-\vert b-e\vert,d}, &\mbox{ if $a < e < b < c < d$, $\bar{b} =\bar{ c},\bar{e} >\bar{ a},$} \\ & &\qquad u(a + r) >\ u(b) > 0 \\ (4b) &u\mathbf{t}_{eb}\mathbf{t}_{ae}\mathbf{t}_{c-\vert b-e\vert,d} \equiv u\mathbf{t}_{eb}\mathbf{t}_{d-r,d}\mathbf{t}_{ab},&\mbox{ if $a < e < b < c < d$, $\bar{b} =\bar{ c},\bar{e} >\bar{ a},$} \\ & &\qquad u(a + r) \leq 0\\ \end{array} }$$

If the reader represents these relations as a system of bars, they can be interpreted as exchanging an ascent-descent by a descent-ascent. As an example, putting b ^′ = b − | c − e | in relation (1a) we can represent it graphically as

Next we list more ascent-descent relations equivalent to descent-ascent. This is not an exhaustive list but it gives a good sense of the behaviour of these operators.

$$\displaystyle{ \begin{array}{clrclll} (6a)&&u\mathbf{t}_{ea}\mathbf{t}_{ab}\mathbf{t}_{cd}& \equiv &u\mathbf{t}_{eb}\mathbf{t}_{c,d-\vert a-e\vert }\mathbf{t}_{ea},&&\mbox{ if $c < d < e < a < b$, $\bar{c} <\bar{ e},\,\bar{a} =\bar{ d},$} \\ && & & &&\qquad u(b - r) \leq 0 \\ (6b) &&u\mathbf{t}_{ea}\mathbf{t}_{ab}\mathbf{t}_{cd}& \equiv &u\mathbf{t}_{eb}\mathbf{t}_{c,c+r}\mathbf{t}_{ab}, &&\mbox{ if $c < d < e < a < b$, $\bar{c} \leq e,\,\bar{a} =\bar{ d},$} \\ && & & &&\qquad u(b - r) >\ 0 \\ (6c) &&u\mathbf{t}_{ea}\mathbf{t}_{ab}\mathbf{t}_{cd}& \equiv &u\mathbf{t}_{eb}\mathbf{t}_{d,c+r}\mathbf{t}_{b-r,a}, &&\mbox{ if $c < d < e < a < b$, $\bar{c} >\bar{ e},\,\bar{a} =\bar{ d},$} \\ && & & &&\qquad u(b - r) \leq 0 \\ (6d)&&u\mathbf{t}_{ea}\mathbf{t}_{ab}\mathbf{t}_{cd}& \equiv &u\mathbf{t}_{eb}\mathbf{t}_{d-r,c}\mathbf{t}_{b,a+r}, &&\mbox{ if $c < d < e < a < b$, $\bar{c}\neq \bar{e} \leq \bar{ d},\,\bar{b} =\bar{ c},$} \\ && & & &&\qquad u(c) >\ 0 \\ (6e) &&u\mathbf{t}_{ea}\mathbf{t}_{ab}\mathbf{t}_{cd}& \equiv &u\mathbf{t}_{eb}\mathbf{t}_{cd}\mathbf{t}_{a,a+r}, &&\mbox{ if $c < d < e < a < b$, $\bar{c}\neq \bar{e} \leq \bar{ d},\,\bar{b} =\bar{ c},$} \\ && & & &&\qquad u(c) \leq 0\\ \end{array} }$$

We encourage the reader to draw the corresponding diagrams of the given relations together with their virtual copies in order to realize what these relations look like and understand better the interaction of these triplets. A full understanding of the relations satisfied by tuples of the operators t _ab will lead us to describe connected components of these relations. This is work in progress that we aim to use, for instance, to solve question (VII) as stated before.

Remark 7.

In a recent paper, Assaf and Billey [3] have constructed involutions ϕ _i on the so called star-tableaux. Such involutions preserve the spin statistic. Star-tableaux are equivalent to non-zero sequences of operators t _ab acting on the identity 0-grassmannian permutation Id. These transformations ϕ _i are strongly related to the relations we study satisfied by triplets t _ab . Showing that these triplets satisfy the spin statistic as well will in fact give us a much stronger positive result. We expect to include this as well in future work.