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 B_n (n=1, 2, ...) of groups, where B_n is presented on n - 1 generators s_1, ..., s_(n - 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) .
B_n is called braid group on n strings. In the sequel, we
refer to the above presentation as Artin presentation and to
s_1, ..., s_(n - 1) as Artin generators of B_n.
Birman, Ko and Lee introduced an alternative way of presenting braid groups [BKL98]. Here, B_n is presented on n(n - 1)/2 generators a_(r, t) (n >= r > t >= 1) with the defining relations
a_{t,s} a_{r,q} = a_{r,q} a_{t,s} (n \ge t > s \ge 1, n \ge r > q \ge 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 \ge t > s > r > 0) .
We refer to this presentation as BKL presentation and to
a_(r, t) (n >= r > t >= 1) as BKL generators of B_n.
A possible choice for the BKL generators in terms of Artin generators is a_(r, t) = (s_(r - 1)...s_(t + 1)) s_t (s_(t + 1)^(-1)...s_(r - 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.
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.
In the sequel, let P be either the Artin presentation or the BKL presentation of the braid group B on n strings, let X denote the generators of P and let R denote the relations of P. As the relations in R do not contain inverses of generators, we can interpret P as monoid presentation. We denote the finitely presented monoid defined by P 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 in 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 in B there are elements d_l, m_l, d_r, m_r in 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 d_l, m_l, d_r and m_r 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 P 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 D^N of D generates the centre of B. (N = 2 for the Artin presentation and N = n for the BKL presentation.) Moreover, u preceq D^k is equivalent to D^k succeq u and D^k preceq u is equivalent to u succeq D^k for all k in Z, u in B.
In Magma, the partial ordering preceq is provided as operator le and the partial ordering succeq is provided as operator le; 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 canonical factors; we denote the set of canonical factors by C. Canonical factors can be uniquely described by permutations on n points. In Magma, a canonical factor c inducing a permutation pi on the strings on which B is defined, is represented by the permutation pi^(-1).
If P is the Artin presentation, every permutation on n points corresponds to a canonical factor, that is, |C| = n!.
If P is the BKL presentation, |C| = (2n)!/(n!(n + 1)!) and only permutations on n points which are products of parallel, descending cycles correspond to canonical factors. Here, a cycle (i_1, ..., i_r) is called descending if i_1> ... >i_r and two descending cycles (i_1, ..., i_r) and (j_1, ..., j_s) are called parallel if (i_k - j_l)(i_k - j_(l'))(i_(k') - j_l)(i_(k') - j_(l')) > 0 for all 1 <= k, k' <= r and 1 <= l, l' <= s. The descending cycle (i_1, ..., i_r) corresponds to the element a_(i_1, i_2)a_(i_2, i_3) ... a_(i_(r - 1), i_r) of B. It is obvious from the defining relations that the canonical factors defined by two parallel descending cycles commute.
Every element u of B can be written in the form u = D^l c_1 ... c_k, where l is a suitable integer and c_1, ... c_k are canonical factors. We call representations of this form canonical factor 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 canonical factors (see Section Lattice Structure and Canonical Factors) 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 canonical factors 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 canonical factors 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 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 canonical factors 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 P for B, either the Artin presentation or the BKL presentation. A product of canonical factors D^l c_1 ... c_k is said to be in left normal form with respect to P, if c_1 != D, c_k != 1 and (c_i^(-1)D) wedge_l c_(i + 1) = 1 for i = 1, ..., k - 1, where (c_i^(-1)D) wedge_l c_(i + 1) denotes the left-gcd of c_i^(-1)D and c_(i + 1) with respect to the presentation P.
Similarly, we define c_1 ... c_k D^l to be in right normal form with respect to P, if c_k != D, c_1 != 1 and c_i wedge_r (Dc_(i + 1)^(-1)) = 1 for i = 1, ..., k - 1, where wedge_r denotes right-gcd with respect to the presentation P.
To bring a product D^l c_1 ... c_k of canonical factors into left normal form, we proceed by induction, assuming that D^l c_1 ... c_(k - 1) is in left normal form. For i = k - 1, ..., 1 we now compute d := (c_i^(-1)D) wedge_l c_(i + 1) and, if d != 1, replace c_i by c_i d and c_(i + 1) by d^(-1) c_(i + 1). Finally, we delete trailing trivial canonical factors and absorb canonical factors 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 canonical factors is O(n log n) [ECH+92], whence the complexity of bringing a product of canonical factors as above into left normal form is O(k^2 n log n).
For the Artin presentation, the cost of computing the left-gcd of two canonical factors is O(n) [BKL98], whence the complexity of bringing a product of canonical factors as above into left normal form is O(k^2 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 P 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 P is straightforward. u preceq v if and only if u^(-1) v is a positive element with respect to P. The latter can be decided by computing the left normal form D^l c_1 ... c_k of u^(-1) v with respect to P: 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 in B, if a = a_1 ... a_k and b = b_1 ... b_s are positive elements in left normal form (a_1 = D, b_1 = D is permitted), x = a^(-1)b and the left-gcd of a_1 and b_1 is trivial.
Similarly, we call the tuple <a, b> the right-mixed canonical form of x, if a = a_1 ... a_k and b = b_1 ... b_s are positive elements in right normal form (a_k = D, b_s = D is permitted), x = ab^(-1) and the right-gcd of a_k and b_s 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^(-1)v, and that the right-gcd of u and v is given by a^(-1)u, 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^(-1)v, and that 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^(-1)b 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 canonical factors. Computing the right-mixed canonical form is analogous.
This section recalls the definition of the super summit set of an element and sketches the algorithms used for computing super summit sets and sets of positive conjugates. The relevant Magma commands are described in Section Positive Conjugates and Super Summit Sets.
Let B be a braid group and let P be either the Artin presentation or the BKL presentation of B. Let x be an element of B with left normal form x = D^l c_1 ... c_k as defined in Section Normal Form for Elements of a Braid Group. We call inf(x) := l the infimum of x, k the canonical length of x and sup(x) := l + k the supremum of x. l is the maximal integer d satisfying D^d preceq x and l + k is the minimal integer d satisfying x preceq D^d. Moreover define c(x) := D^l c_2 ... c_k (c_1^(D^(-l))), the cycling of x, and d(x) := D^l (c_k^(D^l)) c_1 ... c_(k - 1), the decycling of x. Note that c(x) and d(x) are conjugates of x.
Consider now the set C_x of all conjugates of x and the set P_x of all positive conjugates of x. Proofs for the following facts can be found in [ECH+92] or [BKL98].
The main tool for computing the set of positive conjugates or the super summit set of an element is the following "convexity" result [ERM94]:
Let M be either S_x or P_x. For y, z in M, there exists a finite sequence y = y_0, ..., y_r=z such that for i=1, ..., r, y_i in M and y_i = y_(i - 1)^(c_i) for a canonical factor c_i.
Since there are only finitely many canonical factors, M can be computed from a representative found as described above as closure under conjugation with canonical factors. This algorithm can be improved significantly by restricting to conjugation by minimal canonical factors; for details we refer to [FGM01].
Testing conjugacy of elements can be reduced to the computation of super summit sets. From the definition of the super summit set S_x of x it is obvious that S_x depends only on the conjugacy class of x. Moreover, since S_x consists of conjugates of x and is non-empty, two elements x and y of a braid group B are conjugate in B if and only if S_x = S_y. In Magma, conjugacy of elements can be tested using the function IsConjugate.
[Next][Prev] [Right] [____] [Up] [Index] [Root]