## DIMACS TR: 95-30

## Algorithms for matrix groups and the Tits alternative

### Author: Robert Beals

**
ABSTRACT
**

Tits has shown that a finitely generated linear 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 linear groups with solvable subgroups of finite index.
For such a group G, we are able in polynomial time to compute a
homomorphism phi such that phi(G) is a finite matrix group and
the kernel of phi is solvable. If in addition G has a nilpotent
subgroup of finite index, we obtain much stronger results. These
include an effective encoding of elements of G such that the
encoding length of an element obtained as a product of length
L over the generators is 0(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 c^L 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.

Paper available at:
ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1995/95-30.ps.gz

DIMACS Home Page