Garside monoids and groups, braids.

Chevie.Garside — Module

Garside monoids are a general class of monoids whose most famous examples are the braid and dual braid monoids. They have groups of fractions which in both examples are the braid group. Here we implement braid groups in the framework of a general implementation of Garside monoids and groups.

To define Garside monoids we 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, and write d≼ x). We say that a monoid M is left cancellable if an equality dx=dy implies x=y. We define symmetrically right-divisors, left multiples and right cancellability. We say that x is an atom if 1 and x are its only divisors. 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 left-divisor 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 call Garside a monoid M which:

is left and right cancellable.
is generated by its atoms.
admits left and right gcds and lcms.
is such that any element has only finitely many left (or right) divisors.
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 that a Garside 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 (a group can have several different Garside structures, for instance braid groups of finite Coxeter groups have an ordinary and a dual braid monoid).

We also implement locally Garside monoids, which are monoids where lcms do not always exist, but exist if any common multiple exists; the set of simples is then not defined by a Garside element, but by the condition that they contain the atoms and are closed under lcms and taking divisors (see BDM01); since this is not ensured by the existence of a Garside element, one has to add the condition that each element is divisible by finitely many simples (but the number of simples can be infinite). The most important example is the Artin monoid of an infinite Coxeter group. It is not known whether these monoids embed in their group of fractions (although this has been proved for Artin 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 here for these cases.

What allows computing with Garside and locally Garside monoids, and Garside groups, is the fact that they admit normal forms –- these normal forms were exhibited for braid monoids of Coxeter groups by Deligne Del72, who extended earlier work of Brieskorn, Saito BS72 and Garside Gar69:

Let M be a locally Garside monoid. Then for b∈ M there is a unique maximal simple left-divisor α(b) of b; any other simple dividing b divides α(b).
Let M be a Garside monoid with Garside element Δ and group of fractions G. Then for any x∈ G, for large enough i we have Δⁱx∈ M.

A consequence of 1. is that every 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 we use 2. to represent elements of G: given x∈ G we compute the smallest power i such that Δⁱ x∈ M, and we represent x by the pair (i,Δ⁻ⁱx). We are thus reduced to the case where x∈ M, not divisible by Δ, where we represent x by the sequence of simples that make up its normal form.

We now describe Artin-Tits braid monoids. Let (W,S) be a Coxeter system, that is W has presentation

⟨s∈ S∣s²=1, sts⋯ =tst⋯ (mₛₜ factors on each side) for s,t∈ S⟩

for some Coxeter matrix mₛₜ. The braid group B associated to (W,S) is the group defined by the presentation

⟨𝐬∈ 𝐒∣ 𝐬𝐭𝐬⋯ =𝐭𝐬𝐭⋯ (mₛₜ factors on each side) for 𝐬,𝐭∈ 𝐒⟩

The positive braid monoid B⁺ associated with W is the monoid defined by the presentation above –- it identifies with the submonoid of B generated by 𝐒 by Paris01. This monoid is locally Garside, with the set of simples in bijection with the elements of W and with 𝐒 as atoms; we will denote by 𝐖 the set of simples, and by 𝐰 ↦ w the bijection between simples and elements of W. The group W has a length defined in terms of reduced expressions. Similarly, having only homogeneous relations, B⁺ has a natural length function. Then 𝐖 can be characterised as the subset of elements of B⁺ with the same length as their image in W.

If W is finite, then B⁺ is Garside with Garside element the element of 𝐖 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 also has a topological definition as the fundamental group of the space Vʳᵉᵍ/W, where Vʳᵉᵍ is the set of elements of V which are not fixed by any non-identity element of S; however, we will not use this here.

We implement in general only monoids which have a finite number of atoms (there an implementation following the work of François Digne for the dual braid monoid of the affine Coxeter group W(Ãₙ)).

Given a Coxeter group W,

julia> W=coxgroup(:A,4)
A₄

julia> B=BraidMonoid(W)
BraidMonoid(A₄)

constructs the associated braid monoid, and then, used as a function, B constructs elements of the braid monoid (or group when W is finite) from a list of generators:

julia> w=B(1,2,3,4) # represents 𝐬₁𝐬₂𝐬₃𝐬₄
1234

julia> w^3  # the terms of the normal form are printed separated by a .
121321432.343

julia> word(α(w^3))
9-element Vector{Int64}:
 1
 2
 1
 3
 2
 1
 4
 3
 2

julia> w^4
Δ.232432

julia> inv(w)
(1234)⁻¹

How an element of a Garside group is printed is controlled by the IOcontext attribute ':greedy'. By default, elements are printed as fractions a⁻¹b 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 by the rest. One can print the entire element in the left-greedy normal from by setting the IOContext :greedy=>true; with the same w as above we have:

julia> xrepr(w^-1,greedy=true,limit=true)
"Δ⁻¹.232432"

By default, repr gives w back in a form which after assigning B=BraidMonoid(W) can be input back into Julia:

julia> repr(w)
"B(1,2,3,4)"

julia> repr(w^3)
"B(1,2,1,3,2,1,4,3,2,3,4,3)"

julia> repr(w^-1)
"B(-4,-3,-2,-1)"

In general elements of a Garside monoid are displayed as a list of their constituting atoms.

We now describe the dual braid monoid. For that, we first define interval monoids. Given a group W and a set S of generators of W as a monoid, we define the S-length l_S(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_S(d)+l_S(y)=l_S(x). We say that w∈ W is balanced if its set of left and right-divisors coincide; in which case we denote this set by [1,w], an "interval" for the poset of S-divisibility. We say that w is Garside for the S-length if it is balanced and [1,w] is a lattice (where upper and lower bounds are lcms and gcds), which generates W. Then we have the theorem:

Suppose w is Garside for the S-length. Then the monoid M with generators [1,w] and relations xy=z whenever xy=z holds in W and l_S(x)+l_S(y)=l_S(z), is a Garside monoid, with simples [1,w] and atoms S. It is called the interval monoid defined by the interval [1,w].

The Artin-Tits braid monoid is an interval monoid by taking for S the Coxeter generators, in which case l_S 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 w a Coxeter element, for l_S the reflection length 'reflength' and for S_S the reflections which divide w for the reflection length (for Coxeter groups all reflections divide w but for well-generated complex reflection groups not all reflections divide); for the dual monoid the simples are of cardinality the generalized Catalan numbers catalan. An interval monoid has naturally an inverse morphism from M to W, called 'image' which is the quotient map from the interval monoid to W which sends back simple braids to [1,w].

A last pertinent notion is reversible monoids. Since we store left normal forms, it is easy to compute left lcms and gcds, but hard to compute right lcms and gcds. But this becomes easy to do if the monoid has an operation 'reverse', 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 of groups generated by true reflections; 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⁻¹. The operations 'rightlcm' and 'rightgcd', and some other algorithms, have faster implementations if the monoid has a reverse operation.

This module implements also functions to solve the conjugacy problem and compute centralizers in Garside groups, following the work of Franco, Gebhardt and Gonzalez-Meneses.

Two elements w and w' 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⁻¹wx=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 Δⁱ which is central and such that xΔⁱ∈ M. Then wxΔⁱ=xΔⁱ w' is a conjugation in M.

The crucial observation for solving the conjugacy problem is to introduce inf(w):=sup{i such that Δ⁻ⁱw∈ M} and sup(w):=inf{i such that w⁻¹Δⁱ∈ M}, and to notice that the number of conjugates of w with same inf and sup as w is finite (since our monoids have a finite number of atoms). 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. For the implementation of finite categories we use, see the docstrings of Category and endomorphisms.

We illustrate this on an example:

julia> b=B(2,1,4,1,4)
214.14

julia> c=B(1,4,1,4,3)
14.143

julia> d=conjugating_elt(b,c)
(1)⁻¹21321432

julia> b^d
14.143

julia> centralizer_gens(b)
3-element Vector{GarsideElt{Perm{Int16}, BraidMonoid{Perm{Int16}, FiniteCoxeterGroup{Perm{Int16},Int64}}}}:
 321432.213243
 21.1
 4

julia> C=conjcat(b;ss=Val(:ss))
category with 10 objects and 32 generating maps

julia> C.obj
10-element Vector{GarsideElt{Perm{Int16}, BraidMonoid{Perm{Int16}, FiniteCoxeterGroup{Perm{Int16},Int64}}}}:
 1214.4
 214.14
 124.24
 1343.1
 14.124
 143.13
 24.214
 134.14
 13.134
 14.143

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 slide 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 slide 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,

julia> word(W,preferred_prefix(b))
2-element Vector{Int64}:
 2
 1

julia> b^B(preferred_prefix(b))
1214.4

julia> b1=b^B(preferred_prefix(b))
1214.4

julia> C=conjcat(b)
category with 2 objects and 6 generating maps

julia> C.obj
2-element Vector{GarsideElt{Perm{Int16}, BraidMonoid{Perm{Int16}, FiniteCoxeterGroup{Perm{Int16},Int64}}}}:
 1214.4
 1343.1

Finally, we have implemented Hao Zheng's algorithm to extract roots in a Garside monoid:

julia> W=coxgroup(:A,3)
A₃

julia> B=BraidMonoid(W)
BraidMonoid(A₃)

julia> Pi=B(B.δ)^2
Δ²

julia> root(Pi,2)
Δ

julia> root(Pi,3)
1232

julia> root(Pi,4)
132