# Lecture Series October

## Model Theory

Lecture Series VIII: Automorphism groups of countable structures

Speaker: David Evans, Imperial College

Dates:

(1) Tuesday, October 30, 12 p.m.

(2) Wednesday, October 31, 11 a.m.

(3) Friday, November 2, 11 a.m.

Abstract:

Many countable first-order structures have `rich' automorphism groups, and it is interesting to study these automorphism groups both as groups and as topological groups (with the topology of pointwise convergence). Here, `rich' is undefined and depends on the context, but examples which we are interested in include: homogeneous structures such as the random graph or the rational numbers as an ordered set; omega-categorical structures, where the automorphism group is oligomorphic; the free group of countably infinite rank. Studying the structure of these automorphism groups and their actions can involve a mixture of model theory, group theory, combinatorics, descriptive set theory and topological dynamics. To illustrate this, we will discuss the construction of structures with `rich’ automorphism groups (starting from certain classes of finite structures) and go on to describe a selection of results and problems in the area. The lectures will discuss:

- The topology of the symmetric group; automorphism groups; Baire category arguments. Homogeneous structures; amalgamation classes; Fraissé's theorem and generalisations.
- Large subgroups: the small index property.
- Actions on compact spaces, amenability and structural Ramsey theory.
- Normal subgroup structure and simplicity results using notions of independence.

### Lecture Notes: All Lectures

## Expanders, approximate subgroups

Lecture Series VII: Growth and expansion in linear algebraic groups

Speaker: Harald Andres Helfgott, Universität Göttingen

Dates:

(1) Tuesday, October 16, 11 a.m.

(2) Wednesday, October 17, 11 a.m.

(3) Thursday, October 18, 11 a.m.

Abstract:

The course will be a brief introduction to the study of growth in simple (or almost-simple) linear algebraic groups $G$, in the following sense: for $A$ a generating set of $G$, either $A\cdot A\cdot A$ is much larger than $A$, or it equals all of $G$. Our focus will be on groups of Lie type, i.e., linear algebraic groups $G$ over finite fields, in part because they are in some senses the hard case: we want bounds that are independent of the size of the field.

We will discuss applications to expansion (starting with the work of Bourgain-Gamburd), but will focus on the main techniques and strategy in proofs of growth. While we will take $G=SL_2$ as the case to be discussed in detail, we will be careful to frame matters in a way that generalizes easily to other linear algebraic groups, while also emphasizing points in common with the study of growth in permutation groups.

The exposition will be mainly based on that in my survey paper in Bull. Am. Math. Soc. ("Growth in groups: ideas and perspectives", 2015) and that in my notes for the Arizona Winter School (2016), with some changes in perspective due to my ongoing work on permutation groups. Links will be made to the previous work of Larsen-Pink (see also: Hrushovski); the structure of the proof presented will be informed by generalizations by Breuillard-Green-Tao and Pyber-Szabo, and also by my old $SL_3$ paper, in so far as we will be working partly over Lie algebras.

### Lecture Notes: All Lectures

## Computational Group Theory

Lecture Series VI: Decision problems, languages, geometry and automata

Speaker: Sarah Rees, Newcastle

Dates:

(1) Tuesday, October 2, 2 p.m.

(2) Tuesday, October 9, 10 a.m.

(3) Wednesday, October 10, 10 a.m.

Abstract:

I'll deal with algorithms for finitely presented groups, in particular I will consider methods connected with rewriting, finite state automata, other models of

computation and formal languages. A general theme is the use of finite methods that capture finite aspects of geometry within the group.

I'll cover:

- the word problem:

in particular Dehn's algorithm and the geometry behind it, use of rewriting to solve the word problem, definition of the word problem in terms of Turing machines and its insolubility for finitely presented groups in general, van Kampen diagrams and the Dehn function, rewrite system, their confluence and completeness and the Knuth-Bendix process - automatic, biautomatic and hyperbolic groups:

basic definitions and examples, finite presentation and quadratic Dehn function,quadratic solution to the word problem, solubility of the conjugacy problem for biautomatic groups - automata and finite languages:

introduction to finite state automata and other models of computation, basic methods for finite state automata, computation and verification of automatic structures for groups, using Knuth Bendix and automata methods, examination of properties of automatic group using automata - hyperbolic groups:

proving a group hyperbolic, solving conjugacy problem in a hyperbolic group

### Lecture Notes: All Lectures

Lecture Series V: Computing with polycyclic groups

Speaker: Bettina Eick, Braunschweig

Dates:

(1) Tuesday, October 2, 10 a.m.

(2) Thursday, October 4, 10 a.m.

(3) Friday, October 5, 10 a.m.

Abstract:

Lecture 1: Polycyclic presentations, consistency and the word problem

This talk provides the basis for this series of lectures. It introduces

the well-known polycyclic presentations and the concept of consistency.

Then it discusses solutions to the word problem. One such solution is the

well established collection algorithm. This has proved to be practical in

many circumstances. An alternative solution is to determine explicit

functions describing the multiplication. A solution of the word problem

then reduces to evaluating these functions. We investigate the functions

arising in this setting.

Lecture 2: The conjugacy problem and its variations

Given a polycyclically presented group G and two elements g and h, the

conjugacy problem asks to check if there exists x in G with g^{x} = h and,

if so, then to determine one such x. Related to the conjugacy problem is

the construction of the centralizer C_{G}(g) = { y in G | g^{y} = g }. In

nilpotent polycyclic groups, the conjugacy problem can be solved via

applications of linear algebra. This talk also shows how to solve this

problem in arbitrary polycyclic groups.

Lecture 3: The isomorphism problem and open problems

Grunewald and Segal proved that the isomorphism problem can be decided

in nilpotent polycyclic groups. A practical algorithm for this problem

is one of the main open problems in the theory of algorithms for

polycyclic groups. The talk discusses approaches towards solving this

problem and it exhibits other related problems.

### Lecture Notes: Lecture I

### Lecture Notes: Lecture II Slides: Lecture II

### Lecture Notes: Lecture III Slides: Lecture III

Lecture Series IV: Computing with arithmetic groups

Speaker: Gabrielle Nebe, Aachen

Dates:

(1) Monday, October 1, 10 a.m.

(2) Monday, October 8, 10 a.m.

(3) Tuesday, October 9, 2 p.m.

Abstract:

Lecture 1: The historical development: Voronoi's algorithm to compute all locally densest lattices

It is a very classical problem to find the densest sphere packings in a given dimension. This is solved in dimension 1,2 (classical, Lagrange), 3 (recent work by Thomas Hales), 8 and 24 (2017 Maryna Viazowska et al). Asking for lattice sphere packings this problem is accessible to algorithmic treatment thanks to the developments by Korkine and Zolotarev (1873), and Voronoi (around 1900): The density function has finitely local maxima on the space of all similarity classes of lattices in n-dimensional Euclidean space. These are characterised as those that are perfect (a linear condition comparable to "derivative equals 0") and eutactic (a convexity condition, f''<0). Voronoi designed an algorithm to compute all perfect lattices which has been successfully applied to find all perfect lattices in dimensions $\leq 8$. This algorithm computes a locally finite face to face tesselation by polyhedral cones of the cone of all positive definite real symmetric $n \times n$ matrices on with the arithmetic group GL$_n({\bf Z})$ acts with finitely many orbits on these cones, that are in bijection to the similarity classes of perfect lattices of dimension n.

Lecture 2: A finite presentation for arithmetic groups

The Voronoi algorithm (more precisely the effectively computable action

of GL$_n({\bf Z}) $ on the face to face tessellation) can be used to compute

generators and relations for the arithmetic group GL$_n({\bf Z})$ and provides an algorithm to express any matrix $g\in $ GL$_n({\bf Z})$ as a word in these generators. The second lecture will present a formalization (going back to Max Koecher) of Voronoi's algorithm and various situations to which it applies to compute generators and relations (and the integral homology) of arithmetic groups.

Lecture 3: $S$-arithmetic groups and open problems

The last talk will introduce affine Bruhat-Tits buildings and an algorithmic

down to earth approach to the work by Borel and Serre on finiteness properties of S-arithmetic groups. We will show how to extend Voronoi's algorithm to obtain generators and relations also for S-arithmetic groups (like SL$_n({\bf Z}[1/p])$). It will also report on open problems and conjectures for S-arithmetic groups.