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
 ⟨ 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 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```

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
gap> b := Braid( W )(  );
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 ]```

`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))
[ [ . ], [ 3, 1 ], [ 13 ], [ 132 ] ]
gap> M:=DualBraidMonoid(W);
DualBraidMonoid(CoxeterGroup("A",3),[ 1, 3, 2 ])
[ [ . ], [ 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 EltBraid

`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.17 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.18 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
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.19 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.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
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```

gap3-jm
11 Mar 2019