\documentclass[12pt]{article}
\usepackage{amsmath,amsfonts,amssymb,colordvi}

\textheight=22cm
\textwidth=15cm
\topmargin=-1cm
\leftmargin=13cm
%%%%%%%%%format of begin %%%%%%%%

\def\L{\Lambda}
\def\qed{\nopagebreak\hfill{\rule{4pt}{7pt}}}
\def\proof{\noindent {\it{Proof.} \hskip 2pt}}
\def\dis{\displaystyle}
\def\Remark{\noindent{\textbf Remark}}

\def\d{\partial}
\def\bp{\widehat{\pi}}
\def\Kh{\widehat K}
\def\FKh{\mathcal{F}\widehat K}
\def\FK{\mathcal{F}K}
\def\FS{\mathcal{F}Y}

\def\A{A}
\def\bA{{\mathbb A}}
\def\bB{{\mathbb B}}
\def\bC{{\mathbb C}}
\def\bN{{\mathbb N}}
\def\bL{{\mathbb L}}
\def\bY{{\mathbb Y}}
\def\bZ{{\mathbb Z}}
\def\bK{{\mathbb K}}

\def\mfs{{\mathfrak S}}
\def\d{\partial}
\def\moins{\raise 1pt\hbox{{$\scriptstyle -$}}}
\def\plus{\raise 1pt\hbox{{$\scriptstyle +$}} }
\def\Plax{{ \mathfrak{ P\hspace{-0.07 em}l\hspace{-0.05 em}a\hspace{-0.05 em} x}}}
\def\Schub{{\mathfrak{S\hspace{-0.06 em}c\hspace{-0.05 em}h%
\hspace{-0.05 em}u\hspace{-0.05 em}b}}}
\def\Sym{\mathfrak{Sym}}


\newtheorem{theo}{Theorem}[section]
\newtheorem{defi}[theo]{Definition}
\newtheorem{lemm}[theo]{Lemma}
\newtheorem{prop}[theo]{Proposition}
\newtheorem{coro}[theo]{Corollary}

\newcommand{\newsection}[1]{\section{#1} \setcounter{equation}{0}}

\renewcommand{\theequation}{\arabic{section}.\arabic{equation}}
\renewcommand{\thesection}{\arabic{section}.}
\renewcommand{\thetheo}{\arabic{section}.\arabic{theo}}
\renewcommand{\thefigure}{\arabic{section}.\arabic{figure}}
\makeatletter \@addtoreset{figure}{section} \makeatother
\makeatletter
\long\def\@makecaption#1#2{%
   \vskip 10\p@
   \setbox\@tempboxa\hbox{{#1}\ \ #2}%
   \ifdim \wd\@tempboxa >\hsize
       {#1}\ \ #2\par
   \else
       \hbox to\hsize{\hfil\box\@tempboxa\hfil}%
   \fi}
\makeatother

\parskip=8pt

\begin{document}

\begin{center}
{\Large \bf {Pieri formulas for Demazure characters} }
\end{center}
\centerline{Alain Lascoux, Hui Lin and Arthur L. B. Yang}

\vspace{0.3cm} \noindent{\bf Abstract.} We give a Pieri formula
for key polynomials (also called Demazure characters). It implies
an explicit decomposition of Schubert polynomials in terms of key
polynomials. The constructions extend to the non-commutative
cases.

\section{Motivation and background}

\section{Notation}

Given a polynomial $f$ in the variables
$x_1,\,x_2,\,\ldots,\,x_n$, the simple transposition $s_i$ acts on
$f$ by exchanging the variables $x_i$ and $x_{i+1}$, denoted by
$f^{s_i}$.

The divided difference $\d_i$ acts on $f$ in the following way:
\begin{equation}
f\d_i=\frac{f-f^{s_i}}{x_i-x_{i+1}}.
\end{equation}

The isobaric divided differences $\pi_i$ and $\bp_i$ are defined
by:
\begin{equation}
f\pi_i=\frac{x_if-x_{i+1}f^{s_i}}{x_i-x_{i+1}}=fx_i\d_i \quad
\mbox{and} \quad f\bp_i=f\pi_i-f=f\d_ix_{i+1},
\end{equation}
where $x_i$ means ``multiplication by $x_i$''.

For any permutation $\sigma$ we define the operator $\d_{\sigma}$
as $\d_{r_1}\cdots\d_{r_k}$, where $s_{r_1}\cdots s_{r_k}$ is a
reduced decomposition of $\sigma$. Since the operators $\d_i$
satisfy the braid relations,  $\d_{\sigma}$ is well defined.
Similarly we define the operators $\pi_{\sigma}$ and
$\bp_{\sigma}$.

We now give the definition of Schubert polynomials and key
polynomials.

For any $J\in \bN^n$, we say that $J$ is dominant if $J$ is weakly
decreasing. In the dominant case, we define the Schubert
polynomial $Y_J$, the key polynomial $K_J$ and $\Kh_J$ as the same
monomial $x_1^{j_1}x_2^{j_2}\cdots x_{n}^{j_n}$, namely,
\begin{equation}
Y_J=K_J=\Kh_J=x_1^{j_1}x_2^{j_2}\cdots x_{n}^{j_n}.
\end{equation}
If $J$ is not dominant, then there must exist $i$ such that
$j_i<j_{i+1}$. Let $J'=[\ldots,j_{i+1},j_i,\ldots]$. Then the
Schubert polynomial $Y_J$, the key polynomial $K_J$ and $\Kh_J$
are recursively defined as
\begin{equation}
Y_J=Y_{J'}\d_i, \quad K_J=K_{J'}\pi_i \quad \mbox{and} \quad
\Kh_J=\Kh_{J'}\bp_i.
\end{equation}
For any $J\in \bN^n$, the polynomials $Y_J,\,K_J,\,\Kh_J$ are well
defined.

Suppose $\lambda$ is a weakly decreasing reordering of $J$, then
there exists a permutation $\sigma$ such that
$J=\lambda^{\sigma}$. We have
\begin{equation}
Y_J=Y_{\lambda}\d_\sigma, \quad K_J=K_{\lambda}\pi_\sigma \quad
\mbox{and} \quad \Kh_J=\Kh_{\lambda}\bp_\sigma.
\end{equation}

Given two sets $u,\,v$ of the same size, written increasingly,
then $u\leq v$ if and only if $u_1\leq v_1$, $u_2\leq v_2...$. Let
$\lambda$ and $\mu$ be two partitions which are decreasing
reordering of $u$ and $v$ respectively. Graphically, $u\leq v$
means that the diagram of $\lambda$ is a subdiagram of $\mu$. The
diagram of $\lambda$ is also called the diagram of $u$.

Given two permutations $\sigma$ and $\nu$, we say that $\sigma\leq
\nu$ if and only if for any $k$ one has
$\{\sigma_1,\,\ldots,\,\sigma_k\} \leq
\{\nu_1,\,\ldots,\,\nu_k\}$. This order is called the
Ehresmann-Bruhat order of the symmetric group. It can be used to
define an order on vectors with repeated components.

Given two vectors $u,\,v$ of the same length, then $u\leq v$ if
and only if for any $k$, $\{u_1,...,u_k\}\leq \{v_1,...,v_k\}$.

The Ehresmann-Bruhat order of the symmetric group also has another
definition. For $\sigma\in S_n$, let ${r_1}\cdots {r_m}$ be a
reduced expression of $\sigma$. For $\nu\in S_n$, $\nu\leq \sigma$ if and only if there exists a
sequence of natural numbers $1\leq j_1\leq \cdots\leq j_k\leq m$
such that ${r_{j_1}}\cdots {r_{j_k}}$ is one of the reduced
decompositions of $\nu$.

\section{Commutation rule on operators}

From the definitions of $\d_i,\,\pi_i$ and $\bp_i$, we directly
get
\begin{equation}\label{comm-1}
\pi_i=x_i\, \d_i, \quad \bp_i=\d_i\, x_{i+1}
\end{equation}
that we can rewrite as commutation rules
\begin{eqnarray}
\bp_i \, x_i =  x_{i+1}\, \pi_i, \quad x_{i} \,\bp_i= \pi_i \, x_{i+1}.
\end{eqnarray}

The following relation is immediate from the
definitions of divided differences
\begin{equation}
x_i\d_j=\d_jx_i,\quad x_i\pi_j=\pi_jx_i,\quad
x_i\bp_j=\bp_jx_i,\quad \mbox{for $|i-j|>1$.}
\end{equation}
Then for any $k>j$ we have
\begin{eqnarray}
\pi_k\,\pi_{k-1}\cdots \pi_j= x_k\d_k\,x_{k-1}\d_{k-1}\cdots
x_j\d_j = x_k\,x_{k-1}\cdots x_j \ \d_k\,\d_{k-1}\cdots
\d_j,  \\ \label{comm-2}
\bp_k\,\bp_{k-1}\cdots \bp_j= \d_k\,x_{k+1}\d_{k-1}x_k\cdots
\d_jx_{j+1} = \d_k\,\d_{k-1}\cdots
\d_j\ x_{k+1}\,x_k\cdots x_{j+1}.\label{comm-3}
\end{eqnarray}


The following commutation rules are needed in the following, for
$k>j$
\begin{eqnarray}
\pi_k\cdots \pi_j \, x_{k+1}\cdots x_{j+1}& = & x_k\cdots x_j \, \bp_k\cdots \bp_j\label{comm-4}\\
x_{j+1}\cdots x_{k+1}\, \pi_j\cdots \pi_k & = & \bp_j\cdots \bp_k
\, x_j \cdots x_k.\label{comm-5}
\end{eqnarray}

Let $\sigma$ be a permutation with one reduced decomposition
inscribed in the diagram of a partition in the South-East corner
of the rectangles
\begin{equation}\label{mtx-rd}
 \begin{matrix}  s_{n-k} & \cdots & s_{n-1} \\
                  \vdots  &         & \vdots \\
                  s_1   & \cdots        & s_k
\end{matrix}.
\end{equation}
Then applying the above commutation rules, we get
\begin{lemm}\label{lem-main}
For any $k$ and $\sigma$ having the above reduced decomposition,
the following relations hold
\begin{equation}
\bp_{\sigma}x_k\cdots x_1 =(x_k\cdots x_1)^{\nu}\pi_{\sigma},
\quad \pi_{\sigma}x_n\cdots x_{k+1}=(x_n\cdots
x_{k+1})^{\nu}\bp_{\sigma},
\end{equation}
where $\nu=\sigma^{-1}$.
\end{lemm}


For example we take $n=8,\,k=3$ and
$\sigma=s_4s_3s_2\,s_7s_6s_5s_4s_3$, the following planar display
implies a proof of the above lemma.
\begin{figure}[h]
\setlength{\unitlength}{2pt}
\begin{center}
\begin{picture}(180,100)
\put(0,70){$\begin{matrix}&\pi_7 & x_8\\ &\pi_6 & x_7\\ \pi_4 & \pi_5 & x_6\\
\pi_3 & \pi_4 & x_5\\ \pi_2 & \pi_3 & x_4\end{matrix}$}

\put(40,70){$\rightarrow$}

\put(60,70){$\begin{matrix}& x_7 & \d_7 & x_8\\ & x_6 & \d_6 & x_7\\ \pi_4 & x_5 & \d_5 & x_6\\
\pi_3 & x_4 & \d_4 & x_5\\ \pi_2 & x_3 & \d_3 & x_4\end{matrix}$}

\put(110,70){$\rightarrow$}

\put(130,70){$\begin{matrix}& x_7 & \d_7 & x_8\\ & x_6 & \d_6 & x_7\\ \pi_4 & x_5 & \d_5 & x_6\\
\pi_3 & x_4 & \d_4 & x_5\\ \pi_2 & x_3 & \d_3 & x_4\end{matrix}$}

\put(180,70){$\rightarrow$}

\thinlines {\put(9,53){\framebox(19,37)[0,0]}}
\Blue{\put(67,54){\framebox(19,37)[0,0]}}
\put(66,53){\framebox(30,39)[0,0]}

\Blue{\put(147,54){\framebox(19,37)[0,0]}}
\put(136,53){\framebox(31,39)[0,0]}

%%%
\put(-2,20){$\begin{matrix}&x_7 & \bp_7\\ &x_6 & \bp_6\\ \pi_4 & x_5 & \bp_5\\
\pi_3 & x_4 & \bp_4\\ \pi_2 & x_3 & \bp_3\end{matrix}$}

\put(38,20){$\rightarrow$}

\put(58,20){$\begin{matrix}&x_7 & \bp_7\\ &x_6 & \bp_6\\ \pi_4 & x_5 & \bp_5\\
\pi_3 & x_4 & \bp_4\\ \pi_2 & x_3 & \bp_3\end{matrix}$}

\put(108,20){$\rightarrow$}

\put(128,20){$\begin{matrix}&x_7 & \bp_7\\ &x_6 & \bp_6\\ x_4 & \bp_4 & \bp_5\\
x_3 & \bp_3 & \bp_4\\ x_2 & \bp_2 & \bp_3\end{matrix}$}

\Blue{\put(7,3){\framebox(19,37)[0,0]}}

\put(56,4){\framebox(19,20)[0,0]}

\Blue{\put(126,4){\framebox(19,22)[0,0]}}

\end{picture}
\end{center}
\caption{Commutations between $\pi_{\sigma}$ and $x_{k+1}\cdots
x_n$}
\end{figure}

We have a Leibniz formula
\begin{equation}\label{id-lz}
\pi_i x_i = x_{i+1} \pi_i + x_i.
\end{equation}
For any $j<k$ and $m\geq 0$, iterating the above formula we get
\begin{equation}
\pi_j\cdots \pi_k\pi_{k+1}\cdots \pi_{k+m} \, x_j\cdots x_k
=\sum_{i=j}^{k+1}x_j\cdots \bar{x}_i\cdots x_{k+1} \, \pi_j\cdots
\bar{\pi}_{i-1}\cdots \pi_{k}\pi_{k+1}\cdots \pi_{k+m},
\end{equation}
where $\bar{x}_i$ and $\bar{\pi}_{i-1}$ means the missing in the product. For this formula
we have the following planar display reading the word by rows
%For example when $j=1,\,k=4$ we have
\begin{figure}[h]
\setlength{\unitlength}{2pt}
\begin{center}
\begin{picture}(240,75)
\put(-2,55){\framebox(88,13)[0,0]}
\put(100,55){\framebox(97,13)[0,0]}
\put(23,30){\framebox(153,13)[0,0]}
\put(15,0){\framebox(122,13)[0,0]}

\put(0,60){$
\begin{matrix}
\cdot & \pi_j & \cdots  & \pi_{k} & \pi_{k+1} & \cdots & \pi_{k+m}\\
\cdot & x_j   & \cdots  & x_k & \cdot & \cdots & \cdot
\end{matrix}
\quad = \quad
\begin{matrix}
\cdot & x_{j+1} & \cdots & x_{k+1} & \cdot & \cdots & \cdot\\
\cdot & \pi_{j} & \cdots & \pi_k & \pi_{k+1} & \cdots & \pi_{k+m}
\end{matrix}\quad +$}
\put(0,35){$\cdots \quad + \quad
 \begin{matrix}
x_j \quad x_{j+1} & \cdots & x_{i-1} & \cdot & x_{i+1} & \cdots  & x_{k+1}  & \cdot & \cdots & \cdot \\
\cdot \quad \pi_j & \cdots & \pi_{i-2} & \cdot & \pi_{i} & \cdots
& \pi_{k} & \pi_{k+1} & \cdots & \pi_{k+m}
\end{matrix} \quad + \quad \cdots
$} \put(0,5){$\quad + \quad \begin{matrix}
x_j & x_{j+1} & \cdots & x_{k-1} & x_k & \cdot & \cdot & \cdots & \cdot\\
\cdot & \pi_j & \cdots & \pi_{k-2} & \pi_{k-1} & \cdot & \pi_{k+1}
& \cdots & \pi_{k+m}
\end{matrix}$}

\end{picture}
\end{center}
\caption{Basic process I}\label{basic-pro-1}
\end{figure}

We call the above process the basic process I. We also need basic process II and III in the following, Figure \ref{basic-pro-2}
and Figure \ref{basic-pro-3} give their planar displays.
\begin{figure}[h]
\setlength{\unitlength}{2pt}
\begin{center}
\begin{picture}(180,30)
\put(27,5){\framebox(50,13)[0,0]}
\put(95,5){\framebox(60,13)[0,0]} \put(30,10){$
\begin{matrix}
\pi_{j-1} & \pi_{j} & \cdots & \pi_k \\
\cdot     & x_j     & \cdots & x_k
\end{matrix}
\quad \rightarrow \quad
\begin{matrix}
\cdot &   x_{j+1}   & \cdots & x_{k+1} \\
\pi_{j-1} & \pi_{j} & \cdots & \pi_k
\end{matrix}
$}
\end{picture}
\end{center}
\caption{Basic process II}\label{basic-pro-2}
\end{figure}
\begin{figure}[h]
\setlength{\unitlength}{2pt}
\begin{center}
\begin{picture}(220,40)
\put(27,5){\framebox(70,13)[0,0]}
\put(0,28){\framebox(70,13)[0,0]}
\put(112,5){\framebox(75,13)[0,0]} \put(3,33){$
\begin{matrix}
\cdot & \pi_{j} & \pi_{j+1} & \cdots & \pi_k  & \cdot \\
\cdot & x_j     & \pi_{j}     & \cdots & \pi_{k-1} & \cdot
\end{matrix}
\quad = \quad $} \put(30,10){$\begin{matrix}
x_j & \cdot  & \pi_{j+1} & \cdots & \pi_k  & \cdot \\
\cdot & \cdot & \pi_{j} & \cdots & \pi_{k-1} & \cdot
\end{matrix}
\quad+\quad
\begin{matrix}
\cdot & x_{j+1} & \pi_{j+1} & \cdots & \pi_k  & \cdot \\
\cdot & \cdot   & \pi_{j}     & \cdots & \pi_{k-1} & \pi_{k}
\end{matrix}$}
\end{picture}
\end{center}
\caption{Basic process III}\label{basic-pro-3}
\end{figure}

We still take a permutation $\sigma$ with one reduced
decomposition inscribed in the diagram \eqref{mtx-rd}. Let
$\mathcal{C}(\sigma,k)$ be the set of all the permutations which
are smaller than or equal to $\sigma$ for the Ehresmann-Bruhat
order with maximal length in the coset class modulo $S_k\times
S_{n-k}$. Then
\begin{lemm}\label{lem-main2} For any $k>0$ and $\sigma$ defined as above,
\begin{equation}
\pi_{\sigma}\, x_1\cdots x_k=\sum_{\nu\in
\mathcal{C}(\sigma,k)}(x_1\cdots x_k)^{\nu^{-1}}\,\pi_{\nu}.
\end{equation}
Moreover we have
\begin{equation}
\sum_{\nu\in \mathcal{C}(\sigma,k)}(x_1\cdots
x_k)^{\nu^{-1}}=K[1^k]\,\pi_{\sigma^{-1}}.
\end{equation}
\end{lemm}

To illustrate this Lemma, we take $k=3$ and
$\sigma=s_4s_5s_3s_4s_1s_2s_3$. Using the above three basic
processes, we show the commutations between the $\pi_i$ operators
and monomials by induction on rows. Figure \ref{com-dia-1} and
Figure \ref{com-dia-2} show how to apply the commutations
inductively in a planar display.
\begin{figure}[h]
\setlength{\unitlength}{2pt}
\begin{center}
\begin{picture}(220,190)

\put(2,170){$
\begin{matrix}
\cdot & \cdot & \pi_4 & \pi_5 & \cdot\\[2pt]
\cdot & \cdot & \pi_3 & \pi_4 & \cdot\\[2pt]
\cdot & \pi_1 & \pi_2 & \pi_3 & \cdot\\[2pt]
\cdot & x_1 & x_2 & x_3 & \cdot
\end{matrix}\quad = \quad \begin{matrix}
\cdot & \cdot & \pi_4 & \pi_5 & \cdot\\[2pt]
\cdot & \cdot & \pi_3 & \pi_4 & \cdot\\[2pt]
x_1 & x_2 & x_3 & \cdot & \cdot\\[2pt]
\cdot & \pi_1 & \pi_2 & \cdot & \cdot
\end{matrix}\quad+\quad\begin{matrix}
\cdot & \cdot & \pi_4 & \pi_5 & \cdot\\[2pt]
\cdot & \cdot & \pi_3 & \pi_4 & \cdot\\[2pt]
x_1 & x_2 & \cdot & x_4 & \cdot\\[2pt]
\cdot & \pi_1 & \cdot & \pi_3 & \cdot
\end{matrix}\quad + \quad
$}

\put(49,130){$ \quad \, \quad \begin{matrix}
\cdot & \cdot & &\pi_4 & \pi_5 & \cdot\\[2pt]
\cdot & \cdot & &\pi_3 & \pi_4 & \cdot\\[2pt]
x_1 & \cdot & & x_3 & x_4 & \cdot\\[2pt]
\cdot & \cdot & & \pi_2 & \pi_3 & \cdot
\end{matrix}\quad + \quad\begin{matrix}
\cdot & \cdot & \pi_4 & \pi_5 & \cdot\\[2pt]
\cdot & \cdot & \pi_3 & \pi_4 & \cdot\\[2pt]
\cdot & x_2 & x_3 & x_4 & \cdot\\[2pt]
\cdot & \pi_1 & \pi_2 & \pi_3 & \cdot
\end{matrix}
$}

\put(2,90){$
\begin{matrix}
\cdot & \cdot & \pi_4 & \pi_5 & \cdot\\[2pt]
\cdot & \cdot & \pi_3 & \pi_4 & \cdot\\[2pt]
x_1 & x_2 & x_3 & \cdot & \cdot\\[2pt]
\cdot & \pi_1 & \pi_2 & \cdot & \cdot
\end{matrix}\,\, = \quad \begin{matrix}
\cdot & \cdot & \pi_4 & \pi_5 & \cdot\\[2pt]
\cdot & x_3 & \cdot & \pi_4 & \cdot\\[2pt]
x_1 & x_2 & \cdot & \cdot & \cdot\\[2pt]
\cdot & \pi_1 & \pi_2 & \cdot & \cdot
\end{matrix}\quad+\quad\begin{matrix}
\cdot & \cdot & \pi_4 & \pi_5 & \cdot\\[2pt]
\cdot & \cdot & x_4 & \pi_4 & \cdot\\[2pt]
x_1 & x_2 & \pi_3 & \cdot & \cdot\\[2pt]
\cdot & \pi_1 & \pi_2 & \cdot & \cdot
\end{matrix} \quad =
$}

\put(2,50){$
\begin{matrix}
\cdot & \cdot & \pi_4 & \pi_5 & \cdot\\[2pt]
\cdot & x_3 & \cdot & \pi_4 & \cdot\\[2pt]
x_1 & x_2 & \cdot & \cdot & \cdot\\[2pt]
\cdot & \pi_1 & \pi_2 & \cdot & \cdot
\end{matrix}\quad + \quad \begin{matrix}
\cdot & x_4 & \cdot & \pi_5 & \cdot\\[2pt]
\cdot & \cdot & \cdot & \pi_4 & \cdot\\[2pt]
x_1 & x_2 & \pi_3 & \cdot & \cdot\\[2pt]
\cdot & \pi_1 & \pi_2 & \cdot & \cdot
\end{matrix}\quad+\quad\begin{matrix}
\cdot & \cdot & x_5 & \pi_5 & \cdot\\[2pt]
\cdot & \cdot & \cdot & \pi_4 & \pi_5\\[2pt]
x_1 & x_2 & \pi_3 & \cdot & \cdot\\[2pt]
\cdot & \pi_1 & \pi_2 & \cdot & \cdot
\end{matrix}
$}

\put(2,10){$
\begin{matrix}
\cdot & \cdot & \pi_4 & \pi_5 & \cdot\\[2pt]
\cdot & \cdot & \pi_3 & \pi_4 & \cdot\\[2pt]
x_1 & x_2 & \cdot & x_4 & \cdot\\[2pt]
\cdot & \pi_1 & \cdot & \pi_3 & \cdot
\end{matrix}\quad = \quad \begin{matrix}
\cdot & \cdot & \pi_4 & \pi_5 & \cdot\\[2pt]
\cdot & \cdot & \cdot & x_5 & \cdot\\[2pt]
x_1 & x_2 & \pi_3 & \pi_4 & \cdot\\[2pt]
\cdot & \pi_1 & \cdot & \pi_3 & \cdot
\end{matrix}\quad=\quad\begin{matrix}
\cdot & \cdot & \cdot & x_6 & \cdot\\[2pt]
\cdot & \cdot & \pi_4 & \pi_5 & \cdot\\[2pt]
x_1 & x_2 & \pi_3 & \pi_4 & \cdot\\[2pt]
\cdot & \pi_1 & \cdot & \pi_3 & \cdot
\end{matrix}
$}

\put(0,155){\framebox(45,32)[0,0]}
\Blue{\put(61,155){\framebox(47,32)[0,0]}}
\Red{\put(123,155){\framebox(47,32)[0,0]}}
\Gray{\put(57,115){\framebox(47,32)[0,0]}}
\Green{\put(119,115){\framebox(47,32)[0,0]}}
\Blue{\put(-7,75){\framebox(45,32)[0,0]}}
\Blue{\put(50,75){\framebox(47,32)[0,0]}}
\Blue{\put(112,75){\framebox(47,32)[0,0]}}
\Blue{\put(-13,35){\framebox(45,32)[0,0]}}
\Blue{\put(47,35){\framebox(47,32)[0,0]}}
\Blue{\put(110,35){\framebox(49,32)[0,0]}}
\Red{\put(-20,-5){\framebox(47,32)[0,0]}}
\Red{\put(42,-5){\framebox(47,32)[0,0]}}
\Red{\put(104,-5){\framebox(47,32)[0,0]}}

\end{picture}
\end{center}
\caption{(I) Commutations between $\pi_\sigma$ and $x_1\cdots
x_k$}\label{com-dia-1}
\end{figure}


\begin{figure}[h]
\setlength{\unitlength}{2pt}
\begin{center}
\begin{picture}(220,260)

\put(2,260){$
\begin{matrix}
\cdot & \cdot & &\pi_4 & \pi_5 & \cdot\\[2pt]
\cdot & \cdot & &\pi_3 & \pi_4 & \cdot\\[2pt]
x_1 & \cdot & & x_3 & x_4 & \cdot\\[2pt]
\cdot & \cdot & & \pi_2 & \pi_3 & \cdot
\end{matrix}\quad + \quad\begin{matrix}
\cdot & \cdot & \pi_4 & \pi_5 & \cdot\\[2pt]
\cdot & \cdot & \pi_3 & \pi_4 & \cdot\\[2pt]
\cdot & x_2 & x_3 & x_4 & \cdot\\[2pt]
\cdot & \pi_1 & \pi_2 & \pi_3 & \cdot
\end{matrix}\quad = \quad
$} \put(2,220){$
\begin{matrix}
\cdot & \cdot &\pi_4 & \pi_5 & \cdot\\[2pt]
\cdot & x_3 & x_4 & \cdot & \cdot\\[2pt]
x_1 & \cdot & \pi_3 & \cdot & \cdot\\[2pt]
\cdot & \cdot & \pi_2 & \pi_3 & \cdot
\end{matrix}\quad + \quad \begin{matrix}
\cdot & \cdot &\pi_4 & \pi_5 & \cdot\\[2pt]
\cdot & x_3 & \cdot & x_5 & \cdot\\[2pt]
x_1 & \cdot &  \cdot & \pi_4 & \cdot\\[2pt]
\cdot & \cdot  & \pi_2 & \pi_3 & \cdot
\end{matrix}\quad+\quad\begin{matrix}
\cdot & \cdot  &\pi_4 & \pi_5 & \cdot\\[2pt]
\cdot & \cdot  & x_4 & x_5 & \cdot\\[2pt]
x_1 & \cdot &  \pi_3 & \pi_4 & \cdot\\[2pt]
\cdot & \cdot  & \pi_2 & \pi_3 & \cdot
\end{matrix} \quad +
$}

\put(2,180){$
\begin{matrix}
\cdot & \cdot &\pi_4 & \pi_5 & \cdot\\[2pt]
\cdot & x_3 & x_4 & \cdot & \cdot\\[2pt]
\cdot & x_2 & \pi_3 & \cdot & \cdot\\[2pt]
\cdot & \pi_1 & \pi_2 & \pi_3 & \cdot
\end{matrix}\quad \quad + \quad \begin{matrix}
\cdot & \cdot &\pi_4 & \pi_5 & \cdot\\[2pt]
\cdot & x_3 & \cdot & x_5 & \cdot\\[2pt]
\cdot & x_2 &  \cdot & \pi_4 & \cdot\\[2pt]
\cdot & \pi_1  & \pi_2 & \pi_3 & \cdot
\end{matrix}\quad \quad+\quad\begin{matrix}
\cdot & \cdot  &\pi_4 & \pi_5 & \cdot\\[2pt]
\cdot & \cdot  & x_4 & x_5 & \cdot\\[2pt]
\cdot & x_2 &  \pi_3 & \pi_4 & \cdot\\[2pt]
\cdot & \pi_1  & \pi_2 & \pi_3 & \cdot
\end{matrix} \quad =
$}

\put(2,140){$
\begin{matrix}
\cdot & x_4 & \cdot & \cdot & \cdot\\[2pt]
\cdot & x_3 & \cdot & \pi_5 & \cdot\\[2pt]
x_1 & \cdot & \pi_3 & \cdot & \cdot\\[2pt]
\cdot & \cdot & \pi_2 & \pi_3 & \cdot
\end{matrix}\quad + \quad \begin{matrix}
\cdot & \cdot & x_5 & \cdot & \cdot\\[2pt]
\cdot & x_3 & \pi_4 & \pi_5 & \cdot\\[2pt]
x_1 & \cdot & \pi_3 & \cdot & \cdot\\[2pt]
\cdot & \cdot & \pi_2 & \pi_3 & \cdot
\end{matrix}\quad+\quad\begin{matrix}
\cdot & \cdot &\cdot & x_6 & \cdot\\[2pt]
\cdot & x_3 & \pi_4 & \pi_5 & \cdot\\[2pt]
x_1 & \cdot &  \cdot & \pi_4 & \cdot\\[2pt]
\cdot & \cdot  & \pi_2 & \pi_3 & \cdot
\end{matrix}\quad +
$}

\put(2,100){$
\begin{matrix}
\cdot & x_4  & x_5 & \cdot & \cdot\\[2pt]
\cdot & \cdot  & \pi_4 & \cdot & \cdot\\[2pt]
x_1 & \cdot &  \pi_3 & \pi_4 & \cdot\\[2pt]
\cdot & \cdot  & \pi_2 & \pi_3 & \cdot
\end{matrix}\quad + \quad \begin{matrix}
\cdot & x_4  & \cdot & x_6 & \cdot\\[2pt]
\cdot & \cdot  & \cdot & \pi_5 & \cdot\\[2pt]
x_1 & \cdot &  \pi_3 & \pi_4 & \cdot\\[2pt]
\cdot & \cdot  & \pi_2 & \pi_3 & \cdot
\end{matrix}\quad+\quad\begin{matrix}
\cdot & \cdot  & x_5 & x_6 & \cdot\\[2pt]
\cdot & \cdot  & \pi_4 & \pi_5 & \cdot\\[2pt]
x_1 & \cdot &  \pi_3 & \pi_4 & \cdot\\[2pt]
\cdot & \cdot  & \pi_2 & \pi_3 & \cdot
\end{matrix}\quad \quad +
$}

\put(2,60){$
\begin{matrix}
\cdot & x_4 & \cdot & \cdot & \cdot\\[2pt]
\cdot & x_3 & \cdot & \pi_5 & \cdot\\[2pt]
\cdot & x_2 & \pi_3 & \cdot & \cdot\\[2pt]
\cdot & \pi_1 & \pi_2 & \pi_3 & \cdot
\end{matrix}\quad + \quad \begin{matrix}
\cdot & \cdot & x_5 & \cdot & \cdot\\[2pt]
\cdot & x_3 & \pi_4 & \pi_5 & \cdot\\[2pt]
\cdot & x_2 & \pi_3 & \cdot & \cdot\\[2pt]
\cdot & \pi_1 & \pi_2 & \pi_3 & \cdot
\end{matrix}\quad+\quad\begin{matrix}
\cdot & \cdot &\cdot & x_6 & \cdot\\[2pt]
\cdot & x_3 & \pi_4 & \pi_5 & \cdot\\[2pt]
\cdot & x_2 &  \cdot & \pi_4 & \cdot\\[2pt]
\cdot & \pi_1  & \pi_2 & \pi_3 & \cdot
\end{matrix}\quad +
$}

\put(2,20){$
\begin{matrix}
\cdot & x_4  & x_5 & \cdot & \cdot\\[2pt]
\cdot & \cdot  & \pi_4 & \cdot & \cdot\\[2pt]
\cdot & x_2 &  \pi_3 & \pi_4 & \cdot\\[2pt]
\cdot & \pi_1  & \pi_2 & \pi_3 & \cdot
\end{matrix}\quad + \quad \begin{matrix}
\cdot & x_4  & \cdot & x_6 & \cdot\\[2pt]
\cdot & \cdot  & \cdot & \pi_5 & \cdot\\[2pt]
\cdot & x_2 &  \pi_3 & \pi_4 & \cdot\\[2pt]
\cdot & \pi_1  & \pi_2 & \pi_3 & \cdot
\end{matrix}\quad+\quad\begin{matrix}
\cdot & \cdot  & x_5 & x_6 & \cdot\\[2pt]
\cdot & \cdot  & \pi_4 & \pi_5 & \cdot\\[2pt]
\cdot & x_2 &  \pi_3 & \pi_4 & \cdot\\[2pt]
\cdot & \pi_1  & \pi_2 & \pi_3 & \cdot
\end{matrix}
$}

\Gray{\put(0,245){\framebox(47,32)[0,0]}}
\Green{\put(61,245){\framebox(47,32)[0,0]}}
\Gray{\put(-3,205){\framebox(45,32)[0,0]}}
\Gray{\put(57,205){\framebox(47,32)[0,0]}}
\Gray{\put(118,205){\framebox(47,32)[0,0]}}
\Green{\put(-9,165){\framebox(45,32)[0,0]}}
\Green{\put(52,165){\framebox(47,32)[0,0]}}
\Green{\put(114,165){\framebox(47,32)[0,0]}}

\Gray{\put(-15,125){\framebox(45,32)[0,0]}}
\Gray{\put(47,125){\framebox(47,32)[0,0]}}
\Gray{\put(108,125){\framebox(49,32)[0,0]}}
\Gray{\put(-21,85){\framebox(47,32)[0,0]}}
\Gray{\put(41,85){\framebox(47,32)[0,0]}}
\Gray{\put(103,85){\framebox(47,32)[0,0]}}

\Green{\put(-28,45){\framebox(45,32)[0,0]}}
\Green{\put(30,45){\framebox(45,32)[0,0]}}
\Green{\put(88,45){\framebox(45,32)[0,0]}}
\Green{\put(-34,5){\framebox(47,32)[0,0]}}
\Green{\put(25,5){\framebox(45,32)[0,0]}}
\Green{\put(82,5){\framebox(45,32)[0,0]}}

\end{picture}
\end{center}
\caption{(II) Commutations between $\pi_\sigma$ and $x_1\cdots
x_k$}\label{com-dia-2}
\end{figure}


Given $u\in\bN^n$ and $i: 1\leq i<n$, define $\phi_i(u)$ as
follows:
$$\phi_i(u)=\left\{\begin{array}{ll}u^{s_i},& u_i>u_{i+1}; \\ u, & u_i\leqslant u_{i+1}. \end{array} \right.$$
For fixed $k: 1\leq k\leq n$ let $\mathcal{E}_k(u)$ be the set of
all the distinct permutations of $u$ which are greater than or
equal to $u$ for the Ehresmann-Bruhat order and of minimum length
in their coset class modulo $S_{k}\times S_{n-k}$. Then we have
the following lemma
\begin{lemm}\label{lemm-op}
For any $i\neq k$ such that $u_i>u_{i+1}$, we have
\begin{equation}
\mathcal{E}_k(u^{s_i})=\{\phi_i(v)\, | \, v\in \mathcal{E}_k(u)\}.
\end{equation}
\end{lemm}
\proof Let $\lambda$ be the decreasing reordering of $u$, and let
$\sigma$ be the permutation such that $\lambda^{\sigma}=u$. Taking
another vector $v$, there exists a permutation $\nu$ such that
$\lambda^{\nu}=v$. Then $v\geq u$ if and only if $\nu\leq \sigma$
by checking that every simple transposition in the reduced
decomposition decreases the number of inversions by $1$.

Suppose $r_1\cdots r_m$ is one reduced decomposition of $\sigma$,
then $r_1\cdots r_ms_i$ is one reduced decomposition of $\sigma'$
where $\lambda^{\sigma'}=u^{s_i}$. For any $v=\lambda^{\nu}\in
\mathcal{E}_k(u)$, by the subword property there exists a sequence
$1\leq j_1,\cdots,j_{\ell}\leq m$ such that $r_{j_1}\cdots
r_{j_{\ell}}=\nu$. If $\phi_i(v)=v$, we immediately get $\nu\leq
\sigma'$, thus $\phi_i(v)\geq u^{s_i}$. If $\phi_i(v)=v^{s_i}$,
then $r_{j_1}\cdots r_{j_{\ell}}s_i$ is one reduced decomposition
of $\nu s_i$, thus $\nu s_i \leq \sigma'$, and one also gets
$\phi_i(v)\geq u^{s_i}$.

Since $v$ is of minimum length in the coset class modulo
$S_k\times S_{n-k}$, then $\nu$ must have the maximum length among
all the vectors smaller than $\sigma$ in the coset class, that is
to say, for any $t\neq k$ the permutation $\nu s_t$ with length
increased by $1$ is not smaller than $\sigma$. Let
$\phi_i(v)=\lambda^{\nu'}$. For the case of $\phi_i(v)=v$ if there
exists an integer $t\neq k$ such that $r_{j_1}\cdots
r_{j_{\ell}}s_t$ as a subword sequence of $r_1\cdots r_ms_i$ is
reduced. Then $t\neq i$, otherwise it is contrary to $v_i\leq
v_{i+1}$. Thus $r_{j_1}\cdots r_{j_{\ell}}s_t$ is a subword
sequence of $r_1\cdots r_m$. This is a contrary to the minimum
length of $v$. For the case of $\phi_i(v)=v^{s_i}$ if there exists
an integer $t\neq k$ such that $r_{j_1}\cdots r_{j_{\ell}}s_is_t$
as a subword sequence of $r_1\cdots r_ms_i$ is reduced. Then we
must have a subword sequence of $r_1\cdots r_m$ with length
greater than $\ell$ such that it is also reduced. This is also a
contrary to the minimum length of $v$. Thus we obtain $\phi_i(v)$
must have the minimum length among all the vectors greater than
$u^{s_i}$ in the coset class.

Conversely, following the above arguments, one can check that for
any $v'\in \mathcal{E}_k(u^{s_i})$ there exists a vector $v\in
\mathcal{E}_k(u)$ such that $v'=\phi_i(v)$. \qed


\section{Pieri formula for key polynomials}
In this section, we will prove the following two theorems:
\begin{theo}
Given $J\in \bN^n$, let $k$ be such that
 $j_1\geq \cdots \geq j_k$, $j_{k+1}\geq \cdots \geq j_n$.
Then
\begin{equation}\label{pf-1}
\Kh_J \, x_k\cdots x_1 =  K_{J+ [1^k\, 0^{n-k}]}
\end{equation}
and
\begin{equation}
K_J\, x_n\cdots x_{k+1} = \Kh_{J+[0^k\, 1^{n-k}]}.
\end{equation}
\end{theo}
\proof  $\Kh_J$ and $\Kh_J$ are the images of $x^\lambda=
K_\lambda=\Kh_\lambda$ (with $\lambda=$ decreasing reordering of
$J$), under some $\bp_\sigma$ or $\pi_\sigma$ respectively. These
two operators can be realized as
 a sequence of isobaric divided differences
 inscribed in the diagram of a partition
in the South-East corner of the rectangles
\begin{equation*}
 \begin{matrix}  \bp_{n-k} & \cdots & \bp_{n-1} \\
                  \vdots  &         & \vdots \\
                  \bp_1   & \cdots        & \bp_k
\end{matrix}
\qquad \text{or}\qquad
\begin{matrix}  \pi_{n-k} & \cdots & \pi_{n-1} \\
                  \vdots  &         & \vdots \\
                  \pi_1   & \cdots        & \pi_k
\end{matrix}   \ .
\end{equation*}
By Lemma \ref{lem-main}, we have
\begin{equation}
\bp_{\sigma}x_k\cdots x_1 =(x_k\cdots x_1)^{\nu}\pi_{\sigma},
\quad \pi_{\sigma}x_n\cdots x_{k+1}=(x_n\cdots
x_{k+1})^{\nu}\bp_{\sigma},
\end{equation}
where $\nu=\sigma^{-1}$. One concludes by checking that
multiplying $x^\lambda$ by one of the two monomials corresponds to
adding $[1^k\, 0^{n-k}]$ or $[0^k\, 1^{n-k}]$ to $J$. \qed

\begin{theo}
Given $J\in \bN^n$, then for any $k$ we have
\begin{equation}\label{pf-2}
K_J\, x_1..x_k = \sum_{I\in \mathcal{E}_k(J)} K[I +[1^k,0^{n-k}]],
\end{equation}
sum over all $I$ which are $\geq J$ (for the Ehresmann-Bruhat
order) and of minimum length in their coset class modulo $S_k
\times S_{n-k}$.
\end{theo}
\proof Let $u=(j_1,\,\ldots,\,j_k)$ and
$v=(j_{k+1},\,\ldots,\,j_n)$. First we prove the special case
where both $u$ and $v$ are decreasing. Let $\lambda$ be the
decreasing reordering of $J$, then there exists a permutation
$\sigma$ with one reduced decomposition inscribed in the diagram
\eqref{mtx-rd} such that $J=\lambda^\sigma$. Now from the
definition of key polynomials we deduce that
\begin{equation}
K_J\,x_1\cdots x_k=(x_1^{\lambda_1}x_2^{\lambda_2}\cdots
x_n^{\lambda_n}\, \pi_{\sigma})\,x_1\cdots
x_k=(x_1^{\lambda_1}x_2^{\lambda_2}\cdots x_n^{\lambda_n})\,
\pi_{\sigma} \,x_1\cdots x_k.
\end{equation}
By Lemma \ref{lem-main2}, we have
\begin{equation}
K_J\,x_1\cdots x_k=(x_1^{\lambda_1}x_2^{\lambda_2}\cdots
x_n^{\lambda_n})\sum_{\nu\in \mathcal{C}(\sigma,k)}(x_1\cdots
x_k)^{\nu^{-1}}\,\pi_{\nu}=\sum_{I\in \mathcal{E}_k(J)} K[I
+[1^k,0^{n-k}]].
\end{equation}

For general $J$ we don't have $u$ and $v$ are decreasing. Let $u'$
and $v'$ be decreasing reordering of $u$ and $v$ respectively.
Then $K_J$ is obtained from $K[u',v']$ by applying a series of
isobaric divided differences (where $\pi_k$ is not a factor).
Notice that $K[J]$ is symmetric in $x_i$ and $x_{i+1}$ if
$j_i<j_{i+1}$, which means that in this case we have $K_J\pi=K_J$.
By successively using Lemma \ref{lemm-op}, we get the desired
theorem. \qed

\section{Decomposition of Schubert polynomials}

The preceding Pieri formula allows us to give a generation of
Schubert polynomials, providing their decomposition in terms of
key polynomials.
\begin{theo}\label{theo-dec}
 Given $J\in \bN^n$, let $k$ be minimum such that $j_k=0$
(if it does not exist, replace $J$ by $J0$). Let $I=[j_1-1,\ldots,
j_{k-1}-1, j_{k+1},\ldots, j_n]$. Then
\begin{equation}
  Y_J = Y_I\ \pi_{n-1}\cdots \pi_k\ x_{k-1}\cdots x_1.
\end{equation}
\end{theo}

\proof Notice that $x_{k-1}\cdots x_1$ commutes with
$\pi_{n-1}\cdots \pi_k$, and therefore
$$
\begin{array}{rcl}
Y_I\ \pi_{n-1}\cdots \pi_k\ x_{k-1}\cdots x_1 & = &
 Y_I (x_{n-1}\cdots x_k)(x_{k-1}\cdots x_1) \d_{n-1}\cdots \d_k\\
& = & Y_{I+1^{n-1}} \, \d_{n-1}\cdots \d_k= Y_J.
\end{array}
$$
 \qed

Consequently the decomposition of $Y_I$ in terms of key
polynomials gives the decomposition of $Y_J$. Let
\begin{equation}
Y_I=\sum_{u}c_u\,K_u,
\end{equation}
Then
$$
\begin{array}{rcl}
Y_J & = & (\sum_{u}c_u\,K_u)\ \pi_{n-1}\cdots \pi_k\ x_{k-1}\cdots
x_1\\[5pt]
& = & \sum_{u}(c_u\,K_u)\ \pi_{n-1}\cdots \pi_k\ x_{k-1}\cdots
x_1\\[5pt]
& = & \sum_{u}c_u\,(K_{u'}\ x_{k-1}\cdots x_1)\\[5pt]
& = & \sum_{u}c_u\sum_{v}K_v=\sum_{v'}c_{v'}K_{v'}
\end{array}
$$

An immediate consequence of this theorem is that any Schubert
polynomials can be expressed as the image of $1$ under the action
of a product of isobaric divided differences and monomials
$x_1x_2\cdots x_k$.

\section{Noncommutative Pieri formula}

Given an infinite totally ordered alphabet $\A$ with
noncommutative letters, let $\A_n=\{ a_1,\ldots, a_n\}$, and let
$\Plax$ be the plactic algebra of $\A$.

Let $\Sym(\A_n)$ be the linear span of the Schur functions in
$\A_n$. We denote the elementary symmetric function of order $k$
in $A_n$ by $\L^k(A_n)$.

Define the \emph{Schubert Module} to be the  subspace of $\Plax$~:
$$ \Schub = \cdots \otimes
              \Sym(\A_3) \otimes \Sym(\A_2) \otimes \Sym(\A_1) $$
linearly generated by finite products of symmetric polynomials (
respecting the order $\ldots, \A_3,\A_2,\A_1$).

It is known that $\Sym(\A_n)$ has a basis $\{P_J\ |\ J\leq
[\ldots, 3, 2, 1, 0]\}$ \cite{ssp} where for $J\in \bN^n$
\begin{equation}
P_J = \L^{j_1}(\A_{n-1})\cdots \L^{j_{n}}(\A_0).
\end{equation}

Let $ev$ be a map which sends $a_i$ to $x_i$ for each $i$, then
$\{ev(P_J)\}$ is a basis of $\mathfrak{Pol}$.

Let $\lambda$ be a partition, then $\cdots
a_3^{\lambda_3}a_2^{\lambda_2}a_1^{\lambda_1}$ is defined as the
free key polynomials corresponding to $\lambda$, which belongs to
$\Schub$. The operators $\pi_i^a$ and $\bp_i^a$ introduced in
\cite{keys} are the operators which act on $\Plax$, and they
preserve the module $\Schub$. Notice that they don't satisfy the
braid relations, i.e., there is no operator $\pi_{\sigma}^a$ or
$\bp_{\sigma}^a$ on the free algebra. However we can still define
the free key polynomials recursively as shown in \cite{keys}
\begin{equation}
K_J=K_{J'}\pi_i^a \quad \mbox{and} \quad \Kh_J=\Kh_{J'}\bp_i^a,
\end{equation}
where $J_i<J_{i+1}$ and $J'=J^{s_i}$. Thus the free key
polynomials constitute another basis of $\Schub$.

The following figure shows the relations between these several
algebras.
\begin{figure}[h]
\setlength{\unitlength}{2pt}
\begin{center}
\begin{picture}(180,70)
\put(30,20){$\mathfrak{Pol}$} \put(30,50){$\Schub$}
\put(55,50){$\hookrightarrow$} \put(70,50){$\Plax$}
\put(35,35){$\downarrow$}

\put(110,20){$\Sym(X_n)$} \put(140,20){$\hookrightarrow$}
\put(150,20){$\mathfrak{Pol}$} \put(140,50){$\hookrightarrow$}
\put(150,50){$\Plax$} \put(110,50){$\Sym(A_n)$}
\put(155,35){$\downarrow$} \put(120,35){$\large{\wr}
\small{\mid}$}

\put(65,40){\vector(-1,-1){10}}

\end{picture}
\end{center}
\end{figure}

Notice that Pieri formulas \eqref{pf-1} and \eqref{pf-2} are also
true in the Schubert module, because both the divided differences
$\pi_i^a, \bp_i^a$ and the standard monomial $a_k \cdots a_1$
preserve the Schubert module. These corresponding formulas are
called noncommutative Pieri formulas. By Theorem \ref{theo-dec},
we also have the decomposition of free Schubert polynomial in
terms of free key polynomials.

\end{document}
