Fundamental Algorithms for Permutation Groups

Permutation groups are mathematical objects—and a rich setting for studying how algebraic structure can make computation more efficient. Gregory Butler’s Fundamental Algorithms for Permutation Groups develops that connection from the ground up, showing how group-theoretic information shapes algorithms and how those algorithms can be understood, justified, and improved.

From small groups to large computations

The opening part builds a working foundation in group theory before exploring computations with small groups: generating and listing elements, searching for elements with particular properties, using Cayley graphs to find defining relations, and constructing subgroup lattices. Rather than treating these procedures as black boxes, Butler develops them incrementally and explains how each new idea can refine an algorithm.

How permutations act on points

The focus then shifts to techniques specific to permutation groups. Orbits and Schreier vectors lead into questions of regularity and primitivity, followed by stabiliser chains, bases, and strong generating sets. These structures provide ways to represent and compute with groups without simply enumerating every element.

Search, structure, and Schreier–Sims

Backtrack search is a major theme, with examples involving centralisers, normalisers, intersections, and set stabilisers. The discussion also considers choosing a useful base, changing bases, and preprocessing information for repeated searches. Later chapters develop the Schreier–Sims method and examine its complexity.

Homomorphisms and further algorithms

The final part explores how homomorphisms support computations involving Sylow subgroups, p-groups, and soluble groups. A closing chapter surveys additional topics, including coset enumeration, conjugacy classes, cohomology, and group recognition.

A text for learning algorithms as they are built

Examples, exercises, implementation details, and bibliographical remarks accompany the algorithmic development. Butler says that no prior group theory is assumed, though mathematical sophistication is an advantage. The book can therefore serve as a structured introduction for mathematics and computer science students, as well as a detailed reference for readers with existing group-theory knowledge who want to study computational methods.