ON 321-AVOIDING PERMUTATIONS

IN AFFINE WEYL GROUPS

R.M. Green

Department of Mathematics and Statistics Lancaster University Lancaster LA1 4YF England E-mail: r.m.green@lancaster.ac.uk

Abstract. We introduce the notion of 321-avoiding permutations in the affine Weyl group W of type A_{n−1} by considering the group as a George group (in the sense of Eriksson and Eriksson). This enables us to generalize a result of Billey, Jockusch and Stanley to show that the 321-avoiding permutations in W coincide with the set of fully commutative elements; in other words, any two reduced expressions for a 321-avoiding element of W (considered as a Coxeter group) may be obtained from each other by repeated applications of short braid relations.

Using Shi’s characterization of the Kazhdan–Lusztig cells in the group W, we use our main result to show that the fully commutative elements of W form a union of Kazhdan–Lusztig cells. This phenomenon has been studied by the author and J. Losonczy for finite Coxeter groups, and is interesting partly because it allows certain structure constants for the Kazhdan–Lusztig basis of the associated Hecke algebra to be computed combinatorially.

We also show how some of our results can be generalized to a larger group of permutations, the extended affine Weyl group associated to GL_{n}(ℂ).

To appear in the Journal of Algebraic Combinatorics

Introduction

Let W be a Coxeter group with generating set S = {s_{i}}_{i∈I}. The fully commu-

tative elements of W were defined by Stembridge, and may be characterised [18,

Proposition 1.1] as those elements all of whose reduced expressions avoid strings of

length m of the form s_{i}s_{j}s_{i} ⋯, where 2 < m = m_{i,j} is the order of s_{i}s_{j}. Billey,

Jockusch and Stanley [1, Theorem 2.1] show that in the case where W is the sym-

metric group (under the natural identifications), w ∈ W is fully commutative if and

2000 Mathematics Subject Classification. 05E15, 20C32. This paper was written at the Newton Institute, Cambridge, and supported by the special semester on Symmetric Functions and Macdonald Polynomials, 2001.

Typeset by AMS-TEX 2 R.M. GREEN

only if it is 321-avoiding. The latter condition means that there are no i < j < k such that w(i) > w(j) > w(k). It is clear from properties of root systems of type A that the 321-avoiding elements w ∈ W are precisely those for which there are no positive roots α, β such that both (i) α + β is a root and (ii) w(α) and w(β) are both negative roots.

In this paper we consider the affine analogue of this problem. To define the analogue of a 321-avoiding permutation, we recall Lusztig’s realization of the affine Weyl group of type Ã_{n−1} as a group of permutations of the integers. The interplay between the permutation representation and the root system of type Ã can be seen in the work of Papi [15], and the relationship between full commutativity and root systems in simply laced types has been established by Fan and Stembridge [6]. It is therefore not hard to show that the 321-avoiding elements and the fully commutative elements coincide in type Ã, but we choose to give a different derivation of this result (avoiding root systems) because the equivalence of conditions (iii) and (iv) of Theorem 2.7 is not made explicit in [15].

Our real interest in this problem stems from a desire to understand the Kazhdan– Lusztig basis combinatorially. The two-sided Kazhdan–Lusztig cells for Coxeter groups of type Ã_{n−1} were classified by Shi [16] according to a combinatorial criterion on elements w ∈ W generalizing the notion of 321-avoidance. Although it may be possible to classify the Kazhdan–Lusztig cells of a given Coxeter group using a purely algebraic or combinatorial approach, it is not reasonable to expect that the Kazhdan–Lusztig basis {C′_{w} : w ∈ W } itself and its structure constants may be understood using similar means. However, as we discuss in §5, if the fully commutative elements form a union of Kazhdan–Lusztig cells closed under ≥_{LR}, results of the author and J. Losonczy in [10] reduce the problem of computing the coefficient of C′_{z} in C′_{x}C′_{y} to a tractable combinatorial problem in the case that z is fully commutative.

We also show how these results may be generalized to a certain extension of the affine Weyl group of type Ã_{n−1}.

1. Affine Weyl groups of type A as permutations

In §1, we show how the affine Weyl group W of type A and its extension Ŵ may be viewed as groups of permutations of ℤ. In the case of the Coxeter group W,

ON 321-AVOIDING PERMUTATIONS IN AFFINE WEYL GROUPS 3

Eriksson and Eriksson [3, §5] call such a group of permutations a “George group” (after G. Lusztig). The group Ŵ is called (following [19, §2.1]) the extended affine Weyl group associated to GL_{n}(ℂ), and it can be similarly considered as a group of permutations. We follow the treatment of these groups in [7, §1] but work with left actions rather than right actions.

The affine Weyl group of type Ã_{n−1} arises from the Dynkin diagram in Figure 1.

Figure 1. Dynkin diagram of type Ã_{n−1}

The number of vertices in Figure 1 is n. The top vertex is regarded as an extra relative to the remainder of the graph, which is a Coxeter graph of type A_{n−1}. We will assume n ≥ 3 throughout this paper.

We associate an affine Weyl group, W = W (Ã_{n−1}), to this Dynkin diagram in the usual way (as in [12, §2.1]). This associates to node i of the graph a generating involution s_{i} of W, where s_{i}s_{j} = s_{j}s_{i} if i and j are not adjacent in the graph, and

s_{i}s_{j}s_{i} = s_{j}s_{i}s_{j}

if i and j are adjacent in the graph. For t ∈ ℤ, it is convenient to denote by t̄ the congruence class of t modulo n, taking representatives in the set {1, 2, …, n}. For the purposes of this paper, it is helpful to think of the group W as follows. Proposition 1.1 (Lusztig). There exists a group isomorphism from W to the set of permutations of ℤ which satisfy the following conditions:

w(i + n) = w(i) + n for i ∈ ℤ,  (1)
∑_{t=1}^{n} w(t) = ∑_{t=1}^{n} t  (2)

such that s_{i} is mapped to the permutation

t ↦ \{ \begin{matrix}t & if t̄≠ ī, \overline{i + 1}, \\ t − 1 & if t̄= \overline{i + 1}, \\ t + 1 & if t̄= ī, \end{matrix}

4 R.M. GREEN

for t ∈ ℤ. Proof. This result is stated in [14, §3.6]; a proof may be found in [3, Theorem 20]. □

We also define an extension, Ŵ, of W as a group of permutations of ℤ, as in [19]. This group will be discussed in more depth in §4. Definition 1.2. Let ρ be the permutation of ℤ taking t to t + 1 for all t. Then the group Ŵ is defined to be the group of permutations of ℤ generated by the group W and ρ. Proposition 1.3. There exists a group isomorphism from Ŵ to the set of permutations of ℤ that satisfies the condition w(i + n) = w(i) for all i ∈ ℤ. Any element of Ŵ is uniquely expressible in the form ρ^{z}w for z ∈ ℤ and w ∈ W. Conversely, any element of this form is an element of Ŵ. Proof. Note that we automatically have

∑_{t=1}^{n} w(t) ≡ ∑_{t=1}^{n} t mod n

because w is a permutation. The result now follows from [7, Proposition 1.1.3, Corollary 1.1.4]. □

The group Ŵ can be expressed in a more familiar way using a semidirect product construction. Proposition 1.4. Let S_{n} be the subgroup of Ŵ generated by

{s_{1}, s_{2}, …, s_{n−1}}.

Let Z be the subgroup of Ŵ consisting of all permutations z satisfying

z(t) ≡ t mod n

for all t. Then ℤ^{n} ≅ Z ⊴ Ŵ and W is isomorphic to the semidirect product of S_{n} and Z. Proof. See [7, Proposition 1.1.5]. □

In the language of [3, 5.1.2], the George group W is defined as the group of “locally finite” permutations which commute with all elements of the “rigid group”

ON 321-AVOIDING PERMUTATIONS IN AFFINE WEYL GROUPS 5

of translations generated by ρ^{n}. Proposition 1.4 is saying that the group Ŵ may be obtained by dropping the hypothesis of local finiteness.

It is convenient to extend the usual notion of the length of an element of a Coxeter group to the group Ŵ in the following way.

Definition 1.5. Let w ∈ W and let w = s_{i_{1}}s_{i_{2}} ⋯ s_{i_{r}} be a word in the set S of generating involutions such that r is minimal. Then we define the length of w, ℓ(w), to be equal to r.

The length, ℓ(w′), of a typical element w′ = ρ^{z}w of Ŵ (where z ∈ ℤ and w ∈ W) is defined to be ℓ(w).

Definition 1.5 is very natural from the point of view of George groups: in the language of [3, §6.1] it states that the length of an element w ∈ Ŵ is equal to the “class inversion number” of w.

2. Pattern avoidance in Coxeter groups

In §2, we restrict our attention to the Coxeter group W of type Ã_{n−1}. We first recall the notions of full commutativity and 321-avoidance.

Definition 2.1. Let w ∈ W.

We say w is fully commutative if no reduced expression for w contains a subword of the form s_{i}s_{j}s_{i} for Coxeter generators s_{i} and s_{j}. The set of fully commutative elements of W is denoted by W_{c}.

We say w is 321-avoiding if, when W is considered as a George group as in Proposition 1.1, there are no integers a < b < c such that w(a) > w(b) > w(c).

Remark 2.2. Notice that if w ∈ W is such that a < b < c and w(a) > w(b) > w(c), it must be the case that w(a), w(b) and w(c) are pairwise non-congruent modulo n.

The following result will be used to address the issue of checking whether an infinite permutation is 321-avoiding.

Proposition 2.3. Let w ∈ W and a, b, c ∈ ℤ with a < b < c. If w(a) > w(b) > w(c), then there exist a′, c′ ∈ ℤ with 0 < b − a′ < n, 0 < c′ − b < n, a ≡ a′ mod n, c ≡ c′ mod n, a′ < b < c′ and w(a′) > w(b) > w(c′).

6 R.M. GREEN

Proof. First, note that a, b and c are pairwise noncongruent modulo n by Remark 2.2.

Write c = c′ + kn with k ∈ ℤ^{≥0} and 0 < c′ − b < n. By condition (1) of Proposition 1.1, we may assume without loss of generality that k = 0 by replacing the triple (a, b, c) by (a, b, c′). This satisfies the claimed properties because w(b) > w(c) = w(c − kn) + kn ≥ w(c′).

The argument to find a′ is similar, starting with the condition a = a′ − kn with k ∈ ℤ^{≥0} and 0 < b − a′ < n. □ Remark 2.4. Suppose w ∈ W is given as a permutation. Proposition 2.3 shows that we can determine whether there exist a < b < c with w(a) > w(b) > w(c) by testing \binom{n}{3} triples. This is because if such a triple exists, we may assume that 1 ≤ b ≤ n by condition (1) of Proposition 1.1, and we may apply Proposition 2.3 to show that there exists a triple that in addition satisfies b − a < n and c − b < n. (Recall that a, b, c will be pairwise noncongruent modulo n by Remark 2.2.)

The next result will be useful in the proof of Theorem 2.7. Lemma 2.5.

(a) Let w ∈ W. We have

w(i) < w(i + 1) ⇔ ℓ(ws_{i}) > ℓ(w)

and

w^{−1}(i) < w^{−1}(i + 1) ⇔ ℓ(s_{i}w) > ℓ(w).

(b) If c, d ∈ ℤ with c < d, and s ∈ S is a generator of W, then s(c) ≥ s(d) implies that c = d − 1, s(c) = d and s(d) = c.

Proof. Part (a) is a restatement of [7, Corollary 1.3.3].

It is clear from Proposition 1.1 that s(c) ≥ s(d) can only occur if d − c ≤ 2, because |s(z) − z| ≤ 1 for all z ∈ ℤ. If d − c = 1 and s(c) ≥ s(d), then the fact that s induces a permutation of ℤ implies that s(c) = d and s(d) = c as claimed. If d − c = 2 and s(c) ≥ s(d), we must have s(c) = c + 1 and s(d) = d − 1, which also cannot happen since s induces a permutation and c + 1 = d − 1. Part (b) follows. □

The following result is reminiscent of [2, Lemma 1].

ON 321-AVOIDING PERMUTATIONS IN AFFINE WEYL GROUPS 7

Lemma 2.6. Let w ∈ W be fully commutative, and let s_{i_{1}}s_{i_{2}} ⋯ s_{i_{r}} be a reduced expression for w. Suppose s_{i_{j}} and s_{i_{k}} are consecutive occurrences of the generator s (meaning that s_{i_{j}} = s = s_{i_{k}} for some j < k and s_{i_{l}} ≠ s for all j < l < k). Let t and t′ be the two distinct Coxeter generators that do not commute with s. Then there is an occurrence s_{i_{p}} = t and an occurrence s_{i_{q}} = t′ with j < p, q < k. Note. This result is a consequence of [5, Lemma 4.3.5 (ii)] and its proof, but here we present a more direct argument based on property R3 of [4, §2]. Proof. Since w ∈ W_{c}, we can see that between the two named occurrences of s there must be at least two occurrences of generators that do not commute with s. If we choose s such that k − j is minimal, there must be at least one occurrence of each of the generators t and t′ in the given interval, as required. □ Theorem 2.7. Let w ∈ W = W (Ã_{n−1}). The following are equivalent:

(i) w is fully commutative (considering W as a Coxeter group); (ii) if a, b ∈ ℤ with a < b and we have w(a) > w(b), then w(a) > a and w(b) < b; (iii) w is 321-avoiding (considering W as a George group); (iv) there are no positive roots α, β, α + β in the root system of type Ã_{n−1} such that

w(α) < 0 and w(β) < 0. Note. Recall that the action of a generator s_{i} ∈ W on a simple root α_{j} is given by

s_{i}.α_{j} = \{ \begin{matrix}−α_{j} & if i = j, \\ α_{j} + α_{i} & if ī = \overline{j − 1} or ī = \overline{j + 1}, \\ α_{j} & otherwise. \end{matrix}

The reader is referred to [6] or [15] for further details of the root system. Proof. The equivalence of (i) and (iv) follows from [6, Theorem 2.4].

(i) ⇒ (ii).

Suppose that (ii) fails to hold. Suppose a < b and w(a) > w(b) and w(a) ≤ a. (The other possibility, that w(b) ≥ b, is proved using an argument similar to the following.)

Let s_{i_{r}}s_{i_{r−1}} ⋯ s_{i_{1}} be a reduced expression for w. For 1 ≤ j ≤ r, define

w[j] := s_{i_{j}}s_{i_{j−1}} ⋯ s_{i_{1}},

with w[0] := 1 for notational convenience. Since a < b and w(a) > w(b), there must exist 1 ≤ j ≤ r such that w[j](a) ≥ w[j](b) and w[j − 1](a) < w[j − 1](b).

8 R.M. GREEN

Applying Lemma 2.5 (b) with c = w[j − 1](a), d = w[j − 1](b) and s = s_{i_{j}}, we find that w[j](b) = w[j − 1](a) = w[j − 1](b) − 1 = w[j](a) − 1. There are two cases to check; they cover the possibilities because w(a) ≤ a.

Case 1: w(a) < w[j](a). Now w(a) = w[r](a) < w[j](a) > w[j − 1](a). It follows that there exist k and l with j ≤ k < l ≤ r such that

w[k−1](a)+1 = w[k](a) = w[k+1](a) = ⋯ = w[l−2](a) = w[l−1](a) = w[l](a)+1.

It follows that s_{i_{k}} = s_{i_{l}} and that no generator s_{i_{p}} for k < p < l is equal to s_{i_{k}} or to s_{1+i_{k}} (where addition is taken modulo n). Applying Lemma 2.6 to s_{i_{k}} and s_{i_{l}} now shows that w is not fully commutative, because s_{1+i_{k}} does not commute with s_{i_{k}}.

Case 2: a > w[j − 1](a). Here w[0](a) = a > w[j − 1](a) < w[j](a). It follows that there exist k and l with 1 ≤ k < l ≤ j and

w[k−1](a)−1 = w[k](a) = w[k+1](a) = ⋯ = w[l−2](a) = w[l−1](a) = w[l](a)−1.

The consideration of this case is now similar to case 1, mutatis mutandis. (ii) ⇒ (iii).

Suppose (iii) fails, so that there exist a < b < c with w(a) > w(b) > w(c). If w(b) ≤ b then (ii) fails when applied to b < c, and if w(b) ≥ b then (ii) fails when applied to a < b. (iii) ⇒ (i).

Suppose (i) fails. Let s_{i_{r}}s_{i_{r−1}} ⋯ s_{i_{1}} be a reduced expression for w for which s_{i_{t+1}} = s_{i_{t−1}} for some 1 < t < r. Define w[j] as in the proof of (i) ⇒ (ii) above. Let us assume that i_{t} = i_{t+1} + 1; the other case (i_{t} = i_{t+1} − 1) follows by a symmetric argument.

Let y = w[t − 2] and m = i_{t−1} (so that m + 1 = i_{t} by the previous paragraph). We first claim that y^{−1}(m) < y^{−1}(m + 1) < y^{−1}(m + 2). Since s_{i_{t−1}}y > y, Lemma 2.5 (a) shows that y^{−1}(m) < y^{−1}(m + 1). Since ℓ(s_{i_{t+1}}s_{i_{t}}s_{i_{t−1}}y) = ℓ(y) + 3 and s_{i_{t+1}}s_{i_{t}}s_{i_{t−1}} = s_{i_{t}}s_{i_{t−1}}s_{i_{t}}, it follows that s_{i_{t}}y > y and Lemma 2.5 (a) shows that y^{−1}(m + 1) < y^{−1}(m + 2). (This uses the fact that i_{t} = m + 1.)

Define a = y^{−1}(m), b = y^{−1}(m + 1) and c = y^{−1}(m + 2), and let z = w[t + 1]. It follows from the definition of the realization of the generators of W as permutations (given in Proposition 1.1) and the above paragraph that z(a) = m+2, z(b) = m+1 and z(c) = m. We are done once we show that w(a) > w(b) > w(c). Suppose

ON 321-AVOIDING PERMUTATIONS IN AFFINE WEYL GROUPS 9

w(a) ≤ w(b). Then there exists k such that t+1 < k ≤ r where we have w[k−1](a) > w[k − 1](b) and w[k](a) < w[k](b). This implies that w[k − 1](a) = w[k − 1](b) + 1 by Lemma 2.5 (b). Since ℓ(s_{i_{k}}w[k − 1]) > ℓ(w[k − 1]), applying Lemma 2.5 (a) with i = w[k − 1](b) yields a contradiction. We deduce that w(a) > w(b) and the proof that w(b) > w(c) is similar. □

It is possible to prove the equivalence of conditions (iii) and (iv) of Theorem 2.7 by using the formalism of George groups from [3]. If w ∈ W then the condition that wα < 0 for a positive root α is equivalent to the condition that ℓ(wt) < ℓ(w), where t is the (not necessarily simple) reflection corresponding to the root α. The simple reflections are defined in Proposition 1.1 and reflections in general will be conjugates of these, so they are easily identified. A more direct approach using roots as opposed to reflections is implicit in [15, Theorem 1].

It would be interesting to have an interpretation of condition (ii) of Theorem 2.7 in terms of roots, since this would enable the condition to be generalized to other types. Condition (ii) is also interesting in that it captures the notion of 321-avoiding by considering the images of only two elements.

3. Kazhdan–Lusztig cells

We wish to apply Theorem 2.7 in order to understand better the Kazhdan– Lusztig cells in type Ã_{n−1}. For any Coxeter group W, Kazhdan and Lusztig [13] defined partitions of W into left cells, right cells and two-sided cells, where the two-sided cells are unions of left (or right) cells. These cells are naturally partially ordered by an explicitly defined order, ≤_{LR}. We do not present the full definitions here; an elementary introduction to the theory may be found in [12, §7].

The properties of these cells are subtle and it seems impossible to understand them fully without using heavy machinery such as intersection cohomology. However, the problem of classifying the two-sided cells is combinatorially tractable in special cases, and Shi [16] succeeded in describing combinatorially the two-sided cells for the Coxeter group of type Ã_{n−1}. One of the main results of [16] describes a natural bijection between two-sided cells and partitions of n. This bijection, which is a generalization of the Robinson–Schensted correspondence, depends on concepts of which 321-avoidance is a special case.

10 R.M. GREEN

Our aim in §3 is to explain why the fully commutative elements in type Ã form a union of Kazhdan–Lusztig cells closed under the order ≥_{LR}. Fan and Stembridge [6, Theorem 3.1] have shown that for Coxeter groups of types A, D, E and Ã, W_{c} is a union of Spaltenstein–Springer–Steinberg cells. It is not always true (even in the aforementioned cases) that W_{c} is a union of Kazhdan–Lusztig cells, but the situation for finite Coxeter groups is well understood: the author and J. Losonczy proved in [10, Corollary 3.1.3] that an irreducible finite Coxeter group has this property if and only if it does not contain a parabolic subgroup of type D_{4}.

We start by recalling Shi’s map σ from W to the partitions of n as described in [16]. (We have changed the action of W on ℤ from being a right action to being a left action, but this makes no difference and σ(w) = σ(w^{−1}).)

Definition 3.1. Fix w ∈ W = W (Ã_{n−1}). Define, for k ≥ 1,

d_{k} = d_{k}(w) := max {|X| : X = ⋃_{i=1}^{k} X_{i} ⊂ ℤ}

where (a) the union is disjoint, (b) any two integers u, v ∈ X are required not to be congruent modulo n, and (c) whenever the subset X_{i} of ℤ contains integers u and v with u < v then we require w(u) > w(v). (Here, |X| denotes the cardinality of X.)

The partition σ(w) of n is defined by

(d_{1}, d_{2} − d_{1}, d_{3} − d_{2}, …, d_{t} − d_{t−1}),

where t is maximal subject to the condition that d_{t−1} < d_{t} (meaning that d_{t} = n).

It may not be obvious from the definition that σ(w) is a partition (i.e., d_{1} ≥ d_{2} −d_{1} ≥ ⋯ ≥ d_{t} −d_{t−1}), but this follows by a result of Greene and Kleitman [11].

Recall that if λ and μ are two partitions of n, we say that λ ⊵ μ (λ dominates μ) if for all k we have

∑_{i=1}^{k} λ_{i} ≥ ∑_{i=1}^{k} μ_{i}.

This defines a partial order on the set of partitions of n. As mentioned before, there is also a natural partial order ≤_{LR} on the two-sided Kazhdan–Lusztig cells of a Coxeter group. The following theorem explains how these two orders are related.

ON 321-AVOIDING PERMUTATIONS IN AFFINE WEYL GROUPS 11

Theorem 3.2 (Shi). Let y, w ∈ W = W (Ã_{n−1}). Then y ≤_{LR} w in the sense of Kazhdan–Lusztig if and only if σ(y) ⊵ σ(w). In particular, y and w are in the same two-sided cell (i.e., y ≤_{LR} w ≤_{LR} y) if and only if σ(y) = σ(w). Proof. See [17, §2.9]. □

As we now explain, it is not hard to see from these definitions that the 321avoiding elements of W are a union of Kazhdan–Lusztig cells. Lemma 3.3. Fix w ∈ W.

(i) If w is 321-avoiding then all the sets X_{i} in Definition 3.1 satisfy |X_{i}| ≤ 2. (ii) If w is not 321-avoiding then the number d_{1} in Definition 3.1 satisfies d_{1} ≥ 3. Proof. If there is a set X_{i} with |X_{i}| ≥ 3 then by definition of X_{i}, there exist u_{1}, u_{2}, u_{3} ∈ X_{i} with u_{1} < u_{2} < u_{3} but w(u_{1}) > w(u_{2}) > w(u_{3}). This proves (i). The proof of (ii) is similar: if a < b < c with w(a) > w(b) > w(c) then we may choose X_{1} to contain these integers a, b, c (and possibly others), thus showing that d_{1} ≥ 3. □ Theorem 3.4. Let W_{c} denote the set of fully commutative elements of W (Ã_{n−1}). Then W_{c} is a union of two-sided Kazhdan–Lusztig cells closed under ≥_{LR}. Note. By the statement W_{c} is closed under ≥_{LR} we mean that if w ∈ W_{c} and y ≥_{LR} w then y ∈ W_{c}. Proof. It is clearly enough to show that if w ∈ W \W_{c} and w ≥_{LR} y then y ∈ W \W_{c}. By theorems 2.7 and 3.2, it is enough to show that if w is not 321-avoiding and σ(y) ⊵ σ(w) then y is not 321-avoiding.

Suppose w and y are as above. Let λ = σ(w) and μ = σ(y). By Lemma 3.3 (ii), λ_{1} ≥ 3. Since μ ⊵ λ, it follows from the definition of the dominance order that μ_{1} ≥ 3. By Lemma 3.3 (i), this means that y is not 321-avoiding, as required. □

We will discuss some of the applications of Theorem 3.4 in §5.

4. The extended affine Weyl group associated to GL_{n}(ℂ)

We now return to the group Ŵ of Proposition 1.3. The generalization of Theorem 2.7 to this group is straightforward as we now show. Recall that every element w′ ∈ Ŵ may be written uniquely as ρ^{z}w for z ∈ ℤ and w ∈ W, where ρ is as in Definition 1.2.

12 R.M. GREEN

Definition 4.1. Let w′ = ρ^{z}w be a typical element of Ŵ. We say w′ is fully commutative if w is fully commutative, and we say w′ is 321-avoiding if w is 321avoiding.

The definition of 321-avoiding above is a natural one as if a < b then w(a) < w(b) if and only if w′(a) < w′(b).

The group Ŵ may be made to act on the root system of W in a natural way which is clear from the following fact. Lemma 4.2. Let s_{i} be a Coxeter generator of W. Then ρs_{i}ρ^{−1} = s_{i+1}, where addition is taken modulo n. Proof. This follows by considering the induced permutations on ℤ. □

We define the action of Ŵ on the root system by stipulating that ρ(α_{i}) = α_{i+1} (with addition taken modulo n); this is reasonable by Lemma 4.2. Notice that ρ^{n} acts as the identity; the extended affine Weyl group associated to SL_{n}(ℂ) is the quotient of Ŵ by the relation ρ^{n} = 1. Proposition 4.3. Let w ∈ Ŵ. The following are equivalent:

(i) w is fully commutative; (ii) w is 321-avoiding; (iii) there are no positive roots α, β, α + β in the root system of type Ã_{n−1} such that

w(α) < 0 and w(β) < 0. Proof. The equivalence of (i) and (ii) is immediate from the definitions and Theorem 2.7. It follows from the definition of the action of ρ on simple roots that powers of ρ permute the positive roots linearly. This means that if w = ρ^{z}w′ then w′(α) < 0 and w′(β) < 0 if and only if w(α) < 0 and w(β) < 0. The equivalence of (iii) with the other conditions now follows by Theorem 2.7. □

There seems to be no direct analogue of condition (ii) of Theorem 2.7 for the group Ŵ.

Our results here suggest the following question about George groups. Question 4.4. Is it possible to define in a uniform way an extended George group for affine types A, B, C and D that specializes to the group Ŵ in type A?

We do not necessarily expect that the extended George group for types B, C and D should be closely related to the group Ŵ.

ON 321-AVOIDING PERMUTATIONS IN AFFINE WEYL GROUPS 13

It is also natural to wonder whether Theorem 3.4 may be extended to other affine types. The theorem will fail for Coxeter systems containing a parabolic subgroup of type D_{4} by the results of [10], which rules out type D̃ and type B̃_{l} (at least for l ≥ 4). The most interesting open case is therefore that of type C̃.

5. Applications to Kazhdan–Lusztig theory

Theorem 3.4 shows that for the group W = W (Ã_{n−1}), the set W_{c} is a union of two-sided Kazhdan–Lusztig cells. This result may be refined as follows. Proposition 5.1. Let W_{c} denote the set of fully commutative elements of W (Ã_{n−1}). Then the number of distinct two-sided cells contained in W_{c} is (n+1)/2 if n is odd, and (n + 2)/2 if n is even. A set of representatives in W for the two-sided cells is given by the set

\{s_{2}s_{4} ⋯ s_{2k} : 0 ≤ k ≤ \frac{n}{2}\} ,

using the usual numbering of the generators shown in Figure 1. Proof. By theorems 2.7, 3.2, 3.4 and Lemma 3.3, the number of fully commutative two-sided cells in W_{c} is equal to the number of partitions of n with all parts less than or equal to 2, and the first claim follows. It follows from Definition 3.1 that if w = s_{2}s_{4} ⋯ s_{2k}, the partition σ(w) has k parts equal to 2 and the other parts equal to 1. The result follows. □

We end by discussing briefly the application of Theorem 3.4 to the computation of certain structure constants for the Kazhdan–Lusztig basis.

The Kazhdan–Lusztig basis, which first appeared in [13], is a free ℤ[v, v^{−1}]-basis for the Hecke algebra H(W) associated to the group W. The basis, {C′_{w} : w ∈ W }, is naturally indexed by W. The structure constants g_{x,y,z}, namely the Laurent polynomials occurring in the expression

C′_{x}C′_{y} = ∑_{z∈W} g_{x,y,z}C′_{z},

have many subtle properties, such as the fact that g_{x,y,z} ∈ ℕ[v, v^{−1}]. (It seems impossible to establish this fact combinatorially.)

Theorem 3.4 implies that the ℤ[v, v^{−1}]-span of the set

J(W) = {C′_{w} : w ∉ W_{c}}

is an ideal of H(W). The quotient algebra H(W)/J(W) is equipped with a nat-

ural basis {c_{w} : w ∈ W_{c}}, where c_{w} := C′_{w} + J(W). The basis {c_{w} : w ∈ W_{c}}

is the canonical basis (in the sense of [9]) for the quotient of the Hecke algebra

H(W)/J(W) by [10, Theorem 2.2.3]. Although we do not present full details, it

is possible to realize this canonical basis combinatorially; the description is similar

to that given in [8, Definition 6.4.3]. This means that, if z ∈ W_{c}, we can compute

g_{x,y,z} by simple combinatorial means. (Note that if z ∈ W_{c} and g_{x,y,z} ≠ 0 then we

must have x, y ∈ W_{c}.) In particular, it is easily checked that g_{x,y,z} ∈ ℕ[v, v^{−1}] in

this case.

Acknowledgements

The author thanks J.R. Stembridge for some helpful discussions and J. Losonczy

for comments on the manuscript.

References

[1] S.C. Billey, W. Jockusch and R.P. Stanley, Some Combinatorial Properties of Schubert Polynomials, J. Algebraic Combin. 2 (1993), 345–374.

[2] S.C. Billey and G.S. Warrington, Kazhdan–Lusztig Polynomials for 321-hexagon-avoiding permutations, J. Algebraic Combin. 13 (2001), 111–136.

[3] H. Eriksson and K. Eriksson, Affine Weyl groups as infinite permutations, Electron. J. Combin. 5 (1998).

[4] C.K. Fan, Structure of a Hecke algebra quotient, J. Amer. Math. Soc. 10 (1997), 139–167.

[5] C.K. Fan and R.M. Green, On the affine Temperley–Lieb algebras, Jour. L.M.S. 60 (1999), 366–380.

[6] C.K. Fan and J.R. Stembridge, Nilpotent orbits and commutative elements, J. Alg. 196 (1997), 490–498.

[7] R.M. Green, The affine q-Schur algebra, J. Alg. 215 (1999), 379–411.

[8] , Tabular algebras and their asymptotic versions, J. Algebra (to appear;

    math.QA/0107230).

[9] R.M. Green and J. Losonczy, Canonical bases for Hecke algebra quotients, Math. Res. Lett. 6 (1999), 213–222.

[10] , Fully commutative Kazhdan–Lusztig cells, Ann. Inst. Fourier (Grenoble) 51 (2001), 1025–1045.

[11] C. Greene and D.J. Kleitman, The structure of Sperner k-families, J. Combin. Theory Ser. A 20 (1976), 41–68.

[12] J.E. Humphreys, Reflection Groups and Coxeter Groups, Cambridge University Press, Cambridge, 1990.

[13] D. Kazhdan and G. Lusztig, Representations of Coxeter groups and Hecke algebras, Invent. Math. 53 (1979), 165–184.

[14] G. Lusztig, Some examples of square integrable representations of semisimple p-adic groups, Trans. Amer. Math. Soc. 277 (1983), 623–653.

[15] P. Papi, Inversion tables and minimal left coset representatives for Weyl groups of classical type, J. Pure Appl. Alg. 161 (2001), 219–234.

[16] J.Y. Shi, The Kazhdan–Lusztig cells in certain affine Weyl groups, Lecture Notes in Mathematics 1179 (1986), Spinger, Berlin.

[17] , The partial order on two-sided cells of certain affine Weyl groups, J. Alg. 176 (1996), 607–621.

[18] J.R. Stembridge, On the fully commutative elements of Coxeter groups, J. Algebraic Combin. 5 (1996), 353–385.

[19] N. Xi, The based ring of two-sided cells of affine Weyl groups of type Ã_{n−1} (to appear;

    math.QA/0010159).