Equations in groups, formal languages and complexity

Solving equations has always been a central question for mathematics. Whether searching for the roots of a polynomial or solving a differential equation, finding or approximating the solutions is an essential part of science, from pure to applied, and understanding the properties of the solutions opens up worlds of algebraic, dynamical, geometric or logical structure.

This project centres on finding and understanding the solutions of equations in infinite nonabelian discrete groups, a topic at the wild frontier between solvable and unsolvable, with far-reaching applications to algebra, logic, geometry and theoretical computer science. Understanding solutions is crucial in order to expand algebraic geometry to a non-commutative setting, to master the first order theory of a structure, to determine isomorphism between two hyperbolic groups, to advance unification theory, and to answer questions about combinatorics on words. Despite the groundbreaking work in the this area by Makanin, Razborov, Sela, Kharlampovich, Miasnikov and others, very few examples can be tackled, no implementation exists, and the area remains notoriously technical.

On the strength of my expertise and long term preparatory work towards the objectives of this project, I will push forward both the theoretical and computational side of this area by linking nondeterministic algorithms to group theoretic and geometric approaches. I aim to map the essential features of the landscape more clearly and produce not only deep results, but also accessible literature and new algorithms.

1. An important research direction will be the formal language characterisation of solutions of equations and inequations, as well as definable sets, in the most important classes of infinite groups, such as free, hyperbolic or certain nilpotent and Artin groups. Our work will give a new, combinatorial description of sets that have a complex algebraic structure.

2. Another goal of the project is to develop algorithms that solve equations in the Heisenberg group and dihedral Artin groups. At the moment no such algorithms exist, and these problems will require groundbreaking, novel approaches.

3. The most ambitious goal of the project is to exploit the information lying at the core of the new, nondeterministic algorithm due to Diekert, Elder and myself in order to extract not just formal language characterisations, but the algebraic structure of varieties in free groups, and compare this to the information given by Makanin-Razborov diagrams.

The project's most innovative dimension is its authentic interdisciplinary nature: we will use tools from computer science and combinatorics to answer questions rooted in group theory, non-commutative algebraic geometry and logic, and vice versa, we will use algebraic and geometric results in order to improve and generalise the existing computational approaches.

Our work will bring together group theory and theoretical computer science, and deepen the connections between the two. We will advance our understanding of topics of interest to group theory, logic, combinatorics and algebraic geometry, and topics in theoretical computer science such as computability, complexity of algorithms, language theory and unification theory. Finding answers to the questions in this proposal will represent an important contribution to algorithmic group theory and computability theory, and will lead to a much more active flow of ideas between the computer science and mathematics community. This grant will enable me to have a small team in combinatorial and algorithmic group theory at Heriot-Watt, and both my university and the group theory and theoretical computer science communities at nearby institutions will benefit from the activity generated by the project. Group and semigroup theory, as well as formal language theory and combinatorics are well represented in St. Andrews, Glasgow, Aberdeen and Newcastle.

With respect to EPSRC key priority areas, the impact will be as follows.

KNOWLEDGE and DISSEMINATION.

* We will maintain a project website and link it to the main portals in geometric and combinatorial group theory.
* We will present the work at major international conferences in mathematics and computer science, such as GAGTA, ICALP, LATA, and publish in high impact journals in both mathematics and computer science.
* The RA and myself will organise a school for young researchers in the final year of the project at ICMS in Edinburgh, with funding from the ICMS, LMS and EMS. There will be lectures from high-profile invited speakers, as well as the PI, RA and the young participants.

PEOPLE.

* We will train the RA in this area at the intersection of mathematics and computer science.
* We will involve at least 1 PhD student in aspects of the project.
* We will organize the concluding school in order to influence and train the next generation of research leaders.
* We will apply for a Marie Curie Research and Innovation Staff Exchange (RISE) grant in the Horizon 2020 framework, together with colleagues from Spain, Switzerland, the US and Australia. If successful, this grant will allow for a continuous flow of researchers to and from Heriot-Watt to exchange knowledge.

OUTREACH ACTIVITIES and STEM INVOLVEMENT.

* I will give Maths Masterclasses to upper primary and secondary school students from the Edinburgh area on topics related to the project.
* I will organise an LMS Women and Girls in Mathematics event in 2019 in Edinburgh where at least one of the speaker's research will bridge mathematics and computer science. I will continue to mentor young women who want to pursue and succeed in a career in science.