The growth function of the adding machine
We compute the growth function of the generalized adding machine and show that its generating function is not algebraic.
Gespeichert in:
| Datum: | 2018 |
|---|---|
| 1. Verfasser: | |
| Format: | Artikel |
| Sprache: | English |
| Veröffentlicht: |
Інститут прикладної математики і механіки НАН України
2018
|
| Schriftenreihe: | Algebra and Discrete Mathematics |
| Online Zugang: | http://dspace.nbuv.gov.ua/handle/123456789/188365 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Zitieren: | The growth function of the adding machine / V. Skochko // Algebra and Discrete Mathematics. — 2018. — Vol. 25, № 2. — С. 303–310. — Бібліогр.: 8 назв. — англ. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
irk-123456789-188365 |
|---|---|
| record_format |
dspace |
| spelling |
irk-123456789-1883652023-02-27T01:27:54Z The growth function of the adding machine Skochko, V. We compute the growth function of the generalized adding machine and show that its generating function is not algebraic. 2018 Article The growth function of the adding machine / V. Skochko // Algebra and Discrete Mathematics. — 2018. — Vol. 25, № 2. — С. 303–310. — Бібліогр.: 8 назв. — англ. 1726-3255 2010 MSC: 20M35, 68Q70. http://dspace.nbuv.gov.ua/handle/123456789/188365 en Algebra and Discrete Mathematics Інститут прикладної математики і механіки НАН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
English |
| description |
We compute the growth function of the generalized adding machine and show that its generating function is not algebraic. |
| format |
Article |
| author |
Skochko, V. |
| spellingShingle |
Skochko, V. The growth function of the adding machine Algebra and Discrete Mathematics |
| author_facet |
Skochko, V. |
| author_sort |
Skochko, V. |
| title |
The growth function of the adding machine |
| title_short |
The growth function of the adding machine |
| title_full |
The growth function of the adding machine |
| title_fullStr |
The growth function of the adding machine |
| title_full_unstemmed |
The growth function of the adding machine |
| title_sort |
growth function of the adding machine |
| publisher |
Інститут прикладної математики і механіки НАН України |
| publishDate |
2018 |
| url |
http://dspace.nbuv.gov.ua/handle/123456789/188365 |
| citation_txt |
The growth function of the adding machine / V. Skochko // Algebra and Discrete Mathematics. — 2018. — Vol. 25, № 2. — С. 303–310. — Бібліогр.: 8 назв. — англ. |
| series |
Algebra and Discrete Mathematics |
| work_keys_str_mv |
AT skochkov thegrowthfunctionoftheaddingmachine AT skochkov growthfunctionoftheaddingmachine |
| first_indexed |
2025-07-16T10:23:33Z |
| last_indexed |
2025-07-16T10:23:33Z |
| _version_ |
1837798695984168960 |
| fulltext |
“adm-n2” — 2018/7/24 — 22:32 — page 303 — #141
Algebra and Discrete Mathematics RESEARCH ARTICLE
Volume 25 (2018). Number 2, pp. 303–310
c© Journal “Algebra and Discrete Mathematics”
The growth function of the adding machine
Volodymyr Skochko
Communicated by R. Grigorchuk
Abstract. We compute the growth function of the general-
ized adding machine and show that its generating function is not
algebraic.
Introduction
Abstract automata are mathematical models of machines and computa-
tional processes. There are many classes of automata, and in this paper we
consider (initial) automata-transducers, which generate an output string
depending on an input string. Therefore, automata-transducers generate
transformations of words over alphabet. The standard question is how to
realize a given transformation by an automaton, and what is the minimal
number of states required for such implementation.
Another problem is to find for a given automaton transformation f
the minimal number of states required to implement composition f (n) =
f ◦f ◦. . .◦f (n times). In order to solve this problem we have to understand
the behavior of the growth function γA(n) of an (initial) automaton A,
which counts the number of states in the n-th iteration of A after its
minimization. Note that here we should deal with automata with fixed
initial state, while the theory of automaton groups deals with groups
generated by all transformations obtained by changing the initial state
The author would like to thank his advisor Ievgen Bondarenko for his help, guidance
and time spent during discussions and corrections of this article.
2010 MSC: 20M35, 68Q70.
Key words and phrases: automaton, growth function, adding machine.
“adm-n2” — 2018/7/24 — 22:32 — page 304 — #142
304 The growth function of the adding machine
of a given automaton. In this case, the growth function of an automaton
counts the number of different elements of length n in the semigroup
generated by this automaton. We have a connection with growth of groups
which has essential influence in both group theory and automata theory.
The most spectacular example is the automaton group of Grigorchuk [7],
which was the first example of a group of intermediate growth between
polynomial and exponential. Later, Bartholdi, Reznykov, and Sushchansky
constructed the smallest automaton with intermediate growth function
[1] and many examples of automata with polynomial growth of irrational
degree [2]. The growth function of automata plays important role in
decision problems around automaton group: see [3, 4] for applications to
the word problem and [5] for the order and conjugacy problems.
In this paper we consider the growth function of initial automata,
namely, the generalized adding machine. The standard adding machine
(odometer) realizes addition of one to binary numbers. Therefore, its
growth function γ(n) counts the minimal number of states required to
realize an automaton that adds n to binary numbers. We consider a
generalized version of the adding machine and give an exact formula for
its growth function. As a corollary, we obtain that the generating function
of the growth function is algebraic only in the trivial cases.
1. Automata and their growth functions
Definition 1. An automaton A is a tuple (X,S, λ), where X is a finite
set (alphabet) with at least two elements, S is the set of states, and
λ : S ×X → X × S is the output-transition map.
An automaton A = (X,S, λ) is usually identified with the directed
labeled graph with the vertex set S, where an arrow s → t with label x|y
exists if and only if λ(s, x) = (y, t). We say that a state t is reachable from
a state s if there is a directed path in A from s to t. If the labels x1|y1,
x2|y2,. . .xn|yn are read along this path, then we use notation t = s|x1x2...xn
.
We also say that t is a (sub)state of s at the n-th level.
The composition of automata A = (X,S1, λ1) and B = (X,S2, λ2) is
the automaton A ◦ B = (X,S1 × S2, λ3), where λ3 is defined as follows.
Let we have denoted λ2(s2, x) = (z, t2), λ1(s1, z) = (y, t1) then
λ3((s1, s2), x) = (y, (t1, t2)).
Definition 2. An automaton A with fixed state s ∈ S is called initial
and is denoted by As.
“adm-n2” — 2018/7/24 — 22:32 — page 305 — #143
V. Skochko 305
Every initial automaton As defines a transformation of the space X∗ of
all finite words over X. The output As(x1x2 . . . xn) is defined recursively
as follows:
As(x1x2 . . . xn) = y1y2 . . . yn
if λ(s, x1) = (y1, t) and At(x2 . . . xn) = y2 . . . yn. Informally speaking,
the initial automaton reads the input word letter by letter, generates an
output letter depending on the current state, and changes its current state
according to the transition map. Note that the terminal state of As after
processing a word x1x2 . . . xn is s|x1x2...xn
.
The composition of two initial automata As and Bt over the alphabet
X is the initial automaton (A◦B)(s,t). It is easy to see that the composition
of automata agrees with the composition of transformations:
(As ◦Bt)(x1x2 . . . xn) = (A ◦B)(s,t)(x1x2 . . . xn) for all xi ∈ X, n ∈ N.
Different states of an automaton may define the same transformation
of X∗. The following concept eliminates this difficulty.
Definition 3. Two automata A and B over the same alphabet X are
called equivalent if for every state s of A there exists a state t of B such
that the transformations defined by As and Bt are equal, and vise versa.
The minimal automaton Min(A) is an automaton equivalent to A with
the property that different states define different transformations.
For an initial automaton As, its minimal automaton Min(As) is a
subautomaton of Min(A) with initial state t, where As and Min(A)t
define the same transformation, and every state of Min(As) is reachable
from t.
Note that for finite automata the minimal automaton Min(A) has
the least number of states required to realize all transformations defined
by the states of an automaton A. The automaton Min(As) has the least
number of states required to realize the transformation As.
Definition 4. The growth function of an initial automaton As is defined
as the function which counts the number of states in the minimized n-th
power of As, e.g.
γAs
(n) = γs(n) = #States(Min(A(n)
s )), n ∈ N,
where A
(n)
s = As ◦ . . . ◦As (n times).
“adm-n2” — 2018/7/24 — 22:32 — page 306 — #144
306 The growth function of the adding machine
In other words, if we take the automaton Min(A(n)) and its state
sn = (s, . . . , s) (n times), which corresponds to n-th time iteration of As,
then the growth function γAs
(n) counts the number of all states sn|v for
v ∈ X∗ in Min(A(n)).
One of the classical examples of automata is the adding machine.
Definition 5. The adding machine on d digits is the initial automaton
over the alphabet X = {0, 1, . . . , d− 1} with two states S = {e, a}, initial
state a, where the output-transition map is defined by
λ(e, x) = (x, e) for all x ∈ X,
λ(a, x) =
{
(0, a) if x = d− 1,
(x+ 1, e) otherwise.
We denote the adding machine by its initial state a.
The state e defines the trivial transformation, while the transformation
defined by the state a corresponds to the addition of 1 in the position
numeral system with base d. In other words a(x1x2 . . . xn) = y1y2 . . . yn if
and only if
1 + x1 + x2d+ . . .+ xnd
n−1 ≡ y1 + y2d+ . . .+ ynd
n−1 mod dn
for all n ∈ N. Hence, the growth function γa(n) gives us the minimal
number of states required to construct the automaton that realizes the
addition of n to numbers written in base d.
In this paper we consider the following generalization of the adding
machine.
Definition 6. For every permutation π on the alphabet X = {0, . . . , d−1}
the generalized adding machine is defined as the initial automaton over
X with two states S = {e, aπ} and initial state aπ, where the output-
transition map is defined by
λ(e, x) = (x, e) for all x ∈ X,
λ(aπ, x) =
{
(π(d− 1), aπ) if x = d− 1,
(π(x), e) otherwise.
2. Main results
First we compute the growth function of the standard adding machine.
“adm-n2” — 2018/7/24 — 22:32 — page 307 — #145
V. Skochko 307
Theorem 1. The growth function γ(n) of the adding machine a on d
digits can be computed as follows. Let n = ε0 + ε1d+ . . .+ εmdm be the
expansion of n in base d and p be the first non-zero position.
1) If d > 2 then
γ(n) =
{
2m− p+ 2 if εm = 1,
2m− p+ 3 otherwise.
2) If d = 2 then
γ(n) =
{
2m− p+ 2 if εm−1 = 1 or p = m,
2m− p+ 1 otherwise.
Proof. Each state of an is of the form ai for some 0 6 i 6 n, and since
the adding machine has infinite order, ai = aj only when i = j. Let A(n)
be the set of all nonnegative integers i such that ai is a state of an. Then
γ(n) counts the number of elements in A(n). We show how to construct
A(n) iteratively and then conclude the result.
Let us divide n by d with reminder: n = dq + r, 0 6 r < d. Then the
states of an on the first level are
an|x =
{
aq+1 for x = 0, . . . , r − 1,
aq for x = r, . . . , d− 1.
(1)
Notice that q < q + 1 < n for all n and d, except for n = d = 2 when
q + 1 = n. The above rule suggests an iterative construction of the set
A(n). Let Ak(n) consists of all integers i such that an|v = ai for some
word v ∈ Xk; we have A(n) = ∪k>0Ak(n). The equation (1) tells us
that one can construct Ak+1(n) from Ak(n) as follows: for every number
y ∈ Ak(n), if d divides y, then put
[
y
d
]
into Ak+1(n); otherwise put two
numbers
[
y
d
]
and
[
y
d
]
+ 1. Since each time we divide by d, it is direct to
get the following properties of Ak(n) by induction:
1) Ak(n) =
{[
n
dk
]}
for k = 0, 1, . . . , p;
2) Ak(n) =
{[
n
dk
]
,
[
n
dk
]
+ 1
}
for k = p+ 1, . . . ,m− 1;
3) Ak(n) are disjoint for k = 0, 1, . . . ,m− 1;
4) A(n) = A0(n) ∪A1(n) ∪ . . . ∪Am+1(n);
The last two sets in the union may have non-empty intersection and must
be considered more carefully.
5) If p = m then in this case n = εmdm and εm 6= 0. So we get
Ak(n) = {εmdm−k} for k = 0, 1, . . . ,m and Am+1(n) = {0, 1}.
Therefore, Am(n) ∪ Am+1(n) = {0, 1, εm} and its cardinality is
equal to 2 or 3 depending on whether εm is equal to 1 or not.
“adm-n2” — 2018/7/24 — 22:32 — page 308 — #146
308 The growth function of the adding machine
6) If p 6 m− 1 and d > 2, then
Am(n) ∪Am+1(n) = {0, 1, εm, εm + 1}
and this set is disjoint withAk(n) for k < m (note that the cardinality
of the union is 3 or 4 depending on whether εm is equal to 1 or not).
Indeed, in this case
Am−1(n) =
{
{[ n
dm−1 ]} if p = m− 1,
{[ n
dm−1 ], [
n
dm−1 ] + 1} if p < m− 1.
and
[
n
dm−1
]
>
[
n
dm
]
+ 1.
Therefore, Am(n) = {[ n
dm
], [ n
dm
] + 1} = {εm, εm + 1} and it is disjoint
with Ak(n) for k < m. But 1 6 εm < εm+1 6 d. Hence, Am+1(n) = {0, 1}
by construction and we get Am(n) ∪Am+1(n) = {0, 1, εm, εm + 1}.
7) If p 6 m−1 and d = 2, then Am(n)∪Am+1(n) = {0, 1, 2}. However,
this set may have a non-empty intersection with Am−1(n); this
happens exactly in the case εm−1 = 0 when 2 ∈ Am−1(n).
In this case εm = 1 and [ n
2m−1 ] = 2εm + εm−1 = 2 + εm−1. Therefore,
Am−1(n) =
{3} if p = m− 1,
{3, 4} if εm−1 = 1, p 6= m− 1,
{2, 3} otherwise.
In any case we have Am(n) = {1, 2} and Am+1(n) = {0, 1}. So we get
that Am(n) ∪Am+1(n) = {0, 1, 2}.
The value of the growth function γ(n) immediately follows from items
1)-7).
Corollary 1. Let aπ be the generalized adding machine on d digits with
π ∈ Sym(X).
1) If π(d−1) = d−1, then aπ has finite order |aπ| = |π| and its growth
function is periodic.
2) If π(d− 1) 6= d− 1, then γaπ(n) coincides with the growth function
of the standard adding machine on l digits, where l is the length of the
orbit of d − 1 under π. More precisely, let n = ε0 + ε1l + . . .+ εmlm be
the expansion in base l of n and p be the first non-zero position. Then
(a) if l > 2 then
γaπ(n) =
{
2m− p+ 2 if εm = 1,
2m− p+ 3 otherwise.
“adm-n2” — 2018/7/24 — 22:32 — page 309 — #147
V. Skochko 309
(b) if l = 2 then
γaπ(n) =
{
2m− p+ 2 if εm−1 = 1 or p=m,
2m− p+ 1 otherwise.
Proof. 1) If π(d − 1) = d − 1, then aπ changes only the first letter not
equal to d− 1 by π. Hence, akπ = e, where k is the order of π.
2) Without loss of generality we can suppose that the orbit of d− 1
under π corresponds to the cycle τ = (d− l, . . . , d− 1). Then the subtree
{d − l, . . . , d − 1}∗ of X∗ is invariant under the action of aπ and the
restricted action is exactly the standard adding machine on l letters.
Therefore, anπ has the same states at words from {d− l, . . . , d− 1}∗ as the
standard adding machine. For a word v not in {d− l, . . . , d− 1}∗ (here v
contains a letter x 6∈ {d− l, . . . , d− 1}), we have anπ|v = e. The statement
follows.
Corollary 2. The growth function of the generalized adding machine aπ
on d digits for π(d− 1) 6= d− 1 satisfies
[
log n
log l
]
+ 2 6 γ(n) 6 2
[
log n
log l
]
+ cdfor all n > 1,
where cd = 2 for d = 2 and cd = 3 for d > 2. Moreover, the lower and the
upper bounds are reached for infinitely many values of n.
Let us recall that the generating function of a function γ : N∪{0} → N
is the formal power series Γ(t) =
∑
n>0 γ(n)t
n. A formal power series is
called algebraic if it is algebraic over the field of rational functions.
Corollary 3. Let aπ be the generalized adding machine on d digits. The
generating function of γaπ(n) is algebraic if and only if π(d− 1) = d− 1;
moreover, in this case the generating function is rational.
Proof. If π(d− 1) = d− 1, then the growth function of aπ is periodic and
its generating function is rational.
The coefficients of an algebraic power series
∑
n>0 cnt
n have asymptotic
of the type cn ∼ CnαAn (see theorem VII.8 in [6]) and cannot be of
logarithmic growth as in Corollary 2.
Corollary 4. The growth function of the standard adding machine has
non-algebraic generating function.
“adm-n2” — 2018/7/24 — 22:32 — page 310 — #148
310 The growth function of the adding machine
References
[1] L. Bartholdi, I. I. Reznykov, V. I. Sushchansky, The smallest Mealy automaton of
intermediate growth, J. Algebra 295 (2006), no. 2, 387–414.
[2] L. Bartholdi, I. I. Reznykov, A Mealy machine with polynomial growth of irrational
degree, Internat. J. Algebra Comput. 18 (2008), no. 1, 59–82.
[3] I. Bondarenko, Growth of Schreier graphs of automaton groups, Mathematische
Annalen 354 (2012), no. 2, 765–785.
[4] I. Bondarenko, The word problem in Hanoi Towers groups, Algebra and Discrete
Mathematics 17 (2014), no. 2, 248–255.
[5] I. Bondarenko, N.Bondarenko, S.Sidki, F.Zapata, On the conjugacy problem for
finite-state automorphisms of regular rooted trees (with an appendix by Raphael
M. Jungers), Groups, Geometry, and Dynamics 7 (2013), no. 2, 323–355.
[6] Ph. Flajolet, R. Sedgewick, Analytic combinatorics, Cambridge University Press,
2009.
[7] R. I. Grigorchuk, On the Milnor problem of group growth, Dokl. Akad. Nauk SSSR
271 (1983), no. 1, 30-33.
[8] R.I. Grigorchuk, V.V. Nekrashevych, V.I. Sushchansky, Automata, dynamical
systems and groups, Proceedings of the Steklov Institute of Mathematics 231
(2000), 128–203.
Contact information
V. Skochko Department of Mechanics and Mathematics,
Kyiv National Taras Shevchenko Univ.,
Volodymyrska str., 64, 01033 Kyiv, Ukraine
E-Mail(s): vovaskochko@gmail.com
Received by the editors: 22.10.2016
and in final form 27.11.2016.
|