Special inverse monoids: subgroups, structure, geometry, rewriting systems and the word problem

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

Abstract

This project is concerned with the study of certain fundamental objects in algebra called groups, monoids and inverse monoids. These objects arise naturally in the mathematical study of symmetry and partial symmetry. Given any mathematical structure on a set, the collection of structure-preserving mappings from the set to itself form a monoid, the collection of all symmetries form a group, while the partial symmetries give rise to an inverse monoid. In this way these algebraic objects pervade mathematics.

One way to represent a group, monoid of inverse monoid is via a presentation. The elements are represented by strings of letters, called words. We are also given a set of pairs of words, called defining relations, which are rules telling us that certain pairs of words are equal to each other. Then two words are defined to be equal if one can be turned into the other by a sequence of applications of the defining relations. For example, using the alphabet with the letters a and b, and just with a single defining relation ab=ba, the words aba and aab are equal since aba = a(ba) = a(ab) = aab. On the other hand, the words bb and ab are not equal since one cannot be transformed into the other using the relation ab=ba.

A famous result in twentieth century mathematics shows that there does not exist, in general, an algorithm to decide whether two words are equal in a monoid defined by a finite presentation. This is known as the word problem, and is also undecidable in general both for finitely presented groups and inverse monoids. These results are important since they were some of the first concrete natural decision problems proven to be undecidable in general. 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 to be major difficulties in investigating the class as a whole.

Given that the word problem is undecidable in general, a lot of research has been done to identify classes of monoids for which the word problem is decidable. One fundamental idea is that by restricting the number of defining relations in the presentation, this should limit the complexity of the object that it defines. An important 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. In contrast to this, the following problem remains open:

Open problem. Is the word problem decidable for monoids with a single defining relation?

This important problem has been open for more than half a century, and is one of the main motivations for our research project. Rather than attacking this problem directly, the project instead aims to develop various aspects of the theory of certain inverse monoids, called special inverse monoids. Specifically the project will develop certain important tools from theoretical computer science, from the area of rewriting systems, to investigate the subgroups, structure, and geometry of these inverse monoids. We will then apply this theory to investigate the word problem for these inverse monoids which will then lead to important results about decidability of the word problem, in general, for monoids defined by a single defining relation.

The project will involve 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.

Planned Impact

This is a wide-ranging project which has connections with numerous different topics in mathematics and computer science. The immediate impact of the project will be felt in these research areas, and is outlined in the National Importance and Academic Impact section of the Case for Support. The details of how academics working in these areas will benefit from the research is explained in the Academic Beneficiaries section. Also, the Pathways to Impact statement outlines how the project has been designed to maximise its impact in mathematics and other disciplines, and its potential future applications outside academia.

In this section we concentrate on the longer-term potential impact of this project and its subject area.

One of the central problems motivating this research project is the question of decidability of the word problem for one-relation monoids. Algorithmic questions such as this are of central importance to contemporary research in algebra, logic and combinatorics. This question is fundamental, and answering it would be a huge step forward in our general understanding of the boundary between problems which are decidable and those that are not. The problem has been open for more than half a century and is regarded as one of the key unresolved questions about decidability. Because of this, the progress that is made on this problem as a consequence of the research done in this project, has the potential for major long-term impact. The results will be of interest to experts working in combinatorial and geometric group and semigroup theory, algorithms decidability and complexity, rewriting systems, automata theory and formal language theory. If the project leads to a positive solution to the word problem, as well as being a major result, this would open up a whole host of new questions to be explored, such as complexity of the word problem, and whether such monoids admit presentations by complete rewriting systems. On the other hand, if the project led to a counterexample, then new techniques would have been needed for its construction (e.g. methods encoding the halting problem into the relation) and these techniques would then be explored and developed further by other researchers to obtain applications to other decidability questions.

Since the project has connections with such a diverse range of topics, another long-term impact it will have is to strengthen the connections between these areas. As explained in the National Importance and Academic Impact section of the Case for Support, there has been a recent trend aimed at increasing communication and collaboration internationally between researchers in semigroup theory and group theory, algorithms, decidability and complexity, combinatorics, constraint satisfaction and connections with logic and model theory. This is demonstrated by numerous conferences and workshops that have been held over the past few years at which researchers with different areas of expertise from these fields have been brought together to share their ideas, methods and results. This research project builds on, and continues, this trend. It will strengthen connections between several different areas of mathematics and computer science. This will also ensure that researchers from different areas are involved in explaining their work to a broader audience, which in turn helps them understand how to explain it to an audience outside of their immediate area of expertise. In this way, this project will indirectly have a positive impact on the understanding and appreciation of mathematics in the wider population.

Publications

10 25 50
publication icon
Cain A (2019) Crystal monoids & crystal bases: Rewriting systems and biautomatic structures for plactic monoids of types A, B, C, D, and G2 in Journal of Combinatorial Theory, Series A

publication icon
Cain A (2017) On finite complete rewriting systems, finite derivation type, and automaticity for homogeneous monoids in Information and Computation

publication icon
Coleman T (2019) Permutation monoids and MB-homogeneity for graphs and relational structures in European Journal of Combinatorics

publication icon
Dolinka I (2021) New results on the prefix membership problem for one-relator groups in Transactions of the American Mathematical Society

publication icon
Dolinka I (2018) Universal locally finite maximally homogeneous semigroups and inverse semigroups in Forum Mathematicum

publication icon
Dolinka I (2017) On regularity and the word problem for free idempotent generated semigroups THE WORD PROBLEM FOR FREE IDEMPOTENT GENERATED SEMIGROUPS in Proceedings of the London Mathematical Society

publication icon
East J (2017) Diagram monoids and Graham-Houghton graphs: Idempotents and generating sets of ideals in Journal of Combinatorial Theory, Series A

publication icon
East J (2021) Ehresmann theory and partition monoids in Journal of Algebra

publication icon
Gray R (2019) Undecidability of the word problem for one-relator inverse monoids via right-angled Artin subgroups of one-relator groups in Inventiones mathematicae

publication icon
Gray R (2022) Topological finiteness properties of monoids, I: Foundations in Algebraic & Geometric Topology

 
Description (a) Undecidability of the word problem for one-relator inverse monoids via right-angled Artin subgroups of one-relator groups. The question of whether the word problem is decidable for all one-relator monoids is one of the most fundamental longstanding open problems in combinatorial algebra. An important result of Ivanov, Margolis and Meakin (2001) shows that a positive solution to the word problem for one-relator special inverse monoids of the form Inv would give a positive solution to the word problem for arbitrary one-relator monoids. This result motivated subsequent work investigating the question of whether all special one-relator inverse monoids have decidable word problem. This problem has now been shown to have a positive answer in several cases, by several different authors, including when the defining relator word is: an idempotent word, a sparse word, a one-relator surface group relation, a Baumslag--Solitar relation, or a relation of Adjan type. There are several places in the literature where it is mentioned that the problem of whether special one-relator inverse monoids have decidable word problem remains unsolved. The first place this question appears in the literature is in a paper of Margolis, Meakin and Stephen published in 1987, where they in fact make the conjecture that the word problem is decidable for all special one-relator inverse monoids. One of the most important discoveries made during this research project is a proof that, quite surprisingly, this conjecture does not hold. This result answers the main problem set out in the original Case for Support for this research project. Consequently it achieves the main objective of the research project. In more detail, specifically we have proved the following results: (1) There is a one-relator inverse monoid Inv with undecidable word problem; and (2) There are one-relator groups with undecidable submonoid membership problem. The second of these results is proved by showing that for any finite forest the associated right-angled Artin group embeds into a one-relator group. To prove (1) a new construction is introduced which uses the one-relator group and submonoid in which membership is undecidable from (2) to construct a one-relator inverse monoid Inv with undecidable word problem. These results have now been published in the leading mathematics journal Inventiones Mathematicae (2020, doi: 10.1007/s00222-019-00920-2). The new construction the PI introduced in this paper has also subsequently been used in the paper https://arxiv.org/abs/1912.00950 to prove new results about the word problem for inverse monoids with hyperbolic Schutzenberger graphs.

(b) Topological finiteness properties of monoids, string rewriting systems with applications to special monoids (joint work with B. Steinberg, City College of New York). We have developed a theory of topological finiteness properties of monoids by studying monoids acting on CW-complexes. Our theory allows us to define and investigate topological analogues of some important homological finiteness properties which arise in the theory of string rewriting systems. These topological finiteness properties are called property F_n and the geometric dimension of the monoid. A major benefit of our new approach is that it allows one to use topological arguments to deduce homological information about a monoid. To show a monoid satisfies a certain homological finiteness property it suffices to construct an appropriate equivariant classifying space for the monoid, which is a certain CW complex on which the monoid acts in a suitable way. Applications of our topological approach include (1) A topological proof of the Anick-Groves-Squier theorem for monoids, by developing an M-equivariant analogue of Brown's theory of collapsing schemes (2) Results about the closure properties of left-Fn and bi-Fn for amalgamated free products and HNN extensions. (3) A topological proof that a free inverse monoid on one or more generators is neither of type left-FP_2 nor right-FP_2 generalising a classical result of Schein that such monoids are not finitely presented. Another major application of our results is a proof of a Lyndon's Identity theorem for arbitrary one-relator monoids, which also answers a 20-year-old conjecture of Kobayashi. See (c) below for more details of this result. We also apply our methods to prove results about the homological finiteness properties of special monoids, that is, monoids defined by finite presentations where every defining relation is of the form r=1. We prove that if M is a special monoid with group of units G then if G is of type FP_n, then M is of type left- and right-FPn; and moreover that cd G = cd M = max{2, cd G}. As a corollary we obtain that all special one-relation monoids are of type left- and right-FP infinity, answering a question of Kobayashi for special one-relator monoids. We also recover Kobayashi's result that if the relator is not a proper power then the cohomological dimension is at most 2. These results on special monoids relate to the word problem for one-relator monoids in the following way. If a monoid admits a convergent presentation (a FCRS) then it has decidable word problem. It is open whether every one-relation monoid admits a FCRS. It follows from the Anick-Groves-Squier Theorem that if a monoid has FCRS then it is of type FP infinity. So it is natural to ask whether every one-relator monoid is FP infinity. Our topological approach gives a solution to this problem in the case of monoids with a defining relation of the form r=1. The result is achieved by analysing the geometry of the Cayley graphs of special monoids and showing that they are tree-like modulo their Schutzenberger graphs. In a research visit to Steinberg in spring 2018 as part of this research project, we extended this result, proving the result for arbitrary one-relator monoids. See (c) below for more details of this result. The results giving the foundations of our topological methods, and the above-mentioned applications, have been written up and submitted for publication. Preprints of these articles are available on the arxiv at: https://arxiv.org/abs/1706.04387, https://arxiv.org/abs/1805.03413, and https://arxiv.org/abs/2002.07690.

(c) A Lyndon's Identity theorem for one-relator monoids (joint work with B. Steinberg, City College of New York). One-relator groups are a fundamental class of groups in combinatorial and geometric group theory, and there is an extensive literature devoted to their study. The word problem for one-relator groups was solved by Magnus in 1932. Later in 1950 Lyndon published a highly influential paper in which he computed the cohomology of an arbitrary one-relator group. As Lyndon states in his paper, his result, which is now known as Lyndon's Identity Theorem, may be viewed as a complementary result to Magnus's word problem solution: that of determining all identities among the relations. Lyndon's work implies that all one-relator groups satisfy the homological finiteness property FP infinity, and that torsion free one-relator groups have cohomological dimension at most two. When interpreted topologically, Lyndon's results show how to construct certain natural classifying spaces for one-relator groups which are, in a sense which can be made precise, as small as possible. In particular, this can be used to show that the presentation 2-complex for a torsion-free one-relator group is aspherical, and thus is a classifying space for the group. The question of whether one-relator monoids have decidable word problem is an important longstanding open problem. While the question is open in general, it has been solved in a number of special cases e.g. in work of Adjan (1966) and Adjan and Oganessian (1987). Applying the general topological methods developed in (b) above, we have found new methods for constructing equivariant classifying spaces for one-relator monoids which, in particular, have allowed us to prove that all one-relator monoids are of type FP infinity. We also apply our results to classify the one-relator monoids of cohomological dimension at most 2, and to describe the relation module, in the sense of Ivanov, of a torsion-free one-relator monoid presentation as an explicitly given principal left ideal of the monoid ring. These results give a natural monoid-theoretic analogue of Lyndon's identity theorem for one-relator groups, and they also give a positive answer to an open problem originally posed by Kobayashi in 2000. As mentioned above, the fact that one-relator monoids all have type FP infinity is also of interest because of its connection with the question of whether all one-relator monoids admit presentations by finite complete rewriting systems. Indeed, the Anick-Groves-Squier theorem implies that if a monoid admits a presentation by a finite complete rewriting system then that monoid must be of type FP infinity. Our result that one-relator monoids are type FP infinity may thus be regarded as some evidence towards the possibility that one-relator monoids admit finite complete presentations, which if true would imply that they have decidable word problem. One key question we said we would attack in the original Case for Support for this research project was whether all one-relator monoids are of type FP infinity. These results achieve this objective by giving a positive answer to that question, and at the same time our results give more information about the topological and homological finiteness properties of one-relator monoids by establishing an analogue of Lyndon's Identity Theorem for this class. These results have been written up and submitted for publication. A preprint of this article is available on the arxiv at: https://arxiv.org/abs/1910.09914.

(d) On units of special and one-relator inverse monoids (joint work with N. Ruskuc, St Andrews). One of the central themes of the research project is to analyse the extent to which Adian and Zhang's approaches to one-relator special monoids might be developed to give an analogous theory for special inverse monoids. This could then be applied to give new insights into the important problem of decidability of the word problem for one-relator special inverse monoids, via the results of Ivanov, Margolis, and Meakin, as explained above. The approach of Adian and Zhang for special one-relator monoids is to first show that the group of units is a one-relator group, and to reduce the word problem for the monoid to that of the group of units, by relating the structure of the monoid with the structure of its units. An important part of this is understanding how the presentation for the special one relator monoid can be rewritten to obtain a presentation for the group of units. Correspondingly, this is a key step in developing a corresponding theory for special inverse monoids. The O'Hare monoid of Margolis and Meakin shows that this question is far more difficult than the corresponding question for special monoids. We began by analysing this example. We found a method for computing the group of units in this case. Building on this, we have now made progress on the general case by developing new methods for computing the groups of units of one-relator special inverse monoids. We have also devised a procedure, combining ideas of Adian and Benois, which computes invertible pieces of the relator. Our results can be applied to show that in many natural situations, the group of units of a special one-relator inverse monoid is a one-relator group. On the other hand, we also introduce new constructions which show that, rather surprisingly, there are examples of special one-relator inverse monoids whose groups of units are not one-relator groups. The same construction can be used to exhibit other interesting examples, such as a finitely presented special inverse monoid whose group of units is not finitely presented. This behaviour is surprising and interesting, since it contrasts with the way that non-inverse special inverse monoids behave. These results give answers to several of the central questions about units of special inverse monoids posed in the original Case for Support for this research project. This work also establishes links between these problems and fundamental questions in combinatorial and geometric group theory, including the open problem of whether all one-relator groups are coherent. These results have been written up and submitted for publication. A preprint of this article is available on the arxiv at: https://arxiv.org/abs/2103.02995.

(e) On the prefix membership problem for certain one-relator groups (joint work with I. Dolinka, Novi Sad). Results of Ivanov, Margolis, and Meakin from 2001 show that if w is a cyclically reduced word then the word problem for Inv is decidable provided the group Gp has a decidable prefix membership problem. The prefix membership problem for one-relator groups has received attention in the literature and has been shown to have a positive solution in a number of special cases. The general case remains an open problem. In joint work with Igor Dolinka we have proved new results which show that the prefix membership problem is decidable for certain classes of one-relator groups which are low down in the Magnus--Moldovanskii hierarchy. Our methods use a mix of inverse semigroup theory, and ideas from combinatorial group theory, specifically the theory of free products with amalgamation and HNN-extensions. As predicted in the original case for support, the Magnus breakdown procedure (in its HNN-formulation developed by McCool and Schupp) is central to this work. We prove four general theorems showing that the membership problem is decidable for particular submonoids of certain HNN-extensions, and amalgamated free products, of groups. These results can then be applied to obtain a positive answer to the word problem for certain one-relator inverse monoids of the form Inv for which it was previously unknown. The word problem for one-relator special inverse monoids is one of the central questions of this research project, and these results represent a significant contribution to this problem. In particular our results can be applied to show that the above-mentioned O'Hare monoid example of Margolis and Meakin does have a decidable word problem. These results appear in the publication https://doi.org/10.1090/tran/8338.

The 2018 WOW conference at UEA, funded by this project, was used to bring some of these questions and connections to the attention of researchers working in geometric group theory. (See below more on the WOW conference and the benefits that have come from it.) In this way, this research is has brought researchers in combinatorial semigroup theory together with researchers in combinatorial and geometric group theory, achieving one of the objectives of the research proposal.

(f) Crystal monoids (joint work with A. Cain and A. Malheiro, both of the New University of Lisbon). This work arose from earlier joint work of ours on an important example called the Plactic monoid. This monoid can be defined by a presentation where the relations are determined by isomorphisms between certain coloured graphs, with vertex set the words over the generators. These coloured graphs are called crystals. They arise originally in work of Kashiwara on quantum group algebras associated with classical Lie algebras. Crystal monoids can be defined in general combinatorial terms. They give a large class of monoids for which the word problem is decidable. Some one-relator monoids arise as examples of crystal monoids (e.g. the bicyclic monoid), and so this theory gives an alternative way of solving the word problem in those cases. In all classical cases we have shown that these monoids are all biautomatic. Hence, not only do they have decidable word problem, but they have word problem which is decidable in quadratic time. These results appear in the publication doi: 10.1016/j.jcta.2018.11.010.

(g) Cogrowth, amenability and spectral radius of random walks on monoids (joint work with M. Kambites, Manchester). We introduce and investigate several notions of cogrowth for monoids, and explore connections with amenability, spectral radius, and random walks on Cayley graphs of finitely generated monoids. This is part of the continued development of our theory of directed geometry of monoids. These results appear in the publication doi: 10.1093/imrn/rny125.

(h) Universal locally finite maximally homogeneous semigroups and inverse semigroups (joint work with Dolinka, Novi Sad). As part of my work with Dolinka, in particular on inverse monoids which are a class of central importance in the current proposal, we did some work looking at the maximal amount of symmetry that such semigroups can have. This led us to define analogues of Hall's universal locally finite homogeneous group, for monoids and inverse monoids, and prove results about the highly symmetrical objects which are encoded in their algebraic and combinatorial structure. These results appear in the publication doi: 10.1515/forum-2017-0074.

(i) The research project has also partially supported several other pieces of research, including: (1) Results on the word problem for free idempotent generated semigroups joint with Dolinka and Ruskuc (2) Results joint with my former PhD student Coleman, and Evans (Imperial), studying symmetry properties based on monoids acting on combinatorial structures by bijective endomorphisms (3) Joint work with East on the structure of certain diagram monoids. These results appear in the publications doi: 10.1016/j.ejc.2019.02.005, 10.1112/plms.12011, 10.1016/j.jcta.2016.09.001.

(j) Winter one-relator workshop 2018 conference. Another important objective of the research project was to bring together researchers from geometric group theory together with researchers in combinatorial semigroup theory to discuss the problems related to the project. We did this this year in a very successful conference WOW 2018 held at UEA in January 2018. The conference webpage may be found here: https://archive.uea.ac.uk/~fga12juu/WOW.html. Ideas discussed at this conference have already led to further progress on some of the key questions being investigated, in particular in relation to the problem of computing the groups of units of special one-relator monoids, and the word problem for certain classes of one-relator inverse monoids. The research connections made though this conference led to the PI being invited to the ICMS research group: "Solving equations in one-relator groups/semigroups (solvability issues, algorithms, one-variable equations etc) and more specifically Baumslag-Solitar groups" organised by Laura Ciobanu, at the ICMS in Edinburgh in September 2018. That meeting led to a collaboration between the PI and Dr Albert Garreta (University of the Basque Country UPV/EHU) on the Diophantine Problem for one-relator monoids (see https://arxiv.org/abs/1908.00098).
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, together with his future research collaborators, PhD and research students.
Sectors Digital/Communication/Information Technologies (including Software)
 
Description This project has led to the publication of 13 research articles in a range of leading mathematics and computer science journals. These papers have already received over 138 citations showing the significant impact that this research is already having. One of the key discoveries of this research project, which answered a longstanding algorithmic question in algebra, is included in the recent book "Landscape of 21st Century Mathematics Selected Advances, 2001-2020" by Bogdan Grechuk. This is a popular maths book which, from the author's description "...presents an array of breathtaking recent advances in mathematics. It is written for everyone with a background in mathematics, from inquisitive university students to mathematicians curious about recent achievements in areas beyond their own." This is an example of the way results from this project are being used to educate and inspire, and to popularise mathematics. In addition to this, the topic of the research project formed the basis of a mini-course that the Principal Investigator (PI) of the project gave at the School of Algebra, XXIV Brazilian Algebra Meeting, Diamantina, in August 2016. This mini-course was attended by many masters and PhD students. Ideas from the research project also formed the basis of a course that he gave at the "LMS Undergraduate Summer School 2017" at the University of Manchester. The aim of the LMS Summer School is to introduce modern mathematics to the best UK undergraduates who are not currently in their final year of study. This gave him the opportunity to use ideas from the research project to help inspire and educate the next generation of mathematicians in the UK. Following the success of the above course, the PI was invited again, and he gave a course on the same topic at the "LMS Undergraduate Summer School 2018" at the University of Glasgow.
First Year Of Impact 2016
Sector Education
Impact Types Societal