Finite automaton actions of free products of groups
It is shown that for groups G and H that act faithfully by finite state automorphisms on regular rooted trees their free product G∗H admits a faithful action by finite state automorphisms on some regular rooted tree.
Gespeichert in:
| Datum: | 2017 |
|---|---|
| Hauptverfasser: | , |
| Format: | Artikel |
| Sprache: | English |
| Veröffentlicht: |
Інститут прикладної математики і механіки НАН України
2017
|
| Schriftenreihe: | Algebra and Discrete Mathematics |
| Online Zugang: | http://dspace.nbuv.gov.ua/handle/123456789/156019 |
| 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: | Finite automaton actions of free products of groups / M. Fedorova, A. Oliynyk // Algebra and Discrete Mathematics. — 2017. — Vol. 23, № 2. — С. 230-236. — Бібліогр.: 4 назв. — англ. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
irk-123456789-156019 |
|---|---|
| record_format |
dspace |
| spelling |
irk-123456789-1560192019-06-18T01:31:14Z Finite automaton actions of free products of groups Fedorova, M. Oliynyk, A. It is shown that for groups G and H that act faithfully by finite state automorphisms on regular rooted trees their free product G∗H admits a faithful action by finite state automorphisms on some regular rooted tree. 2017 Article Finite automaton actions of free products of groups / M. Fedorova, A. Oliynyk // Algebra and Discrete Mathematics. — 2017. — Vol. 23, № 2. — С. 230-236. — Бібліогр.: 4 назв. — англ. 1726-3255 2010 MSC:20E08, 20E06, 20F65. http://dspace.nbuv.gov.ua/handle/123456789/156019 en Algebra and Discrete Mathematics Інститут прикладної математики і механіки НАН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
English |
| description |
It is shown that for groups G and H that act faithfully by finite state automorphisms on regular rooted trees their free product G∗H admits a faithful action by finite state automorphisms on some regular rooted tree. |
| format |
Article |
| author |
Fedorova, M. Oliynyk, A. |
| spellingShingle |
Fedorova, M. Oliynyk, A. Finite automaton actions of free products of groups Algebra and Discrete Mathematics |
| author_facet |
Fedorova, M. Oliynyk, A. |
| author_sort |
Fedorova, M. |
| title |
Finite automaton actions of free products of groups |
| title_short |
Finite automaton actions of free products of groups |
| title_full |
Finite automaton actions of free products of groups |
| title_fullStr |
Finite automaton actions of free products of groups |
| title_full_unstemmed |
Finite automaton actions of free products of groups |
| title_sort |
finite automaton actions of free products of groups |
| publisher |
Інститут прикладної математики і механіки НАН України |
| publishDate |
2017 |
| url |
http://dspace.nbuv.gov.ua/handle/123456789/156019 |
| citation_txt |
Finite automaton actions of free products of groups / M. Fedorova, A. Oliynyk // Algebra and Discrete Mathematics. — 2017. — Vol. 23, № 2. — С. 230-236. — Бібліогр.: 4 назв. — англ. |
| series |
Algebra and Discrete Mathematics |
| work_keys_str_mv |
AT fedorovam finiteautomatonactionsoffreeproductsofgroups AT oliynyka finiteautomatonactionsoffreeproductsofgroups |
| first_indexed |
2025-07-14T08:16:42Z |
| last_indexed |
2025-07-14T08:16:42Z |
| _version_ |
1837610077626826752 |
| fulltext |
Algebra and Discrete Mathematics RESEARCH ARTICLE
Volume 23 (2017). Number 2, pp. 230–236
c© Journal “Algebra and Discrete Mathematics”
Finite automaton actions
of free products of groups
Mariia Fedorova and Andriy Oliynyk
Communicated by A. P. Petravchuk
Abstract. It is shown that for groups G and H that act
faithfully by finite state automorphisms on regular rooted trees
their free product G ∗ H admits a faithful action by finite state
automorphisms on some regular rooted tree.
The class of groups that act faithfully on regular rooted trees by
finite state automorphisms (equivalently, groups defined by finite initial
automata over finite alphabets) constitute a remarkable family among
residually finite groups. It is rich of many interesting and important groups
with a solid influence on different branches of mathematics. One can easily
show that this class is closed under finite direct products. The Kaloujnine-
Krasner theorem implies that it is closed under finite extensions as well.
The purpose of this short note is to show that this class is closed under
finite free products. Thus, we positively solve the following problem from
Kourovka Notebook (see [1, Problem 16.85]).
Suppose that groups G,H act faithfully on a regular rooted tree by
finite state automorphisms. Can their free product G ∗H act faithfully on
a regular rooted tree by finite state automorphisms?
In fact, to obtain the affirmative solution it is sufficient to prove the
following
Theorem 1. The free product FAutTn ∗ FAutTn is isomorphic to a
subgroup of FAutT3n, n > 2.
2010 MSC: 20E08, 20E06, 20F65.
Key words and phrases: rooted tree, tree automorphism, finite automaton, free
product.
M. Fedorova, A. Oliynyk 231
All notions and notations we use are standard for groups defined
by finite automata and can be found in [2] and [3]. In particular, by
FAutTm,m > 2 we denote the group of all finite state automorphisms of
m-regular rooted tree.
The idea of the main construction used in the proof is influenced by
the paper [4].
Proof of Theorem 1. We start with three disjoint alphabets X, Y and Z,
each of cardinality n. We assume that their elements are enumerated, i.e.
let
X = {x0, . . . , xn−1}, Y = {y0, . . . , yn−1} and Z = {z0, . . . , zn−1}.
Consider two isomorphic copies G and H of the group FAutTn as groups
whose elements are defined by finite initial automata over alphabets X
and Y correspondingly. The elements of the group FAutT3n will be defined
by finite initial automata over the alphabet X ∪ Y ∪ Z. We will construct
isomorphic embeddings Ψ1 and Ψ2 of the groups G and H correspondingly
into the group FAutT3n and show that the subgroup generated by their
images splits into the free product Ψ1(G) ∗ Ψ2(H). The proof is divided
into three parts.
Step 1. Construction of Ψ1,Ψ2.
We describe the map Ψ1 : G → FAutT3n. The map Ψ2 is defined
analogously replacing X by Y and vice versa in the constructions below.
For each element g ∈ G fix a finite initial automaton
Ag = (Q,X, λ, µ, qg)
such that g is defined by Ag. Here Q denotes the set of inner states of
Ag, λ and µ its transition and output functions respectively, qg the initial
state.
The definition of Ψ1 consists of two stages.
At the first stage we define another automaton Bg by adding to the
set Q of states of Ag two states sg, dg. The functions λ, µ are extended
by the equalities
λ(sg, x0) = qg, λ(sg, x) = dg, x ∈ X \ {x0}, λ(dg, x) = dg, x ∈ X,
µ(sg, x) = µ(dg, x) = x, x ∈ X.
Then
Bg = (Q ∪ {sg, dg},X, λ, µ, sg).
232 Finite automaton actions of free products
Denote by ψ1(g) the element of the group G defined by the automaton Bg.
Then the rule
g 7→ ψ1(g)
defines an isomorphic embedding of G into G. Indeed, the definition of
the automaton Bg implies that for arbitrary x ∈ X, w ∈ X
∗ the following
equality holds
(xw)ψ1(g) =
{
xwg, if x = x0,
xw otherwise.
Hence, ψ1 is injective and preserves multiplication.
Note, that the map ψ1 is nothing but the identification of G with the
first term in the direct product
G(0) × . . .×G(n−1), G(i) ≃ G, 0 6 i 6 n− 1.
This direct product is a natural subgroup of G as soon as we look at the
action of G on X
∗.
Let us proceed to the second stage of the definition. We construct a
finite initial automaton Cg over the alphabet X ∪ Y ∪ Z. Its set of inner
states is Q ∪ {sg, dg} ∪Q× Z.
The transition function λ is extended by the following rules:
λ(dg, y) = dg, y ∈ Y, λ(dg, z) = sg, z ∈ Z,
λ(q, y) = sg, q ∈ Q ∪ {sg} ∪Q× Z, y ∈ Y,
λ(sg, z) = sg, z ∈ Z, λ(q, z) = (q, z), q ∈ Q, z ∈ Z,
λ((q, z), t) = sg, q ∈ Q, z ∈ Z, t ∈ Y ∪ Z,
λ((q, z), x) = λ(sg, x), q ∈ Q, z ∈ Z, x ∈ X.
The output function µ is extended on new states by the rule:
µ((q, z), x) = µ(sg, x), q ∈ Q, z ∈ Z, x ∈ X.
Let us define the action of the output function µ in new states on letters
from Y. For arbitrary q ∈ Q, i, j ∈ {0, . . . , n−1} the value µ(q, x(j−i) mod n)
is a well-defined letter x ∈ X. Then x = xk for some k ∈ {0, . . . , n− 1}
and we define
µ((q, zi), yj) = y(k+i) mod n.
In other words, the permutation πY on the alphabet Y defined in the state
(q, zi) “mimics” the permutation πX on X defined in the state q. More
M. Fedorova, A. Oliynyk 233
precisely, if we denote by σ the one-to-one correspondence between X and Y
given by the rule xj 7→ y(j+k) mod n, 0 6 j 6 n− 1, then πY = σ(πX(σ−1)).
None of the rest of the states change letters from Y. Finally, none of
the states change letters from Z.
Then the automaton
Cg = (Q ∪ {sg, dg} ∪Q× Z,X ∪ Y ∪ Z, λ, µ, sg)
is well-defined.
Denote by Ψ1(g) the element of the group FAutT3n defined by the
automaton Cg.
Step 2. Ψ1,Ψ2 are isomorphic embeddings.
As above, we consider Ψ1 only. The proof for Ψ2 is completely analo-
gous.
Let g ∈ G, w ∈ (X ∪ Y ∪ Z)∗. We examine the word wΨ1(g) to show
that Ψ1 preserve multiplication in G. The main idea is to split w into
sub-words such that under the action of Ψ1(g) each image coincides with
the one obtained by the action of g. Under the action of Ψ1(g) in w letters
from X,Y,Z are transformed into the letters of the same alphabet. The
letters from Z are preserved under the action of Ψ1(g).
For w ∈ X
∗ the definition of the automaton Cg directly implies the
equality
wΨ1(g) = wψ1(g).
In particular, the mapping Ψ1 is injective.
Let the first letter of w belongs to X and differs from x0. If w contain
no letters from Z then w is a fixed point under Ψ1(g). In other case
w = xw1zw2 for some w1 ∈ (X ∪ Y)∗, z ∈ Z, w2 ∈ (X ∪ Y ∪ Z)∗. Then
wΨ1(g) = (xw1zw2)Ψ1(g) = xw1zw
Ψ1(g)
2 .
Assume that w ∈ (X ∪ Y ∪ Z)∗ \ X
∗ and the first letter of w either
belongs to Y ∪ Z or equals x0. Then w can be uniquely written in the
form
w = w1u1w2u2,
where w1, w2 ∈ X
∗, u1 ∈ (Y ∪ Z)+, u2 ∈ (X ∪ Y ∪ Z)∗ and the word w1
either empty or its first letter equals x0. In the former case from the
definition of Cg we obtain the following equality:
(w1u1w2u2)Ψ1(g) = w1u1(w2u2)Ψ1(g).
234 Finite automaton actions of free products
In the latter case if the first letter of u1 belongs to Y or the length
of u1 is greater than 1 and the first and the second letters of u1 belong
to Z the definition of Cg implies
(w1u1w2u2)Ψ1(g) = w
Ψ1(g)
1 u1(w2u2)Ψ1(g).
It is left to consider two cases.
Case I. Let w1 = x0w3 for some w3 ∈ X
∗, u1 = z for some z ∈ Z
and the word w2 is non-empty. In this case w = x0w3zxw4u2 for some
x ∈ X, w4 ∈ X
∗ and we obtain
(x0w3zxw4u2)Ψ1(g) = x0w
g
3z(xw4u2)Ψ1(g).
Case II. Let w1 = x0w3 for some w3 ∈ X
∗ and u1 = zyu3 for some z ∈
Z, y ∈ Y, u3 ∈ (Y ∪ Z)∗. Then y = yj , z = zi for some i, j ∈ {0, . . . , n− 1},
w = x0w3ziyju3w2u2 and we obtain
(x0w3ziyju3w2u2)Ψ1(g) = (x0w3ziyj)
Ψ1(g)u3(w2u2)Ψ1(g).
Further we obtain
(x0w3ziyj)
Ψ1(g) = (x0w3)ψ1(g)ziy(i+k) mod n,
where number k is uniquely determined by the equality
(x0w3x(j−i) mod n)Ψ1(g) = x0w
g
3xk.
The last equality means that Ψ1(g) acts on words of the form x0w3ziyj
as g acts on words w3x(j−i) mod n, i.e. corresponding permutation groups
are isomorphic.
Step 3. 〈Ψ1(G),Ψ2(H)〉 splits as Ψ1(G) ∗ Ψ2(H).
It is required to prove that for arbitrary positive integer m and non-
identity elements g1, . . . , gm ∈ G, h1, . . . , hm ∈ H the product
Ψ1(g1)Ψ2(h1) . . .Ψ1(gm)Ψ2(hm)
defines a non-trivial permutation on the set (X ∪ Y ∪ Z)∗. Denote by
a1, b1, . . . , am, bm, the elements
Ψ1(g1), Ψ1(g1)Ψ2(h1), . . . , Ψ1(g1)Ψ2(h1) . . .Ψ1(gm)Ψ2(hm)
correspondingly. We will find words
u1, . . . , um, um+1 ∈ X
∗ and v1, . . . , vm ∈ Y
∗
M. Fedorova, A. Oliynyk 235
and letters
t1, . . . , tm, s1, . . . , sm ∈ Z
such that the word w of the form
w = u1t1v1s1 . . . umtmvmsmum+1
is not a fixed point under the action of the element bm.
For any non-trivial element g ∈ G there exist a non-empty word from
X
∗ that is not a fixed point under the action of g. In each non-fixed word
of the shortest possible length the last letter does not coincide with the
last letter of its image under g. Note, that all other letters are preserved
under the action of g. Hence, there exist a word w(g) ∈ X
∗ and numbers
i(g), k(g) ∈ {0, . . . , n− 1} such that i(g) 6= k(g) and
(w(g)xi(g))
g = w(g)xk(g).
Denote j(g) = (i(g) − k(g)) mod n. Then j(g) 6= 0. In the same way for
any non-trivial element h ∈ H one can choose a word w(h) ∈ Y
∗ and
numbers i(h), k(h) ∈ {0, . . . , n− 1} such that i(h) 6= k(h) and
(w(h)yi(h))
h = w(h)yk(h).
Denote j(h) = (i(h) − k(h)) mod n. Then j(h) 6= 0.
Now define
u1 = x0w(g1), ur = xj(hr−1)w(gr), 2 6 r 6 m, um+1 = xj(hm),
vr = yj(gr)w(hr), 1 6 r 6 m, and tr = zk(gr), sr = zk(hr), 1 6 r 6 m.
Hence, we put
w = x0w(g1)zk(g1)yj(g1)w(h1)zk(h1)xj(h1) . . .
. . . xj(hm−1)w(gm)zk(gm)yj(gm)w(hm)zk(hm)xj(hm).
The definition of Ψ1 and Ψ2 implies that under the action of mappings
a1, b1, . . . , bm−1, am, bm in the word w letters
yj(g1), xj(h1), . . . , xj(hm−1), yj(gm), xj(hm)
one by one become
y0, x0, . . . , x0, y0, x0.
236 Finite automaton actions of free products
More precisely, one can verify by induction the following 2m equalities
wa1 = (u1)a1t1y0w(h1)s1u2 . . . umtmvmsmum+1,
wb1 = (u1t1v1)b1s1x0w(g2) . . . umtmvmsmum+1,
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
wam = (u1t1v1s1 . . . um)amtmy0w(gm)smum+1,
wbm = (u1t1v1s1 . . . umtmvm)bmsmx0.
In particular, wbm 6= w. The proof is complete.
References
[1] E.I. Khukhro (ed.), V.D. Mazurov (ed.), Unsolved Problems in Group Theory. The
Kourovka Notebook. 18th edition, Novosibirsk (2014). (English version available
online at http://arxiv.org/abs/1401.0300)
[2] R.I.Grigorchuk, V.V.Nekrashevych, V.I.Sushchanskii Automata, Dynamical Systems,
and Groups, Proceedings of the Steklov Institute of Mathematics. –2000. – 231. –
p.128 –203.
[3] V.V.Nekrashevych Self-similar groups, Mathematical Surveys and Monographs, 117.
AMS, Providence, RI, 2005. xii+231 pp.
[4] V.Salo A note on subgroups of automorphism groups of full shifts, Ergodic Theory
and Dynamical Systems, 2016, 1-13. doi:10.1017/etds.2016.95
Contact information
M. Fedorova,
A. Oliynyk
Taras Shevchenko National University of Kyiv,
Volodymyrska 60, Kyiv, Ukraine, 01033
E-Mail(s): mfed@univ.kiev.ua,
olijnyk@univ.kiev.ua
Received by the editors: 10.06.2017
and in final form 13.06.2017.
|