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.