Writing an algorithm solving the word-problem in hyperbolic groups

Question

I am reading in the “Metric Spaces of Non-Positive Curvature Book by André Haefliger and Martin Bridson”, on Dehn's Algorithm (Chapter III.Γ, p.449).

Let $\mathcal{A}$ be a finite generating set of a group $\Gamma$. A list of pairs of words $(u_{1},v_{1}),...,(u_{n},v_{n})\in\Gamma\times\Gamma$ is called “satisfies the conditions of Dehn's Algorithm” if the following hold: 1) $u_{i}=v_{i}$ in $\Gamma$; 2) $\forall i=1,...,n$, $|u_{i}|>|v_{i}|$, where $|u|$ denotes the length of $u$ as a word in the free group $F(\mathcal{A})$; 3) $\forall w\in\Gamma$, $[w=1$ in $\Gamma$ implies that at least one of the $u_{i}$'s is a subword of $w]$.

A finite presentation $\langle\mathcal{A}\mid\mathcal{R}\rangle$ of a group $\Gamma$ is called Dehn presentation if $\mathcal{R}=\{u_{1}v_{1}^{-1},...,u_{n}v_{n}^{-1}\}$, where $(u_{1},v_{1}),...,(u_{n},v_{n})\in\Gamma\times\Gamma$ satisfy the conditions of Dehn's Algorithm.

Given such a presentation it is obvious that the word problem is solvable $\Gamma$.

Assume now that the Cayley graph $C_{\mathcal{A}}(\Gamma)$ is $\delta$-hyperbolic, where $\delta\geq0$. I want to understand is it possible to construct an algorithm which solves the word-problem in $\Gamma$. In the book above, Thm. 2.6, p.450, the authors proved that $\Gamma$ admits Dehn presentation. Namely, They proved that if $k>8\delta$ is a fixed integer, $u_{1},...,u_{n}$ are all the words in $F(\mathcal{A}) $with $|u_{i}|\leq k$, and $v_{i}$, $i=1,...,n$, is a word of minimal length in $F(\mathcal{A})$ such that $v_{i}=u_{i}$ in $\Gamma$, then $\langle\mathcal{A}\mid u_{1}v_{1}^{-1},...,u_{n}v_{n}^{-1}\rangle$ is a Dehn presentation of $\Gamma$.

My question is to know if there exists an algorithm, which given (as variables) $\delta>0$, and a finite presentation $\langle\mathcal{A}\mid\mathcal{D}\rangle$ of $\delta$-hyperbolic group $\Gamma$, the algorithm plots a list $(u_{1},v_{1}),...,(u_{n},v_{n})\in\Gamma\times\Gamma$ which satisfy the conditions of Dehn's Algorithm (that is, finds a geodesic word for every word of length $\leq8\delta+1$)? If no, then why do “they” say that the word problem is solvable in hyperbolic groups?

Answer 1

In order to compute a Dehn presentation for a hyperbolic group you need to have a solution to the word problem, at least within the $8\delta+1$-ball centred at the origin. This is because we need to compute the words $v_i$, and in the proof by Bridson and Haefliger these are not constructed (however, I have a nagging feeling that I saw them constructed in a different proof of the theorem). Given a solution to the word problem you find the $v_i$ by verifying if $w_i=u$ for every word $u$ shorter than $w_i$, and then picking the shortest such word (clearly this procedure can be optimised!).

There are other solutions to the word problem. In Gromov's essay (Section 2.3, p28) he gives a more geometric way of solving the word problem (which holds in every presentation). Roughly, Gromov says that if $W=1$ in $G$ then there is a computable bound (dependent only on the length $|W|$) on both the number of relators and the length of the relators needed to "fill" the word $W$. Therefore, if you want to check whether or not a word if trivial then you first compute this bound and then check if your word is one of the finitely many words permitted by this bound. Please note that this algorithm is theoretically nice, but (as Derek Holt points out in the comments) it is a useless algorithm in practice.

Indeed, Derek Holt points out a more computationally effective way of solving the word problem. Basically, hyperbolic groups are automatic and automatic groups have a really nice solution to the word problem. The kbmag package is relevant here (GitHub, GAP), which will allow your computer to try and find an automatic structure for an input group, and hence solve the word problem. (You should look at the author of this package, and then maybe re-read some of the comment to your question with this added knowledge :-) )