Группа неподвижных точек автоморфизма свободной группы тема автореферата и диссертации по математике, 01.01.06 ВАК РФ

На правах рукописи УДК 512.54

Маслакова Ольга Сергеевна

ГРУППА НЕПОДВИЖНЫХ ТОЧЕК АВТОМОРФИЗМА СВОБОДНОЙ ГРУППЫ

01.01.06 — математическая логика, алгебра и теория чисел

Автореферат

диссертации на соискание учёной степени кандидата физико-математических наук

Новосибирск-2004

Работа выполнена в Институте математики им. С. Л. Соболева СО РАН.

Научный руководитель:

доктор физико-математических наук, доцент Богопольский Олег Владимирович

Официальные оппоненты:

доктор физико-математических наук, профессор Губа Виктор Сергеевич

Защита состоится 3 июня 2004 г. в 14 ч. 00 мин. на заседании специализированного совета К 217.174.01 Новосибирского государственного университета по адресу: 630090, Новосибирск-90, ул. Пирогова, 2.

С диссертацией можно ознакомиться в библиотеке Новосибирского государственного университета.

Автореферат разослан " " апреля 2004 г. Ученый секретарь

диссертационного совета К 212.174.01 кандидат физико-математических наук

кандидат физико-математических наук, Нещадим Михаил Владимирович

Ведущая организация:

Омский государственный университет

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы. Для автоморфизма а свободнойгруп-пы 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(ar) конечно порождена для любого автоморфизма а свободной группы F. Томас [27] обобщил этот результат для произвольного множества автоморфизмов S. В 1992 году Бествина и Хендел [4] ввели понятие относительного трейн-трека, при помощи которого доказали гипотезу Скотта для произвольного автоморфизма а группы F. Другие доказательства [13, 14, 21, 25] получены с помощью действий групп на деревьях. Имрихом и Тернером [18] было показано, что гипотеза Скотта выполняется и для произвольного эндоморфизма группы F. Дике и Вентура [9] на основе работы [4] доказали, что ранг группы Fix(5) не превосходит ранга F для множества S инъек-тивных эндоморфизмов группы F. Бергман [2] показал, что такое же неравенство выполняется для произвольного множества S эндоморфизмов группы F. С использованием техники трейн-треков Коллинз и Тернер полностью описали автоморфизмы, у которых группа неподвижных имеет максимальный возможный ранг. В частности, все они полиномиального роста.

С развитием компьютерных вычислений всё большую актуальность приобретают алгоритмические аспекты в теории групп. В последнее время в области комбинаторной теории групп появилось много алгоритмов, иногда весьма громоздких, но с развитием компьютерных исследований даже эти алгоритмы становятся

реальными; В работе Коэна и Люстига[7] приводится алгоритм вычисления базиса РЬс(а) для положительных автоморфизмов а группы Т7, то есть таких, что для некоторого базиса ж1,...,ж„ группы Е приведенные слова 0(11),... ,а(хп) состоят только из положительных степеней х,..., хп. Используя работу [7], Тернер [28] указал алгоритм, позволяющий вычислять базис группы гомотопических классов петель в графе Г, неподвижных относительно трейн-трека /. При этом предполагается, что базисная вершина V неподвижна относительно /. Таким образом, работа Тернера позволяет вычислять базис РЬс(а) для автоморфизма а, который можно топологически представить трейн-треком. На основе техники относительных трейн-треков и с использованием техники работ [б, 7, 28] в данной диссертации строится алгоритм нахождения базиса группы неподвижных точек для произвольного автоморфизма свободной группы конечного ранга. Однако, в отличие от работ [7, 28], оценка на число шагов алгоритма не получена.

Знаменитая теорема Громова утверждает, что только почти нильпотентные группы в классе конечно порождённых групп имеют полиномиальный рост, и характеризует этот класс групп их асимптотической геометрией. Тогда возник вопрос насколько асимптотические характеристики конечно порождённой группы влияют на её алгебраическую структуру. Это дало толчок в изучении асимптотических свойств групп, и их классификации с точностью до квазиизометрий. Фарб и Мошер [11, 12] в важном частном случае установили критерий квазиизометричности групп расширений абелевой посредством циклической в терминах абсолютной жордановой формы. Поскольку предложенный критерий достаточно прост, то возникает вопрос о его алгоритмической проверке. В данной диссертации построен алгоритм для проверки этого критерия.

Цель работы. Работа посвящена построению алгоритма нахождения базиса группы неподвижных точек автоморфизма свободной группы конечного ранга и проверке квазиизометрично-

сти неполициклических расширений абелевых групп посредством циклической.

Основные результаты диссертации. Основными результатами работы являются следующие:

1. Построен алгоритм нахождения базиса группы неподвижных точек автоморфизма свободной группы конечного ранга.

2. Построен алгоритм проверки квазиизометричности неполи-циклических расширений абелевых групп посредством циклической.

Методы исследования. В диссертации используются методы теории трейн-треков, развитые в работах [3,4], и методы работ

[7, 28].

Научная новизна работы. Все результаты диссертационной работы являются новыми и снабжены доказательствами.

Теоретическая и практическая ценность. Работа носит теоретический характер. Ее методы и результаты могут быть полезны специалистам в области комбинаторной теории групп.

Апробация результатов работы. Результаты диссертации были представлены на XXXVII Международной научной студенческой конференции "Студент и научно-технический прогресс" (Новосибирск, 1999), на IV Международной алгебраической конференции, посвященной 60-ти леЛю профессора Ю. И. Мерзлякова, (Новосибирск, .2000), на Третьей Международной алгебраической конференции на Украине (Сумы, 2001), на Международной конференции "Алгебра и её приложения" (Красноярск, 2002), а также на семинарах 'Теория групп", 'Теометрическая теория групп" Института математики СО РАН и "Алгебра и Логика" Новосибирского государственного университета.

Публикации. Все основные результаты диссертации опубликованы в работах [32]-[37].

Структура и объем работы. Диссертация состоит из введения, двух глав, разбитых на параграфы, и списка литературы. Список литературы содержит 37 наименований. Общий объем диссертации 74 страницы.

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

СОДЕРЖАНИЕ РАБОТЫ

Во введении приводится обзор работ, посвященных исследуемой теме, и формулируются результаты диссертации. Глава 1 разбита на семь параграфов, в ней построен алгоритм нахождения базиса группы неподвижных точек автоморфизма свободной группы. В § 1 приводятся основные сведения из теории трейн-треков [3, 4], на основе которых находятся число конечный связный граф Г1, гомотопическая эквивалентность }\ Гх —»• Гц., являющаяся относительным трейн-треком и обладающая некоторыми дополнительными свойствами, и вершина ь\ графа Гь неподвижная относительно Д, такие, что отображение /х индуцирует на фундаментальной группе 7Г1(Г1,«1) автоморфизм а„ (теорема 1.5).

Кроме того, в § 1 показано, что если ¥ — свободная группа конечного ранга и а — ее автоморфизм конечного порядка, то базис группы неподвижных точек автоморфизма находится алгоритмически (теорема 1.9). Это позволяет заменить автоморфизм а на некоторую его степень (следствие 1.10). В результате параграф 1 позволяет перейти от автоморфизма свободной группы конечного ранга к гомотопической эквивалентности конечного связного графа. В параграфе 1 также цитируется результат Бринкманна [б]

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

СЛЕДСТВИЕ 1.8. Пусть Г — конечный связный граф и / : Г Г — гомотопическая эквивалентность такая, что образ каждого ребра является конкатенацией несколькихребер. Тогда для любых двух путей р, г, начальные и конечные точки которых являются вершинами, в графеТможно алгоритмически определить, существует ли натуральное к такое, что /к(р) = т.

В § 2 дается описание графов ^ и С/ из работ [7, 28] для гомотопической эквивалентности / конечного связного графа таких, что /(«») = V* для выделенной вершины V* графа Г. Граф V/ бесконечен и фундаментальная группа его компоненты связности, содержащей вершину и», совпадает с

Щ/) = {[[р]]бтг1(г,^)| /(р) = р)

([1р]] обозначает гомотопический класс петлир). Граф С/ конечен, содержит вершину и» и фундаментальная группа его компоненты связности, содержащей вершину тоже совпадает с В

работах [7, 28] предлагается лишь процедура построения графа С/, то есть на каждом шаге этой процедуры нет уверенности, что построен весь граф С/. Параграфы 3, 5, б посвящены алгоритмизации этой процедуры.

В § 3 вводится отображениие / и доказываются основные свойства этого отображения. Отображение f расширяет понятие движения по предпочтительным направлениям из процедуры построения графа С/ и оказывается более удобным в техническом плане. В § 4 формулируются и доказываются некоторые свойства относительного трейн-трека. Эти свойства затем применяются в параграфах 5, 6 для доказательства следующей теоремы.

ТЕОРЕМА 6.10. Граф С/ строится алгоритмически.

В § 7 собраны основные результаты главы 1. Там доказана следующая теорема, отвечающая на вопрос (Е1) (а) из [1].

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

Пусть ¥ — свободная группа конечного ранга и а — ее автоморфизм. Для элемента и 6 Р множество {а* (и) : к 6 Щ называется а-орбитой, а множество {ги-1иа(го) : ю € .Р} — а-классом Райдемайстера элемента и. В § 7 также доказана теорема 7.2, которая показывает, что проблема вхождения в а-класс Райдемайстера алгоритмически разрешима. Пункт (2) этой теоремы отвечает на вопрос 3 из [9].

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

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

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

На основе этой теоремы получена

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

Глава 2 посвящена построению алгоритма проверки квазиизо-метричности неполициклических расширений абелевых групп посредством циклической. В § 1 этой главы приводятся необходимые теоретические сведения об оценке и разделении корней полиномов с рациональными коэффициентами [30, 31] и структуре группы единиц модуля алгебраических целых поля алгебраических чисел [22-24, 29].

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

ТЕОРЕМА [11]. Пусть Mi,M2 е Мп{Z), detMi,detM2 ф

О, ±1. Тогда группы Гд^ U Тщ квазиизометричны в том и только том случае, когда найдутся натуральные ri,r2 такие, что матрицы М£1 и М^2 имеют одинаковые абсолютные жордановы формы.

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

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

ЛИТЕРАТУРА

1. Baumslag G., Myasnikov A. G., Shpilrain V., Open problems in combinatorial group theory. Second edition, (Contemp. Math., 296), Providence, RI, Am. Math. Soc, 2002.

2. Bergman G. M., Supports of derivations, free factorizations, and ranks of fixed subgroups in free groups, (preprint, 1995, 18 pages).

3. Bestvina M., Feighn M, Handel M., The Tits alternative for Out(Fn) I: Dynamics of exponentially-growing automorphisms, Ann. Math., 151, N 2 (2000), 517-623.

4. Bestvina M., Handel M., Train tracks and automorphisms of free groups, Ann. Math. (2), 135, N 1 (1992), 1-53.

5. Bridson M., Metric spaces of non-positive curvature, Grundlehren der Mathematischen Wissenschaften, 319, Berlin: Springer, xxi, 1999.

6. Brinkmann P., Dynamics of free groups automorphisms, preprint, (2003), 40 pp.

7. Cohen M. M., Lustig M., On the dynamics and the fixed subgroup of a free group automorphism, Invent. Math., 96, N 3 (1989), 613-638.

8. Cooper D., Automorphisms of free groups have finitely generated fixed point sets, J. Algebra, 111, N 2 (1987), 453-456.

9. Dicks W., Ventura E., The group fixed by a family of injective endomorphisms of a free group (Contemp. Math., 195), Providence, RI, Am. Math: Soc, 1996.

10. Dyer J. L., Scott G. P., Periodic automorphisms of free groups, Commun, Algebra, 3, N 3 (1975) , 195-201.

11. Farb В., Mosher L., Quasi-isometric rigidity for the solvable Baumslag-Solitar groups, II, Inv. Math., 137, N 3 (1999), 273-296.

12. Farb В., Mosher L., On the asymptotic geometry of abelian-by-cyclic groups, I, Acta Math., 184, N 2 (2000), 145-202.

13. Gaboriau D., Jaeger A., Levitt G.,, Lustig M., An index for counting fixed points of automorphisms of free groups, Duke Math. J., 93, N 3 (1998), 425-452.

14. Gaboriau D., Levitt G., Lustig M., A dendrological proof of the Scott conjecture for automorphisms of free groups, Proc. Edinburgh Math. Soc. (2), 41, N 2 (1998), 325-332.

15. Gersten S. M., Fixed points of automorphisms of free groups, Adv. in Math., 64, N 1 (1987), 51-85.

16. Goldstein R. Z., Turner E. C, Fixed subgroups of homomor-phisms of free groups, Bull. London Math. Soc, 18 (1986), 468-470.

17. Goldstein R. Z., Turner E. C., Automorphisms of free groups and their fixed points, Inv. Math., 78, N 1 (1984), 1-12.

18. Imrich W., Turner E. C, Endomorphisms of free groups and their fixed points, Math. Proc. Cambridge Philos. Soc, 105 (1989), 421-422.

19. Lustig M., Structure and conjugacy for automorphisms of free groups I, II, Max-Plank-Institut fur Mathematik, 2000(130), 2001(4) (preprint, 30 pages, 28 pages).

20. Papasoglu P., An algorithm detecting hyperbolicity, Proc. of a joint DIMACS / Geometry Center workshop, Univ. of Minnesota Minneapolis, 1994, DIMACS, Prinston, NJ, USA, Providence, 1994, RI: AMS, DIMACS, Ser. Discrete Math. Theor. Comput. Sci 25, 1996, 193-200.

21. Paulin F., Actions de groupes sur les arbres, Seiminaire Bourbaki, Vol. 1995/96. Astirisque No. 241 (1997), Exp. No. 808, 3, 97-137.

22. Pohst M., Computational Algabraic Number Theory, DMV Seminar Band 21, Basel-Boston-Berlin, Birkhauser, 1993.

23. Pohst M., Zassenhaus #., Algorithmic Algebraic Number Theory, Camridge University Press, 1989.

24. Pohst M., Zassenhaus #., Weiler P., On effective computation of fundamental units I, II, Math. Сотр., 38 (1982), 275-292, 293-329.

25. Sela Z., The Nielsen-Thurston classification and automorphisms of a free group I, Duke Math. J., 84, N 2 (1996), 379-397.

26. Stallings J.R., Topology of finite graphs, Inv. Math., 71, N 3 (1983), 551-566.

27. Thomas S., Fixed points of automorphisms of finitely generated free groups, Proc. Amer. Math. Soc, 103 (1988), 333.

28. Turner E. C, Finding invisible Nielsen paths for a train tracks map, Proc. of a workshop held at Heriot-Watt Univ., Edinburg, 1993 (Lond. Math. Soc. Lect. Note Ser., 204), Cambridge, Cambridge Univ. Press., 1995, 300-313.

29. Боревич З.И., Шафаревич И.Р., Теория чисел, Москва, Наука, 1964.

30. ван дер Варден Б.Л., Алгебра, Москва, Наука, 1979.

31. Прасолов В., Многочлены, МЦНМО, 1999.

Работы автора по теме диссертации

32. Тишкина О. С, Группа неподвижных точек автоморфизма свободной группы, тезисы XXXVII Международной научной студенческой конференции "Студент и научно-технический прогресс", Математика, Новосибирск, изд. Новосибирского государственного университета, 1999, 138.

33. Тишкина О. С, Группа неподвижных точек автоморфизма свободной группы, тезисы IV Международной алгебраической конференции, посвященной 60-ти летию профессора Ю. И. Мерз-лякова, Новосибирск, 7-11 августа 2000, изд. Института математики СОРАН, 2000, 171.

34. Тишкина О. С, Группа неподвижных точек автоморфизма свободной группы, тезисы Третьей Международной алгебраической конференции в Украине, Сумы, 2-8 июля 2001, изд. Сумского государственного педагогического университета им. А. С. Макаренко, 259.

35. Маслакова О. С, Алгоритмическая проверка квазиизомет-ричности некоторых ИКК-расширений абелевых групп, тезисы Международной конференции "Алгебра и её приложения", Красноярск, 5-9 августа 2002, изд. Красноярского государственного университета, 2002, 120.

36. Маслакова О. С, Группа неподвижных точек автоморфизма свободной группы, Алгебра и Логика, 42, N 4 (2003), 422-472.

37. Маслакова О. С, Алгоритмическая проверка квазиизомет-ричности некоторых ИNN-расширений абелевых групп, Сибирский математический журнал, 44, N 1 (2003), 199-205.

Маслакова Ольга Сергеевна

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

группы

Автореферат диссертации на соискание ученой степени кандидата физико-математических наук

Подписано в печать 21.04.2004. Формат 60 х 84 1/16. Печать

офсетная.

Усл.-печ. л. 0,8. Уч.-изд. л. 0,8. Тираж 80 экз. Заказ N 26.

Отпечатано на полиграфическом участке ИМ СО РАН, пр. Академика Коптюга, 4, 630090 Новосибирск, Россия.

Р-97 5 ?

ВВЕДЕНИЕ

ГЛАВА 1. ГРУППА НЕПОДВИЖНЫХ ТОЧЕК АВТОМОРФИЗМА СВОБОДНОЙ ГРУППЫ

§ 1. Относительный трейн-трек для автоморфизма свободной группы конечного ранга.

§ 2. Конструкция графов Dj и Cf для гомотопической эквивалентности /

§ 3. Определение и свойства отображения f

§ 4. Запрещенные развороты в экспоненциальном слое.

§ 5. Свойства некоторых путей в графе Г

§ 6. Алгоритм построения графа С/

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

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

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

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

Для автоморфизма а свободной группы 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) € <Q>[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 можно определить число элементов в множестве {а*: = |ог^01,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), €\,.,£Г — основные единицы кольца ор. Предположим, что e,£0,elt. ,ег заданы алгоритмически. Тогда можно алгоритмически вычислить целые числа ко, •. •, кг такие, что е =

ДОКАЗАТЕЛЬСТВО. Оценим kQ,.,kT. Можно считать, что к0 ^ \TU(oF)\. Пусть сгх,., сга — вещественные изоморфизмы поля F. Из каждой пары сопряженных между собой комплексных изоморфизмов выберем какой-нибудь один и обозначим полученные изоморфизмы aa+i,.,сга+ь- Обозначим через логарифмическое изображение х Е F. Известно, что вектора 1(ег),.,l(er) линейно независимы и 1(e) = k\l(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 |<Te(x)|, 2In |ae+i(a:)|,., 2In ke+fc(®)|)

Nul(/)Dfo(e)|ls$i<a + 6}.

§ 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 могут быть вычислены алгоритмически. □

1. G. Baumslag, A. G. Myasnikov, V. Shpilrain, Open problems in combinatorial group theory. Second edition, (Contemp. Math., 296), Providence, R1. Am. Math. Soc., 2002.

2. G. M. Bergman, Supports of derivations, free factorizations, and ranks of fixed subgroups in free groups, (preprint, 1995, 18 pages).

3. M. Bestvina, M. Feighn, M. Handel, The Tits alternative for Out(Fn) I: Dynamics of exponentially-growing automorphisms, Ann. Math., 151, N 2 (2000), 517-623.

4. M. Bestvina, M. Handel, Train tracks and automorphisms of free groups, Ann. Math. (2), 135, N 1 (1992), 1-53.

5. M. Bridson, Metric spaces of non-positive curvature, Grundlehren der Mathema-tischen Wissenschaften, 319, Berlin: Springer, xxi, 1999.

6. P. Brinkmann, Dynamics of free groups automorphisms, preprint, (2003), 40 pp.

7. M. M. Cohen, M. Lustig, On the dynamics and the fixed subgroup of a free group automorphism, Invent. Math., 96, N 3 (1989), 613-638.

8. D. Cooper, Automorphisms of free groups have finitely generated fixed point sets, J. Algebra, 111, N 2 (1987), 453-456.

9. W. Dicks, E. Ventura, The group fixed by a family of injective endomorphisms of a free group (Contemp. Math., 195), Providence, RI, Am. Math. Soc., 1996.

10. J. L. Dyer, G. P. Scott, Periodic automorphisms of free groups, Commun. Algebra, 3, N 3 (1975) , 195-201.

11. B. Farb, L. Mosher, Quasi-isometric rigidity for the solvable Baumslag-Solitar groups, II, Inv. Math., 137, N 3 (1999), 273-296.

12. B. Farb, L. Mosher, On the asymptotic geometry of abelian-by-cyclic groups, I, Acta Math., 184, N 2 (2000), 145-202.

13. D. Gaboriau, A. Jaeger, G. Levitt, M. Lustig, An index for counting fixed points of automorphisms of free groups, Duke Math. J., 93, N 3 (1998), 425-452.

14. D. Gaboriau, G. Levitt, M. Lustig, A dendrological proof of the Scott conjecture for automorphisms of free groups, Proc. Edinburgh Math. Soc. (2), 41, N 2 (1998), 325-332.

15. S. M. Gersten, Fixed points of automorphisms of free groups, Adv. in Math., 64, N 1 (1987), 51-85.

16. R. Z. Goldstein, E. C. Turner, Fixed subgroupsofhomomorphisms of free groups, Bull. London Math. Soc., 18 (1986), 468-470.

17. R. Z. Goldstein, E. C. Turner, Automorphisms of free groups and their fixed points, Inv. Math., 78, N 1 (1984), 1-12.

18. W. Imrich, E. C. Turner, Endomorphisms of free groups and their fixed points, Math. Proc. Cambridge Philos. Soc., 105 (1989), 421-422.

19. M. Lustig, Structure and conjugacy for automorphisms of free groups I, II, Max-Plank-Institut fur Mathematik, 2000(130), 2001(4) (preprint, 30 pages, 28 pages).

20. F. Paulin, Actions de groupes sur les arbres, Seiminaire Bourbaki, Vol. 1995/96. Astirisque No. 241 (1997), Exp. No. 808, 3, 97-137.

21. M. Pohst, Computational Algabraic Number Theory, DMV Seminar Band 21, Basel-Boston-Berlin, Birkhauser, 1993.

22. M. Pohst, H. Zassenhaus, Algorithmic Algebraic Number Theory, Camridge University Press, 1989.

23. M. Pohst, H. Zassenhaus, P. Weiler, On effective computation of fundamental units I, II, Math. Сотр., 38 (1982), 275-292, 293-329.

24. Z. Sela, The Nielsen-Thurston classification and automorphisms of a free group I, Duke Math. J., 84, N 2 (1996), 379-397.

25. J.R. Stallings, Topology of finite graphs, Inv. Math., 71, N 3 (1983), 551-566.

26. S. Thomas, Fixed points of automorphisms of finitely generated free groups, Proc. Amer. Math. Soc., 103 (1988), 333.

27. E. C. Turner, Finding invisible Nielsen paths for a train tracks map, Proc. of a workshop held at Heriot-Watt Univ., Edinburg, 1993 (Lond. Math. Soc. Lect. Note Ser., 204), Cambridge, Cambridge Univ. Press., 1995, 300-313.

28. З.И. Боревич, И.Р. Шафаревич, Теория чисел, Москва, Наука, 1964.

29. Б.Л. ван дер Вардеп, Алгебра, Москва, Наука, 1979.

30. В. Прасолов, Многочлены, МЦНМО, 1999.

31. Работы автора по теме диссертации

32. О. С. Тишкина, Группа неподвижных точек автоморфизма свободной группы, тезисы IV Международной алгебраической конференции, посвящённой 60-ти летию профессора Ю. И. Мерзлякова, Новосибирск, 7-11 августа 2000, изд. Института математики СОРАН, 2000, 171.

33. О. С. Тишкина, Группа неподвижных точек автоморфизма свободной группы, тезисы Третьей Международной алгебраической конференции в Украине, Сумы, 2-8 июля 2001, изд. Сумского государственного педагогического университета им. А. С. Макаренко, 259.

34. О. С. Маслакова, Группа неподвижных точек автоморфизма свободной группы, Алгебра и Логика, 42, N 4 (2003), 422-472.

35. О. С. Маслакова, Алгоритмическая проверка квазиизометричности некоторых HNN-расширений абелевых групп, Сибирский математический журнал, 44, N 1 (2003), 199-205.