FREELY BRAIDED ELEMENTS IN COXETER GROUPS, II

R.M. Green and J. Losonczy

Department of Mathematics University of Colorado Campus Box 395 Boulder, CO 80309-0395 USA E-mail: rmg@euclid.colorado.edu

Department of Mathematics Long Island University Brookville, NY 11548 USA E-mail: losonczy@e-math.ams.org

Abstract. We continue the study of freely braided elements of simply laced Coxeter groups, which we introduced in a previous work. A known upper bound for the number of commutation classes of reduced expressions for an element of a simply laced Coxeter group is shown to be achieved only when the element is freely braided; this establishes the converse direction of a previous result. It is also shown that a simply laced Coxeter group has finitely many freely braided elements if and only if it has finitely many fully commutative elements.

To appear in Advances in Applied Mathematics

Introduction

In [5] we defined, for an arbitrary simply laced Coxeter group, a subset of “freely

braided elements”. Such elements include the fully commutative elements of Stem-

bridge [8] as a particular case. The idea behind the definition is that although it

1991 Mathematics Subject Classification. 20F55. Key words and phrases. braid relation, commutation class, Coxeter group, root sequence.

Typeset by AMS-TEX 2 R.M. GREEN AND J. LOSONCZY

may be necessary to use long braid relations in order to pass between two reduced expressions for a freely braided element, the necessary long braid relations in a certain sense do not interfere with one another.

Every reduced expression for a Coxeter group element w determines a total ordering of the set of positive roots made negative by w. These totally ordered sets are known as “root sequences”. If a root sequence for an element w of a simply laced Coxeter group contains a consecutive subsequence of the form α, α + β, β, then we refer to the set of these roots as a “contractible inversion triple” of w. A group element is said to be “freely braided” if its contractible inversion triples are pairwise disjoint.

Let N(w) denote the number of contractible inversion triples of w. It was shown in [5] that the number of commutation classes (short braid equivalence classes of reduced expressions) of w is bounded above by 2^{N(w)}, and that this bound is achieved if w is freely braided. In this paper, we prove that the bound can be achieved only for freely braided w (Theorem 2.2.1). This was previously known in the type A setting [5, Theorem 5.2.1], but the argument given here has the advantage of being conceptual as well as more general.

The second main result of this paper is a classification of the simply laced Coxeter groups having only finitely many freely braided elements. Note that it is possible for such a group to be infinite. It turns out (see the discussion following Theorem 3.3.3) that this question has the same answer as a classification question previously answered by others [2, 4, 8]: we will show in Theorem 3.3.3 that a simply laced Coxeter group has finitely many freely braided elements if and only if it has finitely many fully commutative elements. One implication here is easy, but the converse requires some effort. Our proof of Theorem 3.3.3 does not rely on a case analysis based on any classification result.

FREELY BRAIDED ELEMENTS IN COXETER GROUPS, II 3

1. Preliminaries

1.1 Basic terminology and notation.

Let W be a simply laced Coxeter group with distinguished generators S = {s_{i} : i ∈ I} and Coxeter matrix (m_{ij})_{i,j∈I}. For the basic facts concerning Coxeter groups, see [1] or [6]. Denote by I^{∗} the free monoid on I. We call the elements of I letters and those of I^{∗} words. The length of a word is the number of factors required to write the word as a product of letters. Let ϕ : I^{∗} ⟶ W be the surjective morphism of monoid structures satisfying ϕ(i) = s_{i} for all i ∈ I. A word i ∈ I^{∗} is said to represent its image w = ϕ(i) ∈ W; furthermore, if the length of i is minimal among the lengths of all the words that represent w, then we call i a reduced expression for w. The length of w, denoted by ℓ(w), is then equal to the length of i.

Let V be a vector space over the field of real numbers with basis {α_{i} : i ∈ I}, and denote by B the Coxeter form on V associated to W. This is the symmetric bilinear form satisfying B(α_{i}, α_{j}) = − cos \frac{π}{m_{ij}} for all i, j ∈ I. We view V as the underlying space of a reflection representation of W, determined by the equalities s_{i}α_{j} = α_{j} − 2B(α_{j}, α_{i})α_{i} for all i, j ∈ I. The Coxeter form is preserved by W relative to this representation.

Denote by Φ the root system of W, i.e., the set {wα_{i} : w ∈ W and i ∈ I}. Let Φ^{+} be the set of all β ∈ Φ such that β is expressible as a linear combination of the α_{i} with nonnegative coefficients, and let Φ^{−} = −Φ^{+}. We have Φ = Φ^{+} ∪Φ^{−} (disjoint). The elements of Φ^{+} (respectively, Φ^{−}) are called positive (respectively, negative) roots. The α_{i} are also referred to as simple roots. We define the height of any root β to be the sum of the coefficients used to express β as a linear combination of the simple roots.

Associated to each w ∈ W is the inversion set Φ(w) = Φ^{+}∩w^{−1}(Φ^{−}). It has ℓ(w) elements and determines w uniquely. Given any reduced expression i_{1}i_{2} ⋯ i_{n} for w, we have Φ(w) = {r_{1}, r_{2}, …, r_{n}}, where r_{1} = α_{i_{n}} and r_{l} = s_{i_{n}} ⋯ s_{i_{n−l+2}}(α_{i_{n−l+1}}) for all l ∈ {2, …, n}. Form the sequence r̄ = (r_{1}, r_{2}, …, r_{n}). We call r̄ the root

4 R.M. GREEN AND J. LOSONCZY

sequence of i_{1}i_{2} ⋯ i_{n}, or a root sequence for w. Notice that any initial segment of a root sequence is also a root sequence for some element of W.

Let w ∈ W. Any subset of Φ(w) of the form {α, β, α + β} will be called an inversion triple of w. We say that an inversion triple T of w is contractible if there is a root sequence for w in which the elements of T appear consecutively (in some order). The number of contractible inversion triples of w will be denoted by N(w). If the contractible inversion triples of w are pairwise disjoint, then w is said to be freely braided. 1.2 Braid moves.

Given any i, j ∈ I and any nonnegative integer n, we write (i, j)_{n} for the length n word iji ⋯ ∈ I^{∗}. Let i, j ∈ I^{∗} and let i, j ∈ I with m_{ij} ≠ 1. We call the substitution i(i, j)_{m_{ij}}j → i(j, i)_{m_{ji}}j a braid move, qualifying it short or long according as m_{ij} equals 2 or 3.

Let w ∈ W. A well-known result of Matsumoto [7] and Tits [9] states that any reduced expression for w can be transformed into any other by applying a (possibly empty) sequence of braid moves.

We say that two words are commutation equivalent if one can be transformed into the other by a sequence of short braid moves. The set of words that are commutation equivalent to a given word is called the commutation class of that word. If the set of reduced expressions for an element w ∈ W forms a single commutation class, then we call w fully commutative, following [8, §1].

Applying a braid relation to a reduced expression corresponds to applying a permutation to the root sequence of that reduced expression. The following proposition makes this more precise. Proposition 1.2.1 [5, Proposition 3.1.1]. Let w ∈ W, let i, j ∈ I^{∗} and let i, j, k ∈ I. Denote the length of j by n.

(a) Assume that iijj is a reduced expression for w, and let r̄ = (r_{l}) be the associated root sequence.

FREELY BRAIDED ELEMENTS IN COXETER GROUPS, II 5

(i) Suppose m_{ij} = 2, so that ijij is also a reduced expression for w. Then the root sequence r̄′ of ijij can be obtained from r̄ by interchanging r_{n+1} and r_{n+2}, which are mutually orthogonal relative to B.

(ii) If r_{n+1} and r_{n+2} are orthogonal, then m_{ij} = 2.

(b) Assume that iijkj is a reduced expression for w, and let r̄ = (r_{l}) be the associated root sequence.

(i) Suppose k = i, so that m_{ij} = 3 and ijijj is also a reduced expression for w. Then the root sequence r̄′ of ijijj can be obtained from r̄ by interchanging r_{n+1} and r_{n+3}. Furthermore, we have r_{n+1} + r_{n+3} = r_{n+2}.

(ii) If r_{n+1} + r_{n+3} = r_{n+2}, then k = i ≠ j and m_{ij} = 3. □

Let r̄ and r̄′ be as in part (a)(i) (respectively, part (b)(i)) of Proposition 1.2.1. Employing again the terminology used above for words, we say that the passage from r̄ to r̄′ is obtained by a short braid move (respectively, long braid move). Two root sequences are said to be commutation equivalent if one can be transformed into the other by applying a sequence of short braid moves. The set of root sequences that are commutation equivalent to a given root sequence is called the commutation class of that root sequence.

Let w ∈ W. The recipe for associating a root sequence to a reduced expression defines a bijection from the set of reduced expressions for w to the set of root sequences for w, and by Proposition 1.2.1, this bijection is compatible with the application of both long and short braid moves. Hence, by the result of Matsumoto and Tits cited above, any root sequence for w can be transformed into any other by applying a sequence of long and short braid moves. It also follows that there is a natural bijection between the set of commutation classes of reduced expressions for w and the set of commutation classes of root sequences for w.

A subword of a word i_{1}i_{2} ⋯ i_{n} (each i_{l} ∈ I) is any word of the form i_{p}i_{p+1} ⋯ i_{q}, where 1 ≤ p ≤ q ≤ n. Proposition 1.2.2. Let w ∈ W. The following are equivalent:

6 R.M. GREEN AND J. LOSONCZY

(i) w is fully commutative. (ii) w has no inversion triples. (iii) w has no contractible inversion triples. (iv) No reduced expression for w contains a subword of the form iji, where i, j ∈ I.

Proof.

(i) ⇒ (ii) This is the implication (a) ⇒ (c) of [3, Theorem 2.4]. (ii) ⇒ (iii) This is immediate from the definitions. (iii) ⇒ (iv) If w has a reduced expression with a subword of the form iji, then Proposition

1.2.1 (b)(i) shows that w has a contractible inversion triple.

(iv) ⇒ (i) If w is not fully commutative, then there exists a pair of commutation inequivalent reduced expressions for w. It follows by the result of Matsumoto and Tits mentioned above that w has a reduced expression to which a braid move can be applied. Thus, w does not satisfy (iv). □

2. Freely braided elements and commutation classes

2.1 The map F_{w}.

Let w ∈ W. Fix an arbitrary antisymmetric relation ⪯ on Φ(w) with the property that any two roots in Φ(w) are comparable relative to ⪯. Let C(w) and I(w) denote the set of commutation classes of root sequences for w and the set of contractible inversion triples of w, respectively. We define a map

F_{w} : C(w) ⟶ {0, 1}^{I(w)},

depending on ⪯, as follows. If I(w) is empty, then {0, 1}^{I(w)} contains just the empty map, and the set C(w) is also a singleton by Proposition 1.2.2. Thus, in this situation, F_{w} is uniquely determined. Suppose that I(w) is nonempty. Let C ∈ C(w) and let ≤_{C} be the partial ordering of Φ(w) obtained by taking the transitive closure of the following relations: α < β whenever α lies to the left of β in some root sequence from C and B(α, β) ≠ 0. Note that ≤_{C} is well-defined by [5,

FREELY BRAIDED ELEMENTS IN COXETER GROUPS, II 7

Proposition 3.1.5]. Given any {α, β, α + β} ∈ I(w), we define F_{w}(C)({α, β, α + β}) to be 0 if α and β are in the same relative order with respect to ≤_{C} and ⪯, and otherwise we define F_{w}(C)({α, β, α + β}) to be 1.

The map F_{w} is injective [5, Theorem 4.1.1].

It will be convenient to have the following terminology when determining the surjectivity, or otherwise, of F_{w}. Let w ∈ W and let T be a subset of I(w). We say that F_{w} separates T if every map from T to {0, 1} is the restriction of some element of F_{w}(C(w)). Clearly, if F_{w} fails to separate some nonempty subset of I(w), then F_{w} is not surjective.

2.2 First main result.

It was shown in [5, Corollary 4.1.2, Corollary 4.2.4] that every w ∈ W has at most 2^{N(w)} commutation classes, with equality if w is freely braided. The following theorem shows that equality is achieved only if w is freely braided. For the special case where W is of type A, this was already done in [5, Theorem 5.2.1] using an ad hoc argument.

Theorem 2.2.1. If w ∈ W has 2^{N(w)} commutation classes, then w is freely braided.

Proof. Let w be a non-freely-braided element. Since F_{w} is injective, it suffices to prove that F_{w} is not surjective. Let α be a root belonging to at least two contractible inversion triples of w, and assume that the height of α is maximal with respect to this property. Let T and T′ be distinct contractible inversion triples of w containing α. Note that |T ∩ T′| = 1 (this follows easily from [5, Remark 2.2.2] and the contractibility of the triples). By symmetry, there are three cases to consider.

Case 1: T = {α, β, α + β} and T′ = {α, γ, α + γ}.

By [5, Remark 2.2.2] and the contractibility of T, w has a root sequence of the form

(…, α, α + β, β, …, α + γ, …, γ, …)

8 R.M. GREEN AND J. LOSONCZY

or

(…, γ, …, α + γ, …, α, α + β, β, …).

We assume the existence of a sequence of the former type, the argument for the latter being similar. By our choice of α, the roots α + β and α + γ cannot belong to the same contractible inversion triple of w. Suppose that α + β is not orthogonal to α + γ. Then, by [5, Proposition 3.2.2], α + β lies to the left of α + γ in every root sequence for w, and so it is impossible for α to be at the same time to the left of α + β and to the right of α + γ. Thus, F_{w} does not separate {T, T′}.

Suppose instead that α + β is orthogonal to α + γ. Then α + β and γ are not mutually orthogonal, since α + β is not orthogonal to α. Furthermore, α + β and γ cannot belong to the same contractible inversion triple of w, by our choice of α. It follows (again by [5, Proposition 3.2.2]) that α + β lies to the left of γ in every root sequence for w. This means that in any root sequence for w in which α lies to the left of α + β, the root γ necessarily lies to the right of α + γ (otherwise, γ lies to the left of α + γ, which must then be to the left of α, which in turn is to the left of α + β, a contradiction). Again, F_{w} does not separate {T, T′}.

Case 2: T = {α, β, α − β} and T′ = {α, γ, α − γ}.

Here, we may assume without loss of generality that w has a root sequence of the form

(…, γ, …, β, α, α − β, …, α − γ, …).

Note that γ cannot be orthogonal to both β and α−β, or it would be orthogonal to their sum. We may assume that γ is not orthogonal to β. If no contractible inversion triple of w contains both γ and β, then γ lies to the left of β in every root sequence for w, and consequently there is no root sequence for w in which β lies to the left of α and γ lies to the right of α. It follows that F_{w} does not separate {T, T′}.

Suppose instead that there is a contractible inversion triple T′′ of w that contains

FREELY BRAIDED ELEMENTS IN COXETER GROUPS, II 9

γ and β. We claim that F_{w} does not separate {T, T′, T′′}. To see this, observe that if C is a commutation class relative to which γ lies to the left of β (this determines F_{w}(C)(T′′)), and β lies to the left of α (this determines F_{w}(C)(T)), then γ lies to the left of α (so that F_{w}(C)(T′) is also determined). (These conditions are well-defined by [5, Proposition 3.1.5].)

Case 3: T = {α, β, α − β} and T′ = {α, γ, α + γ}.

In this situation, w has a root sequence of the form

(…, β, α, α − β, …, α + γ, …, γ, …)

or

(…, γ, …, α + γ, …, β, α, α − β, …).

We deal with the former sequence, the analysis of the latter being similar.

Note that α + γ cannot be orthogonal to both β and α − β, or it would be orthogonal to their sum. We may assume that α + γ is not orthogonal to β. By our choice of α, the roots α + γ and β cannot belong to the same contractible inversion triple of w. Hence, β lies to the left of α + γ in every root sequence for w. It follows that there is no root sequence for w in which α lies to the right of α + γ and β lies to the right of α. This means that F_{w} does not separate {T, T′}.

We conclude that F_{w} is not surjective. □

Corollary 2.2.2. Every w ∈ W has at most 2^{N(w)} commutation classes, with equality if and only if w is freely braided. □

3. Free braidedness and full commutativity

The goal of this section, achieved by Theorem 3.3.3, is to prove that W has finitely many freely braided elements if and only if it has finitely many fully commutative elements.

10 R.M. GREEN AND J. LOSONCZY

3.1 Reduced expressions for freely braided elements.

For the purposes of the proof of Theorem 3.3.3, we wish to have a clearer picture on the nature of reduced expressions for freely braided elements.

Definition 3.1.1. Let i be a word in I^{∗} and suppose that i can be written as u_{0}b_{1}u_{1}b_{2}u_{2} ⋯ b_{p}u_{p}, where each b_{l} is of the form iji for some i, j ∈ I with m_{ij} = 3. Then we call b_{1}, b_{2}, …, b_{p} a braid sequence for i. If, furthermore, i is reduced and w = ϕ(i) is freely braided, then we say that i is contracted provided there exists a braid sequence for i with p = N(w) terms.

Definition 3.1.2. Let i ∈ I^{∗}. A word j ∈ I^{∗} is said to be close to i if there is a (possibly empty) braid sequence b_{1}, b_{2}, …, b_{p} for i such that j is the word obtained by applying a long braid move to each of the b_{l}. We also say that j is close to i via the sequence b_{1}, b_{2}, …, b_{p}.

Note that if two words are close to one another, then they represent the same element of W. Note also that any expression that is close to a contracted reduced expression is itself contracted.

We say that i, j ∈ I are m-commuting, or simply commuting, if m_{ij} ≠ 3.

Proposition 3.1.3. Let w ∈ W be freely braided.

(i) There exists a contracted reduced expression i for w. (ii) The reduced expressions close to i, which are also contracted reduced expressions,

form an irredundantly described set of commutation class representatives for w. (iii) Any contracted reduced expression for w has a unique braid sequence with N(w)

terms.

Proof. By [5, Theorem 4.2.3], there is a root sequence r̄ for w such that the roots in any given contractible inversion triple of w appear consecutively in r̄. Part (i) follows by applying Proposition 1.2.1 (b)(ii): take i to be the reduced expression corresponding to r̄, and note that the N(w) contractible inversion triples correspond to a braid sequence for i with N(w) terms. In view of Proposition 1.2.1 (b)(i), the

FREELY BRAIDED ELEMENTS IN COXETER GROUPS, II 11

expression i, or any contracted reduced expression for w, has at most one braid sequence with N(w) terms. This proves (iii).

If i′, i′′ ∈ I^{∗} are distinct and close to i, then i′ is not commutation equivalent to i′′ (to see this, observe that the sequence of occurrences of any pair of non-m-commuting letters in a word is an invariant of the commutation class of that word). Therefore, since there are 2^{N(w)} expressions close to i, and since w has exactly 2^{N(w)} commutation classes (by Corollary 2.2.2), part (ii) is proved. □

Remark 3.1.4. Let w ∈ W. From the proof of Proposition 3.1.3 (ii), we see that if a reduced expression for w has a braid sequence with p terms, then w has at least 2^{p} commutation classes.

Definition 3.1.5. Let i be a contracted reduced expression for a freely braided element w ∈ W, and write

i = u_{1}b_{1}u_{2}b_{2} ⋯ u_{N(w)}b_{N(w)}q,

where b_{1}, b_{2}, …, b_{N(w)} is the unique braid sequence for i with N(w) terms. If N(w) > 0, then we define D(i) = D^{1}(i) to be the word in I^{∗} obtained from i by deleting the rightmost letter in b_{N(w)}. We do not define D(i) if N(w) = 0. By induction, we write D^{n}(i) for D(D^{n−1}(i)) if n > 1 and the composition is defined. We agree that D^{0}(i) = i, regardless of the value of N(w).

Our strategy for the proof of Theorem 3.3.3 will be to argue that if i is a contracted reduced expression for a freely braided element w ∈ W, then D^{N(w)}(i) is a well-defined reduced expression for some fully commutative element. This will require several intermediate steps. One of these is the following technical lemma.

Lemma 3.1.6. Maintain the notation of Definition 3.1.5. Suppose that D(i) is a reduced expression for a freely braided element w′ ∈ W with N(w′) = N(w) − 1. Then any expression close to D(i) is of the form D(j), where j is a reduced expression for w that is close to i via a braid sequence not involving b_{N(w)}.

12 R.M. GREEN AND J. LOSONCZY

Proof. The hypotheses on D(i) imply that it is a contracted reduced expression for w′, and that b_{1}, b_{2}, …, b_{N(w)−1} is a braid sequence for D(i) with N(w′) terms. The conclusion follows. □

3.2 Freely braided elements and the N-statistic.

The following lemma describes what happens when one goes up in the weak Bruhat order from a freely braided element.

Lemma 3.2.1. Suppose that w ∈ W is freely braided, and that ℓ(ws_{i}) > ℓ(w) for some i ∈ I. As usual, we denote the simple root corresponding to i by α_{i}.

(a) Assume that α_{i} does not lie in any contractible inversion triple of ws_{i}.

(i) The roots occurring before α_{i} in any root sequence for ws_{i} are orthogonal to α_{i}. (ii) The contractible inversion triples of ws_{i} are precisely those of the form s_{i}(T),

where T is a contractible inversion triple of w. (iii) The element ws_{i} is freely braided and N(ws_{i}) = N(w).

(b) Assume that α_{i} lies in some contractible inversion triple of ws_{i}.

(i) There is a reduced expression i for w of the form uijv, where j ∈ I does not commute with i and where each letter in v commutes with i.

(ii) Any reduced expression for w that is commutation equivalent to the reduced expression i in (i) must be of the form u′iv_{1}jv_{2}, where each letter in v_{1} and each letter in v_{2} commutes with i.

Note. We do not require above that ws_{i} be freely braided.

Proof. We first prove (a).

Since there is a reduced expression for ws_{i} in which s_{i} appears last, there is a root sequence r̄ for ws_{i} in which α_{i} is the first root. Let r̄′ be an arbitrary root sequence for ws_{i}. By the discussion following Proposition 1.2.1, r̄′ may be obtained from r̄ by applying a sequence of braid moves. Since none of these braid moves can be a long braid move involving α_{i}, we find that all the roots occurring before α_{i} in r̄′ are orthogonal to α_{i}. This proves (i).

FREELY BRAIDED ELEMENTS IN COXETER GROUPS, II 13

Suppose that T is a contractible inversion triple of w, and let r̄_{0} be a root sequence for w in which the elements of T appear consecutively. Since (α_{i}, s_{i}(r̄_{0})) is a root sequence for ws_{i} (recall the definition of root sequence in §1.1), it follows that s_{i}(T) is a contractible inversion triple of ws_{i}.

Conversely, suppose that T′ is a contractible inversion triple of ws_{i}, and let r̄_{1} be a root sequence for ws_{i} in which the elements of T′ appear consecutively. By hypothesis, α_{i} does not appear in T′, and by (i), the elements appearing before α_{i} in r̄_{1} are orthogonal to α_{i}. Hence, we may apply short braid moves if necessary to obtain a root sequence r̄′_{1} for ws_{i} in which α_{i} appears first and in which the elements of T′ still appear consecutively. Now, r̄′_{1} is of the form (α_{i}, s_{i}(r̄′′_{1})), where r̄′′_{1} is a root sequence for w in which the elements of s_{i}(T′) occur consecutively. This proves (ii).

By (ii), we have N(ws_{i}) = N(w). Let r̄_{2} be a root sequence for w of the form specified in [5, Theorem 4.2.3]. Using (ii) again, we see that the contractible inversion triples of ws_{i}, the roots in each of which appear consecutively in the root sequence (α_{i}, s_{i}(r̄_{2})), are pairwise disjoint. Hence, ws_{i} is freely braided, and (iii) is proved.

We turn to (b).

Let r̄ be a root sequence for ws_{i} in which α_{i} appears first, and consider a sequence of braid moves of minimal length subject to the condition that applying the sequence to r̄ results in a root sequence r̄′ in which the elements of some contractible inversion triple containing α_{i} appear consecutively. Denote by T the contractible inversion triple that contains α_{i} and is consecutive in r̄′. By the minimality assumption, none of the braid moves in the above sequence is a long braid move involving α_{i}. Hence, every root occurring before α_{i} in r̄′ is orthogonal to α_{i}, and we may therefore apply a sequence of short braid moves to r̄′ to obtain a root sequence r̄′′ in which α_{i} appears first and in which the other elements of T appear consecutively. By Proposition 1.2.1, the sequence r̄′′ corresponds to a reduced expression for ws_{i} of

14 R.M. GREEN AND J. LOSONCZY

the form uijvi, where all of the letters in v commute with i. Deleting the rightmost i, we obtain a reduced expression for w of the required form, thus proving (i).

To prove (ii), we note that the reduced expression obtained in (i) is of the stated form, taking u′ = u, v_{1} = ∅ and v_{2} = v. The result follows, once we observe that applying a short braid move to a reduced expression of the form given in (ii) produces another expression of the same form. □

The next result describes what happens when one goes down in the weak Bruhat order from a freely braided element.

Lemma 3.2.2. Suppose that w ∈ W is freely braided and that i ∈ I satisfies ℓ(ws_{i}) < ℓ(w). Then ws_{i} is freely braided, and we have

N(ws_{i}) = \{ \begin{matrix}N(w) − 1 & if α_{i} lies in a contractible inversion triple of w, \\ N(w) & otherwise. \end{matrix}

Proof. If r̄ is a root sequence for ws_{i}, then (α_{i}, s_{i}(r̄)) is a root sequence for w. Therefore, every contractible inversion triple T of ws_{i} yields a contractible inversion triple s_{i}(T) of w. This gives N(w) ≥ N(ws_{i}). The inequality is strict if α_{i} lies in a contractible inversion triple of w.

By the Exchange Condition for Coxeter groups (see [6, §5.8]), w has a reduced expression i ending with i, and by Proposition 3.1.3 (ii), there is a contracted reduced expression j for w that is commutation equivalent to i. Write j = v_{1}iv_{2}, where each letter in v_{2} commutes with i. Suppose that α_{i} lies in a contractible inversion triple of w. Then N(ws_{i}) ≤ N(w)−1 by the first paragraph. On the other hand, it is clear that v_{1}v_{2}, a reduced expression for ws_{i}, has a braid sequence with N(w) − 1 terms; hence, N(ws_{i}) ≥ N(w) − 1 by Proposition 1.2.1 (b)(i). Further, by Remark 3.1.4, ws_{i} has at least 2^{N(ws_{i})} commutation classes. It now follows from Corollary 2.2.2 that ws_{i} is freely braided.

Suppose instead that α_{i} does not belong to a contractible inversion triple of w. Then, by Proposition 1.2.1 (b)(i), v_{1}v_{2} has a braid sequence with N(w) terms. It

FREELY BRAIDED ELEMENTS IN COXETER GROUPS, II 15

follows by the same proposition together with the first paragraph that N(ws_{i}) = N(w). As above, we find that ws_{i} has at least 2^{N(ws_{i})} commutation classes, and so is freely braided. □

Remark 3.2.3. If w ∈ W is freely braided and ℓ(ws_{i}) > ℓ(w) with ws_{i} non-freely-braided, it may happen that N(ws_{i}) > N(w) + 1. For example, if W is of type A_{3} and w = s_{2}s_{1}s_{3}s_{2} (using the obvious indexing), then N(w) = 0 but N(ws_{3}) = 2.

3.3 Groups with finitely many freely braided elements.

The following lemma is a crucial ingredient in the proof of Theorem 3.3.3.

Lemma 3.3.1. Let i be a contracted reduced expression for a freely braided element w ∈ W with N(w) > 0. Then D(i) is a contracted reduced expression for a freely braided element w′ with N(w′) = N(w) − 1.

Proof. We start by writing

i = c_{1}b_{1}c_{2}b_{2} ⋯ c_{N(w)}b_{N(w)}q,

where b_{1}, b_{2}, …, b_{N(w)} is the unique braid sequence for i with N(w) terms. Let i_{q} be the expression obtained from i by deleting from q all but its first q letters. We thus have i = i_{l}, where l is the length of q. If r̄ is the root sequence of i, then the first l roots in r̄ are not involved in any contractible inversion triple of w, and it follows from repeated applications of Lemma 3.2.2 that for each q, the reduced expression i_{q} represents a freely braided element y_{q} with N(y_{q}) = N(w). Moreover, if q > 0, then the first root in the root sequence of i_{q} does not lie in any contractible inversion triple of y_{q}.

We will prove by induction on q that D(i_{q}) is a reduced expression for a freely braided element w_{q} with N(w_{q}) = N(w) − 1. (These properties imply that D(i_{q}) is contracted.) Denote the letter that is deleted from i to form D(i) by j.

Base case: q = 0.

16 R.M. GREEN AND J. LOSONCZY

In this case, D(i_{0}) is obtained from i_{0} by removing the last letter, j. It is clear that D(i_{0}) is a reduced expression for some group element w_{0}, which is freely braided by Lemma 3.2.2. The first three roots in the root sequence of i_{0} comprise a contractible inversion triple containing α_{j}. Hence, by Lemma 3.2.2 again, N(w_{0}) = N(y_{0}) − 1, and the latter equals N(w) − 1 by the first paragraph.

Inductive step: proof that D(i_{q}) is reduced.

Suppose that the statement is true for all q with 0 ≤ q ≤ k < l. Let q = k + 1, and let i be the (k + 1)-st factor of q. By the inductive hypothesis, D(i_{k}) is a contracted reduced expression for a freely braided element w_{k} with N(w_{k}) = N(w) − 1. Assume toward a contradiction that D(i_{k+1}) is not reduced. Then by the Exchange Condition for Coxeter groups, there is a reduced expression i′ for w_{k} ending in i. According to Proposition 3.1.3 (ii), there is a unique contracted reduced expression i′′ for w_{k} that is both close to D(i_{k}) and commutation equivalent to i′. We may write

i′′ = p′′ic′′,

where all of the letters in c′′ commute with i.

By Lemma 3.1.6, i′′ must be of the form D(j), where j is close to i_{k}. The expression j is thus obtainable from i′′ by inserting the letter j at some point into the word. Since i_{k+1} is reduced, this insertion must take place to the right of the indicated occurrence of i in i′′. Therefore, ji, which is a reduced expression for y_{k+1}, is of the form

p′′ic′′_{1}jc′′_{2}i,

where each letter in c′′_{1} and each letter in c′′_{2} commutes with i. Applying short braid moves if necessary, we obtain

p′′c′′_{1}ijic′′_{2},

and it follows from Proposition 1.2.1 (b) that the first root in the root sequence of ji belongs to a contractible inversion triple. Now, j (respectively, ji) is a re-

FREELY BRAIDED ELEMENTS IN COXETER GROUPS, II 17

duced expression for y_{k} (respectively, y_{k+1}), and N(y_{k}) = N(y_{k+1}) = N(w). This contradicts Lemma 3.2.2, taking w = y_{k+1}.

We conclude that D(i_{k+1}) is reduced.

Inductive step: proof that w_{q} is freely braided and N(w_{q}) = N(w) − 1.

By the above, we have w_{k+1} = w_{k}s_{i} with ℓ(w_{k}s_{i}) > ℓ(w_{k}). If α_{i} does not lie in any contractible inversion triple of w_{k}s_{i}, then the inductive step follows from Lemma 3.2.1 (a)(iii) (with w_{k} playing the role of w). Assume instead that we are in case (b) of Lemma 3.2.1, which is the only alternative.

By Lemma 3.2.1 (b)(i), the element w_{k} has a reduced expression of the form uii′v, where i′ ∈ I does not commute with i and every letter in v commutes with i. Recall that D(i_{k}) is contracted by the inductive hypothesis. Hence, by Proposition 3.1.3 (ii), there is a contracted reduced expression d_{k} for w_{k} that is both close to D(i_{k}) and commutation equivalent to uii′v. According to Lemma 3.2.1 (b)(ii), we have d_{k} = u′iv_{1}i′v_{2}, where every letter in v_{1} and every letter in v_{2} commutes with i. Because d_{k} is close to D(i_{k}) and N(w_{k}) = N(y_{k}) − 1, Lemma 3.1.6 implies that d_{k} is of the form D(i′_{k}), where i′_{k} is a reduced expression for y_{k} that is close to i_{k} by a sequence of braid relations not involving b_{N(w)}. There is no loss in generality in assuming that i_{k} is equal to i′_{k}, so we will do this in order to make the arguments clearer.

Let d_{k+1} = d_{k}i = u′iv_{1}i′v_{2}i. Since d_{k} = D(i_{k}), we have d_{k+1} = D(i_{k+1}). Hence, by appropriately inserting j in d_{k+1}, we obtain i_{k+1}. The insertion must take place immediately to the right of a subword of d_{k+1} of the form jj′, where j′ ∈ I does not commute with j.

We know from the first paragraph of the proof that α_{i} does not lie in a contractible inversion triple of y_{k+1}. The only way this can happen is if the letter j is inserted in d_{k+1} somewhere between the two indicated occurrences of i, and if j does not commute with i. Since the letter sitting two places to the left of the insertion site is also an occurrence of j, the latter occurrence of j must either occur

18 R.M. GREEN AND J. LOSONCZY

to the left of the leftmost indicated occurrence of i in d_{k+1}, or must be the indicated occurrence of i′ in d_{k+1}. We consider each of these two cases in turn.

In the first case, i_{k+1} can be written as

u′′jijv_{1}i′v_{2}i,

where v_{1} and v_{2} are as before and u′′j = u′. Applying a long braid move, we obtain the following reduced expression for y_{k+1}:

u′′ijiv_{1}i′v_{2}i.

This contradicts the fact (mentioned in the first paragraph of the proof) that y_{k+1} is freely braided, because Proposition 1.2.1 can now be used to show that the middle of the three indicated occurrences of i corresponds to a root that lies in two different contractible inversion triples.

In the second case, i′ = j and i_{k+1} can be written as

u′iv_{1}jj′jv′_{2}i,

where v_{1} is as above and j′v′_{2} = v_{2}, meaning that i commutes with j′. Applying a long braid move and commutations, we obtain

u′v_{1}ij′jj′iv′_{2}.

This again leads to a contradiction because the indicated occurrence of j corresponds to a root that belongs to two different contractible inversion triples of y_{k+1}.

We have completed the inductive step by showing that case (b) of Lemma 3.2.1 cannot occur. □

Corollary 3.3.2. Let i be a contracted reduced expression for a freely braided element w ∈ W, and maintain the notation of Definition 3.1.5, so that

i = u_{1}b_{1}u_{2}b_{2} ⋯ u_{N(w)}b_{N(w)}q.

FREELY BRAIDED ELEMENTS IN COXETER GROUPS, II 19

Then the expression obtained by omitting the rightmost letter in each of the words b_{l} is a reduced expression for a fully commutative element.

Proof. By applying Lemma 3.3.1 N(w) times, we find that D^{N(w)}(i), which is the expression described in the conclusion, is a reduced expression for a freely braided element w′ with N(w′) = 0. By Proposition 1.2.2, w′ is fully commutative. □

Theorem 3.3.3. A simply laced Coxeter group W has finitely many freely braided elements if and only if it has finitely many fully commutative elements.

Proof. By Proposition 1.2.2, any fully commutative w ∈ W satisfies N(w) = 0, and so is freely braided for vacuous reasons. This proves the “only if” part of the theorem.

Conversely, suppose that W has finitely many fully commutative elements. By Corollary 3.3.2, there is a map from the set of contracted reduced expressions for freely braided elements of W to the set of reduced expressions for fully commutative elements of W, given by

i ↦ D^{N(ϕ(i))}(i).

Any element in the fibre over D^{N(ϕ(i))}(i) can be recovered from D^{N(ϕ(i))}(i) by making appropriate insertions of generators after certain subwords of the form ij, where i, j ∈ I are noncommuting. Hence, the fibres of the above map are all finite. Since there are finitely many fully commutative elements and each of these has finitely many reduced expressions, there are finitely many fibres. It follows that W has finitely many freely braided elements. □

Independently of one another, Graham [4] and Stembridge [8] have classified the Coxeter groups with finitely many fully commutative elements. The classification has also been worked out in the simply laced case by Fan [2]. It turns out that a simply laced Coxeter group has finitely many fully commutative elements if and only if each connected component of its Coxeter graph is of type A_{n}, D_{n} or E_{n} for arbitrary n. In particular, Coxeter groups of type E_{n} for n > 8 have finitely many fully commutative elements, although the groups are infinite. This classification

carries over for freely braided elements, by the above theorem.

References

[1] N. Bourbaki, Groupes et Algèbres de Lie, Chapitres IV–VI, Masson, Paris, 1981.

[2] C.K. Fan, A Hecke algebra quotient and properties of commutative elements of a Weyl group, Ph.D. thesis, M.I.T., 1995.

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

[4] J.J. Graham, Modular representations of Hecke algebras and related algebras, Ph.D. thesis, University of Sydney, 1995.

[5] R.M. Green and J. Losonczy, Freely braided elements in Coxeter groups, Ann. Comb. 6 (2002), 337–348.

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

[7] H. Matsumoto, Générateurs et relations des groupes de Weyl généralisés, C. R. Acad. Sci. Paris 258 (1964), 3419–3422.

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

[9] J. Tits, Le problème des mots dans les groupes de Coxeter, Ist. Naz. Alta Mat. (1968), Sympos. Math., vol. 1, Academic Press, London, 1969, pp. 175–185.