85 Root systems and finite Coxeter groups

In this chapter we describe functions for dealing with finite Coxeter groups as permutation groups of root systems. A suitable reference for the general theory is, for example, the volume of Bourbaki Bou68. Finite Coxeter groups coincide with finite real reflection groups. If a finite Coxeter group can be defined over the rational numbers (it is a rational reflection group), it is called a Weyl group.

Root systems play an important role in mathematics; they classify semi-simple Lie algebras and algebraic groups. A root system is a set of roots defining reflections (see the chapter on finite reflection groups) generating the Weyl group. We treat at the same time other finite Coxeter groups by using a generalization of root systems to the non-crystallographic (non-rational) case.

We give now the definitions. Let V be a real vector space, V its dual and let ( , ) be the natural pairing between V and V. A root system in V is a finite set of vectors R (the roots), together with a map r→ r from R to a subset R of V (the coroots) such that:

For any r∈ R, we have (r,r)=2 and the reflection V→ V: x→ x- (r,x) r with root r and coroot r stabilizes R. If R does not span V we also have to impose the condition that the dual reflection V → V: y → y -(y,r)r stabilizes R. Note (r,r)=2 is equivalent to the condition that we have true reflections (of order 2).

We will only consider reduced root systems, i.e., such that the only elements of R colinear with a root r are r and -r.

A root system R is called crystallographic if (r,s) is an integer, for any s∈ R,r∈ R --- these are the root systems considered by Bourbaki.

The dimension of the subspace VR of V spanned by R will be called the semi-simple rank of R.

The subgroup W=W(R) of GL(V) generated by the `Reflection(r,r∨)` is a finite Coxeter group (see chapter Coxeter groups --- we describe explicitly below how to obtain the Coxeter generators from the root system). If the root system is crystallographic, the representation V of W is defined over the rational numbers, thus W is a Weyl group, in which case all finite-dimensional (complex) representations of W can be realized over the rational numbers. Weyl groups are characterized amongst finite Coxeter groups by the fact that all numbers m(i,j) in the Coxeter matrix are in {2,3,4,6}.

If we identify V with V by choosing a W-invariant bilinear form ( ; ), then we have r=2r/(r;r). A root system R is irreducible if it is not the union of two orthogonal subsets. If R is reducible then the corresponding Coxeter group is the direct product of the Coxeter groups associated with the irreducible components of R. The irreducible crystallographic root systems are classified by the following list of Dynkin diagrams. We show the labeling of the nodes given by the function `CartanMat` described below.

```         1   2   3           n                1   2   3           n
A_n   o---o---o-- . . . --o          B_n   o=<=o---o-- . . . --o

1 o
\    4             n                1   2   3           n
D_n   3 o---o---  . . . --o          C_n   o=>=o---o-- . . . --o
/
2 o

1   2             1   2   3   4          1   3   4   5   6
G_2   0->-0        F_4  o---o=>=o---o     E_6  o---o---o---o---o
6                                              |
o 2

1   3   4   5   6   7            1   3   4   5   6   7   8
E_7   o---o---o---o---o---o       E_8  o---o---o---o---o---o---o
|                                |
o 2                              o 2```

These diagrams encode the presentation of the Coxeter group W as follows: the vertices represent the set `S` of generating reflections; an edge is drawn between s and t if the order m(s,t) of st is greater than 2; the edge is single if m(s,t)=3, double if m(s,t)=4, triple if m(s,t)=6. The arrows indicate the relative root lengths when W has more than one orbit on R, as explained below; we get the Coxeter Diagram, which describes the underlying Weyl group, if we ignore the arrows: we see that the root systems Bn and Cn correspond to the same Coxeter group.

To complete the classification of finite Coxeter groups, we need to add the following Coxeter diagrams:

```             1   2                 1   2   3          1   2   3   4
I_2(m)    o---o            H_3  o---o---o     H_4  o---o---o---o
m                     5                  5           ```

where a single edge has the value m(s,t) written above if m(s,t)∉ {2,3,4,6}. These correspond to non-crystallographic groups, excepted for the special cases I2(3)=A2, I2(4)=B2 and I2(6)=G2.

Let us now describe how the root systems are encoded in these diagrams. Let R be a root system in V. Then we can choose a linear form on V which vanishes on no element of R. According to the sign of the value of this linear form on a root r ∈ R we call r positive or negative. Then there exists a unique subset of the set of positive roots, called the set of simple roots, such that any positive root is a linear combination with non-negative coefficients of simple roots. It can be shown that any two sets of simple roots, corresponding to different choices of linear forms, can be transformed into each other by a unique element of W(R). Hence, since the pairing between V and V is W-invariant, if {r1,...,rn} is a set of simple roots and if we define the Cartan matrix as being the n times n matrix C={ri(rj)}ij, this matrix is unique up to simultaneous permutation of rows and columns. It is this matrix which is encoded in a Dynkin diagram, as follows.

The indices for the rows of C label the nodes of the diagram. The edges, for i ≠ j, are given as follows. If Cij and Cji are integers such that |Cij| ≥ |Cji| the vertices are connected by |Cij| lines, and if |Cij|>1 then we put an additional arrow on the lines pointing towards the node with label i. In all other cases, we simply put a single line equipped with the unique integer pij ≥ 1 such that CijCji=cos2 (π/pij).

It is important to note that, conversely, the whole root system can be recovered from the simple roots: the set S of reflections in W(R) corresponding to the simple roots are called simple reflections. They are precisely the generators corresponding to the vertices of the Coxeter diagram. Each root is in the orbit of a simple root, so that R is obtained as the orbit of the simple roots under the group generated by the simple reflections. The restriction of the simple reflections to VR is determined by the Cartan matrix, so R is determined by the Cartan matrix and the set of simple roots.

The Cartan matrix corresponding to one of the above irreducible root systems (with the specified labeling) is returned by the command `CartanMat` which takes as input a string giving the type (e.g., `"A"`, `"B"`, ..., `"I"`) and a positive integer giving the rank. For type I2(m), we give as a third argument the integer m. This function returns a matrix (that is in GAP3, a list of lists) with entries in or in a cyclotomic extension of the rationals. Given two Cartan matrices, their matrix direct sum, corresponding to the orthogonal direct sum of the root systems, ) can be produced by the function `DiagonalMat`.

The function `CoxeterGroup` takes as input some data which determine the roots and the coroots and produces a GAP3 permutation group record, where the Coxeter group is represented by its faithful permutation action on the root system R, with additional components holding information about R and the additional components which makes it also a Coxeter group record. If we label the positive roots by `[1 .. N]`, and the negative roots by `[N+1 .. 2*N]`, then each simple reflection is represented by the permutation of `[ 1 .. 2*N ]` which it induces on the roots.

The function `CoxeterGroup` has several forms; in one of them, the argument is the Cartan matrix of the root system This constructs a root system where the simple roots are the canonical basis of V, and the matrix of the coroots expressed in the dual basis of V is then equal to the Cartan matrix.

If one only wants to work with Cartan matrices with a labeling as specified by the above list, the function call can be simplified. Instead of `CoxeterGroup( CartanMat("D", 4 ) )` the following is also possible.

```    gap> W := CoxeterGroup( "D", 4 );       # Coxeter group of type D4
CoxeterGroup("D",4)
gap> PrintArray(CartanMat(W));
[[ 2,  0, -1,  0],
[ 0,  2, -1,  0],
[-1, -1,  2, -1],
[ 0,  0, -1,  2]]```

Also, the Coxeter group record associated to a direct sum of irreducible root systems with the above standard labeling can be obtained by listing the types of the irreducible components:

```    gap> W := CoxeterGroup( "A", 2, "B", 2 );;
gap> PrintArray(CartanMat(W));
[[ 2, -1,  0,  0],
[-1,  2,  0,  0],
[ 0,  0,  2, -2],
[ 0,  0, -1,  2]]```

The same record is constructed by applying `CoxeterGroup` to the matrix `CartanMat("A",2,"B",2)` or to ```DiagonalMat(CartanMat("A",2), CartanMat("B",2))```, or even by calling `CoxeterGroup("A",2)*CoxeterGroup("B",2)`

The following sections give more details on how to work with the elements of W and different representations for them (permutations, reduced expressions, matrices).

85.1 CartanMat for Dynkin types

`CartanMat( type, n )`

returns the Cartan matrix of Dynkin type type and rank n. Admissible types are the strings `"A"`, `"B"`, `"C"`, `"D"`, `"E"`, `"F"`, `"G"`, `"H"`, `"I"`, `"Bsym"`, `"Gsym"`, `"Fsym"`, `"Isym"`, `"B?"`, `"G?"`, `"F?"`, `"I?"`.

```    gap> C := CartanMat( "F", 4 );;
gap> PrintArray( C );
[[ 2, -1,  0,  0],
[-1,  2, -1,  0],
[ 0, -2,  2, -1],
[ 0,  0, -1,  2]]```

For type I2(m), which is in fact an infinity of types depending on the number m, a third argument is needed specifying the integer m so the syntax is in fact `CartanMat( "I", 2, m )`:

```    gap> CartanMat( "I", 2, 5 );
[ [ 2, E(5)^2+E(5)^3 ], [ E(5)^2+E(5)^3, 2 ] ]```

The types like `"Bsym"` specify (non crystallographic) root systems where all roots have the same length, which is necessary for some automorphisms to exist, like the outer automorphism of B2 which exchanges the two generating reflections:

```    gap> CartanMat("Bsym",2);
[ [ 2, -E(8)+E(8)^3 ], [ -E(8)+E(8)^3, 2 ] ]```

Finally, for irreducible root systems which have two root lengths, the forms like `"B?"` allow to specify arbitrary root systems (up to a scalar) by giving explicitly as a third argument the coefficient by which to multiply the second conjugacy class of roots compared to the default Cartan matrix for that type.

```    gap> CartanMat("B?",2,1); # the same as C2
[ [ 2, -1 ], [ -2, 2 ] ]```

`CartanMat( type1, n1, ... , typek, nk )`

returns the direct sum of `CartanMat( type1, n1 )`, ..., `CartanMat( typek, nk )`. One can use as argument a computed list of types by ```ApplyFunc( CartanMat, [ type1, n1, ... , typek, nk ] )```.

85.2 CoxeterGroup

`CoxeterGroup( C )`

`CoxeterGroup( type1, n1, ... , typek, nk )`

`CoxeterGroup( rec )`

This function returns a permutation group record containing the basic information about the Coxeter group and the root system determined by its arguments. In the first form the canonical basis of a real vector space V of dimension `Length(C)` is taken as simple roots, and the lines of the matrix C express the set of coroots in the dual basis of V. The matrix C must be a valid Cartan matrix (see CartanMat). The length of C is called the semisimple rank of the Coxeter datum. This function creates a semisimple root system, where the length of C is also equal to the dimension of V, called the rank. The function ReflectionSubgroup can create a Coxeter group record where the rank is not equal to the semisimple rank.

The second form is equivalent to

`CoxeterGroup(CartanMat(type1, n1, ..., typek, nk))`.

The resulting record, that we will call a Coxeter datum, has additional entries describing various information on the root system and Coxeter group that we describe below.

The last form takes as an argument a record which has a field `coxeter` and returns the value of this field. This is used to return the Coxeter group of objects derived from Coxeter groups, such as Coxeter cosets, Hecke algebras and braid elements.

We document the following entries in a Coxeter datum record which are guaranteed to remain present in future versions of the package. Other undocumented entries should not be relied upon, they may change without notice.

`isCoxeterGroup`, `isDomain`, `isGroup`, `isPermGroup`, `isFinite`:

`true`

`cartan`:

the Cartan matrix C

`roots`:

the root vectors, given as linear combinations of simple roots. The first `N` roots are positive, the next `N` are the corresponding negative roots. Moreover, the first `SemisimpleRank(W)` roots are the simple roots. The positive roots are ordered by increasing height.

`coroots`:

the same information for the coroots. The coroot corresponding to a given root is in the same relative position in the list of coroots as the root in the list of roots.

`N`:

the number of positive roots

`rootLengths`:

the vector of length of roots the simple roots. The shortest roots in an irreducible subsystem are given the length 1. The others then have length 2 (or 3 in type G2). The matrix of the W-invariant bilinear form is given by `List([1..SemisimpleRank(W)], i->W.rootLengths[i]*W.cartan[i])/2`.

`orbitRepresentative`:

this is a list of same length as `roots`, which for each root, gives the smallest index of a root in the same W-orbit.

`orbitRepresentativeElements`:

a list of same length as `roots`, which for the i-th root, gives an element w of W of minimal length such that `i=orbitRepresentative[i]^w`.

`matgens`:

the matrices (in row convention --- that is the matrices operate from the right) of the simple reflections of the Coxeter group.

`generators`:

the generators as permutations of the root vectors. They are given in the same order as the first `SemisimpleRank(W)` roots.

```    gap> W := CoxeterGroup( "A", 4 );;
gap> PrintArray( W.cartan );
[[ 2, -1,  0,  0],
[-1,  2, -1,  0],
[ 0, -1,  2, -1],
[ 0,  0, -1,  2]]
gap> W.matgens;
[ [ [ -1, 0, 0, 0 ], [ 1, 1, 0, 0 ], [ 0, 0, 1, 0 ], [ 0, 0, 0, 1 ] ],
[ [ 1, 1, 0, 0 ], [ 0, -1, 0, 0 ], [ 0, 1, 1, 0 ], [ 0, 0, 0, 1 ] ],
[ [ 1, 0, 0, 0 ], [ 0, 1, 1, 0 ], [ 0, 0, -1, 0 ], [ 0, 0, 1, 1 ] ],
[ [ 1, 0, 0, 0 ], [ 0, 1, 0, 0 ], [ 0, 0, 1, 1 ], [ 0, 0, 0, -1 ] ]
]
gap> W.roots;
[ [ 1, 0, 0, 0 ], [ 0, 1, 0, 0 ], [ 0, 0, 1, 0 ], [ 0, 0, 0, 1 ],
[ 1, 1, 0, 0 ], [ 0, 1, 1, 0 ], [ 0, 0, 1, 1 ], [ 1, 1, 1, 0 ],
[ 0, 1, 1, 1 ], [ 1, 1, 1, 1 ], [ -1, 0, 0, 0 ], [ 0, -1, 0, 0 ],
[ 0, 0, -1, 0 ], [ 0, 0, 0, -1 ], [ -1, -1, 0, 0 ],
[ 0, -1, -1, 0 ], [ 0, 0, -1, -1 ], [ -1, -1, -1, 0 ],
[ 0, -1, -1, -1 ], [ -1, -1, -1, -1 ] ]```

85.3 Operations and functions for finite Coxeter groups

All permutation group operations are defined on Coxeter groups, as well as all functions defined for finite reflection groups. However, the following operations and functions have been specially written to take advantage of the particular structure of real reflection groups:

`=`:

Two Coxeter data are equal if they are equal as permutation groups and the fields `simpleRoots` and `simpleCoroots` agree (independently of the value of any other bound fields).

`Print`:

prints a Coxeter group in a form that can be input back in GAP3 as a Coxeter group.

`Size`:

uses the classification of Coxeter groups to work faster (specifically, uses the function `ReflectionDegrees`).

`Elements`:

returns the set of elements. They are computed using CoxeterElements. (Note that in an earlier version of the package the elements were sorted by length. You can get such a list by `Concatenation( List( [1..W.N], i -> CoxeterElements(W, i)))`)

`ConjugacyClasses`:

Uses classification of Coxeter groups to work faster, and the resulting list is given in the same order as the result of `ChevieClassInfo` (see ChevieClassInfo). Each `Representative` given by CHEVIE has the property that it is of minimal Coxeter length in its conjugacy class and is a "good" element in the sense of GM97.

`CharTable`:

Uses the classification of Coxeter groups to work faster, and the result has better labeling than the default (see Classes and representations for reflection groups).

`PositionClass`, `ClassInvariants`, `FusionConjugacyClasses`:

Use the classification of Coxeter groups to work faster.

`DecompositionMatrix(W,p)`:

Returns the p-modular decomposition matrix for Weyl groups which have no component of type `D`.

Similarly, all functions for abstract Coxeter groups are available for finite Coxeter groups. However a few of them are implemented by more efficient methods. For instance, an efficient way of coding `IsLeftDescending(W,w,s)` is `s^w>W.N` (for reflection subgroups this has to be changed slightly: elements are represented as permutations of the roots of the parent group, so one needs to write `s^w>W.parentN`, or `W.rootRestriction[s^w]>W.N`). The functions `CoxeterWord`, `CoxeterLength`, `ReducedCoxeterWord`, `IsLeftDescending`, `FirstLeftDescending`, `LeftDescentSet` and `RightDescentSet` also have a special implementation. Finally, some functions for finite reflection groups which are implemented by more efficient methods, are `ReflectionType`, `ReflectionName`, `MatXPerm`, `Reflections`, `ReflectionDegrees`, `ReflectionCharValue`.

`PrintDiagram`:

Prints the Dynkin diagram of the root system (a more specific information that the Coxeter diagram, since it includes an indication of the relative root lengths).

```    gap> C := [ [ 2, 0, -1 ], [ 0, 2, 0 ], [ -1, 0, 2 ] ];;
gap> t := ReflectionType( C );
[ rec(rank    := 2,
series  := "A",
indices := [ 1, 3 ]), rec(rank    := 1,
series  := "A",
indices := [ 2 ]) ]
gap> PrintDiagram( t );
A2 1 - 3
A1 2
gap> PrintDiagram( CoxeterGroup( "C", 3) );
C3 1 >=> 2 - 3```

85.4 HighestShortRoot

`HighestShortRoot( W )`

Let W be an irreducible Coxeter group. `HighestShortRoot` computes the unique short root of maximal height of W. Note that if all roots have the same length then this is the unique root of maximal height, which can also be obtained by `W.roots[W.N]`. An error message is returned for W not irreducible.

```    gap> W := CoxeterGroup( "G", 2 );;  W.roots;
[ [ 1, 0 ], [ 0, 1 ], [ 1, 1 ], [ 1, 2 ], [ 1, 3 ], [ 2, 3 ],
[ -1, 0 ], [ 0, -1 ], [ -1, -1 ], [ -1, -2 ], [ -1, -3 ],
[ -2, -3 ] ]
gap> HighestShortRoot( W );
4
gap> W1 := CoxeterGroup( "A", 1, "B", 3 );;
gap> HighestShortRoot( W1 );
Error, CoxeterGroup("A",1,"B",3) should be irreducible
in
HighestShortRoot( W1 ) called from
main loop
brk>```

`BadPrimes( W )`

`BadPrimes( R )`

Let W be a Weyl group. A prime is bad for W if it divides a coefficient on the simple roots of some root. The function `BadPrimes` returns the list of prime which are bad for W.

Alternately the argument can be a set of integer vectors and then the function returns all prime numbers which divide one of their coefficients.

```    gap> W:=CoxeterGroup("E",8);
CoxeterGroup("E",8)
[ 2, 3, 5 ]
[ 2 ]```

85.6 PermMatY

`PermMatY( W, M )`

Let M be a linear transformation of the vector space V on which the Coxeter datum W acts which preserves the set of coroots. `PermMatY` returns the corresponding permutation of the coroots; it signals an error if M does not normalize the set of coroots.

```    gap>  W:=ReflectionSubgroup(CoxeterGroup("E",7),[1..6]);
ReflectionSubgroup(CoxeterGroup("E",7), [ 1, 2, 3, 4, 5, 6 ])
gap>  w0:=LongestCoxeterElement(W);;
gap> my:=MatYPerm(W,w0);;
gap> PermMatY( W, my ) = w0;
true```

85.7 Inversions

`Inversions( W, w )` Returns the inversions of the element w of the finite Coxeter group W, that is, the list of the indices of roots of the parent of W sent by w to negative roots. The element w can also be given as a word s1... sn, in which case the function returns inversions in the order of the roots of the reflections s1, s1 s2 s1,...,s1 s2... sn sn-1... s1.

```    gap> W:=CoxeterGroup("A",3);
CoxeterGroup("A",3)
gap> Inversions(W,W.1^W.2);
[ 1, 2, 4 ]
gap> Inversions(W,[1,2,1]);
[ 1, 4, 2 ]```

85.8 ElementWithInversions

`ElementWithInversions( W, N )`

W should be a finite Coxeter group and N a subset of `[1..W.N]`. Returns the element w of W such that N is the list of indices of positive roots which are sent to negative roots by w. Returns false if no such element exists.

```    gap> W:=CoxeterGroup("A",2);
CoxeterGroup("A",2)
gap> List(Combinations([1..W.N]),N->ElementWithInversions(W,N));
[ (), (1,4)(2,3)(5,6), false, (1,5)(2,4)(3,6), (1,6,2)(3,5,4),
(1,3)(2,5)(4,6), (1,2,6)(3,4,5), false ]```

85.9 DescribeInvolution

`DescribeInvolution( W, w )`

Given an involution w of a Coxeter group W, by a theorem of Richardson (rich82) there is a unique parabolic subgroup P of W such that that w is the longest element of P, and is central in P. `DescribeInvolution` returns I such that `P=ReflectionSubgroup(W,I)`, so that `w=LongestCoxeterElement(ReflectionSubgroup(W,I))`.

```    gap> W:=CoxeterGroup("A",2);
CoxeterGroup("A",2)
gap> w:=LongestCoxeterElement(W);
(1,5)(2,4)(3,6)
gap> DescribeInvolution(W,w);
[ 3 ]
gap> w=LongestCoxeterElement(ReflectionSubgroup(W,));
true```

85.10 ParabolicSubgroups

`ParabolicSubgroups( W )`

returns the list of all parabolic subgroups of W. These are the conjugates of the groups returned by `ParabolicRepresentatives(W)`; they are also in bijection with the flats of the hyperplane arrangement defined by W. To save memory, the list is given as a list of generating reflections for each group. For each element `I` of this list, one has to call `ReflectionSubgroup(W,I)` to actually get the corresponding group.

```    gap> ParabolicSubgroups(CoxeterGroup("A",3));
[ [  ], [ 1 ], [ 2 ], [ 3 ], [ 4 ], [ 5 ], [ 6 ], [ 1, 2 ], [ 1, 5 ],
[ 2, 3 ], [ 3, 4 ], [ 1, 3 ], [ 2, 6 ], [ 4, 5 ], [ 1, 2, 3 ] ]```

85.11 ExtendedReflectionGroup

`ExtendedReflectionGroup( W, M )`

This function creates an extended reflection group, which is represented as an object with two field, one recording a reflection group W on a vector space V, and the other a subgroup M of the linear group of V which normalizes W. Actually M should normalize the set of roots of W. If W is semisimple, that is `Rank(W)=SemisimpleRank(W)`, then one can give M as a group of permutations (of the roots of W), otherwise one must give M as a matrix group.

```    gap> W:=CoxeterGroup("F",4);
CoxeterGroup("F",4)
gap> D4:=ReflectionSubgroup(W,[1,2,9,16]);
ReflectionSubgroup(CoxeterGroup("F",4), [ 1, 2, 9, 16 ])
gap> t:=ReducedRightCosetRepresentatives(W,D4){[3,4]};
[ ( 2, 9)( 3,27)( 4, 7)( 5,11)(10,13)(12,15)(17,19)(20,22)(26,33)
(28,31)(29,35)(34,37)(36,39)(41,43)(44,46),
( 2, 9,16)( 3, 4,31)( 5,11,18)( 6,13,10)( 7,27,28)( 8,15,12)
(14,22,20)(17,19,21)(26,33,40)(29,35,42)(30,37,34)(32,39,36)
(38,46,44)(41,43,45) ]
gap> ExtendedReflectionGroup(D4,Group(t,()));
Extended(D4<9,2,1,16>,(2,9),(2,9,16))```

gap3-jm
11 Mar 2019