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

Для автоморфизма, а свободной группы 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 (а) конечно порождена для любого автоморфизма, а свободной группы 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) для положительных автомофизмов, а группы F, то есть таких, что для некоторого базиса Xi,., хп группы F приведенные слова a (xi),., а (хп) состоят только из положительных степеней xi,., хп.

Пусть Г — конечный связный граф. Трейн-треком называется такая гомотопическая эквивалентность /: Г —>¦ Г, что любая степень / локально инъективна на внутренности любого ребра графа Г. Используя работу [7], Тернер [28] указал алгоритм, позволяющий вычислять базис группы гомотопических классов петель в графе Г, неподвижных относительно трейн-трека /. При этом предполагается, что базисная вершина v неподвижна относительно /. Таким образом, работа Тернера позволяет вычислять базис Fix (а) для автоморфизма а, который можно топологически представить трейн-треком. Не для любого автоморфизма группы F можно построить трейн-трек, однако Бествиной и Хенделом [4] было показано, что для неприводимых автоморфизмов можно. Приводимым называется такой автоморфизм а, что существует неединичный свободный множитель группы F вида G* — * Gk и, а транзитивно переставляет классы сопряженности подгрупп Gi,., GkПри этом если G *• • •*Grfc = F, то к должно быть не меньше 2. Иначе автоморфизм, а называется неприводимым. В той же работе [4] введено понятие относительного трейн-трека. Это понятие более сложное, оно формулируется в § 1 главы 1 диссертации. На основе техники относительных трейн-треков и с использованием техники работ [6, 7, 28] в данной диссертации строится алгоритм нахождения базиса для произвольного автоморфизма, а свободной группы F. Однако, в отличие от работ [7, 28J, оценка на число шагов алгоритма не получена. Итак, в главе 1 диссертации получена следующая основная теорема 7.1, отвечающая на вопрос (F1) (а) из [1].

ТЕОРЕМА 7.1. Пусть F — свободная группа конечного ранга, а — ее автоморфизм, заданный образом некоторого фиксированного базиса. Тогда алгоритмически вычислим базис подгруппы Fix (a).

Для элемента и G F множество (afc (it): k G Z} называется а-орбитой, а множество {w~lua (u>) :wGF} — а-классом Райдемайстера элемента и. В § 1 используется также понятие а±орбиты, которая совпадает с множеством {afe (tt): k € N}. Бринк-манн в препринте [6} показал, что проблема вхождения в a-орбиту алгоритмически разрешима. В главе 1 также доказана теорема 7.2, которая показывает, что проблема вхождения в a-класс Райдемайстера тоже алгоритмически разрешима. Пункт (2) этой теоремы отвечает на вопрос 3 (i) из [9].

ТЕОРЕМА 7.2. Пусть F — свободная группа конечного ранга, а — ее автоморфизм, заданный образом некоторого фиксированного базиса. Тогда выполняются следующие утверждения.

1) Для любого слова w € F его а-класс Райдемайстера состоит из а-орбит.

2) Пусть и, v — слова в группе F. Тогда можно алгоритмически определить, принадлежит ли слово v а-классу Райдемайстера слова и.

На основе теоремы 7.2 получена теорема.

ТЕОРЕМА 7.3. Пусть F — свободная группа конечного ранга. Тогда в любом расширении группы F посредством циклической группы разрешима проблема сопряженности.

Структура главы 1 такова. В § 1 приводятся необходимые сведения из теории относительных трейн-треков Бествины, Фейна и Хенделя [3,4], а также две теоремы Бринкманна из [б] о проблеме вхождения в a-орбиту. В том же параграфе строится «хорошее» геометрическое представление некоторой фиксированной степени автоморфизма, а и выводится следствие из теоремы Бринкманна для случая гомотопической эквивалентности конечного связного графа. В § 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, dx) и (У, dy) — метрические пространства. Отображение /: X -+Y называется квазиизометприей, если существуют константы К, С, С2 такие, что.

1) ¦p^dx (xi, x2)-C2^dr (ffa), f (z2)) < Cidx{xi, x2) + C2 для всех хих2 G X;

2) if-окрестность f (X) совпадает с Y.

Пространства X и Y назывются квазиизометричными, если существует ква-зиизометрия /: X —? У. Пусть G, Н — конечно порожденные группы, da, dff — словарные метрики на G, H. Группы G и Н называются квазиизометричными, если метрические пространства ((?, da) и (Н, dg) квазиизометричны. Это определение корректно, поскольку словарные метрики, определенные различными конечными порождающими множествами, задают квазиизометричные пространства.

Пусть М.— целочисленная матрица порядка п с определителем, отличным от О, ±1, и пусть через Гм обозначено HNN-расширение группы Zn при помощи мономорфизма <рм с матрицей М. Фарб и Мошер [11] привели следующий критерий квазиизометричности групп вида Га/.

ТЕОРЕМА [11]. Пусть MUM2 е M"(Z), detMbdetM2 ф 0,±1. Тогда группы Гл^ иГМ2 квазиизометричны в том и только том случае, когда найдутся натуральные ri, r2 такие, что матрицы М[1 и имеют одинаковые абсолютные жордановы формы.

Абсолютная жорданова форма матрицы М получается из жордановой формы заменой диагональных элементов на их модули. Условие det М = ±1 эквивалентно полицикличности группы Гм (доказательство можно найти в [12]) и на данный момент критерий квазиизометричности таких групп Гм неизвестен. На основе теоремы Дирихле [29, т. 5, стр. 131] о строении группы единиц модуля алгебраических целых поля F в главе 2 получена следующая.

ТЕОРЕМА 2.5. Пусть А, В G M"(Z). Тогда можно алгоритмически проверить, существуют ли натуральные k, т такие, что абсолютные жордановы формы матриц Ак и В1 совпадают. В частности, существует алгоритм проверки квазиизометричности групп Гд^ и Гм2 пРи det М, det М2 ф 0, ±1.

Результаты главы 2 докладывались на семинарах «Алгебра и Логика» Новосибирского государственного университета, «Теория групп» и «Геометрическая теория групп» Института математики СО РАН, а также на конференции в Красноярске в 2002 г. [35]. Эти результаты опубликованы в [37].

Автор благодарит своего научного руководителя д.ф.-м.н. Олега Владимировича Богопольского за внимание и помощь, оказанные в работе.

§ 7. Основные результаты.

ТЕОРЕМА 7.1. Пусть F — свободная группа конечного ранга, а — ее автоморфизм, заданный образом некоторого фиксированного базиса. Тогда алгоритмически вычислим базис подгруппы Fix (a).

ДОКАЗАТЕЛЬСТВО. В силу теоремы 1.5 можно найти число п, граф Г, вершину г/", изоморфизм j: F —t 714(Г, г/*) и относительный трейн-трек /: Г —> Г такие, что Fix (an) = j~x (Fix (/)). В § 2 показано, что для вычисления базиса группы Fix (/) достаточно построить граф С/. По теореме 6.10 граф С/ строится алгоритмически. Таким образом, базис группы Fix (an) ищется алгоритмически. Но тогда по следствию 1.10 базис группы Fix (а) также ищется алгоритмически. ?

ТЕОРЕМА 7.2. Пусть F — свободная группа конечного ранга, а — ее автоморфизм, заданный образом некоторого фиксированного базиса. Тогда выполняются следующие утверждения.

1) Для любого слова w? F его а-класс Райдемайстера состоит из а-орбит.

2) Пусть и, v — слова в группе F. Тогда можно алгоритмически определить, принадлежит ли слово v а-классу Райдемайстера слова и.

ДОКАЗАТЕЛЬСТВО. Докажем (1). Пусть v = иа" для некоторого k? Z. Положим w = ииа .иа ~. Легко проверить, что v — w~1uwa. Следовательно, слова и, v входят в один a-класс Райдемайстера и (1) доказано.

Докажем (2). Принадлежность и и v одному и тому же классу Райдемайстера означает, что существует w € F такое, что w~xuwa — v. Это равенство равносильно равенству u>~lw^ = vu~l, где /3 — автоморфизм F, действующий по правилу = ихаи~х, где х? F. Положим Н = F * (а |) и пусть 7 — автоморфизм группы Н, продолжающий /3 и действующий на, а по правилу a7 = a (vu-1). Тогда w~lwp = vu~x О w~xwp = a~la7 w7(a-1)7 = wa~x wa~x E Fix (7).

Поэтому v лежит в a-классе Райдемайстера слова и тогда и только тогда, когда найдется такое w € F, что wa~x € Fix (7).

Пусть at,., a" — базис F и пусть — граф с одной вершиной * и с п +1 ориентированными ребрами, помеченными ai,., an, a. Тогда Н естественным образом отождествляется с 7Ti (!R, *). Пусть ср: —> (32, *) — накрытие, соответствующее подгруппе Fix (7). Считаем, что ребра графа Q помечены теми метками, которыми помечены их образы относительно ср. Метка пути — это произведение меток ребер, из которых этот путь состоит. Для слова h = h (a,., a", a) G H определим Ph как путь в графе О, выходящий из вершины и) и имеющий метку h (a,., ап, а).

Пусть С — ядро графа fi, содержащее вершину и. По теореме 7.1 можно алгоритмически найти базис группы Fix (7). Отсюда по работе [26, § 7] алгоритмически строится С. Пусть С — подграф графа П, полученный из С присоединением ребра с меткой а, выходящего из из, и его конечной вершины t. Для w G F справедливо wa~x € Fix (7) тогда и только тогда, когда pw — путь в С с конечной вершиной t. Таким образом, вопрос сводится к отысканию в С пути р, соединяющего вершины из и t, метка которого есть слово от а,., ап. Если такой путь существует, то существует путь с тем же свойством, длина которого не превосходит числа ребер в С. Следовательно, задача решается перебором. ?

ТЕОРЕМА 7.3. Пусть F — свободная группа конечного ранга. Тогда в любом расширении группы F посредством циклической группы разрешима проблема сопряженности.

ДОКАЗАТЕЛЬСТВО. Если G — нерасщепляемое расширение F посредством циклической группы, то индекс F в G конечен и, значит, G — гиперболическая группа. Известно, что проблема сопряженности в гиперболической группе алгоритмически разрешима (см., например, [5]).

Поэтому считаем, что G — расщепляемое расширение группы F посредством циклической группы (а). Тогда сопряжение группы F элементом, а задает некоторый автоморфизм F. Обозначим fa = а/а-1 для / е F. Пусть (иа5) и (vak), где u, v G F, s, k € Z, — два элемента в G, сопряженность которых мы хотим выяснить. Если эти элементы сопряжены в G, то с помощью канонического гомоморфизма G —> (а) легко вывести что s = к. Поэтому считаем далее, что s = к.

Предположим, что к = 0. Элементы и иг" сопряжены в G тогда и только тогда, когда существуют м е F и j e Z с условием v = (wctf)u (wai)~1, что равносильно и" 1 — w~xvw. По теореме 1.7 (2) проблема существования таких wnj алгоритмически разрешима.

Пусть теперь к ф 0. Докажем, что элементы иак и vak сопряжены в группе G тогда и только тогда, когда найдется такое 0 ^ г < |А-|, что слова var и и лежат в одном ак-классе Райдемайстера. Тогда проблема сопряженности этих элементов будет разрешима по теореме 7.2 (2).

Предположим, что элементы uak и vak сопряжены в G, то есть для некоторых w? F и г е Z выполнено uak = (wac%)vak (wa*)~1, что эквивалентно w~luwa = va'. Пусть г = kq+r, где 0 ^ г < k, q е Z. Положим wq = tt/(v—1)t** (¦и-1)" '-2*. (и1)а* Тогда Wq1uujq = vaT, значит, слова vaT и и лежат в одном а*-классе Райдемайстера.

Наоборот, предположим, что некоторого 0 ^ г < слова var и и лежат в одном а^-классе Райдемайстера. Тогда w~luwa = vaT для некоторого w е F. Отсюда следует, что uak = (war)vak (war)~1, то есть элементы иак и vak сопряжены в G. ?

ГЛАВА 2. АЛГОРИТМИЧЕСКАЯ ПРОВЕРКА КВАЗИИЗОМЕТРИЧНОСТИ НЕКОТОРЫХ РАСШИРЕНИЙ АБЕЛЕВЫХ ГРУПП ПОСРЕДСТВОМ.

ЦИКЛИЧЕСКОЙ.

§ 1. Предварительные сведения.

В этом параграфе приводятся необходимые сведения об оценке корней полиномов с рациональными коэффициентами и о группе единиц. Через Nul (/) обозначается множество корней многочлена f (t). Несложно получить оценки корней многочлена в следующем виде.

ПРЕДЛОЖЕНИЕ 1.1. Пусть f (t) = antn Н——— ait + а0 G R[t]. Выполнены следующие утверждения.

1) Для любого корня, а многочлена f (t) выполнено.

Ы ^ А, где, А = т-^-г max |а*| + 1.

1 1 lanlo^n-i1 11.

2) Если оо ф 0, то для любого корня, а многочлена f (t) выполнено ¦ а| ^ 1/(1 + В), где В = -рЦ max Ы 4- 1.

3) Для любых корней c*i ф многочлена f (t) выполнено где d (f) — дискриминант многочлена /.

Поскольку дискриминант многочлена вычисляется через его коэффициенты, то приведенные оценки находятся алгоритмически.

ПРЕДЛОЖЕНИЕ 1.2 [31]. Для произвольного многочлена /(f) € Q[t] алгоритмически вычисляются п.

1) многочлены fi (t) € [t], г = 1,., п, такие, что f (t) — /,-(?)* и корнями t=i многочлена fi (t) являются все корни многочлена f (t) кратности iв частности, п многочлен JJ/t (i) € Q[t] не имеет кратных корней- «=i.

2) взаимно простые неприводимые многочлены Fj (t) € Q[i], j = l,., m, тага кие, что f (t) = Д Fjffl*. i=i.

ПРЕДЛОЖЕНИЕ 1.3. Для произвольного многочлена f (t) € Q[?] можно алгоритмически построить многочлен g (t) € Q[f] без кратных корней такой, что Ш (д) Э {|i|2: t € Nul (/)}..

С помощью теоремы Штурма можно алгоритмически разделить вещественные корни многочлена без кратных корней с вещественными коэффициентами. Кронекер доказал, что можно алгоритмически указать набор кругов на комплексной плоскости, каждый из которых содержит единственный корень комплексного многочлена без кратных корней, [31]. Следующее предложение вытекает из комбинации этих алгоритмов с использованием предложения 1.3..

ПРЕДЛОЖЕНИЕ 1.4. Пусть f (t) — произвольный многочлен из Q[i] и «и., ап — его корни. Тогда по коэффициентам многочлена f (t) можно алгоритмически указать центры Z,., zn и радиусы ri,., rn замкнутых кругов Кп на комплексной плоскости таких, что для всех i, j:.

1) € Ki-.

2) если cii ф otj, то Ki Kj = 0-.

3) если a, = cij, то Щ = Kj-.

4) если |aj|2 Ф |c*j|2, то интервалы (Ы-г,)2,(Ы + г<)2 ] «[ (|^|-г,)2,(|г,|+г,)2 I не пересекаются..

ДОКАЗАТЕЛЬСТВО. По теореме Штурма локализуем вещественные неотрицательные корни многочлена g{t) из предложения 1.3 в попарно непересекающихся интервалах/х,.,/т. По предложению 1.2 (1) построим многочлен /i (t) без кратных корней с Nul (/i) = Nul (/) = {c*i,., с*.,}. Для многочлена fi (t) методом Крюнекера построим круги Ki,., Ka, удовлетворяющие условиям (1) — (2) такие, что для каждого Ki существует Э |—r^)2, (|zj | +rj)2]. Тогда для кругов К,., К, выполнено условие (4). Произвольный корень, а многочлена f (t) совпадает с одним из корней ctj, j = 1,., s. По предложению 1.2 можно размножить все круги Kj, j = 1,., s в нужном количестве. ?.

ЗАМЕЧАНИЕ 1.5. Для данного круга Kio в силу условия (4) и предложения 1.2 можно определить число элементов в множестве {а*: = |ог⁰¹, i = 1,., п}..

Будем говорить, что корень, а многочлена f (t) задается кругом Ка, если Nul (/) Р] Ка = {а}. Дальнейшие формулировки и определения можно найти в книге [29]. Пусть F — поле алгебраических чисел, оно может быть получено присоединением к Q примитивного элемента в, являющегося корнем неприводимого многочлена h (t) G Q[t] со старшим коэффициентом равным 1. Пусть, а — число вещественных, 2Ь — число комплексных невещественных корней многочлена h (t), тп = deg (/i) = a + -Ь 26. Пусть of — множество алгебраических целых поля F = Q (0). Известно, что кольцо Ор является свободным Z-модулем ранга т..

ЗАМЕЧАНИЕ 1.6. Пусть, А е Mn (Z). Тогда для любого, а G Бр (Л) числа, а и |с*|2 являются алгебраическими целыми..

Число, а G F назовём вычислимым алгоритмически, если существует алгоритм нахождения рациональных коэффициентов в разложении, а по степеням в. В книге [23] приведен алгоритм нахождения Z-базиса модуля алгебраических целых. Пусть {а-ь. ., и>т} — Q-базис F. Тогда для любого a G F линейный оператор.

Ла: х —)• ах задаёт матрицу Ма € Mm (Q) в этом базисе. Обозначим через N (a) норму а. Напомним, что N (a) = det Ма € Q..

ЗАМЕЧАНИЕ 1.7. Если базис {cji, ., и число, а вычислимы алгоримиче-ски, то матрица Ма и норма, а вычисляются алгоритмически..

Группа единиц11(ор) состоит из всех обратимых по умножению элементов кольца ofЧисло, а? о? попадает в группу единиц тогда и только тогда, когда |iV (a)| = 1. Подгруппа TU (op) ^ U (op) единиц кручения состоит из всех корней из 1, попадающих в OfТеорема Дирихле описывает строение группы единиц..

ТЕОРЕМА (Дирихле) 1.8 [29, т. 5, стр. 131]. Группа единиц модуля Of поля F является прямым произведением своей (циклической) подгруппы TU (ор) порядка mur = a + b — 1 бесконечных циклических подгрупп, порожденных основными единицами £х,., еГ € of.

Метод алгоритмического вычисления основных единиц и группы TU (op) приведен, например, в работе [24]..

ПРЕДЛОЖЕНИЕ 1.9. Пусть ее U (oF), е0 — порождающий группы TU (oF), &euro-,.,£Г — основные единицы кольца ор. Предположим, что e,?0,elt., ег заданы алгоритмически. Тогда можно алгоритмически вычислить целые числа ко, •. •, кг такие, что е =.

ДОКАЗАТЕЛЬСТВО. Оценим kQ,., kT. Можно считать, что к0 ^ TU (oF). Пусть сгх,., сга — вещественные изоморфизмы поля F. Из каждой пары сопряженных между собой комплексных изоморфизмов выберем какой-нибудь один и обозначим полученные изоморфизмы aa+i,., сга+ьОбозначим через логарифмическое изображение х Е F. Известно, что вектора 1(ег),., l (er) линейно независимы и 1(e) = kl (ei) + • • • + кТ1(еТ). Тогда для всех 1 ^ j ^ г выполнено неравенство где G — матрица Грама системы l (e), ., 1(ег). В книге [22] приведена нижняя оценка для определителя матрицы G, поэтому достаточно показать, как оценить |/(е)|, |Z (ei)|,., l (er) сверху. Покажем, как это сделать для 1(е). Для |Z (?i)|,. -., К (?г)| оценка получается аналогично. Поскольку е вычислимо алгоритмически и известен минимальный многочлен для в, то можно построить многочлен f (t) G Q[<] такой, что.

Тогда по предложению 1.1 алгоритмически вычислима константа Со такая, что In <Т{(£) ^ ^ Со для всех г. Отсюда |Z (e)| ^ Сол/a + 46. В итоге для всех 1 ^ j ^ г можно найти константу С такую, что ^ С. Осталось перебрать конечное число произведений вида. -£кг для ко ^ TU (op), kj ^ С и сравнить их с е. ?.

U (oF) = TU (oF) х (ex) х. х (er> Cm x Zr. m l (x) = (In |<7i (x)|,., In |.

Nul (/)Dfo (e)|ls$i

§ 2. Доказательство теоремы 2.5.

Обозначим через Q/ расширение Q с помощью корня неприводимого многочлена /. Следующее предложение позволяет по оценке корней си, (3 многочленов f (t), g (t) построить минимальный многочлен для примитивного элемента 7 расширения Q (7) = Q (a, /3)..

ПРЕДЛОЖЕНИЕ 2.1. Пусть f (t), g (t) G Q[t] — неприводимые многочлены, се и (3 — их корни, заданные кругами Ка, Кр. Тогда можно алгоритмически вычислить неприводимый многочлен h (t) G Z[t] со старшим коэффициентом 1 такой, что для некоторого его корня 7 выполнено Q (a, /3) = Q (7). Также можно алгоритмически вычислить многочлены ha (t), hp (t) € Q[f] такие, что, а = ha (j), /3 — hp (7)..

ДОКАЗАТЕЛЬСТВО. По теореме о примитивном элементе [30, § 46] можно положить 9 = а'. + с/3 для произвольного с? Х = ': «г Ф «2 6 Nnl (/), A фр2е Nulfo)} ..

В качестве с можно взять любое натуральное число, большее тах|а:|, используя оценки предложения 1.1. Положим d = deg (/) deg (p) и пусть v — d-мерный векторьстолбец с координатами vitj = а'/Р, 0 < i < deg (/), 0 < j < degfo)..

Так как 1, a,., ade8(/)-i и 1, /3,., ^st")-1 — Q-базисы расширений Qf nQg, то по коэффициентам многочленов / и g можно вычислить матрицу М € Md (Q) такую, что (a + c/3)v = Mv. Значит, 9 = ае + с (3 — корень характеристического многочлена Хм матрицы М с рациональными коэффициентами. Разлагая по предложению 1.2 многочлен хм на неприводимые множители и оценивая корни а, (3 (а, следовательно, и 9) с необходимой точностью, можно найти неприводимый многочлен h (t) G Z[t], корнем которого является 9. Пусть к — старший коэффициент h (t). Положим h (t) = k^hit/k) и 7 = кв..

Многочлены g (t) и f (9 — ct) имеют единственный общий корень f3, поэтому t — (3 — нод (<7(<), f (9 — ct)). С другой стороны, g (t), f{9 — ct)? Q (0)[i], и по алгоритму Евклида коэффициенты нод (</(4), f (9—ct)) можно выразить через коэффициенты g (t) и f (9 — ct). Так мы получим выражение f3 в виде многочлена от 9 с коэффициентами из Q, по которому можно построить многочлен hp. Положим ha (t) = t/k — chp (t). ?.

ПРЕДЛОЖЕНИЕ 2.2. Пусть, А € Mn (Z), а — характеристическое число матрицы А, заданное кругом Ка. Тогда ранг матрицы (А — аЕ)3 вычисляется алгоритмически (с помощью метода окаймления миноров) для любого натурального j..

ПРЕДЛОЖЕНИЕ 2.3. Пусть f (t), g (t) € ОД, a G Nul (/), Р € Nul (g) заданы кругами Ка, Кр, числа а,(3 > 0 — алгебраические целые. Тогда можно алгоритмически проверить, существуют ли такие натуральные к, тп, что ак = /Зт, и найти такие к, т, если они существуют..

ДОКАЗАТЕЛЬСТВО. Рассмотрим расширение Q (a,/3) = Q (9), построенное в предложении 2.1. По замечанию 1.7 можно вычислить нормы а,/3 в расширении Q (0). Необходимым условием равенства ак и /Зт является N (a)k = N (f3)m..

Поскольку N (a), N (P) Е Q, то можно выяснить, существуют ли натуральные p, q такие, что N (a)p = N (/3)q. Предположим, существуют. Возьмем некоторые. Тогда N (ap) = N ((3q). Заметим, что вместо a, J3 можно рассматривать ар, /3я и в дальнейшем считать, что N (a) = N (0). Рассмотрим возможные случаи..

1. |-/V (a)| = |N (, 5)| Ф 1. Если ак = /?т для некоторых к и ш, то к = т. Отсюда, а = ft т. к. по условию а, (3 > 0..

2. |iV (a)| = |iV (/?)| = 1. В этом случае, а и fi являются единицами модуля Of и могут быть представлены как произведение основных единиц: а = Eq0. ejr и Р = Cq. .elT с целыми показателями. Эти показатели можно вычислить алгоритмически по предложению 1.9. Используя теорему 1.8, можно найти натуральные к, т (если они существуют) такие, что ак = ft71. ?.

ПРЕДЛОЖЕНИЕ 2.4. Пусть aj, ft (1 ^ г ^ s) — вещественные положительные числа, не равные 1. Предположим, что ак< = ft™' для некоторых натуральных ki, mi таких, что нод (ki, rrii) = 1, i = 1,., s. Тогда существуют натуральные k, т такие, что ак = /3™ если и только если ki — • • • = ks и т = • • • — т3..

ТЕОРЕМА 2.5. Пусть А, В G Mn (Z). Тогда можно алгоритмически проверить, существуют ли натуральные к, тп такие, что абсолютные жордановы формы матриц Ак и Вт совпадают. Следовательно, существует алгоритм проверки квазиизометричности групп ГМ1 и Гм2 при det Mi, det М2 ф 0, ±1..

ДОКАЗАТЕЛЬСТВО. Пусть Sp (A) = {аи., ап}, Sp (B) = {ft,., ft,} с учё.

УЧ том кратности, и = |а"|, ft = |ft |2. Пусть Кг,., Кп и Lb ., Ln — круги, удовлетворяющие условиям предложения 1.4 для характеристических многочленов матриц А, В соответственно..

Если искомые k, т существуют и матрицы имеют нулевые собственные значения, то (увеличив к, т в несколько раз) можно считать, что все жордановы клетки с нулём на диагонали имеют порядок один. Поэтому в дальнейшем предполагаем, что 0 ^ Sp (A) U Sp (В). Так как при возведении в степень таких матриц структура жордановых клеток не меняется, необходимые и достаточные условия существования степеней к, т таковы: а) модули собственных значений в некоторой степени совпадают: существуют подстановка, а Е Sn и числа к, т Е Z>0 такие, что для любого г.

Ык = lft (0lmб) совпадает структура клеток в абсолютной жордановой форме: для к, т найденных в предыдущем пункте, при всех io, j должно выполняться равенство ь где Sq (j) — число жордановых клеток порядка j с числом у на диагонали в жордановой форме матрицы С..

Сложность проверки условия (а) заключается в том, что собственные числа матриц неизвестны. По предложению 1.3 можно построить многочлены f (t), g (t) такие, что f (6ti) = g (Pi) = 0 для всех i. л".

Фиксируем, а Е Sn. Так как по замечанию 1.6 числа щ, ft алгебраические целые, то для каждой пары ai, ft (j) можно применять предложение 2.3 для отыскания чисел ki, nii € Z>° таких, что а^ =. Чтобы условие (а) выполнялось при данном сг, по предложению 2.4 необходимо и достаточно, чтобы к =••• — кп и Щ — — = тпп. Таким образом, проверка условия (а) может быть выполнена алгоритмически, и, в случае успеха, позволит определить кит. Условие (б) также проверяется алгоритмически. В силу замечания 1.5 множество {г: щ = а^, г = 1,., го} перечисляется алгоритмически. Числа выражаются через ранги матриц (С — 7Е) е и, следовательно, по предложению 2.2 могут быть вычислены алгоритмически. ?.