Содержание к диссертации
Введение
ГЛАВА 1. Группа неподвижных точек автоморфизма свободной группы
1. Относительный трейн-трек для автоморфизма свободной группы конечного ранга 6
2. Конструкция графов Df и С/ для гомотопической эквивалентности 12
3. Определение и свойства отображения 16
4. Запрещенные развороты в экспоненциальном слое 19
5. Свойства некоторых путей в графе Г 37
6. Алгоритм построения графа С 46
7. Основные результаты 65
ГЛАВА 2. Алгоритмическая проверка квазиизометрично-сти некоторых расширений абелевых групп посредством циклической
1. Предварительные сведения 67
2. Доказательство теоремы 2.5 70
Литература 73
- Конструкция графов Df и С/ для гомотопической эквивалентности
- Запрещенные развороты в экспоненциальном слое
- Алгоритм построения графа С
- Доказательство теоремы 2.5
Введение к работе
Для автоморфизма а свободной группы F конечного ранга группа неподвижных точек Fix(a) состоит из всех слов w F таких, что a(w) = w. Для множества автоморфизмов S группа неподвижных точек Fix(S') определяется как пересечение всех групп Fix(a) для автоморфизмов а, входящих в S. В 1975 году Дайер и Скотт [10] показали, что для автоморфизма конечного порядка группа неподвижных точек — свободный множитель в F. В частности, для таких автоморфизмов верна гипотеза Скотта о том, что ранг группы Fix(a) не превосходит ранга F. Позднее Герстеном [15], Голдстейном и Тернером [16, 17], Купером [8] было доказано, что группа Fix(tt) конечно порождена для любого автоморфизма а свободной группы F. Томас [27] обобщил этот результат для произвольного множества автоморфизмов S. В 1992 году Бествина и Хендел [4] ввели понятие относительного трейн-трека, при помощи которого доказали гипотезу Скотта для произвольного автоморфизма а группы F. Другие доказательства [13, 14, 21, 25] получены с помощью действий групп на деревьях. Имрихом и Тернером [18] было показано, что гипотеза Скотта выполняется и для произвольного эндоморфизма группы F. Дике и Вентура [9] на основе работы [4] доказали, что ранг группы Fix (5) не превосходит ранга F для множества S инъективных эндоморфизмов группы F. Бергман [2] показал, что такое же неравенство выполняется для произвольного множества S эндоморфизмов группы F.
С использованием техники трейн-треков Коллинз и Тернер полностью описали автоморфизмы, у которых группа неподвижных имеет максимальный возможный ранг. В частности, все они полиномиального роста. В работе Коэна и Люстига [7] приводится алгоритм вычисления базиса Fix(a) для положительных автомофизмов а группы .FY то есть таких, что для некоторого базиса Хи...,хп группы F приведенные слова cx(xi),...,а(хп) состоят только из положительных степеней xi,...,хп.
Пусть Г — конечный связный граф. Трейн-треком называется такая гомотопическая эквивалентность / : Г —> Г, что любая степень /локально инъективна на внутренности любого ребра графа Г. Используя работу [7], Тернер [28] указал алгоритм, позволяющий вычислять базис группы гомотопических классов петель в графе Г, неподвижных относительно трейн-трека /. При этом предполагается, что базисная вершина v неподвижна относительно /. Таким образом, работа Тернера позволяет вычислять базис Fix(a) для автоморфизма а, который можно топологически представить трейн-треком. Не для любого автоморфизма группы F можно построить трейн-трек, однако Бествиной и Хенделом [4] было показано, что для неприводимых автоморфизмов можно. Приводимым называется такой автоморфизм а, что существует неединичный свободный множитель группы F вида G\ * * Gk и а транзитивно переставляет классы сопряженности подгрупп Gi,...,Gfc. При этом если G\ *' -*Gk = F, то к должно быть не меньше 2. Иначе автоморфизм а называется неприводимым. В той же работе [4] введено понятие относительного трейн-трека. Это понятие более сложное, оно формулируется в 1 главы 1 диссертации. На основе техники относительных трейн-треков и с использованием техники работ [6, 7, 28] в
данной диссертации строится алгоритм нахождения базиса для произвольного автоморфизма а свободной группы F. Однако, в отличие от работ [7, 28], оценка на число шагов алгоритма не получена. Итак, в главе 1 диссертации получена следующая основная теорема 7.1, отвечающая на вопрос (F1) (а) из [1].
ТЕОРЕМА 7.1. Пусть F — свободная группа конечного ранга, а — ее автоморфизм, заданный образом некоторого фиксированного базиса. Тогда алгоритмически вычислим базис подгруппы Fix(a).
Для элемента и Є F множество {ак(и) : к Є Z} называется а-орбитой, а множество {w~1ua(w) :w Є F} — а-классом Райдемайстера элемента и. В 1 используется также понятие а+-орбиты, которая совпадает с множеством {ак(и) : к Є N}. Бринк-манн в препринте [6} показал, что проблема вхождения в а-орбиту алгоритмически разрешима. В главе 1 также доказана теорема 7.2, которая показывает, что проблема вхождения в а-класс Райдемайстера тоже алгоритмически разрешима. Пункт (2) этой теоремы отвечает на вопрос 3 (і) из [9].
ТЕОРЕМА 7.2. Пусть F — свободная группа конечного ранга, а — ее автоморфизм, заданный образом некоторого фиксированного базиса. Тогда выполняются следующие утверждения.
Для любого слова w F его а-класс Райдемайстера состоит из а-орбит.
Пусть и, v — слова в группе F. Тогда можно алгоритмически определить, принадлежит ли слово v а-классу Райдемайстера слова и.
На основе теоремы 7.2 получена теорема
ТЕОРЕМА 7.3. Пусть F — свободная группа конечного ранга. Тогда в любом расширении группы F посредством циклической группы разрешима проблема сопряженности.
Структура главы 1 такова. В 1 приводятся необходимые сведения из теории относительных трейн-треков Бествины, Фейна и Хенделя [3,4], а также две теоремы Бринкманна из [б] о проблеме вхождения в а-орбиту. В том же параграфе строится "хорошее" геометрическое представление некоторой фиксированной степени автоморфизма а и выводится следствие из теоремы Бринкманна для случая гомотопической эквивалентности конечного связного графа. В 2 описывается подход Коэна— Люстига и Тернера к вычислению базиса Fix (а) из [7, 28] при помощи конструкции графа С/. В 3 вводится определение отображения / и выводятся некоторые его свойства. Это отображение тесно связано с определением движения по предпочтительным направлениям из 2. Параграф 4 является ключевым в главе 1. В нем выводятся некоторые свойства произвольного относительного трейн-трека, которые используются в параграфах 5,6. Предложения параграфа 5 имеют технический характер и содержат свойства, необходимые в 6. В самом же параграфе б доказывается алгоритмичность построения графа С/ (в 2 была предложена лишь процедура). Наконец, в 7 формулируются основные теоремы и приводятся их доказательства на основе предыдущих параграфов.
Результаты главы 1 докладывались на семинарах "Алгебра и Логика" Новосибирского государственного университета, "Теория групп" и "Геометрическая теория групп" Института математики СО РАН, а также на конференциях в Новосибирске в 1999 г. и в Сумах в 2001 г. [32, 34]. Эти результаты опубликованы в [36]. Имеется препринт Люстига [19], в котором утверждается, что проблема алгоритмической
сопряженности в группах Aut(Fn) и Out(Fn) алгоритмически разрешима. Там же сформулировано замечание 9.3 о том, что из соответствующего алгоритма можно вывести алгоритм нахождения базиса группы Fix(a).
Вторая глава диссертации посвящена проверке квазиизометричности некоторых HNN-расширений абелевых групп. Пусть (X,d\) и (У, dy) — метрические пространства. Отображение / : X —> Y называется квазиизометприей, если существуют константы К, С\, С2 такие, что
—dx(xi,х2)-С2 ^dY(/(^1),/(^2)) < Cidx(xi,x2) + C2 для всех хих2 Є X;
if-окрестность f(X) совпадает с Y.
Пространства X и Y назывются квазиизометричными, если существует ква-зиизометрия f : X - У. Пусть G,H — конечно порожденные группы, da,du — словарные метрики на G,H. Группы G и Н называются квазиизометричными, если метрические пространства (G, da) и (Н, dg) квазиизометричны. Это определение корректно, поскольку словарные метрики, определенные различными конечными порождающими множествами, задают квазиизометричные пространства.
Пусть М.— целочисленная матрица порядка п с определителем, отличным от О, ±1, и пусть через Тм обозначено HNN-расширение группы Zn при помощи мономорфизма срм с матрицей М. Фарб и Мошер [11] привели следующий критерий квазиизометричности групп вида Гд/.
ТЕОРЕМА [11]. Пусть МиМ2 Є M„(Z), detMbdetM2 ф 0,±1. Тогда группы Гм1 и Гм2 квазиизометричны в том и только том случае, когда найдутся натуральные Гі,г2 такие, что матрицы М[1 и М? имеют одинаковые абсолютные жордановы формы.
Абсолютная жорданова форма матрицы М получается из жордановой формы заменой диагональных элементов на их модули. Условие det М = ±1 эквивалентно полицикличности группы Гм (доказательство можно найти в [12]) и на данный момент критерий квазиизометричности таких групп Гм неизвестен. На основе теоремы Дирихле [29, т. 5, стр. 131] о строении группы единиц модуля алгебраических целых поля F в главе 2 получена следующая
ТЕОРЕМА 2.5. Пусть А, В Є M„(Z). Тогда можно алгоритмически проверить, существуют ли натуральные k, т такие, что абсолютные жордановы формы матриц Ак и В1 совпадают. В частности, существует алгоритм проверки квазиизометричности групп Гд^ и Гм2 при det М\, det М2 ф О, ±1.
Результаты главы 2 докладывались на семинарах "Алгебра и Логика" Новосибирского государственного университета, "Теория групп" и "Геометрическая теория групп" Института математики СО РАН, а также на конференции в Красноярске в 2002 г. [35]. Эти результаты опубликованы в [37].
Автор благодарит своего научного руководителя д.ф.-м.н. Олега Владимировича Богопольского за внимание и помощь, оказанные в работе.
Конструкция графов Df и С/ для гомотопической эквивалентности
В этом параграфе приводятся необходимые сведения из работ [7] и [28]. Пусть Г — конечный граф, / : Г — Г — гомотопическая эквивалентность, отображающая вершины графа Г в вершины, /г\г локально инъективно, v» — вершина графа Г, неподвижная относительно /. Положим Fix(/) = { [\р]] Є 7Гі(Г,і7„) /(р) = р }. В работах [7], [28] предложена процедура вычисления базиса Fix(/) при помощи построения некоторых графов Df и С/. Эта процедура обладает одним существенным недостатком: в ней не указано, когда нужно остановиться, то есть на каждом шаге нет уверенности, что построен весь базис Fix(/). Дадим краткое описание этой процедуры. Путь fj, в графе Г называется /-путем, если конечная вершина пути /л совпадает с начальной вершиной пути /(д). Отметим следующие свойства /-путей: тождественный путь в вершине v, обозначаемый 1„, является /-путем тогда и только тогда, когда вершина v фиксируется отображением /; если р. — /-путь, то [р] тоже /-путь; если р — /-путь и Е — ребро в Г с начальной вершиной а(р), то Epf(E) — /-путь. Граф Df определяется следующим образом. Вершинами графа Df являются приведенные /-пути в графе Г. Пусть р — приведенный /-путь в графе Г. Обозначим через Е\,...,Еп все ребра в графе Г с начальной вершиной а(р). Тогда в графе Df вершина р, соединяется с вершинами [Eipf(Ei)],...,[Enpf(En)] ребрами с метками Ei,...,En соответственно. Метка пути в графе Df — соединяются в графе Df путем с меткой р тогда и только тогда, когда ppif(p) — путь в графе Г, гомотопный пути рг- В частности, при цг = р2 = 1«. получим, что петле с меткой р в графе Df с началом в вершине 1„, соответствует петля р в графе Г с началом в вершине и такая, что /(р) = р, и наоборот. Поэтому фундаментальную группу компоненты графа Df, содержащую вершину lVt, можно отождествить cFS(/). В общем случае граф Df может иметь бесконечное число компонент связности и некоторые из них могут быть бесконечны. Обозначим компоненту связности графа Df, содержащую вершину lv,, через )/(1ю,). Пусть С/ — некоторый конечный связный подграф графа Df(lVm), содержащий вершину 1„. и такой, что фундаментальная группа С/ совпадает с фундаментальной группой графа )/(1,,.). Заметим, что граф С/ определяется неоднозначно. Если удастся алгоритмически построить С/, то задача о нахождении Fix(/) также будет алгоритмически разрешима. Пусть р, — приведенный /-путь в графе Г и Е — его первое ребро. Тогда /х и [Ep,f(p)\ — вершины графа Df, соединенные ребром с меткой Е. Выделенным направлением в вершине [м графа Df называется направление этого ребра. На этом ребре вблизи вершины ц ставится треугольник вида D .
Заметим, что нет выделенного направления только в вершинах 1„, где v Є Г — неподвижная относительно / вершина. Такие вершины назовем тупиками. является первым ребром пути v в графе Г). Вершины отталкивающих ребер будем называть о-вершинами. однозначном соответствии с вхождениями ребер Е графа Г в путь j(E). Другими словами, существует биекция вида Пусть и — вершина в Dj и \i = ЕіЕ2...Ет в графе Г для некоторых ребер ЕиЕ2,...,Ет. Движением в D/ назовем переход по выделенному направлению от вершины и к вершине [Е2... Emf(Ei)]. Назовем ц-множеством линейно упорядоченное множество вершин графа /, получающихся при движении по выделенным направлениям из вершины д. Заметим, что /it-множество конечно тогда и только тогда, когда при движении из вершины / можно попасть в тупик или происходит зацикливание. Таким образом //-множество имеет один из трех видов, изобралсенных на рис. 1. Если //-множество и т-множество пересекаются, то по определению движения, они могут отличаться лишь начальными отрезками. Тогда корректно говорить о точке пересечения как о ближайшей (в линейном порядке) к // вершине из //-множества, содержащейся в r-множестве. Отметим следующие свойства //-множеств: если //о — вершина из //-множества, то //о-множество содержится в //-множестве; если //о — вершина из //-множества и то — вершина из т-множества, то //-множество пересекается с r-множеством тогда и только тогда, когда //о-множество пересекается с то-множеством; бесконечное //-множество не может пересекаться с конечным т-множеством. (1) Перечислить отталкивающие ребра. Перечислить неподвижные относитель но / вершины v графа Г, им соответствуют тупики 1„. (2) Для каждой вершины // отталкивающего ребра выяснить, конечно ли //-множество. (3) Для каждой вершины /х отталкивающего ребра с конечным /х-множеством перечислить все элементы из этого множества (они являются вершинами графа Dj) и соединяющие их по движению ребра. (4) Для каждой пары различных о-вершин /ІИГ таких, что и- и г-множества бесконечны, выясить, пересекаются ли эти множества. (5) Если ц- и т-множества в (4) пересекаются, то найти их точку пересечения, перечислить все вершины из /i-множества от д до этой точки включительно, а также соединяющие их по движению ребра. Сделать то же самое для т. Граф Cf будет состоять из всех полученных вершин и ребер (рис. 2). Поскольку отталкивающие ребра и движение определяются алгоритмически, то осталось построить алгоритмы для пунктов (2) и (4). В статьях [7], [28] эти алгоритмы приводятся лишь в некоторых частных случаях (для неприводимых и положительных автоморфизмов). Ключевой идеей в этих статьях является использование обратного выделенного направления в графе Dj. Это направление строится алгоритмически с помощью обратной к / гомотопии. Мы не будем приводить строгое определение, нам важно лишь, что (і) это направление не совпадает с исходным выделенным направленим в вершинах вне некоторого конечного подграфа, (іі) оно задает конечное множество своих отталкивающих ребер, которые можно найти алгоритмически. Вершины графа Df вне конечного подграфа из (і) назовем нормальными. ПРЕДЛОЖЕНИЕ 2.2 [7, 28]. Пусть /л,т — две нормальные вершины графа Df такие, что и- и т-множества не содержат вершин отталкивающих ребер относительно обратного выделенного направления. Тогда следующие условия равносильны: (1) ц-множество пересекается с т-множеством, (2) вершина г содержится в ц-множестве или наоборот. Итак, пункт (4) можно заменить на следующие три пункта. (4.1) Для каждой отталкивающей вершины ц с бесконечным //-множеством найти в этом множестве некоторую вершину \XQ такую, что /іо-множество не содержит вершин отталкивающих ребер относительно обратного направления. (4.2) В о-множестве найти нормальную вершину Ц\. (4.3) Для каждой пары полученных таким образом вершин Ці,Т\ проверить, содержится ли ті в -множестве и наоборот. Пункт (4.2) алгоритмичен, так как бесконечность / -множества дает возможность заменить fj,0 на более далекую по движению вершину Ц\ из этого множества,
Запрещенные развороты в экспоненциальном слое
Пусть Г — конечный связный граф, / : Г - Г — относительный трейн-трек и 0 = Go С С GN = Г — максимальная фильтрация Г. Зафиксируем г. Далее в этом параграфе рассматриваются только пути, лежащие в подграфе Gr, и предполагается, что слой Нг — экспоненциальный. Далее в 4 понадобится следующая ЛЕММА 4.1 [8; 9, лемма И.2.4]. Пусть тит2 такие, что ш(ті) = а(т2). Тогда приведенные пути в графе Г іШпть)]) і№ті)]) + і(иШ-с, где с — алгоритмически вычислимая константа Купера, зависящая только от /. Введем некоторые обозначения. Пусть т — приведенный путь в подграфе Gr и г = Ei ...Еп — его представление в виде конкатенации ребер. Если для некоторого 1 і п — 1 разворот (ЕІ, ЕІ+І) запрещен, то скажем, что путь г содержит запрещенный разворот (ЕІ, ЕІ+І) в вершине u(Ei... Ei). Напомним, что когда говорится о вершинах и ребрах некоторого пути, то подразумеваются их определенные вхождения в этот путь. Из свойств (RTT-i)-(RTT-iii) следует, что число запрещенных разворотов из Нг в пути [/(г)] не больше, чем в пути г (см. рис. 4). Покажем, как определить, когда число запрещенных разворотов из Нг в путях последовательности т, [/(г)], [/2(т)],... постоянно. Если некоторый путь а разрешен в Нг, то по предложению 1.1 в пути f(a) не сокращаются ребра из Нт, однако могут сокращаться ребра из G _i- Для упрощения обозначений в 4 будем считать, что все сокращения ребер из G _і в пути f(o ) произведены. Введем некоторые обозначения. Пусть р0, q0 — приведенные пути в графе Г с общей начальной вершиной. Через 1(ро, ?о) обозначим наибольший общий начальный подпуть путей ро, д0- Тогда р0 = I(p0, до) Ри 7о = 1(Ро, Яо) Я\ Для некоторых приведенных путей р\,Ч\- Обозначим через A(p0,q0) упорядоченную пару путей (рг, 7і). Пусть г — приведенный путь в подграфе Gr, у — его некоторая вершина и разворот пути г в вершине у запрещен. Обозначим через qo — конечный подпуть пути г с начальной вершиной у, а через ро такой путь, что т = р0 qQ. Положим (см. рис. 5). Обозначим через хк начальную, а через zk — конечную вершины пути ак. Иногда, чтобы подчеркнуть зависимость ак, хк, zk от у, будем использовать выражения ак{у), хк{у)у zk(y). ПРЕДЛОЖЕНИЕ 4.2.
Пусть известно, что в каждом из путей г, [/(т)], [/2(т)], ... есть единственный запрещенный разворот из Нг. Тогда существуют алгоритмически вычислимые константы Т 0, р 1 такие, что для всех j 0 выполняется ат+j = Or+j+p ДОКАЗАТЕЛЬСТВО. (A) По условию предложения для любого к 0 путь [/ (т)] = pk-qk содержит единственный запрещенный разворот из Нг и вершина этого запрещенного разворота — точка zk. В частности, пути pk,qk — r-разрешены и их первые ребра лежат в Нг. По (RTT-i) и из формулы ak+i = I(f(pk)jf{qk)) следует, что если путь ак+1 невырожден, то ojfc+i начинается на ребро из Нт. Так как разворот в пути [/ (т)] в вершине zk — запрещенный разворот из НГ1 то по определению запрещенного разворота найдется такое j 0, зависящее от к, что путь ak+j невырожден и, значит, начинается на ребро из Нт. (B) Пусть с — константа из леммы 4.1. Тогда для любого к число ребер из Нг в пути ак не превосходит с и Lr(ak) С, где С = с max{Lr(E) Е— ребро изЯг} . Фиксируем натуральное to такое, что (С) Для любых t 1, s 0 в путях / + (Ро)» / + ( 7о) рассмотрим поддуть &,а = /5(af)/e-1(at+i).../(Q;t+e_i)at+s (см. рис. 6). Начальной точкой пути /?м является вершина f(xt). Заметим, что м+і = Я ( м)/і_1(о!і+в+і).../(аі+в+,_г)о!і+в+і для всех j 0. Отсюда и из пункта (А) следует, что если путь /3tiS вырожден, то существует j 1 такое, что путь fit,s+j невырожден. По (А) все пути at, ..., at+s либо вырождены, либо начинаются на ребро из ЯГ. Значит, по (RTT-i) все пути fs(ott), fs 1(at+i), ...,f(at+s-i), at+s либо вырождены, либо начинаются на ребро из Яг. Поэтому путь PtjS либо вырожден, либо начинается на ребро из ЯГ. Рассмотрим некоторое ребро Е из Нт в пути / ( 7о) или /1(ро)- Тогда по предложению 1.1 путь / +в(?) является г-разрешенным подпутем в пути /,+to+e( ft)) или /Жо+Ї(р0) и ЬГ{} +3(Е)) = A +eLr(.E). Поэтому путь fto+s(E) не может целиком СОДержаТЬСЯ В Пути /?t„+t,s (Е) Очевидно, что путь /to+s(/ (9o)) содержит Pto+i,s- Рассмотрим все подпути пути / ( 7о) такие, что их образ относительно / +8 содержит путь /? 0+)в. Выберем среди них пути с самой левой конечной вершиной, а уже среди этих путей — путь с самой правой начальной вершиной. Обозначим этот путь через piiS, его начальную и конечную вершины — через М и N соответственно (см. рис. 7).
Алгоритм построения графа С
Пусть Г — конечный связный граф, / : Г — Г — относительный трейн-трек и 0 = Go С С GN — Г — максимальная фильтрация Г. Предположим, что для / выполнены следующие свойства: для любой вершины t вершина f(t) неподвижна; если Нт — единичный слой, то в нем содержатся только два ребра: Е и Е, причем f(E) = Е-v, где г; — некоторая петля из подграфа G _i с начальной точкой, неподвижной относительно /. ПРЕДЛОЖЕНИЕ 6.1. Пусть Нг — экспоненциальный слой и їх — приведенный f-путъ в подграфе Gr такой, что пути /х и [///(//)] являются г-разрешенными. Тогда существует вершина // графа Df, содержащаяся в ц-множестве, для которой выполняется одно из следующих не исключающих друг друга утверждений: (1) путь /х содержится в подграфе G _i; (2) путь /х является г-совершенным; (3) -множество конечно. Существует алгоритм, позволяющий построить такую вершину /х и указать номер утверждения, которое для нее выполнено. ДОКАЗАТЕЛЬСТВО. Предположим вначале, что пути ц, [fif(fx)] являются г-разрешенными и путь /(Д, [/(/ )]) лежит в подграфе Gr-\ или вырожден. Если путь (і лежит в G _i, то для // = ц выполнено утверждение (1). Пусть теперь у, не лежит в Gr-\. Покажем, как построить путь / , удовлетворяющий (2). Путь їх можно представить в виде конкатенации трех подпутей: /t = Ь\ &2 &з где пути &і, &з лежат в G _i, путь &г начинается и заканчивается на ребра из Нг. Положим и = 2- [Ьз/{Ь\)]. Вершина jxr графа D/ содержится в //-множестве, так как Докажем сначала, что пути р! и [u f(u )] — r-разрешены. Это следует из выражений и = [[5і]/іі[/(Ьг)1І» [/х /(м )] = [[6І][А І/М][/(М]], предположения о г-разрешенности путей /І, [/х/(/х)] и очевидного замечания, что при умножении г-разрешенного пути слева и справа на подпути из Gr-\ получается снова г-раз-решенный путь. Для доказательства г-совершенности пути /х осталось показать, что разворот между путями // и [/(//)] разрешен. Рассмотрим сначала случай, когда путь [&з/(&і)] невырожден. Так как путь [&з/(&і)1 содержится в подграфе C7r_i, то р! = 62 [ з/( і)І заканчивается на ребро из Нг. Так как путь р! начинается на ребро из Нт, то по предложению 1.1 и свойству (RTT-i) путь [/(//)] тоже начинается на ребро из Нт. Поэтому разворот между путями р! и [/(/ )] смешанный и, значит, разрешенный. Пусть теперь путь [63/(61)] вырожден. Тогда р! = Ь2. Кроме того, &з = [/(&г)] и предполагалось, что /(Д, [/(/х)]) С Gr-i- Отсюда следует, что 1{Ьч, [/()]) С G -1- Так как путь 62 заканчивается на ребро из Нг, то путь J(&2, [/()]) вырожден. Поэтому [/«/(//)] = &1&2[/(ЫП/(&з)]- ПОСКОЛЬКУ путь [ixf(fx)] ЯВЛЯетСЯ Г-раЗрешеННЫМ, pJ = 02, [/(/ )] — [/(Ml» т0 разворот между путями р! и [/(/ )] разрешен.
Таким образом, доказано, что путь и является г-совершенным. Итак, далее можно строить приведенный путь //, содержащийся в //-множестве, для которого вместо утверждения (2) выполнено утверждение (2 ) пути и , [/ /(д )1 являются r-разрешенными и путь 7(Д , [/(/ )]) содержится в Gr_i или вырожден. Далее можно считать, что сегмент /(/2, [/(//)]) содержит ребра из Нг. Обозначим через Е первое ребро пути \х. Если Е — ребро из Gr_i, то заменим ц на [Ец/(Е)\. При такой замене число ребер из Нг в пути //ив сегменте /(Д, [/(/ )]) останется прежним, но число ребер из Gy-i в начале пути fj, уменьшится. Поэтому считаем далее, что Е — ребро из Нг. Возможны следующие случаи, изображенные на рис. 15. Случай (1). Начальный подпуть пути /л до /(Д, [/(//)]) невырожден (и, значит, содержит ребро Е). Путь f(E) является начальным подпутем пути /(Д, [/(/ )]) (воз можно совпадение). Случай (2). Начальный подпуть пути ц до /(Д, [/(//)]) невырожден (и, значит, содержит ребро Е). Путь 7(Д, [/(//)]) является строгим начальным подпутем пути f(E). Случай (3). Начальный подпуть пути ц до /(/І, [/( )]) вырожден, то есть fi = /(Д, [/(/І)])- Путь f(E) является строгим начальным подпутем пути /(Д, [/( )]). Случай (4). Начальный подпуть пути ц до /(Д, [/(д)]) вырожден, то есть ц = 7(Д, [/(/л)]). Путь /(Д, [/(/ )]) является начальным подпутем пути /(E) (возможно совпадение). первое ребро пути Цх лежит в Нг. Заменим путь ц на у,\ Будем производить такие замены каждый раз, когда ц удовлетворяет случаю (1) или (3). Число таких замен конечно, поскольку число ребер из Нг в пути /(/ ъ [/(А І)1) меньше, чем в пути 7(/х, [/( )1)- В итоге мы придем к случаю (2) или (4). Разберем случай (2). Возможны два подслучая. (A) Пусть начальный подпуть пути /І до сегмента 7(Д, [/(/ )]) содержит по край ней мере два ребра. Пусть Еі — следующее за Е ребро пути /х. Положим fj, = [Е/л/(Е)]. Путь \J r-разрешен как подпуть пути [///(/ )], начинается на ребро Е\ и заканчивается на последнее ребро пути f(E). Предположим сначала, что Ех — ребро из слоя Нт (см. рис. 16 (1)). Тогда путь [f([i )] начинается на первое ребро пути f(Et). Поэтому разворот на стыке путей // и [/(//)] совпадает с разворотом на стыке путей f(E) и f(Ex) и, следовательно, разрешен (это следует из г-разрешенности пути ц). В частности, сегмент /(Д , [/(//)]) вырожден и путь // - [/(/ )] является г-разрешенным. То есть путь // удовлетворяет утверждению (2) и предложение в случае, когда Ех — ребро из слоя Нг, доказано. Пусть теперь Еі — ребро из подграфа Gr-\. Обозначим через а максимальный начальный подпуть в пути //, лежащий в Gr-i (см. рис. 16 (2)).
Начальная вершина а совпадает с конечной вершиной ребра Е и лежит в Нг; конечная вершина а также лежит в Нг из-за максимальности а и того, что в пути /х есть хотя бы одно ребро из Нг (например, последнее ребро пути /(E)). Поэтому путь [/(а)] невырожден по (RTT-ii). Путь [/(//)] начинается на подпуть [/(с)], а путь у! заканчивается на последнее ребро пути f(E)t которое по (RTT-i) лежит в ІУГ. Поэтому разворот между путями fj, и [/(//)1 является разрешенным и путь 7(Д , [/(AOD- Кроме того, путь А [/(А01 является г-разрешенным, поскольку r-разрешены пути //, [/(д )1 и разрешен разворот между путями (/ и [/(//)]. То есть путь // удовлетворяет утверждению (2 ) и предложение в случае, когда Ех — ребро из подграфа G -ь доказано. (B) Пусть начальный подпуть пути fj, до сегмента /(Д, [/(/х)]) содержит только одно ребро Е (см. рис. 16 (3)). Положим ц = [Efxf(E)]. Тогда f(E) = 7(Д, [/(/ )]) fj/ и путь ц невырожден, так как /(Д, [/(/х)]) — строгий начальный подпуть f(E). Путь р! является г-разрешенным как подпуть пути f(E). По предложению 1.1 путь [/(/х )1 также является г-разрешенным. Докажем далее, что разворот между путями у! и [/(/ )] разрешен. Из этого будет следовать вырожденность пути 7(Д , [/(//)]) И г-разрешенность пути [n j{ii }\ = у! - [/(/і )]..Таким образом, для пути у! выполнено утверждение (2 ). Обозначим через Q первое ребро пути у/. Предположим вначале, что Q — ребро из Нг. Тогда разворот (Е, Q) лежит в Нг, и поскольку он также является разворотом г-разрешенного пути [y/f(//)], то он разрешен. Значит, разворот между путями f(E) и f(Q) также разрешен. Из предложения 1.1, примененного к г-разрешенному пути у/, следует, что f(Q) — начальный подпуть пути [/(//)]. С другой стороны, у/ — конечный подпуть f(E). Поэтому разворот между путями у! и [/(//)] разрешен. Пусть теперь Q — ребро из Gr_i- Обозначим через а максимальный начальный подпуть пути у/, лежащий в Gr-\. Заметим, что путь у/ содержит хотя бы одно ребро из Нгу например, последнее ребро пути f(E), которое по (RTT-i) лежит в Нг. Поэтому а не совпадает со всем у!. В частности, конечная вершина пути а является начальной вершиной некотрого ребра из Нг и, потому, лежит в Нт. Начальная вершина пути а совпадает конечной вершиной ребра Е и, значит, лежит в Нг. Отсюда по (RTT-ii) путь [/(а)] невырожден и по предложению 1.1, примененному к г-разрешенному пути //,. является начальным подпутем пути [/(А )]- Так как последнее ребро пути р! совпадает с последним ребром пути f(E), то оно лежит в Нг. Отсюда и из того, что путь [f(u )] начинается на подпуть [/(с)] С G -i, следует, что разворот между путями ц и [f(fjf)] разрешен. Итак, предложение в случае (2) доказано.
Доказательство теоремы 2.5
Обозначим через Q/ расширение Q с помощью корня неприводимого многочлена /. Следующее предложение позволяет по оценке корней а, /3 многочленов f(t),g{t) построить минимальный многочлен для примитивного элемента 7 расширения Q(7) = Q(a, 0). ПРЕДЛОЖЕНИЕ 2.1. Пусть f(t),g(t) Є Q[t] — неприводимые многочлены, а и /3 — их корни, заданные кругами Ка,Кр. Тогда можно алгоритмически вычислить неприводимый многочлен h(t) Є Z[i] со старшим коэффициентом 1 такой, что для некоторого его корня j выполнено Q(a, /3) = Q(7)- Также можно алгоритмически вычислить многочлены ha(t), hp(t) Є Q[] такие, что a = ha(j), /З — hp(j). ДОКАЗАТЕЛЬСТВО. По теореме о примитивном элементе [30, 46] можно положить в = ос + с/3 для произвольного В качестве с можно взять любое натуральное число, большее таха;, используя оцен XfcA ки предложения 1.1. Положим d = deg(/) deg(p) и пусть v — d-мерный вектор-столбец с координатами Так как 1, а,..., « (/Ь1 и 1, /?,..., р4 »)-1 — Q-базисы расширений Q/ и Qg, то по коэффициентам многочленов / и g можно вычислить матрицу М Є Md(Q) такую, что (a 4- c/3)v = Ми. Значит, в = а + с/3 — корень характеристического многочлена Хм матрицы М с рациональными коэффициентами. Разлагая по предложению 1.2 многочлен хм на неприводимые множители и оценивая корни а, (3 (а, следовательно, и 9) с необходимой точностью, можно найти неприводимый многочлен k(t) Є Z[t], корнем которого является 9. Пусть к — старший коэффициент h(t). Положим h(t) = kn-xh[t/k) wj = k9. Многочлены g(t) и f(9 — ct) имеют единственный общий корень /?, поэтому t — /3 — нод( 7(), f(9 — ct)). С другой стороны, g(t), f(9 — ct) Є Q(9)[t], и по алгоритму Евклида коэффициенты под(д(Ь), f(9—ct)) можно выразить через коэффициенты g(t) и f(9 — ct). Так мы получим выражение (3 в виде многочлена от 9 с коэффициентами из Q, по которому можно построить многочлен hp. Положим ha(t) = t/k — chp{t). ПРЕДЛОЖЕНИЕ 2.2. Пусть А Є M„(Z), a — характеристическое число матрицы А, заданное кругом Ка. Тогда ранг матрицы (А — аЕ)3 вычисляется алгоритмически (с помощью метода окаймления миноров) для любого натурального j. ПРЕДЛОЖЕНИЕ 2.3. Пусть f(t),g(t) Є ОД], а Є Nul(/), /З Є Nvu(g) заданы кругами Ка,Кр, числа а,/3 0 — алгебраические целые. Тогда можно алгоритмически проверить, существуют ли такие натуральные к, т, что ак = /Зт, и найти такие к, т, если они существуют. ДОКАЗАТЕЛЬСТВО.
Рассмотрим расширение Q(a, ) = Q(9), построенное в предложении 2.1. По замечанию 1.7 можно вычислить нормы а,р" в расширении Q(0). Необходимым условием равенства ак и J3m является N(a)k = N(f3)m. Поскольку N(ct),N(fi) Є Q, то можно выяснить, существуют ли натуральные р, q такие, что N(a)p = N(/3)4. Предположим, существуют. Возьмем некоторые. Тогда N(a?) = N(Pq). Заметим, что вместо а, J3 можно рассматривать ар, /3я и в дальнейшем считать, что N(a) = N{0). Рассмотрим возможные случаи. 1. ./V(a) = \N(j3)\ ф 1. Если ак = /?" для некоторых к и ш, то к = т. Отсюда а = Р, т. к. по условию а, /3 0. 2. iV(a) = \N(P)\ = 1. В этом случае а и @ являются единицами модуля Ор и могут быть представлены как произведение основных единиц: a = etf ...єг/ и Р = є ... е Г с целыми показателями. Эти показатели можно вычислить алгоритмически по предложению 1.9. Используя теорему 1.8, можно найти натуральные к,т (если они существуют) такие, что ак = /3"\ ПРЕДЛОЖЕНИЕ 2.4. Пусть а ,/?» (1 г s) — вещественные положительные числа, не равные 1. Предположим, что а = Р% для некоторых натуральных k, rtii таких, что нод(&,-, ш,-) = 1, і = 1,..., s. Тогда существуют натуральные к, т такие, что ctk = /J если и только если к\ = - = ks и ті = = ms. ТЕОРЕМА 2.5. Пусть А, В Є Mn(Z). Тогда можно алгоритмически проверить, существуют ли натуральные к,т такие, что абсолютные жордановы формы матриц Ак и Вт совпадают. Следовательно, существует алгоритм проверки квазиизометричности групп ГМі и Гм2 при det Мх, detM2 Ф 0, ±1. ДОКАЗАТЕЛЬСТВО. Пусть Sp(A) = {аь...,а„}, Sp(B) = {&,...,#,} с учё-том кратности, и щ = ск , / = А2- Пусть К\,..., Кп и Lb...,Ln — круги, удовлетворяющие условиям предложения 1.4 для характеристических многочленов матриц А, В соответственно. Если искомые &, га существуют и матрицы имеют нулевые собственные значения, то (увеличив к, т в несколько раз) можно считать, что все жордановы клетки с нулём на диагонали имеют порядок один. Поэтому в дальнейшем предполагаем, что 0 $. Sp(. 4) U Sp(.B). Так как при возведении в степень таких матриц структура жордановых клеток не меняется, необходимые и достаточные условия существования степеней к, т таковы: (а) модули собственных значений в некоторой степени совпадают: существуют подстановка а Є Sn и числа к,т Є Z 0 такие, что для любого і (б) совпадает структура клеток в абсолютной жордановой форме: для к, т най денных в предыдущем пункте, при всех г о j должно выполняться равенство где SQIJ) — число жордановых клеток порядка j с числом 7 на диагонали в жордановой форме матрицы С. Сложность проверки условия (а) заключается в том, что собственные числа матриц неизвестны. По предложению 1.3 можно построить многочлены f(t),g(t) такие, что f(6ti) = g(Pi) = 0 для всех і. Фиксируем а Є Sn. Так как по замечанию 1.6 числа 6? , / алгебраические целые, то для каждой пары 6? , Д, ) можно применять предложение 2.3 для отыскания чисел
