Бесплатно скачать, заказать диплом, курсовую, диссертацию Группа неподвижный точек автоморфизма свободной группы

У нас уже 21989 рефератов, курсовых и дипломных работ

Сделать закладку на сайт

Заказать диплом, курсовую, диссертацию

Быстрый переход к готовым работам

Мнение посетителей:

Книга жалоб
и предложений

Название	Группа неподвижный точек автоморфизма свободной группы

Количество страниц	73

ВУЗ	МГИУ

Год сдачи	2010

Бесплатно Скачать	23532.doc

Содержание	Содержание ОГЛАВЛЕНИЕ ВВЕДЕНИЕ...3 ГЛАВА 1. ГРУППА НЕПОДВИЖНЫХ ТОЧЕК АВТОМОРФИЗМА СВОБОДНОЙ ГРУППЫ § 1. Относительный трейн-трек для автоморфизма свободной группы конечного ранга...6 § 2. Конструкция графов Df и С/ для гомотопической эквивалентности / . 12 § 3. Определение и свойства отображения /...16 § 4. Запрещенные развороты в экспоненциальном слое...19 § 5. Свойства некоторых путей в графе Г ...37 § 6. Алгоритм построения графа С/...46 § 7. Основные результаты...65 ГЛАВА 2. АЛГОРИТМИЧЕСКАЯ ПРОВЕРКА КВАЗИИЗОМЕТРИЧНО-СТИ НЕКОТОРЫХ РАСШИРЕНИЙ АБЕЛЕВЫХ ГРУПП ПОСРЕДСТВОМ ЦИКЛИЧЕСКОЙ § 1. Предварительные сведения ...67 § 2. Доказательство теоремы 2.5 ...70 ЛИТЕРАТУРА...73 ВВЕДЕНИЕ Для автоморфизма а свободной группы F конечного ранга группа неподвижных точек Fix (а) состоит из всех слов w € F таких, что a(w) = w. Для множества автоморфизмов S группа неподвижных точек Fix(S) определяется как пересечение всех групп Fix(a) для автоморфизмов а, входящих в S. В 1975 году Дайер и Скотт [10] показали, что для автоморфизма конечного порядка группа неподвижных точек— свободный множитель в F. В частности, для таких автоморфизмов верна гипотеза Скотта о том, что ранг группы Fix(a) не превосходит ранга F. Позднее Герстеном [15], Голдстейном и Тернером [16, 17], Купером [8] было доказано, что группа Fix (а) конечно порождена для любого автоморфизма а свободной группы F. Томас [27] обобщил этот результат для произвольного множества автоморфизмов S. В 1992 году Бествина и Хендел [4] ввели понятие относительного трейн-трека, при помощи которого доказали гипотезу Скотта для произвольного автоморфизма а группы F. Другие доказательства [13, 14, 21, 25] получены с помощью действий групп на деревьях. Имрихом и Тернером [18] было показано, что гипотеза Скотта выполняется и для произвольного эндоморфизма группы F. Дике и Вентура [9] на основе работы [4] доказали, что ранг группы Fix(S') не превосходит ранга F для множества S инъективных эндоморфизмов группы F. Бергман [2] показал, что такое же неравенство выполняется для произвольного множества S эндоморфизмов группы F. С использованием техники трейн-треков Коллинз и Тернер полностью описали автоморфизмы, у которых группа неподвижных имеет максимальный возможный ранг. В частности, все они полиномиального роста. В работе Коэна и Люстига [7] приводится алгоритм вычисления базиса Fix(a) для положительных автомофизмов а группы F, то есть таких, что для некоторого базиса Xi,...,xn группы F приведенные слова а(х\),...,а(хп) состоят только из положительных степеней хь...,хп. Пусть Г — конечный связный граф. Трейн-треком называется такая гомотопическая эквивалентность / : Г -* Г, что любая степень / локально инъективна на внутренности любого ребра графа Г. Используя работу [7], Тернер [28] указал алгоритм, позволяющий вычислять базис группы гомотопических классов петель в графе Г, неподвижных относительно трейн-трека /. При этом предполагается, что базисная вершина v неподвижна относительно /. Таким образом, работа Тернера позволяет вычислять базис Fix(a) для автоморфизма а, который можно топологически представить трейн-треком. Не для любого автоморфизма группы F можно построить трейн-трек, однако Бествиной и Хенделом [4] было показано, что для неприводимых автоморфизмов можно. Приводимым называется такой автоморфизм а, что существует неединичный свободный множитель группы F вида G\ * • • • * Gk и а транзитивно переставляет классы сопряженности подгрупп Gi,...,Cr. При этом если 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~lua(w) : w € F} — а-классом Райдемайстера элемента и. В § 1 используется также понятие а+-орбиты, которая совпадает с множеством {ак(и) : к € N}. Бринк-манн в препринте [б] показал, что проблема вхождения в а-орбиту алгоритмически разрешима. В главе 1 также доказана теорема 7.2, которая показывает, что проблема вхождения в а-класс Райдемайстера тоже алгоритмически разрешима. Пункт (2) этой теоремы отвечает на вопрос 3 (i) из [9]. ТЕОРЕМА 7.2. Пусть F — свободная группа конечного ранга, а — ее автоморфизм, заданный образом некоторого фиксированного базиса. Тогда выполняются следующие утверждения. (1) Для любого слова w G F его а-класс Райдемайстера состоит из ct-орбит. (2) Пусть и, v — слова в группе F. Тогда можно алгоритмически определить, принадлежит ли слово v а-классу Райдемайстера слова и. На основе теоремы 7.2 получена теорема ТЕОРЕМА 7.3. Пусть F — свободная группа конечного ранга. Тогда в любом расширении группы F посредством циклической группы разрешима проблема сопряженности. Структура главы 1 такова. В § 1 приводятся необходимые сведения из теории относительных трейн-треков Бествины, Фейна и Хенделя [3,4], а также две теоремы Бринкманна из [б] о проблеме вхождения в а-орбиту. В том же параграфе строится "хорошее" геометрическое представление некоторой фиксированной степени автоморфизма а и выводится следствие из теоремы Бринкманна для случая гомотопической эквивалентности конечного связного графа. В § 2 описывается подход Коэна— Люстига и Тернера к вычислению базиса Fix(a) из [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\) и (Y, dy) — метрические пространства. Отображение / : X —> Y называется квазиизометрией, если существуют константы K,Ci,C2 такие, что (1) 7^dx{xi,x2)-C2 < dY(f(xi),f(x2)) ^ Ctdx(xux2) + C2 для всех хих2 G X; (2) if-окрестность f(X) совпадает с Y. Пространства X и Y назывются квазиизометричными, если существует ква-зиизометрия f : X.—? Y. Пусть G,H — конечно порожденные группы, dc,dn — словарные метрики на G,H. Группы G и Н называются квазиизометричными, если метрические пространства ((?, da) и (Н, da) квазиизометричны. Это определение корректно, поскольку словарные метрики, определенные различными конечными порождающими множествами, задают квазиизометричные пространства. Пусть М — целочисленная матрица порядка п с определителем, отличным от О, ±1, и пусть через Гд/ обозначено HNN-расширение группы Ъп при помощи мономорфизма срм с матрицей М. Фарб и Мошер [11] привели следующий критерий квазиизометричности групп вида Гд/. ТЕОРЕМА [11]. Пусть MUM2 e M«(Z), detMbdetM2 ф 0,±1. Тогда группы Тмх и Гм2 квазиизометричны в том и только том случае, когда найдутся натуральные ri,r2 такие, что матрицы Мр и М?2 имеют одинаковые абсолютные жордановы формы. Абсолютная оюорданова форма матрицы М получается из жордановой формы заменой диагональных элементов на их модули. Условие det M — ±1 эквивалентно полицикличности группы Гм (доказательство можно найти в [12]) и на данный момент критерий квазиизометричности таких групп Гд^ неизвестен. На основе теоремы Дирихле [29, т. 5, стр. 131] о строении группы единиц модуля алгебраических целых поля F в главе 2 получена следующая ТЕОРЕМА 2.5. Пусть А,В? М„(Ж). Тогда можно алгоритмически проверить, существуют ли натуральные к,т такие, что абсолютные жордановы формы матриц Ан и В1 совпадают. В частности, существует алгоритм проверки квазиизометричности групп Гд/, и Гм2 при det Mi, det М2 Ф 0, ±1. Результаты главы 2 докладывались на семинарах "Алгебра и Логика" Новосибирского государственного университета, "Теория групп" и "Геометрическая теория групп" Института математики СО РАН, а также на конференции в Красноярске в 2002 г. [35]. Эти результаты опубликованы в [37]. Автор благодарит своего научного руководителя д.ф.-м.н. Олега Владимировича Богопольского за внимание и помощь, оказанные в работе. ГЛАВА 1. ГРУППА НЕПОДВИЖНЫХ ТОЧЕК АВТОМОРФИЗМА СВОБОДНОЙ ГРУППЫ § 1. Относительный трейн-трек для автоморфизма свободной группы конечного ранга Введем основные определения и напомним некоторые факты из [4]. Пусть Г — конечный связный граф, Г° — множество вершин, Г1 — множество ребер графа Г. Через Е обозначается ребро, противоположное ребру Е. Иногда будем рассматривать геометрическую реализацию графа Г и обозначать ее той же буквой. Путь в графе Г — это непрерывное отображение т : [0,1] —> Г, локально инъек-тивное в точках t G [0,1] таких, что т(<) $. Г°. Часто путь будет отождествляться со своей геометрической реализацией в графе Г и обозначаться той же буквой. Через f обозначается путь, обратный пути г, через а(т) и cj(t) обозначаются начальная и конечная точки пути т, через 1(т) обозначается длина геометрической реализации пути г (считаем, что каждое ребро отождествляется с отрезком [0,1]). Через 1„ обозначается тождественный путь в вершине v графа Г. Под обозначением 1 понимается тождественный путь в некоторой вершине графа Г. Далее рассматриваются только те пути т, для которых точки а(т) и ш(т) являются вершинами графа Г. Скажем, что путь приведен, если он не содержит подпутей вида j/Д. Подпути вида ц]х будем называть сокращениями. Через [г] обозначается приведенный путь в Г, гомотопный т относительно его концов, через [[г]] — класс путей в Г, гомотопных пути г относительно его концов. Выражение т = ц означает, что пути ти/i гомотопны. Если пути т и \1 совпадают, то используется обозначение г = ц. Скажем, что между приведенными путями ц vi т нет сокращений, если ш{ц) = а(т) и последнее ребро пути ц не противоположно первому ребру пути т. В этом случае конкатенацию ц и т будем обозначать ц • т. Далее в главе 1 при упоминании вершин и ребер некоторых путей, подразумеваются их определенные вхождения, которые будут ясны из контекста. Пусть / : Г —> Г — гомотопическая эквивалентность, удовлетворяющая условиям: /(Г°) С Г°, отображение /\|г\г° локально инъективно. В частности, для любого ребра Е путь f(E) приведен и невырожден, a(f(E)), ш(/(Е)) — вершины в Г. Пусть v — произвольная вершина графа Г и р — произвольный путь в Г, соединяющий вершины v и /(и). Отображение 7i"i(r,v) —> tti(T,v), заданное правилом [[ж]] ¦-»¦ [[р/(х)р]], является автоморфизмом группы 7Гх(Г, v). Для различных путей р соответствующие им автоморфизмы отличаются на внутренний автоморфизм группы тгх(Г,v). Обозначим через /« изоморфизм групп iri(T,v) -> Ж\(Г,/(ь)), заданный правилом [[а;]] ¦->• [[/(х)]].. Разворотом в графе Г называется неупорядоченная пара его ребер с общей начальной вершиной. Разворот вырожден, если эти ребра совпадают, и невырожден в противном случае. Отображение Df : Г1 -> Г1 каждому ребру Е ставит в соответствие первое ребро пути f(E). Отображение Т/ действует на разворотах по правилу Tf{[Ei,E2)) = (Df(El),Df(E2)). Разворот (ЕХ,Е2) называется разрешенным, если развороты (Tf)n((Ei,E2)) невырождены для всех натуральных п, и запрещенным в противном случае. Путь называется разрешенным, если он не содержит запрещенных разворотов. Из каждой пары противоположных ребер графа Г выберем по одному и занумеруем выбранные ребра натуральными числами от 1 до к. Матрица М = (m,-j) отображения / : Г —» Г определяется следующим образом: rriij равно числу вхождений ребра с номером г и обратного к нему в /-образ ребра с номером j. Фильтрация для / : Г —>• Г — это возрастающая последовательность /-инвариантных подграфов 0 = Go С • • • С Gn = Г. Подграф Щ = cl(G< \ Gj_i) называется г-ым слоем. Разворот с одним ребром из Щ и другим из Gi-\ называется смешанным разворотом в (Gi, Gi-i). Можно предполагать, что ребра в Г упорядочены так, что ребра из Щ предшествуют ребрам из Hi+i. Ребра из Щ определяют квадратную подматрицу М^ матрицы М. Фильтрация называется максимальной, если каждая матрица М^ неприводима или является нулевой. В дальнейшем будут рассматриваться только максимальные фильтрации. Число Перрона-Фробениуса ненулевой матрицы Mj обозначим через Aj. Известно, что А$ ^ 1. Слой Щ называется нулевым слоем, если Mi — нулевая матрица. В этом случае для любого ребра Е из НТ путь f(E) не содержит ребер из НТ и, значит, лежит G>-i- Слой Щ называется экспоненциальным, если Aj > 1. Слой Щ называется единичным, если А< = 1. В последнем случае известно, что Mi — матрица перестановки и, значит, для любого ребра Е из Нт путь f(E) содержит в точности одно ребро из Нг. Путь в подграфе Gr, не содержащий запрещенных разворотов в Нт, называется г-разрешенным. Последовательность максимальных подпутей пути г из Нг назовем г-частью пути т. Пусть Нг — экспоненциальный слой, v — фиксированный собственный вектор-столбец матрицы Мгу отвечающий числу Перрона-Фробениуса Аг. Так как матрица МТ целочисленная, то координаты вектора v — частное полиномов от Аг с рациональными коэффициентами. Для экспоненциального слоя Нт определим г-длину произвольного пути г следующим образом и обозначим ее через Lt{t). Положим г-длину любого ребра из Нг равной соответствующей этому ребру координате вектора v. Для произвольного пути г в графе Г положим Ьт(т) равной сумме г-длин ребер, из которых состоит этот путь. Пусть А — число Перрона-Фробениуса некоторой целочисленной неотрицательной неприводимой матрицы М. Так как А алгебраично, то для любых двух выражений Pi(A)/gi(A) и Р2(А)/<7г(А), где Pi,P2, Qi, 4i — многочлены с рациональными коэффициентами, можно алгоритмически выяснить, равны ли они, и если не равны, то какое из этих выражений больше. Гомотопическая эквивалентность / : Г —>¦ Г такая, что /(Г°) С Г° и отображение /\|г\г° локально инъективно, называется относительным трейн-треком, если можно указать максимальную фильтрацию для графа Г такую, что для любого экспоненциального слоя НТ этой фильтрации выполняются следующие условия: (RTT-i) Df отображает ребра из Нг в ребра из НГ; в частности, все смешаные развороты в (G>,Gy_i) разрешены; (RTT-ii) если р С Gr_i — нетривиальный путь с конечными вершинами из Нг П G>_i, то [/(/>)] — нетривиальный путь с конечными вершинами из Нг П G>_i; (RTT-iii) для любого г-разрешенного пути р С Gr с конечными точками из Г° путь /(р) не содержит запрещенных разворотов из Нг. Первая часть следующего предложения доказана в [4, лемма 5.8], вторая часть следует из нее и свойств (RTT-i)-(RTT-iii). ПРЕДЛОЖЕНИЕ 1.1. Пусть р — приведенный г-разрешенный путь в подграфе GT графа Г, слой НТ — экспоненциальный up = bo • а\ • &i •¦...- а • 6, где к ^ 1, oi,..., dk — пути из Нг, 60» • • - > Ь ~ пути из Gr-\, причем все эти пути за исключением, быть может, bo и bk невырождены. Тогда [/(/>)] = [f(b0)] • /Ы • [№)] •... • /(«) • [ДМ] является невырожденным г-разрешенным путем. Более того, для всех г ^ 1 [Г(р)\ = [f (bo)] • [/' («О] • [f(bx)] -... • [/'К)] • [/ (ь)] явллетсл невырожденным r-разрешенным путем. Из определения относительного трейн-трека следует, что для любых экспоненциально растущего слоя НТ и ребра Е из Нг выполнено Lr(f(E)) — \Lr(E). Отсюда и из предложения 1.1 имеем, что для любых экспоненциально растущего слоя Нг и г-разрешенного пути р С Gr имеем Lr([f(p)]) = ArLr(p)- В главе 1 диссертации используется следующая замечательная теорема Бествины и Хендела из [4], с учетом принятых в § 1 этой статьи соглашений. Композиция отображений читается слева направо. ТЕОРЕМА 1.2 [4, т. 5.12]. Для любого автоморфизма а свободной группы F конечного ранга можно алгоритмически построить граф Г, относительный трейн-трек f : Г —> Г, найти вершину v G Г°, путь р С Г, соединяющий вершины v и /(и), и указать изоморфизм i : F —? 7ri(r, v) такие, что автоморфизм «~1аг группы 7Гг(Г, v) совпадает с отображением, заданным правилом [[х\] ¦->¦ [[р]]/([[ж]])[[р]], где В работе [3] относительный трейн-трек модифицирован до улучшенного, но при этом автоморфизм а заменен на а" при некотором алгоритмически вычислимом показателе п > 0. Следующая теорема является частью теоремы 5.1.5 из [3]. ТЕОРЕМА 1.3. Для любого автоморфизма а свободной группы F конечного ранга можно алгоритмически вычислить число п, построить граф V, относительный трейн-трек f : Г —* Г, найти вершину v € Г°, путь р С Г, соединяющий вершины v и f(v), и указать изоморфизм i : F —> 7Ti(T,v) такие, что ав- томорфизм z~xani группы 7Гх(Г,г;) совпадает с отображением, заданным правилом [[х\] н-> [[р]]/»([[з:]])[[р]], где [[х]] е тп(Г, v). Кроме того, выполнены следующие свойства. (1) Для любой вершины t графа Г вершина f(t) неподвижна. (2) Если Нг — единичный слой, то в нем содержатся только два ребра: Е и Е, причем f(E) = Е • а, где а — некоторая петля из подграфа Gr-\ с начальной точкой, неподвижной относительно /. ПРЕДЛОЖЕНИЕ 1.4. Пусть X и Y — конечные связные одномерные CW-комплексы, f : X —> Y — непрерывное клеточное отображение. Тогда f является гомотопической эквивалентностью тогда и только тогда, когда отображение f индуцирует изоморфизм фундаментальных групп irx(Xyv) и tti(Y, f(v)) для некоторой вершины v комплекса X. ДОКАЗАТЕЛЬСТВО. Очевидно, что гомотопическая эквивалентность конечных связных одномерных CW-комплексов индуцирует изоморфизм их фундаментальных групп. Докажем обратное утверждение. Пусть непрерывное отображение / : X —>У индуцирует изоморфизм фундаментальных групп щ(Х,у) -+ tti(Y, /(и)). Стягивание максимальных поддеревьев в конечных одномерных СИ^-комплексах является гомотопической эквивалентностью. Поэтому можно считать, что X, Y — розы, т.е. СЖ-комплексы с одной вершиной и некоторым количеством ребер с началом и концом в этой вершине. Пусть х — вершина розы X и у — вершина розы Y. Число ребер в этих розах одинаково, так как их фундаментальные группы изоморфны. Для изоморфизма (Z)"1 можно построить непрерывное отображение д : (У, у) —> (Х,х) такое, что <7» = (Z)"1. Заметим, что (5°/)* — тождественное отображение на тгх (X, х). Тогда для каждого ребра е розы X путь (gof)(e) гомотопен е. Поэтому отображение д о /гомотопно тождественному. Аналогично отображение fog гомотопно тождественному. Это означает, что / — гомотопическая эквивалентность. ? ТЕОРЕМА 1.5. Пусть а — автоморфизм свободной группы F конечного ран-га, f : Г —»¦ Г — относительный трейн-трек из теоремы 1.3. Тогда можно алгоритмически расширить граф Г до графа Г\, продолжить отобраоюение f до относительного трейн трека fi : IY—> 1\ и указать вершину Vi € Г°, неподвижную относительно Д, и изоморфизм j : F' —>¦ 7Ti(ri,Vi) такие, что автоморфизм j~lanj группы 7Ti(ri,Vi) совпадает с (Д). Кроме того, выполнены следующие свойства. (1) Для любой вершины t графа Г\ вершина fi(t) неподвижна. (2) Если Нг — единичный слой, то в нем содержатся только два ребра: Е и Е, причем fi(E) = Е • а, где а — некоторая петля из подграфа Gr-\ с начальной точкой, неподвижной относительно Д. ДОКАЗАТЕЛЬСТВО. Пусть п, v, р и i : F —>¦ тг^Г,^) — число, вершина, путь и изоморфизм из теоремы 1.3. В частности, для любого w G F выполняется равенство Граф Гх получим из графа Г присоединением новой вершины v\ и нового ребра Е с начальной вершиной vi и конечной /(и). Отображение /i определим, как продолжение /, заданное на ребре Е правилом fi(E) = Ef(p). По предложению 1.4 отображение /i является гомотопической эквивалентностью. Максимальная фильтрация для Fi получается из максимальной фильтрации для Г добавлением нового единичного слоя сверху, состоящего из ребер Ел Е и их вершин. Легко проверить, что Д —относительный трейн-трек. Утверждения (1), (2) следуют из утверждений (1), (2) теоремы 1.3 и определения отображения Д. Изоморфизм j : F —> 7ri(Fi,vi) установим правилом j(w) — [[?]]/«(г(го))[[?]], где w € F. Проверим, что автоморфизм j~xanj группы 7Ti(Fi,vi) совпадает с автоморфизмом (Д). Достаточно проверить, что (fi){j(w)) = j(an(w)) для произвольного w € F. Имеем, Пусть F — свободная группа конечного ранга с фиксированным базисом X. Для любого w G F через \w\ обозначим словарную, а через \|\|го\|\| — циклическую длину слова w в базисе X. Понятие улучшенного трейн-трека использовано Бринкманном для решения проблемы вхождения слова v G F в а-орбиту слова и G F. Приведем две основные теоремы из [6] и, для полноты, доказательство теоремы 1.7 на основе теоремы 1.6. ТЕОРЕМА .1.6 [б, т. 0.1]. Пусть F — свободная группа конечного ранга с фиксированным базисом X и а — автоморфизм F. Тогда можно алгоритмически вычислить константу К такую, что для любого w € F и для любых натуральных N, г, удовлетворяющих условию 0 ^ г ^ N, выполнены следующие утверждения: ТЕОРЕМА 1.7 [6, т. 0.2]. Пусть а — автоморфизм свободной группы F конечного ранга, u,v E F. Тогда можно алгоритмически проверить следующие утверждения. (1) Существует ли целое N такое, что aN(u) = v. Более того, можно проверить, существует ли натуральное N такое, что aN(u) = v. (2) Существует ли целое N такое, что aN(u) и v сопряжены в F. Более того, можно проверить, существует ли натуральное N такое, что а1 (и) и v сопряжены eF. ДОКАЗАТЕЛЬСТВО. Покажем, как проверить, существует ли N ^ 0 такое, что aN(u) = v. Пусть К — константа из теоремы 1.6, L = К{\и\ + \v\), M — число слов в F длины не более, чем L. Будем вычислять а(и), а2(и),... до тех пор, пока не будет выполнено одно из утверждений: а* (и) — и или \|а1(и)\| > L. Одно из этих утверждений выполнено для некоторого 1 ^ i ^ М + 1. Если выполнено первое условие, то справедливо следующее утверждение: если есть N ^ 0 с условием aN(u) = vt то можно выбрать N < г. При выполнении второго условия теорема 1.6 (2) гарантирует, что N < г. Итак, достаточно сравнить с v конечное число слов: и,а(и),...,ам(и). Для доказательства (1) достаточно заменить и на и и повторить рассуждения. Алгоритм проверки (2) строится аналогично, с заменой словарной длины на циклическую. ? Из этой теоремы выведем нужное нам СЛЕДСТВИЕ 1.8. Пусть Г - конечный связный граф и / : Г ->¦ Г — гомотопическая эквивалентность такая, что образ каждого ребра является конкатенацией нескольких ребер. Тогда для любых двух путей р, т, начальные и конечные точки которых являются вершинами, в графе Г можно алгоритмически определить, существует ли натуральное к такое, что f k(p) = т. ДОКАЗАТЕЛЬСТВО. Сведем проблему к случаю, когда начало р совпадает с началом г и конец р совпадает с концом т. Положим pi = /(р) и пусть u^Vi — начальная и конечная вершины пути р<. Так как множество упорядоченных пар вершин графа Г конечно и / действует на этом множестве, то можно найти натуральные ni,ri2 такие, что упорядоченные пары (щ, Vi) различны при 0^i^ni+n2 — 1 и Если / (р) = т при к ^ щ + гаг, то к можно записать в виде к = г + где j ^ 0 и П\ + П2 ^ i < п\ + 2п2- Положим g = /П2. Тогда fk(p) = g{pi) и g сохраняет начало и конец пути р^. Таким образом, наша задача сводится к проверке, выполняется ли равенство /(р) = т при 0^A; 0 такое, что g-'(pi) = т для некоторого пг + п2 ^ г < щ + 2пг- При этом g сохраняет начальную и конечную вершины пути р^. Итак, с самого начала молено считать, что начальная вершина р совпадает с начальной вершиной т и конечная вершина р совпадает с конечной вершиной г, причем отображение / сохраняет эти вершины. Обозначим их через и, v. Добавим к графу Г новую вершину w и два новых ребра Е\ и Е^, соединяющие вершину w с вершинами и и и. Получим новый граф Т\. Определим продолжение /i отображения / на ребрах Е\, Еч тождественно. Докажем, что эндоморфизм (/i)« группы 7ri(Ti,w), индуцируемый отображением Д, является автоморфизмом. Действительно, 7ri(rbiw) является свободным произведением групп Fi и Fi, где Fx =-{[[Е1ХЩ] \| [[]] 6 7п(Г,«)}, F2 = (а), где а = [[Е^Ж]]- Отображение (/х), переводит группу F\ изоморфно в себя, поскольку отображение / индуцирует автоморфизм группы 7Ti(r,«) (т.к. / является гомотопической эквивалентностью). Далее, (/i)(a) = а^а, где а\ = [[Eif(r)fEi]] G F\. Итак, (/i)« — автоморфизм группы Заметим, что при фиксированном к ^ 0 равенство / к(р) = г выполнено тогда и только тогда, когда выполнено равенство fxk(E\pE2) = EitE2. Таким образом, исходная задача эквивалентна проблеме вхождения элемента [[^т.Е'г]] в (Л)^-орбиту элемента [[2?1р?72]]» которая разрешима по теореме 1.7 (1). П ТЕОРЕМА 1.9. Пусть F — свободная группа конечного ранга и а — ее автоморфизм конечного порядка. Тогда можно алгоритмически вычислить базис Fix(a). ДОКАЗАТЕЛЬСТВО. Пусть Н — полупрямое расширение группы F с помощью группы, порожденной а, С(а) — централизатор а в Н. Как конечное расширение гиперболической группы Н является гиперболической группой. По [20] можно вычислить константу гиперболичности 5 группы Яипо [5] вычислить порождающие С (а). Очевидно, Fix(a) = C(a)nF и поэтому порождающие группы Fix(a) (а значит, и базис) можно вычислить алгоритмически. ? СЛЕДСТВИЕ 1.10. Пусть а — автоморфизм свободной группы конечного ранга, п — некоторое натуральное число. Пусть таксисе известен базис Fix(an). Тогда можно алгоритмически вычислить базис Fix(a). ДОКАЗАТЕЛЬСТВО. Ограничение а на Fix(an) имеет конечный порядок, делящий п, причем Fix(a) — подгруппа в Fix(an). Применяя теорему 1.9 к группе F = Fix(an) и ее автоморфизму а\р, вычислим базис Fix(a). ? Таким образом, для вычисления базиса Fix(a) достаточно вычислить базис подгруппы F5c(/i) = { [[т]] € 7Ti(rbvi) \| /(т) = г }, где Гь vu h ~ граф, вершина и относительный трейн-трек из теоремы 1.5. § 2. Конструкция графов Dj и С/ для гомотопической эквивалентности / В этом параграфе приводятся необходимые сведения из работ [7] и [28]. Пусть Г — конечный граф, / : Г —> Г — гомотопическая эквивалентность, отображающая вершины графа Г в вершины, /\|г\г° локально инъективно, v, — вершина графа Г, неподвижная относительно /. Положим Fix(/) = { [\р]] 6 7гг(Г,и») \| /(р) = р }. В работах [7], [28] предложена процедура вычисления базиса Fix(/) при помощи построения некоторых графов D/ и С/. Эта процедура обладает одним существенным недостатком: в ней не указано, когда нужно остановиться, то есть на каждом шаге нет уверенности, что построен весь базис Fix(/). Дадим краткое описание этой процедуры. Путь ц в графе Г называется f-путем, если конечная вершина пути /и совпадает с начальной вершиной пути /(/). Отметим следующие свойства /-путей: тождественный путь в вершине v, обозначаемый lv, является /-путем тогда и только тогда, когда вершина v фиксируется отображением /; если ц — /-путь, то [//] тоже /-путь; если ц — /-путь я Е — ребро в Г с начальной вершиной а(ц), то E[i,f(E) — /-путь. Граф D/ определяется следующим образом. Вершинами графа D/ являются приведенные /-пути в графе Г. Пусть ц — приведенный /-путь в графе Г. Обозначим через Е\,...,Еп все ребра в графе Г с начальной вершиной а{ц). Тогда в графе D/ вершина ц соединяется с вершинами [Einf(Ei)],..., [Enfif(En)] ребрами с метками Е\,...,Еп соответственно. Метка пути в графе D/ — это произведение меток последовательных ребер, из которых этот путь состоит. Заметим, что вершины //г и цъ соединяются в графе D/ путем с меткой р тогда и только тогда, когда p(Aif(p) — путь в графе Г, гомотопный пути Ц2. В частности, при дг = ц2 = lv. получим, что петле с меткой р в графе Df с началом в вершине 1„, соответствует петля р в графе Г с началом в вершине и, такая, что /(р) = р, и наоборот. Поэтому фундаментальную группу компоненты графа Df, содержащую вершину lVt, можно отождествить В общем случае граф Df может иметь бесконечное число компонент связности и некоторые из них могут быть бесконечны. Обозначим компоненту связности графа Df, содержащую вершину 1^., через Df{lVm). Пусть С/ — некоторый конечный связный подграф графа Df(lVm), содержащий вершину 1„, и такой, что фундаментальная группа С/ совпадает с фундаментальной группой графа ?)/(1„.). Заметим, что граф С/ определяется неоднозначно. Если удастся алгоритмически построить С/, то задача о нахождении Fix(/) также будет алгоритмически разрешима. Пусть ц — приведенный /-путь в графе Г и Е — его первое ребро. Тогда /л и [Efif(fj,)] — вершины графа Df, соединенные ребром с меткой Е. Выделенным направлением в вершине [м графа Df называется направление этого ребра. На этом ребре вблизи вершины ц ставится треугольник вида >. Заметим, что нет выделенного направления только в вершинах 1„, где v G Г° — неподвижная относительно / вершина. Такие вершины назовем тупиками. Отталкивающими ребрами в Df называются ребра с меткой Q € Г1 вида Q и v (то есть ребро Q не является первым ребром пути и, ребро Q не является первым ребром пути v в графе Г). Вершины отталкивающих ребер будем называть о-вершинами. ПРЕДЛОЖЕНИЕ 2.1 [7, 28]. Отталкивающие ребра находятся во взаимнооднозначном соответствии с вхождениями ребер Е графа Г в путь f(E). Другими словами, существует биекция вида Е f(E)=u-E-v и v Отталкивающих ребер конечное число и они находятся алгоритмически. Пусть ц — вершина в Df и /х = Е\Е2-..Ет в графе Г для некоторых ребер ЕиЕ2,...,Ет. Движением в Df назовем переход по выделенному направлению от вершины ц к вершине [Е2... Emf(Ei)]. Назовем ц-множеством линейно упорядоченное множество вершин графа D/, получающихся при движении по выделенным направлениям из вершины /. Заметим, что /t-множество конечно тогда и только тогда, когда при движении из вершины /t можно попасть в тупик или происходит зацикливание. Таким образом /i-множество имеет один из трех видов, изображенных на рис. 1. Если д-множество и т-множество пересекаются, то по определению движения, они могут отличаться лишь начальными отрезками. Тогда корректно говорить о точке пересечения как о ближайшей (в линейном порядке) к (л вершине из /^-множества, содержащейся в т-множестве. Отметим следующие свойства /j-множеств: если //о — вершина из д-множества, то /^о-множество содержится в ^-множестве; если hq — вершина из //-множества и tq — вершина из т-множества, то ^-множество пересекается с т-множеством тогда и только тогда, когда /ио-множество пересекается с то-множеством; бесконечное //-множество не может пересекаться с конечным т-множеством. Процедура построения графа С/ (1) Перечислить отталкивающие ребра. Перечислить неподвижные относительно / вершины v графа Г, им соответствуют тупики 1„. (2) Для каждой вершины /* отталкивающего ребра выяснить, конечно ли //-множество. (3) Для каждой вершины /t отталкивающего ребра с конечным /х-множеством перечислить все элементы из этого множества (они являются вершинами графа Dj) и соединяющие их по движению ребра. (4) Для каждой пары различных о-вершин у. и г таких, что /х- и г-множества бесконечны, выясить, пересекаются ли эти множества. (5) Если \ь- и r-множества в (4) пересекаются, то найти их точку пересечения, перечислить все вершины из /г-множества от /х до этой точки включительно, а также соединяющие их по движению ребра. Сделать то же самое для т. Граф С/ будет состоять из всех полученных вершин и ребер (рис. 2). Поскольку отталкивающие ребра и движение определяются алгоритмически, то осталось построить алгоритмы для пунктов (2) и (4). В статьях [7], [28] эти алгоритмы приводятся лишь в некоторых частных случаях (для неприводимых и положительных автоморфизмов). Ключевой идеей в этих статьях является использование обратного выделенного направления в графе Dj. Это направление строится алгоритмически с помощью обратной к / гомотопии. Мы не будем приводить строгое определение, нам важно лишь, что (i) это направление не совпадает с исходным выделенным направлении в вершинах вне некоторого конечного подграфа, (И) оно задает конечное множество своих отталкивающих ребер, которые молено найти алгоритмически. Вершины графа Dj вне конечного подграфа из (i) назовем нормальными. ПРЕДЛОЖЕНИЕ 2.2 [7, 28]. Пусть ц,т — две нормальные вершины графа Dj такие, что /х- и т-множества не содержат вершин отталкивающих ребер относительно обратного выделенного направления. Тогда следующие условия равносильны: (1) ^.-множество пересекается с т-множеством, (2) вершина т содержится в ц-множестве или наоборот. Итак, пункт (4) можно заменить на следующие три пункта. (4.1) Для каждой отталкивающей вершины /х с бесконечным //-множеством найти в этом множестве некоторую вершину /t0 такую, что /х0-множество не содержит вершин отталкивающих ребер относительно обратного направления. (4.2) В /io-множестве найти нормальную вершину у,\. (4.3) Для каждой пары полученных таким образом вершин /xi,Ti проверить, содержится ли Т\ в /^-множестве и наоборот. Пункт (4.2) алгоритмичен, так как бесконечность /х-множества дает возможность заменить /х0 на более далекую по движению вершину у,\ из этого множества, находящуюся вне конечного подграфа из (i). Алгоритмы для пунктов (4.1) и (4.3) являются частными случаями алгоритма для (4.4). (4.4) Для данных вершин /лиг графа D/ проверить, содержится ли вершина т в /^-множестве. Таким образом, для алгоритмического построения графа С/ достаточно указать алгоритмы для пунктов (2) и (4.4). § 3. Определение и свойства отображения / Пусть Г — конечный граф, / : Г -* Г — гомотопическая эквивалентность, отображающая вершины графа Г в вершины и /\|г\г° локально инъективно. Пусть /л (не обязательно приведенный) /-путь в графе Г, то есть его начальная вершина под действием / переходит в его конечную вершину. Пусть /л = Q1Q2. ¦ .Qa — представление пути ц в виде конкатенации ребер графа Г. Тогда определен путь Q2-"Qaf{Qi)- Обозначим этот путь через /(/л) и положим / '(/л) = /(/ 1~1(ц)) для / ^ 1. Будем называть jl-множеством линейно упорядоченное множество вершин №ШиТЧ»)},•-•} графа Dj. Напомним, что через [[л] обозначается приведенный путь в графе Г, гомотопный пути //.Так как начальная и конечная вершины путей /х и [/л] совпадают, то [/л] тоже /-путь. Напомним, что вершинами графа Dj являются приведенные /-пути, причем если [fjb] = EiE2-..Ek — представление пути [ц] в виде конкатенации ребер графа Г, то следующая по движению за [/л] вершина графа Df равна [Е2 ... Ekf(Ei)]. В § 2 для вершины [/л] графа D/ определялось [^-множество как линейно упорядоченное множество вершин графа D/, получающихся при движении по выделенным направлениям из вершины [//]. Отметим, что [/х]-множество в общем случае не совпадает с Д-множеством. Например, вершина [/(/^)] может не быть следующей по движению за вершиной [/г], если Qi ф Е\. ПРЕДЛОЖЕНИЕ 3.1. Если /х — f-путь (не обязательно приведенный) и [/л] = Ei... Ек, то существует такое 1 ^t ^1((л), что [Е2... Ekf{E{)] = [f (fi)\. ДОКАЗАТЕЛЬСТВО. В случае, когда /х ==-~ЁЕ\ц], где Е е Г1, выполнено равенство / 3(//) = E2...Ekf(E)f(E)f(El) и тогда [/3(/х)] = [E2...Ekf(Ex)]. Рассмотрим теперь общий случай: ц = T\H\r2^.. .Ts/xars+i, где все пути т гомотопны тождественному и [/л] = цг - (л2 •... • //,. Тогда [/'(ti)+1(m)] = \Ег ¦ -- Ек/(Ег)]. ? ПРЕДЛОЖ!ЕНИЕ 3.2. Пусть р. — f-путь. Тогда выполнены следующие утверждения. (1) Для любого s существует t такое, что /3(/л) = / (ju). (2) Если f$(n) = о\о2, то существует t такое, что cr2f{o-\) = / (/х). (3) Для всякого t существует s и такое представление /5(/х) = О\О2, что ДОКАЗАТЕЛЬСТВО. Утверждение (1) следует индукцией по s, при s = 1 надо положить t = 1(/л). Докажем (2). По (1) имеем /(//) = / г(/х) для некоторого г. Тогда ^2/(^1) = /г+'^<Т1^(а) и можно положить t = г + l( Докажем утверждение (3) индукцией по 5. Если s ^ 1((л), то / (/«) = cr2f(cri), где ц = G\cr2 и 1{р\) = s. В этом случае молено положить t = 0. Если s > 1{/л)., то / (/х) = / '-'С1) (/(//)) и можно применить индукционное предположение к пути /(/л) вместо (л. D ПРЕДЛОЖЕНИЕ 3.3. Пусть /х — f-путь. Тогда выполнены следующие утверждения. (1) \у]-множество содержится в fl-множестве. Вообще говоря, jx-множество может содержать и некоторые другие вершины графа D/. (2) Для любого i ^ 0 положим Дг = /(/ (/)). Тогда среди вершин [/ (а)]г [/ +1(и)]г •••» [/ +Л(/)] найдется хотя бы одна из {^-множества. (3) Пусть существует сколь угодно большое г и для него сколь угодно большое j такие, что / (д) = / '(/х). Тогда [^-множество конечно. (4) Для любой вершины т, входящей в ^-множество, г-множество содержится в fi-множестве. ДОКАЗАТЕЛЬСТВО. Утверждение (1) следует из предложения 3.1. Доказательство утверждения (2) проведем индукцией по г. Заметим предварительно, что Д(» + 1) ^ Д()> так как / не отображает ребра графа Г в вершины в силу локальной инъективности /\|г\г°- При г = 0 утверждение (2) выполняется, так как [ц] лежит в [д]-множестве. Пусть г — произвольное натуральное число и предположим по индукции, что в множестве {[/'(//)],[/'+1(д)],...,[/+А(/)]} найдется вершина из [/^-множества. Предположим, что в множестве {[/ +1(а0]> [/ +2(/)], •-., [/ \|+1+А(1+1)(д)]} нет вершин из [//[-множества. Так как Д(» + 1) ^ Дг, то из этого следует, что вершина [/ (?)] лежит в [//]-множестве. Применим предложение 3.1 к /-пути / (/х). Тогда следующая вершина по движению за вершиной [/ (//)] имеет вид [/ i+t{fj)], где 1 < t < l(f (а«)) = Дг. Противоречие. Докажем (3). Предположим, что [/х]-множество бесконечно. Тогда вершины этого множества можно занумеровать натуральными числами так, что (п+1)-я вершина получается из n-й движением по предпочтительному направлению вдоль некоторого ребра. Эти вершины и ребра образуют бесконечный луч. Каждая компонента графа Df имеет конечно порожденную фундаментальную группу. Поэтому в той компоненте, где идет этот луч, имеется конечный подграф, дополнением к которому является конечное множество деревьев. Наш луч, начиная с некоторого момента, идет в одном из этих деревьев Т на бесконечность. По пункту (1) начальная вершина этого подлуча имеет вид [/ от(д)] для некоторого т. Если мы заменим /* на / m(fj), to условие пункта (3) сохранится. Поэтому далее считаем, что [^-множество образует луч, который идет в дереве Т на бесконечность. Вершины Д-множества и соединяющие их ребра тоже образуют бесконечное дерево (см. рис. 3), лежащее в Т\ Его "корень" — вершина [/л], "ствол" — вершины [/х]-множества и соединяющие их ребра. Движение по стволу от корня является движением по предпочтительным направлениям- Опишем "ветки" этого дерева. Пусть [а] — произвольная вершина на стволе этого дерева. По пункту (1) имеем [а] = [/ (//)] для некоторого t. Пусть / г([л) = т\о~\Тго-ъ. ¦ • тао~ата+хг где все пути т гомотопны тождественному и [/ (//)] = <7i •. -. • сг,. Если путь т\ вырожден, то следующая за [/ (/х)] вершина из /J-множества [/ t+1(/)] лежит на стволе на одно ребро дальше от [а]. Предположим, что путь Т\ невырожден, т.е. Т\ = EiE2...Ek, где к ^ 1. Тогда вершина [/ +1(д)] лежит не на стволе, а на ветке, выходящей из [а]. Вершинами этой ветки являются [/(д)], [/ t+1(/u)],..., [/ t+k(y)], причем первая и последняя вершины совпадают с [<т], а при обходе этой ветки на ее ребрах будут читаться метки Е\,Е2,...,Ек. Следующая вершина из Д-множестваравна [/ ++1(/)] и расположена на одно ребро дальше по стволу. Заметим, что к ^ At = l(f l(fj))- Поэтому любые две вершины [/ (/)] и [/ J(/)] из /-множества при j—i> Дг лежат на разных ветках и, следовательно, не совпадают. Противоречие с условием.

Список литературы

Цена, в рублях: (при оплате в другой валюте, пересчет по курсу центрального банка на день оплаты)	1425

Скачать бесплатно	23532.doc

Найти готовую работу

ЗАКАЗАТЬ

Обратная связь:

Связаться

Вход для партнеров

Регистрация

Восстановить доступ

Материал для курсовых и дипломных работ

03.11.24 Лексикографический анализ единиц поля

03.11.24 Из истории слова гость и его производных

03.11.24 Семантическое поле гость в русском языке

Архив материала для курсовых и дипломных работ

Ссылки:

Счетчики:

© 2006-2024. Все права защищены.
Выполнение уникальных качественных работ - от эссе и реферата до диссертации. Заказ готовых, сдававшихся ранее работ.