On the subexponential growth of groups acting on rooted trees
Dominik Francoeur



We show that every group in a large family of (not necessarily torsion) spinal groups acting on the ternary rooted tree is of subexponential growth.


Topological Interference Management with 
Decoded Message Passing
    Xinping Yi, Member, IEEE and Giuseppe Caire, Fellow, IEEE
 
This work has been presented in part at Proc. IEEE Int. Symp. Information Theory (ISIT'16), Barcelona, Spain, Jul. 2016.
X. Yi and G. Caire are with Communication and Information Theory Chair in Department of Electrical Engineering and Computer Science at Technische Universität Berlin, 10587 Berlin, Germany. (email: {xinping.yi, caire}@tu-berlin.de)

    December 30, 2023
================================================================================================================================================================================================================================================================================================================================================================================================================================






§ INTRODUCTION


Word growth is an important quasi-isometry invariant of finitely generated groups. Such groups can be broadly divided into three distinct classes: groups of polynomial growth, groups of exponential growth and groups of intermediate growth (that is, groups whose growth is faster than any polynomial but slower than exponential).

While the existence of groups of polynomial or exponential growth is readily established, the question is far less obvious in the case of groups of intermediate growth and was first raised by Milnor in 1968 (<cit.>). It was settled by Grigorchuk in 1983 <cit.> when he proved that the infinite, finitely generated torsion group defined in <cit.>, now known as the first Grigorchuk group, is of intermediate growth.

Since this initial discovery, many other groups of intermediate growth have been found. One of those, now known as the Fabrykowski-Gupta group, was first studied by Fabrykowski and Gupta in <cit.> and in <cit.>. It is a self-similar branch group acting on the ternary rooted tree. The Fabrykowski-Gupta group was later revisited by Bartholdi and Pochon in <cit.>, where they provided a different proof of the fact that its growth is intermediate, along with bounds on the growth.

In order to establish their results, Bartholdi and Pochon proved that under suitable conditions on the length of words, the growth of a self-similar group acting on a rooted tree is subexponential if and only if the growth of a subset of elements (those for which the projection to a certain fixed level does not reduce the length) is subexponential.

It turns out that the same holds if we consider the subset of elements whose length is never reduced by the projection to any level. As this set is smaller than the one considered by Bartholdi and Pochon, it can potentially be easier to show that its growth is subexponential.

After reviewing some basic results and definitions in Section <ref>, we will define non-ℓ_1-expanding similar families of groups of rooted tree automorphisms and prove a generalized Bartholdi-Pochon criterion for such families of groups in Section <ref>. We will then use it in Section <ref> to prove that a large family of spinal groups acting on the ternary rooted tree are of subexponential growth.





§ PRELIMINARIES






 §.§ Word growth


Given a finite and symmetric (i.e. closed under the operation of taking the inverse) generating set of a group, one can construct a natural metric on the group called the word metric.


Let G be a finitely generated group and S be a symmetric finite generating set. The word norm on G (with respect to S) is the map

    |·|  G    →
    
    g   ↦min{k∈| g=s_1… s_k, s_i∈ S}.

The word metric on G (with respect to S) is the metric

    d G× G    →
    
    (g,h)   ↦ |g^-1h|

induced by the word norm on G.

The word metric is simply the metric coming from the Cayley graph of G with the generating set S.

It is clear from the definition that every ball of radius n in G (with the word metric) is finite. We will be interested in seeing how quickly these balls grow.

Let G=⟨ S ⟩, where S is symmetric and finite. The map

    γ_G,S   →
    
    n   ↦|B_G,S(n)|,

where B_G,S(n) is the ball of radius n centred at the identity in the word metric of G with respect to S, is the growth function of G (with respect to S).


The growth function of a group depends on the generating set we choose. In order to remove this dependence, we introduce an equivalence relation on functions.


Given two non-decreasing functions f,g →, we write f≲ g if there exists C∈^* such that f(n)≤ g(Cn) for all n∈^*. The functions f and g are said to be equivalent, written f∼ g, if f≲ g and g≲ f.



Let G be a finitely generated group and S, T be two finite symmetric generating set. Then, γ_G,S∼γ_G,T.


Let 

    C=max_t∈ T{|t|_S},

where |·|_S is the norm on G with respect to S. Then, clearly, for all g∈ G, we have |g|_S ≤ C|g|_T. Hence,

    γ_G,T(n) ≤γ_G,S(Cn),

so γ_G,T≲γ_G,S. The result follows from the symmetry of the argument.


Thanks to proposition <ref>, the equivalence class of the growth function is independent of the choice of generating set. For this reason, we will often omit the reference to the generating set and write simply γ_G for the growth function of the group G.


Let f→ be a non-decreasing function. We say that


  * f is of polynomial growth if there exists d∈ such that f≲ n^d

  * f is of superpolynomial growth if n^d ⋦ f for all d∈

  * f is of exponential growth if f∼ e^n

  * f is of subexponential growth if f⋦ e^n

  * f is of intermediate growth if f is of superpolynomial growth and of subexponential growth.




The above definitions do not depend on the exact function f, but only on its equivalence class.


Remark <ref> allows us to define growth for groups.


A finitely generated group G is said to be of polynomial, superpolynomial, exponential, subexponential or intermediate growth if for any (and hence all) generating set S, the growth function γ_G,S is of polynomial, superpolynomial, exponential, subexponential or intermediate growth, respectively.



Since the growth of a free group is exponential, a finitely generated group cannot have a growth faster than exponential.


In what follows, we will be interested mainly in distinguishing between groups of exponential or subexponential growth. For this purpose, it will be convenient to study a quantity called the exponential growth rate of the group.


Let G be a finitely generated group and S be a finite generating set. The limit

    κ_G,S = lim_n→∞γ_G,S(n)^1/n

exists.


It follows easily from the definition that for all n,m∈,

    γ_G,S(n+m) ≤γ_G,S(n)γ_G,S(m).

Hence, lnγ_G,S is a subadditive function, so according to Fekete's subadditive lemma, the limit

    lim_n→∞lnγ_G,S(n)/n

exists. The result follows.



The limit

    κ_G,S = lim_n→∞γ_G,S(n)^1/n

is the exponential growth rate of the group G (with respect to the generating set S).



Let G be a finitely generated group with a finite symmetric generating set S. Then, κ_G,S > 1 if and only if G is of exponential growth.


It will sometimes be more convenient to consider spheres instead of balls. In the case of infinite finitely generated groups, the exponential growth rate can also be calculated from the size of spheres.


Let G be an infinite finitely generated group with finite symmetric generating set S. Then,

    κ_G,S = lim_n→∞|Ω_G,S(n)|^1/n,

where Ω_G,S(n) is the sphere of radius n in the word metric on G with respect to S.


It follows from the definition of the word metric that Ω_G,S(n + m) ≤Ω_G,S(n)Ω_G,S(m), so by Fekete's subadditive lemma, the limit exists.

Since Ω_G,S(n)≤γ_G,S(n), we have lim_n→∞|Ω_G,S(n)|^1/n≤κ_G,S. On the other hand,

    γ_G,S(n)    = ∑_i=0^n|Ω_G,S(i)|
       ≤ (n+1)|Ω_G,S(s(n))|

where s(n)∈{0,1,…, n} is such that |Ω_G,S(s(n))|≥ |Ω_G,S(i)| for all i≤ i ≤ n. Hence,

    κ_G,S   ≤lim_n→∞ (n+1)^1/n|Ω_G,S(s(n))|^1/n
       =lim_n→∞(|Ω_G,S(s(n))|^1/s(n))^s(n)/n
       =(lim_n→∞ |Ω_G,S(n)|^1/n)^(lim_n→∞s(n)/n)
       ≤lim_n→∞ |Ω_G,S(n)|^1/n

(this uses the fact that G is infinite, so |Ω_G,S(n)| ≥ 1 for all n∈, and that s(n) is a non-decreasing function bounded from above by n).





 §.§ Word pseudometrics


Sometimes, instead of the word metric, it might be more convenient to consider a word pseudometric.


Let G be a finitely generated group and S be a symmetric finite set generating G. A map |·| S→{0,1} that associates to every generator a length of 0 or 1 will be called a pseudolength on S. A pseudolength can be extended to a map

    |·| G    →
    
    g    ↦min_g=s_1… s_k, s_i∈ S{∑_i=1^k|s_i| }

called the word pseudonorm of G (associated to (S, |·|)). The corresponding pseudometric

    d G× G    →
    
    (g,h)    ↦ |g^-1h|

is the word pseudometric of G (associated to (S, |·|)).


For the growth function to make sense with the word pseudometric, though, there must be only a finite number of elements with length 0. In this case, the growth function is well defined and equivalent to the growth function given by the word metric.


Let G be a group generated by a finite symmetric set S and |·|  S →{0,1} be a pseudolength on S. If the subgroup

    G_0 = ⟨{s∈ S | |s|=0}⟩

is finite, then the map

    γ_G,S,|·|   →
    
    n   ↦|B_G,S,|·|(n)|

is well-defined, where B_G,S,|·|(n)={g∈ G | |g|≤ n}. Furthermore, γ_G,S,|·|∼γ_G,S.


To show that γ_G,S,|·| is well-defined, we need to show that

    |B_G,S,|·|(n)| < ∞

for every n∈. For g∈ G with |g|=n, it follows from the definition of the word pseudonorm that there exist s_1,…, s_n ∈ S_1, g_0,…, g_n∈ G_0 such that

    g=g_0s_1g_1… s_n g_n,

where S_1 = {s∈ S | |s|=1}. Hence,

    |B_G,S,|·|(n)| ≤ |G_0|^n+1|S_1|^n < ∞.


We must now show that the growth function with respect to the word pseudometric is equivalent to the growth function with the word metric. Let us denote by |·|_w the word metric in G with respect to S. Let

    M = max{|g|_w | g∈ G_0}.

Then, the decomposition

    g=g_0s_1g_1… s_n g_n

implies that

    |g|_w    ≤ (n+1)M + n 
       = |g|(M+1) + M 
       ≤ (2M+1)|g|

if |g|≥ 1. Hence, if n≥ 1,

    γ_G,S,|·|(n) ≤γ_G,S((2M+1)n)

so γ_G,S,|·|≲γ_G,S. Since it is clear from the definition that γ_G,S≲γ_G,S,|·|, we have γ_G,S,|·|∼γ_G,S.


Since the growth function coming from a word pseudometric with a finite subgroup of length 0 is equivalent to the growth function coming from a word metric, we will make no distinction between the two in what follows.


The conclusion of proposition <ref> remains valid if we replace γ_G,S by γ_G,S,|·| for some pseudonorm |·|. Hence, we can define an exponential growth rate with respect to a pseudonorm, which we will denote by κ_G,S,|·|. Likewise, the conclusions of proposition <ref> are also true, so the exponential growth rate can be computed from the growth of spheres.






 §.§ Equivalence classes of non-decreasing functions


Given two non-decreasing functions f,g →, we write f≲ g if there exists C∈^* such that f(n)≤ g(Cn) for all n∈^*. The functions f and g are said to be equivalent, written f∼ g, if f≲ g and g≲ f. We say that


  * f is of polynomial growth if there exists d∈ such that f≲ n^d

  * f is of superpolynomial growth if n^d ⋦ f for all d∈

  * f is of exponential growth if f∼ e^n

  * f is of subexponential growth if f⋦ e^n

  * f is of intermediate growth if f is of superpolynomial growth and of subexponential growth.





 §.§ Word pseudometrics and word growth


Given a finite symmetric generating set of a group G, one can construct a natural metric on G called the word metric. For our purposes, it will be more convenient to consider the more general notion of a word pseudometric.


Let G be a finitely generated group and S be a symmetric finite set generating G. A map |·| S→{0,1} that associates to every generator a length of 0 or 1 will be called a pseudolength on S. A pseudolength can be extended to a map

    |·| G    →
    
    g    ↦min_g=s_1… s_k, s_i∈ S{∑_i=1^k|s_i| }

called the word pseudonorm of G (associated to (S, |·|)). The corresponding pseudometric

    d G× G    →
    
    (g,h)    ↦ |g^-1h|

is the word pseudometric of G (associated to (S, |·|)).



If every generator is assigned a length of 1, then the word pseudometric is in fact a metric, called the word metric.


If there is only a finite number of elements with length 0, one can define a growth function for the group with regards to the given pseudometric. The growth function thus obtained is in fact equivalent to the usual growth function.


Let G be a group generated by a finite symmetric set S and |·|  S →{0,1} be a pseudolength on S. If the subgroup

    G_0 = ⟨{s∈ S | |s|=0}⟩

is finite, then the growth function

    γ_G,S,|·|   →
    
    n   ↦|B_G,S,|·|(n)|

is well-defined, where B_G,S,|·|(n)={g∈ G | |g|≤ n}. Furthermore, γ_G,S,|·|∼γ_G,S, where γ_G,S is the usual growth function obtained by giving length 1 to each generator.


To show that γ_G,S,|·| is well-defined, we need to show that

    |B_G,S,|·|(n)| < ∞

for every n∈. For g∈ G with |g|=n, it follows from the definition of the word pseudonorm that there exist s_1,…, s_n ∈ S_1, g_0,…, g_n∈ G_0 such that

    g=g_0s_1g_1… s_n g_n,

where S_1 = {s∈ S | |s|=1}. Hence,

    |B_G,S,|·|(n)| ≤ |G_0|^n+1|S_1|^n < ∞.


We must now show that the growth function with respect to the word pseudometric is equivalent to the growth function with the word metric. Let us denote by |·|_w the word metric in G with respect to S. Let

    M = max{|g|_w | g∈ G_0}.

Then, the decomposition

    g=g_0s_1g_1… s_n g_n

implies that

    |g|_w    ≤ (n+1)M + n 
       = |g|(M+1) + M 
       ≤ (2M+1)|g|

if |g|≥ 1. Hence, if n≥ 1,

    γ_G,S,|·|(n) ≤γ_G,S((2M+1)n)

so γ_G,S,|·|≲γ_G,S. Since it is clear from the definition that γ_G,S≲γ_G,S,|·|, we have γ_G,S,|·|∼γ_G,S.



A word pseudometric yielding a finite subgroup of length 0 will be called a proper word pseudometric. Since the growth function coming from a proper word pseudometric is equivalent to the growth function coming from a word metric, we will make no distinction between the two.


In what follows, we will be interested mainly in distinguishing between groups of exponential or subexponential growth. For this purpose, it will be convenient to study a quantity called the exponential growth rate of the group.


Let G be a finitely generated group, S be a finite symmetric generating set and |·| G → be a proper word pseudonorm. The limit

    κ_G,S, |·| = lim_n→∞γ_G,S, |·|(n)^1/n

exists and is called the exponential growth rate of the group G (with respect to the generating set S and the pseudonorm |·|).



Let G be a finitely generated group with a finite symmetric generating set S and a proper word pseudonorm |·|. Then, κ_G,S,|·| > 1 if and only if G is of exponential growth.


It will sometimes be more convenient to consider spheres instead of balls. In the case of infinite finitely generated groups, the exponential growth rate can also be calculated from the size of spheres.


Let G be an infinite finitely generated group with finite symmetric generating set S and proper word pseudonorm |·|. Then,

    κ_G,S,|·| = lim_n→∞|Ω_G,S,|·|(n)|^1/n,

where Ω_G,S,|·|(n) is the sphere of radius n in the word pseudometric |·|.





 §.§ Rooted trees


Let d>1 be a natural number and T_d be the d-regular rooted tree. The set of vertices of T_d is V(T_d) = X^*, the set of finite words in the alphabet X={1,2,… d}. We will often abuse the notation and write v∈ T_d instead of v∈ V(T_d) or v∈ X^* to refer to a vertex of T_d. The set of edges is

    E(T_d)= {{w,wx}⊂ X^* | w∈ X^*, x∈ X}.

A vertex w'∈ X^* is said to be a child of w∈ X^* if w'=wx for some x∈ X. In this case, w is called the parent of w'. For n∈, the set L_n⊂ X^* of words of length n is called the n-th level of the tree.

The group of automorphisms of T_d, that is, the group of bijections of X^* that leave E(T_d) invariant, will be denoted by (T_d). For G≤(T_d) and v∈ T_d, we will write _G(v) to refer to the stabilizer of v in G. For n∈, we define the stabilizer of the n-th level in G, denoted _G(n), as

    _G(n) = ⋂_v∈ L_n_G(v).

When G=(T_d), we will often simply write (v) and (n) in order to make the notation less cluttered.

For v∈ T_d, we will denote by T_v the subtree rooted at v. This subtree is naturally isomorphic to T_d. Any g∈ St(v) leaves T_v invariant. The restriction of g to T_v is therefore (under the natural isomorphism between T_v and T_d) an automorphism of T_d, which we will denote by g|_v. The map

    φ_v(v)    →(T_d) 
    
    g   ↦ g|_v

is clearly a homomorphism. This allows us to define a homomorphism

    ψ(1)   →(T_d)^d 
    
    g   ↦(g|_1,g|_2,…, g|_d).

We can also define homomorphisms

    ψ_n(n) →(T_d)^d^n

for all n∈^* inductively by setting ψ_1 = ψ and 

    ψ_n+1(g) = (ψ_n(g|_1), ψ_n(g|_2), …, ψ_n(g|_d)).

It is clear from the definition that these homomorphisms are in fact isomorphisms. In what follows, we will use the same notation for those maps and their restriction to some subgroup G≤(T_d). In this case, it is important to note that the maps ψ_n are still injective, but are no longer surjective in general.

There is a faithful action of (d) on T_d given by

    τ(xw) = τ(x)w

where τ∈(d), x∈ X and w∈ X^*. This action gives us an embedding of (d) in T_d and in what follows, we will often identify (d) with its image in T_d under this embedding. The automorphisms in the image of (d) are called rooted automorphisms. Any g∈(T_d) can be uniquely written as g=hτ with h∈(1) and τ∈(d). In a slight abuse of notation, we will often find it more convenient to write

    g=(g_1,g_2,…, g_d)τ,

where (g_1,g_2,…,g_d) = ψ(h).

More generally, for any n∈^*, there is a natural embedding of the wreath product (d)≀…≀(d) of (d) with itself n times in (T_d) and any g∈(T_d) can be written uniquely as g=hτ with h∈(n) and τ∈(d)≀…≀(d). In the same fashion as above, we will often write

    g= (g_11… 1, g_11… 2, …, g_dd… d)τ

where (g_11… 1, g_11… 2, …, g_dd… d) = ψ_n(h).




§ INCOMPRESSIBLE ELEMENTS AND GROWTH




 §.§ Non-ℓ_1-expanding similar families of groups acting on rooted trees


A classical way of showing that a group acting on a rooted tree is of subexponential growth is to show that the projection of elements to some level induces a significant amount of length reduction. We introduce here a class of groups that seem well suited to this kind of argument, non-ℓ_1-expanding similar families of groups acting on rooted trees. This is a restriction of the more general notion of similar families of groups as defined by Bartholdi in <cit.>.

Note that for the rest of this section, d will denote an integer greater than 1.


Let Ω be a set and σΩ→Ω be a map from this set to itself. For each ω∈Ω, let G_ω≤(T_d) be a group of automorphisms of T_d acting transitively on each level, generated by a finite symmetric set S_ω and endowed with a proper word pseudonorm |·|_ω. The family {(G_ω, S_ω, |·|_ω)}_ω∈Ω is a similar family of groups of automorphisms of T_d if for all ω∈Ω and all g∈ G_ω,

    g=(g_1,g_2, …, g_d)τ

with g_1,g_2,…,g_d ∈ G_σ(ω), τ∈(d). Furthermore, if

    ∑_i=1^d |g_i|_σ(ω)≤ |g|_ω,

the similar family {(G_ω, S_ω, |·|_ω)}_ω∈Ω is said to be a non-ℓ_1-expanding similar family of groups of automorphisms of T_d.

In the case where |Ω|=1, a similar family contains only one group, which is then said to be self-similar.



There is a more general notion of a similar family of groups in which the groups need not act on regular rooted trees, but only on spherically homogeneous rooted trees. However, we will not need such generality for what follows.



In what follows, we will frequently consider only (non-ℓ_1-expanding) similar families of the form {(G_ν, S_ν, |·|_ν)}_ν∈, where the map from  to  is the addition by 1. This has the advantage of simplifying the notation without causing any significant loss in generality. Indeed, let {(G_ω, S_ω, |·|_ω)}_ω∈Ω be a (non-ℓ_1-expanding) similar family. Then, for any ω∈Ω, {(G_ν, S_ν, |·|_ν)}_ν∈ is also a (non-ℓ_1-expanding) similar family, where (G_ν, S_ν, |·|_ν) = (G_σ^ν(ω), S_σ^ν(ω), |·|_σ^ν(ω)).





For all ν∈, let G_ν≤(T_d) be a finitely generated subgroup of (T_d) acting transitively on each level with finite symmetric generating set S_ν and proper word pseudonorm |·|_ν. The collection {(G_ν, S_ν, |·|_ν)}_ν∈ is said to be a non-ℓ_1-expanding similar family of groups (of automorphisms of T_d) if for all ν∈ and all g∈ G_ν,

    g=(g_1,g_2, …, g_d)τ

with g_1,g_2,…,g_d ∈ G_ν+1, τ∈(d) and

    ∑_i=1^d|g_i|_ν+1≤ |g|_ν.





If {(G_ν, S_ν, |·|_ν)}_ν∈ is a non-ℓ_1-expanding similar family of groups, then for any ν∈ and s=(s_1,s_2,…,s_d)τ∈ S_ν, we have

    ∑_i=1^d|s_i|_ν+1≤ |s|_ν≤ 1

so there is at most one s_i with positive length (and none if |s|_ν=0).



In order to keep the notation simple, if {(G_ν, S_ν, |·|_ν)}_ν∈ is a non-ℓ_1-expanding similar family of groups, for ν∈, we will write γ_ν for the growth function and κ_ν for the exponential growth rate of G_ν with respect to the pseudonorm |·|_ν.


The exponential growth rates of a non-ℓ_1-expanding similar family of groups form a non-decreasing sequence.


Let {(G_ν,S_ν,|·|_ν)}_ν∈ be a non-ℓ_1-expanding similar family of groups of automorphisms of T_d. For any ν∈,

    κ_ν≤κ_ν+1.



Let n∈ be greater than d and let g∈ G_ν be such that |g|_ν≤ n. We have

    g=(g_1,g_2,…,g_d)τ

with g_1,g_2,…, g_d∈ G_ν+1, τ∈(d) and

    ∑_i=1^d|g_i|_ν+1≤ |g|_ν = n.

Since g is determined by g_1,g_2,…, g_d and τ, we have

    γ_ν(n) ≤ d!∑_r_1+r_2+… + r_d ≤ nγ_ν+1(r_1)γ_ν+1(r_2)…γ_ν+1(r_d).


Let C(k) = γ_ν+1(k)/κ_ν+1^k for any k∈.We have

    γ_ν(n)    ≤ d!∑_r_1+r_2+… + r_d ≤ nC(r_1)κ_ν+1^r_1C(r_2)κ_ν+1^r_2… C(r_d)κ_ν+1^r_d
       =d!κ_ν+1^n ∑_r_1+r_2+… + r_d ≤ nC(r_1)C(r_2)… C(r_d).

Let s(n)∈{1,…, n} be such that C(s(n)) ≥ C(r) for all 1≤ r ≤ n. We then have

    γ_ν(n)    ≤ d!κ_ν+1^n ∑_r_1+r_2+… + r_d ≤ nC(s(n))^d 
       ≤ d! κ_ν+1^n C(s(n))^d n^d

It is clear from the definition that the sequence s(n) is non-decreasing. Therefore, either it stabilizes or it goes to infinity. Since lim_k→∞C(k)^1/k=1, in both cases we have lim_n→∞C(s(n))^1/n=1. Hence,

    κ_ν   =lim_n→∞γ_ν(n)^1/n
       ≤κ_ν+1lim_n→∞ d!^1/n C(s(n))^1/n n^d/n
       =κ_ν+1.





 §.§ Examples


Let us now present some examples of non-ℓ_1-expanding similar families of groups of automorphisms of T_d.



  §.§.§ Spinal groups


Spinal groups were first introduced and studied, in a more restrictive version, by Bartholdi and Šuniḱ in <cit.>. A more general version was later introduced by Bartholdi, Grigorchuk and Šuniḱ in <cit.>. Spinal groups form a large family of groups which include many previously studied examples, such as the Grigorchuk groups and the Gupta-Sidki group. Note that the definition we give here is not the most general one, because we consider only regular rooted trees.

Let B be a finite group and

    Ω = {{ω_ij}_i∈, 1≤ j < d|ω_ij∈(B,(d)), ⋂_i≥ k⋂_j=1^d-1ω_ij = {1}∀ k ∈}

be the set of sequences of homomorphisms from B to (d) such that the intersection of the kernels is trivial no matter how far into the sequence we start. Let

    σΩ   →Ω
    ω = {ω_ij}_i∈, 1≤ j ≤ d - 1   ↦σ(ω) = {ω_(i+1)j}_i∈, 1≤ j ≤ d - 1

be the left-shift (with respect to the first index), which is well-defined thanks to the way the condition on the kernels was formulated.

For each ω = {ω_ij}_i∈, j∈{1,2,…,d-1}∈Ω, we can recursively define a homomorphism

    β_ω G_B    →(T_d) 
    
    b    ↦ (ω_01(b), ω_02(b),…, ω_0(d-1)(b), β_σ(ω)(b))

where, as usual, we identify (d) with rooted automorphisms of T_d. The condition on the kernels of sequences in Ω ensures that this homomorphism is injective. Let us write B_ω = β_ω(B)≤(T_d).

For a fixed ω = {ω_ij}∈Ω, let A_ω≤(d) be any subgroup of (d). For any k∈^*, we then define

    A_σ^k(ω) = ⟨⋃_j=1^dω_kj(B)⟩.



Using the notation above, the group G_ω = ⟨ A_ω, B_ω⟩ for some ω∈Ω and A_ω≤(d) is a spinal group if A_σ^k(ω) acts transitively on {1,2,…,d} for all k∈.



For ω∈Ω and A_ω≤(d), if G_ω = ⟨ A_ω, B_ω⟩ is a spinal group, then G_σ^k(ω) = ⟨ A_σ^k(ω), B_σ^k(ω)⟩ is a spinal group for all k∈.


For any spinal group G_ω, the set S_ω = A_ω∪ B_ω is a finite symmetric generating set. Let |·|_ω S_ω→{0,1} be defined by

    |g|_ω = 
    
    0     if  g∈ A_ω
    
    1     otherwise.

It is clear from the definition that if g∈ S_ω, we have

    g=(g_1,g_2,…,g_d)τ

with τ∈ A_ω, g_1,g_2,…, g_d∈ S_σ(ω) and

    ∑_i=1^d|g_i|_σ(ω) = |g|_ω.

As explained above, |·|_ω can be extended to a word pseudonorm on G_ω that we will also denote by |·|_ω. The set of elements of length 0 in this pseudonorm is exactly A_ω, which is finite, and since it is true for the generators, we have that for g∈ G_ω,

    g=(g_1,g_2,…,g_d)τ

with τ∈ A_ω, g_1,g_2,…, g_d∈ G_σ(ω) and

    ∑_i=1^d|g_i|_σ(ω)≤ |g|_ω.

Hence,

    {G_ω, S_ω, |·|_ω}_ω∈Ω

is a non-ℓ_1-expanding similar family of groups.

Hence, for any ω∈Ω,

    {(G^ω_ν, S^ω_ν, |·|^ω_ν)}_ν∈

is a non-ℓ_1-expanding similar family of groups, where G^ω_ν = G_σ^ν(ω), S^ω_ν = S_σ^ν(ω) and |·|_ν^ω = |·|_σ^ν(ω).



[The first Grigorchuk group]
Let d=2, A = (2)≅/2 and B = (/2)^2. Let a be the non-trivial element of A and b,c,d be the non-trivial elements of B. For x∈{b,c,d}, let ω_x B→ A be the epimorphism that sends x to 1 and the other two non-trivial letters to a. The group G_ω with ω = ω_dω_cω_bω_dω_cω_b… (here, since d-1 = 1, there is only one index) and A_ω=A is the first Grigorchuk group, which was first introduced in <cit.>.

[Grigorchuk groups]
More generally, let d=p, where p is a prime number, A = ⟨(1 2 … p)⟩≅/p and B=(/p)^2. Let

    ϕ_k (/p)^2    →/p
    
    (x,y)    ↦ x+ky

for 0≤ k ≤ p-1 and let

    ϕ_p (/p)^2    →/p
    
    (x,y)    ↦ y.

The groups G_ω with A_ω = A and ω={ω_ij}_i∈, 1≤ j ≤ p-1∈Ω such that ω_i1 =ϕ_k_i for all i∈ and ω_ij = 1 if j 1 are called Grigorchuk groups and were studied in <cit.>.

[Šuniḱ groups]
Let d=p a prime number, A = ⟨(1 2 … p)⟩≅/p and B=(/p)^m for some m∈. Let ϕ (/p)^m→/p be the epimorphism given by the matrix

    [ 0 0 … 0 1 ]

in the standard basis, ρ (/p)^m → (/p)^m be the automorphism given by

    [     0     0     …     0    -1;     1     0     …     0   a_1;     0     1     …     0   a_2;     ⋮     ⋮     ⋱     ⋮     ⋮;     0     0     …     1 a_m-1 ]

in the standard basis, for some a_1,…, a_m-1∈/p, and ω={ω_ij}∈Ω, where

    ω_i1 = ϕ∘ρ^i

and ω_ij = 1 if j 1. For any such ω, we let A_ω = A.

The groups G_ω that can be constructed in this way are exactly the groups that were introduced and studied by Šuniḱ in <cit.>.


[GGS groups]
GGS groups form another important family of examples of spinal groups. They are a generalization of the second Grigorchuk group (introduced in <cit.>) and the groups introduced by Gupta and Sidki in <cit.>. We present here the definition of GGS groups that was given in <cit.>.

Let A=⟨(1 2 … d)⟩≅/d, B=/d and ϵ = (ϵ_1,ϵ_2,…, ϵ_d-1) ∈ (/d)^d such that ϵ 0. Let ω = {ω}_ij∈Ω, where

    ω_ij(1̅) = a^ϵ_j

1̅∈ B is the equivalence class of 1 and a=(1 2 d) ∈ A, and let A_ω = A. If (ϵ_1,ϵ_2,…, ϵ_d-1,d) = 1, then G_ω is called a GGS group.





  §.§.§ Nekrashevych's family of groups 𝒟_ω


Let {0,1}^ be the set of infinite sequences of 0 and 1 and

    σ{0,1}^   →{0,1}^
    ω_0ω_1ω_2…   ↦ω_1ω_2ω_3…

be the left-shift. For ω = ω_0ω_1ω_2…∈{0,1}^, we can recursively define automorphisms β_ω, γ_ω∈(T_2) by

    β_ω   = (α, γ_σ(ω))
    γ_ω   = 
    
    (β_σ(ω), 1)     if ω_0=0 
    
    (1, β_σ(ω))     if ω_0=1

where α∈(T_2) is the non-trivial rooted automorphism of T_2. We can then define the group 𝒟_ω = ⟨α, β_ω, γ_ω⟩. This family of groups was first studied by Nekrashevych in <cit.>.

It follows from the definition that α^2=β_ω^2 = γ_ω^2 = 1. Hence, the set S_ω = {α, β_ω, γ_ω} is a finite symmetric generating set of 𝒟_ω. Let |·|_ω S→{0,1} be given by |α|_ω = 0, |β_ω|_ω = |γ_ω|_ω = 1. Then, the family {(G_ν, S_ν, |·|_ν)}_ν∈ is a non-ℓ_1-expanding similar family of automorphisms of T_2, where G_ν = 𝒟_σ^ν(ω), S_ν = S_σ^ν(ω) and |·|_ν = |·|_σ^ν(ω).





  §.§.§ Peter Neumann's example


We present here a group that first appeared as an example in Neumann's paper <cit.>. The description we use here is based on <cit.>.

Let A=(6) and X={1,2,…,6}. For every couple (a,x)∈ A× X such that x is a fixed point of a, we can recursively define an automorphism of (T_6) by

    b_(a,x) = (1,…, b_(a,x),…, 1)a

where the b_(a,x) is in the xth position. Let

    S={b_(a,x)∈(T_6) | (a,x)∈ A× X },

G=⟨ S ⟩ and |·| G → be the word norm associated to S. Then, it is clear from the definition that {(G_ν,S_ν,|·|_ν)}_ν∈ is a non-ℓ_1-expanding similar family of automorphisms of T_6, where G_ν=G, S_ν=S and |·|_ν = |·| for all ν∈. Hence, G is a non-ℓ_1-expanding self-similar group.






 §.§ Incompressible elements


Let {(G_ν, S_ν, |·|_ν)}_ν∈ be a non-ℓ_1-expanding similar family of groups of automorphisms of T_d. For any k∈^*, we recursively define the sets _k^ν of elements of G_ν which have no length reduction up to level k as

    _k^ν = {g = (g_1,g_2,…, g_d)τ∈ G_ν| g_1,g_2,…, g_d ∈_k-1^ν+1, ∑_i=1^d|g_i|_ν+1 = |g|_ν}

where _0^ν = G_ν for all ν∈.

We will call the set

    _∞^ν = ⋂_k=1^∞_k^ν

the set of incompressible elements of G_ν. This is the set of elements which have no length reduction on any level.



 §.§ Growth of incompressible elements


We will see that if every group in a non-ℓ_1-expanding similar family of groups of automorphisms of T_d is generated by incompressible elements and the sets of incompressible elements grow uniformly subexponentially, then the groups themselves are also of subexponential growth. This result is a generalization of the first part of Proposition 5 in <cit.>. The main difference is that we show here that under our assumptions, it is sufficient to look at the growth of the set _∞^ν of incompressible elements instead of the set _k^ν of elements which have no reduction up to level k for some k∈.


Let A∈ be an integer, {(G_ν, S_ν, |·|_ν)}_ν∈ be a non-ℓ_1-expanding similar family of automorphisms of T_d such that S_ν⊆_∞^ν and |S_ν|≤ A for every ν∈, and let Ω_ν(n) be the sphere of radius n∈ in G_ν with respect to the pseudometric |·|_ν. If there exists a subexponential function δ→ with ln(δ) concave such that for infinitely many ν∈, _∞^ν∩Ω_ν(n) ≤δ(n) for all n∈, then the groups G_ν are of subexponential growth for every ν∈.


The proof is inspired by the one found in <cit.>, with a few key modifications. The idea is to split the set Ω_ν(n) in two, the set of elements which can be written as a product of a few incompressible elements and the set of elements which can only be written as a product of a large number of incompressible elements. The first set grows slowly because there are few incompressible elements, and the second set grows slowly because there is a significant amount of length reduction.

Let us fix ν∈ such that _∞^ν∩Ω_ν(n) ≤δ(n) for all n∈. In what follows, we will show that κ_ν = 1. By Proposition <ref>, this will show that κ_ν' =1 for all ν'≤ν.

Since S_ν⊆_∞^ν, we have that for every g∈ G_ν, the set

    {N∈| g=g_1g_2… g_N, g_i∈_∞^ν, ∑_i=1^N|g_i|_ν = |g|_ν}

is not empty. Hence, we can define

    N(g) = min{N∈| g=g_1g_2… g_N, g_i∈_∞^ν, ∑_i=1^N|g_i|_ν = |g|_ν}.



For any n∈ and 0<ϵ < 1, the sphere of radius n in G_ν, Ω_ν(n), can be partitioned in two by the subsets

    Ω_ν^>(n,ϵ)    = {g∈Ω_ν(n) | N(g) > ϵ n}
    Ω_ν^<(n,ϵ)    = {g∈Ω_ν(n) | N(g) ≤ϵ n}.


Let g∈Ω_ν^>(n,ϵ). By definition of N(g), there exists g_1,g_2,…, g_N(g)∈_∞^ν such that g=g_1g_2… g_N(g) and ∑_i=1^N(g)|g_i|_ν = |g|_ν. Let h_i = g_2i-1g_2i for 1≤ i ≤⌊N(g)/2⌋. Then,

    g=h_1h_2… h_N(g)-1/2g_N(g)    if  N(g)  is odd
    
    h_1h_2… h_N(g)/2    if  N(g)  is even.

Notice that since

    |g|_ν = ∑_i=1^N(g)|g_i|_ν,

we must have |h_i|_ν = |g_2i-1|_ν + |g_2i|_ν. Hence, no h_i can be in _∞^ν (otherwise, this would contradict the minimality of N(g)).

Let

    S(g) = {i | |h_i|_ν≤6/ϵ}

be the set of "small" factors of g and

    L(g) = {i | |h_i|_ν > 6/ϵ}

be the set of "large" factors. Clearly, |S(g)| + |L(g)| = ⌊N(g)/2⌋. Since g∈Ω_ν^>(n,ϵ), N(g) is not too small compared to n, which implies that as long as n is large enough, more than half of the factors of g must be small. More precisely, if n>3/ϵ, then |S(g)| ≥1/2⌊N(g)/2⌋. Indeed, it that were not the case, then we would have |L(g)|> ⌊N(g)/2⌋, so

    n    ≥∑_i=1^⌊N(g)/2|h_i|_ν≥∑_h_i∈ L(g) |h_i|_ν
       > 1/2⌊N(g)/2⌋6/ϵ≥(N(g)-1)/46/ϵ
       > 3/2n - 3/2ϵ
       > n

which is a contradiction. Therefore, if n>3/ϵ,

    |S(g)|    ≥1/2⌊N(g)/2⌋≥N(g)-1/4
       >ϵ/4n - 1/4
       > ϵ/8n.

This means that the number of small factors is comparable with n. This is important because, as we will see, every small factor gives us some length reduction on a fixed level (fixed in the sense that it does not depend on n, but only on ϵ). Hence, on this level, we will see a large amount of length reduction.

For r∈, let

    l_ν(r) = max{k∈|(G_ν∖_∞^ν)∩ B_ν(r) ⊆_k^ν} + 1

where B_ν(r) is the ball of radius r in G_ν. Notice that since (G_ν∖_∞^ν)∩ B_ν(r) is finite and not contained in _∞^ν, l_ν(r) is well-defined (i.e. finite).

Let us consider the l_ν(6/ϵ)th-level decomposition of g,

    g=(g_11… 1, g_11… 2, …, g_dd… d)τ.

Since

    g=h_1h_2… h_N(g)-1/2g_N(g)    if  N(g)  is odd
    
    h_1h_2… h_N(g)/2    if  N(g)  is even,

we have

    ∑_j∈ X^l_ν(6/ϵ) |g_j|_ν + l_ν(6/ϵ)≤(∑_i=1^N(g)-1/2∑_j∈ X^l_ν(6/ϵ)|h_i,j|_ν + l_ν(6/ϵ)) + ∑_j∈ X^l_ν(6/ϵ)|g_N(g),j|_ν + l_ν(6/ϵ)

if N(g) is odd and

    ∑_j∈ X^l_ν(6/ϵ) |g_j|_ν + l_ν(6/ϵ)≤∑_i=1^N(g)/2∑_j∈ X^l_ν(6/ϵ)|h_i,j|_ν + l_ν(6/ϵ)

if N(g) is even, where X^l_ν(6/ϵ) is the set of words of length l_ν(6/ϵ) in the alphabet {1,2,…, d},

    h_i = (h_i,11… 1, h_i, 11… 2, …, h_i, dd… d)τ_i

is the l_ν(6/ϵ)th-level decomposition of h_i and

    g_N(g) = (g_N(g),11… 1, g_N(g), 11… 2, …, g_N(g), dd… d)τ_N(g)

is the l_ν(6/ϵ)th-level decomposition of g_N(g).

It follows from the definition of l_ν(6/ϵ) that h_i∉_l_ν(6/ϵ)^ν for all i∈ S(g). Hence, for all i∈ S(g),

    ∑_j∈ X^l_ν(6/ϵ)|h_i,j|_ν + l_ν(6/ϵ)≤ |h_i|_ν - 1.

Therefore, as long as n>3/ϵ,

    ∑_j∈ X^l_ν(6/ϵ)|g_j|_ν+l_ν(6/ϵ)   ≤ n-|S(g)| 
       <n-ϵ/8n 
       =8-ϵ/8n.

It follows that for n>3/ϵ,

    |Ω_ν^>(n,ϵ)|    ≤∑_k_1+… +k_d^l_ν(6/ϵ)≤8-ϵ/8nC|Ω_ν + l_ν(6/ϵ)(k_1)|… |Ω_l_ν(6/ϵ)(k_d^l_ν(6/ϵ))| 
       ≤(8-ϵ/8n)^d^l_ν(6/ϵ)K(n)κ_ν + l_ν(6/ϵ)^8-ϵ/8n

where C=[G_ν : _Gν(l_ν(6/ϵ))] and K(n) is a function such that

    lim_n→∞K(n)^1/n = 1.


We conclude that, for a fixed ϵ between 0 and 1,

    lim sup_n→∞|Ω_ν^>(n, ϵ)|^1/n≤κ_ν + l_ν(6/ϵ)^8-ϵ/8.


On the other hand,

    |Ω_ν^<(n,ϵ)|    ≤∑_i=1^ϵ n∑_k_1+… + k_i = n∏_j=1^iδ(k_j)
       ≤∑_i=1^ϵ n∑_k_1+… + k_i = nδ(n/i)^i

by lemma 6 of <cit.>, since ln(δ) is concave. Hence, assuming that ϵ < 1/2, we have

    |Ω_ν^<(n,ϵ)|    ≤∑_i=1^ϵ nni-1max_1≤ i ≤ϵ n{δ(n/i)^i}
       ≤ϵ n nϵ nmax_1≤ i ≤ϵ n{δ(n/i)^i}.

Using the fact that nϵ n≤n^ϵ n/(ϵ n )! and Stirling's approximation, we get

    |Ω_ν^<(n,ϵ)| ≤ϵ n (e/ϵ)^ϵ nC(n)/√(2πϵ n)max_1≤ i ≤ϵ n{δ(n/i)^i}

where lim_n→∞C(n) = 1. Therefore,

    lim sup_n→∞|Ω_ν^<(n,ϵ)|^1/n≤(e/ϵ)^ϵlim sup_n→∞δ(n/i_n)^i_n/n

where 1≤ i_n ≤ϵ n maximises δ(n/i)^i. Let k_n=n/i_n. Then, 1/ϵ≤ k_n ≤ n. Since lim_k→∞δ(k)^1/k = 1, there must exist N∈ such that sup_1/ϵ≤ k{δ(k)} = sup_1/ϵ≤ k ≤ N{δ(k)}. Hence, there exists some K_ϵ∈ such that K_ϵ≥1/ϵ and lim sup_n→∞δ(n/i_n)^i_n/n = δ(K_ϵ)^1/K_ϵ. We conclude that

    lim sup_n→∞|Ω_ν^<(n,ϵ)|≤(e/ϵ)^ϵδ(K_ϵ)^1/K_ϵ

for some K_ϵ≥1/ϵ.


Since, for any 0<ϵ<1/2, we have |Ω_ν(n)| = |Ω_ν^>(n,ϵ)| + |Ω_ν^<(n,ϵ)|,

    κ_ν   = lim_n→∞|Ω_ν(n)|^1/n = lim_n→∞(|Ω_ν^>(n,ϵ)| + |Ω_ν^<(n,ϵ)|)^1/n
       ≤lim sup_n→∞(2 max{|Ω_ν^>(n,ϵ)|, |Ω_ν^<(n,ϵ)|})^1/n
       = max{lim sup_n→∞|Ω_ν^>(n,ϵ)|^1/n, lim sup_n→∞|Ω_ν^<(n,ϵ)|^1/n}
       ≤max{κ_ν + l_ν(6/ϵ)^8-ϵ/8, e^ϵ(1/ϵ)^ϵδ(K_ϵ)^1/K_ϵ}.

Let us now fix 0<ϵ<1/2. There must exist a k∈ such that

    κ_ν+k≤ e^ϵ(1/ϵ)^ϵδ(K_ϵ)^1/K_ϵ.

Indeed, otherwise we would have κ_ν+i > e^ϵ(1/ϵ)^ϵδ(K_ϵ)^1/K_ϵ for all i∈. In particular, this would imply that

    κ_ν≤κ_ν + l_ν(6/ϵ)^8-ϵ/8.

Let ν'∈ be such that ν' ≥ν + l_ν(6/ϵ) and _∞^ν'∩Ω_ν'(n) ≤δ(n) for all n∈ (such a ν' exist by hypothesis). Then, we would also have

    κ_ν'≤κ_ν' + l_ν'(6/ϵ)^8-ϵ/8,

and so, using the fact that by Proposition <ref>, κ_ν + l_ν(6/ϵ)≤κ_ν', we would have

    κ_ν≤κ_ν' + l_ν'(6/ϵ)^(8-ϵ/8)^2.

By induction, we conclude that for any m∈^*, there exists k_m∈ such that

    κ_ν≤κ_ν + k_m^(8-ϵ/8)^m.

Since |S_i| ≤ A for every i∈, we have that κ_i ≤ A for every i∈. Hence, we get that κ_ν≤ A^(8-ϵ/8)^m for every m∈^*, which implies that κ_ν = 1. This contradicts the hypothesis that κ_ν > e^ϵ(1/ϵ)^ϵδ(K_ϵ)^1/K_ϵ.

Therefore, there must exist some i∈ such that κ_ν + i≤ e^ϵ(1/ϵ)^ϵδ(K_ϵ)^1/K_ϵ. By Proposition <ref>, we must have

    κ_ν≤ e^ϵ(1/ϵ)^ϵδ(K_ϵ)^1/K_ϵ.

As the above inequality is valid for any 0<ϵ<1/2 and 

    lim_ϵ→ 0e^ϵ(1/ϵ)^ϵδ(K_ϵ)^1/K_ϵ = 1

we must have κ_ν = 1, and so G_ν is of subexponential growth.





§ GROWTH OF SPINAL GROUPS


Using the techniques developed by Grigorchuk in <cit.>, one can show that every spinal group acting on the binary rooted tree is of subexponential growth.

In this section, we will study the growth of some spinal groups acting on the 3-regular rooted tree T_3. We will be able to prove that the growth is subexponential in several new cases. In particular, our results will imply that all the groups in Šuniḱ's family acting on T_3 (Example <ref>) are of subexponential growth. While this was already known for torsion groups, this was previously unknown for groups with elements of infinite order, except for the case of the Fabrykowski-Gupta group.

Unfortunately, we were unable to obtain similar results for spinal groups acting on rooted trees of higher degrees, as the methods used here do not seem to have obvious generalizations in those settings.



 §.§ Growth of spinal groups acting on T_3


Let m∈, /3≅ A = ⟨ (1 2 3) ⟩⊆(3) and B=(/3)^m. Let

    Ω = {{ω_ij}_i∈, 1≤ j ≤ 2|ω_i,1∈(B,A), ω_i,2 = 1, ⋂_i≥ k(ω_ij) = 1 ∀ k∈}

be a set of sequences of homomorphisms of B into A and σΩ→Ω be the left-shift (see Section <ref>). For any ω∈Ω, let us define A_ω = A. Using the notation of Section <ref>, we get spinal groups G_ω = ⟨ A, B_ω⟩ acting on T_3 which naturally come equipped with a word pseudonorm |·|_ω assigning length 0 to elements of A and length 1 to elements of B_ω.


In order to streamline the notation, we will drop the indices ω wherever it is convenient and rely on context to keep track of which group we are working in. We will also drop the second index in the sequences of Ω and write ω=ω_0ω_1…∈Ω, which is a minor abuse of notation.

The set of incompressible elements of G_ω will be denoted by _∞^ω, and we will write _∞^ω(n) for the set of incompressible elements of length n.

We will write a=(1 2 3) ∈ A, and for any b∈ B_ω, we will write b^a^i = a^iba^-i where i ∈/3.



As in the case of the binary tree, we have that for every ω∈Ω, the group G_ω is a quotient of A∗ B_ω. Hence, every element of g_ω can be written as an alternating product of elements of A and B_ω.

It follows that every g∈ G_ω of length n can be written as

    g=β_1^a^c_1β_2^a^c_2…β_n^a^c_na^s

for some s∈/3, β{1,2,…, n}→ B_ω and c{1,2,…, n}→/3 (where we use indices to denote the argument of the function in order to make the notation more readable).



For any n∈ at least 2 and c{1,2,…, n}→/3, we will denote by ∂ c{1,2,… n-1}→/3 the discrete derivative of c, that is,

    ∂ c(k) = c_k+1-c_k.




Let ω∈Ω and g∈ G_ω with |g|=n. Writing 

    g=β_1^a^c_1β_2^a^c_2…β_n^a^c_na^s

for some n∈, s∈/3, β{1,2,…, n}→ B_ω and c{1,2,…, n}→/3, if g∈_∞^ω(n), then there exists m_c∈{1,2,…, n} such that

    ∂ c(k) = 
    2  if  k< m_c 
    
    1  if  k≥ m_c.



If there exists k∈{1,2,…, n-1} such that ∂ c(k) = 0, then c(k)=c(k+1), which means that 

    |g|=|β_1^a^c_1β_2^a^c_2… (β_kβ_k+1)^a^c_k…β_n^a^c_na^s| ≤ n-1

a contradiction. Hence, ∂ c(k)  0 for all k∈{1,2,…, n-1}.

Therefore, to conclude, we only need to show that if ∂ c(k) = 1 for some k∈{1,2,…, n-2}, then ∂ c(k+1)  2. For the sake of contradiction, let us assume that ∂ c(k) = 1 and ∂ c(k+1) = 2 for some k∈{1,2,…, n-2}. Without loss of generality, we can assume that c_k=0 (indeed, it suffices to conjugate by the appropriate power of a to recover the other cases). We have

    β_kβ_k+1^aβ_k+2   = (α_k, 1, β_k)(β_k+1,α_k+1, 1)(α_k+2, 1, β_k+2)
       =(α_kβ_k+1α_k+2, α_k+1, β_kβ_k+2)

for some α_k,α_k+1, α_k+2∈ A. Since

    |α_kβ_k+1α_k+2| + | α_k+1| + |β_kβ_k+2| = 2 < 3 = |β_kβ_k+1^aβ_k+2|,

there is some length reduction on the first level, so g∉_∞^ω.


It follows from Lemma <ref> that an element

    g=β_1^a^c_1β_2^a^c_2…β_n^a^c_na^s∈_∞^ω

is uniquely determined by the data (β, s, c_1, m_c), where β{1,2,…, n}→ B_ω, s,c_1∈/3 and m_c∈{1,2,…, n}. Of course, not every possible choice corresponds to an element of _∞^ω. In what follows, we will bound the number of good choices for (β, s, c_1, m_c).


Let ω = ω_0ω_1ω_2…∈Ω and let l∈ be the smallest integer such that ∩_i=0^l(ω_i) = 1. Then, there exists a constant C_l∈ such that

    |_∞^ω(n)| ≤ C_ln^3^l+2 - 1/2

for all n∈.


Let us fix n∈, s, c_1∈/3 and m_c∈{1,2,…, n}, and let c{1,2,…, n}→/3 be the unique sequence such that c(1)=c_1 and

    ∂ c(k) = 
    2  if  k< m_c 
    
    1  if  k≥ m_c

for all k∈{1,2,… n-1}. We will try to bound the number of maps β{1,2,…,n}→ B_ω∖{1} such that

    g=β_1^a^c_1β_2^a^c_2…β_n^a^c_na^s∈_∞^ω(n).

Assuming that g∈_∞^ω(n), let us look at the first-level decomposition of g,

    g=(g_1,g_2,g_3)a^s.

Since g∈_∞^ω, we must have |g|=|g_1|+|g_2|+|g_3|. As for any k∈{1,2,…,n}, β_k^a^c_k adds 1 to the length of g and to the length of exactly one of g_1,g_2 or g_3 no matter the value of β_k, we conclude that |g_1|, |g_2|, |g_3| do not depend on β.

Since g∈_∞^ω, we must also have that g_1,g_2,g_3∈_∞^ω. Hence, for i=1,2,3, there must exist s^(i),c_1^(i)∈/3, m_c^(i)∈{1,2,…, |g_i|} and β^(i){1,2,…, |g_i|}→ B_σ(ω)∖{1} such that

    g_i=(β_1^(i))^a^c_1^(i)(β_2^(i))^a^c_2^(i)… (β_|g_i|^(i))^a^c_|g_i|^(i)a^s^(i)

where c^(i) is the unique map satisfying c^(i)(1)=c_1^(i) and

    ∂ c^(i)(k) = 
    2  if  k< m_c^(i)
    
    1  if  k≥ m_c^(i).

It is clear that the maps β^(i) are completely determined by the map β. Therefore, to specify g_1,g_2,g_3, we only need to consider s^(i), c_1^(i) and m_c^(i). However, the choice of s^(i), c_1^(i) and m_c^(i) impose some non-trivial conditions on β. Indeed, once these three numbers are fixed, we have

    g_i=a^k_1^(i)□ a^k_2^(i)□…□ a^k_|g_i|^(i)□ a^k_|g_i|+1^(i)

where □ are unspecified elements of B_σ(ω)∖{1} and the k_j are uniquely determined by s^(i), c_1^(i) and m_c^(i). These k_j^(i) completely determine ω_0(β_k) for all but at most one k∈{1,2,…, n}. Indeed, for k∈{1,2,…,n}, we have

    β_k^a^c_k = 
    
    (α_k^ω_0, 1, β_k)     if  c_k=0 
    
    (β_k, α_k^ω_0, 1)     if  c_k=1 
    
    (1, β_k, α_k^ω_0)     if  c_k=2

where α_k^ω_0 = ω_0(β_k)∈ A. As long as ∂ c is constant, c is a subsequence of

    … 021021021 …

or

    … 012012012 …

which means that g_1,g_2 and g_3 will be given by an alternating product of α_k^ω_0 and β_k, except perhaps at m_c, if 1<m_c<n. Let us assume for the sake of illustration that c_m_c-1 = 0 (the other two cases are obtained simply by permuting the indices). In that case, we have

    β_m_c-1β_m_c^a^2β_m_c+1   = (α_m_c-1^ω_0, 1, β_m_c-1)(1,β_m_c, α_m_c^ω_0)(α_m_c+1^ω_0, 1, β_m_c+1)
       =(α_m_c - 1^ω_0α_m_c+1^ω_0, β_m_c, β_m_c-1α_m_c^ω_0β_m_c+1)

Therefore, the choice of s^(i), c_1^(i) and m_c^(i) give us conditions on ω_0(β_k) for all but at most one k.

By induction, on level l+1, the choice of s^(x), c_1^(x),m_c^(x) for all words x of length at most l+1 in the alphabet {1,2,3} (that is, for all vertices of the tree up to level l+1) determine ω_i(β_k) for all 1≤ i ≤ l and for all k∈{1,2,…, n} except for at most ∑_j=0^l3^j = 3^l+1-1/2. Since ∩_i=0^lω_i = {1}, for each k, there is at most one β_k∈ B having the prescribed images ω_i(β_k) for all 1≤ i ≤ l.

Since there are 3^l+2-1/2 vertices in the tree up to level l+1, we have 3^3^l+2-1/2 choices for s(x) and 3^3^l+2-1/2 choices for c_1(x). Since m_c^(x) satisfies 1≤ m_c^(x)≤ n, there are at most n^3^l+2-1/2 choices for m_c^(x). Once all these choices are made, β is completely determined, except for at most 3^l+1-1/2 values. For each of these, we have |B|-1 choices, so there are at most (|B|-1)^3^l+1-1/2 choices for β. Hence, there are at most

    C_ln^3^l+2-1/2

elements in _∞^ω(n), where

    C_l = 3^3^l+2-1(|B|-1)^3^l+1-1/2.




With this, we can prove that many spinal groups are of subexponential growth.


Let ω∈Ω and G_ω be the associated spinal group of automorphisms of T_3. If there exists l∈ such that ∩_i=k^k+l(ω_i) = 1 for infinitely many k∈, then G_ω is of subexponential growth.


According to Proposition <ref>, there exist infinitely many k∈ such that

    |_∞^σ^k(ω)(n)| ≤ C_ln^3^l+2-1/2

for some C_l∈. Since ln(C_ln^3^l+2-1/2) is concave, the result follows from Theorem <ref>.







§ ACKNOWLEDGEMENTS

This work was supported by the Natural Sciences and Engineering Research Council of Canada. The author would like to thank Tatiana Nagnibeda for many useful discussions and suggestions, as well as Laurent Bartholdi and Rostislav Grigorchuk for reading previous versions of this paper and offering helpful comments.














§ GROWTH OF SPINAL GROUPS




 §.§ Growth of spinal groups acting on T_2


In this section, we will show that many spinal groups acting on T_2 are of subexponential growth.


Let m∈^*, A=(2)≅/2 and B=(/2)^m. Let

    Ω = {ω=ω_0ω_1ω_2…∈(B,A)^|⋂_j≥ i (ω_j) = {1}∀ i∈}

be a set of sequences of epimorphisms. Notice that Ω is closed under the left-shift σ. For ω∈Ω, let A_ω = A. Using the notation of Section <ref>, the group G_ω = ⟨ A_ω, B_ω⟩ is a spinal group, and in fact, it is straightforward to show that all spinal groups acting on T_2 are in fact of this form. Again as in Section <ref>, we equip G_ω with the word pseudonorm |·|_ω induced by giving length 0 to the elements of A_ω and length 1 to the non-trivial elements of B_ω.


In what follows, we will use the letter a to denote the non-trivial element of A_ω (for any ω∈Ω). We will also denote by _∞^ω the set of incompressible elements in G_ω.



Since G_ω is a quotient of A_ω∗ B_ω≅ (/2)∗ (/2)^m, every element of G_ω can be written as an alternating product of elements of A_ω and B_ω, and geodesics in G_ω are all of this form. We will often make no distinction between elements of G_ω and reduced words in the alphabet A_ω∪ B_ω, i.e. elements of A_ω∗ B_ω≅ (/2)∗ (/2)^m. This identification is harmless, because passing from reduced words to elements in the group can only reduce the length.



Let g=(g_1,g_2)τ∈ G_ω for some ω∈Ω, where G_ω is the spinal group associated to ω as defined above and τ∈ A_ω. Then, |g_i|_σ(ω)≤|g|_ω + 1/2 (i=1,2).


Let c_ω∈ B_ω. We have c_ω = (ω_0(c),c_σ(ω)), so the left child has length 0 and the right child has length 1, and ac_ω a = (c_σ(ω),ω_0(c)), so the left child has length 1 and the right child has length 0. As g can be written as an alternating product of a and elements of B_ω, we see that only half (plus one to account for parity) of the elements of B_ω in g contribute to length on the left child and the other half only contributes to adding length on the right child. The result follows. 



Let ω=ω_0ω_1ω_2…∈Ω and let G_ω be a spinal group acting on T_2 as defined above. Then, there is at most one element b_ω∈ B_ω such that b_ω∉(ω_i) for all i∈.


Suppose that there exist b_ω, c_ω∈ B_ω such that b_ω, c_ω∉(ω_i) for all i∈. Then, ω_i(b_ω)=ω_i(c_ω)=a for all i∈, where a is the non-trivial element of A. Hence, ω_i(b_ω c_ω) = a^2 = 1 for all i∈, which implies that b_ω = c_ω.



Let G_ω be the spinal group associated to ω=ω_0ω_1ω_2…∈Ω and c∈ B be such that ω_m(c) = 1 for some m∈. Then, for all g,h∈ G_ω such that |g|_ω, |h|_ω≥ 2^m+1-1 and gc_ω h is geodesic, we have

    gc_ω h ∉_∞^ω.



Let us first notice that in order for gc_ω h to be geodesic, g must end with a and h must begin with a.

We will proceed by induction on m. For m=0, we have ω_0(c)=1. Hence, c_ω = (1,c_σ(ω)). Let g=g'd_ω a,h = ae_ω h'∈ G_ω with d_ω, e_ω∈ B_ω and |g'|_ω = |g|_ω -1, |h'|_ω = |h|_ω - 1. Then,

    gc_ω h = g'd_ω a c_ω a e_ω h' = g' (ω_0(d)c_σ(ω)ω_0(e), d_σ(ω)e_σ(ω))h'.

Since

    |ω_0(d)c_σ(ω)ω_0(e)|_σ(ω) + |d_σ(ω)e_σ(ω)|_σ(ω) = 2≤ 3 = |d_ω a c_ω a e_ω|_ω

we clearly have gc_ω h ∉_∞^ω.

Now, let us assume that the result is true for some m∈ and any sequence ω∈Ω and let us show that it must also hold for m+1.

Let c∈ B_ω be such that ω_m+1(c) = 1 and g,h∈ G_ω be such that |g|_ω, |h|_ω≥ 2^m+2-1 and gc_ω h is geodesic. Let us write g=τ_g(g_1,g_2), with τ_g∈ A. If |g_i|_σ(ω) < |g|_ω-1/2 for some i∈{1,2}, then g∉_∞^ω, and so gc_ω h ∉_∞^ω. Indeed, according to Lemma <ref>, we have |g_i|_σ(ω)≤|g|_ω + 1/2 for i=1,2, so if one of these is smaller than |g|_ω - 1/2, we must have |g_1|_σ(ω) + |g_2|_σ(ω) < |g|_ω. Likewise, writing h=(h_1,h_2)τ_h with τ_h∈ A, if |h_i|_σ(ω)<|h|_ω - 1/2 for some i∈{1,2}, then gc_ω h ∉_∞^ω.

If |g_i|_σ(ω)≥|g|_ω-1/2 and |h_i|_σ(ω)≥|h|_ω-1/2 for i=1,2, then we have

    gc_ω h = τ_g(g_1ω_0(c)h_1, g_2c_σ(ω) h_2)τ_h

with |g_2|_σ(ω),|h_2|_σ(ω)≥ 2^m+1-1 and σ(ω)_m(c) = ω_m+1(c)=1. If g_2c_σ(ω)h_2 is not geodesic, then |g_2c_σ(ω)h_2|_σ(ω) < |g_2|_σ(ω) + |c_σ(ω)|_σ(ω) + |h_2|_σ(ω) so gc_ω h∉_∞^ω. On the other hand, if g_2 c_σ(ω) h_2 is geodesic, then the induction hypothesis applies and we conclude that g_2c_σ(ω) h_2∉_∞^ω, which means that gc_ω h∉_∞^ω.



For every ω=ω_0ω_1ω_2…∈Ω, there exists a constant C_ω∈ such that |_∞^ω(n)| ≤ C_ω for all n∈, where _∞^ω(n) is the set of incompressible elements of length n in the spinal group G_ω.


For ω=ω_0ω_1ω_2…∈Ω and c∈ B, let

    l(c) = min{m∈|ω_m(c)=1}

if min{m∈|ω_m(c)=1}∅ and l(c)=0 if ω_m(c)=a for all m∈.

If w∈_∞^ω, then according to Lemma <ref>, for any c∈ B such that there exists m∈ with ω_m(c)=1, a geodesic for w can only contain c_ω in the first 2^l(c)+1 - 1 or in the last 2^l(c)+1 - 1 positions.

Let

    M_ω = max_c∈ B{l(c)}

and let C_ω = 16(|B|-1)^2^2M_ω + 2. Notice that there are at most C_ω/4 reduced words in A∪ B of length smaller that 2^2M_ω + 2.

If g∈_∞^ω is an element of length n ≥ 2^M_ω + 2, we can decompose g as

    g=g_1g_2g_3,

where |g_1|_ω+|g_2|_ω+ |g_3|_ω = |g|_ω and |g_1|_ω, |g_3|_ω≤ 2^M_ω + 1. We have at most 4(|B|-1)^2^M_ω + 1 possibilities for g_1 and 4(|B|-1)^2^M_ω + 1 possibilities for g_2. Since the only elements b_ω∈ B_ω which can appear in a geodesic of g_2 must satisfy ω_m(b)=a for all m∈, it follows from Lemma <ref> that there is at most one possibility for g_2. Hence, there are at most C_ω elements in _∞^ω(n).



Let ω=ω_0ω_1ω_2…∈Ω be such that C_σ^k(ω) ≤ D for some D∈ and infinitely many k∈. Then, G_ω is of subexponential growth.


Thanks to Proposition <ref>, it suffices to apply Theorem <ref> to G_ω with δ(n) = D.



The theorem applies if there exists d∈ such that |∪_i=0^d(ω_k+i)| = 2^m-1 for infinitely many k∈. In particular, all the Šuniḱ groups (see Example <ref>) are of subexponential growth.



Since we are working on the binary tree, where, according to <ref>, there is at most one generator which is never in the kernel, it is possible to extend the proof that Grigorchuk used in <cit.> to show that every spinal group acting on the binary tree is of subexponential growth.





 §.§ Growth of spinal groups acting on T_3


In this section, we will study the growth of some spinal groups acting on the 3-regular rooted tree T_3.

Let m∈, A = ⟨ (1 2 3) ⟩⊆(3) ≅/3 and B=(/3)^m. Let

    Ω = {{ω_ij}_i∈, 1≤ j ≤ 2|ω_i,1∈(B,A), ω_i,2 = 1, ⋂_i≥ k(ω_ij) = 1 ∀ k∈}

be a set of sequences of homomorphisms of B into A and σΩ→Ω be the left-shift (see Section <ref>). For any ω∈Ω, let us define A_ω = A. Using the notation of Section <ref>, we get spinal groups G_ω = ⟨ A, B_ω⟩ acting on T_3 which naturally come equipped with a word pseudonorm |·|_ω assigning length 0 to elements of A and length 1 to elements of B_ω.


In order to streamline the notation, we will drop the indices ω wherever it is convenient and rely on context to keep track of which group we are working in. We will also drop the second index in the sequences of Ω and write ω=ω_0ω_1…∈Ω, which is a minor abuse of notation.

The set of incompressible elements of G_ω will be denoted by _∞^ω, and we will write _∞^ω(n) for the set of incompressible elements of length n.

We will write a=(1 2 3) ∈ A, and for any b∈ B_ω, we will write b^a^i = a^iba^-i where i ∈/3.



As in the case of the binary tree, we have that for every ω∈Ω, the group G_ω is a quotient of A∗ B_ω. Hence, every element of g_ω can be written as an alternating product of elements of A and B_ω.

It follows that every g∈ G_ω of length n can be written as

    g=β_1^a^c_1β_2^a^c_2…β_n^a^c_na^s

for some s∈/3, β{1,2,…, n}→ B_ω and c{1,2,…, n}→/3 (where we use indices to denote the argument of the function in order to make the notation more readable).



For any n∈ at least 2 and c{1,2,…, n}→/3, we will denote by ∂ c{1,2,… n-1}→/3 the discrete derivative of c, that is,

    ∂ c(k) = c_k+1-c_k.




Let ω∈Ω and g∈ G_ω with |g|=n. Writing 

    g=β_1^a^c_1β_2^a^c_2…β_n^a^c_na^s

for some n∈, s∈/3, β{1,2,…, n}→ B_ω and c{1,2,…, n}→/3, if g∈_∞^ω(n), then there exists m_c∈{1,2,…, n} such that

    ∂ c(k) = 
    2  if  k< m_c 
    
    1  if  k≥ m_c.



If there exists k∈{1,2,…, n-1} such that ∂ c(k) = 0, then c(k)=c(k+1), which means that 

    |g|=|β_1^a^c_1β_2^a^c_2… (β_kβ_k+1)^a^c_k…β_n^a^c_na^s| ≤ n-1

a contradiction. Hence, ∂ c(k)  0 for all k∈{1,2,…, n-1}.

Therefore, to conclude, we only need to show that if ∂ c(k) = 1 for some k∈{1,2,…, n-2}, then ∂ c(k+1)  2. For the sake of contradiction, let us assume that ∂ c(k) = 1 and ∂ c(k+1) = 2 for some k∈{1,2,…, n-2}. Without loss of generality, we can assume that c_k=0 (indeed, it suffices to conjugate by the appropriate power of a to recover the other cases). We have

    β_kβ_k+1^aβ_k+2   = (α_k, 1, β_k)(β_k+1,α_k+1, 1)(α_k+2, 1, β_k+2)
       =(α_kβ_k+1α_k+2, α_k+1, β_kβ_k+2)

for some α_k,α_k+1, α_k+2∈ A. Since

    |α_kβ_k+1α_k+2| + | α_k+1| + |β_kβ_k+2| = 2 < 3 = |β_kβ_k+1^aβ_k+2|,

there is some length reduction on the first level, so g∉_∞^ω.


It follows from Lemma <ref> that an element

    g=β_1^a^c_1β_2^a^c_2…β_n^a^c_na^s∈_∞^ω

is uniquely determined by the data (β, s, c_1, m_c), where β{1,2,…, n}→ B_ω, s,c_1∈/3 and m_c∈{1,2,…, n}. Of course, not every possible choice corresponds to an element of _∞^ω. In what follows, we will bound the number of good choices for (β, s, c_1, m_c).


Let ω = ω_0ω_1ω_2…∈Ω and let l∈ be the smallest integer such that ∩_i=0^l(ω_i) = 1. Then, there exists a constant C_l∈ such that

    |_∞^ω(n)| ≤ C_ln^3^l+2 - 1/2

for all n∈.


Let us fix n∈, s, c_1∈/3 and m_c∈{1,2,…, n}, and let c{1,2,…, n}→/3 be the unique sequence such that c(1)=c_1 and

    ∂ c(k) = 
    2  if  k< m_c 
    
    1  if  k≥ m_c

for all k∈{1,2,… n-1}. We will try to bound the number of maps β{1,2,…,n}→ B_ω∖{1} such that

    g=β_1^a^c_1β_2^a^c_2…β_n^a^c_na^s∈_∞^ω(n).

Assuming that g∈_∞^ω(n), let us look at the first-level decomposition of g,

    g=(g_1,g_2,g_3)a^s.

Since g∈_∞^ω, we must have |g|=|g_1|+|g_2|+|g_3|. As for any k∈{1,2,…,n}, β_k^a^c_k adds 1 to the length of g and to the length of exactly one of g_1,g_2 or g_3 no matter the value of β_k, we conclude that |g_1|, |g_2|, |g_3| does not depend on β.

Since g∈_∞^ω, we must also have that g_1,g_2,g_3∈_∞^ω. Hence, for i=1,2,3, there must exist s^(i),c_1^(i)∈/3, m_c^(i)∈{1,2,…, |g_i|} and β^(i){1,2,…, |g_i|}→ B_σ(ω)∖{1} such that

    g_i=(β_1^(i))^a^c_1^(i)(β_2^(i))^a^c_2^(i)… (β_n^(i))^a^c_n^(i)a^s^(i)

where c^(i) is the unique map satisfying c^(i)(1)=c_1^(i) and

    ∂ c^(i)(k) = 
    2  if  k< m_c^(i)
    
    1  if  k≥ m_c^(i).

It is clear that the maps β^(i) are completely determined by the map β. Therefore, to specify g_1,g_2,g_3, we only need to consider s^(i), c_1^(i) and m_c^(i). However, the choice of s^(i), c_1^(i) and m_c^(i) impose some non-trivial conditions on β. Indeed, once these three numbers are fixed, we have

    g_i=a^k_1^(i)□ a^k_2^(i)□…□ a^k_|g_i|^(i)□ a^k_|g_i|+1^(i)

where □ are unspecified elements of B_σ(ω)∖{1} and the k_j are uniquely determined by s^(i), c_1^(i) and m_c^(i). These k_j^(i) completely determine ω_0(β_k) for all but at most one k∈{1,2,…, n}. Indeed, for k∈{1,2,…,n}, we have

    β_k^a^c_k = 
    
    (α_k^ω_0, 1, β_k)     if  c_k=0 
    
    (β_k, α_k^ω_0, 1)     if  c_k=1 
    
    (1, β_k, α_k^ω_0)     if  c_k=2

where α_k^ω_0 = ω_0(β_k)∈ A. As long as ∂ c is constant, c is a subsequence of

    … 021021021 …

or

    … 012012012 …

which means that g_1,g_2 and g_3 will be given by an alternating product of α_k^ω_0 and β_k, except perhaps at m_c, if 1<m_c<n. Let us assume for the sake of illustration that c_m_c-1 = 0 (the other two cases are obtained simply by permuting the indices). In that case, we have

    β_m_c-1β_m_c^a^2β_m_c+1   = (α_m_c-1^ω_0, 1, β_m_c-1)(1,β_m_c, α_m_c^ω_0)(α_m_c+1^ω_0, 1, β_m_c+1)
       =(α_m_c - 1^ω_0α_m_c+1^ω_0, β_m_c, β_m_c-1α_m_c^ω_0β_m_c+1)

Therefore, the choice of s^(i), c_1^(i) and m_c^(i) give us conditions on ω_0(β_k) for all but at most one k.

By induction, on level l+1, the choice of s^(x), c_1^(x),m_c^(x) for all words x of length at most l+1 in the alphabet {1,2,3} (that is, for all vertices of the tree up to level l+1) determine ω_i(β_k) for all 1≤ i ≤ l and for all k∈{1,2,…, n} except for at most ∑_j=0^l3^j = 3^l+1-1/2. Since ∩_i=0^lω_i = {1}, for each k, there is at most one β_k∈ B having the prescribed images ω_i(β_k) for all 1≤ i ≤ l.

Since there are 3^l+2-1/2 vertices in the tree up to level l+1, we have 3^3^l+2-1/2 choices for s(x) and 3^3^l+2-1/2 choices for c_1(x). Since m_c^(x) satisfies 1≤ m_c^(x)≤ n, there are at most n^3^l+2-1/2 choices for m_c^(x). Once all these choices are made, β is completely determined, except for at most 3^l+1-1/2 values. For each of these, we have |B|-1 choices, so there are at most (|B|-1)^3^l+1-1/2 choices for β. Hence, there are at most

    C_ln^3^l+2-1/2

elements in _∞^ω(n), where

    C_l = 3^3^l+2-1(|B|-1)^3^l+1-1/2.




With this, we can prove that many spinal groups are of subexponential growth.


Let ω∈Ω and G_ω be the associated spinal group of automorphisms of T_3. If there exists l∈ such that ∩_i=k^k+l(ω_i) = 1 for infinitely many k∈, then G_ω is of subexponential growth.


According to Proposition <ref>, there exist infinitely many k∈ such that

    |_∞^σ^k(ω)(n)| ≤ C_ln^3^l+2-1/2

for some C_l∈. Since ln(C_ln^3^l+2-1/2) is concave, the result follows from Theorem <ref>.



In particular, all groups in Šuniḱ's family acting on T_3 (Example <ref>) are of subexponential growth. While this was already known for torsion groups, this was previously unknown for groups with elements of infinite order, except for the case of the Fabrykowski-Gupta group.
























plain

