To Infinity and Beyond∗
Ines Klimann
Univ Paris Diderot, Sorbonne Paris Cité, IRIF,
UMR 8243 CNRS, F-75013 Paris, France,
klimann@irif.fr

arXiv:1708.06173v2 [cs.FL] 4 Sep 2017

September 5, 2017

Abstract
We prove that if a group generated by a bireversible Mealy automaton contains an element of
infinite order, its growth blows up and is necessarily exponential. As a direct consequence, no infinite
virtually nilpotent group can be generated by a bireversible Mealy automaton.

The study on how (semi)groups grow has been highlighted since Milnor’s question on the existence of
groups of intermediate growth (faster than any polynomial and slower than any exponential) in 1968 [12],
and the very first example of such a group given by Grigorchuk [5]. Uncountably many examples have
followed this first one, see for instance [6]. Bartholdi and Erschler have even obtained results on precise
computations of growth, in particular they proved that if a function satisfies some frame property, then
there exists a finitely generated group with growth equivalent to it [1]. Besides, for now, intermediate
growth and automaton groups, that is groups generated by Mealy automata, seem to have a very strong
link, since the only known examples of intermediate growth groups are either automaton groups, or based
on such groups.
There exists no criterium to test if a Mealy automaton generates a group of intermediate growth and
it is not even known if this property is decidable. However, there is no known example in the litterature of
a bireversible Mealy automaton generating an intermediate growth group and it is legitimate to wonder
if it is possible. This article enter in this scope. We prove that if there exists at least one element of
infinite order in a group generated by a bireversible Mealy automaton, then its growth is necessarily
exponential. It has been conjuctered, and proved in some cases [4], that an infinite group generated by
a bireversible Mealy automaton always has an element of infinite order, which suggests that, indeed, a
group generated by a bireversible Mealy automaton either is finite, or has exponential growth.
Finally, let us mention the work by Brough and Cain to obtain some criteria to decide if a semigroup
is an automaton semigroup [2]. Our work can be seen as partially answering a similar question: can a
given group be generated by a bireversible Mealy automaton? A consequence of our result is that no
infinite virtually nilpotent group can be.
This article is organized as follows. In Section 1, we define the automaton groups and the growth of
a group, and give some properties on the connected components of the powers of a Mealy automaton.
In Section 2, we study the behaviour of some equivalence classes of words on the state set of a Mealy
automaton. Finally, the main result takes place in Section 3.

1

Basic notions

In all the article, if E is a finite set, its cardinality is denoted by |E|. A finite word of length n on E is a
finite sequence of n elements of E and is denoted classically as the concatenation of its elements. The set
of finite words over E is denoted by E ∗ , the set of non-empty finite words by E + , and the set of words
of length n by E n . In general the elements of E are written in plain letters, e.g. q, while the words on E
are written in bold letters, e.g. u. The length of u is denoted by |u|, its letters are numbered from 0
∗ This work was partially supported by the French Agence Nationale pour la Recherche, through the Project MealyM
ANR-JS02-012-01.

1

to u − 1 and if i is an integer, its (i mod |u|)-th letter is denoted by u⁅i⁆; for example its first letter
is u⁅0⁆, while its last letter is u⁅−1⁆. If L is a set of words on E, L⁅i⁆ denotes the set {u⁅i⁆ | u ∈ L}.

1.1

Semigroups and groups generated by Mealy automata

We first recall the formal definition ofan automaton. A (finite, deterministic, and complete) automaton
is a triple Q, Σ, δ = (δi : Q → Q)i∈Σ , where the state set Q and the alphabet Σ are non-empty finite
sets, and the δi are functions.
A Mealy automaton is a quadruple A = (Q, Σ, δ, ρ), such that (Q, Σ, δ) and (Σ, Q, ρ) are both automata. In other terms, a Mealy automaton is a complete, deterministic, letter-to-letter transducer with
the same input and output alphabet. Its size is the cardinality of its state set and is denoted by #A.
The graphical representation of a Mealy automaton is standard, see Figure 1. But, for practical
reasons, we use sometimes other graphical representations for the transitions. For example the transition
from x to z with input letter 0 and output letter 1 in the automaton of Figure 1 can be represented
0
either by

0|1

x −−→ z ,

x

or by

z .
1

0|1
x

z

0|0, 1|1
1|0

1|0
y

0|1

Figure 1: The Aleshin automaton.
Let A = (Q, Σ, δ, ρ) be a Mealy automaton. Each state q ∈ Q defines a mapping from Σ∗ into itself,
recursively by:
∀i ∈ Σ, ∀s ∈ Σ∗ ,
ρq (is) = ρq (i)ρδi (q) (s) .
The image of the empty word is itself. For each q ∈ Q, the mapping ρq is length-preserving and
prefix-preserving. We say that ρq is the function induced by q. For u = q1 · · · qn ∈ Qn with n > 0, set
ρu : Σ∗ → Σ∗ , ρu = ρqn ◦ · · · ◦ ρq1 .
The semigroup of mappings from Σ∗ to Σ∗ generated by {ρq , q ∈ Q} is called the semigroup generated
by A and is denoted by hAi+ .
A Mealy automaton A = (Q, Σ, δ, ρ) is invertible if the functions ρq are permutations of the alphabet Σ.
In this case, the functions induced by the states are permutations on words of the same length and thus
we may consider the group of mappings from Σ∗ to Σ∗ generated by {ρq , q ∈ Q}: it is called the group
generated by A and is denoted by hAi.
When A is invertible, define its inverse A−1 as the Mealy automaton with state set Q−1 , a disjoint
j|i

copy of Q, and alphabet Σ, where the transition p−1 −→ q −1 belongs to A−1 if and only if the transii|j

tion p −→ q belongs to A. Clearly the action induced by the state p−1 of A−1 is the reciprocal of the
action induced by the corresponding state p in A.
A Mealy automaton (Q, Σ, δ, ρ) is reversible if the functions δi induced on Q by the input letters
of the transitions are permutations. The connected components of a reversible automaton are strongly
connected. In a reversible automaton of state set Q and alphabet Σ, for any word s ∈ Σ∗ and any state q,
there exists exactly one path in the automaton with label s and final state q, hence we can consider the
backtrack application induced by q: it associates to s the output label t ∈ Σ|s| of this single path.
A Mealy automaton is coreversible if the functions induced on Q by the letters as output letters of
the transitions are permutations.
A Mealy automaton is bireversible if it is both reversible and coreversible. It is quite simple to see
that the applications and the backtrack applications induced by the states of a bireversible automaton
are permutations.
Two Mealy automata are said to be isomorphic if they are identical up to the labels of their states.
2

We extend to δ the former notations on ρ, in a natural way. Hence δi : Q∗ → Q∗ , i ∈ Σ, are the
functions extended to Q∗ , and for s = i1 · · · in ∈ Σn with n > 0, we set δs : Q∗ → Q∗ , δs = δin ◦ · · · ◦ δi1 .

1.2

Growth of a semigroup or of a group

Let H be a semigroup generated by a finite set S. The length of an element g of the semigroup, denoted
by |g|, is the length of its shortest decomposition as a product of generators:
|g| = min{n | ∃s1 , . . . , sn ∈ S, g = s1 · · · sn } .
S
The growth function γH
of the semigroup H with respect to the generating set S enumerates the
elements of H with respect to their length:
S
γH
(n) = |{g ∈ H ; |g| ≤ n}| .

The growth functions of a group are defined similarly by taking symmetrical generating sets.
The growth functions corresponding to two generating sets are equivalent [11], so we may define the
growth of a group or a semigroup as the equivalence class of its growth functions. Hence, for example, a
finite (semi)group has a bounded growth, while an infinite abelian (semi)group has a polynomial growth,
and a non-abelian free (semi)group has an exponential growth.
It is quite easy to obtain groups of polynomial or exponential growth. Answering a question of Milnor [12], Grigorchuk gave an example of an automaton group of intermediate growth [5]: faster than any
polynomial, slower than any exponential, opening thus a new classification criterium for groups, that
has been deeply studied since this seminal article (see [7] and references therein). Besides, intermediate growth and automaton groups seem to have a very strong link, since the only known examples of
intermediate growth groups in the literature are based on automaton groups.
Note an important point for our purpose: let G be a group finitely generated by S, and (In )n>0 a
sequence of subsets of G, compatible with the length of the elements, i.e. the sets In are pairwise distinct
and P
the elements of In have all length less than or equal to n. The growth function of (In )n>0 is given
by ( k≤n |In |)n>0 ; if it grows exponentially, then so does G. In the same spirit, a group which admits
a subgroup of exponential growth grows exponentially.

1.3

The powers of a Mealy automaton and their connected components

The powers of a Mealy automaton have been shown to play an important role in the finiteness and
the order problem for an automaton (semi)groups, as highlighted in [8, 10, 4]. The n-th power of the
automaton A = (Q, Σ, δ, ρ) is the Mealy automaton

An = Qn , Σ, (δi : Qn → Qn )i∈Σ , (ρu : Σ → Σ)u∈Qn .

Note that the powers of a reversible (resp. bireversible) Mealy automaton are reversible (resp. bireversible).
The (semi)group generated by a connected component of some power of A is a sub(semi)group of the
(semi)group generated by A.
Let u and v be elements of Q+ and C be a connected component of some power of A: v can follow
u in C if uv is the prefix of some state of C. We denote by {u? # C} the set of the states which can
follow u in C:
{u? # C} = {q ∈ Q | uq is the prefix of some state of C} .
We define similarly the fact that v can precede u in C if vu is the suffix of some state of C, and we
introduce the set
{?u # C} = {q ∈ Q | qu is the suffix of some state of C} .
The aim of this section is to give some intuition on the links between the connected components of
consecutive powers of A. Since a word can be extended with a prefix or a suffix, most of the results
exposed here are expressed in both cases, but only the first result is proved in both cases, to show how
bireversibility allow to consider similarly the actions and the backtrack actions.

3

Lemma 1. Let A be a bireversible Mealy automaton with state set Q and C a connected component of
one of its powers. If u ∈ Q+ is a proper prefix of some state of C, then the cardinality of the set {u? # C}
depends only on the length of u.
Proof. Suppose that u′ is such that uu′ is a state of C, and let v be a prefix of some state vv′ of C with
the same length as u. Since C is a connected component in a reversible Mealy automaton, it is strongly
connected, so there exists a word s ∈ Σ∗ such that δs (uu′ ) = vv′ . Now, consider the action induced by s
on up, for p ∈ {u? # C}:
s
u
v
s′
p′

p

Since the automaton A is reversible, the action induced by s′ is a permutation of Q, and we have
|{u? # C}| ≤ |{v? # C}| .
The reciprocal inequality is obtained symmetrically.
Lemma 2. Let A be a bireversible Mealy automaton with state set Q and C a connected component of
one of its powers. If u ∈ Q+ is a proper suffix of some state of C, then the cardinality of the set {?u # C}
depends only on the length of u.
Proof. Suppose that u′ is such that u′ u is a state of C, and let v be a suffix of some state v′ v of C with
the same length as u. Since C is a connected component in a reversible Mealy automaton, it is strongly
connected, so there exist words s, t ∈ Σ∗ such that δs (u′ u) = v′ v and ρu′ u (s) = t:
s
u

v′

′

s′
u

v
t

Now, consider the backtrack action induced by t on pu, for p ∈ {?u # C}:
p′

p
s′
u

v
t

Since the automaton A is bireversible, the backtrack action induced by s′ is a permutation of Q, and we
have
|{?u # C}| ≤ |{?v # C}| .
The reciprocal inequality is obtained symmetrically.
Consider a state q of A. For any integer n > 0, we denote by cc(q n ) the connected component of q n
in An . The sequence of such components has some properties which we give here. These properties can
be seen as properties of the branch represented by q ω in the Schreier trie of A (also known as the orbit
tree of the dual of A) which has been introduced in [10, 4] (to keep this article self-contained, we give
here only the properties of this branch, but for a more global intuition on the constructions, the reader
can consult these references).
The first point is given by Lemma 1: for any n > 0, the component cc(q n+1 ) can be seen as several
full copies of the component cc(q n ); indeed, if u and v are states of cc(q n ), then in cc(q n+1 ) there are as
many states with prefix u as states with prefix v, i.e.
∀u ∈ cc(q n ), ∀v ∈ cc(q n ), |{u? # cc(q n+1 )}| = |{v? # cc(q n+1 )}| .
Hence the ratio between the size of cc(q n+1 ) and the size of cc(q n ) is necessarily an integer: it is the
cardinality of the set {u? # cc(q n+1 )} for any state u of cc(q n ), and in particular for u = q n .
4

We define by


# cc(q n+1 )
# cc(q n )



= |{q n ? # cc(q n+1 )}|

n>0



n>0

the sequence of ratios associated to the state q.
Lemma 3. Let A be a bireversible Mealy automaton with state set Q, q ∈ Q a state of A, and u and v
be two elements of Q+ . If uv is a state of cc(q |uv| ), then v is a state of cc(q |v| ) and
{uv? # cc(q |uv|+1 )} ⊆ {v? # cc(q |v|+1 )} .
Proof. Take A = (Q, Σ, δ, ρ) and let p ∈ {uv? # cc(q |uv|+1 )}.
Since A is reversible, there exist a word s ∈ Σ∗ such that δs (uvp) = q |uv|+1 :
s
q |u|

u
s′

q |v|

v
s′′
p

q

Hence δs′ (v) = q v and so v ∈ cc(q |v| ), and δs′ (vp) = q |v|+1 , which means that p ∈ {v? # cc(q |v|+1 )}.
Lemma 4. Let A be a bireversible Mealy automaton with state set Q, q ∈ Q a state of A, and u and v
be two elements of Q+ . If uv is a state of cc(q |uv| ), then u is a state of cc(q |u| ) and
{?uv # cc(q |uv|+1 )} ⊆ {?u # cc(q |u|+1 )} .
As {q n ? # cc(q n+1 )} ⊆ {q n+1 ? # cc(q n+2 )} by Lemma 3, it is straightforward to see that the
sequence of ratios associated to q decreases:
∀n > 0,

# cc(q n+1 )
# cc(q n+2 )
≤
,
# cc(q n+1 )
# cc(q n )

and hence is ultimately constant. We say that q has a constant ratio if this sequence is in fact constant,
and then the unique value of the sequence of ratios associated to q is called the ratio of q.
It has been proven in [10] that q induces an action of infinite order if and only if the sizes of the
components (cc(q n ))n>0 are unbounded, i.e. the limit of the sequence of ratios associated to q is greater
than 1.
We study now some properties on followers and predecessors in the components cc(q n ), when q has
a constant ratio.
The next lemma is an improvement of Lemma 3.
Lemma 5. Let A be a bireversible Mealy automaton, and q be a state of A of constant ratio. Let u and
v be two elements of Q+ such that uv is a state of cc(q |uv| ). We have:
{uv? # cc(q |uv|+1 )} = {v? # cc(q |v|+1 )} .
Proof. The left part is a subset of the right one by Lemma 3 and both sets have the same cardinality,
which is the ratio of q, by hypothesis.
In particular, by taking the word v of length 1 in the previous lemma, we can see that the set of
followers of a word w in cc(q n ) only depends on its last letter w⁅−1⁆.
Lemma 6. Let A be a bireversible Mealy automaton of state set Q, q be a state of A of constant ratio,
and n > 1 be an integer. If u ∈ Q+ is a suffix of some state of cc(q n ), then the set {?u # cc(q n )} only
depends on u⁅0⁆, the first letter of u.
The next lemma links up the sets of followers and of predecessors in cc(q n ) when q has a constant
ratio.

5

Lemma 7. Let A be a bireversible Mealy automaton of state set Q, q be a state of A of constant ratio,
and n > 1 be an integer. The sets of followers and of predecessors in cc(q n ) have the same cardinality
which is the ratio of q.
Proof. By Lemmas 5 and 6, we only have to prove that
|{q? # cc(q n )}| = |{?q # cc(q n )}| .
Even simpler: notice that if u is a prefix of some state of cc(q n ), then it is also a prefix of some state
in cc(q n+k ) for any k > 0, and it has the same followers in both. Of course, an equivalent property holds
for the sets of predecessors.
So it is sufficient to prove that
|{q? # cc(q 2 )}| = |{?q # cc(q 2 )}| ,
which is true because
| cc(q 2 )| = | cc(q)| × |{q? # cc(q 2 )}| = |{?q # cc(q 2 )}| × | cc(q)| .

2
2.1

Several equivalences on words
Minimization and Nerode classes

Let A = (Q, Σ, δ, ρ) be a Mealy automaton.
The Nerode equivalence ≡ on Q is the limit of the sequence of increasingly finer equivalences (≡k )
recursively defined by:
∀p, q ∈ Q,

p ≡0 q ⇐⇒ ρp = ρq ,

∀k > 0, p ≡k+1 q ⇐⇒

p ≡k q

∧


∀i ∈ Σ, δi (p) ≡k δi (q) .

Since the set Q is finite, this sequence is ultimately constant. For every element q in Q, we denote
by [q] the class of q w.r.t. the Nerode equivalence, called the Nerode class of q. Extending to the n-th
power of A, we denote by [u] the Nerode class in Qn of u ∈ Qn .
Two states of a Mealy automaton belong to the same Nerode class if and only if they represent the
same element in the generated (semi)group, i.e. if and only if they induce the same action on Σ∗ . Two
words on Q of the same length n are equivalent if they belong to the same Nerode class in Qn . By
extension, any two words on Q are equivalent if they induce the same action.
The minimization of A is the Mealy automaton m(A) = (Q/≡, Σ, δ̃, ρ̃), where for every (q, i) in
Q × Σ, δ̃i ([q]) = [δi (q)] and ρ̃[q] = ρq . This definition is consistent with the standard minimization of
“deterministic finite automata” where instead of considering the mappings (ρq : Σ → Σ)q , the computation
is initiated by the separation between terminal and non-terminal states.
A Mealy automaton is minimal if it has the same size as its minimization.
Two states of two different connected reversible minimal Mealy automata with the same alphabet
induce the same action if and only if the automata are isomorphic and both states are in correspondance
by this isomorphism. As a direct consequence, if two connected reversible minimal Mealy automata have
different sizes, then any two states of each of them cannot be equivalent.
As we have seen in Section 1.3, a state q of an invertible-reversible Mealy automaton induces an action
of infinite order if and only if the sizes of the (cc(q n ))n>0 are unbounded. The proof of [10] can be easily
adapted to see that q induces an action of infinite order if and only if the sizes of the (m(cc(q n )))n>0
are unbounded, but you can see it by a direct argument: if the sizes are bounded, there is an infinite
set I ⊆ N such that all the element (m(cc(q n )))n∈I are isomorphic, and in this sequence there exist at
least two different integer i 6= j such that q i and q j are represented by the same state in the minimal
automata, and so they induce the same action; if the sizes are unbounded, the sequence (# m(cc(q n )))n>0
has infinitely many values, and each value corresponds to a different action for the corresponding power
of q.
Note that the Nerode classes of a connected reversible Mealy automaton have the same cardinality.
The size of the minimization automaton in this case is the ratio between its size and the cardinality of
the Nerode classes.
6

Lemma 8. Let A be a connected bireversible Mealy automaton, N a Nerode class of a connected component of one of its powers, and p and q two elements of N ⁅−1⁆. There are as many elements of N with
last letter p as with last letter q.
Proof. The proof of this lemma is quite similar to the proof of Lemma 6 considering not words of length 1
as predecessors, but words on length n − 1, where n is the length of the states in N .

2.2

Restricted Nerode classes

When the considered automaton is not connected, it can be interesting to consider the restriction of
the Nerode class of an element to its connected component: we denote it by JqK et call it the restricted
Nerode class of q.
Lemma 9. The restricted Nerode classes of two elements in the same connected component of a reversible
Mealy automaton have the same cardinality.
Let A = (Q, Σ, δ, ρ) be a bireversible automaton and q a state of A of constant ratio. As it will be
discussed in Section 3, the result of this article is somehow a generalization of a much simpler result
proved in [9], in the case where all the powers of A are connected. The strategy used then is based on
the fact that Jq n Kq ⊆ Jq n+1 K when all the powers of A are connected. However in the more general case
we study here, this fact is false: a priori there is no inclusion link between Jq n K and Jq n+1 K, because if
u is a state of Jq n K, then nothing ensures that uq belongs to cc(q n+1 ); hence we have to find a different
strategy. For this purpose, we introduce the q-restricted Nerode class of q n , i.e. the set of states of Jq n K
which admit q as a suffix: J q n •K = Jq n K ∩ Q∗ q.
The aim of this section is to study the sequence (J q n •K)n>0 .
Lemma 10. There is an inclusion link in the sequence of q-restricted Nerode classes:
∀n > 0, J q n •K q ⊆ J q n+1 •K .
Proof. Let u be an element of J q n •K: u is a state of cc(q n ) and {u? # cc(q n+1 )} depends only on
u⁅−1⁆ = q from Lemma 5, so in particular q can follow u since q ∈ {q? # cc(q n+1 )}. Since u and q n
induce the same action, so do uq and q n+1 .
The next results give more information on the growth of the q-restricted Nerode classes of q n with
respect to n.
Proposition 11. Let A be a bireversible Mealy automaton, and q be a state of A of constant ratio k.
The ratio between the sizes of J q n+1 •K and J q n •K is an integer and:
∀n > 0,

| J q n+1 •K |
= |J q n+1 •K⁅−2⁆| .
| J q n •K |

In particular this ratio cannot be greater than k.
Proof. If p ∈ J q n+1 •K ⁅−2⁆, then the sets J q n+1 •K ∩Q∗ pq and J q n+1 •K ∩Q∗ qq have the same cardinality;
indeed, an element u ∈ Q∗ p satisfies uq ∈ J q n+1 •K if and only if u ∈ Jq n K by Lemmas 10 and 5 (since by
hypothesis p can precede q in Jq n+1 K). So by Lemma 8, |Jq n K ∩ Q∗ p| = | J q n •K | and the result follows.
Since p ∈ J q n+1 •K ⁅−2⁆ can precede q in cc(q n+1 ), we obtain the bound k = {?q # cc(q 2 )} from
Lemmas 6 and 7.
Proposition 12. Let A be a bireversible Mealy automaton, and q be a state of A of constant ratio k.
The sequence


| J q n+1 •K |
| J q n •K | n>0
is ultimately increasing to a limit less than or equal to k.
Proof. Consider the sequence (J q n •K )n>0 and particularly the sequence (J q n •K ⁅0⁆)n>0 : from Lemma 10,
this sequence increases. Denote by Q1 its limit: Q1 = J q n •K ⁅0⁆ for n large enough, say n ≥ N ; in
particular this set contains q.
Now, suppose n > N and take p ∈ J q n+1 •K⁅−2⁆: clearly (J q n+1 •K ∩Q∗ pq)⁅0⁆ is a subset of Q1 =
n+1
Jq
•K ⁅0⁆ = J q n •K⁅0⁆; since it has the same cardinality as the set (J q n+1 •K ∩Q∗ qq)⁅0⁆ = J q n •K ⁅0⁆ by
7

Lemma 8, it is in fact equal to Q1 . But q belongs to Q1 , so it means that the set J q n+1 •K ∩qQ∗ pq is not
empty, take u one of its elements. By Lemma 6, q can precede u in cc(q n+2 ) and qu ∈ J q n+2 •K . Hence
any penultimate letter in J q n+1 •K is also a penultimate letter in J q n+2 •K:
J q n+1 •K⁅−2⁆ ⊆ J q n+2 •K ⁅−2⁆ .
The result is now a direct consequence of Proposition 11

3

Main result

The following theorem is proved in [9]:
Theorem 13. A semigroup generated by an invertible-reversible Mealy automaton whose all powers are
connected has exponential growth.
The main result of this article, Theorem 14, is somehow a generalization of this result because all
the elements of a semigroup generated by an invertible-reversible Mealy automaton whose all powers
are connected have infinite order [10]. To prove this generalization, we need to reinforce the hypothesis
on the structure of the automaton which is supposed here to be bireversible and not only invertiblereversible, but we do not use anymore the really strong hypothesis on the connected powers. Since it is
(easily) decidable if a Mealy automaton is bireversible, while the condition on the powers is not known
to be decidable or undecidable, except in very restricted cases, the result here is way more interesting
and powerful, but it is also more tricky to establish. The question of the existence of elements of infinite
order in a semigroup generated by a bireversible automaton is under study for several years now and has
been solved in quite a few cases [8, 10, 4].
Here is the generalized version of the former theorem we prove in this section:
Theorem 14. A group generated by a bireversible Mealy automaton which contains an element of infinite
order has exponential growth.
Note that the result still holds for the generated semigroup and the proof is easily adaptable.
Proof. Let A = (Q, Σ, δ, ρ) be a bireversible Mealy automaton and u ∈ (Q ⊔ Q−1 )∗ which induces an
action of infinite order. The Mealy automaton (A ∪ A−1 )|u| is bireversible, u is one if its state, and it
generates a subgroup of A. So without lost of generality, we can suppose that u is in fact a state of A.
To be consistent with the rest of the article, let us call it q.
i+1
)
For any integer i > 0, note ri = ##cc(q
cc(qi ) . The sequence of ratios associated to q is of the form
(r1 , r2 , . . . , rj , rj+1 = rj , . . .), where ri ≥ ri+1 for any i ≥ 1 and ri = rj for any i ≥ j. Now, consider
the component cc(q j ) as a Mealy automaton and q = q j as its state: the state q induces an action
of infinite order and the sequence of ratios associated to q is of the form (rjj , rjj , . . .): q has constant
ratio. Moreover, cc(q) generates a subgroup of the group hAi, so if we prove that hcc(q)i has exponential
growth, so has hAi. So, without loss of generality we can suppose that q has a constant ratio, say k.
It is quite immediate to obtain the following inequalities:
∀n > 0,

| cc(q n )|
| cc(q n )|
| cc(q n )|
≤
≤
.
|Q| × | J q n •K |
|Jq n K|
| J q n •K |

(1)

Indeed, the right part is a consequence of the fact that J q n •K ⊆ Jq n K, and the left part of Lemma 8 and
the fact that Jq n K = ∪p∈Q (Jq n K ∩ Q∗ p).
The central part in (1) is in fact the size of the minimization of cc(q n ), and the cardinality of cc(q n )
is equal to |Q| × k n−1 since q has constant ratio k, so (1) can be re-written as:
∀n > 0,

k n−1
|Q| × k n−1
n
≤
#
m(cc(q
))
≤
.
| J q n •K |
| J q n •K |

(2)

Let us prove that for n large enough, | J q n+1 •K | < k × | J q n •K |. From Proposition 11 we know that
the corresponding non strict inequality is satisfied. Now, from Propositions 11 and 12 we know that
for N large enough, if the equality holds at rank N , it also holds at any rank greater than N : for any
n ≥ N , | J q n+1 •K | = k × | J q n •K |. This means that for n large enough, the value of the n-th term of the
sequence (| J q n •K |)n>0 is ck n−1 , where c does not depend on n. Hence by the right part of Equation (2),
8

the minimizations of the connected powers of q have bounded size, which implies that q has finite order
as seen in Section 2.1, and this is in contradiction with the hypotheses.
Denote by ℓ the limit of the sequence


| J q n+1 •K |
| J q n •K | n>0
(it exists from Proposition 12): ℓ > 1 because q has infinite order and ℓ < k from the above paragraph.
n
For n large enough, there exists a constant c such that | J q n •K | = ℓkc .
So Equation (2) becomes:
 n
 n
k
k
n
≤ # m(cc(q )) ≤ c|Q|
.
(3)
∀n > N, c
ℓ
ℓ
α
α
Since ℓ < k, there exists α such that kl
> |Q|. Let us denote u = q α and K = kℓ , we have that
for n large enough:
c · K n ≤ # m(cc(un )) ≤ c · |Q| · K n < c · K n+1 ≤ # m(cc(un+1 )) ≤ c · |Q| · K n+1 .

(4)

Consequently, the minimizations of the components cc(un ) are pairwise not isomorphic, for n large
enough, because they do not have the same size. So their states induce different elements of the group A.
Hence the sets
In = {ρv | v is a state of m(cc(un ))}
are pairwise disjoint. By Equation (4), the growth of the sequence (In )n>0 is exponential, and so is the
growth of A.
By combining Theorem 14 with the fact that connected bireversible Mealy automata of prime size
cannot generate infinite Burnside groups [4], we have:
Corollary 15. Any infinite group generated by a bireversible connected Mealy automaton of prime size
has exponential growth.
Another consequence of Theorem 14 concerns virtually nilpotent groups. This class is important in
the classification of groups and contains in particular all the abelian groups. It is known that any infinite
virtually nilpotent group contains an element of infinite order [3, Proposition 10.48] and has polynomial
growth [13]. This leads to
Corollary 16. No infinite virtually nilpotent group can be generated by a bireversible Mealy automaton.

Acknowledgement
The author is very grateful to Dmytro Savchuk for suggesting Corollary 16.

References
[1] L. Bartholdi and A. Erschler. Groups of given intermediate word growth. Ann. Inst. Fourier,
64(5):2003–2036, 2014.
[2] T. Brough and A.J. Cain. Automaton semigroups: New constructions results and examples of
non-automaton semigroups. Theoretical Computer Science, 674:1 – 15, 2017.
[3] C. Drutu and M. Kapovich.
Lectures on geometric
https://www.math.ucdavis.edu/~kapovich/EPR/ggt.pdf.

group

theory.

URL:

[4] Th. Godin and I. Klimann. On bireversible Mealy automata and the Burnside problem. Theor.
Comput. Sci., 2017. extended version of MFCS’16, to appear.
[5] R. Grigorchuk. Degrees of growth of finitely generated groups and the theory of invariant means.
Izv. Akad. Nauk SSSR Ser. Mat., 48-5:939–985, 1984.
[6] R. Grigorchuk. Degrees of growth of finitely generated groups, and the theory of invariant means.
Mathematics of the USSR-Izvestiya, 25(2):259, 1985.
9

[7] R. Grigorchuk and I. Pak. Groups of intermediate growth: an introduction for beginners, 2006.
arXiv:math/0607384.
[8] I. Klimann. Automaton semigroups: The two-state case. Theor. Comput. Syst. (special issue
STACS’13), pages 1–17, 2014.
[9] I. Klimann. On level-transitivity and exponential growth. Semigroup Forum, Sep 2016.
[10] I. Klimann, M. Picantin, and D. Savchuk. A connected 3-state reversible Mealy automaton cannot
generate an infinite Burnside group. In DLT’ 15, volume 9168 of LNCS, pages 313–325, 2015.
[11] A. Mann. How groups grow, volume 395 of Lecture Note Series. The London Mathematical Society,
2012.
[12] J. Milnor. Advanced problem 5603. MAA Monthly, 75:685–686, 1968.
[13] J.A. Wolf. Growth of finitely generated solvable groups and curvature of riemanniann manifolds. J.
Differential Geom., 2(4):421–446, 1968.

10

