In this chapter we describe functions for dealing with general Coxeter groups.
A suitable reference for the general theory is, for example, the volume of Bourbaki Bou68; an English reference is the book of Humphreys Hum90.
A Coxeter group is a group W defined by a presentation of the form
〈 s1, ..., sn | (si sj)m(i,j)=1 for all i, j 〉 |
CoxeterGroupByCoxeterMatrix
); the faithfulness of this representation
in the main argument to prove that the order of si sj is exactly
m(i,j). Thus Coxeter groups are real reflection groups. The converse
need not be true if the set of reflecting hyperplanes has bad
topological properties, but it turns out that finite Coxeter groups are
the same as finite real reflection groups. The corresponding possible
Coxeter matrices have been completely classified, and the corresponding
groups play a deep role in several areas of mathematics.
One main reason general Coxeter groups are useful is that they have a
nice solution to the word problem. The length l(w) of an element w
of W is the minimum number of elements of S of which it is a product
(since the elements of S are involutions, we do not need inverses). An
expression of w of minimal length as a product of elements of S is
called a reduced word for w. The main property here is the exchange
lemma which states that if s∈ S and l(sw) ≤ l(w) then there
exists a reduced word s s2 ... sk of w which starts with s
(thus s2... sk is a reduced word of sw). Thus given s∈ S
and w∈ W, either l(sw)=l(w)+1 or l(sw)=l(w)-1 and we say in this
last case that s belongs to the left descent set of w. The
computation of reduced word for elements, and all kinds of word
problems, can be easily done if we know the left descent sets of
elements. For most Coxeter groups that we will be able to build in
CHEVIE, this left descent set can be easily determined (see e.g.
CoxeterGroupSymmetricGroup
below), so this suggests how to deal with
Coxeter groups in CHEVIE: they are reflection groups, so the
following fields in the group record defined:
.nbGeneratingReflections
:
.reflections
:W.reflections{[1..W.nbGeneratingReflections]}
is the set S.
the above names are used instead of names like CoxeterGenerators
and
CoxeterRank
since the Coxeter groups are reflection groups and we
want the functions for reflection groups applicable to them (similarly,
if you have read the chapter on reflections and reflection groups, you
will realize that there is also a field .OrdersGeneratingReflections
which contains only 2's). The main additional function which allows to
compute within Coxeter groups is:
.operations.IsLeftDescending(W,w,i)
:
For Coxeter groups constructed in CHEVIE an IsLeftDescending
operation is provided, but you can construct your own Coxeter
groups just by filling the above fields (see the function
CoxeterGroupSymmetricGroup
below for an example). It should be noted
than you can make into a Coxeter group any kind of group: finitely
presented groups, permutation groups or matrix groups, if you fill
appropriately the above fields; and the given generating reflection do
not have to be the generators of the group (but they could be; they
usually are, actually, in CHEVIE). All functions for Coxeter group
and Hecke algebras will then work for your Coxeter groups (using
your function IsLeftDescending
).
A common occurrence in CHEVIE code for Coxeter groups is a loop like:
First([1..W.semisimpleRank],x->IsLeftDescending(W,w,x))
which actually for reflection subgroups becomes
First(W.rootRestriction{[1..W.semisimpleRank]},x->IsLeftDescending(W,w,x))
where the overhead is quite large, since dispatching on the group type
(e.g. finite or infinite) is done in IsLeftDescending
. To improve this
case, if you provide a function FirstLeftDescending(W,w)
it will be
called instead of the above loop (if you do not provide one the above
loop will be used). Such a function provided by CHEVIE in the programs
for finite Coxeter groups is 3 times more efficient than the above loop.
Because of the easy solution of the word problem in Coxeter groups,
a convenient way to represent their elements is as words in the
Coxeter generators. They are represented in CHEVIE as lists of
labels for the generators. By default these labels are given as
the index of a generator in S, so a Coxeter word is just a
list of integers which run from 1 to the length of S. This
can be changed to reflect a more conventional notation for some
groups, by changing the field .reflectionsLabels
of the Coxeter group
which contains the labels used for the Coxeter words (by default it
contains [1..W.nbGeneratingReflections]
). For a Coxeter group with 2
generators, you could for instance set this field to "st"
to use
words such as "sts"
instead of [1,2,1]
. For reflection subgroups,
this is used in CHEVIE by setting the reflection labels to the
indices of the generators in the set S of the parent group (which is
given by .rootInclusion
).
The functions CoxeterWord
and EltWord
will do the conversion between
Coxeter words and elements of the group.
gap> W := CoxeterGroup( "D", 4 );; gap> p := EltWord( W, [ 1, 3, 2, 1, 3 ] ); ( 1,14,13, 2)( 3,17, 8,18)( 4,12)( 5,20, 6,15)( 7,10,11, 9)(16,24) (19,22,23,21) gap> CoxeterWord( W, p ); [ 1, 3, 1, 2, 3 ] gap> W.reflectionsLabels:="stuv"; "stuv" gap> CoxeterWord(W,p); "sustu"
We notice that the word we started with and the one that we
ended up with, are not the same. But of course, they represent
the same element of W. The reason for this difference is that
the function CoxeterWord
always computes a reduced word which is
the lexicographically smallest among all possible expressions of an
element of W as a word in the fundamental reflections. The function
ReducedCoxeterWord
does the same but with a word as input (rather than
an element of the group). Below are some other possible computations
with the same Coxeter group as above:
gap> LongestCoxeterWord( W ); # the (unique) longest element in W [ 1, 2, 3, 1, 2, 3, 4, 3, 1, 2, 3, 4 ] gap> w0 := LongestCoxeterElement( W ); # = EltWord( W, last ) ( 1,13)( 2,14)( 3,15)( 4,16)( 5,17)( 6,18)( 7,19)( 8,20)( 9,21) (10,22)(11,23)(12,24) gap> CoxeterLength( W, w0 ); 12 gap> List( Reflections( W ), i -> CoxeterWord( W, i ) ); [ "s", "t", "u", "v", "sus", "tut", "uvu", "stust", "suvus", "tuvut", "stuvust", "ustuvustu" ] gap> l := List( [1 .. W.N+1], x -> CoxeterElements( W, x-1 ) );; gap> List( l, Length ); [ 1, 4, 9, 16, 23, 28, 30, 28, 23, 16, 9, 4, 1 ]
The above line tells us that there is 1 element of length 0, there are 4 elements of length 4, etc.
For many basic functions (like Bruhat
, CoxeterLength
, etc.) we have
chosen the convention that the input is an element of a Coxeter group
(rather than a Coxeter word). As a rule of thumb one should keep in mind
that for a Coxeter group which is a permutation group, if in some
application one has to do a lot of computations with Coxeter group
elements then using the low level GAP functions for permutations is
usually much faster than manipulating lists of reduced expressions.
Before describing functions applicable to Coxeter groups and Coxeter words we describe functions which make two familiar Coxeter groups that we will use in our examples.
CoxeterGroupSymmetricGroup( n )
returns the symmetric group on n letters as a Coxeter group. We give the code of this function as it is a good example on how to make a Coxeter group:
CoxeterGroupSymmetricGroup := function ( n ) local W; W := SymmetricGroup( n ); W.reflections := List( [ 1 .. n - 1 ], i->(i,i + 1) ); W.operations.IsLeftDescending := function ( W, w, i ) return i ^ w > (i + 1) ^ w; end; AbsCoxOps.CompleteCoxeterGroupRecord( W ); return W; end;
In the above, we first set the generating reflections of
W to be the elementary transpositions (i,i+1)
(which are
reflections in the natural representation of the symmetric group
permuting the standard basis of an n-dimensional vector space),
then give the IsLeftDescending
function (which just checks
if (i,i+1)
is an inversion of the permutation). Finally,
AbsCoxOps.CompleteCoxeterGroupRecord
is a service routine which fills
other fields from the ones we gave. We can see what it did by doing:
gap> PrintRec(CoxeterGroupSymmetricGroup(3)); rec( isDomain := true, isGroup := true, identity := (), generators := [ (1,3), (2,3) ], operations := ..., isPermGroup := true, isFinite := true, 1 := (1,3), 2 := (2,3), degree := 3, reflections := [ (1,2), (2,3) ], nbGeneratingReflections := 2, generatingReflections := [ 1 .. 2 ], OrdersGeneratingReflections:= [ 2, 2 ], isCoxeterGroup := true, reflectionsLabels := [ 1 .. 2 ], coxeterMat := [ [ 1, 3 ], [ 3, 1 ] ], orbitRepresentative := [ 1, 1 ], longestElm := (1,3), longestCoxeterWord := [ 1, 2, 1 ], N := 3 )
We do not indicate all the fields here. Some are there for
technical reasons and may change from version to version of
CHEVIE. Among the added fields, we see nbGeneratingReflections
(taken to be Length(W.reflections)
if we do not give it),
.OrdersGeneratingReflections
, the Coxeter matrix .coxeterMat
, a
description of conjugacy classes of the generating reflections given in
.orbitRepresentative
(whose i-th entry is the smallest index of a
reflection conjugate to .reflections[i]
), .reflectionsLabels
(the
default labels used for Coxeter word). At the end are 3 fields which are
computed only for finite Coxeter groups: the longest element, as an
element and as a Coxeter word, and in W.N
the number of reflections in
W (which is also the length of the longest Coxeter word).
76.2 CoxeterGroupHyperoctaedralGroup
CoxeterGroupHyperoctaedralGroup( n )
returns the hyperoctaedral group of rank n as a Coxeter group. It is
given as a permutation group on 2n letters, with Coxeter generators
the permutations (i,i+1)(2n+1-i,2n-i)
and (n,n+1)
.
gap> CoxeterGroupHyperoctaedralGroup(2); Group( (2,3), (1,2)(3,4) )
This function requires the package "chevie" (see RequirePackage).
CoxeterMatrix( W )
return the Coxeter matrix of the Coxeter group W, that is the matrix
whose entry m[i][j]
contains the order of gi*gj where gi is
the i-th Coxeter generator of W. An infinite order is represented by
the entry 0.
gap> W:=CoxeterGroupSymmetricGroup(4); Group( (1,4), (2,4), (3,4) ) gap> CoxeterMatrix(W); [ [ 1, 3, 2 ], [ 3, 1, 3 ], [ 2, 3, 1 ] ]
This function requires the package "chevie" (see RequirePackage).
76.4 CoxeterGroupByCoxeterMatrix
CoxeterGroupByCoxeterMatrix( m )
returns the Coxeter group whose Coxeter matrix is m. The group
is constructed as a matrix group, using the standard reflection
representation for Coxeter groups. This is the representation on a real
vector space V of dimension Length(m)
defined as follows : if
es is a basis of V indexed by the lines of m, we make the s-th
reflection act by s(x)=x-2〈 x, es〉 es where the scalar
product on V defined by 〈 es,et〉=-cos(π/m[s,t])
(where by convention π/m[s,t]=0 if m[s,t]=∞, which is
represented in CHEVIE by setting m[s,t]:=0
). In the example below
the affine Weyl group ~ A2 is constructed, and then ~
A1.
gap> m:=[[1,3,3],[3,1,3],[3,3,1]];; gap> W:=CoxeterGroupByCoxeterMatrix(m); CoxeterGroupByCoxeterMatrix([ [ 1, 3, 3 ], [ 3, 1, 3 ], [ 3, 3, 1]]) gap> CoxeterWords(W,3); [ [ 1, 3, 2 ], [ 1, 2, 3 ], [ 1, 2, 1 ], [ 1, 3, 1 ], [ 2, 1, 3 ], [ 3, 1, 2 ], [ 2, 3, 2 ], [ 2, 3, 1 ], [ 3, 2, 1 ] ] gap> CoxeterGroupByCoxeterMatrix([[1,0],[0,1]]); CoxeterGroupByCoxeterMatrix([ [ 1, 0 ], [ 0, 1 ] ])
This function requires the package "chevie" (see RequirePackage).
76.5 CartanMatFromCoxeterMatrix
CartanMatFromCoxeterMatrix( m )
The argument is a CoxeterMatrix for a finite Coxeter group W and the
result is a Cartan Matrix for the standard reflection representation of
W. Its diagonal terms are 2 and the coefficient between two
generating reflections s and t is -2cos(π/m[s,t]) (where by
convention π/m[s,t]=0 if m[s,t]=∞, which is represented in
CHEVIE by setting m[s,t]:=0
).
gap> m:=[[1,3],[3,1]]; [ [ 1, 3 ], [ 3, 1 ] ] gap> CartanMatFromCoxeterMatrix(m); [ [ 2, -1 ], [ -1, 2 ] ]
This function requires the package "chevie" (see RequirePackage).
76.6 Functions having a special method for general Coxeter groups
Some functions take advantage of the fact a group is a Coxeter group to use a better algorithm. A typical example is:
Elements(W)
For finite Coxeter groups, uses a recursive algorithm based on the construction of elements of a chain of parabolic subgroups
ReflectionSubgroup(W, J)
When I is a subset of [1..W.nbGeneratingReflections]
then the
reflection subgroup of W generated by W.reflections{I}
can
be generated abstractly (without any specific knowledge about the
representation of W) as a Coxeter group. This is what this routine
does: implement a special case of ReflectionSubgroup
which works
for arbitrary Coxeter groups (see ReflectionSubgroup). The actual
argument J should be reflection labels for W, i.e. be a subset of
W.reflectionsLabels
.
Similarly, the functions ReducedRightCosetRepresentatives
,
PermCosetsSubgroup
, work for reflection subgroups of the above form.
See the chapter on reflection subgroups for a description of these
functions.
CartanMat(W)
Returns CartanMatFromCoxeterMatrix(CoxeterMatrix(W))
(see
CartanMatFromCoxeterMatrix).
The functions ReflectionType
, ReflectionName
and all functions
depending on the classification of finite Coxeter groups work for finite
Coxeter groups. See the chapter on reflection groups for a description
of these functions.
These functions require the package "chevie" (see RequirePackage).
IsLeftDescending( W , w, i )
returns true
if and only if the i-th generating reflection
W.reflections[i]
is in the left descent set of the element w of W.
gap> W:=CoxeterGroupSymmetricGroup(3); Group( (1,3), (2,3) ) gap> IsLeftDescending(W,(1,2),1); true
This function requires the package "chevie" (see RequirePackage).
FirstLeftDescending( W , w )
returns the index in the list of generating reflections of W of the
first element of the left descent set of the element w of W (i.e.,
the first i such that if s=W.reflections[i]
then l(sw)<l(w)). It
is quite important to think of using this function rather than write
a loop like First([1..W.nbGeneratingReflections],IsLeftDescending)
,
since for particular classes of groups (e.g. finite Coxeter groups) the
function is much optimized compared to such a loop.
gap> W:=CoxeterGroupSymmetricGroup(3); Group( (1,3), (2,3) ) gap> FirstLeftDescending(W,(2,3)); 2
This function requires the package "chevie" (see RequirePackage).
LeftDescentSet( W, w )
The set of generators s such that l(sw)<l(w), given as a list of labels for the corresponding generating reflections.
gap> W:=CoxeterGroupSymmetricGroup(3); Group( (1,3), (2,3) ) gap> LeftDescentSet( W, (1,3)); [ 1, 2 ]
See also RightDescentSet.
This function requires the package "chevie" (see RequirePackage).
RightDescentSet( W, w )
The set of generators s such that l(ws)< l(w), given as a list of labels for the corresponding generating reflections.
gap> W := CoxeterGroup( "A", 2 );; gap> w := EltWord( W, [ 1, 2 ] );; gap> RightDescentSet( W, w ); [ 2 ]
See also LeftDescentSet.
This function requires the package "chevie" (see RequirePackage).
EltWord( W , w )
returns the element of W which corresponds to the Coxeter word w. Thus it returns a permutation if W is a permutation group (the usual case for finite Coxeter groups) and a matrix for matrix groups (such as affine Coxeter groups).
gap> W:=CoxeterGroupSymmetricGroup(4); Group( (1,4), (2,4), (3,4) ) gap> EltWord(W,[1,2,3]); (1,4,3,2)
See also CoxeterWord.
This function requires the package "chevie" (see RequirePackage).
CoxeterWord( W , w )
returns a reduced word in the standard generators of the Coxeter group W for the element w (represented as the GAP list of the corresponding reflection labels).
gap> W := CoxeterGroup( "A", 3 );; gap> w := ( 1,11)( 3,10)( 4, 9)( 5, 7)( 6,12);; gap> w in W; true gap> CoxeterWord( W, w ); [ 1, 2, 3, 2, 1 ]
The result of CoxeterWord
is the lexicographically smallest reduced
word for w (for the ordering of the Coxeter generators given by
W.reflections
).
See also EltWord and ReducedCoxeterWord.
This function requires the package "chevie" (see RequirePackage).
CoxeterLength( W , w )
returns the length of the element w of W as a reduced expression in the standard generators.
gap> W := CoxeterGroup( "F", 4 );; gap> p := EltWord( W, [ 1, 2, 3, 4, 2 ] ); ( 1,44,38,25,20,14)( 2, 5,40,47,48,35)( 3, 7,13,21,19,15) ( 4, 6,12,28,30,36)( 8,34,41,32,10,17)( 9,18)(11,26,29,16,23,24) (27,31,37,45,43,39)(33,42) gap> CoxeterLength( W, p ); 5 gap> CoxeterWord( W, p ); [ 1, 2, 3, 2, 4 ]
This function requires the package "chevie" (see RequirePackage).
ReducedCoxeterWord( W , w )
returns a reduced expression for an element of the Coxeter group W, which is given as a GAP list of reflection labels for the standard generators of W.
gap> W := CoxeterGroup( "E", 6 );; gap> ReducedCoxeterWord( W, [ 1, 1, 1, 1, 1, 2, 2, 2, 3 ] ); [ 1, 2, 3 ]
This function requires the package "chevie" (see RequirePackage).
BrieskornNormalForm( W , w )
Brieskorn Bri71 has noticed that if L(w) is the left descent
set of w (see LeftDescentSet), and if wL(w) is the longest
Coxeter element (see LongestCoxeterElement) of the reflection subgroup
WL(w) (not that this element is an involution), then wL(w)
divides w, in the sense that l(wL(w))+l(wL(w)-1w)=l(w).
We can now divide w by wL(w) and continue this process
with the quotient. In this way, we obtain a reduced expression
w=wL1 ... wLr where Li=L(wLi ... wLr) for
all i, which we call the Brieskorn normal form of w. The
function BrieskornNormalForm
will return a description of this form,
by returning the list of sets L(w) which describe the above
decomposition.
gap> W:=CoxeterGroup("E",8); CoxeterGroup("E",8) gap> w:=[ 2, 3, 4, 2, 3, 4, 5, 4, 2, 3, 4, 5, 6, 5, 4, 2, 3, 4, > 5, 6, 7, 6, 5, 4, 2, 3, 4, 5, 6, 7, 8 ];; gap> BrieskornNormalForm(W,EltWord(W,w)); [ [ 2, 3, 4, 5, 6, 7 ], [ 8 ] ] gap> EltWord(W,w)=Product(last,x-> > LongestCoxeterElement(ReflectionSubgroup(W,x))); true
This function requires the package "chevie" (see RequirePackage).
LongestCoxeterElement( W )
If W is finite, returns the unique element of maximal length of the Coxeter group W. May loop infinitely otherwise.
gap> LongestCoxeterElement( CoxeterGroup( "A", 4 ) ); ( 1,14)( 2,13)( 3,12)( 4,11)( 5,17)( 6,16)( 7,15)( 8,19)( 9,18) (10,20)
This function requires the package "chevie" (see RequirePackage).
LongestCoxeterWord( W )
If W is finite, returns a reduced expression in the standard generators for the unique element of maximal length of the Coxeter group W. May loop infinitely otherwise.
gap> LongestCoxeterWord( CoxeterGroup( "A", 4 ) ); [ 1, 2, 1, 3, 2, 1, 4, 3, 2, 1 ]
This function requires the package "chevie" (see RequirePackage).
CoxeterElements( W, l )
returns the list of all elements of W of Coxeter length l.
gap> W := CoxeterGroup( "G", 2 );; gap> e := CoxeterElements( W, 6 ); [ ( 1, 7)( 2, 8)( 3, 9)( 4,10)( 5,11)( 6,12) ] gap> e[1] = LongestCoxeterElement( W ); true
After the call to CoxeterElements(W,l)
, the list of elements of W
of
length l
is stored in the component elts[l+1]
of the record of W.
Thus W.elts[lw+1]
contains the list of all elements of length lw in
W. There are a number of programs (like criticalPairs
, see Chapter
Kazhdan-Lusztig polynomials and bases) which refer to the ordering of
the elements in these lists in W.elts
.
This function requires the package "chevie" (see RequirePackage).
CoxeterWords( W[, l] )
returns the list of all elements in the Coxeter group W. The ordering
is the same as that given by concatenating the lists of elements of
length 0,1,... obtained by the function CoxeterElements
. If the
second argument is specified, only elements of length l are returned
(this is the only form of the call which makes sense for infinite
Coxeter groups).
gap> CoxeterWords( CoxeterGroup( "G", 2 ) ); [ [ ], [ 2 ], [ 1 ], [ 2, 1 ], [ 1, 2 ], [ 2, 1, 2 ], [ 1, 2, 1 ], [ 2, 1, 2, 1 ], [ 1, 2, 1, 2 ], [ 2, 1, 2, 1, 2 ], [ 1, 2, 1, 2, 1 ], [ 1, 2, 1, 2, 1, 2 ] ]
This function requires the package "chevie" (see RequirePackage).
Bruhat( W, y, w[, ly, lw] )
returns true
, if the element y is less than or equal to the element
w of the Coxeter group W for the Bruhat order, and false
otherwise
(y is less than w if a reduced expression for y can be extracted
from one for w). The optional arguments ly, lw can contain the
Coxeter length of the elements y and w. (In a computation with many
calls to Bruhat
this may speed up the computation considerably.) See
Hum90, (5.9) and (5.10) for properties of the Bruhat order.
gap> W := CoxeterGroup( "H", 3 );; gap> w := EltWord( W, [ 1, 2, 1, 3 ] );; gap> b := Filtered( Elements( W ), i -> Bruhat( W, i, w, > CoxeterLength( W, i ), 4 ) );; gap> List( b, x -> CoxeterWord( W, x ) ); [ [ ], [ 3 ], [ 2 ], [ 2, 1 ], [ 2, 3 ], [ 2, 1, 3 ], [ 1 ], [ 1, 3 ], [ 1, 2 ], [ 1, 2, 1 ], [ 1, 2, 3 ], [ 1, 2, 1, 3 ] ]
This function requires the package "chevie" (see RequirePackage).
BruhatSmaller( W, w)
Returns a list whose i-th element is the list of elements of W
smaller for the Bruhat order that w and of Length i-1. Thus the
first element of the returned list contains only W.identity
and the
CoxeterLength(W,w)
-th element contains only w.
gap> W:=CoxeterGroupSymmetricGroup(3); Group( (1,3), (2,3) ) gap> BruhatSmaller(W,(1,3)); [ [ () ], [ (2,3), (1,2) ], [ (1,2,3), (1,3,2) ], [ (1,3) ] ]
This function requires the package "chevie" (see RequirePackage).
ReducedInRightCoset( W, w)
Let w be an element of a parent group of W whose action by
conjugation induces an automorphism of Coxeter groups on W, that is
sends the Coxeter generators of W to a conjugate set (but may not send
the tuple of generators to a conjugate tuple). ReducedInRightCoset
returns the unique element in the right coset W.w which is
W-reduced, that is which preserves the set of Coxeter generators of
W.
gap> W:=CoxeterGroupSymmetricGroup(6); Group( (1,6), (2,6), (3,6), (4,6), (5,6) ) gap> H:=ReflectionSubgroup(W,[2..4]); Subgroup( Group( (1,6), (2,6), (3,6), (4,6), (5,6) ), [ (2,3), (3,4), (4,5) ] ) gap> ReducedInRightCoset(H,(1,6)(2,4)(3,5)); (1,6)
This function requires the package "chevie" (see RequirePackage).
ForEachElement( W, f)
This functions calls f(x)
for each element x of the Coxeter group
W. It is quite useful when the Size
of W would make impossible to
call Elements(W)
. For example,
gap>i:=0;; gap>W:=CoxeterGroup("E",8);; gap>ForEachElement(W,function(x)i:=i+1; > if i mod 1000000=0 then Print("*\c");fi; > end);
prints a *
about every 10 seconds on a 1Ghz computer, so takes about
two hours to enumerate the whole group E8.
This function requires the package "chevie" (see RequirePackage).
GAP 3.4.4