Repository logo
 

Navigating directed Cayley graphs of small diameter: A potent Solovay–Kitaev procedure

Accepted version
Peer-reviewed

Type

Article

Change log

Authors

Abstract

Let [Formula: see text] be a group and [Formula: see text] be a descending sequence of finite-index normal subgroups. We establish explicit upper bounds on the diameters of the directed Cayley graphs of the [Formula: see text], under some natural hypotheses on the behavior of power and commutator words in [Formula: see text]. The bounds we obtain do not depend on a choice of generating set. Moreover, under reasonable conditions our method provides a fast algorithm for navigating directed Cayley graphs. The proof is closely analogous to the Solovay–Kitaev procedure, which only uses commutator words, but also only constructs small-diameter undirected Cayley graphs. We apply our procedure to give new directed diameter bounds on finite quotients of a large class of regular branch groups, and of [Formula: see text] (for [Formula: see text] even).

Description

Keywords

4613 Theory Of Computation, 46 Information and Computing Sciences, 4904 Pure Mathematics, 49 Mathematical Sciences

Journal Title

International Journal of Algebra and Computation

Conference Name

Journal ISSN

0218-1967
1793-6500

Volume Title

29

Publisher

World Scientific Pub Co Pte Lt

Rights

All rights reserved