Saturday, August 16, 2008

Untangling with Continued Fractions: Part 1

Continuing from before It's time now do discuss the problem of forming a representation of a knot or tangle in machine readable form.

I've defined rational tangles but I should set that in a wider context. A knot is essentially a single closed loop embedded in 3D space and a link is a non-intersecting union of a bunch of these. Any tangle, knot or link can be projected down to 2D space so that you get a finite collection of 'over' or 'under' crossings connected by arcs. You might have to jiggle things around a bit to ensure that you don't get any degeneracies like two separate parts of a knot being projected to the same segment of curve in 2D, but this is always possible. Here's an example of such a 2D projection, a knot diagram, for the photograph I posted last week:

Roughly speaking, two knots or links or tangles are equivalent if you can slide the strings about to get from one to the other without passing one string through another. In the case of rational tangles we have the extra constraint that the free ends mustn't move and must always remain 'at infinity' so you can't pass loops over the end. Given two diagrams for rational tangles, the task is to tell when they represent something equivalent. I'll start on this in a future posting, but for now I just want to consider the problem of getting diagrams like that above into machine readable from. (Incidentally, the rigorous mathematical definition of knot equivalence, ambient isotopy, relies on the notion of finding a continuous bijection between the space around the two knots, not the knot itself.)

We don't need anything particularly clever to form our representation as there is a fairly commonplace way to represent connectons between components using monads. If we have some kind of block with inputs a and b and outputs c and d we can represent this as a line of do-notation looking like


(c,d) <- block (a,b)


Examples of such notation are in Matthew Naylor's article on Lava. We could also use arrows but in this case there is no need.

So now we need to break up a diagram of a rational tangle into components and hook them up, working down the diagram from top to bottom. There are four essential components that can be discerned and I'm calling them cups, caps, overs and unders. Here are the corresponding diagrams for each one:

Cups have two inputs but no output and caps have two outputs and no inputs.

Now all we have to do is label the inputs and outputs of each arc, write the corresponding lines as above, and collect them together in a do-block. Here I've redrawn the above diagram marking the cups and caps with red circles and the overs and unders with green circles.

I've also labelled the inputs and outputs. We can now write the following block of code.


> example (a,b) = do
> (c,d) <- over (a,b)
> (e,f) <- cap
> (g,h) <- over (c,e)
> (i,j) <- over (f,d)
> (m,n) <- cap
> (k,l) <- cap
> (q,r) <- over (h,k)
> (s,y) <- over (l,i)
> (o,p) <- over (n,g)
> (t,u) <- under (p,q)
> (v,w) <- under (r,s)
> (x,z) <- over (y,j)
> cup (o,t)
> cup (u,v)
> cup (w,x)
> return (m,z)


Note how this block has a pair of inputs (a,b) and a pair of outputs (m,z) corresponding to the strings at the top and bottom. Clearly knots and links should have no inputs or outputs but rational tangles should have a pair of inputs and a pair of outputs. The precise order shouldn't matter as long as you don't try to use a name that isn't yet in scope.

So what monad should we use? It's easy to imagine some kind of state monad that allows us to generate fresh labels for each of the connections and collects up a graph-like representation of our tangle. But the surprise is this: it turns out we don't need to do anything complicated like this. With suitable definitions of cup, cap, over and under, not only does the vector space monad give us the representation we want, it also does most of our computation for us. But first I need to explain the underlying mathematics in an upcoming installment.

12 comments:

oldtimer said...

Small typo, I think: the first example should be (c,d) <- block (a,b).

logopetria said...

Your first example of a block:
(b,c) <- block (a,b)
seems to have a typo. I think this should be:
(c,d) <- block (a,b)

Arnar Birgisson said...

Nice teaser.. :)

leithaus said...

i think you should at least make a nod to Conway's knotation. If you stack cup and cap; and you place them (suitably rotated) side by side, then together with the two crossings you get Conway's knotation combinators. You can get a good description from Rob Scharein's thesis. For that matter, knotplot is a cool site and a cool tool.

sigfpe said...

leithaus,

I can't talk about Conway notation until I've talked about the classification of rational tangles. Or at least talked a bit more about rational tangles.

alpheccar said...

Your readers may be interested in the application of rational tangles to biology. For instance the article Modeling protein-DNA complexes with tangles (PDF) is a fun introduction.

leithaus said...

So... here's a question for you. How do quandles and Hopf algebras relate to each other? i know you can get a quandle out of a group with conjugation, but i'm fuzzy on the Hopf-crossed widget connection.

sigfpe said...

leithaus,

Almost everything I know about knots comes from Kauffman's book "Knots and Physics" (and countless mostly-forgotten seminars from my student days). I don't recall anything about a relationship between Hopf algebras and quandles, at least not a direct one.

leithaus said...

Do you know Kassel's Quantum Groups book?

sigfpe said...

leithaus,

Only by name.

Leon Smith said...

Nice. Although, one thing that strikes me about your monadic abstraction is the naming issue, specifically, names need to be referred to on the R.H.S. of a function once, and only once. So it begs the questions:

1. Is there a reasonable or useful interpretation when a name is referred to more than once?

2. Similarly, what if a name is introduced but not referred to at all?

3. Is there an alternate abstraction that enforces this condition?

From reading the comments here, I suspect the answer to #3 is "Conway Notation." Great post, I look forward to reading the rest!

sigfpe said...

Leon,

In answer to (3), what we really want are, I think, linear names.

Blog Archive