Derek Holt: Algorithms for finitely presented groups III

The lecture was held within the framework of the Hausdorff Trimester Program: Logic and Algorithms in Group Theory.

Abstract:
This short course of three lectures will be on the fundamental algorithms for computing in groups that are defined by a finite presentation G=⟨X∣R⟩. For example, the simple group A5 of order 60 can be defined by the presentation A5=⟨x,y∣x2,y3,(xy)5⟩

. A knowledge of the basic theory of groups defined by presentations will be assumed.

Many of the most natural questions that one could ask about such groups G
have been proved to be theoretically undecidable. For example, we cannot in general decide whether G is nontrivial or finite, and we cannot decide whether two words in the generators of G represent the same element of G

. But the computational methods available can attempt to resolve such questions, and are successful in many naturally arising examples.

Here is a summary of the contents of the course.

Computing the largest abelian quotient of G

, with example. Brief discussion of other algorithms for computing quotients, such as p

-quotients, nilpotent quotients and solvable quotients.

Identifying subgroups of G

of finite index using Todd-Coxeter coset enumeration, with example.

Computing presentations of subgroups of finite index in G

using the Reidemeister-Schreier algorithm with example. Application to attempting to prove that G

is infinite.

The Dehn algorithm in small cancellation groups, generalizing to hyperbolic groups.

Rewrite systems and the Knuth-Bendix completion algorithm, with example.

Finite state automata, automatic groups, and an algorithm for computing automatic structures. Application to computing growth rates.

(Time permitting) Brief discussion of methods for approaching the conjugacy problem and generalized word problem in G

.