6
$\begingroup$

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

Improve this question
$\endgroup$
11
  • 3
    $\begingroup$ Please stop deleting your questions - it is impolite to various people who have made helpful comments. $\endgroup$
    – Derek Holt
    Commented Apr 22, 2021 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
    Commented Apr 22, 2021 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
    Commented Apr 22, 2021 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
    Commented Apr 22, 2021 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
    Commented Apr 22, 2021 at 12:49

1 Answer 1

Reset to default
5
$\begingroup$

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.

Improve this answer
$\endgroup$

You must log in to answer this question.