Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
КИЇВСЬКИЙ НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ
ІМЕНІ ТАРАСА ШЕВЧЕНКА
НЕКРАШЕВИЧ Володимир Володимирович
УДК 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* збігається із дією якогось елемента цієї ж групи.
Самоподібність є зручним інструментом для дослідження груп, оскільки перехід до дії на піддереві дозволяє доводити властивості груп за індукцією. Важливу роль при цьому відіграє властивість скорочення довжини елементів групи при переході до обмеження на піддерево. Самоподібні групи із такою властивістю дістали назву стискуючих. Стискуючі групи є найбільш вивченим класом самоподібних груп. Велика частина дисертації присвячена систематичному вивченню стискуючих самоподібних груп.
Одним із перших прикладів самоподібної групи є відома група Григорчука2, яка початково будувалася як особливо простий приклад періодичної групи. Згодом було помічено, що вона має проміжний ріст3, і таким чином дає відповідь на відому проблему Дж.Мілнора про існування таких груп. Група Григорчука була також використана при розв'язанні інших проблем: наприклад, це перший приклад аменабельної групи, що не належить до класу елементарно аменабельних груп4.
Пізніше почали вивчатися аналоги групи Григорчука та розроблятися техніка для вивчення таких груп. Тут варто згадати групи Гупти-Сідкі5, групу Браннера-Сідкі-Вієйри6 та групу описану Р.Григорчуком та А.Жуком у статті7.
Характерною властивістю автоматних груп є простота їх визначення при складності і незвичності їх теоретико-групових властивостей. При цьому спочатку вони розглядалися в першу чергу як цікаві (контр)приклади. Ця ситуація аналогічна тому, як перші фрактальні множини (множина Кантора, килим Серпінського, та інші) були на час своєї появи цікавими прикладами множин із незвичними топологічними властивостями. Як відомо, пізніше виявилося, що такі фрактальні множини з'являються природньо в багатьох розділах математики та природознавства8.
Так само згодом стало зрозуміло, що самоподібні групи також є не просто цікавими прикладами груп, але й виникають природнім чином в теорії груп та інших розділах математики.
Так, наприклад Р.Григорчук у 1997 році на конференції з теорії груп у Базі означив клас гіллястих груп (branch groups). Тоді ж було доведено Р. Григорчуком та Д. Вілсоном, що клас екстремальних (just infinite) груп (нескінченних груп, всі власні фактори яких скінченні) розпадається на три класи: майже простих, спадково екстремальних та гіллястих. У класі проскінченних груп лише останні два типи можливі. Р.Григорчуком було також доведено, що довільна скінченно-породжена група має екстремальну фактор-групу. Ці результати показують важливість класу гіллястих груп, першими прикладами яких є група Григорчука та її аналоги. Детальніше про даний напрямок досліджень можна прочитати в9.
Крім важливості самоподібних груп в алгебрі, вони знайшли своє застосування в інших галузях математики: спектральній теорії груп та нескінченних графів, теорії lІ-інваріантів, а також голоморфній та символьній динаміці (див. роботи10).
Після введення автором понять групи ітерованих монодромій та граничного простору з’явився новий місток між теорією самоподібних груп та топологічною і голоморфною динамікою. Екзотичні групи типу групи Григорчука стали тепер не просто (контр)прикладами, а природніми об’єктами пов’язаними, наприклад, із ітераціями раціональних функцій. Стало можливо застосовувати теорію груп породжених автоматами до розв’язання задач голоморфної динаміки. Так, наприклад, автору дисертації разом із Л. Бартолді вдалося розв’язати проблему Д. Хаббарда про композицію многочленів із гомеоморфізмами площини ("twisted rabbit problem"), яку було важко розв’язати іншими методами. Про розв’язок цього питання можна прочитати в монографії11.
Навіть вивчення самоподібних дій вільних абелевих груп пов'язано із багатьма цікавими поняттями і конструкціями. Кожна така самоподібна дія будується за деякою <<системою числення>> на Zn. Якщо дія є стискуючою, то ця система числення поширюється і на векторний простір Rn. Із системами числення на дійсному векторному просторі пов'язані природньо самоподібні замощення простору так званими цифровими плитками. Такі плитки і відповідні системи числення вивчаються багатьма математиків як з теоретичної так і з прикладної точки зору. Вони знайшли своє застосування у комп'ютерній обробці зображень, теорії сплесків, теорії C*-алгебр, і.т.д.12.
Таким чином, вивчення самоподібних груп відкриває нові перспективи застосувань теорії груп до інших розділів математики, а також збагачує теорію груп новими техніками досліджень.
Зв'язок роботи з науковими програмами, планами, темами. Дослідження проводилися на кафедрі алгебри та математичної логіки Київського Національного Університету імені Тараса Шевченка, що ведуться за темою „Теорія алгебраїчних систем та їх зображень і її застосування” (номер державної реєстрації 0197U003160).
Мета і задачі дослідження. Метою дослідження є побудова загальної теорії самоподібних груп автоматів та їх застосування.
Об’єктом дослідження є (синхронні та асинхронні) автомати, ними породжені групи, самоподібні групи та інверсні напівгрупи, групи ітерованих монодромій, граничні простори стискуючих груп, операторні алгебри асоційовані із самоподібними групами.
Предметом дослідження є алгоритмічні проблеми груп породжених автоматами, властивості таких груп, алгебраїчні аспекти самоподібності, застосування самоподібних груп.
Методи дослідження. У роботі використовуються методи теорії автоматів, вінцевих добутків груп підстановок, геометричної та комбінаторної теорії груп.
Наукова новизна одержаних результатів. Результати роботи є новими і основні з них полягають в наступному.
Групи, породжені автоматами:
Побудовано алгоритми для розв'язання проблеми рівності в групах та напівгрупах (асинхронних) автоматних перетворень. (Підрозділ 2.3) Групи та напівгрупи асинхронних автоматних перетворень було означено в спільній роботі із Р. Григорчуком. Алгоритми було розроблено автором самостійно.
Доведено ізоморфізм груп асинхронно автоматних перетворень над різними алфавітами. Таким чином введено групу раціональних гомеоморфізмів множини Кантора (Теорема 2.33).
Розв'язано проблему Григорчука про класифікацію груп Gw з точністю до ізоморфізму (Теорема 2.65).
Самоподібні інверсні напівгрупи:
Введено поняття самоподібної інверсної напівгрупи, що узагальнює поняття самоподібної групи, та доведено еквівалентність двох природних означень самоподібності для інверсних напівгруп (Означення 3.9 та Твердження 3.10).
Знайдено явний вигляд автомата, що породжує напівгрупу суміжності плиток мозаїки Пенроуза (Твердження 3.13). Аналогічна напівгрупа розглядалася іншими авторами13, але без обчислення її дії на відповідному зсуві.
Алгебраїчні аспекти самоподібності:
Знайдено дві алгебраїчні моделі самоподібності груп: віртуальні ендоморфізми та підстановкові бімодулі, та досліджено зв'язки між ними (Розділ 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 сторінок.
ОСНОВНИЙ ЗМІСТ РОБОТИ
Перший розділ дисертації вводить необхідні означення і робить огляд відомих результатів, що використовуються далі в дисертації. Він включає в себе основні означення просторів слів та структур на них, необхідну термінологію з теорії графів, основні поняття теорії псевдогруп, етальних групоїдів та орбіпросторів. Результати цього розділу не є новими.
Другий розділ <<Групи та напівгрупи автоматних перетворень>> вивчає (асинхронні) автомати та (напів)групи автоматних перетворень. У першому підрозділі визначаються асинхронні автомати та їх дія на словах. Результати цього підрозділу є біль-менш класичними. Нагадаємо означення автомата (подібне означення можна знайти в14).
Асинхронним автоматом називається набір A=<XI, XO, Q, р , л> де:
1. XI, XO - скінченні множини (вхідний и вихідний алфавіти відповідно);
2. Q - множина внутрішніх станів автомата;
. р:QЧXI → Q - відображення (функція переходів);
. л: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,
a(v) інакше,
cw (1v)=1c у(w) (v), c w (0v)=0v, якщо w1=1
a(v), інакше,
d w (1v)=1d у(w) (v), d w (0v)=0v, якщо w1=0,
a(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→ ∞ n√limsup 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). Цей граф є комбінаторною моделлю граничного простору і може бути ефективно використаним для його вивчення. Цим самим показано зв’язок між гіперболічними групами та групами зі стискуючою самоподібністю у стилі словника Салівана15.
Наступний, п’ятий розділ <<Групи ітерованих монодромій>> присвячений новому природньому джерелу самоподібних груп. Ці групи асоційовані із самонакриттями орбіпросторів, зокрема із комплексними раціональними функціями. Початок розділу присвячено визначенню груп ітерованих монодромій, підготовці необхідної техніки для роботи з ними та доводиться формула для їх
обчислення. Теорія груп ітерованих монодромій стає симетричнішою у випадку, коли розглядаються не просто накриття просторів, а накриття орбіпросторів, тобто просторів із деякою додатковою груповою структурою. Відповідна техніка орбіпросторів розробляється на початку п’ятого розділу. Ми показуємо, зокрема, які орбіпростори канонічно асоційовані із пост-критично скінченними раціональними функціями.
У підрозділі <<Ітеровані монодромії>> визначаються групи ітерованих монодромій і доводяться їх основні властивості. Групою ітерованих монодромій накриття 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, асоційований із її самоподібною дією, то, перейшовши до лінійних оболонок над деяким полем, ми отримуємо бімодуль над груповою алгеброю. Такі бімодулі з’являються природньо при вивченні зображень самоподібних груп, обчисленні їх спектрів та вивченні випадкових блукань. При обчисленні спектрів природньо постає питання які поповнення групової алгебри (над полем комплексних чисел) узгоджені із відповідним бімодулем. Це є
центральним питанням цього розділу.
Розділ розпочинається із огляду понять пов’язаних із бімодулями над алгебрами та конструкцією лінійної оболонки підстановкового бімодуля. Крім того вивчаються ідеали, які інваріантні під дією бімодуля, доводиться що існує єдиний максимальний такий ідеал (він відіграє роль ядра стандартної самоподібної дії групи). Ці дослідження близькі за духом до досліджень С. Сідкі16.
Наступний підрозділ вивчає самоподібні унітарні зображення та самоподібні поповнення групової алгебри (тобто поповнення за нормою визначеною самоподібним зображенням). Зображення р називається самоподібним якщо р і Цoр унітарно еквівалентні, де Ц - лінійна оболонка бімодуля самоподібності. Це поняття мотивоване технікою операторних рекурсій, що були використані Р. Григорчуком, Л. Бартолді та А. Жуком для обчислення спектрів випадкових блукань на самоподібних групах та їх графах Шрайєра17. Ми показуємо, що існує мінімальна та максимальна самоподібні норми, і що зображення є самоподібним тоді і лише тоді, коли воно продовжується до зображення асоційованої алгебри Кунца-Пімзнера, тобто коли існує набір операторів Sx, x є X, для яких виконані наступні співвідношення:
Sx*Sx=1;
Уx є X SxSx*=1;
р(g)Sx=Sy р(h), якщо g.x=y.h.
Алгеброю Кунца-Пімзнера називається алгебра, породжена операторами р(G) таSx.
У підрозділі ми вивчаємо алгебри Кунца-Пімзнера та пов’язані з нею алгебри та напівгрупи. Зокрема, ми показуємо, що алгебра Кунца-Пімзнера, визначена за найменшим самоподібним поповненням групової алгебри є простою.
В останньому підрозділі ми узагальнюємо конструкцію К. Рьофера18 простої надгрупи групи Григорчука на випадок довільної самоподібної групи. Ми показуємо новий зв’язок між алгеброю Кунца та групою Хігмана-Томпсона (будуємо природє точне зображення групи Хігмана-Томпсона в унітарній групі алгебри Кунца) і вивчаємо групу Vd(G), породжену самоподібною групою G та групою Хігмана-Томпсона. Ця група має аналогічне природнє занурення в унітарну групу відповідної алгебри Кунца-Пімзнера. Зокрема, ми доводимо наступне твердження
Теорема Всі власні фактор-групи груп Vd(G) та Vd'(G) є абелевими.
Більше того, ми ефективно описуємо всі власні фактор-групи групи Vd(G). У багатьох випадках група Vd(G) є простою, і ми отримуємо нову цікаву серію простих нескінченних скінченно породжених груп.
ВИСНОВКИ
У дисертаційній роботі закладено основи нових напрямків та розв'язано ряд актуальних проблем геометричної теорії груп та теорії груп, породжених автоматами.
--- Побудовано алгоритми для обчислень із асинхронними автоматами та алгоритми для розв'язання проблеми рівності у групах та напівгрупах, породжених автоматами. Доведено, що група скінченних асинхронних автоматів не залежить від розміру алфавіту над яким визначаються автомати. Таким чином введено нову групу - групу раціональних гомеоморфізмів множини Кантора. Розв'язану проблему Р. Григорчука про класифікацію груп Gw.
--- Побудовано алгебраїчну теорію самоподібності груп. Визначається поняття самоподібної групи та самоподібної інверсної напівгрупи. Показано, що самоподібні інверсні напівгрупи з'являються природньо як напівгрупи пов'язані із мінімальними динамічними системами Вершика, та як напівгрупи суміжності плиток аперіодичних самоподібних мозаїк. Розроблено техніку для роботи із самоподібними групами: віртуальні ендоморфізми та підстановкові бімодулі. Показано зв'язок між підстановковими бімодулями та віртуальними ендоморфізмами груп. Описано повністю самоподібні транзитивні дії вільних абелевих груп. Показано зв'язок таких дій із системами числення.
--- Вивчено клас груп зі стискуючою самоподібністю. Доведено еквівалентність двох означень стискуючої самоподібності (скорочення довжини слів під дією віртуального ендоморфізму та означення на основі поняття нуклеуса дії). Доведено, що проблема рівності у стискуючих групах має поліноміальну складність та розроблено ефективний алгоритм для розв'язання проблеми слів у таких групах.
--- Описано стискуючі дії вільних абелевих груп та показано, що у цьому випадку відповідні системи числення поширюються на дійснівекторні простори та пов'язані із самоподібними <<цифровими>> мозаїками.
--- Введено поняття граничного простору самоподібної стискуючої групи. Ці простори мають фрактальну структуру і, для випадку груп ітерованих монодромій, гомеоморфні множинам Жюліа розширюючих відображень. Вивчено структуру граничних просторів та описано різні способи їх задання: як фактор-простори простору послідовностей, аксіоматичне, як границі послідовності скінченних графів та як границі гіперболічного за М. Громовим графу. Ці різні підходи дозволяють вивчати граничні простори (та відповідні множини Жюліа) із використанням різних технік, адекватних до відповідних питань.
--- Побудовано теорію груп ітерованих монодромій - природніх прикладів самоподібних груп. Групи ітерованих монодромій асоціюються із самонакриттями (орбі)просторів і містять інформацію про комбінаторику їх ітерацій. Знаходиться формула для обчислення природньої точної дії груп ітерованих монодромій на кореневому дереві слів. Цим самим зокрема розв'язано проблему Р. Пінка про обчислення груп Галуа ітерованих розширень поля функцій.
--- Показано, що група ітерованих монодромій містить всю <<суттєву>> інформацію про відповідне самонакриття, якщо воно є розширюючим. А саме, показано, як можна відновити множину Жюліа та дію самонакриття на ній за його групою ітерованих монодромій. Показано, що множина Жюліа є гомеоморфною граничному простору групи ітерованих монодромій. Цим самим відкрито нову можливість вивчення множин Жюліа за допомогою техніки самоподібних груп та груп, породжених скінченними автоматами, а також можливість застосування теорії груп до голоморфної динаміки.
--- Крім ітерацій раціональних функцій, групи ітерованих монодромій застосовуються до інших динамічних систем. Зокрема, показано, як розвинуту теорію можна застосувати до узагальнення теореми М. Шуба та М. Громова про розширюючі ендоморфізми многовидів на випадок орбі-многовидів. Зауважимо, що наше доведення є незалежним від результатів М. Шуба (використовує лише теорему М. Громова про групи поліноміального росту).
--- Вивчено алгебри, асоційовані із самоподібними групами. Введено поняття самоподібного унітарного зображення та показано, що існують найменша та найбільша C*-норми на груповій алгебрі самоподібної групи, які узгоджені із самоподібністю. Ці дослідження проливають світло на техніку операторних рекурсій, що використовувалися Р. Григорчуком, А. Жуком та Л. Бартолді.
--- Показано, що із самоподібними групами природньо асоціюються відповідні алгебри Кунца-Пімзнера, та показано, що алгебри Кунца-Пімзнера, побудовані за мінімальною самоподібною нормою є простими. Таким чином, самоподібні групи є також джерелом простих C*-алгебр. Знайдено природнє точне зображення простої групи Хігмана-Томпсона в унітарній групі алгебри Кунца та показано, що аналогічна група визначена за алгеброю Кунца-Пімзнера самоподібної групи, є також близькою до простої (і є простою для багатьох самоподібних груп). Таким чином, самоподібні групи є цікавим джерелом нескінченних скінченно-породжених простих груп.
Список опублікованих робіт за темою дисертації
. Nekrashevych V. Uniformly bounded spaces// Вопросы Алгебры. --- 1999. --- Т. 14. --- ст. 47--97.
. 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. (особистий внесок --- теорема про ізоморфізм групи біреверсивних автоматів та підгрупи співмірювача вільної групи.)
. Nekrashevych V. Stabilizers of transitive actions on locally finite graphs // Int. J. of Algebra and Computation. --- 2000. --- № 10. --- Vol. 5. --- p. 591--602.
. 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. (особистий внесок --- доведення основної теореми про класи спряженості автоморфізмів дерева у випадку, коли автоморфізм не фіксує вершину дерева.)
. Nekrashevych V. State-closed groups of automatic transformations// Вопросы алгебры. 2001. --- № . 17. --- С. 16--21.
9. Некрашевич В.В., Сущанський В.І. Автомати з обмеженою пам'яттю і ендоморфізми зсуву // Доп. НАН України. --- 2001. --- № 4. --- С. 18--21. (особистий внесок --- Теорема 3.)
. 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 у термінах гомеморфізмів границі дерева.)
. Nekrashevych V.V. Virtual endomorphisms of groups // Algebra and Discrete Mathematics. --- 2002. --- № 1. --- Vol. 1. --- p. 96--136.
. Nekrashevych V.V. Hyperbolic spaces from self-similar group actions // Algebra and Discrete Mathematics. --- 2003. --- № 1. --- Т. 2. --- С. 68--77.
. 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.
. 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.)
. 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).)
. 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.)
. 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. (особистий внесок --- застосування техніки бімодулів та тензорних степенів до зображень груп трикутними матрицями та інтерпретація їх у термінах підстановкових зображень.)
. 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.
2 Р. И. Григорчук. К пpоблеме Беpнсайда о пеpиодических гpуппах.// Функциональный анализ и пpиложения. --- 1980. --- 14. --- № 1. --- 53--54.
3 Р. И. Григорчук. Степени pоста конечно-поpожденных гpупп и теоpия инваpиантных сpедних. // Изв. АH СССР Сеp. матем. --- 1984. --- 48. --- № 5. --- 939--985.
4 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.
5 Narain D. Gupta and Said N. Sidki. On the Burnside problem for periodic groups. // Math. Z. --- 1983. --- 182. --- 385--388.
6 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.
7 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.
8 Benoit B. Mandelbrot. The fractal geometry of nature. Rev. ed. of "Fractals", 1977. / San Francisco: W. H. Freeman and Company. 1982.
9 Laurent Bartholdi, Rostislav I. Grigorchuk, and Zoran Sunik. Branch groups. / In Handbook of Algebra, Vol. 3. p. 989--1112. North-Holland. Amsterdam. 2003.
10 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.
11 Volodymyr Nekrashevych. Self-similar groups./ volume 117 of Mathematical Surveys and Monographs. Amer. Math. Soc., Providence, RI. 2005.
12 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.
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.
14 Samuel Eilenberg. Automata, Languages and Machines. volume A. / Academic Press, New York, London. --- 1974.
15 Dennis Sullivan Quasi-conformal homeomorphisms and dynamics I, solution of the Fatou-Julia problem on wandering domains. // Ann. Math. --- 1985. --- 122. --- 401--418.
16 Said N. Sidki. A primitive ring associated to a Burnside 3-group.// J. London Math. Soc. (2). --- 1997. --- 55. --- 55--64.
17 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.
18 Claas E. Rover. Constructing finitely presented simple groups that contain Grigorchuk groups. // J. Algebra. --- 1999. --- 220. --- 284--313.