# Modifying Dehn's algorithm to allow equal length replacements?

I'm an analyst trying to understand a certain class of finitely presented groups (one example is below) so it's quite likely this question is naive but I hope it is at least intelligible. Given a finitely presented group $G$ with generators $g_1, \dots g_n$ and relations $R=\{r_1,\dots r_m\}$ one would like to solve the word problem in $G$; of course it is not solvable in general, but is solvable for certain classes of $G$. In particular there is Dehn's algorithm, which (as I understand it) runs like this: given a word $w$ in the generators, with length $|w|$, if one finds a subword $v$ of $w$ such that $vu^{-1}\in R$ and $|u|<|v|$ then replace $v$ by $u$ and continue. If no such word $v$ exists, stop. (The length-decreasing condition guarantees that the algorithm will halt.) Say Dehn's algorithm works if, whenever $w=e$ in $G$, then Dehn's algorithm successfully reduces $w$ to $e$. (One should probably have some symmetry conditions on the set of relators (that they be closed under cyclic permutations, etc.); for the purposes of this question assume whatever symmetry you need.)

It is known that Dehn's algorithm works for surface groups (this was Dehn's original result), and it has since been extended to groups satisfying some kinds of "small cancellation" conditions, word-hyperbolic groups, etc. My question is about the following modification of Dehn's algorithm and which, if any, groups for which it is known to work. The idea is simply to modify the original algorithm to allow substitutions $v\to u$ if $vu^{-1}\in R$ and $|u|\leq |v|$, rather than only $|u|<|v|$. (Since everything is finite, it seems clear enough that one can specify some particular method of searching through the word so that the algorithm still halts. That is, at each step first look for length-reducing substitutions; if there are none, look for length-preserving substitutions, there are only finitely many possible so one may enumerate the possibilities and specify some rule for picking one. After each length-preserving substitution, check again for length-reducing substitutions. If there is one, continue, if none of the possible length-preserving substitutions allow for a subsequent length-reducing substitution, halt.)

A motivating example is the following: consider the group $G$ on six generators $g_1, g_2, g_3, h_1, h_2, h_3$ and relations $$R=\{ g_jh_kh_j^{-1}g_k^{-1}:j,k =1,2,3 \text{ distinct}\};$$ enlarge $R$ to be closed under inverses and cyclic permutations. It is not hard to see that Dehn's algorithm fails in $G$: in particular one may verify that the word $$w=h_2 h_1^{-1} h_3 h_2^{-1} h_1 h_3^{-1}$$ has the form $$w=g_1^{-1} rstg_1$$ with $r,s,t\in R$ so $w=e$ in $G$. But Dehn's algorithm does not reduce $w$ since all the relators have length 4, and no 3-letter subword of a relator appears in $w$ (a 3-letter subword of a relator must contain both $g$'s and $h$'s). However if we allow length-preserving substitutions such as $h_2h_3^{-1}\to g_2^{-1}g_3$ then the algorithm gets "unstuck": $$h_2 h_1^{-1} h_3 h_2^{-1} h_1 h_3^{-1} \to h_2 h_1^{-1} g_2^{-1}g_3 h_1 h_3^{-1}\to g_1^{-1}g_3 h_1 h_3^{-1} \to e.$$ I suspect (but don't yet have a proof) that the modified Dehn's algorithm works for this group.

Question: are there known classes of groups (beyond those for which Dehn's algorithm works) for which the modified Dehn's algorithm (with substitutions $|u|=|v|$ allowed) solves the word problem?

• I suspect there are no other such group clases known: I imagine one can well-(partial-)order the words and run a variant of Dehn's algorithm using the well-order. There may be issues of definability, and so one can't just use "any" well-order. In particular, I think one can define a group G' and a translation of rules so that length-preserving rules in G become length reducing rules in G', and get essentially the same results. Gerhard "Is Just Guessing About This" Paseman, 2014.02.24 – Gerhard Paseman Feb 24 '14 at 19:36
• Remark : A group $G$ has a presentation for which there is a classical Dehn algorithm if and only if $G$ is hyperbolic. You indicated that you know the "if" direction; for the "only if" direction, it is clear that if there is a presentation where the classical Dehn algorithm works, then the group has a linear Dehn function (which is known to be equivalent to hyperbolicity). – Andy Putman Feb 24 '14 at 20:17
• A group has a presentation satisfying Dehn's algorithm iff it's Gromov-hyperbolic. So the question eventually is whether there is a non-hyperbolic group with a presentation satisfied the "modified" Dehn algorithm. – YCor Jan 28 at 15:29
• It should be emphasized that one main advantage of Dehn's algorithm is its efficiency. The example of $\mathbf{Z}^2$ (mentioned by Derek) shows that the modified algorithm can be extremely inefficient: if we start with $x^ny^nx^{-n}y^{-n}$, most algorithm operations preserve the length and if we blindly do them, we probably have to do exponentially many until we get the right ones (those leading to a simplification). – YCor Jan 28 at 15:35

There are some other types of groups for which this type of algorithm would work. The easiest examples are abelian groups. For example, with the free abelian group of rank $$2$$, $$\langle x,y, \mid xy=yx \rangle$$, if you systematically make the substitutions $$y^ax^b \mapsto x^ay^b$$ with $$a,b = \pm 1$$, together with free reductions, then you can transform any word to the normal form $$x^iy^j$$ with $$i,j \in {\mathbb Z}$$.

This would work for all groups with a finite confluent rewriting system with respect to an ordering on words that respects length: the lenlex orderings are the most common. This includes surface groups, which you can do already, but this class of groups is closed under direct products, so you are getting some new examples.

This property is actually stronger than what you want - you don't require complete confluence, just confluence on the identity element. Unfortunately, unlike complete confluence, confluence on the identity is known to be undecidable for a general finite rewriting system.

I tried running the Knuth-Bendix completion algorithm on your $$6$$-generator example, but without success, so I don't know whether there is a modified Dehn's algorithm for that group.

But I did verify that it is an automatic group, which means that you can construct finite state automata that can solve the word problem in quadratic time, by reducing word to a normal form.

Added later: I have now checked HJRW's calculation computationally, and calculated an explicit isomorphism to the group $${\mathbb Z}^2 * F_2 = \langle a,b,c,d \mid ab=ba \rangle$$. This is

$$a \mapsto g_1g_3^{-1}$$, $$b \mapsto g_1 g_2^{-1}$$, $$c \mapsto h_1$$, $$d \mapsto g_1$$

with inverse

$$g_1 \mapsto d$$, $$g_2 \mapsto b^{-1}d$$, $$g_3 \mapsto a^{-1}d$$, $$h_1 \mapsto c$$, $$h_2 \mapsto d^{-1}b^{-1}dc$$, $$h_3 \mapsto d^{-1}a^{-1}dc$$.

• Thanks! As you can guess what I'd really like to do is solve the word problem here; I have come across automatic groups as a class in which the word problem is solvable--could you say more about how you verify it is automatic? Is there a theorem that applies here, or an algorithm that (sometimes) says a given group is automatic? – Mike Jury Feb 24 '14 at 23:05
• In this case, I just ran the programs to construct the automata, and they worked. I don't know of any theoretical result that applies to these groups in particular. The programs are available either as a standalone package or from GAP or Magma. – Derek Holt Feb 24 '14 at 23:26

In fact, we can describe your group $G$ quite explicitly.

The presentation has the property that each generator appears in exactly two relators. Therefore, the corresponding presentation complex $X$ is locally a surface everywhere except at the unique vertex. In particular, $X$ is homeomorphic to a surface $S$ with some number of points identified.

To find out how many points are identified, we need to compute the link of the vertex. This is exactly the Whitehead graph of the relators $R$, and can be done quite explicitly. If I did it correctly, it consists of two triangles and one hexagon; in particular, it has three components. (I did this in a hurry and may have done it incorrectly, but in any case it's a good exercise to do for yourself, and the same principles apply.)

Therefore, $S$ has a cell decomposition with three vertices, six edges and four three squares, giving $\chi(S)=0$ and so $S$ is a torus or a Klein bottle. (More explicitly, I think we can see that it is in fact a torus.) Since identifying a pair of vertices corresponds to taking a free product with $\mathbb{Z}$, we have

$G\cong \pi_1S*F_2$ ,

in which case G is in fact a hyperbolic group with torsion, and of course the word problem is easy to solve. Note that this does not contradict your observation that your presentation is not Dehn---as well as a Dehn presentation, hyperbolic groups have many non-Dehn presentations.

It's not too hard to see this explicitly by using two of the relators to eliminate two of the generators.

• Of course, your class probably don't all have this form. But if the relators are all of length four (as is the case here) then there's a good chance that there's some sort of uniform geometric solution to the word problem. – HJRW Feb 25 '14 at 13:51
• This is very helpful, I'm heartened at the prospect of being able to calculate explicitly. Indeed in the general case all of my relators have length four (though the number of relators will in general be quite a bit larger than the number of generators). Is there a reference you can point me to that describes these methods? – Mike Jury Feb 25 '14 at 14:13
• Well, the best-case scenario is that the Whitehead graph is triangle-free. In this case, the presentation complex is non-positively curved, which makes solving the word problem fairly straightforward. This doesn't seem to be the case here. The next-best case is that you can glue in higher-dimensional cubes to make the link of the vertex a flag complex - ie every 1-skeleton of an n-simplex (for n>1) in the Whitehead graph gets filled in. In this case, the resulting complex is again non-positively curved... – HJRW Feb 25 '14 at 21:24
• ... I haven't had a chance to think about whether this is possible in the case of your example. The standard reference is Metric spaces of non-positive curvature by Bridson and Haefliger, specifically the section on Gromov's link condition. It would help to know the next-simplest example in your class. – HJRW Feb 25 '14 at 21:26
• Thanks, both answers help a lot. The general case is $3n$ generators $a_1, a_2, a_3, b_1, b_2, b_3,\dots$ and relations $a_jb_kb_j^{-1}a_k^{-1}, b_jc_kc_j^{-1}b_k^{-1},\dots$ etc. Actually I think these groups can now be calculated using the explicit isomorphism found by Derek Holt; the $n^{th}$ group will be an amalgamated free product of the $(n-1)^{st}$ group with $\mathbb Z^2\ast F_2$. For example in the 9-generator case we get $(\mathbb Z^2\ast F_2)\ast_B(\mathbb Z^2\ast F_2)$ where $B$ is the subgroup generated by the $b_j$, which I think is isomorphic to $\mathbb Z^2\ast \mathbb Z$. – Mike Jury Feb 26 '14 at 13:09

Tits' solution to the word problem for Coxeter groups involves making subsitutions $$u\mapsto v$$ where $$|u|=|v|$$ and $$uv^{-1}\in R$$. Many (most) Coxeter groups are not hyperbolic, so (by Andy Putman's remark) the usual Dehn algorithm doesn't apply. See for example Section 3.4 of Mike Davis's book $$`$$The Geometry and Topology of Coxeter Groups'.