Hard Diagrams of Split Links

The Reidemeister theorem [32] is a fundamental and powerful result in low-dimensional topology. It states that any two link diagrams represent equivalent links¹¹1A link is an embedding of a collection of circles into ${ℝ}^3$ and two links are considered equivalent if they are ambient isotopic. Link diagrams are projections of links into a plane as shown, for instance, in Figure 2. We refer to Section 2 for standard definitions in knot theory. if and only if they can be related by a sequence of planar isotopies and local moves, called Reidemeister moves, pictured in Figure 1. This theorem is at the heart of many theoretical results as well as computational applications. Indeed, many knot invariants, from the most basic ones such as tri-colourability [1, Section 1.5] to more advanced ones such as the Jones polynomial [20] or Khovanov homology [3], can be shown to be invariants by demonstrating that they are not modified by Reidemeister moves. From a computational point of view, the Reidemeister theorem allows for a discretisation of the space of possible transformations to consider when testing for knot equivalence. This fact is at the root of a straightforward algorithm to study algorithmic problems in knot theory: at the level of diagrams, apply Reidemeister moves in a random or brute-force manner until a desired property is verified.

A primary example of such a knot theory problem is recognising the unknot, that is, the unique knot admitting a diagram with no crossings. This is a first instance of the fundamental problem of knot theory of deciding whether two knots are equivalent. It turns out that some unknot diagrams, called hard unknot diagrams or culprits [6, 21], exhibit an unwanted behaviour for the above algorithm. Namely, given an initial diagram $𝒟$ of the unknot, the largest number of crossings of a diagram in any sequence of Reidemeister moves from $𝒟$ to the $0$-crossing diagram must be larger than in $𝒟$. This means one first needs to add crossings before being able to reach the $0$-crossing diagram. The existence of such diagrams implies that it is not possible to untangle an unknot diagram by only applying Reidemeister moves that do not increase the number of crossings. An example of such a hard unknot diagram, called the Goeritz culprit, is shown in Figure 2. In [6], it is shown that, when diagrams in ${𝕊}^2$ are considered, at least one extra crossing is required to untangle this unknot. We do not know of systematic techniques or methods to prove easily that a given diagram of the unknot is hard. Instead, all proofs known to the authors resort to an exhaustive search in the graph of Reidemeister moves, which quickly becomes infeasible. Recently, new techniques based on reinforcement learning have been applied to find large numbers of hard unknot diagrams [2], but the proofs of hardness still involved exhaustive enumerations.

Following the notations of [6, 21] we denote the number of crossings in a diagram $𝒟$ by $\mathrm{cr}(𝒟)$. For diagrams ${𝒟}_1$ and ${𝒟}_2$ of equivalent links, and a sequence $R$ of $r$ Reidemeister moves transforming ${𝒟}_1$ into ${𝒟}_2$, we define $\text{Top}\mathbf{(}{𝓓}_{\mathrm{𝟏}}\mathbf{,}𝑹\mathbf{)}$$={\max }_{i\in \{0,1,\mathrm{\dots },r\}}\{\mathrm{cr}({𝒟}^i)-\mathrm{cr}({𝒟}_1)\}$ where ${𝒟}^i$, $0\le i\le r$, is the diagram after performing the first $i$ moves of the sequence. The minimal number of extra crossings to pass from ${𝒟}_1$ to ${𝒟}_2$ is denoted by $\text{Add}\mathbf{(}{𝓓}_{\mathrm{𝟏}}\mathbf{,}{𝓓}_{\mathrm{𝟐}}\mathbf{)}$, which, formally, is the minimum of $\mathrm{Top}({𝒟}_1,R)$ taken over all sequences of Reidemeister moves $R$ transforming ${𝒟}_1$ into ${𝒟}_2$. Hence, $\mathrm{Add}({𝒟}_1,{𝒟}_2)$ is a lower bound on the number of crossings we must add in any sequence of Reidemeister moves performed on ${𝒟}_1$ to reach ${𝒟}_2$.

Let $𝒟$ be a diagram of the unknot and $\widehat{𝒟}$ be its $0$-crossing diagram. Naturally, $𝒟$ is a hard unknot diagram if and only if $\mathrm{Add}(𝒟,\widehat{𝒟})$ is positive. This measure of complexity is called $m$ in [6] (see also the recalcitrance in [21]). Studying these complexity measures and hard unknot diagrams is trickier than one might think. In fact, one of the purposes of [6] is to confirm or invalidate claims about previously known hard unknot diagrams using an exhaustive computer search over all possible sequences of Reidemeister moves. Still, the “hardest” known diagrams of the unknot have only been verified to require at least three extra crossings before they can be untangled. In contrast, the following conjecture is folklore.

Note that a proof of Conjecture 1, formulated in terms of recalcitrance, is claimed in [21], but concerns about the correctness of this proof are raised in [6].

In this article, as a possible step towards a proof of Conjecture 1, we shift our focus to split links. A link $L$ is said to be split if there exists a sphere disjoint from $L$ separating at least two link components of $L$. If such a sphere exists, there exists a link diagram in which two sublinks of $L$ are disjoint: they are separated by a circle in the plane. Such a diagram is called a split diagram. By capping off the aforementioned circle with one disc above and one disc below the plane of projection, we can verify that conversely a split diagram witnesses a split link. Determining if a link is split is known as the splitting problem.

Given a split link $L$ with a diagram ${𝒟}_1$, we study $\mathrm{Add}({𝒟}_1,{𝒟}_2)$ where ${𝒟}_2$ is a split diagram of $L$. If the minimum of $\mathrm{Add}({𝒟}_1,{𝒟}_2)$ over all split diagrams ${𝒟}_2$ of $L$, called the crossing-complexity and denoted by $\text{CC}(D_1)$, is positive, we call ${𝒟}_1$ a hard split link.

We work with the definitions of Section 2. We start with a sequence of Reidemeister moves $R$ turning $𝒟$ into ${𝒟}^{\prime }$, and consider the induced homotopy ${\varphi }_U$ of the link component $𝒰$ in the plane of projection. The goal of this section is to use results from [7] in order to locally alter the images ${𝒰}_t={\varphi }_U({𝕊}^1,t)$ into simple closed curves, and hence to obtain an isotopy taking ${𝒰}_0$ to ${𝒰}_1$. After these modifications, the altered simple closed curves representing $U$ still sweep over the remainder ${ℳ}_t$ of the diagrams ${𝒟}_t$, but this sweep no longer necessarily corresponds to a sequence of Reidemeister moves on the original link $L$.

Nevertheless, in the next section we use the isotopy from ${𝒰}_0$ to ${𝒰}_1$ to define a family of $2$-spheres in ${𝕊}^3$ sweeping through $M$. This setup then allows us to use bubble tangles to obstruct small values of $\mathrm{Top}(𝒟,R)$ in the initial sequence of Reidemeister moves $R$.

The key points of this process are given by the following statement.

We emphasise that in the second item of Proposition 6, we only consider the sublink $M$ in ${\mathrm{\Phi }}^{\prime }(M,t)$, and not the entire link. That is, the proposition provides an ambient isotopy for $M$ in ${ℝ}^3$ and an isotopy for $p(U)$ in ${ℝ}^2$, while preserving a bound on the total number of intersections of $p({\mathrm{\Phi }}^{\prime }(M,t))$ and $h({𝕊}^1,t)$ in the plane of projection. This proposition follows from the techniques of Chambers and Liokumovich developed in Chapter $2$ of [7], the proof is detailed in the full version of the article for completeness. We first state one of their main results.

The main result we use for the proof of Proposition 6 is given by the following statement.

Informally, we think of Definition 7 and Theorem 8 as follows. When a curve $\alpha$ self-intersects in the plane, each crossing point can be resolved in one of two ways by reconnecting the endpoints in a small ball around the crossing point, see Figure 6 on the right. When all the crossings have been resolved in some way and we obtain a simple closed curve ${\alpha }^{\prime }$, we say that ${\alpha }^{\prime }$ is a resolution of $\alpha$. The theorem states that if we have a homotopy $\gamma$ on a surface between two simple curves ${\gamma }_0$ and ${\gamma }_1$, one can obtain an isotopy $\overline{\gamma }$ between ${\gamma }_0$ and ${\gamma }_1$³³3Or ${\gamma }_1$ with its orientation reversed. Since it is safe to disregard orientations for our purpose, we always consider curves up to orientation reversal. where each intermediate curve $\overline{{\gamma }_t}$ is a resolution of some intermediate curve ${\gamma }_{t^{\prime }}$. Note that, here, the times $t$ and $t^{\prime }$ may not coincide.

If $M$ is endowed with a metric (for example, a Riemannian one), the lengths of ${\gamma }_t$ and of $\overline{{\gamma }_{t^{\prime }}}$ differ by an arbitrarily small quantity. Hence, Theorem 8 immediately implies that, for all $\epsilon >0$, if there exists a homotopy between two simple curves ${\gamma }_0$ and ${\gamma }_1$ where each intermediate curve has length at most $\mathrm{\ell }$, then there also exists an isotopy between ${\gamma }_0$ and ${\gamma }_1$ where each intermediate curve has length at most $\mathrm{\ell }+\epsilon$.

Theorem 8 can be applied as a black-box to prove Proposition 6 in the particular case where the sublink $M$ stays invariant throughout the sequence of Reidemeister moves $R$, i.e., ${\mathrm{\Phi }}_R(M,t)={\mathrm{\Phi }}_R(M,0)$ for all $t\in [0,1]$. Indeed, in this case, we can think of ${ℳ}_t$ as a discrete metric measuring the length of a curve ${𝒰}_t$ by its number of intersections with ${ℳ}_t$. More formally, we can take $\gamma$ to be the homotopy ${\varphi }_U$ between ${𝒰}_0$ and ${𝒰}_1$, which are both simple closed curves by the definition of the link diagram $𝒟$. Applying Theorem 8 provides us with an isotopy $h$ between ${𝒰}_0$ and ${𝒰}_1$ where all intermediate curves ${𝒰}_t^{\prime }$ are obtained from resolving intersections of some ${𝒰}_{t^{\prime }}$. In particular, for all $t\in [0,1]$, the number of intersections between ${𝒰}_t^{\prime }$ and ${ℳ}_t$ is at most the number of intersections between ${𝒰}_{t^{\prime }}$ and ${ℳ}_t$, which is at most $k$ since ${ℳ}_t={ℳ}_0$ does not depend on $t$.

A careful reading of [7] shows that the general case of Proposition 6, where the diagram ${ℳ}_t$ of the sublink $M$ evolves during the sequence of Reidemeister moves, can also be obtained using the same proof techniques: The basic idea of the proof of Theorem 8 is to first decompose the homotopy of $\gamma$ into a sequence of local moves, and then replace each curve ${\gamma }_t$ by one of its resolutions.

For the first step, they track discrete times where the self-intersection pattern (i.e., the homeomorphism type) of ${\gamma }_t$ changes. By an argument similar to the proof of the Reidemeister theorem, one can assume that this only happens at critical events, when a curve ${\gamma }_t$ undergoes a homotopy move, which is a transformation analogue to a Reidemeister move but without any crossing information. This step is formalised by their Proposition 2.1 and Lemma 2.2. Note that this step is unnecessary for us, since by construction the local transformations undergone by ${\varphi }_U$ are projections of Reidemeister moves.

Between these critical events, any homotopy of a curve ${\gamma }_t$ can be applied similarly to any of its resolutions, yielding an isotopy. Hence, the idea is to replace each of these Reidemeister moves by a resolution of the move, as explained by their Figure $2$. However, doing so in a naive way runs into discontinuity issues, a basic example of which is detailed in [7, Example 2], which is associated to their Figures $3$ and $4$. Therefore, the authors provide a more intricate workaround: the key to the proof of Theorem 8 is to show how to choose the correct resolutions and connect their isotopies together. This is achieved by defining an auxiliary graph of resolutions (see their Figure 7), synthesising how they are connected by local isotopies. The precise definition for this graph follows their Figure 8. The proof is then finalised by finding a path through this graph by using the handshaking lemma [13].

In our case, the critical events are exactly the times $t$ when ${𝒰}_t$ undergoes a Reidemeister move. In-between these critical events, there are other Reidemeister moves involving either (i) both ${𝒰}_t$ and ${ℳ}_t$, or (ii) only ${ℳ}_t$. Note that in case (i), the Reidemeister move only changes the relative position of ${𝒰}_t$ and ${ℳ}_t$, and hence such a move can be treated as leaving the isotopy type of ${ℳ}_t$ unchanged. Therefore the homotopy of ${𝒰}_t$ can be used as an isotopy of any of its resolutions in this case. In case (ii), ${ℳ}_t$ changes, but ${𝒰}_t$, considered up to isotopy, does not. Therefore, by applying the same Reidemeister moves to ${ℳ}_t$, any motion of ${𝒰}_t$ between critical events can be applied to any of its resolutions while preserving the number of intersections with ${ℳ}_t$. These motions can then be connected using the same handshaking argument as in the proof of Theorem 8. Summarising, the proof technique directly adapts to the case of an evolving metric, as long as these evolutions are applied appropriately throughout the new sequence of isotopies.

For the remainder of this article, we use Proposition 6 to assume that the homotopy ${\varphi }_U:{𝕊}^1\times [0,1]\to {ℝ}^2$ sweeping $U$ across $M$ is an isotopy. In other words, let $h$ be the isotopy of $𝒰$ in ${ℝ}^2$ and ${\mathrm{\Phi }}^{\prime }$ be the ambient isotopy of $M$ in ${𝕊}^3$ from Proposition 6, and for all $t\in [0,1]$, we replace ${\varphi }_U({𝕊}^1,t)$ by $h({𝕊}^1,t)={𝒰}_t$ which is a simple closed curve.