• Logic and Algorithms in Group Theory
• Summer School

• Schedule
• Poster
• Participants
• Recorded talks

Lecture 1: Amalgamated products and HNN extensions.
This lecture will introduce the key constructions in group theory needed to embed abstract computational machines into groups. We will go over the definitions and give normal forms for elements in these groups.

Lecture 2: Computability and a construction of Aanderaa and Cohen.
This lecture will introduce Modular Machines as a method of abstract computation. After discussing what it means for a problem to be undecidable, we will go over (without proof) the explicit construction of Aanderaa and Cohen which gives both a finitely presented group with undecidable word problem, and extends to prove Higman's embedding theorem.

Lecture 3: Undecidability for other group-theoretic problems.
We will prove the Adian-Rabin theorem, which allows us to export undecidability of the word problem to other decidability problems in group theory. We use this to show that, for practically every group-theoretic property, recognising if a finitely presented group has that property is undecidable.

Notes

The lectures begin by introducing finite groups of Lie type, in particular their structural properties relevant for their representation theory. Then some of the most fundamental goals and the state of the art will be discussed. Harish-Chandra theory, one of the major tools, will be presented. The focus will be on Deligne-Lusztig theory, which yields a classification of the irreducible complex representations of the groups of Lie type.

Lecture I

Lecture II

Lecture III

Recorded Talks

Part I

Part II

Part III

This short course of three lectures will be on the fundamental algorithms for computing in groups that are defined by a finite presentation $G = \langle X \mid R \rangle$. For example, the simple group $A_5$ of order $60$ can be defined by the presentation $A_5 = \langle x,y \mid x^2,y^3,(xy)^5 \rangle$. A knowledge of the basic theory of groups defined by presentations will be assumed.

The first few sections of the author's lecture notes https://warwick.ac.uk/fac/sci/maths/people/staff/fbouyer/ provide an introduction to this theory, and these notes also include material on the Todd-Coxeter and Reidemeister-Schreier algorithms, which will feature in this course.

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$.

A course of four lectures with a similar remit was given by Max Neunhöffer at Groups St Andrews in 2013, and the lecture notes areavailable at http://www-groups.mcs.st-andrews.ac.uk/cgt2013/lectures.shtml

Slides

Recorded Talks

Part I

Part II

Part III

An infinite group is pseudofinite if it has the 'finite model property' – that is, if every sentence of first order logic which is true of it is also true of some finite group; equivalently, an infinite group is pseudofinite if it satisfies the same first order sentences as some infinite ultraproduct of finite groups. The study of pseudofinite groups is thus a kind of study of uniform first order properties of finite groups. There is a more general notion of pseudofinite structure, and for example pseudofinite fields are well-studied.

I will give some basic background in concepts from model theory (eg ultraproducts, and concepts from `generalised stability theory’). The lectures will then survey work of several authors on the model theory of finite and pseudofinite groups. Key themes will be

(1) Theorems of J.S. Wilson on simple pseudofinite groups, and uniform definability of solubility and the soluble radical in finite groups;

(2) structure theory of pseudofinite groups under model-theoretic assumptions from generalised stability theory, and connections to finite group theory.

I may also discuss connections to profinite groups, and recent work of Nikolov, Schneider and Thom answering questions of Pillay and Zilber.

Article

Recorded Talks

Part I

Part II

Part III

Is a pair of almost commuting permutations close to a pair of commuting permutations? Arzhantseva and Paunescu answered a more precise form of this question positively. In this course, I will discuss methods to decide when almost solutions to equations in permutation groups are close to actual solutions of those equations. The course will contain a basic introduction to the theory of unimodular random networks as well as invariant random subgroups and explain their use in decision problems in graph theory and group theory.

Article

Recorded Talk 

Part I

Part II

Part III