Fundamental Algorithms for Permutation Groups

G. Butler (eds.)3540549552, 9783540549550, 0387549552

This is the first-ever book on computational group theory. It provides extensive and up-to-date coverage of the fundamental algorithms for permutation groups with reference to aspects of combinatorial group theory, soluble groups, and p-groups where appropriate. The book begins with a constructive introduction to group theory and algorithms for computing with small groups, followed by a gradual discussion of the basic ideas of Sims for computing with very large permutation groups, and concludes with algorithms that use group homomorphisms, as in the computation of Sylowsubgroups. No background in group theory is assumed. The emphasis is on the details of the data structures and implementation which makes the algorithms effective when applied to realistic problems. The algorithms are developed hand-in-hand with the theoretical and practical justification.All algorithms are clearly described, examples are given, exercises reinforce understanding, and detailed bibliographical remarks explain the history and context of the work. Much of the later material on homomorphisms, Sylow subgroups, and soluble permutation groups is new.

---

Table of contents :
Introduction….Pages 1-6
Group theory background….Pages 7-13
List of elements….Pages 14-23
Searching small groups….Pages 24-32
Cayley graph and defining relations….Pages 33-43
Lattice of subgroups….Pages 44-55
Orbits and schreier vectors….Pages 56-63
Regularity….Pages 64-70
Primitivity….Pages 71-77
Inductive foundation….Pages 78-97
Backtrack search….Pages 98-116
Base change….Pages 117-128
Schreier-Sims method….Pages 129-142
Complexity of the Schreier-Sims method….Pages 143-155
Homomorphisms….Pages 156-170
Sylow subgroups….Pages 171-183
P-groups and soluble groups….Pages 184-204
Soluble permutation groups….Pages 205-228
Some other algorithms….Pages 229-232