Word problem for braid group using a representation

Problem1The word problem for braid groups

Input: $w$ is a word of length $l$ from the presentation $⟨ σ_{1}, σ_{2}, \dots, σ_{n - 1} ∣ σ_{i + 1} σ_{i} σ_{i + 1} = σ_{i} σ_{i + 1} σ_{i}, σ_{i} σ_{j} = σ_{j} σ_{i} ⟩$ where $∣ i - j ∣ \neq = 1$ .

Output: Return true if $w$ is the identity, else return false.

The word problem for braid group was solved a long time ago with Artin combing. It requires one to express pure braid group $P_{n}$ as a semidirect product of free groups $F_{1}, \dots, F_{n - 1}$ . It is slow and quite difficult, at least I wasn’t able to come up with an explicit algorithm for it.

Another way was to create a faithful homomorphism $^{*} : B_{n} \to Aut (F_{n})$ . This is what I implemented in Haskell.

If $B_{n} \to Aut (F_{n})$ is faithful and it sends $w$ to $w^{*}$ , then $w$ is $I$ iff $w^{*} (a) = a$ for every generator $a$ of $F_{n}$ .

In the a survey by Jonathan Boiser, there is one explicate map. Defined as $σ_{i}^{*} (t_{j}) = ⎩ ⎨ ⎧ t_{j} t_{i + 1} t_{i + 1} t_{i} t_{i + 1}^{- 1} if j \neq = i, i + 1 if j = i if j = i + 1$

Where $t_{i}$ are generators of $F_{n}$ , and $σ_{i}$ are the generators of the braid group. The inverse can easily be found.

Using a recursive definition. Let any word of the form $(σ_{i} w)^{*}$ be $σ_{i}^{*} \circ w^{*}$ . The algorithm is obvious. Test if $w^{*} (t_{i}) = t_{i}$ for every generator in $F_{n}$ is applying a list of $σ_{i}$ to elements in $F_{n}$ .

I wrote the program in Haskell, and posted it on github.

The analysis: Given a word with length $l$ in $B_{n}$ , how long does it take to solve the problem with this algorithm? Each application of $σ_{i}^{*} (u)$ to some word $u$ takes $O (∣ u ∣)$ time. One then free reduce. $σ_{i}$ is applied $l$ times.

An application of $σ_{i}^{*}$ can potentially triple the length of the word. If one shows that it can only increase the length of the word by a constant term(given one started from a generator), then we have a $O (l^{2} n)$ algorithm.

Braid groups are automatic. If this natural algorithm solves the problem in $O (l^{2} n)$ time, it is not a surprise. However, it is likely not true. The running time is more likely to be $O (c^{l} n)$ for some constant $c$ . Although I can prove neither $σ_{i}^{*}$ and increase the length by a constant factor or by a constant. The best known algorithm in 2000 was provided by a paper of Hessam Hamidi-Tehrani. It runs in $O (l^{2} n + l n lo g n)$ time, and was proved with advanced techniques.

Update 06/24/2011: Siegel provided a example in $B_{3}$ where the algorithm run in exponential time. $((σ_{2} σ_{1}^{- 1})^{n})^{*} (t_{1})$ .

If we define $a_{n}, b_{n}, c_{n}$ to be the amount of $t_{1}, t_{2}, t_{3}$ (include it’s inverses) at step $n$ , ignoring the possibility of cancellation. We have the following recurrence relation.

$a_{n + 1} b_{n + 1} c_{n + 1} = 2 a_{n} + b_{n} = c_{n} = a_{n} + 2 c_{n}$

One can show $a_{n} + b_{n} + c_{n} = 2 F_{2 n + 1} - 1$ . It is also true that cancellations are not possible.

Posted by Chao Xu on 2011-06-23.

Tags: braid group, BSU REU, group theory, Haskell.