GAP

Main Branches

Downloads  Installation  Overview  Data Libraries  Packages  Documentation  Contacts  FAQ  GAP 3 

References for Methods of Computational Group Theory

This page provides some guide to theoretical background material for the methods implemented in GAP and its packages.

The most comprehensive (and extremely well-written) textbook on computational group theory (excluding computational representation theory) is the

  • Handbook of Computational Group Theory [Ho05] by Derek Holt.

The Computer Algebra Handbook [GKW03] aims to provide an overview of the full field of computer algebra by individual articles written by different authors in the style of an encyclopedia. There are surveys on different areas and aspects as well as descriptions of program systems, a bibliography with over 2100 entries, and pointers to many conferences since 1979 and their proceedings. (It should be noted, however, that most articles of the handbook were already written about four years before its publication.) The two most relevant articles in our context are also available via the internet:

  • Computational Group Theory by Charles C. Sims (pp. 64-83 in [GKW03]), available as Postscript or PDF file from Selected Publications of Charles C. Sims (note that for reading the PDF file you will probably need acrobat6), and
     
  • Algorithms of Representation Theory by Gerhard Hiss (pp. 84-88 in [GKW03]), available as PDF file.

There are some monographs covering special areas:

  • Permutation Groups
    Greg Butler [Bu91] gives an elementary introduction. Ákos Seress [Se03] gives an up-to-date survey on permutattion group algorithms and analyses their complexity.
     
  • Finitely Presented Groups
    David Johnson's book [Jo97] is a very readable introduction to the general subject of fp groups touching computational aspects. The authoritative text on the subject of computing methods for fp groups is the book [Si94] by Charles C. Sims.
     
  • Polycyclic Groups
    There is no published textbook yet, the Habilitationsschrift [Ei01] of Bettina Eick is presently the most comprehensive source.
     
  • Representation Theory
    The book Representations of Groups, A Computational Approach by Klaus Lux and Herbert Pahlings [LP10] provides a joint development of both ordinary and modular representation theory together with the wealth of algorithms and their implementations that are playing such an important role in the recent development of the field. GAP programs are used and documented throughout the book. An important feature is that the book is accompanied by an own website http://www.math.rwth-aachen.de/~RepresentationsOfGroups/ which i.a. provides errata, solutions for the numerous exercises in the book and additional material. This feature will in particular allow further updating of this important text.
    Still, another good source are the two survey papers [LP91] and [LP99].
     
  • Lie Algebras
    The book [deG00] by Willem A. de Graaf covers the standard topics of Lie Algebra theory with strong emphasis on algorithmic aspects.
     
  • Algebraic Number Theory and Commutative Algebra
    These areas, some methods of which are used in GAP and its packages, are e. g. presented by the book [Co00] on computational number theory by Henri Cohen and the book [GP02] on commutative algebra by Gerd-Martin Greuel and Gerhard Pfister.

We refrain from listing any of the several hundred papers having contributed to the development of algorithms in computational group theory. Rather we refer to the bibliographies of the quoted books and the Algebra Database in BibTeX, containing many such titles, which has been compiled by Eamonn O'Brien.

Bibliography

Bu91
Gregory Butler,
Fundamental Algorithms for Permutation Groups.
Lecture Notes in Computer Science, vol. 559, Springer Verlag 1991, xii + 238 p.
Co00
Henri Cohen,
A Course in Computational Number Theory.
Graduate texts in mathematics, vol. 138, Springer Verlag, 4th ed. 2000, xx + 545 p.
deG00
Willem A. de Graaf,
Lie Algebras: Theory and Algorithms.
North-Holland mathematical Library, vol. 56, Elsevier 2000, xii + 393 p.
Ei01
Bettina Eick,
Algorithms for Polycyclic Groups.
Habilitationsschrift, Universität Kassel, 2000, 113 p.
GKW03
Johannes Grabmeier, Erich Kaltofen, Volker Weispfenning, eds.,
Computer Algebra Handbook.
Springer Verlag 2003, xx + 637 p.
GP02
Gerd-Martin Greuel, Gerhard Pfister
A SINGULAR Introduction to Commutative Algebra.
Springer Verlag 2003, xvii + 588 p.
Ho05
Derek F. Holt,
Handbook of Computational Group Theory.
In the series 'Discrete Mathematics and its Applications',
Chapman & Hall/CRC 2005, xvi + 514 p.
Jo97
David L. Johnson,
Presentations of Groups.
LMS Student Texts, vol. 15, Cambridge University Press, 2nd ed. 1997, x + 216 p.
LP91
Klaus Lux, Herbert Pahlings,
Computational Aspects of Representation Theory of Finite Groups.
pp. 37-64 in: Representation Theory of Finite Groups and Finite-Dimensional Algebras, G. O. Michler, C. M. Ringel, eds., 1991.
LP99
Klaus Lux, Herbert Pahlings,
Computational Aspects of Representation Theory of Finite Groups II.
pp. 381-397 in: Algorithmic Algebra and Number Theory, B. H. Matzat, G.-M. Greuel, G. Hiss, eds., 1999.
LP10
Klaus Lux, Herbert Pahlings,
Representations of Groups, A Computational Approach.
Cambridge Studies in Advanced Mathematics 124, Cambridge University Press 2010, x+460 p.
Se03
Ákos Seress
Permutation Group Algorithms.
Cambridge Tracts in Mathematics, vol 152, Cambridge University Press 2003, ix + 264 p.
A sample of the book, including contents and introduction, can be looked at in the web.
Si94
Charles C. Sims,
Computation with finitely presented groups.
Encyclopedia of mathematics and its applications, vol. 48, Cambridge University Press 1994, xiii + 604 p.