A Polynomial-Time Algorithm to Compute Turaev–Viro Invariants $\mathrm {TV}_{4,q}$ of 3-Manifolds with Bounded First Betti Number

Abstract

In this article, we introduce a fixed-parameter tractable algorithm for computing the Turaev–Viro invariants $\mathrm {TV}_{4,q}$, using the first Betti number, i.e. the dimension of the first homology group of the manifold with $\mathbb {Z}_2$-coefficients, as parameter. This is, to our knowledge, the first parameterised algorithm in computational 3-manifold topology using a topological parameter. The computation of $\mathrm {TV}_{4,q}$ is known to be #P-hard in general; using a topological parameter provides an algorithm polynomial in the size of the input triangulation for the family of 3-manifolds with first $\mathbb {Z}_2$-homology group of bounded dimension. Our algorithm is easy to implement, and running times are comparable with running times to compute integral homology groups for standard libraries of triangulated 3-manifolds. The invariants we can compute this way are powerful: in combination with integral homology and using standard data sets, we are able to almost double the pairs of 3-manifolds we can distinguish. We hope this qualifies $\mathrm {TV}_{4,q}$ to be added to the short list of standard properties (such as orientability, connectedness and Betti numbers) that can be computed ad hoc when first investigating an unknown triangulation.

1 Introduction

In geometric topology, topological invariants are properties of manifolds telling some (but typically not all) pairs of non-homoeomorphic manifolds apart. Invariants are important, since deciding whether two manifolds are topologically equivalent—the so-called homeomorphism problem—is remarkably complicated to solve in dimension three [20], and undecidable in dimensions four and higher [26, 36]. Topological invariants help to settle this potentially unsolvable, yet fundamentally important problem in many, albeit not all cases.

This article focuses on the special case of three-dimensional manifolds, where the homeomorphism problem is mathematically settled [20, 31], but continues to withstand practical computations in general. More precisely, in this article we focus on the family of Turaev–Viro invariants $\mathrm {TV}_{r,q}$, parameterised by integers r and q (where $3 \le r$, $0< q < 2r$, and $(q,r)=1$), which are amongst the most powerful invariants for 3-manifolds [38, 39]. The Turaev–Viro invariants are numerical invariants. Similarly to the Jones polynomial for knots, they stem from topological quantum field theory and can be computed by purely combinatorial means. For a broad and detailed treatment of quantum invariants of knots and 3-manifolds, we refer to the monograph [38].

Algorithms to compute these invariants are implemented for 3-manifolds represented by triangulations (see the software package Regina [6]) and special spines (see the software Manifold Recogniser [28, 29]), and they play a key role in enumerating 3-manifolds of bounded topological complexity (an analogue to the famous knot tables) [3, 28].

Existing algorithms and complexity Turaev–Viro invariants are defined as exponentially large state sums over combinatorial data—the so-called admissible colourings—defined on the edges and triangles of a triangulated 3-manifold. A naive algorithm to compute the state sums consists of enumerating all admissible colourings of the triangulation and sums up their weights. This algorithm runs in exponential time, but only consumes a polynomial amount of memory.

Recently, new algorithms and techniques have been introduced to improve performance. In [7], Burton and the authors introduce a fixed-parameter tractable algorithm for computing Turaev–Viro invariant $\mathrm {TV}_{r,q}$ for any admissible choice of r and q, using the treewidth of the dual graph of the triangulation as parameter. Both the naive and the fixed-parameter tractable (FPT) algorithms can be improved further by pruning the search space for admissible colourings for some of the Turaev–Viro invariants [23]. While significantly improving both the practical and theoretical complexity of the computation, both versions of the fixed-parameter algorithms are exponential in both time and space complexity.

Our contribution In this article, we focus on the case $r=4$, which is of particular interest for complexity theory: $\mathrm {TV}_{4,q}$ is known to be #P-hard to compute for 3-manifold triangulations. (This follows from [19], as explained in [7].) We introduce a fixed-parameter tractable algorithm to compute $\mathrm {TV}_{4,q}$ on a triangulation $\mathfrak {T}$ of a 3-manifold $M$, using the first $\mathbb {Z}_2$-Betti number, i.e. the dimension of the first homology group of $M$ with $\mathbb {Z}_2$-coefficients, as parameter for the algorithm:

Theorem 1

Let $\mathfrak {T}$ be a one-vertex,¹n-tetrahedra triangulation of a 3-manifold $M$ with first Betti number $\beta _1 (M,\mathbb {Z}_2)$. Then, there exists an algorithm to compute $\mathrm {TV}_{4,q}$ of $M$ with running time $O(2^{\beta _1 (M, \mathbb {Z}_2)} n^3)$, $O(n^2)$ space requirement, and with at most $2^{\beta _1 (M, \mathbb {Z}_2)}$ cyclotomic field operations.

The algorithm interprets $\mathrm {TV}_{4,q}$ as a sum over the weights of a family of embedded normal surfaces of the triangulation. We show that each of these surfaces can be assigned a 1-cohomology class $\theta \in H^1 (\mathfrak {T}, \mathbb {Z}_2)$ which determines its weight, up to a sign. We show that, for each such $\theta$, the set of surfaces associated with $\theta$ (with all of its members necessarily having the same weight, up to a sign) can be efficiently described as the solution space of a linear system of size O(n). The sign of the weight of a fixed surface in this space is determined by the parity of the number of certain surface pieces (octagons, or the so-called almost normal surface pieces). We show that the number of surfaces in the solution space with a fixed parity equals the number of zeroes of a quadratic form over $\mathbb {Z}_2$ on this space. Following the theory of quadratic forms over $\mathbb {Z}_2$, this quadratic form can be transformed into standard form yielding its number of zeroes. This is all we need to compute the sum of weights over all surfaces corresponding to $\theta$ in polynomial time. Summing over all 1-cohomology classes concludes the algorithm.

Discussion of the parameter As mentioned above, the state-of-the-art algorithm to compute $\mathrm {TV}_{r,q}$ is fixed-parameter tractable in the treewidth of the dual graph of the triangulation. It is obtained using standard techniques from parameterised complexity.

The fixed-parameter tractable algorithm introduced in this article uses a topological parameter and requires a non-standard topological and combinatorial interpretation of the Turaev–Viro invariant $\mathrm {TV}_{4,q}$. The use of the first Betti number as parameter has several significant advantages over the use of a graph theoretical parameter such as treewidth:

• The parameter is topological Treewidth is a combinatorial property of the triangulation in use. This means that even triangulations of very simple manifolds, such as the 3-sphere or other lens spaces, can be represented by an input triangulation of arbitrarily high treewidth. The first Betti number is a topological invariant of the underlying manifold and thus independent of the choice of triangulation. Eliminating such a dependence on the combinatorial structure of a triangulation is highly desirable in the field of computational topology.

  Having a topological parameter means, in particular, that the problem of computing $\mathrm {TV}_{4,q} (M)$, for a fixed 3-manifold $M$, becomes polynomial-time solvable.

  To our knowledge, this is the first non-trivial fixed-parameter tractable algorithm of a problem in 3-manifold topology using a topological parameter. Note that, for algorithmic problems dealing with surfaces, similar results exist. For instance, graph embeddability is known to be fixed-parameter tractable in the genus of the surface [30].

• The parameter is efficiently computable Given a graph, computing its treewidth is NP-complete [1]. The problem is known to be fixed-parameter tractable in the natural parameter [2], but in practice this algorithm is not the method of choice. Thus, in practice, it can be difficult to decide whether a given triangulation has a small treewidth. In contrast, computing the first $\mathbb {Z}_2$-Betti number of a triangulation amounts to solving a linear system of roughly the size of the triangulation (see for example [9, Chapter IV]). Hence, the running time of this procedure is a small polynomial, regardless of the size of the Betti number.

• Small treewidth is rare Bounded treewidth is a condition which is closed under minors. It thus follows from standard results in forbidden minor theory and the theory of triangulations that, for a given number of tetrahedra n, the number of triangulations of bounded treewidth is bounded from above by a singly exponential function; see [32]. On the other hand, the number of 3-manifolds which can be triangulated with $\le n$ tetrahedra grows super-exponentially fast in n. Thus, most 3-manifolds only have few small triangulations with small treewidth. This is despite recent results showing that many standard families of closed 3-manifolds are known to have small triangulations of (very) small treewidth [15, 22].

• Small treewidth cannot always be obtained In recent work, Huszár and Wagner, together with the second author, show that some 3-manifolds do not admit triangulations of small treewidth at all [16]. More precisely, they show that for every $k \in \mathbb {N}$ there exists a 3-manifold $M$ such that all triangulations $\mathfrak {T}$ of $M$ must have treewidth at least k.

  See also work by de Mesmay, Purcell, Schleimer and Sedgwick [34] for a similar result about the treewidth of knot diagrams.

There are a number of further advantages of the new algorithm over previous algorithms. Most notably, while the space requirements of the treewidth algorithm are exponential in the parameter (an actual bottleneck for practical computations), our algorithm only uses quadratic space in the input size, regardless of the size of the parameter. Moreover, our algorithm uses no more than $2^{\beta _1 (M, \mathbb {Z}_2)}$ cyclotomic field operations, which are necessary for exact computation of the Turaev–Viro invariants. Considering that cyclotomic field operations for computing $\mathrm {TV}_{4,q}$ are computable in constant time, this fact is of little to no theoretical importance. However, its practical impact on running times is significant.

Structure of the article The paper is organised as follows. After going over some important concepts used in the article, we describe the FPT algorithm for $\mathrm {TV}_{4,q}$ in three steps. In Sect. 3, we start by describing embedded surfaces defined by admissible colourings and show that their weights can be interpreted as a function of their topological and combinatorial properties. In doing so, we split the sum of weights defining $\mathrm {TV}_{4,q} (M)$ for a triangulation $\mathfrak {T}$ of $M$ by grouping colourings according to associated 1-cohomology classes. In Sect. 4.1, we introduce a polynomial-time algorithm to compute the weight participation of a set of colourings assigned to a given 1-cohomology class. In Sect. 4.2, the FPT algorithm is deduced by essentially running this procedure on all of the $2^{\beta _1 (M,\mathbb {Z}_2)}$ cohomology classes. In Sect. 5, we discuss implications of the algorithm from a complexity theoretic point of view. Recall that $\mathrm {TV}_{4,q}$ is known to be #P-hard due to work by Kirby and Melvin [19] and a slight adjustment by Burton and the authors [7]. Using the structure of our algorithm, we show that $\mathrm {TV}_{4,q}$ is not harder than counting, thus further bounding the complexity of computing $\mathrm {TV}_{4,q}$ from above. In Sect. 6, we focus on the benefits of the new algorithm for research in computational topology—which strongly depend on the power of $\mathrm {TV}_{4,q}$ to distinguish between manifolds with equal homology. We provide theoretical and experimental evidence that our algorithm, in combination with integral homology,² provides an efficient tool to distinguish between almost twice as many manifolds as integral homology on its own.

2 Background

Manifolds and generalised triangulations Throughout this article, closed 3-manifolds are given in the widely used form of generalised triangulations. Generalised triangulations are more general than simplicial complexes and can encode a wide range of manifolds with very few tetrahedra.

More precisely, a generalised triangulation $\mathfrak {T}$ of a (closed) 3-manifold $M$ is a collection of n abstract tetrahedra $T = \{ \Delta _1,\ldots ,\Delta _n \}$ together with 2n gluing maps identifying their 4n triangular faces in pairs, such that the underlying topological space is homoeomorphic to $M$. An equivalence class of vertices, edges, or triangles of $\Delta _i$, $1 \le i \le n$, identified under the gluing maps, is referred to as a single vertex, edge, or triangle of $\mathfrak {T}$. We denote by V, E, and F the sets of such vertices, edges, and triangles, respectively, of $\mathfrak {T}$. It is common in practical applications to have one-vertex triangulations where all 4n vertices of $\Delta _i$, $1 \le i \le n$, are identified to one point. The number of tetrahedra n of $\mathfrak {T}$ is often referred to as the size of the triangulation.

Since, by construction, every n-tetrahedra v-vertex closed 3-manifold triangulation $\mathfrak {T}$ must have 2n triangles, and every closed 3-manifold has Euler characteristic zero, it follows that $\mathfrak {T}$ must have $n+v$ edges.

We refer the reader to [17] for more details on generalised triangulations.

Homology, cohomology and Betti numbers Let $\mathfrak {T}$ be a generalised triangulation of a 3-manifold $M$. For the ring of coefficients $\mathbb {Z}_2 := \mathbb {Z}/ 2\mathbb {Z}$, the group of p-chains, $0 \le p \le 3$, denoted $\mathbf {C}_p(\mathfrak {T},\mathbb {Z}_2)$, of $\mathfrak {T}$ is the group of formal sums of p-dimensional faces with $\mathbb {Z}_2$ coefficients. The boundary operator is a linear operator $\partial _p: \mathbf {C}_p(\mathfrak {T},\mathbb {Z}_2) \rightarrow \mathbf {C}_{p-1}(\mathfrak {T},\mathbb {Z}_2)$ such that $\partial _p \sigma = \partial _p \{v_0, \ldots , v_p\} = \sum _{j=0}^p \{v_0,\ldots ,\widehat{v_j}, \ldots ,v_p\}$, where $\sigma$ is a face of $\mathfrak {T}$, $\{v_0, \ldots , v_p\}$ represents $\sigma$ as a face of a tetrahedron of $\mathfrak {T}$ in local vertices $v_0, \ldots , v_p$, and $\widehat{v_j}$ means $v_j$ is deleted from the list. Denote by $\mathbf {Z}_p(\mathfrak {T},\mathbb {Z}_2)$ and $\mathbf {B}_{p-1}(\mathfrak {T},\mathbb {Z}_2)$ the kernel and the image of $\partial _p$, respectively. Observing $\partial _p \circ \partial _{p+1}=0$, we define the pth homology group $\mathbf {H}_p(\mathfrak {T},\mathbb {Z}_2)$ of $\mathfrak {T}$ by the quotient $\mathbf {H}_p(\mathfrak {T},\mathbb {Z}_2) = \mathbf {Z}_p(\mathfrak {T},\mathbb {Z}_2)/ \mathbf {B}_p(\mathfrak {T},\mathbb {Z}_2)$. $\mathbf {H}_p$ is a topological invariant of the manifold $M$ triangulated by $\mathfrak {T}$.

The concept of cohomology is in many ways dual to homology, but endowed with more algebraic structure. It is defined in the following way: the group of p-cochains $\mathbf {C}^p(\mathfrak {T},\mathbb {Z}_2)$ is the formal sum of linear maps of p-dimensional faces of $\mathfrak {T}$ into $\mathbb {Z}_2$. The coboundary operator is a linear operator $\delta ^p: \mathbf {C}^{p-1}(\mathfrak {T},\mathbb {Z}_2) \rightarrow \mathbf {C}^{p}(\mathfrak {T},\mathbb {Z}_2)$ such that for all $\phi \in \mathbf {C}^{p-1}(\mathfrak {T},\mathbb {Z}_2)$ we have $\delta ^p (\phi ) = \phi \circ \partial _p$. As above, p-cocycles are the elements in the kernel of $\delta ^{p+1}$, p-coboundaries are elements in the image of $\delta ^{p}$, and the pth cohomology group $\mathbf {H}^p(\mathfrak {T},\mathbb {Z}_2)$ is defined as the p-cocycles factored by the p-coboundaries.

The exact correspondence between elements of homology and cohomology is best illustrated by Poincaré duality stating that for closed d-manifold triangulations $\mathfrak {T}$, $\mathbf {H}^p(\mathfrak {T},\mathbb {Z}_2)$ and $\mathbf {H}_{d-p}(\mathfrak {T},\mathbb {Z}_2)$ are dual as vector spaces.

For instance, let S be a 2-cycle in $\mathfrak {T}$ representing a class in $\mathbf {H}_{2}(\mathfrak {T},\mathbb {Z}_2)$. We can perturb S such that it contains no vertex of $\mathfrak {T}$ and intersects every tetrahedron of $\mathfrak {T}$ in a single triangle (separating one vertex from the other three) or a single quadrilateral (separating pairs of vertices). It follows that every edge of $\mathfrak {T}$ intersects S in zero or one points. Then, the 1-cochain defined by mapping every edge intersecting S to 1 and mapping all other edges to 0 represents the Poincaré dual of S in $\mathbf {H}^1(\mathfrak {T},\mathbb {Z}_2)$. We use this exact duality to switch between admissible colourings in $\mathrm {Adm}(\mathfrak {T},3)$ and surfaces defined by these colourings (see Sect. 3).

For an arbitrary ring of coefficients R, if R is a field (e.g. as above), homology groups are R-vector spaces, otherwise they are R-modules. If the ring of coefficients is equal to the integers, we refer to them as integral homology groups. For each finite field $\mathbb {F}$, integral homology groups determine homology groups with coefficients in $\mathbb {F}$ by virtue of the universal coefficient theorem [12]. Hence, as a topological invariant they are at least as powerful as homology with coefficients in $\mathbb {F}$.

We refer the reader to [12, 13] or [9] for more details on homology and cohomology.

Turaev–Viro invariants Here, we introduce the Turaev–Viro invariants $\mathrm {TV}_{r,q}$ parameterised by two integers r and q. To this end, let $\mathfrak {T}$ be a generalised triangulation of a closed 3-manifold $M$, fix an integer $r \ge 3$ (the other parameter q will be considered later), and let $I = \{0, 1/2, 1, 3/2, \ldots , (r-2)/2\}$. A colouring of $\mathfrak {T}$ is defined to be a map $\theta :E \rightarrow I$ from the edges of $\mathfrak {T}$ to I. A colouring $\theta$ is admissible if, for each triangle of $\mathfrak {T}$, the three edges $e_1$, $e_2$ and $e_3$ bounding the triangle satisfy the

• parity condition $\theta (e_1)+\theta (e_2)+\theta (e_3)\in \mathbb {Z}$;

• triangle inequalities $\theta (e_i) \le \theta (e_j) + \theta (e_k)$, $\{i,j,k\} = \{ 1,2,3\}$; and

• upper bound constraint $\theta (e_1)+\theta (e_2)+\theta (e_3)\le r-2$.

The set of such admissible colourings is denoted by $\mathrm {Adm}(\mathfrak {T},r)$.

For each admissible colouring $\theta$, and for each vertex $w \in V$, edge $e \in E$, triangle $f \in F$, or tetrahedron $t \in T$, we define weights $|w|_{\theta }, |e|_{\theta }, |f|_{\theta }, |t|_{\theta } \in \mathbb {C}$. The weights of vertices are constant, and the weights of edges, triangles and tetrahedra only depend on the colours of edges they are incident to. Using these weights, we define the weight of the colouring to be

$$\begin{aligned} |\mathfrak {T}|_{\theta } = \prod _{w \in V} |w|_{\theta } \times \prod _{e \in E} |e|_{\theta } \times \prod _{f \in F} |f|_{\theta } \times \prod _{t \in T} |t|_{\theta }, \end{aligned}$$

(1)

Invariants of Turaev–Viro type Turaev and Viro [39] show that, whenever the weighting system described above satisfies some identities, the state sum $\mathrm {TV}_{r}(\mathfrak {T}) = \sum _{\theta \in \mathrm {Adm}(\mathfrak {T},r)} |\mathfrak {T}|_{\theta }$ is a topological invariant of $M$; that is, if $\mathfrak {T}$ and $\mathfrak {T}'$ are generalised triangulations of the same closed 3-manifold $M$, then $\mathrm {TV}_{r}(\mathfrak {T}) = \mathrm {TV}_{r}(\mathfrak {T}')$. We thus mostly write $\mathrm {TV}_r (M)$ and omit the triangulation $\mathfrak {T}$ of $M$ which was used to compute this number.

Below, we invoke the second parameter q, $0< q < 2r$ co-prime to r, to specify the weights in the case of the original Turaev–Viro invariants $\mathrm {TV}_{r,q}$, which we use in this article.

We continue to write $| \cdot |_{\theta }$ for the weights where r and/or q are given from context or the statement holds in more generality.

For an n-tetrahedra triangulation $\mathfrak {T}$ of $M$ with v vertices, there is a simple backtracking algorithm to compute $\mathrm {TV}_{r,q}(M)$ by testing the $(r-1)^{v+n}$ possible colourings for admissibility and computing their weights. The case $r=3$ can, however, be computed in polynomial time, due to a connection between $\mathrm {Adm}(\mathfrak {T},3)$ and cohomology; see [7, 28]. The case $r=4$, which we study in this article, is #P-hard to compute in general [7, 19].

Weight formulas for Turaev–Viro invariants We introduce the weight formulas for the original Turaev–Viro invariants $\mathrm {TV}_{r,q}$ defined in [39]. For this, let r and q be two integers, such that $r \ge 3$ and $0< q < 2r$, with $\gcd (r,q) = 1$.

Our notation differs slightly from Turaev and Viro [39].³ Our choice simplifies the notation and avoids unnecessary (but harmless) ambiguities when taking square roots.

Let $\zeta = e^{i \pi q / r} \in \mathbb {C}$. The conditions on r and q imply that $\zeta$ is a (2r)th root of unity, and that $\zeta ^2$ is a primitive rth root of unity; that is, $(\zeta ^2)^k \ne 1$ for $k=1,\ldots ,r-1$. For each positive integer $\iota$, we define the quantum integer $[\iota ] = (\zeta ^\iota -\zeta ^{-\iota })/(\zeta -\zeta ^{-1})$ and, as a special case, $[0] = 1$. We next define the “bracket factorial” $[\iota ]! = [\iota ]\,[\iota -1] \ldots [0]$. Note that $[r] = 0$, and thus $[\iota ]! = 0$ for all $\iota \ge r$.

We give every vertex constant weight

$$\begin{aligned} |v|_\theta = \frac{\left| \zeta -\zeta ^{-1}\right| ^2}{2r} , \end{aligned}$$

and to each edge e of colour $i \in I$ (i.e. for which $\theta (e) = i$) we give the weight

$$\begin{aligned} |e|_\theta = (-1)^{2i} \cdot [2i+1]. \end{aligned}$$

A triangle f whose three edges have colours $i,j,k \in I$ is assigned the weight

$$\begin{aligned} |f|_\theta = (-1)^{i+j+k} \cdot \frac{[i+j-k]! \cdot [i+k-j]! \cdot [j+k-i]!}{[i+j+k+1]!}. \end{aligned}$$

Note that the parity condition and triangle inequalities ensure that the argument inside each bracket factorial is a non-negative integer.

Fig. 1

Edge colours of a tetrahedron

Finally, let t be a tetrahedron with edge colours $i_0,i_1,i_2,i_3,i_4,i_5$ as indicated in Fig. 1. In particular, the four triangles surrounding t have colours $(i_0,i_1,i_3)$, $(i_0,i_2,i_4)$, $(i_1,i_2,i_5)$ and $(i_3,i_4,i_5)$, and the three pairs of opposite edges have colours $(i_0,i_5)$, $(i_1,i_4)$ and $(i_2,i_3)$. We define

$$\begin{aligned} \tau _\theta (t,u)= & {} [u-i_0-i_1-i_3]! \cdot [u-i_0-i_2-i_4]! \cdot \\&[u-i_1-i_2-i_5]! \cdot [u-i_3-i_4-i_5]!\,, \\ \kappa _\theta (t,u)= & {} [i_0+i_1+i_4+i_5-u]! \cdot [i_0+i_2+i_3+i_5-u]! \cdot \\&[i_1+i_2+i_3+i_4-u]! \end{aligned}$$

for all integers u such that the bracket factorials above all have non-negative arguments; or, equivalently, for all integers u in the range $u^-\le u \le u^+$ with

$$\begin{aligned} u^-= & {} \max \{i_0+i_1+i_3,\quad i_0+i_2+i_4,i_1+i_2+i_5,\quad i_3+i_4+i_5\}\,; \\ u^+= & {} \min \{i_0+i_1+i_4+i_5,\quad i_0+i_2+i_3+i_5,\quad i_1+i_2+i_3+i_4\}. \end{aligned}$$

As before, the parity condition ensures that the argument inside each bracket factorial above is an integer. We then declare the weight of tetrahedron t to be

$$\begin{aligned} |t|_\theta = \sum _{u^-\le u \le u^+} \frac{(-1)^u \cdot [u+1]!}{\tau _\theta (t,u) \cdot \kappa _\theta (t,u)}, \end{aligned}$$

All weights are polynomials on $\zeta$ with rational coefficients, where $\zeta = e^{i \pi q/r}$.

Example 1

Let t be a tetrahedron with an admissible colouring on its edges, labelled as in Fig. 1. Assume that we have for the colours $i_0 = i_1 = i_2 = \frac{1}{2}$ and $i_3=i_4=i_5 = 0$. Following the definitions above, we have

$$\begin{aligned} u^-&= \max \{ 1/2+1/2+0, 1/2+1/2+0, 1/2+1/2+0, 0+0+0 \} \\&= 1. \end{aligned}$$

And similarly

$$\begin{aligned} u^+&= \max \{ 1/2+1/2+0+0, 1/2+1/2+0+0, 1/2+1/2+0+0 \} \\&= 1. \end{aligned}$$

Hence, if follows that

$$\begin{aligned} \tau (t,u)&= [u-1]! \cdot [u-1]! \cdot [u-1]! \cdot [u]! \\ \kappa (t,u)&= [1-u]! \cdot [1-u]! \cdot [1-u]! \end{aligned}$$

The sum defining the weight of t then simplifies in the following way:

$$\begin{aligned} |t|&= \sum _{u^-\le u \le u^+} \frac{(-1)^u \cdot [u+1]!}{\tau _\theta (t,u) \cdot \kappa _\theta (t,u)} \\&= \frac{- [2]!}{[0]! \cdot [0]! \cdot [0]! \cdot [1]! \cdot [0]! \cdot [0]! \cdot [0]!} \\&= - [2]. \end{aligned}$$

See Fig. 2 and, more generally, Sect. 3 for details about weights for all faces and colourings in the case $r=4$.

Quadratic forms over $\mathbb {Z}_2$. Quadratic forms over $\mathbb {Z}_2$ play an essential role in our algorithm to compute $\mathrm {TV}_{4,q}$: they allow us to efficiently determine the number of admissible colourings with a weight of a fixed parity.

A quadratic form over $\mathbb {Z}_2$ is a form $\phi :\mathbb {Z}_2^k \rightarrow \mathbb {Z}_2$ satisfying $\phi :x \mapsto x^T R x$, for a fixed $(k \times k)$-matrix $R \in \mathbb {Z}_2^{k \times k}$. Two quadratic forms $\phi :x \mapsto x^T R x$ and $\phi :x \mapsto x^T S x$ are called equivalent, if there exists a matrix $C \in {\text {GL}}(k,\mathbb {Z}_2)$ such that $R = C^T S C$. Equivalent quadratic forms have the same number of zeroes. A quadratic form described by a $(k \times k)$-matrix is called degenerate whenever it is equivalent to a quadratic form described by a direct sum of an $(\ell \times \ell )$-matrix, $\ell < k$, and the all-zero matrix of size $((k-\ell ) \times (k-\ell ))$. Otherwise, it is called non-degenerate.

Note that the theory of quadratic forms over fields of characteristic two significantly differs from the theory over characteristic zero. Most quadratic forms over fields of characteristic two cannot be represented by symmetric matrices and thus are not diagonalisable. Moreover, a diagonalisable quadratic form over a field of characteristic two must be equivalent to a quadratic form in (at most) one indeterminant.

In what follows, whenever we work with a fixed quadratic form $\phi$ we assume it is represented by an upper triangular matrix—which is always possible.

Lemma 1

(see Theorem 6.30 in [21]) Let $\phi$ be a (possibly degenerate) quadratic form over $\mathbb {Z}_2$. Then, $\phi$ is equivalent to the direct sum of the all-zero quadratic form in $k-\ell$ indeterminants (admitting $2^{k-\ell }$ zeroes), and one of the following non-degenerate quadratic forms in $\ell \le k$ indeterminants.

$$\begin{aligned} \left\{ \begin{array}{lcl} \text {If }\ell \hbox { is odd},\quad &{}&{} x^T \tilde{R} x = x_1x_2 + x_3x_4 + \cdots + x_{\ell -2}x_{\ell -1} + x_{\ell }^2, \\ &{}&{} \text {admitting }2^{\ell -1}\hbox { zeroes}. \\ \\ \text {If }\ell \hbox { is even},\quad &{}&{} x^T \tilde{R} x = x_1x_2 + x_3x_4 + \cdots + x_{\ell -1}x_{\ell }, \\ &{}&{} \text {admitting }2^{\ell -1} + 2^{\frac{\ell }{2} -1}\hbox { zeroes}, \\ \text {or} &{}&{} \\ &{}&{} x^T \tilde{R} x = x_1x_2 + x_3x_4 + \cdots + x_{\ell -1}x_{\ell } + x_{\ell -1}^2 + x_{\ell }^2, \\ &{}&{} \text {admitting }2^{\ell -1} - 2^{\frac{\ell }{2} -1}\hbox { zeroes}. \\ \end{array}\right. \end{aligned}$$

Proof

(Sketch) Given a quadratic form $\phi :\mathbb {Z}_2^k \rightarrow \mathbb {Z}$ in indeterminants $x_1, x_2, \ldots , x_k$ described by a $(k \times k)$-matrix over $\mathbb {Z}_2$, we can determine $\ell$ and reduce $\phi$ to either one of the three forms of Lemma 1 in polynomial time following the constructive proof of Theorem 6.30 in [21]:

The proof repeatedly splits $\phi$ into blocks of form $x_1 x_2$ and a new quadratic form $\phi '$ in indeterminants $x_3, x_4, \ldots , x_k$. (This step is described in detail in Lemma 6.29 in [21].) One such splitting step requires a constant number of variable relabelings and sparse variable substitutions and is able to detect and handle degeneracies. The distinction between the three cases is made in the last step when $k \le 2$, where at most $2^3 = 8$ possible cases have to be considered.

The overall number of zeroes of $\phi$ follows by multiplying the number of zeroes of the non-degenerate part by $2^{k-\ell }$. (Note that the all-zero quadratic form never evaluates to 1.) $\square$

Fig. 2

All tetrahedron intersection patterns of an admissible colouring for $r=4$, their edge colours (top) and tetrahedron weights for $\mathrm {TV}_{4,q}$ (bottom), where $z \in \{ \sqrt{2}, -\sqrt{2} \}$ depending on q

3 Surface Interpretation of Admissible Colourings and Weights

Surface interpretation for $r=4$. An admissible colouring for the triangulation $\mathfrak {T}$ may be interpreted as a surface embedded in $\mathfrak {T}$, called a spinal surface in [11].⁴ A spinal surface is an embedded surface disjoint to the vertices of $\mathfrak {T}$, intersecting the edges of $\mathfrak {T}$ transversally, the triangles of $\mathfrak {T}$ in a collection of straight line segments, and the tetrahedra of $\mathfrak {T}$ in a collection of embedded topological discs. To define a spinal surface $S_{\theta }$ from an admissible colouring $\theta$, interpret $\theta (e)$ as half the number of times $S_\theta$ intersects e. The admissibility constraints ensure that there is a well-defined and, up to isotopy, unique spinal surface with each such intersection pattern: all such surfaces may be classified for every value of r [11, 24], and all intersection patterns for $r=4$ are shown in Fig. 2.

The three top leftmost intersection patterns in Fig. 2 are the ones for $r=3$, where edge colours belong to $\{0,\frac{1}{2}\}$. The admissibility constraints ensure the following fact for $\mathrm {Adm}(\mathfrak {T},3)$.

Lemma 2

(See also [23, 28]) Let $\mathfrak {T}$ be a triangulated 3-manifold. Then, $\mathrm {Adm}(\mathfrak {T},3)$ is in one-to-one correspondence with the set of $\mathbb {Z}_2$ 1-cocycles of $\mathfrak {T}$.

If $\mathfrak {T}$ is a one-vertex triangulation, then $\mathrm {Adm}(\mathfrak {T},3)$ is in one-to-one correspondence with the elements of $\mathbf {H}^1(\mathfrak {T},\mathbb {Z}_2)$.

Proof

Let E denote the set of edges of $\mathfrak {T}$. An edge colouring $\theta : E \rightarrow \{ 0, 1/2 \}$ defines a 1-cochain $\alpha _{\theta }$ with coefficients in $\mathbb {Z}_2$ evaluating to 1 on edges coloured 1 / 2 and to 0 otherwise.

If $\theta$ satisfies the parity condition on the triangles of $\mathfrak {T}$, the coboundary of $\alpha _{\theta }$ (a 2-cochain) vanishes over $\mathbb {Z}_2$ and vice versa. Moreover, $\theta : E \rightarrow \{ 0, 1/2 \}$ is admissible for $r=3$ if and only if it satisfies the parity condition on the triangles of $\mathfrak {T}$. Thus, $\theta$ is admissible if and only if $\alpha _{\theta }$ is a cocycle. This proves the first claim.

The second claim follows from the observation that the only 1-coboundary of a one-vertex triangulation is the empty one (all edges in $\mathfrak {T}$ are loop edges). $\square$

Corollary 1

Let $\mathfrak {T}$ be a triangulation of 3-manifold $M$ with v vertices. Then,

$$\begin{aligned} |\mathrm {Adm}(\mathfrak {T},3)| = 2^{\beta _1 (M,\mathbb {Z}_2) + v -1}. \end{aligned}$$

Proof

This follows immediately from Lemma 2 and the fact that a v-vertex triangulation of $M$ has $2^{\beta _1 (M,\mathbb {Z}_2) + v -1}$ 1-cocycles. $\square$

We use Lemma 2 and Corollary 1 in Sect. 4.

Fig. 3

2–3-move performed on two coloured tetrahedra, yielding two possible colourings with equal boundary pattern. The weight under each configuration does not take into account the participation of boundary faces: for the state sum to define an invariant, z must satisfy $z^2 = 2$

In the following, we talk about an admissible colouring $\theta$ and its spinal surface $S_\theta$ interchangeably, and, in particular, talk about the Euler characteristic of a colouring $\theta$ defined as $\chi (S_{\theta })$. For $\theta \in \mathrm {Adm}(\mathfrak {T},3)$, we also talk indifferently of the admissible colouring and the corresponding 1-cocycle in $\mathbb {Z}_2$-cohomology.

Weight system Before we can describe the algorithm, we first must take a closer look at the weights of edges, triangles and tetrahedra defined in Sect. 2 for the case $r=4$, and q such that $1 \le q \le 7$, $\gcd (4,q)=1$.

First, note that the values of the quantum integers [k], $0\le k \le 4$, are given by

$$\begin{aligned}&[1] = [3] = 1 \quad \text { and } \quad [4] = 0 \quad \text {for all }\,\,q,\\&\text { and } [2] = \left\{ \begin{array}{rl} \sqrt{2} &{}\quad \text {if }\,\, q \in \{1,7\},\\ - \sqrt{2} &{}\quad \text {if }\,\, q \in \{3,5\}. \end{array} \right. \end{aligned}$$

For the remainder of this article, we define $z := -[2]$.

We study the weights of faces for each choice of admissible colouring separately. Let $\theta \in \mathrm {Adm}(\mathfrak {T},4)$, that is, $\theta$ colours the edges of $\mathfrak {T}$ with colours 0, $\frac{1}{2}$, and 1, such that—up to permutation—the three edges of each triangle are coloured (0, 0, 0), $(0,\frac{1}{2},\frac{1}{2})$, $(\frac{1}{2},\frac{1}{2},1)$ and (0, 1, 1). For a vertex w, an edge e and a triangle f, we have

Tetrahedron weights are presented in Fig. 2; see also Example 1 for a detailed example calculation.

Considering the definition of Turaev–Viro-type invariants (see Sect. 2) and the observations made above, we deduce that $\mathrm {TV}_{4,q}$ is a Laurent polynomial in z, evaluated at $\pm \sqrt{2}$. To see that other values of z cannot lead to a topological invariant, consider two tetrahedra coloured $(\frac{1}{2}, 0, \frac{1}{2}, 0, \frac{1}{2}, 0)$ joined along the zero-coloured triangle f (see Fig. 3). The two tetrahedra and the common triangle contribute a factor of $z^2$ to this colouring. Performing a 2–3-move (i.e. replacing two tetrahedra joined along a triangle by three tetrahedra joined along an edge) across f yields three tetrahedra joined along a common edge e. Keeping the colouring on all boundary edges fixed, e can be coloured 0 or 1 leading to two valid colourings. In each case, the three tetrahedra weights multiplied with the three internal triangle weights and the internal edge weight contribute a factor of 1 to the colouring. Since the 2–3-move does not change the topology of the triangulation, the sum of the weights of the two new colourings must equal the weight of the original colouring. Hence, $z^{2} = 1 + 1$ and thus $z \in \{\pm \sqrt{2} \}$. However, we know from the work of Turaev and Viro [39] that both solutions give rise to a topological invariant.

By Matveev [27], and independently by Piergallini [33], we know that any two one-vertex triangulations of a 3-manifold are connected by a sequence of 2–3-moves and their inverses. There are 28 more constellations (up to symmetry) of how two coloured tetrahedra from the list in Fig. 2 can meet along a triangle. Performing a 2–3-move on one of them gives rise to an equivalent condition ($z^2 = 2$), the other 27 do not impose any restrictions. This defines a very basic (although slightly lengthy) proof of the topological invariance of $\mathrm {TV}_{4,q}$.

For the remainder of this article, we assume that $\mathfrak {T}$ is a one-vertex triangulation of a closed 3-manifold $M$. This is a reasonable assumption for the following reasons: (a) every closed 3-manifold admits a one-vertex triangulation [17, Theorem 5.6], (b) input triangulations in computational 3-manifold topology are typically presented in this form, and (c) given an arbitrary triangulation of a closed 3-manifold, there exists a polynomial-time algorithm which turns it into a one-vertex triangulation $\mathfrak {T}'$ of smaller or equal size, [5, 8].⁵

Since we restrict ourselves to one-vertex triangulations, we omit the constant vertex weight 1 / 4 when defining colouring weights and the Turaev–Viro invariant for such triangulations. Note that, this way, we can deduce from the above calculations that all computations are done within the ring $\mathbb {Z}[\sqrt{2}]$, where arithmetic operations (called cyclotomic field operations) are constant time representing $\sqrt{2}$ symbolically. (However, keep in mind that minimising the number of arithmetic operations in $\mathbb {Z}[\sqrt{2}]$ may have a significant impact on practical running times; see Sect. 6.2.)

Topological interpretation of weights for $\mathrm {TV}_{4,q}$ We interpret the weights of admissible colourings of $\mathfrak {T}$ in terms of the Euler characteristic of their associated spinal surfaces. For admissible colourings with edge colours $\{0,\frac{1}{2}\}$, we have:

Lemma 3

Let $\theta \in \mathrm {Adm}(\mathfrak {T},4)$ such that no edge of $\mathfrak {T}$ is coloured with 1, and let $S_{\theta }$ be the surface associated with $\theta$. Then, $\theta \in \mathrm {Adm}(\mathfrak {T},3)$ and

$$\begin{aligned} |\mathfrak {T}|_{\theta } = z^{\chi (S_\theta )}, \end{aligned}$$

where $\chi$ denotes the Euler characteristic.

Proof

First note that $\theta \in \mathrm {Adm}(\mathfrak {T},4)$ with no edge coloured by 1 implies that all triangles are coloured (0, 0, 0) or $(0,\frac{1}{2},\frac{1}{2})$ (up to symmetry) and thus $\theta \in \mathrm {Adm}(\mathfrak {T},3)$.

The proof is a direct corollary of the face weights listed above. Let $S_{\theta }$ have $m_0$ vertices, $m_1$ edges, $m_{\triangle }$ triangles and $m_{\square }$ quadrilaterals or, in other terms, let $m_0$ be the number of edges of $\mathfrak {T}$ that are coloured $\frac{1}{2}$ by $\theta$, $m_1$ be the number of $(0,\frac{1}{2},\frac{1}{2})$-coloured triangles (up to symmetry), $m_{\triangle }$ be the number of $(\frac{1}{2},0,\frac{1}{2},0,\frac{1}{2},0)$-coloured tetrahedra (up to symmetry), and $m_{\square }$ be the number of $(0,\frac{1}{2},\frac{1}{2},0,\frac{1}{2},\frac{1}{2})$-coloured tetrahedra (up to symmetry). All other faces must be zero-coloured and hence have weight 1.

It follows that we have for the product of all weights

$$\begin{aligned} |\mathfrak {T}|_{\theta } = z^{m_0} \cdot z^{-m_1} \cdot z^{m_{\triangle }} \cdot z^{m_{\square }} = z^{\chi (S_\theta )}, \end{aligned}$$

where $\chi$ denotes the Euler characteristic of the surface $S_{\theta }$. $\square$

For a colouring $\hat{\theta } \in \mathrm {Adm}(\mathfrak {T},4)$, we define its reduction $\theta$ satisfying:

$$\begin{aligned} \text {For every edge }{e \in E, } \theta (e) = \hat{\theta }(e) - \lfloor \hat{\theta }(e) \rfloor . \end{aligned}$$

(2)

It follows from elementary calculations that the reduction in an admissible colouring of $\mathrm {Adm}(\mathfrak {T},4)$ is an admissible colouring of $\mathrm {Adm}(\mathfrak {T},3)$.

Lemma 4

Let $\hat{\theta } \in \mathrm {Adm}(\mathfrak {T},4)$ and let $\theta$ be the reduction in $\hat{\theta }$. Then,

$$\begin{aligned} |\mathfrak {T}|_{\hat{\theta }} = (-1)^{\alpha } |\mathfrak {T}|_{\theta } = (-1)^{\alpha } z^{\chi (S_\theta )}, \end{aligned}$$

where $\alpha$ denotes the number of tetrahedra coloured $(1,\frac{1}{2},\frac{1}{2},1,\frac{1}{2},\frac{1}{2})$ in $\hat{\theta }$ (up to symmetry), i.e. the number of octagons in $S_{\hat{\theta }}$.

Proof

We want to express the weight of $\hat{\theta }$ in terms of the weight of its reduction $\theta$.

Following the study of weights for $\mathrm {TV}_{4,q}$ above (see also Fig. 2), the only face colourings of $\hat{\theta }$ whose weight changes in $\theta$ are: the triangle $(\frac{1}{2},\frac{1}{2},1)$ and the tetrahedra $(\frac{1}{2},\frac{1}{2},1,\frac{1}{2},\frac{1}{2},0)$, $(\frac{1}{2},\frac{1}{2},1,0,1,\frac{1}{2})$ and $(1,\frac{1}{2},\frac{1}{2},1,\frac{1}{2},\frac{1}{2})$. Their weights differ only by a factor of $(-1)$. Let $\gamma$ be the total number of those faces whose weights with $\hat{\theta }$ change in the reduction. We have that $|\mathfrak {T}|_{\hat{\theta }} = (-1)^{\gamma } |\mathfrak {T}|_{\theta }$.

Note that $(1,\frac{1}{2},\frac{1}{2},1,\frac{1}{2},\frac{1}{2})$ contains four, $(\frac{1}{2},\frac{1}{2},1,\frac{1}{2},\frac{1}{2},0)$ and $(\frac{1}{2},\frac{1}{2},1,0,1,\frac{1}{2})$ contain two, and all other tetrahedra types contain zero triangles of type $(\frac{1}{2},\frac{1}{2},1)$. Moreover, every triangle is contained in two tetrahedra. If there are $\alpha$ tetrahedra of octagon type $(1,\frac{1}{2},\frac{1}{2},1,\frac{1}{2},\frac{1}{2})$, $\lambda$ of type $(\frac{1}{2},\frac{1}{2},1,\frac{1}{2},\frac{1}{2},0)$ and $\mu$ of type $(\frac{1}{2},\frac{1}{2},1,0,1,\frac{1}{2})$, we have that

$$\begin{aligned} \gamma = \alpha + \lambda + \mu + (4\alpha + 2\lambda + 2\mu )/2 = 3\alpha + 2\lambda + 2\mu \end{aligned}$$

and thus $(-1)^{\gamma } = (-1)^{\alpha }$, and, by virtue of Lemma 3,

$$\begin{aligned} |\mathfrak {T}|_{\hat{\theta }} = (-1)^{\alpha } |\mathfrak {T}|_{\theta } = (-1)^{\alpha } z^{\chi (S_\theta )}. \end{aligned}$$

$\square$

4 Fixed-Parameter Tractable Algorithm in $\beta _1$ for $\mathrm {TV}_{4,q}$

Recall that, in what follows, we assume that $\mathfrak {T}$ is a one-vertex triangulation of a closed 3-manifold $M$.

In this section, we present a fixed-parameter tractable (FPT) algorithm to compute $\mathrm {TV}_{4,q} (M)$, for any $1 \le q \le 8$, $\gcd (4,q)=1$, which runs in polynomial time in the size of $\mathfrak {T}$ as long as the first Betti number of the 3-manifold $M$ triangulated by $\mathfrak {T}$ is bounded. More precisely, the algorithm has running time $O(2^{\beta _1 (M, \mathbb {Z}_2)}\cdot n^3)$.

4.1 Polynomial-Time Algorithm at a Cohomology Class

Let $\theta$ be an admissible colouring of $\mathrm {Adm}(\mathfrak {T},3)$ (i.e. we fix a 1-cohomology class, cf. Lemma 2). We define:

$$\begin{aligned}&A_{\theta } = \{ \hat{\theta } \in \mathrm {Adm}(\mathfrak {T},4) \,\,|\,\, \hat{\theta } \text { reduces to } \theta \}, \quad \text {and}\\&\mathrm {TV}_{4,q}(M,[\theta ]) := \sum _{\hat{\theta } \in A_\theta } |\mathfrak {T}|_{\hat{\theta }} \end{aligned}$$

to be the set of colourings reducing to $\theta$ via Eq. 2, and the sum of their weights, respectively. By virtue of Lemma 4, the weights $|\mathfrak {T}|_{\hat{\theta }}$ of the sum are all equal, up to a sign, to $z^{\chi (S_\theta )}$.

This partial sum of the Turaev–Viro invariant is called the Turaev–Viro invariant at a cohomology class [39]. We present a polynomial-time algorithm to compute $\mathrm {TV}_{4,q}(M,[\theta ])$ at a given cohomology class $[\theta ]$.

Characterisation of the set of colourings $A_{\theta }$ Given $\theta \in \mathrm {Adm}(\mathfrak {T},3)$, we partition the set of edges E of $\mathfrak {T}$ into three groups $E_0$, $E_1$ and $E_2$:

• $E_0$ contains all edges coloured by $\frac{1}{2}$ in $\theta$,

• $E_1$ contains all edges coloured 0 which occur in at least one triangle of type (0, 0, 0), and

• $E_2$ contains all edges coloured 0 which only occur in triangles of type $(0,\frac{1}{2},\frac{1}{2})$.

We characterise the set of colourings $A_{\theta }$ as the solution space of a set of linear equations over $\mathbb {Z}_2$.

By definition, the edges in $E_0$ are exactly the ones coloured $\frac{1}{2}$ by all colourings $\hat{\theta } \in A_{\theta }$. Every admissible colouring $\hat{\theta } \in A_{\theta }$ must colour triangles of type (0, 0, 0) in $\theta$ by either (0, 0, 0) or (0, 1, 1), up to permutation. Hence, such a triangle $\{e_1,e_2,e_3\}$ is admissible if and only if $\hat{\theta } (e_1) + \hat{\theta } (e_2) + \hat{\theta } (e_3) = 0 \mod 2$. Considering $\hat{\theta } (e)$, $e \in E_1$, as an element of $\mathbb {Z}_2$, all possible colourings of these triangles in $A_{\theta }$ can be described by a homogeneous linear system over $\mathbb {Z}_2$, that is, the incidence matrix of edges in $E_1$ and triangles of type (0, 0, 0) in $\theta$.

Observe that every solution of this system can be extended to an admissible colouring $\hat{\theta } \in A_{\theta }$ by assigning colour 0 to all edges in $E_2$. Indeed, all triangles of type (0, 0, 0) in $\theta$ are now of type (0, 0, 0) or (1, 1, 0) in $\hat{\theta }$, and all triangles of type $(\frac{1}{2},\frac{1}{2},0)$ in $\theta$ are now of type $(\frac{1}{2},\frac{1}{2},0)$ or $(\frac{1}{2},\frac{1}{2},1)$.

Finally, by definition of the set $E_2$, every assignment of colours to the edges $E_0 \cup E_1$, satisfying the conditions above, gives rise to $2^{|E_2|}$ admissible colourings given by all possible $\{0,1\}$ assignments of colours to edges in $E_2$. Take a moment to verify that no such assignment of colours can result in a non-admissible triangle colouring.

It follows that the set $A_{\theta }$ can be described as a subspace in $\mathbb {Z}_2^{|E_1| + |E_2|}$ where the first $|E_1|$ coordinates are associated with the edges in $E_1$ and the last $|E_2|$ coordinates are associated with the edges in $E_2$. (The edges in $E_0$ are always coloured $\frac{1}{2}$ and thus need no explicit description.) A basis of this subspace is given by a basis $\{b_1, b_2,\ldots ,b_m\}$ of the solution space of the above linear system concatenated with the standard basis on the last $|E_2|$ coordinates $\{ d_1, d_2, \ldots , d_{|E_2|} \}$. The subspace naturally decomposes into two blocks of size m and $|E_2|$.

Evaluation of $\mathrm {TV}_{4,q}(M,[\theta ])$. Hence, using the characterisation above, we can efficiently compute the cardinality of $A_{\theta }$. Furthermore, we know from Lemma 4 that all colourings in $A_{\theta }$ have the same weight, up to a sign which only depends on the parity of the number of octagons of a colouring.

Thus, it remains to show that we can determine the number of admissible colourings in $A_{\theta }$ with an even number of octagons in polynomial time.

With $\theta \in \mathrm {Adm}(\mathfrak {T},3)$ fixed, the only tetrahedra which can be of type $(1,\frac{1}{2},\frac{1}{2},1,\frac{1}{2},\frac{1}{2})$ in $\hat{\theta } \in A_{\theta }$ are the ones of type $(0,\frac{1}{2},\frac{1}{2},0,\frac{1}{2},\frac{1}{2})$ in $\theta$. Denote these tetrahedra by $t_1, \ldots , t_s$, and denote their opposite 0-coloured edges by $x_i$, $y_i$, $1 \le i \le s$. Considering the 0 or 1 colour of an edge as elements of $\mathbb {Z}_2$, the parity of the number of octagons in $\hat{\theta }$ is now given by:

$$\begin{aligned} \sum \limits _{i = 1}^{s} \hat{\theta } (x_i) \hat{\theta } (y_i) \in \mathbb {Z}_2. \end{aligned}$$

(3)

This expression can be regarded as a quadratic form $x \mapsto x^T Q x$, where $Q \in \mathbb {Z}_2^{(|E_1| + |E_2|)\times (|E_1| + |E_2|)}$ is an upper triangular matrix obtained by setting $Q_{i,j}$, $i \le j$, if and only if the corresponding pair of edges occurs in an odd number of terms in Eq. 3 (note that, in a generalised triangulation, two edges may appear as opposite edges in more than one tetrahedron).

As we have seen, every colouring in $A_{\theta }$ is given by a linear combination of vectors $b_i$, $1 \le i \le m$, and $d_j$, $1 \le j \le |E_2|$, that is, by a vector in $\mathbb {Z}_2^{|E_1| + |E_2|}$ of the form $Mv \in \mathbb {Z}_2^{|E_1| + |E_2|}$, where $v \in \mathbb {Z}_2^{m + |E_2|}$, and M is the $(|E_1|+|E_2|) \times (m + |E_2|)$-matrix $( b_1, b_2, \ldots , b_m, d_1, \ldots d_{|E_2|})$ with entries in $\mathbb {Z}_2$.

Defining $R = M^T Q M$, we obtain an $(m+|E_2|)\times (m+|E_2|)$-matrix satisfying that (i) the input vectors $v \in \mathbb {Z}_2^{m+|E_2|}$ are in one-to-one correspondence with the admissible colourings in $A_{\theta }$ and (ii) $v^T R v = 0 \mod 2$ if and only if the admissible colouring encoded by v has an even number of tetrahedra of type $(1,\frac{1}{2},\frac{1}{2},1,\frac{1}{2},\frac{1}{2})$.

Following the proof of Lemma 1, we can transform R into an equivalent quadratic form of type direct sum of one of the three non-degenerate forms given in Lemma 1 in $\ell$ indeterminants, and the all-zero quadratic form in $m+|E_2|-\ell$ indeterminants. The number of zeroes of the non-degenerate part, denoted by $\sigma$, now follows from Lemma 1, and we have

$$\begin{aligned} \mathrm {TV}_{4,q}(M,[\theta ])&= \sum \limits _{\hat{\theta } \in A_{\theta }} |\mathfrak {T}|_{\hat{\theta }} \\&= \sum \limits _{v \in \mathbb {Z}_2^{m+|E_2|}: v^T R v = 0} |\mathfrak {T}|_{\theta } \quad - \sum \limits _{v \in \mathbb {Z}_2^{m+|E_2|}: v^T R v = 1}|\mathfrak {T}|_{\theta } \\&= 2^{m+|E_2|-\ell } (2 \, \sigma - 2^{\ell }) \, |\mathfrak {T}|_\theta . \end{aligned}$$

4.2 Fixed-Parameter Tractable Algorithm in $\beta _1$

The fixed-parameter tractable algorithm to compute $\mathrm {TV}_{4,q}$ simply consists of running the procedure described in Sect. 4.1 for every 1-cohomology class in $\mathfrak {T}$ and sums up all partial sums for all 1-cohomology classes. A basis for the 1-cohomology group of a triangulation may be computed in polynomial time, and the cohomology classes may be enumerated efficiently. Moreover, we can sum up the contributions from the trivial cohomology class, and cohomology classes $\theta$ with even and odd Euler characteristic surfaces $S_{\theta }$ separately, resulting in the invariants $\mathrm {TV}_{4,q,\nu } (M)$, $\nu \in \{0,1,2\}$, as defined by Matveev [28, Section 8.1.5]. These three invariants sum up to $\mathrm {TV}_{4,q}$, but considering them separately yields to a stronger topological invariant than $\mathrm {TV}_{4,q}$.

Correctness of the algorithm Following Lemma 3, every colouring $\hat{\theta }$ belonging to $\mathrm {Adm}(\mathfrak {T},4)$ reduces to a unique colouring $\theta \in \mathrm {Adm}(\mathfrak {T},3)$ and can thus be associated with a unique 1-cohomology class (note that $\mathfrak {T}$ has only one vertex) [23]. By Lemma 4, all colourings associated with $\theta$ are assigned the same weight up to a sign. By definition of the sets $E_0$, $E_1$ and $E_2$, every colouring in $\mathrm {Adm}(\mathfrak {T},4)$ reducing to $\theta$ is considered, and by the definition of the quadratic form, the number of colourings with a positive weight equals the number of zeroes of the quadratic form. Thus, all admissible colourings are considered with their proper weight.

Running time of the algorithm Given an n-tetrahedron triangulation $\mathfrak {T}$ of 3-manifold $M$, we transform $\mathfrak {T}$ into a one-vertex $n'$-tetrahedron triangulation $\mathfrak {T}'$, $n' \le n$ in $O(n^3)$ time, using a slight adaptation of the algorithm for knot complements presented in [8, Lemma 6].⁶

Computing admissible colourings $\mathrm {Adm}(\mathfrak {T}', 3)$ requires solving a linear system of size $O(n')$ which can be done in $O(n'^3)$ time. By Corollary 1, we have $|\mathrm {Adm}(\mathfrak {T}', 3)| = 2^{\beta _1 (M,\mathbb {Z}_2)}$. For each $\theta \in \mathrm {Adm}(\mathfrak {T}', 3)$, we can compute $|\mathfrak {T}'|_{\theta }$ and determine $E_0$, $E_1$, and $E_2$ in linear time. Computing admissible colourings $A_\theta \subset \mathrm {Adm}(\mathfrak {T}', 4)$, again, requires solving a linear system which, again, requires $O(n'^3)$ time. Finally, setting up the quadratic form consists of two matrix multiplications and transforming it into canonical form requires $O(m + |E_2|)$ variable relabelings and sparse basis transforms running in $O((m + |E_2|)^2)$ time each. Altogether, the algorithm thus runs in

$$\begin{aligned} O(2^{\beta _1 (M,\mathbb {Z}_2)} \cdot n^3) \end{aligned}$$

time. The algorithm has polynomial memory complexity $O(n^2)$: we have to keep track of the current state sum, as well as a constant number of matrices of size $O(n) \times O(n)$. Moreover, the only cyclotomic field operations occur, whenever the contribution of one of the $2^{\beta _1 (M, \mathbb {Z}_2)}$ cohomology classes is added to the state sum.

5 $\mathrm {TV}_{4,q}$ is not Harder than Counting

The computational complexity of quantum invariants and its connection to the counting complexity class #P establish deep connections between the structure of representations of 3-manifolds or knots and separation of complexity classes (see Freedman’s seminal work [10] for the Jones polynomial).

Computing $\mathrm {TV}_{4,1}$ is known to be #P-hard, via a reduction from #3SAT [7, 19]. We prove a converse result here, specifically that computing $\mathrm {TV}_{4,q}$, $q \in \{1,3\}$, using an n-tetrahedron triangulation $\mathfrak {T}$, can be reduced to $\mathrm {poly}(n)$ instances of a counting problem.⁷ This is a direct consequence of Lemma 4. Using the notations from Sect. 3, consider the Laurent polynomial

$$\begin{aligned} P_\mathfrak {T}(z) = \sum _{\hat{\theta } \in \mathrm {Adm}(\mathfrak {T},4)} (-1)^{\alpha } z^{\chi (S_{\theta })} = \sum _{m \in \mathbb {Z}} a_m z^m . \end{aligned}$$

Note that in this presentation, we group admissible colourings by the Euler characteristic of their reductions, as opposed to in Sect. 4 where they are grouped by the cohomology class of their reductions. The degree of the Laurent polynomial $P_\mathfrak {T}(z)$ is O(n). This follows from the facts that (i) the intersection patterns between a surface $S_{\hat{\theta }}$ and the tetrahedra of $\mathfrak {T}$ are constrained to the finite set of cases presented in Sect. 3, and (ii) $\chi$ is a linear function. Naturally, $\mathrm {TV}_{4,1}(M) = P_\mathfrak {T}(-\sqrt{2})$ and $\mathrm {TV}_{4,3}(M) = P_\mathfrak {T}(\sqrt{2})$.

For an integer m, let $b^+_m$ (respectively $b^-_m$) be the number of colourings $\hat{\theta } \in \mathrm {Adm}(\mathfrak {T},4)$ with an even (respectively odd) number of octagons and $\chi (S_\theta ) = m$. Consequently, $a_m = b^+_m - b^-_m$, and computing the Laurent polynomial $P_\mathfrak {T}(z)$ (and consequently computing $\mathrm {TV}_{4,q}$) reduces to $\mathrm {poly}(n)$ calls to the following problems:

These problems belong to the counting class #P since checking whether an arbitrary assignment of edge colours $\hat{\theta }$ is an admissible colouring of $\mathrm {Adm}(\mathfrak {T},4)$, computing the parity of the number of octagons and computing the Euler characteristic of $S_{\theta }$ are all polynomial-time procedures.

6 Practical Significance of the Algorithm

6.1 The Power of $\mathrm {TV}_{4,q}$ to Distinguish Between 3-Manifolds

The significance of the FPT algorithm from Sect. 4.2 to compute $\mathrm {TV}_{4,q}$ strongly depends on the power of $\mathrm {TV}_{4,q}$ to distinguish between 3-manifolds that are not homoeomorphic.

Since there is no canonical way to quantify this power in general, we give evidence of the power of $\mathrm {TV}_{4,q}$ along two specific directions: (i) We present an infinite family of non-homoeomorphic but homotopy equivalent 3-manifolds, which are provably distinguished by $\mathrm {TV}_{4,1}$. (ii) We run experiments on large censuses of 3-manifold triangulations.

The Turaev–Viro invariants of lens spaces have been studied in [35, 40].

Theorem 2

(Based on [35, 40]) Let L(p, q) be the lens space with co-prime parameters p and q, $0< q < p$, and let $k > 0$. Then, we have

$$\begin{aligned} \begin{array}{cccc} \mathrm {TV}_{4,1} ( L(16k,q) ) &{}=&{} \left\{ \begin{array}{ll} 1 &{} \quad \text { if }\quad q = \pm 1 \, \mathrm {mod}\, 8 \\ 0 &{}\quad \text { otherwise}, \end{array}\right. &{} \quad \text { and } \\ \mathrm {TV}_{4,1} ( L(16k-8,q) ) &{}=&{} \left\{ \begin{array}{ll} 1 &{} \quad \text { if } q = \pm 3 \, \mathrm {mod}\, 8 \\ 0 &{}\quad \text { otherwise}. \end{array}\right. &{} \\ \end{array} \end{aligned}$$

Hence, given the FPT algorithm introduced above, we deduce:

Corollary 2

Let $M$ and N be triangulated 3-manifolds which are known to be homoeomorphic to lens spaces $L(8k,q_1)$ and $L(8\ell ,q_2)$, $k,\ell > 0$, $q_1,q_2 \in \{1,3\}$. Then, there exists a polynomial-time procedure to decide the homeomorphism problem for $M$ and N.

Proof

The first integral homology group of L(p, q) equals $\mathbb {Z}_p$. Thus, we use homology calculations—a polynomial-time procedure—to determine 8k and $8\ell$. If $8k \ne 8\ell$, then $M$ and N are not homoeomorphic. If $8k = 8\ell$, we know that $M$ is homoeomorphic to $L(8k,q_1)$ and N is homoeomorphic to $L(8k,q_2)$, $q_1,q_2 \in \{1,3\}$.

We compute $\mathrm {TV}_{4,1}$ of both $M$ and N. Since both $M$ and N have first $\mathbb {Z}_2$-Betti number equal to 1, this is a polynomial-time procedure. By Theorem 2, we conclude that $M$ and N are homoeomorphic if and only if both values for $\mathrm {TV}_{4,1}$ coincide. $\square$

To determine the power of $\mathrm {TV}_{4,q}$ on a less specific level, we run large-scale experiments on the census of 13,397 distinct topological types of minimal one-vertex triangulations of 3-manifolds with up to 11 tetrahedra [4, 28], and on the Hodgson–Weeks census of 11,031 topologically distinct closed hyperbolic manifolds [14]. In our experiments, we use an implementation of the algorithm presented in Sect. 4.2 to compute the finer 3-uplet of invariants $\mathrm {TV}_{4,q,\nu }(M)$, $\nu \in \{0,1,2\}$.

Fig. 4

Comparison of the running times of the FPT algorithm from [7] and the FPT algorithm from Sect. 4.2 to compute $\mathrm {TV}_{4,1}$. The algorithms are run on the minimal one-vertex triangulations of the $\le 11$-tetrahedra census [4, 28]. For every data point the parameters of both algorithms are given by (i) size of the dot for treewidth, and (ii) colour for first $\mathbb {Z}_2$-Betti number (Color figure online)

Table 1 Timings for the computation of $\mathrm {TV}_{4,1}$, using the algorithm parameterised by $\beta _1$ introduced in this article and the algorithm parameterised by treewidth introduced in [7], over all triangulations of the up to 11 tetrahedra census, and the Hodgson–Weeks census

The 13,397 distinct topologies of up to 11 tetrahedra census split into 697 groups of manifolds with equal integral homology. Combining integral homology with $\mathrm {TV}_{4,q,\nu }$, $q \in \{1,3\}$, $\nu \in \{0,1,2\}$, we are able to split the manifolds further into 1205 groups. The 11,031 manifolds in the Hodgson–Weeks census split into 516 groups of equal integral homology. Combining integral homology with $\mathrm {TV}_{4,q,\nu }$ yields 816 groups of manifolds.

Using $\mathrm {TV}_{4,q,\nu }(M)$, $\nu \in \{0,1,2\}$, we are thus able to distinguish nearly twice as many pairs of 3-manifolds than with integral homology alone.

6.2 Timings

To illustrate its potential for fast practical computations, we compare running times of our algorithm with the algorithm from [7], currently used by the 3-manifold software Regina [6]. More precisely, we compare running times for every minimal one-vertex triangulation of the $\le 11$-tetrahedra census with positive first $\mathbb {Z}_2$-Betti number, while recording both the first Betti number and the treewidth of the respective triangulation. The running times show a clear stratification of the data by first $\mathbb {Z}_2$-Betti number. The impact of the treewidth of the triangulations is smaller but still visible: high treewidth triangulations are amongst the examples exhibiting the greatest improvements in running times. The findings are summarised in Fig. 4.

In conclusion, the FPT algorithm for $\mathrm {TV}_{4,q}$ presented in this article is of practical importance. Combined with integral homology, it allows to refine the classification of 3-manifolds, on our censuses, by a factor of 1.73 and 1.58, respectively, at a cost comparable to the computation of homology. Moreover, practical running times on standard data sets are orders of magnitude faster than previous state-of-the-art implementations to compute $\mathrm {TV}_{4,q}$; see Table 1 for an overview. We hope this qualifies $\mathrm {TV}_{4,q}$ to become a standard pre-computation in 3-manifold topology.

We will integrate the algorithm into the 3-manifold software Regina [6].