PORTRAIT GROWTH IN CONTRACTING, REGULAR BRANCH
GROUPS

arXiv:1710.02902v1 [] 9 Oct 2017

ZORAN ŠUNIĆ AND JONE URIA-ALBIZURI
Abstract. We address a question of Grigorchuk by providing both a system
of recursive formulas and an asymptotic result for the portrait growth of the
first Grigorchuk group. The results are obtained through analysis of some features of the branching subgroup structure of the group. More generally, we
provide recursive formulas for the portrait growth of any finitely generated,
contracting, regular branch group, based on the coset decomposition of the
groups that are higher in the branching subgroup structure in terms of the
lower subgroups. Using the same general approach we fully describe the portrait growth for all non-symmetric GGS-groups and for the Apollonian group.

1. Introduction
Regular branch groups acting on rooted trees have been extensively studied since
the 1980s. The interest in these groups is due to their remarkable properties. For
instance, some of the groups in this class provide counterexamples to the General
Burnside Problem, many of them are amenable but not elementary amenable, and
the first example of a group of intermediate word growth was of this type. The initial
examples, constructed in the early 1980s, were the Grigorchuk 2-groups [Gri80,
Gri84] and the Gupta-Sidki p-groups [GS83]. Many other examples and different
generalizations have been introduced since then.
The notion of word growth for a finitely generated group was introduced by
A.S. Švarc [Šva55] and later, independently, by J. Milnor [Mil68a, Mil68b]. Given
a finitely generated group, one can define the word metric with respect to a finite
generating set. It is natural to ask what is the word growth function of a particular
group, that is, what is the number of elements that can be written as words up
to a given length (equivalently, what is the volume of the ball of a given radius
in the word metric). A lot of work has been done in this direction. For instance,
it is known that groups of polynomial growth are exactly the virtually nilpotent
groups [Gro81]. Since the free group of rank at least 2 has exponential growth,
the word growth of every finitely generated group is at most exponential. In 1968,
Milnor [Mil68c] asked if every finitely generated group has either polynomial or
exponential growth, and Grigorchuk [Gri83, Gri84] showed in the early 1980s that
groups of intermediate growth exist. In particular, the growth of the first Grigorchuk group [Gri80], introduced in 1980 as an example of a Burnside 2-group, is
superpolynomial, but subexponential.
The first Grigorchuk group is a self-similar, contracting, regular branch group,
and so are the Gupta-Sidki p-groups. The study of such groups often relies on
the representation of their elements through portraits. For instance, the known
estimate [Bar98] of word growth for the first Grigorchuk group is based on an
estimate of the number of portraits of elements of given length. Thus, in the
2010 Mathematics Subject Classification. Primary 20E08.
J. Uria-Albizuri acknowledge financial support from the Spanish Government, grants
MTM2011-28229-C02 and MTM2014-53810-C2-2-P, and from the Basque Government, grants
IT753-13, IT974-16 and the predoctoral grant PRE-2014-1-347.
1

2

ZORAN ŠUNIĆ AND JONE URIA-ALBIZURI

context of self-similar, contracting groups acting on regular rooted trees, it is of
interest to study the portrait growth of a group with respect to a finite generating
set. The necessary definitions are given in Section 2, but let us provide here a
rough description. Given a finitely generated group acting on a rooted tree, one
can consider the action of the group on the subtrees below each vertex of the tree.
If the action on such subtrees is always given by elements of the group itself, the
group is called self-similar. Moreover, if the elements describing the action at the
subtrees on each level are getting shorter (with respect to the word metric) with the
level, with finitely many exceptions, the group is said to be contracting. Thus, in a
finitely generated, contracting group G, there is a finite set M such that, for every
element g in G, there exists a level such that all elements describing the action of g
on the subtrees below that level come from the finite set M. The first level where
this happens is called the depth of the element g (with respect to M), a concept
introduced by Sidki [Sid87]. In this setting, the portrait growth function (growth
sequence) counts the number of elements up to a given depth and one may ask
what is the growth rate of such a function. This question was specifically raised by
Grigorchuk [Gri05] for the first Grigorchuk group.
We provide a system of recursive formulas for the portrait growth of the first
Grigorchuk group (see Theorem 4.2) and the following asymptotic result.
Theorem 1.1. There exists a positive constant γ such that the portrait growth
sequence {an }∞
n=0 of the first Grigorchuk group G satisfies the inequalities
n
1 γ2n
e
≤ an ≤ 4eγ2 ,
4
for all n ≥ 0. Moreover, γ ≈ 0.71.
We note here that the recursive formulas from Theorem 4.2, together with the
results of Lemma 3.2, may be used to estimate γ with any desired degree of accuracy.
More generally, we provide recursive formulas (see (2)) for the portrait growth
sequence of any finitely generated, contracting, regular branch group. The formulas
are directly based on the branching subgroup structure of the group.
As a further application, we also study the portrait growth for all non-symmetric
GGS-groups and for the Appollonian group and, in each case, we resolve the obtained recursion and provide a straightforward description of the portrait growth.
Theorem 1.2. Let G be a GGS-group defined by a non-symmetric vector e ∈ Fp−1
.
p
The portrait growth sequence of G {an }∞
is
given
by
n=0
a0 = 1 + 2(p − 1)

n−1

an = p(x1 + (p − 1)y1 )p

,

where x1 and y1 are the number of solutions in Fp of
((n0 , . . . , np−1 )C(0, e)) ⊙ (n0 , . . . , np−1 ) = (0, . . . , 0),

with n0 + · · · + np−1 = 0 and n0 + · · · + np−1 = 1, respectively.

For instance, for the so called Gupta-Sidki 3-group, which corresponds to the
GGS-group defined by e = (1, −1) with p = 3, the portrait growth sequence is
n−1
given by a0 = 5 and an = 3 · 93 , for n ≥ 1.
Theorem 1.3. The portrait growth sequence {an }∞
n=0 of the Apollonian group is
given by
n
n
3n −1
1  √ 3
.
an = 3 2 · 7 3 = √ 7 3
3

PORTRAIT GROWTH IN CONTRACTING, REGULAR BRANCH GROUPS

3

Note that, in all three cases, the portrait growth is doubly exponential even
though the word growth function is intermediate for the first Grigorchuk group,
mostly unknown for the GGS-groups, and exponential for the Apollonian group. We
conjecture that the portrait growth is doubly exponential for all finitely generated,
contracting, regular branch groups.
The paper is organized as follows: in Section 2 we provide the basic definitions regarding groups acting on regular rooted trees and we describe a procedure
yielding recursive relations for the portrait growth sequence of a finitely generated,
contracting, regular branch group. In Section 3 we state some useful observations
about sequences of doubly exponential growth. Finally in Sections 4, 5 and 6 we
describe the cases of the first Grigorchuk group, non-symmetric GGS-groups, and
the Apollonian group.
2. Portrait growth sequence on a regular branch contracting
group
A regular rooted tree T is a graph whose vertices are the words over a finite
alphabet X, and two vertices u and v are joined by an edge if v = ux for some
x ∈ X. The empty word, denoted ∅, represents the root of the tree and the tree
is called d-adic if X consists of d elements. The vertices represented by words of
a fixed length constitute a level, that is, the words of length n constitute the nth
level of the tree. The ternary rooted tree based on X = {1, 2, 3} is displayed in
Figure 1.
∅

1

11

12

2

..
.

13

21

22

3

..
.

23

31

32

..
.

33

Figure 1. A ternary rooted tree
An automorphism of the tree T is a permutation of the vertices preserving incidence. Such a permutation, by necessity, must also preserve the root and all
other levels of the tree. The automorphisms of T form the automorphism group
Aut T under composition. A group acting faithfully on a regular rooted tree may
be regarded as a subgroup of Aut T . Every automorphism g can be fully described
by indicating how g permutes the d vertices at level 1 below the root, and how it
acts on the subtrees hanging from each vertex at level 1. Observe that each subtree hanging from a vertex is isomorphic to the whole tree T , so that the following
description makes sense. Namely, we decompose any automorphism g ∈ Aut T as

(1)

g = (g1 , . . . , gd )α,

where α ∈ Sd is the permutation describing the action of g on the d vertices at
level 1, and each gi ∈ Aut T describes the action of g on the ith subtree below
level 1, for i = 1, . . . , d. This process can be repeated at any level, and the element

4

ZORAN ŠUNIĆ AND JONE URIA-ALBIZURI

describing the action of g at a particular vertex u is called the section of g at the
vertex u. Given a group G ≤ Aut T we say that G is self-similar if the sections of
each element in G belong again to the group G.
We say that a self-similar group G ≤ Aut T is contracting if there is a finite
set M of elements in G such that, for every element g, there exists some level n
such that all sections of g at the vertices at and below the nth level belong to
M. The smallest set M among such finite sets is called the nucleus of G and we
denote it by N (G) (or by N , when G is clear from the context). The definition of
a contracting group, in this form, is due to Nekrashevych [Nek05].
For any finitely generating group G, generated by a finite symmetric set S = S −1 ,
we define the word length of g, denoted ∂(g), to be the length of the shortest word
over the alphabet S representing the element g. A self-similar group G generated
by a finite symmetric set S is contracting if and only if there exist constants λ < 1
and C ≥ 0, and level n such that for every g ∈ G and every vertex u on level n
∂(gu ) ≤ λ∂(g) + C.
Note that, if ∂(g) >

C
1−λ ,

then
∂(gu ) ≤ λ∂(g) + C < ∂(g),

that is, the sections gu are strictly shorter than g. Thus, the elements that possibly
have no shortening in their sections are the ones that belong to the finite set


C
g ∈ G | ∂(g) ≤
.
1−λ
In particular, the nucleus is part of this finite set. The metric approach to contracting groups precedes the nucleus definition of Nekrashevych and was used by
Grigorchuk in his early works on families of groups related to the first Grigorchuk
group [Gri80, Gri84]. Nekrasevych [Nek05] showed that he nucleus definition and
the metric definition are equivalent in the case of finitely generated groups.
Given a contracting group G acting on a d-ary tree and an element g in G,
the nucleus portrait is a finite tree, whose interior vertices are decorated by
permutations from Sd and whose leaves are decorated by elements of the nucleus,
describing the action of the element g. The portrait is constructed recursively as
follows. If g is an element of the nucleus the tree consist only of the root decorated
by g. If g is not an element of the nucleus, then we consider its decomposition (1).
The portrait of g is obtained by decorating the root by the permutation α and by
attaching the portraits of the section g1 , . . . , gd at the corresponding vertices of the
first level. Since G is contracting this recursive procedure must end at some point,
and we obtain the portrait of the element g. (A concrete example in the case of
the first Grigorchuk group is provided in Figure 2.)
Let us denote by d(g) the depth of the portrait of an element g ∈ G, that is,
the length of the largest ray from the root to a leaf in the portrait of g. For each
n ∈ N, the set {g ∈ G | d(g) ≤ n} is finite, and the function a : N → N given by
a(n) = |{g ∈ G | d(g) ≤ n}|
is called the portrait growth function, or portrait growth sequence, of G (with
respect to the nucleus).
We now focus on regular branch groups, since their structure gives us a way to
describe the portrait growth function of a contracting group in a recursive way.
Given G ≤ Aut T , the elements of G fixing level n form a normal subgroup of
G, called the nth level stabilizer and denoted stG (n). For every n ∈ N, we have an

PORTRAIT GROWTH IN CONTRACTING, REGULAR BRANCH GROUPS

5

injective homomorphism
ψn : stG (n) −→ Aut T × · · · × Aut T ,
|
{z
}
dn

sending each element g ∈ stG (n) to the dn -tuple consisting of the sections of g at
n
level n. Note that, if the group is self-similar, ψn (stG (n)) ≤ G × .d. . × G. For
simplicity we write ψ = ψ1 . A group G ≤ Aut T is level transitive if it acts
transitively on every level of the tree. A level transitive group G ≤ Aut T is called
regular branch if there exists a normal subgroup K of finite index in G such that
ψ(K ∩ stG (1)) ≥ K × · · · × K.
Observe that, since K is of finite index in G, the group ψ −1 (K × · · · × K) has finite
index in K ∩ stG (1), and hence in G.
We now describe a procedure yielding recursive formulas for the portrait growth
of any finitely generated, contracting, regular branch group G, branching over its
normal subgroup K of index k. Consider a left transversal T = {t1 , . . . , tk } for K
in G and denote by pn (ti ) = |{g ∈ ti K | d(g) ≤ n}| and pn = |{g ∈ G | d(g) ≤ n}|
the sizes of the sets consisting of the elements of depth at most n in the coset ti K
Pk
and in the whole group G, respectively. We have pn = i=1 pn (ti ).
Let S = {s1 , . . . , sℓ } be a left transversal for ψ −1 (K × · · · × K) in K. For
i = 1, . . . , k and j = 1, . . . , ℓ we have
ti sj = (g1 , . . . , gd )α ≡ (tij1 , . . . , tijd )α

(mod K × · · · × K),

for some tijr ∈ T , r = 1, . . . , d. Thus, for n ≥ 0,
(2)

pn+1 (ti ) =

ℓ
X

pn (tij1 ) . . . pn (tijd )

j=1

(3)

pn+1 =

k X
ℓ
X

pn (tij1 ) . . . pn (tijd ).

i=1 j=1

The initial conditions p0 (ti ), i = 1, . . . , k, for the recursive formulas can be
obtained simply by counting the members of the nucleus that come from the corresponding coset, while p0 is the size of the nucleus.
The following observation will be helpful later on. A rooted automorphism is an
automorphisms whose sections, other than at the root, are trivial.
Lemma 2.1. Let G be a finitely generated, contracting, regular branch group
branching over the subgroup K and let T be a transversal of K in G. If a ∈ G is a
rooted automorphism then, for every t ∈ T and n ≥ 1, we have
pn (t) = pn (at) = pn (ta) = pn (ta ).
Proof. Observe that for every g ∈ tK and u ∈ Ln , n ≥ 1, we have
(ag)u = au ga(u) = ga(u) ,
(ga)u = gu ag(u) = gu ,
(g a )u = ga−1 (u) .
Thus, there are bijections between the sets of elements of depth n in tK, atK, taK
and ta K.


6

ZORAN ŠUNIĆ AND JONE URIA-ALBIZURI

3. Doubly exponential growth
We begin by defining sequences of doubly exponential growth.
Definition 3.1. A sequence of positive real numbers {an }n∈N grows doubly exponentially if there exist some positive constants α, β and some γ, d > 1 such that
n

n

αeγd ≤ an ≤ βeγd ,

for every n ∈ N.

In order to show that the portrait growth sequences in our examples are doubly
exponential we need the following auxiliary result.
∞

Lemma 3.2. Let {an }n=0 be a sequence of positive real numbers and d a constant
with d > 1. The following are equivalent.
(i) There exist positive constants A and B such that, for all n ≥ 0,
Aadn ≤ an+1 ≤ Badn .

(ii) There exist positive constants α, β, and γ such that, for all n ≥ 0,
n

n

αeγd ≤ an ≤ βeγd .

∞
Moreover, in case (i) is satisfied, the sequence lndann n=0 is convergent, we may
set
ln an
γ = lim
n→∞ dn
−M
and α and β can be chosen to be e
and eM , respectively, where
1
M=
max{| ln A|, | ln B|}.
d−1

The error of the approximation γ ≈ γn =

ln an
dn

is no greater than M/dn .

Proof. (ii) implies (i). We have, for all n,
β  γdn d
β
α d
α  γdn d
γdn+1
γdn+1
βe
=
αe
≤
a
≤
βe
=
αe
≤ d adn .
a
≤
n+1
n
d
d
d
β
β
α
α
≤ ln B, and therefore
(i) implies (ii). For all i, we have ln A ≤ ln aai+1
d
i

ln

ai+1
≤ max{| ln A|, | ln B|} = (d − 1)M.
adi

For n ≥ 0, let
rn =

∞
X
ai+1
1
ln d .
i+1
d
ai
i=n

The series rn isPabsolutely convergent and we have the estimate |rn | ≤ M/dn , by
M
1
comparison to ∞
i=n di+1 (d − 1)M = dn .
Let
∞
X
1
ai+1
γ = ln a0 + r0 = ln a0 +
ln d .
i+1
d
ai
i=0
Since r0 is a convergent series, γ is well defined. We have
1 a1
γ = ln a0 + r0 = ln a0 + ln d + r1
d a0
a2
ln a1
1
ln a1
+ r1 =
+ 2 ln d + r2
=
d
d
d
a1
ln a2
= 2 + r2 = . . .
d

PORTRAIT GROWTH IN CONTRACTING, REGULAR BRANCH GROUPS

7

Thus, for all n,
ln an
+ rn .
dn

∞
Since |rn | ≤ M/dn , we see that the sequence lndann n=0 converges to γ. Moreover,
the inequalities γ − M/dn ≤ lndann ≤ γ + M/dn yield
γ=

n

n

e−M eγd ≤ an ≤ eM eγd .



We end this section with a simple combinatorial observation that shows that an
upper bound of the form required in condition (i) of the lemma always exists for
regular branch groups.
Lemma 3.3. Let G be a finitely generated, contracting, regular branch group
acting on the d-adic tree and let {an }n≥0 be the portrait growth sequence of G.
Then
an+1 ≤ |G : stG (1)|adn , for n ≥ 0.
Proof. Since every element of depth at most n + 1 has sections at the first level
that have depth at most n, the number of possible decorations at level 1 and below
for portraits of depth at most n + 1 is at most adn . On the other hand, the number
of possible labels at the root is |G : stG (1)|, and we obtain the inequality.

4. Portrait growth in the first Grigorchuk group
Denote by G the first Grigorchuk group, introduced in [Gri80]. In his treatise [Gri05] on solved and unsolved problems centered around G, Grigorchuk asked
what is the growth of the sequence counting the number of portraits of given size
in G (Problem 3.5).
The first Grigorchuk group is defined as follows.
Definition 4.1. Let T be the binary tree. The first Grigorchuk group G is the
group generated by the rooted automorphism a permuting the two subtrees on
level 1, and by b, c, d ∈ stG (1), where b, c and d are defined recursively by
ψ(b) = (a, c)
ψ(c) = (a, d)
ψ(d) = (1, b)
Already in his early works in 1980s Grigorchuk observed that G is contracting
with nucleus N (G) = {1, a, b, c, d}. Since G is a contracting group, its elements have
well defined portraits, which are finite decorated trees. For instance, the portrait
of the element bacac is provided in Figure 2.
Grigorchuk also showed that G is a regular branch group, branching over the
subgroup K = h[a, b]iG of index |G : K| = 16. An accessible account can be found
in Chapter VIII of [dlH00]. A transversal for K in G is given by
T = { 1, d, ada, dada, a, ad, da, dad, b, c, aca, cada, ba, ac, ca, cad }.

and a transversal for ψ −1 (K × K) in K is given by

S = {1, abab, (abab)2, baba}.

Theorem 4.2. The portrait growth sequence {an }∞
n=0 of the first Grigorchuk group
G is given recursively by
a0 = 5
an = 2xn + 4yn + 2zn + 2Xn + 4Yn + 2Zn , for n ≥ 1,

8

ZORAN ŠUNIĆ AND JONE URIA-ALBIZURI

()

()

(1 2)

1

b

(1 2)

c

d

a

Figure 2. portrait of the element bacac

where xn , yn , zn , Xn , Yn , and Zn , for n ≥ 1, satisfy the system of recursive relations
xn+1 = x2n + 2yn2 + zn2 ,
yn+1 = xn Yn + Yn zn + Xn yn + yn Zn ,
zn+1 = Xn2 + 2Yn2 + Zn2
Xn+1 = 2xn yn + 2yn zn ,
Yn+1 = xn Xn + 2yn Yn + zn Zn ,
Zn+1 = 2Xn Yn + 2Yn Zn ,

with initial conditions

x1 = y1 = z1 = Y1 = 1,
X1 = 2,
Z1 = 0.
Proof. Denote by pn (t) the number of portraits of depth no greater than n in Γ
that represent elements in the coset tK.
By Lemma 2.1, we have

(4)

pn+1 (t) = pn+1 (at) = pn+1 (ta ) = pn+1 (ta), for n ≥ 0, t ∈ T.

Thus we only need to exhibit recursive formulas for the 6 coset representatives in
the set {1, c, dada, b, d, cada}. We have

PORTRAIT GROWTH IN CONTRACTING, REGULAR BRANCH GROUPS

ψ(1) = (1, 1)

ψ(abab) = (ca, ac)

2

ψ((abab) ) = (dada, dada)

ψ(baba) = (ac, ca)

ψ(c) = (a, d)

ψ(cabab) = (aca, cad)

2

ψ(c(abab) ) = (dad, ada)
ψ(dada) = (b, b)
2

ψ(dada(abab) ) = (cada, cada)

9

ψ(cbaba) = (c, ba)
ψ(dadaabab) = (da, ad)
ψ(dadababa) = (ad, da)

ψ(b) = (a, c)

ψ(babab) = (aca, dad)

2

ψ(b(abab) ) = (dad, aca)

ψ(bbaba) = (c, a)

ψ(d) = (1, b)

ψ(dabab) = (ca, ad)

2

ψ(d(abab) ) = (dada, cada)
ψ(cada) = (ba, d)
2

ψ(cada(abab) ) = (cad, ada)

ψ(dbaba) = (ac, da)
ψ(cadaabab) = (ada, cad)
ψ(cadababa) = (d, ba),

where the sections are already written modulo K by using representatives in T (the
spacing into 6 groups of 4 indicates how each of the 6 cosets of K with representatives 1, c, dada, b, d, and cada splits into 4 cosets of K × K).
Thus, for n ≥ 0,
pn+1 (1) = pn (1)2 + 2pn (ac)pn (ca) + pn (dada)2 ,

pn+1 (c) = pn (a)pn (d) + pn (dad)pn (ada) + pn (c)pn (ba) + pn (aca)pn (cad),
pn+1 (dada) = pn (b)2 + 2pn (ad)pn (da) + pn (cada)2
(5)

pn+1 (b) = 2pn (a)pn (c) + 2pn (dad)pn (aca),
pn+1 (d) = pn (1)pn (b) + pn (ac)pn (da) + pn (ca)pn (ad) + pn (dada)pn (cada),

pn+1 (cada) = 2pn (d)pn (ba) + 2pn (ada)pn (cad),
with initial conditions
p0 (1) = p0 (a) = p0 (b) = p0 (c) = p0 (d) = 1,
p0 (t) = 0, for t ∈ T \ {1, a, b, c, d}.
Direct calculations, based on (5), give
p1 (b) = 2
p1 (cada) = 0
p1 (t) = 1, for t ∈ {1, c, d, dada}.

If we denote, for n ≥ 1,

xn = pn (1) = pn (a),
yn = pn (c) = pn (ac) = pn (aca) = pn (ca),
zn = pn (dada) = pn (dad),

Xn = pn (b) = pn (ba),
Yn = pn (d) = pn (ad) = pn (ada) = pn (da),
Zn = pn (cada) = pn (cad)
we obtain, for n ≥ 1,
an = 2xn + 4yn + 2zn + 2Xn + 4Yn + 2Zn ,

10

ZORAN ŠUNIĆ AND JONE URIA-ALBIZURI

where xn , yn , zn , Xn , Yn , and Zn satisfy the recursive relations and initial conditions as claimed, which follows from (5).

Theorem 4.3. There exists a positive constant γ such that the portrait growth
sequence {an }∞
n=0 of the first Grigorchuk group G satisfies the inequalities
n
1 γ2n
e
≤ an ≤ 4eγ2 ,
4
for all n ≥ 0. Moreover, γ ≈ 0.71.

Proof. Following Lemma 3.2, we first determine positive constants A an B such
that for each n ∈ N we have
Aa2n ≤ an+1 ≤ Ba2n .

By Lemma 3.3 we may take B = |G : stG (1)| = 2.
For the other inequality, we need a constant A such that
an+1 − Aa2n ≥ 0.

Using Theorem 4.2 we may express, for n ≥ 1, both an+1 and an in terms of
xn , yn , zn , Xn , Yn , Zn and if we set A = 14 , we obtain
an+1 − Aa2n = (xn − zn + Xn − Zn )2 ≥ 0.
1
1
Since M = d−1
max{| ln A|, | ln B|} = 2−1
max{| ln 1/4|, | ln 2|} = ln 4, we obtain
−M
M
α=e
= 1/4 and β = e = 4. Finally, the approximation of γ ≈ 0.71 can be
calculated by using the recursion given by Theorem 4.2 and Lemma 3.2.


5. Portrait growth in non-symmetric GGS-groups
The GGS-groups (named after Grigorchuk, Gupta, and Sidki) form a family of
groups generalizing the Gupta-Sidki examples [GS83] (which were in turn inspired
by the first Grigorchuk group [Gri80]).
Definition 5.1. For a prime p, p ≥ 3, and a vector e = (e1 , . . . , ep−1 ) ∈ Fp−1
,
p
the GGS-group defined by e is the group of p-ary automorphisms generated by
the rooted automorphism a, which permutes the subtrees on level 1 according to
the permutation (1 . . . p), and the automorphism b ∈ st(1) defined recursively by
b = (b, ae1 , . . . , aep−1 ).
Set S = S −1 = {a, a2 , . . . , ap−1 , b, . . . , bp−1 }. It is easy to see that G is contracting with nucleus N (G) = S ∪ {1}.
Let


0
e1 e2
. . . ep−1
ep−1 0 e1
. . . ep−2 


C(0, e) =  .
.
.
.. 
..
..
..
 ..
.
. 
e1
e2 . . . ep−1
0
be the circulant matrix of the vector (0, e1 , . . . , ep−1 ). We say that the vector
e = (e1 , . . . , ep−1 ) is symmetric if ei = ep−i , for i = 1, . . . , p − 1 (that is, the vector
is symmetric precisely when the corresponding circulant matrix is symmetric).
.
Theorem 5.2. Let G be a GGS-group defined by a non-symmetric vector e ∈ Fp−1
p
The portrait growth sequence {an }∞
of
G
is
given
by
n=0
a0 = 1 + 2(p − 1)

n−1

an = p(x1 + (p − 1)y1 )p

,

PORTRAIT GROWTH IN CONTRACTING, REGULAR BRANCH GROUPS

11

where x1 and y1 are the number of solutions in Fpp of
((n0 , . . . , np−1 )C(0, e)) ⊙ (n0 , . . . , np−1 ) = (0, . . . , 0),
with n0 + · · · + np−1 = 0 and n0 + · · · + np−1 = 1, respectively, where ⊙ denotes
the product by coordinates.
Proof. Fernández-Alcober and Zugadi-Reizabal [FAZR14] showed that a GGS-group
defined by a non-symmetric vector is regular branch over G′ , whose index in G is
p2 . A left-transversal for G′ in G is given by
T = {ai bj | i, j = 0, . . . , p − 1}.

For each pair (i, j) ∈ {0, . . . , p − 1}2 denote by pn (i, j) the number of portraits
of depth no greater than n in the coset ai bj G′ .
We have
2

ai bj ≡ ai bn0 (ba )n1 (ba )n2 . . . (ba
where j = n0 + · · · + np−1 in Fp . And then,

ai bj ≡ ai (ai0 bn0 , . . . , aip−1 bnp−1 )

p−1

)np−1

(mod G′ ),

(mod G′ × · · · × G′ ),

where (i0 , . . . , ip−1 ) = (n0 , . . . , np−1 )C(0, e). We obtain that,
X

pn+1 (i, j) =

n0 +···+np−1 =j

p−1
Y

pn (ir , nr ).

r=0

Observe that the decomposition of pn+1 (i, j) does not depend on i, so we can
set pn+1 (i, j) = Pn+1 (j) and we have
(6)

X

pn+1 (j) =

n0 +···+np−1 =j

p−1
Y

pn (ir , nr ),

r=0

Pp−1
and then, for n ≥ 1, we have an = p j=0 pn (j), where we multiply by p because
we have to sum for each i = 0, . . . , p − 1.
Since the nucleus is S ∪ {1}, the initial conditions are the given by
p0 (0, 0) = p0 (i, 0) = p0 (0, j) = 1 for i, j ∈ {1, . . . , p − 1},
p0 (i, j) = 0 otherwise.

In other words, p0 (i, j) = 1 if ij = 0 and p0 (i, j) = 0, otherwise. By (6), p1 (0) is
the number of solutions in Fpp of
(7) (n0 , . . . , np−1 )C(0, e) ⊙ (n0 , n1 , . . . , np−1 ) = (i0 n0 , . . . , ip−1 np−1 ) = (0, . . . , 0),
with n0 + · · · + np−1 = 0, and p1 (j) is the number of solutions of the same equation,
but with n0 + · · · + np−1 = j.
We prove by induction that pn (1) = pn (j), for n ≥ 1 and j 6= 0. Observe that,
for n = 1, if (n0 , . . . , np−1 ) is a solution of (7), with n0 + · · · + np−1 = 1, then
(jn0 , . . . , jnp−1 ) is also a solution, but with n0 + · · · + np−1 = j. Similarly, if we
multiply a solution that sums up to j by the multiplicative inverse j −1 of j in Fp , we
obtain a solution that sums up to 1. Thus, there is a bijection between the solutions
and hence p1 (1) = p1 (j), for j 6= 0. Let us now assume that pn (1) = pn (j), for
n ≥ 1 and j 6= 0, and let us prove the equality for n + 1. By (6) and the assumption
that n ≥ 1, we have that pn (i, j) = pn (j) and
pn+1 (j) =

X

n0 +···+np−1 =j

p−1
Y
r=0

pn (nr ).

12

ZORAN ŠUNIĆ AND JONE URIA-ALBIZURI

By the inductive hypothesis we have pn (nr ) = pn (j −1 nr ) (this is true regardless of
whether nr is 0 or not). Thus,
pn+1 (j) =

p−1
Y

X

n0 +···+np−1 =j

pn (nr ) =

n0 +···+np−1 =j

r=0

X

=

j −1 n0 +···+j −1 np−1 =1

X

p−1
Y

pn (j −1 nr )

r=0

X

pn (j −1 nr ) =

r=0

p−1
Y

n′0 +···+n′p−1 =1

p−1
Y

pn (n′r ) = pn+1 (1).

r=0

We now resolve the recursion (6).
Denote xn = pn (0) and yn = pn (1), for n ≥ 1, so that an = p(xn + (p − 1)yn ).
The fact that pn (ni ) = yn whenever ni 6= 0, together with (6), implies that
X
Y
Y
xn+1 =
xn
yn ,
yn+1 =

n0 +···+np−1 =0

ni =0

X

Y

n0 +···+np−1 =1

ni 6=0

xn

ni =0

Y

yn

ni 6=0

Thus, by making all possible choices of ℓ coordinates, ℓ = 0, . . . , p, in (n0 , . . . , np−1 )
that are equal to 0, we obtain
 
p
X
p−ℓ ℓ p
(8)
zℓ
xn yn
xn+1 =
ℓ
ℓ=0
 
p
X
ℓ p
yn+1 =
(9)
z′ ,
xp−ℓ
y
n
n
ℓ ℓ
ℓ=0

where zℓ is the number of solutions of n′1 + · · · + n′ℓ = 0 such that none of n′1 , . . . , n′ℓ
is 0 and zℓ′ the number of solutions of n′1 + · · · + n′ℓ = 1 such that none of n′1 , . . . , n′ℓ
is 0.
For zℓ and zℓ′ , ℓ ≥ 1, we have the relations
zℓ+1 = (p − 1)zℓ′

′
zℓ+1
= zl + (p − 2)zℓ′ ,

with initial conditions z1 = 0 and z1′ = 1. The solution to this system is
1
((p − 1)ℓ − (−1)ℓ−1 (p − 1)),
p
1
zℓ′ = ((p − 1)ℓ − (−1)ℓ ),
p

zℓ =

which, by (8) and (9), gives
1
(xn + (p − 1)yn )p +
p
1
= (xn + (p − 1)yn )p −
p

xn+1 =
yn+1

p−1
(xn − yn )p ,
p
1
(xn − yn )p .
p

Finally, we obtain
xn+1 + (p − 1)(yn+1 ) = (xn + (p − 1)yn )p ,
and we conclude that
n−1

an = p(x1 + (p − 1)y1 )p

.



PORTRAIT GROWTH IN CONTRACTING, REGULAR BRANCH GROUPS

13

6. Portrait growth in the Apollonian group
The Apollonian group is a subgroup of the Hanoi Towers group. The Hanoi
Towers group was introduced by Grigorchuk and the first author [GŠ06] and the
Apollonian group was introduced later by Grigorchuk, Nekrashevych and the first
author [GNŠ06].
Definition 6.1. The Appolonian group A acting on the ternary tree is the group
generated by the automorphisms
x = (1, y, 1)(1 2),
y = (x, 1, 1)(1 3),
z = (1, 1, z)(2 3).
Set S = {x, y, z, x−1 , y −1 , z −1 . It is easy to see that A is contracting with nucleus
N (A) = S ∪ {1}.
Theorem 6.2. The portrait growth sequence {an }∞
n=0 of the Apollonian group is
given, for n ≥ 0, by
n
3n −1
n
1  √ 3
.
an = 3 2 · 7 3 = √ 7 3
3
Proof. Denote by E the subgroup of index 2 in A consisting of the elements in A
that are represented by words of even length over the alphabet {x± , y ± , z ± }. A left
transversal for E in A is given by T = {1, x}. It is known [GŠ07] that the Hanoi
Towers group H is a regular branch group over its commutator H ′ , which is of index
8 in H, and that the index of H ′ × H ′ × H ′ in H ′ is 12. The Apollonian group A
has index 4 in H and contains the commutator H ′ . Moreover, E = H ′ , implying
that A is a regular branch group, branching over E. The index of E × E × E in E
is 12, and a transversal is given by
T ′ = {1, yx, (yx)2 , x2 , y 2 , z 2 , x2 yx, y 3 x, z 2 yx, x2 (yx)2 , y 2 (yx)2 , z 2 (yx)2 }.

(1, 1, 1)

=1

(x, y, 1)(1 3 2)

= yx

≡ 1,
2

(x, yx, y)(1 2 3)

= (yx)

(y, y, 1)

= x2

(x, 1, x)

=y

2

=z

2

(1, z, z)
2

2

(yx, y , 1)(1 3 2) = x yx
2

(x , y, x)(1 3 2)
(x, zy, z)(1 3 2)

3

=y x
2

= z yx

≡ x,

(1, y, 1)(1 2)

=x

≡ 1,

(y, yx, 1)(2 3)

= xyx

(yx, yx, y)(1 3)

= x(yx)

≡ 1,

(y, y 2 , 1)(1 2)

= x3

≡ 1,
≡ 1,

(1, yx, x)(1 2)

≡ 1,

(z, y, z)(1 2)

≡ 1,

2

≡ 1,

≡ 1,

2

2

2

= xy

2

= xz

2

3

(y , y x, 1)(2 3) = x yx
(y, yx , x)(2, 3)
(zy, yx, z)(2 3)

3

= xy x
2

= xz yx

≡ x,

≡ x,

≡ x,

≡ x,

≡ x,

≡ x,

≡ x,

≡ x,

(yx, y 2 x, y)(1 2 3) = x2 (yx)2 ≡ 1,

(y 2 x, y 2 x, y)(1 3) = x3 (yx)2 ≡ x,

(x, zyx, zy)(1 2 3) = z 2 (yx)2 ≡ 1,

(zyx, yx, zy)(1 3) = xz 2 (yx)2 ≡ x,

(x2 , yx, xy)(1 2 3) = y 2 (yx)2 ≡ 1,

(yx, yx2 , xy)(1 3) = xy 2 (yx)2 ≡ x,

Table 1. The cosets of E × E × E decomposing the cosets of E

14

ZORAN ŠUNIĆ AND JONE URIA-ALBIZURI

Denote by Xn and Yn the number of portraits of depth at most n in the cosets
1E and xE respectively. The coset decomposition provided in Table 1 implies that
Xn+1 = 3Xn3 + 9Xn Yn2 ,
Yn+1 = 3Yn3 + 9Xn2 Yn .
which then yields
an+1 = Xn+1 + Yn+1 = 3(Xn + Yn )3 = 3a3n .
Taking into account the initial condition a0 = 7, we obtain an = 3
induction.

3n −1
2

n

73 by


References
[Bar98]

Laurent Bartholdi. The growth of Grigorchuk’s torsion group. Internat. Math. Res.
Notices, (20):1049–1054, 1998.
[dlH00]
Pierre de la Harpe. Topics in geometric group theory. Chicago Lectures in Mathematics.
University of Chicago Press, Chicago, IL, 2000.
[FAZR14] Gustavo A. Fernández-Alcober and Amaia Zugadi-Reizabal. GGS-groups: order of congruence quotients and Hausdorff dimension. Trans. Amer. Math. Soc., 366(4):1993–
2017, 2014.
[GNŠ06] Rostislav Grigorchuk, Volodymyr Nekrashevych, and Zoran Šunić. Hanoi towers groups.
In Topological and Geometric Methods in Group Theory, volume 3 issue 2 of Oberwolfach Reports. 2006.
[Gri80]
R. I. Grigorčuk. On Burnside’s problem on periodic groups. Funktsional. Anal. i
Prilozhen., 14(1):53–54, 1980.
[Gri83]
R. I. Grigorchuk. On the Milnor problem of group growth. Dokl. Akad. Nauk SSSR,
271(1):30–33, 1983.
[Gri84]
R. I. Grigorchuk. Degrees of growth of finitely generated groups and the theory of
invariant means. Izv. Akad. Nauk SSSR Ser. Mat., 48(5):939–985, 1984.
[Gri05]
Rostislav Grigorchuk. Solved and unsolved problems around one group. In Infinite
groups: geometric, combinatorial and dynamical aspects, volume 248 of Progr. Math.,
pages 117–218. Birkhäuser, Basel, 2005.
[Gro81]
Mikhael Gromov. Groups of polynomial growth and expanding maps. Inst. Hautes
Études Sci. Publ. Math., (53):53–73, 1981.
[GS83]
Narain Gupta and Saı̈d Sidki. On the Burnside problem for periodic groups. Math. Z.,
182(3):385–388, 1983.
[GŠ06]
Rostislav Grigorchuk and Zoran Šuniḱ. Asymptotic aspects of Schreier graphs and
Hanoi Towers groups. C. R. Math. Acad. Sci. Paris, 342(8):545–550, 2006.
[GŠ07]
Rostislav Grigorchuk and Zoran Šunić. Self-similarity and branching in group theory.
In Groups St. Andrews 2005. Vol. 1, volume 339 of London Math. Soc. Lecture Note
Ser., pages 36–95. Cambridge Univ. Press, Cambridge, 2007.
[Mil68a] J. Milnor. A note on curvature and fundamental group. J. Differential Geometry, 2:1–7,
1968.
[Mil68b] John Milnor. Growth of finitely generated solvable groups. J. Differential Geometry,
2:447–449, 1968.
[Mil68c] John Milor. Problem 5603. Amer. Math. Monthly, 75:685–686, 1968.
[Nek05]
Volodymyr Nekrashevych. Self-similar groups, volume 117 of Mathematical Surveys
and Monographs. American Mathematical Society, Providence, RI, 2005.
[Sid87]
Said Sidki. On a 2-generated infinite 3-group: subgroups and automorphisms. J. Algebra, 110(1):24–55, 1987.
[Šva55]
A. S. Švarc. A volume invariant of coverings. Dokl. Akad. Nauk SSSR (N.S.), 105:32–34,
1955.
Department of Mathematics, Hofstra University, Hempstead, NY 11549, USA
E-mail address: zoran.sunic@hofstra.edu
Department of Mathematics, University of the Basque Country, UPV/EHU, Leioa,
Bizkaia, Spain.
E-mail address: jone.uria@ehu.eus

