Tag - Computational group theory

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.