arXiv:1607.07653v1 [math.GR] 26 Jul 2016

The classification of abelian groups generated by
time-varying automata and by Mealy automata over
the binary alphabet
Adam Worynaa
a Silesian

University of Technology, Institute of Mathematics, ul. Kaszubska 23, 44-100
Gliwice, Poland

Abstract
For every natural number n, we classify abelian groups generated by an n-state
time-varying automaton over the binary alphabet, as well as by an n-state Mealy
automaton over the binary alphabet.

1. Introduction
In the theory of computation time-varying automata over a finite alphabet
are finite-state transducers which constitute a natural generalization of Mealytype automata as they allow to change both the transition function and the
output function in successive steps of processing input sequences of letters into
output sequences (see [10]). These automata in turn constitute a subclass in
the class of time-varying automata over a changing alphabet (see [14]). In
group theory all these types of transducers turned out to be a useful tool for
defining and studying groups of automorphisms of certain rooted trees, which
helped in the discovery of interesting geometric and algebraic properties and
the dynamics of various types of groups associated with their actions on these
trees. The intensive study of Mealy automata in relation to automorphism
groups has continued for last three decades, and the extraordinary properties of
these groups are discussed in a great deal of papers (for the comprehensive works
see [6, 7, 8, 9, 11]). On the other hand, the investigation of automorphism groups
as groups defined by time-varying automata is a quite new approach, which we
introduced in [14] (for other results on this subject see [3, 4, 15, 16, 18, 19]).
If an automaton A is invertible, then each of its states defines an automorphism of the corresponding rooted tree. The group generated by these automorphisms (i.e. by automorphisms corresponding to all the states of A) is called
the group generated by the automaton A and is usually denoted by G(A).
Definition 1. Let n and k be natural numbers and let G be an abstract group.
We say that G is generated by an n-state time-varying (Mealy) automaton over
Email address: adam.woryna@polsl.pl (Adam Woryna)

Preprint

a k-letter alphabet if there is an invertible time-varying (Mealy) automaton A
with an n-element set of states which works over a k-letter alphabet such that
G is isomorphic to the group G(A) generated by this automaton.
Given two natural numbers n, k and a class of abstract groups, the natural question arises: which groups from this class are generated by an n-state
(time-varying or Mealy) automaton over a k-letter alphabet? This problem was
studied so far only in the case of Mealy-type automata and it turned out to be
difficult even for small values of n and k and for classes containing algebraically
well known constructions, such as abelian groups, free groups, free products of
finite groups, and many others.
It is worth noting that there is no general methods for deducing even the
basic algebraic properties of the group generated by an automaton directly from
the structure of this automaton. For example, for a long time it was an open
problem whether a free non-abelian group is generated by a Mealy automaton
(see [5] solving this problem). However, a candidate for the solution was known
and studied since 80’s last century (the so-called Aleshin-Vorobets automaton
– see [1, 13]). Until now, we do not know if the free non-abelian group of rank
two is generated by a 2-state Mealy automaton or by a 2-state time-varying
automaton over a finite alphabet. On the other hand, we provided for this group
a natural construction of a 2-state time-varying automaton over an unbounded
changing alphabet (see [16]).
The full classification of groups generated by Mealy automata is known only
in the simplest non-trivial case, i.e. when n = k = 2 ([7]). Apart from that, for
the classes of abelian groups and finite groups the solutions for Mealy automata
are known only in the case (n, k) = (3, 2) (see Theorems 3,4 in the extensive
work [2] devoted to the classification of all groups generated by 3-state Mealy
automata over the binary alphabet).
2. The results
The goal of this paper is providing for every natural number n the full
classification of abelian groups generated by an n-state time-varying automaton
over the binary alphabet as well as by an n-state Mealy automaton over the
binary alphabet.
Let us denote the following classes of abelian groups:
• T VA(n) – the class of abelian groups generated by an n-state time-varying
automaton over the binary alphabet,
• MA(n) – the class of abelian groups generated by an n-state Mealy automaton over the binary alphabet,
• AB 2 (n) – the class of abelian groups of rank not greater than n in which
the torsion part is a 2-group,
• F A(n) – the class of free abelian groups of rank not greater than n,
2

• EA2 (n) – the class of elementary abelian 2-groups of rank not greater than
n.
The main result of the paper is the following characterization.
Theorem 1. T VA(1) = EA2 (1), and if n > 1, then T VA(n) = AB 2 (n).
Theorem 2. MA(n) = F A(n − 1) ∪ EA2 (n). In particular, there are exactly
2n abelian groups generated by an n-state Mealy automaton over the binary
alphabet.
For the proof of Theorem 1 (Section 5), we find at first some restrictions on
abelian groups generated by time-varying automata over the binary alphabet.
These restrictions imply the inclusion T VA(n) ⊆ AB 2 (n) for each n ≥ 1, as
well as the equality T VA(1) = EA2 (1). Next, for every n ≥ 1 and every group
G ∈ AB 2 (n) of rank n, we provide an explicit construction of a time-varying
automaton A over the binary alphabet which generates G (see Propositions 5–
7). In the construction of the automaton A, we distinguish between three cases:
where the group G is cyclic, where G is non-cyclic and has a non-trivial torsion
part, and finally, where G is a non-cyclic, torsion-free group. Note that in the
last case G must be a free abelian group, which follows from the property that
every finitely generated, abelian group is a direct sum of cyclic groups. To
derive the required property of our construction, we use the language of wreath
recursions, which is popular in the study of groups generated by automata,
and which arises from an embedding of the group G(A) into the permutational
wreath product (for more on the method involving wreath recursions in the
case of Mealy automata see, for example, [7, 11], and in the case of time-varying
automata – see [19]).
In the proof of Theorem 2 (Section 6), for an arbitrary group G generated
by a Mealy automaton over the binary alphabet, we deduce certain relations
between the first level stabilizer of G, the set IG of involutions and the set G2 of
squares. We show (Proposition 8) a quite unexpected dichotomy, which holds
in the case when G is abelian. Namely, the relations imply in this case that G is
either a free abelian group or an elementary abelian 2-group. Next, we introduce
and study a construction of the Mealy automata generating elementary abelian
2-groups. We also use the known construction of the Mealy automata generating
free abelian groups (so-called “sausage” automata – see [7]), as well as the
restriction for the rank of free abelian groups generated by Mealy automata
over the binary alphabet (see Proposition 3.1 from [17]).
We hope that the above characterizations, together with the involved constructions and the methods presented in the proofs, will encourage to develop
further study of the groups generated by time-varying automata. This may be
useful when investigating some important, computational problems, which are
open in the class of groups generated by time-varying automata, but have a simple solution in the class of groups generated by Mealy automata. Let us mention
the word problem for groups (which is decidable in the latter class). It is known

3

that there is a time-varying automaton A over an arbitrary, unbounded changing alphabet such that the group G(A) has undecidable word problem. This
follows from the fact that there exist finitely generated, residually finite groups
with undecidable word problem, as well as from some unconstructive method of
defining an automaton realization for an arbitrary, finitely generated, residually
finite group (the so-called diagonal realization – see [14, 18]). However, there
is not known any explicit and naturally defined construction of an automaton
A such that the group G(A) has undecidable word problem. Moreover, in the
class of time-varying automata over a finite alphabet, even the question on the
existence of such an automaton is open.
In view of the above study, also the following problem is interesting and
far from trivial: given n and k, how many (pairwise non-isomorphic) groups
are contained in the class GT V(n, k) of the groups generated by an n-state
time-varying automaton over a k-letter alphabet? Obviously, if n = 1 or k =
1, then the class GT V(n, k) is finite. Further, if n ≤ n′ and k ≤ k ′ , then
GT V(n, k) is contained in GT V(n′ , k ′ ) (see the last paragraph of Section 5 for
the corresponding reasoning). Directly by Theorem 1, we obtain AB 2 (2) ⊆
GT V(2, 2), which implies that GT V(2, 2) contains infinitely many groups. But, if
k > 1 or n > 1, then there are uncountable many n-state time-varying automata
over a k-th letter alphabet. Thus the natural problem arises: find the smallest
n and k such that the class GT V(n, k) is uncountable. In particular, is the
class GT V(2, 2) uncountable? Note that the class of all groups generated by
an n-state Mealy automaton over a k-letter alphabet is finite (there are exactly
(nk · k!)n invertible Mealy automata with the n-element set of states over a k-th
letter alphabet), which implies that the class of all groups generated by Mealy
automata is countable.
The paper is organized as follows. Section 3 contains definitions of an automaton over a finite alphabet and the group generated by the automaton transformations of the corresponding rooted tree. In Section 4, we describe the notion
of the wreath recursion. In the last two sections, we present the proofs of our
characterization.
3. Automata and groups generated by automata
Let N = {1, 2, . . .} be the set of natural numbers, and let X be a nonempty,
finite set (a finite alphabet). A time-varying automaton over X is a quadruple
A = (X, Q, ϕ, ψ),
where Q is a finite set (set of states), ϕ = (ϕi )i∈N is a sequence of so-called
transition functions ϕi : Q × X → Q, and ψ = (ψi )i∈N is a sequence of so-called
output functions ψi : Q × X → X. If the sequences ψ and ϕ are constant, then
the automaton A is called a Mealy automaton. In this case the sequences ϕ,
ψ are identified with, respectively, the transition function ϕ1 and the output
function ψ1 , i.e. we can write A = (X, Q, ϕ1 , ψ1 ). If for every i ∈ N and every
q ∈ Q the mapping σi,q : x 7→ ψi (q, x) (the so-called labeling of the state q in
4

the i-th transition of A) is a bijection on the alphabet, then the automaton A
is called invertible.
The tree X ∗ of finite words over a finite alphabet X consists of finite sequences of the form x1 x2 . . . xl (l ∈ N), where xi ∈ X (1 ≤ i ≤ l), together with
the empty sequence (empty word) denoted by ǫ. The tree X ∗ is an example of
a rooted tree with the empty word as the root, and two words are adjacent if
and only if they are of the form w and wx for some w ∈ X ∗ , x ∈ X.
Let A = (X, Q, ϕ, ψ) be a time-varying automaton over X. We consider the
transformations
qi : X ∗ → X ∗ , q ∈ Q, i ∈ N
defined in the following recursive way:
• qi (ǫ) = ǫ for all q ∈ Q, i ∈ N,
′
• qi (xw) = x′ qi+1
(w) for any q ∈ Q, i ∈ N, x ∈ X, w ∈ X ∗ , where
′
x = ψi (q, x) = σi,q (x), q ′ = ϕi (q, x).

The image qi (w) of any word w ∈ X ∗ can be easily found directly from the
diagram of the automaton A = (X, Q, ϕ, ψ). We define such a diagram as an
infinite, directed, locally finite graph with the set Q × N as the set of vertices.
Each vertex (q, i) ∈ Q × N is labeled by the labeling σi,q of the state q in the
i-th transition of A. Two vertices (q, i), (q ′ , i′ ) ∈ Q × N are connected with a
directed edge which starts at (q, i) and ends at (q ′ , i′ ) if and only if i′ = i + 1
and there is x ∈ X such that ϕi (q, x) = q ′ ; we label this edge by the letter x.
In particular, for every i ∈ N, q ∈ Q and x ∈ X, there is a unique edge which is
labeled by x and starts at (q, i). Now, if w = x1 . . . xl ∈ X ∗ is any word and if
τ1 , . . . , τl are the labels of the consecutive vertices on the directed path which is
labeled by w and which starts at (q, i), then we have qi (w) = τ1 (x1 ) . . . τl (xl ).
The transformation qi is called the automaton transformation corresponding
to the state q in its i-th transition. If the automaton A is invertible, then each
qi is an element of the automorphism group Aut(X ∗ ) of the tree X ∗ , i.e. qi
is a permutation of the set X ∗ preserving the root ǫ and the vertex adjacency.
For every i ∈ N we denote by G(Ai ) the subgroup of Aut(X ∗ ) generated by
automorphisms qi for q ∈ Q:
G(Ai ) := hqi : q ∈ Qi.
The group
G(A) := G(A1 )
is called the group generated by the automaton A.
4. The language of wreath recursions
Let A = (Q, X, ϕ, ψ) be a time-varying automaton over a finite alphabet X.
We define the transformations
qi |w : X ∗ → X ∗ , i ∈ N, q ∈ Q, w ∈ X ∗
in the following recursive way:
5

• qi |ǫ = qi for all q ∈ Q, i ∈ N,
′
• qi |xw = qi+1
|w for all q ∈ Q, i ∈ N, x ∈ X, w ∈ X ∗ , where q ′ = ϕi (q, x).

The transformation qi |w is called the section of the transformation qi at the word
w. Assuming that A is invertible, we can use the labelings of the states and the
sections at one-letter words to describe the elements of the groups G(Ai ) (i ∈ N)
in the algebraical language of wreath products. Namely, if X = {x1 , . . . , xk },
then for every i ∈ N the mapping
qi → (qi |x1 , . . . , qi |xk )σi,q , q ∈ Q
induces an embedding
φi : G(Ai ) → G(Ai+1 ) ≀X Sym(X)
of the group G(Ai ) into the permutational wreath product of the group G(Ai+1 )
and the symmetric group of the alphabet, that is into the semidirect product
G(Ai+1 )X ⋊ Sym(X)
with the natural action of Sym(X) on the direct power G(Ai+1 )X by permuting
the factors. Further, we identify any element g ∈ G(Ai ) with its image φi (g)
and call the relation g = φi (g) the wreath recursion of g. In particular, for the
wreath recursion of any generator qi ∈ G(Ai ) (q ∈ Q) we have:
qi = ((r1 )i+1 , . . . , (rk )i+1 )σi,q ,
where rj = ϕi (q, xj ) for 1 ≤ j ≤ k. In general, if
g = (h1 , . . . , hk )π
is the wreath recursion of an arbitrary element g ∈ G(Ai ), then the element
hj ∈ G(Ai+1 ) (1 ≤ j ≤ k), denoted further by g|xj , is called the section of g at
the letter xj ∈ X, and the permutation π, denoted further by σg , is called the
root permutation of g. In particular, for the wreath recursion of the inverse g −1
we have
g −1 = ((g|y1 )−1 , . . . , (g|yk )−1 )π −1 ,
where yj = π −1 (xj ) (1 ≤ j ≤ k), and if an element g ′ ∈ G(Ai ) is defined by the
wreath recursion
g ′ = (g ′ |x1 , g ′ |x2 , . . . , g ′ |xk )π ′ ,
then the wreath recursion of the product g · g ′ satisfies:
g · g ′ = (g|x1 · g ′ |z1 , . . . , g|xk · g ′ |zk )ππ ′ ,
where zj = π(xj ) for 1 ≤ j ≤ k.

6

Remark 1. If the root permutation σg is trivial, then it is usually omitted in
the wreath recursion, and we write g = (g|x1 , . . . , g|xk ); also, if the sections g|xj
(1 ≤ j ≤ k) are all trivial, then g is identified with its root permutation, and
we write g = σg .
We also define the sections g|w (g ∈ G(Ai ), w ∈ X ∗ ) recursively: g|ǫ = g,
g|xw = (g|x )|w for all x ∈ X, w ∈ X ∗ .
It is worth noting that if A is a Mealy automaton, then for any i ∈ N and
any q ∈ Q the automaton transformation qi : X ∗ → X ∗ of the state q in its i-th
transition coincides with the automaton transformation q1 . In particular, if A
is invertible, then G(Ai ) = G(A) for every i ∈ N, and if g ∈ G(A) and w ∈ X ∗ ,
then g|w ∈ G(A).
Given a nonempty word w = x1 x2 . . . xl ∈ X ∗ and an element g ∈ G(A), we
can use the notions of a section and a root permutation to compute the image
g(w) of w under g in the following way:
g(w) = g0 (x1 )g1 (x2 ) . . . gl−1 (xl ) = σg0 (x1 )σg1 (x2 ) . . . σgl−1 (xl ),

(1)

where g0 := g and gi := g|x1 x2 ...xi for 1 ≤ i ≤ l − 1.
5. The proof of Theorem 1
The inclusion T VA(n) ⊆ AB 2 (n) follows from the obvious observation that
the rank of a group generated by an n-state time-varying automaton is not
greater than n, as well as from the following result
Proposition 3. In the group Aut({0, 1}∗) the order of any element of finite
order is a power of two.
Proof. Let g ∈ Aut({0, 1}∗) be an element of a finite order d := o(g). For
every 1 ≤ i < d there is a word wi ∈ {0, 1}∗ such that g i (wi ) 6= wi . Let
m = max{|wi | : 1 ≤ i < d} and let g be the restriction of g to the subtree
T := {0, 1}≤m consisting of all binary words of length not greater than m.
Then g ∈ Aut(T ) and o(g) = o(g) = d. It is well known that the group Aut(T )
is isomorphic to the m-iterated wreath product C2 ≀ C2 ≀ . . . ≀ C2 of the cyclic
m
group of order two, and that the order of this wreath product is equal to 22 −1 .
m
In particular, we have the divisibility d|22 −1 , which implies the claim.

The next two propositions concern the generation of cyclic groups by timevarying automata over the binary alphabet equipped, respectively, with a single
state and two states.
Proposition 4. The only groups generated by a time-varying automaton over
the binary alphabet with a single state is the trivial group and the group of order
two, i.e. we have T VA(1) = EA2 (1).

7

Proof. If A = ({0, 1}, {a}, ϕ, ψ) is a time-varying automaton with a single
state a, then the corresponding automaton transformations ai : {0, 1}∗ → {0, 1}∗
(i ∈ N) satisfy the following wreath recursions: ai = (ai+1 , ai+1 )πi , where
πi ∈ Sym({0, 1}). In particular, we have a2i = (a2i+1 , a2i+1 ) for every i ∈ N,
which implies: a2i = id for every i ∈ N. Now, if πi = id for every i ∈ N, then
the group G(A) = ha1 i is trivial, and if πi 6= id for some i ∈ N, then G(A) is
the group of order two.

Proposition 5. Let G be an infinite cyclic group C∞ or a finite cyclic group
C2r of order 2r , where r ∈ N. Then there is a 2-state time-varying automaton
A over the binary alphabet such that G ≃ G(A).
Proof. Let us define the subsets N1 , N2 ⊆ N as follows: N1 = {1, 2, . . . , r},
N2 = N. For each k ∈ {1, 2} let
A[k] = ({0, 1}, {a1, a2 }, ϕ, ψ)
be the 2-state time-varying automaton over the binary alphabet in which the
sequences ϕ, ψ of transition and output functions are defined as follows:

a1 , if j = 2, i ∈ Nk , x = 1,
ϕi (aj , x) =
aj , otherwise,

τ (x), if j = 2, i ∈ Nk ,
ψi (aj , x) =
x,
otherwise
for all i ∈ N, j ∈ {1, 2}, x ∈ {0, 1}, where τ ∈ Sym({0, 1}) is a transposition.
Let aj,i := (aj )i ∈ G(A[k]i ) (j ∈ {1, 2}, i ∈ N) be the automaton transformation of the state aj in its i-th transition.
In the case k = 1 we obtain by the above formulae the following wreath
recursions:

(a1,i+1 , a2,i+1 )τ, if 1 ≤ i ≤ r,
a1,i = (a1,i+1 , a1,i+1 ), a2,i =
(a2,i+1 , a2,i+1 ), if i > r.
Hence a1,i = id for i ∈ N, a2,i = (id, a2,i+1 )τ for 1 ≤ i ≤ r, and a2,i = id for
i > r. In particular, the order o(a2,r ) of the generator a2,r ∈ G(A[1]r ) is equal
to 2, and for every i ∈ {1, . . . , r} we obtain by easy induction on i the equality
o(a2,r+1−i ) = 2i . Hence o(a2,1 ) = 2r and G(A[1]) = ha1,1 , a2,1 i = ha2,1 i ≃ C2r .
In the case k = 2 we have: a1,i = id for i ∈ N and a2,i = (id, a2,i+1 )τ for
i ∈ N. From the last wreath recursion we obtain for any i, s ∈ N the following
wreath recursion for the s-th power of a2,i :
⌊s/2⌋

⌈s/2⌉

as2,i = (a2,i+1 , a2,i+1 )τ s .
In particular, if as2,i = id for some i, s ∈ N, then τ s = id. Hence the number
s/2

s/2

s is even and as2,i = (a2,i+1 , a2,i+1 ) = id. For every j ∈ N we obtain by easy
induction on j the divisibility 2j | s. In particular, the generator a2,1 ∈ G(A[2])
is of infinite order and G(A[2]) = ha1,1 , a2,1 i = ha2,1 i ≃ C∞ .

8

Further, let n ≥ 2 and let G be an arbitrary abelian group from the class
AB 2 (n) such that the rank of this group is equal to n. We provide the construction of an n-state time-varying automaton A over the binary alphabet such that
G is isomorphic to the group G(A) generated by this automaton. As we see in
the following two propositions, our construction depends on whether G contains
a non-trivial torsion part.
Proposition 6. Let n ∈ N and let G be an abelian group of rank n such that
the torsion part of G is a non-trivial 2-group. If n ≥ 2, then there is an n-state
time-varying automaton A over the binary alphabet such that G is isomorphic
to G(A).
Proof. By the fundamental theorem of finitely generated abelian groups there
are integers 1 ≤ d ≤ n and 0 ≤ d′ ≤ n such that d + d′ = n and the group G is
isomorphic to the direct sum
′

d
C2r1 ⊕ . . . ⊕ C2rd ⊕ C∞

(2)

′

d
for some rj ∈ N (1 ≤ j ≤ d), where C∞
denotes the free abelian group of rank
′
′
d in the case d > 0 or the trivial group in the case d′ = 0. Let us denote:

N,
if d′ > 0,
M=
{1, 2, . . . , R}, if d′ = 0,

where R = r1 + . . . + rd , and let N1 ∪ . . . ∪ Nn be an arbitrary partition of the
set M in which: N1 = {1, . . . , r1 }, |Nj | = rj for 1 < j ≤ d and |Nj | = ∞ for
d < j ≤ n.
Let us assume that n ≥ 2 and let A be an n-state time-varying automaton
over the binary alphabet in which the set Q of states consists of the symbols
a1 , . . . , an , and the sequences ϕ = (ϕi )i∈N , ψ = (ψi )i∈N of transition and output
functions are defined as follows:

a1 , if j 6= 1, i ∈ Nj , x = 1,



a2 , if j = 1, i ∈ N1 \ {r1 }, x = 1,
ϕi (aj , x) =
a

2 , if j = 1, i = r1 ,


aj , otherwise,

τ (x), if i ∈ Nj ,
ψi (aj , x) =
x,
otherwise
for all i ∈ N, j ∈ {1, 2, . . . , n}, x ∈ {0, 1}, where τ ∈ Sym({0, 1}) is a transposition. In the case n = 4, d = 3, r1 = 3, r2 = 1, r3 = 2, N1 = {1, 2, 3}, N2 = {4},
N3 = {5, 6}, N4 = N \ {1, 2, 3, 4, 5, 6}, the diagram of the automaton A is depicted in Figure 1 (for clarity, we replaced a large number of edges connecting
two given vertices and having the same direction with a one multi-edge and,
since every multi-edge is labeled by the both letters of the alphabet, we omitted
its labeling).

9

1

a1

2

0

t

t
1

a2 id

3

4

5

6

7

8

9

t

id

id

id

id

id

id

id

id

id

id

id

id

id

id

1

1

0

1

1

id

id

t

0

1

1

a3 id

a4 id

id

id

id

id

t

id

id

id

0

t

0

id

t

t

t
0

0

Figure 1: The automaton from Proposition 6 for n = 4, d = 3, r1 = 3, r2 = 1, r3 = 2.

Let aj,i := (aj )i (1 ≤ j ≤ n, i ∈ N) be the automaton transformation of the
state aj ∈ Q in its i-th transition. Directly by the above formulae, we have the
following wreath recursions for the automorphisms a1,i (i ∈ N):

if i ∈ N1 \ {r1 },
 (a1,i+1 , a2,i+1 )τ,
a1,i =
(a2,r1 +1 , a2,r1 +1 )τ, if i = r1 ,
(3)

(a1,i+1 , a1,i+1 ),
if i ∈
/ N1 .

This implies: a1,i = id for i > r1 . Similarly, for every 2 ≤ j ≤ n the wreath
recursions for aj,i (i ∈ N) satisfy: aj,i = (aj,i+1 , a1,i+1 )τ for every i ∈ Nj and
aj,i = (aj,i+1 , aj,i+1 ) for i ∈
/ Nj . If j 6= 1 and i ∈ Nj , then i ∈
/ N1 and hence
i > r1 . Consequently, we have:

(aj,i+1 , id)τ,
if j 6= 1 and i ∈ Nj ,
aj,i =
(4)
(aj,i+1 , aj,i+1 ), if j 6= 1 and i ∈
/ Nj .
By (4), we obtain for all i, s ∈ N and every j 6= 1:
(
⌈s/2⌉ ⌊s/2⌋
(aj,i+1 , aj,i+1 )τ s , if i ∈ Nj ,
asj,i =
(asj,i+1 , asj,i+1 ),
if i ∈
/ Nj .

The above formula implies that the generator aj,1 ∈ G(A) (j 6= 1) is of infinite
order if and only if |Nj | = ∞, and if |Nj | < ∞ (which implies |Nj | = rj by our
assumption), then o(aj,1 ) = 2rj .
Since a2,i = (a2,i+1 , a2,i+1 ) for every i ∈ N1 , the wreath recursion of the
element b1,i := a1,i a−1
2,i (i ∈ N1 ) satisfies:
b1,i =



(b1,i+1 , id)τ,
(id, id)τ,

In particular, we obtain o(b1,1 ) = 2r1 .
10

if i ∈ N1 \ {r1 },
if i = r1 .

(5)

By (3) and (4), we also obtain the following condition: if aj,i 6= (aj,i+1 , aj,i+1 )
for some i ∈ N and 1 ≤ j ≤ n, then aj,i = (al,i+1 , al′ ,i+1 )π for some l, l′ ∈
{1, 2, j}, π ∈ {id, τ }, and then for every j ′ 6= j the element aj ′ ,i has the following
wreath recursion: aj ′ ,i = (aj ′ ,i+1 , aj ′ ,i+1 ). This implies that for any i ∈ N,
1 ≤ j, j ′ ≤ n, x ∈ {0, 1} there are π ∈ {id, τ } and l, l′ ∈ {1, 2, j, j ′ } such that
aj,i aj ′ ,i |x

=

al,i+1 al′ ,i+1 ,

σaj,i aj′ ,i

=

σaj′ ,i aj,i = π.

aj ′ ,i aj,i |x = al′ ,i+1 al,i+1 ,

Consequently, the elements aj,i and aj ′ ,i commute for all i ∈ N and 1 ≤ j, j ′ ≤ n.
Thus the group G(A) = ha1,1 , . . . , an,1 i = hb1,1 , a2,1 , . . . , an,1 i is abelian.
1
Let kj (1 ≤ j ≤ n) be arbitrary integers for which the product g = bk1,1
·
k2
kn
a2,1 · . . . · an,1 represents the trivial element in G(A). By (4)–(5), we see that
1
the root permutation σg is equal to τ k1 . Hence 2 | k1 and consequently bk1,1
=
k /2

k

k

k

k /2

j
j
j
1
1
) for 2 ≤ j ≤ n. Thus g|0 =
, aj,2
= (aj,2
(b1,2
, b1,2
). By (4), we have: aj,1

k /2

1
n
2
. Since g|w = id for every w ∈ {0, 1}∗, a trivial
· . . . · akn,2
· ak2,2
g|1 = b1,2
induction on i gives for every i ∈ N1 and every w ∈ {0, 1}i−1 the divisibility

k /2i−1

2i−1 | k1 and the equality g|w = b1,i1
r1 −1

k /2

1
b1,r
1

n
. In particular g|w =
· ak2,i2 · . . . · akn,i

2
n
· ak2,r
· . . . · akn,r
for every w ∈ {0, 1}r1−1 . Again by (4)–(5), we see that
1
1
r1 −1

the root permutation of the last product is equal to τ k1 /2
, which implies
2
n
2r1 | k1 . Since b1,r1 |0 = b1,r1 |1 = id, we obtain: gw = ak2,r
·
. . . · akn,r
for
1 +1
1 +1
r1
every w ∈ {0, 1} and hence:
2
n
ak2,r
· . . . · akn,r
= id.
1 +1
1 +1

(6)

Let us fix i ∈ N \ {1, . . . , r1 }. Let lj (2 ≤ j ≤ n) be any integers for which
the product
n
2
(7)
· . . . · aln,i
h = al2,i
represents the trivial element in the group G(Ai ). Since the sets Nj (2 ≤ j ≤ n)
are pairwise disjoint, we have two possibilities: (i) there is a unique 2 ≤ j0 ≤ n
/ Nj . In the case (i), by
such that i ∈ Nj0 , (ii) for every 2 ≤ j ≤ n we have i ∈
the wreath recursion (4), we see that the root permutation σh is equal to τ lj0 .
Since h = id, we obtain: 2 | lj0 , and consequently, the sections h|0 , h|1 coincide
l

l

/2

and they both arise from (7) by replacing the factor ajj00,i with ajj00,i+1 and the
0
for j 6= j0 with
factors alj,i

lj
,
aj,i+1

i.e. we have:
l

l

/2

l

+1
−1
n
2
.
· . . . · aln,i+1
· ajj00,i+1 · ajj00+1,i+1
· . . . · ajj00−1,i+1
h|0 = h|1 = al2,i+1

l

j
In the case (ii) the sections h|0 , h|1 both arise from h by replacing each aj,i

l

j
n
2
. Since
· . . . · aln,i+1
, i.e. we have: h|0 = h|1 = al2,i+1
(2 ≤ j ≤ n) with aj,i+1
∗
h|w = id for every w ∈ {0, 1} , we obtain by the trivial induction on t ∈ N that
for every t ∈ N and every 2 ≤ j ≤ n the number lj is divisible by 2µj,t , where

µj,t = |Nj ∩ {i, i + 1, . . . , i + t − 1}|.
11

Thus, if for some 2 ≤ j ≤ n the set Nj is infinite, then the sequence (µj,t )t∈N
is unbounded, which implies lj = 0. If |Nj | < ∞ for some 2 ≤ j ≤ n, then
we obtain the divisibility: 2µj | lj , where µj = |Nj ∩ {i′ ∈ N : i′ ≥ i}|. By our
assumption, we have Nj ∩ {1, 2, . . . , r1 } = ∅ and |Nj | = rj for every 2 ≤ j ≤ n.
In particular, if i = r1 + 1, then we obtain in that case: µj = |Nj | = rj , and
hence o(aj,1 ) | lj . Applying this result to the equality (6), we obtain: kj = 0 for
every 2 ≤ j ≤ n such that |Nj | = ∞ and o(aj,1 ) | kj for every 2 ≤ j ≤ n such
that |Nj | < ∞. Consequently, we obtain
G(A) ≃ hb1,1 i ⊕ ha2,1 i ⊕ . . . ⊕ han,1 i ≃ G.

Now, it remains to consider the case of abelian groups of rank n (n ≥ 2)
without torsion elements. Note that every such a group must be the free abelian
group of rank n, which follows from the property that every finitely generated
abelian group is a direct sum of cyclic groups.
Proposition 7. If n ≥ 2, then there is an n-state time-varying automaton A
over the binary alphabet which generates a group isomorphic to the free abelian
group of rank n.
Proof. Let n ∈ N \ {1} and let N2 ∪ . . . ∪ Nn be an arbitrary partition of the
set N \ {1} in which |Nj | = ∞ for every 2 ≤ j ≤ n.
Let A be an n-state time-varying automaton over the binary alphabet in
which the set Q of states consists of the symbols a1 , . . . , an , and the sequences
ϕ = (ϕi )i∈N , ψ = (ψi )i∈N of transition and output functions are defined as
follows:

 a1 , if j 6= 1, i ∈ Nj , x = 1,
ϕi (aj , x) =
a2 , if j = 1, i = 1, x = 1,

aj , otherwise,

τ (x), if j 6= 1, i ∈ Nj ,
ψi (aj , x) =
x,
otherwise
for all i ∈ N, j ∈ {1, 2, . . . , n}, x ∈ {0, 1}.
As before, we denote by aj,i := (aj )i (1 ≤ j ≤ n, i ∈ N) the automaton
transformation of the state aj ∈ Q in its i-th transition. By the above formulae,
we have the following wreath recursions for the automorphisms a1,i (i ∈ N):

(a1,i+1 , a2,i+1 ), if i = 1,
a1,i =
(a1,i+1 , a1,i+1 ), if i 6= 1.
This implies that a1,i = id for i 6= 1, and consequently we obtain:

(id, a2,i+1 ), if i = 1,
a1,i =
(id, id),
if i 6= 1.
12

(8)

The wreath recursions for aj,i (i ∈ N, j 6= 1) satisfy (4), and similarly as in the
previous proof, we obtain that the group G(A) is abelian. Let kj (1 ≤ j ≤ n)
1
n
be arbitrary integers for which the product g = ak1,1
· . . . · akn,1
represents the
trivial element in G(A). By (4) and by (8), we obtain:
g|0
g|1

=

2
n
ak2,2
· . . . · akn,2
,

=

k1 +k2
a2,2

· ...·

n
akn,2
.

(9)
(10)

Since g|0 = id, we can apply to the product (9) the same reasoning as in the
previous proof and obtain that for every t ∈ N \ {1} and every 2 ≤ j ≤ n the
number kj is divisible by 2µj,t , where µj,t = |Nj ∩ {2, . . . , t}|. Similarly, since
g|1 = id, we use the product (10) and obtain that the number k1 + k2 is divisible
by 2µ2,t for every t ∈ N \ {1}. Since each Nj is an infinite set, we obtain: kj = 0
for every 1 ≤ j ≤ n. Thus G(A) is isomorphic to the free abelian group of rank
n, which finishes the proof of the proposition.

Finally, we need to observe that if G is a group generated by an n-state
(n ∈ N) time-varying (Mealy) automaton A over a finite alphabet X, then for
every n′ > n the group G is also generated by an n′ -state time-varying (Mealy)
automaton over X. Indeed, the required n′ -state automaton is obtained by
adding certain new symbols q1 , . . . , qn′ −n to the set of states of A together
with the following formulae for transition and output functions: ϕi (qj , x) = qj ,
ψi (qj , x) = x for all i ∈ N, j ∈ {1, . . . , n′ − n}, x ∈ X. Then the automaton
transformations (qj )i ∈ Aut(X ∗ ) (i ∈ N, 1 ≤ j ≤ n′ − n) are all trivial, and the
transformations corresponding to the “old” states remain unchanged. Hence, by
Propositions 5–7, we obtain the inclusion T VA(n) ⊇ AB 2 (n) for every n > 1,
which finishes the proof of Theorem 1.
6. The proof of Theorem 2
Let G = G(A) be the group generated by an arbitrary Mealy automaton A
over the binary alphabet and let us denote the following subsets of G:
• G1 = {g ∈ G : σg = id} = {g ∈ G : ∀x ∈ {0, 1} g(x) = x} – the first level
stabilizer,
• IG = {g ∈ G : g 2 = id} – the set of involutions,
• G2 = {g 2 : g ∈ G} – the set of squares in G.
Lemma 1. If G2 = G21 , then G is an elementary abelian 2-group.
Proof. Suppose that G2 = G21 . We have to show that IG = G. So, let g ∈ G
be arbitrary. It can be seen by the formula (1) that the equality g 2 = id follows
from the following condition: g 2 |w ∈ G1 for every w ∈ {0, 1}∗. But, since
G21 ⊆ G1 , it is enough to show that g 2 |w ∈ G21 for every w ∈ {0, 1}∗. We use
induction on the length of a word w. The claim is obvious in the case |w| = 0,
13

as then we have g 2 |w = g 2 |ǫ = g 2 ∈ G2 = G21 . Suppose that g 2 |w ∈ G21 for some
w ∈ {0, 1}∗ . Then g 2 |w = h2 for some h ∈ G1 . Since h = (h|0 , h|1 ), we obtain:
g 2 |w = ((h|0 )2 , (h|1 )2 ), and consequently g 2 |wx = (g 2 |w )|x = (h|x )2 ∈ G2 = G21
for x ∈ {0, 1}. An inductive argument finishes the proof of Lemma 1.

Lemma 2. If IG ⊆ G1 , then IG = {id}.
Proof. Suppose that IG ⊆ G1 and let g ∈ IG be arbitrary. We must show
that g = id. As before, we see by the formula (1) that we need to show the
condition: g|w ∈ G1 for every w ∈ {0, 1}∗. Since IG ⊆ G1 , it is enough to
show that g|w ∈ IG for every w ∈ {0, 1}∗. We use induction on the length of
a word w. The claim is obvious in the case |w| = 0. Suppose that g|w ∈ IG
for some w ∈ {0, 1}∗. Since IG ⊆ G1 , we have: g|w = (g|w0 , g|w1 ). Hence
id = (g|w )2 = ((g|w0 )2 , (g|w1 )2 ). Thus (g|wx )2 = id for x ∈ {0, 1}, i.e. g|wx ∈ IG
for x ∈ {0, 1}. An inductive argument finishes the proof.

Proposition 8. If the group G is abelian, then G is torsion free or it is an
elementary abelian 2-group.
Proof. Suppose that the group G is non-trivial, abelian and not torsion free.
Then there is g ∈ G with 1 < o(g) < ∞. By Proposition 3, there is r ∈ N such
r−1
that o(g) = 2r . Then g 2
is a non-trivial element from IG , and consequently,
by Lemma 2, the set IG \ G1 is not empty. Let h ∈ IG \ G1 . For every g ∈ G
we have: if g ∈
/ G1 , then gh ∈ G1 and g 2 = g 2 h2 = (gh)2 ∈ G21 . Consequently,
2
we obtain G = G21 and, by Lemma 1, the group G is an elementary abelian
2-group, which finishes the proof of Proposition 8.

Remark 2. The statement of Proposition 8 can also be derived by using the
concept of a 1/2-endomorphism of a group, which defines its state-closed representation on the tree {0, 1}∗ – see [12] and Proposition 3.4 therein.
Now, the inclusion MA(n) ⊆ F A(n − 1) ∪ EA2 (n) (n ≥ 2) follows directly
by Proposition 8 and by the following proposition (see Proposition 3.1 in [17]):
Proposition 9 ([17]). For every n ∈ N there is no n-state Mealy automaton
over the binary alphabet which generates the free abelian group of rank n.
Since the equality MA(1) = EA2 (1) is trivial, we see by the observation
at the end of the previous section that to show for every n ≥ 2 the converse
inclusion (i.e. MA(n) ⊇ F A(n − 1) ∪ EA2 (n)), we only need to show that the
free abelian group of rank n − 1 as well as the elementary abelian 2-group of
rank n is generated by an n-state Mealy automaton over the binary alphabet.
The case of a free abelian group follows directly by the following well known
construction of so-called “sausage” automata (see [7] for example):
Proposition 10 ([7]). Let A = ({0, 1}, Q, ϕ, ψ) be an n-state (n ≥ 2) Mealy
automaton in which Q = {a1 , . . . , an } and the transition and output functions

14

are defined as follows:

aj−1 ,



an ,
ϕ(aj , x) =
a1 ,



a1 ,

if
if
if
if

2 < j ≤ n,
j = 2, x = 0,
j = 2, x = 1,
j = 1,

ψ(aj , x) =



τ (x),
x,

if j = 2,
otherwise

for all j ∈ {1, 2, . . . , n} and x ∈ {0, 1}. Then the group G(A) is isomorphic to
the free abelian group of rank n − 1.
The case of an elementary abelian 2-group follows by the following
Proposition 11. Let A = ({0, 1}, Q, ϕ, ψ) be an n-state (n ∈ N) Mealy automaton in which Q = {a1 , . . . , an } and the transition and output functions are
defined as follows:


aj−1 , if 2 ≤ j ≤ n,
τ (x), if j = 1,
ϕ(aj , x) =
ψ(aj , x) =
an ,
if j = 1,
x,
otherwise
for all j ∈ {1, 2 . . . , n} and x ∈ {0, 1}. Then G(A) is isomorphic to the elementary abelian 2-group of rank n.
Proof. To simplify notation we will use the notation aj (1 ≤ j ≤ n) for the
automaton transformation (aj )1 ∈ G(A). By the formulae for transition and
output functions, we have the following wreath recursions for the generators aj :

(aj−1 , aj−1 ), if 2 ≤ j ≤ n,
aj =
(11)
(an , an )τ,
if j = 1.
In particular, for any 1 ≤ j, j ′ ≤ n and any x ∈ {0, 1} there are 1 ≤ i, i′ ≤ n and
π ∈ {id, τ } such that (aj aj ′ )|x = ai ai′ , (aj ′ aj )|x = ai′ ai and σaj aj′ = σaj′ aj = π.
Thus for any 1 ≤ j, j ′ ≤ n the elements aj , aj ′ commute, and hence the group
G(A) is abelian. For every 1 ≤ j ≤ n we have: aj (0n ) = 0j−1 10n−j , and hence
aj 6= id. On the other hand, by (11), we see that for every 1 ≤ j ≤ n there is
1 ≤ i ≤ n such that a2j = (a2i , a2i ). Thus a2j = id for every 1 ≤ j ≤ n. Finally,
suppose that for some integers kj (1 ≤ j ≤ n) the product g = ak11 · . . . · aknn
represents the trivial element in the group G(A). Then the root permutation
σg is equal to τ k1 , and hence 2 | k1 . We also see by wreath recursions (11) that
for every t ∈ {0, . . . , n − 1} and every word w ∈ {0, 1}t the section g|w is equal
to
k
k
n
1
a1t+1 · a2t+2 · . . . · akn−t
· akn−t+1
· . . . · aknt .
Thus id = σg|w = τ kt+1 , and consequently 2 | kt+1 , which implies the isomorphism G(A) ≃ ha1 i ⊕ . . . ⊕ han i ≃ C2n .

References
[1] V. Aleshin. A free group of finite automata. Mosc. Univ. Math. Bull.
38(1983), no.4, 10–13.
15

[2] I. Bondarenko, R. Grigorchuk, R. Kravchenko, Y. Muntyan, V. Nekrashevych, D. Savchuk, and Z. Sunik. Groups generated by 3-state automata
over a 2-letter alphabet. II. Journal of Mathematical Sciences, Vol. 156,
No. 1, 2009.
[3] A. Erschler. Piecewise automatic groups. Duke Math. J., 134:3 (2006), 591–
613.
[4] A. Erschler. Automatically presented groups. Groups Geom. Dyn., (2007),
47–59.
[5] Y.Glasner, S.Mozes. Automata and square complexes. Geom. Dedicata
111(2005), 43–64.
[6] R. Grigorchuk. Solved and Unsolved Problems Around One Group. in Infinite Groups: Geometric, Combinatorial and Dynamical Aspects. Progress
in Mathematics Series, Vol. 248, 2005.
[7] R. Grigorchuk, V. Nekrashevych, V. Sushchanskyy. Automata, Dynamical Systems and Groups. Proceedings of Steklov Institute of Mathematics,
231:128–203, 2000.
[8] R. Grigorchuk. Some topics in the dynamics of group actions on rooted
trees. Proceedings of the Steklov Institute of Mathematics. July 2011, Volume 273, Issue 1, pp 64–175.
[9] V.B. Kudryavtsev, S.V. Aleshin, and A.S. Podkolzin. Introduction to the
Theory of Automata (Nauka, Moscow, 1985) [in Russian].
[10] B. Mikolajczak. Algebraic and structural automata theory, translated from
the Polish Annals of Discrete Mathematics, Vol. 44 (North-Holland Publishing Co., Amsterdam, 1991).
[11] V. Nekrashevych. Self-similar Groups. Am. Math. Soc., Providence, RI,
2005, Math. Surv. Monogr. 117.
[12] V. Nekrashevych, S.Sidki. Automorphisms of the binary tree: state-closed
subgroups and dynamics of 1/2-endomorphisms, In T.W. Mller, editor,
Groups: Topological, Combinatorial and Arithmetic Aspects, volume 311 of
LMS Lecture Notes Series, pages 375–404, 2004.
[13] M. Vorobets, Ya. Vorobets. On a free group of transformations defined by
an automaton, Geom. Dedicata, 124 (2007), 237–249.
[14] A. Woryna. On permutation groups generated by time-varying Mealy automata. Publ. Math. Debrecen, 67(1-2):115–130, 2005.
[15] A. Woryna. On generation of wreath products of cyclic groups by two
state time varying Mealy automata. Int. J. Algebra Comput., 16(2):397–
415, 2006.
16

[16] A. Woryna. The concept of duality for automata over a changing alphabet
and generation a free group by such automata. Theoret. Comput. Sci.,
412(45):6420–6431, 2011.
[17] A. Woryna. Automaton ranks of some self-similar groups. Lecture Notes in
Computer Science, 2012, Volume 7183/2012, 514–525.
[18] A. Woryna. The concept of self-similar automata over a changing alphabet
and lamplighter groups generated by such automata. Theoret. Comput.
Sci., 482:96–110, 2013.
[19] A. Woryna. On some universal construction of minimal topological generating sets for inverse limits of iterated wreath products of non-Abelian
finite simple groups. J Algebr Comb, Vol. 42, Issue 2, pp 365-390, 2015.

17

