GroupsComputability · Algorithms in algebra and topology

Algorithms in algebra and topology

"Group theory is the study of symmetry in mathematical objects, such as rotations of geometric shapes. Groups help us understand the underlying structure of mathematical objects by revealing their symmetries. To understand groups we need an efficient way to describe them. Some groups admit a finite presentation, which is a finite set of building blocks, along with a finite set of rules on when we can substitute one collection of blocks for another. These descriptions are convenient. However, results in algebra and logic show that such descriptions are not always suitable to work with, as certain problems (e.g., the word problem, of deciding if two distinct collections of blocks represent the same group element) are incomputable; no computer can be built to always answer this. We can embed incomputable problems from groups into geometry, to show that the homeomorphism problem, of recognising if two geometric shapes are equivalent under smooth deformation, is incomputable in all dimensions above three. Thus we can't computationally classify geometric shapes in higher dimensions; we can't identify the unique distinguishing features of each shape. Groups, and higher-dimensional geometric shapes, appear in many other areas of study. One such application is in cryptography, where we use groups to develop the underlying framework of the cryptosystems used to keep internet transactions safe and secure; in this context, being unable to compute various questions in group theory makes them useful for cryptographic applications. Another application is in physics, where we use both groups and our knowledge of geometry to understand the `shape' of the universe; in this context, the ability to compute various properties of the geometric objects that we are working with is of great help in understanding them. The purpose of this project was to investigate other algorithmic questions in group theory, beyond the word problem, to determine if they are computable. We aimed to then apply these results to particular classes of higher-dimensional geometric objects, identifying whether certain problems relating to them are computable or not. One of the key tools in doing this, which was developed during the project, is the use of ""embedding theorems""; these are constructions which allow us to realise groups as sub-structures of other groups in a ""nice"" (= algorithmic) manner. Using this, it is then possible to export undecidable problems from one group to another. This project also involved the PI carrying out various teaching activities, in order to improve and refine his teaching and communication skills. This included teaching undergraduate and graduate courses, and supervising masters theses and undergraduate summer research projects."

Data: CORDIS, © European Union