Patrick Dehornoy
email: dehornoy@math.unicaen.fr

EFFICIENT SOLUTIONS TO THE BRAID ISOTOPY PROBLEM

Keywords: 1991 Mathematics Subject Classification. 20F36, 94A60 braid group, isotopy problem, word problem, greedy normal form, word redressing, handle reduction, Dynnikov's coordinates

We describe the most efficient solutions to the word problem of Artin's braid group known so far, i.e., in other words, the most efficient solutions to the braid isotopy problem, including the Dynnikov method, which could be especially suitable for cryptographical applications. Most results appear in literature; however, some results about the greedy normal form and the symmetric normal form and their connection with grid diagrams may have never been stated explicitly.

Because they are both not too simple and not too complicated, Artin's braid groups B n have been and remain one of the most natural and promising platform groups for non-commutative group-based cryptography [START_REF] Anshel | An algebraic method for public-key cryptography[END_REF][START_REF] Ko | New public-key cryptosystem using braid groups[END_REF][START_REF] Dehornoy | Braid-based cryptography[END_REF]. More precisely, braid groups are not too simple in that they lead to problems with presumably difficult instances, typically the conjugacy problem and the related conjugacy and multiple conjugacy search problems, and they are not too complicated in that there exist efficient solutions to the word problem, a preliminary requirement when one aims at practically computing in a group. It turns out that, since the founding paper [START_REF] Artin | Theory of Braids[END_REF] appeared in 1947, the word problem of braid groups-which is also the braid isotopy problem-has received a number of solutions: braid groups might even be the groups for which the number of known solutions to the word problem is currently the highest one.

In this paper, we review some of these solutions, namely those that, at the moment, appear as the most efficient ones for practical implementation, and, therefore, the most promising ones for cryptographical applications. What makes the subject specially interesting is that these solutions relie on deep underlying structures that explain their efficiency. Five solutions are described, and they come in two families, namely those based on a normal form, and those that use no normal form. In the first family, we consider the so-called greedy normal form, both in its nonsymmetric and symmetric versions. In the second family, we consider the so-called word redressing method, which, like the greedy normal forms, has a quadratic complexity, the handle reduction method, whose complexity remains unknown but which is very efficient in practice, and Dynnikov's coordinization method, which relies on an entirely different, geometric approach, and might turn to be very efficient. In this description, we deliberately discard lots of alternative solutions which are intrinsically exponential in complexity.

The paper is organized as follows. In Section 1, after setting the background, we describe the greedy normal form and the symmetric normal form, without providing explicit rules to compute them. All results in this section are standard. In Section 2, we introduce grid diagrams and explain-and prove-how to use such diagrams to compute the normal forms of Section 1. Though more or less equivalent to that of [START_REF] Epstein | Word Processing in Groups[END_REF]Chapter 9], this approach is less standard, and, to the best of our knowledge, the results may have never been stated in the form given here. Finally, in Section 3, we describe the word redressing, handle reduction, and Dynnikov coordinates methods. The results here already appeared in literature, but Dynnikov's approach, which appears in [START_REF] Dehornoy | Why are braids orderable?[END_REF]Chapter 7], has not yet become classical. Also, the formulae of Section 3.3 have been optimized to make implementation easy.

Solutions based on a normal form

This section deals about solutions to the braid word problem that consist in defining for each braid x a unique distinguished representative called the normal form of x. When this is done, in order to compute with braids, it is in practice sufficient to work with normal representatives. There exist excellent normal forms for braids, namely those connected with the so-called greedy normal form based on Garside's theory [START_REF] Garside | The braid group and other groups[END_REF]. Here we describe them, successively in a non-symmetric and a symmetric version.

1.1. Braid groups. We first recall a few basic definitions and general results about braid groups.

1.1.1. Presentation. Artin's braid groups are infinite non-commutative groups. They appear in several a priori unrelated frameworks, and they admit many equivalent definitions. In our case, it will be convenient to introduce them by means of explicit presentations.

Definition 1.1. For n 2, the braid group B n is defined by the presentation (1.1) σ 1 , ..., σ n-1 ; σ i σ j = σ j σ i for |i -j| 2, σ i σ j σ i = σ j σ i σ j for |i -j| = 1 .

An element of B n will be called an n-braid. For each n, the identity mapping on {σ 1 , ..., σ n-1 } induces an embedding of B n into B n+1 , so that we can consider an n-braid as a particular (n + 1)-braid. Note that B 2 is an infinite cyclic group, i.e., is isomorphic to the group Z of integers. For n 3, the group B n is not commutative: the center of B n is the cyclic subgroup generated by the element ∆ 2 n , where ∆ n is introduced in (1.2) below.

When a group is specified using a presentation, each element of the group is an equivalence class of words with respect to the congruence generated by the relations of the presentation. In the sequel, a word on the letters σ ±1 1 , ..., σ ±1 n-1 will be called an n-braid word. So, every n-braid is an equivalence class of n-braid words under the congruence ≡ generated by the relations of (1.1). If the braid x is the equivalence class of the word w, we say that w is a representative of x, and we write x = w.

1.1.2. The word problem. Using ε for the empty word, the word problem of (1.1) is the algorithmic problem:

Given one braid word w, does w ≡ ε hold, i.e., does w represent the unit braid 1? This is the problem we investigate in the sequel. Because B n is a group, the above one parameter problem is equivalent to the two parameter problem:

Given two braid words w, w ′ , does w ≡ w ′ hold, i.e., do w and w ′ represent the same braid? Indeed, w ≡ w ′ is equivalent to w -1 w ′ ≡ ε, where w -1 is the word obtained from w by reversing the order of the letters and exchanging σ i and σ -1 i everywhere.

1.1.3. Geometric interpretation. The elements of B n can be interpreted as geometric n strand braids [START_REF] Birman | Braids, Links, and Mapping Class Groups[END_REF][START_REF] Kassel | Braid groups[END_REF][START_REF] Dehornoy | Why are braids orderable?[END_REF]. To this end, one associates with every braid word the plane diagram obtained by concatenating the elementary diagrams of Figure 1 corresponding to the successive letters.

1 i i+1 n σ i σ -1 i . . . . . . . . . . . . σ 1 σ -1 2 σ 1 σ 2 σ 1 σ 3 σ -1 1 σ -1 2 σ -1 1 σ -1 2 σ -1 1 σ 2 σ 2 σ -1 3 σ -1 2 Figure 1.
The n strand braid diagrams associated with σ i and σ -1 i , and the 4 strand braid diagram associated with the 4braid word

σ 1 σ -1 2 σ 1 σ 2 σ 1 σ 3 σ -1 1 σ -1 2 σ -1 1 σ -1 2 σ -1 1 σ 2 σ 2 σ -1 3 σ -1
2 -also denoted aBabacABABAbbCB in the sequel: one concatenates the successive 4 strand diagrams corresponding to the successive letters of the word.

A braid diagram can be seen as a plane projection of a three-dimensional figure consisting on n disjoint curves connecting the points (1, 0, 0), ..., (n, 0, 0) to the points (1, 0, 1), ..., (n, 0, 1) in R 3 . Then the relations of (1.1) correspond to ambient isotopy, i.e., to continuously moving the curves without moving their ends and without allowing them to intersect. It is easy to check that each relation in (1.1) corresponds to such an isotopy; the converse implication, i.e., the fact that the projections of isotopic 3D figures can always be encoded in words connected by (1.1) was proved by E. Artin in [START_REF] Artin | Theory of Braids[END_REF]. Thus the braid word problem for the presentation (1.1) is also the braid isotopy problem-thus similar to the (much more difficult) knot isotopy problem.

1.1.4. Positive braids. A braid word is said to be positive if it contains no letter σ -1 i . A braid is said to be positive if it can be represented by at least one positive word. Positive n-braids form a submonoid denoted B + n of the group B n . Garside's theory [START_REF] Garside | The braid group and other groups[END_REF] implies that B + n admits, as a monoid, the presentation (1.1) and that B n is a group of fractions of B + n , i.e., every braid in B n can be expressed as y -1 x with x, y in B + n . For x, y in B + n , we say that x is a left divisor of y, or, equivalently, that y is a right multiple of x, denoted x L y, if y = xz holds for some z in B + n . Right divisors and left multiples are defined symmetrically. With respect to left divisibility (and to right divisibility as well), B + n has the structure of a lattice: any two positive n-braids x, y admit a greatest common left divisor gcd L (x, y), and a least common right multiple. 1.1.5. Permutation of a braid. The geometric interpretation makes it clear that mapping σ i to the transposition that exchanges i and i + 1 induces a surjective homomorphism of the braid group B n onto the symmetric group S n . Under this homomorphism, here denoted π, a braid x is mapped to the permutation f of {1, ..., n} such that the strand that finishes at position i in any braid diagram representing x begins at position f (i).

1.1.6. Simple braids. A special rôle is played by the positive n-braid ∆ n inductively defined by

(1.2) ∆ 1 = 1, ∆ n = σ 1 σ 2 . . . σ n-1 ∆ n-1 .
In B + n , the left and the right divisors of ∆ n coincide, they include each of σ 1 , ..., σ n-1 , and they make a finite sublattice of B + n with n! elements. These divisors of ∆ n are called simple braids. Geometrically, simple braids are those positive braids that can be represented by a braid diagram in which any two strands cross at most once. Moreover, the restriction of the projection π to simple braids is a bijection: for each permutation f in S n , there exists exactly one simple braid s satisfying π(s) = f . This simple braid will be denoted by f . 1.2. The greedy normal form. The seminal results of F.A. Garside [START_REF] Garside | The braid group and other groups[END_REF] subsequently developed in [START_REF] Thurston | Finite state algorithms for the braid group[END_REF][START_REF] Adyan | Fragments of the word Delta in a braid group[END_REF][START_REF] Elrifai | Algorithms for positive braids[END_REF] imply that braid groups can be equipped with a remarkable normal form, the so-called greedy normal form. The latter is excellent both in theory and in practice as it provides a bi-automatic structure, and it is easily computable. 1.2.1. Description. The greedy normal form exists in several variants, in particular left and symmetric right versions. Here we shall consider the left versions only. Again, there exist two different versions. Both consist in expressing an arbitrary braid as a quotient of two positive braids, i.e., as a fraction. In the version considered in this section, all denominators have some special form, namely they are powers of the element ∆ n . By contrast, in the version considered in Section 1.3 below, the numerator and the denominator of fractions play symmetric rôles. Definition 1.2. (i) A sequence of simple braids (s 1 , ..., s p ) is said to be normal if, for each k < p, every σ i that is a left divisor of s k+1 is a right divisor of s k .

(ii) A sequence of permutations (f 1 , ..., f p ) is said to be normal if, for each k < p,

every recoil of f k+1 is a descent of f k , i.e., if f -1 k+1 (i) > f -1 k+1 (i + 1) implies f k (i) > f k (i + 1).
The connection between (i) and (ii) in Definition 1.2 is that, if s is a simple n-braid and f is the associated permutation, then σ i is a left (resp. right) divisor of s if and only if we have f -1 (i) > f -1 (i + 1) (resp. f (i) > f (i + 1)). So a sequence of simple braids (s 1 , ..., s p ) is normal if and only if the associated sequence of permutations (π(s 1 ), ..., π(s p )) is normal.

We denote by ω n the flip permutation of {1, ..., n} defined by ω n (i) = ni + 1.

Theorem (ii) Every braid z in B n admits a unique decomposition of the form ∆ m n f 1 ... f p with m in Z and (f 1 , ..., f p ) a normal sequence of permutations satisfying f 1 = ω n and f p = id.

In the situation of Theorem 1.3(i), the sequence (m; s 1 , ..., s p ) is called the greedy normal form of z-or the n-greedy normal form of z if we wish to insist on the braid index n. As simple braids are in one-to-one correspondence with permutations, and by the remark above, the braid form and the permutation form of the greedy normal form are equivalent. So there is no problem in also calling the sequence (m; f 1 , ..., f p ) of Theorem 1.3(ii) the greedy normal form of z.

Clearly, (0; ∅) is the greedy normal form of 1, and the uniqueness of the greedy normal form implies the following solution to the braid isotopy problem-but a solution that remains uneffective as long as we give no method for computing from an arbitrary braid word w the greedy normal form of w, i.e., until Section 2 below: Corollary 1.4. A braid word w represents 1 in the braid group if and only if the greedy normal form of w is (0; ∅). Two braid words w, w ′ represent the same braid in B n if and only if the greedy normal forms of the braids w and w ′ coincide.

Example 1.5. In order to obtain shorter notation, we shall in the sequel use a, b, c... for σ 1 , σ 2 , σ 3 ..., and, symmetrically, A, B... for σ -1 1 , σ -1 2 ... (as in the caption of Figure 1). Then, a typical greedy normal form for a 4-braid is the sequence (-2; ac, abcb, bcba, a), i.e., equivalently, using (f (1), ..., f (n)) to specify a permutation f of {1, ..., n}, (-2; (2, 1, 4, 3), (2, 4, 3, 1), (4, 1, 3, 2), (2, 1, 3, 4)), consisting of an integer and four simple 4-braids, or, equivalently, four permutations of {1, ..., 4}: for instance, (2, 1, 4, 3) is the permutation associated with ac, i.e., with σ 1 σ 3 . To check that we have a greedy normal form, we observe for instance that the descents of (2, 1, 4, 3) are 1 and 3, while the recoils of (2, 4, 3, 1), i.e., the descents of (4, 1, 2, 3), are 1 and 3 as well, so the normality condition is satisfied between (2, 1, 4, 3) and [START_REF] Anshel | An algebraic method for public-key cryptography[END_REF][START_REF] Bessis | Garside categories, periodic loops and cyclic sets[END_REF][START_REF] Artin | Theory of Braids[END_REF][START_REF] Adyan | Fragments of the word Delta in a braid group[END_REF]. The other verifications are similar. So, the above sequences are two versions of the greedy normal form of the 4-braid represented by ∆ -2 4 .ac.abcb.bcba.a, i.e., by w = ABACBA.ABACBA.ac.abcb.bcba.a. As the above normal form is not (0, ∅), we deduce from Corollary 1.4 that w does not represent 1 in B 4 .

1.2.2. Explanation. The existence and uniqueness of the greedy normal form follows from two results:

(i) For every braid z in B n , there exist m ∈ Z and x ∈ B + n satisfying ∆ m n x = z, the decomposition being unique provided ∆ n L x is required;

(ii) For every positive braid x, there exists a unique normal sequence (s 1 , ..., s p ) of simple n-braids with s p = 1 satisfying s 1 ...s p = x.

The proof of (i) is an easy induction on the length of a braid word representing z once one knows, for each i, the relations σ i L ∆ n and ∆ n σ i = σ n-i ∆ n , which imply that, by multiplying an n-braid by a sufficient large power of ∆ n , one can always obtain a positive braid.

As for (ii), the existence of left gcd's in the monoid B + n implies that each positive n-braid x can be expressed as x = s 1 x ′ with s 1 = gcd L (x, ∆ n ), and x = 1 implies s 1 = 1. By iterating the process, thus writing x ′ = s 2 x ′′ , etc., one eventually obtains a decomposition x = s 1 ...s p . By construction, the sequence (s 1 , ..., s p ) consists of divisors of ∆ n , i.e., of simple n-braids, and, for each k < p, one has

s k = gcd L (s k s k+1 ...s p , ∆ n ), hence, a fortiori, s k = gcd L (s k s k+1 , ∆ n ).
The point is that the latter relations are equivalent to (s k , s k+1 ) being normal for each k, and, therefore, to (s 1 , ..., s p ) being normal. The uniqueness comes from the fact that, if (s 1 , ..., s p ) is a normal sequence, then, necessarily, one has s 1 = gcd L (s 1 ...s p , ∆ n ). 1.2.3. Discussion. What is missing in the above description of the greedy normal form is an algorithm for computing the (unique) normal form of a braid z starting from an arbitrary representative of z. Clearly, the existence of such an algorithm is a necessary condition for using the normal form in practice. Such an algorithm will be provided in Section 2 below, and discussing the practical implementation of the greedy normal form will be possible only then.

Actually, the point is not necessarily to find the normal form equivalent to an arbitrary word, but rather to find the normal form of the product or the quotient of two normal forms. Indeed, whenever one chooses to work with normal forms, one may forget about non-normal words provided one is able to perform the basic operations inside the family of normal forms. Of course, as the generator σ i is itself a braid, with normal form (0; σ i ), an algorithm computing the product of two normal forms will in particular determine the product of a normal form by σ i and, therefore, inductively determine the normal form of any product of σ ±1 i 's, but the general philosophy is not exactly that of a normalizing algorithm.

Note that, while the permutation variant of the greedy normal form is nonambiguously defined, the braid word variant is not: for instance, the first braid factor in Example 1.5, namely ac, is uniquely defined as a simple braid, but it can be represented by two different positive braid words, namely ac and ca. So the braid word form becomes unique only when a distinguished word representative has been chosen for every simple braid. This explains why the permutation form is often more convenient.

1.3. The symmetric normal form. In the greedy normal form where the denominator is always a power of ∆ n . The symmetric normal form is a variant in which the numerator and the denominator play symmetric rôles. 1.3.1. Description. The symmetric normal form appeals to the same notion of a normal sequence of simple braids as the greedy normal form.

Theorem 1.6. [19, Chapter 9] (i) Every braid z admits a unique decomposition as t -1 q ... t -1 1 s 1 ... s p with (s 1 , ..., s p ), (t 1 , ..., t q ) two normal sequences of simple braids satisfying s p = 1, t q = 1, and gcd L (s 1 , t 1 ) = 1.

(ii) Every braid z admits a unique decomposition as g q -1 ... g 1 -1 f 1 ... f p with (f 1 , ..., f p ), (g 1 , ..., g q ) two normal sequences of permutations satisfying f p , g q = id and such that f -1

1 (i) > f -1 1 (i + 1) implies g -1 1 (i) g -1 1 (i + 1
). In the situation of Theorem 1.6(i), the double sequence (t 1 , ..., t q ; s 1 , ..., s p ) is called the symmetric normal form of z. As for the greedy normal form, both versions of the symmetric normal forms are equivalent, and the double sequence of permutations (g 1 , ..., g q ; f 1 , ..., f p ) of Theorem 1.6(ii) is also called the symmetric normal form of z. As (∅; ∅) is the symmetric normal form of 1, the uniqueness of the symmetric normal form provides the following solution to the braid isotopy problem:

Corollary 1.7. A braid word w represents 1 in the braid group if and only if the symmetric normal form of w is (∅; ∅). Two braid words w, w ′ represent the same braid in B n if and only if the symmetric normal forms of w and w ′ coincide.

Example 1.8. A typical symmetric normal form is (ab, bacb; bcba, a), i.e., equivalently, ((2, 3, 1, 4), (3, 4, 1, 2); (4, 1, 3, 2), (2, 1, 3, 4)), For instance, the normality condition between the first factors of the two sequences holds as 1 is the only recoil of (2, 3, 1, 4), while 2 and 3 are those of (4, 1, 3, 2). In other words, the simple braids ab and bcba admit no nontrivial common left divisor. Thus the above expressions specify the symmetric normal form of the braid represented by w = BCAB.BA.bcba.a, which we shall see below coincides with the braid of Example 1.5-and of Figure 1. As the above normal form is not (∅, ∅), we deduce that w does not represent 1 in B 4 .

1.3.2. Explanation. As B n is a group of fractions for the monoid B + n , every element of B n can be expressed as a fraction y -1 x with x, y in B + n , and the decomposition is unique if, in addition, gcd L (x, y) is required. The symmetric normal form is obtained by taking the greedy normal forms of the positive braids x, y so obtained, with the only difference that the ∆ n factors are not separated. The specific properties of normal sequences imply that gcd L (x, y) = 1 is equivalent to gcd L (s 1 , t 1 ) = 1, where s 1 and t 1 respectively are the first factors in the normal forms of x and y.

1.3.3. Discussion. As in Section 1.2, our description will be complete only when we give algorithms for computing the symmetric normal form of a product or of a quotient. This will be done in Section 2.

Grid properties of the normal form

The interest of the greedy and symmetric normal forms of braids lies in the existence of simple computing rules for determining the normal form of a product or of a quotient. Here we shall solve the following two problems, which then easily leads to complete algorithms for all problems connected with the normal forms:

Starting with the greedy normal forms of two positive braids x, y, find the greedy normal form of the product yx and, assuming that y is a right divisor of x, the greedy normal form of the quotient xy -1 . The solutions we shall describe involve grid diagrams that visualize the properties of normal sequences. To this end, it will be convenient to associate with every braid x an arrow labelled x, so that a relation of the form xy = z corresponds to a commutative diagram for the associated arrows. We shall indicate that a sequence (s 1 , ..., s p ) is normal by drawing an arc connecting the final end of each arrow with the initial end of the next one, on the shape of

s 1 s 2 s 3 . . . s p .
2.1. Prerequisites. The only properties of simple braids needed in the forthcoming proofs are summarized in the following lemma, which is standard:

Lemma 2.1. [7] For x in B + n , let α(x) := gcd L (x, ∆ n ).
Then, for all x, y, we have: α(x) L x, and α(x) = x if x is simple, (2.1)

x L y implies α(x) L α(y), (2.2) α(xy) = α(xα(y)). (2.3)
Then the definition of normal sequences immediately rewrites in terms of the function α as follows-and this is the technical form we shall use in the sequel: Lemma 2.2. A sequence of simple braid (s 1 , ..., s p ) is normal if and only if, for each k < p, we have s k = α(s k s k+1 ).

In the sequel, we mostly deal with positive braids. When we say that (s 1 , ..., s p ) is the normal form of a positive n-braid x, we mean that (s 1 , ..., s p ) is normal and that x = s 1 ...s p . Equivalently, this means that the greedy normal form of x is (m; s m+1 , ..., s p ), where m is the number of initial k's such that s k equals ∆ n .

2.2. Grid properties for the quotient. We start with the problem of finding the normal form of xy -1 from those of x and y, where x and y belong to B + n . In principle, the computation makes sense only if y happens to be a right divisor of x. Actually, in any case, the positive braids x, y admit a left lcm in B + n , and what we shall do is to compute the normal form of this left lcm, denoted lcm L (x, y), and of the associated left complements defined as follows:

Definition 2.3. For x, y in B +
n , the unique x ′ in B + n satisfying lcm L (x, y) = x ′ y is called the left complement of x in y, and denoted by x/y.

If y happens to be a right divisor of y, i.e., if y/x = 1 holds, then we have lcm L (x, y) = y, and x/y = xy -1 . Thus an algorithm computing the left complement is in particular an algorithm computing the right quotient when it exists.

A standard observation is that simple braids are closed under left lcm and left complement. Indeed, assume that s, t are simple, and let u = lcm L (s, t) = s ′ t = t ′ s, i.e., s ′ = s/t and t ′ = t/s. Then, s and t are right divisors of ∆ n , hence u is also a right divisor of ∆ n , and it is therefore a simple braid. Then, s ′ and t ′ are simple as well, as every left divisor of a simple braid is a simple braid. Moreover, it is straightforward to check that s ′ t being the left lcm of s and t is equivalent to s ′ and t ′ admitting no common left divisor except 1, i.e., to gcd L (s ′ , t ′ ) = 1. Definition 2.4. A commutative diagram consisting of four simple braids s, t, s ′ , t ′ satisfying s ′ t = t ′ s and gcd L (s ′ , t ′ ) = 1 is called a C-tile (like "complement tile"), and it is represented as in Figure 2. We establish normality conditions for diagrams involving the above C-tiles.

t ′ t s s ′
Lemma 2.5. Proof. With the notation of Figure 3, we compute:

(Figure 3) Assume that s 1 , s 2 , s ′ 1 , s ′ 2 , t 0 , t 1 , t 2 are simple braids satis- fying t 2 s 1 = s ′ 1 t 1 , t 1 s 2 = s ′ 2 t 0 , gcd L (s ′ 2 , t 1 ) =
α(s ′ 1 s ′ 2 ) L α(s ′ 1 s ′ 2 t 0 ) by (2.2) = α(t 2 s 1 s 2 ) by commutativity = α(t 2 α(s 1 s 2 )) by (2.3) = α(t 2 s 1 ) by the hypothesis that (s 1 , s 2 ) is normal = α(s ′ 1 t 1 ) by commutativity L s ′ 1 t 1 by (2.1).
On the other hand, by (2.1) again, we have α(s

′ 1 s ′ 2 ) L s ′ 1 s ′ 2 , hence α(s ′ 1 s ′ 2 ) L gcd L (s ′ 1 s ′ 2 , s ′ 1 t 1 ) = s ′ 1 • gcd L (s ′ 2 , t 1 ) = s ′ 1 , using the hypothesis gcd L (s ′ 2 , t 1 ) = 1. It follows that (s ′ 1 , s ′ 2 ) is normal.
Similarly, we have the following result involving the diagonals of C-tiles, i.e., the left lcm's of the corresponding simple braids.

Lemma 2.6. (Figure 4) Assume that (s 1 , s 2 ) and (t 1 , t 2 ) are normal sequences of simple braids. Let u 1 , u 2 be as in Figure 4. Then (u 1 , u 2 ), (u 1 , s ′

2 ), and (u 1 , t ′ 2 ) are normal as well.

t ′′ 2 t ′ 2 t 2 t ′′ 1 t ′ 1 t 1 s 1 s 2 s ′ 1 s ′ 2 s ′′ 1 s ′′ 2 u 1 u 2 Figure 4.
Another grid property involving C-tiles: assuming that the bottom right rectangle is a C-tile and the bottom and right sequences (s1, s2) and (t1, t2) are normal, the diagonal sequence (u1, u2) is normal as well, and so are the diagonal-then-horizontal sequence (u1, s ′ 2 ) and the diagonal-then-vertical sequence (u1, t ′ 2 ). Proof. With the notation of Figure 4, we compute

s 1 s q-1 s q s q+1 s p s ′ 1 s ′ q-1 s ′ q s ′ q+1 s ′ p t ′ q t ′ q-1 t ′ 1 t q t q-1
α(u 1 u 2 ) = α(t ′′ 2 t ′′ 1 s 1 s 2 ) by commutativity = α(t ′′ 2 t ′′ 1 α(s 1 s 2 )) by (2.3) = α(t ′′ 2 t ′′ 1 s 1 ) by the hypothesis that (s 1 , s 2 ) is normal = α(u 1 t ′ 2 ) by commutativity L u 1 t ′ 2 by (2.1).
Similarly, we obtain α(u 1 u 2 ) L u 1 s ′ 2 , and we deduce α(u

1 u 2 ) L gcd L (u 1 t ′ 2 , u 1 s ′ 2 ) = u 1 • gcd L (s ′ 2 , t ′ 2 ) = u 1 from the hypothesis gcd L (s ′ 2 , t ′ 2 ) = 1. So (u 1 , u 2 ) is normal.
As s ′ 2 is a left divisor of u 2 , the normality of (u 1 , u 2 ) implies that of (u 1 , s ′

2 ), and, similarly, that of (u 2 , t ′ 2 ).

We are ready to establish:

Proposition 2.7. (i) Assume that (s 1 , ..., s p ) and (t 1 , ..., t q ) are normal sequences of simple braids. Let D be the grid diagram obtained by starting from the right column (t 1 , ..., t q ) and the bottom row (s 1 , ..., s p ) and filling the diagram with Ctiles from right to left, and from bottom to top, as shown in Figure 5. Then every path in D consisting of diagonal arrows followed by horizontal arrows, as well as every path consisting of diagonal arrows followed by horizontal arrows corresponds to a normal sequence.

(ii) Let x = s 1 ...s p and y = t 1 ...t q . Let (s ′ 1 , ..., s ′ p ) be the top row of D, let (t ′ 1 , ..., t ′ q ) be its left column, and, assuming p q, let (u 1 , ..., u q ) be the diagonal from the top-left corner. Then (s ′ 1 , ..., s ′ p ) is the normal form of x/y, while (t ′ 1 , ..., t ′ q ) is the normal form of y/x, and (u 1 , ..., u q , s q+1 , ..., s p ) is the normal form of the left lcm of x and y.

Proof. By construction, the diagram D is commutative. Let z = s ′ 1 ...s ′ p t 1 ...t q .
Then z is a common left multiple of x and y. Moreover, an easy induction shows that every common left multiple z ′ of x and y has to be a left multiple of z: indeed, z ′ , being a common left multiple of s p and t q , has to be a left multiple of the braid represented by the diagonal of the bottom-right rectangle in D, and we argue similarly for each of the pq rectangles in D. Hence z is the left lcm of x and y, and, therefore, we have s ′ 1 ...s ′ p = x/y and t ′ 1 ...t ′ q = y/x. Then, by repeatedly applying Lemma 2.5, we obtain that every row and every column in D is a normal sequence. As for the diagonals, and the diagonals followed by rows or columns, we similarly apply Lemma 2.6.

As a straightforward application, we obtain the following computing rule for determining the normal form of xu -1 from that of x.

Corollary 2.8. Assume that (s 1 , ..., s p ) is the normal form of a positive braid x, and that u is a simple braid that divides x on the right. Then the normal form of xu -1 is the sequence (s ′ 1 , ..., s ′ p ) determined by the grid diagram of Figure 6.

s 1 s 2 s p-1 s p u 0 u 1 u p-1 u p u s ′ 1 s ′ 2 s ′ p-1 s ′ p . . . . . . Figure 6
. Normal form of xu -1 from that of x: start from the plain arrows and fill the diagram with C-tiles, from right to left; the expected normal form is the sequence (s ′ 1 , ..., s ′ p ) read on the top line; the hypothesis that u is a right divisor of x guarantees that u0 is 1-without any hypothesis, (s ′ 1 , ..., s ′ p ) is the normal form of x/u, and u0 is then u/x.

2.3.

Grid properties for the product. We turn to the product, with the question of determining the normal form of yx from the normal forms of x and y. The method is similar to that of the previous section, with another type of basic tile. For all simple braids t 1 , t 2 , there exist simple braids s 1 , s 2 satisfying s 1 s 2 = t 1 t 2 and (s 1 , s 2 ) is normal. Indeed, let s 1 = α(t 1 t 2 ), and s 2 satisfying t 1 t 2 = s 1 s 2 . By (2.1), t 1 L t 1 t 2 implies t 1 = α(t 1 ) L α(t 1 t 2 ) = s 1 , so we have t 2 = us 2 for some u, which forces s 2 to be simple. In other words, the normal form of the product of two simple braids must consist of at most two simple braids. Definition 2.9. A commutative diagram consisting of four simple braids s 1 , s 2 , t 1 , t 2 satisfying s 1 s 2 = t 1 t 2 and such that (s 1 , s 2 ) is normal is called a P -tile (like "product tile"), and it is represented as in Figure 7. As was done above with C-tiles, we establish normality results in diagrams involving P -tiles. Proof. (ii) With the notation of Figure 8, we compute:

α(s ′ 1 s ′ 2 ) L α(s ′ 1 s ′ 2 t 2 ) by (2.2) = α(t 0 s 1 s 2 ) by commutativity = α(t 0 α(s 1 s 2 )) by (2.3) = α(t 0 s 1 ) by the hypothesis that (s 1 , s 2 ) is normal = α(s ′ 1 t 1 ) by commutativity = s ′ 1 by the hypothesis that (s ′ 1 , t 1 ) is normal, so (s ′ 1 , s ′ 2
) is normal. To go further, we need to use the duality with respect to ∆ n . For each simple nbraid s, there exists a unique simple n-braid s * satisfying ss * = ∆ n . Then, we have s∆ n = ss * s * * = ∆ n s * * , hence s * * is the conjugate ∆ -1 n s∆ n , which is easily seen to be the image of s under the flip automorphism φ n that exchanges σ i and σ n-i for 1 i < n. Lemma 2.11. Assume that s, t are simple braids. Then (s, t) is normal if and only if gcd L (s * , t) = 1 holds.

Proof. We have

α(st) = gcd L (st, ∆ n ) = gcd L (st, ss * ) = s • gcd L (t, s * ), hence α(st) = s is equivalent to gcd L (t, s * ) = 1.
Lemma 2.12. (Figure 9) Assume that s 0 , s 1 , s We deduce Proposition 2.13. (i) Assume that (s 1 , ..., s p ) and (t 1 , ..., t q ) are normal sequences of simple braids. Let D be the grid diagram obtained by starting from the left column (t 1 , ..., t q ) and the bottom row (s 1 , ..., s p ) and filling the diagram with P -tiles from left to right, and from bottom to top, as shown in Figure 11. Then every path in D consisting of horizontal arrows followed by vertical arrows corresponds to a normal sequence.

(ii) Let x = s 1 ...s p and y = t 1 ...t q . Let (s ′ 1 , ..., s ′ p ) be the top row of D and (t ′ 1 , ..., t ′ q ) is its right column. Then (s ′ 1 , ..., s ′ p , t ′ 1 , ..., t ′ q ) is the normal form of yx.

Proof. By hypothesis, the bottom row is normal, hence, by Lemma 2.10, we inductively deduce that the kth row from the bottom is normal. Similarly, by hypothesis, the left column is normal, hence, by Lemma 2.12, we inductively deduce that kth column from the left is normal. Finally, the sequence (s ′ 1 , ..., s ′ p , t ′ 1 , ..., t ′ q ) is normal, as it is the concatenation of two normal sequences and, moreover, (s ′ p , t ′ 1 ) is normal by construction. As, by construction, the diagram D is commutative, the product of the latter sequence is also the product of the left column and the bottom row, i.e., it is the braid yx.

As in the case of the quotient, we deduce in particular rules for computing the normal form of ux and xu from that of x when u is a simple braid. 12.

t 1 t q-1 t q s 1 s
s ′′ 1 s ′′ 2 s ′′ p-1 s ′′ p s 1 s 2 s p-1 s p s 1 s 2 s p-1 s p s ′ 1 s ′ 2 s ′ p-1 s ′ p . . . . . . . . . . . . u ′′ 0 u ′′ 1 u ′′ p-1 u ′′ p u u u ′ 0 u ′ 1 u ′ p-1 u ′ p
, ..., s ′ p , u ′ p ) (resp. (u ′′ 0 , s ′′ 1 , ..., s ′′ p ))
is the expected normal form-up to removing u ′ p or s ′′ p if the latter happen to be 1.

Application to computing normal forms.

We can now easily provide algorithms that compute the greedy normal form and the symmetric normal form of a braid starting from an arbitrary word that represents it. Clearly, the point is, starting from the greedy (resp. symmetric) normal form of a braid z, to be able to determine the greedy (resp. symmetric) normal form of zu ±1 when u is a simple braid, hence in particular a generator σ i . The solutions come as easy applications of the results of the previous sections. 4)) -this is the symmetric normal form of Example 1.8. As in the case of the greedy normal form, we observe that the steps corresponding to a single simple factor can be gathered. We deduce from Corollary 1.7 that w 0 does not represent 1 in B 4 .

t q t 1 s 1 s p t ′ q t ′ 1 s ′ 1 s ′ p . . . . . . . . . . . . v q v q-1 v 1 v 0 u 0 u 1 u p-1 u p u t q t 2 t 1 s 1 s p t ′ q t ′ 2 v * 0 s ′ 1 s ′ p . . . . .
The complexity analysis is the same as in the case of the greedy normal form: for a fixed braid index n, the algorithm of Proposition 2.17 is quadratic in the length of the initial word; when n is not fixed, a multiplicative factor n log n has to be inserted.

Remark. The diagrams of Figures 13 and 14 make it clear that the greedy and symmetric normal forms satisfy the fellow traveler property of [START_REF] Epstein | Word Processing in Groups[END_REF] and therefore are connected with an automatic structure on the braid group B n .

Also, let us point here that the greedy and symmetric normal forms exist for a class of structures that is much wider than braid groups, namely the so-called Garside groups of [START_REF] Dehornoy | Gaussian groups and Garside groups, two generalizations of Artin groups[END_REF][START_REF] Dehornoy | Groupes de Garside[END_REF], and even more: thin groups of fractions of [START_REF] Dehornoy | Thin groups of fractions[END_REF], Garside categories of [START_REF] Krammer | A class of Garside groupoid structures on the pure braid group[END_REF][START_REF] Digne | Garside and locallly Garside categories[END_REF][START_REF] Bessis | Garside categories, periodic loops and cyclic sets[END_REF]]-all eligible for the grid properties described above.

Finally, we mention the existence of alternative normal forms [START_REF] Burckel | The wellordering on positive braids[END_REF][START_REF] Dehornoy | Alternating normal forms for braids and locally Garside monoids monoids[END_REF] whose computation has the same complexity as the greedy and symmetric normal forms, but which rely on different bases and are connected with the braid order alluded to in Section 3.2 below. So far, there seems to be no reason to expect these normal forms to be more suitable for practical applications than those described above.

Direct solutions

Using a normal form is not the only way for solving the braid isotopy problem. Besides the solutions of Section 1, there exist alternative solutions directly deciding whether a given braid word w represents the trivial braid 1 or not.

Using such solutions entails working with arbitray braid words. As discussed in [START_REF] Dehornoy | Braid-based cryptography[END_REF], this option makes the computation of product and inverse obvious (merely concatenating or reversing words), at the expense of making equivalence not obvious, whereas the option of using a normal form and restricting to normal words makes equivalence obvious (a mere equality), but makes the algebraic operations of product and inverse less obvious, as normalization processes such as those described in Propositions 2.13 and 2.7 are needed.

Here we describe three direct solutions to the braid isotopy problem, namely two syntactic solutions based on some word rewrite systems, and one geometric method due to I. Dynnikov which consists in attributing integral coordinates to every braid.

3.1. Word redressing. Word redressing (also called reversing in literature) is a simple syntactic transformation that consists in pushing the positive letters σ i in one direction and the negative letters σ -1 i in the other direction, until a word of the form "all positive, then all negative" is obtained. This leads to solutions of the word problem that admit a quadratic complexity. The underlying theory is Garside theory again.

3.1.1. Description. Redressing a braid word consists in looking for the subwords of the form σ -1 i σ j , i.e., one negative letter followed by a positive letter, and transforming them into equivalent patterns consisting of positive letters followed by negative letters, i.e., replacing negative-positive subwords with equivalent positive-negative words.

Definition 3.1. [START_REF] Dehornoy | Groups with a complemented presentation[END_REF][START_REF] Dehornoy | Complete positive group presentations[END_REF] Assume that w, w ′ are braid words. We say that w is right redressible to w ′ in one step if w ′ is obtained from w either by deleting some subword of the form σ -1 i σ i , or by replacing some subword of the form σ -1 i σ j with |i -j| 2 by σ j σ -1 i , or by replacing some subword of the form σ -1 i σ j with |i -j| = 1 by σ j σ i σ -1 j σ -1 i . We say that w w ′ holds if there is a finite sequence w 0 = w, ..., w N = w ′ such that w k is right redressible to w k+1 in one step for each k.

By construction, the words that are terminal for redressing are the words that include no subword of the form σ -1 i σ j , i.e., the words of the form w ′ w ′′-1 with w ′ , w ′′ positive braid words. Theorem 3.2. [START_REF] Dehornoy | Groups with a complemented presentation[END_REF] For each braid word w, there exist two unique positive braid words w ′ , w ′′ such that w w ′ w ′′-1 holds.

A new solution to the braid isotopy problem follows:

Corollary 3.3. A braid word w represents 1 in the braid group if and only if, denoting by w ′ and w ′′ the positive words for which w w ′ w ′′-1 holds, we have w ′′-1 w ′ ε, where ε denotes the empty word.

Example 3.4. Let us start again with the braid word w 0 = aBabacABABAbbCB of Examples 2.16 and 2.18. Owing to Corollary 3.3, we decide whether w is trivial or not by redressing w to a word of the form w ′ w ′′-1 with w ′ , w ′′ positive words, then redressing w ′′-1 w ′ again, and looking whether we finally obtain the empty word.

In the current case, selecting at each step the leftmost pattern of the form σ -1 i σ j (underlined in the words below), the successive words are as follows 0 : aBabacABABAbbCB 1 : aabABbacABABAbbCB 2 : aabAacABABAbbCB 3 : aabcABABAbbCB 4 : aabcABABbaBAbCB . . . 11 : aabcbABBACB. At this point, we switch the positive and negative subword, and redress again:

12 : ABBACBaabcb 13 : ABBACabABabcb 14 : ABBAaCbABabcb . . . 37 : cbaaBbcBCABBA. 38 : cbaacBCABBA. The latter word is not empty: we conclude that w 0 does not represent 1 in B 4 .

3.1.2. Explanation. Clearly, redressing replaces a braid word with an equivalent braid word, and it is easy to show that, if w redresses to a word of the form w ′ w ′′-1 with w ′ , w ′′ positive, then w ′ and w ′′ are uniquely determined. Now the problem is that, as Example 3.4 shows, redressing may increase the length of the words, and it is not obvious that the process terminates. The point is that, if w has the form w -1 1 w 2 where w 1 , w 2 are positive words representing simple braids, then w redresses to some word w ′ w ′′-1 where w ′ and w ′′ are positive and again represent simple braids. Thus, with respect to an enhanced alphabet containing all positive braid words representing simple braids, the length does not increase under redressing, and this leads to the termination result. Actually, what redressing does is to compute the right lcm in the braid monoid, and so the properties behing redressing are the Garside theory.

3.1.3. Discussion. The advantage of the redressing method is the simplicity of its implementation: there is a unique syntactic operation, involving length 2 subwords of the considered word only. From that point of view, the method is more easily implemented than the greedy or symmetric normal form. At a theoretical level, both methods are essentially equivalent: there exist positive constants C, C ′ such that, for each n-braid word w, if N 1 (w) (resp. N 2 (w)) denotes the number of braid relations needed to put w into a greedy normal form (resp. to redress w), then we have CN 1 (w) N 2 (w) C ′ N 1 (w). However, by representing simple braids by permutations and using fast sorting algorithms to compute the normal form as explained in [START_REF] Epstein | Word Processing in Groups[END_REF]Chapter 9], one presumably obtains a more efficient algorithm.

According to Theorem 3.2, the redressing method starting from a braid word w yields a final braid word w ′ such that w ≡ ε is equivalent to w ′ = ε. However, in general, w ′ ≡ w fails: because of the exchange of the negative and positive factors between the two passes, w ′ is only equivalent to a conjugate of w. Now, it is easy to describe a variant of the redressing method that avoids the median conjugation. Indeed, let left redressing, denoted w w ′ , be the symmetric counterpart to (right) redressing consisting in replacing each pattern σ i σ -1 j with an equivalent negativepositive word. Formally, we may define w w ′ to mean w w ′ , where w is the word obtained from w by reversing the order of the letters.

Corollary 3.5. [8]

A braid word w represents 1 in the braid group if and only if, denoting by w ′ and w ′′ the positive words for which w w ′ w ′′-1 holds, we have w ′ w ′′-1 ε.

So the method is the same as in Corollary 3.3, with the only difference that we do not change the word obtained at the end the first redressing pass, but instead continue with left redressing. The criterion remains the same, namely that the initial word w is trivial if and only if the final word w ′′ is empty. The advantage of this variant is that w ′′ is equivalent to w, and, moreover, it gives a fractionary decomposition of w which is geodesic, i.e., has minimal length among all fractionary expressions of w. This implies that the negative and the positive parts of w ′′ must be equivalent to the two components of the symmetric normal form of w, although they need not be in normal form in general. Assuming that an algorithm for computing the normal form of a positive braid is available, one obtains in this way an alternative way for computing the symmetric normal form of an arbitrary braid that is more simply implemented than the method of Proposition 2.17: perform double redressing, then put the numerator and the denominator in normal form.

Example 3.6. Starting with aBabacABABAbbCB once more, the first 11 steps of the redressing algorithm are as in Example 3.4, but, then, we appeal to left redressing, and the sequel is different. We find: 0 : aBabacABABAbbCB . . . 11 : aabcbABBACB 12 : aabcABabBBACB 13 : aabAcBabBBACB 14 : aaABabcBabBBACB . . . 39 : BACBBAcbaacbB. 40 : BACBBAcbaac. Once again, the latter word is not empty, and we conclude that w 0 does not represent 1 in B 4 . In addition, we obtain that BACBBAcbaac is a shortest expression of w 0 as a negative-positive fraction, which is coherent with Example 1.8, where it was shows that the symmetric normal form of w 0 is (ab, bacb, bcba, a): indeed, (ab, bacb) is the normal form of abbcab, and (bcba, a) is the normal form of cbaac.

As a final remark, let us observe that, because redressing is efficient at computing lcm's and complements in the braid monoid, it also provides an easy way to compute gcd's and, from there, normal forms. Though not as efficient as those based on quick sorting, the algorithms based on word redressing are more easily implemented than the latter, and they are convenient for small and medium size braid words.

Handle reduction.

Handle reduction is another syntactic braid word transformation which, like redressing, consists in iterating some basic word transformation and concluding that the initial braid word represents 1 if and only if the final word is empty. The basic transformation step is more complicated that the one involved in redressing but the number of steps is much lower, and the method turns out to be extremaly efficient in practice. The underlying structure behind handle reduction is a linear ordering of braids, which pilots the reduction process and heuristically explains its efficiency. w ′ = w 0 σ -e i+1 σ d i σ e i+1 w 1 σ -e i+1 σ d i σ e i+1 . . . σ -e i+1 σ d i σ e i+1 w m , i.e., we delete the initial and final letters σ ±1 i , and we replace each letter σ ±1 i+1 with σ -e i+1 σ ±1 i σ e i+1 . (ii) We say that a braid word w is reduced if it contains no σ i -handle, where σ i is the generator with minimal index occurring in w.

Figure 15. Reduction of a handle, here a σ 1 -handle: the dashed strand has the shape of a handle, and reduction consists in pushing that strand so that it skirts above the next crossings instead of below.

A braid word of the form σ i σ -1 i or σ -1 i σ i is a handle, and reducing it means deleting it, so handle reduction generalizes free reduction. As illustrated in Figure 15, reducing a handle yields an equivalent braid word. So, as in the case of free reduction, if there is a reduction sequence from a braid word w to the empty word, i.e., a sequence w = w 0 , ..., w N = ε such that, for each k, the word w k+1 is obtained from w k by replacing some handle of w k by its reduct, then w represents 1 in the braid group. The point is that the converse is also true. Theorem 3.8. [START_REF] Dehornoy | A fast method for comparing braids[END_REF] For every braid word w, every sequence of handle reductions from w leads in finitely many steps to a reduced word w ′ . Moreover, a reduced word w ′ represents 1 if and only if it is empty.

We obtain a new solution to the braid isotopy problem: Corollary 3.9. A braid word w represents 1 in the braid group if and only if any sequence of handle reductions starting from w terminates with the empty word.

Example 3.10. Consider w 0 = aBabacABABAbbCB again. Choosing to reduce the leftmost handle at each step and underlying it, we succesively obtain: 0 : aBabacABABAbbCB 1 : aBabcBABAbbCB 2 : aBaCbcABAbbCB 3 : aBCBabcBAbbCB 4 : aBCBaCbcAbbCB 5 : aBCBCBabcbbCB. The latter word contains no σ 1 -handle, so it is reduced, and it is not empty, so we conclude that w 0 does not represent 1 in B 4 .

3.2.2. Explanation. Two different structures lie behind handle reduction, namely Garside's theory that was already involved on the previous solutions, and, in addition, some linear order that is compatible with left multiplication on B n . It can be seen that each handle reduction is essentially a composition of redressing steps, but the main difference with the algorithms of Sections 1 and 3.1 is that, here, we do not perform all redressing steps systematically, but only some of them according to a general strategy provided by the underlying braid order. This should make it natural why the handle reduction method is, in practice, much more efficient than the redressing method and than the greedy and symmetric normal form methods (5 vs. 40 steps in our example).

3.2.3.

Discussion. A braid word may contain many handles, so building an actual algorithm requires to fix a strategy prescribing in which order the handles will be reduced. In Example 3.10, we chose to reduce the leftmost handle, but more efficient strategies exist. As can be expected, the most efficient ones use a divide-andconquer trick. Although the only upper bound for space and time complexity proved so far is exponential, handle reduction is extremely efficient in practice, as show the statistics of [START_REF] Dehornoy | Braid-based cryptography[END_REF]. Also, reduction being a local procedure, the amount of memory needed to implement it is what is needed to just store the braid under reduction. So, using arbitrary words together with handle reduction instead of normal words could be specially interesting when the computing resources are limited.

It was mentioned above that the symmetric normal form, as well as the redressing method, yield fractionary expressions of minimal length. Such fractionary expressions need not be expressions of minimal length: there may be shorter expressions that are not fractions, i.e., in which all negative letters are not gathered in one block and all positive letters in another block. The general problem of finding the shortest expression of a braid is difficult: its B ∞ version is known to be N P -complete [START_REF] Paterson | The set of minimal braids is co-NP-complete[END_REF]. Although no actual result is proved, it has been observed that handle reduction is good at providing short expressions. Actually, the definition of handle reduction is not symmetric and the left side plays a distinguished rôle. One can compensate this lack of symmetry by defining iterated handle reduction as follows: starting with w, we reduce w to w ′ , then flip w ′ using φ n , reduce it, and flip the result. Equivalently, after one handle reduction, one performs the symmetric operation in which the right side is distinguished. By doing so, and possibly iterating the process, one empirically obtains short expressions. It is conjectured by the author, as well as by A. Miasnikov and A. Ushakov, that there might exist a constant C such that applying the previous process to any braid word w leads to a final word of length at most Cℓ min (w), where, for x a braid, ℓ min (x) denotes the length of the shortest word x.

Example 3.11. Starting once more with w 0 = aBabacABABAbbCB, iterated handle reduction from w 0 leads in 3 steps to the word acBCCBa, which happens to be a geodesic representative of the braid w 0 .

3.3. Dynnikov coordinates. We conclude with still another solution to the braid isotopy problem, namely the one provided by the so-called Dynnikov coordinates. This solution relies on a completely different approach steming from geometry and deep results by L. Mosher about the existence of an automatic structure for all mapping class groups [START_REF] Mosher | Mapping class groups are automatic[END_REF].

3.3.1. Description. The principle consists in associating with every n-braid word a sequence of 2n integers, that can be thought of as coordinates for the braid. This coordinization is faithful in that two braid words receive the same coordinates if and only if they represent the same braid.

3.3.2. Explanation. At first, the formulae (3.3) seem quite mysterious. Actually, there is no miracle here, but a very clever use of the simple formula (3.4) x + x ′ = max(x 1 + x 3 , x 2 + x 4 )

that compares the number of intersections of a family of curves with two triangulations obtained one from the other by switching one diagonal in a quadrilateral (flip transformation). The framework consists in considering an n-braid as the isotopy class of a homeomorphism of a disk with n punctures: then the generator σ i corresponds to the homeomorphism that exchanges the ith and (i + 1)st punctures by a half-turn. Dynnikov's idea is to let the braid act on a family of curves in the punctured disk, and to count their intersections with a fixed triangulation, or, equivalently, to let the braid act on the triangulation and count its intersections with a fixed family of curves. The action of σ i on the chosen triangulation can then be decomposed into the composition of four flips, and applying (3.4) repeatedly leads to the mysterious formulae (3.3).

3.3.3. Discussion. The remarkable point about the Dynnikov coordinates is that they involve the semiring (Z, max, +, 0), which explains their efficiency. Multiplying by one generator σ i can only increase the size of the coordinates by one unit, whereas similar formulae in the ring (Z, +, ×, 1) would double the size in the worst case. It follows that the solution to the braid word problem given by Theorem 3.13 has a linear space complexity, and a quadratic time complexity.

It is not so easy to compare the solution based on the Dynnikov coordinates with the other solutions to the braid isotopy problem, because its practical efficiency much depends on the way large integer arithmetic is implemented-large integers do appear when long braid words are considered, typically length O(ℓ) binary integers for a length ℓ braid word representing a pseudo-Anosov braid. However, the only arithmetic operations involved are addition and maximum, and both can be implemented very efficiently and easily. No statistical study has been completed so far, and it would be desirable to compare Dynnikov's method with handle reduction. The only weak point of the former is that, at the moment, it is purely incremental: the only available formulae correspond to multiplying by one single letter σ i or σ -1 i , so, in particular, no divide-and-conquer variant exists.

Figure 2 .

 2 Figure 2. A C-tile: a commutative diagram involving four simple braids such that the two initial ones have no nontrivial common left divisor-here indicated by a perpendicularity sign.

Figure 5 .

 5 Figure 5. Construction of the left lcm and the left complements by the grid method: we start from the bottom and right sides, and fill the grid with C-tiles, from right to left and from bottom to top; then every row, every column, and every diagonal in the grid consist of normal sequences.

t 1 s 2 t 2 s 1 Figure 7 .

 217 Figure 7. A P -tile: a commutative diagram involving four simple braids such that two of them make a normal sequence.

Figure 12 .

 12 Figure 12. Construction of the normal from of ux (above) and xu (below) from the normal form (s1, ..., sp) of x: start with u ′ 0 := u (resp. with u ′′ p := u) and fill the diagram with P -tiles from left to right (resp. from right to left); then (s ′ 1, ..., s ′ p , u ′ p ) (resp. (u ′′ 0 , s ′′ 1 , ..., s ′′ p ))is the expected normal form-up to removing u ′ p or s ′′ p if the latter happen to be 1.

3. 2 . 1 . 1 i 1 iDefinition 3 . 7 .

 211137 Description. Handle reduction is an extension of free reduction. The latter consists in iteratively deleting patterns of the form xx -1 or x -1 x. Handle reduction involves not only patterns of the form σ i σ -or σ -1 i σ i , but also more general patterns of the form σ i . . . σ -or σ -1 i . . . σ i with intermediate letters between the letters σ i and σ -1 i . (i) A σ i -handle is a braid word of the form(3.1) w = σ e i w 0 σ d i+1 w 1 σ d i+1 . . . σ d i+1 w m σ -e i ,with e, d = ±1, m 0, and w 0 , ..., w m containing no σ ±1 j with j i + 1. Then the reduct of w is defined to be(3.2)

  1.3. [19, Chapter 9] (i) Every braid z in B n admits a unique decomposition of the form ∆ m n s 1 ...s p with m in Z and (s 1 , ..., s p ) a normal sequence of simple braids satisfying s 1 = ∆ n and s p = 1.

  1, and that (s 1 , s 2 ) is normal. Then Figure 3. A grid property involving C-tiles: assuming that the right rectangle is a C-tile and the bottom sequence (s1, s2) is normal, the top sequence (s ′ 1 , s ′ 2 ) is normal as well.

	s ′ 1	s ′ 2
	t 2	t 1	t 0
	s 1	s 2
	(s ′ 1 , s ′ 2 ) is normal as well.

  Lemma 2.10. (Figure8) Assume that s 1 , s 2 , s ′ 1 , s ′ 2 , t 0 , t 1 , t 2 be simple braids satisfying t 0 s 1 = s ′ 1 t 1 , t 1 s 2 = s ′ 2 t 2 , and such that (s 1 , s 2 ) and (s ′

			1 , t 1 ) are normal. Then
	(s ′ 1 , s ′ 2 ) is normal as well.
	s ′ 1	s ′ 2
	t 0	t 1	t 2
	s 1	s 2
	Figure 8. A grid property involving P -tiles: assuming that the left rec-
	tangle is a P -tile and the bottom sequence (s1, s2) is normal, the top
	sequence (s ′ 1 , s ′ 2 ) is normal as well.

  2 , t 1 , t 2 , t ′ 1 , t ′ 2 are simple braids satisfying t 1 s 1 = s 0 t ′ 1 , t 2 s 2 = s 1 t ′ 2 ,and such that (t 1 , t 2 ) and (s 1 , t ′

		s 0
	t 1	t ′ 1
		s 1
	t 2	t ′ 2
		s 2
	Figure 9. Another grid property involving P -tiles: assuming that the
	bottom rectangle is a P -tile and the left sequence (t1, t2) is normal, the
	right sequence (t ′ 1 , t ′ 2 ) is normal as well.
	s 0	s * 0
	t 1	t ′ 1	φ
	s 1	s * 1
	t 2	t ′ 2
	s 2	s * 2
			2 ) are normal. Then
	(t ′ 1 , t ′ 2 ) is normal as well.
	Proof. Introduce s * 0 , s * 1 and s * 2 . Then the diagram of Figure 10 is commutative.
	As φ n is an automorphism of B + n -and of the group B n too-the hypothesis that
	(t 1 , t 2 ) is normal implies that (φ n (t 1 ), φ n (t 2 )) is normal as well.
	Now, by Lemma 2.11, the hypothesis that (s 1 , t ′ 2 ) is normal gives gcd L (s * 1 , t ′ 2 ) = 1.
	By Lemma 2.5, the latter condition together with the normality of (φ n (t 1 ), φ n (t 2 ))
	implies that (t ′ 1 , t ′ 2 ) is normal.

n (t 1 )

φ n (t 2 )

Figure

10

. Proof of Lemma 2.12: one introduces the dual of the horizontal arrows; the hypothesis that the left column (t1, t2) is normal implies that the right column (φn(t1), φn(t2)) is normal as well, and, then, we apply Lemma 2.5 to come back to (t ′ 1 , t ′ 2 ).

  Computation of the normal form of a product by means of a grid: we start from the left and the bottom sides, and fill the diagram using P -tiles, from left to right and from bottom to top; then the top row and the right column are normal sequences as well, and so is the sequence obtained by concatenating them.

	s ′ 1	s ′ 2		. . .	s ′ p
						t ′ 1
				. . .
	. . .	. . .	. . .	. . .	. . .	. . .
						t ′ q-1
				. . .
						t ′ q
		2		. . .	s p
	Figure 11.

Corollary 2.14. Assume that (s 1 , ..., s p ) is the normal form of the positive braid x, and that u is a simple braid. Then the normal forms of ux and xu are the sequences (s ′ 1 , ..., s ′ p , u ′ p ) and (u ′′ 0 , s ′′ 1 , ..., s ′′ p ) determined by the grid diagrams of Figure

.

  Example 2.18. Let w 0 be the braid word aBabacABABAbbCB again. Applying the algorithm of Proposition 2.17 to the successive letters of w leads to the symmetric

	normal forms (here in braid word form):
	0 : ε	(∅; ∅)
	1 : a	(∅; a)
	2 : aB	(ab; ba)
	3 : aBa	(ab; ba, a)
	4 : aBab	(ab; ba, ab)
	5 : aBaba	(∅; a, ab)
	6 : aBabac	(∅; a, abc)
	. . .
	14 : aBabacABABAbbC (ab, bacb; bcba, ab)
	15 : aBabacABABAbbCB (ab, bacb; bcba, a).
	Thus the symmetric normal form of the braid represented by w 0 is the double
	sequence (ab, bacb; bcba, a), i.e., in permutation form,
	((2, 3, 1, 4), (3, 4, 1, 2); (4, 1, 3, 2), (2, 1, 3,

2.4.1.

Computing the greedy normal form. We recall that, for s a simple n-braid, s * denotes the unique (simple) braid satisfying ss * = ∆ n . Symmetrically, we denote by * s the unique (simple) braid satisfying * ss = ∆ n . Note that, by construction, ( * s) * = s holds for each simple braid s.

Proposition 2.15. Assume that the n-greedy normal form of z is (m; s 1 , ..., s p ) and u is a simple n-braid.

(i) Let s ′ p , u p-1 , ..., s ′ 1 , u 0 be determined by filling the top diagram of Figure 13. Then the greedy normal form of zu is (m + 1; s ′ 1 , ..., s ′ p ) if u 0 = ∆ n holds, and (m; u 0 , s ′ 1 , ..., s ′ p ) otherwise. (ii) Let s ′ p , u p-1 , ..., s ′ 1 , u 0 be determined by filling the bottom diagram of Figure 13. Then the greedy normal form of zu -1 is (m; s ′ 1 , ..., s ′ p ) if u 0 = 1 holds, and (m -1; * u 0 , s ′ 1 , ..., s ′ p ) otherwise. Proof. (i) By commutativity of the diagram, we have zu = ∆ m n u 0 s ′ 1 ...s ′ p , so the point is to check that the sequence (m; u 0 , s ′ 1 , ..., s ′ p ), or (m+ 1; s ′ 1 , ..., s ′ p ), is normal. Now Corollary 2.14 guarantees that (u 0 , s ′ 1 , ..., s ′ p ) is normal. According to whether u 0 equals ∆ n or not, we integrate the factor u 0 in ∆ m n , and we obtain a greedy normal form, hence the greedy normal form of zu by uniqueness.

(ii) By commutativity, we have zu ) is a greedy normal form, hence it is the greedy normal form of zu -1 ; otherwise, we observe that (m -1; * u 0 , s ′ 1 , ..., s ′ p ) is a greedy normal form, as u 0 = 1 implies * u 0 = ∆ n , and, by Lemma 2.11, the hypothesis gcd L (u 0 , s ′ 1 ) = 1 is equivalent to ( * u 0 , s ′ 1 ) being normal since u 0 = ( * u 0 ) * holds.

Example 2.16. Let w 0 be the braid word aBabacABABAbbCB-the randomly chosen 4-braid word illustrated in Figure 1, which will be repeatedly considered in the sequel. Starting with (0; ∅), which is the greedy normal form of 1, and applying the algorithm of Proposition 2.15 to the successive letters of w, we obtain the 4-greedy normal form of the prefixes of w, namely (in braid words form): 0 : ε (0; ∅) 1 : a (0; a) 2 : aB (-1; abcb, ba) 3 : aBa (-1; abcb, ba, a) 4 : aBab (-1; abcb, ba, ab) 5 : aBaba (0; a, ab) 6 : aBabac (0; a, abc) . . . 14 : aBabacABABAbbC (-2; ac, abcb, bcba, ab) 15 : aBabacABABAbbCB (-2; ac, abcb, bcba, a). Thus the greedy normal form of the braid represented by w is the sequence (-2; ac, abcb, bcba, a), i.e., in permutation form, (-2; (2, 1, 4, 3), (2, 4, 3, 1), (4, 1, 3, 2), (2, 1, 3, 4)) -this is the greedy normal form of Example 1.5. As the initial word w 0 contains 15 letters, computing its greedy normal form entails 15 applications of Proposition 2.15. However, one can speed up the process by gathering adjacent letters that together represent a simple braid: for instance, abac represents a simple braid, so steps 3 to 6 above can be gathered into a single step corresponding to multiplying by the simple braid abac. By Corollary 1.4, we deduce that the braid word w 0 does not represent 1 in B 4 .

As for complexity analysis, two cases are to be considered. If the braid index n is fixed, and, for practical implementations, has a small value, say n 6, then one can precompute the tables of the binary operations (s, t) → α(st), (s, t) → α(st) -1 st, and (s, t) → gcd L (s, t), in which case the determination of the greedy normal form for a braid word of length ℓ has complexity O(ℓ 2 ), and is easy and quick in practice. Otherwise, there are too many simple n-braids to store all results, and one has to compute the values of α(st) and gcd L (s, t) locally. As explained in [START_REF] Epstein | Word Processing in Groups[END_REF]Chapter 9], this is essentially a sorting process, and, therefore, each such computation can be done in time O(n log n), resulting in a global time complexity O(ℓ 2 n log n) for the computation of the normal form for an n-braid word of length ℓ.

2.4.2.

Computing the symmetric normal form. We now consider the symmetric normal form of Section 1.3, and show how to compute the symmetric normal form of zu and zu -1 form that of z by using convenient grid diagrams. The method is similar to that for the greedy normal, but a bit more care is needed for the transition between the numerator and the denominator in the case of a product. Proposition 2.17. Assume that the symmetric normal form of z is the double sequence (t 1 , ..., t q ; s 1 , ..., s p ), and u is a simple braid.

.. , t ′ q , v q be determined by filling the top diagram of Figure 14. Then the symmetric normal form of zu is

.. , t ′ q , v q are determined by filling the bottom diagram of Figure 14. Then the symmetric normal form of zu -1 is (t ′ 1 , ..., t ′ q , v q ; s ′ 1 , ..., s ′ p ) , . . .

. Symmetric normal form of zu (top) and zu -1 (bottom) from the symmetric normal form (t1, ..., tq; s1, ..., sp) of z: start from up := u, and fill the diagram from right to left using P -tiles (resp. C-tiles, then Ptiles); in the case of the product, the transition is as follows: having got u0, we find * u0 using a C-tile, then let (v0, v1) be the normal form of * u0t1 using a P -tile, and continue with v1, t2, etc..; in the case of the quotient, we simply put v0 := u0, and continue with v0, t1, etc.

Proof. (i) By commutativity of the diagram, we have zu

..s ′ p , and the point is to show that the double sequence (t ′ 2 , ..., t ′ q , v q ; v * 0 , s ′ 1 , .., s ′ p ) is a symmetric normal form. Corollary 2.14 guarantees that the sequences (u 0 , s ′ 1 , ..., s ′ p ) and (v 0 , t ′ 2 , ..., t ′ q , v q ) are normal. There remain two points to check, namely that gcd L (t ′ 2 , v * 0 ) is 1, and that (v * 0 , s ′ 1 ) is normal. For the first relation, Lemma 2.10 implies that (v 0 , t ′ 2 ) is normal, which is equivalent to gcd L (t ′ 2 , v * 0 ) = 1 by Lemma 2.11. As for the second relation, i.e., for the normality of (v * 0 , s ′ 1 ), by Lemma 2.11 again, it is equivalent to gcd L (v * * 0 , s ′ 1 ) = 1, hence to gcd L (v 0 , φ -1 n (s ′ 1 )) = 1. Now we have v 0 v 1 = * u 0 t 1 , and

Assume s is a simple left divisor of v 0 and φ -1 n (s ′ 1 ). Then, a fortiori, we have s L v 0 v 1 and s L φ -1 n (s ′ 1 ) * u 1 , hence, by the above computations, s L * u 0 t 1 and s L * u 0 s 1 , and, therefore, s L * u 0 as, by hypothesis, gcd L (s 1 , t 1 ) = 1 holds. Now, by hypothesis, (u 0 , s ′ 1 ) is normal, hence, by Lemma 2.11, we have gcd L (u * 0 , s ′ 1 ) = 1, and therefore gcd

)) = 1, which was seen above to be equivalent to (v * 0 , s ′ 1 ) being normal. So the proof is complete.

(ii) The argument for the quotient is similar. By commutativity of the diagram, we have zu

..s ′ p , and, once again, the point is to check that the double sequence (t ′ 1 , ..., t ′ q , v q ; s ′ 1 , ..., s ′ p ) is a symmetric normal form. Corollary 2.8 implies that (s ′ 1 , ..., s ′ p ) is normal, and Corollary 2.14 implies that (t ′ 1 , ..., t ′ q , v q ) is normal, so the only remaining point to check is gcd L (s ′ 1 , t ′ 1 ) = 1. Now assume that s is a simple left divisor of s ′ 1 and t ′ 1 . Then, a fortiori, we have s L s ′ 1 u 1 = u 0 s 1 and

As gcd L (s 1 , t 1 ) = 1 holds by hypothesis, we deduce s L u 0 , and, finally, s = 1 as, by construction, we have gcd L (u 0 , s ′ 1 ) = 1. Hence gcd L (s ′ 1 , t ′ 1 ) = 1 holds. Definition 3.12. (i) For x in Z, write x + for max(0, x), and x -for min(x, 0). Let F, F : Z 4 → Z 4 be defined by F = (F 1 , ..., F 4 ), F = (F 1 , ..., F 4 ) with

where we put z

Then, for w an n-braid word, we recursively define

The Dynnikov coordinates of w are defined to be the sequence (0, 1, 0, 1, ..., 0, 1) • w. We deduce still another solution to the braid isotopy problem:

Corollary 3.14. An n-strand braid word represents 1 in B n if and only if its Dynnikov coordinates are (0, 1, 0, 1, ..., 0, 1).

Example 3.15. Consider w 0 = aBabacABABAbbCB once more. By applying the formulae of (3.3) inductively, we compute the Dynnikov coordinates of the successive prefixes of w 0 : 0 : ε (0, 1, 0, 1, 0, 1, 0, 1) 1 : a (1, 0, 0, 2, 0, 1, 0, 1) 2 : aB (1, 0, -2, 0, 0, 3, 0, 1) 3 : aBa (1, -3, -2, 3, 0, 3, 0, 1) 4 : aBab (1, -3, 3, 2, 0, 4, 0, 1) 5 : aBaba

(1, -1, 3, 0, 0, 4, 0, 1) . . . 14 : aBabacABABAbbC (1, -7, 5, -1, -7, 4, 0, 8) 15 : aBabacABABAbbCB (1, -7, -6, 4, 1, -1, 0, 8). The latter coordinates are not (0, 1, 0, 1, 0, 1, 0, 1), so we conclude that w 0 does not represent 1 in B 4 .