Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

My apologies if this is too closely related to this closed post.

I have been collaborating with a physicist looking at long polymer chains. These chains form knots with 2D projections having on the order of 100s of crossings, but which may in some/most cases all cancel out to give knots of relatively few crossings. I realize that there is no absolute knot invariant to definitively classify the knots that arise. But what is the best or best combination of knot invariants that would be 1) straightforward to compute on static diagrams and 2) distinguish most of the knots?

(By "straightforward to compute" I mean something like skein relations and not something like the fundamental group of the complement space. I realize that this requirement might be somewhat ill-defined, so feel free to lead me in the direction of computational references.)

For instance, I seem to recall somewhere that the trio of the Alexander Polynomial along with the 2nd and 3rd Vassiliev invariants was pretty powerful. Can anyone substantiate that and/or provide a reference?

share|improve this question
3  
Correct me if I am wrong, but isn't computing via skein relations exponential-time, at least if done naively? –  Sam Nead May 2 '12 at 16:16
1  
@Sam Nead: I believe so, which is why, if we're going to work on optimizing computational methods, I want to make sure I'm working with the "right" invariant(s) to begin with. –  Aeryk May 2 '12 at 16:29
add comment

5 Answers

Probably a better answer will come along soon, but in the meantime...

I remember listening to a talk by biologists in the late 1980's about this very problem, but with knotted DNA. They used the Jones polynomial (or perhaps the Kauffman bracket polynomial), but perhaps because that invariant was trendy in those days.

I think professional knot enumerators first compute the Kauffman bracket (or some similar polynomial), and then count representations of the fundamental group into small symmetric groups. I've heard that in practice this almost always distinguishes distinct prime knots, but of course these are knots with relatively few crossings.

If you have hundreds of crossings, I think the most efficient thing to do would be to first find all Reidemeister 1 and 2 moves which reduce the number of crossings. Once that's done hopefully there are many fewer crossings and you can compute the Kauffman bracket using a straightforward algorithm.

share|improve this answer
add comment

In practice, one of the fastest way to tell knots apart is to use SnapPea, http://www.geometrygames.org/SnapPea/

This program computes (approximately, of course) hyperbolic volume of the knot complement. "Most" knots tend to be hyperbolic and for some reasons that we still do not really understand, SnapPea is very efficient in "computing" the hyperbolic structure. Different hyperbolic volumes imply non-isotopic knots. Of course, sometimes, SnapPea will either get stuck (maybe because the knot is not hyperbolic) or will give you the "same" volumes (here "the same" means that the digits that it will give as an output are the same, the actual volumes could be different). For such knots, you would run a different, probably slower, program, using other knot invariants.

share|improve this answer
2  
I think with polymer chains, with high probability you get knots with many trefoil summands. So SnapPea wouldn't be very useful in this situation. SnapPea works best when your input knots tend to be prime. –  Ryan Budney May 2 '12 at 20:53
add comment

I think Kevin's suggestion is likely to be a productive one. GAP has good routines for counting conjugacy classes of representations to a large number of finite groups.

A similar strategy you could use would be this sequence of steps:

1) triangulate the complement and simplify the triangulation. I would do this in SnapPy since its triangulation-simplification code is quite nice. http://www.math.uic.edu/t3m/SnapPy/

2) Export the triangulation to Regina http://regina.sourceforge.net/

3) In Regina, double the 3-manifold and compute Turaev-Viro invariants of the corresponding closed 3-manifold.

The nice thing about these steps is you could do them all in a python scripting interface. They're also very robust. Kevin's suggestions are quite robust, as well. It's not clear to me if one technique would have any advantage over the other.

edit: The above three steps are relatively fast. Turaev-Viro invariants come in a sliding-scale, so you can choose the order of your invariant based on how quick you want the computation to be.

In the near future we'll have Alexander polynomial and module computations available in Regina, including things like signature invariants. Much of the code is written but I want to spend some more time extending the code and ensuring the code is bug-free before release. There are also a lot of other code you could use in Regina, like unknot recognition. But that's computationally quite expensive and you wouldn't want to use it on a large collection of knots.

share|improve this answer
add comment

If your polymer chains are open (embedded closed line segment in 3-space), then I wouldn't recommend using global knot invariants (Alexander polynomial, Jones polynomial) because they will not make any sense. Artificially closing open knots (pretending they are honest topological knots) strikes me as being bad strategy. Instead, Peter Røgen has a body of work on Gauss integral invariants (modifications of early Vassiliev invariants) which in my understanding are the best computational "invariants" ("descriptors" is the right word, because an open knot is topologically trivial) out there right now. His papers also discuss the use of early Vassiliev invariants in distinguishing closed knots.

For closed knots at least, it is my understanding that knot signatures and versions of covering linkage invariants (see e.g. Hartley-Murasugi and e.g. Gordon-Litherland) can be calculated in polynomial time, and are very good at distinguishing knots in practice. I don't know why biologists who study molecules which form closed loops are not using such invariants more extensively, in preference to more computationally expensive invariants; maybe somebody more knowledgeable can comment.

The best answer I can give, though, would be to e-mail Peter Røgen directly and to ask him, because this is exactly what he does for a living.

share|improve this answer
add comment

If these knots can be put in the form of braids, either closed or plat, then you can compute their Jones polynomials quickly if the braid index is reasonably small, say \leq 12. This is particularly useful if you have lots of twisting, which quickly increases crossing number but preserves braid index. Snappy can also handle braids with hundreds of crossings, so you would have two effective and generally independent invariants.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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