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. Björn Assmann and Bettina Eick, Computing polycyclic presentations for polycyclic rational matrix groups, J. Symbolic Comput. 40 (2005), no. 6, 1269–1284. MR 2178086, 10.1016/j.jsc.2005.05.003
  • 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. Gilbert Baumslag, Lecture notes on nilpotent groups, Regional Conference Series in Mathematics, No. 2, American Mathematical Society, Providence, R.I., 1971. MR 0283082
  • 5. Gilbert Baumslag, Frank B. Cannonito, Derek J. Robinson, and Dan Segal, The algorithmic theory of polycyclic-by-finite groups, J. Algebra 142 (1991), no. 1, 118–149. MR 1125209, 10.1016/0021-8693(91)90221-S
  • 6. Robert Beals, Improved algorithms for the Tits alternative, Groups and computation, III (Columbus, OH, 1999) Ohio State Univ. Math. Res. Inst. Publ., vol. 8, de Gruyter, Berlin, 2001, pp. 63–77. MR 1829471
  • 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. Derek F. Holt, Bettina Eick, and Eamonn A. O’Brien, Handbook of computational group theory, Discrete Mathematics and its Applications (Boca Raton), Chapman & Hall/CRC, Boca Raton, FL, 2005. MR 2129747
  • 10. E. I. Khukhro, 𝑝-automorphisms of finite 𝑝-groups, London Mathematical Society Lecture Note Series, vol. 246, Cambridge University Press, Cambridge, 1998. MR 1615819
  • 11. A. I. Mal′cev, On some classes of infinite soluble groups, Mat. Sbornik N.S. 28(70) (1951), 567–588 (Russian). MR 0043088
  • 12. Gretchen Ostheimer, Practical algorithms for polycyclic matrix groups, J. Symbolic Comput. 28 (1999), no. 3, 361–379. MR 1716421, 10.1006/jsco.1999.0287
  • 13. Daniel Segal, Polycyclic groups, Cambridge Tracts in Mathematics, vol. 82, Cambridge University Press, Cambridge, 1983. MR 713786
  • 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