# Decision Problem for finitely generated subgroups

Suppose $G$ is a finitely generated subgroup of $GL_n(Z)$, $n\ge 3$. I suspect that there is no decision procedure for deciding whether or not such $G$ is finitely presented. How can this proved?

-
Yes, it's impossible for $n>3$ by Mikhailova's construction. Open problem, essentially due to Serre, for $n=3$. –  Misha Sep 13 '12 at 13:10
Even more interestingly, there are examples due to Bridson and HW where you have a fp subgroup for which one cannot compute a finite presentation! –  Misha Sep 13 '12 at 13:25
@Misha: Your second comment cannot be correct. For any given finitely generated subgroup the question of finding a finite presentation is not a "mass" problem. So the statement "we cannot..." does not make sense. Moreover, if you consider the mass problem where the input is a finitely presented subgroup of $SL_n(\mathbb{Z})$ and the output its finite presentation, then it is not clear that this problem is undecidable for any given $n$. Bridson and HW proved that here are recursive sequences of hyperbolic groups $\Gamma_n$ and of finite sets $S_n⊂\Gamma_n×\Gamma_n$ for which the group $A_n$ ... –  Mark Sapir Sep 13 '12 at 22:06
cont: generated by $S_n$ is f.p. but there is no algorithm that, given $n$ computes a finite presentation of $A_n$. They use a Dani Wise version of the Rips' construction to construct $\Gamma_n$. So each $\Gamma_n$ is linear but the degree of the linear presentation of $\Gamma_n$ depends on $n$. –  Mark Sapir Sep 13 '12 at 22:08
Mark, you are right, I was sloppy here. –  Misha Sep 14 '12 at 0:04

Various forms of this question were discussed on MO several times, see e.g. here. The key is that $SL(4,Z)$ contains $H=F_2\times F_2$, direct product of rank 2 free groups. Then for every finitely-presented group $Q$ (i.e., a group $Q$ with a given finite presentation), there is an epimorphism $H\to Q$ with finitely-generated kernel $K$, see e.g. here; this is called Mikhailova's construction. Unless $Q$ is finite, $K$ is not finitely-presented, see the same link. Now, take a finitely-presented group $Q$ for which it is undecidable if it is finite or not. Then for $K$ it will be undecidable if it is fp or not.
Situation is different for $GL(3,Z)$ as it contains no direct products of free nonabelian groups. It is an open problem due to J.-P. Serre (1979 or so, depending how you count), if $SL(3,Z)$ is coherent (i.e., if every finitely-generated subgroup of $SL(3,Z)$ is also finitely-presentable). Situation with $GL(3,Z)$ is the same, of course. At this moment, all known (say, torsion-free) f.g. subgroups of $SL(3,Z)$ fall into the following classes:
a. Finite index. b. Closed surface subgroups. c. Free subgroups. d. Non-Zariski dense in $SL(3,R)$ subgroups (abelian subgroups and semidirect products of free groups of rank $1\le r< \infty$ with $Z^2$).
All of such subgroups are finitely-presented, of course, so, for all what we know, $SL(3,Z)$ is coherent, in which case your question has obvious answer. If $SL(3,Z)$ is not coherent, who knows...