.. _SectGrpCoxIntro:

.. _introduction:

Introduction
============

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

.. math:: s_is_js_i\cdots = s_js_is_j\cdots

for :math:`i,j=1,\dots,n` with :math:`i<j`, where each side of this relation has
length :math:`m_{ij}\ge 2`. Traditionally, :math:`m_{ij}=\infty` signifies that
the corresponding relation is omitted but, for technical reasons,
:math:`m_{ij}=0` is used in Magma instead. The group :math:`G` is called a
*Coxeter group* and :math:`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
:cite:`BourbakiLie` for more details on the theory of Coxeter
groups.

The *rank* of the Coxeter system is :math:`n=|S|`. A Coxeter system is said to
be *reducible* if there is a proper subset :math:`I` of :math:`\{1,\dots,n\}`
such that :math:`m_{ij}=2` or :math:`m_{ji}=2` whenever :math:`i\in I` and
:math:`j\notin I`. In this case, :math:`G` is an (internal) direct product of
the Coxeter subgroups :math:`W_I=\langle s_i \mid i \in I \rangle` and
:math:`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, :math:`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 :ref:`ChapGrpFP` 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 :ref:`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 :ref:`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 :cite:`Chevie` by
Meinholf Geck, Frank Lübeck, Jean Michel and Götz Pfeiffer.

.. _SubsectGrpCoxRed:

.. _reduction:

The Normal Form for Words
-------------------------

Every element :math:`w` of a Coxeter group :math:`W` can be written as a word

.. math:: w = r_1 r_2\cdots r_l

with each :math:`r_i` in :math:`S`. A *reduced expression* for :math:`w` is such
a word with :math:`l` minimal; in this case, :math:`l` is defined to be the
*length* of :math:`w`.

An ordering on words in :math:`S` is obtained by taking the *lexicographic
(alphabetic) order* induced by the existing ordering on :math:`S`. The *normal
form* for :math:`w` in :math:`W` is the smallest reduced expression for
:math:`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
:cite:`Brink98,BrinkHowlett93`.

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 :ref:`SectGrpCoxConvert`).