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$.

  • 2
    $\begingroup$ If you restrict to irreducible 3-manifolds then "most" have automatic fundamental groups (the only exceptions are Sol and Nil-manifolds). This gives you some "explicit" bounds. See "Word processing in groups." $\endgroup$ – Moishe Kohan Dec 18 '20 at 17:02
  • 1
    $\begingroup$ In SOL the Dehn function is exponential but the word problem is very efficiently solvable. The assertion, sometimes heard, that the Dehn function is a measure of the complexity of the word problem is quite misleading. Actually, I'd tend to believe that the $\pi_1$ of every compact 3-fold (possibly with boundary) embeds into a group with quadratic Dehn function (but I don't think this is the easiest/ most efficient approach to algorithms). $\endgroup$ – YCor Dec 18 '20 at 19:02
  • 1
    $\begingroup$ I don't understand the last paragraph: there should be a quantifier for $l$. $\endgroup$ – YCor Dec 18 '20 at 19:04
  • 4
    $\begingroup$ A uniform treatment of the word problem in 3-manifold groups is given here: arxiv.org/abs/1609.06253 However, the issues of computational complexity are not addressed. $\endgroup$ – Ian Agol Dec 20 '20 at 19:11
  • 1
    $\begingroup$ @dodd -- presumably you are worried about the compact case with boundary, rather than the non-compact case addressed in YCor's comment. Compact 3-manifolds with boundary are retracts of their doubles, which are closed. This usually makes it easy to reduce from the compact case to the closed case. $\endgroup$ – HJRW Dec 23 '20 at 16:22

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.

  1. 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.

  2. 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.

  • $\begingroup$ Thank you, this is helpful $\endgroup$ – Ben Cooper Dec 19 '20 at 3:18
  • 5
    $\begingroup$ If you multiply $n$ bounded matrices in $SL(3,Z)$ you get matrices of exponential size, i.e., exponents have $\sim n$ digits. The multiplication of a single such matrix with a single bounded matrix takes time $\sim n$. So it looks like the total time is likely to be $O(n^2)$ rather than $O(n)$. $\endgroup$ – YCor Dec 19 '20 at 7:07
  • $\begingroup$ @YCor: Right, I was careless. I will correct the answer once I am back to my computer. $\endgroup$ – Moishe Kohan Dec 19 '20 at 22:40
  • $\begingroup$ Some graph manifolds virtually fiber, and hence their fundamental groups are (virtually) the subgroup of a mapping class group, which is automatic. So they also have a quadratic time solution to the word problem. doi.org/10.2307/2118637 But I think that there are graph manifolds that are neither cubulated nor virtually fibered. $\endgroup$ – Ian Agol Dec 20 '20 at 19:15
  • 2
    $\begingroup$ @dodd: Afaik, linearity is an open problem (for graph-manifolds without metrics of nonpositive curvature). As for Dehn function, it provides only an upper bound on complexity of the WP, as I explain, one can do better. $\endgroup$ – Moishe Kohan Dec 20 '20 at 23:43

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)$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.