Notes on Schubert Polynomials
Chapter 2

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

Last update: 27 June 2013

Divided differences

If $f$ is a function of $x$ and $y$ (and possibly other variables), let

$${\partial }_{xy}f=\frac{f(x,y)-f(y,x)}{x-y}$$

("divided difference"). Equivalently

$${\partial }_{xy}f={(x-y)}^{-1}(1-s_{xy})$$

where $s_{xy}$ interchanges $x$ and $y\text{.}$ The operator ${\partial }_{xy}$ takes polynomials to polynomials, and has degree $-1$ (i.e., if $f$ is homogeneous of degree $d,$ then ${\partial }_{xy}f$ is homogeneous of degree $d-1\text{).}$ Explicitly, if $f=x^r{y}^s$ we have

$$\begin{array}{cc}\text{(2.1)}& \begin{array}{ccc}{\partial }_{xy}\left(x^r{y}^s\right)& =& \frac{x^r{y}^s-x^s{y}^r}{x-y}\\ & =& \sigma (r-s)\sum x^p{y}^q\end{array}\end{array}$$

where the sum is over $(p,q)$ such that $p+q=r+s-1$ and $\text{max}(p,q)<\text{max}(r,s),$ and $\sigma (r-s)$ is $+1,0$ or $-1$ according as $r-s$ is positive, zero or negative.

On a product $fg,{\partial }_{xy}$ acts according to the rule

$$\begin{array}{cc}\text{(2.2)}& {\partial }_{xy}\left(fg\right)=\left({\partial }_{xy}f\right)g+\left(s_{xy}f\right)\left({\partial }_{xy}g\right)\text{.}\end{array}$$

In particular we have

$$\begin{array}{cc}\text{(2.2')}& {\partial }_{xy}\left(fg\right)=f{\partial }_{xy}g\end{array}$$

if $f(x,y)=f(y,x)\text{.}$

(2.3)

(i)	${\partial }_{xy}{s}_{xy}=-{\partial }_{xy},s_{xy}{\partial }_{xy}={\partial }_{xy},$
(ii)	${\partial }_{xy}^2=0,$
(iii)	${\partial }_{xy}{\partial }_{yz}{\partial }_{xy}={\partial }_{yz}{\partial }_{xy}{\partial }_{yz}\text{.}$

		Proof.
	(i) and (ii) are immediate from the definitions, and (iii) is verified by direct calculation: each side is equal to $${(x-y)}^{-1}{(x-z)}^{-1}{(y-z)}^{-1}\sum _{w\in S_3}\epsilon \left(w\right)w,$$ where the symmetric group $S_3$ permutes $x,y$ and $z,$ and $\epsilon \left(w\right)$ is the sign of the permutation $w\text{.}$ $\square$

Let $x_1,x_2,\dots ,x_n,\dots$ be independent variables, and let

$$P_n=\mathbb{Z}[x_1,x_2,\dots ,x_n]$$

for each $n\ge 1,$ and

$$\begin{array}{ccc}{P}_{\infty }& =& \mathbb{Z}[x_1,x_2,\dots ]\\ & =& \bigcup _{n=1}^{\infty }{P}_n\text{.}\end{array}$$

For each $i\ge 1$ let

$${\partial }_i={\partial }_{x_i,x_{i+1}}\text{.}$$

Each ${\partial }_i$ is a linear operator on $P_{\infty }$ (and on $P_n$ for $n>i\text{)}$ of degree $-1\text{.}$ From (2.3) we have (compare with (1.1))

$$\begin{array}{cc}\text{(2.4)}& \{\begin{array}{cc}{\partial }_i^2=0,& \\ {\partial }_i{\partial }_j={\partial }_j{\partial }_i& \text{if}\hspace{0.17em}|i-j|>1,\\ {\partial }_i{\partial }_{i+1}{\partial }_i={\partial }_{i+1}{\partial }_i{\partial }_{i+1}& \end{array}\end{array}$$

For any sequence $a=(a_1,\dots ,a_p)$ of positive integers, we define

$${\partial }_a={\partial }_{a_1}\dots {\partial }_{a_p}\text{.}$$

Recall that if $w$ is any permutation, $R\left(w\right)$ denotes the set of reduced words for $w,$ i.e. sequences $(a_1,\dots ,a_p)$ such that $w=s_{a_1}\dots s_{a_p}$ and $p=\ell \left(w\right)\text{.}$

(2.5) If $a,b\in R\left(w\right)$ then ${\partial }_a={\partial }_b\text{.}$

		Proof.
	We proceed by induction on $p=\ell \left(w\right)\text{.}$ Let us write $a\equiv b$ to mean that ${\partial }_a={\partial }_b\text{.}$ The inductive hypothesis then implies that $$\begin{array}{cc}(*)& a\equiv b\hspace{0.17em}\text{if either}\hspace{0.17em}{a}_1=b_1\hspace{0.17em}\text{or}\hspace{0.17em}{a}_p=b_p\text{.}\end{array}$$ By the exchange lemma (1.8) we have $$c_i=(b_1,a_1,\dots ,{\hat{a}}_i,\dots ,a_p)\in R\left(w\right)$$ for some $i=1,\dots ,p\text{.}$ If $i\ne p$ then $b\equiv c_i\equiv a$ by virtue of $(*),$ so that $a\equiv b\text{.}$ If $i=p$ and $|b_1-a_1|>1$ then by (2.4) and (1.1) $$c_p^{\prime }=(a_1,b_1,a_2,\dots ,a_{p-1})\in R\left(w\right)$$ and $a\equiv c_p^{\prime }\equiv c_p\equiv b,$ so that again $a\equiv b\text{.}$ Finally, if $i=p$ and $|b_1-a_1|=1,$ we apply the exchange lemma again, this time to $c_p$ and $a\text{;}$ this shows that $$d_i=(a_1,b_1,a_1,\dots ,{\hat{a}}_i,\dots ,a_{p-1})\in R\left(w\right)$$ for some $i=2,\dots ,p-1\text{.}$ But then by (2.4) and (1.1) we have $$d_i^{\prime }=(b_1,a_1,b_1,a_2,\dots ,{\hat{a}}_i,\dots ,a_{p-1})\in R\left(w\right)$$ and $a\equiv d_i\equiv d_i^{\prime }\equiv b\text{.}$ Hence $a\equiv b$ in all cases. $\square$

Remark. For any permutation $w,$ let $GR\left(w\right)$ denote the graph whose vertices are the reduced words for $w,$ and in which a reduced word $a$ is joined by an edge to each of the words obtained from $a$ by either interchanging two consecutive terms $i,j$ such that $|i-j|>1,$ or by replacing three consecutive terms $i,j,i$ such that $|i-j|=1$ by $j,i,j\text{.}$ Then the proof of (2.5) shows that

(2.5') The graph $GR\left(w\right)$ is connected.

From (2.5) it follows that we may define

$${\partial }_w={\partial }_a$$

unambiguously, where $a$ is any reduced word for w. By (2.2'), the operators ${\partial }_w$ for $w\in S_n$ are ${\Lambda }_n$ linear, where

$${\Lambda }_n=\mathbb{Z}{[x_1,\dots ,x_n]}^{S_n}\subset P_n$$

is the ring of symmetric polynomials in $x_1,\dots ,x_n\text{.}$

A sequence $a=(a_1,\dots ,a_p)$ will be said to be reduced if $a\in R\left(w\right)$ for some permutation $w\text{.}$

(2.6) If $a=(a_1,\dots ,a_p)$ is not reduced, then ${\partial }_a=0\text{.}$

		Proof.
	By induction on $p\text{.}$ If $a\prime =(a_1,\dots ,a_{p-1})$ is not reduced, then ${\partial }_{a\prime }=0$ and hence ${\partial }_a={\partial }_{a\prime }{\partial }_{a_p}=0\text{.}$ So we may assume that $a\prime$ is reduced. Let $v=s_{a_1}\dots s_{a_{p-1}},$ $w=s_{a_1}\dots s_{a_p}\text{.}$ We have $\ell \left(v\right)=p-1$ and $\ell \left(w\right)\le p-1,$ hence by (1.3) $\ell \left(w\right)=p-2,$ so that $\ell \left(v\right)=\ell \left(w{s}_{a_p}\right)=\ell \left(w\right)+1\text{.}$ Consequently ${\partial }_v={\partial }_w{\partial }_{a_p}$ and therefore ${\partial }_a={\partial }_v{\partial }_{a_p}={\partial }_w{\partial }_{a_p}^2=0\text{.}$ $\square$

(2.7) Let $u,v$ be permutations. Then

$${\partial }_u{\partial }_v=\{\begin{array}{cc}{\partial }_{uv}& \text{if}\hspace{0.17em}\ell \left(uv\right)=\ell \left(u\right)+\ell \left(v\right),\\ 0& \text{otherwise.}\end{array}$$

		Proof.
	(2.5), (2.6). $\square$

(2.8) Let $w$ be a permutation, $i\ge 1\text{.}$ Then

$$s_i{\partial }_w={\partial }_w⟺\ell \left(s_{i}w\right)=\ell \left(w\right)-1\text{.}$$

		Proof.
	We have $s_i{\partial }_w={\partial }_w⟺{\partial }_i{\partial }_w=0,$ hence the result follows from (2.7). $\square$

As before let $w_0=(n,n-1,\dots ,2,1)$ be the longest element of $S_n\text{.}$ One element of $R\left(w_0\right)$ is the sequence

$$\begin{array}{cc}\text{(2.9)}& (1,2,\dots ,n-1,1,2,\dots ,n-2,\dots ,1,2,3,1,2,1)\text{.}\end{array}$$

(2.10) We have

$${\partial }_{w_0}=a_{\delta }^{-1}\sum _{w\in S_n}\epsilon \left(w\right)w$$

where $a_{\partial }=\prod _{1\le i<j\le n}(x_i-x_j),$ and $\epsilon \left(w\right)=\pm 1$ is the sign of $w\text{.}$

		Proof.
	From the definition it follows that ${\partial }_{w_0}$ is of the form $$\begin{array}{cc}\text{(1)}& {\partial }_{w_0}=\sum _{w\in S_n}{c}_{w}w\end{array}$$ with coefficients $c_w$ rational functions of $x_1,\dots ,x_n\text{.}$ By (2.8) we have $s_i{\partial }_{w_0}={\partial }_{w_0}$ for $1\le i\le n-1,$ so that $v{\partial }_{w_0}={\partial }_{w_0}$ for all $v\in S_n,$ and therefore $$\begin{array}{cc}\text{(2)}& {\partial }_{w_0}=\sum _{w\in S_n}v\left(c_w\right)vw\text{.}\end{array}$$ Comparison of (1) and (2) shows that $$\begin{array}{cc}\text{(3)}& c_{vw}=v\left(c_w\right)(v,w\in S_n)\text{.}\end{array}$$ Hence all the coefficients $c_w$ are determined by one of them, say $c_{w_0}\text{.}$ From the sequence (2.9) for $w_0$ it is easily checked that the coefficient of $w_0$ in ${\partial }_0$ is $$c_{w_0}=\epsilon \left(w_0\right)a_{\delta }^{-1}\text{.}$$ Hence from (3) we have $$c_w=w{w}_0\left(c_{w_0}\right)=\epsilon \left(w\right)a_{\delta }^{-1}$$ which proves (2.10). $\square$

From (2.10) it follows that, for any $\alpha =({\alpha }_1,\dots ,{\alpha }_n)\in {\mathbb{N}}^n,$

$$\begin{array}{cc}\text{(2.11)}& {\partial }_{w_0}{x}^{\alpha }=s_{\alpha -\delta }(x_1,\dots ,x_n)\end{array}$$

where $x^{\alpha }$ means $x_1^{{\alpha }_1}\dots x_n^{{\alpha }_n},$ $\delta =(n-1,n-2,\dots ,1,0)$ and $s_{\alpha -\delta }$ is the Schur function indexed by $\alpha -\delta \text{.}$ Thus ${\partial }_{w_0}$ is a ${\Lambda }_n\text{-linear}$ mapping of $P_n$ onto ${\Lambda }_n\text{.}$

For $w\in S_n,$ let $\bar{w}=w_{0}w{w}_0\text{.}$ Then

$$\begin{array}{cc}\text{(2.12)}& {\partial }_{\bar{w}}=\epsilon \left(w\right)w_0{\partial }_w{w}_0\text{.}\end{array}$$

		Proof.
	From the definition of ${\partial }_i$ we have $$w_0{\partial }_i{w}_0=-{\partial }_{n-i}$$ from which (2.12) follows easily, since $w_0^2=1\text{.}$ $\square$

If $f$ and $g$ are polynomials in $x_1,x_2,\dots ,$ the expression of ${\partial }_w\left(fg\right)$ as a sum of polynomials ${\partial }_{u}f·{\partial }_{v}g$ (i.e. the "Leibnitz formula" for ${\partial }_w\text{)}$ is in general rather complicated. However, there is one case in which it is reasonably simple, namely when one of the factors $f,g$ is linear:

(2.13) If $f=\sum {\alpha }_i{x}_i$ then

$${\partial }_w\left(fg\right)=w\left(f\right){\partial }_{w}g+\sum ({\alpha }_i-{\alpha }_j){\partial }_{w{t}_{ij}}g$$

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

		Proof.
	Let $(a_1,\dots ,a_p)$ be a reduced word for $w\text{.}$ Since $f$ is linear it follows from (2.2) that $$\begin{array}{ccc}{\partial }_w\left(fg\right)& =& {\partial }_{a_1}\dots {\partial }_{a_p}\left(fg\right)\\ & =& s_{a_1}\dots s_{a_p}\left(f\right){\partial }_{a_1}\dots {\partial }_{a_p}g+\sum _{r=1}^p{s}_{a_1}\dots {\partial }_{a_r}\dots s_{a_p}\left(f\right){\partial }_{a_1}\dots {\hat{\partial }}_{a_r}\dots {\partial }_{a_p}g\text{.}\end{array}$$ Now ${\partial }_{a_1}\dots {\hat{\partial }}_{a_r}\dots {\partial }_{a_p}=0$ unless $(a_1,\dots ,{\hat{a}}_r,\dots ,a_p)$ is reduced, and then by (1.11) it is equal to ${\partial }_{wt},$ where $wt=s_{a_p}\dots {\hat{s}}_{a_r}\dots s_{a_p}$ has length $p-1=\ell \left(w\right)-1,$ and $t=s_{a_p}\dots s_{a_r}\dots s_{a_p}=t_{ij}$ where $(i,j)=s_{a_p}\dots s_{a_{r+1}}(a_r,a_{r+1}),$ so that $$s_{a_1}\dots s_{a_{r-1}}{\partial }_{a_r}{s}_{a_{r+1}}\dots s_{a_p}\left(f\right)={\alpha }_i-{\alpha }_j\text{.}$$ $\square$

We also introduce the operators ${\pi }_i(i\ge 1)$ defined by

$${\pi }_{i}f={\partial }_i\left(x_{i}f\right)\text{.}$$

In place of (2.4) we have

$$\begin{array}{cc}\text{(2.14)}& \{\begin{array}{cc}{\pi }_i^2={\pi }_i,& \\ {\pi }_i{\pi }_j={\pi }_j{\pi }_i& \text{if}\hspace{0.17em}|i-j|>1,\\ {\pi }_i{\pi }_{i+1}{\pi }_i={\pi }_{i+1}{\pi }_i{\pi }_{i+1}\text{.}& \end{array}\end{array}$$

If we define ${\pi }_a$ to be ${\pi }_{a_1}\dots {\pi }_{a_p}$ for any sequence $a=(a_1,\dots ,a_p)$ of positive integers, then corresponding to (2.5) we have

(2.15) If $a,b\in R\left(w\right)$ then ${\pi }_a={\pi }_b\text{.}$

The proof is the same as that of (2.5), and rests only on the second and third of the relations (2.14). From (2.15) it follows that we may define

$${\pi }_w={\pi }_a$$

unambiguously, where $a$ is any reduced word for $w\text{.}$

In place of (2.10) we have

(2.16) For any $f\in P_n,$

$${\pi }_{w_0}f=a_{\delta }^{-1}\sum _{w\in S_n}\epsilon \left(w\right)w\left(x^{\delta }f\right)={\partial }_{w_0}\left(x^{\delta }f\right)\text{.}$$

In particular, if $\alpha \in {\mathbb{N}}^n,$

$$\begin{array}{cc}\text{(2.16')}& {\pi }_{w_0}{x}^{\alpha }=s_{\alpha }(x_1,\dots ,x_n)\text{.}\end{array}$$

		Proof.
	We have $$\begin{array}{c}{\pi }_{1}f={\partial }_1\left(x_{1}f\right),\\ {\pi }_1{\pi }_{2}f={\partial }_1\left(x_1{\partial }_2\left(x_{2}f\right)\right)={\partial }_1{\partial }_2\left(x_1{x}_{2}f\right)\end{array}$$ and generally $${\pi }_1\dots {\pi }_{r}f={\partial }_1\dots {\partial }_r\left(x_1\dots x_{r}f\right)$$ for each $r\ge 1\text{.}$ From this and (2.10) it follows easily that ${\pi }_{w_0}f={\partial }_{w_0}\left(x^{\delta }f\right)\text{.}$ $\square$

Let $(a_1,\dots ,a_p)$ be a reduced word for $w\text{.}$ Then

$$\begin{array}{ccc}{\partial }_w& =& {\partial }_{a_1}\dots {\partial }_{a_p}\\ & =& {(x_{a_1}-x_{a_1+1})}^{-1}(1-s_{a_1}){(x_{a_2}-x_{a_2+1})}^{-1}(1-s_{a_2})\dots \end{array}$$

which shows on expansion that ${\partial }_w$ is of the form

$${\partial }_w=\sum _{v\le w}{f}_{vw}v$$

where $f_{vw}$ are rational functions of $x_1,x_2,\dots ,$ and in particular (by (1.7))

$$f_{ww}={(-1)}^p\prod _{(i,j)\in I\left(w^{-1}\right)}{(x_i-x_j)}^{-1}$$

and thus is $\ne 0\text{.}$ It follows that the ${\partial }_w$ are linearly independent over the field of rational functions ${\mathbb{Q}}_{\infty }=\mathbb{Q}(x_1,x_2,\dots )\text{.}$

Now from (2.2) we have

$${\partial }_a\left(fg\right)=\left({\partial }_{a}f\right)g+\left(s_{a}f\right)\left({\partial }_{a}g\right)$$

or equivalently, if $\mu :P_{\infty }\otimes P_{\infty }\to P_{\infty }$ is the multiplication map,

$${\partial }_a\circ \mu =\mu \circ ({\partial }_a\otimes 1+s_a\otimes {\partial }_a)\text{.}$$

From this it follows that

$${\partial }_w\circ \mu =\mu \circ ({\partial }_{a_1}\otimes 1+s_{a_1}\otimes {\partial }_{a_1})\circ \dots \circ ({\partial }_{a_p}\otimes 1+s_{a_p}\otimes {\partial }_{a_p})$$

On expansion this is a sum over subsequences $b$ of $a=(a_1,\dots ,a_p),$ say

$$\begin{array}{cc}\text{(1)}& {\partial }_w\circ \mu =\mu \circ \sum _{b\subset a}\varphi (a,b)\otimes {\partial }_b\end{array}$$

where

$$\varphi (a,b)={\varphi }_1(a,b)\circ \dots \circ {\varphi }_p(a,b)$$

and

$${\varphi }_i(a,b)=\{\begin{array}{cc}{s}_{a_1}& \text{if}\hspace{0.17em}{a}_i\in b,\\ {\partial }_{a_1}& \text{if}\hspace{0.17em}{a}_i\notin b\text{.}\end{array}$$

Since ${\partial }_b=0$ if $b$ is not reduced (2.6), the sum is over reduced subsequences $b$ of $a,$ and by (1.17) we can write

$$\begin{array}{cc}\text{(2)}& {\partial }_w\circ \mu =\mu \circ \sum _{v\le w}v{\partial }_{w/v}\otimes {\partial }_v\end{array}$$

where for $v\le w$

$$\begin{array}{cc}\text{(3)}& {\partial }_{w/v}=v^{-1}\sum \varphi (a,b)\end{array}$$

summed over subsequences $b\subset a$ such that $b$ is a reduced word for $v\text{.}$

So for each pair of permutations $w,v$ such that $w\ge v$ we have a well-defined operator ${\partial }_{w/v}$ on $P_{\infty },$ defined by (3). Since the ${\partial }_v$ are linearly independent, the definition (3) is independent of the reduced word $a\in R\left(w\right)\text{.}$

(2.17) For each pair $w,v\in S_{\infty }$ such that $w\ge v$ there is a linear operator ${\partial }_{w/v}$ on $P_{\infty }$ such that

$${\partial }_w\left(fg\right)=\sum _{v\le w}v\left({\partial }_{w/v}f\right)·{\partial }_{v}g\text{.}$$

${\partial }_{w/v}$ has degree $-\ell \left(w\right)+\ell \left(v\right)\text{.}$

Examples

1.	Let $v=w,$ then $${\partial }_{w/w}=w^{-1}\varphi (a,a)=w^{-1}{s}_{a_1}\dots s_{a_p}=1\text{.}$$
2.	Let $v=1,$ then $${\partial }_{w/1}=\varphi (a,\varnothing )={\partial }_{a_1}\dots {\partial }_{a_p}={\partial }_w\text{.}$$
3.	Suppose that $v\to w,$ so that $v=s_{a_1}\dots {ŝ}_{a_r}\dots s_{a_p}$ for an unique $r\in [1,p]\text{.}$ Then $b=(a_1,\dots ,{\hat{a}}_r,\dots ,a_p)$ and $$\begin{array}{ccc}{\partial }_{w/v}& =& v^{-1}\varphi (a,b)\\ & =& v^{-1}{s}_{a_1}\dots s_{a_{r-1}}{\partial }_{a_r}{s}_{a_{r+1}}\dots s_{a_p}\\ & =& s_{a_p}\dots s_{a_{r+1}}{\partial }_{a_r}{s}_{a_{r+1}}\dots s_{a_p}\end{array}$$ Now $w=vt$ where $t$ is the transposition $$t=t_{ij}=s_{a_p}\dots s_{a_r}\dots s_{a_p}(i<j)$$ so that $(i,j)=s_{a_p}\dots s_{a_{r+1}}(a_r,a_r+1)$ and therefore $$\begin{array}{ccc}{\partial }_{w/v}& =& s_{a_p}\dots s_{a_{r+1}}{(x_{a_r}-x_{a_r+1})}^{-1}(1-s_{a_r})s_{a_{r+1}}\dots s_{a_p}\\ & =& {(x_i-x_j)}^{-1}(1-t_{ij})\end{array}$$ is the divided difference operator ${\partial }_{x_i,x_j}\text{.}$ The product formula for ${\partial }_{w/u}$ is $$\begin{array}{cc}\text{(2.18)}& {\partial }_{w/u}\left(fg\right)=\sum _{u\le v\le w}{u}^{-1}v\left({\partial }_{w/v}f\right){\partial }_{w/u}g\text{.}\end{array}$$ Proof. We have $$\begin{array}{cc}{\partial }_w\left(fgh\right)=\sum _{u\le w}u{\partial }_{w/u}\left(fg\right){\partial }_{u}h& \text{(1)}\end{array}$$ and on the other hand $$\begin{array}{ccc}{\partial }_w\left(fgh\right)& =& \sum _{u\le w}v{\partial }_{w/u}\left(f\right){\partial }_v\left(gh\right)\\ & =& \sum _{u\le v\le w}v{\partial }_{w/v}\left(f\right)·u{\partial }_{v/u}\left(g\right)·{\partial }_{u}h\text{.}\end{array}$$ Comparison of (1) and (2) gives $$u{\partial }_{w/u}\left(fg\right)=\sum _{u\le v\le w}v{\partial }_{w/u}\left(f\right)·u{\partial }_{v/u}\left(g\right)$$ which gives the result. $\square$ When $u=1,$ this reduces to (2.17).

Notes and References

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

page history