Permutation Group Algorithms

Cover Page......Page 1
Title......Page 5
ISBN 052166103X......Page 6
Contents (with page links)......Page 7
1 Introduction......Page 11
1.1. List of Algorithms......Page 14
1.2. Notation and Terminology......Page 16
1.2.1. Groups......Page 17
1.2.2. Permutation Groups......Page 19
1.2.3. Algorithmic Concepts......Page 20
1.2.4. Graphs......Page 21
1.3.Classification of Randomized Algorithms......Page 22
2 Black-Box Groups......Page 26
2.1.1. Orbit Computations......Page 28
Algorithms Based on Normal Closure......Page 33
2.2. Random Elements of Black-Box Groups......Page 34
The Product Replacement Algorithm......Page 37
2.3.1. Definition and Basic Properties......Page 40
2.3.2. Reducing the Number of Generators......Page 43
2.3.3. Closure Algorithms without Membership Testing......Page 47
2.3.4. Derived and Lower Central Series......Page 48
2.4.1. Definition and Basic Properties......Page 50
2.4.2. Applications......Page 54
Exercises......Page 57
3.1. Polynomial-Time Algorithms......Page 58
3.2. Nearly Linear-Time Algorithms......Page 61
3.3. Non-Polynomial-Time Methods......Page 62
4.1. Basic Definitions......Page 65
The Sifting Procedure......Page 66
4.2. The Schreier–Sims Algorithm......Page 67
The Schreier–Sims Algorithm......Page 69
4.3. The Power of Randomization......Page 72
4.4. Shallow Schreier Trees......Page 74
The SGS Construction......Page 80
The Algorithm Solving (4.6)......Page 82
4.5.1. Implementation......Page 85
Exercises......Page 87
5.1.1. Pointwise Stabilizers......Page 89
5.1.2. Homomorphisms......Page 90
5.1.3. Transitive Constituent and Block Homomorphisms......Page 91
The Block Homomorphism Algorithm......Page 92
5.1.4. Closures and Normal Closures......Page 93
5.2. Working with Base Images......Page 94
Representation as a Black-Box Group......Page 103
The Exchange of Two Base Points (Deterministic Version)......Page 107
Base Change by Conjugation......Page 108
5.5. Blocks of Imprimitivity......Page 110
5.5.1. Blocks in Nearly Linear Time......Page 111
Computation of the Smallest Block Containing…......Page 117
Exercises......Page 121
6 A Library of Nearly Linear-Time Algorithms......Page 124
6.1.1. Intersection with a Normal Closure......Page 125
6.1.2. Centralizer in the Symmetric Group......Page 127
6.1.4. Centralizer of a Normal Subgroup......Page 130
6.1.5. Core of a Subnormal Subgroup......Page 134
6.2. Composition Series......Page 135
6.2.1. Reduction to the Primitive Case......Page 136
6.2.2. The O’Nan–Scott Theorem......Page 139
Computing the Socle of a Frobenius Group......Page 143
Luks’s Algorithm......Page 144
Neumann’s Algorithm (the EARNS Subroutine)......Page 147
6.2.4. Groups with a Unique Nonabelian Minimal Normal Subgroup......Page 149
The Algorithm for Case B of Theorem 6.2.7......Page 150
The Algorithm for Case C(i)......Page 152
The Algorithm for Case C(ii)......Page 153
The Algorithm for Case C(iii)......Page 155
6.2.5. Implementation......Page 156
6.2.6. An Elementary Version......Page 159
Beals’s Algorithm for Groups with No Regular Normal Subgroups......Page 160
6.2.7. Chief Series......Page 165
6.3. Quotients with Small Permutation Degree......Page 166
6.3.1. Solvable Radical and p-Core......Page 167
The Algorithms......Page 168
Exercises......Page 169
7.1. Strong Generators in Solvable Groups......Page 172
The Generalized Normal Closure Algorithm......Page 174
7.2. Power-Conjugate Presentations......Page 175
7.3. Working with Elementary Abelian Layers......Page 176
7.3.1. Sylow Subgroups......Page 177
7.3.2. Conjugacy Classes in Solvable Groups......Page 182
Computation of the Class Representatives......Page 183
Computation of the Centralizers......Page 184
7.4. Two Algorithms for Nilpotent Groups......Page 185
7.4.1. A Fast Nilpotency Test......Page 186
7.4.2. The Upper Central Series in Nilpotent Groups......Page 189
Exercises......Page 191
8 Strong Generating Tests......Page 193
8.1.1. Coset Enumeration......Page 194
The STCS Algorithm......Page 196
8.2. Sims’s Verify Routine......Page 198
The Verify Routine......Page 200
8.3. Toward Strong Generators by a Las Vegas Algorithm......Page 201
8.4. Short Presentation......Page 207
9 Backtrack Methods......Page 211
9.1. Traditional Backtrack......Page 212
9.1.1. Pruning the Search Tree: Problem-Independent Methods......Page 213
9.1.2. Pruning the Search Tree: Problem-Dependent Methods......Page 215
9.2. The Partition Method......Page 217
9.3. Normalizers......Page 221
Class Representatives by Random Sampling......Page 224
Separation of the Solvable Radical......Page 226
Exercises......Page 227
10.1. Labeled Branchings......Page 228
10.1.1. Construction......Page 232
10.2. Alternating and Symmetric Groups......Page 235
10.2.1. Number Theoretic and Probabilistic Estimates......Page 238
10.2.2. Constructive Recognition: Finding the New Generators......Page 245
10.2.3. Constructive Recognition: The Homomorphism Lambda......Page 249
10.2.4. Constructive Recognition: The Case of Giants......Page 254
10.3. A Randomized Strong Generator Construction......Page 256
Bibliography......Page 264
Index (with page links)......Page 272