# (un)decidability in matrix groups

Given a collection of matrices $S=\{M_1, \dots, M_k\}$ in (say) $SL(n, Z), \ n>2$ does $S$ generate $SL(n, Z)?$

Similar are questions are undecidable for $n\geq 4$ (eg, given a set $S$ as above, is a given matrix in the subgroup generated by $S$) but I cannot find any reference for the above.

For $n=2$ all questions of this sort are reasonably efficiently decidable.

EDIT (in response to @Misha's interesting comments).

It is not clear that Mihailova tells you that the generation problem is undecidable. I believe that it IS a result of Baumslag, Miller, Short that this is undecidable for some word-hyperbolic groups (see MR1246477 (94i:20053) Baumslag, G.(1-CCNY); Miller, C. F., III(5-MELB); Short, H.(1-CCNY) Unsolvable problems about small cancellation and word hyperbolic groups. (English summary) Bull. London Math. Soc. 26 (1994), no. 1, 97–101. 20F10 (20F06) ) [they use the Rips construction @Misha alludes to].

For $n\geq 4,$ there are the non-free Zariski-dense examples of Margulis-Soifer (1979). I haven't read their paper in detail, but it seems that their technique does not work in $SL(3, \mathbb{Z}).$ However, there is the nice result of Stephen Wang: Wang, Stephen(1-HAV) Representations of surface groups and right-angled Artin groups in higher rank. (English summary) Algebr. Geom. Topol. 7 (2007), 1099–1117. 20F36 (20F65 57M25)

Which can presumably be generalized to other RAAGs.

Geometric finiteness: I think the action of $SL(n)$ on the positive semidefinite cone was studied first by Minkowski (for $SL(2)$ the PSD cone is just the light cone in the usual Minkowski space), and I had actually implemented this. The program usually run forever.

AND ALSO Mihailova's counterexample for generalized word problem (AKA membership problem) uses SEVEN generators. Undoubtedly she had tried to get it down lower, but apparently failed. It turns out that in many applications, we have two generators, in which case it seems that even the generalized word problem is open even for $F_2 \times F_2.$

-
@Igor, it is probably unknown. The only hope is if the following statement is true: if $H$ is a subgroup of $SL_n(\mathbb{Z})$ and every natural homomorphism $H\to SL_n(\mathbb{Z}/m\mathbb{Z}$ is surjective, then $H=SL_n(\mathbb{Z})$. I do not know the answer to this question, but it seems easier than yours. If the answer is yes", then your question has positive answer too. The membership problem for subgroups of $SL_n(\mathbb{Z})$, $n\ge 4$, is trivially undecidable because $F_2\times F_2\lt SL_4(\mathbb{Z})$. But it has nothing to do with your question. – Mark Sapir Dec 2 '10 at 2:39
@Mark, for $n\ge 3$ there are even finitely generated free subgroups of $SL(n,\mathbb Z)$ which are profinitely dense, i.e. map onto every finite quotient of $SL(n,Z)$. This was proved by Soifer and Venkataramana, see MR1745714. So this approach doest not work. I do not know if the problem asked by Igor is decidable. – Denis Osin Dec 2 '10 at 7:13
I don't know the answer to this question, but I'd like to shamelessly advertise my paper 'On the difficulty of presenting finitely presentable groups', with Bridson. We prove various undecidability results for matrix groups, including the fact that you can't compute a finite presentation even if you are promised that one exists. – HJRW Dec 2 '10 at 23:11
To get some perspective: Is it true that for any finitely presented word-hyperbolic group, it's decidable whether a finite set of elements generate the group? What's known about this case (generalizing SL(2,z)). Is there any developed notion of a "geometrically finite" subgroup of SL(n,R)? I.e. it's tempting (but probably futile) to try to construct a fundamental domain for the group action on SL(n,R)/SO(n) by some sort of reduction technique to see if the volume is bigger than that for SL(n,Z). This idea might stand a chance for negatively curved homogeneous spaces (although I don't see it). – Bill Thurston Dec 28 '10 at 2:41
@Denis: in fact there is a much earlier paper of Steve Humphries where he constructs an explicit set of transvections in $SL(n, \mathbb{Z}), n>2$ which generate a free subgroup such that every congruence quotient is onto. (J. Algebra, 1988) – Igor Rivin Apr 6 '11 at 16:10

Igor, the following is not an answer but, I think, is as close to an answer as one can get at this time. First of all, Bill Thurston is making two good points:

(a) There is no algorithm in the context of hyperbolic groups, as it follows from the Rips' 1982 construction.

(b) At this stage, there is no good notion of geometrically-finite discrete group actions on higher rank symmetric spaces, but people are working on it. For instance, "Anosov actions" of Guichard and Wienhard is a stab at defining analogues of "convex cocompact" actions (although, I think, their definition is too restrictive, but it is the best that we have at this point). In the case of discrete subgroups of $SL(n, {\mathbb R})$ one can (very) tentatively define geometrically finite groups as ones which have finitely-sided "Dirichlet-Selberg" fundamental domains (the definition is too limited even in rank 1 case but is good enough for the purposes of what follows). These domains were introduced in Selberg's famous 1960 paper (and, I think, deserve to be better known) and have the (algorithmic) advantage of being defined by linear inequalities in the space of symmetric matrices. With this definition, Thurston's suggestion goes through as one can algorithmically construct such fundamental domains using Jorgensen's algorithm (that you probably know from the real-hyperbolic case): Each time you add a bisector you check if Poincare's fundamental domain conditions hold. Of course, if there is no finitely-sided domain, this algorithm runs forever.

(c) On the other hand, I think, already for $n=4$, there is no algorithm. The idea is to exploit Mikhailova-type subgroups $\Lambda$ in products $\Gamma=F_2\times F_2\subset SL(4, {\mathbb Z})$ (see Mark's comments). Because of such subgroups, there is no algorithm to determine if a finite subset $P\subset \Gamma$ generates $\Gamma$. The problem, of course, is that $\Gamma$ is too small (not even Zariski dense in $SL(4, {\mathbb R})$). The idea is to look for finite subsets $Q\subset SL(4, {\mathbb Z})$ so that $\langle \Gamma \cup Q\rangle$ generates $SL(4, {\mathbb Z})$ (or, at least, a finite-index subgroup), while $\langle \Lambda \cup Q\rangle$ generates an infinite-index subgroup in $SL(4, {\mathbb Z})$. This is easier said than done, but, in principle, there is no reason to think that such sets do not exist. For instance, this idea does work for some lattices in $SO(4,1)$, where instead of $F_2\times F_2$ you take a lattice from $SO(3,1)$ (uniformizing a hyperbolic 3-manifold fibered over the circle) and as a subgroup $\Lambda$ you take a normal surface subgroup in $\Gamma$. This does not prove anything, of course, for $SL(4, {\mathbb Z})$ since "life is hard" in higher rank.

(d) Situation could be radically different for $SL(3, {\mathbb Z})$. Suppose that $\Lambda$ is an infinite index fg torsion-free sugroup of $SL(3, {\mathbb Z})$ which is Zariski dense in $SL(3, {\mathbb R})$. Sadly, at this point we know exactly two constructions of such subgroups: (1) free subgroups (Tits), (2) closed surface subgroups (originally due to Kac and Vinberg but, now, there are more constructions due to Alan Reid and maybe others). Both constructions are very "tame" and, I think, lead to geometrically finite subgroups. It is then not impossible that every fg subgroup of $SL(3, {\mathbb Z})$ is geometrically finite.

-
@Misha: these are very interesting comments. See edits in the question. – Igor Rivin Mar 11 '12 at 1:02

@Igor: The membership in 2-generated subgroups of $F\times F'$ (where $F,F'$ are free) is decidable. Take any 2-generated subgroup $H=\langle (a,b), (c,d)\rangle$ of $F\times F'$. First we may suppose that $H$ is a subdirect product, that is $F$ is generated by $a,c$, $F'$ is generated by $b,d$. By Baumslag-Roseblate, $H$ is a pullback of two homomorphisms $f,g: F\to F/N$ where $N$ is the intersection of $H$ with the $F\times \{1\}$, and the $F$ is identified with $F\times \{1\}$. The membership problem is equivalent to the word problem in $F/N$. The subgroup $N$ is then obtained as follows. Let $L$ be the subgroup of $F'$ consisting of all words $w(x,y)$ such that $w(b,d)=1$. Then $N$ is the image of $L$ under the endomorphism $x\to a, y\to b$. The group $L$ is non-trivial if and only if $b,d$ commute. Hence $b^m=d^n$ for some $m,n$. Thus $L$ is generated as a normal subgroup by two words $[x,y], x^my^{-n}$. Hence $F'/L$ (which is isomorphic to $F/N$) is Abelian (in fact cyclic) and the word problem in $F'/L$ is decidable. Hence the membership problem for $H$ is decidable (in linear time because the distortion of $H$ is equivalent to the Dehn function of $F/N$ by our theorem with Olshanskii).

-
Thanks! I will try to digest this... – Igor Rivin Apr 4 '12 at 18:36
It could be true that even for 3-generated subgroups the membership problem is decidable. It probably reduces to the word problem in 1-related groups (which is decidable by Magnus). – Mark Sapir Apr 4 '12 at 18:51

Just some minor comments on the problem of testing whether a finitely generated subgroup H of SL(n, Z) equals SL(n, Z), n > 2. This is a partial case of the arithmeticity testing (AT) problem, i.e., testing whether H has finite index in SL(n, Z). To our knowledge it is not known whether AT problem is decidable; but most likely, in general, the answer is negative (some arguments for this have been provided by C. F. Miller III). If so, the AT problem is semidecidable: if H does happen to be arithmetic then it is possible to verify that, by, e.g., the Todd-Coxeter procedure. So, if H is known to be arithmetic, one can test whether H = SL(n, Z). However, the obstacle here is that Todd-Coxeter is impractical (the index of H in SL(n, Z) could be arbitrarily large). An alternative approach is based on the congruence subgroup property, i.e., construction of a principal congruence subgroup in H (for which Todd-Coxeter is not required). Note that in the class of solvable algebraic groups, the AT problem is decidable and a practical algorithm is available.

A very brief (although now somewhat outdated) survey on decidable problems in the class of finitely generated linear groups is available in Section 3 of London Math. Soc. Lecture Note Ser. 387 (2011) 256–270. Also, a series of papers by F. Grunewald and D. Segal on decidable problems for explicitly given arithmetic groups may be of interest with regard to your question (e.g., see `Some general algorithms. I. Arithmetic groups', Ann. of Math. (2) 112(3) (1980) 531–583.)

-