Coxeter

Reduced expressions and normal forms

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.