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?
$\begingroup$
$\endgroup$
5
-
4$\begingroup$ Yes, it's impossible for $n>3$ by Mikhailova's construction. Open problem, essentially due to Serre, for $n=3$. $\endgroup$– MishaCommented Sep 13, 2012 at 13:10
-
5$\begingroup$ 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! $\endgroup$– MishaCommented Sep 13, 2012 at 13:25
-
1$\begingroup$ @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$ ... $\endgroup$– user6976Commented Sep 13, 2012 at 22:06
-
$\begingroup$ 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$. $\endgroup$– user6976Commented Sep 13, 2012 at 22:08
-
$\begingroup$ Mark, you are right, I was sloppy here. $\endgroup$– MishaCommented Sep 14, 2012 at 0:04
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
1
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...
-
1$\begingroup$ @Misha, this is a nice answer. There is a very slight misstatement. There is no such thing as a single finite presentation for which it is undecidable whether the group is finite or not. Either the Turing machine that says yes or the one which says no is correct. What is undecidable is the uniform problem. Similarly finite presentability is undecidable as a uniform problem, not for a fixed subgroup. On the other hand the generalized word problem is unsolvable for a fixed subgroup. $\endgroup$ Commented Sep 14, 2012 at 2:05