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]