A note on words in braid monoids

Jean Michel

The purpose of this note is to give a self-contained (apart from simple facts about Coxeter groups) and we hope a bit shorter and more understandable account of some results of [Charney1] and [Charney2] on normal forms of braids which are themselves based on papers by [Deligne1] and [Thurston]. In particular a motivation was to give a proof of 5.1 that we use in [Broué-Michel]. Some proofs and results from section 2 onwards seem to be new. I thank several people for improvements from earlier versions of the manuscript: M. Geck for pointing out some errors, F. Digne for pointing out that some results don’t need the braid group to be of finite type, and J.-Y. Hée for suggesting (and providing) further improvements in that direction.

Let W be a Coxeter group with presentation

<s ∈ S | s^{2} = 1(quadratic relations), \underbrace{sts ⋯}_{m_{st} factors} = \underbrace{tst ⋯}_{m_{st} factors} (braid relations)>

where S is a finite set and M = (m_{st})_{s,t∈S} is a symmetric matrix of positive integers with m_{ss} = 1 and m_{st} > 1 if s ≠ t; it is allowed that m_{s,t} = ∞, in which case we impose no braid relation linking s and t. The Artin-Tits braid group B associated to W is the group defined by the presentation

<s ∈ S | \underbrace{sts ⋯}_{m_{st} factors} = \underbrace{tst ⋯}_{m_{st} factors} for s, t ∈ S, s ≠ t>.  (∗)

We say that B is of finite type if M is chosen so that W is a finite group. We denote by B^{+} the monoid defined by presentation (*); if B is of finite type, we shall see in 3.2 that B^{+} can be identified to the submonoid of B generated by S.

1. The section B_{red}^{+}.

The relations defining B^{+} being homogeneous (i.e. both sides have same length), for b ∈ B^{+} there is a natural length function l(b) defined as the length of any expression of b as a product of elements of S. There is also a natural length function on W, which we denote again by l, defined by the length of a minimal expression as a product of elements of S. It is known (cf. e.g. [Bourbaki, §1 ex.13 b)]) that two minimal expressions for an element of W are equivalent by using only the braid relations. This implies that the natural quotient map p : B^{+} → W has a canonical section (as a map of sets) whose image B_{red}^{+} consists of those elements of B^{+} which have same length as their image in W. It also implies:

1.1. Proposition. B^{+} has the following presentation:

(i) As a set of generators we take B_{red}^{+} (considered as an abstract set of generators endowed with a bijection p : B_{red}^{+}⟶^{∼}W).

(ii) For relations we take ab = c whenever a, b, c ∈ B_{red}^{+} are such that the relation p(a)p(b) = p(c) holds in W, with l(p(a)) + l(p(b)) = l(p(c)).

More convenient for us will be the following equivalent construction of B^{+}:

1.2. Proposition. B^{+} can be identified with the set of sequences of elements of B_{red}^{+}, quotiented by the equivalence relation which is the transitive closure of: the sequences (g_{1}, …, g_{i−1}, g_{i}, g_{i+1}, …, g_{n}) and (g_{1}, …, g_{i−1}, a, b, g_{i+1}, …, g_{n}) are equivalent whenever ab = g_{i} is a relation in 1.1(ii).

The identification above is by the product (g_{1}, …, g_{n}) ↦ g_{1} … g_{n} ∈ B^{+}. We will call (g_{1}, …, g_{n}) a decomposition of length n of the braid element g_{1} … g_{n}. For g ∈ B^{+}, we define ν(g) as being the minimal n such that g has a decomposition of length n (thus ν(g) = 0 if and only if g = 1 and ν(g) = 1 if and only if g ∈ B_{red}^{+}).

In what follows, properties of B^{+} will be proved by first establishing them on B_{red}^{+}, where they will in a further step be reduced to properties of W via the bijection p :

B_{red}^{+}⟶^{∼}W.

We denote by ≺ divisibility on the left in B^{+} (that is, for a, b ∈ B^{+}, we have a≺b if and only if there exists c ∈ B^{+} such that b = ac), and we denote similarly by ≻ divisibility on the right. From the inequality l(a) + l(b) ≥ l(ab) which holds in W, it follows that if a≺b, b ∈ B_{red}^{+} then also a ∈ B_{red}^{+}. We also note

1.3. Remark. Elements of B_{red}^{+} are cancellable, that is, if a ∈ B^{+} , b, c ∈ B_{red}^{+} and ab = ac ∈ B_{red}^{+} or ba = ca ∈ B_{red}^{+} then b = c.

Proof: Obvious, since then b and c have same image in W.

For s, t ∈ S such that m_{s,t} < ∞ we denote by Δ_{{s,t}} the element of B^{+} which appears on both sides of the braid relation involving s and t.

The following lemma is adapted from [Deligne1, 1.14].

1.4. Lemma. Let M be a finite set of elements of B^{+} such that:

(i) If b ∈ M, a ∈ B^{+}, a≺b then a ∈ M. (ii) If a ∈ B^{+}, s, t ∈ S, as, at ∈ M then m_{s,t} < ∞ and aΔ_{{s,t}} ∈ M.

Then there exists g ∈ M such that M = {a ∈ B^{+} | a≺g}.

Proof: Let g be an element of maximal length in M. We will prove by contradiction that every element of M divides g. If it were not the case, we can find some a≺g, s ∈ S such that as ∈ M, as ⊀g (take an element x ∈ M, x ⊀g, and take for a any maximal (for ≺) divisor of x which divides g). We consider such an a of maximal length and derive a contradiction by constructing a longer one. Since a≺g and l(a) < l(g) (since l(a) < l(as) ≤ l(g) by maximality of l(g)), there exists t ∈ S such that at≺g (and t ≠ s). Thus at ∈ M and by (ii) we have aΔ_{{s,t}} ∈ M. Since as≺aΔ_{{s,t}}, we cannot have aΔ_{{s,t}}≺g. So there exists some v≺Δ_{{s,t}} such that at≺av, av≺g and there exists r ∈ S equal to either s or t such that avr≺aΔ_{{s,t}}, avr ⊀g, whence the contradiction.

For a ∈ B^{+} we put L(a) = {s ∈ S | s≺a} and R(a) = {s ∈ S | a≻s}. For w ∈ W we also define L(w) = {s ∈ S | l(sw) < l(w)} and R(w) = {s ∈ S | l(ws) < l(w)} (the definitions agree on B_{red}^{+}).

1.5. Proposition. Let a ∈ B_{red}^{+}, and s, t ∈ L(a). Then Δ_{{s,t}}≺a.

Proof: We only have to check this property in W where it is well known: write p(a) = vv′ where v is an element of the parabolic subgroup W_{{s,t}} of W generated by s and t and v′ is {s, t}-reduced — i.e. L(v′) ∩ {s, t} = ∅. Then v is an element of W_{{s,t}} such that L(v) = {s, t}; there exists such an element if and only if the group W_{{s,t}} is finite (equivalently m_{s,t} < ∞) and then the only such element is p(Δ_{{s,t}}), the longest element of W_{{s,t}}.

1.6. Proposition. Let a, b ∈ B_{red}^{+}. There exists a unique maximal (for the partial order ≺) c ∈ B_{red}^{+} such that c≺a and c≺b (we will call c the g.c.d. of a and b and denote c = a ∧ b).

Proof: It is enough to show that the set c ∈ B^{+}, c≺a and c≺b satisfies the hypotheses of lemma 1.4: (i) is obvious; to see (ii), since B_{red}^{+} has the left cancellation property (1.3), it is enough to show that if a ∈ B_{red}^{+}, s, t ∈ S, s≺a, t≺a then Δ_{{s,t}}≺a. But this is just the statement of 1.5.

Note that the above construction of a ∧ b shows that the operation ∧ is associative.

1.7. Proposition/Definition. Let a, b ∈ B_{red}^{+}. There exists a unique maximal c≺b such ac ∈ B_{red}^{+}. In this situation, we define two elements of B_{red}^{+}: we put α_{2}(a, b) = ac and ω_{2}(a, b) =the unique d such that b = cd (thus we have ab = α_{2}(a, b)ω_{2}(a, b)).

Proof: In order to check that the set of c such that c≺b and ac ∈ B_{red}^{+} satisfies the assumptions of 1.4, the only new thing we have to check is that if a ∈ B^{+}, s, t ∈ S, as, at ∈ B_{red}^{+} and m_{s,t} < ∞ then aΔ_{{s,t}} ∈ B_{red}^{+} (we know that m_{s,t} < ∞ since we are in a case where s and t divide some tail of c). Again this is a verification in W: a must be {s, t}-reduced, thus adds to Δ_{{s,t}}.

Note also that it follows from 1.3 that ω_{2}(a, b) is unique.

Before extending them to the whole of B^{+}, we check some properties of α_{2} and ω_{2}.

1.8. Proposition. Let a, b, c, ab ∈ B_{red}^{+}. Then α_{2}(ab, c) = α_{2}(a, α_{2}(b, c)).

Proof: By definition α_{2}(b, c) is of the form by with y≺c, so α_{2}(a, α_{2}(b, c)) is of the form aby′ ∈ B_{red}^{+} with y′≺y≺c, so aby′≺α_{2}(ab, c). Let α_{2}(ab, c) = abz. We thus have y′≺z≺c. But this implies y′ = z since bz ∈ B_{red}^{+}, bz≺bc so bz≺by = α_{2}(b, c) and since abz ∈ B_{red}^{+}, abz cannot be longer than aby′ = α_{2}(a, by).

1.9. Proposition. Let a, b, c, ab ∈ B_{red}^{+}. Then ω_{2}(ab, c) = ω_{2}(a, α_{2}(b, c))ω_{2}(b, c).

Proof: We first notice that, using 1.8 and 1.7, both sides have the same value when multiplied on the left by α_{2}(ab, c). This implies that the equality holds when projected to W, and by 1.3 it will hold in B^{+} if we show that the right-hand side is in B_{red}^{+}. But this results from the fact that the equality holds in W and that (since it holds when multiplied by α_{2}(ab, c)) we have l(ω_{2}(ab, c)) = l(ω_{2}(a, α_{2}(b, c))) + l(ω_{2}(b, c)).

2. Cancellability in B^{+}.

We first define a function α on B^{+}, which extends α_{2}, considered as a function defined on those g ∈ B^{+} such that ν(g) = 2. The following proof of the existence of α is inspired by [Thurston].

2.1. Proposition. There is a unique function α : B^{+} → B_{red}^{+} which is the identity on B_{red}^{+}, is such that α(ab) = α_{2}(a, b) for a, b ∈ B_{red}^{+} and is such that α(gh) = α(gα(h)) for all g, h ∈ B^{+}. Further, α(g) is the unique maximal (for ≺) element in the set {c ∈ B_{red}^{+} | c≺g}.

Proof: We define recursively (by induction on n) a function α on decompositions of length n of elements of B^{+}, considered just as sequences. We first define it on decompositions of length≤ 1 by α(()) = 1, α((a)) = a, and for longer decompositions we set α((g_{1}, …, g_{n})) = α_{2}(g_{1}, α((g_{2}, …, …, g_{n}))). We claim that α induces a well-defined function on B^{+}. Indeed, in view of the equivalence relation 1.2 which we put on decompositions and the inductive definition of α, it is enough to check α_{2}(ab, c) = α_{2}(a, α_{2}(b, c)), which is the statement of 1.8.

It is clear that the α(g) we have thus defined for g ∈ B^{+} is maximal amongst divisors in B_{red}^{+} of g: if a≺g, a ∈ B_{red}^{+} then there exists a decomposition g = ag_{2} … g_{n} with g_{i} ∈ B_{red}^{+}, and α(g) = α(a, g_{2}, … g_{n}) is by construction a multiple of a.

Also if g, h ∈ B^{+} and ν(g) = 1 there is a decomposition of gh which starts with g so by construction we have α(gh) = α(gα(h)). We show by induction on ν(g) that this equality remains true for all g: if g = g′g′′ with g′ ∈ B_{red}^{+}, ν(g′′) = ν(g) − 1 then α(g′g′′h) = α(g′α(g′′h)) = α(g′α(g′′α(h))) where the first equality holds by the case ν = 1 and the second case by induction, and on the other hand α(g′g′′α(h)) = α(g′α(g′′α(h))) by using the case ν = 1.

The unicity of α is clear by construction.

We would like now to define ω(g) as the unique h such that g = α(g)h, but until we know that B^{+} has the left cancellation property we will not know the unicity of h, so we proceed differently.

2.2. Proposition. There is a unique function ω : B^{+} → B^{+} which maps B_{red}^{+} to 1, is such that ω(ab) = ω_{2}(a, b) for a, b ∈ B_{red}^{+} and is such that ω(gh) = ω(gα(h))ω(h) for all g, h ∈ B^{+}.

Proof: As for α, we define ω recursively on decompositions by setting ω((g_{1}, …, g_{n})) = ω_{2}(g_{1}, α(g_{2} … g_{n}))ω((g_{2}, …, g_{n})). This time, to check that this definition is compatible with the equivalence relation we put on decompositions, we must check that ω_{2}(ab, c) = ω_{2}(a, α(bc))ω_{2}(b, c), which is the statement of 1.9.

Again we have by definition ω(gh) = ω(gα(h))ω(h) when ν(g) = 1 and again by an easy induction on ν(g) this extends to all elements g.

We can now prove:

2.3. Proposition. Let g ∈ B^{+}. Then there is a unique y such that g = α(g)y, and this y equals ω(g).

Proof: We show by induction on the length of g that if y is any element such that g = α(g)y, then y = ω(g). Computing ω(g) according to 2.2 we get ω(g) = ω(α(g)α(y))ω(y).

Now, we have α(g) = α(α(g)y) = α(α(g)α(y)) by the defining property of α. Thus, in view of the definition of ω (c.f. 1.7) we have ω(α(g)α(y)) = α(y). Now, by induction (since the length of y is less than that of g) we have y = α(y)ω(y) thus we get ω(g) = y.

2.4. Proposition. The monoid B^{+} has the left and right cancellation property (ab = ac ⇒ b = c and ba = ca ⇒ b = c).

Proof: By symmetry, it is enough to check e.g., left cancellability. First by induction on ν(a) we notice that it is enough to prove cancellability for ν(a) = 1: if ν(a) > 1 we write a = a′a′′ with ν(a′) = 1, ν(a′′) < ν(a), thus ab = a′(a′′b), ac = a′(a′′c) and by the case ν = 1 we get a′′b = a′′c, from which we deduce by induction b = c.

So assume now a ∈ B_{red}^{+}. Then there is x ∈ B_{red}^{+}, x≺b, such that α(ab) = ax: indeed, by the formula α(ab) = α(aα(b)) we have α(ab) = ax where x≺α(b)≺b. Similarly x≺c. So there exists b′, c′ such that ab = (ax)b′ = (ax)c′. We then have b′ = c′ = ω(ab) by 2.3 whence b = xb′ = xc′ = c.

We are now in a position to extend 1.5 and 1.6 to the whole of B^{+}

2.5. Proposition. Let a ∈ B^{+}, and s, t ∈ L(a). Then Δ_{{s,t}}≺a.

Proof: If s, t ∈ L(a) then s≺α(a) and t≺α(a) so by 1.5 we have Δ_{{s,t}}≺α(a)≺a.

2.6. Proposition. Let a, b ∈ B^{+}. There exists a unique maximal (for the partial order ≺) c ∈ B^{+} such that c≺a and c≺b (we still denote c = a ∧ b).

Proof: Since B^{+} has the left cancellation property, we can just follow the proof of 1.6 using 2.5 instead of 1.5.

3. The center, and monoids of finite type.

If B is of finite type, W is finite thus has a unique longest element. We define Δ as the element of B_{red}^{+} such that p(Δ) is the longest element of W. We can in this case redefine α on B^{+} by α(g) = Δ ∧ g.

3.1. Proposition. Assume B of finite type. There is an automorphism g ↦ \overline{g} of order 2 of B^{+} defined by Δg = \overline{g}Δ. This automorphism preserves S.

Proof: It is sufficient to prove that there is an involution s ↦ \overline{s} of S such that Δs = \overline{s}Δ. It is well known (cf. e.g. [Bourbaki, §1 ex.22]) that the same property holds in W, i.e. that for s ∈ S there exists \overline{s} ∈ S such that p(s)p(Δ) = p(Δ)p(\overline{s}), and \overline{\overline{s}} = s. But p(s) is of order 2, so if w′ ∈ B_{red}^{+} is defined by p(w′) = p(s)p(Δ), we have Δ = sw′ = w′\overline{s}, thus sΔ = sw′\overline{s} = Δ\overline{s}.

3.2. Corollary. Assume B of finite type. The element π = Δ^{2} is central in B^{+}. The monoid B^{+} injects in B, and for any b ∈ B, there exists i > 0 such that π^{i}b ∈ B^{+}. Any element g ∈ B can be written uniquely as x^{−1}y, where x, y ∈ B^{+} have no common divisor.

Proof: The first assertion is clear from 3.1. To see the second one, notice that any x ∈ B_{red}^{+} divides Δ, thus in particular divides π. It results by induction on n that if we write x ∈ B^{+} as x_{1} … x_{n}, with x_{i} ∈ B_{red}^{+}, then x≺π^{n}: indeed, x_{2} … x_{n}≺π^{n−1} so x≺x_{1}π^{n−1} = π^{n−1}x_{1}≺π^{n−1}π = π^{n}. It follows that every two elements of B^{+} have a common multiple (some power of π), thus by 2.4 B^{+} satisfies the Öre condition and thus injects in B. The group B can be identified with the group of fractions of the monoid B^{+}; in particular every element of B is of the form x^{−1}y with x, y ∈ B^{+}. We have π^{i}x^{−1}y ∈ B^{+} for large enough i (such that x≺π^{i}); also the existence of the g.c.d. proves the unicity of such a decomposition with no common divisor.

Note that the existence of a g.c.d. implies that of an l.c.m.: given a, b ∈ B^{+} they have some common multiple (e.g. some power of π), so the set of elements which are common multiples of a and b has a g.c.d., which is the l.c.m. of a and b. We will denote a ∨ b the l.c.m.

The center of B^{+} can be determined in general using the following

3.3. Lemma. If w is central in B^{+} and s, t ∈ S are such that s≺w and st ≠ ts then t≺w.

Proof: Under the assumption of the lemma, s and t both divide wt = tw, thus if we define δ by Δ_{{s,t}} = tδ then δ≺w. Now st ≠ ts implies st≺δ≺w, so there exists x such that w = stx. Now sw = ws gives sstx = stxs and cancelling s we get w = stx = txs so t≺w.

This lemma implies that the center of B^{+} is generated by the Δ_{I}^{2} (or possibly Δ_{I} when the automorphism of 3.1 is trivial on W_{I}) where I runs over the connected components of the Coxeter diagram of W such that the parabolic subgroup W_{I} is finite.

4. Normal forms.

We say that a decomposition (g_{1}, …, g_{n}) is the normal form of g_{1} … g_{n} ∈ B^{+} if no g_{i} is equal to 1 and for any i we have g_{i} = α(g_{i} … g_{n}) (so g_{i+1} … g_{n} = ω(g_{i} … g_{n})).

4.1. Proposition (cf. [Charney1, 2.5]). The normality of a form can be seen locally: (g_{1}, …, g_{k}) is a normal form if and only if (g_{i}, g_{i+1}) is for all i. This implies that any segment (g_{i}, …, g_{j}) of a normal form is normal.

Proof: Indeed, using the formula α(gh) = α(gα(h)) we have for all i that α(g_{i} … g_{h}) = α(g_{i}g_{i+1}).

4.2. Corollary. A form (g_{1}, …, g_{k}) is normal if and only if for any i we have R(g_{i}) ⊃ L(g_{i+1}).

Thus we have a new, very convenient presentation of B^{+} (we don’t need to quotient by an equivalence relation):

4.3. Corollary. B^{+} can be identified to the set of sequences {(g_{1}, …, g_{k}), g_{i} ∈ W −{1} | R(g_{i}) ⊃ L(g_{i+1}) for any i}.

Let Γ be a group of diagram automorphisms of W (i.e., automorphisms of W which stabilize S). Then the set of fixed points W^{Γ} is still a Coxeter group, with Coxeter generating set the set of longest elements in the parabolic subgroups W_{O} where O runs over the orbits S/Γ such that the group W_{O} is finite (the idea of the proof is essentially due to Steinberg; see [Hée] or [Mühlherr] for a proof in the general case). In this situation, Γ acts naturally on B (by acting on the generators), and from 4.3 we get:

4.4. Corollary. In the above situation, (B^{+})^{Γ} identifies to the Braid monoid of W^{Γ}. If W is of finite type, B^{Γ} identifies to the Braid group of W^{Γ}.

Proof: By the unicity of α, a normal form (g_{1}, …, g_{k}) represents an element of (B^{+})^{Γ} if and only if all g_{i} ∈ W^{Γ}. The condition R(g_{i}) ⊃ L(g_{i+1}) translates to the same condition in W^{Γ}, whence the first part of the statement. For the second part, we just notice that if Δ^{−n}b ∈ B^{Γ}, with b ∈ B^{+}, then since Δ is Γ-fixed we must have b ∈ (B^{+})^{Γ}; and Δ is also the lift to the braid monoid of W^{Γ} of the longest element of W^{Γ}.

We note that at this stage we can show easily (following [Deligne1, 4.24]):

4.5. Corollary. Assume that B is of finite type. Then x, y ∈ B^{+} are conjugate under B if and only if there exists a_{1}, …, a_{k} ∈ B_{red}^{+} such that x_{1} = x, x_{k+1} = y and x_{i}a_{i} = a_{i}x_{i+1}. In particular the conjugacy problem in B is decidable.

Proof: Multiplying a conjugating element by a suitable power of π we may assume that x and y are conjugate by some a ∈ B^{+}, so that xa = ay. So α(a)≺xa, which implies by the defining property of α that α(a)≺xα(a), so x_{1} = α(a)^{−1}xα(a) is in B^{+}. We take a_{1} = α(a), x_{2} = a_{1} ∈ x_{1}a_{1} and we go on in this way taking a_{2}, …, a_{k} such that (a_{1}, …, a_{k}) is the normal form of a.

4.6. Lemma (cf. [Charney1, 3.1). Let w ∈ B_{red}^{+} and (g_{1}, …, g_{k}) be the normal form of g ∈ B^{+}. Then we can write g_{1} = g′_{1}g′′_{1}, …, g_{k} = g′_{k}g′′_{k} such that the normal form of wg is (wg′_{1}, g′′_{1}g′_{2}, …, g′′_{i}g′_{i+1}, …, g′′_{k−1}g′_{k}, g′′_{k}) if g′′_{k} ≠ 1 and (wg′_{1}, g′′_{1}g′_{2}, …, g′′_{i}g′_{i+1}, …, g′′_{k−1}g′_{k}) if g′′_{k} = 1.

Proof: We apply repeatedly α(gh) = α(gα(h)): we start with α(wg) = α(wg_{1}) = wg′_{1} (this defines g′_{1} and g′′_{1} = g_{1}^{′−1}g_{1}), then α(g′′_{1}g_{1} … g_{k}) = α(g′′_{1}g_{2}) = … etc. . ..

4.7. Proposition. Let (g_{1} … g_{n}) be the normal form of g. Then n = ν(g).

Proof: We proceed by induction on ν(g). Let n(g) be the number of terms in the normal form of g. Let wh_{1} … h_{k} be a decomposition of g of length ν(g) (so that w, h_{1}, …, h_{k} are reduced and k = ν(g)−1). By induction we have n(h_{1} … h_{k}) = k. Let g_{1}..g_{k} be the normal form of h_{1}..h_{k}. Then by 4.6 we have n(g) ≤ k + 1. Since we cannot have n(g) < ν(g) we must have n(g) = k + 1 = ν(g).

Note that 4.6 can be rephrased: either ν(wg) = ν(g) and ω^{ν(wg)−1}(wg)≻ω^{ν(g)−1}(g) (when g′′_{k} = 1) or ν(wg) = ν(g) + 1 and ω^{ν(g)−1}(g)≻ω^{ν(wg)−1}(wg).

4.8. Proposition. For g, h ∈ B^{+} we have max(ν(g), ν(h)) ≤ ν(gh) ≤ ν(g) + ν(h)

Proof: This is clear by induction on ν(g), applying repreatedly 4.6.

4.9. Lemma. If g ∈ B^{+}, w ∈ B_{red}^{+} and ν(gw) > ν(g) then w≻ω^{ν(g)}(gw).

Proof: By induction on k = ν(g). If (g_{1}, …, g_{k}) is the normal form of g, then we must have ν(g_{2} … g_{k}w) > ν(g_{2} … g_{k}) otherwise ν(gw) could not be greater than ν(g). So the normal form of g_{2} … g_{k}w is by induction (x_{1}, …, x_{k}) where w≻x_{k}. By lemma 4.6 the last term of the normal form of g_{1}x_{1} … x_{k} is a right divisor of x_{k} (so of w) — otherwise we would have ν(gw) = ν(g_{1}x_{1} … x_{k}) = k, a contradiction.

4.10. Lemma. Let (g_{1}, …, g_{k}) be the normal form of g ∈ B^{+} and let x ∈ B^{+}, x≺g. Then ν(x) ≤ k and x≺g_{1} … g_{ν(x)}.

Proof: The fact that ν(x) ≤ k comes from e.g. 4.8. We prove the second part by induction on h = ν(x). We have x = x′w with ν(x′) = h − 1 and w ∈ B_{red}^{+}. By induction, there exists a ∈ B^{+} such that x′a = g_{1} … g_{h−1}, so g = x′ag_{h} … g_{k}. Therefore x = x′w≺g implies w≺ag_{h} … g_{k}. Since w ∈ B_{red}^{+} we get w≺α(ag_{h} … g_{k}) = α(aα(g_{h} … g_{k})) = α(ag_{h}), so w≺ag_{h} thus x = x′w≺x′ag_{h} = g_{1} … g_{h} q.e.d.

5. Charney’s results.

I would like to thank J.-Y. Hée for providing me the proof given below of 5.1 (as well as lemma 4.10 above, used along the way) which replaces my proof which needed to assume B of finite type.

5.1. Proposition. Let g ∈ B^{+}, w ∈ B_{red}^{+}; then ν(gw) = ν(g) if and only if ω^{ν(g)−1}(g)w ∈ B_{red}^{+}.

Proof: Let (g_{1}, …, g_{k}) be the normal form of g. We first notice that the “if” part, which says that g_{k}w ∈ B_{red}^{+} implies ν(gw) = ν(g), results from 4.8 which gives k = ν(g) ≤ ν(gw) ≤ ν(g_{1} … g_{k−1}) + ν(g_{k}w) = k.

Conversely, assume ν(gw) = k and let (h_{1}, …, h_{k}) be the normal form of gw. By 4.10, there exists a ∈ B^{+} such that g_{1} … g_{k−1}a = h_{1} … h_{k−1}. From g_{1} … g_{k−1}g_{k}w = h_{1} … h_{k−1}h_{k} = g_{1} … g_{k−1}ah_{k} we get g_{k}w≻h_{k}. Let α′ be the left l.c.m. of h_{k} and w, so there exists g′ such that g_{k}w = g′α′ and h′ such that α′ = h′h_{k}; let x = g_{1} … g_{k−1}g′. Then by construction g′≺g_{k}, thus x≺g; on the other hand xh′h_{k} = xα′ = gw = h_{1} … h_{k}, thus xh′ = h_{1} … h_{k−1}, so ν(x) ≤ k − 1 and by 4.10 we have x≺g_{1} … g_{k−1}, which implies g′ = 1 and g_{k}w = α′ ∈ B_{red}^{+} q.e.d.

5.1 can be rephrased as follows:

5.2. Proposition. If there exists i such that ν(ω^{i}(g)w) = ν(ω^{i}(g)) then for any i we have ν(ω^{i}(g)w) = ν(ω^{i}(g)).

Proof: If (g_{1}, …, g_{k}) is the normal form of g, we can rephrase 5.2 as: if there exists i such that k − i = ν(g_{i} … g_{k}w) then for any i we have k − i = ν(g_{i} … g_{k}w). By 5.1 applied to g_{i} … g_{k} and w, the hypothesis implies that g_{k}w ∈ B_{red}^{+} which in turn implies for any i (applying 5.1 to g_{i} … g_{k}) that ν(g_{i} … g_{k}w) = k.

The next proposition says a bit more than [Charney1, 3.3]. Note that it implies that the equality ν(ω^{i}(g)w) = ν(ω^{i}(g)) in 5.2 can be replaced by ν(ω^{i}(gw)) = ν(ω^{i}(g)).

5.3. Proposition. For any i, g ∈ B^{+} and w ∈ B_{red}^{+} then ω^{i+1}(gw) = ω(ω^{i}(g)w).

Proof: It is sufficient to check the proposition for i = 1. Indeed from the case i = 1: ω^{2}(gw) = ω(ω(g)w) and the case for i − 1: ω^{i}(gw) = ω(ω^{i−1}(g)w) we get ω^{i+1}(gw) = ω^{2}(ω^{i−1}(g)w) = ω(ω^{i}(g)w) which is the case for i.

We proceed by induction on k = ν(g). The result is clear for k ≤ 1. Assume k ≥ 2 and let (g_{1}, …, g_{k}) be the normal form of g. Assume first ν(gw) = k. Then by corollary 5.1 g_{k}w ∈ B_{red}^{+} which implies

ω^{2}((g_{1} … g_{k−1})(g_{k}w)) = ω(ω(g_{1} … g_{k−1})g_{k}w) = ω(g_{2} … g_{k}w) = ω(ω(g)w) q.e.d.

where the first equality is by the induction hypothesis. Otherwise let (η_{0}, …, η_{k}) be the normal form of gw. Then by 4.9 we have w≻η_{k}, say w = βη_{k}. Then g_{k}β must be in B_{red}^{+} else by 5.1 k = ν(η_{0} … η_{k−1} = g_{1} … g_{k}β) > ν(g_{1} … g_{k}) = k, a contradiction. We thus get by induction: η_{2} … η_{k−1} = ω^{2}(η_{0} … η_{k−1} = (g_{1} … g_{k−1})(g_{k}β)) = ω(g_{2} … g_{k−1}g_{k}β) so there exists a such that the normal form of g_{2} … g_{k}β is (a, η_{2}, …, η_{k−1}). If k > 2 this implies that (a, η_{2}, …, η_{k−1}, η_{k}) is the normal form of g_{2} … g_{k}w, since it verifies the local criterion for normality. Thus ω(g_{2} … g_{k}w) = η_{2} … η_{k} as we had to prove. If k = 2 it remains to prove that (a, η_{2}) is normal. In this case, let (a_{1}, a_{2}) be the normal form of aη_{2}. By definition η_{2}≻a_{2}. We have g_{1}a_{1}a_{2} = g_{1}aη_{2} = g_{1}g_{2}w = η_{0}η_{1}η_{2} so ν(g_{1}a_{1}a_{2}) > ν(a_{1}a_{2}) so by 4.6 a_{2}≻ω^{2}(g_{1}a_{1}a_{2}) = η_{2}. So a_{2} = η_{2} q.e.d.

References.

[Bourbaki] N. Bourbaki, Groupes et algèbres de Lie, Chap. 4,5 et 6, Masson (1981).

[Broué-Michel] M. Broué and J. Michel, Sur certains éléments réguliers des groupes de Weyl et les variétés de Deligne-Lusztig associées, “Finite reductive Groups”, Progress in Mathematics 141, 73–139 Birkhauser (1996).

[Charney1] R. Charney, Artin groups of finite type are biautomatic, Math. Ann. 292, 671–683 (1992).

[Charney2] R. Charney, Geodesic automation and growth functions for Artin groups of finite type, Math. Ann. 301, 307–324 (1995).

[Deligne1] P. Deligne, Les immeubles des groupes de tresses généralisés, Inventiones math. 17, 273–302 (1972).

[Deligne2] P. Deligne, Action du groupe des tresses sur une catégorie, Inventiones math. 128, 159–175 (1997).

[Hée] J.-Y. Hée, Systèmes de racines sur un anneau commutatif totalement ordonné, Geom. Dedicata 37, 65–102 (1991).

[Mühlherr] B. Mühlherr, “Coxeter groups in Coxeter groups”, in “finite geometry and combinatorics”, 277–287, London Math. Soc. Lecture Notes Ser. 191, Cambridge University press (1993).

[Thurston] W. Thurston, Braid groups, in D. Epstein, J. Cannon, D. Holt, S. Levy, M. Paterson, W. Thurston, Word Processing in Groups, Jones and Bartlett (1992).