On the finite state automorphism group of a rooted tree
The normalizer of the finite state automorphism group of a rooted homogeneous tree in the full automorphism group of this tree was investigated. General form of elements in the normalizer was obtained and countability of the normalizer was proved.
Gespeichert in:
| Datum: | 2002 |
|---|---|
| 1. Verfasser: | |
| Format: | Artikel |
| Sprache: | English |
| Veröffentlicht: |
Інститут прикладної математики і механіки НАН України
2002
|
| Schriftenreihe: | Algebra and Discrete Mathematics |
| Online Zugang: | http://dspace.nbuv.gov.ua/handle/123456789/154680 |
| 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: | On the finite state automorphism group of a rooted tree / Y. Lavrenyuk // Algebra and Discrete Mathematics. — 2002. — Vol. 1, № 1. — С. 79–87. — англ. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
irk-123456789-154680 |
|---|---|
| record_format |
dspace |
| spelling |
irk-123456789-1546802019-06-16T01:31:58Z On the finite state automorphism group of a rooted tree Lavrenyuk, Y. The normalizer of the finite state automorphism group of a rooted homogeneous tree in the full automorphism group of this tree was investigated. General form of elements in the normalizer was obtained and countability of the normalizer was proved. 2002 Article On the finite state automorphism group of a rooted tree / Y. Lavrenyuk // Algebra and Discrete Mathematics. — 2002. — Vol. 1, № 1. — С. 79–87. — англ. 1726-3255 2000 Mathematics Subject Classification 20E08, 20F28.. http://dspace.nbuv.gov.ua/handle/123456789/154680 en Algebra and Discrete Mathematics Інститут прикладної математики і механіки НАН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
English |
| description |
The normalizer of the finite state automorphism
group of a rooted homogeneous tree in the full automorphism group
of this tree was investigated. General form of elements in the normalizer was obtained and countability of the normalizer was proved. |
| format |
Article |
| author |
Lavrenyuk, Y. |
| spellingShingle |
Lavrenyuk, Y. On the finite state automorphism group of a rooted tree Algebra and Discrete Mathematics |
| author_facet |
Lavrenyuk, Y. |
| author_sort |
Lavrenyuk, Y. |
| title |
On the finite state automorphism group of a rooted tree |
| title_short |
On the finite state automorphism group of a rooted tree |
| title_full |
On the finite state automorphism group of a rooted tree |
| title_fullStr |
On the finite state automorphism group of a rooted tree |
| title_full_unstemmed |
On the finite state automorphism group of a rooted tree |
| title_sort |
on the finite state automorphism group of a rooted tree |
| publisher |
Інститут прикладної математики і механіки НАН України |
| publishDate |
2002 |
| url |
http://dspace.nbuv.gov.ua/handle/123456789/154680 |
| citation_txt |
On the finite state automorphism group of a rooted tree / Y. Lavrenyuk // Algebra and Discrete Mathematics. — 2002. — Vol. 1, № 1. — С. 79–87. — англ. |
| series |
Algebra and Discrete Mathematics |
| work_keys_str_mv |
AT lavrenyuky onthefinitestateautomorphismgroupofarootedtree |
| first_indexed |
2025-07-14T06:42:27Z |
| last_indexed |
2025-07-14T06:42:27Z |
| _version_ |
1837603590462504960 |
| fulltext |
Algebra and Discrete Mathematics RESEARCH ARTICLE
Number 1. (2002). pp. 79–87
c© Journal ”Algebra and Discrete Mathematics”
On the finite state automorphism group of a
rooted tree
Yaroslav Lavrenyuk
Communicated by V.I. Sushchansky
Dedicated to V. V. Kirichenko on the occasion of his 60th birthday
Abstract. The normalizer of the finite state automorphism
group of a rooted homogeneous tree in the full automorphism group
of this tree was investigated. General form of elements in the nor-
malizer was obtained and countability of the normalizer was proved.
1. Introduction
Automorphism groups of rooted trees are studied strongly last years in
connection with their application in geometric group theory, theory of
dynamic systems, ergodic and spectral theory, and that they also contain
various interesting subgroups with extremal properties. In particular,
there are free constructions among them, various constructions of groups
of intermediate growth, etc (see [GNS] and its bibliography).
Among subgroups of automorphism group of a rooted tree the finite
state automorphism group arise the big interest [Su].
In the paper [NS] the number of problems on the finite state auto-
morphism group of a rooted tree was posed. This work partially solves
one of these problems. In the paper the normalizer of the finite state
automorphism group of a rooted tree in the full automorphism group
of this tree was investigated. General form of elements in normalizer
was obtained and countability of normalizer was proved. According to
Key words and phrases: group automorphisms, automorphisms of rooted trees,
finite automata.
2000 Mathematics Subject Classification 20E08, 20F28..
80 On the finite state automorphism group of a rooted tree
[L, LN] this normalizer is isomorphic to the automorphism group of the
finite state automorphism group of a rooted tree.
2. Preliminary
Definition 1. A synchronous automaton is a set A = 〈XI ,XO, Q, π, λ〉,
where
1. XI and XO are finite sets (respectively, the input and the output
alphabets),
2. Q is a set (the set of internal states of the automaton),
3. π : XI × Q −→ Q is a mapping (transition function), and
4. λ : XI × Q −→ XO is a mapping (output function).
Automaton A is finite if |Q| < ∞.
Henceforth, we will consider the automata whose input and output
alphabets coincide. Let X = XI = XO be a finite alphabet, X∗ be the
set of all words over X, Xω be the set of all ω-words (infinite words) over
X.
A permutation of the set X∗ or Xω is called a (finitely) automatic if
it is caused by a (finite) automaton over alphabet X. All finitely auto-
matic permutations form subgroup of the group GA(X) of all automatic
permutations over X. Let us denote this subgroup by FGA(X).
For the alphabet X we can construct the word tree TX (see also
[GNS]). The vertices of the tree TX are the elements of the set X∗. Two
vertices u and v are incident if and only if u = vx or v = ux for a certain
x ∈ X. The vertex ∅ is the root of the tree.
The group AutTX of all automorphisms TX is isomorphic to the group
GA(X) of all automatic permutations over X.
For every two vertices u, v of the tree TX (i. e. u, v ∈ V (TX)) we
define the distance between u and v, denoted by d(u, v), to be equal to
the length of the path connecting them.
For rooted tree TX with the root v0 = ∅ and an integer n ≥ 0 we
define the level number n (the sphere of the radius n) as the set
Vn = {v ∈ V (TX) : d(v0, v) = n} .
Let us say that vertex v of rooted tree TX lies under vertex w, if path,
that connects vertice v and v0, contains vertex w.
Let us denote by Tv the full subtree consisting of all vertices, that lie
under the vertex v with the root v.
Y. Lavrenyuk 81
Let G ≤ AutTX be an automorphism group of the rooted tree TX .
Then for every vertex v of the tree TX and a nonnegative integer n:
1. The group of all automorphisms g ∈ G fixing every vertex outside
the subtree Tv is called the vertex group (or the rigid stabilizer of
the vertex) and is denoted by rist v.
2. The group of all automorphisms fixing all vertices of the level num-
ber n is denoted by stabG(n) or just stab(n) and is called the level
stabilizer.
An automorphism group G is said to be level-transitive if it acts
transitively on all the levels of the rooted tree TX .
An automorphism group G is said to be weakly branch if it is level-
transitive and for every vertex v of the tree the vertex group is nontrivial.
Statement 1. [LN] If G is a weakly branch group then the centralizer
CAut TX
(G) of G in the automorphism group AutTX is trivial.
In the word tree TX every subtree Tv, where v ∈ V (TX), can be
naturally identified with the whole tree TX by the map:
πv : x1x2 . . . xnxn+1 . . . xm 7→ xn+1xn+2 . . . xm,
where x1x2 . . . xn = v.
So, if g ∈ stab(n) then the action of g on Tv for every v ∈ Vn can be
identified by πv with the isometry gv of TX defined by the equality
πv (ug) = (πv (u))gv .
The isometry gv is called the state of g in v or the restriction of g on v.
When g ∈ stab(n), we write g = (gv1
, gv2
, . . . , gvrn )(n), where
{v1, v2, . . . , vrn} = Vn, r = |X|.
Let T n
X be the subtree of the rooted tree TX , that consists of all vertices
on a distance no greater than n from the root. Then the group AutT n
X
is naturally embedded in the group AutTX and the latter is decomposed
into semidirect product
AutTX = stab(n) ⋋ AutT n
X .
So for each g ∈ AutTX we can write
g = gnag = (gv1
, gv2
, . . . , gvrn )(n)ag, (1)
82 On the finite state automorphism group of a rooted tree
where gn ∈ stab(n), and ag ∈ AutT n
X .
By the state of an element gn in the vertex v ∈ Vn we mean the state
of an element g ∈ AutTX in the vertex v.
An automorphism g ∈ AutTX is called finite state automorphism if
the set of all its states is finite.
All finite state automorphisms form a subgroup of the group AutTX .
The group FGA(TX ) of all finite state automorphisms TX is isomorphic
to the group FGA(X) of all finitely automatic permutations.
End is an infinite sequence of vertices (v0, v1, v2, . . .), vk ∈ Vk such
that d(vk, vk+1) = 1 for every nonnegative integer k. Every ω-word
determines an end of the tree TX . Conversely every end of the tree TX
determines some ω-word.
An ω-word (end) w is called periodic if there exists the word v ∈ X∗
such that w = v · v · v · . . . = vω. We say that w is ultimately periodic if
there exist words u, v ∈ X∗ such that w = u · vω.
Let Xup be the set of all ultimately periodic words over alphabet X
(of the ends of the tree TX).
Lemma 2. [Su]
1. The set Xup is an orbit of the group FGA(X).
2. The action of the group FGA(TX) is faithful on this orbit.
3. The permutation group (FGA(TX ),Xup) is an imprimitive group
and its domain of imprimitivity are intersections of domains of
imprimitivity of permutation group (AutTX ,Xω) with the set Xup.
3. Main results
In the paper the normalizer N = NAutTX
(FGA(TX )) of the group
FGA(TX ) in the group AutTX of all automorphisms of rooted tree TX ,
|X| ≥ 2 is investigated.
As it was shown in [L] (see also [LN]) the normalizer N is isomorphic
to the automorphism group of the group A = FGA(TX ).
In the paper the next results on the structure of normalizer (of auto-
morphism group) have been obtained:
Theorem 3. Let g ∈ N . For every ultimately periodic end u the sequence
of states {g(n) | n ∈ N} that correspond to the end u (i.e. states in vertices
pertinent to this end) is ultimately periodic.
Y. Lavrenyuk 83
Theorem 4. For an element g ∈ N there exist m,k ∈ N, a, b ∈
FGA(TX) and h ∈ N such that
h = (h, ..., h)(m)a,
g = (h, ..., h)(k)b.
Corollary 1. The normalizer N = NAutTX
(FGA(TX )), |X| ≥ 2, is
countable.
4. Proofs
Let |X| = r ≥ 2, and let u0 = 00 . . . be an end of the tree Tr.
Lemma 5. An element of the group N turn an ultimately periodic end
to an ultimately periodic one. That is N : Xup → Xup.
Proof. Since Xup is an orbit of the group A, it is sufficient to prove the
statement for one ultimately periodic end. Let us consider, for example,
the end u0.
Let w be not an ultimately periodic end. Suppose there is g ∈ N
which turn the end w to the end u0.
Let a = (a, 1, ..., 1)(1)τ lie in A where τ is a cyclic permutation of
order r − 1 with 0 as fixed point. Therefore, ua
0 = u0, and u0 is the only
fixed end of the element a.
We have gag−1 : w → w. Since g acts on set of ends as permutation,
we have that the end w is the only fixed end of the element gag−1.
Since w /∈ Xup, among subtrees with roots in the vertices of the end
w there are infinitely many different subtrees. That is, gag−1 /∈ A. We
have contradiction.
This lemma implies
Corollary 2. 1. The set Xup is an orbit of the group N .
2. Action of the group N is faithful on this orbit.
Let g ∈ N , and
g = gnag = (gv1
, gv2
, . . . , gvrn )(n)ag
be decomposition (1) for g where {v1, v2, . . . , vrn} = Vn.
Lemma 6. Let g ∈ N . For each Vn the elements gv1
, gv2
, . . . , gvrn are
contained in the same left (right) coset of A.
84 On the finite state automorphism group of a rooted tree
Proof. We can assume ag = 1. Let vi, vj ∈ Vn and A ∋ b : vi → vj be
such that bn = 1. We have
(bg)vj
= g−1
vi
gvj
.
Since bg ∈ A then g−1
vi
gvj
∈ A for all vi, vj ∈ Vn.
Corollary 3. For an element g ∈ N there exists a ∈ A such that ga ∈
stab(n) and (ga)vi
= (ga)v1
for all i = 2, ..., r.
Let T be a rooted tree. We will denote by kn(v) the number of vertices
belonging to Vn+1 and adjacent to v for each integer n ≥ 0 and v ∈ Vn.
A tree is spherically homogeneous if kn(v) does not depend on v ∈ Vn. If
kn does not depend on n too then the tree is called homogeneous. For
example word tree TX is homogeneous.
For spherically homogeneous tree the sequence χ = 〈k0, k1, . . .〉 is
called tree index and such a tree is denoted by Tχ. We will use denotation
k̄ = {k, k, ...} for homogeneous tree.
For denotation of vertices of the tree Tχ we will use two indices: first
one is the number of the level containing this vertex, second one is the
number of this vertex (in the lexigraphic ordering) among the all vertices
of the given level.
We will need the next fact
Lemma 7. The group AutTχ contains finitely generated weakly branch
subgroups for all χ = 〈k1, k2, ...〉 (ki ≥ 2).
Proof. The group AutT2̄ contains finitely generated weakly branch sub-
groups, for example, the Grigorchuk 2-group Gr is a such one [GNS].
The natural embeddings {0, 1} in {0, ....ki − 1} define the natural
embedding T2̄ in Tχ and the group AutT2̄ is being ebedded in AutTχ.
Let us define h = h1 ∈ AutTχ recurrently
hi = (hi+1, 1, ..., 1)
(1)σi
where σi is the cyclic permutation (vi2, ..., viki
).
Let H = 〈Gr, h〉. The group H acts level-transitively on Tχ. We
use induction by level number n. The group Gr acts transitively on
{v11, v12} ⊂ V1 and h cyclically permutes the vertices v12, ..., v1ki
. Thus
H acts transitively on the first level. Let H acts transitively on Vn. It
is sufficient to prove that for the level number n + 1 the group H acts
transitively on the vertices that are adjacent to the vertex vn1 from level
number n. In this case the proof is similar to the proof for the level
number one with substitution hk1...kn for h.
Y. Lavrenyuk 85
Therefore H is a level-transitive subgroup of Tχ.
Since there are vertices with infinite rigid stabilizers in G on each
level we conclude that rigid stabilizer in H of each vertex is infinite.
Thus, H is a finitely generated weakly branch subgroup of group
Tχ.
Remark 1. For homogeneous tree Tk̄ group H is contained in the group
FGA(Tk̄).
Proof of theorem 3. Let |X| = r. Since the group FGA(X) acts
transitively on Xup, it is sufficient to prove the theorem only for one
ultimately periodic end u0, and g : u0 → u0.
1. r = 2.
Let αi ∈ A (i = 1, ..., k) such that αi = (αi, ai)
(1) where a1, ..., ak
are elements genereting a weakly branch group H (for example,
Grigorchuk group). Then
αg : u0 −→ u0, (2)
(αg)vn2
= a
gvn2
i (3)
where vn2 ∈ Vn and vn2 = 00 . . . 01.
Since αg
i ∈ A and taking into account (2) we conclude that se-
quences {a
gvn2
i | n ∈ N} are ultimately periodic for i = 1, ..., k.
Therefore there are pi, n0 ∈ N such that for i = 1, ..., k and n ≥ n0
the next equality holds
a
gvn+pi,2
i = a
gvn2
i .
Thus
gvn+pi,2
g−1
vn2
∈ CAut T2
(〈ai〉).
Taking p = gcd(p1, ..., pk) we have
a
gvn+p,2
i = a
gvn2
i ,
gvn+p,2
g−1
vn2
∈ CAut T2
(〈ai〉)
for i = 1, ..., k and n ≥ n0. Therefore using (1) we have
gvn+p,2
g−1
vn2
∈
⋂k
i=1 CAut T2
(〈ai〉) = CAut T2
(〈a1, ..., ak〉) =
= CAut T2
(H) = 1
for n ≥ n0.
Thus {gvn2
| n ∈ N} is ultimately periodic, and, taking into account
(2), we have that {gvn1
| n ∈ N} is ultimately periodic too.
86 On the finite state automorphism group of a rooted tree
2. r > 2.
Let αi ∈ A (i = 1, ..., k) such that αi = (αi, ai, ..., ai)
(1)σ where
a1, ..., ak are elements genereting a weakly branch group H (such
group exists by statement 7), and σ is the permutation on r points:
σ = (0)(123...r − 1).
Denote (1, ai, ..., ai)
(1)σ by bi (i = 1, ..., k).
All elements gvn1
, α1, b1, ..., αk, bk act naturally on Tχ where χ =
{r − 1, r, r, ...} that is from the tree Tr truncate the subtree Tv10
.
For αi, bi (i=1,...,k) the next equations hold:
αg : u0 −→ u0, (4)
(αg)vn1
|Tχ = b
gvn1
i |Tχ (5)
where vn1 ∈ Vn and vn1 = 00 . . . 00.
Since αg
i ∈ A and taking into account (4)we get that sequences
{b
gvn1
i |Tχ | n ∈ N} are ultimately periodic for i = 1, ..., k. Therefore
there are pi, n0 ∈ N such that for i = 1, ..., k and n ≥ n0 the next
equality holds
b
gvn+pi,1
i |Tχ = b
gvn1
i |Tχ .
Thus
(gvn+pi,1
g−1
vn1
)|Tχ ∈ CAut Tχ(〈bi|Tχ〉).
Taking p = gcd(p1, ..., pk) we have
b
gvn+p,1
i |Tχ = b
gvn1
i |Tχ ,
(gvn+p,1
g−1
vn1
)|Tχ ∈ CAut Tχ(〈bi|Tχ〉)
for i = 1, ..., k and n ≥ n0. Therefore in virtue of (1) and that H1 =
〈b1|Tχ , ..., bk |Tχ〉 is weakly branch subgroup of the group AutTχ we
have
(gvn+p,1
g−1
vn1
)|Tχ ∈
⋂k
i=1 CAut Tχ(〈bi|Tχ〉) =
= CAut Tχ(〈b1|Tχ , ..., bk |Tχ〉) = CAut Tχ(H1) = 1
for n ≥ n0.
Thus {gvn1
|Tχ | n ∈ N} is ultimately periodic, and we have by (4)
that {gvn1
| n ∈ N} is ultimately periodic too.
Y. Lavrenyuk 87
Proof of theorem 4. It follows from the corollary 2 that there is
b1 ∈ A such that gb1 : u0 −→ u0. The sequence {(gb1)vn1
| n ∈ N} is
ultimately periodic by the theorem 3. Therefore there is k ∈ N such that
{(gb1)vn1
| n ≥ k} is periodic.
Let us denote by h = (gb1)vn1
. There is b2 ∈ A such that
gb1b2 = (h, ..., h)(k)
by the corollary 3. For h we have h : u −→ u, and the sequence {hvn1
| n ∈
N} is periodic. Let this period be m.
There is a1 ∈ A such that
ha1 = (h, ..., h)(m)
by the corollary 3. Let us denote by a = a−1
1 , b = (b1b2)
−1. We have
h = (h, ..., h)(m)a,
g = (h, ..., h)(k)b,
and statement is proved.
References
[GNS] R. I. Grigorchuk, V. V. Nekrashevych, V. I. Sushchansky, Automata, dynam-
ical systems and groups. Proc. V.A. Steklov Inst. Math., Vol. 231. 2000, 134-215.
[Su] V.I.Sushchansky, The groups of finitely automatic permutations. Dopovidi NAN
Ukrainy. 1999, No. 2, 29-32. (In Ukrainian).
[L] Lavreniuk Ya., Automorphisms of wreath branch groups. Visnyk Kyivskogo Uni-
versytetu. Ser. fiz. mat. nauk. 1999, No. 1, 50-57. (In Ukrainian).
[LN] Lavreniuk Ya., Nekrashevych V., Rigidity of branch groups acting on rooted
trees. Geometriae Dedicata. February, 89 2002, No. 1, 159-179.
[NS] V. V. Nekrashevych, V. I. Sushchansky, Some problems on groups of finitely
automatic permutations. Matematychni Studii, 13 (2000), No. 1, 93-96.
Contact information
Y. Lavrenyuk Kyiv Taras Shevchenko University, Ukraine
E-Mail: yar lav@hotmail.com
Received by the editors: 23.09.2002.
|