A MONOID FOR THE UNIVERSAL k-BRUHAT ORDER

NANTEL BERGERON AND FRANK SOTTILE

Abstract. Structure constants for the multiplication of Schubert polynomials by Schur symmetric polynomials are known to be related to the enumeration of chains in a new partial order on S_{∞}, the universal k-Bruhat order. Here we present a monoid M for this order. We show that M is analogous to the nil-Coxeter monoid for the weak order on S_{∞}. For this, we develop the theory of reduced sequences for M. We use these sequences to give a combinatorial description of the structure constants above. We also give a combinatorial proof of some of the symmetry relations satisfied by these constants.

1. Introduction

Let S_{∞} denote the infinite symmetric group consisting of permutations of {1, 2, … } which fix all but finitely many numbers. In their approach to the Schubert calculus for flag manifolds, Lascoux and Schützenberger [9, 10, 11, 12] defined Schubert polynomials 𝔖_{u} ∈ ℤ[x_{1}, x_{2}, …], a homogeneous basis indexed by permutations u ∈ S_{∞}. By construction, the degree of 𝔖_{u} is the length, ℓ(u), of u. We refer the reader to [13] for an interesting detailed account of Schubert polynomials and double Schubert polynomials. This construction has been extended to quantum Schubert polynomials for the manifolds of complete flags [5, 7] and for manifolds of partial flags [3]. In [6], W. Fulton generalizes all of these constructions.

It is a famous open problem to understand the multiplicative structure constants for the Schubert polynomials and any of their generalizations. This would provide an understanding of some Gromov-Witten invariants. From algebraic geometry, the structure constants c_{uv}^{w} defined by the identity

𝔖_{u}𝔖_{v} = ∑_{w∈S_{∞}} c_{uv}^{w}𝔖_{w}

are known to be positive integers, and in some cases they reduce to the Littlewood-Richardson coefficients. A general combinatorial construction or bijective formula for the c_{uv}^{w} is not known.

It is believed that c_{uv}^{w} counts the number of chains from u to w in the Bruhat order which satisfy conditions imposed by v [2]. In particular, if v is a Grassmannian permutation with descent in k, then one can restrict the chains to a suborder: the k-Bruhat order ≤_{k} on S_{∞} [11, 15, 2]. In [2], a study of ≤_{k} leads to a new partial order ⪯ on S_{∞} which we call the universal k-Bruhat order. This order is ranked and has the property that a nonempty interval [u, w]_{k} in a k-Bruhat order is isomorphic to the interval [1, wu^{−1}]_{⪯} in the universal order (independent of k). Every interval in Young’s lattice is an interval in this universal order. The first aim of this paper is to present a monoid M that describes the chain structure of the universal k-Bruhat order.

Date: 2 July 1997.

1991 Mathematics Subject Classification. 05E15, 14M15, 05E05.

Key words and phrases. Bruhat order, nil-Coxeter monoid, flag manifold, Grassmannian.

Bergeron supported in part by CRM, MSRI, and NSERC.

Sottile supported in part by NSF grant DMS-9022140, NSERC grant OGP0170279, and CRM.

The monoid M has a 0 and generators u_{αβ} indexed by integers 0 < α < β, subject to the relations

(1) u_{βγ}u_{γδ}u_{αγ} ≡ u_{βδ}u_{αβ}u_{βγ},  if α < β < γ < δ,
(2) u_{αγ}u_{γδ}u_{βγ} ≡ u_{βγ}u_{αβ}u_{βδ},  if α < β < γ < δ,
(3)  u_{αβ}u_{γδ} ≡ u_{γδ}u_{αβ},  if β < γ or α < γ < δ < β,
(4)  u_{αγ}u_{βδ} ≡ u_{βδ}u_{αγ} ≡ 0,  if α ≤ β < γ ≤ δ,
(5) u_{βγ}u_{αβ}u_{βγ} ≡ u_{αβ}u_{βγ}u_{αβ} ≡ 0, if α < β < γ.

(1.1)

The relation between M and the order ⪯ on S_{∞} is obtained via a faithful representation of M as linear operators on ℚS_{∞}. Let ℓ_{u} denote the rank function of ⪯. Let (α β) ∈ S_{∞} be the transposition that interchanges α and β. We define linear operators û_{αβ} by

û_{αβ} : ℚS_{∞} ⟶ ℚS_{∞},
ζ ⟼ \{ \begin{matrix}(α β)ζ & if ℓ_{u}((α β)ζ)) = ℓ_{u}(ζ) + 1, \\ 0 & otherwise. \end{matrix} (1.2)

The main results of Section 3 are summarized in the following theorem.

Theorem 1.1.

(a) The map ℓ_{u} : S_{∞} → ℕ is well defined by ℓ_{u}(ζ) = ℓ(ζu) − ℓ(u) for any u and k such that u ≤_{k} ζu.

(b) The operators û_{αβ} satisfy the relations (1.1), and a composition of operators is characterized by its value at the identity. That is û_{α′_{m}β′_{m}} ⋯ û_{α′_{1}β′_{1}} = û_{α_{n}β_{n}} ⋯ û_{α_{1}β_{1}} if and only if û_{α′_{m}β′_{m}} ⋯ û_{α′_{1}β′_{1}}1 = û_{α_{n}β_{n}} ⋯ û_{α_{1}β_{1}}1.

(c) For x = u_{α_{n}β_{n}} ⋯ u_{α_{2}β_{2}}u_{α_{1}β_{1}} ∈ M, the map x ↦ x̂ = û_{α_{n}β_{n}} ⋯ û_{α_{2}β_{2}} û_{α_{1}β_{1}} is a faithful representation of M.

(d) The following map is a well defined bijection:

M ⟶ S_{∞} ∪ {0},
x ⟼ x̂1.

(e) The universal k-Bruhat order ⪯ on S_{∞} is ranked by ℓ_{u}. We have η ⪯ ζ if and only if there exists x ∈ M such that ζ = x̂η. The order ⪯ satisfies the universal property: [u, ζu]_{k} ≅ [1, ζ]_{⪯} whenever u ≤_{k} ζu. In particular [η, ζ]_{⪯} ≅ [1, ζη^{−1}]_{⪯} whenever η ⪯ ζ.

(f) The set R_{u}(ζ) = {x̂ : x̂1 = ζ} corresponds to the set of all maximal chains in [1, ζ]_{⪯}.

We call the elements of R_{u}(ζ) the u-reduced sequences of ζ. Parts (a) and (e) of Theorem 1.1 are obtained in §3.2 of [2]. In Section 2, we relate Theorem 1.1 to classical results on the weak order of S_{∞} and the nil-Cotexer monoid.

Recall [13] that the Schur polynomial S_{λ}(x_{1}, x_{2}, …, x_{k}) = 𝔖_{v(λ,k)} for a unique Grassmannian permutation v(λ, k). In Theorem E of [2], we have shown that if c_{uv(λ,k)}^{w} ≠ 0, then c_{uv(λ,k)}^{w} depends only on λ and ζ = wu^{−1}. We can thus define constants c_{λ}^{ζ} such that c_{uv(λ,k)}^{w} = c_{λ}^{wu^{−1}} whenever u ≤_{k} w. We note that (cf. Proposition 1.1 [2])

|R_{u}(ζ)| = ∑_{λ} f^{λ}c_{λ}^{ζ},  (1.3)

where f^{λ} is the number of standard Young tableaux of shape λ. In Section 4 we give a combinatorial description of the constant c_{uv(λ,k)}^{w} using elements of R_{u}(ζ). We use this description to give a combinatorial proof of many of the symmetry relations given in [2]. In Section 5 we discuss open problems related to the monoid M and the constants c_{uv(λ,k)}^{w}.

The interested reader may obtain by email from bergerna@mathstat.yorku.ca or

find at http://www.math.yorku.ca/Who/Faculty/Bergeron two appendices. One

describes a graphical representation of chains in ⪯ which greatly helps visualize the relations (1.1) and the arguments of §3. The other describes an insertion correspondence, giving a bijection between H_{n,1}(ζ) and H_{1,n}(ζ). This is related to one open problem described in Section 5.

2. orders and monoids on S_{∞}

The weak order ≤_{weak} on S_{∞} is the transitive closure of the following cover relation: for u, w ∈ S_{∞}, we say that w covers u in the weak order if ℓ(w) = ℓ(u) + 1 and wu^{−1} is a simple transposition (α α+1). Maximal chains from the identity to w ∈ S_{∞} correspond to reduced sequences for w. The nil-Coxeter monoid N plays an important role [4, 10, 13] in studying reduced sequences. The monoid N has a 0 and generators u_{i} indexed by integers i > 0, subject to the nil-Coxeter relations:

u_{α}u_{α+1}u_{α} ≡ u_{α+1}u_{α}u_{α+1},
u_{α}u_{β} ≡ u_{β}u_{α},  if |α − β| > 1,
u_{α}u_{α} ≡ 0.

(2.1)

There is a faithful representation of N as linear operators on the group algebra ℚS_{∞}. For this, let

û_{α} : ℚS_{∞} ⟶ ℚS_{∞},
ζ ⟼ \{ \begin{matrix}(α α+1)ζ & if ℓ((α α+1)ζ) = ℓ(ζ) + 1, \\ 0 & otherwise. \end{matrix}

The following proposition is a reformulation of well known facts about reduced sequences of a permutation and the weak order. See [13] for a proof of most of them.

Proposition 2.1.

(a) The map ℓ : S_{∞} → ℕ is well defined.

(b) The operators û_{α} satisfy the relations (2.1), and a composition of operators is characterized by its value at the identity. That is û_{α_{n}} ⋯ û_{α_{1}} = û_{β_{m}} ⋯ û_{β_{1}} if and only if û_{α_{n}} ⋯ û_{α_{1}}1 = û_{β_{m}} ⋯ û_{β_{1}}1.

(c) For x = u_{α_{n}} ⋯ u_{α_{2}}u_{α_{1}} ∈ N, the map x ↦ x̂ = û_{α_{n}} ⋯ û_{α_{2}} û_{α_{1}} is a faithful representation of N.

(d) The following map is a well defined bijection:

N ⟶ S_{∞} ∪ {0},
x ⟼ x̂1.

(e) The weak order ≤_{weak} on S_{∞} is ranked by ℓ. We have u ≤_{weak} w if and only if there exists x ∈ N such that w = x̂u. Also [η, ζ]_{weak} ≅ [1, ζη^{−1}]_{weak} whenever η ≤_{weak} ζ.

(f) The set R(w) = {x̂ : x̂1 = w} corresponds to the set of all maximal chains in [1, w]_{weak}. The elements of R(w) are the reduced sequences of w.

At this point we note the striking resemblance between Theorem 1.1 and Proposition 2.1. The proof of Proposition 2.1 relies on the understanding of reduced sequences. For Theorem 1.1, the order ⪯ is new and its chains have not been studied previously. We develop the elementary theory of the analogue of reduced sequences for ⪯.

We note that not all orders on S_{∞} have such a simple monoid. In particular, the Bruhat order ≤ on S_{∞} has no known monoid. Recall that w covers u in the Bruhat order if ℓ(w) = ℓ(u) + 1 and wu^{−1} is a transposition (α β). In fact, very little is known about the problem of chain enumeration for the Bruhat order. We believe that a monoid for the Bruhat order would not satisfy conditions as simple as those of Theorem 1.1 and Proposition 2.1.

The monoid structure for the weak order was a key factor in the following results. Under the nil-Coxeter-Knuth relations

u_{α}u_{α+1}u_{α} ≡ u_{α+1}u_{α}u_{α+1},
u_{β}u_{γ}u_{α} ≡ u_{β}u_{α}u_{γ},  if α < β < γ,
u_{α}u_{γ}u_{β} ≡ u_{γ}u_{α}u_{β},  if α < β < γ,
u_{α}u_{α} ≡ 0,

(2.2)

the set of all reduced sequences R(w) for a permutation w ∈ S_{∞} is refined into classes, called Coxeter-Knuth cells, indexed by some semi-standard tableaux. The cardinality of a cell is the number of standard tableaux of the same shape as the cell’s index [4, 10, 16]. This decomposition suggests an action of the symmetric group on R(w). The symmetric function corresponding to such an action is the function F_{w} introduced by Stanley in [16]. Equation (1.3) suggests the possibility of similar structure for the monoid M and relations (1.1).

3. k-Bruhat orders and the monoid M

The multiplicative structure of Schubert polynomials is determined by Monk’s rule [13]:

𝔖_{u}(x_{1} + x_{2} + ⋯ + x_{k}) = ∑_{ℓ(u(a b)) = ℓ(u) + 1^{a≤k<b}} 𝔖_{u(a b)}.

Successive applications of this give

𝔖_{u}(x_{1} + x_{2} + ⋯ + x_{k})^{n} = ∑_{w ∈ S_{∞}_{ℓ(w)=ℓ(u)+n}} γ(u, w, k)𝔖_{w},

where γ(u, w, k) counts the sequences of transpositions (a_{1} b_{1}), (a_{2} b_{2}), …, (a_{n} b_{n}) such that w = u(a_{1} b_{1})(a_{2} b_{2}) ⋯ (a_{n} b_{n}) and, for all r, we have a_{r} ≤ k < b_{r} with

ℓ(u(a_{1} b_{1})(a_{2} b_{2}) ⋯ (a_{r−1} b_{r−1})) = ℓ(u(a_{1} b_{1})(a_{2} b_{2}) ⋯ (a_{r} b_{r})) + 1.

On the other hand

(x_{1} + x_{2} + ⋯ + x_{k})^{n} = ∑_{λ} f^{λ}S_{λ}(x_{1}, x_{2}, …, x_{k}),

where S_{λ}(x_{1}, x_{2}, …, x_{k}) is the Schur polynomial indexed by a partition λ of n. There is a unique Grassmannian permutation v(λ, k) such that S_{λ}(x_{1}, x_{2}, …, x_{k}) = 𝔖_{v(λ,k)} [13]. Hence

𝔖_{u}(x_{1} + x_{2} + ⋯ + x_{k})^{n} = ∑_{λ} f^{λ}𝔖_{u}𝔖_{v(λ,k)} = ∑_{w} (∑_{λ} f^{λ}c_{u v(λ,k)}^{w}) 𝔖_{w},

and we have

∑_{λ} f^{λ}c_{u v(λ,k)}^{w} = γ(u, w, k).  (3.1)

The equation (3.1) suggests that we should study the partial order defined by the following relation: u ≤_{k} w if and only if γ(u, w, k) > 0. Equivalently, this is the partial order with covering relation given by the index of summation in Monk’s rule. We call this suborder of the Bruhat order the k-Bruhat order. Denote by [u, w]_{k} the interval from u to w in the k-Bruhat order. Then γ(u, w, k) is the number of maximal chains in [u, w]_{k}.

These cover relations give some invariants of the k-Bruhat order. For example, consider the following maximal chain in the 3-Bruhat order:

(3, 1, 5, 2, 6, 4) ≤_{3} (3, 1, 6, 2, 5, 4) ≤_{3} (3, 2, 6, 1, 5, 4) ≤_{3} (3, 5, 6, 1, 2, 4).^{†}

In this chain, the first three entries of the permutations do not decrease and the other entries do not increase. Also, the second and third entries remain in the same relative order for all permutations in the chain. This leads to a characterization of the k-Bruhat order based on such invariants.

†Notation: For every w ∈ S_{∞} there exists infinitely many n such that w ∈ S_{n} ⊂ S_{∞}. For any such n we write (w(1), w(2), …, w(n)) to represent such a w.

Proposition 3.1 (Theorem A of [2]). For u, w ∈ S_{∞}, u ≤_{k} w if and only if

(1) u(i) ≤ w(i) for i ≤ k,

(2) u(i) ≥ w(i) for i > k,

(3) (u(i) < u(j) ⟹ w(i) < w(j)) for i < j ≤ k or k < i < j.

The sufficiency of these conditions follows from the existence of a specific maximal chain in the interval [u, w]_{k}. We call it the CM-chain of [u, w]_{k}.

Definition 3.2 (CM-chain). For u <_{k} w, the CM-chain of the interval [u, w]_{k} is recursively defined as follows:

• If ℓ(w) = ℓ(u) + 1 then the unique chain u <_{k} w is the CM-chain of [u, w]_{k}.

• If ℓ(w) > ℓ(u) + 1, let a ≤ k < b be the unique integers such that I u(a) < w(a) and w(a) = max{w(j) : j ≤ k, u(j) < w(j)}, II u(b) > u(a) ≥ w(b) and w(b) = min{w(j) : j > k, u(j) > u(a) ≥ w(j)}. Let u_{1} = u(a b). The CM-chain of [u, w]_{k} is

u = u_{0} <_{k} u_{1} <_{k} u_{2} <_{k} ⋯ <_{k} u_{n} = w,

where u_{1} <_{k} u_{2} <_{k} ⋯ <_{k} u_{n} is the CM-chain of [u_{1}, w]_{k}.

It is not obvious that conditions I and II define unique integers a ≤ k < b. We refer the reader to §3.1 of [2] for a complete proof of this fact. The symmetry in the conditions (1)-(3) of Proposition 3.1 implies the following lemma.

Lemma 3.3 (Vertical Symmetry). Let m be any integer such that u, w ∈ S_{m}. Let ω_{0} denote the longest element (m, m−1, …, 1) of S_{m}. Then the map Ω_{m} : S_{m} → S_{m} defined by Ω_{m}(u) = ω_{0}uω_{0} is an order preserving involution. That is

u ≤_{k} w  ⟺  Ω_{m}(u) ≤_{m−k} Ω_{m}(w).

We use Lemma 3.3 to define another specific maximal chain in the interval [u, w]_{k}. Given u, w ∈ S_{m}, apply Ω_{m} to the CM-chain of [Ω_{m}(u), Ω_{m}(w)]_{m−k} to obtain the DCM-chain of [u, w]_{k}. We can define it recursively, as in Definition 3.2, replacing I and II by:

I′ u(b) > w(b) and w(b) = min{w(j) : j > k, u(j) > w(j)}, II′ u(a) < u(b) ≤ w(a) and w(a) = max{w(j) : j ≤ k, u(j) < u(b) ≤ w(j)}. For example, if u = (2, 1, 6, 4, 3, 5) and w = (4, 5, 6, 1, 2, 3), the first step of the

procedure for the CM-chain of [u, w]_{3} gives us (a, b) = (2, 4). The full chain is given below, written from bottom to top.

(4, 5, 6, 1, 2, 3)  (4, 5, 6, 1, 2, 3)  (4, 5, 6, 1, 2, 3)
(3, 5, 6, 1, 2, 4)  (4, 3, 6, 1, 2, 5)  (3, 5, 6, 1, 2, 4)
(2, 5, 6, 1, 3, 4)  (4, 1, 6, 3, 2, 5)  (3, 4, 6, 1, 2, 5)
(2, 4, 6, 1, 3, 5)  (3, 1, 6, 4, 2, 5)  (2, 4, 6, 1, 3, 5)
(2, 1, 6, 4, 3, 5)  (2, 1, 6, 4, 3, 5)  (2, 1, 6, 4, 3, 5)
CM-Chain  A Maximal Chain DCM-Chain

Consider a maximal maximal chain of [u, w]_{k},

u = u_{0} <_{k} u_{1} <_{k} u_{2} <_{k} ⋯ <_{k} u_{n} = w,  (3.2)

where u_{i+1} = u_{i}(a_{i} b_{i}). We note that if (3.2) is the CM-chain, then w(a_{i}) > w(a_{j}), or w(a_{i}) = w(a_{j}) and w(b_{i}) < w(b_{j}) for all 1 ≤ i < j ≤ n. This motivates our definition of inversion. We say that (i, j) is an inversion of the chain (3.2) if 1 ≤ i < j ≤ n and

• w(a_{i}) < w(a_{j}), or

• w(a_{i}) = w(a_{j}) and w(b_{i}) > w(b_{j}).

The inversion set I of a chain is the set of all its inversions. In the example above, the inversion set of the middle maximal chain is {(1, 2), (1, 3), (1, 4), (2, 3), (2, 4)}.

Lemma 3.4. A maximal chain is the CM-chain if and only if it has no inversions.

Proof The reverse implication is clear. Consider a maximal chain with an inversion (i, j). It suffices to show there is an i′ such that (i′, i′ + 1) is also an inversion of the chain. If (i, i + 1) is an inversion then we are done. If (i, i + 1) is not an inversion then either

(a) w(a_{i}) > w(a_{i+1}) or

(b) w(a_{i}) = w(a_{i+1}) and w(b_{i}) < w(b_{i+1}).

In the first case we have w(a_{i+1}) < w(a_{i}) ≤ w(a_{j}), and in the second case we have w(a_{i+1}) = w(a_{i}) < w(a_{j}), or w(a_{i+1}) = w(a_{i}) = w(a_{j}) and w(b_{i+1}) > w(b_{i}) > w(b_{j}). Thus (i + 1, j) is an inversion. By induction on j − i we conclude that there is an i ≤ i′ < j such that (i′, i′ + 1) is an inversion of the chain.

Our next objective is to generate all the maximal chains of [u, w]_{k}. For this we need the definitions of ℓ_{u} and ⪯. The reader will find more details in [2].

Proposition 3.5 (Theorem E of [2]). For u ≤_{k} w and u′ ≤_{k′} w′, if wu^{−1} = w′(u′)^{−1}, then v ↦ vu^{−1}u′ induces [u, w]_{k} ≅ [u′, w′]_{k′}.

Proposition 3.6 (Theorem 3.1.5 of [2]). For ζ ∈ S_{∞}, let up(ζ) = {j : ζ^{−1}(j) < j} = {j_{1} < j_{2} < ⋯ < j_{k}}. Let w = (j_{1}, j_{2}, …, j_{k}, …) where, to the right of j_{k}, we put the complement of up(ζ) in increasing order. We have that [ζ^{−1}w, w]_{k} is nonempty.

We use the above two propositions to define the function ℓ_{u}. The number k in Proposition 3.6 is the smallest possible for which [u, w]_{k} is nonempty and w = ζu. The length difference ℓ(w)−ℓ(u) is the same for all nonempty [u, w]_{k} such that w = ζu. With this in mind we define ℓ_{u}(ζ) to be the length difference ℓ(w) − ℓ(u) obtained from any nonempty [u, w]_{k} such that w = ζu. This shows part (1) of Theorem 1.1. Let dw(ζ) = {j : ζ^{−1}(j) > j}. Proposition 3.6 constructs a standard interval [u, w]_{k} for any ζ. Counting the inversions of u and w, and rearranging the terms we deduce

ℓ_{u}(ζ) = |{(i, j) ∈ up(ζ) × dw(ζ) : i > j}|
−|{(i, j) ∈ ζ^{−1}(up(ζ)) × ζ^{−1}(dw(ζ)) : i > j}|
−|{(i, j) ∈ (ζ^{−1}(up(ζ)))^{2} : i < j and ζ(i) > ζ(j)}|
−|{(i, j) ∈ (ζ^{−1}(dw(ζ)))^{2} : i < j and ζ(i) > ζ(j)}|.

If u ≤_{k} ζu and u′ ≤_{k′} ζu′, then the isomorphism [u, ζu]_{k} ≅ [u′, ζu′]_{k′} is given by ηu ↦ ηu′. We now introduce the universal k-Bruhat order ⪯ on S_{∞}.

η ⪯ ζ ⟺ (There exists u, k such that u ≤_{k} ηu ≤_{k} ζu).  (3.3)

Using the permutation u given by Proposition 3.6, we see that η ⪯ ζ if and only if (1) η(α) ≤ ζ(α) for α ∈ ζ^{−1}(up(ζ)),

(2) η(α) ≥ ζ(α) for α ∈ ζ^{−1}(dw(ζ)),

(3) (η(α) < η(β) ⟹ ζ(α) < ζ(β)) for α < β ∈ ζ^{−1}(up(ζ)) or α < β ∈ ζ^{−1}(dw(ζ)). It follows from the definition that the order ⪯ is ranked by ℓ_{u} and [1, ζη^{−1}]_{⪯} ≅ [η, ζ]_{⪯} via the map ξ ↦ ξη. The operators û_{αβ} in (1.2) are defined so that û_{αβ}η = ζ if and only if ζ covers η in ⪯. In particular, nonzero compositions x̂ = û_{α_{n}β_{n}} ⋯ û_{α_{2}β_{2}} û_{α_{1}β_{1}} such that x̂η = ζ correspond bijectively to maximal chains in [η, ζ]_{⪯}:

η ⪯ û_{α_{1}β_{1}}η ⪯ û_{α_{2}β_{2}} û_{α_{1}β_{1}}η ⪯ ⋯ ⪯ x̂η = ζ

We note that the isomorphism [1, ζη^{−1}]_{⪯} ≅ [η, ζ]_{⪯} implies

x̂η = ζ ⟺ x̂1 = ζη^{−1}.  (3.4)

The isomorphism [1, wu^{−1}]_{⪯} ≅ [u, w]_{k} given by η ↦ ηu, induces an isomorphism on chains. Given a maximal chain

u = u_{0} <_{k} u_{1} <_{k} u_{2} <_{k} ⋯ <_{k} u_{n} = w  (3.5)

of [u, w]_{k}, we adopt the following conventions.

• Let a_{i} ≤ k < b_{i} be such that u_{i+1} = u_{i}(a_{i} b_{i}).

• Let α_{i} = u_{i−1}(a_{i}) and β_{i} = u_{i−1}(b_{i}). Hence u_{i} = (α_{i} β_{i})u_{i−1}. Under the isomorphism above, this defines a unique (nonzero) composition

x̂ = û_{α_{n}β_{n}} ⋯ û_{α_{2}β_{2}} û_{α_{1}β_{1}}  (3.6)

such that wu^{−1} = x̂1. Conversely, given a nonzero composition as in (3.6) such that wu^{−1} = x̂1, we define a unique maximal chain as in (3.5) where u_{i} = (û_{α_{i}β_{i}} ⋯ û_{α_{1}β_{1}}1)u. This correspondence is used to encode maximal chains for the rest of the paper. Via this identification, we will refer to a nonzero composition x̂ such that x̂1 = wu^{−1} as a maximal chain of [u, w]_{k}.

Proposition 3.6 is very useful for constructing intervals in k-Bruhat orders. For example, let ζ = (5, 4, 2, 1, 3). Proposition 3.6 gives u = (2, 1, 4, 3, 5) ≤_{2} (4, 5, 1, 2, 3) = ζu. From Definition 3.2, the CM-chain is û_{34}û_{23}û_{45}û_{14}. Now if we apply the relations (1)-(3) of (1.1) to the CM-chain we get:

û_{34}\underline{û_{23}û_{45}}û_{14} ≡ û_{34}û_{45}\underline{û_{23}û_{14}} ≡ \underline{û_{34}û_{45}û_{14}}û_{23} ≡ û_{35}\underline{û_{13}û_{34}û_{23}} ≡ û_{35}û_{23}û_{12}û_{24}.

These are all the maximal chains in the interval [u, w]_{k} as depicted in Figure 1. The first two equivalences are instances of the relation (3) of (1.1), the last two are instances of relations (1) and (2) of (1.1), respectively. The second chain is the DCM-chain.

Theorem 3.7. If u ≤_{k} w, then any two maximal chains in [u, w]_{k} are connected by a series of relations (1)-(3) of (1.1). Moreover, it is never possible to apply any of the relations (4) or (5) of (1.1) to a maximal chain.

Figure 1. The interval [(2, 1, 4, 3, 5), (4, 5, 1, 2, 3)]_{2}.

Proof We first show that any of the relations (1)-(3) of (1.1) that can be applied to a maximal chain

x̂ = û_{α_{n}β_{n}} ⋯ û_{α_{2}β_{2}} û_{α_{1}β_{1}}  (3.7)

in [u, w]_{k} results in another maximal chain. Moreover, the relations (4) and (5) can never be applied to this chain. Given the maximal chain (3.7), let u_{i} = (û_{α_{i}β_{i}} ⋯ û_{α_{1}β_{1}}1)u be as before, for 0 ≤ i ≤ n. Then since u_{i−1} ≤_{k} u_{i} is a cover,

(i) u_{i} = (α_{i} β_{i})u_{i−1} = u_{i−1}(a_{i} b_{i}) with a_{i} ≤ k < b_{i}. (ii) If α_{i} < γ < β_{i}, then u_{i−1}^{−1}(γ) < a_{i} or b_{i} < u_{i−1}^{−1}(γ).

Consider applying the relations (1.1) to a segment of length two in the chain (3.7). We may assume that the segment is û_{α_{2}β_{2}} û_{α_{1}β_{1}}. Suppose {α_{1}, β_{1}} ∩ {α_{2}, β_{2}} = ∅, and assume α_{1} < α_{2}, as the other case is symmetric. There are three possible relative orders for the numbers α_{1}, β_{1}, α_{2} and β_{2}. We consider each in turn. If α_{1} < α_{2} < β_{1} < β_{2}, the situation in relation (4) with strict inequalities, then condition (ii) for i = 1 implies a_{2} = u_{0}^{−1}(α_{2}) < a_{1}, and for i = 2 implies a_{1} = u_{1}^{−1}(β_{1}) < a_{2}, a contradiction. Now suppose α_{1} < β_{1} < α_{2} < β_{2} or α_{1} < α_{2} < β_{2} < β_{1}. An example of each case is found as a square in Figure 1. Then (i) and (ii) impose no additional conditions on a_{1}, a_{2}, b_{1} and b_{2}, so u_{0} ≤_{k} u_{0}(a_{2} b_{2}) ≤_{k} u_{0}(a_{2} b_{2})(a_{1} b_{1}) = u_{2}.

Suppose one of the relations (1) or (2) of (1.1) applies to a segment of length three. Again an example of each case is found as a hexagon in Figure 1. Both argument are similar, so suppose that (1) applies. We have α < β < γ < δ and the segment is û_{βγ}û_{γδ}û_{αγ}. By condition (ii), the numbers α, β, γ and δ appear in u in one of the following two orders

( …, β, …, α, …, γ, …, δ, …) or ( …, β, …, α, …, δ, …, γ, …).

Suppose we are in the first case, the argument in the second being similar. Then the chain is

( …, γ, …, δ, …, α, …, β, …)
( …, β, …, δ, …, α, …, γ, …)
( …, β, …, γ, …, α, …, δ, …)
( …, β, …, α, …, γ, …, δ, …)

It is clear that

( …, γ, …, δ, …, α, …, β, …)
( …, γ, …, β, …, α, …, δ, …)
( …, γ, …, α, …, β, …, δ, …)
( …, β, …, α, …, γ, …, δ, …)

is also a chain. This is represented by û_{βδ}û_{αβ}û_{βγ}, completing this case. To conclude our first objective, we notice that the fourth relation, with equalities, or the fifth relation, are clearly not possible for k-Bruhat orders, by Proposition 3.1 (1) and (2).

We now show that any two maximal chains in [u, w]_{k} are connected by successive uses of the relations (1.1). It suffices to show that any maximal chain x̂ is connected to the CM-chain. For this we proceed by induction on n. If n = 1, then there is a unique maximal chain. Let n > 1 and assume that the theorem holds for all intervals [u′, w′]_{k′} such that ℓ(w′) − ℓ(u′) < n. That is, we may assume that x̂ = ŷû_{α_{1}β_{1}} where y is any maximal chain. If a_{1}, b_{1} satisfy the conditions I and II of Definition 3.2 then choosing ŷ to be the CM-chain of [u_{1}, w]_{k} completes the proof since then x̂ is the CMchain of [u, w]_{k}. If condition I fails, then w(a_{1}) is not maximal with u(a_{1}) < w(a_{1}). In this case assume that ŷ is the CM-chain of [u_{1}, w] so that w(a_{2}) > w(a_{1}). We have two sub-cases to consider: Case 1a: {α_{1}, β_{1}} ∩ {α_{2}, β_{2}} = ∅. We can use relation (3) of (1.1) and get

x̂ ≡ û_{α_{n}β_{n}} ⋯ û_{α_{1}β_{1}} û_{α_{2}β_{2}}.  (3.8)

The hypothesis on y and w(a_{2}) > w(a_{1}) implies that û_{α_{2}β_{2}} is the first step of the CM-chain of [u, w]_{k}. We can use our induction hypothesis on [û_{α_{2}β_{2}}u, w]_{k} and get x̂ ≡ ẑû_{α_{2}β_{2}}, t he CM-chain of [u, w]_{k}. Case 1b: α_{2} < β_{2} = α_{1} < β_{1}. Since y is the CM-chain of [u_{1}, w]_{k}, we have

β_{2} = α_{3} < β_{3} = α_{4} < ⋯ < β_{m−1} = α_{m},

for m ≥ 3, where β_{m} = w(a_{2}) > w(a_{1}) ≥ β_{1}. Let 3 ≤ s ≤ m be such that α_{s} < β_{1} < β_{s}. We can apply the relations (1.1) and get

x̂ = û_{α_{n}β_{n}} ⋯ û_{α_{m}β_{m}} ⋯ û_{α_{s}α_{s}} cdotsû_{α_{2}β_{2}} û_{α_{1}β_{1}}
≡ û_{α_{n}β_{n}} ⋯ û_{α_{m}β_{m}} ⋯ û_{α_{s+1}α_{s+1}} û_{α_{s}β_{1}} û_{β_{1}β_{s}} û_{α_{2}β_{1}} û_{α_{s−1}β_{s−1}} ⋯ û_{α_{3}β_{3}}
≡ û_{α_{n}β_{n}} ⋯ û_{α_{m}β_{m}} ⋯ û_{α_{s+1}α_{s+1}} û_{α_{s}β_{1}} û_{α_{s−1}β_{s−1}} ⋯ û_{α_{3}β_{3}} û_{β_{1}β_{s}} û_{α_{2}β_{1}}
≡ ẑû_{α_{2}β_{1}}.

where, by the induction hypothesis, ẑ is the CM-chain of [û_{α_{1}β_{2}}u, w]_{k}. Here û_{α_{2}β_{1}} is the first step in the CM-chain of [u, w]_{k}. Hence x̂ ≡ ẑû_{α_{2}β_{1}}, the CM-chain of [u, w]_{k}.

If condition I holds but condition II fails, then w(b_{1}) is not minimal. In this case assume that y is the DCM-chain of [u_{1}, w]. Here, we must have that w(b_{2}) < w(b_{1}) and again we have two sub-cases to consider: Case 2a: {α_{1}, β_{1}} ∩ {α_{2}, β_{2}} = ∅. We can use the relation (3) of (1.1) and the induction hypothesis to get

x̂ ≡ û_{α_{n}β_{n}} ⋯ û_{α_{1}β_{1}} û_{α_{2}β_{2}} ≡ ẑû_{α_{2}β_{2}},  (3.9)

where ẑ is the CM-chain of [û_{α_{2}β_{2}}u, w]_{k}. If û_{α_{2}β_{2}} is the first step in the CM-chain of [u, w]_{k} we are done. If not, then condition I′ on û_{α_{2}β_{2}} implies that only condition I can fail in ẑû_{α_{2}β_{2}} and we are back to cases 1a or 1b. Case 2b: α_{1} < β_{1} = α_{2} < β_{2}. Since y is the DCM-chain of [u_{1}, w]_{k}, we have

α_{2} = β_{3} > α_{3} = β_{4} > ⋯ > α_{m−1} = β_{m},

for m ≥ 3, where α_{m} = w(b_{2}) > w(b_{1}) ≥ α_{1}. Let 3 ≤ s ≤ m be such that β_{s} > α_{1} > α_{s}. We can apply the relations (1.1) and get

x̂ = û_{α_{n}β_{n}} ⋯ û_{α_{m}β_{m}} ⋯ û_{α_{s}α_{s}} ⋯ û_{α_{2}β_{2}} û_{α_{1}β_{1}}
≡ û_{α_{n}β_{n}} ⋯ û_{α_{m}β_{m}} ⋯ û_{α_{s+1}α_{s+1}} û_{α_{1}β_{s}} û_{α_{s}β_{1}} û_{α_{1}β_{2}} û_{α_{s−1}β_{s−1}} ⋯ û_{α_{3}β_{3}}
≡ û_{α_{n}β_{n}} ⋯ û_{α_{m}β_{m}} ⋯ û_{α_{s+1}α_{s+1}} û_{α_{1}β_{s}} û_{α_{s−1}β_{s−1}} ⋯ û_{α_{3}β_{3}} û_{α_{s}β_{1}} û_{α_{1}β_{2}}
≡ ẑû_{α_{1}β_{2}},

(3.10)

where ẑ is the CM-chain of [û_{α_{1}β_{2}}u, w]_{k}. If û_{α_{1}β_{2}} is the first step in the CM-chain of [u, w]_{k}, then we are done. If not, then condition I′ on û_{α_{1}β_{2}} implies that only the condition I can fail in ẑû_{α_{2}β_{2}} and again we are back to cases 1a or 1b.

We now complete the characterization of compositions x̂ = û_{α_{n}β_{n}} ⋯ û_{α_{1}β_{1}} which correspond to maximal chains for some [u, w]_{k}. If x̂ corresponds to a maximal chain in [u, w]_{k}, then wu^{−1} = x̂. Hence w = ζu where ζ = x̂1 = wu^{−1}. Conversely, Proposition 3.6 shows that for any ζ ∈ S_{∞} we can find u and w such that w = ζu and [u, w]_{k} is nonempty for some k. In the following, we say that a composition x̂ = û_{α_{n}β_{n}} ⋯ û_{α_{1}β_{1}} is u-reduced if x̂1 ≠ 0. Theorem 3.7 gives us a way of generating all u-reduced sequences for ζ ∈ S_{∞}; they are all connected via the relations (1)-(3) of (1.1). To complete our study, we need to characterize the compositions x̂ such that x̂ = 0.

Theorem 3.8. Let x̂ = û_{α_{n}β_{n}} ⋯ û_{α_{1}β_{1}} be a composition. If x̂1 = 0, then x̂ ≡ 0 modulo the relations (1.1).

Proof We proceed by induction on n. When n = 2, x̂1 = 0 implies that relation (4) applies to x̂. Suppose n ≥ 3 and the theorem holds for all compositions of length < n. Let ŷ = û_{α_{n−1}β_{n−1}} ⋯ û_{α_{1}β_{1}} and we may assume that ŷ1 = τ ≠ 0.

We first characterize those w such that τ^{−1}w ≤_{k} w, for some k. Let up(τ) and dw(τ) be defined as above, and let fix(τ) be the set of fixed points of τ. By Proposition 3.1, u = τ^{−1}w ≤_{k} w if and only if

• up(τ) ⊆ {w(i) : 1 ≤ i ≤ k} ⊆ up(τ) ∪ fix(τ),
• for i < j ≤ k or k < i < j, if u(i) < u(j) then w(i) < w(j).

(3.11)

The second condition implies that if α < γ are in up(τ)∪fix(τ) and τ^{−1}(α) > τ^{−1}(γ), then max{w^{−1}(α), w^{−1}(γ)} ≤ k implies w^{−1}(α) < w^{−1}(γ). Similarly, if γ < β are in dw(τ) ∪ fix(τ) and τ^{−1}(γ) > τ^{−1}(β) then k < min{w^{−1}(β), w^{−1}(γ) ≤ k} implies w^{−1}(γ) < w^{−1}(β). With this and the definition of ⪯, we see that ℓ_{u}((α_{n}, β_{n})τ) ≠ ℓ_{u}(τ) + 1 implies one of the following holds:

(a) α_{n} ∈ dw(τ),

(b) β_{n} ∈ up(τ),

(c) α_{n} < γ < β_{n} where τ^{−1}(α_{n}) > τ^{−1}(γ), or τ^{−1}(γ) > τ^{−1}(β_{n}).

We complete the proof by showing that each case (a), (b), or (c) implies û_{α_{n}β_{n}} ŷ ≡ 0 modulo the relations (1.1). If (a) holds: By Theorem 3.7 we may assume that ŷ is any maximal chain. Let ŷ = ẑû_{α_{1}β_{1}}. Note that if α_{n} ∈ dw(ẑ1) then the induction hypothesis applies and we are done. We can thus assume that α_{n} = α_{1}. But this must be true for any maximal chain ŷ. Since α_{1} = min (dw(τ)) for the DCM-chain, we have α_{n} = min (dw(τ)). Now let ŷ be the CM-chain, and consider its initial segment û_{α_{m}β_{m}} ⋯ û_{α_{1}β_{1}} where β_{1} = α_{2} < β_{2} = α_{3} < ⋯ < β_{m−1} = α_{m} and β_{m} = max (up(τ)). If |up(τ)| > 1, then m < n − 1. Consider the next operator û_{α_{m+1}β_{m+1}}. Since α_{1} = min (dw(τ)), we have α_{1} < α_{m} + 1, and since β_{m} = max (up(τ)), we have β_{m+1} < β_{m}. Thus we may apply a sequence of the relations (1)-(3) of (1.1), as in (3.10), to obtain ŷ ≡ ẑ′û_{α_{m+1}β′} for some ẑ′ and β′. Since α_{n} = α_{1} ∈ dw(ẑ′1), the induction hypothesis applies to conclude û_{α_{n}β_{n}} ẑ′ ≡ 0. Thus we may assume that (a) holds and |up(τ)| = 1. That is, β_{1} = α_{2} < β_{2} = α_{3} < ⋯ < β_{n−2} = α_{n−1} and α_{n} = α_{1}. If β_{n} < α_{n−1} or β_{n} > β_{n−1} then we apply relation (3) to obtain û_{α_{n}β_{n}} ŷ ≡ û_{α_{n−1}β_{n−1}} û_{α_{n}β_{n}} û_{α_{n−2}β_{n−2}} ⋯ û_{α_{1}β_{1}} ≡ û_{α_{n−1}β_{n−1}} ŷ′, and ŷ′ ≡ 0 by the induction hypothesis. If β_{n} = α_{n−1} then we may apply relation (2) to obtain û_{α_{n}β_{n}} x̂ ≡ û_{α_{n−2}β_{n−2}} û_{α_{n}α_{n−2}} û_{α_{n−2}β_{n−1}} ⋯ û_{α_{1}β_{1}}, which is equivalent to 0 as before. Finally if α_{n−1} < β_{n} ≤ β_{n−1} then û_{α_{n}β_{n}} û_{α_{n−1}β_{n−1}} ≡ 0 If (b) holds: This case is similar to (a), the map Ω_{n} from Lemma 3.3 can be used to interchange the roles of conditions (a) and (b). If (c) holds: Assume that τ^{−1}(α_{n}) > τ^{−1}(γ). The other case, τ^{−1}(γ) > τ^{−1}(β_{n}), is argued in a similar fashion using the map Ω_{n}. We may also assume that (a) does not hold, hence we have τ^{−1}(γ) < τ^{−1}(α_{n}) ≤ α_{n} < γ < β_{n} and, in particular, γ ∈ up(τ). Let γ be minimal with these properties. We may assume that ŷ is the CM-chain and we let ŷ = û_{α_{n−1}β_{n−1}} ẑ and ẑ1 = σ ∈ S_{∞}. In this case β_{n−1} = min (up(τ)) ≤ γ. If β_{n−1} < γ then the minimality of γ implies β_{n−1} ≤ α_{n}. We have a four sub-cases to consider:

(i) If β_{n−1} = γ and α_{n−1} ≤ α_{n}, then û_{α_{n}β_{n}} û_{α_{n−1}β_{n−1}} ≡ 0 is an instance of relation (4) of (1.1).

(ii) If β_{n−1} = γ and α_{n−1} > α_{n}, then û_{α_{n}β_{n}} ŷ ≡ û_{α_{n−1}β_{n−1}} û_{α_{n}β_{n}} ẑ. Since τ^{−1}(γ) < α_{n} and x is the CM-chain, we must have β_{n−2} = α_{n−1}. So α_{n} < α_{n−1} = β_{n−2} < γ < β_{n} and σ^{−1}(β_{n−2}) = τ^{−1}(γ) < α_{n}. By the induction hypothesis û_{α_{n}β_{n}} ŷ ≡ 0.

(iii) If β_{n−1} < α_{n}, then û_{α_{n}β_{n}} ŷ ≡ û_{α_{n−1}β_{n−1}} û_{α_{n}β_{n}} ẑ where σ^{−1}(β_{n−2}) = τ^{−1}(γ). The induction hypothesis applies and again û_{α_{n}β_{n}} ẑ ≡ 0.

(iv) If β_{n−1} = α_{n}, then since ŷ is the CM-chain, the minimality of γ implies that β_{m} = γ < β_{n} for some 1 ≤ m ≤ n − 2, with

α_{n} = β_{n−1} > α_{n−1} = β_{n−2} > ⋯ > α_{m+2} = β_{m+1} > α_{m+1}.

For some 1 ≤ s ≤ m we also have

γ = β_{m} > α_{m} = β_{m−1} > ⋯ > α_{s+1} = β_{s},

where α_{s} = τ^{−1}(γ) < τ^{−1}(α_{n}) = α_{m+1}. If s > 1 we may appeal to the induction hypothesis and get û_{α_{n}β_{n}} ŷ ≡ 0. Thus we may assume that s = 1. Also, since α_{1} < α_{m+1} < β_{m+1} ≤ α_{n} < γ = β_{m} we may apply relations (1)-(3) as in (3.10) to obtain

û_{α_{m+1}β_{m+1}} û_{α_{m}β_{m}} ⋯ û_{α_{1}β_{1}} ≡ û_{α′_{m}β′_{m}} ⋯ û_{α′_{1}β′_{1}} û_{α_{m+1}β_{m+1}},

where γ = β_{m} = β′_{m}, β′_{m−1} = α′_{m}, β′_{m−2} = α′_{m−1}, …, β′_{1} = α′_{2} and α′_{1} = α_{1}. Hence we can use the induction hypothesis on û_{α_{n}β_{n}} ⋯ û_{α_{m+2}β_{m+2}} û_{α′_{m}β′_{m}} ⋯ û_{α′_{1}β′_{1}}, to obtain

û_{α_{n}β_{n}} ⋯ û_{α_{m+2}β_{m+2}} û_{α′_{m}β′_{m}} ⋯ û_{α′_{1}β′_{1}} ≡ 0,

and this concludes our proof.

Proof [of Theorem 1.1]

(a) This is a direct consequence of Proposition 3.5 and Proposition 3.6.

(b) Theorem 3.7 and Theorem 3.8 imply that the operators û_{αβ} satisfy the relations (1.1). Equation (3.4) gives the characterization part.

(c) This is a consequence of (b), Theorem 3.7, and Theorem 3.8.

(d) Injection is from part (b) and (c). Surjection is given by Proposition 3.6.

(e) Follows from the definitions of ⪯ and û_{αβ}.

(f) This is a direct consequence (a)-(f) above.

The universal k-Bruhat order is a very interesting object to study on its own. Numerous other results of [2] can be translated to the monoid M and on the universal k-Bruhat order. We consider a few in the next section.

4. A Combinatorial description of c_{λ}^{ζ}.

We give a combinatorial description of the constants c_{λ}^{ζ} appearing in Equation (1.3) and combinatorial proofs of many of the identities of [2]. Recall that the Schur polynomial S_{λ}(x_{1}, x_{2}, …, x_{k}) equals 𝔖_{v(λ,k)} for a unique Grassmannian permutation v(λ, k). We have

𝔖_{u}𝔖_{v(λ,k)} = ∑_{w} c_{uv(λ,k)}^{w}𝔖_{w}.  (4.1)

First we consider a special case of (4.1). The Schubert polynomial 𝔖_{v((n),k)} = h_{n}(x_{1}, x_{2}, …, x_{k}) is the homogeneous symmetric polynomial on k variables. Lascoux and Schützenberger [9] formulated a Pieri-type formula for 𝔖_{u}𝔖_{v((n),k)}. In [1], proven in [15], we have reformulated this rule. Using Theorem 1.1, we can state it here as follows:

𝔖_{u}𝔖_{v((n),k)} = ∑_{x̂ = û_{α_{n}β_{n}} ⋯ û_{α_{1}β_{1}} ≢ 0_{α_{1}<α_{2}<···<α_{n}}} 𝔖_{(x̂1)u}.  (4.2)

There are now other proofs of (4.2), some of them are combinatorial [14, 17]. Let p = (p_{1}, p_{2}, …, p_{r}) be a sequence of r integers such that p_{1} + p_{2} + ⋯ + p_{r} = n. We say that a u-composition x̂ = û_{α_{n}β_{n}} ⋯ û_{α_{1}β_{1}} weakly fits p if

α_{1} < α_{2} < ⋯ < α_{p_{1}},
α_{p_{1}+1} < α_{p_{1}+2} < ⋯ < α_{p_{1}+p_{2}},
⋮
α_{n−p_{r}+1} < α_{n−p_{r}+2} < ⋯ < α_{n},

and for all i, we have p_{i} ≥ 0. Let H_{p}(ζ) = {x̂ ∈ R_{u}(ζ) : ζ = x̂1 and x̂ weakly fits p}. Note that H_{p}(ζ) = ∅ if some p_{i} < 0.

Remark 4.1. From (4.2), H_{p}(wu^{−1}) is the coefficient of 𝔖_{w} in the product

𝔖_{u}𝔖_{v((p_{1}),k)}𝔖_{v((p_{2}),k)} ⋯ 𝔖_{v((p_{r}),k)}

when all p_{i} > 0.

Now consider the Jacobi identity [13]: for λ = (λ_{1}, λ_{2}, …, λ_{r}) a partition of n,

𝔖_{v(λ,k)} = S_{λ}(x_{1}, x_{2}, …, x_{k}) = det (h_{λ_{i}+j−i}(x_{1}, x_{2}, …, x_{k}))_{1≤i,j≤r} ,  (4.3)

where h_{0}(x_{1}, x_{2}, …, x_{k}) = 1, h_{n}(x_{1}, x_{2}, …, x_{k}) = 𝔖_{v((n),k)} for n > 0, and h_{n} = 0 for n < 0. For σ ∈ S_{r}, let λ_{σ} = (λ_{σ}(1), λ_{σ}(2), …, λ_{σ}(r)), where λ_{σ}(i) = λ_{σ(i)} + i − σ(i). Denote by ϵ(σ) the sign of the permutation σ ∈ S_{r}. Expanding the determinant (4.3) in (4.1), and using (4.2), we get

𝔖_{u}𝔖_{v(λ,k)} = ∑_{σ∈S_{r}} ϵ(σ)𝔖_{u}𝔖_{v((λ_{σ}(1)),k)}𝔖_{v((λ_{σ}(2)),k)} ⋯ 𝔖_{v((λ_{σ}(r)),k)}

= ∑_{w∈S_{∞}} (∑_{σ∈S_{r}} ϵ(σ) |H_{λ_{σ}}(wu^{−1})|) 𝔖_{w}.

Thus

c_{uv(λ,k)}^{w} = ∑_{σ∈S_{r}} ϵ(σ) |H_{λ_{σ}}(wu^{−1})| .  (4.4)

This is a consequence of Theorem 1.1. From this we deduce the following proposition.

Proposition 4.2.

(1) c_{uv(λ,k)}^{w} = 0 if u ≰_{k} w, and

(2) if u ≤_{k} w then c_{uv(λ,k)}^{w} depends only on λ and wu^{−1}.

Hence, we have that c_{λ}^{ζ} = c_{uv(λ,k)}^{w} is well defined for any u ≤_{k} w with ζ = wu^{−1}. We have

Theorem 4.3. c_{λ}^{ζ} = ∑_{σ∈S_{r}} ϵ(σ) |H_{λ_{σ}}(ζ)|.

Let us illustrate Theorem 4.3 on an example. Let ζ = (2, 5, 4, 1, 6, 3). Using Proposition 3.6 we have (3, 1, 2, 5, 6, 4) = u ≤_{4} ζu = (4, 2, 5, 6, 3, 1). In Figure 2, we have drawn the interval [u, ζu]_{4} and we have labeled each covering edge in the interval by the index α of the corresponding û_{αβ}. Here we have removed the commas and parentheses to represent the permutations in a more compact form. Note that there are 14 maximal chains in this interval.

Theorem 4.3 gives us that

c_{(2,2,1)}^{ζ} = |H_{(2,2,1)}(ζ)| − |H_{(1,3,1)}(ζ)| − |H_{(2,0,3)}(ζ)| + |H_{(1,0,4)}(ζ)|
+ |H_{(−1,3,3)}(ζ)| − |H_{(−1,2,4)}(ζ)| .

The sets H_{(−1,3,3)}(ζ) and H_{(−1,2,4)}(ζ) are both empty since the indices contains a negative component. Looking at Figure 2, we find

H_{(2,2,1)}(ζ) = {û_{12}û_{35}û_{23}û_{56}û_{34}, û_{34}û_{45}û_{12}û_{56}û_{24}}

and H_{(1,3,1)}(ζ) = H_{(2,0,3)}(ζ) = ∅. Hence c_{(2,2,1)}^{ζ} = 2. Now for λ = (2, 1, 1, 1) and σ ∈ S_{4}, the sequences λ_{σ} that do not contains a negative component are (2, 1, 1, 1), (2, 1, 0, 2), (2, 0, 2, 1), (2, 0, 0, 3), (0, 3, 1, 1), (0, 3, 0, 2), (0, 0, 4, 1) and (0, 0, 0, 5). For our example, we have |H_{(2,1,1,1)}(ζ)| = 5, |H_{(2,1,0,2)}(ζ)| = 2, |H_{(2,0,2,1)}(ζ)| = 2 and all the others are empty. Hence c_{(2,1,1,1)}^{ζ} = 5 − 2 − 2 = 1. Using (1.3) for this example, we get c_{λ}^{ζ} = 0 for the other λ, since 14 = 5 ∗ 2 + 4 ∗ 1 is the total number of maximal chains.

With Theorem 4.3, we are able to show combinatorialy many of the symmetries of the c_{λ}^{ζ} that were first shown using geometry in [2]. Let us start with symmetries derived from algebraic structures in the cohomology of the flag manifolds. If ζ ∈ S_{n} ⊂ S_{∞}, let ω_{0} = (n, n − 1, …, 3, 2, 1) be the longest element of S_{n}. As in Lemma 3.3, the vertical and horizontal symmetries of (1.1) imply the following lemmas.

Lemma 4.4. The following map (vertical symmetry) is a bijection

Ψ_{v}: R_{u}(ζ)  ⟶ R_{u}(ω_{0}ζω_{0})
û_{α_{n}β_{n}} ⋯ û_{α_{1}β_{1}} ⟼ û_{ω_{0}(β_{n})ω_{0}(α_{n})} ⋯ û_{ω_{0}(β_{1})ω_{0}(α_{1})}

Lemma 4.5. The following map (horizontal symmetry) is a bijection

Ψ_{h}: R_{u}(ζ)  ⟶ R_{u}(ζ^{−1})
û_{α_{n}β_{n}} ⋯ û_{α_{1}β_{1}} ⟼ û_{α_{1}β_{1}} ⋯ û_{α_{n}β_{n}}

Given a non-degenerate hermitian form on ℂ^{n}, we get an involution on the flag manifold induced by taking orthogonal complements. On the Schubert basis, this corresponds to 𝔖_{w} ↦ 𝔖_{ω_{0}wω_{0}} and 𝔖_{v(λ,k)} ↦ 𝔖_{v(λ^{t},n−k)}, where λ^{t} denotes the conjugate partition. Thus c_{λ}^{ζ} = c_{λ^{t}}^{ω_{0}ζω_{0}}. Also c_{uv(λ,k)}^{w} is the coefficient of 𝔖_{ω_{0}} in 𝔖_{ω_{0}w}𝔖_{u}𝔖_{v(λ,k)}.

Interchanging the roles of u and w gives c_{λ}^{ζ} = c_{λ}^{ω_{0}ζ^{−1}ω_{0}}. Combining these, we get c_{λ}^{ζ} = c_{λ^{t}}^{ζ^{−1}}. Here we show these identities directly from Theorem 4.3 and its dual version.

Corollary 4.6. c_{λ}^{ζ} = c_{λ^{t}}^{ζ^{−1}}.

Proof We note that both (4.2) and the Jacobi identity have dual versions. For this, let 1^{n} denote the partition conjugate to (n), that is (1, 1, …, 1). From [15] or other formulations, the reader deduces that

𝔖_{u}𝔖_{v(1^{n},k)} = ∑_{x̂ = û_{α_{n}β_{n}} ⋯ û_{α_{1}β_{1}} ≢ 0_{α_{1}>α_{2}>···>α_{n}}} 𝔖_{(x̂1)u}.  (4.5)

Here 𝔖_{v(1^{n},k)} = e_{n}(x_{1}, x_{2}, …, x_{k}) is the nth elementary symmetric polynomial. On the other hand, we know from [13] that

𝔖_{v(λ^{t},k)} = S_{λ^{t}}(x_{1}, x_{2}, …, x_{k}) = det (e_{λ_{i}+j−i}(x_{1}, x_{2}, …, x_{k}))_{1≤i,j≤r} .  (4.6)

For p ∈ ℤ^{r}, we define E_{p}(ζ) = ∅ if p_{i} < 0 for some i, and set E_{p}(ζ) to be

{x̂ ∈ R_{u}(ζ) : α_{1} > ⋯ > α_{p_{1}}; α_{p_{1}+1} > ⋯ > α_{p_{1}+p_{2}}; …; α_{n−p_{r}+1} > ⋯ > α_{n}}.

otherwise. With computations similar to (4.4), using a different expansion for the determinant (4.6), we deduce that

c_{λ^{t}}^{ζ} = ∑_{σ∈S_{r}} ϵ(σ) |E\overleftarrow{λ_{σ}}(ζ)| ,  (4.7)

where for p = (p_{1}, p_{2}, …, p_{r}) we define \overleftarrow{p} = (p_{r}, …, p_{2}, p_{1}). Now we note that Ψ_{h} in Lemma 4.5 maps H_{p}(ζ) bijectively to E\overleftarrow{p}(ζ^{−1}). Hence by Theorem 4.3, the equation (4.7) is equal to c_{λ}^{ζ}.

Corollary 4.7. c_{λ}^{ζ} = c_{λ^{t}}^{ω_{0}ζω_{0}}.

Proof We only sketch the proof here since it is very similar to that of Corollary 4.6. First, we use a different version of (4.5), see [15]:

𝔖_{u}𝔖_{v(1^{n},k)} = ∑_{x̂ = û_{α_{n}β_{n}} ⋯ û_{α_{1}β_{1}} ≢ 0_{β_{1}>β_{2}>···>β_{n}}} 𝔖_{(x̂1)u}.

From this we define E′_{p}(ζ) to be

{x̂ ∈ R_{u}(ζ) : β_{1} > ⋯ > β_{p_{1}}; β_{p_{1}+1} > ⋯ > β_{p_{1}+p_{2}}; …; β_{n−p_{r}+1} > ⋯ > β_{n}}

for p ∈ ℕ^{r}. We deduce that

c_{λ^{t}}^{ζ} = ∑_{σ∈S_{r}} ϵ(σ) |E′_{λ_{σ}}(ζ)| .  (4.8)

Finally we note that Ψ_{v} in Lemma 4.4 maps H_{p}(ζ) bijectively to E′_{p}(ζ) and this concludes our proof.

For an integer a, let ϕ_{a}: ℕ → ℕ be defined by ϕ_{a}(i) = i if i < a, and ϕ_{a}(i) = i + 1 if i ≥ a. This map ϕ_{a} induces an imbeding ϕ_{a}^{∗}: S_{∞} → S_{∞} where ζ′ = ϕ_{a}^{∗}(ζ) is the unique permutation defined by ζ′(a) = a and ϕ_{a} ∘ ζ′ = ζ ∘ ϕ_{a}. If fact, ϕ_{a} also induces a monomorphism ϕ_{a}^{∗}: M → M where ϕ_{a}^{∗}(û_{αβ}) = û_{ϕ_{a}(α)ϕ_{a}(β)}. This is obvious since the map ϕ_{a}^{∗} sends generators to generators and preserves the relations. This shows that ϕ_{a}^{∗}: S_{∞} → S_{∞} is also ⪯-order preserving.

Lemma 4.8. ϕ_{a}^{∗}: R_{u}(ζ) → R_{u}(ϕ_{a}^{∗}(ζ)) is a bijection.

As far as we know, the next corollary was first discovered in [2] using geometry.

Corollary 4.9 (Theorem 5.1.1 of [2]). c_{λ}^{ζ} = c_{λ}^{ϕ_{a}^{∗}(ζ)}.

Proof This follows directly from Theorem 4.3 since ϕ_{a}^{∗}(H_{p}(ζ)) = H_{p}(ϕ_{a}^{∗}(ζ)).

A. Postnikov has communicated to us that he has also found combinatorial proofs of some of these identities, particuliarly Proposition 4.2 and Corollary 4.9.

5. Open Problems.

One of the most enigmatic identities of [2] is the following proposition:

Proposition 5.1 (Theorem H of [2]). Let γ = (1, 2, 3, …, n) and ζ be in S_{n}. Then

c_{λ}^{ζ} = c_{λ}^{γζγ^{−1}}.

This was obtained using geometry, and as of now, we do not know how to show this combinatorially. We note that (1.3) implies that |R_{u}(ζ)| = |R_{u}(γζγ^{−1})|. This suggests the existence of a bijection

φ: R_{u}(ζ) ⟶ R_{u}(γζγ^{−1}).  (5.1)

Note that the two Posets [1, ζ]_{⪯} and [1, γζγ^{−1}]_{⪯} are not necessarily isomorphic. For example let ζ = (2, 4, 1, 3), the interval [1, γζγ^{−1}]_{⪯} is a hexagon and [1, ζ]_{⪯} is not, it is a kite. For our next problem, we remark that the Jacobi identity (4.3) is invertible, hence Proposition 5.1 implies that |H_{p}(ζ)| = |H_{p}(γζγ^{−1})| for any p.

Problem 5.2. Construct a bijection φ as in (5.1) such that φ(H_{p}(ζ)) = H_{p}(γζγ^{−1}).

A positive answer to this problem, combined with Theorem 4.3, would give a combinatorial proof of Proposition 5.1.

Another direction of inquiry is to improve on Theorem 4.3. It is a useful combinatorial description of the c_{λ}^{ζ} but it is very unsatisfactory. It would be more elegant to have a formula that does not involve signs. Using symmetric polynomials [13], we know that

𝔖_{v((p_{1}),k)}𝔖_{v((p_{1}),k)} ⋯ 𝔖_{v((p_{1}),k)} = 𝔖_{v(λ,k)} + ∑_{μ◁λ} a_{λμ}𝔖_{v(μ,k)},  (5.2)

where λ = λ(p) is the partition of n obtained by rearranging the numbers p_{1}, p_{2}, …, p_{r} in decreasing order, and ◁ is the strict dominance order on partitions. Iterating (4.2) and using (5.2) it becomes clear that c_{λ}^{ζ} ≤ |H_{p}(ζ)| for any p such that λ(p) = λ. Now, let D_{λ}(ζ) = ∑_{σ∈S_{r}} H_{λ_{σ}}(ζ) where the sum here denotes the disjoint union of sets. In general, a chain x̂ of [1, ζ]_{⪯} weakly fits many compositions of n. We use pairs (x̂, σ) to describe elements in D_{λ}(ζ) meaning that x̂ ∈ H_{λ_{σ}}(ζ). We extend the definition of ϵ to pairs (x̂, σ) by setting ϵ(x̂, σ) = ϵ(σ). The Equation (4.4) can be rewritten as

c_{λ}^{ζ} = ∑_{(x̂,σ)∈D_{λ}} ϵ(x̂, σ).

In many cases, we can construct an involution θ : D_{λ}(ζ) → D_{λ}(ζ) such that

(i) θ(x̂, σ) = (x̂, σ) only if σ is the identity, and (ii) if θ(x̂, σ) ≠ (x̂, σ) then ϵ(θ(x̂, σ)) = −ϵ(x̂, σ).

When this happens, we get a very nice combinatorial construction of c_{λ}^{ζ} since

c_{λ}^{ζ} = ∑_{x̂ ∈ H_{λ}_{θ(x̂,1)=(x̂,1)}} 1 = |{x̂ ∈ H_{λ} : θ(x̂, 1) = (x̂, 1)}| .  (5.3)

Problem 5.3. Find an involution θ : D_{λ}(ζ) → D_{λ}(ζ) for any ζ and λ.

With λ = (2, 1, 1, 1) and ζ = (1, 4, 3, 5, 6, 2), as in Figure 2, the set D_{λ}(ζ) contains nine elements. Here, it is clear how to construct θ and the only fixed point of θ is the chain û_{12}û_{34}û_{45}û_{56}û_{24}.

It is interesting to note that among all the previously proposed conjectures to describe the c_{λ}^{ζ} combinatorially, none works. Using the monoid M, it is relatively easy to test them against Equation (1.3). We use Proposition 3.6 to get u ≤_{k} w = ζu. We then use Theorem 3.7 to produce all maximal chains in [1, ζ]_{⪯} from the CM-chain. Finally we compare the two sides of (1.3). For example, in [18], it is suggested that if we display the numbers β_{1}, β_{2}, …, β_{n} in a right adjusted shape λ, then c_{λ}^{ζ} counts the number of chains that weakly fit λ and are strictly decreasing in every column (using the β’s). A small counterexample to this is obtained using ζ = (3, 5, 4, 2, 1).

In the cases where we know how to construct the involution θ, we have used a Schensted-like insertion algorithm. This is an explicit correspondence H_{(1,n)}(ζ) ⟶ H_{(n,1)}(ζ). For this we consider the following transformations:

A) û_{cγ}û_{aα}û_{bβ} ↦ û_{aα}û_{cγ}û_{bβ}, if {a, α} ∩ {c, γ} = ∅ and a < b < c, B) û_{βγ}û_{αβ}û_{βδ} ↦ û_{αγ}û_{γδ}û_{βγ}, if α < β < γ < δ, C) û_{βδ}û_{αβ}û_{βγ} ↦ û_{βγ}û_{γδ}û_{αγ}, if α < β < γ < δ, D) û_{cγ}û_{ac}û_{bβ} ↦ û_{bβ}û_{cγ}û_{ac}, if {a, c, γ} ∩ {b, β} = ∅ and a < b < c, E) û_{bβ}û_{ac}û_{cγ} ↦ û_{ac}û_{cγ}û_{bβ}, if {a, c, γ} ∩ {b, β} = ∅ and a < b < c, F) û_{bβ}û_{aα}û_{cγ} ↦ û_{bβ}û_{cγ}û_{aα}, if {a, α} ∩ {c, γ} = ∅ and a < b < c,

The algorithm is very simple: To a chain in H_{(1,n)}(ζ), we keep on applying the transformations A to F to the rightmost triples. When we stop, we have a chain in H_{(n,1)}(ζ). The analysis of this algorithm can be found at:

http://www.math.yorku.ca/Who/Faculty/Bergeron.

There is one last identity of [2] that is asking for a combinatorial proof. Given η, ζ ∈ S_{∞}, we say that the permutations are u-disjoint if for any û_{α_{n}β_{n}} ⋯ û_{α_{1}β_{1}} ∈ R_{u}(ζ) and any û_{γ_{n}δ_{n}} ⋯ û_{γ_{1}δ_{1}} ∈ R_{u}(η) we have {α_{1}, β_{1}, …, α_{n}, β_{n}} ∩ {γ_{1}, δ_{1}, …, γ_{n}, δ_{n}} = ∅ and û_{α_{n}β_{n}} ⋯ û_{α_{1}β_{1}} û_{γ_{n}δ_{n}} ⋯ û_{γ_{1}δ_{1}} ≠ 0. From the relations (1.1) it is clear that this definition depends only on one choice of an element from each R_{u}(ζ) and R_{u}(η).

Proposition 5.4 (Theorem G of [2]). Given η and ζ u-disjoint, we have

c_{λ}^{ζη} = ∑_{ν,μ} c_{νμ}^{λ}c_{ν}^{ζ}c_{μ}^{η},

where c_{νμ}^{λ} is the classical Littlewood-Richardson coefficient.

Here it is not difficult to see how R_{u}(ζη) is related to R_{u}(ζ) and R_{u}(η). In fact u-disjointness directly implies that [1, ζη]_{⪯} ≅ [1, ζ]_{⪯} × [1, η]_{⪯}. We can use that to relate H_{p}(ζη) to H_{q}(ζ) and H_{q′}(η) for some q, q′.

Problem 5.5. For ζ, η two u-disjoint permutations, use [1, ζη]_{⪯} ≅ [1, ζ]_{⪯} × [1, η]_{⪯} and Theorem 4.3 to construct a combinatorial proof of Proposition 5.4.

We end our list with problems related to M and ⪯.

Problem 5.6. Let m = ℓ_{u}(ζ). Equation (1.3) suggests that we could:

(a) Find a representation of the symmetric group S_{m} on ℚR_{u}(ζ) with character given by

∑_{λ} c_{λ}^{ζ}χ^{λ}.

(b) Find a partition of R_{u}(ζ) similar to the one discussed after the relations (2.2).

Problem 5.7. Describe the polynomial P_{n}(t) = ∑_{ζ∈S_{n}} t^{ℓ_{u}(ζ)}.

Here, let us list the first few of these polynomials:

P_{1}(t) = 1, P_{2}(t) = 1 + t, P_{3}(t) = 1 + 3t + 2t^{2},

P_{4}(t) = 1 + 6t + 10t^{2} + 6t^{3} + t^{4},

P_{5}(t) = 1 + 10t + 30t^{2} + 40t^{3} + 27t^{4} + 10t^{5} + 2t^{6},

P_{6}(t) = 1 + 15t + 70t^{2} + 155t^{3} + 195t^{4} + 156t^{5} + 86t^{6} + 33t^{7} + 8t^{8} + t^{9}, P_{7}(t) = 1 + 21t + 140t^{2} + 455t^{3} + 875t^{4} + 1120t^{5} + 1038t^{6} + 735t^{7} + 406t^{8}

+175t^{9} + 58t^{10} + 14t^{11} + 2t^{12}, P_{8}(t) = 1 + 28t + 252t^{2} + 1120t^{3} + 2996t^{4} + 5432t^{5} + 7252t^{6} + 7562t^{7} + 6398t^{8}

+4492t^{9} + 2652t^{10} + 1324t^{11} + 556t^{12} + 192t^{13} + 52t^{14} + 10t^{15} + t^{16}.

It is also instructive to display the Poset (S_{4}, ⪯). Here we represent the permutations using disjoint cycles notation.

Problem 5.8. What are the properties of the partial order ⪯. e.g. What is its Möbius function? Is any interval Cohen-Macauley?

We should mention here that the intervals contain hexagons in general, hence they are not shellable in the classical sense.

Problem 5.9. Is it possible to find a faithful representation of M as operators on the polynomial ring ℤ[x_{1}, x_{2}, x_{3}, …]?

This last problem is suggested by the situation for the nilplactic monoid N. For N we have a faithful representation defined by u_{i} ↦ ∂_{i}, where ∂_{i} is the divided difference operator on ℤ[x_{1}, x_{2}, x_{3}, …].

Acknowledgment The authors are grateful to M. Shimozono and many others for stimulating conversations.

References

[1] N. Bergeron and S. Billey, RC-Graphs and Schubert polynomials, Experimental Math., 2 (1993), pp. 257–269.

[2] N. Bergeron and F. Sottile, Schubert polynomials, the Bruhat order, and the geometry of flag manifolds. Duke Math. J., to appear, 48pp., 1997.

[3] I. Ciocan-Fontanine, On quantum cohomology of partial flag varieties. 1997.

[4] P. Edelman and C. Grene, Balanced tableaux, Adv. Math., 63 (1987), pp. 42–99.

[5] S. Fomin, S. Gelfand, and A. Postnikov, Quantum Schubert polynomials. J. AMS, to appear, 1997.

[6] W. Fulton, Universal Schubert polynomials. alg-geom preprint # 9702012, 1997.

[7] A. Kirillov and T. Maeno, Quantum Schubert polynomials and the Vafa-Intriligator formula, Tech. Rep. 96-41, University of Tokyo Mathematical Sciences, 1996.

[8] A. Lascoux and M.-P. Schützenberger, Le monoïd plaxique, in Non-Commutative Structures in Algebra and Geometric Combinatorics, Quad. “Ricera Sci.,” 109 Roma, CNR, 1981, pp. 129–156.

[9] , Polynômes de Schubert, C. R. Acad. Sci. Paris, 294 (1982), pp. 447–450.

[10] , Structure de Hopf de l’anneau de cohomologie et de l’anneau de Grothendieck d’une variété de drapeaux, C. R. Acad. Sci. Paris, 295 (1982), pp. 629–633.

[11] , Symmetry and flag manifolds, in Invariant Theory, (Montecatini, 1982), vol. 996 of Lecture Notes in Math., Springer-Verlag, 1983, pp. 118–144.

[12] A. Lascoux and M.-P. Schützenberger, Noncommutative Schubert polynomials, Funct. Anal. Appl., 23 (1989), pp. 223–225.

[13] I. G. Macdonald, Notes on Schubert Polynomials, Laboratoire de combinatoire et d’informatique mathématique (LACIM), Université du Québec à Montréal, Montréal, 1991.

[14] A. Postnikov, On a quantum version of pieri’s formula. Manuscript, 1997.

[15] F. Sottile, Pieri’s formula for flag manifolds and Schubert polynomials, Annales de l’Institut Fourier, 46 (1996), pp. 89–110.

[16] R. Stanley, On the number of reduced decompositions of elements of Coxeter groups, Europ. J. Combin., 5 (1984), pp. 359–372.

[17] S. Veigneau, Ph.d. Thesis, Universite Marne-la-Valée. Manuscript to appear, 1996.

[18] R. Winkel, On the multiplication of Schubert polynomials. manuscript, http://wwwmath.mit.edu/˜ winkel, 1996.

Department of Mathematics and Statistics, York University, North York, Ontario M3J 1P3, CANADA

E-mail address, Nantel Bergeron: bergeron@mathstat.yorku.ca

Department of Mathematics, University of Toronto, 100 St. George Street, Toronto, Ontario M5S 3G3, CANADA

E-mail address, Frank Sottile: sottile@math.toronto.edu