Notes on Schubert Polynomials
Chapter 7

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

Last update: 2 July 2013

Schubert Polynomials (2)

Recall the decomposition (4.17) of a Schubert polynomial ${𝔖}_w\text{:}$

$${𝔖}_w(x_1,x_2,\dots )=\sum _{u,v}{d}_{uv}^w{𝔖}_u(x_1,\dots ,x_m){𝔖}_v(x_{m+1},x_{m+2},\dots )$$

Our first aim in this Chapter will be to give a method for calculating the coefficients $d_{uv}^w\text{.}$ We shall then apply our results to the calculation of $\text{Card}\hspace{0.17em}\left(R\left(w\right)\right),$ the number of reduced decompositions $w=s_{a_1}\dots s_{a_p}$ (where $p=\ell \left(w\right)\text{)}$ of a permutation $w\text{.}$

For this purpose, we introduce the operators ${\partial }_i^{*},$ $i\ge 1,$ defined by

$$\begin{array}{cc}\text{(7.1)}& {\partial }_i^{*}{𝔖}_w=\{\begin{array}{cc}{𝔖}_{s_{i}w}& \text{if}\hspace{0.17em}\ell \left(s_{i}w\right)<\ell \left(w\right),\\ 0& \text{otherwise.}\end{array}\end{array}$$

Remarks. 1. If $\omega$ is the (linear) involution defined by $\omega \left({𝔖}_w\right)={𝔖}_{w^{-1}}$ for each permutation $w,$ it follows from (4.2) that ${\partial }_i^{*}=\omega {\partial }_i\omega \text{.}$ Hence we may define ${\partial }_w^{*}=\omega {\partial }_w\omega$ for any permutation $w,$ and we have ${\partial }_w^{*}={\partial }_{a_1}^{*}\dots {\partial }_{a_p}^{*}\text{.}$ whenever $(a_1,\dots ,a_p)$ is a reduced word for $w\text{.}$

2. If $w\in S_n$ we have ${\partial }_i^{*}{𝔖}_w=0$ for all $i>n,$ because ${\partial }_i^{*}{𝔖}_w=\omega {\partial }_i{𝔖}_{w^{-1}},$ which is zero because $w^{-1}\left(i\right)<w^{-1}(i+1)\text{.}$

(7.2) ${\partial }_i^{*}$ commutes with ${\partial }_j$ for all $i,j\ge 1\text{.}$

		Proof.
	We have $${\partial }_i^{*}{\partial }_j{𝔖}_w=\{\begin{array}{cc}{\partial }_i^{*}{𝔖}_{w{s}_j}={𝔖}_{s_{i}w{s}_j}& \text{if}\hspace{0.17em}\ell \left(s_{i}w{s}_j\right)=\ell \left(w\right)-2,\\ 0& \text{otherwise.}\end{array}$$ Likewise $${\partial }_j{\partial }_i^{*}{𝔖}_w=\{\begin{array}{cc}{\partial }_j{𝔖}_{s_{i}w}={𝔖}_{s_{i}w{s}_j}& \text{if}\hspace{0.17em}\ell \left(s_{i}w{s}_j\right)=\ell \left(w\right)-2,\\ 0& \text{otherwise.}\end{array}$$ Hence ${\partial }_i^{*}{\partial }_j-{\partial }_j{\partial }_i^{*}$ vanishes on each Schubert polynomial ${𝔖}_w,$ and therefore vanishes identically. $\square$

(7.3) Let $w_0=w_0^{\left(n\right)}$ be the longest element of $S_n\text{.}$ Then for $r=1,2,\dots ,n-1$ we have

$$(1+t{\partial }_{n-r}^{*})\dots (1+t{\partial }_{n-1}^{*}){𝔖}_{w_0}=(1+t{\partial }_1)\dots (1+t{\partial }_r){𝔖}_{w_0}$$

as polynomials in $t,x_1,x_2,\dots \text{.}$

		Proof.
	The coefficient of $t^p$ $(1\le p\le r)$ on the left-hand side is $$\begin{array}{cc}\text{(1)}& \sum {\partial }_{a_1}^{*}\dots {\partial }_{a_p}^{*}{𝔖}_{w_0}\end{array}$$ summed over all reduced sequences $(a_1,\dots ,a_p)$ satisfying $$n-r\le a_1\le \dots \le a_p\le n-1\text{.}$$ Let $b_i=n-a_{p+1-i}$ for all $1\le i\le p,$ so that $$\begin{array}{cc}\text{(2)}& 1\le b_1<\dots <b_p\le r\text{.}\end{array}$$ Let $w=s_{a_p}\dots s_{a_1},$ so that $w_{0}w{w}_0=s_{b_1}\dots s_{b_p}\text{.}$ Then $$\begin{array}{ccc}{\partial }_{a_1}^{*}\dots {\partial }_{a_p}^{*}{𝔖}_{w_0}& =& {𝔖}_{w^{-1}{w}_0}={\partial }_{w_{0}w{w}_0}{𝔖}_{w_0}\\ & =& {\partial }_{b_1}\dots {\partial }_{b_p}{𝔖}_{w_0}\text{.}\end{array}$$ Hence (1) is equal to $$\sum {\partial }_{b_1}\dots {\partial }_{b_p}{𝔖}_{w_0}$$ summed over all reduced sequences $(b_1,\dots ,b_p)$ satisfying (2), which is the coefficient of $t^p$ on the right hand side of (7.2). $\square$

Next, we have

$$\begin{array}{cc}\text{(7.4)}& {𝔖}_{1\times w_0}(t,x_1,\dots ,x_{n-1})=(1+t{\partial }_1)\dots (1+t{\partial }_{n-1}){𝔖}_{w_0}(x_1,\dots ,x_{n-1})\text{.}\end{array}$$

By (4.22) we have to show that

$$(1+t{\partial }_1)\dots (1+t{\partial }_{n-1})s_{\delta }(X_1,\dots ,X_{n-1})=s_{\delta }(t+X_1,\dots ,t+X_{n-1})$$

where $X_i=x_1+\dots +x_i$ for each $i\ge 1,$ and $\delta ={\delta }_n\text{.}$ For this it is enough to show that

$$\begin{array}{cc}\text{(1)}& (1+t{\partial }_i)s_{\delta }(X_1,\dots ,X_i,t+X_{i+1},\dots ,t+X_{n-1})=s_{\delta }(X_1,\dots ,X_{i-1},t+X_i,\dots ,t+X_{n-1})\end{array}$$

for $i=1,2,\dots ,n-1\text{.}$

Both sides of (1) are determinants with $n-1$ rows and columns which agree in all the $i^{\text{th}}$ row. On the left-hand side, the elements of the $i^{\text{th}}$ row are by (3.10)

$$h_k\left(X_i\right)+t{h}_{k-1}\left(X_{i+1}\right)$$

and on the right-hand side they are $h_k(t+X_i),$ where $k$ runs form $n-2i+1$ to $2n-2i-1$ in each case.

Now we have

$$\begin{array}{ccc}{h}_k\left(X_i\right)+t{h}_{k-1}\left(X_{i+1}\right)& =& h_k(t+X_i)-t{h}_{k-1}(t+X_i)+t{h}_{k-1}(t+X_{i+1})-t^2{h}_{k-2}(t+X_{i+1})\\ & =& h_k(t+X_i)-t(t-x_{i+1})h_{k-2}(t+X_{i+1})\end{array}$$

Hence if we add $t(t-x_{i+1})$ times the ${(i+1)}^{\text{th}}$ row to the $i^{\text{th}}$ row in the determinant on the left-hand side, we shall obtain the right-hand side of (1).

For each $r\ge 1,$ let

$${\Phi }_r\left(t\right)=t^r(1+t{\partial }_{r+1}^{*})(1+t{\partial }_{r+2}^{*})\dots$$

For each permutation $w,$ we have $(1+t{\partial }_j^{*}){𝔖}_w={𝔖}_w$ for all sufficiently large $j$ by (7.1), so that ${\Phi }_r\left(t\right){𝔖}_w$ is a polynomial in $t$ (and $x_1,x_2,\dots \text{).}$ With this notation, we have

$$\begin{array}{cc}\text{(7.5)}& {\partial }_1{\partial }_2\dots {\partial }_{n-r+1}\left(x_1^n{x}_2^{n-1}\dots x_n\right)={\Phi }_{r-1}\left(x_1\right){𝔖}_{w_0^{\left(n\right)}}(x_2,x_3,\dots )\end{array}$$

		Proof.
	Let $s=n-r+1$ and $$a=x_2^{s-1}{x}_3^{s-2}\dots x_s,b=x_{s+2}^{r-2}{x}_{s+3}^{r-3}\dots x_n,c={\left(x_2\dots x_{s+1}\right)}^{r-1}$$ so that $abc=x_2^{n-1}{x}_3^{n-2}\dots x_n\text{.}$ Hence $$\begin{array}{ccc}{\partial }_1{\partial }_2\dots {\partial }_n\left(x_1^n{x}_2^{n-1}\dots x_n\right)& =& x_1^{r-1}bc{\partial }_1\dots {\partial }_s\left(x_1^s{x}_2^{s-1}\dots x_s\right)\\ & =& x_1^{r-1}bc{𝔖}_{1\times w_0^{\left(s\right)}}(x_1,\dots ,x_s)& \text{by (4.21)}\\ & =& x_1^{r-1}bc(1+x_1{\partial }_2)\dots (1+x_1{\partial }_s)a& \text{by (7.4)}\\ & =& x_1^{r-1}(1+x_1{\partial }_2)\dots (1+x_1{\partial }_s)abc\\ & =& x_1^{r-1}(1+x_1{\partial }_2)\dots (1+x_1{\partial }_s){𝔖}_{w_0^{\left(n\right)}}(x_1,\dots ,x_n)\\ & =& x_1^{r-1}(1+x_1{\partial }_r^{*})\dots (1+x_1{\partial }_{n-1}^{*}){𝔖}_{w_0^{\left(n\right)}}(x_2,\dots ,x_n)& \text{by (7.3).}\end{array}$$ $\square$

Let $w$ be any permutation. If $w\left(1\right)=r,$ then $s_1\dots s_{r-1}w\left(1\right)=1,$ so that we may write

$$s_1\dots s_{r-1}w=1\times w_1$$

where $w_1$ is defined by

$$w_1\left(i\right)=\{\begin{array}{cc}w(i+1)& \text{if}\hspace{0.17em}w(i+1)<r,\\ w(i+1)-1& \text{if}\hspace{0.17em}w(i+1)>r\text{.}\end{array}$$

If the code of $w$ is $(c_1,c_2,\dots )$ (so that $c_1=r-1\text{),}$ the code of $w_1$ is $(c_2,c_3,\dots )\text{.}$ With this notation we have

$$\begin{array}{cc}\text{(7.6)}& {𝔖}_w(x_1,x_2,\dots )={\Phi }_{r-1}\left(x_1\right){𝔖}_{w_1}(x_2,x_3,\dots )\end{array}$$

		Proof.
	Suppose that $w\in S_{n+1}\text{.}$ Then $$\begin{array}{ccc}{w}_0^{(n+1)}w& =& w_0^{(n+1)}{s}_{r-1}\dots s_1(1\times w_1)\\ & =& s_{n-r+2}\dots s_n{w}_0^{(n+1)}(1\times w_0^{\left(n\right)})(1\times w_0^{\left(n\right)}{w}_1)\\ & =& s_{n-r+1}\dots s_1(1\times w_0^{\left(n\right)}{w}_1)\end{array}$$ since $w_0^{(n+1)}(1\times w_0^{\left(n\right)})=s_n{s}_{n-1}\dots s_1\text{.}$ Hence $$\begin{array}{ccc}{𝔖}_w(x_1,\dots ,x_n)& =& {\partial }_{w^{-1}{w}_0^{(n+1)}}\left(x_1^n{x}_2^{n-1}\dots n_x\right)\\ & =& {\partial }_{1\times w_1^{-1}{w}_0^{\left(n\right)}}{\partial }_1\dots {\partial }_{n-r+1}\left(x_1^n\dots x_n\right)\\ & =& {\partial }_{1\times w_1^{-1}{w}_0^{\left(n\right)}}{\Phi }_{r-1}\left(x_1\right){𝔖}_{w_0^{\left(n\right)}}(x_2,x_3,\dots ,x_n)& \text{by (7.5)}\\ & =& {\Phi }_{r-1}\left(x_1\right){\partial }_{1\times w_1^{-1}{w}_0^{\left(n\right)}}{𝔖}_{w_0^{\left(n\right)}}(x_2,x_3,\dots ,x_n)& \text{by (7.2)}\\ & =& {\Phi }_{r-1}\left(x_1\right){𝔖}_{w_1}(x_2,x_3,\dots )\text{.}\end{array}$$ $\square$

Remark. The right-hand side of (7.6) is a sum of terms of the form $x_1^p{𝔖}_u(x_2,x_3,\dots )\text{.}$ By applying (7.6) to each ${𝔖}_u,$ and so on, we can decompose ${𝔖}_w$ into a sum of monomials, and thus we have another proof of the fact (4.17) that ${𝔖}_w$ is a polynomial in $x_1,x_2,\dots$ with positive integer coefficients.

Next, let $m\ge 1$ and assume that the permutation $w$ statisfies

$$w\left(1\right)>w\left(2\right)>\dots >w\left(m\right)\text{.}$$

Define a partition $\mu =\mu (w,m)$ of length $\le m$ by

$${\mu }_i=w\left(i\right)-(m+1-i)(1\le i\le m)\text{.}$$

If $w\in S_{m+n}$ we have ${\mu }_1\le n,$ hence $\mu \subset \left(n^m\right)\text{.}$

Also let

$${\Phi }_{\mu }(x_1,\dots ,x_m)={\Phi }_{{\mu }_m}\left(x_m\right)\dots {\Phi }_{{\mu }_2}\left(x_2\right){\Phi }_{{\mu }_1}\left(x_1\right)$$

and let $w_m$ be the permutation whose code is $(c_{m+1},c_{m+2},\dots ),$ where $(c_1,c_2,\dots )$ is the code of $w\text{.}$

With this notation established, we have

$$\begin{array}{cc}\text{(7.7)}& {𝔖}_w\left(x\right)=x^{{\delta }_m}{\Phi }_{\mu }(x_1,\dots ,x_m){𝔖}_{w_m}(x_{m+1},x_{m+2},\dots )\text{.}\end{array}$$

		Proof.
	We proceed by induction on $m\text{;}$ the case $m=1$ is (7.6). From (7.6) we have $$\begin{array}{ccc}{𝔖}_w\left(x\right)& =& {\Phi }_{{\mu }_1+m-1}\left(x_1\right){𝔖}_{w_1}(x_2,x_3,\dots )\\ & =& \sum _u{x}_1^{{\mu }_1+m+p-1}{𝔖}_{u{w}_1}(x_2,x_3,\dots )\end{array}$$ summed over all $u=s_{a_1}\dots s_{a_p},$ where $$c_1\left(w\right)+1={\mu }_1+m\le a_1<\dots <a_p$$ and $\ell \left(u{w}_1\right)=\ell \left(w_1\right)-p\text{.}$ The code of $u{w}_1$ satisfies $c_i\left(u{w}_1\right)=c_i\left(w_1\right)$ for $1\le i\le m-1,$ and hence $${\left(u{w}_1\right)}_{m-1}=s_{a_1-m+1}\dots s_{a_p-m+1}{w}_m\text{.}$$ It follows that $$\sum _u{x}_1^{{\mu }_1+m+p-1}{𝔖}_{{\left(u{w}_1\right)}_{m-1}}(x_{m+1},x_{m+2},\dots )=x_1^{m-1}{\Phi }_{{\mu }_1}\left(x_1\right){𝔖}_{w_m}(x_{m+1},x_{m+2},\dots )$$ and therefore, by the inductive hypothesis, $$\begin{array}{ccc}{𝔖}_w\left(x\right)& =& \sum _u{x}_1^{{\mu }_1+m+p-1}{x}_2^{m-2}\dots x_{m-1}{\Phi }_{{\mu }_m}\left(x_m\right)\dots {\Phi }_{{\mu }_2}\left(x_2\right){𝔖}_{{\left(u{w}_1\right)}_{m-1}}(x_{m+1},x_{m+2},\dots )\\ & =& x_1^{m-1}{x}_2^{m-2}\dots x_{m-1}{\Phi }_{{\mu }_m}\left(x_m\right)\dots {\Phi }_{{\mu }_1}\left(x_1\right){𝔖}_{w_m}(x_{m+1},x_{m+2},\dots )\text{.}\end{array}$$ $\square$

Finally, for any permutation $w,$ let $v$ be the unique element of $S_m$ such that $wv\left(1\right)>\dots >wv\left(m\right),$ and let $\mu =\mu (wv,m)\text{.}$ We have $\ell \left(wv\right)=\ell \left(w\right)+\ell \left(v\right)$ and ${\left(wv\right)}_m=w_m,$ so that by (7.7)

$${𝔖}_{wv}\left(x\right)=x^{{\delta }_m}{\Phi }_{\mu }(x_1,\dots x_m){𝔖}_{w_m}(x_{m+1},x_{m+2},\dots )\text{.}$$

Hence

$$\begin{array}{cc}\text{(7.8)}& \begin{array}{ccc}{𝔖}_w\left(x\right)& =& {\partial }_v{𝔖}_{wv}\left(x\right)\\ & =& {\partial }_v\left(x^{{\delta }_m}{\Phi }_{\mu }(x_1,\dots ,x_m)\right){𝔖}_{w_m}(x_{m+1},x_{m+2},\dots )\text{.}\end{array}\end{array}$$

Now by (4.14), for any polynomial $f\in P_m,$ we have

$$f=\sum _{u\in S^{\left(m\right)}}\eta \left({\partial }_{u}f\right)S_u$$

where $S^{\left(m\right)}$ consists of the permutations whose codes have length $\le m,$ and $\eta \left({\partial }_{u}f\right)$ is the constant term of the polynomial ${\partial }_{u}f\text{.}$ Applying this to (7.8), we obtain our final result:

$$\begin{array}{cc}\text{(7.9)}& {𝔖}_w\left(x\right)=\sum _u{𝔖}_u(x_1,\dots ,x_m)\eta \left({\partial }_{uv}\left(x^{{\delta }_m}{\Phi }_{\mu }(x_1,\dots ,x_m)\right)\right){𝔖}_{w_m}(x_{m+1},x_{m+2},\dots )\end{array}$$

summed over all $u\in S^{\left(m\right)}$ such that $\ell \left(uv\right)=\ell \left(u\right)+\ell \left(v\right)\text{.}$

For each such $u,$ the constant term $\eta \left({\partial }_{uv}\left(x^{{\delta }_m}{\Phi }_{\mu }(x_1,\dots ,x_m)\right)\right)$ is a polynomial in the (non-commuting) operators ${\partial }_i^{*}$ with integer coefficients. Hence (7.9) gives a decomposition of the Schubert polynomial ${𝔖}_w\left(x\right)$ of the form

$$\begin{array}{cc}\text{(7.10)}& {𝔖}_w\left(x\right)=\sum _{u,v}{d}_{uv}^w{𝔖}_u\left(y\right){𝔖}_v\left(z\right),\end{array}$$

where $y=(x_1,\dots ,x_m)$ and $z=(x_{m+1},x_{m+2},\dots )\text{.}$ If $w\in S^{(m+n)},$ so that ${𝔖}_w\left(x\right)\in P_{m+n},$ then $u\in S^{\left(m\right)}$ and $v\in S^{\left(n\right)}$ in this sum. From (4.18) we know that the coefficients $d_{uv}^w$ in (7.10) are $\ge 0\text{.}$

In particular, if we apply (7.7) to a permutation of the form $w_0^{\left(m\right)}\times w,$ we shall obtain

$$\begin{array}{cc}\text{(1)}& {𝔖}_{w_0^{\left(m\right)}\times w}\left(x\right)=x^{{\delta }_m}{\Phi }_0(x_1,\dots ,x_m){𝔖}_w(x_{m+1},x_{m+2},\dots )\text{.}\end{array}$$

On the other hand, by (4.6) we have

$$\begin{array}{cc}\text{(2)}& {𝔖}_{w_0^{\left(m\right)}\times w}={𝔖}_{w_0^{\left(m\right)}}{𝔖}_{1_m\times w}\end{array}$$

and comparison of (1) and (2) gives

$$\begin{array}{cc}\text{(7.12)}& {𝔖}_{1_m\times w}\left(x\right)={\Phi }_0(x_1,\dots ,x_m){𝔖}_w(x_{m+1},x_{m+2},\dots )\text{.}\end{array}$$

By (4.3), ${𝔖}_{1_m\times w}$ is symmetrical in $x_1,\dots ,x_m\text{.}$ Hence so is the operator ${\Phi }_0(x_1,\dots ,x_m),$ and we may therefore write ${\Phi }_0$ in the form

$$\begin{array}{cc}\text{(7.13)}& {\Phi }_0(x_1,\dots ,x_m)=\sum _{\lambda ,v}{\alpha }_m(\lambda ,v)s_{\lambda }(x_1,\dots ,x_m){\partial }_v^{*}\end{array}$$

summed over partitions $\lambda$ of length $\le m$ and permutations $v,$ with integral coefficients ${\alpha }_m(\lambda ,v)\text{.}$ From (7.12) and (7.13) we have

$$\begin{array}{cc}\text{(7.14)}& {𝔖}_{1_m\times w}=\sum _{\lambda ,v}{\alpha }_m(\lambda ,v)s_{\lambda }(x_1,\dots ,x_m){𝔖}_{vm}(x_{m+1},x_{m+2},\dots )\end{array}$$

summed over $\lambda$ of length $\le m$ and $v$ such that $\ell \left(vw\right)=\ell \left(w\right)-\ell \left(v\right)\text{.}$ The Schur functions occuring here are precisely the Schubert polynomials ${𝔖}_u,$ where $u$ is Grassmannian with descent at $m\text{.}$ Hence, by (4.18),

(7.15) The coefficients ${\alpha }_m(\lambda ,v)$ in (7.13) are $\ge 0\text{.}$

Since ${\Phi }_0(x_1,\dots ,x_m,0)={\Phi }_0(x_1,\dots ,x_m)$ and $s_{\lambda }(x_1,\dots ,x_m,0)=s_{\lambda }(x_1,\dots ,x_m)$ if $\ell \left(\lambda \right)\le m,$ it follows from (7.13) that

$$\begin{array}{cc}\text{(7.16)}& {\alpha }_{m+1}(\lambda ,v)={\alpha }_m(\lambda ,v)=\alpha (\lambda ,v)\hspace{0.17em}\text{say}\end{array}$$

for all partitions $\lambda$ such that $\ell \left(\lambda \right)\le m\text{.}$

We may also calculate the operator ${\Phi }_0(x_1,\dots ,x_m)$ as follows. For each integer $p\ge 1$ and each subset $D$ of $\{1,2,\dots ,p-1\}$ let

$$Q_{D,p}(x_1,\dots ,x_m)=\sum x_{u_1}\dots x_{u_p}$$

summed over all sequences $(u_1,\dots ,u_p)$ such that $1\le u_1\le \dots \le u_p\le m$ and $u_i\le u_{i+1}$ whenever $i\in D\text{.}$ Then $Q_{D,p}(x_1,\dots ,x_m)$ is a homogeneous polynomial of degree $p,$ and is zero if $m\le \text{Card}\left(D\right)\text{.}$

Now let $a=(a_1,\dots ,a_p)$ be a reduced word, so that $\ell \left(s_{a_1}\dots s_{a_p}\right)=p\text{.}$ The descent set of $a$ is

$$D\left(a\right)=\{i:a_i>a_{i+1}\}\text{.}$$

We now define, for each permutation $w,$

$$F_w(x_1,\dots ,x_m)=\sum _{a\in R\left(w\right)}{Q}_{D\left(a\right),\ell \left(w\right)}(x_1,\dots ,x_m),$$

a homogeneous polynomial of degree $\ell \left(w\right)\text{.}$

With these definitions we have

$$\begin{array}{cc}\text{(7.17)}& {\Phi }_0(x_1,\dots ,x_m)=\sum _w{F}_w(x_1,\dots ,x_m){\partial }_w^{*}\text{.}\end{array}$$

		Proof.
	Let $a=(a_1,\dots ,a_p)$ be a reduced word. Since $${\Phi }_0\left(x_i\right)=(1+x_i{\partial }_1^{*})(1+x_i{\partial }_2^{*})\dots$$ it is clear from the definitions that the coefficient of ${\partial }_a^{*}={\partial }_{a_1}^{*}\dots {\partial }_{a_p}^{*}$ in ${\Phi }_0(x_1,\dots ,x_m)={\prod }_{i=1}^m{\Phi }_0\left(x_i\right)$ is just $Q_{D\left(a\right),p}(x_1,\dots ,x_m)\text{.}$ Hence $$\begin{array}{ccc}{\Phi }_0(x_1,\dots ,x_m)& =& \sum _a{Q}_{D\left(a\right),p}(x_1,\dots ,x_m){\partial }_a^{*}\\ & =& \sum _w{F}_w(x_1,\dots ,x_m){\partial }_w^{*}\text{.}\end{array}$$ $\square$

Comparison of (7.17) and (7.13) now shows that $F_w(x_1,\dots ,x_m)$ is a symmetric polynomial in $x_1,\dots ,x_m,$ and that

$$\begin{array}{cc}\text{(7.18)}& \begin{array}{ccc}{F}_w(x_1,\dots ,x_m)& =& \sum _{\lambda }{\alpha }_m(\lambda ,w)s_{\lambda }(x_1,\dots ,x_m)\\ & =& {\rho }_m\left({𝔖}_{1_m\times w^{-1}}\right)\text{.}\end{array}\end{array}$$

The sum in (7.18) is over partitions $\lambda$ such that $\ell \left(\lambda \right)\le m$ and $\left|\lambda \right|=\ell \left(w\right)\text{.}$ By (7.16) we have

$$F_w(x_1,\dots ,x_m,0)=F_w(x_1,\dots ,x_m)$$

and therefore we have a well defined symmetric function $F_w\in \Lambda ,$ such that ${\rho }_m\left(F_w\right)=F_w(x_1,\dots ,x_m)$ for all $m\ge 0\text{:}$ namely

$$\begin{array}{cc}\text{(7.19)}& F_w=\sum _{\lambda }\alpha (\lambda ,w)s_{\lambda }\end{array}$$

where the sum is over partitions $\lambda$ of $\ell \left(w\right),$ and $\alpha (\lambda ,w)={\alpha }_m(\lambda ,w)$ for any $m\ge \ell \left(\lambda \right)\text{.}$

Since the coefficient of $x_1\dots x_p$ in $Q_{D,p}(x_1,\dots ,x_m)$ is $1$ if $m\ge p,$ it follows that the coefficient of $x_1\dots x_p$ (where $p=\ell \left(w\right)\text{)}$ in $F_w(x_1,\dots ,x_m)$ is equal to $\text{Card}\left(R\left(w\right)\right)$ whenever $m\ge \ell \left(w\right)\text{.}$ On the other hand, the coefficient of $x_1\dots x_p$ in a Schur function $s_{\lambda },$ where $\left|\lambda \right|=p,$ is equal to $f^{\lambda },$ the number of standard tableaux of shape $\lambda ,$ or equivalently the degree of the irreducible representation ${\chi }^{\lambda }$ of $S_p$ indexed by the partition $\lambda$ ([Mac1979], Ch.I, §7). It follows therefore from (7.19) that

$$\begin{array}{cc}\text{(7.20)}& \text{Card}\hspace{0.17em}R\left(w\right)=\sum _{\left|\lambda \right|=\ell \left(w\right)}\alpha (\lambda ,w)f^{\lambda }\text{.}\end{array}$$

Remark. Since the coefficients $\alpha (\lambda ,w)$ are $\ge 0$ by (7.15), the number of reduced words for $w$ is always equal to the degree of an (in general reducible) representation of the symmetric group $S_{\ell \left(w\right)}\text{.}$ It is therefore natural to ask whether there is a "natural" action of this symmetric group on the $\mathbb{Z}\text{-span}$ (or perhaps $\mathbb{Q}\text{-span)}$ of the set $R\left(w\right),$ with character $\sum _{\lambda }\alpha (\lambda ,w){\chi }^{\lambda }\text{.}$

We shall conclude with some properties of the symmetric functions $F_w$ and the coefficients $\alpha (\lambda ,w)\text{.}$

(7.21) Let $u\in S_m,$ $v\in S_n\text{.}$ Then

$$F_{u\times v}\left(x\right)=F_u\left(x\right)F_v\left(x\right)\text{.}$$

		Proof.
	By (7.18), we have for any $N,$ $$\begin{array}{ccc}{F}_{u\times v}(x_1,\dots ,x_N)& =& {\rho }_N\left(S_{1_N\times u^{-1}\times v^{-1}}\right)\\ & =& {\rho }_N\left(S_{1_N\times u^{-1}}{S}_{1_{m+N}\times v^{-1}}\right)& \text{by (4.6)}\\ & =& {\rho }_N\left(S_{1_N\times u^{-1}}\right){\rho }_N\left({\rho }_{m+N}\left(S_{1_{m+N}\times v^{-1}}\right)\right)\\ & =& F_u(x_1,\dots ,x_N)F_v(x_1,\dots ,x_N)\text{.}\end{array}$$ $\square$

(7.22) Let $w\in S_n$ and let $\bar{w}=w_{0}w{w}_0,$ where $w_0$ is the longest element of $S_n\text{.}$ Then

$$F_{w^{-1}}=F_{\bar{w}}=\omega F_w$$

where $\omega$ is the involution that interchanges $s_{\lambda }$ and $s_{\lambda \prime }\text{.}$ In other words

$$\alpha (\lambda ,w^{-1})=\alpha (\lambda ,\bar{w})=\alpha (\lambda \prime ,w)$$

for all partitions $\lambda \text{.}$

For the proof of (7.22) we require a lemma. If $t$ is a standard tableau of shape $\lambda ,$ the descent set $D\left(t\right)$ of $t$ is the set of $i$ such that $i+1$ lies in a lower row than $i$ in the tableau $t\text{.}$ We have

$$\begin{array}{cc}\text{(7.23)}& s_{\lambda }=\sum _t{Q}_{D\left(t\right),p}\end{array}$$

where the sum is over the standard tableaux of shape $\lambda ,$ and $p=\left|\lambda \right|\text{.}$

		Proof.
	In the notation of [Mac1979, Ch. I, §5], $s_{\lambda }$ is the sum of monomials $x^T$ where $T$ runs through the (column-strict) tableaux of shape $\lambda \text{.}$ Each such tableau $T$ determines a standard tableau $t,$ as follows. If a square in the $j^{\text{th}}$ column of the diagram of $\lambda$ is occupied by the number $i,$ replace $i$ by the pair $(i,j)\text{.}$ Since $T$ is column-strict the pairs $(i,j)$ so obtained are all distinct. If we now order them lexiographically, (so that $(i,j)$ precedes $\lambda (i\prime ,j\prime )$ if and only if either $i<i\prime ,$ or $i=i\prime$ and $j<j\prime \text{)}$ and relabel them as $1,2,\dots ,p,$ we have a standard tableau $t\text{:}$ say $T\to t\text{.}$ It follows easily that $\sum _{T\to t}{x}^T=Q_{D\left(t\right),p},$ which proves the lemma. $\square$

If $D$ is any subset of $\{1,2,\dots ,p-1\},$ let $\bar{D}$ denote the complementary subset, and let $D^{*}=\{p-i:i\in D\}\text{.}$ From the definition of $Q_{D,p}$ we have

$$\begin{array}{cc}\text{(1)}& Q_{D,p}(x_m,x_{m-1},\dots ,x_1)=Q_{D^{*},p}(x_1,\dots ,x_m)\text{.}\end{array}$$

If $a=(a_1,\dots ,a_p)\in R\left(w\right),$ let $\bar{a}=(n-a_1,\dots ,n-a_p)$ and $a^{*}=(n-a_p,\dots ,n-a_1)\text{.}$ Then we have

$$\begin{array}{cc}\text{(2)}& \bar{a}\in R\left(\bar{w}\right),a^{*}\in R\left(w^{*}\right),\end{array}$$

where $w^{*}={\left(\bar{w}\right)}^{-1}=w_0{w}^{-1}{w}_0\text{.}$ Also

$$\begin{array}{cc}\text{(3)}& D\left(\bar{a}\right)=\overline{D\left(a\right)},D\left(a^{*}\right)=D{\left(a\right)}^{*}\text{.}\end{array}$$

Moreover, it $t$ is a standard tableau we have

$$\begin{array}{cc}\text{(4)}& D\left(t\prime \right)=\overline{D\left(t\right)}\end{array}$$

where $t\prime$ is the transpose of $t,$ obtained by reflecting $t$ in the main diagonal. For $i\in D\left(t\right)$ if and only if $i+1$ does not lie in a later column than $i$ in the tableau $t,$ that is to say if and only if $i\notin D\left(t\prime \right)\text{.}$

Since $F_w$ is symmetric, it follows from (1),(2), and (3) that

$$F_w(x_1,\dots ,x_m)=F_w(x_m,\dots ,x_1)=F_{w^{*}}(x_1,\dots ,x_m)$$

and hence by (7.16) that $F_w=F_{w^{}}\text{.}$

From (7.23) and (4) above we have

$$\omega s_{\lambda }=s_{\lambda \prime }=\sum _{t\in St(){\alpha }_{\ell }\lambda }{Q}_{\overline{D\left(t\right)},p}$$

for all partitions $\lambda$ of $p,$ where $St\left(\lambda \right)$ is the set of standard tableaux of shape $\lambda ,$ and hence it follows from (2) and (3) and the definition of $F_w$ that $\omega F_w=F_{\bar{w}}\text{.}$ Hence

$$\omega F_{w^{-1}}=F_{w^{*}}=F_w,$$

which completes the proof of (7.22).

(7.24)

(i) $\alpha (\mu ,w)=0$ unless $\lambda \left(w^{-1}\right)\le \mu \le \lambda \left(w\right)\prime \text{.}$ (ii) $\alpha (\mu ,w)=1$ if $\mu =\lambda \left(w^{-1}\right)$ or $\mu =\lambda \left(w\right)\prime \text{.}$ (iii) $w$ is vexillary if and only if $F_w$ is a Schur function.

		Proof.
	(i) Suppose $\alpha (\mu ,w)\ne 0\text{.}$ Then the monomial $x^{\mu }$ occurs in $F_w,$ and hence there is a reduced word $(a_1,\dots ,a_p)$ for $w$ such that $$\begin{array}{cc}\text{(1)}& a_1<\dots <a_{{\mu }_1},a_{{\mu }_1+1}<\dots <a_{{\mu }_1+{\mu }_1,}\dots \text{.}\end{array}$$ By (1.14) the code of $w$ is $$\begin{array}{cc}\text{(2)}& c\left(w\right)=\sum _{i=1}^p{s}_{a_p}\dots s_{a_{i+1}}\left({\epsilon }_{a_i}\right)\text{.}\end{array}$$ If $w^{\left(1\right)}=s_{a_p}\dots s_{a_{{\mu }_1}+1},$ the sum of the first ${\mu }_1$ terms of this series is $$w^{\left(1\right)}({\epsilon }_{a_{{\mu }_1}}+s_{a_{{\mu }_1}}\left({\epsilon }_{a_{{\mu }_1-1}}\right)+\dots +s_{a_{{\mu }_1}}\dots s_{a_2}\left({\epsilon }_{a_1}\right)),$$ and since $a_1<\dots <a_{{\mu }_1}$ this is equal to $$\begin{array}{cc}\text{(3)}& w^{\left(1\right)}({\epsilon }_{a_{{\mu }_1}}+{\epsilon }_{a_{{\mu }_1-1}}+\dots +{\epsilon }_{a_1})=V_1\hspace{0.17em}\text{say,}\end{array}$$ where $V_1$ is a $(0,1)$ vector (i.e., a vector with each component $0$ or $1\text{)}$ of weight ${\mu }_1\text{.}$ Likewise the sum of the next block of ${\mu }_2$ terms of the series (2) is a $(0,1)$ vector $V_2$ of weight ${\mu }_2,$ and so on. Hence $$c\left(w\right)=V_1+\dots +V_m$$ where $m=\ell \left(\lambda \right),$ and each $V_i$ is a $(0,1)$ vector of weight ${\mu }_i\text{.}$ Let $V$ be the $(0,1)$ matrix whose $i^{\text{th}}$ row is $V_i,$ for $i=1,2,\dots ,m\text{.}$ Then $V$ has row sums ${\mu }_1,\dots ,{\mu }_m$ and column sums $c_1\left(w\right),c_2\left(w\right),\dots$ As in the proof of (1.26) it follows that $\mu \le \lambda \left(w\right)\prime \text{.}$ Since $\alpha (\mu ,w)=\alpha (\mu \prime ,w^{-1})$ by (7.23), the same argument applied to $\mu \prime$ and $w^{-1}$ gives $\mu \prime \le \lambda \left(w^{-1}\right)\prime$ i.e., $\lambda \left(w^{-1}\right)\le \mu \text{.}$ (ii) Suppose now that $\mu =\lambda \left(w\right)\prime \text{.}$ Then there is only one $(0,1)$ matrix $V$ with row sums ${\mu }_i$ and column sums $c_i\text{.}$ Its first row $V_1$ is $\sum {\epsilon }_j$ summed over $j$ such that $c_j\ne 0,$ i.e. such that there exists $k>j$ with $w\left(k\right)<w\left(j\right)\text{.}$ From (3) it follows that $$w{V}_1=\sum _{i=1}^{{\mu }_1}{\epsilon }_{a_i+1}$$ and therefore $a_1+1,\dots ,a_{{\mu }_1}+1$ are the terms of the sequence $w$ that have a smaller element somewhere to the right, in increasing order of magnitude. Hence $a_1$ has no smaller elements to the right of it, and therefore lies to the right of $a_1+1,$ so that $\ell \left(s_{a_1}w\right)=\ell \left(w\right)-1\text{.}$ The same argument shows that $\ell \left(s_{a_2}{s}_{a_1}w\right)=\ell \left(s_{a_1}w\right)-1$ and so on. Hence if $w_1=s_{a_{{\mu }_1}}\dots s_{a_1}w$ we have $\ell \left(w_1\right)=\ell \left(w\right)-{\mu }_1,$ and $\lambda \left(w_1^{\prime }\right)=({\mu }_2,{\mu }_3,\dots )\text{.}$ It follows by induction on $\ell \left(\mu \right)$ that the word $(a_1,\dots ,a_p)$ determined by the matrix $V$ is reduced, and hence $\alpha (\mu ,w)=1$ when $\mu =\lambda \left(w\right)\prime \text{.}$ By (7.23) it follows that $\alpha (\mu ,w)=1$ when $\mu =\lambda \left(w^{-1}\right)\text{.}$ (iii) This follows immediately from (i) and (ii), and the characterization (1.27) of vexillary permutations. $\square$

Notes and References

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

page history