Seminars in Computational Group Theory

Test

Test

Markus Lohrey: Streaming word problems

8th December, 2023

We are interested in highly efficient algorithms for word problems of groups: the algorithm should read the input word once from left to right symbol by symbol (such algorithms are known as streaming algorithms), spending ideally only constant time for each input letter. Moreover, the space used by the algorithm should be small, e.g. O(log n) if n is the length of the input word. To achieve these goals we need randomization: the algorithm is allowed to make random guesses and at the end it gives a correct answer (is the input word trivial in the underlying group?) with high probability. We show that for a large class of groups such algorithms exist, where in particular the space complexity is bounded by O(log n). These groups are obtained by starting with finitely generated linear groups and closing up under the following operations: finite extensions, graph products, and wreath products where the left factor is f.g. abelian. We also contrast this result with lower bounds. For instance, for Thompsonโ€™s group F every randomized streaming algorithm for the word problem for F has space complexity Ω(n) (n is again the length of the input word).

Enric Ventura: The central tree property and some average case complexity results for algorithmic problems in free groups

8th December, 2023

We study the average case complexity of the Uniform Membership Problem for subgroups of free groups, and we show that it is orders of magnitude lower than the worst case complexity of the best known algorithms. This applies both to subgroups given by a fixed number of generators, and to subgroups given by an exponential number of generators. The main idea behind this result is to exploit a generic property of tuples of words, called the central tree property. Another application is given to the average case complexity of the relative primitivity problem, using Shpilrain's recent algorithm to decide primitivity in a free group, whose average case complexity is a constant depending only on the rank of the ambient free group.

Alexander Hulpke: Constructing Perfect Groups

2nd November, 2022

The construction of perfect groups of a given order can be considered as the prototype of the construction of insoluble groups of a given order. I will describe a recent project to enumerate, up to isomorphism, the perfect groups of order up to 2โ‹…106. It crucially relies on new tools for calculating cohomology, as well as improved implementations for isomorphism test. This work extends results of Holt and Plesken from 1989 and illustrates the scope of algorithmic improvements over the past decades.

Volker Diekert: Decidability of membership problems for 2ร—2 matrices over โ„š

7th October, 2022

We consider membership problems in matrix semigroups. Using symbolic algorithms on words and finite automata, we prove various new decidability results for 2ร—2 matrices over โ„š. For that, we introduce the concept of flat rational sets: if M is a monoid and N is a submonoid, then flat rational sets of M over N are finite unions of the form L0g1L1โ‹ฏgtLt where all Li are rational subsets of N and gi โˆˆ M. We give quite general sufficient conditions under which flat rational sets form an effective relative Boolean algebra. As a corollary, we obtain that the emptiness problem for Boolean combinations of flat rational subsets of GL2(โ„š) over GL2(โ„ค) is decidable (in singly exponential time). It is possible that such a strong decidability result cannot be pushed any further for groups sitting between GL2(โ„ค) and GL2(โ„š).

We also show a dichotomy for non-trivial group extension of GL2(โ„ค) in GL2(โ„š): if G is a f.g. group such that GL2(โ„ค) < G โ‰ค GL2(โ„š), then either G โ‰… GL2(โ„ค) ร— โ„คk, for some k โ‰ฅ 1, or G contains an extension of the Baumslag-Solitar group BS(1,q), with q โ‰ฅ 2, of infinite index. In the first case of the dichotomy the membership problem for G is decidable but the equality problem for rational subsets of G is undecidable. In the second case, decidability of the membership problem for rational subsets in G is open.

Our result improves various natural decidability results for 2ร—2 matrices with rational entries, and it also supports them with concrete complexity bounds for the first time.

Sarah Rees: The compressed word problem in relatively hyperbolic groups

3rd December, 2021

I'll discuss recent work with Derek Holt that proves that the compressed word problem in groups that are hyperbolic relative to free abelian subgroups can be solved in polynomial time. This result extends results of Lohrey, and of Holt, Lohrey and Schleimer, for free groups and for word hyperbolic groups, and our proof imitates the proofs of those results. I'll define all the terms used in the title, explain background that motivates the result, and outline the methods used in the proof.

Alexander Ushakov: Quadratic equations in Baumslag-Solitar groups

19th November, 2021

We prove that the Diophantine problem for quadratic equations in unimodular and metabelian Baumslag-Solitar groups BS(m,n) is decidable and belongs to NP. Furthermore, the problem is polynomial-time decidable if |m|=|n|=1 and is NP-hard otherwise.

Alexei Myasnikov: On the Andrews-Curtis conjecture

8th October, 2021

I am going to talk about the group-theoretic aspects of the Andrews-Curtis conjecture, some recent results, and some old. From my viewpoint the Andrews-Curtis conjecture is not just a hard stand-alone question, coming from topology, but a host of very interesting problems in group theory.

Laura Ciobanu: Free group homomorphisms and the Post Correspondence Problem

19th April, 2021

The Post Correspondence Problem (PCP) is a classical problem in computer science that can be stated as: is it decidable whether, given two morphisms g and h between two free semigroups A and B, there is any non-trivial x in A such that g(x)=h(x)? This question can be phrased in terms of equalizers, asked in the context of free groups, and expanded: if the 'equalizer' of g and h is defined to be the subgroup consisting of all x where g(x)=h(x), it is natural to wonder not only whether the equalizer is trivial, but what its rank or basis might be. While the PCP for semigroups is famously insoluble and acts as a source of undecidability in many areas of computer science, the PCP for free groups is open, as are the related questions about rank, basis, or further generalizations. However, in this talk we will show that there are links and surprising equivalences between these problems in free groups, and classes of maps for which we can give complete answers.

Arman Darbinyan: Subgroups of left-orderable groups

18th March, 2021

A recent advancement in the theory of left-orderable groups is the discovery of finitely generated left-orderable simple groups by Hyde and Lodha. We will discuss a construction that extends this result by showing that every countable left-orderable group is a subgroup of such a group. In conjunction with this construction, we will also discuss computability properties of left-orders in groups. Based on a joint work with M. Steenbock.

Stephan Tornier: Think globally, act locally

9th December, 2020

Let G be a group acting on a regular tree. The 'local' actions that vertex stabilisers in G induce on balls around the fixed vertex are innately connected to the 'global' structure of G. I demonstrate this relationship and define a particularly accessible class of groups acting on (locally finite) regular trees by 'prescribing' said local actions, following Burger-Mozes. Being defined solely in terms of finite permutation groups, these groups allow us to introduce computational methods to the world of locally compact groups: I will outline the capabilities of a recently developed GAP package that provides methods to create, analyse and find suitable local actions.

Laura Ciobanu: On computing fixed subgroups of endomorphisms in free groups

1st October, 2020

Given an endomorphism h of a free group F, the fixed subgroup of h consists of those elements x โˆˆ F for which h(x)=x. In this talk I will give some background on fixed subgroups in free groups, and then present an algorithm which computes the fixed subgroup and the stable image for any endomorphism of the free group of rank 2. This answers, for rank 2, a question posed by Stallings in 1984 and a more recent question of Ventura. I will explain why general endomorphisms are more difficult than automorphisms, and in what ways our algorithm needs the restriction on the rank. This is joint work with Alan Logan.

Alexei Miasnikov: The Diophantine problem in classical matrix groups

24th September, 2020

The Diophantine problem in a group (ring) G is decidable if there exists an algorithm that given a finite system of equations with coefficients in G decides whether or not the system has a solution in G. I will discuss the Diophantine problem in the groups the classical matrix groups Gn(R), where R is an associative unitary ring, n > 2, and Gn(R) is one of the groups GLn(R), SLn(R), Tn(R), UTn(R), PGLn(R), or PSLn(R) (in the last two cases we assume that R is also commutative). The main result is that the Diophantine problem in Gn(R) with a chosen set of coefficients is Ptime reducible (Karp reducible) to the Diophantine problem in R with respect to a suitable set of coefficients in R. What is much more interesting is that the converse is also true. In the case when the ring R is finitely generated and commutative the result above allows one to clarify the situation completely, modulo a big conjecture in number theory.

For not finitely generated rings, more so for uncountable rings, decidability of the Diophantine problem heavily depends on the set of constants. The case of classical fields of reals, complex and p-adic numbers is especially interesting, as well as the rings of p-adic integers (which is related to pro-p completions of groups). I am going to touch on this subject and, if time permits, show some surprising examples.

Alexander Hulpke: Index computations in arithmetic groups

30th April, 2020

The question of whether a subgroup, given by generators, has finite (and then which) index is a natural question in group theory. Unfortunately, for natural groups such as SLn(โ„ค) and Sp2n(โ„ค), this question cannot have a general algorithmic solution. Nevertheless it is often possible to determine this information in many cases using a computer. I will describe some approaches to this problem and illustrate these in examples.

This is joint work with Alla Detinko (Hull) and Dane Flannery (Galway).