# Conjugacy problem for small braid groups

The conjugacy problem for braid groups $B_3$ and $B_4$ can be solved in polynomial time, it is noted in the paper by Birman, Ko and Lee(2001).

That was a result in 2001. Are there any new results on other small braid groups? Is the conjugacy problem in $B_5$ solvable in polynomial time?

Also, I'm still curious on exactly how fast the conjugacy problem in $B_3$ can be solved(polynomial time is too broad). The only paper that described such algorithm is behind a paywall.

-

This 2008 paper (freely available) explains the fastest known solution of the conjugacy problem in $B_3$. I think the polynomial time complexity of that solution can be easily extracted from that paper.

-

This is a longish comment on the $B_3$ case.

$B_3$ is isomorphic to the fundamental group of the complement of a trefoil knot. A trefoil complement fibres over $S^1$ with fiber a once-punctured surface of genus $1$, so $B_3 \simeq F_2 \rtimes \mathbb Z$. So the conjugacy problem in $B_3$ is reducible to a conjugacy problem in $F_2$, the free group on two generators. I believe the action of $\mathbb Z$ on the fiber comes from the hexagonal tiling of the torus. An automorphism of order $6$ about a point of the hexagon induces the monodromy of the bundle.

Conjugacy in a free group can be solved by hyperbolic group / Dehn algorithm techniques (cyclic reduction of words, etc). So I expect this should be quite fast.

-
Yes, this would result a linear algorithm for conjugacy problem in $B_3$. – Chao Xu Jul 18 '11 at 1:19
@Ryan: The conjugacy problem for $F_2 \rtimes \mathbb Z$ does not reduce to the conjugacy problem in $F_2$. The conjugacy problem in $F_2$ is trivial: two cyclically reduced words are conjugate iff they are cyclic shifts of each other. – Mark Sapir Jul 18 '11 at 2:37
Hi Mark. What do you mean by "does not reduce to..." ? By "reduce to" I don't mean they're the same thing, just that you can use the solution of the latter as a step in solving the former problem. The idea is to conjugate elements of $F_2 \rtimes \mathbb Z$ first by elements of $\mathbb Z$, then by elements of $F_2$. In both cases we know the outcome of the action, so technically this reduces to six applications of the solution to the conjugacy problem in $F_2$, one for every outer automorphism of $F_2$ induced by the monodromy. – Ryan Budney Jul 18 '11 at 3:18
@Ryan: I mean that although the conjugacy problem in free-by-cyclic groups is solvable, it is a very non-trivial statement and the complexity is not known. In general the conjugacy problem in a semidirect product $G\rtimes {\mathbb Z}$ may be undecidable even if it is decidable in $G$. – Mark Sapir Jul 18 '11 at 4:36
@Ryan: There are groups with solvable conjugacy problem which are index 2 subgroups in groups with unsolvable conjugacy problem (and vice versa). As I understand, the easiest solutions of the conjugacy problem in $B_3$ uses the fact that $B_3$ is a central extension of $PSL_2({\mathbb Z})$. It is not trivial and is explained in the 2008 paper by Birman and others. – Mark Sapir Jul 18 '11 at 16:40