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.

This project is in pure mathematics, and algorithmic support for pure mathematics. As is standard in pure mathematics, its nonacademic impact is likely to come indirectly, through the impact of our research on other research, which turns out to have practical applications. This kind of long-term impact is well established: number theory has had a critical impact on modern cryptography, logic is crucial to the design of computer languages, and group theory is central to the design of error-correcting codes for data transmission.

We foresee two main kinds of academic impact: increased understanding and new questions arising from our theoretical results; and the availability of our software for use by others. On the theoretical side, a uniform understanding and generalisation of small cancellation properties will be of great interest to geometrical group theorists and should produce new connections between their work and that of semigroup theorists and others. A deeper understanding of the van Kampen diagrams of non-positively curved groups will spark new lines of inquiry in geometric group theory.

On the practical side, our programs might help anyone seeking to investigate finite presentations, and hence our plans to publish free software are important. We will seek out opportunities to present our work to other communities: for example, a trip to NUI Galway to discuss topological applications is planned. Incorporating our software into GAP removes hurdles to uptake of our methods, and increases the effectiveness of GAP, even for users who are unaware of our techniques. Releasing it ``freely'' more than pays for itself in the quality and quantity of feedback obtained from users. We will retain ownership and the option to license it commercially.

Experience tells us that there may be unforeseeable future impacts on other areas. The most important way to ensure impact is to record our work effectively in the refereed scientific literature. Thus, as ever, we will publish papers, speak at conferences, and release technical reports to publicise our achievements.

Another impact will be the training of the RA, who will gain expertise in geometric and computational group theory, algorithm design and implementation, and the dissemination of research. St Andrews has an excellent track record of developing RAs' careers, and we would expect whoever is hired to become a leading junior researcher.

We do not expect this project to lead directly to commercial development, however, research can be surprising. Should commercial exploitation of our work become appropriate, we would work with the University's Knowledge Transfer Office, and draw on the experience of our commercial contacts.

This project is ideally suited for outreach work, and the PI will build on her extensive public engagement experience. Raising public awareness of science influences career choices and enriches the cultural environment. For example, reading Plus magazine (where the PI has several publications) is often mentioned on UCAS forms as the first reason why people became interested in non-school mathematics, eventually leading to university study, thus increasing the supply of mathematics graduates.

We work within CIRCA, the Centre for Interdisciplinary Research in Computational Algebra. It is a key aim of CIRCA to see research achieve maximum impact in all possible ways. We bring interesting problems arising from one area to the attention of researchers in other areas. Thus, we have spoken and published about artificial intelligence at mathematics conferences, and about group theory at parallel computing conferences: our seminars range from advanced algebra to medical image processing. CIRCA preserves a ``corporate memory": work done can be applied to new problems, and opportunities to follow up successful projects are pursued. We train people in an unusually broad academic background, who contribute to the economy in a wide range of ways.