The Jellyfish Algorithm

Stephen Bigelow, Scott Morrison, Emily Peters and I have a preprint up on the arxiv today about the extended Haagerup subfactor and its planar algebra. Scott already explained nicely the story that this paper fits into. Today I wanted to tell you about one of the key elements of this paper, Stephen’s “Jellyfish algorithm.” This algorithm is a kind of “evaluation algorithm” and I hope to get around to putting up some more posts on some other evaluation algorithms as well as some open questions concerning evaluation algorithms (one would prove the 4-color theorem and another is related to whether the exceptional lie algebras aren’t so exceptional after all).

What is an evaluation algorithm? Well suppose you have a bunch of diagrams (think formal sums of links) constructed out of a few generators (think crossings) modulo some relations (think the HOMFLY relations). There are two obvious questions. Are these rules enough to reduce every link to a constant times the empty diagram? Does any way of reducing a given diagram give the same answer? Usually the former question is substantially easier than the latter. Often the first question is answered by giving an explicit algorithm for simplifying diagrams.

One simple example is the Kauffman bracket description of the Jones polynomial. Here the evaluation algorithm is very easy: find a crossing and resolve it, wash, rinse, repeat. This clearly terminates because at every step you get fewer crossings.

A slightly trickier example is HOMFLY. Here you can’t just reduce the number of crossings straight away. However, every knot can be unknotted by switching a certain number of crossings (the minimal such number is called the “crossing number”). So first you find some crossing such that switching it decreases crossing number. Using the HOMFLY relation on that crossing gives a sum of two terms one of which has fewer crossings, and the other of which has the same number of crossings but smaller crossing number. Continue until your knot is unknotted.

For extended Haagerup the situation turns out to be much much trickier. Here’s the basic setup. We have a generator with 16 strands coming into it (for comparison a crossing has 4 strands coming into it). Instead of the HOMFLY relation and the Reidemeister moves we instead have much more complicated relations. Rather than giving the exact form of the relations (which you can find on pages 13 and 14 of the preprint) I’ll sketch the general form of them.

• If a generator connects back to itself then the diagram is zero.
• If you rotate a generator you get a multiple of the generator you started with
• If two generators are connected by half their strands then you can replace that with a sum of diagrams involving no generators
• If you have a generator next to some strands then you can replace it with a sum of a bunch of diagrams (possibly with lots of generators) but where all the generators are on the “far side of the strands.”

Let me elaborate a little on the last relation. In our particular case we have two “pulling through strands” relations, because of the shading. One pulls through a single strand and the other pulls through two. I’ll show you one of them.

In this image the rectangles on the bottom are “Jones-Wenzl” idempotents. These are given by a recurrence relation and correspond to the irreducible representations of quantum su_2. All you need to know about them for this post is that they’re a complicated linear combination of diagrams with no copies of the generator. What happens when you expand all of those out? Well exactly one term (the LHS when you look at all vertical strands) is blocked from the top by a strand. All the other terms are zero or have all generators at the top of the screen.

Ok, now that we have relations of this form how do we evaluate a closed diagram? It proceeds in two totally different phases.

1. Pull all the generators to the outside of the diagram
2. Once they’re all on the outside of the diagram find two of them that are connected by half their strands and reduce them

(Why does the second phase work? It’s a simple lemma about planar graphs and I wouldn’t want to spoil your fun.)

Notice that this is quite different from the algorithms described above. The first phase wildly increases the number of generators. Only in the second phase do we make any progress on removing generators. Here’s a beautiful picture Scott made illustrating the first stage.