Quantitative word problem for 3-manifold groups

Question

The word problem for 3-manifold groups is solvable: given a based loop $\gamma$ in $M^3$ there is an algorithm to decide whether $\gamma$ bounds a disk.

What kinds of quantitative results are known about this problem? Specifically, what are the known best upper bound estimates for the time and space complexity of these algorithms?

Suppose we use a triangulation as a genie, are there any results like the following? If $(M,T)$ is a closed 3-manifold $M$ and a triangulation $T$ of $M$ then there exists a PL loop $\gamma$ in $M$ such that if $T'$ is a triangulation of $M$ with a 2-skeleton containing a disk bounding the loop then the Pachner distance between the two triangulations $T$ and $T'$ must be greater than $e^l$, where $l$ is the length of $\gamma$.

Answer 1

Suppose that $M$ is a compact irreducible 3-manifold.

1. Assume that $M$ is neither a Nil nor a Sol-manifold. Then $G=\pi_1(M)$ is automatic, which implies that $G$ has quadratic Dehn function and the word problem in $G$ is decidable in $O(n^2)$-time. If $M$ is a closed hyperbolic 3-manifold, then, of course, you get a linear estimate.

From the practical standpoint, finding an automatic structure on $G$ if $M$ is just given by its triangulation is a hard task. Even in the case when $M$ is a closed hyperbolic 3-manifold given by its triangulation, I do not think there are known explicit estimates of hyperbolicity constant for $G=\pi_1(M)$ (with generating set, say, given by the triangulation) in terms of the triangulation. However, in principle, techniques for such estimates are available once you computed a Haken hierarchy (if $M$ is Haken). In general, this is an open problem how to extract geometric information about hyperbolic structure from a triangulation (besides estimating the hyperbolic volume), although in the last 10-15 years there was some progress in this direction.

2. If $M$ is a Nil or a Sol-manifold, the group $G=\pi_1(M)$ embeds in $SL(3, Z)$. Hence, the WP in $G$ is decidable in (correction) $O(n^2)$-time: You just multiply integer matrices.

3. In the case of reducible oriented 3-manifolds, the fundamental group splits as a free product of fundamental groups of irreducible components and you obtain the same estimates on complexity of the WP as above.

Thus, the answer to your question is "at most quadratic and in some cases linear." The fact that the estimate is always quadratic suggests that there is a uniform proof of such a quadratic bound. I have no idea how this could/would work, apart from proving (Thurston's?) conjecture that fundamental groups of all compact 3-manifolds embed in $SL(N,Z)$ for some nonuniform $N$. The latter is known in "most" but not all cases.

Some references:

Epstein, David B. A.; Cannon, James W.; Holt, Derek F.; Levy, Silvio V. F.; Paterson, Michael S.; Thurston, William P., Word processing in groups, Boston, MA etc.: Jones and Bartlett Publishers. xi, 330 p. (1992). ZBL0764.20017.

Aschenbrenner, Matthias; Friedl, Stefan; Wilton, Henry, 3-manifold groups, EMS Series of Lectures in Mathematics. Zürich: European Mathematical Society (EMS) (ISBN 978-3-03719-154-5/pbk). xiv, 215 p. (2015). ZBL1326.57001.

Answer 2

Moshe’s answer points out that one gets a quadratic algorithm for the word problem for subgroups of $GL_N(\mathbb{Z})$. I thought I would expand a comment on his answer into an answer, since I’m not aware of such a result strictly in the literature (even though it is relatively trivial, the estimate depends on recent advances).

Firstly, as you can find from the reference 3-Manifold Groups cited in Moshe’s answer, a compact orientable 3-manifold $M$ admitting a non-positively curved metric (which includes compact irreducible manifolds with non-empty boundary) admits a faithful representation of its fundamental group into $GL_N(\mathbb{Z})$ for some $N$ depending on $M$. This follows from results of Yi Liu in the graph manifold case and Przytycki-Wise in the “mixed manifold” case (see Cor. 1.2), where there is a hyperbolic piece of the JSJ decomposition (such irreducible manifolds always admit non-positively curved metric by a result of Bernhard Leeb). The remaining graph manifold cases may have linear fundamental group, but there are certain restrictions.

In any case, one can show that finitely-generated subgroups of $GL_N(\mathbb{Z})$ have word problem which is $O(n\log^2 n)$ in the length of the word $n$. Suppose that we are given $k$ $N\times N$ matrices $A_1,\ldots, A_k \in GL_N(\mathbb{Z})$ which generate the group $G<GL_N(\mathbb{Z})$ as a semigroup (so if we are initially given generators, we can throw in their inverses to get a semigroup generating set). The word problem then asks whether the product $A_{i_1} A_{i_2}\cdots A_{i_n} = I$ for a sequence $i_1, \ldots, i_n,$ where $i_j \in \{1,\ldots,k\}$.

If the entries of the matrices $A, B \in GL_N(\mathbb{Z})$ are integers represented by at most $a$ and $b$ bits respectively, then the product $AB$ will have entries with at most $a+b+N$ bits, since each entry is the sum of $N$ integers with at most $a+b$ bits. Assuming $b$ is bounded, then we can compute the product in time $O(a)$, where the constant depends on $b$ and $N$. So to multiply $n$ matrices whose entries have size $b$, this takes at most time $O(n^2)$. This gives the $O(n^2)$ estimate in Moshe’s answer.

Note that due to recent advances, multiplication of numbers of size $a$ takes time at most $a\log a$, although sub-$a^2$ algorithms have been known for a while. So multiplying matrices whose entries use at most $a$ bits takes time $O(a\log a)$, where the constant depends on $N$.

A more efficient procedure in theory to multiply $n$ things is to divide and conquer. For clarity, let’s consider the worst case where $n=2^m$. First compute the products $A= A_{i_1}\cdots A_{i_{2^{m-1}}}$ and $B=A_{i_{2^{m-1}+1}}\cdots A_{i_n}$. These matrices have entries of size (number of bits) $C n/2=C2^{m-1}$ for some constant $C$ depending on $\{A_1,\ldots,A_k\}$. Computing $AB =A_{i_1}\cdots A_{i_n}$ takes time $O(n/2 \log(n/2))=O(2^{m-1} (m-1)) $. By induction, computing these products in terms of 4 products of length $2^{m-2}$ takes time $O(2^{m-2} (m-2))$, but there are two matrices, so time $O(2^{m-1}(m-2))$. At the $i$th step, we multiply $2^{i-1}$ pairs of matrices of size $O(2^{m-i})$, which takes time $2^{i-1}\cdot O(2^{m-i}(m-i))=O(2^{m-1}(m-i))$. Thus, we get total time $O(2^{m-1} ((m-1)+(m-2)+\cdots + 1))=O(2^{m-1} m^2)= O(n\log^2 n)$.

For the general case, we multiply $A=A_{i_1}\cdots A_{i_{\lceil n/2\rceil}}$ and $B=A_{i_{\lceil n/2\rceil +1}}\cdots A_{i_n}$. We get a similar estimate, but our computation tree may be shorter since some of the branches terminate in the identity. In any case, at the $i$th step we multiply at most $2^{i-1}$ pairs of matrices of size at most $\approx n/2^i$, and hence we get a similar time bound of $O(n\log^2n)$. Maybe another way to think about it is that we can assume that $A_1=I$, so to compute $A_{i_1}\cdots A_{i_n}$, we append $2^{\lceil\log_2 n\rceil-n}$ copies of $A_1$ and use the procedure described in the previous paragraph. But $2^{\lceil\log_2 n\rceil}\leq 2n$, so this still takes time $O(n\log^2n)$.