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

  • 1
    $\begingroup$ 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$. $\endgroup$ – Steven Stadnicki May 3 '17 at 18:49
  • 2
    $\begingroup$ 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. $\endgroup$ – Derek Holt May 3 '17 at 22:18
  • $\begingroup$ 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! $\endgroup$ – nihil May 4 '17 at 13:03
  • $\begingroup$ 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). $\endgroup$ – YCor May 5 '17 at 10:30
  • $\begingroup$ Oh I see Derek already pointed this. You should have edited. $\endgroup$ – 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.


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.