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

无限群、幺半群和逆半群的算法、拓扑和几何方面

• 批准号: EP/V032003/1
• 负责人: Robert Gray
• 金额: $ 152.9万
• 依托单位: University of East Anglia
• 依托单位国家: 英国
• 项目类别: Fellowship
• 财政年份: 2022
• 资助国家: 英国
• 起止时间: 2022 至 无数据
• 项目状态: 未结题
• 来源: https://gtr.ukri.org/projects?ref=EP%2FV032003%2F1
• 关键词: Algorithmic; topological; geometric; aspects; infinite

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.

二十世纪数学最令人惊奇的结果之一是，阿隆佐教堂（Alonzo Church）和艾伦·图宁（Alan Turing）的发现是，数学上存在问题，这是无法解决的，从某种意义上说，没有算法可以解决它们。这意味着，无论您用来帮助您的计算机多么强大，都有一些数学问题仍然无法解决。如果无法解决的问题是以“是”或“否”问题的形式，那么我们将其称为一个不确定的问题。另一方面，如果可以解决，那么我们说这是一个可决定的问题。代数自然出现了许多决策问题。重要示例包括“问题”一词，要求我们确定两个不同的代数表达式是否彼此平等，并且会员问题要求我们决定是否可以用另一个元素来表示代数结构中的一个元素。在研究无限代数结构时，能够解决此类问题很重要。该项目的主要主题是研究三类的代数对象，称为群体，单体和反向半群。这三个类别自然出现在数学中的对称性和部分对称性的研究中。定义无限群，单体和逆半群的重要工具是由发电机和关系中的演示理论给出的。这个想法是，小组或单体的元素由字母字符串表示，称为单词。我们还获得了一组定义关系，这是一个规则，告诉我们某些单词彼此相等。如果一个单词可以通过应用关系转换为另一个单词。例如，如果我们使用字母x和y，并且有一个定义关系xy = yx，则单词xyx和yxx是相等的，因为xyx =（xy）x =（yx）x = yxx。另一方面，xy和yy单词不等。确定两个单词是否彼此相等的问题是上面提到的单词问题。当我们使用演示文稿定义单体或组时，通过增加关系数量，我们可以增加我们定义的单体或组的复杂性。如果没有关系，这些被称为自由的单体和群体，并且由于它们简单的结构，在这些情况下，可以认为几个自然决策问题，例如问题问题，可以看见是可以决定的。相比之下，众所周知，有一个有限的生成器和关系定义的单素，组和反向半群，但有不确定的单词问题。这种情况与代数出现的许多其他决策问题相似。自然要问，从某种意义上说，几乎是自由的小组或单体是否具有良好的算法属性。这类对组的重要积极结果是Magnus的定理，该定理表明，由单个定义关系定义的群体都有可决定的单词问题。另一方面，最近发现有一个由单个定义的关系定义的，这些关系具有不可决定的单词问题。但是，如果单词问题对于单余的单体可以决定，这仍然是一个重要的长期开放问题。像这样的问题有许多有趣的开放问题，这些问题提出了有关有限呈现的群体，单体和反向半群的基本问题的基本问题。在这个项目中，我们将探讨此类相互关联的一系列问题。这将通过开发几何和拓扑方法来完成，这些方法使用这些代数对象的“形状”或与空间相互作用的方式来阐明其算法属性。

项目成果

Prefix monoids of groups and right units of special inverse monoids

群的前缀幺半群和特殊逆幺半群的右单位

• DOI: 10.1017/fms.2023.99
• 发表时间: 2023
• 期刊: Forum of Mathematics, Sigma
• 作者: Dolinka I

Group $\mathcal{H}$-classes of finitely presented special inverse monoids

有限呈现的特殊逆幺半群的$mathcal{H}$类群

• DOI: 10.48550/arxiv.2212.04204
• 发表时间: 2022
• 作者: Gray R

Membership problems for positive one-relator groups and one-relation monoids

正单关系群和单关系幺半群的隶属问题

• DOI: 10.48550/arxiv.2305.15672
• 发表时间: 2023
• 作者: Foniqi I

ON GROUPS OF UNITS OF SPECIAL AND ONE-RELATOR INVERSE MONOIDS

关于特殊单位和一关系逆幺半群的群

• DOI: 10.1017/s1474748023000439
• 发表时间: 2023
• 期刊: Journal of the Institute of Mathematics of Jussieu
• 影响因子: 0.9
• 作者: Gray R

Subgroups of even Artin groups of FC-type

FC型偶Artin群的子群

• DOI: 10.48550/arxiv.2305.17292
• 发表时间: 2023
• 作者: Antolín Y