Séminaire Lotharingien de Combinatoire, B39a(1997), 28pp.

SCHUBERT FUNCTIONS AND THE NUMBER OF REDUCED WORDS OF PERMUTATIONS

RUDOLF WINKEL

Abstract: It is well known that a Schur function is the ‘limit’ of a sequence of Schur polynomials in an increasing number of variables, and that Schubert polynomials generalize Schur polynomials. We show that the set of Schubert polynomials can be organized into sequences, whose ‘limits’ we call Schubert functions. A graded version of these Schubert functions can be computed effectively by the application of mixed shift/multiplication operators to the sequence of variables x = (x_{1}, x_{2}, x_{3}, …). This generalizes the Baxter operator approach to graded Schur functions of G.P. Thomas, and allows the easy introduction of skew Schubert polynomials and functions.

Since the computation of these operator formulas relies basically on the knowledge of the set of reduced words of permutations, it seems natural that in turn the number of reduced words of a permutation can be determined with the help of Schubert functions: we describe new algebraic formulas and a combinatorial procedure, which allow the effective determination of the number of reduced words for an arbitrary permutation in terms of Schubert polynomials.

Let S_{n} denote the symmetric group on the ‘letters’ {1, …, n} and ℤ[x_{1}, …, x_{n}]^{S_{n}} the ℤ-algebra of symmetric polynomials in n variables. There are several well known ℤ-bases of this algebra (cf. [M1, Sa]), which are indexed by the partitions λ ≡ λ_{1} … λ_{s} (λ_{1} ≥ … ≥ λ_{s} ≥ 1) with length l(λ) := s ≤ n. The most important of these bases are the Schur polynomials s_{λ}^{(n)}(x) := s_{λ}(x_{1}, …, x_{n}), which can be defined alternatively by determinant formulas or combinatorially with the help of semistandard Young tableaux. The Schur polynomials are cumulative in the following sense: if ℤ[x_{1}, …, x_{n}]^{S_{n}} is extended to ℤ[x_{1}, …, x_{n}, x_{n+1}]^{S_{n+1}}, then (setting s_{λ}^{(n)}(x) := 0 for λ with l(λ) > n) one has

∀λ : s_{λ}^{(n)}(x_{1}, …, x_{n}) = s_{λ}^{(n+1)}(x_{1}, …, x_{n}, 0) . (0.1)

In other words:

s_{λ}^{(n+1)}(x) = s_{λ}^{(n)}(x) + ‘non-negative terms containing x_{n+1}, but no x_{ν} with ν > n + 1’.

It is therefore possible to extend the Schur polynomials to Schur functions s_{λ}(x), which are homogeneous formal power series contained in the direct limit

ℤ[[x]]^{S_{∞}} = lim_{⟵}_{n}ℤ[x_{1}, …, x_{n}]^{S_{n}}

Date: July 1996.

1991 Mathematics Subject Classification. 14M15, 05E15, 20F55.

such that s_{λ}^{(n)}(x) = s_{λ}(x_{1}, …, x_{n}, 0, …). Since the Schur polynomials are homogeneous of degree |λ| := λ_{1} + … + λ_{s} the natural grading is not by degree but by the number of variables appearing; and cumulativeness shows, that for fixed λ the complete information about all Schur polynomials and the Schur function is contained in the graded Schur function:

s_{[λ]}(x) := (s_{λ}^{[1]}(x), s_{λ}^{[2]}(x), s_{λ}^{[3]}(x), …) (0.2)

with n^{th} part

s_{λ}^{[n]}(x) := s_{λ}^{(n)}(x) − s_{λ}^{(n−1)}(x) (s_{λ}^{(0)}(x) := 0) . (0.3)

G.P. Thomas has shown that the graded Schur functions s_{[λ]}(x) can be represented by closed formulas, which are very well suited to computation; namely

s_{[λ]}(x) = ∑_{ζ∈SY T (λ)} B_{ζ}(x) , (0.4)

where SY T (λ) is the (finite) set of standard Young tableaux of shape λ and the expressions B_{ζ}(x), which are easily computed for a given ζ, are a mixture of multiplication and shift operators applied to the basis sequence x = (x_{1}, x_{2}, x_{3}, …) of variables.

In [W3] we have shown that this approach of Thomas can be extended to the 1- and 2-parameter families of Hall-Littlewood, Jack, and Macdonald symmetric polynomials, which contain Schur polynomials for special choices of parameters. In this paper we will introduce graded Schubert functions, which extends the Schur case in another direction:

Due to the work of A. Borel (1953), I.N. Bernstein, I.M. Gelfand, and S.I. Gelfand (1973), M. Demazure (1973-74), and finally A. Lascoux and M.-P. Schützenberger (mainly 1982-87) the Schubert calculus for the cohomology ring of flag manifolds has been shown to have an isomorphic realization in terms of polynomials. In fact to every finite permutation π contained in some S_{n} there is associated an in general nonsymmetric Schubert polynomial X_{π} ∈ ℤ[x_{1}, …, x_{n}]. The set of all Schubert polynomials forms a ℤ-basis of ℤ[x] and contains the Schur polynomials as special cases, namely, X_{π} is a Schur polynomial exactly when π is a Grassmannian permutation π(λ, n) (cf. Sec.1 below). More information about the Schubert calculus can be found in [Hi] and about Schubert polynomials in [LS, M2, M3, W1].

In Section 1 we will see that the X_{π} are cumulative with respect to a certain natural embedding of the symmetric groups S_{n} ↪ S_{n′} for n < n′ (Theorem 1.1). This will allow us to introduce the (graded) Schubert functions X_{[π]}, which generalize (graded) Schur functions.

In Sections 2 and 3 we extend Thomas’ formula for graded Schur functions (0.4) to the Schubert case (Theorem 3.9). The sets SY T (λ) of standard Young tableaux will be seen to be generalized by the sets R(π) of reduced sequences for π. Recall that S_{n} is generated by the elementary transpositions σ_{i} = (i, i + 1)

(i = 1, …, n − 1) subjected to the relations

(i) σ_{i}^{2} = id, (ii) σ_{i}σ_{i′} = σ_{i′}σ_{i} , if |i − i′| ≥ 2, and (iii) σ_{i}σ_{i+1}σ_{i} = σ_{i+1}σ_{i}σ_{i+1} .

For π = σ_{a} := σ_{a_{1}} … σ_{a_{p}} the sequence a ≡ a_{1} … a_{p} resp. the word σ_{a} is said to be reduced (for π) iff the number p is minimal. Then l(π) := p is called the length of π. We use the notations R(π) for the set of reduced sequences for π, and

(0.5)  r(π) := |R(π)| ,
(0.6)  f^{λ} := |SY T (λ)| .

A basic fact underlying the generalization of Schur functions to Schubert functions is that r(π(λ)) = f^{λ}, where π(λ) is a Grassmannian permutation associated to λ. This can be proved for example by a simple combinatorial bijection between the two sets R(π(λ)) and SY T (λ) (cf. [W4]).

Moreover, in Section 3 we introduce skew Schubert polynomials and functions. In Section 4 we derive a formula for the number of terms in each component

of X_{[π]}, which generalizes the results of [W3, Sec.3] in the Schur case, and we recall some important results of I.G. Macdonald, which relate reduced words and Schubert polynomials resp. functions. Moreover we introduce ‘hexagon free’ and ‘decomposable’ permutations, which will simplify in many cases the computation of the numbers r(π).

In Section 5 two generalizations of binomial coefficients will be discussed: first by the numbers f^{λ} and r(π) in a lattice theoretic context, and second with the help of graded Schubert functions.

The final Section 6 begins with a brief survey of what is known about the numbers r(π). There are explicit formulas in special cases, and theoretical results, which relate reduced sequences, balanced labelings, Stanley functions, and Schubert polynomials ([S1, EG, FS, FGRS]), but there is no general formula (see however Rem.6.13). We use initial parts of graded Schubert functions to provide new effective algebraic formulas (Theorems 6.3, 6.5, 6.7) and a combinatorial method (Cor.6.11), which enable the determination of the r(π)’s in general.

1. Schubert functions

We recall some facts about permutations, their codes, and Schubert polynomials. For every permutation π ∈ S_{n} the Schubert polynomial X_{π} ∈ ℤ[x_{1}, …, x_{n}] is defined as the result of applying a certain π-dependent sequence of divided differences to the monomial x_{1}^{n−1}x_{2}^{n−2} … x_{n}^{0}. The divided differences ∂_{i} (i ∈ ℕ) are defined by ∂_{i}f = (f − σ_{i}(f))/(x_{i} − x_{i+1}), where f is an arbitrary function of x, and the elementary transposition σ_{i} acts on f by interchanging the variables x_{i} and x_{i+1}.

An important elementary device for working with permutations and Schubert polynomials is the Lehmer code of a permutation: for π ∈ S_{n} the Lehmer code L(π) is an element of the set L_{n} := \{ \overline{l_{n−1}, …, l_{0}} | 0 ≤ l_{n−ν} ≤ n − ν, ν = 1, …, n } defined by l_{n−ν}(π) := ♯{ j | ν < j, πν > πj} for all ν ∈ {1, …, n}, e.g.

L(361542) = \overline{240210} or L(1257346) = \overline{0023000}; this sets up a bijection between S_{n} and L_{n} (cf. [W1]).

A permutation π is called Grassmannian iff there is a partition λ ≡ λ_{1} … λ_{s} and a natural number n ≥ l(λ) = s such that L(π) = \overline{0 … 0 λ_{s} … λ_{1} 0 … 0} with n − s ≥ 0 zeros on the left and (at least) λ_{1} zeros on the right. An alternative definition is: π is called Grassmannian iff π has a at most one descent, i.e. there is at most one i with π(i) > π(i + 1). Anyway

π(λ, n) := L^{−1}(\overline{0 … 0 λ_{s} … λ_{1} 0 … 0}) . (1.1)

Then a result of fundamental importance is

X_{π(λ,n)} = s_{λ}^{(n)}(x) , (1.2)

in other words: a Schubert polynomial X_{π} is a Schur polynomial exactly when π is Grassmannian (see [M3] or [W1] for a proof).

The exact number of zeros on the right side in L(π(λ, m)) is irrelevant – provided we get a well defined Lehmer code –, because in general the Schubert polynomials are invariant under left embedding of the symmetric groups: the left embedding of S_{p} into S_{p′} (p < p′) is given by π ↦ π(1) … π(p) p + 1 … p′, and the invariance of Schubert polynomials as X_{π} = X_{π(1)... π(p) p+1 ... p′}.

On the other hand for q := p′ − p > 0 one has the right embedding of S_{p} into S_{p′} given by

π ↦ 1 … q q_{+}(π) := 1 … q (π(1) + q) … (π(p) + q) , (1.3)

but this time the corresponding Schubert polynomials behave cumulative:

Theorem 1.1. Schubert polynomials are cumulative under right embedding of the symmetric groups, i.e. let π′ be the right embedding of a permutation π ∈ S_{p} into S_{p′} with q := p′ − p > 0, then

(1.4) X_{π′} = X_{π} + ‘non-negative terms’ .

Proof. Clearly it suffices to show the assertion for q = 1. Set π′ := 1 1_{+}(π) and π′′ := 1_{+}(π) 1, then π′ = π′′σ_{p} … σ_{1} and repeated use of [W1, Cor.6.8] gives:

X_{π′} = X_{(π′′σ_{p}... σ_{2})σ_{1}} = x_{1}^{−1}X_{π′′σ_{p}... σ_{2}} + ‘non-negative terms’ = … =

(x_{1} … x_{p})^{−1}X_{π′′} + ‘non-negative terms’ .

Now [W1, Prop. 3.3] says X_{π′′} = (x_{1} … x_{p})X_{π}, which proves (1.4).

Theorem 1.1 enables the following

Definition 1.2. Let π ∈ S_{n} be an arbitrary unembedded permutation, i.e. π is not left embedded (π(n) ≠ n), and π is not right embedded (π(1) ≠ 1). Set π^{(0)} := π and for m ∈ ℕ let π^{(m)} := 1 … m m_{+}(π) the right embedding of π into S_{n+m}. Then the graded Schubert function associated to π is

X_{[π]} := ( 0, …, 0, X_{π^{[0]}}, X_{π^{[1]}}, X_{π^{[2]}}, …) (1.5) with n − 2 leading zeros and m^{th} part

X_{π^{[m]}} := X_{π^{(m)}} − X_{π^{(m−1)}} (X_{π^{(−1)}} := 0) . (1.6)

The Schubert function associated to π is the formal sum

X̃_{π} := ∑_{m≥0} X_{π^{[m]}} . (1.7)

Remark 1.3. There are currently four possibilities to define Schubert polynomials: (1) the algebraic definition based on divided differences (as indicated above),

(2) combinatorial rules based on box diagrams (similar to Ferrer diagrams, but with movements of boxes instead of numberings) (cf. Sec.6 below), (3) a semicombinatorial rule based on reduced words: the BJS-formula due to S.C. Billey, W. Jokusch and R.P. Stanley ([FS]) (cf. Sec.2 below), and (4) two algebrocombinatorial methods, which are consequences of Monk’s rule: the “transition equation” method of Lascoux and Schützenberger [M3, (4.16)], and the “ascentdescent” method introduced in [W1, Sec.6].

For the proof of Thm.1.1 we have used the algebraic definition, but it is equally possible to proceed from one of the others: the cumulativeness of Schubert polynomials follows from the combinatorial definition via box diagrams with the same ease, as the cumulativeness of Schur polynomials from their combinatorial definition via semistandard Young tableaux. (In fact for all m ∈ ℕ the box diagrams for the sequence of right embeddings π^{(0)}, …, π^{(m)} form an ascending chain of principal box diagrams in the K-derived set 𝕂(π^{(m)}) (cf. [W2, Thm. 2.7]) ). With regard to the “ascent-descent” method (4) the result is immediate from the natural embedding of the right weak Bruhat order on S_{n} into that of S_{n+1} and with regard to the BJS-formula compare the proof of Thm.6.8 below.

Note that every finite permutation is of the form π^{(m)} for some unembedded π and a natural number m. Therefore every Schubert polynomial occurs as the sum of the initial parts of some graded Schubert function. For unembedded Grassmannian permutations π(λ) := π(λ, l(λ)) we clearly obtain (setting X_{π(λ,m)} = 0 for m < l(λ) ):

X_{[π]} = s_{[λ]}(x) and X̃_{π} = s_{λ}(x) .

It is important to observe that X_{π^{(m)}} ∈ ℤ[x_{1}, …, x_{n+m−1}] does not in general originate from X_{π^{(m+1)}} ∈ ℤ[x_{1}, …, x_{n+m}] by setting x_{n+m} = 0, but in general

X_{π^{(m+1)}}|_{x_{n+m}=0} = X_{π^{(m)}} + ‘non-negative terms’ .

For example let π = π^{(0)} = 321; then: X_{π^{(0)}} = x_{1}^{2}x_{2}, but π^{(1)} = 1432 and X_{π^{(1)}} = x_{1}^{2}x_{2} + x_{1}x_{2}^{2} + x_{1}^{2}x_{3} + x_{1}x_{2}x_{3} + x_{2}^{2}x_{3}. This destroys the notion of ‘grading’ as introduced in the Schur case, namely grading by the “number of variables”. But there is a substitute relying on the recursive structure of Schubert polynomials (cf. [W1, Cor.3.6]), which is almost as simple:

X_{π^{(m)}} = 1_{−}^{↓}(X_{π^{(m+1)}}|_{x_{1}=0}) , (1.8) where the operator 1_{−}^{↓} means: ‘shift all indices of variables by −1’. Indeed for the above example one computes 1_{−}^{↓}(X_{π^{(1)}}|_{x_{1}=0}) = 1_{−}^{↓}(x_{2}^{2}x_{3}) = x_{1}^{2}x_{2} = X_{π^{(0)}}. Note that for symmetric polynomials (1.8) is equivalent to (0.1).

2. The BJS-formula and the algebra of sequences of polynomials

Our general task in this section is to establish τP x-formulas for the graded Schubert functions X_{[π]}, i.e. to express X_{[π]} as a ℤ-linear combination of sequences consisting of the symbols τ, P and x, which are the shift operator, the geometric shift operator, and the multiplication operator, respectively, on the the space of sequences of polynomials in a growing number of variables. We discuss first the BJS-formula for Schubert polynomials found by S.C. Billey, W. Jokusch and R.P. Stanley (cf.[FS]), than we introduce the algebra of sequences of polynomials and the above mentioned operators, and in the next section we construct the τP x-formulas. The BJS-formula is our point of departure, because the divided difference definition does not work (see Rem.3.11 below).

Let π ∈ S_{n} be an arbitrary permutation of length l(π) = p and R(π) be the set of reduced sequences for π. To every a ≡ a_{1} … a_{p} ∈ R(π) we can then associate a set of p-tuples

B(a) := {b = b_{p} … b_{1} | n − 1 ≥ b_{p} ≥ … ≥ b_{1} ≥ 1, a_{i} ≥ b_{i}, a_{i} < a_{i+1} ⟹ b_{i+1} > b_{i}}. (2.1)

The BJS-formula now reads:

X_{π} = ∑_{a∈R(π)} ∑_{b∈B(a)} x_{b} ( with x_{b} = x_{b_{1}} … x_{b_{p}}) . (2.2)

We define the support of π as the set supp π := {a ∈ R(π)|B(a) ≠ ∅} ⊂ R(π).

Remark 2.1. Let GR(π) denote the graph with vertices R(π) and edges (a, a′) :⟺ ‘a can be transformed to a′ according to the relations (ii) and (iii) of elementary transpositions’. GR(π) is connected (see e.g. [W1, Prop. 1.2]), but supp π in general is not. It is therefore necessary to compute the whole set R(π). This can be done conveniently by computing one reduced sequence (for example with the method described below) and than using relations (ii) and (iii) and the connectedness of GR(π).

In [W1, Cor.2.11] it has been shown that for arbitrary π ∈ S_{n} with Lehmer code L(π) ≡ \overline{l_{n−1} … l_{0}} the sequence ΦL(π) := Φ(l_{n−1}) … Φ(l_{0}) with

Φ(l_{n−ν}) := (ν − 1)_{+}(l_{n−ν} … 1) = (l_{n−ν} + ν − 1 … ν) , if l_{n−ν} > 0 (2.3)

and Φ(l_{n−ν}) := ∅, if l_{n−ν} = 0, is reduced; in signs: ΦL(π) ∈ R(π). For example ΦL(214635) = Φ(\overline{101200}) = 1354 ∈ R(214635). Note that Ω_{n} := ΦL(n … 1) = Φ(\overline{n − 1 … 0}) is given by

Ω_{n} = n − 1 … 1 | n − 1 … 2 | … | n − 1 ,

where we have included vertical sectioning bars for clarity. We call

a(π) := ΦL(π) (2.4)

the canonical reduced sequence of π.

For the determination of B(a) it is not necessary to know the exact form of a, but only the ‘type’ T (a) of a, which we will introduce next. Every reduced word a ∈ R(π) can be written as

a ≡ a_{1} … a_{p} ≡ A_{k} … A_{1} ,

where A_{k}, …, A_{1} (k ≤ p) are the sections of a defined by

(2.5) a_{i} and a_{i+1} are in the same section :⟺ a_{i} > a_{i+1} .

For a reduced sequence a of length p with k sections the type T (a) of a is defined as a sequence of p integers

T (a) := t_{1} … t_{1} t_{2} … t_{2} … t_{k} … t_{k} ≡ τ_{p} … τ_{1} , (2.6)

where the multiplicity of each t_{ν} is |A_{ν}|, t_{1} := a_{p}, and recursively

(2.7) t_{ν} := min{min A_{ν}, t_{ν−1} − 1} for ν > 1.

Note that

t_{1} > t_{2} > … > t_{k} and τ_{p} ≥ … ≥ τ_{1} . (2.8)

For example a = 324324 has length p = 6 and k = 3 sections; therefore T (32|432|4) = 422211. Similarly T (43|5|61) = 110(−1)(−1), and for Ω_{n} ∈ R(n … 1) one has:

T (Ω_{n}) = \underbrace{n − 1}_{1} \underbrace{n − 2 n − 2}_{2} … \underbrace{2 … 2}_{n−2} \underbrace{1 … 1}_{n−1} . (2.9)

Let b ≡ b_{1} … b_{s}, \overline{b} ≡ \overline{b}_{1} … \overline{b}_{r} be (finite) words in the alphabet ℤ, then the componentwise order on such words (w.r.t. the linear order: ‘empty space’< … < −1 < 0 < 1 < 2 < …) is defined by: b ≤ \overline{b} :⟺ b_{ν} ≤ \overline{b_{ν}} for all ν ∈ ℕ.

Lemma 2.2. For π ∈ S_{n} and a ∈ R(π) one has with the above notations:

a) T (a) = max B(a) for every a ∈ supp π;

b) a ∈ supp π ⟺ T (a) ∈ B(a) ⟺ t_{k}(a) ≥ 1;

c) a ∈ supp π ⟺ a subword of Ω_{n}.

Proof. a) follows directly from the definitions and implies b), which in turn implies c): a ∈ supp π ⟺ T (a) ∈ B(a) ⟺ ∀ν : min A_{k+1−ν} ≥ ν ⟺ A_{k+1−ν} is subword of (n − 1) … ν ⟺ a is subword of Ω_{n}.

Let now R be a commutative ring with unit and x = (x_{1}, x_{2}, …) a sequence of variables; then

A ≡ A(R, x) := ( R[x_{1}], R[x_{1}, x_{2}], R[x_{1}, x_{2}, x_{3}], …) (2.10) is a R-algebra under componentwise addition and multiplication; note that the sequences X_{[π]} are elements of A(ℤ, x) for all (unembedded) π. The n^{th}-component of a ≡ (a_{1}, a_{2}, …) ∈ A is [a]_{n} := a_{n}. The shift operator τ : A ⟶ A, defined by

τ(a_{1}, a_{2}, a_{3}, …) := (0, a_{1}, a_{2}, …) or ∀n : [τa]_{n+1} := [a]_{n}, [τa]_{1} := 0 , (2.11)

and all its powers τ^{ν} (ν ∈ ℕ), τ^{0} := id are algebra endomorphism of A; consequently the same is true for all operators f(τ) ∈ R[τ] and even f(τ) ∈ R[[τ]], because [A]_{n} is not affected by τ^{ν} with ν > n. For x = (x_{1}, x_{2}, …) ∈ A and all n ∈ ℕ one has { [τ^{ν}x]_{n} | ν ∈ ℕ_{0} } = {x_{1}, …, x_{n}} ∪ {0}. One can calculate as usual in the rings R[τ] and R[[τ]]. Especially important is the ‘geometric’ shift operator

P := ∑_{ν=0}^{∞} τ^{ν} , P (a_{1}, a_{2}, a_{3}, …) = (a_{1}, a_{1} + a_{2}, a_{1} + a_{2} + a_{3}, …) . (2.12)

Consequently one has for all unembedded π:

\overline{X_{π}} := P X_{[π]} = (0, …, 0, X_{π^{(0)}}, X_{π^{(1)}}, X_{π^{(2)}}, …) , (2.13)

which justifies our restriction to the graded case of X_{[π]}. P and S := τP are Baxter operators, but because τ itself is not a Baxter operator we will not stress this topic further.

It is not hard to see (e.g. by induction) that a sequence a ∈ A(ℤ, x) of the form

∀n : [a]_{n} = ∑_{\begin{matrix}n=i_{p}≥... ≥i_{1}≥1 \\ i_{ν}∈D⇒i_{ν+1}>i_{ν} \end{matrix}} x_{i_{1}} … x_{i_{p}} (2.14)

for a fixed subset D ⊂ {1, …, p − 1} can be written using the τP x-formula (or Baxter sequence)

B_{p,D}(x) := xB_{p−1} … xB_{1}x with B_{ν} ∈ {P, S} and B_{ν} = S ⟺ i_{ν} ∈ D . (2.15)

For the rest of this section (and the next) let π be an unembedded permutation of S_{n} and π^{(0)} = π, π^{(1)}, π^{(2)}, … its sequence of right embeddings.

Lemma 2.3. For every unembedded π of length p and every m ∈ ℕ_{0} one has

R(π^{(m)}) = m_{+}R(π) := {m_{+}(a) = a_{1} + m … a_{p} + m | a ∈ R(π)} . (2.16)

Proof. We use the above cited result that ΦL(π′) ∈ R(π′) for arbitrary π′. It follows from Def.1.2 and (2.3) that ΦL(π^{(m)}) = m_{+}(ΦL(π)), and by the connectedness of the graph GR(π) that every element a ∈ R(π) can be derived by a chain of applications of the relations (ii) and (iii). Shifting the indices of the occurring elementary transpositions by m gives for every a ∈ R(π) exactly one corresponding m_{+}(a) ∈ R(π^{(m)}), which proves the assertion.

The BJS-formula together with Lemma 2.3 clearly implies

x_{π^{(m)}} = ∑_{a∈R(π)} ∑_{b∈B(m_{+}(a))} x_{b} , (2.17)

whence we can write

(2.18)  X_{[π]} ≡ ∑_{a∈R(π)} X_{[π]}(a) with
(2.19) X_{[π]}(a) = (0, …, 0, ∑_{b∈B^{[0]}(a)} x_{b}, ∑_{b∈B^{[1]}(a)} x_{b}, ∑_{b∈B^{[2]}(a)} x_{b}, …) and
(2.20) B^{[m]}(a) := B(m_{+}(a)) \ B((m − 1)_{+}(a)) , for m > 0, B^{[0]}(a) := B((a)) .

3. τP x-formulas for graded Schubert functions

Continuing the discussion of the last section we want to find now τP x-expressions B_{a}(x) for the sequences X_{[π]}(a) ∈ A(ℤ, x) [(2.18-20)]. We begin with a simple

Lemma 3.1. For π ∈ S_{n} and a ∈ R(π) with k sections one has:

a) T (m_{+}(a)) = m_{+}(T (a));

b) m_{+}(a) ∈ supp π^{(m)} ⟺ t_{k}(m_{+}(a)) = t_{k}(a) + m ≥ 1;

c) m_{+}(a) ∈ supp π^{(m)} ⟺ m_{+}(a) subword of Ω_{n+m}.

Proof. Immediate from the Lemmata 2.2 and 2.3.

Corollary 3.2. For π ∈ S_{n} and a ∈ R(π) with k sections let

m_{0}(a) := min{m ∈ ℕ_{0} | m_{+}(a) ∈ supp π^{(m)}} , (3.1)

which can be computed conveniently by Lemma 3.1 b) as

m_{0}(a) = max{0, 1 − t_{k}(a)} . (3.2)

Then the first non-zero term of X_{[π]}(a) appears in [A]_{n−1+m_{0}}, i.e. in the (n − 1 + m_{0})th component of A ≡ A(ℤ, x).

For a reduced sequence a ∈ R(π) of length p let

D(a) := {ν | a_{ν} < a_{ν+1}, ν = 1, …, p} = {ν | τ_{ν} > τ_{ν+1}, ν = 1, …, p} (3.3)

be the descent set of a (compare Rem.3.6 below). Let in addition π ∈ S_{n} be unembedded; then the number

d(a) := n − 1 − a_{l(π)} (3.4)

is called the global delay for a and the number

d(π) := min{d(a) | a ∈ R(π)} (3.5)

the global delay for π. Before stating a general result we elucidate the significance of the number d(a) by the following Example 3.3. Let π = 21543 ∈ S_{5} and a = 4341 a reduced sequence for π. Then T (a) = 1100, m_{0} = 1 by (3.1), i.e. the first von vanishing term of X_{[π]}(a) occurs in [A]_{5}, and the global delay is d(a) = 3 by (3.4). Observe that B(1_{+}(a)) = B(2211) = {2211} whence from (2.15-19) one has X_{[π]}(a) = (0, 0, 0, 0, x_{1}^{2}x_{2}^{2}, …). On the other hand it is not hard to see that X_{[π]}(a) is “essentially” of the form (2.14) with p = 4, descend set D(a) = {2}, and τP x-expression xP xSxP x = (0, x_{1}^{2}x_{2}^{2}, …), which implies B_{a}(x) = τ^{3}xP xSxP x. In other words: the onset of the sequence xP xSxP x is delayed by τ^{3} = τ^{d(a)}.

Proposition 3.4. Let π ∈ S_{n} be unembedded, a ∈ R(π), and B_{a}(x) the τP xformula for X_{[π]}(a). Then every term in B_{a}(x) begins with τ^{d(a)} …. If moreover d(π) > 0, then the deletion of d(π) (but not d(π) + 1) leading zeros from X_{[π]}(a) yields again an element of A(ℤ, x).

Proof. By Cor.3.2 the first non-zero term in X_{[π]}(a) appears in [A]_{n−1+m_{0}} with a_{l(π)} + m_{0} as the maximal index of the occurring variables. On the other hand any τP x-formula of the form x … ∈ A contains in component [A_{ν}] the variable x_{ν} as the variable of maximal index. Therefore the τP x-formula for X_{[π]}(a) must have the form τ^{d} …, with d = (n − 1 + m_{0}) − (a_{l(π)} + m_{0}) = n − 1 − a_{l(π)}, which is d(a) by (3.4). The second assertion is now immediate.

We call sequences of the form (2.14), which are expressed by τP x-formulas of type (2.15), regular and all other singular. Let a be a reduced sequence of length p with k sections; then using (2.6) we define

(3.6) a is regular :⟺ t_{ν}(a) − t_{ν+1}(a) = 1 for ν = 1, …, k − 1 ,

where the t_{ν}(a) ≡ t_{ν} are the entries of the type T (a), or alternatively

(3.7) a is regular :⟺ τ_{ν+1}(a) − τ_{ν}(a) ≤ 1 for ν = 1, …, p − 1 ,

where the τ_{ν}(a) ≡ τ_{ν} are the entries of T (a).

Proposition 3.5. Let π ∈ S_{n} be unembedded of length p and a ∈ R(π) with descent set D(a), and global delay d(a). If a ∈ R(π) is regular, then

(3.8) X_{[π]}(a) is regular and X_{[π]}(a) = τ^{d(a)}B_{p,D(a)}(x) .

For a partition λ ≡ λ_{1} … λ_{s} and its associated unembedded Grassmannian permutation π(λ) every a ∈ R(π(λ)) is regular, the global delay for π(λ) is s − 1, and:

X_{[π(λ)]} = τ^{s−1} ∑_{a∈R(π(λ))} B_{p,D(a)}(x) (3.9)

in accordance with (0.4) (see Rem.3.6 below).

Proof. Comparison between the summation in (2.15) and the definition (3.6-7) yields (3.8). By the definition of the unembedded Grassmannian permutation [ (1.1) with n = l(λ) = s ] one sees that π(λ) is an element of S_{λ_{1}+s}. Moreover (2.3) shows that the number a_{p} with p = |λ| of the reduced sequence a = ΦL(π(λ)) ∈ R(π(λ)) is a_{p} = λ_{1}. But by the results of [W4] (see Rem.3.6 below) every a ∈ R(π(λ)) then ends with a_{p} = λ_{1}, and therefore we have proved d(π) = λ_{1} + s − 1 − λ_{1} = s − 1. The term wise equality (except for the global delay) between (3.9) and (0.4) yields the regularity of all a ∈ R(π(λ)).

Remark 3.6. For any partition λ we have established in [W4] a natural combinatorial bijection between the set R(π(λ)) of reduced words of the unembedded Grassmannian permutation π(λ) associated to λ and the set SY T (λ) of standard Young tableaux of shape λ. Under this bijection every set D(a) is mapped in fact to the corresponding descent set D(ζ) of a standard Young tableaux ζ (cf. [W3]) thus justifying the notion ‘descent set’ for D(a).

It remains to find the τP x-expressions X_{[π]}(a) for non regular a. In view of the above proposition the following definition seems natural:

Let T (a) be the type of an arbitrary a with k sections and subdivide T (a) into h ≤ k parts T (a) ≡ T_{h} … T_{1} according to the condition:

(3.10) t_{ν} and t_{ν+1} are in the same part :⟺ t_{ν} − t_{ν+1} = 1 .

Then the parts T_{h}, …, T_{1} are called the regular parts of T (a). As an example consider a = 14356: it has length p = 6, the type T (a) = 65331 has k = 4 sections, and the h = 3 regular parts T_{3} = 65, T_{2} = 33, T_{1} = 1. Of course one has: a is regular iff T (a) has exactly one regular part.

As a convenient notation we introduce moreover the complement C(a) of the type T (a) for any reduced sequence a of length p by

C(a) ≡ c_{p} … c_{1}, with c_{ν} := τ_{p} − τ_{ν} for ν = 1, …, p . (3.11)

For example a = 14356 has type T (a) = 65331 and complement C(a) = 01335.

In front of Lemma 2.2 we have already described the componentwise order on the set of all finite words over ℤ. Below we will use this componentwise order restricted to the sets

W_{p,D} := {i ≡ i_{p} … i_{1} | i_{p} ≥ … ≥ i_{1}, ν ∈ D ⟹ i_{ν+1} > i_{ν}} (3.12)

where p is a natural number and D a subset of {1, …, p − 1}. Define

(3.13) ∀i ∈ W_{p,D} : \overline{i} := min\{h ∈ W_{p,D} | i ≤ h, h regular \} ;

\overline{i} is called the regular supremum of i. Furthermore for a ≡ a_{1} … a_{p}, T (a) ≡ τ_{p} … τ_{1}, and every l with 1 ≤ l ≤ p let

T^{+}(l, a) := τ_{p} … τ_{l+1} and T^{−}(l, a) := τ_{l} … τ_{1} (3.14)

Assume that T (a) has h regular parts and let p = j_{h} > … > j_{1} ≥ 1 be the indices of the leftmost entries in each regular part T_{h}, …, T_{1}, i.e. T_{j_{ν}} = τ_{j_{ν}} …. Then we define for ν = 1, …, h (with (3.3), (3.12-14)):

(3.15) W^{+}(j_{ν}, a) := {i_{p} … i_{j_{ν}+1} ∈ W_{p−j_{ν},D(T^{+}(j_{ν},a))} | i_{j_{ν}+1} > τ_{j_{ν}} and i_{j_{s}} ≤ τ_{j_{s}}−1 for s = ν+1, …, h} ,

W^{−}(j_{ν}, a) := \{i_{j_{ν}} … i_{1} ∈ W_{j_{ν},D(T^{−}(j_{ν},a))} | i_{j_{ν}} … i_{1} ≰ T^{−}(j_{ν}, a), i_{j_{ν}} … i_{1} ≤ \overline{T^{−}(j_{ν}, a)}\} . (3.16)

Before proceeding to the general description of how to set up the τP x-expressions B_{a}(x) for arbitrary reduced sequences a, it will be helpful to go through some examples:

Example 3.7. Let π = 21543 ∈ S_{5} and a = 1434 a reduced sequence for π. Then T (a) = 4331, C(a) = 0113, m_{0} = 0, and global delay d(a) = 0. By the definition of B(a) resp. B^{[m]}(a) the sum in [A]_{n−1+m} is over all 4-tuples i ≡ i_{4}i_{3}i_{2}i_{1} with n − 1 + m =: r ≥ i_{4} > i_{3} ≥ i_{2} > i_{1} ≥ 1, r − 1 ≥ i_{3} ≥ i_{2} (automatically), r − 3 ≥ i_{1}. Moreover at least of the conditions: i_{4} = r, i_{3} = r − 1, i_{2} = r − 1, i_{1} = r − 3 must be fulfilled; otherwise the 4-tuple i would be contained in some prior component [A]_{n−1+ν} with 0 ≤ ν < m.

Assume first that i_{4} = r. Then using r − 2 ≥ i_{1} instead of r − 3 ≥ i_{1} gives a regular sequence with p = 4, D = {1, 3}, and τP x-expression xSxP xSx, which has to be diminished in every part of [A]_{r} by the term x_{r}x_{r−1}^{2}x_{r−2}. Hence in case of i_{4} = 4 we get the expression xSxP xSx − xτx^{2}τx. Observe that xSxP xSx alone yields (0, 0, x_{3}x_{2}^{2}x_{1}, x_{4}x_{2}^{2}x_{1} + x_{4}x_{3}x_{2}x_{1} + x_{4}x_{3}^{2}x_{1} + x_{4}x_{3}^{2}x_{2}, …), which is diminished by (0, 0, x_{3}x_{2}^{2}x_{1}, x_{4}x_{3}^{2}x_{2}, …), and in fact X_{[π]}(a) has its first non vanishing term in [A]_{4}.

Assume now that i_{3} = r − 1 or i_{2} = r − 1. This implies i_{4} = r, which is already done. In general only the first place of a regular part in some T (a) gives a contribution (here T_{2} = 433 and T_{1} = 1). Therefore it remains to study the case i_{1} = r − 3 under the condition that i_{4} ≤ r − 1. But this forces of course i_{4} = r − 1, i_{3} = i_{2} = r − 2, and hence a term τxτx^{2}τx in X_{[π]}(a). Observe that in deed x_{3}x_{2}^{2}x_{1} has to occur in [A]_{4}, and not in [A]_{3}. In total we have

X_{[21543]}(1434) = (xSxP xSx − xτx^{2}τx) + τxτx^{2}τx .

Example 3.8. Let π = 2153674 ∈ S_{7} and a = 14356 a reduced sequence for π. Then T (a) = 65331, C(a) = 011335, m_{0} = 0, d(a) = 0, D(a) = {1, 3, 4}, and the regular parts of T (a) are T_{3} = 65, T_{2} = 33, T_{1} = 1. By the definition of B(a) resp. B^{[m]}(a) the sum in [A]_{n−1+m} is over all 5-tuples i ≡ i_{5}i_{4}i_{3}i_{2}i_{1} with n − 1 + m =: r ≥ i_{5} > i_{4} > i_{3} ≥ i_{2} > i_{1} ≥ 1, r − 1 ≥ i_{4}, r − 3 ≥ i_{3} ≥ i_{2}, r − 5 ≥ i_{1}, and at least one of the conditions: i_{5} = r, i_{4} = r − 1, i_{3} = i_{2} = r − 3, i_{1} = r − 5 has to be fulfilled.

Assume first that i_{5} = r. Then the regular supremum [(3.13)] of T (a) in W_{5,D(a)} is \overline{T (a)} = 65443. This yields a regular expression in A with τP x-formula xSxSxP xSx, which has to be diminished by singular expressions corresponding to the words 65443, 65442, 65441, 65432, 65431, 65421, 65332, 64332 ∈ W_{5,D(a)}, i.e. xτxτx^{2}τx, xτxτx^{2}τ^{2}x, xτxτx^{2}τ^{3}x, xτxτxτxτx, xτxτxτxτ^{2}x, xτxτxτ^{2}xτx, xτxτ^{2}x^{2}τx, xτ^{2}xτx^{2}τx.

i_{4} = r − 1 implies i_{5} = r, which is done already, but i_{3} = r − 3 with i_{5} ≤ r − 1 yields: r −1 = i_{5} > i_{4} > i_{3} = r −3, whence i_{4} = r −2, and r −3 = i_{3} ≥ i_{2} > i_{1} ≥ 1. Therefore we have the τP x-expression: τxτxτ[…], where ‘… ’ is determined by arguments similar to the case i_{5} = r or Ex.3.7 above as xP xSx − x^{2}τx.

i_{2} = r −3 implies i_{3} = r −3, which is done already, but i_{1} = r −5 with i_{5} ≤ r −1 and i_{3} ≤ r − 4 yields: r − 1 = i_{5} > i_{4} > r − 4 ≥ i_{3} ≥ i_{2} > i_{1} = r − 5, whence i_{3} = i_{2} = r − 4, and we have to consider singular expressions corresponding to the words 54221, 53221, 43221 ∈ W_{5,D(a)}, i.e. τxτxτ^{2}x^{2}τx, τxτ^{2}xτx^{2}τx, τ^{2}xτxτx^{2}τx.

In total we have

X_{[2153674]}(14356) = xSxSxP xSx − (xτxτx^{2}τx + xτxτx^{2}τ^{2}x + xτxτx^{2}τ^{3}x

+xτxτxτxτx + xτxτxτxτ^{2}x + xτxτxτ^{2}xτx + xτxτ^{2}x^{2}τx + xτ^{2}xτx^{2}τx)

+ τxτxτ(xP xSx − x^{2}τx) + (τxτxτ^{2}x^{2}τx + τxτ^{2}xτx^{2}τx + τ^{2}xτxτx^{2}τx) .

Theorem 3.9. (Computation of the τP x-formulas for graded Schubert functions X_{[π]} ) For an unembedded π ∈ S_{n} of length p one computes first the set of reduced sequences R(π), e.g. with the help of (2.3), the relations (ii) and (iii) for elementary transpositions, and the connectivity of GR(π) [Rem.2.1].

For fixed a ∈ R(π) let B_{a}(x) be the τP x-expression for the sequence X_{[π]}(a) [(2.18-20)]. Calculate T (a) [(2.6-7)], d(a) [(3.4)], the regular parts of T (a) [(3.10)], and with the help of the indices j_{h}, … j_{1}, which are the leftmost entries in each regular part T_{h}, …, T_{1} of T (a), the sets W^{+}(j_{ν}, a) and W^{−}(j_{ν}, a) [(3.15-16)]. Then

B_{a}(x) = τ^{d(a)} ∑_{ν=1}^{h} B_{a,ν}(x) ≡ τ^{d(a)} ∑_{ν=1}^{h} α_{a,ν}(x) β_{a,ν}(x) , (3.17)

where α_{a,ν}(x) and β_{a,ν}(x) are given by

(3.18) α_{a,ν}(x) = ∑_{i_{p}... i_{jν +1}∈W^{+}(j_{ν},a)} τ^{τ_{p}(a)−i_{p}}xτ^{i_{p}−i_{p−1}}x … xτ^{i_{jν +1}−τ_{jν} (a)} ,

(3.19) β_{a,ν}(x) = B_{j_{ν},D(T^{−}(j_{ν},a))}(x) − ∑_{i_{jν} ... i_{1}∈W^{−}(j_{ν},a)} xτ^{i_{jν} −i_{jν −1}}x … xτ^{i_{2}−i_{1}}x .

Proof. Assuming that the set R(π) and the types are already computed we are concerned with the computation of the B_{a}(x) for fixed a ∈ R(π). In case of regular a [(3.6-7)] one has: h = 1, j_{1} = p, W^{+}(p, a) = ∅, T^{−}(p, a) = T (a), T (a) = \overline{T (a)} ⟹ W^{−}(p, a) = ∅, and finally B_{a}(x) = τ^{d(a)}B_{p,D(a)}(x) in accordance with Prop.3.5 . Note that the global delay d(a) is already handled by Prop.3.4 for every a ∈ R(π). We have therefore to show the validity of formulas (3.17-19) in case of h ≥ 2.

Since ∑_{b∈B^{[m]}(a)} x_{b} is the part of X_{[π]}(a) in [A]_{r} with r := n − 1 + m, the task is to describe the sets B^{[m]}(a) [(2.20)] for all m ≥ 0 simultaneously. Using C(a) [(3.11)] and D(a) [(3.3)] the set B(m_{+}(a)) is given by

B(m_{+}(a)) = {b_{p} … b_{1} ∈ W_{p,D(a))} | ∀ν = 1 … p : b_{ν} ≤ r − c_{ν}} .

For B^{[m]}(a) we have to consider only those p-tuples of B(m_{+}(a)), which are not contained in B((m − 1)_{+}(a)), i.e. for at least one ν ∈ {1, …, p} we require b_{ν} = r − c_{ν}. But this has to be assured only for ν ∈ {j_{h}, … j_{1}}: for simplicity we consider ν = 1 resp. the regular part T_{1}(a) = τ_{j_{1}} … τ_{1} and s ∈ {1, …, j_{1} − 1}; if τ_{s} = r − c_{s}, then from T_{1}(a) ∈ W_{j_{1},D(T_{1}(a))}, regularity of T_{1}(a), and τ_{j_{1}} ≤ r − c_{j_{1}} it follows that τ_{j_{1}} = r − c_{j_{1}}. In other words the case of τ_{s} = r − c_{s} is identical to the case of τ_{j_{1}} = r − c_{j_{1}}.

Fix some ν ∈ {j_{h}, … j_{1}} and let B_{ν}^{[m]}(a) be the set of all b_{p} … b_{1} ∈ B(m_{+}(a)) with b_{j_{ν}} = r − c_{j_{ν}} and b_{j_{s}} ≤ r − c_{j_{s}} − 1 for s = ν + 1, …, h. By the preceding discussion B_{ν}^{[m]}(a) ⊂ B^{[m]}(a), ⋃_{ν=1}^{h} B_{ν}^{[m]}(a) = B_{ν}^{[m]}(a), and by definition B_{ν}^{[m]}(a) ∩ B_{μ}^{[m]}(a) = ∅ for every ν and μ > ν, i.e.

B^{[m]}(a) is the disjoint union of the B_{ν}^{[m]}(a) .

The τP x-expression B_{a}(x) for the sequence X_{[π]}(a) is therefore the sum of the τP x-expressions B_{a,ν}(x) (ν = 1, …, h) for the sequences

(0, …, 0, ∑_{b∈B_{ν}^{[0]}(a)} x_{b}, ∑_{b∈B_{ν}^{[1]}(a)} x_{b}, …) .

From the definition of B_{ν}^{[m]}(a) and taking into account that b_{j_{ν}+1} > b_{j_{ν}} = r − c_{j_{ν}} it is easily seen that the ‘translations’ of W^{+}(j_{ν}, a) by m_{+} yield the first p − j_{ν} entries b_{p} … b_{j_{ν}+1} of the b ∈ B_{ν}^{[m]}(a). Thus every (p − j_{ν})-tuple i_{p} … i_{j_{ν}+1} of W^{+}(j_{ν}, a) yields a corresponding singular expression, the sum of which gives α_{a,ν}(x) as described by (3.18).

For the remaining part b_{j_{ν}} … b_{1} of the b ∈ B_{ν}^{[m]}(a) observe that r − c_{j_{ν}} = b_{j_{ν}} ≥ … ≥ b_{1} ≥ 1 and b_{j_{ν}−1} ≤ r − c_{j_{ν}−1}, …, b_{1} ≤ r − c_{1}. The (j_{ν})-tuple r−c_{j_{ν}} … r−c_{1} giving these ‘upper bounds’ is obtained by ‘translation’ of T^{−}(j_{ν}, a) by m_{+}. Taking therefore the regular supremum \overline{T^{−}(j_{ν}, a)} of T^{−}(j_{ν}, a) gives the regular τP x-formula B_{j_{ν},D(T^{−}(j_{ν},a))}(x), which includes all terms x_{b} for the b ∈ B_{ν}^{[m]}(a) in every component [A]_{r}. But in general this is too much, and therefore singular terms corresponding to all those i_{j_{ν}} … i_{1} ∈ W_{j_{ν},D(T^{−}(j_{ν},a))}, which are less or equal (in componentwise order) to \overline{T^{−}(j_{ν}, a)} but not less or equal to T^{−}(j_{ν}, a) have to be subtracted. (Note that i_{j_{ν}}(a) = τ_{j_{ν}}(a) for all i_{j_{ν}} … i_{1} ∈ W^{−}(j_{ν}, a).) In total this yields β_{a,ν}(x) as defined by (3.20).

Remark 3.10. Note that the sets (3.15-16) and formulas (3.18-19) are unchanged if one replaces T (a) by some T (m_{+}(a)). It is therefore convenient always to use \overline{T} (a) := T (m_{+}(a)) with m = m_{0}, because then \overline{τ}_{1} = 1 : in fact this is true for m_{0} > 0 by Lemma 3.1, and

m_{0} = 0 ⟹ τ_{1}(a) = 1 , (3.20)

because: ‘π unembedded’ ⟹ ‘π(1) ≠ 1′ ⟹ ‘1 occurs in a’ ⟹ (3.20) by definition of the type T (a).

Remark 3.11. The algebraic definition of Schubert polynomials relying on divided differences is not suitable to build up τP x-formulas:

It would be necessary to have a ‘well behaved’ extension of the operators ∂_{i} to A(ℤ, x). For an unembedded π ∈ S_{n} the m^{th} part X_{π^{[m]}} of the graded Schubert function and the Schubert polynomial X_{π^{(m)}} = [\overline{X_{π}}]_{n−1+m} (recall (2.4)) are elements of ℤ[x_{1}, …, x_{n−1+m}]. Now ‘well behaved’ should clearly mean that the extended operator \overline{∂_{i,π}} fulfills \overline{∂_{i,π}} \overline{X_{π}} = \overline{∂_{i}X_{π}}. This is achieved, if we define:

[\overline{∂_{i,π}} \overline{X_{π}}]_{r} := ∂_{i+r−n+1} [\overline{X_{π}}]_{r} , if r ≥ n − 1, and
[\overline{∂_{i,π}} \overline{X_{π}}]_{r} := 0 , if 1 ≤ r < n − 1.

Now one has for example ∂_{1}X_{321} = ∂_{1}x_{1}^{2}x_{2} = x_{1}x_{2} = X_{231}. The general approach in this section shows that \overline{X_{321}} = P xSxP x + SxP xSx and \overline{X_{231}} = P xSx, whence \overline{∂_{1}}(P xτP xP x + τP xP xτP x) = P xτP x. Since the term τP xP xτP x does not contribute to [\overline{X_{321}}]_{2} = X_{321}, we would expect it to be of minor importance in \overline{∂_{1}} \overline{X_{321}}, too, but the contrary is the case: an tedious but elementary computation shows that \overline{∂_{1}}(P xSxP x) = xτx and \overline{∂_{1}}(SxP xSx) = P xSx − xτx. This unforeseen behavior of \overline{∂_{1}} in our example clearly shows that we can not hope to build up a neat calculus of τP x-formulas on the basis of extended divided differences.

The τP x-formulas for the graded Schubert functions allow the introduction and easy computation of (graded) skew Schubert functions and therefore skew Schubert polynomials, which in the Grassmannian case specialize to skew Schur functions and polynomials:

Let π be an unembedded permutation of length p and μ an unembedded permutation of length q ≤ p, which is less than or equal to π in right weak Bruhat order. For our purpose this means that every reduced sequence a_{1} … a_{q} ∈ R(μ) can be extended by suitable numbers a_{q+1}, …, a_{p} to a reduced sequence a_{1} … a_{q} a_{q+1} … a_{p} of π. It is therefore possible to define

R(π/μ) := {a ≡ a_{1} … a_{p} ∈ R(π) | a_{1} … a_{q} ∈ R(μ)} . (3.21)

Every term in the τP x-formula for X_{[π]} is of the form

xf_{p−1}x … xf_{1}x with f_{p−1}, …, f_{1} ∈ ℤ[[τ]] .

For such an expression and q ∈ ℕ we define

(xf_{p−1}x … xf_{1}x) ⇂ q := xf_{p−1}x … xf_{q+1}x ,

where of course (xf_{p−1}x … xf_{1}x) ⇂ (p − 1) = x and (xf_{p−1}x … xf_{1}x) ⇂ q = 0 for q ≥ p. With this not(at)ions we define the graded skew Schubert function associated to the pair (π, μ) to be

X_{[π/μ]} := ∑_{a∈R(π/μ)} B_{a}(x) ⇂ l(μ) . (3.22)

Proposition 3.12. Let λ, μ be partitions with μ ⊂ λ, i.e. the Ferrer diagram of μ is included in that of λ, and π(λ), π(μ) the associated unembedded Grassmannian permutations. Then R(π(λ)/π(μ)) is well defined, and X_{[π(λ)/π(μ)]} equals τ^{d(π(λ))}s_{[λ/μ]}(x), the graded skew Schur function associated to the skew partition λ/μ (shifted by τ^{d(π(λ))}).

Proof. (Sketch) Recall from Prop.3.5 or (3.9) that X_{[π(λ)]} = τ^{d(π)} ∑_{a∈R(π(λ))} B_{p,D(a)}(x). For R(π(λ)/π(μ)) to be well defined it is necessary and sufficient that every reduced sequence of π(μ) is contained as an initial segment of a reduced sequence of π(λ). But this is immediate from the combinatorial bijection between the sets R(π(λ)) and SY T (λ) of standard Young tableaux of shape λ set up in [W4], and the obvious fact that the inclusion of the shapes μ ⊂ λ implies the inclusion SY T (μ) ⊂ SY T (λ) of standard Young diagrams. Finally it has been shown in [W3, Sec.2] how the τP x-formulas of the graded skew Schur functions s_{[λ/μ]}(x) can be deduced from the τP x-formula of s_{[λ]}(x), and an easy comparison with the Schubert case yields that the latter is in fact a generalization of the former.

4. The number of terms of graded Schubert functions

In this section let π ∈ S_{n} be an unembedded permutation and a ∈ R(π). In view of the cumulativeness of Schubert polynomials and the τP x-formulas for graded Schubert functions it is natural to investigate the sequences π^{♯}(a) := (π_{1}^{♯}(a), π_{2}^{♯}(a), …) of numbers π_{r}^{♯}(a) := |B^{[r−n+1]}(a)|, which is the number of terms in each component of the sequence X_{[π]}(a) [(2.19-20)]. Obviously one has

π^{♯}(a) := B(a)(1) with 1 = (1, 1, …) . (4.1)

Since all factors x = 1 except the rightmost act as the identity automorphism on A ≡ A(ℤ, x), they can be neglected. Moreover shift operators in R[[τ]] commute and therefore every term in B_{a}(1) can be written in the ‘normal form’ τ^{K}P^{N}(1), where N is the number of symbols P or S occurring and K is the sum of exponents of the τ’s occurring outside the P ’s. In [W3, (3.3)] it has been shown that P^{N}(1) = \binom{r+N−1}{N}, whence

τ^{K}P^{N}(1) = \binom{r − K + N − 1}{N} . (4.2)

For example from Ex.3.7 one concludes

21543^{♯}(1434) = B_{1434}(1) = (τ^{2}P^{3}1 − τ^{2}1) + τ^{3}1 = \binom{r}{3} − (0, 0, 1, 0, 0, …)

and from Ex.3.8

2153674^{♯}(14356) = B_{14356}(1) = τ^{3}P^{4}1 − (τ^{3} + 4τ^{4} + 3τ^{5})1 + τ^{3}(τP^{2} − τ)1 + 3τ^{5}1

= \binom{r}{4} + \binom{r − 3}{2} − (0, 0, 0, −1, −6, −6, …) .

Summing up all sequences π^{♯}(a) gives

π^{♯} := ∑_{a∈R(π)} π^{♯}(a) ≡ (π_{1}^{♯}, π_{2}^{♯}, …) , (4.3)

where π_{r}^{♯} = |X_{π^{[r−n+1]}}| by (2.18) and (1.5-6). Of course

π^{♯} = X_{[π]}(1) , (4.4) and as we will see below the tedious computation of π^{♯} via the π^{♯}(a) and their τP x-formulas can be simplified very much.

By (2.13) the sequence X_{[π]}(1) is clearly known iff one knows the sequence

(s_{π^{(0)}}, s_{π^{(1)}}, s_{π^{(3)}}, …) with s_{π^{(m)}} := X_{π^{(m)}}(1, …, 1) , (4.5)

i.e. s_{π^{(m)}} is the sum of coefficients of the corresponding Schubert polynomial. It has been shown by I.G. Macdonald ([M1, M2, FS]) that for every permutation μ ∈ S_{n} of length p = l(μ)

X_{μ}(1, …, 1) = \frac{1}{p!} ∑_{a∈R(μ)} pr(a) with pr(a) := a_{1} … a_{p} . (4.6)

Moreover Macdonald has conjectured the following q-analog, which subsequently has been proven by S. Fomin and R.P. Stanley in [FS]:

X_{μ}(1, q, …, q^{n−2}) = \frac{1}{[p]!} ∑_{a∈R(μ)} pr_{q}(a) q^{α(a)} , (4.7)

where α(a) := ∑_{a_{ν}<a_{ν+1}} ν, [k] := 1 + q + ⋯ + q^{k−1}, [p]! := [1][2] … [p], and pr_{q}(a) := [a_{1}] … [a_{p}].

Observing that for an unembedded π ≡ π^{(0)} ∈ S_{n} of length p all π^{(m)} have length p, too, by Lemma 2.3, formula (4.6) immediately implies

s_{π^{(m)}} = \frac{1}{p!}P_{π}(m) (4.8)

with

P_{π}(m) := ∑_{a∈R(μ)} pr^{(m)}(a) and pr^{(m)}(a) := (m + a_{1}) … (m + a_{p}) . (4.9)

The q-analog with pr_{q}^{(m)}(a) := [m + a_{1}] … [m + a_{p}] is of course

s_{π^{(m)}}(q) := X_{π^{(m)}}(1, q, …, q^{n−2}) = \frac{1}{[p]!}P_{π}(m; q) := \frac{1}{[p]!} ∑_{a∈R(μ)} pr_{q}^{(m)}(a) q^{α(a)} .

Proposition 4.1. For all unembedded π of length p the polynomials \frac{1}{p!}P_{π}(m) are elements of ℚ[m] with non-negative coefficients and degree p with the property of

integrality: \frac{1}{p!}P_{π}(m) ∈ ℕ for all m ∈ ℕ_{0} .

Proof. Immediate from formula (4.8) and the fact that the coefficients of Schubert polynomials are non-negative integers.

Remark 4.2. In [FK] S. Fomin and A.N. Kirillov have shown that the polynomials P_{π}(m) and P_{π}(m; q) enumerate certain sets of plane partitions at least in the special case of π being of ‘staircase shape’ π = n (n − 1) … 1 or more generally π being dominant. Cor.4.4 below gives an answer to one of the question raised in [FK], namely for which π the polynomial P_{π}(m) is a product of linear factors in ℤ[m].

Proposition 4.3. Let μ ∈ S_{n} be a permutation of length p = l(μ), r(μ) the number of reduced sequences [(0.5)], and a(μ) the canonical reduced sequence of μ [(2.4)]. If now μ is hexagon free, that is: every a ∈ R(μ) can be computed from a(μ) by a sequence of transpositions according to relation (ii) alone, then

p! s_{μ} = r(μ) pr(a(μ)) . (4.10)

Proof. Since transpositions according to relation (ii) do not change the ‘letters’ contained in a reduced sequence a, the result is immediate from (4.8-9).

Corollary 4.4. The following statements are equivalent:

a) the polynomial P_{π}(m) is a product of linear factors in ℤ[m];

b) π is hexagon free.

c) π is 321-avoiding, i.e. there are no numbers i < j < k, such that π(i) > π(j) > π(k).

Proof. a) ⟺ b) by the preceding proposition and b) ⟺ c) by [BJS, Thm.2.1].

We quote without proof a nice result from [M1, M2]:

Proposition 4.5. Let μ be vexillary of length p and λ ≡ λ(μ) the partition obtained from reordering the entries of L(μ). Then with (0.5-6)

r(μ) = f^{λ} = \frac{p!}{h(λ)} , (4.11)

where h(λ) is the product of hooks according to the celebrated hook length formula. For Grassmannian permutations π(λ) imply formulas (4.10-11) that h(λ) = s_{π(λ)}/pr(a(π(λ))).

Unfortunately the proportion of vexillary permutations contained in some S_{n} is ≤ (23/24)^{n−3} for n ≥ 4 and thus vanishes for n ⟶ ∞. In comparing Propositions 4.3 and 4.5 note that Grassmannian permutations are vexillary and hexagon free, but in general a vexillary permutation need not be hexagon free (e.g. π = 321) and vice versa (e.g. π = 2143).

The following important general result has been observed by I.G. Macdonald, too:

Proposition 4.6. Let π be an unembedded permutation of length p. Then

r(π) = p! lim_{m⟶∞} X_{π^{(m)}}(\frac{1}{m}, …, \frac{1}{m}) . (4.12)

Proof. One has p := l(π) = l(π^{(m)}) for all m; and a well known fact about Schubert polynomials says that the X_{π^{(m)}} are homogeneous of degree p for all m. Thus

X_{π^{(m)}}(\frac{1}{m}, …, \frac{1}{m}) = (\frac{1}{m})^{p} X_{π^{(m)}}(1, …, 1)

and

(\frac{1}{m})^{p} lim_{m⟶∞} pr^{(m)}(a) = lim_{m⟶∞}(1 + \frac{a_{1}}{m}) … (1 + \frac{a_{p}}{m}) = 1 ∀a ∈ R(π)

together with (4.8) prove (4.12).

Definition 4.7. Let π ∈ S_{n} be an arbitrary permutation, then π is called decomposable iff it is of the form ‘π_{1} × π_{2}’, where π_{1} ∈ S_{k} for some k ∈ {1, …, n − 1} and π_{2} ∈ S_{k_{+}(n−k)} := S_{{k+1,...,n}}. Otherwise π is called indecomposable. The decomposition π = π_{1} × … × π_{s} is called maximal iff the ‘parts’ π_{ν} are indecomposable. (But it is useful to collect neighborly ‘identities’.)

Proposition 4.8. Let π ∈ S_{n}. Then the following statements are equivalent:

i) π is decomposable with π = π_{1} × π_{2} and π_{1} ∈ S_{k} with 1 ≤ k ≤ n − 1; ii) L(π) = [l_{n−1} … l_{0}] (cf. Sec.1) with [l_{n−1} … l_{n−k}] ∈ L_{k} and [l_{n−k−1} … l_{0}] ∈ L_{n−k}. iii) The interval [id, π] in right (weak Bruhat) order is the direct product of the intervals [id, π_{1}] and [id, π_{2}].

Moreover with the notation of i) and p := l(π_{1}), q := l(π_{2}):

r(π) = \binom{p + q}{q} r(π_{1}) r(π_{2}) . (4.13)

Proof. i) means that on places 1, …, k there is a permutation of the letters 1, …, k, and on places k + 1, …, n there is a permutation of the letters k + 1, …, n. Hence π_{1} and π_{2} have independent complete Lehmer codes as stated in ii), and for the entries of a ≡ a_{1}, …, a_{p} ∈ R(π_{1}) and b ≡ b_{1}, …, b_{q} ∈ R(π_{2}) one has from (2.3): a_{ν} ∈ {1, …, k − 1} and b_{ν′} ∈ {k + 1, …, n − 1}. Therefore all a_{ν} and b_{ν′} ‘commute’ in the sense of relation (ii) of the introduction, which shows that ii) ⟹ iii) ⟹ i).

Moreover the ‘commutativity’ of a_{ν}’s and b_{ν′}’s yields that the reduced sequences in R(π) are exactly the (p, q)-shuffles of pairs (a, b) ∈ R(π_{1}) × R(π_{2}), where the shuffles of the words a and b are all distributions of the p letters of a and the q letters of b over p+q places such that a and b remain subwords. Clearly for a given pair (a, b) the number of (p, q)-shuffles is \binom{p+q}{q}, which completes the proof.

Remark 4.9. The reduced sequences of some permutation π are the sequences of edge labels of maximal chains (without repetitions) in the interval [id, π] of right order. In Rem.2.1 we have introduced the graph GR(π) with vertex set R(π) and in [W4] we have made GR(π) into a ranked poset P R(π) by declaring the canonical reduced word a(π) as bottom element. It would be nice now to continue the equivalences of Prop.4.8 above by a characterization ‘iv)’ of decomposability in terms of GR(π) or P R(π).

This hints at a general problem: to every lattice L (or poset with top and bottom element) with labeled edges one can associate a graph GL on the set of ‘vertices’ = ‘the maximal chains of L’ by considering two chains, i.e. the associated sequences of labels, as ‘adjacent’ iff they can by transformed into each other by changing as less labels as possible. With every (natural) choice of a ‘canonical vertex’ as bottom element this graph may be turned into a poset P L. The problem is now to find relationships between the original L and the associated graph or poset of maximal chains.

5. Generalizations of binomial coefficients

For every n, k ∈ ℕ_{0} the binomial coefficients \binom{n}{k} are well known to have the following properties:

integrality: \binom{m + k}{k} ∈ ℕ for all m ∈ ℕ_{0} ,
recursion: \binom{n}{k} = \binom{n − 1}{k} + \binom{n − 1}{k − 1} , and
symmetry: \binom{n}{k} = \binom{n}{n − k} .

All these properties can be deduced at once from the fact (cf. [S2, Ex.3.5.4-5]) that \binom{m+k}{k} is the number of linear extensions of the direct sum of the chains m and k with m and k elements, respectively, which is well known to be the number of saturated chains in the direct product m + 1 × k + 1: take the rectangular grid of points [0, m] × [0, k] ⊂ ℤ × ℤ (–this is the direct product of the chains–) and count all possible paths or chains on this grid from (0, 0) to (m, k) with steps (1, 0) and (0, 1); clearly the number of such chains is \binom{m+k}{k}, because the k steps (0, 1) can be chosen as an arbitrary subset of the set of all m + k steps.

We call the partition λ = (n−k+1) 1^{k} of n+1 the (n, k)-hook with leg consisting of k boxes and arm consisting of m = n − k boxes. The set SY T (λ) of standard Young tableaux of such a (n, k)-hook is clearly in bijective correspondence to the saturated chains in m + 1 × k + 1: for ν = 1, …, m + k write the number ν into a box of the leg, if ν is a step (0, 1), otherwise into a box of the arm, such that resulting tableau is standard.

Thus we conclude that the numbers f^{λ} = |SY T (λ)| for partitions λ generalize binomial coefficients. In fact all the direct sums of the chains m and k are the finite order ideals in ℕ + ℕ (ℕ viewed as the infinite chain 1 < 2 < …). ℕ + ℕ is embedded (as half axes) into the direct product ℕ × ℕ, which has as finite order ideals the Ferrer shapes of partitions λ. The Young lattice Y of all Ferrer shapes ordered by inclusion is therefore the (distributive) lattice of order ideals of ℕ × ℕ, and the saturated chains of an interval [∅, λ] in Y are in natural one to one correspondence with the set SY T (λ). The symmetry of binomial coefficients is generalized now by the conjugation of partitions:

symmetry: f^{λ} = f^{λ′} ( with λ′ the conjugate of λ) ,

the recursion relation is generalized by

recursion: f^{λ} = ∑_{\overline{λ} is covered by λ in Y} f\overline{λ} .

Let S_{∞} = lim_{⟵}_{n}S_{n} (using left embedding) and P_{∞} the set S_{∞} with right (weak

Bruhat) order, where right order is the transitive closure of the covering relation:

(5.1) π covers \overline{π} in S_{∞} :⟺ ∃i ∈ ℕ : π = \overline{π}σ_{i}, l(π) = l(\overline{π}) + 1 .

Since the above condition for i is fulfilled exactly when i is a descent of π, i.e. π(i) > π(i + 1), it is helpful to define the descent set of π:

D(π) := {i | π(i) > π(i + 1)} . (5.2)

Note that for i ∈ D(π) the permutation πσ_{i} is the same as π except for the numbers π(i) and π(i + 1) interchanged. The edges of the Hasse diagram of P_{∞} can be labeled by the natural numbers i according to (5.1-2).

Since for every partition λ we know e.g. from (4.11) that r(π(λ)) = f^{λ} (– see [W4] for a combinatorial bijection establishing this identity –), the sets SY T (λ) are special cases of reduced words, and the reduced sequences for π are the sequences of edge labels of saturated chains from id to π in P_{∞}. Therefore the numbers f^{λ} are generalized by the numbers r(π) ∈ ℕ, which obey

(5.3) symmetry: r(π) = r(π′) ( with π′ := ωπω the ‘conjugate’ of π) and
(5.4) recursion: r(π) = ∑_{i∈D(π)} r(πσ_{i}) .

The notion ‘conjugate permutation’ is justified by the fact that for every partition λ one has π′(λ) := ω π(λ) ω = π(λ′) with ω = n (n − 1) … 1 for n large enough ([W1, Prop.4.9]).

Remark 5.1. R.P. Stanley has defined “generalized Pascal triangles” in an purely order theoretic way ([S2, S3]) relying on the Birkhoff duality between (finite) posets and distributive lattices ([S2, 3.4.1-3]). But the above described embedding of Y into P_{∞} is not covered by this result, because P_{∞} is not even modular as can be seen already in the case of S_{3}.

An interesting other approach to a generalization of binomial coefficients is suggested by

\binom{m + k}{k} = \frac{1}{k!} P_{π(λ)}(m) for λ = 1^{k} or λ = k. (5.5)

This is true, because by (2.3-4) one has a(π(1^{k})) = 1 … k and a(π(k)) = k … 1, whence P_{π(λ)}(m) = (m + k) · · · · · (m + 1) in both cases. Therefore binomial coefficients are generalized by the expressions \frac{1}{l(π)!} P_{π}(m), which by Prop.4.1 fulfill

(5.6)  integrality:  \frac{1}{l(π)!} P_{π(λ)}(m) ∈ ℕ for all m ∈ ℕ_{0}.

(Note that for every k ≥ 2 there are infinitely many unembedded π of length k.) Furthermore one has the

(5.7) recursion: P_{π}(m) = ∑_{i∈D(π)}(m + i) P_{πσ_{i}}(m) ,

where for unembedded π the covered πσ_{i} are not necessarily unembedded.

6. Computing the number of reduced sequences of a permutation

The number r(π) of reduced sequences of a permutation π ∈ S_{n} is easily computable by the recursion (5.4). But of course one would like to have a simple closed formula as in the case of Grassmannian or more generally vexillary permutations (Prop.4.5). An important step in this direction are the results of R.P. Stanley ([S1]) and Edelman and Green ([EG]), which say that the number of reduced sequences of a permutation π can be computed as a sum of f^{λ}, where the λ’s are partitions of the length l(π) of π:

r(π) = ∑_{λ⊢l(π)} α_{πλ} f^{λ} with α_{πλ} ∈ ℕ_{0} (6.1)

The non-negativity has been established in [EG] with the help of balanced tableaux. But more can be said:

Theorem 6.1. ([S1, Thm.4.1, Cor.4.2]) Let π ∈ S_{n} be an arbitrary permutation and π′ = ω_{n}πω_{n} its conjugate. Define

λ_{0} ≡ λ_{0}(π) := λ(L(π′)) ,
λ_{1} ≡ λ_{1}(π) := λ′(L(π)) ,

where λ(L(μ)) is the partition obtained by reordering the components of the Lehmer code of the permutation μ, and λ′(L(μ)) is the conjugate of λ(L(μ)). Then (with ‘<’ being the dominance order on partitions)

r(π) = f^{λ_{0}} = f^{λ_{1}} , if λ_{0} = λ_{1} ,
r(π) = f^{λ_{0}} + ∑_{λ_{0}<λ<λ_{1}} α_{πλ} f^{λ} + f^{λ_{1}} , if λ_{0} ≠ λ_{1} , whence:
r(π) = f^{λ_{0}} + f^{λ_{1}} , if λ_{1} covers λ_{1} in dominance order.

The α_{πλ} occurring in the case ‘λ_{0} ≠ λ_{1}’ may be nonzero !

Except for the special cases discussed above there is unfortunately no simple method known how to compute the coefficients α_{πλ}:

In [S1] Stanley has introduced symmetric functions F_{π} (= G_{π^{−1}} in the notation of [FS]), which upon expansion into Schur functions yield the α_{πλ} as coefficients; but the F_{π} in turn are computed from the sets R(π) of reduced sequences of π. The sets of balanced tableaux studied and used in [EG] and [FGRS] seems to be much more complicated than the sets of standard tableaux or the sets R(π) itself. Especially the computation of reduced words from balanced tableaux by a procedure of promotion and evacuation in [EG] seems to be of theoretical interest only.

In view of the close connections between reduced words and balanced tableaux ([EG, FGRS]), reduced words and the Stanley functions F (π) ([S1]), Stanley functions and Schubert polynomials ([FS]), and balanced tableaux and both Stanley functions and Schubert polynomials ([FGRS]), it doesn’t come as a surprise that Schubert polynomials can be used for the computation of the numbers r(π). This will be the subject of this final section.

By (2.16) and (4.13) we can restrict to unembedded and indecomposable permutations π. As an example take π = 132458769, which is represented by the unembedded permutation 2134765 = 21×34×765 ≡ π_{1} ×π_{2} ×π_{3}. Since l(π_{1}) = 1, l(π_{2}) = 0, L(π_{3}) = \overline{210}, l(π_{3}) = 3, and π_{3} dominant (hence vexillary) of shape λ(π_{3}) = 21, one sees: r(π) = \binom{4}{3}1 · 3 = 12. (Note: R(id) = \{∅\}, r(id) = 1.)

Propositions 4.1 and 4.6 have clearly shown the combinatorial significance of the polynomials P_{π}(m) and their coefficients, and formula (4.8) connects the P_{π}(m) to the sums s_{π^{(m)}} of coefficients of the Schubert polynomials X_{π^{(m)}} [(4.5)].

Lemma 6.2. Let π be an unembedded permutation of length p and P_{π}(m) = c_{p}m^{p}+ … + c_{1}m + c_{0}. Then c_{0} = p! s_{π} and c_{p} = r(π).

Proof. Setting m = 0 in (4.8) gives c_{0} = p! s_{π}. The other equality c_{p} = r(π) follows directly from the definition of P_{π}(m) in (4.8) and the observation that pr^{(m)}(a) is a monic polynomial of degree p in m for all a ∈ R(π).

Theorem 6.3. Let π ∈ S_{n} be an unembedded permutation of length p > 0. Then

r(π) = ∑_{i=0}^{p}(−1)^{p−i}\binom{p}{i} s_{π^{(i)}} . (6.2)

Proof. Using the notation of the above lemma and formula (4.8) one sees that for p + 1 different values of m one gets p + 1 linear equations for the coefficients c_{0}, …, c_{p}. Taking the values 0, …, p we get the system

c_{p}i^{p} + ⋯ + c_{1}i + c_{0} = p! s_{π^{(i)}}, (i = p, …, 0) ,

which can be solved for c_{p} by Cramers rule. We use the Vandermonde V_{n}(x_{1}, …, x_{n}) := det((x_{i}^{n−j})) to compute:

r(π) = c_{p} = \frac{p!}{V_{p+1}(p, …, 0)} det((∗| (p − i)^{p−j}))\begin{matrix}i=0,...,p \\ j=1,...,p \end{matrix}

with ∗ being the column vector (s_{π^{(i)}})_{i=p,...,0}. Expansion of the determinant w.r.t. the first column ∗ yields

∑_{i=0}^{p}(−1)^{p−i} s_{π^{(i)}} V_{p}(p, …, p − i + 1, p − i − 1, …, 0) =

∑_{i=0}^{p}(−1)^{p−i} s_{π^{(i)}} \frac{V_{p+1}(p, …, 0)}{i!(p − i)!} ,

which completes the proof.

The drawback of formula (6.2) is of course that one needs to compute all the numbers s_{π^{(m)}} for m = 0, …, p, which is getting harder for increasing m. But as we will see next one usually has to compute only a small fraction of the numbers s_{π^{(m)}}. As Prop.4.3 has shown the complexity of the determination of P_{π}(m) can be reduced considerably by singling out a factor corresponding to the multiset M(π) of letters, which occur in all reduced sequences a ∈ R(π) simultaneously. Since we don’t want to determine M(π) by enumeration of all reduced sequences, we must be content with the following (good) ‘approximation’ of M(π):

Lemma 6.4. ([FK, Lem.2.2]) For any permutation π the number of occurrences of an entry k in every a ∈ R(π) is at least

m_{k} ≡ m_{k}(π) := {i | i ≤ k, π(i) > k} . (6.3)

Proof. For the convenience and pleasure of the reader we quote the argument from [FK]: “Let us interpret a reduced word as a process of converting the identity permutation into π by means of adjacent transpositions. Since m_{k} numbers have to be moved from some of the first k positions to some of the remaining ones, it follows that the transposition σ_{k} has to be applied at least m_{k} times.”

For (unembedded) π ∈ S_{n} we define the m-vector of π by

m(π) := (m_{1}, …, m_{n−1}) , (6.4)

e.g. m(597216384) = (1, 2, 3, 3, 2, 2, 1, 1), and a polynomial

(x)^{m(π)} := (x + 1)^{m_{1}} (x + 2)^{m_{2}} … (x + n − 1)^{m_{n−1}} . (6.5)

In addition we introduce the polynomial Q_{π}(m) by requiring

P_{π}(m) = (m)^{m(π)} Q_{π}(m) . (6.6)

Then we get the following refinement of Thm.6.3:

Theorem 6.5. Let π ∈ S_{n} be an unembedded permutation of length p > 0 and d := p − |m(π)| = p − (m_{1} + m_{2} + …) [(6.3-4)]. Then with with notations (4.5), (6.6):

r(π) = ∑_{i=0}^{d}(−1)^{d−i} \frac{p!}{d! (i)^{m(π)}} \binom{p}{i} s_{π^{(i)}} . (6.7)

Proof. Using the notation of Lemma 6.4, and (4.8), (6.4-6) one sees that Q_{π}(m) = c_{p}m^{d} + …. Taking m = 0, …, d one now gets the system of linear equations:

(i)^{m(π)} (c_{p}i^{d} + …) = p! s_{π^{(i)}}, (i = d, …, 0) .

A calculation similar to that in the proof of Thm.6.3 yields the result.

For the computation of the numbers s_{π^{(0)}}, …, s_{π^{(d)}} one can use advantageously the (up case) recursive structure of Schubert polynomials described in [W1]: assume π ∈ S_{n} and X_{π^{(m)}} as known; then

X_{π^{(m+1)}} = ∂_{1} … ∂_{n+m}((x_{1} … x_{n+m})X_{π^{(m)}}) . (6.8)

Example 6.6. Take π = 4321. Then L(π) = \overline{3210}, l(π) = 6, λ(L(π)) = 321, and r(π) = 16 by Prop.4.5. The m-vector for π is m(π) = (1, 2, 1), whence d = 2. Since s_{π^{(0)}} = 1, s_{π^{(1)}} = 14, and s_{π^{(2)}} = 84, formula (6.7) gives

r(4321) = 30 · 1 − 10 · 14 + \frac{3}{2} · 84 = 30 − 140 + 126 = 16

as desired.

Remark 6.7. In a sense the Theorems 6.3 and 6.5 are complementary to the recursion formula (5.4): formula (5.4) relies on knowledge about the interval [id, π] in right weak Bruhat order, and formulas (6.2) and (6.7) on knowledge about certain Schubert polynomials, which is essentially equivalent to knowledge about the intervals [π, ω_{n+p}] and [π, ω_{n+d}], respectively. This can be seen from the method of divided differences or even more clearly from the ascent-descent method (cf. [W1, Sec.6]) for the computation of Schubert polynomials.

Theorem 6.8. Let π ∈ S_{n} be an unembedded permutation of length p > 0 and let \overline{s}_{π^{(m)}} denote the coefficient of the monomial x_{1} … x_{p} in X_{π^{(m)}}. Then

0 ≤ \overline{s}_{π^{(0)}} ≤ \overline{s}_{π^{(1)}} ≤ … ≤ \overline{s}_{π^{(p−2)}} ≤ r(π) = \overline{s}_{π^{(p−1)}} = \overline{s}_{π^{(p)}} = …. (6.9)

Proof. Recall the BJS-formula (2.2) for Schubert polynomials. Clearly b = p … 1 appears at most once in a set B(a). Moreover, B(m_{+}(a)) ⊂ B((m + 1)_{+}(a)) for all m ∈ ℕ_{0} by Lemma 2.3, whence: 0 ≤ \overline{s}_{π^{(m)}} ≤ r(π) and \overline{s}_{π^{(m)}} ≤ \overline{s}_{π^{(m+1)}} for all m ∈ ℕ_{0}. But for m ≥ p − 1 every entry a_{ν} of a reduced sequence a obeys a_{ν} + m ≥ 1 + (p − 1) = p; thus from the definition of the sets B(m_{+}(a)) it follows: b = p … 1 ∈ B(m_{+}(a)) for m ≥ p − 1 independently of a ∈ R(π).

Of course (6.9) in connection with the recursive computation (6.8) of Schubert polynomials can be used to determine r(π), but more importantly (6.9) in connection with the K-rule for the combinatorial generation of Schubert polynomials opens up a way for the combinatorial determination of r(π) and possibly the simple determination of the coefficients α_{πλ} in (6.1). Below we describe briefly the K-rule, which has been conjectured for arbitrary π (and proved for vexillary π) by A. Kohnert, and proved in general in [W2].

A box diagram B is a subset of an n×n-array of unit squares or boxes in the plane: B ⊂ {[i, j] ∈ ℤ × ℤ | 1 ≤ i, j ≤ n} for some n ∈ ℕ. The position “column i, row j” will be denoted by (i, j), the box at position (i, j) by [i, j]. We use the notation [i, j] ∈ B ([i, j] ∉ B) as an abbreviation for: B contains (does not contain) the box [i, j].

The diagram D(π) of a permutation π ∈ S_{n} is the box diagram, which originates from {[i, j] | 1 ≤ i, j ≤ n} by cancelation of the ‘hooks’ of boxes

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

for i = 1, …, n. For example π = 263154 has the diagram

×× × × ×× × · · · · · ·^{1}^{2}^{3}^{4}^{5}^{6} _{x_{1}}_{x_{2}}_{x_{3}}_{x_{4}}_{x_{5}}_{x_{6}} ,

where we have added: dots in the positions (i, π(i)), row numbers j = 1, …, 6 at the left, and variables x_{i} in columns i = 1, …, 6 at the bottom of the diagram. For the columns we have taken variables instead of numbers in view of the following evaluation rule: to every box diagram B one associates a monomial x^{B} := x_{1}^{β_{1}}x_{2}^{β_{2}} …, where β_{i} is the number of boxes in column i of B. The most important part of the K-rule is now a prescription, how to move a box [i, j] of a given box diagram B:

Definition 6.9. (of K-moves:) Let [i, j] ∈ B with {(i, j′) | j′ ≥ j} ∩ B = ∅, i.e. there is no box above [i, j] in B, and assume that M_{B}(i, j) := {(i′, j) | i′ < i, [i′, j] ∉ B} ≠ ∅. Then [i, j] is allowed to move to the position in M_{B}(i, j) with the greatest column number i′, i.e. the closest empty position left to [i, j] in row j of B.

Theorem 6.10. ([W2]) Let 𝕂(π) denote the set of all box diagrams, which can be derived by (repeated) K-moves from D(π); then

X_{π} = ∑_{B∈𝕂(π)} x^{B} .

Example 6.11. We depict 𝕂(31542) with D(π) appearing as the upper left box diagram. (The empty third level has been omitted from all box diagrams.)

× × × ××  × × × × ×  × × × × ×  × × × × × × × × × ×  × × × ××  × ×× ××  × × × ××

And indeed 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}.

Corollary 6.12. Let π ∈ S_{n} be an unembedded permutation of length p > 0, and define

\overline{𝕂}(π^{(m)}) := \{B ∈ 𝕂(π^{(m)}) | x^{B} = x_{1} … x_{p}\}

for every m ∈ ℕ_{0}. Then r(π) = |\overline{𝕂}(π^{(m)})| for m ≥ p − 1.

Proof. Immediate from Theorems 6.7 and 6.9.

This corollary opens up a combinatorial way for the determination of the numbers r(π). We remark that a box diagrams in B ∈ 𝕂(π^{(m)}) (or \overline{𝕂}(π^{(m)})) gives rise in a natural way to a labeling of D(π), which is called the retract r(B) in [W2, Def.4.1], and which in general is substantially different from the balanced labelings of [EG] and [FGRS]. It seems possible that a closer inspection of the sets 𝕂(π^{(m)}) could yield a combinatorial method for the determination of the coefficients α_{πλ} in (6.1) resp. Theorem 6.1.

Remark 6.13. A short time after finishing the present paper conversations with Mark Shimozono brought to light that the paper [RS, Thm.24] of Reiner and Shimozono contains a combinatorial algorithm for the computation of the numbers α_{πλ}. The algorithm begins with the diagram D(π) and is based on the notions of ‘plactification’ and ‘peelable tableau’. In fact it seems that this approach has been known already by Lascoux and Schützenberger and that it underlies a MAPLE routine in the package ACE, which computes the number of reduced words. Therefore it is almost certain that a related algorithm exists, which is based on the K-rule.

References

[BJS] S. Billey, W. Jockusch, R.P. Stanley, Some combinatorial properties of Schubert polynomials, J. of Algebraic Combinatorics 2 (1993), 345 -374.

[EG] P. Edelman, C. Greene, Balanced Tableaux, Advances in Math. 63 (1987), 42 - 99.

[FGRS] S. Fomin, C. Greene, V. Reiner, M. Shimozono, Balanced Labelings and Schubert Polynomials, preprint (1995).

[FK] S. Fomin, A.N. Kirillov, Reduced words and plane partitions, preprint (1995).

[FS] S. Fomin, R.P. Stanley, Schubert Polynomials and the NilCoxeter Algebra, Advances in Math. 103 (1994), 196 - 207.

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

[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, “Symmetric functions and Hall polynomials”, Clarendon Press, Oxford, 1979.

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

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

[Sa] B.E. Sagan, “The Symmetric Group”, Wadsworth & Brooks/Cole, Pacific Grove, California (1991).

[RS] V. Reiner, M. Shimozono, Plactification, J. of Algebraic Combinatorics 4 (1995), 331 - 351.

[S1] R.P. Stanley, On the Number of Reduced Decompositions of Elements of Coxeter Groups, Europ. J. Combinatorics 5 (1984), 359 - 372.

[S2] R.P. Stanley, “Enumerative Combinatorics, Volume I”, Wadsworth & Brooks/Cole, Montery CA, 1986.

[S3] R.P. Stanley, The Fibonacci lattice, Fib. Quart. 13 (1975), 215 - 232.

[T] G.P. Thomas, Frames, Young Tableaux, and Baxter Sequences, Advances in Math. 26 (1977), 275 - 289.

[W1] R. Winkel, Recursive and combinatorial properties of Schubert polynomials, preprint (1995).

[W2] R. Winkel, A combinatorial rule for the generation of Schubert polynomials, preprint (1995).

[W3] R. Winkel, Sequences of symmetric polynomials and combinatorial properties of tableaux, preprint (1995).

[W4] R. Winkel, A combinatorial bijection between standard Young tableaux and reduced words of Grassmannian permutations, Sèminaire Lotharingien et Combinatoire, B36h (1996), 24pp.

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