Unknot recognition is one of the fundamental questions in low dimensional topology. In this work, we show that this problem can be encoded as a validity problem in the existential fragment of the rst-order theory of real closed elds. This encoding is derived using a well-known result on SU(2) representations of knot groups by Kronheimer-Mrowka. We further show that applying existential quanti er elimination to the encoding enables an UnKnot Recognition algorithm with a complexity of the order 2O(n), where n is the number of crossings in the given knot diagram. Our algorithm is simple to describe and has the same runtime as the currently best known unknot recognition algorithms. This leads to an interesting class of problems, of interest to both SMT solving and knot theory.
In mathematics, a knot refers to an entangled loop. The fundamental problem
in the study of knots is the question of knot recognition: can two given knots
be transformed to each other without involving any cutting and pasting? This
problem was shown to be decidable by Haken in 1962 [
More recent developments show that the UnKnot Recognition
recognition is in NP \ co-NP. Using the theory of normal surfaces, Hass, Lagarias and
Pippenger [
Several approaches to unknot recognition can be found in literature, such as
a complete knot invariant such as Khovanov homology, branching algorithms [
Most of the known algorithms deciding UnKnot Recognition are complex
and have an involved analysis. There are few implementations of this algorithm.
One of the implementations is known to show polynomial time behaviour to
recognize an unknot, but behaves exponentially to detect that a given diagram
represents a knotted knot. [
The authors believe that this paper presents a simpler alternate algorithm,
which relies on reducing the above problem to a sentence in the existential theory
of reals [
Acknowledgments: The authors would like to thank the Institute of Mathematical Sciences, HBNI, Chennai, India, where a part of the work was carried out. The rst author is supported by the NCN grant number 2015/18/E/ST6/00456. The second author is supported by the FWF project number P30301. 2
This section contains some of the basic de nitions in knot theory, and a brief
note on quanti er elimination and existential theory of reals without explicitly
stating the algorithm. For a more detailed introduction to knot theory one may
refer to [
For a natural number n, we use [n] to denote the set f1; 2; : : : ; ng. We use SU(2) to denote the group which contains 2 2 complex hermitian matrices with unit determinant, with multiplication as the group operation. For a natural number d, we use Sd to denote the subset of Rd with euclidean norm equal to one. The symbol i denotes p 1, the imaginary root of unity. The symbol ^ is used to denote the operation of logical conjunction. The symbol _ is used to denote the operation of logical disjunction.
De nition 1. A (tame) knot K is the image of a smooth injective map from S1 to S3.
Remark 1. S3 in the above de nition can be replaced by R3. But we use S3, because some of the concepts that we introduce such as knot groups, exist only in the context of the embedding of a circle in S3.
Two knots are considered to be the same, if they are related by an equivalence condition called ambient isotopy. It is de ned as follows: De nition 2 (Ambient Isotopy). The knots K1 and K2 are ambient isotopic if there exists a smooth map F : S3 [0; 1] ! S3 such that: { 8x 2 S3: F (x; 0) = x. { F (K1; 1) = K2. { 8t 2 [0; 1]: F (S3; t) is a homeomorphism of S3.
Ambient isotopy describes when a knot can be transformed into another by a deformation that does not involve any cutting and pasting. To draw a knot on paper, we use the convention that wherever the string is shown broken it is assumed to be passing under the unbroken string. To illustrate the above condition, consider the following knots:
The rst two knot diagrams shown above can be deformed into each other by twisting/untwisting, thus they represent the same knot. Deforming either of the rst two knots into the third knot, would involve cutting and pasting. Thus it is di erent from the former knots.
De nition 3. An unknot is a knot which is ambient isotopic to the circle S1. A knot k is knotted if and only if it is not an unknot.
Determining when two diagrams represent the same knot, is the key problem of knot theory. The special case of it, determining when a given knot diagram is equivalent to unknot is called the unknot recognition problem. There have been several algorithms and approaches to the knot recognition, listed in the previous section. Knot Group One of the known invariants of knots is the fundamental group of the knot complement. Knot complement refers to the compact 3-manifold obtained by considering the complement of a tubular neighbourhood of the knot. This invariant can detect knots up to mirror image. Presentations of this group, called the Wirtinger presentation, can be easily computed from a knot diagram in the following manner: { The knot diagram is oriented in one of the two possible directions. The string constituting the knot is given a direction which xes the direction of all the arcs occurring in the knot diagram. { Every connected arc is associated to a distinct generator. { Every crossing gives rise to a relation in the presentation. The relation depends on the orientation of the arcs in the crossing, in the manner as shown in Figure 1.
Computing the Wirtinger presentation of a group from the diagram can be achieved using the steps described above in time which is a linear function of the number of crossings in the given knot diagram.
SU(2) representations of the knot group The following theorem by Kronheimer - Mrowka, translates unknot recoginition to existence of non-commutative SU(2) representations of the knot group.
Proposition 1 ([
The following lemma is derived from the theorem above. The reverse direction of the lemma follows from the fact the knot group of the unknot is Z, and all its SU(2) representations are commutative.
Lemma 1. A knot K is knotted if and only if there exists a non-commutative SU(2) representation of the knot group 1(S3 n K).
We note that every nitely presented group has a trivial homomorphism to the group SU(2) via a mapping of each generator to the identity matrix. xj x x x -1 j k j xk xk+1 = xk+1 xj xj
xj xk+1 xk x -1 xkxj = xk+1
j
Quanti er Elimination in Existential Theory of Reals Decidability of the rst-order existential theory of reals refers to the existence of a decision procedure for validity of all sentences of the form:
9X: F (X); where F is any quanti er free formula of polynomial equalities and inequalities in real variables X. It follows from the Tarski-Seidenberg theorem that the problem above is decidable by a quanti er elimination algorithm. The quanti er elimination in this case, in fact holds true for deciding validity of all rst-order sentences. Quanti er elimination algorithm refers to computation of a quanti er free sentence, which is equivalent to the sentence with quanti ers. Validity of the quanti er free sentences can be computed, which makes the algorithm a decision procedure for the rst-order theory. Quanti er elimination algorithm in the existential fragment is restricted to nding equivalent quanti er free sentences only for rst-order sentences with existential quanti ers, of the form described above.
The known complexity bounds for the quanti er elimination in the general
rst-order theory of reals are doubly exponential. The existential fragment has
a much lower complexity bound and there are several algorithms for it. Our
analysis will be based on the following result:
Proposition 2 (see Proposition 4:2 in [
The algorithm Unknot-QE appears as Algorithm 1 on the next page. Remark 2. The algorithm can be simpli ed leading to improvements in e ciency, within the same complexity class, but our choice of description is motivated by expository concerns.
The key idea behind the algorithm can be stated in terms of the following theorem which will be proved in the next section.
Theorem 1. There exists a computable map , which takes a knot diagram K to a sentence in the existential fragment of the rst order theory of reals. A knot K is knotted if and only if (K) is valid. Moreover, applying an existential quanti er elimination algorithm to (K) leads to a decision method for UnKnot Recognition. 5 6 7 8 9 10 11 12 13 14 25 26 27 28 29 30 end end for for k 1 to n do if Rk = gjgkgj 1gk+11 then
Ek Mk+1Mj MjMk end if if Rk = gj 1gkgjgk+11 then
Ek MkMj MjMk+1 end if /* the real part of the entries of the first row of Ek */ EkRe ReU(Ek) /* the complex part of the entries of the first row of Ek */ EkIm ImU(Ek) Put all the polynomials in EkRe and EkIm in the set P
Put a2k + b2k + c2k + d2k 1 in P end for
Put the equation Pp2P p2 = 0 in E Algorithm 1: Description of the algorithm for Unknot detection.
In the proof, we reduce the Kronheimer-Mrowka property, stated in Section 2.1, to a rst-order sentence in the existential theory of quanti er elimination. Observe that every knot group has Wirtinger presentations which correspond to knot diagrams. These presentations are of the following form:
h g1; g2; : : : ; gn j R1; R2; : : : ; Rn i: For i 2 [n], the symbol gi denotes a generator of the group and Ri denotes a relation satis ed by the generators. In the Wirtinger presentation, each Rk is either gjgkgj 1gk+11 or gj 1gkgjgk+11, where j 2 [n] and depends on k, we use +(Rk) or (Rk) to denote them respectively.
Finding a non-commutative SU(2) representation of 1(S3 n K), if it exists, can be seen as a conjunction of the following steps: 1. Mapping generators of the Wirtinger presentation to matrices in SU(2). 2. Checking that the above map extends to a well de ned homomorphism, i.e. the matrices corresponding to generators satisfy the generating relations of the Wirtinger presentation. 3. Checking that the map is non-commutative.
In the following paragraphs, we elaborate on and construct equivalent conditions for each of the above steps. Let gk be a generator in the Wirtinger presentation, associated to a knot diagram. Consider a map from the set of generators to M, in which we map gk to Mk.
Mk = ak + ibk ck + idk ck + idk ak ibk (1) Here ak, bk, ck, dk are real variables. For Mk to be an element of SU(2), it must be unitary (i.e. the inverse of Mk is equal to transpose of its complex-conjugate) and it must have unit determinant, which gives us the following extra condition on the variables used to de ne it.
Observation 2 (folklore) Mk 2 SU(2) if and only if (a2k + b2k + c2k + d2k = 1).
In addition, the mapped elements Mk's have to satisfy the knot group relations obtained from the Wirtinger presentation i.e.
(+(Rk) ! MjMkMj 1Mk+11 = I) ^ ( (Rk) ! Mj 1MkMjMk+11 = I) (2) where I is the 2 2 identity matrix.
For k 2 [n], we de ne Ek as follows:
Ek = (Mk+1Mj
MkMj
MjMk MjMk+1 +(Rk) (Rk)
The condition on matrices in Equation (2) can be restated in terms ot Ek as follows: satisfy Ek =
00 00 : Observation 3 For Mk 2 SU(2), for i 2 [n], a knot group embedding must
The above observation meets the goal of step (2). The above matrix equality can be rewritten as a system of four quadratic equations in real variables in the following fashion: { Decompose the matrix Ek into real and imaginary parts { Re(Ek) and
Im(Ek): then Ek = 0 if and only if Re(Ek) = 0 and Im(Ek) = 0. { De ne ReU (Ek) and ImU (Ek) to be the sets of polynomial equalities: p(x) = 0; where p(x) is an entry in the top row of the Re(Ek) and Im(Ek) respectively. We similarly de ne ReD(Ek) and ImD(Ek) for the bottom row. Either by simplifying Ek or by noticing the fact that the matrices Mk form a group and their product matrix must also be of the same form as Equation (1), one can observe that:
ReU (Ek) [ ImU (Ek) = ReD(Ek) [ ImU (Ek):
Consider the set P, consisting of all the polynomials ReU (Ek), ImU (Ek) and
a2k + b2k + c2k + d2k 1 = 0, where k 2 [n]. The following lemma allows us to
decrease the number of equalities we have in the system of equations.
Lemma 2 (Reverse Rabinoswitch Encoding [
Let P = fp1 = 0; : : : ; pm = 0g be the system of m equality constraints, as de ned above. Then p1 = 0 ^ p2 = 0 ^ pm = 0 is satis able if and only if Pi2[m] pi2 = 0 is satis able.
The above equation gives an equivalent condition for checking the existence of a SU(2) representation of a knot group. We need to further ensure that the representation is non-commutative. In general, to check that the generators are non-commutative, we would have to check that at least one of the pairs of generators does not commute. However, the special structure of knot group relations allows for a much simpler encoding into polynomial inequalities. In the following lemma we show that nding a non-commutative SU(2) representation is equivalent to nding a representation which maps at least two distinct generators of the Wirtinger presentation to distinct elements of SU(2).
Lemma 3. A knot group 1(S3 n K), with generators gi, has a non-commutative homomorphism to a group if and only if (gi) 6= (gj), for some i 6= j. Proof. In the forward direction, observe that if the generator's images are all equal then is commutative. In the backward direction, assume that the image set of fgig1 i n has at least two distinct elements. Therefore, there must exist an index k 2 [n] such that (gk) 6= (gk+1). Without loss of generality assume the relation Rk = +(Rk), similar steps would be true for the relations. Since (Rk) = I, we have (Rk) form of the As (gk) 6= (gk+1), it must be the case that (gj ) (gk) (gj ) 1 (gk+1) 1 = I: =) (gj ) (gk) (gj ) 1 6= (gk) (gj ) (gk) 6= (gk) (gj ): Therefore
is non-commutative.
If is the SU(2) representation, then it su ces to check that there exist at least two distinct matrices in the image to obtain the existence of a noncommutative representation, in addition to the earlier mentioned constraints. The following series of observations further simplify the criterion: Observation 4 Consider the matrices Mj and Mk, as de ned above where j; k 2 [n].
(Mj 6= Mk) $ (aj 6= ak _ bj 6= bk _ cj 6= ck _ dj 6= dk) Observation 5 Let r1; : : : ; rm be real numbers. There exist indices j; k 2 [n] such that rj 6= rk if and only if W`m=2(r1 6= r`) is true.
The following lemma allows us to convert the system of inequalities encoding the constraint of non-commutativity into just one equivalent inequality. Lemma 4. Let N = fp1 6= 0; : : : ; pm 6= 0g be a system of m inequality constraints. Then p1 6= 0 _ p2 6= 0 _ _ pm 6= 0 is satis able if and only if Pi2[m] pi2 6= 0 is satis able.
Proof. The lemma follows from the negation of the statement of Lemma 2.
Combining Lemmas 3, 4 and Observations 4, 5, we get that it su ces to add the the following inequality, to check non-commutativity:
Xn i=1 (ai a1)2 + (bi b1)2 + (ci c1)2 + (di d1)2 6= 0
Let E be the set consisting of above inequality and the equation in Lemma 2. It is easy to see from Lemma 2, Observations 4 and 5 and Lemma 4, that there exists a non-commutative representation from the knot group to SU(2), if and only if E has a solution. This completes the proof of Theorem 1.
The algorithm consists of rst computing Wirtinger presentation from the input knot diagram, which can be done in linear time. The formula E can be constructed in polynomial time. Next, we analyse the complexity of deciding the feasibility of the constructed existential formula. If the number of crossings in the provided knot diagram is n then the number of real variables in the system of equations is 4n. The system of equations E consists of exactly two statements; one equality and one inequality, with maximum total degree of any monomial of 4. Finally, note that the coe cients of polynomials occurring in our system of equations are from the set f 2 1; 1; 2g, as the coe cients of the polynomials before squaring are from the set f 1; 1g. Using Proposition 2, we get the following result. Theorem 6. The procedure Unknot-QE solves the problem UnKnot Recognition in time 2O(n), where n is the number of crossings in the given knot diagram. 6
In this article, we presented an algorithm for UnKnot Recognition, a proof of correctness, and an analysis of its complexity. The key advantage of this algorithm over the existent algorithms is the simplicity of description while having the same runtime complexity as the other currently best algorithms. The simplicity of this algorithm is largely from an expository perspective, if the existential quanti er elimination is treated as a blackbox. As an open problem, it would be of interest to probe whether one can reduce the runtime complexity further by using a variant of the algorithm presented. It may be possible to do so by decreasing the number of variables in the equation via substitution methods. Practical aspects of this algorithm also need to be explored further, for instancean implementation using existent tools such as SMT solvers and Cylindrical Algebraic Decomposition would be useful. A more `e cient' or implementable algorithm for quanti er elimination in the existential theory of reals would further aid both the theoretical and practical aspects of unknot recognition.