Introduction

This chapter describes Magma functions for computing with Coxeter groups. A Coxeter system is a group \(G\) with finite generating set \(S=\{s_1,\dots,s_n\}\), defined by relations \(s_i^2=1\) for \(i=1,\dots,n\) and

\[s_is_js_i\cdots = s_js_is_j\cdots\]

for \(i,j=1,\dots,n\) with \(i<j\), where each side of this relation has length \(m_{ij}\ge 2\). Traditionally, \(m_{ij}=\infty\) signifies that the corresponding relation is omitted but, for technical reasons, \(m_{ij}=0\) is used in Magma instead. The group \(G\) is called a Coxeter group and \(S\) is called the set of Coxeter generators. Since every group in Magma has a preferred generating set, no distinction is made between a Coxeter system and its Coxeter group. See [Bourbaki, 1968] for more details on the theory of Coxeter groups.

The rank of the Coxeter system is \(n=|S|\). A Coxeter system is said to be reducible if there is a proper subset \(I\) of \(\{1,\dots,n\}\) such that \(m_{ij}=2\) or \(m_{ji}=2\) whenever \(i\in I\) and \(j\notin I\). In this case, \(G\) is an (internal) direct product of the Coxeter subgroups \(W_I=\langle s_i \mid i \in I \rangle\) and \(W_{I^c}=\langle s_i \mid i \notin I \rangle\). Note that an irreducible Coxeter group may still be a nontrivial direct product of abstract subgroups (for example, \(W(G_2)\cong S_2\times S_3\)). Two Coxeter groups are Coxeter isomorphic if there is a group isomorphism between them which takes Coxeter generators to Coxeter generators. In other words, the two groups are the same modulo renumbering of the generators.

Magma provides three methods for working with Coxeter groups:

1. As a finitely presented group with the standard presentation given above. These groups have type . See Chapter [DRAFT] FINITELY PRESENTED GROUPS for general functions for finitely presented groups.

2. As a permutation group acting on the roots of the root system. Clearly the group must be finite. These groups have type . See Chapter ChapGrpPerm for general functions for permutation groups.

3. As a reflection group, i.e. a matrix group generated by reflections. These groups have the same type as general matrix groups (). They can be distinguished with the IsReflectionGroup function.

The first two methods are described in this chapter. The third is described in Chapter ChapGrpRfl.

A permutation Coxeter group always has an underlying root system or root datum, and so many commands involving roots also work for these groups. A finitely presented Coxeter group does not have such an underlying structure.

The code for Coxeter groups as permutation groups was originally modelled on the corresponding part of the Chevie package of GAP [Geck et al., 1996] by Meinholf Geck, Frank Lübeck, Jean Michel and Götz Pfeiffer.

The Normal Form for Words

Every element \(w\) of a Coxeter group \(W\) can be written as a word

\[w = r_1 r_2\cdots r_l\]

with each \(r_i\) in \(S\). A reduced expression for \(w\) is such a word with \(l\) minimal; in this case, \(l\) is defined to be the length of \(w\).

An ordering on words in \(S\) is obtained by taking the lexicographic (alphabetic) order induced by the existing ordering on \(S\). The normal form for \(w\) in \(W\) is the smallest reduced expression for \(w\) with respect to this ordering. Algorithms for efficiently computing this normal form have been developed and implemented by R.B. Howlett. These algorithms are based on the concept of a minimal root [Brink, 1998, Brink and Howlett, 1993].

The main difference of the category of Coxeter groups () from the category of finitely presented groups (GrpFP) is that that all words are automatically put into this normal form. In particular, this means that two words are equal if, and only if, they are equal as group elements. Coxeter groups can also be constructed in the category GrpFP if the user wishes to avoid automatic normalisation of elements (see Section Converting Between Types of Coxeter Group).