On conjugacy in groups of finite-state automorphisms of rooted trees
We show that the conjugacy of elements of finite order in the group of finite-state automorphisms of a rooted tree is equivalent to their conjugacy in the group of all automorphisms of the rooted tree. We establish a criterion for conjugacy between a finite-state automorphism and the adding machine...
Saved in:
| Date: | 2008 |
|---|---|
| Main Authors: | , |
| Format: | Article |
| Language: | Ukrainian English |
| Published: |
Institute of Mathematics, NAS of Ukraine
2008
|
| Online Access: | https://umj.imath.kiev.ua/index.php/umj/article/view/3250 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | Ukrains’kyi Matematychnyi Zhurnal |
| Download file: |  |
Institution
Ukrains’kyi Matematychnyi Zhurnal| _version_ | 1860509305218793472 |
|---|---|
| author | Russev, A. V. Руссєв, А. В. |
| author_facet | Russev, A. V. Руссєв, А. В. |
| author_sort | Russev, A. V. |
| baseUrl_str | https://umj.imath.kiev.ua/index.php/umj/oai |
| collection | OJS |
| datestamp_date | 2020-03-18T19:49:15Z |
| description | We show that the conjugacy of elements of finite order in the group of finite-state automorphisms of a rooted tree is equivalent to their conjugacy in the group of all automorphisms of the rooted tree. We establish a criterion for conjugacy between a finite-state automorphism and the adding machine in the group of finite-state automorphisms of a rooted tree of valency 2. |
| first_indexed | 2026-03-24T02:38:59Z |
| format | Article |
| fulltext |
УДК 512.54
А. В. Руссєв (Київ. нац. ун-т iм. Т. Шевченка)
ПРО СПРЯЖЕНIСТЬ У ГРУПАХ СКIНЧЕННОСТАНОВИХ
АВТОМОРФIЗМIВ КОРЕНЕВИХ ДЕРЕВ
We show that conjugacy of elements of finite order in the group of finite-state automorphisms
of a rooted tree is equivalent to their conjugacy in the automorphism group of the rooted tree.
We find a criterion for the conjugacy of a finite-state automorphism to the adding machine in
the group of finite-state automorphisms of the 2-valent rooted tree.
Установлено, что сопряженность элементов конечного порядка в группе автоморфизмов
корневого дерева с конечным числом состояний равносильна их сопряженности в группе
всех автоморфизмов корневого дерева. Найден критерий сопряженности автоморфизма
с конечным числом состояний со счетной машиной в группе автоморфизмов корневого
дерева валентности 2 с конечным числом состояний.
1. Вступ. При дослiдженнi будови тих чи iнших груп одним iз ключових є питання
про структуру їх класiв спряженостi. Дану роботу присвячено дослiдженню спря-
женостi у пiдгрупi скiнченностанових автоморфiзмiв групи AutTn автоморфiзмiв
однорiдного кореневого дерева Tn валентностi n. Опис класiв спряженостi в групi
AutTn у термiнах дiй елементiв цiєї групи на деревi Tn наведено в роботi [1].
Властивостi пiдгруп групи AutTn, що пов’язанi зi спряженiстю, вивчались також
в [2] (роздiл 3.11) i [3]. В групi AutTn природним чином видiляється пiдгрупа
скiнченностанових автоморфiзмiв FAutTn. Класи спряженостi групи FAutTn не
можна одержати як перетини класiв спряженостi групи AutTn з пiдгрупою FAutTn.
Вiдповiдний приклад двох автоморфiзмiв, спряжених в AutTn i не спряжених в
FAutTn, наведено в [4]. Тому природною є задача опису класiв спряженостi в
групi FAutTn.
В данiй роботi встановлено, що елементи групи FAutTn, якi мають скiнченний
порядок, є спряженими в групах AutTn i FAutTn одночасно. Для елементiв не-
скiнченного порядку аналогiчне твердження, як показує згаданий вище приклад, не
iснує. В цьому випадку вдалося знайти зв’язок мiж спряженiстю елементiв та спря-
женiстю станiв їх перших рiвнiв i степенiв самих елементiв. У випадку бiнарного
дерева знайдено критерiй спряженостi з додавальною машиною в групi FAutT2.
2. Визначення i позначення. Нехай Sn — симетрична група степеня n,
N — множина натуральних чисел, N0 — множина невiд’ємних цiлих чисел, X =
= {1, 2, . . . , n} — алфавiт. Розглянемо множину всiх слiв над алфавiтом X:
X∗ =
⋃
n≥0
Xn, X0 = {Λ},
де Λ — порожнє слово. Для слiв iз цiєї множини визначено операцiю приписування,
яка перетворює X∗ у моноїд.
Означення 1. Кореневим деревом валентностi n називається граф Tn =
= (X∗, E,Λ), деX∗ — множина вершин, E ⊂ X∗×X∗ — множина ребер, Λ ∈ X∗ —
корiнь дерева, причому (u, v) ∈ E тодi i лише тодi, коли iснує x ∈ X таке, що
u = vx або v = ux.
c© А. В. РУССЄВ, 2008
ISSN 1027-3190. Укр. мат. журн., 2008, т. 60, № 10 1357
1358 А. В. РУССЄВ
Означення 2. Вiдображення ϕ : Tn → Tn називається автоморфiзмом коре-
невого дерева, якщо ϕ : X∗ → X∗ — бiєкцiя, ϕ(e) = (ϕ(u), ϕ(v)) ∈ E ⇔ e =
= (u, v) ∈ E, ϕ(Λ) = Λ.
Всi автоморфiзми кореневого дерева Tn утворюють групу вiдносно композицiї,
яку позначимо AutTn. Символом id будемо позначати одиничний елемент цiєї
групи.
Означення 3. Станом автоморфiзму ϕ ∈ AutTn у вершинi w ∈ X∗ назива-
ється такий автоморфiзм ϕw ∈ AutTn, що для довiльного u ∈ X∗ виконується
рiвнiсть ϕ(wu) = ϕ(w)ϕw(u).
Таке означення є коректним [4].
Означення 4. Автоморфiзм називається скiнченностановим, якщо множина
всiх його станiв є скiнченною.
Множина всiх скiнченностанових автоморфiзмiв утворює пiдгрупу FAutTn в
групi AutTn [4].
Визначимо вiдображення π : AutTn → Sn за правилом (π(ϕ))(x) = ϕ(x),
x ∈ X, ϕ ∈ AutTn.
Автоморфiзм ϕ ∈ AutTn також будемо записувати у формi ϕ = (ϕ1, ϕ2, . . . ,
. . . , ϕn)π(ϕ), де ϕ1, ϕ2, . . . , ϕn — стани автоморфiзму ϕ у вершинах 1, 2, . . . , n
вiдповiдно. Нехай ϕ = (ϕ1, ϕ2, . . . , ϕn)πϕ i ψ = (ψ1, ψ2, . . . , ψn)πψ — два автомор-
фiзми з AutTn. Тодi для довiльних x ∈ X i u ∈ X∗ маємо
(ϕψ)(xu) = ψ(ϕ(xu)) = ψ(πϕ(x)ϕx(u)) =
= πψ(πϕ(x))ψπϕ(x)(ϕx(u)) = (πϕπψ)(x)(ϕxψπϕ(x))(u).
Вважаємо, що перший множник у добутку автоморфiзмiв або пiдстановок дiє пер-
шим. Отже, для добутку ϕψ маємо ϕψ = (ϕ1ψπϕ(1), ϕ2ψπϕ(2), . . . , ϕnψπϕ(n))πϕπψ.
Нехай f : X → X — частково визначене вiдображення. Символом dom f бу-
демо позначати пiдмножину X, на якiй визначено f, а символом im f — множину
значень f.
3. Спряженiсть елементiв скiнченного порядку в FAut Tn. Визначимо
функцiї l : Sn × X → N, s : Sn × X → X та d : Sn × X → N0. Для пiдстановки
π ∈ Sn i лiтери i ∈ X покладемо: l(π, i) — довжина циклу в циклiчному розкладi
π, що мiстить i; s(π, i) — мiнiмальний елемент цього циклу; d(π, i) — мiнiмальне
невiд’ємне число таке, що s(π, i) = πd(π,i)(i).
Лема 1. Нехай πu, πv та πh — пiдстановки з Sn такi, що πu = π−1
h πvπh.
Тодi має мiсце рiвнiсть l(πv, i) = l(πu, πh(i)).
Доведення. З означення маємо рiвнiсть πl(πv,i)
v (i) = i. Тому
πl(πv,i)
u (πh(i)) = (π−1
h πvπh)l(πv,i)(πh(i)) =
= (π−1
h πl(πv,i)
v πh)(πh(i)) = πh(πl(πv,i)
v (i)) = πh(i).
Звiдcи l(πu, πh(i)) ≤ l(πv, i). Аналогiчно доводиться нерiвнiсть в iнший бiк.
Лему доведено.
Визначимо вiдображення r : AutTn ×X × N0 → AutTn та r̂ : AutTn ×X →
→ AutTn. Для автоморфiзму u = (u1, u2, . . . , un)πu з AutTn i лiтери i ∈ X
покладемо
ISSN 1027-3190. Укр. мат. журн., 2008, т. 60, № 10
ПРО СПРЯЖЕНIСТЬ У ГРУПАХ СКIНЧЕННОСТАНОВИХ АВТОМОРФIЗМIВ ... 1359
r(u, i,m) =
m−1∏
j=0
uπj
u(i), m ∈ N, r(u, i, 0) = id,
r̂(u, i) = r(u, i, l(πu, i)) =
l(πu,i)−1∏
j=0
uπj
u(i).
Легко перевiрити, що r(u, i,m) = (um)i i r̂(u, i) = (ul(πu,i))i.
Лема 2. Вiдображення r задовольняє рiвностi
r(u, i,m) = uir(u, πu(i),m− 1),
де u = (u1, u2, . . . , un)πu — автоморфiзм з AutTn, i ∈ X, m ∈ N.
Доведення. Випадок m = 1 є наслiдком рiвностей r(u, i, 1) = ui та r(u, πu(i),
0) = id, якi випливають з означення. У випадку m > 1 за означенням маємо
r(u, i,m) =
m−1∏
j=0
uπj
u(i) = ui
m−1∏
j=1
uπj
u(i) = ui
m−2∏
j=0
uπj
u(πu(i)) = uir(u, πu(i),m− 1).
Лему доведено.
Лема 3. Нехай u = (u1, u2, . . . , un)πu, v = (v1, v2, . . . , vn)πv та h = (h1,
h2, . . . , hn)πh — такi автоморфiзми з AutTn, що u = h−1vh. Тодi для довiльного
i ∈ X має мiсце рiвнiсть
h−1
i r̂(v, i)hi = r̂(u, πh(i)).
Доведення. Зафiксуємо i ∈ X. З умови маємо рiвнiсть ul(πv,i) = h−1vl(πv,i)h
або
ul(πv,i) = π−1
h (h−1
1 , h−1
2 , . . . , h−1
n )vl(πv,i)(h1, h2, . . . , hn)πh.
Звiдси
πhu
l(πv,i) = (h−1
1 , h−1
2 , . . . , h−1
n )vl(πv,i)(h1, h2, . . . , hn)πh. (1)
Стан, що вiдповiдає лiтерi i, для автоморфiзму в лiвiй частинi рiвностi (1) має
вигляд
uπh(i)uπu(πh(i))uπ2
u(πh(i)) . . . uπl(πv,i)−1
u (πh(i))
= r̂(u, πh(i)),
оскiльки l(πv, i) = l(πu, πh(i)) за лемою 1. Стан, що вiдповiдає лiтерi i, для
автоморфiзму в правiй частинi рiвностi (1) має вигляд
h−1
i vivπv(i)vπ2
v(i) . . . vπl(πv,i)−1
v (i)
hi = h−1
i r̂(v, i)hi.
Отже, h−1
i r̂(v, i)hi = r̂(u, πh(i)).
Лему доведено.
Далi в даному пунктi доводиться, що скiнченностановi автоморфiзми з FAutTn,
якi мають скiнченний порядок i спряженi в групi AutTn, також будуть спряженими
в групi FAutTn.
ISSN 1027-3190. Укр. мат. журн., 2008, т. 60, № 10
1360 А. В. РУССЄВ
Розглянемо множину
M =
{
(u, v) ∈ FAutTn × FAutTn :
u, v мають скiнченний порядок i є спряженими в групi AutTn
}
.
Для кожної пари θ = (u, v) ∈M зафiксуємо елемент Ψ(θ) ∈ AutTn такий, що(
Ψ(θ)
)−1
vΨ(θ) = u.
Таким чином, визначено вiдображення Ψ: M → AutTn.
Схема подальшого доведення є такою: за вiдображенням Ψ будуємо нове вi-
дображення Ψ∗ : M → AutTn таким чином. Спочатку визначимо дiю всiєї сiм’ї
автоморфiзмiв {Ψ∗(θ) : θ ∈M} на словах довжини 1, потiм на словах довжини 2 i
т. д. Пiсля цього покажемо, що Ψ∗ має ту ж властивiсть, що й Ψ, тобто для будь-
якого θ = (u, v) ∈ M (Ψ∗(θ))−1vΨ∗(θ) = u. Залишиться довести, що Ψ∗(M) ⊂
⊂ FAutTn, тобто для кожної пари θ ∈M автоморфiзм Ψ∗(θ) є скiнченностановим
спрягаючим елементом.
Визначимо вiдображення Φ: M × X → AutTn та Ψ∗ : M → AutTn. Нехай
θ = (u, v) ∈M. Позначимо h = Ψ(θ), πu = π(u), πv = π(v), πh = π(h). Покладемо
Φ(θ, i) = Ψ∗(r̂(u, πh(s(πv, i))), r̂(v, s(πv, i))), i ∈ X, (2)
Ψ∗(θ) = (r(v, i, d(πv, i))Φ(θ, i)(r(u, πh(i), d(πv, i)))−1, 1 ≤ i ≤ n)πh. (3)
Рiвнiсть (3) визначає дiю сiм’ї {Ψ∗(θ) : θ ∈ M} на словах довжини 1. Нехай дiю
сiм’ї {Ψ∗(θ) : θ ∈ M} визначено на словах довжини k. Якщо θ = (u, v) ∈ M, то
за лемою 3
(
r̂(u, πh(s(πv, i))), r̂(v, s(πv, i))
)
∈ M, а тому за рiвнiстю (2) дiю сiм’ї
{Φ(θ, i) : θ ∈M, i ∈ X} визначено на словах довжини k. Тодi рiвнiсть (3) визначає
дiю сiм’ї {Ψ∗(θ) : θ ∈ M} на словах довжини k + 1. З принципу математичної
iндукцiї випливає, що дiю сiм’ї {Ψ∗(θ) : θ ∈ M} визначено на словах довiльної
довжини.
Лема 4. Для довiльної пари θ = (u, v) ∈M має мiсце рiвнiсть
u =
(
Ψ∗(θ)
)−1
vΨ∗(θ).
Доведення проведемо iндукцiєю за рiвнем m кореневого дерева. База iндукцiї
m = 1 випливає з рiвностi пiдстановок, що вiдповiдають автоморфiзмам в обох
частинах, оскiльки π(Ψ∗(θ)) = π(Ψ(θ)). Припустимо, що твердження має мiсце
для рiвня m = k. Покажемо, що воно має мiсце i для рiвня m = k + 1. Обчислимо
стан g правої частини для лiтери πh(i):
g =
(
r
(
v, i, d(πv, i)
)
Φ(θ, i)
(
r(u, πh(i), d(πv, i))
)−1
)−1
vi×
× r
(
v, πv(i), d(πv, πv(i))
)
Φ(θ, πv(i))
(
r
(
u, πh(πv(i)), d(πv, πv(i))
))−1
.
Розглянемо два випадки:
1) i = s(πv, i). Тодi d(πv, i) = 0 та d(πv, πv(i)) = l(πv, i) − 1. Для автомор-
фiзму g маємо (знак рiвностi показує, що автоморфiзми однаково дiють на слова
довжини k)
ISSN 1027-3190. Укр. мат. журн., 2008, т. 60, № 10
ПРО СПРЯЖЕНIСТЬ У ГРУПАХ СКIНЧЕННОСТАНОВИХ АВТОМОРФIЗМIВ ... 1361
g = (r(v, i, 0)Φ(θ, i)(r(u, πh(i), 0))−1)−1vi×
×r(v, πv(i), l(πv, i)− 1)Φ(θ, πv(i))(r(u, πh(πv(i)), l(πv, i)− 1))−1 =
= (Φ(θ, i))−1vir(v, πv(i), l(πv, i)− 1)Φ(θ, πv(i))(r(u, πh(πv(i)), l(πv, i)− 1))−1 =
= (Φ(θ, i))−1r(v, i, l(πv, i))Φ(θ, πv(i))(r(u, πu(πh(i)), l(πv, i)− 1))−1 =
= (Φ(θ, i))−1r̂(v, i)Φ(θ, i)(r(u, πu(πh(i)), l(πv, i)− 1))−1 =
(рiвнiсть (2) в цьому випадку набирає вигляду Φ(θ, i) = Ψ∗(r̂(u, πh(i)), r̂(v, i)),
тому за припущенням iндукцiї)
= r̂(u, πh(i))(r(u, πu(πh(i)), l(πv, i)− 1))−1 =
= uπh(i)r(u, πu(πh(i)), l(πu, πh(i))− 1)(r(u, πu(πh(i)), l(πv, i)− 1))−1 = uπh(i).
2) i 6= s(πv, i). Тодi d(πv, πv(i)) = d(πv, i) − 1. Шуканий автоморфiзм g має
вигляд
g = (r(v, i, d(πv, i))Φ(θ, i)(r(u, πh(i), d(πv, i)))−1)−1vi×
×r(v, πv(i), d(πv, i)− 1)Φ(θ, πv(i))(r(u, πh(πv(i)), d(πv, i)− 1))−1 =
= r(u, πh(i), d(πv, i))(Φ(θ, i))−1r(v, i, d(πv, i))−1×
×vir(v, πv(i), d(πv, i)− 1)Φ(θ, πv(i))(r(u, πh(πv(i)), d(πv, i)− 1))−1 =
= r(u, πh(i), d(πv, i))(Φ(θ, i))−1r(v, i, d(πv, i))−1×
×r(v, i, d(πv, i))Φ(θ, i)(r(u, πu(πh(i)), d(πv, i)− 1))−1 =
= r(u, πh(i), d(πv, i))(r(u, πu(πh(i)), d(πv, i)− 1))−1 =
= uπh(i)r(u, πu(πh(i)), d(πv, i)− 1)(r(u, πu(πh(i)), d(πv, i)− 1))−1 = uπh(i).
З принципу математичної iндукцiї випливає, що твердження має мiсце для всiх
рiвнiв кореневого дерева.
Лему доведено.
Лема 5. Має мiсце включення
Ψ∗(M) ⊂ FAutTn.
Доведення. Нехай Mk = {θ ∈ M | порядок елементiв з пари θ дорiвнює
k}. Доведемо iндукцiєю по k, що Ψ∗(Mk) ⊂ FAutTn. База iндукцiї k = 1,
M1 =
{
(id, id)
}
. Для a = Ψ∗
(
(id, id)
)
з рiвностей (2) та (3) одержуємо a =
= (a, a, . . . , a)π(Ψ(id, id)). Тому a є скiнченностановим.
ISSN 1027-3190. Укр. мат. журн., 2008, т. 60, № 10
1362 А. В. РУССЄВ
Нехай Ψ∗(Mk) ⊂ FAutTn для всiх k < m. Покажемо, що Ψ∗(Mm) ⊂ FAutTn.
Якщо Mm є порожньою, то вкладення має мiсце. Нехай θ = (u, v) ∈ Mm. Пот-
рiбно показати, що множина всiх станiв Ψ∗(θ) є скiнченною. Позначимо множину
всiх станiв uw автоморфiзму u таких, що u(w) = w, через Qu. Аналогiчно визна-
чаємо для автоморфiзму v множину Qv . Цi множини є скiнченними. Розглянемо
множину Q1 = Ψ∗((Qu ×Qv) ∩M) ⊂ AutTn, всi елементи якої будемо називати
автоморфiзмами першого типу. Вона також є скiнченною.
Нехай Ψ∗((ũ, ṽ)) ∈ Q1 — довiльний автоморфiзм першого типу, де ũ = (ũ1,
ũ2, . . . , ũn)π(ũ) та ṽ = (ṽ1, ṽ2, . . . , ṽn)π(ṽ) — стани автоморфiзмiв u та v вiдпо-
вiдно. Якщо l(π(ṽ), i) = 1, то стан Ψ∗((ũ, ṽ)), що вiдповiдає лiтерi i, дорiвнює
Φ((ũ, ṽ), i) = Ψ∗((ũπh(i), ṽi)) ∈ Q1, оскiльки d(π(ṽ), i) = 0, тобто є автоморфiзмом
першого типу. Якщо l(π(ṽ), i) 6= 1, то порядок елементiв, до яких застосовується
Ψ∗ у рiвностi (2), менше m принаймнi в l(π(ṽ), i) разiв. Дiйсно, вони є стана-
ми l(π(ṽ), i)-го степеня автоморфiзмiв ũ та ṽ вiдповiдно та l(π(ṽ), i) є дiльником
порядкiв ũ та ṽ, оскiльки π(ũ) та π(ṽ) мiстять цикл довжини l(π(ṽ), i). За припу-
щенням iндукцiї Φ((ũ, ṽ), i) ∈ FAutTn. Тому стан Ψ∗((ũ, ṽ)), що вiдповiдає лiтерi
i, також є скiнченностановим, бо є добутком Φ((ũ, ṽ), i) та станiв або обернених до
станiв деяких степенiв ũ та ṽ. Такi стани будемо називати автоморфiзмами другого
типу.
Всi автоморфiзми другого типу можна проiндексувати пiдмножиною множини
Qu×Qv ×X, де елемент Qu×Qv визначає пару (ũ, ṽ), а елемент X — лiтеру, якiй
вiдповiдає стан. Отже, їх скiнченна кiлькiсть. Позначимо множину автоморфiзмiв
другого типу через Q2.
Розглянемо множину Q3, що складається зi всiх станiв усiх автоморфiзмiв з Q2.
Вона є скiнченною, бо Q2 складається зi скiнченної кiлькостi скiнченностанових
автоморфiзмiв. Таким чином, приходимо до висновку, що всi стани Ψ∗(θ) належать
скiнченнiй множинi Q1 ∪Q3, тобто Ψ∗(θ) є скiнченностановим.
З принципу математичної iндукцiї випливає, що Ψ∗(Mk) ⊂ FAutTn для до-
вiльного k, тобто Ψ∗(M) ⊂ FAutTn.
Лему доведено.
Теорема 1. Нехай g1 i g2 — два скiнченностановi автоморфiзми скiнченного
порядку, що спряженi в групi AutTn. Тодi g1 i g2 спряженi в групi FAutTn.
Доведення. Розглянемо пару θ = (g1, g2). За умовою θ ∈ M. Тому визначений
автоморфiзм ψ = Ψ∗(θ). За лемою 5 вiн є скiнченностановим, а за лемою 4 має
мiсце рiвнiсть g1 = ψ−1g2ψ. Отже, g1 i g2 є спряженими в FAutTn.
4. Спряженiсть елементiв FAut Tn у загальному випадку. Нехай u i v —
деякi автоморфiзми з FAutTn, πu = π(u), πv = π(v). Будемо говорити, що для
автоморфiзмiв u i v iснує частковий генератор спряження ζ, якщо iснує таке
частково визначене iн’єктивне вiдображення ζ : X → X, що на im ζ виконується
рiвнiсть πu = ζ−1πvζ, dom ζ iнварiантна при дiї πv та для кожної лiтери i ∈ dom ζ
автоморфiзми r̂(v, s(πv, i)) i r̂(u, ζ(s(πv, i))) є спряженими в FAutTn.
Лема 6. Нехай для u i v iснує частковий генератор спряження πh та
domπh = X. Тодi u i v є спряженими в FAutTn.
Доведення. За умовою iснують такi автоморфiзми hi ∈ FAutTn, i ∈ X, що
для кожної лiтери i ∈ X виконується рiвнiсть
r̂
(
u, πh(s(πv, i))
)
= h−1
i r̂(v, s(πv, i))hi. (4)
ISSN 1027-3190. Укр. мат. журн., 2008, т. 60, № 10
ПРО СПРЯЖЕНIСТЬ У ГРУПАХ СКIНЧЕННОСТАНОВИХ АВТОМОРФIЗМIВ ... 1363
Для пари θ = (u, v) автоморфiзм Ψ∗(θ) визначаємо за рiвнiстю (3), але покладаємо
Φ(θ, i) = hi. Подальше доведення повторює доведення кроку iндукцiї в лемi 4, але
замiсть припущення iндукцiї використовуємо рiвнiсть (4).
Теорема 2. Нехай пiдстановки πu i πv з Sn є спряженими в Sn, для u i v iснує
частковий генератор спряження ζ та для кожного k ∈ Lζ = {l(πv, i) : i /∈ dom ζ}
автоморфiзми uk i vk спряженi в FAutTn. Тодi u i v є спряженими в FAutTn.
Доведення. Нехай k — найменший елемент Lζ . За умовою iснує автомор-
фiзм ϕk ∈ FAutTn такий, що uk = ϕ−1
k vkϕk. Позначимо πk = π(ϕk). Нехай
Yv =
{
i : k дiлиться на l(πv, i)
}
, Yu =
{
i : k дiлиться на l(πu, i)
}
. Очевидно, що
πk(Yv) ⊂ Yu i для кожної лiтери i ∈ Yv автоморфiзми r(v, i, k) i r(u, πk(i), k) є
спряженими в FAutTn. Розглянемо вiдображення ζ−1πk : ζ(Yv) → Yu∩πk(dom ζ).
Воно є бiєктивним i його iнварiантна множина є пiдмножиною Yu ∩ πk(dom ζ).
Побудуємо вiдображення π̂ : dom ζ ∪ Yv → im ζ ∪ Yu. Покладемо π̂|dom ζ = ζ.
Для лiтери з множини Yv \ dom ζ застосуємо πk; далi, поки одержаний на попе-
редньому кроцi образ належить в ζ(Yv), застосовуємо ζ−1πk; результат i буде обра-
зом при дiї π̂. Кiлькiсть крокiв буде скiнченною, оскiльки ми починаємо застосову-
вати бiєктивне вiдображення ζ−1πk з лiтери, що належить множинi Yu \πk(dom ζ),
тобто не належить iнварiантнiй множинi вiдображення. Остання лiтера належить
множинi Yu \ ζ(Yv) = Yu \ im ζ. Вiдображення π̂ є бiєкцiєю та зберiгає довжини
циклiв.
Довизначимо ζ на елементах Yv \ dom ζ. Для лiтери i ∈ Yv \ dom ζ покладемо
ζ(s(πv, i)) = π̂(s(πv, i)). На рештi елементiв визначимо ζ так, щоб виконувалась
умова πu = ζ−1πvζ на im ζ ∪ Yu. Це можна зробити, оскiльки ми довизначили
ζ на кожному циклi довжини k рiвно в однiй точцi. Вiдображення πk зберiгає
спряженiсть добуткiв довжини k. Таку ж властивiсть має ζ−1πk. Отже, для кожної
лiтери i ∈ dom ζ ∪ Yv автоморфiзми r̂(v, s(πv, i)) i r̂(u, ζ(s(πv, i))) є спряженими в
FAutTn. Довизначене вiдображення ζ знову є частковим генератором спряження.
Мiркуючи аналогiчно, можна продовжити початкове вiдображення на всю мно-
жину X. Тодi за лемою 6 матиме мiсце твердження теореми.
Нехай для u i v iснує частковий генератор спряження ζ. Розглянемо множину
Xv,1 =
{
i : l(πv, i) = 1
}
. Якщо dom ζ 6⊃ Xv,1, то Lζ 3 1, тобто умова теореми
мiстить припущення, що u i v є спряженими в FAutTn. Отже, для одержання
нової iнформацiї має виконуватись включення dom ζ ⊃ Xv,1. Умови iснування
часткового генератора спряження ζ з dom ζ = Xv,1 дає наступна лема.
Лема 7. Нехай u = (u1, u2, . . . , un)πu i v = (v1, v2, . . . , vn)πv, ζ : Xv,1 →
→ Xu,1
(
Xu,1 =
{
i : l(πu, i) = 1
})
— бiєктивне вiдображення та vi i uζ(i) є
спряженими для i ∈ Xv,1, Тодi ζ є частковим генератором спряження.
Доведення. Вiдображення πu i πv є тотожними на множинах Xu,1 i Xv,1 вiдпо-
вiдно. Тому при дiї πv множина dom ζ = Xv,1 є iнварiантною та πu = ζ−1πvζ
на im ζ. Для довiльної лiтери i ∈ dom ζ маємо s(πv, i) = i, l(πv, i) = 1 та
l(πu, ζ(i)) = 1, тому r̂(v, s(πv, i)) = vi i r̂(u, ζ(s(πv, i))) = uζ(i). Оскiльки vi i
uζ(i) є спряженими за умовою для всiх i ∈ dom ζ, вiдображення ζ є частковим
генератором спряження.
Лему доведено.
Теорема 3. Нехай пiдстановки πu i πv з Sn — цикли довжини n та un i vn є
спряженими в FAutTn. Тодi u i v спряженi в FAutTn.
ISSN 1027-3190. Укр. мат. журн., 2008, т. 60, № 10
1364 А. В. РУССЄВ
Доведення. Пiдстановки πu i πv є спряженими в Sn. Розглянемо частковий
генератор спряження ζ з dom ζ = ∅. Для нього Lζ = {n}. За умовою теореми 2
автоморфiзми u i v є спряженими в FAutTn.
5. Спряженiсть з додавальною машиною в FAut T2. В цьому пунктi вважа-
ємо, що X = {1, 2}. Нехай u ∈ FAutT2 — автоморфiзм, спряжений з додавальною
машиною, тобто з f = (1, f)σ в AutT2. Як показано в [4], це буде тодi й тiльки то-
дi, коли u — шарово транзитивний автоморфiзм, тобто транзитивно дiє на кожнiй iз
множин Xn, n ∈ N. Для спрощення запису введемо позначення Υ(u) = Ψ∗(u, f),
тобто Υ є вiдображенням iз множини автоморфiзмiв FAutT2, спряжених з f в
AutT2, в множину AutT2. Також вважаємо, що для кожної пари θ = (ϕ, f) пiд-
становка π(Ψ(θ)) = e (це можна зробити замiною Ψ(θ) на fΨ(θ)). Тодi для Υ
одержуємо
Υ(u) = (Υ(u1u2), fΥ(u1u2)u−1
2 ) = (Υ(u1u2),Υ(u1u2)u1), (5)
оскiльки fΥ(u1u2) = Υ(u1u2)u1u2 за лемою 4.
Розглянемо вiдображення p : X∗ → X∗ та m : X∗ → N0. Для слова w ∈
∈ X∗ слово p(w) складається лише з одиниць i має ту саму довжину, а m(w) =
=
∑|w|
i=1
2i−1(wi − 1), де wi — i-та лiтера w.
Лема 8. Для довiльного слова w ∈ X∗ має мiсце рiвнiсть
Υ(u)|w = Υ
(
2|w|−1∏
k=0
u|uk(p(w))
)
m(w)−1∏
k=0
u|uk(p(w)). (6)
Доведення проведемо iндукцiєю за довжиною слова w. База iндукцiї |w| = 0.
Тодi w = Λ, p(w) = Λ та m(w) = 0. Рiвнiсть (6) набирає вигляду Υ(u)|Λ = Υ(u|Λ),
яка, очевидно, виконується.
Нехай рiвнiсть (6) виконується для слова w. Обчислимо
Υ(u)|wx =
(за припущенням iндукцiї)
=
(
Υ
(
2|w|−1∏
k=0
u|uk(p(w))
)
m(w)−1∏
k=0
u|uk(p(w))
)∣∣∣∣∣
x
=
(
оскiльки Υ
(∏2|w|−1
k=0 u|uk(p(w))
)
не змiнює першу лiтеру
)
= Υ
(
2|w|−1∏
k=0
u|uk(p(w))
)∣∣∣∣∣
x
(
m(w)−1∏
k=0
u|uk(p(w))
)∣∣∣∣∣
x
=
(за рiвнiстю (5))
ISSN 1027-3190. Укр. мат. журн., 2008, т. 60, № 10
ПРО СПРЯЖЕНIСТЬ У ГРУПАХ СКIНЧЕННОСТАНОВИХ АВТОМОРФIЗМIВ ... 1365
= Υ
((
2|w|−1∏
k=0
u|uk(p(w))
)∣∣∣∣∣
1
(
2|w|−1∏
k=0
u|uk(p(w))
)∣∣∣∣∣
2
)
×
×
(
2|w|(x−1)−1∏
k=0
u|uk(p(w))
)∣∣∣∣∣
1
(
m(w)−1∏
k=0
u|uk(p(w))
)∣∣∣∣∣
x
=
= Υ
(
2|w|−1∏
k=0
u|uk(p(w)1) ·
2|w|−1∏
k=0
u|uk(p(w)2)
)
×
×
2|w|(x−1)−1∏
k=0
u|uk(p(w)1) ·
m(w)−1∏
k=0
u|uk(p(w)x) =
(оскiльки автоморфiзм u2|w| не змiнює першi |w| лiтер i u2|w| |p(w) спряжений до f,
то має мiсце рiвнiсть u2|w|(p(w)1) = p(w)2)
= Υ
(
2·2|w|−1∏
k=0
u|uk(p(w)1)
)
m(wx)−1∏
k=0
u|uk(p(w)1) =
= Υ
(
2|wx|−1∏
k=0
u|uk(p(wx))
)
m(wx)−1∏
k=0
u|uk(p(wx)).
Отже, рiвнiсть (6) має мiсце для слова wx. А тому i для довiльного слова w ∈ X∗.
Лему доведено.
Розглянемо множину
S(u) =
{
m(w)−1∏
k=0
u|uk(p(w)) : w ∈ X∗
}⋃{2n−1∏
k=0
u|uk(p(w)) : w ∈ X∗
}
.
Елементами цiєї множини є добутки станiв автоморфiзму u. Але такий добуток
є насправдi станом вiдповiдного степеня u, оскiльки кожний наступний множник
є станом u у вершинi, яка є образом слова p(w) пiд дiєю попереднiх множникiв.
Тому
S(u) =
{
uk|vn : n ≥ 0, 0 ≤ k ≤ 2n
}
,
де слово vn довжини n складене лише з одиниць.
Теорема 4. Нехай u та f є спряженими в AutT2. Автоморфiзми u та f
спряженi в FAutT2 тодi i лише тодi, коли множина S(u) є скiнченною.
Доведення. Якщо множина S(u) є скiнченною i
∣∣S(u)
∣∣ = N, то за формулою (6)∣∣{Υ(u)|w : w ∈ X∗}∣∣ ≤ NN.
Отже, u та f є спряженими в FAutT2.
ISSN 1027-3190. Укр. мат. журн., 2008, т. 60, № 10
1366 А. В. РУССЄВ
Нехай u = h−1fh, де h ∈ FAutT2. Тодi uk = h−1fkh та
S(u) =
{
(h−1fkh)|vn : n ≥ 0, 0 ≤ k ≤ 2n
}
=
=
{
h−1|vnf
k|h−1(vn)h|fk(h−1(vn)) : n ≥ 0, 0 ≤ k ≤ 2n
}
=
(оскiльки f дiє транзитивно на словах фiксованої довжини n i 0 ≤ k ≤ 2n, стан
не бiльш нiж одного множника fk дорiвнює f, а решта дорiвнюють тотожному
автоморфiзму)
=
{
h−1|vnf
lh|fk(h−1(vn)) : n ≥ 0, 0 ≤ k ≤ 2n, l ∈ {0, 1}
}
.
Якщо кiлькiсть станiв h дорiвнює N, то |S(u)| ≤ 2N2.
1. Gawron P. W., Nekrashevych V. V., Sushchansky V. I. Conjugation in tree automorphism groups //
Int. J. Algebra Comput. – 2001. – 11, № 5. – P. 529 – 547.
2. Nekrashevych V. V. Self-similar groups // Math. Surv. and Monogr. – 2005. – 117. – 231 p.
3. Brunner A. M., Sidki S. On the automorphism group of the one-rooted binary tree // J. Algebra. –
1997. – 195. – P. 465 – 486.
4. Григорчук Р. И., Некрашевич В. В., Сущанский В. И. Автоматы, динамические системы и
группы // Тр. Мат. ин-та РАН. – 2000. – 231. – С. 134 – 214.
Одержано 10.01.07,
пiсля доопрацювання — 13.09.07
ISSN 1027-3190. Укр. мат. журн., 2008, т. 60, № 10
|
| id | umjimathkievua-article-3250 |
| institution | Ukrains’kyi Matematychnyi Zhurnal |
| keywords_txt_mv | keywords |
| language | Ukrainian English |
| last_indexed | 2026-03-24T02:38:59Z |
| publishDate | 2008 |
| publisher | Institute of Mathematics, NAS of Ukraine |
| record_format | ojs |
| resource_txt_mv | umjimathkievua/1b/c5091f9b2608d38d9b23de5bf732ea1b.pdf |
| spelling | umjimathkievua-article-32502020-03-18T19:49:15Z On conjugacy in groups of finite-state automorphisms of rooted trees Про спряженість у групах скінченностанових автоморфізмів кореневих дерев Russev, A. V. Руссєв, А. В. We show that the conjugacy of elements of finite order in the group of finite-state automorphisms of a rooted tree is equivalent to their conjugacy in the group of all automorphisms of the rooted tree. We establish a criterion for conjugacy between a finite-state automorphism and the adding machine in the group of finite-state automorphisms of a rooted tree of valency 2. Установлено, что сопряженность элементов конечного порядка в группе автоморфизмов корневого дерева с конечным числом состояний равносильна их сопряженности в группе всех автоморфизмов корневого дерева. Найден критерий сопряженности автоморфизма с конечным числом состояний со счетной машиной в группе автоморфизмов корневого дерева валентности 2 с конечным числом состояний. Institute of Mathematics, NAS of Ukraine 2008-10-25 Article Article application/pdf https://umj.imath.kiev.ua/index.php/umj/article/view/3250 Ukrains’kyi Matematychnyi Zhurnal; Vol. 60 No. 10 (2008); 1357–1366 Український математичний журнал; Том 60 № 10 (2008); 1357–1366 1027-3190 uk en https://umj.imath.kiev.ua/index.php/umj/article/view/3250/3246 https://umj.imath.kiev.ua/index.php/umj/article/view/3250/3247 Copyright (c) 2008 Russev A. V. |
| spellingShingle | Russev, A. V. Руссєв, А. В. On conjugacy in groups of finite-state automorphisms of rooted trees |
| title | On conjugacy in groups of finite-state automorphisms of rooted trees |
| title_alt | Про спряженість у групах скінченностанових автоморфізмів кореневих дерев |
| title_full | On conjugacy in groups of finite-state automorphisms of rooted trees |
| title_fullStr | On conjugacy in groups of finite-state automorphisms of rooted trees |
| title_full_unstemmed | On conjugacy in groups of finite-state automorphisms of rooted trees |
| title_short | On conjugacy in groups of finite-state automorphisms of rooted trees |
| title_sort | on conjugacy in groups of finite-state automorphisms of rooted trees |
| url | https://umj.imath.kiev.ua/index.php/umj/article/view/3250 |
| work_keys_str_mv | AT russevav onconjugacyingroupsoffinitestateautomorphismsofrootedtrees AT russêvav onconjugacyingroupsoffinitestateautomorphismsofrootedtrees AT russevav prosprâženístʹugrupahskínčennostanovihavtomorfízmívkorenevihderev AT russêvav prosprâženístʹugrupahskínčennostanovihavtomorfízmívkorenevihderev |