9
$\begingroup$

Is the following algorithmic problem known to be decidable/undecidable?

Input: a finite group presentation $P$.

Decide: is the commutator subgroup of the group presented by $P$ finitely generated?

$\endgroup$
  • 3
    $\begingroup$ It's undecidable, by a classical argument. Indeed, a finitely generated group $G$ is nontrivial if and only if the commutator subgroup of $G\ast\mathbf{Z}$ is infinitely generated. Hence if we could solve this problem by some machine $X$, we would solve the triviality problem of $G$ by inputting in $X$ the presentation with an additional generator. $\endgroup$ – YCor Mar 23 '15 at 17:15
  • 3
    $\begingroup$ The solution is easy when you see it, but not obvious, so I would not vote to close it. $\endgroup$ – Derek Holt Mar 23 '15 at 17:32
  • 7
    $\begingroup$ I agree with Derek. I think the question is fine for MO, and rather than close it because it's been answered in a comment, it would be better to turn the comment into an actual answer (and I'd be pleased if @YCor does the honors). I spoke further on this here: meta.mathoverflow.net/a/2111/2926 $\endgroup$ – Todd Trimble Mar 23 '15 at 17:37
16
$\begingroup$

It's undecidable.

Lemma: a group $G$ is nontrivial if and only if the free product $H=G\ast\mathbf{Z}$ has an infinitely generated derived subgroup.

Proof: assume $G$ finitely generated and nontrivial. The kernel $N$ of the canonical epimorphism $H\to\mathbf{Z}$ is isomorphic to $G^{\ast\mathbf{Z}}$ and hence is infinitely generated. Since $H/[H,H]$ is finitely generated abelian, so is $N/[H,H]$; if $[H,H]$ were finitely generated, so would be $N$, a contradiction. Hence $[H,H]$ is infinitely generated. In case $G$ is infinitely generated and if by contradiction $[H,H]$ is finitely generated, then its generators belong to $G_1\ast\mathbf{Z}$ for some proper subgroup $G_1$ of $G$, which is obviously a contradiction.$\Box$

The result then from the fact that if we have a Turing machine $X$ whose input is a finite presentation $P$ and whose answer is yes or no according to whether the group presented by $P$ has a finitely generated derived subgroup, then if we input in $X$ the presentation obtained from $P$ by adding a generator, the output is yes or no according to whether the group presented by $P$ is trivial. Thus the resulting machine solves the triviality problem, and it is known that there is no such machine.

$\endgroup$
  • $\begingroup$ Yes, it looks easy now. Thank you Yves! $\endgroup$ – suitangi Mar 24 '15 at 19:10

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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