J Ér

Émie Brieussel

GROWTH BEHAVIORS IN THE RANGE e r α

published or not. The documents may come

Growth behaviors in the range e r α

Introduction

The growth function b Γ,S (r) = |S r | of a group Γ with finite generating set S was introduced by Milnor [Mil] in relation with Riemannian geometry. The class b Γ (r) of b Γ,S (r) under the equivalence relation associated to the order f (r) ≤ g(Cr) for some C (written f g) is independant of the generating set S, so that b Γ (r) is a group invariant.

For many groups, e.g. those containing a free semigroup, the growth function is exponential. However, the growth function of a nilpotent group Γ is polynomial b Γ (r) ≈ r d (Γ) where d(Γ) = k.rank(Γ k /Γ k+1 ) is the algebraic degree of nilpotency of Γ = Γ 1 associated to the filtration Γ k+1 = [Γ k , Γ] ( [Bas], [Gui], [Wol]). Conversely, Gromov proved that polynomial growth implies virtual nilpotency ( [Gro], see also [Kle] and [ST] for an explicit version applying to finite groups). This implies in particular that polynomial growth functions are indexed by integers d(Γ) and any two are always comparable for .

In the eighties, Grigorchuk has shown some groups have intermediate growth, i.e. faster than polynomial and slower than exponential. In [START_REF] Grigorchuk | Degrees of growth of finitely generated groups and the theory of invariant means[END_REF], he considers a family indexed by a Cantor set {0, 1, 2} N of groups G ω acting on a binary rooted tree. These groups are commensurable with the infinite torsion groups constructed earlier by Aleshin in [Ale]. Many groups in these families satisfy growth inequalities of the form e r α b Gω (r) e r β for exponents 1 2 ≤ α < β < 1. On the other hand, for some sequences ω, the growth of G ω is "close to" e r . Grigorchuk also proved the existence of uncountable antichains of growth functions (i.e. collections of pairwise non comparable such functions).

Recently, Bartholdi and Erschler have computed the intermediate growth functions of some groups related to the group G (012) ∞ (see [BE]). More precisely, for Γ 0 = Z/2Z X G (012) ∞ and Γ k+1 = Γ k X G (012) ∞ , there are explicit exponents α k < 1 accumulating to 1, such that their growth functions satisfy b Γ k (r) ≈ e r α k .

The purpose of the present article is to draw a panorama of growth behaviors in the range e r α . The two main points are that on the one hand there is a neighborhood of 1 in which any α is the growth exponent of some group, raising an explicit uncountable family of groups for which the growth functions are strictly comparable, and on the other hand, there are groups the growth function of which oscillates between two distinct exponents α < β, which explains non comparison phenomena. More precisely:

Theorem 1.1. Let η ≈ 0.8105 be the real root of X 3 + X 2 + X -2 and α 0 = log 2 log 2-log η ≈ 0.7674. Then for any α 0 ≤ α ≤ β ≤ 1, there exists a group G(α, β) such that: lim inf log log b G(α,β) (r) log r = α and lim sup log log b G(α,β) (r) log r = β.

In particular, there exists a group G(α) such that lim

log log b G(α) (r) log r = α.
The groups G(α, β) will be explicitely described as F X G ω for appropriate sequence ω = ω(α, β). Note that the group G(α 0 ) is precisely the group Γ 0 = Z/2Z X G (012) ∞ considered in [BE]. Also a better study of oscillation phenomena provides uncountable antichains of growth functions satisfying a uniform upper bound e r β for any β > α 0 .

The strategy to prove theorem 1.1 is to construct first the groups G(α) by appropriate sequences ω(α). The construction of the groups G(α, β) with oscillating growth for α < β then follows from the fact that the asymptotic behavior of the growth of G ω depends only on the asymptotic of ω, whereas the first values of the growth function depend only on the first values of ω. This permits to construct groups with different growth behaviors at different scales.

In order to ease notation, adopt the following: Definition 1.2. Given a finitely generated group G, the upper logarithmic growth exponent α(G) and the lower logarithmic growth exponent α(G) are real numbers in [0, 1] defined as: α(G) = lim sup log log b G (r) log r and α(G) = lim inf log log b G (r) log r .

In case of equality, call logarithmic growth exponent the number α(G) = α(G) = α(G).

For submultiplicative functions, inequality b(Cr) ≤ b(r) C implies:

log log b(Cr) log r ≤ log log b(r) log r + log C log r ,
so that the logarithmic growth exponents of groups are independent of the choice of a particular representative b Γ,S (r), i.e. the choice of generating set. Note that if b G (r) e r α , then α(G) = α but the converse is not true, as shown by functions e r α (log r) p for any value of p. In particular, the growth functions of the groups studied here are not computed, but only their logarithmic growth exponents.

The article is structured as follows. Sections 2 and 3 are devoted to the description of the involved groups Γ ω , and in particular the notion of activity of a representative word. Section 4 presents the three main tools of estimation for growth. The activity of words is studied in section 5 to derive precise growth estimates, i.e. construct groups with a given logarithmic growth exponent. Oscillation phenomena are studied in sections 7 and 8, which permits to explain the existence of antichains of growth functions. Some explicit estimates on the frequency of oscillation are given. A few comments and some questions conclude the article.

Note that after this work was first submitted, further computations of growth functions of similar groups have been done in [KP] and [START_REF] Bartholdi | Groups of given intermediate word growth[END_REF]. Also similar estimates on entropy of random walks have been done in [START_REF] Brieussel | Behaviors of entropy on finitely generated groups[END_REF].

The groups involved

2.1. Definition. Following Grigorchuk [START_REF] Grigorchuk | Degrees of growth of finitely generated groups and the theory of invariant means[END_REF], associate to each given sequence ω = ω 0 ω 1 ω 2 . . . in {0, 1, 2} N a group G ω of automorphism of a binary rooted tree T , generated by four elements G ω = a, b ω , c ω , d ω , defined via the wreath product isomorphism:

Aut(T ) Aut(T ) S 2 = (Aut(T ) × Aut(T )) S 2 , (1)
where S 2 acts on the product by permuting components. The generator a = (1, 1)ε, where ε is non-identity in S 2 , is independent of ω and only acts at the root of T . The three other generators are defined recursively by:

b ω = (u b (ω 0 ), b σω ), c ω = (u c (ω 0 ), c σω ), d ω = (u d (ω 0 ), d σω ), ( 2
)
where σ is the shift of sequence σω = ω 1 ω 2 . . . and:

u b   0 1 2   =   a a id   , u c   0 1 2   =   a id a   , u d   0 1 2   =   id a a   . (3)
The group G ω is defined by the sequence ω which rules the embeddings G ω → G σω S 2 . The following relations are easily checked:

a 2 = b 2 ω = c 2 ω = d 2 ω = b ω c ω d ω = id. (4)
In particular, the group generated by b ω , c ω , d ω is a Klein group V = S 2 × S 2 and each of the four generators has order 2 (unless ω is constant), so they generate G ω as a quotient semigroup of Ω ω = {a, b ω , c ω , d ω } * , the free semigroup of words in the generators with concatenation as product. Also note that conjugating by a exchanges the components on the two subtrees, in particular:

ab ω a = (b σω , u b (ω 0 )), ac ω a = (c σω , u c (ω 0 )), ad ω a = (d σω , u b (ω 0 )). (5)
Now following [BE], let ρ = 1 ∞ ∈ ∂T be the rightmost geodesic ray out of the root of T . Note that b ω , c ω , d ω fix ρ independently of ω. Denote X = ρG ω the right orbit of ρ under G ω . The permutational wreath product of G ω and another group F over X is the group:

Γ ω = F X G ω = (Σ X F ) G ω ,
where Σ X F is the group of finitely supported functions ϕ : X → F , on which G ω acts on the left by (g.ϕ)(x) = ϕ(xg), and in particular the supports satisfy supp(g.ϕ) = supp(ϕ)g -1 . The elements are denoted ϕg for ϕ ∈ Σ X F and g ∈ G ω . The computation rule is (ϕ 1 g 1 )(ϕ 2 g 2 ) = (ϕ 1 (g 1 .ϕ 2 ))(g 1 g 2 ). Throughout the present article, assume the group F is finite.

As a generating set, use

S ω = {a} {ϕ f v|v ∈ {id Gω , b ω , c ω , d ω }, f ∈ F }. Note that ρv = ρ, so [ϕ f , v] = id Γω and the set {ϕ f v} generates a finite subgroup in Γ ω , which is abstractly isomorphic to F × V .
2.2. A short history. The groups G ω are commensurable with the groups introduced by Aleshin [Ale], where automata techniques were used to provide a short solution to Burnside's problem. The groups G ω and especially G (012) ∞ have been widely studied especially since they provide the essentially only known exemples of groups of intermediate growth ( [START_REF] Bartholdi | The growth of Grigorchuk's torsion group[END_REF], [START_REF] Bartholdi | Lower bounds on the growth of a group acting on the binary rooted tree[END_REF], [BS], [Bri], [START_REF] Erschler | Boundary behavior for groups of subexponential growth[END_REF], [START_REF] Erschler | Not residually finite groups of intermediate growth, commensurability and nongeometricity[END_REF], [START_REF] Erschler | On the degrees of growth of finitely generated groups[END_REF], [START_REF] Grigorchuk | Degrees of growth of finitely generated groups and the theory of invariant means[END_REF], [START_REF] Grigorchuk | Degrees of growth of p-groups and torsion free groups[END_REF], [MP], [Zuk]). In particular, the best known estimates on the growth of G (012) ∞ are:

Theorem 2.1. e r 0.5207 b G (012) ∞ (r) e r α 0 .
The upper bound comes from [START_REF] Bartholdi | The growth of Grigorchuk's torsion group[END_REF] (see also [MP]) and the lower bound from [Bri] (see also [START_REF] Bartholdi | Lower bounds on the growth of a group acting on the binary rooted tree[END_REF], [Leo]). The estimation on the growth exponents of G ω is tightly related to the contraction of the length of reduced words w = (w 0 , w 1 ) under the wreath product decomposition (1). If for all reduced words, |w 0 | + |w 1 | is a large contraction of |w|, the upper growth exponent is small. If for all pairs of reduced words, |w| is a small dilatation of |w 0 | + |w 1 |, the lower growth exponent is big. As it turns out, the study of dilatation of pair of words is delicate to handle, explaining the large gap between the upper and lower exponents of G (012) ∞ .

In [BE], Bartholdi and Erschler have bypassed this problem, considering (among others) the group F X G (012) ∞ , where F is any finite group, for which they prove:

Theorem 2.2. [BE] b F X G (012) ∞ (r) ≈ e r α 0 .
In short, if the upper estimates still apply, the use of permutational wreath product permits to obtain a good lower bound from small dilatation of some pairs of words. The techniques developed in [BE] are not restricted to the specific sequence ω = (012) ∞ , and can provide a good understanding of growth of Γ ω for rotating sequences ω, as explained below. The construction of an appropriate sequence ω(α) or ω(α, β) will be the key point to prove Theorem 1.1.

A description of the groups

This section aims at giving description of the group Γ ω = F X G ω . Useful notions are that of minimal tree and active set of a word. The active set is very much related with the inverted orbit introduced in [BE].

Lemma 3.1. The group Γ ω = F X G ω embeds cannonically into the finite permutational wreath product Γ σω S 2 . More precisely, the application Φ:

Γ ω → Γ σω S 2 a → (1, 1)a v ω → (u v (ω 0 ), v σω ) ϕ f → (1, ϕ f )
is an injective morphism of groups.

Any γ in Γ ω is decomposed γ = ϕg, with g ∈ G ω and ϕ : X → F . The classical embedding G ω → G σω S 2 provides a decomposition g = (g 0 , g 1 )σ. Also the boundary of the tree can be decomposed into two components ∂T = ∂T 0 ∂T 1 with T t the tree descended from the first level vertex t. In particular, the orbit X inherits this decomposition into X = X 0 X 1 . Set ϕ t = ϕ| Xt the restriction of ϕ to the subset X t of the orbit X. With these notations, the application Φ is given by:

Φ(γ) = (ϕ 0 g 0 , ϕ 1 g 1 )σ ∈ Γ ω S 2 .
In order to prove the lemma, it is sufficient to check that Φ(γγ ) = Φ(γ)Φ(γ ).

Proof. On the one hand, γγ = ϕgϕ g = ϕ(g.ϕ )gg = ψgg , with ψ = ϕ(g.ϕ ). As above set ψ t = ψ| Xt , and as gg = (g 0 g σ(0) , g 1 g σ(1) )σσ , the embedding is:

Φ(γγ ) = (ψ 0 g 0 g σ(0) , ψ 1 g 1 g σ(1) )σσ .
On the other hand:

Φ(γ)Φ(γ ) = (ϕ 0 g 0 , ϕ 1 g 1 )σ(ϕ 0 g 0 , ϕ 1 g 1 )σ = (ϕ 0 g 0 ϕ σ(0) g σ(0) , ϕ 1 g 1 ϕ σ(1) g σ(1) )σσ = (ϕ 0 (g 0 .ϕ σ(0) )g 0 g σ(0) , ϕ 1 (g 1 .ϕ σ(1) )g 1 g σ(1) )σσ
There remains to check ψ t = ϕ t (g t .ϕ σ(t) ), and indeed for any y ∈ X t X:

ψ t (y) = ψ(ty) = (ϕ(g.ϕ ))(ty) = ϕ(ty)((g.ϕ )(ty)) = ϕ(ty)ϕ (ty.g) = ϕ(ty)ϕ (σ(t)(y.g t )) = ϕ t (y)ϕ σ(t) (y.g t ) = ϕ t (y)(g t .ϕ σ(t) )(y).
The embedding ψ : Γ ω → Γ σω S 2 can also be used at the word level. Let us describe the rewriting process of a given word of the form w = a i 1 k 1 ak 2 . . . ak r a i 2 , for

k i = ϕ f i v i in {ϕ f v|v ∈ {id, b ω , c ω , d ω }, f ∈ F },
which is said pre-reduced. Note that any reduced representative word in Γ ω has this form.

Any such word can be rewritten

w = k a 1 k 2 k a 3 k 4 . . . k r a i 3 or w = k 1 k a 2 . . . k r a i 4 , where i j ∈ {0, 1}. Note also that k = ϕ f v ω = (u v (ω 0 ), ϕ f v σω ) = (u v (ω 0 ), k) and k a = (k, u v (ω 0 )
) and remind u v (ω 0 ) ∈ {id, a}. This permits to rewrite w = (w 0 , w 1 )σ(w) via the wreath product embedding, and w 0 , w 1 appear as products of the type w 0 = a ε 1 k 2 a ε 3 k 4 . . . k r and w 1 = k 1 a ε 2 . . . a εr for ε j ∈ {0, 1}. Now reduce w 0 , w 1 to obtain pre-reduced words in S σω , by using the rule

T (w) σ ∅ σ v σ v a εz σ v w z a εz
k i a 0 k i+1 = k i k i+1 = ϕ f i v i ϕ f i+1 v i+1 = ϕ (f i f i+1 ) (v i v i+1 ).
The rewritting process associates to w this representation w = (w 0 , w 1 )σ(w) where σ(w) is the image of w in the quotient group S 2 acting at the root.

The process can be iterated, which provides for any level p a representation w = (w 1 , . . . , w 2 p )σ p (w) with w i pre-reduced words in S σ p ω and σ p (w) ∈ Aut(T 2 (p)) = S 2 • • • S 2 with p factors describes the action of w on the subtree T 2 (p) consisting of the first p levels. Definition 3.2. Given a pre-reduced word w in S ω , define T (w), called minimal tree of w, to be the minimal regular rooted subtree of T such that for any leaf z in ∂T (w), one has |w z | pr ≤ 1 for the word w z obtained by iterated rewritting process, where |w| pr is the number of factors k i = ϕ f i v i in a pre-reduced word w z . Remind that a subtree T is rooted if it contains the root and regular if any vertex in T either has its two descendants in T or none of them. Note that the leaves of ∂T (w) have depth at most log 2 |w| because w 0 , w 1 have length ≤ |w|+1 2 .

The tree T (w) allows a nice description of the action of a word w in Γ ω on T . Indeed, the group element γ = Γω w is described by the following data. First the minimal tree T (w), secondly the permutations σ v ∈ S 2 describing the action at vertex v in the interior of T (w) and third the short words w z = a εz ϕ fz v z a δz for z ∈ ∂T (w). The latter can be refined in the tree action a εz v z a δz as an automorphism of T z the subtree issued from the vertex z and the boundary function ϕ

(x) = id F for all x ∈ ∂T z \ {zε z (1)ρ} and ϕ(zε z (1)ρ) = f z . Call z ∈ ∂T (w) an active leaf if |w z | pr = 1, an inactive leaf if |w z | pr = 0, denote S(w)
the set of active leaves of w, and s(w) = #S(w) its size. Mind that if z is inactive then w z = a εz ∈ S 2 is just a permutation. Note also that regarding the rules of rewritting process |ϕ id F | pr = 1 so that an active leaf does not necessarily act on the tree, nor its boundary (see figure 1).

However, it appears from the description above that the support of ϕ : X → F associated to w is included in {zε z (1)ρ|z is an active leaf}. Call this set the support a priori of ϕ, denoted supp ap (ϕ). Note that for w = a i 1 ϕ f 1 v 1 a . . . aϕ fr v r a i 2 , if i 1 , i 2 , v j are kept fixed and (f 1 , . . . , f r ) are taking all possible values, then any function with support included in supp ap (ϕ) can be obtained. In particular, the support a priori of the function ϕ for the word w depends only on the image in the quotient

Γ ω → G ω , w → g = a i 1 v 1 a . . . av r a i 2 .
Remark 3.3. In order to clarify the notion of support a priori, let us introduce a notion associated to the word combinatorics of the rewritting process of a fixed word w. For z an active leaf of T (w), the rewritting process provides f z as a product of terms f z i in w z (where z is the first ascendant of z), which are themselves products of terms f z j in w z , etc. so eventually f z is a product of terms (f j ) j∈J(z) for a subset J(z) ⊂ {1, . . . , r}. Note that in this situation: z∈S(w) J(z) = {1, . . . , r}.

More generally, if y is a vertex of T , the rewritting process of w provides w y = a i y 1 ϕ f y 1 v y 1 a . . . aϕ f y r y v y y ra i y 2 , and each factor f y i is obtained as an ordered product:

f y i = j∈I(y,i) f y j , ( 6
)
where y is the first ascendant of y, and I(y, i) = {1, . . . , r y } where the disjoint union runs over all direct descendants y of y and i ∈ {1, . . . , r y }. Now the graph with vertex set (f y i ) y∈T,i∈{1,...,ry} and edges pairs of elements appearing on different sides of all possible products ( 6) is a forest, called the ascendance forest of w. It describes the combinatorics of the rewritting process of the word w. It depends only on g = a i 1 v 1 a . . . av r a i 2 . Precisely, this graph is a finite union of trees rooted in f z for each z ∈ S(w) and with respective sets of leaves {f j |j ∈ J(z)}. The ordered product f z = j∈J(z) f j shows that indeed, the function ϕ can take any value at the point zε z (1)ρ.

Proposition 3.4. (Activity of a pre-reduced word) The activity s(w) of a pre-reduced word w = a i 1 ϕ f 1 v 1 a . . . aϕ fr v r a i 2 in Γ ω , S ω , which counts equivalently (1) the size of the set S(w) of active leaves in the minimal tree T (w), (2) the number of components (i.e. trees) in the ascendance forest of w, (3) the size of the support a priori supp ap (ϕ), (4) the size of the inverted orbit O(g -1 ) of the word g -1 in the sense of [BE], depends only on the word w = a i 1 v 1 a . . . av r a i 2 in G ω and satisfies under rewritting process w = (w 0 , w 1 )σ(w), with w 0 , w 1 in S σω :

s(w) = s(w 0 ) + s(w 1 ).
Also there exists a constant C depending only on #F such that:

#{γ ∈ Γ ω |∃w = Γω γ, s(w) ≤ s} ≤ C s .
Proof. The equivalence of (1), ( 2) and (3), as well as the behavior of activity function under rewritting process follow from the descriptions above. Proceed by induction on r to show equivalence with (4

). If w = a i 1 ϕ f 1 v 1 a . . . aϕ fr v r a i 2 = F Γ ϕg then wϕ fn v n = ϕ(g.ϕ fn )gv n . The point g -1 (1 ∞ ) is added to the support a priori of ϕ. This shows supp ap (ϕ) = {(a i 1 v 1 . . . v k a i 2 ) -1 (1 ∞ )|k ≤ n} = O(g -1 )
. Mind that the inverse appears as a difference with [BE] notations, replacing gf by ϕg for elements of F G. Then ϕg = (g.f )g and g -1 supp(f ) = supp(ϕ).

There remains only to show that the number of elements described grows at most exponentially fast with s(w). First check that 2s(w) ≥ #∂T (w) when s(w) ≥ 1, by induction on s(w). If |w| pr = 1, then T (w) is just the root of T . Now if s(w) ≥ 2, then s(w 0 ), s(w 1 ) ≥ 1 by pre-reduction of w, so that induction ensures 2s(w t ) ≥ #∂T (w t ), and the result follows from #∂T (w 0 ) + #∂T (w 1 ) ≥ #∂T (w) by construction of minimal trees. Now if s(w) ≤ s, the minimal tree T (w) has size ≤ 2s. There is 4 2s possibilities for T (w) (Catalan numbers), and then 2 #interior(T (w)) ≤ 2 2s choices for the interior permutations σ v for interior vertices v and finally (2 2 .4.#F ) #∂T (w) ≤ C 2s choices for the boundary short words a εz ϕ fz v z a δz .

Corollary 3.5. The relation between word activity and growth function is two-fold:

(1) b Γω (r) ≥ #F s(w) for any |w| ≤ r. (2) b Γω (r) ≤ C max{s(w)|r≥|w|} .
In particular, word activity governs the growth function.

Proof. Point (1) is clear from remark 3.3 and point (2) from proposition 3.4.

Technics of estimation

4.1. Growth Lemma. The following lemma is used to estimate upper bounds on the growth of activity hence on the growth of groups. It improves on previous versions such as the Growth Theorem in [MP] and Lemma 4.3 in [BE] by keeping track of the constants in terms of the bound on the sequence p(r) of variable depth of recursion.

Lemma 4.1. Given η and a parameter λ

∈ [0, 1], set α = log(2) log(2)-λ log(η) , so that α satisfies 2 = 2 η λ α .
Let ∆ : N → N be a function such that for any r there exists q(r) ≤ p(r) and l 1 , . . . , l 2 p(r) integers such that, for a constant C:

(1) l 1 + • • • + l 2 p(r) ≤ η q(r) r + 2 p C, (2) ∆(r) ≤ ∆(l 1 ) + • • • + ∆(l 2 p(r) ), (3) q(r) p(r) ≥ λ.
Suppose moreover that p(r) ≤ P is bounded. Then ∆(r) ≤ Lr α for some constant L = L(C, P ).

Assume given a trivial bound ∆(r) ≤ Kr. Then L can be chosen L = A P for A depending only on C and K.

Proof. Choose R 0 big, to be determined later. Choose R ≥ R 0 large enough so that the function:

∆ * * (r) = r -r 1 2 α if r ≥ R, 1 + r R (∆ * * (R) -1) if r ≤ R, is concave (it is
also non decreasing). Choose M large enough so that for all r ≥ M , η q(r) 2 p(r) r ≥ R, and let L ≥ 1 be large enough so that ∆ * (r) = L∆ * * (r) ≥ ∆(r) for all r ≤ M . Let r > M, there exists p(r), q(r), l i , with ∆(l i ) ≤ ∆ * (l i ) by induction, and using successively (2), induction, concavity of ∆ * , (1) and the choice of M :

∆(r) ≤ ∆(l 1 ) + • • • + ∆(l 2 p ) ≤ ∆ * (l 1 ) + • • • + ∆ * (l 2 p ) ≤ 2 p ∆ * 1 2 p (l 1 + • • • + l 2 p ) ≤ 2 p ∆ * 1 2 p (η q r + 2 p C) = 2 p L η q p 2 p r + C - η q 2 p r + C 1 2 α , = L 2 1 α η q p 2 p r + 2 p α C -2 p α η q 2 p r + C 1 2 α , Now q p ≥ λ ensures 2 1 α η q p 2 p
≤ 1, so:

∆(r) ≤ L r + 2 p α C -2 p α η q 2 p r + C 1 2 α ≤ L r -r 1 2 α = ∆ * (r).
The last inequality holds when r is big enough so that:

2 p α η q 2 p r + C 1 2 -2 p α C ≥ r 1 2 .
Observe that 2

η λ η q p 2 1 2 ≥ √
2η > 1 so the latter is true when:

( 2η) p 2 r 1 2 ≥ r 1 2 + 2 p α C, which holds when r ≥ a P 0 = R 0 = 2 2p α C 2 ( √ 2η p 2 -1) 2 with a constant a 0 depending only on C. For P big, R = R 0 and so M = 2 η P R 0 = 2 η a 0 P . It is sufficient to take L∆ * * (M ) ≥ KM so L ≥ K 2 η a 0 P . 4.2.
Localization. The asymptotic behavior of the growth of Γ ω depends on the asymptotic of ω. On the other hand, the description of a ball of a given radius in Γ ω requires only some first terms of ω. The following lemma of localization is helpful to study growth of groups Γ ω for non periodic sequences ω.

Lemma 4.2. Suppose that the sequence ω is not asymptotically constant, then the ball B Γω (r) of radius r for the word norm with respect to the generating set

S ω = {a} {ϕ f v|v ∈ {id Gω , b ω , c ω , d ω }, f ∈ F } depends only on ω 0 ω 1 . . . ω k for k = log 2 (r).
The Cayley graph Cay(Γ, S) of a group Γ with generating set S is the colored graph with vertices γ in Γ and edges (γ, γs) of color s in S. The ball B Γ (r) of radius r is the subgraph obtained by restriction to vertices and ends of edges such that |γ| ≤ r for the word norm for S.

Proof. The ball B ω (1) of Γ ω for the generating set S ω is independent of ω among sequences that are not constant, it consists of the Cayley graph Cay(F × V, F × V ) together with an edge from the neutral element leading to the vertex a. By proposition 3.1, the ball B Γω (r) can be described using B Γσω ( r+1

2 ) and the wreath product recursion (2), i.e. ω 0 . Indeed, an element γ admits a reduced representative word w = a i 1 k 1 ak 2 . . . ak r/2 a i 2 and so γ = (γ 0 , γ 1 )ε

s with |γ 0 |, |γ 1 | ≤ r+1
2 by rewritting process. By iteration, B Γω (r) is described by B Γ σ k ω ( r 2 k + 1) and ω 0 . . . ω k . Remark 4.3. When ω = 0 ∞ is constant, the generator d ω acts trivially on the rooted tree T , hence is identity, so that the Klein group V degenerates into a group S 2 , and

G ω = a, b 0 ∞ |a 2 = b 2 = id = D ∞ is dihedral infinite.
However, the whole sequence ω is required to obtain this information. The group G0 ∞ obtained by "finite information" (concretely as a limit group of

G 0 k (012) ∞ for instance) is in fact the group G0 ∞ S 2 X G 0 ∞ = d 0 ∞ X a, b 0 ∞ , which is metabelien of exponential growth. Indeed, the wreath product embeddings G 0 k (012) ∞ → G 0 k-1 (012) ∞ S 2 , b k = (a, b k-1 , d k = (1, d k-1 ) and b ∞ = (a, b ∞ ), d ∞ = (1, d ∞ ) coincide on the k first levels.
As the balls of radius 1 of the groups G 0 k (012) ∞ and d 0 ∞ X a, b 0 ∞ also coincide, the argument of the proof of lemma 4.2 shows that these groups coincide on their balls of radius 2 k , showing isomorphism G0 ∞ S 2 X G 0 ∞ . This group played a crucial role in the construction of antichains of growth functions, cf. section 6 in [START_REF] Grigorchuk | Degrees of growth of finitely generated groups and the theory of invariant means[END_REF]. 4.3. Asymptotic growth. Opposed to localization, the asymptotic behavior of the growth depends only on the asymptotic of ω.

Proposition 4.4. For generating sets

S ω = {a} {ϕ f v|v ∈ {id, b ω , c ω , d ω }, f ∈ F }, the growth function of Γ ω = F X G ω satisfies for all r: b Γσω r -1 2 ≤ b Γω (r) ≤ 2b Γσω r + 1 2 2 .
Also by iteration:

b Γ σ k ω r 2 k -1 ≤ b Γω (r) ≤ 2 2 k b Γ σ k ω r 2 k + 1 2 k .
Proof. Let γ = ϕg belong to B Γω (r). It admits a minimal representative word w = Γω γ of length r, which is uniquely described after rewritting process as w = (w 0 , w 1 )σ(w) with |w 0 |, |w 1 | ≤ r+1 2 . Conclude that γ is determined by two elements γ 0 , γ 1 in B Γσω ( r+1

2 ) and a permutation σ(w) in S 2 , which proves the upper bound. Suppose ω 0 = 1 and let γ 0 belong to B Γσω ( r-1 2 ). It admits a minimal representative word

w 0 = a i 1 k 1 ak 2 a . . . ak l a i 2 of length ≤ r-1 2 . Set w = b ω ka 1 b ω ka 2 . . . b ω ka l b i 2 ω if i 1 = 1 and w = k1 b a ω k2 b a ω . . . b a ω kl b i 2 a ω if i 1 = 0 of length ≤ r, where kj = ϕ f j v j ω
for k j = ϕ f j v j σω . Proposition 3.1 and relations (2) from section 2.1 guarantee that w = (w 0 , w 1 )σ(w) for some w 1 , σ(w). Now if w = Γω w , then w 0 = Γσω w 0 , so that B Γσω ( r-1

2 ) injects into B Γω (r). (Note that when ω 0 = 1, the same computation works if b ω is replaced by d ω .) 5. Activity and growth 5.1. Activity of some words and lower bound on growth. Denote ||A|| the operator norm of a 3 × 3 matrix A acting on C 3 . The proposition 4.7 in [BE] generalizes as: Proposition 5.1. Denote:

A 0 =   2 0 1 0 2 1 0 0 1   , A 1 =   2 1 0 0 1 0 0 1 2   , A 2 =   1 0 0 1 2 0 1 0 2   .
There is C > 0 such that for any k, there is a word Such a pull back substitution is designed so that ζ(au) = (ua, au) when au is aprereduced word containing an even number of v's (where

w k in Γ ω , S ω such that s(w k ) ≥ 2 k and |w k | ≤ C||A ω 0 . . . A ω k ||.
v = d if ω 0 = 0, v = c if ω 0 = 1 and v = b if ω 0 = 2)
. Indeed, the following relations hold (take ω 0 = 0, similar otherwise):

ζ(ab) = abab = (ba, ab), baba= (ab, ba), ζ(ac) = acac = (ca, ac), caca= (ac, ca), ζ(ad) = abadac = (d, ada)a, badaca = (ada, d)a.
The pull back of v σω furnishes v ω on both components of the wreath product. The a's behave conveniently under the parity condition.

Given a word w

0 = au 0 in Ω σ k ω , define by induction ζ(au k-1 ) = au k = w k ∈ Ω ω .
The initial word u 0 can be chosen among the generators {b σ k ω , c σ k ω , d σ k ω } so that ζ(au 0 ) = avav for another generator v of G σ k-1 ω , so that ζ(au k ) always has an even number of v's, and the inverted orbit of au k can be studied by induction via:

ζ(au k-1 ) = au k = (u k-1 a, au k-1 ) and u k a = (au k-1 , u k-1 a).
Proposition 3.4 now ensures that:

s(au k ) ≥ s(au k-1 ) + s(u k-1 a) and s(u k a) ≥ s(u k-1 a) + s(au k-1 ), which is integrated in s(au k ) ≥ 2 k .
To estimate the length of w k = ζ(w k-1 ), it is sufficient to count the numbers |w| bω , |w| cω , |w| dω of generators b ω , c ω , d ω appearing in w, since the total length is controlled by |w| ≤ 2(|w| bω + |w| cω + |w| dω ). The construction of the pull back substitution ζ provides the relations:

A ω 0   |w k-1 | bσω |w k-1 | cσω |w k-1 | dσω   =   |w k | bω |w k | cω |w k | dω   ,
for the matrices A 0 , A 1 , A 2 , and eventually by induction:

A ω 0 A ω 1 . . . A ω k   |w 0 | b σ k ω |w 0 | c σ k ω |w 0 | d σ k ω   =   |w k | bω |w k | cω |w k | dω   , so that |w k | ≤ C||A ω 0 . . . A ω k ||. The matrices A 0 , A 1 , A 2 are cyclic conjugates A 1 = CA 0 C -1 and A 2 = C -1 A 0 C = CA 1 C -1 , so that A k 1 0 A k 2 1 A k 3 2 • • • = A k 1 0 CA k 2 0 CA k 3 0 . . . with C =   0 1 0 0 0 1 1 0 0   , A 0 C =   1 2 0 1 0 2 1 0 0   .
The matrix A 0 C has caracteristic polynomial X 3 -X 2 -2X -4 with positive real root 2 η , and two complex conjugate roots of smaller absolute value, hence spectral radius ρ(A 0 C) = 2 η . (Remind that η is the positive root of X 3 + X 2 + X -2.) Examples 5.2.

(1) For ω = (012) ∞ , the spectral radius theorem gives:

||A ω 0 . . . A ω k || ≤ ||(A 0 C) k+1 || ≤ Cρ(A 0 C) k = C 2 η k .
(2) For other periodic sequences, similar bounds are obtained, as for instance ω = (001122) ∞ , then:

||A ω 0 . . . A ω k || ≤ ||(A 2 0 C) k+1 2 || ≤ Cρ(A 2 0 C) k 2
, where the spectral radius ρ(A 2 0 ) ≈ 5.63 is the positive root of X 3 -3X 2 -12X -16.

Such estimates for periodic sequences are not usually sharp enough. The following lemma is the key step to obtain the lower bound on the growth function in theorem 6.1:

Lemma 5.3. Let ω = 0 m 1 (012) n 1 0 m 2 (012) n 2 . . . , with m i , n i → ∞.
There exists a constant C, such that for every ε > 0 and k = j i=1 m i + 3n i big enough:

||A ω 0 . . . A ω k || ≤ C εk ρ(A 0 ) m i ρ(A 0 C) 3 n i = C εk 2 m i 2 η 3 n i .
Note that this inequality is essentially optimal.

Proof. By the spectral radius theorem, there exists C such that ||A m 0 || ≤ Cρ(A 0 ) m and ||(A 0 C) 3n || ≤ Cρ(A 0 C) 3n , so:

||A ω 0 . . . A ω k || ≤ ||A m 1 0 (A 0 C) 3n 1 A m 2 0 (A 0 C) 3n 2 . . . || ≤ ||A m 1 0 ||.||(A 0 C) 3n 1 ||.||A m 2 0 ||.||(A 0 C) 3n 2 || . . . ≤ C j ρ(A 0 ) j i=1 m i ρ(A 0 C) 3 j i=1 n i , where j = o(k) since m i , n i → ∞.
Note that if m i , n i are of the order log i, then j ≈ k log k , and if m i , n i are of the order i θ , then j ≈ k 1 θ+1 .

Activity of all words and upper bound on growth. Say a sequence

ω = ω 0 ω 1 ω 2 . . . in {0, 1, 2} N is rotating if ω i+1 ∈ {ω i , ω i + 1} mod 3 for all i.
Remind that η is the positive root of X 3 + X 2 + X -2. Adapting [START_REF] Bartholdi | The growth of Grigorchuk's torsion group[END_REF] to rotating sequences ω, define a length on G ω by assigning weights to the generating set a, b ω , c ω , d ω . Set ||a|| = 1 -η 3 and:

if ω 0 = 0, ||b ω || = η 3 , ||c ω || = 1 -η 2 , ||d ω || = 1 -η, if ω 0 = 1, ||b ω || = 1 -η 2 , ||c ω || = 1 -η, ||d ω || = η 3 , if ω 0 = 2, ||b ω || = 1 -η, ||c ω || = η 3 , ||d ω || = 1 -η 2 .
This defines a length on G ω for which the minimal representative words are prereduced (η is chosen so that this is the case, see lemma 4.1 in [START_REF] Bartholdi | The growth of Grigorchuk's torsion group[END_REF]), which is obviously equivalent to the usual word length 1 C |w| ≤ ||w|| ≤ C|w|, and designed so that if ω 1 = ω 0 + 1, then: This length on G ω can be extended to a function on the set of words in the generating set

ε b (ω 0 )||a|| + ||b σω || = η(||a|| + ||b ω ||), ε c (ω 0 )||a|| + ||c σω || = η(||a|| + ||c ω ||), ε d (ω 0 )||a|| + ||d σω || = η(||a|| + ||d ω ||), where: ε b   0 1 2   =   1 1 0   , ε c   0 1 2   =   1 0 1   , ε d   0 1 2   =   0 1 1   ,
S ω of Γ ω by ||ϕ f v|| = ||v|| if v ∈ {b ω , c ω , d ω } and ||ϕ f id|| = 0. Note that even though ||w|| is not a length on Γ ω it is still equivalent to the length of pre- reduced words, i.e. 1 C |w| ≤ ||w|| ≤ C|w|, because if w = a i 1 ϕ f 1 v 1 aϕ f 2 v 2 . . . aϕ fr v r a i 2 , then ||w|| = ||w|| for w = a i 1 v 1 av 2 . . . av r a i 2 , which is bilipschitz equivalent to r.
The following statement generalizes Lemma 4.2 in [BE].

Lemma 5.4. Let w be a pre-reduced word of Γ ω , S ω with rewritting process giving w = (w 0 , w 1 )ε s , then:

||w 0 || + ||w 1 || ≤ η q(ω 0 ,ω 1 ) ||w|| + C,
where C = η||a||, q(ω 0 , ω 1 ) = 0 if ω 1 = ω 0 , q(ω 0 , ω 1 ) = 1 if ω 1 = ω 0 + 1 and the left-handside lengths are in Γ σω , the right-hand side one in Γ ω .

Proof. The inequalities for w = (w 0 , w 1 )σ(w) in G ω and G σω are obvious by construction of the length ||.||, i.e. by choice of η. They still apply to pre-reduced words in Γ ω and Γ σω .

In order to estimate the growth function from above, the word activity function s ω (r) = max{s(w)|w ∈ (Γ ω , S ω ), |w| ≤ r} will be usefull. However, it is smoother to estimate first the bilipschitz equivalent auxiliary

∆ ω (r) = max{s(w)|w is pre-reduced, ||w|| ≤ r}.
Fact 5.5. For any r, there exists l 0 , l 1 integers such that:

(1) ∆ ω (r) ≤ ∆ σω (l 0 ) + ∆ σω (l 1 ), and (2) l 0 + l 1 ≤ η q(ω 0 ,ω 1 ) r + C.

By induction, there exists l 1 , . . . , l 2 p integers such that:

(1) ∆ ω (r) ≤ ∆ σ p ω (l 1 ) + • • • + ∆ σ p ω (l 2 p ), and (2) l 1 + • • • + l 2 p ≤ η q(ω 0 ,...,ωp) r + 2 p+1 C, where q(ω 0 , . . . , ω p ) is the number of i such that ω i+1 = ω i + 1 mod 2.
Proof. The maximum is realized for a certain word w, for which the rewritting process furnishes w = (w 0 , w 1 )σ(w) with l 0 = ||w 0 || and l 1 = ||w 1 || such that l 0 + l 1 ≤ η q(ω 0 ,ω 1 ) ||w|| + C by lemma 5.4. Thus:

∆ ω (r) = s(w) = s(w 0 ) + s(w 1 ) ≤ ∆ σω (l 0 ) + ∆ σω (l 1 ).

Proposition 5.6. Suppose ω is such that for all i, there exists p(i) ≤ P such that q(ω i , . . . , ω i+p(i) ) = q(i) and q(i) p(i) ≥ λ, then:

log b Γω (r) ≤ A P r α , for α = log(2) log(2) -λ log(η)
.

In particular, if ω is p-periodic and q(ω 0 , . . . ,

ω p ) = q, then log b Γω (r) ≤ Lr α for α = log(2) log(2)-q p log(η) . Proof. Set ∆(r) = sup{∆ σ p ω (r)|p ∈ N}. Fact 5.5 provides the existence of l 1 + • • • + l 2 p ≤ η q(ω 0 ,...,ωp) r + 2 p C such that ∆(r) ≤ ∆(l 1 ) + • • • + ∆(l 2 p )
, and so by lemma 4.1 there is a constant A such that ∆(r) ≤ A P r α , so that s ω (r) ≤ A P r α (mind that there is a trivial bound ∆(r) ≤ Kr because the activity is bounded by the word length). Now corollary 3.5 shows log b Γω (r) ≤ A P r α .

Precise growth estimates

The particular case of theorem 1.1 can now be derived. Recall that α 0 is such that 2 = 2 η α 0 . Theorem 6.1. For any α ∈ [α 0 , 1], there exists a sequence ω(α) such that α(Γ ω(α) ) = α, i.e.

lim log log b Γ ω(α) (r) log r = α.
Proof. Given α, take λ in [0, 1] such that 2 = ( 2 η λ ) α . Consider a sequence of the form ω = 0 m 1 (012) n 1 0 m 2 (012) n 2 . . . . Denote the ith period p i = m i + 3n i and q i = 3n i the number of steps of rotation of ω, and assume both tend to infinity. Suppose moreover that q i p i ≥ λ for each i and q i p i → λ, so that j i=1 p i = k j and j i=1 q i = λk j + o(k j ). Lemma 4.2 of localization allows to use proposition 5.6 for P depending on the scale r. Indeed, b Γω (r) depends only on ω 0 , . . . , ω k for k = log 2 (r), for which p i ≤ P (k), so that: log b Γω (r) ≤ A P (k) r α ≤ r α+ε , as soon as P (k) ≤ ε log A (r). In particular, if ω is chosen such that P (k) = o(log(r)) = o(k), the required upper bound holds: α(Γ ω ) ≤ α.

Concerning lower estimates, the word w k j introduced in proposition 5.1 has length bounded by (lemma 5.3):

|w k j | ≤ C ε k j 2 j i=1 p i η j i=1 q i ≤ C 2ε k j 2 η λ k j ≤ 2 η λ k j (1+ε)
. Now lemma 3.5 ensures, for r j = 2 η λ k j (1+ε)

:

r α 1+ε j = 2 k j ≤ s(w k j ) ≤ log b Γω (|w k j |) ≤ log b Γω 2 η λ (1+ε)k j = log b Γω (r j ).
Interpolating for r j ≤ r ≤ r j+1 gives:

log b(r) ≥ log b(r j ) ≥ r α 1+ε j = r α 1+ε j+1 2 η λ -αp j ≥ r α 1+ε 2 η λ -αp j ≥ r α-2ε ,
where the last inequality holds for large r since

p j+1 ≤ P (k) = o(k) = o(log r). As ε is arbitrary, α(Γ ω ) ≥ α for any such sequence ω.
Remark 6.2. Obviously, the computation of the exact growth exponent α(G) = α does not imply that b G (r) e r α . The precise estimates obtained with the proof above are (for r j ≤ r ≤ r j+1 ):

C -(j+p j +e(j)) r α ≤ log b ω (r) ≤ r α A p j+1 ,
where e(j) = ( j i=1 q i ) -λk j = o(j) is the error on the rationnal approximation of λ by greater values. Taking p i of the order log i, and thus j of the order log r log log r , one obtains for some A:

r α-A log log r ≤ log b ω (r) ≤ r α+ A log log r log r
, and taking p i of the order i θ for 0 < θ < 1, thus j of order (log r) 1 θ+1 , one obtains:

r α-A(log r) -θ θ+1 ≤ log b ω (r) ≤ r α+A(log r) -1 θ+1 .
7. Oscillation phenomena 7.1. Groups with oscillating logarithmic growth exponents. The oscillation of logarithmic exponents of growth function is the phenomenon that underlies the construction of antichains of growth function in section 7 of [START_REF] Grigorchuk | Degrees of growth of finitely generated groups and the theory of invariant means[END_REF] and of "fast intermediate" growth in [START_REF] Erschler | On the degrees of growth of finitely generated groups[END_REF]. It was studied for its own interest in the second chapter of [Bri]. Theorem 6.1 allows a better understanding.

Theorem 7.1.

For any α ≤ β ∈ [α 0 , 1], there exists a sequence ω(α, β) such that α(Γ ω(α,β) ) = α and α(Γ ω(α,β) ) = β, i.e. lim inf log log b Γ ω(α,β) (r) log r = α and lim sup log log b Γ ω(α,β) (r) log r = β.
To ease notations, b Γω (r) = b ω (r) from now on.

Proof. Take ω(α, β) = ω(α) |0...m 1 ω(β) |m 1 +1...n 1 ω(α) |n 1 +1...m 2 ω(β) |m 2 +1...n 2 .
. . for some sequences m i , n i tending to infinity. Such a choice ensures that:

α ≤ α(Γ ω(α,β) ) and α(Γ ω(α,β) ) ≤ β.
If m i , n i tend to infinity sufficiently fast, these inequalities become equalities. Indeed, take ε i → 0, and construct r i , r i such that:

log log b(r i ) log r i ≤ α + ε i and log log b(r i ) log r i ≥ β -ε i .
By localization 4.2, left inequality holds for all ω |0...m i = ω(α, β) |0...m i and right inequality for all ω |0...n i = ω(α, β) |0...n i with log 2 r i = m i and log 2 r i = n i .

Assume by induction that m j , n j are constructed for j ≤ i and construct m i+1 = log r i+1 . Take ω = ω(α, β) |0...n i ω(α) |n i +1... . By proposition 4.4 on asymptotic growth:

b ω (r) ≤ 2 2 n i b σ n i ω ( r 2 n i + 1) 2 n i = 2 2 n i b σ n i ω(α) ( r 2 n i + 1) 2 n i ≤ 2 2 n i b ω(α) (r + 2 n i +1 ) 2 n i , so that: log log b ω (r) log r ≤ log log b ω(α) (r + 2 n i +1 ) + n i log 2 log r log log b ω(α) (r) log r -→ r→∞ α,
and there exists r i+1 as required. Set m i+1 = log 2 (r i+1 ).

Now construct n i+1 = log 2 (r i+1 ). Take ω = ω(α, β) |0...m i+1 ω(β) |m i+1 +1... . Again proposition 4.4: b ω (r) ≥ b σ m i+1 ω ( r 2 m i+1 -1) = b σ m i+1 ω(β) ( r 2 m i+1 -1) ≥ 1 2 b ω(β) (r -2 m i+1 +1 ) 1 2 m i+1 , so that: log log b ω i+1 (r) log r ≥ log log b ω(β) (r -2 m i+1 +1 ) -m i+1 log 2 log r -→ r→∞ β,
and there exists r i+1 and n i+1 = log 2 r i+1 .

7.2. Antichains of growth functions. The following result is an improvement of Theorem 7.2 in [START_REF] Grigorchuk | Degrees of growth of finitely generated groups and the theory of invariant means[END_REF], which established the existence of antichains of intermediate growth functions accumulating to e r .

Theorem 7.2. For any α 0 ≤ α < β ≤ 1, there exists uncountably many groups Γ ω with pairwise non comparable growth functions (such a collection of groups is called an antichain) satisfying α(Γ ω ) = α and α(Γ ω ) = β.

Moreover, if β < β ≤ 1, such an antichain can be chosen so that b ω (r) ≤ Ce r β for a constant C depending only on β, β and not on ω.

Lemma 7.3. Given α 0 ≤ α < β ≤ 1, there exists an application ω from the set F(N, {α, β}) of functions f : N → {α, β} to the Cantor space of infinite sequences {0, 1, 2} N , and there exists sequences r i → ∞ and β-α 2 > ε i → 0 such that:

(1) α(Γ ω(f ) ) = α and α(Γ ω(f ) ) = β, (2)
log log b ω(f ) (r i ) log r i ≥ β -ε i if f (i) = β, (3)
log log b ω(f ) (r i ) log r i ≤ α + ε i if f (i) = α.
Proof of theorem 7.2. There are uncountably many functions ξ : N × N → {α, β} such that ξ(x, y) = α implies ξ(x, y + 1) = β and ξ(x, y) = β implies ξ(x, y + 1) = α. Any bijection ϕ :

N → N × N, provides an injection ξ → f ξ by f ξ (i) = ξ • ϕ(i). Now given ξ 1 = ξ 2 , if f ξ 1 (i) < f ξ 2 (i)
, there exists j > i such that f ξ 2 (j) < f ξ 1 (j). Lemma 7.3 ensures that b ω(f ξ 1 ) (r) and b ω(f ξ 2 ) (r) are not comparable.

Proof of lemma 7.3. The proof of this lemma is a variation on the proof of theorem 7.1. Pick:

ω(f ) = ω(f (0)) |0...m 0 ω(f (1)) |m 0 +1...m 1 ω(f (2)) |m 1 +1...m 2 . . .
for a sequence m i = log 2 (r i ) increasing sufficiently fast. Mind that this guarantees a uniform upper bound

log log b ω(f ) (r) log r
≤ β+ε = β for any ε and r big enough (depending on ε).

Assume by induction m j and r j constructed for j ≤ i and consider:

ω = ω(f (0)) |0...m 0 . . . ω(f (i)) |m i-1 +1...m i ω(α) |m i +1... , ω = ω(f (0)) |0...m 0 . . . ω(f (i)) |m i-1 +1...m i ω(β) |m i +1... .
As above, proposition 4.4 on asymptotic growth provides:

b ω (r) ≤ 2 2 m i b ω(α) (r + 2 m i +1 ) 2 m i , b ω (r) ≥ 1 2 b ω(β) (r -2 m i +1 ) 1 2 m i +1 ,
so that there exists r i+1 , independent of (f (0), . . . , f(i)), such that:

log log b ω (r i+1 ) log r i+1 ≤ α + ε i , log log b ω (r i+1 ) log r i+1 ≥ β -ε i ,
and this is true for any sequence ω coinciding with ω , ω on the m i+1 = log 2 r i+1 first values.

Remark 7.4. The idea behind the proof of theorem 7.1, is that the asymptotic behavior of the growth function b ω (r) of the group Γ ω depends only on the asymptotic of the defining sequence ω, whereas locally a ball of given radius depends only on some first terms of ω. This permits to produce scales at which the growth function is essentially e r α and others at which it is essentially e r β , thus explaining oscillation between this two behaviors. Of course, the process can be used to produce a variety of different behaviors at different scales, for instance scales S i at which Γ ω seems to have growth e r γ i for countably many α i ∈ [α 0 , 1], intertwined with scales S j at which Γ ω seems to have growth oscillating between e r α j and e r β j . The only point is to allow enough "time" so that the behavior at scale S i or S j becomes visible, i.e. functions m i , n i in the proofs above increasing sufficiently fast.

Frequency of oscillations

This section aims at studying the frequency of oscillations for groups of the type Γ ω . The main question is to maximize the frequency of oscillation between two given bounds, or equivalently to minimize the period. Some pseudo-period exponents are defined, and shown to be group invariants. Some estimates on these exponents are then obtained. 8.1. Group invariants associated to oscillation. Given α < β and a Lipschitz function b : N → N, define the upper set U (α, β) and lower set L(α, β) of b for α, β to be:

U (α, β) = {s ∈ N| log log b(s) log s ≥ β} and L(α, β) = {t ∈ N| log log b(t) log t ≤ α}. Note that log log b(s) log s ≥ β is equivalent to log b(s) ≥ s β and log log b(t) log t ≤ α is equivalent to log b(t) ≤ t α .
Property 8.1. Let α < β and b : N → N be a Lipschitz function, then:

(1) L(α, β) U (α, β) ⊂ N, and the inclusion is strict if both upper and lower sets are infinite.

(2) Assume α < α < β < β then:

L(α , β) ⊂ L(α, β) and U (α, β ) ⊂ U (α, β),
and the inclusions are strict if both upper and lower sets are infinite. .

β α s i s i s i+1 s i+1 t i t i U i L i U i+1 U i+1
Note that when b(r) = b Γ (r) is the growth function of a finitely generated group Γ such that α(Γ) < α < β < α(Γ), then both upper and lower sets are infinite.

Property (1) allows to decompose U = ∞ j=0 U j and L = ∞ j=0 L j such that:

(1) U i , L i are non empty, (2) for any s ∈ U i , then s ≥ max ∪ j≤i-1 L j and s ≤ min ∪ j≥i L j , (3) for any t ∈ L i , then t ≥ max ∪ j≤i U j and t ≤ min ∪ j≥i+1 U j .

Call this decomposition alternating (see figure 2).

In order to study oscillation, set s i = min U i , s i = max U i , t i = min L i and t i = max L i . The upper pseudo period function u is the partially defined s i+1 = u(t i ) and the lower pseudo period function l is the partially defined t i = l(s i ). In order to investigate how small these functions can be, define:

u α,β = inf{ν|∃i o , ∀i ≥ i o , s i+1 ≤ (t i ) ν } and l α,β = inf{λ|∃i o , ∀i ≥ i o , t i ≤ (s i ) λ }. Equivalently: u α,β = lim sup i→∞ log s i+1 log t i and l α,β = lim sup i→∞ log t i log s i .
The following fact provides estimates on the pseudo period functions that any growth function of infinite group must satisfy. (

1) if b(r) is submultiplicative, u α,β ≥ 1-α 1-β > 1, (2) if b(r) is increasing, l α,β ≥ β α > 1. Proof. Suppose log b(t) ≤ t α . Submultiplicativity implies log b(kt) ≤ kt α , so that log b(kt) ≥ (kt) β forces kt α ≥ (kt) β hence kt ≥ t β-α 1-β +1 . Now suppose log b(s) ≥ s β , then log b(t) ≤ t α forces t α ≥ s β .
By property (2), given α < α < β < β , one has u α ,β ≥ u α ,β and l α ,β ≥ l α ,β . This permits the: Definition 8.3. The upper pseudo period exponent u(α, β) and the lower pseudo period exponent l(α, β) of a function b(r) are:

u(α, β) = lim α → α + β → β - u α ,β , and l(α, β) = lim α → α + β → β - l α ,β . Remind notation α → α + (respectively β → β -) for α → α and α > α (respec- tively β → β and β < β).
This definition is appropriate because it permits to define u(α(Γ), α(Γ)) and l(α(Γ), α(Γ)) associated to the growth function b Γ (r) even though the upper and lower sets U (α(Γ), α(Γ)) and L(α(Γ), α(Γ)) may be empty. Also: Proposition 8.4. The upper and lower pseudo period exponents u(α, β) and l(α, β) are group invariants. Remark 8.5. Given α < β, one can similarly define the pseudo period exponent of oscillations for a function b(r), by p(α, β) = lim p α ,β for p α ,β = lim sup log s i+1 log s i , and it is a group invariant for b Γ (r). However, it is not true a priori that replacing s i by t i , t i or s i would provide the same exponent. 8.2. Estimates on pseudo-period. Theorem 6.1 shows that for any γ ∈ [α 0 , 1] there exists a group Γ ω(γ) such that:

1 C ε r γ-ε ≤ log b ω(γ) (r) ≤ C ε r γ+ε ,
where ε > 0 is arbitrary and C ε depends only on ε.

Suppose that log b ω (t) = t α for some t. This fact depends only on (ω i ) m i=0 for m = log 2 t by localization. Now consider the group Γ ω for the sequence ω = ω 0 . . . ω m ω(γ)| m+1... , for some γ ≥ β > α. By proposition 4.4 on asymptotic growth, one has:

log b ω (s) ≥ 1 2 m log b ω(γ) (s -2 m+1 -log 2) ≥ 1 C ε t (s -2t) γ-ε ,
so that for any β < β and ε small enough: The choice of ω(α, β, γ, δ) guarantees α(Γ ω(α,β,γ,δ) ) ≥ δ and α(Γ ω(α,β,γ,δ) ) ≤ γ, but these are probably strict inequalities.

Note that the construction of ω(α, β) in the proof of theorem 7.1 is a particular instance of the above proposition with γ = β and δ = α. In this case, the upper and lower pseudo period exponents are (a priori) infinite.

On the other hand, in order to minimize the upper and lower pseudo period exponents for a fixed oscillation magnitude α < β, taking γ = 1 and δ = α 0 gives upper bounds (the lower bounds are trivial from fact 8.2):

1 -α 1 -β ≤ u(α, β) ≤ 1 1 -β and β α ≤ l(α, β) ≤ 1 α -α 0 .
Since the estimates above are done for any t in L(α, β) and s in U (α, β), they provide an upper bound for (any choice of definition in remark 8.5) pseudo period:

β(1 -α) α(1 -β) ≤ p(α, β) ≤ 1 (1 -β)(α -α 0 )
.

8.3. Further developments on frequency of oscillations. After this work was first submitted, the results of [START_REF] Bartholdi | Groups of given intermediate word growth[END_REF] show that there are groups with u(α, β) = 1-α 1-β and l(α, β) = β-α 0 α-α 0 . Such an upper pseudo-period exponent is optimal by submultiplicativity of growth function. It is not known if such a lower pseudo-period exponent is optimal.

Similar results concerning oscillations of entropy functions of random walks on groups are obtained in [START_REF] Brieussel | Behaviors of entropy on finitely generated groups[END_REF], theorem 5.8.

  . . . ϕ(x) . . . . . . . . . . . . ϕ(x) . . .

Figure 1 .

 1 Figure 1. Description of the action of a word w via the minimal tree T (w)

Proof.

  Consider the subsemigroup Ω ω = {ab ω , ac ω , ad ω } * ⊂ Ω ω , and define the pull back substitution ζ : Ω σω → Ω ω by: ζ(ab σω ) = ab ω ab ω ζ(ac σω ) = ac ω ac ω ζ(ad σω ) = ab ω ad ω ac ω if ω 0 = 0, ζ(ab σω ) = ab ω ab ω ζ(ac σω ) = ad ω ac ω ab ω ζ(ad σω ) = ad ω ad ω if ω 0 = 1, ζ(ab σω ) = ac ω ab ω ad ω ζ(ac σω ) = ac ω ac ω ζ(ad σω ) = ad ω ad ω if ω 0 = 2.

  and if ω 0 = ω 1 , then the factor η on the right-hand sides disappears.

Figure 2 .

 2 Figure 2. Upper and lower sets U (α, β) and L(α, β) seen by drawing the curve f (r) = log log b(r) log r

Fact 8. 2 .

 2 Consider α < β and a function b : N → N, then:

Proof.

  In order to show the exponents are not perturbed by change of generating set, consider a function b (r) such that there existsC with b( r C ) ≤ b (r) ≤ b(Cr). Then L (b ) (α , β ) = {t| log b (t) ≤ t α } ⊂ {t| log b( t C ) ≤ t α } = C{x| log b(x) ≤ C α x α }.But given any α > α and x large enough, one has C α x α ≤ x α , so that if x large enough belongs to L (b ) (α , β ), then x belongs to CL (b) (α , β ). Similarly, for any β < β , large enough y that belong to U (b ) (α , β ) also belong to 1 C U (b) (α , β ). This permits to deduce that there is a j such that:j+1 (α , β ) -log C log t (b) j (α , β ) + log C so that u (b ) α ,β ≥ u (b) α ,β for any α < α < β < β , which implies u (b ) (α, β) ≥ u (b) (α,β), and equality holds by symetry. Similar proof for l(α, β).

  min{s| log b ω (s) ≥ s β } ≤ C ε t 1 γ-ε-β + o(t 1 γ-ε-β ).Conversely suppose that log b ω (s) = s β for some s, which depends only on (ω i ) n i=0 for n = log 2 s, and consider the group Γ ω for the sequence ω = ω 0 . . . ω n ω(δ)| n+1... for some δ ≤ α < β. As above, one has:log b ω (t) ≤ 2 n (log b ω(δ) (t + 2 n+1 ) + log 2) ≤ C ε s(t + 2s) δ+ε ,so that for any α < α and ε small enough:min{t| log b ω (t) ≤ τ α } ≤ C ε s 1 α -δ-ε + o(s 1 α -δ-ε ).These two observations show the following (passing to the limits α → α, β → β and ε → 0):Proposition 8.6. Given α 0 ≤ δ ≤ α < β ≤ γ ≤ 1, there exists a sequence ω(α, β, γ, δ) = ω(δ)| 0...m 1 ω(γ)| m 1 +1...n 1 ω(δ)| n 1 +1...m 2 ω(γ)| m 2 +1...n 2 . . .such that the group Γ ω(α,β,γ,δ) satisfies: u(α, β) ≤ 1 γ -β and l(α, β) ≤ 1 α -δ .

Supported by Swiss NSF grant 20-126689.