TY - JOUR
T1 - Algorithms for matrix groups and the Tits alternative
AU - Beals, Robert
N1 - Funding Information:
* Research conducted while visiting IAS and DIMACS and supported in part by an NSF Mathematical Sciences Postdoctoral Fellowship and by the Alfred P. Sloan foundation. These results have been announced previously in Proc. 36th IEEE FOCS, 1995, pp. 593 602.
PY - 1999/4
Y1 - 1999/4
N2 - Tits has shown that a finitely generated matrix group either contains a nonabelian free group or has a solvable subgroup of finite index. We give a polynomial time algorithm for deciding which of these two conditions holds for a given finitely generated matrix group over an algebraic number field. Noting that many computational problems are undecidable for groups with nonabelian free subgroups, we investigate the complexity of problems relating to matrix groups with solvable subgroups of finite index. For such a group G, we are able in polynomial time to compute a homomorphism φ such that φ(G) is a finite matrix group and the kernel of φ is solvable. If, in addition, G has a nilpotent subgroup of finite index, we obtain much stronger results. For such groups, we show how to effectively compute an encoding of elements of G such that the encoding length of an element obtained as a product of length ≤l over the generators is O(log l) times a polynomial in the input length. This result is the best possible; it has been shown by Tits and Wolf that if a finitely generated matrix group does not have a nilpotent subgroup of finite index. then the number of group elements expressible as words of length l over the generators grows as cl for some constant c>1 depending on G. For groups with abelian subgroups of finite index, we obtain a Las Vegas algorithm for several basic computational tasks, including membership testing and computing a presentation. This generalizes recent work of Beals and Babai, who give a Las Vegas algorithm for the case of finite groups, as well as recent work of Babai, Beals, Cai, Ivanyos, and Luks, who give a deterministic algorithm for the case of abelian groups.
AB - Tits has shown that a finitely generated matrix group either contains a nonabelian free group or has a solvable subgroup of finite index. We give a polynomial time algorithm for deciding which of these two conditions holds for a given finitely generated matrix group over an algebraic number field. Noting that many computational problems are undecidable for groups with nonabelian free subgroups, we investigate the complexity of problems relating to matrix groups with solvable subgroups of finite index. For such a group G, we are able in polynomial time to compute a homomorphism φ such that φ(G) is a finite matrix group and the kernel of φ is solvable. If, in addition, G has a nilpotent subgroup of finite index, we obtain much stronger results. For such groups, we show how to effectively compute an encoding of elements of G such that the encoding length of an element obtained as a product of length ≤l over the generators is O(log l) times a polynomial in the input length. This result is the best possible; it has been shown by Tits and Wolf that if a finitely generated matrix group does not have a nilpotent subgroup of finite index. then the number of group elements expressible as words of length l over the generators grows as cl for some constant c>1 depending on G. For groups with abelian subgroups of finite index, we obtain a Las Vegas algorithm for several basic computational tasks, including membership testing and computing a presentation. This generalizes recent work of Beals and Babai, who give a Las Vegas algorithm for the case of finite groups, as well as recent work of Babai, Beals, Cai, Ivanyos, and Luks, who give a deterministic algorithm for the case of abelian groups.
UR - http://www.scopus.com/inward/record.url?scp=0032631460&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=0032631460&partnerID=8YFLogxK
U2 - 10.1006/jcss.1998.1614
DO - 10.1006/jcss.1998.1614
M3 - Article
AN - SCOPUS:0032631460
SN - 0022-0000
VL - 58
SP - 260
EP - 279
JO - Journal of Computer and System Sciences
JF - Journal of Computer and System Sciences
IS - 2
ER -