Groups of intermediate growth
Laurent Bartholdi
I describe a class of groups acting on rooted trees that all have intermediate word growth between polynomial and exponential. The argument constructs a functional equation on the growth formal power series, and derives the growth properties from its analytical behaviour. This places under a unified proof all known or conjectured examples of such groups, and answers a few open questions by Rostislav Grigorchuk. I then sketch some algebraic results enjoyed by this class of groups, and list what seem promising open questions and further directions.
interm.tex
\documentclass{amsart}
\usepackage{math,epsfig,psfrag}

\begin{document}
\title{Groups of intermediate growth}
\author{Laurent Bartholdi}
\date\today
\email{laurent@math.berkeley.edu}
\address{Department of Mathematics, 970 Evans Hall, CA94720-3840
  Berkeley, USA}
\thanks{The author acknowledges support from the ``Swiss National Fund
  for Scientific Research'', stipend \#83R-063208}
\keywords{intermediate growth; growth of groups; tree automorphisms}
\subjclass{
  \textbf{20E08} (Groups acting on trees),
  \textbf{20F32} (Geometric group theory)}
\begin{abstract}
  I describe a class of groups acting on rooted trees that all have
  intermediate word growth between polynomial and exponential.

  The argument constructs a functional equation on the growth formal
  power series, and derives the growth properties from its analytical
  behaviour.

  This places under a unified proof all known or conjectured examples
  of such groups, and answers a few open questions by Rostislav
  Grigorchuk.
  
  I then sketch some algebraic results enjoyed by this class of
  groups, and list what seem promising open questions and further
  directions.
\end{abstract}
\maketitle

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Introduction}
Let $G$ be a group, finitely generated by a set $S$. The \emph{word
  norm} on $G$ is the norm
\begin{equation}\label{eq:metric}
  \|g\|=\min\setsuch{n\in\N}{g=s_1\dots s_n\text{ for some }s_i\in S}.
\end{equation}
The \emph{growth function} of $G$ is the function
$\gamma(n)=\#\setsuch{g\in G}{\|g\|\le n}$, measuring the growth of
the volume of balls in the metric space $G$.

Say two functions $\gamma,\delta$ are equivalent if
$\gamma(n)\le\delta(Cn)$ and $\delta(n)\le\gamma(Cn)$ for some large
enough $C\in\N$. Then although $\gamma$ depends both on $G$ and $S$,
its equivalence class depends only on $G$.

This notion of growth was introduced in the 1950's in the
USSR~\cite{svarts:growth} and in the 1960's in the
West~\cite{milnor:solvable}, in relation with properties of Riemannian
manifolds and coverings : assume $G$ is the fundamental group of a
compact metrized $CW$-complex $K$. Then the growth function of $G$
measures the growth of balls in the universal cover $\tilde K$.

If $\gamma$ is dominated by a polynomial function, i.e.\ $\gamma(n)\le
Cn^D$ for some $C,D\in\N$, then $G$ is of \emph{polynomial growth}.
This happens when $G$ is free abelian (indeed then $\tilde K$ is
Euclidean space), and more generally when $G$ has a nilpotent subgroup
of finite index, as was observed by John Milnor~\cite{milnor:solvable}
and Joseph Wolf~\cite{wolf:solvable}. Mikhail Gromov proved conversely
that these are the only examples~\cite{gromov:nilpotent}.

In the other end of the spectrum, if $\gamma(n)\ge C^n$ for some
$C>1$, then $G$ is of \emph{exponential growth}. Clearly, one must have
$C\le\#S$. This happens e.g.\ when $G$ is non-virtually-nilpotent
linear~\cite{tits:linear} or non-elementary
hyperbolic~\cite{ghys-h:gromov}.

John Milnor asked in 1968~\cite{milnor:5603} whether there exist
finitely generated groups of \emph{intermediate growth}, i.e.\ with
growth greater than polynomial but less than exponential. The first
example of such a group was discovered in 1978 by Rostislav
Grigorchuk~\cite{grigorchuk:growth,grigorchuk:kyoto}.  He
later constructed a continuum of groups of intermediate
growth~\cite{grigorchuk:gdegree}, and showed that the growth
functions $\gamma$ of all these groups satisfy
\[e^{\sqrt{n}}\precsim\gamma(n)\not\sim e^n;\]
he also showed that the growth function of his main example, the
``first Grigorchuk group''~\cite[Chapter~VIII]{harpe:ggt}, satisfies
\[\gamma(n)\precsim e^{n^\beta},\qquad \beta=\log_{32}(31)\approx0.991.\]

I have improved the upper~\cite{bartholdi:upperbd} and
lower~\cite{bartholdi:lowerbd} bounds of this group to
\[e^{n^{0.5157}}\precsim\gamma(n)\precsim e^{n^{0.7675}};\]
and have obtained with Zoran \v Suni\'k~\cite{bartholdi-s:wpg} upper
and lower bounds for the continuum of Grigorchuk groups.

The Grigorchuk groups are, under a very small condition, infinite
torsion groups. A similar construction of infinite torsion groups was
proposed by Narain Gupta and Said
Sidki~\cite{gupta-s:burnside,gupta-s:infinitep}, and the natural
question as to whether these groups are also of intermediate growth
has been long open. I address it in this paper by the following
result:
\subsection*{Data} Let $\Sigma=\{1,\dots,d\}$ be a finite set; the set
$\Sigma^*$ of finite sequences over $\Sigma$ is naturally (the vertex
set of) a $d$-regular rooted tree, rooted at the empty sequence, if
one connects for all $\sigma_i\in\Sigma$ the vertices
$\sigma_1\dots\sigma_n$ and $\sigma_1\dots\sigma_n\sigma_{n+1}$.

Let $A$ be a subgroup of the symmetric group of $\Sigma$; let $B$ be a
finite group, and let $\tilde B=B_1\times B_2\times\dots$ be the
direct product of countably many copies of $B$; let
$\phi_1,\dots,\phi_{d-1}$ be homomorphisms $\tilde B\to A$, and let
$\phi_d:\tilde B\to\tilde B$ be the one-sided shift
$(b_1,b_2,\dots)\mapsto(1,b_1,b_2,\dots)$. Write $\phi_i^n$ for the
restriction of $\phi_i$ to $B_n$.

\subsection*{Action} $A$ and $\tilde B$ act on $\Sigma^*$ as follows:
the action of $a\in A$ is
\[(\sigma_1\sigma_2\dots\sigma_n)^a=(\sigma_1)^a\sigma_2\dots\sigma_n,\]
and the action of $\tilde b\in\tilde B$ is defined inductively by
$()^{\tilde b}=()$ and
\[(\sigma_1\sigma_2\dots\sigma_n)^{\tilde
  b}=\sigma_1(\sigma_2\dots\sigma_n)^{\phi_{\sigma_1}(\tilde b)}.\]
%\[(d\dots d\sigma_m\sigma_{m+1}\dots\sigma_n)^b=d\dots d\sigma_m(\sigma_{m+1}\dots\sigma_n)^{\phi^m_{\sigma_m}(b)}.\]
Let $G$ be the subgroup of $\aut\Sigma^*$ generated by $A$ and $B_1$,
i.e.\ the largest quotient of $A*B_1$ that acts faithfully on
$\Sigma^*$. Such a group $G$ is called a \emph{splitter-mixer group},
since its action is two-step: the $\tilde b$'s ``split'' in actions of
$a$'s, and the actions of $a$'s ``mix'' the subtrees below them.

\begin{thm}\label{thm:main}
  Let $G$ be a splitter-mixer group as defined above. Then
  \begin{enumerate}
  \item $G$ has subexponential growth;
  \item assume that $A$ acts transitively on $\Sigma$; that for all
    $1\neq b\in B$ there exists infinitely many
    $(n,i)\in\N\times\{1,\dots,d-1\}$ with $\phi_i^n(b)\neq1$; and
    that $\langle \phi_1^n(B),\dots,\phi_{d-1}^n(B)\rangle=A$ for all
    $n\in\N$. Then $G$ has superpolynomial growth, unless $A=1$ or
    $A=B=\Z/2$.
  \end{enumerate}
\end{thm}
The description of groups of intermediate growth followed a long
evolution. They were first described as transformations of the
interval $[0,1]$, and only later as permutations of a rooted tree,
finally presented algebraically as $\Sigma^*$.

Theorem~\ref{thm:main} proves that the following groups have
intermediate growth:
\begin{description}
\item[The first Grigorchuk group] It is obtained by taking
  $\Sigma=\{1,2\}$; $A=\{1,a=(1,2)\}$; $B=A\times A=\{1,b,c,d\}$; and
  \[\phi_1^n(b)=\phi_1^{n-1}(c)=\phi_1^{n-2}(d)=\begin{cases}
    1 & \text{ if }n\equiv0\mod 3,\\
    a & \text{ else.}\end{cases}\]
\item[The ``Grigorchuk Overgroup''] It is obtained by taking
  $\Sigma=\{1,2\}$; $A=\{1,a=(1,2)\}$; $B=A^3=\langle\tilde b,\tilde
  c,\tilde d\rangle$; and
  \[\phi_1^n(\tilde b)=\phi_1^{n-1}(\tilde c)=\phi_1^{n-2}(\tilde d)=\begin{cases}
    a & \text{ if }n\equiv1\mod 3,\\
    1 & \text{ else.}\end{cases}\]
  Note that this group $\tilde G$ contains the first Grigorchuk group
    as the subgroup $\langle a,\tilde b\tilde c,\tilde b\tilde
    d,\tilde c\tilde d\rangle$. The growth of $\tilde G$ is shown to
    be exponential in~\cite{bartholdi-g:parabolic}.
\item[The Grigorchuk groups $\mathbf{G_\omega}$] These groups form an
  uncountable family described in~\cite{grigorchuk:gdegree}, indexed
  by $\omega\in\{X,Y,Z\}^\N$. They are obtained by taking
  $\Sigma=\{1,2\}$; $A=\{1,a\}$; $B=A\times A$; and
  $\phi_1^n=\omega_n$, if one interprets $X,Y,Z$ as the three
  non-trivial homomorphisms $B\to A$.
  
  Grigorchuk proves in~\cite{grigorchuk:gdegree} that if every letter
  appears infinitely often in $\omega$, then $G_\omega$ is an infinite
  torsion group of intermediate growth.
\item[The Gupta-Sidki group] It is obtained by taking
  $\Sigma=\{1,2,3\}$, $A=\langle x=(1,2,3)\rangle$; $B=A$; and
  $\phi_1^n(x)=\phi_2^n(x^{-1})=x$.
\item[The Gupta-Sidki $p$-groups] They are defined
  in~\cite{gupta-s:burnside}, and in our setting are obtained by
  taking $\Sigma=\{1,2,\dots,p\}$ for $p\ge3$, $A=\langle
  x=(1,2,\dots,p)\rangle$, $B=A$, and
  $\phi_1^n(x)=\phi_2^n(x^{-1})=x$,
  $\phi_3^n(x)=\dots=\phi_{p-1}^n(x)=1$. These groups are infinite
  $p$-torsion groups for all $p$.
\item[The Gupta-Fabrykowski group] It is obtained by taking
  $\Sigma=\{1,2,3\}$, $A=\langle x=(1,2,3)\rangle$; $B=A$; and
  $\phi_1^n(x)=\phi_2^n(x)=x$. This group was announced to be of
  intermediate growth in~\cite{fabrykowski-g:growth1}, but the
  arguments presented failed to convince, and were improved
  in~\cite{fabrykowski-g:growth2}.
\item[The ``Spinal groups''] These groups were first introduced
  in~\cite{gupta-s:ext} where they were given with a condition for
  torsion. They were rediscovered in~\cite{bartholdi-s:wpg} with a
  condition for word and period growth. In the present setting, they
  amount to imposing $\phi^n_2=\dots=\phi^n_{d-1}(b)=1$, and the
  condition that for all $b\in B$, we have $\phi^n_1(b)=1$ for
  infinitely many $n$. Note that in compensation for these
  restrictions some quantitative growth estimates are obtained.
\item[The ``Square group''] It is an example proposed by Grigorchuk,
  who stated its growth as an interesting open question. One takes
  $\Sigma=\{1,2,3,4\}$, $A=\langle x=(1,2,3,4)\rangle$; $B=A$; and
  $\phi_1^n(x)=x$, $\phi_2^n(x)=1$, $\phi_3^n(x)=x^{-1}$.
\end{description}

The paper is organized as follows: Section~\ref{sec:growth} recalls
notions on growth of groups. Section~\ref{sec:subexp}
and~\ref{sec:superpol} prove respectively the first and second part of
Theorem~\ref{thm:main}.  Section~\ref{sec:distr} describes the
distribution of the projections for some examples of splitter-mixer
groups, Section~\ref{sec:algebra} gives some algebraic properties of
splitter-mixer groups (torsion, branchness), and
Section~\ref{sec:final} closes with some remarks and open questions.

The emphasis of this paper is on growth; a future paper will study
more deeply the algebraic nature of the groups introduced here.

This work was initiated when I was a PhD student of Professor Pierre
de la Harpe in the University in Geneva. I thank Pierre heartily for
everything he has taught me during those years.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Growth}\label{sec:growth}
Let $G$ be a group, finitely generated as a monoid by a set $S$. The
word norm~\eqref{eq:metric} gives rise to the growth function
$\gamma(n)=\#\setsuch{g\in G}{\|g\|\le n}$, conveniently studied
through its \emph{growth series}, the generating function
\[\Gamma(z)=\sum_{g\in
  G}z^{\|g\|}=(1-z)\sum_{n\ge0}\gamma(n)z^n.\] This power
series has been extensively studied, in particular when viewed as an
analytic function in the ball of radius $1/\#S$. If $G$ is virtually
abelian~\cite{benson:zn}, hyperbolic~\cite[Chapter~9]{ghys-h:gromov},
or a Coxeter group~\cite{parry:salem}, then $\Gamma$ is a rational
function of $z$. If $G$ is the Heisenberg group $G=\langle
x,y|\,[x,y]\text{ central}\rangle$, its growth series is also
rational~\cite{shapiro:n2}. There are other nilpotent groups whose
growth series is rational for some generating sets and irrational for
others~\cite{stoll:heisenberg}; the same phenomenon occurs for other
cyclic fiber groups~\cite{shapiro:psl2r}.

Note that if $G$ is finite, then $\Gamma$ is a polynomial; otherwise,
the convergence radius of $\Gamma$ is at least $1/(\#S-1)$, and at
most $1$. The following is a formulation of the root test:
\begin{lem}\label{lem:diskconv}
  $G$ has subexponential growth if and only if $\Gamma$ converges in
  the unit disk.
\end{lem}

The following result is due to Pierre Fatou and Fritz Carlson:
\begin{lem}[\cite{fatou:series}, page~368; \cite{carlson:potenzreihen}]
  \label{lem:fatou}
  If $\Gamma$ is a formal power series with integer coefficients,
  converging in the unit disk, then $\Gamma$ is either rational or
  transcendental; in the latter case, it has the unit disk as natural
  boundary.
\end{lem}

\begin{cor}
  If $G$ has intermediate growth, then $\Gamma$ is a transcendental
  function.
\end{cor}
\begin{proof}
  By Lemmata~\ref{lem:fatou} and~\ref{lem:diskconv}, $\Gamma$ is
  either rational or transcendental. If $\Gamma$ were rational, it
  would have finitely many singularities on the unit circle, and each
  of them would be of pole type $f(z)=(z-\omega)^{-D}$. Then $G$ would
  have polynomial growth, of degree $D+1$ for the largest such $D$.
\end{proof}

\begin{lem}\label{lem:oint}
  Let $a_n,b_n,c_n$ be real sequences related by the equation
  \[c_n=\sum_{i+j=n}\binom nia_ib_j.\]
  Let $\Gamma_a,\Gamma_b,\Gamma_c$ be the related generating series
  $\Gamma_a=\sum_{n\ge0}a_nz^n$, etc. Then for all $\epsilon>0$ we have
  \[\Gamma_c(z)=\frac1{2i\pi}\oint_{|w|=\epsilon}\Gamma_a\big((1+w)z\big)\Gamma_b\big((1+w^{-1})z\big)\frac{dw}{w}.\]
  In consequence, if $\Gamma_a$ and $\Gamma_b$ respectively have
  radius of convergence $1/\alpha$ and $1/\beta$, then $\Gamma_c$ has
  radius of convergence at least $1/(\alpha+\beta)$.
\end{lem}
\begin{proof}
  By linearity, it suffices to check the formula for
  $\Gamma_a(z)=z^i$ and $\Gamma_b(z)=z^j$. Then
  \[\Gamma_c(z)=\frac{z^{i+j}}{2i\pi}\oint_{|w|=\epsilon}(1+w)^i(1+w^{-1})^j\frac{dw}{w}=\binom{i+j}{j}z^{i+j},\]
  by the Cauchy residue formula.

  Next, consider the integral on the circle
  $|w|=\epsilon=\beta/\alpha$. If $|z|<1/(\alpha+\beta)$, then
  $|(1+w)z|<1/\alpha$ and $|(1+w^{-1})z|<1/\beta$, so the
  integral converges uniformly.
\end{proof}

\begin{cor}\label{cor:oint}
  Let $\eta>0$ be fixed, and assume the real sequences $a_n,b_n,c_n$
  are related by the equation\footnote{The binomial coefficients are
    evaluated on non-integers by the formula $\binom
    nm=\Gamma(n+1)/\Gamma(m+1)\Gamma(n-m)$.}
  \[c_n=\sum_{i+j=n}\eta\binom{\eta n}{\eta i}a_ib_j.\]
  Let $\Gamma_a,\Gamma_b,\Gamma_c$ be the related generating series
  $\Gamma_a=\sum_{n\ge0}a_nz^n$, etc., with radius of convergence
  $1/\alpha,1/\beta,1/\gamma$. Then
  \[\gamma\ge\left(\alpha^{-1/\eta}+\beta^{-1/\eta}\right)^{-\eta}.\]
\end{cor}
\begin{proof}
  Consider the associated series $\Delta_a=\sum_{n\ge0}a_nz^{\lfloor\eta
  n\rfloor}$, etc.; then the radius of convergence of $\Delta_a$ is
  $\alpha^{1/\eta}$, etc., and the power series
  $\Delta_a,\Delta_b,\Delta_c$ satisfy the hypotheses of the previous
  Lemma.
\end{proof}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Subexponential growth}\label{sec:subexp}
Let $A$, $\tilde B=B_1\times\dots$ and $\phi_i^k$ be as in
Theorem~\ref{thm:main}. For $k\in\N$, define $G_k$ as the subgroup of
$\aut\Sigma^*$ generated by $A$ and $B_k$. In particular, $G=G_1$, and
we will show that all $G_k$'s have subexponential growth.

As generating set $S_k$ of $G_k$, we choose all symbols $s_{a,b,a'}$
with $a,a'\in A$ and $b\in B_k$.  There is an obvious cancellation
among these generators:
\[s_{a,b,a'}s_{a'',b',a'''}=s_{a,bb',a'''}\text{ if }a'a''=1,\]
and that is the only one that we shall use.

Given $w\in S_{k-1}^*$, we may uniquely write $w$ as an expression
$[w_1,\dots,w_d]a$, for some $a\in A$ and $w_1,\dots,w_d\in S_k^*$, as
follows:
\begin{itemize}
\item first rewrite $w=s_{a'_1,b_1,a''_1}\dots s_{a'_n,b_n,a''_n}$ as
  a word $w=b_1^{a_1}\dots b_n^{a_n}a$, by setting $a_i=a'_1a''_1\dots
  a'_i$ for all $i$;
\item then rewrite each $b_i^{a_i}$ as
  $[\phi_{1^{a_i}}^{k-1}(b_i),\dots,\phi_{d^{a_i}}^{k-1}(b_i)]$, and
  multiply coordinate-wise;
\item finally multiply out all consecutive elements of $A$, and
  rewrite each coordinate $w_i=a_1b_1\dots a_nb_na_{n+1}$ as
  $s_{a_1,b_1,1}\dots s_{a_n,b_n,a_{n+1}}$.
\end{itemize}
We insist that cancellations of the form
$s_{a,b,a'}s_{(a')^{-1},b^{-1},a''}=aa''$ are \underline{never} to be
performed; the maximal cancellation is $s_{a,1,a''}$. We call the
expression $[w_1,\dots,w_d]a$ the \emph{decomposition} of $w$.

Our choice of generators has the following interpretation: the
\emph{length} of an element $g\in G_k$ is the minimal number of
$B$-generators needed to express $g$. The total length of the $w_i$ is
the length of $w$ minus the number of cancellations performed.

Fix an integer $n$, and consider a random word of length $n$. We say
it has \emph{uniform distribution} if all its $B$-symbols are uniform,
independent variables in $B$, and all its $A$-symbols are non-trivial.
\begin{lem}\label{lem:uniform}
  Let $w$ be uniform of length $n$, and let $[w_1,\dots,w_d]a$ be its
  decomposition. Then each $w_i$ is uniform.
\end{lem}
\begin{proof}
  Each $w_i$ is a sequence of $B$-letters separated by strings of
  $A$-letters, and each of these letters is the $\phi$-image of a
  uniformly distributed $B$-letter.
  
  The $A$-letters are combined together by cancellation; but thanks to
  our assumption that trivial $B$-letters are not cancelled, the
  different strings of $A$-letters (which need not be uniform) never
  combine, so remain separated by products of uniform $B$-letters,
  which are again uniform.
\end{proof}

We now wish to estimate the cancellation that occurs in the
decomposition of $w$. In the strings of $A$-letters comprising $w_i$,
each is the $\phi$-image of a uniform $B$-letter. It follows that each
such $A$-letter has probability at least $1/\#A$ of being trivial, in
which case a cancellation occurs; unless it is the first or last
letter, which does not contribute to the length of $w_i$. Therefore if
$w_i$ had length $n_i$ before cancellation, then at worst\footnote{In
  this section, ``at worst'' means ``giving the largest growth
  estimate''.} the probability that there be $m$ cancellations in $w_i$
is
\begin{equation}\label{eq:binom}
  C^{n_i-1}_m=\binom{n_i-1}m\left(\frac1{\#A}\right)^m\left(\frac{\#A-1}{\#A}\right)^{n_i-1-m}.
\end{equation}

We now estimate the total length of the $w_i$. It is at most
$|w|+d-1-m$, where $m$ is the total number of cancellations. We may
not claim that the cancellations on all $w_i$ are independent ---
indeed, it may happen that abundant cancellation in $w_i$ implies
abundant cancellation in some other $w_j$.

However, the longest of the $w_i$ has cancellation given by the
previous paragraph, and the other $w_j$'s have cancellation correlated
(to some positive or negative degree) with $w_i$. Call $p(m)$ the
probability that there be $m$ cancellations. If there is no
correlation, then at worst $p(m)=C^{|w|-d+1}_m$, since then all $n-d+1$
inner $A$-syllables have independent probability at least
$1/\#A$ of being trivial. If there is full positive correlation, then
at worst $p(m)=\frac1d C^{|w|/d-1}_{m/d}$, since the $d$ words
$w_1,\dots,w_d$ can be assumed to behave in the same way.

We may therefore assume that there is an unknown parameter $\eta$,
depending on $G$, such that at worst $p(m)=\eta
C^{\eta(|w|-d+1)}_{\eta m}$.

The decomposition map on words induces a natural map $G_{k-1}\to
G_k\wr_\Sigma A$, also written $g\mapsto[g_1,\dots,g_d]g_a$, where
$g_a$ is obtained by restricting the action of $g\in G_{k-1}$ to
$\Sigma$, and $g_i$ are obtained by restricting the action of
$gg_a^{-1}$ to $i\Sigma^*$. For all $k\in\N$ let $\Gamma_k$ denote the
growth series of $G_k$, and write $\langle n,\Gamma\rangle$ for the
degree-$n$ coefficient of $\Gamma$.

We relate $\Gamma_{k-1}$ to $\Gamma_k$ as follows:
\begin{align*}
  \Gamma_{k-1}(z)&=\sum_{n\ge0}\langle n,\Gamma_{k-1}\rangle z^n=\sum_{g\in G_{k-1}}z^{\|g\|}\\
  &\le\sum_{[g_1,\dots,g_d]a\in G_k\wr_\Sigma A}z^{\|[g_1,\dots,g_d]a\|}\\
  &\le\#A\sum_{[g_1,\dots,g_d]\in G_k\times\dots G_k}z^{\|[g_1,\dots,g_d]\|}\\
  &\le\#A\sum_{\substack{[g_1,\dots,g_d]\in G_k\times\dots G_k\\ 0\le
      m\le \|[g_1,\dots,g_d]\|}}\eta C^{\eta(\|[g_1,\dots,g_d]\|-d+1)}_mz^{\|[g_1,\dots,g_d]\|}\\
  &\le\#A\sum_{\substack{n_1,\dots,n_d,m\ge0\\
      n+d-1-m=n_1+\dots+n_d}}\eta C^{\eta(n-d+1)}_{\eta m}\langle n_1,\Gamma_k\rangle\dots\langle
  n_d,\Gamma_k\rangle z^n\text{ with $n_i=\|g_i\|$}\\
  &=z^d\#A\sum_{m,p\ge0}\eta\binom{\eta(m+p)}{\eta m}\left(\frac
  z{\#A^\eta}\right)^m\left\langle
    p,z^{-2}\Gamma_k\left(z\Big(\frac{\#A-1}{\#A}\Big)^\eta\right)^d\right\rangle z^p.\tag{*}\label{eq:finalineq}
\end{align*}
Let $1/\rho_k$ be the convergence radius of $\Gamma_k$. Define the
power series $\Delta(z)=(1-z/\#A^\eta)^{-1}$, with radius of
convergence $\#A^\eta$. Corollary~\ref{cor:oint} may be applied to the
inequality~\eqref{eq:finalineq} involving the power series $\Gamma_k$
and $\Delta$; hence we obtain
\[\rho_{k-1}\le\rho_k\frac{\#A-1}{\#A}+\frac1{\#A},\]
and hence by induction
\[\rho_k\le(\rho_\ell-1)\left(\frac{\#A-1}{\#A}\right)^{k-\ell}+1\text{
  for all }k,\ell\in\N.\]
Since $\rho_\ell\le\#S-1$ for all $\ell\in\N$, we obtain $\rho_k=1$ for
all $k\in\N$. Therefore by Lemma~\ref{lem:diskconv} all $G_k$ have
subexponential growth.

For simplicity assume now $\eta=1$. We actually derived more
information from the previous computation; namely, writing
$\Delta(z)=1/(1-z/\#A)$,
\begin{equation}\label{eq:funct}
  \Gamma_{k-1}(z)\le\#A\frac1{2i\pi}\oint_{|w|=\epsilon}\Delta((1+w^{-1})z)\Gamma_k\left((1+w)z\frac{\#A-1}{\#A}\right)^d\frac{dw}{w}.
\end{equation}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Superpolynomial growth}\label{sec:superpol}
Make the assumptions of the second part of Theorem~\ref{thm:main}, and
consider also the groups $G_k$ introduced in the beginning of
Section~\ref{sec:subexp}. The hypotheses show that the map $G_{k-1}\to
G_k\wr_\Sigma A$ is surjective onto $A$ and each of the factors $G_k$.

Assume for contradiction that some $G_k$ has polynomial growth, say of
degree $D$, and assume $D$ is minimal among the growth rates of
all $G_n$'s.

Consider the subgroup $H$ of $G_k$, that fixes $\Sigma$ pointwise.
Restriction of the action to $d\Sigma^*$ defines a surjective map
$H\to G_{k+1}$. On the other hand, consider the two cases:
\begin{description}
\item[$\mathbf{d\ge3}$] Then among the conjugates $b^a$ for all $b\in
  B_k$ and $a\in A\setminus\stab_A(d)$, there must be at least two
  distinct, say $b_1^{a_1}$ and $b_2^{a_2}$, with same $d$-coordinate.
  Consider $K$, the normal closure in $H$ of $b_1^{a_1}b_2^{-a_2}$.
\item[$\mathbf{d=2}$] Then $A=\langle(1,2)\rangle$ and $|B|>|A|$ by
  assumption, so there must be a non-trivial $b\in B_k$ with
  $\phi_1(b)=1$.  Consider $K$, the normal closure in $H$ of
  $b^{(1,2)}$.
\end{description}
Since $A$ acts transitively on $\Sigma$ and all $B_n$'s map onto $A$,
the group $G_k$ acts transitively on $\Sigma^n$ for all $n\in\N$. The
$b^h\neq1$ for $b\in B_k$ and $h\in H$ have an ``axis'', which is the
infinite path $(dd\dots)^h$ in $\Sigma^*$. Since $H$ is transitive on
$i\Sigma^*$ for all $i\in\Sigma$, it follows that there are infinitely
many conjugates $b^h$, and hence in all cases $K$ is infinite.

Clearly the restriction of $K$ to $d\Sigma^*$ is trivial, so we have a
surjective map $H\to G_{k+1}$ with infinite kernel. The growth of
$G_{k+1}$ is at least polynomial of degree $D$, so the growth of $H$,
and hence of $G_k$, is at least polynomial of degree $D+1$. This
contradicts our assumption on the growth of $G_k$.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{The distribution of the decomposition}\label{sec:distr}
The proof of subexponential growth made two simplifying assumptions:
Given a uniform word $w$ and its decomposition $[w_1,\dots,w_d]a$,
each $A$-syllable of $w_i$ has probability $1/\#A$ of being trivial,
and these probabilities are independent, even between syllables in
$w_i$ and $w_j$ coming from the same $B$-letter of $w$.

These simplifications were legitimate in that they only increased the
growth estimate. We consider in this section whether they actually
hold.
\begin{prop}
  Assume $w$ is a uniform word with decomposition $[w_1,\dots,w_d]a$.
  If all homomorphisms $\phi_i^n$ are onto, then the $w_i$ are
  mutually independent uniform words.
\end{prop}
\begin{proof}
  Clearly all the $B$-letters in $\{w_1,\dots,w_d\}$ are uniform and
  independent, since they come from all different $B$-letters in $w$.

  Consider an arbitrary $A$-syllable in a word $w_i$. Since the
  $\phi^n_i$ are onto, it is a product of at least one uniform
  variable on $A$, and hence it is uniformly distributed.
  
  Consider next two $A$-syllables in $w_i$ and $w_j$. If $i=j$, then
  they are independent by Lemma~\ref{lem:uniform}. If $i\neq j$, then
  the $B$-letters from which they come in $w$ are not all the same.
  Consider a $B$-letter contributing to the first syllable but not the
  next; then the distribution of the first syllable is a convolution
  with a uniform distribution over $A$ that is independent of the
  second syllable, so these syllables have independent distribution.
\end{proof}

The first group of intermediate growth for which the proposition does
not apply is the ``Fabrykowski-Gupta group''. There I found
experimentally that on average the total length of the $w_i$'s is
$\frac12|w|$, and not $\frac23|w|$.

For a splitter-mixer group $G$, consider a uniform word $w$ of length
$n$, and decompose it as $[w_1,\dots,w_d]a$. Consider the distribution
of $|w_1|+\dots+|w_d|$. For $n$ large, it will be a sum of many
independent events, and hence will follow a normal distribution, with
mean $\mu_Gn$ and variance $\sigma_Gn$.

\def\group#1#2#3{\fbox{$#1#2#3$}}
\begin{figure}
  \begin{picture}(0,0)(277,579)
%   \put(125,216){X}
    \put(485,205){$\mu$}
    \put(112,568){$\sigma$}
    \put(143,239){$\group001$}
    \put(143,258){$\fbox{01}$}
    \put(143,409){$G,\tilde G,\fbox{1},\group010$}
    \put(217,562){$\group1ij,\group1ik,\group1jk$}
    \put(290,332){$\group021$}
    \put(290,410){$\group012$}
    \put(290,455){$\group102$}
    \put(328,447){$\group iij,\group iik,\group jii$}
    \put(309,295){$\group011,\group013$}
    \put(365,334){$\fbox{11},\fbox{12}$}
    \put(365,351){$\group122$}
    \put(365,371){$\group212$}
    \put(365,420){$\group ijk,\group ikj,\group jki$}
    \put(365,480){$\group101,\group103$}
    \put(439,284){$\group112,\group132$}
    \put(439,308){$\group121,\group123$}
    \put(394,225){$\group131,\group113,\group111$}
  \end{picture}
  \psfrag{0.18}[r][r]{$0.18$}
  \psfrag{0.2}[r][r]{$0.20$}
  \psfrag{0.22}[r][r]{$0.22$}
  \psfrag{0.24}[r][r]{$0.24$}
  \psfrag{0.26}[r][r]{$0.26$}
  \psfrag{0.28}[r][r]{$0.28$}
  \psfrag{0.3}[r][r]{$0.30$}
  \psfrag{0.5}[][]{$\frac12$}
  \psfrag{0.55}[l][l]{\kern+18pt$\frac59$}
  \psfrag{0.6}[l][l]{\kern+19pt$\frac{11}{18}$}
  \psfrag{0.65}[l][l]{\kern+34pt$\frac23$}
  \psfrag{0.7}[l][l]{\kern+34pt$\frac{13}{18}$}
  \psfrag{0.75}[][]{$\frac34$}
  \epsfig{file=distribution.eps}
  \label{fig:distr}
  \caption{The distribution of the Grigorchuk group $G$ and overgroup
    $\tilde G$, and the splitter-mixer groups with $\phi^n_i$
    independent of $n$ and
    $(A,B)\in\{(\Z/2,\Z/2),(\Z/3,\Z/3),(\Z/4,\Z/4),((\Z/2)^2,\Z/2)$.
    The notation $\epsilon_1\dots\epsilon_{d-1}$ refers to the group
    with $|A|=d$ and $\phi^n_i(1)=\epsilon_i$; elements of $\Z/d\Z$
    are given as integers in $\{0,\dots,d-1\}$, and $(\Z/2)^2$ is
    given as $\{1,i,j,k\}$. The parabola indicates groups with no
    correlation between coordinates.}
\end{figure}

The model used in section~\ref{sec:subexp} made the assumptions
$\mu_G=(\#A-1)/\#A$ and $\sigma_G=\mu_G(1-\mu_G)$.
Figure~\ref{fig:distr} shows the distributions for the first examples
of splitter-mixer groups, given by $A=B=\Z/d$ and $A=(\Z/2)^2,B=\Z/2$.
They first are identified by a sequence of integers
$\epsilon_1,\dots,\epsilon_{d-1}$ with $0\le\epsilon_i<d$, and are
constructed as follows: $A=B=\Z/d\Z=\langle a\rangle$, and
$\phi^n_i(a)=a^{\epsilon_i}$. The same construction gives the second,
where $(\Z/2)^2$ is described as $\{1,i,j,k\}$ with
$1=i^2=j^2=k^2=ijk$.

If there were no correlation between the coordinates, the distribution
would follow the binomial law~\eqref{eq:binom}, with mean
$\frac{\#A-1}{\#A}$ and variance $\mu_G(1-\mu_G)$. The correlation
factor $\eta$ satisfies $\sigma_G\eta=\mu_G(1-\mu_G)$; hence points
above the parabola indicate groups with positive correlation, while
points below the parabola indicate groups with negative correlation
between the coordinates $w_i$.

The data in Figure~\ref{fig:distr} were obtained either by theoretical
means (for $G$, $\tilde G$ and $d\le3$), or by Monte-Carlo simulation
with $500\,000$ words of length $10\,000$ (for the $18$ groups with
$d=4$ listed below).

Not all sequences of $\epsilon_i$ need be considered: the two
sequences $\epsilon_1,\dots,\epsilon_{d-1}$ and
$\epsilon_{d-1},\dots,\epsilon_1$ define the same group, and so does
$d-1-\epsilon_1,\dots,d-1-\epsilon_d$. These transformations amount to
replacing the generator of $A$ or $B$ by its inverse.

We also restrict to sequences $\epsilon_1,\dots,\epsilon_{d-1}$ such
that $l.c.m.(\epsilon_i)=1$; this amounts to asking the embedding
$G_{k-1}\to G_k\wr A$ to be subdirect.

The first examples are:
\begin{itemize}
\item $1$ for $d=2$; this is the infinite dihedral group;
\item $0,1$ and $1,1$ and $1,2$ for $d=3$; these are respectively the
  Fabrykowski-Gupta group, the Gupta-Sidki group, and the
  Bartholdi-Grigorchuk group. These $3$ groups are non-isomorphic: the
  G-S group is torsion, the F-G is virtually torsion-free branch, and
  the B-G group is not branch.
\item for $d=4$, there are at most $18$ isomorphism classes of groups,
  namely
  \[001,010,021,012,102,011,013,122,212,
  101,103,112,132,121,123,111,113,131.\]
  I do not know which are isomorphic, but possibly their values of
  $\mu$ and $\sigma$ serve as invariants to distinguish them.
\item for $B=\Z/2$ and $A=(\Z/2)^2$, there is an action of
  $SL_2(\Z/2)=S_6$ on the sequences that simultaneously permutes the
  three entries and their contents. There are at most $9$ isomorphism
  classes, namely
  \[1ij,1ik,1jk,\quad iij,iik,jii,\quad ijk,jik,jki.\]
\end{itemize}

Note finally that the contraction distribution in a mixer-splitter
group may be even larger than described here. First, the $A$-letters
of the restrictions $w_i$ need not be uniformly distributed over
$A\setminus\{1\}$, even if those of $w$ were. Secondly, there may be
some extra cancellation coming from consideration of the $B$-letters.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{More on splitter-mixer groups}\label{sec:algebra}
In this section I give some more algebraic results on mixer-splitter
groups. They extend naturally considerations by Taras
Vovkivsky~\cite{vovkivsky:ggs} and Gupta and
Sidki~\cite{gupta-s:ext}.

As above, we assume a mixer-splitter group $G$ has been fixed, with
data $\Sigma=\{1,\dots,d\}$; a group $A$ acting on $\Sigma$; and $B$ and
$\phi^n_i:B\to A$ for all $i\in\{1,\dots,d-1\}$ and $n\in\N$.

Let us make the assumption that the $\phi^n_i:B\to A$ are periodic
functions, i.e.\ there is $k_i\in\N$ with $\phi^{n+k_i}_i=\phi^n_i$.
Up to replacing $\Sigma$ by a cartesian power of itself and extending $A$
and $B$ appropriately, we may suppose in that case that
$\phi^{n+1}_i=\phi^n_i$ for all $n,i$. We will call $G$ \emph{regular}
in that case.

Construct the graph $\gf$ with vertex set $B\times A$; for all
$(b,a)\in V(\gf)$, let $\{d,x_2,\dots,x_e\}$ be the $\Sigma$-orbit of
$a$ containing $d$, and call $e(b,a)$ its size. Put a directed edge
from $(a,b)$ to $\pi(b,a)=(b',a')$, where the action on $d\Sigma^*$ of
$(ba)^e$ is $b'a'$.  (Note that $b'=b$ or $b'=1$, and $e(b,a)=1$
implies $e\pi(b,a)=1$).
\begin{thm}
  Let $G$ be a regular mixer-splitter group with $A$ abelian. Then
  $G$ is a torsion group if and only if all the cycles in $\gf$ are
  loops at vertices $(b,a)$ with $e(b,a)=1$.
\end{thm}
\begin{proof}
  First, assume that the path starting at $(b,a)$ does not reach a
  loop with $e(b,a)=1$. Consider the elements $g_0=ba$ and
  $g_{i+1}=g_i^{e\pi^i(b,a)}$. Then $g_i$ fixes the vertex $d^i$ but
  not $d^{i+1}$, so all these elements are distinct and hence $G$ is
  not torsion.
  
  On the other hand, suppose that the only loops in $\gf$ are at
  $(b,a)$ with $e(b,a)=1$.  Let $g=b_1a_1\dots b_ka_k$ be an
  element of $G$; we reason by induction on $k$.
  
  If $k=1$, we have $g=ba$; let $\{d=x_1,x_2,\dots,x_e\}$ be the
  $a$-orbit of $d$ in $\Sigma$. Assume first $e(b,a)=1$; then the order of
  $g$ is the l.c.m.\ of the order of $b$ and the order of $a$, and
  hence is finite.
  
  If $e(b,a)>1$, then $g^{e(b,a)}$ fixes all subtrees $x_i\Sigma^*$, and
  acts like a conjugate of $b'a'$ on them. Since $A$ is finite, a
  power of $g^e$ furthermore fixes $\Sigma$ and acts trivially on all
  subtrees not of this form. Repeating from $(b',a')$, we reach the
  previous case after a finite number of steps.
  
  Suppose now $k>1$, and assume all words of length at most $k-1$ are
  torsion. Write the decomposition of $g$ as $[g_1,\dots,g_d]a$, and
  let $\{d=x_1,x_2,\dots,x_e\}$ be the $a$-orbit of $d$ in $\Sigma$. Then
  $g^e$ fixes the subtree $d\Sigma^*$, and acts like $g'=g_{x_1}\dots
  g_{x_e}$ on it. In particular, the length of this word is at most
  $k$.
  
  For all $x\in \Sigma\setminus\{x_1,\dots,x_d\}$ the restriction to the
  subtree $x\Sigma^*$ of $g^f$, where $f>0$ is minimal such that $g^f$
  fixes $x$, has length at most $k-1$, so is torsion by induction.
  
  If $g'$ has length $k$, then it is a product, in some order, of all
  the $b'_i$ and $a'_i$ with $\pi(b_i,a_i)=(b'_i,a'_i)$; since $A$ is
  abelian, the order is unimportant. Sufficient applications of this
  step will lead us either to a situation where all $a'_i$ fix the
  vertex $d$, and in that case $g'$ has finite order at most $|B\times
  A|$; or to a situation where $g'$ has length at most $k-1$, in which
  case we may apply induction.
\end{proof}

A subgroup $G$ of $\aut\Sigma^*$ is \emph{weakly
  branch}~\cite{grigorchuk:jibg} if it acts transitively on $\Sigma^n$
for all $n\in\N$, and for all $\sigma\in\Sigma^*$ there exists
$g\neq1$ in $G$ fixing pointwise $\Sigma^*\setminus\sigma\Sigma^*$.
Weakly branch groups may not satisfy a non-trivial identity, so cannot
be virtually nilpotent, so cannot have polynomial growth.

Note that there exist weakly branch groups of exponential growth ---
the simplest is probably $\langle a,b\rangle$ acting on $\{1,2\}^*$,
whose generators are defined by their decomposition $a=[1,b](1,2)$ and
$b=[1,a]$.
  
Branch groups are those weakly branch groups such that for every
$n\in\N$ the subgroup generated by all elements acting only on some
subtree $\sigma_1\dots\sigma_n\Sigma^*$ has finite index in $G$. All
known branch groups have intermediate growth.

\begin{thm}\label{thm:branch}
  Let $G$ be a level-transitive regular mixer-splitter group of
  intermediate growth with $A$ abelian. Then $G$ is weakly branch.

  If furthermore $G$ is torsion, then $G$ is branch.
\end{thm}
\begin{proof}
  The subgroup $G'$ is the kernel of the natural map $G\to A\times
  B$. Consider the subgroup $K=G''$; then $K\neq1$ since then $G$
  would be solvable, and hence have polynomial or exponential growth.
  
  Assume first $|X|\ge3$. For any $k\in K$ we have
  $k'=[1,\dots,1,k]\in K$; indeed for any $g_d\in G'$ we have some
  $[g_1,\dots,g_d]\in G'$, with at most one of
  $g_1,\dots,g_{d-1}\neq1$. Taking commutators of two such expressions
  with other non-trivial element in different coordinates gives an
  arbitrary element $[1,\dots,1,k]$ with $k\in K$.
  
  If $|X|=2$, then $|B|>|A|$ so we may follow similar considerations
  starting from elements in the kernel of $\phi^1_1$.

  If $G$ is torsion, then $G''$ has finite index in $G$.
\end{proof}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Final remarks}\label{sec:final}
In this final section I list a few remarks, extensions and open
questions related to the growth of groups acting on trees.

\begin{enumerate}
\item It is worthwhile to stress where the inequalities are strict in
  the first part of Theorem~\ref{thm:main}'s proof. First, the
  embedding $G_{k-1}\to G_k\wr_\Sigma A$ is not onto. Then in the
  decomposition process only some simplifications are performed.
  Finally the cancellations are assumed to occur independently --- if
  they are correlated, then more cancellation occurs and the growth is
  smaller than predicted.
\item The extension of Theorem~\ref{thm:branch} to groups with
  non-abelian $A$ should not pose any difficulty. However, is there a
  criterion to determine when such a group is branch? To see the
  difficulty, note that the groups $01$ and $12$ are branch, while
  $11$ is only weakly branch. Among the examples with $d=4$, it seems
  that all are branch except $012,212,103,113,1x1$.
\item Even though Theorem~\ref{thm:main} covers all known
  constructions of groups of intermediate growth, it would be
  interesting to discover such groups of a completely different nature
  --- for instance, simple groups, or finitely presented groups.
\item Andrew Brunner, Said Sidki and Ana Cristina
  Vieira~\cite{brunner-s-v:nonsolvable} studied extensively the
  subgroup $G$ of $\aut\{1,2\}^*$ generated by $\tau,\mu$ defined by
  their decompositions $\tau=[1,\tau](1,2)$ and
  $\mu=[1,\mu^{-1}](1,2)$. They ask what the growth of $G$ is, and
  this question is still open.  Edmeia Da Silva~\cite{silva:phd}
  showed that $G$ does not contain any free subgroup; however, it is
  unknown whether $G$ contains any free submonoids.
\item It should be possible to obtain quantitative estimates on the
  growth of $G$ in Section~\ref{sec:subexp}, based on a study of the
  singularities of $\Gamma$ on the unit circle imposed
  by~\eqref{eq:funct}.
\item We mentioned that the groups of polynomial growth are precisely
  the virtually nilpotent groups. Grigorchuk proved
  in~\cite{grigorchuk:hp} that among residually-$p$ groups,
  non-virtually-nilpotent groups have growth at least $e^{\sqrt n}$,
  and Alex Lubotzky and Avinoam Mann obtained the same result for
  residually-nilpotent groups---see~\cite{bartholdi-g:lie} for more
  details.
  
  If $A$ is a $p$-group, the growth of $G$ must therefore be at least
  $e^{\sqrt n}$. It seems reasonable to guess that this holds for all
  $A$, but a different argument may be needed.
  
  It is not known whether there exist groups of growth strictly
  between polynomial and $e^{\sqrt n}$.
\item The analogous question for semigroups is well understood.
  Namely, given any two submultiplicative, superquadratic and
  subexponential functions $\gamma,\delta$, there is a semigroup whose
  growth function is infinitely often larger than $\gamma$ and
  infinitely often smaller than $\delta$. George Bergman shows
  in~\cite{bergman:growth} that any polynomial growth rate
  $\gamma(n)=n^\alpha$ is possible with $\alpha\ge2$, and Lev
  Shneerson shows in~\cite{shneerson:interm} that the free semigroup
  with respect to a simple identity has intermediate growth of rate
  $e^{\sqrt n}$. See~\cite{MR2001g:20076} for semigroups of matrices
  with this property.
\item Groups of subexponential growth are amenable. It may be that
  all weakly branch groups are amenable, even those of exponential
  growth. There is no known example of a weakly branch group having
  Kazhdan's property~(T).
\item The tree automorphisms corresponding to the $a\in A$ and
  $b\in B_k$ can be described by \emph{transducer automata}. These are
  finite devices with states corresponding to the generators $A\cup
  B$, and transitions and activity corresponding to the decomposition
  map.

  The nature of the automorphisms considered translates to the
  transitions being only from $B$ states to $A$ states, and from $A$
  states to the trivial state.

  Said Sidki considered in~\cite{sidki:acyclicity} a hierarchy of tree
  automorphisms, in which ours occupy the lowest layers. It might
  prove interesting to explore growth properties among higher groups
  in the Sidki ladder.
\item The proof of Section~\ref{sec:subexp} extends \emph{verbatim} to
  groups acting on irregular rooted trees
  $\Sigma_1\times\Sigma_2\times\dots$, with varying alphabets
  $\Sigma_i$ and associated group $A_i$. In that setting $G$ has
  subexponential growth as soon as $\sum_{n\in\N}\frac1{\#A_n}$
  diverges. I would be hard pressed to find any usefulness to this
  generalization.
\end{enumerate}
\bibliography{mrabbrev,people,math,grigorchuk,bartholdi}
\end{document}
001     [ 2, 10, 34, 130 ]      1/2*4^n+2
010     [ 2, 10, 30, 110 ]      (5/4*4^n+10)/3
021     [ 2, 10, 34, 130 ]      1/2*4^n+2
012     [ 2, 10, 32, 118 ]X
102     [ 2, 10, 34, 130 ]      1/2*4^n+2
011     [ 2, 8, 26, 98 ]        6/16*4^n+2
013     [ 2, 8, 26, 98 ]        6/16*4^n+2
122     [ 2, 10, 34, 130 ]      1/2*4^n+2
212     [ 2, 10, 31, 113 ]X
101     [ 2, 6, 17, 60, 232 ]
103     [ 2, 6, 19, 68, 264 ]X
112     [ 2, 8, 26, 98 ]        6/16*4^n+2
132     [ 2, 8, 26, 98 ]        6/16*4^n+2
121     [ 2, 6, 19, 68, 264 ]X
123     [ 2, 6, 16, 56, 216 ]   (10/16*4^n+8)/3
111     [ 2, 10, 32, 118 ]X
113     [ 2, 10, 32, 119 ]X
131     [ 2, 10, 32, 118 ]X

TST := function(n,b)
  G := MakeFrGroup("a=[,,,](1,2,3,4)",b);
  return List([1..n],n->LogInt(Size(Image(EpimorphismPermGroupFrGroup(G,n))),2));
end;
TST(4,"b=[a^0,a^0,a^1,b]()");
TST(4,"b=[a^0,a^1,a^0,b]()");
TST(4,"b=[a^0,a^2,a^1,b]()");
TST(4,"b=[a^0,a^1,a^2,b]()");
TST(4,"b=[a^1,a^0,a^2,b]()");
TST(4,"b=[a^0,a^1,a^1,b]()");
TST(4,"b=[a^0,a^1,a^3,b]()");
TST(4,"b=[a^1,a^2,a^2,b]()");
TST(4,"b=[a^2,a^1,a^2,b]()");
TST(5,"b=[a^1,a^0,a^1,b]()");
TST(5,"b=[a^1,a^0,a^3,b]()");
TST(4,"b=[a^1,a^1,a^2,b]()");
TST(4,"b=[a^1,a^3,a^2,b]()");
TST(5,"b=[a^1,a^2,a^1,b]()");
TST(5,"b=[a^1,a^2,a^3,b]()");
TST(4,"b=[a^1,a^1,a^1,b]()");
TST(4,"b=[a^1,a^1,a^3,b]()");
TST(4,"b=[a^1,a^3,a^1,b]()");

interm.bbl
\def\nop#1{}\font\cyr=wncyr8\def\cprime{$'$}
\providecommand{\bysame}{\leavevmode\hbox to3em{\hrulefill}\thinspace}
\begin{thebibliography}{Mil68b}

\bibitem[Bar98]{bartholdi:upperbd}
Laurent Bartholdi, \emph{The growth of {Grigorchuk}'s torsion group}, Internat.
  Math. Res. Notices \textbf{20} (1998), 1049--1054.

\bibitem[Bar01]{bartholdi:lowerbd}
Laurent Bartholdi, \emph{Lower bounds on the growth of a group acting on the
  binary rooted tree}, Internat. J. Algebra Comput. \textbf{11} (2001), no.~1,
  73--88.

\bibitem[Ben83]{benson:zn}
Michael Benson, \emph{Growth series of finite extensions of {$\mathbb Z^n$} are
  rational}, Invent. Math. \textbf{73} (1983), 251--269.

\bibitem[Ber78]{bergman:growth}
George~M. Bergman, \emph{A note on growth functions of algebras and
  semigroups}, unpublished, 1978.

\bibitem[BG00]{bartholdi-g:lie}
Laurent Bartholdi and Rostislav~I. Grigorchuk, \emph{Lie methods in growth of
  groups and groups of finite width}, Computational and Geometric Aspects of
  Modern Algebra (Michael~Atkinson et~al., ed.), London Math. Soc. Lect. Note
  Ser., vol. 275, Cambridge Univ. Press, Cambridge, 2000, pp.~1--27.

\bibitem[BG02]{bartholdi-g:parabolic}
Laurent Bartholdi and Rostislav~I. Grigorchuk, \emph{On parabolic subgroups and
  {Hecke} algebras of some fractal groups}, to appear in Serdica Math. J.,
  2002, math.GR/9911206.

\bibitem[B{\v{S}}01]{bartholdi-s:wpg}
Laurent Bartholdi and Zoran {\v{S}}uni{\'k}, \emph{On the word and period
  growth of some groups of tree automorphisms}, Comm. Algebra \textbf{29}
  (2001), no.~11, 4923--4964.

\bibitem[BSV99]{brunner-s-v:nonsolvable}
Andrew~M. Brunner, Said~N. Sidki, and Ana~Cristina Vieira, \emph{A just
  nonsolvable torsion-free group defined on the binary tree}, J. Algebra
  \textbf{211} (1999), no.~1, 99--114.

\bibitem[Car21]{carlson:potenzreihen}
Fritz Carlson, \emph{\"uber {P}otenzreihen mit ganzzahligen {K}oefficienten},
  Math. Z. \textbf{9} (1921), 1--13.

\bibitem[Fat06]{fatou:series}
Pierre Fatou, \emph{S\'eries trigonom\'etriques et s\'eries de taylor}, Acta
  Math. \textbf{30} (1906), 335--400.

\bibitem[FG85]{fabrykowski-g:growth1}
Jacek Fabrykowski and Narain~D. Gupta, \emph{On groups with sub-exponential
  growth functions}, J. Indian Math. Soc. (N.S.) \textbf{49} (1985), no.~3-4,
  249--256.

\bibitem[FG91]{fabrykowski-g:growth2}
Jacek Fabrykowski and Narain~D. Gupta, \emph{On groups with sub-exponential
  growth functions. {II}}, J. Indian Math. Soc. (N.S.) \textbf{56} (1991),
  no.~1-4, 217--228.

\bibitem[GH90]{ghys-h:gromov}
{\'E}tienne Ghys and Pierre~{de la} Harpe, \emph{Sur les groupes hyperboliques
  d'apr\`es {Mikhael Gromov}}, Progress in Mathematics, vol.~83, Birkh{\"a}user
  Boston Inc., Boston, MA, 1990, Papers from the Swiss Seminar on Hyperbolic
  Groups held in Bern, 1988.

\bibitem[Gri83]{grigorchuk:growth}
Rostislav~I. Grigorchuk, \emph{On the {M}ilnor problem of group growth}, Dokl.
  Akad. Nauk SSSR \textbf{271} (1983), no.~1, 30--33.

\bibitem[Gri84]{grigorchuk:gdegree}
Rostislav~I. Grigorchuk, \emph{Degrees of growth of finitely generated groups
  and the theory of invariant means}, Izv. Akad. Nauk SSSR Ser. Mat.
  \textbf{48} (1984), no.~5, 939--985, English translation: {Math. USSR-Izv.
  \textbf{25} (1985), no.~2, 259--300}.

\bibitem[Gri89]{grigorchuk:hp}
Rostislav~I. Grigorchuk, \emph{On the {H}ilbert-{P}oincar\'e series of graded
  algebras that are associated with groups}, Mat. Sb. \textbf{180} (1989),
  no.~2, 207--225, 304, English translation: {Math. USSR-Sb. \textbf{66}
  (1990), no.~1, 211--229}.

\bibitem[Gri91]{grigorchuk:kyoto}
Rostislav~I. Grigorchuk, \emph{On growth in group theory}, Proceedings of the
  International Congress of Mathematicians, Vol.\ I, II (Kyoto, 1990) (Tokyo),
  Math. Soc. Japan, 1991, pp.~325--338.

\bibitem[Gri00]{grigorchuk:jibg}
Rostislav~I. Grigorchuk, \emph{Just infinite branch groups}, New horizons in
  pro-$p$ groups (Markus P. F. du~Sautoy Dan~Segal and Aner Shalev, eds.),
  Birkh\"auser Boston, Boston, MA, 2000, pp.~121--179.

\bibitem[Gro81]{gromov:nilpotent}
Mikhael Gromov, \emph{Groups of polynomial growth and expanding maps}, Inst.
  Hautes {\'E}tudes Sci. Publ. Math. (1981), no.~53, 53--73.

\bibitem[GS83a]{gupta-s:burnside}
Narain~D. Gupta and Said~N. Sidki, \emph{On the {Burnside} problem for periodic
  groups}, Math. Z. \textbf{182} (1983), 385--388.

\bibitem[GS83b]{gupta-s:infinitep}
Narain~D. Gupta and Said~N. Sidki, \emph{Some infinite $p$-groups}, Algebra i
  Logika \textbf{22} (1983), no.~5, 584--589.

\bibitem[GS84]{gupta-s:ext}
Narain~D. Gupta and Said~N. Sidki, \emph{Extension of groups by tree
  automorphisms}, Contributions to group theory, Amer. Math. Soc., Providence,
  R.I., 1984, pp.~232--246.

\bibitem[Har00]{harpe:ggt}
Pierre~{de la} Harpe, \emph{Topics in geometric group theory}, University of
  Chicago Press, Chicago, IL, 2000.

\bibitem[Mil68a]{milnor:solvable}
John~W. Milnor, \emph{Growth of finitely generated solvable groups}, J.
  Differential Geom. \textbf{2} (1968), 447--449.

\bibitem[Mil68b]{milnor:5603}
John~W. Milnor, \emph{Problem 5603}, Amer. Math. Monthly \textbf{75} (1968),
  685--686.

\bibitem[Okn98]{MR2001g:20076}
Jan Okni{\'n}ski, \emph{Semigroups of matrices}, World Scientific Publishing
  Co. Inc., River Edge, NJ, 1998.

\bibitem[Par93]{parry:salem}
Walter Parry, \emph{Growth series of {Coxeter} groups and {Salem} numbers}, J.
  Algebra \textbf{154} (1993), 406--415.

\bibitem[Sha89]{shapiro:n2}
Michael Shapiro, \emph{A geometric approach to almost convexity and growth of
  some nilpotent groups}, Math. Ann. \textbf{285} (1989), 601--624.

\bibitem[Sha94]{shapiro:psl2r}
Michael Shapiro, \emph{Growth of a {${\rm {P}{S}{L}}\sb 2\mathbb{R}$} manifold
  group}, Math. Nachr. \textbf{167} (1994), 279--312.

\bibitem[Shn01]{shneerson:interm}
Lev~M. Shneerson, \emph{Relatively free semigroups of intermediate growth}, J.
  Algebra \textbf{235} (2001), no.~2, 484--546.

\bibitem[Sid00]{sidki:acyclicity}
Said~N. Sidki, \emph{Automorphisms of one-rooted trees: growth, circuit
  structure, and acyclicity}, J. Math. Sci. (New York) \textbf{100} (2000),
  no.~1, 1925--1943, Algebra, 12.

\bibitem[Sil01]{silva:phd}
Edm{\'e}ia Fernandes~da Silva, \emph{Uma fam\'\i lia de grupos quase
  n\~ao-sol\'uveis definida sobre \'arvores $n$-\'arias, $n\ge2$}, Ph.D.
  thesis, Universidade de Bras\'\i lia, 2001.

\bibitem[Sto96]{stoll:heisenberg}
Michael Stoll, \emph{Rational and transcendental growth series for the higher
  {H}eisenberg groups}, Invent. Math. \textbf{126} (1996), no.~1, 85--109.

\bibitem[{\v S}va55]{svarts:growth}
Albert~S. {\v S}varc, \emph{A volume invariant of coverings}, Dokl. Akad. Nauk
  SSSR (1955), no.~105, 32--34 (Russian).

\bibitem[Tit72]{tits:linear}
Jacques Tits, \emph{Free subgroups in linear groups}, J. Algebra \textbf{20}
  (1972), 250--270.

\bibitem[Vov00]{vovkivsky:ggs}
Taras Vovkivsky, \emph{Infinite torsion groups arising as generalizations of
  the second {G}rigorchuk group}, Algebra (Moscow, 1998), de Gruyter, Berlin,
  2000, pp.~357--377.

\bibitem[Wol68]{wolf:solvable}
Joseph~A. Wolf, \emph{Growth of finitely generated solvable groups and
  curvature of {R}iemanniann manifolds}, J. Differential Geom. \textbf{2}
  (1968), 421--446.

\end{thebibliography}
