Can it be just the not-ation?

Colin Rourke is a topologist at the University of Warwick in England. He is one of numerous mathematicians whose work is surveyed in an entertaining article by Sam Nelson of the Claremont Colleges in California, “The Combinatorial Revolution in Knot Theory” which appeared in last month’s AMS Notices. Rourke’s home page has interesting materials and notes besides a selection of his papers. These include a one-page formulation of Gödel’s first incompleteness theorem and a model for the universe that “overturns nearly every tenet of current cosmology.”

Today Dick and I wish to draw attention to the mathematical structures in Nelson’s article, whose properties have been developed by Rourke and others, and to how syntax may take precedence over the ‘real physical meaning’ of a mathematical concept.

Nelson summarizes the “revolution” in his opening paragraph as follows:

Instead of thinking of knots…geometrically as simple closed curves in ${\mathbb{R}^3}$, a new approach defines knots combinatorially as equivalence classes of knot diagrams under…certain diagrammatic moves.

Much as the concept of number needed to move from ‘real’ to ‘imaginary’ in order to yield the fundamental theorem of algebra, so are the more general not-ation based not-ions of knots needed to fill out invariants of certain mathematical structures.

Rourke also made an important advance on the Poincaré Conjecture in 1994, about a decade before it was completed to a theorem by Grigory Perelman. He proved that there was an algorithmic procedure that would generate a counterexample to the conjecture if it were false. In logical terms, he proved the negation of the conjecture equivalent to a ${\Sigma_1}$, i.e. existential, statement of arithmetic. Of course Perelman’s proof obviated this theorem. However, the idea matters to us because ${\mathsf{P} = \mathsf{NP}}$ is only known to be a ${\Sigma_2}$ statement. Proving it equivalent to a ${\Sigma_1}$ or ${\Pi_1}$ statement, so that at least one of the ‘equal’ or ‘not equal’ cases would be provable, would be the greatest development in decades.

Knots Into Codes

According to a multiple-sourced legend, Alexander the Great was once challenged to untie a complicated knot that had tied the ox-cart of a peasant-king named Gordias for many years. Alexander either used his sword or pulled out the rod of the cart by which it was tied, thus creating or exposing ends of the string by which to undo it. Pulling out an end of a string to unravel a knot may not yield any useful mathematics, however.

Alexander could have first fluffed the knot so that no more than two segments of string would cross each other at any point. Then the knot’s shadow yields a planar graph of degree 4 in which each vertex has two “over” edges and two “under” edges, and this is the knot’s diagram. If the knot had eleven crossings, the diagram might look like this:

If we trace the diagram beginning at the arrow, assign a number for each crossing in the order encountered, and use a minus sign when traversing an “under” edge, we can abstract the knot into the sequence of numbers

$\displaystyle 1,-2,3,-4,5,6,-7,-8,4,-9,2,-10,8,11,-6,-1,10,-3,9,-5,-11,7$

Of course this code is named after Gauss. There are several variations on it. We adopt the “signed Gauss code” in one of Nelson’s attractive knot-theory pages, but using ${{}^*}$ to mean “under” and suggest complex conjugation—in line with a footnote in his survey.

To define it formally, choose ${\omega = \sqrt{2} + \sqrt{2}i}$ as the principal eighth root of unity. The crossing elements are now subscripted copies of a power of ${\omega}$. If you are following the “over” edge with the “under” edge directed right-to-left, take ${\omega}$; if left-to-right, take ${\omega^5 = -\omega}$. If you are following the “under” edge with the “over” edge going right-to-left use ${\omega^3}$; if left-to-right then by ${\omega^7 = \omega^*}$. If the second crossing has this last case we can write ${2^*}$ as short for ${\omega_2^*}$. The code always has a ${{}^*}$ where the original Gauss code had a ${-}$ sign. The above knot gives:

$\displaystyle -1,2^*,3,-4^*,-5,6,-7^*,8^*,-4,9^*,2,-10^*,8,-11,6^*,-1^*,-10,-3^*,9,-5^*,-11^*,-7.$

Flipping the knot over conjugates every element, while any reflection (right to left or top to bottom) negates every one. Reversing every edge reverses the sequence but does not change any ${*}$ or ${-}$. As with the “extended Gauss code” defined in our source for this diagram, this code preserves enough information to reconstruct the knot from the diagram.

The code ${1,2^*,3,1^*,2,3^*}$ yields the trefoil knot. Note that in any code, each element appears once with a ${*}$ and once without. Thus the codes are some kind of generalized commutator.

Diagrammer Move Grammar

Suppose the modified Gauss code has the sub-sequence

$\displaystyle a,a^*\quad\mbox{or}\quad a^*,a$

for some crossing element ${a}$. This means we’ve drawn a loop over or under in he direction of travel, but the loop isn’t wound around anything. So it can just be pulled taut. Since the crossing elements are complex units, we already have ${a a^* = a^* a = 1}$. Note that since the codes are really cycles, ${a^*,\dots,a}$ and ${a,\dots,a^*}$ are the same cases.

Now suppose instead that the modified Gauss code has

$\displaystyle \dots,a,-b,\dots, a^*,-b^*,\dots \qquad\mbox{or}\qquad\dots,a,-b,\dots, -b^*,a^*$

where ${a}$ and ${b}$ have the same sign, and the subscripts on ${a}$ and ${b}$ differ by ${1}$. In words this means we have two consecutive over-crossings of the same other segment, or two under-crossings of it. In either case the two segments are merely sitting one atop the other and are not linked. Again these sub-sequences can be erased.

To describe the third move, suppose we originally had 3 segments cross at one point: a lower strand going northwest–southeast, a middle strand going southwest–northeast, and a top strand going east–west. When Alexander fluffs the knot, the top segment can either bend up or bend down. The two resulting equivalent configurations are:

Suppose the topmost segment is first traversed west-to-east, next the bottom one NW-to-SE, and last the middle one SW-to-NE. The corresponding rule for the modified Gauss code is:

$\displaystyle \dots,-a,b,\dots,-a^*,-c^*,\dots,-c,b^*,\dots \quad\leftrightarrow\quad \dots,a,-b,\dots,-c^*,-b^*,\dots,a^*,-c,\dots$

There are similar rules for the other arrow directions and orders of visiting the segments. The diagram comes from this article in John Armstrong’s blog “The Unapologetic Mathematician” which we keep in our sidebar, and shows colorings associated to diagrams.

How Knotty is the Not-Knot?

Nelson’s article shows the moving strand in the middle rather than on top. This doesn’t matter—if we were to move the SW-NE strand in the left diagram northwest, we would still get the right diagram. This neat theorem was proved in 1923 by Kurt Reidemeister:

Theorem 1 A knot diagram represents the unknot if and only if all of its crossings can be eliminated by some sequence of the above moves—equivalently, iff its (modified) Gauss code is reducible to 1.

Here is a “Gordian” example. This echoes Hilbert’s Nullstellensatz saying that a system of polynomial equations over ${\mathbb{C}}$ has no solution if and only if 1 can be derived from it by Gröbner basis moves.

As shown by Dick’s posts on work with Zeke Zalcstein, we are interested in complexity properties of these kinds of rewriting systems. In particular, the problem of whether a diagram represents the unknot is in ${\mathsf{NP}}$, and is in ${\mathsf{co}\mbox{-}\mathsf{NP}}$ if the Generalized Riemann Hypothesis is true, but has not been proved to be in ${\mathsf{P}}$. GRH is needed only to get good bounds on primes ${p}$ such that certain integer polynomials associated to the knots have roots in ${\mathbb{Z}/p}$.

To Knot or Not to Knot, or N-Knot?

The point of departure in Nelson’s survey is that the rewriting theorems apply even to codes that are not from shadows of “real” knots in 3-space. The simplest such code is the commutator

$\displaystyle a,b^*,a^*,b.$

Any shadow that includes this pattern must have at least one more crossing. However, a diagram giving this code can be drawn on the torus, looping from ${b}$ under and around to join the line into ${a}$.

His survey goes into a concept of virtual crossings and virtual knots introduced in this 1999 paper by Louis H. Kauffman. There is no Gauss code for the virtual crossing itself, though we have marked it ${c}$ in this diagram:

The point is that every (modified) Gauss code—subject only to the rule of every element and its conjugate appearing once each—has a planar diagram with virtual crossings. This allows spatial intuition and properties about crossings to be applied to all codes.

In passing we ask whether there is any utility in considering ${c}$ in the diagram to be a “nondeterministic crossing” instead—with either strand possibly being the “over” one. This could be coded as

$\displaystyle a,b^*,c/c^*,a^*,b,c^*/c.$

Note that if the SW-to-NE strand in crossing ${c}$ is “over,” then we get the trefoil knot. If “under,” then it becomes ${a,b^*,c^*,a^*,b,c}$ which the second Reidemeister move applied to ${b,c}$ transforms to ${aa^* = 1}$. (One could also use the move for ${a,c}$ since it is a cycle.)

Another way to think of an “N-Knot” is that for any element ${c}$ labeled nondeterministic, it is legal to swap ${c}$ and ${c^*}$. Is it harder to decide whether an N-Knot can be reduced to ${1}$ than for a regular (or virtual) knot? This is different from computing the unknotting number insofar as only some crossings are nondeterministic. It strikes us that this problem ought to be ${\mathsf{NP}}$-complete, which would make it unlikely that an efficient invariant can be found to prove that a given non-trivial N-knot does not reduce to ${1}$.

Not Knot-Code Codes

It would be nice to avoid the non-local coupling between the two times a crossing is visited. Therefore let us try to abstract the crossing itself. Or, let us abstract the notion of a segment as it goes through one or more crossings. Define ${x \rhd y}$ to mean that ${x}$ goes under ${y}$ at a crossing. Optionally we can specify ${x \triangleright y}$ to mean that the crossing is positive in our signed Gauss code, and use ${\triangleright^{-1}}$ when it is negative. The three Reidemeister moves then yield these axioms:

$\displaystyle \begin{array}{rcl} && x \triangleright x = x\\ && (x \triangleright y) \triangleright^{-1} y = (x \triangleright^{-1} y) \triangleright y = x\\ && (x \triangleright y) \triangleright z = (x \triangleright z) \triangleright (y \triangleright z). \end{array}$

That ${x \triangleright^{-1} x = x}$ and the last equation with ${\triangleright^{-1}}$ in place of ${\triangleright}$ everywhere follow from this. When the distinction between ${\triangleright^{-1}}$ and ${\triangleright}$ is ignorable, these define a structure called a kei, else they define a quandle. These rewriting systems tell some already-familar stories.

Keis and Quandles and Racks, Oh My

Here are two examples that distinguish a kei from a quandle. Consider any group, such as one of nonsingular matrices. Define:

$\displaystyle \begin{array}{rcl} A \rhd B &=& B A^{-1} B\\ A \triangleright B &=& B A B^{-1}\\ A \triangleright^{-1} B &=& B^{-1} A B. \end{array}$

The first operation gives a kei because ${(A \rhd B) \rhd B = B A^{-1} B \rhd B = B (B^{-1} A B^{-1}) B = A}$ and

$\displaystyle \begin{array}{rcl} (A \rhd C ) \rhd (B \rhd C) &=&C A^{-1} C \rhd C B^{-1} C\\ &=& C B^{-1} C (C^{-1} A C^{-1}) C B^{-1} C\\ &=& C (B A^{-1} B)^{-1} C = (A \rhd B) \rhd C. \end{array}$

The latter two operations give a quandle and not a kei because both are needed to cancel the ${B}$‘s, namely

$\displaystyle (A \triangleright B) \triangleright^{-1} B = (B A B^{-1}) \triangleright^{-1} B = B^{-1} (B A B^{-1}) B = A,$

while

$\displaystyle \begin{array}{rcl} (A \triangleright C) \triangleright (B \triangleright C) &=&(C A C^{-1}) \triangleright (C B C^{-1})\\ &=& (C B C^{-1}) (C A C^{-1}) (C B^{-1} C^{-1})\\ &=& C B A B^{-1} C^{-1} = (A \triangleright B) \triangleright C. \end{array}$

We can get the same examples with unitary matrices ${A}$ and ${A^*}$ for inverses, and this is just one hint of why knots and keis and quandles are relevant to quantum mechanics.

If a quandle is “excused” from obeying the first axiom, then it becomes a rack. Our last example, from Nelson’s survey and quandle page, shows all three. Consider any algebraic structure ${{\cal S}}$ that admits left-multiplication by objects ${s}$ and ${t}$, such as a module. For ${x,y \in {\cal S}}$ define:

$\displaystyle \begin{array}{rcl} x \triangleright y &=& tx + sy \quad (\mbox{modulo~} s^2 - (1-t)s)\\ x \triangleright y &=& tx + (1-t)y\\ x \triangleright^{-1} y &=& (1/t)x + (1-(1/t))y\\ x \rhd y &=& tx + (1-t)y \quad (\mbox{modulo~} t^2) \end{array}$

The middle two operations define the Alexander quandle, which needs no modulus, while the first defines only a rack because ${x \triangleright x = (t+s)x}$ makes no assumption on ${t+s}$.

David Joyce showed in his dissertation in 1980 that two oriented knots are related by a homeomorphism of the 3-sphere if and only if the quandles they generate are isomorphic. Racks go with a further loosening of the idea of knots, and working with Roger Fenn, Colin Rourke proved a similar theorem. Nelson’s survey closes with links to further applications. We are interested in what computational complexity may say about them.

Open Problems

Can we extend the applications of these knot-derived notions?

Is the set of (codes for) unknots in ${\mathsf{P}}$? Does membership in ${\mathsf{NP} \cap \mathsf{co}\mbox{-}\mathsf{NP}}$ need GRH?

Are there coding schemes that are both smarter in helping prove theorems and simpler in complexity?

[changed way signs were described in second move; inserted “negation of the” before Poincaré conjecture.]

1. January 15, 2012 11:01 am

Thanks for the interesting article, I often think about P=NP in terms of TSP, but this makes me aware of another way to look at this question. My thoughts on this are probably nothing new or noteworthy as I am not nearly as well read as others, but when I think of this problem I have noticed many start by trying to find some sort of single solving algorithm that would solve something like TSP in Polynomial time.

It is well known that there are polynomial time algorithms that can solve TSP if the location of the nodes follow some sort of pattern. So it would seem natural to assume that there are families of polynomial time algorithms that are possible in all the cases where there is some apparent pattern in the nodes (e.g. if the locations of nodes are constrained in some useful way). So if one had someway of finding all those possible patterns and algorithms, those things could be solved in polynomial time (which itself is probably a very hard problem). However, this leaves the problem(s) where the location of the nodes can only be described as noise (completely random).

When I think along those lines, the I find it difficult to think of a perfect algorithm, or even a countable set of algorithms that could reduce all the noise (unless perhaps if the locations of nodes are discrete). So even if I could find polynomial time algorithms in one noisy case, it isn’t obvious to me how that could be extended to all cases.

2. January 16, 2012 3:28 am

The negation of the Poincare Conjecture is Sigma_1, and therefore the Poincare Conjecture is Pi_1.

• January 16, 2012 8:20 am

Oops! And I wrote it correctly in the previous sentence! Thanks.

January 18, 2012 6:36 pm

“P=NP is a $\Sigma_2$ statement” – can someone post a reference to this? Thanks.

• January 18, 2012 6:50 pm

One can just do it: P = NP iff (\exists k)(\exists a deterministic TM M)(\forall x)[M(x) halts within |x|^k + k steps and (M(x) = 1 iff x \in SAT)]. This is a \Sigma_2 statement.

At various times I’ve heard rumours of someone proving equivalence to a simpler statement, but I don’t know of anything citable from them.

• January 18, 2012 8:26 pm

“P=NP is a $\Sigma_2$ statement” – can someone post a reference to this? Thanks.

I too would enjoy further references. What Ken posted seems (to me) like the standard definition of the complexity class P! So for Ken’s statement to be a conjecture, there must be an alternative and nontrivially differing definition of P. Plausibly this nontrivial difference is associated to the clause “$(\exists k)$“,   yet I don’t mind saying that I could not describe why this clause (or some other clause) has nontrivial import.

• January 19, 2012 12:01 am

Ah, my formula does include the standard definition of P, but includes SAT as meeting it, so it defines NP=P. It’s not a conjecture—it’s just syntax in the required (exists…)(forall…)[decidable stuff] form.

There are tricky issues of how to represent languages that are outside of P, ones that made my thesis and some of my early papers pretty long…

• January 19, 2012 4:46 am

Thank you very much, Ken!

(1) A lesser portion of my confusion was that I had mentally exchanged (what I guessed to be) the definitions of $\Sigma_2$ and $\Sigma_1$. Ouch!

(2) A grosser and deeper source of confusion was that (as yet) I have conceived no concrete working example of a $\Sigma_1$ statement that, in conjunction with plausible & conceivably provable postulates, would imply $P\ne NP$.

(3) Worst of all, Wikipedia was blacked-out for a day! Which reduced our planetary intelligence by some immeasurable yet surely immense degree.

Seriously, if anyone can point to on-line surveys of these $\Sigma_2$ versus $\Sigma_1$ matters, those surveys would be interesting (to me and) perhaps to many folks. Such surveys don’t seem to be easy to find … perhaps this might be a future GLL topic?

4. April 8, 2012 12:50 am

Regarding the complexity of knottiness. Joel Hass, Jeff Lagarias and Nick Pippinger proved in 1999 that telling that a knot is unknotted is in NP. This is a major result!

An outstanding problem for many years was to determine if telling that a knot is unknotted is in coNP or equivalently if telling that a knot is nontrivial is in NP as well. A few month ago Greg Kuperberg proved it under GRH! Amazing! Kuperberg ingenious short proof is based on a recent important knot-theoretic result by Kronheimer and Mrowka combined with computational complexity result by Korian (discussed in the section “from Primes to Complexity”over this GLL’s post).

There were several results in knot theory in recent years that gradually showed that several invariants (related, generally speaking, to Jones polynomials but more detailed) are enough to tell knottyness. Mrowka is a leading person. I am not so sure about how this story goes.

Eralier Yana, Mari and Yamamoto Proved (Soda 2005) that unknotting is in AM $cap$ coAM.

It is very interesting if the dependence on GRH can be removed. Of course, a major problem is if telling if a knot is trivial is in P. Showing that the problem is in BQP will also be great.

I am not sure what is the complexity for telling if two knots are equivalent. Haken proved that it is decidable. Telling if a knot is trivial feels a little like PRIMALITY while telling two knots apart feels a little like FACTORING.