This chapter deals with another, quite specialised, class of finitely presented groups for which the word problem is solvable, the category of braid groups. The corresponding Magma category is called GrpBrd.
The notion of braid groups was introduced by Artin [Art47], who considered a sequence Bn (n=1, 2, ...) of groups, where Bn is presented on n - 1 generators s1, ..., sn - 1 with the defining relations
s_i s_j = s_j s_i (0 < i < j < n, j-i > 1)
s_i s_{i+1} s_i = s_{i+1} s_i s_{i+1} (0 < i < n-1) .
Bn is called braid group on n strings. In the sequel, we
refer to the above presentation as Artin presentation and to
s1, ..., sn - 1 as Artin generators of Bn.
Birman, Ko and Lee introduced an alternative way of presenting braid groups [BKL98]. Here, Bn is presented on n(n - 1)/2 generators ar, t (n ≥r > t ≥1) with the defining relations
a_{t,s} a_{r,q} = a_{r,q} a_{t,s} (n ≥t > s ≥1, n ≥r > q ≥1,
(t-r)(t-q)(s-r)(s-q) > 0)
a_{t,s} a_{s,r} = a_{t,r} a_{t,s} = a_{s,r} a_{t,r} (n ≥t > s > r > 0) .
We refer to this presentation as BKL presentation and to
ar, t (n ≥r > t ≥1) as BKL generators of Bn.
A possible choice for the BKL generators in terms of Artin generators is ar, t = (sr - 1...st + 1) st (st + 1 - 1...sr - 1 - 1). This identification is used in Magma.
Recently, braid groups came under consideration as possible sources for public key cryptosystems [AAG99], [KLC+00]. The features of braid groups which make them interesting for public key cryptography are the following.
The Magma category GrpBrd was introduced mainly with these applications in mind. Focus was put on providing fast operations with elements and on giving the user as much control over the details of computations as possible.
In this section we briefly recall the basic terminology used for describing elements of braid groups. More detailed descriptions can be found in [ECH+92] for the Artin presentation and in [BKL98] for the BKL presentation.
We remark that both Artin presentation and BKL presentation are special cases of so-called Garside groups [Deh02].
In the sequel, let M be either the Artin presentation or the BKL presentation of the braid group B on n strings, let X denote the generators of M and let R denote the relations of M. As the relations in R do not contain inverses of generators, we can interpret M as monoid presentation. We denote the finitely presented monoid defined by M by B^ +. The natural homomorphism from B^ + to B can be shown to be injective. We identify its image with B^ + and call it the set of positive elements of B. Finally, we denote the identity of B by 1.
We can now define two partial orderings on B. For elements u, v ∈B we say u preceq v, if there exists a positive element a such that ua = v, and we say v succeq u, if there exists a positive element a such that v = au. Note that these partial orderings are different; u preceq v is not equivalent to v succeq u.
B can be shown to be a lattice with respect to both partial orderings, that is, for elements u, v ∈B there are elements dl, ml, dr, mr ∈B such that
d_l \preceq u, d_l \preceq v and
d \preceq u, d \preceq v implies d \preceq d_l for all d in B
u \preceq m_l, v \preceq m_l and
u \preceq m, v \preceq m implies m_l \preceq m for all m in B
u \succeq d_r, v \succeq d_r and
u \succeq d, v \succeq d implies d_r \succeq d for all d in B
m_r \succeq u, m_r \succeq v and
m \succeq u, m \succeq v implies m \succeq m_r for all m in B
We call dl, ml, dr and mr the left-gcd, the left-lcm,
the right-gcd and the right-lcm, respectively, of u and v.
It can be shown that the left-lcm of the elements of X and the right-lcm of the elements of X are equal; we call this element the fundamental element of the presentation M and denote it by D. The fundamental element is crucial for the study of braid groups. One of its most important properties is that a certain power DN of D generates the centre of B. (N = 2 for the Artin presentation and N = n for the BKL presentation.) Moreover, u preceq Dk is equivalent to Dk succeq u and Dk preceq u is equivalent to u succeq Dk for all k ∈Z, u ∈B.
In Magma, the partial ordering preceq is provided as operator le and the partial ordering succeq is provided as operator ge; see Section Boolean Predicates for Elements. For a description of the functions computing lcm and gcd of elements, see Section Lattice Operations.
The positive elements c of B satisfying c preceq D are called simple elements; we denote the set of simple elements by C. simple elements can be uniquely described by permutations on n points. In Magma, a simple element c inducing a permutation π on the strings on which B is defined, is represented by the permutation π - 1.
If M is the Artin presentation, every permutation on n points corresponds to a simple element, that is, |C| = n!.
If M is the BKL presentation, |C| = (2n)!/(n!(n + 1)!) and only permutations on n points which are products of parallel, descending cycles correspond to simple elements. Here, a cycle (i1, ..., ir) is called descending if i1> ... >ir and two descending cycles (i1, ..., ir) and (j1, ..., js) are called parallel if (ik - jl)(ik - jl')(ik' - jl)(ik' - jl') > 0 for all 1≤k, k'≤r and 1≤l, l'≤s. The descending cycle (i1, ..., ir) corresponds to the element ai1, i2ai2, i3 ... a_(ir - 1, ir) of B. It is obvious from the defining relations that the simple elements defined by two parallel descending cycles commute.
Every element u of B can be written in the form u = Dl c1 ... ck, where l is a suitable integer and c1, ... ck are simple elements. We call representations of this form simple element representations or canonical factor products (CFP).
This section describes the ways in which elements of a braid group can be represented internally by Magma. From the user's point of view, this mainly affects input and printing of elements. This section is intended to be a concise overview; for a detailed description of functions and for examples we refer to Section Constructing and Accessing Braid Groups, Section Creating Elements of a Braid Group and Section Accessing Information.
Since an element of a braid group B can be represented either as word in the generators or as product of simple elements (see Section Lattice Operations) with respect to either the Artin presentation or the BKL presentation of B, there are four different ways of representing elements of B, which can be used for entering or printing elements and for computing with elements.
Magma can work with all the above representations and conversions are done automatically when necessary, for example, when multiplying an element defined as word in the Artin generators with an element given as product of simple elements for the BKL presentation. Hence, the user normally does not have do give too much thought about how elements are represented. It should be noted, however, that automatic conversions can affect performance and that in time critical situations, the best results in general are obtained if automatic conversions are avoided.
When creating a braid group B using the command BraidGroup, the user can specify whether the Artin presentation or the BKL presentation should be used as default presentation for B. Unless specified otherwise by the user, this presentation is used in all subsequent operations with B or with elements of B. In particular, group operations and printing of elements are performed with respect to this presentation. It is possible to change the default presentation using the command SetPresentation. Certain commands accept a parameter Presentation, which can be used to perform that command with respect to a presentation other than the default presentation.
By default, group operations with elements of a braid group B are performed using representations of the elements as products of simple elements for the default presentation of B. Experienced users can change this behaviour using the command SetForceCFP. If this flag is set to false, arguments of a group operation are not automatically converted into CFP representation if both arguments are represented as words in the generators of the default presentation of B, but the operation is performed, if possible, using the word representations instead.
The default printing format for an element u of a braid group B is that both a representation of u as word in the generators of the default presentation of B and a representation of u as product of simple elements for the default presentation of B are printed.
Depending on the application, the user may wish to change the print format so that only one of the above representations of u is printed. This can be achieved using the command SetElementPrintFormat.
This section briefly describes the normal form for elements of braid groups. For details we refer to [ECH+92] and [BKL98]. The Magma commands for computing normal forms are described in Section Computing Normal Forms of Elements.
Let B be the braid group on n strings and fix a presentation M for B, either the Artin presentation or the BKL presentation. A product of simple elements Dl c1 ... ck is said to be in left normal form with respect to M, if c1 ≠D, ck ≠1 and (ci - 1D) ^l ci + 1 = 1 for i = 1, ..., k - 1, where (ci - 1D) ^l ci + 1 denotes the left-gcd of ci - 1D and ci + 1 with respect to the presentation M.
Similarly, we define c1 ... ck Dl to be in right normal form with respect to M, if ck ≠D, c1 ≠1 and ci ^r (Dci + 1 - 1) = 1 for i = 1, ..., k - 1, where ^r denotes right-gcd with respect to the presentation M.
It can be shown that the numbers of simple elements and the powers of D in the left and right normal forms of an element are equal, that is, if x∈B has left normal form Dl c1 ... ck and right normal form bar(c)1 ... bar(c)kprime Dlprime then kprime=k and lprime=l. In this situation we call l the infimum of x, denoted by inf(x), k the canonical length of x, denoted by len(x), and l + k the supremum of x, denoted by sup(x). l is the maximal integer d satisfying Ddpreceq x and l + k is the minimal integer d satisfying x preceq Dd.
To bring a product Dl c1 ... ck of simple elements into left normal form, we proceed by induction, assuming that Dl c1 ... ck - 1 is in left normal form. For i = k - 1, ..., 1 we now compute d = (ci - 1D) ^l ci + 1 and, if d ≠1, replace ci by ci d and ci + 1 by d - 1 ci + 1. Finally, we delete trailing trivial simple elements and absorb simple elements equal to D into the leading power of D. The result can be shown to be in left normal form [ECH+92], [BKL98].
Both the theoretical complexity of this algorithm and its performance in practice are determined by the gcd computations.
For the Artin presentation, the cost of computing the left-gcd of two simple elements is O(n log n) [ECH+92], whence the complexity of bringing a product of simple elements as above into left normal form is O(k2 n log n).
For the Artin presentation, the cost of computing the left-gcd of two simple elements is O(n) [BKL98], whence the complexity of bringing a product of simple elements as above into left normal form is O(k2 n).
Computing right normal forms is analogous.
This section outlines the algorithms used for lattice operations in a braid group. Let u and v be elements of a braid group B and let M be either the Artin presentation or the BKL presentation of B. The Magma commands for computing mixed canonical forms are described in Section Computing Normal Forms of Elements and the commands providing lattice operations are described in Section Lattice Operations.
Evaluating partial orderings for u and v with respect to M is straightforward. u preceq v if and only if u - 1 v is a positive element with respect to M. The latter can be decided by computing the left normal form Dl c1 ... ck of u - 1 v with respect to M: u - 1 v is positive if and only if l≥0. Evaluating the partial ordering succeq is analogous.
We call the tuple <a, b> the left-mixed canonical form of an element x∈B, if a = a1 ... ak and b = b1 ... bs are positive elements in left normal form (a1 = D, b1 = D is permitted), x = a - 1b and the left-gcd of a1 and b1 is trivial.
Similarly, we call the tuple <a, b> the right-mixed canonical form of x, if a = a1 ... ak and b = b1 ... bs are positive elements in right normal form (ak = D, bs = D is permitted), x = ab - 1 and the right-gcd of ak and bs is trivial.
It is not difficult to show that the left-gcd of u and v is given by u a - 1, where <a, b> is the left-mixed canonical form of u - 1v, and that the right-gcd of u and v is given by a - 1u, where <a, b> is the right-mixed canonical form of u v - 1 [ECH+92].
Similarly, the left-lcm of u and v is given by ua, where <a, b> is the right-mixed canonical form of u - 1v and the right-lcm of u and v is given by au, where <a, b> is the left-mixed canonical form of u v - 1
Computing the left-mixed canonical form of an element x can, after writing x=a - 1b with two positive elements a and b, easily be reduced to computing repeatedly the left-normal forms of a and b and cancelling the left-gcd of the leading simple elements. Computing the right-mixed canonical form is analogous.
Conjugacy testing, that is, deciding whether two given braids are conjugate, and conjugacy search, that is, computing a conjugating element for a pair of conjugate braids, are of particular importance to public key cryptosystems based on braid groups. Known algorithms for both conjugacy testing and conjugacy search require the (at least partial) computation of an invariant of the conjugacy classes of the elements in question, either the super summit set [Gar69], [ERM94] or the ultra summit set [Geb03].
This section recalls the definition of these invariants and sketches the algorithms used for computing them, for conjugacy testing and for conjugacy search. The relevant Magma commands are described in Section Invariants of Conjugacy Classes.
For this section let B be a braid group and let M be either the Artin presentation or the BKL presentation of B.
We define two operations, the cycling operation cyc and the decycling operation dec, each mapping an arbitrary element x∈B to a conjugate of x as follows. Let x∈B be a braid with left normal form x = Dl c1 ... ck as defined in Section Normal Form for Elements of a Braid Group. If k=0, we define cyc(x) = x and dec(x) = x. Otherwise, we define cyc(x) = Dl c2 ... ck (c1^(D - l)) and dec(x) = Dl (ckDl) c1 ... ck - 1.
We now fix an element x∈B and consider the set Cx of all conjugates of x. Proofs for the following facts can be found in [ECH+92] or [BKL98].
Proofs of the following properties can be found in [ECH+92] and [BKL98] for the sets Px and Sx and in [Geb03] for the set Ux.
The main tools for computing the class invariants introduced in Section Definition of the Class Invariants are the following "convexity" results established in [ERM94] and [FGM03] for the sets Px and Sx and in [Geb03] for the set Ux. Let Ix ∈{ Px, Sx, Ux }.
Algorithms for computing the minimal simple elements ιy(c) are given in [FGM03] for the case Ix ∈{Px, Sx} and in [Geb03] for the case Ix = Ux.
The Magma commands for computing the class invariants Px, Sx and Ux as well as corresponding minimal simple elements ιy(c) are described in Section Invariants of Conjugacy Classes.
Testing conjugacy of two braids x, y∈B can be performed using either super summit sets or ultra summit sets. It is obvious from the results cited in Section Definition of the Class Invariants that the following are equivalent.
The size of super summit sets grows rapidly with increasing values of braid index n and canonical length. In general, computing super summit sets is difficult or infeasible for braids on more than 5-10 strings, except for very short canonical lengths. Ultra summit sets, on the other hand tend to be much smaller and can frequently be computed for braids on up to 100 strings and canonical length up to 1000, provided sufficient memory is available [Geb03]. Conjugacy search may be successful even in situations where the entire class invariant is too large to be computed.
In Magma, conjugacy testing and conjugacy search based on ultra summit sets is provided by the function IsConjugate.