The Art Gallery Guardian

Word problem for braid group using a representation

Problem1The word problem for braid groups

Input: ww is a word of length ll from the presentation σ1,σ2,,σn1σi+1σiσi+1=σiσi+1σi,σiσj=σjσi\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 ij1|i-j|\neq 1.

Output: Return true if ww 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 PnP_n as a semidirect product of free groups F1,,Fn1F_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 :BnAut(Fn)^*: B_n \to \mathop{\mathrm{Aut}}(F_n). This is what I implemented in Haskell.

If BnAut(Fn)B_n \to \mathop{\mathrm{Aut}}(F_n) is faithful and it sends ww to ww^*, then ww is II iff w(a)=aw^*(a) = a for every generator aa of FnF_n.

In the a survey by Jonathan Boiser, there is one explicate map. Defined as σi(tj)={tjif ji,i+1ti+1if j=iti+1titi+11if j=i+1 \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 tit_i are generators of FnF_n, and σi\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 (σiw)(\sigma_i w)^* be σiw\sigma_i^* \circ w^*. The algorithm is obvious. Test if w(ti)=tiw^*(t_i) = t_i for every generator in FnF_n is applying a list of σi\sigma_i to elements in FnF_n.

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

The analysis: Given a word with length ll in BnB_n, how long does it take to solve the problem with this algorithm? Each application of σi(u)\sigma_i^*(u) to some word uu takes O(u)O(|u|) time. One then free reduce. σi\sigma_i is applied ll times.

An application of σi\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(l2n)O(l^2 n) algorithm.

Braid groups are automatic. If this natural algorithm solves the problem in O(l2n)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(cln)O(c^l n) for some constant cc. Although I can prove neither σi\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(l2n+lnlogn)O(l^2 n + l n \log n) time, and was proved with advanced techniques.

Update 06/24/2011: Siegel provided a example in B3B_3 where the algorithm run in exponential time. ((σ2σ11)n)(t1)((\sigma_2\sigma_1^{-1})^n)^*(t_1).

If we define an,bn,cna_n,b_n,c_n to be the amount of t1,t2,t3t_1,t_2,t_3 (include it’s inverses) at step nn, ignoring the possibility of cancellation. We have the following recurrence relation.

an+1=2an+bnbn+1=cncn+1=an+2cn\begin{aligned} a_{n+1} &= 2a_n + b_n\\ b_{n+1} &= c_n\\ c_{n+1} &= a_n+2c_n\\ \end{aligned}

One can show an+bn+cn=2F2n+11a_n+b_n+c_n = 2F_{2n+1}-1. It is also true that cancellations are not possible.

Posted by Chao Xu on .
Tags: braid group, BSU REU, group theory, Haskell.