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?
$\begingroup$
$\endgroup$
3
-
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$– YCorMar 23, 2015 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 HoltMar 23, 2015 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, 2015 at 17:37
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
1
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.
