RECURSIVE AND COMBINATORIAL PROPERTIES OF SCHUBERT POLYNOMIALS

RUDOLF WINKEL

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.

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ü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 ∈ ℕ let S_{n} ≡ S_{{1,...,n}} denote the group of permutations of the ‘letters’ 1, …, n and S_{∞} := ⋃_{n>0} S_{n} the set of all finite permutations, where the union of the S_{n}’s uses for m ≥ n the identification of S_{n} with the stabilizer of n + 1, …, m in S_{m}. The set of all Schubert polynomials S_{∞} := {X_{π}|π ∈ S_{∞}} (well defined by Prop.3.1 i) ) then forms a basis of the polynomial ring ℤ[x] := ℤ[x_{1}, x_{2}, …].

Much of the importance of Schubert polynomials is due to the fact that they contain as a subset the set of all Schur polynomials {{λ}^{s}|λ ⊢ n, n ∈ ℕ} in s variables, where ‘λ ⊢ n’ means that λ = (λ_{1}, …, λ_{s}) is a partition of n, i.e. λ_{1} ≥ ⋯ ≥ λ_{s} ≥ 0 and |λ| = λ_{1} + ⋯ + λ_{s} = n . The Schur polynomials in n variables form the basis for the rings ℤ[x]^{S_{n}} := ℤ[x_{1}, …, 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 ℤ[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]).

Date: March 1995, revised November 1996.

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 S_{∞} described here provides as a new tool ‘long induction’, i.e. induction over all permutations π ∈ S_{∞}, 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 S_{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 S_{n}.

1. Basic material and the definition of Schubert polynomials

Let ℕ_{0}^{∗} [and ℤ^{∗}] denote the set of all finite nonempty words in the “alphabet” ℕ_{0} = {0, 1, 2, … } [and ℤ] ; then the usual linear order on ℕ_{0} induces a lexicographic order ‘≤’ on ℕ_{0}^{∗}. For all n ∈ ℕ we define the word E_{n} := n − 1 … 1 0 ∈ ℕ_{0}^{∗} and the subsets of words D_{n} := {d = d_{1} … d_{n})|0 ≤ d_{ν} ≤ n − ν, ν = 1, …, n}; clearly d ≤ E_{n} for all d ∈ D_{n}. Moreover let ℤ_{E_{n}}[x] denote the ℤ-submodule of ℤ[x] generated finitely free by the set of monomials {x^{d} := ∏_{v=1}^{n} x_{ν}^{d_{ν}} | d ∈ D_{n}}. The rank of ℤ_{E_{n}}[x] is n! and ℤ[x] = ⋃_{n∈ℕ} ℤ_{E_{n}}[x], where for all m, n ∈ ℕ, m > n the inclusion of sets D_{n} ↪ D_{m} , d ↦ d 0 … 0 extends to an embedding of ℤ_{E_{n}}[x] into ℤ_{E_{m}}[x].

To every permutation π ∈ S_{n} one can associate its Lehmer code L(π) ≡ \overline{l_{n−1} … l_{1} l_{0}} with l_{n−i}(π) := ♯{j|j > i, πj < πi} = ♯{ all letters to the right of place i less than πi} for i = 1, …, n, e.g. L(35142) = \overline{23010} or 35142 ≈ \overline{23010}. This sets up a bijection L between S_{n} and 𝕃_{n} := \{l := \overline{l_{n−1} … l_{1} l_{0}} | 0 ≤ l_{ν} ≤ ν, ν = 0, …, n − 1\}, as we will see in Section 2 below. We will often use the notation k_{+}(k_{1} … k_{s}) := k_{1} + k … k_{s} + k for k ∈ ℤ and words k_{1} … k_{s} ∈ ℤ^{∗}; a first instance of this is the following: the embeddings of S_{n} into S_{m} given by π ↦ π1 … πn n+1 … m and π ↦ 1 … m−n (m−n)_{+}(π1 … πn) induce the inclusions of 𝕃_{n} into 𝕃_{m} given by l ↦ l \overline{0 … 0} and l ↦ \overline{0 … 0} l, which we call, respectively, (left) embedding and right embedding; for example π = 34152 ∈ S_{5} with L(π) = \overline{22010} is (left) embedded into S_{8} as 34152678 with Lehmer code \overline{22010000} and right embedded into S_{8} as 12367485 with Lehmer code \overline{00022010}.

A mere re-indexing of components (d_{ν} ↔ l_{n−ν}) now gives a bijection between 𝕃_{n} and D_{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 ℤ[x] = ⋃_{n>0} ℤ_{E_{m}}[x], the set D_{∞} := ⋃_{n>0} D_{n} = ℕ_{0}^{∗} of all finite sequences of nonnegative integers, the set 𝕃_{∞} := ⋃_{n>0} 𝕃_{n} of all Lehmer codes and the group S_{∞} := ⋃_{n>0} S_{n} of all finite permutations of ℕ.

Let { P_{π} | π ∈ S_{n} } (n ∈ ℕ) be any subset of polynomials from ℤ_{E_{n}}[x] indexed by the permutations π ∈ S_{n} and for p ∈ ℤ[x] let lmin(p) denote the monomial of p with the lexicographically smallest exponent; then the property

(B): lmin(P_{π}) = x^{L(π)} with coefficient 1 for all polynomials in { P_{π} | π ∈ S_{n} }

is called the basis property, since (B) implies that { P_{π} | π ∈ S_{n} } is a basis for the ℤ-module ℤ_{E_{n}}[x] : take any polynomial p ∈ ℤ_{E_{n}}[x], then by (B) there exists a π ∈ S_{n} such that p = αx^{L(π)} +… with x^{L(π)} = lmin(p); therefore p = αP_{π} +p′ and p′ ∈ ℤ_{E_{n}}[x] with lmin(p′) > lmin(p) proving the assertion by induction. In Section 5 we will show that the set S_{n} of Schubert polynomials indexed by the π ∈ S_{n} has the basis property (B).

The symmetric groups S_{n} are special Coxeter groups (cf. [Hi,Hu]) generated by the elementary transpositions σ_{i} := (i, i + 1) ( i = 1, …, n − 1 ) with relations: (i) σ_{i}^{2} = id, (ii) σ_{i}σ_{j} = σ_{j}σ_{i}, if |i − j| > 1, and (iii) σ_{i}σ_{i+1}σ_{i} = σ_{i+1}σ_{i}σ_{i+1}. Clearly, for every π ∈ S_{n} there exists a minimal number l(π) ∈ ℕ_{0} called the length of π, such that π is the product of l(π) elementary transpositions: π = σ_{i_{1}} … σ_{i_{l(π)}}. The set R(π) of all such minimal expressions for π is called the set of reduced words. (When dealing with reduced words, we almost always omit the σ’s and write simply the indices i_{1} … i_{l(π)}.) In Lemma 2.1 below we show that l(π) = |L(π)| := ∑_{ν=0}^{n−1} l_{ν}(π), because both numbers are equal to the number of inversions in π.

The weak Bruhat order, denoted by ‘≤_{w}’, on the S_{n}’s is defined as the transitive closure of the following covering relation: let π, μ ∈ S_{n}, then ‘π is covered by μ’, ( in signs: π ≤_{w} · μ ) :⇔ μ = πσ_{k} for some k ∈ {1, …, n − 1} and l(μ) = l(π) + 1. If we replace the elementary transpositions σ_{k} in this definition by arbitrary transpositions (i, j) (1 ≤ i < j ≤ n) in S_{n}, then the resulting richer order is called Bruhat order, ‘≤_{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.

Exchange Condition ( [Hi, Thm.I.3.7], [Hu, Sec.1.7], [K, 1.3.29] ) Let π ∈ S_{∞}, p = l(π) and i_{1} … i_{p}, j_{1} … j_{p} ∈ R(π), then there is a unique k ∈ {1, …, n}, such that j_{1} i_{1} … i_{k−1} i_{k+1} … i_{p} ∈ R(π).

Subword Property ( [Hi, Cor.I.6.5-6], [Hu, Thm.5.10] ) Let π ∈ S_{∞}, p = l(π) and π = σ_{i_{1}} … σ_{i_{p}} an arbitrary reduced decomposition; then π′ ≤_{B} π iff π′ = σ_{j_{1}} … σ_{j_{p′}} for some subword j_{1} … j_{p′} of i_{1} … i_{p}.

There is a natural action of S_{∞} on ℤ[x] given by π(f) ≡ π(f(x)) := f(x_{π1}, x_{π2}, …). Using this action the divided difference operators ∂_{i} are for all f ∈ ℤ[x] and i ∈ ℕ defined by

∂_{i}f = \frac{f − σ_{i}(f)}{x_{i} − x_{i+1}} .

We list some easily verifiable properties of the ∂_{i} : they obey the same relations as the σ_{i} except that (i) now reads ∂_{i}^{2} = 0; ∂_{i}f is symmetric in x_{i} and x_{i+1}; ∂_{i}f ≡ 0, if f is already symmetric in x_{i} and x_{i+1}; if f is homogeneous of degree m, then ∂_{i}f is homogeneous of degree m-1 or ∂_{i}f ≡ 0; the product rule is given by

∂_{i}(fg) = (∂_{i}f)g + (σ_{i}(f))(∂_{i}g) for f, g ∈ ℤ[x] ;

the quotient rule by

∂_{i} \frac{f}{g} = \frac{(∂_{i}f)(σ_{i}(g)) − (σ_{i}(f))(∂_{i}g)}{g σ_{i}(g)} for f, g ∈ ℤ[x] ;

∂_{i} is ℤ-linear, but the product rule also implies linearity of ∂_{i} with respect to the multiplication by functions symmetric in x_{i} and x_{i+1}; therefore one has to calculate ∂_{i} only for monomials x_{i}^{d_{i}}x_{i+1}^{d_{i+1}} with min{d_{i}, d_{i+1}} = 0 :

∂_{i}(x_{i}^{k+1}x_{i+1}^{0}) = ∑_{ν=0}^{k} x_{i}^{k−ν}x_{i+1}^{ν} for k ∈ ℕ_{0} ,

and interchanging the role of x_{i} and x_{i+1} in the preceding formula does only change the sign of the sum, because ∂_{i}(f ∘ σ_{i}) = −∂_{i}f; thus divided differences are just a convenient way to describe a symmetrisation process: more specifically we will speak of i-symmetrisation in the case of application of ∂_{i}.

Calculation in ℤ[x] can be done conveniently using only the exponent tuples: let ℤD_{∞} be the ℤ-module freely generated on the set D_{∞}; then a distributive multiplication on ℤD_{∞} can be defined as the ℤ-linear extension of the ‘product’ of two elements of D_{∞}, which is simply componentwise addition. Clearly ℤ[x] and ℤD_{∞} are isomorphic as rings, and we denote the operator of i-symmetrisation on ℤD_{∞} by ∂_{i} as well.

Example 1.1. ∂_{1} (x_{1}^{3}x_{2}^{2}x_{3}^{1}) = x_{1}^{2}x_{2}^{2}x_{3}^{1} in ℤ[x] transfers to ∂_{1}(321) = 221 in ℤD_{∞}. And ∂_{2} (2 · 1302 + 0121 + 1332) = 2 · (1202 + 1112 + 1022) − 0111 + 0.

Proposition 1.2. Let π ∈ S_{∞}, then by a chain of transformations according to the relations (ii) and (iii)

a) every word ∈ R(π) can be transformed into every other word ∈ R(π) and

b) every non-reduced word representing π into a word of the form … σ_{i}σ_{i} … for some i.

Proof. of a): Let π ∈ S_{∞}, p = l(π) and i_{1} … i_{p}, j_{1} … j_{p} ∈ R(π). We proceed by induction over p. If p = 0 or p = 1 the assertion is trivial, so let p ≥ 2. If i_{1} = j_{1}, we are done by induction hypothesis, hence assume i_{1} ≠ j_{1} and in addition |i_{1} − j_{1}| > 1. The Exchange Theorem then shows that j_{1} i_{1} … i_{k−1} i_{k+1} … i_{p} ∈ R(π) for a uniquely determined k ∈ {1, …, n}, which by relation (ii) can be transformed into i_{1} j_{1} … i_{k−1} i_{k+1} … i_{p} ∈ R(π). On the other hand every word i_{1} … or j_{1} ⋯ ∈ R(π) can be transformed to i_{1} j_{1} … i_{k−1} i_{k+1} … i_{p} or j_{1} i_{1} … i_{k−1} i_{k+1} … i_{p} as seen already.

It remains to investigate the case i_{1} ≠ j_{1} and |i_{1} − j_{1}| = 1. Apply the Exchange Theorem to j_{1} i_{1} … i_{k−1} i_{k+1} … i_{p} and i_{1} … i_{p} ∈ R(π); there are essentially three different possibilities to cancel a number from i_{1}j_{1}i_{1} … i_{k−1} i_{k+1} … 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 π, and so it only remains to 3^{rd}) cancel one of the numbers i_{2}, …, i_{k−1}, i_{k+1}, …, i_{p}. Hence we get a word i_{1} j_{1} i_{1} ⋯ ∈ R(π), which by relation (iii) can be transformed to j_{1} i_{1} j_{1} ⋯ ∈ R(π). 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 non-reduced words i_{1} … i_{p} representing some π ∈ S_{∞}. Clearly for p ∈ {0, 1} there are no nonreduced expressions and for p = 2 the only possibility is i_{1} i_{2} ≡ i_{1} i_{1}; assume therefore that p ≥ 3 and the subword i_{2} … i_{p} of i_{1} … i_{p} is ∈ R(μ) for some μ; otherwise we are done by induction hypothesis. Since i_{1} … i_{p} is a non-reduced representation of π, we must have l(π) ≤ l(μ); on the other hand multiplication by an elementary transposition changes the length exactly by ±1 (cf. Lemma 2.1 i) ), hence l(π) = l(μ) − 1, which can only be achieved, if i_{1} … i_{p} can also be represented by i_{1} i_{1} . . ..

It is now possible to define ∂_{π} := ∂_{i_{1}} … ∂_{i_{l(π)}} using any reduced word i_{1} … i_{l(π)} for π, because the result is independent of the special reduced sequence chosen: simply use case a) of the above Prop. and observe that the ∂_{i} obey the same relations (ii) and (iii) as the σ_{i}. Similarly one gets ∂_{i_{1}} … ∂_{i_{p}} = 0 for every non-reduced sequence i_{1} … i_{p} from Prop. 1.2 b) and ∂_{i}^{2} = 0. (When looking to [K,KKL], be aware that the ‘∂_{π}’ there is the same as ∂_{π^{−1}} in the notation of [M1, M2] and the present paper.)

Permutations of special importance are the ω_{n} := n … 1 = L^{−1}(E_{n}) = (1, n)(2, n − 1) ⋯ = ω_{n}^{−1} of maximal length l(ω_{n}) = n(n − 1)/2 in S_{n}, which correspond to the greatest elements E_{n} of the D_{n}.

We can now define the Schubert polynomial X_{π} for every π ∈ S_{n} by

X_{π} := ∂_{π^{−1}ω_{n}}x^{E_{n}} .

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. (M) π dominant :⇔ L(π) weakly decreasing (= non-increasing) ⇒ X_{π} = x^{L(π)}, i.e. X_{π}

is a monomial. (M for ‘monomial’.) (S) π Grassmannian :⇔ π has a unique descent at place j, i.e. πj > π(j + 1),

⇔ L(π)^{+} :=‘L(π) without end zeros’ is weakly increasing (= non-decreasing) and has exactly j components; then X_{π} equals the Schur polynomial {λ}^{j} in the variables x_{1}, …, x_{j} with λ given by L(π) without end zeros and read backwards. (S for ‘Schur’.)

(P) Every X_{π} is a polynomial with non-negative integer coefficients. (P for ‘positive’.)

2. Permutations and Lehmer codes

For n ∈ ℕ, π ∈ S_{n} we define: I_{n} := {(i, j) ∈ {1, …, n}^{2}|i < j}, the set of inversions of π: I(π) := {(i, j) ∈ {1, …, n}^{2}|i < j, πi > πj}, the involution ι on 𝕃_{n} by l_{k} ↦ k − l_{k} and the involution ω_{n} on {1, …, n} by k ↦ n + 1 − k. The latter induces involutions on S_{n} by right multiplication π ↦ πω_{n} (involution of places), by left multiplication π ↦ ω_{n}π (involution of letters) and on I_{n} by (i, j) ↦ ω_{n}^{(2)}(i, j) := (ω_{n}j, ω_{n}i). We collect some basic facts in

Lemma 2.1. With the notations above and π written as the list π1 … πn one has: a) πω_{n} = (π read backwards );

b) |L(π)| = ♯I(π) ≡ l(π) ;

c) I(ω_{n}) = I_{n}, |L(ω_{n})| = n(n − 1)/2 ;

d) I(ω_{n}π) = I_{n} \ I(π), I(πω_{n}) = ω_{n}^{(2)}I(ω_{n}π) ;

e) |L(ω_{n}π)| = n(n − 1)/2 − |L(π)| = |L(πω_{n})| ;

f) L(ω_{n}π) = ιL(π) ;

g) |L(π)| = |L(π^{−1})| ;

h) l(ππ′) ≤ l(π) + l(π′), equality holds iff ππ′ is reduced;

i) let k ∈ ℕ and π sufficiently high embedded, if necessary; then

l(πσ_{k}) = \{ \begin{matrix}l(π) + 1 & , if πk < π(k + 1) \\ l(π) − 1 & , if πk > π(k + 1) \end{matrix} .

Proof. a) trivial;

b) |L(π)| = ∑_{i=1}^{n} l_{n−i}(π) = ∑_{i=1}^{n} ♯{j|i < j, πi > πj} = ♯(⋃_{i=1}^{n}{(i, j)|i < j, πi > πj}) = ♯{(i, j)|i < j, πi > πj} = ♯I(π) ;

c) from the definition;

d) I(ω_{n}π) = {(i, j)|i < j, ω_{n}πi > ω_{n}πj} = {(i, j)|i < j, πi < πj} = I_{n} \ I(π), ω_{n}^{(2)}(I_{n} \ I(π)) = {(ω_{n}j, ω_{n}i)|i < j, πi < πj} = {(i, j)|ω_{n}j < ω_{n}i, πω_{n}j < πω_{n}i} = {(i, j)|i < j, πω_{n}j < πω_{n}i} = I(πω_{n}) ;

e) from d);

f) from the proof of b) one sees l_{n−k}(π) = ♯{(i, j) ∈ I(π) | i = k}, hence l_{n−k}(ω_{n}π) = ♯{(i, j) ∈ I(ω_{n}) \ I(π)|i = k} = k − l_{n−k}(π) ;

g) let π = σ_{i_{1}} … σ_{i_{l(π)}}, then π^{−1} = σ_{i_{l(π)}}^{−1} … σ_{i_{1}}^{−1} and l(π) ≥ l(π^{−1}); now interchange the role of π and π^{−1} ;

h) immediate from using reduced words for π and π′;

i) immediate from b) and the definition of Lehmer codes.

Definition 2.2. Let k ∈ ℕ and π ∈ S_{∞}, i.e. there exists an n ∈ ℕ, such that πn ≠ n and π = π1 … πn n + 1 n + 2 …. Then for every m ∈ ℕ we define the sets:

J_{m}^{<k}(π) := { j | 1 ≤ j < k, πj < πk, ♯{ν|j < ν < k, πj < πν < πk} = m − 1} J_{m}^{>k}(π) := { j | k < j, πk < πj, ♯{ν|k < ν < j, πk < πν < πj} = m − 1}

and similarly for m ∈ −ℕ :

J_{m}^{<k}(π) := { j | 1 ≤ j < k, πj > πk, ♯{ν|j < ν < k, πj > πν > πk} = |m| − 1} J_{m}^{>k}(π) := { j | k < j, πk > πj, ♯{ν|k < ν < j, πk > πν > πj} = |m| − 1}.

Set J_{m}^{k}(π) := J_{m}^{<k}(π) ∪ J_{m}^{>k}(π) for m ∈ ℤ \ {0}. Moreover for m ∈ ℕ we define

J_{m}(π) := { (i, j) | i < j, πi < πj, ♯{ν|i < ν < j, πi < πν < πj} = m − 1} and similarly for m ∈ −ℕ :

J_{m}(π) := { (i, j) | i < j, πi > πj, ♯{ν|i < ν < j, πi > πν > πj} = |m| − 1}.

Note that it is especially easy to determine the above sets for m = 1, e.g. for π = 413276958 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), (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, π and m ∈ ℕ J_{m}^{>k}(π) is never empty.

Proposition 2.3. Using the notations of Definition 2.2 one has: j ∈ J_{m}^{k}(π) ⇔ l(π ∘ (j, k)) = l(π) ± (2m + 1) and (i, j) ∈ J_{m}(π) ⇔ l(π ∘ (i, j)) = l(π) ± (2m + 1), where one uses the + sign, if m > 0, and the − sign, if m < 0.

Proof. Let r < ν < s and assume that πr < πs, then (r, s) = σ_{s−1} ∘ ⋯ ∘ σ_{r} ∘ ⋯ ∘ σ_{s−1} implies that in order to get π ∘ (r, s) one has first to commute πs to place r and than πr (on place r+1) to place s. If πν > πs or πν < πr, then by Lemma 2.1 i) it contributes the length 1 + (−1) = 0, but if πr < πν < πs it contributes the length 1 + 1 = 2. The cases πr < πs and m < 0 are similar and the second assertion follows from J_{m}(π) = ⋃_{k} J_{m}^{k}(π).

The Lehmer code L(π) of a permutation π ∈ S_{n} has a close relationship to the inversions of π as Lemma 2.1 and the definition l_{n−i} = ♯{ all letters to the right of place i less than πi\} shows. There are alternative codes Y (π) ≡ \overline{y_{n−1} … y_{0}}, where (Y, y) ∈ {(G, g), (H, h), (K, k)}; they are defined as follows (we list L again for ease of comparison) :

L(π) : l_{n−i} := ♯{ j | j > i, πj < πi }
H(π) : h_{n−i} := ♯{ j | j < π^{−1}i, πj > i }
K(π) : k_{i−1} := ♯{ j | j < i, πj > πi }
G(π) : g_{i−1} := ♯{ j | j > π^{−1}i, πj < i }

Proposition 2.4. For π ∈ S_{n} and L, H, K, G as above one has: |L(π)| = |H(π)| = |K(π)| = |G(π)| = ♯I(π) and H(π) = L(π^{−1}), K(π) = L(ω_{n}πω_{n}), G(π) = L(ω_{n}π^{−1}ω_{n}).

Proof. l_{n−i}(π^{−1}) = ♯{j | i < j, π^{−1}i > π^{−1}j} = ♯{πk | i < πk, π^{−1}i > k} = ♯{k | k < π^{−1}i, πk > i} = h_{n−i}; then |L(π)| = |H(π)| follows from Lemma 2.1 b,g). The proofs for K and G are similar; two applications of Lemma 2.1 e) give ♯I(ω_{n}πω_{n}) = ♯I(π).

Example 2.5. Let π = 3417625 ∈ S_{7}; then L(π) = \overline{2203200}, π^{−1} = 3612754 ≈ \overline{2400210} = H(π), ω_{7}πω_{7} = 3621745 ≈ \overline{2410200} = K(π), and ω_{7}π^{−1}ω_{7} = 4316725 ≈ \overline{3202200} = G(π).

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_{∞} and arbitrary finite sequences of nonnegative numbers D_{∞} modulo embedding as discussed in Section 1. But most important for this paper:

The set of all Lehmer codes 𝕃_{∞} has a natural recursive structure, which translates into recursions for permutations and Schubert polynomials.

For a permutation π ∈ S_{n} one computes its Lehmer code by the definition l_{n−i}(π) = ♯{j|j > i, πj < πi}. Clearly the procedure can be reversed: π1 is the (l_{n−1} + 1)-th element of {1, …, n} in the natural order, π2 is the (l_{n−2} +1)-th element of {1, …, n}\ {π1} etc. . Notice that necessarily π is build up from left to right.

Now the recursive structure on 𝕃_{∞} is given by extension to the left or more exactly: for n ∈ ℕ_{0} and 0 ≤ k ≤ n the mapping ε_{nk} : 𝕃_{n} ⟶ 𝕃_{n+1} defined by l ↦ \overline{k}l is an embedding and the set of images {ε_{n0}𝕃_{n}, …, ε_{nn}𝕃_{n}} is a partition of 𝕃_{n+1} into parts of equal cardinality. (For n = 0 set 𝕃_{0} := ∅ and ε_{00}(∅) = \{\overline{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 ∈ ℕ_{0} and 0 ≤ k ≤ n the mapping ε′_{nk} : S_{n} ⟶ S_{n+1} defined by ε′_{nk} = L^{−1} ∘ ε_{nk} ∘ L or π ↦ π_{k} with

π_{k} := L^{−1}(\overline{k}L(π))

is an embedding and the set of images {ε′_{n0}S_{n}, …, ε′_{nn}S_{n}} is a partition of S_{n+1} in parts of equal cardinality. ( For n = 0 set S_{0} := ∅ and ε′_{00}(∅) = {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.

Notation: Subsequently we often view permutations and also Lehmer codes as words in the alphabet ℕ_{0}, so that it makes sense to append ‘letters’ to the left or right and also to apply operators such as σ_{i} or the m_{+} discussed in Section 1 to these ‘words’. As an example consider (1_{+} ∘ (3, 1, 2) ∘ (1 2 2_{+}(π σ_{1})) ∘ σ_{2}) 1, which means: take the word π 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 π = 312 ∈ S_{3} is 324651 ∈ S_{6}.

The next proposition indicates how to build up permutations according to the recursive structure on Lehmer codes.

Proposition 2.6. π_{n} = (n + 1)π, π_{0} = 1 1_{+}(π) and π_{k} = σ_{k}π_{k−1} for 0 < k ≤ n using the above notations.

Proof. Directly from the definitions one has π_{k}1 = k + 1 for all k and L((n + 1) π) = \overline{n} L(π), which implies the first assertion. The second follows from L(1 1_{+}(π)) = \overline{0} L(π), because the Lehmer code is invariant under the ‘translations’ m_{+} : ℤ ⟶ ℤ for all m ∈ ℤ, i.e. for fixed π ∈ S_{n} and m_{+}π ∈ S_{m_{+}({1,...,n})} one has L(π) = L(m_{+}π) for all m ∈ ℤ.

Now π_{k−1} = k … (k +1) … with k +1 standing at some place ν between 2 and n+1. Therefore σ_{k}π_{k−1} = (k + 1) … k … with k at place ν and L(σ_{k}π_{k−1}) is the same as L(π_{k−1}) except for k instead of k − 1 at the first place. Hence L(π_{k−1}) = \overline{k − 1} L(π) ⇒ L(σ_{k}π_{k−1}) = \overline{k} L(π) ⇒ σ_{k}π_{k−1} = L^{−1}(\overline{k} L(π)) = π_{k}.

Corollary 2.7. π_{k} = ε′_{nk}(π) = σ_{k} … σ_{1}(1 1_{+}(π)) = 1_{+} ∘ (k, …, 0) ∘ (0 π) .

Proof. Only the last equality needs an explanation: σ_{k} … σ_{1}(1 1_{+}(π)) = (k + 1, …, 1) ∘ 1_{+}(0 π) = 1_{+} ∘ (k, …, 0) ∘ (0 π) .

The corollary describes an algorithm, which computes a permutation π from L(π) in such a way, that for each right part of L(π) we get the corresponding permutation.

Example 2.8. Recursive computation of L^{−1}(\overline{23010}) = 35142 .

\begin{matrix}\overline{0} : & 1 = L^{−1}(\overline{0}) \\ \overline{10} : & 01 ⟶^{(1,0)} 10 ⟶^{1_{+}} 21 = L^{−1}(\overline{10}) \\ \overline{010} : & 021 ⟶^{(0)} 021 ⟶^{1_{+}} 132 = L^{−1}(\overline{010}) \\ \overline{3010} : & 0132 ⟶^{(3,2,1,0)} 3021 ⟶^{1_{+}} 4132 = L^{−1}(\overline{3010}) \\ \overline{23010} : & 04132 ⟶^{(2,1,0)} 24031 ⟶^{1_{+}} 35142 = L^{−1}(\overline{23010}) \end{matrix}

The preceding example computes π ∈ S_{n} from L(π) by starting from id_{1} ≡ 1 ∈ S_{1}; the next proposition shows, how one can do this computation starting from id_{n} ≡ 1 … n ∈ S_{n}.

Proposition 2.9. For π ∈ S_{n} let L(π) ≡ \overline{l_{n−1} … l_{0}} , then π = 1_{+}(l_{n−1}, …, 0) ∘ 2_{+}(l_{n−2}, …, 0) ∘ ⋯ ∘ n_{+}(l_{0}) (1 … n) .

Proof. This is the first instance of what we called long induction, i.e. an induction over all permutations π ∈ S_{∞} : we establish the property in question for S_{1} and then use the recursive structure on 𝕃_{∞} or S_{∞}, i.e we investigate two types of induction steps: first from π ∈ S_{n} to π_{0} ∈ S_{n+1} [or π_{n} ∈ S_{n+1}] and second from π_{k−1} to π_{k} [or π_{k} to π_{k−1}] in S_{n+1}.

For π = 1 ∈ S_{1} the assertion is trivial. Step π to π_{0}: L(π_{0}) = \overline{0} L(π) implies l_{ν} ≡ l_{ν}(π) = l_{ν}(π_{0}) for ν = 0, …, n − 1 and l_{n}(π_{0}) = 0, hence π_{0} = 1 1_{+}(π) = 1 [2_{+}(l_{n−1}, …, 0) ∘ ⋯ ∘ (n + 1)_{+}(l_{0})(2 … (n + 1))] which equals 1_{+}(0) ∘ 2_{+}(l_{n−1}, …, 0) ∘ ⋯ ∘ (n + 1)_{+}(l_{0})(1 … (n + 1)), because the cycles do not act upon the letter 1 and 1_{+}(0) = id.

Step π_{k−1} to π_{k}: π_{k} = σ_{k}π_{k−1} = σ_{k} ∘1_{+}(k−1, …, 0)∘⋯∘(n+1)_{+}(l_{0}) (1 … (n+1)) = 1_{+}(k, …, 0) ∘ ⋯ ∘ (n + 1)_{+}(l_{0}) (1 … (n + 1)) .

Example 2.10. L^{−1}(\overline{23010}) = 1_{+}(2, 1, 0)∘2_{+}(3, 2, 1, 0)∘3_{+}(0)∘4_{+}(1, 0)∘5_{+}(0) (1 … n) = (3, 2, 1)∘(5, 4, 3, 2)∘id∘(5, 4)∘id (12345) = (3, 2, 1)∘(5, 4, 3, 2) (12354) = (3, 2, 1) (15243) = 35142 .

Corollary 2.11. For π ∈ S_{n} and L(π) ≡ \overline{l_{n−1} … l_{0}} is

Φ(L(π)) := 0_{+}(l_{n−1} … 1) 1_{+}(l_{n−2} … 1) … (n − 2)_{+}(l_{1} … 1) ∈ R(π)

a reduced sequence, where for k ≤ 0 we define m_{+}(k … 1) to be the empty sequence .

Proof. Clearly 0_{+}(l_{n−1} … 1)1_{+}(l_{n−2} … 1) … (n−2)_{+}(l_{1} … 1) contains l(π) components, hence k_{+} (l_{n−k}, …, 0) = (k − 1)_{+} (l_{n−k} + 1, …, 1) = (k − 1)_{+} ((l_{n−k}, l_{n−k} + 1) ∘ ⋯ ∘ (1, 2)) gives the result.

Example 2.12. By Cor.2.11 a reduced sequence for π = 35142 ≈ \overline{23010} is given by 0_{+}(21) 1_{+}(321) 3_{+}(1) = 214324 and indeed π = σ_{2}σ_{1}σ_{4}σ_{3}σ_{2}σ_{4} .

3. Recursive structure of Schubert polynomials

We first collect some elementary properties of Schubert polynomials and the operators ∂_{π} in:

Proposition 3.1. a) X_{id} = 1 and X_{ω_{n}} = x^{E_{n}};

b) X_{π} is a homogeneous polynomial of degree l(π);

c) for all π, ρ ∈ S_{∞}: ∂_{π}∂_{ρ} = ∂_{πρ}, if l(πρ) = l(π) + l(ρ), and = 0 otherwise;

d) for all π, ρ ∈ S_{∞}: ∂_{π}X_{ρ} = X_{ρπ^{−1}}, if l(ρπ^{−1}) = l(ρ) − l(π), and = 0 otherwise;

e) for π ∈ S_{n}, 1 ≤ k < n : ∂_{k}X_{π} = X_{πσ_{k}}, if πk > π(k + 1), and ∂_{k}X_{π} = 0, if πk < π(k + 1);

f) X_{π} is symmetric in x_{k} and x_{k+1} iff πk < π(k+1); let j be the first descent in π, then X_{π}(x_{1}, …, x_{j}, 0, …) is symmetric and called the symmetric part of X_{π};

g) X_{π} is symmetric iff π is Grassmannian;

h) X_{σ_{i}} = x_{1} + ⋯ + x_{i} for all i ∈ ℕ;

i) X_{π} is invariant under embedding of π, i.e. X_{π′} = X_{π} for n < m, π ∈ S_{n} and π′ = π1 … πn (n + 1) … m ∈ S_{m}.

Proof. a), b) and c) are immediate from the definition X_{π} := ∂_{π^{−1}ω_{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 ∂_{π}X_{ρ} = ∂_{π}∂_{ρ^{−1}ω_{n}}x^{E_{n}} =^{!} ∂_{πρ^{−1}ω_{n}}x^{E_{n}} = X_{ρπ^{−1}}, if l(π) = l(ρ^{−1}ω_{n})+

l(πρ^{−1}ω_{n}), which is by Lemma 2.1 e,g) equivalent to l(ρπ^{−1}) = l(ρ) − l(π);

e): by part c) X_{πσ_{k}} = ∂_{(πσ_{k})^{−1}ω_{n}}x^{E_{n}} = ∂_{σ_{k}π^{−1}ω_{n}}x^{E_{n}} =^{!} ∂_{k}∂_{π^{−1}ω_{n}}x^{E_{n}} = ∂_{k}X_{π}, if

|L(σ_{k}π^{−1}ω_{n})| = |L(π^{−1}ω_{n})| + 1 ⇔ |L(πσ_{k})| = |L(π)| − 1 ⇔ πk > π(k + 1);

e) ⟹ f) ⟹ g) ;

h) X_{σ_{i}} is homogeneous of degree 1 by b), symmetric in x_{1}, …, x_{i} by f) and ∂_{i}X_{σ_{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(π′) = l(π) and l(ω_{n+1}π′) = l(ω_{n}π) + n; let ρ = (n + 1, n, …, 1) = σ_{n} ∘ ⋯ ∘ σ_{1}, then ρ^{−1} = (1, 2, …, n + 1) and ρ^{−1}ω_{n}π = ω_{n+1}π′; moreover a_{1} … a_{p} ∈ R(π^{−1}ω_{n}) ⟹ a_{1} … a_{p} n … 1 ∈ R(π^{−1}ω_{n}ρ) = R((ρ^{−1}ω_{n}π)^{−1}) = R((π′)^{−1}ω_{n+1}); finally X_{π′} = ∂_{(π′)^{−1}ω_{n+1}}x^{E_{n+1}} = ∂_{π^{−1}ω_{n}}∂_{n} … ∂_{1}x^{E_{n+1}} = ∂_{π^{−1}ω_{n}}x^{E_{n}} = X_{π}.

Obviously the recursive structures for permutations (cf. Section 2) given by π → π_{0} → ⋯ → π_{n} resp. π → π_{n} → ⋯ → π_{0} can not be applied directly, but Prop.3.1 e) suggests an idea how to proceed.

We define for n ∈ ℕ, 1 ≤ k ≤ n the following subsets of S_{n}:

S_{n}(k) := {π ∈ S_{n} | πk = 1} , S′_{n}(k) := {π ∈ S_{n} | πk = n} ;

Clearly the sets {S_{n}(1), …, S_{n}(n)} and {S′_{n}(1), …, S′_{n}(n)} are partitions of S_{n} into

parts of equal cardinality (n − 1)! . Moreover with σ_{k}^{∗}π := π ∘ σ_{k} one has S_{n}(n) ⟶^{σ_{n−1}^{∗}}

⋯ ⟶^{σ_{1}^{∗}} 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) ⟶^{σ_{1}^{∗}} ⋯ ⟶^{σ_{n−1}^{∗}} S′_{n}(n) , i.e. the letter n is moved by transpositions from the 1^{st} place to the n^{th} . For the subsets

S_{n}(k) := {X_{π} | π ∈ S_{n}(k)} , S′_{n}(k) := {X_{π} | π ∈ S′_{n}(k)}

of S_{n} the preceding proposition yields: S_{n}(n) ⟶^{∂_{n−1}} ⋯ ⟶^{∂_{1}} S_{n}(1) and S′_{n}(1) ⟶^{∂_{1}} ⋯ ⟶^{∂_{n−1}} S′_{n}(n − 1).

We now investigate the meaning of the bijective sequences S_{n}(n) ⟶^{σ_{n−1}^{∗}} ⋯ ⟶^{σ_{1}^{∗}} S_{n}(1)

and S′_{n}(1) ⟶^{σ_{1}^{∗}} ⋯ ⟶^{σ_{n−1}^{∗}} S′_{n}(1) in terms of Lehmer codes. For n ∈ ℕ, 1 ≤ k ≤ n we define the following subsets of 𝕃_{n}:

𝕃_{n}(n − k) := L(S_{n}(k)) , 𝕃′_{n}(n − k) := L(S′_{n}(k)) .

Then 𝕃_{n}(k) = {l ∈ 𝕃_{n} | l_{k} = 0 and for k′ > k : l_{k′} > 0}, because the place of 1 in π is the place of the first \overline{0} in L(π) ; similarly 𝕃′_{n}(k) := \{l ∈ 𝕃_{n} | l_{k} = k and for k′ > k : l_{k′} < k\} , because the place of n in π is the place of the first l_{k} taking its maximum possible value. With this notations one gets the bijective sequences 𝕃_{n}(0) ⟶^{τ_{1}} ⋯ ⟶^{τ_{n−1}} 𝕃_{n}(n−1)

and 𝕃′_{n}(n − 1) ⟶^{τ′_{n−1}} ⋯ ⟶^{τ′_{1}} 𝕃′_{n}(0) , where for 1 ≤ k < n :

τ_{k} : 𝕃_{n}(k − 1) ⟶ 𝕃_{n}(k) , \overline{… l_{k} 0 …} ↦ \overline{… 0 (l_{k} − 1) …}
τ′_{k} : 𝕃′_{n}(k) ⟶ 𝕃′_{n}(k − 1) , \overline{… k l_{k−1} …} ↦ \overline{… l_{k−1} (k − 1) …}

The next result recasts the preceding facts in terms of the π_{k} := L^{−1}(\overline{k} L(π)).

Proposition 3.2. Let π ∈ S_{n−1}. Then π_{0}^{−1}ω_{n} ↦ ⋯ ↦ π_{n−1}^{−1}ω_{n} and ω_{n}π_{0}^{−1} ↦ ⋯ ↦ ω_{n}π_{n−1}^{−1} are sequences of elements subordinate to the sequences

S_{n}(n) ⟶^{σ_{n−1}^{∗}} ⋯ ⟶^{σ_{1}^{∗}} S_{n}(1) and S′_{n}(1) ⟶^{σ_{1}^{∗}} ⋯ ⟶^{σ_{n−1}^{∗}} S′_{n}(n) .

Proof. π_{0} = 1 1_{+}(π) ⇒ π_{0}^{−1}(1) = 1 implies π_{0}^{−1}ω_{n}(n) = 1 and ω_{n}π_{0}^{−1}(1) = n . Hence π_{0}^{−1}ω_{n} ∈ S_{n}(n) and ω_{n}π_{0}^{−1} ∈ S′_{n}(1). Using π_{k} = σ_{k}π_{k−1} it is not hard to see that π_{k}^{−1}ω_{n} = π_{k−1}^{−1}σ_{k}ω_{n} = (π_{k−1}^{−1}ω_{n})σ_{n−k} and ω_{n}π_{k}^{−1} = ω_{n}(σ_{k}π_{k−1})^{−1} = (ω_{n}π_{k−1}^{−1})σ_{k} .

Clearly the following mappings are bijections:

σ_{+}^{(n)} : S_{n−1} ⟶ S_{n}(n) , π ↦ 1_{+}(π) 1 , (σ′)_{+}^{(n)} : S_{n−1} ⟶ S′_{n}(1) , π ↦ n π ;

in terms of Lehmer codes they read

τ_{+}^{(n)} : 𝕃_{n−1} ⟶ 𝕃_{n}(0) , L(π) ↦ 1_{+}(L(π)) \overline{0}
(τ′)_{+}^{(n)} : 𝕃_{n−1} ⟶ 𝕃′_{n}(n − 1) , L(π) ↦ \overline{n − 1} L(π) .

It remains to describe the corresponding mappings for the Schubert polynomials S_{n−1}. First we define the following ℤ-linear mappings (recall d_{n} = 0 for all d ∈ D_{n}) :

(1_{+}^{↑})^{(n)} ≡ ∂_{+}^{(n)} , 1_{+}^{↓} , (∂′)_{+}^{(n)} : ℤ_{E_{n−1}}[x] ⟶ ℤ_{E_{n}}[x] ,

(1_{+}^{↑})^{(n)} ∏_{ν=1}^{n−1} x_{ν}^{d_{ν}} := ∏_{ν=1}^{n−1} x_{ν}^{d_{ν}+1} , 1_{+}^{↓} ∏_{ν=1}^{n−1} x_{ν}^{d_{ν}} := ∏_{ν=1}^{n} x_{ν+1}^{d_{ν}} , (∂′)_{+}^{(n)} := x_{1}^{n−1} 1_{+}^{↓} .

It is not hard to compute that

∂_{i} ∘ (1_{+}^{↑})^{(n)} = (1_{+}^{↑})^{(n)} ∘ ∂_{i} , ∂_{i+1} ∘ 1_{+}^{↓} = 1_{+}^{↓} ∘ ∂_{i} and (1_{+}^{↑})^{(n)}x^{E_{n−1}} = x^{E_{n}} = x_{1}^{n−1} 1_{+}^{↓}x^{E_{n−1}} .

The next result now closes the remaining gap in our recursion:

Proposition 3.3. Let π ∈ S_{n−1}, then with the above notations X_{σ_{+}π} = ∂_{+}^{(n)}X_{π} = x_{1} … x_{n−1}X_{π} and X_{σ′_{+}π} = (∂′)_{+}^{(n)}X_{π} = x_{1}^{n−1} 1_{+}^{↓} X_{π}.

Proof. (We suppress the indices ^{(n)}.) Recall the mapping Φ from Cor.2.8, which maps L(π) to a reduced sequence ∈ R(π).

σ_{+}π = 1_{+}(π) 1 ⇒ σ_{+}π(n) = 1 and for k = 1, …, n − 1 : σ_{+}π(k) = π(k) + 1. Hence (σ_{+}π)^{−1}ω_{n}(n) = (σ_{+}π)^{−1}(1) = n and (σ_{+}π)^{−1}ω_{n}(k) = (σ_{+}π)^{−1}(n + 1 − k) = π^{−1}(n − k) = π^{−1}ω_{n−1}(k), i.e. (σ_{+}π)^{−1}ω_{n} = (π^{−1}ω_{n−1}) n. Therefore ΦL((σ_{+}π)^{−1}ω_{n}) = Φ( L(π^{−1}ω_{n−1})\overline{0} ) = ΦL(π^{−1}ω_{n−1}) ⇒ ∂_{(σ_{+}π)^{−1}ω_{n}} = ∂_{π^{−1}ω_{n−1}} and finally X_{σ_{+}π} = ∂_{(σ_{+}π)^{−1}ω_{n}} x^{E_{n}} = ∂_{π^{−1}ω_{n−1}} 1_{+}^{↑}x^{E_{n−1}} = 1_{+}^{↑}∂_{ΦL(π^{−1}ω_{n−1})} x^{E_{n−1}} = 1_{+}^{↑}X_{π} ≡ ∂_{+}X_{π} .

Similarly σ′_{+}π = n π ⇒ σ′_{+}π(1) = n and for k = 2, …, n : σ′_{+}π(k) = π(k+1) . Hence (σ′_{+}π)^{−1}ω_{n}(1) = (σ′_{+}π)^{−1}(n) = 1 and (σ′_{+}π)^{−1}ω_{n}(k) = π^{−1}( ω_{n}(k) ) + 1 = 1_{+}π^{−1}ω_{n}(k), i.e. (σ′_{+}π)^{−1}ω_{n} = 1 1_{+}(π^{−1}ω_{n}). Therefore ΦL((σ′_{+}π)^{−1}ω_{n}) = Φ(\overline{0} L(π^{−1}ω_{n−1}) ) = 1_{+}ΦL(π^{−1}ω_{n−1}), which implies X_{σ′_{+}π} = ∂_{(σ′_{+}π)^{−1}ω_{n}} x^{E_{n}} = ∂_{ΦL((σ′_{+}π)^{−1}ω_{n})} x^{E_{n}} = ∂_{1_{+}ΦL(π^{−1}ω_{n−1})} x_{1}^{n−1}1_{+}^{↓}x^{E_{n−1}} = x_{1}^{n−1} 1_{+}^{↓}(∂_{ΦL(π^{−1}ω_{n−1})} x^{E_{n−1}}) = x_{1}^{n−1} 1_{+}^{↓}X_{π} = ∂′_{+}X_{π} .

The following commutative diagrams, in which all arrows are bijections, summarize our information about the recursive structures:

𝕃_{n−1} ⟶^{τ_{+}^{(n)}} 𝕃_{n}(0) ⟶^{τ_{1}} … ⟶^{τ_{n−1}} 𝕃_{n}(n − 1)
L^{−1}↓  _{L^{−1}}↓  _{L^{−1}}↓
S_{n−1} ⟶^{σ_{+}^{(n)}} S_{n}(n) ⟶^{σ_{n−1}^{∗}} … ⟶^{σ_{1}^{∗}} S_{n}(1)
X↓  ^{X}↓  ^{X}↓
S_{n−1} ⟶^{∂_{+}^{(n)}} S_{n}(n) ⟶^{∂_{n−1}} … ⟶^{∂_{1}} S_{n}(1)

𝕃_{n−1} ⟶^{(τ′)_{+}^{(n)}} 𝕃′_{n}(n − 1) ⟶^{τ′_{n−1}} … ⟶^{τ′_{1}} 𝕃′_{n}(0)
L^{−1}↓  _{L^{−1}}↓  _{L^{−1}}↓
S_{n−1} ⟶^{(σ′)_{+}^{(n)}} S′_{n}(1) ⟶^{σ_{1}^{∗}} … ⟶^{σ_{n−1}^{∗}} S′_{n}(n)
X↓  ^{X}↓  ^{X}↓
S_{n−1} ⟶^{(∂′)_{+}^{(n)}} S′_{n}(1) ⟶^{∂_{1}} … ⟶^{∂_{n−1}} S′_{n}(n)

We call the first diagram the up case diagram, because (1_{+}^{↑})^{(n)} acts on the exponents, and the second the down case diagram, because 1_{+}^{↓} acts on the subscripts.

Example 3.4. π = 41253 ≈ \overline{30010} , X_{π} = x_{1}^{3}x_{4} + x_{1}^{3}x_{3} + x_{1}^{3}x_{2} , which reads in ℤD_{∞} : 30010 + 30100 + 31000.

First the up case (recall that for Lehmer codes the position of the first \overline{0} is crucial, and for permutations the position of the 1 ) :

\overline{0} ⟶^{τ_{+}^{(2)}} \overline{10} ⟶^{τ_{1}} \overline{00} ⟶^{τ_{+}^{(3)}} \overline{110} ⟶^{τ_{+}^{(4)}} \overline{2210} ⟶^{τ_{1}} \overline{2200} ⟶^{τ_{2}} \overline{2010} ⟶^{τ_{+}^{(5)}} \overline{31210} ⟶^{τ_{1}} \overline{31200} ⟶^{τ_{2}}
\overline{31010} ⟶^{τ_{3}} \overline{30010}

1 ⟶^{σ_{+}^{(2)}} 21 ⟶^{σ_{1}^{∗}} 12 ⟶^{σ_{+}^{(3)}} 231 ⟶^{σ_{+}^{(4)}} 3421 ⟶^{σ_{3}^{∗}} 3412 ⟶^{σ_{2}^{∗}} 3142 ⟶^{σ_{+}^{(5)}} 42531 ⟶^{σ_{4}^{∗}} 42513 ⟶^{σ_{3}^{∗}}

42153 ⟶^{σ_{2}^{∗}} 41253

0 ⟶^{∂_{+}^{(2)}} 10 ⟶^{∂_{1}} 00 ⟶^{∂_{+}^{(3)}} 110 ⟶^{∂_{+}^{(4)}} 2210 ⟶^{∂_{3}} 2200 ⟶^{∂_{2}} 2100 + 2010 ⟶^{∂_{+}^{(5)}} 32110 + 31210 ⟶^{∂_{4}}

32100 + 31200 ⟶^{∂_{3}} 32000 + 31100 + 31010 ⟶^{∂_{2}} 31000 + 30100 + 30010.

Second the 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 π(k) ) :

\overline{0} ⟶^{(τ′)_{+}^{(2)}} \overline{10} ⟶^{τ′_{1}} \overline{00} ⟶^{(τ′)_{+}^{(3)}} \overline{200} ⟶^{τ′_{2}} \overline{010} ⟶^{τ′_{1}} \overline{000} ⟶^{(τ′)_{+}^{(4)}} \overline{3000} ⟶^{(τ′)_{+}^{(5)}} \overline{43000} ⟶^{τ′_{4}} \overline{33000} ⟶^{τ′_{3}}
\overline{30200} ⟶^{τ′_{2}} \overline{30010}

1 ⟶^{(σ′)_{+}^{(2)}} 21 ⟶^{σ_{1}^{∗}} 12 ⟶^{(σ′)_{+}^{(3)}} 312 ⟶^{σ_{1}^{∗}} 132 ⟶^{σ_{2}^{∗}} 123 ⟶^{(σ′)_{+}^{(4)}} 4123 ⟶^{(σ′)_{+}^{(5)}} 54123 ⟶^{σ_{1}^{∗}} 45123 ⟶^{σ_{2}^{∗}}

41523 ⟶^{σ_{3}^{∗}} 41253

0 ⟶^{(∂′)_{+}^{(2)}} 10 ⟶^{∂_{1}} 00 ⟶^{(∂′)_{+}^{(3)}} 200 ⟶^{∂_{1}} 100+010 ⟶^{∂_{2}} 000 ⟶^{(∂′)_{+}^{(4)}} 3000 ⟶^{(∂′)_{+}^{(5)}} 43000 ⟶^{∂_{1}} 33000 ⟶^{∂_{2}}

32000 + 31100 + 30200 ⟶^{∂_{3}} 31000 + 30100 + 30010.

Note that the Lehmer codes occur as summands in the ℤD_{∞} sequence by property (B).

The existence of the recursive structures makes possible long induction over all Lehmer codes, permutations or Schubert polynomials by using two different types of steps: first the (+)-step or embedding step from (n − 1) to n and second the (τ)-, (σ)- or (∂)-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 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 up case, which by virtue of its especially simple form of the (τ)-step will be used later to give new proofs of the basic properties (B), (M), (P) and (S) of Schubert polynomials, and the down case.

Remark 3.5. There are unique ‘minus’-bijections σ_{−}^{(n)} and (σ′)_{−}^{(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 σ_{−}^{(n)} : S_{n}(1) ⟶ S_{n−1}, such that the composition of mappings

S_{n−1} ⟶^{σ_{+}^{(n)}} S_{n}(n) ⟶^{σ_{n−1}^{∗}} ⋯ ⟶^{σ_{1}^{∗}} S_{n}(1) ⟶^{σ_{−}^{(n)}} S_{n−1} is the identity on S_{n−1} . Clearly σ_{−}^{(n)} is

given by 1 1_{+}(π) ↦ π and τ_{−}^{(n)} by \overline{0} l ↦ l ; ∂_{−}^{(n)} means: first set x_{1} = 0 and then apply 1′_{−} , i.e. x_{k} ↦ x_{k−1} for all k. Similarly (σ′)_{−}^{(n)} is given by π n ↦ π and (τ′)_{−}^{(n)} by l \overline{0} ↦ l ; (∂′)_{−}^{(n)} is the reversal of the embedding S_{n−1} ↪ S_{n} , i.e. forgetting x_{n}^{0} .

Corollary 3.6. Let π′ ∈ S_{n+m} be the image of π ∈ S_{n} under right embedding, i.e. L(π′) = \overline{0 … 0} L(π) with m zeros (cf. Section 1), then

X_{π} = (1_{−}^{↓})^{m}(X_{π′}|_{x_{1}=···=x_{m}=0}) ,

i.e. in order to compute X_{π} from X_{π′} set x_{1} = ⋯ = x_{m} = 0 and shift all indices by −m.

We close this section with an investigation of the recursive structures for double Schubert polynomials:

For arbitrary n and π ∈ S_{n} the double Schubert polynomials 𝕏_{π}(x, y) ∈ ℤ[x, y] in the sets of variables x = (x_{1}, x_{2}, …) and y = (y_{1}, y_{2}, …) are defined by

𝕏_{π}(x, y) := ∂_{π^{−1}ω_{n}}Δ_{n}(x, y) with Δ_{n}(x, y) := ∏_{i+j≤n}(x_{i} − y_{j}),

where ∂_{π^{−1}ω_{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 Δ_{n}(x, y) in the definition according to the formula ([M1],(5.7) )

Δ_{n}(x, y) = ∑_{π∈S_{n}} 𝕏_{π}(x)𝕏_{πω_{n}}(−y) ,

then the divided differences do not affect the 𝕏_{πω_{n}}(−y)’s and by Prop.3.1 e) ∂_{k}X_{π}(x) = X_{πσ_{k}}(x), if πk > π(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 ∂_{+} and ∂′_{+} are defined as follows: assume π ∈ S_{n−1}, then

∂_{+}^{(n)} 𝕏_{π}(x, y) := (x_{1} − y_{1}) … (x_{n−1} − y_{1}) 1_{+,y}^{↓} 𝕏_{π}(x, y)
(∂′)_{+}^{(n)} 𝕏_{π}(x, y) := (x_{1} − y_{1}) … (x_{1} − y_{n−1}) 1_{+,x}^{↓} 𝕏_{π}(x, y),

where 1_{+,x}^{↓}, 1_{+,y}^{↓} 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 Δ_{n}(x, y) = (x_{1}−y_{1}) … (x_{1}−y_{n−1}) 1_{+,x}^{↓} Δ_{n−1}(x, y) and for the up case Δ_{n}(x, y) = (x_{1}−y_{1}) … (x_{n−1}− y_{1}) 1_{+,y}^{↓} Δ_{n−1}(x, y). Observe that for π ∈ S_{n−1} only ∂_{k} with 1 ≤ k ≤ n − 2 occurs in ∂_{π^{−1}ω_{n}} and that for these k one has ∂_{k}(x_{1} −y_{1}) … (x_{n−1} −y_{1}) 1_{+,y}^{↓} = (x_{1} −y_{1}) … (x_{n−1} − y_{1}) ∂_{k} 1_{+,y}^{↓} = (x_{1} − y_{1}) … (x_{n−1} − y_{1}) 1_{+,y}^{↓} ∂_{k} .

4. 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 ∂_{π^{−1}ω_{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’ ∅ . It turns out that this sequence can itself be described by a Lehmer code. As an example consider 3.4 above: \overline{30010} = τ_{3}τ_{2}τ_{1}τ_{+}^{(5)}τ_{2}τ_{1}τ_{+}^{(4)}τ_{+}^{(3)}τ_{1}τ_{+}^{(2)}τ_{+}^{1} (∅) , where τ_{+}^{(1)} : 𝕃_{0} ⟶ 𝕃_{1}, ∅ ↦ \overline{0}. We now divide this sequence into parts each beginning with a τ_{+} and ending before the next τ_{+} to the left. Representing ‘parts’ τ_{k} … τ_{1}τ_{+} by the number k and a ‘part’ τ_{+} by the number 0 , the building sequence for \overline{30010} (in the up case) can be coded by the sequence of numbers 32010 .

Let now \overleftarrow{E} 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 \overleftarrow{E} is a graded bijection of 𝕃_{∞} onto itself.

Let \overleftarrow{E}(l) ≡ \overline{e_{n−1} … e_{0}} for l = \overline{l_{n−1} … l_{0}} ∈ 𝕃_{n} and let l^{(i)} be the last item on level i in the (up case) building sequence for l , so l^{(0)} = ∅ and l^{(n)} = l . Then e_{i} = k iff l^{(i+1)} ∈ 𝕃_{i+1}(k), i.e. 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 (τ_{+})^{−1}(τ_{1})^{−1} … (τ_{k−1})^{−1} : 𝕃_{i+1}(k) ⟶ 𝕃_{i} , which maps l^{(i+1)} to l^{(i)} is accomplished by the transformation

\overline{l_{i} … l_{k+1}0 l_{k−1} … l_{0}} ↦ \overline{(l_{i} − 1) … (l_{k+1} − 1) l_{k−1} … l_{0}} .

Therefore we have specified an algorithm, which allows the computation of the \overleftarrow{E}- transform and moreover yields all information needed to compute a certain Schubert polynomial X_{π} for π ∈ S_{m} under the assumption that all Schubert polynomials S_{n} for some n < m are already known, thus bringing the recursive structures of Section 3 to a practical level.

Example 4.1. \overleftarrow{E}( \overline{30010} ) = \overline{32010}: \begin{matrix}3\underline{0}010 & | & 3 \\ 2\underline{0}10 & | & 2 \\ 11\underline{0} & | & 0 \\ \underline{0}0 & | & 1 \\ \underline{0} & | & 0 \end{matrix} and under the assumption that all

of S_{3} is known, one can calculate X_{L^{−1}(\overline{30010})} by applying the operator ∂_{2}∂_{3}∂_{4}(1_{+}^{↑})^{(5)}∂_{2}∂_{3}(1_{+}^{↑})^{(4)} to X_{L^{−1}(\overline{110})}.

Remark 4.2. For the last statement of Ex.4.1 we used the rule that τ_{k} … τ_{1}τ_{+}^{(i)} on 𝕃_{i} corresponds to ∂_{i+1−k} … ∂_{i}(1_{+}^{↑})^{(i)} on S_{i}. Concerning the whole building sequence for some X_{π}, π ∈ S_{n}, the n − 1 factors 1_{+}^{↑} can be commuted to the right and give (1_{+}^{↑})^{n−1}(1) = x^{E_{n}}; the remaining l(π) factors ∂_{ν} are now applied to x^{E_{n}} with the result X_{π}. Hence the sequence of the indices of the ∂_{ν} is a reduced sequence for π^{−1}ω_{n} , which can be computed from \overleftarrow{E}(L(π)) ≡ \overline{e_{n−1} … e_{0}} by application of the mapping

Φ′(\overline{e_{n−1} … e_{0}}) := Φ′_{n−1}(e_{n−1}) … Φ′_{0}(e_{0}),

where Φ′_{i}(k) := (i + 1 − k) … i if k > 0 and Φ′_{i}(0) = ∅.

Consequently |\overleftarrow{E}(L(π))| = n(n + 1)/2 − |L(π)| for π ∈ S_{n}. In general Φ′ \overleftarrow{E}(L(π)) ≠ Φ L(π^{−1}ω_{n}), where Φ is the mapping from Cor.2.11 .

Remark 4.3. Different reduced words for the calculation of some X_{π} can lead to very different amount of work, because of the intermediary number of monomials involved. For example the permutation π^{−1}ω_{5} = 52341 ≈ \overline{41110} has the reduced sequences 1234321 and 4321234, the first leading to an economic computation of X_{π} = 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 ∂_{i} gives a Schubert polynomial with non-negative integer coefficients.

Using the algorithm for \overleftarrow{E} one easily computes \overleftarrow{E}( \overline{(n − 1) … 0} ) = \overline{0 … 0} and \overleftarrow{E}( \overline{0 … 0} ) = \overline{(n − 1) … 0} . More generally let π′ be the natural embedding of π ∈ S_{n} into S_{m} (n < m), i.e. l′ = L(π′) equals l = L(π) with m−n zeros appended to the right. Then we have \overleftarrow{E}(l′) = (m − n)_{+}(\overleftarrow{E}(l))\overline{(m − n − 1) … 1 0}, \overleftarrow{E}^{2}(l′) = \overline{0 … 0} \overleftarrow{E}^{2}(l), \overleftarrow{E}^{3}(l′) = \overline{m … (n + 1)} \overleftarrow{E}^{3}(l), and \overleftarrow{E}^{4}(l′) = \overleftarrow{E}^{4}(l)\overline{0 … 0} = l′. The 4-cycle appearing here is no accident, in fact one of our next results is \overleftarrow{E}^{4} = id_{𝕃_{∞}}.

Closely related with \overleftarrow{E} is the operator \overrightarrow{E}, which differs from \overleftarrow{E} only in counting the position of the first zero beginning with zero from left to right:

Example 4.4. \overrightarrow{E}( \overline{30010} ) = \overline{11200}: \begin{matrix}3\underline{0}010 & | & 1 \\ 2\underline{0}10 & | & 1 \\ 11\underline{0} & | & 2 \\ \underline{0}0 & | & 0 \\ \underline{0} & | & 0 \end{matrix} . Note that π = 41253 ≈ \overline{30010} and

\overline{11200} ≈ 23514 = π^{−1}.

Proposition 4.5. For all π ∈ S_{∞}: \overrightarrow{E}(L(π)) = L(π^{−1}) = H(π).

Proof. As usual let π ∈ S_{n} . The proof of Prop.2.4 shows l_{n−k}(π^{−1}) = {j|j < π^{−1}k, πj > k}, i.e. l_{n−k}(π^{−1}) is the number of letters in π left to the letter k greater than k . But in the k^{th} step of the algorithm for the determination of \overrightarrow{E}(L(π)) the zero of the intermediary Lehmer code corresponds to the letter k in π (— the k − 1 zeros in the preceding steps correspond to 1, …, k − 1 —); hence all entries in the intermediary Lehmer code other than the first zero correspond to letters in π greater than k and the algorithm for \overrightarrow{E}(L(π)) counts exactly the number of these entries left to the first zero.

Corollary 4.6. Let ε : S_{∞} ⟶ S_{∞} be defined on π ∈ S_{n} by π ↦ ω_{n}π^{−1} and recall that ι is the involution on Lehmer codes from Lemma 2.1, then:

a) \overleftarrow{E} = ι \overrightarrow{E} and \overleftarrow{E} L = L ε;

b) \overrightarrow{E} = ι \overleftarrow{E}, \overleftarrow{E}^{4} = id, \overrightarrow{E}^{2} = id, \overleftarrow{E} \overrightarrow{E} = ι, \overleftarrow{E} \overrightarrow{E} \overleftarrow{E} \overrightarrow{E} = \overrightarrow{E} \overleftarrow{E} \overrightarrow{E} \overleftarrow{E} = id.

Proof. a): \overleftarrow{E}(L(π)) = ι \overrightarrow{E}(L(π)) for all π ∈ S_{n}, because the counts in the k^{th} step of the algorithm for the determination of \overleftarrow{E}(L(π)) and \overleftarrow{E}(L(π)) add up to n − k. Moreover by Lemma 2.1 f): \overleftarrow{E}(L(π)) = ι \overrightarrow{E}(L(π)) = ι L(π^{−1}) = L(ω_{n}π^{−1}) = L(επ).

b) is immediate.

Remark 4.7. In (4.1) it has been shown that Φ′(\overleftarrow{E}(L(π))) ∈ R(π^{−1}ω_{n}). By Cor.4.6 this implies Φ′ L(ω_{n}π^{−1}) ∈ R(π^{−1}ω_{n}) or

Φ′ L(ω_{n}πω_{n}) ∈ R(π) ,

which is therefore a second method to compute a reduced word for an arbitrary permutation. For example π = 41532 ≈ \overline{30210} ⟶^{Φ} 321434 ∈ R(π) and ω_{5}πω_{5} = 43152 ≈

\overline{32010} ⟶^{Φ′} 234231 ∈ R(π).

Remark 4.8. In view of Cor.4.6 it seems interesting to describe the sets fix_{n}(ε^{m}) := {π ∈ S_{n} | ε^{m}π = π } in more detail. Trivially fix_{n}(ε^{4}) = S_{n} and by cyclicity it is enough to investigate fix_{n}(ε^{m}) for m = 1, 2, 3. We have ε(π) = ω_{n}π^{−1}, ε^{2}(π) = ω_{n}πω_{n} and ε^{3}(π) = π^{−1}ω_{n} and fix_{n}(ε^{3}) = fix_{n}(ε) , because ε^{3}(π) = π ⇔ π^{2} = ω_{n} ⇔ π = ω_{n}π^{−1} = ε(π). The next result fully describes the situation in the remaining cases m = 1, 2 for all n ∈ ℕ.

Proposition 4.9. a) |fix_{2n+1}(ε^{2})| = |fix_{2n}(ε^{2})| = n! 2^{n} ;

b) |fix_{n}(ε)| = 0, if n ≡ 2, 3 (mod4) and |fix_{4n+1}(ε)| = |fix_{4n}(ε)| = (2n)!/n!. Moreover the proof contains a procedure to enumerate the elements of these sets.

Proof. ε^{2}(π) = π ⇔ ω_{n}π = πω_{n} ⇔ πi+π(n+1−i) = n+1, i.e. letters on complementary places in π are complementary. Hence every π ∈ fix_{2n}(ε^{2}) is completely determined by π1, …, πn. There are n pairs of complementary numbers in {1, …, 2n}, 2^{n} possibilities for selecting one number from every pair and n! permutations for every selection. The bijection a_{1} … a_{n} a_{n+1} … a_{2n} ↦ a_{1} … a_{n} ((n+1)/2) (a_{n+1}+1) … (a_{2n}+1) from fix_{2n}(ε^{2}) to fix_{2n+1}(ε^{2}) completes the proof of a).

π ∈ fix_{n}(ε) ⇔ π^{2} = ω_{n} implies π^{4} = id, so that the possible cycle lengths of π are 1, 2, 4. If π has a fixpoint k, then k = π^{2}k = ω_{n}k = n + 1 − k ⇔ k = (n + 1)/2, and if k lies in a 2-cycle of π, then k is already a fixpoint. Therefore any π ∈ fix_{n}(ε) 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}(ε) = ∅, if n ≡ 2, 3 ( mod 4), and that 2n+1 is the unique fixpoint for every π ∈ fix_{4n+1}(ε).

Now let π ∈ fix_{4n}(ε), then every i ∈ {1, …, 4n} generates a 4-cycle (i, πi, π^{2}i = ω_{4n}i, π^{3}i = π^{2}(πi) = ω_{4n}πi). Suppose that k 4-cycles of π are already determined (0 ≤ k ≤ 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, …, 4n} \ M_{k}; clearly πi ∈ {1, …, 4n} \ M_{k} and because π is fixpoint free: πi ≠ i and πi ≠ ω_{4n}i, otherwise π(ω_{4n}i) = π^{2}i = ω_{4n}. Therefore one has |{1, …, 4n} \ M_{k}| − 2 = 4n − 4k − 2 choices for πi and consequently |fix_{4n+1}(ε)| = ∏_{k=0}^{n−1}(4(n − k) − 2) = (2n)!/n!. In exactly the same manner the π ∈ fix_{4n}(ε) are constructed, where the fixpoint 2n + 1 is a priori excluded.

As examples we note fix_{1}(ε) = S_{1}, fix_{4}(ε) = {2413, 3142}, fix_{5}(ε) = {25314, 41352} and fix_{8}(ε) = { 28463517, 28536417, 34872156, 35827146, 43781265, 46281735 } ∪ { the same π read backwards }.

We now briefly discuss the down case anlogues of the preceding results.

The role of \overleftarrow{E} is now played by \overrightarrow{E}′. The i^{th} component of \overrightarrow{E}′(L(π)) 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(π). 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 π — the numbers n, …, i + 2 have been removed in previous steps.

Example 4.10. \overrightarrow{E}′( \overline{30010} ) = \overline{30210}: \begin{matrix}300\underline{1}0 & | & 3 \\ \underline{3}000 & | & 0 \\ 00\underline{0} & | & 2 \\ 0\underline{0} & | & 1 \\ \underline{0} & | & 0 \end{matrix} and under the assumption that all

of S_{3} is known, one can calculate X_{L^{−1}(\overline{30010})} by applying the operator ∂_{3}∂_{2}∂_{1}(∂′)_{+}^{(5)}(∂′)_{+}^{()} to X_{L^{−1}(\overline{000})}.

For the last statement of Ex. 4.1’ we used the rule that τ_{i−k+1} … τ_{i}(τ′)_{+}^{(i)} on 𝕃_{i} corresponds to ∂_{k} … ∂_{1}(∂′)_{+}^{(i)} on S_{i}. Since we have 1_{+}^{↓} ∘ ∂_{i} = ∂_{i+1} ∘ 1_{+}^{↓}, the sequence of indices of the ∂_{ν} is ∈ R(π^{−1}ω_{n}) and equals Φ(π^{−1}ω_{n}) (Φ from Cor.2.11).

To \overrightarrow{E} corresponds the operator \overleftarrow{E}′, which is the same as \overrightarrow{E}′ except that counting proceeds from the right to left beginning with zero, e.g. \overleftarrow{E}′( \overline{30010} ) = \overline{13000}.

Proposition 4.11. For all π ∈ S_{∞}: \overleftarrow{E}′(L(π)) = L(ωπ^{−1}ω) = G(π).

Corollary 4.12. Let ε′ : S_{∞} ⟶ S_{∞} be defined on π ∈ S_{n} by π ↦ π^{−1}ω_{n}, then:

a) \overrightarrow{E}′ = ι \overleftarrow{E}′ and \overrightarrow{E}′ L = L ε′;

b) \overleftarrow{E}′ = ι \overrightarrow{E}′, (\overrightarrow{E}′)^{4} = id, (\overleftarrow{E}′)^{2} = id, \overrightarrow{E}′ \overleftarrow{E}′ = ι, \overrightarrow{E}′ \overleftarrow{E}′ \overrightarrow{E}′ \overleftarrow{E}′ = \overleftarrow{E}′ \overrightarrow{E}′ \overleftarrow{E}′ \overrightarrow{E}′ = id;

c) \overrightarrow{E} \overleftarrow{E}′ L(π) = \overleftarrow{E}′ \overrightarrow{E} L(π) = L(ωπω) = K(π).

The sets fix_{n}(ε^{m}) and fix_{n}((ε′)^{m}) coincide, because ε(π) = π ⇔ ε^{3}(π) = π and ε′ = ε^{3}.

As a further application of the operators discussed in this section we show that the mapping π ↦ ωπω for unembedded permutations π generalizes the conjugation of partitions:

Proposition 4.13. Let λ = λ_{1} … λ_{m} with λ_{1} ≥ ⋯ ≥ λ_{m} ≥ 1 be a partition, λ′ its conjugate and π(λ) = L^{−1} (\overline{λ_{m} … λ_{1} 0 … 0}) (with λ_{1} zeros) the corresponding Grassmannian permutation in S_{n}, n = m + λ_{1}; then

π(λ′) = ω_{n} π(λ) ω_{n} .

Proof.

\overrightarrow{E} \overleftarrow{E}′ L(π(λ)) =\overrightarrow{E} \overleftarrow{E}′ (\overline{λ_{m} … λ_{1} \underbrace{0 … 0}_{λ_{1}}})
=\overrightarrow{E} \overline{λ_{1} \underbrace{0 … 0}_{λ_{1}−λ_{2}} λ_{2} … λ_{m−1} \underbrace{0 … 0}_{λ_{m−1}−λ_{m}} λ_{m} \underbrace{0 … 0}_{λ_{m}}}
=\overline{\underbrace{1 … 1}_{λ_{1}−λ_{2}} \underbrace{2 … 2}_{λ_{2}−λ_{3}} … \underbrace{m − 1 … m − 1}_{λ_{m−1}−λ_{m}} \underbrace{m … m}_{λ_{m}} \underbrace{0 … 0}_{m}} .

Clearly the last expression is the Lehmer code of π(λ′) and the result follows from Cor. 4.7′ c).

5. Proofs of properties (B), (M), (P) and (S)

All proofs proceed by long induction over all permutations π ∈ S_{∞} 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 (∂)-step. In contrast to the (∂)-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 ∈ ℤ[x] let M(f) and DM(f) denote respectively the set of monomials and exponents of monomials occurring in f .

Proof. (B) (+)-step: assume (B) for all π ∈ S_{n−1}, then DM(X_{σ_{+}π}) = DM((1_{+}^{↑})^{(n)}(X_{π})) = 1_{+}DM(X_{π}) implies lmin(X_{σ_{+}π}) = x^{1_{+}π} = x^{σ_{+}π} with coefficient 1.

(∂)-step: let d^{0} and (d′)^{0} correspond respectively (by re indexing) to L(π) with π ∈ S_{n}(k + 1) and L(πσ_{k}) ; let ∂_{k}d denote the k-symmetrisation of d in ℤD_{∞} (cf. Ex.2.1). Assume now for d, d′ ∈ D_{n} that d < d′ in the lexicographic order and that ∂_{k}d, ∂_{k}d′ ≠ ∅; it is not hard to see that this implies lmin(∂_{k}d) < lmin(∂_{k}d′). Therefore lmin(X_{πσ_{k}}) = x^{L(πσk)} with coefficient 1, since for d^{0} we have: d_{k}^{0} > 0, d_{k+1}^{0} = 0 ⇒ ∂_{k}d^{0} ≠ ∅ and lmin(∂_{k}d^{0}) = (d′)^{0}.

Proof. (M) The (+)-step is trivial. For the ∂-step observe that for π ∈ S_{n}(k + 1) one has L(πσ_{k}) = \overline{l_{n−1} … l_{n−k+1} 0 … 0} with l_{n−1}, …, l_{n−k+1} ≥ 1; therefore L(π) = \overline{l_{n−1} … l_{n−k+1} 1 0 … 0} and ‘πσ_{k} dominant’ implies ‘π dominant’. Hence we compute X_{πσ_{k}} = ∂_{k}X_{π} = ∂_{k}x^{L(π)} = x^{τ_{n−k}L(π)} = x^{L(πσ_{k})}.

Proof. (P) Clearly (P) is valid for π ∈ S_{1}, S_{2}. Assume (P) for S_{1}, …, S_{n} (n ≥ 2) and let π ∈ S_{n+1}(k + 1). Then X_{π} = ∂_{k+1} … ∂_{n} (x_{1} … x_{n} X_{ρ}) for ρ = π(1) − 1 … π(k) − 1 π(k +2)−1 … π(n+1)−1 ∈ S_{n}. By the product rule one has for all ν ∈ ℕ, f ∈ ℤ[x]:

∂_{ν} ((x_{1} … x_{ν}) f) = (x_{1} … x_{ν−1}) (f + x_{ν+1}(∂_{ν}f)) ≡ (x_{1} … x_{ν−1}) (\overline{∂_{ν}}f) ,

i.e. \overline{∂_{ν}} = id + x_{ν+1} ∂_{ν}. Therefore X_{π} = (x_{1} … x_{k}) (\overline{∂_{k+1}} … \overline{∂_{n}} X_{ρ}). Let m_{k}(x) denote a monomial in x_{k+1}, …, x_{n}; expanding \overline{∂_{k+1}} … \overline{∂_{n}} X_{ρ} gives a sum with terms of the form m_{k}(x) · \overline{∂_{ν_{1}}} … \overline{∂_{ν_{s}}} X_{ρ}, where k + 1 ≤ ν_{1} < ⋯ < ν_{s} ≤ n. Now by Prop.3.1 e) every nonvanishing summand is of the form m_{k}(x) · X_{ρ′} for some ρ′ ∈ S_{n} and the induction hypothesis gives the result.

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 λ be of the form λ = (λ_{1}, …, λ_{m}), λ_{1} ≥ ⋯ ≥ λ_{p} > 0, λ_{p+1}, …, λ_{m} = 0 for m ≥ p > 0; then we denote the Schur polynomial in the variables x_{1}, …, x_{m} by \{λ\}^{m}. Now (S) says that \{λ\}^{m} = X_{L^{−1}(l)} with l = \overline{0 … 0 λ_{p} … λ_{1} 0 … 0} having m − p zeros on the left and ≥ λ_{1} zeros on the right. We consider the following subsequence of the long bijective staircase

\overline{0 … 0 λ_{p} … λ_{1} 0 … 0} ⟶^{τ_{+}} \overline{1 … 1 λ_{p} + 1 … λ_{1} + 1 1 … 1 0} ⟶ …

⟶ \overline{1 … 1 λ_{p} + 1 … λ_{1} + 1 0 … 0 0} ⟶ … ⟶ \overline{0 0 … 0 λ_{p} … λ_{1} 0 … 0}.

In this sequence \overline{1 … 1 λ_{p} + 1 … λ_{1} + 1 0 … 0 0} should correspond by (S) to \{1_{+}(λ)\}^{m} and \overline{0 0 … 0 λ_{p} … λ_{1} 0 … 0} to \{λ\}^{m+1}. Clearly all other intermediary Lehmer codes are not weakly increasing and all paths in the long bijective staircase, which start with a σ_{+}-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:

(1): l^{+} ↦ 1_{+}(l^{+}) and (2): l^{+} ↦ 0 l^{+} applied to −1. For partitions λ and Schur polynomials {λ}^{m} the corresponding operations are (1): λ ↦ 1_{+}λ, (2): λ ↦ λ 0 and (1): {λ}^{m} ↦ {1_{+}(λ)}^{m}), (2): {λ}^{m} ↦ {λ}^{m+1} beginning at the empty partition or the constant 1. For Lehmer codes l = L(π) ≡ \overline{0 … 0 λ_{p} … λ_{1} 0 … 0} with l_{n−m} = λ_{1} and λ_{1} zeros on the right side this means

(1) : l ↦ l^{(1)} := \overline{1 … 1 λ_{p} + 1 … λ_{1} + 1 0 … 0 0} = τ_{λ_{1}} … τ_{1} τ_{+} l
(2) : l ↦ l^{(2)} := \overline{0 0 … 0 λ_{p} … λ_{1} 0 … 0} = τ_{λ_{1}+m} … τ_{λ_{1}+1} l^{(1)} .

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 ℤ[x]:

(1) : < 0 > : up_{+} and
(2) : < m > : ∂_{1} … ∂_{m} up_{+} for m ∈ ℕ, where up_{+} means:

increase the exponents by 1 without increasing the number of variables.

Now the ∂_{m}’s introduce the new variables x_{m+1} and the beginning step is < 0 > (∅) := x_{1}^{0}.

A convenient way to compute this operator for a Grassmannian permutation π is to look at the sequence L(π)^{+} ≡ \overline{0 … 0 λ_{p} … λ_{1}}, i.e. L(π) without end zeros: if L(π)^{+} has m entries, then the operator in question is < (m − 1) … 1 0 > with k additional zeros between two consecutive numbers (left to right), if the entries on the corresponding places in L(π)^{+} increase by k.

Example 5.1. The operator corresponding to π = 12578346 ≈ \overline{0023300} is < 43002010 > and for π = 13524 ≈ \overline{01200} one has < 20100 >. In fact (calculating in ℤD_{∞}) gives: < 20100 > (∅) =< 2010 > (0) =< 201 > (1) = < 20 > (∂_{1}(2)) = < 20 > (10 + 01)= < 2 > (21 + 12)= ∂_{1}∂_{2}(32 + 23)= ∂_{1}(310 + 301 + 220 + 211 + 202)=210 + 120 + 201 + 111 + 021 + 111 + 102 + 012, which is X_{13524} = {21}^{3}.

Corollary 5.2. 2^{n} −n is the number of Grassmannian permutations in S_{n}, the number of symmetric functions in S_{n}, and also the number of Schur polynomials in S_{n}.

Proof. Denote by c_{n} the number of Grassmannian permutations in S_{n} \ S_{n−1}. Clearly c_{1} = c_{2} = 1 and in general c_{n} is the number of operators < a_{n−1} … a_{1}a_{0} > discussed above — note that each < a_{ν} > is a mapping from S_{ν} to S_{ν+1}. Since always a_{0} = 0 and for the other a_{ν} the only choice is zero or nonzero, there are 2^{n−1} possible operators. Moreover < (n − 1) … 1 0 >=< 0 > for all n. Hence c_{n} = 2^{n−1} − 1 for n ≥ 2 and ∑_{k=1}^{n} c_{k} = 2^{n} − n. The other assertions are consequences of Prop.3.1 g) and (S).

Proof. (S) By the above discussion it is enough to show that X_{L^{−1}(l)} = {λ}^{m} implies (1): X_{L^{−1}(l^{(1)})} = {1_{+}(λ)}^{m} and (2): X_{L^{−1}(l^{(2)})} = {λ 0}^{m+1}.

Recall the determinantal formula for Schur polynomials ([M3,Kr])

{λ}^{m} = V_{m}^{−1} det((x_{i}^{λ_{j}+m−j}))_{i,j=1,...,m}

where V_{m} := det((x_{i}^{m−j}))_{i,j=1,...,m} = ∏_{1≤i<j≤m}(x_{i}−x_{j}) is the Vandermonde determinant in m variables.

(1): {1_{+}(λ)}^{m} = V_{m}^{−1} det((x_{i}^{λ_{j}+1+m−j})) = V_{m}^{−1} det((x_{i}^{λ_{j}+m−j}))·x_{1} … x_{m} = x_{1} … x_{m}{λ}^{m} = 1_{+}^{↑}({λ}^{m}). Hence: X_{L^{−1}(l^{(1)})} = X_{L^{−1}(τ_{λ_{1}}...τ_{1} τ_{+} l)} = ∂_{m+1} … ∂_{m+λ_{1}}1_{+}^{↑}(X_{L^{−1}(l)}) = ∂_{m+1} … ∂_{m+λ_{1}}1_{+}^{↑}({λ}^{m}) · x_{m+1} … x_{m+λ_{1}} = 1_{+}^{↑}({λ}^{m}) = {1_{+}(λ)}^{m}, where the operator 1_{+}^{↑} acts in 1_{+}^{↑}(X_{L^{−1}(l)}) on all variables and in 1_{+}^{↑}({λ}^{m}) only on the first m variables.

(2) : X_{L^{−1}(l^{(2)})} = X_{L^{−1}(τ_{λ_{1}+m}...τ_{λ_{1}+1} l^{(1)})} = ∂_{1} … ∂_{m} X_{L^{−1}(l^{(1)})} =^{(1)}

∂_{1} … ∂_{m} {1_{+}(λ)}^{m} = ∂_{1} … ∂_{m} ( (x_{1} … x_{m}) {λ}^{m} ) =^{(a)}

{λ}^{m} + ∑_{ν=0}^{m−1} x_{m+1−ν} … x_{m+1}∂_{m−ν} … ∂_{m}{λ}^{m} =^{(b)} {λ 0}^{m+1}

(a): Let g be a symmetric function in x_{1}, …, x_{m} and 0 ≤ k ≤ m − 1; we claim :

∂_{m−k} … ∂_{m}((x_{1} … x_{m})g) = (x_{1} … x_{m−k−1})(g + ∑_{ν=0}^{k} x_{m+1−ν} … x_{m+1}∂_{m−ν} … ∂_{m}g)

Note that equality (a) is obtained by setting g = {λ}^{m} and k = m − 1 . We show the claim by induction over k.

An application of the product rule yields :

∂_{m}((x_{1} … x_{m}) g ) = (x_{1} … x_{m−1}) (g + x_{m+1}(∂_{m}g)) (case k = 0).

Assume now the claim to be true for some k, then:

∂_{m−k−1}∂_{m−k} … ∂_{m}((x_{1} … x_{m}) g ) =

x_{1} … x_{m−k−2}( g + ∑_{ν=0}^{k} x_{m+1−ν} … x_{m+1}∂_{m−ν} … ∂_{m}g ) +

x_{1} … x_{m−k−2}x_{m−k} [ ∂_{m−k−1} g + ∂_{m−k−1} ( ∑_{ν=0}^{k−1} x_{m+1−ν} … x_{m+1} ∂_{m−ν} … ∂_{m} g ) +

x_{m+1−k} … x_{m+1}∂_{m−k−1}∂_{m−k} … ∂_{m}g ] .

Since g is symmetric we note ∂_{m−k−1} g = 0 and for 0 ≤ ν ≤ k−1: ∂_{m−k−1}∂_{m−ν} … ∂_{m} g = ∂_{m−ν} … ∂_{m}∂_{m−k−1} g = 0. Therefore x_{m−k} = x_{(m+1)−(k+1)} completes the proof of the claim.

(b): With n := m + 1 (b) reads:

{λ}^{n−1} + ∑_{ν=0}^{n−2} x_{n−ν} … x_{n}∂_{n−1−ν} … ∂_{n−1}{λ}^{n−1} = {λ 0}^{n}

The following notations will be helpful: Π_{rs} := ∏_{ν=1}^{r}(x_{ν} − x_{s}) for r, s ≥ 1 and Π_{0s} := 1 for s ∈ ℕ; hence Π_{rs} = 0 for r ≥ s ; D_{i}h := ∂_{i}h + 2(σ_{i}(h))/(x_{i} − x_{i+1}) = (h + σ_{i}(h))/(x_{i} − x_{i+1}) for h ∈ ℤ[x]; and for all λ = (λ_{1}, …, λ_{m}) (as defined above) and canonical column vectors e_{k} =

(δ_{ik})_{i=1,...,n}

ê_{k} := det(( x_{i}^{λ_{j}+n−1−j} | e_{k} )) _{i=1,...,n; j=1,...,m} ,

i.e. the last column of the determinant is substituted by e_{k}. This makes sense, because the operations σ_{i}^{∗} and ∂_{i} applied to the determinant yield results independent of λ:

ê_{i} ∘ σ_{i} = −ê_{i+1}, ê_{i+1} ∘ σ_{i} = −ê_{i} and ê_{k} ∘ σ_{i} = −ê_{k} for k ≠ i, i + 1
∂_{i}ê_{i} = (ê_{i} + ê_{i+1}) / (x_{i} − x_{i+1}) = ∂_{i}ê_{i+1} and
∂_{i}ê_{k} = 2ê_{k} / (x_{i} − x_{i+1}) for k ≠ i, i + 1 .

Moreover

∂_{i} V_{n} = 2V_{n} / (x_{i} − x_{i+1}) for 1 ≤ i ≤ n − 1 and σ_{i}(V_{n}) = −V_{n}

and for 1 ≤ j < k ≤ n :

∂_{i}(x_{i} − x_{i+1}) = 2, ∂_{i}(x_{j} − x_{i}) = −1 = ∂_{i}(x_{i+1} − x_{k})
∂_{i}(x_{i} − x_{k}) = 1 = ∂_{i}(x_{j} − x_{i+1}) for k > i + 1 and j < i .

Now

{λ}^{n−1} = V_{n−1}^{−1} det(( x_{i}^{λ_{j}+n−1−j} | e_{k} ))_{i,j=1,...,n−1} = V_{n−1}^{−1}ê_{n} = V_{n}^{−1}Π_{n−1 n}ê_{n} .

Hence a proof of (b) demands the computation of ∂_{ν} … ∂_{n−1}(V_{n}^{−1}Π_{n−1 n}ê_{n}) for 1 ≤ ν ≤ n − 1. Since by the quotient rule

∂_{i}(V_{n}^{−1}h) = V_{n}^{−1} D_{i}h for all h ∈ ℤ[x] ,

it is enough to compute the expressions D_{ν} … D_{n−1}(Π_{n−1 n}ê_{n}) for 1 ≤ ν ≤ n − 1. Let h be the matrix of column vectors h_{ν} ≡ (h_{ν}^{k})_{k∈ℕ}, with

h_{ν}^{k} := Π_{ν−1 k}ê_{k} for ν, k ∈ ℕ .

Clearly h_{ν}^{k} = 0 for k < ν , i.e. h is a lower triangular matrix. Using the above notations and results one computes for n ≥ 2 and 2 ≤ s ≤ n − 1

D_{n−1}h_{n}^{n} = h_{n−1}^{n} + h_{n−1}^{n−1} and D_{s−1}h_{s}^{n} = h_{s−1}^{n} .

Therefore D_{ν−1}h_{ν}^{k} = 0, if k < ν, = h_{ν−1}^{ν} + h_{ν−1}^{ν−1}, if k = ν, and = h_{ν−1}^{k}, if k > ν, which can be summarized as

H_{ν n} := ∑_{k=1}^{n} h_{ν}^{k} ⟹ D_{ν−1} H_{ν n} = H_{ν−1 n} for 2 ≤ ν ≤ n .

Note that H_{n n} = h_{n}^{n}; consequently:

h_{n}^{n} + ∑_{ν=0}^{n−2} x_{n−ν} … x_{n}D_{n−1−ν} … D_{n−1} h_{n}^{n} = H_{n n} + ∑_{ν=1}^{n−1} x_{ν+1} … x_{n} H_{ν n} .

We show next, that for all k, 1 ≤ k ≤ n:

x_{1} … x_{k−1}x_{k+1} … x_{n} ê_{k} = h_{n}^{k} + ∑_{ν=1}^{n−1} x_{ν+1} … x_{n} h_{ν}^{k} .

Elimination of ê_{k} from h_{...}^{k}, application of Π_{rs} = 0 for r ≥ s and division by x_{k+1} … x_{n} for 1 ≤ k ≤ n − 1 yields the following equivalent formula, which is independent of λ and n:

x_{1} … x_{k−1} = Π_{k−1 k} + ∑_{ν=1}^{k−1} x_{ν+1} … x_{k} Π_{ν−1 k} for k ∈ ℕ .

The r.h.s. of the last formula equals

x_{2} … x_{k} +[ (x_{2} −x_{k}) … (x_{k−1} −x_{k})+∑_{ν=2}^{k−1} x_{ν+1} … x_{k} (x_{2} −x_{k}) … (x_{ν−1} −x_{k}) ] (x_{1} −x_{k})

= x_{2} … x_{k} + 1_{+}^{↓} [ (x_{1} − x_{k−1}) … (x_{k−2} − x_{k−1}) +

∑_{ν=1}^{k−2} x_{ν+1} … x_{k−1} (x_{1} − x_{k−1}) … (x_{ν−1} − x_{k−1}) ] (x_{1} − x_{k}).

By induction over k this is : x_{2} … x_{k} + 1_{+}^{↓} (x_{1} … x_{k−2}) (x_{1} − x_{k}) = x_{2} … x_{k} + x_{2} … x_{k−1}(x_{1} − x_{k}) = x_{2} … x_{k−1} (x_{k} + x_{1} − x_{k}) = x_{1} … x_{k−1}.

In summary we have, that the l.h.s. of (b) equals

V_{n}^{−1} det(( x_{i}^{λ_{j}+n−1−j} | ∗ )) _{i=1,...,n; j=1,...,n−1} ,

where the last column is ∗ = ( ∏_{l=1 ;l≠i}^{n} x_{l} )_{i=1,...,n} . Expansion with respect to the last column then yields : V_{n}^{−1} det(( x_{i}^{λ_{j}+n−j} )) _{i,j=1,...,n} = {λ 0}^{n} .

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(π) = \overline{0 … 0 λ_{p} … λ_{1} 0 … 0}, l^{(1)} = \overline{1 … 1 λ_{p} + 1 … λ_{1} + 1 0 … 0 0} and l^{(2)} = \overline{0 0 … 0 λ_{p} … λ_{1} 0 … 0} (λ = λ_{1} … λ_{m} as always in this section) .

Corollary 5.3. Using the above notations one has: X_{π} = x_{m+1} … x_{m+q} {1_{+}λ}^{m} for L(π) = \overline{1 … 1 λ_{p} + 1 … λ_{1} + 1 1 … 1 0 … 0} with q one’s on the right;

let l′ := \overline{1 … 1 λ_{p} + 1 … λ_{s+1} + 1 0 λ_{s} … λ_{1} 0 … 0}, i.e. the first zero is on place r = m + 1 − s = n − s, 1 ≤ r ≤ m + 1, then

X_{L^{−1}(l′)} = V_{n}^{−1} det(( x_{i}^{λ_{j}+n−1−j} | ∗ )) _{i=1,...,n; j=1,...,n−1} ,

where the last column ∗ is: ∗ = ( Π_{r−1 i} ∏_{l=1 ;l≠i}^{n} x_{l} )_{i=1,...,n} .

Note that l′ = l^{(2)} for r = 1 and l′ = l^{(1)} for r = n .

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) — :

X_{L^{−1}(l′)} = X_{L^{−1}(τ_{λ_{1}+s}...τ_{λ_{1}+1} l^{(1)})} = ∂_{m−s+1} … ∂_{m} X_{L^{−1}(l^{(1)})}
= ∂_{m−s+1} … ∂_{m} ( (x_{1} … x_{m}) {λ}^{m} )
= (x_{1} … x_{n−s−1}) {λ}^{n−1} + ∑_{ν=0}^{s−1} x_{n−ν} … x_{n}∂_{n−1−ν} … ∂_{n−1}{λ}^{n−1}

= (x_{1} … x_{n−s−1}) ( H_{n n} + ∑_{ν=n−s}^{n−1} x_{ν+1} … x_{n} H_{ν n} )

The k^{th} component of this expression equals

(x_{1} … x_{r−1}) ( Π_{r+s−1 k} + ∑_{ν=r}^{r+s−1} x_{ν+1} … x_{r+s} Π_{ν−1 k} ) ê_{k}

= (x_{1} … x_{r−1}) (x_{k+1} … x_{n}) ( Π_{k−1 k} + ∑_{ν=r}^{k−1} x_{ν+1} … x_{k} Π_{ν−1 k} ) ê_{k}

= (x_{1} … x_{r−1}) (x_{k+1} … x_{n}) ( Π_{r−1 k} x_{r} … x_{k−1} ) ê_{k} = Π_{r−1 k} ∏_{l=1 ;l≠k}^{n} x_{l}

Example 5.4. Consider l^{(1)} = \overline{23000}, l′ = \overline{20200} and l^{(2)} = \overline{01200} :

X_{L^{−1}(l^{(1)})} = \frac{1}{V_{3}} | \begin{matrix}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{matrix} | = \frac{1}{V_{2}} | \begin{matrix}x_{1}^{4} & x_{1}^{2} \\ x_{2}^{4} & x_{2}^{2} \end{matrix} | = \{3 2\}^{2} ,

X_{L^{−1}(l′)} = \frac{1}{V_{3}} | \begin{matrix}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{matrix} | , and

X_{L^{−1}(l^{(2)})} = \frac{1}{V_{3}} | \begin{matrix}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{matrix} | = \frac{1}{V_{3}} | \begin{matrix}x_{1}^{4} & x_{1}^{2} & 1 \\ x_{2}^{4} & x_{2}^{2} & 1 \\ x_{3}^{4} & x_{3}^{2} & 1 \end{matrix} | = \{2 1\}^{3}

6. 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 ℤ[x] into Schubert polynomials and a general product formula for the operators ∂_{π}.

Proposition 6.1. (Expansion Formula) Let η : ℤ[x] ⟶ ℤ, f ↦ f(0) be the augmentation map on ℤ[x]; then for all f ∈ ℤ[x] one has

f = ∑_{π} η(∂_{π}f) X_{π} .

Proof. Since the X_{π} form a basis of ℤ[x] and η, ∂_{π} are linear mappings, one has to investigate only the case f = X_{ρ}; but ∑_{π} η(∂_{π}X_{ρ}) X_{π} = X_{ρ}, because η(∂_{π}X_{ρ}) = δ_{π,ρ}: by Prop.3.1 d) one has ∂_{π}X_{ρ} = X_{ρ π^{−1}}, if l(ρ π^{−1}) = l(ρ) − l(π), and by Prop.3.1 b) η(X_{π}) = δ_{π,id}.

Proposition 6.2. (General Product Rule) [M1,(2.5)] Let π be a permutation of length p and b a reduced subword of a ≡ a_{1} … a_{p} ∈ R(π); let further φ(a, b) denote the expression σ_{a_{1}} … σ_{a_{p}}, where σ_{a_{ν}} is replaced by ∂_{a_{ν}} for ν ∈ {1, …, p} iff a_{ν} is not contained in b. Then for all μ, π we define the relative operators

∂_{π/μ} := μ^{−1} ∑ φ(a, b) ,

where the sum is taken over all subwords b of a fixed a ∈ R(π) such that b ∈ R(μ). These operators are ℤ-linear of degree l(μ) − l(π) ≤ 0, independent of the choice of a and nonzero only for μ ≤_{B} π (Bruhat order). Now for all f, g ∈ ℤ[x] the general product rule reads:

∂_{π}(fg) = ∑_{μ≤_{B}π} μ(∂_{π/μ}f) · ∂_{μ}g .

Proof. By the subword property (cf. Sec.1) the operators ∂_{π/μ} are nonzero only for μ ≤_{B} π and independent of the choice of a; clearly they are ℤ-linear of degree l(μ) − l(π) ≤ 0 too.

We show the general product rule by induction over p = l(π). For π = id the assertion is trivial. Assume now that it is true for all π of length p and that π′ is some permutation of length p + 1; then for fixed a = a_{1} … a_{p} a_{p+1} ∈ R(π′) let k = a_{p+1} and π be the permutation represented by a_{1} … a_{p}. Using Prop.3.1 c), the product rule and the linearity of ∂_{π} one computes

∂_{π′}(fg) = ∂_{π} [ ∂_{k}(fg) ] = ∂_{π} [ ( ∂_{k}(f) ) g + σ_{k}(f) (∂_{k}(g) ) ]

= ∑_{μ≤_{B}π} μ(∂_{π/μ}∂_{k}f) · (∂_{μ}g) + ∑_{μ≤_{B}π} μ(∂_{π/μ}σ_{k}(f)) · (∂_{μ}∂_{k}g) ,

which should be equal to ∑_{μ′≤_{B}π′} μ′(∂_{π′/μ′}f) · ∂_{μ′}g. But using the subword property again we see that for μ ≤_{B} π and b ∈ R(π) two cases are to be distinguished: 1^{st}) k = a_{p+1} not contained in b, then μ′ = μ, ∂_{π′/μ′} = ∂_{π/μ}∂_{k} gives the first summand, and 2^{nd}) k = a_{p+1} contained in b, then μ′ = μσ_{k}, ∂_{π′/μ′} = σ_{k}^{−1}∂_{π/μ}σ_{k} gives the second summand.

Corollary 6.3. Let π ∈ S_{∞}, f = ∑ α_{i}x_{i} ∈ ℤ[x], g ∈ ℤ[x] and J_{−1}(π) as in Def.2.2; then

∂_{π}(fg) = π(f)(∂_{π}g) + ∑_{(i,j)∈J_{−1}(π)}(α_{i} − α_{j}) ∂_{π∘(i,j)}g.

Proof. The expressions ∂_{π/μ}f are nonzero only for −1 ≤ l(μ) − l(π) ≤ 0, i.e. μ = π or ‘μ ⪯_{B} π’ (π covers μ in Bruhat order) ⇔ μ = π ∘ (i, j), (i, j) ∈ J_{−1}(π) by Prop.2.3. Therefore either ∂_{π /π} = π^{−1} π = id or , if μ ⪯_{B} π, there exists ν ∈ {1, …, p} such that for a = a_{1} … a_{p} ∈ R(π) one has ∂_{π/μ} = a_{p} … a_{1} a_{1} … a_{ν−1} ∂_{a_{ν}} a_{ν+1} … a_{p} = a_{p} … a_{ν+1} ∂_{a_{ν}} a_{ν+1} … a_{p} ≡ ρ^{−1} ∂_{a_{ν}} ρ. Then it is easy to calculate that for i := ρ^{−1}(a_{ν}) and j := ρ^{−1}(a_{ν} + 1) one has ρ^{−1} ∂_{a_{ν}} ρ = (x_{i} − x_{j})^{−1}(id − (i, j)) ≡ ∂_{i,j} (, i.e. ∂_{i,i+1} = ∂_{i} ), which completes the proof.

Theorem 6.4. [M1,(4.10)] Let π ∈ S_{∞}, f = ∑ α_{i}x_{i} ∈ ℤ[x] and J_{1}(π) as in Def.2.2; then

fX_{π} = ∑_{(i,j)∈J_{1}(π)}(α_{i} − α_{j}) X_{π∘(i,j)} .

Proof. f X_{π} = ∑_{ρ} η(∂_{ρ}(fX_{π}))X_{ρ} by Prop.6.1 and

∂_{ρ}(fX_{π}) = π(f)(∂_{ρ}X_{π}) + ∑_{(i,j)∈J_{−1}(ρ)}(α_{i} − α_{j}) ∂_{ρ∘(i,j)} X_{π} .

Since η(π(f)) = 0 for all choices of the α_{i} and η(∂_{ρ∘(i,j)} X_{π}) = δ_{ρ∘(i,j),π} by Prop.6.1 and its proof, we only need to observe that

[ρ ∘ (i, j) = π and (i, j) ∈ J_{−1}(ρ)] ⇔ [ρ = π ∘ (i, j) and (i, j) ∈ J_{1}(π)]

in order to finish the proof by the calculation:

fX_{π} = ∑_{ρ} ∑_{(i,j)∈J_{1}(π)}(α_{i} − α_{j}) δ_{ρ,π∘(i,j)} X_{ρ} = ∑_{(i,j)∈J_{1}(π)}(α_{i} − α_{j}) X_{π∘(i,j)} .

Corollary 6.5. (Monk-Pieri) ([Mo]) Let π ∈ S_{∞}, k ∈ ℕ and J_{1}(k, π) := { (i, j) | 1 ≤ i ≤ k < j, πi < πj, ♯{ν|i < ν < j, πi < πν < πj} = 0 }, then

X_{σ_{k}} X_{π} = ∑_{(i,j)∈J_{1}(k,π)} X_{π∘(i,j)} .

Proof. By Prop.3.1 h) f = X_{σ_{k}} means α_{1} = … α_{k} = 1, α_{k+1} = α_{k+2} = ⋯ = 0, hence α_{i} − α_{j} = 1, if 1 ≤ i ≤ k < j, and zero otherwise.

Corollary 6.6. [KKL, (3.1) ] Let π ∈ S_{∞}, k ∈ ℕ and J_{1}^{>k}(π), J_{1}^{<k}(π) as in Def.2.2; then

x_{k} X_{π} = ∑_{j∈J_{1}^{>k}(π)} X_{π∘(k,j)} − ∑_{j∈J_{1}^{<k}(π)} X_{π∘(k,j)} .

Proof. By Cor. 6.5 one has:

x_{k} X_{π} = (X_{σ_{k}} − X_{σ_{k−1}}) X_{π} = ∑_{(r,s)∈J_{1}(k,π)} X_{π∘(r,s)} − ∑_{(r,s)∈J_{1}(k−1,π)} X_{π∘(r,s)} .

The terms with 1 ≤ r ≤ k − 1 and k < s in the two sums cancel; in the first sum only terms with r = k or s ∈ J_{1}^{>k}(π) survive, in the second sum only terms with s = k or r ∈ J_{1}^{<k}(π), proving the assertion.

Remark 6.7. (cf. [KKL]) Cor.6.6 has been the starting point for the “transition formula” of Lascaux and Schü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.

Corollary 6.8.

a) X_{π} = \frac{1}{x_{k}} ( ∑_{j∈J_{1}^{>k}(π)} X_{π∘(k,j)} ) , if J_{1}^{<k}(π) = ∅.

b) Let π ∈ S_{n} and πk = 2, π(k + 1) = 1 for some k with 1 ≤ k ≤ n − 1, then ∂_{k}X_{π} = X_{π}/x_{k}.

Proof. a) is immediate from Cor.6.6 . For b) observe that under the assumptions made one has J_{1}^{<k}(πσ_{k}) = ∅ and J_{1}^{>k}(πσ_{k}) = {k + 1}. This together with Prop.3.1 e) gives

∂_{k} X_{π} = X_{πσ_{k}} = \frac{1}{x_{k}} X_{πσ_{k}σ_{k}} = \frac{1}{x_{k}} X_{π}.

Of course it may happen that there is more than one k for given π, such that J_{1}^{<k}(π) = ∅ for Example: let π = 2143 ∈ S_{4}, then X_{π} = x_{1}^{2} + x_{1}x_{2} + x_{1}x_{3}, and for k = 1 one has X_{π} = 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_{π} = 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 π ≠ ω_{n} there exists at least one k with J_{1}^{<k}(π) = ∅, namely

k = the first ascend of π, i.e. π1 > ⋯ > πk < π(k + 1) < ….

This gives us the possibility to compute the Schubert polynomial X_{π} for every π ∈ S_{n} recursively from X_{ω_{n}} = x_{1}^{n−1} … x_{n}^{0} without using divided differences. (Clearly it is convenient to choose for given π the smallest possible n, i.e. the greatest n, such that πn ≠ n).

The advantage of avoiding divided differences is, that the determination of the set J_{1}^{<k}(π) for the first ascend k in π seems slightly easier than handling the formula for the ∂_{k}, and — more importantly — that the use of an operator ∂_{π}, 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 S_{n}; in this case one begins with X_{ω_{n}} and works down through all levels of the weak order of S_{n}: suppose the sets S_{n}^{p} := {π ∈ S_{n} | l(π) = p} and S_{n}^{p} := {X_{π} ∈ S_{n} | π ∈ S_{n}^{p}} for some p with 1 ≤ p ≤ n are already know, then one finds S_{n}^{p−1} = {πσ_{k} | π ∈ S_{n}^{p}, πk > π(k+1)} and every Schubert polynomial in the set S_{n}^{p−1} can be computed according to Cor.6.8 a).

In the case of a computation of a single Schubert polynomial X_{π} (π ∈ S_{n}) one should build up an ‘ad hoc set’ of already known Schubert polynomials initialized as {X_{ω_{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.

References

[Hi] H. Hiller, “Geometry of Coxeter groups”, Pitman, Boston, 1982.

[Hu] J.E. Humphreys, “Reflection groups and Coxeter groups”, Cambridge University Press, Cambridge, 1990. [K] A. Kerber, “Algebraic combinatorics via finite group actions”, BI Wissenschaftsverlag, Mannheim 1991.

[KKL] A. Kerber, A. Kohnert, A. Lascoux, SYMMETRICA, an object oriented computeralgebra system for the symmetric group, J. Symbolic Computation 14 (1992), 195-203.

[Kr] V. Krishnamurthy, “Combinatorics: Theory and Applications”, Ellis Horwood, Chichester 1986.

[LS] A. Lascoux, M.-P. Schützenberger, Décompositions dans l’algébre des différences divisées, discrete math. 99 (1992), 165-179.

[M1] I.G. Macdonald, Schubert polynomials, in: A.D. Kendwell (ed.), “Surveys in Combinatorics”, London Math. Soc. Lec. Notes Ser. 166, 73 - 99, Cambridge University Press, Cambridge 1991.

[M2] I.G. Macdonald, “Notes on Schubert polynomials”, Publications du L.A.C.I.M., vol. 6, Université du Québec, Montréal, 1991.

[M3] I.G. Macdonald, “Symmetric functions and Hall polynomials”, Clarendon Press, Oxford 1979.

[Mo] D. Monk, The geometry of flag manifolds, Proc. London Math. Soc. (3) 9 (1959), 253-286.

[Sb] H. Schubert, “Kalkül der Abzählenden Geometrie” (Reprint), Springer, Berlin, 1979.

[W] R. Winkel, Diagram rules for the generation of Schubert polynomials, preprint (1995/97).

Institut für Reine und Angewandte Mathematik, RWTH Aachen, D-52056 Aachen, Germany, papers/preprints: http://www.iram.rwth-aachen.de/ ∼winkel/

  E-mail address: winkel@iram.rwth-aachen.de