89 Garside and braid monoids and groups

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
for some Coxeter matrix {ms,t}s,t∈ S. The braid group B associated to (W,S) is the group defined by the presentation
sS| sts...m(s,t) factors = tst...m(s,t) factors for all s,tS

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 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 constructed this way from an interval in a group, are called interval monoids.

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 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.

We illustrate this on an example:

    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

Subsections

  1. Operations for (locally) Garside monoid elements
  2. Records for( locally) Garside monoids
  3. GarsideWords
  4. Presentation
  5. ShrinkGarsideGeneratingSet
  6. locally Garside monoid and Garside group elements records
  7. AsWord
  8. GarsideAlpha
  9. LeftGcd
  10. LeftLcm
  11. ReversedWord
  12. RightGcd
  13. RightLcm
  14. AsFraction
  15. LeftDivisorsSimple
  16. The Artin-Tits braid monoids and groups
  17. Construction of braids
  18. Operations for braids
  19. EltBraid
  20. GoodCoxeterWord
  21. BipartiteDecomposition
  22. DualBraidMonoid
  23. DualBraid
  24. Operations for dual braids
  25. ConjugacySet
  26. CentralizerGenerators
  27. RepresentativeConjugation

89.1 Operations for (locally) Garside monoid elements

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:

the list of simples which are atoms of M.

M.identity:

the identity element of M, a simple.

M.IsLeftDescending(s,i):

tells whether M.atoms[i] divides on the left the simple s.

M.IsRightAscending(s,i):

tells whether the product of the simple s by M.atoms[i] is still simple.

M.Product(s,t):

returns the product of the simples s and t. It does not have to be defined in all cases, but should at least be defined when t=M.atom[i] and M.IsRightAscending(s,i).

M.LeftQuotient(s,t):

returns the quotient 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):

returns the quotient 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:

the fundamental element Δ.

M.DeltaAction(s,i):

Let f be the automorphism induced on simples by Δ (such that Δ s=f(s)Δ). The function returns fi(s).

M.stringDelta:

how Δ should be printed in normal forms.

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):

returns the list of atoms of which the simple s is the product. This is mostly used for display purposes, so the individual representation for atoms may be any kind of object. However it is useful for the function 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):

for Garside monoids. Given a simple s returns the simple t such that st=Δ. Again one may often be able to pre-define a faster function than the default one.

M.LeftComplementToDelta(s):

for Garside monoids. Given a simple s returns the simple t such that ts=Δ. The default version reads DeltaAction(RightComplementToDelta(s),1).

For interval monoids, fast versions of RightComplementToDelta and LeftComplementToDelta are automatically defined.

M.LeftGcdSimples(a1,...,an):

returns the simple which is the left gcd of the simples a1,...,an.

M.LeftLcmSimples(a1,...,an):

for Garside monoids. Returns the simple which is the left lcm of the simples 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.

89.3 GarsideWords

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 ]

89.4 Presentation

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

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:

the list of simples in the left-greedy normal form.

operations:

points to GarsideEltOps.

monoid:

points to the record describing the corresponding Garside or locally Garside monoid.

And a fourth field if the monoid is Garside:

pd:

the power of Δ involved in the greedy normal form.

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([]).

89.7 AsWord

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 ]   

89.8 GarsideAlpha

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 ] 

89.9 LeftGcd

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 ]

89.10 LeftLcm

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 ]

89.11 ReversedWord

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

89.12 RightGcd

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 ]

89.13 RightLcm

RightLcm( a, b )

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 ]

89.14 AsFraction

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 ]

89.15 LeftDivisorsSimple

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.

89.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.

89.17 Construction of braids

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 

89.18 Operations for braids

Frobenius( WF )(b):

If 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 ):

If b is an element of the braid monoid of the Coxeter group 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).

89.19 EltBraid

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 ] 

89.20 GoodCoxeterWord

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 

89.21 BipartiteDecomposition

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 ] ]

89.22 DualBraidMonoid

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

corresponding to each simple of length 2 of the dual monoid:

    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 ]

89.23 DualBraid

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.

89.24 Operations for dual braids

EltBraid has the same meaning as for ordinary braids.

89.25 ConjugacySet

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 ]

89.26 CentralizerGenerators

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.27 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> RepresentativeConjugation(b,c,F);
    (13)^-1.23.31
    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

Previous Up Next
Index

gap3-jm
19 Feb 2018