Solving word problems via generalisations of small cancellation

这个项目是关于群论的。群论是一门研究对称性的学科——任何物体形成一个群的对称集合——它有着广泛的应用。例如，现代纠错码——例如用于将数据存储到cd上的纠错码——使用了群论，而将群论应用于数据加密是一个非常活跃的研究课题。描述一个团队的一种方式是通过演讲。组中的元素由称为单词的字母串表示。然而，有些单词对在组中是相等的：这些相等是由在组中与空单词相等的单词列表确定的，这些单词列表称为关联词。这是群在许多情况下自然出现的方式：例如在拓扑学中，当研究流形的基本群时。这也是在计算机上处理无限群的少数几种方法之一，因为计算机可以通过有限表示来了解无限多的群元素。20世纪数学中最著名的结果之一证明，一般来说，不存在一种算法来决定两个词在组中何时相等。这个问题- -词语问题- -是第一个被证明一般来说是不可决定的具体决策问题之一；并证明了不完备性这类概念并非纯粹哲学意义上的。然而，这并不意味着这个问题不能在特殊情况下解决，它的解决对于发展对无限群的广泛类别的具体理解是必不可少的。该项目旨在开发一种新的思考这些群体的方式，从而为其中的许多群体提供快速运行、实用的算法。我们将使用一种称为van Kampen图的图片来处理这些组，它由点（顶点），它们之间的线（边）和由线包围的区域组成。每条边都标有一个单词，这样，读取其中一个区域的所有路径，就会得到该组的一个亲戚。将区域拼接在一起可以被认为是一种拼图游戏，只有当两个区域在其中一个边缘上彼此一致时，它们才能并排放置。我们将开发实用的算法，将一组相关器作为输入，并证明所有可以由它们组成的图只有相当少的区域，相对于单词的外部边界的长度。由此可以得出，如果一个单词在组中等于空单词，那么这可以在相应的短步骤中显示出来。为了开发这些算法，需要进行大量的理论探索：例如，我们需要确定我们将要研究的群体类别与自动群体类别之间的关系，其中一种非常不同的方法已被证明是成功的。我们也将我们的工作扩展到更广泛的代数结构类，而不是有限表示群，包括monoids和矩阵群。这项工作将有几个应用和好处，其中一些应用在群论内部，另一些应用在更远的地方。我们将把我们的软件作为计算机代数系统GAP的一部分提供，这是免费提供的，因此即使是不知道我们技术的用户也会注意到在广泛的相关算法中改进了性能。能够在计算机上输入一个组并快速获得有关其结构的答案，使研究人员能够进行实验并形成猜想。此外，将这些方法集成到更大的软件套件中意味着其他领域的研究人员可以使用依赖于群论技术的方法，而无需了解任何群论，从而促进整个学科范围的快速进步，从余集枚举等应用到拓扑等纯数学领域，再到化学和物理等更遥远的学科。

This project is concerned with group theory. Group theory is the study of symmetry - the set of symmetries of any object form a group - and has wide-ranging applications. For example, modern error-correcting codes - such as are used for storing data onto CDs - use group theory, and the application of group theory to the encryption of data is an extremely active research topic. One way to describe a group is via a presentation. Elements of the group are represented by strings of letters, called words. However, some of the pairs of words are equal in the group: these equalities are determined by a list of words that are equal in the group to the empty word, called relators. This is the way that groups naturally arise in many contexts: for example in topology, when studying fundamental groups of manifolds. It is also one of the few ways of working with an infinite group on a computer, as the computer can be told about the infinitely many group elements by means of a finite presentation. One of the most famous results in twentieth century mathematics proves that, in general, there cannot exist an algorithm to decide when two words are equal in the group. This problem - the word problem - was one of the first concrete decision problems proven to be undecidable in general; and showed that notions such as incompleteness are not of purely philosophical interest. However, that does not mean that the word problem cannot be solved in special cases, and its solution is essential to the development of a concrete understanding of a wide class of infinite groups. This project seeks to develop a new way of thinking about these groups, leading to fast-running, practical algorithms for many of them.We will work with these groups by using a type of picture called a van Kampen diagram, which consists of dots (vertices), lines between them (edges), and regions enclosed by the lines. Each edge is labelled with a word, such that reading all of the way around one of the regions gives one of the relators of the group. Fitting regions together can be thought of as a kind of jigsaw puzzle, where two regions can be put side-by-side only if they agree with each other along one of their edges. We will develop practical algorithms which take as input a set of relators, and prove that all diagrams that can be made from them have only a fairly small number of regions, relative to the length of the word around the outer boundary. From this it follows that if a word is equal in the group to the empty word, then this can be shown in a correspondingly short number of steps. To develop these algorithms, a considerable amount of theoretical exploration will be required: for example, we need to determine the relationship between the class of groups that we will study and the class of automatic groups, for which a very different approach has been shown to be successful. We will also extend our work to a wider class of algebraic structures than finitely-presented groups, including monoids and matrix groups. This work will have several applications and benefits, some of them inside group theory and others considerably further afield. We will make our software available as part of the computer algebra system GAP, which is freely available, so that even users who are unaware of our techniques will notice improved performance in a wide range of related algorithms. Being able to input a group on a computer and rapidly get answers about its structure enables researchers to experiment and form conjectures. Furthermore, integrating such methods into larger suites of software means that researchers in other areas can use methods which rely on group-theoretic techniques without needing to know any group theory, facilitating rapid progress in a whole range of disciplines, from applications such as coset enumeration, to pure mathematical areas such as topology, to more distant subjects such as chemistry and physics.