5
$\begingroup$

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.

Improve this question
$\endgroup$

2 Answers 2

Reset to default
3
$\begingroup$

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.

Improve this answer
$\endgroup$
2
$\begingroup$

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.

Improve this answer
$\endgroup$
6
  • $\begingroup$ Yes, this would result a linear algorithm for conjugacy problem in $B_3$. $\endgroup$
    – Chao Xu
    Jul 18, 2011 at 1:19
  • 1
    $\begingroup$ @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. $\endgroup$
    – user6976
    Jul 18, 2011 at 2:37
  • $\begingroup$ 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. $\endgroup$
    – Ryan Budney
    Jul 18, 2011 at 3:18
  • $\begingroup$ @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$. $\endgroup$
    – user6976
    Jul 18, 2011 at 4:36
  • 4
    $\begingroup$ @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. $\endgroup$
    – user6976
    Jul 18, 2011 at 16:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.