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
GAP 3.4.4