Decision problem on triviality of intersection of two subgroups

Question

What is known about the following decision problem?

Given two finite sets in a finitely generated group G, decide whether the subgroups generated by them have trivial intersection.

Is this problem decidable for a free non-abelian group G?

Answer 1

Let $F$ be a free group of rank $2$. If the intersection triviality problem is decidable for $F\times F$, then using the Mikhailova construction, it would be decidable given a finitely presented group $G=\langle X\mid R\rangle$ and a word $w$ in $X$ whether $w$ has infinite order in $G$. This latter problem was proved undecidable in G. Baumslag, W. Boone, and B. Neumann, Some unsolvable problems about elements and subgroups of groups. Math. Scand. 7 (1959), 191–201.

Indeed, embed $F_X\times F_X$ in $F\times F$. The subgroup $E=\{(u,v)\in F_X\times F_X\mid u=v\ \text{in}\ G\}$ is finitely generated. It intersects $\langle (1,w)\rangle$ trivially if and only if $w$ has infinite order in $G$.

So intersection triviality is undecidable for $F\times F$, although this group has decidable word problem.

I assume this is what the OP was getting at in his/her comment.

Added In G. Arzhantseva, J.F. Lafont, and A. Minasyan, Isomorphism versus commensurability for a class of finitely presented groups, examples of finitely presented groups with solvable word problem are given for which it is undecidable if an element has infinite order. Belk and Bleak proved the Brin-Thompson group nV has unsolvable torsion problem. Thus both intersecting subgroups can be chosen to have decidable membership problem.

Answer 2

The OP asks for examples of groups with solvable word problem for which the intersection problem is undecidable. Such examples certainly exist. Here's one way to construct one.

Let $G$ be a finitely presented, torsion-free group with undecidable word problem. The Rips construction provides a short exact sequence

$1\to K\to\Gamma\to G\to 1$

where $\Gamma$ is torsion-free hyperbolic (in particular, fp, with solvable word problem and many other nice properties) and $K$ finitely generated. In particular, any cyclic subgroup $\langle w\rangle$ intersects $K$ non-trivially if and only if $w\in K$, which is undecidable.

With a little more work, one can combine this idea with the Mihailove construction mentioned by Benjamin Steinberg in his answer to provide counterexamples in which the subgroup $K$ is finitely presented (this time inside a product of hyperbolic groups). This uses the 1-2-3 theorem of Baumslag--Bridson--Miller--Short.

The above techniques are a standard machine for producing finitely generated and presented examples of pathological subgroups of otherwise fairly well behaved groups. For example, you can arrange for $\Gamma$ to be linear over $\mathbb{Z}$ etc.

Answer 3

Allow me to elaborate on Benjamin's answer:

Proposition: There is a fixed finitely presented group $H$, and fixed finite set of words $S$ on the generators of $H$ for which $\langle S\rangle \leq H$ has solvable subgroup membership problem, such that the problem of determining if the subgroup generated by one word $\langle w \rangle$ intersects $\langle S \rangle$ non-trivially in $H$ is algorithmically undecidable.

Proof: There exists a finitely presented group $G=\langle X|R \rangle$ for which the word problem is solvable, but for which the torsion problem, of determining if a word has infinite order, is unsolvable. This is a consequence of Theorem A in D. Collins, The word, power, and order problem in finitely presented groups, in Word Problems, eds. W. W. Boone, F. B. Cannonito and R. C. Lyndon, 401–420 (1973). (On top of this theorem, one needs the additional observation that having solvable word problem means one can effectively compute the order of a torsion element). So now take the group $H$ to be $F_{X} \times F_{X}$, and take the set $S$ to be the finite set $\{(x_{1}, x_{1}), \ldots, (x_{n}, x_{n}), (r_{1}, 1) \ldots, (r_{m}, 1)\}$, and thus $\langle S \rangle =\{(u,v) \in F_{X}\times F_{X}\ |\ u=v \ \ in \ \ G \}$. Since $G$ has solvable word problem, we have that $\langle S \rangle \leq H$ has solvable membership problem. Moreover, as Benjamin observed, for an arbitrary word $z \in G$, we have $\langle (1,z) \rangle$ intersects $\langle S \rangle$ trivially if and only if $z$ has infinite order in $G$ (the latter being undecidable).

I suppose the above should really be a comment to Benjamin's answer, but at the time I couldn't add comments as I had <50 reputational points.

-Maurice