# Word problem for braid group using a representation

**Input:** $w$ is a word
of length $l$ from the presentation $⟨σ_{1},σ_{2},…,σ_{n−1}∣σ_{i+1}σ_{i}σ_{i+1}=σ_{i}σ_{i+1}σ_{i},σ_{i}σ_{j}=σ_{j}σ_{i}⟩$ where $∣i−j∣=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},…,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}→Aut(F_{n})$. This is what I implemented in Haskell.

If $B_{n}→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} ifj=i,i+1ifj=iifj=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}∘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+lngn)$ 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})_{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} =2a_{n}+b_{n}=c_{n}=a_{n}+2c_{n} $

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