Алгоритмические и метрические проблемы в теории бесконечных групп

Содержание
Введение ............................................................ 9
Глава 1. Проблема сопряженности для метабелевых групп . . 24
1.1. Тождества и многообразия....................................24
1.2. Редукция к задаче коммутативной алгебры ....................27
1.3. Конструктивная коммутативная алгебра........................30
1.4. Эффективная нормализация....................................32
1.5. Конструктивное вложение в проективное многообразие .... 34
1.6. Целозамкнутые негеровы кольца ..............................35
1.7. Дивизориальное отображение . . . .'.........................36
1.8. Соотношения в группе единиц (случай поля алгебраических
чисел).......................................................36
1.9. Соотношения в группе единиц (случай области над полем к) . 39
1.10. Соотношения в группе единиц (случай произвольной алгебры
над к).......................................................40
1.11. Соотношения в группе единиц (случай произвольного конечно порожденного кольца)...............................................41
Глава 2. Элементарные теории разрешимых групп и колец . . 43
2.1. Структуры, языки, теории....................................43
2.2. О доказательстве теоремы 3..................................47
2.3. Теорема конечности..........................................50
2.3.1. Теория абсолютных значений............................51
2.3.2. Нормализованные абсолютные значения глобальных полей .........................................................53
2.3.3. Кольца арифметического типа ..........................54
2
2.3.4. Погружение кольца алгебраических чисел в кольцо
арифметического типа....................................54
2.3.5. Теорема конечности для колец арифметического типа . 55
2.3.6. Ограниченность множества делителей.......................57
2.3.7. Теорема конечности 4 в случае нулевой характеристики 58
2.3.8. Теорема конечности 4 в случае ненулевой характеристики .........................................................62
2.4. Необратимые элементы вида (ап — £)пек..........................63
2.4.1. Лемма о компактных абелевых группах......................63
2.4.2. Доказательство теоремы 5 для колец арифметического
типа....................................................64
2.4.3. Аппроксимация элементов бесконечного порядка .... 65
2.4.4. Доказательство теоремы 5 в общем случае..................67
2.5. Формульность предиката, делимости..............................67
2.5.1. Редукция к проблеме обратимых элементов в последо-
дт 1
вательности вида дттгг...................................^
2.5.2. Доказательство леммы 10..................................68
2.6. Редукция доказательства теоремы 3 к случаю мегабелевой группы специального вида 72
2.6.1. Сведение к случаю метабелевой группы....................73
2.6.2. МА-свойство..............................................74
2.6.3. АРГ-свойство.............................................75
2.7. О делимости элементов модуля и элементов кольца ...............79
2.8. Доказательство теоремы 3.......................................80
2.8.1. Выбор специальной подгруппы Р в (? и элемента А 6 Р 81
2.8.2. Предикат т..............................................82
2.8.3. Формульность полугруппы ил>1 \пМ .......................82
3
2.8.4. Интерпретация арифметики - окончание доказательства теоремы 3 ................................................84
2.9. Элементарная теория конечно порожденною коммутативною
кольца ........................................................85
2.9.1. Конечность числа делителей..............................87
2.9.2. Необратимые элементы....................................88
2.9.3. А - целое замыкание кольца ^[£] в поле К - конечном сепарабельном расширении поля ^Р(Ь)............................89
2.9.4. А - целостная [/фалгебра, целая и сепарабельная над
•..................................................................................................................................................................91
2.9.5. А - целостная ^-алгебра степени транссндентности 1
над ¥р..................................................91
2.9.0. А - целостная Рр-алгебра размерности Крулля 1 . . . . 91
2.9.7. А состоит из алгебраических чисел.......................92
2.9.8. А - целостное кольцо характеристики нуль и размерности Крулля 1 92
2.9.9. А - произвольное бесконечное конечно порожденное коммутативное целостное кольцо.................................93
2.9.10. А - произвольное бесконечное конечно порожденное коммутативное кольцо...........................................93
Глава 3. Проблема рода для метабелевых групп......................94
3.1. Вложение Магнуса...............................................96
3.2. Нормализация генетического кода группы О.....................98
3.3. Описание группы 5 и критерий свободы группы С.................100
3.4. Вложение Магнуса свободной АяАр-группы........................102
3.5. Критерий свободы модуля Л£+т/Т ...............................103
3.6..........................................................Случай 1т ф Ад ................................................104
4
3.7. Случай 1т = \ч,1т+\ Ф 0......................................105
3.7.1. Хорошие простые р....................................106
3.8. Приведение Я к нормальной форме ..........................111
3.9. Завершение доказательства в случае простого или нулевого ^ .115
3.10. Редукция к случаю, когда д простое или равно нулю...........118
Глава 4. Инвариант Бири-Штребеля и гомологические условия конечности для метабелевых групп .................................121
4.Г Инвариант Бири-Штребеля ........................124
4.1.1. Инвариант Т,°м ......................................124
4.1.2. Нормирования.........................................125
4.1.3. Нормирования и характеры.............................126
4.1.4. Структура множества А (Кр, С}).......................126
4.1.5. Свойство 771-асимметричности.........................127
4.1.6. Конечное подмножество в контролирующее асимметричность ..................................................128
4.2. Доказательство теоремы 10....................................129
4.2.1. Редукции.............................................130
4.2.2. Критерий нетривиальности элемента из (ХТ*)Г„ в терминах порядковой функции......................................131
4.2.3. Фильтрации в N ......................................133
4.2.4. Оценка порядковой функции в терминах нормирований 134
4.2.5. Построение элемента а € Е®...........................136
4.2.6. Завершение доказательства теоремы 10: нетривиальность
образа а в (ЪГ^)г„....................................138
4.3. Доказательство теоремы 12....................................139
4.3.1. Построение ..........................................139
4.3.2. Построение Уа........................................140
4.4. Доказательство теоремы 14...................................141
4.4.1. Класс /С мульти-нормированных векторных пространств 141
4.4.2. Переформулировка теоремы 14...........................142
4.4.3. р-адические нормирования принадлежат /Со...........143
4.4.4. Случай полиномиального расширения.....................149
4.4.5. Случай поля рациональных функций......................153
4.4.6. Переход к конечному расширению........................153
4.4.7. Окончание доказательства теоремы 14...................155
Глава 5. Автоматные группы ..........................................157
5.1. Евклидовы комплексы Кокстера................................159
5.1.1. Корни и группа Вейля..................................159
5.1.2. Дуальные корни, решетки...............................160
5.1.3. Фундаментальная область и сферический комплекс Кокстера 161
5.1.4. Евклидовы отражения и аффинная группа Вейля ... 162
5.1.5. Евклидовы комплексы Кокстера..........................163
5.1.6. Инвариантность групп Вейля............................164
5.1.7. Стандартный альков....................................165
5.1.8. Специальные вершины...................................165
5.1.9. Подкомплексы..........................................167
5.2. Упорядочение евклидовых билдингов...........................167
5.3. Определение комбинга........................................175
5.3.1. Квазигеодезичность комбинга...........................178
5.3.2. Носитель пути.........................................178
5.3.3. Реберные пути.........................................179
5.3.4. Путь в выпуклой оболочке..............................179
5.3.5. Инвариантность комбинга...............................181
5.3.6. Единственность пути...................................181
5.4. Устойчивость комбинга.........................................181
5.5. Рекурсивность комбинга С.......................................185
5.5.1. Доказательство леммы 39................................187
5.6. Автоматные структуры на группах, действующих на евклидовых билдингах типа Л, В, С 192
5.7. Автоматные структуры на группах и группоидах..................193
5.7.1. Группоид 7Г1 196
5.7.2. Язык...................................................198
0 5.8. Завершение доказательства теоремы 22........................199
5.9. Геодезичность локальных геодезических..........................199
5.10. Групповые действия на неархимедовых деревьях, кубические
комплексы и автоматы..........................................204
5.10.1. I?-деревья ...........................................208
5.10.2. Распутывание Ъ2-деревьев в Ъ-деревья..................209
5.10.3. Приготовление конечных графов.........................214
5.10.4. Графы групп и графы пространств.......................216
5.10.5. Кубические комплексы..................................219
^ 5.10.6. Кривизна X............................................219
5.10.7. Завершение доказательства основной теоремы ...........221
5.11. Свойство ограниченного укорачивания и рациональность функции роста для групп, действующих па билдингах.......................222
5.11.1. Р’.РТ-свойство........................................223
5.11.2. Стенки в комплексах Кокстера..........................224
5.11.3. Укорачивание в группах Кокстера.......................225
5.11.4. Укорачивание в билдингах..............................227
5.12. Модулярная группа Гильберта...................................228
7
5.12.1. Конструкция Эпстина-Тёрстона циклов в произведении гиперболических плоскостей....................................229
5.12.2. Прямое произведение гиперболических плоскостей Нп . 229
5.12.3. Конструкция Эпстина-Терстона..........................230
5.12.4. Доказательство теоремы 29 ........................... 235
Литература............................................................238
1. Обозначения...................................................254
2. Тематический указатель........................................255
8
Введение
Актуальность работы. В 1912 году М.Дэн сформулировал три фундаментальные алгоритмические проблемы теории групп: проблема равенства, проблема сопряженности и проблема изоморфизма. Эти проблемы играют важную роль и в современной геометрической теории групп, являясь мерой сложности различных классов групп. Отметим, что проблема сопряженности содержит в себе проблему равенства, так как сопряженность единичному элементу равносильна его тривиальности. Проблемы сопряженности и изоморфизма, понимаемые в широком смысле, также связаны между собой. Например. сопряженность матриц над некоторым кольцом эквивалентна изо-морфности определенного типа модулей над кольцом многочленов. В свою очередь, проблема изоморфизма модулей ранга 1 над коммутативным целостным кольцом А может быть сведена к проблеме равенства в группе Пикара кольца А.
Мотивация к изучению проблем М.Дэна исходит из алгебраической топологии. Проблеме равенства для фундаментальной группы топологического пространства Т соответствует топологическая проблема: стягиваема ли данная замкнутая петля в Т? Сопряженность элементов в группе тгДТ) соответствует свободной гомотопности двух замкнутых петель. Наконец, решение проблемы изоморфизма для фундаментальных групп дает метод для различения пространств (проблема гомеоморфизма).
В работе М.Дэна первые две проблемы были решены для фундаментальных групп компактных поверхностей. Но только в 1968 году Ф.Вальдхаузен сумел доказать разрешимость проблемы равенства для групп узлов, и понадобилось еще 22 года, прежде чем З.Села (1993) доказал разрешимость проблемы сопряженности.
Принципиальное решение проблем Дэна было получено благодаря про-
никновению в теорию групп идей и методов математической логики. Одним из величайших достижений математики двадцатого века является установление точного смысла понятия «алгоритм». В 1936 г. были практически одновременно опубликованы работы А.Чёрча, С.К.Клини, А.М.Тьюринга и
Э.Л.Поста, в которых эта проблема была решена. Появление первых результатов о неразрешимости привело к идее о том, что фундаментальные проблемы М.Дэна рекурсивно неразрешимы. В частности, оказалось, что существует конечно заданная группа с неразрешимой проблемой равенства. Полное и детальное доказательство этой теоремы было опубликовано ак. П.С.Новиковым в 1955 году. Вскоре после этого ак. С.И.Адян доказал неразрешимость проблемы изоморфизма любой данной конечно определенной группе. Неразрешимость сопутствующей проблемы гомеоморфизма п-мерных топологических многообразий при п > 4 доказал А.А.Марков (1958).
В многообразии всех абелевых групп А все проблемы Дэна и многие другие имеют очевидное положительное решение. Поэтому естественным представляется вопрос об алгоритмических проблемах для разрешимых групп.
Проблема равенства для разрешимых групп. Проблема равенства решается положительно в классе полицкклических групп ввиду их матричной представимости. В силу теоремы Ф.Холла (1954) конечно порожденная ме-табелева группа финитно аппроксимируема, поэтому проблема равенства в многообразии А2 решается положительно. Прямой алгоритм для проблемы равенства в А2 указал Е.И.Тимошенко (1973). Проблема равенства в многообразии 2А2 центральио-метабелевых групп решена положительно Н.С.Романовским (1982). Результат затем был усилен О.Г.Харлампович (1987), доказавшей, что в многообразии А/г А, как и в любом его подмногообразии, проблема равенстза разрешима.
Н.С.Романовский доказал, что проблема вхождения решается положи-
тельно для конечно порожденных АЛЛ групп (1980). По-видимому, теорема Романовского справедлива и для конечно порожденных полициклических-над-абелевыми групп.
Проблема сопряженности. М.И.Каргаполов и В.Н.Ремесленников (1966) доказали разрешимость проблемы сопряженности в классе всех конечно порождённых свободных разрешимых групп. Проблема сопряженности в свободных поли-нильпотентных группах решена P.A.Саркисяном (1972). Из теоремы В.Н.Ремесленникова (1973) следует, что при п>Ъ существуют примеры конечно определенных в многообразии Лп групп, для которых она решается отрицательно. С другой стороны, P.A.Саркисян (1972) указал алгоритм решения проблемы сопряженности для свободных полинильпотентных групп, а Дж.Волер (1976) - для одного конкретного класса метабелевых групп.
Проблема изоморфизма. В.II.Ремесленников и А.С.Киркинский построили для каждого п > 7 такую конечно определенную в Лп группу G, что не существует алгоритма, выясняющего для любой конечно определенной в Лп группы, изоморфна она G или нет. Здесь интересной нерешенной задачей остается проблема изоморфизма для метабелевых групп. Напомним, что в классе всех групп отрицательно решается проблема изоморфизма единичной группе, в то время как в многообразии Лп эта проблема, имеет положительное решение. Проблема изоморфизма для нильпотентных групп решена положительно Ф.Грюневальдом и Д.Сегалом (1980). Отметим, что близкая к ней по постановке проблема эпиморфизма неразрешима уже в классе 2-нильпотент-пых групп. Неразрешимость проблемы эндоморфной сводимости в свободных нильпотентных группах большого ранга доказал В.А.Романьков (1997). Эта работа имеет важные следствия, в том числе её идеи привели к доказательству неразрешимости проблемы тождества в теории групп (Ю.Г.Клейман). Альтернативный подход к алгоритмическим проблемам для линейных алгеб-
раических групп был развит в 80-х годах прошлого столетия P.A.Саркисяном. Этот подход также даёт положительное решение проблемы изоморфизма для конечно порожденных нильпотентных групп но модулю выполнимости «принципа Хассе» для односвязных полупростых алгебраических групп, определенных над полем рациональных чисел. Выполнимость «принципа Хассе» долгое время оставалась доказанной для всех одиосвязных полупростых алгебраических групп, кроме группы Е8 (Г.Хардер). Случай Es был рассмотрен В.И.Черноусовым (1989) и, таким образом, решение Саркисяна стало безусловным. Проблема изоморфизма для полициклических групп была решена Д.Ссгалом (1990).Один из возможных подходов к проблеме изоморфизма ос-новап на понятии рода. Для произвольной группы G обозначим через TG множество конечных гомоморфных образов группы G, рассматриваемых с точностью до изоморфизма. Род Q{G) группы G - это множество всех групп //, таких, что TG = ТН (снова рассматриваемых с точностью до изоморфизма). Вопрос о мощности a(G) множества G{G) известен как проблема рода. Известно, что почти полициклические группы G, Н принадлежат одному роду в том и только том случае, когда их пополнения в проконечной топологии топологически изоморфны. Легко видеть, что a(G) = 1 в случае абелевой группы G. В то же время существуют достаточно простые примеры неизоморфных нильпотентных групп одного рода. Для класса нильпотентных групп функцию ol{G) исследовали Ф.Харари и П.Пикель, Г.Мислин, К.Лемер и другие (1970-е годы). Для этих групп Ф.Грюневальд и Р.Шарлау показали, что функция а(<3) не ограничена даже на классе нильпотентных групп класса 2 (1979). П. Пикель доказал, что род свободной группы в любом нильпотентном многообразии тривиален (1976). Глубокий результат Ф.Грюневальда и Д.Сегала утверждает конечность a(G) для произвольной полициклической группы G (1978). Из этого результата следует, что для фиксированной полициклической
группы (7 существует алгоритм, распознающий, изоморфна ли произвольная пол и циклическая группа группе (7.
Проблема рода усложняется при переходе к метабелевым группам. Основываясь на результатах X.Васса и П.Мурти о группе Пикара группового кольца абелевой группы, П.Пикель построил пример метабелевой группы бесконечного рода и доказал, что род произвольной группы не содержит собственного гомоморфного образа этой группы. Наконец, все еще неизвестно, тривиален ли род абсолютно свободной группы ранга п > 2. Аналогичный вопрос для группы также все еще открыт.
Предположим, что С есть класс групп, имеющий «локально-глобальное свойство для изоморфизма», т.е. для С и II в С имеет место изоморфизм (7 ~ Н тогда и только тогда, когда .Д((7) = Р(Н). Используя «челночный» алгоритм, легко убедиться, что проблема изоморфизма для конечно определенных групп из С имеет положительное решение. Хотя локально-глобальное свойство не имеет места для полициклических групп, его более слабый вариант все же справедлив: для данного множества X конечных групп существует лишь конечное множество изоморфных классов почти полициклических групп, таких, что У7(С) = X (Грюневальд - Пикель - Сегал (1980)).
Порождающий ранг. Понятие размерности в линейной алгебре имеет естественный аналог в теории групп. Порождающим рангом д(С) группы С называется минимальная мощность ее порождающего множества. П.Линнел и Дж.Вархюрст доказали, что для полициклической группы (7 выполняется неравенство д(0) < с1(6) +1 (1981). Здесь д(6) обозначает минимальное число топологических порождающих прокоиечного пополнения группы (7, так что теорема утверждает, что если все конечные факторы группы (7 порождаются (I элементами, то сама группа (7 порождается (1+\ элементами. Для абелевой группы <7 имеет место равенство <Д(7) = (1(6).
Элементарные теории. Алгоритмические проблемы в многообразиях структур глубоко связаны с фрагментами элементарных теорий этих многообразий. Так проблема равенства в многообразии эквивалентна проблеме разрешимости его универсальной теории (Дж.Мак-Кинси ). Пусть /С - класс алгебраических структур определенной сигнатуры Е. Сигнатуре Е известным образом сопоставляется язык первого порядка С%. Множество Т всех предложений сигнатуры Е, справедливых в некотором классе структур сигнатуры Е, называется элементарной теорией данного класса. Теория называется разрешимой, если существует алгоритм, позволяющий по любому предложению определить, принадлежит ли оно теории или нет. Первым фундаментальным результатом явилась теорема Геделя - Россера (1936) о неразрешимости арифметики. С другой стороны, А.Тарсхий доказал разрешимость теории ноля комплексных чисел (1948). Он же придумал методы определимости и интерпретируемости для доказательства неразрешимости теорий. В самой общей форме основной метод доказательства неразрешимости - метод относительной элементарной определимости - был изобретен и сформулирован ак. Ю.Л. Ершовым. Пусть 5 - структура сигнатуры а. Пусть сг$ ” сигнатура, получаемая из (7 добавлением констант, по одной для каждого элемента из 5. Подмножество Ь С 5л,п > 1, (относительно) определимо, если существует формула Ф(х),х = зп) сигнатуры <75, такая, что Ь = {э € Бп : Б \= Ф(б*)}.
Аналогично вводятся определимые предикаты, конгруэнции, факторструктуры. Назовем структуру Бо предикатной сигнатуры (Р™1) определимой (с параметрами) в £, если имеются определимое в 5 подмножество определимая конгруэнция К на определимые предикаты на 5Ь согласованные с конгруэнцией К и такие, что факторструктура Ь\/К изоморфна 5о- Оказывается, что если в структуре 5 определима структура Бо с наследственно неразрешимой элеменатарной теорией, то элементарная теория £ также на-
следственно неразрешима. В качестве £о часто используется стандартная модель арифметики, а также группа Новикова. Метод определимости широко применялся в работах Р.Робинсона и Дж.Робинсон, где, в частности, доказано, что если Я - кольцо полиномов на полем нулевой характеристики или р-адических чисел, то существует р € Я, такой, что рт определимо в Я. При отождествлении р® ~ N умножение в N определимо в Я, и, следовательно, Я. неразрешимо. До сих пор неизвестен ответ на вопрос: разрешима ли дио-фантова проблема над бесконечным конечно порожденным коммутативным кольцом? Разрешима ли диофантова проблема на полем рациональных чисел? В случае кольца Ъ диофантова проблема, известная как 10-я проблема Гильберта, неразрешима (ак. Ю.В.Матиясевич (1970)).
В области теории групп исходным был вопрос А.Тарского (1945) : разрешима ли элементарная теория свободной неабелевой группы? Положительный ответ дан А.Г.Мясниковым и О.Г.Харламиович.
Широкое внимание привлек класс разрешимых групп. А.И.Мальцев доказал неразрешимость элементарной теории конечно порожденной свободной разрешимой неабелевой группы (1960). В статье чл. корр., АН СССР М.И.Каргаполова и его учеников была выдвинута гипотеза: элементарная теория конечно порожденной нильпотентной группы разрешима тогда и только тогда, когда группа почти абелева (1969).Гипотеза была доказана Ю.Л.Ершовым (1972). М.И.Каргаполов в докладе на международной конференции по теории групп (Канберра, 1973 г.) обобщил гипотезу на конечно порожденные почти разрешимые группы. Н.С.Романовский доказал гипотезу для почти полициклических групп (1980).
Условия конечности для метпабелевых групп. Свойства конечной порож-денности и конечной определенности являются фундаментальными свойствами в теории бесконечных групп. Для группы (7 в многообразии групп V
свойство конечной определенности приобретает новый смысл - мы называем (7 конечно определенной в V, если (7 имеет код, являющийся объединением конечного числа соотношений и всех тождеств V. Естественный вопрос, когда эта «относительная» конечная определенность влечет «абсолютную», привлек широкое внимание. Уже в случае многообразия метабелевых групп вопрос оказался в высшей степени нетривиальным и привел к открытию замечательного «инварианта Бири-Штрсбеля», позволяющего эффективно решить алгоритмическую проблему распознаваемости конечной определенности. Пусть ф - конечно порожденная абелева группа, и <3* = Нот((5, К) \ {0} - множество ненулевых характеров из С? в аддитивную группу 1Е. Инвариант Бири-Штребеля Т.см конечно порожденного Еф-модуля М состоит из всех характеров х € <?*» Для которых М не является конечно порожденным над полугрупповым кольцом ГЩХ полугруппы С}х = {д 6 <2*. х(<?) ^ 0}- Назовем инвариант т-асимметричным, если любое т-точечное подмножество в Т,см содержится в открытом полупространстве пространства <5*. Произвольная конечно порожденная метабелева группа Г является расширением вида М >—► Г -» <3 с абелевыми группами М, (2, причем М обладает естественной структурой конечно порожденного 2 <2-модул я. Теорема Бири-Штребеля утверждает, что конечно порожденная метабелева группа Г конечно определена тогда и только тогда, когда £^ является 2-асимметричиым, т.е. не содержит пары диаметрально противоположных точек. Из конструктивного описания Е^ следует алгоритмическая разрешимость проблемы распознаваемости конечной определенности в многообразии метабелевых групп. Свойства конечной порождеиности и конечной определенности являются лишь первыми двумя в бесконечной цепочке «гомологически-топологических» свойств конечности. По определению группа Г имеет тип РРП} если тривиальный
Е Г-модуль Ъ обладает проективной резольвентой
V : • • • Рп —► • • • —* Р\ —> Ро -» й,
в которой 2Т-модули Рп, ■.., Ри Л) конечно порождены. Хорошо известно,что класс РР\-групп совпадает с классом всех конечно порожденных групп, и что конечная определенность влечет РР^.
Р.Бири (1981) высказал гипотезу, описывающую структуру метабелевых .РРп-групп в терминах инварианта Т,см. Произвольная конечно порожденная метабелева группа Г является расширением вида М >—* Г -» <2 с абелевыми группами М,<2, причем М обладает естественной структурой йф-модуля.
Гипотеза (Р.Бири ). Конечно порожденная метабелева группа Г принадлежит классу РРт при т > 2 в том и только том случае, когда инвариант Ед,; является т-асимметричным.
Р.Бири и Р.Штребель доказали сформулированную гипотезу при т = 2. Гипотеза была доказана также для метабелевых групп конечного ранга (X. Оберг (1986)). Бири и Гровз доказали, что «РРт над О» влечет ш-асим-метричность инварианта модуля Техника доказательства включает
гомологическую алгебру.
Автоматные группы. Существование алгоритма, решающего проблему равенства в данной группе б?, еще не означает возможность проводить реально эффективные вычисления. Нужды теории 3-мерных многообразий привели Кеннона, Терстона и Эпстина к созданию теории автоматных групп. В процессе исследования авторы пришли к замечательному определению ав-томатности, представляющему собой сплав свойства «рекурсивности» нормальных форм и чисто геометрического свойства «устойчивости». Пусть А* - свободный моноид над конечным алфавитом А. Мы предполагаем, что А содержит «формально обратные» элементы, т.е состоит из пар символов а, а-1.
Будем говорить, что группа G порождается множеством Л, если задано отображение а а е G,a € А, индуцирующее эпиморфизм : А* —> G. Граф Кэли С = Ca(G) состоит из множества вершин VC — G и ребер (= дуг ) из 9 в да (д е G) а 6 Л). Всякое ребро д да имеет метку а. Каждое слово w = охагаз ... Е Л* имеет значение й> 6 G. Кроме того, w определяет путь из д € G в gw:
д^+дщЛ* даi02 gaia2a3 ...
Подмножество L С Л' называется нормальной формой в G, если L = G. Нормальная форма L определяет комбинг (= причёсывание) графа Кэли, а именно, для любой пары g,h € G и любого слова w 6 L, такого, что и» = g~lh, однозначно определён путь из г/ в /i с меткой гу. Подмножество L С А" называется регулярным (рациональным) языком, если L распознается конечным автоматом над Л или. эквивалентно, L получается из конечного множества применением конечного числа операций объединения, произведения и порождения.
Нормальная форма L устойчива (fellow traveller property), если существует константа k = k(L)} такая, что любые пути с метками v,w € L, общим началом и с концами на расстоянии < 1 являются /г-близкими в том смысле, что выполняется неравенство d(v(t),w(t)) < k,\ft = 0,1,... Если, более того, неравенство выполняется для путей, начала и, соответственно, концы которых находятся на расстоянии < 1. то L называется биустойчивой. (Би)автоматная структура на группе G - это (би)устойчивая регулярная нормальная форма на G. В то время как автоматность дает эффективное решение проблемы равенства, биавтоматность дает эффективное решение проблемы сопряженности. Примерами автоматных групп являются гиперболические группы (М. Л. Громов (1987)). Примером неавтоматных групп являются все группы SLM(Z)(n > 3). В задаче классификации автоматных ариф-
метических групп получены значительные продвижения, но окончательное решение до сих пор не получено. В качестве подзадачи здесь содержится проблема автоматности групп, действующих на билдингах. В самом деле, например, всякая дискретная подгруппа группы SLn(Qp) действует собственно на ассоциированном билдинге Брюа - Титса. Более общо, пусть Д - кусочно евклидов стягиваемый комплекс неположительной кривизны (=САТ(0) комплекс). Пусть G : А - собственное кокомпактное изометрическое действие. Верно ли, что G биавтоматна? Ответ неизвестен даже в случае евклидовых билдингов. В двумерном случае проблема детально рассмотрена С.Герстеном и X.Шортом, доказавшими биавтоматность фундаментальной группы конечного кусочно евклидова 2-комплекса неположительной кривизны, имеющего тип А\ х Ль А2 , В2 или б?2. В качестве следствия они получили биавтоматность группы без кручения, действующей собственно и кокомпактно на евклидовом билдинге типа /Ь. Близкие результаты были получены В.Бальманом и М.Брином, Д.Картрайтом и М.Шапиро, Я.Святковским. Важным общим результатом является теорема Г.Нибло и Л.Ривза о биавтоматиости кубических групп.
Связный граф С обладает свойством ограниченного укорачивания 1 если существует к > 0, такое, что для любого негеодезического пути v(t) в С существует к-близкий путь w(t) с теми же концами, что и v(t), но короче, нежели v(t). Важность свойства ограниченного укорачивания для изучения функций роста объясняется теоремой Дж.Кеннона: если группа G порождается конечным множеством А, и Ca(G) обладает FFT- свойством, то язык геодезических в этом графе регулярен. Кроме того, функция роста J2\Bn\tn группы G относительно А рациональна.
Свободные, подгруппы. Нахождение свободных неабелевых подгрупп иг-
1 В англоязычной литературе «falsification by fellow traveller property» или «FFT-property» .
рает важную роль в изучении парадокса Банаха - Тарского, функций роста и алгебраической энтропии.
Автоморфизмы. Изучение групп автоморфизмов алгебраических структур важно с алгоритмической точки зрения. Например, пусть С и Ы — конечно порожденные нильпотентные группы. Изоморфизм мальцевских пополнений 0е2 и имеет место в том и только том случае, когда изоморфны соответствующие О-алгебры Ли 0, ф Решая вопрос об изоморфизме 0, ф мы можем считать, что эти алгебры изоморфны над полем комплексных чисел, так как элементарная теория этого поля разрешима. В этом случае можно применить теорию иеабслевых когомологий, из которой следует, что алгебра изоморфна алгебре 0 тогда и только тогда, когда построенный по I) коцикл из множества Н1(Са1(^/0)) АиЬд) тривиален. Р.А.Саркисян доказал, что тривиальность коцикла можно алгоритмически распознать при условии выполнимости «принципа Хассе» для односвязных полупростых алгебраических групп, определенных над (12. Таким образом, группа автоморфизмов АиЬ(д) появляется в проблеме изоморфизма.
Научная новизна. Все результаты, представленные в диссертации, являются новыми на момент их публикации.
Объект исследования. Объектами исследования являются разрешимые группы, коммутативные кольца, группы Ли, кусочно евклидовы комплексы (включая евклидовы билдинги), группы когомологий .
Методы исследования. В работе используются методы геометрической и комбинаторной теории групп (включая вложение Магнуса и кусочно евклидову геометрию), коммутативной алгебры, алгебраической геометрии (включая примарное разложение и группы классов дивизоров) и гомологической алгебры (включая спектральную последовательность Хохшильда -
Цель и задачи диссертации. Изучение алгоритмических свойств разрешимых групп и групп, действующих на комплексах неположительной кривизны. Решение ряда проблем теории групп: проблемы Каргаполова о разрешимости элементарной теории разрешимой группы, проблемы сопряженности в метабелевых группах, проблемы рода для свободных мстабелевых групп. Построение биавтоматных структур на группах автоморфизмов евклидовых билдингов. Доказательство несуществования автоматных структур на модулярных группах Гильберта.
Достоверность научных положений. Достоверность научных положений и полученных результатов обеспечиваются их согласованностью с общепризнанными представлениями. Результаты опубликованы в российских и зарубежных журналах, неоднократно док лады вались на семинарах и конференциях. Они известны в научном сообществе и цитируются в работах других авторов. Показатель цитируемости по поисковой системе Google Scholars равен 236 (на ноябрь 2010 г.). Результаты по теме диссертации опубликованы в 1977-2009 годах. Достоверность научных положений и полученных результатов обеспечиваются также положительными рецензиями в реферативных журналах «Математика», Math, reviews, и Zentralblatt fuer Mathematics.
Практическая ценность и область применения результатов. Предлагаемая работа носит теоретический характер. Полученные результаты и методы могут найти применение в дальнейших исследованиях по теории групп. Многие доказанные в диссертации теоремы могут быть включены в спецкурсы для студентов и аспирантов.
Научные положения, выносимые на защиту. На защиту выносятся следующие положения и результаты.
1. Решение проблемы сопряженности для конечно порожденных метабелевых групп.
2. Характеризация конечно порожденных разрешимых групп с разрешимой элементарной теорией.
3. Решение проблемы рода для свободной метабелеиой группы конечного ранга.
4. Доказательство гипотезы Вири для расщепляемых конечно порожденных метабелевых групп без кручения.
5. Построение биавтоматных структур на группах автоморфизмов евклидовых билдингов. Доказательство неавтоматпости модулярной группы Гильберта.
Публикации. Материалы диссертации опубликованы в 39 печатных работах, из них 37 статей - в рецензируемых журналах, в т.ч. 29 статей - в журналах и изданиях из перечня ВАК. Без соавторов выполнены 27 опубликованных научных работ по теме диссертации, 12 работ написаны совместно. Из 29 работ в журналах из перечня ВАК 9 выполнены в соавторстве.
Апробация и внедрение результатов. Результаты, полученные в диссертации, докладывались на российских и международных конференциях: в Марселе-Люмини (Франция, 2004), Омске (2008, 2010). Новосибирске (2000, 2003, 2005). Эрлаголе (2000), Франкфурте-на-Майне (Германия, 1999), Билефельде (Германия, 2003), Гомеле (1986), Санкт-Петербурге (1982), Кемерове (1987), Кортрайке (Бельгия, 1999), Гаете (Италия, 2003), Варшаве (Польша, 2003), Гданьске (Польша, 2004), Обервольфахе (Германия, 2002, 2008), Красноярске (1993, 2002), Барнауле (1991).
Результаты обсуждались на специализированных семинарах: в Омском государственном университете (1975-2010), Новосибирском государственном университете (1981. 1983, 1987,1994, 2008), в университете Манитобы (Канада, 1991, 1994), университете Кембриджа (Великобритания, 1995), Лондонском университете (Великобритания, 1995), университете Манчестера (Вели-
кобритания, 1995), университете Бильги (Турция, 2002, 2005), университете Билефельда (Германия, 1998-2008), университете Франкфурта-на-Майне (Германия, 1995, 1996), университете Дюссельдорфа (Германия, 1999), университете Бонна (Германия, 2003).
Структура и объем диссертации Диссертационная работа состоит из введения, пяти глав, списка цитируемой литературы, списка обозначений и списка терминов (предметного указателя). Диссертация содержит 6 рисунков. Список литературы состоит из 155 наименований. Полный объем диссертации составляет 257 страниц машинописного текста.
Каждая глава имеет номер и состоит из разделов и подразделов, нумерация которых подчинена нумерации глав. Нумерация теорем, лемм и рисунков в тексте диссертации сквозная. Номера формул подчиняются главам.