Notation and displayed procedures |
|
xvi | |
|
A Historical Review of Computational Group Theory |
|
|
1 | (8) |
|
|
9 | (52) |
|
|
9 | (8) |
|
|
9 | (2) |
|
|
11 | (1) |
|
Cyclic and dihedral groups |
|
|
12 | (1) |
|
|
13 | (1) |
|
Examples --- permutation groups and matrix groups |
|
|
13 | (1) |
|
Normal subgroups and quotient groups |
|
|
14 | (1) |
|
Homomorphisms and the isomorphism theorems |
|
|
15 | (2) |
|
|
17 | (9) |
|
|
17 | (2) |
|
|
19 | (1) |
|
Conjugacy, normalizers, and centralizers |
|
|
20 | (1) |
|
|
21 | (1) |
|
Transitivity and primitivity |
|
|
22 | (4) |
|
|
26 | (7) |
|
Simple and characteristically simple groups |
|
|
26 | (1) |
|
|
27 | (1) |
|
The derived series and solvable groups |
|
|
27 | (2) |
|
Central series and nilpotent groups |
|
|
29 | (2) |
|
The socle of a finite group |
|
|
31 | (1) |
|
The Frattini subgroup of a group |
|
|
32 | (1) |
|
|
33 | (8) |
|
|
33 | (3) |
|
|
36 | (2) |
|
Presentations of group extensions |
|
|
38 | (2) |
|
|
40 | (1) |
|
Presentations of subgroups |
|
|
41 | (5) |
|
Subgroup presentations on Schreier generators |
|
|
41 | (3) |
|
Subgroup presentations on a general generating set |
|
|
44 | (2) |
|
Abelian group presentations |
|
|
46 | (2) |
|
Representation theory, modules, extensions, derivations, and complements |
|
|
48 | (8) |
|
The terminology of representation theory |
|
|
49 | (1) |
|
Semidirect products, complements, derivations, and first cohomology groups |
|
|
50 | (2) |
|
Extensions of modules and the second cohomology group |
|
|
52 | (2) |
|
The actions of automorphisms on cohomology groups |
|
|
54 | (2) |
|
|
56 | (5) |
|
Field extensions and splitting fields |
|
|
56 | (2) |
|
|
58 | (1) |
|
|
59 | (2) |
|
Representing Groups on a Computer |
|
|
61 | (16) |
|
Representing groups on computers |
|
|
61 | (6) |
|
The fundamental representation types |
|
|
61 | (1) |
|
|
62 | (2) |
|
|
64 | (1) |
|
|
65 | (2) |
|
The use of random methods in CGT |
|
|
67 | (5) |
|
|
67 | (2) |
|
Finding random elements of groups |
|
|
69 | (3) |
|
Some structural calculations |
|
|
72 | (2) |
|
Powers and orders of elements |
|
|
72 | (1) |
|
|
73 | (1) |
|
The commutator subgroup, derived series, and lower central series |
|
|
73 | (1) |
|
Computing with homomorphisms |
|
|
74 | (3) |
|
Defining and verifying group homomorphisms |
|
|
74 | (1) |
|
|
75 | (2) |
|
Computation in Finite Permutation Groups |
|
|
77 | (72) |
|
The calculation of orbits and stabilizers |
|
|
77 | (4) |
|
|
79 | (2) |
|
Testing for Alt(Ω) and Sym(Ω) |
|
|
81 | (1) |
|
|
82 | (5) |
|
|
82 | (1) |
|
|
83 | (2) |
|
Implementation of the class merging process |
|
|
85 | (2) |
|
Bases and strong generating sets |
|
|
87 | (18) |
|
|
87 | (3) |
|
The Schreier-Sims algorithm |
|
|
90 | (3) |
|
Complexity and implementation issues |
|
|
93 | (2) |
|
Modifying the strong generating set --- shallow Schreier trees |
|
|
95 | (2) |
|
The random Schreier-Sims method |
|
|
97 | (1) |
|
The solvable BSGS algorithm |
|
|
98 | (4) |
|
|
102 | (3) |
|
Homomorphisms from permutation groups |
|
|
105 | (3) |
|
The induced action on a union of orbits |
|
|
105 | (1) |
|
The induced action on a block system |
|
|
106 | (1) |
|
Homomorphisms between permutation groups |
|
|
107 | (1) |
|
|
108 | (24) |
|
Searching through the elements of a group |
|
|
110 | (3) |
|
|
113 | (1) |
|
Searching for subgroups and coset representatives |
|
|
114 | (4) |
|
Automorphism groups of combinatorial structures and partitions |
|
|
118 | (3) |
|
Normalizers and centralizers |
|
|
121 | (3) |
|
Intersections of subgroups |
|
|
124 | (2) |
|
Transversals and actions on cosets |
|
|
126 | (5) |
|
Finding double coset representatives |
|
|
131 | (1) |
|
Sylow subgroups, p-cores, and the solvable radical |
|
|
132 | (11) |
|
Reductions involving intransitivity and imprimitivity |
|
|
133 | (1) |
|
Computing Sylow subgroups |
|
|
134 | (3) |
|
A result on quotient groups of permutation groups |
|
|
137 | (1) |
|
|
138 | (2) |
|
Computing the solvable radical |
|
|
140 | (1) |
|
Nonabelian regular normal subgroups |
|
|
141 | (2) |
|
|
143 | (6) |
|
|
144 | (1) |
|
Graphs, block designs, and error-correcting codes |
|
|
145 | (2) |
|
Diameters of Cayley graphs |
|
|
147 | (1) |
|
Processor interconnection networks |
|
|
148 | (1) |
|
|
149 | (50) |
|
|
150 | (12) |
|
Coset tables and their properties |
|
|
151 | (1) |
|
|
152 | (4) |
|
|
156 | (6) |
|
Strategies for coset enumeration |
|
|
162 | (11) |
|
|
162 | (3) |
|
The coset table-based method |
|
|
165 | (2) |
|
Compression and standardization |
|
|
167 | (1) |
|
Recent developments and examples |
|
|
168 | (2) |
|
|
170 | (1) |
|
The use of coset enumeration in practice |
|
|
171 | (2) |
|
Presentations of subgroups |
|
|
173 | (15) |
|
Computing a presentation on Schreier generators |
|
|
173 | (5) |
|
Computing a presentation on the user generators |
|
|
178 | (6) |
|
Simplifying presentations |
|
|
184 | (4) |
|
Finding all subgroups up to a given index |
|
|
188 | (10) |
|
Coset tables for a group presentation |
|
|
189 | (1) |
|
|
190 | (6) |
|
Variations and improvements |
|
|
196 | (2) |
|
|
198 | (1) |
|
Presentations of Given Groups |
|
|
199 | (20) |
|
Finding a presentation of a given group |
|
|
199 | (6) |
|
Finding a presentation on a set of strong generators |
|
|
205 | (3) |
|
|
205 | (2) |
|
The Todd-Coxeter-Schreier-Sims algorithm |
|
|
207 | (1) |
|
The Sims `Verify' algorithm |
|
|
208 | (11) |
|
The single-generator case |
|
|
209 | (4) |
|
|
213 | (4) |
|
|
217 | (2) |
|
Representation Theory, Cohomology, and Characters |
|
|
219 | (54) |
|
Computation in finite fields |
|
|
220 | (1) |
|
Elementary computational linear algebra |
|
|
221 | (5) |
|
Factorizing polynomials over finite fields |
|
|
226 | (4) |
|
Reduction to the squarefree case |
|
|
228 | (1) |
|
Reduction to constant-degree irreducibles |
|
|
229 | (1) |
|
|
229 | (1) |
|
Testing KG-modules for irreducibility --- the Meataxe |
|
|
230 | (7) |
|
|
230 | (4) |
|
|
234 | (1) |
|
The Ivanyos-Lux extension |
|
|
235 | (1) |
|
Actions on submodules and quotient modules |
|
|
235 | (1) |
|
|
236 | (1) |
|
|
237 | (11) |
|
Testing modules for absolute irreducibility |
|
|
237 | (4) |
|
Finding module homomorphisms |
|
|
241 | (3) |
|
Testing irreducible modules for isomorphism |
|
|
244 | (1) |
|
Application --- invariant bilinear forms |
|
|
245 | (1) |
|
Finding all irreducible representations over a finite field |
|
|
246 | (2) |
|
|
248 | (7) |
|
Computing first cohomology groups |
|
|
249 | (4) |
|
Deciding whether an extension splits |
|
|
253 | (1) |
|
Computing second cohomology groups |
|
|
254 | (1) |
|
Computing character tables |
|
|
255 | (9) |
|
|
256 | (1) |
|
|
257 | (3) |
|
|
260 | (4) |
|
Structural investigation of matrix groups |
|
|
264 | (9) |
|
Methods based on bases and strong generating sets |
|
|
264 | (4) |
|
Computing in large-degree matrix groups |
|
|
268 | (5) |
|
Computation with Polycyclic Groups |
|
|
273 | (52) |
|
|
274 | (12) |
|
|
274 | (4) |
|
Polycyclic presentations and consistency |
|
|
278 | (2) |
|
|
280 | (4) |
|
Changing the presentation |
|
|
284 | (2) |
|
Examples of polycyclic groups |
|
|
286 | (4) |
|
Abelian, nilpotent, and supersolvable groups |
|
|
286 | (2) |
|
Infinite polycyclic groups and number fields |
|
|
288 | (1) |
|
Application --- crystallographic groups |
|
|
289 | (1) |
|
Subgroups and membership testing |
|
|
290 | (8) |
|
Induced polycyclic sequences |
|
|
291 | (5) |
|
Canonical polycyclic sequences |
|
|
296 | (2) |
|
Factor groups and homomorphisms |
|
|
298 | (2) |
|
|
298 | (1) |
|
|
299 | (1) |
|
|
300 | (2) |
|
|
302 | (2) |
|
Complements and extensions |
|
|
304 | (7) |
|
Complements and the first cohomology group |
|
|
304 | (3) |
|
Extensions and the second cohomology group |
|
|
307 | (4) |
|
Intersections, centralizers, and normalizers |
|
|
311 | (6) |
|
|
311 | (2) |
|
|
313 | (1) |
|
|
314 | (2) |
|
Conjugacy problems and conjugacy classes |
|
|
316 | (1) |
|
|
317 | (3) |
|
The structure of finite solvable groups |
|
|
320 | (5) |
|
|
320 | (2) |
|
|
322 | (3) |
|
Computing Quotients of Finitely Presented Groups |
|
|
325 | (50) |
|
Finite quotients and automorphism groups of finite groups |
|
|
326 | (9) |
|
Description of the algorithm |
|
|
326 | (6) |
|
|
332 | (1) |
|
Automorphism groups of finite groups |
|
|
333 | (2) |
|
|
335 | (12) |
|
The linear algebra of a free abelian group |
|
|
335 | (1) |
|
Elementary row operations |
|
|
336 | (1) |
|
|
337 | (4) |
|
Elementary column matrices and the Smith normal form |
|
|
341 | (6) |
|
Practical computation of the HNF and SNF |
|
|
347 | (6) |
|
|
347 | (2) |
|
The use of norms and row reduction techniques |
|
|
349 | (3) |
|
|
352 | (1) |
|
p-quotients of finitely presented groups |
|
|
353 | (22) |
|
Power-conjugate presentations |
|
|
353 | (2) |
|
|
355 | (9) |
|
Other quotient algorithms |
|
|
364 | (1) |
|
Generating descriptions of p-groups |
|
|
364 | (7) |
|
Testing finite p-groups for isomorphism |
|
|
371 | (1) |
|
Automorphism groups of finite p-groups |
|
|
371 | (1) |
|
|
372 | (3) |
|
Advanced Computations in Finite Groups |
|
|
375 | (18) |
|
|
376 | (5) |
|
Definition of the subgroups |
|
|
376 | (1) |
|
Computing the subgroups --- initial reductions |
|
|
377 | (1) |
|
|
378 | (1) |
|
Finding the socle factors -- the primitive case |
|
|
379 | (2) |
|
Computing composition and chief series |
|
|
381 | (2) |
|
Refining abelian sections |
|
|
381 | (1) |
|
Identifying the composition factors |
|
|
382 | (1) |
|
Applications of the solvable radical method |
|
|
383 | (2) |
|
Computing the subgroups of a finite group |
|
|
385 | (5) |
|
Identifying the TF-factor |
|
|
386 | (1) |
|
Lifting subgroups to the next layer |
|
|
387 | (3) |
|
Application -- enumerating finite unlabelled structures |
|
|
390 | (3) |
|
|
393 | (18) |
|
Primitive permutation groups |
|
|
394 | (3) |
|
Affine primitive permutation groups |
|
|
395 | (1) |
|
Nonaffine primitive permutation groups |
|
|
396 | (1) |
|
Transitive permutation groups |
|
|
397 | (3) |
|
|
397 | (2) |
|
|
399 | (1) |
|
|
400 | (2) |
|
|
402 | (5) |
|
The Frattini extension method |
|
|
404 | (1) |
|
A random isomorphism test |
|
|
405 | (2) |
|
|
407 | (2) |
|
The ``Atlas of Finite Groups'' |
|
|
409 | (2) |
|
Rewriting Systems and the Knuth-Bendix Completion Process |
|
|
411 | (22) |
|
|
412 | (5) |
|
|
412 | (3) |
|
Free monoids and monoid presentations |
|
|
415 | (2) |
|
|
417 | (6) |
|
Rewriting systems in monoids and groups |
|
|
423 | (3) |
|
Rewriting systems for polycyclic groups |
|
|
426 | (3) |
|
|
429 | (2) |
|
|
431 | (2) |
|
Finite State Automata and Automatic Groups |
|
|
433 | (38) |
|
|
434 | (17) |
|
|
434 | (3) |
|
Enumerating and counting the language of a dfa |
|
|
437 | (2) |
|
The use of fsa in rewriting systems |
|
|
439 | (2) |
|
|
441 | (1) |
|
|
442 | (1) |
|
Operations on finite state automata |
|
|
442 | (1) |
|
Making an fsa deterministic |
|
|
443 | (1) |
|
|
444 | (2) |
|
Testing for language equality |
|
|
446 | (1) |
|
Negation, union, and intersection |
|
|
447 | (1) |
|
|
447 | (1) |
|
Existential quantification |
|
|
448 | (3) |
|
|
451 | (5) |
|
Definitions, examples, and background |
|
|
451 | (2) |
|
Word-differences and word-difference automata |
|
|
453 | (3) |
|
The algorithm to compute the shortlex automatic structures |
|
|
456 | (12) |
|
|
457 | (2) |
|
Step 2 and word reduction |
|
|
459 | (1) |
|
|
460 | (2) |
|
|
462 | (2) |
|
|
464 | (2) |
|
Comments on the implementation and examples |
|
|
466 | (2) |
|
|
468 | (1) |
|
|
469 | (2) |
References |
|
471 | (26) |
Index of Displayed Procedures |
|
497 | (2) |
Author Index |
|
499 | (4) |
Subject Index |
|
503 | |