8
$\begingroup$

I will start with a general algorithmic question:

Question. (A faithfulness decision problem.) Suppose that $G, H$ are finitely-presented groups with decidable word problem. Is injectivity decidable for homomorphisms $f: G\to H$ (defined by the images of generators of $G$)?

[A very minor side issue: I am not even sure if this decision problem has an established name. For some reason, Max Dehn did not consider it.]

The non-injectivity problem is trivially semidecidable.

More specifically, I am interested in decidability of faithfulness for homomorphisms from (finitely generated, nonabelian) free groups to (nonelementary) hyperbolic groups $H$. The decision problem then becomes:

Freedom problem. Do given elements $g_1,...,g_n\in H$ generate a rank $n\ge 2$ free subgroup?

Things that I know:

If $H$ is locally quasiconvex (or, more generally, all finite rank free subgroups of $H$ are undistorted), then the freedom problem is decidable. The same applies to the injectivity problem for homomorphisms from general finitely-presented groups $G\to H$ to locally quasiconvex hyperbolic groups. The injectivity problem is decidable if $H$ is the fundamental group of a compact hyperbolic 3-manifold.

It is natural to expect that the decidability of the freedom problem in hyperbolic groups $H$ is closely related to distortion of free subgroups in $H$. One can conjecture that if every f.g. free subgroup in $H$ is recursively distorted then the freedom problem is decidable. One can also conjecture that hardness of the freedom problem correlates to the degree of distortion of free subgroups. (For instance, for "hyperbolic hydra groups" of Brady-Dison-Riley, the distortions of some free subgroups are given by Ackerman functions.) I do not know how to approach any of these conjectures.

So, my question is if anything else is known about these problems.

One more thing: There is a "dual" problem about surjectivity of group homomorphisms. I am not asking about this one. (It is more related to the subgroup membership problem and more is known about it.)

Improve this question
$\endgroup$
4
  • $\begingroup$ This question seems to be about a special case of your general question. I seem to remember asking Martin Bridson about the decidability of the freeness (freedom?) of subgroups of hyperbolic groups, and I believe that he thought that it was unknown but likely to be undecidable. $\endgroup$
    – Derek Holt
    Commented Jan 1, 2020 at 20:34
  • $\begingroup$ BTW if $H$ is hyperbolic and $G$ is a f.p. group with non-solvable word problem, the question of injectivity for homomorphisms $G\to H$ is quite easy to solve :) $\endgroup$
    – YCor
    Commented Jan 2, 2020 at 9:35
  • $\begingroup$ @YCor: Yes, of course; ditto for infinite simple groups, groups containing $Z^2$, etc., which is why I assumed that $G$ is free, so we have an ample supply of homomorphisms. $\endgroup$
    – Misha
    Commented Jan 2, 2020 at 13:52
  • $\begingroup$ You might like to compare with Question 9.4 of arxiv.org/abs/1003.5117 . Bridson and I asked if the finite presentation problem is (uniformly) solvable over hyperbolic groups. If the freedom problem is unsolvable in some hyperbolic group, then the answer to our question is (as expected) "no". $\endgroup$
    – HJRW
    Commented Jan 2, 2020 at 15:12

1 Answer 1

Reset to default
4
$\begingroup$

As regards the first question (with $H$ not hyperbolic), it has a negative answer even with $G$ free:

This question has an answer saying that there exists a f.p. $H$ group with solvable word problem in which injectivity of homomorphisms $\mathbf{Z}\to H$ is undecidable. (Hence injectivity of homomorphisms $F_n\to H\ast F_{n-1}$ is undecidable too.)

Nevertheless for $H$ hyperbolic, it is decidable whether an element has infinite order (because the conjugacy problem is solvable and there are finitely many finite order conjugacy classes, so it is enough to test conjugacy with each representative).

Improve this answer
$\endgroup$
4
  • 1
    $\begingroup$ (Please don't accept this answer, because the freeness problem in hyperbolic groups is more interesting.) $\endgroup$
    – YCor
    Commented Jan 1, 2020 at 23:10
  • $\begingroup$ Ah, I see. Thank you! $\endgroup$
    – Misha
    Commented Jan 2, 2020 at 3:35
  • 1
    $\begingroup$ Can't you test finiteness in a hyperbolic group without using the conjugacy problem? Since there are only finitely many finite conjugacy classes of finite order there is a fixed number $n$ so that every element of finite order has order dividing $n$. To check finiteness you just raise an element to the power $n$ and use the word problem to check if you get $1$. $\endgroup$
    – Benjamin Steinberg
    Commented Jan 3, 2020 at 0:49
  • $\begingroup$ @BenjaminSteinberg (You mean test finite order.) Indeed, you're right. It looks like a simpler approach. $\endgroup$
    – YCor
    Commented Jan 3, 2020 at 3:16

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .