%This is an AMS-Latex1.2 file
\documentclass[12pt]{amsart} 
\usepackage{amssymb,amsmath,amscd} 
\pagestyle{plain}  
\textwidth 444pt \oddsidemargin 20pt \evensidemargin 20pt 
\headsep 0pt \flushbottom  \textheight 630pt 
\theoremstyle{plain} 
\newtheorem{Lem}{Lemma}[section]
\newtheorem{Thm}[Lem]{Theorem} 
\newtheorem{Prop}[Lem]{Proposition} 
\newtheorem{Cor}[Lem]{Corollary}
\newtheorem{Def}[Lem]{Definition} 
\theoremstyle{definition} 
\newtheorem{Rem}[Lem]{Remark} 
\newtheorem{Ex}[Lem]{Example}
\theoremstyle{remark}
\errorcontextlines=0  \numberwithin{equation}{section} 
\newcommand{\C}{\mathbb C} 
\newcommand{\R}{\mathbb R} 
\newcommand{\Q}{\mathbb Q} 
\newcommand{\Z}{\mathbb Z} 
\newcommand{\N}{\mathbb N} 
\newcommand{\X}{\mathbb X} 
\newcommand{\LL}{\mathbb L}
\newcommand{\D}{\mathbb D}
\newcommand{\dcal}{\mathcal D} 
\newcommand{\scal}{\mathcal S}
\newcommand{\ooo}{\overline} 
\newcommand{\lae}{\overleftarrow{E}} 
\newcommand{\rae}{\overrightarrow{E}} 
\newcommand{\gdw}{\Leftrightarrow} 
\newcommand{\lra}{\longrightarrow} 
\newcommand{\Lra}{\Longrightarrow} 
\newcommand{\epu}{1_{+}^{\uparrow}} 
\newcommand{\epd}{1_{+}^{\downarrow}} 
\newcommand{\eh}{\hat{e}} 
%\renewcommand{\baselinestretch}{1.1}

\begin{document} 
\title{Recursive and combinatorial properties of Schubert polynomials}
\date{March 1995, revised November 1996}
\author[R. Winkel]{Rudolf Winkel} 
\address{Institut f\"ur Reine und Angewandte Mathematik \\  RWTH Aachen \\ 
D-52056 Aachen \\ Germany\\ \hfill  {\it papers/preprints}: 
http://www.iram.rwth-aachen.de/ $\sim$winkel/} 
\email{winkel@iram.rwth-aachen.de}

 
\begin{abstract} We describe two recursive methods for the 
calculation of Schubert polynomials and use them to give new relatively simple 
proofs of their basic properties. 
Moreover, we present (1) methods for the calculation of a reduced word for 
a permutation from its Lehmer code (and other small algorithms for 
the manipulation of Lehmer codes), (2) new determinantal formulas for 
certain Schubert polynomials, which `interpolate' the well known 
formulas for Schur polynomials, and (3) a fast and simple method for 
the recursive calculation of Schubert polynomials avoiding divided 
differences (thereby avoiding completely the computation of 
intermediary terms, which eventually cancel). 
The paper can be read as a short self contained introduction to Schubert 
polynomials providing full proofs.
\end{abstract}
\maketitle 
								  
Schubert polynomials are named in honor of the German $19^{th}$ century 
school teacher Hermann Schubert and his work on ``enumerative 
geometry" ([Sb]). In 1973/74 I.N. Bernstein, I.M. Gelfand and S.I. Gelfand 
 and independently M. Demazure in his work on desingularisation of 
Schubert varieties observed that the ``Schubert Calculus" (always the 
same Schubert !) for cohomology classes of flag manifolds can be  
substituted by much 
simpler algebraic manipulations in the coinvariant algebra for Coxeter 
groups (for details see Hillers book [Hi]). 
From 1982 on A. Lascoux and M.-P. Sch\"{u}tzenberger showed in a  
sequence of papers (cf. [LS] and references therein) that for the 
symmetric groups this calculus can be simplified even more 
using an algebra of difference operators and finally using polynomials --- 
called Schubert polynomials by them. It turned out that these 
polynomials did not only have geometrical meaning, but also had  
important applications in subjects such as Newton interpolation in several 
variables, representation and invariant theory of the symmetric and the 
general linear groups and in computer algebra (cf.[KKL]).  
 
For $n\in \N$ let $S_{n}\equiv S_{ \{ 1,\dots,n \} }$ denote the group 
of permutations of the `letters' $1,\dots,n$ 
and $S_{\infty}:=\bigcup_{n>0} S_{n}$ the set 
of all finite permutations, where the union of the $S_{n}$'s uses for  
$m\geq n$ the identification of $S_{n}$ with the stabilizer of 
$n+1,\dots,m$ in $S_{m}$. The set of all Schubert polynomials 
$\scal_{\infty } :=\{X_{\pi} |\pi \in S_{\infty}\}$ (well defined by 
Prop.3.1\,i) ) then forms a basis of the polynomial ring 
$\Z[x]:=\Z[x_{1},x_{2},\dots]$.  
 
Much of the importance of Schubert polynomials is due to the 
fact that they contain as a subset the set of all Schur polynomials  
$\{ \{ \lambda \}^{s} | \lambda \vdash n, n\in\N \}$ in s variables, 
where `$\lambda\vdash n$' means that 
$\lambda=(\lambda _{1},\dots,\lambda _{s}) $ is a {\it partition} of $n$, 
i.e. $\lambda_{1}\geq\dots\geq \lambda _{s} \geq 0$ and  
$|\lambda |=\lambda _{1}+\dots +\lambda_{s}=n$ .  
The Schur polynomials in $n$ variables form the basis for 
the rings $\Z[x]^{S_{n}}:=\Z[x_{1},\dots, x_{n}]^{S_{n}}$ of symmetric 
polynomials and they generate [are] the irreducible characters of 
the ordinary representations of the symmetric [the general linear] 
groups. Because the computation of the structure constants of the algebras  
$\Z[x]^{S_{n}}$ with respect to the Schur polynomials as basis involves 
rather cumbersome manipulations of tableaux according to the 
Littlewood-Richardson rule it came as a relief that multiplication 
of Schubert polynomials (and therefore Schur functions) can be 
accomplished by merely manipulating permutations. This is the core of 
the use of Schubert polynomials in computer algebra (cf. [KKL]). 
 
The present paper investigates the basic theory of Schubert polynomials  
from the angle of their recursive structure thereby complementing the 
existing introductions [K,KKL,M1,M2]. The recursive structure on 
$\scal_{\infty}$ 
described here provides as a new tool `long induction', i.e. induction over  
all permutations $\pi \in S_{\infty }$, which enables us to give  
new and sometimes much easier proofs of the basic properties of Schubert 
polynomials. `Long induction' is also one of the fundamental devices in our 
proof of ``Kohnert's conjecture'' [W], an extremely elegant combinatorial rule 
for the generation of the Schubert polynomials. 
On the level of computations the recursive structure makes it possible to 
use an already known (and stored) set $\scal_{n}$ of Schubert polynomials  
as the point of departure for the computation  
of `higher' Schubert polynomials instead of always making a new start. 
 
Section 1 introduces Lehmer codes, reduced words, divided differences  
and Schubert polynomials, and describes their main properties.  
Section 2 introduces recursive structures for permutations and their  
Lehmer codes and gives a first method for the computation of a reduced 
word for any permutation. Section 3 describes two recursive 
structures for Schubert polynomials, which we call, respectively,  
`the up case' and `the down case' of the `long bijective stair' for reasons 
explained in this section.  
Section 4 investigates these recursive structures under the 
viewpoint of concrete calculations and gives a second method for the 
computation of a reduced word for a permutation. Section 5 contains new 
proofs of the basic properties of Schubert polynomials with the help of long 
induction (in the up case). It also contains new determinantal formulas 
for all Schubert polynomials, which are `passed by' on the way, i.e. by 
following the up case recursive structure, to Schur polynomials.
Finally, Section 6 contains the basic theorems and formulas for 
`multiplication involving Schubert polynomials' and also 
presents a simple recursive method for the calculation of Schubert 
polynomials based on Bruhat, which avoids divided differences, and is 
especially economical for the calculation of a whole set $\scal_{n}$. 
 
\section{Basic material and the definition of Schubert polynomials} 
 
Let $\N_{0}^{*}$ \ [and $\Z^{*}$] denote the set of all finite nonempty words 
in the ``alphabet" $\N_{0}=\{0,1,2,\dots\}$ \ [and $\Z$] ; then the usual 
linear 
order on $\N_{0}$ induces a lexicographic order `$\leq$' on $\N_{0}^{*}$. 
For all $n\in\N$  we define the word $E_{n}:=n-1\ \dots 1\ 0\in \N_{0}^{*}$ 
and the subsets of words 
$\dcal_{n}:=\{ d=d_{1}\dots d_{n}) | 0\leq d_{\nu } \leq n-\nu ,\ \nu =1,\dots,n \}$; 
clearly $d\leq E_{n}$ for all $d\in \dcal_{n}$. Moreover let $\Z_{E_{n}}[x]$ 
denote the $\Z$-submodule of $\Z[x]$ generated finitely free by the set of 
monomials  
$\{ x^{d}:=\prod_{v=1}^{n} x_{\nu }^{d_{\nu }}\ |\ d\in \dcal_{n} \}$. 
The rank of $\Z_{E_{n}}[x]$ is $n!$ and  
$\Z[x]=\bigcup_{n\in \N} \Z_{E_{n}}[x]$, 
where for all $m,n\in\N, m>n$ the inclusion of sets 
$\dcal_{n}\hookrightarrow \dcal_{m}\ , d\mapsto d\ 0 \dots 0$ extends to 
an embedding of $\Z_{E_{n}}[x]$ into $\Z_{E_{m}}[x]$.  
 
To every permutation $\pi \in S_{n}$ one can associate its {\it 
Lehmer code} $L(\pi )\equiv \ooo{l_{n-1} \dots l_{1}\ l_{0}}$ 
with $l_{n-i}(\pi ):=\sharp\{ j | j>i, \pi j<\pi i\}  
=\sharp\{ $ all letters to the right of place $i$ less than $\pi i \}$ 
for $i=1,\dots,n$, e.g. $L(35142)=\ooo{23010}$ or $35142\approx \ooo{23010}$. 
This sets up a bijection $L$ between $S_{n}$ and 
$\LL_{n}:=\{ l:=\ooo{l_{n-1} \dots l_{1}\ l_{0}}\ |\ 0\leq l_{\nu 
}\leq\nu, \nu =0,\dots,n-1 \}$, as we will see in Section 2 below. 
We will often use the notation 
$k_{+}(k_{1} \dots k_{s}):= k_{1}+k \dots k_{s}+k$ for $k \in\Z$ and 
words $k_{1} \dots k_{s}\in \Z^{*}$; a first instance of this is the 
following: the embeddings of $S_{n}$ into $S_{m}$  
given by $\pi \mapsto \pi 1 \dots \pi n\  n+1 \dots m$ and 
$\pi \mapsto 1 \dots m-n \ (m-n)_{+}(\pi 1 \dots \pi n)$ 
induce the inclusions of $\LL_{n}$ into $\LL_{m}$ given by  
$l \mapsto l\ \ooo{0\dots 0}$ and $l \mapsto \ooo{0\dots 0}\ l$, 
which we call, 
respectively, (left) embedding and right embedding; for example  
$\pi=34152\in S_{5}$ with $L(\pi)=\ooo{22010}$ is (left) embedded into 
$S_{8}$  as $34152678$ with Lehmer code $\ooo{22010000}$ and right embedded 
into $S_{8}$  as $12367485$ with Lehmer code $\ooo{00022010}$. 
 
A mere re-indexing of components ($d_{\nu } \leftrightarrow l_{n-\nu}$)  
now gives a bijection between 
$\LL_{n}$ and $\dcal_{n}$ and so ties together several infinite structures, 
which are build up (as `direct limits') from finite structures of increasing 
size using natural embeddings: 
the polynomial ring $\Z[x]=\bigcup_{n>0} \Z_{E_{m}}[x]$, the set  
$\dcal_{\infty }:=\bigcup_{n>0} \dcal_{n}=\N_{0}^{*}$ of all 
finite sequences of nonnegative integers, the set  
$\LL_{\infty }:=\bigcup_{n>0} \LL_{n}$ of all Lehmer codes and the 
group $S_{\infty }:=\bigcup_{n>0} S_{n}$ of all finite permutations 
of $\N$. 
 
Let $\{\ P_{\pi} \mid \pi\in S_{n}\ \}$ ($n\in \N$) be any subset of 
polynomials from $\Z_{E_{n}}[x]$ indexed by the permutations $\pi\in S_{n}$ 
and for $p\in\Z[x]$ let $lmin(p)$ denote the monomial  
of $p$ with the lexicographically smallest exponent; then  
the property \begin{description} \item [(B)] 
$lmin(P_{\pi }) = x^{L(\pi )}$ with coefficient 1 for all 
polynomials in $\{\ P_{\pi} \mid \pi\in S_{n}\ \}$ \end{description}  
is called the {\it basis property}, since  
(B) implies that $\{\ P_{\pi} \mid \pi\in S_{n}\ \}$ is a basis for 
the $\Z$-module $\Z_{E_{n}}[x]$ :  
take any polynomial $p\in \Z_{E_{n}}[x]$, then by (B) there exists a $\pi\in 
S_{n}$ such that $p=\alpha x^{L(\pi )}+\dots$ with $x^{L(\pi )}=lmin(p)$; 
therefore $p= \alpha P_{\pi } + p'$  and $p' \in \Z_{E_{n}}[x]$ 
with $lmin(p')>lmin(p)$ proving the assertion by induction.  
In Section 5 we will show that the set $\scal_{n}$ of Schubert polynomials 
indexed by the $\pi\in S_{n}$ has the basis property (B). 
 
The symmetric groups $S_{n}$ are special Coxeter groups (cf. [Hi,Hu]) 
generated by the {\it elementary transpositions} 
$\sigma _{i}:=(i,i+1)$ ( $i=1,\dots,n-1$ ) 
with relations: (i)\ $\sigma _{i}^{2}=id$, 
(ii)\ $\sigma _{i}\sigma _{j}=\sigma _{j}\sigma_{i}$, if $|i-j|>1$, and  
(iii)\ $\sigma _{i}\sigma _{i+1}\sigma _{i}= 
\sigma _{i+1}\sigma _{i}\sigma _{i+1}$. Clearly, 
for every $\pi \in S_{n}$ there exists a minimal number $l(\pi )\in\N_{0}$ 
called the {\it length} of $\pi $, such that $\pi$ is the product of  
$l(\pi )$ elementary transpositions:  
$\pi=\sigma _{i_{1}} \dots\sigma _{i_{l(\pi)}}$. The set 
$R(\pi)$ of all such minimal expressions for $\pi $ is called the set  
of {\it reduced words}. (When dealing with reduced words, we almost always 
omit the $\sigma$'s and write simply the indices $i_{1}\dots i_{l(\pi )}$.) 
In Lemma 2.1 below we show that  
$l(\pi )=|L(\pi )|:= \sum_{\nu =0}^{n-1} l_{\nu }(\pi )$, because  
both numbers are equal to the number of inversions in $\pi$. 
 
The {\it weak Bruhat order}, denoted by `$\leq_{w}$', on the 
$S_{n}$'s is defined as the transitive closure of the following covering 
relation: let $\pi,\ \mu \in S_{n}$, then `$\pi$ is covered by $\mu$', 
( in signs: $\pi \leq_{w}\cdot\ \mu$ )\ $:\gdw$ \ $\mu=\pi \sigma_{k}$ for 
some $k\in\{1,\dots,n-1\}$ and $l(\mu)=l(\pi) +1$. 
If we replace the elementary transpositions 
$\sigma_{k}$ in this definition by arbitrary transpositions $(i,j)$ 
($1\leq i < j \leq n$) in $S_{n}$, then the resulting richer order is 
called {\it Bruhat order}, `$\leq_{B}$'. 
(What we have defined just now are strictly 
speaking `right' orders, because the transpositions act on the right or on 
the `places' of the permutations; similarly `left' orders are defined by 
using the left action on the `numbers' or `letters', but we will not 
use these (isomorphic) orderings here.) 
 
We quote two fundamental results for the Bruhat order, which have easily 
accessible proofs in the literature. \\
 
{\bf Exchange Condition} ( [Hi, Thm.I.3.7], [Hu, Sec.1.7], [K, 1.3.29] ) 
Let $\pi\in S_{\infty}$, $p=l(\pi)$ and $i_{1}\dots i_{p},\ j_{1}\dots j_{p} 
\in R(\pi)$, then there is a unique $k\in\{1,\dots,n\}$, such 
that $j_{1}\ i_{1}\dots i_{k-1}\ i_{k+1}\dots i_{p}\in R(\pi)$.\\ 
 
{\bf Subword Property} ( [Hi, Cor.I.6.5-6], [Hu, Thm.5.10] ) 
Let $\pi\in S_{\infty}$, $p=l(\pi)$ and 
$\pi=\sigma_{i_{1}} \dots \sigma _{i_{p}}$ an arbitrary reduced decomposition; 
then $\pi' \leq_{B} \pi$ iff $\pi'=\sigma_{j_{1}} \dots \sigma _{j_{p'}}$ 
for some subword $j_{1}\dots j_{p'}$ of $i_{1}\dots i_{p}$.\\ 
 
There is a natural action of $S_{\infty}$ on $\Z[x]$ given by 
$\pi(f)\equiv \pi(f(x)):= f(x_{\pi 1}, x_{\pi 2}, \dots)$. Using this 
action the {\it divided difference operators} $\partial_{i}$ are  
for all $f\in\Z[x]$ and $i\in\N$ defined by \begin{equation*} 
\partial_{i} f =\frac{f-\sigma _{i}(f)}{x_{i}-x_{i+1}}\ .\end{equation*} 

We list some easily verifiable properties of the $\partial_{i} $ :\\ 
they obey the same relations as the $\sigma _{i}$ except that (i) 
now reads $\partial_{i}^{2}=0$; \\ 
$\partial_{i} f$ is symmetric in $x_{i}$ and $x_{i+1}$; \\ $\partial_{i} 
f \equiv 0$, if $f$ is already symmetric in $x_{i}$ and $x_{i+1}$;\\ 
if $f$ is homogeneous of degree m, then $\partial_{i} f$ is homogeneous 
of degree m-1 or $\partial_{i} f\equiv 0$; \\ the product rule is given by 
\begin{equation*} \partial_{i}(fg)=(\partial_{i} f) g +( \sigma _{i}(f) ) 
(\partial_{i} g) \ {\rm for}\  f,g\in\Z[x]\ ; \end{equation*} 
the quotient rule by \begin{equation*} \partial_{i} \frac{f}{g}= 
\frac{(\partial_{i} f) (  \sigma _{i}(g) )  
-( \sigma _{i}(f) ) (\partial_{i} g)} 
{g \ \sigma _{i}(g) }\  {\rm for}\  f,g\in\Z[x]\ ; \end{equation*} 
$\partial_{i} $ is  $\Z$-linear, but the product rule also  
implies linearity of $\partial_{i} $ with respect to the 
multiplication by functions symmetric in $x_{i}$ and $x_{i+1}$; therefore \\  
one has to calculate $\partial_{i} $ only for monomials  
$x_{i}^{d_{i}} x_{i+1}^{d_{i+1}}$ with $\min \{ d_{i},d_{i+1} \}=0$ : 
\begin{equation*} 
\partial_{i} (x_{i}^{k+1} x_{i+1}^{0}) = \sum_{\nu=0}^{k} 
x_{i}^{k-\nu} x_{i+1}^{\nu}\ \ \ {\rm for}\  k\in\N_{0}\ , \end{equation*} 
and interchanging the role of $x_{i}$ and $x_{i+1}$ in the preceding 
formula does only change the sign of the sum, because $\partial_{i} 
(f\circ \sigma _{i})= -\partial_{i} f$; \\ thus divided differences are 
just a convenient way to describe a {\it symmetrisation} process: 
more specifically we will speak of {\it i-symmetrisation} in the case  
of application of $\partial_{i} $. 
 
Calculation in $\Z[x]$ can be done conveniently using only the 
exponent tuples: let $\Z\dcal_{\infty }$  be the $\Z$-module freely 
generated on the set $\dcal_{\infty }$; then a distributive multiplication 
on $\Z\dcal_{\infty }$ can be defined as the $\Z$-linear extension of the  
`product' of two elements of $\dcal_{\infty }$, which is simply  
componentwise addition. Clearly $\Z[x]$ and $\Z\dcal_{\infty }$ are isomorphic 
as rings, and we denote the operator of i-symmetrisation on 
$\Z\dcal_{\infty }$ by $\partial_{i} $ as well. 
 
\begin{Ex} $\partial_{1}\ ( x_{1}^{3} x_{2}^{2} x_{3}^{1} ) = 
x_{1}^{2} x_{2}^{2} x_{3}^{1}$ in $\Z[x]$ transfers to $\partial_{1} 
( 321 )= 221$ in $\Z\dcal_{\infty }$. And 
$\partial_{2}\ ( 2\cdot 1302 + 0121 + 
1332) =  2\cdot (1202+1112+1022) - 0111 +0$.\end{Ex}
 
\begin{Prop} Let $\pi\in S_{\infty}$, then by a chain of 
transformations according to the relations (ii) and (iii) \\ 
a) every word $\in R(\pi)$ can be transformed into every other word 
$\in R(\pi)$ and \\ 
b) every non-reduced word representing $\pi$ into a word of the form  
$\dots \sigma_{i} \sigma_{i} \dots$ for some $i$.\end{Prop} 
\begin{proof} of a):\ Let $\pi\in S_{\infty}$, $p=l(\pi)$ and 
$i_{1}\dots i_{p},\ j_{1}\dots j_{p} \in R(\pi)$. We proceed by 
induction over $p$. If $p=0$ or $p=1$ the assertion is trivial, so 
let $p\geq 2$. If $i_{1}=j_{1}$, we are done by induction hypothesis, 
hence assume $i_{1}\neq j_{1}$ and in addition $|i_{1}-j_{1}|>1$.  
The Exchange Theorem then shows that 
$j_{1}\ i_{1}\dots i_{k-1}\ i_{k+1}\dots i_{p}\in R(\pi)$ 
for a uniquely determined $k\in\{1,\dots,n\}$, which by relation (ii) can be 
transformed into $i_{1}\ j_{1}\dots i_{k-1}\ i_{k+1}\dots i_{p}\in R(\pi)$. 
On the other hand every word $i_{1}\dots$ or $j_{1}\dots \in R(\pi)$ 
can be transformed to $i_{1}\ j_{1}\dots i_{k-1}\ i_{k+1}\dots i_{p}$ or 
$j_{1}\ i_{1}\dots i_{k-1}\ i_{k+1}\dots i_{p}$ as seen already. 
 
It remains to investigate the case $i_{1}\neq j_{1}$ and $|i_{1}-j_{1}|=1$. 
Apply the Exchange Theorem to $j_{1}\ i_{1}\dots i_{k-1}\ i_{k+1}\dots i_{p}$ 
and $i_{1}\dots i_{p} \in R(\pi)$; there are essentially three 
different possibilities to cancel a number from 
$i_{1} j_{1} i_{1}\dots i_{k-1}\ i_{k+1}\dots i_{p}$: $1^{st}$) cancel 
$j_{1}$, then the remaining word is certainly not reduced, $2^{nd}$) 
cancel $i_{1}$ on the second place, then the remaining word may be 
reduced, but certainly not for $\pi$, and so it only remains to  
$3^{rd}$) cancel one of the numbers  
$i_{2},\dots, i_{k-1}, i_{k+1},\dots, i_{p}$. Hence we get a word 
$i_{1}\ j_{1}\ i_{1}\dots \in R(\pi)$, which by relation (iii) can be 
transformed to $j_{1}\ i_{1}\ j_{1}\dots \in R(\pi)$. The argument is 
now completed as above, which finally shows a). 
 
For the proof of part b) we proceed by induction over the length $p$ 
of {\em non-reduced} words $i_{1}\dots i_{p}$ representing some $\pi\in 
S_{\infty}$. Clearly for $p\in \{ 0,1 \}$ there are no non-reduced 
expressions and for $p=2$ the only possibility is $i_{1}\ i_{2}\equiv  
i_{1}\ i_{1}$; assume therefore that $p \geq 3$ and the subword 
$i_{2}\dots i_{p}$ of $i_{1}\dots i_{p}$ is $\in R(\mu)$ for some $\mu$; 
otherwise we are done by induction hypothesis. Since $i_{1}\dots i_{p}$ 
is a non-reduced representation of $\pi$, we must have $l(\pi)\leq 
l(\mu)$; on the other hand multiplication by an elementary 
transposition changes the length exactly by $\pm 1$ (cf. Lemma 2.1 i) ),  
hence $l(\pi)=l(\mu)-1$, which can only be achieved, if $i_{1}\dots i_{p}$ 
can also be represented by $i_{1}\ i_{1}\dots $.
\end{proof} 
 
It is now possible to define $\partial_{\pi }:=  
\partial_{i_{1}}\dots \partial_{i_{l(\pi)}}$	using any  
reduced word $i_{1}\dots i_{l(\pi )}$ for $\pi$, because the 
result is independent of the special reduced sequence chosen: 
simply use case a) of the above Prop. and observe that the $\partial_{i}$ 
obey the same relations (ii) and (iii) as the $\sigma _{i}$. 
Similarly one gets $\partial_{i_{1}}\dots \partial_{i_{p}}=0$ for 
every non-reduced sequence $i_{1}\dots i_{p}$ from Prop. 1.2 b) and 
$\partial_{i}^{2}=0$.  
(When looking to [K,KKL], be aware that the `$\partial_{\pi} $' there is the 
same as $\partial_{\pi^{-1}}$ in the notation of [M1, M2] and the 
present paper.) 
	     
Permutations of special importance are the  
$\omega _{n}:=n\dots 1= L^{-1}(E_{n})=(1,n) (2,n-1)\dots= 
\omega _{n}^{-1}$ of maximal length	$l(\omega_{n})=n(n-1)/2$ in $S_{n}$, 
which correspond to the greatest elements $E_{n}$ of the $\dcal_{n}$. 
 
We can now define the {\it Schubert polynomial} $X_{\pi}$ for every  
$\pi \in S_{n}$ by 
\begin{equation*} X_{\pi }:=\partial_{\pi^{-1} \omega _{n}} x^{E_{n}} \ 
.\end{equation*}  Some elementary properties of the Schubert polynomials are 
listed in Prop.3.1. The properties (M), (S) and (P) below 
together with (B) are proved in Section 5; all these proofs are new, 
some are shorter than the former ones, some give new insights. 
\begin{itemize} \item[{\bf (M)}]  $\pi $ {\it dominant} $:\gdw$ 
$L(\pi )$ weakly decreasing (= non-increasing)  
$\Rightarrow  X_{\pi }=x^{L(\pi)}$, i.e. $X_{\pi }$ is a monomial. (M 
for `monomial'.) 
\item[{\bf (S)}] $\pi $ {\it Grassmannian} $:\gdw \pi $  has a 
unique descent at place $j$, i.e. $\pi j>\pi (j+1)$, $\gdw \ L(\pi)^{+} :=  
$`$L(\pi)$ without end zeros' is weakly increasing (= non-decreasing)  
and has exactly $j$ components; then $X_{\pi }$ 
equals the Schur polynomial $\{\lambda \}^{j}$ in the variables  
$x_{1},\dots,x_{j}$ with $\lambda$ given by $L(\pi )$ without end zeros 
and read backwards. (S for `Schur'.) 
\item[{\bf (P)}] Every $X_{\pi}$ is a polynomial with non-negative  
integer coefficients. (P for `positive'.) 
\end{itemize} 
\vspace{20pt}

\section{Permutations and Lehmer codes} 
 
For $n\in\N$, $\pi\in S_{n}$ we define:  
$I_{n}:=\{ (i,j)\in \{1,\dots,n\}^{2} | i<j \}$,  
the {\it set of inversions} of $\pi $:  
$I(\pi ):=\{ (i,j)\in \{1,\dots,n\}^{2} | i<j, \pi i > \pi j \}$, 
the involution $\iota $ on $\LL_{n}$ by $l_{k}\mapsto k-l_{k}$ 
and the involution $\omega _{n}$ on $\{1,\dots,n\}$ by $k \mapsto 
n+1-k$. The latter induces involutions on $S_{n}$ by  
right multiplication $\pi \mapsto \pi \omega _{n}$ (involution of 
places), by left multiplication $\pi \mapsto \omega _{n}\pi $  
(involution of letters) and on $I_{n}$ by $(i,j) \mapsto \omega 
_{n}^{(2)} (i,j):=(\omega _{n}j, \omega _{n}i)$. We collect some 
basic facts in  \\
\begin{Lem} With the notations above and $\pi $ written as the list 
$\pi 1\dots \pi n$ one has: \begin{itemize}
\item[a)] $\pi \omega _{n}=( \pi $ read backwards $)$;
\item[b)] $|L(\pi )| = \sharp I(\pi ) \equiv l(\pi) $\ ;
\item[c)] $I(\omega _{n}) = I_{n}$, $|L(\omega _{n})| = n(n-1)/2$\ ; 
\item[d)] $I(\omega _{n}\pi ) = I_{n}\setminus I(\pi )$,  
   $I(\pi  \omega _{n}) = \omega _{n}^{(2)} I(\omega _{n}\pi )$\ ;
\item[e)] $|L(\omega _{n}\pi )| = n(n-1)/2 -|L(\pi )|= |L(\pi\omega _{n} )|$\ ;
\item[f)] $L(\omega _{n} \pi ) = \iota L(\pi )$\ ;
\item[g)] $|L(\pi )| = |L(\pi^{-1} )|$\ ;
\item[h)] $l(\pi \pi')\leq l(\pi )+l(\pi')$, equality holds iff $\pi\pi'$ is 
reduced;
\item[i)] let $k\in \N$ and $\pi$ sufficiently high embedded, if necessary; 
then \\ \hspace{40pt} $l(\pi \sigma _{k})=\left\{ \begin{array}{cl}  
l(\pi) +1 & \text{, if $\pi k < \pi (k+1)$} \\ 
l(\pi) -1 & \text{, if $\pi k > \pi (k+1)$}  
\end{array} \right.$. \end{itemize}
\end{Lem}
\begin{proof} a) trivial;
  
b) $|L(\pi )| = \sum_{i=1}^{n} l_{n-i}(\pi ) 
= \sum_{i=1}^{n} \sharp\{ j | i<j, \pi i > \pi j \}  
= \sharp (\bigcup_{i=1}^{n} \{ (i,j) | i<j, \pi i > \pi j \}) 
= \sharp \{ (i,j) | i<j, \pi i > \pi j \} = \sharp I(\pi )$\ ; 
 
c) from the definition;  

d) $I(\omega _{n}\pi ) =  
\{ (i,j) | i<j, \omega _{n}\pi i > \omega _{n}\pi j \} = 
\{ (i,j) | i<j, \pi i < \pi j \} = I_{n}\setminus I(\pi )$,  
   $ \omega _{n}^{(2)}(I_{n}\setminus I(\pi )) = 
\{ (\omega _{n} j, \omega _{n} i) | i<j, \pi i < \pi j \} = 
\{ (i,j) | \omega_{n}j< \omega_{n}i, \pi\omega_{n} j< \pi\omega_{n}i \} = 
\{ (i,j) | i<j, \pi\omega_{n} j< \pi\omega_{n}i \} = 
 I(\pi  \omega _{n})$\ ;
 
e) from d);

f) from the proof of b) one sees  
$l_{n-k}(\pi ) = \sharp \{ (i,j)\in I(\pi ) \mid i=k \}$, hence  
$l_{n-k}(\omega _{n}\pi ) =  
\sharp \{ (i,j)\in I(\omega_{n})\setminus I(\pi) | i=k \} =  
k-l_{n-k}(\pi)$\ ;

g) let $\pi = \sigma _{i_{1}}\dots\sigma _{i_{l(\pi)}}$, then  
$\pi^{-1} =  
\sigma _{i_{l(\pi)}}^{-1} \dots \sigma_{i_{1}}^{-1}$ and  
$l(\pi ) \geq l(\pi ^{-1})$; now interchange the role of $\pi $ and $\pi 
^{-1}$\ ;

h) immediate from using reduced words for $\pi $ and $\pi'$;

i) immediate from b) and the definition of Lehmer codes. 
\end{proof} 
 
\begin{Def} Let $k\in \N$ and $\pi \in S_{\infty}$, i.e. 
there exists an $n\in \N$, such that $\pi n \neq n$ and  
$\pi= \pi 1 \dots \pi n\ n+1\ n+2\ \dots$ .  
Then for every $m\in \N$ we define the sets:

$J_{m}^{<k} (\pi):=\{\ j \mid 1\leq j <k,\pi j < \pi k, 
\sharp \{ \nu | j< \nu < k,\pi j <\pi\nu <\pi k \}=m-1 \}$
 
$J_{m}^{>k} (\pi):=\{\ j \mid k<j,\pi k < \pi j, 
\sharp \{ \nu | k< \nu < j,\pi k <\pi\nu <\pi j \}=m-1 \} $\\ 
and similarly for $m\in -\N$ : 
 
$J_{m}^{<k} (\pi):=\{\ j \mid 1\leq j <k,\pi j > \pi k, 
\sharp \{ \nu | j< \nu < k,\pi j >\pi\nu >\pi k \}=|m|-1 \}$
 
$J_{m}^{>k} (\pi):=\{\ j \mid k<j,\pi k > \pi j, 
\sharp \{ \nu | k< \nu < j,\pi k >\pi\nu >\pi j \}=|m|-1 \}$. \\ 
 Set $J_{m}^{k}(\pi):= J_{m}^{<k}(\pi) \cup J_{m}^{>k}(\pi)$ for 
$m\in \Z\setminus \{ 0 \}$. Moreover for $m\in \N$ we define 
 
$J_{m}(\pi):=\{\ (i,j) \mid i<j,\pi i<\pi j, 
\sharp \{ \nu | i< \nu < j,\pi i <\pi\nu <\pi j \}=m-1 \}$ \\
and similarly for $m\in -\N$ :

$J_{m}(\pi):=\{\ (i,j) \mid i<j,\pi i>\pi j, 
\sharp \{ \nu | i< \nu < j,\pi i >\pi\nu >\pi j \}=|m|-1 \}$. 
\end{Def}
 
Note that it is especially easy to determine the above sets for 
$m=1$, e.g. for $\pi= 4 1 3 2 7 6 9 5 8$ one has $J_{1}^{< 6}=\{ 4,3,1 \}$, 
$J_{1}^{> 6}=\{ 7,9 \}$, and $J_{1}=\{ (1,5), (1,6), (1,8), (2,3), 
(2,4),\linebreak (3,5), (3,6), (3,8), (4,5), (4,6), (4,8), (5,7),  
(5,9), (6,7), (6,9), (8,9) \}$. Note further that for all  
$k$, $\pi$ and $m\in \N$ \ \ $J_{m}^{>k}(\pi)$ is never empty. 
 
\begin{Prop} Using the notations of Definition 2.2 one has: 
\\ $j\in J_{m}^{k}(\pi) \gdw l(\pi\circ (j,k))=l(\pi) \pm (2 m+1) $ \  and   
$(i,j) \in J_{m}(\pi) \gdw l(\pi\circ (i,j))=l(\pi) \pm (2 m +1)$, where 
one uses the $+$ sign, if $m> 0$, and the $-$ sign, if $m< 0$.
\end{Prop} 
\begin{proof} Let $r<\nu< s$ and assume that $\pi r < \pi s$, then
$(r,s)=\sigma_{s-1}\circ\dots\circ \sigma_{r}\circ\dots\circ\sigma_{s-1}$ 
implies that in order to get $\pi\circ (r,s)$ one has first to 
commute $\pi s$ to place r and than $\pi r$ (on place r+1) to place s.
If $\pi \nu > \pi s$ or $\pi \nu < \pi r$, then by Lemma 2.1 i) it 
contributes the length $1+(-1)=0$, but if $\pi r< \pi \nu < \pi s$ it 
contributes the length $1+1=2$. The cases $\pi r < \pi s $ and $m<0$ are 
similar and the second assertion follows from 
$J_{m}(\pi)=\bigcup_{k} J_{m}^{k}(\pi)$. \end{proof}
 
The Lehmer code $L(\pi )$ of a permutation $\pi\in S_{n}$ has a close 
relationship to the inversions of $\pi $ as Lemma 2.1 and 
the definition $l_{n-i}=\sharp \{ $ all letters to the right of 
place $i$ less than $\pi i \}$ shows. There are alternative codes  
$Y(\pi)\equiv \ooo{y_{n-1} \dots y_{0}}$, where $(Y,y)\in\{ (G,g), 
(H,h), (K,k) \}$; they are defined as follows (we list L again for ease of 
comparison) : \begin{align*} 
L(\pi) :\ & l_{n-i} := \sharp\{\ j \mid j > i,\ \pi j < \pi i\ \} \\ 
H(\pi) :\ & h_{n-i} := \sharp\{\ j \mid j< \pi^{-1} i,\ \pi j > i\ \} \\ 
K(\pi) :\ & k_{i-1} := \sharp\{\ j \mid j < i,\ \pi j > \pi i\ \} \\ 
G(\pi) :\ & g_{i-1} := \sharp\{\ j \mid j > \pi^{-1} i,\ \pi j < i\ \} 
\end{align*}  
 
\begin{Prop}  For $\pi\in S_{n}$ and $L,H,K,G$ as above 
one has: $|L(\pi)|=|H(\pi)|=|K(\pi)|=|G(\pi)|=\sharp I(\pi)$ and  
 $H(\pi)=L(\pi^{-1})$, $K(\pi)=L(\omega_{n} \pi \omega_{n})$, 
$G(\pi) = L(\omega_{n} \pi^{-1} \omega_{n})$.\end{Prop} 
\begin{proof} $ l_{n-i}(\pi^{-1}) =  
\sharp \{ j \mid i<j,\ \pi^{-1} i > \pi^{-1} j \} = 
\sharp \{ \pi k \mid i<\pi k,\ \pi^{-1} i > k \} = 
\sharp \{ k \mid k < \pi^{-1} i,\ \pi k > i \} = h_{n-i}$; then 
$|L(\pi)| = |H(\pi)|$ follows from Lemma 2.1 b,g). The	proofs 
for	$K$ and $G$ are similar; two applications of Lemma 2.1 e) give 
$\sharp I(\omega_{n} \pi \omega_{n}) = \sharp I(\pi)$. \end{proof} 
 
\begin{Ex}  Let $\pi=3417625\in S_{7}$; then $L(\pi)=\ooo{2203200}$, 
$\pi^{-1}=3612754 \approx \ooo{2400210}=H(\pi)$, 
$\omega_{7} \pi \omega_{7}= 3621745 \approx \ooo{2410200}=K(\pi)$, and 
$\omega_{7} \pi^{-1} \omega_{7}= 4316725 \approx \ooo{3202200}=G(\pi)$. 
\end{Ex} 
 
The Lehmer code has several aspects: it is a description of a 
permutation with emphasis on inversions/transpositions/reduced word  
representations; it also furnishes a graded bijection 
between the set of all finite permutations $S_{\infty }$ and arbitrary 
finite sequences of nonnegative numbers $\dcal_{\infty }$ modulo embedding as 
discussed in Section 1. But most important for this paper:  
 
{\em The set of all Lehmer codes $\LL_{\infty }$ has a natural recursive 
structure, which translates into recursions for permutations and 
Schubert polynomials.} 
 
For a permutation $\pi \in S_{n}$ one computes its Lehmer code by the 
definition $l_{n-i}(\pi )=\sharp\{ j | j>i,\ \pi j<\pi i\}$. 
Clearly the procedure can be reversed: $\pi 1$ is the $(l_{n-1}+1)$-th 
element of $\{1,\dots,n\}$ in the natural order, $\pi 2$ is the  
$(l_{n-2}+1)$-th element of $\{1,\dots,n\}\setminus \{\pi 1\}$ etc. . 
Notice that necessarily $\pi $ is build up from left to right. 
 
Now the recursive structure on $\LL_{\infty }$ is given by extension to the 
left or more exactly: for $n\in\N_{0}$ and $0\leq k \leq n$ the mapping  
$\varepsilon_{n k}:\LL_{n}\lra \LL_{n+1}$ 
defined by $l\mapsto \ooo{k}l$ is an embedding and the set of images 
$\{ \varepsilon _{n 0} \LL_{n},\dots, \varepsilon _{n n} \LL_{n} \}$ 
is a partition of $\LL_{n+1}$ into parts of equal cardinality. 
(For $n=0$ set $\LL_{0}:=\emptyset$ and 
$\varepsilon _{0 0}(\emptyset )=\{ \ooo{0} \}$.) According to the 
recursive structure it is natural to view Lehmer codes as being build up 
from right to left, which explains our choice for the indices. 
 
The recursive structure for Lehmer codes extends naturally to permutations: 
for $n\in\N_{0}$ and $0\leq k \leq n$ the mapping  
$\varepsilon_{n k}': S_{n}\lra S_{n+1}$	defined by  
$\varepsilon_{n k}'= L^{-1}\circ \varepsilon_{n k}\circ L$ or 
$\pi \mapsto \pi_{k}$ with \begin{equation*} \pi_{k}:=L^{-1}(\ooo{k}L(\pi)) 
\end{equation*}
is an embedding and the set of images 
$\{ \varepsilon _{n 0}' S_{n},\dots, \varepsilon _{n n}' S_{n} \}$ 
is a partition of $S_{n+1}$ in parts of equal cardinality. ( For $n=0$  
set $S_{0}:=\emptyset$ and $\varepsilon_{0 0}'(\emptyset )=\{ id\}=S_{1}$. ) 
 
In the rest of this section we examine the relationship between these 
two structures more closely and in the next section we investigate 
its meaning for Schubert polynomials. \\ 
 
{\bf Notation}: Subsequently we often view permutations and also 
Lehmer codes as words in the alphabet $\N_{0}$, so that it makes sense 
to append `letters' to the left or right and also to apply operators 
such as $\sigma _{i}$ or the $m_{+}$ discussed in Section 1 to these `words'. 
As an example consider $(1_{+}\circ (3,1,2)\circ (1\ 2\ 2_{+} (\pi\ \sigma 
_{1})) \circ \sigma _{2}) \ 1$, which means: take the word $\pi$ 
with the letters on places 1 and 2 interchanged, add 2 to all 
numbers, put the word `1 2' in front, interchange the numbers 1, 2, 3 
cyclically according to the cycle $(3,1,2)$ and the numbers on places 
2 and 3, add 1 to all numbers and finally a letter 1 on the right 
side; the reader may convince himself that the result for $\pi=312 
\in S_{3}$ is $324651\in S_{6}$. \\ \\ 
 
The next proposition indicates how to build up permutations according to  
the recursive structure on Lehmer codes. 
 
\begin{Prop} $\pi _{n}=(n+1)\pi$, $\pi _{0}= 1 \ 1_{+}(\pi)$ and 
$\pi_{k} = \sigma_{k} \pi_{k-1}$ for $0<k\leq n$ using the above notations.
\end{Prop} 
\begin{proof} Directly from the definitions one has $\pi _{k} 1 = k+1$ 
for all $k$ and \\ 
$L( (n+1)\ \pi) = \ooo{n}\ L(\pi )$, which implies the first assertion.  
The second follows from $L(1\ 1_{+}(\pi)) = \ooo{0}\ L(\pi )$,  
because the Lehmer code is invariant under the `translations'  
$m_{+}:\Z \lra \Z$ for all $m\in\Z$, i.e. for fixed  
$\pi \in S_{n}$ and $m_{+}\pi \in S_{m_{+}( \{1,\dots,n\} )}$ one has 
$L(\pi )= L( m_{+}\pi )$ for all $m\in\Z$. 
 
Now $\pi _{k-1}= k\dots (k+1) \dots$ with $k+1$ standing at some place $\nu $ 
between $2$ and $n+1$. Therefore $\sigma _{k}\pi _{k-1}=(k+1) \dots k \dots$  
with $k$ at place $\nu $ and $L(\sigma _{k} \pi _{k-1})$ is the same 
as $L(\pi _{k-1})$ except for $k$ instead of $k-1$ at the first place. 
Hence $L(\pi _{k-1}) = \ooo{k-1}\ L(\pi ) \Rightarrow  
L(\sigma _{k}\pi _{k-1}) = \ooo{k}\ L(\pi ) \Rightarrow  
\sigma _{k}\pi _{k-1} = L^{-1}(\ooo{k}\ L(\pi ) ) = \pi _{k}$. \end{proof}  
 
\begin{Cor} $\pi _{k}= \varepsilon _{n k}'(\pi ) =  \sigma_{k}\dots  
\sigma _{1} (1\ 1_{+}(\pi) ) = 1_{+} \circ (k,\dots,0) \circ (0\ \pi)$\ .
\end{Cor} 
\begin{proof} Only the last equality needs an explanation: $\sigma  
_{k}\dots \sigma _{1} (1\ 1_{+} (\pi))= (k+1,\dots,1) \circ\ 1_{+}(0\ \pi ) 
= 1_{+} \circ (k,\dots,0)\circ (0\ \pi)$\ . \end{proof} 
 
The corollary describes an algorithm, which computes a permutation 
$\pi $ from $L(\pi )$ in such a way, that for each right part of $L(\pi )$ 
we get the corresponding permutation.\\ 
\begin{Ex} Recursive computation of $L^{-1} (\ooo{23010}) = 35142$\ . 
\\ $\begin{array}{rl} 
\ooo{0}: &  1 = L^{-1} (\ooo{0}) \\ 
\ooo{10}: &  01 \stackrel{(1,0)}{\lra} 10  
                \stackrel{1_{+}}{\lra} 21 = L^{-1} (\ooo{10}) \\ 
\ooo{010}: &  021 \stackrel{(0)}{\lra} 021  
                \stackrel{1_{+}}{\lra} 132 = L^{-1} (\ooo{010}) \\ 
\ooo{3010}: &  0132 \stackrel{(3,2,1,0)}{\lra} 3021 
                \stackrel{1_{+}}{\lra} 4132 = L^{-1} (\ooo{3010}) \\ 
\ooo{23010}: &  04132 \stackrel{(2,1,0)}{\lra} 24031 
                \stackrel{1_{+}}{\lra} 35142 = L^{-1} (\ooo{23010})  
\end{array}$ \end{Ex}
 
The preceding example computes $\pi\in S_{n} $ from $L(\pi )$ by starting 
from $id_{1}\equiv 1 \in S_{1}$; the next proposition shows, how one can  
do this computation starting from $id_{n} \equiv 1 \dots n \in S_{n}$. 
 
\begin{Prop} For $\pi \in S_{n}$ let $L(\pi ) \equiv 
\ooo{l_{n-1} \dots l_{0}}$\ , then $\pi = 1_{+}(l_{n-1},\dots,0) \circ  
2_{+}(l_{n-2},\dots,0) \circ \dots \circ n_{+}(l_{0}) \ (1 \dots n)$\ .
\end{Prop} 
\begin{proof} This is the first instance of what we called {\em long 
induction}, i.e. an induction over all permutations $\pi \in S_{\infty 
}$ : we establish the property in question for $S_{1}$ 
and then use the recursive structure on $\LL_{\infty }$ or 
$S_{\infty }$, i.e we investigate two types of induction steps: first 
from $\pi \in S_{n}$ to $\pi _{0}\in S_{n+1}$ [or $\pi _{n}\in S_{n+1}$]  
and second from $\pi _{k-1}$ to $\pi _{k}$ [or $\pi _{k}$ to $\pi_{k-1}$] 
in $S_{n+1}$. 
 
For $\pi =1 \in S_{1}$ the assertion is trivial. Step $\pi $ to $\pi 
_{0}$: $L(\pi _{0}) = \ooo{0}\ L(\pi )$ implies $l_{\nu } \equiv  
l_{\nu } (\pi ) = l_{\nu }(\pi _{0})$ for $\nu =0,\dots,n-1$ and $l_{n}(\pi 
_{0}) = 0$, hence $\pi _{0} = 1\ 1_{+}(\pi) = 
1\ [ 2_{+}(l_{n-1},\dots,0) \circ \dots \circ (n+1)_{+}(l_{0})  
(2 \dots (n+1) ) ]$ which equals 
$1_{+}(0)\circ 2_{+}(l_{n-1},\dots,0) \circ \dots \circ (n+1)_{+}(l_{0})  
(1 \dots	(n+1) )$, because the cycles do not act upon the letter $1$ 
and $1_{+}(0)=id$. 
 
Step $\pi _{k-1}$ to $\pi _{k}$: $\pi _{k}= \sigma _{k} \pi_{k-1} = 
\sigma_{k} \circ 1_{+}(k-1,\dots,0) \circ\dots\circ (n+1)_{+}(l_{0})\  
 ( 1\dots (n+1) ) = 
1_{+}(k,\dots,0) \circ \dots \circ (n+1)_{+}(l_{0})\ ( 1\dots (n+1) )$\ .
\end{proof}  
 
\begin{Ex} $L^{-1} (\ooo{23010})= 1_{+}(2,1,0) \circ 
2_{+}(3,2,1,0) \circ 3_{+}(0) \circ 4_{+}(1,0) \circ 5_{+}(0) \ ( 1\dots n )  
= (3,2,1) \circ (5,4,3,2) \circ id \circ (5,4) \circ id \ (12345)   
= (3,2,1) \circ (5,4,3,2) \   (12354)  
= (3,2,1) \ (15243) = 35142 $\ .\end{Ex}
 
\begin{Cor} For $\pi \in S_{n}$ and $L(\pi ) \equiv \  
\ooo{l_{n-1} \dots l_{0}}$\ is  \begin{equation*} \Phi (L(\pi)) :=  
0_{+}(l_{n-1}\dots 1)\  1_{+}(l_{n-2}\dots 1)\ \dots (n-2)_{+}(l_{1}\dots 1) 
\in R(\pi )\end{equation*} a reduced sequence, where for  
$k\leq 0$ we define $m_{+}(k \dots 1)$ to be the empty sequence\ .\end{Cor} 
\begin{proof} Clearly  
$0_{+}(l_{n-1}\dots 1) 1_{+}(l_{n-2}\dots 1) \dots (n-2)_{+}(l_{1}\dots 1)$ 
contains $l(\pi )$ components, hence \linebreak $k_{+}\ (l_{n-k},\dots,0) = 
(k-1)_{+}\ (l_{n-k}+1,\dots,1) =  
(k-1)_{+}\ ( (l_{n-k},l_{n-k}+1)\circ\dots\circ (1,2) )$ gives the 
result. \end{proof} 
 
\begin{Ex} By Cor.2.11 a reduced sequence for 
$\pi=35142 \approx \ooo{23010}$ is 
given by $0_{+}( 21 )\ 1_{+}( 321 )\ 3_{+}( 1 ) = 214324$  and indeed 
$\pi = \sigma_{2}\sigma_{1}\sigma_{4}\sigma_{3}\sigma_{2}\sigma_{4}$\ .
\end{Ex}
\vspace{20pt}

\section{Recursive structure of Schubert polynomials} 
 
We first collect some elementary properties of Schubert polynomials 
and the operators $\partial_{\pi}$ in:
 
\begin{Prop}  \begin{itemize} 
\item[a)] $X_{id}=1$ and $X_{\omega_{n}}=x^{E_{n}}$; 
\item[b)] $X_{\pi}$ is a homogeneous polynomial of degree $l(\pi)$;
\item[c)] for all $\pi,\rho\in S_{\infty}$:  
$\partial_{\pi} \partial_{\rho}=\partial_{\pi\rho}$, if 
$l(\pi\rho)=l(\pi)+l(\rho)$, and $=0$ otherwise;
\item[d)] for all $\pi,\rho\in S_{\infty}$:  
$\partial_{\pi} X_{\rho}=X_{\rho \pi^{-1}}$, if 
$l(\rho \pi^{-1})=l(\rho)-l(\pi)$, and $=0$ otherwise;
\item[e)] for $\pi \in S_{n},\ 1\leq k<n$\ : 
$ \partial_{k} X_{\pi }= X_{\pi \sigma _{k}}$, if $\pi k>\pi  (k+1)$, and  
$ \partial_{k} X_{\pi }= 0$, if $\pi k <  \pi  (k+1)$; 
\item[f)] $X_{\pi}$ is symmetric in $x_{k}$ and $x_{k+1}$ iff 
$\pi k<\pi (k+1)$; 
let $j$ be the first descent in $\pi$, then \linebreak $X_{\pi}(x_{1},\dots, 
x_{j}, 0,\dots)$ is symmetric and called the {\em symmetric part of 
$X_{\pi}$};
\item[g)] $X_{\pi}$ is symmetric iff $\pi$ is Grassmannian;
\item[h)] $X_{\sigma _{i}}= x_{1}+\dots +x_{i}$ for all $i\in \N$;
\item[i)] $X_{\pi}$ is invariant under embedding of $\pi$, i.e. 
$X_{\pi'}=X_{\pi}$ for $n<m$, $\pi \in S_{n}$ and 
$\pi'=\pi 1 \dots \pi n \ (n+1) \dots m \in S_{m}$.
 \end{itemize} \end{Prop} 
\begin{proof} a), b) and c) are immediate from the definition  
$X_{\pi }:=\partial_{\pi^{-1} \omega _{n}} x^{E_{n}}$ of Schubert 
polynomials, the elementary properties of the divided differences 
listed in Section 1 and Lemma 2.1 h); \\ 
d): from part c) follows $\partial_{\pi} X_{\rho}= 
\partial_{\pi} \partial_{\rho^{-1} \omega _{n}} x^{E_{n}} \stackrel{!}{=} 
\partial_{\pi \rho^{-1} \omega _{n}} x^{E_{n}} = X_{\rho \pi^{-1}}$, if 
$l(\pi)=l(\rho^{-1} \omega _{n})+l(\pi \rho^{-1} \omega _{n})$, which 
is by Lemma 2.1 e,g) equivalent to $l(\rho \pi^{-1})=l(\rho)-l(\pi)$;\\ 
e): by part c) $X_{\pi\sigma_{k} }= 
\partial_{(\pi\sigma_{k})^{-1} \omega_{n}}x^{E_{n}}  
= \partial_{\sigma _{k}\pi^{-1} \omega _{n}}x^{E_{n}} \stackrel{!}{=} 
 \partial_{k} \partial_{\pi^{-1} \omega _{n}}x^{E_{n}} =  
 \partial_{k} X_{\pi }$, if \\ $|L(\sigma _{k}\pi ^{-1}\omega _{n})| = 
|L(\pi ^{-1}\omega _{n})|+1 \gdw |L(\pi \sigma _{k})|= |L(\pi )|-1 
\gdw \pi k>\pi (k+1)$;\\ 
e) $\Lra$ f) $\Lra$ g) ;\\ 
h) $X_{\sigma _{i}}$ is homogeneous of degree 1 by b), symmetric in 
$x_{1},\dots ,x_{i}$ by f) and $\partial_{i} X_{\sigma _{i}}=1$ by e,a);\\ 
i): [the ``proof" in [K] is misleading] it is enough to show the assertion 
for $m=n+1$: by Lemma 2.1 b,e) one has $l(\pi')=l(\pi)$ and 
$l(\omega_{n+1} \pi')= l(\omega _{n} \pi)+n$; let $\rho=(n+1,n,\dots,1)= 
\sigma _{n}\circ\dots\circ\sigma _{1}$, then $\rho^{-1}=(1,2,\dots,n+1)$ and 
$\rho^{-1} \omega_{n} \pi= \omega_{n+1} \pi'$; moreover 
$a_{1} \dots a_{p}\in R(\pi^{-1}\omega _{n}) \Lra  
a_{1} \dots a_{p}\ n \dots 1 \in R(\pi^{-1}\omega _{n}\rho)= 
R( (\rho^{-1}\omega _{n}\pi)^{-1} )=R((\pi')^{-1}\omega _{n+1})$; 
finally $X_{\pi'}= \partial_{(\pi')^{-1}\omega _{n+1}} x^{E_{n+1}} 
=\partial_{\pi^{-1}\omega _{n}} \partial_{n}\dots \partial_{1} x^{E_{n+1}} 
=\partial_{\pi^{-1}\omega _{n}} x^{E_{n}}=X_{\pi}$. \end{proof} 
 
Obviously the recursive structures for permutations (cf. Section 2) given by 
$\pi \rightarrow \pi _{0} \rightarrow \dots \rightarrow \pi _{n}$ resp.  
$\pi \rightarrow \pi _{n} \rightarrow \dots \rightarrow \pi _{0}$ can 
not be applied directly, but Prop.3.1 e) suggests an idea how to proceed. 
 
We define for $n\in \N, 1\leq k\leq n$ the following subsets of $S_{n}$: 
\begin{equation*} S_{n}(k):=\{ \pi \in S_{n} \mid \pi k = 1 \}\ ,\  
S_{n}'(k):=\{ \pi \in S_{n} \mid \pi k = n \}\  ;\end{equation*} 
Clearly the sets $\{ S_{n}(1),\dots, S_{n}(n) \}$ and 
$\{ S_{n}'(1),\dots, S_{n}'(n) \}$ are 
partitions of $S_{n}$ into parts of equal cardinality $(n-1)!$ . 
Moreover with $\sigma _{k}^{*}\pi :=\pi \circ\sigma _{k}$ one has  
$S_{n}(n) \stackrel{\sigma _{n-1}^{*}}{\lra} 
\dots \stackrel{\sigma _{1}^{*}}{\lra} S_{n}(1)$ , 
i.e. the letter $1$	is moved by transpositions from the $n^{th}$ 
place to the $1^{st}$ ,  and 
$S_{n}'(1) \stackrel{\sigma_{1}^{*}}{\lra}\dots 
\stackrel{\sigma _{n-1}^{*}}{\lra} S_{n}'(n)$\ , 
i.e. the letter $n$	is moved by transpositions from the $1^{st}$ 
place to the $n^{th}$ . For the subsets \begin{equation*} 
\scal_{n}(k):=\{ X_{\pi} \mid \pi \in S_{n}(k)\}\ ,\  
\scal_{n}'(k):=\{ X_{\pi} \mid \pi \in S_{n}'(k)\} 
\end{equation*}  of $\scal_{n}$ the preceding proposition yields: 
$\scal_{n}(n) \stackrel{\partial_{n-1}}{\lra} 
\dots \stackrel{\partial_{1} }{\lra} \scal_{n}(1)$ and 
$\scal_{n}'(1) \stackrel{\partial_{1}}{\lra} 
\dots\stackrel{\partial_{n-1}}{\lra}\scal_{n}'(n-1)$. 
 
We now investigate the meaning of the bijective sequences 
$S_{n}(n) \stackrel{\sigma _{n-1}^{*}}{\lra} 
\dots \stackrel{\sigma _{1}^{*}}{\lra} S_{n}(1)$ and 
$S_{n}'(1) \stackrel{\sigma_{1}^{*}}{\lra}\dots 
\stackrel{\sigma _{n-1}^{*}}{\lra} S_{n}'(1)$ 
in terms of Lehmer codes.  
For $n\in \N, 1\leq k\leq n$ we define the following subsets of $\LL_{n}$:  
\begin{equation*} \LL_{n}(n-k):=L(S_{n}(k))\ ,\  
\LL_{n}'(n-k):=L(S_{n}'(k))\  .\end{equation*}   Then 
$\LL_{n}(k)=\{ l \in \LL_{n} \mid l_{k}=0\ {\rm and\ for }\ 
k'>k : l_{k'} > 0 \}$ , because the place of $1$ in $\pi $ is 
the place of the first $\ooo{0}$ in $L(\pi )$ ; similarly 
$\LL_{n}'(k):=\{ l \in \LL_{n} \mid l_{k}=k\ {\rm and\ for}\ 
k'>k : l_{k'}<k \}$ , because the place of $n$	in $\pi $ is the 
place of the first $l_{k}$ taking its maximum possible value. 
With this notations one gets the bijective sequences 
$\LL_{n}(0)\stackrel{\tau_{1}}{\lra} 
\dots\stackrel{\tau_{n-1}}{\lra}\LL_{n}(n-1)$ and 
$\LL_{n}'(n-1)\stackrel{\tau_{n-1}'}{\lra}\dots 
\stackrel{\tau_{1}'}{\lra}\LL_{n}'(0)$ 
, where for $1\leq k<n$\ : \begin{align*}  
\tau_{k} :\ & \LL_{n}(k-1) \lra  
\LL_{n}(k)\ ,\ \ooo{\dots l_{k}\  0 \dots}\mapsto 
\ooo{\dots 0\  (l_{k}-1) \dots} \\
\tau_{k}' :\ & \LL_{n}'(k) \lra  
\LL_{n}'(k-1)\ ,\  \ooo{\dots k\ l_{k-1} \dots} 
\mapsto \ooo{\dots l_{k-1}\ (k-1) \dots} \end{align*} 
 
The next result recasts the preceding facts in terms of the  
$\pi_{k}:=L^{-1}(\ooo{k}\ L(\pi))$. 
 
\begin{Prop} Let $\pi \in S_{n-1}$. Then  
$\pi _{0}^{-1}\omega _{n}\mapsto\dots\mapsto \pi _{n-1}^{-1}\omega _{n}$ 
and \linebreak  
$\omega_{n}\pi _{0}^{-1}\mapsto\dots\mapsto \omega _{n}\pi_{n-1}^{-1}$ 
are sequences of elements subordinate to the sequences \linebreak 
$S_{n}(n) \stackrel{\sigma _{n-1}^{*}}{\lra} 
\dots \stackrel{\sigma _{1}^{*}}{\lra} S_{n}(1)$ and 
$S_{n}'(1) \stackrel{\sigma_{1}^{*}}{\lra}\dots 
\stackrel{\sigma _{n-1}^{*}}{\lra} S_{n}'(n)$ .\end{Prop} 
\begin{proof} $\pi _{0}=1\ 1_{+}(\pi ) \Rightarrow \pi _{0}^{-1}(1)=1$ 
implies $\pi _{0}^{-1}\omega _{n}(n)=1$ and $\omega _{n}\pi _{0}^{-1}(1)=n$ . 
Hence $\pi _{0}^{-1}\omega _{n}\in S_{n}(n)$ and 
$\omega _{n}\pi _{0}^{-1} \in S_{n}'(1)$. Using $\pi 
_{k}= \sigma _{k}\pi _{k-1}$ it is not hard to see that 
$\pi _{k}^{-1}\omega _{n}=\pi _{k-1}^{-1}\sigma _{k}\omega _{n}= 
( \pi _{k-1}^{-1}\omega _{n} ) \sigma _{n-k}$ and 
$\omega _{n}\pi _{k}^{-1} = \omega _{n} ( \sigma _{k}\pi _{k-1} )^{-1} 
= ( \omega _{n}\pi _{k-1}^{-1} ) \sigma _{k}$ . \end{proof}   
Clearly the following mappings are bijections:
\begin{equation*} \sigma^{(n)} _{+}: S_{n-1} \lra  
S_{n}(n)\ , \pi \mapsto 1_{+}(\pi )\ 1\ ,\  
(\sigma')^{(n)} _{+}: S_{n-1} \lra  
S_{n}'(1)\ , \pi \mapsto n\ \pi\ ; \end{equation*}   
in terms of Lehmer codes they read \begin{align*} 
\tau^{(n)} _{+}:\  & \LL_{n-1} \lra  
\LL_{n}(0)\ , L(\pi )\mapsto 1_{+}(L(\pi ))\ \ooo{0}\\
(\tau')^{(n)}_{+}:\  & \LL_{n-1} \lra  
\LL_{n}'(n-1)\ , L(\pi )\mapsto \ooo{n-1}\ L(\pi )\ .\end{align*} 
 
It remains to describe the corresponding mappings for the Schubert 
polynomials $\scal_{n-1}$. First we define the following  
$\Z$-linear mappings (recall $d_{n}=0$ for all $d\in\dcal_{n}$) :
\begin{equation*} 
(\epu)^{(n)}\equiv\partial^{(n)}_{+} \ , \epd\ , 
(\partial')^{(n)}_{+}:\ \Z_{E_{n-1}}[x] \lra \Z_{E_{n}}[x] \ ,\end{equation*} 
\begin{equation*} (\epu)^{(n)} \prod_{\nu=1}^{n-1} x_{\nu }^{d_{\nu }} :=  
\prod_{\nu=1}^{n-1} x_{\nu }^{d_{\nu }+1}\ ,\    
\epd \prod_{\nu=1}^{n-1} x_{\nu }^{d_{\nu }} 
:= \prod_{\nu=1}^{n} x_{\nu+1}^{d_{\nu} }\ ,\  
(\partial')^{(n)}_{+}:= x_{1}^{n-1}\ \epd \ .\end{equation*}  
It is not hard to compute that \begin{equation*} 
\partial_{i}\circ(\epu)^{(n)} = (\epu)^{(n)}\circ\partial_{i}\ , 
\ \partial_{i+1}\circ\epd = \epd\circ\partial_{i} \ \ \ {\rm and \ }  
(\epu)^{(n)} x^{E_{n-1}} = x^{E_{n}} = x_{1}^{n-1} \ \epd x^{E_{n-1}}\ .
\end{equation*}  
The next result now closes the remaining gap in our recursion: 
 
\begin{Prop} Let $\pi \in S_{n-1}$, then with the above 
notations $X_{\sigma _{+} \pi } =  
\partial^{(n)}_{+} X_{\pi } = x_{1} \dots x_{n-1} X_{\pi }$ and 
$X_{\sigma_{+}' \pi}=(\partial')^{(n)}_{+} X_{\pi } = 
x_{1}^{n-1}\ \epd \ X_{\pi }$.\end{Prop} 
\begin{proof} (We suppress the indices $^{(n)}$.) 
Recall the mapping $\Phi $ from Cor.2.8,  
which maps $L(\pi )$ to a reduced sequence $\in R(\pi )$.  
 
$\sigma _{+} \pi = 1_{+}(\pi )\ 1 \Rightarrow  
 \sigma _{+} \pi (n) = 1$ and for $k=1,\dots,n-1\ : 
\sigma _{+} \pi (k) = \pi (k) +1$. Hence  
$(\sigma _{+} \pi)^{-1} \omega _{n} (n) =  
 (\sigma _{+} \pi)^{-1} (1) = n$	and  
$(\sigma _{+} \pi)^{-1} \omega _{n} (k) =  
 (\sigma _{+} \pi)^{-1} (n+1-k) = \pi ^{-1}(n-k)	= 
 \pi ^{-1} \omega _{n-1} (k)$, i.e.  
$(\sigma_{+} \pi)^{-1} \omega_{n}=(\pi ^{-1} \omega_{n-1})\ n$. 
Therefore $\Phi L( (\sigma_{+} \pi)^{-1} \omega_{n} )= 
\Phi(\ L( \pi^{-1}\omega_{n-1})\ooo{0}\ ) = \Phi L( \pi ^{-1} \omega_{n-1} ) 
\Rightarrow \partial_{(\sigma_{+} \pi)^{-1} \omega_{n}}= 
\partial_{\pi ^{-1} \omega_{n-1}}$ and finally \\ 
$X_{\sigma _{+} \pi } =  
\partial_{ (\sigma_{+} \pi)^{-1} \omega_{n} } \ x^{E_{n}} 
=\partial_{ \pi ^{-1} \omega_{n-1} }\  \epu x^{E_{n-1}} =  
\epu \partial_{\Phi L( \pi ^{-1} \omega_{n-1} )} \ x^{E_{n-1}} 
=\epu X_{\pi } \equiv \partial_{+} X_{\pi }$ . 
 
Similarly $\sigma _{+}' \pi = n\ \pi \Rightarrow  
\sigma _{+}' \pi (1)= n$ and for $k=2,\dots,n:\  
\sigma _{+}' \pi (k) = \pi (k+1)$ . Hence  
$(\sigma _{+}' \pi)^{-1} \omega _{n} (1) =  
 (\sigma _{+}' \pi)^{-1} (n) = 1$	and  
$(\sigma _{+}' \pi)^{-1} \omega _{n} (k) =  
 \pi^{-1} (\ \omega _{n} (k)\ ) +1 = 1_{+}\pi^{-1} \omega _{n} (k)$, i.e. 
\linebreak $(\sigma_{+}' \pi)^{-1}\omega_{n}=1\ 1_{+}(\pi^{-1} \omega_{n})$. 
Therefore $\Phi L( (\sigma_{+}' \pi)^{-1} \omega_{n} )= 
\Phi( \ooo{0}\ L( \pi^{-1}\omega_{n-1})\ ) =\\  
1_{+} \Phi L( \pi ^{-1} \omega_{n-1} ) $, which implies 
$X_{\sigma _{+}' \pi } =  
\partial_{ (\sigma_{+}' \pi)^{-1} \omega_{n} } \ x^{E_{n}} = 
\partial_{\Phi L( (\sigma_{+}'\pi)^{-1} \omega_{n} )} \ x^{E_{n}} 
=\\ \partial_{1_{+} \Phi L( \pi ^{-1} \omega_{n-1} )} \  
                       x_{1}^{n-1} \epd x^{E_{n-1}} 
=x_{1}^{n-1}\ \epd (\partial_{\Phi L( \pi^{-1}  
                                         \omega_{n-1})}\ x^{E_{n-1}}) 
=x_{1}^{n-1}\ \epd X_{\pi } =\partial_{+}' X_{\pi }$ \ . 
\end{proof}  
The following commutative diagrams, in which all arrows are bijections,  
summarize our information about the recursive structures:\\ 
\begin{equation*}\begin{CD} 
\LL_{n-1} @>\tau^{(n)} _{+}>> \LL_{n}(0) 
@>\tau_{1}>> \dots  
@>\tau_{n-1}>> \LL_{n}(n-1) \\ 
@VL^{-1}VV @VL^{-1}VV && @VL^{-1}VV\\ 
S_{n-1} @>\sigma^{(n)} _{+}>> S_{n}(n) 
@>\sigma_{n-1}^{*}>> \dots  
@>\sigma_{1}^{*}>> S_{n}(1) \\ 
@VXVV @VXVV && @VXVV\\ 
\scal_{n-1} @>\partial^{(n)}_{+}>> \scal_{n}(n) 
@>\partial_{n-1}>> \dots  
@>\partial_{1}>> \scal_{n}(1)  
\end{CD}\end{equation*} \vspace{5pt} 
\begin{equation*}\begin{CD} 
\LL_{n-1} @>(\tau')^{(n)} _{+}>> \LL_{n}'(n-1) 
@>\tau_{n-1}'>> \dots  
@>\tau_{1}'>> \LL_{n}'(0) \\ 
@VL^{-1}VV @VL^{-1}VV && @VL^{-1}VV \\ 
S_{n-1} @>(\sigma')^{(n)}_{+}>> S_{n}'(1) 
@>\sigma_{1}^{*}>> \dots  
@>\sigma_{n-1}^{*}>> S_{n}'(n) \\ 
@VXVV @VXVV && @VXVV \\ 
\scal_{n-1} @>(\partial')^{(n)}_{+}>> \scal_{n}'(1) 
@>\partial_{1}>> \dots  
@>\partial_{n-1}>> \scal_{n}'(n)  
\end{CD}\end{equation*}  \ \\ 
We call the first diagram the {\it up case diagram}, because $(\epu)^{(n)}$ 
acts on the exponents, and the second the {\it down case diagram}, because  
$\epd $ acts on the subscripts. 
 
\begin{Ex} $\pi = 41253 \approx \ooo{30010}$ , $X_{\pi } = 
x_{1}^{3}x_{4}+x_{1}^{3}x_{3}+x_{1}^{3}x_{2}$ , which reads in 
$\Z\dcal_{\infty }$ : $30010 + 30100 + 31000$.  
 
First the {\it up case} (recall that for Lehmer codes the position  
of the first $\ooo{0}$ is crucial, and for permutations the  
position of the $1$ ) :\\ $ 
\ooo{0}\stackrel{\tau^{(2)}_{+}}{\lra} 
\ooo{10}\stackrel{\tau_{1}}{\lra} 
\ooo{00}\stackrel{\tau^{(3)}_{+}}{\lra} 
\ooo{110}\stackrel{\tau^{(4)}_{+}}{\lra} 
\ooo{2210}\stackrel{\tau_{1}}{\lra} 
\ooo{2200}\stackrel{\tau_{2}}{\lra} 
\ooo{2010}\stackrel{\tau^{(5)}_{+}}{\lra} 
\ooo{31210}\stackrel{\tau_{1}}{\lra} 
\ooo{31200}\stackrel{\tau_{2}}{\lra} 
\ooo{31010}\stackrel{\tau_{3}}{\lra}\ooo{30010}\\  
1 \stackrel{\sigma^{(2)}_{+}}{\lra} 
21 \stackrel{\sigma_{1}^{*}}{\lra} 
12 \stackrel{\sigma^{(3)}_{+}}{\lra} 
231 \stackrel{\sigma^{(4)}_{+}}{\lra} 
3421 \stackrel{\sigma_{3}^{*}}{\lra} 
3412 \stackrel{\sigma_{2}^{*}}{\lra} 
3142 \stackrel{\sigma^{(5)}_{+}}{\lra} 
42531 \stackrel{\sigma_{4}^{*}}{\lra} 
42513 \stackrel{\sigma_{3}^{*}}{\lra} 
42153 \stackrel{\sigma_{2}^{*}}{\lra} 41253 \\  
0 \stackrel{\partial^{(2)}_{+}}{\lra} 
10 \stackrel{\partial_{1}}{\lra} 
00 \stackrel{\partial^{(3)}_{+}}{\lra} 
110 \stackrel{\partial^{(4)}_{+}}{\lra} 
2210 \stackrel{\partial_{3}}{\lra} 
2200 \stackrel{\partial_{2}}{\lra} 
2100 + 2010 \stackrel{\partial^{(5)}_{+}}{\lra} 
32110 + 31210 \stackrel{\partial_{4}}{\lra} 
32100 + 31200 \stackrel{\partial_{3}}{\lra} 
32000 + 31100 + 31010 \stackrel{\partial_{2}}{\lra}  
31000 + 30100 + 30010 $. \\  
 
Second the {\it down case} (recall that for Lehmer codes the position  
of the first maximal $l_{k}$ is crucial, and for permutations the  
position of the maximal $\pi (k)$ ) :\\ $ 
\ooo{0}\stackrel{(\tau')^{(2)}_{+}}{\lra} 
\ooo{10}\stackrel{\tau_{1}'}{\lra} 
\ooo{00}\stackrel{(\tau')^{(3)}_{+}}{\lra} 
\ooo{200}\stackrel{\tau_{2}'}{\lra} 
\ooo{010}\stackrel{\tau_{1}'}{\lra} 
\ooo{000}\stackrel{(\tau')^{(4)}_{+}}{\lra} 
\ooo{3000}\stackrel{(\tau')^{(5)}_{+}}{\lra} 
\ooo{43000}\stackrel{\tau_{4}'}{\lra} 
\ooo{33000}\stackrel{\tau_{3}'}{\lra} 
\ooo{30200}\stackrel{\tau_{2}'}{\lra}\ooo{30010}\\  
1 \stackrel{(\sigma')^{(2)}_{+}}{\lra} 
21 \stackrel{\sigma_{1}^{*}}{\lra} 
12 \stackrel{(\sigma')^{(3)}_{+}}{\lra} 
312 \stackrel{\sigma_{1}^{*}}{\lra} 
132 \stackrel{\sigma_{2}^{*}}{\lra} 
123 \stackrel{(\sigma')^{(4)}_{+}}{\lra} 
4123 \stackrel{(\sigma')^{(5)}_{+}}{\lra} 
54123 \stackrel{\sigma_{1}^{*}}{\lra} 
45123 \stackrel{\sigma_{2}^{*}}{\lra} 
41523 \stackrel{\sigma_{3}^{*}}{\lra} 41253 \\  
0 \stackrel{(\partial')^{(2)}_{+}}{\lra} 
10 \stackrel{\partial_{1}}{\lra} 
00 \stackrel{(\partial')^{(3)}_{+}}{\lra} 
200 \stackrel{\partial_{1}}{\lra} 
100 + 010 \stackrel{\partial_{2}}{\lra} 
000 \stackrel{(\partial')^{(4)}_{+}}{\lra} 
3000 \stackrel{(\partial')^{(5)}_{+}}{\lra} 
43000 \stackrel{\partial_{1}}{\lra} 
33000 \stackrel{\partial_{2}}{\lra} 
32000 + 31100 + 30200 \stackrel{\partial_{3}}{\lra}  
31000 + 30100 + 30010 $.  
 
Note that the Lehmer codes occur as summands in the $\Z\dcal_{\infty }$ 
sequence by property (B). \end{Ex} 
 
The existence of the recursive structures makes possible {\em long 
induction} over all Lehmer codes, permutations or Schubert 
polynomials by using two different types of steps: first the 
(+)-{\em step} or {\em embedding step} from $(n-1)$ to $n$ and  
second the ($\tau $)-, ($\sigma$)- or ($\partial$)-step on a certain 
`$n$-level'; because all kinds of steps are bijections, we can call the 
appropriate connection of all diagrams of the above type 
suggestively the {\em long bijective stair} on which the the long 
induction is carried out. We have chosen the name `long bijective 
stair' in analogy to the `long exact sequence' in homological 
algebra (the embedding step resembles the connecting homomorphism). 
\ With respect to the long bijective stair we  
distinguish two cases: the {\em up case}, which by virtue of its especially 
simple form of the ($\tau $)-step will be used later to give new  
proofs of the basic properties (B), (M), (P) and (S) of Schubert 
polynomials, and the {\em down case}. \\  
 
\begin{Rem} There are unique `minus'-bijections $\sigma^{(n)}_{-}$ and 
$(\sigma')^{(n)}_{-}$, which `close' the rows of two above diagrams.  
In the up case (and similar in the down case) this means: there  
exists a mapping $\sigma^{(n)}_{-}: S_{n}(1)\lra S_{n-1} $,  
such that the composition of mappings $S_{n-1} 
\stackrel{\sigma^{(n)}_{+}}{\lra}  
S_{n}(n)\stackrel{\sigma_{n-1}^{*}}{\lra} \dots  
\stackrel{\sigma_{1}^{*}}{\lra} S_{n}(1)  
\stackrel{\sigma^{(n)}_{-}}{\lra} S_{n-1}$ is the identity on $S_{n-1} $ . 
Clearly $\sigma ^{(n)}_{-}$ is given by $1\ 1_{+}(\pi )\mapsto \pi $ 
and $\tau^{(n)}_{-}$ by $\ooo{0}\ l \mapsto l$ ;  
$\partial^{(n)}_{-}$ means: first set $x_{1}=0$ and then apply 
$1_{-}'$ , i.e. $x_{k}\mapsto x_{k-1}$ for all $k$. Similarly 
$(\sigma')^{(n)}_{-}$ is given by $\pi\ n \mapsto \pi $ and 
$(\tau')^{(n)}_{-}$ by $l\ \ooo{0} \mapsto l$ ; 
$(\partial')^{(n)}_{-}$ is the reversal of the embedding $\scal_{n-1} 
\hookrightarrow \scal_{n}$ , i.e. forgetting $x_{n}^{0}$ . \end{Rem}
 
\begin{Cor}  Let $\pi'\in S_{n+m}$ be the image of $\pi\in 
S_{n}$ under right embedding, i.e. $L(\pi')= \ooo{0\dots 0}\ L(\pi)$ 
with $m$ zeros (cf. Section 1), then \begin{equation*} 
X_{\pi}= (1_{-}^{\downarrow})^{m} (X_{\pi'} | _{x_{1}=\dots=x_{m}=0})\ ,
\end{equation*}
i.e. in order to compute $X_{\pi}$ from $X_{\pi'}$ set $x_{1}=\dots=x_{m}=0$
 and shift all indices by $-m$.\end{Cor} 
 
We close this section with an investigation of the recursive structures for 
double Schubert polynomials:  
 
For arbitrary $n$ and $\pi \in S_{n}$ the  
{\it double Schubert polynomials} $\X_{\pi }(x,y)\in \Z[x,y]$  
in the sets of variables $x=(x_{1},x_{2},\dots)$ and $y=(y_{1},y_{2},\dots)$ 
are defined by \begin{equation*} \X_{\pi }(x,y) :=  
\partial_{\pi^{-1} \omega _{n}} \Delta _{n}(x,y) {\rm \ with\ } 
\Delta _{n}(x,y):= \prod_{i+j \leq n} (x_{i}-y_{j}) ,\end{equation*} 
where $\partial_{\pi^{-1} \omega _{n}}$ acts only on the $x$ variables. 
 
The calculation of the double Schubert polynomials from this 
definition is especially simple, if the ordinary Schubert polynomials are 
already known: substitute $\Delta _{n}(x,y)$ in the definition 
according to the formula ([M1],(5.7)\,) 
\begin{equation*} \Delta _{n}(x,y)= \sum_{\pi \in S_{n}} \X_{\pi }(x)  
\X_{\pi \omega _{n}}(-y) \  , \end{equation*} then the divided differences  
do not affect the $\X_{\pi \omega _{n}}(-y)$'s and 
by Prop.3.1 e)\  $\partial_{k} X_{\pi } (x) = X_{\pi \sigma _{k}}(x)$, if  
$\pi k>\pi  (k+1)$, or otherwise it vanishes.  
(Formula (6.3) of [M1] does not seem favorable for $n$ greater say 4 , 
because much information on the weak Bruhat order of $S_{n}$ is needed.) 
 
Alternatively double Schubert polynomials can be calculated 
recursively; the commutative diagrams above remain completely the 
same, but now the operators $\partial_{+}$ and $\partial_{+}'$ are 
defined as follows: assume $\pi\in S_{n-1}$, then \begin{align*} 
\partial^{(n)}_{+}\ \X_{\pi}(x,y)  
:= (x_{1}-y_{1}) \dots (x_{n-1}-y_{1})\ 1_{+,y}^{\downarrow} 
\ \X_{\pi}(x,y) \\
(\partial')^{(n)}_{+}\ \X_{\pi}(x,y) 
:=(x_{1}-y_{1}) \dots (x_{1}-y_{n-1})\ 1_{+,x}^{\downarrow}\ \X_{\pi}(x,y) , 
\end{align*} where $1_{+,x}^{\downarrow} , 1_{+,y}^{\downarrow}$ increase 
the indices of the $x_{i}$'s and $y_{j}$'s respectively by one. The proof of 
these formulas is analogous to that of Prop.3.3: for the down case 
one uses $\Delta _{n}(x,y) =  
(x_{1}-y_{1}) \dots (x_{1}-y_{n-1})\ 1_{+,x}^{\downarrow}\ \Delta _{n-1}(x,y)$ 
and for the up case $\Delta _{n}(x,y) =  
(x_{1}-y_{1}) \dots (x_{n-1}-y_{1})\ 1_{+,y}^{\downarrow}\ \Delta_{n-1}(x,y)$. 
Observe that for $\pi\in S_{n-1}$ only $\partial_{k} $ with $1\leq k 
\leq n-2 $ occurs in $\partial_{\pi^{-1} \omega _{n}}$ and that for  
these $k$ one has  
$\partial_{k} (x_{1}-y_{1}) \dots (x_{n-1}-y_{1})\ 1_{+,y}^{\downarrow}= 
(x_{1}-y_{1}) \dots (x_{n-1}-y_{1})\ \partial_{k}\ 1_{+,y}^{\downarrow}= 
(x_{1}-y_{1}) \dots (x_{n-1}-y_{1})\ 1_{+,y}^{\downarrow}\ \partial_{k}$ . 
\vspace{20pt}


\section{Operations on Lehmer codes} 
 
In this section we study mainly the up case of the long bijective 
staircase for Lehmer codes and permutations;  
the down case is completely analogous and will be summarized at the end. 
 
In contrast to the definition of the $\partial_{\pi^{-1} \omega_{n}}$, 
the long bijective stair has the property that each item 
is reached by a uniquely determined sequence of building operations  
beginning at the `root' $\emptyset $ . It turns out that this sequence  
can itself be described by a Lehmer code. As an example consider 3.4 above: 
$\ooo{30010}= \tau_{3} \tau_{2} \tau_{1}  \tau^{(5)}_{+} \tau_{2} \tau_{1}
\tau^{(4)}_{+} \tau^{(3)}_{+} \tau_{1} \tau^{(2)}_{+}  
\tau^{1}_{+}\ ( \emptyset ) $ , where  
$\tau^{(1)}_{+}:\LL_{0}\lra\LL_{1} , \emptyset \mapsto \ooo{0}$. 
We now divide this sequence into parts each beginning with a  
$\tau_{+}$ and ending before the next $\tau_{+} $ to the 
left. Representing `parts' $\tau_{k}\dots\tau_{1} 
\tau_{+} $  by the number $k$ and a `part' $\tau_{+} $ 
by the number $0$ , the building sequence for $\ooo{30010}$ (in the 
up case) can be coded by the sequence of numbers $32010$ . 
 
Let now $\lae $ denote the mapping, which assigns to each Lehmer code  
the description of its up case building sequence with respect  
to the abbreviations given above. Clearly this description is itself  
a Lehmer code and $\lae$ is a graded bijection of $\LL_{\infty }$  
onto itself.  
 
Let $\lae (l)\equiv \ooo{e_{n-1}\dots e_{0}}$ for $l=\ooo{l_{n-1}\dots l_{0}}  
\in \LL_{n}$ and let $l^{(i)}$ be the last item on level $i$ in the 
(up case) building sequence for $l$ , so $l^{(0)}=\emptyset $ and  
$l^{(n)}=l$ . Then $e_{i}=k$ {\em iff} $l^{(i+1)} \in \LL_{i+1} (k)$,  
i.e. {\em the index of the first zero (left to right) in $l^{(i+1)}$  
is $k$}. Because indices for Lehmer codes are counted from right to left  
beginning with a zero, we have chosen the arrow over $E$ pointing to the 
left. Observe further that the mapping $(\tau_{+})^{-1} 
(\tau_{1})^{-1}\dots (\tau_{k-1})^{-1} : 
\LL_{i+1} (k) \lra \LL_{i}$ , which maps $l^{(i+1)}$ to 
$l^{(i)}$ is accomplished by the transformation \begin{equation*} 
\ooo{l_{i}\dots l_{k+1} 0\ l_{k-1}\dots l_{0}}	\mapsto 
\ooo{(l_{i}-1)\ \dots\ (l_{k+1}-1)\ l_{k-1}\dots l_{0}}\ .\end{equation*} 
Therefore we have specified an algorithm, which allows the computation of 
the $\lae$-transform and moreover yields all information needed to compute a 
certain Schubert polynomial $X_{\pi}$ for $\pi\in S_{m}$ under the 
assumption that all Schubert polynomials $\scal_{n}$ for some $n < m$ are 
already known, thus bringing the recursive structures of Section 3 to a 
practical level. \\ 
 
\begin{Ex} $\lae(\ \ooo{30010}\ )=\ooo{32010}$: 
$\begin{array}{rcl} 3\underline{0}010  & | & 3 \\ 
				   2\underline{0}10   & | & 2 \\ 
				   11\underline{0}	  & | & 0 \\ 
				   \underline{0}0     & | & 1 \\ 
				   \underline{0}      & | & 0  \end{array} $ 
and under the assumption that all of $\scal_{3}$ is known,  
one can calculate $X_{L^{-1}( \ooo{30010} )}$ by applying the operator\\  
$\partial_{2} \partial_{3} \partial_{4} (\epu)^{(5)} \partial_{2} 
\partial_{3} (\epu)^{(4)}$  to $X_{L^{-1}( \ooo{110} )}$. \end{Ex}
 
\begin{Rem} For the last statement of Ex.4.1 we used the rule that 
{\em $\tau_{k}\dots\tau_{1}\tau^{(i)}_{+} $ on 
$\LL_{i}$ corresponds to $\partial_{i+1-k}\dots\partial_{i} (\epu)^{(i)}$ 
on $\scal_{i}$}. Concerning the whole building sequence for some 
$X_{\pi},\ \pi\in S_{n}$, the $n-1$ factors $\epu$ can be commuted 
to the right and give $(\epu)^{n-1} ( 1 )=x^{E_{n}}$; the remaining 
$l(\pi)$ factors $\partial_{\nu} $ are now applied to $x^{E_{n}}$ 
with the result $X_{\pi}$. Hence the sequence of the indices of the  
$\partial_{\nu } $ is a reduced sequence for $\pi^{-1}\omega _{n}$ , 
which can be computed from $\lae(L(\pi))\equiv \ooo{e_{n-1}\dots e_{0}}$ 
by application of the mapping \begin{quote} 
$\Phi' ( \ooo{e_{n-1}\dots e_{0}} ) := \Phi'_{n-1} ( e_{n-1} ) \dots  
\Phi'_{0} ( e_{0} )$, \\ where $\Phi'_{i} ( k ):= (i+1-k)\dots i$ if $k>0$ 
and $\Phi'_{i} ( 0 ) = \emptyset $. \end{quote} 
Consequently $|\lae(L(\pi))|= n (n+1)/2 - |L(\pi)|$ for $\pi\in 
S_{n}$. In general $\Phi'\ \lae(L(\pi)) \linebreak \neq \Phi\  
L(\pi^{-1}\omega_{n})$, where $\Phi $ is the mapping from Cor.2.11 . \end{Rem}
 
\begin{Rem} Different reduced words for the calculation of some 
$X_{\pi}$ can lead to very different amount of work, because of the 
intermediary number of monomials involved. For example the permutation 
$\pi^{-1}\omega _{5}=52341 \approx \ooo{41110}$ has the reduced sequences 
$1234321$ and $4321234$, the first leading to an economic computation  
of $X_{\pi}=X_{14325}$, which increases the number of monomials gradually 
up to the maximum number necessary; the second blows up the number of 
intermediary monomials, and finally reduces them by cancelation. 
Clearly the number of intermediary monomials is minimized, if one 
follows the bijective staircase, because every application of an 
operator $\partial_{i} $ gives a Schubert polynomial with non-negative integer
coefficients. \end{Rem} 
 
Using the algorithm for $\lae$ one easily computes  
$\lae (\ \ooo{(n-1)\dots 0}\ )= 
\ooo{0\dots 0}$ and $\lae (\ \ooo{0\dots 0}\ )=\ooo{(n-1)\dots 0}$ . 
More generally let $\pi'$ be the natural embedding of $\pi\in S_{n}$ 
into $S_{m}$ ($n<m$), i.e. $l'=L(\pi')$ equals $l=L(\pi)$ with $m-n$ 
zeros appended to the right. Then we have 
$\lae(l')= (m-n)_{+}( \lae(l) ) \ooo{(m-n-1)\dots 1\ 0}$, 
$\lae^{2}(l')= \ooo{0\dots 0}\ \lae^{2}(l)$, 
$\lae^{3}(l')= \ooo{m\dots (n+1)}\ \lae^{3}(l)$, and 
$\lae^{4}(l')= \lae^{4}(l) \ooo{0\dots 0}$ $= l'$. The 4-cycle appearing 
here is no accident, in fact one of our next results is 
$\lae^{4}=id_{\LL_{\infty }}$. 
 
Closely related with $\lae$ is the operator $\rae$, which differs 
from $\lae$ only in {\em counting the position of the first zero  
beginning with zero from left to right}:\\  
 
\begin{Ex} $\rae(\ \ooo{30010}\ )=\ooo{11200}$: 
$\begin{array}{rcl} 3\underline{0}010  & | & 1 \\ 
				   2\underline{0}10   & | & 1 \\ 
				   11\underline{0}	  & | & 2 \\ 
				   \underline{0}0     & | & 0 \\ 
				   \underline{0}      & | & 0  \end{array} $.  
Note that $\pi=41253\approx \ooo{30010}$ and $\ooo{11200}\approx 
23514=\pi^{-1}$.  \end{Ex} 
 
\begin{Prop} For all $\pi\in S_{\infty }$: 
$\rae(L(\pi))=L(\pi^{-1}) = H(\pi)$. \end{Prop} 
\begin{proof}  As usual let $\pi\in S_{n}$ . The proof of Prop.2.4 
shows $l_{n-k}(\pi^{-1})=\{j| j<\pi^{-1} k, \pi j> k \}$, i.e.  
$l_{n-k}(\pi^{-1})$ is the number of letters in $\pi$ left to the letter $k$ 
greater than $k$ . But in the $k^{th}$ step of the algorithm for the 
determination of $\rae(L(\pi))$ the zero of the intermediary Lehmer 
code corresponds to the letter $k$ in $\pi$ (--- the $k-1$ zeros in the 
preceding steps correspond to $1,\dots,k-1$ ---); hence all entries in 
the intermediary Lehmer code other than the first zero correspond to 
letters in $\pi$ greater than $k$ and the algorithm for $\rae(L(\pi))$ 
counts exactly the number of these entries left to the first zero. 
\end{proof}  
 
\begin{Cor} Let $\varepsilon : S_{\infty }\lra S_{\infty }$ 
be defined on $\pi\in S_{n}$ by $\pi \mapsto \omega _{n} \pi^{-1}$ and 
recall that $\iota $ is the involution on Lehmer codes from Lemma 2.1, then:\\ 
a) $\lae=\iota \ \rae$ and $\lae\ L=L\ \varepsilon $;\\ 
b) $\rae=\iota \ \lae$, $\lae^{4}=id$, $\rae^{2}=id$, $\lae\ \rae=\iota 
$, $\lae\ \rae\ \lae\ \rae=\rae\ \lae\ \rae\ \lae=id$. \end{Cor}  
\begin{proof} a): $\lae(L(\pi))=\iota \ \rae(L(\pi))$ for all $\pi\in S_{n}$, 
because the counts in the $k^{th}$ step of the algorithm for the  
determination of $\lae(L(\pi))$ and $\lae(L(\pi))$ add up to $n-k$. 
Moreover by Lemma 2.1 f): $\lae(L(\pi))=\iota \ \rae(L(\pi)) =\iota \ 
L(\pi^{-1})= L(\omega _{n}\pi^{-1})= L(\varepsilon \pi)$. b) is immediate.
\end{proof} 
 
\begin{Rem}  In (4.1) it has been shown that 
$\Phi' (\lae(L(\pi))) \in R(\pi^{-1} \omega _{n})$. By Cor.4.6 this implies  
$\Phi'\ L(\omega_{n} \pi^{-1}) \in R(\pi^{-1} \omega _{n})$ or 
\begin{equation*} 
\Phi'\ L(\omega_{n} \pi \omega_{n} ) \in R(\pi) \ ,\end{equation*}  
which is therefore a second method to compute a reduced word for an 
arbitrary permutation.  
For example $\pi=41532\approx \ooo{30210}\ \stackrel{\Phi}{\lra} 
321434 \in R(\pi)$ and $\omega_{5} \pi \omega _{5}=43152 \approx  
\ooo{32010} \stackrel{\Phi'}{\lra} 234231 \in R(\pi)$. \end{Rem}
 
\begin{Rem}   In view of Cor.4.6 it seems interesting to 
describe the sets $fix_{n}(\varepsilon^{m}) :=  
\{ \pi\in S_{n} \mid \varepsilon^{m}\pi=\pi\ \}$ in more detail. 
Trivially $fix_{n}(\varepsilon^{4})=S_{n}$ and by cyclicity it is 
enough to investigate $fix_{n}(\varepsilon^{m})$ for $m=1,2,3$. 
We have $\varepsilon (\pi) = \omega _{n} \pi^{-1}$, 
$\varepsilon^{2} (\pi) = \omega _{n} \pi\omega _{n}$ and  
$\varepsilon^{3} (\pi) = \pi^{-1} \omega _{n}$ and  
$fix_{n}(\varepsilon^{3}) = fix_{n}(\varepsilon)$ , because 
$\varepsilon^{3} (\pi) = \pi \gdw \pi^{2}=\omega _{n} \gdw \pi= 
\omega _{n} \pi^{-1} =\varepsilon (\pi) $. The next result fully 
describes the situation in the remaining cases $m=1,2$ for all $n\in 
\N$. \end{Rem} 
 
\begin{Prop} a) $| fix_{2n+1}(\varepsilon^{2}) | = 
| fix_{2n}(\varepsilon^{2}) | = n!\ 2^{n}$ ;\\ 
b) $| fix_{n}(\varepsilon) | = 0$, if $n\equiv 2,3\ (\bmod 4)$ and 
$| fix_{4n+1}(\varepsilon) | = | fix_{4n}(\varepsilon) | = (2n)!/n!$.\\ 
Moreover the proof contains a procedure to enumerate the elements of  
these sets. \end{Prop}
\begin{proof} $\varepsilon^{2} (\pi) = \pi \gdw \omega _{n}\pi = 
\pi \omega _{n} \gdw \pi i +\pi(n+1-i)= n+1$,  
i.e. letters on complementary places in $\pi$ are complementary.  
Hence every $\pi\in fix_{2n}(\varepsilon ^{2})$ is completely 
determined by $\pi 1,\dots ,\pi n$. There are $n$ pairs of 
complementary numbers in $\{1,\dots,2n\}$, $2^{n}$ possibilities for  
selecting one number from every pair and $n!$ permutations for every 
selection. The bijection $a_{1}\dots a_{n}\ a_{n+1}\dots a_{2n} \mapsto 
a_{1}\dots a_{n}\ ((n+1)/2)\ (a_{n+1}+1)\dots (a_{2n}+1)$ from  
$fix_{2n}(\varepsilon^{2})$ to $fix_{2n+1}(\varepsilon^{2})$ 
completes the proof of a). 
 
$\pi\in fix_{n}(\varepsilon) \gdw \pi^{2}=\omega _{n}$ implies 
$\pi^{4}=id$, so that the possible cycle lengths of $\pi$ are $1,2,4$. 
If $\pi$ has a fixpoint $k$, then $k=\pi^{2} k= \omega _{n} k= n+1-k 
\gdw k=(n+1)/2$, and if $k$ lies in a 2-cycle of $\pi$, then $k$ is 
already a fixpoint. Therefore any $\pi\in fix_{n}(\varepsilon)$ 
factorises into proper 4-cycles and for odd $n$ there is exactly one 
additional 1-cycle $((n+1)/2)$ possible. This shows that 
$fix_{n}(\varepsilon)= \emptyset $, if $n\equiv 2,3\ (\bmod 4)$, and 
that $2n+1$ is the unique fixpoint for every $\pi\in fix_{4n+1}(\varepsilon)$. 
 
Now let $\pi\in fix_{4n}(\varepsilon)$, then every $i \in \{1,\dots,4n\}$ 
generates a 4-cycle \linebreak $( i, \pi i, \pi^{2}i=\omega _{4n}i, \pi^{3}i= 
\pi^{2}(\pi i)=\omega _{4n}\pi i )$. Suppose that $k$ 4-cycles of 
$\pi$ are already determined ($0\leq k \leq n-1$) and that $M_{k}$ is 
the set of numbers contained in these 4-cycles, then a new 4-cycle 
can be constructed by defining $i:=\min \{1,\dots,4n\}\setminus M_{k}$; 
clearly $\pi i \in \{1,\dots,4n\}\setminus M_{k}$ and because $\pi$ is  
fixpoint free: $\pi i \neq i$ and $\pi i \neq \omega _{4n}i$, otherwise 
$\pi ( \omega _{4n} i )= \pi^{2}i= \omega _{4n}$. Therefore one has  
$| \{1,\dots,4n\}\setminus M_{k} |-2 = 4n-4k-2$ choices for $\pi i$ 
and consequently $| fix_{4n+1}(\varepsilon) | = \prod_{k=0}^{n-1} 
(4(n-k)-2)=(2n)!/n!$. In exactly the same manner the  
$\pi\in fix_{4n}(\varepsilon)$ are constructed, where the fixpoint 
$2n+1$ is a priori excluded. \end{proof}
 
As examples we note $fix_{1}(\varepsilon)=S_{1}$, $fix_{4}(\varepsilon)=  
\{ 2413, 3142 \}$, $fix_{5}(\varepsilon)= \{ 25314, 41352 \}$ and 
$fix_{8}(\varepsilon)= \{\ 28463517, 28536417, 34872156, 35827146, 
43781265, 46281735\ \} \cup \{ $ the same $\pi$ read backwards $ \}$.
\\ \\ \\ 
We now briefly discuss the {\it down case} anlogues of the 
preceding results. 
 
The role of $\lae$ is now played by $\rae'$. The $i^{th}$  
component of $\rae'(L(\pi))$ is the number --- counted from left to right  
beginning with zero --- of the first place, where $l_{k}^{(i+1)}=k$, and  
$l_{k}^{(i+1)}$ is the component with index $k$ of the last 
intermediary Lehmer code on level $i+1$ in the (down case) building  
sequence for $L(\pi)$. The reduction step from $l^{(i+1)}$ to $l^{(i)}$ 
is now simply elimination of $l_{k}^{(i+1)}$, because $l_{k}^{(i+1)}$ 
corresponds to $i+1$ in $\pi$ --- the numbers $n,\dots,i+2$ have been 
removed in previous steps. 
 
\begin{Ex} $\rae'(\ \ooo{30010}\ )=\ooo{30210}$: 
$\begin{array}{rcl} 300\underline{1}0  & | & 3 \\ 
				   \underline{3}000   & | & 0 \\ 
				   00\underline{0}	  & | & 2 \\ 
				   0\underline{0}     & | & 1 \\ 
				   \underline{0}      & | & 0  \end{array} $ 
and under the assumption that all of $\scal_{3}$ is known,  
one can calculate $X_{L^{-1}( \ooo{30010} )}$ by applying the operator  
$\partial_{3} \partial_{2} \partial_{1} (\partial')^{(5)}_{+}  
(\partial')^{()}_{+}$ to $X_{L^{-1}( \ooo{000} )}$.  \end{Ex}
 
For the last statement of Ex. 4.1' we used the rule that 
$\tau_{i-k+1}\dots\tau_{i}(\tau')^{(i)}_{+} $ on 
$\LL_{i}$ corresponds to $\partial_{k}\dots\partial_{1}  
(\partial')^{(i)}_{+}$ on $\scal_{i}$. Since we have 
$\epd\circ\partial_{i}=\partial_{i+1}\circ\epd$, the 
sequence of indices of the $\partial_{\nu } $ is $\in R(\pi^{-1}\omega_{n})$ 
and equals $\Phi ( \pi^{-1}\omega_{n} )$ \ ($\Phi$ from Cor.2.11). 
 
To $\rae$ corresponds the operator $\lae'$, which is the same as $\rae'$ 
except that counting proceeds from the right to left beginning with zero, 
e.g. $\lae'(\ \ooo{30010}\ )=\ooo{13000}$.\\ 
\begin{Prop} For all $\pi\in S_{\infty }$: 
$\lae'(L(\pi))=L(\omega \pi^{-1}\omega )=G(\pi)$. \end{Prop} 
\begin{Cor} Let $\varepsilon': S_{\infty }\lra S_{\infty }$ 
be defined on $\pi\in S_{n}$ by $\pi \mapsto \pi^{-1}\omega _{n}$, then:\\ 
a) $\rae'=\iota \ \lae'$ and $\rae'\ L=L\ \varepsilon'$;\\ 
b) $\lae'=\iota \ \rae'$, $(\rae')^{4}=id$,  
$(\lae')^{2}=id$, $\rae'\ \lae'=\iota$, \\ \hspace*{110pt}  
$\rae'\ \lae'\ \rae'\ \lae'=\lae'\ \rae'\ \lae'\ \rae'=id$;\\ 
c) $\rae\ \lae'\ L(\pi) = \lae'\ \rae\ L(\pi) = L(\omega \pi \omega) 
= K(\pi)$. \end{Cor}
 
The sets $fix_{n}(\varepsilon^{m})$ and $fix_{n}( (\varepsilon')^{m})$ 
coincide, because $\varepsilon (\pi)=\pi \gdw \varepsilon^{3} (\pi)=\pi$ 
and $\varepsilon'=\varepsilon^{3} $. \\ 
 
As a further application of the operators discussed in this section 
we show that the mapping $\pi \mapsto \omega \pi \omega $ for 
unembedded permutations $\pi$ generalizes the conjugation of 
partitions: 
 
\begin{Prop}  Let $\lambda =\lambda _{1} \dots \lambda _{m}$ 
with $\lambda _{1}\geq\dots\geq \lambda _{m}\geq 1$ be a partition, $\lambda 
'$ its conjugate and $\pi(\lambda ) = 
L^{-1}\ ( \ooo{\lambda_{m}\dots\lambda_{1} \ 0\dots 0} )$  
(with $\lambda _{1}$ zeros) the corresponding Grassmannian 
permutation in $S_{n} , \ n=m+\lambda _{1}$; then \begin{equation*} 
\pi(\lambda ') = 
\omega _{n}\ \pi(\lambda )\ \omega _{n}\ .
\end{equation*} \end{Prop} 
\begin{proof} \begin{align*}\rae\ \lae'\ L(\pi(\lambda )) =&  
\rae\ \lae'\ ( \ooo{\lambda_{m}\ \dots\ \lambda_{1} \ 
\underbrace{0\ \dots\ 0}_{\lambda _{1}} } ) \\ 
=& \rae\ \ \ooo{\lambda _{1}\ 
\underbrace{0\ \dots\ 0}_{\lambda_{1}-\lambda_{2}} \  
\lambda_{2}\ \dots\ \lambda _{m-1}\  
\underbrace{0\ \dots\ 0}_{\lambda_{m-1}-\lambda_{m}}\  
\lambda _{m} \ \underbrace{0\ \dots\ 0}_{\lambda_{m}} } \\
=& \ooo{\underbrace{1\ \dots\ 1}_{\lambda_{1}-\lambda_{2}} \ 
\underbrace{2\ \dots\ 2}_{\lambda_{2}-\lambda_{3}}\  \dots \   
\underbrace{m-1\ \dots\  m-1}_{\lambda_{m-1}-\lambda_{m}} \   
\underbrace{m\ \dots\ m}_{\lambda_{m}} \ \underbrace{0\ \dots\ 0}_{m} }\ .
\end{align*} 
Clearly the last expression is the Lehmer code of $\pi(\lambda ')$ 
and the result follows from Cor. 4.7$'$ c). \end{proof}
\vspace{20pt}

\section{Proofs of properties (B), (M), (P) and (S)} 
 
All proofs proceed by long induction over all permutations $\pi\in  
S_{\infty }$ using the up case long bijective staircase. The 
beginning of the induction is always trivial and will not be 
mentioned hereafter; the $(+)$-step is usually easy  
and the main work is always to be done in the 
$(\partial)$-step. In contrast to the $(\partial)$-step  
in proofs proceeding from the definition of Schubert 
polynomials we now have to consider only the very special situation 
of the $S_{n}(k)$'s, which is much easier to handle. 
 
For $f\in\Z[x]$\ let $M(f)$ and $\dcal M(f)$ denote respectively the 
set of monomials and exponents of monomials occurring in $f$ . 
 
\begin{proof} {\bf (B)}\ \ $(+)$-step: assume (B) for all $\pi\in S_{n-1}$, 
then $\dcal M(X_{\sigma _{+}\pi}) =\dcal M((\epu)^{(n)}(X_{\pi}))\  =
 1_{+}\dcal M(X_{\pi})$ implies $lmin (X_{\sigma _{+}\pi})=x^{1_{+}\pi}= 
x^{\sigma _{+}\pi}$ with coefficient $1$. 
 
$(\partial )$-step: let $d^{0}$ and $(d')^{0}$ correspond respectively 
(by re indexing) to $L(\pi)$ with $\pi\in S_{n}(k+1)$ and $L(\pi\sigma_{k})$ 
; let $\partial_{k} d $ denote the k-symmetrisation of $d$ in 
$\Z\dcal_{\infty }$ (cf. Ex.2.1). Assume now for $d,d' \in \dcal_{n}$ 
that $d<d'$ in the lexicographic order and that $\partial_{k} d, 
\partial_{k}d'\neq \emptyset $; it is not hard to see that this implies 
$lmin(\partial_{k} d)< lmin(\partial_{k} d')$. Therefore $lmin 
(X_{\pi\sigma _{k}})=x^{L(\pi\sigma k)}$ with coefficient 1, since 
for $d^{0}$ we have: $d^{0}_{k}>0 ,\ d^{0}_{k+1}=0 \Rightarrow 
\partial_{k}d^{0} \neq \emptyset $ and $lmin(\partial_{k}d^{0} 
)= (d')^{0 }$. \end{proof}
 
\begin{proof} {\bf (M)}\ \ The $(+)$-step is trivial. \  For the 
$\partial$-step observe that for $\pi\in S_{n}(k+1)$ one has  
$L(\pi\sigma_{k})= \ooo{l_{n-1}\dots l_{n-k+1} \ 0\dots 0}$ with  
$l_{n-1},\dots,l_{n-k+1}\geq 1$; therefore $L(\pi)= $ \hfill\linebreak
$ \ooo{l_{n-1}\dots l_{n-k+1} \ 1\ 0\dots 0}$ and `$\pi\sigma _{k}$  
dominant' implies `$\pi$ dominant'. Hence we compute 
$X_{\pi\sigma _{k}}=\partial_{k} X_{\pi}=\partial_{k} x^{L(\pi)}=x^{\tau 
_{n-k} L(\pi)}=x^{L(\pi\sigma _{k})}$. \end{proof}
 
\begin{proof} {\bf (P)}\ \ Clearly (P) is valid for $\pi \in  S_{1},\ S_{2}$. 
Assume (P) for $S_{1},\dots, S_{n}\ (n\geq 2)$ and let $\pi \in 
S_{n+1}(k+1)$. Then $X_{\pi}= \partial_{k+1} \dots \partial_{n}\ ( 
x_{1} \dots x_{n}\ X_{\rho})$ for $\rho= \pi (1)-1 \dots \pi (k) -1\ 
\pi (k+2)-1 \dots \pi (n+1)-1 \in S_{n}$. By the product rule one has 
for all $\nu\in \N,\ f \in \Z[x]$:\begin{equation*} 
\partial_{\nu}\ ( ( x_{1} \dots x_{\nu})\ f ) = ( x_{1} \dots x_{\nu-1})\  
(f + x_{\nu+1} (\partial_{\nu} f )) \equiv ( x_{1} \dots x_{\nu-1})\  
(\ooo{\partial_{\nu}} f ) \ , \end{equation*} i.e.  
$\ooo{\partial_{\nu}}= id + x_{\nu+1}\ \partial_{\nu}$. Therefore 
$X_{\pi}= (x_{1} \dots x_{k})\  
(\ooo{\partial_{k+1}}\dots \ooo{\partial_{n}}\ X_{\rho})$.  
Let $m_{k}(x)$ denote a monomial in $x_{k+1},\dots , x_{n}$; expanding  
$\ooo{\partial_{k+1}}\dots \ooo{\partial_{n}}\ X_{\rho}$ gives a sum 
with terms of the form $m_{k}(x) \cdot  
\ooo{\partial_{\nu_{1}}}\dots \ooo{\partial_{\nu_{s}}}\ X_{\rho}$, 
where $k+1 \leq \nu_{1}< \dots < \nu_{s} \leq n$. Now by Prop.3.1 e) 
every nonvanishing summand is of the form $m_{k}(x) \cdot X_{\rho'}$ 
for some $\rho' \in S_{n}$ and the induction hypothesis gives the result.
\end{proof} 
 
As a preparation for the proof of property (S) we investigate first how 
Grassmannian permutations are embedded into the (up case) long bijective 
staircase. In this section let a partition $\lambda $ be of the form 
$\lambda =(\lambda _{1},\dots,\lambda _{m}),\  
\lambda_{1}\geq \dots\geq \lambda_{p}>0,\ \lambda_{p+1},\dots, 
\lambda_{m}=0$ for $m\geq p>0$; 
then we denote the Schur polynomial in the variables $x_{1},\dots,x_{m}$ 
by $\{\lambda\}^{m}$. Now (S) says that $\{\lambda\}^{m}=X_{L^{-1}(l)}$ 
with $l=\ooo{0\dots 0\ \lambda _{p}\dots \lambda_{1}\ 0\dots 0}$ having $m-p$ 
zeros on the left and $\geq \lambda _{1}$ zeros on the right. We 
consider the following subsequence of the long bijective 
staircase \begin{multline*}
\ooo{0\dots 0\ \lambda _{p}\dots \lambda_{1}\ 0\dots 0} 
\stackrel{\tau_{+}}{\lra} 
\ooo{1\dots 1\ \lambda _{p}+1\dots \lambda_{1}+1\ 1\dots 1\ 0}\lra\dots 
\\   \lra \ooo{1\dots 1\ \lambda _{p}+1\dots \lambda_{1}+1\ 0\dots 0\ 0} 
\lra\dots\lra \ooo{0\ 0\dots 0\ \lambda _{p}\dots \lambda_{1}\ 0\dots 0}.
\end{multline*} 
In this sequence 
$\ooo{1\dots 1\ \lambda _{p}+1\dots \lambda_{1}+1\ 0\dots 0\ 0}$ 
should correspond by (S) to $\{1_{+}( \lambda) \}^{m}$ and \linebreak 
$\ooo{0\ 0\dots 0\ \lambda _{p}\dots \lambda_{1}\ 0\dots 0}$ to 
$\{\lambda\}^{m+1}$. Clearly all other intermediary Lehmer codes are 
not weakly increasing and all paths in the long bijective staircase,  
which start with a $\sigma _{+}$-step from a non-grassmannian permutation, 
can contain only non-grassmannian permutations.  
 
Furthermore every weakly increasing sequence $l^{+}$ of nonnegative numbers  
can be obtained by a sequence of operations of the following two  
types: \begin{quote} (1): $l^{+} \mapsto 1_{+}(l^{+})$\ \  and \ \ \  
(2): $l^{+} \mapsto 0\ l^{+}$ \end{quote} applied to $-1$.  
For partitions $\lambda $ and Schur polynomials $\{\lambda \}^{m}$ the
corresponding operations are (1): $\lambda \mapsto 1_{+}\lambda $, 
(2): $\lambda \mapsto \lambda\ 0$ and
(1): $\{\lambda \}^{m}\mapsto \{ 1_{+}(\lambda) \}^{m}) $, 
(2): $\{\lambda \}^{m}\mapsto \{\lambda \}^{m+1}$  
beginning at the empty partition or the constant $1$.  
For Lehmer codes $l=L(\pi)\equiv\ooo{0\dots 0\ \lambda _{p}\dots \lambda_{1}\  
0\dots 0}$ with $l_{n-m}=\lambda _{1}$ and $\lambda _{1}$ zeros on the 
right side this means \begin{align*} {\rm (1):} &\  l\mapsto l^{(1)}:=  
\ooo{1\dots 1\ \lambda _{p}+1\dots \lambda_{1}+1\ 0\dots 0\ 0} = 
\tau _{\lambda _{1}} \dots \tau _{1}\ \tau _{+}\ l \\ 
{\rm (2):} &\  l\mapsto l^{(2)}:=  
\ooo{0\ 0\dots 0\ \lambda _{p}\dots \lambda_{1}\ 0\dots 0} = 
\tau _{\lambda _{1}+m} \dots \tau _{\lambda _{1}+1}\ l^{(1)}\ . 
\end{align*}  
 
Similarly to Section 4 we can describe the uniquely determined building 
sequence for a weakly increasing Lehmer code and its corresponding 
Schubert polynomial by another Lehmer code. To accomplish this we 
define the following operators on $\Z[x]$: \begin{align*} 
{\rm (1):}& <0> \ :\  up_{+}\  \text{ and }\\ 
{\rm (2):}& <m> \ :\  \partial_{1}\dots \partial_{m}\ up_{+} \  \text{ for 
$m\in\N$, where $up_{+}$ means: }\\ 
& \ \ \ \text{ increase the exponents by 1 
{\em without}  increasing the number of variables. }
\end{align*} 
Now the $\partial_{m} $'s introduce the new variables $x_{m+1}$ and the 
beginning step is \linebreak $<0> (\emptyset ):= x_{1}^{0}$.  
 
A convenient way to compute this operator for a Grassmannian 
permutation $\pi$ is to look at the sequence 
$L(\pi)^{+}\equiv \ooo{0\dots 0\ \lambda _{p}\dots \lambda_{1}}$, i.e.  
$L(\pi)$ without end zeros: \ if $L(\pi)^{+}$ has $m$ entries, then 
the operator in question is $<(m-1)\dots 1\ 0>$ with $k$ additional zeros 
between two consecutive numbers (left to right), if the entries 
on the corresponding places in $L(\pi)^{+}$ increase by $k$.  
 
\begin{Ex} The operator corresponding to  
$\pi=12578346\approx \ooo{0023300}$ is $<43002010>$ and for  
$\pi=13524\approx \ooo{01200}$ one has $<20100>$. In fact  
(calculating in $\Z\dcal_{\infty }$) gives:  
$<20100>(\emptyset )= <2010> (0)= <201>(1)$ = $<20>(\partial_{1}(2) )$ = $ 
<20>( 10 + 01 )$= $<2>(21+12)$= $\partial_{1}\partial_{2}(32+23)$=  
$\partial_{1}(310+301+220+211+202)$=$210+120+201+111+021+111+102+012$,  
which is $X_{13524}= \{21\}^{3}$.  \end{Ex}
 
\begin{Cor} $2^{n}-n$ is the number of Grassmannian 
permutations in $S_{n}$, the number of symmetric functions in 
$\scal_{n}$, and also the number of Schur polynomials in $\scal_{n}$.
\end{Cor} 
\begin{proof} Denote by $c_{n}$ the number of Grassmannian 
permutations in $S_{n}\setminus S_{n-1}$. Clearly $c_{1}=c_{2}=1$ and 
in general $c_{n}$ is the number of operators $<a_{n-1} \dots a_{1} 
a_{0}>$ discussed above --- note that each $<a_{\nu }>$ is a mapping 
from $\scal_{\nu }$ to $\scal_{\nu +1}$. Since always $a_{0}=0$ and for the 
other $a_{\nu }$ the only choice is zero or nonzero, there are $2^{n-1}$ 
possible operators. Moreover $<(n-1)\dots 1\ 0>=<0>$ for all $n$. 
Hence $c_{n}=2^{n-1}-1$ for $n\geq 2$ and $\sum_{k=1}^{n}c_{k}=2^{n}-n$.  
The other assertions are consequences of Prop.3.1 g) and (S). \end{proof} 
 
\begin{proof} {\bf (S)} \ \ By the above discussion it is enough to show  
that $X_{L^{-1}(l)}=\{\lambda \}^{m}$ implies\   
(1):\ $X_{L^{-1}(l^{(1)})} = \{ 1_{+}(\lambda ) \}^{m}$ 
and\ (2):\ $X_{L^{-1}(l^{(2)})} = \{ \lambda\ 0 \}^{m+1}$. 
 
Recall the determinantal formula for Schur polynomials ([M3,Kr]) 
\begin{equation*} 
\{\lambda\}^{m}=V_{m}^{-1}\ \det((x_{i}^{\lambda_{j}+m-j}))_{i,j=1,\dots,m} 
\end{equation*} where $V_{m}:=\det((x_{i}^{m-j}))_{i,j=1,\dots,m}=\prod_{1\leq 
i<j\leq m} (x_{i}-x_{j})$ is the Vandermonde determinant in $m$ variables.
\\ \\ 
{\bf (1):}\ $\{ 1_{+}(\lambda ) \}^{m}= 
V_{m}^{-1}\ \det((x_{i}^{\lambda_{j}+1+m-j}))= 
V_{m}^{-1}\ \det((x_{i}^{\lambda_{j}+m-j}))\cdot x_{1}\dots x_{m}= 
x_{1}\dots x_{m} \{ \lambda \}^{m}\ =\epu(\{\lambda \}^{m})$. Hence: 
$X_{L^{-1}(l^{(1)})} =  
X_{L^{-1}(\tau _{\lambda _{1}} \dots \tau _{1}\ \tau _{+}\ l)}= 
\partial_{m+1}\dots \partial_{m+\lambda _{1}}\epu(X_{L^{-1}(l)})=\linebreak 
\partial_{m+1}\dots \partial_{m+\lambda _{1}}\epu(\{\lambda\}^{m})\cdot  
x_{m+1}\dots x_{m+\lambda _{1}}= \epu(\{\lambda\}^{m})= 
\{ 1_{+}(\lambda ) \}^{m}$, where the operator $\epu$ acts in  
$\epu(X_{L^{-1}(l)})$  on all variables and in $\epu(\{\lambda\}^{m})$ 
only on the first $m$ variables.\\  
\begin{align*} 
{\rm {\bf (2):}}&\ \ \  X_{L^{-1}(l^{(2)})} =  
X_{L^{-1}(\tau _{\lambda _{1}+m} \dots \tau _{\lambda _{1}+1}\ l^{(1)})}= 
\partial_{1}\dots\partial_{m}\ X_{L^{-1} (l^{(1)})} \stackrel{(1)}{=} \\
& \partial_{1}\dots\partial_{m}\ \{ 1_{+}(\lambda ) \}^{m} = 
\partial_{1}\dots\partial_{m}\ (\ (x_{1}\dots x_{m})\ \{ \lambda \}^{m}\ ) 
\stackrel{(a)}{=} \\ & 
\{ \lambda \}^{m} + \sum_{\nu =0}^{m-1} x_{m+1-\nu}\dots x_{m+1} 
\partial_{m-\nu} \dots\partial_{m} \{ \lambda \}^{m} \stackrel{(b)}{=} 
\{ \lambda\ 0 \}^{m+1} \end{align*} 
{\bf (a):}\ Let $g$ be a symmetric function in $x_{1},\dots,x_{m}$ and 
$0\leq k \leq m-1$; we claim : \begin{equation*} \hspace{-25pt} 
\partial_{m-k} \dots\partial_{m} ((x_{1}\dots x_{m}) g ) =  
(x_{1}\dots x_{m-k-1}) ( g+\sum_{\nu =0}^{k} x_{m+1-\nu}\dots x_{m+1}  
\partial_{m-\nu} \dots\partial_{m} g )  \end{equation*} 
Note that equality (a) is obtained by setting $g=\{\lambda \}^{m}$ and  
$k=m-1$ . We show the claim by induction over $k$.  
 
An application of the product rule yields : 
\begin{equation*} \partial_{m} ((x_{1}\dots x_{m})\ g\ )=  
(x_{1}\dots x_{m-1})\ ( g+ x_{m+1} (\partial_{m} g ) )\ \  
\text{ (case $k=0$).}\end{equation*}  
Assume now the claim to be true for some $k$, then: \begin{multline*} 
\partial_{m-k-1} \partial_{m-k} \dots\partial_{m} ((x_{1}\dots x_{m})\ g\ ) 
=\\ 
x_{1}\dots x_{m-k-2} (\ g+\sum_{\nu =0}^{k} x_{m+1-\nu}\dots x_{m+1}  
\partial_{m-\nu} \dots\partial_{m} g\ ) + \\
x_{1}\dots x_{m-k-2} x_{m-k}\ [\ \partial_{m-k-1}\ g+ \partial_{m-k-1}  
\ (\ \sum_{\nu =0}^{k-1}\ x_{m+1-\nu}\dots x_{m+1} \ 
\partial_{m-\nu} \dots\partial_{m}\ g\ ) + \\  x_{m+1-k}\dots x_{m+1} 
\partial_{m-k-1} \partial_{m-k} \dots\partial_{m} g\ ]\ .\end{multline*} 
Since $g$ is 
symmetric we note  $\partial_{m-k-1}\ g=0$ and for  
$0\leq \nu\leq k-1$: $\partial_{m-k-1} \partial_{m-\nu} \dots\partial_{m}\ g 
= \partial_{m-\nu} \dots\partial_{m} \partial_{m-k-1}\ g = 0$. Therefore 
$x_{m-k}=x_{(m+1)-(k+1)}$ completes the proof of the claim.\\ \\ 
{\bf (b):}\ With $n:=m+1$ \ \ (b) reads:\begin{equation*} 
\{ \lambda \}^{n-1} + \sum_{\nu =0}^{n-2} x_{n-\nu}\dots x_{n} 
\partial_{n-1-\nu} \dots\partial_{n-1} \{ \lambda \}^{n-1} = 
\{ \lambda\ 0 \}^{n} \end{equation*}   
\hspace{-10pt} The following {\it notations} will be helpful: 
 
$\Pi_{rs}:=\prod_{\nu=1}^{r}(x_{\nu}-x_{s})$ for $r,s \geq 1$  
and $\Pi_{0s}:=1$ for $s\in \N$; hence $\Pi_{rs}=0$ for $r\geq s$ ; 
 
$D_{i}h:= \partial_{i} h + 2 (\sigma _{i}(h))/(x_{i}-x_{i+1})=  
(h + \sigma _{i}(h))/(x_{i}-x_{i+1})$ for $h\in\Z[x]$; and  
 
for all $\lambda =(\lambda _{1},\dots,\lambda _{m})$ (as defined above)  
and canonical column vectors $e_{k}= (\delta_{ik})_{i=1,\dots,n}$  
\begin{equation*} 
\eh_{k} := \det ((\ x_{i}^{\lambda _{j}+n-1-j} \mid e_{k}\ )) 
_{\ i=1,\dots,n ; \ j=1,\dots,m}\ \ \ , \end{equation*} 
i.e. the last column of the determinant is substituted by $e_{k}$. 
This makes sense, because the operations $\sigma _{i}^{*}$ and 
$\partial_{i} $ applied to the determinant yield results independent 
of $\lambda $: \begin{align*} & \eh_{i}\circ\sigma _{i}=-\eh_{i+1},\  
\eh_{i+1}\circ\sigma _{i}=-\eh_{i} {\rm\ and\ }  
\eh_{k}\circ\sigma _{i}=-\eh_{k} {\rm\ for\ } k\neq i,i+1 \\
& \partial_{i} \eh_{i}=(\eh_{i}+\eh_{i+1})\ /\ (x_{i}-x_{i+1})= 
\partial_{i} \eh_{i+1} {\rm\ \ and\ } \\
& \partial_{i} \eh_{k}= 
2 \eh_{k}\ /\ (x_{i}-x_{i+1}) {\rm\ \ for\ \ } k\neq i,i+1\ . \end{align*}  
Moreover \begin{equation*} 
\partial_{i} \ V_{n} = 2 V_{n}\ /\ (x_{i}-x_{i+1})  
\text{\ for $1\leq i\leq n-1$ \ and\ } \sigma_{i}(V_{n})=-V_{n} 
\end{equation*} and for $1\leq j < k\leq n$ : \begin{align*} 
\partial_{i} (x_{i}-x_{i+1})=2,\ \partial_{i} (x_{j}-x_{i})= 
-1= \partial_{i} (x_{i+1}-x_{k}) \\
\partial_{i} (x_{i}-x_{k}) = 1 = \partial_{i} (x_{j}-x_{i+1}) 
{\rm\ \ for\ \ } k>i+1 {\rm\ and\ } j<i \ .\end{align*} 
Now \begin{equation*} \{ \lambda \}^{n-1} =  V_{n-1}^{-1}\  
\det ((\ x_{i}^{\lambda _{j}+n-1-j} \mid e_{k}\ ))_{i,j=1,\dots,n-1}= 
V_{n-1}^{-1} \eh_{n}= V_{n}^{-1} \Pi_{n-1\ n} \eh_{n}\ .\end{equation*} 
Hence a proof of (b) 
demands the computation of $\partial_{\nu}\dots\partial_{n-1} 
(V_{n}^{-1} \Pi_{n-1\ n} \eh_{n})$ for $1\leq \nu \leq n-1$. Since by 
the quotient rule \begin{equation*}  
\partial_{i} (V_{n}^{-1} h)= V_{n}^{-1}\ D_{i} h  
\text{\ for all $h\in\Z[x]$ ,} \end{equation*} 
it is enough to compute the expressions 
$D_{\nu}\dots D_{n-1} (\Pi_{n-1\ n} \eh_{n})$ for  
$1\leq \nu \leq n-1$.  
 
Let $h$ be the matrix of column vectors $h_{\nu}\equiv 
( h_{\nu}^{k} )_{k\in \N}$, with \begin{equation*}  
h_{\nu}^{k}:= \Pi_{\nu-1\ k}\eh_{k}  
{\rm\ \ for\ \ } \nu, k\in\N \ . \end{equation*} 
Clearly $h_{\nu}^{k}=0$ for $k<\nu$ , i.e. $h$ is a lower triangular 
matrix.	Using the above notations and results one computes 
for $n\geq 2$ and $2\leq s \leq n-1$ 
\begin{equation*} D_{n-1} h_{n}^{n} = h_{n-1}^{n}+h_{n-1}^{n-1} \text{ and }  
 D_{s-1} h_{s}^{n}  = h_{s-1}^{n}\ .\end{equation*} 
 
Therefore $D_{\nu-1} h_{\nu}^{k}= 0$, if $k<\nu$,\   
$=h_{\nu-1}^{\nu}+h_{\nu-1}^{\nu-1}$, if $k=\nu$, and  
$=h_{\nu-1}^{k}$, if $k>\nu$, which can be summarized as \begin{equation*} 
H_{\nu\ n}:=\sum_{k=1}^{n} h_{\nu}^{k}\ \Longrightarrow \  
D_{\nu-1}\ H_{\nu\ n}=H_{\nu-1\ n}\ \ {\rm for\ } 2\leq \nu\leq n\ .
\end{equation*} 
Note that $H_{n\ n}=h_{n}^{n}$; consequently:  
\begin{equation*} h_{n}^{n}+\sum_{\nu=0}^{n-2} x_{n-\nu}\dots x_{n} 
D_{n-1-\nu}\dots D_{n-1}\ h_{n}^{n}  =  H_{n\ n}  
+ \sum_{\nu=1}^{n-1} x_{\nu+1}\dots x_{n}\ H_{\nu\ n}\ .\end{equation*} 
We show next, 
that for all $k,\ 1\leq k\leq n$: \begin{equation*} 
x_{1}\dots x_{k-1} x_{k+1}\dots x_{n}\  
\eh_{k} = h_{n}^{k} + \sum_{\nu=1}^{n-1} x_{\nu+1}\dots x_{n}\ h_{\nu}^{k}  
\ . \end{equation*}  
Elimination of $\eh_{k}$ from $h_{\dots}^{k}$, application of $\Pi_{rs}=0$  
for $r\geq s$ and division by $x_{k+1}\dots x_{n}$ for $1\leq k\leq n-1$ 
yields the following equivalent formula, which is independent 
of $\lambda$ and $n$: \begin{equation*} x_{1}\dots x_{k-1} =  
\Pi_{k-1\ k}+ \sum_{\nu=1}^{k-1} x_{\nu+1}\dots x_{k}\ \Pi_{\nu-1\ k}\ \  
\text{ for $k\in \N$ }. \end{equation*} 
The r.h.s. of the last formula equals \begin{multline*} 
x_{2}\dots x_{k} +  [\  
(x_{2}-x_{k})\dots (x_{k-1}-x_{k}) + \sum_{\nu=2}^{k-1} x_{\nu+1}\dots x_{k}\  
(x_{2}-x_{k})\dots (x_{\nu-1}-x_{k})\ ]\  (x_{1}-x_{k}) \\
 = x_{2}\dots x_{k}+  
\epd\ [\ (x_{1}-x_{k-1})\dots (x_{k-2}-x_{k-1}) + \\ 
\sum_{\nu=1}^{k-2} x_{\nu+1}\dots x_{k-1}\ (x_{1}-x_{k-1})\dots  
(x_{\nu-1}-x_{k-1})\ ]\ (x_{1}-x_{k}).\end{multline*} By induction over $k$ 
this is : $x_{2}\dots x_{k}+\ \epd\ (x_{1}\dots x_{k-2})\ (x_{1}-x_{k})= $
\hfill\linebreak
$x_{2}\dots x_{k}+ x_{2}\dots x_{k-1} (x_{1}-x_{k})=  
x_{2}\dots x_{k-1}\ ( x_{k} + x_{1} - x_{k} )= x_{1}\dots x_{k-1}$. 
 
In summary we have, that the l.h.s. of (b) equals \begin{equation*} 
V_{n}^{-1}\  
\det ((\ x_{i}^{\lambda _{j}+n-1-j} \mid *\ ))_{\ i=1,\dots,n ; 
\ j=1,\dots,n-1}\ ,\end{equation*} 
where the last column is  
$*=(\ \prod_{l=1\ ; l\neq i}^{n} x_{l}\ )_{i=1,\dots,n}$ \ .  
Expansion with respect to the last column then yields : $V_{n}^{-1}\  
\det ((\ x_{i}^{\lambda _{j}+n-j}\ ))_{\ i,j=1,\dots,n } =  
\{\lambda\ 0 \}^{n}$\ .  \end{proof} 
 
The following corollary shows how the determinantal formula for Schur 
polynomials is interpolated for the Schubert polynomials `between' 
(w.r.t. the up case recursive structure) 
$l=L(\pi)=\ooo{0\dots 0\ \lambda _{p}\dots \lambda_{1}\ 0\dots 0}$,  
$l^{(1)}=\ooo{1\dots 1\ \lambda _{p}+1\dots \lambda_{1}+1\ 0\dots 0\ 0}$ and  
$l^{(2)}=\ooo{0\ 0\dots 0\ \lambda _{p}\dots \lambda_{1}\ 0\dots 0}$ \   
($\lambda =\lambda _{1} \dots \lambda _{m}$ as always in this 
section)\ . 
 
\begin{Cor} Using the above notations one has: 
$X_{\pi}=x_{m+1}\dots x_{m+q}\ \{ 1_{+} \lambda \}^{m}$ for  
$L(\pi)=\ooo{1\dots 1\ \lambda _{p}+1\dots \lambda_{1}+1\ 1\dots 1\ 0\dots 0}$ 
with $q$ one's on the right; 
  
let $l':=\ooo{1\dots 1\ \lambda _{p}+1\dots \lambda_{s+1}+1\ 0\  
\lambda _{s}\dots \lambda_{1}\ 0\dots 0}$, i.e. the first zero is on 
place $r=m+1-s=n-s,\ 1\leq r\leq m+1$, then \begin{equation*} 
X_{L^{-1}(l')}=V_{n}^{-1}\ \det ((\ x_{i}^{\lambda _{j}+n-1-j} \mid *\ )) 
_{\ i=1,\dots,n ; \ j=1,\dots,n-1}\ ,\end{equation*} 
where the last column $*$ is:  
$*=(\ \Pi_{r-1\ i}\ \prod_{l=1\ ; l\neq i}^{n} x_{l}\ )_{i=1,\dots,n}$ \ .  
 
Note that $l'=l^{(2)}$ for $r=1$ and $l'=l^{(1)}$ for $r=n$ \ . \end{Cor} 
\begin{proof} The first assertion is immediate from the preceding proof  
of (1). The second follows similarly from the proof of (2); we give 
here the main steps --- for $r=1$ this summarizes the proof of (S) --- : 
\begin{align*} X_{L^{-1}(l')} =&\  
X_{L^{-1}(\tau _{\lambda _{1}+s} \dots \tau _{\lambda _{1}+1}\ l^{(1)})}= 
\partial_{m-s+1}\dots\partial_{m}\ X_{L^{-1} (l^{(1)})} \\ =&\ 
\partial_{m-s+1}\dots\partial_{m}\ (\ (x_{1}\dots x_{m})\ \{ \lambda \}^{m}\ ) 
\\ =&\  ( x_{1}\dots x_{n-s-1} )\  
\{ \lambda \}^{n-1} + \sum_{\nu =0}^{s-1} x_{n-\nu}\dots x_{n} 
\partial_{n-1-\nu} \dots\partial_{n-1} \{ \lambda \}^{n-1} \\ =&\
( x_{1}\dots x_{n-s-1} )\ (\ H_{n\ n} +  
\sum_{\nu=n-s}^{n-1} x_{\nu+1}\dots x_{n}\ H_{\nu\ n}\ ) \end{align*}  
The $k^{th}$ component of this expression equals 
\begin{align*} &( x_{1}\dots x_{r-1} )\ (\ \Pi_{r+s-1\ k} + 
\sum_{\nu=r}^{r+s-1} x_{\nu+1}\dots x_{r+s}\ \Pi_{\nu-1\ k}\ )\ \eh_{k} \\ =
&\ ( x_{1}\dots x_{r-1} )\ ( x_{k+1}\dots x_{n} )\ (\ \Pi_{k-1\ k} + 
\sum_{\nu=r}^{k-1} x_{\nu+1}\dots x_{k}\ \Pi_{\nu-1\ k}\ )\ \eh_{k} \\ =
&\ ( x_{1}\dots x_{r-1} )\ ( x_{k+1}\dots x_{n} )\ (\ \Pi_{r-1\ k} \  
x_{r}\dots x_{k-1}\ )\ \eh_{k} =  
\Pi_{r-1\ k}\ \prod_{l=1\ ; l\neq k}^{n} x_{l} \end{align*}  \end{proof}  
 
\begin{Ex} Consider $l^{(1)}= \ooo{23000}$, $l'= \ooo{20200}$ 
and $l^{(2)}= \ooo{01200}$ : \\ 
\begin{center} $ 
X_{L^{-1}(l^{(1)})} = \frac{1}{V_{3}}  
\left|  \begin{array}{ccc}  
x_{1}^{3} & x_{1} & 0 \\ 
x_{2}^{3} & x_{2} & 0 \\ 
x_{3}^{3} & x_{3} & (x_{1}-x_{3}) (x_{2}-x_{3}) x_{1} x_{2}  
\end{array} \right|  = 
\frac{1}{V_{2}} \left|  \begin{array}{cc}  
x_{1}^{4} & x_{1}^{2} \\ x_{2}^{4} & x_{2}^{2}  
\end{array} \right|  = \{ 3\ 2 \}^{2}\ , 
$ \end{center}  \begin{center} $ 
X_{L^{-1}(l')} = \frac{1}{V_{3}} \left|  \begin{array}{ccc}  
x_{1}^{3} & x_{1} & 0 \\ 
x_{2}^{3} & x_{2} & (x_{1}-x_{2}) x_{1} x_{3} \\ 
x_{3}^{3} & x_{3} & (x_{1}-x_{3}) x_{1} x_{2}  
\end{array} \right| \ ,  \ \ {\rm and} 
$ \end{center}  \begin{center} $ 
X_{L^{-1}(l^{(2)})} = \frac{1}{V_{3}} \left|  \begin{array}{ccc}  
x_{1}^{3} & x_{1} & x_{2} x_{3} \\ 
x_{2}^{3} & x_{2} & x_{1} x_{3} \\ 
x_{3}^{3} & x_{3} & x_{1} x_{2}  
\end{array} \right| =   
\frac{1}{V_{3}} \left|  \begin{array}{ccc}  
x_{1}^{4} & x_{1}^{2} & 1 \\ 
x_{2}^{4} & x_{2}^{2} & 1 \\ 
x_{3}^{4} & x_{3}^{2} & 1  
\end{array} \right| = \{ 2\ 1 \}^{3} $   
\end{center}   \end{Ex}
\vspace{20pt}


\section{Multiplication formulas} 
 
In this last section the emphasis is on multiplication 
properties of Schubert polynomials culminating in the rule of 
Monk-Pieri ([Mo]) and their corollaries; one of these corollaries 
will enable the computation of Schubert polynomials without divided 
differences on the basis of some easily obtained information about
 Bruhat order. 
 
Following the line of reasoning indicated by I.G. Macdonald in [M1, M2], 
we begin with a formula for the expansion of an arbitrary polynomial 
in $\Z[x]$ into Schubert polynomials and a general product formula 
for the operators $\partial_{\pi} $. 
 
\begin{Prop} {\bf (Expansion Formula)}   
Let $\eta : \Z[x] \lra \Z,\ f\mapsto f(0)$ be the 
augmentation map on $\Z[x]$; then for all $f\in \Z[x]$ one has 
\begin{equation*} 
f= \sum_{\pi} \eta ( \partial_{\pi} f )\ X_{\pi}\ . \end{equation*}
\end{Prop}  
\begin{proof} Since the $X_{\pi}$ form a basis of $\Z[x]$ and $\eta 
,\ \partial_{\pi} $ are linear mappings, one has to investigate only 
the case $f=X_{\rho}$; but $\sum_{\pi} \eta  
( \partial_{\pi} X_{\rho} )\ X_{\pi} = X_{\rho}$, because  
$\eta ( \partial_{\pi} X_{\rho} ) = \delta _{\pi, \rho}$: by 
Prop.3.1 d) one has $\partial_{\pi} X_{\rho}= X_{\rho\ \pi^{-1}}$, 
if $l(\rho\ \pi^{-1})=l(\rho)-l(\pi)$, and by Prop.3.1 b) 
$\eta (X_{\pi})= \delta _{\pi, id}$.  \end{proof} 
 
\begin{Prop} {\bf (General Product Rule)} {\rm [M1,(2.5)]} \ Let 
$\pi$ be a permutation of length $p$ and $b$ a reduced subword of 
$a \equiv a_{1}\dots a_{p}\in R(\pi)$; let further $\varphi (a,b)$ denote the  
expression $\sigma_{a_{1}}\dots \sigma _{a_{p}}$, where  
$\sigma _{a_{\nu}}$ is replaced by $\partial_{a_{\nu}}$ for $\nu \in 
\{ 1,\dots, p \}$ iff $a_{\nu}$ is not contained in $b$. 
Then for all $\mu,\ \pi$ we define the {\em relative operators} 
\begin{equation*} 
\partial_{\pi / \mu} := \mu^{-1} \sum \varphi (a,b)\ , \end{equation*} 
where the sum is taken over all subwords $b$ of a fixed  
$a\in R(\pi)$ such that $b\in R(\mu)$. These operators are $\Z$-linear 
of degree $l(\mu)-l(\pi)\leq 0$, independent of the choice of $a$ 
and nonzero only for $\mu\leq_{B} \pi $ (Bruhat order). 
Now for all $f,g \in \Z[x]$ the general product rule reads: \begin{equation*} 
\partial_{\pi} ( f g )\ = \ \sum_{\mu \leq_{B} \pi}  
\mu ( \partial_{\pi / \mu} f ) \cdot \partial_{\mu} g \ .\end{equation*}
\end{Prop} 
\begin{proof} By the subword property (cf. Sec.1) the operators  
$\partial_{\pi / \mu} $ are nonzero	only for $\mu\leq_{B} \pi$ and 
independent of the choice of $a$; clearly they are  
$\Z$-linear of degree $l(\mu)-l(\pi)\leq 0$ too.  
 
We show the general product rule by induction over $p=l(\pi)$. For 
$\pi= id$ the assertion is trivial. Assume now that it is true for  
all $\pi$ of length $p$ and that $\pi'$ is some permutation of length 
$p+1$; then for fixed $a=a_{1}\dots a_{p}\ a_{p+1} \in R(\pi')$ let 
$k=a_{p+1}$ and $\pi$ be the permutation represented by $a_{1}\dots a_{p}$. 
Using Prop.3.1 c), the product rule and the linearity of $\partial_{\pi}$ 
one computes \begin{multline*} 
\partial_{\pi'} ( f g ) = \partial_{\pi}\ [\ \partial_{k} ( f g )\ ] = 
\partial_{\pi}\ [\ (\ \partial_{k} ( f )\ )\ g + \sigma _{k} ( f )\  
( \partial_{k} ( g )\ )\ ] \\ =
\sum_{\mu \leq_{B} \pi} \mu ( \partial_{\pi / \mu} \partial_{k} f ) 
                                    \cdot ( \partial_{\mu} g ) + 
\sum_{\mu \leq_{B} \pi} \mu ( \partial_{\pi / \mu} \sigma_{k} ( f ) ) 
               \cdot ( \partial_{\mu} \partial_{k} g ) \ ,\end{multline*} 
which should be equal to $ \sum_{\mu' \leq_{B} \pi'}  
\mu' (\partial_{\pi' / \mu'} f) \cdot \partial_{\mu'} g $. But using 
the subword property again we see that for $\mu \leq_{B} \pi$  
and $b\in R(\pi)$ two cases are to be distinguished: \\ 
$1^{st}$) $k=a_{p+1}$ not contained in $b$, then $\mu'=\mu$, \  
$\partial_{\pi' / \mu'}=\partial_{\pi / \mu} \partial_{k} $ gives the 
first summand, and \\ 
$2^{nd}$) $k=a_{p+1}$ contained in $b$, then $\mu'=\mu \sigma _{k}$, \  
$\partial_{\pi' / \mu'}=\sigma _{k}^{-1} \partial_{\pi / \mu} 
\sigma _{k}$ gives the second summand.  \end{proof} 
 
\begin{Cor}  Let $\pi\in S_{\infty}$, $f=\sum \alpha _{i} 
x_{i} \in \Z[x]$, $g \in \Z[x]$ and $J_{-1}(\pi)$ as in Def.2.2; then 
\begin{equation*} 
\partial_{\pi} ( f g ) = \pi ( f ) ( \partial_{\pi} g ) + 
\sum_{(i,j) \in J_{-1}(\pi)} ( \alpha _{i} - \alpha _{j} )\ 
\partial_{\pi \circ (i,j)} g  .\end{equation*} \end{Cor}
\begin{proof} The expressions $\partial_{\pi /\mu} f$ are nonzero 
only for $-1 \leq l(\mu) -l(\pi) \leq 0$, i.e. $\mu=\pi$ or `$\mu 
\preceq_{B} \pi$' ($\pi$ covers $\mu$ in Bruhat order) $\gdw \ \mu 
= \pi \circ (i,j) ,\ (i,j)\in J_{-1}(\pi)$ by Prop.2.3. Therefore 
either $\partial_{\pi\ /\pi}= \pi^{-1} \ \pi= id$ or , if 
$\mu \preceq_{B} \pi$, there exists $\nu\in \{1,\dots , p\}$ such that 
for $a=a_{1}\dots a_{p}\in R(\pi)$ one has $\partial_{\pi /\mu}= 
a_{p}\dots a_{1}\ a_{1}\dots a_{\nu-1}\ 
\partial_{a_{\nu}}\ a_{\nu+1}\dots a_{p} 
 = a_{p}\dots a_{\nu+1}\ \partial_{a_{\nu}}\ a_{\nu+1}\dots a_{p} 
\equiv \rho^{-1}\ \partial_{a_{\nu}}\ \rho$. Then it is easy to 
calculate that for $i:=\rho^{-1}(a_{\nu})$ and $j:=\rho^{-1}(a_{\nu}+1)$ 
one has $\rho^{-1}\ \partial_{a_{\nu}}\ \rho = (x_{i} - x_{j})^{-1} 
(id - (i,j))\equiv \partial_{i,j}$ (, i.e. $\partial_{i,i+1}=\partial_{i}$ ), 
which completes the proof.  \end{proof} 
 
\begin{Thm} {\rm [M1,(4.10)]} \ Let $\pi\in S_{\infty}$, 
$f=\sum \alpha _{i} x_{i} \in \Z[x]$ and $J_{1}(\pi)$ as in Def.2.2; 
then \begin{equation*} f X_{\pi} = \sum_{(i,j) \in J_{1}(\pi)} 
( \alpha _{i} - \alpha _{j} )\ X_{\pi \circ (i,j)}\ .\end{equation*}
\end{Thm} 
\begin{proof} $f\ X_{\pi} = \sum_{\rho} \eta  
( \partial_{\rho} ( f X_{\pi} ) ) X_{\rho}$ by Prop.6.1 and  
\begin{equation*} \partial_{\rho} ( f  X_{\pi} )=	 
\pi ( f ) ( \partial_{\rho} X_{\pi} ) + 
\sum_{(i,j) \in J_{-1}(\rho)} ( \alpha _{i} - \alpha _{j} )\ 
\partial_{\rho \circ (i,j)}\ X_{\pi}\ .\end{equation*} Since 
$\eta ( \pi ( f ) )=0$ 
for all choices of the $\alpha _{i}$ and  
$\eta ( \partial_{\rho \circ (i,j)}\ X_{\pi} ) =\delta _{\rho \circ 
(i,j) , \pi}$ by Prop.6.1 and its proof, we only need to observe that 
\begin{equation*} 
[ \rho \circ (i,j)=\pi \text{ and } (i,j) \in J_{-1}(\rho)] \ \ \gdw\ \  
[ \rho =\pi \circ (i,j) \text{ and } (i,j) \in J_{1}(\pi) ] \end{equation*} 
in order to finish the proof by the calculation:  \begin{equation*}
f X_{\pi} =  \sum_{\rho}\ \sum_{(i,j) \in J_{1}(\pi)} 
( \alpha _{i} - \alpha _{j} )\ \delta_{\rho ,  \pi \circ (i,j)}\ X_{\rho} 
=  \sum_{(i,j) \in J_{1}(\pi)} 
( \alpha _{i} - \alpha _{j} )\ X_{\pi \circ (i,j)}\ .\end{equation*}  
\end{proof} 
 
\begin{Cor}{\bf (Monk-Pieri)} ([Mo]) \  
Let $\pi \in S_{\infty}$, $k \in \N $ and  $J_{1}( k,\pi ):= $ \\
$ \{\ (i,j) \mid 1\leq i\leq k < j ,\ \pi i <\pi j, \  
\sharp \{ \nu | i<\nu<j ,\ \pi i<\pi \nu<\pi j \}=0\ \}$, then 
\begin{equation*} X_{\sigma _{k}}\ X_{\pi} = 
\sum_{(i,j) \in J_{1} (k,\pi)} X_{\pi\circ (i,j)} \ .\end{equation*} 
\end{Cor}
\begin{proof} By Prop.3.1 h) $f=X_{\sigma _{k}}$ means 
$\alpha_{1}=\dots \alpha _{k}= 1$, $\alpha_{k+1}=\alpha _{k+2}=\dots = 
0$, hence $\alpha _{i} - \alpha _{j} =1$, if $1\leq i\leq k < j$, and 
zero otherwise.  \end{proof} 
 
\begin{Cor} {\rm [KKL, (3.1) ]} \  
Let $\pi \in S_{\infty}$, $k \in \N $ and $J_{1}^{>k}(\pi ) ,\  
J_{1}^{<k}(\pi )$ as in Def.2.2; then \begin{equation*} x_{k}\ X_{\pi} =  
\sum_{j \in J_{1}^{>k} (\pi)} X_{\pi\circ (k,j)} - 
\sum_{j \in J_{1}^{<k} (\pi)} X_{\pi\circ (k,j)} \ .\end{equation*} 
\end{Cor}
\begin{proof} By Cor. 6.5 one has: \begin{equation*} x_{k}\ X_{\pi} = 
(X_{\sigma _{k}} -X_{\sigma_{k-1}})\ X_{\pi} =  
\sum_{(r,s) \in J_{1} (k,\pi)} X_{\pi\circ (r,s)} - 
\sum_{(r,s) \in J_{1} (k-1,\pi)} X_{\pi\circ (r,s)} \ . \end{equation*} 
The terms with  
$1\leq r\leq k-1 $ and $k<s$ in the two sums cancel; in the first sum 
only terms with $r=k$ or $s \in J_{1}^{>k} (\pi)$ survive, in the 
second sum only terms with $s=k$ or $r \in J_{1}^{<k} (\pi)$, proving 
the assertion.  \end{proof} 
 
\begin{Rem}  (cf. [KKL])  Cor.6.6 has been the starting point for the 
``transition formula" of Lascaux and Sch\"{u}tzenberger (1985), which 
allows to expand the symmetric part of a Schubert polynomial (cf. 
Prop.3.1 f) ) into a sum of Schur polynomials. Using this algorithm 
it is possible to compute the Littlewood-Richardson coefficients, 
i.e. the structure constants for the algebra of Schur polynomials. \end{Rem}
 
\begin{Cor}  \begin{equation*} 
{\rm a)\ \ } \ X_{\pi} = \frac{1}{x_{k}}\  
( \sum_{j \in J_{1}^{>k} (\pi)} X_{\pi\circ (k,j)}\ )\ \text{, if  
$J_{1}^{<k}(\pi)=\emptyset$} .\end{equation*}   b) Let $\pi\in S_{n}$ and 
$\pi k =2,\ \pi (k+1)=1$ for some $k$ with $1\leq k \leq n-1$, 
then $\partial_{k} X_{\pi}= X_{\pi } / x_{k}$. \end{Cor} 
\begin{proof} a) is immediate from Cor.6.6 . For b) observe that under the 
assumptions made one has $J_{1}^{<k}(\pi \sigma _{k})=\emptyset$ and 
$J_{1}^{>k}(\pi \sigma _{k})=\{k+1\}$. This together with  Prop.3.1 e) gives 
\begin{equation*} \partial_{k}\ X_{\pi} = X_{\pi \sigma _{k} } =  
\frac{1}{x_{k}}\ X_{\pi\sigma_{k}\sigma_{k} } =
\frac{1}{x_{k}}\ X_{\pi }.\end{equation*}   
\end{proof}
 
Of course it may happen that there is more than one $k$ for given $\pi$, 
such that $J_{1}^{<k}(\pi)=\emptyset$ for \\{\bf Example}: 
let $\pi=2143\in S_{4}$, then $X_{\pi} = x_{1}^{2}+ x_{1} x_{2}+x_{1} x_{3}$, 
and for $k=1$ one has $X_{\pi} = x_{1}^{-1} ( X_{4123} + X_{3142})= 
x_{1}^{-1} (\ x_{1}^{3}+(x_{1}^{2} x_{3}+x_{1}^{2} x_{2})\ )$ or for $k=2$ :  
$X_{\pi} = x_{2}^{-1} ( X_{2341} + X_{2413})= x_{2}^{-1}  
(\ x_{1} x_{2} x_{3} + (x_{1} x_{2}^{2} + x_{1}^{2} x_{2})\ )$ .\\ \\
 
On the other hand for all $\pi \neq \omega _{n}$ there exists at least one  
$k$ with $J_{1}^{<k}(\pi)=\emptyset$, namely 
\begin{equation*}\text{ {\em $k=$ the first ascend of $\pi$}, 
i.e. $\pi 1 > \dots > \pi k < \pi (k+1) < \dots$ }\ . \end{equation*} 
This gives us the possibility to compute the Schubert polynomial $X_{\pi}$ 
for every $\pi \in S_{n}$ recursively from   
$X_{\omega_{n}}=x_{1}^{n-1} \dots x_{n}^{0}$ 
without using divided differences. 
(Clearly it is convenient to choose for given $\pi$ the smallest possible $n$,
i.e. the greatest $n$, such that $\pi n \neq n$).  
 
The advantage of avoiding divided 
differences is, that the determination of the set $J_{1}^{<k}(\pi)$ for  
the first ascend $k$ in $\pi$ seems slightly easier than handling the  
formula for the $\partial_{k} $, and --- more importantly --- that 
the use of an operator $\partial_{\pi} $, although in its optimal realization 
(cf. Rem.4.3), usually involves the computation of terms, which 
cancel subsequently; to the contrary in our method only terms, which  
contribute to the final result, are generated. 
 
The method seems to be especially effective for the computation of a  
whole set $\scal_{n}$; in this case one begins with $X_{\omega _{n}}$ 
and works down through all levels of the weak order of $S_{n}$: 
suppose the sets $S_{n}^{p}:=\{\pi\in S_{n} \mid l(\pi)=p\}$ and  
$\scal_{n}^{p}:=\{X_{\pi}\in \scal_{n} \mid \pi\in S_{n}^{p}\}$ for some $p$ 
with $1\leq p \leq n$ are already know, then one finds $S_{n}^{p-1}= 
\{\pi\sigma_{k} \mid \pi\in S_{n}^{p}, \pi k> \pi (k+1) \}$ and every 
Schubert polynomial in the set $\scal_{n}^{p-1}$ can be computed 
according to Cor.6.8 a).  
 
In the case of a computation of a single Schubert polynomial $X_{\pi}\ 
(\pi\in S_{n})$ one should build up an `ad hoc set' of already known Schubert 
polynomials initialized as $\{X_{\omega _{n}}\}$, which is checked in 
every step of a `depth first' recursion: if it contains the necessary 
intermediary result, this branch of the recursion terminates, otherwise 
continues. 
\vspace{20pt}

%\vfill\pagebreak
\begin{thebibliography}{99}
\bibitem[Hi]{Hi} {\sc H. Hiller}, ``Geometry of Coxeter groups'', Pitman, 
Boston, 1982.   
\bibitem[Hu]{Hu} {\sc J.E. Humphreys}, ``Reflection groups and Coxeter 
groups'',  Cambridge University Press, Cambridge, 1990.  
{\bf [K]} {\sc A. Kerber}, ``Algebraic combinatorics via finite group 
actions", BI Wissenschaftsverlag, Mannheim 1991.
\bibitem[KKL]{KKL} {\sc A. Kerber, A. Kohnert, A. Lascoux}, 
{\sc SYMMETRICA}, an 
object oriented computer-algebra system for the symmetric group,  
{\it J. Symbolic Computation} {\bf 14} (1992), 195-203. 
\bibitem[Kr]{Kr} {\sc V. Krishnamurthy}, ``Combinatorics: Theory and 
Applications'', Ellis Horwood, Chichester 1986.
\bibitem[LS]{LS} {\sc A. Lascoux, M.-P. Sch\"{u}tzenberger}, 
D\'{e}compositions dans l'alg\'{e}bre des diff\'{e}rences divis\'{e}es, 
{\it discrete math.} {\bf 99} (1992), 165-179.
\bibitem[M1]{M1} {\sf I.G. Macdonald}, Schubert polynomials, {\it in}: 
{\sf A.D. Kendwell (ed.)}, ``Surveys in Combinatorics", London Math. 
Soc. Lec. Notes Ser. {\bf 166}, 73 - 99, Cambridge University Press, Cambridge 
1991. 
\bibitem[M2]{M2} {\sf I.G. Macdonald}, ``Notes on Schubert 
polynomials", Publications du L.A.C.I.M., vol. 6, Universit\'{e} du  
Qu\'{e}bec, Montr\'{e}al, 1991.
\bibitem[M3]{M3} {\sf I.G. Macdonald}, ``Symmetric functions and Hall 
polynomials", Clarendon Press, Oxford 1979.
\bibitem[Mo]{Mo} {\sc D. Monk}, The geometry of flag manifolds, 
{\it Proc. London Math. Soc. (3)} {\bf 9} (1959), 253-286. 
\bibitem[Sb]{Sb} {\sc H. Schubert}, 
``Kalk\"{u}l der Abz\"{a}hlenden Geometrie" 
(Reprint), Springer, Berlin, 1979.
\bibitem[W]{W} {\sc R. Winkel}, Diagram rules for the 
generation of Schubert polynomials, preprint (1995/97).
\end{thebibliography}			
\end{document} 
