Garside monoids are a general class of monoids whose most famous examples are the braid and dual braid monoids. The CHEVIE implementation of these last monoids is in the framework of a general implementation of Garside monoids.
To define them we first need to introduce some vocabulary about divisibility in monoids. A left divisor of x is a d such that there exists y with x=dy (and then we say that x is a right multiple of d). The divisor d is proper if y ≠ 1. We say that x is an atom if it has no proper left divisor apart from 1. A left gcd of x and y is a common left divisor d of x and y such that any other common left divisor is a right multiple of d. Similarly a right lcm of x and y is a common multiple which is a left divisor of any other common multiple. We say that a monoid M is left (resp. right) cancellable if an equality dx=dy (resp. xd=yd) implies x=y.
We can now define a Garside monoid M as a cancellable monoid which is generated by its atoms, which are finite in number, which is such that any element has only finitely many divisors, which admits left and right gcds and lcms, and further admits a Garside element or fundamental element Δ, which is an element whose set of left and right divisors coincide and generate M. There could be several such elements, but there is a unique minimal one (for divisibility); we assume such an element has been chosen. Then the divisors of Δ are called the simples of M. A Garside monoid embeds into its group of fractions, which is called a Garside group (it may be that a Garside group has several distinct Garside structures, as we will see is the case for Braid groups of finite Coxeter groups).
In CHEVIE, we also consider locally Garside monoids, which are monoids where lcms do not always exist, but exist when any common multiple exists; the set of simples is then not defined using a Garside element, but by the condition that they contain the atoms and are closed under lcms and taking divisors (see BDM01); since it is not ensured by the existence of Δ, one has to add the condition that any element is divisible by finitely many simples (but the number of simples can be infinite). The main example is the braid monoid of an infinite Coxeter group. It is not known if these monoids embed in their group of fractions (though that has been proved for braid monoids of Coxeter groups by Paris Paris01) and thus computing in the monoid does not help for computing in the group (only the monoid is implemented in CHEVIE in this case).
What allows computation inside Garside and locally Garside monoids, and Garside groups, is the fact that they admit normal forms (these normal forms where first exhibited for braid monoids by Deligne Del72, who extended previous work of Brieskorn, Saito BS72 and Garside Gar69):
\renewcommand\labelenumi{(\romanenumi)}
• Let M be a locally Garside monoid and let b∈ M. Then there is a unique maximal left simple divisor α(b) of b (thus any other simple dividing b on the left divides α(b) on the left).
• Assume M is a Garside monoid, Δ is its fundamental element and G is its group of fractions. Then, given any element x∈ G, there is some power Δi such that Δi x∈ M.
A consequence of (i) is that any element has a canonical decomposition as a product of simples, called its left-greedy normal form. If we define ω(x) by x=α(x)ω(x), then the normal form of x is α(x)α(ω(x))α(ω2(x))... We use the normal form to represent elements of M, and when M is Garside (ii) to represent elements of G: given x∈ G we compute the smallest power of Δ such that Δi x∈ M, and we represent x by the couple (i,Δi x). We are thus reduced to the case where x∈ M where we represent it by the sequence of simples which constitutes its normal form.
We now describe Artin-Tits braid monoids. Let W be a Coxeter group, with presentation
〈 s1, ... , sn | si2=1, sisjsi...m(i,j) factors = sjsisj...m(i,j) factors for all i, j with i ≠ j 〉 |
〈 s1, ... , sn | sisjsi...m(i,j) factors = sjsisj...m(i,j) factors for all i, j with i ≠ j〉 |
The positive braid monoid B+=B+(mi,j) associated to W is the monoid
defined by the presentation above (it identifies by the submonoid generated by
the si by the result of Paris mentioned above). This monoid is locally
Garside, with set of simples in bijection with elements of W and atoms in
bijection with the si; we will denote by W the set of simples, and by
w→ w the bijection between simples and elements of W. The group
W has a length defined in terms of reduced expressions (see
CoxeterLength
). Similarly, having only homogeneous relations, B+ has a
natural length function. Then W can be characterized as the subset of the
elements of B+ of the same length as their image in W.
If W is finite, then B+ is Garside with Garside element the element of W whose image is the longest element of W. Such a W is also a real reflection group in a vector space V, and B has also a topological definition as the fundamental group of the space ((V-∪s Hs)⊗C)/W, where s runs over the reflections in W and Hs=ker(s-1); however, we will not use this here.
Given a Coxeter group W,
gap> M:=BraidMonoid(W);
constructs the associated braid monoid, and then the function M.B
constructs
elements of the braid monoid (or group when W is finite) from a list of
generators. This function is directly available from W as Braid(W)
. Here
is an example:
gap> W:=CoxeterGroup("A",4);; gap> w:=Braid(W)(1,2,3,4); 1234 gap> w^3; 121321432.343 gap> CoxeterWord(W,GarsideAlpha(w^3)); [ 1, 2, 1, 3, 2, 1, 4, 3, 2 ] gap> w^4; w0.232432 gap> w^-1; (1234)^-1
As seen in the fourth line above, the function GarsideAlpha(
b) returns
the simple α(b), which is for braids returned as an element of W.
How an element of a Garside group is printed is controlled by the record
CHEVIE.PrintGarside
. The user can change the way elements of Garside monoids
and groups are printed whenever she wants during a GAP session by changing
this record.
When you load the CHEVIE package, PrintGarside
is initialized to the
empty record. Then elements are printed as fractions a-1b where a and
b have no left common divisor. Each of a and b is printed using its
left-greedy normal form, that is a maximal power of the Garside element
followed the rest. One can print the entire element in the left-greedy normal
from by setting the Greedy
field in PrintGarside
; with the same w as
above we have:
gap> CHEVIE.PrintGarside:=rec(Greedy:=true);; gap> w^-1; w0^-1.232432
Finally, if the field GAP
in the PrintGarside
record is set, the element
is printed in a form which after assigning B:=Braid(W);
can be input back
into GAP:
gap> CHEVIE.PrintGarside:=rec(GAP:=true);; gap> w; B(1,2,3,4) gap> w ^ 3; B(1,2,1,3,2,1,4,3,2,3,4,3) gap> w^-1; B(1,2,3,4)^-1 gap> CHEVIE.PrintGarside:=rec(GAP:=true,Greedy:=true);; gap> w^-1; B([2,3,2,4,3,2],-1) gap> CHEVIE.PrintGarside:=rec();;
In general elements of a Garside monoid are displayed thus as a list of their constituting atoms.
We now describe the dual braid monoids. For that, we first give another possible approach to the Artin-Tits braid monoid. Given a group W and a set S of generators of W as a monoid, we define the length l(w) as the minimum number of elements of S needed to write w. We then define left divisors of x as the d such that there exists y with x=dy and l(d)+l(y)=l(x). We say that w∈ W is balanced if its set of left and right divisors coincide, is a lattice (where upper and lower bounds are lcms and gcds) and generates W. Then we have:
suppose w is balanced and let D be its set of divisors. Then the monoid with generators D and relations xy=z whenever xy=z holds in W and l(x)+l(y)=l(z) is Garside, with simples D and atoms S.
The Artin-Tits braid monoid can be obtained in this fashion by taking for S
the Coxeter generators, in which case l is the Coxeter length, and taking
for w the longest element of W. The dual monoid, constructed by Birman, Ko
and Lee for type A and by Bessis for all well-generated complex reflection
groups, is obtained in a similar way, by taking this time for S the set of
all reflections, and for w a Coxeter element; then l is the
ReflectionLength
, see ReflectionLength; (this is for Coxeter groups; for
well-generated complex reflection groups S has to be restricted to only
those reflections which divide w for the reflection length); the simples are
in bijection with a subset of W of cardinality the generalized Catalan
numbers.
A last point to note is the notion of reversible monoids. Since in CHEVIE\
we store only left normal forms, it is easy to compute left lcms and gcds, but
hard to compute right ones. But this becomes easy to do if the monoid has an
operation a->reverse(a)
, which has the property that a
is a left divisor
of b
if and only if reverse(a)
is a right divisor of reverse(b)
. This is
used for the Artin-Tits and dual braid monoids; the Artin-Tits braid monoids
has a reverse operation which consists of reversing a word, written as a list
of atoms. The dual monoid also has a reverse operation defined in the same
way, but this operation changes monoid: it goes from the dual monoid for the
Coxeter element w to the dual monoid for the Coxeter element w-1.
The operations RightLcm
and RightGcd
, as well as the Franco and
Gonzáles-Meneses algorithms for conjugacy classes and
centralizers, are provided only if the monoid has a reverse operation.
We illustrate with braids basic operations on elements of a locally Garside
monoid or a Garside group. Thus we suppose first we have defined two elements
a
, b
as
gap> W := CoxeterGroup( "A", 2 );; gap> a := Braid( W )( [1] ); 1 gap> b := Braid( W )( [2] ); 2
All examples below are with CHEVIE.PrintOption("Garside","Greedy")
.
b1 * b2
The multiplication of two elements of the same locally Garside monoid or Garside group is defined.
gap> a * b; 12
b1 ^ i
An element can be raised to an integral, positive power (or negative power if
the monoid is Garside, which is the case here since W is finite). Here w0
is how the fundamental element Δ prints in the case of braids.
gap> ( a * b ) ^ 4; w0.w0.12 gap> ( a * b ) ^ -1; (12)^-1
b1 ^ b2
This is defined if the monoid is Garside and returns b1-1b2b1.
gap> a ^ b; (2)^-1.12
b1 / b2
This is defined if the monoid is Garside and returns b1b2-1.
gap> a / b; (12)^-1.21
Format( b, option )
String( b )
Print( b )
String
returns a display form of the element b, and Print
prints the
result of String
. The way elements are printed depends on the value of the
record CHEVIE.PrintGarside
. If if it is rec(GAP:=true)
, the elements are
printed in a form which can be read in back by a function B()
which accepts
a list of atoms (for braids, Braid(W)
returns such a function). If it is
rec(Greedy:=true)
(resp. rec()
) the left-greedy (resp. fraction) normal
form (as explained in the introduction) is printed:
gap> CHEVIE.PrintGarside:=rec(GAP:=true);; gap> ( a * b ) ^ -1; B(1,2)^-1 gap> CHEVIE.PrintGarside:=rec(Greedy:=true);; gap> ( a * b ) ^ -1; w0^-1.2 gap> CHEVIE.PrintGarside:=rec();; gap> ( a * b ) ^ -1; (12)^-1
The function Format( b, option)
returns the element formatted in a
string the same way it would be printed with PrintGarside
set to the
corresponding option. String
is equivalent to Format(b)
so always
formats its argument as Print
does after CHEVIE.PrintGarside:=rec()
.
These functions require the package "chevie" (see RequirePackage).
81.2 Records for( locally) Garside monoids
This section is rather technical and describes an internal representation
which is not yet completely fixed and thus might still change. We describe
here how a Garside or locally Garside monoid is specified in CHEVIE, as a
particular kind of record. If someone uses the information below to construct
a new kind of Garside monoid, it is thus advisable to contact me (Jean Michel)
to discuss possible changes. To construct a locally Garside monoid one creates
a record M
containing the following fields holding data and operations, and
then calls CompleteGarsideRecord(M)
:
atoms
:
identity
:
IsLeftDescending(s,i)
:
IsRightAscending(s,i)
:
RightMultiple(s,i)
:IsRightAscending(s,i)
, returns the
product of s by the i-th atom.
LeftQuotient(s,i)
:IsLeftDescending(s,i)
, returns the
quotient on the left of s by the i-th atom.
The source code for BraidMonoid
and DualBraidMonoid
functions provide
examples. The above functions are sufficient for multiplication, and most
operations on locally Garside monoids, like LeftGcd
, GarsideAlpha
, etc...
to be defined. However, for functions like RightGcdSimples
(see below) and
for algorithms like the Franco and Gonzáles-Meneses Conjugacy and
centralizer algorithms to be defined, one needs the symmetric routines
IsRightDescending
, IsLeftAscending
, LeftMultiple
, RightQuotient
to be
defined.
For the monoid constructed to be Garside one should in addition define the following data and operations:
delta
:
DeltaAction(s,i)
:
orderDelta
:
stringDelta
:
The code uses internally the test IsBound(M.delta)
to detect if the monoid
is Garside. Some additional fields and methods are added by
CompleteGarsideRecord
if not present; they are only added if not present
since often the user could define more efficient or more appropriate versions
for a particular kind of monoid (this is the case for braid monoids, for
instance). These fields and methods are :
AtomListSimple(s)
:AsWord
that atoms be represented by positive integers (if
AtomListSimple
not pre-defined, CompleteGarsideRecord
defines a default
version where an atom is represented by its index in the list M.atoms
). An
existing situation where the representation of an atom is not by its index in
the list of atoms is for braid monoids of Coxeter subgroups (where the index
in the list of generators of the parent is used --- see .reflectionLabels
);
also in this case the pre-defined function is faster than the default one
would be.
RightComplementToDelta(s)
:
LeftComplementToDelta(s)
:DeltaAction(RightComplementToDelta(s),1)
.
LeftGcdSimples(a,b)
:a
and b
.
LeftLcmSimples(a,b)
:a
and b
.
In addition CompleteGarsideRecord
defines RightGcdSimples
and (for Garside
monoids) RightLcmSimples
if the methods IsRightDescending
,
IsLeftAscending
, LeftMultiple
, RightQuotient
have been defined.
Finally, the user has to define a function M.reverse
which defines the
reverse
operation (one may look at the code for BraidMonoid
or
DualBraidMonoid
to see examples) if he wants the operations ReversedBraid
,
RightGcd
, RightLcm
to be defined.
GarsideWords( M, l )
M should be a (locally) Garside monoid which has an additive length function
(that is, a product of l atoms is not equal to any product of less than l
atoms). GarsideWords(M, l)
returns the list of elements of length l in
M.
gap> M := BraidMonoid(CoxeterGroup( "A", 2 ));; gap> GarsideWords( M, 4 ); [ 21.1.1, 21.12, w0.2, 2.21.1, 2.2.21, 2.2.2.2, w0.1, 1.1.1.1, 1.1.12, 1.12.2, 12.21, 12.2.2 ]
This function requires the package "chevie" (see RequirePackage).
Presentation(M)
M should be a Garside monoid. Presentation
returns a presentation of the
corresponding Garside group (the presentation is as given in theorem 4.1 of
DePa99).
gap> M := DualBraidMonoid(CoxeterGroup( "A", 3 ));; gap> p:=Presentation(M);Display(p); << presentation with 6 gens and 15 rels of total length 62 >> 1: ab=da 2: ac=ca 3: ec=cb 4: bd=da 5: bd=ab 6: cd=fc 7: ae=fa 8: be=cb 9: be=ec 10: de=ed 11: ef=fa 12: df=fc 13: df=cd 14: ef=ae 15: def=acb gap> ShrinkPresentation(p);Display(p); #I there are 3 generators and 4 relators of total length 26 #I there are 3 generators and 3 relators of total length 16 1: ab=ba 2: cbc=bcb 3: cac=aca
This function requires the package "chevie" (see RequirePackage).
81.5 ShrinkGarsideGeneratingSet
ShrinkGarsideGeneratingSet(b)
The list b is a list of elements of the same Garside group G. This
function tries to find another set of generators of the subgroup of G
generated by the elements of b, of smaller total length (the length being
counted as returned by the function AsWord
). The function can be called
several times, which sometimes may give a better result.
gap> B:=Braid(CoxeterGroupSymmetricGroup(3)); function ( arg ) ... end gap> b:=[B(1)^3,B(2)^3,B(-2,-1,-1,2,2,2,2,1,1,2),B(1,1,1,2)]; [ 1.1.1, 2.2.2, (1.12)^-1.2.2.2.21.12, 1.1.12 ] gap> ShrinkGarsideGeneratingSet(b); #I total length 20 maximal length 10 #I 4:10.31.2. reduced to 6.1 3.4. #I 3:4.01.2. reduced to 1.0 3. #I 2:3.01. #I total length 13 maximal length 6 #I 4:6.11. reduced to 4.0 2.3. reduced to 1.0 4. #I 3:3.01.2. #I 2:3.01. reduced to 2.0 2. #I total length 7 maximal length 3 #I 4:3.01.2. reduced to 2.0 3. #I 3:2.01. eliminated #I 2:1.01. #I total length 4 maximal length 2 #I 3:2.01.2. eliminated #I 2:1.01. [ 2, 1 ]
This function requires the package "chevie" (see RequirePackage).
81.6 locally Garside monoid and Garside group elements records
Now, we describe elements of a (locally) Garside monoid which are records with 3 fields:
elm
:
operations
:
monoid
:And a fourth field if the monoid is Garside:
pd
:
CompleteGarsideRecord
adds to (locally) Garside monoid records M
a
function M.Elt
which can be used to build such elements. The syntax is
M.Elt(s [,pd])
which defines an element with .elm=s
and .pd=pd
(if the monoid is
Garside but pd is not given it is initialized to 0
). The user must only
give valid normal forms in s, otherwise impredictable errors may occur. For
example, Δ should be entered as M.Elt([],1)
and the identity as
M.Elt([])
.
AsWord( b )
b should be a locally Garside monoid or Garside group element. AsWord
then
returns a description of b as a list of the atoms of which it is a product
(as returned by AtomListSimple
). If b is in the group but not the monoid,
it is represented in fraction normal form where as a special convention the
inverses of the atoms are represented by negating the corresponding integer.
gap> W := CoxeterGroup( "A", 3 );; gap> b := Braid(W)(2, 1, 2, 1, 1)*Braid(W)(2,2)^-1; (21)^-1.1.12.21 gap> AsWord( b ); [ -1, -2, 1, 1, 2, 2, 1 ]
This function requires the package "chevie" (see RequirePackage).
GarsideAlpha( b )
b should be an element of a (locally) Garside monoid. GarsideAlpha
returns the simple α(b) (for braids this is an element of the
corresponding Coxeter group).
gap> W := CoxeterGroup( "A", 3 );; gap> b := Braid( W )(2, 1, 2, 1, 1); 121.1.1 gap> CoxeterWord(W,GarsideAlpha( b )); [ 1, 2, 1 ]
This function requires the package "chevie" (see RequirePackage).
LeftGcd( a, b )
a and b should be elements of the same (locally) Garside monoid M.
Let d be the greatest common left divisor of a and b; then
LeftGcd
returns the list [d,d^-1*a,d^-1*b]
.
gap> W := CoxeterGroup( "A", 3 );; gap> b := Braid(W)(2,1,2)^2; 121.121 gap> LeftGcd(b,Braid(W)(3,2)^2); [ 2, 121.21, 32.2 ]
This function requires the package "chevie" (see RequirePackage).
LeftLcm( a, b )
a and b should be elements of the same Garside monoid M. Let m
be the least common left multiple of a and b; then LeftGcd
returns
the list [m,m*a^-1,m*b^-1]
.
gap> W := CoxeterGroup( "A", 3 );; gap> b := Braid(W)(2,1,2)^2; 121.121 gap> LeftLcm(b,Braid(W)(3,2)^2); [ w0.121, 123, 23.321 ]
This function requires the package "chevie" (see RequirePackage).
ReversedWord( b )
b should be an element of a (locally) Garside monoid which has a
reverse
operation (see the end of the introduction). The function
returns the result of the reverse operation applied to b.
gap> W := CoxeterGroup( "A", 3 );; gap> b := Braid(W)(2,1); 21 gap> ReversedWord(b); 12
This function requires the package "chevie" (see RequirePackage).
RightGcd( a, b )
a and b should be elements of the same (locally) Garside monoid M
which has a reverse
operation (see the end of the introduction). Let
d be the greatest common right divisor of a and b; then RightGcd
returns the list [d,a*d^-1,b*d^-1]
.
gap> W := CoxeterGroup( "A", 3 );; gap> b := Braid(W)(2,1,2)^2; 121.121 gap> RightGcd(b,Braid(W)(3,2)^2); [ 2.2, 12.21, 23 ]
This function requires the package "chevie" (see RequirePackage).
RightLcm( a, b )
a and b should be elements of the same Garside monoid M which has
a reverse
operation (see the end of the introduction). Let m be the
least common right multiple of a and b; then RightGcd
returns the
list [m,a^-1*m,b^-1*m]
.
gap> W := CoxeterGroup( "A", 3 );; gap> b := Braid(W)(2,1,2)^2; 121.121 gap> RightLcm(b,Braid(W)(3,2)^2); [ w0.w0, 321.123, 12321.321 ]
This function requires the package "chevie" (see RequirePackage).
AsFraction( b )
Let b be an element of the Garside group G. AsFraction
returns a
pair [x,y]
of two elements of M with no non-trivial common left
divisor and such that b=x^-1*y
.
gap> W := CoxeterGroup( "A", 3 );; gap> b := Braid(W)( 2, 1, -3, 1, 1); (23)^-1.321.1.1 gap> AsFraction(b); [ 23, 321.1.1 ]
This function requires the package "chevie" (see RequirePackage).
SimpleLeftDivisors( M, s )
Returns all the left divisors of the simple element s of the (locally) Garside monoid M.
gap> W:=CoxeterGroup("A",3); CoxeterGroup("A",3) gap> M:=BraidMonoid(W); BraidMonoid(CoxeterGroup("A",3)) gap> List(SimpleLeftDivisors(M,EltWord(W,[1,3,2])),M.B); [ ., 3, 1, 13, 132 ] gap> M:=DualBraidMonoid(W); DualBraidMonoid(CoxeterGroup("A",3),[ 1, 3, 2 ]) gap> List(SimpleLeftDivisors(M,EltWord(W,[1,3,2]),M.B); [ ., 3, 2, 5, 1, 4, 6, 45, 25, 13, 34, 12, 15, c ]
SimpleLeftDivisors(M,M.delta)
will return all simples of the monoid M.
This function requires the package "chevie" (see RequirePackage).
81.16 The Artin-Tits braid monoids and groups
BraidMonoid(W)
Returns (as a Garside or locally Garside monoid record) the Artin-Tits braid monoid of the Coxeter group W. The monoid is Garside if and only if W is finite; in which case elements of the resulting monoid can be used as elements of a group.
This function requires the package "chevie" (see RequirePackage).
Braid( W )( s1, .., sn )
Braid( W )( list [, pd ])
Braid( W )( w [, pd ])
Let W be a Coxeter group and let w be an element of W or a sequence
s1,..,sn of integers representing a (non necessarily reduced) word in the
generators of W. The calls above return the element of the braid monoid of
W defined by w. In the second form the list is a list of si as in the
first form. If pd (a positive or negative integer) is given (which is
allowed only when W is finite), the resulting element is multiplied in the
braid group by w0pd. The result of Braid(W)
is a braid-making
function, which can be assigned to make conveniently braid elements as in the
example below. This function can also be obtained as BraidMonoid(W).B
.
gap> W := CoxeterGroup( "A", 3 );; gap> B := Braid( W ); function ( arg ) ... end gap> B( W.generators[1] ); 1 gap> B( 2, 1, 2, 1, 1 ); 121.1.1 gap> CHEVIE.PrintGarside:=rec(Greedy:=true);; gap> B( [ 2, 1, 2, 1, 1 ], -1 ); w0^-1.121.1.1
As a special case (to follow usual conventions for entering braids) a negative integer in a given list representing a word in the generators is taken as representing the inverse of a generator.
gap> CHEVIE.PrintGarside:=rec();; gap> B( -1, -2, -3, 1, 1 ); (321)^-1.1.1
This function requires the package "chevie" (see RequirePackage).
Frobenius( WF )(b)
:WF
is a Coxeter coset associated to the
Coxeter group W, the function Frobenius(WF)
returns the associated
automorphism of the braid monoid of W.
gap> W:=CoxeterGroup("A",3); CoxeterGroup("A",3) gap> WF:=CoxeterCoset(W,(1,3)); 2A3 gap> B:=Braid(W);;b:=B(1,2,3); 123 gap> Frobenius(WF)(b); 321
BrieskornNormalForm( b )
:W
, this function returns the Brieskorn normal form of b,
which is defined as the concatenation of the Brieskorn normal form for the
terms of the normal form of b (see BrieskornNormalForm).
These functions require the package "chevie" (see RequirePackage).
EltBraid( b )
Returns the image of the braid element b in the group of which b is a braid element.
gap> W := CoxeterGroup( "A", 3 );; gap> b := Braid( W )(2, 1, 2, 1, 1); 121.1.1 gap> p := EltBraid( b ); ( 1, 8)( 2, 7)( 3, 6)( 4,10)( 9,12) gap> CoxeterWord( W, p ); [ 1, 2, 1 ]
This function requires the package "chevie" (see RequirePackage).
GoodCoxeterWord( W, w )
Let W be a Coxeter group with associated braid monoid B+.
GoodCoxeterWord
checks if the element w of W (given as sequence of
generators of W) represents a ``good element'' in the sense of
Geck-Michel GM97 of the braid monoid, i.e., if wd (where d is
the order of the element w in W, and w is the element of W with
image w) is a product of (the braid elements corresponding to) longest
elements in a decreasing chain of parabolic subgroups of W. If this is true,
then a list of couples, the corresponding subsets of the generators with their
multiplicities in the chain, is returned. Otherwise, false
is returned.
Good elements have nice properties with respect to their eigenvalues in
irreducible representations of the Hecke-Iwahori algebra associated to W.
The representatives in the component classtext
of ChevieClassInfo(W)
are
all good elements of minimal length in their class.
gap> W := CoxeterGroup( "F", 4 );; gap> w:=[ 2, 3, 2, 3, 4, 3, 2, 1, 3, 4 ];; gap> GoodCoxeterWord( W, w ); [ [ [ 1, 2, 3, 4 ], 2 ], [ [ 3, 4 ], 4 ] ] gap> OrderPerm( EltWord( W, w ) ); 6 gap> Braid( W )( w ) ^ 6; w0.w0.343.343.343.343 gap> GoodCoxeterWord( W, [ 3, 2, 3, 4, 3, 2, 1, 3, 4, 2 ] ); false
This function requires the package "chevie" (see RequirePackage).
BipartiteDecomposition(W)
Returns a bipartite decomposition [L,R]
of the indices of the generators of
the reflection group W
, such that ReflectionSubgroup(W,L)
and
ReflectionSubgroup(W,R)
are abelian subgroups (and
W=ReflectionSubgroup(W,Concatenation(L,R))
). Gives an error if no such
decomposition is possible.
gap> BipartiteDecomposition(CoxeterGroup("E",8)); [ [ 1, 4, 6, 8 ], [ 3, 2, 5, 7 ] ]
This function requires the package "chevie" (see RequirePackage).
DualBraidMonoid(W [, c])
Returns (as a Garside monoid record) the dual braid monoid of the finite and
well-generated complex reflection group W associated to the Coxeter
element c of W. If W is a Coxeter group, c can be omitted and a
particular one is then chosen, the element
EltWord(W,Concatenation(BipartiteDecomposition(W)))
.
gap> DualBraidMonoid(CoxeterGroup("A",4)); DualBraidMonoid(CoxeterGroup("A",4),[ 1, 3, 2, 4 ]) gap> DualBraidMonoid(CoxeterGroup("A",4),[1,2,3,4]); DualBraidMonoid(CoxeterGroup("A",4),[ 1, 2, 3, 4 ])
This function requires the package "chevie" (see RequirePackage).
B:=DualBraid( W [, c])
then
B( s1, .., sn )
B( list [, pd ])
B( w [, pd ])
Let W be a ell generated complex reflection group and c be a Coxeter
element of W (if W is a Coxeter group and no c is given a particular one
is chosen by making the product of elements in a partition of the Coxeter
diagram in two sets where elements in each commute pairwise). The result of
DualBraid
is a dual braid-making function for the dual monoid determined by
W and c: let w be an element of W or a sequence s1,..,sn of
integers representing a list of reflections of W. The calls to B
above
return the element of the dual braid monoid of W defined by w. In the
second form the list is a list of si as in the first form. If pd (a
positive or negative integer) is given, the resulting element is multiplied in
the braid group by cpd.
gap> W := CoxeterGroup( "A", 3 );; gap> B := DualBraid( W ); function ( arg ) ... end gap> B( W.reflections[4] ); 4 gap> B( 2, 1, 2, 1, 1 ); 12.1.1.1 gap> B( [ 2, 1, 2, 1, 1 ], -1 ); (3)^-1.5.5.5
As a special case (to follow usual conventions for entering braids) a negative integer in a given list representing a word in the generators is taken as representing the inverse of a generator.
gap> B( -1, -2, -3, 1, 1 ); (25.1)^-1.1.1
The function B
can also be obtained by making the calls
M:=DualBraidMonoid( W [, c])
and B:=M.B
.
This function requires the package "chevie" (see RequirePackage).
81.24 Operations for dual braids
EltBraid
has the same meaning as for ordinary braids.
These functions require the package "chevie" (see RequirePackage).
GAP 3.4.4