Baumslag, Cannonito, Robinson and Segal prove that the problem of determining whether or not a finitely generated subgroup of GL(n,Z) is polycyclic-by-finite is decidable and that the problem of testing membership in a polycyclic-by-finite subgroup of GL(n,Z) is also decidable ([BCRS]). In this report we extend these results by describing algorithms which appear to be suitable for computer implementation. Experimentation is needed to determine the range of input for which they are practical.
Our method is to first reduce each problem to the corresponding problem for triangularizable matrix groups. The reduction is an easy consequence of the result of Dixon ([Di1]) that subgroups of the p-congruence subgroup of GL(n,Z_p) are connected in the Zariski topology, where Z_p is the ring of p-adic integers for a prime p.
We then prove a structure theorem for triangularizable matrix groups
that allows us to decide whether or not a matrix group is
triangularizable and to reduce the problem of testing membership in a
polycyclic, triangularizable matrix group to the corresponding
problems for finitely generated abelian matrix groups and for finitely
generated unitriangular matrix groups. In the case of an abelian
matrix group we can find a presentation for the group, and our
membership test can be made constructive. For these results we rely
heavily on the work of Ge ([Ge]) concerning algorithms for
multiplicative subgroups of a number field. We also rely on an
algorithm of Beals ([Be2]) to decide whether or not a triangularizable
matrix group is polycyclic.
Paper available at:
ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1995/95-33.ps.gz
DIMACS Home Page