# A canonical expansion of the product of two Stanley symmetric functions

Nan Li

Department of Mathematics, Massachusetts Institute of Technology, Cambridge, MA 02139

**Abstract.** We study the problem of expanding the product of two Stanley symmetric functions $F_w \cdot F_u$ into Stanley symmetric functions in some natural way. Our approach is to consider a Stanley symmetric function as a stabilized Schubert polynomial $F_w = \lim_{n \to \infty} \mathfrak{S}_{1^n \times w}$, and study the behavior of the expansion of $\mathfrak{S}_{1^n \times w} \cdot \mathfrak{S}_{1^n \times u}$ into Schubert polynomials, as $n$ increases. We prove that this expansion stabilizes and thus we get a natural expansion for the product of two Stanley symmetric functions. In the case when one permutation is Grassmannian, we have a better understanding of this stability.

**Résumé.** Nous étudions le problème de l’ét développement du produit de deux fonctions symétriques de Stanley $F_w \cdot F_u$ en fonctions symétriques de Stanley de façon naturelle. Notre méthode consiste à considerer une fonction symétrique de Stanley comme un polynôme du Schubert stabilisé $F_w = \lim_{n \to \infty} \mathfrak{S}_{1^n \times w}$, et à étudier le comportement de l’ét développement de $\mathfrak{S}_{1^n \times W} \cdot \mathfrak{S}_{1^n \times U}$ en polynômes de Schubert lorsque $n$ augmente. Nous prouvons que cette développement se stabilise et donc nous obtenons une développement naturelle pour le produit de deux fonctions symétriques de Stanley. Dans le cas où l’une des permutations est Grassmannienne, nous avons une meilleure compréhension de cette stabilité.

**Keywords:** Stanley symmetric functions, Schubert polynomials, Littlewood-Richardson rule

## 1 Introduction

In [19], Stanley defined a homogeneous power series $F_w$ in infinitely many variables $x_1, x_2, \dots$, to compute the number of reduced decompositions of a given permutation $w$. He also proved that $F_w$ is symmetric, and $F_w$ is now referred to as a Stanley symmetric function. Our convention is that $F_w$ means the usual $F_{w^{-1}}$ as defined in [19]. It is shown in [6] that

$$F_w = s_D(w),$$

where $D(w)$ is the diagram of $w$ and $s_D(w)$ is the generalized Schur function defined in terms of the column-strict balanced labellings of $D(w)$. We are interested in the problem of expanding the product of two Stanley symmetric functions $F_w \cdot F_u$ into Stanley symmetric functions. The hope is that we can explain the coefficients in terms of $D(w)$ and $D(u)$, as a generalized Littlewood-Richardson rule for Schur functions.
However, since the Stanley symmetric functions are not linearly independent, we want to expand them in some natural way. For $w \in S_m$ and $u \in S_n$, denote by $w \times u$ the permutation $v \in S_{m+n}$, with one line notation: $w(1) \cdots w(m)(u(1) + m) \cdots (u(n) + m)$. Also, by $1^n$, we mean $1 \times 1 \times \cdots \times 1 = 123 \cdots n$. For example, $1^2 \times 2134 = 124356$. We consider a Stanley symmetric function as a stabilized Schubert polynomial [14]:

$$F_w = \lim_{n \to \infty} \mathfrak{S}_{1^n \times w}. \qquad (1)$$

Divided difference operators were first used by Bernstein-Gelfand-Gelfand [3] and Demazure [5] for the study of the cohomology of flag manifolds. Later, Lascoux and Schützenberger [10] developed the theory of Schubert polynomials based on divided difference operators. The collection $\{\mathfrak{S}_w | w \in S_n\}$ of Schubert polynomials determines an integral basis for the cohomology ring of the flag manifold, and thus there exist integer structure constants $c_{wu}^v$ such that

$$\mathfrak{S}_w \cdot \mathfrak{S}_u = \sum_v c_{wu}^v \mathfrak{S}_v.$$

It is a long standing question to find a combinatorial description of these constants. Some special cases are known. The simplest but important case is Monk's rule [16], which corresponds to the case when one of the Schubert polynomials is indexed by a simple transposition. A generalized Pieri rule was conjectured by Lascoux and Schützenberger [10], where they also sketched an algebraic proof. This Pieri rule was also conjectured by Bergeron and Billey [2] in another form, and was proved by Sottile [18] using geometry, and by Winkel [20] via a combinatorial proof. There are also results about the case of a Schubert polynomial times a Schur polynomial, for example see [9], [13] and [1].

In order to study the expansion of $F_w \cdot F_u$, we study the behavior, as $n$ increases, of the expansion of $\mathfrak{S}_{1^n \times w} \cdot \mathfrak{S}_{1^n \times u}$ into Schubert polynomials. Let us look at a toy example when $u = t_{m,m+1}$, a simple transposition.

By Monk's rule [16], we have

$$\mathfrak{S}_w \cdot \mathfrak{S}_{t_{m,m+1}} = \sum_{\substack{j \le m < k \\ \ell(wt_{jk}) = \ell(w)+1}} \mathfrak{S}_{wt_{jk}},$$

where $\ell(w)$ is the length of the permutation $w$ and $wt_{jk}$ is the permutation obtained from $w$ by exchanging $w(j)$ and $w(k)$. Notice that $1 \times t_{m,m+1} = t_{m+1,m+2}$. Then for $\mathfrak{S}_{1 \times w} \cdot \mathfrak{S}_{1 \times t_{m,m+1}}$, we will have a term $\mathfrak{S}_{1 \times wt_{jk}}$ corresponding to each term $\mathfrak{S}_{wt_{jk}}$ in the expansion of $\mathfrak{S}_w \cdot \mathfrak{S}_{t_{m,m+1}}$. Let the position of 1 in $w$ be $s$, i.e., $w^{-1}(1) = s$. If $s \le m$, then there are no more permutations; otherwise, if $s > m$, we get one more permutation $(1 \times w)t_{1,s+1}$. This holds for all $\mathfrak{S}_{1^n \times w} \cdot \mathfrak{S}_{1^n \times t_{m,m+1}}$. More precisely, we have

$$\mathfrak{S}_{1^n \times w} \cdot \mathfrak{S}_{1^n \times t_{m,m+1}} = \sum_{\substack{j \le m < k \\ \ell(wt_{jk}) = \ell(w)+1}} \mathfrak{S}_{1^n \times wt_{jk}} (+\mathfrak{S}_{1^n-1 \times (1 \times w)t_{1,s+1}}, \text{ if } s > m).$$

Now taking the limit for $n \to \infty$, we get the following canonical expansion:

$$F_w \cdot F_{t_{m,m+1}} = \sum_{\substack{j \le m < k \\ \ell(wt_{jk}) = \ell(w)+1}} F_{wt_{jk}} (+F_{(1 \times w)t_{1,s+1}}, \text{ if } s > m).$$
Let us look at another example for $w = 3241$ and $u = 4312$. Consider $\mathfrak{S}_{1^n \times 3241} \cdot \mathfrak{S}_{1^n \times 4312}$ as $n$ increases. For $n = 0, 1, 2$, we have

$$ \begin{aligned} \mathfrak{S}_{3241} \cdot \mathfrak{S}_{4312} &= \mathfrak{S}_{642135} \\ \mathfrak{S}_{1 \times 3241} \cdot \mathfrak{S}_{1 \times 4312} &= \mathfrak{S}_{1 \times 642135} + \mathfrak{S}_{265314} + \mathfrak{S}_{2743156} + \mathfrak{S}_{356214} + \mathfrak{S}_{364215} + \mathfrak{S}_{365124} \\ &\qquad + \mathfrak{S}_{462315} + \mathfrak{S}_{561324} \\ \mathfrak{S}_{1^2 \times 3241} \cdot \mathfrak{S}_{1^2 \times 4312} &= \mathfrak{S}_{1^2 \times 642135} + \mathfrak{S}_{1 \times 265314} + \mathfrak{S}_{1 \times 2743156} + \mathfrak{S}_{1 \times 356214} + \mathfrak{S}_{1 \times 364215} + \mathfrak{S}_{1 \times 365124} \\ &\qquad + \mathfrak{S}_{1 \times 462315} + \mathfrak{S}_{1 \times 561324} + \mathfrak{S}_{2375416} + \mathfrak{S}_{246531} + \mathfrak{S}_{256341}. \end{aligned} $$

Notice that as $n$ increases, we keep all the permutations appearing in the previous case and add some new permutations (the underlined terms). In this example, the expansion stabilizes after $n = 2$, i.e., we do not add new permutations for $n > 2$, i.e.,

$$ \begin{aligned} \mathfrak{S}_{1^n \times 3241} \cdot \mathfrak{S}_{1^n \times 4312} &= \mathfrak{S}_{1^n \times 642135} + \mathfrak{S}_{1^{n-1} \times 265314} + \mathfrak{S}_{1^{n-1} \times 2743156} + \mathfrak{S}_{1^{n-1} \times 356214} + \mathfrak{S}_{1^{n-1} \times 364215} \\ &\quad + \mathfrak{S}_{1^{n-1} \times 365124} + \mathfrak{S}_{1^{n-1} \times 462315} + \mathfrak{S}_{1^{n-1} \times 561324} + \mathfrak{S}_{1^{n-2} \times 2375416} + \mathfrak{S}_{1^{n-2} \times 246531} \\ &\quad + \mathfrak{S}_{1^{n-2} \times 256341}. \end{aligned} $$

Then taking $n \to \infty$, we have

$$ F_{3241} \cdot F_{4312} = F_{642135} + F_{265314} + F_{2743156} + F_{356214} + F_{364215} + F_{365124} + F_{462315} + F_{561324} \\ + F_{2375416} + F_{246531} + F_{256341}. $$

The stability of the expansion $\mathfrak{S}_{1^n \times w} \cdot \mathfrak{S}_{1^n \times u}$ we observed in the previous two examples are true in general. Here is the main result of this paper.

**Theorem 1.1** Let $w, u$ be two permutations.

1. Suppose $\mathfrak{S}_w \cdot \mathfrak{S}_u = \sum_{v_0 \in V_0} c_{w,u}^{v_0} \mathfrak{S}_{v_0}$. Then

$$ \mathfrak{S}_{1 \times w} \cdot \mathfrak{S}_{1 \times u} = \sum_{v_0 \in V_0} c_{w,u}^{v_0} \mathfrak{S}_{1 \times v_0} + \sum_{v_1 \in V_1} c_{w,u}^{v_1} \mathfrak{S}_{v_1}, $$

where $v_1(1) \neq 1$, for each $v_1 \in V_1$.

2. Let $k = \ell(w) + \ell(u)$. Then for all $n \ge k$, we have

$$ \mathfrak{S}_{1^n \times w} \cdot \mathfrak{S}_{1^n \times u} = \sum_{v_0 \in V_0} c_{w,u}^{v_0} \mathfrak{S}_{1^n \times v_0} + \sum_{v_1 \in V_1} c_{w,u}^{v_1} \mathfrak{S}_{1^{n-1} \times v_1} + \dots + \sum_{v_k \in V_k} c_{w,u}^{v_k} \mathfrak{S}_{1^{n-k} \times v_k}, $$

where $V_i$ (possibly empty) is the set of new permutations appearing in $\mathfrak{S}_{1^{i \times w}} \cdot \mathfrak{S}_{1^{i \times u}}$ compared to $\mathfrak{S}_{1^{i-1 \times w}} \cdot \mathfrak{S}_{1^{i-1 \times u}}$. Taking $n \to \infty$, we have a canonical expansion:

$$ F_w \cdot F_u = \sum_{v \in V} c_{w,u}^{v} F_v, \qquad (2) $$

where $V = V_0 \cup \dots \cup V_k$.
For a permutation $w \in S_n$, define the code $c(w)$ to be the sequence $c(w) = (c_1, c_2, \dots)$ of nonnegative integers given by $c_i = \#\{j \in [n] \mid j > i, w(j) < w(i)\}$. Define the length of $c(w)$ to be $i_0 = \max\{i \mid c_i \neq 0\}$, denoted by $\ell(c(w))$. We call a permutation **Grassmannian** if it has at most one descent. It is known that if $w$ is Grassmannian, then $\mathfrak{S}_w$ is a Schur polynomial in $\ell(c(w))$ variables.

**Theorem 1.2** Apply the above notations. If one of $w, u$ is Grassmannian, then we also have:

1. If $V_i = \emptyset$ for some $i$, then $V_j = \emptyset$ for all $j > i$. We call the smallest $i$ such that $V_i = \emptyset$ the **stability number** for $w, u$.

2. The stability number is bounded by $\max\{\ell(c(w)), \ell(c(u))\}$. In particular, if $w = u$ with $w(1) \neq 1$, the stability number equals $w^{-1}(1) - 1$.

**Conjecture 1.3** Theorem 1.2 is true for general $w, u$.

In Section 2, we prove Theorem 1.1 using the combinatorial definition of Schubert polynomials given in [4]. In Section 3, we study the case when one of the permutation is Grassmannian. We prove Theorem 1.1 and 1.2 by an algorithm described in [9] using maximal transitions [11]. In Section 4, we generalize this stability to the product of double Schubert polynomials. We also give the definition of the weak and strong stable expansions, and prove some other stable properties, which provide a second proof of Theorem 1.1.

## 2 Proof of Theorem 1.1

Let us recall the combinatorial definition of Schubert polynomials introduced in Theorem 1.1 [4]. Let $p = \ell(w)$ be the length of $w$, and $R(w)$ be the set of all the reduced words of $w$. For $a = (a_1, \dots, a_p)$, let $K(a)$ be the set of all $a$-compatible sequences, i.e., $(i_1, \dots, i_p)$ such that: 1) $i_1 \le \dots \le i_p$; 2) $i_j \le a_j$, for $j = 1, \dots, p$; and 3) $i_j < i_{j+1}$, if $a_j < a_{j+1}$. Then we have

$$ \mathfrak{S}_w = \sum_{a \in R(w)} \sum_{(i_1, \dots, i_p) \in K(a)} x_{i_1} \cdots x_{i_p}. \qquad (3) $$

**Definition 2.1** For two integer vectors $b^1 = (b_1^1, \dots, b_p^1)$ and $b^2 = (b_1^2, \dots, b_p^2)$, consider the following conditions:

1. $b^1$ and $b^2$ are weakly increasing. Namely, $b_1^1 \le \dots \le b_p^1$ and $b_1^2 \le \dots \le b_p^2$.

2. $b^1$ is smaller than $b^2$, denoted by $b^1 < b^2$, which means $b_i^1 \le b_i^2$ for each $i = 1, \dots, p$;

3. $b^1$ is similar with $b^2$, denoted by $b^1 \sim b^2$, which means $b^1$ and $b^2$ increase at the same time, i.e., $b_i^1 < b_{i+1}^1$ if and only if $b_i^2 < b_{i+1}^2$;

4. $b^1$ and $b^2$ are bounded by $n$, i.e., $b_i^1 \le n$ and $b_i^2 \le n$, for all $i = 1, \dots, p$.

We call $(b^1, b^2)$ a **good pair** if it satisfies the first three conditions, call it a **good-n pair**, if all four conditions are satisfied.

For example, $(b^1, b^2)$, with $b^1 = (2, 4, 4, 5)$ and $b^2 = (2, 6, 6, 8)$, is a good-8 pair. Denote $X_b = x_{b_1} x_{b_2} \cdots x_{b_p}$. For example, $X_{b^1} = x_2 x_4^2 x_5$, for the previous $b^1$. We use $\co(X_b)$ to denote the coefficient of $X_b$.
**Lemma 2.2** 1. In $\mathfrak{S}_w$, $\co(X_{b^1}) \ge \co(X_{b^2})$, for any good pair $(b^1, b^2)$.

2. In $\mathfrak{S}_{1^n \times u}$, $\co(X_{b^1}) = \co(X_{b^2})$, for any good-n pair $(b^1, b^2)$.

3. In $\mathfrak{S}_{1^n \times u}$, $\co(X_{b^1} \cdot g) = \co(X_{b^2} \cdot g)$, for any good-n pair $(b^1, b^2)$ and any monomial $g$ with variable indices larger than $n$.

4. In $\mathfrak{S}_{1^n \times w} \cdot \mathfrak{S}_{1^n \times u}$, $\co(X_{b^1} \cdot g) = \co(X_{b^2} \cdot g)$, for any good-n pair $(b^1, b^2)$ any monomial $g$ with indices larger than $n$.

**Proof:** Parts 1-3 follow from the combinatorial definition (3) of Schubert polynomials and Definition 2.1. Now we will prove part 4. In fact, any $X_{b^1} \cdot g$ it is the product of two monomials, one from $\mathfrak{S}_{1^n \times w}$ and one from $\mathfrak{S}_{1^n \times u}$, let us assume $X_{b^1} = X_{b^{11}} \cdot X_{b^{12}}$, and the corresponding decomposition for $X_{b^2}$ is $X_{b^2} = X_{b^{21}} \cdot X_{b^{22}}$. For example, consider the previous good-8 pair $(b^1, b^2)$. If $X_{b^1} = x_2 x_4^2 x_5 = (x_2 x_4)(x_4 x_5)$ with $b^{11} = (2, 4)$ and $b^{12} = (4, 5)$, then we decompose $X_{b^2} = x_2 x_6^2 x_8$ as $(x_2 x_6)(x_6 x_8)$ with $b^{21} = (2, 6)$ and $b^{22} = (6, 8)$. Since $b^1 \sim b^2$, we have $b^{11} \sim b^{21}$ and $b^{12} \sim b^{22}$. Applying part 3 to both pairs, we have $\co(X_{b^1} \cdot g) = \co(X_{b^2} \cdot g)$. $\square$

Write the code of $w$ as $c(w) = (c_1, c_2, \dots, c_p)$ and $X^{c(w)} = x_1^{c_1} x_2^{c_2} \cdots x_p^{c_p}$. Let $b(c)$ be the weakly increasing sequence such that $X_{b(c)} = X^c$. We use reverse lex-order in this section. It is known that the top degree term of $\mathfrak{S}_w$ is $X^{c(w)}$, i.e.,

$$ \mathfrak{S}_w = X^{c(w)} + \sum_{b} X_b, \qquad (4) $$

where each $b$ satisfies $b < b(c(w))$ termwisely, as defined in part 2 of Definition 2.1. Now we consider the process of getting the expansion of $\mathfrak{S}_w \cdot \mathfrak{S}_u$. By (3), the top degree term is $X^{c(w)+c(u)}$. Let $v_1$ be the permutation such that $c(v_1) = c(w) + c(u)$. Then

$$ \mathfrak{S}_w \cdot \mathfrak{S}_u = \mathfrak{S}_{v_1} + \dots, $$

so $c_{wu}^{v_1} = 1$. Then consider the top degree term in $\mathfrak{S}_w \cdot \mathfrak{S}_u - \mathfrak{S}_{v_1}$. Let it be $c_2 X^{c(v_2)}$ for some $v_2$. Then

$$ \mathfrak{S}_w \cdot \mathfrak{S}_u - \mathfrak{S}_{v_1} = c_2 \mathfrak{S}_{v_2} + \dots. $$

Next, consider the top degree term in $\mathfrak{S}_w \cdot \mathfrak{S}_u - \mathfrak{S}_{v_1} - c_2 \mathfrak{S}_{v_2}$, etc. Since there are finitely many monomials in $\mathfrak{S}_w \cdot \mathfrak{S}_u$, this process terminates, and we get an expansion $\mathfrak{S}_w \cdot \mathfrak{S}_u = \sum_{v \in V_0} c_{wu}^v \mathfrak{S}_v$.

**Proof of Theorem 1.1:**

1. By the combinatorial definition of Schubert polynomial (3) and the above process of expanding $\mathfrak{S}_w \cdot \mathfrak{S}_u$, we have $c_{1 \times w, 1 \times u}^{1 \times v} = c_{w, u}^v$ for all $v \in V_0$. Further more, each term in

$$ \mathfrak{S}_{1 \times w} \cdot \mathfrak{S}_{1 \times u} - \sum_{v_0 \in V_0} c_{w, u}^{v_0} \mathfrak{S}_{1 \times v_0} $$

is divided by $x_1$. So any $\mathfrak{S}_v$ with $c(v) = (c_1, c_2, \dots)$ appear in the above difference has $c_1 \ne 0$, which is equivalent to $v(1) \ne 0$. This proves part one.
2. For a fixed $n$, suppose

$$ \mathfrak{S}_{1^n \times w} \cdot \mathfrak{S}_{1^n \times u} = \sum_{v \in V} c_{wu}^v \mathfrak{S}_v. $$

We claim that the code $c(v) = (c_1, c_2, \dots, c_p)$ for $v \in V$ has to satisfy the following property: let $c(v)_n = (c_1, c_2, \dots, c_n)$ be the first $n$ elements in $c(v)$. Let $i(v)$ be the smallest number such that $c_i \neq 0$. Then the claim is that if $i(v) \le n$, then for all $i(v) < j \le n$, we have $c_j \neq 0$. Suppose we have proved this claim. Then since $c_1 + \dots + c_n \le k$, where $k = \ell(w) + \ell(u)$, for each $v \in V$, we have $i(v) \ge n-k$. In other words, the code $c(v)$ starts with at least $n-k$ zeros, and thus $v$ starts with $12 \dots (n-k)$, which will finish the proof. Now let us prove the claim.

In fact, suppose we have some $v_0 \in V$ which does not satisfy the claim. Namely there exists some $j$ such that $i(v) < j \le n$ and $c_j = 0$. Let $c' = (0, c_1, c_2, \dots, c_{j-1}, c_{j+1}, \dots, c_n)$. Consider the pair $b^1 = b(c(v)_n)$ and $b^2 = b(c')$, i.e., $X_{b^1} = X^{c(v)_n}$ and $X_{b^2} = X^{c'}$. For example, let $n = 7$, and $c(v_0)_n = (0, 0, 0, 2, 3, 0, 2)$. Then $X_{b^1} = X_4^2 X_5^3 x_7^2$, $c' = (0, 0, 0, 0, 2, 3, 2)$ and $X_{b^2} = X_5^2 X_6^3 x_7^2$. Then $(b^1, b^2)$ is a good $n$-pair.

Now let $g = X^{(c_{n+1}, \dots, c_p)}$. Notice that $X_{b^1} \cdot g$ is the top degree term in $\mathfrak{S}_{v_0}$ by (4). Since $b^2 > b^1$, $\co(X_{b^2} \cdot g) = 0$ in $\mathfrak{S}_{v_0}$. Therefore, $\co(X_{b^1} \cdot g) > \co(X_{b^2} \cdot g)$ in $\mathfrak{S}_{v_0}$. By Lemma 2.2, on the right hand side, for each $v \in V$, we have $\co(X_{b^1} \cdot g) \ge \co(X_{b^2} \cdot g)$, therefore, on the right hand side, we have $\co(X_{b^1} \cdot g) > \co(X_{b^2} \cdot g)$. However, on the left hand side, we must have $\co(X_{b^1} \cdot g) = \co(X_{b^2} \cdot g)$, a contradiction. $\square$

# 3 Schubert polynomial times a Schur polynomial

In this section we will prove Theorem 1.1 and 1.2 for the case when one of the permutation $w, u$ is Grassmannian. We will apply an algorithm for multiplying a Schubert polynomial by a Schur polynomial based on the following result. This result was originally proved using Kohnert's algorithm, which unfortunately, has not been completely proved yet. However, using the very similar algorithm called ladder and chute moves studied in [2], we can still show that the following theorem is true.

**Theorem 3.1 (Theorem 3.1 in [9])** Let $\mathfrak{S}_u$ be a Schur polynomial with $m$ variables, i.e., $u$ is a Grassmannian permutation with $\ell(c(v)) = m$. Let $\mathfrak{S}_w$ be a Schubert polynomial with $m$ variables, i.e., $\ell(c(w)) = m$. Then

$$ \mathfrak{S}_w \cdot \mathfrak{S}_u = \mathfrak{S}_{w \times u} \downarrow A_m, $$

where $f \downarrow A_m = f(x_1, \dots, x_m, 0, \dots, 0)$.

The algorithm we will apply for multiplying a Schubert polynomial by a Schur polynomial was studied in [9] and is a modification of the algorithm by Lascoux and Schützenberger [11] for decomposing the product of two Schur functions into a sum of Schur functions.

## 3.1 Maximal transition tree

Recall that $wt_{rs}$ is the permutation obtained from $w$ by switching $w(r)$ and $w(s)$. Let $r$ be the largest descent of the permutation $w$, and $s$ be the largest integer such that $w(s) < w(r)$. The following formula
<figure><img src="image_1.png" /><figcaption>Fig. 1: MT-tree rooted at 321 × 2413 for Example 3.2</figcaption></figure>

follows from Monk's rule [16]

$$ \mathfrak{S}_w = x_r \mathfrak{S}_u + \sum_{v \in S(w)} \mathfrak{S}_v, \qquad (5) $$

where $u = wt_{rs}$ and $S(w)$ is the set of permutations of the form $wt_{rs}t_{jr}$ with $j < r$ such that $\ell(wt_{rs}t_{jr}) = \ell(w)$. So each $v \in S(w)$ corresponds to a different $j \in J(w)$. We call (5) a **maximal transition** (MT for short) (see [11]). For example, for $w = 321654$, we have $r(w) = 5$, $s(w) = 6$, $J(w) = \{1, 2, 3\}$ and $S(w) = \{421635, 341625, 324615\}$. We call each $v \in S(w)$ a descendent of $w$.

Notice that $c_i = 0$, for all $i > r(w)$ in the code $c(w) = (c_1, c_2, \dots)$, and $\mathfrak{S}_w$ is a polynomial with $r(w)$ variables. So if $r(w) \le m$, then $\mathfrak{S}_w = \mathfrak{S}_w \downarrow A_m$. If $r(w) > m$, we have $\mathfrak{S}_w \downarrow A_m = \sum_{v \in S(w)} \mathfrak{S}_v \downarrow A_m$ by (5), since we set $x_r = 0$. Notice that for each permutation $v \in S(w)$, $r(v) < r(w)$. We call a permutation $v$ **bad** if $v^{-1}(1) > m + 1$. If $v$ is bad, then $x_{m+1}$ divides each monomial of $\mathfrak{S}_v$, so $\mathfrak{S}_v \downarrow A_m = 0$.

Apply MT successively to $w \times u$, each $v \in S(w \times u)$ and their descendants as long as the permutation is not bad, until their largest descents are smaller than $m$. This way we get a finite tree with two types of leaves: 1) a permutation with largest descent $\le m$, we call it a **good leaf**; and 2) a bad permutation as defined above. Then $\mathfrak{S}_{w \times u} \downarrow A_m$ is obtained by summing up all of the good leaves. We call this tree the MT-tree rooted at $w \times u$; we call the edge between a permutation $w$ and one of its descendant $v \in S(w)$ an MT-move.

**Example 3.2** Here is an example of the MT tree rooted at $w \times u$, for $w = 321$, $u = 2413$ and $m = 2$ (see Figure 1). The leaves we cross out are the bad leaves, i.e., permutations with 1 in position larger than $m + 1 = 3$. The remaining leaves are good leaves, i.e., they have largest descent $\le m = 2$. So summing up all the good leaves, we have $\mathfrak{S}_{321} \cdot \mathfrak{S}_{2413} = \mathfrak{S}_{321 \times 2413} \downarrow A_2 = \mathfrak{S}_{53124} + \mathfrak{S}_{45123}$.

**Remark 3.3** Notice that in Figure 1, the descendants of 341625 are bad leaves (35214 and 34512). It will be nice if one could simplify the tree so that we can remove 341625 without applying further moves. However, it seems that such a rule, if exists, will be related with some pattern avoidances, which is hard to describe in general.

Now we want to study the difference between the MT-tree rooted at $1 \times w \times 1 \times u$ and the one rooted at $w \times u$.

**Example 3.4** Continue Example 3.2. We study $\mathfrak{S}_{1 \times 321} \cdot \mathfrak{S}_{1 \times 2413}$ (see Figure 2). Notice that now $m = 3$ instead of 2 in Example 3.2. Summing up all good leaves, we have $\mathfrak{S}_{1 \times 321} \cdot \mathfrak{S}_{1 \times 2413} = \mathfrak{S}_{1432 \times 13524} \downarrow A_3 = \mathfrak{S}_{164235} + \mathfrak{S}_{156234} + \mathfrak{S}_{263145} + \mathfrak{S}_{25413} + \mathfrak{S}_{246135} + \mathfrak{S}_{34512}$.
<figure><img src="image_2.png" /><figcaption>Fig. 2: MT-tree rooted at $1 \times 321 \times 1 \times 2413$ for Example 3.4</figcaption></figure>

Compare the leaves of the above tree and those in Example 3.2. We have the following observations.

1. The good leaves in Example 3.2 (53124 and 45123) stay good in Example 3.4, simply with a one added in front ($1 \times 53124 = 164235$ and $1 \times 45123 = 156234$, bolded in Figure 2).

2. The remaining good leaves in Example 3.4 are descendants of some bad leaves in Example 3.2. For example, 263145 (underlined in Figure 2) is obtained from 52314 which used to be bad in Example 3.2.

3. For the new good leaves in Example 3.4, the position of 1 stays the same as their ancestor in Example 3.2. For example, both 263145 and 52314 has 1 in the fourth position.

In general, the first and second observations above are true as a consequence of Lemma 3.5, and the third observation is true by Lemma 3.6.

**Lemma 3.5** For the MT tree rooted at $1 \times w \times 1 \times u$, consider the subtree $T$ with all permutations starting with 1. Then the leaves of $T$ are exactly the leaves of the MT tree rooted at $w \times u$ with 1 added in front.

**Lemma 3.6** For any reduced permutation $w$ (cannot make more MT-moves), if we add 1 in the beginning and then apply the MT-moves to $1 \times w$, the position of 1 in the leaves is the same as the position of 1 in $w$.

Lemma 3.6 can be proved using the definition of an MT-move. For Lemma 3.5, we need to have a closer look at the MT-move in terms of diagrams, which will be studied in the next subsection.

Now notice that in Example 3.4, there is still one bad leaf 243615 (see Figure 2). So in the next step $\mathfrak{S}_{12 \times 321} \cdot \mathfrak{S}_{12 \times 2413}$, there will be some more good leaves with 243615 as ancestor. After that, the expansion $\mathfrak{S}_{1^n \times 321} \cdot \mathfrak{S}_{1^n \times 2413}$, for $n \ge 2$ should have no more new permutations. And in fact, this is the case: $\mathfrak{S}_{1^n \times 321} \cdot \mathfrak{S}_{1^n \times 2413} = \mathfrak{S}_{1^n \times 53124} + \mathfrak{S}_{1^n \times 45123} + \mathfrak{S}_{1^{n-1} \times 263145} + \mathfrak{S}_{1^{n-1} \times 25413} + \mathfrak{S}_{1^{n-1} \times 246135} + \mathfrak{S}_{1^{n-1} \times 34512} + \mathfrak{S}_{1^{n-2} \times 236415}$, for all $n \ge 2$. So we have

$$F_{321} \cdot F_{2413} = F_{53124} + F_{45123} + F_{263145} + F_{25413} + F_{246135} + F_{34512} + F_{236415}. \quad (6)$$

So the stability number for $\mathfrak{S}_{321} \cdot \mathfrak{S}_{2413}$ is 2, as predicted by Theorem 1.2 part 2 that it should be bounded by $\ell(c(321)) = \ell(c(2413)) = 2$. Now look at the positions of 1 in each permutation appearing on the right hand side of (6): $I = \{3, 4, 5\}$, which is an interval without any gaps. In general, we have
**Lemma 3.7** Let $F_w \cdot F_u = \sum_{v \in V} F_v$ be the expansion we get by Theorem 1.1. Let $I\{v^{-1}(1) | v \in V\}$. Then $I = [a, b]$ an interval without any gaps.

Lemma 3.7 together with Theorem 1.1 will imply Theorem 1.2. For a proof of Lemma 3.7, we also want to use the diagrams interpretation of the MT-move studied in the next subsection.

## 3.2 MT-move in terms of diagrams

In order to prove Lemma 3.5 and 3.7, we want to describe the MT-move in terms of diagrams. Let $v$ be a descendant of $w$ via an MT-move. Then $D(v)$ is obtained from $D(w)$ by moving some part of the diagram up and left. For example, as shown in the first step of Example 3.2, applying an MT-move to $w = 3215746$, we get $v = 3216547$, and the diagram of $v$ is obtained from $D(w)$ by moving the box with a bullet up and left by one row and one column (see Figure 3). Notice that this diagram move is very similar to the move described in [8].

<figure><img src="image_3.png" /><figcaption>Fig. 3: MT-move</figcaption></figure>

In the diagram of $w$, consider the right-down corner box $B(w)$, i.e., the box in the rightmost column of the lowest row. By the definition of $r(w) = r$ and $s(w) = s$, we have $B(w) = B_{r,w(s)}$. For each $j \in J(w)$, denote the box $B_{j,w(j)}$ by $T(w, j)$. Then the above changes of inversions can be seen as moving some blocks with $B(w)$ as its right-down corner up and left so that $T(w, j)$ becomes its up-left corner. For example, consider $w = 321654$ in the branching part of Example 3.2, with $J(w) = \{1, 2, 3\}$. See Figure 4(a) for $D(w)$, where $B(w)$ is marked with a bullet and all three possible $T(w, j)$'s are marked with $\times$. Now applying MT-moves to $D(w)$, all three $D(v)$, for $v \in S(w)$ are shown in Figure 4(b), 4(c) and 4(d). Using this diagram interpretation of the MT-move, we can prove Lemma 3.5 by comparing the MT-moves of $D(w \times u)$ and $D(1 \times w \times 1 \times u)$.

Now consider Lemma 3.7. Notice that $v^{-1}(1) - 1$ is the number of boxes in the first column of $D(v)$. Consider again $w$ and $S(w)$ shown in Figure 4. Notice that applying different $j \in J(w)$ may result in different numbers $b(j)$ of potential boxes to be added to the first column. For example, for $j = 2$, there is one box left, and for $j = 3$, there are two boxes left (and are already added). The set $b = \{b(j) | j \in J(w)\} = [1, 2]$ is an interval without any gaps. Using the diagram interpretation of the MT-move we can show that this holds in general, which implies Lemma 3.7.

**Corollary 3.8** Let $w, u$ be two permutations both with $\ell(c(w)) = \ell(c(u)) = m$ (for the case when $\ell(c(w)) \neq \ell(c(u))$, add enough ones to the front of one permutation). Assume $u$ is Grassmannian. Apply MT-moves successively to $D(1^m \times w \times u)$. Stop applying MT-moves to a diagram $D$ as soon as all the boxes in its diagram are in the first $2m$ rows. Denote the multiset of the diagrams obtained this way by $A$. Then in the canonical expansion (2) $F_w \cdot F_u = \sum_{v \in V} c_{wu}^v F_v$, we have

$$c_{wu}^v = \#\{D \in A \mid D = D(v)\}.$$
<figure><img src="image_4.png" /><figcaption>Fig. 4: MT-moves using different j's</figcaption></figure>

## 4 Other Stable Expansions

In this section, we will study some other stable expansions related with Schubert polynomials. Given some expansion, we can study the behavior of that expansion when we keep adding ones in front of the indices, as we did for Theorem 1.1 and Theorem 1.2. We call the eventually stabilized behavior, described in Theorem 1.1 the weak stable property; and if the expansion further satisfies the property that once there are no new terms, there will be no new terms ever, as described in Theorem 1.2, we say that it satisfies the strong stable property.

First note that by Theorem 1.1, we have the weak stable property for the expansion of the product of finitely many Schubert polynomials into Schubert polynomials. Now, let us consider the double Schubert polynomials. Corollary 4.1 follows from the following identity (see for example [15, Proposition 2.4.7]):

$$ \mathcal{S}_w(x, y) = \sum_{\substack{w=v^{-1}u \\ \ell(w)=\ell(u)+\ell(v)}} \mathcal{S}_u(x)\mathcal{S}_v(-y). $$

**Corollary 4.1** For the unique expansion of the product of finitely many double Schubert polynomials into Schubert polynomials, we have the weak stable property.

Now we consider the stable property for some other related expansions. It is well known (see [10], [12, (2.6)-(2.7)], [7, (4.13)]) that the following are Z-linear bases for $Z[x_1, \dots, x_n]/I_n$, and each of them spans the same vector space which is complementary to $I_n$:

1. the monomials $x_1^{a_1} \cdots x_{n-1}^{a_{n-1}}$ such that $0 \le a_k \le n-k$;

2. the standard elementary monomials $e_I = e_{i_1 i_2 \dots i_{n-1}} = e_{i_1}^1 e_{i_2}^2 \dots e_{i_{n-1}}^{n-1}$, where $e_i^k = e_i(x_1, \dots, x_k)$ is the k'th elementary symmetric polynomial with k variables;

3. the Schubert polynomials $\mathcal{S}_w$ for $w \in S_n$.

In the rest of this section, we will prove the stable property for the unique expansions of $e_I$ into the $\mathcal{S}_w$'s and $\mathcal{S}_w$ into the $e_I$'s.

**Proposition 4.2** For $e_I = \sum_{w \in W} \beta_w^I \mathcal{S}_w$, we have the strong stable property, i.e., there exists some r such that for all $k \ge r$, we have

$$ e_{(0^k, i_1, i_2, \dots, i_{n-1})} = \sum_{w \in W} \beta_w^I \mathcal{S}_{1^k \times w} + \sum_{w_1 \in W_1} \beta_{w_1}^I \mathcal{S}_{1^{k-1} \times w} + \dots + \sum_{w_k \in W_r} \beta_{w_k}^I \mathcal{S}_{1^{k-r} \times w}, $$
where for $i = 1, \dots, r$, we have $W_i \neq \emptyset$; and for $1 \le k < r$, $W_k$ is the set of new permutations added in the expansion of $e_{(0^k, i_1, i_2, \dots, i_{n-1})}$ from $e_{(0^{k-1}, i_1, i_2, \dots, i_{n-1})}$. Moreover, we have $r = i_1 + i_2 + \dots + i_n - (n-1)$ and $W_r$ is the single permutation $23 \dots (r+n)1$.

We prove Proposition 4.2 by the following lemma, which is implied by the Pieri rule.

**Lemma 4.3** We have the strong stable property for the unique expansion of $e_i^j \mathfrak{S}_w$ into Schubert polynomials.

For the expansion of $\mathfrak{S}_w$ into the $e_I$'s, we have the following stable property:

**Proposition 4.4** For the unique expansion $\mathfrak{S}_w = \sum_{I \in \mathbb{N}^\infty} a_I^w e_I$, we have the weak stable property.

To prove Proposition 4.4, we use the following two identities from [17]: for any $w, u \in S_n$ and $a \in \mathbb{N}^\infty$, we have

$$ \mathfrak{S}_{ww_0} = \sum_{b \in \mathbb{N}^{\infty}} K_{b,w}^{-1} e_{w_0(\rho_n - b)}, \quad K_{a,u}^{-1} = \sum_{w \in S_n} (-1)^{\ell(w)} K_{w_0 u, w(\rho_n) - a} $$

where $w_0 = n(n-1)\dots1$, $\rho_n = (n-1, n-2, \dots, 1, 0)$, and $K^{-1} = (K_{a,w}^{-1})$ is the inverse of the Schubert-Kostka matrix $K = (K_{w,a})$, defined as the coefficients of the expansion $\mathfrak{S}_w = \sum_{a \in \mathbb{N}^\infty} K_{w,a} X^a$.

**Remark 4.5** Consider the expansion of two Schubert polynomials $\mathfrak{S}_w \mathfrak{S}_u$ into Schubert polynomials as we studied in Theorem 1.1. By Proposition 4.4, we get a stabilized expansion of $\mathfrak{S}_w$ into the $e_I$'s. Then, by Lemma 4.3, the expansion of each term $e_I \mathfrak{S}_u$ into Schubert polynomials stabilizes. This way, we have a second proof of Theorem 1.1.

Acknowledgements

I thank Richard Stanley and Steven Sam for helpful discussions and reading the draft. I am also very grateful for the anonymous referee from Fpsac 2012 for some very good suggestion.

References

[1] S. Assaf, N. Bergeron and F. Sottile, On the multiplication of Schubert polynomials, in preparation.

[2] N. Bergeron and S. Billey, RC-Graphs and Schubert polynomials, *Experimental Math.* **2** (1993), 257–269.

[3] I. N. Bernstein, I. M. Gelfand, and S. I. Gelfand, Schubert cells and cohomology of the spaces G/P, *Russian Mathematical Surveys* **28** (1973), 1–26.

[4] S. Billey, W. Jockusch and R. P. Stanley, Some combinatorial properties of Schubert polynomials, *J. Algebraic Combin.* **2** (1993), 345–374.

[5] M. Demazure, Désingularisation des variétés de Schubert généralisées, *Ann. Sc. E. N. S.* **4** 7(1974), 53–88.

[6] S. Fomin, E. Greene, V. Reiner and M. Shimozono, Balanced Labellings and Schubert Polynomials, *Europ. J. Combinatorics* **18** (1997), 373–389.
[7] I. Gelfand, D. Krob, A. Lascoux, B. Leclerc, V. S. Retakh, and J.-Y. Thibon, Noncommutative symmetric functions, *Adv. Math* **112** (1995), no. 2, 218–348.

[8] A. Knutson and A. Yong, A formula for K-theory truncation Schubert calculus, *International Mathematics Research Notices* **70** (2004), 3741–3756.

[9] A. Kohnert, Multiplication of a Schubert polynomial by a Schur polynomial, *Annals of Combinatorics* **1** (1997), 367–375.

[10] A. Lascoux and M.P. Schützenberger, Polynômes de Schubert, *C. R. Acad. Sci. Paries* **294** (1982), 447–450.

[11] A. Lascoux and M.P. Schützenberger, Schubert polynomials and the Littlewood-Richardson rule, *Letters in Mathematical Physics* **10** (1985), 111–124.

[12] A. Lascoux and M.P. Schützenberger, Fonctorialité de polynômes de Schubert, *Contemp. Math.* **88** (1989), 585–598.

[13] C. Lenart, Growth Diagrams for the Schubert Multiplication, *Journal of Combinatorial Theory, Series A*, **117** (2010) 842–856.

[14] I. G. Macdonald, Notes on Schubert polynomials, *Laboratoire de Combinatoire et d'Informatique Mathématique, Université du Québec à Montréal* (1991).

[15] L. Manivel, Symmetric functions, Schubert polynomials and degeneracy loci, *American Mathematical Soc.* (2001).

[16] D. Monk, Geometry of flag manifolds, *Proc. London Math. Soc.* **9** (1959), 253–286.

[17] A. Postnikov, Richard Stanley, Chains in the Bruhat order, *Journal of Algebraic Combinatorics.*, **46** (2009) 29: 133–174.

[18] F. Sottile, Pieri's rule for flag manifolds and Schubert polynomials, *Ann. de l'Inst. Four.*, **46** (1996) 89–110.

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

[20] R. Winkel, On the multiplication of Schubert polynomials, *Advances in Applied Mathematics*, **20** (1998) 73–97.