Let $f:G\to H$ be a homomorphism of finitely presented groups with decidable word problems.

Assume you are given explicit finite presentations for both $G$ and $H$ and you are given the words to which $f$ sends the generators of $G$.

Question. Is it possible that no algorithm exists deciding, given $w\in H$, whether $f^{-1}(w)$ is empty or not?

P.S. Having explicit finite presentations is important https://arxiv.org/abs/1003.5117

  • 3
    $\begingroup$ Please stop deleting your questions - it is impolite to various people who have made helpful comments. $\endgroup$ – Derek Holt Apr 22 at 9:51
  • 1
    $\begingroup$ By the discussion in your earlier deleted question, it would be enough to find a group $H$ with a specific presentation and normal subgroup $K$ with specified generators such that $H/K$ has unsolvable word problem. $G$ can be a free group. I think the examples of Rips in which $H$ satisfies arbitrarily stringent small cancellation conditions does that. $\endgroup$ – Derek Holt Apr 22 at 9:58
  • 2
    $\begingroup$ It is known that there exist finitely presented groups $H$ with solvable word problem that have a finitely generated subgroup $K$ with unsolvable subgroup membership problem. For example, Mikhailova has shown that $H=F_2\times F_2$ has such a subgroup. Then $G$ could be a free group and $f$ could be a homomorphism whose image is $K$, and there's no way to tell whether a given element of $H$ lies in the image of $f$. $\endgroup$ – Jim Belk Apr 22 at 10:02
  • 1
    $\begingroup$ In the example I am talking about (see here ), $H/K$ is any group with unsolvable word problem with specific presentation, $H$ is a small cancellation group with explicit presentation derived from that of $H/K$, and $K = \langle b_1,b_2 \rangle$, where $b_1$ and $b_2$ are generators in that presentation. So we can take $G$ free of rank $2$ with generators mapping to $b_1$ and $b_2$. $\endgroup$ – Derek Holt Apr 22 at 11:05
  • 1
    $\begingroup$ This seems essentially the same question as yesterday and Jim Belk's answer here is exactly @YCor's answer from yesterday from the comments. We said in the comments last time that this is exactly equivalent to the generalized word problem for $H$ since you can always replace $G$ by a free group on the original generators of $G$ (and so finite presentedness of $G$ is not necessary and then any finitely generated subgroup can be the image. $\endgroup$ – Benjamin Steinberg Apr 22 at 12:49

It is known that there exists a finitely presented group $H$ with solvable word problem that has a finitely generated subgroup $K$ whose subgroup membership problem is unsolvable. For example, Mikhailova has shown that the product $F_2\times F_2$ of non-abelian free groups has such a subgroup (see here).

Now let $k_1,\ldots,k_n$ be the generators for $K$, let $G$ be a free group with $n$ generators $x_1,\ldots,x_n$, and let $f\colon G\to H$ be the homomorphism that maps each $x_i$ to $k_i$. Then a given element $h\in H$ has the property that $f^{-1}(h)$ is nonempty if and only if $h\in K$, and therefore it is undecidable in general whether $f^{-1}(h)$ is nonempty.


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.