A GEOMETRIC APPROACH TO THE COMBINATORICS OF SCHUBERT POLYNOMIALS

FRANK SOTTILE

English Summary

Schubert polynomials, which had their origins in the cohomology of flag varieties, have recently been the subject of much interest in algebraic combinatorics. This scrutiny has led to an elucidation of many of their properties. A basic open problem is to give a rule for multiplying two Schubert polynomials, that is, find an analog of the Littlewood-Richardson rule for Schubert polynomials.

Our talk would discuss some recent work on this problem using ideas from algebraic geometry, as well as some implications of this work for the combinatorics of the symmetric group. Specifically, we will describe a geometric proof of an analog of Pieri’s rule for Schubert polynomials. This was stated by Lascoux and Schützenberger in [?], where an algebraic proof was suggested. Interpreting this formula geometrically exposes a new and striking link to the Littlewood-Richardson rule for Schur polynomials, and indicates possible extensions of this result. While our approach uses ideas and methods from algebraic geometry, we will present proofs involving little more than elementary (albeit complicated) linear algebra.

Résumé

Les polynômes de Schubert, qui sont issus de la cohomologie des variétés de drapeaux, ont sucité depuis quelques temps un grand intérêt en combinatoire algébrique. Un examen attentif a conduit à l’élucidation de beaucoup de leurs propriétés. Un problème ouvert fondamental est de trouver une règle pour multiplier deux polynômes de Schubert, autrement dit, un analogue de la règle de Littlewood-Richardson.

Notre exposé discutera certains travaux récents sur ce problème en faisant appel à des idées provenant de la géométrie algébrique, et aussi certaines conséquences de ces travaux pour la combinatoire du groupe symétrique. Plus précisément, nous décrirons une preuve géométrique d’un analogue de la règle de Pieri pour les polynômes de Schubert. Cette règle a été énoncée dans [?], où une preuve algébrique était suggérée. L’interpretation géométrique de cette formule met en évidence un lien nouveau et surprenant avec la règle de Littlewood-Richardson, et indique des extensions possibles de ce résultat. Bien que notre approche fasse appel à des idées et des méthodes de géométrie algébrique, nous présenterons des preuves qui n’utilisent guère que de l’algèbre linéaire élémentaire (quoique compliquée).

Date: 8 March, 1995.

Extended abstract of talk delivered at SFCA’95 29 May – 2 June, 1995, Paris. Published in conference abstracts, pp 501–510.

1. Structure Constants for Schubert Polynomials

The Appendix contains a brief introduction to Schubert polynomials. Let S_{n} be the symmetric group of permutations on the set {1, 2, …, n} and S_{∞} = ⋃_{n=1}^{∞} S_{n}, the group of permutations of the positive integers that fix all but finitely many integers. The collection of Schubert polynomials {𝔖_{w} | w ∈ S_{∞}} forms a basis for the polynomial ring R_{∞} = ℤ[x_{1}, x_{2}, …]. A basic open question is the analog of the Littlewood-Richardson rule: For u, v, w ∈ S_{n}, find integer constants c_{uv}^{w} such that

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

These structure constants are positive and are known only in certain special cases.

For example, if both u and v are Grassmannian permutations with descent k so that 𝔖_{u} and 𝔖_{v} are symmetric polynomials in the variables x_{1}, …, x_{k}, then (??) reduces to the classical Littlewood-Richardson rule.

An important case is when one of u or v is an adjacent transposition, t_{k k+1}. This is usually attributed to Monk [?]. However, at the same time Chevalley established the analogous formula for generalized flag varieties in an unpublished manuscript [?]. For w ∈ S_{∞}, let ℓ(w) be the length of w. Monk’s rule states:

𝔖_{w} · 𝔖_{t_{k k+1}} = ∑ 𝔖_{w·t_{a b}},  (2)

the sum over all a ≤ k < b with ℓ(wt_{a b}) = ℓ(w) + 1. We use geometry to prove a similar result, which is the analog for Schubert polynomials of the classical Pieri’s rule. This analog of Pieri’s rule was announced by Lascoux and Schützenberger in [?], where an algebraic proof was suggested.

Permutations w are represented by the sequence (w(1), w(2), …) of their values. For positive integers k, m, we define the permutations:

r[k, m] = (1, 2, …, k−1, k+m, k, k+1, …, k+m−1, k+m+1, …)
c[k, m] = (1, 2, …, k−m, k−m+2, …, k+1, k−m+1, k+2, …)

Let w, w′ ∈ S_{∞}. Write w ⟶^{r[k,m]} w′ if there exist a_{1}, b_{1}, …, a_{m}, b_{m} such that

(a) a_{i} ≤ k < b_{i} for 1 ≤ i ≤ m and w′ = w · t_{a_{1} b_{1}} ⋯ t_{a_{m} b_{m}},

(b) ℓ(w^{(i)}) = ℓ(w) + i, where w^{(0)} = w and w^{(i)} = w^{(i−1)} · t_{a_{i} b_{i}},

(c) w^{(1)}(a_{1}) < w^{(2)}(a_{2}) < ⋯ < w^{(m)}(a_{m}). Equivalently, given any a_{1}, …, b_{m} satisfying (a) and (b), b_{1}, …, b_{m} are distinct. Simi-

larly, write w ⟶^{c[k,m]} w′ if we have such a_{1}, b_{1}, …, a_{m}, b_{m} where now

w^{(1)}(a_{1}) > w^{(2)}(a_{2}) > ⋯ > w^{(m)}(a_{m}).

The range of summation in Monk’s rule (??) generates a partial order ≤_{k} on S_{n} by w ≤_{k} wt_{a b} whenever a ≤ k < b and ℓ(wt_{a b}) = ℓ(w) + 1. We call it the k-Bruhat order (k-colored Ehresmanoëdre in [?]). The data (a_{1}, b_{1}), …, (a_{m}, b_{m}) in the definition of

w ⟶^{r[k,m]} w′ describe a particular path from w to w′ in the k-Bruhat order.

Theorem 1. Let w ∈ S_{∞} and k, m be positive integers. Then we have

1. 𝔖_{w} · 𝔖_{r[k,m]} = ∑_{w⟶^{r[k,m]}w′} 𝔖_{w′}.

2. 𝔖_{w} · 𝔖_{c[k,m]} = ∑_{w⟶^{c[k,m]}w′} 𝔖_{w′}.

This is in a different form than the original statement in [?]. Bergeron and Billey [?] independently conjectured the above form.

This form exposes a link between multiplying Schubert polynomials and paths in the Bruhat order. Such a link is not unexpected. The Littlewood-Richardson rule for multiplying Schur functions may be expressed as a sum over certain paths in Young’s lattice of partitions. Lascoux and Schützenberger [?] give a procedure for multiplying Schur polynomials based upon paths in the Bruhat order on S_{n}. A connection between paths in the Bruhat order and the intersection theory of Schubert varieties is described in [?]. We believe the eventual description of the structure constants c_{uv}^{w} will be in terms of paths of certain types in the Bruhat order on S_{n}.

We first establish the equivalence of the two formulas given in Theorem ??, then prove the first formula by reducing it to the classical Pieri’s rule. Our approach illustrates an unexpected link to the classical Pieri’s rule, allowing the elucidation of more structure constants. We conclude with a ‘path counting formula’ generalizing Theorem ?? where 𝔖_{r[k,m]} and 𝔖_{c[k,m]} are replaced by hook Schur polynomials.

We would like to thank Sara Billey who suggested these problems to us, Jean-Yves Thibon for indicating to us the work of Lascoux and Schützenberger, and Nantel Bergeron for many stimulating discussions about these results and possible extensions.

2. The Flag Variety

Let 𝔽(n) denote the variety of complete flags in ℂ^{n}, that is

𝔽(n) = {E.: E_{1} ⊂ E_{2} ⊂ ⋯ ⊂ E_{n} = ℂ^{n} | dim E_{j} = j}.

A fixed flag F. determines a cell decomposition of 𝔽(n) due to Ehresmann [?], which may be indexed by elements of S_{n}. The cell determined by w ∈ S_{n} is

{E.| ∃ f_{1}, …, f_{n} with f_{i} ∈ F_{n+1−w(i)} − F_{n−w(i)} for 1 ≤ i ≤ n and E_{j} = span{f_{1}, …, f_{j}}, for 1 ≤ j ≤ n},

which has codimension ℓ(w). Its closure is the Schubert variety X_{w}F..

The cohomology classes^{1} [X_{w}F.] of the Schubert varieties X_{w}F. give an integral basis for the cohomology ring of the flag variety [?]. Using Chern classes, Borel [?] gave an alternate description of this ring as H_{n} = ℤ[x_{1}, …, x_{n}]/S, where S is the ideal generated by the symmetric polynomials. These two descriptions were reconciled by Demazure [?] and Berstein-Gelfand-Gelfand [?], who described representatives for the cohomology classes of Schubert varieties. Later, Lascoux and Schützenberger [?] gave explicit polynomial representatives 𝔖_{w}, called Schubert polynomials.

1Strictly speaking, we mean the classes Poincaré dual to the fundamental cycles in homology.

We utilize a few algebraic facts about these cohomology rings. Let w_{0} be the longest element of S_{n}, that is, w_{0}(j) = n+1−j. Then X_{w_{0}}F. = {F.}, so 𝔖_{w_{0}} is the class of a point. The Schubert polynomial basis is a Poincaré dual basis; by this we mean if ℓ(w) + ℓ(w′) = ℓ(w_{0}), then

𝔖_{w} · 𝔖_{w′} = \{ \begin{matrix}𝔖_{w_{0}} & if w′ = w_{0}w \\ 0 & otherwise \end{matrix} .

There is also an involution induced by the map 𝔖_{w} ⟼ 𝔖_{w_{0}ww_{0}}.

We first observe that the two formulas in Theorem ?? are equivalent. This follows easily from the next lemma.

Lemma 2.

1. Let w, w′ ∈ S_{n}. Then w ⟶^{r[k,m]} w′ if and only if w_{0}ww_{0} ⟶^{c[n−k,m]} w_{0} w′ w_{0}.

2. w_{0} r[k, m] w_{0} = c[n − k, m].

Using Poincaré duality, formula (1) of Theorem ?? is equivalent to

𝔖_{w} · 𝔖_{w_{0}w′} · 𝔖_{r[k,m]} = \{ \begin{matrix}𝔖_{w_{0}} & if w ⟶^{r[k,m]} w′ \\ 0 & otherwise \end{matrix} .

Alternatively,

c_{w r[k,m]}^{w′} = \{ \begin{matrix}1 & if w ⟶^{r[k,m]} w′ \\ 0 & otherwise \end{matrix} .  (3)

To prove (3), fix w and w′ in S_{n}. Note that r[k, m] = t_{k k+1} t_{k k+2} ⋯ t_{k k+m}. Iterating Monk’s rule shows that 𝔖_{r[k,m]} is a summand of 𝔖_{t_{k k+1}}^{m} with coefficient 1. Thus the coefficient of 𝔖_{w′} in the expansion of 𝔖_{w} · 𝔖_{t_{k k+1}}^{m} exceeds the coefficient of 𝔖_{w′} in 𝔖_{w} · 𝔖_{r[k,m]}. The first coefficient is zero unless w ≤_{k} w′ and ℓ(w′) = ℓ(w) + m. Thus c_{w r[k,m]}^{w′} = 0 unless w ≤_{k} w′ and ℓ(w′) = ℓ(w) + m.

For the rest of this section, we will assume that w ≤_{k} w′ and ℓ(w′) = ℓ(w) + m. We will also refer to the accompanying data: integers a_{1}, b_{1}, a_{2}, …, a_{m}, b_{m} with a_{i} ≤ k < b_{i} where w′ = wt_{a_{1} b_{1}} ⋯ t_{a_{m} b_{m}} and ℓ(wt_{a_{1} b_{1}} ⋯ t_{a_{i} b_{i}}) = ℓ(w) + i.

We establish (??) using the cohomology of Grassmann varieties. The association of a flag E.to its k-dimensional part gives a map π from the flag variety to the Grassmannian of k-dimensional subspaces in ℂ^{n}, G(k, n). This induces a ring homomorphism π^{∗} from the cohomology of G(k, n) to that of the flag variety. Algebraically, π^{∗} is induced by the inclusion of symmetric polynomials in x_{1}, …, x_{k} into the ring ℤ[x_{1}, …, x_{n}]. There is also a covariant pushforward map π_{∗} induced via Poincaré duality from the functorial map on homology. While π_{∗} is not a ring homomorphism, it does satisfy the following projection formula (see Example 8.17 of [?]): For cohomology classes α on the flag variety and β on G(k, n), we have:

π_{∗}(α · π^{∗}β) = π_{∗}(α) · β.  (4)

The cohomology ring of G(k, n) is isomorphic to a quotient of the ring of symmetric polynomials in x_{1}, …, x_{k} by the ideal generated by all Schur polynomials s_{λ} where the partition λ satisfies λ_{1} > n − k. The class of a point is s_{(n−k)^{k}}, where (n−k)^{k} is the partition with k parts each equal to n − k. For a partition λ with λ_{1} ≤ n − k and λ_{k+1} = 0, let λ^{c} be the partition (n − k − λ_{k}, …, n − k − λ_{1}). Then s_{λ} and s_{λ^{c}} are Poincaré dual cohomology classes. Let \underline{m} be the partition (m, 0, …, 0). A key fact is that π^{∗}(s\underline{m}) = 𝔖_{r[k,m]}. For partitions μ and λ, write λ ⟶^{m} μ if |λ| + m = |μ| and

μ_{1} ≥ λ_{1} ≥ μ_{2} ≥ ⋯ ≥ μ_{k} ≥ λ_{k}.

That is, if μ ⊃ λ and the skew diagram μ/λ is a skew row of length m.

The classical Pieri’s rule states that for any partitions λ and μ with |λ| + m = |μ|,

s_{λ} · s_{μ^{c}} · s\underline{m} = \{ \begin{matrix}s_{(n−k)^{k}} & if λ ⟶^{m} μ \\ 0 & otherwise \end{matrix} .

We use geometry to prove the following:

Lemma 3. Let w <_{k} w′ be permutations in S_{n}. Suppose w′ = wt_{a_{1} b_{1}} ⋯ t_{a_{m} b_{m}}, where a_{i} ≤ k < b_{i}, and ℓ(wt_{a_{1} b_{1}} ⋯ t_{a_{i} b_{i}}) = ℓ(w) + i. Then

1. There is a cohomology class δ on G(k, n) such that π_{∗}(𝔖_{w} · 𝔖_{w_{0}w′}) = δ · s_{d^{k}}, where d = #{j > k | w(j) = w′(j)} = n − k − #{b_{1}, …, b_{m}}.

2. If w ⟶^{r[k,m]} w′, then there are partitions μ ⊃ λ where μ/λ is a skew row of length m whose j^{th} row is equal to #{i | a_{i} = j} and π_{∗}(𝔖_{w} · 𝔖_{w_{0}w′}) = s_{λ} · s_{μ^{c}}.

In our talk, we will not present a proof of this Lemma. A proof involving a mixture of combinatorics, linear algebra and geometry may be found in [?].

We deduce Theorem ?? from Lemma 3. Suppose w ≤_{k} w′ and ℓ(w′) = ℓ(w) + m. We use π_{∗} to evaluate c_{w r[k,m]}^{w′}. Recall that c_{w r[k,m]}^{w′} is defined by

c_{w r[k,m]}^{w′}𝔖_{w_{0}} = 𝔖_{w} · 𝔖_{w_{0}w′} · 𝔖_{r[k,m]}.

As 𝔖_{w_{0}} is the class of a point, π_{∗}(𝔖_{w_{0}}) = s_{(n−k)^{k}}. Apply π_{∗} to obtain

c_{w r[k,m]}^{w′}s_{(n−k)^{k}} = π_{∗}(𝔖_{w} · 𝔖_{w_{0}w′} · 𝔖_{r[k,m]}).

Since π^{∗}(s\underline{m}) = 𝔖_{r[k,m]}, we apply the projection formula (??) to obtain

c_{w r[k,m]}^{w′}s_{(n−k)^{k}} = π_{∗}(𝔖_{w} · 𝔖_{w_{0}w′}) · s\underline{m}.

Since s\underline{m}s_{d^{k}} = 0 unless d + m ≤ n − k, we apply part (1) of Lemma ?? to see that

π_{∗}(𝔖_{w} · 𝔖_{w_{0}w′}) · s\underline{m} = δ · s_{d^{k}} · s\underline{m} = 0,

unless #{b_{1}, …, b_{m}} = m, that is unless w ⟶^{r[k,m]} w′. Supposing w ⟶^{r[k,m]} w′, part (2) of Lemma ?? and the classical Pieri’s rule shows that

π_{∗}(𝔖_{w} · 𝔖_{w_{0}w′}) · s\underline{m} = s_{λ} · s_{μ^{c}} · s\underline{m} = s_{(n−k)^{k}},

as μ/λ is a skew row of length m. This establishes Theorem ??.

3. Connection to Pieri’s Rule and Extensions

The formulas in Theorem ?? are the analogs of Pieri’s rule for several reasons:

1. The Schubert polynomial 𝔖_{r[k,m]} equals π^{∗}(s\underline{m}).

2. The structure constants in both are either 1 or 0.

3. Theorem ?? is proven by reduction to Pieri’s rule. In [?], we show the geometry of the classical Pieri’s rule and Theorem ?? to be nearly identical. This is the unexpected link to Pieri’s rule mentioned in §1.

The computation of π_{∗}(𝔖_{w}·𝔖_{w_{0}w′}) in Lemma ?? allows us to determine more structure constants. To any partition ν with at most k parts, associate a permutation

w(ν) = (ν_{k} + 1, ν_{k−1} + 2, …, ν_{2} + k − 1, ν_{1} + k, …),

the remaining entries written in increasing order. Then π^{∗}(s_{ν}) = 𝔖_{w(ν)}.

Theorem 4. Let w ∈ S_{n} and k, m be integers. Suppose w ≤_{k} w′ and ℓ(w′) = ℓ(w) + m. Let a_{1}, b_{1}, …, a_{m}, b_{m} be such that a_{i} ≤ k < b_{i} where w′ = wt_{a_{1} b_{1}} ⋯ t_{a_{m} b_{m}} and ℓ(wt_{a_{1} b_{1}} ⋯ t_{a_{i} b_{i}}) = ℓ(w) + i. Then

1. Suppose w ⟶^{r[k,m]} w′. For any partition ν, the structure constant c_{w w(ν)}^{w′} equals the Littlewood-Richardson coefficient c_{λ ν}^{μ}, where μ/λ is a skew row of length m, whose j^{th} row has length μ_{j} − λ_{j} = #{i | a_{i} = j}.

2. Suppose w ⟶^{c[k,m]} w′. For any partition ν, the structure constant c_{w w(ν)}^{w′} equals the Littlewood-Richardson coefficient c_{λ ν}^{μ}, where μ/λ is a skew column of length m, whose j^{th} column has length #{i | b_{i} = j}.

Proof: Using the involution 𝔖_{w} ⟼ 𝔖_{w_{0} w w_{0}}, it suffices to prove part (1). We use part (2) of Lemma ?? to evaluate c_{w w(ν)}^{w′}. Recall that 𝔖_{w(ν)} = π^{∗}(s_{ν}). Then

c_{w w(ν)}^{w′} s_{(n−k)^{k}} = π_{∗}(c_{w w(ν)}^{w′} 𝔖_{w_{0}}) = π_{∗}(𝔖_{w} · 𝔖_{w_{0}w′} · 𝔖_{w(ν)})
= π_{∗}(𝔖_{w} · 𝔖_{w_{0}w′}) · s_{ν}
= s_{λ} · s_{μ^{c}} · s_{ν}
= c_{λν}^{μ} s_{(n−k)^{k}}.

In multiset notation for partitions, (p, 1^{(q−1)}) is the hook shape partition whose first row has length p and first column has length q. Define

h[k; p, q] = w(p, 1^{(q−1)}).

We use Theorem ?? to deduce the following formula for multiplication of an arbitrary Schubert polynomial 𝔖_{w} by the hook symmetric function 𝔖_{h[k; p,q]} = π^{∗}(s_{(p,1^{(q−1)})}).

Theorem 5. Let q ≤ k and k+p ≤ n be integers. Set m = p+q−1. For w ∈ S_{n},

𝔖_{w} · 𝔖_{h[k; p,q]} = ∑ 𝔖_{w t_{a_{1} b_{1}}···t_{am bm}},

the sum over all a_{1}, b_{1}, …, a_{m}, b_{m} with w^{(i)} = wt_{a_{1} b_{1}} ⋯ t_{a_{m} b_{m}} where

(a) For 1 ≤ i ≤ m, we have a_{i} ≤ k < b_{i} and ℓ(w^{(i)}) = ℓ(w) + i.

(b) w^{(1)}(a_{1}) < ⋯ < w^{(p)}(a_{p}) and w^{(p)}(a_{p}) > w^{(p+1)}(a_{p+1}) > ⋯ > w^{(m)}(a_{m}). Alternatively, condition (b) for the summation may be replaced by (b′) w^{(1)}(a_{1}) > ⋯ > w^{(q)}(a_{q}) and w^{(q)}(a_{q}) < ⋯ < w^{(m)}(a_{m}).

Proof: Consider the formula involving Schur polynomials in variables x_{1}, …, x_{k}:

s\underline{p} · s_{1^{(q−1)}} = s_{(p+1,1^{(q−2)})} + s_{(p,1^{(q−1)})}.

Expressing these as Schubert polynomials (applying π^{∗}), we have:

𝔖_{r[k,p]} · 𝔖_{c[k,q−1]} = 𝔖_{h[k; p+1,q−1]} + 𝔖_{h[k; p,q]}.

To establish the Theorem, fix m and use downward induction on either p or q, using this formula and Theorem ??.

Appendix: Schubert Polynomials

In [?, ?] cohomology classes of Schubert subvarieties of the flag manifold were obtained from the class of a point using repeated correspondences in ℙ^{1}-bundles. Subsequently, Lascoux and Schützenberger [?] showed it was possible to find explicit polynomial representatives. This has given rise to the present algebraic and combinatorial theory of Schubert polynomials. We outline their construction of Schubert polynomials; for a more complete account see [?].

For each integer n > 1, let R_{n} = ℤ[x_{1}, …, x_{n}]. The polynomial ring R_{n} is graded by the total degree of a monomial. The symmetric group S_{n} acts on R_{n} by permuting the variables. Let f ∈ R_{n} and s_{i} = t_{i i+1} be an adjacent transposition. The polynomial f − s_{i}f is anti-symmetric in x_{i} and x_{i+1}, and so is divisible by x_{i} − x_{i+1}. Thus we define the linear divided difference operator

∂_{i} = (x_{i} − x_{i+1})^{−1}(1 − s_{i}).

This operator has degree −1. If f is symmetric in x_{i} and x_{i+1}, then ∂_{i}f is zero. Otherwise, ∂_{i}f is symmetric in x_{i} and x_{i+1}. The divided differences satisfy

∂_{i} ∘ ∂_{i} = 0
∂_{i} ∘ ∂_{j} = ∂_{j} ∘ ∂_{i}  if |i − j| ≥ 2
∂_{i} ∘ ∂_{i+1} ∘ ∂_{i} = ∂_{i+1} ∘ ∂_{i} ∘ ∂_{i+1}

Thus, if a = (a_{1}, …, a_{p}) is a reduced word for a permutation w, then the composition of divided differences ∂_{a} = ∂_{a_{1}} ∘ ⋯ ∘ ∂_{a_{p}} depends only upon w and not upon a. This defines operators ∂_{w} for each w ∈ S_{n}.

Let w_{0} be the longest permutation in S_{n}, that is w_{0}(j) = n+1−j. For w ∈ S_{n}, define the Schubert polynomial 𝔖_{w} by

𝔖_{w} = ∂_{w^{−1}w_{0}} (x_{1}^{n−1}x_{2}^{n−2} ⋯ x_{n−1}) .

Recently other, more combinatorial descriptions have been discovered for the Schubert polynomials [?, ?, ?]. In each of these a class of combinatorial objects is defined with a rule for associating a monomial to each object. Given a permutation w, a finite set of these combinatorial objects is constructed. Then it is proven that the Schubert polynomial 𝔖_{w} is the sum of all monomials obtained from that set (counting multiplicities). This is in the same spirit as the tableaux theoretic description of symmetric polynomials given by Lascoux and Schützenberger [?].

The polynomial 𝔖_{w} is homogeneous of degree ℓ(w), and is independent of which n was chosen, thus 𝔖_{w} is well defined for each w ∈ S_{∞}. Here S_{∞} = ⋃_{n=1}^{∞} S_{n}, the group of permutations of the positive integers which fix all but finitely many integers.

If w has a unique descent (j such that w(j) > w(j+1)) at k, then w is said to be Grassmannian with descent k and 𝔖_{w} is the Schur polynomial s_{λ(w)}(x_{1}, …, x_{k}). Here λ(w) is the partition (λ_{1} ≥ ⋯ ≥ λ_{k}) with k parts where λ_{k−j+1} = w(j)−j. A permutation w ∈ S_{n} is represented as the sequence (w(1), w(2), …) of its values. A partition λ with at most k parts determines a Grassmannian permutation w(λ) with descent at k:

w(λ) = (1+λ_{k}, 2+λ_{k−1}, …, k+λ_{1}, …),

the remaining entries written in increasing order. If we define

r[k, m] = (1, 2, …, k−1, k+m, k, k+1, …, k+m−1, k+m+1, …)
c[k, m] = (1, 2, …, k−m, k−m+2, …, k+1, k−m+1, k+2, …),

then r[k, m] and c[k, m] are Grassmannian permutations with descent at k, and we have λ(r[k, m]) = (m, 0, …, 0) and λ(c[k, m]) = (1^{m}), a single column of length m.

The set {𝔖_{w} | w ∈ S_{n}} is an integral basis for the ℤ-module

H_{n} = ℤ⟨x_{1}^{i_{1}} ⋯ x_{n−1}^{i_{n−1}} | i_{j} ≤ n−j⟩ ⊂ ℤ[x_{1}, …, x_{n}],

which is a complete transversal to the ideal S generated by the non-constant symmetric functions. As ℤ-modules, H_{n} ≃ ℤ[x_{1}, …, x_{n}]/S. Allowing n to increase shows {𝔖_{w} | w ∈ S_{∞}} is an integral basis for R_{∞} = ℤ[x_{1}, x_{2}, …]. Given any formula involving finitely many Schubert polynomials (as in the statement of Theorem ??), there is a positive integer n such that H_{n} contains all the Schubert polynomials appearing in that formula. Thus it is no loss of generality in proving formulas in the rings ℤ[x_{1}, …, x_{n}]/S. This is the approach we take in §§1–3.

References

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

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

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

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

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

[6] C. Chevalley, Sur les décompositions cellulaires des espaces g/b. unpublished manuscript, 1958.

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

[8] C. Ehresmann, Sur la topologie de certains espaces homogènes, Ann. Math., 35 (1934), pp. 396– 443.

[9] S. Fomin and A. Kirillov, Yang-Baxter equation, symmetric functions and Schubert polynomials, Adv. Math., 103 (1994), pp. 196–207.

[10] W. Fulton, Intersection Theory, Ergebnisse der Math. 2, Springer-Verlag, 1984.

[11] H. Hiller, Combinatorics and intersections of Schubert varieties, Comment. Math. Helvetica, 57 (1982), pp. 41–59.

[12] A. Lascoux and M.-P. Schützenberger, Le monoïd plaxique, in Non-Commutative Structures in Algebra and Geometric Combinatorics, Quaderni de “la ricerca scientifica,” 109 Roma, CNR, 1981, pp. 129–156.

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

[14] , Symmetry and flag manifolds, in Invariant Theory, (Montecatini, 1982), Springer–Verlag, 1983, pp. 118–144. Lecture Notes in Mathematics 996.

[15] , Schubert polynomials and the Littlewood-Richardson rule, Lett. Math. Phys., 10 (1985), pp. 111–124.

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

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

[18] F. Sottile, Pieri’s rule for flag manifolds and Schubert polynomials, Annales d’Institut Fourier, Grenoble, 46 no. 1 (1996), pp. 1–22.

Department of Mathematics, University of Toronto, 100 St. George Street, Toronto, Ontario M5S 3G3, Canada, (416) 978-4031

  E-mail address: sottile@math.toronto.edu