Algorithmic, topological and geometric aspects of infinite groups, monoids and inverse semigroups
(EPSRC Fellowship EP/V032003/1, September 2022-September 2027)
(EPSRC Fellowship EP/V032003/1, September 2022-September 2027)
When studying algebraic structures defined by presentations in generators and relations one is immediately confronted with certain fundamental algorithmic problems. These problems were first identified and studied in classical work in logic and topology by Thue (1914), Tietze (1912), and Dehn (1912). The most fundamental algorithmic problem in algebra is the word problem, which asks whether there is an algorithm which takes two expressions over the generators and decides whether they represent the same element. Other important algorithmic problems in algebra include the conjugacy problem, subgroup membership problem, submonoid and rational subset membership problems, and the Diophantine problem.
Combinatorial group and semigroup theory have developed in parallel, with each influencing the other. During the first few decades of the 20th century the word problem was shown to be decidable for several classes of finitely presented groups arising naturally in topology. This was followed by Magnus’s groundbreaking work in the 1930s proving that all one-relator groups have decidable word problem. The next key phase was the construction of the first examples of finitely presented semigroups and groups with undecidable word problem. Markov (1947) and Post (1947) proved independently that the word problem for finitely presented monoids is undecidable in general. This was extended by Turing (1950) to cancellative semigroups, and then by Novikov (1955) and Boone (1958) to groups. This is an example of how the areas of combinatorial group and semigroup theory have influenced each other: first finitely presented examples with undecidable word problem were constructed for semigroups and then, building on these ideas, the problem of constructing finitely presented groups with undecidable word problem was eventually solved.
Another fundamental class of algebraic structures that arises naturally when studying finitely presented groups and monoids is the family of inverse semigroups. While groups are an algebraic abstraction of permutations, and monoids of arbitrary mappings, inverse monoids correspond to partial bijections and provide an algebraic framework for studying partial symmetries of structures. This class arises naturally in many areas of mathematics, for example a number of $\mathrm{C}^*$-algebras (e.g. Cuntz–Krieger algebras) associated to symbolic dynamical systems are generated by an inverse semigroup of partial isometries. The study of inverse monoid presentations has its roots in the fundamental work of Scheiblich (1973) and Munn (1974) who described the free inverse monoid using subtrees of Cayley graphs of free groups. This shows the close connection between finitely presented inverse monoids and groups. This is a theme which has been at the heart of developments in combinatorial inverse semigroup theory, and there are now many results which show deep connections between the theories of finitely presented groups, monoids and inverse monoids.
A key theme in this area is the rich interplay between algebraic, geometric and topological ideas on the one hand, and logical and algorithmic notions, on the other. Important examples include the theory of hyperbolic groups, the Muller–Schupp Theorem characterising virtually free groups via context-free languages, Stephen’s method using Schutzenberger graphs to study presentations of inverse semigroups and the word problem, and the Anick–Groves–Squier Theorem on homological finiteness properties of monoids defined by finite complete presentations, and the related theory of collapsing schemes, and discrete Morse theory.
In this landscape of exploring algorithmic aspects of finitely presented groups and monoids, the two extremes are free groups, monoids and inverse semigroups, at one end, and finitely presented groups and monoids with undecidable word problem, at the other. The primary aim is then to understand the examples which lie between these two extremes. In particular, for any given algorithmic problem one would like to understand exactly where the boundary lies separating those classes for which the problem is decidable, and those for which the problem is undecidable. Despite the huge advances in this area over the past century, there still remain many fundamental open problems about the nature of this boundary. Important examples include: the conjugacy and isomorphism problems for one-relator groups, the subgroup and prefix membership problems for one-relator groups, the rational subset membership problem for surface groups, the word problem for two-relator groups, and the word problem for one-relator monoids.
In this area of exploring the boundaries of decidability, the one-relator case clearly plays a fundamental role. Following Magnus’s solution to the word problem for one-relator groups other important results were established for this class including: Lyndon’s Identity Theorem on the cohomology of one-relator groups, the Newman Spelling Theorem on hyperbolicity of one-relator groups with torsion, and the proof of local indicability in the torsion-free case. One-relator monoids were studied in the 1960s and 70s by Adjan, Oganessian, and Lallement, with the word problem shown to be decidable in a number of important cases. It is a well-known longstanding open problem whether the word problem is decidable for all one-relator monoids. The best known undecidability result is due to Matiyasevich (1967) who proved there are three-relator monoids with undecidable word problem. The word problem for one-relator inverse monoids was first investigated by Margolis, Meakin and Stephen in 1987, and in the years that followed it was shown to be decidable in many cases. As part of this investigation, Ivanov, Margolis and Meakin proved two important results which reveal a fundamental connection between algorithmic problems in one-relator inverse monoids, and algorithmic questions for both one-relator groups and one-relator monoids. Firstly, they proved that a positive solution to the word problem for one-relator inverse monoid presentations of the form ${\rm Inv} \langle A \; | \; w=1 \rangle$ with $w$ a reduced word would imply a positive solution to the word problem for arbitrary one-relator monoids. Secondly they proved that, for $w$ cyclically reduced, to solve the word problem in ${\rm Inv} \langle A \; | \; w=1 \rangle$ it suffices to solve a decision problem in the one-relator group ${\rm Gp} \langle A \; | \; w=1 \rangle$ called the prefix membership problem (deciding membership in the submonoid generated by prefixes of $w$).
The central aim of this research project is to study algorithmic problems in algebra with the aim of getting a better understanding of where the boundary between decidability and undecidability lies. Despite the significant advances that have been made in combinatorial and geometric group and monoid theory, the exact nature of this boundary remains poorly understood, and many fundamental questions about it remain open like those listed above. In the past decade there have been several important advances in our understanding of the algebraic, topological, geometric, and algorithmic properties of one-relator groups, and one-relator monoids and inverse semigroups and related classes. Building on this, in this project we will:
- Investigate algorithmic, logical, combinatorial, topological and geometric aspects of one-relator groups, monoids, and inverse semigroups, and related classes.
- Explore the boundary between decidability and undecidability for finitely presented groups, monoids and inverse semigroups.
Special inverse monoids: subgroups, structure, geometry, rewriting systems and the word problem
(EPSRC grant EP/N033353/1, July 2016-July 2018)
(EPSRC grant EP/N033353/1, July 2016-July 2018)
Algorithmic problems in algebra have their origins in problems in logic and topology investigated in the beginning of the 20th century by Thue (1914), Tietze (1912), and Dehn (1912). This work shows how the problems of decidability of relations in Thue systems, the homeomorphism problem for topological manifolds, and the homotopy equivalence problem in finite dimensional manifolds, are equivalent to certain algebraic problems, specifically the word problem for finitely presented semigroups and groups, and the isomorphism and conjugacy problems for finitely presented groups. Since then the subject has developed into what is now a highly active and exciting area of research, which provides a meeting point for ideas from logic, algebra and theoretical computer science.
One of the most fundamental and important algorithmic problems in algebra is the word problem. Recall that an algebraic structure (e.g. a group, semigroup, associative algebra or Lie algebra) presented by a set of generators $X$ and defining relations is said to have decidable word problem if there exists an algorithm which, for any pair of terms over the alphabet $X$, tells us whether they represent the same element. The importance of the word problem is clear: decidability of the word problem for a class of algebras indicates that we have some hope of studying the structural properties of algebras in the class, while undecidability of the word problem would suggest there would likely be major difficulties in investigating the class as a whole.
Markov (1947) and Post (1947) proved independently that the word problem for finitely presented monoids is undecidable in general. This result was extended by Turing (1950) to cancellative semigroups, and then by Novikov (1955) and Boone (1958) to groups. Given that the word problem is undecidable in general, a central theme running through the development of combinatorial and geometric group and semigroup theory over the last sixty years has been to identify and study classes of finitely presented groups and semigroups all of whose members have solvable word problem. Important examples include commutative semigroups, hyperbolic groups (in the sense of Gromov), word hyperbolic semigroups, and groups and semigroups that are automatic, admit presentations by finite complete rewriting systems, or satisfy certain small overlap conditions.
One of the most interesting classes of groups that has arisen in this context is that of one-relator groups, that is, groups defined by a finite presentation with a single defining relator. In 1932 Magnus developed a powerful general approach to one-relator groups, now known as the Magnus break-down procedure, which he used to prove several important results about arbitrary one-relator groups, including the Freiheitssatz, and decidability of the word problem. One key tool in Magnus's method is the Reidemeister-Schreier rewriting process for rewriting a presentation of a group to obtain a presentation for a subgroup. He uses this method to give structural information about one-relator groups, showing how any such group can be built up from cyclic groups, in an elegant and intricate way, by repeatedly forming amalgamated products. While this does give a solution to the word problem, the decision algorithm is complicated and its time complexity is unknown.
Since Magnus's groundbreaking work, many other important results about one-relator groups have been proved, including on: the conjugacy and isomorphism problems, hyperbolicity, residual finiteness and solvability, hopficity, automaticity, and cohomology.
Given how much combinatorial algebra has developed over the past sixty years, it is quite striking that the following problem remains open:
Open problem. Is the word problem decidable for one-relation monoids $\mathrm{Mon}\langle A \:|\: u=v \rangle$?
This is widely regarded as one of the most important longstanding open problems in the area. The problem has received significant attention, and a number of special cases have been solved. Adjan (1966) proved that the word problem for $\mathrm{Mon}\langle A \:|\: u=v \rangle$ is decidable if one of the words $u$ or $v$ is empty, or if they are both non-empty and have different initial and different terminal letters. For each of these particular cases, Adjan showed how to reduce decidability of the word problem to solving the word problem for an associated one-relator group, and then appealed to Magnus's result for one-relator groups. Adjan and Oganessian (1987) showed that the word problem in general can be reduced just to considering presentations of the form ${\rm Mon} \langle A \; | \; bsa=cta \rangle $ where $a,b,c \in A$, $b \neq c$ and $s, t \in A^*$. All such monoids are known to be left cancellative. Other important results on one-relation monoids include results on: residual finiteness, the isomorphism problem, conjugacy problem, finite derivation type ($\mathrm{FDT}$), and the Freiheitssatz.
Since Adjan's work, two of the most important contributions to the problem may be found firstly in the work on Zhang on special monoid presentations, and secondly in the work of Ivanov, Margolis and Meakin, on inverse monoid presentations.
Zhang (1991), (1992) showed how any presentation of the form $\mathrm{Mon}\langle A \:|\: w_1=1, \ldots, w_k=1 \rangle$ (so-called, special monoids) can be rewritten to give a finite presentation for its group of units $G$. Using the theory of noetherian confluent string rewriting systems, he showed that in this situation $M$ has decidable word problem if and only if $G$ has decidable word problem. In the particular case that $M$ is one-relator, one obtains a one-relator presentation for $G$, and hence applying Magnus it follows that $M$ has decidable word problem. In this way, Zhang's work both generalises, and provides a new more elegant proof of, Adjan's theorem that special one-relator monoids have decidable word problem.
Ivanov, Margolis and Meakin (2001) give an entirely new approach to the word problem for one-relation monoids via the theory of inverse monoid presentations. The study of algorithmic problems in inverse semigroups goes back to work of Scheiblich (1973) and Munn (1974) who showed how one can use birooted edge-labelled trees (Munn trees) to represent elements of the free inverse monoid. This work was extended by Stephen who used Schutzenberger graphs to study presentations of inverse semigroups. Utilising Adyan (1987), Ivanov, Margolis and Meakin (2001) made the crucial and fundamental observation that a positive solution to the word problem for one-relator special inverse monoid presentations ${\rm Inv} \langle A \; | \; w=1 \rangle$ would imply a positive solution to the word problem for one-relation monoids $\mathrm{Mon}\langle A \:|\: u=v \rangle$. This important result translates the question of decidability of the word problem for arbitrary one-relation monoids into the the realm of inverse monoids---a key step, since inverse monoids are a class that lie closer to groups than arbitrary monoids, and for groups the word problem has been solved. The word problem for one-relator special inverse monoids has been solved in some particular cases, including the case that $w$ is an idempotent.
While Reidemeister-Schreier-rewriting methods are of fundamental importance in the Magnus break-down procedure described above, no attempt has yet been made to use semigroup-theoretic -rewriting methods to investigate the corresponding problems for monoids and inverse monoids. A central theme of the current research project will be to use Reidemeister-Schreier-rewriting methods, and string rewriting systems, to carry out a comprehensive investigation of the class of special inverse monoids with the ultimate aim of making further progress towards the question of decidability of the word problem for one-relation monoids.
Various aspect of one-relation monoids, and inverse monids, will be investigated in the project. Including:
I) Subgroups of special inverse monoids
Developing RS-rewriting methods to study the units (right units, and other maximal subgroups) of special inverse monoids.
II) Rewriting systems and the word problem
To develop a theory of convergent rewriting systems which operate on Munn trees, and apply it to relate decidability of the word problem of the special inverse monoid $M$ and its group of units $G$.
III) Directed geometry
Investigate the directed geometry of the one-relation left-cancellative monoids, and the directed geometry of the Schutzenberger graphs, and groups, of special one-relator inverse monoids.
IV) Homological finiteness properties
Investiage the question of whether every one-relation monoid admits a presentation by a finite complete rewriting system, and closely related to this the question of whether every such monoid is of homological type left- and right-FP infinity?
The project involes extensive collaboration with researchers both from the UK and from universities in Portugal, Serbia and the USA. We will organise a workshop midway through the project, centred around its main themes, which will bring together leading experts from a diverse range of topics in algebra, logic and theoretical computer science.