# A Molev-Sagan type formula for double Schubert polynomials

Matthew J. Samuel  Monroe Township, Middlesex County, New Jersey, United
States<EMAIL_ADDRESS>
###### Abstract.

We give a Molev-Sagan type formula for computing the product
$\operatorname{\mathfrak{S}}_{u}(x;y)\operatorname{\mathfrak{S}}_{v}(x;z)$ of
two double Schubert polynomials in different sets of coefficient variables
where the descents of $u$ and $v$ satisfy certain conditions that encompass
Molev and Sagan’s original case and conjecture positivity in the general case.
Additionally, we provide a Pieri formula for multiplying an arbitrary double
Schubert polynomial $\operatorname{\mathfrak{S}}_{u}(x;y)$ by a factorial
elementary symmetric polynomial $E_{p,k}(x;z)$. Both formulas remain positive
in terms of the negative roots when we set $y=z$, so in particular this gives
a new equivariant Littlewood-Richardson rule for the Grassmannian, and more
generally a positive formula for multiplying a factorial Schur polynomial
$s_{\lambda}(x_{1},\ldots,x_{m};y)$ by a double Schubert polynomial
$\operatorname{\mathfrak{S}}_{v}(x_{1},\ldots,x_{p};y)$ such that $m\geq p$.
An additional new result we present is a combinatorial proof of a conjecture
of Kirillov of nonnegativity of the coefficients of skew Schubert polynomials,
and we conjecture a weight-preserving bijection between a modification of
certain diagrams used in our formulas and RC-graphs/pipe dreams arising in
formulas for double Schubert polynomials.

###### Key words and phrases:

Double Schubert polynomials, Schubert polynomials, structure constants,
Littlewood-Richardson, Pieri, factorial Schur polynomials, elementary
symmetric polynomials, RC-graphs, pipe dreams

###### 2020 Mathematics Subject Classification:

05E05, 05E14, 05A15, 05A05, 14N10

##  1\. Introduction

Schubert polynomials were originally defined by Lascoux and Schützenberger in
[19], and double Schubert polynomials are a generalization found in [21]. The
double Schubert polynomials are polynomials in two infinite sets of variables
$\\{x_{i}:i\in\mathbb{N}\\}$ and $\\{y_{i}:i\in\mathbb{N}\\}$ with integer
coefficients and are denoted by $\operatorname{\mathfrak{S}}_{u}(x;y)$ for
permutations $u$. Double Schubert polynomials are linearly independent and in
fact form a basis of the polynomial ring over the coefficient ring
$\mathbb{Z}[y]$. Double Schubert polynomials are interesting first and
foremost because they represent Schubert classes in the torus-equivariant
cohomology ring of the complete flag variety. If we introduce a third infinite
set of variables $\\{z_{i}:i\in\mathbb{N}\\}$, we may write the product of two
double Schubert polynomials with different sets of coefficient variables,
defining coefficients $c_{uv}^{w}(y;z)$ as follows:

$\operatorname{\mathfrak{S}}_{u}(x;y)\operatorname{\mathfrak{S}}_{v}(x;z)=\sum_{w\in
S_{\infty}}{c_{uv}^{w}(y;z)\operatorname{\mathfrak{S}}_{w}(x;y)}$

We have the following conjecture:

######  Conjecture 1.1.

For all $u,v,w$ we have that $c_{uv}^{w}(y;z)$ is a polynomial in the
differences $y_{i}-z_{j}$ with nonnegative integer coefficients.

At the time of this writing, we have computationally verified this conjecture
for all $u,v\in S_{5}$ for all $w\in S_{\infty}$. The truth of this conjecture
was demonstrated for factorial Schur functions in [23] via a Littlewood-
Richardson rule. $c_{uv}^{w}(0;0)$ is known to be nonnegative as these are the
structure constants in the ordinary cohomology of the complete flag variety,
which count points in triple intersections of Schubert varieties. No
combinatorial proof is known of this in general, but several widely applicable
combinatorial results are known; the full proof is obtained using algebraic
geometry. It is also known [9] via another algebraic geometry proof that
$c_{uv}^{w}(y;y)$ is a polynomial in the differences $y_{i+1}-y_{i}$ with
nonnegative integer coefficients, which was shown combinatorially for the
Grassmannian in [14] and for the two-step flag variety in [5]. It was
conjectured by Kirillov [12] (essentially) that $c_{uv}^{w}(y;0)$ is a
polynomial in $y$ with nonnegative integer coefficients for all $u,v,w$ and
proved in the same article that the conjecture holds when $\ell(u,w)=1$. This
is clearly a special case of Conjecture 1.1. We have verified Kirillov’s
conjecture, which is easier to test, for $u,v\in S_{7}$ for all $w\in
S_{\infty}$. Kirillov’s conjecture was presented in an alternative form by the
author on MathOverflow [10], and in a comment Dave Anderson suggested that we
likely have the tools to prove this with the current state of knowledge,
though as far as we know this has not yet been done. We present a
combinatorial proof of an additional special case (conjectured separately in
Kirillov’s article) in Theorem 5.2.

This article has two main results. The first, Theorem 3.1, is a positive
combinatorial formula for $c_{uv}^{w}(y;z)$ where there exists a positive
integer $p$ such that $\ell(us_{i})>\ell(u)$ whenever $i<p$ and
$\ell(vs_{i})>\ell(v)$ whenever $i>p$. Equivalently, it is a positive formula
as a polynomial in the differences $y_{i}-z_{j}$ for coefficients of
$\operatorname{\mathfrak{S}}_{w}(x;y)$ in the expansion of the product

$\operatorname{\mathfrak{S}}_{u}(x_{1},\ldots,x_{m};y)\operatorname{\mathfrak{S}}_{v}(x_{1},\ldots,x_{p};z)$

where $\operatorname{\mathfrak{S}}_{u}(x_{1},\ldots,x_{m};y)$ is symmetric in
the variables $x_{1},\ldots,x_{p}$. The formula when substituting to obtain
$c_{uv}^{w}(y;y)$ is also nonnegative (though some terms are $0$) in the sense
of [9], which we show in Theorem 6.1, thus also giving a positive formula for
ordinary double Schubert polynomial multiplication for these pairs of
permutations; all of the nonzero terms in the formula for $c_{uv}^{w}(y;y)$
are visibly polynomials in $y_{i+1}-y_{i}$ with nonnegative integer
coefficients.

The second main result, Theorem 7.1, is a Pieri formula for computing
$c_{uv}^{w}(y;z)$ when $v$ is a cycle of the form
$c_{p,k}=s_{k-p+1}s_{k-p+2}\cdots s_{k}$, in which case
$\operatorname{\mathfrak{S}}_{c_{p,k}}(x;z)$ is a factorial elementary
symmetric polynomial, for which we introduce the alternative notation
$E_{p,k}(x;z)$. This generalizes the main result of [27] and is closely
related to the equivariant Pieri formula in [25]. Via the formula in [23, (4)]
applied to a column shape, which we state here as an explicit formula for
$E_{p,k}(x;z)$ (Proposition 7.10), our Pieri formula is positive in the sense
of Conjecture 1.1 and also positive for $c_{uv}^{w}(y;y)$ in the sense of [9].

In Section 8 we state a more general result than Theorem 3.1 (Theorem 8.1)
that differs only in the choices of the permutations $u$ and $v$; the formula
is the same as that of the main result. Theorem 8.1 is the most general case
to which our method applies.

##  2\. Preliminaries

######  Definition 2.1 (The symmetric group).

There are many references regarding the algebraic combinatorics of symmetric
groups as Coxeter groups, for which we will cite [4]. We use the notation
$S_{\infty}$ for the infinite symmetric group of bijections
$\mathbb{N}\to\mathbb{N}$ fixing all but finitely many elements, with function
composition in the usual order being the operation, and $S_{n}<S_{\infty}$ is
the subgroup of all $u\in S_{\infty}$ such that $u(i)=i$ if $i>n$. We think of
elements of $S_{\infty}$ as sequences and refer to them as _permutations_.
Every element $u\in S_{\infty}$ is in $S_{n}$ for some $n$, and if $u\in
S_{n}$ we may write

$u=[u(1),u(2),\ldots,u(n)]$

(this is known as “window notation”). Clearly if $u\in S_{n}$ then $u\in
S_{N}$ for all $N>n$ as well.

$s_{i}\in S_{\infty}$ is the adjacent transposition (also known as a simple
reflection) exchanging the values $i$ and $i+1$, and $t_{ab}$ for positive
integers $a\neq b$ is the (not necessarily adjacent) transposition exchanging
$a$ and $b$ and fixing everything else. Note that we do not impose an order on
$a$ and $b$ in the definition of a transposition, so $t_{ab}=t_{ba}$. Every
element of $S_{\infty}$ can be written as a product of adjacent
transpositions. For $u\in S_{\infty}$, $us_{i}$ is $u$ with the indices $i$
and $i+1$ flipped, and $s_{i}u$ exchanges the values instead. The _length_
$\ell(u)$ is the number of inversions of $u$, the pairs of indices $(i,j)$
with $i<j$ such that $u(i)>u(j)$. For elements $u,w$ with $\ell(u)\leq\ell(w)$
we define $\ell(u,w)=\ell(w)-\ell(u)$. A _word_ for an element $u\in
S_{\infty}$ is a sequence of simple reflections

$(s_{i_{1}},\ldots,s_{i_{m}})$

such that

$s_{i_{1}}\cdots s_{i_{m}}=u$

and the word is said to be _reduced_ if it is as short as possible. It is well
known that a reduced word for $u$ is of length exactly $\ell(u)$. If
$u(i)>u(i+1)$, then $\ell(us_{i})=\ell(u)-1$, and if $u(i)<u(i+1)$ then
$\ell(us_{i})=\ell(u)+1$. Indices $i$ with $u(i)>u(i+1)$ are called _(right)
descents_ of $u$.

The _(right) weak Bruhat order_ $\leq$ on permutations is the partial ordering
that is the reflexive, transitive closure of the relation $v\trianglelefteq
vs_{i}$ whenever $\ell(vs_{i})=\ell(v)+1$. In general, if $v\leq w$, then
$\ell(v^{-1}w)=\ell(w)-\ell(v)$.

We denote by $w_{0}(n)$ the longest element (element with the most inversions)
of $S_{n+1}$. This is easily seen to be

$w_{0}(n)(i)=\begin{cases}n+2-i&\mbox{ if }i\leq n+1\\\ i&\mbox{ if
}i>n+1\end{cases}$

######  Definition 2.2 (Double Schubert polynomials, $\partial^{w}$,
$\partial_{u}^{w}$).

A simple definition of double Schubert polynomials is through divided
difference operators as defined in [3]. $S_{\infty}$ acts on the polynomial
ring by extending via automorphisms the rule

$u(x_{j})=x_{u(j)}$

We also insist that $u(y_{j})=y_{j}$ and $u(z_{j})=z_{j}$ for all $j$. We
define the divided difference operator $\partial^{s_{i}}$ by

$\partial^{s_{i}}(P)=\frac{P-s_{i}(P)}{x_{i}-x_{i+1}}$

It is well known that applying divided difference operators to a polynomial
yields a polynomial; this is proved, for example, in [26].

The divided difference operators can be composed to yield operators indexed by
the symmetric group, $\partial^{u}$ for $u\in S_{\infty}$, defined by

$\partial^{u}=\partial^{s_{i_{1}}}\cdots\partial^{s_{i_{\ell(u)}}}$

where $(s_{i_{1}},\ldots,s_{i_{\ell(u)}})$ is a reduced word for $u$. This
does not depend on the choice of reduced word. If $\ell(us_{i})>\ell(u)$, then

$\partial^{u}\partial^{s_{i}}=\partial^{us_{i}}$

If $\ell(us_{i})<\ell(u)$, then

$\partial^{u}\partial^{s_{i}}=0$

Divided difference operators satisfy the Leibniz formula

(2.1) $\partial^{s_{i}}(PQ)=\partial^{s_{i}}(P)s_{i}(Q)+P\partial^{s_{i}}(Q)$

which can be seen by direct computation. There exist skew divided difference
operators $\partial_{u}^{w}$ (the same as those defined in [26], differing by
a permutation from those in [21] and [12]) defined by the more general Leibniz
formula

$\partial^{w}(PQ)=\sum_{u}\partial^{u}(P)\partial_{u}^{w}(Q)$

We identify divided difference operators, group elements, and skew divided
difference operators with the corresponding elements of the nil-Hecke ring
[18], which is a free left module over $\mathbb{Z}[x]$ with basis
$\\{\partial^{u}\mid u\in S_{\infty}\\}$. For example,

$s_{i}=1+(x_{i+1}-x_{i})\partial^{s_{i}}$

It is shown in [26] that

$\partial_{u}^{w}=\sum_{v}c_{uv}^{w}(x;x)\partial^{v}$

More usefully for this article, skew divided difference operators satisfy the
following recurrence relation. For the base case,

$\partial_{1}^{1}=1$

and if $u\in S_{\infty}$ satisfies $u\neq 1$ then

$\partial_{u}^{1}=0$

Suppose $\ell(ws_{i})<\ell(w)$. If $\ell(us_{i})<\ell(u)$, then

$\partial_{u}^{w}=\partial_{u}^{ws_{i}}\partial^{s_{i}}+\partial_{us_{i}}^{ws_{i}}s_{i}$

and if $\ell(us_{i})>\ell(u)$ then

$\partial_{u}^{w}=\partial_{u}^{ws_{i}}\partial^{s_{i}}$

We define, for any $n>0$,

$\operatorname{\mathfrak{S}}_{w_{0}(n)}(x;y)=\prod_{i+j\leq n+1}(x_{i}-y_{j})$

Then the double Schubert polynomial $\operatorname{\mathfrak{S}}_{u}(x;y)$ for
$u\in S_{n+1}$ is given by

$\operatorname{\mathfrak{S}}_{u}(x;y)=\partial^{u^{-1}w_{0}(n)}(\operatorname{\mathfrak{S}}_{w_{0}(n)}(x;y))$

This definition is shown to yield a well-defined polynomial (i.e., not
depending on the choice of $n$) by Macdonald in [21].

Note that if $\ell(us_{i})>\ell(u)$, then
$\operatorname{\mathfrak{S}}_{u}(x;y)$ is symmetric in the variables $x_{i}$
and $x_{i+1}$ and

$\partial^{s_{i}}(\operatorname{\mathfrak{S}}_{u}(x;y))=0$

If $\ell(us_{i})<\ell(u)$, then

$\partial^{s_{i}}(\operatorname{\mathfrak{S}}_{u}(x;y))=\operatorname{\mathfrak{S}}_{us_{i}}(x;y)$

We also have the vanishing formula [21, (6.4)]

$\operatorname{\mathfrak{S}}_{u}(y;y)=\delta_{1,u}$

The collection of $\operatorname{\mathfrak{S}}_{u}(x;y)$ for $u\in S_{\infty}$
forms a basis for $\mathbb{Z}[x,y,z]$ as a module over $\mathbb{Z}[y,z]$, and
by the vanishing formula, applying the divided difference $\partial^{w}$ then
setting $x=y$ allows us to pull out the coefficient of
$\operatorname{\mathfrak{S}}_{w}(x;y)$ in the expansion of any polynomial in
$\mathbb{Z}[x,y,z]$.

The skew divided difference operators allow us to obtain coefficients of
products of arbitrary polynomials with double Schubert polynomials in $x$ and
$y$ as follows. Using the Leibniz formula, for an arbitrary polynomial $P$ and
a permutation $u$ we obtain

$\partial^{w}(P\operatorname{\mathfrak{S}}_{u}(x;y))=\sum_{v}\partial_{v}^{w}(P)\partial^{v}(\operatorname{\mathfrak{S}}_{u}(x;y))$

Again applying the vanishing formula, we obtain the result that substituting
$x=y$ in the polynomial $\partial_{u}^{w}(P)$ extracts the coefficient of
$\operatorname{\mathfrak{S}}_{w}(x;y)$ in the expansion of
$P\operatorname{\mathfrak{S}}_{u}(x;y)$. In particular, setting
$P=\operatorname{\mathfrak{S}}_{v}(x;z)$, we obtain

$c_{uv}^{w}(x;z)=\partial_{u}^{w}(\operatorname{\mathfrak{S}}_{v}(x;z))$

for all $u,v,w\in S_{\infty}$.

######  Definition 2.3 (Factorial Schur polynomials, Grassmannian
permutations).

A permutation $u\in S_{\infty}$ is said to be _Grassmannian_ if it has at most
one descent. A factorial Schur polynomial is a double Schubert polynomial
corresponding to a Grassmannian permutation [6, Theorem 4]. Factorial Schur
polynomials are indexed by partitions and denoted by
$s_{\lambda}(x_{1},\ldots,x_{m};y)$. The partition $\lambda$ together with the
value of $m$ determine the permutation for the double Schubert polynomial to
which $s_{\lambda}(x_{1},\ldots,x_{m};y)$ corresponds. Specifically, we define
a Grassmannian permutation $w_{\lambda;m}$ corresponding to the partition
$\lambda$ with descent at position $m$ as follows. Let

$\lambda=(\lambda_{1},\ldots,\lambda_{p})$

and suppose $m\geq p$. Define $\lambda_{i}=0$ if $i>p$, then let
$w_{\lambda;m}(i)=i+\lambda_{m+1-i}$ if $1\leq i\leq m$. The remainder of
$w_{\lambda;m}$ is the complement of $w_{\lambda;m}([m])$ arranged in
increasing order. For example,

$w_{(3,1,1);4}=[1,3,4,7,2,5,6]$

Given this definition of $w_{\lambda;m}$, we have the formula

$s_{\lambda}(x_{1},\ldots,x_{m};y)=\operatorname{\mathfrak{S}}_{w_{\lambda;m}}(x;y)$

The _factorial elementary symmetric polynomial_ $E_{p,k}(x;y)$ is the special
case $s_{(1^{p})}(x_{1},\ldots,x_{k};y)$, about which we go into much more
detail below.

Molev and Sagan’s Littlewood-Richardson rule [23] computes the product of two
factorial Schur polynomials
$s_{\lambda}(x_{1},\ldots,x_{m};y)s_{\mu}(x_{1},\ldots,x_{m};z)$ where the
corresponding permutations have the same descent, i.e. the polynomials have
the same number of $x$ variables.

######  Definition 2.4 (The code $\mathfrak{c}(v)$, dominant permutations, the
dominant approximation $\mu_{v}$, and the partition $\lambda(v)$).

We define the _code_ $\mathfrak{c}(v)$ of a permutation $v\in S_{\infty}$, a
sequence indexed by $i\geq 1$, as follows:

$\mathfrak{c}_{i}(v)=\\#\\{j>i\mid v(i)>v(j)\\}$

Note that if $v\in S_{n+1}$, then $\mathfrak{c}_{i}(v)\leq n+1-i$, and it is
not hard to see that

$\ell(v)=\sum_{i=1}^{\infty}\mathfrak{c}_{i}(v)$

Also, $\ell(vs_{i})=\ell(v)+1$ if and only if
$\mathfrak{c}_{i}(v)\leq\mathfrak{c}_{i+1}(v)$, in which case
$\mathfrak{c}_{i}(vs_{i})=\mathfrak{c}_{i+1}(v)+1$,
$\mathfrak{c}_{i+1}(vs_{i})=\mathfrak{c}_{i}(v)$, and
$\mathfrak{c}_{j}(vs_{i})=\mathfrak{c}_{j}(v)$ for $j\notin\\{i,i+1\\}$.

A permutation $v$ is said to be _dominant_ if $\mathfrak{c}(v)$ is a
partition. For $v\in S_{\infty}$, we define a dominant permutation $\mu_{v}$,
the _dominant approximation_ of $v$, as follows. If $v$ is dominant, let
$\mu_{v}=v$. If $v$ is not dominant, let $i$ be the maximal index such that
$\mathfrak{c}_{i}(v)<\mathfrak{c}_{i+1}(v)$, and define
$\mu_{v}=\mu_{vs_{i}}$. It is clear that this recursion terminates in a unique
dominant permutation. Note that at each step $\ell(vs_{i})=\ell(v)+1$, so that
$v\leq\mu_{v}$ and hence $\ell(v^{-1}\mu_{v})=\ell(\mu_{v})-\ell(v)$. Define a
partition $\lambda(v)$ to be the conjugate of the code of $\mu_{v}$, meaning

$\lambda_{i}(v)=\\#\\{j\mid\mathfrak{c}_{j}(\mu_{v})\geq i\\}$

######  Example 2.1.

Let $v=[1,3,5,2,4]$. Then

$\mathfrak{c}(v)=(0,1,2)$

In the recursion computing the dominant approximation, the first reflection to
apply is at index $2$. We have that

$vs_{2}=[1,5,3,2,4]$

and

$\mathfrak{c}(vs_{2})=(0,3,1)$

Continuing in this manner, we obtain that the remaining reflections are
$s_{1},s_{2}$, and hence $\mu_{v}=vs_{2}s_{1}s_{2}$. We have

$\mu_{v}=[5,3,1,2,4]$ $\mathfrak{c}(\mu_{v})=(4,2)$

which is a partition. $\lambda(v)$ is the conjugate partition, namely

$\lambda(v)=(2,2,1,1)$

######  Definition 2.5 ($\xrightarrow{k}$, $P_{k}(u,w)$,
$\mathrm{Path}_{\lambda}(u,w)$, $\mathrm{weight}_{P,\lambda}(y;z)$).

We define a relation $\xrightarrow{k}$ on pairs of permutations, introduced by
Sottile [27], which was used originally to indicate when the coefficient of a
Schubert polynomial is nonzero in a suitable application of the Pieri formula.
In the generalization to double Schubert polynomials in [25], the same
relation applies to all nonzero coefficients in the expansion of the
generalized Pieri formula. The relation plays the same role in our case.

Given $u,u^{\prime}\in S_{\infty}$ and a positive integer $k$, we declare that
$u\xrightarrow{k}u^{\prime}$ if there exists a $p$ with $0\leq p\leq k$ such
that there are transpositions $t_{a_{1}b_{1}},\ldots,t_{a_{p}b_{p}}$
satisfying

  1. (1)

$a_{i}\leq k<b_{i}$ for all $i$

  2. (2)

$a_{i}\neq a_{j}$ whenever $i\neq j$

  3. (3)

$\ell(ut_{a_{1}b_{1}}\cdots t_{a_{i}b_{i}})=\ell(u)+i$ for all $i$

  4. (4)

$u^{\prime}=ut_{a_{1}b_{1}}\cdots t_{a_{p}b_{p}}$

If $u\xrightarrow{k}w$, define

$P_{k}(u,w)=\\{u(i)\mid i\leq k\mbox{ and }u(i)=w(i)\\}$

For an integer $j$ we define the weight of this interval by

$\mathrm{weight}_{u,k}^{w}(y;z_{j})=\prod_{i\in P_{k}(u,w)}(y_{i}-z_{j})$

where by convention the empty product is $1$.

Given $u,w\in S_{\infty}$ and a partition $\lambda$ of length $m$, define
$\mathrm{Path}_{\lambda}(u,w)$ to be the set of sequences defined by

$\mathrm{Path}_{\lambda}(u,w)=\\{(u_{0},u_{1},\ldots,u_{m})\mid
u=u_{0}\xrightarrow{\lambda_{1}}u_{1}\xrightarrow{\lambda_{2}}\cdots\xrightarrow{\lambda_{m}}u_{m}=w\\}$

Then given such a path $P$ and the partition $\lambda$ we define

$\mathrm{weight}_{P,\lambda}(y;z)=\prod_{i=1}^{m}\mathrm{weight}_{u_{i-1},\lambda_{i}}^{u_{i}}(y;z_{i})$

For illustration in examples, we will represent the elements of
$\mathrm{Path}_{\lambda}(u,w)$ with certain diagrams of numbers. In the
diagrams, the permutations $(u_{0},\ldots,u_{m})$ in the paths will be written
vertically in each column, with the columns progressing according to the
permutations in the path from left to right. More specifically, the element
$u_{j}(i)$ at the $i$th index in the permutation $u_{j}$ will be in row $i$
and column $j$, with the column numbers starting at $0$ and row numbers
starting at $1$. In column $j$, a horizontal line will be drawn below row
$\lambda_{j}$. The entries that contribute factors to the weight are those
where $u_{j-1}(i)=u_{j}(i)$ for rows $i$ above the horizontal line in column
$j$, meaning the number is the same as the number in the same row in the
column immediately to the left. These entries will be circled in the diagram.
The circled entries in column $j$ represent elements of
$P_{\lambda_{j}}(u_{j-1},u_{j})$. If the circled number is $i$ (the value, not
the row number) in column $j$, a term of $y_{i}-z_{j}$ will occur as a factor
in the product computing the weight of the path. The weight
$\mathrm{weight}_{P,\lambda}(y;z)$ will be written beneath the diagram.

######  Example 2.2.

Let $\lambda=(3,2,2)$. Then

$P=([1,3,4,2],[1,3,5,2,4],[3,5,1,2,4],[4,5,1,2,3])$

is in $\mathrm{Path}_{\lambda}([1,3,4,2],[4,5,1,2,3])$. This corresponds to
the following diagram.

1 | 1 | 3 | 4
---|---|---|---
3 | 3 | 5 | 5
4 | 5 | 1 | 1
2 | 2 | 2 | 2
5 | 4 | 4 | 3
$(y_{1}-z_{1})(y_{3}-z_{1})(y_{5}-z_{3})$

$\mathrm{weight}_{P,\lambda}(y;z)$ is written beneath the diagram.
$(y_{1}-z_{1})(y_{3}-z_{1})$ corresponds to the circled $1$ and $3$ in column
$1$ and $y_{5}-z_{3}$ corresponds to the circled $5$ in column $3$.

##  3\. The first formula

######  Definition 3.1 ($d_{u,\lambda}^{w}(y;z)$, $e_{uv}^{w}(y;z)$).

Given permutations $u,w\in S_{\infty}$ and a partition $\lambda$ we define a
polynomial $d_{u,\lambda}^{w}(y;z)$ with nonnegative integer coefficients in
terms of products of linear terms of the form $y_{i}-z_{j}$ as follows:

$d_{u,\lambda}^{w}(y;z)=\sum_{P\in\mathrm{Path}_{\lambda}(u,w)}\mathrm{weight}_{P,\lambda}(y;z)$

We define coefficients $e_{uv}^{w}(y;z)$ as follows. If $u,v,w\in S_{\infty}$,
define

$e_{uv}^{w}(y;z)=0$

unless $\ell(wv^{-1}\mu_{v})=\ell(w)+\ell(v^{-1}\mu_{v})$, in which case
define

$e_{uv}^{w}(y;z)=d_{u,\lambda(v)}^{wv^{-1}\mu_{v}}(y;z)$

######  Theorem 3.1.

Let $u,v\in S_{\infty}$ be such that there exists a $p>0$ for which
$\ell(us_{i})>\ell(u)$ for all $i<p$ and $\ell(vs_{i})>\ell(v)$ for all $i>p$.
Then

$\operatorname{\mathfrak{S}}_{u}(x;y)\operatorname{\mathfrak{S}}_{v}(x;z)=\sum_{w\in
S_{\infty}}e_{uv}^{w}(y;z)\operatorname{\mathfrak{S}}_{w}(x;y)$

The condition on $u$ and $v$ in the statement of Theorem 3.1 is referred to as
$u$ and $v$ having “separated descents” in [15], for which a puzzle rule is
found for the coefficients $c_{uv}^{w}(0;0)$, a case that is also covered in
[11]. In a more recent paper, [16] extends this to equivariant K-theory. The
main result of [8] is a similar formula for double Grothendieck polynomials,
which also gives a positive formula for the $z=0$ case in the coefficients we
consider.

We illustrate this with some examples.

######  Example 3.1.

We compute the example using factorial Schur functions in [14, 6.4]. Let
$u=v=[1,3,2]$, and we first let $w=[1,3,2]$. Then

$\displaystyle\mu_{v}$ $\displaystyle=[3,1,2]$
$\displaystyle\mathfrak{c}(\mu_{v})$ $\displaystyle=(2)$
$\displaystyle\lambda(v)$ $\displaystyle=(1,1)$ $\displaystyle v^{-1}\mu_{v}$
$\displaystyle=[2,1]$ $\displaystyle wv^{-1}\mu_{v}$ $\displaystyle=[3,1,2]$

Then $c_{uv}^{w}(y;z)=(y_{3}-z_{2})+(y_{1}-z_{1})$, as witnessed by the
following paths.

1 | 3 | 3
---|---|---
3 | 1 | 1
2 | 2 | 2
$y_{3}-z_{2}$
1 | 1 | 3
---|---|---
3 | 3 | 1
2 | 2 | 2
$y_{1}-z_{1}$

The reference computes the result as $(y_{3}-z_{1})+(y_{1}-z_{2})$ instead,
which of course yields the same result but differs from our formula in the
terms produced by the combinatorial elements. As we show in Theorem 6.1, our
formula has the advantage that it yields a positive formula in equivariant
cohomology when $y$ is substituted for $z$; this is not the case for
$(y_{3}-y_{1})+(y_{1}-y_{2})$, as $y_{1}-y_{2}$ is not a positive term in the
sense of [9]. Our formula gives $(y_{3}-y_{2})+(y_{1}-y_{1})$, and both terms
are nonnegative. We note that Molev in [22] provides a positive formula
stemming from Molev and Sagan’s rule.

For the remaining paths we write $w$ at the top of the diagram to save space.

$[1,4,2,3]$
---
1 | 3 | 4
3 | 1 | 1
2 | 2 | 2
4 | 4 | 3
$1$
$[2,3,1]$
---
1 | 2 | 3
3 | 3 | 2
2 | 1 | 1
$1$

Thus

$\operatorname{\mathfrak{S}}_{[1,3,2]}(x;y)\operatorname{\mathfrak{S}}_{[1,3,2]}(x;z)=((y_{3}-z_{2})+(y_{1}-z_{1}))\operatorname{\mathfrak{S}}_{[1,3,2]}(x;y)+\operatorname{\mathfrak{S}}_{[1,4,2,3]}(x;y)+\operatorname{\mathfrak{S}}_{[2,3,1]}(x;y)$

which agrees with [14].

######  Example 3.2.

We compute the product of two factorial Schur polynomials with different
numbers of $x$ variables, namely
$s_{(2,1)}(x_{1},x_{2},x_{3};y)s_{(2)}(x_{1},x_{2};z)$. This is the product
$\operatorname{\mathfrak{S}}_{[1,3,5,2,4]}(x;y)\operatorname{\mathfrak{S}}_{[1,4,2,3]}(x;z)$.
Notice that in this level of generality our formula cannot compute the product
in the opposite order.

$\displaystyle\mu_{v}$ $\displaystyle=[4,1,2,3]$
$\displaystyle\mathfrak{c}(\mu_{v})$ $\displaystyle=(3)$
$\displaystyle\lambda(v)$ $\displaystyle=(1,1,1)$ $\displaystyle
v^{-1}\mu_{v}$ $\displaystyle=[2,1]$ $[1,3,5,2,4]$
---
1 | 3 | 3 | 3
3 | 1 | 1 | 1
5 | 5 | 5 | 5
2 | 2 | 2 | 2
4 | 4 | 4 | 4
$(y_{3}-z_{2})(y_{3}-z_{3})$

$[1,3,5,2,4]$ 1 1 3 3 3 3 1 1 5 5 5 5 2 2 2 2 4 4 4 4
$(y_{1}-z_{1})(y_{3}-z_{3})$ $[1,3,5,2,4]$ 1 1 1 3 3 3 3 1 5 5 5 5 2 2 2 2 4 4
4 4 $(y_{1}-z_{1})(y_{1}-z_{2})$

$((y_{3}-z_{2})(y_{3}-z_{3})+(y_{1}-z_{1})(y_{3}-z_{3})+(y_{1}-z_{1})(y_{1}-z_{2}))\operatorname{\mathfrak{S}}_{[1,3,5,2,4]}(x;y)$
$[1,4,5,2,3]$
---
1 | 3 | 3 | 4
3 | 1 | 1 | 1
5 | 5 | 5 | 5
2 | 2 | 2 | 2
4 | 4 | 4 | 3
$y_{3}-z_{2}$
$[1,4,5,2,3]$
---
1 | 3 | 4 | 4
3 | 1 | 1 | 1
5 | 5 | 5 | 5
2 | 2 | 2 | 2
4 | 4 | 3 | 3
$y_{4}-z_{3}$
$[1,4,5,2,3]$
---
1 | 1 | 3 | 4
3 | 3 | 1 | 1
5 | 5 | 5 | 5
2 | 2 | 2 | 2
4 | 4 | 4 | 3
$y_{1}-z_{1}$
$((y_{3}-z_{2})+(y_{4}-z_{3})+(y_{1}-z_{1}))\operatorname{\mathfrak{S}}_{[1,4,5,2,3]}(x;y)$
$[2,3,5,1,4]$
---
1 | 1 | 2 | 3
3 | 3 | 3 | 2
5 | 5 | 5 | 5
2 | 2 | 1 | 1
4 | 4 | 4 | 4
$y_{1}-z_{1}$
$[2,3,5,1,4]$
---
1 | 2 | 2 | 3
3 | 3 | 3 | 2
5 | 5 | 5 | 5
2 | 1 | 1 | 1
4 | 4 | 4 | 4
$y_{2}-z_{2}$
$[2,3,5,1,4]$
---
1 | 2 | 3 | 3
3 | 3 | 2 | 2
5 | 5 | 5 | 5
2 | 1 | 1 | 1
4 | 4 | 4 | 4
$y_{3}-z_{3}$
$((y_{1}-z_{1})+(y_{2}-z_{2})+(y_{3}-z_{3}))\operatorname{\mathfrak{S}}_{[2,3,5,1,4]}(x;y)$
$[1,5,3,2,4]$
---
1 | 1 | 3 | 5
3 | 3 | 1 | 1
5 | 5 | 5 | 3
2 | 2 | 2 | 2
4 | 4 | 4 | 4
$y_{1}-z_{1}$
$[1,5,3,2,4]$
---
1 | 3 | 5 | 5
3 | 1 | 1 | 1
5 | 5 | 3 | 3
2 | 2 | 2 | 2
4 | 4 | 4 | 4
$y_{5}-z_{3}$
$[1,5,3,2,4]$
---
1 | 3 | 3 | 5
3 | 1 | 1 | 1
5 | 5 | 5 | 3
2 | 2 | 2 | 2
4 | 4 | 4 | 4
$y_{3}-z_{2}$
$((y_{1}-z_{1})+(y_{5}-z_{3})+(y_{3}-z_{2}))\operatorname{\mathfrak{S}}_{[1,5,3,2,4]}(x;y)$
$[1,5,4,2,3]$
---
1 | 3 | 4 | 5
3 | 1 | 1 | 1
5 | 5 | 5 | 4
2 | 2 | 2 | 2
4 | 4 | 3 | 3
$1$
$[2,4,5,1,3]$
---
1 | 2 | 3 | 4
3 | 3 | 2 | 2
5 | 5 | 5 | 5
2 | 1 | 1 | 1
4 | 4 | 4 | 3
$1$
$[2,5,3,1,4]$
---
1 | 2 | 3 | 5
3 | 3 | 2 | 2
5 | 5 | 5 | 3
2 | 1 | 1 | 1
4 | 4 | 4 | 4
$1$
$[1,6,3,2,4,5]$
---
1 | 3 | 5 | 6
3 | 1 | 1 | 1
5 | 5 | 3 | 3
2 | 2 | 2 | 2
4 | 4 | 4 | 4
6 | 6 | 6 | 5
$1$
$\operatorname{\mathfrak{S}}_{[1,5,4,2,3]}(x;y)+\operatorname{\mathfrak{S}}_{[2,4,5,1,3]}(x;y)+\operatorname{\mathfrak{S}}_{[2,5,3,1,4]}(x;y)+\operatorname{\mathfrak{S}}_{[1,6,3,2,4,5]}(x;y)$

######  Example 3.3.

Our formula computes the product of the double Schubert polynomial
$\operatorname{\mathfrak{S}}_{[1,4,3,2]}(x;y)$, which is not a factorial Schur
polynomial, with the factorial Schur polynomial $s_{(2,1)}(x_{1},x_{2};z)$. We
set $u=[1,4,3,2]$, $v=[2,4,1,3]$. We compute the coefficient where
$w=[3,4,1,2]$. We have

$\displaystyle\mu_{v}$ $\displaystyle=[4,2,1,3]$ $\displaystyle\mathfrak{c}(\mu_{v})$ $\displaystyle=(3,1)$ $\displaystyle\lambda(v)$ $\displaystyle=(2,1,1)$ $\displaystyle v^{-1}\mu_{v}$ $\displaystyle=[2,1]$ $\displaystyle wv^{-1}\mu_{v}$ $\displaystyle=[4,3,1,2]$ 1 | 1 | 3 | 4
---|---|---|---
4 | 4 | 4 | 3
3 | 3 | 1 | 1
2 | 2 | 2 | 2
$(y_{1}-z_{1})(y_{4}-z_{1})$

1 3 3 4 4 4 4 3 3 1 1 1 2 2 2 2 $(y_{3}-z_{2})(y_{4}-z_{1})$ 1 3 4 4 4 4 3 3 3
1 1 1 2 2 2 2 $(y_{4}-z_{1})(y_{4}-z_{3})$

Thus

$c_{uv}^{w}(y;z)=(y_{1}-z_{1})(y_{4}-z_{1})+(y_{3}-z_{2})(y_{4}-z_{1})+(y_{4}-z_{1})(y_{4}-z_{3})$

Now we compute the coefficient for $w=[3,5,1,2,4]$. We have
$wv^{-1}\mu_{v}=[5,3,1,2,4]$.

1 | 1 | 3 | 5
---|---|---|---
4 | 5 | 5 | 3
3 | 3 | 1 | 1
2 | 2 | 2 | 2
5 | 4 | 4 | 4
$y_{1}-z_{1}$

1 3 3 5 4 5 5 3 3 1 1 1 2 2 2 2 5 4 4 4 $y_{3}-z_{2}$ 1 3 4 5 4 4 3 3 3 1 1 1
2 2 2 2 5 5 5 4 $y_{4}-z_{1}$ 1 3 5 5 4 5 3 3 3 1 1 1 2 2 2 2 5 4 4 4
$y_{5}-z_{3}$

Thus

$c_{uv}^{w}(y;z)=(y_{1}-z_{1})+(y_{3}-z_{2})+(y_{4}-z_{1})+(y_{5}-z_{3})$

##  4\. Proof of Theorem 3.1

We show in this section that if $u$ and $v$ satisfy the hypotheses of Theorem
3.1, then we may reduce multiplying $\operatorname{\mathfrak{S}}_{u}(x;y)$ by
$\operatorname{\mathfrak{S}}_{v}(x;z)$ to multiplying
$\operatorname{\mathfrak{S}}_{u}(x;y)$ by the double Schubert polynomial
corresponding to $v$’s dominant approximation,
$\operatorname{\mathfrak{S}}_{\mu_{v}}(x;z)$. We then show that a double
Schubert polynomial corresponding to a dominant permutation is a product of
factorial elementary symmetric polynomials, which will allow us to reduce the
computation to applying the Pieri formula. The special case of the Pieri
formula that we will need is Proposition 4.4, which we will prove in Section
7.

######  Lemma 4.1.

Let $u,v,w\in S_{\infty}$, and suppose $i>0$ is such that
$\ell(ws_{i})<\ell(w)$. If $\ell(us_{i})>\ell(u)$ and $\ell(vs_{i})>\ell(v)$,
then $c_{uv}^{w}(y;z)=0$.

###### Proof.

Recall that

$c_{uv}^{w}(x;z)=\partial_{u}^{w}(\operatorname{\mathfrak{S}}_{v}(x;z))$

Since $\ell(us_{i})>\ell(u)$ we have that

$\partial_{u}^{w}=\partial_{u}^{ws_{i}}\partial^{s_{i}}$

Since $\partial^{s_{i}}(\operatorname{\mathfrak{S}}_{v}(x;z))=0$, we have the
result. ∎

######  Lemma 4.2.

Let $u,v,w\in S_{\infty}$ and let $i>0$ be such that $\ell(us_{i})>\ell(u)$,
$\ell(vs_{i})>\ell(v)$, and $\ell(ws_{i})>\ell(w)$. Then

$c_{uv}^{w}(y;z)=c_{u,vs_{i}}^{ws_{i}}(y;z)$

###### Proof.

We have that

$\partial_{u}^{ws_{i}}=\partial_{u}^{w}\partial^{s_{i}}$

Hence

$\partial_{u}^{ws_{i}}(\operatorname{\mathfrak{S}}_{vs_{i}}(x;z))=\partial_{u}^{w}(\partial^{s_{i}}(\operatorname{\mathfrak{S}}_{vs_{i}}(x;z)))=\partial_{u}^{w}(\operatorname{\mathfrak{S}}_{v}(x;z))$

and the result follows. ∎

######  Proposition 4.3.

Suppose $p$ is a positive integer, $u\in S_{\infty}$ satisfies
$\ell(us_{i})>\ell(u)$ for all $i<p$, and $v\in S_{\infty}$ satisfies
$\ell(vs_{i})>\ell(v)$ for all $i>p$. Then $c_{uv}^{w}(y;z)=0$ unless
$\ell(wv^{-1}\mu_{v})=\ell(w)+\ell(v^{-1}\mu_{v})$, in which case

$c_{uv}^{w}(y;z)=c_{u,\mu_{v}}^{wv^{-1}\mu_{v}}(y;z)$

###### Proof.

Note that for any permutation $v$ we have that $\ell(vs_{i})>\ell(v)$ for all
$i>p$ if and only if $\mathfrak{c}_{i}(v)=0$ for all $i>p$. We prove the
result by induction on $\ell(\mu_{v})-\ell(v)$. If $\ell(\mu_{v})-\ell(v)=0$,
then $c_{uv}^{w}(y;z)=c_{u,\mu_{v}}^{wv^{-1}\mu_{v}}(y;z)$ because
$v^{-1}\mu_{v}=1$ and $v=\mu_{v}$. Otherwise, suppose $i$ is the maximal index
such that $\mathfrak{c}_{i}(v)<\mathfrak{c}_{i+1}(v)$. Since
$\mathfrak{c}_{i+1}(v)\neq 0$, we must have that $i<p$. Therefore, by
assumption $\ell(us_{i})>\ell(u)$. Also, since
$\mathfrak{c}_{j}(v)=\mathfrak{c}_{j}(vs_{i})=0$ for all $j>p$, it follows
that $\ell(vs_{i}s_{j})>\ell(vs_{i})$ for all $j>p$.

We split the argument into whether or not $\ell(ws_{i})<\ell(w)$. Assume first
that $\ell(ws_{i})<\ell(w)$. Note that $v^{-1}\mu_{v}$ has a specific
expression as a product of $\ell(\mu_{v})-\ell(v)$ simple reflections (the
ones that occur in the recursion passing from $v$ to $\mu_{v}$), with the
first being $s_{i}$, and in order for $w(v^{-1}\mu_{v})$ to have length
$\ell(w)+\ell(v^{-1}\mu_{v})$ each of these must successively increase the
length by $1$ in the multiplication of $w$ on the right by $v^{-1}\mu_{v}$.
Since the length decreases upon multiplication by the first reflection
$s_{i}$, we must have that $\ell(wv^{-1}\mu_{v})<\ell(w)+\ell(v^{-1}\mu_{v})$.
By Lemma 4.1 we also have that $c_{uv}^{w}(y;z)=0$ since both
$\ell(us_{i})>\ell(u)$ and $\ell(vs_{i})>\ell(v)$. Thus, if
$\ell(ws_{i})<\ell(w)$ then $c_{uv}^{w}(y;z)=0$ and
$\ell(wv^{-1}\mu_{v})<\ell(w)+\ell(v^{-1}\mu_{v})$, so the result follows in
that case.

Assume then that $\ell(ws_{i})>\ell(w)$. In that case, by Lemma 4.2,
$c_{uv}^{w}(y;z)=c_{u,vs_{i}}^{ws_{i}}(y;z)$. We have that
$\mu_{vs_{i}}=\mu_{v}$ by definition, and
$\ell(\mu_{v})-\ell(vs_{i})<\ell(\mu_{v})-\ell(v)$. Note that

$wv^{-1}\mu_{v}=w(s_{i}s_{i})v^{-1}\mu_{v}=ws_{i}(vs_{i})^{-1}\mu_{v}$

By the induction hypothesis, we have that $c_{u,vs_{i}}^{ws_{i}}(y;z)=0$
unless

$\ell(wv^{-1}\mu_{v})=\ell(ws_{i}(vs_{i})^{-1}\mu_{v})=\ell(ws_{i})+\ell((vs_{i})^{-1}\mu_{v})=\ell(w)+\ell(v^{-1}\mu_{v})$

In the case where the length condition is satisfied (where there is a
possibility that $c_{u,vs_{i}}^{ws_{i}}(y;z)\neq 0$), by the induction
hypothesis we have that

$c_{uv}^{w}(y;z)=c_{u,vs_{i}}^{ws_{i}}(y;z)=c_{u,\mu_{vs_{i}}}^{ws_{i}(vs_{i})^{-1}\mu_{vs_{i}}}(y;z)=c_{u,\mu_{v}}^{wv^{-1}\mu_{v}}(y;z)$

and it follows that $c_{uv}^{w}(y;z)=0$ unless
$\ell(wv^{-1}\mu_{v})=\ell(w)+\ell(v^{-1}\mu_{v})$, in which case
$c_{uv}^{w}(y;z)=c_{u,\mu_{v}}^{wv^{-1}\mu_{v}}(y;z)$.

Having verified in the two exhaustive cases $\ell(ws_{i})<\ell(w)$ and
$\ell(ws_{i})>\ell(w)$ that the result follows after the increase in length
difference from the induction hypothesis, we have the result by induction. ∎

######  Definition 4.1 (Factorial elementary symmetric polynomials
$E_{k}(x;z)$, $E_{p,k}(x;z)$).

Let $E_{k}(x;z)$ be the factorial elementary symmetric polynomial defined by

$E_{k}(x;z)=\prod_{i=1}^{k}(x_{i}-z_{1})$

This is the double Schubert polynomial
$\operatorname{\mathfrak{S}}_{c_{k,k}}(x;z)$ where

$c_{p,k}=s_{k+1-p}s_{k+2-p}\cdots s_{k}$

We define more generally

$E_{p,k}(x;z)=\operatorname{\mathfrak{S}}_{c_{p,k}}(x;z)$

so that $E_{k}(x;z)=E_{k,k}(x;z)$. If $p<0$ or $p>k$, we define

$E_{p,k}(x;z)=0$

Since exactly one $z$ variable occurs in the product for $E_{k}(x;z)$, namely
$z_{1}$, we use the notation $E_{k}(x;z_{j})$ for any $j$ to substitute
$z_{j}$ for $z_{1}$.

######  Proposition 4.4.

Let $j,k$ be positive integers and suppose $u\in S_{\infty}$. Then

$\operatorname{\mathfrak{S}}_{u}(x;y)E_{k}(x;z_{j})=\sum_{u\xrightarrow{k}w}\mathrm{weight}_{u,k}^{w}(y;z_{j})\operatorname{\mathfrak{S}}_{w}(x;y)$

We postpone the proof of this to Section 7.

The next lemma, for which we cite [21, (6.14)], expresses the double Schubert
polynomial corresponding to a dominant permutation as a product of these
factorial elementary symmetric polynomials.

######  Lemma 4.5.

Suppose $v\in S_{\infty}$. Then

$\operatorname{\mathfrak{S}}_{\mu_{v}}(x;z)=\prod_{i=1}^{\infty}E_{\lambda_{i}(v)}(x;z_{i})$

###### Proof.

In [21, (6.14)] there is a formula for the double Schubert polynomial
corresponding to a dominant permutation $\mu$ in terms of the coordinates of
the boxes in the Young diagram of $\mathfrak{c}(\mu)$. The formula is

$\operatorname{\mathfrak{S}}_{\mu_{v}}(x;z)=\prod_{(i,j)\in
Y_{\mathfrak{c}(\mu_{v})}}(x_{i}-z_{j})$

If we fix $j$ and consider the terms involving $z_{j}$ in this product, the
terms that occur are $x_{i}-z_{j}$ where $1\leq i\leq\lambda_{j}(v)$, since
the length of this column in the diagram is the value at the corresponding
index in the conjugate partition of the code. The product of these terms is
therefore equal to $E_{\lambda_{j}(v)}(x;z_{j})$. Iterating over $j$, we
obtain the result. ∎

From this we may derive the following.

######  Proposition 4.6.

Suppose $u,v\in S_{\infty}$. Then

$\operatorname{\mathfrak{S}}_{u}(x;y)\operatorname{\mathfrak{S}}_{\mu_{v}}(x;z)=\sum_{w\in
S_{\infty}}d_{u,\lambda(v)}^{w}(y;z)\operatorname{\mathfrak{S}}_{w}(x;y)$

###### Proof.

Assume the length of the partition $\lambda(v)$ is $m$. To shorten notation,
for an integer $0\leq p\leq m$ define a partition $\lambda^{p}$ as

$\lambda^{p}=(\lambda_{1}(v),\ldots,\lambda_{p}(v))$

We note by Lemma 4.5 that

$\operatorname{\mathfrak{S}}_{\mu_{v}}(x;z)=\prod_{i=1}^{m}E_{\lambda_{i}(v)}(x;z_{i})$

We apply Proposition 4.4 and induction to successively multiply by the factors
of $\operatorname{\mathfrak{S}}_{\mu_{v}}(x;z)$. The statement we will prove
is that for $0\leq p\leq m$ we have

$\operatorname{\mathfrak{S}}_{u}(x;y)E_{\lambda_{1}(v)}(x;z_{1})\cdots
E_{\lambda_{p}(v)}(x;z_{p})=\sum_{w}d_{u,\lambda^{p}}^{w}(y;z)\operatorname{\mathfrak{S}}_{w}(x;y)$

For the base case, multiplying by none of the factors, the product is
$\operatorname{\mathfrak{S}}_{u}(x;y)$. Assume the induction hypothesis that
for some $p$ with $p-1<m$ we have

$\operatorname{\mathfrak{S}}_{u}(x;y)E_{\lambda_{1}(v)}(x;z_{1})\cdots
E_{\lambda_{p-1}(v)}(x;z_{p-1})=\sum_{w}d_{u,\lambda^{p-1}}^{w}(y;z)\operatorname{\mathfrak{S}}_{w}(x;y)$

We multiply both sides by the additional factor $E_{\lambda_{p}(v)}(x;z_{p})$,
applying Proposition 4.4:

$\operatorname{\mathfrak{S}}_{u}(x;y)E_{\lambda_{1}(v)}(x;z_{1})\cdots
E_{\lambda_{p}(v)}(x;z_{p})=\sum_{w}\sum_{w^{\prime}:w\xrightarrow{\lambda_{p}(v)}w^{\prime}}d_{u,\lambda^{p-1}}^{w}(y;z)\mathrm{weight}_{w,\lambda_{p}(v)}^{w^{\prime}}(y;z_{p})\operatorname{\mathfrak{S}}_{w^{\prime}}(x;y)$

Interchange the order of summation on the right hand side to obtain that the
coefficient of $\operatorname{\mathfrak{S}}_{w^{\prime}}(x;y)$ is, fixing
$w^{\prime}$ and summing over all $w$,

$\sum_{w:w\xrightarrow{\lambda_{p}(v)}w^{\prime}}d_{u,\lambda^{p-1}}^{w}(y;z)\mathrm{weight}_{w,\lambda_{p}(v)}^{w^{\prime}}(y;z_{p})$

We claim that this is equal to $d_{u,\lambda^{p}}^{w^{\prime}}(y;z)$. Recall
that $d_{u,\lambda^{p-1}}^{w}(y;z)$ is a sum over paths

$u=u_{0}\xrightarrow{\lambda_{1}(v)}u_{1}\xrightarrow{\lambda_{2}(v)}\cdots\xrightarrow{\lambda_{p-1}(v)}u_{p-1}=w$

of the product

$\prod_{i=1}^{p-1}\mathrm{weight}_{u_{i-1},\lambda_{i}(v)}^{u_{i}}(y;z_{i})$

We are extending each path by an additional edge
$w\xrightarrow{\lambda_{p}(v)}w^{\prime}$. As this ranges over all $w$ (the
penultimate element in the path), we obtain exactly the paths that occur in
the sum for $d_{u,\lambda^{p}}^{w^{\prime}}(y;z)$ with the desired extra
factor occurring in the weight, obtaining the result by induction. ∎

###### Proof of Theorem 3.1.

By Proposition 4.3, we have under the conditions that $c_{uv}^{w}(y;z)=0$
unless $\ell(wv^{-1}\mu_{v})=\ell(w)+\ell(v^{-1}\mu_{v})$, in which case we
have

$c_{uv}^{w}(y;z)=c_{u,\mu_{v}}^{wv^{-1}\mu_{v}}(y;z)$

By Proposition 4.6 we have that

$\operatorname{\mathfrak{S}}_{u}(x;y)\operatorname{\mathfrak{S}}_{\mu_{v}}(x;z)=\sum_{w^{\prime}\in
S_{\infty}}{d_{u,\lambda(v)}^{w^{\prime}}(y;z)\operatorname{\mathfrak{S}}_{w^{\prime}}(x;y)}$

Picking out the coefficient of $\operatorname{\mathfrak{S}}_{w^{\prime}}(x;y)$
with $w^{\prime}=wv^{-1}\mu_{v}$ we obtain the result. ∎

##  5\. Positive formula for (skew) double Schubert polynomials

Theorem 3.1 yields a nontrivial formula even when $u$ is the identity. In that
case, $\partial_{u}^{w}=\partial^{w}$, hence
$c_{uv}^{w}(x;y)=\partial^{w}(\operatorname{\mathfrak{S}}_{v}(x;y))$. Thus

$c_{1,v}^{1}(x;y)=\operatorname{\mathfrak{S}}_{v}(x;y)$

and hence our formula yields a positive formula for double Schubert
polynomials. We record this as a theorem.

######  Theorem 5.1.

For all $v\in S_{\infty}$ we have

$\operatorname{\mathfrak{S}}_{v}(x;y)=e_{1,v}^{1}(x;y)$

and hence $\operatorname{\mathfrak{S}}_{v}(x;y)$ is a polynomial in the
differences $x_{i}-y_{j}$ with nonnegative integer coefficients.

######  Example 5.1.

We use the formula to obtain $\operatorname{\mathfrak{S}}_{[1,4,3,2]}(x;y)$.
We set $u=1$, $v=[1,4,3,2]$, and $w=1$. Then

$\displaystyle\mu_{v}$ $\displaystyle=[4,3,1,2]$
$\displaystyle\mathfrak{c}(\mu_{v})$ $\displaystyle=(3,2)$
$\displaystyle\lambda(v)$ $\displaystyle=(2,2,1)$ $\displaystyle
v^{-1}\mu_{v}$ $\displaystyle=[2,3,1]$ $\displaystyle wv^{-1}\mu_{v}$
$\displaystyle=[2,3,1]$

We iterate over the paths to obtain the polynomial.

1 | 1 | 1 | 2
---|---|---|---
2 | 2 | 3 | 3
3 | 3 | 2 | 1
$(x_{1}-y_{1})(x_{1}-y_{2})(x_{2}-y_{1})$

1 1 2 2 2 2 3 3 3 3 1 1 $(x_{1}-y_{1})(x_{2}-y_{1})(x_{2}-y_{3})$

1 | 1 | 1 | 2
---|---|---|---
2 | 3 | 3 | 3
3 | 2 | 2 | 1
$(x_{1}-y_{1})(x_{1}-y_{2})(x_{3}-y_{2})$

1 1 2 2 2 3 3 3 3 2 1 1 $(x_{1}-y_{1})(x_{2}-y_{3})(x_{3}-y_{2})$

1 | 2 | 2 | 2
---|---|---|---
2 | 3 | 3 | 3
3 | 1 | 1 | 1
$(x_{2}-y_{2})(x_{2}-y_{3})(x_{3}-y_{2})$

Thus

$\displaystyle\operatorname{\mathfrak{S}}_{[1,4,3,2]}(x;y)$
$\displaystyle=(x_{1}-y_{1})(x_{1}-y_{2})(x_{2}-y_{1})+(x_{1}-y_{1})(x_{2}-y_{1})(x_{2}-y_{3})+(x_{1}-y_{1})(x_{1}-y_{2})(x_{3}-y_{2})$
$\displaystyle+(x_{1}-y_{1})(x_{2}-y_{3})(x_{3}-y_{2})+(x_{2}-y_{2})(x_{2}-y_{3})(x_{3}-y_{2})$

While our formula for double Schubert polynomials derived in this way is new,
it is not the first positive formula for double Schubert polynomials in terms
of $x_{i}-y_{j}$. For example, see the formula in [13] using the pipe dreams
(or equivalently RC-graphs) in [1]. We suspect from empirical evidence, though
have not proved, that a modification of our formula for
$\operatorname{\mathfrak{S}}_{v}(x;y)$ to computing
$c_{1,w_{0}(n)}^{v^{-1}w_{0}(n)}(x;y)$ but applying Proposition 4.4 in
increasing order of degree instead of decreasing order yields the same terms
as the definition of pipe dream polynomials with the corresponding RC-graph
obtained directly by sorting the columns of our diagram. It would be
interesting to establish this correspondence in general. We give an example.

######  Example 5.2 (Illustration of the conjectural relation to RC-graphs).

An example RC-graph for the permutation $v=[3,1,4,6,5,2]$ is given in Figure
(3.1) in [1]. Namely, the example is

| 1 | 2 | 3 | 4 | 5 | 6
---|---|---|---|---|---|---
1 | $+$ | $+$ | $\cdot$ | $\cdot$ | $+$ | $\cdot$
2 | $\cdot$ | $+$ | $\cdot$ | $\cdot$ | $\cdot$ |
3 | $\cdot$ | $+$ | $\cdot$ | $\cdot$ |  |
4 | $\cdot$ | $\cdot$ | $\cdot$ |  |  |
5 | $+$ | $\cdot$ |  |  |  |
6 | $\cdot$ |  |  |  |  |

The corresponding term in the double Schubert polynomial given by the formula
in [13] (each plus sign gives a factor of $x_{r}-y_{c}$, where $r$ is the row
and $c$ is the column) would be

$(x_{1}-y_{1})(x_{1}-y_{2})(x_{1}-y_{5})(x_{2}-y_{2})(x_{3}-y_{2})(x_{5}-y_{1})$

Applying Proposition 4.4 to

$\operatorname{\mathfrak{S}}_{w_{0}(5)}(x;y)=E_{1}(x;y_{5})E_{2}(x;y_{4})E_{3}(x;y_{3})E_{4}(x;y_{2})E_{5}(x;y_{1})$

to compute $c_{1,w_{0}(5)}^{v^{-1}w_{0}(5)}(x;y)$ we obtain for one of the
terms the following diagram, multiplying in increasing order of degree,
beginning the path in the diagram from the right:

4 | 3 | 3 | 2 | 1 | 1
---|---|---|---|---|---
5 | 5 | 4 | 3 | 2 | 2
3 | 2 | 2 | 1 | 3 | 3
1 | 1 | 1 | 4 | 4 | 4
6 | 4 | 5 | 5 | 5 | 5
2 | 6 | 6 | 6 | 6 | 6

This diagram yields the same term as the RC-graph. Sorting the columns in this
diagram, we obtain

1 | 1 | 1 | 1 | 1 | 1
---|---|---|---|---|---
2 | 2 | 2 | 2 | 2 | 2
3 | 3 | 3 | 3 | 3 | 3
4 | 4 | 4 | 4 | 4 | 4
5 | 5 | 5 | 5 | 5 | 5
6 | 6 | 6 | 6 | 6 | 6

which coincides with the RC-graph. The interested reader may wish to verify
that the remaining $14$ diagrams all coincide with other RC-graphs for $v$ in
the same way.

While one might initially expect that any formula should involve the same term
at some point, this specific term does not occur at all in the formula for
$e_{1,v}^{1}(x;y)$, which uses a different dominant permutation and uses
multiplication in decreasing order of degree (with increasing order of
indices). Expressions of double Schubert polynomials
$\operatorname{\mathfrak{S}}_{v}(x;y)$ for permutations $v$ as polynomials in
$x_{i}-y_{j}$ are generally not at all unique. This is easily seen in the
simple example of the polynomial

$\operatorname{\mathfrak{S}}_{s_{2}}(x;y)=(x_{1}-y_{1})+(x_{2}-y_{2})=(x_{1}-y_{2})+(x_{2}-y_{1})$

and in general for the linear double Schubert polynomials in $n$ variables
there are $n!$ ways to group the terms.

Kirillov in [12] defines skew Schubert polynomials as polynomials of the form
$u^{-1}\partial_{u}^{w}(\operatorname{\mathfrak{S}}_{w_{0}(n)}(x))$, or
equivalently $u^{-1}(c_{u,w_{0}(n)}^{w}(x;0))$, and conjectures that they have
nonnegative integer coefficients. We note that there are other notions of skew
Schubert polynomials, for example in [7], [2], [20], and [28]. Using our
formulas, we have been able to prove Kirillov’s conjecture.

######  Theorem 5.2.

The skew Schubert polynomials defined by Kirillov in [12] have nonnegative
integer coefficients.

###### Proof.

We have that $c_{u,w_{0}(n)}^{w}(x;0)=e_{u,w_{0}(n)}^{w}(x;0)$ since
$w_{0}(n)$ is dominant, hence any permutation of this polynomial has
nonnegative integer coefficients. ∎

The polynomials $c_{u,w_{0}(n)}^{w}(0;-y)$ seem to be closely related to the
skew Schubert polynomials in [20] and [2] in that they are nonnegative linear
combinations of ordinary Schubert polynomials via Littlewood-Richardson
coefficients, and it would be worthwhile to investigate the connection between
them, which we will not do here. The “double skew Schubert polynomials”
$c_{u,w_{0}(n)}^{w}(x;-y)$ would then seem to connect Kirillov’s skew Schubert
polynomials and polynomials similar to Lenart’s/Bergeron’s/Sottile’s.

######  Example 5.3.

We compute, using our positive formula, the skew Schubert polynomial computed
in Example 3 of [12], up to a permutation. Specifically, the polynomial being
computed is $c_{u,w_{0}(3)}^{w}(x;0)$, where $u=[3,1,2,4]$ and $w=[4,3,1,2]$.

3 | 3 | 3 | 4
---|---|---|---
1 | 1 | 4 | 3
2 | 4 | 1 | 1
4 | 2 | 2 | 2
$(x_{1}-y_{1})(x_{3}-y_{1})(x_{3}-y_{2})$

3 3 4 4 1 1 3 3 2 4 1 1 4 2 2 2 $(x_{1}-y_{1})(x_{3}-y_{1})(x_{4}-y_{3})$

3 | 4 | 4 | 4
---|---|---|---
1 | 1 | 3 | 3
2 | 3 | 1 | 1
4 | 2 | 2 | 2
$(x_{1}-y_{1})(x_{4}-y_{2})(x_{4}-y_{3})$

Setting $y=0$, we obtain $(x_{3}^{2}+x_{3}x_{4}+x_{4}^{2})x_{1}$, which is the
desired permutation of the result given in the article,
$(x_{1}^{2}+x_{1}x_{4}+x_{4}^{2})x_{2}$.

##  6\. Equivariant positivity

The order of multiplication by factorial elementary symmetric polynomials in
computation of $e_{uv}^{w}(y;z)$ may seem arbitrary, and indeed any order will
of course give the same overall result. Example 5.2 illustrates that different
choices can result in interesting combinatorial consequences. The particular
choice of multiplying in decreasing order of degree (with increasing order of
indices) is advantageous in that it gives a positive formula for
$c_{uv}^{w}(y;y)$ for the relevant $u$ and $v$, as we show in this section.

######  Definition 6.1 (Graham-nonnegative).

The negative roots are the linear polynomials of the form $y_{j}-y_{i}$ with
$j>i$, and the simple negative roots are the polynomials
$\alpha_{i}=y_{i+1}-y_{i}$. It is easy to see that the negative roots have
nonnegative coefficients when expressed in terms of the simple negative roots.
A polynomial $P(y)$ is said to be Graham-nonnegative if $P(y)$ can be
expressed as a polynomial in the simple negative roots with nonnegative
integer coefficients.

######  Theorem 6.1.

Let $u,w\in S_{\infty}$, let $\lambda$ be a partition, and suppose
$P\in\mathrm{Path}_{\lambda}(u,w)$. Then $\mathrm{weight}_{P,\lambda}(y;y)$ is
Graham-nonnegative.

This requires some setup.

######  Definition 6.2 (Factors of a path).

Let $\lambda$ be a partition and let
$P=(u_{0},\ldots,u_{m})\in\mathrm{Path}_{\lambda}(u,w)$. Then if $a,q$ are
integers we say that $(a,q)$ is a _factor_ of $P$ if $1\leq q\leq m$, $1\leq
a\leq\lambda_{q}$, and

$u_{q-1}(a)=u_{q}(a)$

This factor is said to be in row $a$ and column $q$. If $(a,q)$ is a factor of
$P$, then $(a,q)$ is said to be a _negative factor_ if $u_{q}(a)<q$, a _zero
factor_ if $u_{q}(a)=q$, and a _positive factor_ if $u_{q}(a)>q$.

######  Lemma 6.2.

Let $u,w$ be permutations, let $\lambda$ be a partition, and let
$P\in\mathrm{Path}_{\lambda}(u,w)$. If $(j,k)$ is a negative factor of $P$,
then there exists a zero factor $(a,q)$ of $P$ with $q\leq k$.

###### Proof.

Let $P=(u_{0},\ldots,u_{m})$. We note that it is a consequence of the
definition of $\xrightarrow{}$ that for each $1\leq q\leq m$ we have that if
$j\leq\lambda_{q}$ then $u_{q-1}(j)\leq u_{q}(j)$. We prove by induction on
$q$ that if there are no integers $j,k$ with $k\leq q$ such that $(j,k)$ is a
zero factor of $P$, then for all factors $(j,k)$ of $P$ with $1\leq k\leq q$
we have that $(j,k)$ is a positive factor of $P$. For $q=1$ this is clear, as
in that case any factor is either a positive factor or a zero factor.
Otherwise, suppose it holds for all $q^{\prime}<q$ for some $q>1$. Then if
there are no zero factors to the left of column $q$, since $u_{q-1}(j)\geq q$
for all $j\leq\lambda_{q-1}$ by the induction hypothesis we have that
$u_{q}(j)\geq q$ for all $j\leq\lambda_{q}$. If $u_{q}(a)=q$ for some
$a\leq\lambda_{q}$ then $u_{q}(a)=u_{q-1}(a)=q$ and it follows that $(a,q)$ is
a zero factor of $P$. Otherwise we have that $u_{q}(j)>q$ for all
$j\leq\lambda_{q}$, so that there can only be positive factors of $P$ in
column $q$ and the result follows by induction. ∎

###### Proof of Theorem 6.1.

Let $u,w\in S_{\infty}$, let $\lambda$ be a partition, and let
$P=(u_{0},\ldots,u_{m})\in\mathrm{Path}_{\lambda}(u,w)$. We show that
$\mathrm{weight}_{P,\lambda}(y;y)$ is Graham-nonnegative. Recall the
definition

$\mathrm{weight}_{P,\lambda}(y;y)=\prod_{i=1}^{m}\mathrm{weight}_{u_{i-1},\lambda_{i}}^{u_{i}}(y;y_{i})$

In this product, for each $j$ the factor
$\mathrm{weight}_{u_{j-1},\lambda_{j}}^{u_{j}}(y;y_{j})$ can only fail to be
Graham-nonnegative if there exists at least one negative factor $(i,j)$ of
$P$, which would contribute $y_{u_{j}(i)}-y_{j}$ to the product with
$u_{j}(i)<j$. However, by Lemma 6.2, if there is such a factor then there
exists a zero factor $(a,q)$ with $q\leq j$; this contributes $y_{q}-y_{q}=0$
to $\mathrm{weight}_{u_{q-1},\lambda_{q}}^{u_{q}}(y;y_{q})$, hence
$\mathrm{weight}_{P,\lambda}(y;y)=0$. Therefore if there are any negative
factors in the product the entire product vanishes, and it follows that
$\mathrm{weight}_{P,\lambda}(y;y)$ is Graham-nonnegative. ∎

While Theorem 3.1 fails to be symmetric in that the roles of $u$ and $v$
cannot be interchanged, in the equivariant case it is. Some general results
include a positive formula for multiplying a double Schubert polynomial
$\operatorname{\mathfrak{S}}_{u}(x;y)$ by a factorial Schur polynomial
$s_{\lambda}(x;y)$ where the factorial Schur polynomial has at least as many
$x$ variables as the double Schubert polynomial, which is an equivariant
analog of the formula of Kohnert in [17] (though not in the sense of using the
same combinatorial elements). In particular this also gives a Littlewood-
Richardson rule for equivariant cohomology of the Grassmannian, and for
multiplying pairs of factorial Schur functions that have different numbers of
variables, which is an equivariant analog of the main result of [24]. Most
generally, the separated descents case in [15] and [11] is covered in
equivariant cohomology.

######  Example 6.1 (Grassmannian case).

This computes the example in Figure 8 of [14]. Let $u=[2,4,1,3]$, let
$v=[1,3,2]$, and let $w=[2,4,1,3]$. Then

$\displaystyle\mu_{v}$ $\displaystyle=[3,1,2]$
$\displaystyle\mathfrak{c}(\mu_{v})$ $\displaystyle=(2)$
$\displaystyle\lambda(v)$ $\displaystyle=(1,1)$ $\displaystyle v^{-1}\mu_{v}$
$\displaystyle=[2,1]$ $\displaystyle wv^{-1}\mu_{v}$ $\displaystyle=[4,2,1,3]$

Then $c_{uv}^{w}(y;y)=y_{4}-y_{1}$, as witnessed by the following paths.

2 | 2 | 4
---|---|---
4 | 4 | 2
1 | 1 | 1
3 | 3 | 3
$y_{2}-y_{1}$
2 | 4 | 4
---|---|---
4 | 2 | 2
1 | 1 | 1
3 | 3 | 3
$y_{4}-y_{2}$

The formula in [14] also has two terms that combine to yield the
$y_{4}-y_{1}$, but the weight of the two terms is $y_{4}-y_{3}$ and
$y_{3}-y_{1}$, which are different from the elements of our formula.

Now let $w=[3,4,1,2]$. Then $wv^{-1}\mu_{v}=[4,3,1,2]$ and
$c_{uv}^{w}(y;y)=1$, as witnessed by the following path:

2 | 3 | 4
---|---|---
4 | 4 | 3
1 | 1 | 1
3 | 2 | 2
1

There is a third term in the expansion of the product, but in [14] this is $0$
because it falls outside the cohomology ring of the chosen Grassmannian.

######  Example 6.2.

We multiply a double Schubert polynomial by a factorial Schur polynomial that
has more $x$ variables. Namely, we multiply the factorial Schur polynomial
$s_{(2,1)}(x_{1},x_{2},x_{3},x_{4};y)$, which is equal to
$\operatorname{\mathfrak{S}}_{[1,2,4,6,3,5]}(x;y)$, by
$\operatorname{\mathfrak{S}}_{[3,1,4,2]}(x_{1},x_{2},x_{3};y)$. Hence we set
$u=[1,2,4,6,3,5]$, $v=[3,1,4,2]$. Then

$\displaystyle\mu_{v}$ $\displaystyle=[3,4,1,2]$
$\displaystyle\mathfrak{c}(\mu_{v})$ $\displaystyle=(2,2)$
$\displaystyle\lambda(v)$ $\displaystyle=(2,2)$ $\displaystyle v^{-1}\mu_{v}$
$\displaystyle=[1,3,2]$

We write $w$ on top of the diagram to save space.

$[3,1,4,6,2,5]$
---
1 | 2 | 3
2 | 4 | 4
4 | 1 | 1
6 | 6 | 6
3 | 3 | 2
5 | 5 | 5
$y_{4}-y_{2}$
$[3,1,5,6,2,4]$
---
1 | 2 | 3
2 | 4 | 5
4 | 1 | 1
6 | 6 | 6
3 | 3 | 2
5 | 5 | 4
1
$[3,1,6,4,2,5]$
---
1 | 2 | 3
2 | 4 | 6
4 | 1 | 1
6 | 6 | 4
3 | 3 | 2
5 | 5 | 5
1
$[3,2,4,6,1,5]$
---
1 | 2 | 3
2 | 3 | 4
4 | 4 | 2
6 | 6 | 6
3 | 1 | 1
5 | 5 | 5
1
$[4,1,6,2,3,5]$
---
1 | 2 | 4
2 | 4 | 6
4 | 1 | 1
6 | 6 | 2
3 | 3 | 3
5 | 5 | 5
1

For $w=[3,1,4,6,2,5]$ there are two paths, but the weight of one of them is
$y_{1}-z_{1}$ which specializes to $0$. There are several other paths for
other values of $w$ that specialize to $0$ when we set $z=y$ which we do not
include in the calculation.

Thus

$\displaystyle
s_{(2,1)}(x_{1},x_{2},x_{3},x_{4};y)\operatorname{\mathfrak{S}}_{[3,1,4,2]}(x;y)=$
$\displaystyle(y_{4}-y_{2})\operatorname{\mathfrak{S}}_{[3,1,4,6,2,5]}(x;y)+\operatorname{\mathfrak{S}}_{[3,1,5,6,2,4]}(x;y)$
$\displaystyle+\operatorname{\mathfrak{S}}_{[3,1,6,4,2,5]}(x;y)+\operatorname{\mathfrak{S}}_{[3,2,4,6,1,5]}(x;y)$
$\displaystyle+\operatorname{\mathfrak{S}}_{[4,1,6,2,3,5]}(x;y)$

######  Example 6.3.

We give an example which does not involve factorial Schur functions. Set
$u=[1,3,5,4,2]$, $v=[3,1,4,2]$. Then

$\displaystyle\mu_{v}$ $\displaystyle=[3,4,1,2]$
$\displaystyle\mathfrak{c}(\mu_{v})$ $\displaystyle=(2,2)$
$\displaystyle\lambda(v)$ $\displaystyle=(2,2)$ $\displaystyle v^{-1}\mu_{v}$
$\displaystyle=[1,3,2]$ $[3,1,5,4,2]$
---
1 | 3 | 3
3 | 5 | 5
5 | 1 | 1
4 | 4 | 4
2 | 2 | 2
$(y_{3}-y_{2})(y_{5}-y_{2})$

$[3,2,5,4,1]$ 1 2 3 3 3 5 5 1 1 4 4 4 2 2 2 $y_{3}-y_{1}$ $[3,2,5,4,1]$ 1 2 3
3 5 5 5 3 2 4 4 4 2 1 1 $y_{5}-y_{2}$

$(y_{3}-y_{2})(y_{5}-y_{2})\operatorname{\mathfrak{S}}_{[3,1,5,4,2]}(x;y)+((y_{3}-y_{1})+(y_{5}-y_{2}))\operatorname{\mathfrak{S}}_{[3,2,5,4,1]}(x;y)$
$[3,4,5,1,2]$
---
1 | 3 | 3
3 | 4 | 5
5 | 5 | 4
4 | 1 | 1
2 | 2 | 2
$y_{3}-y_{2}$

$(y_{5}-y_{2})$ $[4,1,5,3,2]$ 1 3 4 3 5 5 5 1 1 4 4 3 2 2 2 $y_{5}-y_{2}$
$(y_{5}-y_{2})$ $[3,1,6,4,2,5]$ 1 3 3 3 5 6 5 1 1 4 4 4 2 2 2 6 6 5
$y_{3}-y_{2}$

$(y_{3}-y_{2})\operatorname{\mathfrak{S}}_{[3,4,5,1,2]}(x;y)+(y_{5}-y_{2})\operatorname{\mathfrak{S}}_{[4,1,5,3,2]}(x;y)+(y_{3}-y_{2})\operatorname{\mathfrak{S}}_{[3,1,6,4,2,5]}(x;y)$
$[3,4,5,2,1]$
---
1 | 2 | 3
3 | 4 | 5
5 | 5 | 4
4 | 3 | 2
2 | 1 | 1
$1$

$(y_{5}-y_{2})$ $[4,2,5,3,1]$ 1 2 4 3 4 5 5 5 2 4 3 3 2 1 1 $1$
$(y_{5}-y_{2})$ $[4,3,5,1,2]$ 1 3 4 3 4 5 5 5 3 4 1 1 2 2 2 $1$

$\operatorname{\mathfrak{S}}_{[3,4,5,2,1]}(x;y)+\operatorname{\mathfrak{S}}_{[4,2,5,3,1]}(x;y)+\operatorname{\mathfrak{S}}_{[4,3,5,1,2]}(x;y)$
$[3,2,6,4,1,5]$
---
1 | 2 | 3
3 | 5 | 6
5 | 3 | 2
4 | 4 | 4
2 | 1 | 1
6 | 6 | 5
$1$

$(y_{5}-y_{2})$ $[4,1,6,3,2,5]$ 1 3 4 3 5 6 5 1 1 4 4 3 2 2 2 6 6 5 $1$

$\operatorname{\mathfrak{S}}_{[3,2,6,4,1,5]}(x;y)+\operatorname{\mathfrak{S}}_{[4,1,6,3,2,5]}(x;y)$

##  7\. The Pieri formula

######  Definition 7.1.

Suppose $A$ is a finite set of positive integers, and suppose the distinct
elements of $A$ are $a_{1},\ldots,a_{m}$ in increasing order. If $P(y;z)$ is a
polynomial in $y$ and $z$, we write $P(y_{A};z)$ to mean

$P(y_{a_{1}},y_{a_{2}},\ldots,y_{a_{m}};z)$

The case where $m$ is smaller than the actual number of $y$ variables
occurring in $P(y;z)$ will not happen in the exposition, and as such we do not
define the notation in this case.

######  Theorem 7.1 (The Pieri formula).

Let $u\in S_{\infty}$ and $p\leq k$. Then

$\operatorname{\mathfrak{S}}_{u}(x;y)E_{p,k}(x;z)=\sum_{u\xrightarrow{k}w}E_{p-\ell(u,w),k-\ell(u,w)}(y_{P_{k}(u,w)};z)\operatorname{\mathfrak{S}}_{w}(x;y)$

######  Example 7.1.

Let $u=[4,3,5,1,2]$, let $p=3$, and let $k=4$. Then

$\displaystyle\operatorname{\mathfrak{S}}_{u}(x;y)E_{p,k}(x;z)$
$\displaystyle=E_{3,4}(y_{1},y_{3},y_{4},y_{5};z)\operatorname{\mathfrak{S}}_{[4,3,5,1,2]}(x;y)$
$\displaystyle+E_{2,3}(y_{3},y_{4},y_{5};z)\operatorname{\mathfrak{S}}_{[4,3,5,2,1]}(x;y)$
$\displaystyle+E_{2,3}(y_{1},y_{3},y_{4};z)\operatorname{\mathfrak{S}}_{[4,3,6,1,2,5]}(x;y)$
$\displaystyle+E_{1,2}(y_{3},y_{4};z)\operatorname{\mathfrak{S}}_{[4,3,6,2,1,5]}(x;y)$
$\displaystyle+E_{1,2}(y_{1},y_{4};z)\operatorname{\mathfrak{S}}_{[4,5,6,1,2,3]}(x;y)$
$\displaystyle+E_{1,2}(y_{1},y_{3};z)\operatorname{\mathfrak{S}}_{[5,3,6,1,2,4]}(x;y)$
$\displaystyle+\operatorname{\mathfrak{S}}_{[4,5,6,2,1,3]}(x;y)+\operatorname{\mathfrak{S}}_{[5,3,6,2,1,4]}(x;y)+\operatorname{\mathfrak{S}}_{[5,4,6,1,2,3]}(x;y)$

The Pieri formula will be derived from Proposition 4.4, the proof of which
will require extensive setup. First, we give a formula for multiplication by
$x_{i}-z_{j}$ for general $i,j$.

######  Lemma 7.2.

Let $u\in S_{\infty}$ and let $i,j\geq 1$. Then

$(x_{i}-z_{j})\operatorname{\mathfrak{S}}_{u}(x;y)=(y_{u(i)}-z_{j})\operatorname{\mathfrak{S}}_{u}(x;y)+\sum_{\begin{subarray}{c}q\neq
i\\\
\ell(ut_{iq})=\ell(u)+1\end{subarray}}\mathrm{sign}(q-i)\operatorname{\mathfrak{S}}_{ut_{iq}}(x;y)$

###### Proof.

It can be shown by the recurrence relation for $\partial_{u}^{w}$ that
$\partial_{u}^{u}=u$. Thus we have

$\partial_{u}^{u}(x_{i}-z_{j})=x_{u(i)}-z_{j}$

Substituting $y$ for $x$, we obtain that the coefficient of
$\operatorname{\mathfrak{S}}_{u}(x;y)$ is $y_{u(i)}-z_{j}$.

To compute the constant coefficients we use the equivariant Chevalley formula

$\operatorname{\mathfrak{S}}_{u}(x;y)\operatorname{\mathfrak{S}}_{s_{i}}(x;y)=(\operatorname{\mathfrak{S}}_{s_{i}}(u(x);y))|_{x=y}\operatorname{\mathfrak{S}}_{u}(x;y)+\sum_{\begin{subarray}{c}u\xrightarrow{i}u^{\prime}\\\
\ell(u^{\prime})=\ell(u)+1\end{subarray}}\operatorname{\mathfrak{S}}_{u^{\prime}}(x;y)$

We have that

$x_{i}-z_{j}=\operatorname{\mathfrak{S}}_{s_{i}}(x;y)-\operatorname{\mathfrak{S}}_{s_{i-1}}(x;y)+y_{i}-z_{j}$

with the negative term $\operatorname{\mathfrak{S}}_{s_{i-1}}(x;y)$ excluded
if $i=1$. Thus the terms occurring with constant coefficients in the expansion
of $(x_{i}-z_{j})\operatorname{\mathfrak{S}}_{u}(x;y)$ are

$\sum_{\begin{subarray}{c}u\xrightarrow{i}u^{\prime}\\\
\ell(u,u^{\prime})=1\end{subarray}}\operatorname{\mathfrak{S}}_{u^{\prime}}(x;y)-\sum_{\begin{subarray}{c}u\xrightarrow{i-1}u^{\prime\prime}\\\
\ell(u,u^{\prime\prime})=1\end{subarray}}\operatorname{\mathfrak{S}}_{u^{\prime\prime}}(x;y)$

The overlap in the two sums is when $u^{\prime}=u^{\prime\prime}=ut_{qk}$
where $i\notin\\{q,k\\}$, which cancel, and what remains is the negative terms
$ut_{qi}$ where $q<i$ and the positive terms $ut_{iq}$ where $q>i$. Therefore,

$\partial_{u}^{ut_{qk}}(x_{i}-z_{j})=0$

if $i\notin\\{q,k\\}$, and if $q\neq i$ then

$\partial_{u}^{ut_{iq}}(x_{i}-z_{j})=\mathrm{sign}(q-i)$

The result follows. ∎

######  Definition 7.2 (Cycles, cycle length, disjoint cycles).

Recall that a _cycle_ or _cyclic permutation_ is a permutation $c$ written
with alternative notation (not window notation) as $c=(a_{1},\ldots,a_{m})$
for positive integers $a_{i}$ such that $a_{i}\neq a_{j}$ if $i\neq j$
characterized by the fact that $c(a_{i})=a_{i+1}$ for all $1\leq i\leq m$,
with the index wrapping around so that $a_{m+1}=a_{1}$, and $c(j)=j$ if
$j\notin\\{a_{1},\ldots,a_{m}\\}$. Cycles $c$ have a _cycle length_ which is
equal to the value $m$, most often distinct from their length $\ell(c)$ as a
permutation. A cycle of cycle length $m$ is called an $m$-cycle. Note that
$t_{ab}=(a,b)$ is a $2$-cycle. We refer to the “elements” of the cycle $c$ as
the integers $a_{i}$ and say that $c$ _contains_ $a_{i}$ as though it were a
set.

For an $m$-cycle $(a_{1},\ldots,a_{m})$ with $m>2$ we have for any $1<j<m$
that

$(a_{1},\ldots,a_{m})=(a_{1},\ldots,a_{j})(a_{j},\ldots,a_{m})$

and we also have that

$(a_{1},\ldots,a_{m})=(a_{m},a_{1},\ldots,a_{m-1})$

hence the cycle is unchanged by cyclic permutation of the indices in its
representation in this form. Two cycles $c_{1}=(a_{1},\ldots,a_{p})$ and
$c_{2}=(b_{1},\ldots,b_{q})$ are said to be _disjoint_ if $a_{i}\neq b_{j}$
for all $i,j$. It is a basic fact proved in an undergraduate abstract algebra
course that every permutation has a unique decomposition as a product of
pairwise disjoint cycles (up to commutation).

We present here in Lemma 7.3 an alternative characterization of the Pieri
relation $\xrightarrow{k}$ in terms of cycles that is used as the definition
in [25]. Satisfaction of these conditions is usually easier to check than
Definition 2.5 since it is a characterization in terms of the unique disjoint
cycle decomposition of $u^{-1}w$. We note, and leave the proof to the reader,
that in the Pieri relation $u\xrightarrow{k}w$ if we have a sequence of
reflections $t_{a_{1}b_{1}}$, $\ldots$, $t_{a_{p}b_{p}}$ realizing this then
we may assume by rearranging the reflections that $b_{i}\leq b_{j}$ whenever
$i\leq j$.

######  Lemma 7.3.

Suppose $u,w\in S_{\infty}$ and let $k>0$ be an integer. Then
$u\xrightarrow{k}w$ if and only if there exist pairwise disjoint cyclic
permutations $c_{1},\ldots,c_{n}$ of respective cycle lengths
$p_{1}+1,\ldots,p_{n}+1$ such that

$w=uc_{1}\cdots c_{n}$

and

$\ell(u,w)=p_{1}+\cdots+p_{n}$

such that for each $i$ there exist pairwise distinct positive integers
$a_{1},\ldots,a_{p_{i}}$ and $b$ (different for each $i$) such that we may
write the cycle $c_{i}$ as

$c_{i}=(a_{p_{i}},a_{p_{i}-1},\ldots,a_{1},b)$

where $a_{j}\leq k$ for all $1\leq j\leq p_{i}$, $b>k$, and

$u(a_{p_{i}})<\cdots<u(a_{1})<u(b)$

###### Proof.

Suppose first that $u\xrightarrow{k}w$. Then there exist reflections
$t_{a_{1}b_{1}},\ldots,t_{a_{m}b_{m}}$ for some $m$ with $a_{i}\neq a_{j}$ if
$i\neq j$, $a_{i}\leq k<b_{i}$ for all $i$, $\ell(ut_{a_{1}b_{1}}\cdots
t_{a_{i}b_{i}})=\ell(u)+i$ for all $i$, $b_{i}\leq b_{j}$ if $i\leq j$, and
$w=ut_{a_{1}b_{1}}\cdots t_{a_{m}b_{m}}$. Fix $b$ such that there is an index
$1\leq q\leq m$ such that $b=b_{q}$ and let $i$ and $p$ be such that
$a_{i},\ldots,a_{i+p}$ is the maximal portion of the sequence such that
$b_{j}=b$ for all $i\leq j\leq i+p$. Let

$c=t_{a_{i}b_{i}}\cdots t_{a_{i+p}b_{i+p}}$

Given $j$ with $i\leq j\leq i+p$ we claim that if we define a permutation
$c^{(j)}$ with

$c^{(j)}=t_{a_{i}b}\cdots t_{a_{j}b}$

then

$c^{(j)}=(a_{j},a_{j-1},\ldots,a_{i},b)$

and that

$u(a_{j})<\cdots<u(a_{i})<u(b)$

This is clear if $j=i$. Otherwise, suppose

$c^{(j-1)}=t_{a_{i}b}\cdots t_{a_{j-1}b}=(a_{j-1},\ldots,a_{i},b)$

Then

$c^{(j-1)}t_{a_{j}b}=(a_{j-1},\ldots,a_{i},b)(b,a_{j})=(a_{j-1},\ldots,a_{i},b,a_{j})=(a_{j},\ldots,a_{i},b)$

as desired. We have that

$u(a_{j})=uc^{(j-1)}(a_{j})<uc^{(j-1)}(b)=u(a_{j-1})$

and hence the desired claim follows by induction. Hence,

$c=c^{(i+p)}=(a_{i+p},\ldots,a_{i},b)$

and

$u(a_{i+p})<\cdots<u(a_{i})<u(b)$

Ranging over all $b$, these cycles, which we index in order of increasing $b$
as $c_{1},\ldots,c_{n}$, are the ones that occur in the disjoint cycle
decomposition of $u^{-1}w$, which we can see by the fact that the cycles are
pairwise disjoint and $w=uc_{1}\ldots c_{n}$. Letting $p_{i}+1$ be the cycle
length of each cycle $c_{i}$, we have that there are $p_{1}+\cdots+p_{n}=m$
reflections, and hence

$\ell(uc_{1}\cdots c_{n})=\ell(u)+p_{1}+\cdots+p_{n}$

and we have the result.

We prove the converse now. Suppose the cycles $c_{1},\ldots,c_{n}$ of cycle
length $p_{i}+1$ for each $i$ exist satisfying the conditions, fixing $k$.
Write $c_{1}$ as

$c_{1}=(a_{p_{1}},\ldots,a_{1},b)$

with $u(a_{p_{1}})<\cdots<u(a_{1})<u(b)$. Then

$c_{1}=t_{a_{1}b}\cdots t_{a_{p_{1}}b}$

We claim that $\ell(ut_{a_{1}b}\cdots t_{a_{i}b})>\ell(ut_{a_{1}b}\cdots
t_{a_{i-1}b})$ for all $i$ (not yet claiming that the length increases by
exactly $1$). We prove this by induction on $i$. For $i=1$, we note that
$u(a_{1})<u(b)$ by assumption, hence $\ell(ut_{a_{1}b})>\ell(u)$. Assume now
that the result holds for $i-1$. Then

$ut_{a_{1}b}\cdots t_{a_{i-1}b}(b)=u(a_{i-1})>u(a_{i})=ut_{a_{1}b}\cdots
t_{a_{i-1}b}(a_{i})$

since $a_{j}\neq a_{i}$ if $j\neq i$. Thus multiplying on the right by
$t_{a_{i}b}$ increases the length by at least $1$. Applying this argument for
each disjoint cycle $c_{i}$ to $\ell(uc_{1}\cdots c_{i})$ and expanding the
cycles into reflections, we obtain that successively multiplying on the right
by each reflection increases the length by at least $1$ per reflection. Since
there are $p_{1}+\cdots+p_{n}$ reflections and this is equal to $\ell(u,w)$,
each reflection must increase the length by exactly $1$ and we have the
result. ∎

Note that it is not sufficient in Lemma 7.3 to require only that
$\ell(uc_{i})=\ell(u)+p_{i}$ for all $i$, as it could occur that, for example
in the case of two cycles, $\ell(uc_{1})=\ell(u)+p_{1}$ and
$\ell(uc_{2})=\ell(u)+p_{2}$ but $\ell(uc_{1}c_{2})\neq\ell(u)+p_{1}+p_{2}$.
This can even happen if $p_{1}=p_{2}=1$, so that the cycles are reflections.

######  Lemma 7.4.

Let $u,w\in S_{\infty}$, let $k>0$ be an integer, and suppose
$u\xrightarrow{k}w$. Then $u(i)\leq w(i)$ for all $i\leq k$, and $u(i)\geq
w(i)$ for all $i>k$.

###### Proof.

Let $t_{a_{1}b_{1}},\ldots,t_{a_{p}b_{p}}$ be a sequence of reflections
realizing $u\xrightarrow{k}w$, with $a_{i}\leq k<b_{i}$ for all $i$ and
$a_{i}\neq a_{j}$ if $i\neq j$, by which we mean $\ell(ut_{a_{1}b_{1}}\cdots
t_{a_{i}b_{i}})=\ell(u)+i$ for all $i$ and $w=ut_{a_{1}b_{1}}\cdots
t_{a_{p}b_{p}}$. We prove the statement by induction on $p$. If $p=0$, then
$u(i)=w(i)$ for all $i$, so the result is clear. Otherwise, suppose the result
holds for some $p\geq 0$; we show the result holds for $p+1$, considering a
reflection $t_{a_{p+1}b_{p+1}}$ such that $a_{p+1}\leq k<b_{p+1}$ and
$\ell(wt_{a_{p+1}b_{p+1}})=\ell(w)+1$, with $a_{i}\neq a_{p+1}$ for all $1\leq
i\leq p$. By the induction hypothesis, $u(i)\leq w(i)$ for all $i\leq k$, and
$u(i)\geq w(i)$ for all $i>k$. The only two positions that
$wt_{a_{p+1}b_{p+1}}$ and $w$ differ are $a_{p+1}$ and $b_{p+1}$. Since
$\ell(wt_{a_{p+1}b_{p+1}})=\ell(w)+1$, we have that $w(a_{p+1})<w(b_{p+1})$,
hence

$u(a_{p+1})\leq w(a_{p+1})<w(b_{p+1})=wt_{a_{p+1}b_{p+1}}(a_{p+1})$

Similarly,

$u(b_{p+1})\geq w(b_{p+1})>w(a_{p+1})=wt_{a_{p+1}b_{p+1}}(b_{p+1})$

The result follows by induction. ∎

The following is easy to see, but we will be required to refer back to it and
hence we state it as a lemma.

######  Lemma 7.5.

Suppose $u,w\in S_{\infty}$, $k>0$ is an integer, and suppose
$u\xrightarrow{k}w$. Then

$|P_{k}(u,w)|=k-\ell(u,w)$

###### Proof.

Let $p=\ell(u,w)$. Then there are reflections
$t_{a_{1}b_{1}},\ldots,t_{a_{p}b_{p}}$ such that $a_{i}\leq k<b_{i}$ for all
$i$,

$\ell(ut_{a_{1}b_{1}}\cdots t_{a_{i}b_{i}})=\ell(u)+i$

for all $i$, and $w=ut_{a_{1}b_{1}}\cdots t_{a_{p}b_{p}}$, with $a_{i}\neq
a_{j}$ whenever $i\neq j$. By this last condition, the number of indices
$i\leq k$ such that $u(i)\neq w(i)$ is exactly $p$; specifically, these
indices are the values $a_{j}$. Thus $u(i)=w(i)$ for exactly $k-p=k-\ell(u,w)$
values of $i$ such that $i\leq k$. ∎

Parts of the statements of the below lemmas are presented in [25] (the results
are stated for multiplying $w$ by a reflection instead of $u$, which is
equivalent via applying our lemmas to the interval $[w_{0}(n)w,w_{0}(n)u]$),
but we will include proofs here in order to be complete. The purpose of the
lemmas is to determine which terms remain and which terms cancel in an
expansion of the Pieri product in the proof of Proposition 4.4.

######  Lemma 7.6.

Suppose $u,w\in S_{\infty}$ and let $k>1$ be an integer. If
$u\xrightarrow{k}w$ but $u\centernot{\xrightarrow{k-1}}w$, then there is a
unique $q^{\prime}>k$ such that $\ell(ut_{kq^{\prime}})=\ell(u)+1$ and
$ut_{kq^{\prime}}\xrightarrow{k-1}w$. Furthermore, in that case there does not
exist a $q<k$ such that $\ell(ut_{qk})=\ell(u)+1$ and
$ut_{qk}\xrightarrow{k-1}w$.

###### Proof.

Suppose $u\xrightarrow{k}w$ but $u\centernot{\xrightarrow{k-1}}w$. Let
$c_{1},\ldots,c_{n}$ be the pairwise disjoint cycles in the decomposition of
$u^{-1}w$, with the cycle length of $c_{i}$ being $p_{i}+1$. Some such cycle
must contain $k$, as otherwise we would have $u\xrightarrow{k-1}w$ by Lemma
7.3. Assume that $c_{1}=(a_{p_{1}},\ldots,a_{1},b)$ is the cycle that contains
$k$ and set $q^{\prime}=b$. We claim that $ut_{kq^{\prime}}\xrightarrow{k-1}w$
and $\ell(ut_{kq^{\prime}})=\ell(u)+1$. Note that
$u=(ut_{kq^{\prime}})t_{kq^{\prime}}$ and hence

$(ut_{kq^{\prime}})t_{kq^{\prime}}c_{1}\cdots c_{n}=w$

Let $j$ be the index such that $a_{j}=k$. Then we have

$\displaystyle
t_{kq^{\prime}}(a_{p_{1}},\ldots,a_{j+1},k,a_{j-1},\ldots,a_{1},q^{\prime})$
$\displaystyle=t_{kq^{\prime}}(q^{\prime},a_{p_{1}},\ldots,a_{j+1},k,a_{j-1},\ldots,a_{1})$
$\displaystyle=t_{kq^{\prime}}(q^{\prime},a_{p_{1}},\ldots,a_{j+1},k)(k,a_{j-1},\ldots,a_{1})$
$\displaystyle=t_{kq^{\prime}}(k,q^{\prime})(a_{p_{1}},\ldots,a_{j+1},q^{\prime})(a_{j-1},\ldots,a_{1},k)$
$\displaystyle=(a_{p_{1}},\ldots,a_{j+1},q^{\prime})(a_{j-1},\ldots,a_{1},k)$

Note that $ut_{kq^{\prime}}(k)=u(q^{\prime})$,
$ut_{kq^{\prime}}(q^{\prime})=u(k)$, and otherwise $ut_{kq^{\prime}}(a)=u(a)$
for all $a\notin\\{k,q^{\prime}\\}$. Thus,

$ut_{kq^{\prime}}(a_{p_{1}})<\cdots<ut_{kq^{\prime}}(a_{j+1})$

since the same is true for $u$, and

$ut_{kq^{\prime}}(a_{j+1})=u(a_{j+1})<u(k)=ut_{kq^{\prime}}(q^{\prime})$

hence the first cycle is valid for $\xrightarrow{k-1}$. Furthermore, if $j>1$
then

$ut_{kq^{\prime}}(a_{j-1})<\cdots<ut_{kq^{\prime}}(a_{1})$

for the same reason, and

$ut_{kq^{\prime}}(a_{1})=u(a_{1})<u(q^{\prime})=ut_{kq^{\prime}}(k)$

hence the second cycle is valid for $\xrightarrow{k-1}$ as well, whereas if
$j=1$ then there is no second cycle. Since the (up to) two new cycles together
with $c_{2},\ldots,c_{n}$ are all pairwise disjoint and
$\ell(ut_{kq^{\prime}},w)=\ell(u,w)-1$, the cycle lengths sum up correctly and
we have that $ut_{kq^{\prime}}\xrightarrow{k-1}w$ by Lemma 7.3, as desired.

To show that the $q^{\prime}$ we have chosen is unique, let $r>k$ be any index
other than $q^{\prime}$ such that $\ell(ut_{kr})=\ell(u)+1$. Suppose first
that $r$ is not in any of the cycles $c_{i}$. Recall that $c_{1}$ is the cycle
that contains $k$. Then $t_{kr}c_{1}$ is a cycle in the disjoint cycle
decomposition of $(ut_{kr})^{-1}w$ containing both $k$ and $r$, which are both
larger than $k-1$. This violates the condition of Lemma 7.3 that in order for
$ut_{kr}\xrightarrow{k-1}w$ we must have that each cycle contains exactly one
element larger than $k-1$, hence we have
$ut_{kr}\centernot{\xrightarrow{k-1}}w$. If $r$ is in one of the cycles, since
$r>k$ and $r\neq q^{\prime}$ this cycle cannot be $c_{1}$. Say the cycle
containing $r$ is $c_{2}=(a_{p_{2}}^{\prime},\ldots,a_{1}^{\prime},r)$. Then

$\displaystyle t_{kr}c_{1}c_{2}$
$\displaystyle=t_{kr}(r,a_{p_{2}}^{\prime},\ldots,a_{1}^{\prime})(a_{p_{1}},\ldots,a_{1},q^{\prime})$
$\displaystyle=(r,a_{p_{2}}^{\prime},\ldots,a_{1}^{\prime},k)(k,a_{j-1},\ldots,q^{\prime},a_{p_{1}},\ldots,a_{j+1})$
$\displaystyle=(r,a_{p_{2}}^{\prime},\ldots,a_{1}^{\prime},k,a_{j-1},\ldots,q^{\prime},a_{p_{1}},\ldots,a_{j+1})$

is a single cycle disjoint from all the others containing both $k$ and $r$,
which are both greater than $k-1$, hence we have
$ut_{kr}\centernot{\xrightarrow{k-1}}w$ by Lemma 7.3. The uniqueness of
$q^{\prime}$ follows.

To prove the nonexistence of $q$, consider the same cycle decomposition
$c_{1},\ldots,c_{n}$. Let $q<k$ be such that $\ell(ut_{qk})=\ell(u)+1$. If
$c_{1}$ (the cycle that contains $k$) does not contain $q$, then $t_{qk}c_{1}$
is a cycle containing both $k$ and some integer larger than $k$. If some other
cycle $c_{2}$ contains $q$, $t_{qk}c_{1}c_{2}$ is disjoint from all the other
cycles and contains both $k$ and some integer larger than $k$, similarly to
the calculation above. Thus if $c_{1}$ does not contain $q$ then the disjoint
cycle decomposition of $(ut_{qk})^{-1}w$ contains the cycle $t_{qk}c_{1}$ or
$t_{qk}c_{1}c_{2}$, which implies that $ut_{qk}\centernot{\xrightarrow{k-1}}w$
by Lemma 7.3 since the cycle contains two elements larger than $k-1$. To
handle the case where $c_{1}$ contains $q$, in that case $t_{qk}$ splits
$c_{1}$ into two disjoint cycles as follows. Assume
$c_{1}=(a_{p_{1}},\ldots,q^{\prime})$ with $a_{j}=k$ and $a_{j^{\prime}}=q$.
We must have that $j^{\prime}>j$ since $u(q)<u(k)$. Then

$\displaystyle t_{qk}c_{1}$
$\displaystyle=t_{qk}(a_{p_{1}},\ldots,q,\ldots,k,\ldots,q^{\prime})$
$\displaystyle=t_{qk}(q,\ldots,k,\ldots,q^{\prime},a_{p_{1}},\ldots,a_{j^{\prime}+1})$
$\displaystyle=t_{qk}(q,a_{j^{\prime}-1},\ldots,k)(k,\ldots,q^{\prime},a_{p_{1}},\ldots,a_{j^{\prime}+1})$
$\displaystyle=(q,a_{j^{\prime}-1},\ldots,a_{j+1})(a_{p_{1}},\ldots,a_{j^{\prime}+1},k,\ldots,q^{\prime})$

The cycle $(a_{p_{1}},\ldots,k,\ldots,q^{\prime})$ contains two elements
larger than $k-1$, implying that $ut_{qk}\centernot{\xrightarrow{k-1}}w$ by
Lemma 7.3, as desired. ∎

######  Example 7.2.

Let $u=[3,1,6,5,2,4]$, let $w=[4,2,7,6,1,3,5]$, and let $k=4$. We have that

$u^{-1}w=(1,6)(2,5)(4,3,7)$

Thus $u\xrightarrow{k}w$, but $u\centernot{\xrightarrow{k-1}}w$ because of the
third cycle containing two elements greater than $k-1$. We set $q^{\prime}=7$
according to the proof. Then

$ut_{kq^{\prime}}=[3,1,6,7,2,4,5]$

Then we see the cycle splits by

$t_{kq^{\prime}}u^{-1}w=(1,6)(2,5)t_{kq^{\prime}}(4,3,7)=(1,6)(2,5)t_{kq^{\prime}}(4,7)(3,4)=(1,6)(2,5)(3,4)$

and indeed we have that $ut_{kq^{\prime}}\xrightarrow{k-1}w$.

######  Lemma 7.7.

Suppose $u,w\in S_{\infty}$ and let $k>1$ be an integer. If
$u\xrightarrow{k}w$ and $u\xrightarrow{k-1}w$, then there is no $q<k$ such
that $\ell(ut_{qk})=\ell(u)+1$ and $ut_{qk}\xrightarrow{k-1}w$ and there is no
$q^{\prime}>k$ such that $\ell(ut_{kq^{\prime}})=\ell(u)+1$ and
$ut_{kq^{\prime}}\xrightarrow{k-1}w$.

###### Proof.

Let $c_{1},\ldots,c_{n}$ be the pairwise disjoint cycles with $c_{i}$ a
$(p_{i}+1)$-cycle in the decomposition of $u^{-1}w$. These cycles, since the
disjoint cycle decomposition is unique, must realize both $u\xrightarrow{k}w$
and $u\xrightarrow{k-1}w$. Thus none of these cycles can contain $k$; if one
of them did, it would be impossible that $u\xrightarrow{k-1}w$ because the
cycle would have two elements larger than $k-1$.

We show first that element $q^{\prime}>k$ cannot exist. Suppose $q^{\prime}>k$
is such that $\ell(ut_{kq^{\prime}})=\ell(u)+1$. If none of the cycles $c_{i}$
contains $q^{\prime}$, then $(k,q^{\prime})$ is a free cycle in the disjoint
cycle decomposition of $(ut_{kq^{\prime}})^{-1}w$. Since both elements are
greater than $k-1$, we then cannot have that
$ut_{kq^{\prime}}\xrightarrow{k-1}w$. If one of the cycles does contain
$q^{\prime}$, say $c_{1}$, then since $c_{1}$ does not contain $k$ we have
that $t_{kq^{\prime}}c_{1}$ is a $(p_{1}+2)$-cycle containing both $k$ and
$q^{\prime}$; again, this implies that
$ut_{kq^{\prime}}\centernot{\xrightarrow{k-1}}w$ because both elements are
greater than $k-1$. It follows that no $q^{\prime}$ exists with
$\ell(ut_{kq^{\prime}})=\ell(u)+1$ and $ut_{kq^{\prime}}\xrightarrow{k-1}w$.

Now we consider $q$. Suppose $q<k$ is such that $\ell(ut_{qk})=\ell(u)+1$.
Then $u(q)<u(k)\leq w(k)$, the second inequality by Lemma 7.4 since
$u\xrightarrow{k}w$. We then have that $ut_{qk}(k)=u(q)<w(k)$, hence by Lemma
7.4 we cannot have that $ut_{qk}\xrightarrow{k-1}w$ since this would require
that $ut_{qk}(k)\geq w(k)$. The result follows. ∎

######  Lemma 7.8.

Suppose $u,w\in S_{\infty}$ and let $k>1$ be an integer. If
$u\xrightarrow{k-1}w$ and $u\centernot{\xrightarrow{k}}w$, then there is a
unique $q<k$ such that $\ell(ut_{qk})=\ell(u)+1$ and
$ut_{qk}\xrightarrow{k-1}w$. When this is the case, then
$P_{k-1}(ut_{qk},w)=P_{k-1}(u,w)\cup\\{u(k)\\}$, and for any $q^{\prime}>k$
such that $\ell(ut_{kq^{\prime}})=\ell(u)+1$ we have that
$ut_{kq^{\prime}}\centernot{\xrightarrow{k-1}}w$.

###### Proof.

Let $t_{a_{1}b_{1}},\ldots,t_{a_{p}b_{p}}$ be a sequence of reflections
realizing $u\xrightarrow{k-1}w$, and assume $b_{i}\leq b_{j}$ whenever $i\leq
j$. Since $u\centernot{\xrightarrow{k}}w$, we must have that $b_{i}=k$ for
some $i$. Let $i$ be minimal with this property and set $q=a_{i}$. Then
$\ell(ut_{qk})=\ell(u)+1$. Let $c_{1},\ldots,c_{n}$ be the pairwise disjoint
cycles in the decomposition of $u^{-1}w$ with $c_{i}$ having cycle length
$p_{i}+1$, and suppose the cycle with $q$ is $c_{1}$. $c_{1}$ then also must
contain $b_{i}=k$. We then have that $t_{qk}c_{1}$ is the $p_{1}$-cycle we
obtain by deleting $q$. We can see this by writing
$c_{1}=(a_{p_{1}}^{\prime},\ldots,q,k)$, then cyclically permuting to obtain
$(q,k,a_{p_{1}}^{\prime},\ldots,a_{2}^{\prime})=(q,k)(a_{p_{1}}^{\prime},\ldots,a_{2}^{\prime},k)$,
and multiplying this on the left by $t_{qk}$ cancels the $(q,k)$. We have that
$ut_{qk}(k)=u(q)$, hence

$ut_{kq}(a_{p_{1}}^{\prime})<\cdots<ut_{kq}(a_{2}^{\prime})<ut_{qk}(k)$

hence $ut_{qk}\xrightarrow{k-1}w$.

To show uniqueness of $q$, let $r<k$ be such that $r\neq q$ and
$\ell(ut_{rk})=\ell(u)+1$, and let the cycle $c_{1}$ be as in the previous
paragraph. If $r$ is not in any of the cycles, then $t_{rk}c_{1}$ has cycle
length $p_{1}+2$, hence the length condition is not satisfied in Lemma 7.3,
implying that $ut_{rk}\centernot{\xrightarrow{k-1}}w$. A similar length
argument applies when $r$ is in a cycle other than $c_{1}$, say $c_{2}$, with
$t_{rk}c_{1}c_{2}$ being a single cycle that is too long. Suppose instead that
$r$ is in $c_{1}$, say $a_{j}^{\prime}=r$ with $j\geq 2$. Write

$c_{1}=(k,a_{p_{1}}^{\prime},\ldots,a_{j+1}^{\prime},a_{j}^{\prime})(a_{j}^{\prime},a_{j-1}^{\prime},\ldots,a_{2}^{\prime},q)=(a_{j}^{\prime},k)(k,a_{p_{1}}^{\prime},\ldots,a_{j+1}^{\prime})(a_{j}^{\prime},a_{j-1}^{\prime},\ldots,a_{2}^{\prime},q)$

The $(a_{j}^{\prime},k)=(r,k)$ cancels in $t_{rk}c_{1}$ and we obtain two
cycles, one of which is nontrivial (because it contains both $r$ and $q$) and
contains only elements less than or equal to $k-1$, contradicting
$ut_{rk}\xrightarrow{k-1}w$. Uniqueness of $q$ follows.

Now we prove that $P_{k-1}(ut_{qk},w)=P_{k-1}(u,w)\cup\\{u(k)\\}$. Note that
$u(i)=ut_{qk}(i)$ if $i<k$ and $i\neq q$. Thus, if $u(i)\in P_{k-1}(u,w)$ and
$i\neq q$, then $u(i)\in P_{k-1}(ut_{qk},w)$. Since $P_{k-1}(ut_{qk},w)$ must
have exactly one more element than $P_{k-1}(u,w)$ by Lemma 7.5, this element
must occur at index $q$. Thus $ut_{qk}(q)=w(q)=u(k)$, hence the claim follows.

Suppose finally that $q^{\prime}>k$ is such that
$\ell(ut_{kq^{\prime}})=\ell(u)+1$; we show that
$ut_{kq^{\prime}}\centernot{\xrightarrow{k-1}}w$. This is due to the fact
that, again assuming $c_{1}$ contains $k$, $t_{kq^{\prime}}c_{1}$ contains
both $k$ and $q^{\prime}$. If in addition there is a cycle $c_{2}$ containing
$q^{\prime}$, then $t_{kq^{\prime}}c_{1}c_{2}$ is again a single cycle
containing both $k$ and $q^{\prime}$. In either case, since both $k$ and
$q^{\prime}$ are larger than $k-1$, this contradicts the conditions in Lemma
7.3, implying that $ut_{kq^{\prime}}\centernot{\xrightarrow{k-1}}w$. The
result follows. ∎

######  Example 7.3.

Let $u=[3,1,6,5,2,4]$, let $w=[5,3,6,1,2,4]$, and let $k=4$. We have that

$u^{-1}w=(2,1,4)$

Then $u\xrightarrow{k-1}w$ because $u(2)<u(1)<u(4)$, but
$u\centernot{\xrightarrow{k}}w$ because there is no element greater than $4$
in the cycle. We also have

$ut_{1,4}t_{2,4}=w$

Thus we choose $q=1$, since this is the first index such that the higher index
is $k$. Then

$ut_{qk}=[5,1,6,3,2,4]$

and

$t_{qk}(2,1,4)=(1,4)(1,4)(2,4)=(2,4)$

Hence $ut_{qk}\xrightarrow{k-1}w$. We have that $P_{k-1}(u,w)=\\{6\\}$, and
$P_{k-1}(ut_{qk},w)=\\{5,6\\}=P_{k-1}(u,w)\cup\\{u(k)\\}$.

######  Lemma 7.9.

Suppose $u,w\in S_{\infty}$ and let $k>1$ be an integer. Suppose also that
$u\centernot{\xrightarrow{k}}w$ and $u\centernot{\xrightarrow{k-1}}w$. Then
there exists a $q^{\prime}>k$ such that $\ell(ut_{kq^{\prime}})=\ell(u)+1$ and
$ut_{kq^{\prime}}\xrightarrow{k-1}w$ if and only if there exists a $q<k$ such
that $\ell(ut_{qk})=\ell(u)+1$ and $ut_{qk}\xrightarrow{k-1}w$. If either
exists, then each is unique, and
$P_{k-1}(ut_{qk},w)=P_{k-1}(ut_{kq^{\prime}},w)$.

###### Proof.

Let $q^{\prime}>k$ be such that $\ell(ut_{kq^{\prime}})=\ell(u)+1$ and
$ut_{kq^{\prime}}\xrightarrow{k-1}w$. Suppose also that
$u\centernot{\xrightarrow{k}}w$. We find a $q<k$ with
$\ell(ut_{qk})=\ell(u)+1$ and $ut_{qk}\xrightarrow{k-1}w$ and afterwards show
that $q^{\prime}$ is unique. Let $c_{1},\ldots,c_{n}$ be the pairwise disjoint
cycles in the decomposition of $(ut_{kq^{\prime}})^{-1}w$, with $c_{i}$ of
cycle length $p_{i}+1$. We claim that there must be some such cycle that
contains $k$. If neither $k$ nor $q^{\prime}$ were present, then we would have
that $u\xrightarrow{k}w$ by adding this disjoint cycle $(k,q^{\prime})$ to the
decomposition of $(ut_{kq^{\prime}})^{-1}w$, which we assumed is not the case.
The same is true if $q^{\prime}$ is present but not $k$. To see this, say
$c_{2}$ is the $(p_{2}+1)$-cycle containing $q^{\prime}$. Then
$t_{kq^{\prime}}c_{2}$ is a ($p_{2}+2$)-cycle satisfying the conditions of
Lemma 7.3 for $u$, $w$, and $k$ (which we can see from the fact that this is a
sequence of reflections of the form $t_{aq^{\prime}}$, each increasing the
length by $1$ and the lower indices being pairwise distinct), and we assumed
that $u\centernot{\xrightarrow{k}}w$.

In the case where $k$ is present but not $q^{\prime}$, say in the cycle
$c_{1}$, suppose

$c_{1}=(a_{p_{1}},\ldots,a_{1},k)$

Then we have

$t_{kq^{\prime}}c_{1}=(q^{\prime},k)(k,a_{p_{1}},\ldots,a_{1})=(q^{\prime},k,a_{p_{1}},\ldots,a_{1})=(k,a_{p_{1}},\ldots,a_{1},q^{\prime})$

If $u(k)<u(a_{p_{1}})$, then $u\xrightarrow{k}w$, which we assumed is not the
case. Therefore $u(k)>u(a_{p_{1}})$. Choose the minimal $j$ such that
$u(a_{j})<u(k)$, and write $t_{kq^{\prime}}c_{1}$ as

$(k,a_{p_{1}},\ldots,a_{j})(a_{j},\ldots,q^{\prime})=(a_{j},k)(k,a_{p_{1}},\ldots,a_{j+1})(a_{j},\ldots,q^{\prime})=(a_{j},k)(a_{p_{1}},\ldots,a_{j+1},k)(a_{j},\ldots,q^{\prime})$

and set $q=a_{j}$. Then $ut_{qk}\xrightarrow{k-1}w$ because
$ut_{qk}(a_{p_{1}})<\cdots<ut_{qk}(k)=ut_{kq^{\prime}}(a_{j})$, and if $j>1$
then

$ut_{qk}(a_{j})=u(k)<u(a_{j-1})=ut_{qk}(a_{j-1})<\cdots<ut_{qk}(q^{\prime})\mathrm{,}$

whereas if $j=1$ then $ut_{qk}(q)=u(k)<u(q^{\prime})=ut_{qk}(q^{\prime})$
since $\ell(ut_{kq^{\prime}})=\ell(u)+1$.

Finally consider the case where both $k$ and $q^{\prime}$ are present. Suppose

$c_{1}=(a_{p_{1}},\ldots,a_{1},k)$

and

$c_{2}=(a_{p_{2}}^{\prime},\ldots,a_{1}^{\prime},q^{\prime})$

Then

$t_{kq^{\prime}}c_{1}c_{2}=(k,a_{p_{1}},\ldots,a_{1},q^{\prime})(q^{\prime},a_{p_{2}}^{\prime},\ldots,a_{1}^{\prime})=(k,a_{p_{1}},\ldots,a_{1},q^{\prime},a_{p_{2}}^{\prime},\ldots,a_{1}^{\prime})$

Since $u\centernot{\xrightarrow{k}}w$, we have that $u(a_{1}^{\prime})>u(k)$
or $u(k)>u(a_{p_{1}})$ by the conditions in Lemma 7.3, and since
$u(k)=ut_{kq^{\prime}}(q^{\prime})>ut_{kq^{\prime}}(a_{1}^{\prime})$ given
that $ut_{kq^{\prime}}\xrightarrow{k-1}w$ it follows that $u(k)>u(a_{p_{1}})$.
Choose the minimal $j$ such that $u(a_{j})<u(k)$. Then we obtain

$(k,a_{p_{1}},\ldots,a_{j+1},a_{j})(a_{j},\ldots,a_{1},q^{\prime},a_{p_{2}}^{\prime},\ldots,a_{1}^{\prime})=(a_{j},k)(k,a_{p_{1}},\ldots,a_{j+1})(a_{p_{2}}^{\prime},\ldots,a_{1}^{\prime},a_{j},\ldots,a_{1},q^{\prime})$

and we may set $q=a_{j}$ as before, since then

$ut_{qk}(a_{1}^{\prime})=ut_{kq^{\prime}}(a_{1}^{\prime})<ut_{kq^{\prime}}(q^{\prime})=u(k)=ut_{qk}(a_{j})$

and if $j>1$ then

$ut_{qk}(a_{j})=u(k)<ut_{kq^{\prime}}(a_{j-1})=ut_{qk}(a_{j-1})$

whereas if $j=1$ then

$ut_{qk}(a_{1})=u(k)<u(q^{\prime})=ut_{qk}(q^{\prime})$

since $\ell(ut_{kq^{\prime}})=\ell(u)+1$, so that $ut_{qk}\xrightarrow{k-1}w$.
Thus, given such a $q^{\prime}$, we have identified an integer $q<k$ such that
$\ell(ut_{qk})=\ell(u)+1$ and $ut_{qk}\xrightarrow{k-1}w$. To see that
$q^{\prime}$ is unique, we note that $q^{\prime}$ is the unique element
contained in the cycle containing $k$ in the disjoint cycle decomposition of
$u^{-1}w$ that is larger than $k$.

We show now that if $u\centernot{\xrightarrow{k-1}}w$, then if $q<k$ is such
that $\ell(ut_{qk})=\ell(u)+1$ and $ut_{qk}\xrightarrow{k-1}w$ then there
exists a $q^{\prime}>k$ such that $\ell(ut_{kq^{\prime}})=\ell(u)+1$ and
$ut_{kq^{\prime}}\xrightarrow{k-1}w$, and we show that $q$ is unique assuming
additionally that $u\centernot{\xrightarrow{k}}w$. Let $q<k$ be such that
$\ell(ut_{qk})=\ell(u)+1$ and $ut_{qk}\xrightarrow{k-1}w$, and assume
$u\centernot{\xrightarrow{k-1}}w$. Let the pairwise disjoint cycles in the
decomposition of $(ut_{qk})^{-1}w$ be $c_{1},\ldots,c_{n}$, with $c_{i}$
having length $p_{i}+1$ (note that we have redefined the cycles here, and they
are not the same as the previous paragraph). If there were no cycle that
contained $q$, then we claim that we would then have that
$u\xrightarrow{k-1}w$, which we assumed is not the case. To see this, suppose
no cycle contains $q$ and no cycle contains $k$. Then $t_{qk}$ is a free cycle
in the decomposition of $u^{-1}w$ and its existence implies
$u\xrightarrow{k-1}w$ by Lemma 7.3. If instead no cycle contained $q$ but some
cycle contained $k$, then say this cycle containing $k$ is $c_{2}$. Then
$t_{qk}c_{2}$ can be written as a product of reflections of the form $t_{ak}$
for pairwise distinct choices of $a$ that are less than $k$, and we can deduce
that this forms a $(p_{2}+2)$-cycle $t_{qk}c_{2}$ that together with
$c_{1},c_{3},\ldots,c_{n}$ imply that $u\xrightarrow{k-1}w$ by Lemma 7.3. Thus
as claimed some cycle must contain $q$.

Assume without loss of generality that $c_{1}$ is the cycle containing $q$.
Then $c_{1}$ cannot contain $k$ because $ut_{qk}(q)>ut_{qk}(k)$. Thus assume

$c_{1}=(a_{p_{1}},\ldots,a_{1},q^{\prime})$

with $q^{\prime}>k$ and let $j$ be such that $a_{j}=q$. We have

$\displaystyle t_{qk}c_{1}$
$\displaystyle=t_{qk}(a_{j},\ldots,q^{\prime})(q^{\prime},a_{p_{1}},\ldots,a_{j+1})$
$\displaystyle=(k,a_{j},\ldots,a_{1},q^{\prime})(q^{\prime},a_{p_{1}},\ldots,a_{j+1})$
$\displaystyle=(k,q^{\prime})(a_{j},\ldots,a_{1},k)(a_{p_{1}},\ldots,a_{j+1},q^{\prime})$
$\displaystyle=t_{kq^{\prime}}(a_{j},\ldots,a_{1},k)(a_{p_{1}},\ldots,a_{j+1},q^{\prime})$

Since $ut_{qk}(a_{1})<ut_{qk}(q^{\prime})$, we have that
$ut_{kq^{\prime}}(a_{1})<ut_{kq^{\prime}}(k)$ if $j>1$, and in that case

$ut_{kq^{\prime}}(a_{j})=u(q)<u(k)=ut_{qk}(a_{j})<ut_{qk}(a_{j-1})=ut_{kq^{\prime}}(a_{j-1})$

We also have, if $j=1$,

$ut_{kq^{\prime}}(a_{1})=u(q)<u(k)<u(q^{\prime})=ut_{kq^{\prime}}(k)$

Thus

$ut_{kq^{\prime}}(a_{j})<\cdots<ut_{kq^{\prime}}(a_{1})<ut_{kq^{\prime}}(k)$

so that the first cycle is valid for $ut_{kq^{\prime}}\xrightarrow{k-1}w$.
Since $ut_{qk}(a_{j+1})<ut_{qk}(q)=u(k)$, we have that
$ut_{kq^{\prime}}(a_{j+1})<ut_{kq^{\prime}}(q^{\prime})=u(k)$. If there is no
other $c_{i}$ containing $k$, then we obtain that
$\ell(ut_{kq^{\prime}})=\ell(u)+1$ and $ut_{kq^{\prime}}\xrightarrow{k-1}w$ by
Lemma 7.3. If there exists a nontrivial cycle containing $k$, say
$c_{2}=(a_{p_{2}}^{\prime},\ldots,a_{1}^{\prime},k)$, then $t_{qk}c_{1}$
combines with $c_{2}$ to obtain

$\displaystyle t_{qk}c_{1}c_{2}$
$\displaystyle=t_{kq^{\prime}}(a_{j},\ldots,a_{1},k,a_{p_{2}}^{\prime},\ldots,a_{1}^{\prime})(a_{p_{1}},\ldots,a_{j+1},q^{\prime})$
$\displaystyle=t_{kq^{\prime}}(a_{p_{2}}^{\prime},\ldots,a_{1}^{\prime},a_{j},\ldots,a_{1},k)(a_{p_{1}},\ldots,a_{j+1},q^{\prime})\mathrm{.}$

Since $ut_{qk}(a_{1}^{\prime})<ut_{qk}(k)$, we have
$ut_{kq^{\prime}}(a_{1}^{\prime})<ut_{kq^{\prime}}(q)=ut_{kq^{\prime}}(a_{j})$,
hence $ut_{kq^{\prime}}\xrightarrow{k-1}w$. Hence, given $q$, we have
identified a $q^{\prime}>k$ such that $\ell(ut_{kq^{\prime}})=\ell(u)+1$ and
$ut_{kq^{\prime}}\xrightarrow{k-1}w$.

Assume now that $u\centernot{\xrightarrow{k}}w$; in that case, we know that
the $q^{\prime}$ we have identified is unique. Since

$u(k)=ut_{qk}(a_{j})<ut_{qk}(a_{j-1})=u(a_{j-1})$

we have that $q$ is the rightmost element in the cycle containing $k$, with
$k$ held fixed as the rightmost element of the cycle, in the disjoint cycle
decomposition of $(ut_{kq^{\prime}})^{-1}w$ such that $u(q)<u(k)$, hence $q$
is unique. Thus, if $u\centernot{\xrightarrow{k}}w$ and
$u\centernot{\xrightarrow{k-1}}w$, then $q^{\prime}$ exists if and only if $q$
does, and each is unique, as desired.

For the last part we show that
$P_{k-1}(ut_{qk},w)=P_{k-1}(ut_{kq^{\prime}},w)$ if $q$ and $q^{\prime}$
exist. We have that $ut_{qk}(i)=ut_{kq^{\prime}}(i)$ if $i\neq q$ and $i<k$,
and the cardinalities of $P_{k-1}(ut_{qk},w)$ and
$P_{k-1}(ut_{kq^{\prime}},w)$ are the same by Lemma 7.5. If $ut_{qk}(q)\in
P_{k-1}(ut_{qk},w)$, then $ut_{kq^{\prime}}(q)\notin
P_{k-1}(ut_{kq^{\prime}},w)$, and vice versa, because the values at these
indices are not equal and hence they cannot both be equal to $w(q)$. Hence,
neither $ut_{qk}(q)$ nor $ut_{kq^{\prime}}(q)$ is equal to $w(q)$, for if one
of them were then one of the two sets $P_{k-1}(ut_{qk},w)$ and
$P_{k-1}(ut_{kq^{\prime}},w)$ would have more elements than the other. We must
therefore have that $P_{k-1}(ut_{qk},w)=P_{k-1}(ut_{kq^{\prime}},w)$, as
stated. ∎

######  Example 7.4.

Let $u=[3,1,2,5,6,4]$, let $w=[5,1,6,2,3,4]$, and let $k=4$. We have that

$u^{-1}w=(1,4,3,5)$

Thus $u\centernot{\xrightarrow{k}}w$ because $u(3)<u(4)$, and
$u\centernot{\xrightarrow{k-1}}w$ because both $4$ and $5$ are present in the
cycle. However, if we let $q^{\prime}=5$, then

$ut_{kq^{\prime}}=[3,1,2,6,5,4]$

and

$(ut_{kq^{\prime}})^{-1}w=(1,5)(3,4)$

and hence $ut_{kq^{\prime}}\xrightarrow{k-1}w$. Since $u^{-1}w=(1,4,3,5)$,
this is the case where both $k$ and $q^{\prime}=5$ are present. Thus we should
be able to pick $q=3$ to have $ut_{qk}\xrightarrow{k-1}w$, since this is the
minimal (only) element in the cycle after $k$ such that $u(q)<u(k)$.
Calculating this, we get

$ut_{qk}=[3,1,5,2,6,4]$

and

$(ut_{qk})^{-1}w=(1,3,5)$

Thus $ut_{qk}\xrightarrow{k-1}w$. One can check that this is the only index
that satisfies the condition. Going in the opposite direction, since
$(ut_{qk})^{-1}w=(1,3,5)$ we would have picked $q^{\prime}=5$ via the proof.
Additionally note that
$P_{k-1}(ut_{qk},w)=\\{1\\}=P_{k-1}(ut_{kq^{\prime}},w)$.

###### Proof of Proposition 4.4.

We are trying to prove that

$\operatorname{\mathfrak{S}}_{u}(x;y)E_{k}(x;z_{j})=\sum_{u\xrightarrow{k}w}\mathrm{weight}_{u,k}^{w}(y;z_{j})\operatorname{\mathfrak{S}}_{w}(x;y)$

We note that

$\mathrm{weight}_{u,k}^{w}(y;z_{j})=E_{k-\ell(u,w)}(y_{P_{k}(u,w)};z_{j})=\prod_{i\in
P_{k}(u,w)}(y_{i}-z_{j})$

so, re-expressing the desired result, we want to prove that

$\operatorname{\mathfrak{S}}_{u}(x;y)E_{k}(x;z_{j})=\sum_{u\xrightarrow{k}w}\left(\prod_{i\in
P_{k}(u,w)}(y_{i}-z_{j})\right)\operatorname{\mathfrak{S}}_{w}(x;y)$

We prove this by induction on $k$. For $k=1$, the result is covered by Lemma
7.2, where there are no negative terms. Otherwise, assume the result holds for
$k-1$. Note that

$E_{k}(x;z_{j})=E_{k-1}(x;z_{j})(x_{k}-z_{j})$

We apply Lemma 7.2 to multiply $\operatorname{\mathfrak{S}}_{u}(x;y)$ by
$x_{k}-z_{j}$. Namely, the computation of
$\operatorname{\mathfrak{S}}_{u}(x;y)E_{k}(x;z_{j})$ becomes

$\operatorname{\mathfrak{S}}_{u}(x;y)(x_{k}-z_{j})E_{k-1}(x;z_{j})=(y_{u(k)}-z_{j})\operatorname{\mathfrak{S}}_{u}(x;y)E_{k-1}(x;z_{j})+\sum_{\ell(ut_{kq})=\ell(u)+1}\mathrm{sign}(q-k)\operatorname{\mathfrak{S}}_{ut_{kq}}(x;y)E_{k-1}(x;z_{j})$

Applying the induction hypothesis to expand the terms on the right hand side
by multiplying the double Schubert polynomial by the factor
$E_{k-1}(x;z_{j})$, we obtain

(7.1) $\sum_{w:u\xrightarrow{k-1}w}(y_{u(k)}-z_{j})\left(\prod_{i\in
P_{k-1}(u,w)}(y_{i}-z_{j})\right)\operatorname{\mathfrak{S}}_{w}(x;y)$

as well as

(7.2) $\sum_{\begin{subarray}{c}q^{\prime}>k\\\
\ell(ut_{kq^{\prime}})=\ell(u)+1\end{subarray}}\sum_{w:ut_{kq^{\prime}}\xrightarrow{k-1}w}\left(\prod_{i\in
P_{k-1}(ut_{kq^{\prime}},w)}(y_{i}-z_{j})\right)\operatorname{\mathfrak{S}}_{w}(x;y)$

and

(7.3) $-\sum_{\begin{subarray}{c}q<k\\\
\ell(ut_{qk})=\ell(u)+1\end{subarray}}\sum_{w:ut_{qk}\xrightarrow{k-1}w}\left(\prod_{i\in
P_{k-1}(ut_{qk},w)}(y_{i}-z_{j})\right)\operatorname{\mathfrak{S}}_{w}(x;y)$

The terms we want to eliminate are as follows

  1. (1)

Terms in (7.1) such that $w(k)\neq u(k)$.

  2. (2)

Terms in (7.2) such that $u\centernot{\xrightarrow{k}}w$.

  3. (3)

All terms in (7.3).

For all arguments here we assume that $\ell(ut_{ab})=\ell(u)+1$ for all
reflections $t_{ab}$ we consider. For each $w$ occurring in a term of type
(1), we identify a term in the sum (7.3) that cancels it. Assume then that $w$
is such that $u\xrightarrow{k-1}w$ but $u(k)\neq w(k)$. Then $u(k)>w(k)$ by
Lemma 7.4; by the same lemma, this makes it impossible that
$u\xrightarrow{k}w$. By Lemma 7.8, there exists a unique $q<k$ such that
$ut_{qk}\xrightarrow{k-1}w$. Since
$P_{k-1}(ut_{qk},w)=P_{k-1}(u,w)\cup\\{u(k)\\}$ by the same lemma, the term
corresponding to $w$ in (7.3) corresponding to the permutation $ut_{qk}$
cancels the term corresponding to $w$ in (7.1), applying the induction
hypothesis. Thus for each term of type (1) we have identified a unique term in
(7.3) that cancels it.

Let $q^{\prime}>k$ be a positive integer and let $w$ be an index such that
there is a term corresponding to $ut_{kq^{\prime}}$ and $w$ of type (2) in
(7.2), meaning that $u\centernot{\xrightarrow{k}}w$. By definition we have
that $ut_{kq^{\prime}}\xrightarrow{k-1}w$. We cannot have that
$u\xrightarrow{k-1}w$ by Lemma 7.8 since the existence of the index
$q^{\prime}>k$ contradicts the conclusion of the lemma, so we have that
$u\centernot{\xrightarrow{k}}w$, $u\centernot{\xrightarrow{k-1}}w$, and
$q^{\prime}>k$ is such that $ut_{kq^{\prime}}\xrightarrow{k-1}w$. Therefore,
by Lemma 7.9, $q^{\prime}$ is unique and there is a unique $q<k$ such that
$ut_{qk}\xrightarrow{k-1}w$. By the same lemma,
$P_{k-1}(ut_{qk},w)=P_{k-1}(ut_{kq^{\prime}},w)$, so the two terms
corresponding to these indices have the same weight with opposite signs by the
induction hypothesis, hence they cancel. Thus all terms of type (2) are
canceled from the sum with a term from (7.3) that was not canceled in the
previous paragraph by a term of type (1) since
$u\centernot{\xrightarrow{k-1}}w$.

We claim that at this point all terms in (7.3) have been canceled. Fix $w$.
Note first that if there is a $q<k$ such that $ut_{qk}\xrightarrow{k-1}w$,
then by Lemma 7.7 we cannot have that both $u\xrightarrow{k}w$ and
$u\xrightarrow{k-1}w$. Thus either $u\centernot{\xrightarrow{k-1}}w$ or
$u\centernot{\xrightarrow{k}}w$. In the case where both are true we identified
a unique corresponding $q^{\prime}>k$ such that
$ut_{kq^{\prime}}\xrightarrow{k-1}w$ and we showed that the corresponding term
has the same coefficient with the opposite sign. Thus all terms with
$u\centernot{\xrightarrow{k-1}}w$ and $u\centernot{\xrightarrow{k}}w$ have
been canceled. If $u\centernot{\xrightarrow{k-1}}w$ but $u\xrightarrow{k}w$,
by Lemma 7.6 $\operatorname{\mathfrak{S}}_{w}(x;y)$ has a coefficient of $0$
in (7.3). Finally, suppose $u\xrightarrow{k-1}w$ but
$u\centernot{\xrightarrow{k}}w$. Then the $q<k$ corresponding to the term in
the sum such that $ut_{qk}\xrightarrow{k-1}w$ is the unique index with this
property by Lemma 7.8, and as argued previously it has been canceled. The
claim follows.

At this point the only terms that remain are those such that
$u\xrightarrow{k}w$ in (7.1) and (7.2). The weight in (7.1) is correct by the
induction hypothesis because we canceled the terms with $u(k)\neq w(k)$, and
for (7.2), fixing $q^{\prime}>k$, since $ut_{kq^{\prime}}$ differs from $u$
only at $k$ and $q^{\prime}$ we have that
$P_{k}(u,w)=P_{k-1}(ut_{kq^{\prime}},w)$. By Lemma 7.7, no $w$ that occurs in
(7.1) also occurs in (7.2). By Lemma 7.6, if $u\centernot{\xrightarrow{k-1}}w$
and $u\xrightarrow{k}w$ there is exactly one $q^{\prime}>k$ such that
$ut_{kq^{\prime}}\xrightarrow{k-1}w$, so all
$\operatorname{\mathfrak{S}}_{w}(x;y)$ such that $u\xrightarrow{k}w$ occur
exactly once and we have the result. ∎

###### Proof of Theorem 7.1.

This follows from Proposition 4.4 coupled with the Cauchy formula for double
Schubert polynomials [21]. Let $e_{i,k}(x)$ be the usual elementary symmetric
polynomial $e_{i}(x_{1},\ldots,x_{k})$ and let
$h_{i,k}(x)=h_{i}(x_{1},\ldots,x_{k})$ be the complete homogeneous symmetric
polynomial of degree $i$ in $x_{1},\ldots,x_{k}$. Note that when we expand the
product in the definition of $E_{k}(x;z_{1})$ we obtain

$E_{k}(x;z_{1})=\sum_{i=0}^{k}e_{i,k}(x)(-z_{1})^{k-i}$

By Proposition 4.4, we have

$\displaystyle\sum_{i=0}^{k}\operatorname{\mathfrak{S}}_{u}(x;y)e_{i,k}(x)(-z_{1})^{k-i}$
$\displaystyle=\operatorname{\mathfrak{S}}_{u}(x;y)E_{k}(x;z_{1})$
$\displaystyle=\sum_{u\xrightarrow{k}w}E_{k-\ell(u,w)}(y_{P_{k}(u,w)};z)\operatorname{\mathfrak{S}}_{w}(x;y)$
$\displaystyle=\sum_{u\xrightarrow{k}w}\sum_{i=\ell(u,w)}^{k}e_{i-\ell(u,w),k-\ell(u,w)}(y_{P_{k}(u,w)})\operatorname{\mathfrak{S}}_{w}(x;y)(-z_{1})^{(k-\ell(u,w))-(i-\ell(u,w))}$

Equating the coefficients of powers of $-z_{1}$ in the above equation we
obtain that

$\operatorname{\mathfrak{S}}_{u}(x;y)e_{i,k}(x)=\sum_{u\xrightarrow{k}w}{e_{i-\ell(u,w),k-\ell(u,w)}(y_{P_{k}(u,w)})\operatorname{\mathfrak{S}}_{w}(x;y)}$

By the Cauchy formula in [21] we have that

$E_{p,k}(x;z)=\sum_{i=0}^{p}e_{i,k}(x)h_{p-i,k+1-p}(-z)$

Therefore the coefficient of $\operatorname{\mathfrak{S}}_{w}(x;y)$ in
$\operatorname{\mathfrak{S}}_{u}(x;y)E_{p,k}(x;z)$ is, replacing the index $i$
with $j+\ell(u,w)$,

$\sum_{j=0}^{p-\ell(u,w)}e_{j,k-\ell(u,w)}(y_{P_{k}(u,w)})h_{p-\ell(u,w)-j,(k-\ell(u,w))+1-(p-\ell(u,w))}(-z)$

which is exactly $E_{p-\ell(u,w),k-\ell(u,w)}(y_{P_{k}(u,w)};z)$, and we have
the result. ∎

Via the following formula, our Pieri formula is also positive in the sense of
Conjecture 1.1 as well as the equivariant specialization.

######  Proposition 7.10.

Let $p,k$ with $1\leq p\leq k$ be integers. Let $\mathcal{S}_{p,k}$ be the set
of sequences $(a_{0},\ldots,a_{p-1})$ such that $1\leq a_{i}\leq k+1-p$ for
all $i$ and $a_{i}\leq a_{i+1}$ for all $0\leq i<p-1$. Then

$E_{p,k}(x;z)=\sum_{(a_{0},\ldots,a_{p-1})\in\mathcal{S}_{p,k}}\prod_{i=0}^{p-1}(x_{a_{i}+i}-z_{a_{i}})$

###### Proof.

This follows from the formula [23, (4)]. A term in a factorial Schur function
is written as the product of linear factors $x_{T(\alpha)}-z_{T(\alpha)+c-r}$,
where $T$ is a tableau, $\alpha$ ranges over all boxes, and $\alpha$ is in
column $c$ and row $r$. For $E_{p,k}(x;z)$, this tableau is on a single
column, so that $c=1$ and $1\leq r\leq p$, and $T$ is strictly increasing
along the rows. ∎

######  Example 7.5.

We select some of the coefficients in Example 7.1 to see that they are
nonnegative when substituting $z=y$.

$\displaystyle E_{3,4}(y_{1},y_{3},y_{4},y_{5};z)$
$\displaystyle=(y_{1}-z_{1})(y_{3}-z_{1})(y_{4}-z_{1})+(y_{1}-z_{1})(y_{3}-z_{1})(y_{5}-z_{2})$
$\displaystyle+(y_{1}-z_{1})(y_{4}-z_{2})(y_{5}-z_{2})+(y_{3}-z_{2})(y_{4}-z_{2})(y_{5}-z_{2})$
$\displaystyle\Rightarrow(y_{3}-y_{2})(y_{4}-y_{2})(y_{5}-y_{2})$
$\displaystyle E_{2,3}(y_{3},y_{4},y_{5};z)$
$\displaystyle=(y_{3}-z_{1})(y_{4}-z_{1})+(y_{3}-z_{1})(y_{5}-z_{2})+(y_{4}-z_{2})(y_{5}-z_{2})$
$\displaystyle\Rightarrow(y_{3}-y_{1})(y_{4}-y_{1})+(y_{3}-y_{1})(y_{5}-y_{2})+(y_{4}-y_{2})(y_{5}-y_{2})$
$\displaystyle E_{1,2}(y_{1},y_{3};z)$
$\displaystyle=(y_{1}-z_{1})+(y_{3}-z_{2})$ $\displaystyle\Rightarrow
y_{3}-y_{2}$

##  8\. A more general result

We note that in Theorem 3.1 the value of $p$ is unimportant as long as the
condition is satisfied; the computation of the coefficient $e_{uv}^{w}(y;z)$
has nothing to do with $p$. Indeed, Theorem 3.1 is not the most general
possible result that comes out of this method. The most general result is the
following.

######  Theorem 8.1.

Let $u,v\in S_{\infty}$ and suppose $v^{-1}\mu_{v}=s_{i_{1}}\cdots s_{i_{m}}$
with $\ell(us_{i_{j}})>\ell(u)$ for all $j$. Then

$\operatorname{\mathfrak{S}}_{u}(x;y)\operatorname{\mathfrak{S}}_{v}(x;z)=\sum_{w\in
S_{\infty}}e_{uv}^{w}(y;z)\operatorname{\mathfrak{S}}_{w}(x;y)$

The proof of this result is virtually identical and we will not include it.
One obvious case where this works is where $u$ is arbitrary and $v$ is
dominant, so that $v=\mu_{v}$ and $v^{-1}\mu_{v}$ is the identity. We
illustrate a less trivial case, computing all of the coefficients that occur
in the product.

######  Example 8.1.

Let $u=[4,1,3,2]$ and let $v=[3,1,4,2]$. Then $u$ and $v$ do not satisfy the
conditions of Theorem 3.1, but Theorem 8.1 applies. We have

$\displaystyle\mu_{v}$ $\displaystyle=[3,4,1,2]$
$\displaystyle\mathfrak{c}(\mu_{v})$ $\displaystyle=(2,2)$
$\displaystyle\lambda(v)$ $\displaystyle=(2,2)$ $\displaystyle v^{-1}\mu_{v}$
$\displaystyle=[1,3,2]$ $[4,1,3,2]$
---
4 | 4 | 4
1 | 1 | 3
3 | 3 | 1
2 | 2 | 2
$(y_{1}-z_{1})(y_{4}-z_{1})(y_{4}-z_{2})$

$[4,1,3,2]$ 4 4 4 1 3 3 3 1 1 2 2 2 $(y_{3}-z_{2})(y_{4}-z_{1})(y_{4}-z_{2})$
$[4,2,3,1]$ 4 4 4 1 2 3 3 3 2 2 1 1 $(y_{4}-z_{1})(y_{4}-z_{2})$

$((y_{1}-z_{1})(y_{4}-z_{1})(y_{4}-z_{2})+(y_{3}-z_{2})(y_{4}-z_{1})(y_{4}-z_{2}))\operatorname{\mathfrak{S}}_{[4,1,3,2]}(x;y)+(y_{4}-z_{1})(y_{4}-z_{2})\operatorname{\mathfrak{S}}_{[4,2,3,1]}(x;y)$
$[5,1,3,2,4]$
---
4 | 4 | 5
1 | 3 | 3
3 | 1 | 1
2 | 2 | 2
5 | 5 | 4
$(y_{3}-z_{2})(y_{4}-z_{1})$

$[5,1,3,2,4]$ 4 4 5 1 1 3 3 3 1 2 2 2 5 5 4 $(y_{1}-z_{1})(y_{4}-z_{1})$
$[5,1,3,2,4]$ 4 5 5 1 1 3 3 1 1 2 2 2 5 4 4 $(y_{1}-z_{1})(y_{5}-z_{2})$
$[5,1,3,2,4]$ 4 5 5 1 3 3 3 1 1 2 2 2 5 4 4 $(y_{3}-z_{2})(y_{5}-z_{2})$

$((y_{3}-z_{2})(y_{4}-z_{1})+(y_{1}-z_{1})(y_{4}-z_{1})+(y_{1}-z_{1})(y_{5}-z_{1})+(y_{3}-z_{2})(y_{5}-z_{2}))\operatorname{\mathfrak{S}}_{[5,1,3,2,4]}(x;y)$
$[4,1,5,2,3]$
---
4 | 4 | 4
1 | 3 | 5
3 | 1 | 1
2 | 2 | 2
5 | 5 | 3
$(y_{4}-z_{1})(y_{4}-z_{2})$

$[5,1,4,2,3]$ 4 5 5 1 3 4 3 1 1 2 2 2 5 4 3 $y_{5}-z_{2}$ $[5,1,4,2,3]$ 4 4 5
1 3 4 3 1 1 2 2 2 5 5 3 $y_{4}-z_{1}$

$(y_{4}-z_{1})(y_{4}-z_{2})\operatorname{\mathfrak{S}}_{[4,1,5,2,3]}(x;y)+((y_{5}-z_{2})+(y_{4}-z_{1}))\operatorname{\mathfrak{S}}_{[5,1,4,2,3]}(x;y)$
$[5,2,3,1,4]$
---
4 | 5 | 5
1 | 2 | 3
3 | 3 | 2
2 | 1 | 1
5 | 4 | 4
$y_{5}-z_{2}$

$[5,2,3,1,4]$ 4 4 5 1 2 3 3 3 2 2 1 1 5 5 4 $y_{4}-z_{1}$

$((y_{5}-z_{2})+(y_{4}-z_{1}))\operatorname{\mathfrak{S}}_{[5,2,3,1,4]}(x;y)$
$[6,1,3,2,4,5]$
---
4 | 5 | 6
1 | 1 | 3
3 | 3 | 1
2 | 2 | 2
5 | 4 | 4
6 | 6 | 5
$y_{1}-z_{1}$

$[6,1,3,2,4,5]$ 4 5 6 1 3 3 3 1 1 2 2 2 5 4 4 6 6 5 $y_{3}-z_{2}$
$[6,1,4,2,3,5]$ 4 5 6 1 3 4 3 1 1 2 2 2 5 4 3 6 6 5 $1$ $[6,2,3,1,4,5]$ 4 5 6
1 2 3 3 3 2 2 1 1 5 4 4 6 6 5 $1$

$((y_{1}-z_{1})+(y_{3}-z_{2}))\operatorname{\mathfrak{S}}_{[6,1,3,2,4,5]}(x;y)+\operatorname{\mathfrak{S}}_{[6,1,4,2,3,5]}(x;y)+\operatorname{\mathfrak{S}}_{[6,2,3,1,4,5]}(x;y)$

##  9\. Python package for computing Schubert products

We have written a python package `schubmult` that is available in the central
python package repository which requires python $3.9$ or higher that allows
one to compute products of ordinary Schubert polynomials, products of double
Schubert polynomials in the same set of variables, and products of double
Schubert polynomials in different sets of variables. When one installs the
package with

pip install schubmult

this installs three executables on the user’s system: `schubmult_py` for
ordinary Schubert polynomials (so named so as not to conflict with existing
software named `schubmult`), `schubmult_double` for double Schubert
polynomials in the same set of variables, with the result expressed with
nonnegative coefficients in terms of the negative roots, and `schubmult_yz`
for computing Molev-Sagan products of double Schubert polynomials. It is
entirely platform independent, provided the python installation can be
configured properly on the system. We have tested it on both Linux and
Windows.

It is recommended you periodically check for new versions, which you can do
directly by running

pip install schubmult --upgrade

when you already have `schubmult`.

The method of calculation is to express one of the (double) Schubert
polynomials in the product in terms of (factorial) elementary symmetric
polynomials and apply the Pieri formula. There’s no choice of which one to
express in this way in the Molev-Sagan case, but for `schubmult_py` and
`schubmult_double` it picks the one that is closest to being dominant. Even in
the ordinary Schubert polynomial case it is faster than currently existing
software in most cases, sometimes dramatically.

All three executables have the same command line syntax, which is the same as
the command line syntax for `schubmult` from `lrcalc`. An instructive example
is to compute

schubmult_py 1 2 4 9 11 6 8 12 3 5 7 10 - 6 8 1 2 3 4 7 10 12 14 5 9 11 13

The number of permutations on the command line is not limited to two, so we
could for example compute the product of three Schubert polynomials as

schubmult_py 6 1 4 3 2 5 - 7 6 3 5 1 2 4 - 5 1 4 3 2

For an example Molev-Sagan product, one could execute

schubmult_yz 1 3 4 6 2 5 - 2 1 5 7 3 4 6

and the same product in equivariant cohomology can be computed as

schubmult_double 1 3 4 6 2 5 - 2 1 5 7 3 4 6

where some terms will vanish.

For all three executables, one can specify the input as the code of the
permutation instead of the permutation itself with the command line argument
`-code`. For example,

schubmult_yz -code 0 1 1 2 - 1 0 2 3

The output will then express the permutations as codes as well.

The coefficients in `schubmult_yz` are expressed in terms of $y_{i}-z_{j}$. If
desired, the coefficients can be displayed positively as polynomials in
$y_{i}-z_{j}$ using the command line option `--display-positive`, for example

schubmult_yz 1 3 4 6 2 5 - 2 1 5 7 3 4 6 --display-positive

Feasibility of displaying the result positively varies, and one should expect
to run into some cases such that the computation will not finish in a
reasonable amount of time. As this is still only always possible
conjecturally, it is conceivable one could run into a counterexample; if one
is found, please email the counterexample to the author.

The coefficients in `schubmult_double` are subjected to a change of variables
in order for them to visibly have nonnegative coefficients.

Though the package was primarily intended to be used through the installed
executables, it can also be imported into your own python script and the
function `schubmult` used programmatically. For example,

from schubmult.schubmult_yz import schubmultcoeff_dict = schubmult({(1, 3, 4,
6, 2, 5): 1}, (2, 1, 5, 7, 3, 4, 6))The return value is a python `dict` where
the keys are permutations, which are expressed as `tuple`s of `int`s, and the
values are either `int`s (for `schubmult.schubmult_py`) or `symengine` objects
(which can be polynomials). The `dict` representation is intended to represent
a linear combination of (double) Schubert polynomials with the values as the
coefficients. Note that there may be values of $0$ in the resulting `dict`, or
values that simplify to $0$ but do not appear immediately to be $0$ if they
are `symengine` objects. No $0$ values will be displayed in `schubmult_py` or
`schubmult_double`, but there may be coefficients displayed in `schubmult_yz`
that simplify to $0$. Simplifying a polynomial is an expensive calculation,
and in the interest of saving time this is not done in the output, except in
`schubmult_double`.

In addition to python, `schubmult` is also functional in Sage.

Visit the pypi page at

https://pypi.org/project/schubmult

for updates on the latest version.

## References

  * [1] Bergeron, N., and Billey, S. RC-graphs and Schubert polynomials.  Experimental Math. 2, 4 (1993), 257–269.
  * [2] Bergeron, N., and Sottile, F. Skew Schubert functions and the Pieri formula for flag manifolds.  Trans. Amer. Math. Soc. 354, 2 (2001), 651–673.
  * [3] Bernstein, I. N., Gelfand, I. M., and Gelfand, S. I. Schubert cells and the cohomology of the spaces G/P.  Russian Math. Surveys 28 (1973), 1–26.
  * [4] Björner, A., and Brenti, F. Combinatorics of Coxeter Groups.  Springer, 2005.
  * [5] Buch, A. S. Mutations of puzzles and equivariant cohomology of two-step flag varieties.  Ann. of Math. (2015), 173–220.
  * [6] Bump, D., McNamara, P. J., and Nakasuji, M. Factorial Schur functions and the Yang-Baxter equation.  arXiv preprint arXiv:1108.3087 (2011).
  * [7] Chen, W. Y., Yan, G.-G., and Yang, A. L. The skew Schubert polynomials.  European J. Combin. 25, 8 (2004), 1181–1196.
  * [8] Fan, N. J., Guo, P. L., and Xiong, R. Bumpless pipe dreams meet Puzzles.  arXiv preprint arXiv:2309.00467 (2023).
  * [9] Graham, W. Positivity in equivariant Schubert calculus.  Duke Math. J. 109, 3 (2001), 599–614.
  * [10] (https://mathoverflow.net/users/62135/matt samuel), M. S. Product of a Schubert polynomial and a double Schubert polynomial.  MathOverflow.  URL:https://mathoverflow.net/q/212762 (version: 2016-09-06).
  * [11] Huang, D. Schubert products for permutations with separated descents.  International Mathematics Research Notices (November 2022).
  * [12] Kirillov, A. N. Skew divided difference operators and Schubert polynomials.  SIGMA. Symmetry, Integrability and Geometry: Methods and Applications 3 (2007), 072.
  * [13] Knutson, A. Schubert polynomials, pipe dreams, equivariant classes, and a co-transition formula.  arXiv.org:1909.13777 (2019).
  * [14] Knutson, A., and Tao, T. Puzzles and (equivariant) cohomology of Grassmannians.  Duke Math. J. 119, 2 (2003), 221–260.
  * [15] Knutson, A., and Zinn-Justin, P. Schubert calculus and quiver varieties.  https://pi.math.cornell.edu/allenk/boston2019.pdf, 2019.  Accessed 2023-06-10.
  * [16] Knutson, A., and Zinn-Justin, P. Schubert puzzles and integrability III: separated descents.  arXiv preprint arXiv:2306.13855 (2023).
  * [17] Kohnert, A. Multiplication of a Schubert polynomial by a Schur polynomial.  Ann. Comb. 1, 1 (1997), 367–375.
  * [18] Kostant, B., and Kumar, S. The nil Hecke ring and cohomology of G/P for a Kac-Moody group G.  Proceedings of the National Academy of Sciences 83, 6 (1986), 1543–1545.
  * [19] Lascoux, A., and Schützenberger, M. Polynômes de Schubert.  Comptes Rendus de l’Académie des Sciences, Série I 294, 13 (1982), 447–450.
  * [20] Lenart, C., and Sottile, F. Skew Schubert polynomials.  Proc. Amer. Math. Soc. 131, 11 (2003), 3319–3328.
  * [21] Macdonald, I. G. Notes on Schubert Polynomials.  Université Du Québec à Montréal, Dép. de mathématiques et d’informatique, 1991.
  * [22] Molev, A. Littlewood–Richardson polynomials.  Journal of Algebra 321, 11 (2009), 3450–3468.
  * [23] Molev, A., and Sagan, B. A Littlewood-Richardson rule for factorial Schur functions.  Trans. Amer. Math. Soc. 351, 11 (1999), 4429–4443.
  * [24] Purbhoo, K., and Sottile, F. A Littlewood-Richardson rule for Grassmannian permutations.  Proc. Am. Math. Soc. 137 (2009), 1875–1882.
  * [25] Robinson, S. A Pieri-Type Formula for $H^{*}T(SL_{n}(C)/B)$.  J. Algebra 249, 1 (2002), 38–58.
  * [26] Samuel, M. J. The Leibniz formula for divided difference operators associated to Kac-Moody root systems.  PhD thesis, Rutgers, The State University of New Jersey, 2014.
  * [27] Sottile, F. Pieri’s rule for flag manifolds and Schubert polynomials.  Ann. Inst. Fourier 46, 1 (1996), 89–110.
  * [28] Tamvakis, H. Tableau formulas for skew Schubert polynomials.  arXiv preprint arXiv:2008.07034 (2020).