Knot or Not? — The Tangled Topic of Knot Theory

One of the most thorny problems in knot theory is that of knot equivalence: determining if two knots made in a closed loop can be transformed into one another by a series of moves which do not involve cutting the string. Alan Turing conjectured that the problem might be undecidable—impossible to solve in finite time by an algorithm. In 2011, Alexander Coward and Marc Lackenby proved there was “An upper bound on Reidemeister moves” (full text at link) which solves the equivalence problem for the more general problem of link and knot diagrams. For a link with n crossings, they prove:

Theorem 1.1. Let D_1 and D_2 be connected diagrams for some knot or link in \mathbb{R}^3, and let n be the sum of their crossing numbers. Then D_2 may be obtained from D_1 by a sequence of at most \exp ^{(c^n)}(n) Reidemeister moves, where c = 101,000,000.

Now, what is that innocent-looking \exp function with a superscript expression?

The function \exp(x) is the exponential function 2^x , and \exp^{(r)}(x) means iterate this function r times. Thus, \exp^{(c^n)}(n) is shorthand for a tower of 2s with an n at the top, the height of the tower being c^n.

The paper notes:

This upper bound is very large indeed, but it is explicit and computable

How “very large indeed”?

The \exp function is, then the operation of tetration, or iterated exponentiation, also written in Donald Knuth’s up-arrow notation as (2\uparrow\uparrow 101000000 n)^n.

Thus, the problem is computable, but the upper bound on how long it may take is a number so many times longer than the age of the universe that there aren’t enough elementary particles in the visible universe even to write it down.

So, get started on that tangle of cables underneath your desk—“this may take some time”.


Your timing is impeccable from my perspective - especially the reference to the cables underneath my desk. Being an “elevated” kind of guy, I raised some of the tangle to shelf level, as the accompanying photo shows (it is a work in progress and I hope to eventually make it somewhat more tidy).

Yesterday, you see, I installed a set of shelves above part of my extensive desk (Ikea), intended for placement of many of my wired network devices. These include: Synology Router (fabulous), Synology NAS (excellent for automatic backup using Time Machine software), one POE switch (for security cameras), one unmanaged switch (for extra ethernet ports), Apple Time Capsule (functional antique for redun-dun-dundant! backup), and a Fuji scanner (vintage, but still a great device with very good software - though it no longer works with Apple, since Fuji decided to not update software of older models to 64bit processing; thus it connects to my high-horsepower VR machine, on which it works with original software).

[in sum, this is more evidence for my recurring assertion: “life has become too complicated to be lived by un-augmented humans”].