# If G has solvable word problem, then word metric $d_{S}(e,w)$ is computable.

I was recently given feedback on an assignment in Geometric Group Theory that the following proposition is false:

If $G = \langle S \rangle$ is finitely generated and has solvable word problem, then for every word $w \in F(S)$, $d_{S}(e,w)$ is computable

(where $e$ is identity element of $G$ and $F(S)$ is the free group on $S$)

Here's an attempeted proof of the statement, where do I go wrong?

By definition of word metric $d_{S}$, $d_{S}(e,w) = |v|_{S} \leq |w|_{S}$ for some $v \in F(S)$ such that $v =_{G} w$. To find such a $v$, enumerate all words $v \in F(S)$ of length $|v|_{S} \leq |w|_{S}$. Since $S$ is a finite set and $|w|_{S}$ is finite, there are only finitely many such $v$. At each step in the enumeration, use $G$'s solvable word procedure to determine if $v =_{G} w$ (i.e $vw^{-1} =_{G} e$). Terminate the enumeration with the $v$ of shortest length. The length of $v$ is $d_{S}(e,w)$.

• At first glance this looks entirely sensible to me. You should even be able to go further and say that $d_S(v,w)$ is computable for any words $v$ and $w$. – Steven Stadnicki May 3 '17 at 18:49
• I agree: your proof is correct.But you need to assume that $S$ is finite - you did not actually say that! Also the relator set $R$ does not seem relevant, so it is not clear why you introduced it. – Derek Holt May 3 '17 at 22:18
• Fair point, I assumed $G$ was finitely-generated, but not necessarily that $S$ was such a finite generating set. Thanks for the affirmation, maybe there was a mistake! – nihil May 4 '17 at 13:03
• It makes little sense to assume that "$\langle S|R\rangle$ has solvable word problem", since $R$ has nothing to do with this (the word problem does not refer to $R$ on both the input and the output). – YCor May 5 '17 at 10:30
• Oh I see Derek already pointed this. You should have edited. – YCor May 5 '17 at 10:39

If $S$ is not assumed to be finite, one has to be careful in the formulation "$G=\langle S\rangle$ is finitely generated with solvable word problem". If one understands that $G$ has solvable word problem (in the usual sense, w.r.t some/any finite generating subset), then there are trivial counterexamples if it is not assumed that $S$ is finite.

For instance, let $G=\mathbf{Z}$. Let $I$ be a subset of $\mathbf{N}$; define $s(n)=2$ for $n\in I$ and $s(n)=3$ for $n\notin I$. Define $u(n)=n!$ for $n\ge 1$ odd and $u(n)=s(n/2)(n-1)!$ for $n$ even.

So $u(1)=1$, $u(2)\in\{2,3\}$, $u(3)=6$, $u(4)\in\{12,18\}$, $u(5)=120$, etc.

Then $u$ is injective; since $u_1=1$, the image of $u$ generates $\mathbf{Z}$. Let the free group on $\mathbf{N}_{>0}$ map to $\mathbf{Z}$ by the assignment $s_i\mapsto u(i)$. Then the word length of the image of $s_i^2$ is 1 if and only if $n\in I$. In particular, if $I$ is not a recursive subset, then the word length is not computable.

Edit: If one understands that $G$ has solvable word problem with respect to the family $S$, then it slightly more tricky when $S$ is infinite. (When $S$ is finite, the word length is computable, as you proved it.)

But a variant of the previous example works. Let $G$ be an arbitrary infinite f.g. group with solvable word problem (for instance $\mathbf{Z}$). Fix a finitely generated free group $F$ with a surjective homomorphism to $G$, and let $(s_n)_{n\in\mathbf{N}}$ be an arbitrary computable sequence in $F$, starting with the family of free generators. Then the corresponding word problem (determining whether an element of $F_\mathbf{N}$ maps to a trivial element of $G$) is solvable, by computation inside $F$.

On the other hand, we can assume that the image of the family is a recursively enumerable, but non-recursive subset of $G$. In this case, the word length is not computable, since one cannot decide whether the length of an element is 1.