Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



Testing polycyclicity of finitely generated rational matrix groups

Authors: Björn Assmann and Bettina Eick
Journal: Math. Comp. 76 (2007), 1669-1682
MSC (2000): Primary 20F16, 20-04; Secondary 68W30
Published electronically: March 9, 2007
MathSciNet review: 2299794
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: We describe algorithms for testing polycyclicity and nilpotency for finitely generated subgroups of $ \mathrm{GL}(d,\mathbb{Q})$ and thus we show that these properties are decidable. Variations of our algorithm can be used for testing virtual polycyclicity and virtual nilpotency for finitely generated subgroups of $ \mathrm{GL}(d,\mathbb{Q})$.

References [Enhancements On Off] (What's this?)

  • 1. B. Assmann.
    Polenta - Polycyclic presentations for matrix groups, 2006.
    A refereed GAP 4 package, see [14].
  • 2. B. Assmann and B. Eick.
    Computing polycyclic presentations for polycyclic rational matrix groups.
    Accepted by J. Symb. Comput., 2005. MR 2178086 (2006g:20044)
  • 3. L. Babai, R. Beals, and D. Rockmore.
    Deciding finiteness of matrix groups in deterministic polynomial time.
    In Proc. of International Symposium on Symbolic and Algebraic Computation ISSAC '93, pages 117-126. (Kiev), ACM Press, 1993.
  • 4. G. Baumslag.
    Lecture notes on nilpotent groups.
    Amer. Math. Soc., Providence, 1971. MR 0283082 (44:315)
  • 5. G. Baumslag, F. B. Cannonito, D. J. S. Robinson, and D. Segal.
    The algorithmic theory of polycyclic-by-finite groups.
    J. Alg., 142:118-149, 1991. MR 1125209 (92i:20036)
  • 6. R. Beals.
    Improved algorithms for the Tits alternative.
    In W. M. Kantor and A. Seress, editors, Groups and Computation III, pages 63-77. (DIMACS, 1999), 2001. MR 1829471 (2002g:20085)
  • 7. L. E. Dickson.
    Algebras and their arithmetics.
    University of Chicago, 1923.
  • 8. B. Eick.
    Algorithms for polycyclic groups.
    Habilitationsschrift, Universität Kassel, 2001.
  • 9. D. F. Holt, B. Eick, and E. A. O'Brien.
    Handbook of Computational Group Theory.
    Discrete Mathematics and its Applications. CRC Press, 2005. MR 2129747 (2006f:20001)
  • 10. E. Khukhro.
    $ p$-Automorphisms of Finite $ p$-Groups, volume 246 of Lecture Note Series.
    London Mathematical Soc., 1998. MR 1615819 (99d:20029)
  • 11. A. J. Mal'cev.
    On certain classes of infinite soluble groups.
    Mat. Sb., 28:567-588, 1951. MR 0043088 (13:203k)
  • 12. G. Ostheimer.
    Practical algorithms for polycyclic matrix groups.
    J. Symb. Comput., 28:361-379, 1999. MR 1716421 (2000h:20004)
  • 13. D. Segal.
    Polycyclic Groups.
    Cambridge University Press, Cambridge, 1983. MR 713786 (85h:20003)
  • 14. The GAP Group.
    GAP-Groups, Algorithms and Programming., 2006.

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2000): 20F16, 20-04, 68W30

Retrieve articles in all journals with MSC (2000): 20F16, 20-04, 68W30

Additional Information

Björn Assmann
Affiliation: Centre for Interdisciplinary Research in Computational Algebra (CIRCA), University of St Andrews, North Haugh, St Andrews, KY16 9SS Fife, Scotland

Bettina Eick
Affiliation: Institut Computational Mathematics, Fachbereich Mathematik und Informatik, Technische Universität Braunschweig, Braunschweig, Germany

Keywords: Finitely generated matrix group, Tits' alternative, polycyclicity, nilpotency, Mal' cev correspondence
Received by editor(s): February 21, 2006
Received by editor(s) in revised form: August 3, 2006
Published electronically: March 9, 2007
Additional Notes: The first author was supported by a Ph.D. fellowship of the “Gottlieb Daimler- und Karl Benz-Stiftung" and the UK Engineering and Physical Science Research Council (EPSRC)
The second author was supported by a Feodor Lynen Fellowship from the Alexander von Humboldt Foundation and by the Marsden Fund of New Zealand via grant UOA412
Article copyright: © Copyright 2007 American Mathematical Society

American Mathematical Society