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 call Garside a monoid M which is:
• left and right cancellable.
• generated by its atoms, which are finite in number.
• such that any element has only finitely many divisors.
• admits left and right gcds and lcms.
• admits a Garside element, which is an element Δ whose set of left and right divisors coincide and generate M.
Garside elements are not unique, 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).
CHEVIE also implements 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).
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:
•[(i)] Let M be a locally Garside monoid and let b∈ M. Then there is a unique maximal left simple divisor α(b) of b, called the head of b --- any other simple dividing b on the left divides α(b) on the left.
•[(ii)] Assume M is a Garside monoid, Δ is its Garside 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, not divisible by Δ, where we represent x by the sequence of simples which constitutes its normal form.
We now describe Artin-Tits braid monoids. Let (W,S) be a Coxeter system, that is W has presentation
| ⟨ s∈ S | s2=1, sts...m(s,t) factors = tst...m(s,t) factors for all s,t∈ S ⟩ |
| ⟨ s∈S| sts...m(s,t) factors = tst...m(s,t) factors for all s,t∈S⟩ |
The positive braid monoid B+ associated to W is the monoid defined
by the presentation above --- it identifies to the submonoid of B
generated by S by the result of Paris mentioned above. This monoid
is locally Garside, with set of simples in bijection with elements of W
and atoms the elements of S; 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. A finite Coxeter group is also a reflection group in a real vector space, thus in its complexified V, and B has also a topological definition as the fundamental group of the space Vreg/W, where Vreg is the set of elements of V which are fixed by no non-identity element of S; however, we will not use this here.
Given a Coxeter group W,
gap> W:=CoxeterGroup("A",4);;M:=BraidMonoid(W);
BraidMonoid(CoxeterGroup("A",4))
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);;B:=Braid(W);;
gap> w:=B(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)∈W, which is 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 GAP3 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 GAP3:
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 monoid. For that, we first give a possible approach to construct Garside monoids. 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 [1,w] be its set of divisors (an interval for the partial order defined by divisibility). Then the monoid M with generators [1,w] and relations xy=z whenever xy=z holds in W and l(x)+l(y)=l(z) is Garside, with simples [1,w] 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 [1,w], a subset of W of
cardinality the generalized Catalan numbers. Monoids M constructed this
way from an interval in a group, are called interval monoids. An interval
monoid has naturally an inverse morphism from M to W, called EltBraid
which is the quotient map from the interval monoid to W which sends back
simple braids to [1,w].
A last notable notion is 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 holds for Artin-Tits and dual braid monoids; Artin-Tits
monoids have 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
quite a few algorithms have faster implementations if the monoid has a
reverse operation.
We have implemented in CHEVIE functions to solve the conjugacy problem and compute centralizers in Garside groups, following the work of Franco, Gebhardt and Gonzalez-Meneses (gebgon10 and fragon03).
We say that w and w', elements of a monoid M are conjugate in M if there exists x∈ M such that wx=xw'; if M satisfies the Öre conditions, it has a group of fractions where this becomes x-1wx=w', the usual definition of conjugacy. A special case which is even closer to conjugacy in the group is if there exists y∈ M such that w=xy and w'=yx. This relation is not transitive in general, but we call cyclic conjugacy the transitive closure of this relation, a restricted form of conjugacy.
The next observation is that if w,w' are conjugate in the group of fractions of the Garside monoid M then they are conjugate in M, since if wx=xw' then there is a power Δi which is central and such that xΔi∈ M. Then wxΔi=xΔi w' is a conjugation in M.
The crucial observation for solving the conjugacy problem is to introduce inf(w):=sup{i such that Δi divides w} and sup(w):=inf{i such that w divides Δi}, and to notice that the number of conjugates of w with same inf and sup as w is finite. Further, a theorem of Birman shows that the maximum inf and minimum sup in a conjugacy class can be achieved simultaneously; the elements achieving this are called the super summit set of w. Thus a way to determine if two elements are conjugate is to find a representative of both of them in their super summit set, and then solve conjugacy within that set. This can also be used to compute the centralizer of an element: if we consider the super summit set as the objects of a category whose morphisms are the conjugations by simple elements, the centralizer is given by the endomorphisms of the given object.
gap> w:=B(2,1,4,1,4);
214.14
gap> ConjugacySet(w,"SS"); # super summit set
[ 1214.4, 214.14, 124.24, 1343.1, 14.124, 143.13, 24.214, 134.14,
13.134, 14.143 ]
gap> RepresentativeConjugation(w,B(1,4,1,4,3));
(1)^-1.21321432
gap> w^B(-1,2,1,3,2,1,4,3,2);
14.143
gap> CentralizerGenerators(w);
[ 4, 321432.213243, 21.1 ]
There is a faster solution to the conjugacy problem given in gebgon10: for each b∈ M, they define a particular simple left divisor of b, its preferred prefix such that the operation sliding which cyclically conjugates b by its preferred prefix, is eventually periodic, and the period is contained in the super summit set of x. We say that x is in its sliding circuit if some iterated sliding of x is equal to x. The set of sliding circuits in a given conjugacy class is smaller than the super summit set, thus allows to solve the conjugacy problem faster. Continuing from the above example,
gap> CoxeterWord(W,PreferredPrefix(w));
[ 2, 1 ]
gap> w^B(PreferredPrefix(w));
1214.4
gap> last^B(PreferredPrefix(last));
1214.4
gap> ConjugacySet(w,"SC"); # set of sliding circuits
[ 1214.4, 1343.1 ]
Finally, we have implemented Hao Zheng's algorithm to extract roots in a Garside monoid:
gap> W:=CoxeterGroup("A",3);; M:=BraidMonoid(W);
BraidMonoid(CoxeterGroup("A",3))
gap> pi:=M.B(M.delta)^2;
w0.w0
gap> GetRoot(pi,2);
w0
gap> GetRoot(pi,3);
1232
gap> GetRoot(pi,4);
132
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().
GetRoot( b, n )
Returns the n-th root of b.
89.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 with finitely many atoms 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). The simples can be arbitrary objects (for
interval monoids they should be elements of a group), the following
operations should just be defined on them.
M.atoms:
M.identity:
M.IsLeftDescending(s,i):M.atoms[i] divides on the left
the simple s.
M.IsRightAscending(s,i):M.atoms[i] is still simple.
M.Product(s,t):t=M.atom[i] and M.IsRightAscending(s,i).
M.LeftQuotient(s,t):s^-1*t for simples s
and t. It does not have to be defined in all cases, but should at least
be defined when s=M.atom[i] and M.IsLeftDescending(t,i).
M.RightQuotient(s,t):s/t for simples s and t
The source code for BraidMonoid and DualBraidMonoid provide examples.
The above functions are sufficient for multiplication, and most operations
on locally Garside monoids, like LeftGcd, GarsideAlpha, etc... to be
defined; however see below for conjugacy.
In the case the monoid is an interval monoid, which is specified by giving
a second argument rec(interval:=true) to CompleteGarsideMonoid, then
the functions Product, LeftQuotient, RightQuotient are automatically
defined (since in that case simples are element of a group, they are
defined by the group operations).
For ReversedBraid, RightGcd, RightLcm, M.RightGcdSimples to work
(see below) and the Franco and González-Meneses conjugacy and
centralizer algorithms to be defined, one needs in addition either:
a function M.ReverseSimple to be defined, which defines the Reverse
operation (if M is an interval monoid and M.delta^2=M.identity, this
is just x->x^-1 thus is then automatically defined),
or the symmetric routines M.IsRightDescending, M.IsLeftAscending to be
defined, and one needs that Product(M.atoms[i],s) be defined for s
simple such that M.IsLeftAscending(s,i), and that
M.RightQuotient(s,M.atoms[i]) be defined when M.IsRightDescending(s,i).
For the monoid constructed to be Garside one should in addition define the following data and operations:
M.delta:
M.DeltaAction(s,i):
M.stringDelta:
If the monoid is an interval monoid, DeltaAction is automatically defined
as conjugation by M.delta in the group to which simples belong.
CompleteGarsideRecord 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 :
M.AtomListSimple(s):AsWord that atoms be represented by positive integers
(if M.AtomListSimple is 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.
M.RightComplementToDelta(s):
M.LeftComplementToDelta(s):DeltaAction(RightComplementToDelta(s),1).
For interval monoids, fast versions of RightComplementToDelta and
LeftComplementToDelta are automatically defined.
M.LeftGcdSimples(a1,...,an):
M.LeftLcmSimples(a1,...,an):
In addition CompleteGarsideRecord defines M.RightGcdSimples and (for
Garside monoids) M.RightLcmSimples if the methods M.IsRightDescending,
M.IsLeftAscending, M.LeftMultiple, M.RightQuotient have been 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 ]
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);DisplayPresentation(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);DisplayPresentation(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
89.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).
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);
[ 2, 1 ]
89.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 unpredictable 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 ]
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 ]
LeftGcd( a1,...,an )
a1,...,an should be elements of the same (locally) Garside monoid
M. Let d be the greatest common left divisor of a1,...,an; then
LeftGcd returns the list [d,d^-1*a1,...,d^-1*an].
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 ]
LeftLcm( a1,...,an )
a1,...,an should be elements of the same Garside monoid M. Let m
be the least common left multiple of a1,...,an; then LeftGcd
returns the list [m,m*a1-1,...,m*an-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 ]
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
RightGcd( a1,...,an )
a1,...,an 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 a1,...,an; then RightGcd
returns the list [d,a1*d^-1,...,an*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 ]
RightLcm( a1,...,an )
a1,...,an 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 a1,...,an; then RightLcm returns
the list [m,a1-1*m,...,an-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 ]
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 ]
LeftDivisorsSimple( M, s [,i])
Returns all the left divisors of the simple element s of the (locally) Garside monoid M, as a list of lists, where the i+1th list holds the divisors of length i in the atoms. If a third argument i is given, returns only the list of divisors of length i.
gap> W:=CoxeterGroup("A",3);
CoxeterGroup("A",3)
gap> M:=BraidMonoid(W);
BraidMonoid(CoxeterGroup("A",3))
gap> List(LeftDivisorsSimple(M,EltWord(W,[1,3,2])),x->List(x,M.B));
[ [ . ], [ 3, 1 ], [ 13 ], [ 132 ] ]
gap> M:=DualBraidMonoid(W);
DualBraidMonoid(CoxeterGroup("A",3),[ 1, 3, 2 ])
gap> List(LeftDivisorsSimple(M,EltWord(W,[1,3,2])),x->List(x,M.B));
[ [ . ], [ 3, 2, 5, 1, 4, 6 ], [ 45, 25, 13, 34, 12, 15 ], [ c ] ]
Concatenation(LeftDivisorsSimple(M,M.delta)) returns all simples of the
monoid M.
LeftDivisors( b[, i] )
returns all left divisors of Garside element b (of length i if specified).
gap> B:=DualBraid(CoxeterGroupSymmetricGroup(4));
function ( arg ) ... end
gap> LeftDivisors(B(1,5,4,3));
[ ., 5, 1, 1.4, 1.4.3, 1.4.2, 6, 15, 15.4, 15.4.3 ]
gap> LeftDivisors(B(1,5,4,3),1);
[ 5, 1, 6 ]
EltBraid( b )
This function is defined only if b is an element of an interval monoid, for instance a braid. It returns the image of b in the group of which the monoid is an interval monoid. For instance it gives the projection of a braid in an Artin monoid back to the Coxeter group.
gap> W := CoxeterGroupSymmetricGroup( 4 );;
gap> b := Braid( W )(2, 1, 2, 1, 1);
121.1.1
gap> p := EltBraid( b );
(1,3)
gap> CoxeterWord( W, p );
[ 1, 2, 1 ]
89.18 The Artin-Tits braid monoids and groups
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.
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
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("D",4);WF:=CoxeterCoset(W,(1,2,4));
CoxeterGroup("D",4)
3D4
gap> B:=Braid(W);;b:=B(1,3);
13
gap> Frobenius(WF)(b);
43
gap> Frobenius(WF)(b,-1);
23
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).
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
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 ] ]
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> M:=DualBraidMonoid(CoxeterGroup("A",4),[1,2,3,4]);
DualBraidMonoid(CoxeterGroup("A",4),[ 1, 2, 3, 4 ])
For Coxeter groups, the dual monoid contains an operation .ToOrdinary
which converts simples to elements of the ordinary braid monoid of W. To
go on from the above example, we compute the list of ordinary braids
gap> List(LeftDivisorsSimple(M,M.delta,2),M.ToOrdinary);
[ 34, 24, 23, (34)^-1.2343, (3)^-1.234, (4)^-1.234, 14, 13,
(4)^-1.134, (2)^-1.124, (23)^-1.1232, (2343)^-1.123243, 12,
(2)^-1.123, (234)^-1.12324, (3)^-1.123, (23)^-1.1234,
(234)^-1.12343, (24)^-1.1234, (34)^-1.1234 ]
B:=DualBraid( W [, c])
then
B( s1, .., sn )
B( list [, pd ])
B( w [, pd ])
Let W be a well 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.
89.25 Operations for dual braids
EltBraid has the same meaning as for ordinary braids.
ConjugacySet(b[,F][,type])
b should be an element of a Garside group. By default, or if the type
given is "SC", computes the set of sliding circuits of b. If type
is "SS", computes the super summit set of b. If type is "Cyc",
computes the cyclic conjugacy class of b. Finally, if type is "Pos",
computes the set of all positive elements conjugate to b.
If an argument F is given it should be the Frobenius of a Reflection coset attached to the same group to which the Garside monoid is attached. Then the same computations are effected but relative to F-conjugacy.
gap> W:=CoxeterGroup("A",4);;w:=Braid(W)(4,3,3,2,1);
43.321
gap> ConjugacySet(w);
[ 32143, 21324 ]
gap> ConjugacySet(w,"SC");
[ 32143, 21324 ]
gap> ConjugacySet(w,"SS");
[ 32143, 13243, 21432, 21324 ]
gap> ConjugacySet(w,"Cyc");
[ 43.321, 3.3214, 32143, 2143.3, 143.32, 213.34, 13.324, 13243,
1243.3, 123.34 ]
gap> ConjugacySet(w,"Pos");
[ 43.321, 3.3214, 32143, 2143.3, 21432, 143.32, 213.34, 1432.2,
21324, 13.324, 432.21, 1324.2, 13243, 324.21, 124.23, 1243.3,
24.213, 12.234, 123.34, 2.2134 ]
gap> W:=CoxeterGroup("D",4);;
gap> F:=Frobenius(CoxeterCoset(W,(1,2,4)));
function ( arg ) ... end
gap> w:=Braid(W)(4,4,4);
4.4.4
gap> ConjugacySet(w);
[ 4.4.4, 3.3.3, 1.1.1, 2.2.2 ]
gap> ConjugacySet(w,F);
[ 124 ]
CentralizerGenerators(b[,F][,type])
b should be an element of a Garside group. The function returns a list of
generators of the centralizer of b. The computation is done by computing
the endomorphisms of the object b in the category of its sliding
circuits. If an argument type is given, the computation is done in the
corresponding category --- see ConjugacySet. The main use of this is to
compute the centralizer in the category of cyclic conjugacy by giving
"Cyc" as the type.
If an argument F is given it should be the Frobenius of a Reflection coset attached to the same group to which the Garside monoid is attached. Then the F-centralizer is computed.
gap> W:=CoxeterGroup("D",4);;
gap> w:=Braid(W)(4,4,4);
4.4.4
gap> CentralizerGenerators(w);
[ 4, 2, (1)^-1.34.431, 34.43, (32431)^-1.132431, 1, (2)^-1.34.432,
(31432)^-1.231432 ]
gap> ShrinkGarsideGeneratingSet(last);
[ 4, 2, 1, 34.43, (3243)^-1.13243 ]
gap> CentralizerGenerators(w,"Cyc");
[ 4 ]
gap> F:=Frobenius(CoxeterCoset(W,(1,2,4)));
function ( arg ) ... end
gap> CentralizerGenerators(w,F);
[ 312343123, 124 ]
89.28 RepresentativeConjugation
RepresentativeConjugation(b,b1[,F][,type])
b and b1 should be elements of the same Garside group. The function
returns false if they are not conjugate, and an element a such that
b^a=b1 if they are conjugate. The computation is done by computing the
set of the sliding circuits of b and check if it is the same as the set
of sliding circuits of b1. If an argument type is given, the
computation is done in the corresponding category --- see ConjugacySet.
The main use of this is to compute if b and b1 are related by cyclic
conjugacy by giving "Cyc" as the type.
If an argument F is given it should be the Frobenius of a Reflection coset attached to the same group to which the Garside monoid is attached. Then F-conjugacy is used for the computations.
gap> W:=CoxeterGroup("D",4);;B:=Braid(W);
function ( arg ) ... end
gap> b:=B(2,3,1,2,4,3);b1:=B(1,4,3,2,2,2);
231243
1432.2.2
gap> RepresentativeConjugation(b,b1);
(134312.23)^-1
gap> b^last;
1432.2.2
gap> RepresentativeConjugation(b,b1,"Cyc");
232.2
gap> b^last;
1432.2.2
gap> RepresentativeConjugation(b,b1,F);
false
gap> c:=B(3,2,2,3,3,4);
32.23.34
gap> F:=Frobenius(CoxeterCoset(W,(1,2,4)));
function ( arg ) ... end
gap> a:=RepresentativeConjugation(b,c,F);
(13)^-1.23.31
gap> a^-1*b*F(a);
32.23.34
gap> a:=RepresentativeConjugation(b,c,F,"Cyc");
2312431.312343.324.23.31
gap> a^-1*b*F(a);
32.23.34
gap3-jm