(un)decidability in matrix groups

Question

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

Answer 1

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.

Answer 2

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

Answer 3

I do not know direct answer to your problem, but I will think about this as it is close to the area of problems which we are currently working on.

Although I would like to comment that not all questions are "reasonably efficiently decidable" for SL(2,Z) as most of known to me problems for SL(2,Z) are at least NP-hard, meaning that none of these problems have efficient (polynomial time) solutions unless P=NP.

The membership for Identity Matrix is NP-hard for a finitely generated matrix semigroup from SL(2,Z) and there is no even simple NP brute-force algorithm as there is a class of semigroups where the shortest identity could require exponential length of products to reach the identity. See: Paul C. Bell, Igor Potapov: On the Computational Complexity of Matrix Semigroup Problems. Fundam. Inform. 116(1-4): 1-13 (2012) Similar results exist for Mortality problem (membership of the Zero matrix) Paul C. Bell, Mika Hirvensalo, Igor Potapov: Mortality for 2×2 Matrices Is NP-Hard. MFCS 2012: 148-159

Recently we proved that the Vector Reachability for SL(2, Z) is decidable (in general it is harder to check than membership as there is an infinite set of matrices that can connect two points and decidability of the membership is not lead to vector reachability problem decidability). Potapov, Pavel Semukhin: Vector Reachability Problem in SL(2, Z). MFCS 2016: 84:1-84:14 http://drops.dagstuhl.de/opus/volltexte/2016/6492/

The other fresh 2016 result is the proof that the membership for nonsingular matrix semigroup from $Z^{2x2}$ is decidable. http://arxiv.org/abs/1604.02303

In relation to the membership in SL(2,Z) we recently managed to improve the complexity for the membership problem from PSPACE to NP, the main idea of the paper that we are able to operate effectively with compressed versions of matrices from SL(2,Z) by application of number of new results about structural properties of matrix products.

---

For undecidability side the membership problem for a semigroup generated by matrices from SL(2,H) or even for a semigroup of double quaternions is undecidable http://www.sciencedirect.com/science/article/pii/S0890540108000771

Moreover the membership of the identity matrix for semigroup generated by matrices from SL(4,Z) is undecidable: Paul C. Bell, Igor Potapov: On the Undecidability of the Identity Correspondence Problem and its Applications for Word and Matrix Semigroups. Int. J. Found. Comput. Sci. 21(6): 963-978 (2010) Archive vestion: arxiv.org/abs/0902.1975 See Problem 10.3 http://press.princeton.edu/math/blondel/solutions.html but the same problem for 3x3 is sill open.

Answer 4

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