Chapter 4: Schubert Polynomials (1) - Notes on Schubert Polynomials

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, \dots, 1, 0),$ so that

x^{δ} = x_{1}^{n - 1} x_{2}^{n - 2} \dots x_{n - 1} .

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

\begin{matrix} (4.1) & 𝔖_{w} = \partial_{w^{- 1} w_{0}} (x^{δ}) \end{matrix}

where as usual $w_{0}$ is the longest element of $S_{n} .$

(4.2) Let $v, w \in S_{n} .$ Then

\partial_{v} 𝔖_{w} = {\begin{matrix} 𝔖_{w v^{- 1}} & if ℓ (w v^{- 1}) = ℓ (w) - ℓ (v), \\ 0 & otherwise. \end{matrix}

In particular,

\partial_{i} 𝔖_{w} = {\begin{matrix} 𝔖_{w s_{i}} & if w (i) > w (i + 1), \\ 0 & if w (i) < w (i + 1) . \end{matrix}

Proof.

From (2.7) we have

\partial_{v} \partial_{w^{- 1} w_{0}} = {\begin{matrix} \partial_{v w^{- 1} w_{0}} & if ℓ (v) + ℓ (w^{- 1} w_{0}) = ℓ (v w^{- 1} w_{0}), \\ 0 & otherwise. \end{matrix}

Now

ℓ (v) + ℓ (w^{- 1} w_{0}) = ℓ (v) + ℓ (w_{0}) - ℓ (w)

and

ℓ (v w^{- 1} w_{0}) = ℓ (w_{0}) - ℓ (w v^{- 1})

by (1.6). Hence $\partial_{v} 𝔖_{w} = \partial_{v} \partial_{w^{- 1} w_{0}} x^{δ}$ is equal to $\partial_{v w^{- 1} w_{0}} x^{δ} = 𝔖_{w v^{- 1}}$ if $ℓ (w) - ℓ (v),$ and is zero otherwise.

$□$

(4.3)

(i)	$𝔖_{w_{0}} = x^{δ}, 𝔖_{1} = 1 .$
(ii)	For each $w \in S_{n},$ $𝔖_{w}$ is a non-zero homogeneous polynomial in $x_{1}, \dots, x_{n - 1}$ of degree $ℓ (w),$ of the form $𝔖_{w} = \sum_{α} c_{α} x^{α}$ summed over $α \in ℕ^{n - 1}$ such that $α \subset δ$ (i.e., $α_{i} \leq n - i$ for each $i)$ and $\| α \| = ℓ (w) .$
(iii)	$𝔖_{w}$ is symmetrical in $x_{i}, x_{i + 1}$ if and only if $w (i) < w (i + 1) .$
(iv)	If $r$ is the last descent of $w \in S_{n}$ (i.e., if $w (r) > w (r + 1)$ and $w (r + 1) < w (r + 2) < \dots < w (n)),$ then $𝔖_{w} \in P_{r} = ℤ [x_{1}, \dots, x_{r}],$ and $𝔖_{w} \notin P_{r - 1} .$

Proof.

(i) That $𝔖_{w_{0}} = x^{δ}$ is clear from the definition (4.1). Also by (2.11) we have

𝔖_{1} = \partial_{w_{0}} x^{δ} = s_{δ - δ} = 1 .

(ii) The operator $\partial_{w^{- 1} w_{0}}$ lowers degrees by $ℓ (w^{- 1} w_{0}) = ℓ (w_{0}) - ℓ (w^{- 1}) = \frac{1}{2} n (n - 1) - ℓ (w) .$ Hence $𝔖_{w} = \partial_{w^{- 1} w_{0}} x^{δ}$ is homogeneous of degree $ℓ (w) .$ If now $α \in ℕ^{n - 1}$ is such that $α \subset δ,$ then by (2.1) $\partial_{r} x^{α}$ is a linear combination of monomials $x^{β}$ such that $β_{i} = α_{i}$ if $i \neq r, r + 1,$ and

max (β_{i}, β_{i + 1}) \leq max (α_{i}, α_{i + 1}) - 1 \leq n - i - 1,

so that $β \subset δ .$ Hence the linear span $H_{n}$ of the monomials $x^{α}, α \subset δ$ is mapped into itself by each $\partial_{r}$ $(1 \leq r \leq n - 1)$ and hence by each $\partial_{w},$ $w \in S_{n} .$ Hence $𝔖_{w} \in H_{n}$ for each $w \in S_{n} .$

(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 (i) < w (i + 1) .$

(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} .$

$□$

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

𝔖_{s_{i}} = x_{1} + x_{2} + \dots + x_{i} .

Proof.

By (4.3), $𝔖_{s_{i}}$ is a homogeneous symmetric polynomial of degree $ℓ (s_{i}) = 1$ in $x_{1}, \dots, x_{i},$ hence is equal to $c (x_{1} + \dots + x_{i})$ for some integer $c .$ But $\partial_{i} 𝔖_{s_{i}} = 𝔖_{1} = 1$ by (4.2) and (4.3)(i), hence $c = 1 .$

$□$

(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} .$

Proof.

We may assume that $m = n + 1 .$ Let $w_{0}^{'}$ be the longest element of $S_{n + 1},$ then $w_{0}^{'} = w_{0} s_{n} s_{n - 1} \dots s_{1},$ where $w_{0}$ is the longest element of $S_{n},$ and hence

\begin{matrix} 𝔖_{i (w)} & = & \partial_{w^{- 1} w_{0}^{'}} (x_{1}^{n} x_{2}^{n - 1} \dots x_{n}) \\ = & \partial_{w^{- 1} w_{0}} \partial_{n} \partial_{n - 1} \dots \partial_{1} (x_{1}^{n} x_{2}^{n - 1} \dots x_{n}) \\ = & \partial_{w^{- 1} w_{0}} (x_{1}^{n - 1} x_{2}^{n - 2} \dots x_{n - 1}) \end{matrix}

(because $\partial_{1} (x_{1}^{n} x_{2}^{n - 1} \dots x_{n}) = x_{1}^{n - 1} x_{2}^{n - 1} x_{3}^{n - 2} \dots x_{n},$ hence $\partial_{2} \partial_{1} (x_{1}^{n} x_{2}^{n - 1} \dots x_{n}) = x_{1}^{n - 1} x_{2}^{n - 2} x_{3}^{n - 2} x_{4}^{n - 3} \dots x_{n},$ and so on.)

$□$

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

If $u \in S_{m}$ and $v \in S_{n},$ we denote by $u \times v$ the permutation

u \times v = (u (1), \dots, u (m), v (1) + m, \dots, v (n) + m)

in $S_{m + n} .$ We have then

\begin{matrix} (4.6) & 𝔖_{u \times v} = 𝔖_{u} \cdot 𝔖_{1_{m} \times v} \end{matrix}

where $1_{m}$ is the identity element of $S_{m} .$

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 \geq 1,$ then $f$ is a constant. For $f \in P_{n} = ℤ [x_{1}, \dots, x_{n}]$ for some $n,$ and is symmetric in $x_{1}, \dots, x_{n + 1}$ because $\partial_{1} f = \dots = \partial_{n} f = 0 .$

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

F (u, v) = 𝔖_{u \times v} - 𝔖_{u} 𝔖_{1_{m} \times v} .

By the remark above, it is enough to show that $\partial_{i} F (u, v) = 0$ for each $i .$

Suppose first that $i < m .$ Then

\partial_{i} F (u, v) = \partial_{i} (𝔖_{u \times v}) - \partial_{i} (𝔖_{u}) \cdot 𝔖_{1_{m} \times v}

because $\partial_{i} (𝔖_{1_{m} \times v}) = 0$ by (4.2). Hence we have $\partial_{i} F (u, v) = 0$ if $ℓ (u s_{i}) > ℓ (u);$ and if $ℓ (u s_{i}) < ℓ (u)$ then

\partial_{i} F (u, v) = F (u s_{i}, v)

which is zero by the inductive hypothesis.

Likewise, if $i > m$ we have

\partial_{i} F (u, v) = {\begin{matrix} F (u, v s_{i}) & if ℓ (v s_{i}) < ℓ (v), \\ 0 & otherwise, \end{matrix}

and so again $\partial_{i} F (u v) = 0$ by the inductive hypothesis.

Finally, if $i = m$ we have $ℓ ((u \times v) s_{m}) > ℓ (u \times v),$ because

(u \times v) (m) = u (m) < m + v (1) = (u \times v) (m + 1),

and therefore $\partial_{m}$ kills $𝔖_{u \times v}$ and $𝔖_{1_{m} \times v};$ moreover, $\partial_{m} 𝔖_{u} = 0,$ because $𝔖_{u} \in ℤ [x_{1}, \dots, x_{m - 1}] .$ Hence $\partial_{m} F (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 $w \in S_{n} .$ The result is true for $w = w_{0}$ by (4.3)(i), since $w_{0}$ is dominant of shape $δ .$

Suppose $w \in S_{n},$ $w \neq w_{0}$ and $w$ is dominant of shape $λ .$ Then $λ \subset δ$ and $λ \neq δ .$ Let $r \geq 0$ be the largest integer such that $λ_{i}^{'} = n - i$ for $1 \leq i \leq r,$ and let $a = λ_{r + 1}^{'} + 1 \leq n - r - 1 .$ Then $w s_{a}$ is dominant of length $ℓ (w) + 1,$ and $λ (w s_{a}) = λ + ε_{a},$ where $ε_{a}$ is the vector whose $a^{th}$ component is $1$ and all other components zero. Hence we have

𝔖_{w} = \partial_{a} 𝔖_{w s_{a}} = \partial_{a} (x_{a} x^{λ}) = 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_{λ} (X_{r}),$ where $r$ is the unique descent of $w,$ and $X_{r} = x_{1} + \dots + x_{r} .$

Proof.

We may assume that $w \neq 1$ (by (4.3)(i), $𝔖_{1} = 1).$ Then $r \geq 1$ and the code of $w$ is

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

so that $λ = (w (r) - r, \dots, w (2) - 2, w (1) - 1) .$ Let $u = w_{0}^{(r)}$ be the longest element of $S_{r} .$ Then

w u = (w (r), \dots, w (1), w (r + 1), w (r + 2) \dots)

is dominant of shape $λ + δ_{r},$ where $δ_{r} = (r - 1, r - 2, \dots, 1, 0),$ and $ℓ (w u) = ℓ (w) + ℓ (u) .$ Hence

𝔖_{w} = \partial_{u} 𝔖_{w u} = \partial_{u} (x^{λ + δ_{r}}) = s_{λ} (X_{r})

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

$□$

Conversely, every Schur function $s_{λ} (X_{r})$ (where $λ$ is a partition of length $\leq r)$ occurs as a Schubert polynomial, namely as $𝔖_{w}$ where $w$ is the permutation with code $c (w) = (λ_{r}, λ_{r - 1}, \dots, λ_{1}),$

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

\begin{matrix} (4.9) & 𝔖_{w} = s_{λ} (X_{ϕ_{1}}, \dots, X_{ϕ_{m}}) \end{matrix}

where $X_{i} = x_{1} + \dots + x_{i}$ for each $i \geq 1 .$

Proof.

The idea is to convert $w$ systematically into a dominant permutation. Recall ((1.23), (1.24)) that if $c (w) = (c_{1}, c_{2}, \dots)$ and $c_{i} \leq c_{i + 1}$ for some $i \geq 1,$ then $ℓ (w s_{i}) = ℓ (w) + 1$ and

\begin{matrix} (*) & c (w s_{i}) = (c_{1}, \dots, c_{i - 1}, c_{i + 1} + 1, c_{i}, c_{i + 2}, c_{i + 3}, \dots) . \end{matrix}

As in Chapter I let

λ (w) = (p_{1}^{m_{1}}, \dots, p_{k}^{m_{k}})

where $p_{1} > \dots > p_{k} > 0$ (and each $m_{i} \geq 1),$ and let

ϕ (w) = (f_{1}^{m_{1}}, \dots, f_{k}^{m_{k}})

where $f_{1} \leq \dots \leq f_{k} .$

Consider first the terms equal to $p_{1}$ in the sequence $c (w) .$ They occupy the positions $f_{1} - m_{1} + 1, \dots, f_{1} .$ We shall use $(*)$ to move them all to the left until they occupy the first $m_{1}$ positions, by multiplying $w$ on the right by

u_{1} = (s_{f_{1} - m_{1}} \dots s_{2} s_{1}) (s_{f_{1} - m_{1} + 1} \dots s_{3} s_{2}) \dots (s_{f_{1} - 1} \dots s_{m_{1} + 1} s_{m_{1}}) .

Let $w_{1} = w u_{1} .$ In the code of $w_{1},$ the first $m_{1}$ entries will be equal to $p_{1} + f_{1} - m_{1};$ the shape of $w_{1}$ is

λ^{(1)} = λ (w_{1}) = ({(p_{1} + f_{1} - m_{1})}^{m_{1}}, p_{s}^{m_{2}}, \dots, p_{k}^{m_{k}}),

and it follows from the description (1.38) of vexillary codes that the terms equal to $p_{2}$ in the sequence $c (w_{1})$ will occupy the positions $f_{2} - m_{2} + 1, \dots, f_{2} .$ 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

u_{2} = (s_{f_{2} - m_{2}} \dots s_{m_{1} + 2} s_{m_{1} + 1}) (s_{f_{2} - m_{2} + 1} \dots s_{m_{1} + 2}) \dots (s_{f_{2} - 1} \dots s_{m_{1} + m_{2}}) .

Let $w_{2} = w_{1} u_{2};$ 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};$ the shape of $w_{2}$ is

λ^{(2)} = λ (w_{2}) = ({(p_{1} + f_{1} - m_{1})}^{m_{1}}, {(p_{1} + f_{2} - m_{1} - m_{2})}^{m_{2}}, p_{3}^{m_{3}}, \dots, p_{k}^{m_{k}}),

and the terms equal to $p_{3}$ in the sequence $c (w_{2})$ will occupy the positions $f_{3} - m_{3} + 1, \dots, f_{3} - m_{3} .$

We continue in this way; at the $r^{th}$ stage we define $w_{r} = w_{r - 1} u_{r},$ where

u_{r} = (s_{f_{r} - m_{r}} \dots s_{m_{1} + \dots + m_{r - 1} + 1}) \dots (s_{f_{r} - 1} \dots s_{m_{1} + \dots + m_{r}}),

and $w_{r}$ has shape

λ^{(r)} = λ (w_{r}) = ({(p_{1} + a_{1})}^{m_{1}}, \dots, {(p_{r} + a_{r})}^{m_{r}}, p_{r + 1}^{m_{r} + 1}, \dots, p_{k}^{m_{k}})

where $a_{i} = f_{i} - (m_{1} + \dots + m_{i}) \geq 0$ by (1.36). Notice also that

(p_{i - 1} + a_{i - 1}) - (p_{i} + a_{i}) = (m_{i} + p_{i - 1} - p_{i}) - (f_{i} - f_{i - 1}) \geq 0

by (1.37).

Finally we reach $w_{k} = w u_{1} \dots u_{k},$ which is dominant with shape (and code)

μ = λ^{(k)} = ({(p_{1} + a_{1})}^{m_{1}}, \dots, {(p_{k} + a_{k})}^{m_{k}}) .

We have

\begin{matrix} ℓ (w) = | λ | = \sum m_{i} p_{i}, \\ ℓ (w_{k}) = | λ^{(k)} | = \sum m_{i} (p_{i} + a_{i}), \end{matrix}

and

ℓ (u_{r}) = a_{r} m_{r} (1 \leq r \leq k)

so that

ℓ (w_{k}) = ℓ (w) + \sum_{r = 1}^{k} ℓ (u_{r})

and therefore, since $w = w_{k} {(u_{1} \dots u_{k})}^{- 1},$

𝔖_{w} = \partial_{u_{1}} \dots \partial_{u_{k}} 𝔖_{w_{k}}

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

𝔖_{w_{k}} = x^{μ} = s_{μ} (X_{1}, \dots, X_{m})

where $m = m_{1} + \dots + m_{k} = ℓ (λ) .$ Hence by repeated use of (3.10) we obtain

\begin{matrix} 𝔖_{w_{k - 1}} & = & \partial_{u_{k}} 𝔖_{w_{k}} \\ = & s_{λ^{(k - 1)}} (X_{1}, \dots, X_{m_{1} + \dots + m_{k - 1}}, X_{f_{k} - m_{k} + 1}, \dots, X_{f_{k} - 1}, X_{f_{k}}) \\ = & s_{λ^{(k - 1)}} (X_{1}, \dots, X_{m_{1} + \dots + m_{k - 1}}, {(X_{f_{k}})}^{m_{k}}) \end{matrix}

by virtue of (3.6). If we now operate with $\partial_{u_{k - 1}}$ we shall obtain in the same way

𝔖_{w_{k - 1}} = \partial_{u_{k - 1}} 𝔖_{w_{k - 1}} = s_{λ^{(k - 2)}} (X_{1}, \dots, X_{m_{1} + \dots + m_{k - 2}}, {(X_{f_{k - 1}})}^{m_{k - 1}}, {(X_{f_{k}})}^{m_{k}})

and so finally

𝔖_{w} = s_{λ} ({(X_{f_{1}})}^{m_{1}}, \dots, {(X_{f_{k}})}^{m_{k}}) .

$□$

Remarks. 1. As in Chapter I, let

λ' = (q_{1}^{n_{1}}, \dots, q_{k}^{n_{k}})

be the conjugate partition, so that

m_{1} + \dots + m_{i} = = q_{k + 1 - i} (1 \leq i \leq k)

and therefore

\begin{matrix} p_{i} + a_{i} & = & p_{i} + f_{i} - q_{k + 1 - i} \\ = & g_{k + 1 - i} \end{matrix}

by (1.41), where $(g_{1}^{n_{1}}, \dots, g_{k}^{n_{k}})$ is the flag of $w^{- 1} .$ Thus

\begin{matrix} (4.10) & μ = λ^{(k)} = (g_{k}^{m_{1}}, g_{k - 1}^{m_{2}}, \dots, g_{1}^{m_{k}}) . \end{matrix}

2. The result (4.9) admits a converse. If $λ = (p_{1}^{m_{1}}, \dots, p_{k}^{m_{k}})$ as above, every non-zero multi-Schur function $s_{λ} ({(X_{f_{1}})}^{m_{1}}, \dots, {(X_{f_{k}})}^{m_{k}})$ that satisfies the conditions of the duality theorem (3.8''), namely

\begin{matrix} (1) & 0 \leq f_{i + 1} - f_{i} \leq m_{i + 1} + n_{k + 1 - i} (1 \leq i \leq k - 1), \end{matrix}

is the Schubert polynomial of a vexillary permutation, namely the permutation with shape $λ$ and flag $ϕ = (f_{1}^{m_{1}}, \dots, f_{k}^{m_{k}}) .$ 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

f_{i} \geq m_{1} + \dots + m_{i} (1 \leq i \leq k)

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

Let $H_{n}$ denote the additive subgroup of $P_{n} = ℤ [x_{1}, \dots, x_{n}]$ spanned by the monomials $x^{α}, α \subset δ_{n} = (n - 1, n - 2, \dots, 1, 0) .$

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

Proof.

By (4.3) each $𝔖_{w}$ lies in $H_{n} .$ If

\sum a_{w} 𝔖_{w} = 0 (a_{w} \in ℤ)

is a linear dependence relation, then by homogeneity we have

\begin{matrix} (1) & \sum_{ℓ (w) = p} a_{w} 𝔖_{w} = 0 \end{matrix}

for each $p \geq 0,$ and by operating on (1) with $\partial_{w}$ we see that $a_{w} = 0 .$ Hence the $𝔖_{w}$ are linearly independent and hence form a $ℚ -basis$ of $H_{n} \otimes ℚ .$ It follows that each monomial $x^{α}, α \subset δ_{n},$ can be expressed in the form

\begin{matrix} (2) & x^{α} = \sum_{ℓ (w) = | α |} b_{w} 𝔖_{w} \end{matrix}

with rational coefficients $b_{w};$ by operating on (2) with $\partial_{w}$ we have $b_{w} = \partial_{w} x^{α},$ and hence the $b_{w}$ are integers.

$□$

From (4.11) it follows that

(4.12) The $𝔖_{w}, w \in S_{\infty},$ form a $ℤ -basis$ of $P_{\infty} = ℤ [x_{1}, x_{2}, \dots] .$

Proof.

Let $x^{α}$ be a monomial in $P_{\infty} .$ Then $α \subset δ_{n}$ for sufficiently large $n,$ hence $x^{α}$ is a linear combination of the $𝔖_{w} .$

$□$

For each $n \geq 1,$ let $S^{(n)}$ denote the set of all permutations $w$ such that $w (n + 1) < w (n + 2) < \dots,$ or equivalently such that the code of $w$ has length $\leq n .$

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

Proof.

By (4.3)(iii) we have

\begin{matrix} 𝔖_{w} \in P_{n} & ⟺ & \partial_{m} 𝔖_{w} = 0 for all m > n \\ ⟺ & w \in S^{(n)} . \end{matrix}

Let $P_{n}^{'} \subset P_{n}$ be the $ℤ -span$ of the $𝔖_{w}, w \in S^{(n)} .$ If $P_{n}^{'} \neq P_{n},$ choose $f \in P_{n} - P_{n}^{'};$ by (4.12) we can write $f$ as a linear combination of Schubert polynomials, say

\begin{matrix} (1) & f = \sum_{w} a_{w} 𝔖_{w} \end{matrix}

where there is at least one term with $a_{w} \neq 0$ and $w \notin S^{(n)} .$ 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}^{'} = P_{n},$ which proves (4.13).

$□$

Let $η : P_{n} \to ℤ$ be the homomorphism defined by $η (x_{i}) = 0$ $(1 \leq i \leq n) .$ In other words, $η (f)$ is the constant term of $f,$ for each polynomial $f \in P_{n} .$ The expression of $f$ in terms of Schubert polynomials is then

\begin{matrix} (4.14) & f = \sum_{w \in S^{(n)}} η (\partial_{w} f) 𝔖_{w} . \end{matrix}

Proof.

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

$□$

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

f 𝔖_{w} = \sum (α_{i} - α_{j}) 𝔖_{w t_{i j}},

where $t_{i j}$ is the transposition that interchanges $i$ and $j,$ and the sum is over all pairs $i < j$ such that $ℓ (w t_{i j}) = ℓ (w) + 1 .$

Proof.

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

f 𝔖_{w} = \sum_{v} \partial_{v} (f 𝔖_{w}) \cdot 𝔖_{v}

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

\partial_{v} (f 𝔖_{w}) = v (f) \partial_{v} 𝔖_{w} + \sum (α_{i} - α_{j}) \partial_{v t_{i j}} 𝔖_{w}

summed over $i < j$ such that $ℓ (v t_{i j}) = ℓ (v) - 1 = ℓ (w) .$ It follows that $\partial_{v} (f 𝔖_{w}) = α_{i} - α_{j}$ if $w = v t_{i j},$ and is zero otherwise.

$□$

In particular:

\begin{matrix} (4.15') & x_{r} 𝔖_{w} = \sum σ (t) 𝔖_{w t} \end{matrix}

summed over transpositions $t = t_{i r}$ such that $ℓ (w t) = ℓ (w) + 1,$ where $σ (t) = - 1$ or $+ 1$ according as $i < r$ or $i > r .$

(4.15'') (Monk's formula) $𝔖_{s_{r}} 𝔖_{w} = \sum 𝔖_{w t}$ summed over transpositions $t = t_{i j}$ such that $i \leq r < j$ and $ℓ (w t) = ℓ (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) \leq \dots .$ Choose the largest $s > r$ such that $w (r) > w (s)$ and let $v = w t_{r s} .$ Then from (4.15') applied to $v$ we have

\begin{matrix} (1) & x_{r} 𝔖_{v} = 𝔖_{w} - \sum_{w'} 𝔖_{w'} \end{matrix}

summed over all permutations $w' = v t_{q r}$ 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 $i \geq 1$ we have

w' (j) = w (j) for j < i, and w' (i) > w (i) .

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

We have proved

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

𝔖_{w} = x_{r} 𝔖_{v} + \sum_{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, 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 $ℓ (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, \dots, p)$ has code $(p),$ hence is dominant with Schubert polynomial $x_{1}^{p}$ by (4.7)·)

$□$

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

\begin{matrix} (4.18) & 𝔖_{w} (x_{1}, \dots, x_{n}) = \sum_{u, v} d_{u v}^{w} 𝔖_{u} (x_{1}, \dots, x_{m}) 𝔖_{v} (x_{m + 1}, \dots, x_{n}) \end{matrix}

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

(4.19) The coefficients $d_{u v}^{w}$ in (4.18) are non-negative integers.

Proof.

We proceed by induction on $ℓ (v) .$ Suppose first that $d_{u v}^{w} \neq 0$ and that $ℓ (v) > 0,$ so that $v \neq 1 .$ Then there exists $j > m$ such that $\partial_{j} 𝔖_{v} (x_{m + 1}, \dots, x_{n}) \neq 0 .$ From (4.18) we conclude that $\partial_{j} 𝔖_{w} \neq 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 $ℓ (v s_{j}) = ℓ (v) - 1 .$ By the inductive hypothesis, we conclude that $d_{u v}^{w} \geq 0$ if $v \neq 1 .$

It remains to consider the case $v = 1 .$ Let $ρ_{m} : P_{n} \to P_{m}$ be the homomorphism for which $ρ (x_{i}) = x_{i}$ if $i \leq m,$ and $ρ (x_{i}) = 0$ if $i > m .$ From (4.18) we have

\begin{matrix} (2) & ρ_{m} 𝔖_{w} = \sum_{u} d_{u, 1}^{w} 𝔖_{u} . \end{matrix}

Let $r$ be the last descent of $w .$ If $r \leq m$ then $𝔖_{w} \in P_{r}$ and hence $ρ_{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

\begin{matrix} (3) & ρ_{m} 𝔖_{w} = \sum_{w'} ρ_{m} 𝔖_{w'} . \end{matrix} Assume that the coefficients d_{u, 1}^{w'} are \geq 0 whenever w' precedes w in the reverse 
lexicographical ordering. Then it follows from (2) and (3) that each d_{u, 1}^{w} \geq 0 . (As remarked before (4.16), the first element in this ordering (if ℓ (w) = p) is the permutation (p + 1, 1, 2, \dots, 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 $(i \geq 1, j \geq 1) .$ Choose a point $p = (i, j) \in D$ which is rightmost in its row, and suppose that not all the points $(1, j), \dots, (i - 1, j)$ directly above $p$ belong to $D .$ If $h$ is the largest integer less than $i$ such that $(h, j) \in D,$ let $D_{1}$ denote the diagram obtained from $D$ by replacing $p = (i, j)$ by $(h, j) .$ 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 (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

x^{D} = \prod_{i \geq 1} x_{i}^{a_{i}}

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

With this notation established, Kohnert's algorithm states that

(4.20) For each permutation $w$ we have

𝔖_{w} = \sum_{D \in K (D (w))} x^{D}

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

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

\begin{matrix}  \end{matrix}

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} .$

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 \geq n .$ Then

\begin{matrix} (4.21) & \begin{matrix} τ f = τ_{m} f & = & \partial_{1} \dots \partial_{m} (x_{1} \dots x_{m} f) \\ = & π_{1} \dots π_{m} (f) \end{matrix} \end{matrix}

is independent of $m,$ because $π_{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} .$

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

τ x_{1} = \partial_{1} (x_{1}^{2}) = x_{1} + x_{2}

and for $i \geq 2,$

\begin{matrix} τ x_{i} & = & \partial_{1} \dots \partial_{i} (x_{1} \dots x_{i - 1} x_{i}^{2}) \\ = & \partial_{1} \dots \partial_{i - 1} (x_{1} \dots x_{i - 1} (x_{i} + x_{i + 1})) \\ = & x_{i + 1} \partial_{1} \dots \partial_{i - 1} (x_{1} \dots x_{i - 1}) \\ = & x_{i + 1} \end{matrix}

so that by (4.4)

τ 𝔖_{s_{i}} = τ (x_{1} + \dots + x_{i}) = x_{1} + \dots + x_{i + 1} = 𝔖_{s_{i + 1}} .

More generally,

(4.22) For all permutations $w,$

τ 𝔖_{w} = 𝔖_{1 \times w}

where $1 \times w$ is the permutation $(1, w (1) + 1, w (2) + 1, \dots) .$

Proof.

For each $r \geq 1$ let $w_{0}^{(r)}$ be the longest element of $S_{r},$ and let $δ_{r} = (r - 1, r - 2, \dots, 1) .$ Then if $w \in S_{n}$ we have

\begin{matrix} τ 𝔖_{w} & = & \partial_{1} \dots \partial_{n} (x_{1} \dots x_{n} \partial_{w^{- 1} w_{0}^{(n)}} x^{δ_{n}}) \\ = & \partial_{1} \dots \partial_{n} \partial_{w^{- 1} w_{0}^{(n)}} (x^{δ_{n + 1}}) . \end{matrix}

Now $s_{1} \dots s_{n}$ is the cycle $1 \to 2 \to \dots \to n + 1 \to 1,$ and hence

s_{1} \dots s_{n} w^{- 1} w_{0}^{(n)} = {(1 \times w)}^{- 1} w_{0}^{(n + 1)}

so that

ℓ (s_{1} \dots s_{n} w^{- 1} w_{0}^{(n)}) = ℓ (s_{1} \dots s_{n}) + ℓ (w^{- 1} w_{0}^{(n)})

and therefore by (2.7) we have

τ 𝔖_{w} = \partial {(1 \times w)}^{- 1} w_{0}^{(n + 1)} (x^{δ_{n + 1}}) = 𝔖_{1 \times w} .

$□$

(4.23) Let $α \in ℕ^{n}$ and $0 \leq p_{1} \leq \dots \leq p_{n} .$ Then

τ s_{α} (X_{p_{1}}, \dots, X_{p_{n}}) = s_{α} (X_{p_{1} + 1}, \dots, X_{p_{n} + 1}) .

Proof.

Since $τ = π_{1} π_{2} \dots π_{p_{n}},$ this follows from (3.10).

$□$

(4.24) We have

\partial_{i} τ^{r} = 0

for $1 \leq i \leq r .$

Proof.

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

$□$

For each $n \geq 1$ let $ρ_{n} : P_{\infty} \mapsto P_{m}$ be the homomorphism defined by

ρ_{n} (x_{i}) = {\begin{matrix} x_{i} & if i \leq n, \\ 0 & if i > n . \end{matrix}

(4.25) Let $w_{0}^{(n)}$ be the longest element of $S_{n} .$ Then

π_{w_{0}^{(n)}} (f) = ρ_{n} τ^{n} (f)

for all $f \in P_{n} .$

Proof.

By linearity we may assume that $f = x^{α}$ where $α \in ℕ^{n} .$ Since $x^{α} = s_{α} (X_{1}, \dots, X_{n})$ by (3.5'), we have

τ^{n} (x^{α}) = s_{α} (X_{n + 1}, \dots, X_{2 n})

by (4.23), and hence

ρ_{n} τ^{n} (x_{α}) = s_{α} (X_{n}, \dots, X_{n})

which is equal to $π_{w_{0}^{(n)}} (x^{α})$ by (2.16')·

$□$

Transitions

A transition is an equation of the form

\begin{matrix} T (w, r) & 𝔖_{w} = x_{r} 𝔖_{u} + \sum_{v \in Φ} 𝔖_{v} \end{matrix}

where $r \geq 1,$ $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

x_{r} 𝔖_{u} = \sum_{t} σ (t) 𝔖_{u t}

summed over transpositions $t = t_{i r}$ such that $ℓ (u t) = ℓ (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

\begin{matrix} (1) & ℓ (u t_{r j}) & = & ℓ (u) + 1, \\ (2) & w & = & u t_{r j} . \end{matrix}

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

\begin{matrix} G (w) & G (u) \end{matrix}

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

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

(A \cup B \cup C) \cap G (w) = \emptyset .

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

d_{0} (w) \leq r \leq d_{1} (w)

where $d_{0} (w)$ (resp. $d_{1} (w))$ is the first (resp. last) descent of $w .$ (In terms of the code $c (w), d_{0} (w)$ is the first descent of the sequence $c (w),$ and $d_{1} (w)$ is the largest $i$ such that $c_{i} (w) \neq 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 \in Φ$ is of the form $v = u t_{i r}$ with $i < r$ and $ℓ (v) = ℓ (u) + 1$ $(= ℓ (w)).$ Again by (1.10), this means that

\begin{matrix} G (w) & G (u) & G (v) \end{matrix}

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

The element $v = u t_{i r}$ of $Φ$ for which $i$ is maximal is called the leader of $Φ .$ Thus $v \in Φ$ is the leader if and only if

\begin{matrix} (4.27) & (A' \cup B') \cap G (w) = \emptyset . \end{matrix}

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 \times w .$ If $Φ (w, r)$ is not empty, then $v \mapsto 1 \times v$ is a bijection of $Φ (w, r)$ onto $Φ (1 \times 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}} = x_{s} 𝔖_{u^{- 1}} + \sum_{v \in Φ} 𝔖_{v^{- 1}} .

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

𝔖_{w} (1) = 𝔖_{w} (1, 1, \dots)

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) + \sum_{v \in Φ} 𝔖_{v} (1)

and also, by (4.29)

𝔖_{w^{- 1}} (1) = 𝔖_{u^{- 1}} (1) + \sum_{v \in Φ} 𝔖_{v^{- 1}} (1) .

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

\begin{matrix} (4.30) & 𝔖_{w} (1) = 𝔖_{w^{- 1}} (1) \end{matrix}

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 (w, r)$ be a transition and let $v \in Φ (w, r) .$ Consider again the graphs of $w$ and $v :$

\begin{matrix} G (w) & G (v) \end{matrix}

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

\begin{matrix} (4.31) & \begin{matrix} c_{i} (w) = m + n, & c_{r} (w) = n + p + 1, \\ c_{i} (v) = m + n + p + 1, & c_{r} (v) = n, \end{matrix} \end{matrix}

and $c_{k} (v) = c_{k} (w)$ if $k \neq i, r .$ In particular, $c_{r} (w) > c_{r} (v)$ for all $v \in Φ (w, r) .$

Proof.

$c_{i} (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 $c_{i} (w) = c_{r} (v)$ and $c_{r} (w) = c_{i} (v) .$ Hence in this case $c (v) = t_{i r} c (w)$ and therefore $λ (v) = λ (w) .$

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

either

c_{i} (v) > c_{i} (w) \geq c_{r} (w) > c_{r} (v),

c_{i} (v) > c_{r} (w) > c_{i} (w) > c_{r} (v) .

In both cases it follows that $λ (v)$ is of the form $R^{a} λ (w),$ where $R$ is a raising operator and $a \geq 1 .$ 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) \geq λ (w)$ for all $v \in Φ (w, r),$ with equality if and only if $v$ is the leader of $Φ .$

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

λ (w)' \geq λ (w^{- 1}) .

Hence for $v \in Φ (w, r)$ we have

\begin{matrix} (4.33) & λ (w)' \overset{(*)}{\geq} λ (v)' \geq λ (v^{- 1}) \overset{(*)}{\geq} λ (w^{- 1}) \end{matrix}

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

(A' \cup B' \cup C') \cap G (w) = \emptyset

and hence, as in the proof of (4.26), that $Card Φ \leq 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 \in Φ .$ 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 > d_{0} (w) .$ Then

d_{0} (v) \geq d_{0} (w)

for all $v \in Φ (w, r) .$

Proof.

As before, let $v = u t_{i r}$ with $i < r,$ and let $d_{0} (w) = d .$ We have to show that

\begin{matrix} (*) & c_{1} (v) \leq \dots \leq c_{d} (v) . \end{matrix}

We distinguish three cases:

(a)	$i > d,$ so that $d \leq i - 1$ and therefore $c_{k} (v) = c_{k} (w)$ for $1 \leq k \leq d .$
(b)	$i = d .$ In this case we have $c_{k} (v) = c_{k} (w)$ for $1 \leq k \leq d - 1,$ and $c_{d - 1} (v) = c_{d - 1} (w) \leq c_{d} (w) < c_{d} (v)$ by (4.31), so that $c_{d - 1} (v) < c_{d} (v) .$
(c)	$i > d .$ Since $d < r$ we have $i + 1 < r$ and $c_{i} (w) \leq c_{i + 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 $c_{i} (v) \leq c_{i + 1} (v) .$ Hence $c_{i - 1} (v) = c_{i - 1} (w) \leq c_{i} (w) < c_{i} (v) \leq c_{i + 1} (v)$ and therefore $c_{i - 1} (v) < c_{i} (v) \leq c_{i + 1} (v) .$ Since the sequences $(c_{1} (v), \dots, c_{d} (v))$ and $(c_{1} (w), \dots, c_{d} (w))$ differ only in the $i th$ place, we have $c_{1} (v) \leq \dots \leq c_{d} (v)$ as required.

$□$

The maximal transition for $w$ is $T (w, d_{1} (w)) .$ Let us temporarily write $w \to v$ to mean that $v \in Φ (w, d_{1} (w)) .$

(4.36) Suppose that

w = w_{0} \to w_{1} \to \dots \to w_{p}

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

p < (d_{1} (w) - d_{0} (w)) ℓ (w) .

Proof.

For any permutation $v,$ let $e (v) = d_{1} (v) - d_{0} (v) \geq 0 .$ Also let $f (v)$ denote the last nonzero term in the sequence $c (v),$ i.e. $f (v) = c_{d_{1} (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

d_{0} (w_{k}) \geq d_{0} (w_{k - 1})

for $1 \leq k \leq p,$ and from (4.31) we have

\begin{matrix} (1) & c_{r} (w_{k}) < c_{r} (w_{k - 1}) \end{matrix}

where $r = d_{1} (w_{k - 1}) .$ Hence $d_{1} (w_{k}) \leq d_{1} (w_{k - 1})$ and therefore

e (w_{k}) \leq e (w_{k - 1}) .

Moreover, if $e (w_{k}) = e (w_{k - 1})$ we must have $d_{1} (w_{k}) = d_{1} (w_{k - 1})$ and hence by (1)

f (w_{k}) < f (w_{k - 1}) .

It follows that the $p + 1$ points $(x_{k}, y_{k}) = (e (w_{k}), f (w_{k}))$ are all distinct. Since they all satisfy $1 \leq w_{k} \leq e (w)$ and $1 \leq y_{k} \leq ℓ (w),$ we have $p + 1 \leq e (w) ℓ (w),$ as required.

$□$

The rooted tree of a permutation

In what follows we shall when necessary replace a permutation $w$ by $1 \times 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 $(d_{1} (w) - d_{0} (w)) ℓ (w)$ in (4.36).

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

(i)	if $w$ is vexillary, then $T_{w} = {w};$
(ii)	if $w$ is not vexillary, take the maximal transition for $w :$ $\begin{matrix} (*) & 𝔖_{w} = x_{r} 𝔖_{u} + \sum_{v \in Φ} 𝔖_{v} \end{matrix}$

where $r = d_{1} (w) .$ (If $Φ$ is empty, replace $w$ by $1 \times w$ as explained above.) To obtain $T_{w},$ join $w$ by an edge to each $v \in Φ,$ and attach to each $v \in Φ$ its tree $T_{v} .$

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

Recall that $ρ_{m} : P_{\infty} \to P_{m}$ is the homomorphism defined by $ρ_{m} (x_{i}) = x_{i}$ if $1 \leq i \leq m,$ and $ρ_{m} (x_{i}) = 0$ if $i > m .$

(4.37) Let $V$ be the set of endpoints of $T_{w} .$ Then if $m \leq d_{0} (w)$ we have

ρ_{m} (𝔖_{w}) = \sum_{v \in V} s_{λ (v)} (X_{m}) .

Proof.

If $w$ is vexillary we have $ρ_{m} (𝔖_{w}) = s_{λ (w)} (X_{m})$ by (4.4), since $ϕ_{1} (w) = d_{0} (w) \geq m .$ If $w$ is not vexillary, it follows from the maximal transition $(*)$ above that

ρ_{m} (𝔖_{w}) = \sum_{v \in Φ} ρ_{m} (𝔖_{v})

since $r = d_{1} (w) > d_{0} (w) \geq m .$ The result now follows by induction on $Card (T_{w}) .$

$□$

Multiplication of Schur functions

Let $μ, ν$ be partitions and let $u \in S_{n},$ $u' \in S_{p}$ be Grassmannian permutations of shapes $μ, ν$ respectively. Let $w = u \times u' \in S_{n + p},$ so that by (4.6) and (4.8)

\begin{matrix} 𝔖_{w} & = & 𝔖_{u} \cdot 𝔖_{1_{n} \times u'} \\ = & s_{μ} (X_{r}) s_{ν} (X_{s}) \end{matrix}

where $r = d_{0} (u)$ and $s = n + d_{0} (u') .$ Hence if $m \leq r$ we have

ρ_{m} (𝔖_{w}) = s_{μ} (X_{m}) s_{ν} (X_{m})

and so by (4.37)

s_{μ} (X_{m}) s_{ν} (X_{m}) = \sum_{v \in V} s_{λ (v)} (X_{m})

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

\begin{matrix} (4.38) & s_{μ} s_{ν} = \sum_{v \in V} s_{λ (v)} \end{matrix}

where $V$ is the set of endpoints of the tree $T_{u \times 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)}, \dots, μ^{(k)}$ are partitions, let $u_{i} \in S_{n_{i}}$ be a Grassmannian permutation of shape $μ^{(i)},$ for each $i = 1, \dots, k$ (so that $n_{i} \geq ℓ (μ^{(i)}) + ℓ (μ^{(i)}'))$ and let $w = u_{1} \times \dots \times u_{k} .$ Then

\begin{matrix} (4.38') & s_{μ^{(1)}} \dots s_{μ^{(k)}} = \sum_{v \in V} s_{λ (v)} \end{matrix}

where $V$ is the set of endpoints of the tree $T_{w} .$

In particular, suppose that each $μ^{(i)}$ is one-part partition, say $μ^{(i)} = (μ_{i}),$ so that the left-hand side of (4.38') becomes $h_{μ_{1}} h_{μ_{2}} \dots = h_{μ} .$ Correspondingly, each $u_{i}$ is a cycle of length $μ_{i} + 1,$ namely $u_{i} = (μ_{i} + 1, 1, 2, \dots, μ_{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 = u_{1} \times u_{2} \times \dots .$

Schubert polynomials for $S_{4}$

\begin{matrix} 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{matrix}

Notes and References

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

page history

Notes on Schubert PolynomialsChapter 4

Schubert Polynomials (1)

Kohnert's algorithm

The shift operator

Transitions

The rooted tree of a permutation

Multiplication of Schur functions

Notes and References

Notes on Schubert Polynomials
Chapter 4