КИЇВСЬКИЙ НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ

ІМЕНІ ТАРАСА ШЕВЧЕНКА

НЕКРАШЕВИЧ Володимир Володимирович

УДК 512.745

САМОПОДІБНІ ГРУПИ АВТОМАТІВ

01.01.06 --- алгебра і теорія чисел

АВТОРЕФЕРАТ

дисертації на здобуття наукового ступеня

доктора фізико-математичних наук

Київ --- 2006

Дисертацією є рукопис.

Робота виконана у Київському національному університеті імені Тараса Шевченка.

Науковий консультант:

СУЩАНСЬКИЙ Віталій Іванович, доктор фізико-математичних наук, професор.

Офіційні опоненти:

НОВІКОВ Борис Володимирович, доктор фіз.-мат. наук, професор, Харківський національний університет ім. В.Н.Каразіна, кафедра теорії функцій та функціонального аналізу;

САМОЙЛЕНКО Юрій Стефанович, доктор фіз.-мат. наук, професор, член-кореспондент НАН України, Інститут математики НАН України, завідувач відділу функціонального аналізу;

УСТИМЕНКО Василь Олександрович, доктор фіз.-мат. наук, професор, Національний університет, "Києво-Могилянська Академія", кафедра математики.

Провідна установа:

Львівський національний університет ім. І.Франка.

Захист відбудеться 14 червня 2006 р. о 14 год. на засіданні спеціалізованої вченої ради Д 26.001.18 Київського університету імені Тараса Шевченка за адресою: Київ , вул. Глушкова 6.

З дисертацією можна ознайомитись у бібліотеці Київського національного університету імені Тараса Шевченка.

Автореферат розісланий "27'' квітня 2006 р.

Вчений секретар

спеціалізованої вченої ради

кандидат фіз.-мат. наук ПЛАХОТНИК В.В.

ЗАГАЛЬНА ХАРАКТЕРИСТИКА РОБОТИ

Актуальність теми. Поняття самоподібності є одним із основних понять у фрактальній геометрії, динамічних системах, мультирезолюційному аналізі та інших галузях математики. Починаючи із 1980 року ідея самоподібності почала також проникати і в теорію груп.

Явище самоподібності є властивістю груп автоморфізмів регулярних кореневих дерев. Кожне регулярне кореневе дерево ізоморфне дереву X* скінченних слів над деяким алфавітом X. У дереві X* два слова з'єднані ребром тоді і лише тоді, коли вони маю вигляд v та vx, де v — слово, а x — буква.

Самоподібні (станово-замкнені) групи з'являються природньо при дослідженні груп автоматних підстановок. Більшість таких груп, які вивчаються в літературі, визначаються саме через їх самоподібну дію, і таке визначення є найприроднішим та найзручнішим. Група, що діє на дереві X* називається самоподібною, якщо дія кожного елемента g групи на довільному піддереві vX* збігається із дією якогось елемента цієї ж групи.

Самоподібність є зручним інструментом для дослідження груп, оскільки перехід до дії на піддереві дозволяє доводити властивості груп за індукцією. Важливу роль при цьому відіграє властивість скорочення довжини елементів групи при переході до обмеження на піддерево. Самоподібні групи із такою властивістю дістали назву стискуючих. Стискуючі групи є найбільш вивченим класом самоподібних груп. Велика частина дисертації присвячена систематичному вивченню стискуючих самоподібних груп.

Одним із перших прикладів самоподібної групи є відома група Григорчука Р. И. Григорчук. К пpоблеме Беpнсайда о пеpиодических гpуппах.// Функциональный анализ и пpиложения. --- 1980. --- 14. --- № 1. --- 53--54., яка початково будувалася як особливо простий приклад періодичної групи. Згодом було помічено, що вона має проміжний ріст Р. И. Григорчук. Степени pоста конечно-поpожденных гpупп и теоpия инваpиантных сpедних. // Изв. АH СССР Сеp. матем. --- 1984. --- 48. --- № 5. --- 939--985., і таким чином дає відповідь на відому проблему Дж.Мілнора про існування таких груп. Група Григорчука була також використана при розв'язанні інших проблем: наприклад, це перший приклад аменабельної групи, що не належить до класу елементарно аменабельних груп Rostislav I. Grigorchuk. An example of a finitely presented amenable group that does not belong to the class EG. // Mat. Sb. --- 1998. --- 189. --- № 1. --- 79--100..

Пізніше почали вивчатися аналоги групи Григорчука та розроблятися техніка для вивчення таких груп. Тут варто згадати групи Гупти-Сідкі Narain D. Gupta and Said N. Sidki. On the Burnside problem for periodic groups. // Math. Z. --- 1983. --- 182. --- 385--388., групу Браннера-Сідкі-Вієйри Andrew M. Brunner, Said N. Sidki, and Ana. C. Vieira. A just-nonsolvable torsion-free group defined on the binary tree. // J. Algebra. --- 1999. --- 211. --- 99--144. та групу описану Р.Григорчуком та А.Жуком у статті Rostislav I. Grigorchuk and Andrzej Zuk. On a torsion-free weakly branch group defined by a three state automaton.// Internat. J. Algebra Comput. --- 2002. --- 12. --- № 1. --- 223--246..

Характерною властивістю автоматних груп є простота їх визначення при складності і незвичності їх теоретико-групових властивостей. При цьому спочатку вони розглядалися в першу чергу як цікаві (контр)приклади. Ця ситуація аналогічна тому, як перші фрактальні множини (множина Кантора, килим Серпінського, та інші) були на час своєї появи цікавими прикладами множин із незвичними топологічними властивостями. Як відомо, пізніше виявилося, що такі фрактальні множини з'являються природньо в багатьох розділах математики та природознавства Benoit B. Mandelbrot. The fractal geometry of nature. Rev. ed. of "Fractals", 1977. / San Francisco: W. H. Freeman and Company. 1982..

Так само згодом стало зрозуміло, що самоподібні групи також є не просто цікавими прикладами груп, але й виникають природнім чином в теорії груп та інших розділах математики.

Так, наприклад Р.Григорчук у 1997 році на конференції з теорії груп у Базі означив клас гіллястих груп (branch groups). Тоді ж було доведено Р. Григорчуком та Д. Вілсоном, що клас екстремальних (just infinite) груп (нескінченних груп, всі власні фактори яких скінченні) розпадається на три класи: майже простих, спадково екстремальних та гіллястих. У класі проскінченних груп лише останні два типи можливі. Р.Григорчуком було також доведено, що довільна скінченно-породжена група має екстремальну фактор-групу. Ці результати показують важливість класу гіллястих груп, першими прикладами яких є група Григорчука та її аналоги. Детальніше про даний напрямок досліджень можна прочитати в Laurent Bartholdi, Rostislav I. Grigorchuk, and Zoran Sunik. Branch groups. / In Handbook of Algebra, Vol. 3. p. 989--1112. North-Holland. Amsterdam. 2003..

Крім важливості самоподібних груп в алгебрі, вони знайшли своє застосування в інших галузях математики: спектральній теорії груп та нескінченних графів, теорії lІ-інваріантів, а також голоморфній та символьній динаміці (див. роботи Laurent Bartholdi and Rostislav I. Grigorchuk. On the spectrum of Hecke type operators related to some fractal groups. // Proceedings of the Steklov Institute of Mathematics. --- 2000. --- 231. --- 5--45.\\ Rostislav I. Grigorchuk and Andrzej Zuk. The lamplighter group as a group generated by a 2-state automaton and its spectrum. // Geom. Dedicata. --- 2001. --- 87. --- № 1--3. --- 209--244. \\ Rostislav I. Grigorchuk, Peter Linnell, Thomas Schick, and Andrzej Zuk. On a question of Atiyah. // C. R. Acad. Sci. Paris Ser. I Math.. --- 2000. --- 331. --- № 9. --- 663--668.).

Після введення автором понять групи ітерованих монодромій та граничного простору з’явився новий місток між теорією самоподібних груп та топологічною і голоморфною динамікою. Екзотичні групи типу групи Григорчука стали тепер не просто (контр)прикладами, а природніми об’єктами пов’язаними, наприклад, із ітераціями раціональних функцій. Стало можливо застосовувати теорію груп породжених автоматами до розв’язання задач голоморфної динаміки. Так, наприклад, автору дисертації разом із Л. Бартолді вдалося розв’язати проблему Д. Хаббарда про композицію многочленів із гомеоморфізмами площини ("twisted rabbit problem"), яку було важко розв’язати іншими методами. Про розв’язок цього питання можна прочитати в монографії Volodymyr Nekrashevych. Self-similar groups./ volume 117 of Mathematical Surveys and Monographs. Amer. Math. Soc., Providence, RI. 2005..

Навіть вивчення самоподібних дій вільних абелевих груп пов'язано із багатьма цікавими поняттями і конструкціями. Кожна така самоподібна дія будується за деякою <<системою числення>> на Zn. Якщо дія є стискуючою, то ця система числення поширюється і на векторний простір Rn. Із системами числення на дійсному векторному просторі пов'язані природньо самоподібні замощення простору так званими цифровими плитками. Такі плитки і відповідні системи числення вивчаються багатьма математиків як з теоретичної так і з прикладної точки зору. Вони знайшли своє застосування у комп'ютерній обробці зображень, теорії сплесків, теорії C*-алгебр, і.т.д. Christoph Bandt. Self-similar sets. V: Integer matrices and fractal tilings of R^n. // Proc. Am. Math. Soc. --- 1991. --- 112. --- № 2. --- 549--562. \\ Andrew Vince. Rep-tiling Euclidean space. // Aequationes Mathematicae. --- 1995. --- 50. --- 191--213. \\ Andrew Vince. Digit tiling of Euclidean space. // In Directions in Mathematical Quasicrystals. pages 329--370. --- Amer. Math. Soc. Providence, RI. --- 2000. \\ Ola Bratteli and Palle E. T. Jorgensen. Iterated function systems and Permutation representations of the Cuntz algebra./ volume 139 of Memoirs of the American Mathematical Society. --- A. M. S., Providence, Rhode Island. --- 1999..

Таким чином, вивчення самоподібних груп відкриває нові перспективи застосувань теорії груп до інших розділів математики, а також збагачує теорію груп новими техніками досліджень.

Зв'язок роботи з науковими програмами, планами, темами. Дослідження проводилися на кафедрі алгебри та математичної логіки Київського Національного Університету імені Тараса Шевченка, що ведуться за темою „Теорія алгебраїчних систем та їх зображень і її застосування” (номер державної реєстрації 0197U003160).

Мета і задачі дослідження. Метою дослідження є побудова загальної теорії самоподібних груп автоматів та їх застосування.

Об’єктом дослідження є (синхронні та асинхронні) автомати, ними породжені групи, самоподібні групи та інверсні напівгрупи, групи ітерованих монодромій, граничні простори стискуючих груп, операторні алгебри асоційовані із самоподібними групами.

Предметом дослідження є алгоритмічні проблеми груп породжених автоматами, властивості таких груп, алгебраїчні аспекти самоподібності, застосування самоподібних груп.

Методи дослідження. У роботі використовуються методи теорії автоматів, вінцевих добутків груп підстановок, геометричної та комбінаторної теорії груп.

Наукова новизна одержаних результатів. Результати роботи є новими і основні з них полягають в наступному.

Групи, породжені автоматами:

Побудовано алгоритми для розв'язання проблеми рівності в групах та напівгрупах (асинхронних) автоматних перетворень. (Підрозділ 2.3) Групи та напівгрупи асинхронних автоматних перетворень було означено в спільній роботі із Р. Григорчуком. Алгоритми було розроблено автором самостійно.

Доведено ізоморфізм груп асинхронно автоматних перетворень над різними алфавітами. Таким чином введено групу раціональних гомеоморфізмів множини Кантора (Теорема 2.33).

Розв'язано проблему Григорчука про класифікацію груп Gw з точністю до ізоморфізму (Теорема 2.65).

Самоподібні інверсні напівгрупи:

Введено поняття самоподібної інверсної напівгрупи, що узагальнює поняття самоподібної групи, та доведено еквівалентність двох природних означень самоподібності для інверсних напівгруп (Означення 3.9 та Твердження 3.10).

Знайдено явний вигляд автомата, що породжує напівгрупу суміжності плиток мозаїки Пенроуза (Твердження 3.13). Аналогічна напівгрупа розглядалася іншими авторами J. Kellendonk and I. F. Putnam. Tilings, C*-algebras, and K-theory. // In Michael et al. Baake, editor, Directions in mathematical quasicrystals. volume 13 of CRM Monogr. Ser.. pages 177--206. --- Providence, RI:AMS, American Mathematical Society. --- 2000., але без обчислення її дії на відповідному зсуві.

Алгебраїчні аспекти самоподібності:

Знайдено дві алгебраїчні моделі самоподібності груп: віртуальні ендоморфізми та підстановкові бімодулі, та досліджено зв'язки між ними (Розділ 4). Розпочато систематичне вивчення ітерацій віртуальних ендоморфізмів. Зокрема, показано як за допомогою віртуального ендоморфізму можна визначати самоподібні дії груп (Твердження 3.57).

Показано зв'язок між самоподібними діями та позиційними системами числення (3.5.4). Повністю описано самоподібні дії вільних абелевих груп у термінах систем числення (підрозділ 3.6). Останній опис (для випадку бінарного дерева) було отримано в спільній роботі із С. Сідкі.

Доведено еквівалентність комбінаторного та метричного означення стискуючої самоподібності (Твердження 4.9). Поняття стискуючої самоподібності використовувалося раніше при дослідженні окремих прикладів самоподібних груп. Чітке означення стискуючої самоподібності і еквівалентність двох означень є новим результатом.

Побудовано алгоритм для проблеми слів у стискуючих самоподібних групах та знайдено поліноміальну оцінку складності цього алгоритму (Теорема 4.14).

Граничні простори самоподібних груп:

Введено поняття граничного простору та граничної динамічної системи самоподібної групи, та досліджено їх основні властивості.

Знайдено аксіоматичний опис граничного простору в термінах самоподібності. Показано, що граничний простір описується як єдиний власний ко-компактний G-простір зі стискуючою самоподібністю (Теорема 4.44).

Побудовано комбінаторну модель граничного простору, як ідеальної границі графа самоподібності (Теорема 4.58). Це також є новою комбінаторною моделлю множин Жюліа раціональних функцій.

Групи ітерованих монодромій:

Введено поняття групи ітерованих монодромій - самоподібної групи асоційованої із (частковим) самонакриттям топологічного простору (або орбіпростору) (підрозділ 5.2.1).

Розв'язано проблему Р.Пінка про обчислення груп Галуа ітерованих розширень поля функцій (Теорема 5.43).

Доведено, що граничний простір групи ітерованих монодромій розширюючого накриття чи суб-гіперболічної раціональної функції гомеоморфний відповідній множині Жюліа (Теорема 5.39).

Побудовану теорію стискуючих груп, груп ітерованих монодромій та граничних просторів можна вважати паралельною в сенсі словника Д.Саллівана до теорії гіперболічних груп за М.Громовим. Аналогії включають в себе як алгоритмічні, так і геометричні (поняття ідеальної границі та поняття граничного простору) аспекти.

Узагальнено теореми М.Шуба та М.Громова про будову розширюючих ендоморфізмів многовидів на випадок орбі-многовидів (Теорема 5.55 та Наслідок 5.56). Отримане доведення використовує розроблену теорію самоподібних груп, і є незалежним від результатів М.Шуба.

Показано зв'язок самоподібних дій вільних абелевих груп та самоподібних мозаїк площини (5.5.3).

Алгебри, асоційовані із самоподібними групами:

Знайдено найменшу та найбільшу самоподібну норму на груповій алгебрі самоподібної групи. Показано як ці норми пов'язані із зображеннями алгебри Кунца-Пімзнера, асоційованої із самоподібною групою (підрозділ 6.2).

Доведено простоту алгебри Кунца-Пімзнера, асоційованої із мінімальною самоподібною нормою (Теорема 6.21).

Знайдено зв'язок між групою Хігмана-Томпсона та алгеброю Кунца (Твердження 6.26).

Описано всі власні фактор-групи груп, породжених самоподібною групою та групою Хігмана-Томпсона (Теорема 6.30). Таким чином узагальнено результати К.Рьофера про групу Григорчука.

Теоретична та практична цінність дисертації. Робота має теоретичний характер. Розроблені в дисертаційній роботі методи можуть використовуватися для подальшого дослідження груп породжених автоматами, символьній та голоморфній динаміці, дослідженні спектрів нескінченних графів, та інших дослідженнях пов'язаних із самоподібними групами.

Дисертація може бути використана для читання спецкурсів з теорії груп та напівгруп на механіко-математичних факультетах університетів.

Особистий внесок здобувача. Всі основні результати дисертації отримані автором особисто. Перший розділ дисертації є оглядовим, а тому в ньому викладено відомі результати.

Підрозділи 2.1--2.2 основані на спільній роботі з Р. Григорчуком та В. Сущанським. Підрозділ 2.4 оглядовий і містить загальновідомі результати інших математиків. Підрозділ 2.5 містить спільні результати із В. Сущанським та О. Мацедонською (пункт 2.5.1). У підрозділі 2.6 пункт 1 основано на спільній роботі із Я. Лавренюком.

У розділі 3 підрозділ 3.6 містить результати одержані у співавторстві із С. Сідкі.

Решта результатів отримані автором особисто.

Апробація результатів дисертації. Результати дисертації доповідалися на: Симпозіумі із обчислювальної теорії груп та геометрії (1999, Ворвік, Англія), XVI Школі з алгебри (2000, Бразіліа), конференції <<Комбінаторика, динаміка, ймовірність>> (2000, Стокгольм), <<Випадкові блукання та геометрія>> (2001, Відень), Третій міжнародній алгебраїчній конференції в Україні (2001, Суми), Міжнародній конференції з функціонального аналізу (2001, Київ), конференції <<Дискретні групи та геометричні структури і їх застосування>>, (2002, Кортрайк, Бельгія), Міжнародній конференції з теорії напівгруп та груп у честь 65-річного ювілею Джона Роудза (2002, Порту, Португалія), конференції <<Гармонічний аналіз>> (2002, Люксембург), конференції <<Проскінченні групи і дискретні підгрупи груп Лі>> (2003, Обервольфах, Німеччина), міжнародній конференції <<Теорія груп: комбінаторні, геометричні та динамічні аспекти нескінченних груп>> (2003, Гаета, Італія), IV міжнародній алгебраїчній конференції в Україні (2003, Львів), конференції <<Аналіз та геометрія на випадкових структурах>>, (2004, Ліль, Франція), конференції <<Геометрична теорія груп, випадкові блукання та гармонічний аналіз>>, (2004, Кортона, Італія), конференції <<Групи, що діють на деревах та CAT(0)-просторах>>, (2004, Орсей, Франція), а також на семінарах та колоквіумах у Київському Національному університеті імені Тараса Шевченка, Інституті математики Національної Академії Наук України, Університеті Женеви (Швейцарія), Університеті Бразіліа, Королівському Технічному Інституті (Швеція), Дюсельдорфському Університеті імені Генріха Гейне (Німеччина), Університеті Риму (Італія), Науково-технічному Університеті Ліль I (Фрація), Міжнародному Університеті Бремена (Німеччина), Політехнічному Інституті Цюріха (Швейцарія), Університеті штату Нью Йорк у Стоні Брук (США), Університеті Упсали (Швеція).

За результатами дисертації читалися мінікурс <<Self-similar groups>> на літній школі <<Autour de groupes agissant sur des arbres, 3`eme cycle romand>> (Вілляр, Швейцарія) а також мінікурс <<Automata groups and holomorphic dynamics>> на літній школі <<Advanced Course on Automata Groups>> (Барселона, Іспанія).

Публікації. Результати дисертації опубліковано у 21 науковій публікації: одній монографії [21] та 20 фахових публікаціях [1--20].

Структура та обсяг дисертації. Дисертаційна робота складається зі вступу, шести розділів, висновків та бібліографії, що містить 136 найменувань. Повний обсяг роботи складає 305 сторінок, із них бібіліографія займає 13 сторінок.

ОСНОВНИЙ ЗМІСТ РОБОТИ

Перший розділ дисертації вводить необхідні означення і робить огляд відомих результатів, що використовуються далі в дисертації. Він включає в себе основні означення просторів слів та структур на них, необхідну термінологію з теорії графів, основні поняття теорії псевдогруп, етальних групоїдів та орбіпросторів. Результати цього розділу не є новими.

Другий розділ <<Групи та напівгрупи автоматних перетворень>> вивчає (асинхронні) автомати та (напів)групи автоматних перетворень. У першому підрозділі визначаються асинхронні автомати та їх дія на словах. Результати цього підрозділу є біль-менш класичними. Нагадаємо означення автомата (подібне означення можна знайти в Samuel Eilenberg. Automata, Languages and Machines. volume A. / Academic Press, New York, London. --- 1974.).

Асинхронним автоматом називається набір A=<XI, XO, Q, р , л> де:

1. XI, XO - скінченні множини (вхідний и вихідний алфавіти відповідно);

2. Q - множина внутрішніх станів автомата;

3. р:QЧ XI > Q - відображення (функція переходів);

4. л:QЧ XI >XO* - відображення (функція виходів);

Автомат A скінченний, якщо |Q|<?.

Якщо всі значення функції л ( . , . ) однобуквенні, то автомат A називається синхронним.

У другому підрозділі опусується побудова суперпозиції автоматів та визначається напівгрупа асинхронних автоматів. Доводиться, що ця напівгрупа збігається із напівгрупою неперервних перетворень множини Кантора (Теорема 2.8). Також доводиться, що множина перетворень, визначених скінченними автоматами є напівгрупою відносно суперпозиції (як наслідок Твердження 2.7).

У третьому підрозділі будуються алгоритми редукції скінченних асинхронних автоматів. Ці алгоритми дають можливість проводити ефективні обчислення в напівгрупах асинхронних автоматів (Теорема 2.36). Крім того, доводиться, що група та напівгрупа скінченних асинхронних автоматів не залежать від розміру скінченного алфавіту, над яким вони визначені (Теорема 2.33). Таким чином можна говорити про групу раціональних гомеоморфізмів та напівгрупу раціональних перетворень множини Кантора. У цьому ж підрозділі будується алгоритм для побудови автомата, оберненого до даного (Теорема 2.40). Таким чином показано, що в групі раціональних гомеоморфізмів множини Кантора позитивно розв’язується проблема слів.

Четвертий підрозділ вивчає синхронні автомати та автоморфізми кореневих дерев. На відміну від підрозділу 3, він в основному містить класичні результати. Вводяться необхідні технічні поняття, критерій оборотності автомата, згадуються алгоритми редукції (мінімізації) та вводиться техніка вінцевих рекурсій.

П’ятий підрозділ вивчає спеціальні класи синхронних автоматів. Описуються їх застосування до теорії груп та теорії динамічних систем.

Шостий підрозділ другого розділу вивчає групи, породжені синхронними автоматами з точки зору їх дій на кореневому дереві скінченних слів. Серед нових результатів цього підрозділу є критерій спряженості шарово-транзитивних груп (Теорема 2.59) та розв’язання проблеми Р. Григорчука про класифікацію груп Gw. Нагадаємо означення цих груп

Означення. Нехай w=w1w2 ... . Група Gw визначається як група автоморфізмів бінарного дерева X* ={0, 1}*, породжена перетвореннями a, bw, cw, dw, де

a(0v)=1v, a(1v)=0v

для всіх v е X*,

bw(1v)=1bу(w)(v), bw (0v)=0v, якщо w1=2,

0a(v) інакше,

cw (1v)=1c у(w) (v), c w (0v)=0v, якщо w1=1

0a(v), інакше,

d w (1v)=1d у(w) (v), d w (0v)=0v, якщо w1=0,

0a(v), інакше,

де у(w)=w2w3... - зсув послідовності w.

Наступна теорема класифікує групи Григорчука.

Теорема. Нехай послідовності w1=x1x2..., w2=y1y2 ... е {0, 1, 2}щ не є майже сталими. Тоді групи Gw1 та Gw2 ізоморфні тоді і лише тоді, коли існує підстановка р е S(0, 1, 2) така, що р(xn)=yn для всіх n.

Шостий підрозділ закінчується вивченням графів Шрайєра дії груп на границі дерева. Головним результатом цього розділу є доведення локального ізоморфізму майже всіх графів Шрайєра шарово-транзитивної групи (Твердження 2.70).

Метою третього розділу <<Самоподібні групи та віртуальні ендоморфізми>> є розробка алгебраїчної техніки для роботи із самоподібними групами та інтерпретація самоподібності груп у термінах підстановкових бімодулів та віртуальних ендоморфізмів груп.

Розділ розпочинається обговоренням різних еквівалентних означень самоподібності. Перше визначення використовує дії на словах. А саме

Означення. Точна дія групи G на просторі Xщ називається самоподібною якщо для довільних g е G, і x е X існують h е G і y е X такі, що

g(xw)=yh(w),

для всіх w е Xщ.

Крім цього означення, самоподібні групи можна визначати в термінах теорії автоматів (як синхронний автомат, множина станів якого є групою та як групу, породжену автоматом) та за допомогою вінцевих рекурсій. У кінці першого підрозділу розглядаються класичні приклади самоподібних груп (група Григорчука, групи Гупти-Сідкі, група Гупти-Фабриковського, група Браннера-Сідкі-Вієйри, група <<блимаючих лампочок>>, самоподібна дія вільної групи та стабілізатори вершини в транзитивних діях на графах).

У другому підрозділі третього розділу вводиться поняття самоподібної інверсної напівгрупи. При цьому узагальнюється означення самоподібної групи як

автомата. Розглядаються різні приклади самоподібних інверсних напівгруп: напівгрупа пов’язана із <<системою числення Фібоначчі>>, напівгрупа породжена <<адичними пертвореннями>> (діаграмами Вершика-Браттелі) та напівгрупа суміжності плиток мозаїки Пенроуза.

Третій підрозділ вивчає віртуальні ендоморфізми - один із двох основних інструментів вивчення самоподібних груп. Віртуальним ендоморфізмом групи G називається гомоморфізм із підгрупи скінченного індексу групи G у групу G. Із ітераціями віртуального ендоморфізму ц пов’язується (оскільки область визначення Dom цn ітерацій зменшується) дерево класів суміжності групи G за підгрупами Dom цn. Група G діє на цьому кореневому дереві автоморфізмами шарово-транзитивно. У підрозділі 3.3 вивчається ця дія, його ядро (доводиться, що ядром є найбільша нормальна підгрупа, що є інваріантною відносно дії віртуального ендоморфізму, Твердження 3.22), будуються спеціальні інваріантні підгрупи.

У четвертому підрозділі вводиться інший інструмент вивчення самоподібних дій - підстановкові бімодулі.

Означення. Нехай G - група. (Підстановковий) G-бімодуль - це множина M із лівою і правою комутуючими діями G на M підстановками, тобто із двома відображеннями G Ч M > M:(g, m) > g . m і M Ч G> M:(m, g) > m . g такими, що

1 . m=m . 1=m для всіх m е M;

(g1g2) . m=g1 . (g2 . m) і m . (g1g2)=(m . g1) . g2 для всіх g1, g2 е G і m е M;

(g1 . m) . g2=g1 . (m . g2) для всіх g1, g2 е G і m е M.

Ми показуємо зв’язок між підстановковими бімодулями та віртуальними ендоморфізмами. А саме, за даним віртуальним ендоморфізмом ц групи G будується природнім чином бімодуль ц(G)G, що складається із формальних виразів вигляду ц(g1)g2, із природніми ототожненнями та природними діями групи G на них. В інший бік, якщо для бімодуля виконані певні прості технічні умови, то його можна відновити вищенаведеним способом за віртуальним ендоморфізом асоційованого із бімодулем. Тому для наших потреб віртуальні ендоморфізми та підстановкові бімодулі є еквівалентними поняттями, але в різних випадках вигідно

використовувати різні конструкції.

Якщо ми маємо самоподібну дію групи G над алфавітом X, то відповідним асоційованим бімодулем, або бімодулем самоподібності є множина X.G перетворень вигляду

v > xg(v),

де x е X, і g е G (див. підпункт 3.4.2 та Означення 3.37). Із означення самоподібної дії легко випливає, що множина X.G є підстановковим бімодулем відносно операцій суперпозиції перетворень.

Ці ідеї використовуються у п’ятому підрозділі до вивчення самоподібних дій. У ньому показано, що якщо у бімодуля права дія є вільною і має скінченне число орбіт, то такий бімодуль асоційований із деякою самоподібною дією і ця самоподібна дія визначена однозначно з точністю до спряження. Більше того, подано ефективний метод побудови відповідної самоподібної дії. Зокрема, таким чином ми отримуємо самоподібну дію із віртуального ендоморфізму.

Ця конструкція основана на поняттях базису бімодуля та тензорного добутку. А саме, базисом підстановкового бімодуля називається трансверсаль орбіт його правої дії. Якщо права дія G-бімодуля M вільна, а X - базис бімодуля, то тоді довільний елемент бімодуля єдиним чином записується у вигляді x.g, де x е X, а g належить групі G. Зокрема, для довільних x е M та g е G однозначно визначені елементи y е M та h е G такі, що g.x=y.h. Цю рівність можна інтерпретувати як визначення автомата над алфавітом X та множиною станів G, що будучи в стані g і отримуючи на вхід букву x, дає на вихід букву y та переходить у стан h. Ми позначаємо цей автомат A(G, M, X), і називаємо стандартним автоматом, заданим бімодулем та базисом (Означення 3.44). Цей автомат визначає деяку самоподібну дію групи G, що називається стандартною самоподібною дією визначеною бімодулем та базисом. Ми вивчаємо цю стандартну дію у підрозділі 5: показуємо її зв’язок із поняттям тензорного добутку бімодулів, виводимо формулу стандартної дії побудованої за віртуальним ендоморфізмом (Твердження 3.45), показуємо, що довільна самоподібна дія є стандартною для відповідного асоційованого бімодуля та інтерпретуємо самоподібні дії у термінах узагальнених систем числення. А саме, стандартна дія задана за віртуальним ендоморфізмом наступним чином.

Твердження. Нехай X={x1=ц(r1)h1, x2= ц(r2)h2, ..., xd= ц(rd)hd} - базис підстановкового бімодуля ц(G)G. Тоді, для довільного g е G і xi е X маємо

g. xi=xj.hj-1ц(rj-1gri)hi,

де j визначено єдиним чином умовою rj-1gri е Dom ц .

Тому, якщо алфавіт X={x0, x1, ..., xd-1} ототожнено із множиною

{ц(r0)h0, ц (r1)h1, ... , ц (rd-1)hd-1},

то довільному нескінченному слову xi0xi1xi2 ... е Xщ можна поставити у відповідність формальний вираз

ri0 ц-1(hi0ri1) ц-2(hi1ri2)ц-3(hi2ri3)... .

Тоді, для того, щоб знайти образ слова xi0xi1xi2... під дією елемента g е G потрібно просто помножити даний вираз зліва на g, а потім звести до вигляду аналогічного початковому.

Ми показуємо, що стандартна самоподібна дія, з точністю до спряження, залежить лише від бімодуля (не залежить від вибору базиса) та описуємо ядро стандартної дії (Твердження 3.59).

В останньому, шостому підрозділі розділу 3 ми застосовуємо розроблену техніку до класифікації самоподібних дій вільних абелевих груп. Ми показуємо, що самоподібна дія групи Zn (якщо вона шарово-транзитивна на дереві) на просторі нескінченних послідовностей можна описати як дію групи Zn на своєму <<B-адичному>> поповненні, тобто на групі формальних рядів

r0+B(r1)+B2(r2)+...,

де B - деяка цілочисельна матриця із визначником більшим за модулем одиниці, а ri - елементи деякої системи редставників класів суміжності групи Zn за підгрупою B(Zn). Дане поповнення збігається із замиканням групи Zn у рупі автоморфізмів дерева X*. Матриця B відіграє тут роль <<основи>> системи числення, а відповідна система представників класів суміжності є <<множиною цифр>> системи. Така інтерпретація пов'язана із тим, що довільна точна дія абелевої групи є вільною, а тому в нашому випадку B-адичне поповнення можна ототожнити із множиною Xщ нескінченних послідовностей, на якому вона діє

точно і транзитивно.

Розділ 4 <<Стискуюча самоподібність та граничний простір>> розглядає найбільш вивчений клас самоподібних дій. Нагадаємо, що якщо G - група, що діє самоподібно на множині слів X*, а g є G та v є X*, то g|v визначається як елемент, такий, що

g(vw)=g(v)g|v(w)

для всіх w є X*.

Означення. Самоподібна дія групи G називається стискуючою (чи гіперболічною), якщо існує скінченна множина N<G така, що для довільного g є G існує n0 є N таке, що

g|v є N,

для всіх v є Xn, n > n0. Мінімальна множина N з такою властивістю називається нуклеусом самоподібної дії.

У першому підрозділі ми доводимо перші прості властивості стискуючих груп та деякі технічні твердження. Зокрема, ми показуємо, що властивість дії бути стискуючою залежить лише від асоційованого бімодуля. Крім того, ми показуємо, що у випадку, коли група скінченно-породжена, можна дати інше означення стискуючої групи.

Означення. Нехай G - скінченно породжена група, що діє самоподібно на X*. Число

с=limsupn> ? nvlimsup l(g) > ?maxv є Xn (l(g|v)/l(g))

називається коефіцієнтом стиску дії.

Подібним чином визначається також і коефіціент стиску (спектральний радіус) віртуального ендоморфізму, асоційованого із самоподібною дією. Ми показуємо, що самоподібна дія є стискуючою тоді і лише тоді, коли її коефіціент стиску (чи коефіціент стиску віртуального ендоморфізму) менший одиниці (Твердження 4.9).

У цьому ж підрозділі ми описуємо алгоритм для розв’язку проблеми слів у стискуючих групах та оцінюємо час його роботи. А саме, ми доводимо наступну теорему.

Теорема Якщо існує точна стискуюча дія скінченно-породженої групи G, то для довільного е>0 існує алгоритм поліноміальної складності степеня не вище log|X|/(-logс+е), що розв'язує проблему рівності у групі G, де с - коефіціент стиску групи.

У наступному підрозділі розвинута техніка застосовується до вивчення скінченно-станових дій вільних абелевих груп. Ми показуємо, що самоподібна дія вільної абелевої групи, визначена за B-адичною системою числення діє скінченними автоматами тоді і лише тоді, коли вона є стискуючою, що в свою чергу еквівалентне тому, що матриця B-1 є стискуючою, тобто всі її власні числа менші одиниці за модулем (Теорема 4.15). Наводяться також деякі приклади стискуючих самоподібних дій вільних абелевих груп.

У третьому підрозділі вивчаються граничні простори самоподібних стискуючих груп. Ці топологічні простори природньо асоційовані зі стискуючими діями. На початку підрозділу ми вводимо простір на якому діє група G (так званий граничний G-простір XG). А саме: нехай G - самоподібна група, що діє на множині слів X*. Тоді граничний простір XG визначається як фактор простору X-щЧG, де X-щ - простір нескінченних вліво послідовностей, за асимптотичною еквівалентністю, яка визначається наступним чином.

Два елементи ...x2x1.g and ...y2y1.h множини X-щ .G асимптотично еквівалентні тоді і лише тоді, коли існує послідовність hn, n>0, елементів нуклеуса N такі, що hn.xn=yn.hn-1 для всіх n>1 і h0g=h.

У дисертації означення граничного простору XG дещо інше, а вищенаведене означення сформульовано як теорема (Теорема 4.20). Початкове означення дещо складніше, оскільки воно не залежить від вибору базису X підстановкового бімодуля.

Ми доводимо, що граничний простір XG є метризовним та має скінченну топологічну розмірність (Твердження 4.21). Крім того ми показуємо, що група G діє на ньому природнім чином гомеоморфізмами. Ця дія є ко-компактною та власною (розривною), і простір орбіт XG також називається граничним простором самоподібної дії (простір XG називається граничним G-простором).

Граничний простір JG можна визначити і безпосередньо як фактор простору нескінченних послідовностей X-щ за відношенням еквівалентності, визначеним наступним чином.

Означення Кажемо, що два елементи ...x2x1.g, ...y2y1.h асимптотично еквівалентні відносно дії групи G, якщо існує обмежена послідовність gk, k є N така, що

gk(xkxk-1... x2x1)= ykyk-1... y2y1

для кожного k є N.

Тут послідовність називається обмеженою, якщо її множина значень скінченна.

У дисертації вивчається граничний простір JG та його природнє розбиття на <<плитки>>. Це розбиття використовується для знаходження аксіоматичного опису граничного простору XG як єдиного ко-компактного власного G-простору зі стискуючою самоподібністю (Теорема 4.44).

Іншим можливим описом граничного простору JG є його визначення як гіперболічної границі природньо визначеного гіперболічного за М.Громовим графа (Теорема 4.58). Цей граф є комбінаторною моделлю граничного простору і може бути ефективно використаним для його вивчення. Цим самим показано зв’язок між гіперболічними групами та групами зі стискуючою самоподібністю у стилі словника Салівана Dennis Sullivan Quasi-conformal homeomorphisms and dynamics I, solution of the Fatou-Julia problem on wandering domains. // Ann. Math. --- 1985. --- 122. --- 401--418..

Наступний, п’ятий розділ <<Групи ітерованих монодромій>> присвячений новому природньому джерелу самоподібних груп. Ці групи асоційовані із самонакриттями орбіпросторів, зокрема із комплексними раціональними функціями. Початок розділу присвячено визначенню груп ітерованих монодромій, підготовці необхідної техніки для роботи з ними та доводиться формула для їх

обчислення. Теорія груп ітерованих монодромій стає симетричнішою у випадку, коли розглядаються не просто накриття просторів, а накриття орбіпросторів, тобто просторів із деякою додатковою груповою структурою. Відповідна техніка орбіпросторів розробляється на початку п’ятого розділу. Ми показуємо, зокрема, які орбіпростори канонічно асоційовані із пост-критично скінченними раціональними функціями.

У підрозділі <<Ітеровані монодромії>> визначаються групи ітерованих монодромій і доводяться їх основні властивості. Групою ітерованих монодромій накриття p: M1 > M (позначення IMG(p)), де M1 - відкритий під-орбіпростір орбіпростору M називається фактор-група

р1(M)/?n>0Stn,

де Stn < р1(M) - ядро дії монодроміями на n-тій ітерації pn:Mn > M самонакриття p.

Ми показуємо, на протязі підрозділу, що група ітерованих монодромій діє природньо на деякому кореневому дереві, та що ця дія є спряженою зі стандартною самоподібною дією, побудованою за природньо визначеним підстановковим бімодулем M(p). Доведені твердження дають ефективну формулу для обчислення груп ітерованих монодромій як груп, породжених автоматами (Теорема 5.27).

У наступному підрозділі <<Групи ітерованих монодромій розширюючих відображень>> показано, що у випадку, коли накриття p є розширюючим, множина Жюліа відображення p збігається із граничним простором його групи ітерованих монодромій. А саме, доведено наступну теорему.

Теорема Нехай p:M1 > M - самонакриття лінійно зв'язного і локально однозв'язного орбіпростору M із повною структурою довжини. Припустимо, що фундаментальна група орбіпростору M скінченно-породжена, накриття p - рівномріно розширююче на своїй множині Жюліа і що групи ізотропій орбіпростору M зображуються точно ітерованими монодроями. Тоді асоційований бімодуль M(p) самонакриття є гіперболічним і наступні самонакриття спряжені:

обмеження p:Jp > Jp самонакриття p на орбіпростір Жюліа,

зсув s: Jр1(M) > J р1(M),

зсув s: : JIMG(p) > JIMG(p),

де J р1(M) і JIMG(p) побудовано за гіперболічним бімодулем M(p) і стандартною стискуючою дією групи IMG(p), відповідно.

У підрозділі 5.4 застосовуються отримані результати до розв’язання проблеми Р. Пінка про обчислення груп Галуа ітерованих розширень поля функцій. Нехай f є C[z] - многочлен над C. Для n>0 визначимо многочлен Fn(z)=fn(z)-t є C(t)[z] над полем C(t), де fn(z) позначає n-ту ітерацію f. Нехай Щn - поле розкладу многочлена Fn, і нехай Щ=Un є N Щn. Ми доводимо наступну теорему.

Теорема Нехай f є C[z] - многочлен, для якого множина C\ P лінійно зв'язна. Тоді замкнена група ітерованих монодромій IMG(f) ізоморфна групі Галуа Aut(Щ/Omega/C(t)), де Щ=?n>0 Щn.

Тут замкненою групою ітерованих монодромій називається замикання групи ітерованих монодромій у групі автоморфізмів кореневого дерева.

Крім того, у цьому ж підрозділі ми показуємо застосування груп ітерованих монодромій до вивчення динаміки ітерацій раціональних функцій та геометрії їх множин Жюліа (Теорема 5.47).

У підрозділі 5.5 <<Самонакриття орбі-многовидів>> ми узагальнюємо результати М.Шуба та М.Громова про розширюючі ендоморфізми многовидів на випадок орбі-многовидів. Основним результатом є наступне твердження.

Наслідок Нехай p:M > M - розширююче самонакриття орбі-многовиду, що розгортається. Тоді орбі-многовид M ізоморфний орбі-многовиду афінної дії фундаментальної групи р1(M) на нільпотетній зв'язній та однозв'язній групі Лі L. Самонакриття p індуковане деяким розширюючим автоморфізмом групи Лі L, обернений до якого індукує віртуальний ендоморфізм групи р1(M) так, що якщо J р1(M) - граничний простір асоційованої самоподібної дії, то динамічні системи (p, J р1(M)) та (L, M) топологічно спряжені.

Як приклади ми розглядаємо самонакриття торів, самоподібні дії вільних абелевих груп та відповідні системи числення на Rn. Крім цього ми розглядаємо також групу Гайзенберга та деякі віртуально абелеві групи.

Розділ 6 присвячено алгебрам асоційованим із самоподібними групами. Якщо M - бімодуль над групою G, асоційований із її самоподібною дією, то, перейшовши до лінійних оболонок над деяким полем, ми отримуємо бімодуль над груповою алгеброю. Такі бімодулі з’являються природньо при вивченні зображень самоподібних груп, обчисленні їх спектрів та вивченні випадкових блукань. При обчисленні спектрів природньо постає питання які поповнення групової алгебри (над полем комплексних чисел) узгоджені із відповідним бімодулем. Це є

центральним питанням цього розділу.

Розділ розпочинається із огляду понять пов’язаних із бімодулями над алгебрами та конструкцією лінійної оболонки підстановкового бімодуля. Крім того вивчаються ідеали, які інваріантні під дією бімодуля, доводиться що існує єдиний максимальний такий ідеал (він відіграє роль ядра стандартної самоподібної дії групи). Ці дослідження близькі за духом до досліджень С. Сідкі Said N. Sidki.