Hardness of Computation of Quantum Invariants on 3-Manifolds with Restricted Topology

An arc in a surface $\mathrm{\Sigma }$ is the image of a proper embedding of the interval in $\mathrm{\Sigma }$ (i.e., its endpoints lie both on $\partial \mathrm{\Sigma }$). Similarly, a simple closed curve is the image of a proper embedding $S^1\hookrightarrow \mathrm{\Sigma }$. We will often refer to a simple closed curve by only closed curve or just curve. A multicurve is a finite collection of disjoint properly embedded simple curves in $\mathrm{\Sigma }$. We denote by $\mathrm{\#}\gamma$ its number of connected components. Whenever possible, we distinguish simple curves from multicurves by using Greek letters to represent the latter.

A curve in the surface will be called essential if not homotopic to a point (or, equivalently, if it does not bound a disk on the surface), a puncture, or a boundary component. A multicurve is essential if all its components are essential. Unless otherwise stated, all curves and multicurves will be assumed essential.

We will often be interested not in a curve $s$, but in the equivalence classes of $s$ up to isotopies in ${\mathrm{\Sigma }}_g$, $[s]$. Being essential is preserved under isotopies, so we naturally extend the definition of essential curves to their isotopy classes. For two curves $s,t$ in some surface $\mathrm{\Sigma }$, their geometric intersection number is defined as the minimal number of their intersection points up to isotopy, that is $i(s,t)=\min \{|s^{\prime }\cap t^{\prime }|:s^{\prime }\in [s],t^{\prime }\in [t]\}$. Two curves in a surface ${\mathrm{\Sigma }}_g$ are isotopic if and only if they are (free) homotopic [18].

The curve graph of a closed surface ${\mathrm{\Sigma }}_g$, $C({\mathrm{\Sigma }}_g)$, is the graph whose vertices are isotopy classes of essential curves and any two vertices $[s]$ and $[t]$ are connected by an edge if and only if $i(s,t)=0$. The usual graph distance $d$ defines a metric on the vertices of $C({\mathrm{\Sigma }}_g)$ that is interpreted as $d([s],[t])=n$ implying the existence a sequence of essential curves $r_0,r_1,\mathrm{\dots },r_n$ with $r_0\in [s]$, $r_n\in [t]$, and $r_i\cap r_{i+1}=\mathrm{\varnothing }$ for . The definitions related to the curve graph can be naturally extended to curves by identifying the elements of an isotopy class to the same vertex; in particular, $d(r,s)=0$ is equivalent to $r$ and $s$ being isotopic.

We recall that for each surface ${\mathrm{\Sigma }}_g$, its mapping class group, $\mathrm{Mod}({\mathrm{\Sigma }}_g)$, is the group of orientation-preserving homeomorphisms ${\mathrm{\Sigma }}_g\to {\mathrm{\Sigma }}_g$ up to isotopies. Its canonical action on the surface conserves the geometric intersection number between curves [18], therefore acting isometrically on $(C({\mathrm{\Sigma }}_g),d)$ by the induced map $\varphi \cdot [s]={\varphi }_{\ast }([s])$. The mapping class groups always contain the (isotopy classes of) Dehn twists, homeomorphisms ${\tau }_s:{\mathrm{\Sigma }}_g\to {\mathrm{\Sigma }}_g$ defined by cutting off a local neighborhood of the (multi)curve $s$ of ${\mathrm{\Sigma }}_g$ and gluing it back with a $2\pi$ counterclockwise twist, determined by the orientation of the surface (Figure 1). In particular, for each $g\ge 2$, $\mathrm{Mod}({\mathrm{\Sigma }}_g)$ is generated as a group by (isotopy classes of) Dehn twists about the $3g-1$ recursively defined Lickorish curves in ${\mathrm{\Sigma }}_g$ (Figure 2) [32]. We can, consequently, always assume that an element of $\mathrm{Mod}({\mathrm{\Sigma }}_g)$ is of form $\varphi ={\tau }_{s_r}^{n_r}\circ \mathrm{\cdots }\circ {\tau }_{s_1}^{n_1}$, where $n_i\in \mathbb{Z}$ and $s_i$ are Lickorish curves for $1\le i\le r$.

An essential multicurve $\gamma \subset C({\mathrm{\Sigma }}_g)$ is a (full) system if no two components are isotopic to each other and ${\mathrm{\Sigma }}_g-\gamma$ is a union of $\mathrm{\#}\gamma -g+1$ punctured spheres (here the minus sign indicates cutting the surface along $\gamma$). The minimum number of connected components that a full system may have is $g$, in which case ${\mathrm{\Sigma }}_g-\gamma$ is a $2g$-punctured sphere and $\gamma$ is called a minimum system. On the other extreme, a system $\gamma$ is maximum or a pants decomposition when $\mathrm{\#}\gamma =3g-3$ and ${\mathrm{\Sigma }}_g-\gamma$ is the union of $2g-2$ thrice punctured spheres, also known as pairs of pants (see Figure 4). When every connected component of a system $\gamma$ is isotopic to a connected component of another system ${\gamma }^{\prime }$, we say that $\gamma$ is contained in ${\gamma }^{\prime }$ and denote that by $\gamma \subseteq {\gamma }^{\prime }$. A minimum system $\gamma$ can always be extended to a pants decomposition $\rho \supseteq \gamma$, see Theorem 16.

The genus $g$ handlebody defined for a full system $\gamma$ in the surface ${\mathrm{\Sigma }}_g$ is the 3-manifold

built by attaching the 2-handles along the curves $\gamma$ in $\mathrm{\Sigma }\times \{0\}$ and then filling any resulting $S^2$ boundary component with 3-handles. By construction $\partial V_{\gamma }={\mathrm{\Sigma }}_g$. Because the curves in the system $\gamma$ are assumed to be essential, each of its components will bound (non-trivial) compression disks in $V_{\gamma }$: they will be meridians of the handlebody. There are, however, many other meridians in $V_{\gamma }$, as it will be implied by the following definition.

Note that $\gamma$ is equivalent to ${\gamma }^{\prime }$ if and only if they define the same handlebody. In particular, if $\gamma \subset \rho$, $\gamma$ and $\rho$ are equivalent.

In a seminal work, Hempel [22] studied the metric $d$ of the disk graph canonically inherited from $C({\mathrm{\Sigma }}_g)$. This inspires the next definition. Here and throughout, whenever $A,B\subset C(\mathrm{\Sigma })$ and $r$ is a curve in $\mathrm{\Sigma }$, we let $d(r,A)=\min \{d(r,s):s\in A\}$ and $d(A,B)=\min \{d(s,t):s\in A,t\in B\}$. We assume a curve $s$ on a handlebody $V_{\gamma }$ to be fully contained in $\partial V_{\gamma }$.

[52] provides a combinatorial condition to verify if a curve on a handlebody is diskbusting, which we quote using the language of [56]. Before, however, we will need a definition.

A closed 3-manifold $M$ is said to have a Heegaard splitting if it is the union of two handlebodies intersecting only at their common boundary. It is well-known [45] that there exists, for every closed 3-manifold $M$, a tuple $({\mathrm{\Sigma }}_g,\alpha ,\beta )$ called a Heegaard diagram (of genus $g$), where $\alpha$ and $\beta$ are two full systems with the same cardinality in ${\mathrm{\Sigma }}_g$, and a Heegaard splitting $M=V_{\alpha }{\cup }_{{\mathrm{\Sigma }}_g}{V}_{\beta }$. Note, on the other hand, that neither the Heegaard diagram nor the splitting is unique: for example, isotopies to $\alpha$ or $\beta$ yield the same splitting, whereas given a diagram $({\mathrm{\Sigma }}_g,\alpha ,\beta )$, one can define another splitting for the same manifold, this time of diagram $({\mathrm{\Sigma }}_{g+1},\alpha \cup \{c\},\beta \cup \{c^{\prime }\})$, where $c$ and $c^{\prime }$ are curves with $i(c,c^{\prime })=1$ fully contained in the extra handle. This last process, known as stabilization, is topologically equivalent to directly summing a copy of $S^3$ to the original manifold $M$.

Some properties of 3-manifolds can be read straight-up from their Heegaard splittings. For example, a splitting $({\mathrm{\Sigma }}_g,\alpha ,\beta )$ is called irreducible if $V_{\alpha }$ and $V_{\beta }$ do not share a meridian. Haken’s lemma [49, Theorem 6.3.5] implies that reducible closed 3-manifolds cannot have irreducible Heegaard splittings. Similarly, a splitting $({\mathrm{\Sigma }}_g,\alpha ,\beta )$ is strongly irreducible if there are no two essential disjoint curves $a$ and $b$ in ${\mathrm{\Sigma }}_g$ such that $a$ is a meridian of $V_{\alpha }$ and $b$ is a meridian of $V_{\beta }$. Every strongly irreducible splitting is irreducible, but the converse is not true (Haken manifolds provide a list of counterexamples [49]).

Given two handlebodies $V_{\alpha }$ and $V_{\beta }$, we define their Hempel distance by $d(K_{\alpha },K_{\beta })$. In [22], Hempel argued that this distance could be seen as a measure of the complexity of a Heegaard splitting $V_{\alpha }{\bigsqcup }_{{\mathrm{\Sigma }}_g}{V}_{\beta }$, which is translated into the following theorem, whose proof (a simple application of results by others) can be found in the full version of the paper.

Our proof of Theorem 1 will mainly consist of increasing the Hempel distance so that the hypotheses of Theorem 7 are satisfied. For such, we will extensively use the next two theorems due to Yoshizawa.

We will not review the technical construction of TQFTs here, referring the interested reader to [53]. For our purposes, it is enough to know that, for a fixed choice of modular category $𝒞$ (again, refer to [53] for the definition), the TQFT associates to every closed 3-manifold $M$ a complex scalar known as its Reshetikhin-Turaev (RT) invariant. The RT invariant can be given as a function of a Heegaard diagram $({\mathrm{\Sigma }}_g,\alpha ,\beta )$ of $M$ and is denoted by ${⟨M⟩}_{𝒞}^{RT}$ or ${⟨({\mathrm{\Sigma }}_g,\alpha ,\beta )⟩}_{𝒞}^{RT}$, depending on whether we want to emphasize the manifold or the diagram.

The algebraic structure imposed by the modular category sets some constraints on the quantum invariants. The next theorem, for example, is already somewhat folklore in the literature (see [41]) since it implies that non-homeomorphic 3-manifolds may share RT invariants. It can be deduced from Theorem 5.1 of [16] and [43, 53].

For a fixed modular category, we call the integer $N$ the category’s Vafa’s constant.

An embedded graph $G=(V,E)$ in a surface $\mathrm{\Sigma }$ defines a cellular complex for $\mathrm{\Sigma }$ if $\mathrm{\Sigma }-G$ is a union of open disks, which we call faces. Note that this implies that any boundary component of $\mathrm{\Sigma }$ fully lies within some set of edges in $E$. The dual graph of $G$ is another graph embedded in $\mathrm{\Sigma }$ defined by assigning a vertex to each face of $\mathrm{\Sigma }-G$ and an edge between the vertices if and only if the corresponding faces are separated by an edge in $E$. As a data structure, we represent a cellular embedding by the lists of faces, their incident edges, and vertices, allowing us to reconstruct $\mathrm{\Sigma }$ by gluing the appropriate pieces. Using this structure, one can compute the dual graph of the cellular embedding in linear time on the number of faces.

A (generalized) triangulation $T=(V,E)$ of a surface $\mathrm{\Sigma }$ is a cellular complex where all faces are bounded by exactly 3 edges. We denote the number of triangles in a triangulation by $|T|$; note that $|T|=O(|E|)$. We will most often consider oriented triangulations by giving an orientation to each triangle consistent with the orientation of the surface; we orient a triangle by imposing an order to its vertices as in the right-hand rule. We say that a triangulation $T^{\prime }$ of a surface $\mathrm{\Sigma }$ is a subtriangulation of another triangulation $T$ of $\mathrm{\Sigma }$, denoting $T\le T^{\prime }$, if the graph of $T$ is embedded on $T^{\prime }$ (i.e., each vertex of $T$ is a vertex of $T^{\prime }$ and each edge of $T$ is a union of edges in $T^{\prime }$). ’If $T$ and $T^{\prime }$ are oriented, we also require the induced order of the vertices to be the same. Every face of $T^{\prime }$ is naturally contained in a face of $T$.

Using a triangulation $T=(V,E)$ of a surface $\mathrm{\Sigma }$, we can describe an arc, curve, or multicurve $s$ in $\mathrm{\Sigma }$ lying fully within the edges $E$ by the list of the edges in $E\cap s$ (the red curve in Figure 3). We will call this list an edge list representation of the curve $s$, denote it by $E_T(s)$, and say that the number of edges in $E\cap s$ is the edge complexity, $\Vert E_T(s)\Vert$. We can always assume that $\Vert E_T(s)\Vert \le |T|$.

For any fixed triangulation $T$ of the surface $\mathrm{\Sigma }$, there are always, however, isotopy classes of curves in $\mathrm{\Sigma }$ not representable as a subset of edges of $T$. To deal with this hindrance, we say, for a fixed oriented triangulation $T=(V,E)$ of the surface $\mathrm{\Sigma }$, that a curve $s$ is standard (to $T$) if it intersects $T$ only transversely and at edges (green curve of Figure 3). If $s$ is standard, we may represent it as an intersection word $I_T(s)$, taking $E$ as an alphabet and traversing $s$ along some arbitrary direction and, whenever we meet an edge $e\in E$, we append $e$ to $I_T(s)$ if $e$ is crossed according to the orientation of $\mathrm{\Sigma }$ and $e^{-1}$ otherwise. While the edge representation is well-defined at the curve level, intersection words are defined only up to isotopies inside the triangulation’s faces. Furthermore, isotopy classes of $I_T(s)$ are closed under cyclic permutations and taking inverses. The complexity of an intersection word $I_T(s)$, $\Vert I_T(s)\Vert$, is its length (i.e., the number of edges of $T$ intersected by $s$, counted with multiplicity). If $\gamma$ is a multicurve, we let $I_T(\gamma )$ be the set of $\mathrm{\#}\gamma$ intersection words representing each component. Similarly, the complexity of a Heegaard diagram $({\mathrm{\Sigma }}_g,\alpha ,\beta )$, where $\alpha$ and $\beta$ are standard multicurves, equals $\Vert I_T(\alpha )\Vert +\Vert I_T(\beta )\Vert$. Standard arcs are treated accordingly.

A standard curve, multicurve or arc $s$ is normal if no intersection word $I_T(s)$ contains a substring of form $e{e}^{-1}$ or $e^{-1}e$ where $e\in E$ (the blue curve in Figure 3). When normal, the intersections of $s$ and the faces of the triangulation are arcs connecting distinct edges of each triangle, which we call fundamental arcs. Normal curves are more convenient for tracing than their more general standard counterparts (refer to Proposition 14); moreover, any standard curve $s$ can be made normal in time $O(\Vert I_T(s)\Vert )$, see the proof of Theorem 15.

In Section 2.4, we saw two representations of curves in a surface: edge lists and intersection words. While some topological operations such as cutting along a curve are easier to implement using edge list representations (one needs only to delete the edges crossing $E_T(s)$ from the dual graph of $T$ to cut along $s$), others, such as doing Dehn twists (Theorem 15) are more suited to curves intersecting the triangulation transversely. Therefore, it will be convenient to have procedures to convert from one representation to the other.

First, we describe an algorithm to transform curves represented by edge lists into intersection words. For an edge list $E_T(s)$ not in a boundary of an oriented surface $\mathrm{\Sigma }$, there are two choices of normal curves isotopic to $s$ created by slightly displacing it either to the left or to the right of the edges (with respect to the orientation of $\mathrm{\Sigma }$ and some arbitrary orientation of $s$); we call them twins born from $s$. Given a choice of twin for $s$, say left, one can compute its intersection word by traversing $s$ and appending the letters representing adjacent edges coming from the left side of the triangulation graph when embedded in $\mathrm{\Sigma }$. If, however, $s$ lies either partially or fully on the boundary of $\mathrm{\Sigma }$, we can only consistently displace it to one side, which can be determined in time $O(\Vert E_T(s)\Vert )$. This algorithm does not change the triangulation. For convenience, we state this argument as the following proposition.

The next result, whose proof is in the paper’s full version, describes an algorithm for the other direction, that is, for going from an intersection word to an edge list representation.

Before proceeding with the main results, we will establish algorithms for some basic operations. The first of these is only a minor modification of [47], whereas the second, in the context of curves in surfaces, is mostly due to [55, Theorem 7.1]. The proofs of both theorems are in the paper’s full version.

For every Heegaard diagram $({\mathrm{\Sigma }}_g,\alpha ,\beta )$, there is an orientation-preserving homeomorphism $\varphi :{\mathrm{\Sigma }}_g\to {\mathrm{\Sigma }}_g$ such that $\beta =\varphi (\alpha )$ [18, 56]. A lthough not unique, this map is well-defined on $\mathrm{Mod}({\mathrm{\Sigma }}_g)$, so it can be described by a word on Lickorish generators. We do not differentiate between the notation of the homomorphism $\varphi$ from its equivalence class in $\mathrm{Mod}({\mathrm{\Sigma }}_g)$.

Before applying Theorem 1 to this result, we need to find an algorithm to convert the pair $({\mathrm{\Sigma }}_g,\varphi )$ into a proper Heegaard diagram $({\mathrm{\Sigma }}_g,\beta )$. This cannot be done through brute force computing $\beta =\varphi (\alpha )$, since, as we saw in the proof of Proposition 20, it can lead to exponential bottlenecks. We fix the problem with the following lemma at the cost of potentially increasing the value of $g$. The proof of the next, as well as all other results of this section (except for Corollary 25), is found in the paper’s full version.

A compact 3-manifold can also be combinatorially described by a set of tetrahedra $𝒯$, together with rules on how to glue their triangular faces [10, 40]. This description is called a triangulation of the 3-manifold, but it should not be confused with triangulations of surfaces. Nonetheless, if $M$ has a boundary, $𝒯$ naturally defines a (surface) triangulation for $\partial M$. For each $g\ge 1$, there exists a one-vertex triangulation of the handlebody of genus $g$ [27].

The Turaev-Viro invariant (TV) is another quantum invariant for closed 3-manifolds. It is defined for spherical categories (which include modular categories) and is computed directly from a triangulation [7]. The Turaev-Walker theorem [53] states that, given a manifold $M$, ${|{⟨M⟩}_{𝒞}^{RT}|}^2={⟨M⟩}_{𝒞}^{TV}$, provided $𝒞$ is a modular category. We show that an approximation of the $S{O}_r(3)$-TV invariant can be used to compute an approximation of $S{O}_r(3)$-RT [3]. For such, we use the next theorem due to [21].