EPSRC Reference: 
EP/I03582X/1 
Title: 
Solving word problems via generalisations of small cancellation 
Principal Investigator: 
RoneyDougal, Dr CM 
Other Investigators: 

Researcher CoInvestigators: 

Project Partners: 

Department: 
Mathematics and Statistics 
Organisation: 
University of St Andrews 
Scheme: 
Standard Research 
Starts: 
01 October 2011 
Ends: 
30 September 2014 
Value (£): 
444,508

EPSRC Research Topic Classifications: 
Algebra & Geometry 
Logic & Combinatorics 

EPSRC Industrial Sector Classifications: 
No relevance to Underpinning Sectors 


Related Grants: 

Panel History: 
Panel Date  Panel Name  Outcome 
24 May 2011

Mathematics Prioritisation Panel Meeting May 2011

Announced


Summary on Grant Application Form 
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 wideranging applications. For example, modern errorcorrecting 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 fastrunning, 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 sidebyside 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 finitelypresented 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 grouptheoretic 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.

Key Findings 
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk

Potential use in nonacademic contexts 
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk

Impacts 
Description 
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk 
Summary 

Date Materialised 


Sectors submitted by the Researcher 
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk

Project URL: 

Further Information: 

Organisation Website: 
http://www.stand.ac.uk 