Linear time algorithm for the conjugacy problem in the first Grigorchuk group

Abstract

We prove that the conjugacy problem in the first Grigorchuck group $\Gamma$ can be solved in linear time. Furthermore, the problem to decide if a list of elements $w_1,\dots ,w_k\in \Gamma$ contains a pair of conjugate elements can be solved in linear time. We also show that a conjugator for a pair of conjugate element $u,v\in \Gamma$ can be found in polynomial time.