CHEVIE is a joint project of Meinolf Geck, Gerhard Hiss, Frank
Laccent127 ubeck, Gunter Malle, Jean Michel, and Gaccent127 otz
Pfeiffer. The **GAP**--part of CHEVIE is a package, written entirely in
the **GAP** language, which consists of
item
functions implementing algorithms for finite reflection groups and their
root systems, braid groups, and Iwahori-Hecke algebras, including normal
forms for the elements in these objects and, for example, special
functions for computing Kazhdan-Lusztig polynomials and lefts cells;
item
library files containing pre-stored information about conjugacy classes
of finite Coxeter groups, fake degrees and generic degrees of the
irreducible characters, and character tables of finite Coxeter groups and
the associated Iwahori-Hecke algebras.
The files containing these programs and data are built up in a similar
way as the files in **GAP**. In particular, each file contains a copyright
notice and the name(s) of the CHEVIE authors who wrote that file.

This package replaces the former `weyl`

package. A number of functions
have got new names (mathematically more correct, we hope). For example,
one can now work systematically with non-crystallographic Coxeter groups,
and so the former function `Weyl`

has become `CoxeterGroup`

. Elements in
these groups are systematically permutations on the underlying root
system, and reduced expressions in the generators of the group will be
called `CoxeterWords`

. For the convenience of the user we have provided a
file which contains just assignments of the form `Weyl:=CoxeterGroup`

etc., so that many functions written with the old system should still
work. This file can be read into the system using the command
`ReadChv("compatib")`

, but we do not guarantee that this file will
survive in future releases. The package itself is loaded using the
command `RequirePackage("chevie")`

(see RequirePackage).

The overall logical structure of this package is as follows. The basic
input datum is a Cartan matrix associated with a finite reduced root
system in some Euclidean space. The function `CoxeterGroup`

computes from
such a matrix a record which contains basic information and upon which
all further applications are based. This is described in detail in
chapter Root systems and finite Coxeter groups. There are extensions to
this basic construction allowing, more generally, inputs like root data
and automorphisms acting on the ingredients of such root data. This is
described in more detail in chapter Coxeter cosets.

But it is important to keep in mind that the whole system is structured
bottom-up. This means that, if one is only interested in the finite
Coxeter groups themselves then one can just stick to the simplest form of
the function `CoxeterGroup`

and one does not have to worry about any of
the more elaborate concepts which can be build upon this. Any higher
order application just adds new components to the original record and
increases its functionality.

A similar remark applies to braid groups and Iwahori--Hecke algebras:
they are constructed by applying the functions `Braid`

and `Hecke`

to a
Coxeter group record which had already been constructed before using the
function `CoxeterGroup`

. Again, all the functionality of the original
record remains valid.

The files containing the most basic functions implementing these
structures are `coxeter.g`

, `braid.g`

and `hecke.g`

. There are more files
containing functions for special purposes like `kl.g`

(for
Kazhdan-Lusztig polynomials).

The record computed by `CoxeterGroup`

is, in the first place, a
permutation group record in **GAP**. Thus, all **GAP** functions for
dealing with finite groups and, in particular, permutation groups can be
applied to such a record, like `Elements`

, `Size`

, `CharTable`

to mention
but a few. These are generic **GAP** functions in the usual sense that
they first look at the operations record of `CoxeterGroup`

to see which
algorithm has to be taken. Another important feature of the design of
the CHEVIE package is that many of these functions admit more
efficient versions by taking into account the particular structure of
finite Coxeter groups.

Many objects constructed in or associated with finite Coxeter groups admit some canonical labeling which carries additional information. It is precisely this labeling which is very often important to know for the application of results on Coxeter groups in Lie theory or related areas.

For example, the generic **GAP** function `ConjugacyClasses`

applied to a
Coxeter group record does not invoke the general algorithm for computing
conjugacy classes of permutation groups in **GAP**, but first decomposes
the given Coxeter group into irreducible components, and then reads
canonical representatives of minimal length in the various classes of
these irreducible components from library files. These canonical
representatives also come with some additional information, for example
Carter's admissible diagrams (see ChevieClassInfo). In a similar way,
the function `CharTable`

does not invoke the Dixon--Schneider algorithm
but proceeds in a similar way as described above. Moreover, the resulting
character table comes with additional labelings of the classes and
characters, like partitions of *n* in the case of the symmetric group
*{mathfrak S}_n*, i.e., the Coxeter group of type *A_{n-1}* (see
ChevieCharInfo).

Thus, roughly *2/3* of the total memory space required by the CHEVIE
files is occupied by the files containing the basic information about the
finite irreducible Coxeter groups. These files are called `weyla.g`

,
`weylb.g`

etc. up to the biggest file `weyle8.g`

whose size is about
*500*~KBytes. These data files are structured in a uniform manner so that
any piece of information can be extracted separately from them. (For
example, it is not necessary to first compute the character table in
order to have labels for the characters and classes.)

The conventions that we use about normal forms of elements, labeling of classes and characters for the individual types are explained in detail in the introductions to chapters Root systems and finite Coxeter groups and~Character tables for Coxeter groups.

Several computations in the literature concerning the irreducible
characters of finite Coxeter groups and Iwahori--Hecke algebras can now
be checked or re-computed by anyone who is willing to use **GAP** and
CHEVIE. Re-doing such computations and comparing with existing tables
has sometimes lead to the discovery of bugs in the programs or to
misprints in the literature. We believe that having the possibility of
repeating such computations and experimenting with the results has
increased the reliability of the data (and the programs).

For example, it is now a trivial matter to re-compute the tables of induce/restrict matrices (with the appropriate labeling of the characters) for exceptional finite Weyl groups (see Section ReflectionSubgroup). These matrices have various applications in the representation theory of finite reductive groups, see Lusztig's book cite[Ch.4]Lus85.

We ourselves have used these programs to prove results about the existence of elements with special properties in the conjugacy classes of finite Coxeter groups (see GP93, GM97), and to compute character tables of Iwahori--Hecke algebras of exceptional type (see Gec94, GM97). For a survey, see also Chv96.

Of course, our hope is that more applications will be added in the
future! For contributions to CHEVIE from outside (or one or several
among us) we have created a directory `contr`

in which the corresponding
files are distributed with CHEVIE. However, they do remain under the
authorship and the responsibility of their authors. Files from that
directory can be read into **GAP** using the command
`ReadChv("contr/filename")`

. At present, the directory `contr`

contains
the following files:

smallskip
noindent `murphy`

by A.~Mathas; it contains programs which allow
calculations with the Murphy basis of the Hecke algebra of type *A*.

smallskip
noindent `minrep`

by M.~Geck and G.~Pfeiffer; it contains programs (used
in GP93) for computing representatives of minimal length in the
conjugacy classes of finite Coxeter groups.

smallskip
noindent `brbase`

by M.~Geck and S.~Kim; it contains programs for
computing bi-grassmannians and the base for the Bruhat--Chevalley order
on finite Coxeter groups (see GK96).

smallskip
noindent `braidsup`

by J.~Michel; it contains some supplementary
programs for working with braids.

smallskip
noindent `chargood`

by M.~Geck and J.~Michel; it contains functions
(used in GM97) implementing algorithms to compute character tables
of Iwahori--Hecke algebras, especially that of type *E_8*.

medskip
Finally, it should be mentioned that there is also a MAPLE-part of
CHEVIE which contains generic character tables of finite groups of Lie
type and tables of Green functions. The conventions about data related to
the associated finite Weyl groups are compatible with those in the
present package. It is planned that, in the not too far future, the
MAPLE-part will be re-written in **GAP**.

medskip
noindent bf Acknowledgments. We wish to thank the Aachen **GAP** team
for general support over the last years.

We also gratefully acknowledge financial support by the DFG in the framework of the Forschungsschwerpunkt "Algorithmische Zahlentheorie und Algebra" since 1992.

We are indebted to Andrew Mathas for contributing a package with
functions for calculating the various Kazhdan-Lusztig bases in
Iwahori--Hecke algebras. (These functions have now become a part of the
file `kl.g`

.)

hfill St.~Andrews, Paris and Heidelberg, December 1996

Index

GAP 3.4.4

April 1997