# Empty preimage under homomorphism of finitely presented groups with decidable word problems

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

• 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. – Derek Holt Apr 22 at 9:58
• 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$. – Jim Belk Apr 22 at 10:02
• 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$. – Derek Holt Apr 22 at 11:05
• 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. – 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.