Notes on Schubert Polynomials
Chapter 4

Arun Ram
Department of Mathematics and Statistics
University of Melbourne
Parkville, VIC 3010 Australia
aram@unimelb.edu.au

Last update: 28 June 2013

Schubert Polynomials (1)

Let δ=δn=(n-1,n-2,,1,0), so that

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

For each permutation wSn the Schubert polynomial 𝔖w is defined to be

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

where as usual w0 is the longest element of Sn.

(4.2) Let v,wSn. Then

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

In particular,

i𝔖w= { 𝔖wsi ifw(i)> w(i+1), 0 ifw(i)< w(i+1).

Proof.

From (2.7) we have

vw-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 v𝔖w=vw-1w0xδ is equal to vw-1w0xδ=𝔖wv-1 if (w)-(v), and is zero otherwise.

(4.3)
(i) 𝔖w0=xδ, 𝔖1=1.
(ii) For each wSn, 𝔖w is a non-zero homogeneous polynomial in x1,,xn-1 of degree (w), of the form 𝔖w=αcα xα summed over αn-1 such that αδ (i.e., αin-i for each i) and |α|=(w).
(iii) 𝔖w is symmetrical in xi,xi+1 if and only if w(i)<w(i+1).
(iv) If r is the last descent of wSn (i.e., if w(r)>w(r+1) and w(r+1)<w(r+2)<<w(n)), then 𝔖wPr=[x1,,xr], and 𝔖wPr-1.

Proof.

(i) That 𝔖w0=xδ is clear from the definition (4.1). Also by (2.11) we have

𝔖1=w0xδ =sδ-δ=1.

(ii) The operator w-1w0 lowers degrees by (w-1w0)=(w0)-(w-1)=12n(n-1)-(w). Hence 𝔖w=w-1w0xδ is homogeneous of degree (w). If now αn-1 is such that αδ, then by (2.1) rxα is a linear combination of monomials xβ such that βi=αi if ir,r+1, and

max(βi,βi+1) max(αi,αi+1) -1n-i-1,

so that βδ. Hence the linear span Hn of the monomials xα,αδ is mapped into itself by each r (1rn-1) and hence by each w, wSn. Hence 𝔖wHn for each wSn.

(iii) 𝔖w is symmetrical in xi and xi+1 if and only if si𝔖w=𝔖w, that is to say if and only if i𝔖w=0, which by (4.2) is equivalent to w(i)<w(i+1).

(iv) 𝔖w is symmetrical in xr+1,,xn by (iii) above, but does not contain xn, hence does not contain any of xr+1,,xn.

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,,n-1 we have

𝔖si=x1+x2 ++xi.

Proof.

By (4.3), 𝔖si is a homogeneous symmetric polynomial of degree (si)=1 in x1,,xi, hence is equal to c(x1++xi) for some integer c. But i𝔖si=𝔖1=1 by (4.2) and (4.3)(i), hence c=1.

(4.5) (Stability) Let m>n and let i:SnSm be the embedding. Then

𝔖w=𝔖i(w)

for all wSn.

Proof.

We may assume that m=n+1. Let w0 be the longest element of Sn+1, then w0=w0snsn-1s1, where w0 is the longest element of Sn, and hence

𝔖i(w) = w-1w0 (x1nx2n-1xn) = w-1w0 nn-1 1 (x1nx2n-1xn) = w-1w0 (x1n-1x2n-2xn-1)

(because 1(x1nx2n-1xn)= x1n-1x2n-1x3n-2xn, hence 21(x1nx2n-1xn)= x1n-1 x2n-2 x3n-2 x4n-3 xn, and so on.)

From (4.5) it follows that 𝔖w is a well-defined polynomial for each permutation wS=nSn.

If uSm and vSn, we denote by u×v the permutation

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

in Sm+n. We have then

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

where 1m is the identity element of Sm.

Proof.

We shall make use of the following fact: if f is a polynomial in x1,x2,, and if=0 for all i1, then f is a constant. For fPn=[x1,,xn] for some n, and is symmetric in x1,,xn+1 because 1f==nf=0.

To prove (4.6) we proceed by induction on (u)+(v). If (u)=(v)=0 then u=1m, v=1n, and both sides of (4.6) are equal to 1. Let

F(u,v)= 𝔖u×v-𝔖u 𝔖1m×v.

By the remark above, it is enough to show that iF(u,v)=0 for each i.

Suppose first that i<m. Then

iF(u,v)=i (𝔖u×v)-i (𝔖u)·𝔖1m×v

because i(𝔖1m×v)=0 by (4.2). Hence we have iF(u,v)=0 if (usi)>(u); and if (usi)<(u) 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 iF(uv)=0 by the inductive hypothesis.

Finally, if i=m we have ((u×v)sm) >(u×v), because

(u×v)(m)= u(m)<m+v(1) =(u×v)(m+1),

and therefore m kills 𝔖u×v and 𝔖1m×v; moreover, m𝔖u=0, because 𝔖u[x1,,xm-1]. Hence mF(u,v)=0, and the proof is complete.

For certain classes of permutations there are explicit formulas for 𝔖w. We consider first the case where w is dominant, of shape λ (so that the diagram of w coincides with the diagram of λ).

(4.7) If w is dominant of shape λ, then

𝔖w=xλ.

Proof.

We use descending induction on (w). where wSn. The result is true for w=w0 by (4.3)(i), since w0 is dominant of shape δ.

Suppose wSn, ww0 and w is dominant of shape λ. Then λδ and λδ. Let r0 be the largest integer such that λi=n-i for 1ir, and let a=λr+1+1n-r-1. Then wsa is dominant of length (w)+1, and λ(wsa)=λ+εa, where εa is the vector whose ath component is 1 and all other components zero. Hence we have

𝔖w=a𝔖wsa =a(xaxλ)= xλ,

because λa=λa+1.

Conversely, every monomial xλ (where λ is a partition) occurs as a Schubert polynomial, namely as 𝔖w where w is the permutation with code c(w)=λ.

Suppose next that w is Grassmannian, with descent at r.

(4.8) If w is Grassmannian of shape λ, then 𝔖w is the Schur function sλ(Xr), where r is the unique descent of w, and Xr=x1++xr.

Proof.

We may assume that w1 (by (4.3)(i), 𝔖1=1). Then r1 and the code of w is

( w(1)-1,w(2)-2, ,w(r)-r )

so that λ=(w(r)-r,,w(2)-2,w(1)-1). Let u=w0(r) be the longest element of Sr. Then

wu= ( w(r),,w(1), w(r+1),w(r+2) )

is dominant of shape λ+δr, where δr=(r-1,r-2,,1,0), and (wu)=(w)+(u). Hence

𝔖w=u𝔖wu= u(xλ+δr) =sλ(Xr)

by (4.2), (4.7) and (2.11).

Conversely, every Schur function sλ(Xr) (where λ is a partition of length r) occurs as a Schubert polynomial, namely as 𝔖w where w is the permutation with code c(w)=(λr,λr-1,,λ1),

More generally, let w be vexillary with shape λ=(λ1,,λm) (where m=(λ)) and flag ϕ=(ϕ1,,ϕm) (Chapter I). Then 𝔖w is a multi-Schur function (Chapter III), namely

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

where Xi=x1++xi for each i1.

Proof.

The idea is to convert w systematically into a dominant permutation. Recall ((1.23), (1.24)) that if c(w)=(c1,c2,) and cici+1 for some i1, then (wsi)=(w)+1 and

(*) c(wsi)= ( c1,,ci-1, ci+1+1,ci, ci+2,ci+3 , ) .

As in Chapter I let

λ(w)= ( p1m1,, pkmk )

where p1>>pk>0 (and each mi1), and let

ϕ(w)= ( f1m1,, fkmk )

where f1fk.

Consider first the terms equal to p1 in the sequence c(w). They occupy the positions f1-m1+1,,f1. We shall use (*) to move them all to the left until they occupy the first m1 positions, by multiplying w on the right by

u1= (sf1-m1s2s1) (sf1-m1+1s3s2) (sf1-1sm1+1sm1) .

Let w1=wu1. In the code of w1, the first m1 entries will be equal to p1+f1-m1; the shape of w1 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 p2 in the sequence c(w1) will occupy the positions f2-m2+1,,f2. The next step is to move those to the left until they occupy the positions m1+1,,m1+m2 by multiplying w1 on the right by

u2= (sf2-m2sm1+2sm1+1) (sf2-m2+1sm1+2) (sf2-1sm1+m2).

Let w2=w1u2; the code of w2 starts off with m1 entries to p1+f1-m1, then m2 entries equal to p2+f2-m1-m2; the shape of w2 is

λ(2)=λ(w2)= ( (p1+f1-m1)m1, (p1+f2-m1-m2)m2, p3m3,,pkmk ) ,

and the terms equal to p3 in the sequence c(w2) will occupy the positions f3-m3+1,,f3-m3.

We continue in this way; at the rth stage we define wr=wr-1ur, where

ur= ( sfr-mr sm1++mr-1+1 ) ( sfr-1 sm1++mr ) ,

and wr has shape

λ(r)=λ(wr)= ( (p1+a1)m1 ,, (pr+ar)mr ,pr+1mr+1 ,,pkmk )

where ai=fi-(m1++mi)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 wk=wu1uk, 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 (1rk)

so that

(wk)=(w)+ r=1k(ur)

and therefore, since w=wk(u1uk)-1,

𝔖w=u1 uk𝔖wk

by (4.2). Now by (4.6) and (3.5') we have

𝔖wk=xμ=sμ (X1,,Xm)

where m=m1++mk=(λ). 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 uk-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 ) .

Remarks. 1. As in Chapter I, let

λ= ( q1n1,, qknk )

be the conjugate partition, so that

m1++mi== qk+1-i (1ik)

and therefore

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

by (1.41), where (g1n1,,gknk) is the flag of w-1. Thus

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

2. The result (4.9) admits a converse. If λ=(p1m1,,pkmk) as above, every non-zero multi-Schur function sλ((Xf1)m1,,(Xfk)mk) that satisfies the conditions of the duality theorem (3.8''), namely

(1) 0fi+1-fi mi+1+nk+1-i (1ik-1),

is the Schubert polynomial of a vexillary permutation, namely the permutation with shape λ and flag ϕ=(f1m1,,fkmk). This follows from (1.38) and (4.9), since the conditions (1) on the flag ϕ coincide with those of (1.37). (The conditions (1.36), namely

fim1++mi (1ik)

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

Let Hn denote the additive subgroup of Pn=[x1,,xn] spanned by the monomials xα,αδn=(n-1,n-2,,1,0).

(4.11) The Schubert polynomials 𝔖w,wSn form a -basis of Hn.

Proof.

By (4.3) each 𝔖w lies in Hn. If

aw𝔖w=0 (aw)

is a linear dependence relation, then by homogeneity we have

(1) (w)=p aw𝔖w=0

for each p0, and by operating on (1) with w we see that aw=0. Hence the 𝔖w are linearly independent and hence form a -basis of Hn. It follows that each monomial xα,αδn, can be expressed in the form

(2) xα=(w)=|α| bw𝔖w

with rational coefficients bw; by operating on (2) with w we have bw=wxα, and hence the bw are integers.

From (4.11) it follows that

(4.12) The 𝔖w,wS, form a -basis of P=[x1,x2,].

Proof.

Let xα be a monomial in P. Then αδn for sufficiently large n, hence xα is a linear combination of the 𝔖w.

For each n1, let S(n) denote the set of all permutations w such that w(n+1)<w(n+2)<, or equivalently such that the code of w has length n.

(4.13) The 𝔖w,wS(n), form a -basis of Pn.

Proof.

By (4.3)(iii) we have

𝔖wPn m𝔖w=0 for allm>n wS(n).

Let PnPn be the -span of the 𝔖w,wS(n). If PnPn, choose fPn-Pn; 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 aw0 and wS(n). Hence for some m>n we have m𝔖w=𝔖wsm, and since mf=0 we obtain from (1) a nontrivial linear dependence relation among the Schubert polynomials, contradicting (4.12). Hence Pn=Pn, which proves (4.13).

Let η:Pn be the homomorphism defined by η(xi)=0 (1in). In other words, η(f) is the constant term of f, for each polynomial fPn. The expression of f in terms of Schubert polynomials is then

(4.14) f=wS(n) η(wf)𝔖w.

Proof.

By (4.13) and linearity, it is only necessary to verify this formula when f is a Schubert polynomial 𝔖v,vS(n), and then it follows from (4.2) and (4.3)(ii) that η(w𝔖v) is equal to 1 when w=v and is zero otherwise.

(4.15) Let f=αixi be a homogeneous linear polynomial, and let w be a permutation. Then

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

where tij is the transposition that interchanges i and j, and the sum is over all pairs i<j such that (wtij)=(w)+1.

Proof.

The polynomial f𝔖w is homogeneous of degree (w)+1, and hence by (4.14) we have

f𝔖w=vv (f𝔖w)·𝔖v

summed over v of length (w)+1. Now by (2.13)

v(f𝔖w)=v(f) v𝔖w+ (αi-αj) vtij𝔖w

summed over i<j such that (vtij)=(v)-1=(w). It follows that v(f𝔖w)=αi-αj if w=vtij, and is zero otherwise.

In particular:

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

summed over transpositions t=tir such that (wt)=(w)+1, where σ(t)=-1 or +1 according as i<r or i>r.

(4.15'') (Monk's formula) 𝔖sr𝔖w=𝔖wt summed over transpositions t=tij such that ir<j and (wt)=(w)+1.

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(r)>w(r+1) and w(r+1)<w(r+2). Choose the largest s>r such that w(r)>w(s) and let v=wtrs. Then from (4.15') applied to v we have

(1) xr𝔖v=𝔖w- w𝔖w

summed over all permutations w=vtqr where q<r and (w)=(v)+1=(w). Hence w(q)=v(r)>v(q)=w(q), and w(j)=w(j) for j<q.

Let us arrange the permutations of a given length p in reverse lexicographical ordering, so that if (w)=(w)=p then w precedes w if and only if for some i1 we have

w(j)=w(j) forj<i,and w(i)>w(i).

For this ordering there is a first element, namely the permutation (p+1,1,2,,p).

We have proved

(4.16) For each permutation w1 the Schubert polynomial 𝔖w can be expressed in the form

𝔖w=xr𝔖v+ w𝔖w

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

From (4.16) we deduce immediately that

(4.17) For each permutation w,Sw is a polynomial in x1,x2, with positive integral coefficients.

Proof.

For we may assume, as inductive hypothesis, that (4.17) is true for all permutations v such that either (v)-(w), or (v)=(w) and v precedes w in the reverse lexicographical ordering; and then (4.16) shows that the result is true for w. (The permutation (p+1,1,2,,p) has code (p), hence is dominant with Schubert polynomial x1p by (4.7)·)

Now fix integers m,n such that 1m<n, and let wS(n), so that 𝔖wPn. 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 uS(m) and vS(n-m).

(4.19) The coefficients duvw in (4.18) are non-negative integers.

Proof.

We proceed by induction on (v). Suppose first that duvw0 and that (v)>0, so that v1. Then there exists j>m such that j𝔖v(xm+1,,xn)0. From (4.18) we conclude that j𝔖w0, hence is equal to 𝔖wsj, and therefore we have du,vw=du,vsj-mwsj and (vsj)=(v)-1. By the inductive hypothesis, we conclude that duvw0 if v1.

It remains to consider the case v=1. Let ρm:PnPm be the homomorphism for which ρ(xi)=xi if im, and ρ(xi)=0 if i>m. From (4.18) we have

(2) ρm𝔖w=u du,1w𝔖u.

Let r be the last descent of w. If rm then 𝔖wPr and hence ρm𝔖w=𝔖w, so that du,1w 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 du,1w are 0 whenever w precedes w in the reverse lexicographical ordering. Then it follows from (2) and (3) that each du,1w0. (As remarked before (4.16), the first element in this ordering (if (w)=p) is the permutation (p+1,1,2,,p), for which the last descent r is equal to 1.)

Kohnert's algorithm

Let D be a "diagram", which for present purposes means any finite non empty set of lattice points (i,j) in the positive quadrant (i1,j1). Choose a point p=(i,j)D which is rightmost in its row, and suppose that not all the points (1,j),,(i-1,j) directly above p belong to D. If h is the largest integer less than i such that (h,j)D, let D1 denote the diagram obtained from D by replacing p=(i,j) by (h,j). We can then repeat the process on D1, by choosing the rightmost element in some row, and obtain a diagram D2, and so on. Let K(D) 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=i1 xiai

where ai is the number of elements of D in the ith row, i.e., the number of j such that (i,j)D.

With this notation established, Kohnert's algorithm states that

(4.20) For each permutation w we have

𝔖w=DK(D(w)) xD

where D(w) is the diagram (1.20) of w.

Example. If w=(1432), K(D(w)) consists of the diagrams

and 𝔖w= x22x3+ x1x2x3+ x1x22+ x12x3+ x12x2.

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 fPn and let mn. Then

(4.21) τf=τmf = 1m (x1xmf) = π1πm(f)

is independent of m, because πmf=f if f is symmetrical in xm and xm+1, and in particular if f does not contain xm,xm+1.

The operator τ:PnPn+1 is called the shift operator. For example, we have

τx1=1 (x12)=x1 +x2

and for i2,

τxi = 1i (x1xi-1xi2) = 1i-1 (x1xi-1(xi+xi+1)) = xi+11 i-1 (x1xi-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 (1,w(1)+1,w(2)+1,).

Proof.

For each r1 let w0(r) be the longest element of Sr, and let δr=(r-1,r-2,,1). Then if wSn we have

τ𝔖w = 1n ( x1xn w-1w0(n) xδn ) = 1n w-1w0(n) (xδn+1).

Now s1sn is the cycle 12n+11, and hence

s1snw-1 w0(n)= (1×w)-1 w0(n+1)

so that

(s1snw-1w0(n)) =(s1sn)+ (w-1w0(n))

and therefore by (2.7) we have

τ𝔖w= (1×w)-1 w0(n+1) (xδn+1)= 𝔖1×w.

(4.23) Let αn and 0p1pn. Then

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

Proof.

Since τ=π1π2πpn, this follows from (3.10).

(4.24) We have

iτr=0

for 1ir.

Proof.

By (4.12) it is enough to show that iτr𝔖w=0 for all permutations w, and this follows from (4.22) and (4.2).

For each n1 let ρn:PPm be the homomorphism defined by

ρn(xi)= { xi ifin, 0 ifi>n.

(4.25) Let w0(n) be the longest element of Sn. Then

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

for all fPn.

Proof.

By linearity we may assume that f=xα where αn. Since xα=sα(X1,,Xn) 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 πw0(n)(xα) by (2.16')·

Transitions

A transition is an equation of the form

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

where r1, w and u are permutations and Φ is a set of permutations. It exists only for certain values of r, depending on w. An example is (4.16), in which r is the last descent of w.

By (4.15') we have

xr𝔖u=t σ(t)𝔖ut

summed over transpositions t=tir such that (ut)=(u)+1, where σ(t) is the sign of i-r. So for T(w,r) to hold there must be exactly one j>r such that

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

Consider the graphs G(w) and G(u) of w and u. They differ only in rows r and j:

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 AG(u)=, where A is the open region indicated in the diagram. Moreover, j is the only integer >r such that u(j)>u(r) and AG(u)=, and this will be the case if and only if (ABC)G(u) is empty. Since (ABC)G(u)=(ABC)G(w), it follows that

(4.26) There is a transition T(w,r) if and only if

(ABC)G(w) =.

From (4.26) it follows that if T(w,r) exists we must have w(r)>w(r+1), i.e., r must be a descent of w. Hence

d0(w)rd1 (w)

where d0(w) (resp. d1(w)) is the first (resp. last) descent of w. (In terms of the code c(w),d0(w) is the first descent of the sequence c(w), and d1(w) is the largest i such that ci(w)0.) 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 Φ=Φ(w,r) of permutations that feature in T(w,r). Each vΦ is of the form v=utir with i<r and (v)=(u)+1 (=(w)). 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)

AG(w) is empty, where A is the open region indicated in the diagram above.

The element v=utir of Φ for which i is maximal is called the leader of Φ. Thus vΦ is the leader if and only if

(4.27) (AB) G(w)=.

Remark (4.28). The set Φ will be empty if and only if there is no i<r such that w(i)<w(j). We can always avoid this possibility by replacing w by 1×w. If Φ(w,r) is not empty, then v1×v is a bijection of Φ(w,r) onto Φ(1×w,r+1).

The condition (4.26) is stable under reflection in the main diagonal, which interchanges G(w) and G(w-1). Hence

(4.29) The transition T(w,r) exists if and only if T(w-1,s) exists, where s=w(j). Moreover we have

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

so that T(w-1,s) 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(w,r) 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 (w) and on the integer 𝔖w(1), 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

CardK(D(w))= CardK(D(w-1)) .

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

Let T(w,r) be a transition and let vΦ(w,r). Consider again the graphs of w and v:

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(w) (or equivalently G(v)) in the open regions of M,N,P. (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 ck(v)=ck(w) if ki,r. In particular, cr(w)>cr(v) for all vΦ(w,r).

Proof.

ci(w) is the number of positive integers k>i such that w(k)<w(i), hence is equal to m+n. Similarly for the other assertions.

Suppose first that m=0, i.e (by (4.27)) that v is the leader of Φ. Then from (4.31) we have ci(w)=cr(v) and cr(w)=ci(v). Hence in this case c(v)=tirc(w) and therefore λ(v)=λ(w).

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 λ(v) is of the form Raλ(w), where R is a raising operator and a1. Hence λ(v)>λ(w) (for the dominance partial ordering on partitions), and we have proved

(4.32) If T(w,r) is a transition, we have λ(v)λ(w) for all vΦ(w,r), with equality if and only if v is the leader of Φ.

Recall (1.26) that for any permutation w we have

λ(w) λ(w-1).

Hence for vΦ(w,r) we have

(4.33) λ(w) (*) λ(v) λ(v-1) (*)λ (w-1)

by (4.29) and (4.32). Moreover, at least one of the inequalities (*) is strict unless v is the leader of Φ(w,r) and v-1 is the leader Φ(w-1,s) (in the notation of (4.29)). In the notation of the diagram preceding (4.27) this means that

(ABC) G(w)=

and hence, as in the proof of (4.26), that CardΦ1.

(4.34) If T(w,r) is a transition with w vexillary, then Φ(w,r) is either empty or consists of one vexillary permutation.

Proof.

Suppose that Φ is not empty, and let vΦ. By (1.27) we have λ(w)=λ(w-1), 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 Φ.

(4.35) Let T(w,r) be a transition with r>d0(w). Then

d0(v) d0(w)

for all vΦ(w,r).

Proof.

As before, let v=utir with i<r, and let d0(w)=d. We have to show that

(*) c1(v) cd(v).

We distinguish three cases:

(a) i>d, so that di-1 and therefore ck(v)=ck(w) for 1kd.
(b) i=d. In this case we have ck(v)=ck(w) for 1kd-1, and cd-1(v)= cd-1(w) cd(w)< cd(v) by (4.31), so that cd-1(v)<cd(v).
(c) i>d. Since d<r we have i+1<r and ci(w)ci+1(w), hence w(i+1)>w(i). The diagram on p. 58 shows that w(i+1)>w(j), or equivalently v(i+1)>v(i), so that ci(v)ci+1(v). 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 (c1(v),,cd(v)) and (c1(w),,cd(w)) differ only in the ith place, we have c1(v)cd(v) as required.

The maximal transition for w is T(w,d1(w)). Let us temporarily write wv to mean that vΦ(w,d1(w)).

(4.36) Suppose that

w=w0w1 wp

is a chain of maximal transitions in which none of the wi is Grassmannian. Then

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

Proof.

For any permutation v, let e(v)=d1(v)-d0(v)0. Also let f(v) denote the last nonzero term in the sequence c(v), i.e. f(v)=cd1(v)(v). Recall that v is Grassmannian if and only if it has only one descent, that is to say if and only if e(v)=0.

From (4.35) we have

d0(wk) d0(wk-1)

for 1kp, and from (4.31) we have

(1) cr(wk)< cr(wk-1)

where r=d1(wk-1). Hence d1(wk)d1(wk-1) and therefore

e(wk)e (wk-1).

Moreover, if e(wk)=e(wk-1) we must have d1(wk)=d1(wk-1) and hence by (1)

f(wk)<f(wk-1) .

It follows that the p+1 points (xk,yk)=(e(wk),f(wk)) are all distinct. Since they all satisfy 1wke(w) and 1yk(w), we have p+1e(w)(w), as required.

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 Φ(w,r) is not empty (4.28). Observe that this replacement does not change the bound (d1(w)-d0(w))(w) in (4.36).

The rooted tree Tw of a permutation w defined as follows:

(i) if w is vexillary, then Tw={w};
(ii) if w is not vexillary, take the maximal transition for w: (*) 𝔖w=xr𝔖u+ vΦ 𝔖v

where r=d1(w). (If Φ is empty, replace w by 1×w as explained above.) To obtain Tw, join w by an edge to each vΦ, and attach to each vΦ its tree Tv.

By (4.36), Tw is a finite tree, and by construction all its endpoints are vexillary permutations of length (w). It follows from (4.28) that v1×v is a bijection of Tw onto T1×w. Thus Tw depends (up to isomorphism) only on the diagonal equivalence class (Chapter I) of the permutation w.

Recall that ρm:PPm is the homomorphism defined by ρm(xi)=xi if 1im, and ρm(xi)=0 if i>m.

(4.37) Let V be the set of endpoints of Tw. Then if md0(w) we have

ρm(𝔖w)= vVsλ(v) (Xm).

Proof.

If w is vexillary we have ρm(𝔖w)=sλ(w)(Xm) by (4.4), since ϕ1(w)=d0(w)m. If w is not vexillary, it follows from the maximal transition (*) above that

ρm(𝔖w)= vΦ ρm(𝔖v)

since r=d1(w)>d0(w)m. The result now follows by induction on Card(Tw).

Multiplication of Schur functions

Let μ,ν be partitions and let uSn, uSp be Grassmannian permutations of shapes μ,ν respectively. Let w=u×uSn+p, so that by (4.6) and (4.8)

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

where r=d0(u) and s=n+d0(u). Hence if mr we have

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

and so by (4.37)

sμ(Xm) sν(Xm)= vV sλ(v) (Xm)

where V is the set of endpoints of the tree Tw. Here the integer m can be arbitrarily large, because we can replace w by 1k×w for any positive integer k. Consequently we have

(4.38) sμsν= vV sλ(v)

where V is the set of endpoints of the tree Tu×u, and u (resp. u) is Grassmannian of shape μ (resp. ν).

The same argument evidently applies to the product of any number of Schur functions. If μ(1),,μ(k) are partitions, let uiSni be a Grassmannian permutation of shape μ(i), for each i=1,,k (so that ni(μ(i))+(μ(i))) and let w=u1××uk. Then

(4.38') sμ(1) sμ(k)= vV sλ(v)

where V is the set of endpoints of the tree Tw.

In particular, suppose that each μ(i) is one-part partition, say μ(i)=(μi), so that the left-hand side of (4.38') becomes hμ1hμ2=hμ. Correspondingly, each ui is a cycle of length μi+1, namely ui=(μi+1,1,2,,μi). Now [Mac1979, Ch.I, §6] the coefficient of a Schur function sλ in hμ is the Kostka number Kλμ. Hence we have

(4.39) Kλμ is the number of endpoints of shape λ in the tree of w=u1×u2×.

Schubert polynomials for S4

w 𝔖w 1234 1 1243 x1+x2+x3 1324 x1+x2 1342 x1x2+ x1x3+ x2x3 1423 x12+ x1x2+ x22 1432 x12x2+ x12x3+ x1x22+ x1x2x3+ x22x3 2134 x1 2143 x12+ x1x2+ x1x3 2314 x1x2 2341 x1x2x3 2413 x12x2+ x1x22 2431 x12x2x3+ x1x22x3 3124 x12 3142 x12x2+ x12x3 3214 x12x2 3241 x12x2x3 3412 x12x22 3421 x12x22x3 4123 x13 4132 x13x2+ x13x3 4213 x13x2 4213 x13x2 4231 x13x2x3 4312 x13x22 4321 x13x22x3

Notes and References

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

page history