74 CHEVIE Version 3 -- a short introduction

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


Previous Up Next

GAP 3.4.4
April 1997