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.
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.
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.
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.
I will answer this question by explaining each of the terms used, then give some examples, and define an even more general class called 𝒞-Cayley polynomial time computable. I will not however answer the obvious follow-on question "and why would you care?"
I will report on some recent progress on the group isomorphism problem.
Using tricks from L2-homology and some abstract algebra we will show how to algorithmically compute the structure of the fibred cohomology classes of free-by-cyclic groups and most 3-manifolds. (Joint with Giles Gardam.)
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.
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.
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).
You must be logged in to post a comment.