# Schedule of the International Workshop on Logic and Algorithms in Group Theory

## Monday, October 22

10:15 - 10:50 |
Registration & Welcome coffee |

10:50 - 11:00 |
Opening remarks |

11:00 - 12:00 |
Alex Lubotzky: First order rigidity of high-rank arithmetic groups |

12:00 - 14:00 |
Lunch break |

14:00 - 15:00 |
Zlil Sela: Basic conjectures and preliminary results in non-commutative algebraic geometry |

15:00 - 16:00 |
Katrin Tent: Burnside groups of relatively small odd exponent |

16:00 - 16:30 |
Coffee, tea and cake |

16:30 - 17:30 |
Harald Andres Helfgott: Growth in linear algebraic groups and permutation groups: towards a unified perspective |

afterwards |
Reception |

## Tuesday, October 23

09:30 - 10:30 |
Chloe Perin: Forking independence in the free group |

10:30 - 11:00 |
Group photo and coffee break |

11:00 - 12:00 |
Krzysztof Krupinski: Amenable theories |

12:00 - 14:00 |
Lunch break |

14:00 - 15:00 |
Gregory Cherlin: The Relational Complexity of a Finite Permutation Group |

15:00 - 16:00 |
Todor Tsankov: A model-theoretic approach to rigidity in ergodic theory |

16:00 - 16:30 |
Coffee, tea and cake |

## Wednesday, October 24

09:30 - 10:30 |
Dan Segal: Small profinite groups |

10:30 - 11:00 |
Coffee break |

11:00 - 12:00 |
Martin Kassabov: On the complexity of counting homomorphism to finite groups |

12:00 - 13:00 |
Anna Erschler: Arboreal structures, Poisson boundary and growth of Groups |

19:00 - |
Dinner - Tuscolo Münsterblick, Gerhard-von-Are-Straße 8, Bonn |

## Thursday, October 25

09:30 - 10:30 |
Laura Ioana Ciobanu Radomirovic: Equations in groups, formal languages and complexity |

10:30 - 11:00 |
Coffee break |

11:00 - 12:00 |
James Wilson: Distinguishing Groups and the Group Isomorphism problem |

12:00 - 14:00 |
Lunch break |

14:00 - 15:00 |
Alan Reid: Distinguishing certain triangle groups by their finite quotients |

15:00 - 16:00 |
Alla Detinko: Computing with infinite linear groups: methods, algorithms, and applications |

16:00 - 16:30 |
Tea and cake |

## Friday, October 25

09:30 - 10:30 |
George Willis: Computing the scale |

10:30 - 11:00 |
Coffee break |

11:00 - 12:00 |
Agatha Atkarskaya; Towards a Group-like Small Cancellation Theory for Rings |

# Abstracts

## Agatha Atkarskaya: Towards a Group-like Small Cancellation Theory for Rings

Let a group $G$ be given by generators and defining relations. It is known that we cannot extract specific information about the structure of $G$ using the defining relations in the general case. However, if these defining relations satisfy small cancellation conditions, then we possess a great deal of knowledge about $G$. In particular, such groups are hyperbolic, that is we can express the multiplication in the group by means of thin triangles. It seems of interest to develop a similar theory for rings. Let $kF$ be the group algebra of the free group $F$ over some field $k$. Let $F$ have a fixed system of generators, then its elements are reduced words in these generators that we call monomials. Let $\mathcal{I}$ be ideal of $kF$ generated by a set of polynomials and let $kF / \mathcal{I}$ be the corresponding quotient algebra. In the present work we state conditions on these polynomials that will enable a combinatorial description of the quotient algebra similar to small cancellation quotients of the free group. In particular, we construct a linear basis of $kF / \mathcal{I}$ and describe a special system of linear generators of $kF / \mathcal{I}$ for which the multiplication table amounts to a linear combination of thin triangles. Constructions of groups with exotic properties make extensive use of small cancellation theory and its generalizations. In the similar way, generalizations of our approach allow to construct various examples of algebras with exotic properties. This is a joint work with A. Kanel-Belov, E. Plotkin and E. Rips.

## Gregory Cherlin: The Relational Complexity of a Finite Permutation Group

I am interested in a numerical invariant of finite permutation groups called the {\it relational complexity} which is suggested by the model theoretic point of view. (From a model theorist's perspective, the study of finite structures and the study of finite permutation groups are the same subject.) One conjecture about this invariant states that an almost simple primitive permutation group of relational complexity 2 must be the symmetric group acting naturally [1]. Considerable progress toward a proof has been made lately using a combination of theory and machine computation (e.g., [2]). A variety of computational methods have been devised which are very helpful in the limited context of the stated conjecture, and perhaps in other cases. I aim to provide a sense of what the invariant measures, and to discuss some ways that it can be determined, or estimated (structurally, group theoretically, or computationally).

References:

[1] Gregory Cherlin, Sporadic homogeneous structures, The Gelfand Mathematical Seminars, 1996-1999, pp.~15-48, Birkhäuser, 2000.

[2] Nick Gill and Pablo Spiga, Binary permutation groups: Alternating and Classical Groups, preprint. arXiv:1610.01792 [math.GR]

Related Talks:

http://sites.math.rutgers.edu/~cherlin/Talks/

* The relational complexity of a finite primitive structure, ICMS, Sep.~19, 2018

* Finite binary homogeneous structures, ICMS, July 10, 2014

## Alla Detinko: Computing with infinite linear groups: methods, algorithms, and applications

In the talk we will survey our ongoing collaborative project in a novel domain of computational group theory: computing with linear groups over infinite fields. We provide an introduction to the area, and discuss available methods and algorithms. Special consideration will be given to the most recent developments in computing with Zariski dense groups and applications. This talk is aimed at a general algebraic audience (see also our expository article https://doi.org/10.1016/j.exmath.2018.07.002}).

## Anna Erschler: Arboreal structures, Poisson boundary and growth of groups

A group is said to be ICC if all non-identity elements have infinitely many conjugates. In a joint work with Vadim Kaimanovich, given an ICC group, we construct a forest F with the vertex set G and a probability measure on G such that trajectories of the random walk tend almost surely to points of the boundary of F; we show that the Poisson boundary can be identified with the boundary of the forest, endowed with the hitting distribution; we show that the convergence to Poisson boundary has strong convergence property, resembling the case of simple random walks on free groups and we show that the action of G on the Poisson boundary is free.

Our result is a development of a recent result of Joshua Frisch, Yair Hartman, Omer Tamuz and Pooya Vahidi Ferdowsi, who has shown that any ICC group admits a measure with non-trivial Poisson boundary. In a joint work with Tianyi Zheng, we construct measures with power law decay on torsion Grigorchuk groups that have non-trivial Poisson boundary. As an application we obtain near optimal lower bound for the growth of these groups.

## Harald Andres Helfgott: Growth in linear algebraic groups and permutation groups: towards a unified perspective

Given a finite group $G$ and a set $A$ of generators, the diameter $ diam(\Gamma(G,A))$ of the Cayley graph $\Gamma(G,A)$ is the smallest $\ell$ such that every element of $G$ can be expressed as a word of length at most $\ell$ in $A \cup A^{-1}$. We are concerned with bounding $diam(G):= \max_A diam(\Gamma(G,A))$. It has long been conjectured that the diameter of the symmetric group of degree $n$ is polynomially bounded in $n$. In 2011, Helfgott and Seress gave a quasipolynomial bound $\exp((\log n)^{4+\epsilon})$. We will discuss a recent, much simplified version of the proof, emphasising the links in commons with previous work on growth in linear algebraic groups.

Reference:

## Martin Kassabov: On the complexity of counting homomorphism to finite groups (joint with Eric Samperton)

I will discuss the complexity of determining the number of homomorphisms from finitely presented groups to finite groups, which turns out to be a #P complete problem. Somewhat surprisingly, this is even the case when the target is a finite nilpotent group.

## Krzysztof Krupinski: Amenable theories

I will introduce the notion of an amenable theory as a natural counterpart of the notion of a definably amenable group. Roughly speaking, amenability means that there are invariant (under the action of the group of automporphism of a sufficiently saturated model), Borel, probability measures on various types spaces. I will discuss several equivalent definitions and give some examples. Then I will discuss the result that each amenable theory is Gcompact. This is a part of my recent paper (still in preparation) with Udi Hrushovski and Anand Pillay.

## Alex Lubotzky: First order rigidity of high-rank arithmetic groups

The family of high rank arithmetic groups is a class of groups playing an important role in various areas of mathematics. It includes SL(n,Z), for n>2 , SL(n, Z[1/p] ) for n>1, their finite index subgroups and many more.

A number of remarkable results about them have been proven including; Mostow rigidity, Margulis Super rigidity and the Quasi-isometric rigidity. We will talk about a further type of rigidity: "first order rigidity" (also called quasi-axiomatisable in some articles). Namely, if G is such a non-uniform characteristic zero arithmetic group and H a finitely generated group which is elementary equivalent to it, then H is isomorphic to G. This stands in contrast with Zlil Sela's remarkable work which implies that the free groups, surface groups and hyperbolic groups (many of which are low-rank arithmetic groups) have many non isomorphic finitely generated groups which are elementary equivalent to them. Joint work with Nir Avni and Chen Meiri.

## Chloe Perin: Forking independence in the free group

Model theorists define, in structures whose first-order theory is "stable" (i.e. suitably nice), a notion of independence between elements. This notion coincides for example with linear independence when the structure considered is a vector space, and with algebraic independence when it is an algebraically closed field. Sela showed that the theory of the free group is stable. In a joint work with Rizos Sklinos, we give an interpretation of this model theoretic notion of independence in the free group using Grushko and JSJ decompositions.

## Laura Ioana Ciobanu Radomirovic: Equations in groups, formal languages and complexity

For a group G, solving equations where the coefficients are elements in G and the solutions take values in G can be seen as akin to solving Diophantine equations in number theory, answering questions from linear algebra or moregenerally, algebraic geometry. Moreover, the question of satisfiability of equations fits naturally into the framework of the first order theory of G.I will start the talk with a survey containing results from both mathematics and computer science about solving equations in infinite nonabelian groups, with emphasis on free and hyperbolic groups. I will then show how for these groups the solutions to equations can be beautifully described in terms of formal languages, and that the latest techniques involving string compression produce optimal space complexity algorithms. If time allows, I will show how some of the results can carry over to certain group extensions. This is joint work, in several projects, with Volker Diekert, Murray Elder, Derek Holt and Sarah Rees.

## Alan Reid: Distinguishing certain triangle groups by their finite quotients

We prove that certain arithmetic Fuchsian triangle groups are profinitely rigid in the sense that they are determined by their set of finite quotients amongst all finitely generated residually finite groups. Amongst the examples are the (2,3,8) triangle group.

## Dan Segal: Small profinite groups

I will explore the connections between various conditions of smallness on a profinite group, such as being (topologically) finitely generated, having only finitely many open subgroups of each finite index, or having all finite-index subgroups open, and the extent to which these can be characterized by algebraic properties of the associated system of finite groups.

Reference:

Remarks on profinite groups having few open subgroups, J. Combinatorial Algebra 2 (2018), 87-101.

## Zlil Sela: Basic conjectures and preliminary results in non-commutative algebraic geometry

Algebraic geometry studies the structure of varieties over fields and commutative rings. Starting in the 1960's ring theorists (Cohn, Bergman and others) have tried to study the >structure of varieties over some non-commutative rings (notably free associative algebras). The lack of unique factorization that they tackled and studied in detail, and the pathologies that they were aware of, prevented any attempt to prove or even speculate what can be the properties of such varieties. Using techniques and concepts from geometric group theory and from low dimensional topology, we formulate concrete conjectures about the structure of these varieties, and prove preliminary results in the direction of these conjectures.

## Katrin Tent: Burnside groups of relatively small odd exponent

(joint work with A. Atkarskaya and E. Rips)

The free Burnside group B(n,m) of exponent m is the quotient of the free group on n generators by the normal subgroup generated by its mth powers. Novikov and Adyan showed that for odd m sufficiently large and n at least 2, the group B(n,m) is infinite. In subsequent work, Adyan improved the lower bound on m, the latest bound being 101.

Our approach to Burnside groups combines geometric and combinatorial aspects. We first define a collection of canonical relators for the normal subgroup with nice combinatorial properties. These properties allow us to use generalized small cancellation methods leading to a version of Greendlinger's Lemma sufficient to deduce the infinity of these groups.

## Todor Tsankov: A model-theoretic approach to rigidity in ergodic theory

(joint work with Tomás Ibarlucía)

I will discuss a new approach to some rigidity results in the ergodic theory of non-amenable groups via model theory. I will explain how ergodic theory can be formalized in continuous logic and how the model-theoretic notion of algebraic closure plays an important role in understanding strongly ergodic systems.

No prior knowledge of modeltheory or ergodic theory will be assumed.

## George Willis: Computing the scale

The scale function on a totally disconnected, locally compact (t.d.l.c.) group is continuous and takes positive integer values. In special cases, such as when the group has a linear [1] or geometric [2] representation, it may be computed. However not all t.d.l.c. groups have representations which allow computation of the scale and other features of the group and the extent to which it is possible to obtain such representations is not known.

[1] H. Glöckner, Scale functions on linear groups over local skew fields, J. Algebra 205, 525-541 (1998).

[2] G. A. Willis, The structure of totally disconnected, locally compact groups, Math. Ann. 300, 341-363 (1994).