On growth of generalized Grigorchuk's overgroups
Grigorchuk’s Overgroup Ĝ, is a branch group of intermediate growth. It contains the first Grigorchuk’s torsion group G of intermediate growth constructed in 1980, but also has elements of infinite order. Its growth is substantially greater than the growth of G. The group G, corresponding to the sequ...
Gespeichert in:
| Datum: | 2020 |
|---|---|
| 1. Verfasser: | |
| Format: | Artikel |
| Sprache: | English |
| Veröffentlicht: |
Інститут прикладної математики і механіки НАН України
2020
|
| Schriftenreihe: | Algebra and Discrete Mathematics |
| Online Zugang: | http://dspace.nbuv.gov.ua/handle/123456789/188556 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Zitieren: | On growth of generalized Grigorchuk's overgroups / S.T. Samarakoon // Algebra and Discrete Mathematics. — 2020. — Vol. 30, № 1. — С. 97–117. — Бібліогр.: 20 назв. — англ. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
irk-123456789-188556 |
|---|---|
| record_format |
dspace |
| spelling |
irk-123456789-1885562023-03-07T01:26:54Z On growth of generalized Grigorchuk's overgroups Samarakoon, S.T. Grigorchuk’s Overgroup Ĝ, is a branch group of intermediate growth. It contains the first Grigorchuk’s torsion group G of intermediate growth constructed in 1980, but also has elements of infinite order. Its growth is substantially greater than the growth of G. The group G, corresponding to the sequence (012)∞ = 012012 . . ., is a member of the family {Gω|ω ∈ Ω = {0, 1, 2}ᴺ} consisting of groups of intermediate growth when sequence ω is not eventually constant. Following this construction, we define the family { Ĝω, ω ∈ Ω} of generalized overgroups. Then Ĝ = Ĝ (012)∞ and Gω is a subgroup of Ĝω for each ω ∈ Ω. We prove, if ω is eventually constant, then Ĝω is of polynomial growth and if ω is not eventually constant, then Ĝω is of intermediate growth. 2020 Article On growth of generalized Grigorchuk's overgroups / S.T. Samarakoon // Algebra and Discrete Mathematics. — 2020. — Vol. 30, № 1. — С. 97–117. — Бібліогр.: 20 назв. — англ. 1726-3255 DOI:10.12958/adm1451 2010 MSC: 20E08 http://dspace.nbuv.gov.ua/handle/123456789/188556 en Algebra and Discrete Mathematics Інститут прикладної математики і механіки НАН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
English |
| description |
Grigorchuk’s Overgroup Ĝ, is a branch group of intermediate growth. It contains the first Grigorchuk’s torsion group G of intermediate growth constructed in 1980, but also has elements of infinite order. Its growth is substantially greater than the growth of G. The group G, corresponding to the sequence (012)∞ = 012012 . . ., is a member of the family {Gω|ω ∈ Ω = {0, 1, 2}ᴺ} consisting of groups of intermediate growth when sequence ω is not eventually constant. Following this construction, we define the family { Ĝω, ω ∈ Ω} of generalized overgroups. Then Ĝ = Ĝ (012)∞ and Gω is a subgroup of Ĝω for each ω ∈ Ω. We prove, if ω is eventually constant, then Ĝω is of polynomial growth and if ω is not eventually constant, then Ĝω is of intermediate growth. |
| format |
Article |
| author |
Samarakoon, S.T. |
| spellingShingle |
Samarakoon, S.T. On growth of generalized Grigorchuk's overgroups Algebra and Discrete Mathematics |
| author_facet |
Samarakoon, S.T. |
| author_sort |
Samarakoon, S.T. |
| title |
On growth of generalized Grigorchuk's overgroups |
| title_short |
On growth of generalized Grigorchuk's overgroups |
| title_full |
On growth of generalized Grigorchuk's overgroups |
| title_fullStr |
On growth of generalized Grigorchuk's overgroups |
| title_full_unstemmed |
On growth of generalized Grigorchuk's overgroups |
| title_sort |
on growth of generalized grigorchuk's overgroups |
| publisher |
Інститут прикладної математики і механіки НАН України |
| publishDate |
2020 |
| url |
http://dspace.nbuv.gov.ua/handle/123456789/188556 |
| citation_txt |
On growth of generalized Grigorchuk's overgroups / S.T. Samarakoon // Algebra and Discrete Mathematics. — 2020. — Vol. 30, № 1. — С. 97–117. — Бібліогр.: 20 назв. — англ. |
| series |
Algebra and Discrete Mathematics |
| work_keys_str_mv |
AT samarakoonst ongrowthofgeneralizedgrigorchuksovergroups |
| first_indexed |
2025-07-16T10:39:42Z |
| last_indexed |
2025-07-16T10:39:42Z |
| _version_ |
1837799711616008192 |
| fulltext |
“adm-n3” — 2021/1/3 — 11:48 — page 97 — #103
© Algebra and Discrete Mathematics RESEARCH ARTICLE
Volume 30 (2020). Number 1, pp. 97–117
DOI:10.12958/adm1451
On growth of generalized
Grigorchuk’s overgroups
S. T. Samarakoon
Communicated by V. Nekrashevych
Abstract. Grigorchuk’s Overgroup G̃, is a branch group
of intermediate growth. It contains the first Grigorchuk’s torsion
group G of intermediate growth constructed in 1980, but also has
elements of infinite order. Its growth is substantially greater than the
growth of G. The group G, corresponding to the sequence (012)∞ =
012012 . . ., is a member of the family {Gω|ω ∈ Ω = {0, 1, 2}N}
consisting of groups of intermediate growth when sequence ω is
not eventually constant. Following this construction, we define the
family {G̃ω, ω ∈ Ω} of generalized overgroups. Then G̃ = G̃(012)∞
and Gω is a subgroup of G̃ω for each ω ∈ Ω. We prove, if ω is
eventually constant, then G̃ω is of polynomial growth and if ω is
not eventually constant, then G̃ω is of intermediate growth.
Introduction
The growth rate of groups is a long studied area [15, 17, 20] and it
was known that growth rates of groups can vary from polynomial growth
through intermediate growth to exponential growth. First group of inter-
mediate growth (the growth which is neither polynomial nor exponential),
known as the first Grigorchuk’s torsion group G, was constructed by Ros-
tislav Grigorchuk in 1980 [10] as a finitely generated infinite torsion group
and later [11] it was shown that it has intermediate growth. The growth rate
2010 MSC: 20E08.
Key words and phrases: growth of groups, intermediate growth, Grigorchuk
group, growth bounds.
https://doi.org/10.12958/adm1451
“adm-n3” — 2021/1/3 — 11:48 — page 98 — #104
98 On growth of G̃ω
γG(n) of G was first shown to be bounded below by e
√
n and bounded above
by en
β
, where β = log32 31 ≈ 0.991 [11,12]. In 1998, Laurent Bartholdi [1]
and in 2001, Roman Muchnik and Igor Pak [18] independently refined the
upper bound to γG(n) � en
α
, where α = log (2)/ log (2/η) ≈ 0.767 and η
is the real root of the polynomial x3 + x2 + x− 2. Recent work of Anna
Erschler and Tianyi Zheng [8] showed γG(n) � en
(α−ǫ)
for any positive ǫ.
At the same time, in [11, 12] (also see [14]) an uncountable family
of groups {Gω : ω ∈ Ω = {0, 1, 2}N}, known as generalized Grigorchuk’s
groups were constructed. They consist of groups of intermediate growth
when sequence ω is not virtually constant and of polynomial growth when
sequence ω is virtually constant [12].
Since the construction of the first Grigorchuk group, there was an
expansion of the area of study and new groups of intermediate growth
were introduced [3,4, 13,16,19]. The group G̃ known as the Grigorchuk’s
overgroup [5] is an infinite finitely generated group of intermediate growth
which shares many properties with first Grigorchuk’s group [6]. In contrast,
the Grigorchuk’s overgroup has an element of infinite order [5]. As a
corollary to Proposition 4 and Theorem 2′′ of present article, the growth
rate γG̃(n) of G̃ satisfies,
exp
(
n
log2+ǫ n
)
� γG̃(n) � exp
(
n log(log n)
log n
)
for any ǫ > 0.
First introduced technique for getting an upper bound for G uses the
strong contraction property [12] (also known as sum contraction property),
which says that there is a finite index subgroup H of G such that any
element g ∈ H can be uniquely decomposed into some elements, whose
sum of lengths in not larger than C|g|+D, where 0 < C < 1 and D are
constants independent of g [12]. Later this technique was developed and
many variants were introduced [2, 7, 9]. In 2004, to get a lower bound for
a certain class of groups of intermediate growth, Anna Erschler introduced
a method for partial description of the Poisson boundary [7]. This idea
was used to get the current known best lower bound for the growth of
G [8]. We will be using a version of strong contraction property in this
text.
Following the construction in [12], we introduce an uncountable family
{G̃ω, ω ∈ Ω} called generalized Grigorchuk’s overgroups, where Ω =
{0, 1, 2}N (see Section 1.1).
“adm-n3” — 2021/1/3 — 11:48 — page 99 — #105
S. T. Samarakoon 99
Theorem 1. Let ω ∈ Ω. Then G̃ω is of polynomial growth if ω is virtually
constant and G̃ω is of intermediate growth if ω is not virtually constant.
Let Ω0,Ω1 be subsets of Ω, where Ω0 is the set consisting of all
sequences containing 0, 1 and 2 infinitely often, Ω1 is the set consisting
of sequences containing exactly two symbols infinitely often. Define Ω∗
0
to be the subset of Ω0 containing sequences ω = {ωn}, such that there
is an integer M = M(ω) with the property that for all k > 1, the set
{ωk, ωk+1, . . . , ωk+M−1} contains all three symbols 0,1 and 2. Similarly,
define Ω∗
1 to be the subset of Ω1 containing sequences ω = {ωn}, such that
there is an integer M =M(ω) with the property that for all k > 1, the set
{ωk, ωk+1, . . . , ωk+M−1} contains at least two symbols. Let Ω∗ = Ω∗
0 ∪Ω∗
1.
Sequences in Ω∗ are called homogeneous sequences.
Theorem 2. Let ω ∈ Ω∗. Then
γ
G̃ω
(n) � exp
(
n log(log n)
log n
)
.
Theorem 2 provides an upper bound for growth of G̃ω only for ho-
mogeneous sequences. In fact, it is impossible to give a unifying upper
bound for growth of G̃ω, for all ω ∈ Ω0 ∪ Ω1. This follows from Theorem
7.1 of [12], together with the fact that Gω ⊂ G̃ω. However, it is possible
to provide a unifying lower bound for the growth of groups G̃ω for all
ω ∈ Ω0 ∪ Ω1 by a function of type exp
(
n
log2+ǫ(n)
)
for arbitrary ǫ > 0
(see Proposition 4).
We prove Theorem 1 in Section 2 and Theorem 2 in Section 3.
1. Preliminaries
First recall Ω = {0, 1, 2}N and Ω0,Ω1 ⊂ Ω are the set of all sequences
containing 0, 1 and 2 infinitely often and the set of all sequences containing
exactly two symbols infinitely often, respectively. Now let Ω2,Ω1,2 be
subsets of Ω, where Ω2 is the set consisting of all eventually constant
sequences and Ω1,2 is the set consisting of sequences containing at most
two symbols. Let σ : Ω → Ω be the left shift. i.e. (σω)n = ωn+1.
1.1. Generalized Grigorchuk’s groups Gω
and generalized Grigorchuk’s overgroups G̃ω
Let T2 be the labeled binary rooted tree with root ∅, where vertices
are labeled by finite strings of 0s and 1s (see Figure 1). Let Aut(T2) be
“adm-n3” — 2021/1/3 — 11:48 — page 100 — #106
100 On growth of G̃ω
∅
0
00
000 001
01
010 011
1
10
100 101
11
110 111
1
∞
∈ ∂T2
Figure 1. Labeled binary rooted tree T2
the group of automorphisms of T2, fixing the root and preserving the tree
structure. That is, if g ∈ AutT2, then g is a bijection from set of vertices
of T2 onto itself such that g(∅) = ∅ and g(u), g(v) are adjacent if and
only if u, v are adjacent. For two vertices u, v of T2, let uv be the vertex
of T2 labeled by the concatenation of labels of u and v.
For g ∈ Aut(T2), v ∈ T2, there is a unique element g|v ∈ Aut(T2), such
that g(vu) = g(v)g|v(u), for all u ∈ T2. g|v is called the section of g at v.
In this article, we will only consider the sections for which g(v) = v.
Denote the identity in Aut(T2) by 1. Let a ∈ Aut(T2) be such that
a(0v) = 1v and a(1v) = 0v, for all v ∈ Aut(T2). Note that any g ∈ Aut(T2),
that fixes vertices 1n−10 for all n > 1, can be uniquely identified by its
sections at 1n−10, for all n > 1. So we identify an infinite sequence of auto-
morphisms {An} with the element g ∈ Aut(T2) where g(1n−10) = 1n−10
and g|1n−10 = An for all n > 1. Identify x ∈ Aut(T2) with the sequence
(a, a, . . .).
For ω ∈ Ω, define bω, cω, dω, b̃ω, c̃ω, d̃ω ∈ Aut(T2) to be the elements
identified with sequences {Bn}, {Cn}, {Dn}, {B̃n}, {C̃n}, {D̃n}, respec-
“adm-n3” — 2021/1/3 — 11:48 — page 101 — #107
S. T. Samarakoon 101
tively, where
Bn =
{
a ωn = 0 or 1
1 ωn = 2
, B̃n =
{
1 ωn = 0 or 1
a ωn = 2
,
Cn =
{
a ωn = 0 or 2
1 ωn = 1
, C̃n =
{
1 ωn = 0 or 2
a ωn = 1
,
Dn =
{
a ωn = 1 or 2
1 ωn = 0
, D̃n =
{
1 ωn = 1 or 2
a ωn = 0
. (1)
We will denote a, x by aω, xω, respectively, if it is convenient. Note that all
these elements are involutions and all except a commute with each other.
The generalized Grigorchuk group Gω is the group generated by elements
a, bω, cω, dω and the generalized overgroup G̃ω is the group generated by
a, bω, cω, dω, x. As follows from definition, Gω ⊂ G̃ω and it is useful to view
G̃ω as the group generated by the set S̃ω = {a, bω, cω, dω, x, b̃ω, c̃ω, d̃ω}.
For any ω ∈ Ω, elements in S̃ω satisfy the following relations called
simple contractions;
a2 = x2 = b2ω = c2ω = d2ω = b̃2ω = c̃2ω = d̃2ω = 1,
bωcω = cωbω = dω, cωdω = dωcω = bω, dωbω = bωdω = cω,
b̃ω c̃ω = c̃ω b̃ω = dω, c̃ωd̃ω = d̃ω c̃ω = bω, d̃ω b̃ω = b̃ωd̃ω = cω,
bω c̃ω = c̃ωbω = d̃ω, cωd̃ω = d̃ωcω = b̃ω, dω b̃ω = b̃ωdω = c̃ω,
b̃ωcω = cω b̃ω = d̃ω, c̃ωdω = dω c̃ω = b̃ω, d̃ωbω = bωd̃ω = c̃ω,
bω b̃ω = b̃ωbω = cω c̃ω = c̃ωcω = dωd̃ω = d̃ωdω = x,
bωx = xbω = b̃ω, cωx = xcω = c̃ω, dωx = xdω = d̃ω,
b̃ωx = xb̃ω = bω, c̃ωx = xc̃ω = cω, d̃ωx = xd̃ω = dω. (2)
Any word over the alphabet S̃ω can be reduced using simple contractions (2)
to a word of the form,
(a) ∗ a ∗ a ∗ . . . ∗ a ∗ a ∗ (a). (3)
Here the first and the last a can be omitted and ‘∗’s represent generators
in S̃ω \ {a}. A word of the form (3) is called a reduced word. Thus, each
element g ∈ G̃ω can be represented using a reduced word.
Denote H̃ω := H̃
(1)
ω := {g ∈ G̃ω : g(v) = v for v = 0, 1}. Then g ∈ H̃ω
if and only if every word representing g has even number of ‘a’s. It is easy
“adm-n3” — 2021/1/3 — 11:48 — page 102 — #108
102 On growth of G̃ω
to see that H̃ω is generated by {s, sa : s ∈ S̃ω \ {a}}, using (3). There is a
natural embedding ψ̃ω from {s, sa : s ∈ S̃ω \ {a}} to
(
S̃σω ∪ {1}
)2
given
by
bω 7→ (B1, bσω), cω 7→ (C1, cσω), dω 7→ (D1, dσω),
baω 7→ (bσω, B1), caω 7→ (cσω, C1), daω 7→ (dσω, D1),
b̃ω 7→ (B̃1, b̃σω), c̃ω 7→ (C̃1, c̃σω), d̃ω 7→ (D̃1, d̃σω),
b̃aω 7→ (̃bσω, B̃1), c̃aω 7→ (c̃σω, C̃1), d̃aω 7→ (d̃σω, D̃1),
x 7→ (a, x), xa 7→ (x, a). (4)
Let W be a word with even number of ‘a’s, over alphabet S̃ω, in the
reduced form (3). Then W can be written in the form,
(∗a) ∗ ∗a ∗ ∗a . . . ∗ ∗a ∗ (∗a), (5)
where ‘∗’s represent elements in S̃ω \ {a}. Here the first and last ∗a can be
omitted depending on first and last letter of W . Now using (5) and (4),
we can extend ψ̃ω to the set of words W , of the reduced form (3), over
alphabet S̃ω, with even number of a’s. Then W 7→ (W̃0, W̃1), where W̃0, W̃1
are words over alphabet S̃σω, which need not to be in reduced form (3).
Note that each ∗, ∗a in (5) contributes either a letter or no letters (if the
corresponding coordinate is 1) to each of W̃0 and W̃1. Write W in the
form (5), and suppose there are n number of ‘∗’s in it. Then
∣∣∣W̃0
∣∣∣ ,
∣∣∣W̃1
∣∣∣ 6 n.
If W = ∗∗a∗∗a . . .∗∗a∗, then |W | = 2n−1. If W = (∗a)∗∗a∗∗a . . .∗∗a∗ or
W = ∗∗a∗∗a . . .∗∗a∗(∗a), then |W | = 2n. IfW = (∗a)∗∗a∗∗a . . .∗∗a∗(∗a),
then |W | = 2n+ 1. In either case, we get
∣∣∣W̃0
∣∣∣ ,
∣∣∣W̃1
∣∣∣ 6 |W |+ 1
2
and
∣∣∣W̃0
∣∣∣+
∣∣∣W̃1
∣∣∣ 6 |W |+ 1. (6)
Here |W | ,
∣∣∣W̃0
∣∣∣ ,
∣∣∣W̃1
∣∣∣, represents the number of letters in W, W̃0, W̃1,
respectively. In fact, we can give a better upper bound,
∣∣∣W̃0
∣∣∣+
∣∣∣W̃1
∣∣∣ 6 |W |+ 1− α, (7)
where α is the number of letters in W , whose first coordinate of the
natural embedding is 1. ψ̃ω can also be extended to a map from H̃ω into
G̃σω × G̃σω given by,
ψ̃ω(g) = (g|0, g|1). (8)
“adm-n3” — 2021/1/3 — 11:48 — page 103 — #109
S. T. Samarakoon 103
We will denote both of theses extensions also by ψ̃ω and we may drop the
subscript ω if there is no ambiguity.
Let G be a group with a finite generating set S. For a word W over
the alphabet S, the number of letters in W is denoted by |W | and for
s ∈ S, the number of occurrences of s in W is denoted by |W |s. For any
element g ∈ G, the length of g, denoted by |g|, is defined by
|g| = min{|W | : g =W in G}.
It is easy to see from (8) and (6), that for g ∈ H̃ω,
|g|0| , |g|1| 6
|g|+ 1
2
and |g|0|+ |g|1| 6 |g|+ 1. (9)
Now define γG,S , a positive integer valued function on nonnegative integers
by
γG,S(n) = |BG,S(n)| ,
where BG,S(n) = {g ∈ G : |g| 6 n} is the ball of radius n in the Cayley
graph of G with respect to the generating set S. γG,S is called the volume
growth function of G with respect to the finite generating set S.
There is a partial order relation � for growth functions defined by f � g
if and only if there are constants A and B such that f(n) 6 Ag(Bn) for all
n. We define an equivalence relation ≃ by, f ≃ g if and only if f � g and
g � f . The equivalence class of γG,S(n) is known as the growth rate of the
group G. The growth rate of a group does not depend on the generating set.
So we denote the growth rate of a group G, by γG(n). Growth rate can be
polynomial, exponential, or intermediate if γG,S(n) ≃ nd for some positive
integer d, γG,S(n) ≃ en, or nd ň γG,S(n) ň en for all positive integers d,
respectively. Growth above polynomial is called super polynomial and
growth below exponential is called subexponential.
The growth exponent λG,S of a group G generated by S, is given by
λG,S = lim
n
(γG,S(n))
1/n, and λG,S > 1 for any finitely generated group G.
Note that 1/λG,S is the radius of convergence of the generating function
of {γG,S(n)}. An easy exercise shows that, for finitely generated, infinite
group G with generating set S
lim
n
(γG,S(n))
1/n = lim
n
(
γ′G,S(n)
)1/n
, (10)
by looking at the radii of convergence of generating functions of {γG,S(n)}
and {γ′G,S(n)}, where γ′G,S(n) = |BG,S(n) \BG,S(n− 1)| = γG,S(n) −
“adm-n3” — 2021/1/3 — 11:48 — page 104 — #110
104 On growth of G̃ω
γG,S(n − 1) is the spherical growth function of G with respect to the
generating set S. For finite indexed subgroup H of G,
γH,S(n) 6 γG,S(n) 6 γH,S(n+N),
where γH,S(n) = |BG,S(n) ∩H| and N is the maximum of lengths of right
coset representatives of H in G. Thus for infinite group G, we get
lim
n
(γH,S(n))
1/n = lim
n
(
γ′H,S(n)
)1/n
= lim
n
(γG,S(n))
1/n . (11)
Here γ′H,S(n) = |(BG,S(n) \BG,S(n− 1)) ∩H|. It is known that λG,S > 1
if and only if G has exponential growth [12]. We will be using γ̃ω, λ̃ω in this
text to denote γ
G̃ω ,S̃ω
, λ
G̃ω ,S̃ω
, where S̃ω = {a, bω, cω, dω, x, b̃ω, c̃ω, d̃ω}.
2. Growth of G̃ω
Proposition 1. G̃ω has subexponential growth for each ω ∈ Ω1 ∪ Ω2.
Before proceeding to the proof, we start with three lemmas.
Lemma 1. A non-decreasing semi-multiplicative function γ(n) with ar-
gument a natural number, can be extended to a non-decreasing semi-
multiplicative function γ(x), with argument a non-negative real number.
Proof. See Lemma 3.1 of [12].
Lemma 2. For any ω ∈ Ω, λ̃ω 6 λ̃σω.
Proof. Denote B̃ω(n) = B
G̃ω ,S̃ω
(n) and H̃ω(n) = H̃ω∩B̃ω(n). Any element
g ∈ B̃ω(n) is either in H̃ω or is of the form g = ag′, where g′ ∈ H̃ω and
|g′| 6 |g|+ 1 6 n+ 1. Thus,
γ̃ω(n) = |B̃ω(n)| 6 |H̃ω(n)|+ |H̃ω(n+ 1)| 6 2|H̃ω(n+ 1)|.
For each g ∈ H̃ω, g|0, g|1 ∈ G̃σω from (8) satisfy (9) and so,
|H̃ω(n)| 6 |B̃σω(
n+ 1
2
)|2 =
(
γ̃σω(
n+ 1
2
)
)2
.
Therefore,
γ̃ω(n) 6 2
(
γ̃σω(
n+ 2
2
)
)2
.
“adm-n3” — 2021/1/3 — 11:48 — page 105 — #111
S. T. Samarakoon 105
Consequently,
λ̃ω = lim
n
(γ̃ω(n))
1/n
6 lim
n
(
2
(
γ̃σω(
n+ 2
2
)
)2
)1/n
= lim
n
(
γ̃σω(
n+ 2
2
)
)2/n
= λ̃σω.
Lemma 3. For any ω ∈ Ω1,2, G̃ω = Gω.
Proof. First note that x ∈ Gω =⇒ xbω, xcω, xdω ∈ Gω =⇒ b̃ω, c̃ω, d̃ω ∈
Gω =⇒ G̃ω ⊂ Gω =⇒ G̃ω = Gω. To prove Lemma 3, we only need
to show that x ∈ Gω. For definiteness we may assume ω consists only of
symbols 0, 1. Then by (1), bω = (a, a, a, ...) = x. Therefore x ∈ Gω and
thus the result is true.
Proof of Proposition 1. Let ω ∈ Ω1 ∪ Ω2. Then there exists N ∈ N such
that σNω ∈ Ω1,2. Then by Lemma 3, G̃σNω = GσNω. Therefore λ̃σNω =
λσNω. For any ω,Gω is of intermediate growth if ω ∈ Ω1 and of polynomial
growth if ω ∈ Ω2 [12]. Thus λσNω = 1. So by Lemma 2, λ̃ω 6 λ̃σNω = 1.
Thus G̃ω is of subexponential growth.
Proposition 2. G̃ω has intermediate growth for ω ∈ Ω1.
Proof. By Proposition 1, G̃ω is of subexponential growth. Since Gω ⊂ G̃ω
and Gω is of super-polynomial growth [12], G̃ω is of super-polynomial
growth. Hence G̃ω is of intermediate growth.
Proposition 3. G̃ω has polynomial growth for ω ∈ Ω2.
Proof. Since ω ∈ Ω2, there is a natural number N such that ωn = ωN for
all n > N , where ω = {ωn}. Then G̃σN−1ω = 〈a, x〉 ∼= D∞, the infinite
Dihedral group. Let G be the subgroup of Aut(T2) containing elements
g such that g|v ∈ 〈a, x〉 for all v in level N − 1 of T2. Then G̃ω ⊂ G. Let
G0 be the subgroup of G containing automorphisms fixing all vertices in
the first N − 1 levels of T2. Note that G0 ⊳G and [G : G0] 6 22
N−1. But
G0
∼= 〈a, x〉2N−1 ∼= D
2N−1
∞ . Thus G0 is virtually abelian and of polynomial
growth. Since [G : G0] <∞,G is of polynomial growth. G̃ω ⊂ G implies
that G̃ω is of polynomial growth.
Theorem 3. G̃ω has intermediate growth for ω ∈ Ω0.
“adm-n3” — 2021/1/3 — 11:48 — page 106 — #112
106 On growth of G̃ω
We will, from now on, consider the generating set of G̃ω to be S̃ω =
{a, bω, cω, dω, b̃ω, c̃ω, d̃ω, x}. A reduced word W satisfying g = W in G̃ω
and |g| = |W | is called a minimal representation of g. For any ǫ > 0 define
F ǫ(n) = F ǫ
ω(n) to be the set of length n elements g in G̃ω such that for
any minimal representation W of g over alphabet S̃ω,
|W |∗ > (1/2− ǫ)n, for some ∗ ∈ S̃ω \ {a}. (12)
So for any minimal representation of elements in F ǫ(n), its reduced form (3)
has most of ∗s as the same letter. Now define Dǫ(n) = Dǫ
ω(n) to be the
complement of F ǫ(n) in B̃ω(n) \ B̃ω(n− 1), the sphere of radius n. Thus
if g ∈ Dǫ(n), then g has a minimal representation W satisfying
|W |∗ 6 (1/2− ǫ)n, for all ∗ ∈ S̃ω \ {a}. (13)
For any δ > 0 define F̃δ(n′) to be the set of words W ′ over the alphabet
S̃ω \ {a} of length n′ such that
∣∣W ′∣∣
∗ > (1− δ)n′, for some ∗ ∈ S̃ω \ {a}. (14)
Therefore, each word in F̃δ(n′) has mostly equal letters.
Lemma 4. Let 0 < ǫ < 1/2 and let W be a minimal representation of an
element in F ǫ(n). Let W ′ be the word obtained by deleting all letters a
from W . Then W ′ ∈ F̃δ(n′) where
n− 1
2
6 n′ 6
n+ 1
2
, (15)
δ = 2ǫ+
(1− 2ǫ)
n− 1
. (16)
Proof. Since W is a reduced word, by (3), we observe that, 2 |W |a − 1 6
|W | 6 2 |W |a + 1. Thus
|W | − 1
2
6 |W |a 6
|W |+ 1
2
, and so
|W | − 1
2
6
|W | − |W |a 6
|W |+ 1
2
. So we get (15).
By (12),
∣∣W ′∣∣
∗ = |W |∗ > (1/2− ǫ)n > (1/2− ǫ)(2n′ − 1)
=
(
1− 2ǫ− (1− 2ǫ)
2n′
)
n′ >
(
1− 2ǫ− (1− 2ǫ)
n− 1
)
n′ = (1− δ)n′,
from (16).
“adm-n3” — 2021/1/3 — 11:48 — page 107 — #113
S. T. Samarakoon 107
Lemma 5. If δ < 1, then lim
k
|F̃δ(k)|1/k 6 (1− δ)−1(δ/6)−δ.
Proof. Any word W ∈ F̃δ(k) can be constructed by choosing a letter ∗
out of {b, c, d, b̃, c̃, d̃, x}, which satisfies (14). So, W contains the letter ∗
at least k − ⌊δk⌋ times and possibly t times more, where 0 6 t 6 ⌊δk⌋.
The rest of the positions of W can be filled by the other six letters with
frequencies i1, . . . , i6, where
∑
ij = ⌊δk⌋ − t. Therefore, we have
∣∣∣F̃δ(k)
∣∣∣ 6 7 + 7
⌊δk⌋∑
t=0
∑
∑
ij=⌊δk⌋−t
k!
(k − ⌊δk⌋+ t)!i1! . . . i6!
.
Let (δk − t)∗ := 6
⌊⌊δk − t⌋
6
⌋
be the largest integer not greater than
⌊δk − t⌋, that is divisible by 6. Since i1, . . . , i6 are non negative integers,
we have
i1! . . . i6! >
⌊∑
ij
6
⌋
!6 =
⌊⌊δk⌋ − t
6
⌋
!6 =
⌊⌊δk − t⌋
6
⌋
!6 =
(
(δk − t)∗
6
)
!6.
Since the number of ways to choose non negative integers i1, . . . , i6 such
that
∑
ij = ⌊δk⌋ − t is
(⌊δk⌋−t+5
5
)
, we get
∣∣∣F̃δ(k)
∣∣∣ 6 7 + 7
⌊δk⌋∑
t=0
(⌊δk⌋ − t+ 5
5
)
k!
(k − ⌊δk⌋+ t)!
(
(δk−t)∗
6
)
!6
6 7 + 7
(⌊δk⌋+ 5
5
) ⌊δk⌋∑
t=0
k!
(k − ⌊δk⌋+ t)!
(
(δk−t)∗
6
)
!6
6 (⌊δk⌋+ 5)5
⌊δk⌋∑
t=0
k!
(k − ⌊δk⌋+ t)!
(
(δk−t)∗
6
)
!6
6 (⌊δk⌋+ 5)5
⌊δk⌋∑
t=0
e
√
kkke−ke(k−⌊δk⌋+t)e(δk−t)∗
(k − ⌊δk⌋+ t)(k−⌊δk⌋+t)
(
(δk−t)∗
6
)(δk−t)∗
.
Here we used the Stirling’s formula
nn
en
6 n! 6 e
√
n
nn
en
. Since 0 6
(⌊δk⌋ − t)− (δk − t)∗ 6 6,
∣∣∣F̃δ(k)
∣∣∣ 6 e(⌊δk⌋+ 5)5
⌊δk⌋∑
t=0
√
kk(⌊δk⌋−t)−(δk−t)∗e(δk−t)∗−(⌊δk⌋−t)
(
1− ⌊δk⌋
k + t
k
)(k−⌊δk⌋+t) (
(δk−t)∗
6k
)(δk−t)∗
“adm-n3” — 2021/1/3 — 11:48 — page 108 — #114
108 On growth of G̃ω
6 e(⌊δk⌋+ 5)5
⌊δk⌋∑
t=0
√
kk6
(
1− ⌊δk⌋
k + t
k
)(k−⌊δk⌋+t) (
(δk−t)∗
6k
)(δk−t)∗
6 ek6(⌊δk⌋+ 5)5
√
k(1− δ)−k
⌊δk⌋∑
t=0
(
(δk − t)∗
6k
)−(δk−t)∗
.
Note that the real valued function, ξ 7→ ξ−ξ for ξ > 0, is an increasing
function on the interval (0, e−1). Since δ/6 < 1/6 < e−1, we get
(
(δk − x)∗
6k
)−
(
(δk−x)∗
6k
)
6
(
δ
6
)−( δ
6)
.
Therefore,
∣∣∣F̃δ(k)
∣∣∣ 6 ek6(⌊δk⌋+ 5)5
√
k(1− δ)−k(⌊δk⌋+ 1)
(
δ
6
)−( δ
6)6k
.
Hence,
lim
k
∣∣∣F̃δ(k)
∣∣∣
1/k
6 (1− δ)−1(δ/6)−δ.
Corollary 1. Let ǫ < 1/2. Then, lim
n
|F ǫ(n)|1/n 6 (1− 2ǫ)−1/2(ǫ/3)−ǫ.
Proof. If n is even, then minimal representations of at most two elements
in F ǫ(n) give the same word in F̃δ(n/2). So,
|F ǫ(n)| 6 2|F̃δ(n/2)|.
If n is odd, then for each element in F ǫ(n), we can assign a unique word
in F̃δ((n− 1)/2) or F̃δ((n+ 1)/2), and so,
|F ǫ(n)| 6 |F̃δ((n− 1)/2)|+ |F̃δ((n+ 1)/2)|.
Note that,
lim
n
|F̃δ(n/2)|1/n 6 lim
n
(
(1− δ)−1(δ/6)−δ
)1/2
,
lim
n
|F̃δ((n− 1)/2)|1/n 6 lim
n
(
(1− δ)−1(δ/6)−δ
)1/2
,
lim
n
|F̃δ((n+ 1)/2)|1/n 6 lim
n
(
(1− δ)−1(δ/6)−δ
)1/2
,
“adm-n3” — 2021/1/3 — 11:48 — page 109 — #115
S. T. Samarakoon 109
and thus,
lim
n
|F ǫ(n)|1/n 6 lim
n
(
(1− δ)−1(δ/6)−δ
)1/2
.
Since δ = 2ǫ+
(1− 2ǫ)
n− 1
, lim
n
δ = 2ǫ and therefore,
lim
n
(
(1− δ)−1(δ/6)−δ
)−1/2
= (1− 2ǫ)−1/2(ǫ/3)−ǫ.
Hence we get the desired result.
For each s > 1, let H̃
(s)
ω := {g ∈ G̃ω : g(v) = v for v in level s} and
denote the canonical generators of G̃σsω by a, bs, cs, ds, b̃s, c̃s, d̃s, x. We
assign above symbols, when s = 0, to the generators of G̃ω. Using the
map ψ̃, we get the following:
ωs = 0 =⇒ bs−1 = (a, bs) cs−1 = (a, cs) ds−1 = (1, ds) x = (a, x)
b̃s−1 = (1, b̃s) c̃s−1 = (1, c̃s) d̃s−1 = (a, d̃s),
ωs = 1 =⇒ bs−1 = (a, bs) cs−1 = (1, cs) ds−1 = (a, ds) x = (a, x)
b̃s−1 = (1, b̃s) c̃s−1 = (a, c̃s) d̃s−1 = (1, d̃s),
ωs = 2 =⇒ bs−1 = (1, bs) cs−1 = (a, cs) ds−1 = (a, ds) x = (a, x)
b̃s−1 = (a, b̃s) c̃s−1 = (1, c̃s) d̃s−1 = (1, d̃s). (17)
Let W be a minimal representation of an element in H̃
(s)
ω . Then there
are W̃0, W̃1 such that W = (W̃0, W̃1) using substitutions in (17). Let
W0,W1 be obtained by doing simple contractions on W̃0, W̃1. Let α1
denote the number of such simple contractions. So W0,W1 are minimal
representations of words in H̃
(s−1)
σ1ω
and by (6),
|W0|+ |W1| 6
∣∣∣W̃0
∣∣∣+
∣∣∣W̃1
∣∣∣− α1 6 |W |+ 1− α1. (18)
Now there are W̃00, W̃01, W̃10, W̃11 such that W0 = (W̃00, W̃01),
W1 = (W̃10, W̃11) using substitutions in (17). Let W00,W01, W10,W11 be
obtained by doing simple contractions on W̃00, W̃01, W̃10, W̃11. Let α2
denote the number of such simple contractions. So W00,W01,W10,W11
“adm-n3” — 2021/1/3 — 11:48 — page 110 — #116
110 On growth of G̃ω
are minimal representations of elements in H̃
(s−2)
σ2ω
and applying (18), we
get
|W00|+ |W01|+ |W10|+ |W11| 6 |W0|+ 1 + |W1|+ 1− α2
6 |W |+ 22 − 1− (α1 + α2).
Proceeding this manner we get {Wi1i2...is}ij∈{0,1} minimal representations
of elements in H̃
(s−s)
σsω = G̃σsω. Denote by αs the number of simple con-
tractions done to obtain {Wi1i2...is}ij∈{0,1} from {W̃i1i2...is}ij∈{0,1}. Then
by applying (18) repeatedly, we get
∑
i1,i2,...,is
|Wi1i2...is | 6 |W |+ 2s − 1−
s−1∑
1
αi. (19)
Let X0 := |W |d0 + |W |̃
b0
+ |W |c̃0 , Y0 := |W |c0 + |W |̃
b0
+ |W |
d̃0
and
Z0 := |W |b0 + |W |c̃0 + |W |
d̃0
. Also for j = 1, 2, . . . s, let
Xj =
∑(
|Wi1i2...ij |dj + |Wi1i2...ij |̃bj + |Wi1i2...ij |c̃j
)
,
Yj =
∑(
|Wi1i2...ij |cj + |Wi1i2...ij |̃bj + |Wi1i2...ij |d̃j
)
,
Zj =
∑(
|Wi1i2...ij |bj + |Wi1i2...ij |c̃j + |Wi1i2...ij |d̃j
)
.
Lemma 6. Let ǫ > 0, nǫ ∈ N such that nǫǫ > 5/2. Let n > nǫ. Let s ∈ N
such that ωs is the first time that the third symbol appears in ω. Let W be
a minimal representation of an element in Dǫ(n) ∩ H̃(s)
ω . Then,
∑
i1,i2,...,is
|Wi1i2...is | 6
(
1− ǫ
5
)
n+ 2s − 1.
Proof. For definiteness, suppose the sequence ω begins with the symbol 0,
first 1 appears in the t-th position, and first 2 appears in the s-th position.
That is, ω1 = . . . = ωt−1 = 0, ωt = 1, ωm 6= 2 for every m < s, and
ωs = 2. First note that each simple contraction decreases Yi, Zi by at
most 2. Thus,
Yt−1 > Y0− 2
t−1∑
1
αi > Y0− 2
s−1∑
1
αi and Zs−1 > Z0− 2
s−1∑
1
αi. (20)
Since ω1 = 0 there are X0 of letters in W , with 1 in their first coordinate
when written using (17). Thus we modify (19), as done in (7) to be
∑
i1,i2,...,is
|Wi1i2...is | 6 n+ 2s − 1−
s−1∑
1
αi −X0.
“adm-n3” — 2021/1/3 — 11:48 — page 111 — #117
S. T. Samarakoon 111
Similarly, since ωt = 1 and ωs = 2, we get
∑
i1,i2,...,is
|Wi1i2...is | 6 n+ 2s − 1−
s−1∑
1
αi −X0 − Yt−1 − Zs−1. (21)
Now let us show that X0 + Yt−1 + Zs−1 +
∑s−1
1 αi > nǫ/5. To the
contrary assumeX0+Yt−1+Zs−1+
∑s−1
1 αi 6 nǫ/5. Therefore,
∑s−1
1 αi 6
nǫ/5 and by (20) and (21),we get
X0 + Y0 + Z0 6 X0 +
(
Yt−1 + 2
s−1∑
1
αi
)
+
(
Zs−1 + 2
s−1∑
1
αi
)
6
(
X0 + Yt−1 + Zs−1 +
s−1∑
1
αi
)
+ 3
(
s−1∑
1
αi
)
6
4
5
nǫ.
But n = |W | 6 |W |a + |W |x +X0 + Y0 +Z0 6
n+1
2 + n
2 − nǫ+ 4
5nǫ, since
|W |x 6 (1/2− ǫ)n by (13). Thus nǫ 6 5/2, which is a contradiction. So
X0 + Yt−1 + Zs−1 +
∑s−1
1 αi > nǫ/5. Therefore,
∑
i1,i2,...,is
|Wi1i2...is | 6
(
1− ǫ
5
)
n+ 2s − 1.
Proof of Theorem 3. Take a fixed 0 < ǫ < 1/2. Suppose first that there
are positive integers k, s, such that there exists an infinite set N0 ⊂ N
where ∣∣∣H̃(s)
σkω
∩ F ǫ
σkω(n)
∣∣∣ >
∣∣∣H̃(s)
σkω
∩ Dǫ
σkω(n)
∣∣∣ , (22)
for all n ∈ N0. By Lemma 2 and (11),
λ̃ω 6 λ̃σkω = lim
n
|γ̃σkω(n)|1/n
= lim
n
|γ′
G̃
σkω
,S̃
σkω
(n)|1/n = lim
n∈N0
|γ′
G̃
σkω
,S̃
σkω
(n)|1/n
= lim
n∈N0
(∣∣∣H̃(s)
σkω
∩ F ǫ
σkω(n)
∣∣∣+
∣∣∣H̃(s)
σkω
∩ Dǫ
σkω(n)
∣∣∣
)1/n
.
Using (22), we get
λ̃ω 6 lim
n∈N0
(
2
∣∣∣H̃(s)
σkω
∩ F ǫ
σkω(n)
∣∣∣
)1/n
= lim
n∈N0
(∣∣∣H̃(s)
σkω
∩ F ǫ
σkω(n)
∣∣∣
)1/n
6 lim
n∈N0
∣∣F ǫ
σkω(n)
∣∣1/n 6 lim
n
∣∣F ǫ
σkω(n)
∣∣1/n .
“adm-n3” — 2021/1/3 — 11:48 — page 112 — #118
112 On growth of G̃ω
Using Corollary 1 we get
λ̃ω 6 (1− 2ǫ)−1/2(ǫ/3)−ǫ. (23)
Now suppose that for every k, s ∈ N, there exists an N(k, s) such that
for all n > N(k, s),
∣∣∣H̃(s)
σkω
∩ F ǫ
σkω(n)
∣∣∣ <
∣∣∣H̃(s)
σkω
∩ Dǫ
σkω(n)
∣∣∣ . (24)
As before, let H̃
(s)
ω (n) := B̃ω(n) ∩ H̃(s)
ω and H̃
(s)
σkω
(n) := B̃σkω(n) ∩ H̃
(s)
σkω
.
Let ω = ω1 . . . ωs1ωs1+1 . . . ωs1+s2ωs1+s2+1 . . . ωs1+s2+s3 . . . where s1 is the
first time third symbol appears in ω, s2 is the first time third symbol
appears in σs1ω, and so on.
Since [G̃ω : H̃
(s1)
ω ] 6 22
s1−1 =: K1, there is a fixed Schreier system
of representatives of the right cosets of G̃ω modulo H̃
(s1)
ω with Schreier
representatives of length less than K1. So for any g ∈ B̃ω(n), there are
h ∈ H̃
(s1)
ω , l a Schreier representative such that g = hl and since |l| 6 K1,
we have |h| 6 n+K1. Therefore,
∣∣∣B̃ω(n)
∣∣∣ 6 K1
∣∣∣H̃(s1)
ω (n+K1)
∣∣∣ . (25)
Let N1 = max{nǫ, N(0, s1)}, where nǫ is defined in Lemma 6 and N(0, s1)
is defined in (24). Note that
∣∣∣H̃(s1)
ω (n+K1)
∣∣∣ = 1 +
n+K1∑
k=1
∣∣∣H̃(s1)
ω (n+K1) ∩
(
B̃ω(k) \ B̃ω(k − 1)
)∣∣∣
6 N1
∣∣∣B̃ω(N1)
∣∣∣+
n+K1∑
k=N1
∣∣∣H̃(s1)
ω (n+K1) ∩
(
B̃ω(k) \ B̃ω(k − 1)
)∣∣∣ .
From (24), for k > N1,
∣∣∣H̃(s1)
ω (n+K1) ∩
(
B̃ω(k) \ B̃ω(k − 1)
)∣∣∣
=
∣∣∣H̃(s1)
ω (n+K1) ∩ F ǫ(k)
∣∣∣+
∣∣∣H̃(s1)
ω (n+K1) ∩ Dǫ(k)
∣∣∣
6 2
∣∣∣H̃(s1)
ω (n+K1) ∩ Dǫ(k)
∣∣∣ .
Therefore,
∣∣∣H̃(s1)
ω (n+K1)
∣∣∣ 6 N1
∣∣∣B̃ω(N1)
∣∣∣+ 2
n+K1∑
k=N1
∣∣∣H̃(s1)
ω (n+K1) ∩ Dǫ(k)
∣∣∣ .
“adm-n3” — 2021/1/3 — 11:48 — page 113 — #119
S. T. Samarakoon 113
Now using Lemma 6,
∣∣∣H̃(s1)
ω (n+K1)
∣∣∣ 6 N1
∣∣∣B̃ω(N1)
∣∣∣+ 2
∑
j1,...,j2s1
∣∣∣B̃σs1ω(j1)
∣∣∣ . . .
∣∣∣B̃σs1ω(j2s1 )
∣∣∣ ,
(26)
where
2s1∑
i=1
ji 6
(
1− ǫ
5
)
(n+K1) + 2s1 − 1.
Note that
λ̃σs1ω = lim
j
|B̃σs1ω(j)|1/j ,
and therefore, for each δ > 0, there exists an J = J(δ) such that for j > J ,
|B̃σs1−1ω(j)| 6 (λ̃σs1ω + δ)j .
Thus for all j
|B̃σs1−1ω(j)| 6 |B̃σs1−1ω(J)|(λ̃σs1ω + δ)j ,
which implies
∣∣∣B̃σs1ω(j1)
∣∣∣ . . .
∣∣∣B̃σs1ω(j2s1 )
∣∣∣ 6
∣∣∣B̃σs1−1ω(J)
∣∣∣
2s1
(λ̃σs1ω + δ)
∑2s1
i=1 ji
6
∣∣∣B̃σs1−1ω(J)
∣∣∣
2s1
(λ̃σs1ω + δ)(1−
ǫ
5)(n+K1)+2s1−1. (27)
The number of summands in the right hand side of (26) is
((
1− ǫ
5
)
(n+K1) + 2s1 − 1 + 2s1
2s1
)
6
(
n+K1 + 2s1+1 − 1
2s1
)
6 (n+K1 + 2s1+1 − 1)2
s1
. (28)
Now by (25), (26), (27) and (28) we get
∣∣∣B̃ω(n)
∣∣∣ 6 K1N1
∣∣∣B̃ω(N1)
∣∣∣
+
(
2K1(n+K1 + 2s1+1 − 1)2
s1
∣∣∣B̃σs1−1ω(J)
∣∣∣
2s1
×(λ̃σs1ω + δ)(1−
ǫ
5)(n+K1)+2s1−1
)
.
Therefore,
λ̃ω = lim
n
∣∣∣B̃ω(n)
∣∣∣
1/n
6
(
λ̃σs1ω + δ
)(1− ǫ
5)
.
“adm-n3” — 2021/1/3 — 11:48 — page 114 — #120
114 On growth of G̃ω
Since δ is arbitrary,
λ̃ω 6
(
λ̃σs1ω
)(1− ǫ
5)
.
In the same way, still under the assumption (24), and replacing ω by
ω, σs1ω, σs1+s2ω, σs1+s2+s3ω, . . ., we get
λ̃ω 6
(
λ̃σs1ω
)(1− ǫ
5)
λ̃σs1ω 6
(
λ̃σs1+s2ω
)(1− ǫ
5)
λ̃σs1+s2ω 6
(
λ̃σs1+s2+s3ω
)(1− ǫ
5)
...
Thus for each k ∈ N,
λ̃ω 6
(
λ̃σs1+...+skω
)(1− ǫ
5)
k
. (29)
But the growth index λ of a group with 8 generators of order 2 cannot
exceed 9. Since k may be chosen arbitrarily large, it follows from (29) that
λ̃ω = 1. If there exists an ǫ > 0 satisfying (24), then λ̃ω = 1. If not, then
for all ǫ > 0 we have (22). Thus by (23) and
lim
ǫ→0
(1− 2ǫ)−1/2(ǫ/3)−ǫ = 1,
we get λ̃ω = 1 in all cases. Since λ̃ω = 1, G̃ω has subexponential growth.
We knowGω ⊂ G̃ω and by [12],Gω is of intermediate growth. Therefore
G̃ω is of intermediate growth.
Note that the Theorem 1 follows directly from Proposition 2, Proposi-
tion 3, and Theorem 3.
3. Growth bounds for G̃ω
Proposition 4. Let ω ∈ Ω0 ∪ Ω1. Then for each ǫ > 0,
γ
G̃ω
(n) � exp
(
n
log2+ǫ(n)
)
.
“adm-n3” — 2021/1/3 — 11:48 — page 115 — #121
S. T. Samarakoon 115
Proof. Let ω ∈ Ω0 ∪ Ω1. We may assume ω has infinitely many 0’s and
2’s. Then, by (1), bω as a sequence of P ’s and I’s contains both symbols
infinitely often. By Theorem 2 of [7] the group generated by elements
a, bω, x has growth bounded below by exp
(
n
log2+ǫ(n)
)
. Since G̃ω contains
the elements a, bω, x, we get the required result.
Theorem 2′. Let ω ∈ Ω∗
1. Then,
γ
G̃ω
(n) � exp
(
n log (log (n)
log (n)
)
.
Proof. Since ω ∈ Ω∗
1, there is an N such that σNω contains exactly two
symbols, say i, j. Then by Lemma 3, G̃σNω = GσNω. By Theorem 3 of [7],
we get
γ
G̃σnω
(n) � exp
(
n log (log (n)
log (n)
)
,
and therefore,
γ
G̃ω
(n) ≈
(
γ
G̃σnω
(n)
)2N
�
(
exp
(
n log (log (n)
log (n)
))2N
≈ exp
(
n log (log (n)
log (n)
)
.
While Theorem 3 states that G̃ω has intermediate growth for all ω ∈ Ω0,
for homogeneous sequences from Ω∗
0, we can actually provide an explicit
upper bound on growth.
Theorem 2′′. Let ω ∈ Ω∗
0. Then,
γ
G̃ω
(n) 6 exp
(
n log (log (n)
log (n)
)
.
Proof. The proof follows similarly as of the proof of Theorem 3 of [7] by
replacing Lemma 6.2 (1) of [7] by Lemma 6.
Theorem 2′ together with Theorem 2′′ implies Theorem 2.
“adm-n3” — 2021/1/3 — 11:48 — page 116 — #122
116 On growth of G̃ω
References
[1] L. Bartholdi, The growth of Grigorchuk’s torsion group, Int. Math. Res. Not. IMRN,
N.20, 1998, pp.1049-1054.
[2] L. Bartholdi, A Wilson group of non-uniformly exponential growth, C. R. Math.
Acad. Sci. Paris, 336, 2003, N.7, pp.549-554.
[3] M. G. Benli, R. I. Grigorchuk, T. Nagnibeda, Universal groups of intermediate
growth and their invariant random subgroups, Funct. Anal. Appl., 49, 2015, N.3,
pp.159-174.
[4] L. Bartholdi, A. Erschler, Groups of given intermediate word growth, Ann. Inst.
Fourier (Grenoble), 64, 2014, N.5, pp.2003-2036.
[5] L. Bartholdi, R. I. Grigorchuk, On the spectrum of Hecke type operators related
to some fractal groups, Tr. Mat. Inst. Steklova, N.231, 2000, Din. Sist., Avtom. i
Beskon. Gruppy, pp.5-45; translation in Proc. Steklov Inst. Math., 2000, no. 4(231),
pp.1-41.
[6] L. Bartholdi, R. I. Grigorchuk, On parabolic subgroups and Hecke algebras of some
fractal groups, Serdica Math. J., 28, 2002, N.1, pp.47-90.
[7] A. Erschler, Boundary behavior for groups of subexponential growth, Ann. of Math.,
160, 2004, N.3, pp.1183-1210.
[8] A. Erschler, T. Zheng, Growth of periodic Grigorchuk groups, Invent. math., 219,
2020, pp.1069-1155.
[9] D. Francoeur, On the subexponential growth of groups acting on rooted trees, Groups
Geom. Dyn., 14, 2020, N.1, pp.1-24.
[10] R. I. Grigorchuk, On Burnside’s problem on periodic groups, Funct. Anal. Appl.,
14, 1980, N.1, pp.41-43.
[11] R. I. Grigorchuk, On the Milnor problem of group growth, Soviet Math. Dokl., 28,
1983, N.1, pp.23-26.
[12] R. I. Grigorchuk, Degrees of growth of finitely generated groups and the theory of
invariant means, Izv. Akad. Nauk SSSR Ser. Mat., 48, 1984, N.5, pp.939-985.
[13] R. I. Grigorchuk, Construction of p-groups of intermediate growth that have a
continuum of factor-groups, Algebra Logika, 23, 1984, N.4, pp.383-394.
[14] R. I. Grigorchuk, Degrees of growth of p-groups and torsion-free groups, Math.
USSR-Sb., 54, 1986, N.1, pp.185-205.
[15] R. I. Grigorchuk, On growth in group theory, Proceedings of the International
Congress of Mathematicians Vol I (August 21-29, 1990), Kyoto, Japan, Math. Soc.
Japan, 1991, pp.325-338.
[16] M. Kassabov, I. Pak, Groups of Oscillating Intermediate Growth, Ann. of Math.,
177, 2013, N.3, pp.1113-1145.
[17] J. Milnor, Problem 5603, Amer. Math. Monthly, 75, 1968, N.6, pp.685-686.
[18] R. Muchnik, I. Pak, On growth of Grigorchuk groups, Internat. J. Algebra Comput.
11, 2001, N.1, pp.1-17.
[19] V. Nekrashevych, Palindromic subshifts and simple periodic groups of intermediate
growth, Ann. of Math., 187, 2018, N.3, pp.667-719.
[20] A. I. Schwarz, A volume invariant of covering, Dokl. Akad. Nauk SSSR, N.105,
1955, pp.32-34.
“adm-n3” — 2021/1/3 — 11:48 — page 117 — #123
S. T. Samarakoon 117
Contact information
Supun Thamara
Samarakoon
Department of Mathematics
Mailstop 3368
Texas A&M University
College Station, TX 77843-3368
United States
E-Mail(s): sts@tamu.edu
Web-page(s): www.math.tamu.edu/~stsamster
Received by the editors: 06.09.2019
and in final form 30.06.2020.
mailto:sts@tamu.edu
www.math.tamu.edu/~stsamster
S. T. Samarakoon
|