×

Fundamental algorithms for permutation groups. (English) Zbl 0785.20001

Lecture Notes in Computer Science 559. Berlin etc.: Springer-Verlag (ISBN 3-540-54955-2). XII, 238 p. (1991).
The area of Computational Group Theory (CGT for short) comprises the design, (complexity) analysis, implementation and application of group theoretical algorithms. CGT is a fast growing part of group theory, drawing from and being applied to many parts of group theory, from the theory of finitely presented groups to representation theory, as demonstrated by a flood of original publications as well as conferences. However, except for some surveys, it is lacking so far a comprehensive description.
G. Butler’s book, published in 1991 but showing in parts that it is written during the years before, is the first attempt of such a comprehensive description of at least a wide part of CGT. The author has further complicated his difficult task by trying to address a variety of different audiences at the same time. The book appeared in the series “Lecture Notes in Computer Science” and accordingly, assuming zero knowledge on groups, starts with the group axioms. It is rather obvious that this level of preknowledge can not be maintained if a book of less than 250 pages intends to reach the newest state of development of algorithms for permutation groups. The author tries to overcome this difficulty by switching at certain stages to a more narrative introduction of mathematical facts, but it seems questionable to the reviewer whether with this method he can really achieve the goal of leading group theoretical novices to an appreciation and understanding of the later parts of the book, so in fact these later parts of the book only address a much more sophisticated reader.
There are 2 dominating features of the style of the book:
1. Algorithms are given at length using a Pascal like command structure.
2. Each section is followed by extensive bibliographical remarks.
To this reviewer these bibliographical remarks are perhaps the most valuable information to be taken from the book, while some of the rather extensive descriptions of rather simple algorithms and overaccurate counting of steps in algorithms are too wasteful in comparison to the short treatments towards the end.
The book does not quite stick to its title, the first part “Small groups” of 6 sections and 55 pages deals with elementary handling of what nowadays might be called black box groups. Part 2 of further 8 chapters and 100 pages is the central part presenting the basic methods for the handling of permutation groups. Schreier-Sims method for the construction of a stabilizer chain with some of its variations, base change, backtrack search techniques, primitivity and regularity tests. The rest of the book, further 5 sections of about 75 pages, comes under the title of homomorphisms and their use, it does cover techniques using the natural homomorphisms of permutation groups, but also contains a section on polycyclic presentations and their use for the study of \(p\)- groups and finite soluble groups, and in a last brief section gives an outlook on recent developments like double coset enumeration, cohomology groups, and the method of Luks, Kantor and Neumann for finding composition series of permutation groups.
As indicated, to this reviewer the book appears to be rather inhomogeneous, going into too trivial details in some parts while leaving out important considerations in others. Nevertheless its appearance, aiming at a summary of important developments, is to be welcomed.

MSC:

20-04 Software, source code, etc. for problems pertaining to group theory
20B40 Computational methods (permutation groups) (MSC2010)
68W30 Symbolic computation and algebraic computation
20-01 Introductory exposition (textbooks, tutorial papers, etc.) pertaining to group theory
20F05 Generators, relations, and presentations of groups
20C40 Computational methods (representations of groups) (MSC2010)
PDFBibTeX XMLCite
Full Text: DOI