A Practical Algorithm for Knot Factorisation

Computational problems in $3$-manifold topology often exhibit a gap between theory and practice. For example, consider the Unknot Recognition problem, which takes a knot $K$ as input, and asks whether $K$ is equivalent to the unknot (see Section 2 for a review of all technical terminology used in this introduction). Although Regina [12] offers an Unknot Recognition algorithm that experimentally exhibits polynomial-time behaviour [15], in theory this algorithm is exponential-time in the worst case. There are other theoretical upper bounds on the complexity of Unknot Recognition, but these often use very different (and in some cases, much more complicated) techniques: it is in both $\mathrm{𝖭𝖯}$ [17] and $\mathrm{𝖼𝗈𝖭𝖯}$ [25, 26], and Lackenby has announced a quasipolynomial-time algorithm [27]. It remains unknown whether there is a (deterministic) polynomial-time algorithm for Unknot Recognition.

We are interested in algorithmically recognising other types of knots as well. Baldwin and Sivek give some complexity results for such other recognition problems in [4]: they show that a range of natural problems are in $\mathrm{𝖭𝖯}$ and/or $\mathrm{𝖼𝗈𝖭𝖯}$ (some unconditionally, others conditional on the Generalised Riemann Hypothesis). Prior to the work in the present paper, none of these problems had algorithms with practical software implementations.

In this paper, we focus on the problem of deciding whether a knot is prime or composite, and in the composite case on computing its prime factorisation. This problem arises from the classical result of Schubert [30] that every knot has a unique prime factorisation. We study variants of this problem, in decreasing order of specificity:

Most commonly, the input knot $K$ is presented as a knot diagram. However, a diagram is difficult to work with in many settings, and the first step of many algorithms is to convert the diagram into a more useful form. Often, the conversion is to a triangulation of the knot exterior: the $3$-manifold obtained by deleting a small open neighbourhood of $K$ from the ambient $3$-sphere. This is fine for decision problems like Problems 2 and 3; however, for Knot Factorisation, if we require the output to be in the form of knot diagrams – rather than triangulations of knot exteriors – then we have the additional challenge of converting these triangulations to diagrams, which is itself a highly nontrivial problem [16].

Our approach is to encode knots as edge-ideal triangulations (H-triangulations in [3]). For a knot $K$, an edge-ideal triangulation is a pair $(𝒯,\mathrm{\ell })$, where $𝒯$ is a triangulation of the $3$-sphere ${𝕊}^3$, and $\mathrm{\ell }$ is an embedded loop (called an ideal loop) of edges (called ideal edges) in $𝒯$, such that $\mathrm{\ell }$ is topologically equivalent to $K$. This idea extends to triangulations $𝒯$ of arbitrary compact $3$-manifolds, and collections of loops in the $1$-skeleton of $𝒯$.

Embedding a knot in the $1$-skeleton of a triangulation is, on its own, not a new idea. For knots in $3$-manifolds this is a common choice of combinatorial encoding; e.g., see [1, 26]. But even for knots in ${𝕊}^3$, this setting has been described and used in many publications with various backgrounds; e.g., see [3, 5, 6, 14, 20, 28] and the references therein.

The novelty of our approach is to view an ideal loop as representing a boundary component of a $3$-manifold, loosely analogous to how an ideal triangulation (in the usual sense) has boundary components given by the ideal vertices. More precisely, given an edge-ideal triangulation $(𝒯,\mathrm{\ell })$ of a knot $K$, we consider a small open solid torus neighbourhood $N$ of $\mathrm{\ell }$, and we view $(𝒯,\mathrm{\ell })$ as a combinatorial presentation of the $3$-manifold $ℳ$ given by deleting $N$ from $𝒯$. In this article, $𝒯$ is a $3$-sphere and hence $ℳ$ is just the exterior of $K$.

To see why this perspective is useful, consider a normal surface $S$ in $𝒯$. The intersection of $S$ with the solid torus $N$ is a disjoint union of meridian discs, with one such disc for each point in $S\cap \mathrm{\ell }$. After deleting $N$, $S$ becomes a surface that intersects the torus boundary of $ℳ$ in curves that all have the same slope (in our case, the slope of the meridian of the knot). Hence, the edge-ideal triangulation carries more information than just the topology of $ℳ$: it also prescribes a slope along which normal surfaces must intersect the boundary of $ℳ$.

We use this setting to factorise knots in the $3$-sphere. However, we believe other applications for edge-ideal triangulations exist. For instance, consider the problem of recognising Seifert fibred spaces (SFS) with nonempty boundary. This was shown to be in $\mathrm{𝖭𝖯}$ by Jackson [22], but the techniques are not well-suited to practical implementation. SFS with boundary fit well into the framework of edge-ideal triangulations: any such SFS $ℳ$ can be characterised using “vertical” essential annuli, which intersect components of $\partial ℳ$ in prescribed slopes. Exploring this idea is work in progress.

The utility of edge-ideal triangulations goes beyond the observation about boundary slopes of surfaces. It also allows us to apply the tool of crushing a normal surface, discussed in detail below. Crushing plays a central role in a number of practical $3$-manifold algorithms provided by Regina [9, 10, 12], such as unknot recognition or $3$-sphere recognition.

Our work extends this to give practical algorithms for Problems 1, 2, and 3. In Section 5.3, we give a straightforward linear-time procedure to convert a diagram of a knot $K$ into an edge-ideal triangulation of $K$, so our techniques apply equally to either method of encoding the input knot. However, converting an edge-ideal triangulation back into a knot diagram is sufficiently difficult to be beyond the scope of this paper. Thus, we settle for the following:

The algorithm (see Algorithm 13) relies heavily on the tool of crushing normal surfaces. For our implementation, we use Regina’s [12] longstanding crushing functionality, which is already known to be effective in practice. As it turns out, this practicability extends to our implementation: we are able to run our algorithm on prime knots from the census up to $19$ crossings [11], as well as composite knots constructed by summing up to $8$ knots sampled from the census (hence, knots with up to $152$ crossings), including some “hard” diagrams of composite knots with up $70$ crossings. See Section 5.4 for details on these experiments.

In addition to the practical implications, we also adapt our techniques to obtain theoretical upper bounds on computational complexity. Specifically, we prove the following:

Since Problem 3 is a special case of Problem 2, this yields an alternative proof of one of Baldwin and Sivek’s results [4, Theorem 7.3]: Composite Knot Recognition is in $\mathrm{𝖭𝖯}$.

The operation of crushing a normal surface is crucial to both the practicality of Algorithm 13 and the proof of Theorem 5, so we now elaborate on its role in our work.

Inspired by unpublished work of Casson, crushing was first studied in detail by Jaco and Rubinstein [23], and later reformulated into a more implementation-friendly framework by Burton [10]. To date, one limitation of crushing is that the theory remains relatively poorly developed for surfaces other than $2$-spheres and discs (though see [13, 21]). At first glance, this is an obstacle for the applications we have mentioned. For a knot $K$, testing whether $K$ is composite entails finding a certain essential annulus (in the exterior of $K$). The same applies to recognising SFS with boundary.

By working with an edge-ideal triangulation $(𝒯,\mathrm{\ell })$, we circumvent this issue: the annuli show up in $𝒯$ as $2$-spheres that intersect $\mathrm{\ell }$ in two points. Thus, instead of crushing annuli, we are able to work in the better-understood setting of crushing $2$-spheres. In Section 4, we develop the theory required to apply crushing in the presence of ideal loops.

The reason crushing is useful for practical computations is that it never increases the number of tetrahedra in a triangulation. This allows us to factor a knot efficiently: we can repeatedly crush surfaces to progressively “decompose” the knot, whilst simultaneously keeping tight control on the amount of data needed to encode the resulting factorisation.

Another feature of our work is that we work exclusively with quad vertex $2$-spheres in our edge-ideal triangulations; we show that suitable $2$-spheres exist in Section 3. Theoretically, this is necessary to control how crushing affects the ideal loop; see Section 4. But even if this theoretical challenge were not present, working with quad (instead of standard) coordinates is often crucial for improving the practical performance of algorithms involving normal surfaces.

We combine the aforementioned ideas to formulate our main algorithm (Algorithm 13) in Section 5; we prove correctness of the algorithm, discuss some implementation details, and summarise our experimental results. In Section 6, we show how our techniques also give a proof of Theorem 5. Finally, we discuss further applications in relation to triangulation complexity in Section 7.

A knot is an embedding of a circle $K:S^1\to {ℝ}^3$ into $3$-space. We sometimes embed knots into the $3$-sphere ${𝕊}^3$, instead of ${ℝ}^3$; since ${𝕊}^3$ is the one-point compactification of ${ℝ}^3$, this has the benefit of making our topological space compact, but otherwise makes very little difference to the theory. Two knots are equivalent, or of the same type, if there is an ambient isotopy $\mathrm{\Phi }:{ℝ}^3\times [0,1]\to {ℝ}^3$ taking the image of one to the image of the other; intuitively, two knots are equivalent if one can be deformed into the other without passing the knot through itself. If a knot is equivalent to the trivial unknotted circle, we call it the unknot, or the trivial knot; otherwise, the knot is nontrivial.

We typically represent a knot by a diagram, obtained by generically projecting the knot into a plane, while keeping information about which strand goes over and which goes under at crossings of the projection. Given two knots $K_1$ and $K_2$, we can construct a connected sum $K=K_1\mathrm{\#}{K}_2$ by cutting both $K_1$ and $K_2$ and gluing the ends together to form a new knot. A knot is composite if it is the connected sum of two nontrivial knots; otherwise, the knot is prime. Every nontrivial knot $K$ has a factorisation $K=K_1\mathrm{\#}\mathrm{\dots }\mathrm{\#}{K}_{\mathrm{\ell }}$ into nontrivial prime knots $K_i$, $1⩽i⩽\mathrm{\ell }$, and this factorisation is unique up to re-ordering [30].

In this section we prove that, in any edge-ideal triangulation $(𝒯,\mathrm{\ell })$ of a composite knot, we can always find a normal $2$-sphere that we can use to either reduce the size of our input, or to witness a (possibly trivial) decomposition of the knot. Crucially, we can ensure that these $2$-spheres are quad vertex, which allows us to: (a) enumerate candidate $2$-spheres efficiently, and (b) control the effect of crushing such $2$-spheres.

Let $(𝒯,\mathrm{\ell })$ be an edge-ideal triangulation of a knot $K$. The ideal loop $\mathrm{\ell }$ consists of a sequence of edges of $𝒯$, which we denote by ${\mathrm{\ell }}_1,\mathrm{\dots },{\mathrm{\ell }}_m$. For any edge $e$ of $𝒯$ and any normal surface $S$ in $𝒯$, let $w_e(S)$ denote the edge-weight of $S$ at $e$ – i.e., the number of times $S$ intersects $e$. Moreover, we define $w_{\mathrm{\ell }}(S)={\sum }_{i=1}^m{w}_{{\mathrm{\ell }}_i}(S)$ – i.e., the number of times $S$ intersects the loop $\mathrm{\ell }$. We have the following two lemmas (see [18, Section 3] for proofs):

Consider an edge-ideal triangulation $(𝒯,\mathrm{\ell })$ and a quad vertex $2$-sphere $S$ intersecting $\mathrm{\ell }$ twice. It is known that crushing $S$ only mildly changes the topology of $𝒯$ [10]. In this section, we use a new characterisation of quad vertex $2$-spheres to show that crushing $S$ also only mildly changes the ideal loop $\mathrm{\ell }$. Moreover, using work of Agol, Hass, and Thurston [1, Sections 4 and 6], we can track how $\mathrm{\ell }$ changes in time polynomial in $|𝒯|$; this is purely theoretical, and in practice a much simpler and more naive tracking method is efficient enough.

The algorithm below takes a knot $K$ as input, and produces the prime factorisation of $K$ as a collection of edge-ideal triangulations. As stated, the input is a diagram of $K$, but by skipping Step 1 the algorithm can also be seen as taking an edge-ideal triangulation as input.

We now adapt our techniques to prove Theorem 5: Problem 2 is in $\mathrm{𝖭𝖯}$, and hence Composite Knot Recognition is in $\mathrm{𝖭𝖯}$. Recall that Problem 2 asks whether a given knot $K$ has at least $k$ summands in its prime factorisation.

Our certificate consists of a sequence of edge-ideal triangulations $({𝒯}_0,L_0),\mathrm{\dots },({𝒯}_m,L_m)$ and quad vertex normal surfaces $S_i$ of ${𝒯}_i$, $i\in \{0,\mathrm{\dots },m-1\}$, such that: (a) $({𝒯}_0,L_0)$ is obtained from $K$ via the procedure outlined in Section 5.3; (b) every $({𝒯}_{i+1},L_{i+1})$ is obtained from $({𝒯}_i,L_i)$ by crushing a suitable quad vertex normal sphere $S_i$ of ${𝒯}_i$; and (c) for all $i\in \{0,\mathrm{\dots },m\}$, $({𝒯}_i,L_i)$ is a union of edge-ideal triangulations of knots in ${𝕊}^3$, such that the input knot $K$ is equal to the connected sum of the knots represented by the components of $L_i$. The certificate is completed by a set of $k$ components of $L_m$ together with a certificate that they form nontrivial knots in their respective components.

Since crushing reduces the size of a triangulation, the $S_i$ are quad vertex normal surfaces, and knottedness lies in $\mathrm{𝖭𝖯}$, the certificate is of polynomial size due to [17, 26].

The procedure from Section 5.3 to build an edge-ideal triangulation $({𝒯}_0^{\prime },L_0^{\prime })$ of $K$, and the verification that $({𝒯}_0^{\prime },L_0^{\prime })$ is combinatorially isomorphic to $({𝒯}_0,L_0)$ are both polynomial time procedures (see, e.g., [29, Lemma 3.1 and Remark 3.2]). The same applies to checking for each $i\in \{0,\mathrm{\dots },m-1\}$, that either $w_{{\mathrm{\ell }}_i}(S_i)=0$ or $w_{{\mathrm{\ell }}_i}(S_i)=2$, and certifying that $S_i$ is a quad vertex $2$-sphere. For this latter task, we must show that type-1 and type-2 induced orbits are trivial, and that $S_i$ is connected; see [18, Section 6.1] for details.

Crushing ${𝒯}_i$ along $S_i$ to obtain triangulation ${𝒯}^{\prime }$ can be done in polynomial time; see [18, Section 2.5]. The same is true for identifying the new collection of ideal loops $L_{i+1}^{\prime }$, following Section 4; and for verifying that $({𝒯}_{i+1}^{\prime },L_{i+1}^{\prime })$ and $({𝒯}_{i+1},L_{i+1})$ are combinatorially isomorphic. Verifying knottedness of components of $L_m$ is polynomial time due to [26].

To prove correctness of the above algorithm, it suffices to check that condition (c) above is valid for all $i\in \{0,\mathrm{\dots },m\}$. It then follows from the uniqueness of prime factorisation [30], that this is enough to verify that the input knot $K$ has at least $k$ summands.

First note that (c) is clearly satisfied for $({𝒯}_0,L_0)$. To proceed by induction, assume that (c) is satisfied for some $({𝒯}_i,L_i)$, . Let $C_i$ denote the component of ${𝒯}_i$ containing $S_i$ and with ideal loop ${\mathrm{\ell }}_i$. Lemmas 11 and 12 imply that crushing $S_i$ replaces $(C_i,{\mathrm{\ell }}_i)$ with either a new edge-ideal triangulation of the same knot, or a pair of edge-ideal triangulations giving a pair of knots obtained by a (possibly trivial) connected sum decomposition of ${\mathrm{\ell }}_i$. Either way, (c) is also satisfied for $({𝒯}_{i+1},L_{i+1})$. See [18, Section 6.3] for more details.

For the converse, suppose the verification algorithm succeeds. It follows that $({𝒯}_0,L_0)$ must be an edge-ideal triangulation of $K$. Moreover, it follows that the $S_i$ are quad vertex normal surfaces, and hence Lemmas 11 and 12 imply that (c) holds for all $i\in \{0,\mathrm{\dots },m\}$. Hence, it follows that $({𝒯}_m,L_m)$ contains $k$ nontrivial knot summands. By uniqueness of the prime factorisation of $K$, this verifies that $K$ has at least $k$ summands.

In this section we leverage the fact that crushing a nontrivial normal surface reduces the size of its ambient triangulation to study triangulation complexity – i.e., the minimum number of tetrahedra necessary to triangulate a given manifold within a fixed class of triangulations.

Let $ℳ$ be the exterior of a composite knot $K$ in ${𝕊}^3$, and let $\tilde{c}(ℳ)$ be the triangulation complexity of $ℳ$ over the class of edge-ideal triangulations. Write $K=K_1\mathrm{\#}\mathrm{\cdots }\mathrm{\#}{K}_m$ for the unique prime factorisation of $K$. Starting with an edge-ideal triangulation $(𝒯,\mathrm{\ell })$ for $K$, our results from Section 4.3 ensure that we can iteratively find quad vertex $2$-spheres to crush at least $m-1$ times to obtain edge-ideal triangulations for each of the prime knots $K_1,\mathrm{\dots },K_m$. If we only crush $m-1$ times, then every crush performs a nontrivial connected sum decomposition; thus, by Lemma 12, each crush increases the number of ideal edges by exactly $2$. Due to the excess ideal edges, it can be shown (see [18, Lemma 25]) that we can crush an additional $2$-sphere. So in fact, we can always crush at least $m$ times, and each crush strictly decreases the overall number of tetrahedra, which establishes the bound

Example 15 motivates the following question.

We can also adapt our methods to obtain complexity results about ideal triangulations of knot complements; see [18, Section 7.2] for details.