J Ér

Émie Brieussel

BEHAVIORS OF ENTROPY ON FINITELY GENERATED GROUPS

A variety of behaviors of entropy functions of random walks on finitely generated groups is presented, showing that for any 1 2 ≤ α ≤ β ≤ 1, there is a group Γ with measure µ equidistributed on a finite generating set such that:

The groups involved are finitely generated subgroups of the group of automorphisms of an extended rooted tree. The return probability and the drift of a simple random walk Y n on such groups are also evaluated, providing an example of group with return probability satisfying:

and lim sup log | log P (Y n = Γ 1)| log n = 1, and drift satisfying: lim inf log E||Y n || log n = 1 2 and lim sup log E||Y n || log n = 1.

Introduction

The caracterisation of groups by an asymptotic description of their Cayley graphs may be dated back to Folner's criterion of amenability by quasi-invariant subsets [Fol]. Shortly after, Kesten showed equivalence with the probabilistic criterion that a group Γ is amenable if and only if the return probability P (Y n = 1) of a simple random walk Y n on Γ decays exponentialy fast [Kes]. This article focuses on three quantities that partially describe the behavior of the diffusion process of a random walk Y n with step distribution µ on a group Γ. Namely the entropy function H Γ,µ (n) = H(µ * n ) = H(Y n ), the return probability P (Y n = 1) and the drift, also called rate of escape, L Γ,µ (n) = E µ * n ||γ|| = E||Y n ||, where ||.|| is a word norm,

H(µ) = - γ∈Γ µ(γ) log µ(γ)
is the Shannon entropy of the probability measure µ, and µ * n is the n-fold convolution of µ, or in other terms the distribution of Y n . The return probability for a finitely supported symmetric law µ is a group invariant by [START_REF] Pittet | On the stability of the behavior of random walks on groups[END_REF], which is not known to be the case for entropy and drift. However, sublinearity of the entropy or of the drift for some measure µ with generating support implies amenability [KV].

In the present paper, the measure µ will always be equidistributed on a canonical finite symmetric generating set of Γ.

The asymptotic behavior of these functions has been precisely established in a number of cases, that mainly include virtually nilpotent groups, linear groups and wreath products ( [Var], [START_REF] Pittet | On random walks on wreath products[END_REF], [START_REF] Pittet | Random walks on finite rank solvable groups[END_REF], [START_REF] Erschler | On drift and entropy growth for random walks on groups[END_REF], [START_REF] Erschler | On the asymptotics of the rate of departure to infinity[END_REF], [START_REF] Erschler | Isoperimetric inequality for wreath product of Markov chains and selfintersections of random walks[END_REF], [Rev]), and a variety of less precise estimates exist for some groups acting on rooted trees ( [BV], [Kai], [START_REF] Erschler | Piecewise automatic groups[END_REF], [BKN], [AAV], [AV]).

The object of this article is to present examples of groups that provide new asymptotic behaviors for these probabilistic functions. Entropy, return probability and drift functions will not be precisely computed, but only mild approximations in terms of their exponents.

Definition 1.1. The lower and upper entropy exponents of a random walk Y n of law µ on a group Γ are respectively: h(Γ, µ) = lim inf log H Γ,µ (n) log n and h(Γ, µ) = lim sup log H Γ,µ (n) log n .

The lower and upper return probability exponents of a random walk Y n of symmetric finitely supported law µ on a group Γ are respectively: The lower and upper drift exponents of a random walk Y n of law µ on a group Γ are respectively:

δ(Γ, µ) = lim inf log L Γ,µ (n) log n and δ(Γ, µ) = lim sup log L Γ,µ (n) log n .

When equality holds, the entropy exponent of the group Γ with law µ is h(Γ, µ) = h(Γ, µ) = h(Γ, µ), the return probability exponent of a group Γ is p(Γ) = p(Γ) = p(Γ) and the drift exponent of the group Γ with law µ is δ(Γ, µ) = δ(Γ, µ) = δ(Γ, µ). Return probability exponents do not depend on the particular choice of the measure by [START_REF] Pittet | On the stability of the behavior of random walks on groups[END_REF].

Computing the exponents gives moderate information on the function. By [START_REF] Pittet | On random walks on wreath products[END_REF], the wreath product Z ≀ Z has return probability P (Y n = 1) ≈ exp(-n 1 3 (log n) 2 3 ), and the lamplighter F ≀ Z with finite group F has return probability P (Y n = 1) ≈ exp(-n 1 3 ). Both have return probability exponent 1 3 . Exponent 1 does not imply linearity of entropy or drift, nor exponential decay of return probability, as seen by the exemples in [START_REF] Erschler | Piecewise automatic groups[END_REF].

The groups considered here are directed groups of automorphisms of extended rooted trees. The main construction combines the directed groups of [START_REF] Brieussel | Amenability and non-uniform growth of some directed automorphism groups of a rooted tree[END_REF] with the notion of boundary permutational extension introduced in [BE] and used in [START_REF] Brieussel | Growth behaviors in the range e r α[END_REF] to exhibit various behaviors of growth functions on groups. The entropy exponents can be computed explicitely in terms of the group construction (see theorem 5.1), which leads to the following corollary: Theorem 1.2. For any 1 2 ≤ α ≤ β ≤ 1, there exists a finitely generated group Γ = Γ(α, β) and a symmetric finitely supported measure µ such that: h(Γ, µ) = α and h(Γ, µ) = β.

In particular when α = β, there is a finitely generated group Γ(β) with measure µ such that: h(Γ, µ) = β.

Entropy is related to growth because over a finite set, entropy is maximized for equidistribution probability, so that:

h Γ,µ (r) = h(µ * n ) ≤ log #supp(µ * n ) = log b Γ,S (r).
The groups of theorem 1.2 have sublinear entropy and often exponential growth. However, most of the groups Γ ω of [START_REF] Brieussel | Growth behaviors in the range e r α[END_REF] have intermediate growth and are extended directed groups of a binary rooted tree, so by theorem 5.1 they all have entropy exponent h(Γ, µ) = 1 2 . The return probability and drift exponents of extended directed groups can be estimated from above and from below, but the bounds do not match in general. A specific example provides the: Theorem 1.3. There exists a finitely generated group ∆ and a symmetric finitely supported measure µ ′ such that:

p(∆) = 1 3 , p(∆) = 1 and δ(∆, µ ′ ) = 1 2 , δ(∆, µ ′ ) = 1.
These theorems show that the phenomenon of oscillation studied in [START_REF] Brieussel | Growth behaviors in the range e r α[END_REF] for growth function exponents (see also [START_REF] Brieussel | Croissance et moyennabilité de certains groupes d'automorphismes d'un arbre enraciné[END_REF] and [KP]) also occurs for entropy, return probability and drift. The existence of a group with such drift exponents was mentionned without proof in [START_REF] Erschler | Poisson-Furstenberg boundaries, large-scale geometry and growth of groups[END_REF].

The article is structured as follows. The main construction of extended directed groups of a rooted tree T d is described in section 2, where is also presented a side application to the Haagerup property of groups with non-uniform growth. Section 3 presents the basic tool to study these groups which is the rewritting process, leading to the notions of minimal tree and activity, related to inverted orbits of permutational extensions defined in [BE]. Section 4 relates the expected activity of a random walk Y n to the exponent sequence, which depends only on the tree T d. At this stage one can prove the main theorem 5.1 on entropy, which implies theorem 1.2 for β < 1 and permits to derive estimates on the drift. The frequency of oscillation of entropy exponents is also studied in section 5. The main estimates on return probability of extended directed groups are given in theorem 6.1, with a specific example related to the lamplighter group. Section 7 is devoted to another construction adapted from [KP] and similar to [START_REF] Erschler | Piecewise automatic groups[END_REF], which permits to obtain the case β = 1 in theorem 1.2 and to prove theorem 1.3. A generalisation of the construction of extended directed groups is presented in section 8, followed by some comments and questions in the final section 9.

Aknowledgements. I am most grateful to Gidi Amir and Balint Virag who helped me correct and improve a preliminary non-accurate version of this article. I also wish to thank Laurent Saloff-Coste, Alain Valette and Andrzej Zuk, who supported me during this work. Finally, I thank the anonymous referee for careful reading and many comments.

The groups involved

2.1. Directed groups. Given a sequence d = (d j ) j≥0 of integers d j ≥ 2, the spherically homogeneous rooted tree T d is the graph with vertices v = (i 1 i 2 . . . i k ) with i j in {1, 2, . . . , d j-1 }, including the empty sequence ∅ called the root, and edges

{(i 1 i 2 . . . i k ), (i 1 i 2 . . . i k i k+1 )}. The index k is called the depth or level of v, denoted |v| = k.
The boundary ∂T d of the tree T d is the collection of infinite sequences x = (i 1 i 2 . . . ) with i j in {1, 2, . . . , d j-1 }.

The group Aut(T d) of automorphisms of the rooted tree is the group of graph automorphisms that fix the root ∅. The following isomorphism is canonical:

(1)

Aut(T d) ≃ Aut(T σ d) ≀ S d 0 .
The symbol ≀ represents the permutational wreath product

G ≀ S d = (G × • • • × G) ⋊ S d
where S d acts on the direct product of d copies of G by permutation, and σ represents the shift on sequences, so that σ d = (d 1 , d 2 , . . . ). As the isomorphism (1) is canonical, we identify an element and its image and write:

(2) g = (g 1 , . . . , g d 0 )σ with g in Aut(T d), the g i in Aut(T σ d) and σ in S d 0 . The automorphism g t represents the action of g on the subtree T t , isomorphic to T σ d, hanging from vertex t, and the rooted component σ describes how these subtrees (T t ) t=1...d 0 are permuted.

With notation (2), for any vertex ty in T d, one has g(ty

) = σ(t)g t (y). If f = (f 1 , . . . , f d 0 )τ , then (gf )(ty) = (f • g)(ty) = τ (σ(t))f σ(t) (g t (y)) = (στ )(t)(g t f σ(t) )(y), so that gf = (g 1 f σ(1) , . . . , g d 0 f σ(d 0 ) )στ .
An automorphism g is rooted if g = (1, . . . , 1)σ for a permutation σ in S d 0 . The group of rooted automorphisms of T d is obviously isomorphic to S d 0 and can be realised canonically as a subgroup or a quotient of Aut(T d).

The set H d of automorphisms directed by the geodesic ray

1 ∞ = (111 . . . ) in T d is defined recursively. An element h is in H d if there exists h ′ in H σ d and σ 2 , . . . , σ d 0 rooted in Aut(T σ d) such that: h = (h ′ , σ 2 , . . . , σ d 0 ). (3)
There is a canonical isomorphism of abstract groups:

H d ≃ S d 1 × • • • × S d 1 × H σ d with d 0 -1 factors S d 1 . As a consequence, H d is the uncountable but locally finite product: (4) H d ≃ S d 1 × • • • × S d 1 × S d 2 × • • • × S d 2 × . . . , with d l-1 -1 factors S d l , indexed by {2, . . . , d l-1 }. Under this isomorphism, denote: h = (σ 1,2 , . . . , σ 1,d 0 , σ 2,2 , . . . , σ 2,d 1 , . . . ) with σ k,t in S d k .
The action of h ∈ H d on the rooted tree T d and its boundary ∂T d is given by:

h(1 k-1 ti k+1 i k+2 . . . ) = 1 k-1 tσ k,t (i k+1 )i k+2 . . . ,
where each vertex or boundary element is uniquely written 1

= S e 1 × • • • × S e T embeds diagonaly into S d 1 × • • • × S d 1 × • • • ≃ H d (
Aut(ET d) = S d ≀ ∂T d Aut(T d) = {ϕ : ∂T d → S d } ⋊ Aut(T d), (5)
where the action of the group Aut(T d) on functions is given by g.ϕ(x) = ϕ(gx) so that (g 1 g 2 ).ϕ = g 2 .(g 1 .ϕ). The group Aut(ET d) of automorphisms of extended tree was introduced by Bartholdi and Erschler in [BE] as "permutational wreath product over the boundary". The wreath product isomorphism (1) extends well: Proposition 2.2. There is a canonical isomorphism:

Aut(ET d) ≃ Aut(ET σ d) ≀ {1,...,d 0 } S d 0 . Proof. Any γ in Aut(ET d) is decomposed γ = ϕg, with g ∈ Aut(T d) and ϕ : ∂T d → S d .
The classical isomorphism (1) provides a decomposition g = (g 1 , . . . , g d )σ. Also the boundary of the tree can be decomposed into

d 0 components ∂T d = ∂T 1 ⊔• • •⊔∂T d with T t ≃ T σ d the
tree descended from the first level vertex t. Set ϕ t = ϕ| ∂Tt the restriction of ϕ. With these notations, the application Φ realising the canonical isomorphism is given by:

Φ(γ) = (ϕ 1 g 1 , . . . , ϕ d g d )σ ∈ Aut(ET σ d) ≀ {1,...,d 0 } S d 0 .
In order to prove the proposition, it is sufficient to check that Φ(γγ ′ ) = Φ(γ)Φ(γ ′ ).

On the one hand, γγ ′ = ϕgϕ ′ g ′ = ϕ(g.ϕ ′ )gg ′ = ψgg ′ , with ψ = ϕ(g.ϕ ′ ). As above set ψ t = ψ| ∂Tt , and as classicaly gg ′ = (g 1 g ′ σ(1) , . . . , g d g ′ σ(d) )σσ ′ , the embedding is:

Φ(γγ ′ ) = (ψ 1 g 1 g ′ σ(1) , . . . , ψ d g d g ′ σ(d) )σσ ′ . On the other hand: Φ(γ)Φ(γ ′ ) = (ϕ 1 g 1 , . . . , ϕ d g d )σ(ϕ ′ 1 g ′ 1 , . . . , ϕ ′ d g ′ d )σ ′ = (ϕ 1 g 1 ϕ ′ σ(1) g ′ σ(1) , . . . , ϕ d g d ϕ ′ σ(d) g ′ σ(d) )σσ ′ = (ϕ 1 (g 1 .ϕ ′ σ(1) )g 1 g ′ σ(1) , . . . , ϕ d (g d .ϕ ′ σ(d) )g d g ′ σ(d) )σσ ′ There remains to check ψ t = ϕ t (g t .ϕ ′ σ(t)
), and indeed for any y ∈ ∂T t ≃ ∂T σ d:

ψ t (y) = ψ(ty) = (ϕ(g.ϕ ′ ))(ty) = ϕ(ty)((g.ϕ ′ )(ty)) = ϕ(ty)ϕ ′ (g.ty) = ϕ(ty)ϕ ′ (σ(t)(g t .y)) = ϕ t (y)ϕ ′ σ(t) (g t .y) = ϕ t (y)(g t .ϕ ′ σ(t) )(y).
Functions over ∂T d supported on 1 ∞ = 1111 . . . will play a specific role. For

f ∈ S d , denote ϕ f : ∂T d → S d the function ϕ f (1 ∞ ) = f and ϕ f (x) = id if x = 1 ∞ . Note that for h in H d, one has hϕ f = ϕ f h in Aut(ET d) because h fixes the ray 1 ∞ .
Definition 2.3. A group Γ of automorphisms of the extended tree ET d is called directed when it admits a generating set of the form S ∪ H ∪ F where S is rooted, H is included in H d and elements of F have the form

ϕ f for f ∈ S d . Denote Γ = Γ(S, H, F ) such a directed group. Say a group Γ(S d 0 , H, F ) < Aut(ET d) is saturated if G(S d 0 , H) is saturated.
Saturation implies that equidistribution on H×F projects to equidistribution on each factor S d k of (4) and on the factor F which justifies the notation Γ(S d 0 , H × F ) for saturated directed groups.

Unless mentioned otherwise, use for the directed group Γ(S, H, F ) the set S ∪ H × F , where both S and H × F are finite groups themselves (hence symmetric) in the case of finitely generated saturated directed groups.

Denote H l the restriction of H < H d to levels ≥ l, i.e. the projection of H to

H σ l d = S d l+1 × • • • × S d l+1 × . . . . Also denote S l
the subgroup of S d l generated by the projections of H on the d l-1 -1 factors S d l of (4).

Proposition 2.4. Let Γ(S, H, F ) < Aut(ET d) be a directed group. There is a canonical embedding:

Γ(S, H, F ) ֒→ Γ(S 1 , H 1 , F ) ≀ S.
More generally:

Γ(S l , H l , F ) ֒→ Γ(S l+1 , H l+1 , F ) ≀ S l .
Proof. The embedding is clear from proposition 2.2 as the image of generators is given by s = (1, . . . , 1)s, h = (h ′ , σ 2 , . . . , σ d ) and ϕ f = (ϕ f , 1, . . . , 1).

Observe that if Γ(S, HF ) is saturated, then Γ(S l , H l F ) is saturated for all l.

2.3. Examples. The class of directed groups of Aut(T d) contains many examples of groups that have been widely studied in relation with torsion ( [Ale], [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], [GS], [BS]), intermediate growth ( [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], [BS], [START_REF] Erschler | On the degrees of growth of finitely generated groups[END_REF]), subgroup growth ( [Seg]), non-uniform exponential growth ([Wil1], [START_REF] Wilson | Further groups that do not have uniformly exponential growth[END_REF], [START_REF] Brieussel | Amenability and non-uniform growth of some directed automorphism groups of a rooted tree[END_REF]) and amenability ( [GZ], [BV], [START_REF] Brieussel | Amenability and non-uniform growth of some directed automorphism groups of a rooted tree[END_REF], [BKN], [AAV], [AV]).

Theorem 3.6 in [START_REF] Brieussel | Amenability and non-uniform growth of some directed automorphism groups of a rooted tree[END_REF] states that the full directed group G(S d 0 , H d) is amenable if and only if the sequence d is bounded. This result obviously extends to the setting of automorphisms of extended trees. Indeed, the group Γ(S, H, F ) is a subgroup of F ≀ ∂T d G(S, H) which is a group extension of a direct sum of finite groups (copies of F ) by the group G(S, H), hence is amenable when valency d is bounded. On the other hand, G(S, H) is a quotient of Γ(S, H, F ), so the latter inherits non-amenability when d is unbounded.

The notion of automorphisms of extended trees is a reformulation of permutational wreath product, which were introduced in [BE] in order to compute explicit intermediate growth functions (see also [START_REF] Brieussel | Growth behaviors in the range e r α[END_REF]). The boundary extension T d does not need to be a finite tree, i.e. the permutationnal wreath product F ≀ ∂T d makes sense for any group F . This was used in [BE] to make a stack of extensions of trees and compute the growth function of some finitely generated groups of their automorphisms, namely b k (r) ≈ e r α k , where α k → 1 with the number k of extensions in the stack.

2.4. Non-uniform growth and Haagerup property. This paragraph illustrates the interest of extended trees by an application that will not be used further in the rest of the article. It can be omitted at first reading.

A group is said to have the Haagerup property if it admits a proper continuous affine action on a Hilbert space (see [CCJJV]). This is for instance the case for free groups and amenable groups. Groups with the Haagerup property have attracted interest as they are known to satisfy the Baum-Connes conjecture. (1) abstractly

A d ≃ A d × • • • × A D with projection on factor d ′ denoted pr d ′ , (2) an element b ∈ A d is realised in Aut(T d) according to the recursive rule b = (b ′ , pr d 1 (b), 1, . . . , 1) for b ′ ∈ A σ d < Aut(T σ d).
Take F to be the free product A 5 * A 5 , and consider the group Γ(A d 0 , A d, A 5 * A 5 ) < Aut(ET d) which is a directed group of automorphisms of an extended tree (with infinite extension at the boundary so that A 5 * A 5 < S ∞ ). [START_REF] Wilson | Further groups that do not have uniformly exponential growth[END_REF], [START_REF] Wilson | On exponential growth and uniformly exponential growth for groups[END_REF]). For bounded valency and A d finite as above these groups are amenable ( [START_REF] Brieussel | Amenability and non-uniform growth of some directed automorphism groups of a rooted tree[END_REF]) hence have Haagerup property. For unbounded valency and A d ≃ A 5 * A 5 , these groups are non-amenable. Zuk asked whether they still have Haagerup property. The groups Γ(A d 0 , A d, A 5 * A 5 ) resemble the groups G(A d, A d) for unbounded sequences d in the sense that the "free product factor" A 5 * A 5 is "located at the boundary of the tree". Thus the proposition above hints that Wilson groups G(A d, A d) of [START_REF] Wilson | Further groups that do not have uniformly exponential growth[END_REF] have Haagerup property (but it does not prove it). It provides the first example of groups of non-uniform growth for which Haagerup property does not follow from amenability. No example of group having non-uniform growth but not Haagerup property is known.

Proof. Each of the groups A d 0 , A d and A 5 * A 5 is perfect and generated by finitely many involutions (the number of which depends only on D), so that this is also the case for Γ(A d 0 , A d, A 5 * A 5 ). Moreover, there is an isomorphism:

Γ(A d 0 , A d, A 5 * A 5 ) ≃ Γ(A d 1 , A σ d, A 5 * A 5 ) ≀ A d 0 .
(Indeed by proposition 7.2 in [START_REF] Brieussel | Amenability and non-uniform growth of some directed automorphism groups of a rooted tree[END_REF], Γ contains any commutator ([b 1 , b 2 ], 1, . . . , 1) for b 1 , b 2 a pair of elements in one of the generating groups A d 0 , A d, A 5 * A 5 . By perfection, it shows that the embedding of proposition 2.4 is onto.) This shows that Γ(A d 0 , A d, A 5 * A 5 ) belongs to a class χ (see [START_REF] Wilson | Further groups that do not have uniformly exponential growth[END_REF]) and there exists generating sets with growth exponent tending to 1. Also, the group contains a non-trivial free product, hence is non amenable, and has non-uniform exponential growth.

The group Γ(A d

0 , A d, A 5 * A 5 ) inherits Haagerup property for it is contained in (A 5 * A 5 )≀ ∂T d G(A d 0 , A d) which itself has Haagerup property. Indeed, there is a short exact sequence: 1 → (A 5 * A 5 ) ∂T d → (A 5 * A 5 ) ≀ ∂T d G(A d 0 , A d) → G(A d 0 , A d) → 1,
where (A 5 * A 5 ) ∂T d has Haagerup property and G(A d 0 , A d) is amenable, which implies Haagerup property for the middle term (example 6.1.6 in [CCJJV]).

In the remaining sections of the present article (as well as in [START_REF] Brieussel | Growth behaviors in the range e r α[END_REF]), only finite groups F are considered, which simplifies some arguments and still permits to observe various phenomena.

Rewriting process and activity of words

3.1. Rewriting process. Given a finitely generated saturated (extended) directed group Γ(S d 0 , HF ) acting on a tree T d of bounded valency, a canonical generating set is S d 0 ⊔ F H. Note that by saturation and bounded valency, both S d 0 and HF are finite subgroups of Γ(S d 0 , HF ). In the present article, the disjoint union of these subgroups is taken as generating set. In particular both 1 S d 0 and 1 HF are generators, distinct in a "word perspective". Definition 3.1. Given the generating set S d 0 ⊔ F H of a finitely generated saturated group Γ(S d 0 , HF ), a representative word is alternate if it has the form w = s 1 k 1 s 2 k 2 . . . s n k n s n+1 for some s i in S d 0 and k i in HF .

Note that any word w in this generating set admits a canonical alternate form obtained by merging packs of successive terms belonging to the same finite group S d 0 or HF . For example, the canonical alternate form of s Proposition 3.2 (Rewriting process). With the notations above, the alternate word w = s 1 k 1 . . . s n k n s n+1 can be algorithmically rewritten in the wreath product as w = (w 1 , . . . , w d 0 )σ ∅ where:

1 s 2 k 3 k -1 3 1 S d 0 k 4 1 HF is (s 1 s 2 )1 F H 1 S d 0 k 4 . The alternate form w = s 1 k 1 . . . s n k n s n+1 of a word in the generating set S d ⊔ F H is equivalent to w = k σ 1 1 . . . k σn n σ n+1 , for σ i = s 1 . . . s i , where k σ = σkσ -1 denotes the conjugate of k by σ. Remind that k j in HF is uniquely decomposed into k j = (k ′ j , b j,2 , . . . , b j,d 0 ) with k ′ j in H 1 F and b j,t in S d 1 rooted.
(1) the rooted permutation is

σ ∅ = s 1 s 2 . . . s n+1 = σ n+1 , (2) the word w t = s t 1 k t 1 . . . s t mt k t mt s t mt+1
is alternate in the generating system

S d 1 ⊔ H 1 F of the saturated directed group Γ(S d 1 , H 1 F ), of length m t ≤ n+1 2 such that m 1 + • • • + m d 0 ≤ n,
(3) the factors s t i depend only on factors b j,t ′ at times j when σ j (t) = t ′ , (4) the factors k t i depend only on factors k ′ j at times j when σ j (t) = 1.

Proof. The factor k

σ j j = σ j k j σ -1 j
has image in the wreath product:

k σ j j = (b j,σ j (1) , . . . , k ′ j , . . . , b j,σ j (d 0 ) ), with k ′ j in position σ -1 j (1)
. This shows that w t in the wreath product image of w is a product of terms b j,σ j (t) at times j when σ j (t) = 1 and terms k ′ j at times j when σ j (t) = 1. The word w t is the canonical alternate form of this product. Each factor k j furnishes a factor k ′ j to exactly one of the coordinates, so the sum of length is ≤ n. Also by looking at alternate forms, there has to be a factor k σ j j such that σ j (t) = 1, giving b j,t ′ on coordinate t, between two factors such that σ j (t) = 1, giving k ′ j on coordinate t, so that the length of w t is at most half the length of w.

Of course, the rewriting process can be iterated, and at each vertex v = ut is associated to the alternate word w another alternate word w v of length m v in the generating set

S d |v| ⊔ H |v| F of the saturated directed group Γ(S d |v| , H |v| ) defined inductively by w v = w ut = (w u ) t . Note that the word w v has length m v ≤ n 2 |v| + 1, and |v|=l m v ≤ n.

Minimal tree and activity.

Definition 3.3. The minimal tree T (w) of the alternate word w in S d 0 ⊔ HF is the minimal regular rooted subtree of T d such that m v ≤ 1 for any leaf v of T (w). Recall that a subtree T of T d is regular if whenever a vertex v belongs to T , either all its descendants vt also belong to T , or none of them does.

The minimal tree T (w) is constructed algorithmically. Indeed it contains the root ∅, and if v is in T (w), either m v ≤ 1 and no descendant of v belongs to T (w), or The leaves of the minimal tree T (w) satisfy either m v = 0 in which case they are called inactive, or m v = 1 called active leaves. The subset A(w) of the boundary (set of leaves) ∂T (w) of the minimal tree T (w) is called the active set of the word w. Its size is the activity a(w) = #A(w) of the word w. The activity of a word w = s 1 of length 0 (no factor in HF ) is a(s) = 0.

T (w) σ ∅ σ u σ u σ u w v w v σ u σ u w v ∂T 2 . . . ϕ(x) . . . ϕ(x) . . . . . . . . . ϕ(x) . . . . . . . . .
Remark 3.4. The minimal tree T (w), as well as the set of active leaves A(w), of a word w = s 1 k 1 . . . k n s n+1 depend only on the word s 1 h 1 . . . h n s n+1 where k j = ϕ f j h j , i.e. on the quotient G(S, H) of Γ(S, HF ).

The notions of minimal tree and active set allow an interesting description of the action of a word w on the tree T d. Indeed, the action of the automorphism γ = Γ w in Aut(ET d) is determined by the following data:

(1) the minimal tree T (w) and its active set A(w), (2) the permutations σ u ∈ S d |u| attached to vertices u ∈ T (w)\A(w), (3) the "short words"

w v = s v 1 k v s v 2 attached to active vertices v. The description of the short word w v = s v 1 k v s v
2 at an active vertex v can be refined into a tree action s v 1 h v s v 2 , together with a boundary function given by ϕ

f v (x) = f v for x = v(s v 1 (1))1 ∞ and ϕ fv (x) = 1 otherwise. A point x in ∂T d is called active when it is of the form x = v(s v 1 (1)
)1 ∞ for some active leaf v of T (w). If the element γ = Γ w in Γ(S, HF ) has the form γ = ϕg in the permutational wreath product (5), then the support of ϕ is included in the set A ∂ (w) of active boundary points.

3.3. Ascendance forest. Given an alternate word w in Γ(S d 0 , HF ) and the collection (w v ) v∈T (w) of words obtained by rewriting process, each word w v is a product of factors

w v = s v 1 k v 1 . . . k v mv s v mv+1 . Recall that each factor k vt i in the word w vt is a product of terms k ′v j , obtained from (k v j ) σ v j = (b v j,σ v j (1) , . . . , k ′v j , . . . , b v j,σ v j (d |v| ) ) with
k ′v j in position t, during the rewriting process of the word w v for the vertex v, into w v = (w v1 , . . . , w vd |v| )σ v .

Consider the graph AF (w) with set of vertices the collection (k v i ) v,i of factors in H |v| F appearing in the rewritten words (w v ) v∈T (w) , where a pair of factors (k v i , k v ′ j ) is linked by an edge when v ′ = vt and the term k ′v i appears in k vt j . Fact 3.5. The graph AF (w) is a forest, i.e. a graph with no loop. More precisely, AF (w) is a union of trees (τ v ) v∈A(w) indexed by the active set of w. Moreover, if v is an active leaf, then

k v = k j ∈∂τv k (|v|) j
is the product ordered with j, where k

(|v|) j
is the restriction of k j ∈ HF to H |v| F . In particular:

f v = k j ∈∂τv f j . Proof. Let v = t 1 . . . t l be an active leaf with w v = s v 1 k v s v 2 . The term k v is a product of terms k ′t 1 ...t l-1 j in w t 1 ...t l-1 (for those j's where σ t 1 ...t l-1 j
(1) = t l ), which are the neighbours of the vertex k v in the graph AF (w). This describes the ball of center k v and radius 1.

Inductively, each factor k t 1 ...t l-r i which represents a vertex in the sphere of center k v and radius r is a product of terms k

′t 1 ...t l-r-1 j in w t 1 ...t l-r-1 (for those j's where σ t 1 ...t lr -1 j (1) = t l-r ), which form the link of k t 1 ...t l-r i
in the sphere of radius r + 1. Now each factor k ′t 1 ...t λ j in a word of level λ contributes to exactly one factor k t 1 ...t λ t λ+1 i , which rules out the possibility of a loop.

So the connected component of k v in the graph AF (w) is a tree τ v , it is also the l-ball of center k v and the leaves of τ v form the l-sphere, which is precisely the set of factors k j of w that lie in τ v . By construction of AF (w), k v is the required ordered product.

Remark 3.6. Observe that the ascendance forest AF (w) of a word w = s 1 k 1 . . . k n s n+1 depends only on the word s 1 h 1 . . . h n s n+1 for k j = ϕ f j h j . Indeed given a factor k t 1 ...t λ i , its link to factors in level λ + 1 is determined by the factor σ t 1 ... ) j . Thus the link of k v i does not depend on the sequence (f j ) j∈{1,...,n} . A consequence of this observation and the preceding fact is that for any function ϕ with support included in A ∂ (w), there exists (f j ) j∈{1,...,n} such that ϕs 1 h 1 . . . h n s n+1 = Γ s 1 ϕ f 1 h 1 . . . ϕ fn h n s n+1 . Moreover the number of such n-tuples is independent of the function ϕ. This shows:

Fact 3.7. Given g = s 1 h 1 . . . h n s n+1 , for any ϕ : ∂T d → F with support in A ∂ (g), one has: #{f 1 , . . . , f n ∈ F |ϕg = Γ s 1 ϕ f 1 h 1 . . . ϕ fn h n s n+1 } = 1 #F #A ∂ (g)
.

3.4. Counting activity. The inverted orbit of a product w = r 1 . . . r k of automorphisms [BE]). The inverted orbit of w -1 coincides with the activity set A ∂ (w) defined in section 3.2. The notion of activity is classical in the context of automorphisms of rooted trees (see [Nek], [Sid]).

r i ∈ Aut(T d) is the set O(w) = {1 ∞ , r k 1 ∞ , r k-1 r k 1 ∞ , . . . , r 1 . . . r k 1 ∞ } (see
Proposition 3.8. On a finitely generated saturated directed group Γ(S d 0 , HF ) acting on a tree of bounded valency d, the activity function a(w) which for w = s 1 ϕ f 1 h 1 . . . ϕ fn h n s n+1 counts equivalently:

(1) the size of the set A(w) of active leaves in the minimal tree T (w) ⊂ T d,

(2) the size of the set A ∂ (w) of active boundary points in ∂T d,

(3) the number of trees (i.e. connected components) in the ascendance forest AF (w), (4) the size of the inverted orbit

O(s -1 n+1 h -1 n . . . h -1 1 s -1 1 )
in the sense of [BE],

satisfies under rewriting process w = (w 1 , . . . , w d 0 )σ ∅ :

a(w) = a(w 1 ) + • • • + a(w d 0 ).
Moreover, the constraint a(w) ≤ r only permits to describe at most exponentially many elements in Γ(S d 0 , HF ), i.e. there exists a constant C depending only on D = max{d i } and #HF such that:

#{γ ∈ Γ(S d 0 , HF )|∃w = Γ γ, a(w) ≤ r} ≤ C r .
Note that a(w) is the activity for words in the group Γ(S d 0 , HF ) and a(w t ) is the activity function for words in the group Γ(S d 1 , H 1 F ).

Proof. Points (1), (2), (3) are clear from the descriptions above. Point (4) is shown by induction on n. Suppose s

1 k 1 . . . k n-1 s n = ϕ n g n for g n = s 1 h 1 . . . h n-1 s n , then s 1 k 1 . . . k n-1 s n ϕ fn h n = ϕ n (g n .ϕ fn )g n h n and the point g -1 n (1 ∞
) which is the support of the function g n .ϕ fn is added to the set of active leaves A ∂ (w).

The equality on activities under rewriting process is trivial when n ≤ 1, and if n ≥ 2 then the minimal tree is not restricted to the root, one has

T (w) = T (w 1 ) ⊔ • • • ⊔ T (w d 0 ) ⊔ {∅}, so that A(w) = A(w 1 ) ⊔ • • • ⊔ A(w d 0 )
, and equality holds.

In order to prove the exponential bound, first observe that #∂T (w) ≤ Da(w). It is obvious if ∂T (w) is the root {∅} or the first level {1, . . . , d 0 }, and then clear for arbitrary T (w) by induction on the size #T (w) since

∂T (w) = ∂T (w 1 ) ⊔ • • • ⊔ ∂T (w d 0 ).
Now if a(w) ≤ r, its minimal tree T (w) has a boundary of size ≤ Dr, so there are ≤ K r possibilities for T (w) (for some K depending only on D). To finish the description of γ = Γ w, one has to choose permutations σ u at vertices u ∈ T (w)\∂T (w), for which there are ≤ D! Dr possibilities, and short words s v 1 k v s v 2 at leaves v ∈ ∂T (w), for which there are ≤ (D! 2 #HF ) Dr possibilities.

Random walks

Given a finitely generated saturated directed group Γ(S d 0 , HF ), consider random alternate words Y n = s 1 k 1 s 2 k 2 . . . s n k n s n+1 , where s i in S d 0 and k i in HF are equidistributed and all factors are independent. Such a random alternate product Y n is the simple random walk on Γ(S d 0 , HF ) for the symmetric generating set S d 0 HF S d 0 (for the product of two independent equidistributed variables s ′ i s i+1 in S d 0 is another equidistributed variable, independent of other factors).

4.1. Inheritance of random process through wreath product. Given a random alternate word Y n , the rewriting process of proposition 3.2 furnishes an image in the wreath product

Y n = (Y 1 n , . . . , Y d 0 n )τ n . Each coordinate Y t
n is a random process on words in S d 1 ⊔ H 1 F by proposition 2.4, which turns out to be a random alternate word of random length.

Lemma 4.1. Denote Y n = (Y 1 n , . . . , Y d 0 n )τ n
the alternate words obtained by rewriting process of a random alternate word Y n = s 1 k 1 s 2 k 2 . . . s n k n s n+1 in a finitely generated saturated directed group Γ(S d 0 , HF ). Then:

(1) The rooted random permutation is τ n = s 1 . . . s n+1 hence is equidistributed.

(2) The random length m t of the random product Y t n has the law of the sum of n independent Bernoulli variables (u j ) on {0, 1} with P (u j = 1) = p 0 = d 0 -1

d 2 0 .
In particular, by the law of large numbers m t ∼ p 0 n almost surely, and by the principle of large deviations, for any θ > 0, there exists c θ < 1 such that

P m t n / ∈ [p 0 -θ, p 0 + θ] ≤ c n θ .
( This lemma is a restating of lemma 4.6 in [START_REF] Brieussel | Croissance et moyennabilité de certains groupes d'automorphismes d'un arbre enraciné[END_REF]. A brief proof is given below.

Proof. As in proposition 3.2, write Y n = k σ 1 1 . . . k σn n σ n+1 , where each factor has image in the wreath product k

σ j j = (b j,σ j (1) , . . . , k ′ j , . . . , b j,σ j (d 0 ) ) with k ′ j ∈ H 1 F in position σ j (t) and b j,s ∈ S d 1 . As (σ j ) n
j=1 is a sequence of independent terms equidistributed in S d 0 (for σ j = s 1 . . . s j with (s i ) n i=1 is a sequence of independent terms equidistributed in S d 0 ), the position sequence (σ j (t)) n j=1 is equidistributed in {1, . . . , d 0 } for any choice of t.

Then for a fixed t, Y t n is a product of n terms which are either b j,σ j (t) at times j when σ j (t) = 1, which happens with probability d 0 -1 d 0 , or k ′ j at times j when σ j (t) = 1, which happens with probability 1 d 0 . In both cases, the factors are equidistributed in S d 1 or H 1 F respectively because k j is equidistributed in HF by saturation. Moreover, all the terms are independent. Now to obtain an alternate word, the runs of successive terms that belong to the same finite group (either S d 1 or H 1 F ) are merged, the factors (s t j , k t j ) j are still equidistributed and independent.

There remains to count the number of such runs, given by:

2m t + 1 = 1 + n j=1
1 {(σ j (t)=1 and σ j+1 (t) =1) or (σ j (t) =1 and σ j+1 (t)=1)} .

Knowing that P (σ j (t) = 1) = 1 d 0 and P (σ j (t) = 1) = d 0 -1 d 0 independently of previous terms, two successive terms belong to different finite groups with probability 2 d 0 -1

d 0 1 d 0 = 2p 0 . Note that
d = (d i ) i of integers ≥ 2, define p = (p i ) i by p i = d i -1 d 2 i . Note d = min(d i ), D = max(d i ), p = max(p i ) = d-1 d 2 and P = min(p i ) = D-1 D 2 .
Define the exponent function β(n) associated to the valency sequence d by:

k(n) = k d(n) = min{k|p 0 . . . p k n ≤ 1} and β(n) = β d(n) = log(d 0 . . . d k(n) ) log n .
Moreover, given a small θ = 0 and an integer N 0 depending only on θ, set:

k θ (n) = min{k|(p 0 + θ) . . . (p k + θ)n ≤ N 0 } and β θ (n) = log(d 0 . . . d k θ (n) ) log n .
For N 0 = 1, the function k θ (n) is increasing with θ, and β θ (n) -→ θ→0 β(n) for a fixed n.

Proposition 4.2. There exists a function ε(θ) -→ θ→0 0 such that for all n large enough (depending on θ):

|β(n) -β θ (n)| ≤ ε(θ).
Proof. Assume θ > 0 (similar proof for θ < 0). For n large enough,

k θ (n) ≥ k(n),
and the difference is:

|β(n) -β θ (n)| = | log n (d 0 . . . d k(n) ) -log n (d 0 . . . d k θ (n) )| = log n (d k(n)+1 . . . d k θ (n) ),
hence is bounded by:

|β(n) -β θ (n)| ≤ |k θ (n) -k(n)| log D log n .
By definition of k(n) and k θ (n), there are inequalities:

N 0 n ≥ (p 0 + θ) . . . (p k θ (n) + θ) > N 0 (p k θ (n) + θ) n ≥ p 0 . . . p k(n) N 0 (P + θ),
so that:

(p + θ) k θ (n)-k(n) ≥ (p k(n)+1 + θ) . . . (p k θ (n) + θ) = (p 0 + θ) . . . (p k θ (n) + θ) (p 0 + θ) . . . (p k(n) + θ) ≥ p 0 p 0 + θ . . . p k(n) p k(n) + θ N 0 (P + θ) ≥ P P + θ k(n) N 0 (P + θ),
which shows that for some constant K:

|k θ (n) -k(n)| ≤ k(n) log( P P +θ ) log(p + θ) + K. Notice that log n | log P | ≤ k(n) ≤ log n
| log p| to finally obtain:

|β θ (n) -β(n)| ≤ log D | log p| log( P P +θ ) log(p + θ) + K ′ log n .
The proposition follows from the limit | log( P P +θ )| -→ θ→0 0. Fact 4.3. There is a bound on β(n) depending only on the bounds d ≤ d i ≤ D on the valency of the rooted tree T d. Namely for some constant C depending only on D:

β d ≤ β(n) ≤ β D + C log n ,
where

β d = log d -log p = log d log( d 2 d-1 ) = 1 1+ log d d-1 log d = 1 2- log(d-1) log d .
Note that β 2 = 1 2 and β d -→ d→∞ 1.

Proof. Note that:

β(n) = log(d 0 . . . d k(n) ) log n ≥ log(d 0 . . . d k(n) ) -log(p 0 . . . p k(n) ) , β(n) ≤ log(d 0 . . . d k(n) ) -log(p 0 . . . p k(n) ) + log p k(n) ≤ log(d 0 . . . d k(n) ) -log(p 0 . . . p k(n) ) + C log n . As p i = d i -1 d 2 i , simply compute: log(d 0 . . . d k(n) ) log( d 2 0 d 0 -1 . . . d 2 k(n) d k(n) -1 ) = 1 1 + log( d 0 d 0 -1 )+•••+log( d k(n) d k(n) -1 ) log d 0 +•••+log d k(n) ≤ 1 1 + log( D D-1 ) log D
, and similarly for the lower bound, by the inequality on ratio of average:

log( D D-1 ) log D ≤ log( d 0 d 0 -1 ) + • • • + log( d k(n) d k(n) -1 ) log d 0 + • • • + log d k(n) ≤ log( d d-1 ) log d .
For a real number x > 0, define h d(x) = d 0 . . . d k(x) for the unique integer k(x) such that 1 p 0 . . .

1 p k(x) ≥ x > 1 p 0 . . . 1 p k(x)-1 . In particular, n β d(n) = h d(n)
for any integer n.

Fact 4.4. Given a non-decreasing function g(x) such that:

dg(x) ≤ g d 2 d -1 x and g D 2 D -1 x ≤ Dg(x),
there exists a sequence d in {d, D} N and a constant C such that:

1 C g(x) ≤ h d(x) ≤ Cg(x). Proof. Set x k = 1 p 0 . . . 1 p k so that h(x k+1 ) = d 0 . . . d k+1 = h(x k )d k+1 and x k+1 = 1 p k+1 x k .
Assume by induction that d 0 , . . . , d k are constructed. Then:

(1) if h(x k ) g(x k ) ≥ 1, set d k+1 = d, and obtain:

dh(x k ) Dg(x k ) ≤ dh(x k ) g( 1 P x k ) ≤ h(x k+1 ) g(x k+1 ) = h( 1 p x k ) g( 1 p x k ) ≤ dh(x k ) dg(x k ) , (2) if h(x k ) g(x k ) < 1, set d k+1 = D and obtain: Dh(x k ) Dg(x k ) ≤ Dh(x k ) g( 1 P x k ) = h(x k+1 ) g(x k+1 ) ≤ Dh(x k ) g( 1 p x k ) ≤ Dh(x k ) dg(x k ) .
This shows that d D ≤ h(x k ) g(x k ) ≤ D d . As moreover P p ≤ x k x k+1 ≤ p P and g is non-decreasing, this proves the fact. 4.3. Expected activity. The expectation of activity is ruled by the exponent sequence.

Lemma 4.5. For any θ > 0 and n large enough, there exists C θ > 0 such that:

1 C θ n β -θ (n) ≤ Ea(Y n ) ≤ C θ n β θ (n) ,
where the functions β(n), β θ (n) are defined in section 4.2. In particular, for any ε > 0 and n large enough:

log Ea(Y n ) log n -β(n) ≤ ε.
For the following proof observe the fact that for any words a(ww ′ ) ≥ a(w) by proposition 3.8(4), so that the function Ea(Y n ) is non-decreasing with n.

Proof. By proposition 3.8, the activity of Y n relates to activity on the inherited process by a

0 (Y n ) = a 1 (Y 1 n ) + • • • + a 1 (Y d 0 n ),
Ea 1 (Y t n ) = n i=0 E(a 1 (Y t n )|m t = i)P (m t = i) ≤ i≤(p 0 +θ)n P (m t = i)Ea 1 (Y i ) + nP (m t ≥ (p 0 + θ)n) ≤ Ea 1 (Y ′ (p 0 +θ)n ) + nc n θ ,
where c θ < 1 (use that Ea 1 (Y ′ n ) is non-decreasing to bound the sum). This shows that for N 0 large enough so that d 0 N 0 c N 0 θ ≤ 1 and n ≥ N 0 :

Ea 0 (Y n ) ≤ d 0 Ea 1 (Y ′ (p 0 +θ)n ) + 1.
Note that c θ hence N 0 depend on θ and on d 0 , but as the valency is bounded they can be chosen uniform for all d i . This permits to iterate the above inequality to get for all k:

Ea 0 (Y n ) ≤ d 0 . . . d k Ea k+1 (Y (k+1) (p 0 +θ)...(p k +θ)n ) + d 0 . . . d k-1 + • • • + d 0 + 1, provided n is large enough. Recall that Y (k) m is a random alternate word of length m in Γ(S d k , H k F ). For k(n) = min{k|(p 0 + θ) . . . (p k + θ)n ≤ N 0 }, this shows: Ea 0 (Y n ) ≤ d 0 . . . d k(n) (Ea k θ (n)+1 (Y (k θ (n)+1) N 0 ) + 1) ≤ n β θ (n) (N 0 + 1),
by the trivial estimation a k (Y N 0 ) ≤ N 0 for any k and the definition of β θ (n).

Similarly for the lower bound:

Ea 0 (Y n ) ≥ d 0 Ea 1 (Y ′ (p 0 -θ)n )-1 ≥ d 0 . . . d k Ea k+1 (Y (k+1) (p 0 -θ)...(p k -θ)n )-(d 0 . . . d k-1 +• • •+1), so that for k = k -θ (n) = min{k|(p 0 -θ) . . . (p k -θ)n ≤ N 0 }, one has: Ea 0 (Y n ) ≥ 1 2 d 0 . . . d k -θ (n) = 1 2 n β -θ (n) , by the trivial estimate Ea k (Y (k) N ) ≥ 3 2 for any k and N ≥ 3 (indeed, a k (Y (k)
N ) ≥ 2 as soon as there are two distinct elements among {σ -1 1 (1), σ -1 2 (1), σ -1 3 (1)}, which happens with probability ≥ 3 4 for any value of d k ).

Entropy exponents

5.1. Main theorem. Given a valency sequence d = (d i ) i and p i = d i -1

d 2 i
, recall that the exponent sequence β d(n) is defined by:

β d(n) = β(n) = log(d 0 . . . d k(n) ) log n
where k(n) = min{k|p 0 . . . p k n ≤ 1}.

Theorem 5.1. Let Γ = Γ(S d 0 , HF ) be a finitely generated saturated directed subgroup of Aut(ET d), µ the measure equidistributed on S d 0 HF S d 0 , and β(n) the exponent sequence of d, then for any ε > 0 and n large enough:

log H Γ,µ (n) log n -β(n) ≤ ε.
In particular, h(Γ, µ) = lim sup β(n) and h(Γ, µ) = lim inf β(n).

Fact 4.3 ensures that if d ≤ d i ≤ D for all i, then: 1 2 ≤ β d ≤ h(Γ, µ) ≤ h(Γ, µ) ≤ β D < 1.
Proof. First prove the upper bound, which is a straightforward generalisation of proposition 4.11 in [BKN]. Note the similarity with the upper bound in lemma 4.5. Indeed, under rewriting process

Y n = (Y 1 n , . . . , Y d 0 n )τ n one has: H(Y n ) ≤ H(Y 1 n ) + • • • + H(Y d 0 n ) + H(τ n ), where τ n is equidistributed on S d 0 so H(τ n ) ≤ C for a constant C depending only on D.
By lemma 4.1, the law of Y t n |m t under the length condition m t is the law of a random alternate product Y ′ mt in the group Γ(S d 1 , H 1 F ), and the length m t has the binomial law of n i=1 u i for independent u i in {0, 1} with P (u i = 1) = p 0 , of entropy bounded by C log n for C depending only on D. This ensures (lemma A.4 in [BKN]):

H(Y t n ) ≤ n m=0 H(Y ′ m )P (m t = m) + H(m t ) ≤ H(Y ′ (p 0 +θ)n ) + nP (m t ≥ (p 0 + θ)n) + C log n
, by splitting the sum at m = (p 0 + θ)n for an arbitrary θ > 0. By large deviation principle, there exists c θ < 1 such that P (m t ≥ (p 0 + θ)n) ≤ c n θ . Thus there is N 0 depending only on θ and D such that for n ≥ N 0 one has (for a slightly larger constant

C since nc n θ = o(log n)) : H(Y n ) ≤ d 0 H(Y ′ (p 0 +θ)n ) + C log n.
As for expected activity, this permits to integrate

H(n) = sup k≥0 {H(Y (k) n )} ≤ Cn, where Y (k) n
is a random alternate product in the group Γ(S d k , H k F ) and C is a uniform constant depending only on the sizes of the generating sets S d k ⊔ H k F , hence only on D and #HF , into:

H(n) ≤ d 0 . . . d k H((p 0 + θ) . . . (p k + θ)n) + (d 0 . . . d k-1 + • • • + 1)C log n,
as long as k ≤ k θ (n), i.e. when (p 0 + θ) . . . (p k-1 + θ)n ≥ N 0 (see section 4.2 for definition of k θ (n) and β θ (n)). Thus: θ) for n large enough, by proposition 4.2.

H(Y n ) ≤ H(n) ≤ d 0 . . . d k θ (n) (CN 0 + C log n) = n β θ (n) (CN 0 + C log n), and H(Y n ) ≤ n β(n)+2ε(
To prove the lower bound, the following fact is useful: Fact 5.2. For γ = ϕg in Γ(S d 0 , HF ) = F ≀ ∂T G(S d 0 , H), one has:

P (Y n = γ) ≤ 1 #F #supp(ϕ)
.

Proof of fact 5.2. Denote Y n = Γ ϕ n g n , and remark that supp . This permits to compute by conditioning on activity:

(ϕ n ) ⊂ A ∂ (Y n ) of size a(Y n ).
P (Y n = γ) = n a=1 P (Y n = γ|a(Y n ) = a)P (a(Y n ) = a) ≤ a≥#supp(ϕ) P (ϕ n = ϕ|a(Y n ) = a)P (a(Y n ) = a) ≤ a≥#supp(ϕ) 1 #F a P (a(Y n ) = a) ≤ 1 #F #supp(ϕ)
This fact guarantees:

H(Y n ) = - γ∈Γ P (Y n = γ) log P (Y n = γ) ≥ C γ∈Γ P (Y n = γ)#supp(ϕ) = CE µ * n #supp(ϕ) = CE#supp(ϕ n ),
and the expected value of the size of the support of ϕ n relates to activity.

More precisely by fact 3.7, given A ∂ (g n ), the function

ϕ n : A ∂ (g n ) → F is random, so that: E[#supp(ϕ n )|A ∂ (g n )] = #F -1 #F #A ∂ (g n ).
This permits once again to compute by conditioning on activity:

E#supp(ϕ n ) = n a=1 E[#supp(ϕ n )|#A(Y n ) = a]P [#A(Y n ) = a] = n a=1 #F -1 #F aP [#A(Y n ) = a] = #F -1 #F Ea(Y n ).
By lemma 4.5, conclude:

H(Y n ) ≥ C #F -1 #F Ea(Y n ) ≥ C #F -1 #F n β(n)-ε .
Note that the proof for the upper bound remains valid for the group G(S, H) < Aut(T d), i.e. when the group F is trivial, but the lower bound is true only with a non-trivial finite group F (otherwise fact 5.2 is obviously empty).

Remark 5.3. In information theory, the entropy is the "average number of digits" needed to describe some data. In this heuristic point of view, theorem 5.1 is a corollary of lemma 4.5.

Indeed, the activity a(w) of a word w is equivalent to the size of the minimal tree T (w) defined in section 3.2 (recall a(w) ≤ #∂T (w) ≤ Da(w)). Moreover, the element γ = Γ w in Γ is described by figure 1, with σ u for u non-active vertices, w v for v active vertices and ϕ(x) at active boundary points x. As each of them is described by ≤ C digits for some C depending uniquely on the bound D on valency, the element γ is described with ≤ C#T (w) ≈ a(w) digits. Moreover, since any function ϕ : A ∂ (w) → F appears equaly likely, one needs at least a(w) digits to describe γ.

Figure 1 is in this sense the "best description" of the element γ in Γ (position in the Cayley graph) represented by the word w (path in the Cayley graph). The loss of information from w to γ is somewhat described by the graph structure of the ascendance forest AF (w) of section 3.3. 5.2. Precise entropy exponent and oscillation phenomena. Theorem 5.1 exhibits a large variety of behaviors for entropy of random walk. In particular, it implies theorem 1.2 for 1 2 ≤ α ≤ β < 1. Corollary 5.4. For any 1 2 ≤ β < 1, there is a valency sequence d such that the entropy exponent of the random walk Y n on a finitely generated saturated directed group Γ(S d 0 , HF ) < Aut(ET d) is: Remark 5.5. This corollary shows in particular that any saturated directed group of a binary tree has entropy exponent h(Γ, µ) = 1 2 . This is the case of the groups Γ ω = F ≀ ∂T 2 G ω for G ω an Aleshin-Grigorchuk group, for which a great variety of growth behaviors are known. For instance, Γ (012) ∞ has growth function b (012) ∞ (r) ≈ e r α 0 for an explicit α 0 < 1 ( [BE]), and for any α ∈ [α 0 , 1] there is a group G ω(α) with growth such that lim [START_REF] Brieussel | Growth behaviors in the range e r α[END_REF]). Considering the entropy, all these growth behaviors collapse to a unique entropy exponent.

h(Γ, µ) = β. Proof. Take d ≤ D such that β 2 ≤ β d = log d log p ≤ β ≤ log D log P = β D < 1. There exist λ ∈ [0, 1] such that β = log(d λ D 1-λ ) log(p λ P 1-λ ) .
log log b ω(α) (r) log r = α ([
Corollary 5.6. For any 1 2 ≤ α < β < 1, there is a valency sequence d such that the lower and upper entropy exponents of the random walk Y n on a finitely generated saturated directed group Γ(S d 0 , HF ) < Aut(ET d) are:

h(Γ, µ) = α and h(Γ, µ) = β.
Proof. By theorem 5.1, it is sufficient to construct an appropriate exponent sequence in order to prove the corollary. Take d ≤ D such that β d ≤ α < β ≤ β D . Construct a sequence d such that d i ∈ {d, D} for all i according to the following rules.

Recall the definition (see section 4.2) of β(n) as satisfying n

β(n) = d 0 . . . d k(n)
where k(n) as the unique integer such that

p k(n) n < p 0 . . . p k(n) ≤ 1 n .
In order to ease the reading of the present proof, use the shortcut notation p 0 . . . p k(n) ≈ 1 n . There exists a constant C depending uniquely on D such that the following statements are true if all relations x ≈ y below are replaced by y

C ≤ x ≤ Cy. Suppose k(n) is such that p 0 . . . p k(n) ≈ 1 n and d 0 . . . d k(n) ≈ n α for some n (hence |β(n) -α| ≤ C log n ), then set d k(n)+1 = • • • = d k(n)+l = D
for l such that for some minimal integer m:

P l n ≈ p 0 . . . p k(n) P l = p 0 . . . p k(n)+l ≈ 1 m , n α D l ≈ d 0 . . . d k(n) D l = d 0 . . . d k(n)+l ≈ m β . This forces n α D l ≈ n P l β , hence l = β-α log(P β D) log n + o(log n). Suppose l(m) is such that p 0 . . . p l(m) ≈ 1 m and d 0 . . . d l(m) ≈ m β for some m (hence |β(m) -β| ≤ C log m ), then set d l(m)+1 = • • • = d l(m)+k = d
for k such that for some minimal integer n:

p k m ≈ p 0 . . . p l(m) p k = p 0 . . . p l(m)+k ≈ 1 n , m β d k ≈ d 0 . . . d l(m) d k = d 0 . . . d l(m)+k ≈ n α . This forces m β d k ≈ m p k α , hence k = α-β log(p α d) log m + o(log m). This process produces a sequence d such that α -C log n ≤ β(n) ≤ β + C
log n for all n. Moreover, d 0 . . . d k(n) ≈ n α for infinitely many n and d 0 . . . d l(m) ≈ m β for infinitely many m. Hence h(Γ, µ) = α, and h(Γ, µ) = β.

Remark 5.7. The above two corollaries are obtained by taking particular instances of exponent functions β(n). Theorem 5.1 provides a variety of behaviors for entropy functions. For instance similarly to theorems 7.2 on growth functions in [START_REF] Grigorchuk | Degrees of growth of finitely generated groups and the theory of invariant means[END_REF] and [START_REF] Brieussel | Growth behaviors in the range e r α[END_REF], there exists uncountable antichains of entropy functions with h(Γ, µ) = α < β = h(Γ, µ) for any given 1 2 ≤ α < β < 1, as easily proved by playing with exponent functions. 5.3. Frequency of oscillations. Corollary 5.6 shows that at different scales, the entropy exponent of a random walk can take different values. In order to study the difference between such scales, given 1 2 ≤ α ≤ β ≤ 1 and a function H(n), introduce the following quantities, called respectively upper and lower pseudo period exponents of the function H(n) for α and β :

u H (α, β) = inf{ν|∃N 0 , ∀n ≥ N 0 , if H(n) ≤ n α , then ∃n ≤ m ≤ n ν , H(m) ≥ m β }, l H (α, β) = inf{λ|∃N 0 , ∀m ≥ N 0 , if H(m) ≥ m β , then ∃m ≤ n ≤ m λ , H(n) ≤ n α }.
For H = H Γ,µ entropy of a finitely supported measure µ on a group Γ, write u H (α, β) = u Γ,µ (α, β) and l H (α, β) = l Γ,µ (α, β).

Note that by playing with the sequence d in the proof of corollary 5.6, one can easily produce examples of random walks with arbitrarily large pseudo period exponents, i.e. low frequency. To study how high the frequency may be, i.e. how small the pseudo periods, introduce the functions:

u(α, β) = inf{u Γ,µ (α, β)| µ finitely supported symmetric measure on a group Γ}, l(α, β) = inf{l Γ,µ (α, β)| µ finitely supported symmetric measure on a group Γ}.
The finitely generated saturated directed groups of theorem 5.1 will provide the upper bounds in the following.

Theorem 5.8. For 1 2 < α ≤ β < 1, u(α, β) = α -1 β -1 , and
β α ≤ l(α, β) ≤ β -1 2 α -1 2 .
Proof. The lower bounds follow from elementary properties of entropy. For a submultiplicative function

H(n) ≤ n α implies H(kn) ≤ kn α , so that if H(kn) ≥ (kn) β , then (kn) β ≤ kn α , so kn ≥ n 1-α 1-β and u H (α, β) ≥ 1-α 1-β . For an increasing function H(m) ≥ m β and H(n) ≤ n α imply n ≥ m β α , so l H (α, β) ≥ β α .
Concerning the upper pseudo period exponents, the proof of corollary 5.6 shows that given n, one can take m ≤ C n P l for l ≤ ( β-α log(P β D) + ε) log n, where C depends only on D and ε > 0 is arbitrary, i.e. m ≤ n ν for:

ν = 1 - (β -α) log P log(P β D) -ε log P = 1 - β -α β + log D log( D-1 D 2 ) + ε| log P |.
As D tends to infinity:

log D log( D-1 D 2 ) = log D log(D -1) -2 log D = 1 log(D-1) log D -2 -→ -1,
which proves:

u(α, β) ≤ 1 - β -α β -1 = α -1 β -1 .
Similarly for the lower pseudo period exponent, the proof of corollary 5.6 shows that given m, one can take n ≤ C m p k for k = ( α-β log(p α d) + ε) log m, i.e. n ≤ m λ for:

λ = 1 - (α -β) log p log(p α d) -ε log p = 1 - α -β α + log d log( d-1 d 2 )
+ ε| log p|.

Taking d = 2, this proves:

l(α, β) ≤ 1 + β -α α -1 2 = β -1 2 α -1 2 .
Remark 5.9. The value u(α, β) = α-1 β-1 is tightly related to subadditivity of entropy, which implies in particular that h(Γ, µ) ≤ 1 for any group Γ with finitely supported measure µ. Also theorem 5.1 shows that the upper bound l(α, β)

≤ β-1 2 α-1 2
is optimal among saturated directed groups with the measure µ equidistributed on S d 0 HF S d 0 . It is unclear whether this bound is optimal in general. It could be related to question 9.3 on lower bound h(Γ, µ) ≥ 1 2 .

5.4. Drift of the random walk. Theorem 5.1 provides estimates on the drift L Γ,µ (n) = E||Y n || of the random walk Y n of step distribution µ equidistributed on S d 0 HF S d 0 , where ||.|| is the word norm for some (arbitrary) generating set.

Corollary 5.10. For any ε > 0 and n large enough:

β(n) -ε ≤ log L Γ,µ (n) log n ≤ 1 + β(n) 2 + ε.
Proof. Lemma 6 and 7 in [START_REF] Erschler | On drift and entropy growth for random walks on groups[END_REF] show that there are c 1 , c 2 , c 3 > 0 with:

c 1 H Γ,µ (n) -c 2 ≤ L Γ,µ (n) ≤ c 3 n(H Γ,µ (n) + log n).
Combine with theorem 5.1.

6. Return probability 6.1. General estimates. Given a valency sequence d = (d i ) i , set:

l(n) = l d(n) = max{l| d 3 0 d 0 -1 . . . d 3 l d l -1 = d 0 p 0 . . . d l p l ≤ n},
and define the auxiliary exponent sequence:

β ′ (n) = β ′ d(n) = log(d 0 . . . d l(n) ) log n . In particular, p 0 . . . p l(n) n ≈ d 0 . . . d l(n) = n β ′ (n) .
Theorem 6.1. For any ε > 0 the return probability of the simple random walk Y n with generating set S d 0 HF S d 0 on the saturated directed group Γ(S d 0 , HF ) < Aut(ET d) satisfies for n large enough:

β ′ (n) -ε ≤ log(-log P (Y n = id)) log n ≤ β(n) + ε.
In particular, p(Γ) ≥ lim inf β ′ (n) and p(Γ) ≤ lim sup β(n).

For instance in the case of constant valency d, one has:

β ′ d = 1 3 -log(d-1) log d ≤ log(-log P (Y n = id)) log n ≤ 1 2 -log(d-1) log d = β d .
Note that β ′ 2 = 1 3 and β ′ d -→ d→∞ 1 2 for lower bounds, compared with β 2 = 1 2 and β d -→ d→∞ 1 for upper bounds.

Proof. Proposition 4.5 implies that for n large enough:

P (a(Y n ) ≥ n β(n)+ε ) ≤ Ea(Y n ) n β(n)+ε ≤ n β(n)+ ε 2 n β(n)+ε = n -ε 2 -→ 0.
Using the fact that for fixed n, the function P (Y n = γ) is maximal at γ = id by symmetry of the random walk, and the inequality of proposition 3.8 deduce:

1 ←-P (a(Y n ) ≤ n β(n)+ε ) = {γ|∃w= Γ γ,a(w)≤n β(n)+ε } P (Y n = γ) ≤ P (Y n = id)C n β(n)+ε .
This proves the upper bound.

Recall that given a word Y n of length n, the rewriting process provides for each vertex v ∈ T d a word Y v n of random length m v (proposition 3.2). Given θ > 0 small enough so that for any n large enough l(n) ≤ k -θ (n) (defined in section 4.2 by (p 0θ) . . . (p k -θ (n)θ)n ≈ N 0 for an arbitrary N 0 ≥ 1, so that the inequality holds for large n as soon as d i -1 n) , there exists a vertex v in T d such that:

d 2 i -θ > d i -1 d 3 i for all i), observe the: Fact 6.2. For a word Y n with a(Y n ) < n β ′ (
(1) |v| ≤ l(n), (2) there is t such that m vt < (p |v| -θ)m v , (3) m v ≥ (p 0 -θ) . . . (p |v|-1 -θ)n.
Proof of fact 6.2. By contradiction assume that for all |v| ≤ l(n) and t one has m vt ≥ (p |v|θ)m v . Then by induction on |v|, for all v in level l(n): n) , which is a contradiction. This shows the existence of a vertex v satisfying (1) and (2). Such a vertex that is closest to the root also satisfies (3). This fact 6.2 guarantees that:

m v ≥ (p 0 -θ) . . . (p l(n)-1 -θ)n ≥ N 0 C(p l(n) -θ) . . . (p k -θ (n) -θ) ≥ 1, so that a(Y v n ) ≥ 1. Then a(Y n ) ≥ |v|=l(n) a(Y v n ) ≥ d 0 . . . d l(n) = n β ′ (
P (a(Y n ) ≤ n β ′ (n) ) ≤ |v|≤l(n) P [∃t, m vt ≤ (p |v| -θ)m v and m v ≥ (p 0 -θ) . . . (p |v|-1 -θ)n]. Now P [m vt ≤ (p |v| -θ)m v and m v ] = P [m vt ≤ (p |v| -θ)m v |m v ]P (m v ), and by proposition 4.1 there is c θ < 1 with P [m vt ≤ (p |v| -θ)m v |m v ] ≤ c mv θ . Then: P (a(Y n ) ≤ n β ′ (n) ) ≤ |v|≤l(n) c (p 0 -θ)...(p l(n)-1 -θ)n θ = n β ′ (n) c (p 0 -θ)...(p l(n)-1 -θ)n θ , (6)
because there are d 0 . . . d l(n) = n β ′ (n) vertices such that |v| ≤ l(n). Compute by conditioning on activity, recalling that fact 3.7 ensures

P [ϕ n = id|a(Y n ) = a] = ( 1 #F ) a : P (Y n = id) ≤ P (ϕ n = id) = n a=0 P [ϕ n = id|a(Y n ) = a]P (a(Y n ) = a), = n a=0 1 #F a P (a(Y n ) = a).
The decay of 1 #F a with a permits to split the sum between a < n β ′ (n) and a ≥ n β ′ (n) . Obtain:

P (Y n = id) ≤ P (a(Y n ) < n β ′ (n) ) + 1 #F n β ′ (n) P (a(Y n ) ≥ n β ′ (n) ), ≤ n β ′ (n) c (p 0 -θ)...(p l(n)-1 -θ)n θ + 1 #F n β ′ (n)
, by inequality (6). Now there is a function ε(θ) -→ θ 0 such that (p 0θ) . . .

(p l(n)-1 - θ)n ≥ n β ′ (n)-ε(θ) (cf proposition 4.
2), so:

P (Y n = id) ≤ exp(-cn β ′ (n)-ε(θ) ),
which proves the lower bound.

As for theorem 5.1, the upper bound is valid for G(S, H), i.e. for F = {1}, but the lower bound is valid only with a non-trivial finite group F . Remark 6.3. Fact 6.2 shows that if the activity is small, then there is at least one edge along which the word length is contracted more than expected, with m vt ≤ (p |v|θ)m v instead of m vt = p |v| m v . In fact, in order to have a(Y n ) < n β ′ (n) , such a strong contraction must occur at many edges, so that inequality (6) does not seem optimal. The example below shows that the lower bound of theorem 6.1 is tight, and thus inequality ( 6) is essentially optimal in general. It might however be improved for particular instances of saturated directed groups. 6.2. A specific example. Consider the particular case of a binary tree and specific generators s = (1, 1)σ with σ the non-trivial permutation in S 2 and h = (h, s). The group s, h < Aut(T 2 ) is a well-known automata group isomorphic to the infinite dihedral group D ∞ = s, h|s 2 = h 2 = 1 . Proposition 6.4. A random walk Z n on the extended directed group Γ(S, HF ) = F ≀ ∂T 2 D ∞ < Aut(ET 2 ) with F abelian finite with step distribution equidistributed on SHF HS satisfies:

lim log | log P (Z n = id)| log n = 1 3 and lim log E||Z n || log n = 1 2 .
In this particular case, the lower bounds of theorem 6.1 and corollary 5.10 are tight. Note that this specific group played a crucial role in the construction of antichains of growth functions in [START_REF] Grigorchuk | Degrees of growth of finitely generated groups and the theory of invariant means[END_REF] and in the construction of groups with oscillating growth in [START_REF] Brieussel | Croissance et moyennabilité de certains groupes d'automorphismes d'un arbre enraciné[END_REF] (chapter 2).

Proof. Theorem 6.1 and corollary 5.10 ensure:

lim inf log | log P (Z n = id)| log n ≥ 1 3 and lim log E||Z n || log n ≥ 1 2 .
To get an upper bound, compare with the usual wreath product F ≀ D∞ D ∞ , for which the return probability satisfies P ( Xn = id) ≈ e -n 1 3 (theorem 3.5 in [START_REF] Pittet | On random walks on wreath products[END_REF], noting that Z and D ∞ with their usual generating sets have the same Cayley graph) and the drift L F ≀ D∞ D∞ (n) ≈ n 1 2 (by lemma 3 in [START_REF] Erschler | On the asymptotics of the rate of departure to infinity[END_REF]). Precisely, consider the usual wreath product (lamplighter):

F ≀ D∞ D ∞ = {Φ : D ∞ → F |supp(Φ) is finite} ⋊ D ∞ ,
with the action d.Φ(x) = Φ(xd). Denote S = s ≃ S 2 and H = h ≃ S 2 , so that D ∞ ≃ G(S, H) < Aut(T 2 ), and denote F the subgroup {Φ :

D ∞ → F |∀x = 1 D∞ , Φ(x) = 1 F } in F ≀ D∞ D ∞ .
Let Xn be the random walk with alternate successive increments equidistributed in the finite symmetric sets HSH and F (this is, up to negligible first and last factors, the random walk with step distribution µ equidistributed on the finite symmetric set SHF HS):

Xn = h 1 s 1 h ′ 1 f 1 h 2 s 2 h ′ 2 f 2 . . . h n s n h ′ n f n .
It induces in particular a random walk X n on the base group D ∞ given by:

X n = h 1 s 1 h ′ 1 h 2 s 2 h ′ 2 . . . h n s n h ′ n = r 1 r 2 . . . r n , with r i = h i s i h ′ i .
The value of Xn in F ≀ D∞ D ∞ is given by the value of X n in D ∞ together with a function Φ n : D ∞ → F the support of which is included in {r -1 1 , (r 1 r 2 ) -1 , . . . , (r 1 r 2 . . . r n ) -1 }, since at time i the lamp in position (r 1 r 2 . . . r i ) -1 is modified.

With obvious identification of S, H, F , denote Z n the similar random walk on F ≀ ∂T 2 G(S, H):

Z n = h 1 s 1 h ′ 1 f 1 h 2 s 2 h ′ 2 f 2 . . . h n s n h ′ n f n . The value of Z n is given by the value of X n in G(S, H) ≃ D ∞ and a function ϕ n : ∂T 2 → F with support included in {1 ∞ r -1
1 , 1 ∞ (r 1 r 2 ) -1 , . . . , 1 ∞ (r 1 r 2 . . . r n ) -1 } by proposition 3.8. Now the Schreier graph 1 ∞ G(S, H) can easily be described as a semi-line. If w is a reduced representative word in D ∞ = s, h|s 2 = h 2 = 1 then 1 ∞ hw = 1 ∞ w and 1 ∞ w = 1 ∞ w ′ if w = w ′ and both w and w ′ start with s, so there is a canonical 2-covering application c : Cay(D ∞ , {s, h}) ։ 1 ∞ G(S, H) with c(w) = c(hw). This implies:

ϕ n (x) = y∈c -1 (x) Φ n (y)
because F is abelian, so that the order of increments does not influence the sum. This shows that

if Xn = 1 in F ≀ D∞ D ∞ then Z n = 1 in F ≀ ∂T 2 G(S,

Higher order oscillations

This section aims at proving theorem 1.3 and treating the case β = 1 in theorem 1.2. The following construction is designed to obtain groups ∆(S ′ , H ′ F ′ ) that ressemble Γ(S, HF ) at some scales and non-amenable groups at other scales. They are still directed groups of a rooted tree but of unbounded valency d (in the cases of interest here) and not saturated.

The construction generalises [KP], where a group ∆(S ′ , H ′ ω ) is constructed given an Aleshin-Grigorchuk group Γ(S, H ω ) and additional data. Theorem 6.1 and corollary 5.10 permit to show that some of the groups ∆ = ∆(S ′ , H ′ ω ) or almost equivalently some of the piecewise automatic groups of [START_REF] Erschler | Piecewise automatic groups[END_REF] satisfy:

p(∆) ≤ 1 2 , p(∆) = 1 and δ(∆) ≤ 3 4 , δ(∆) = 1.
The description of the construction in [KP] is more algebraic, whereas the point of view adopted here is in terms of automorphisms of an ambiant tree T ē.

7.1. Definition of ∆(S ′ , H ′ F ′ ). Given a bounded sequence d and a saturated directed finitely generated group Γ = Γ(S, HF ) < Aut(ET d), construct a modification ∆ of this group, acting on an extended spherically homogeneous rooted tree ET ē for another sequence ē = (e l ) l∈N , with e l = d l + d ′ l for some d ′ l ≥ 0, possibly d ′ l = ∞. Note that there is a canonical inclusion ET d ⊂ ET ē, hence a canonical embedding:

Aut(ET d) ֒→ Aut(ET ē).
Corresponding to the group Γ(S, HF ), determined by the finite groups S, H, F and the portraits of their elements, i.e. their realisation in Aut(ET d), construct a new group ∆(S ′ , H ′ F ′ ) < Aut(ET ē), where S ≃ S ′ , H ≃ H ′ and F ≃ F ′ as abstract groups. Define the generators via the wreath product isomorphism of proposition 2.2.

(1) The element s ′ in S ′ corresponding to s ∈ S ≃ S ′ has the form:

s ′ = (1, . . . , 1)s ′ where s ′ is a permutation of {1, . . . , d 0 , d 0 + 1, . . . , d 0 + d ′ 0 } respecting the decomposition {1, . . . , d 0 } ⊔ {d 0 + 1, . . . , d 0 + d ′ 0 }, so that s ′ | {1,...,d 0 } = s ∈ S = S d 0 < S e 0 (canonical inclusion) and moreover s ′′ = s ′ s -1 = s ′ | {d 0 +1,...,d 0 +d ′ 0 } is chosen so that s → s ′′ is a morphism of groups from S ≃ S ′ into the permutation group S {d 0 +1,...,d 0 +d ′ 0 } ≃ S d ′ 0 . Denote S ′′ its image. (2) The element h ′ in H ′ corresponding to h = (h 1 , σ 2 , . . . , σ d 0 ) ∈ H ≃ H ′ has the form: h ′ = (h ′ 1 , σ ′ 2 , . . . , σ ′ d 0 , 1, . . . , 1)h ′′ where σ ′ 2 , . . . , σ ′ d 0 ∈ S ′ 1 are defined as above, corresponding to σ 2 , . . . , σ d 0 ∈ S 1 , h ′ 1 ∈ H ′ 1 corresponds to h 1 ∈ H 1 , and h ′′ is a permutation in S d 0 +d ′ 0 with support included in {d 0 + 1, . . . , d 0 + d ′ 0 } so that h → h ′′ is a morphism of groups with image H ′′ < S d ′ 0 .
Elements of H ′ do not act at the boundary ∂T ē.

with σ h in F ix S d 0 (1), a permutation of {1, . . . , d 0 } that fixes 1. By recursion, σ h l (1) = 1 for all l, hence h fixes the infinite ray 1 ∞ , and thus commutes with ϕ f . The group H d directed by the ray 1 ∞ is the uncountable locally finite group:

H d = AT 0 × AT 1 × . . . , where AT l = S d l+1 ≀ S d l -1 = (S d l+1 × • • • × S d l+1 d l -1 factors ) ⋊ S d l -1 .
Given another sequence c = (c l ) l of integers such that 1 ≤ c l ≤ d l -1, define the subgroup P T l by:

P T l = S d l+1 × • • • × S d l+1 c l factors ×{1} × • • • × {1} < S d l+1 ≀ S d l -1 = AT l ,
with c l factors S d l+1 when c l < d l -1, and P T l = AT l if c l = d l -1. The hypothesis of saturation of a group G(S, H) can be relaxed as relative saturation with respect to c by requiring that S = S d 0 acts transitively on {1, . . . , d 0 } and the subgroup H < H d is included in:

H < P T 0 × P T 1 × . . . , with the equidistribution measure on H projecting to equidistribution measure on each factor P T l .

Given the sequences d = (d l ) l and c = (c l ) l of integers with 1

≤ c l ≤ d l -1, define a new sequence p′ = (p ′ l ) l by p ′ l = c l (c l +1)d l . and set: β d,c (n) = log(d 0 ...d k(n) ) log n , where k(n) = k d,c (n) = min{k|p ′ 0 . . . p ′ k n ≤ 1}, β ′ d,c (n) = log(d 0 ...d l(n) ) log n , where l(n) = l d,c (n) = max{l| d 0 p ′ 0 . . . d l p ′ l ≤ n}.
With these notations, theorems 5.1 and 6.1 generalise to:

Theorem 8.1. Given bounded sequences d and c, a relatively saturated directed group Γ(S, HF ) and the measure µ of equidistribution on SHF S, one has for arbitrary ε > 0 and n large:

(1) | log H Γ,µ (n) log n -β d,c (n)| ≤ ε, (2) β d,c (n) -ε ≤ log L Γ,µ (n) log n ≤ 1+β d,c (n) 2 + ε, (3) β ′ d,c (n) -ε ≤ log log P (Yn= Γ 1) log n ≤ β d,c (n) + ε.
For constant sequences d l = d and c l = c ≤ d -1, the sequences β d,c (n) and β ′ d,c (n) have limits respectively:

β d,c = log d log( d(c+1) c ) = 1 1+ log( c+1 c ) log d , so β d,1 = 1 1+ log 2 log d , β ′ d,c = log d log( d 2 (c+1) c ) = 1 2+ log( c+1 c ) log d , so β ′ d,1 = 1 2+ log 2 log d .
Examples 8.2.

(1) In the case of constant valency d, for H = AT (d) = S d ≀ S d-1 diagonally embedded into AT 0 × AT 1 × . . . , obtain the mother group G(S d , AT (d)) of polynomial automata of degree 0 (see [AAV], [BKN]). With an extension F at the tree boundary, one has for Γ(d) = Γ(S d , AT (d)F ) < Aut(ET d ) the estimates:

h(Γ(d), µ) = β d and β ′ d ≤ p(Γ(d), µ) ≤ p(Γ(d), µ) ≤ β d .
(2) For the spinal groups G ω (q) of the article [BS] acting on a tree of constant valency q = d. With an extension F at the tree boundary, one has for Γ ω (q) = F ≀ ∂T G ω (q) the estimates:

h(Γ ω (q), µ) = β q,1 and β ′ q,1 ≤ p(Γ ω (q), µ) ≤ p(Γ ω (q), µ) ≤ β q,1 .

Proof of theorem 8.1. Notation of proposition 3.2 and lemma 4.1 becomes:

k j = (k ′ j , b j,2 , .
. . , b j,c 0 +1 , 1, . . . , 1)σ h j , and one should consider k σ j j for σ j = s 1 σ h 1 s 2 . . . s j-1 σ h j-1 s j . The sequence (σ j ) j consists of independent terms equidistributed in S d 0 . As its action is transitive on {1, . . . , d 0 }, for any fixed t, the sequence (σ j (t)) j is a sequence of independent equidistributed elements of {1, . . . , d 0 }. This ensures that Y t n is a product of n terms that are: (1) either b j,σ j (t) equidistributed in S d 1 at times j when σ j (t) ∈ {2, . . . , c 0 + 1}, (2) or k ′ j equidistributed in H 1 F at times j when σ j (t) = 1, (3) or trivial factors 1 at times j when σ j (t) ∈ {c 0 + 2, . . . , d 0 }.

The number of non-trivial terms is n t ∼ c 0 +1 d 0 n almost surely. Now merging packs of terms in the same finite group S d 1 (with probability c 0 c 0 +1 among non-trivial terms) or H 1 F (with probability 1 c 0 +1 among non-trivial terms), the length of Y t n is almost surely: for ε > 0 and n large. Theorems 5.1 and 6.1 and corollary 5.10 follow straightforwardly. Note that the condition on θ in fact 6.2 becomes p ′ iθ >

m t ∼ c 0 (c 0 + 1) 2 n t ∼
p ′ i d i .
9. Comments and questions 9.1. Analogies between growth and entropy for directed groups. Analogies between growth and entropy for directed groups are two fold.

First, there is an analogy between the computation of growth exponents (as liminf α(Γ), limsup α(Γ) or limit α(Γ) of log log b Γ (r) log r

) in [START_REF] Brieussel | Growth behaviors in the range e r α[END_REF] and the computation of entropy exponents in theorem 5.1. For entropy, the computation is based on the contraction by a factor p 0 of the word length under rewriting process of random alternate words in Γ(S, HF ). For growth in the extended Aleshin-Grigorchuk group Γ (012) ∞ = F ≀ G (012) ∞ , the computation is based on the contraction by a factor η 2 in the wreath product for reduced representative words (see [BE], and lemma 5.4 in [START_REF] Brieussel | Growth behaviors in the range e r α[END_REF]).

The contraction factor for entropy should only hold for random alternate words, whereas the contraction factor for growth has to hold for any alternate (pre-reduced) word, which heuristically explains why 1 2 = h(Γ (012) ∞ , µ) < α(Γ (012) ∞ ) ≈ 0.76. This inequality is a well-known property of Shannon entropy that H(µ) ≤ log #supp(µ) with equality for an equidistributed measure.

There is a second analogy at the level of parameter space. For a fixed bound D on the valency d, the space of saturated directed groups is D-1 n) ≤ Dg(n) is the entropy of some finitely generated group (with the approximation of theorem 5.1).

The space of extended Aleshin-Grigorchuk groups Γ ω is also parametrized by a Cantor set {0, 1, 2} N . Though the growth function for a given sequence ω is not known, Bartholdi and Erschler have shown recently in [START_REF] Bartholdi | Groups of given intermediate word growth[END_REF] that any function e g (n) with g(2n) ≤ 2g(n) ≤ g(η + n) for η + ≈ 2.46 explicit is the growth function of some group (also compare corollary 4.2 in [START_REF] Bartholdi | Groups of given intermediate word growth[END_REF] with definition of exponent sequence at section 4.2). 9.2. Comparison between growth, entropy, return probability and drift. Among finitely generated groups with symmetric finitely supported measure, it is a natural question to classify the pairs (α(Γ), α(Γ)), (h(Γ, µ), h(Γ, µ)), (p(Γ), p(Γ)) and (δ(Γ, µ), δ(Γ, µ)) in the triangle 0 ≤ α ≤ β ≤ 1. Comparing theorem 1.3 with theorem 1.2 and the main result in [START_REF] Brieussel | Growth behaviors in the range e r α[END_REF] raises the following two questions.

Question 9.1. Given a point (α, β) in the triangle 1 3 ≤ α ≤ β ≤ 1, does there exist a finitely generated group Γ the return probability exponents of which satisfy:

(p(Γ), p(Γ)) = (α, β) ? Question 9.2. Given a point (α, β) in the triangle 1 2 ≤ α ≤ β ≤ 1, does there exist a finitely generated group Γ together with a (symmetric finitely supported) measure µ, the drift exponents of which satisfy: (δ(Γ, µ), δ(Γ, µ)) = (α, β) ? One approach would be to improve theorem 6.1 by understanding how a particular choice of H affects the return probability. Another approach is by the technics developped in [KP], that could lead to strengthening of theorems 7.8 and 7.10.

Another natural question is to know if there are such pairs outside the above mentioned triangles besides the pair (0, 0), obtained by virtually nilpotent groups for growth, entropy and return probability, by finite groups for drift. By [LP], the number 1 2 is a lower bound on the drift exponent of infinite groups. It raises the: Question 9.3. Does there exist a group Γ and a measure µ such that: 0 < h(Γ, µ) < 1 2 , or 0 < p(Γ) < 1 3 , or 0 < α(Γ) < α(Γ (012) ∞ ) ≈ 0.76 ? By [CGP], groups of exponential growth have return probability exponents ≥ 1 3 . By theorem 6.1, this is also a lower bound for many groups with intermediate growth. A conjecture of Grigorchuk asserts that a finitely generated group Γ is virtually nilpotent when its growth function satisfies b Γ (r) ≤ e r 1 2 -ε . If this were the case, then p(Γ) < 1 5 would imply virtual nilpotency by [CGP]. The bound 1 2 for entropy corresponds to some simple random walk on the lamplighter group or on an extended directed Aleshin-Grigorchuk group (see remark 5.5).

Finally, one may wonder how these asymptotic quantities relate with each other. For instance entropy is bounded by logarithm of growth so h(Γ, µ) ≤ α(Γ). Also corollary 7.4 in [CGP] implies that:

α(Γ) 2 + α(Γ)
≤ p(Γ) and p(Γ) ≤ α(Γ) 2α(Γ) .

Naively, one expects groups with low growth to have low return probability exponents and vice-versa. However, taking Γ the lamplighter on Z and Γ ′ = F ≀ G ω (q) an extension of a spinal group G ω (q) of the article [BS], one has (note that theorem 6.1 in [BS] still applies with boundary extension F and see exemple 8.2 (2)):

α(Γ ′ ) < α(Γ) = 1 but 1 3 = p(Γ) < 1 2 + log 2 log q ≤ p(Γ ′ ).
This raises the: Question 9.4. For Γ finitely generated group with finitely supported symmetric measure µ, what are the possible values of the 8-tuple:

(α(Γ), α(Γ), p(Γ), p(Γ), h(Γ, µ), h(Γ, µ), δ(Γ, µ), δ(Γ, µ)) ?

  p(Γ) = lim inf log | log P (Y n = 1)| log n and p(Γ) = lim sup log | log P (Y n = 1)| log n .

2. 2 .

 2 Extended directed groups. For a fixed x, the set xT d = {x, x1, . . . , xd} has a structure of rooted tree with root x and one level {x1, . . . , xd}. The extended boundary E∂T d of the rooted tree T d is obtained by replacing each boundary point x by a short rooted tree xT d : E∂T d = {xT d |x ∈ ∂T d} = {(x; x1, . . . , xd)|x ∈ ∂T d}. Call extended tree the set ET d = T d ⊔ E∂T d. Its group of automorphisms is the group:

  Denote A d < S d the group of alternate permutations, and given a bounded sequence d of integers d ≤ d i ≤ D, define the finite subgroup A d < H d < Aut(T d) by the following:

Figure 1 .

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

  Define the sequence d by d i ∈ {d, D} for all i and #{i ≤ n|d i = d} = [λn]. Then the exponent sequence β d(n) → β and the corollary follows from theorem 5.1.

  H), hence P (Z n = 1) ≥ P ( Xn = 1) and the group F ≀ ∂T 2 G(S, H) is a quotient of F ≀ D∞ D ∞ with identification of the generators, so || Xn || ≤ ||Z n ||.

  This shows that lemma 4.1 is true with p ′ 0 = c 0 (c 0 +1)d 0 instead of p 0 = d 0

  (partially) parametrised by the Cantor set {2, . . . , D} N . The entropy exponent β d(n) is computed in theorem 5.1 in terms of the sequence d and the contraction factors (p i ) i as n β d(n) = d 0 . . . d k(n) where p 0 . . . p k(n) ≈ 1 n . By fact 4.4, any function g(n) such that dg(n) ≤ g( d 2 d-1 n) and g( D 2

  k-1 ti k+1 i k+2 . . . with t in {2, . . . , d k-1 } and k ≥ 1 integer. Notation 1 k is a shortcut for 11 . . . 1 with k terms. Definition 2.1. A group G of automorphisms of T d is called directed when it admits a generating set of the form S ∪ H where S is included in the group S d 0 of rooted automorphisms and H is included in H d. Denote G = G(S, H) such a directed group. Then G(S d 0 , H d) is the (uncountable) full directed group of T d. Say a group G(S, H) is saturated if S = S d 0 is the full group of rooted automorphism and H is a group such that the projection of the equidistribution measure over H onto each factor S d l in (4) is the equidistribution measure on S d l . The full directed group is obviously saturated. Assume the sequence d = (d i ) i is bounded taking finitely many values e 1 , . . . , e T , then the direct product H

  where the factors S et embeds diagonaly into the subproduct of factors for which d l = e t ). With the obvious identifications, the group G(S d 0 , H) is a finitely generated saturated directed group. Note that this precise group is minimal among saturated directed groups of T d.

)

  For each coordinate t, the conditionned variable Y t n |m t has precisely the law of the random alternate word Y ′ mt of length m t in S d 1 ⊔ H 1 F , i.e.

	Y t n = Y ′ mt = s t 1 k t 1 . . . k t mt s t mt+1
	where the factors s t j and k t j are equidistributed in S d 1 and H 1 F respectively
	(except s t 1 and s t mt+1 ), and all factors (s t j , k t j )

j are independent.

  m t depends only on σ 1 , . . . , σ n , i.e. on s 1 , . . . , s n , whereas the factors (s t j , k t j ) are determined by k 1 , . . . , k n . In particular, fixing σ 1 , . . . , σ n (hence m t ), and playing with k 1 , . . . , k n any alternate word Y t n of length m t in S d 1 ⊔ H 1 F appears with the same probability. The lemma can be iterated to show that for any vertex v in T d, the random product Y v n obtained by rewriting process of the random alternate word Y n is also an alternate random word in the group Γ(S d |v| , H |v| F ), of length m v ∼ p 0 . . . p |v| n almost surely, i.e. the conditioned variable Y v n |m v = Y (S d |v| , H |v| F ) of length m v . 4.2. Exponent sequence associated to valency sequence. Given a bounded sequence

	(|v|) mv	is a random alternate
	word in Γ

  where a k (w) is the activity function on the group Γ(S d k , H k F ). Thus:

	d 0
	Ea 0 (Y n ) =	Ea 1 (Y t n ).
	t=1
	Now by lemma 4.1, the conditioned variable Y t n |m t is a random alternate word Y ′ mt
	of random length m t in the group Γ(S d 1 , H 1 F ). Compute by conditioning and large
	deviation principle:

  Also recall remark 3.6 that A ∂ (Y n ) depends only on g n = s 1 h 1 . . . h n s n+1 , and fact 3.7 that given A ∂ (g n ), any function ϕ : ∂T → F with support included in A ∂ (g n )

	#F appears with probability 1	#A ∂ (gn)

Supported by Swiss NSF grant 20-126689.

(3) The element f ′ in F ′ corresponding to ϕ f ∈ F ≃ F ′ has the form:

where f ′ 1 ∈ F ′ corresponds to ϕ f ∈ Γ(S 1 , H 1 F ) and f ′′ is a permutation in S d 0 +d ′ 0 with support included in {d 0 + 1, . . . , d 0 + d ′ 0 } so that f → f ′′ is a morphism of groups with image F ′′ < S d ′ 0 . The element f ′ acts at the boundary ∂T ē by ϕ(x) = 1 F if x = 1 ∞ and ϕ(1 ∞ ) = f . (4) Any two elements f ′′ and h ′′ in S {d 0 +1,...,d 0 +d ′ 0 } commute. Note that similarly to the definition of h ∈ Aut(T d) in section 2.1, the definitions of h ′ and f ′ are recursive for they involve the generators h ′ 1 and f ′ 1 of the group ∆(S ′ 1 , H ′ 1 F ′ 1 ) < Aut(ET σē ) associated to the saturated directed group Γ(S 1 , H 1 F ) < Aut(ET ē).

Condition (4) implies by recursion that at any level l the elements h ′′ l and f ′′ l in S {d l +1,...,d l +d ′ l } commute, which implies that the subgroup {s ′′ l }, {h ′′ l }, {f ′′ l } < S d ′ l is a quotient of the free product of finite groups S ′ l * (H ′ l × F ′ l ) ≃ S l * (H l × F ), possibly an infinite quotient in the case d ′ l = ∞. Denote S ′′ l = {s ′′ l }, H ′′ l = {h ′′ l }, F ′′ l = {f ′′ l }. They are subgroups of S {d l +1,...,d l +d ′ l } . By recursion, the action of the generators s ′ , h ′ , f ′ is well defined on the whole tree T ē. Moreover, only generators f ′ act non trivially at the boundary ∂T ē, thus the action of s ′ , h ′ , f ′ on ET ē is well defined.

To summarise, the group ∆(S ′ , H ′ F ′ ) is defined by Γ(S, HF ) and a collection of groups S ′′ l , H ′′ l F ′′ l < S d ′ l that are quotients of the free products of finite groups S l * H l F by identification of generators.

Elementary properties of

Properties 7.1.

(1) The canonical isomorphism of proposition 2.2 induces a canonical embedding:

. By recursion, this shows that [h ′ , f ′ ] has a trivial action on T ē. Moreover, the support of the corresponding function

For (3), observe that all the permutations involved in the description of S ′ , H ′ , F ′ respect the decomposition {1, . . . , d l } ⊔ {d l + 1, . . . , d l + d ′ l } for all l ∈ N, so that the subset ET d ⊂ ET ē is stable under the action of ∆(S ′ , H ′ , F ′ ). The quotient action is precisely given by Γ(S, HF ).

Observe that if d l = 0 for all l ≥ 1 then ∆(S ′ , H ′ F ′ ) ≃ Γ(S, HF ) × S ′′ , H ′′ F ′′ . In particular, if d ′ l = 0 for all l ∈ N then ∆(S ′ , H ′ F ′ ) = Γ(S, HF ). A word w(S, HF ) is an ordered product of generators s in S, h in H and ϕ f in F of the group Γ. By replacing s by s ′ , h by h ′ and ϕ f by f ′ , one naturally obtains a word w(S ′ , H ′ F ′ ) in the generators of ∆. The rewriting process of proposition 3.2 applies to the groups ∆(S ′ , H ′ F ′ ). More precisely: Proposition 7.2 (Rewriting process for groups ∆(S ′ , H ′ F ′ )). If the rewriting process in the group Γ ֒→ Γ 1 ≀ S d 0 provides:

then the rewriting process in the group ∆ ֒→ ∆ 1 ≀ S ′ provides:

, where s → s ′ , h → h ′ and ϕ f → f ′ are given in the definition of generators of ∆. These forms are equivalent to:

For

with h 1 ϕ f in position σ(1).

Correspondingly, for h

acts trivially on {1, . . . , d 0 }, one can compute products (words) componentwise, which proves the proposition.

Remark 7.3. Proposition 7.2 shows in particular that the minimal tree description of section 3.2 and figure 1 for a word w(S, HF ) in Γ(S, HF ) remains valid for the word w

7.3. Localisation. A ball of given radius in the Cayley graph of ∆(S ′ , H ′ F ′ ) depends only on the description of the action on a neighbourhood of the root of the tree.

Proposition 7.4. The ball

Proof. The ball B ∆ (R) can be drawn if one can test (algorithmically) the oracle w = ∆ 1 for any given word w in S ′ ⊔ H ′ F ′ of length ≤ r = 2R + 1. To test such an oracle, use the following algorithm.

First test the permutation value of w at the root Φ(w(s ′ , h ′ f ′ )) = w(s ′ , h ′′ f ′′ ) = Se 0 1 Se 0 , where Φ : Aut(ET ē) → S e 0 is the root evaluation. This test depends only on the zero level in ∆(S ′ , H ′ F ′ ) and the |w|-ball in

then w fixes all vertices in the first level of T ē. By propositions 3.2 and 7.2 of rewriting process, one has w = (w 1 , . . . , w d 0 , 1, . . . , 1) in the wreath product with

2 . Test for each t in {1, . . . , e 0 }, the permutation value at the root Φ(w

for all t, then w fixes all vertices in the two first levels of T ē. By propositions 3.2 and 7.2 of rewriting process, w t = (w t1 , . . . , w te 0 , 1, . . . , 1) in the wreath product with |w ts | ≤ |w t |+1 2 < r 4 + 1. Continue the process and test the value at the root of the words w t 1 ...t l while their length is ≥ 1. This test depends only on the l first levels in ∆(S ′ , H ′ F ′ ) and the

The algorithm allows to test the oracle w = ∆ 1 using only the data in the L = log 2 R first levels of ∆(S ′ , H ′ F ′ ) and the r 2 l -ball in the group

In particular, for the random walks Y n in Γ(S, HF ) of law µ equidistributed on SHF S and Y ′ n in ∆(S ′ , H ′ F ′ ) of law µ ′ equidistributed on S ′ H ′ F ′ S ′ , there exists C, K > 0 such that for all n:

(1)

Proof. An element δ in the kernel ker f = {δ ∈ ∆|δ| ET d = 1} is described by its action on ET ē\ET d. By rewriting process, δ = (δ 1 , . . . , δ d 0 , 1, . . . , 1)δ ′′ with δ ′′ ∈ S d 0 +1,...,d 0 +d ′ 0 < S e 0 , for which there are ≤ # S ′′ , H ′′ F ′′ choices. To describe δ, there remains to describe δ 1 , . . . , δ d 0 that belong to the kernel ker(f 1 : ∆ 1 → Γ 1 ).

For each t ∈ {1, . . . , d 0 }, the element δ t has the form δ t = (δ t1 , . . . , δ td 1 , 1, . . . , 1)δ ′′ t with δ ′′ t ∈ S d 1 +1,...,d 1 +d ′ 1 < S e 1 , for which there are ≤ # S ′′ 1 , H ′′ 1 F ′′ 1 choices. By induction, the element δ ∈ ker f is described by:

For γ = 1, this guarantees (1):

One also has ||δ|| ≤ ||f (δ)|| + K for K = max{||δ 1 ||, . . . , ||δ C ||}. Indeed, if w(S, HF ) = γ = f (δ), then w(S ′ , H ′ F ′ ) = δδ i for some i and when

Now fix n, and define for any γ in Γ the measure with support in f -1 (γ) ⊂ ∆:

Then the measure µ ′ * n decomposes as:

and by lemma A.4 in [BKN] on conditionnal entropy:

The support of ν γ has size ≤ C so H(ν γ ) ≤ log C, which shows (3):

In particular, for the random walk Y n of law µ equidistributed on the finite generating set S ′ H ′ F ′ S ′ , there exists c > 0 such that for n large enough:

The proof will use the following: Fact 7.7. Given γ 1 ∈ ∆ 1 , there exists γ ∈ ∆ such that γ = (γ 1 , γ 2 , . . . , γ e 0 )id S ′ for some γ 2 , . . . , γ e 0 in ∆ 1 .

Note that this fact implies that ∆ is infinite, for it contains γs for all s in S ′ and then

. . . This is in particular an elementary proof that directed saturated groups are infinite.

Proof of fact 7.7. Let γ 1 = x 1 . . . x r be a representative word in S ′ 1 ⊔ H ′ 1 F ′ . By saturation of H, there exists for each x i , an element h ′ i in H ′ such that h ′ i = ( * , . . . , x i , . . . , * ) (where * marks some unknown value) with x i in position 1 if x i ∈ H ′ 1 F ′ and x i in some position between 2 and d 0 if x i ∈ S ′ 1 . Now by saturation of Γ, S = S d 0 so S ′ acts transitively on {1, . . . , d 0 }, and there exists s i ∈ S ′ such that y i = s i h i s -1 i = (x i , * , . . . , * ). Then γ = y 1 . . . y r = (x 1 . . . x r , * , . . . , * ) = (γ 1 , γ 2 , . . . , γ e 0 ). (Note that in fact

Proof of proposition 7.6. The fact shows that the composition

is surjective, so that if ∆ 1 is non-amenable, so is St 1 (∆) which is a subgroup of ∆, and thus ∆ is non amenable. Iterating the process shows that if ∆ l is non-amenable, so is ∆. Consequence (1) follows by Kesten theorem [Kes], ( 2) and ( 3) by a theorem of Kaimanovich-Vershik [KV]. 7.5. High order oscillations. The following theorems are similar to theorem 7.1 in [START_REF] Brieussel | Growth behaviors in the range e r α[END_REF] on oscillation of growth functions (see also chapter 2 in [START_REF] Brieussel | Croissance et moyennabilité de certains groupes d'automorphismes d'un arbre enraciné[END_REF] and [KP]). The entropy function of the groups ∆ involved is not precisely evaluated, but only some (rare) values of the function. The idea is to use alternatingly localisation and asymptotic evaluation to obtain a group with low entropy at some scales and high entropy at other scales.

Theorem 7.8. Let Γ(S, HF ) < Aut(ET d) be a saturated directed group with measure µ equidistributed on SHF S.

Then there exists a group ∆(S ′ , H ′ F ′ ) < Aut(ET ē) such that the entropy for the measure µ ′ equidistributed on S ′ H ′ F ′ S ′ satisfies:

Corollary 7.9. For any 1 2 ≤ α ≤ 1, there exists a finitely generated group ∆ and a finitely supported symmetric measure µ ′ such that:

Corollaries 5.4, 5.6 and 7.9 imply theorem 1.2.

Proof of corollary 7.9. If α = 1, take ∆ any non-amenable group. If α < 1, apply theorem 7.8 with h(Γ, µ) = α (exists by corollary 5.4),

Proof of theorem 7.8. The first condition is trivially satisfied since Γ(S, HF ) is a quotient of ∆(S ′ , H ′ F ′ ).

Construct the group ∆(S

is a big finite quotient of the free product S ′′ l i * H ′′ l i F ′′ l i . Roughly, as (l i ) is rapidly increasing, there are scales at which an observer has the impression that ∆(S ′ , H ′ F ′ ) resembles the group Γ(S, HF ) and has low asymptotic. As d ′ l i is big, there are scales at which an observer has the impression that ∆(S ′ , H ′ F ′ ) contains a free group and has high asymptotic.

More precisely, assume by induction that parameters l j , d ′ l j and integers m j-1 ≤ n j ≤ m j are constructed for j < i together with an integer k i-1 = 1+ log 2 r i-1 ≥ l i-1 such that {H(m)|m ≤ m i-1 } depends only on B(r i-1 ). By localisation 7.4, this ball hence the values of the m i-1 first values of the entropy function depend uniquely on l, d ′ l and the groups

The group ∆ i (Γ ′ , H ′ F ′ ) where d ′ l = 0 for all l ≥ k i has low asymptotic by proposition 7.5, so:

for some C, and in particular, there exists n i such that:

By localisation 7.4 this value of entropy depends only on a ball of radius R i in the Cayley graph of ∆ i (Γ ′ , H ′ F ′ ) which depends only on the

as above for l ≤ l i -1 and fix (momentarily) d ′ l i = ∞, with: andd ′ l = 0 for l > l i . The group ∆ i (S ′ , H ′ F ′ ) is non-amenable by proposition 7.6 of high asymptotic, so:

for some c > 0 and in particular, there exists m i such that:

Now by localisation 7.4, the m i first values of the entropy function depend only on a ball of radius r i in the Cayley graph of ∆ i (S ′ , H ′ F ′ ), which depends only on the k i = 1 + log 2 r i first levels, and the balls of radius 2r

In particular, the values {H(m)|m ≤ m i } are the same if S ′′ l i , H ′′ l i F ′′ l i is any group coinciding with the free product S ′′ l i * H ′′ l i F ′′ l i ≃ S l * H l F in a ball of radius 2r i + 1. As a free product of finite groups is residually finite, there exists such a group which is finite of size d ′ l i . The parameters l i , d ′ l i , k i ≥ l i , the finite groups S ′′ l , H ′′ l F ′′ l < S d ′ l for l ≤ k i and the integers n i , m i are now constructed for all i by induction.

The sequence (d ′ l i ) i of positive integers and the finite groups

for all i, because the balls of radius r i in ∆ and in ∆ i coincide.

In the point of view of information theory of remark 5.3, the minimal tree description remains valid. However, the number of digits needed to describe σ u is not anymore bounded independently of the level l, for now d l i → ∞, which explains the higher values taken by the entropy.

Theorem 7.10. Let Γ(S, HF ) < Aut(ET d) be a saturated directed group with random walk Y n of law µ equidistributed on SHF S. Let p 1 (n), p 2 (n) be functions such that p 1 (n) P (Yn= Γ 1) → 0 and that for any c > 0 and n large, p 2 (n) ≥ e -cn . Then there exists a group ∆(S ′ , H ′ F ′ ) < Aut(ET ē) such that the return probability for the random walk Y ′ n with law µ ′ equidistributed on S ′ H ′ F ′ S ′ satisfies: (1) P (Y n = Γ 1) ≥ P (Y ′ n = ∆ 1) ≥ e -Cn for all n and a constant C, (2) P (Y ′ n i = ∆ 1) ≥ p 1 (n i ) for an infinite sequence (n i ), (3) P (Y ′ n i = ∆ 1) ≤ p 2 (m i ) for an infinite sequence (m i ). Theorem 7.11. Let Γ(S, HF ) < Aut(ET d) be a saturated directed group with measure µ equidistributed on SHF S.

Then there exists a group ∆(S ′ , H ′ F ′ ) < Aut(ET ē) such that the drift for the measure µ ′ equidistributed on S ′ H ′ F ′ S ′ satisfies:

(1) L Γ,µ (n) ≤ L ∆,µ ′ (n) ≤ Cn for all n and a constant C, (2) L ∆,µ ′ (n i ) ≤ L 1 (n i ) for an infinite sequence (n i ), (3) L ∆,µ ′ (m i ) ≥ L 2 (m i ) for an infinite sequence (m i ).

Proof. The proof of theorem 7.8 applies to theorems 7.10 and 7.11, with (a priori) different choices of parameters l i , d ′ l i and integers n i , m i , obtained by replacing inequality ( 7) by (proposition 7.5 of low asymptotic):

for n large enough, which permits to find n i , and replacing inequality ( 8) by (proposition 7.6 of high asymptotic):

for m large enough, which permits to find m i .

Corollary 7.12. [theorem 1.3] There exists a finitely generated group ∆ and a finite symmetric measure µ ′ such that the return probability of the random walk Y ′ n of law µ ′ satisfies: p(∆) = 1 3 , p(∆) = 1 and δ(∆, µ ′ ) = 1 2 , δ(∆, µ ′ ) = 1.

Proof. Take Γ(S, HF ) = F ≀ ∂T 2 D ∞ < Aut(ET 2 ) to be the directed saturated group of proposition 6.4, for which e -n

Generalisation

The definition of a saturated directed group Γ(S, HF ) acting on an extended tree ET d for a bounded sequence d can be slightly generalised, with adaptation of theorems 5.1 and 6.1.

By S d denote a finite group acting faithfully and transitively on {1, . . . , d} (not necessarily the full group of permutation). Replace definition (3) in section 2.1 by: h = (h 1 , σ 2 , . . . , σ d 0 )σ h ,