SKEW SCHUBERT FUNCTIONS AND THE PIERI FORMULA FOR FLAG MANIFOLDS

NANTEL BERGERON AND FRANK SOTTILE

Abstract. We show the equivalence of the Pieri formula for flag manifolds and certain identities among the structure constants, giving new proofs of both the Pieri formula and of these identities. A key step is the association of a symmetric function to a finite poset with labeled Hasse diagram satisfying a symmetry condition. This gives a unified definition of skew Schur functions, Stanley symmetric function, and skew Schubert functions (defined here). We also use algebraic geometry to show the coefficient of a monomial in a Schubert polynomial counts certain chains in the Bruhat order, obtaining a new combinatorial construction of Schubert polynomials.

Introduction

A fundamental open problem in the theory of Schubert polynomials is to find an analog of the Littlewood-Richardson rule. By this, we mean a bijective description of the structure constants for the ring of polynomials with respect to its basis of Schubert polynomials. Such a rule would express the intersection form in the cohomology of a flag manifold in terms of its basis of Schubert classes. Other than the classical Littlewood-Richardson rule (when the Schubert polynomials are Schur symmetric polynomials) little is known.

Using geometry, Monk [26] established a formula for multiplication by linear Schubert polynomials (divisor Schubert classes). A Pieri-type formula for multiplication by an elementary or complete homogeneous symmetric polynomial (special Schubert class) was given in [21], but only recently proven [29] using geometry. There are now several proofs [7, 27, 33, 31], some of which [27, 33, 31] are purely combinatorial.

In the more general setting of multiplication by a Schur symmetric polynomial, formulas for some structure constants follow from a family of identities which were proven using geometry [3]. Also in (ibid.) are combinatorial results about intervals in the Bruhat order which are formally related to these identities. A combinatorial (but not a bijective) formula was given for these coefficients [4] using the Pieri formula, which gave a direct connection between some of these order-theoretic results and identities.

Date: 30 September 1997.

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

Key words and phrases. Pieri formula, Bruhat order, Schubert polynomial, Stanley symmetric function, flag manifold, jeu de taquin, weak order.

First author supported in part by NSERC and CRM grants.

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

A first goal of this paper is to deduce another identity [3, Theorem G(ii)] from the Pieri formula, and also to deduce the Pieri formula from these identities. This furnishes a new proof of the Pieri formula, shows its equivalence to these (seemingly) more general identities, and, together with the combinatorial proofs of the Pieri formula, gives a purely combinatorial proof of these identities.

A key step is the definition of a symmetric function associated to any finite symmetric labeled poset, which is a poset whose Hasse diagram has edges labeled with integers with a symmetry condition satisfied by its maximal chains. This gives a unified construction of skew Schur functions (for intervals in Young’s lattice of partitions), Stanley symmetric functions [30] (for intervals in the weak order on the symmetric group), and for intervals in a k-Bruhat order, skew Schubert functions (defined in another fashion in §1).

In [22], Lascoux and Schützenberger show that if a Schubert polynomial is expressed as a univariate polynomial in the first variable, then the coefficients are (explicitly determined) multiplicity-free sums of Schubert polynomials in the remaining variables. This may be used to show that Schubert polynomials are sums of monomials with non-negative coefficients. We use a cohomological formula [3, Theorem 4.5.4] to generalize their result, obtaining a similar formula for expressing a Schubert polynomial as a polynomial in any variable. This also extends Theorem C (ii) of [3], which identified the constant term of this expression. From this, we obtain a construction of Schubert polynomials purely in terms of chains in the Bruhat order, and a geometric proof that the monomials which appear in a Schubert polynomial have non-negative coefficients. The Pieri formula shows these coefficients are certain intersection numbers, recovering a result of Kirillov and Maeno [14].

We found these precise formulas in terms of intersection numbers surprising; Other combinatorial constructions are either recursive [24, 4.17] and do not give the coefficients, or are expressed in terms of combinatorial structures (the weak order on the symmetric group [6, 12, 11] or diagrams of permutations [16, 2, 32]) which are not geometric. Previously, we believed this non-negativity of monomials had no relation to geometry. Indeed, only monomials of the form x^{λ} with λ a partition are represented by positive cycles, other polynomial representatives of Schubert classes [5, 8] do not have this non-negativity, and polynomial representatives for the other classical groups cannot [10] have such non-negativity.

This paper is organized as follows. In Section 1, we give necessary background, define skew Schubert functions, and state our main results. In Section 2, we deduce the Pieri formula from the identities and results on the Bruhat order. In Section 3, we define a symmetric function S_{P} associated to a symmetric labeled poset P and complete the proof of the equivalence of the Pieri formula and these identities. We also show how this construction gives skew Schur and Schubert functions. In Section 4, we adapt an argument of Remmel and Shimozono [28] to show that, for intervals in the weak order, this symmetric function is Stanley’s symmetric function [30]. Finally, in Section 5, we use a geometric result of [3] to generalize the result in [22] and interpret the coefficient of a monomial in a Schubert polynomial in terms of chains in the Bruhat order.

1. Preliminaries

Let S_{n} be the symmetric group on n letters and S_{∞} := ⋃_{n} S_{n}, the group of permutations of ℕ which fix all but finitely many integers. We let 1 be the identity permutation. For each w ∈ S_{∞}, Lascoux and Schützenberger [21] defined a Schubert polynomial 𝔖_{w} ∈ ℤ[x_{1}, x_{2}, …] with deg 𝔖_{w} = ℓ(w). These satisfy the following:

1. {𝔖_{w} | w ∈ S_{∞}} is a ℤ-basis for ℤ[x_{1}, x_{2}, …].

2. If w has a unique descent at k (w(j) > w(j + 1) ⇒ j = k), then 𝔖_{w} = S_{λ}(x_{1}, …, x_{k}), where λ_{j} = w(k + 1 − j) − k − 1 + j. We write v(λ, k) for this permutation and call w a Grassmannian permutation with descent k.

By the first property, there exist integral structure constants c_{u v}^{w} for w, u, v ∈ S_{∞} (non-negative from geometry) defined by the identity

𝔖_{u} · 𝔖_{v} = ∑_{w} c_{u v}^{w} 𝔖_{w}. (1)

We are concerned with the coefficients c_{u v(λ,k)}^{w} which arise when 𝔖_{v} in (1) is replaced by the Schur polynomial S_{λ}(x_{1}, …, x_{k}) = 𝔖_{v(λ,k)}.

It is well-known (see for example [29, 3]) that c_{u v(λ,k)}^{w} ≠ 0 only if u ≤_{k} w, where ≤_{k} is the k-Bruhat order (introduced in [23]). In fact, u ≤_{k} w if and only if there is some λ with c_{u v(λ,k)}^{w} ≠ 0. This suborder of the Bruhat order has the following characterization:

Definition 1.1 (Theorem A of [3]). Let u, w ∈ S_{∞}. Then u ≤_{k} w if and only if 1. a ≤ k < b ⟹ u(a) ≤ w(a) and u(b) ≥ w(b),

2. a < b, u(a) < u(b), and w(a) > w(b) ⟹ a ≤ k < b.

For any infinite subset P of ℕ, the order-preserving bijection ℕ ↔ P and the inclusion P ↪ ℕ induce a map

ε_{P} : S_{∞} ≃ S_{P} ↪ S_{∞}.

Shape-equivalence is the equivalence relation generated by ζ ∼ ε_{P} (ζ) for P ⊂ ℕ.

If u ≤_{k} w, let [u, w]_{k} denote the interval between u and w in the k-Bruhat order. These intervals have the following property:

Order 1 (Theorem E(i) of [3]). Suppose u, w, y, z ∈ S_{∞} with u ≤_{k} w, y ≤_{l} z, and wu^{−1} shape-equivalent to zy^{−1}. Then [u, w]_{k} ≃ [y, z]_{l}. Moreover, if zy^{−1} = ε_{P} (wu^{−1}), then this isomorphism is induced by the map v ↦ ε_{P} (vu^{−1})y.

This has a companion identity among the structure constants c_{u v(λ,k)}^{w}:

Identity 1 (Theorem E(ii) of [3]). Suppose u, w, y, z ∈ S_{∞} with u ≤_{k} w, y ≤_{k} l, and wu^{−1} shape-equivalent to zy^{−1}. Then, for any partition λ,

c_{u v(λ,k)}^{w} = c_{y v(λ,l)}^{z}.

This identity was originally proven using geometry [3]. In [4], we showed how to deduce it from Order 1 and the Pieri formula for Schubert polynomials. Here, we use it to deduce the Pieri formula.

By Identity 1, we may define a constant c_{λ}^{ζ} for any permutation ζ ∈ S_{∞} and any partition λ by c_{λ}^{ζ} = c_{u v(λ,k)}^{w} for any u ≤_{k} w with w = ζu. We also define the skew Schubert function S_{ζ} by

S_{ζ} = ∑_{λ} c_{λ}^{ζ}S_{λ}, (2)

where S_{λ} is the Schur symmetric function [25].

By Order 1, we may make the following definition:

Definition 1.2. Let η, ζ ∈ S_{∞}. Then η ⪯ ζ if and only if there is a u ∈ S_{∞} and k ∈ ℕ with u ≤_{k} ηu ≤_{k} ζu. For ζ ∈ S_{∞}, define |ζ| := ℓ(ζu) − ℓ(u) for any u, k with u ≤_{k} ζu. (There always is such a u and k, see §2.)

In §2, ⪯ and |ζ| are given definitions that do not refer to ≤_{k} or ℓ(w).

Let ζ, η ∈ S_{∞}. If we have η · ζ = ζ · η with |ζ · η| = |ζ| + |η|, and neither of ζ or η is the identity, then we say that ζ · η is the disjoint product of ζ and η. If a permutation cannot be written in this way, then it is irreducible. It is a consequence of [3, §3] that a permutation ζ factors uniquely into irreducibles as follows: Let Π be the finest non-crossing partition [19] which is refined by the partition given by the cycles of ζ. For each non-singleton part p of Π, let ζ_{p} be the product of cycles which partition p. Each ζ_{p} is irreducible, and ζ is the disjoint product of the ζ_{p}’s. See Remark 3.7 for a further discussion.

Order 2 (Theorem G(i) of [3]). Suppose ζ = ζ_{1} ⋯ ζ_{t} is the factorization of ζ ∈ S_{∞} into irreducibles. Then the map (η_{1}, …, η_{t}) ↦ η_{1} ⋯ η_{t} induces an isomorphism

[1, ζ_{1}]_{⪯} × ⋯ × [1, ζ_{t}]_{⪯} ⟶^{∼} [1, ζ]_{⪯}.

Identity 2 (Theorem G(ii) of [3]). Suppose ζ = ζ_{1} ⋯ ζ_{t} is the factorization of ζ ∈ S_{∞} into irreducibles. Then

S_{ζ} = S_{ζ_{1}} ⋯ S_{ζ_{t}}.

Theorem G(ii) in [3] states that if ζ · η is a disjoint product, then, for all partitions λ,

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

Thus we see that

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

Iterating this shows the equivalence of Theorem G(ii) of [3] and Identity 2.

A labeled poset P is a finite ranked poset together with an integer label for each cover. Its Hasse diagram is thus a directed labeled graph with integer labels. Write u ⟶^{b} w for a labeled edge in this Hasse diagram. In what follows, we consider four classes of labeled posets: Intervals in a k-Bruhat order. Labeling a cover u ⋖_{k} w in the k-Bruhat order

with b, where wu^{−1} = (a, b) and a < b gives every interval in the k-Bruhat order the structure of a labeled poset.

Intervals in the ⪯-order. Likewise, a cover η ≺· ζ in the ⪯-order gives a transposition (a, b) = ζη^{−1} with a < b. Labeling such a cover with b gives every interval in this order the structure of a labeled poset. Since [η, ζ]_{⪯} ≃ [1, ζη^{−1}]_{⪯}, it suffices to consider intervals of the form [1, ζ]_{⪯}.

Intervals in Young’s lattice. A cover μ ⊂ · λ in Young’s lattice of partitions gives a unique index i with μ_{i} + 1 = λ_{i}. Labeling such a cover with λ_{i} − i gives every interval in Young’s lattice the structure of a labeled poset.

Intervals in the weak order. Finally, labeling a cover u ⋖_{weak} w in the weak order on S_{∞} with the index i of the transposition wu^{−1} = (i, i+1) gives every interval in the weak order the structure of a labeled poset. Since, for u ≤_{weak} w, [u, w]_{weak} ≃ [1, wu^{−1}]_{weak}, it suffices to consider intervals of the form [1, w]_{weak}.

The sequence of edge labels in a (maximal) chain of a labeled poset is the word of that chain. For a composition α = (α_{1}, …, α_{k}) of m = rankP, let H_{α}(P) be the set of maximal chains in P whose word has descent set contained in I(α) := {α_{1}, α_{1} + α_{2}, …, m − α_{k}}. We say that P is symmetric if the cardinality of H_{α}(P) depends only upon the parts of α and not their order.

Each poset in the above classes is symmetric: For the k-Bruhat orders or ⪯ order, this is a consequence of the Pieri formula for Schubert polynomials. For Young’s lattice, this is classical, and for intervals in the weak order, it is due to Stanley [30].

We wish to consider skew Young diagrams to be equivalent if they differ by a translation. This leads to the following notion of isomorphism for labeled posets.

Definition 1.3. A map f : P → Q between labeled posets is an isomorphism if f is an isomorphism of posets which preserves the relative order of the edge labels.

That is, if e, e′ are edges of P with respective labels a ≤ a′, then the edge labels b, b′ of f(e), f(e′) in Q satisfy b ≤ b′. The isomorphisms of Order 1 and Order 2 are isomorphisms of labeled posets. We also see that the interval [μ, λ]_{⊂} in Young’s poset is isomorphic to the interval [v(μ, k), v(λ, k)]_{k}, since the difference between the label of a cover v(α, k) ⋖_{k} v(β, k) in the k-Bruhat order and the corresponding cover α ⊂· β in Young’s lattice is k + 1.

To every symmetric labeled poset P, we associate (Definition 3.6) a symmetric function S_{P} which has the following properties:

Theorem 1.4.

1. If P ≃ Q, then S_{P} = S_{Q}.

2. If u ≤_{k} w, then S_{[u,w]_{k}} = S_{wu^{−1}}, the skew Schubert function.

2′. For ζ ∈ S_{∞}, S_{[1,ζ]_{⪯}} = S_{ζ}, the skew Schubert function.

3. Let μ ⊂ λ be partitions. Then S_{[μ,λ]_{⊂}} = S_{λ/μ}, the skew Schur function.

4. For w ∈ S_{∞}, we have S_{[1,w]_{weak}} = F_{w}, the Stanley symmetric function.

Part 1 is Lemma 3.2(2), parts 2, 2′, and 3 are proven in §3, and part 4 in §4.

A labeled poset P is an increasing chain if it is totally ordered with increasing edge labels. A cycle ζ ∈ S_{∞} is increasing if [1, ζ]_{⪯} is an increasing chain. Decreasing chains and cycles are defined similarly.

For any positive integers m, k let r[m, k] denote the permutation v((m, 0, …, 0), k) which is the increasing cycle (k+m, k+m−1, …, k). It is an easy consequence (see Lemma 2.1) of the definitions of ≤_{k} or ⪯ that any increasing cycle ζ of length m+1 is shape equivalent to r[m, k] and hence |ζ| = m. Likewise, the permutation v(1^{m}, k) is the decreasing cycle (k+1−m, …, k, k+1) and any decreasing cycle of length m+1 is shape equivalent to v(1^{m}, k) for any k ≥ m. Here 1^{m} is the partition of m into m equal parts of size 1. Note that

𝔖_{r[m,k]} = h_{m}(x_{1}, …, x_{k}) and 𝔖_{v(1^{m},k)} = e_{m}(x_{1}, …, x_{k}),

the complete homogeneous and elementary symmetric polynomials.

Proposition 1.5 (Pieri formula for Schubert polynomials and flag manifolds). Let u ≤_{k} w with m = ℓ(w) − ℓ(u). Then

1. c_{u r[m,k]}^{w} = \{ \begin{matrix}1 & if wu^{−1} is the disjoint product of increasing cycles \\ 0 & otherwise. \end{matrix}
2. c_{u v(1^{m},k)}^{w} = \{ \begin{matrix}1 & if wu^{−1} is the disjoint product of deceasing cycles \\ 0 & otherwise. \end{matrix}

This is the form of the Pieri formula stated in [21], as such a disjoint products of increasing (decreasing) cycles are k-soulèvements droits (respectively gauches) for u. By [29, Lemma 6], wu^{−1} is a disjoint product of increasing cycles if and only if there is a maximal chain in [u, w]_{k} with increasing labels, and such chains are unique.

When this occurs, we write u ⟶^{r[m,k]} w, where m := ℓ(w) − ℓ(u). Similarly, wu^{−1} is a disjoint product of decreasing cycles if and only if there is a maximal chain in [u, w]_{k} with decreasing labels, which is necessarily unique.

Recall that

H^{∗}(Flags(ℂ^{n})) ≃ ℤ[x_{1}, x_{2}, …]/⟨𝔖_{w} | w ∉ S_{n}⟩
= ℤ[x_{1}, …, x_{n}]/⟨x^{α} | α_{i} ≥ n − i, for some i⟩.

The map defined by 𝔖_{w} ↦ 𝔖\overline{w}, where \overline{w} = ω_{0}wω_{0}, conjugation by the longest element ω_{0} in S_{n}, is an algebra involution on H^{∗}(Flags(ℂ^{n})). If n ≥ k + m, then this involution shows the equivalence of the two versions of the Pieri formula.

We state the main results of this paper:

Theorem 1.6. Given the results Order 1 and 2 on the k-Bruhat orders/⪯-order, the Pieri formula for Schubert polynomials is equivalent to the Identities 1 and 2.

This is proven in §2 and §3.

Theorem 1.7. If w ∈ S_{n} and 0 ≤ α_{i} ≤ n−i for 1 ≤ i ≤ n−1, then the coefficient of x_{1}^{n−1−α_{1}}x_{2}^{n−2−α_{2}} ⋯ x_{n−1}^{1−α_{n−1}} in the Schubert polynomial 𝔖_{w}(x) is the number of chains

w ⟶^{r[α_{1},1]} w_{1} ⟶^{r[α_{2},2]} ⋯ ⟶^{r[α_{n−1},n−1]} ω_{0}

between w and ω_{0}, the longest element in S_{n}.

This is a restatement of Corollary 5.3.

2. Proof of the Pieri formula for Schubert polynomials and flag manifolds

Here, we use Identities 1 and 2 to deduce the Pieri formula. We first establish some combinatorial facts about chains and increasing/decreasing cycles.

Let ζ ∈ S_{∞}. We give a u ∈ S_{∞} and k > 0 such that u ≤_{k} ζu and ζu is Grassmannian of descent k. Define up(ζ) := {a | a < ζ(a)}, down(ζ) := {b | b > ζ(b)}, fix(ζ) := {c | c = ζ(c)}, and set k := #up(ζ). If we have

up(ζ) = {a_{1}, …, a_{k} | ζ(a_{1}) < ζ(a_{2}) < ⋯ < ζ(a_{k})},
fix(ζ) ⋃ down(ζ) = {b_{1}, b_{2}, … | ζ(b_{1}) < ζ(b_{2}) < ⋯ },

and define u ∈ S_{∞} by

u := \{ \begin{matrix}a_{i} & if i ≤ k \\ b_{i−k} & if i > k \end{matrix} ,

then u ≤_{k} ζu. Set w := ζu.

This construction of u ∈ S_{∞} is Theorem 3.1.5 (ii) of [3]. There, we also show that η ⪯ ζ if and only if

1. a ∈up(ζ) ⟹ η(a) ≤ ζ(a).

2. b ∈down(ζ) ⟹ η(b) ≥ ζ(b).

3. a, b ∈up(ζ) (or a, b ∈down(ζ)) with a < b and ζ(a) < ζ(b) ⟹ η(a) < η(b).

Lemma 2.1. Let ζ ∈ S_{∞}. The labeled poset [1, ζ]_{⪯} is a chain if and only if ζ is either an increasing or a decreasing cycle. Moreover, if ζ is an increasing (decreasing) cycle of length m + 1, then the chain [1, ζ]_{⪯} is increasing (decreasing) and ζ is shapeequivalent to r[m, 1] (v(1^{m}, m)).

Proof. Let ζ ∈ S_{∞} and construct u ≤_{k} ζu as above. Set m := ℓ(ζu) − ℓ(u), and consider any chain in [u, w]_{k}:

u = u_{0} ⟶^{b_{1}} u_{1} ⟶^{b_{2}} u_{2} ⋯ u_{m−1} ⟶^{b_{m}} u_{m} = w.

Suppose that the poset [1, ζ]_{⪯} ≃ [u, ζu]_{k} is a chain. By Order 2, ζ is irreducible. We show that ζ is either an increasing or a decreasing cycle by induction on m. Suppose η = u_{m−1}u^{−1} is an increasing cycle. Then η = (b_{m−1}, b_{m−2}, …, b_{1}, a_{1}) where u_{1} = (a_{1}, b_{1})u and u_{i} = (b_{i−1}, b_{i})u_{i−1} for i > 1. Let ζ = (a_{m}, b_{m})η.

Since u_{m−1}^{−1}(b_{m−1}) ≤ k and u_{m−1}^{−1}(b_{m}) > k, we must have b_{m−1} ≠ b_{m}. If b_{m} > b_{m−1} so that [1, ζ]_{⪯} is increasing, then, as ζ is irreducible, we must have a_{m} = b_{m−1} and so ζ is the increasing cycle

(b_{m}, b_{m−1}, …, b_{1}, a_{1}).

Indeed, if either a_{m} > b_{m−1} or a_{m} < b_{m−2}, then [1, ζ]_{⪯} is not a chain, and b_{m−1} > a_{m} ≥ b_{m−2} contradicts u_{m−2} ⋖_{k} u_{m−1} ⋖_{k} u_{m}. Suppose now that b_{m} < b_{m−1}, then the irreducibility of ζ implies that m = 2 and b_{m} = a_{1}, so that [1, ζ]_{⪯} is decreasing and ζ is a decreasing cycle.

Similar arguments suffice when η = u_{m−1}u^{−1} is a decreasing cycle, and the other statements are straightforward.

Proof that Identities 1 and 2 imply the Pieri formula.

Let ζ ∈ S_{∞} and suppose c_{(m,0,... ,0)}^{ζ} ≠ 0. Then m = |ζ|, by homogeneity. Replacing ζ by a shape-equivalent permutation if necessary, we may assume that ζ ∈ S_{n} and ζ(i) ≠ i for each 1 ≤ i ≤ n.

Define u and w := ζu as in the first paragraph of this section, so that u, w ∈ S_{n} and c_{(m,0,... ,0)}^{ζ} = c_{u r[m,k]}^{w}. Since c_{u r[m,k]}^{w} ≠ 0, we must have m = n − k = #down(ζ): Consider any chain

u = u_{0} ⟶^{b_{1}} u_{1} ⟶^{b_{2}} u_{2} ⋯ u_{m−1} ⟶^{b_{m}} u_{m} = w (3)

in [u, w]_{k}. Then down(ζ) ⊂ {b_{1}, …, b_{m}} so that m ≥ n − k. However, c_{u r[m,k]}^{w} ≠ 0 and w ∈ S_{n} implies that r[m, k] ∈ S_{n}, and hence k+m ≤ n. It follows that down(ζ) = {b_{1}, …, b_{m}}. Thus if we have u_{i} = u_{i−1}(c_{i}, d_{i}) with c_{i} ≤ k < d_{i}, then by the construction of u, {d_{1}, …, d_{m}} = {k+1, …, k+m = n}.

Consider the case when ζ is irreducible. Then we must have c_{1} = c_{2} = ⋯ = c_{m}. This implies that k = #up(ζ) = 1, and m = n − 1. By (1) of Definition 1.1 we must then have b_{1} < b_{2} < ⋯ < b_{m}, and hence ζ = (n, n−1, …, 2, 1), an increasing cycle. But this is r[n−1, 1], so u = 1, the identity permutation. Since c_{1 v}^{w} = δ_{w, v}, the Kronecker delta, c_{λ}^{ζ} = δ_{λ, (m,0,... ,0)} and so S_{ζ} = h_{n−1}.

If more generally we have η ∈ S_{∞} with #down(η) = |η| = m and η irreducible, then considering a shape-equivalent ζ ∈ S_{n} with n minimal, we see that η is an increasing cycle and S_{η} = h_{m}.

We return to the case of ζ ∈ S_{n} with c_{(m,0,... ,0)}^{ζ} ≠ 0. Let ζ = ζ_{1} ⋯ ζ_{t} be the disjoint factorization of ζ into irreducibles. Then each ζ_{i} is an increasing cycle. Suppose that m_{i} = |ζ_{i}|. By Identity 2, we have that

S_{ζ} = S_{ζ_{1}} ⋯ S_{ζ_{t}}
= h_{m_{1}} ⋯ h_{m_{t}}.

This is equivalent to [29, Theorem 5]. From this, we deduce that c_{λ}^{ζ} = c_{ν λ}^{μ}, where μ/ν is a horizontal strip with m_{i} boxes in the ith row. By the classical Pieri formula for Schur polynomials, this implies that c_{(m,0,... ,0)}^{ζ} = 1.

3. Skew Schur functions from labeled posets

In [4, Theorem 4.3], we showed how the Pieri formula implies Identity 1. Here we complete the proof of Theorem 1.6, showing how the Pieri formula implies Identity 2. The first step is a reinterpretation of a construction in [4, §4] from which we associate a symmetric function to any symmetric labeled poset. For intervals in Young’s lattice, we obtain skew Schur functions, and for intervals in either a k-Bruhat order or the ⪯-order, skew Schubert functions. In Section 4, we show that for intervals in the weak order we obtain Stanley symmetric functions.

Let P be a labeled poset with total rank m. A (maximal) chain in P gives a sequence of edge labels, called the word of that chain. A composition α := (α_{1}, …, α_{k}) of m = α_{1} + ⋯ + α_{k} (α_{i} ≥ 0), determines, and is determined by a (multi)subset I(α) := {α_{1}, α_{1} + α_{2}, …, α_{1} + ⋯ + α_{k}} of {1, …, m}. For a composition α of m = rankP, let H_{α}(P) be the set of (maximal) chains in P whose word w has descent set {j | w_{j} > w_{j+1}} contained in the set I(α). We adopt the convention that the last position of a word is a descent. If some α_{i} < 0, then we set H_{α}(P) = ∅. We say that P is (label-) symmetric if the cardinality of H_{α}(P) depends only upon the parts of α and not their order.

Let Λ be the ℤ-algebra of symmetric functions. Recall that Λ = ℤ[h_{1}, h_{2}, …], where h_{i} is the complete homogeneous symmetric function of degree i, the sum of all monomials of degree i. For a composition α, set

h_{α} := h_{α_{1}}h_{α_{2}} ⋯ h_{α_{k}}.

Definition 3.1. Suppose P is a symmetric labeled poset. Define the ℤ-linear map χ_{P} : Λ → ℤ by

χ_{P} : h_{α} ⟼ #(H_{α}(P)).

For any partition λ, define the skew coefficient c_{λ}^{P} to be χ_{P} (S_{λ}), where S_{λ} is the Schur symmetric function.

We point out some properties of these coefficients c_{λ}^{P}. For a partition λ of m (λ ⊢ m) with λ_{k+1} = 0 and a permutation π ∈ S_{k}, let λ_{π} be the following composition of m:

π(1) − 1 + λ_{k+1−π(1)}, π(2) − 2 + λ_{k+1−π(2)}, …, π(k) − k + λ_{k+1−π(k)}.

Lemma 3.2. Let P, Q be symmetric labeled posets.

1. For any partition λ,

c_{λ}^{P} := ∑_{π∈S_{k}} ε(π)#(H_{λ_{π}}(P))

where λ_{k+1} = 0 and ε : S_{k} → {±1} is the sign character.

2. If P ≃ Q as labeled posets (Definition 1.3) then for any partition λ, c_{λ}^{P} = c_{λ}^{Q}.

The first statement follows from the Jacobi-Trudi formula, and the second by noting that the bijection P ↔ Q induces bijections H_{α}(P) ↔ H_{α}(Q).

Remark 3.3. By the Pieri formula for Schubert polynomials, the number #(H_{α}([u, w]_{k})) is the coefficient of 𝔖_{w} in the product 𝔖_{u} · h_{α}(x_{1}, …, x_{k}). It follows that intervals in a k-Bruhat order or in the ⪯-order are symmetric. For similar reasons, we see that intervals in Young’s lattice are symmetric, as #(H_{α}([μ, λ]_{⊂})) is the skew Kostka coefficient K_{α, λ/μ}, which is the coefficient of S_{λ} in S_{μ} · h_{α}, equivalently, the number of semistandard Young tableaux of shape λ/μ and content α. One may construct an explicit bijection with the second set as follows: A chain in H_{α}([μ, λ]_{⊂}) is naturally decomposed into subchains with increasing labels of lengths α_{1}, α_{2}, …, α_{k}. Placing the integer i in the boxes corresponding to covers in the ith such subchain furnishes the bijection.

Proposition 3.4 (Theorem 4.3 of [4]). Let u ≤_{k} w and λ ⊢ ℓ(w) − ℓ(u) = m. Then c_{u v(λ,k)}^{w} = c_{λ}^{[u,w]_{k}}.

Proof. By definition, c_{u v(λ,k)}^{w} is the coefficient of 𝔖_{w} in the expansion of the product 𝔖_{u} · S_{λ}(x_{1}, …, x_{k}) into Schubert polynomials. By the Jacobi-Trudi formula,

𝔖_{u} · S_{λ}(x_{1}, …, x_{k}) = 𝔖_{u} · ∑_{π∈S_{k}} ε(π)h_{λ_{π}}(x_{1}, …, x_{k})
= ∑_{w} ∑_{π∈S_{k}} ε(π)#(H_{λ_{π}}([u, w]_{k})) 𝔖_{w}
= ∑_{w} c_{λ}^{[u,w]_{k}} 𝔖_{w}.

Proposition 3.5 (Corollary 4.9 of [4]). If u ≤_{k} w and y ≤_{l} z with wu^{−1} shape equivalent to zy^{−1}, then for all λ, c_{u v(λ,k)}^{w} = c_{y v(λ,l)}^{z}.

Proof. By Order 1, [u, w]_{k} ≃ [y, z]_{l} is an isomorphism of labeled posets.

Definition 3.6. Let P be a ranked labeled poset with total rank m. Define the symmetric function S_{P} by

S_{P} := ∑_{λ⊢m} c_{λ}^{P} S_{λ},

where S_{λ} is a Schur function.

Proof of Theorem 1.4 (1), (2), and (3). (1) is a consequence of Lemma 3.2 (2). For (3), let μ ⊂ ν in Young’s lattice, suppose ν_{k+1} = 0, and consider the interval [μ, ν]_{⊂} in Young’s lattice. Then [μ, ν] ≃ [v(μ, k), v(ν, k)]_{k}, and so c_{λ}^{[μ,ν]} = c_{v(μ,k) v(λ,k)}^{v(ν,k)} = c_{μ λ}^{ν}. Hence S_{[μ,ν]_{⊂}} = S_{ν/μ}. Similarly, we see that for u ≤_{k} w or ζ ∈ S_{∞}, we have S_{[u,w]_{k}} = S_{wu^{−1}} and S_{[1,ζ]_{⪯}} = S_{ζ}, the skew Schubert functions of §1.

Remark 3.7. According to Proposition 3.5, the skew Schubert function S_{ζ} depends only on the shape equivalence class of ζ. In [3] there is another identity:

Theorem H of [3]. Suppose η, ζ ∈ S_{n} with ζ = η^{(12...n)}. Then S_{η} = S_{ζ}.

The example of η = (1243) and ζ = (1243) in S_{4} (see Figure 1) shows that in general [1, η]_{⪯} ≄ [1, η^{(12...n)}]_{⪯}. However, these two intervals do have the same number of maximal chains [3, Corollary 1.4]. In fact, for η ∈ S_{n} and α a composition, #(H_{α}([1, η]_{⪯})) = #(H_{α}([1, η^{(12...n)}]_{⪯})).

Thus if ∼ is the equivalence relation generated by shape equivalence and this ‘cyclic shift’ (η ∼ η^{(12...n)}, if η ∈ S_{n}), then S_{ζ} depends only upon the ∼-equivalence class of ζ. (This is analogous to, but stronger than the fact that the skew Schur function S_{κ} depends on κ only up to a translation in the plane.)

There is a combinatorial object Γ_{ζ} which determines the ∼-equivalence class of ζ. First place the set {a | a ≠ ζ(a)} at the vertices of a regular #{a | a ≠ ζ(a)}-gon in clockwise order. Next, for each a with a ≠ ζ(a), draw a directed chord from a to ζ(a). Γ_{ζ} is the resulting configuration of directed chords, up to rotation and dilation and without any vertices labeled (cf. [3, §3.3]). The irreducible factors of ζ correspond to connected components of Γ_{ζ} (considered as a subset of the plane). The figure Γ_{(1243)} = Γ_{(1423)} is also displayed in Figure 1.

Figure 1. Intervals under cyclic shift and Γ_{ζ}

We conclude this section with the following Theorem:

Theorem 3.8. Let P and Q be symmetric labeled posets with disjoint sets of edge labels. Then

S_{P ×Q} = S_{P} · S_{Q}.

This will complete the proof of Theorem 1.6, namely that the Pieri formula and Order 2 imply Identity 2: If ζ · η is a disjoint product, then [1, ζ]_{⪯} and [1, η]_{⪯} have disjoint sets of edge labels. Together with Theorem 1.4(4), this gives another proof of Theorem 3.4 in [30], that F_{w×u} = F_{w} · F_{u}.

To prove Theorem 3.8, we first study chains in H_{α}(P × Q). Suppose that P has rank n and Q has rank m. Note that a chain in P × Q determines and is determined by the following data:

• A chain in each of P and Q,

• A subset B of {1, …, n + m} with #B = n.

(4)

Recall that covers (p, q) ⋖ (p′, q′) in P × Q have one of two forms: either p = p′ and q′ covers q in Q or else q = q′ and p′ covers p in P. Thus a chain in P × Q gives a chain in each of P and Q, with the covers from P interspersed among the covers from Q. If we set B to be the positions of the covers from P, we obtain the description (4). Define

sort : chains(P × Q) ⟶ chains(P) × chains(Q)

to be the map which forgets the positions B of the covers from P.

Lemma 3.9. Let P and Q be labeled posets with disjoint sets of edge labels and α be any composition. Then

sort : H_{α}(P × Q) ⟶ ∐_{β+γ=α} H_{β}(P) × H_{γ}(Q)

is a bijection.

For integers a < b, let [a, b] := {n ∈ ℤ | a ≤ n ≤ b}. For a chain ξ, let ξ|_{[a,b]} be the portion of ξ starting at the ath step and continuing to the bth step. Proof. Let ξ ∈ H_{α}(P × Q) and set I = I(α) so that I_{i} = α_{1} + ⋯ + α_{i}. Then sort(ξ) ∈ H_{β}(P)×H_{γ}(Q), where, for each i, β_{i} counts the number of covers of ξ|_{[I_{i−1},I_{i}]} from P and γ_{i} = α_{i} − β_{i}.

To see this is a bijection, we construct its inverse. For chains ξ^{P} ∈ H_{β}(P) and ξ^{Q} ∈ H_{γ}(Q) with β + γ = α, define the set B by the conditions

1. β_{i} = #B ∩ [I(α)_{i−1}, I(α)_{i}].

2. If b_{1} ≤ ⋯ ≤ b_{β_{i}} and c_{1} ≤ ⋯ ≤ c_{γ_{i}} are the covers in ξ^{P} |_{[I(β)_{i−1},I(β)_{i}]} and ξ^{Q}|_{[I(γ)_{i−1},I(γ)_{i}]} respectively, then, up to a shift of I(α)_{i−1}, the set B∩[I(α)_{i−1}, I(α)_{i}] records the positions of the the b’s in the linear ordering of {b_{1}, …, b_{β_{1}}, c_{1}, …, c_{γ_{i}}}.

This clearly gives the inverse to the map sort.

Recall that the comultiplication Δ : Λ → Λ ⊗ Λ is defined by

Δ(h_{a}) = ∑_{b+c=a} h_{b} ⊗ h_{c}.

Thus, for a composition α,

Δ(h_{α}) = ∑_{β+γ=α} h_{β} ⊗ h_{γ}.

From Lemma 3.9, we immediately deduce:

Corollary 3.10. Let P, Q be symmetric labeled posets with disjoint sets of edge labels. Then

[figure: χ_{P ×Q}; Λ; ℤ; Δ; Λ ⊗ Λ; χ_{P} ⊗ χ_{Q}]

commutes.

Corollary 3.11. Let P, Q be symmetric labeled posets with disjoint sets of edge labels. Then, for any partition λ,

c_{λ}^{P ×Q} = ∑_{μ,ν} c_{μ ν}^{λ} c_{μ}^{P} c_{ν}^{Q}.

Proof. Recall [25, I.5.9] that Δ(S_{λ}) = ∑_{μ,ν} c_{μ ν}^{λ} S_{μ} S_{ν}. Hence

χ_{P ×Q}(S_{λ}) = ∑_{μ,ν} c_{μ ν}^{λ} χ_{P} (S_{μ}) χ_{P} (S_{ν}).

We complete the proof of Theorem 3.8: Let P, Q be symmetric labeled posets with disjoint sets of edge labels. Then

S_{P} · S_{Q} = ∑_{μ,ν} c_{μ}^{P} S_{μ} c_{ν}^{Q} S_{ν}
= ∑_{λ,μ,ν} c_{μ ν}^{λ} c_{μ}^{P} c_{ν}^{Q} S_{λ}
= ∑_{λ} c_{λ}^{P ×Q}S_{λ} = S_{P ×Q}.

4. Stanley symmetric functions from labeled posets

We establish Theorem 1.4(4) by adapting the proof of the Littlewood-Richardson rule in [28] to obtain a bijective interpretation of the constants c_{λ}^{[1,w]weak}, which shows S_{[1,w]weak} = F_{w} by the formulas in [22, 9]. The main tool is a jeu de taquin for reduced decompositions.

We use Cartesian conventions for Young diagrams and skew diagrams. Thus the first row is at the bottom. A filling of a diagram D with positive integers which increase across rows and up columns is a tableau with shape D. The word of a tableau is the sequence of its entries, read across each row starting with the topmost row.

A reduced decomposition ρ for a permutation w ∈ S_{∞} is the word of a maximal chain in [1, w]_{weak}. Let R(w) be the set of all reduced decompositions for w and for a composition α of ℓ(w), write H_{α}(w) for H_{α}([1, w]_{weak}). Given any composition α and any reduced decomposition ρ ∈ H_{α}(w), there is a unique smallest diagram λ/μ with row lengths λ_{i} − μ_{i} = α_{k+1−i} for which ρ is the word of a tableau T (α, ρ) of shape λ/μ. By this we mean that μ_{j} − μ_{j+1} is minimal for all j. If μ_{1} = 0, then T (α, ρ) has partition shape λ (= α), otherwise T (α, ρ) has skew shape. Given a reduced decomposition ρ ∈ R(w), define T (ρ) to be the tableau T (α, ρ), where I(α) is the descent set of ρ.

Stanley [30] defined a symmetric function F_{w} for every w ∈ S_{∞}. (That F_{w} is symmetric includes a proof that the intervals [1, w]_{weak} are symmetric.) Thus there exists integers a_{λ}^{w} such that

F_{w} = ∑_{λ⊢l} a_{λ}^{w}S_{λ}.

A combinatorial interpretation for a_{λ}^{w} was given (independently) in [22] and [9]:

a_{λ}^{w} = #{ρ ∈ R(w) | T (ρ) has partition shape λ}.

(See [24, §VII] for an account with proofs.) Theorem 1.4(4) is a consequence of the following result:

Theorem 4.1. For any w ∈ S_{∞} and partition λ ⊢ ℓ(w),

a_{λ}^{w} = c_{λ}^{[1,w]weak}.

Our proof is based on the proof of the Littlewood-Richardson rule given by Remmel and Shimozono [28]. We define an involution θ on the set

∐_{π∈S_{k}}{π} × H_{λ_{π}}(w)

(here λ ⊢ ℓ(w) and λ_{k+1} = 0) such that 1. θ(π, ρ) = (π, ρ) if and only if T (ρ) has shape λ, from which it follows that π = 1.

2. If T (ρ) does not have shape λ, then θ(π, ρ) = (π′, ρ′) where T (ρ′) does not have shape λ and ρ′ ∈ H_{λ_{π′}}(w) with |ℓ(π) − ℓ(π′)| = 1.

Theorem 4.1 is a corollary of the existence of such an involution θ: By property 2, only the fixed points of θ contribute to the sum in Lemma 3.2(1).

The involution θ will be defined using a jeu de taquin for tableaux whose words are reduced decompositions. Because we only play this jeu de taquin on diagrams with two rows, we do not describe it in full.

Definition 4.2. Let T be a tableau of shape (y+p, q)/(y, 0) whose word is a reduced decomposition for a permutation w. If y ≠ 0, we may perform an inward slide. This modification of an ordinary jeu de taquin slide ensures we obtain a tableau whose word is a reduced decomposition of w.

Begin with an empty box at position (y, 1) and move it through the tableau T according to the following local rules:

1. If the box is in the first row, it switches with whichever of its neighbors to the

right or above is smaller.

If both neighbors are equal, say they are a, then their other neighbor is necessarily a + 1, as we have a reduced decomposition. Locally we will have the following configuration, where [figure] denotes the empty box and a + b + 1 < c:

[figure: a; a; a+1; a+1; a+2; · · · · · ·; ⋯; a+b; a+b; a+b+1; c]

The empty box moves through this configuration, transforming it into:

[figure: a; a+1; a+1; a+2; · · · · · ·; ^{· · · · · ·}; a+b; a+b+1; a+b+1; c]

This guarantees that we still have a reduced decomposition for w.

2. If the box is in the second row, then it switches with its neighbour to the right. If y + p > q, then we may analogously perform an outward slide, beginning with

an empty box at (q + 1, 2) and sliding to the left or down according to local rules that are the reverse of those for the inward slide.

We note some consequences of this definition.

• The box will change rows at the first pair of entries b ≤ c it encounters with b at (i, 2) and c immediately to its lower right at (i + 1, 1). If there is no such pair, it will change rows at the end of the first row in an inward slide if p + y = q, and at the beginning of the second row in an outward slide if y = 0.

• At least one of these will occur if y is minimal given the word of the tableau and p, q. Suppose this is the case. Then the tableau T′ obtained from a slide will have another such pair b′ ≤ c′ with b′ at (ı′, 2) and c′ at (ı′ + 1, 1). Hence, if we perform a second slide, the box will again change rows.

• The inward and outward slides are inverses.

Let \overline{H}_{α}(w) be the subset of H_{α}(w) consisting of chains ρ such that T (α, ρ) has skew shape. The proof of the following lemma is straightforward.

Lemma 4.3. Let w ∈ S_{∞} and suppose p < q with p + q = ℓ(w). Then H_{(q,p)}(w) = \overline{H}_{(q,p)}(w) and

1. For every ρ ∈ H_{(q,p)}(w), we may perform q − p inward slides to T ((q, p), ρ). If ρ′ is the word of the resulting tableau, then the map ρ ↦ ρ′ defines a bijection

H_{(q,p)}(w) ⟷ H_{(p,q)}(w).

The inverse map is given by the application of q − p outward slides.

2. If we now let ρ′ be the word of the tableau obtained after q − p − 1 inward slides to T ((q, p), ρ) for ρ ∈ H_{(q,p)}(w), then the map ρ ↦ ρ′ defines a bijection

\overline{H}_{(q,p)}(w) ⟷ \overline{H}_{(p+1,q−1)}(w).

The inverse map is defined by the application of q − 1 − p outward slides.

The first part gives a proof that intervals in the weak order are symmetric: Let α = (α_{1}, …, α_{k}) and α′ = (α_{1}, …, α_{r+1}, α_{r}, …, α_{k}) be compositions of ℓ(w). Then applying the bijection in Lemma lem:bijections(1) to the segment ρ_{r} of ρ ∈ H_{α}(w) between I(α)_{r−1} and I(α)_{r+1} defines a bijection

H_{α}(w) ⟷ H_{α′}(w).

Remark 4.4. This bijection is different from the one used in [30] to prove symmetry of these intervals. Indeed, consider the example given there, which we write as a tableau:

In [30], Stanley maps this to

But the bijection we define gives us this:

Now we may define θ. By the definition of λ_{π}, if ρ ∈ H_{λ_{π}}(w), then T (ρ) has shape λ if and only if T (λ_{π}, ρ) has partition shape, which implies that π = 1.

Definition 4.5. Suppose w ∈ S_{∞} and λ ⊢ ℓ(w) is a partition with λ_{k+1} = 0. Let π ∈ S_{k}. For ρ ∈ H_{λ_{π}}(w), define θ(π, ρ) as follows:

1. If T (ρ) has shape λ, set θ(π, ρ) = (π, ρ). In this case, π = 1, so λ_{π} = λ and T (ρ) = T (λ_{π}, ρ).

2. If T (ρ) does not have shape λ, then T (λ_{π}, ρ) has skew shape and we select

r = r(T (λ_{π}, ρ)) with 1 ≤ r < k as follows:

Left justify the rows of T (λ_{π}, ρ). Since T (λ_{π}, ρ) has skew shape, there is an entry a of this left-justified figure in postiton (i, r + 1) either with no entry in position (i, r) just below it, or else with an entry b ≥ a just below it. Among all such (i, r) choose the one with i minimal, and for this i, r maximal.

Let ρ_{r} be the word given by the rows r + 1 and r of T (λ_{π}, ρ) and (q, p) the lengths of these two rows. Then T ((q, p), ρ_{r}) has skew shape, and we may apply the map of Lemma 4.3(2) to obtain the word ρ′_{r}. Define θ(π, ρ) = (π′, ρ′), where ρ′ is the word obtained from ρ by replacing ρ_{r} with ρ′_{r} and π′π^{−1} = (r, r+1). Note that T (λ_{π′}, ρ′) also has skew shape and T (ρ′) does not have shape λ.

Example 4.6. Let w = 4621357 and λ = (4, 3, 3, 1). Then ρ = 5.345.236.1236 ∈ H_{λ}(w) but

T (λ, ρ) = 53 4 5 2 3 6 1 2 3 5

has skew shape. Left-justifying the rows of T (λ, ρ), we obtain:

53 4 5 2 3 6 1 2 3 5

This is not a tableau, as the third column reads 365, which is not increasing. Since this is the first such column and the last decrease is at position 2, we have r = 2. Since these two rows each have length 3, we perform one outward slide (by our choice of r, we can perform such a slide!) to obtain the tableau T ((4, 2), ρ′_{r}) as follows:

Thus ρ′ = 5.3456.23.1235 ∈ H_{λ_{(2, 3)}}(w). If we left justify T (λ_{(2, 3)}, ρ′), then we obtain:

53 4 5 6 2 3 1 2 3 5

[figure: 3; 4; 5; 2; 3; 6; ⟶; 3; 4; 5; 6; 2; 3; ⟶; 3; 4; 5; 6; 2; 3]

The 5 in the third row has no lower neighbour, hence 2 = r(λ, ρ) = r(λ_{(2, 3)}, ρ′).

We complete the proof of Theorem 4.1 by showing that θ is an involution. This is a consequence of Lemma 4.3(2) and the following fact:

Lemma 4.7. In (2) of Definition 4.5, if ρ ∈ H_{λ_{π}}(w) and T (λ_{π}, ρ) has skew shape, then r(T (λ_{π}, ρ)) = r(T (λ_{π′}, ρ′)).

Proof. Suppose we are in the situation of (2) in Definition 4.5. The lemma follows once we show that that T ((q, p), ρ_{r}) and T ((p+1, q −1), ρ′_{r}) agree in the first i entries of their second rows, the first i − 1 entries of their first rows, and the ith entry c in the first row of T ((p + 1, q − 1), ρ′_{r}) satisfies a ≤ c, or else there is no ith entry.

In fact, we show this holds for each intermediate tableau obtained from T ((q, p), ρ) by some of the slides used to form T ((p + 1, q − 1), ρ′).

We argue in the case that p < q, that is, for inward slides. Suppose that T is an intermediate tableau satisfying the claim, and that the tableau T′ obtained from T by a single inward slide is also an intermediate tableau. It follows that T′ has skew shape, so that if (y + s, t)/(y, 0) is the shape of T, then y > 1.

Suppose that during the slide the box changes rows at the jth column. We claim that j ≥ i + y − 1(> i). If this occurs, then the first i entries in the second row and first i − 1 entries in the first row of T are unchanged in T′. Also, the ith entry in the first row of T′ is either the ith entry in the first row of T (if j ≥ i + y) or it is the jth entry in the second row of T, which is greater than the ith entry, a. Thus showing j ≥ i + y − 1 completes the proof.

To see that j ≥ i + y − 1 note that if j is the last column, then j = t = s + y. Since s ≥ i − 1, we see that j ≥ y + i − 1. If j is not the last column, then the entries b at (j, 2) c at (j + 1, 1) of T satisfy b ≤ c. Suppose that j < i + y − 1. Then c is the (j − y + 1)th entry in the first row of T. Since j − y + 1 < i, our choice of i ensures that c is less than the entry at (j − y + 1, 2) of T. Since j − y + 1 < j, this in turn is less than b, a contradiction.

Similar arguments suffice for the case when p ≥ q.

Remark 4.8. While it may seem this proof has only a formal relation to the proof of Remmel and Shimozono [28], it is in fact nearly an exact translation—the only difference being in our choice of r. (Their choice of r is not easily expressed in this setting.) We elaborate.

The exact same proof, but with the ordinary jeu de taquin, shows that c_{ν}^{[μ,λ]_{⊂}} counts the chains in [μ, λ]_{⊂} whose word is the word of a tableau of shape ν. This is just the Littlewood-Richardson coefficient c_{μ ν}^{λ}. One way to see this is to consider the bijection between H_{ν}([μ, λ]_{⊂}) and the set of semistandard Young tableaux of shape λ/μ and content (ν_{k}, …, ν_{1}). The chains whose word is the word of a tableau of shape ν correspond to reverse LR tableaux of shape λ/μ, which are defined as follows:

Let f_{a,b}(T) be the number of a’s in the first b positions of the word of T. A reverse LR tableau T with largest entry k is a tableau satisfying:

f_{1,b}(T) ≤ f_{2,b}(T) ≤ ⋯ ≤ f_{k,b}(T)

for all b. It is an exercise to verify that there are exactly c_{μν}^{λ} reverse LR tableaux of shape λ/μ and content ν_{k}, …, ν_{2}, ν_{1}.

The choice we make of i and r is easily expressed in these terms: i is the minimum value of f_{a,b}(T) among all violations f_{a,b}(T) > f_{a+1,b}(T), and if a is the minimal first index among all violations with f_{a,b}(T) = i, then r = k − a. The choice in [28] for reverse LR tableaux would be r = k − a, where f_{a,b}(T) is the violation with minimal b.

The key step we used was the jeu de taquin whereas Remmel and Shimozono used an operation built from the r-pairing of Lascoux and Schützenberger [20]. In fact, this too is a direct translation.

The reason for this is, roughly, that the passage from the word of a chain ρ ∈ H_{α}([μ, λ]_{⊂}) to a semistandard Young tableau of shape λ/μ and content (α_{k}, …, α_{1}) (which interchanges shape with content) also interchanges Knuth equivalence and dual Knuth equivalence [13]. The operators constructed from the r-pairing preserve the dual equivalence class of a 2-letter word but alter its content. In fact, this property characterizes such an operation.

As shown in [13], there is at most one tableau in a given Knuth equivalence class and a given dual equivalence class. Also, for semistandard Young tableaux with at most 2 letters, there is at most one tableau with given partition shape and content. It follows that any operation on tableaux acting on the subtableau of entries r, r + 1 which preserves the dual equivalence class of the subtableau, but reverses its content is uniquely defined by these properties.

Thus the symmetrization operators in [20], which generate an S_{∞}-action on tableaux extending the natural action on their contents, is unique. Expressed in this form, we see that this action coincides with one introduced earlier by Knuth [15]. This action was the effect of permuting rows of a matrix on the P -symbol obtained from that matrix by Knuth’s generalization of the Robinson-Schensted correspondence. The origin of these symmetrization operators in the work of Knuth has been overlooked by most authors, perhaps because Bender-Knuth [1] later use a different operation to prove symmetry.

For each poset P in the classes of labeled posets we consider here, the symmetric function S_{P} is Schur-positive. When P is an interval in some k-Bruhat order, this follows from geometry, for intervals in Young’s lattice, this is a consequence of the Littlewood-Richardson rule, and for intervals in the weak order, it is due to Lascoux-Schützenberger [21] and Edelman-Greene [9]. Is there a representation-theoretic explanation? In particular, we ask:

Question: If P is an interval in a k-Bruhat order, can one construct a representation V_{P} of S_{rankP} so that S_{P} is its Frobenius character? More generally, for a labeled poset P, can one define a (virtual) representation V_{P} so that S_{P} is its Frobenius character? If so, is V_{P ×Q} ≃ V_{P} ⊗ V_{Q}?

When P is an interval in Young’s lattice this is a skew Specht module. For an interval [1, w]_{weak} in the weak order, Kráskiewicz [17] constructs a S_{ℓ(w)}-representation of dimension #R(w). For general linear group represenations, such a construction is known. For intervals in the weak oder, this is due to Kráskiewicz and Pragacz [18].

5. The monomials in a Schubert polynomial

We give a new proof based upon geometry that a Schubert polynomial is a sum of monomials with non-negative coefficients. This analysis leads to a combinatorial construction of Schubert polynomials in terms of chains in the Bruhat order. It also shows these coefficients are certain intersection numbers, essentially the same interpretation found by Kirillov and Maeno [14].

The first step is Theorem 5.1, which generalizes both Proposition 1.7 of [22] and

Theorem C (ii) of [3]. Recall that u ⟶^{r[m,k]} w when one of the following equivalent conditions holds:

• c_{u, r[m,k]}^{w} = 1.

• u ≤_{k} w and wu^{−1} is a disjoint product of increasing cycles.

• There is an chain in [u, w]_{k}:

u ⟶^{b_{1}} u_{1} ⟶^{b_{2}} ⋯ ⟶^{b_{m}} u_{m} = w

with b_{1} < b_{2} < ⋯ < b_{m}. For p ∈ ℕ, define the map Φ_{p} : ℤ[x_{1}, x_{2}, …] ⟶ ℤ[y] ⊗ ℤ[x_{1}, x_{2}, …] by

Φ_{p}(x_{i}) = \{ \begin{matrix}x_{i} & if i < p \\ y & if i = p \\ x_{i−1} & if i > p \end{matrix} .

For w ∈ S_{∞} and p, q ∈ ℕ, define φ_{p,q}(w) ∈ S_{∞} by

φ_{p,q}(w)(j) = \{ \begin{matrix}w(j) & j < p and w(j) < q \\ w(j) + 1 & j < p and w(j) ≥ q \\ q & j = p \\ w(j − 1) & j > p and w(j) < q \\ w(j − 1) + 1 & j > p and w(j) ≥ q \end{matrix} .

Representing permutations as matrices, φ_{p,q} adds a new pth row and qth column consisting mostly of zeroes, but with a 1 in the (p, q)th position. For example,

φ_{3,3}(23154) = 243165 and φ_{2,5}(2341) = 25342.

Theorem 5.1. For u ∈ S_{n},

Φ_{p}𝔖_{u} = ∑_{j, w with_{u⟶^{r[n+1−p−j, p]}φ_{p,n+1}(w)}} y^{j} 𝔖_{w}(x).

Moreover, if n is not among {u(1), …, u(p − 1)}, then the sum may be taken over

those j, w with u ⟶^{r[n−p−j, p]} φ_{p,n}(w).

Iterating this gives another proof that the monomials in a Schubert polynomial have non-negative coefficients.

Example 5.2. Consider Φ_{2}𝔖_{13542}. We display all increasing chains in the 2-Bruhat order on S_{5} above 13542 whose endpoint w satisfies w(2) = 5:

We see therefore that

13542 ⟶^{r[3,2]} 25431 = φ_{2,5}(2431),
13542 ⟶^{r[2,2]} 25341 = φ_{2,5}(2341),
13542 ⟶^{r[2,2]} 15432 = φ_{2,5}(1432),
13542 ⟶^{r[1,2]} 15342 = φ_{2,5}(1342).

Then Theorem 5.1 asserts that

Φ_{2}𝔖_{13542} = 𝔖_{2431}(x) + y𝔖_{2341}(x) + y𝔖_{1432}(x) + y^{2}𝔖_{1342}(x),

which may also be verified by direct calculation.

Proof of Theorem 5.1. We make two definitions. For p ≤ n, define another map ψ_{p,[n]} : S_{n} × S_{m} ↪ S_{n+m} by

ψ_{p,[n]}(w, z)(i) = \{ \begin{matrix}w(i) & i < p \\ n + z(1) & i = p \\ w(i − 1) & p < i ≤ n + 1 \\ n + z(i − n) & n + 1 < i ≤ n + m \end{matrix} . (5)

Then ψ_{p,[n]}(1, 1) = r[n+1−p, p].

Let P ⊂ {1, 2, …, n + m} and suppose that

P = p_{1} < p_{2} < ⋯ < p_{n},
{1, …, n + m} − P = q_{1} < q_{2} < ⋯ < q_{m}.

Define the map Ψ_{P} : ℤ[x_{1}, x_{2}, …, x_{n+m}] ⟶ ℤ[x_{1}, …, x_{n}] ⊗ ℤ[y_{1}, …, y_{m}] by

Ψ_{P} (x_{i}) = \{ \begin{matrix}x_{j} & if i = p_{j} \\ y_{j} & if i = q_{j} \end{matrix} .

Suppose now that P = {1, 2, …, p − 1, p + 1, …, n + 1}. Then for u ∈ S_{n+m}, Theorem 4.5.4 of [3] asserts that

Ψ_{P} 𝔖_{u} ≡ ∑_{w∈S_{n}, z∈S_{m}} c_{u r[n+1−p,p]}^{ψ_{p,[n]}(w,z)}𝔖_{w}(x) ⊗ 𝔖_{z}(y), (6)

modulo the ideal ⟨𝔖_{w}(x) ⊗ 1, 1 ⊗ 𝔖_{z}(y) | w ∉ S_{n}, z ∉ S_{m}⟩ which is equal to the ideal ⟨x^{α} ⊗ 1, 1 ⊗ y^{α} | α_{i} ≥ n − i for some i⟩. (The calculation is in the cohomology of the product of flag manifolds Flags(ℂ^{n})×Flags(ℂ^{m}).)

Suppose now that u ∈ S_{n} and m ≥ n. Then (6) is an identity of polynomials, and not just of cohomology classes. We also see that Ψ_{P} 𝔖_{u} = Φ_{p}𝔖_{u}, since 𝔖_{u} ∈ ℤ[x_{1}, …, x_{n}]. By the Pieri formula,

c_{u r[n+1−p,p]}^{ψ_{p,[n]}(w,z)} = \{ \begin{matrix}1 & if u ⟶^{r[n+1−p, p]} ψ_{p,[n]}(w, z), \\ 0 & otherwise. \end{matrix}

Since u ≤_{p} ψ_{p,[n]}(w, z) and u(n + i) = n + i, Definition 1.1 (2) (for u ≤_{p} ψ_{p,[n]}(w, z)) implies that

ψ_{p,[n]}(w, z)(n + 1) < ψ_{p,[n]}(w, z)(n + 2) < · · · .

Thus by the definition (5) of ψ_{p,[n]}, we have z(2) < z(3) < ⋯, and so z is the Grassmannian permutation r[z(1)−1, 1]. Hence 𝔖_{z}(y) = y^{z(1)−1}.

If we set j = z(1) − 1, then ψ_{P,[n]}(w, z) = φ_{p,n+1+j}(w). Thus, for u ∈ S_{n}, we have

Φ_{p}𝔖_{u} = ∑_{j, w such that_{u⟶^{r[n+1−p, p]}φ_{p,n+1+j}(w)}} y^{j} 𝔖_{w}(x).

Suppose that u ⟶^{r[n+1−p, p]} φ_{p,n+1+j}(w). Consider the unique increasing chain in the interval [u, φ_{p,n+1+j}(w)]_{p}:

u = u_{0} ⟶^{b_{1}} ⋯ ⟶^{b_{n−p−j}} u_{n−p−j} ⟶^{b_{n+1−p−j}} ⋯ ⟶^{b_{n+1−p}} φ_{p,n+1+j}(w).

Because u ∈ S_{n}, we must have b_{n+1−p−j} = n + 1 and so u_{n+1−p−j} = φ_{p,n+1}(w). Moreover, if n is not among {u(1), …, u(p)}, then we have b_{n−p−j} = n and so u_{n−p−j} = φ_{p,n}(w). If u(p) = n, then we also have u_{n−p−j} = φ_{p,n}(w). This completes the proof.

Define δ to be the sequence (n − 1, n − 2, …, 1, 0).

Corollary 5.3. For w ∈ S_{n} and α < δ, the coefficient of x^{δ−α} in 𝔖_{w} is the number of chains

w ⋖ w_{1} ⋖ w_{2} ⋖ ⋯ ⋖ w_{α_{1}+···+α_{n−1}} = ω_{0}

in the Bruhat order where, for each 1 ≤ k ≤ n − 1,

w_{α_{1}+···+α_{k−1}} ⋖_{k} w_{1+α_{1}+···+α_{k−1}} ⋖_{k} ⋯ ⋖_{k} w_{α_{1}+···+α_{k}} (7)

is an increasing chain in the k-Bruhat order.

Example 5.4. Here are all such chains in S_{4} from 1432 to 4321, with the index α displayed above each chain:

From this, we see that

𝔖_{1432} = x^{321−111} + x^{321−120} + x^{321−201} + x^{321−210} + x^{321−300}
= x_{1}^{2}x_{2} + x_{1}^{2}x_{3} + x_{1}x_{2}^{2} + x_{1}x_{2}x_{3} + x_{2}^{2}x_{3}.

Proof. Repeatedly applying Φ_{1} and iterating Theorem 5.1, we see that the coefficient of x^{δ−α} in 𝔖_{w}(x) is the number of chains

w ⋖ w_{1} ⋖ w_{2} ⋖ ⋯ ⋖ w_{α_{1}+···+α_{n−1}} = ω_{0}

which satisfy the conditions of the corollary, together with the (apparent) additional requirement that, for each k < n,

w_{α_{1}+···+α_{k}}(j) = n + 1 − j for all j ≤ k. (8)

The corollary will follow, once we show this is no additional restriction.

First note that if u ⟶^{r[a,k]} u′ with u′(j) = n + 1 − j for 1 ≤ j ≤ k, but u(i) < n + 1 − i for some 1 ≤ i ≤ k, then i = k. To see this, note that since u ≤_{k} u′, the form of u′ and Definition 1.1 (2) implies that u(1) > u(2) > ⋯ > u(k). Set

ζ = u′u^{−1}. Since u ⟶^{r[a,k]} u′, ζ is a disjoint product of increasing cycles, hence their supports are are non-crossing. Suppose i < k. Then {u(i), n + 1 − i = u′(i)} and {u(i + 1), n − i = u′(i + 1)} are in the support of distinct cycles. However, u(i + 1) < u(i) ≤ n − i < n + 1 − i contradicts that these supports are non-crossing, so we must have i = k.

Let

w ⋖ w_{1} ⋖ w_{2} ⋖ ⋯ ⋖ w_{α_{1}+···+α_{n−1}} = ω_{0}

be a chain which satisfies the conditions of the corollary. We prove that (8) holds for all k < n by downward induction. Since ω_{0} = w_{α_{1}+···+α_{n−1}}, we see that (8) holds for k = n−1. Suppose that (8) holds for some k. Set u = w_{α_{1}+···+α_{k−1}} and u′ = w_{α_{1}+···+α_{k}}.

Then u ⟶^{r[α_{k},k]} u′ with u′(j) = n + 1 − j for 1 ≤ j ≤ k. By the previous paragraph, we must have u(i) = n + 1 − i for all i < k, hence (8) holds for k − 1.

We could also have written the coefficient of x^{δ−α} in 𝔖_{w}(x) as the number of chains

w ⟶^{r[α_{1},1]} w_{1} ⟶^{r[α_{2},2]} w_{2} ⟶^{r[α_{3},3]} ⋯ ⟶^{r[α_{n−1},n−1]} ω_{0}

in S_{n}. From this and the Pieri formula for Schubert polynomials, we obtain another description of these coefficients. First, for α = (α_{1}, α_{2}, …, α_{n−1}) with α_{i} ≥ 0, let h(α) denote the product of complete homogeneous symmetric polynomials

h_{α_{1}}(x_{1})h_{α_{2}}(x_{1}, x_{2}) ⋯ h_{α_{n−1}}(x_{1}, x_{2}, …, x_{n−1}).

Corollary 5.5. For w ∈ S_{n},

𝔖_{w} = ∑_{α} d_{α}^{w}x^{δ−α}

where d_{α}^{w} is the coefficient of 𝔖_{ω_{0}} in the product 𝔖_{w} · h(α).

This is essentially the same formula as found by Kirillov and Maeno [14] who showed that the coefficient of x^{δ−α} in 𝔖_{w} to be the coefficient of 𝔖_{ω_{0}} in the product 𝔖_{ω_{0}wω_{0}} · e(α), where

e(α) = e_{α_{n−1}}(x_{1})e_{α_{n−2}}(x_{1}, x_{2}) ⋯ e_{α_{1}}(x_{1}, …, x_{n−1}).

To see these are equivalent, note that the algebra involution 𝔖_{w} ↦ 𝔖\overline{w} on H^{∗}(Flags(ℂ^{n})) interchanges e(α) and h(α).

Acknowledgments

We thank Mark Shimozono and Richard Stanley for helpful comments. The second author is grateful to the hospitality of Université Genève and INRIA Sophia-Antipolis, where portions of this paper were developed and written.

References

[1] E. Bender and D. Knuth, Enumeration of plane partitions, J. Combin. Theory, Ser. A, 13 (1972), pp. 40–54.

[2] N. Bergeron, A combinatorial construction of the Schubert polynomials, J. Combin. Theory, Ser. A, 60 (1992), pp. 168–182.

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

[4] , A moniod for the universal k-Bruhat order. MSRI preprint 1997-073, 24 pages, 1997.

[5] I. N. Bernstein, I. M. Gelfand, and S. I. Gelfand, Schubert cells and cohomology of the spaces G/P, Russian Mathematical Surveys, 28 (1973), pp. 1–26.

[6] S. Billey, W. Jockush, and R. Stanley, Some combinatorial properties of Schubert polynomials, J. Algebraic Combinatorics, 2 (1993), pp. 345–374.

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

[8] M. Demazure, Désingularization des variétés de Schubert généralisées, Ann. Sc. E. N. S. (4), 7 (1974), pp. 53–88.

[9] P. Edelman and C. Greene, Balanced tableaux, Adv. Math., 63 (1996), pp. 1–25.

[10] S. Fomin and A. N. Kirillov, Combinatorial B_{n}-analogs of Schubert polynomials, Trans. AMS, 348 (1996), pp. 3591–3620.

[11] S. Fomin and A. N. Kirillov, Yang-Baxter equation, symmetric functions and Schubert polynomials, Discrete Math., 153 (1996), pp. 124–143. Proceedings of the 5th Conference on Formal Power Series and Algebraic Combinatorics (Florence, 1993).

[12] S. Fomin and R. Stanley, Schubert polynomials and the nilCoxeter algebra, Adv. Math., 103 (1994), pp. 196–207.

[13] M. Haiman, Dual equivalence with applications, including a conjecture of Proctor, Discrete Math., 99 (1992), pp. 79–113.

[14] A. Kirillov and T. Maeno, Quantum double Schubert polynomials, quantum Schubert polynomials, and the Vafa–Intriligator formula. 52 pp., 1997.

[15] D. Knuth, Permutations, matrices and generalized Young tableaux, Pacific J. Math., 34 (1970), pp. 709–727.

[16] A. Kohnert, Weintrauben, Polynome, Tableaux, Bayreuth Math. Schrift., 38 (1990), pp. 1–97.

[17] W. Kráskiewicz, Reduced decompositions in Weyl groups, Europ. J. Combin., 16 (1995), pp. 293–313.

[18] W. Kráskiewicz and P. Pragacz, Schubert functors and Schubert polynmials, C. R. Acad. Sci. Paris, 304 (1987), pp. 209–211.

[19] G. Kreweras, Sur les partitions non croissees d’un cycle, Discrete Math., 1 (1972), pp. 333– 350.

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

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

[22] , 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.

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

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

[25] , Symmetric Functions and Hall Polynomials, Oxford University Press, 1995. second edition.

[26] D. Monk, The geometry of flag manifolds, Proc. London Math. Soc., 9 (1959), pp. 253–286.

[27] A. Postnikov, On a quantum version of Pieri’s formula. To appear in Progress in Geometry, J.-L. Brylinski and R. Brylinski, eds., 1997.

[28] J. Remmel and M. Shimozono, A simple proof of the Littlewood-Richardson rule and applications. Manuscript.

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

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

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

[32] R. Winkel, Diagram rules for the generation of Schubert polynomials. manuscript,

    http://www.iram.rwth-aachen.de/~winkel/pp.html, 1995.

[33] , On the multiplication of Schubert polynomials. to appear in Adv. in Appl. Math., man-

    uscript at http://www.iram.rwth-aachen.de/~winkel/pp.html, 1996.

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

  E-mail address: bergeron@mathstat.yorku.ca
  URL: http://www.math.yorku.ca/bergeron

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

  E-mail address: sottile@math.toronto.edu
  URL: http://www.math.toronto.edu/~sottile