A polynomial-time algorithm to compute Turaev-Viro invariants \(\mathrm{TV}_{4,q}\) of 3-manifolds with bounded first Betti number (Q2216247)

Let \({\mathfrak T}\) be a generalized triangulation of a closed 3-manifold \(M\). That is, \(M\) is homeomorphic to a collection of \(n\) tetrahedra glued together along their triangular faces. For an integer \(r\), a coloring of \({\mathfrak T}\) assigns a non-negative integer or half-integer of at most \((r-2)/2\) to each edge. It is admissible if for any triangle, the sum of edge colors is an integer of at most \(r-2\), and each edge color is bounded by the sum of its opposite edge colors. Let \(\mathrm{Adm}({\mathfrak T},r)\) denote the set of all such colorings. For each positive integer \(q\), with \(q\leq 2r\) and relatively prime to \(r\), \textit{V. G. Turaev} and \textit{O. Y. Viro} [Topology 31, No. 4, 865--902 (1992; Zbl 0779.57009)] devised a way of assigning a weight \(|{\mathfrak T}|_\theta\) to a coloring \(\theta\), whose specific value depends on \(r\) and \(q\), such that the sum \(TV_{r,q}\doteq\sum_{\theta\in\mathrm{Adm}({\mathfrak T},r)}|{\mathfrak T}|_\theta\) is a topological invariant. The authors of the article provide an algorithm for computing \(TV_{4,q}\) under the assumption that \({\mathfrak T}\) has only a single vertex (any generalized triangulation can be modified to a single vertex one using a polynomial-time algorithm). In this case, a coloring \(\theta\in\mathrm{ Adm}({\mathfrak T},3)\) defines a unique class in the first cohomology group of \(M\) with coefficients in \({\mathbb Z}_2\), the field of two elements. In particular, the number of colorings in \(\mathrm{Adm}({\mathfrak T},3)\) is equal to \(2^{\beta_1}\), where \(\beta_1\) is the first \({\mathbb Z}_2\)-Betti number of \(M\). On the other hand, any coloring \(\hat\theta\in\mathrm{Adm}({\mathfrak T},4)\) induces a coloring \(\theta\in\mathrm{Adm}({\mathfrak T},3)\), and the authors provide a formula for the weight \(|{\mathfrak T}|_{\hat\theta}\) in terms of \(\theta\) and the combinatorics of \({\mathfrak T}\). The resulting algorithm computes \(TV_{4,q}\) in \(O(n^3\,2^{\beta_1})\) time.