📣 Help Shape the Future of UKRI's Gateway to Research (GtR)

We're improving UKRI's Gateway to Research and are seeking your input! If you would be interested in being interviewed about the improvements we're making and to have your say about how we can make GtR more user-friendly, impactful, and effective for the Research and Innovation community, please email gateway@ukri.org.

Algorithmic, topological and geometric aspects of infinite groups, monoids and inverse semigroups

Lead Research Organisation: University of East Anglia
Department Name: Mathematics

Abstract

One of the most amazing results of twentieth century mathematics was the discovery by Alonzo Church and Alan Turing that there are problems in mathematics which cannot be solved, in the sense that there is no algorithm to solve them. This means that no matter how powerful a computer you use to help you, there are some mathematical problems that you will still not be able to solve. If the problem that cannot be solved is in the form of a "yes" or "no" question, then we call it an undecidable problem. On the other hand, if it can be solved, then we say that it is a decidable problem.

There are many decision problems that arise naturally in algebra. Important examples include the word problem, which asks us to decide whether two different algebraic expressions are equal to each other, and the membership problem, which asks us to decide whether one element in an algebraic structure can be expressed in terms of another collection of elements. Being able to solve problems like these is important when studying infinite algebraic structures.

The main topic of this project is to investigate a range of decision problems like these for three classes of algebraic objects called groups, monoids and inverse semigroups. These three classes arise naturally in the study of symmetry and partial symmetry in mathematics. An important tool for defining infinite groups, monoids and inverse semigroups, is given by the theory of presentations in generators and relations. The idea is that the elements of the group or monoid are represented by strings of letters, called words. We are also given a set of defining relations, which are rules telling us that certain pairs of words are equal to each other. Two words are then equal if one can be transformed into the other by applying the relations. For example, if we use the letters x and y, and we have a single defining relation xy=yx, then the words xyx and yxx are equal since xyx = (xy)x = (yx)x = yxx. On the other hand, the words xy and yy are not equal. The problem of determining whether or not two words are equal to each other is the word problem mentioned above.

When we define a monoid or group using a presentation, by increasing the number of relations we can increase the complexity of the monoid or group that we define. If there are no relations these are called free monoids and groups, and because of their simple structure several natural decision problems, like the word problem, can be seen to be decidable in these cases. In contrast, it is known that there are monoids, groups, and inverse semigroups which are defined by finitely many generators and relations, but have undecidable word problem. The situation is the similar for the many other decision problems arising in algebra.

It is natural to ask whether groups or monoids which are close to being free, in some sense, will have good algorithmic properties. An important positive result of this kind for groups is Magnus's theorem which shows that groups defined by a single defining relation all have decidable word problem. On the other hand, it was recently discovered that there are inverse monoids defined by a single defining relation that have undecidable word problem. However, it remains an important longstanding open problem whether the word problem is decidable for one-relator monoids.

There are many fascinating open problems like this one which ask fundamental questions about where the boundary between decidability and undecidability lies for finitely presented groups, monoids and inverse semigroups. In this project we will explore a range of interrelated problems of this kind. This will be done by developing geometric and topological methods, which use the "shape" of these algebraic objects, or the way they interact with spaces, to shed light on their algorithmic properties.
 
Description (a) Maximal subgroups and right units of special inverse monoids (PI Gray in joint work with Dolinka and Kambites)

We have proved results which have significantly advanced our understanding of the geometry of Cayley graphs, and Schutzenberger graphs, of special inverse monoids. We have then applied this to prove results about the algebraic and algorithmic properties of monoids in this class. Special inverse monoids are those defined by presentations where all defining relations are of the form w=1. This class plays a central role in the study of one-relator monoids, groups and inverse semigroups as a consequence of results of Ivanov, Margolis and Meakin (2001) that show how the word problem for one-relator monoids can be reduced to the word problem in certain special inverse monoids. Hence understanding the algebraic and algorithmic properties of special inverse monoids is a vital part of this research project. This work has therefore allowed us to achieve several objectives in research stream (II) "Topology, homology and geometry" of the project.

In more detail, in joint work of the PI and Kambites (Gray R, Kambites M. (2025). Maximal subgroups of finitely presented special inverse monoids. Journal of the European Mathematical Society, doi: 10.4171/jems/1585) we have shown that the maximal subgroups which can arise in such monoids are exactly the recursively presented groups. We also prove that the possible groups of units are exactly the finitely generated recursively presented groups; this improves upon a result of, and answers a question of, the PI and Ruskuc. These results give the first significant insight into the maximal subgroups of such monoids beyond the group of units, and the results together demonstrate that it is possible for the subgroup structure to have a complexity which significantly exceeds that of the group of units.

Also in joint work of the PI and Kambites, in (Gray R, Kambites M. (2023). Subgroups of E-unitary and R_1-injective special inverse monoids. arXiv), we continued the study of the structure of general subgroups (in particular maximal subgroups, also known as group H-classes) of special inverse monoids. The work described in the previous paragraph established that these can be quite wild, but in this paper we show that if we restrict to special inverse monoids which are E-unitary (or have a weaker property we call R1-injectivity that we introduce) the maximal subgroups are strongly governed by the group of units. In particular, every maximal subgroup has a finite index subgroup which embeds in the group of units. We give a construction to show that every finite group can arise as a maximal subgroup in an R1-injective special inverse monoid with trivial group of units.

In related joint with of PI and Dolinka in (Dolinka I, Gray R. (2023). Prefix monoids of groups and right units of special inverse monoids. Forum of Mathematics, Sigma, doi: 10.1017/fms.2023.99) we conduct a systematic investigation of prefix monoids of finitely presented groups. A prefix monoid is a finitely generated submonoid of a finitely presented group generated by the prefixes of its defining relators. Important results of Guba (1997), and of Ivanov, Margolis and Meakin (2001), show how the word problem for certain one-relator monoids, and inverse monoids, can be reduced to solving the membership problem in prefix monoids of certain one-relator groups. Motivated by this, in this paper of the PI and Dolinka we study the class of prefix monoids of finitely presented groups. We obtain a complete description of this class of monoids. All monoids in this family are finitely generated, recursively presented and group-embeddable. Our results show that not every finitely generated recursively presented group-embeddable monoid is a prefix monoid, but for every such monoid if we take a free product with a suitably chosen free monoid of finite rank, then we do obtain a prefix monoid. Conversely we prove that every prefix monoid arises in this way. Also, we show that the groups that arise as groups of units of prefix monoids are precisely the finitely generated recursively presented groups, while the groups that arise as Schutzenberger groups of prefix monoids are exactly the recursively enumerable subgroups of finitely presented groups. We obtain an analogous result classifying the Schutzenberger groups of monoids of right units of special inverse monoids. We also give some examples of right cancellative monoids arising as monoids of right units of finitely presented special inverse monoids, and show that not all right cancellative recursively presented monoids belong to this class.

(b) One-relator groups, monoids and inverse monoids (PI Gray in joint work with SRA Foniqi, Nyberg-Brodda and Ruskuc)

In joint work of the PI, SRA on the project Foniqi, and Nyberg-Brodda, we have made major advances in research stream (I) "Word and membership problems" which have allowed us to achieve several of the key objectives of this part of the project. As a consequence we have already obtained complete answers to several of the concrete problems posed in the original research proposal. In particular we have now answered Problem 2 (part (a)) by constructing positive one-relator groups with undecidable submonoid membership problem, and Problem 3 (part (i)) by constructing the first examples of one-relation monoids with undecidable submonoid membership problem. Our results also make significant progress towards resolving Problem 4 by obtaining reduced words of the form uv^{-1} with u and v both positive, for which prefix membership is undecidable. Also the positive two-relator inverse monoid with undecidable word problem that we construct is important step towards resolving Problem 5 by building a one-relator inverse monoid with cyclically reduced defining relator (and eventually a positive defining relator) with undecidable word problem. We have also established key structural results, in joint work of the PI and Ruskuc, about special one-relator inverse monoids. Among other things, these results give sufficient conditions for the group of units to be a one-relator group. In contrast we show that the group of units of a one-relator special inverse monoid need not be a one-relator group and establish a key connection between the question of finite presentability of groups of units of special inverse monoids and the recent major result of Jaikin--Zapirain and Linton on coherence of one-relator groups.

In more detail, motivated by approaches to the word problem for one-relation monoids arising from work of Adian and Oganesian (1987), Guba (1997), and Ivanov, Margolis and Meakin (2001), in joint work of the PI, Foniqi, and Nyberg-Brodda in (Foniqi I, Gray R, Nyberg-Brodda C. (2025). Membership problems for positive one-relator groups and one-relation monoids. Canadian Journal of Mathematics, doi: 10.4153/s0008414x24000798) we have studied the submonoid and rational subset membership problems in one-relation monoids and in positive one-relator groups. In this paper we give the first known examples of positive one-relator groups with undecidable submonoid membership problem, and apply this to give the first known examples of one-relation monoids with undecidable submonoid membership problem. We construct several infinite families of one-relation monoids with undecidable submonoid membership problem, including examples that are defined by relations of the form w=1 but which are not groups, and examples defined by relations of the form u=v where both of u and v are non-empty. As a consequence we obtain a classification of the right-angled Artin groups that can arise as subgroups of one-relation monoids. We also give examples of monoids with a single defining relation of the form aUb=a, and examples of the form aUb=aVa, with undecidable rational subset membership problem. We give a one-relator group defined by a freely reduced word of the form uv^{-1} with u,v positive words, in which the prefix membership problem is undecidable. Finally, we prove the existence of a special two-relator inverse monoid with undecidable word problem, and in which both the relators are positive words. As a corollary, we also find a positive two-relator group with undecidable prefix membership problem. In proving these results, we introduce new methods for proving undecidability of the rational subset membership problem in monoids and groups, including by finding suitable embeddings of certain trace monoids.

In joint work of the PI and Ruskuc in (Gray R, Ruskuc N. (2023). ON GROUPS OF UNITS OF SPECIAL AND ONE-RELATOR INVERSE MONOIDS. Journal of the Institute of Mathematics of Jussieu, (4), doi: 10.1017/s1474748023000439) we investigate the groups of units of one-relator and special inverse monoids. These are inverse monoids which are defined by presentations where all the defining relations are of the form r=1. We develop new approaches for finding presentations for the group of units of a special inverse monoid, and apply these methods to give conditions under which the group admits a presentation with the same number of defining relations as the monoid. In particular our results give sufficient conditions for the group of units of a one-relator inverse monoid to be a one-relator group. When these conditions are satisfied these results give inverse semigroup theoretic analogues of classical results of Adjan for one-relator monoids, and Makanin for special monoids. In contrast, we show that in general these classical results do not hold for one-relator and special inverse monoids. In particular, we show that there exists a one-relator special inverse monoid whose group of units is not a one-relator group (with respect to any generating set), and we show that there exists a finitely presented special inverse monoid whose group of units is not finitely presented. This result provided an important foundation for the subsequent results of the PI and Kambites in (a) above where we classify the groups of units of finitely presented special inverse monoids.

(c) Algebraic and algorithmic properties of Braid and Artin groups (PI Gray in joint work with Nyberg-Brodda, and SRA Foniqi in joint work with Antolín, de la Cruz, Cumplido)

An important class of groups related to one-relator groups are the so-called right-angled Artin groups (RAAGs). These groups, and their monoid counterparts called trace monoids, have provided key tools for constructing one-relator groups, monoids and inverse monoids with interesting algorithmic properties (see e.g. the results in (b) above). In particular, the classification of RAAGs with decidable submonoid membership problem due to Lohrey and Steinberg (2008) had been a cornerstone of recent undecidability results for one-relator groups and (inverse) monoids. As part of research stream (I) "Word and membership problems", in joint work of the PI and Nyberg-Brodda we have extended the result Lohrey and Steinberg to the much broader class of Artin groups (which include Braid groups). This work establishes are an important contribution to research stream (I) since they establish key decidability results for classes of groups related to one-relator groups. This work also opens up the study of new algorithmic problems for one-relator groups (and related classes) such as the identity problem and the group problem. Related results were also established by the SRA Foniqi. In addition, Foniqi has also established several other important structural results for Artin groups in joint work with Antolín and also with de la Cruz and Cumplido.

In more detail, in joint of the PI and Nyberg-Brodda in (Gray R, Nyberg-Brodda C. (2024). Membership problems in braid groups and Artin groups. arXiv) we study several natural decision problems in braid groups and Artin groups. We classify the Artin groups with decidable submonoid membership problem in terms of the non-existence of certain forbidden induced subgraphs of the defining graph. Furthermore, we also classify the Artin groups for which the following problems are decidable: the rational subset membership problem, semigroup intersection problem, and the fixed-target submonoid membership problem. In the case of braid groups our results show that the submonoid membership problem, and each and every one of these problems, is decidable in the braid group Bn if and only if n is less than 4, which answers an open problem of Potapov (2013). Our results also generalize and extend results of Lohrey & Steinberg (2008) who classified right-angled Artin groups with decidable submonoid (and rational subset) membership problem. In closely related work of the SRA Foniqi, he demonstrate that the submonoid membership problem and the rational subset membership problem are equivalent in Artin groups.

In joint work of the SRA Foniqi with Antolín in (Antolín Y, Foniqi I. (2024). Subgroups of even Artin groups of FC type. Journal of Group Theory, doi: 10.1515/jgth-2023-0093) they prove a Tits alternative theorem for subgroups of finitely generated even Artin groups of FC type (EAFC groups), stating that there exists a finite index subgroup such that every subgroup of it is either finitely generated abelian, or maps onto a non-abelian free group. Parabolic subgroups play a key role, and it is shown that parabolic subgroups of EAFC groups are closed under taking roots. Also, in joint work of the SRA Foniqi with de la Cruz and Cumplido in (de la Cruz B, Cumplido M, Foniqi I. (2024). On Artin groups admitting retractions to parabolic subgroups. arXiv) they generalize the retractions to standard parabolic subgroups for even Artin groups to FC-type Artin groups and other more general families. They prove that these retractions uniquely extend to any parabolic subgroup, and they use retractions to generalize results of Antolín and Foniqi from above. As a corollary, they characterize coherence for the FC case.

(d) Topological and homological finiteness properties of special and one-relator monoids (PI Gray in joint work with B. Steinberg).

As part of research stream (II) "Topology, homology and geometry" we continue to develop the theory of topological and homological finiteness properties of finitely presented monoids. This connects with the word problem via the Anick-Groves-Squier theorem which says that if a group admits a presentation by a finite complete rewriting system then it must satisfy the homological finiteness property FP infinity. This relates to Major Problem 4 in the proposal which asks whether every one-relator monoid admits a finite complete presentation. A positive answer to this question would answer the famous longstanding open problem of whether all one-relation monoids have decidable word problem. So in Problem 6 of the research proposal we ask which homological and topological finiteness properties are satisfied by one-relation monoids. We have now proved results that answer this question for several key finiteness properties.

In joint work of the PI with Steinberg in (Gray R, Steinberg B. (2024). Topological finiteness properties of monoids, II: Special monoids, one-relator monoids, amalgamated free products, and HNN extensions. Documenta Mathematica, (3), doi: 10.4171/dm/959) we describe the geometry of Cayley graphs of special monoids and use this to give results relating the one-sided homological and topological properties of the monoid to those of its group of units. We apply this to show all special one-relator monoids satisfy the property left (and right) FP infinity. In current ongoing joint work we are now extending these results to the far more challenging two-sided case which once established will fully resolve Problem 6 from research stream (II) for one-relator monoids.

In addition to this, in (Gray R, Steinberg B. (2024). Topological finiteness properties of monoids, II: Special monoids, one-relator monoids, amalgamated free products, and HNN extensions. Documenta Mathematica, (3), doi: 10.4171/dm/959) we also show how our topological approach can be used to prove results about the closure properties of various homological and topological finiteness properties for amalgamated free products and HNN-extensions of monoids. To prove these results we introduce new methods for constructing equivariant classifying spaces for monoids, as well as developing a Bass-Serre theory for free constructions of monoids.

(e) Free idempotent-generated regular *-semigroups. (PI Gray in joint work with East, Muhammed and Ruskuc)

A central theme in the research project is the study of inverse monoids defined by presentations with generators and relations. In joint work of the PI East, Muhammed and Ruskuc in (East J, Gray R, Muhammed P, Ruškuc N. (2024). Projection algebras and free projection- and idempotent-generated regular *-semigroups. arXiv) we have been developing the theory of an important generalisation of inverse monoids called regular *-semigroups. This family captures many interesting example such as many families of diagram monoids. As part of our work in this area we have computed presentations of free projection-generated regular *-semigroups, and their maximal subgroups, and used them to study regular *-semigroups including their algorithmic properties such as the word problem. Thus these results shed light on algorithmic properties of regular *-semigroups which is particularly relevant for research stream (I) of the research project.

(f) Twisted right-angled Artin groups (SRA Foniqi)

In addition to Artin group, another interesting generalisation of RAAGs arising from work of the SRA on the project Foniqi is the class of twisted right-angled Artin groups. As part of research stream (I) the SRA Foniqi has proved various results about algorithmic and algebraic properties of this class.

In more detail, in (Foniqi I. (2024). Twisted right-angled Artin groups. arXiv) he constructs complete rewriting systems for twisted right-angled Artin groups which solves the word problem for this class. In (Foniqi I. (2024). Subgroup separability of twisted right-angled Artin groups. arXiv) he characterises the twisted right-angled Artin groups that are subgroup separable using only their defining mixed graphs. This is an algebraic property that closely relaters to the subgroup membership problem, which is of central importance to research stream (I).

(g) Diophantine problem, equations, and first-order theory (SRA Levine in joint work with Elliott)

The key topic of research stream (III) is to study the "Diophantine problem, equations, and first-order theory" of groups and monoids. As part of his work on this research stream in (Elliott L, Levine A. (2025). The Diophantine problem in Thompson's group F. arXiv.) SRA Levine in joint work with Elliott have proved that the Diophantine problem in Thompson's group F is undecidable. Their proof uses the facts that F has finite commutator width and rank 2 abelianisation combined with results and ideas from work of Büchi and Senger and of Ciobanu and Garreta.
Exploitation Route As well as leading to the discoveries outlined above, this research has also opened up several new research directions which will be explored in the future by the PI and SRAs together with his future research collaborators, PhD and research students.
Sectors Digital/Communication/Information Technologies (including Software)
 
Description This project is still in progress, but has already led to 13 research articles including 6 papers published in leading mathematics and computer science journals and an additional 7 articles that have been submitted for publication and are available as preprints on the arxiv. These papers have already received over 17 citations showing the impact that this research is starting to have. In addition to this, the topic of the research project formed the basis of an activity stand "The Funfair of Impossible Problems" designed by the PI Gray and delivered at the Norwich Science Festival in February 2024 and February 2025. On each occasion we ran the activity stand for an entire day interacting with hundreds of members of the public, including families and children. Our session was based on the question: Can a computer solve all the problems in the universe? Can ChatGPT answer any question that we ask it? Can a computer predict the outcome of the "game of life"? The answer to these questions is surprisingly "no"! Despite the boom in technology and artificial intelligence and increasingly powerful computers, there are seemingly simple problems that cannot be solved by any computer system. These are called "undecidable problems", and in our activity we illustrated some of them by using interactive activities and games, just like at the funfair. This outreach activity helped children (and other participants) to develop their solving-problem skills by actively participating in games and searching for solutions to our problem. It helped members of the public understand the discoveries of the important British mathematician and computer scientist Alan Turing. It allowed us to explain the important idea that there are limits to what can be done using AI and/or using quantum computers. These outreach activities were supported by this EPSRC Fellowship grant. Since the core themes of this research project are concerned with the question of which problems can be solved using computers this outreach activity also has helped explain to the public the importance of the fundamental research being carried out in this project.
First Year Of Impact 2024
Sector Education
Impact Types Societal
 
Description Activity stand "Funfair of Impossible Problems" at the Norwich Science Festival, 2024 and 2025 
Form Of Engagement Activity Participation in an activity, workshop or similar
Part Of Official Scheme? No
Geographic Reach Regional
Primary Audience Public/other audiences
Results and Impact Together with a team of academics and research students from the UEA maths and computer science departments, we ran an interactive activity stand "Funfair of Impossible Problems" at the Norwich Science Festival in February 2024 and 2025.

The Norwich Science Festival has grown from inception and its first outing in 2016 to a nationally recognised Festival that showcases groundbreaking research and brings the best household names the region. Its aims are to spark curiosity and inspire a lifelong interest in science, and to engage with new audiences, specifically those from communities who have low science capital and do not currently engage with the Festival.

Our activity stand "Funfair of Impossible Problems" had range of different mathematical games for young people and their families to play. Each of the games was designed to explain that there are many seemingly simple problems that cannot be solved by any computer system.

Using these games we were able to explain this central idea of my current fellowship project, that of "undecidable problems", to many members of the public.

We interacted with hundreds of children, and their families, at our stand throughout the day. We got feedback that many people really enjoyed playing our games, and that this was a great way of getting young people engaged with mathematics.
Year(s) Of Engagement Activity 2024,2025
URL https://norwichsciencefestival.co.uk/