Let W be a finite (possibly complex) reflection group on the vector space V. A reflection subgroup H of W is a subgroup generated by the reflections it contains. A parabolic subgroup of W is the fixator in W of some subset of V. By a difficult theorem of Steinberg (easy in the real case) a parabolic subgroup is a reflection subgroup.
The function ReflectionSubgroup can be used to construct a reflection
subgroup of W. It takes as arguments the original record for W and a
list of indices for the reflections.
If V is real, so that W is a Coxeter group with generators S, then {wsw-1 | w ∈ W, s∈ S} is the set of all reflections in W. A reflection subgroup generated by a subset of S is parabolic; it is called standard parabolic subgroup of W. Any parabolic subgroup is conjugate to some standard parabolic subgroup. Let R be the set of roots of W, and let Q be the set of roots of H, that is the set of roots for which the corresponding reflection lies in H; by Steinberg's theorem it can be seen that a reflection subgroup H which is not parabolic is characterized by the fact that Q is not closed under linear combinations in R.
It is a theorem discovered by Deodhar Deo89 and Dyer Dye90
independently at the same time that a reflection subgroup H of a
Coxeter group has a canonical set of fundamental roots even if it is not
parabolic: a fundamental system of roots for H is given by the
positive roots t ∈ Q such that the subset of R of roots whose sign
is changed by the reflection with root t meets Q in the single
element t. This is used by the routine ReflectionSubgroup to
determine the root system Q of a reflection subgroup H.
gap> W := CoxeterGroup( "G", 2 );
CoxeterGroup("G",2)
gap> W.roots[4];
[ 1, 2 ]
gap> H := ReflectionSubgroup( W, [ 2, 4 ] );
ReflectionSubgroup(CoxeterGroup("G",2), [ 2, 3 ])
gap> PrintDiagram( H ); # not a parabolic subgroup
~A2 2 - 3
We see that the result of the above algorithm is that W.roots[2] and
W.roots[3] form a system of simple roots in H.
The line containing the Dynkin diagram of H introduces a convention:
we use the notation "~A" to denote a root subsystem of type "A"
generated by short roots.
We now point the differences which occur when considering complex
reflection groups. First, a subgroup generated by a subset of the
standard generators need not always be parabolic, if W needs more than
dim V reflections to be generated. The type of a reflection subgroup
is not known a priori, but CHEVIE will try to determine it if you
call ReflectionType or any operation which needs the classification on
the constructed subgroup. However there are no canonical way to choose
the generators; CHEVIE will try to choose generators giving the same
Cartan matrix as the one for the standard group of the same type defined
by CHEVIE; failing that, it will at least try to find generators
which satisfy the appropriate braid relations.
The record for a reflection subgroup contains additional components the
most important of which is rootInclusion which gives the positions of
the roots of H in the roots of W:
gap> H.rootInclusion;
[ 2, 3, 4, 8, 9, 10 ]
The inverse (partial) map is stored in H.rootRestriction.
If H is a standard parabolic subgroup of a Coxeter group W then the length function on H (with respect to its set of generators) is the restriction of the length function on W. This need not no longer be true for arbitrary reflection subgroups of W:
gap> CoxeterLength( W, H.generators[2] );
3
gap> CoxeterLength( H, H.generators[2] );
1
In GAP3, finite reflection groups W are represented as permutation
groups on a set of roots. Consequently, a reflection subgroup H
⊆ W is a permutation subgroup, i.e., its elements are
represented as permutations of the roots of the parent group. This
has to be kept in mind when working with reduced expressions and
functions like CoxeterWord, and EltWord.
Reduced words in simple reflections of H:
gap> el := CoxeterWords( H );
[ [ ], [ 2 ], [ 3 ], [ 2, 3 ], [ 3, 2 ], [ 2, 3, 2 ] ]
Reduced words in the generators of H:
gap> el1 := List( el, x -> H.rootRestriction{ x } );
[ [ ], [ 1 ], [ 2 ], [ 1, 2 ], [ 2, 1 ], [ 1, 2, 1 ] ]
Permutations on the roots of W:
gap> el2 := List( el, x -> EltWord( H, x ) );
[ (), ( 1, 5)( 2, 8)( 3, 4)( 7,11)( 9,10),
( 1,12)( 2, 4)( 3, 9)( 6, 7)( 8,10),
( 1, 5,12)( 2,10, 3)( 4, 9, 8)( 6, 7,11),
( 1,12, 5)( 2, 3,10)( 4, 8, 9)( 6,11, 7),
( 2, 9)( 3, 8)( 4,10)( 5,12)( 6,11) ]
Reduced words in the generators of W:
gap> List( el2, x -> CoxeterWord( W, x ) );
[ [ ], [ 2 ], [ 1, 2, 1 ], [ 2, 1, 2, 1 ], [ 1, 2, 1, 2 ],
[ 2, 1, 2, 1, 2 ] ]
Another basic result about reflection subgroups of Coxeter groups is that each coset of H in W contains a unique element of minimal length. Since a coset is a subset of W, the length of elements is taken with respect to the roots of W. See ReducedRightCosetRepresentatives.
In many applications it is useful to know the decomposition of
the irreducible characters of W when we restrict them from W
to a reflection subgroup H. In order to apply the usual GAP3
functions for inducing and restricting characters and computing scalar
products, we need to know the fusion map for the conjugacy classes of
H into those of W. This is done, as usual, with the GAP3
function FusionConjugacyClasses, which calls a special implementation
for Coxeter groups. The decomposition of induced characters into
irreducibles then is a simple matter of combining some functions which
already exist in GAP3. The package CHEVIE provides a function
InductionTable which performs this job.
gap> W := CoxeterGroup( "G", 2 );;
gap> W.roots[4];
[ 1, 2 ]
gap> H := ReflectionSubgroup( W, [ 2, 4 ] );;
gap> Display( InductionTable( H, W ) );
Induction from ~A2 to G2
|111 21 3
_____________________
phi{1,0} | . . 1
phi{1,6} | 1 . .
phi{1,3}' | . . 1
phi{1,3}'' | 1 . .
phi{2,1} | . 1 .
phi{2,2} | . 1 .
We have similar functions for the j-induction and the J-induction of characters. These operations are obtained by truncating the induced characters by using the a-invariants and b-invariants associated with the irreducible characters of W (see jInductionTable for Macdonald-Lusztig-Spaltenstein induction and JInductionTable).
ReflectionSubgroup( W, r )
Returns the reflection subgroup of the real or complex reflection group W generated by the reflections with roots specified by r. r is a list of indices specifying a subset of the roots of W.
A reflection subgroup H of W is a permutation subgroup, and otherwise has the same fields as W, with some new ones added which express the relationship with the parent W:
rootInclusion:
parentN:
rootRestriction:2*H.parentN with entries in
positions H.rootInclusion bound to [1..2*H.N].
A reflection group which is not a subgroup actually also contains these
fields, set to the trivial values: rootInclusion = [ 1 .. 2*W.N ],
parentN = W.N and rootRestriction = [ 1 .. 2*W.N ].
With these fields, the method IsLeftDescending(H,w,i) is written
(where w is given as a permutation of the roots of the parent)
H.rootInclusion[i]^w>H.parentN
ReflectionSubgroup returns a subgroup of the parent group of the
argument (like the GAP3 function Subgroup).
gap> W := CoxeterGroup( "F", 4 );;
gap> H := ReflectionSubgroup( W, [ 1, 2, 11, 20 ] );
ReflectionSubgroup(CoxeterGroup("F",4), [ 1, 2, 9, 16 ])
gap> ReflectionName( H ); # not a parabolic subgroup
"D4"
gap> H.rootRestriction;
[ 1, 2,,, 5,,,, 3,, 6,,, 8,, 4,, 7,, 9,, 10, 11, 12, 13, 14,,, 17,,,,
15,, 18,,, 20,, 16,, 19,, 21,, 22, 23, 24 ]
gap> ReflectionSubgroup( H, [ 1, 2, 6 ] );
ReflectionSubgroup(CoxeterGroup("F",4), [ 1, 2, 3 ])
88.2 Functions for reflection subgroups
All functions for Reflection groups are actually defined for reflection
subgroups, provided their reflection type is known (this is automatic in
the Coxeter case, otherwise use ReflectionType as mentioned in
introduction). The generators for the subgroups are labeled according to
the corresponding number of the root they represent in the parent group.
This affects the labeling given by all functions dealing with words and
generators, e.g., PrintDiagram or EltWord.
gap> W := CoxeterGroup( "F", 4 );
CoxeterGroup("F",4)
gap> H := ReflectionSubgroup( W, [ 10, 11, 12 ] );
ReflectionSubgroup(CoxeterGroup("F",4), [ 10, 11, 12 ])
gap> PrintDiagram( H );
B2 10 <=< 11
~A1 12
gap> LongestCoxeterWord( H );
[ 10, 11, 10, 11, 12 ]
Note that for the functions ReflectionType, ReflectionName and
PrintDiagram for Coxeter subgroups, an irreducible subsystem which
consists of short roots in a system which has longer roots (i.e., type
"B", "C", "G" or "F") is labeled as type "~A".
ReducedInRightCoset( H , w ):ReducedInRightCoset returns the unique element in the right coset
H.w which sends all roots of H to positive roots.
gap> W := CoxeterGroup("F", 4 );;
gap> H := ReflectionSubgroup( W, [ 1, 2, 9, 16 ] );;
gap> PrintDiagram( H );
D4 9
\
1 - 16
/
2
gap> w := EltWord( W, [ 3, 2, 3, 4, 3, 2 ] );;
gap> f := ReducedInRightCoset( H, w );;
gap> CoxeterWord( W, f );
[ 4, 3 ]
gap> H.rootInclusion{[ 1 ..4 ]};
[ 1, 2, 9, 16 ]
The triality automorphism of D4 is induced by f:
gap> OnTuples( H.rootInclusion{[ 1 .. 4 ]}, f );
[ 1, 9, 16, 2 ]
88.3 ReducedRightCosetRepresentatives
ReducedRightCosetRepresentatives( W, H [,l])
returns a list of reduced elements in the Coxeter group W which are
distinguished representatives for the right cosets of the reflection
subgroup H in W. The distinguished representative in the coset H.w
is the unique element in the coset which sends all roots of H to
positive roots (the element returned by ReducedInRightCoset). It is
also the element of minimal length in the coset. The representatives are
returned in order of increasing length.
gap> W := CoxeterGroup( "B", 3 );;
gap> H := ReflectionSubgroup(W, [ 2, 3 ]);;
gap> List( ReducedRightCosetRepresentatives( W, H ),
> x-> CoxeterWord( W, x ) );
[ [ ], [ 1 ], [ 1, 2 ], [ 1, 2, 1 ], [ 1, 2, 3 ], [ 1, 2, 1, 3 ],
[ 1, 2, 1, 3, 2 ], [ 1, 2, 1, 3, 2, 1 ] ]
If a third argument l is given, it should be an integer or a list of integers, and only the representatives whose CoxeterLength is in l are returned. This form is the only one which makes sense for infinite Coxeter groups.
gap> W:=Affine(CoxeterGroup("A",2));
Affine(CoxeterGroup("A",2))
gap> H:=ReflectionSubgroup(W,[1]);
ReflectionSubgroup(Affine(CoxeterGroup("A",2)), [ 1 ])
gap> List(ReducedRightCosetRepresentatives(W,H,[0..3]),
> x-> CoxeterWord( W, x ) );
[ [ ], [ 3 ], [ 2 ], [ 3, 1 ], [ 2, 1 ], [ 2, 3 ], [ 3, 2 ],
[ 2, 1, 3 ], [ 3, 1, 2 ], [ 2, 3, 2 ], [ 2, 3, 1 ], [ 3, 2, 1 ] ]
PermCosetsSubgroup( W, H )
returns the list of permutations induced by the standard generators of
the Coxeter group W on the cosets of the Coxeter subgroup H. The
cosets are in the order determined by the result of the function
ReducedRightCosetRepresentatives( W, H ).
gap> W := CoxeterGroup( "F", 4 );;
gap> PermCosetsSubgroup( W, ReflectionSubgroup( W, [ 1, 2, 3 ] ) );
[ ( 4, 5)( 6, 7)( 8,10)(16,18)(17,20)(19,21),
( 3, 4)( 7, 9)(10,12)(14,16)(15,17)(21,22),
( 2, 3)( 4, 6)( 5, 7)( 9,11)(12,14)(13,15)(17,19)(20,21)(22,23),
( 1, 2)( 6, 8)( 7,10)( 9,12)(11,13)(14,15)(16,17)(18,20)(23,24) ]
StandardParabolic( W, H )
returns an element w of W which conjugates the reflection subgroup H of W to a standard parabolic subgroup (that is, a reflection subgroup generated by a subset of the generators of W), if such a w exists. Otherwise returns false.
The returned element w is thus such that H^w is a standard parabolic
subgroup of W.
gap> W:=CoxeterGroup("E",6);;
gap> R:=ReflectionSubgroup(W,[20,30,19,22]);
ReflectionSubgroup(CoxeterGroup("E",6), [ 1, 9, 19, 20 ])
gap> StandardParabolic(W,R);
( 1, 4,49,12,10)( 2,54,62, 3,19)( 5,17,43,60, 9)( 6,21,34,36,20)
( 7,24,45,41,53)( 8,65,50,15,22)(11,32,31,27,28)(13,48,46,37,40)
(14,51,58,44,29)(16,23,35,33,30)(18,26,39,55,38)(42,57,70,72,56)
(47,68,67,63,64)(52,59,71,69,66)
gap> R^last;
ReflectionSubgroup(CoxeterGroup("E",6), [ 4, 5, 2, 6 ])
gap> R:=ReflectionSubgroup(W,[1,2,3,5,6,35]);;
gap> ReflectionName(R);
"A2<1,3>xA2<2,35>xA2"
gap> StandardParabolic(W,R);
false
88.6 jInductionTable for Macdonald-Lusztig-Spaltenstein induction
jInductionTable( H, W )
computes the decomposition into irreducible characters of the reflection
group W of the j-induced of the irreducible characters of the
reflection subgroup H. The j-induced of χ is the sum of the
irreducible components of the induced of χ which have same
b-function (see LowestPowerFakeDegrees) as χ. In the table the
rows correspond to the characters of the parent group, the columns to
those of the subgroup. What is returned is actually a record with
several fields: scalar contains the induction table proper, and there
is a Display method. The other fields contain labeling information
taken from the character tables of H and W when it exists.
gap> W := CoxeterGroup( "D", 4);;
gap> H := ReflectionSubgroup( W, [ 1, 3 ] );;
gap> Display( jInductionTable( H, W ) );
j-Induction from A2 to D4
|111 21 3
________________
11+ | . . .
11- | . . .
1.111 | . . .
.1111 | . . .
11.2 | . . .
1.21 | 1 . .
.211 | . . .
2+ | . . .
2- | . . .
.22 | . . .
1.3 | . 1 .
.31 | . . .
.4 | . . 1
JInductionTable( H, W )
JInductionTable computes the decomposition into irreducible characters
of the reflection group W of the J-induced of the irreducible
characters of the reflection subgroup H. The J-induced of χ is
the sum of the irreducible components of the induced of χ which
have same a-function (see LowestPowerGenericDegrees) as χ. In
the table the rows correspond to the characters of the parent group, the
columns to those of the subgroup. What is returned is actually a record
with several fields: scalar contains the induction table proper,
and there is a Display method. The other fields contain labeling
information taken from the character tables of H and W when it
exists.
gap> W := CoxeterGroup( "D", 4 );;
gap> H := ReflectionSubgroup( W, [ 1, 3 ] );;
gap> Display( JInductionTable( H, W ) );
J-Induction from A2 to D4
|111 21 3
________________
11+ | . . .
11- | . . .
1.111 | . . .
.1111 | . . .
11.2 | 1 . .
1.21 | 1 . .
.211 | . . .
2+ | . . .
2- | . . .
.22 | . . .
1.3 | . 1 .
.31 | . . .
.4 | . . 1
gap3-jm