Equations in Groups and Complexity

Newcastle Upon Tyne 18–22 July 2022

Equations in Groups and Complexity is a conference centred around an invited lecture series, given by Prof. Olga Kharlampovich, and funded by the London Mathematical Society and Heilbronn Institute.

It took place in the Curtis Auditorium in Herschel Building at Newcastle University, UK, between the 18th and 22nd of July 2022.

The timetable is available to view as a PDF by clicking here.

To view titles and abstracts, click here.

To view slides and recordings, click here.

Lecture series by Prof. Olga Kharlampovich (CUNY)


We will talk about modern theory of equations in groups, algebraic geometry and model theory in free groups, hyperbolic groups and random groups.

We first discuss a combinatorial process that combines and generalizes a number of known results and algorithms, such as the Makanin-Razborov process for solving equations in free groups, Rauzy-Veech induction in dynamical systems, classification of basic group actions in group theory and topology.

Rips recognized that the Makanin process can be adapted to study group actions on real trees which gave rise to what is now called the Rips machine, a structure theorem for finitely presented groups acting on real trees (Gaboriau, Levitt, Paulin's and Bestvina, Feighn's results) similar to Bass-Serre theory for groups acting on simplicial trees. This has been generalized to finitely generated groups by Sela and further refined by Guirardel.

Razborov's original description of the solution set has been refined independently by Kharlampovich and Myasnikov and Sela; this description has been an important tool in their solutions to the Tarski problems regarding the elementary theory of free groups. Kharlampovich and Myasnikov modified Razborov's methods to obtain their own version of the rewriting process while Sela used the Rips machine, bypassing much of the combinatorics of the process. Their description is now referred to as an M-R diagram. It was generalized to hyperbolic groups by Reinfield and Weidmann, and to toral relatively hyperbolic groups by Groves. M-R diagrams for free products have been constructed independently by Jaligot and Sela and by Casals-Ruiz and Kazachkov.

We will also discuss the recent result by Kharlampovich and Sklinos that all solutions of equations in random groups come from their solutions in a free group. Namely, suppose Γ_\ell is the random group of density d < 1/16 at length \ell and π : F_n --> Γ_\ell the natural quotient map from a free group. If V(X)=1 is a system of equations, then every solution of V(X)=1 in Γ_\ell is the image of a solution in F_n with probability approaching 1 as \ell goes to infinity.

The development of algebraic geometry comes together with advances in the theory of fully residually free and fully residually hyperbolic groups (limit groups), which are coordinate groups of irreducible algebraic varieties.

I will also survey the results about complexity of algorithms solving equations in free groups (NP completeness of the problem of satisfiability of quadratic equation over a torsion free hyperbolic group by Kharlampovich, Mohajeri, Taam, Vdovina, etc.) and discuss the ongoing program which aims to show that the problem of satisfiability of a system of equations in a free group (hyperbolic or even toral relatively hyperbolic group) is NP-complete. I will also discuss space complexity.

View slides by clicking here.

Click photo to see full size.