Introduction#

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 [Artin, 1947], who considered a sequence \(B_n\) \((n=1,2,\dots)\) of groups, where \(B_n\) is presented on \(n-1\) generators \(\sigma_1,\dots,\sigma_{n-1}\) with the defining relations

\[\begin{split}\begin{aligned}\sigma_i\sigma_j & = \sigma_j\sigma_i \quad\quad\quad\quad (1\le i < j < n,\quad j-i>1) ,\\ \sigma_i\sigma_{i+1}\sigma_i & = \sigma_{i+1}\sigma_i\sigma_{i+1} \quad (1\le i < n-1) \quad .\end{aligned}\end{split}\]

\(B_n\) is called the braid group on \(n\) strings. In the sequel, we refer to the above presentation as Artin presentation and to \(\sigma_1,\dots,\sigma_{n-1}\) as Artin generators of \(B_n\).

Birman, Ko and Lee introduced an alternative way of presenting braid groups [Birman et al., 1998]. Here, \(B_n\) is presented on \(n(n-1)/2\) generators \(a_{r,t}\) \((n \ge r > t \ge 1)\) with the defining relations

\[\begin{split}\begin{aligned}a_{t,s} a_{r,q} & = a_{r,q} a_{t,s} \quad\hbox{for}\; 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} \quad\hbox{for}\; n \ge t > s > r > 0 \quad .\end{aligned}\end{split}\]

We refer to this presentation as BKL presentation and to \(a_{r,t}\) \((n \ge r > t \ge 1)\) as BKL generators of \(B_n\).

A possible choice for the BKL generators in terms of Artin generators is \(a_{r,t} = (\sigma_{r-1}\cdots\sigma_{t+1}) \sigma_t (\sigma_{t+1}^{-1}\cdots\sigma_{r-1}^{-1})\). This identification is used in Magma.

Recently, braid groups came under consideration as possible sources for public key cryptosystems [Anshel et al., 1999, Ko et al., 2000]. The features of braid groups which make them interesting for public key cryptography are the following.

  • The basic group operations in braid groups can be implemented efficiently on a computer.

  • The word problem in braid groups is solvable, that is, there is a normal form for elements of a braid group and elements can be compared. Moreover, there are algorithms which are able to compute the normal form of an element efficiently.

  • There are several problems in braid groups which are believed to be mathematically hard and whose use for cryptographic purposes has been suggested. The most important examples are variations of the conjugacy problem.

However, both recent attacks on particular cryptosystems [Garber et al., 2002, Hofheinz and Steinwandt, 2003, Hughes, 2002, Lee and Park, 2003, Lee and Lee, 2002] and advances in the analysis of the conjugacy problem [Gebhardt, 2003, González-Meneses, 2002] in general shed some doubts on the security of braid group cryptosystems. At the time of this writing it is an open question whether braid group cryptosystems can be made secure by an appropriate choice of parameters and keys or whether they have to be considered as insecure. More research into these issues is necessary.

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.

Lattice Structure and Simple Elements#

In this section we briefly recall the basic terminology used for describing elements of braid groups. More detailed descriptions can be found in [Epstein et al., 1992] for the Artin presentation and in [Birman et al., 1998] for the BKL presentation.

We remark that both Artin presentation and BKL presentation are special cases of so-called Garside groups [Dehornoy, 2002].

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

\[\begin{split}\begin{aligned}d_l \preceq u, \; d_l \preceq v \quad&\hbox{and}\quad d \preceq u, \; d \preceq v \;\;\hbox{implies}\;\; d \preceq d_l\;\;\hbox{for all}\;\; d \in B \\ u \preceq m_l, \; v \preceq m_l \quad&\hbox{and}\quad u \preceq m, \; v \preceq m \;\;\hbox{implies}\;\; m_l \preceq m\;\;\hbox{for all}\;\; m \in B \\ u \succeq d_r, \; v \succeq d_r \quad&\hbox{and}\quad u \succeq d, \; v \succeq d \;\;\hbox{implies}\;\; d_r \succeq d\;\;\hbox{for all}\;\; d \in B \\ m_r \succeq u, \; m_r \succeq v \quad&\hbox{and}\quad m \succeq u, \; m \succeq v \;\;\hbox{implies}\;\; m \succeq m_r\;\;\hbox{for all}\;\; m \in B \quad.\end{aligned}\end{split}\]

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 \(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 \(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 {\mathbb{Z}}, u \in B\).

In Magma, the partial ordering \(\preceq\) is provided as operator u le v and the partial ordering \(\succeq\) is provided as operator u ge v; 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 \(\pi\) on the strings on which \(B\) is defined, is represented by the permutation \(\pi^{-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 \((i_1,\dots,i_r)\) is called descending if \(i_1>\dots>i_r\) and two descending cycles \((i_1,\dots,i_r)\) and \((j_1,\dots,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\le k,k'\le r\) and \(1\le l,l'\le s\). The descending cycle \((i_1,\dots,i_r)\) corresponds to the element \(a_{i_1,i_2}a_{i_2,i_3}\cdots a_{i_{r-1},i_r}\) 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 = D^l c_1\cdots c_k\), where \(l\) is a suitable integer and \(c_1,\dots c_k\) are simple elements. We call representations of this form simple element representations or canonical factor products (CFP).

Representing Elements of a Braid Group#

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 Structure and Simple Elements) 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.

Automatic Conversions#

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.

Default Presentations#

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.

Representation Used for Group Operations#

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.

Printing of Elements#

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.

Normal Form for Elements of a Braid Group#

This section briefly describes the normal form for elements of braid groups. For details we refer to [Epstein et al., 1992] and [Birman et al., 1998]. 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 \(D^l c_1\cdots c_k\) is said to be in left normal form with respect to \(M\), if \(c_1 \ne D\), \(c_k \ne 1\) and \((c_i^{-1}D) \wedge_l c_{i+1} = 1\) for \(i = 1,\dots,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 \(M\).

Similarly, we define \(c_1\cdots c_k D^l\) to be in right normal form with respect to \(M\), if \(c_k \ne D\), \(c_1 \ne 1\) and \(c_i \wedge_r (Dc_{i+1}^{-1}) = 1\) for \(i = 1,\dots,k-1\), where \(\wedge_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\in B\) has left normal form \(D^l c_1\cdots c_k\) and right normal form \(\bar{c}_1\cdots \bar{c}_{k^\prime} D^{l^\prime}\) then \(k^\prime=k\) and \(l^\prime=l\). In this situation we call \(l\) the infimum of \(x\), denoted by \(\inf(x)\), \(k\) the canonical length of \(x\), denoted by \(\hbox{len}(x)\), and \(l+k\) the supremum of \(x\), denoted by \(\sup(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\).

To bring a product \(D^l c_1\cdots c_k\) of simple elements into left normal form, we proceed by induction, assuming that \(D^l c_1\cdots c_{k-1}\) is in left normal form. For \(i = k-1,\dots,1\) we now compute \(d = (c_i^{-1}D) \wedge_l c_{i+1}\) and, if \(d \ne 1\), replace \(c_i\) by \(c_i d\) and \(c_{i+1}\) by \(d^{-1} c_{i+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 [Birman et al., 1998, Epstein et al., 1992].

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)\) [Epstein et al., 1992], whence the complexity of bringing a product of simple elements 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 simple elements is \(O(n)\) [Birman et al., 1998], whence the complexity of bringing a product of simple elements as above into left normal form is \(O(k^2 n)\).

Computing right normal forms is analogous.

Mixed Canonical Form and Lattice Operations#

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 \(D^l c_1\cdots c_k\) of \(u^{-1} v\) with respect to \(M\): \(u^{-1} v\) is positive if and only if \(l\ge 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\cdots a_k\) and \(b = b_1\cdots 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\cdots a_k\) and \(b = b_1\cdots 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}\) [Epstein et al., 1992].

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 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 simple elements. Computing the right-mixed canonical form is analogous.