Séminaire Lotharingien de Combinatoire 54A (2006), Article B54Ai

A LITTLE BIJECTION FOR AFFINE STANLEY SYMMETRIC FUNCTIONS

THOMAS LAM AND MARK SHIMOZONO

Abstract. Little [Adv. Math. 174 (2003), 236–253] developed a combinatorial algorithm to study the Schur-positivity of Stanley symmetric functions and the Lascoux–Schützenberger tree. We generalize this algorithm to affine Stanley symmetric functions, which were introduced recently in [T. Lam: “Affine Stanley symmetric functions,” Amer. J. Math., to appear].

1. Introduction

A new family of symmetric functions, called affine Stanley symmetric functions were recently introduced in [8]. These symmetric functions F̃_{w}, indexed by affine permutations w ∈ S̃_{n}, are an affine analogue of the Stanley symmetric functions F_{w} which Stanley [17] introduced to enumerate the reduced decompositions of a permutation w ∈ S_{n}. Stanley symmetric functions were later shown to be stable limits of the Schubert polynomials 𝔖_{w} [13, 2]. In the case that w is a Grassmannian permutation the Stanley symmetric function is equal to a Schur function. Shimozono conjectured and Lam [9] recently showed that the symmetric functions F̃_{w} also have a geometric interpretation. When w is affine Grassmannian then F̃_{w} represents a Schubert class in the cohomology H^{∗}(G/P) of the affine Grassmannian and F̃_{w} is called an affine Schur function. Affine Schur functions were introduced by Lapointe and Morse in [11], where they were called dual k-Schur functions.

A key property of the Stanley symmetric function F_{w} is that its expansion in terms of the Schur functions s_{λ} involves non-negative coefficients. This was proved by Edelman and Greene [3] using an insertion algorithm and separately by Lascoux and Schützenberger [13] via transition formulae for Schubert polynomials. These transition formulae lead to a combinatorial object known as the Lascoux–Schützenberger tree which allows one to write a Stanley symmetric function F_{w} in terms of other Stanley symmetric functions F_{v} labeled by permutations “closer to Grassmannian”.

M.S. was supported in part by NSF DMS-0401012.

T.L. was supported in part by NSF DMS-0502858 and NSF DMS-0600677.

Answering a question of Garsia, Little [14] recently gave a combinatorial proof of the identity

∑_{\begin{matrix}u=v·t_{r,s} \\ l(u)=l(v)+1 \end{matrix}} F_{u}(X) = ∑_{\begin{matrix}w=v·t_{s′,r} \\ l(w)=l(v)+1 \end{matrix}} F_{w}(X),

from which the Lascoux–Schützenberger tree can be deduced. Here v ∈ S_{n} is any permutation, t_{r,s} denotes a transposition, and the summations are over s > r and s′ < r respectively.

The aim of this article is to generalize Little’s bijection and to prove an affine analogue of the above identity for the affine Stanley symmetric functions F̃_{w}. Our techniques are mainly combinatorial and the resulting bijection appears to be interesting in itself – for example, it seems to be closely related to the affine Chevalley formula. Unfortunately, we have been unable to use our affine Little bijection to prove that an arbitrary affine Stanley symmetric function expands positively in terms of affine Schur functions. This positivity follows from the results of Lam [9] combined with unpublished work of Peterson [16].

2. Affine Stanley symmetric functions

2.1. Affine symmetric group. Let S̃_{n} be the affine symmetric group. It is a Coxeter group with simple reflections {s_{i} | i ∈ ℤ/nℤ} and relations s_{i}^{2} = 1 for all i, (s_{i}s_{i+1})^{3} = 1 for all i, and (s_{i}s_{j})^{2} = 1 for i ≠ j ± 1 not adjacent mod n.

One may realize S̃_{n} as the set of all bijections w : ℤ → ℤ such that w(i + n) = w(i)+n for all i and ∑_{i=1}^{n} w(i) = ∑_{i=1}^{n} i. In this realization, to specify an element it suffices to give the “window” [w(1), w(2), …, w(n)].

Given integers r and s such that s ≢ r mod n, there is a unique element t_{r,s} ∈ S̃_{n} such that, in the function notation, t_{r,s}(r) = s and t_{r,s}(s) = r, and t_{r,s}(i) = i for all i such that i ≢ r mod n and i ≢ s mod n. We note that t_{r,s} = t_{r′,s′} if and only if there is an integer k such that {r, s} = {r′ + kn, s′ + kn} as sets. In this notation s_{i} = t_{i,i+1} for all i.

For a_{i} ∈ ℤ/nℤ we call a = a_{1} ⋯ a_{l} a reduced word for w ∈ S̃_{n} and write a ∈ R(w) if w = s_{a_{1}} ⋯ s_{a_{l}} such that l is minimum. We call l = ℓ(w) the length of w. Let v ⋖ w denote the covering relation of the strong Bruhat order ≤ on S̃_{n}. By definition v ⋖ w if and only if there is a reflection t_{r,s} ∈ S̃_{n} such that w = vt_{r,s} and ℓ(w) = ℓ(v) + 1.

Say that w ∈ S̃_{n} is a right r-cover of v ∈ S̃_{n} if v ⋖ w with w = vt_{r,s} for r < s. Say that w is a left r-cover of v if v ⋖ w with w = vt_{s,r} where s < r. Let Ψ_{r}^{+}(v) denote the set of r-right covers of v and Ψ_{r}^{−}(v) denote the set of r-left covers of v.

Now let S_{n} ⊂ S̃_{n} denote the symmetric group generated by s_{1}, s_{2}, …, s_{n−1}. This is a parabolic subgroup of S̃_{n}. The minimal length coset representatives of S̃_{n}/S_{n} are called Grassmannian and the set of such elements is denoted S̃_{n}^{−}.

2.2. Cyclically decreasing permutations. Let a = a_{1}a_{2} ⋯ a_{l} be a reduced word. Then a is called cyclically decreasing if

(1) The multiset A = {a_{1}, a_{2}, …, a_{l}} is a set.

(2) If i, i + 1 ∈ A then i + 1 occurs before i in a, where indices are considered

modulo n. In particular, if n − 1, 0 ∈ A then 0 appears before n − 1 in a. A permutation w ∈ S̃_{n} is called cyclically decreasing if there is a reduced word for w which is cyclically decreasing. Say that a proper subset I ⊂ ℤ/nℤ is a cyclic interval if it has the form I = {i, i + 1, i + 2, …, i + j} with indices taken mod n. Let (i + j) ⋯ (i + 1)i be the word of I. The cyclically decreasing elements of S̃_{n} are characterized as follows. Lemma 1. (1) Let A ⊂ ℤ/nℤ be a proper subset. Then a word with underly-

ing set A is cyclically decreasing if and only if it is a shuffle of the words of the maximal cyclic subintervals of A.

(2) Every cyclically decreasing word with underlying set A is a reduced word for the same element w(A) ∈ S̃_{n}.

(3) Every reduced word for w(A) is cyclically decreasing with underlying set A.

Proof. (1) holds by definition. Since reflections in different maximal cyclic subintervals commute, it follows that every cyclically decreasing word with underlying set A, is equivalent to a single canonical word, namely, the concatenation of the words of the maximal cyclic subintervals of A, with these words occurring in decreasing order by first element. This given word is a reduced word for some element w(A) ∈ S̃_{n}, so all the cyclically decreasing words with underlying set A are as well. This proves (2). Since there are no repeated reflections, the braid relations do not apply, and the only equivalences among reduced words for w(A) are commutations between reflections in different maximal cyclic subintervals of A. Since the set of reduced words is connected by the Coxeter relations it follows that every reduced word for w(A) is a shuffle of the prescribed sort. This proves (3). □

Lemma 1 has the following immediate consequence. Corollary 2. The strong Bruhat order on the set of cyclically decreasing elements in S̃_{n} is isomorphic to the boolean lattice on proper subsets of ℤ/nℤ.

Now let w ∈ S̃_{n} of length l = ℓ(w) and suppose α = (α_{1}, α_{2}, …, α_{r}) is a composition of l. An α-decomposition of w is an ordered r-tuple of cyclically decreasing affine permutations (w^{1}, w^{2}, …, w^{r}) ∈ S̃_{n}^{r} satisfying ℓ(w^{i}) = α_{i} and w = w^{1}w^{2} ⋯ w^{r}. The following definition is [8, Alternative Definition 2].

Definition 3. The affine Stanley symmetric function F̃_{w}(X) is given by

F̃_{w}(X) = ∑_{α}(number of α-decompositions of w) · x^{α}

where the sum is over all compositions α of ℓ(w).

It is shown in [8] that F̃_{w}(X) is always a symmetric function, though this fact will not be used in the current work. When w ∈ S_{n} ⊂ S̃_{n} is a normal permutation then, the function F̃_{w} is the usual Stanley symmetric function [17]. When w ∈ S_{n} ∩ S̃_{n}^{−} is a usual Grassmannian permutation, the function F̃_{w} is equal to some Schur function s_{λ}.

When w ∈ S̃_{n}^{−} is an affine Grassmannian permutation, then we say that F̃_{w}(X) is an affine Schur function or dual k-Schur function. There is a bijection θ : w ↔ λ(w) between Grassmannian permutations w ∈ S̃_{n}^{−} and partitions λ(w) with no part greater than or equal to n [1]. The bijection θ sends a permutation w with length l to a partition λ with l boxes. We may thus label the affine Schur functions by partitions F̃_{λ(w)} := F̃_{w} so that deg(F̃_{λ}) = |λ|. See [8] for details.

3. Affine Chevalley formula and affine Garsia–Little formula

3.1. Affine Chevalley formula. Let G/B denote the affine flag variety of type A_{n−1}; see [7, 6]. The Bruhat decomposition of G induces a decomposition of G/B into Schubert cells

G/B = ∪_{w∈S̃_{n}}Ω_{w}.

Let 𝔖̃_{w} ∈ H^{∗}(G/B) denote the cohomology class dual to Ω_{w}.

The structure constants for the Schubert basis are denoted by

(1)  𝔖̃_{u}𝔖̃_{v} = ∑_{w∈S̃_{n}} c_{u,v}^{w}𝔖̃_{w}

for u, v ∈ S̃_{n}. The following is a translation of the general Chevalley rule (applicable to symmetrizable Kac-Moody groups) of Kostant and Kumar [6] for the special case of S̃_{n}.

Proposition 4. [6] For v, w ∈ S̃_{n} and any r, c_{s_{r},v}^{w} is zero unless w ⋗ v. In this case, writing w = vt_{a,b} with a < b, c_{s_{r},v}^{w} is the number of times that r occurs modulo n in the interval [a, b − 1].

Conjecturally (1) holds with 𝔖̃_{w} replaced by F̃_{w}(X) everywhere. Note that the functions F̃_{w}(X) are not linearly independent. In particular we have the following conjecture.

Conjecture 5.

(2)  F̃_{s_{r}} F̃_{v} = ∑_{w⋗v}c_{s_{r},v}^{w}F̃_{w}.

In other developments, this conjecture has been proved using an affine Schensted algorithm in a joint work with Lapointe and Morse [10]. It also follows from unpublished geometric work of Peterson [16] and the results in [9].

Example 6. Let n = 4. We use the window notation. Let v = [2, 3, 0, 5] and r = 2. The elements w such that c_{s_{r},v}^{w} > 0, are w_{1} = [2, 5, 0, 3] and w_{2} = [2, 4, −1, 5]. Now w_{1} = vt_{2,4} and 2 occurs once mod 4 in {2, 3}, and w_{2} = vt_{2,7} and 2 occurs twice mod 4 in {2, 3, 4, 5, 6}. Therefore F̃_{s_{2}} F̃_{v} = F̃_{w_{1}} + 2F̃_{w_{2}}.

3.2. Affine Garsia–Little Formula. The following, our main result, is an affine analogue of an identity for Stanley functions observed by Garsia [4], for which David Little [14] found a combinatorial proof.

Theorem 7. For any r ∈ ℤ and v ∈ S̃_{n},

(3)  ∑_{u∈Ψ_{r}^{−}(v)} F̃_{u} = ∑_{w∈Ψ_{r}^{+}(v)} F̃_{w}.

Example 8. Let n = 4 and v = [−1, 1, 4, 6] = s_{3}s_{1}s_{0}. For r = 1 we have Ψ_{1}^{+}(v) = {[1, −1, 4, 6]} and Ψ_{1}^{−}(v) = {[−3, 3, 4, 6], [−2, 1, 4, 7]} and all the Chevalley coefficients are 1:

F̃_{[1,−1,4,6]} = F̃_{[−3,3,4,6]} + F̃_{[−2,1,4,7]}.

With the same n and v but r = 2, we have Ψ_{2}^{+}(v) = {[−1, 4, 1, 6], [−3, 3, 4, 6]} and Ψ_{2}^{−}(v) = {[1, −1, 4, 6], [−1, 0, 5, 6]} and all the Chevalley coefficients are 1:

F̃_{[−1,4,1,6]} + F̃_{[−3,3,4,6]} = F̃_{[1,−1,4,6]} + F̃_{[−1,0,5,6]}.

Using these equations together one may find the equation

F̃_{[−1,4,1,6]} = F̃_{[−2,1,4,7]} + F̃_{[−1,0,5,6]}

The latter two are the affine Schur functions indexed by the partitions (2, 1, 1) and (2, 2) respectively (see [8]).

Remark 9. Theorem 7 is a consequence of Conjecture 5. Note that F̃_{s_{r}} is the Schur function s_{1} for all r. Subtracting (2) for F̃_{s_{r}} F̃_{v} and F̃_{s_{r+1}} F̃_{v} one obtains (3).

3.3. Garsia–Little Formula and the Lascoux–Schützenberger Tree. Theorem 7 holds, with a slight modification in a special case (explained below), with all the affine objects (affine permutations, affine transpositions, affine Stanley symmetric functions) replaced by their usual S_{n}-counterparts. The resulting Garsia–Little formula implies that a Stanley symmetric function F_{w} is Schurpositive, as follows.

Let σ = σ_{1}σ_{2} ⋯ σ_{n} ∈ S_{n} be a permutation. We set

r = max(i | σ_{i} > σ_{i+1}),
s = max(i > r | σ_{i} < σ_{r}),
I = {i < r | σ_{i} < σ_{s} and for all j ∈ (i, r) we have σ_{j} ∉ (σ_{i}, σ_{s})}.

Now let π = σ · t_{r,s}. One can check that we have Ψ_{r}^{+}(π) = {σ} and Ψ_{r}^{−}(π) = {π · t_{i,r} | i ∈ I}. If I ≠ ∅ then Theorem 7 reads

F_{σ} = ∑_{i∈I} F_{π·t_{i,r}}.

The permutations π · t_{i,r} are the children of σ in the Lascoux–Schützenberger tree. When I = ∅, the corresponding equation fails to hold, but we declare σ to have a single child 1 ⊗ σ = (1, σ_{1} + 1, σ_{2} + 1, …, σ_{n} + 1) ∈ S_{n+1} and we note that F_{σ} = F_{1⊗σ}. It can be shown that the process of (repeatedly) taking children eventually results in permutations which are Grassmannian, which are the leaves of the Lascoux–Schützenberger tree. Since the Stanley symmetric function indexed by σ is equal to the sum of those indexed by the children of σ we conclude that it is also the sum of those indexed by the leaves which are descendents of σ. A Stanley symmetric function indexed by a Grassmannian permutation is a Schur function, so in particular every Stanley symmetric function is Schur positive.

Unfortunately, a similar attempt to produce an “affine Lascoux–Schützenberger tree” fails because for an affine permutation w ∈ S̃_{n} there may be no permutation v and index r so that Theorem 7 involves only F̃_{w} on one side. However, by solving simultaneous equations obtained from Theorem 7, we have so far always been able to express an affine Stanley symmetric function in terms of affine Schur functions, as demonstrated in Example 8. It is our hope that the methods of this paper will eventually lead to a combinatorial interpretation of the coefficients a_{w}^{λ} in the expansion F̃_{w} = ∑_{λ} a_{w}^{λ}F̃_{λ} of affine Stanley symmetric functions in terms of affine Schur functions. These coefficients contain, for example, the 3-point, genus zero, Gromov–Witten invariants of the Grassmannian, which are important numbers in combinatorics, geometry, and representation theory; see [11, 8]. The numbers a_{w}^{λ} also include as a special case the structure constants for the multiplication of the homology of the affine Grassmannian in the Schubert basis; see [9, 16].

4. Affine Little Bijection

A v-marked word is a pair (a, i) where a = a_{1} ⋯ a_{l} is a word with letters in {0, 1, …, n − 1} and i ∈ [1, l] is the index of a distinguished letter in a such that a_{1} ⋯ â_{i} ⋯ a_{l} ∈ R(v) where the hatted letter is omitted.

We now define the affine Little graph. It is a directed graph whose vertices are the v-marked words. Given a v-marked word (a, i) with a = a_{1} ⋯ a_{l}, there is a unique directed edge (a, i) → (a′, j) leaving (a, i), where a′ is the word obtained from a by replacing the letter a_{i} by a_{i}−1 (mod n) and the index j is equal to i if a′ is reduced and is otherwise the unique index j ≠ i such that a_{1} ⋯ â_{j} ⋯ a_{l} ∈ R(v), whose existence and uniqueness follows by Lemma 21 (see Section 6).

\begin{matrix}(a, i) & p(a, i) & q(a, i) \\ 3410\underline{2}321042 & 2 & 5 \\ 3410132104\underline{2} & 2 & 3 \\ 34\underline{1}01321041 & 2 & 1 \\ 340\underline{0}1321041 & 2 & 3 \\ 340\underline{4}1321041 & −6 & 2 \end{matrix}

Figure 1. Computation of ϕ^{v}.

It is not hard to see that each vertex (a, i) has a unique incoming edge (b, k) → (a, i): if a is reduced then k = i, and otherwise, k ≠ i is the unique index such that a_{1} ⋯ â_{k} ⋯ a_{l} ∈ R(v), and in either case, b is obtained from a by replacing a_{k} by a_{k} + 1.

Since there are finitely many v-marked words, the connected components of the affine Little graph are finite directed cycles. It is clear from the definition that none of these cycles is a loop, that is, it is never the case that (a, i) → (a, i).

Say that the v-marked word (a, i) is reduced if a is a reduced word for some w ∈ S̃_{n}. Given a reduced v-marked word (a, i), write ϕ^{v}(a, i) = (b, j) where (b, j) is the first reduced v-marked word following (a, i) on the cycle of the affine Little graph containing (a, i). The map ϕ^{v} defines a bijection from the set of reduced v-marked words to itself. We call an application of ϕ^{v} the affine Little algorithm.

Let w ⋗ v, w = vt_{r,s} and a = a_{1} ⋯ a_{l} ∈ R(w). By Proposition 16 there exists a unique i ∈ [1, l] so that a_{1} ⋯ â_{i} ⋯ a_{l} ∈ R(v) and (a, i) is v-marked. Therefore the set of reduced v-marked words is in bijection with ⋃_{w⋗v} R(w), and ϕ^{v} can be regarded as a bijection from this set to itself.

Example 10. Let n = 5, 3410321042 ∈ R(v), r = 2, and b = 3410\underline{2}321042 ∈ Ψ_{r}^{+}(v) where the distinguished reflection (the j-th) is underlined. The computation of ϕ^{v}(b, j) is shown in Figure 1. The indices p(a, i) and q(a, i) are those that appear in the proof of Theorem 11. ϕ^{v}(b, j) is given by the last row. In Figure 1 the edges of the affine Little graph for v go from each v-marked word to the one in the next row. We give some additional data used in the proof of Theorem 11 with r = 2. We note that for the last row, literally p(a, i) = −1 and q(a, i) = 7. However −6 < 2 and t_{−1,7} = t_{−6,2}. In other words, one should identify the pairs (p, q) and (p′, q′) if there is a k such that p′ = kn + p and q′ = kn + q.

Theorem 11. The map ϕ^{v} restricts to a bijection

ϕ_{r}^{v} : R(Ψ_{r}^{+}(v)) ⟶ R(Ψ_{r}^{−}(v)).

Proof. Due to the symmetry of left and right r-covers and the bijectivity of ϕ^{v}, it suffices to show that ϕ^{v} maps Ψ_{r}^{+}(v) into Ψ_{r}^{−}(v).

Given a v-marked word (a, i) with a = a_{1} ⋯ a_{l}, let x and y be the elements of S̃_{n} with reduced words a_{1} ⋯ a_{i−1} and a_{i+1} ⋯ a_{l} respectively. Let w = s_{a_{1}} ⋯ s_{a_{l}} and t = a_{i}. Then w = xs_{t}y = xy(y^{−1}s_{t}y) = vt_{p,q} where y(p) = t and y(q) = t + 1. Note also that if s_{t}y > y (which occurs if a is reduced), then p < q, and if s_{t}y < y then p > q. We shall use the notation p = p(a, i) and q = q(a, i) to emphasize the dependence on (a, i).

Let b ∈ R(Ψ_{r}^{+}(v)) and (b, j) the corresponding v-marked word. Let ϕ^{v}(b, j) = (c, k) where c ∈ R(u). It is enough to show that q(c, k) = r, for if so, then since c is reduced, p(c, k) < q(c, k) = r and u ∈ Ψ_{r}^{−}(v) as desired. To this end we show that p(a, i) = r for all vertices (a, i) on the path in the affine Little graph from (b, j) to (c, k) except (c, k).

Let (a, i) be such a vertex and let p = p(a, i) and q = q(a, i).

For the base case (a, i) = (b, j). Since b ∈ R(w) we have p < q and since w ∈ Ψ_{r}^{+}(v), p = r as required.

For the induction step suppose (a, i) satisfies p = r. Let (a, i) → (a′, i′) in the affine Little graph. Write x′, y′, t′, p′, q′ for the quantities associated with (a′, i′).

By definition a′ is obtained from a by replacing a_{i} = t by a_{i} − 1 = t − 1. Let w′ = s_{a′_{1}} … s_{a′_{l}}. Then w′ = xs_{t−1}y = xy(y^{−1}s_{t−1}y) = vt_{p′,q′}. In particular, since zs_{m}z^{−1} = zt_{m,m+1}z^{−1} = t_{z(m),z(m+1)} for all z ∈ S̃_{n} and m, we have {t − 1, t} = {y(p′), y(q′)} as sets. Let s be such that y(s) = t − 1. Since t = y(p) = y(r) we have {r, s} = {p′, q′}.

Suppose a′ is not reduced. By Lemma 21, i′ ≠ i. Suppose i′ < i. Then s_{t′}y′ < y′ and s_{t−1}y > y. It follows that q′ < p′ and s < r, so that p′ = r as desired. Suppose i′ > i. Then s_{t′}y′ > y′ and s_{t−1}y < y, so that p′ < q′ and r < s and again p′ = r as desired.

Otherwise let a′ be reduced. Then (a′, i′) = (c, k), i = i′, and y′ = y. By the reducedness of a′, s_{t−1}y > y and s < r. Again by reducedness, p′ < q′. Therefore q′ = r as desired. □

5. Generalized affine Little algorithm

We now generalize the affine Little algorithm of the previous section from reduced words to α-decompositions.

Lemma 12. Let v ⋖w both be cyclically decreasing. Then there exists a cyclically decreasing reduced v-marked word a for w which ϕ^{v} maps to a cyclically decreasing reduced v-marked word, for the element w′ say. Furthermore the element w′ is independent of the choice of a.

Proof. Let w = w(A) and v = w(A − {i}). Let j be maximal such that {i, i − 1, …, i − j} ⊂ A, with indices taken mod n. Let A′ be the proper subset of [0, n − 1] obtained from A by replacing i with i − j − 1. Let w′ = w(A′).

Now take any reduced word a of w and apply ϕ^{v} to the word w with the reflection i marked. The application of ϕ^{v} to a replaces the subword i(i−1) ⋯ (i− j) by (i − 1) ⋯ (i − j − 1), resulting in a′, say, with i − j − 1 marked. The only way that a′ is not cyclically decreasing is if i − j − 2 ∈ A and it appears to the left of i − j in a. In this case i − j − 2 and i − j are in different maximal cyclically decreasing subintervals of A. By Lemma 1 there is an a ∈ R(w) with i − j − 2 to the right of i − j. With such a choice of a, by Lemma 1 a′ is a reduced word for w(A′), which depends only on A′, that is, only on A and i. □

In particular, for v ∈ S̃_{n} cyclically decreasing, ϕ^{v} induces a permutation of the set of cyclically decreasing covers of v. Denote this map by ϕ^{v}.

Let v ∈ S̃_{n} and w ∈ Ψ_{r}^{+}(v). Let α be fixed. We will describe an algorithm which takes as input an α-decomposition w = w^{1}w^{2} ⋯ w^{r} of w ∈ Ψ_{r}^{+}(v), and outputs an α-decomposition x = x^{1} ⋯ x^{r} of an element x ∈ Ψ_{r}^{−}(v).

Algorithm 13. Initialize y := w and y^{i} := w^{i}. By Proposition 16 and Corollary 2 we may write v = y^{1}y^{2} ⋯ (y^{i})′ ⋯ y^{r} where (y^{i})′ is obtained from y^{i} by removing a single simple reflection. This simple reflection is the same for any reduced word for y^{i}.

(1) Treating y^{i} as a (y^{i})′-marked word, apply ϕ^{(y^{i})′} to y^{i}.

(2) If y^{1}y^{2} ⋯ ϕ^{(y^{i})′}(y^{i}) ⋯ y^{r} is an α-decomposition of some permutation (that is, it is “reduced”), we terminate with this as the output. Otherwise by Lemma 21 there is a unique index j ≠ i so that

v = y^{1}y^{2} ⋯ (y^{j})′ ⋯ ϕ^{(y^{i})′}(y^{i}) ⋯ y^{r}

where (y^{j})′ is obtained from y^{j} by removing a single simple reflection. Replace the α-decomposition y = y^{1}y^{2} ⋯ y^{i} ⋯ y^{r} by y^{1}y^{2} ⋯ ϕ^{(y^{i})′}(y^{i}) ⋯ y^{r} and set i := j.

(3) Return to 1.

The fact that the algorithm is well-defined is clear from Lemma 12.

Theorem 14. Algorithm 13 is a bijection between α-decompositions of permutations in Ψ_{r}^{+}(v) and α-decompositions of permutations in Ψ_{r}^{−}(v).

Proof. The fact that the output is an α-decomposition of a permutation in Ψ_{r}^{−}(v) follows from the same argument as in Theorem 11, and the fact that ϕ_{r} is a bijection follows from the reversibility. □

Proof of Theorem 7. Since the coefficient [x^{α}]F̃_{w} of x^{α} in the affine Stanley symmetric function F̃_{w} is given by the number of distinct α-decompositions of w, Theorem 14 proves Theorem 7. □

Remark 15. Given an α-decomposition of w, it is not clear whether there is an initial choice of reduced word a for w so that the affine Little algorithm applied to a naturally gives the same α-decomposition as the generalized affine Little algorithm.

6. A Coxeter-theoretic result

Let (W, S) be a Coxeter system, that is, W is a group generated by a set of simple reflections S subject only to relations of the form s^{2} = 1 for all s ∈ S and for s ≠ s′ ∈ S, (ss′)^{m(s,s′)} = 1 for m(s, s′) ≥ 2. W is called a Coxeter group. A reflection is by definition a conjugate in W of an element of S.

In this section, to avoid double subscripting, we shall write s_{i} for an arbitrary simple reflection. A reduced word for w ∈ W is a factorization w = s_{1} ⋯ s_{r} of w with s_{i} ∈ S such that r is minimum. The number r is the length of w, denoted ℓ(w).

Let v ⋖ w denote the covering relation of the strong Bruhat order ≤ on W. By definition v ⋖ w if and only if there is a reflection t ∈ W such that w = vt and ℓ(w) = ℓ(v) + 1.

The goal of this section is to establish Lemma 21, which is used crucially in the affine Little bijection.

Proposition 16. (Strong Exchange Condition) [5, Theorem 5.8] Let w = s_{1}s_{2} ⋯ s_{r} with s_{i} ∈ S not necessarily reduced. Suppose t is a reflection such that ℓ(wt) < ℓ(w). Then there is an index i such that wt = s_{1} ⋯ ŝ_{i} ⋯ s_{r}. Moreover if the expression for w is reduced then the index i is unique.

Corollary 17. [5, Cor. 5.8] Suppose w = s_{1} ⋯ s_{r} with s_{i} ∈ S and r > ℓ(w). Then there are indices i < j for which w = s_{1} ⋯ ŝ_{i} ⋯ ŝ_{j} ⋯ s_{r}.

Lemma 18. [5, Lemma 5.11] Let w′ ⋖ w. Suppose there is an s ∈ S such that w′ < w′s and w′s ≠ w. Then both w < ws and w′s < ws.

Lemma 19. Let w = s_{1} ⋯ s_{r} with s_{i} ∈ S and 1 ≤ i ≤ r. Then there are unique reflections t, t′ such that wt = t′w = s_{1} ⋯ ŝ_{i} ⋯ s_{r}.

Proof. Let x = s_{1} ⋯ s_{i−1} and y = s_{i+1} ⋯ s_{r}. Then s_{1} ⋯ ŝ_{i} ⋯ s_{r} = xy and w = xs_{i}y = xy(y^{−1}s_{i}y). Letting t = y^{−1}s_{i}y and t′ = xs_{i}x^{−1} we have wt = xy and t′w = xs_{i}x^{−1}xs_{i}y = xy as desired. □

Lemma 20. Let x, y ∈ W. Then ℓ(xy) < ℓ(x) + ℓ(y) if and only if there is a reflection t such that xt < x and ty < y.

Proof. For the converse, let t is a reflection such that xt < x and ty < y. Then ℓ(xy) = ℓ(xtty) ≤ ℓ(xt) + ℓ(ty) ≤ ℓ(x) − 1 + ℓ(y) − 1 as desired.

Suppose x, y ∈ W are such that ℓ(xy) < ℓ(x) + ℓ(y). Let x = s_{1} ⋯ s_{l} and y = s′_{1} ⋯ s′_{m} be reduced. Then xy = s_{1} ⋯ s_{l}s′_{1} ⋯ s′_{m} is not reduced. By Corollary 17, xy has a factorization obtained by removing two of the simple reflections. Suppose both of the reflections are removed from the reduced word for x, that is, xy = s_{1} ⋯ ŝ_{i} ⋯ ŝ_{j} ⋯ s_{l}s′_{1} ⋯ s′_{m} for some 1 ≤ i < j ≤ l. Multiplying both sides by y^{−1} = s′_{m} ⋯ s′_{1} we have x = s_{1} ⋯ ŝ_{i} ⋯ ŝ_{j} ⋯ s_{l} which contradicts the assumption that x = s_{1} ⋯ s_{l} was reduced. Similarly both reflections cannot be removed from the reduced word for y. Therefore there are indices 1 ≤ i ≤ l and 1 ≤ j ≤ m such that xy = s_{1} ⋯ ŝ_{i} ⋯ s_{l}s′_{1} ⋯ ŝ′_{j} ⋯ s′_{m}. By Lemma 19 there are reflections t, t′ ∈ W such that xt = s_{1} ⋯ ŝ_{i} ⋯ s_{l} and t′y = s′_{1} ⋯ ŝ′_{j} ⋯ s′_{m}. Therefore xtt′y = s_{1} ⋯ ŝ_{i} ⋯ s_{l}s′_{1} ⋯ ŝ′_{j} ⋯ s′_{m} = xy. It follows that tt′ = 1 and t = t′ since t, t′ are reflections. Since xt admits a shorter factorization in simple reflections that x does, xt < x. Similarly ty = t′y < y as desired. □

Lemma 21. Suppose s_{i} ∈ S for 1 ≤ i ≤ r is such that v = s_{1} ⋯ ŝ_{i} ⋯ s_{r} is reduced, where ŝ_{i} means that the factor s_{i} is removed. Suppose also that w = s_{1} ⋯ s_{r} is not reduced. Then there is a unique index j ≠ i such that s_{1} ⋯ ŝ_{j} ⋯ s_{r} is reduced. Moreover v = s_{1} ⋯ ŝ_{j} ⋯ s_{r}.

Proof. Let x = s_{1} ⋯ s_{i−1} and y = s_{i+1} ⋯ s_{r}. Since v = xy = s_{1} ⋯ ŝ_{i} ⋯ s_{r} is reduced, both of the expressions for x and y are reduced and ℓ(xy) = ℓ(x) + ℓ(y). By Lemma 20 for x, y ∈ W and the reflection s_{i}, either xs_{i} > x or s_{i}y > y. Without loss of generality we assume that xs_{i} > x; one may reduce to this case by reversing the reduced words and replacing elements of W by their inverses.

By assumption xs_{i} = s_{1} ⋯ s_{i} is reduced. Let j be the minimum index such that i + 1 ≤ j ≤ l and s_{1} ⋯ s_{j} is not reduced. Then s_{1} ⋯ s_{j−1} ⋗ s_{1} ⋯ ŝ_{i} ⋯ s_{j−1} since both words are reduced. Suppose that s_{1} ⋯ ŝ_{i} ⋯ s_{j} ≠ s_{1} ⋯ s_{j−1}. By Lemma 18, s_{1} ⋯ s_{j} ⋗ s_{1} ⋯ ŝ_{i} ⋯ s_{j}. Since s_{1} ⋯ ŝ_{i} ⋯ s_{j} is reduced it follows that s_{1} ⋯ s_{j} is also, contradicting our choice of j. Therefore s_{1} ⋯ ŝ_{i} ⋯ s_{j} = s_{1} ⋯ s_{j−1}. Right multiplying by s_{j+1} ⋯ s_{r} we have v = s_{1} ⋯ ŝ_{i} ⋯ s_{r} = s_{1} ⋯ ŝ_{j} ⋯ s_{r}. But s_{1} ⋯ ŝ_{i} ⋯ s_{r} is reduced and s_{1} ⋯ ŝ_{j} ⋯ s_{l} has the same number of reflections, so it too must be reduced.

For uniqueness, suppose there is a k distinct from i and j such that v = s_{1} ⋯ ŝ_{k} ⋯ s_{r} is reduced. We now treat the three indices i, j, k interchangeably and suppose without loss of generality that i < j < k. Using the reduced words for v that omit s_{i} and s_{j}, we have ŝ_{i} ⋯ s_{j} = s_{i} ⋯ ŝ_{j}. Right multiplying by s_{j} we have ŝ_{i} ⋯ ŝ_{j} = s_{i} ⋯ s_{j}. But s_{i} ⋯ s_{j} is reduced, being a subword of the reduced word s_{1} ⋯ ŝ_{k} ⋯ s_{r}. This is a contradiction. □

References

[1] A. Björner and F. Brenti: Affine permutations of type A, The Foata Festschrift, Electronic Journal of Combinatorics 3 (1996), no. 2, Research paper 18.

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

[3] P. Edelman and C. Greene: Balanced tableaux, Adv. in Math. 63(1) (1987), 42–99.

[4] A. Garsia: The saga of reduced factorizations of elements of the symmetric group, Publications du LaCIM, Université du Québec á Montréal, Canada, Vol. 29, 2002.

[5] J. Humphreys: Reflection groups and Coxeter groups. Cambridge Studies in Advanced Mathematics, 29. Cambridge University Press, Cambridge, 1990.

[6] B. Kostant and S. Kumar: The nil Hecke ring and cohomology of G/P for a Kac– Moody group G, Adv. in Math. 62 (1986), 187–237.

[7] S. Kumar: Kac–Moody groups, their flag varieties and representation theory, Progress in Mathematics 204 Birkhuser Boston, Inc., Boston, MA, 2002.

[8] T. Lam: Affine Stanley symmetric functions, Amer. J. Math., to appear.

[9] T. Lam: Schubert polynomials for the affine Grassmannian, in preparation.

[10] T. Lam, L. Lapointe, J. Morse and M. Shimozono: Pieri rules and insertion for the affine Grassmannian, preprint, 2006; math.CO/0609110.

[11] L. Lapointe, J. Morse: Quantum cohomology and the k-Schur basis, preprint, 2005;

math.CO/0501529.

[12] A. Lascoux and M. Schützenberger: Polynômes de Schubert, C.R. Acad. Sci. Paris, 294 (1982), 447–450.

[13] A. Lascoux and M. Schützenberger: Schubert polynomials and the Littlewood– Richardson rule, Lett. Math. Phys. 10(2-3) (1985), 111–124.

[14] D. Little: Combinatorial aspects of the Lascoux–Schützenberger tree. Adv. Math. 174 (2003), 236–253.

[15] I. Macdonald: Symmetric Functions and Hall Polynomials, Oxford University Press, 1995.

[16] D. Peterson: Lecture notes at MIT, 1997.

[17] R. Stanley: On the number of reduced decompositions of elements of Coxeter groups, European J. Combinatorics 5 (1984), 359–372.

E-mail address: tfylam@math.harvard.edu

E-mail address: mshimo@vt.edu