MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
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
up vote 4 down vote accepted

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...

share|cite|improve this answer
@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. – Benjamin Steinberg Sep 14 '12 at 2:05

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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