7
$\begingroup$

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?

$\endgroup$
9
  • 9
    $\begingroup$ It is not decidable in general since it would allow you to solve the word problem (given an element $w$, just apply it to the subgroups $\langle w \rangle$ and $\langle w \rangle$; their intersection is trivial if and only if $w$ is trivial). On the other hand, it is decidable for free groups; indeed, using the algorithm described in Stallings's paper "The topology of finite graphs", you can compute the rank of the intersection of two finitely generated subgroups of a free group. $\endgroup$ Mar 9, 2015 at 3:31
  • $\begingroup$ Yes, the problem is obviously undecidable for groups with unsolvable word problem, and the question was about the groups with solvable word problem. The precise formulation of the problem is as follows. Let G=<A; R>, where A is finite, R is computably enumerable, and G has solvable word problem. Given finite sets of group words V and W over A, decide whether the subgroups of G generated by V and W have trivial intersection. Clearly decidability of the problem does not depend on the choice of the presentation <A;R> of G. $\endgroup$
    – owb
    Mar 9, 2015 at 16:09
  • $\begingroup$ As Andy let me know, Stalling's non-trivial result implies decidability of the problem for free non-abelian groups. Is anything known about this problem for finitely generated nilpotent groups, free solvable groups, etc.? Are there known examples of finitely generated (or even finitely presented) groups with solvable word problem for which the problem above is undecidable? Isn't such an example the group F x F, where F is a finitely generated free non-abelian group? $\endgroup$
    – owb
    Mar 9, 2015 at 16:11
  • $\begingroup$ In the negatively curved world (eg hyperbolic groups, free groups etc) the correct hypothesis is that the subgroup should be not just finitely generated but quasiconvex (in some suitable sense). For these subgroups, Stallings' techniques argument in free groups can be generalized (see a recent paper of Kharlampovich--Myasnikov--Weil). The Rips consruction argument I described in my answer shows that some hypothesis along these lines is necessary. $\endgroup$
    – HJRW
    Mar 9, 2015 at 20:21
  • $\begingroup$ For rational subgroups of automatic groups (in the sense of Gersten-Short), one can check triviality of intersection provided one is given as part of the input the automata giving the rational structure (or the corresponding quasi-convexity constant wrt the regular cross-section). The set of normal forms from the regular cross-section of elements of each of the subgroups is a regular language and hence so is their intersection. But checking if a regular language is just the empty word is decidable. $\endgroup$ Mar 9, 2015 at 21:02

3 Answers 3

9
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ You just beat me to it! $\endgroup$
    – HJRW
    Mar 9, 2015 at 20:23
  • 1
    $\begingroup$ You beat me to the Rips construction. I was going to add that after I put up the first example. Probably leaving that out is why I beat you :) $\endgroup$ Mar 9, 2015 at 20:51
  • $\begingroup$ See my answer below, which strengthens Benjamin's answer. (I now have the rep points to comment!) I was busy playing ping-pong last night, hence why I'm 14 hours late in answering this question. $\endgroup$
    – MCC
    Mar 10, 2015 at 11:17
8
$\begingroup$

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.

$\endgroup$
0
3
$\begingroup$

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

$\endgroup$
2
  • 2
    $\begingroup$ Isn't this what my added statement says except that I didn't emphasize that one of the subgroups is fixed? $\endgroup$ Mar 10, 2015 at 11:58
  • $\begingroup$ Ah, I didn't read your added statement closely enough. So it seems that my answer is merely an elaboration of your answer; I've re-labeled it accordingly. $\endgroup$
    – MCC
    Mar 10, 2015 at 15:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.