Welcome to MathOverflow

Question

4

2

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?

flag	asked Sep 13 at 12:29 solovei 338●5

4

Yes, it's impossible for $n>3$ by Mikhailova's construction. Open problem, essentially due to Serre, for $n=3$. – Misha Sep 13 at 13:10

5

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 at 13:25

1

@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 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 at 22:08

Mark, you are right, I was sloppy here. – Misha Sep 14 at 0:04

Misha · Accepted Answer · 2012-09-13 20:48:26Z UTC

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

Decision Problem for finitely generated subgroups

Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

1 Answer

You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.