%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 \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 \pi j \} = \sharp (\bigcup_{i=1}^{n} \{ (i,j) | i \pi j \}) = \sharp \{ (i,j) | i \pi j \} = \sharp I(\pi )$\ ; c) from the definition; d) $I(\omega _{n}\pi ) = \{ (i,j) | i \omega _{n}\pi j \} = \{ (i,j) | ik} (\pi):=\{\ j \mid k \pi k, \sharp \{ \nu | j< \nu < k,\pi j >\pi\nu >\pi k \}=|m|-1 \}$ $J_{m}^{>k} (\pi):=\{\ j \mid 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)$ for $m\in \Z\setminus \{ 0 \}$. Moreover for $m\in \N$ we define $J_{m}(\pi):=\{\ (i,j) \mid 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 \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\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\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'}\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 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 $d0 ,\ 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):}& \ :\ \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 $$ discussed above --- note that each $$ 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 ii+1 {\rm\ and\ } j\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<\nuk}(\pi ) ,\ J_{1}^{k} (\pi)} X_{\pi\circ (k,j)} - \sum_{j \in J_{1}^{k} (\pi)$ survive, in the second sum only terms with $s=k$ or $r \in J_{1}^{k} (\pi)} X_{\pi\circ (k,j)}\ )\ \text{, if $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}^{ \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}^{ \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}