Robert Gray (University of East Anglia) – Solving equations in one-relator groups

Mathematicians have long been interested in the question of which problems can be automated, that is, which mathematical tasks can be solved using a computer. Famously, in 1900 Hilbert put forward the challenge of finding an algorithm which for any given Diophantine equation (a polynomial equation with integer coefficients and a finite number of unknowns) can decide whether or not the equation has a solution where the unknowns take integer values. In 1970 Matiyasevich showed that no such algorithm exists, that is, the problem is undecidable. One can consider equations for other algebraic structures, and in group theory equations capture many natural and well-studied notions e.g. the question of whether two elements g and h of a group G are conjugate is equivalent to asking whether the equation Xg = hX has a solution. The Diophantine problem for a group G asks whether there is an algorithm that takes any finite system of equations over G as input and decides whether or not it has a solution. The first major breakthrough in this area was achieved by Makanin in the 1970s who proved that free groups have decidable Diophantine problem. Since then the Diophantine problem has been studied for various other classes of groups and a range of decidability and undecidability results have been proved. In particular, the Diophantine problem has been investigated for one-relator groups, that is, groups defined by presentations <A|w=1> with a finite generating set A and just a single defining relation w=1. The study of one-relator groups has long been a central topic in combinatorial and geometric group theory. Magnus proved in the 1930s that all one-relator groups have decidable word problem. However, many algorithmic problems remain open for this class. For example, it is still not know whether all one-relator groups have decidable conjugacy problem. In this talk I will speak about recent joint work with Alex Levine in which we studied the Diophantine problem for one-relator groups. In particular, I will explain some of the ideas behind our recent result which shows that there exist one-relator groups with undecidable Diophantine problem.