Word problem for braid group using a representation
Input: is a word of length from the presentation where .
true if is the identity, else return
The word problem for braid group was solved a long time ago with Artin combing. It requires one to express pure braid group as a semidirect product of free groups . 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 . This is what I implemented in Haskell.
If is faithful and it sends to , then is iff for every generator of .
In the a survey by Jonathan Boiser, there is one explicate map. Defined as
Where are generators of , and are the generators of the braid group. The inverse can easily be found.
Using a recursive definition. Let any word of the form be . The algorithm is obvious. Test if for every generator in is applying a list of to elements in .I wrote the program in Haskell, and posted it on github.
The analysis: Given a word with length in , how long does it take to solve the problem with this algorithm? Each application of to some word takes time. One then free reduce. is applied times.
An application of 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 algorithm.
Braid groups are automatic. If this natural algorithm solves the problem in time, it is not a surprise. However, it is likely not true. The running time is more likely to be for some constant . Although I can prove neither 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 time, and was proved with advanced techniques.
Update 06/24/2011: Siegel provided a example in where the algorithm run in exponential time. .
If we define to be the amount of (include it's inverses) at step , ignoring the possibility of cancellation. We have the following recurrence relation.
One can show . It is also true that cancellations are not possible.