zbMATH — the first resource for mathematics

Examples
Geometry Search for the term Geometry in any field. Queries are case-independent.
Funct* Wildcard queries are specified by * (e.g. functions, functorial, etc.). Otherwise the search is exact.
"Topological group" Phrases (multi-words) should be set in "straight quotation marks".
au: Bourbaki & ti: Algebra Search for author and title. The and-operator & is default and can be omitted.
Chebyshev | Tschebyscheff The or-operator | allows to search for Chebyshev or Tschebyscheff.
"Quasi* map*" py: 1989 The resulting documents have publication year 1989.
so: Eur* J* Mat* Soc* cc: 14 Search for publications in a particular source with a Mathematics Subject Classification code (cc) in 14.
"Partial diff* eq*" ! elliptic The not-operator ! eliminates all results containing the word elliptic.
dt: b & au: Hilbert The document type is set to books; alternatively: j for journal articles, a for book articles.
py: 2000-2015 cc: (94A | 11T) Number ranges are accepted. Terms can be grouped within (parentheses).
la: chinese Find documents in a given language. ISO 639-1 language codes can also be used.

Operators
a & b logic and
a | b logic or
!ab logic not
abc* right wildcard
"ab c" phrase
(ab c) parentheses
Fields
any anywhere an internal document identifier
au author, editor ai internal author identifier
ti title la language
so source ab review, abstract
py publication year rv reviewer
cc MSC code ut uncontrolled term
dt document type (j: journal article; b: book; a: book article)
Fundamental algorithms for permutation groups. (English) Zbl 0785.20001
Lecture Notes in Computer Science. 559. Berlin etc.: Springer-Verlag. 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-04Machine computation, programs (group theory)
20B40Computational methods (permutation groups)
68W30Symbolic computation and algebraic computation
20-01Textbooks (group theory)
20F05Generators, relations, and presentations of groups
20C40Computational methods (representations of groups)