Solving word problems via generalisations of small cancellation

点击翻译按钮获取中文摘要

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.