Modifying Dehn's algorithm to allow equal length replacements?

Question

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?

Answer 1

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

Answer 2

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.

Answer 3

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