## Notes on Schubert PolynomialsChapter 4

Last update: 28 June 2013

## Schubert Polynomials (1)

Let $\delta ={\delta }_{n}=\left(n-1,n-2,\dots ,1,0\right),$ so that

$xδ=x1n-1 x2n-2… xn-1.$

For each permutation $w\in {S}_{n}$ the Schubert polynomial ${𝔖}_{w}$ is defined to be

$(4.1) 𝔖w=∂w-1w0 (xδ)$

where as usual ${w}_{0}$ is the longest element of ${S}_{n}\text{.}$

(4.2) Let $v,w\in {S}_{n}\text{.}$ Then

$∂v𝔖w= { 𝔖wv-1 if ℓ(wv-1) =ℓ(w)-ℓ(v), 0 otherwise.$

In particular,

$∂i𝔖w= { 𝔖wsi if w(i)> w(i+1), 0 if w(i)< w(i+1).$

 Proof. From (2.7) we have $∂v∂w-1w0= { ∂vw-1w0 if ℓ(v)+ ℓ(w-1w0)= ℓ(vw-1w0), 0 otherwise.$ Now $ℓ(v)+ℓ (w-1w0)= ℓ(v)+ ℓ(w0)-ℓ(w)$ and $ℓ(vw-1w0)= ℓ(w0)-ℓ (wv-1)$ by (1.6). Hence ${\partial }_{v}{𝔖}_{w}={\partial }_{v}{\partial }_{{w}^{-1}{w}_{0}}{x}^{\delta }$ is equal to ${\partial }_{v{w}^{-1}{w}_{0}}{x}^{\delta }={𝔖}_{w{v}^{-1}}$ if $\ell \left(w\right)-\ell \left(v\right),$ and is zero otherwise. $\square$

(4.3)
 (i) ${𝔖}_{{w}_{0}}={x}^{\delta },\phantom{\rule{1em}{0ex}}{𝔖}_{1}=1\text{.}$ (ii) For each $w\in {S}_{n},$ ${𝔖}_{w}$ is a non-zero homogeneous polynomial in ${x}_{1},\dots ,{x}_{n-1}$ of degree $\ell \left(w\right),$ of the form $𝔖w=∑αcα xα$ summed over $\alpha \in {ℕ}^{n-1}$ such that $\alpha \subset \delta$ (i.e., ${\alpha }_{i}\le n-i$ for each $i\text{)}$ and $|\alpha |=\ell \left(w\right)\text{.}$ (iii) ${𝔖}_{w}$ is symmetrical in ${x}_{i},{x}_{i+1}$ if and only if $w\left(i\right) (iv) If $r$ is the last descent of $w\in {S}_{n}$ (i.e., if $w\left(r\right)>w\left(r+1\right)$ and $w\left(r+1\right) then ${𝔖}_{w}\in {P}_{r}=ℤ\left[{x}_{1},\dots ,{x}_{r}\right],$ and ${𝔖}_{w}\notin {P}_{r-1}\text{.}$

 Proof. (i) That ${𝔖}_{{w}_{0}}={x}^{\delta }$ is clear from the definition (4.1). Also by (2.11) we have $𝔖1=∂w0xδ =sδ-δ=1.$ (ii) The operator ${\partial }_{{w}^{-1}{w}_{0}}$ lowers degrees by $\ell \left({w}^{-1}{w}_{0}\right)=\ell \left({w}_{0}\right)-\ell \left({w}^{-1}\right)=\frac{1}{2}n\left(n-1\right)-\ell \left(w\right)\text{.}$ Hence ${𝔖}_{w}={\partial }_{{w}^{-1}{w}_{0}}{x}^{\delta }$ is homogeneous of degree $\ell \left(w\right)\text{.}$ If now $\alpha \in {ℕ}^{n-1}$ is such that $\alpha \subset \delta ,$ then by (2.1) ${\partial }_{r}{x}^{\alpha }$ is a linear combination of monomials ${x}^{\beta }$ such that ${\beta }_{i}={\alpha }_{i}$ if $i\ne r,r+1,$ and $max(βi,βi+1) ≤max(αi,αi+1) -1≤n-i-1,$ so that $\beta \subset \delta \text{.}$ Hence the linear span ${H}_{n}$ of the monomials ${x}^{\alpha },\alpha \subset \delta$ is mapped into itself by each ${\partial }_{r}$ $\left(1\le r\le n-1\right)$ and hence by each ${\partial }_{w},$ $w\in {S}_{n}\text{.}$ Hence ${𝔖}_{w}\in {H}_{n}$ for each $w\in {S}_{n}\text{.}$ (iii) ${𝔖}_{w}$ is symmetrical in ${x}_{i}$ and ${x}_{i+1}$ if and only if ${s}_{i}{𝔖}_{w}={𝔖}_{w},$ that is to say if and only if ${\partial }_{i}{𝔖}_{w}=0,$ which by (4.2) is equivalent to $w\left(i\right) (iv) ${𝔖}_{w}$ is symmetrical in ${x}_{r+1},\dots ,{x}_{n}$ by (iii) above, but does not contain ${x}_{n},$ hence does not contain any of ${x}_{r+1},\dots ,{x}_{n}\text{.}$ $\square$

Remark. We shall show later (4.17) that the coefficients in (4.3)(ii) are always non-negative integers.

(4.4) For $i=1,2,\dots ,n-1$ we have

$𝔖si=x1+x2 +…+xi.$

 Proof. By (4.3), ${𝔖}_{{s}_{i}}$ is a homogeneous symmetric polynomial of degree $\ell \left({s}_{i}\right)=1$ in ${x}_{1},\dots ,{x}_{i},$ hence is equal to $c\left({x}_{1}+\dots +{x}_{i}\right)$ for some integer $c\text{.}$ But ${\partial }_{i}{𝔖}_{{s}_{i}}={𝔖}_{1}=1$ by (4.2) and (4.3)(i), hence $c=1\text{.}$ $\square$

(4.5) (Stability) Let $m>n$ and let $i:{S}_{n}↪{S}_{m}$ be the embedding. Then

$𝔖w=𝔖i(w)$

for all $w\in {S}_{n}\text{.}$

 Proof. We may assume that $m=n+1\text{.}$ Let ${w}_{0}^{\prime }$ be the longest element of ${S}_{n+1},$ then ${w}_{0}^{\prime }={w}_{0}{s}_{n}{s}_{n-1}\dots {s}_{1},$ where ${w}_{0}$ is the longest element of ${S}_{n},$ and hence $𝔖i(w) = ∂w-1w0′ (x1nx2n-1…xn) = ∂w-1w0 ∂n∂n-1… ∂1 (x1nx2n-1…xn) = ∂w-1w0 (x1n-1x2n-2…xn-1)$ (because ${\partial }_{1}\left({x}_{1}^{n}{x}_{2}^{n-1}\dots {x}_{n}\right)={x}_{1}^{n-1}{x}_{2}^{n-1}{x}_{3}^{n-2}\dots {x}_{n},$ hence ${\partial }_{2}{\partial }_{1}\left({x}_{1}^{n}{x}_{2}^{n-1}\dots {x}_{n}\right)={x}_{1}^{n-1}{x}_{2}^{n-2}{x}_{3}^{n-2}{x}_{4}^{n-3}\dots {x}_{n},$ and so on.) $\square$

From (4.5) it follows that ${𝔖}_{w}$ is a well-defined polynomial for each permutation $w\in {S}_{\infty }={\bigcup }_{n}{S}_{n}\text{.}$

If $u\in {S}_{m}$ and $v\in {S}_{n},$ we denote by $u×v$ the permutation

$u×v= ( u(1),…,u(m), v(1)+m,…,v(n) +m )$

in ${S}_{m+n}\text{.}$ We have then

$(4.6) 𝔖u×v= 𝔖u· 𝔖1m×v$

where ${1}_{m}$ is the identity element of ${S}_{m}\text{.}$

 Proof. We shall make use of the following fact: if $f$ is a polynomial in ${x}_{1},{x}_{2},\dots ,$ and ${\partial }_{i}f=0$ for all $i\ge 1,$ then $f$ is a constant. For $f\in {P}_{n}=ℤ\left[{x}_{1},\dots ,{x}_{n}\right]$ for some $n,$ and is symmetric in ${x}_{1},\dots ,{x}_{n+1}$ because ${\partial }_{1}f=\dots ={\partial }_{n}f=0\text{.}$ To prove (4.6) we proceed by induction on $\ell \left(u\right)+\ell \left(v\right)\text{.}$ If $\ell \left(u\right)=\ell \left(v\right)=0$ then $u={1}_{m},$ $v={1}_{n},$ and both sides of (4.6) are equal to $1\text{.}$ Let $F(u,v)= 𝔖u×v-𝔖u 𝔖1m×v.$ By the remark above, it is enough to show that ${\partial }_{i}F\left(u,v\right)=0$ for each $i\text{.}$ Suppose first that $i Then $∂iF(u,v)=∂i (𝔖u×v)-∂i (𝔖u)·𝔖1m×v$ because ${\partial }_{i}\left({𝔖}_{{1}_{m}×v}\right)=0$ by (4.2). Hence we have ${\partial }_{i}F\left(u,v\right)=0$ if $\ell \left(u{s}_{i}\right)>\ell \left(u\right)\text{;}$ and if $\ell \left(u{s}_{i}\right)<\ell \left(u\right)$ then $∂iF(u,v)=F (usi,v)$ which is zero by the inductive hypothesis. Likewise, if $i>m$ we have $∂iF(u,v)= { F(u,vsi) if ℓ(vsi) <ℓ(v), 0 otherwise,$ and so again ${\partial }_{i}F\left(uv\right)=0$ by the inductive hypothesis. Finally, if $i=m$ we have $\ell \left(\left(u×v\right){s}_{m}\right)>\ell \left(u×v\right),$ because $(u×v)(m)= u(m) and therefore ${\partial }_{m}$ kills ${𝔖}_{u×v}$ and ${𝔖}_{{1}_{m}×v}\text{;}$ moreover, ${\partial }_{m}{𝔖}_{u}=0,$ because ${𝔖}_{u}\in ℤ\left[{x}_{1},\dots ,{x}_{m-1}\right]\text{.}$ Hence ${\partial }_{m}F\left(u,v\right)=0,$ and the proof is complete. $\square$

For certain classes of permutations there are explicit formulas for ${𝔖}_{w}\text{.}$ We consider first the case where $w$ is dominant, of shape $\lambda$ (so that the diagram of $w$ coincides with the diagram of $\lambda \text{).}$

(4.7) If $w$ is dominant of shape $\lambda ,$ then

$𝔖w=xλ.$

 Proof. We use descending induction on $\ell \left(w\right)\text{.}$ where $w\in {S}_{n}\text{.}$ The result is true for $w={w}_{0}$ by (4.3)(i), since ${w}_{0}$ is dominant of shape $\delta \text{.}$ Suppose $w\in {S}_{n},$ $w\ne {w}_{0}$ and $w$ is dominant of shape $\lambda \text{.}$ Then $\lambda \subset \delta$ and $\lambda \ne \delta \text{.}$ Let $r\ge 0$ be the largest integer such that ${\lambda }_{i}^{\prime }=n-i$ for $1\le i\le r,$ and let $a={\lambda }_{r+1}^{\prime }+1\le n-r-1\text{.}$ Then $w{s}_{a}$ is dominant of length $\ell \left(w\right)+1,$ and $\lambda \left(w{s}_{a}\right)=\lambda +{\epsilon }_{a},$ where ${\epsilon }_{a}$ is the vector whose ${a}^{\text{th}}$ component is $1$ and all other components zero. Hence we have $𝔖w=∂a𝔖wsa =∂a(xaxλ)= xλ,$ because ${\lambda }_{a}={\lambda }_{a+1}\text{.}$ $\square$

Conversely, every monomial ${x}^{\lambda }$ (where $\lambda$ is a partition) occurs as a Schubert polynomial, namely as ${𝔖}_{w}$ where $w$ is the permutation with code $c\left(w\right)=\lambda \text{.}$

Suppose next that $w$ is Grassmannian, with descent at $r\text{.}$

(4.8) If $w$ is Grassmannian of shape $\lambda ,$ then ${𝔖}_{w}$ is the Schur function ${s}_{\lambda }\left({X}_{r}\right),$ where $r$ is the unique descent of $w,$ and ${X}_{r}={x}_{1}+\dots +{x}_{r}\text{.}$

 Proof. We may assume that $w\ne 1$ (by (4.3)(i), ${𝔖}_{1}=1\text{).}$ Then $r\ge 1$ and the code of $w$ is $( w(1)-1,w(2)-2, …,w(r)-r )$ so that $\lambda =\left(w\left(r\right)-r,\dots ,w\left(2\right)-2,w\left(1\right)-1\right)\text{.}$ Let $u={w}_{0}^{\left(r\right)}$ be the longest element of ${S}_{r}\text{.}$ Then $wu= ( w(r),…,w(1), w(r+1),w(r+2)… )$ is dominant of shape $\lambda +{\delta }_{r},$ where ${\delta }_{r}=\left(r-1,r-2,\dots ,1,0\right),$ and $\ell \left(wu\right)=\ell \left(w\right)+\ell \left(u\right)\text{.}$ Hence $𝔖w=∂u𝔖wu= ∂u(xλ+δr) =sλ(Xr)$ by (4.2), (4.7) and (2.11). $\square$

Conversely, every Schur function ${s}_{\lambda }\left({X}_{r}\right)$ (where $\lambda$ is a partition of length $\le r\text{)}$ occurs as a Schubert polynomial, namely as ${𝔖}_{w}$ where $w$ is the permutation with code $c\left(w\right)=\left({\lambda }_{r},{\lambda }_{r-1},\dots ,{\lambda }_{1}\right),$

More generally, let $w$ be vexillary with shape $\lambda =\left({\lambda }_{1},\dots ,{\lambda }_{m}\right)$ (where $m=\ell \left(\lambda \right)\text{)}$ and flag $\varphi =\left({\varphi }_{1},\dots ,{\varphi }_{m}\right)$ (Chapter I). Then ${𝔖}_{w}$ is a multi-Schur function (Chapter III), namely

$(4.9) 𝔖w=sλ ( Xϕ1,…, Xϕm )$

where ${X}_{i}={x}_{1}+\dots +{x}_{i}$ for each $i\ge 1\text{.}$

 Proof. The idea is to convert $w$ systematically into a dominant permutation. Recall ((1.23), (1.24)) that if $c\left(w\right)=\left({c}_{1},{c}_{2},\dots \right)$ and ${c}_{i}\le {c}_{i+1}$ for some $i\ge 1,$ then $\ell \left(w{s}_{i}\right)=\ell \left(w\right)+1$ and $(*) c(wsi)= ( c1,…,ci-1, ci+1+1,ci, ci+2,ci+3 ,… ) .$ As in Chapter I let $λ(w)= ( p1m1,…, pkmk )$ where ${p}_{1}>\dots >{p}_{k}>0$ (and each ${m}_{i}\ge 1\text{),}$ and let $ϕ(w)= ( f1m1,…, fkmk )$ where ${f}_{1}\le \dots \le {f}_{k}\text{.}$ Consider first the terms equal to ${p}_{1}$ in the sequence $c\left(w\right)\text{.}$ They occupy the positions ${f}_{1}-{m}_{1}+1,\dots ,{f}_{1}\text{.}$ We shall use $\left(*\right)$ to move them all to the left until they occupy the first ${m}_{1}$ positions, by multiplying $w$ on the right by $u1= (sf1-m1…s2s1) (sf1-m1+1…s3s2) … (sf1-1…sm1+1sm1) .$ Let ${w}_{1}=w{u}_{1}\text{.}$ In the code of ${w}_{1},$ the first ${m}_{1}$ entries will be equal to ${p}_{1}+{f}_{1}-{m}_{1}\text{;}$ the shape of ${w}_{1}$ is $λ(1)=λ(w1)= ( (p1+f1-m1)m1, psm2,…, pkmk ) ,$ and it follows from the description (1.38) of vexillary codes that the terms equal to ${p}_{2}$ in the sequence $c\left({w}_{1}\right)$ will occupy the positions ${f}_{2}-{m}_{2}+1,\dots ,{f}_{2}\text{.}$ The next step is to move those to the left until they occupy the positions ${m}_{1}+1,\dots ,{m}_{1}+{m}_{2}$ by multiplying ${w}_{1}$ on the right by $u2= (sf2-m2…sm1+2sm1+1) (sf2-m2+1…sm1+2)… (sf2-1…sm1+m2).$ Let ${w}_{2}={w}_{1}{u}_{2}\text{;}$ the code of ${w}_{2}$ starts off with ${m}_{1}$ entries to ${p}_{1}+{f}_{1}-{m}_{1},$ then ${m}_{2}$ entries equal to ${p}_{2}+{f}_{2}-{m}_{1}-{m}_{2}\text{;}$ the shape of ${w}_{2}$ is $λ(2)=λ(w2)= ( (p1+f1-m1)m1, (p1+f2-m1-m2)m2, p3m3,…,pkmk ) ,$ and the terms equal to ${p}_{3}$ in the sequence $c\left({w}_{2}\right)$ will occupy the positions ${f}_{3}-{m}_{3}+1,\dots ,{f}_{3}-{m}_{3}\text{.}$ We continue in this way; at the ${r}^{\text{th}}$ stage we define ${w}_{r}={w}_{r-1}{u}_{r},$ where $ur= ( sfr-mr… sm1+…+mr-1+1 ) … ( sfr-1… sm1+…+mr ) ,$ and ${w}_{r}$ has shape $λ(r)=λ(wr)= ( (p1+a1)m1 ,…, (pr+ar)mr ,pr+1mr+1 ,…,pkmk )$ where ${a}_{i}={f}_{i}-\left({m}_{1}+\dots +{m}_{i}\right)\ge 0$ by (1.36). Notice also that $(pi-1+ai-1) -(pi+ai)= (mi+pi-1-pi) -(fi-fi-1) ≥0$ by (1.37). Finally we reach ${w}_{k}=w{u}_{1}\dots {u}_{k},$ which is dominant with shape (and code) $μ=λ(k)= ( (p1+a1)m1 ,…, (pk+ak)mk ) .$ We have $ℓ(w)=|λ| =∑mipi, ℓ(wk)= |λ(k)|= ∑mi(pi+ai) ,$ and $ℓ(ur)=armr (1≤r≤k)$ so that $ℓ(wk)=ℓ(w)+ ∑r=1kℓ(ur)$ and therefore, since $w={w}_{k}{\left({u}_{1}\dots {u}_{k}\right)}^{-1},$ $𝔖w=∂u1… ∂uk𝔖wk$ by (4.2). Now by (4.6) and (3.5') we have $𝔖wk=xμ=sμ (X1,…,Xm)$ where $m={m}_{1}+\dots +{m}_{k}=\ell \left(\lambda \right)\text{.}$ Hence by repeated use of (3.10) we obtain $𝔖wk-1 = ∂uk𝔖wk = sλ(k-1) ( X1,…, Xm1+…+mk-1, Xfk-mk+1,…, Xfk-1,Xfk ) = sλ(k-1) ( X1,…, Xm1+…+mk-1, (Xfk)mk )$ by virtue of (3.6). If we now operate with ${\partial }_{{u}_{k-1}}$ we shall obtain in the same way $𝔖wk-1=∂uk-1 𝔖wk-1= sλ(k-2) ( X1,…, Xm1+…+mk-2, (Xfk-1)mk-1, (Xfk)mk )$ and so finally $𝔖w=sλ ( (Xf1)m1,…, (Xfk)mk ) .$ $\square$

Remarks. 1. As in Chapter I, let

$λ′= ( q1n1,…, qknk )$

be the conjugate partition, so that

$m1+…+mi== qk+1-i (1≤i≤k)$

and therefore

$pi+ai = pi+fi-qk+1-i = gk+1-i$

by (1.41), where $\left({g}_{1}^{{n}_{1}},\dots ,{g}_{k}^{{n}_{k}}\right)$ is the flag of ${w}^{-1}\text{.}$ Thus

$(4.10) μ=λ(k)= ( gkm1, gk-1m2,…, g1mk ) .$

2. The result (4.9) admits a converse. If $\lambda =\left({p}_{1}^{{m}_{1}},\dots ,{p}_{k}^{{m}_{k}}\right)$ as above, every non-zero multi-Schur function ${s}_{\lambda }\left({\left({X}_{{f}_{1}}\right)}^{{m}_{1}},\dots ,{\left({X}_{{f}_{k}}\right)}^{{m}_{k}}\right)$ that satisfies the conditions of the duality theorem (3.8''), namely

$(1) 0≤fi+1-fi≤ mi+1+nk+1-i (1≤i≤k-1),$

is the Schubert polynomial of a vexillary permutation, namely the permutation with shape $\lambda$ and flag $\varphi =\left({f}_{1}^{{m}_{1}},\dots ,{f}_{k}^{{m}_{k}}\right)\text{.}$ This follows from (1.38) and (4.9), since the conditions (1) on the flag $\varphi$ coincide with those of (1.37). (The conditions (1.36), namely

$fi≥m1+…+mi (1≤i≤k)$

ensure that the multi-Schur function does not vanish indentically.)

Let ${H}_{n}$ denote the additive subgroup of ${P}_{n}=ℤ\left[{x}_{1},\dots ,{x}_{n}\right]$ spanned by the monomials ${x}^{\alpha },\alpha \subset {\delta }_{n}=\left(n-1,n-2,\dots ,1,0\right)\text{.}$

(4.11) The Schubert polynomials ${𝔖}_{w},w\in {S}_{n}$ form a $ℤ\text{-basis}$ of ${H}_{n}\text{.}$

 Proof. By (4.3) each ${𝔖}_{w}$ lies in ${H}_{n}\text{.}$ If $∑aw𝔖w=0 (aw∈ℤ)$ is a linear dependence relation, then by homogeneity we have $(1) ∑ℓ(w)=p aw𝔖w=0$ for each $p\ge 0,$ and by operating on (1) with ${\partial }_{w}$ we see that ${a}_{w}=0\text{.}$ Hence the ${𝔖}_{w}$ are linearly independent and hence form a $ℚ\text{-basis}$ of ${H}_{n}\otimes ℚ\text{.}$ It follows that each monomial ${x}^{\alpha },\alpha \subset {\delta }_{n},$ can be expressed in the form $(2) xα=∑ℓ(w)=|α| bw𝔖w$ with rational coefficients ${b}_{w}\text{;}$ by operating on (2) with ${\partial }_{w}$ we have ${b}_{w}={\partial }_{w}{x}^{\alpha },$ and hence the ${b}_{w}$ are integers. $\square$

From (4.11) it follows that

(4.12) The ${𝔖}_{w},w\in {S}_{\infty },$ form a $ℤ\text{-basis}$ of ${P}_{\infty }=ℤ\left[{x}_{1},{x}_{2},\dots \right]\text{.}$

 Proof. Let ${x}^{\alpha }$ be a monomial in ${P}_{\infty }\text{.}$ Then $\alpha \subset {\delta }_{n}$ for sufficiently large $n,$ hence ${x}^{\alpha }$ is a linear combination of the ${𝔖}_{w}\text{.}$ $\square$

For each $n\ge 1,$ let ${S}^{\left(n\right)}$ denote the set of all permutations $w$ such that $w\left(n+1\right) or equivalently such that the code of $w$ has length $\le n\text{.}$

(4.13) The ${𝔖}_{w},w\in {S}^{\left(n\right)},$ form a $ℤ\text{-basis}$ of ${P}_{n}\text{.}$

 Proof. By (4.3)(iii) we have $𝔖w∈Pn ⟺ ∂m𝔖w=0 for all m>n ⟺ w∈S(n).$ Let ${P}_{n}^{\prime }\subset {P}_{n}$ be the $ℤ\text{-span}$ of the ${𝔖}_{w},w\in {S}^{\left(n\right)}\text{.}$ If ${P}_{n}^{\prime }\ne {P}_{n},$ choose $f\in {P}_{n}-{P}_{n}^{\prime }\text{;}$ by (4.12) we can write $f$ as a linear combination of Schubert polynomials, say $(1) f=∑waw𝔖w$ where there is at least one term with ${a}_{w}\ne 0$ and $w\notin {S}^{\left(n\right)}\text{.}$ Hence for some $m>n$ we have ${\partial }_{m}{𝔖}_{w}={𝔖}_{w{s}_{m}},$ and since ${\partial }_{m}f=0$ we obtain from (1) a nontrivial linear dependence relation among the Schubert polynomials, contradicting (4.12). Hence ${P}_{n}^{\prime }={P}_{n},$ which proves (4.13). $\square$

Let $\eta :{P}_{n}\to ℤ$ be the homomorphism defined by $\eta \left({x}_{i}\right)=0$ $\left(1\le i\le n\right)\text{.}$ In other words, $\eta \left(f\right)$ is the constant term of $f,$ for each polynomial $f\in {P}_{n}\text{.}$ The expression of $f$ in terms of Schubert polynomials is then

$(4.14) f=∑w∈S(n) η(∂wf)𝔖w.$

 Proof. By (4.13) and linearity, it is only necessary to verify this formula when $f$ is a Schubert polynomial ${𝔖}_{v},v\in {S}^{\left(n\right)},$ and then it follows from (4.2) and (4.3)(ii) that $\eta \left({\partial }_{w}{𝔖}_{v}\right)$ is equal to $1$ when $w=v$ and is zero otherwise. $\square$

(4.15) Let $f=\sum {\alpha }_{i}{x}_{i}$ be a homogeneous linear polynomial, and let $w$ be a permutation. Then

$f𝔖w=∑ (αi-αj) 𝔖wtij,$

where ${t}_{ij}$ is the transposition that interchanges $i$ and $j,$ and the sum is over all pairs $i such that $\ell \left(w{t}_{ij}\right)=\ell \left(w\right)+1\text{.}$

 Proof. The polynomial $f{𝔖}_{w}$ is homogeneous of degree $\ell \left(w\right)+1,$ and hence by (4.14) we have $f𝔖w=∑v∂v (f𝔖w)·𝔖v$ summed over $v$ of length $\ell \left(w\right)+1\text{.}$ Now by (2.13) $∂v(f𝔖w)=v(f) ∂v𝔖w+∑ (αi-αj) ∂vtij𝔖w$ summed over $i such that $\ell \left(v{t}_{ij}\right)=\ell \left(v\right)-1=\ell \left(w\right)\text{.}$ It follows that ${\partial }_{v}\left(f{𝔖}_{w}\right)={\alpha }_{i}-{\alpha }_{j}$ if $w=v{t}_{ij},$ and is zero otherwise. $\square$

In particular:

$(4.15') xr𝔖w=∑σ(t) 𝔖wt$

summed over transpositions $t={t}_{ir}$ such that $\ell \left(wt\right)=\ell \left(w\right)+1,$ where $\sigma \left(t\right)=-1$ or $+1$ according as $i or $i>r\text{.}$

(4.15'') (Monk's formula) ${𝔖}_{{s}_{r}}{𝔖}_{w}=\sum {𝔖}_{wt}$ summed over transpositions $t={t}_{ij}$ such that $i\le r and $\ell \left(wt\right)=\ell \left(w\right)+1\text{.}$

Remark. As pointed out by A. Lascoux, Monk's formula (4.15'') (which is the counterpart of Pieri's formula in the theory of Schur functions) characterizes the algebra of Schubert polynomials.

We shall apply (4.15') in the following situation. Suppose that $r$ is the last descent of $w,$ so that $w\left(r\right)>w\left(r+1\right)$ and $w\left(r+1\right) Choose the largest $s>r$ such that $w\left(r\right)>w\left(s\right)$ and let $v=w{t}_{rs}\text{.}$ Then from (4.15') applied to $v$ we have

$(1) xr𝔖v=𝔖w- ∑w′𝔖w′$

summed over all permutations $w\prime =v{t}_{qr}$ where $q and $\ell \left(w\prime \right)=\ell \left(v\right)+1=\ell \left(w\right)\text{.}$ Hence $w\prime \left(q\right)=v\left(r\right)>v\left(q\right)=w\left(q\right),$ and $w\prime \left(j\right)=w\left(j\right)$ for $j

Let us arrange the permutations of a given length $p$ in reverse lexicographical ordering, so that if $\ell \left(w\right)=\ell \left(w\prime \right)=p$ then $w\prime$ precedes $w$ if and only if for some $i\ge 1$ we have

$w′(j)=w(j) for jw(i).$

For this ordering there is a first element, namely the permutation $\left(p+1,1,2,\dots ,p\right)\text{.}$

We have proved

(4.16) For each permutation $w\ne 1$ the Schubert polynomial ${𝔖}_{w}$ can be expressed in the form

$𝔖w=xr𝔖v+ ∑w′𝔖w′$

where $r$ is the last descent of $w,$ $\ell \left(v\right)=\ell \left(v\right)-1$ and each $w\prime$ in the sum precedes $w$ in the reverse lexicographical ordering.

From (4.16) we deduce immediately that

(4.17) For each permutation $w,{S}_{w}$ is a polynomial in ${x}_{1},{x}_{2},\dots$ with positive integral coefficients.

 Proof. For we may assume, as inductive hypothesis, that (4.17) is true for all permutations $v$ such that either $\ell \left(v\right)-\ell \left(w\right),$ or $\ell \left(v\right)=\ell \left(w\right)$ and $v$ precedes $w$ in the reverse lexicographical ordering; and then (4.16) shows that the result is true for $w\text{.}$ (The permutation $\left(p+1,1,2,\dots ,p\right)$ has code $\left(p\right),$ hence is dominant with Schubert polynomial ${x}_{1}^{p}$ by (4.7)·) $\square$

Now fix integers $m,n$ such that $1\le m and let $w\in {S}^{\left(n\right)},$ so that ${𝔖}_{w}\in {P}_{n}\text{.}$ By (4.12) we can express ${𝔖}_{w}$ uniquely in the form

$(4.18) 𝔖w(x1,…,xn) =∑u,vduvw 𝔖u (x1,…,xm) 𝔖v (xm+1,…,xn)$

summed over $u\in {S}^{\left(m\right)}$ and $v\in {S}^{\left(n-m\right)}\text{.}$

(4.19) The coefficients ${d}_{uv}^{w}$ in (4.18) are non-negative integers.

 Proof. We proceed by induction on $\ell \left(v\right)\text{.}$ Suppose first that ${d}_{uv}^{w}\ne 0$ and that $\ell \left(v\right)>0,$ so that $v\ne 1\text{.}$ Then there exists $j>m$ such that ${\partial }_{j}{𝔖}_{v}\left({x}_{m+1},\dots ,{x}_{n}\right)\ne 0\text{.}$ From (4.18) we conclude that ${\partial }_{j}{𝔖}_{w}\ne 0,$ hence is equal to ${𝔖}_{w{s}_{j}},$ and therefore we have ${d}_{u,v}^{w}={d}_{u,v{s}_{j-m}}^{w{s}_{j}}$ and $\ell \left(v{s}_{j}\right)=\ell \left(v\right)-1\text{.}$ By the inductive hypothesis, we conclude that ${d}_{uv}^{w}\ge 0$ if $v\ne 1\text{.}$ It remains to consider the case $v=1\text{.}$ Let ${\rho }_{m}:{P}_{n}\to {P}_{m}$ be the homomorphism for which $\rho \left({x}_{i}\right)={x}_{i}$ if $i\le m,$ and $\rho \left({x}_{i}\right)=0$ if $i>m\text{.}$ From (4.18) we have $(2) ρm𝔖w=∑u du,1w𝔖u.$ Let $r$ be the last descent of $w\text{.}$ If $r\le m$ then ${𝔖}_{w}\in {P}_{r}$ and hence ${\rho }_{m}{𝔖}_{w}={𝔖}_{w},$ so that ${d}_{u,1}^{w}$ is equal to $1$ if $u=w,$ and is zero otherwise. If $r>m$ we deduce from (4.16) that $(3) ρm𝔖w=∑w′ ρm𝔖w′.$ Assume that the coefficients ${d}_{u,1}^{w\prime }$ are $\ge 0$ whenever $w\prime$ precedes $w$ in the reverse lexicographical ordering. Then it follows from (2) and (3) that each ${d}_{u,1}^{w}\ge 0\text{.}$ (As remarked before (4.16), the first element in this ordering (if $\ell \left(w\right)=p\text{)}$ is the permutation $\left(p+1,1,2,\dots ,p\right),$ for which the last descent $r$ is equal to $1\text{.)}$ $\square$

### Kohnert's algorithm

Let $D$ be a "diagram", which for present purposes means any finite non empty set of lattice points $\left(i,j\right)$ in the positive quadrant $\left(i\ge 1,j\ge 1\right)\text{.}$ Choose a point $p=\left(i,j\right)\in D$ which is rightmost in its row, and suppose that not all the points $\left(1,j\right),\dots ,\left(i-1,j\right)$ directly above $p$ belong to $D\text{.}$ If $h$ is the largest integer less than $i$ such that $\left(h,j\right)\in D,$ let ${D}_{1}$ denote the diagram obtained from $D$ by replacing $p=\left(i,j\right)$ by $\left(h,j\right)\text{.}$ We can then repeat the process on ${D}_{1},$ by choosing the rightmost element in some row, and obtain a diagram ${D}_{2},$ and so on. Let $K\left(D\right)$ denote the set of all diagrams (including $D$ itself) obtainable from $D$ by a sequence of such moves.

Next, we associate with each diagram $D$ a monomial

$xD=∏i≥1 xiai$

where ${a}_{i}$ is the number of elements of $D$ in the ${i}^{\text{th}}$ row, i.e., the number of $j$ such that $\left(i,j\right)\in D\text{.}$

With this notation established, Kohnert's algorithm states that

(4.20) For each permutation $w$ we have

$𝔖w=∑D∈K(D(w)) xD$

where $D\left(w\right)$ is the diagram (1.20) of $w\text{.}$

Example. If $w=\left(1432\right),$ $K\left(D\left(w\right)\right)$ consists of the diagrams



and ${𝔖}_{w}={x}_{2}^{2}{x}_{3}+{x}_{1}{x}_{2}{x}_{3}+{x}_{1}{x}_{2}^{2}+{x}_{1}^{2}{x}_{3}+{x}_{1}^{2}{x}_{2}\text{.}$

A proof of a related algorithm by N. Bergeron is given in the Appendix to this chapter. The present status of (4.20) is that it is true for $w$ vexillary [Koh1990], but open in general.

### The shift operator

Let $f\in {P}_{n}$ and let $m\ge n\text{.}$ Then

$(4.21) τf=τmf = ∂1…∂m (x1…xmf) = π1…πm(f)$

is independent of $m,$ because ${\pi }_{m}f=f$ if $f$ is symmetrical in ${x}_{m}$ and ${x}_{m+1},$ and in particular if $f$ does not contain ${x}_{m},{x}_{m+1}\text{.}$

The operator $\tau :{P}_{n}\to {P}_{n+1}$ is called the shift operator. For example, we have

$τx1=∂1 (x12)=x1 +x2$

and for $i\ge 2,$

$τxi = ∂1…∂i (x1…xi-1xi2) = ∂1…∂i-1 (x1…xi-1(xi+xi+1)) = xi+1∂1… ∂i-1 (x1…xi-1) = xi+1$

so that by (4.4)

$τ𝔖si=τ (x1+…+xi)= x1+…+xi+1= 𝔖si+1.$

More generally,

(4.22) For all permutations $w,$

$τ𝔖w=𝔖1×w$

where $1×w$ is the permutation $\left(1,w\left(1\right)+1,w\left(2\right)+1,\dots \right)\text{.}$

 Proof. For each $r\ge 1$ let ${w}_{0}^{\left(r\right)}$ be the longest element of ${S}_{r},$ and let ${\delta }_{r}=\left(r-1,r-2,\dots ,1\right)\text{.}$ Then if $w\in {S}_{n}$ we have $τ𝔖w = ∂1…∂n ( x1…xn ∂w-1w0(n) xδn ) = ∂1…∂n ∂w-1w0(n) (xδn+1).$ Now ${s}_{1}\dots {s}_{n}$ is the cycle $1\to 2\to \dots \to n+1\to 1,$ and hence $s1…snw-1 w0(n)= (1×w)-1 w0(n+1)$ so that $ℓ(s1…snw-1w0(n)) =ℓ(s1…sn)+ℓ (w-1w0(n))$ and therefore by (2.7) we have $τ𝔖w=∂ (1×w)-1 w0(n+1) (xδn+1)= 𝔖1×w.$ $\square$

(4.23) Let $\alpha \in {ℕ}^{n}$ and $0\le {p}_{1}\le \dots \le {p}_{n}\text{.}$ Then

$τsα(Xp1,…,Xpn) =sα ( Xp1+1,…, Xpn+1 ) .$

 Proof. Since $\tau ={\pi }_{1}{\pi }_{2}\dots {\pi }_{{p}_{n}},$ this follows from (3.10). $\square$

(4.24) We have

$∂iτr=0$

for $1\le i\le r\text{.}$

 Proof. By (4.12) it is enough to show that ${\partial }_{i}{\tau }^{r}{𝔖}_{w}=0$ for all permutations $w,$ and this follows from (4.22) and (4.2). $\square$

For each $n\ge 1$ let ${\rho }_{n}:{P}_{\infty }↦{P}_{m}$ be the homomorphism defined by

$ρn(xi)= { xi if i≤n, 0 if i>n.$

(4.25) Let ${w}_{0}^{\left(n\right)}$ be the longest element of ${S}_{n}\text{.}$ Then

$πw0(n)(f) =ρnτn(f)$

for all $f\in {P}_{n}\text{.}$

 Proof. By linearity we may assume that $f={x}^{\alpha }$ where $\alpha \in {ℕ}^{n}\text{.}$ Since ${x}^{\alpha }={s}_{\alpha }\left({X}_{1},\dots ,{X}_{n}\right)$ by (3.5'), we have $τn(xα)=sα ( Xn+1,…, X2n )$ by (4.23), and hence $ρnτn(xα)= sα(Xn,…,Xn)$ which is equal to ${\pi }_{{w}_{0}^{\left(n\right)}}\left({x}^{\alpha }\right)$ by (2.16')· $\square$

### Transitions

A transition is an equation of the form

$T(w,r) 𝔖w=xr𝔖u+ ∑v∈Φ𝔖v$

where $r\ge 1,$ $w$ and $u$ are permutations and $\Phi$ is a set of permutations. It exists only for certain values of $r,$ depending on $w\text{.}$ An example is (4.16), in which $r$ is the last descent of $w\text{.}$

By (4.15') we have

$xr𝔖u=∑t σ(t)𝔖ut$

summed over transpositions $t={t}_{ir}$ such that $\ell \left(ut\right)=\ell \left(u\right)+1,$ where $\sigma \left(t\right)$ is the sign of $i-r\text{.}$ So for $T\left(w,r\right)$ to hold there must be exactly one $j>r$ such that

$(1) ℓ(utrj) = ℓ(u)+1, (2) w = utrj.$

Consider the graphs $G\left(w\right)$ and $G\left(u\right)$ of $w$ and $u\text{.}$ They differ only in rows $r$ and $j\text{:}$

$A B C D r j A B C D r j G(w) G(u)$

By (1.10) the relation (1) above is equivalent to $A\cap G\left(u\right)=\varnothing ,$ where $A$ is the open region indicated in the diagram. Moreover, $j$ is the only integer $>r$ such that $u\left(j\right)>u\left(r\right)$ and $A\cap G\left(u\right)=\varnothing ,$ and this will be the case if and only if $\left(A\cup B\cup C\right)\cap G\left(u\right)$ is empty. Since $\left(A\cup B\cup C\right)\cap G\left(u\right)=\left(A\cup B\cup C\right)\cap G\left(w\right),$ it follows that

(4.26) There is a transition $T\left(w,r\right)$ if and only if

$(A∪B∪C)∩G(w) =∅.$

From (4.26) it follows that if $T\left(w,r\right)$ exists we must have $w\left(r\right)>w\left(r+1\right),$ i.e., $r$ must be a descent of $w\text{.}$ Hence

$d0(w)≤r≤d1 (w)$

where ${d}_{0}\left(w\right)$ (resp. ${d}_{1}\left(w\right)\text{)}$ is the first (resp. last) descent of $w\text{.}$ (In terms of the code $c\left(w\right),{d}_{0}\left(w\right)$ is the first descent of the sequence $c\left(w\right),$ and ${d}_{1}\left(w\right)$ is the largest $i$ such that ${c}_{i}\left(w\right)\ne 0\text{.)}$ In general, not all descents of $w$ will give rise to transitions, but the last descent always does, by (4.16).

Consider next the set $\Phi =\Phi \left(w,r\right)$ of permutations that feature in $T\left(w,r\right)\text{.}$ Each $v\in \Phi$ is of the form $v=u{t}_{ir}$ with $i and $\ell \left(v\right)=\ell \left(u\right)+1$ $\text{(}=\ell \left(w\right)\text{).}$ Again by (1.10), this means that

$A′ B′ C′ D′ i r j i r j i r j G(w) G(u) G(v)$

$A\prime \cap G\left(w\right)$ is empty, where $A\prime$ is the open region indicated in the diagram above.

The element $v=u{t}_{ir}$ of $\Phi$ for which $i$ is maximal is called the leader of $\Phi \text{.}$ Thus $v\in \Phi$ is the leader if and only if

$(4.27) (A′∪B′)∩ G(w)=∅.$

Remark (4.28). The set $\Phi$ will be empty if and only if there is no $i such that $w\left(i\right) We can always avoid this possibility by replacing $w$ by $1×w\text{.}$ If $\Phi \left(w,r\right)$ is not empty, then $v↦1×v$ is a bijection of $\Phi \left(w,r\right)$ onto $\Phi \left(1×w,r+1\right)\text{.}$

The condition (4.26) is stable under reflection in the main diagonal, which interchanges $G\left(w\right)$ and $G\left({w}^{-1}\right)\text{.}$ Hence

(4.29) The transition $T\left(w,r\right)$ exists if and only if $T\left({w}^{-1},s\right)$ exists, where $s=w\left(j\right)\text{.}$ Moreover we have

$Φ(w-1,s)= Φ(w,r)-1$

so that $T\left({w}^{-1},s\right)$ is the relation

$𝔖w-1=xs 𝔖u-1+ ∑v∈Φ𝔖v-1.$

We may notice directly one corollary of (4.29). Let

$𝔖w(1)=𝔖w (1,1,…)$

be the number of monomials in ${𝔖}_{w},$ each counted with its multiplicity. (By (4.17), ${𝔖}_{w}$ is a positive sum of monomials.) If $T\left(w,r\right)$ is a transition, we have

$𝔖w(1)= 𝔖u(1)+ ∑v∈Φ 𝔖v(1)$

and also, by (4.29)

$𝔖w-1(1)= 𝔖u-1(1)+ ∑v∈Φ𝔖v-1 (1).$

From these two relations it follows, by induction on $\ell \left(w\right)$ and on the integer ${𝔖}_{w}\left(1\right),$ that

$(4.30) 𝔖w(1)= 𝔖w-1(1)$

or in other words that ${𝔖}_{w}$ and ${𝔖}_{{w}^{-1}}$ each contain the same number of monomials. So if Kohnert's algorithm (4.20) is true, we should have

$Card K(D(w))= Card K(D(w-1)) .$

Doubtless the combinatorialists will seek a "bijective" proof of this fact.

Let $T\left(w,r\right)$ be a transition and let $v\in \Phi \left(w,r\right)\text{.}$ Consider again the graphs of $w$ and $v\text{:}$

$0 M 0 0 P N 0 i r j i r j G(w) G(v)$

Let $m,n,p$ denote respectively the number of points of $G\left(w\right)$ (or equivalently $G\left(v\right)\text{)}$ in the open regions of $M,N,P\text{.}$ (The regions marked with a zero contain no graph points.) Then we have

$(4.31) ci(w)=m+n, cr(w)=n+p+ 1, ci(v)=m+n+ p+1, cr(v)=n,$

and ${c}_{k}\left(v\right)={c}_{k}\left(w\right)$ if $k\ne i,r\text{.}$ In particular, ${c}_{r}\left(w\right)>{c}_{r}\left(v\right)$ for all $v\in \Phi \left(w,r\right)\text{.}$

 Proof. ${c}_{i}\left(w\right)$ is the number of positive integers $k>i$ such that $w\left(k\right) hence is equal to $m+n\text{.}$ Similarly for the other assertions. $\square$

Suppose first that $m=0,$ i.e (by (4.27)) that $v$ is the leader of $\Phi \text{.}$ Then from (4.31) we have ${c}_{i}\left(w\right)={c}_{r}\left(v\right)$ and ${c}_{r}\left(w\right)={c}_{i}\left(v\right)\text{.}$ Hence in this case $c\left(v\right)={t}_{ir}c\left(w\right)$ and therefore $\lambda \left(v\right)=\lambda \left(w\right)\text{.}$

If on the other hand $m>0,$ there are two possibilities:

either

$ci(v)> ci(w)≥ cr(w)> cr(v),$

or

$ci(v)> cr(w)> ci(w)> cr(v).$

In both cases it follows that $\lambda \left(v\right)$ is of the form ${R}^{a}\lambda \left(w\right),$ where $R$ is a raising operator and $a\ge 1\text{.}$ Hence $\lambda \left(v\right)>\lambda \left(w\right)$ (for the dominance partial ordering on partitions), and we have proved

(4.32) If $T\left(w,r\right)$ is a transition, we have $\lambda \left(v\right)\ge \lambda \left(w\right)$ for all $v\in \Phi \left(w,r\right),$ with equality if and only if $v$ is the leader of $\Phi \text{.}$

Recall (1.26) that for any permutation $w$ we have

$λ(w)′≥ λ(w-1).$

Hence for $v\in \Phi \left(w,r\right)$ we have

$(4.33) λ(w)′ ≥(*) λ(v)′ ≥λ(v-1) ≥(*)λ (w-1)$

by (4.29) and (4.32). Moreover, at least one of the inequalities $\left(*\right)$ is strict unless $v$ is the leader of $\Phi \left(w,r\right)$ and ${v}^{-1}$ is the leader $\Phi \left({w}^{-1},s\right)$ (in the notation of (4.29)). In the notation of the diagram preceding (4.27) this means that

$(A′∪B′∪C′) ∩G(w)=∅$

and hence, as in the proof of (4.26), that $\text{Card} \Phi \le 1\text{.}$

(4.34) If $T\left(w,r\right)$ is a transition with $w$ vexillary, then $\Phi \left(w,r\right)$ is either empty or consists of one vexillary permutation.

 Proof. Suppose that $\Phi$ is not empty, and let $v\in \Phi \text{.}$ By (1.27) we have $\lambda \left(w\right)\prime =\lambda \left({w}^{-1}\right),$ and hence all the inequalities in (4.33) are equalities. Thus $v$ is vexillary, and by the remarks above it is the only member of $\Phi \text{.}$ $\square$

(4.35) Let $T\left(w,r\right)$ be a transition with $r>{d}_{0}\left(w\right)\text{.}$ Then

$d0(v)≥ d0(w)$

for all $v\in \Phi \left(w,r\right)\text{.}$

Proof.

As before, let $v=u{t}_{ir}$ with $i and let ${d}_{0}\left(w\right)=d\text{.}$ We have to show that

$(*) c1(v)≤…≤ cd(v).$

We distinguish three cases:

 (a) $i>d,$ so that $d\le i-1$ and therefore ${c}_{k}\left(v\right)={c}_{k}\left(w\right)$ for $1\le k\le d\text{.}$ (b) $i=d\text{.}$ In this case we have ${c}_{k}\left(v\right)={c}_{k}\left(w\right)$ for $1\le k\le d-1,$ and $cd-1(v)= cd-1(w)≤ cd(w)< cd(v)$ by (4.31), so that ${c}_{d-1}\left(v\right)<{c}_{d}\left(v\right)\text{.}$ (c) $i>d\text{.}$ Since $d we have $i+1 and ${c}_{i}\left(w\right)\le {c}_{i+1}\left(w\right),$ hence $w\left(i+1\right)>w\left(i\right)\text{.}$ The diagram on p. 58 shows that $w\left(i+1\right)>w\left(j\right),$ or equivalently $v\left(i+1\right)>v\left(i\right),$ so that ${c}_{i}\left(v\right)\le {c}_{i+1}\left(v\right)\text{.}$ Hence $ci-1(v)= ci-1(w)≤ ci(w)< ci(v)≤ ci+1(v)$ and therefore $ci-1(v)< ci(v)≤ ci+1(v).$ Since the sequences $\left({c}_{1}\left(v\right),\dots ,{c}_{d}\left(v\right)\right)$ and $\left({c}_{1}\left(w\right),\dots ,{c}_{d}\left(w\right)\right)$ differ only in the $i\text{th}$ place, we have ${c}_{1}\left(v\right)\le \dots \le {c}_{d}\left(v\right)$ as required.

$\square$

The maximal transition for $w$ is $T\left(w,{d}_{1}\left(w\right)\right)\text{.}$ Let us temporarily write $w\to v$ to mean that $v\in \Phi \left(w,{d}_{1}\left(w\right)\right)\text{.}$

(4.36) Suppose that

$w=w0→w1→…→ wp$

is a chain of maximal transitions in which none of the ${w}_{i}$ is Grassmannian. Then

$p< (d1(w)-d0(w)) ℓ(w).$

 Proof. For any permutation $v,$ let $e\left(v\right)={d}_{1}\left(v\right)-{d}_{0}\left(v\right)\ge 0\text{.}$ Also let $f\left(v\right)$ denote the last nonzero term in the sequence $c\left(v\right),$ i.e. $f\left(v\right)={c}_{{d}_{1}\left(v\right)}\left(v\right)\text{.}$ Recall that $v$ is Grassmannian if and only if it has only one descent, that is to say if and only if $e\left(v\right)=0\text{.}$ From (4.35) we have $d0(wk)≥ d0(wk-1)$ for $1\le k\le p,$ and from (4.31) we have $(1) cr(wk)< cr(wk-1)$ where $r={d}_{1}\left({w}_{k-1}\right)\text{.}$ Hence ${d}_{1}\left({w}_{k}\right)\le {d}_{1}\left({w}_{k-1}\right)$ and therefore $e(wk)≤e (wk-1).$ Moreover, if $e\left({w}_{k}\right)=e\left({w}_{k-1}\right)$ we must have ${d}_{1}\left({w}_{k}\right)={d}_{1}\left({w}_{k-1}\right)$ and hence by (1) $f(wk) It follows that the $p+1$ points $\left({x}_{k},{y}_{k}\right)=\left(e\left({w}_{k}\right),f\left({w}_{k}\right)\right)$ are all distinct. Since they all satisfy $1\le {w}_{k}\le e\left(w\right)$ and $1\le {y}_{k}\le \ell \left(w\right),$ we have $p+1\le e\left(w\right)\ell \left(w\right),$ as required. $\square$

### The rooted tree of a permutation

In what follows we shall when necessary replace a permutation $w$ by $1×w,$ in order to ensure that at each stage the set $\Phi \left(w,r\right)$ is not empty (4.28). Observe that this replacement does not change the bound $\left({d}_{1}\left(w\right)-{d}_{0}\left(w\right)\right)\ell \left(w\right)$ in (4.36).

The rooted tree ${T}_{w}$ of a permutation $w$ defined as follows:

 (i) if $w$ is vexillary, then ${T}_{w}=\left\{w\right\}\text{;}$ (ii) if $w$ is not vexillary, take the maximal transition for $w\text{:}$ $(*) 𝔖w=xr𝔖u+ ∑v∈Φ 𝔖v$

where $r={d}_{1}\left(w\right)\text{.}$ (If $\Phi$ is empty, replace $w$ by $1×w$ as explained above.) To obtain ${T}_{w},$ join $w$ by an edge to each $v\in \Phi ,$ and attach to each $v\in \Phi$ its tree ${T}_{v}\text{.}$

By (4.36), ${T}_{w}$ is a finite tree, and by construction all its endpoints are vexillary permutations of length $\ell \left(w\right)\text{.}$ It follows from (4.28) that $v↦1×v$ is a bijection of ${T}_{w}$ onto ${T}_{1×w}\text{.}$ Thus ${T}_{w}$ depends (up to isomorphism) only on the diagonal equivalence class (Chapter I) of the permutation $w\text{.}$

Recall that ${\rho }_{m}:{P}_{\infty }\to {P}_{m}$ is the homomorphism defined by ${\rho }_{m}\left({x}_{i}\right)={x}_{i}$ if $1\le i\le m,$ and ${\rho }_{m}\left({x}_{i}\right)=0$ if $i>m\text{.}$

(4.37) Let $V$ be the set of endpoints of ${T}_{w}\text{.}$ Then if $m\le {d}_{0}\left(w\right)$ we have

$ρm(𝔖w)= ∑v∈Vsλ(v) (Xm).$

 Proof. If $w$ is vexillary we have ${\rho }_{m}\left({𝔖}_{w}\right)={s}_{\lambda \left(w\right)}\left({X}_{m}\right)$ by (4.4), since ${\varphi }_{1}\left(w\right)={d}_{0}\left(w\right)\ge m\text{.}$ If $w$ is not vexillary, it follows from the maximal transition $\left(*\right)$ above that $ρm(𝔖w)= ∑v∈Φ ρm(𝔖v)$ since $r={d}_{1}\left(w\right)>{d}_{0}\left(w\right)\ge m\text{.}$ The result now follows by induction on $\text{Card}\left({T}_{w}\right)\text{.}$ $\square$

### Multiplication of Schur functions

Let $\mu ,\nu$ be partitions and let $u\in {S}_{n},$ $u\prime \in {S}_{p}$ be Grassmannian permutations of shapes $\mu ,\nu$ respectively. Let $w=u×u\prime \in {S}_{n+p},$ so that by (4.6) and (4.8)

$𝔖w = 𝔖u· 𝔖1n×u′ = sμ(Xr)sν (Xs)$

where $r={d}_{0}\left(u\right)$ and $s=n+{d}_{0}\left(u\prime \right)\text{.}$ Hence if $m\le r$ we have

$ρm(𝔖w)= sμ(Xm) sν(Xm)$

and so by (4.37)

$sμ(Xm) sν(Xm)= ∑v∈V sλ(v) (Xm)$

where $V$ is the set of endpoints of the tree ${T}_{w}\text{.}$ Here the integer $m$ can be arbitrarily large, because we can replace $w$ by ${1}_{k}×w$ for any positive integer $k\text{.}$ Consequently we have

$(4.38) sμsν= ∑v∈V sλ(v)$

where $V$ is the set of endpoints of the tree ${T}_{u×u\prime },$ and $u$ (resp. $u\prime \text{)}$ is Grassmannian of shape $\mu$ (resp. $\nu \text{).}$

The same argument evidently applies to the product of any number of Schur functions. If ${\mu }^{\left(1\right)},\dots ,{\mu }^{\left(k\right)}$ are partitions, let ${u}_{i}\in {S}_{{n}_{i}}$ be a Grassmannian permutation of shape ${\mu }^{\left(i\right)},$ for each $i=1,\dots ,k$ (so that ${n}_{i}\ge \ell \left({\mu }^{\left(i\right)}\right)+\ell \left({\mu }^{\left(i\right)}\prime \right)\text{)}$ and let $w={u}_{1}×\dots ×{u}_{k}\text{.}$ Then

$(4.38') sμ(1)… sμ(k)= ∑v∈V sλ(v)$

where $V$ is the set of endpoints of the tree ${T}_{w}\text{.}$

In particular, suppose that each ${\mu }^{\left(i\right)}$ is one-part partition, say ${\mu }^{\left(i\right)}=\left({\mu }_{i}\right),$ so that the left-hand side of (4.38') becomes ${h}_{{\mu }_{1}}{h}_{{\mu }_{2}}\dots ={h}_{\mu }\text{.}$ Correspondingly, each ${u}_{i}$ is a cycle of length ${\mu }_{i}+1,$ namely ${u}_{i}=\left({\mu }_{i}+1,1,2,\dots ,{\mu }_{i}\right)\text{.}$ Now [Mac1979, Ch.I, §6] the coefficient of a Schur function ${s}_{\lambda }$ in ${h}_{\mu }$ is the Kostka number ${K}_{\lambda \mu }\text{.}$ Hence we have

(4.39) ${K}_{\lambda \mu }$ is the number of endpoints of shape $\lambda$ in the tree of $w={u}_{}×{u}_{2}×\dots \text{.}$

Schubert polynomials for ${S}_{4}$

$\begin{array}{cc}w& {𝔖}_{w}\\ 1234& 1\\ 1243& {x}_{1}+{x}_{2}+{x}_{3}\\ 1324& {x}_{1}+{x}_{2}\\ 1342& {x}_{1}{x}_{2}+{x}_{1}{x}_{3}+{x}_{2}{x}_{3}\\ 1423& {x}_{1}^{2}+{x}_{1}{x}_{2}+{x}_{2}^{2}\\ 1432& {x}_{1}^{2}{x}_{2}+{x}_{1}^{2}{x}_{3}+{x}_{1}{x}_{2}^{2}+{x}_{1}{x}_{2}{x}_{3}+{x}_{2}^{2}{x}_{3}\\ 2134& {x}_{1}\\ 2143& {x}_{1}^{2}+{x}_{1}{x}_{2}+{x}_{1}{x}_{3}\\ 2314& {x}_{1}{x}_{2}\\ 2341& {x}_{1}{x}_{2}{x}_{3}\\ 2413& {x}_{1}^{2}{x}_{2}+{x}_{1}{x}_{2}^{2}\\ 2431& {x}_{1}^{2}{x}_{2}{x}_{3}+{x}_{1}{x}_{2}^{2}{x}_{3}\\ 3124& {x}_{1}^{2}\\ 3142& {x}_{1}^{2}{x}_{2}+{x}_{1}^{2}{x}_{3}\\ 3214& {x}_{1}^{2}{x}_{2}\\ 3241& {x}_{1}^{2}{x}_{2}{x}_{3}\\ 3412& {x}_{1}^{2}{x}_{2}^{2}\\ 3421& {x}_{1}^{2}{x}_{2}^{2}{x}_{3}\\ 4123& {x}_{1}^{3}\\ 4132& {x}_{1}^{3}{x}_{2}+{x}_{1}^{3}{x}_{3}\\ 4213& {x}_{1}^{3}{x}_{2}\\ 4213& {x}_{1}^{3}{x}_{2}\\ 4231& {x}_{1}^{3}{x}_{2}{x}_{3}\\ 4312& {x}_{1}^{3}{x}_{2}^{2}\\ 4321& {x}_{1}^{3}{x}_{2}^{2}{x}_{3}\end{array}$

## Notes and References

This is a typed excerpt of the book Notes on Schubert Polynomials by I. G. Macdonald.