4
$\begingroup$

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?

$\endgroup$
7
  • 1
    $\begingroup$ Let $G$ be a hyperbolic group. Then $G$ has a Dehn algorithm which (as you said yourself) can be used to solve the word problem. Therefore the word problem is solvable in $G$. That answers your question. (If you are actually interested in algorithms to solve the word problem in practice then they exist too, but that would be a different question.) $\endgroup$ – Derek Holt Mar 30 '20 at 15:48
  • 1
    $\begingroup$ Use $\langle X\rangle$ for $\langle X\rangle$. $\endgroup$ – Shaun Mar 30 '20 at 16:00
  • 1
    $\begingroup$ Your problem seems to be "given an arbitrary presentation of a hyperbolic group, how can I solve the word problem?". Well, let $\langle X\mid R\rangle$ be your presentation. First construct the Dehn presentation $\langle Y\mid S\rangle$ (the existence proof is constructive); in doing so you also construct an isomorphism $\phi:\pi_1(\langle X\mid R\rangle)\rightarrow \pi_1(\langle Y\mid S\rangle)$, which is defined by the images of the elements of $X$. Therefore, if you want to know if a word $W\in F(X)$ is trivial then you verify if the word $\phi(W)$ is trivial via Dehn's algorithm. $\endgroup$ – user1729 Mar 30 '20 at 16:00
  • 2
    $\begingroup$ As I said in my previous comment, the statement that the word problem is solvable in hyperbolic groups is a purely theoretical statement which the authors have proved. Although it is possible to compute the list of $(u_i,v_i)$ from the presentation, this is not the best approach to solving the word problem in practice, because that list may be impossibly long - also, it is not particularly easy to compute $\delta$ just from the presentation. There is a practical quadratic time algorithm for solving the word problem that makes use of the automatic structure of the group. $\endgroup$ – Derek Holt Mar 30 '20 at 16:34
  • 2
    $\begingroup$ @Al-HasanIbnAl-Hasan You're right, Bridson and Haefliger don't construct them (I wonder if I saw them constructed in a different proof of the theorem?). They can be constructed quite easily though, using a more geometric way of solving the word problem (which holds in every presentation): roughly, if $W=1$ in $G$ then there is a computable bound on the number of relators needed to "fill" the word $W$ (see Section 2.3 of Gromov's essay). You can use this observation to compute the $v_i$, and hence compute your Dehn presentation. $\endgroup$ – user1729 Mar 30 '20 at 16:49
3
$\begingroup$

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 :-) )

$\endgroup$

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.