Séminaire Lotharingien de Combinatoire 48 (2003), Article B48f

A DERIVATION OF KOHNERT’S ALGORITHM FROM MONK’S RULE

RUDOLF WINKEL

Abstract. Kohnert’s algorithm for the generation of Schubert polynomials is derived from Monk’s rule for the multiplication of Schubert polynomials.

1. Introduction

The theory of Schubert polynomials is a beautiful blend of geometric, algebraic and combinatorial ideas: on one hand Schubert polynomials faithfully represent the cohomology calculus of Schubert varieties of flag manifolds; on the other hand Schubert polynomials are a generalization of the classical Schur polynomials and can be studied in a purely algebraic and combinatorial setting. The primary references for Schubert calculus and Schubert polynomials are the papers of Borel [Bo], Bernstein, Gelfand, and Gelfand [BGG], Demazure [D1,D2] and Lascoux and Schützenberger [LS] (see also [L]). Introductory and comprehensive accounts of both the “classical” theory and newer research are [F,FP] (for the algebraic-geometrical side) and [M1,M2,W3] (for the algebraic-combinatorial side).

The purpose of the present paper is to give a short and natural proof of a combinatorial rule for the generation of Schubert polynomials which was conjectured first by Kohnert in his Ph. D. dissertation [K] and subsequently proven in [W1]. The proof in [W1] has two advantages:

• It is the first and only one so far.

• It incorporates as an intermediary step the proof of two other (more complicated) rules for the generation of Schubert polynomials, namely the rules given by Bergeron [B] and Magyar [Ma].

The proof in [W1] has also two disadvantages:

• It is the first and only one so far — and first proofs are rarely the most simple and elegant ones.

• It incorporates as an intermediary step the proof of two other (more complicated) rules for the generation of Schubert polynomials, namely the rules given by Bergeron [B] and Magyar [Ma] — and (as we will make more precise below) these two rules do not provide a natural context for the proof of Kohnert’s algorithm thus severely complicating matters.

Date: November 29th, 2000; revised: March 2nd and November 21th, 2002.

2000 Mathematics Subject Classification. 05E05, 05E10, 05E15, 14M15.

Subsequently in this introduction we collect the basic necessary information about Schubert polynomials, describe Kohnert’s algorithm and introduce some useful notation. In Section 2 the proof is outlined and illustrated in two simple special cases, whereas Section 3 deals with the general case.

To every permutation π on numbers 1, …, n contained in the symmetric group S_{n} one can associate a multivariate polynomial with non-negative integer coefficients X_{π} ∈ ℤ[x_{1}, …, x_{n}] as follows: Let ω_{n} := n (n − 1) … 1 ∈ S_{n} be the permutation of maximal length, i.e., with the maximum number of inversions. Every other permutation π ∈ S_{n} can then be reached from ω_{n} by going down in (right) weak Bruhat order where π′ covers π in weak Bruhat order, if π′ = π ∘ σ_{k} with σ_{k} the elementary transposition (k, k + 1) and π(k) < π(k + 1). In other words: π results from π′ by removing the inversion of numbers on adjacent places k and k + 1. If for all such pairs π, π′ with π′ = π ∘ σ_{k} one defines recursively X_{π} := ∂_{k}X_{π′} where ∂_{k} is the divided difference operator acting on the variables x_{k} and x_{k+1} and if one starts at X_{ω_{n}} := x_{1}^{n−1}x_{n}^{n−2} … x_{n−1} then this leads to well defined polynomials X_{π} for all π ∈ S_{n}, the Schubert polynomials. It is interesting to note that this (classical) approach to Schubert polynomials by divided difference operators reflects the relative geometric positions of Schubert varieties in a flag manifold where one variety lies on the boundary of another.

Alternatively, one can compute the Schubert polynomials without divided differences by going down from ω_{n} in (right strong) Bruhat order where π′ covers π in Bruhat order, if π′ = π ∘ (k, j) and j ∈ J^{>k}(π) for any fixed k with J^{>k}(π) :=

(1) {j | k < j, π(k) < π(j), and |{ν | k < ν < j, π(k) < π(ν) < π(j)}| = 0 } .

Then for every π ≠ ω_{n} in S_{n} and k := π^{−1}(1) one has

(2)  X_{π} = \frac{1}{x_{k}} ( ∑_{j∈J^{>k}(π)} X_{π∘(k,j)}) ,

i.e., if k is chosen such that π(k) = 1 then x_{k}X_{π} equals the sum of X_{π′} where π′ runs through certain π′ covering π in Bruhat order. This formula has been noted first in [W2, Sec. 6] as a simple consequence of Monk’s rule [Mo] for the multiplication of an arbitrary Schubert polynomial by any of the polynomials X_{σ_{k}} = x_{1} + ⋯ + x_{k}. Since (2) is essential for our new proof of Kohnert’s algorithm we explain this point a bit more thoroughly: Monk’s rule is

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

where J(k, π) :=

{(i, j) | i ≤ k < j, π(i) < π(j), and |{ν | i < ν < j, π(i) < π(ν) < π(j)}| = 0 } .

(Concise and simple proofs of Monk’s rule can be found in each of [M1,M2,W2,W3].) From this formula one easily derives that the product x_{k}X_{π} is of the form “sum on the r.h.s. of (2) minus a similar sum”; but the subtracted sum is zero, if for example k = π^{−1}(1) (see [W2] or [W3] for details).

Note that formula (2) relates the calculation of Schubert polynomials directly to their multiplicative properties, respectively, the intersection calculus of Schubert varieties.

It is time now to describe the diagram rule for the generation of Schubert polynomials previously conjectured by Kohnert [K].

A (box) diagram is a finite collection of unit squares or boxes with vertices in the integer lattice ℤ × ℤ; the diagram D(π) of a permutation π ∈ S_{n} is the diagram that originates from the set of boxes {[i, j] | 1 ≤ i, j ≤ n} by cancellation of the ‘hooks’

{[π(j), j′] | j′ ≥ j} ∪ {[i′, j] | i′ ≥ π(j)}

for j = 1, …, n. For example, if π = 263154 ∈ S_{6}, then D(π) =

· · · · · ·^{1}^{2}^{3}^{4}^{5}^{6} _{1} _{2} _{3} _{4} _{5} _{6}

where we have added hooks in the positions (π(j), j), row numbers i = 1, …, 6 at the left and column numbers j = 1, …, 6 at the bottom of the diagram. Kohnert’s algorithm says that all monomials occurring in a Schubert polynomial X_{π} can be found by looking at the set K(D(π)) of box diagrams derivable from D(π) by (repeated) application of K-moves:

Definition 1. (K-moves) Let [i, j] ∈ D with {(i′, j) | i′ > i} ∩ D = ∅, i.e., there is no box above [i, j] in D, and assume that

M_{D}(i, j) := {(i, j′) | j′ < j, [i, j′] ∉ D} ≠ ∅ .

Then [i, j] is allowed to move to the position in M_{D}(i, j) with the greatest column number j′, i.e., the closest empty position left to [i, j] in row i of D. A K-move of the box [i, j] will be called free, if (i, j − 1) ∈ M_{D}(i, j), and a tunnelling move (through the boxes [i, j − 1], [i, j − 2], ⋯ ∈ D) otherwise.

For any diagram D let D^{[j,j′]}, D_{[i,i′]} and D_{[i,i′]}^{[j,j′]} denote the sub diagrams (“minors”) of D that contain only the boxes in the intervals of columns [j, j′], rows [i, i′] and in both columns [j, j′] and rows [i, i′], respectively. A special case of this notation can be used to associate a monomial to a diagram D by x^{D} := x_{1}^{β_{1}}x_{2}^{β_{2}} … where β_{j} := |D^{[j]}| and D^{[j]} := D^{[j,j]}. The purpose of the present paper is to give a simple and natural proof of

Theorem 2. For any natural number n ∈ ℕ and permutation π ∈ S_{n} let K := K(D(π)) be the set of diagrams derivable from D(π) by repeated application of K-moves. Then

X_{π} = ∑_{D∈K} x^{D} .

Example 3. For the permutation π = 31542 one computes algebraically X_{π} = x_{1}^{2}x_{3}^{2}x_{4}+ x_{1}^{2}x_{2}x_{3}x_{4} + x_{1}^{3}x_{3}x_{4} + x_{1}^{2}x_{2}^{2}x_{4} + x_{1}^{2}x_{2}x_{3}^{2} + x_{1}^{3}x_{2}x_{4} + x_{1}^{2}x_{2}^{2}x_{3} + x_{1}^{3}x_{2}x_{3}. And indeed, the set K for this permutation contains all elements of the following poset:

[figure: r; r; r; r; r; r; r]

where D(π) is the top element and all K-derived diagrams are ordered such that D′ covers D, if D originates from D′ by an irreducible (or minimal) K-move. We have used straight lines for the free K-moves and a dotted line for the tunnelling move. More information about these posets can be found in [W1] where they form an integral part of the proof. Here we have exhibited the partial order only as a means to make the process of successive generation of diagrams more transparent. Note that the two boxes in the first column of D(π) never move; such boxes are called inertial. (Why certain boxes are marked with an ‘r’ will become apparent later in Section 3.) □

A “natural” proof of Kohnert’s algorithm is one that “explains” the definition of K-moves and in particular the occurrence of tunnelling moves. Since Schur polynomials are special Schubert polynomials, the definition of K-moves must include moves which guarantee the realization of all monomials of Schur polynomials by box diagrams. But as already observed and proven by Kohnert in [K] the free K-moves are in fact in natural correspondence to the columnstrict numbering of semistandard Young tableaux which are used in the well known combinatorial definition of Schur polynomials (see also [W1, Section 4]). On the other hand free K-moves alone are obviously not sufficient to generate the monomials of general Schubert polynomials. Therefore Bergeron has included in his rule certain “backward” moves, i.e., moves of boxes from the left to the right; these backward moves were used to model in a combinatorial fashion the divided differences used in the classical approach to Schubert polynomials. Similarly Magyar’s rule, which is a simplification of Bergeron’s rule, has the divided difference approach as its starting point (cf. [W1, Section5]). Whereas the proof of these rules in [W1] with the help of the poset structure on the sets K(D(π)) and a suitable recursion argument is relatively transparent and easy, the subsequent derivation of Kohnert’s rule is done by an exhaustive study of cases which establishes correctness without leading to a deeper understanding.

In the next section we will see that the generation of Schubert polynomials via formula (2) (without divided differences) makes the use of tunnelling moves virtually inevitable thereby suggesting the possibility of finding analogs of Kohnert’s rule in more general settings: since the symmetric groups are Coxeter (and Weyl) groups of type A, one could use the generalization of Monk’s (or ”Pieri’s”) rule as the starting point for such an investigation.

2. Outline of the proof and two special examples

The proof proceeds by induction over n and k. It is not hard to verify Theorem 2 for n = 1, 2 and 3 and as induction hypothesis we assume that it is true for all permutations π ∈ S_{n−1}. Setting

(3)  S_{n,k} := {π ∈ S_{n} | π(k) = 1}

one can define a bijection between S_{n−1} and S_{n,n} with the help of the mapping

(4)  π ↦ 1_{+}(π) 1 := (π(1) + 1) … (π(n − 1) + 1) 1 .

But because the diagram D(1_{+}(π) 1)_{[2,n]} has the same shape as D(π) and the n − 1 boxes in the row D(1_{+}(π) 1)_{[1]} are inertial, the formula

(5)  X_{1_{+}(π) 1} = x_{1} · · · · · x_{n−1} X_{π}

from [W2, Prop. 3.3] (or [W3, Prop. 4.3.3]) shows that Theorem 2 is valid also for all π ∈ S_{n,n}.

Subsequently we will assume that π is contained in some S_{n,k} with 1 ≤ k < n and that the assertion of Theorem 2 is true for all π′ ∈ S_{n,n}, …, S_{n,k+1}. Moreover, let

(6)  J^{>k}(π) = {k_{0}, k_{1}, …, k_{q}} with k + 1 = k_{0} < k_{1} < ⋯ < k_{q} ≤ n

and for ν = 0, …, q set π_{ν} := π ∘ (k, k_{ν}), B_{ν} := D(π_{ν}), K_{ν} := K(B_{ν}) and i_{ν} := π(k_{ν}). Recall also that K := K(D(π)).

In view of formula (2) the following steps will constitute a proof of Theorem 2:

(1) There is a bijection between the sets K_{ν} and certain subsets H_{ν} of K that is faithful with respect to columns. By this we mean that the image D ∈ H_{ν} K of some diagram B ∈ K_{ν} has the same number of boxes in every column as B except for column k where |D^{[k]}| = |B^{[k]} − 1|.

(2) H_{ν} ∩ H_{ν′} = ∅, if ν ≠ ν′.

(3) K ⊂ ⋃_{ν=0}^{q} H_{ν}.

Since K ⊃ ⋃_{ν=0}^{q} H_{ν} by 1, points 2 and 3 show that K = ⨄_{ν=0}^{q} H_{ν}; and since the bijections of step 1 are faithful w.r.t. columns, one gets the desired conclusion by induction:

X_{π} =^{(2)} \frac{1}{x_{k}} ∑_{ν=0}^{q} X_{π_{ν}} = \frac{1}{x_{k}} ∑_{ν=0}^{q} ∑_{B∈K_{ν}} x^{B} = ∑_{ν=0}^{q} ∑_{D∈H_{ν}} x^{D} = ∑_{D∈K} x^{D} .

To carry out the above steps we compare first of all the diagrams of π and any of the π_{ν}:

D(π) =  ·  ·^{s} ^{s} ^{s} ^{t}^{t}^{1}^{i_{ν}} _{k}  _{k_{ν}}  B_{ν} := D(π_{ν}) =  · · s s s^{t}^{t}^{1}^{i_{ν}} _{k}  _{k_{ν}}

The diagrams of D(π) and B_{ν} are identical outside of the array of boxes formed by the intersection of rows 1, …, i_{ν} with columns k, …, k_{ν} where the dashed rectangle is completely filled with boxes except for possibly empty rows on levels π(1), …, π(k −1). (These levels are of course also empty in the columns containing the t-boxes for both D(π) and B_{ν}.) Note the additional box [1, k] ∈ B_{ν} corresponds to the fact that π_{ν} covers π in Bruhat order thereby having exactly one more inversion than π.

The diagram in K that corresponds faithfully w.r.t. columns and “naturally”, i.e., with a minimal number of differences to B_{ν}, is the diagram D_{ν} that results from D(π) by “swapping” the boxes (marked with a ‘t’) in column k_{ν} to column k. By the recursiveness inherent in our induction this “swapping” is therefore a necessary supplement of the free moves. In fact, it is a sequence of valid tunnelling moves in the sense of Definition 1, because column k_{ν} is empty above level i_{ν} and because of the structure of the dashed rectangle.

D_{ν} =  ·  ·^{s} ^{s} ^{s}^{t}^{t}^{1}^{i_{ν}} _{k}  _{k_{ν}}

In Example 3 we have introduced already the notion of inertial boxes. They were defined as the boxes in D(π) that can never K-move. Equivalently, they could be defined as the boxes that are not in the upper right area included by any of the hooks that were removed for the generation of the diagram D(π). Clearly, the inertial boxes form a ”partition” (with respect to columns or rows) in the lower left corner of D(π) since there are no empty positions available. All other boxes can move (column wise from left to right) at least one position to the left. Below we will use the notion of inertial boxes in a slightly more general form, namely, a box is called inertial in an arbitrary diagram D, if it can not K-move relative to this diagram, and movable otherwise. Therefore the set of inertial boxes increases monotonically with every K-move executed on a diagram until all boxes are inertial (compare again the poset of Example 3). Furthermore, every rectangle of positions in D formed by the origin as lower left and an inertial box as upper right corner contains only inertial boxes (or empty positions).

Observe now that the s-boxes of B_{ν} above, i.e., the boxes marked with an ‘s’, are inertial (in B_{ν}) so that all diagrams of K_{ν} = K(B_{ν}) can be derived “as if the s-boxes were not there”. Since we want to represent K_{ν} faithfully w.r.t. columns by a set H_{ν} ⊂ K the following definition is natural:

Definition 4. For π, π_{ν} and D_{ν} as above let S(D_{ν}) := {[i_{ν}, k_{0}], [i_{ν}, k_{0} + 1], …, [i_{ν}, k_{ν} − 1]} denote the set of s-boxes of D_{ν}. Let K_{S}(D_{ν}) denote the set of all diagrams in K(D_{ν}) which can be derived without moving any s-box S(D_{ν}). Then D_{ν} is called s-independent, if

K_{S}(D_{ν}) = K(D_{ν} \ S(D_{ν})) ∪ S(D_{ν}) ,

where the union with the set S(D_{ν}) is of course taken for every diagram in K(D_{ν} \ S(D_{ν})). D_{ν} is called s-dependent, if it is not s-independent.

Note that (D_{ν}) is s-independent iff all boxes below S(D_{ν}) in D_{ν} are inertial.

Moreover, we remark that similarly to the notation S(D_{ν}) of Definition 4 one defines the sets of s-boxes S(B_{ν}) := {[1, k_{0}], …, [1, k_{ν} − 1]} and the sets of t-boxes T (B_{ν}) := (B_{ν})^{[k]} \ {[1, k]}, T (D_{ν}) := T (B_{ν}), T_{ν}(D(π)) := D(π)^{[k_{ν}]}.

Lemma 5. For every π ∈ S_{n,k} with k < n and J^{>k}(π) as in (6) the diagrams D_{0} and D_{q} are s-independent.

Proof. For D_{0} this is trivial, because S(D_{0}) = ∅. For D_{q} one observes that (D_{q})_{[1,i_{q}−1]}^{[k_{0},n]}

and (D_{q})_{[i_{q},i_{q}]}^{[k_{q},n]} are empty so that no boxes in D_{q} \ S(D_{q}) can be obstructed in their movability by the boxes in S(D_{q}). (Compare D_{3} in Examples 6 and 11.) □

If for some π all diagrams D_{ν} are s-independent then it is easy to carry out the steps 1, 2 and 3 of the proof:

Example 6. Let π = 15432 ∈ S_{5}. Then D(π) = and

D_{0} = ^{ttt}  , D_{1} = ^{tt s}  , D_{2} = ^{t s s}  , D_{3} = ^{s s s}  .

Clearly, all D_{ν} are s-independent, because the boxes below the sets S(D_{ν}) are inertial. Hence the faithful w.r.t. columns bijection of step 1 is simply given by setting H_{ν} := K(D_{ν} \ S(D_{ν})) ∪ S(D_{ν}) (remember the removal of [1, k]).

For any finite permutation π the number of boxes in S(D_{ν}) is k_{ν} −k −1 by definition. For any diagram D ∈ K(D(15432)) in our example (or more generally any D contained in a s-independent D_{ν}) set

μ(D) := max {ν | S(D_{ν}) ⊂ D} .

Since for all ν the s-boxes of D_{ν} are fixed for the D ∈ H_{ν} and since all boxes in rows below level i_{ν} are inertial, one has D ∈ H_{ν} ⇔ μ(D) = ν. This shows both step 2 and step 3. □

The case that for given π all D_{ν} are s-independent is of course a rare one. To get a first idea about how to deal with a D_{ν} that is s-dependent, we close this section with another simple example.

Example 7. Let π = 21543 ∈ S_{5}. Then D(π) = and (omitting the empty second row)

D_{0} = ^{tt}  , D_{1} = ^{r t s}  , D_{2} =  ^{s s}  .

By Lemma 5 (or direct inspection) one sees that D_{0} and D_{2} are s-independent. But D_{1} is s-dependent. If one K-moves the boxes of D_{1} as if the s-box were not there, one would get

s  ^{s}  ^{s}  .

But then the second move would not be a valid K-move. The way out is to fix the r-box of D_{1} (marked with an ‘r’) instead of the s-box. Then the above diagrams are faithfully w.r.t. columns represented by:

r  ^{r}  ^{r}  .

It is very important to note that simply fixing the r-box in D_{1} allows for more Kderived diagrams than just the two depicted above, namely:

r  ^{r}  ^{r}  .

But these three diagrams are already contained in K_{S}(D_{0}) = K(D_{0})! The key to distinguish between the “right” three the “wrong” three diagrams which fix the r-box is to maintain the order of the two moving boxes “as if they were on the same level”. The

sub diagrams  ,  , etc. where the boxes are in ascending order or form an

ascending step are the “right” one’s in K_{S}(D_{1}). The subdiagrams , , etc. (the

latter being in descending order or forming a descending step) are the “wrong” one’s.

It is clear by the forgoing discussion that H_{2} contains all diagrams derivable from D_{2} with the two s-boxes fixed, that H_{1} contains the diagrams derivable from D_{1} with the r-box fixed and the two movable boxes maintaining ascending order, that D_{0} contains all remaining diagrams of K and that the H_{ν} thus defined form a partition of K. (For a similar situation examine again the poset of Example 3.) □

3. The general case

Since the discussion of Example 6 (and in particular the equivalence D ∈ H_{ν} ⇔ μ(D) = ν) applies to all s-independent diagrams D_{ν}, the work in the general case has to focus on the s-dependent D_{ν}. Example 7 pointed out how to proceed: In case of an s-dependent diagram D_{ν} one must choose r-boxes as substitutes for the s-boxes. They must be below the s-boxes in the same columns (because of faithfulness w.r.t. columns) and the must guarantee optimal movability of the other boxes (“as if they were not there”) without being inertial themselves (because the original s-boxes in B_{ν} are not inertial, too). These requirements solicit the following definition:

Definition 8. Let the permutation π be element of some S_{n,k} with k < n and with J^{>k}(π) as in (6). For any diagram D_{ν} the set of r-boxes R(D_{ν}) ⊂ (D_{ν})^{[k_{0},k_{ν}−1]} contains the unique box in every column in question that is directly above the highest inertial box.

Lemma 9. Let π, J^{>k}(π) and the sets R(D_{ν}) be given as in Definition 8 above. Then:

a) No r-box is above an s-box.

b) If a diagram D_{ν} is s-independent, then the r-boxes of D_{ν} are identical to the s-boxes: R(D_{ν}) = S(D_{ν}). Otherwise the r-boxes are strictly below the s-boxes.

c) All r-boxes of an s-dependent D_{ν} are in the same row.

d) If not all D_{ν} are s-dependent, then

(7)  ρ := max {ν | D_{ν} is s-dependent }

exists and D_{0}, D_{ρ+1}, …, D_{q} are s-independent, whereas D_{1}, …, D_{ρ} are s-dependent. Moreover, the r-boxes of the s-dependent D_{ν} are all on level i_{ρ}.

Proof. a) follows from the definition of r-boxes, the fact that the s-boxes S(D_{ν}) ⊂ (D_{ν})^{[k_{0},k_{ν}−1]} are never inertial and that inertial boxes can not be above movable boxes.

b) After Definition 4 we remarked that D_{ν} is s-independent iff all boxes below S(D_{ν}) in D_{ν} are inertial. Hence b) is a consequence of a).

c) Suppose that [i, j] ∈ R(D_{ν}) has minimal column index j and that [i′, j′] is a different box in R(D_{ν}), which means j < j′. Then by Definition 8 the next box [i′′, j′] below [i′, j′] is inertial and consequently every box in (D_{ν})_{[1,i′′]}^{[1,j′]} is inertial, whence i ≥ i′.

It remains to show that i > i′ is excluded, too. But since [i′, j′] is movable, there must be an empty position (i′, j′′) in D_{ν} with j′′ < j′. In fact, even j′′ < j because k < j < j′ < k_{ν} and all rows below S(D_{ν}) are either completely filled with boxes or completely empty. If now the position (i′, j′′) with j′′ < j is empty in D_{ν}, then the assumption i > i′ forces an empty position (i − 1, j′′) in D_{ν} and [i − 1, j] would be movable instead of being inertial. Hence all r-boxes are in the same row.

d) Assume that D_{ν} is s-independent for some ν > 0. Then the boxes below S(D_{ν}) in the interval of columns [k_{0}, k_{ν−1}] are inertial in D_{ν}. In particular the boxes below [i_{ν+1}, k_{0}], …, [i_{ν+1}, k_{ν−1}] are inertial D_{ν}. Comparison of D_{ν} and D_{ν+1} then shows that consequently the boxes below [i_{ν+1}, k_{0}], …, [i_{ν+1}, k_{ν}] are inertial in D_{ν+1}. Hence D_{ν+1} is s-independent by Definition 4.

This proves the first part of d). That the r-boxes of the s-dependent D_{ν} are all on level i_{ρ} follows by an analogous argument that proceeds from the s-boxes of D_{ρ+1} to the r-boxes of D_{ρ}, D_{ρ−1}, …, D_{1} using Definition 8. □

The next problem is to define the sets H_{ν} ⊂ K for the D_{ν} as required by step 1 in Section 2. For s-independent D_{ν} this is done by setting H_{ν} := K(D_{ν} \ S(D_{ν})) ∪ S(D_{ν}). But for s-dependent D_{ν} it is not possible to simply substitute the s-boxes by the rboxes. The K-derived set fixing the r-boxes would be too big in general. It is necessary to apply the notions of ascending and descending orders of boxes from Example 7 to suitable subdiagrams. This is done by generalizing the notion of a row or level by a “line”:

Definition 10. a) Let π, J^{>k}(π), S(D_{ν}) and R(D_{ν}) as in Definition 8 and ρ as in (7). Then the lines of an s-independent D_{ν} are identical to the rows of D_{ν}; and the lines of an s-dependent D_{ν} are identical to the rows of D_{ν} outside of

(8)  D_{ν} := (D_{ν})_{[i_{ρ}+1,i_{ν}]}^{[k_{0},k_{ν}−1]}

whereas each row i with i_{ρ} ≤ i < i_{0} is continued inside D_{ν} by the next higher non-empty row of boxes.

b) The lines that have a non-empty intersection with D_{ν} are called proper lines. The intersection with D_{ν} is called the middle part of the line and the parts left and right of D_{ν} the left and right part, respectively. The step from the left to the middle part of a proper line is called an ascending step and the step from the middle part to the right part of a proper line a descending step. Alternatively, one could say that the two boxes involved in both kinds of steps are in ascending order respective descending order.

c) The number of boxes contained in the left, middle and right part of the l-th proper line (counted from bottom to top) of D_{ν} form the first, second and third entry of a vector χ_{ν}^{l} ∈ ℕ_{0}^{3} called the characteristic of that proper line.

Example 11. Let π = 31864752 ∈ S_{8}. Then (without the empty third row)

D(π) =  and D_{0} = ^{ttttt}  ,

D_{1} = ^{t r tt s}  , D_{2} = ^{t s s}  , D_{3} =  ^{s s s s s} .

Therefore ρ = 1 and the lines of D_{1} are

D_{1} = [figure: r]

with the characteristics χ_{1}^{1} = (1, 1, 0) and χ_{1}^{2} = (1, 1, 1). □

It is useful to think about the lines of an s-dependent D_{ν} as the rows of B_{ν} being “pushed up” locally by the upward move of the s-boxes of B_{ν} to the position of the rboxes of D_{ν} while at the same time removing the s-boxes of D_{ν}. (Note that the removal of S(D_{ν}) in the process of pushing up guarantees that the lines modify the original rows only inside D_{ν} and that all lines are disjoint.)

Definition 12. Let π be as in Definition 8. For s-independent D_{ν} set H_{ν} := K(D_{ν} \ S(D_{ν})) ∪ S(D_{ν}). For s-dependent D_{ν} let H_{ν} be the set of all diagrams in K(D_{ν}) that fix R(D_{ν}) and which respect lines in the following sense: there are never boxes of the same line on top of each other (except in a transitory way during tunnelling).

In other words: The boxes in a proper line move as if they were on one level. Since all D ∈ H_{ν} are derived by K-moves that respect lines, it is possible to extend the notions of proper lines and characteristics of Definition 10 to all such D:

Definition 13. Let π be as in Definition 8 and H_{ν} as in Definition 12 for any sdependent D_{ν} and D ∈ H_{ν} arbitrary. Then the proper lines of some D can be derived recursively from the proper lines of D_{ν} by a sequence of K-move that respect lines.

Accordingly, the notions of left, middle and right parts, of ascending and descending steps and of a characteristics from Definition 10 b)-c) apply to the proper lines in D. Again the middle part is exactly the elevated portion of the proper line and Again the number of boxes contained in the left, middle and right part of the l-th proper line (counted from bottom to top) of D form the characteristics χ_{ν}^{l}(D) of D.

Note that χ_{ν}^{l}(D) can be differ from χ_{ν}^{l} in a certain way: the number of boxes in the left part of a proper line can increase at the cost of the right part through tunnelling of a box.

We are now prepared to carry out the steps 1 – 3 of the proof of Kohnert’s algorithm (recall Section 2) also for the s-dependent D_{ν} where 1 ≤ ν ≤ ρ. For step 1 observe that for every diagram D ∈ H_{ν} there is clearly some counterpart D′ ∈ K_{ν} = K(B_{ν}) that is faithful w.r.t. columns, because the K-moves in H_{ν} respect lines. But conversely there is also for every D′ ∈ K_{ν} a counterpart D ∈ H_{ν}: any K-move K_{ν} can be imitated by a sequence of one or more K-moves in H_{ν} that respect lines. The ”obstacle” R(D_{ν}) can be overcome by tunnelling.

For steps 2 and 3 it is sufficient to show that every diagram D ∈ K is contained in exactly one H_{ν}. If S(D_{ν}) ⊂ D for any ν ∈ {ρ + 1, …, q}, then necessarily D ∈ H_{ν} for exactly that ν. (Also the reversal is true.) If this is not the case, then we have to show that D ∈ H_{ν} for exactly one ν ∈ {0, 1, …, ρ}. The idea how to proceed is as follows:

For all ν with 1 ≤ ν ≤ ρ try to construct proper lines in D in a way that is consistent with the different characteristics χ_{ν}^{l} – we will describe an appropriate algorithm below –. If this is possible, we write D ⊨ H_{ν}, and D ⊭ H_{ν} otherwise. Clearly, D ∈ H_{ν} ⟹ D ⊨ H_{ν} but not necessarily conversely. The desired conclusion ”D ∈ H_{ν} for exactly one ν” is then implied by the two claims

a) D ⊨ H_{ν} ⟹ D ∉ H_{ν′} ∀ν′ < ν and

b) D ⊭ H_{ν}, ∀ν ≥ 1 ⟹ D ∈ H_{0}. In fact a) and b) together say that the (existing) maximal ν ≤ ρ with D ⊨ H_{ν} is the unique ν for which D ∈ H_{ν}.

Note that for fixed ν ∈ {1, …, ρ}

χ_{ν}^{l}(2) = r_{ν} := |R(D_{ν})|, ∀ l ,

i.e., the middle parts of all proper lines in D_{ν} have the same cardinality r_{ν}. Recall further that by tunnelling of boxes χ_{ν}^{l}(1) may increase at the cost of χ_{ν}^{l}(3) and that on levels i_{ν} no D ∈ K has any boxes right to column k_{ν}.

Lemma 14. (Non-crossing Condition) Let D ∈ K be a diagram with more than one proper line. Then no box from the middle part of a proper line can be left to (in the same row) any box from the left part of the next proper line above. (It is however possible that a box from the right part of a proper line is left to a box from the middle part of the next proper line below.)

Proof. A box from the middle part of any proper line can be moved to the left only after the corresponding boxes from the middle parts of higher proper lines have been moved to the left. But Definition 12 says that moving boxes from the middle part of a proper line results in ”pushing” the boxes from its left part father to the left. □

Given any D ∉ H_{ν} for ρ+1 ≤ ν ≤ q we discuss now how to construct proper lines for given characteristics. Since R(D_{ρ+1}) ⊈ D by assumption, there exists (recall Lemma 9 d) ) a k′: k_{0} ≤ k′ < k_{ρ+1} with {[i_{ρ+1}, k_{0}], …, [i_{ρ+1}, k′]} ⊂ D but [i_{q}, k′ + 1] ∉ D. Hence it is possible that D ⊨ H_{ν} for some ν with k_{ν} ≤ k′ and we begin by checking the maximal ν first, than the next smaller ν, etc. .

Assuming that D ∈ H_{ν} (for 1 ≤ ν ≤ ρ) the positions of the boxes R(D_{ν}) ⊂ D are known and the first proper line can be determined using the characteristic χ_{ν}^{1}. If there are less than χ_{ν}^{1}(3) boxes right to R(D_{ν}) in the first proper line then the missing boxes must have tunnelled to the left part of the line (and possibly higher boxes must have tunnelled, too). Observing the non-crossing condition of Lemma 14 and using the characteristics χ_{ν}^{2}, χ_{ν}^{3}, … it can be checked one line after the other, whether it is possible to construct all proper lines bottom up in a consistent manner, i.e., whether D ⊨ H_{ν}.

Example 15. Consider the permutation π = 3 6 2 1 8 7 10 5 9 4 ∈ S_{10} with (relevant rows only)

D_{0} =  ^{ttt}  , D_{1} =  ^{tt rs}  ,

D_{2} =  ^{t rs rs rs}  , D_{3} =  ^{s s s s s} .

D_{0} and D_{3} have of course no proper lines whereas D_{1} has two of them with characteristics χ_{1}^{1} = (2, 1, 3), χ_{1}^{2} = (2, 1, 1) and D_{2} has one with characteristic χ_{2}^{1} = (2, 3, 1). Accordingly, r_{0} = 0, r_{1} = 1, r_{2} = 3 and r_{3} = 5.

Investigation of the following four diagrams

D =  ^{? ? ?}  , D′ =  ^{? ? ?}

D′′ =  ^{? ? ?}  , D′′′ =  ^{? ? ?}

shows that none of them is an element of H_{3}, but all of them contain boxes in the positions R(D_{1}) and R(D_{2}) indicated by the question marks. Moreover, it is not hard to verify that D ⊨ H_{2} and D ⊭ H_{1}, D′ ⊨ H_{1} (with tunnelling in the second proper line) and D′ ⊭ H_{2}, D′′ ⊨ H_{1} and D′′ ⊨ H_{2} whereas D′′′ ⊭ H_{1} and D′′′ ⊭ H_{2} (watch the necessity of a ascending step!).

Indeed, D ∈ H_{2}, D′ ∈ H_{1}, D′′ ∈ H_{2} and D′′′ ∈ H_{0} in accordance with the claims a) and b) to be shown next. □

Proof. (of a)) Let D ⊨ H_{ν} with ν ≤ ρ maximal. Then all middle parts of the proper lines may be in their original position (forming a ”rectangle” of boxes with possibly some empty rows) or may not.

For the first case recall that ν′ < ν implies k_{ν′} < k_{ν}, i_{ν′} > i_{ν} and r_{ν′} < r_{ν} whence row i_{ν} contains more boxes right to column k than possible for a D ∈ H_{ν′}.

For the second case Definition 12 shows that moving a box from the middle part of a proper lines causes the boxes of its left part to move, too, such that the ascending step from left to middle part is retained. But since i_{ν′} > i_{ν} for ν′ < ν in case of D ∈ H_{ν′} this would mean an ascending step among the t-boxes of D which is impossible. (For an illustration examine again D′′ of Example 15 where the crucial ascending step is marked by a line segment). □

Proof. (of b)) Assume D ⊭ H_{ν}, ∀ν ≥ 1. Then for all ν ≥ 1 the number of boxes right to column k in row i_{ν} must be less than r_{ν} by the arguments in the proof of a). Clearly, D_{0} obeys this condition and at the same time it is the maximal element of the sub poset H_{0} of K. In other words: every D ∈ K obeying the mentioned condition can be derived by a sequence of K-moves from D_{0} whence D ∈ H_{0}. (For an illustration examine again D′′′ of Example 15.) □

Acknowledgement. The valuable remarks and hints of the referees helped much to improve the presentation.

References

[B] N. Bergeron, A combinatorial construction of the Schubert polynomials, J. Comb. Th. A 60 (1992), 168-182.

[BGG] I.N. Bernstein, I.M. Gelfand, S.I. Gelfand, Schubert Cells and cohomology of the spaces G/B, Russian Math. Surveys 28 (1973), 1-26.

[Bo] A. Borel, Sur la cohomologie des espaces fibré principaux et des espaces homogènes des groupes Lie compacts, Ann. Math. 57 (1953), 115 - 207.

[D1] M. Demazure, Invariants symétriques des groups de Weyl et torsion, inventiones math. 21 (1973), 287 - 301.

[D2] M. Demazure, Désingularisation des variétés de Schubert généralisés, Ann. Scient. Ec. Norm. Sup. 7 (1974), 53 - 88.

[F] W. Fulton, “Young tableaux”, Cambridge University Press, Cambridge, 1997.

[FP] W. Fulton, P. Pragacz, “Schubert Varieties and Degeneracy Loci”, Lecture Notes in Mathematics 1689, Springer, Berlin, 1998.

[K] A. Kohnert, “Weintrauben, Polynome, Tableaux”, Bayreuther Mathematische Schriften 38 (1991), 1 - 97.

[L] A. Lascoux, Polynômes de Schubert. Une approache historique, Discrete Math. 139 (1995), 303 - 317.

[LS] A. Lascoux, M.-P. Schützenberger, Polynomes de Schubert, C.R.Acad.Sci.Paris 294 (1982), 447 - 450.

[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.

[Ma] P. Magyar, Four new formulas for Schubert polynomials, preprint (1995).

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

[W1] R. Winkel, Diagram rules for the generation of Schubert polynomials, J. Combin. Theory A 86 (1999), 14 - 48.

[W2] R. Winkel, Recursive and combinatorial properties of Schubert polynomials, Sem. Loth. Comb. B38c (1996), 29 pp.

[W3] R. Winkel, “On algebraic and combinatorial properties of Schur and Schubert polynomials”, Bayreuther Mathematische Schriften 59 (2000), 225 pp.

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