FREELY BRAIDED ELEMENTS IN COXETER GROUPS

R.M. Green and J. Losonczy

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

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

Abstract. We introduce a notion of “freely braided element” for simply laced Coxeter groups. We show that an arbitrary group element w has at most 2^{N(w)} commutation classes of reduced expressions, where N(w) is a certain statistic defined in terms of the positive roots made negative by w. This bound is achieved if w is freely braided. In the type A setting, we show that the bound is achieved only for freely braided w.

1. Introduction

A well-known result in the theory of Coxeter groups states that any two re-

duced expressions for the same element w of a Coxeter group are equivalent under

the equivalence relation generated by braid relations. If w is such that any two

of its reduced expressions are equivalent by short braid relations (i.e., iterated

commutations of commuting generators), we call w “fully commutative,” following

Stembridge [8].

In this paper, we introduce and study “freely braided elements” for an arbitrary

simply laced Coxeter group. This is a more general class of elements than the

aforementioned fully commutative elements. The idea behind the definition is that

although it may be necessary to use long braid relations in order to pass between two

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

1991 Mathematics Subject Classification. 20F55.

Key words and phrases. braid relation, commutation class, Coxeter group, root sequence.

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. The resulting sequences, called root sequences, play a central role in this paper. We are particularly interested in triples of roots of the form {α, α + β, β}, where each root in the triple is made negative by w (inversion triples). An inversion triple that occurs consecutively in some root sequence for w will be called contractible, and the statistic N(w) mentioned in the abstract above is the number of contractible inversion triples of w. We note that Fan and Stembridge have already shown in [5, Theorem 2.4] that an element of a simply laced Coxeter group is fully commutative if and only if it has no inversion triples.

In §4 of this paper, we prove that the number of commutation classes (short braid equivalence classes of reduced expressions) of w is bounded above by 2^{N(w)}, and this bound is achieved if w is freely braided. Furthermore, a freely braided element w has a root sequence in which each contractible inversion triple occurs as a consecutive subword (Theorem 4.2.3). In §5, we prove that if the Coxeter group is of type A, then the 2^{N(w)} bound is achieved only for freely braided w. Our proof relies on the fact that every inversion triple is contractible in the type A setting.

Along the way, we give a short proof that the commutation graph of any element of a simply laced Coxeter group is bipartite, extending a result in [4].

Another possible approach to proving these results is to use Viennot’s heaps of pieces [10]. These are certain labelled posets that can be associated to commutation classes of reduced expressions for elements of a Coxeter group (see [8, §1.2]). It can be shown that the dual of the heap of a reduced expression is isomorphic, as an abstract poset, to a certain poset arising naturally from the associated root sequence. However, we find it more convenient to argue directly with root sequences in this paper.

2. Preliminaries

2.1 Basic terminology and notation.

Let (W, S) be a Coxeter system, with Coxeter matrix {m(s, t)}_{s,t∈S}. It will be assumed throughout this paper that (W, S) is simply laced, so that m(s, t) ∈ {2, 3}

FREELY BRAIDED ELEMENTS IN COXETER GROUPS 3

for all pairs of distinct s, t ∈ S. We refer to W itself as a “Coxeter group”. The basic facts concerning Coxeter systems can be found in [3] or [6].

Let S^{∗} be the free monoid generated by S. The elements of S^{∗} will be written as finite sequences, e.g., s = (s_{1}, …, s_{n}). We define the length of any s ∈ S^{∗} to be the number of its entries.

There is a natural morphism of monoids ϕ : S^{∗} ⟶ W, given by ϕ(s_{1}, …, s_{n}) = s_{1} ⋯ s_{n} (the empty sequence is mapped to the identity, e). We say that an element s ∈ S^{∗} represents its image w = ϕ(s) ∈ W; furthermore, if the length of s is minimal among the lengths of all the sequences that represent w, then we say that s is reduced, and we call s a reduced expression for w. The length of w, denoted by ℓ(w), is then equal to the length of s.

Let V be a vector space over ℝ with basis {α_{s} : s ∈ S}, and let B be the Coxeter form on V associated to (W, S). This is the symmetric bilinear form satisfying B(α_{s}, α_{t}) = − cos \frac{π}{m(s,t)} for all s, t ∈ S. We shall view V as the underlying space of a reflection representation of W, determined by the equalities s α_{t} = α_{t} − 2B(α_{t}, α_{s})α_{s}, for s, t ∈ S. The Coxeter form is preserved by W relative to this representation.

Define Φ = {wα_{s} : w ∈ W and s ∈ S}. This is the root system of (W, S). Let Φ^{+} be the set of all β ∈ Φ such that β is expressible as a linear combination of the α_{s} with nonnegative coefficients, and let Φ^{−} = −Φ^{+}. Then Φ equals the disjoint union Φ^{+}∪Φ^{−} [6, §5.4]. The elements of Φ^{+} (respectively, Φ^{−}) are called “positive” (respectively, “negative”) roots. The α_{s} are often referred to as “simple” roots.

One can associate to each w ∈ W the set Φ(w) = Φ^{+} ∩ w^{−1}(Φ^{−}), which we call the inversion set of w. It is well known that Φ(w) has ℓ(w) elements and that w is uniquely determined by Φ(w). Given any reduced expression (s_{1}, …, s_{n}) for w, one has Φ(w) = {r_{1}, …, r_{n}}, where r_{1} = α_{s_{n}} and r_{i} = s_{n} ⋯ s_{n−i+2}(α_{s_{n−i+1}}) for all i ∈ {2, …, n} [6, Exercise 1, §5.6]. Following [5], we form the sequence r = (r_{1}, …, r_{n}), and call it the root sequence of (s_{1}, …, s_{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. Suppose that α, β are positive roots and a, b are positive integers such that aα + bβ is a positive root. Then one has the following two implications: α, β ∈ Φ(w) ⇒ aα + bβ ∈ Φ(w) and α, β ∉ Φ(w) ⇒ aα + bβ ∉ Φ(w). This property

4 R.M. GREEN AND J. LOSONCZY

of inversion sets is sometimes referred to as “biconvexity” (cf. [2, §3]).

2.2 Inversion triples.

Assume that (W, S) is of arbitrary simply laced type, unless stated otherwise.

Definition 2.2.1. 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). If the contractible inversion triples of w are pairwise disjoint, then w is said to be freely braided.

Remark 2.2.2. Let {α, α + β, β} be an inversion triple of w ∈ W. It follows immediately from the final two paragraphs of §2.1 that α + β must occur between α and β in any root sequence for w.

The following example establishes the existence of non-contractible inversion triples.

Example 2.2.3. Suppose that (W, S) has a parabolic subgroup of type D_{4}, generated by s_{1}, s_{2}, s_{3}, s_{4} ∈ S, where s_{2}s_{i} has order 3 for all i ≠ 2, and s_{i}s_{j} has order 2 whenever i, j ∈ {1, 3, 4} are distinct. Write α_{i} for the simple root α_{s_{i}}. Consider the element w = s_{2}s_{1}s_{3}s_{4}s_{2}s_{4}s_{3}s_{1}s_{2}. The root sequence corresponding to the reduced expression (s_{2}, s_{1}, s_{3}, s_{4}, s_{2}, s_{4}, s_{3}, s_{1}, s_{2}) is

\begin{aligned}(α_{2}, α_{1} + α_{2}, & α_{2} + α_{3}, α_{2} + α_{4}, α_{1} + 2α_{2} + α_{3} + α_{4}, \\ & α_{1} + α_{2} + α_{3}, α_{1} + α_{2} + α_{4}, α_{2} + α_{3} + α_{4}, α_{1} + α_{2} + α_{3} + α_{4}). \end{aligned}

Observe that α_{2} belongs to precisely one inversion triple of w, namely

{α_{2}, α_{1} + 2α_{2} + α_{3} + α_{4}, α_{1} + α_{2} + α_{3} + α_{4}}.

However, there is no root sequence for w in which these roots appear consecutively. This can be seen as follows. By inspection of the above root sequence, α_{2} is the only simple root in Φ(w). Hence, α_{2} must appear first in any root sequence for w. The second root in any root sequence for w must be a linear combination of at most two simple roots; this rules out α_{1} + 2α_{2} + α_{3} + α_{4} as a possibility.

It will be shown in §5.1 that in the type A setting, every inversion triple is contractible.

FREELY BRAIDED ELEMENTS IN COXETER GROUPS 5

3. Braid relations

In this section, (W, S) is assumed to be of arbitrary simply laced type. As in §2, we denote the associated Coxeter matrix by {m(s, t)}_{s,t∈S}.

3.1 More on root sequences.

The group W is by definition generated by the elements of S, subject only to the relations (st)^{m(s,t)} = e, for s, t ∈ S [6, §5]. These relations can be restated as s^{2} = e for s ∈ S, st = ts if m(s, t) = 2, and sts = tst if m(s, t) = 3. Given any s, t ∈ S and any nonnegative integer m, we write (s, t)_{m} for the length m sequence (s, t, s, …) ∈ S^{∗}. Let ≈ be the equivalence relation on S^{∗} generated by the elementary relations (s, t)_{m(s,t)} ≈ (t, s)_{m(s,t)}, for s, t ∈ S. When m(s, t) ≠ 1, we call such an elementary relation a braid relation, qualifying it short or long, according as m(s, t) = 2 or 3.

Let w ∈ W. A well-known result, attributed variously to Matsumoto [7] and Tits [9], states that the equivalence class relative to ≈ of any reduced expression for w coincides with the set of all reduced expressions for w.

We use the term commutation class to refer to any equivalence class arising from the equivalence relation on S^{∗} generated by the short braid relations.

Applying a braid relation to a given reduced expression corresponds to applying a permutation to the root sequence associated with that reduced expression. The following proposition makes this correspondence explicit.

Proposition 3.1.1. Let w ∈ W, let u, v ∈ S^{∗} and let s, s′, s′′ ∈ S. Denote the length of v by k.

(a) Assume that (u, s, s′, v) is a reduced expression for w, and let r = (r_{i}) be the root sequence of (u, s, s′, v).

(i) Suppose m(s, s′) = 2, so that (u, s′, s, v) is also a reduced expression for w. Then the root sequence r′ of (u, s′, s, v) can be obtained from r by interchanging r_{k+1} and r_{k+2}, which are mutually orthogonal.

(ii) If r_{k+1} and r_{k+2} are orthogonal, then m(s, s′) = 2.

(b) Assume that (u, s, s′, s′′, v) is a reduced expression for w, and let r = (r_{i}) be the root sequence of (u, s, s′, s′′, v).

(i) Suppose s′′ = s, so that m(s, s′) = 3 and (u, s′, s, s′, v) is also a reduced expression for w. Then the root sequence r′ of (u, s′, s, s′, v) can be obtained from r by

6 R.M. GREEN AND J. LOSONCZY

interchanging r_{k+1} and r_{k+3}. Furthermore, we have r_{k+1} + r_{k+3} = r_{k+2}. (ii) If r_{k+1} + r_{k+3} = r_{k+2}, then s′′ = s ≠ s′ and m(s, s′) = 3. Proof. We first prove the proposition under the additional hypothesis that v has length 0. For simplicity of notation, we denote the simple roots corresponding to s, s′ and s′′ by α, α′ and α′′, respectively.

Concerning (a), if m(s, s′) = 2, then the reduced expression (u, s, s′) has root sequence (α′, α, r_{3}, …) and (u, s′, s) has root sequence (α, α′, r_{3}, …). Statement (i) immediately follows. For (ii), we observe that if the roots α′ and s′(α) are orthogonal, then so are α and α′, and hence m(s, s′) = 2.

We turn to (b). If s = s′′, then the expression (u, s, s′, s) is reduced and has root sequence (α, α + α′, α′, r_{4}, …); likewise, (u, s′, s, s′) is reduced and has root sequence (α′, α + α′, α, r_{4}, …). This establishes (i). To prove (ii), we observe that in order for the equation

α′′ + s′′s′(α) = s′′(α′)

to hold, we must have s′′ = s; otherwise, the simple root α would lie in the support of the left hand side but not the right hand side (since s ≠ s′). It follows that m(s, s′) = 3 if r_{1} + r_{3} = r_{2}.

The general case (where v has length ≥ 0) follows from the above, using the definition of root sequence together with the fact that W acts linearly on V and preserves B. □ Definition 3.1.2. Let r and r′ be as in part (a)(i) (respectively, part (b)(i)) of Proposition 3.1.1. We call the passage from r to r′ a short braid move (respectively, long braid move). We say that two root sequences are commutation equivalent if one can be transformed into the other by applying a (possibly empty) sequence of short braid moves. The set of all root sequences that are commutation equivalent to a given root sequence will be called the commutation class of that root sequence. Remark 3.1.3. Let w ∈ W. The recipe that associates a root sequence to a reduced expression defines a bijection from the set of all reduced expressions for w to the set of all root sequences for w. By Proposition 3.1.1, this bijection is compatible with the application of both long and short braid moves. Hence, by the result of Matsumoto and Tits cited earlier, any root sequence for w may be transformed into any other by applying a (possibly empty) sequence of long and short braid moves.

FREELY BRAIDED ELEMENTS IN COXETER GROUPS 7

Definition 3.1.4. Let w ∈ W and let r = (r_{1}, …, r_{n}) be any root sequence for w. Following [4], we introduce a partial ordering ≤_{r} of Φ(w) by stipulating that r_{i} <_{r} r_{j} if i < j and the roots r_{i} and r_{j} are not orthogonal relative to B.

The following result is closely related to [5, Proposition 2.2].

Proposition 3.1.5. Let w ∈ W and let r and r′ be root sequences for w with respective partial orderings ≤_{r} and ≤_{r′} of Φ(w). Then ≤_{r} and ≤_{r′} agree if and only if r and r′ are commutation equivalent.

Proof. For the “if ” part, it is enough to treat the case where r and r′ differ by a single short braid move. In such a situation, the conclusion follows immediately from Definition 3.1.4.

For the converse, write r = (r_{1}, …, r_{n}) and r′ = (r′_{1}, …, r′_{n}). Let g be the permutation of {1, …, n} such that r_{i} = r′_{g(i)} for all i ∈ {1, …, n}. If ≤_{r} and ≤_{r′} agree, then, for all i, j ∈ {1, …, n} such that r′_{g(i)} and r′_{g(j)} are nonorthogonal, we have i < j if and only if g(i) < g(j). In particular, this means that if i is an index less than n such that r′_{g(i)} is not orthogonal to r′_{g(n)}, then g(i) < g(n). Hence, r′_{g(n)} can be moved to the last entry of the root sequence r′ using only short braid moves. Denote the resulting root sequence by r′′. Since any initial segment of a root sequence is also a root sequence, and since any element of W is uniquely determined by its inversion set, there is a w′ ∈ W such that the first n − 1 entries of r and the first n − 1 entries of r′′ are both root sequences for w′. The partial orders corresponding to these shorter root sequences agree. By induction, each of the shorter root sequences can be transformed into the other using only short braid moves. □

3.2 More on inversion triples.

The proposition below characterizes contractible inversion triples. Its proof depends on the following basic fact from the theory of Coxeter groups: given w ∈ W and s ∈ S, one has α_{s} ∈ Φ(w) if and only if w has a reduced expression with s as its last entry (see [6, Proposition 5.7, Theorem 5.8]).

Proposition 3.2.1. Let w ∈ W and let T = {α, α + β, β} be an inversion triple of w. The following are equivalent :

(i) T is contractible ;

8 R.M. GREEN AND J. LOSONCZY

(ii) there is a root sequence r for w such that α + β covers α or β relative to ≤_{r}; (iii) there is a root sequence r for w such that α or β covers α + β relative to ≤_{r}. Proof. The implications (i) ⇒ (ii) and (i) ⇒ (iii) are immediate from the definition of contractible inversion triple.

To prove (ii) ⇒ (i), it is enough by symmetry to treat the case where there is a root sequence r for w such that α+β covers α relative to ≤_{r}. We may assume that α and α + β appear consecutively in r = (r_{1}, …, r_{n}) (apply a sequence of short braid moves to r if necessary). In other words, we may assume the existence of an integer k satisfying r_{k} = α and r_{k+1} = α + β. Let (s_{1}, …, s_{n}) be the reduced expression corresponding to r. Parse this reduced expression as (u, s_{n−k}, s_{n−k+1}, v), and denote the images of u and v in W by u and v, respectively. For notational simplicity, write s for s_{n−k} and t for s_{n−k+1}. Then α = v^{−1}(α_{t}) and α + β = v^{−1}t(α_{s}). Note for future reference that t(α_{s}) = s(α_{t}) = α_{s} + α_{t}.

Contractibility of T will follow if we can produce a root sequence for ust of the form (v(α), v(α + β), v(β), …) = (α_{t}, t(α_{s}) = α_{s} + α_{t}, α_{s}, …). Observe that

v^{−1}(α_{s}) = v^{−1}t(α_{s}) − v^{−1}(α_{t}) = (α + β) − α = β ∈ Φ(w),

hence α_{s} ∈ Φ(ust), and consequently α_{t} = st(α_{s}) ∈ Φ(u). Thus, u has a reduced expression with last entry t, and this gives us a reduced expression for ust of the form (…, t, s, t). The latter corresponds to a root sequence with the required property.

The proof of (iii) ⇒ (i) proceeds along similar lines. We start with a root sequence r = (r_{1}, …, r_{n}) for w for which there is an index k satisfying r_{k} = α + β and r_{k+1} = β. We parse the reduced expression (s_{1}, …, s_{n}) corresponding to r as (u, s_{n−k}, s_{n−k+1}, v), denote the images of u and v in W as u and v, and write s for s_{n−k} and t for s_{n−k+1}. Then α + β = v^{−1}(α_{t}) and β = v^{−1}t(α_{s}).

We will be finished if we can show that v has a reduced expression with first entry s, say (s, x). For then, letting x denote the image in W of x, we would have

x^{−1}(α_{s}) = −x^{−1}sts(α_{t}) = −v^{−1}ts(α_{t}) = v^{−1}(α_{t}) − v^{−1}t(α_{s}) = (α + β) − β = α,

showing that α, α + β, β appear consecutively in some root sequence for w. An equivalent requirement is for v^{−1}(α_{s}) to be a negative root, and this follows because

v^{−1}(α_{s}) = v^{−1}(α_{s} + α_{t}) − v^{−1}(α_{t}) = v^{−1}t(α_{s}) − v^{−1}(α_{t}) = β − (α + β) = −α.

FREELY BRAIDED ELEMENTS IN COXETER GROUPS 9

The proof is complete. □

The next proposition will be needed in §4.1.

Proposition 3.2.2. Let w ∈ W. Let α, β ∈ Φ(w) be distinct and nonorthogonal. Suppose that there exist root sequences r and r′ for w such that α ≤_{r} β and β ≤_{r′} α. Then there is a contractible inversion triple of w containing both α and β.

Proof. The relation α ≤_{r} β implies that in r, the root α appears to the left of β; likewise, in r′ the root β appears to the left of α. Now, by Remark 3.1.3, r can be transformed into r′ by a sequence of long and short braid moves. Since α and β are nonorthogonal, they cannot both be involved in the same short braid move. Hence, there is a long braid move in our sequence of moves that involves both α and β. This implies the existence of a contractible inversion triple of w containing α and β. □

4. The statistic N(w) and free braidedness

Throughout this section, (W, S) will be of arbitrary simply laced type.

4.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. Let C ∈ C(w) and let ≤_{C} be the partial ordering of Φ(w) determined by C; this is well-defined by 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. (Note that α and β are comparable under ≤_{C}.)

Theorem 4.1.1. The map F_{w} is injective.

Proof. Let C and C′ be distinct root sequence commutation classes of w, and let ≤_{C} and ≤_{C′} be the respective partial orderings of Φ(w). By Proposition 3.1.5, these partial orderings do not agree. Hence, there exist nonorthogonal roots α, β ∈ Φ(w)

10 R.M. GREEN AND J. LOSONCZY

such that α <_{C} β and β <_{C′} α (note that any two nonorthogonal roots in Φ(w) are comparable under any given partial ordering arising from a commutation class of w). We now invoke Proposition 3.2.2 to deduce that α and β belong to some contractible inversion triple T of w. It is clear from the definition of F_{w} that F_{w}(C)(T) ≠ F_{w}(C′)(T). □

Theorem 4.1.1 has the following immediate Corollary 4.1.2. Every w ∈ W has at most 2^{N(w)} commutation classes, where N(w) denotes the number of contractible inversion triples of w. □ Remark 4.1.3. In [4], Elnitsky exhibits, in types A, B and D, a bijection from the set of all commutation classes of an arbitrary group element to a set of rhombic tilings of a polygon determined by that element. Bédard constructs in [1] a bijection from the set of all commutation classes of an arbitrary Weyl group element w to a certain set of functions from Φ(w) to the set of positive integers. 4.2 Freely braided elements and commutation classes.

In this section, we prove that the freely braided elements of Definition 2.2.1 achieve the bound of Corollary 4.1.2.

Given any v ∈ V, we denote by v^{⊥} the subspace {w ∈ V : B(v, w) = 0} of V. Lemma 4.2.1. Let w ∈ W have length at least 3, and let α_{1}, α_{2}, α_{3} ∈ Φ(w) be distinct. Suppose that r and r′ are root sequences for w such that α_{2} appears between α_{1} and α_{3} in r but not in r′. Then either α_{2}^{⊥} ∩ {α_{1}, α_{3}} ≠ ∅ or else there is a contractible inversion triple of w containing α_{2} and one of α_{1}, α_{3}. Proof. By Remark 3.1.3, it is possible to transform r into r′ using short and long braid moves. Consideration of such a sequence of moves yields the result. □ Lemma 4.2.2. Let w ∈ W be freely braided, and let T = {α, α + β, β} be a contractible inversion triple of w. Suppose that

(…, α, γ_{1}, γ_{2}, …, γ_{k}, α + β, δ_{1}, δ_{2}, …, δ_{m}, β, …)

is a root sequence for w. Then each root γ_{i} is orthogonal to α, and each root δ_{i} is orthogonal to β. Proof. First assume toward a contradiction that γ_{1} is not orthogonal to α. We apply Lemma 4.2.1 with α_{1} = α, α_{2} = γ_{1} and α_{3} = α + β. Because T is contractible,

FREELY BRAIDED ELEMENTS IN COXETER GROUPS 11

there is a root sequence for w in which γ_{1} does not appear between the roots α and α + β. Further, since w is freely braided, and since γ_{1} does not lie in T, it cannot be the case that γ_{1} belongs to a contractible inversion triple containing either α or α + β. Lemma 4.2.1 then implies γ_{1}^{⊥} ∩ {α, α + β} ≠ ∅. But γ_{1} is not orthogonal to α by assumption; hence, γ_{1}⊥(α + β). This in turn implies that γ_{1} is not orthogonal to β. Apply Lemma 4.2.1 again with α_{1} = α, α_{2} = γ_{1} and α_{3} = β, and use the same reasoning to show γ_{1}⊥β. This is a contradiction.

An induction on k now shows that the γ_{i} are all orthogonal to α, and an analogous argument handles the δ_{i}. □

The following theorem and its corollary provide some justification for the terminology “freely braided element”.

Theorem 4.2.3. Let w ∈ W be freely braided. Then there is a root sequence r for w such that the roots in any given contractible inversion triple of w appear consecutively in r. Furthermore, every root sequence for w is commutation equivalent to such a root sequence r.

Proof. Let r′ be an arbitrary root sequence for w, and let T = {α, α + β, β} be a contractible inversion triple of w. By Remark 2.2.2 and symmetry, we may assume that in r′, the root α appears to the left of α + β, which in turn appears to the left of β. According to Lemma 4.2.2 and Proposition 3.1.1(a), there is a sequence of short braid moves that transforms r′ into a root sequence r′′ for w in which α, α + β and β appear consecutively in that order.

The conclusion of the theorem follows from the above by an induction on the number of contractible inversion triples. The crucial point to notice is that if T′ is a consecutively occurring contractible inversion triple in r′, then the sequence of short braid moves of the preceding paragraph may be chosen so that the roots occurring in T′ remain consecutive in r′′. This can be arranged because w is freely braided. □

Corollary 4.2.4. If w ∈ W is freely braided, then w has precisely 2^{N(w)} commutation classes of root sequences, where N(w) is the number of contractible inversion triples of w.

Proof. In view of Corollary 4.1.2, it suffices to show that w has at least 2^{N(w)}

12 R.M. GREEN AND J. LOSONCZY

commutation classes. Theorem 4.2.3 guarantees the existence of a root sequence r for w in which the elements of each contractible inversion triple occur consecutively; moreover, the contractible inversion triples in r are disjoint as w is freely braided. Consequently, F_{w} is surjective, and the conclusion follows. □

The above corollary translates via Remark 3.1.3 into an equivalent statement about commutation classes of reduced expressions for w. 4.3 Commutation graphs.

Let w ∈ W. The commutation graph of w, G(w), is defined to be the graph with vertex set C(w) and with edge set consisting of all pairs {C, C′} of commutation classes with the following property: there exist representatives r ∈ C and r′ ∈ C′ such that r and r′ differ only by a single long braid move.

We define the parity of each commutation class C ∈ C(w) to be the number (−1)^{M(C)}, where M(C) = ∑_{T ∈I(w)} F_{w}(C)(T). Note that the parity of a commutation class depends on the map F_{w}, which in turn depends on the relation ⪯. Proposition 4.3.1. Let w ∈ W. Then the graph G(w) is bipartite. Proof. Let {C, C′} be an edge of G(w). By the definition of edge and Remark 2.2.2, there is precisely one T ∈ I(w) such that F_{w}(C)(T) ≠ F_{w}(C′)(T). Hence, the classes C and C′ have unequal parity. □ Remark 4.3.2. Let Γ be the Coxeter graph of (W, S). If Γ itself is bipartite, then Proposition 4.3.1 can be established using a simple argument counting the number of occurrences of each of the two types of generators in a reduced expression for w.

5. Type A

For the remainder of this paper, we shall assume that (W, S) is of type A. It will be convenient to work with a particular realization of (W, S), under which W is the group S_{n} of permutations of {1, …, n}, and S is the set of simple transpositions s_{1} = (1, 2), …, s_{n−1} = (n − 1, n). Let ε_{1}, …, ε_{n} be the standard basis of ℝ^{n}, and let ⟨·, ·⟩ be the inner product on ℝ^{n} satisfying ⟨ε_{i}, ε_{j}⟩ = δ_{ij}. Allow S_{n} to act on ℝ^{n} by permuting the indices of ε_{1}, …, ε_{n}, and set α_{i} = ε_{i} − ε_{i+1} (i = 1, …, n − 1). Then the vectors α_{1}, …, α_{n−1} may be regarded as the simple roots corresponding to s_{1}, …, s_{n−1}, and the form \frac{1}{2}⟨·, ·⟩ may be regarded as the Coxeter form B. With these identifications, we have Φ = {ε_{i} − ε_{j} : i ≠ j} and Φ^{+} = {ε_{i} − ε_{j} : i < j}.

FREELY BRAIDED ELEMENTS IN COXETER GROUPS 13

Let w ∈ S_{n}. By the “1-line notation” for w, we shall mean the string of numbers w(1) ⋯ w(n). Let (i, j) be a (not necessarily simple) transposition in S_{n}, with i < j. Note that the 1-line notation for the product w(i, j) can be obtained from that for w by interchanging the numbers in positions i and j. Further, we have ℓ(w(i, j)) < ℓ(w) ⇔ w(i) > w(j) ⇔ ε_{i} − ε_{j} ∈ Φ(w).

The set of inversion triples of any permutation w ∈ S_{n} can be read off of the 1-line notation for w. Specifically, a triple {ε_{i} − ε_{j}, ε_{i} − ε_{k}, ε_{j} − ε_{k}} of positive roots is an inversion triple of w if and only if w(i) > w(j) > w(k).

5.1 Contractibility in type A.

The following proposition stands in contrast to Example 2.2.3.

Proposition 5.1.1. Let w ∈ S_{n}. Then every inversion triple of w is contractible.

Proof. We argue by induction on m = ℓ(w). The assertion is vacuously true if 0 ≤ m < 3. Suppose that m ≥ 3 and that w has at least one inversion triple. Let T = {ε_{i} − ε_{j}, ε_{i} − ε_{k}, ε_{j} − ε_{k}} be an inversion triple of w.

Consider the situation where there is a positive integer l < n such that {l, l+1}∩ {i, j, k} = ∅ and w(l) > w(l+1). Then ℓ(ws_{l}) < ℓ(w), and T is an inversion triple of ws_{l}. By the inductive hypothesis, T is contractible relative to ws_{l}. If (r_{1}, …, r_{m−1}) is any root sequence for ws_{l} in which the elements of T appear consecutively, then (α_{l}, s_{l}(r_{1}), …, s_{l}(r_{m−1})) is a root sequence for w in which the elements of T appear consecutively, since s_{l} fixes the elements of T pointwise.

We may therefore assume that w(l) < w(l + 1) for every positive integer l < n such that {l, l + 1} ∩ {i, j, k} = ∅.

Suppose that i < j − 1. Since w(i) > w(j), the previous paragraph implies that either w(i) > w(i + 1) or w(j − 1) > w(j). Suppose for the moment that w(i) > w(i+1). Then ℓ(ws_{i}) < ℓ(w), and the set T′ = {ε_{i+1} −ε_{j}, ε_{i+1} −ε_{k}, ε_{j} −ε_{k}} is an inversion triple of ws_{i}. By the inductive hypothesis, T′ is contractible relative to ws_{i}. If (r_{1}, …, r_{m−1}) is any root sequence for ws_{i} in which the elements of T′ appear consecutively, then (α_{i}, s_{i}(r_{1}), …, s_{i}(r_{m−1})) is a root sequence for w in which the elements of T appear consecutively.

Similar reasoning handles the case where w(j − 1) > w(j). The induction step is therefore proved for i < j − 1.

If j < k − 1, then one argues in a similar way. It remains to deal with the case

14 R.M. GREEN AND J. LOSONCZY

where j = i + 1 and k = j + 1. Here, the element w has a reduced expression of the form (…, s_{i}, s_{i+1}, s_{i}), and it is clear that the first three entries of the corresponding root sequence belong to T. □

Let w ∈ S_{n} and let v ∈ S_{k}, where k ≤ n. Suppose that there do not exist i_{1}, …, i_{k} ∈ {1, …, n} with i_{1} < ⋯ < i_{k} such that the numbers w(i_{1}), …, w(i_{k}) are in the same relative order as v(1), …, v(k). Then one says that w “avoids the pattern” v(1) ⋯ v(k). It can be deduced from Proposition 5.1.1 and the discussion that precedes it that a given permutation is freely braided if and only if it avoids each of the four patterns 3421, 4231, 4312 and 4321.

5.2 Converse to Corollary 4.2.4 in type A.

Let w ∈ S_{n}. Let T be a nonempty subset of I(w), the set of all (contractible) inversion triples of w. We say that the map F_{w} of §4.1 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 a nonempty subset of I(w), then F_{w} is not surjective.

The following theorem is a partial converse to Corollary 4.2.4. Its proof relies on Proposition 5.1.1, which, as was observed in Example 2.2.3, does not hold for all simply laced Coxeter systems.

Theorem 5.2.1. Suppose that w ∈ S_{n} has 2^{N(w)} inversion triples. Then w is freely braided.

Proof. Assume toward a contradiction that there is a non-freely-braided w ∈ S_{n} with 2^{N(w)} inversion triples (all of which must be contractible by Proposition 5.1.1). In other words, w is non-freely-braided and F_{w} is surjective. Let ε_{i} − ε_{j} be an element of Φ(w) that belongs to at least two inversion triples of w, and assume that j − i is as large as possible relative to this property. Let T and T′ be distinct inversion triples of w containing ε_{i} − ε_{j}. By symmetry, there are six cases to consider.

Case 1. ε_{j} − ε_{k} ∈ T and ε_{j} − ε_{l} ∈ T′, where i < j < k < l. Observe that ε_{k}−ε_{l} ∉ Φ(w). Otherwise, the root ε_{i}−ε_{l} would belong to at least two inversion triples of w, namely {ε_{i} − ε_{k}, ε_{i} − ε_{l}, ε_{k} − ε_{l}} and {ε_{i} − ε_{j}, ε_{i} − ε_{l}, ε_{j} − ε_{l}}, contradicting our choice of ε_{i} − ε_{j}.

By Proposition 5.1.1 and Remark 2.2.2, there is a root sequence for w of the

FREELY BRAIDED ELEMENTS IN COXETER GROUPS 15

form

(…, ε_{i} − ε_{j}, ε_{i} − ε_{k}, ε_{j} − ε_{k}, …, ε_{i} − ε_{l}, …, ε_{j} − ε_{l}, …) or
(…, ε_{j} − ε_{l}, …, ε_{i} − ε_{l}, …, ε_{i} − ε_{j}, ε_{i} − ε_{k}, ε_{j} − ε_{k}, …).

Since ε_{k} − ε_{l} ∉ Φ(w), and since ε_{i} − ε_{k} and ε_{i} − ε_{l} are not orthogonal, these last two roots maintain their positions relative to one another in every root sequence for w. If ε_{i} − ε_{k} lies always to the left of ε_{i} − ε_{l}, then ε_{i} − ε_{j} cannot at the same time lie to the left of ε_{i} − ε_{k} and to the right of ε_{i} − ε_{l}. A similar statement can be made if ε_{i} − ε_{k} lies always to the right of ε_{i} − ε_{l}. It follows that F_{w} does not separate {T, T′}.

Case 2. ε_{k} − ε_{i} ∈ T and ε_{l} − ε_{i} ∈ T′, where k < l < i < j. One argues as in Case 1.

Case 3. ε_{k} − ε_{i} ∈ T and ε_{j} − ε_{l} ∈ T′, where k < i < j < l. Note that ε_{k}−ε_{j} ∈ T ⊆ Φ(w). Since both ε_{k}−ε_{i} and ε_{j}−ε_{l} also lie in Φ(w), the root ε_{k} −ε_{j} belongs to at least two inversion triples of w, namely {ε_{k} −ε_{j}, ε_{k} −ε_{l}, ε_{j} −ε_{l}} and {ε_{k} − ε_{i}, ε_{k} − ε_{j}, ε_{i} − ε_{j}}. This contradicts our choice of ε_{i} − ε_{j}.

Case 4. ε_{i} − ε_{k} ∈ T and ε_{j} − ε_{l} ∈ T′, where i < k < j < l. We have ε_{k} − ε_{j} ∈ T ⊆ Φ(w). Hence, ε_{k} − ε_{l} = (ε_{k} − ε_{j}) + (ε_{j} − ε_{l}) ∈ Φ(w). It follows that ε_{i} − ε_{l} belongs to at least two inversion triples of w, namely T′ and {ε_{i} − ε_{k}, ε_{i} − ε_{l}, ε_{k} − ε_{l}}, contradicting our choice of ε_{i} − ε_{j}.

Case 5. ε_{k} − ε_{i} ∈ T and ε_{l} − ε_{j} ∈ T′, where k < i < l < j. One argues as in Case 4.

Case 6. ε_{i} − ε_{k} ∈ T and ε_{l} − ε_{j} ∈ T′, where i < k < l < j. Here, we have T = {ε_{i} − ε_{k}, ε_{i} − ε_{j}, ε_{k} − ε_{j}} and T′ = {ε_{i} − ε_{l}, ε_{i} − ε_{j}, ε_{l} − ε_{j}}. Suppose first that ε_{k} − ε_{l} ∉ Φ(w). Then the roots ε_{i} − ε_{k} and ε_{i} − ε_{l}, which are not orthogonal, maintain their positions relative to one other in every root sequence for w. It follows that F_{w} does not separate {T, T′}.

Finally, suppose that ε_{k} −ε_{l} ∈ Φ(w). Then the sets T′′ = {ε_{k} −ε_{l}, ε_{k} −ε_{j}, ε_{l} −ε_{j}} and T′′′ = {ε_{i} −ε_{k}, ε_{i} −ε_{l}, ε_{k} −ε_{l}} are both inversion triples of w. We claim that F_{w} does not separate {T, T′′, T′′′}. To see this, observe that if C is a commutation class of w relative to which ε_{i} − ε_{k} lies to the left of ε_{k} − ε_{j} (this determines F_{w}(C)(T)) and ε_{k} − ε_{j} lies to the left of ε_{k} − ε_{l} (this determines F_{w}(C)(T′′)), then ε_{i} − ε_{k} lies to the left of ε_{k} − ε_{l} (so that F_{w}(C)(T′′′) is also determined). □

Note added in proof. The authors have found a proof that the converse of

Corollary 4.2.4 holds for arbitrary simply laced Coxeter systems.

References

[1] R. Bédard, On commutation classes of reduced words in Weyl groups, Europ. J. Combinatorics 20 (1999), 483–505.

[2] A. Björner, Orderings of Coxeter groups, Contemporary Math., vol. 34, 1984, pp. 175–195.

[3] N. Bourbaki, Groupes et algèbres de Lie, Chapitres 4, 5, et 6, Masson, Paris, 1981.

[4] S. Elnitsky, Rhombic tilings of polygons and classes of reduced words in Coxeter groups, J. Combin. Theory Ser. A 77 (1997), 193–221.

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

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

[10] G.X. Viennot, Heaps of pieces, I: basic definitions and combinatorial lemmas, Combinatoire Énumérative, ed. G. Labelle and P. Leroux, Springer-Verlag, Berlin, 1986, pp. 321–350.