An Upper Bound on Reidemeister Moves

 

Graham’s number is famous for being the largest number to have ever shown up in a proof. The true story is more complicated, as I discovered by asking Graham. But here’s a much smaller but still respectable number that showed up in knot theory:

2 \uparrow \uparrow (10 \uparrow 1,000,000)

It’s 2 to the 2 to the 2 to the 2… where we go on for 101,000,000 times. It appears in a 2011 paper by Coward and Lackenby. It shows up in their upper bound on how many steps it can take to wiggle around one picture of a link until you get another picture of the same link.

This upper bound is ridiculously large. But because this upper bound is computable, it follows that we can decide, in a finite amount of time, whether two pictures show the same link or not. We know when to give up. This had previously been unknown!

Here’s the paper:

• Alexander Coward and Marc Lackenby, An upper bound on Reidemeister moves, American Journal of Mathematics 136 (2014), 1023–1066.

Let me spell out the details a tiny bit more.

A link is a collection of circles embedded in 3-dimensional Euclidean space. We count two links as ‘the same’, or ‘ambient isotopic’, if we can carry one to another by a smooth motion where no circle ever crosses another. (This can be made more precise.) We can draw links in the plane:

and we can get between any two diagrams of the same link by distorting the plane and also doing a sequence of ‘Reidemeister moves’. There are 3 kinds of Reidemeister moves, shown above and also here:

Coward and Lackenby found an upper bound on how many Reidemeister moves it takes to get between two diagrams of the same link. Let n be the total number of crossings in both diagrams. Then we need at most 2 to the 2 to the 2 to the 2 to the 2… Reidemeister moves, where the number of 2’s in this tower is cn, where c = 101,000,000.

It’s fun to look at the paper and see how they get such a terrible upper bound. I’m sure they could have done much better with a bit of work, but that wasn’t the point. All they wanted was a computable upper bound.

Subsequently, Lackenby proved a polynomial upper bound on how many Reidemeister moves it takes to reduce a diagram of the unknot to a circle, like this:

If the original diagram has n crossings, he proved it takes at most (236n)11 Reidemeister moves. Because this is a polynomial, it follows that recognizing whether a knot diagram is a diagram of the unknot is in NP. As far as I know, it remains an open question whether this problem is in P.

• Marc Lackenby, A polynomial upper bound on Reidemeister moves, Annals of Mathematics 182 (2015), 491–564.

As a challenge, can you tell if this diagram depicts the unknot?

If you get stuck, read Lackenby’s paper!

To learn more about any of the pictures here, click on them. For example, this unknotting process:

showed up in this paper:

• Louis Kauffman and Sofia Lambropoulou, Hard unknots and collapsing tangles, in Introductory Lectures On Knot Theory: Selected Lectures Presented at the Advanced School and Conference on Knot Theory and Its Applications to Physics and Biology, 2012, pp. 187–247.

I bumped into Coward and Lackenby’s theorem here:

• Evelyn Lamb, Laura Taalman’s Favorite Theorem, Scientific American, 8 March 2018.

It says:

Taalman’s favorite theorem gives a way to know for sure whether a knot is equivalent to the unknot, a simple circle. It shows that if the knot is secretly the unknot, there is an upper bound, based on the number of crossings in a diagram of the knot, to the number of Reidemeister moves you will have to do to reduce the knot to a circle. If you try every possible sequence of moves that is at least that long and your diagram never becomes a circle, you know for sure that the knot is really a knot and not an unknot. (Say that ten times fast.)

Taalman loves this theorem not only because it was the first explicit upper bound for the question but also because of how extravagant the upper bound is. In the original paper proving this theorem, Joel Haas and Jeffrey Lagarias got a bound of

2^{n 10^{11}}

where n is the number of crossings in the diagram. That’s 2 to the n hundred billionth power. Yikes! When you try to put that number into the online calculator Wolfram Alpha, even for a very small number of crossings, the calculator plays dead.

Dr. Taalman also told us about another paper, this one by Alexander Coward and Marc Lackenby, that bounds the number of Reidemeister moves needed to show whether any two given knot diagrams are equivalent. That bound involves towers of powers that also get comically large incredibly quickly. They’re too big for me to describe how big they are.

So, I wanted to find out how big they are!

If you want a more leisurely introdution to the Haas–Lagarias result, try the podcast available at Eveyln Lamb’s article, or this website:

• Kevin Knudson, My favorite theorem: Laura Talman, Episode 14.

9 Responses to An Upper Bound on Reidemeister Moves

  1. arch1 says:

    John, in your description of the Coward/Lackenby upper bound, I think you left out the n at the very top of the tower (I’d call this a nit, except I think the topmost is most important number of all:-)

    Your mention of Graham’s number reminded me of another Graham number mentioned in a profile I read long ago in a delightful book titled (I think) Mathematical People. After surveying his life the interviewer asked Graham how he found time for everything (I think he was head of math dept at AT&T Bell Labs, prolific researcher, advisor of numerous grad students, editor of numerous journals, expert trampolinist, accomplished juggler and president of Int’l Juggling Assn, expert bowler (numerous 300 games to his credit), not to mention being Paul Erdos’s link to the real world plus the stuff I forgot). Graham replied: “Well, there are 168 hours in a week.”

    • John Baez says:

      I left out the n on purpose because I was talking about a number, not a function of n. Perhaps that’s too confusing for people? Of course it’s the function of n that really matters here, as I explain later.

      I’m very fond of the number 168, not only because it’s the number of hours in a week, but also because it’s the size of the second smallest nonabelian simple group, PSL(2,7), which is connected to the number 7 in the same way that the rotational symmetry group of the icosahedron, PSL(2,5), is connected to the number 5.

      One cool fact is that this number 168 is related to why the days of the week have the names they do! I wrote a bit about this back in “week214” of This Week’s Finds, so let me quote myself:

      In the old days, astrologers liked to list the planets in order of decreasing orbital period, counting the sun as having a period of one year, and the moon as period of one month:

      Saturn (29 years)
      Jupiter (12 years)
      Mars (687 days)
      Sun (365 days)
      Venus (224 days)
      Mercury (88 days)
      Moon (29.5 days)

      For the purposes of astrology they wanted to assign a planet to each hour of each day of the week. To do this, they assigned Saturn to the first hour of the first day, Jupiter to the second hour of the first day, and so on, cycling through the list of planets over and over, until each of the 24 × 7 = 168 hours was assigned a planet.

      Each day was then named after the first hour in that day. Since 24 mod 7 equals 3, this amounts to taking the above list and cycling around it, reading off every third planet:

      Saturn (Saturday)
      Sun (Sunday)
      Moon (Monday)
      Mars (Tuesday)
      Mercury (Wednesday)
      Jupiter (Thursday)
      Venus (Friday)

      And that’s how they got listed in this order! At least, this is what
      the Roman historian Dion Cassius (AD 150-235) claims. Nobody knows for sure.

  2. bjonas says:

    What happened to your other blog at http://math.ucr.edu/home/baez/diary/ ? Are you abandoning it forever, or are you just taking a break writing it?

    • John Baez says:

      I call that my diary, not a blog… since I deliberately don’t allow comments there. I’m glad you’re curious about it.

      I’ve been too busy to keep up with it! I have a lot of projects going, mainly with my 8 grad students and one postdoc, but also with Metron Scientific Solutions and Pyrofex, and they’re eating up more and more of my time. I’ll eventually get back to it. The week after next is finals week for the winter quarter here at UCR, and I’m not teaching during the spring quarter or summer, so I’m hoping life will calm down slightly.

  3. arch1 says:

    Thanks John (also for the Dion Cassius story – I was aware of the heavenly body / day name link but but never gave a thought to the ordering or the reason why). I guess we’ll never know whether Cassius was better as a historian or a numerologist.

  4. […] John Baez, An Upper Bound on Reidemeister Moves. […]

You can use Markdown or HTML in your comments. You can also use LaTeX, like this: $latex E = m c^2 $. The word 'latex' comes right after the first dollar sign, with a space after it.

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.