4
$\begingroup$

I am interested in the following situation: given a braid $B$, it induces a link $L$ in a pretty straightforward way ("glue" the endpoints, like here). For a braid $B$, we know how to represent it in a normal form, which provides in particular a complete invariant of the braid (two braids have the same normal form if and only if they are equivalent). The computation of a normal form can be done efficiently. But once the link is formed... what can be done? I don't think we know any computable normal form for links... But do we know any good invariant? By "good invariant" I mean:

0) If two links are equivalent, their invariant is the same (definition of an invariant, nothing new here),

1) It can be computed in polynomial time,

2) If two links are not equivalent, they have same invariant with negligible probability (for some notion of "negligible probability"...)

Improve this question
$\endgroup$
1
  • 2
    $\begingroup$ You're asking a variant of several long-standing open problems in knot theory. It's possible that (1) and (2) are mutually exclusive, but it's also possible they're not. Nobody knows for sure. $\endgroup$
    – Ryan Budney
    Commented Aug 5, 2014 at 23:33

1 Answer 1

Reset to default
8
$\begingroup$

There are two ways to interpret your question.

First -- since you are talking about braids, perhaps you are asking about the conjugacy problem for braids. This is the same as taking a braid closure, with an braid axis. In this case the ultra summit set (USS) of a braid $\sigma$ is a complete invariant for conjugacy classes. It is an open question whether or not USS($\sigma$) is polynomial sized (and hence polynomial time computable). There are other approaches to the conjugacy problem in braid groups, but none are know to be polynomial time.

Second -- if you are not including the axis, then, by a result of Alexander, every link can be represented as the closure of a braid. So your question might be: is there a polynomial time solution to the isotopy problem for links? No such algorithm is known. That the isotopy question is even decidable depends on Thurston's geometrization theorem for Haken manifolds; also, a great deal of work prior to Thurston is needed.

Finally -- you ask if there is an invariant that fails with only "negligible probability". This is a good question - I don't know the answer. Just to make things clear. You have the following model of random links: (a) chose a braid index, (b) choose a length, and (c) choose a random braid of that index and length in the standard generators. Now take the closure to get a link. This is a perfectly nice model of random links. I suggest you consider the multi-variable Alexander polynomial. It can be computed in polynomial time, and I believe that it fails with probability tending to zero (for fixed index, and as the length tends to infinity).

EDIT: There is a problem closely related to the conjugacy problem in the braid group; this is the determination of the Nielsen-Thurston type of a braid as either reducible or pseudo-Anosov. This has a polynomial-time solution, due to Matthieu Calvez - see his paper Fast Nielsen-Thurston classification of braids.

FURTHER EDIT: There have also been, very recently, claims concerning the conjugacy problem for pseudo-Anosovs (and the general conjugacy problem) in mapping class groups. Margalit, Strenner, and Yurttas have claimed a polynomial-time algorithm that, given a pseudo-Anosov, computes the veering triangulation for the associated surface bundle. This is a complete conjugacy invariant for such mapping classes. Here are some notes from a talk by Margalit.

Bell and Webb are claiming a polynomial-time solution to the general conjugacy problem, based on techniques from their paper Polynomial-time algorithms for the curve graph and using some new ideas.

Improve this answer
$\endgroup$
4
  • $\begingroup$ If I interpret your answer correctly, you mean that finding a good invariant for links is equivalent to finding a good invariant for conjugacy classes in braid groups, which we don't have? $\endgroup$
    – Calodeon
    Commented Aug 5, 2014 at 20:31
  • $\begingroup$ Rereading your question, I realize that there are two possible versions. I'll add that to the answer. $\endgroup$
    – Sam Nead
    Commented Aug 5, 2014 at 22:20
  • $\begingroup$ Thanks a lot. And do we have any notion of how much information we lose by forgetting the braid axis? Say we pick two random braids the way you describe and we want to determine if they are conjugate. Form two links out of them, forget about the braid axis, and try to determine if they are isotopic. Do we have a notion of how likely it is that the links are isotopic even though the braids are not conjugate? (Then, computing the Alexander or Jones polynomial would provide a probabilistic solution to the decisional braid conjugacy problem). $\endgroup$
    – Calodeon
    Commented Aug 7, 2014 at 7:25
  • $\begingroup$ We "lose" a lot of information by forgetting the braid axis. These are two related problems, but having the braid axis present makes life much, much simpler. However, I'll guess that for most reasonable ways producing random braids the Alexander polynomial of the closure will distinguish two random braids with probability tending to one exponentially quickly in braid length. Ask Igor Rivin about this - it sounds like his cup of tea. Note that this is not a "solution" to the conjugacy problem (not even a probabilistic one...) $\endgroup$
    – Sam Nead
    Commented Apr 28, 2017 at 20:56

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .