Abstract
I’ll be talking about joint work with Derek Holt, which examines the compressed word and conjugacy problems, specifically for relatively hyperbolic groups. Rather than focus on the technicalities of our proof I intend to present a non-technical survey of these problems and related problems, and of the solutions to them that preceded our work, and on which our work is based.
For a group G𝐺 with finite generating set X𝑋, a solution to the word problem provides an algorithm that given a word w𝑤 (finite string of elements from 𝑋∪𝑋−1) can determine whether or not w𝑤 represents the identity element of G𝐺, while a solution to the conjugacy problem can determine whether or not two words u,v𝑢,𝑣 represent elements of G𝐺 that are conjugate within the group (i.e. 𝑔𝑢=𝐺𝑣𝑔 for some 𝑔∈𝐺.
However, in some situations an element of G𝐺 is not most naturally represented as a string over X𝑋 but rather by a sequence of rules from a grammar through which it is produced, e.g. the string 𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑏𝑏𝑏𝑏𝑐𝑐(=𝑎8𝑏4𝑐2) can be constructed as a concatenation of three powers, each produced by repeated squaring of a generator (a𝑎, b𝑏 or c𝑐); such a representation is called a compressed word. Solution to the compressed word and conjugacy problems determine whether a compressed word represents the identity element, or whether two compressed words represent conjugate elements.
Compressed word descriptions of group elements can arise very naturally; we observe that Schleimer’s 2008 result that the word problem for Aut(Fm)𝐴𝑢𝑡(𝐹𝑚) can be solved in polynomial time is a consequence of Lohrey’s 2006 result that the compressed word problem of Fm𝐹𝑚 has a polynomial time solution.
We shall see how solutions for the compressed word problems for first free, then hyperbolic, and then relatively hyperbolic groups all make use of the underlying geometry of the Cayley graph(s) over the groups, over one or more generating sets.