---
abstract: 'We show that the group of bounded automatic automorphisms of a rooted tree is amenable, which implies amenability of numerous classes of groups generated by finite automata. The proof is based on reducing the problem to showing amenability just of a certain explicit family of groups (“Mother groups”) which is done by analyzing the asymptotic properties of random walks on these groups.'
address:
- 'Institut de Mathématiques B, École Polytechnique Fédérale de Lausanne, CH-1015 Lausanne, Switzerland'
- 'Mathematics, Jacobs University Bremen, Campus Ring 1, D-28759, Bremen, Germany'
- 'Department of Mathematics, Texas A&M University, College Station, TX 77843-3368, USA'
author:
- Laurent Bartholdi
- 'Vadim A. Kaimanovich'
- 'Volodymyr V. Nekrashevych'
bibliography:
- 'C:/Sorted/MyTEX/mine.bib'
title: On amenability of automata groups
---

Introduction {#introduction .unnumbered}
============

Since the definition of amenability of groups by von Neumann, many attempts were made to understand amenability and to describe it in various ways. The class of countable amenable groups is, from the analytical point of view, the most natural extension of the class of finite groups. Namely, according to the original definition of von Neumann [@vonNeumann29] these are the groups which admit an invariant mean (a finitely additive probability measure). An amenable group does not contain non-abelian free subgroups. However, the converse is not true, and, in spite of existence of numerous geometric or analytic criteria of amenability (Tarski, Følner, Reiter, Kesten, etc.), there is no satisfactory “algebraic” description of the class of amenable groups. From this point of view, essentially new examples of amenable and non-amenable groups are still of great interest.

It was proved already by von Neumann that the class of amenable groups is closed under passing to subgroups, quotients, group extensions and inductive limits. Therefore, starting from “obviously” amenable groups (which are finite groups and the infinite cyclic group), one can construct many examples of amenable groups. The groups obtained in this way are called *elementary amenable groups*, following Day [@Day57].

It was an open question for a long time whether every amenable group is elementary amenable. The first example of an amenable but not elementary amenable group is the group of intermediate growth found by Grigorchuk [@Grigorchuk80; @Grigorchuk85] (every group of subexponential growth is amenable by Følner’s criterion). Later, a finitely presented amenable extension of the Grigorchuk group was constructed in [@Grigorchuk98].

Groups of subexponential growth can also be considered as “obviously” amenable. Therefore, a natural goal (see [@Grigorchuk98; @Ceccherini-Grigorchuk-delaHarpe99]) is to find amenable groups, which are not *subexponentially elementary*, i.e., can not be obtained from the groups of subexponential growth by the aforementioned amenability preserving operations.

The first example of such a group is the *iterated monodromy group* of the polynomial $z^2-1$ known as the *Basilica group*. It was shown in [@Grigorchuk-Zuk02a] that it does not belong to the class of subexponentially elementary groups, whereas it was proved in [@Bartholdi-Virag05] that the Basilica group is amenable.

The aim of the present paper is to establish amenability of a vast class of groups generated by finite automata. Namely,

**Main Result.** *Any group generated by a finite bounded automaton is amenable*.

The class of groups generated by bounded automata was defined by Sidki in [@Sidki00] (see [@Bondarenko-Nekrashevych03] for an interpretation of these groups in terms of fractal geometry). Most of the well-studied examples of groups of finite automata belong to this class. In particular, it contains the Grigorchuk group, the Gupta–Sidki group, the Basilica group, all iterated monodromy groups of postcritically finite polynomials, and many other examples (see [Section \[sec:examples\]]{} for more details). For most of them (except for the situation when the group happens to have subexponential growth) our proof is the only proof of amenability known so far.

Note that the groups generated by bounded automata form a subclass of the class of *contracting self-similar groups* (see [@Bondarenko-Nekrashevych03; @Nekrashevych05]). It is still an open question whether all contracting groups are amenable.

Any group generated by a bounded automaton is contained in the countable group ${{\mathfrak{BA}}}$ of *all* bounded automatic automorphisms of a rooted homogeneous tree, and it is amenability of the latter that we actually establish ([Theorem \[thm:main\]]{}). Our proof is based on two ideas. First we reduce the question about amenability of ${{\mathfrak{BA}}}$ to that about amenability just of a certain special family of groups which we call *Mother groups* ([Theorem \[thm:reduc\]]{}). Then we deduce amenability of these groups from an analysis of the asymptotic properties of *random walks* on them ([Theorem \[thm:amen\]]{}). Namely, we show, by applying a self-similarity argument, that the growth of the entropy of the $n$-fold convolutions of a certain probability measure is sublinear, which, by the general entropy theory (see [@Kaimanovich-Vershik83]), implies amenability. Therefore, our proof ultimately uses Reiter’s characterization of amenability: we construct a sequence of approximately invariant measures on the group as the convolution powers of a certain finitely supported one. A constructive version of this argument based on entropy estimates yields explicit bounds for the return and isoperimetric profiles on the Mother groups ([Theorem \[th:profile\]]{}). On the other hand, we do not obtain any explicit description of the Følner sets.

The paper has the following structure. In [Section \[sec:main\]]{} we formulate the main result and give a number of examples of its applications. The background on bounded automata is discussed in [Section \[sec:bounded\]]{}. In [Section \[sec:fg\]]{} we reduce the problem to amenability of Mother groups, which is established in [Section \[sec:amen mother\]]{} by an analysis of random walks on these groups. Finally, we relegate certain auxiliary estimates of the entropy of convolutions on general countable groups to the Appendix.

The authors express their debt and gratitude to Bálint Virág, who generously contributed valuable insight to this paper.

Statement of the main result {#sec:main}
============================

Decomposition of tree automorphisms
-----------------------------------

Let $X$ be a finite set called the *alphabet*. The associated *homogeneous rooted tree* $T=T(X)$ is the (right) Cayley graph of the free monoid $X^*$ (so that one connects $w$ to $wx$ by an edge for all $w\in
X^*,x\in X$). Each vertex $w\in T\cong X^*$ is the root of the subtree $T_w$ which consists of all the words beginning with $w$. The map $w'\mapsto ww'$ provides then a canonical identification of the trees $T$ and $T_w$.

Let us denote by ${{\mathfrak W}}={{\mathfrak W}}(X)={\operatorname{\mathsf{Aut}}}(T)$ the *full automorphism group* of the tree $T$. Any automorphism $\alpha\in{{\mathfrak W}}$ obviously preserves the first level of $T$, i.e., determines a permutation $\sigma=\sigma_\alpha\in{{\mathsf{Sym}(X)}}$. Thus, any subtree $T_x$, for $x\in
X$, is mapped by $\alpha$ onto the subtree $T_{\sigma(x)}$, which, in view of the canonical identification of both $T_x$ and $T_{\sigma(x)}$ with $T$, gives rise to an automorphism $\alpha_x\in{{\mathfrak W}}$. Conversely, any set of data consisting of automorphisms $\alpha_x\in{{\mathfrak W}}$ for all $x\in X$ and a permutation $\sigma\in{{\mathsf{Sym}(X)}}$ determines in the above way an automorphism of $T$. Thus, we have a one-to-one correspondence $$\label{eq:dec}
\alpha\mapsto\pair<\alpha_x>_{x\in X}\sigma_\alpha$$ (called *decomposition*) between ${{\mathfrak W}}$ and ${{\mathfrak W}}^X\times{{\mathsf{Sym}(X)}}$. We shall omit $\sigma_\alpha$ in this notation if it is the identity permutation. In terms of this decomposition the group multiplication in ${{\mathfrak W}}$ takes the form $$\pair<\alpha_x>\sigma_\alpha\cdot \pair<\beta_x>\sigma_\beta=
\pair<\alpha_x\beta_{\sigma_\alpha(x)}>\sigma_\alpha\sigma_\beta,$$ which means that decomposition is in fact a group isomorphism between ${{\mathfrak W}}$ and the *permutational wreath product* ${{\mathfrak W}}\wr{{\mathsf{Sym}(X)}}={{\mathfrak W}}^X\rtimes{{\mathsf{Sym}(X)}}$. We shall often identify ${{\mathfrak W}}$ with ${{\mathfrak W}}\wr{{\mathsf{Sym}(X)}}$ by the decomposition isomorphism , writing $\alpha=\pair<\alpha_x>\sigma_\alpha$, especially in recursive definitions of automorphisms of the tree $T$. See [@Bartholdi-Grigorchuk00] or [@Nekrashevych05 Section 2.6] for more on recursions of this kind and [Example \[ex:basilica\]]{} for a more detailed description of this procedure for a concrete group.

Generalized permutation matrices {#sec:gen perm}
--------------------------------

It will also be convenient to use the matrix notation by presenting an element $\alpha=\pair<\alpha_x>\sigma$ as a *generalized permutation matrix* $M=M^\alpha$ of order $|X|$ with entries $$M_{xy}=\left\{\begin{array}{ll}\alpha_x &\text{if $y=\sigma(x)$,}\\
0 & \text{otherwise.}\end{array}\right.$$ We identify in this way the group ${{\mathfrak W}}\wr{{\mathsf{Sym}(X)}}$ with a subgroup of the matrix algebra ${{\mathsf M}}_{|X|}({\mathbb{C}}[{{\mathfrak W}}])$ over the group ring of the group ${{\mathfrak W}}$. It is easy to see that this identification is actually a group isomorphism.

More generally, given an arbitrary group $G$, we shall denote by $${{\mathsf{Sym}(X;G)}}:= G\wr{{\mathsf{Sym}(X)}}=G^X\rtimes{{\mathsf{Sym}(X)}}$$ the *group of generalized permutation matrices* of order $|X|$ with non-zero entries from the group $G$. Obviously, application of the *augmentation map* (which consists in replacing all group elements with 1) to a generalized permutation matrix yields a usual permutation matrix, which corresponds to the natural projection of ${{\mathsf{Sym}(X;G)}} \cong
G^X\rtimes{{\mathsf{Sym}(X)}}$ onto ${{\mathsf{Sym}(X)}}$.

Automatic and bounded automorphisms {#sec:bdd}
-----------------------------------

Recall that given an automorphism $\alpha\in{{\mathfrak W}}$ any symbol $x\in X$ determines an associated automorphism $\alpha_x\in{{\mathfrak W}}$ by decomposition . In the same way such an automorphism $\alpha_w\in{{\mathfrak W}}$ (the *state* of $\alpha$ at the point $w$) can be defined for an arbitrary point $w\in T\cong X^*$, by restricting the automorphism $\alpha$ to the subtree $T_w$ with the subsequent identification of both $T_w$ and its image $\alpha(T_w)=T_{\alpha(w)}$ with $T$. Equivalently, $\alpha_w$ can be obtained from iterating decomposition , see [Example \[ex:basilica\]]{} and the proof of [Theorem \[thm:reduc\]]{}.

If the *set of states* of $\alpha$ $${{\mathsf S}}(\alpha)={{\left\{\alpha_w\left|\,w\in T\right\}\right.}}\subset{{\mathfrak W}}$$is finite, then the automorphism $\alpha$ is called *automatic*. The set of all automatic automorphisms of the tree $T$ forms a countable subgroup ${{\mathfrak A}}={{\mathfrak A}}(X)$ of ${{\mathfrak W}}={{\mathfrak W}}(X)$ (see [Section \[sec:bounded\]]{} for more details).

An automorphism $\alpha$ is called *bounded* if the sets ${{\left\{w\in
X^n\left|\,\alpha_w\neq1\right\}\right.}}$ have uniformly bounded cardinalities over all $n$. The set of all bounded automorphisms forms a subgroup ${{\mathfrak B}}={{\mathfrak B}}(X)$ of ${{\mathfrak W}}={{\mathfrak W}}(X)$. We denote by ${{\mathfrak{BA}}}={{\mathfrak{BA}}}(X)={{\mathfrak B}}(X)\cap{{\mathfrak A}}(X)$ the *group of all bounded automatic automorphisms* of the homogeneous rooted tree $T$.

We can now formulate the main result of the paper

\[thm:main\] The group ${{\mathfrak{BA}}}(X)$ is amenable for any finite set $X$.

Examples {#sec:examples}
--------

In the rest of this Section we describe some interesting finitely generated subgroups of ${{\mathfrak{BA}}}$, amenability of which follows from Theorem \[thm:main\]. We define the generators of these groups by their decomposition .

\[ex:basilica\] Let $|X|=2$, denote by $\sigma$ the non-trivial element of ${{\mathsf{Sym}(X)}}$, and define the automorphisms $a,b$ recursively by the relations $$a=\pair<b,1>,\qquad b=\pair<a,1>\sigma,$$ or, in matrix terms, $$M^a=\left(\begin{array}{cc} b & 0\\ 0 &
  1\end{array}\right),\qquad
  M^b=\left(\begin{array}{cc} 0 & a\\ 1 & 0\end{array}\right).$$ More precisely, application of the augmentation map to the above generalized permutation matrices yields the usual permutation matrices of order 2 which describe the action of $a$ and $b$ on the first level $X$ of the tree $T$. Substitution of $M^a$ for $a$ and $M^b$ for $b$ gives the order 4 generalized permutation matrices $$\begin{pmatrix}
  0 & a & 0 & 0 \\
  1 & 0 & 0 & 0 \\
  0 & 0 & 1 & 0 \\
  0 & 0 & 0 & 1 \\
\end{pmatrix}
\;, \;
\begin{pmatrix}
  0 & 0 & b & 0 \\
  0 & 0 & 0 & 1 \\
  1 & 0 & 0 & 0 \\
  0 & 1 & 0 & 0 \\
\end{pmatrix} \;,$$ which, after applying the augmentation map, give rise to the usual order 4 permutation matrices describing the action of $a$ and $b$, respectively, on the second level $X^2$ of the tree $T$ which extends the action on $X$. By iterating this substitution once again we obtain the action of $a$ and $b$ by permutations on $X^3$, and so on, so that in the limit we obtain automorphisms of the full tree $T$. Note that the entries of the arising matrices are the states of these automorphisms, and therefore we can immediately see that both $a$ and $b$ are automatic and bounded.

The group $G=\langle a,b\rangle$ is called the *Basilica group* (because it is the iterated monodromy group of the *Basilica polynomial* $z^2-1$), it is contained in ${{\mathfrak{BA}}}$, and it is amenable [@Bartholdi-Virag05] but not “subexponentially elementary amenable” [@Grigorchuk-Zuk02a].

More generally, let $f(z)\in{\mathbb{C}}[z]$ be a *postcritically finite* complex polynomial, i.e., such that for every critical point $c$ of $f(z)$ the orbit ${{\left\{f^{n}(c)\left|\,n\ge 1\right\}\right.}}$ is finite. Let $P$ be the union of the orbits of all the critical points of $f$. Given a point $t\in{\mathbb{C}}\setminus P$ the fundamental group $\pi_1({\mathbb{C}}\setminus P, t)$ naturally acts by monodromy on the *preimage tree* $T$, whose vertex set consists of all the pairs $\{(f^{-n}(t),n)\}_{n\ge0}$ with edges joining $(\tau,n)$ and $(f(\tau),n-1)$. The resulting group of automorphisms of the tree $T$ is called the *iterated monodromy group* of the polynomial $f$. For more on iterated monodromy groups see [@Nekrashevych05]. In particular, it is proved in [@Nekrashevych05 Chapter 6] that iterated monodromy groups of postcritically finite polynomials are subgroups of ${{\mathfrak{BA}}}$, hence they are amenable by Theorem \[thm:main\].

Let $X$ and $\sigma$ be as in [Example \[ex:basilica\]]{}, and define the automorphisms $a,b$ by putting $$a=\pair<1,a>\sigma,\quad b=\pair<1,b^{-1}>\sigma\;,$$ i.e., $$M^a = \left(\begin{array}{cc}
  0 & 1\\ a & 0\end{array}\right) \;, \quad M^b = \left(\begin{array}{cc}
  0 & 1\\ b^{-1} & 0\end{array}\right)\;.$$ The group $G=\langle a,b\rangle$ determined by the above presentation is contained in ${{\mathfrak{BA}}}$, and it was studied by Brunner, Sidki and Vieira in [@Brunner-Sidki-Vieira99]. Later da Silva showed in her thesis [@daSilva01] that $G$ does not contain any non-abelian free subgroups. Since $G$ is amenable by Theorem \[thm:main\], we obtain another proof of that result.

Let $\sigma\in{{\mathsf{Sym}(X)}}$ be a cyclic permutation of the alphabet $X$, and choose $\varepsilon_2,\dots,\varepsilon_d$ from the cyclic group ${\mathbb{Z}}/d$, where $d=|X|$. Let $G=\langle a,b\rangle$ be the group generated by two order $d$ elements determined by the decompositions $$a=\pair<1,1,\dots,1>\sigma \;, \quad
b=\pair<b,a^{\varepsilon_2},\dots,a^{\varepsilon_d}> \;.$$ In particular, if $d=3$ and $(\varepsilon_i)=(1,-1)$ then $G$ is the infinite $2$-generated $3$-group studied by Gupta and Sidki in [@Gupta-Sidki83], and if $d=3$ and $(\varepsilon_i)=(1,0)$ then $G$ is the group of intermediate growth studied by Fabrykowski and Gupta in [@Fabrykowski-Gupta91]. This family of groups was called *GGS* groups (referring to Grigorchuk, Gupta and Sidki) by Baumslag [@Baumslag93]. They are all subgroups of ${{\mathfrak{BA}}}$.

Let $A$ be a subgroup of ${{\mathsf{Sym}(X)}}$. We shall consider two embeddings $\theta_1,\theta_2$ of $A$ into ${{\mathfrak W}}$ determined by the decompositions $$\theta_1(a)=\pair<1,1,\dots,1>a \;,\quad
\theta_2(a)=\pair<\theta_1(a),\theta_2(a),1,\dots,1> \;,$$ respectively, and then set $G=\langle\theta_1(A),\theta_2(A)\rangle$. These groups were considered by Neumann in [@Neumann86] to answer some questions of “largeness” formulated by Edjvet and Pride, and more recently by the first author [@Bartholdi03] to construct groups of exponential word growth for which the infimum of the growth rates is $1$ (also see [@Wilson04]). All of these groups are subgroups of ${{\mathfrak{BA}}}$.

Bounded automata {#sec:bounded}
================

In this Section we recall some standard facts about automata, see [@Grigorchuk-Nekrashevich-Sushchanskii00] and [@Sidki00] for further details.

Automata and automorphisms
--------------------------

An *automaton* $\Pi$ is a map of the product $X\times Q$ of two sets to itself. One of these sets $X$ is called the *alphabet* and the other one $Q$ is called the *state space* of the automaton. If $Q$ is finite then the automaton is called *finite*. The components $$\Pi_\oblong:X\times Q\to X \;, \quad \Pi_\bullet:X\times Q\to Q$$ of the map $\Pi$ are called the *output* and the *transition* functions of the automaton, respectively. An automaton $\Pi$ is *invertible* if $\Pi_\oblong(\cdot,q)$ is a bijection $X\to X$ for all $q\in Q$. We shall always impose that condition.

We interpret an automaton $\Pi$ as a machine which, being in state $q$ and reading an input letter $x$, goes to state $\Pi_\bullet(x, q)$ and outputs the letter $\Pi_\oblong(x,q)$. In this way it can also process words, which gives rise to the automaton $\Pi^*$ with extended alphabet $X^*$ and same state space $Q$. Its output and transition functions $\Pi_\oblong^*,\Pi_\bullet^*$ are extensions of the respective original functions $\Pi_\oblong,\Pi_\bullet$ and are defined recursively as $$\label{eq:*}
\begin{aligned}
 \Pi^*_\oblong(x_1x_2\dots x_n,q) &= \Pi_\oblong(x_1,q) \Pi^*_\oblong\left(x_2\dots x_n,\Pi_\bullet(x_1,q)\right) \;, \\
 \Pi_\bullet^*(x_1x_2\dots x_n,q) &= \Pi_\bullet^*(x_2\dots x_n,\Pi_\bullet(x_1,q)) \;.
\end{aligned}$$ Invertibility of $\Pi$ implies invertibility of the extended automaton $\Pi^*$ as well, whence

\[def:autom\] A state $q$ of an automaton $\Pi$ determines an automorphism $\Pi^*_\oblong(\cdot,q)$ of the tree $T(X)$ over its alphabet $X$. Such an automorphism is called *automatic*. Below we shall always identify the state $q$ with the associated automorphism $\Pi^*_\oblong(\cdot,q)$, i.e., we shall assume $Q\subset{{\mathfrak W}}$.

\[prop:equiv\] An automorphism $\alpha\in{{\mathfrak W}}$ is automatic in the sense of [Definition \[def:autom\]]{} if and only if it is automatic in the sense of the definition given in [Section \[sec:bdd\]]{}, i.e., if and only if its set of states ${{\mathsf S}}(\alpha)$ is finite.

If $\alpha=\Pi^*_\oblong(\cdot,q)$ is automatic, then ${{\mathsf S}}(\alpha)$ is precisely the set of states of the automaton $\Pi$ attainable from the state $q$.

Conversely, given an automorphism $\alpha\in{{\mathfrak W}}$, for any $q\in{{\mathsf S}}(\alpha)$ the associated decomposition $q=\pair<q_x>_{x\in X}\sigma_q$ obviously contains only elements of ${{\mathsf S}}(\alpha)$, so that we have maps $$\Pi_\oblong(x,q)=\sigma_q(x) \;, \quad  \Pi_\bullet(x,q)=q_x \;,$$ which, if the set ${{\mathsf S}}(\alpha)$ is finite, determine an automaton $\Pi$ with alphabet $X$ and state space ${{\mathsf S}}(\alpha)$ with the property that $\Pi^*_\oblong(\cdot,q)=q$ for all $q\in{{\mathsf S}}(\alpha)$.

Growth of automorphisms
-----------------------

The *growth function* $\Gamma_\alpha$ of an automorphism $\alpha$ is defined as the growth function of the language $${{\mathsf L}}(\alpha)={{\left\{w\in X^*\left|\,\alpha_w\neq 1\right\}\right.}}\;,$$i.e., $$\label{eq:growth funct}
\Gamma_\alpha(n)=\left|{{\left\{w\in X^n\left|\,\alpha_w\neq1\right\}\right.}}\right|.
$$

Denote by ${{\mathfrak B}}_d$ the set of automorphisms whose growth is bounded by a polynomial of degree $d$, so that, in particular, ${{\mathfrak B}}={{\mathfrak B}}_0$ is the set of *bounded automorphisms* introduced in [Section \[sec:bdd\]]{}, and let ${{\mathfrak F}}={{\mathfrak B}}_{-1}$ be the set of *finitary automorphisms*, i.e., the ones for which the growth function is eventually $0$ (obviously, ${{\mathfrak F}}\subset{{\mathfrak A}}$). Note that if $\alpha$ is automatic, then the language ${{\mathsf L}}(\alpha)$ is regular (since it is recognized by a finite automaton), so that in this case the growth function $\Gamma_\alpha$ is either polynomial or exponential.

It is easy to see that the growth function is *symmetric* and *subadditive* with respect to $\alpha$, i.e., $\Gamma_\alpha=\Gamma_{\alpha^{-1}}$ and $\Gamma_{\alpha\beta}\le\Gamma_\alpha+\Gamma_\beta$, so all subsets ${{\mathfrak B}}_d$ are subgroups of ${{\mathfrak W}}$. The groups ${{\mathfrak B}}_d$ do not contain non-abelian free subgroups [@Sidki04].

We shall say that an automorphism $\alpha\in{{\mathfrak W}}$ is *directed* if there exists a word $w_0\in X^l$ such that $\alpha_{w_0}=\alpha$, and all the other states $\alpha_w$ with $w\in X^l$ are finitary. The smallest number $l$ with this property is called the *period* of $\alpha$.

The following description of the group ${{\mathfrak{BA}}}={{\mathfrak B}}\cap{{\mathfrak A}}$ follows from [@Sidki00 Corollary 14].

\[pr:strbndd\] An automatic automorphism $\alpha$ is bounded if and only if it is either finitary or there exists an integer $m$ such that all non-finitary states $\alpha_w$ with $w\in X^m$ are directed.

\[def:depth\] By using [Proposition \[pr:strbndd\]]{} we can now define the *depth* of an arbitrary automatic bounded automorphism $\alpha$: if $\alpha$ is finitary, then its *finitary depth* is the smallest integer $m$ such that all the states $\alpha_w,\,w\in X^m$ are trivial; otherwise the *bounded depth* of $\alpha$ is the smallest integer $m$ from [Proposition \[pr:strbndd\]]{}.

Finitely generated subgroups of ${{\mathfrak{BA}}}$ and the Mother group {#sec:fg}
========================================================================

We show in this Section that a finitely generated group of bounded automorphisms can be put into a particularly simple form.

The Mother group
----------------

\[defn:mother\] Let $X$ be a finite set with a distinguished element $o\in X$, and put $\overline X=X\setminus\{o\}$. Set $A={{\mathsf{Sym}(X)}}$ and $B={{\mathsf{Sym}(\overline X)}}\wr A={{\mathsf{Sym}(\overline X;A)}}$, and recursively embed the groups $A$ and $B$ into ${{\mathfrak W}}(X)$ as $$A\ni a\mapsto(1,\dots,1)a \quad \text{ and } \quad
  B\ni b=(b_2,\dots,b_d)\sigma\mapsto(b,b_2,\dots,b_d)\sigma,$$ assuming that $X=\{o=1,\dots,d\}$. Still in that notation, the matrix presentations of $a,b$ are given by $$M^a = \phi_A(a) \;, \quad M^b=\begin{pmatrix} b & 0 \\ 0 & \phi_B(b)
\end{pmatrix} \;,$$ where $\phi_A(a),\phi_B(b)$ are, respectively, the permutation and the generalized permutation matrices corresponding to $a\in A,b\in B$. Then the *Mother group* ${{\mathfrak M}}={{\mathfrak M}}(X)=\langle A, B\rangle$ is the subgroup of ${{\mathfrak W}}$ generated by the finite groups $A$ and $B$.

A direct verification shows that both groups $A,B$ are contained in ${{\mathfrak{BA}}}$, whence

The group ${{\mathfrak M}}(X)$ is a subgroup of ${{\mathfrak{BA}}}(X)$.

Embedding of finitely generated subgroups of ${{\mathfrak{BA}}}$
----------------------------------------------------------------

\[thm:reduc\] Any finitely generated subgroup of ${{\mathfrak{BA}}}(X)$ can be embedded as a subgroup into the wreath product ${{\mathfrak M}}(X^N)\wr{{\mathsf{Sym}(X^N)}}$ for some integer $N$.

Let $G=\langle S\rangle$ be a finitely generated subgroup of ${{\mathfrak{BA}}}$, and let $\Pi$ be the automaton with alphabet $X$ and state space $Q=\bigcup_{\alpha\in S}{{\mathsf S}}(\alpha)$ which is the union of the automata associated with each automorphism $\alpha\in S$ (see the proof of [Proposition \[prop:equiv\]]{}). By boundedness, each ${{\mathsf S}}(\alpha)$ contains the identity automorphism 1, so that $1\in Q$.

Let $F={{\mathfrak F}}\cap Q$ be the set of finitary elements of $Q$, let $m$ be an integer greater than the depths of all the elements of $Q$ (see [Definition \[def:depth\]]{}), and finally let $\ell$ be a common multiple of the periods of directed automorphisms associated with non-finitary elements of $Q$.

First we apply $m$ times decomposition to the group $G$, i.e., embed it into the wreath product $H\wr\left(\wr^m{{\mathsf{Sym}(X)}}\right)$, where $\wr^m{{\mathsf{Sym}(X)}}<{{\mathsf{Sym}(X^m)}}$ is the automorphism group of the subtree consisting of the first $m$ levels of the tree $T$ and $H$ is the group generated by all the states $\alpha_w$ with $\alpha\in G$ and $w\in X^m$. Thus, $H=\langle
R\rangle$ for the subset $R={{\left\{q_w\left|\,q\in Q, w\in X^m\right\}\right.}}\subset Q$ of the states of $\Pi$.

We next replace $X$ by $X'=X^\ell$ and denote by $T'=(X')^*$ the associated tree, which is obtained from the tree $T$ by retaining only the levels whose numbers are multiples of $\ell$. Then $H$ is *a fortiori* a group of automatic automorphisms of $T'$. In that process, the automaton $\Pi$ is replaced by an automaton $\Pi'$ with alphabet $X'$, but with the same state space $Q$ as $\Pi$. Its output and transition functions are the restrictions of the respective functions of the automaton $\Pi^*$ .

Let us fix a letter $o'\in X'$, a transitive cycle $\varsigma\in{{\mathsf{Sym}(X')}}$, and for $x\in X'$ put $\varsigma_x=\varsigma^i$ for the unique $i\;
(\textrm{mod}\, |X'|)$ such that $x=\varsigma^i(o')$. We define an automorphism $\delta\in{\operatorname{\mathsf{Aut}}}(T')$ via its decomposition as $\delta=\pair<\delta'_x>_{x\in X'}$ with $\delta'_x=\delta\varsigma_x^{-1}$. In other words, the automorphism $\delta$ maps a word $\varsigma^{i_1}(o')\varsigma^{i_2}(o')\varsigma^{i_3}(o')\ldots\varsigma^{i_n}(o')\in
T'$ to the word $$\varsigma^{i_1}(o')\varsigma^{i_2-i_1}(o')\varsigma^{i_3-i_2}(o')\ldots
\varsigma^{i_n-i_{n-1}}(o') \;.$$

Then the $\delta$-conjugate of any automorphism $$\label{eq:alpha}
\alpha=\pair<\alpha'_x>_{x\in X'}\sigma\in{\operatorname{\mathsf{Aut}}}(T')$$ is $$\label{eq:ad}
\alpha^\delta = \delta^{-1}\alpha\delta =
\pair<{\delta'_x}^{-1}\alpha'_x\delta'_{\sigma(x)}>_{x\in X'} \sigma =
\pair<\varsigma_x\delta^{-1}\alpha'_x\delta\varsigma^{-1}_{\sigma(x)}>_{x\in
X'} \sigma =
\pair<\varsigma_x{\alpha'_x}^\delta\varsigma^{-1}_{\sigma(x)}>_{x\in X'}
\sigma \;.$$ By the choice of $\ell$, each $\alpha\in R$ either belongs to $F$ or else has decomposition with the property that $\alpha'_z=\alpha$ for precisely one letter $z=z(\alpha)\in X'$, and $\alpha'_x\in F$ whenever $x\neq
z$. In the latter case for $\beta=\beta(\alpha)=\varsigma_z\alpha^\delta\varsigma^{-1}_{\sigma(z)}$ we have $\beta=\pair<\beta'_x>\rho'$ with $\beta'_{o'}=\beta$, $\beta'_x\in{{\mathfrak F}}$ for any $x\in X'\setminus\{o'\}$, and the permutation $\rho'=\varsigma_z\sigma\varsigma^{-1}_{\sigma(z)}\in{{\mathsf{Sym}(X')}}$ satisfies $\rho'(o')=o'$.

Denote by $m'$ the maximal bounded depth of the automorphisms $\beta'_x$ from the previous paragraph for all $x\in X'\setminus\{o'\}$ and $\alpha\in R$, and finally enlarge once more the alphabet $X'$ to $X''=(X')^{m'}$ by putting $o''=(o')^{m'}$. Then in the associated decomposition $\beta=\pair<\beta''_x>_{x\in X''}\rho''$ with $\rho''\in{{\mathsf{Sym}(X'')}}$ we have $\rho''(o'')=o''$ and $\beta''_{o''}=\beta$. All the other automorphisms $\beta''_x,\,x\in X''\setminus\{o''\}$ are finitary of depth at most $m'$ with respect to the alphabet $X'$. Consequently they are finitary of depth at most 1 with respect to the alphabet $X''$, i.e., they belong to ${{\mathsf{Sym}(X'')}}$. Therefore, $\beta\in{{\mathfrak M}}(X'')$. Since the auxiliary element $\varsigma$ also belongs to ${{\mathfrak M}}(X'')$, we conclude that the $\delta$-conjugate $\alpha^\delta$ belongs to ${{\mathfrak M}}(X'')$, so that the $\delta$-conjugate of the whole group $H=\langle R\rangle$ is a subgroup of ${{\mathfrak M}}(X'')$.

Amenability of the group ${{\mathfrak{BA}}}$
--------------------------------------------

[Theorem \[thm:reduc\]]{} allows us to reduce the question about the amenability of the groups ${{\mathfrak{BA}}}(X)$ to the one about the amenability of the groups ${{\mathfrak M}}(X)\subset{{\mathfrak{BA}}}(X)$ from [Definition \[defn:mother\]]{}. Further developing the ideas from [@Bartholdi-Virag05] and [@Kaimanovich05] we shall prove in [Section \[sec:amen mother\]]{}

\[thm:amen\] For any finite alphabet $X$ the associated Mother group ${{\mathfrak M}}={{\mathfrak M}}(X)$ is amenable.

The group ${{\mathfrak{BA}}}(X)$ is amenable.

To show that ${{\mathfrak{BA}}}(X)$ is amenable, it suffices to show that all its finitely generated subgroups are amenable. Now by [Theorem \[thm:reduc\]]{} such a subgroup embeds, for a certain integer $N$, in ${{\mathfrak M}}(X^N)\wr{{\mathsf{Sym}(X^N)}}$, which is amenable because ${{\mathfrak M}}(X^N)$ is amenable.

Amenability of the Mother group {#sec:amen mother}
===============================

Random walks on self-similar groups {#sec:ss}
-----------------------------------

Let $G\subset{{\mathfrak W}}={{\mathfrak W}}(X)$ be a countable *self-similar group*, i.e., such that for any $g\in G$ all the elements $g_x$ from the decomposition $g=\pair<g_x>\sigma_g$ belong to $G$. We then have an embedding (not an isomorphism, generally speaking!) $G\to G\wr{{\mathsf{Sym}(X)}}$. In matrix terms it becomes an embedding $g\mapsto M^g$ of the group $G$ into the group of generalized permutation matrices ${{\mathsf{Sym}(X;G)}}$, see [Section \[sec:gen perm\]]{}. The latter embedding extends by linearity to an algebra homomorphism $$\label{eq:Mm}
\mu\mapsto M^\mu=\sum\mu(g) M^g$$ of the Banach algebra $\ell^1(G)$ into ${{\mathsf M}}_{|X|}(\ell^1(G))$.

The correspondence $\mu\mapsto M^\mu$ has a natural interpretation in terms of *random walks* on $G$, see [@Kaimanovich05]. Let $\mu$ be a probability measure on $G$; then the associated random walk $(G,\mu)$ is the Markov chain with transition probabilities $p(g,gh)=\mu(h)$, which we denote as $$g {\mathop{\,\mapstochar\relbar\joinrel\relbar\joinrel\rightsquigarrow\,}}_{h\sim\mu} gh \;.$$ By applying the embedding $g\mapsto M^g$, it gives rise to the random walk on the group ${{\mathsf{Sym}(X;G)}}$ with transition probabilities $$M {\mathop{\,\mapstochar\relbar\joinrel\relbar\joinrel\rightsquigarrow\,}}_{h\sim\mu} M M^h \;.$$ Further, each of the rows of matrices from ${{\mathsf{Sym}(X;G)}}$ performs a Markov chain with transition probabilities $$\label{eq:rwidf}
R {\mathop{\,\mapstochar\relbar\joinrel\relbar\joinrel\rightsquigarrow\,}}_{h\sim\mu} R M^h \;.$$ Due to the definition of the group ${{\mathsf{Sym}(X;G)}}$ the rows of the corresponding matrices can be identified with points of the product space $G\times X$ (each row has precisely one non-zero entry, so that it is completely described by the value of this entry and by its position). Therefore, the latter Markov chain can be interpreted as a Markov chain on $G\times X$ whose transition probabilities are easily seen to be invariant with respect to the left action of $G$ on $G\times X$. Such Markov chains are called random walks on $G$ with *internal degrees of freedom* (parameterized by $X$), for short RWIDF. Random walks with internal degrees of freedom are described by order $|X|$ matrices $M=(M_{xy})_{x,y\in X}$ whose entries $M_{xy}$ are subprobability measures on $G$ such that $\sum_y \|M_{xy}\|=1$ for any $x\in X$ (here $\|\mu\|$ denotes the mass of a measure $\mu$), so that the transition probabilities are then $$\label{eq:trans}
p\bigl((g,x),(gh,y)\bigr) = M_{xy}(h) \;.$$ The projection of the RWIDF governed by $M$ to the space of degrees of freedom $X$ is the Markov chain with transition probabilities $p(x,y)=\|M_{xy}\|$.

Now, the interpretation promised at the beginning of this paragraph is that the matrix describing the RWIDF is precisely the matrix $M^\mu$ from .

Random walks and amenability
----------------------------

The use of random walks for proving amenability of a self-similar group $G$ is based on an idea which first appeared in [@Bartholdi-Virag05] and was further developed in [@Kaimanovich05].

It is well-known that amenability of a countable group $G$ is equivalent to existence of a probability measure $\mu$ on $G$ such that it is *non-degenerate* (in the sense that its support generates $G$ as a group) and the *Poisson boundary* of the associated random walk $(G,\mu)$ is trivial. In addition, if the measure $\mu$ has finite entropy $H(\mu)$, then there is a quantitative criterion of triviality of the Poisson boundary: it is equivalent to vanishing of the *asymptotic entropy* $h(G,\mu)=\lim
H(\mu^n)/n$, where $\mu^n$ denotes the $n$-fold convolution of the measure $\mu$, see [@Kaimanovich-Vershik83]. Thus,

\[thm:entr\] If a countable group $G$ carries a non-degenerate probability measure $\mu$ with $h(G,\mu)=0$ then $G$ is amenable.

If the group $G$ is self-similar, then, as it was explained in [Section \[sec:ss\]]{} above, any random walk $(G,\mu)$ gives rise to a RWIDF $(G\times X,M^\mu)$. In [@Bartholdi-Virag05] and [@Kaimanovich05] one passed then from the RWIDF $(G\times X,M^\mu)$ to a new random walk $(G,\mu')$ by taking the *trace* of the RWIDF $(G\times X,M^\mu)$ on a single “layer” $G\times\{x_0\}\subset G\times X$ for an appropriately chosen letter $x_0\in
X$. The asymptotic entropy does not decrease under this passage: $h(G,\mu)\le
h(G,\mu')$. Therefore, if the measure $\mu$ is *self-similar* in the sense that $\mu'=\alpha\mu +(1-\alpha)\delta_e$ for a certain real $\alpha<1$ (here $\delta_e$ denotes the unit mass at the group identity), then $h(G,\mu)\le\alpha h(G,\mu)$, so that the asymptotic entropy must vanish (*Münchhausen trick*) proving amenability of the group $G$.

In the present paper we take a different approach based on the fact that the Mother group ${{\mathfrak M}}$ is generated by two finite subgroups $A$ and $B$. We take as measure $\mu$ the convolution product of the uniform measures $\mu_A$ and $\mu_B$ on these subgroups. Then the matrix $M^\mu$ has a very special form, so that the projection of the associated RWIDF $({{\mathfrak M}}\times X, M^\mu)$ to ${{\mathfrak M}}$ is just the random walk $({{\mathfrak M}},{\widetilde}\mu)$ determined by a new measure ${\widetilde}\mu$. The measure ${\widetilde}\mu$ is a convex combination of the idempotent measures $\mu_A$ and $\mu_B$, so that its convolution powers are essentially convex combinations of the convolution powers of $\mu$. We then compare the asymptotic entropies of $\mu$ and ${\widetilde}\mu$ and use the Münchhausen trick in order to deduce vanishing of the asymptotic entropy $h({{\mathfrak M}},\mu)$ and to apply [Theorem \[thm:entr\]]{}. Actually, we make this argument more explicit in order to obtain a lower estimate for the return profile of ${{\mathfrak M}}$.

Proof of [Theorem \[thm:amen\]]{}
---------------------------------

Let us consider on ${{\mathfrak M}}$ the probability measure $$\label{eq:mu}
\mu = \mu_A \mu_B \;,$$ where $\mu_A$ and $\mu_B$ are the uniform measures on the finite subgroups $A$ and $B$ from [Definition \[defn:mother\]]{}, respectively. Then the associated matrix $M^\mu$ is $$M^\mu = M^{\mu_A} M^{\mu_B} = E_d \begin{pmatrix} \mu_B & 0 \\ 0 & \mu_A E_{d-1}
\end{pmatrix} \;,$$ where $d=|X|$, and $E_d$ denotes the order $d$ matrix with entries $1/d$, so that $M^\mu$ has identical rows with entries $$M^\mu_{xy} =
  \begin{cases}
    \mu_B/d  &  \text{if $y=o$} \;, \\
    \mu_A/d  & \text{otherwise} \;.
  \end{cases}$$ It means that transition probabilities of the associated RWIDF $({{\mathfrak M}}\times X, M^\mu)$ do not depend on $x$, so that its projection to ${{\mathfrak M}}$ is just the random walk $({{\mathfrak M}},{\widetilde}\mu)$ determined by the measure $${\widetilde}\mu = \sum_y M^\mu_{xy} = \frac{d-1}{d} \mu_A + \frac{1}{d} \mu_B \;,$$ whereas the projection of RWIDF $({{\mathfrak M}}\times X, M^\mu)$ to $X$ is the sequence of independent $X$-valued random variables with uniform distribution on $X$ (because all entries $M^\mu_{xy}$ have mass $1/d$). Note that these two projections are *not* independent.

Let us now compare the entropies $$F(n) = H(\mu^n) \;,\qquad {\widetilde}F(n) = H({\widetilde}\mu^n)$$ of convolution powers of the measures $\mu$ and ${\widetilde}\mu$, respectively.

First suppose that we start the RWIDF $({{\mathfrak M}}\times X, M^\mu)$ at time $0$ from a point $(g,x)\in{{\mathfrak M}}\times X$. Then its time $n$ distribution is $R(M^\mu)^n$, where $R$ denotes the vector $(0,\dots,\delta_g,\dots,0)\in\ell_1(G)^X$ with $\delta_g$ at position $x$. By Scholium \[sch:A0\], the entropy of this distribution does not exceed the sum of the entropies of its projections to ${{\mathfrak M}}$ and to $X$. The projection of $R(M^\mu)^n$ to $X$ is uniform, so its entropy is $\log d$, whereas its projection to ${{\mathfrak M}}$ is ${\widetilde}\mu^n$. Therefore, the entropy of the row distribution $R(M^\mu)^n$ is at most ${\widetilde}F(n) + \log d$.

Now, the measure $\mu^n$ is the time $n$ distribution of the random walk $({{\mathfrak M}},\mu)$. As it was explained in [Section \[sec:ss\]]{}, this distribution can be identified with the time $n$ distribution of the corresponding random walk on the group ${{\mathsf{Sym}(X;{{\mathfrak M}})}}$. Again by Scholium \[sch:A0\], the entropy of the latter distribution of random matrices is at most the sum of the entropies of all the row distributions of these matrices. The distribution of the row parameterized by $x\in X$ is precisely $R(M^\mu)^n$ for the vector $R=(0,\dots,\delta_e,\dots,0)\in\ell_1(G)^X$ with $\delta_e$ at position $x$; so we have the inequality $$\label{eq:first}
F(n) \le d \cdot [ {\widetilde}F(n) + \log d ] = d {\widetilde}F(n) + d\log d \;.$$ Here we interpreted the RWIDF $({{\mathfrak M}}\times X, M^\mu)$ as a “row chain” and used the fact that the amount of information about a random matrix does not exceed the sum of amounts of information about its rows.

Our next step will be to obtain a bound in the opposite direction which will ultimately lead to vanishing of the asymptotic entropy $h({{\mathfrak M}},\mu)=\lim
F(n)/n$. Since the measures $\mu_A,\mu_B$ are idempotent, the convolution power $$\label{eq:Hmu^n}
{\widetilde}\mu^n = \left( \frac{d-1}{d} \mu_A + \frac{1}{d} \mu_B \right)^n = \sum_{i=1}^n
p_{A,i} \mu_{A,i} + \sum_{i=1}^n p_{B,i} \mu_{B,i}$$ is a convex combination of the alternating convolution products $\mu_{A,i}=\mu_A\mu_B\dots$ (respectively $\mu_{B, i}=\mu_B\mu_A\dots$) of length $i\le n$ of the measures $\mu_A$ and $\mu_B$. The probability distribution $(p_{A, i}, p_{B,
i})$ admits a simple interpretation in terms of the sequence of Bernoulli random variables $(\xi_k)$ with distribution $${{\mathbf P}}\{\xi_i=A\}=\frac{d-1}d \;, \quad {{\mathbf P}}\{\xi_i=B\}=\frac1d \;.$$ Namely, $p_{A,i}$ (respectively $p_{B,i}$) is the probability that $\xi_1=A$ (respectively $\xi_1=B$) and the sequence $\xi_1,\xi_2,\dots,\xi_n$ contains precisely $i$ series consisting of repetitions of the same symbol (or, equivalently, that there are precisely $i-1$ *switch times* $t$ such that $\xi_t\neq\xi_{t+1}$ with $1\le t\le n-1$). Clearly, the probability that any given $t$ is a switch time is $\ell=2(d-1)/d^2$, whence the expectation of the amalgamated distribution $p_i = p_{A, i}+p_{B, i}$ is $(n-1)\ell+1$. By using it is easy to see that $$H(\mu_{A, i}), H(\mu_{B, i}) \le F( \lfloor i/2\rfloor + 1) \qquad \text{for
all}\; i\in\{1, \ldots, n\},$$ where $\lfloor\cdot\rfloor$ denotes the integer part (for example, if $i$ is even then $H(\mu_{B,i})\le H(\mu_A \mu_{B,i}\mu_B) = H(\mu_{A,i+2}) = F(i/2+1)$). Then from and we get $${\widetilde}F(n) \le \sum p_i F(\lfloor i/2\rfloor+1) + \log(2n) \;.$$ By applying the Chebyshev inequality to the distribution $p$ (one can check directly that its variance is linear as a function of $n$) and using the fact that the function $F$ is monotone and subadditive (so that its values for all integers up to $n/2$ are controlled from above just by its value at $\left\lfloor\textstyle\frac{d-1}{d^2}n\right\rfloor$), we obtain that for any $\epsilon>0$ and all sufficiently large $n$ $$\label{eq:Htil}
{\widetilde}F(n) \le
F\left(\left\lfloor\left(\textstyle\frac{d-1}{d^2}+\epsilon\right)n\right\rfloor\right)
+ \log(2n).$$ Inequalities and imply, after dividing by $n$ and passing to the limit, the corresponding inequalities for the asymptotic entropies of the measures $\mu$ and ${\widetilde}\mu$: $$h({{\mathfrak M}},\mu) \le d\, h({{\mathfrak M}},{\widetilde}\mu) \;,\qquad h({{\mathfrak M}},{\widetilde}\mu) \le
\textstyle\frac{d-1}{d^2}\, h({{\mathfrak M}},\mu) \;,$$ whence $h({{\mathfrak M}},\mu)\le\frac{d-1}{d}h({{\mathfrak M}},\mu)$, so that $h({{\mathfrak M}},\mu)=0$, and the group ${{\mathfrak M}}$ is amenable by [Theorem \[thm:entr\]]{}.

Triviality of the Poisson boundary of the measure $\mu$ implies that the convolution powers $\mu^n$ satisfy the *Reiter condition* of strong convergence to left-invariance, i.e., $\|g\mu^n-\mu^n\|\to 0$ for any $g\in{{\mathfrak M}}$ [@Kaimanovich-Vershik83]. Moreover, the reflected measure ${\check}\mu=\mu_B \mu_A$ (defined by ${\check}\mu(g)=\mu(g^{-1})$) has the same asymptotic entropy as $\mu$, so that $h({{\mathfrak M}},{\check}\mu)$ also vanishes, and the convolution powers ${\check}\mu^n$ also satisfy the Reiter condition. This fact easily implies that for any probability measure $\mu'$ (other than convex combinations of $\mu_A$ or $\mu_B$ with $\delta_e$) from the $\ell^1$-closure of the algebra generated by the measures $\mu_A$ and $\mu_B$ its convolution powers satisfy the Reiter condition, and therefore the Poisson boundary of $\mu'$ is trivial. Are there any measures on ${{\mathfrak M}}$ with a non-trivial Poisson boundary?

Explicit estimates
------------------

Inequalities and imply that for any $\varepsilon>0$ the sequence of entropies ${\widetilde}F(n)$ of the *symmetric* measure ${\widetilde}\mu$ satisfies the inequality $$\label{eq:phi}
{\widetilde}F(n) \le d\, {\widetilde}F\left(\left\lfloor\left(\textstyle\frac{d-1}{d^2}+\epsilon\right)n\right\rfloor\right)
+d\log d + \log(2n)$$ for all sufficiently large $n$. Roughly speaking, the multiplication of the argument by $\textstyle\frac{d^2}{d-1}>d$ leads to the multiplication of the value of ${\widetilde}F$ by at most $d$.

We shall consider the partial order ${\preccurlyeq}$ on the set of positive functions on $\mathbb R_+$ defined by $f_1{\preccurlyeq}f_2$ if $f_1(t) \le Cf_2(at)$ for certain constants $a,C>0$, and say that two functions $f_1,f_2$ are *equivalent* (written $f_1\sim f_2$) if $f_1{\preccurlyeq}f_2$ and $f_2{\preccurlyeq}f_1$. Inequality implies then

\[pr:entr\] For any $\varepsilon>0$ $${\widetilde}F(n){\preccurlyeq}n^{\alpha+\varepsilon} \;,$$ where $$\label{eq:al}
\alpha=\frac{\log d}{\log \textstyle\frac{d^2}{d-1}} < 1 \;.$$

Recall that the *return profile* $\rho_\mu(n)=\mu_{2n}(e)$ of a symmetric probability measure $\mu$ on a countable group $G$ is defined as the sequence of return probabilities to the identity at even times. If the group is finitely generated then the return profiles of any two symmetric finitely supported non-degenerate measures $\mu_1,\mu_2$ are equivalent in the sense of the above definition [@Pittet-Saloff99a]. Therefore, one can talk about (the equivalence class of) the return profile $\rho_G$ of a finitely generated group $G$ irrespectively of a concrete random walk on this group.

The *isoperimetric profile* of a graph $\Gamma$ is defined as $$I_\Gamma (n) = \min \{|V| : |\partial V|/|V| \le 1/n\} \;,$$ where $\partial V\subset V$ denotes the boundary of a finite vertex subset $V\subset\Gamma$. In the same way as with the return profiles (actually, it is much easier to see in this case), the isoperimetric profiles of the Cayley graphs of a given finitely generated group $G$ corresponding to different choices of generating sets are all pairwise equivalent, so that one can talk about (the equivalence class of) the isoperimetric profile $I_G$ of a finitely generated group $G$.

\[th:profile\] The return and the isoperimetric profiles, respectively, of the Mother group ${{\mathfrak M}}={{\mathfrak M}}(X)$ with $|X|=d$ satisfy, for any $\varepsilon>0$, the relations $$\rho_{{\mathfrak M}}(n) \succcurlyeq \exp\left(-n^{\alpha+\varepsilon}\right) \qquad
\text{and} \qquad I_{{\mathfrak M}}(n) {\preccurlyeq}\exp\left(n^{\frac{2\alpha}{1-\alpha}+\varepsilon}\right) \;,$$ where $\alpha$ is given by formula .

[Proposition \[pr:entr\]]{} in combination with the well-known inequality ${\widetilde}\mu_{2n}(e) \ge \exp(-2H({\widetilde}\mu^n))$ immediately implies the lower estimate for the return profile. By the general Nash inequality machinery (see [@Grigoryan94; @Coulhon96] or a later exposition in [@Woess00 Corollary 14.5(b)]) it leads to the upper estimate for the isoperimetric profile.

We emphasize that our argument provides an upper estimate for the isoperimetric profile of the Mother groups without producing explicit Følner sets. Finding them should apparently precede any work on establishing the precise isoperimetric profiles for these groups.

It is interesting to compare the estimates from [Theorem \[th:profile\]]{} with the precise return and isoperimetric profiles of the *lamplighter groups* ${{\mathfrak L}}_k = {\mathbb{Z}}/2\wr{\mathbb{Z}}^k = ({\mathbb{Z}}/2)^{{\mathbb{Z}}^k}\rtimes{\mathbb{Z}}^k$, $$\rho_{{{\mathfrak L}}_k}(n) \sim \exp\left(-n^{\alpha_k}\right) \qquad \text{and} \qquad
I_{{{\mathfrak L}}_k}(n) \sim \exp\left(n^{\frac{2\alpha_k}{1-\alpha_k}}\right) \;,$$ where $\alpha_k=k/(k+2)$, which were found in [@Pittet-Saloff99a] (also see [@Erschler06]) and [@Erschler03], respectively.

We shall now combine [Theorem \[th:profile\]]{} with [Theorem \[thm:reduc\]]{} in order to obtain similar estimates for an arbitrary finitely generated subgroup $G$ of ${{\mathfrak{BA}}}(X)$. Let us first notice that the return profile $\rho_{{{\mathfrak M}}(X)^d}=\rho^d_{{{\mathfrak M}}(X)}$ of the $d$-th power of the Mother group also satisfies the inequality from [Theorem \[th:profile\]]{}. Since the return profile does not change when passing to a finite extension (see [@Pittet-Saloff99a]), the return profile of the wreath product ${{\mathfrak M}}(X)\wr{{\mathsf{Sym}(X)}}$ satisfies this inequality as well. Further, by the monotonicity of the return profile under passing to subgroups [@Pittet-Saloff00], the same inequality from [Theorem \[th:profile\]]{} is also satisfied for the return profile of an arbitrary finitely generated subgroup of ${{\mathfrak M}}(X)\wr{{\mathsf{Sym}(X)}}$. The corresponding inequality for the isoperimetric profile follows from the inequality for the return profile in the same way as in the proof of [Theorem \[th:profile\]]{}. [Theorem \[thm:reduc\]]{} then implies

Let $G$ be a finitely generated subgroup of ${{\mathfrak{BA}}}(X)$, and let $N=N(G)$ be as in [Theorem \[thm:reduc\]]{}. Then the return and the isoperimetric profiles, respectively, of the group $G$ satisfy, for any $\varepsilon>0$, the relations $$\rho_G(n) \succcurlyeq \exp\left(-n^{\alpha+\varepsilon}\right) \qquad
\text{and} \qquad I_G(n) {\preccurlyeq}\exp\left(n^{\frac{2\alpha}{1-\alpha}+\varepsilon}\right) \;,$$ where $$\alpha=\frac{\log d^N}{\log \textstyle\frac{d^{2N}}{d^N-1}} < 1 \;.$$

Entropy inequalities {#sec:app}
====================

The *entropy* of a discrete probability distribution $p=(p_i)$ is defined as $$H(p) = - \sum p_i \log p_i \;,$$ and it satisfies the inequality $$H(p) \le \log |{\operatorname{\mathsf{supp}}}p\,|$$ if $p$ has finite support.

Although all the properties of the entropy which we need (Scholium \[sch:A0\], [Lemma \[lem:A1\]]{} and [Lemma \[lem:A2\]]{}) could in principle be deduced just from the definition above, it is more convenient to adopt a more general point of view and argue in terms of the *entropy of measurable partitions*. See [@Rohlin67] for all the background notions and definitions.

Let $(X,m)$ be a probability measure space, and $\xi=\{\xi_i\}$ be its countable *measurable partition*, so that $X=\bigcup_i \xi_i$ is a disjoint union of the measurable *elements* $\xi_i$ of the partition $\xi$. We shall denote by $\xi(x)$ the element of $\xi$ which contains a point $x\in X$, and put $$m(x;\xi) = m(\xi(x)) \;.$$ Then the *entropy* of the partition $\xi$ is defined as the entropy of the distribution of measures of its elements, i.e., $$H(\xi) = - \sum_{C\in\xi} m (C) \log m(C) = - \int_X \log
m(x;\xi)\,dm(x) \;.$$ The entropy of partitions is monotone in the sense that if $\xi'$ is another partition finer than $\xi$, i.e., its elements are smaller: $$\xi'(x)\subset\xi(x) \text{\ for all\ }x\in X,$$ then $$\label{eq:Hmonot}
H(\xi') \ge H(\xi) \;.$$ Given a measurable subset $C\subset X$ denote by $m_C$ the corresponding *conditional measure*, i.e., the normalized restriction of the measure $m$ to $C$, and let $\xi_C$ denote the *trace* of the partition $\xi$ on the space $(C,m_C)$, i.e., $\xi_C(x) = \xi(x) \cap C$ for any $x\in C$.

If $\zeta$ is another countable partition, set $$m(x;\xi|\zeta) = m_{\zeta(x)} (x; \xi_{\zeta(x)}) = m( \xi(x) \cap
\zeta(x) ) / m(\zeta(x)) \;.$$ Then the (mean) conditional entropy of $\xi$ with respect to $\zeta$ is defined as the weighted average of the entropies of the traces of $\xi$ on the elements of $\zeta$: $$H(\xi|\zeta) = \sum_{C\in\zeta} m(C) H(\xi_C) = - \int_X \log
m(x;\xi|\zeta)\,dm(x) \;.$$ The conditional entropy has the property that $$H(\xi|\zeta) \le H(\xi) \;,$$ and it satisfies the identity $$H(\xi|\zeta) + H(\zeta) = H(\xi \vee \zeta) \;,$$ where $\xi\vee\zeta$ is the *join* of the partitions $\xi$ and $\zeta$, i.e., $$(\xi\vee\zeta)(x) = \xi(x) \cap \zeta(x) \qquad \text{for all\
}x\in X,$$ so that in view of $$\label{eq:Hineq}
H(\xi|\zeta) \le H(\xi) \le H(\xi|\zeta) + H(\zeta) = H(\xi \vee \zeta) \le
H(\xi) + H(\zeta) \;.$$ We reformulate the right-hand side inequality of  as a

\[sch:A0\] If $m$ is a probability measure on a countable set $X$, and $\pi_i:X\to X_i$ is a family of projections of $X$ which separates its points, then the entropies of $m$ and the image measures $m_i=\pi_i(m)$ satisfy the inequality $$H(m)\le\sum_i H(m_i).$$

We shall now use inequalities to obtain the following properties.

\[lem:A1\] If $\{m_i\}_{i\in I}$ is a countable family of probability measures on a countable set $X$, then for any probability distribution $p=(p_i)$ on the index set $I$ the entropy of the convex combination $\sum p_i m_i$ satisfies the inequalities $$\label{eq:entrineq}
\sum_i p_i H(m_i) \le H\left(\sum_i p_i m_i \right) \le \sum_i p_i
H(m_i) + H(p) \;.$$

Let us consider the space $I\times X$ with the probability measure $$m(i,x) = p(i) m_i(x) \;,$$ and endow it with the partitions $\xi^I,\xi^X$ with elements $\{i\}\times X$ and $I\times \{x\}$, respectively. Then $$H(\xi^X) = H\left(\sum_i p_i m_i \right) \;, \qquad H(\xi^X|\xi^I)
= \sum_i p_i H(m_i) \;, \qquad H(\xi^I) = H(p) \;,$$ and the claim follows from inequalities .

\[lem:A2\] For any two probability measures $\mu_1,\mu_2$ on a countable group $G$ the entropy of their convolution $\mu_1\mu_2$ satisfies the inequalities $$\label{eq:conv}
H(\mu_1), H(\mu_2) \le H(\mu_1\mu_2) \le H(\mu_1) + H(\mu_2) \;.$$

By the definition of the convolution, the measure $\mu_1\mu_2$ is the sum of the translates $$\mu_1\mu_2 = \sum_g \mu_2(g)\,  \mu_1 g  \;,$$ and the inequalities $H(\mu_1) \le H(\mu_1\mu_2) \le H(\mu_1) + H(\mu_2)$ follow from putting $p_g=\mu_2(g)$ and $m_g=\mu_1 g$ in Lemma \[lem:A1\]. In the same way one shows that $H(\mu_2)\le H(\mu_1\mu_2)$.
