Constructing Directed Cayley Graphs of Small Diameter: A Potent Solovay-Kitaev Procedure

Let $\mathrm{\Gamma }$ be a group and $({\mathrm{\Gamma }}_n{)}_{n=1}^{\mathrm{\infty }}$ be a descending sequence of finite-index normal subgroups. We establish explicit upper bounds on the diameters of the directed Cayley graphs of the $\mathrm{\Gamma }\mathrm{/}{\mathrm{\Gamma }}_n$ , under some natural hypotheses on the behaviour of power and commutator words in $\mathrm{\Gamma }$. The bounds we obtain do not depend on a choice of generating set. Moreover under reasonable conditions our method provides a fast algorithm for constructing directed Cayley graphs of diameter satisfying our bounds. The proof is closely analogous to the the Solovay-Kitaev procedure, which only uses commutator words, but also only constructs small-diameter undirected Cayley graphs. As an application we give directed diameter bounds on finite quotients of two very different groups: $S{L}_2({\mathbb{F}}_q[[t]])$ (for $q$ even) and a group of automorphisms of the ternary rooted tree introduced by Fabrykowski and Gupta.