REDUCED WORDS AND A LENGTH FUNCTION FOR G(e, 1, n)

Kirsten Bremke and Gunter Malle

M.I.T. and Universität Heidelberg

In the first part of this paper we study normal forms of elements of the imprimitive complex reflection group G(e, 1, n). This allows to prove a conjecture of Broué on basis elements and the canonical symmetrizing form of the associated cyclotomic Hecke algebra. Secondly we introduce a root system for G(e, 1, n) and study the associated length function. This has many properties in common with the usual length function for finite Weyl groups.

0. Introduction

We study normal forms and a length function for elements of the imprimitive complex reflection group W_{n} := G(e, 1, n). In the first part we show that any reduced expression in terms of a certain standard generating set of reflections of W_{n} can be brought into a normal form by using a very limited set of ’braid relations’. This then allows to verify a conjecture of Broué on basis elements in the associated cyclotomic Hecke algebra and to construct a canonical symmetrizing form on the cyclotomic algebra of any imprimitive complex reflection group.

In the second part we introduce a root system and an associated length function for W_{n} and study their properties. On a finite Weyl group W there exist two natural length functions, one defined by the length of reduced expressions in terms of the set of standard generators, the other by the action of W on the root system. It is a theorem that these two functions agree. Many properties of Weyl groups can be derived by using the second description of the length function. It turns out that for complex reflection groups the length function l defined by reduced expressions in terms of certain standard generators is not so well suited for the study of these groups. Instead we define a new length function coming from a generalized root system.

The general setup is the following. We let Φ be a set on which W_{n} acts, which is partitioned into two subsets Φ = Φ^{+} ∪ Φ^{−}. In our case Φ is closely related to sets of eigenvectors for reflections of W_{n} in its reflection representation. Further inside Φ^{+} we choose a subset Ω which is in bijection with the set of reflections of W_{n}. Then we call (Φ, Φ^{−}, Ω) a root system for W_{n}. The associated length function ℓ : W_{n} → ℕ_{0} is

Typeset by AMS-TEX

1991 Mathematics Subject Classification. 51F15, 20H15.

The second author gratefully acknowledges financial support by the Deutsche Forschungsgemeinschaft

defined by ℓ(w) := |w.Ω ∩ Φ^{−}|. The main result of the second part can be formulated as follows:

Theorem. There exists a root system (Φ, Φ^{−}, Ω) for W_{n} with associated length function ℓ with the following properties:

(a) ℓ(s) = 1 for all s in a certain set S of standard generators of W_{n}.

(b) The restriction of ℓ to the standard parabolic subgroups W_{J} = ⟨s ∈ J⟩ (for J ⊂ S) agrees with the corresponding length functions defined there.

(c) The polynomial ∑_{w∈W_{n}} q^{ℓ(w)} agrees with the Poincaré polynomial of W_{n}.

(d) In the case e = 2, when W_{n} is the real reflection group of type C_{n}, ℓ agrees with the usual length function on this Coxeter group.

It would be interesting to decide whether such root systems and length functions also exist for the other complex reflection groups.

1. Reduced words in G(e, 1, n)

Let V be the unitary space ℂ^{n} with the standard unitary inner product. Denote the standard basis vectors of V by e_{1}, …, e_{n}.

Fix e > 1, and let W_{n} = G(e, 1, n) ⊂ GL(V) be the imprimitive complex reflection group generated by the reflections s_{2}, …, s_{n} of order 2 with roots e_{2} − e_{1}, …, e_{n} − e_{n−1}, respectively, and a (complex) reflection t of order e with root e_{1}. On these generators, W_{n} has a presentation given by the diagram

(1.1)  C_{n}^{(e)}:  ◯_{t}_{e}  ◯_{s_{2}}  ◯_{s_{3}} ⋯ ◯_{s_{n}}

We study properties of reduced expressions of elements of W_{n} in this presentation. Such properties are of importance in the understanding of the cyclotomic algebra H(W_{n}) attached to W_{n}.

First note that the elements s_{2}, …, s_{n} generate a subgroup of W_{n} isomorphic to the symmetric group 𝔖_{n}, and can be identified with a set of standard generators of this Coxeter group. We need the following facts concerning the symmetric group 𝔖_{n}:

Lemma 1.2. (a) Let s_{i_{1}} ⋯ s_{i_{k}}, s_{j_{1}} ⋯ s_{j_{k}} be two reduced expressions of the same element w ∈ 𝔖_{n}. Then the two expressions can be transformed into one another by just using the braid relations.

(b) {1, s_{2}} is a set of double coset representatives of ⟨s_{3}, …, s_{n}⟩ ≅ 𝔖_{n−1} in 𝔖_{n}.

We write S := {t, s_{2}, …, s_{n}} for the set of chosen generators of W_{n}. It is easily checked by induction from the defining relations in W_{n} that

(1.3)  s_{2}t^{a}s_{2}t^{b} = t^{b}s_{2}t^{a}s_{2}  for all a, b ∈ ℤ.

Let M be the free monoid over the alphabet S modulo the braid relations described by (1.1), and M′ the factor of M by the relations (1.3). Two elements x = x_{1} ⋯ x_{l} and x′ = x′_{1} ⋯ x′_{l} with x_{i}, x′_{i} ∈ S in the free monoid over S will be called braidequivalent if they have the same image in M, and weakly braid-equivalent if they have the same image in M′, i.e., if one can be transformed into the other by application of just the braid relations between the x_{i} ∈ S together with the relation (1.3). We will often identify elements x = x_{1} ⋯ x_{l}, x_{i} ∈ S, in M and their images in M′ and W_{n}. An element x = x_{1} ⋯ x_{l} ∈ M is called a reduced expression for its image x in W_{n}, if the product of the images of the x_{i} is a reduced expression for x, i.e., if any other expression of x as product of generators s ∈ S has at least l factors. For such a reduced expression x = x_{1} ⋯ x_{l} of x we let l(x) := l.

For 1 ≤ k ≤ n, a ∈ ℤ, write

t_{k,a} := \{ \begin{matrix}s_{k} ⋯ s_{2}t^{a} & for a ≠ 0, \\ 1 & for a = 0. \end{matrix}

Lemma 1.4. For all a, b ≠ 0 we have in M′:

(a)  s_{i}t_{k,a} = \{ \begin{matrix}t_{k,a}s_{i} & if i > k + 1, \\ t_{k+1,a} & if i = k + 1, \\ t_{k,a}s_{i+1} & if i < k, \end{matrix}

(b)  t_{k,a}t_{k,b} = \{ \begin{matrix}t_{k−1,b}t_{k,a}s_{2} & if k > 1, \\ t_{1,a+b} & if k = 1, \end{matrix}

(c) t_{k+m,a}t_{k,b} = t_{k−1,b}t_{k+m,a}s_{2} for all k > 1, m ≥ 0.

Proof. The first part is immediate. We prove (b) by induction on k, the cases k = 1, 2 being obvious from (1.3). For k > 2 we have

t_{k,a}t_{k,b} = s_{k}t_{k−1,a}s_{k}t_{k−1,b} = s_{k−1}s_{k}t_{k−1,a}t_{k−1,b}

which by induction is equal to

s_{k−1}s_{k}t_{k−2,b}t_{k−1,a}s_{2} = t_{k−1,b}t_{k,a}s_{2}.

Finally by (a) and (b) we have

t_{k+m,a}t_{k,b} = s_{k+m} ⋯ s_{k+1}t_{k,a}t_{k,b} = s_{k+m} ⋯ s_{k+1}t_{k−1,b}t_{k,a}s_{2} = t_{k−1,b}t_{k+m,a}s_{2}

for a, b ≠ 0, k > 1 and m ≥ 0. Note that we only used the braid relations and (1.3), so the above identities already hold inside M′. □

Lemma 1.5. Let x = x_{1} ⋯ x_{k}, with x_{i} ∈ S, be a reduced expression. Then x is weakly braid-equivalent to a word of the form

(1.6)  t_{1,a_{0}} ⋯ t_{n,a_{n−1}}w,  where 0 ≤ a_{i} ≤ e − 1, w ∈ 𝔖_{n} reduced.

Moreover, the words of the shape (1.6) form a system of representatives of elements of W_{n}.

Proof. Let x be an arbitrary reduced expression of an element in W_{n}. Clearly we can write

x = w_{1}t^{a_{1}}w_{2}t^{a_{2}} ⋯ w_{l}t^{a_{l}}w_{l+1}

with w_{i} ∈ 𝔖_{n} and suitable l, a_{1}, …, a_{l}, where moreover w_{i} ∉ ⟨s_{3}, …, s_{n}⟩ ≅ 𝔖_{n−1} for 1 ≤ i ≤ l. By Lemma 1.2 the element w_{1} is braid-equivalent to one of the form w_{1,1}s_{2}w_{1,2} with s_{2} not occurring in w_{1,1} and w_{1,2}. Thus x is braid-equivalent to

w_{1,1}s_{2}t^{a_{1}}w_{1,2}w_{2}t^{a_{2}} ⋯ w_{l}t^{a_{l}}w_{l+1}.

Induction then yields that x is braid-equivalent to first

s_{k_{1}} ⋯ s_{2}t^{a_{1}}w′_{2}t^{a_{2}} ⋯ w_{l}t^{a_{l}}w_{l+1},

and then to

(1.7)  (s_{k_{1}} ⋯ s_{2}t^{a_{1}}) ⋯ (s_{k_{l}} ⋯ s_{2}t^{a_{l}})w = t_{k_{1},a_{1}} ⋯ t_{k_{l},a_{l}}w

for some w ∈ 𝔖_{n}. We may modify the form (1.7) for x by repeated application of Lemma 1.4(a)–(c), starting from the right, to obtain a weakly braid-equivalent expression with k_{1} < k_{2} < ⋯ < k_{l}, and thus by the definition of t_{k,0} the first assertion follows.

To prove the second part we just count the number of expressions of the form (1.6), which is clearly equal to e^{n}n! = |W_{n}|. Since we just showed that every reduced expression is weakly braid-equivalent to one of these normal forms, these must all be different. □

Incidentally, this shows that the length of any reduced expression in W_{n} is at most n(n + e − 2) and that there is a unique element of maximal length, viz.

t_{1,e−1} ⋯ t_{n,e−1}w_{0},

where w_{0} denotes the longest element of 𝔖_{n}.

Remark 1.8. If we enlarge the generating set for W_{n} by adding t^{−1} as a further generator, then the above arguments still apply to show that any expression of w ∈ W_{n} which is reduced with respect to S ∪ {t^{−1}} is weakly braid-equivalent to a word of the form

t_{1,a_{0}} ⋯ t_{n,a_{n−1}}w, where − e/2 < a_{i} ≤ e/2, w ∈ 𝔖_{n} reduced,

where clearly t^{a} is interpreted as (t^{−1})^{−a} for a < 0.

2. The symmetrizing form

In this section we define a canonical symmetrizing form on the cyclotomic Hecke algebra associated to G(e, 1, n) and thus on the Hecke algebra for any imprimitive complex reflection group.

2A. Basis elements in the cyclotomic algebra.

Let u = (u_{1,1}, …, u_{1,e}; u_{2,1}, u_{2,2}) be indeterminates and H(W_{n}, u) be the generic cyclotomic algebra attached to W_{n}, i.e., the free associative A := ℤ[u, u^{−1}]-algebra on generators T, S_{2}, …, S_{n}, subject to the braid relations implied by the diagram (1.1) and the deformed order relations

(T − u_{1,1}) ⋯ (T − u_{1,e}) = 0 = (S_{i} − u_{2,1})(S_{i} − u_{2,2}), 2 ≤ i ≤ n,

(see [3, 4.1]). We also write T = T_{t} and S_{i} = T_{s_{i}}. Under the specialization

(2.1)  u_{1,k} ↦ ζ_{e}^{k}, 1 ≤ k ≤ e,  u_{2,k} ↦ (−1)^{k}, 1 ≤ k ≤ 2,

where ζ_{e} := exp(2πi/e), the cyclotomic algebra specializes to the group algebra of W_{n}. Further, it is known that H is a free A-algebra of rank |W_{n}| (see [2]). For x = x_{1} ⋯ x_{l}, x_{i} ∈ S, a reduced expression in W_{n}, let T_{x} := T_{x_{1}} ⋯ T_{x_{l}}. It is not in general true that if two reduced expressions x, x′ describe the same element in W_{n}, then the corresponding elements T_{x}, T_{x′} coincide in H. Nevertheless, a somewhat weaker statement, which was first suggested by Michel Broué, can be shown to hold true.

For this we record the following analogue of (1.3), which is again easily derived by induction from the defining relations of H:

(2.2) S_{2}T^{a}S_{2}T^{b} = T^{b}S_{2}T^{a}S_{2} + (u_{2,1} + u_{2,2}) ∑_{i=1}^{b} (T^{a+b−i}S_{2}T^{i} − T^{i}S_{2}T^{a+b−i})

for 1 ≤ a ≤ e − 1, 0 ≤ b ≤ e − 1. Note that this agrees with the formula (1.3) in W_{n} up to elements T_{v} with length of v strictly smaller than the length of the element on the left hand side. (Also note that for e = 2, so for the Iwahori-Hecke algebra of type C_{n}, the sum cancels, as expected.)

As above we define

T_{k,a} := \{ \begin{matrix}S_{k} ⋯ S_{2}T^{a} & for a > 0, \\ 1 & for a = 0, \end{matrix}

for 1 ≤ k ≤ n, 0 ≤ a ≤ e − 1. The relations of Lemma 1.4 now become:

Lemma 2.3. We have:

(a)  S_{i}T_{k,a} = \{ \begin{matrix}T_{k,a}S_{i} & if i > k + 1 or a = 0, \\ T_{k+1,a} & if i = k + 1, a ≠ 0 \\ T_{k,a}S_{i+1} & if i < k, a ≠ 0, \end{matrix}

(b) T_{k+m,a}T_{k,b} =

T_{k−1,b}T_{k+m,a}S_{2} + (u_{2,1} + u_{2,2}) ∑_{i=1}^{b} (T_{k−1,a+b−i}T_{k+m,i} − T_{k−1,i}T_{k+m,a+b−i})

for a, b ≠ 0, k > 1, m ≥ 0.

From Lemma 1.5 we may then deduce the first main result:

Proposition 2.4. Let x, x′ be two reduced expressions of the same element in W_{n} = G(e, 1, n). Then

(2.5)  T_{x} − T_{x′} ∈ ∑_{y∉𝔖_{n}, 0<l(y)<l(x)} A T_{y},

where the sum runs over reduced expressions y of elements involving the generator t and of lengths 0 < l(y) < l(x).

Proof. If x, x′ are reduced expressions of an element in 𝔖_{n} then it follows from Matsumoto’s Lemma that T_{x} = T_{x′}. Thus we may assume that x ∉ 𝔖_{n}. Furthermore, it suffices to verify (2.5) for x′ of the form (1.6) and arbitrary reduced x. For this we analyze the proof of Lemma 1.5. By application of the braid relations, which also hold in H, we may assume that x has already been transformed to the form

x = t_{k_{1},b_{1}} ⋯ t_{k_{l},b_{l}}w.

Let

t_{1,a′_{0}} ⋯ t_{n,a′_{n−1}}w′

be the normal form (1.6) of x in W_{n}, as obtained by the method described in the proof of Lemma 1.5. Then clearly by application of Lemma 2.3 in place of Lemma 1.4 we may transform T_{x} to an expression of the form

(2.6)  ∑_{a} c_{a}T_{1,a_{0}} ⋯ T_{n,a_{n−1}}w_{a},

where the sum runs over a = (a_{0}, …, a_{n−1}) ∈ ℕ_{0}^{n} satisfying

∑_{i=0}^{n−1} a_{i} = ∑_{i=0}^{n−1} a′_{i}, and a_{i} = 0 if a′_{i} = 0,

and with c_{a} ∈ A and w_{a} ∈ 𝔖_{n}. Since the expression for x was assumed to be reduced, we have

∑_{i=0}^{n−1} a′_{i} ≤ r(e − 1),

where r is the number of i with a′_{i} ≠ 0. Thus, for any summand in (2.6), at least one of the a_{i} is smaller than e. We can now replace each term T^{a} in T_{k,a} with a ≥ e by a sum of scalar multiples of T^{b} with b ≤ e−1. For the multiple with T^{0} we may transfer the corresponding product S_{k} ⋯ S_{2} to the right by application of Lemma 2.3(a). But by the above observation in all summands of (2.6) there exists at least one factor T_{i,a_{i}} with a_{i} < e, so in all summands at least one positive power of T remains. Thus, none of the terms in the expression for T_{x} is a scalar multiple of 1, as claimed. □

2B. The canonical symmetrizing form.

The preceding proposition allows the definition of a canonical symmetrizing form on H. Note that a basis of H can be obtained from the set of T_{x}, where x runs over an arbitrary set of reduced expressions for the elements of W_{n}. Let L : H → A be the linear form on H with L(T_{1}) = 1, L(T_{x}) = 0 for the reduced expressions x of non-identity elements of W_{n}. By Proposition 2.4 this definition does not depend on the particular reduced expressions chosen in the definition of a basis of H. Hence the linear form is defined unambiguously.

Proposition 2.7. The linear form L on H(W_{n}, u) is central, i.e., L(hh′) = L(h′h) for all h, h′ ∈ H(W_{n}, u).

Proof. We fix the basis {T_{x} | x of the form (1.6)} of H. By linearity it is sufficient to check the claim if h, h′ are basis elements T_{x}, T_{x′}. Further, by induction, x′ = s for some s ∈ S. Finally, by induction on the length of x we may assume that L(T_{y}T_{s}) = L(T_{s}T_{y}) for all y of length strictly smaller than l(x). Let first s = s_{i} for some 2 ≤ i ≤ n. Write x = t_{1,a_{0}} ⋯ t_{n,a_{n−1}}w. Clearly all basis elements T_{y} occurring in T_{x}T_{s} have the shape y = t_{1,a_{0}} ⋯ t_{n,a_{n−1}}w′ for suitable elements w′ ∈ 𝔖_{n}. In particular it follows that L(T_{x}T_{s}) ≠ 0 if and only if x = s. Now define t′_{k,a} := t^{a}s_{2} ⋯ s_{k} if a ≠ 0 and t′_{k,0} := 1. It is clear by application of the procedure in the proof of Proposition 1.5, with all words reversed, that x is weakly braid equivalent to a reduced expression of the form x′ = w′t′_{n,b_{n−1}} ⋯ t′_{1,b_{0}} for suitable w′, b_{i}. By Proposition 2.4 we then have T_{x} = T_{x′} + ∑_{y} c_{y}T_{y} where the sum runs over reduced expressions y ∉ 𝔖_{n} of length strictly smaller than l(x). By induction hypothesis, L(T_{s}T_{y}) = 0 for all such y, and again we see that L(T_{s}T_{x′}) ≠ 0 if and only if x′ = s. But in that case x = x′ = s and T_{x}T_{s} = T_{s}^{2} = T_{s}T_{x}. It remains to consider the case s = t. Firstly, tx = t_{1,1} t_{1,a_{0}} ⋯ t_{n,a_{n−1}}w is reduced unless a_{0} = e − 1, and one sees that L(T_{t}T_{x}) ≠ 0 if and only if x = t^{e−1}. On the other hand, w is braid-equivalent to s_{k} ⋯ s_{2}w′ for some 1 ≤ k ≤ n and w′ ∈ ⟨s_{3}, …, s_{n}⟩. If w′ ≠ 1 we are done by induction since t and w′ commute. So xt = t_{1,a_{0}} ⋯ t_{n,a_{n−1}} t_{k,1}. By Lemma 2.3(b) the expansion of T_{x}T_{t} does only involve the basis element T_{1} if x = t^{e−1}. In that case the required equality clearly holds. □

It is known that the algebra H_{K} := H(W_{n}, u) ⊗_{A} K over K = Quot(A) is split semisimple [2]. We thus obtain:

Theorem 2.8. The cyclotomic algebra H(W_{n}, u) for W_{n} = G(e, 1, n) carries a canonical symmetrizing form L. This satisfies

(2.9) L(T_{x}) = 0 for all reduced expressions x of non-identity elements of W_{n}.

Proof. By Proposition 2.7 the linear form L on H(W_{n}, u) is central. So its extension to H_{K} can be written as

L = ∑_{χ∈Irr(H_{K})} δ_{χ}(L) χ

for certain δ_{χ}(L) ∈ K, where the sum runs over the irreducible characters of H_{K}. Then L defines a symmetrizing form on H(W_{n}, u) if all the δ_{χ}(L) are different from zero. But this is the case, since under the specialization (2.1) of H_{K} to the group algebra K(ζ_{e})W_{n}, the form L is mapped to the canonical central linear form ∑_{χ∈Irr(W_{n})} \frac{χ(1)}{|W_{n}|} χ of K(ζ_{e})W_{n}. □

2C. General imprimitive groups.

For any divisor p|e let W_{n,p} be the normal subgroup of index p of W_{n} generated by

S^{(p)} := {t^{p}, t^{−1}s_{2}t, s_{2}, …, s_{n}}.

Thus W_{n,p} is the imprimitive complex reflection group G(e, p, n) in the notation of Shephard and Todd. Following Ariki [1, Prop. 1.6] we define the cyclotomic algebra H(W_{n,p}; u) as the subalgebra of H(W_{n}; ũ), with parameters

(2.10)  ũ = (u_{1,1}, ζ_{p}u_{1,1}, …, ζ_{p}^{p−1}u_{1,1}, …, u_{1,e/p}, …, ζ_{p}^{p−1}u_{1,e/p}; u_{2,1}, u_{2,2})

(where ζ_{p} := exp(2πi/p)), generated by

{T^{p}, T^{−1}S_{2}T, S_{2}, …, S_{n}} .

Alternatively this could also be defined by a suitable diagram in the spirit of (1.1), see [4]. Since any irreducible imprimitive complex reflection group is isomorphic to some W_{n,p} we may deduce from Theorem 2.8 by restriction of the form L:

Corollary 2.11. Let W be an imprimitive complex reflection group. Then the associated cyclotomic algebra H(W, u) carries a canonical symmetrizing form.

3. A Length Function on G(e, 1, n)

In this section we define a root system and an associated length function for the complex reflection group G(e, 1, n) which generalize the root systems and length functions for Weyl groups. Here a root system for a complex reflection group W is a triple (Φ, Φ^{−}, Ω), where Φ is a set with W -action, Φ^{−} is a subset of Φ of cardinality |Φ^{−}| = |Φ|/2, and Ω is a subset of Φ \ Φ^{−} in bijection with the set of reflections of W. The length function ℓ associated with the root system (Φ, Φ^{−}, Ω) is the function W → ℕ_{0} defined by ℓ(w) := |w.Ω ∩ Φ^{−}|. This generalizes the usual notions for Weyl groups W. Indeed, if Φ is the usual root system and Φ^{±} are the sets of positive respectively negative roots then (Φ, Φ^{−}, Φ^{+}) is a root system in our sense, and the associated length function is the usual length function on W.

3A. Definition.

We continue the study of the imprimitive complex reflection group W_{n} ⊂ GL(V), with distinguished set of generators S = {t, s_{2}, …, s_{n}}. Let ζ = det_{V} (t) be the non-trivial eigenvalue of t. The action of W_{n} on the subset {ζ^{i}e_{j} | 0 ≤ i ≤ e − 1, 1 ≤ j ≤ n} of V defines an embedding of W_{n} into the symmetric group on the set Ψ := {0, …, e − 1} × {1, …, n}, i.e., with s_{k} acting on the second coordinate by interchanging k − 1 and k and with

t.(i, j) = \{ \begin{matrix}(i + 1 mod e, j) & if j = 1, \\ (i, j) & if j > 1. \end{matrix}

This induces an action of W_{n} on the direct product Ψ × Ψ and hence on

Φ := {(α, β) ∈ Ψ × Ψ | α ≠ β}.

By construction there is a natural W_{n}-equivariant map γ from Φ to the vector space V defined by

γ : Φ → V, ((i, j), (k, l)) ↦ ζ^{i}e_{j} − ζ^{k}e_{l}.

It is easily checked that the image of γ consists of eigenvectors for the non-trivial eigenvalues of the reflections in W_{n}. Moreover, the image resembles the root system of W_{n} in [6]. For this reason we call Φ the root system of W_{n}. Correspondingly, an element φ = ((i, j), (k, l)) ∈ Φ is called a root for a reflection s ∈ W_{n} if γ(φ) is an eigenvector for the non-trivial eigenvalue ξ of s, where moreover ξ = ζ^{i−k} if j = l. Note that thus any φ ∈ Φ is a root for precisely one reflection of W_{n}, which we denote by r(φ).

We define subsets of positive and negative roots Φ^{±} by

Φ^{+} ={((i, j), (k, j)) ∈ Φ | 0 ≤ i < k ≤ e − 1, 1 ≤ j ≤ n} ∪
{((0, j), (k, l)) ∈ Φ | 0 ≤ k ≤ e − 1, 1 ≤ l < j ≤ n} ∪
{((i, j), (k, l)) ∈ Φ | 0 ≤ i, k ≤ e − 1, k ≠ 0, 1 ≤ j < l ≤ n},
Φ^{−} = Φ \ Φ^{+}.

Thus Φ^{−} is the image of Φ^{+} under the natural involution

− : Φ → Φ, (α, β) ↦ −(α, β) := (β, α),

and clearly |Φ^{+}| = |Φ^{−}| = \binom{en}{2}, γ(Φ^{−}) = −γ(Φ^{+}) (but note that for e even we have γ(Φ^{−}) = γ(Φ)). Furthermore, we let

Ω = {((0, j), (k, l)) ∈ Φ | 1 ≤ l ≤ j ≤ n, 0 ≤ k ≤ e − 1} ⊂ Φ^{+}.

Thus Ω contains precisely one root for every reflection in W_{n}, and this establishes a bijection s ↦ φ_{s} with inverse r(φ_{s}) = s between the set of reflections R of W_{n} and Ω. Note that for any s ∈ S the only element of Ω sent to Φ^{−} by s is the root φ_{s}.

As in the case of Coxeter groups of type C_{n} we call the W_{n}-invariant subsets

Φ_{1} := {((i, j), (k, j)) ∈ Φ}, Φ_{2} := Φ \ Φ_{1},

the long roots respectively short roots of W_{n}. Hence |Φ_{1}| = en(e−1), |Φ_{2}| = e^{2}n(n−1). Accordingly, let Φ_{i}^{±} := Φ_{i} ∩ Φ^{±} and Ω_{i} := Ω ∩ Φ_{i} for i = 1, 2. We will also need the sets

Φ_{1}^{i} := {((i, j), (k, j)) ∈ Φ_{1}}

for i ∈ {1, e − 1} and

Ω_{2}^{−} := −Ω_{2}.

Finally, we define a length function ℓ : W_{n} → ℕ_{0} on W_{n} by

ℓ : W_{n} → ℕ_{0}, ℓ(w) := |w.Ω ∩ Φ^{−}| .

For example, by our previous remark, the elements of S all have length 1. With the above decomposition Ω = Ω_{1} ∪^{·} Ω_{2} the function ℓ can be written as the sum of the two functions

ℓ_{i} : W_{n} → ℕ_{0}, ℓ_{i}(w) := |w.Ω_{i} ∩ Φ^{−}| , for i = 1, 2.

We shall study the properties of the length functions ℓ, ℓ_{1}, ℓ_{2} in the sequel. We will make frequent use of the following interpretation of ℓ, ℓ_{1}, ℓ_{2}, which was pointed out to us by the referee.

Write w ∈ W_{n} with

w.e_{i} = ζ^{a_{i}}e_{σi}

as w = (a_{1}, …, a_{n}; σ), 0 ≤ a_{i} < e, σ ∈ 𝔖_{n}.

Lemma 3.1. For w = (a_{1}, …, a_{n}; σ) ∈ W_{n}, we have

ℓ_{1}(w) = ∑_{j=1}^{n} a_{j}

and

ℓ_{2}(w) = e · |{(l, j) | l < j, σl < σj, a_{j} ≠ 0}| + l(σ).

So

ℓ(w) = ∑_{j=1}^{n} a_{j} + e · |{(l, j) | l < j, σl < σj, a_{j} ≠ 0}| + l(σ).

Proof. Let ((0, j), (k, j)) ∈ Ω_{1}. Then w.((0, j), (k, j)) = ((a_{j}, σj), (k + a_{j}, σj)), which lies in Φ_{1}^{−} if and only if k ≥ e − a_{j}. The formula for ℓ_{1} follows.

For ((0, j), (k, l)) ∈ Ω_{2}, we have w.((0, j), (k, l)) = ((a_{j}, σj), (k + a_{l}, σl)), which lies in Φ_{2}^{−} if and only if either a_{j} ≠ 0 and σl < σj or k = e − a_{l} and σj < σl. Thus

\begin{matrix}ℓ_{2}(w) = & e · |\{(l, j) | l < j, σl < σj, a_{j} ≠ 0\}| + |\{(l, j) | l < j, σl > σj\} \\ = & e · |\{(l, j) | l < j, σl < σj, a_{j} ≠ 0\}| + l(σ). \end{matrix}

□

An immediate consequence of this formula is that

ℓ(w) = 0 if and only if l(w) = 0.

Remark. Suppose e = 2. We identify W_{n} with the Coxeter group of type C_{n}. Then γ gives a bijection between Ω and the set of (usual) positive roots of W_{n} such that γ(Ω_{i}), i = 1, 2, become the long respectively short positive roots. Further, γ(Φ^{−}) equals the set of negative roots (compare [5, 3.6(ii)]). We deduce that in this case, ℓ coincides with the usual length function on W_{n}.

3B. Parabolic subgroups.

For J ⊆ S, we denote by W_{J} the subgroup of W_{n} generated by s ∈ J. The irreducible components of W_{J} are all of type C_{m}^{(e)} or A_{m} for some 1 ≤ m ≤ n. So there is a well-defined length function ℓ_{J} on W_{J}. Let Φ_{J} := {φ ∈ Φ | r(φ) ∈ W_{J}}, and for any subset Υ ⊆ Φ, set Υ_{J} := Υ ∩ Φ_{J}.

Proposition 3.2. For J ⊆ S, the function ℓ coincides on W_{J} with ℓ_{J}.

Proof. First assume that t ∉ J. Then W_{J} is a direct product of symmetric groups and w ∈ W_{J} can be written as w = (0, …, 0; w). Using Lemma 3.1, we conclude

ℓ(w) = l(w) = ℓ_{J}(w).

Secondly, assume that t ∈ J. We write J = J_{1} ∪^{·} J_{2} where J_{1} = {t, s_{2}, …, s_{m}} with m maximal. If w = (a_{1}, …, a_{n}; σ) ∈ W_{J_{1}} then a_{m+1} = ⋯ = a_{n} = 0. Thus

ℓ(w) = ∑_{j=1}^{m} a_{j} + e · |{(l, j) | l < j, σl < σj, a_{j} ≠ 0, j ≤ m}| + l(σ) = ℓ_{J}(w).

For an arbitrary element w = w_{1}w_{2} ∈ W_{J}, w_{1} = (a_{1}, …, a_{m}, 0, …, 0; σ) ∈ W_{J_{1}}, w_{2} ∈ W_{J_{2}}, we have w = (a_{1}, …, a_{m}, 0, …, 0; σw_{2}) where l(σw_{2}) = l(σ) + l(w_{2}), and thereby

ℓ(w) = ℓ(w_{1}) + ℓ(w_{2}) = ℓ_{J}(w).  □

We intend to study the case J := {t, s_{2}, …, s_{n−1}}, so W_{J} = W_{n−1}.

Proposition 3.3. The set R = {w ∈ W_{n} | w.Ω_{J} ⊂ Φ^{+}} is a set of left coset representatives of W_{J} in W_{n}. Furthermore, for r ∈ R and w_{J} ∈ W_{J}, we have ℓ_{i}(rw_{J}) = ℓ_{i}(r) + ℓ_{i}(w_{J}), i ∈ {1, 2}.

Proof. Following a suggestion of the referee, we claim that

R = {(0, …, 0, a; σ_{h}) | 0 ≤ a ≤ e − 1, 1 ≤ h ≤ n}

where σ_{h} is the element in 𝔖_{n} such that

σ_{h}i = \{ \begin{matrix}i & if 1 ≤ i < h, \\ i + 1 & if h ≤ i < n, \\ h & if i = n. \end{matrix}

Indeed, let w = (a_{1}, …, a_{n}; σ) ∈ R. Then ((a_{j}, σj), (k + a_{j}, σj)) ∈ Φ^{+} for all 1 ≤ j ≤ n − 1, 1 ≤ k ≤ e − 1, in particular for k = e − 1. Hence a_{j} = 0 for all 1 ≤ j ≤ n − 1. Furthermore, ((0, σj), (k, σl)) ∈ Φ^{+} for all 0 ≤ k ≤ e − 1 and 1 ≤ l < j ≤ n − 1. Thus σj < σl for all 1 ≤ l < j ≤ n − 1, which implies σ = σ_{h} for some 1 ≤ h ≤ n. This proves one inclusion. The other inclusion is clear.

Notice that we showed that

R = {w ∈ W_{n} | w.Ω_{J} ⊂ Ω^{+}}.

Now let r = (0, …, 0, a; σ_{h}) ∈ R and w_{J} = (a_{1}, …, a_{n−1}, 0; σ) ∈ W_{J}. Suppose

rw_{J} = (a_{1}, …, a_{n−1}, a; σ_{h}σ) ∈ R.

Then a_{1} = ⋯ = a_{n−1} = 0, and since σ ∈ 𝔖_{n−1} and {σ_{h} | 1 ≤ h ≤ n} is a set of left coset representatives of 𝔖_{n−1} in 𝔖_{n}, we have σ = 1. So w_{J} = 1. This proves that no two elements of R lie in the same left coset of W_{J} in W_{n}.

Since |R| = en = (W_{n} : W_{n−1}), the first part of the proposition follows.

The second part is an easy consequence of the above expression for rw_{J}. Notice that l(σ_{h}σ) = l(σ_{h}) + l(σ). □

Remark. Define expressions

w(j, l) = s_{j}s_{j+1} ⋯ s_{l}

for 2 ≤ j ≤ l + 1 ≤ n + 1 and

w_{i}(j, l) = w(2, j)^{−1}t^{i}w(2, l)

for 1 ≤ j ≤ l ≤ n, 1 ≤ i ≤ e − 1. The element r = (0, …, 0, a; σ_{h}) ∈ R has a unique reduced expression r = w(h + 1, n) if a = 0 and r = w_{a}(h, n) if a ≠ 0. (We identify expressions and elements in W_{n}.)

Let w ∈ W_{n}. We call an expression of the form w = rw_{J} where r ∈ R and w_{J} ∈ W_{J} are reduced an R-expression for w. By comparing the possible (standard) lengths of R-expressions with the lengths of the reduced expressions in Lemma 1.5, it can be seen that R-expressions are reduced. In particular, l(rw_{J}) = l(r) + l(w_{J}).

We can then use induction on n in order to show that

(3.4)  l(w) = ∑_{j=1}^{n} a_{j} + 2 · |{(l, j) | l < j, σl < σj, a_{j} ≠ 0}| + l(σ)

for w = (a_{1}, …, a_{n}; σ) ∈ W_{n}.

With Lemma 3.1 we conclude:

Corollary 3.5. For w ∈ W_{n}, we have

ℓ(w) ≥ l(w).

A straightforward calculation shows:

Lemma 3.6. For r = (0, …, 0, a; σ_{h}) ∈ R, we have

ℓ_{1}(r) = a

and

ℓ_{2}(r) = \{ \begin{matrix}n − h & if a = 0, \\ e(h − 1) + n − h & if a ≠ 0. \end{matrix}

In contrast to the standard length function for W_{n} the length function ℓ attached to the root system Φ satisfies the following identity:

Proposition 3.7. We have

∑_{w∈W_{n}} q^{ℓ(w)} = P (W_{n})

where q is an indeterminate and

P (W_{n}) = ∏_{i=1}^{n}(1 + q + ⋯ + q^{ie−1})

denotes the Poincaré polynomial of W_{n}.

Proof. Recalling the values of ℓ_{1} and ℓ_{2} on R from Lemma 3.6, we obtain

\begin{matrix}\{ℓ(r) | r ∈ R\} = & [0, n − 1] ∪ \{a + n − h + (h − 1)e | 1 ≤ h ≤ n, 1 ≤ a ≤ e − 1\} \\ = & [0, n − 1] ∪ \{n + (a + h(e − 1)) | 0 ≤ h ≤ n − 1, 0 ≤ a ≤ e − 2\} \\ = & [0, n − 1] ∪ [n, ne − 1] = [0, ne − 1], \end{matrix}

and the correspondence between the sets is one-to-one.

The Poincaré polynomial of W_{n} can be factored as

P (W_{n}) = P (W_{n−1}) · (1 + q + ⋯ + q^{ne−1}).

Because of Proposition 3.3, we can use induction on n to complete the proof. □

3C. Some more properties.

We first give combinatorial interpretations for ℓ_{1} and ℓ_{2}.

Lemma 3.8. For w ∈ W_{n}, the value ℓ_{1}(w) equals the minimal number of t’s in an expression for w. In particular, ℓ_{1}(w) equals the number of t’s in any reduced expression.

Proof. It is clear that the number of t’s in any expression for w has to be at least ℓ_{1}(w). By induction on n, we see that the number of t’s in an R-expression for w equals ℓ_{1}(w), which proves the first part of the lemma. The second part follows from the facts that R-expressions are reduced and that, according to Lemma 1.5, any two reduced expressions are weakly braid-equivalent. □

Let A_{i} := ⟨s_{2}, s_{3}, …, s_{i+1}⟩, 0 ≤ i ≤ n − 1.

Proposition 3.9. Suppose w = w_{1}t^{a_{1}}w_{2}t^{a_{2}} ⋯ w_{m}t^{a_{m}}w_{m+1} with all w_{i} ∈ A_{n−1} and 0 ≤ a_{i} < e is an expression for w ∈ W_{n} subject to at least one of the following two conditions.

(i) The expression is reduced.

(ii) The number m is minimal.

Then

(3.10)  ℓ_{2}(w) = ∑_{i=1}^{m+1} l(w_{i}) + \frac{e − 2}{2} \{( ∑_{i=1}^{m+1} l(w_{i})) − l(w_{1} ⋯ w_{m+1})\} ,

where l = ℓ is the usual length function on A_{n−1}.

Proof. If w = (a′_{1}, …, a′_{n}; σ) then σ = w_{1} … w_{m+1}. In view of Lemma 3.1, we therefore only need to show that

∑_{i=1}^{m+1} l(w_{i}) − l(σ) = 2 · |{(l, j) | l < j, σl < σj, a_{j} ≠ 0}|,

which follows from (3.4). □

Let w_{0} be the longest element in W_{n} with respect to ℓ (and also with respect to l). We know from Proposition 3.3, for example, that w_{0} = (e − 1, …, e − 1; 1).

Corollary 3.11. Let w ∈ W_{n}.

(a) We have

ℓ_{1}(w^{−1}) = e m_{w} − ℓ_{1}(w), ℓ_{2}(w^{−1}) = ℓ_{2}(w)

where m_{w} = |{j | 1 ≤ j ≤ n, w.e_{j} ∉ {e_{1}, …, e_{n}}}|.

(b) We have

\begin{matrix}ℓ_{1}(w^{−1}w_{0}) = & ℓ_{1}(w_{0}) − ℓ_{1}(w), \\ ℓ_{2}(w^{−1}w_{0}) = & ℓ_{2}(w) + e (n_{0}(w) − n_{e−1}(w)) \end{matrix}

where n_{i}(w) = |{(l, j) | l < j, σl < σj, a_{j} = i}|, i ∈ {0, e − 1}.

Proof. Part (a) follows from Lemma 3.8 and Proposition 3.9 or, alternatively, from Lemma 3.1.

For part (b), let w = (a_{1}, …, a_{n}; σ) ∈ W_{n}. Then w^{−1}w_{0} = (e − 1 − a_{1}, …, e − 1 − a_{n}; σ^{−1}), and Lemma 3.1 implies the formulas for ℓ_{1} and ℓ_{2}. □

For the following proposition, we remark that

φ_{s} = \{ \begin{matrix}((0, 1), (e − 1, 1)) & if s = t, \\ ((0, i), (0, i − 1)) & if s = s_{i}, 2 ≤ i ≤ n. \end{matrix}

Proposition 3.12. Let w ∈ W_{n}.

(a) For s = t, we have

ℓ(ws) = \{ \begin{matrix}ℓ(w) − (e − 1) & if w.φ_{s} ∈ Φ_{1}^{e−1}, \\ ℓ(w) + 1 & if w.φ_{s} ∉ Φ_{1}^{e−1}. \end{matrix}

(b) For s = s_{i}, 2 ≤ i ≤ n, we have

ℓ(ws) = \{ \begin{matrix}ℓ(w) + 1 & if w.φ_{s} ∈ Ω_{2}, \\ ℓ(w) + (e − 1) & if w.φ_{s} ∈ Φ_{2}^{+} \ Ω_{2}, \\ ℓ(w) − 1 & if w.φ_{s} ∈ Ω_{2}^{−}, \\ ℓ(w) − (e − 1) & if w.φ_{s} ∈ Φ_{2}^{−} \ Ω_{2}^{−}. \end{matrix}

Proof. Part (a) easily follows from the definitions of ℓ_{1} and ℓ_{2}.

Let s = s_{i}, 2 ≤ i ≤ n. Since ℓ_{1}(ws_{i}) = ℓ_{1}(w), we only need to consider ℓ_{2}. We define N (w) := {ρ ∈ Ω_{2} | w.ρ ∈ Φ_{2}^{−}} and Ω_{i,i−1} := {((0, i), (k, i − 1)) ∈ Ω_{2}}, 2 ≤ i ≤ n.

Say w.φ_{s_{i}} = ((a, b), (c, d)) for some 0 ≤ a, c ≤ e − 1, 1 ≤ b, d ≤ n. It is easy to check that

N (ws_{i}) = \{ \begin{matrix}(s_{i}. N (w)) ∪^{·} \{φ_{s_{i}}\} & if w.φ_{s_{i}} ∈ Ω_{2}, \\ s_{i}.(N (w) \ \{((0, i), (e − c, i − 1))\}) ∪^{·} Ω_{i,i−1} & if w.φ_{s_{i}} ∈ Φ_{2}^{+} \ Ω_{2}, \\ s_{i}.(N (w) \ \{φ_{s_{i}}\}) & if w.φ_{s_{i}} ∈ Ω_{2}^{−}, \\ s_{i}.(N (w) \ Ω_{i,i−1}) ∪^{·} \{((0, i), (e − a, i − 1))\} & if w.φ_{s_{i}} ∈ Φ_{2}^{−} \ Ω_{2}^{−}. \end{matrix}

Note that s_{i} fixes all ((0, j), (k, l)) ∈ Ω_{2} such that {j, l} ∩ {i, i − 1} = ∅ and that s_{i} stabilizes the sets {((0, i − 1), (k, l)), ((0, i), (k, l)) | 0 ≤ k ≤ e − 1, 1 ≤ l < i − 1} and {((0, j), (k, i−1)), ((0, j), (k, i)) | 0 ≤ k ≤ e−1, i < j ≤ n}. The assertion follows. □

Corollary 3.13. Let w ∈ W_{n}.

(a) For s = t, we have

ℓ(sw) = \{ \begin{matrix}ℓ(w) − (e − 1) & if w^{−1}.φ_{s} ∈ Φ_{1}^{1}, \\ ℓ(w) + 1 & if w^{−1}.φ_{s} ∉ Φ_{1}^{1}. \end{matrix}

(b) For s = s_{i}, 2 ≤ i ≤ n, we have

ℓ(sw) = \{ \begin{matrix}ℓ(w) + 1 & if w^{−1}.φ_{s} ∈ Ω_{2}, \\ ℓ(w) + (e − 1) & if w^{−1}.φ_{s} ∈ Φ_{2}^{+} \ Ω_{2}, \\ ℓ(w) − 1 & if w^{−1}.φ_{s} ∈ Ω_{2}^{−}, \\ ℓ(w) − (e − 1) & if w^{−1}.φ_{s} ∈ Φ_{2}^{−} \ Ω_{2}^{−}. \end{matrix}

The proof is similar to the previous one. Observe that part (b) can also be obtained as a consequence of the above proposition and Corollary 3.11 (a).

Remark. In view of (3.4), the proof of Proposition 3.12 also shows that

(3.14)  l(wt) = \{ \begin{matrix}l(w) − (e − 1) & if w.φ_{t} ∈ Φ_{1}^{e−1}, \\ l(w) + 1 & if w.φ_{t} ∉ Φ_{1}^{e−1} \end{matrix}

and

(3.15)  l(ws_{i}) = \{ \begin{matrix}l(w) + 1 & if w.φ_{s_{i}} ∈ Φ_{2}^{+}, \\ l(w) − 1 & if w.φ_{s_{i}} ∈ Φ_{2}^{−} \end{matrix}

for 2 ≤ i ≤ n. Similar formulas hold for l(sw), s ∈ S.

Corollary 3.16. For w ∈ W_{n} and s ∈ S, we have ℓ(ws^{−1}) < ℓ(w) resp. ℓ(s^{−1}w) < ℓ(w) if and only if w has a reduced expression ending resp. starting with s.

Proof. We only consider ws^{−1}. It follows from Proposition 3.12 and the above remark that the conditions ℓ(ws^{−1}) < ℓ(w) and l(ws^{−1}) < l(w) are equivalent. If l(ws^{−1}) < l(w) we obtain the desired reduced expression for w by concatenating a reduced expression for ws^{−1} and s. The other direction is equally clear. □

Corollary 3.16 immediately implies the following statement.

Corollary 3.17. For any 1 ≠ w ∈ W_{n}, there exist s, s′ ∈ S such that ℓ(ws^{−1}) < ℓ(w) and ℓ(s′^{−1}w) < ℓ(w).

Remark. The root system introduced above can be used to perform effective computations in the complex reflection groups W_{n}. Indeed, W_{n} can be realized as a permutation group on the set of roots Φ. Then Corollaries 3.13 – 3.17 determine an algorithm which associates to each element w ∈ W_{n} a reduced expression.

The computer algebra system GAP [7] contains functions dealing with finite Weyl groups, based on the realization of the elements of the Weyl group as permutations on its set of roots. We intend to use the preceding results to implement analogous functions for W_{n} in GAP.

3D. A connection with the cyclotomic Hecke algebra.

Let U := {w ∈ W_{n} | ℓ(w) = l(w)}.

Proposition 3.18. Assume e > 2. An element w ∈ W_{n} lies in U if and only if w = w_{n} ⋯ w_{1} where for any 1 ≤ k ≤ n either w_{k} = w(j, k) for some 2 ≤ j ≤ k + 1 or w_{k} = w_{i}(1, k) for some 1 ≤ i ≤ e − 1. These are precisely the elements which avoid a subexpression of the form s_{2}t^{i}s_{2} in any reduced expression.

Proof. For n = 1, we have U = W_{1}, and all statements are clear.

Let n > 1. We use the notations from the previous section. Write w = rw_{J} where r ∈ R and w_{J} ∈ W_{J}. It follows from Proposition 3.3, the subsequent remark, and Corollary 3.5 (applied to r and w_{J}) that ℓ(w) = l(w) is equivalent to ℓ(r) = l(r) and ℓ(w_{J}) = l(w_{J}). But ℓ(r) = l(r) if and only if r = w(j, n) for some 2 ≤ j ≤ n + 1 or r = w_{i}(1, n) for some 1 ≤ i ≤ e − 1. This and induction show the first part of the proposition.

The fact that any reduced expression for w ∈ U avoids expressions of the form s_{2}t^{i}s_{2} follows from Proposition 3.9. For the converse, we choose an R-expression w = rw_{J}. Then obviously r cannot be of the form w_{i}(j, n) with 2 ≤ j ≤ n, 1 ≤ i ≤ e − 1, and we can apply induction to w_{J}. □

Remark. The elements in U (for e > 2) can also be described as the elements w ∈ W_{n} such that for all 1 ≤ l < j ≤ n there exists at most one 0 ≤ k ≤ e − 1 such that w.((0, j), (k, l)) ∈ Φ_{2}^{−}, which then necessarily lies in Ω_{2}^{−}. (This follows from Lemma 3.1.)

The characterization of the elements in U as s_{2}t^{i}s_{2}-, hence in particular s_{2}t^{i}s_{2}t^{j}- avoiding elements has the following consequence for monomials in the cyclotomic algebra associated to W_{n}.

Corollary 3.19. If x and x′ are reduced expressions for an element w ∈ U, i.e., with ℓ(w) = l(w), then T_{x} = T_{x′} in H(W_{n}, u).

References

[1] S. Ariki, Representation theory of a Hecke algebra of G(r, p, n), J. Algebra 177 (1995), 164–185.

[2] S. Ariki and K. Koike, A Hecke algebra of (ℤ/rℤ) ≀ S_{n} and construction of its irreducible representations, Advances in Math. 106 (1994), 216–243.

[3] M. Broué and G. Malle, Zyklotomische Heckealgebren, Astérisque 212 (1993), 119–189.

[4] M. Broué, G. Malle, and R. Rouquier, On complex reflection groups and their associated braid groups, Representations of groups (B.N. Allison and G.H. Cliff, eds.), CMS Conference Proceedings, vol. 16, AMS, Providence, 1995, pp. 1–13.

[5] R. W. Carter, Simple groups of Lie type, John Wiley, London, 1972.

[6] A. M. Cohen, Finite complex reflection groups, Ann. scient. Éc. Norm. Sup. 9 (1976), 379–436.

[7] M. Schönert et al., GAP — Groups, Algorithms, and Programming, fourth ed., Lehrstuhl D für Mathematik, RWTH Aachen, Germany, 1994.

K. B. : Department of Mathematics, M.I.T., Cambridge, MA 02139, U.S.A.

   E-mail address: kbremke@math.rwth-aachen.de

G. M. : I.W.R., Im Neuenheimer Feld 368, D–69120 Heidelberg, Germany

   E-mail address: malle@urania.iwr.uni-heidelberg.de