J Ér

Émie Brieussel

FOLNER SETS OF ALTERNATE DIRECTED GROUPS

Folner sets of alternate directed groups

Jeremie Brieussel

Introduction

By a criterion of Folner [Fol], amenable groups are those that admit finite subsets with arbitrary small boundaries. A sequence of such subsets, called a Folner sequence, is easily described for abelian groups, and well-understood for solvable groups ( [PSC], [Ers]). Many non-solvable amenable groups are directed groups acting on rooted trees. This family of groups gathers many examples with "exotic" properties, such as infinite torsion groups constructed by Aleshin [Ale], groups of intermediate growth by Grigorchuk [Gri] or groups with non-uniform exponential growth by Wilson [Wil1].

Their amenability in the case of bounded valency was shown in [START_REF] Brieussel | Amenability and non-uniform growth of some directed automorphism groups of a rooted tree[END_REF] by use of Kesten's probabilistic criterion [Kes]. The strategy, introduced by Bartholdi and Virag in [BV], is to show that a self-similar random walk on a Cayley graph di↵uses slowly, in the sense that its return probability does not decay exponentially, or that its entropy is sublinear ( [KV]). The same method permits to show that automata groups are amenable when their activity is bounded [BKN] or linear [AAV]. Though it ensures their existence, such a probabilistic proof does not exhibit Folner sets.

For the groups of [Ale] and [Gri], subexponential growth easily implies the existence of a subsequence of the family of balls (for a word length) which is a Folner sequence, but it is not known if the whole sequence of balls is Folner and the subsequence (even though it has density 1) is not explicit. Even for groups of polynomial growth, it is not elementary to show that balls form a Folner sequence, a result due to Pansu [Pan], using technics from Gromov [Gro].

The object of the present article is to exhibit explicit Folner sets for some groups in a class denoted DP, containing in particular directed groups acting on a rooted tree by alternate permutations. A group in this class DP is defined (see section 4) by two subgroups A finite and H finitely generated, together with an action on a rooted tree with valency sequence (d k ) k2N . The main result is: Theorem 1.1. Let belong to the class DP with H amenable and d k log k ! 0, then the group is amenable.

As a corollary, this provides a new proof, using neither random walks nor word length, that directed groups acting on a rooted tree of bounded valency are amenable [START_REF] Brieussel | Amenability and non-uniform growth of some directed automorphism groups of a rooted tree[END_REF]). It also provides many new examples of amenable directed groups acting on a tree of unbounded sublogarithmic valency. Moreover it also permits to reprove amenability of automata groups with bounded activity by methods di↵erent from [BKN].

The article is structured as follows. Rooted trees and their automorphism groups are described in section 2. Section 3 is devoted to the construction of explicit Folner sets for the archetypal example of the alternate mother group G d acting on a regular rooted tree of valency d 5. This example, treated first for simplicity of notations, is generalized to the class DP in section 4. Finally, section 5 is devoted to the construction of groups in the class DP, including the saturated alternate directed groups, and some groups acting on trees with unbounded valency.

Rooted trees and their groups of automorphisms

Let S d denote the group of permutations of the set {1, . . . , d} with d elements, and A d = A {1,...,d} denote the subgroup of alternate permutations.

Aut(T d) ' Aut(T d) o S d 0 , (1)
where d = (d k ) k 1 is the shifted sequence obtained by deleting the first entry, and

G o S d = (G ⇥ • • • ⇥ G) o S d
is the semi-direct product where S d acts by permuting factors, called wreath product. Write g = (g 1 , . . . , g d 0 ) = (g t 0 ) the identification by isomorphism (1). The product rule is gg 0 = (g 1 g 0 (1) , . . . , g d 0 g 0 (d 0 ) ) 0 . By iterating the wreath product ismorphism (1), a family of isomorphisms is obtained:

Aut(T d) ' Aut(T k d) o S d k 1 o • • • o S d 0 . Identifications are denoted g = (g t 0 ...t k )( t 0 ...t k 1 ) . . . ( t 0 )
, where ( t 0 ...t j ) is a sequence of permutations in S d j indexed by the j + 1st level of the tree and (g t 0 ...t k ) is a sequence of automorphisms of T k d indexed by level k + 1. The automorphism g is determined by the whole sequence of permutations ( v ) v2T d , called its portrait.

The automorphism g is said to be alternate if all the permutations v of its portrait are alternate permutations. Denote Aut alt (T d) the group of alternate automorphisms of T d. It also satisfies isomorphisms:

Aut alt (T d) ' Aut alt (T k d) o A d k 1 o • • • o A d 0 .
The neutral element of a group G is denoted e G or e. (1) Given in

3.

A d , denote A = {a( )| 2 A d } ' A d with:
a( ) = (e, . . . , e) .

Elements of

A are called rooted. (2) Given a 2 , . . . , a d in A = A d and ⇢ in F ix A d (1) = A {2,...,d} = A d 1 , set: b(a 2 , . . . , a d , ⇢) = (b(a 2 , . . . , a d , ⇢), a 2 , . . . , a d )⇢. Denote B = {b(a 2 , . . . , a d , ⇢)|a 2 , . . . , a d 2 A d , ⇢ 2 F ix A d (1)}.
Elements of B are called directed. The set B forms a finite subgroup of Aut(T d ). Indeed, the following is an isomorphism:

B ! (A d ⇥ • • • ⇥ A d ) o A {2,...,d} b(a 2 , . . . , a d , ⇢) 7 ! (a 2 , . . . , a d )⇢. . (2)
Define the group generated by the sets A, B:

G d = hA, Bi < Aut(T d ).
By construction, the group G d is an automata group. It is essentially the mother group of degree 0 (see [BKN], [AAV]), but the permutations involved are alternate.

Since A d is simple hence perfect for d 5, the group G d satisfies the:

Proposition 3.1. If d 5, the group G d is isomorphic to its wreath product with A d : G d ' G d o A d = (G d ⇥ • • • ⇥ G d ) o A d .
The proposition follows from the: Recall the conjugacy notation g a = aga 1 , and observe that for g = (g 1 , . . . , g d ) and a in A, one has g a = (g a(1) , . . . , g a(d) ) a .

Proof of fact 3.2. Take ⌧ in A d such that ⌧ (1) = 1 and ⌧ 1 (2) = 3 and observe the commutator relations:

b = b(↵ 2 , e G , . . . , e G , e A ) = (b, ↵ 2 , e G , e G , . . . , e G )e A , b 0⌧ = b(↵ 0 2 , e G , . . . , e G , e A ) ⌧ = (b 0 , 1, ↵ 0 2 , e G , . . . , e G )e A , [b, b 0⌧ ] = ([b, b 0 ], e G ,
) ⌧ = (a 2 , e G , . . . , e G ) for ⌧ in A = A d such that ⌧ 1 (2) = 1. ⇤ Proof of proposition 3.1. By definition, G d admits an embedding into the wreath product G d ,! G d o A d . The key point is that this embedding is surjective. Clearly A ' A d is the set of rooted automorphisms. Moreover, fact 3.2 shows that G d ⇥ {1} ⇥ • • • ⇥ {1} is in G d . As A d acts transitively on {1, . . . , d}, conjugation shows that {1} ⇥ • • • ⇥ G d ⇥ • • • ⇥ {1} also belongs to G d for any position of the non-trivial factor. Then G d ⇥ • • • ⇥ G d belongs to G d by product.
This proves the wreath product isomorphism. ⇤ 3.2. Definition of Folner sets. For a group with finite generating set S, the boundary of a subset L ⇢ is defined as:

@L = { 2 L|9s 2 S, s / 2 L}. The interior of L is the set Int(L) = L \ @L. A sequence L k of subsets of is a Folner sequence if |@L k | |L k | ! 0.
By [Fol], a finitely generated group is amenable if and only if it admits a Folner sequence for some (equivalently for any) finite generating set S.

Let us define a sequence of subsets of G d as follows:

L 0 = {g 2 G d |9 2 B, ↵ 2 , . . . , ↵ d , 2 A, g = ( , ↵ 2 , . . . , ↵ d ) }.

By induction on k, define:

L k+1 = {g = (g 1 , . . . , g d ) |8t, g t 2 L k and 9T, g T 2 Int(L k )}. By proposition 3.1, the sets L k are included in G d for d
5, and not just in the automorphism group Aut(T d ).

Theorem 3.3. For d 5, the sets L k form a Folner sequence for G d . In particular, the group G d is amenable.

The group G d was known to be amenable by [START_REF] Brieussel | Amenability and non-uniform growth of some directed automorphism groups of a rooted tree[END_REF] (use of Kesten criterion on return probability) or [BKN] (triviality of the Poisson boundary). However, these proofs, based on contraction in the wreath product of word length for some random walks, did not provide explicit Folner sets. The following proof uses neither random walks, nor word length.

3.3. Proof of theorem 3.3. Observe that for any a in A and g

= ( , ↵ 2 , . . . , ↵ d ) in L 0 , the element ga = ( , ↵ 2 , . . . , ↵ d ) a still belongs to L 0 . Moreover, for any b = b(a 2 , . . . , a d , ⇢) = (b, a 2 , . . . , a d )⇢ in B, one has: gb = ⇢ ( b, ↵ 2 a (2) , . . . , ↵ d a (d) ) ⇢ if 1 (1) = 1, ( a (1) , ↵ 2 a (2) , . . . , ↵ 1 (1) b, . . . , ↵ d a (d) ) ⇢ if 1 (1) 6 = 1.
As the sets A and B are finite groups, this shows equivalence of ( 1), ( 2) and (3) in the:

Fact 3.4. The following are equivalent:

(1) g belongs to Int(L 0 ), (2) gb 2 L 0 for all b 2 B, (3) 1 (1) = 1, (4) gb 2 Int(L 0 ) for all b 2 B.
In particular, |Int(L 0 )|

|L 0 | = 1 d , hence 0 = |@L 0 | |L 0 | = 1 1 d .
Proof. Point ( 4) is equivalent to (3) due to the fixed point assumption ⇢(1) = 1 in the definition of B, which guarantees that ( ⇢)

1 (1) = (⇢ 1 1 )(1) = 1 (⇢ 1 (1)) = 1 when 1 (1) = 1.
The evaluation of 0 is done by counting |L 0 | = |B||A| d as g is described by , ↵ 2 , . . . , ↵ d , , and condition 1 (1) = 1 occurs with probability 1 d . ⇤

Lemma 3.5. The following are equivalent:

(1)

g belongs to Int(L k ), (2) gb 2 L k for all b 2 B, (3) 1 (1) 2 I(g) = {T |g T 2 Int(L k 1 )}, (4) gb 2 Int(L k ) for all b 2 B.
Proof of lemma 3.5. The case k = 0 is treated by fact 3.4 with convention that

I(g) = {1} if g 2 L 0 .
Assume by induction that the result is true for k 1, and prove it for k.

Again ga = (g 1 , . . . , g d ) a belongs to L k for any value of a in A, g in L k . Moreover: gb = (g 1 a (1) , . . . , g 1 (1) b, . . . , g d a (d) ) ⇢. Suppose (3) that g 1

(1) 2 Int(L k 1 ), then as (1) implies (4) for k 1, the element g 1

(1) b belongs to Int(L k 1 ) for any b in B, so that gb belongs to L k for any b in B, proving (2). Then (1) follows because ga also belongs to L k for a in A, hence g is an interior point of L k .

Suppose (3) does not hold, so g 1 (1) 2 @L k 1 . By equivalence of ( 1) and (2) for k 1, there exists b in B such that g 1

(1) b / 2 L k 1 , so that gb is not in L k , disclaiming (1) and (2) for g. This proves equivalence of (1), ( 2) and (3) for k. Now gb belongs to Int(L k ) if and only if ( ⇢) 1 (1) 2 I(g) by equivalence of ( 1) and (3). But ( ⇢) 3) implies (4). Obviously, (4) implies (2), closing step k of induction. ⇤

1 (1) = 1 (⇢ 1 (1)) = 1 (1) because ⇢(1) = 1. So (
There remains to evaluate the sizes of the interior and boundary of L k . Set:

k = |@L k | |L k | , 1 k = |Int(L k )| |L k | .
Lemma 3.6. The sequence ( k ) satisfies:

1 k+1 = 1 k 1 d k
.

Proof of lemma 3.6. Given a subset I ⇢ {1, . . . , d}, denote:

J I = {g = (g 1 , . . . , g d ) |8T 2 I, g T 2 Int(L k ) and 8t / 2 I, g t 2 @L k }. By definition, L k+1 is the disjoint union L k+1 = t |I| 1 J I .
For i = |I|, the size of J I and its intersection with Int(L k+1 ) are evaluated as:

|J I | = |A d ||Int(L k )| i |@L k | d i = |A d ||L k | d (1 k ) i d i k , |J I \ Int(L k+1 )| = |I| d |A d ||Int(L k )| i |@L k | d i = i d |J I |
, where the factor i d comes from (3) of lemma 3.5. Denote C i d the number of subsets of size i in {1, . . . , d}, and use the mean of binomial distribution to get:

|Int(L k+1 )| = d X i=1 C i d (1 k ) i d i k i d |L k | d |A d | = (1 k )|L k | d |A d |, |L k+1 | = d X i=1 C i d (1 k ) i d i k |L k | d |A d | = (1 d k )|L k | d |A d |.
This shows that:

1 k+1 = |Int(L k+1 )| |L k+1 | = 1 k 1 d k
.

⇤

Proof of theorem 3.3. As k > 0, lemma 3.6 implies 1 k+1 > 1 k , so the sequence ( k ) is decreasing, tending to a limit satisfying 1 = 1 1 d , hence is 0 (or 1, ruled out by 0 < 1). ⇤ More precisely, lemma 3.6 implies that for any ⌘ < 1 d 1 , one has k = O(k ⌘ ), as shown below in lemma 4.12. On the other hand:

|L k | = |B| d k |A| (d 1)d k +(d k +•••+d+1) 2 2 k .
Remark

) = {T k 1 | 1 t 0 ...t k 2 T k 1 (1) = 1} is non-empty. (3) 83  l  k + 1, 8t 0 . . . t k l , the set I(t 0 . . . t k l ) = {T k l+1 | 1 t 1 ...t k l T k l+1 (1) 2 I(t 1 . . . t k l T k l+1
)}, defined by induction on l, is non-empty (for l = k + 1, consider I(;) where ; is the root vertex of T d ).

The element g belongs to Int(L k ) if and only if it satisfies (1), ( 2), (3) and moreover: ( 4)

1 (1) 2 I(;) = {T | T 2 I(T )}.
= hA 0 [ B 0 i), (2
) there is a group 1 in the class DP with an isomorphism: To ease notations, write g instead of ' K (g). For ⌦ ⇢ H K+1 , set:

' 0 : 0 ! 1 o A 0 = ( 1 ⇥ • • • ⇥ 1 ) o A 0 ,
L K 0 (⌦) = {g 2 K |9h 2 ⌦, ↵ 2 , . . . , ↵ d K 2 A K+1 , 2 A K , g = (h, ↵ 2 , . . . , ↵ d K ) }, ◆L K 0 (⌦) = {g 2 L K 0 (⌦)| 1 (1) = 1}
, and by induction for 1  k  K, set:

L K k (⌦) = {g = (g 1 , . . . , g d K k ) 2 K k |8t, g t 2 L K k 1 (⌦), 9T, g T 2 ◆L K k 1 (⌦)}, ◆L K k (⌦) = {g 2 L K k (⌦)|g 1 (1) 2 ◆L K k 1 (⌦)}. The sets ◆L K k (⌦) should be considered as "combinatorial interiors" of L K k (⌦)
. They satisfy a combinatorial description as remark 3.7, but slightly di↵er from the actual interior of L K k (⌦), unless the set ⌦ has empty boundary (see remark 4.9 below). Fact 3.4 generalizes as:

Fact 4.6. The three following are equivalent:

(1) g 2 Int(L K 0 (⌦)), (2) gb K 2 L K 0 (⌦) for all b K 2 B K , (3) 1 (1) = 1 and h 2 Int(⌦) ⇢ ⌦ ⇢ H K+1 .
Moreover they also imply:

(4) gb K 2 ◆L K 0 (⌦) for all b K 2 B K .
In particular,

|Int(L K 0 (⌦))| |L K 0 (⌦)| = |Int(⌦)| d K |⌦| , and K 0 (⌦) = |@L K 0 (⌦)| |L K 0 (⌦)| = 1 |Int(⌦)| d K |⌦| . Proof. Let g = (h, ↵ 2 , . . . , ↵ d K ) belong to L K 0 (⌦)
. By (2)(a) of definition 4.1 for A K , the element ga K still belongs to L K 0 (⌦) for a K in A K . This proves equivalence of (1) and (2).

Now take b

K = (b K+1 , a 2 , . . . , a d K )⇢ in B K , then: gb K = ⇢ (hb K+1 , ↵ 2 a (2) , . . . , ↵ d a (d) ) ⇢ if 1 (1) = 1, (ha (1) , ↵ 2 a (2) , . . . , ↵ 1 (1) b K+1 , . . . , ↵ d a (d) ) ⇢ if 1 (1) 6 = 1
. This shows that gb K belongs to L K 0 (⌦) for all b K if and only if 1 (1) = 1 and h belongs to Int(⌦), i.e. equivalence of (2) and (3). This implies (4) because then ( ⇢) 1 (1) = 1. Computing the sizes follows from (3). ⇤ Notation 4.7. Let g = (g 1 , . . . , g d i ) = (g t i ) in i , with in A i , g t i in i+1 for t i 2 {1, . . . , d i } by identification of g with ' i (g). More generally, identify g t i ...t j with ' j+1 (g t i ...t j ) for i  j  K and denote:

g = (g t i ...t K )( t i ...t K 1 ) . . . ( t i ) ,
where t i ...t j belongs to A j+1 and g t i ...t K to K . Set ⌧ i = 1 (1) 2 {1, . . . , d i }, and by induction ⌧ j+1 = ( ⌧ i ...⌧ j ) 1 (1) 2 {1, . . . , d j+1 }, which guarantees g(⌧ i ⌧ i+1 . . . ⌧ j ) = 11 . . . 1 for the action on the tree of fact 4.2.

The following generalizes lemma 3.5.

Lemma 4.8. For 0  k  K, the three following are equivalent:

(1) g 2 Int(L K k (⌦)), (2) gb K k 2 L K k (⌦) for all b K k 2 B K k , (3) g 2 ◆L K k (⌦) (i.e. 1 (1) 2 I(g) = {T |g T 2 ◆L K k 1 (⌦)}) and g ⌧ K k ...⌧ K 2 Int(⌦).
Moreover, they also imply:

(4) gb K k 2 ◆L K k (⌦) for all b K k 2 B K k . Observe that if g 2 ◆L K k (⌦), then g ⌧ K k ...⌧ K 2 ⌦, by definitions of ◆L K k (⌦) and ⌧ K k . . . ⌧ K . Proof. Let g = (g 1 , . . . , g d K k ) belong to L K k (⌦). For a in A K k , ga still belongs to L K k (⌦) (no condition on ).
Thus ( 1) is equivalent to (2). To prove equivalence with (3) and implication of (4), proceed by induction on 0  k  K. The case k = 0 was treated as fact 4.6 (where h = g 1 = g 1 (1) = g ⌧ K ), now assume the lemma is known for k 1.

For b K k = (b K k+1 , a 2 , . . . , a d K k )⇢, one has: gb K k = (g 1 a (1) , . . . , g 1 (1) b K k+1 , . . . , g d K k a (d K k ) ) ⇢. Assume (2) for g, then g 1 (1) b K k+1 2 L K k 1 (⌦) for all b K k+1 2 B K k+1
, which means (2) for k 1 applied to g 1

(1) . By induction hypothesis, g 1 (1) satisfies (3), which means that it belongs to ◆L K k 1 (⌦), so g 2 ◆L K k (⌦), and

g 1 (1)⌧ K k+1 ...⌧ K = g ⌧ K k ⌧ K k+1 ...⌧ K 2 Int(⌦), proving (3) for g.
Moreover, (2) applied to g 1

(1) implies, by induction, (4) that g

1 (1) b K k+1 2 ◆L K k 1 (⌦) for all b K k+1 2 B K k+1 . As ( ⇢) 1 (1) = 1 (⇢ 1 (1)) = 1 (1), this shows gb K k 2 ◆L K K k (⌦)
, which is (4) for g. Conversely, assume (3) for g, then g 1

(1) 2 ◆L K k 1 (⌦), and

g ⌧ K k ⌧ K k+1 ...⌧ K = g 1 (1)⌧ K k+1 ...⌧ K 2 Int(⌦), i.e. (3) for g 1 (1) . As (3) implies (4) for k 1, one has g 1 (1) b K k+1 2 ◆L K k 1 (⌦) for all b K k+1 2 B K k+1 , so gb K k 2 L K k (⌦) for all b K k 2 B K k , which means (2) for g. ⇤
Remark 4.9. The combinatorial description of remark 3.7 still applies to an element g 2 K k of the form:

g = (g t K k ...t K )( t K k ...t K 1 ) . . . ( t K k ) , with t K k+l 2 {1, . . . , d K k+l }, t K k ...t K k+l 2 A K k+l+1 and g t K k ...t K 2 K+1
. Such an element g belongs to L K k (⌦) if and only if it satisfies the three following conditions:

(1) 8t K k . . . t K 1 , the element g t K k ...t K 1 1 is in ⌦ ⇢ H K+1 and the elements g t K k ...t K 1 2 , . . . , g t K k ...t K 1 d K are in A K+1 , (2) 8t K k . . . t K 2 ,
the set:

I(t K k . . . t K 2 ) = {T K 1 2 {1, . . . , d K 1 }| 1 t K k ...t K 2 T K 1 (1) = 1} = {T K 1 2 {1, . . . , d K 1 }|g t K k ...t K 2 T K 1 2 ◆L K 0 (⌦) ⇢ K } is non-empty. (3) 82  l  k, 8t K k . . . t K l
, the following subset of {1, . . . , d K l+1 }:

I(t K k . . . t K l ) = {T K l+1 | 1 t K k ...t K l T K l+1 (1) 2 I(t K k . . . t K l T k l+1 )}, = {T K l+1 |g t K k ...t K l T K l+1 2 ◆L K l 2 (⌦) ⇢ K l+2 }, defined by induction on l, is non-empty.
The element g belongs to ◆L K k (⌦) if and only if it satisfies (1), ( 2), (3) and moreover: (4)

1 (1) belongs to the set:

I(;) = {T K k | 1 T K k (1) 2 I(T K k )} = {T K k |g T K k 2 ◆L K k 1 (⌦) ⇢ K k+1 }.
The element g belongs to Int(L K k (⌦)) if and only if it satisfies (1), ( 2), ( 3), (4) and moreover:

(5

) g ⌧ K k ...⌧ K 2 Int(⌦).
This description and especially point (5) prove the: Fact 4.10. With respect to the generating set A K k [ B K k of the group K k , and the generating set B K+1 of the group H K+1 , one has:

|Int(L K k (⌦))| = |◆L K k (⌦)| |Int(⌦)| |⌦| .
In particular, the set

◆L K k (⌦) is precisely the interior Int(L K k (⌦)) when Int(⌦) = ⌦. This happens when H K+1 (hence H 0 ) is finite. For 0  k  K, set |◆L K k (⌦)| |L K k (⌦)| = 1 " k .
The number " k will be denoted " K k later on to emphasize the dependance on K. Lemma 3.6 generalizes as: Lemma 4.11. The sequence (" k ) 0kK satisfies " 0 = 1 1 d K and:

1 " k+1 = 1 " k 1 " d K k 1 k .
Proof. Given a subset I ⇢ {1, . . . , d K k 1 }, denote:

J I = {g = (g 1 , . . . , g d K k 1 ) |8T 2 I, g T 2 ◆L K k (⌦) and 8t / 2 I, g t 2 L K k (⌦)\◆L K k (⌦)}. By definition, L K k+1 (⌦) is the disjoint union L K k+1 (⌦) = t |I| 1 J I .
As in the proof of lemma 3.6, one has for i = |I|:

|J I | = |A K k 1 ||L K k (⌦)| d K k 1 (1 " k ) i " d K k 1 i k , |J I \ ◆L K k+1 (⌦)| = i d K k 1 |J I |.
Again by use of the mean of binomial distribution, get:

|◆L K k+1 (⌦)| = d K k 1 X i=1 C i d K k 1 (1 " k ) i " d K k 1 i k i d K k 1 |L K k (⌦)| d |A K k 1 | = (1 " k )|L K k (⌦)| d |A K k 1 |, |L K k+1 (⌦)| = d K k 1 X i=1 C i d K k 1 (1 " k ) i " d K k 1 i k |L K k (⌦)| d K k 1 |A K k 1 | = (1 " d K k 1 k )|L K k (⌦)| d |A K k 1 |. This proves the lemma. ⇤ Lemma 4.12. If d k log k ! 0, then " K K ! 0. If d k  D for all k, then " K K = O(K ⌘ ) for all ⌘ < 1 D 1 .
First check the elementary:

Fact 4.13. Let f (D, ") = 1 " D 1
1 " D , for D 2 and " 2 (0, 1). Then for fixed D, the function f (D, ") is decreasing with ", and for fixed ", the function f (D, ") is increasing with D.

Proof. Compute derivatives:

(1

" D ) 2 @f @" (D, ") = " D 2 (1 ")(" D 1 + • • • + " 2 + " (D 1)) < 0, (1 " D ) 2 @f @D (D, ") = " D 1 (" 1) log " > 0. ⇤
Proof of lemma 4.12. For a fixed K, and 0

 k  K, set D k = d K k , and D(K) = max 0kK {d k } = o(log K)
. By lemma 4.11, one has:

" k+1 = " k 1 " D k+1 1 k 1 " D k+1 k = " k f (D k+1 , " k ).
By fact 4.13, as long as " k E, one has:

" k+1  " k f (D k+1 , E)  " k f (D(K), E), so " K = " K K  max{E, f (D(K), E) K } for any E 2 (0, 1). Now consider a sequence E K ! 0 so that |D(K) log E K | = o(log K) (it exists). One has: f (D(K), E K ) K = expK(log(1 E D(K) 1 K ) log(1 E D(K) K )), = exp( KE D(K) 1 K + O(KE D(K) K )) ! 0, because KE D(K) 1 K ! +1. This shows " K K ! 0. If moreover d k  D, take E K = K ⌘ with ⌘ < 1 D 1 , then: f (D, E K ) K = exp( K 1 ⌘(D 1) + O(K 1 ⌘D )) = o(K ⌘ ), so " K K = O(K ⌘ ). ⇤
Proof of theorem 4.5. By fact 4.10, one has:

|Int(L K K (⌦))| |L K K (⌦)| = |◆L K K (⌦)| |L K K (⌦)| |Int(⌦)| |⌦| = (1 " K K ) |Int(⌦)| |⌦| .
As the group H K+1 is amenable by fact 4.3, the set ⌦ can be chosen with

AT i = AT (d i , d i+1 ) = (A d i+1 ⇥ • • • ⇥ A d i+1 ) o A d i 1 = A d i+1 o A d i 1 ,
where A d is the alternate group of even permutations of the set {1, . . . , d}, there are d i 1 factors in the product (indexed by {2, . . . , d i }), and A d i 1 acts by permuting these factors. Consider the countable infinite direct product:

H alt d = 1 Y i=0 AT i = 1 Y i=0 A d i+1 o A d i 1 .
Its elements are denoted as sequences h = (h i ) When the sequence d is constant

(h i ) 1 i=0 = ((h i ) 1 i=1 , a 0,2 , . . . , a 0,d 0 )⇢ 0 , where ⇢ 0 2 A d 0 1 ' F ix A d 0 (1). Inductively under isomorphism Aut(T k d) ' Aut(T k+1 d) o S d k , one has (h i ) 1 i=k = ((h i ) 1 i=k+1 , a k,2 , . . . , a k,d k )⇢ k .
d i = d, if A = A d and H ' A d oA d 1 is diagonaly embedded into the direct product H alt d , then G(A, H) = G d is
the alternate mother group of section 3. Directed groups (not necessarily alternate) satisfy the same definition without requirement that the permutations involved are even, that is with S d instead of A d and H ]).

d = Q 1 i=0 S d i+1 o S d i 1 instead of H alt d (see [Bri1], [ Bri3
5.2. Case of bounded valency. In this section, assume that the sequence d is bounded 5  d i  D. Let B ⇢ H alt d be a finite subset, and denote its elements by = ( i ) 1 i=0 2 H alt d . Then for each i, the set { i , 2 B} is a B-indexed subset of AT i = AT (d i , d i+1 ). As the valency sequence d is bounded, there is a finite set of pairs:

{(AT (s), { (s), 2 B}), s 2 J}, such that for any i, there exists s(i) in the finite set J with (AT i , { i , 2 B}) = (AT (s(i)), { (s(i)), 2 B}), as pairs of finite groups with B-indexed subsets.

This provides an isomorphism:

H alt d > H = h , 2 Bi ' h( (s)) s2J , 2 Bi < Y s2J AT (s).
The group H is said saturated if H = Q s2J AT (s). (Mind a di↵erence with the notion of saturation in [START_REF] Brieussel | Amenability and non-uniform growth of some directed automorphism groups of a rooted tree[END_REF] and [START_REF] Brieussel | Behaviors of entropy on finitely generated groups[END_REF], where it was only required that H surjects on each factor AT (s). The present condition is slightly stronger.) Finiteness of J shows the: Fact 5.2. If d is bounded, any finitely generated subgroup of H alt d is contained in a finite saturated subgroup H.

The following proposition will permit to show amenability of all directed groups acting on a tree of bounded valency.

0 = H. Proof. Set H 1 = {(h i ) 1 i=1 |(h i ) 1 i=0 2 H}.
The only non-trivial point in order to verify definition 4.1 is surjectivity of the isomorphism: and v = e if v is not of the form 1 k 1 t for some t in {1, . . . , d k }. This is still the case for a( ). ⇤

' 0 : G(A d 0 , H) ! G(A d 1 , H 1 ) o A d 0 . Given h = (h i ) 1 i=0 in H d with h i = (a i,2 , . . . , a i,d i )⇢ i , set: h(2) = ((a i,
The following result from [START_REF] Brieussel | Amenability and non-uniform growth of some directed automorphism groups of a rooted tree[END_REF] can now be reproved.

Corollary 5.5. Directed groups acting on a tree of bounded valency are amenable.

Proof. Let be a directed group, with generating set S [ H where S ⇢ S d 0 and H ⇢ H d. By fact 5.4, the group a( ) < Aut alt (T 2d ) is alternate and directed. By fact 5.2, it can be included in a directed, alternate and saturated subgroup of Aut alt (T 2d ), which is in the class DP by proposition 5.3, hence amenable by theorem 4.5, since 2d is bounded and H 0 finite. The group is also amenable as a subgroup. ⇤ Corollary 5.6 (Main theorem in [BKN]). Automata groups with bounded activity are amenable.

Proof. By theorem 3.3 in [BKN], an automata group with bounded activity is a subgroup of the alternate mother group of degree 0 acting on a d-regular tree for d large enough. By fact 5.4, is a subgroup of G 2d , hence is amenable by theorem 3. given by the portrait (b 0 (h))

1 k 1 2 = a k (h) and (b 0 (h)) v = e if v is not of the form

Fact 3. 2 .

 2 Let d 5, then for any generator a = a( ) 2 A and b = b(a 2 , . . . , a d , ⇢) 2 B, the elements (a, e, . . . , e) and (b, e, . . . , e) belong to G d .

  On the other hand, the group A d 0 acts on T d by rooted automorphisms: A d 0 3 a = (e, . . . , e)a. Definition 5.1. An alternate directed group G is a subgroup of Aut(T d) with generating set A [ H, with A ⇢ A d 0 and H ⇢ H alt d . Denote: G(A, H) = hA [ Hi < Aut(T d).

  Proposition 5.3. Let d be a bounded sequence of integers d i 5. If H < H alt d is a finite saturated subgroup, then the alternate directed group G(A d 0 , H) < Aut(T d) belongs to the class DP with A 0 = A d 0 and H

  Examples with unbounded valency. This section aims at constructing examples of groups in the class DP for which the sequence d of fact 4.2 is unbounded.Let H0 be a finitely generated, residually finite, perfect group with a sequence of normal subgroups (N k ) k 0 of finite index so that each quotient A k = H 0 /N k is perfect, acting faithfully and transitively on a finite set {1, . . . ,d k } of size d k 2. For h in H 0 , denote a k (h) = hN k 2 A k . To thegroup H 0 together with subgroup sequence (N k ) k 0 is associated an action on the rooted tree T d of valency sequence d = (d k ) k 0 , denoted b 0 : H 0 ! Aut(T d),

  Given a sequence d = (d k ) k 0 of integers 2, the spherically homogeneous rooted tree T

d is the graph with vertex set {t 0 t 1 . . . t k |t i 2 {1, . . . , d i }, k 1}, including the empty sequence ;, called the root, corresponding to k = 1, and edge set {(t 0 . . . t k , t 0 . . . t k t k+1 )}. The vertex set restricted to a fixed k is called the k + 1st level of the tree. It is the direct product {1, . . . , d 0 } ⇥ • • • ⇥ {1, . . . , d k }. When the sequence d is constant equal to d, the tree is called d-regular, denoted T d . The group of automorphisms Aut(T d) of the rooted tree T d is the group of graph automorphims that fix the root ;. It satisfies a canonical isomorphism:

  Folner sets of the alternate mother group 3.1. The alternate mother group. Define alternate automorphisms of the dregular rooted tree T d by use of the wreath product isomorphism Aut alt (T d ) ' Aut alt (T d ) o A d .

  e G , e G , . . . , e G ). G , . . . , e G , e A ) with a 2 in A d . Moreover for any b ; = b(e G , . . . , e G , ⇢) with ⇢ in F ix A (1) ' A d 1 , the group G d contains b ; a(⇢ 1 ) = (b ; , e G , . . . , e G ). G , . . . , e G , e A ) and b ; = b(e G , . . . , e G , ⇢) generate B by isomorphism (2), because ⇢ in A {2,...,d} and (a 2 , e A , . . . , e A ) for a 2 in A d generate the finite group (A d ⇥ • • • ⇥ A d ) o A {2,...,d} . Thus G d contains (b, e G , . . . , e G ) for any b in B.

	As [b(↵	2 , e G , . . . , e G , e A ), b(↵ 0 2 , e G , . . . , e G , e A )] = b([↵	2 , ↵ 0 2 ], e G , . . . , e G , e A ) and as the
	group A = A d is perfect (because it is simple), any element a a product of commutators. This shows that G d contains (b 2 , e G , . . . , e G ) for any 2 in A ' A d is
	b	2 = b(a 2 , e Now the elements b 2 , e Finally given a 2 = b(a 2 in A, for b 2 = b(a 2 , e G , . . . , e G , e A ) = (b	2 , a 2 , e G , . . . , e G ), the
	element (b 1 2 , e G , . . . , e

G ) belongs to G d by the above. So do (b 1 2 , e G , . . . , e G )b 2 = (e G , a 2 , e G , . . . , e G ) and (e G , a 2 , e G , . . . , e G

  3.7. Lemma 3.5 provides a complete combinatorial description of L k . An element g of G d has the form g = (g t 0 ...t k )( t 0 ...t k 1 ) . . . ( t 0 ) in the kth iteration of the wreath product. Such an element g belongs to L k if and only if it satisfies the three following conditions: (1) 8t 0 . . . t k 1 , the element g t 0 ...t k 1 1 is in B and g t 0 ...t k 1 2 , . . . , g t 0 ...t k 1 d are in A, (2) 8t 0 . . . t k 2 , the set I(t 0 . . . t k 2

  Conditions (1), (2), (3) ensure that g belongs to L k if and only if each vertex v has at least one neighbour of next level vT which is open. Condition (4) ensures that g is in the interior Int(L k ) if and only if the root itself is open. The class DP. Theorem 3.3 can be generalized to a wider setting.

				4. Generalization
	4.1. Definition 4.1. A group two following conditions:	0 belongs to the class DP if and only if it satisfies the
	(1) the group	0 contains two subgroups A 0 and H	0 such that:
	(a) the set A 0 [ H (b) the group A 0 is finite, acting transitively on a finite set {1, . . . , d 0 generates the group 0 , size d 0 2,	0 } of
	(c) the group H	0 is finitely generated (denote B	0 some finite generating set
	of H	0 , so	0

Note that condition (2) is a specific case of condition (3) where I(t 0 . . . t k 1 ) = {1} for all t 0 . . . t k . As an interpretation, say a vertex v = t 0 . . . t l with l  k 1 is open if 1 v (1) 2 I(v).

  The following theorem provides a partial answer, with a condition on the sequence of integers d = (d i ) i . i in the class DP, consider the sequence of finitely generated groups K = hA K [ B K i obtained by iterating definition 4.1, where B K is the canonical generating set of the group H K .

	Theorem 4.5. Let su ciently slowly (for instance d k 0 belong to the class DP with H log k ! 0), then 0 is amenable. 0 amenable and d growing
	This theorem generalizes theorem 3.3. The proof is similar, though slightly more
	technical.
	4.2. Proof of theorem 4.5. Given	0 = hA	0 [ B
	with d	0 factors in the direct product, on which A 0 is acting by permutation
	of coordinates, according to its transitive action on {1, . . . , d this isomorphism ' 0 satisfies:	0 }. Moreover,
	0 , ' (a) 8s 2 A (b) 8h 2 H 0 , 9h 0 (s) = (e 1 , . . . , e 1 )s, 1 2 H 1 , 9a 2 , . . . , a d 0 2 A 1 , 9⇢ 2 A 0 , with ⇢(1) = 1 and:
		'	0 (h) = (h	1 , a 2 , . . . , a d 0 )⇢.
	Note that in (2)(b), the groups A	1 and H	1 are the subgroups of	1 satisfying condi-
	tion (1) for

1 , which belongs to DP. 0

  Alternate directed groups. Given a sequence d = (d i ) i2N of integers d i 2, set:

	|Int(⌦)| |⌦| arbitrarily close to 1. By lemma 4.12, this shows that there exists a sequence of sets
	⌦ K ⇢ H K+1 so that the sets L K K (⌦ K ) ⇢	0 form a Folner sequence.	⇤
	5. Examples of groups in the class DP
	5.1.

  1 i=0 with h i = (a i,2 , . . . , a i,d i )⇢ i 2 AT i .

	The group H alt d	acts faithfully on the spherically homogeneous rooted tree T	d
	in the direction of the ray 1 1 , where under the canonical isomorphism Aut(T Aut(T d) o S d 0 , one has:	d) '

  Let be a permutation of the set {1, . . . , d}. Denote 0 another copy of acting on the set {d + 1, . . . , 2d} by 0 (t) = (t d) + d, and consider the embedding a : S d ,! A 2d given by a( ) = 0 . It can be extended to furnish: a : Aut(T d) ! Aut alt (T 2d ), an embedding of the group of automorphisms of the tree T d into the group of alternate automorphisms of the tree T 2d . Indeed, let 2 Aut(T d) be described by a family of permutations{ v } v2T d , where v 2 S d k for every v = t 1 . . . t k in T d.The automorphism a( ) is described by a family of permutations {a( ) v } v2T 2d given by a() v = a( v ) 2 A 2d k for v = t 1 . . . t k in T d ⇢ T 2d and a( ) v = e for v 2 T 2d \ T d.Fact 5.4. Directed elements have directed image under a, i.e. a(H d) ⇢ H alt 2d . In particular, the mother group of degree 0 acting on a d-regular tree embeds in the alternate mother group G 2d acting on a 2d-regular tree. Proof. As a shortcut denote 1 k for the sequence 11 . . . 1 with k ones. By definition, an automorphism is directed if and only if 1 k 2 F ix S d k (1) ' S d k 1

			2 , e, . . . , e)e) 1 i=0 , and h(;) = ((e, . . . , e)⇢ i ) 1 i=0 .
	In each factor AT (s) = A d 0	(s) o A d(s) 1 , the subset
	{(a 2 , e, . . . , e)|a	2 2 A d 0	(s) } [ {(e, . . . , e)⇢|⇢ 2 A d(s) 1 }
	generates the group AT (s). Thus by saturation
	hh(2), h 2 Hi '	Y s2J	A d 0	(s) ⇥ {e} ⇥ • • • ⇥ {e}, and hh(;), h 2 Hi '	Y s2J	A d 0	(s) .

So saturation shows that the subsets H(2) = {h(2), h 2 H} and H(;) = {h(;), h 2 H} are subgroups of H, and moreover hH(2) [ H(;)i = H. The proofs of fact 3.2 and proposition 3.1 apply directly, replacing the generators b 2 = b(↵ 2 , e, . . . , e, e A ) and b ; = b(e, . . . , e, ⇢) by h(2) and h(;) respectively. ⇤

E-mail address: jeremie.brieussel@gmail.com

Consider a group

0 in the class DP, together with a finite generating set A 0 [B 0 . There exists a sequence of groups i with finite generating sets A i [ B i , such that A i is a finite group acting transitively on {1, . . . , d i }, and an isomorphism:

such that for any b i 2 B i , there exists b i+1 2 B i+1 , a i,2 , . . . , a i,d i 2 A i+1 , ⇢ i 2 A i with ⇢ i (1) = 1 and:

1 is unique, hence from a given b 0 , there is a unique associated sequence b i ). This sequence of groups i is obtained inductively, applying definition 4.1 to i , which belongs to DP, to define i+1 . Set

The groups of the class DP are related to the groups of non-unifrom growth constructed by Wilson (see [START_REF] Wilson | On exponential growth and uniformly exponential growth for groups[END_REF], [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]). In particular, if all the groups i associated to a group 0 are generated by a finite number (independent of i) of involutions, and if all the groups A i involved are alternate groups A d i acting on sets of size d i 29, then they have non-uniform growth by [START_REF] Wilson | Further groups that do not have uniformly exponential growth[END_REF]. This is the case of the examples in proposition 5.3 below.

Fact 4.2. If 0 belongs to DP, there exists a sequence d = (d i ) i of integers d i 2, and the group 0 is acting by automorphisms on the spherically homogeneous rooted tree T d. This action is transitive on each level. Note that this action on the tree is not necessarily faithful (for instance, the subgroup F of the group = (A d 0 , A d, F ) of section 2.4 of [START_REF] Brieussel | Behaviors of entropy on finitely generated groups[END_REF] has a trivial action on the tree T d, even though belongs to the class DP).

Proof. By iteration of definition 4.1, there is an isomorphism

Taking the limit with i, this provides the action on the tree T d.

⇤

Fact 4.3. The group H 0 is amenable if and only if the groups H i are amenable for all i.

Proof. By (2)(b), the restriction of ' 0 to H 0 provides an embedding:

where the j factors in the iterated wreath product are obtained by iteration of the above isomorphism. The group St j is called stabilizer of level j of the group G d . The quotient G d /St j is acting transitively on level j, which is the set {1, . . . , d} j . By [Neu], these stabilizers St j are the only finite index normal subgroups of G d .

For an arbitrary function j : N ! N, take N k = St j(k) as a sequence of normal subgroups. The group 0 defined by G d together with the function j(k) belongs to the class DP by fact 5.7. It is amenable when d j(k) is sublogarithmic by theorem 4.5. Note that in the construction above, one could use any group of proposition 5.3 with d i 6 instead of G d .