# 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 $$\langle \sigma_1,\sigma_2,\ldots,\sigma_{n-1} \mid \sigma_{i+1}\sigma_i\sigma_{i+1} = \sigma_i\sigma_{i+1}\sigma_i, \sigma_i\sigma_j = \sigma_j\sigma_i \rangle$$ 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,\ldots,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 \mathop{\mathrm{Aut}}(F_n)$$. This is what I implemented in Haskell.

If $$B_n \to \mathop{\mathrm{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 $\sigma_i^*(t_j) = \begin{cases} t_j & \text{if } j\neq i, i+1 \\ t_{i+1} & \text{if } j=i \\ t_{i+1}t_it^{-1}_{i+1} & \text{if } j=i+1\\ \end{cases}$

Where $$t_i$$ are generators of $$F_n$$, and $$\sigma_i$$ are the generators of the braid group. The inverse can easily be found.

Using a recursive definition. Let any word of the form $$(\sigma_i w)^*$$ be $$\sigma_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 $$\sigma_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 $$\sigma_i^*(u)$$ to some word $$u$$ takes $$O(|u|)$$ time. One then free reduce. $$\sigma_i$$ is applied $$l$$ times.

An application of $$\sigma_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 $$\sigma_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 \log 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. $$((\sigma_2\sigma_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.

\begin{align*} a_{n+1} &= 2a_n + b_n\\ b_{n+1} &= c_n\\ c_{n+1} &= a_n+2c_n\\ \end{align*}

One can show $$a_n+b_n+c_n = 2F_{2n+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.