arXiv:1703.05852v1 [] 17 Mar 2017

Uniform Diameter Bounds in Branch Groups
Henry Bradford
March 20, 2017
Abstract
Let G be either the Grigorchuk 2-group or one of the Gupta-Sidki pgroups. We give new upper bounds for the diameters of the quotients of
G by its level stabilisers, as well as other natural sequences of finite-index
normal subgroups. Our bounds are independent of the generating set,
and are polylogarithmic functions of the group order, with explicit degree.
Our proofs utilize a version of the profinite Solovay-Kitaev procedure, the
branch structure of G, and in certain cases, existing computations of the
lower central series of G.

1

Introduction

Let G be a finite group, and S ⊆ G be a generating set. The diameter of G
with respect to S is defined to be:
diam(G, S) = min{n ∈ N : BS (n) = G},
where BS (n) is the (closed) ball of radius n about the identity in the word
metric defined by S on G. The diameter of G, denoted diam(G), is then the
maximal value of diam(G, S) as S ranges over all generating subsets of G. In
this paper we give upper bounds for the diameters of natural families of finite
quotients of certain branch groups.

1.1

Statement of Results

Theorem 1.1. Let G be the Grigorchuk 2-group. Then:

diam(G/ StabG (n)) = O exp(log(35)n)


= O log|G : StabG (n)|log(35)/ log(2) .

We shall define the sequence of level stabilisers StabG (n) for a group G
acting on a rooted tree in subsection 2.2. Our proof makes extensive use of the
description of the lower central series (γn (G))n of G given in [5], building on
[26] (see also [3]). The results of these papers facilitate an explicit description
of the restriction to γn (G) of the action of G on the binary rooted tree. Indeed,
Theorem 1.1 is proved as a consequence of the following.
1

Theorem 1.2.
diam(G/γn (G)) = O nlog(35)/ log(2)




= O log|G : γn (G)|log(35)/ log(2) .

Recall that log(35)/ log(2) ≈ 5.129. We now turn to our results on the
Gupta-Sidki p-groups.
Theorem 1.3. Let p be an odd prime. Let Γ(p) be the Gupta-Sidki p-group.
Then:

diam(Γ(p) / StabΓ(p) (n)) = Op exp(log(Cp )n)

= Op log|Γ(p) : StabΓ(p) (n)|log(Cp )/ log(p)

where Cp = 3 · 4p − 2p (p + 8) + 7.

Theorem 1.3 is a consequence of our next result. Let K be the derived
subgroup of Γ(p) .
Theorem 1.4. Let Cp is as in Theorem 1.3.

n
diam(Γ(p) /K (×p ) ) = Op exp(log(Cp )n)
n


n
= Op log|Γ(p) : K (×p ) |log(Cp )/ log(p) .

Here K (×p ) denotes the Cartesian product of pn copies of K. We define
n
the natural embeddings of the K (×p ) as finite-index normal subgroups of Γ(p)
n
in subsection 2.2. For now suffice to say that there are inclusions K (×p ) ≤
StabΓ(p) (n + 1) and that given certain well-known bounds on the orders of the
relevant groups, Theorem 1.3 quickly follows from these inclusions and Theorem
1.4. In the case p = 3, we can exploit the description of the lower central series
of Γ(3) given by Bartholdi [3] to also deduce the following.
Theorem 1.5.
diam(Γ(3) /γn (Γ(3) )) = O nlog(111)/ log(1+

√

2)




= O log|Γ(3) : γn (Γ(3) )|log(111)/ log(3) .

For the Gupta-Sidki 3-group therefore, our bounds for the diameter are polylogarithmic in the order of the group, with degree log(C3 )/ log(3)
= log(111)/ log(3) ≈ 4.287. As p grows, the degree of the polylogarithm grows,
proportional to p/ log(p). The implied constants in Theorems 1.1-1.5 may all
be explicitly computed from our proofs.
G/ StabG (n) and Γ(p) / StabΓ(p) (n) are transitive imprimitive permutation
groups on, respectively, 2n and pn points. As such, Theorems 1.1 and 1.3 provide
new examples of transitive subgroups of Sym(N ) (N a power of a fixed prime)
whose diameters are polynomially bounded in N . In the next subsection we
will further contextualise Theorems 1.1 and 1.3 within the existing literature on
diameters of permutation groups. G and Γ(p) are particularly famous members
of the class of branch groups, and have been extensively studied since their
introduction, respectively in [16] and [19]. They will be defined precisely in
subsection 2.2.

1.2

Background and Structure of the Paper

G is one of the most exotic objects in geometric group theory: it is a finitely
generated infinite 2-group, so provides a counterexample to the General Burnside Problem; it is a group of intermediate growth, and indeed was the first
example of such a group to be constructed; it is amenable but not elementary
amenable; it is a residually finite just-infinite group; it admits no faithful representation over any field, and every finite 2-group embeds into it as a subgroup
[10]. Similarly, Γ(p) is a finitely generated infinite p-group; contains a copy of
every finite p-group, and shares many of the other aforementioned properties
with G, though its growth is the subject of ongoing discussion.
An understanding of the broader class of branch groups, to which G and Γ(p)
belong, has now become a crucial part of the toolkit of the modern geometric or
profinite group theorist. In one sense this is no surprise, bearing in mind Wilson’s classification of just-infinite groups [29], in which branch groups comprise
an important case (although historically, this may only be noted in hindsight,
since the class of branch groups was not formally defined until some time after
Wilson’s theorem [18]). What was perhaps less expected was the extraordinarily
relevance branch groups would prove to have, to subjects as diverse as (but by
no means limited to) decision problems, finite automata, spectral graph theory,
fractal spaces, and exotic phenomena in the domains of word growth, subgroup
growth and other asymptotic invariants of infinite groups [6].
Seperate from, but roughly concurrent with these developments, interest
was growing in generation problems in various families of groups, including the
search for good diameter bounds. From the start, particular attention was paid
to upper bounds for permutation groups, owing to connections with problems in
theoretical computer science. These included membership testing protocols in
computational group theory and complexity analysis of deciding solvability of
various combinatorial puzzles [13, 23], the most famous of which is of course the
Rubick’s cube. More recently intense interest in diameters of finite groups has
been renewed, motivated by connections with such diverse topics as expander
graphs, approximate groups, the Banach-Ruziewicz problem, Apollonian circle
packings, sum-product phenomena in fields and affine sieves. The modern study
of diameters of groups is therefore an extremely rich and diverse subject, and one
which we cannot hope to fully capture here; we instead refer the interested reader
to [20, 28] and references therein for an overview of the recent developments.
Among the key tools to have featured in proofs of good upper bounds for
the diameters of finite groups is the Solovay-Kitaev procedure. This is a method
which was originally used in the context of compact complex Lie groups (where
it had applications to problems in quantum computer science) but which translated readily to the setting of abstract or profinite groups. Given a group Γ and a
descending sequence (Γi )i of finite-index normal subgroups, the Solovay-Kitaev
procedure proves, under suitable additional assumptions, an upper bound on
the diameters of the finite quotient groups Γ/Γi by induction on the sequence
(Γi )i . A crucial ingredient facilitating the induction step is that any element
of a later term in the sequence should be expressible as (or at least sufficiently

closely approximable by) the product of a small number of commutators of elements lying in earlier terms. Exactly what this means in practice will depend
on the specific group Γ and sequence of subgroups with which we are working.
In the above setting the Solovay-Kitaev procedure was first used by Gamburd
and Shahshahani [14] to give a polylogarithmic upper bound on the diameter
of SL2 (Z/pn Z). Their work was subsequently extended, first by Dinai [12] to
groups of (Z/pn Z)-points of other Chevalley groups, then by the author [8] to
congruence quotients of other p-adic analytic groups, Fq [[t]]-analytic groups and
the Nottingham groups of finite fields.
Producing the commutator expressions required to facilitate the induction
step in the Solovay-Kitaev procedure requires fairly explicit computations of
commutators in the subgroups Γi . As such, it is very useful in practice for
the sequence (Γi )i to be highly “recurrent” in some sense, so that calculations
carried out at one level may be translated to others. In many of the examples
considered in [8], for instance, the group Γ has a naturally associated Lie algebra
over a non-archimedean field, such that the Γi may be identified with a descending sequence of balls in the Lie algebra. Under this identification, computations
of commutators at different levels are simply “rescalings” of each other.
The regular branch structure of G and Γ(p) provides a notion of “recurrence”
of a different sort. These groups each have a finite-index normal subgroup K
which naturally contains a direct product K (×p) of copies of itself, again as a
finite-index normal subgroup (for G we take p = 2). We may therefore consider
i
the descending sequence Γi = K (×p ) , and note that a commutator in Γi+1 is a
p-tuple of commutators in Γi , thereby translating commutator calculations at
the top few levels down to all other levels.
The best previous diameter bounds for quotients of branch groups make no
use of their branch structure, or indeed anything other than the fact that they
are transitive permutation groups. Babai and Seress obtained the following very
general result.
Theorem 1.6 ([1] Theorem 1.4). Let G be a transitive permutation group of
degree N . Then:

diam(G) ≤ exp(C(log(N ))3 ) diam Alt(m(G))

where C is an absolute constant, and m(G) is the maximal degree of an alternating composition factor of G.
If Γ is a regular branch group acting on the k-ary rooted tree, then
G = Γ/ StabΓ (n) has a natural transitive action on the nth level of the tree, so
Theorem 1.6 is applicable, with N = k n and m(G) ≤ k. For Γ = G or Γ(p) ,
n
Γ/ StabΓ (n) is a p-group of order Ω(pΩ(p ) ) (see Lemma 2.9 and Corollary 4.1
below), Theorem 1.6 yields:


diam(Γ/ StabΓ (n)) = O exp O(n3 log(p)3 )


= O exp Op (log log|Γ : StabΓ (n)|3 )

(here we take p = 2 for Γ = G). Theorem 1.6 makes use of some deep machinery,
including the Classification of Finite Simple Groups. Therefore our Theorems
1.1-1.5 improve upon prior results in at least three ways:
(i) They improve the diameter bound qualitatively, from a quasipolynomial
function of log|G| to a polynomial one.
(ii) They give explicit (and small) estimates for implied constants.
(iii) They have self-contained, elementary and constructive proofs, which could
in principle be implemented in reasonable time on a computer.
It is also noteworthy that Theorem 1.6 remains a key tool in the study of
other transitive permutation groups, which are consequently not known to have
diameter less than exp(C(log(N ))3 ). The best known bound in this direction is
the following result of Helfgott and Seress.
Theorem 1.7 ([21]). Let G be as in Theorem 1.6. Then:
diam(G) ≤ exp(C(log(N ))4 log log(N )).
By Theorem 1.6, Theorem 1.7 can be immediately reduced to the case G =
Alt(N ). The proof in this special case also uses Theorem 1.6 to facilitate an
important induction. It is a longstanding conjecture that Sym(N ) and Alt(N )
in reality have diameter polynomial in N (that is, polylogarithmic in their order,
like the groups studied in the present paper).
A permutation group which provides a fascinating example intermediate between Sym(N ) and the groups considered in Theorems 1.1 and 1.3, is the Sylow
p-subgroup Wn = Sylp (Sym(pn )) of Sym(pn ). Wn was studied by Kaloujnine
[22], who showed that it is isomorphic to the n-fold iterated regular wreath
product Cp ≀ Cp ≀ · · · ≀ Cp , which acts naturally on the (first n levels of the) p-ary
rooted tree. Although the inverse limit Γ = limn Wn of the Wn is a regular
←−
branch pro-p group, it appears to be resistant to the Solovay-Kitaev procedure
(for instance, Γ is not finitely generated as a topological group; by contrast,
every version of the profinite Solovay-Kitaev procedure known to the author
proves finite generation as a byproduct). It is however likely that the methods
of this paper are applicable to other residually nilpotent branch groups. This
should be a topic of further study.
The paper is structured as follows. Section 2 is devoted to preliminary
material: in subsection 2.1 we lay out the consequences of the standard commutator identities upon which the profinite Solovay-Kitaev procedure is based,
and illustrate, by means of an example, their relevance to diameter bounds. In
subsection 2.2 we recall some basic material on group actions on regular rooted
trees and the class of (regular) branch groups, define the Grigorchuk group G
and the Gupta-Sidki p-groups Γ(p) and give some basic properties. In Section 3
we prove Theorem 1.2, and deduce Theorem 1.1. These proofs will be based in
part upon prior results on the structure of the lower central series of G (taken
from [3, 5]), which we state there. In Section 4 we prove Theorem 1.4 and deduce Theorem 1.3. In Section 5 we recall some results from [3] on the structure

of the lower central series of Γ(3) and using them, deduce Theorem 1.5 from
Theorem 1.4. In Section 6 we comment on implications of our diameter bounds
for spectral gap and mixing times of random walks on Cayley graphs. Finally
in Section 7 we make some remarks on the relationship between the growth of
an infinite group and the diameters of its finite quotients.

2

Preliminaries

2.1

Commutator Relations

The proofs of Theorems 1.2 and 1.4 (from which our other results are deduced)
will be via a variant of the profinite Solovay-Kitaev Procedure developed in [8],
to which we refer the reader for further background. Given a group G and a
descending sequence of finite-index normal subgroups, the Procedure provides
an approach to proving upper bounds on the diameters of the corresponding
finite quotient groups, and relies on two key ingredients, both concerning the
behaviour of commutator words within the group. The first ingredient encapsulates the intuitive notion that, given two specified elements g, h ∈ G and two
“good approximations” g̃, h̃ ∈ G, the commutator [g̃, h̃] of the approximations is
a good approximation to the commutator [g, h] of the original elements. What
is perhaps not so intuitive is that in many situations, [g̃, h̃] approximates [g, h]
much more closely than g̃ and h̃ did g and h. This idea is made precise in the
following Lemma, which is an immediate consequence of standard commutator
identities.
Lemma 2.1. Let G1 , G2 , H1 , H2 ⊳ G, with G1 ≥ G2 , H1 ≥ H2 . For all
gi ∈ Gi , hi ∈ Hi (i = 1, 2),
[g1 g2 , h1 h2 ] ≡ [g1 , h1 ] mod [G1 , H2 ][G2 , H1 ].
Proof. We compute directly:
[g1 g2 , h1 h2 ] = [g1 , h2 ][g1 , h1 ][[g1 , h1 ], h2 ][[g1 , h1 h2 ], g2 ][g2 , h1 h2 ]
and all terms other than [g1 , h1 ] lie in [G1 , H2 ][G2 , H1 ].
A particularly useful special case of this lemma is the following.
Corollary 2.2. Let (Ki )∞
n=1 be a descending sequence of normal subgroups of
G. Suppose that, for all m, n ∈ N, [Km , Kn ] ⊆ Km+n . Let m1 , m2 , n1 , n2 ∈ N,
with m1 ≤ m2 , n1 ≤ n2 , and let gi ∈ Kmi , hi ∈ Kni (i = 1, 2). Then:
[g1 g2 , h1 h2 ] ≡ [g1 , h1 ] mod Kmin(m1 +n2 ,m2 +n1 ) .
Proof. Set Gi = Kmi and Hi = Kni in Lemma 2.1, for i = 1, 2.
We will use Corollary 2.2 in the proof of Theorem 1.2. It is a classical fact
that the lower central series satisfies the required hypothesis.
Lemma 2.3. Let G be any group. Then for all m, n ∈ N,

[γn (G), γm (G)] ⊆ γm+n (G).
Lemma 2.3 will be used extensively and without further comment in the
sequel, and in particular throughout Section 3.
What is the relevance of the preceding discussion to diameters? As we
intimated in the introduction, given a group Γ and a descending sequence (Γi )i ,
the Solovay-Kitaev procedure requires the existence of an approximation to
elements of a deeper term Γj in the sequence, by commutators [g, h] of elements
g, h lying in a higher term Γi . We may assume by induction that we have
approximations g̃, h̃ to g, h up to an error lying in the intermediate term Γk ,
where g̃ and h̃ are short words in a generating set. Substituting g̃ and h̃ into
our commutator expression, we obtain approximations [g̃, h̃] to elements of Γj
by short words. Lemma 2.1 gives us some control over the fidelity of these
approximations. Let us illustrate this with an example.
Example 2.4. Let Γ be a group, let Γ ≥ Γ1 ≥ Γ2 ≥ Γ3 be finite-index normal
subgroups of Γ, and suppose:
[Γ1 , Γ2 ] ≤ Γ3 .

(1)

Second, suppose that for any k ∈ Γ2 , there exist g, h ∈ Γ1 such that:
[g, h]k −1 ∈ Γ3 .

(2)

Now let S ⊆ Γ, and suppose the image of S in Γ/Γ3 is a generating set. Let
d = diam(Γ/Γ2 , S), so that:
Γ = Γ2 BS (d)
(3)
(here we abuse notation slightly, denoting also by “S” the image of S modulo
any of the Γi ).
We wish to bound diam(Γ/Γ3 , S). That is, given k ∈ Γ we seek a short word
w in S such that kw−1 ∈ Γ3 . First suppose that k ∈ Γ2 . Let g, h ∈ K1 be
as in (2). By (3), there exist g̃, h̃ ∈ BS (d) such that g −1 g̃, h−1 h̃ ∈ Γ2 . Setting
G1 = H1 = Γ1 , G2 = H2 = Γ2 , g1 = g, h1 = h, g2 = g −1 g̃, h2 = h−1 h̃ in
Lemma 2.1, and applying (1),
[g̃, h̃] ≡ [g, h] ≡ k mod Γ3 .
Since [g̃, h̃] ∈ BS (4d), we have Γ2 ⊆ Γ3 BS (4d). Applying (3) again, Γ =
Γ3 BS (5d), so diam(Γ/Γ3 , S) ≤ 5d.
Although the hypotheses (1) and (2) may seem somewhat artificial in the
context of this abstract example, in practice many groups satisfy these conditions, or variants thereof. Modifications to the method of Example 2.4 are
however sometimes necessary, or desirable. For instance the elements g and
h in Example 2.4 were taken to lie at the same level of the subgroup chain,
whereas for many groups, including the branch groups studied in this paper,
good commutator expressions will involve elements lying at different levels.

2.2

Groups Acting on Regular Rooted Trees

Let us set up some basic notation and definitions concerning the class of groups
to be studied in the sequel. All of the material here (and much, much more
besides) is covered in [6] and [10] Chapter VIII.
Let A be a finite set, and let A∗ be the set of formal positive words on the
alphabet A. We may partially order A∗ via the prefix relation ≤, where for
u, v ∈ A∗ , u ≤ v iff there exists w ∈ A∗ such that v = uw.
Geometrically, we may regard A∗ as the set of vertices of a regular rooted
tree TA : the root vertex is identified with the empty word, and every vertex v
is joined by an edge to its |A| children va, a ∈ A. Under this identification, the
set An of words of length n is precisely the sphere of radius n in TA about the
root vertex, known as the nth level set.
The automorphism group Aut(TA ) is the set of permutations of A∗ preserving
the prefix relation. Geometrically this just the group of graph automorphisms
of the tree TA . For the valence of every vertex of TA is |A| + 1 except for the
root vertex (which has valence |A|), so every automorphism of TA fixes the root
vertex, and hence preserves the level sets. The kernel of the action of Aut(TA ) on
the nth level set An will be called the nth level stabiliser and denoted Stab(n);
n
it is naturally isomorphic to Aut(TA )(×|A| ) . If Γ ≤ Aut(TA ) we write StabΓ (n)
for Γ ∩ Stab(n), though in general we cannot say more about the structure of
n
StabΓ (n) than that StabΓ (n) is isomorphic to a subgroup of Aut(TA )(×|A| ) .
For any φ ∈ Aut(TA ), there exists a unique σφ ∈ Sym(A) such that for any
x ∈ A, there exists a unique φx ∈ Aut(TA ) such that:
φ(xw) = σφ (x)φx (w), for all w ∈ A∗ .
The induced map ψ : φ 7→ (φx )x∈A · σφ gives an isomorphism
Aut(TA ) → Aut(TA ) ≀ Sym(A). Note that the level stabilisers may be described
recursively by Stab(0) = Aut(TA ) and Stab(n + 1) = ψ −1 (Stab(n)(×|A|) ) for
n ∈ N.
Of particular interest among the subgroups of Aut(TA ) are those whose
action on A∗ is branch. Our characterization of such groups is based on that
appearing in [3].
Definition 2.5. Let Γ ≤ Aut(TA ). Γ is (regular) branch if:
(i) The action of Γ on A is transitive;
(ii) ψ(StabΓ (1)) ≤ Γ(×|A|) ;
(iii) Γ has a finite-index subgroup K such that K (×|A|) ≤ ψ(K).
We will simply say that a group Γ branches over K when the alphabet A and
the action of Γ on A∗ is clear.
For the sake of uncluttered notation we will allow ourselves to supress the
map ψ from expressions and identify subgroups of Γ with their image under ψ,
so for instance we may (abuse notation somewhat and) speak of K (×|A|) as a
n
subgroup of K; StabΓ (n) as a subgroup of Γ(×|A| ) and so on.

In truth, branch groups form a much broader class than those groups covered
by Definition 2.5 (see for instance [6]), but this more restricted setting will be
most convenient for our purposes.
We now define the specific branch groups which are the subject of Theorems
1.1-1.5.
2.2.1

The Grigorchuk 2-Group

Let A = {0, 1} and write TA = T2 . The Grigorchuk 2-group (sometimes known
as the first Grigorchuk group) is the subgroup G of Aut(T2 ) generated by the
four automorphisms a, b, c, d, defined by:
a(0w) = 1w; a(1w) = 0w;
b(0w) = 0a(w); b(1w) = 1c(w);
c(0w) = 0a(w); c(1w) = 1d(w);
d(0w) = 0w; d(1w) = 1b(w).
In other words, a swaps the subtrees rooted at 0 and 1, while b, c, d ∈ StabG (1)
are defined recursively via:
b = (a, c), c = (a, d), d = (1, b).
An easy induction on the levels shows that:
a2 = b2 = c2 = d2 = 1, bc = cb = d, cd = dc = b, bd = db = c.

(4)

Let x = abab ∈ G and let K = hxiG ⊳ G. We will require the following basic
facts in the sequel.
Proposition 2.6 ([10] Chapter VIII). Let G, K, x be as above.
(i) G branches over K;
(ii) G/K ∼
= D8 × C2 ;
(iii) K/K (×2) ∼
= C4 , generated by x.
m

Lemma 2.7. K (×2

)

⊳ G for all m ≥ 0.

Proof. We proceed by induction on m, the base case m = 0 holding by definition.
m
For m ≥ 1, we verify that K (×2 ) is preserved under conjugation by the
generators a, b, c, d. This is the case for a, which simply permutes the factors in
the direct product.
m
m−1
) (×2)
b, c and d preserve the decomposition K (×2 ) = (K (×2
)
, and act on
(×2m−1 )
each K
-factor as a, b, c or d. The result follows by induction.
m

Lemma 2.8. For all m ≥ 0, K (×2

)

≤ StabG (m + 1).

Proof. Note that x = abab ∈ StabG (1). The result is now immediate from
Proposition 2.6 (iii).

Lemma 2.9. For all n ≥ 1,

n−1

|G : StabG (n)| ≥ 22

+1

.
m−1

Proof. It suffices to prove that |StabG (m) : StabG (m + 1)| ≥ 22
for all
m
m ∈ N. x = abab ≡ (a, a) mod StabAut(T2 ) (2), so as ǫ ranges over {0, 1}2 , the
m
elements (xǫi )2i=1 are all distinct modulo StabG (m + 1), and lie in StabG (m) by
Lemma 2.8.
2.2.2

The Gupta-Sidki p-Groups

Fix an odd prime p, let A = {0, 1, . . . , p−1} and write TA = Tp . The Gupta-Sidki
p-group is the subgroup Γ(p) of Aut(Tp ) generated by the two automorphisms
a, b, where a is defined by:
a(iw) = (i + 1)w for 0 ≤ i ≤ p − 2; a((p − 1)w) = 0w
(so that a cyclically permutes the level-1 subtrees) and b ∈ StabAut(Tp ) (1) is
defined recursively via:
b = (a, a−1 , 1, . . . , 1, b)
so that both a and b have order p. Note that a reduced word in a and b corresponds to an element of StabΓ(p) (1) iff the number of occurences of a (counted
with signs) is congruent to 0 modulo p. Thus StabΓ(p) (1) = hbiΓ(p) .
Let K = [Γ(p) , Γ(p) ] be the derived subgroup of Γ(p) .
Note that
K ≤ StabΓ(p) (1). Let x1 = [a, b] ∈ K, and for 1 ≤ i ≤ p − 2, define
xi+1 = [a, xi ] ∈ K. The following computations were made in [15], generalising results from [27] for Γ(3) .
Proposition 2.10 ([15] Proposition 2.2). Let B = StabΓ(p) (1). Then:
(i) Γ(p) /K ∼
= Cp × Cp , with basis Ka, Kb;
(ii) B ′ = K (×p) ;
(iii) Γ(p) /B ′ ∼
= Cp ≀ Cp .
From this we have an explicit description of the branch structure of Γ(p) .
Corollary 2.11.

(i) Γ(p) branches over K;

(×(p−1))
(ii) K/K (×p) ∼
, with basis x1 , . . . , xp−1 .
= Cp

Proof.

(i) From Proposition 2.10 (ii),
K (×p) = B ′ ≤ Γ′(p) = K.

(ii) We defer this to Section 4, where we introduce additional notation which
will be convenient to use in the proof.

The following observation will be key to the deduction of Theorem 1.3 from
Theorem 1.4.
m

Lemma 2.12. For all m ∈ N, K (×p

)

≤ StabΓ(p) (m + 1).

Proof. It clearly suffices to check that K ≤ StabΓ(p) (1). This is so because
K = [Γ(p) , Γ(p) ] and Γ(p) / StabΓ(p) (1) is abelian.

3

Proofs for Grigorchuk’s Group

In this Section we prove Theorem 1.2 and deduce Theorem 1.1. Before embarking on the proof of our diameter bounds, we marshal some facts about the lower
central series of G.
Recall that for any group G, the degree deg(g) of g ∈T G is given by
∞
g ∈ γdeg(g) (G) \ γdeg(g)+1 (G), with the convention that all g ∈ n=1 γn (G) have
degree ∞ (though in G, the latter situation never arises for gT6= 1: G is a residu∞
ally finite 2-group, so is residually 2-finite, and in particular, n=1 γn (G) = {1}).
For any g ∈ K, write 0(g) = (g, 1), 1(g) = (g, g −1 ) ∈ K (×2) .
Theorem 3.1 ([3, 5, 26]). Let X1 , . . . , Xn ∈ {0, 1}. Then:
deg X1 · · · Xn (x) = 1 +

n
X

Xi 2i−1 + 2n ;

deg X1 · · · Xn (x2 ) = 1 +

n
X

Xi 2i−1 + 2n+1 .

i=1

i=1

Theorem 3.2 ([3, 5, 26]). For all m ≥ 2,
m−1

|G : γ2m +1 (G)| = 22

3+2

.

To avoid cluttered notation, in this section we may write γn = γn (G). The
specific consequences of Theorem 3.1 to be used in the proof of Theorem 1.2 are
as follows.
m

Corollary 3.3. γ2m +2m−1 +1 ≤ K (×2

)

≤ γ2m +1 .

To be more precise, we have the following estimates.
n−2 
\ {0},
Corollary 3.4. For all δ ∈ {0, 1}2
(i) 2n + 1 ≤ deg

(x, 1, 1, 1)δi

2n−2 
i=1

≤ 2n + 2n−2 ;

(ii) 2n + 2n−2 + 1 ≤ deg

(x, 1, x, 1)δi

(iii) 2n + 2n−1 + 1 ≤ deg

(x, x, 1, 1)δi

(iv) 2n + 3 · 2n−2 + 1 ≤ deg

2n−2 
i=1

2n−2 
i=1

(x, x, x, x)δi

≤ 2n + 2n−1 ;
≤ 2n + 3 · 2n−2 ;

2n−2 
i=1

≤ 2n+1 ;

(v) Specifically, deg
(vi) 2n + 1 ≤ deg

2n−2 
(x, x, x, x) i=1 = 2n+1 ;

(x2 , 1)δi

(vii) 2n + 2n−2 + 1 ≤ deg
(viii) Specifically, deg

2n−2 
i=1

≤ 2n + 2n−2 ;

(x2 , x2 )δi

2n−2 
i=1

≤ 2n + 2n−1 ;

2n−2 
(x2 , x2 ) i=1 = 2n + 2n−1 .

We now produce our commutator approximations to elements lying sufficiently deep in (γn )n . The following identities are verified by direct computation.



Lemma 3.5. (i) x, (x, 1) = x−1 , 1, 1, 1 .



(ii) x, (x, x) = x−1 , 1, 1, (1, x−1 )x .



(iii) x2 , (x, 1) = x−1 , x, 1, 1 .



(iv) x2 , (x, x−1 ) = x−1 , x, (x−1 , 1)x−1 , (1, x−1 )x .

Proof. We prove (i) and leave the verifications of the other identities, which are
similar, as an exercise. First note that x = abab = (ca, ac). Thus:



x, (x, 1) = [ca, x], 1
Now, using (4) we have:

[ca, x] = ac(ac, ca)ca(ca, ac)
= a(ca, bad)a(ca, ac)
= (bad, ca)(ca, ac)
= (baba, 1)
= (x−1 , 1)
as desired.
Lemma 3.5 yields good approximations to elements of K (×4) , modulo K (×8) ,
n
by commutators of elements of K and K (×2) . For deeper subgroups K (×2 ) , we
(×4)
express elements as vectors of elements in K
, and produce a commutator
approximation by applying Lemma 3.5 to each term of the vector. The expressions we obtain can be related to the lower central series by using Theorem 3.1
and Corollaries 3.3 and 3.4 to estimate the degrees of the elements occuring. In
summary we have the following Proposition.
Proposition 3.6. Let c : G × G → G be given by c(g, h) = [g, h]. Let m ≥ 2.
Then:
(i) The restriction of c to γ2m−1 × γ2m−1 descends to a well-defined map:
c̄m : (γ2m−1 /γ2m +1 )(×2) → G/γ2m +2m−1 +1

m

whose image contains K (×2

)

/γ2m +2m−1 +1 .

(ii) The restriction of c to γ2m−1 +2m−2 ×γ2m−1 +2m−2 descends to a well-defined
map:
¯c̄m : (γ2m−1 +2m−2 /γ2m +2m−1 +1 )(×2) → G/γ2m+1 +1
whose image contains γ2m +2m−1 +1 /γ2m+1 +1 .
Proof. The well-definedness of c̄m and ¯c̄m is an immediate consequence of Corollary 2.2. It therefore suffices to check the images of the maps contain the specified subgroups.
m
For (i), note that by Corollary 3.4, every element of K (×2 ) /γ2m +2m−1 +1 is
2m−2
represented by (xδi +ǫi , 1, xǫi , 1) i=1 for some δi , ǫi ∈ {0, 1}. By Lemma 3.5
(i) and (ii),


−1
−1
x, (x, 1) · x, 1, 1, 1
= x2 , 1, 1, 1


−1

−1
x, (x, x) · x, 1, x, 1
≡ 1, 1, x, x x2 , 1, x2 , 1

m−2

m−2

2
∈ {0, 1}2
By Corollary 3.4 (iii) and (iv), for any (βi )i=1
2m−2
(1, 1, x, x)βi i=1 ∈ γ2m +2m−1 +1 ,
m−2

3

mod K (×2 ) .
,

m−2

2
by Corollary 3.4 (vi), for any (βi )i=1
∈ {0, 1}2
,
2m−2
2m−2
(x2 , 1, 1, 1)βi i=1 , (x2 , 1, x2 , 1)βi i=1 ∈ γ2m +2m−1 +1 ,
m+1

and from Corollary 3.3, K (×2
m−2
2m−2
(ǫi )i=1
∈ {0, 1}2
,

)

⊆ γ2m+1 +1 .

m−2

2
Hence, for any (δi )i=1
,


2m−2  2m−2
2m−2
(xδi +ǫi , 1, xǫi , 1) i=1 ≡ (x)i=1
, ((x, 1)δi )i=1
 2m−2

2m−2
· (x)i=1
, ((x, x)ǫi )i=1
m−2

mod γ2m +2m−1 +1 .
m−2

m−2

2
2
2
,
and ((x, x)ǫi )i=1
Using Corollary 3.4 to estimate the degrees of (x)i=1
, ((x, 1)δi )i=1
and by the standard identity [a, bc] = [a, c][a, b][[a, b], c], we deduce:


2m−2  2m−2
2m−2
mod γ2m +2m−1 +1 .
(xδi +ǫi , 1, xǫi , 1) i=1 ≡ (x)i=1
, ((xδi +ǫi , xǫi ))i=1
(5)
For (ii), we see similarly by Corollary 3.4 that every element of γ2m +2m−1 +1 /γ2m+1 +1
2m−2
is represented by (xδi +ǫi , xδi +ǫi , xǫi , xǫi ) i=1 for some δi , ǫi ∈ {0, 1}. By
Lemma 3.5 (iii) and (iv),
 2

−1
−1
x , (x, 1) · x, x, 1, 1
= x2 , 1, 1, 1
 2

−1
−1
x , (x, x−1 ) · x, x, x, x
≡ x2 , 1, x2 , 1

3

mod K (×2 ) .

Using Corollary 3.3 and Corollary 3.4 (vi) once again as in (i), we have that for
m−2
2m−2
2m−2
any (δi )i=1
, (ǫi )i=1
∈ {0, 1}2
,

2m−2 
2m−2
2m−2
(xδi +ǫi , xδi +ǫi , xǫi , xǫi ) i=1 ≡ (x2 )i=1
, ((x, 1)δi )i=1


2m−2
2m−2
· (x2 )i=1
, ((x, x−1 )ǫi )i=1

mod γ2m +2m−1 +1 .

As before, we apply the commutator identity for products, using the estimate of
2m−2
2m−2
2m−2
from Corollary 3.4,
and ((x, x−1 )ǫi )i=1
the degrees of (x2 )i=1
, ((x, 1)δi )i=1
and deduce:

2m−2 
2m−2
2m−2
mod γ2m+1 +1 .
(xδi +ǫi , xδi +ǫi , xǫi , xǫi ) i=1 ≡ (x2 )i=1
, ((xδi +ǫi , x−ǫi ))i=1
(6)
Using Proposition 3.6 we may approximate any tuple consisting of xs and
m−1
m
)
1s by a commutator. To express arbitrary tuples in K (×2
/K (×2 ) we must
2
also find approximations for tuples consisting of x s and 1s. Here we will diverge
slightly from our overall strategy of approximating elements by commutators,
since it appears far more natural to express such tuples as squares.
Proposition 3.7. The squaring map s : g 7→ g 2 on G induces a surjection:
m−1

sm : K (×2

)

m

/γ2m +1 → γ2m +1 /K (×2

)

for all m ≥ 1.
Proof. It is immediate from Lemma 2.6 and Corollaries 3.3 and 3.4 that
m−1
m
)
K (×2
/γ2m +1 and γ2m +1 /K (×2 ) are elementary abelian 2-groups, each element of the latter being represented by a vector:
m−1

m−1

2
2
),
= s((xδi )i=1
(x2δi )i=1
m−1

m−1

m−1

2
∈ K (×2
as δ ranges over {0, 1}2
. Since (xδi )i=1
m
(×2m−1 )
(×2
)
K
→ γ2m +1 /K
.
m−1

Now let a ∈ K (×2

)

)

, s induces a surjection

, b ∈ γ2m +1 . We have:

s(ab) = s(a)[a, b−1 ]s(b).

m

But s(γ2m +1 ) ⊆ K (×2

)

(as noted above) and:
m−1

[K (×2

)

m

, γ2m +1 ] ⊆ K (×2
m−1

by Corollary 3.3 (applied to both K (×2
well-defined.

)

)
m

and K (×2

)

). Thus sm is indeed

We now come to the heart of the proof of our diameter bound: using Propositions 3.6 and 3.7, we show that if a symmetric subset X ⊆ G contains an
approximation to every element of G up to an error lying in γ2m +1 , then every
element of G is approximated, up to an error in the (much smaller) subgroup
γ2m+1 +1 , by a short word in X.

Proposition 3.8. Let m ≥ 2 and let X ⊆ Γ be a symmetric subset such that:
Xγ2m +1 = G.

(7)

X 35 γ2m+1 +1 = G.

(8)

Then:
Proof. First, note that Proposition 3.7 immediately implies:
m

X 2 K (×2

)

⊇ γ2m +1 .

(9)

Second, we combine (7) and Proposition 3.6 (ii) with Corollary 2.2 to conclude:
m
K (×2 ) ⊆ X 4 γ2m +2m−1 +1 .
(10)
Taking stock of what we have thus far, (7), (9) and (10) combine to give:
X 7 γ2m +2m−1 +1 = G.

(11)

Finally, we combine (11) and (6) with Corollary 2.2 and conclude:
γ2m +2m−1 +1 ⊆ X 28 γ2m+1 +1 .

(12)

The required conclusion (8) is now immediate from (11) and (12).
Proof of Theorem 1.2. Let S ⊆ G/γn (G) be a generating set. If n ≤ 5 then:
diam(G/γn (G), S) ≤ |G : γn (G)|
is bounded by an absolute constant C̃. Otherwise let S̃ ⊆ G be any subset whose
image in G/γn (G) is S, and let m ∈ N be such that 2m−1 + 1 < n ≤ 2m + 1.
Then BS̃ (C̃)γ5 (G) = G, and by repeated application of Proposition 3.8,
BS̃ (35m−2 C̃)γ2m +1 (G) = G
so that diam(G/γn (G), S) ≤ 35m−2 C̃ ≪ nlog(35)/ log(2) .
The result now follows from Theorem 3.2.
Remark 3.9. Note that the above proof facilitates straightforward computation
of the implied constant from the statement of Theorem 1.2.
Proof of Theorem 1.1. By Lemma 2.8 and Corollary 3.3,
γ2n+1 +1 (G) ≤ StabG (n + 1)
so:
diam(G/ StabG (n + 1)) ≤ diam(G/γ2n+1 +1 (G)).
The result is now immediate from Theorem 1.2, Lemma 2.9 and Theorem 3.2.

Remark 3.10. It is very likely that detailed knowledge of the lower central
series of G is not required to prove Theorem 1.1. Rather, one could give a
n
direct proof of a diameter bound for G/K (×2 ) and deduce Theorem 1.1 from
this, much as we do for the Gupta-Sidki groups in the following Section. The
reason for organizing the proof of Theorem 1.1 as it appears here is historical.
Theorem 1.2 was the first of our results to be proved, followed be a direct
proof of Theorem 1.5, using the results of [3] on the lower central series of Γ(3) .
The case p = 3 of Theorem 1.3 was then deduced from Theorem 1.5 (much as
Theorem 1.1 follows from Theorem 1.2). The (arguably more natural) proof
of Theorem 1.3 from Theorem 1.4 was a later response to the need to avoid
assuming knowledge of the lower central series of Γ(p) in proving Theorem 1.3
for higher p (to the author’s knowledge, the lower central series of Γ(p) has not
been computed for p ≥ 5).
Remark 3.11. Proposition 3.7 hints at the possibility of an alternative approach to proving diameter bounds for sequences of groups, following the same
broad lines as the Solovay-Kitaev procedure employed here and in [8], but using power-words instead of commutator words. This will be explored further
elsewhere [9].

4

Proofs for the Gupta-Sidki Groups

In this section we prove Theorem 1.4 and, from it, Theorem 1.3. For the remainder of the section we shall write Γ for Γ(p) . Any assumptions on the prime
p in what follows will be made explicit in the appropriate place.
The following notation will be useful in the sequel: for any g ∈ Aut(TA ),
let 0(g) = (g, 1, . . . , 1) ∈ Aut(TA )(×p) , and for 0 ≤ j ≤ p − 1, let
(j + 1)(g) = [a, j(g)]. Hence for 0 ≤ j ≤ p − 1,


 g αj,i 1 ≤ i ≤ j + 1
j
j(g)i =
, where αj,i = (−1)i+1
.
1
otherwise
i−1
Note that αp−1,i ≡ 1 mod p for all 1 ≤ i ≤ p. It follows that:
(p − 1)(a) = (a, . . . , a), (p − 1)(b) = (b, . . . , b)
(since a, b have order p) and:
2

(p − 1)(g) ≡ (g, . . . , g) mod K (×p

)

for any g ∈ K

(since K ≤ StabΓ (1) and Γ/K has exponent p, so too does K/K (×p) ).
Note also that in this notation,
b = 1(a)0(b)a

−1

= 0(b)a 1(a).
−1

It follows from the definition of the elements xi that for 1 ≤ i ≤ p − 1:
xi (i + 1)(a)i(b)a

−1

−1

∈ K (×p)

(13)

and in particular:
xp−2 (a, . . . , a)−1 ∈ (StabΓ (1))(×p)

(14)

xp−1 (b, . . . , b)−1 ∈ K (×p)

(15)

These observations facilitate the completion of:
Proof of Corollary 2.11 (ii). Since K ≤ StabΓ (1), K/K (×p) is an elementary
abelian p-group. Moreover, from Proposition 2.10 (i) and (iii) we have
|K : K (×p) | = pp−1 , so it suffices to check that the images of x1 , . . . , xp−1
in K/K (×p) are linearly independent.
Embedding StabΓ (1) into Γ(×p) (via ψ), we have an induced embedding of
K/K (×p) into (Γ/K)(×p) . By Proposition 2.10 (i),
(×2p)
.
(Γ/K)(×p) = hKa, Kbi(×p) ∼
= Cp

From (13), the image of xi in (Γ/K)(×p) is vi = (i + 1)(Ka)i(Kb)a . For all
1 ≤ i ≤ p − 2, vi has non-zero Ka-component in its (i + 2)th entry, but zero
Ka-component in its jth entry for all j ≥ i+3, so that vi is linearly independent
of hv1 , . . . , vi−1 i.
Similarly, for all 1 ≤ i ≤ p − 2, vi has zero Kb-component in its (p − 1)th
entry, whereas vp−1 has non-zero Kb-component there, so vp−1 is independent
of hv1 , . . . , vp−2 i.
−1

Corollary 4.1. For all n ≥ 1,
n−1

|Γ : StabΓ (n)| ≥ p(p−2)(p

−1)+1

.
m−1

−1)
Proof. It suffices to check |StabΓ (m) : StabΓ (m + 1)| ≥ p(p−2)(p
for all
m ≥ 1.
m
Embedding StabΓ (m) into Γ(×p ) (via repeated application of ψ) we have
an induced embedding:
m

StabΓ (m)/ StabΓ (m + 1) ֒→ (Γ/ StabΓ (1))(×p

)

m

(×p
∼
= Cp

)

(with each (Γ/ StabΓ (1))-factor generated by StabΓ (1)a). From (13), the image
of xi ∈ StabΓ (1) in (Γ/ StabΓ (1))(×p) is (i + 1)(StabΓ (1)a).
Arguing as in the proof of Corollary 2.11 (ii), the elements:
 p−2
Y
j=1

λ

xj i,j

pm

i=1

are distinct modulo StabΓ (m + 1) as the pm−1 × (p − 2) coefficients λi,j vary
over {0, 1, . . . , p − 1}, and the required result follows.
We also introduce some further normal subgroups which will be useful “placeholders” for our induction in the proof of Theorem 1.4. For 1 ≤ i ≤ p, let:
Li = xi , . . . , xp−1 , K (×p) ≤ K

(with Lp = K (×p) by convention). For 0 ≤ i ≤ p, let:
(×p)

Ki

(×pn+1 )

Ki

(×p)

= i(x1 ), . . . , (p − 1)(x1 ), L2
(×p) (×pn )

= (Ki

)

(×p)

(×p)

(with the convention Kp
groups:
(×pn )

L2

(×pn )

= Kp

= L2

≤ K (×p) ;

). We thus have descending chains of sub-

(×pn )

(×pn )

≤ Kp−1 ≤ . . . ≤ K1

(×pn )

≤ K0

n

= K (×p

)

and:
n+1

K (×p

)

(×pn )

= Lp

(×pn )

≤ Lp−1

(×pn )

≤ . . . ≤ L2

.

Lemma 4.2. The following are normal in Γ(p) , for all n ∈ N:
n

(i) K (×p ) ;
(×pn )

(ii) Li

, for 1 ≤ i ≤ p − 1;

n+1

(×p

(iii) Ki

)

, for 0 ≤ i ≤ p − 1.

n

Proof. First, by induction we reduce to the case n = 0. For let H = K (×p ) ,
(×pn+1 )
(×pn )
. If H ⊳ Γ(p) , then H (×p) is normalised by a (which permutes
Ki
or Li
the factors) and by b (which acts on each factor as a±1 or b).
Now certainly K ⊳ Γ(p) , so we have (i). In the other cases, we check that
conjugates of a generating set for the subgroup, by the generators of Γ(p) , lie in
the subgroup.
For (ii), consider the conjugation action of Γ(p) on K/K (×p) . We have
a
a
(×p)
xi = xi x−1
and xbi ≡ xi mod K (×p)
i+1 for 1 ≤ i ≤ p−2; xp−1 ≡ xp−1 mod K
for 1 ≤ i ≤ p − 1. Thus Li ⊳ Γ(p) .
(×p)

For (iii), consider the conjugation action of Γ(p) on K (×p) /L2 .
We have i(x1 )a
= i(x1 )(i + 1)(x1 )−1 for 1 ≤ i ≤ p − 2;
(×p)
and i(x1 )b ≡ i(x1 ) for 1 ≤ i ≤ p − 1.
(p − 1)(x1 )a ≡ (p − 1)(x1 ) mod L2
(×p)
Thus Ki
⊳ Γ(p) .

To apply Lemma 2.1 in our induction, we will need certain commutators
of elements in Γ to lie in a sufficiently deep subgroup. As such, we note the
following.
Lemma 4.3.

(i) [StabΓ (1), StabΓ (1)] ≤ K (×p) ;
(×p)

(ii) [StabΓ (1), K (×p) ] ≤ L2

.

Proof. For (i), note that any element of StabΓ (1) is a p-tuple of elements of Γ,
so any commutator of such is a p-tuple of elements of [Γ, Γ] = K.
Likewise in (ii), every element of [StabΓ (1), K (×p) ] is a p-tuple of elements
of [Γ, K]. K/L2 is generated by x1 , and Γ is generated by a and b, so, since
L2 ⊳ K, it suffices to check that [a, x1 ], [b, x1 ] ∈ L2 (the former by definition;
the latter by (i)).

We now describe our approximations to elements of Γ by commutators.
These are split between the next four propositions, which are closely reminiscent of Proposition 3.6 in our proof for Grigorchuk’s group. The first of these
2
(×p2 )
allows us to approximate elements of K (×p ) up to an error in K1
. We remark that this is the only point in the proof of Theorem 1.4 at which different
arguments are required according to the value of p. To be precise, we exhibit
one construction of an approximation by commutators which is valid for p ≥ 7;
one for p = 5 and one for p = 3.
Let c : Γ × Γ → Γ be given by c(g, h) = [g, h].
Proposition 4.4. The restriction of c to Lp−1 × K (×p) descends to a welldefined map:
2

2

(×p2 )

c̄0 : (Lp−1 /K (×p ) ) × (K (×p) /K (×p ) ) → Γ/K1
2

(×p2 )

whose image contains K (×p ) /K1

.

Proof. Observe that by Lemma 2.1, for g1 ∈ Lp−1 , h1 ∈ K (×p) and g2 ,
2
h2 ∈ K (×p ) we have:

2 
[g1 g2 , h1 h2 ][g1 , h1 ]−1 ∈ Lp−1 , K (×p ) .

But Lp−1 is generated by K (×p) and xp−1 , both of which lie in StabΓ (1)(×p)
(the latter since xp−1 is congruent modulo K (×p) to (b, . . . , b)). Hence:


(×p)
2 
(×p2 )
(p2 )
(by Lemma 4.3 (ii)).
Lp−1 , K (×p ) ⊆ StabΓ (1), K (×p)
⊆ L2 ⊆ K1

Thus c̄0 is indeed well-defined.
2
(×p2 )
We now establish that the image of c̄0 contains K (×p ) /K1
. First suppose
p ≥ 7. We have:
xa1 = (b, b−1 a, a−2 , a, 1, . . . , 1)
xa1

−2

= (a, 1, . . . , 1, b, b−1 a, a−2 )

so that 0(x1 ) = [xa1 , xa1 ]. Moreover for λ ∈ N,

 
−2
(×p)
(×p)
0(x1 )λ ≡ [xa1 , (xa1 )λ ] mod K, K K ≤ L2
≤ K1
−2

(by Lemma 4.3).
p
2
(×p2 )
Now, any element of K (×p ) /K1
is represented by a vector 0(x1 )λj j=1
for some (λj )pj=1 ∈ Fpp . By the above,
p
 −2

(×p2 )
0(x1 )λj j=1 ≡ (xa1 )pj=1 , ((xa1 )λj )pj=1 mod K1

and we are done.
Now suppose p = 5. We have xa1 = (b, b−1 a, a−2 , a, 1). Hence:
[x1 , xa1 ] = (x1 , aba−2 b−1 a, 1, 1, 1).

An easy direct computation yields aba−2 b−1 a ≡ x1 mod L2 . So:

(×5)

[x1 , xa1 ] ≡ 0(x1 )2 mod K1

.

(×52 )

2

As before, any element of K (×5 ) /K1
is represented by:



5
(×52 )
0(x1 )λj j=1 ≡ (x1 )5j=1 , ((xa1 )3λj )5j=1 mod K1

for some (λj )5j=1 ∈ F55 , as required.
Finally suppose p = 3. Recall that:

b = (a, a−1 , b) and x1 = [a, b] = (b−1 a, a, ab).
Thus:
[b, x1 ] = ([a, b−1 a], 1, [b, ab])
We compute:
[a, b−1 a] = ([b, a]b )a
−1

≡ (x−1 )a
≡ x−1
1

−1

−1

mod K (×3) (by Lemma 4.3 (i))

mod L2

and:
[b, ab] = [b, a][[b, a], b]
≡ x−1
1

mod K (×3) (by Lemma 4.3 (i))

so that:
−1
[b, x1 ] ≡ (x−1
1 , 1, x1 )

(×3)

mod L2

≡ 0(x1 )

(×3)

mod K1

.

Now:
x2 = [a, x1 ] = (b−1 a−1 b−1 a, a−1 ba, b)
= (bx1 [x1 , b−1 ], bx−1
1 , b)
2

(×3
≡ (bx1 , bx−1
1 , b) mod K

)

(by Lemma 4.3 (i))

so for λ1 , λ2 , λ3 ∈ N,
λ2
λ3
[x2 , (xλ1 1 , xλ1 2 , xλ1 3 )] ≡ [bx1 , xλ1 1 ], [bx−1
1 , x1 ], [b, x1 ]

(by the well-definedness of c0 ) whereas for µ, λ ∈ N,



[bxµ1 , xλ1 ] = [b, xλ1 ][[b, xλ1 ], xµ1 ]
(×3)

≡ [b, xλ1 ] mod L2
≡ [b, x1 ]λ

so by (16) we have:

(×3)

mod L2

(×32 )

mod K1

(by Lemma 4.3 (ii))

(16)

(×32 )

[x2 , (xλ1 1 , xλ1 2 , xλ1 3 )] ≡ (0(x1 )λ1 , 0(x1 )λ2 , 0(x1 )λ3 ) mod L2
(×p2 )

2

and every element of K (×p ) /K1
λi ∈ F3 , as required.

is represented by (xλ1 1 , xλ1 2 , xλ1 3 ) for some
(×p2 )

Second, we construct an approximation to elements of Ki+1
lying in

up to an error

(×p2 )
Ki+2 .

(×p2 )

Proposition 4.5. Let 0 ≤ i ≤ p − 2. The restriction of c to Lp−2 × Ki
descends to a well-defined map:
(×p2 )

2

c̄i : (Lp−2 /K (×p ) ) × (Ki
(×p2 )

(×p2 )

(×p2 )

(×p2 )

/Ki+1 ) → Γ/Ki+2

whose image contains Ki+1 /Ki+2 .
Proof. We check first that c̄i is well-defined. Observe that by Lemma 2.1, for
2
(×p2 )
(×p2 )
g1 ∈ Lp−2 , h1 ∈ Ki
, g2 ∈ K (×p ) and h2 ∈ Ki+1 , we have:

2 
(×p2 )  (×p2 )
Ki
, K (×p ) .
[g1 g2 , h1 h2 ][g1 , h1 ]−1 ∈ Lp−2 , Ki+1
It therefore suffices to check that:

2 
(×p2 )  (×p2 )
(×p2 )
Lp−2 , Ki+1
Ki
, K (×p ) ⊆ Ki+2 .

(17)

But Lp−2 = hxp−2 , Lp−1 i and Lp−1 ⊆ StabΓ (2), so that by Lemma 4.3 (i),

3
(×p2 ) 
(×p2 )
Lp−1 , Ki+1
⊆ K (×p ) ⊆ Ki+2

while xp−2 (a, . . . , a)−1 ∈ StabΓ (1)(×p) , so:


(×p2 ) 
(×p) (×p) 
(×p) (×p)
(×p2 )
hxp−2 i, Ki+1
⊆ hai, Ki+1
StabΓ (1), Ki+1
⊆ Ki+2

(×p2 ) 
(×p2 )
(×p2 )
(using Lemma 4.3 (ii)). Thus Lp−2 , Ki+1
⊆ Ki+2 . Also, Ki
,
(×p2 )
K
⊆ StabΓ (3), so by Lemma 4.3 (i),
 (×p2 ) (×p2 ) 
3
(×p2 )
Ki
,K
⊆ K (×p ) ⊆ Ki+2 .

Thus (17) is indeed satisfied, and c̄i is well-defined.

(×p2 )

(×p2 )

We now check that the image of c̄i contains Ki+1 /Ki+2 . First note that
for any λ ∈ N,
(i + 1)(x1 )λ = (i + 1)(xλ1 )
= [a, i(xλ1 )]
= [a, i(x1 )λ ].
(×p2 )

(×p2 )

Now, every element of Ki+1 /Ki+2 is represented by an element:
p


(i + 1)(x1 )λj j=1 = (a)pj=1 , (i(x1 )λj )pj=1

for some

(λj )pj=1

(18)

∈ Np . From (14), there exist y1 , . . . , yp ∈ StabΓ (1) such that:

xp−2 = (ayj )pj=1 .
For 1 ≤ j ≤ p,


(×p) 
(×p)
[ayj , i(x1 )λj ][a, i(x1 )λj ]−1 ∈ StabΓ (1), Ki
⊆ Ki+2

by Lemma 2.1 and Lemma 4.3 (ii). Combining with (18) we have:
p

(×p2 )
(i + 1)(x1 )λj j=1 ≡ c xp−2 , (i(x1 )λj )pj=1 mod Ki+2 .
(×p2 )

Since xp−2 ∈ Lp−2 and (i(x1 )λj )pj=1 ∈ Ki

we are done.
(×p2 )

Finally, we construct an approximation to elements of Li+1
lying in

up to an error

(×p2 )
Li+2 .

(×p)

(×p2 )

Proposition 4.6. Let 1 ≤ i ≤ p − 2. The restriction of c to Lp−2 × Li
descends to a well-defined map:
2

2

2

(×p
(×p )
(×p )
(×p2 )
¯c̄i : (L(×p)
/Li+1 ) → Γ/Li+2
) × (Li
p−2 /K
(×p2 )

)

(×p2 )

whose image contains Li+1 /Li+2 .
Proof. We check first that ¯c̄i is well-defined. Observe that by Lemma 2.1, for
2
(×p2 )
(×p)
(×p2 )
, g2 ∈ K (×p ) and h2 ∈ Li+1 , we have:
g1 ∈ Lp−2 , h1 ∈ Li
 (×p) (×p2 )  (×p2 ) (×p2 ) 
.
K
, Li
[g1 g2 , h1 h2 ][g1 , h1 ]−1 ∈ Lp−2 , Li+1
It therefore suffices to check that:
 (×p) (×p2 )  (×p2 ) (×p2 ) 
(×p2 )
⊆ Li+2 .
K
, Li
Lp−2 , Li+1

(19)


3
2
(×p2 )
(×p2 ) 
≤ K (×p ) ≤ Li+2 (by Lemma 4.3 (i)). Meanwhile,
Certainly, K (×p ) , Li
 (×p) (×p2 )  
(×p) (×p)
⊆ Lp−2 , Li+1
Lp−2 , Li+1

(×p) 
(×p)
so it suffices to check that Lp−2 , Li+1 ⊆ Li+2 .
Lp−2 is generated by xp−2 and Lp−1 ⊆ StabΓ (1)(×p) (the latter inclusion
holds because Lp−1 is generated by K (×p) and xp−1 ∈ (b, . . . , b)K (×p) ) Thus:
(×p)


2
(×p)
(×p) 
≤ K (×p ) ≤ Li+1 .
Lp−1 , Li+1 ⊆ StabΓ (1), Li+1
(×p)

(×p)

Meanwhile, Li+1 /Li+2 is generated by the images of 0(xi+1 ), . . . , (p − 1)(xi+1 ),
so by (14),

(×p) (×p)

(×p)
(×p) 
Li+2 ⊆ Li+2 .
hxp−2 i, Li+1 ⊆ hai, hxi+1 i
Thus (19) is indeed satisfied, and ¯c̄i is well-defined.
(×p2 )

(×p2 )

We now check that the image of ¯c̄i contains Li+1 /Li+2 .
First, for any λ ∈ N,

xλi+1 = [a, xi ]λ ≡ [a, xλi ] mod K (×p) (by Lemma 4.3 (i)).
As in the proof of Proposition 4.5, there exist, by (14), y1 , . . . , yp ∈ StabΓ (1)
such that:
xp−2 = (ayj )pj=1 .
For 1 ≤ j ≤ p,



λ
λ
[ayj , xi j ][a, xi j ]−1 ∈ K, K ≤ K (×p)

(by Lemma 4.3 (i)). Thus for λ1 , . . . , λp ∈ N,

λ

λ

2

p
1
) mod K (×p ) .
, . . . , xi+1
[xp−2 , (xλi 1 , . . . , xi p )] ≡ (xλi+1

(×p2 )

(×p2 )

Now every element of Li+1 /Li+2

is represented by:
λ

p
1
, . . . , xi+1
)
(xλi+1
2

2

2

for some (λj )pj=1 ∈ Np . From the above,

2 
λp2
3
λ
(×p2 )
1
) ≡ (xp−2 )pj=1 , (xi j )pj=1 mod K (×p ) ≤ Li+2
, . . . , xi+1
(xλi+1
(×p2 )

2

λ

(×p)

and we have (xp−2 )pj=1 ∈ Lp−2 , (xi j )pj=1 ∈ Li

so the result follows.

Up to now, we have concentrated on approximating, by commutators, ele2
3
ments lying in K (×p ) but outside K (×p ) . We can however quickly extend these
m
m+1
)
approximations to elements lying between K (×p ) amd K (×p
for arbitrary
m ≥ 2. Indeed, since the conclusions of Propositions 4.4-4.6 concern only com3
putations within the group K/K (×p ) the generalisation from the case m = 2 is
immediate from the identification:
m−2

K (×p

)

m+1

/K (×p

)

3
m−2
)
∼
= (K/K (×p ) )(×p

and the observation that, in a direct product of groups, a tuple of commutators
of elements of the factors is the commutator of the tuples of those same elements.
Proposition 4.7. Let m ≥ 2.
(×pm−2 )

(i) The restriction of c to Lp−1
map:
(×pm−2 )

c̄0,m : (Lp−1

m

/K (×p

m

whose image contains K (×p

)

)

m−1

× K (×p

m−1

) × (K (×p
(×pm )

/K1

)

)

descends to a well-defined

m

/K (×p

(×pm−2 )

(×pm−2 )

m

/K (×p

)

(×pm )

) × (Ki

(×pm )

) → Γ/K1

.

(ii) Let 0 ≤ i ≤ p − 2. The restriction of c to Lp−2
a well-defined map:
c̄i,m : (Lp−2

)

(×pm )

/Ki+1

(×pm )

× Ki

descends to
(×pm )

) → Γ/Ki+2

(×pm )

whose image contains Ki+1

(×pm )

/Ki+2

.
(×pm−1 )

(iii) Let 1 ≤ i ≤ p − 2. The restriction of c to Lp−2
to a well-defined map:
m−1

¯c̄i,m : (L(×p
p−2

)

m

/K (×p
(×pm )

whose image contains Li+1

)

(×pm )

) × (Li
(×pm )

/Li+2

(×pm )

/Li+1

(×pm−2 )

× Li

descends

(×pm )

) → Γ/Li+2

.

Proof. By the preceding discussion, (i), (ii) and (iii) follow, respectively, from
Propositions 4.4, 4.5 and 4.6.
We are now ready to put everything together, and use the approximations
from Proposition 4.7 (i)-(iii) to prove a result closely analogous to Proposition
3.8: namely, if a symmetric subset X ⊆ Γ contains an approximation to evm
ery element of Γ up to an error lying in K (×p ) , then every element of Γ is
(×pm+1 )
approximated up to an error lying in K
by a short word in X.
Proposition 4.8. Let Cp be as in Theorem 1.3. Let m ≥ 2 and let X ⊆ Γ be
a symmetric subset such that:
m

XK (×p
Then:

)

= Γ.

m+1

X Cp K (×p

)

(20)

= Γ.

(21)

Proof. The first step shall be to show that:
m

K (×p
m

To this end let k ∈ K (×p

h∈K

m−1

(×p

)

such that:

)

)

(×pm )

⊆ X 4 K1

.

(22)
m−2

(×p

. By Proposition 4.7 (i), there exist g ∈ Lp−1
(×pm )

[g, h] ≡ k mod K1
From (20), there exist xg , xh ∈ X such that:

)

,

.
m

xg ≡ g, xh ≡ h mod K (×p

)

so by the well-definedness of the map c̄0,m from Proposition 4.7 (i),
(×pm )

X 4 ∋ [xg , xh ] ≡ k mod K1

and we have (22).
Define the integer sequence (an )n recursively by a0 = 4 and an = 2an−1 + 2
for n ≥ 1. The second step of the proof shall be to show that:
(×pm )

Ki

(×pm )

⊆ X ai Ki+1

(23)

for 0 ≤ i ≤ p − 1. This shall be achieved by induction on i, using Proposition
4.7 (ii) at each stage (and the base case i = 0 being provided by (22)).
(×pm )
For let 1 ≤ i ≤ p − 1 and let k ∈ Ki
. By Proposition 4.7 (ii), there exist
(×pm−2 )

g ∈ Lp−2

(×pm )

, h ∈ Ki−1

such that:

(×pm )

[g, h] ≡ k mod Ki+1

.

From (20) and the induction hypothesis, there exist xg ∈ X, xh ∈ X ai−1 such
that:
m

xg ≡ g mod K (×p

)

(×pm )

, xh ≡ h mod Ki

so by the well-definedness of the map c̄i,m from Proposition 4.7 (ii),
(×pm )

X ai = X 2ai−1 +2 ∋ [xg , xh ] ≡ k mod Ki+1

and we have (23).
Pp−1
Define the integer sequence (bn )n recursively by b1 =
n=0 an and
bn+1 = 2bn + 2 for n ≥ 2. Combining the inclusions (23) for i from 0 to
p − 1, we have:
m

K (×p

)

(×pm )

= K0

m

⊆ X b1 Kp(×p

)

(×pm )

= X b1 L2

.

(24)

Our third objective shall be to show that:
(×pm )

(×pm )

⊆ X bi Li+1

Li

(25)

for 1 ≤ i ≤ p − 1. This again shall be by induction on i, using Proposition 4.7
(iii), the base case i = 1 being provided by (24).
(×pm )
. By Proposition 4.7 (ii), there
Thus let 2 ≤ i ≤ p − 1 and let k ∈ Li
(×pm−1 )

exist g ∈ Lp−2

(×pm )

, h ∈ Li−1

such that:

(×pm )

[g, h] ≡ k mod Li+1

.

By (20) and the induction hypothesis, there exist xg ∈ X, xh ∈ X bi−1 such that:
m

xg ≡ g mod K (×p

)

(×pm )

, xh ≡ h mod Li

so by the well-definedness of the map ¯c̄i,m from Proposition 4.7 (iii),
(×pm )

X bi = X 2bi−1 +2 ∋ [xg , xh ] ≡ k mod Li+1

as desired.
Pp−1
Finally, set Cp = 1 + i=1 bi . Expressing an and bn in closed form, Cp is as
in the statement of Theorems 1.3 and 1.4. We combine the inclusions (25) for
i from 1 to p − 1 to obtain:
m

K (×p

)

(×pm )

= L1

(×pm )

⊆ X Cp −1 Lp

m+1

= X Cp−1 K (×p

)

m+1

Combining this last inclusion with (20), we have Γ = X Cp K (×p
n

Proof of Theorem 1.4. Let S ⊆ Γ/K (×p ) . If n ≤ 2 then:
n

2

diam(Γ/K (×p ) ) ≤ |G : K (×p ) | = pp+1 .

.

)

, as required.

n

If n ≥ 3 then let S̃ ⊆ Γ be any subset whose image in Γ/K (×p ) is S. Then
2
BS̃ (pp+1 )K (×p ) = Γ, and by repeated application of Proposition 4.8,
n

BS̃ (pp+1 Cpn−2 )K (×p

)

= Γ.

Thus:
n

diam(Γ/K (×p ) , S) ≤ pp+1 Cpn−2 ≪p plog(Cp )n/ log(p)
n

n

The result follows, since |Γ : K (×p ) | = pp

+1

.

Proof of Theorem 1.3. By Lemma 2.12, we have:
n−1

diam(Γ/ StabΓ (n)) ≤ diam(Γ/K (×p
n

n

The result now follows from |Γ : K (×p ) | = pp
4.1.

5

+1

)

).

; Theorem 1.4 and Corollary

The Gupta-Sidki 3-Group

In this Section we deduce Theorem 1.5 from Theorem 1.4. We shall require
some facts about the lower central series of Γ = Γ(3) , which were established in
[3]. Define the integer sequence
(αn ) by α1 = 1, α2 = 2, αn = 2αn−1 + αn−2
Pn
for n ≥ 3, and set βn = i=1 αi . We have:
√ 
√
1
αn = √ (1 + 2)n − (1 − 2)n ,
2 2
√
√

1
βn = (1 + 2)n+1 + (1 − 2)n+1 − 2 .
4

Theorem 5.1 ([3]). Let X1 , . . . , Xn ∈ {0, 1, 2}. Then:
deg X1 · · · Xn (x1 ) = 1 +
deg X1 · · · Xn (x2 ) = 1 +

n
X

i=1
n
X

Xi αi + αn+1
Xi αi + 2αn+1 .

i=1

Corollary 5.2. For all m ∈ N,
m

K (×3

)

≤ γαm+1 +1 (Γ) ≤ γβm +1 (Γ).

Corollary 5.3. For all m ∈ N,
m

|Γ : γβm +1 (Γ)| = 3(3

+1)/2

.

Proof of Theorem 1.5. For n = 1 there is nothing to prove. Otherwise, let
m ∈ N be such that βm + 1 ≤ n ≤ βm+1 + 1. Then by Corollary 5.2,
m+1

diam(Γ/γn (Γ)) ≤ diam(Γ/K (×3
≪3

log(111)m/ log(3)

≪ nlog(111)/ log(1+

√

)

)

(by Theorem 1.4)
2)

≪ (log|Γ : γβm +1 (Γ)|)log(111)/ log(3) (by Corollary 5.3)

≤ (log|Γ : γn (Γ)|)log(111)/ log(3) .

6

Spectral Gap and Mixing Time

For G a finite group and S ⊆ G a symmetric subset, let AS be the (normalized)
adjacency operator on the Cayley graph Cay(G, S). AS is a self-adjoint operator
of norm 1; let its spectrum be:
1 = λ1 ≥ λ2 ≥ . . . ≥ λ|G| ≥ −1
with the eigenvalue λ1 = 1 corresponding to the constant functionals on G.
More generally, the 1-eigenspace of AS is spanned by the indicator functions of
the connected components of Cay(G, S); in particular 1 > λ2 if and only if S
generates G, and in this case the quantity 1 − λ2 is known as the spectral gap
of the pair (G, S).
The existence of a large spectral gap for a family of Cayley graphs is a matter
of great interest. If a family of finite graphs of bounded valence with vertex sets
of unbounded size possess a spectral gap bounded below by an absolute positive
constant, then the graphs form an expander family. Expander graphs (and
especially expander Cayley graphs) have multifarious applications across pure
mathematics and theoretical computer science [25].
Now let Γ be G or Γ(p) and let (Γi )i be one of the descending sequences
of finite-index normal subgroups from Theorems 1.1-1.5. Cayley graphs of the
quotient groups Γ/Γi do not in general form expander families: for instance if S
is a finite symmetric generating set for Γ, and Si is the image of S in Γ/Γi , then
the spectral gap of Cay(Γ/Γi , Si ) tends to 0 as i → ∞ (this follows from the
fact that Γ is amenable [7] and Γi exhausts Γ). We do however have a weaker
lower bound on the spectral gap of any connected Cayley graph of Γ/Γi , coming
from our upper bounds on diameter and the following general inequality.
Proposition 6.1 ([11] Corollary 3.1). Let G be a finite group and let S be a symmetric generating set. Then the spectral gap of (G, S) is ≥ (|S| diam(G, S)2 )−1 .
Theorems 1.1-1.5 combine with Proposition 6.1 to yield the following bounds
on spectral gaps.

Corollary 6.2. Let S be an arbitrary generating set for the finite group G.
Denote by ǫ(G, S) the spectral gap of the pair (G, S). Let Cp be as in Theorem
1.3.

(i) If G = G/ StabG (n) then ǫ(G, S) = Ω |S|−1 exp(−2 log(35)n) ;

(ii) If G = G/γn (G) then ǫ(G, S) = Ω |S|−1 n−2 log(35)/ log(2) ;

(iii) If G = Γ(p) / StabΓ(p) (n) then ǫ(G, S) = Ωp |S|−1 exp(−2 log(Cp )n) ;

n
(iv) If G = Γ(p) /K (×p ) then ǫ(G, S) = Ωp |S|−1 exp(−2 log(Cp )n) ;
√ 
(v) If G = Γ(3) /γn (Γ(3) ) then ǫ(G, S) = Ω |S|−1 n−2 log(111)/ log(1+ 2) .

A second closely related numerical invariant of finite Cayley graphs is the
mixing time. This is a measure of the time taken for a lazy random walk on
the Cayley graph to approach the uniform distribution. It may be defined as
follows. Let f0 = δe be the Dirac mass at the identity of G. The lazy random
walk on Cay(G, S) is defined by the operator TS = (AS + I)/2, where I is
the identity operator on Cay(G, S), and describes the progress on Cay(G, S)
of a particle which starts at the identity, and which at each step with equal
probability either traverses an edge (chosen uniformly at random) or remains
stationary. Recursively define fl+1 = TS (fl ), the distribution of the walk at
time l. We may consider the walk to be well-mixed when fl is close to the
uniform distribution, in some appropriate norm on the complex functionals on
G. Here we focus on mixing with respect to the ℓ∞ -norm.
Definition 6.3. Let G be a finite group and S be a symmetric generating set.
The ℓ∞ -mixing time of the pair (G, S) is the smallest positive integer l such
that:
fl −

1
|G| χG ∞

≤

1
2|G| .

It may be easily seen that the LHS of the above inequality is a non-increasing
function of l, so that once the random walk reaches its mixing time, it remains
well-mixed thereafter. There is a close relationship between mixing time and
spectral gap.
Proposition 6.4 ([24] Theorem 5.1). Suppose the pair (G, S) has spectral gap
ǫ > 0. Then there exists an absolute constant C > 0 such that the ℓ∞ -mixing
time of (G, S) is at most (C/ǫ) log|G|.
Applying Proposition to the conclusions of Corollary 6.2, we have corresponding bounds on mixing times, as follows.
Corollary 6.5. Denote by µ(G, S) the ℓ∞ -mixing time of the pair (G, S).

(i) If G = G/ StabG (n) then µ(G, S) = O |S| exp(log(2450)n) ;

(ii) If G = G/γn (G) then µ(G, S) = O |S|n2 log(35)/ log(2)+1 ;


(iii) If G = Γ(p) / StabΓ(p) (n) then µ(G, S) = Op |S| exp(log(pCp2 )n) ;

n
(iv) If G = Γ(p) /K (×p ) then µ(G, S) = Op |S| exp(log(pCp2 )n) ;
√ 
(v) If G = Γ(3) /γn (Γ(3) ) then µ(G, S) = O |S|nlog(36963)/ log(1+ 2) .

7

Growth in Branch Groups

Given a finitely generated group G and a finite generating set S ⊆ G, let
f(G,S) (n) = |BS (n)| be the growth function. Although for a given group G, the
function f(G,S) may vary according to the generating set S, it only does so up
to an appropriate notion of equivalence of functions. As such, we may speak
without ambiguity about groups of polynomial growth, exponential growth and
so on (see [10] Chapters VI-VII).
One of the key sources of interest in branch groups is the fact that they
include many examples of groups with exotic growth behaviour. In particular,
G has intermediate growth, that is: growth faster than any polynomial function
but slower than any exponential function.
The following elementary fact exhibits a relationship between growth and
diameter.
Lemma 7.1. Let F be a finite group, and let φ : G → F be an epimorphism.
Then:
f(G,S) (diam(F, φ(S))) ≥ |F |.
(26)
This inequality suggests the following definition, which is made by analogy
with that of the diameter of a finite group. Let fG (n) be the minimal value
of f(G,S) (n), as S ranges over all finite generating subsets of G. From (26) we
immediately obtain:
fG (diam(F )) ≥ |F |.
(27)
The relationship between growth and diameter can be exploited to yield information about both. For instance, from Theorems 1.2 and 1.4 we have the
following.
Corollary 7.2. There exist constants α(p) > 0 such that:
fG (n) ≫ exp(α(2)nβ(G) ) and fΓ(p) (n) ≫p exp(α(p)nβ(Γ(p) ) ),
where β(G) = log(2)/ log(35) ≈ 0.195 and β(Γ(p) ) = log(p)/ log(C2 (p)) (here
C2 (p) is as in Theorem 1.3).
The bounds in Corollary 7.2 are not the best known: a slight modification of an argument of Grigorchuk [17] shows that if G is any finitely generated residually
√ virtually nilpotent group, then either G is virtually nilpotent or
fG (n) ≥ exp( n) (see [4]). In particular the latter conclusion applies to G and
Γ(p) . It is however possible that improvements upon the diameter bounds in
Theorems 1.2 and 1.4 and their corollaries could yield new lower bounds on fG
and fΓ(p) .

Conversely, known upper bounds on the growth translate into lower bounds
on the diameters of finite quotients. In the case of G, the best upper bound on
the growth is the following result of Bartholdi.
Theorem 7.3 ([16]). Let a, b, c, d ∈ G be as in subsection 2.2.1 and let S =
{a, b, c, d}. Then:
f(G,S) (n) ≪ exp(nβ ),
where β =

log(2)
log(2)−log(η)

≈ 0.768, for η the real root of X 3 + X 2 + X = 2.

Corollary 7.4. There exist absolute constants C, C ′ > 0 such that:
diam(G/ StabG (n)) ≥ C(log|G : StabG (n)|)1/β ;
diam(G/γn (G)) ≥ C ′ (log|G : γn (G)|)1/β
where β is as in Theorem 7.3.
Corollary 7.4 places a limit on the extent to which the constant log(35)/ log(2)
appearing in Theorems 1.1 and 1.2 might be reduced (though it is almost certainly not sharp). It is unclear at this time whether the constant 1/β ≈ 1.303
in Corollary 7.4 could be close to sharp.

Acknowledgements
I would like to thank Laurent Bartholdi and Alejandra Garrido for illuminating
discussions. Parts of this work were completed while the author was a fellowcommoner at Trinity Hall, Cambridge. I would like to thank the fellows of the
College for providing me with a warm welcome and pleasant working conditions.

References
[1] L. Babai, Á. Seress. On the Diameter of Permutation Groups. Europe J.
Combinatorics, Vol. 13 (1992) 231–243
[2] L. Bartholdi. The Growth of Grigorchuk’s Group. Internat. Math. Res.
Notices 20 (1998) 1049–1054
[3] L. Bartholdi. Lie Algebras and Growth in Branch Groups. Pacific Journal
of Mathematics, Vol. 218, No. 1 (2005) 241–282
[4] L. Bartholdi. Growth of Groups and Wreath Products. arXiv:1512.07044
[5] L. Bartholdi, R. Grigorchuk. Lie methods in growth of groups and groups of
finite width. In Computational and geometric aspects of modern algebra,
London Math. Soc. Lecture Note Series 275, Cambridge University Press
(2000), 1–27
[6] L. Bartholdi, R. Grigorchuk, Z. Šuniḱ. Branch Groups. Handbook of algebra, Vol. 3, North-Holland, Amsterdam (2003), 989–1112

[7] L. Bartholdi, V.A. Kaimanovich, V.V. Nekrashevych. On Amenability of
Automata Groups. Duke Math. J., 154 Issue 3 (2010) 575–598.
[8] H. Bradford. New Uniform Diameter Bounds in Pro-p Groups.
arXiv:1410.3007 []
[9] H. Bradford. A Potent Solovay-Kitaev Procedure. In preparation.
[10] P. de la Harpe. Topics in Geometric Group Theory. University of Chicago
Press (2000)
[11] P. Diaconis, L. Saloff-Coste. Comparison techniques for random walk on
finite groups. Ann. Probab. 21, Issue 4 (1993), 2131–2156.
[12] O. Dinai. Diameters of Chevalley groups over local rings. Archiv der Mathematik 99, Issue 5 (2012) 417–424.
[13] J. Driscoll, M. Furst. Computing short generator sequences. Information
and Computation 72 (1987) 117–132
[14] A. Gamburd, M. Shahshahani. Uniform diameter bounds for some families
of Cayley graphs. Internat. Math. Res. Notices 71 (2004) 3813–3824
[15] A. Garrido. Abstract commensurability and the Gupta-Sidki group.
arXiv:1310.0493 []
[16] R. Grigorchuk. On Burnsides problem on periodic groups. Funktsional.
Anal. i Prilozhen. 14 (1980), no. 1, 53-54, English translation: Functional
Anal. Appl. 14 (1980), 41–43
[17] R. Grigorchuk. On the Hilbert-Poincaré series of graded algebras that are
associated with groups. Math. USSR-Sb. 66 (1990) no. 1, 211–229
[18] R. Grigorchuk. Just infinite branch groups. In: New horizons in prop groups (Markus P. F. du Sautoy Dan Segal and Aner Shalev, eds.),
Birkhäuser Boston, Boston, MA, 2000, pp. 121–179
[19] N. Gupta, S. Sidki. On the Burnside problem for periodic groups. Math.
Z., 182(3) (1983) 385–388
[20] H.A. Helfgott. Growth in groups: ideas and perspectives. Bull. Amer. Math.
Soc. 52 (2015), 357–413
[21] H.A. Helfgott, Á. Seress. On the diameter of permutation groups.
arXiv:1109.3550 (2011).
[22] L. Kaloujnine. La structure des p-groupes de Sylow des groupes symétriques
finis. Ann. École Norm. Sup. (3) 65 (1948), 239276.
[23] D. Kornhauser, G. Miller, P. Spirakis. Coordinating pebble motion on
graphs, the diameter of permutation groups, and applications. MS thesis.
M.I.T., Dept. of Electrical Engineering and Computer Science, 1984.

[24] L. Lovász. Random walks on graphs: a survey. Combinatorics, Paul Erdös
is Eighty 2 (1993), 1–46.
[25] A. Lubotzky. Expander Graphs in Pure and Applied Mathematics. Bull.
Amer. Math. Soc. 49, Issue 1 (2012), 113-162.
[26] A.V. Rozhkov. Lower central series of a group of tree automorphisms. Mat.
Zametki Vol. 60, No. 2 (1996) 225–237
[27] S. Sidki. On a 2-generated infinite 3-group: subgroups and automorphisms.
J. Algebra, 110 No. 1 (1987) 24–55
[28] T. Tao. Expansion in finite simple groups of Lie type. AMS Graduate Studies in Mathematics 164, Providence, Rhode Island, 2015
[29] J.S. Wilson. Groups with every proper quotient finite. Math. Proc. Cambridge Philos. Soc. 69 (1971),373–391
H. Bradford, Universität Göttingen, Germany
E-mail address: henry.bradford@mathematik.uni-goettingen.de

