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 gx = h and,
if so, then to determine one such x. Related to the conjugacy problem is
the construction of the centralizer CG(g) = { y in G | gy = 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.