The book describes methods for working with elements, subgroups, and quotient groups of a finitely presented group. The author emphasizes the connection with fundamental algorithms from theoretical computer science, particularly the theory of automata and formal languages, from computational number theory, and from computational commutative algebra. The LLL lattice reduction algorithm and various algorithms for Hermite and Smith normal forms are used to study the Abelian quotients of a finitely presented group. The work of Baumslag, Cannonito, and Miller on computing non-Abelian polycyclic quotients is described as a generalization of Buchberger's Gröbner basis methods to right ideals in the integral group ring of a polycyclic group.
Author(s): Charles C. Sims
Series: Encyclopedia of Mathematics and its Applications
Publisher: CUP
Year: 1994
Language: English
Pages: 620
Contents......Page 9
Preface......Page 13
Introduction......Page 17
1.1 Set-theoretic preliminaries......Page 22
1.2 Monoids......Page 24
1.3 Groups......Page 31
1.4 Presentations......Page 34
1.5 Computability......Page 42
1.6 Procedure descriptions......Page 45
1.7 The integers......Page 49
1.8 Backtrack searches......Page 51
1.9 Historical notes......Page 56
2.1 Orderings of free monoids......Page 59
2.2 Canonical forms......Page 67
2.3 A test for confluence......Page 73
2.4 Rewriting strategies......Page 82
2.5 The Knuth-Bendix procedure......Page 84
2.6 A second version......Page 92
2.7 Some useful heuristics......Page 99
2.8 Right congruences......Page 104
3 Automata and rational languages......Page 112
3.1 Languages......Page 113
3.2 Automata......Page 116
3.3 Automata, continued......Page 124
3.4 The subset construction......Page 127
3.5 Index automata......Page 128
3.6 Trim automata......Page 136
3.7 Minimal automata......Page 142
3.8 Standard automata......Page 146
3.9 Additional constructions......Page 157
3.10 More rewriting applications......Page 163
4.1 Niladic rewriting systems......Page 167
4.2 Subgroups and their languages......Page 175
4.3 Important cosets......Page 178
4.4 Coset automata......Page 187
4.5 Basic coset enumeration......Page 191
4.6 The coincidence procedure......Page 203
4.7 Standardization in place......Page 208
4.8 Computation with subgroups......Page 212
4.9 Standard coset tables......Page 219
*4.10 Other methods......Page 226
*4.11 General nladic systems......Page 228
5.1 The general case......Page 233
5.2 The HLT strategy......Page 243
5.4 Standardizing strategies......Page 248
5.5 Ten versions......Page 255
5.6 Low-index subgroups......Page 261
5.7 Other applications......Page 267
5.8 A comparison with the Knuth-Bendix procedure......Page 276
5.9 Historical notes......Page 280
6.1 Presentations of subgroups......Page 284
6.2 Examples of extended coset enumeration......Page 292
6.3 An extended HLT enumeration procedure......Page 299
6.4 Simplifying presentations......Page 306
6.5 Historical notes......Page 310
*7 Generalized automata......Page 312
*7.1 Definitions......Page 313
*7.2 Generalized coset automata......Page 317
*7.3 Basic operations......Page 324
*7.4 Some examples......Page 330
8 Abelian groups......Page 335
8.1 Free abelian groups......Page 336
8.2 Elementary matrices......Page 346
8.3 Finitely generated abelian groups......Page 348
8.4 Modular techniques......Page 355
8.5 The Kannan-Bachem algorithm......Page 365
8.6 Lattice reduction......Page 376
8.7 The modified LLL algorithm......Page 388
8.8 A comparison......Page 394
8.9 Historical notes......Page 397
9 Polycyclic groups......Page 399
9.1 Commutator subgroups......Page 400
9.2 Solvable and nilpotent groups......Page 402
9.3 Polycyclic groups......Page 406
9.4 Polycyclic presentations......Page 410
9.5 Subgroups......Page 422
9.6 Homomorphisms......Page 430
9.7 Conjugacy in nilpotent groups......Page 433
9.8 Cyclic extensions......Page 435
9.9 Consistency, the nilpotent case......Page 446
9.10 Free nilpotent groups......Page 452
9.11 p-Groups......Page 461
10 Module bases......Page 464
10.1 Ideals in Z[X]......Page 465
10.2 Modules over Z[X]......Page 471
10.3 Modules over 96[X, Y]......Page 483
10.4 The total degree ordering......Page 487
10.5 The Grobner basis approach......Page 498
10.6 Grobner bases......Page 504
10.7 Rings of Laurent polynomials......Page 511
10.8 Group rings......Page 523
10.9 Historical notes......Page 528
11.1 Describing quotient groups......Page 530
11.2 Abelian quotients......Page 533
11.3 Extensions of modules......Page 540
11.4 Class 2 quotients......Page 551
11.5 Other nilpotent quotients......Page 561
11.6 Metabelian quotients......Page 572
11.7 Enforcing exponent laws......Page 577
11.8 Verifying polycyclicity......Page 584
11.9 Historical notes......Page 585
Appendix: Implementation issues......Page 586
Bibliography......Page 597
Index......Page 613
