Notes on Schubert Polynomials
Appendix

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

Last update: 2 July 2013

A Combinatorial Construction of the Schubert Polynomials

by Nantel Bergeron

In this appendix, we shall give a combinatorial rule based on diagrams for the construction of the Schubert polynomials. A different algorithm had been conjectured (and proved in the case of vexillary permutations) by A. Kohnert. We shall give, at the end of this appendix, a sketch of how one can show the equivalence of the two rules. I wish to acknowledge my indebtedness to Mark Shimozono for the stimulating exchanges regarding this work.

Combinatorial construction

Here a "diagram" will be any finite non empty set of lattice points $(i,j)$ in the positive quadrant $(i\ge 1,j\ge 1)\text{.}$ For example the diagram $D\left(w\right)$ of a permutation $w$ is a diagram in the above sense. Let $D$ be any diagram. We denote by $D_{(r,r+1)}$ the diagram $D$ restricted to the row $r$ and $r+1\text{.}$ Let $j(r,D)=(j_1,j_2,\dots ,j_k)$ be the columns of $D$ in which there is exactly one element of $D_{(r,r+1)}$ per column. Choose a column $j_i\in j(r,D)\text{.}$ Assume first that $(r+1,j_i)\in D_{(r,r+1)}\text{.}$ If $i=k$ or if $(r,j_{i+1})\in D_{(r,r+1)},$ let $D_1$ be the diagram obtained from $D$ by replacing the element $(r+1,j_i)$ by $(r,j_i)\text{.}$ Now suppose instead that $(r,j_i)\in D_{(r,r+1)}\text{.}$ We say that the point $(r,j_i)$ is $r\text{-fixed}$ with respect to $D\left(w\right)$ if the number of elements of $D$ in the column $j_i$ and in the rows $r\prime >r$ is equal to the number of elements of $D\left(w\right)$ in the same area. Now if $i=1$ (and if there is no r-fixed element with respect to $D\left(w\right)$ in $D\text{)}$ or if $(r+1,j_{i-1})\in D_{(r,r+1)},$ let $D_1$ be the diagram obtained from $D$ by replacing the element $(r,j_i)$ by $(r+1,j_i)\text{.}$ In both cases we say that the diagram $D_1$ is obtained from $D$ by a $\text{"}B\text{-move}\text{"}$ (with respect to $D\left(w\right)\text{).}$ For example let $D$ be such that $D_{(r,r+1)}$ is the following:

$$1 2 3 4 5 6 7 8 9 r r+1$$

For this case $j(r,D)=(2,5,8,9)\text{.}$ We can perform on this diagram a B-move in column 2, 5 or 9 and obtain, respectively, the following diagrams:

$$\begin{array}{ccc} & & \end{array}$$

The element in column 8 is not allowed to move since $(r+1,5)\notin D_{(r,r+1)}\text{.}$ Let $\Omega \left(w\right)$ denote the set of all diagrams (including $D\left(w\right)\text{)}$ obtainable from $D\left(w\right)$ by any sequence of B-moves.

Next for $D\in \Omega \left(w\right)$ let $x^D$ denote the monomial $x_1^{a_1}{x}_2^{a_2}{x}_3^{a_3}\dots$ where $a_i$ is the number of elements of $D$ in the $i^{\text{th}}$ row. For any permutation $w$ we shall have the following theorem:

$$\begin{array}{cc}\text{(B.1)}& {𝔖}_w=\sum _{D\in \Omega \left(w\right)}{x}^D\text{.}\end{array}$$

To prove this we will proceed by reverse induction on $\ell \left(w\right)\text{.}$ If $w=w_0$ (the longest element of $S_n\text{)}$ then (B.1) holds since $\Omega \left(w_0\right)$ contains only the element $D\left(w_0\right)$ and $x^{D\left(w_0\right)}=x^{\delta }\text{.}$ On the other hand from (4.3), ${𝔖}_{w_0}=x^{\delta }\text{.}$ Now if $w\ne w_0$ then let $r=\text{min}\{i:w\left(i\right)<w(i+1)\}\text{.}$ From (4.2) we have

$$\begin{array}{cc}\text{(B.2)}& {𝔖}_w={\partial }_r{𝔖}_{w{s}_r}\text{.}\end{array}$$

Let $v=w{s}_r\text{.}$ By the induction hypothesis equation (B.1) holds for ${𝔖}_v\text{.}$ The induction step will be to "apply" the operator ${\partial }_r$ to the diagrams in $\Omega \left(v\right)\text{.}$ To this end we need more tools.

For the moment let us fix $D\in \Omega \left(v\right)\text{.}$ Let $a=a_r\left(D\right)$ and $b=a_{r+1}\left(D\right)$ be respectively the number of elements of $D$ in the $r\text{th}$ and $r+1\text{st}$ rows. We have

$$\begin{array}{cc}\text{(B.3)}& {\partial }_r{x}^D={\partial }_r\dots x_r^a{x}_{r+1}^b\dots =\{\begin{array}{cc}{\sum }_{k=0}^{a-b-1}\dots x_r^{a-r-1}{x}_{r+1}^{b+r}\dots & \text{if}\hspace{0.17em}a>b,\\ 0& \text{if}\hspace{0.17em}a=b,\\ -{\sum }_{k=0}^{a-b-1}\dots x_r^{a+r}{x}_{r+1}^{b-r-1}\dots & \text{if}\hspace{0.17em}a<b\text{.}\end{array}\end{array}$$

This suggests we define the operator ${\partial }_r$ directly on the diagram $D\text{.}$ For this we need only to concentrate our attention on the rows $r$ and $r+1$ of $D\text{.}$ Let $j(r,D)=(j_1,j_2,\dots ,j_p)\text{.}$ Notice that in all columns $j<w\left(r\right)$ of $D_{(r,r+1)}$ there are exactly two elements and in column $w\left(r\right)=j_1$ of $D_{(r,r+1)}$ there is exactly one element in position $(r,j_1)\text{.}$ We shall now reduce the sequence of indices $j(r,D)$ according to the following rule. Let $J_{\left(0\right)}=(j_2,j_3,\dots ,j_p)\text{.}$ Remove from $J_{\left(0\right)}$ all pairs $j_k,j_{k+1}$ for which $(r,j_k)\in D$ and $(r+1,j_{k+1})\in D\text{.}$ Let us denote the resulting sequence by $J_{\left(1\right)}\text{.}$ Repeat recursively this process on $J_{\left(1\right)}$ until no such pair can be found. Let us denote by $f(r,D)=(f_1,f_2,\dots ,f_q)$ the final sequence. From construction, the sequence $f(r,D)$ is such that if $(r,f_k)\in D$ then $(r,f_{k+1})\in D\text{.}$ Let $\text{up}(r,D)$ be the minimal $k$ such that $(r,f_k)\in D\text{.}$ If $(r+1,f_q)\in D$ then set $\text{up}(r,D)=q+1\text{.}$ We are now in a position to define the operation of ${\partial }_r$ on the diagram $D\text{.}$ To this end let us first assume that $a>b\text{.}$ This means that we have $a-b$ more elements. in row $r$ then in row $r+1\text{.}$ Hence $q-\text{up}(r,D)+1\ge a-b-1$ for $q$ the length of $f(r,D)\text{.}$ The equality holds if and only if $\text{up}(r,D)=1\text{.}$ In the case $a>b$ the operator ${\partial }_r$ on the diagram $D$ is defined by the map

$$\begin{array}{cc}\text{(B.4a)}& {\partial }_{r}D\to \{D_0,D_1,D_2,\dots ,D_{a-b-1}\}\end{array}$$

where $D_0$ is identical to $D$ except that we remove the element in position $(r,w\left(r\right))$ and for $k=1,2,\dots ,a-b-1$ we successively set $D_k$ to be identical to $D_{k-1}$ except that the element $(r,f_{\text{up}(r,D)+k-1})$ is replaced by $(r+1,f_{\text{up}(r,D)+k-1})\text{.}$ Now if $a<b$ we have $\text{up}(r,D)-1\ge b-a+1$ (with equality iff $\text{up}(r,D)=q+1\text{).}$ So $\text{up}(r,D)-1>b-a\text{.}$ In this case the operator ${\partial }_r$ on the diagram $D$ is defined by the map

$$\begin{array}{cc}\text{(B.4b)}& {\partial }_{r}D\to \{D_0,D_1,D_2,\dots ,D_{b-a-1}\}\end{array}$$

where $D_0$ is identical to $D$ except that we remove the element in position $(r,w_r)$ and the element $(r+1,f_{\text{up}(r,D)-1})$ is replaced by $(r,f_{\text{up}(r,D)-1})\text{.}$ For $k=1,2,\dots ,b-a-1$ we successively set $D_k$ to be identical to $D_{k-1}$ except that the element $(r+1,f_{\text{up}(r,D)-k-1})$ is replaced by $(r,f_{\text{up}(r,D)-k-1})\text{.}$ Finally if $a=b$ then

$$\begin{array}{cc}\text{(B.4c)}& {\partial }_{r}D\to \left\{\right\}\text{.}\end{array}$$

With this definition of ${\partial }_r$ we have that

$$\begin{array}{cc}\text{(B.5)}& {\partial }_r{x}^D=\pm \sum _{D_i\in {\partial }_{r}D}{x}^{D_i},\end{array}$$

with the positive sign in case (B.4a), and the negative sign in case (B.4b). For (B.4c) the result of (B.5) is zero.

We shall now show that

$$\begin{array}{cc}\text{(B.6)}& {\partial }_r\hspace{0.17em}\text{maps}\hspace{0.17em}\Omega \left(v\right)\hspace{0.17em}\text{into}\hspace{0.17em}\Omega \left(w\right)\text{.}\end{array}$$

		Proof.
	The reader will notice that in $D\left(v\right)$ the rectangle defined by the rows $1,2,\dots ,r+1$ and the columns $1,2,\dots ,w\left(r\right)-1$ is filled with elements. None of these elements can B-move. Hence these elements are fixed in any diagram $D\in \Omega \left(v\right)\text{.}$ The same applies to all elements in column $w\left(r\right)\text{;}$ they are packed in the smallest rows and there are no elements in the rows strictly greater than $r\text{.}$ Now let $D$ be a diagram in $\Omega \left(v\right)$ and assume that ${\partial }_{r}D=\{D_0,D_1,\dots ,D_m\}$ is non-empty. The remark above implies that the element in position $(r,w\left(r\right))$ does not affect the sequence of B-moves from $D\left(v\right)$ to $D\text{.}$ Hence we can apply the same sequence of B-moves to $D\left(v\right)-\left\{(r,w\left(r\right))\right\}$ and obtain $D_0\text{.}$ Moreover $D\left(v\right)-\left\{(r,w\left(r\right))\right\}$ is obtainable from $D\left(w\right)$ by a simple sequence of B-moves in rows $r,r+1,$ for this one successively B-moves all the elements in row $r+1$ and columns given by $j(r,D\left(w\right))\text{.}$ This gives that $D_0$ is obtainable from $D\left(w\right)$ by a sequence of B-moves, that is $D_0\in \Omega \left(w\right)\text{.}$ Now from the construction of ${\partial }_{r}D,$ $D_k$ $(k>0)$ is obtained from $D_{k-1}$ by exactly one B-move. Hence ${\partial }_{r}D\subset \Omega \left(w\right)\text{.}$ $\square$

It is appropriate at this point to give an example. Let $w=(6,3,9,5,1,2,11,8,4,7,10)\text{.}$ Hence $r=2$ and $v=(6,9,3,5,1,2,11,8,4,7,10)\text{.}$ We have depicted below the diagrams $D\left(w\right)$ and $D\left(v\right)\text{.}$ In our example the fixed elements described above are colored in grey and the element in position $(r,w\left(r\right))$ is colored black.

$$\begin{array}{cc} 1 2 3 4 5 6 7 8 9 10 11 1 2 3 4 5 6 7 8 9 10 11 & 1 2 3 4 5 6 7 8 9 10 11 1 2 3 4 5 6 7 8 9 10 11 \\ D\left(w\right)& D\left(v\right)\end{array}$$

Now let $D$ be the following diagram of $\Omega \left(v\right)\text{.}$

$$D=\begin{array}{c} \end{array}$$

Here, $a_r\left(D\right)=7,$ $a_{r+1}\left(D\right)=4$ and $j(r,D)=(3,5,7,8,10)\text{.}$ The reduced sequence $f(r,D)$ is $(8,10)$ and $\text{up}(r,D)=1\text{.}$ Hence ${\partial }_{r}D=\{D_0,D_1,D_2\}$ where

$$\begin{array}{ccc} & & \\ D_0& D_1& D_2\end{array}$$

To prove (B.1) the first step is to find a subset of $\Omega \left(v\right)$ such that when we operate with ${\partial }_r$ we obtain $\Omega \left(w\right)\text{.}$ To this end let

$${\Omega }_0\left(v\right)=\{D\in \Omega \left(v\right):a_r\left(D\right)>a_{r+1}\left(D\right)\hspace{0.17em}\text{and}\hspace{0.17em}\text{up}(r,D)=1\}\text{.}$$

We have

$$\begin{array}{cc}\text{(B.7)}& \Omega \left(w\right)=\bigcup _{D\in {\Omega }_0\left(v\right)}{\partial }_{r}D\text{(disjoint union).}\end{array}$$

		Proof.
	It is clear from construction that the subsets ${\partial }_{r}D$ are disjoint when $D\in {\Omega }_0\left(v\right)\text{.}$ From (B.6) we only have to prove that for any $D\prime \in \Omega \left(w\right)$ there is a $D\in {\Omega }_0\left(v\right)$ such that $D\prime \in {\partial }_{r}D\text{.}$ To see that, reduce the sequence $j(r,D\prime )=(j_1,\dots ,j_p)$ by removing recursively all pairs $j_k,j_{k+1}$ for which $(r,j_k)\in D\prime$ and $(r+1,j_{k+1})\in D\prime \text{.}$ Denote the final sequence by $f\prime (r,D\prime )\text{.}$ Let $D$ be the bubble diagram obtained from $D\prime$ by adding an element in position $(r,w\left(r\right))$ and successively B-moving all elements in positions $(r+1,f_i)\in D\prime \text{.}$ We have that $D\in \Omega \left(v\right)\text{.}$ To see this one applies to $D\left(v\right)$ the sequence of B-moves from $D\left(w\right)$ to $D-\left\{(r,w\left(r\right))\right\}\text{.}$ Of course one should ignore any B-move in rows $r,r+1$ performed on the original elements of $D\left(v\right)$ in row $r\text{.}$ But by the choice of $r,$ the other B-moves apply almost directly and the resulting diagram is precisely $D\text{.}$ Moreover since $f(r,D)=f\prime (r,D\prime )$ and $\text{up}(r,D)=1$ we have $D\in {\Omega }_0\left(v\right)$ and $D\prime \in {\partial }_{r}D\text{.}$ $\square$

We shall now investigate the effect of ${\partial }_r$ on ${\Omega }_1\left(v\right)=\Omega \left(v\right)-{\Omega }_0\left(v\right)\text{.}$ More precisely we have

$$\begin{array}{cc}\text{(B.8)}& \sum _{D\in {\Omega }_1\left(v\right)}{\partial }_r{x}^D=0\text{.}\end{array}$$

		Proof.
	There are two classes of diagrams in ${\Omega }_1\left(v\right)\text{.}$ The first class contains the diagrams $D$ for which $a_r\left(D\right)=a_{r+1}\left(D\right)\text{.}$ In this case it is trivial that ${\partial }_r{x}^D=0\text{.}$ The other class is formed by the diagrams $D$ such that $a_r\left(D\right)\ne a_{r+1}\left(D\right)$ and $\text{up}(r,D)>1\text{.}$ In this case we shall construct an involution, $D\to D\prime ,$ such that ${\partial }_r{x}^D+{\partial }_r{x}^{D\prime }=0\text{.}$ Let $f(r,D)=(f_1,f_2,\dots ,f_q),$ $a=a_r\left(D\right)$ and $b=a_{r+1}\left(D\right)\text{.}$ We first define the involution for the case $a>b\text{.}$ Since $\text{up}(r,D)>1$ we must have $q-\text{up}(r,D)+1\ge a-b\text{.}$ So let $D\prime$ be identical to $D$ except that the elements in positions $(r,f_{\text{up}(r,D)}),(f,f_{\text{up}(r,D)+1}),\dots ,(r,f_{\text{up}(r,D)+a-b-1})$ are B-moved to the positions $(r+1,f_{\text{up}(r,D)}),(r+1,f_{\text{up}(r,D)+1}),\dots ,(r,f_{\text{up}(r,D)+a-b-1})\text{.}$ It is clear that $D\prime \in \Omega \left(v\right)\text{.}$ But $f(r,D\prime )=f(r,D)$ and $\text{up}(r,D\prime )>\text{up}(r,D)>1,$ hence $D\prime \in {\Omega }_1\left(v\right)\text{.}$ Moreover we have $a_r\left(D\right)=b$ and $a_{r+1}\left(D\right)=a,$ hence ${\partial }_r{x}^D+{\partial }_r{x}^{D\prime }=0\text{.}$ The case $a<b$ is similar to the previous one. $\square$

A proof of (B.1) is now completed combining (B.2), (B.5), (B.7) and (B.8). More precisely using the induction hypothesis, we have

$$\begin{array}{cccc}{𝔖}_w& =& {\partial }_r{𝔖}_v& \text{(B.2)}\\ & =& \sum _{D\in \Omega \left(v\right)}{\partial }_r{x}^D\\ & =& \sum _{D\in {\Omega }_0\left(v\right)}{\partial }_r{x}^D& \text{(B.8)}\\ & =& \sum _{D\in {\Omega }_0\left(v\right)}\sum _{D_i\in {\partial }_{r}D}{x}^{D_i}& \text{(B.5)}\\ & =& \sum _{D\prime \in \Omega \left(w\right)}{x}^{D\prime }\text{.}& \text{(B.7)}\end{array}$$

Kohnert's construction

Let $D$ be any diagram. Choose $(i,j)\in D$ such that $(i,j\prime )\notin D$ for all $j\prime <j\text{.}$ Let us suppose that there is a point $(i\prime ,j)\notin D$ with $i\prime <i\text{.}$ Then let $h<i$ be the largest integer such that $(h,j)\notin D$ and let $D_1$ denote the diagram obtained from $D$ by replacing $(i,j)$ by $(h,j)\text{.}$ We say that $D_1$ is obtained from $D$ by a "K-move". Now let $K\left(D\left(w\right)\right)$ denote the set of all diagrams (including $D$ itself) obtainable from $D$ by any sequence of K-moves. Kohnert's conjecture states that for any permutation $w$ we have

$$\begin{array}{cc}\text{(B.9)}& {𝔖}_w=\sum _{D\in K\left(D\left(w\right)\right)}{x}^D\text{.}\end{array}$$

A. Kohnert has proved (B.9) for the case where $w$ is a vexillary permutation but the general case was still open. For the interested reader here is a sketch of how one may prove (B.9).

We have noticed by computer that $\Omega \left(w\right)=K\left(D\left(w\right)\right)\text{.}$ The idea then is to show both inclusions by induction. The inclusion $K\left(D\left(w\right)\right)\subset \Omega \left(w\right)$ is the easiest one. We only have to show that any K-move of an element $(i,j)$ to $(h,j)$ can be simulated using B-moves. For this we proceed by induction on $i-h\text{.}$ If $i-h=1$ then the K-move is simply one B-move. Now if $i-h>1,$ we first perform the sequence of B-moves in row $h,h+1$ necessary to B-move the element $(h+1,j)$ to $(h,j)\text{.}$ Then using the induction hypothesis we can K-move $(i,j)$ to $(h+1,j)\text{.}$ Finally we reverse the first sequence of B-moves in rows $h,h+1\text{.}$ That shows $K\left(D\left(w\right)\right)\subset \Omega \left(w\right)\text{.}$

The other inclusion needs a lot more work. For $D\in K\left(D\left(w\right)\right)$ and $i$ any row of $D$ let $B_i\left(D\right)$ denote the set of all diagrams (including $D\text{)}$ obtainable from $D$ by any sequence of B-moves in the rows $i,i+1$ only. It is clear that if $i$ is big enough then $B_i\left(D\right)\subset K\left(D\left(w\right)\right)\text{.}$ We may then proceed by reverse induction on $i\text{.}$ Now for a fixed $i,$ notice that $B_i\left(D\left(w\right)\right)$ is obtainable from $D\left(w\right)$ using only K-moves. Let ${\Omega }_0$ denote the set of all diagrams obtainable from $B_i\left(D\left(w\right)\right)$ by any sequence of K-moves for which no elements crosses the border between the rows $i+1$ and $i+2\text{.}$ A simple inductive algorithm may be used here to show that for any $D\in {\Omega }_0$ we have $B_i\left(D\right)\subset {\Omega }_0\text{.}$ Next let ${\Omega }_k$ denote the set of all diagrams of $K\left(D\left(w\right)\right)$ which have $k$ more elements than $D\left(w\right)$ in the rows $1,2,\dots ,i+1\text{.}$ For almost all the cases it is fairly easy to show (using induction on $k$ and the induction hypothesis on $i\text{)}$ that for $D\in {\Omega }_k$ we have $B_i\left(D\right)\subset {\Omega }_k\text{.}$ But some of the cases are really hard to formalize! Now this completed would show that $\Omega \left(w\right)\subset K\left(D\left(w\right)\right)$ since $K\left(D\left(w\right)\right)=\cup {\Omega }_k\text{.}$

Notes and References

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

page history