Date: Sun, 25 Aug 96 23:57:46 CDT From: rusin (Dave Rusin) To: baumgart@darmstadt.gmd.de Subject: Re: recognition of knots, question Newsgroups: sci.math In article you write: >My question(s): > > Imagine a closed loop with or without knots, drawn 'in the usual way', >e.g. as a closed line with a few underpasses (no hidden edges, >no multiple underpasses). > Is there an algorithm to check whether there is a knot in this loop >or not? Or even to calculate the type of knot? Any ideas about the >complexity of this algorithm? Well, it's quite easy to take the graphical presentation of the knot and write down from it a presentation of the fundamental group of the knot complement. From there you have two difficulties 1) It's not easy to determine just what the fundamental group really is. This is a problem deep in group theory. One of Hilbert's problems asked for an algorithm which would, for example, determine whether or not a group presentation yielded the trivial group. It turned out to be a result from mathematical logic that no, in fact, one could not describe such an algorithm (using first-order logic). Now, the group presentations which result from a knot projection do not include all group presentations, so it is possible that one _could_ develop a procedure to decide unfailingly whether or not the corresponding fundamental group is trivial (or perhaps whether two of them are isomorphic). 2) What can you do with the fundamental group once you know it? Well, there are various notions of equivalence of knots. None of them is quite the same as "having isomorphic knot groups". It is true (I think) that a string is unknotted iff its knot group is Z (the simplest possible), but it's also true that there are pairs of knots with the same groups but which are really _distinct_ knots. This perspective is a little out of date. About a decade ago there was a lot of activity on _polynomials_ which could be associated to a knot, including then-new polynomials in two variables which were sensitive enough to detect some rather sublty-differing knots. A great deal of information is still lacking, however, and I haven't heard much progress lately. I think there was a summary in the Bulletin of the Amer Math Soc about 3 years ago. The field is much larger and more delicate than would be immediately apparent. (By the way, your "loop" is my "knot", your "knot" is my "non-trivial knot", your "unknotted loop" is my "the unknot" (yes for real). ) dave ============================================================================== Date: Mon, 31 Aug 1998 19:35:10 -0500 (CDT) From: Eric Sedgwick To: rusin@math.niu.edu Subject: unknot algorithm Dear Dave Rusin, I was perusing your pages and came across a question about whether there is an algorithm to detect whether a given knot is the unknot. Under subject area 57. I included a bit at the end of my email. You may know that this problem was solved by W. Haken some time ago. The algorithm is based on triangulating the exterior of the knot, and showing that a compressing disk for the knot exterior (if it were an unknot) would necessarily intersect the triangulation in specific way (it is a normal surface). Moreover, it can be computed whether such a disk exists. Recent work has focused on the efficiency of such algorithms, and algorithms to recognize other types of 3-manifolds: i.e. the 3-sphere, a knot complement. I enjoyed looking at your site ! Eric Sedgwick Oklahoma State University [portion of previous message quoted; deleted -- djr]