`Coxeter`

One of the major additions to version 3 of *Coxeter* is that it
contains a full implementation of the minimal root algorithm of Brink and
Howlett [1] (see also Bill Casselman's
paper and
course notes.)
Using this algorithm, it is possible to reduce, and also find the
lexicographically minimal reduced expression (also called the *ShortLex
normal form*), for a given ordering of the generators, of an element in the
group.

Of course the difficulty is to construct the set of minimal roots as an
abstract finite state machine. The program does this for any group whose
rank doesn't exceed one-half of the number of bits in an unsigned long on
your machine (the half is actually there for the convenience of other parts
of the program, and could be removed as far as minimal roots are concerned),
and for which the coefficients of the Coxeter matrix are either infinite
or not exceeding 32763, provided of course that there is enough memory
available for the minimal root table. Although I haven't been able to
prove any realistic estimates, the number of minimal roots seems to be
always reasonably small (although not *very* small; a few hundred thousand
is not out of the question), particularly so for the groups which arise in
common practice. It is known of course that for finite groups the minimal roots
are all the positive roots, and for affine groups their numbers is twice
the number of positive roots of the corresponding finite Weyl group.

In addition to the above normalizations, the program carries out elementary operations such as the computation of the descent set of an element in the group, and the comparison of two elements in the Bruhat ordering by the well-known elementary algorithm (see [2].)

In view of this possibility of efficiently reducing and comparing words for
equality in the group, it is our convention that all words inside the program
are reduced (a function can be called to reduce an arbitrary word if
necessary.) This is the default way of representing a group element,
except for the elements in the enumerated part
of the group, which may be referred by numbers. In addition to this numbering
of the enumerated part (which is indicated with a % sign on output, and may
be session-dependent), there is a canonical numbering of the elements for
finite groups whose cardinality doesn't exceed the largest unsigned long,
indicated with a # sign, which may be used as a convenient shorthand for
input purposes. See the help function for the *compute* command for
further information about input of group elements. In type A, it is also
possible to enter a group element as a permutation.

[1] | B. Brink and R. Howlett, A finiteness property and an automatic structure
for Coxeter groups, Math. Annalen 296, 1993, pp. 179-190. |

[2] | J.E. Humphreys, Reflection groups and Coxeter groups, Cambridge University Press, Cambridge, UK, 1990. |

Back to the Coxeter home page.