Самоподібні групи автоматів

--- Показано, що із самоподібними групами природньо асоціюються відповідні алгебри Кунца-Пімзнера, та показано, що алгебри Кунца-Пімзнера, побудовані за мінімальною самоподібною нормою є простими. Таким чином, самоподібні групи є також джерелом простих C*-алгебр. Знайдено природнє точне зображення простої групи Хігмана-Томпсона в унітарній групі алгебри Кунца та показано, що аналогічна група визначена за алгеброю Кунца-Пімзнера самоподібної групи, є також близькою до простої (і є простою для багатьох самоподібних груп). Таким чином, самоподібні групи є цікавим джерелом нескінченних скінченно-породжених простих груп.

СПИСОК ОПУБЛІКОВАНИХ РОБІТ ЗА ТЕМОЮ ДИСЕРТАЦІЇ

1. Nekrashevych V. Uniformly bounded spaces// Вопросы Алгебры. --- 1999. --- Т. 14. --- ст. 47--97.

2. Nekrashevych V., Sushchansky V. Confinal structure of the automorphisms of rooted trees // Доп. НАН України --- 1999. --- № 11. --- ст. 50--53. (особистий внесок --- Теореми 4, 6 та 9).

3. Григорчук Р.И., Некрашевич В.В., Сущанский В.И. Автоматы, динамические системы и группы // Труды мат. института им. Стеклова. --- 2000. --- № . 231. --- ст. 134--214. (особистий внесок --- алгоритми для обчислень з асинхронними автоматами, теорема про ізоморфізм між групами асинхронних автоматів над різними алфавітами (параграфи 2.5--2.8), приклади асинхронно автоматних груп (розділ 5) а також властивості графів Шраєра та орбіт дій груп автоморфізмів кореневого дерева на границі (параграфи 6.7--6.8).)

4. Григорчук Р.И., Некрашевич В.В. Группа асинхронных автоматов и рациональные гомеоморфизмы множества Кантора // Мат. Заметки. --- 2000. --- Т. 67. --- С. 680--686. (особистий внесок --- означення групи раціональних гомеоморфізмів множини Кантора та теорема про спряженість груп скінченних автоматів, яка обгрунтовує це означення.)

5. Macedonska O., Nekrashevych V., Sushchansky V.I. // Доп. НАН України --- 2000. --- Т. 12. --- С. 36--39. (особистий внесок --- теорема про ізоморфізм групи біреверсивних автоматів та підгрупи співмірювача вільної групи.)

6. Nekrashevych V. Stabilizers of transitive actions on locally finite graphs // Int. J. of Algebra and Computation. --- 2000. --- № 10. --- Vol. 5. --- p. 591--602.

7. Gawron P. W., Nekrashevych V.V., Sushchansky V.I. Conjugation in tree automorphism groups // Int. J. of Algebra and Computation. --- 2001. --- № 5. --- Vol. 11. --- p.529--547. (особистий внесок --- доведення основної теореми про класи спряженості автоморфізмів дерева у випадку, коли автоморфізм не фіксує вершину дерева.)

8. Nekrashevych V. State-closed groups of automatic transformations// Вопросы алгебры. 2001. --- № . 17. --- С. 16--21.

9. Некрашевич В.В., Сущанський В.І. Автомати з обмеженою пам'яттю і ендоморфізми зсуву // Доп. НАН України. --- 2001. --- № 4. --- С. 18--21. (особистий внесок --- Теорема 3.)

10. Lavreniuk Y.V., Nekrashevych V.V., Rigidity of branch groups acting on rooted trees // Geom. Dedicata. --- 2002. --- № 1 --- Vol. 89. --- p. 155--175. (особистий внесок --- Теорема 7.1, Твердження 7.2 та формулювання Теореми 7.3 у термінах гомеморфізмів границі дерева.)

11. Nekrashevych V.V. Virtual endomorphisms of groups // Algebra and Discrete Mathematics. --- 2002. --- № 1. --- Vol. 1. --- p. 96--136.

12. Nekrashevych V.V. Hyperbolic spaces from self-similar group actions // Algebra and Discrete Mathematics. --- 2003. --- № 1. --- Т. 2. --- С. 68--77.

13. Nekrashevych V.V. Self-similar inverse semigroups and groupoids // Ukrainian Congress of Mathematicians: Functional Analysis. --- Kyiv: Institute of Mathematics. --- 2002. --- p. 176--192.

14. Некрашевич В.В. Групи ітерованих монодромій // Доп. НАН України --- 2003. --- № 4. --- С. 18--20.

15. Bartholdi L., Grigorchuk R., Nekrashevych V. From fractal groups to fractal sets // Fractals in Graz. Analysis - Dynamics -- Geometry -- Stochastics. --- Birkhauser Verlag, Basel, Boston, Berlin. --- 2003. --- p. 5--118. (особистий внесок --- результати параграфів 3.3--3.7, 4.2, розділу 5 (за виключенням Теореми 5.8), розділу 6, розділу 9, параграфу 10.3 та розділу 13.)

16. Nekrashevych V., Sidki S. Automorphisms of the binary tree: state-closed subgroups and dynamics of 1/2-endomorphisms // Groups: Topological, Combinatorial and Arithmetic Aspects. --- London Mathematical Society Lecture Notes. --- 2004. --- Vol. 311. --- p. 375--404. (особистий внесок --- результати розділів 4--6 (за винятком Теореми 5.2).)

17. Bondarenko E., Nekrashevych V. Post-critically finite self-similar groups // Algebra and Discrete Mathematics. --- 2003. --- № 4. --- vol. 2. --- p. 21--32. (особистий внесок --- поняття пост-критично скінченної групи, результати розділів 3 та 4 та Наслідок 5.4.)

18. Nekrashevych V. Cuntz-Pimsner algebras of group actions //Journal of Operator Theory. --- 2004. --- № 2. --- vol. 52. --- p. 223--249.

19. Мочко Е., Некрашевич В., Сущанский В. Динамика треугольных преобразований последовательностей над конечным алфавитом // Мат. Заметки --- 2003. --- № 3. --- Т. 73. --- С. 466--468. (особистий внесок --- Теорема 2.2.)

20. Леонов Ю.Г., Некрашевич В.В., Сущанський В.І. Зображення вінцевих добутків унітрикутними матрицями // Доп. НАН України --- 2005. --- № 4. --- С. 29--33. (особистий внесок --- застосування техніки бімодулів та тензорних степенів до зображень груп трикутними матрицями та інтерпретація їх у термінах підстановкових зображень.)

21. Self-similar groups / Nekrashevych V. --- Mathematical Surveys and Monographs. Amer. Math. Soc., Providence, RI, volume 117. --- 2005. --- 231 p.

АНОТАЦІЇ

Некрашевич В.В. Самоподібні групи автоматів. -- Рукопис. -- Дисертація на здобуття наукового ступеня доктора фізико-математичних наук за спеціальністю 01.01.06 -- алгебра і теорія чисел. Київський національний університет імені Тараса Шевченка, Київ, 2006.

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

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

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

Ключові слова: групи автоматів; групи, що діють на кореневому дереві; групи ітерованих монодромій; множини Жюліа; самоподібні множини; орбіпростори.

Некрашевич В.В. Самоподобные группы автоматов. -- Рукопись. -- Диссертация на соискание ученой степени доктора физико-математических наук по специальности 01.01.06 -- алгебра и теория чисел. Киевский национальный университет имени Тараса Шевченко, Киев, 2006.

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

Построено алгоритм для вычислений с асинхронными автоматами и алгоритмы для решения проблемы равенства в группах и полугруппах, порождённых автоматами. Доказано, что группа конечных асинхронных автоматов не зависит от размера алфавита над которым автоматы определены. Таким образом введено новую группу - группу рациональных гомеоморфизмов множества Кантора. Решено проблему Р. Григорчука о классификации групп Gw.

Построена алгебраическая теория самоподобия групп. Определено понятие самоподобной группы и самоподобной инверсной полугруппы. Показано, что самоподобные инверсные полугруппы естественно возникают как полугруппы, связанные с минимальными динамическими системами Вершика и как полугруппы смежности плиток апериодических самоподобных мозаик. Разработано технику для работы с самоподобными группами: виртуальные эндоморфизмы и перестановковые бимодули. Показана связь между перестановковыми бимодулями и виртуальными эндоморфизмами групп. Полностью описано самоподобные транзитивные действия свободных абелевых групп. Показана связь таких действий с системами исчисления.

Изучено класс групп с сжимающим самоподобием. Доказано эквивалентность двух определений сжимающего самоподобия (сокращение длины слов под действием виртуального эндоморфизма и определение с использованием понятия нуклеуса действия). Доказано, что проблема слов в сжимающих группах имеет полиномиальную сложность и построено алгоритм для решения проблемы слов в таких группах.

Описаны сжимающие действия свободных абелевых групп и показано, что в этом случае соответствующие системы исчисления продолжаються на действительные векторные пространства и связаны с самоподобными <<цифровыми>> мозаиками.

Введено понятие предельного пространства самоподобной сжимающей группы. Эти пространства имеют фрактальную структуру и, для случая групп итерированных монодромий, гомеоморфны множествам Жюлиа расширяющих отображений. Изучена структура предельных пространств и описаны различные способы их построения: как факторы пространства последовательностей, аксиоматическое, как предела последовательности конечных графов и как границы гиперболического по М. Громову графа. Эти различные подходы позволяют изучать предельные пространства (а значит, и соответствующие множества Жюлиа) используя различные техники, адекватные соостветствующим вопросам.

Построено теорию групп итерированных монодромий - естественных примеров самоподобных групп. Группы итерированных монодромий асоциированы с самонакрытиями (орби)пространств и содержат информацию о комбинаторике их итераций. Найдена формула для вычисления естественного точного действия групп итерированных монодромий на корневом дереве слов. Этим в частности решена проблема Р. Пинка о вычислении групп Галуа итерированных расширений поля функций.

Показано, что группа итерированных монодромий содержит всю <<существенную>> информацию о соответсвующем самонакрытии, если оно является разширяющим. А именно, показано, что можно по группе итерированных монодромий восстановить множество Жюлиа (как предельное пространство группы) и действие отображения на нём. Этим открыты новые возможности изучения множеств Жюлиа с помощью техники самоподобных групп и групп, порождённых конечными автоматами, а также возможность применения теории групп к голоморфной динамики.

Кроме итераций рациональных функций, группы итерированных монодромий могут применятся и к другим динамическим системам. В частности, показано как можно использовать разработанную теорию к обобщению теоремы М. Шуба и М. Громова о разширяющих эндоморфизмах многообразий на случай орби-многообразий. Отметим, что наше доказательство не зависит от результатов М. Шуба (а использует только теорему М. Громова о группах полиномиального роста).

Изучены алгебры, асоциированные с самоподобными группами. Введено понятие самоподобного унитарного представления и показано, что существует наименьшая и наибольшая C*-нормы на групповой алгебре самоподобной группы, которые согласованы с самоподобием. Эти исследования проливают свет на технику операторных рекурсий, которая использовалась Р. Григорчуком, А. Жуком и Л. Бартолди.

Показано, что с самоподобными группами естественно асоциируются соответствующие алгебры Кунца-Пимзнера. Доказано, что такие алгебры (если построены с использованием минимальной самоподобной нормы) просты. Таким образом, самоподобные алгебры являются источником простых C*-алгебр. Найдено естественное точное представление группы Хигмана-Томпсона в унитарной группе алгебры Кунца и показано, что аналогичная группа, построенная по алгебре Кунца-Пимзнера самоподобной группы, также близка к простой (и является простой для многих самоподобных групп). Таким образом, самоподобные группы являються также и источником бесконечных простых конечно-определённых групп.

Ключевые слова: группы автоматов; группы, действующие на корневом дереве; группы итерированных монодромий; множества Жюлиа; самоподобные множества; орбипространства.

Nekrashevych V. V. Self-similar groups of automata. -- Manuscript. -- The thesis for degree of Doctor in physics and mathematics by the speciality 01.01.06 -- algebra and number theory. Kyiv national Taras Shevchenko university, Kyiv, 2006.

We investigate the properties of self-similar groups, their connections to theory of automata, iterations of virtual endomorphisms, operator algebras and dynamical systems. We construct a theory of contracting groups and their limit spaces. An algorithm for solving the word problem in groups and semigroups of asynchronous automata is constructed. It is proved that contracting groups have word problem of polynomial complexity. New methods of proving non-isomorphism of groups are developed. They made it possible to give an answer to the problem of R. Grigorchuk about classification of the groups Gw up to isomorphisms.

Iterated monodromy groups are introduced. We prove that the limit spaces of the iterated monodromy groups of expanding maps coincide with the Julia sets of the maps. In this way, new possibilities of applications of the group theory to holomorphic dynamics were discovered. We have found a formula for computation of the natural action of the iterated monodromy group on a rooted tree. This solves a problem of R. Pink on computation of Galois groups of iterated extensions of the field of functions.

It is proved that the Cuntz-Pimsner algebras, which are naturally associated with self-similar groups, are simple. We have found a new connection between the Higmann-Thompson groups and Cuntz algebras. It is proved that all proper quotients of the group generated by the Higmann-Thompson group and a self-similar group are abelian. We show how to find the maximal abelian quotient of such a group. This gives a new class of infinite simple groups.

Key words: automata groups; groups acting on rooted trees; iterated monodromy groups; Julia sets; self-similar sets; orbispaces.

Размещено на Allbest.ru