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

МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ имени М. В. ЛОМОНОСОВА

Механико-математический факультет

:Т5 О Л

На правах рукописи

V ° ¡и/

УДК 512

ГУБА Виктор Сергеевич

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

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

АВТОРЕФЕРАТ диссертации на соискание ученой степени доктора физико-математических наук.

Москва 1996

Работа выполнена на кафедре алгебры и геометрии Вологодского государственного педагогического университета.

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

доктор физико-математических наук, профессор Р. И. Григорчук доктор физико-математических наук, профессор А. Л. Шмелькин доктор физико-математических наук, профессор Л. Н. Шеврин

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

Математический Институт им. В. А. Стеклова РАН.

Защита диссертации состоится 1997 г. в 16 ч. 05 мин.

на заседании диссертационного совета Д.053.05.05 при Московском государственном университете имени М.В.Ломоносова по адресу: 119899, ГСП, Москва, Воробьевы горы, МГУ, механико-математический факультет, аудитория 14-08.

С диссертацией можно ознакомиться в библиотеке механико-математического факультета МГУ (Главное здание, 14 этаж).

Автореферат разослан

Ученый секретарь " диссертационного совета

Д.053.05.0-5 при МГУ

доктор физико-математических наук,

профессор

В. Н. Чубариков

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

Актуальность темы. Комбинаторная теория групп давно оформилась в качестве самостоятельного раздела теории групп. Отличительной особенностью комбинаторного полхода к теории групп является задание групп с помощью порождающих и определяющих соотношений. Одним из источников этого подхода можно назвать алгебраическую топологию. Его основы были развиты еще в начале века в работах А. Пуанкаре и М. Дэна. В настоящее время имеется целый ряд книг, посвященных данному вопросу; достаточно назвать монографии Карраса, Магнуса и Солитэра1, а также Линдона и Шуппа2.

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

Одной из основных проблем комбинаторной теории групп является поставленная еще Дэном проблема равенства слов. В общем случае она имеет отрицательное решение — см. работы П. С. Новикова4 и Буна.5. Для полугрупп отрицательное решение проблемы слов еще раньше было получено А. А. Марковым6 и Постом7. Тем пе менее, проблема слов для групп и полугрупп остается ничуть не менее актуальной, так как представляет интерес ее решение для конкретных случаев. В этой связи можно отметить проблему слов для групп с одним соотношением, решенную в 30-е годы Магнусом8, а также открытую по сей день проблему слов для полугрупп с одним соотношением.

Отметим также проблему слов для некоторых свободных алгебраических систем. Нариыер, проблема слов для свободных берпсайдовых групп (заданных тождеством х" = 1) тесно связана с проблемой Бернсайда для групп9. В работе П. С. Новикова и С. И. Адяна10 проблема Бернсайда о локальной конечности таких групп была решена отрицательно для достаточно больших нечетных показателей; для этих же случаев была доказана разрешимость проблемы слов.'-Отметим здесь недавние работы

!В, Магнус. А. Каррас, Д. Солитэр. Комбинаторная теория групп. — М., Наука, 1974.

2Р.. Лнндон. П. Шупп. Комбинаторная теория групп. — М., Мир, 1980.

3Ж. Лаллеман. Полугруппы и комбинаторные приложения. — М., Мир, 1985.

4П. С. Новиков. Об алгоритмической неразрешимости проблемы тождества в теории групп. — Труды МИАН СССР, 1955. т.44, с.3-143.

5 W. W. Boone. The word problem. — Ann. of Math., 1959',. v.70, pp.207-265.

6A. А. Марков. Невозможность некоторых алгорифмов в-теории ассоциативных систем. —ДАН СССР. 1947, т.55, с.587-590; т.58, с.353-356.

7Е. Ь. Post Recursive unsolvability of a problem of Tilge-— J. Symb. Logic, 1947, v.12, pp.I-11.

8 W. Magnus: Das Identitäts - Problem für Gruppen mit einer definierenden Relation. — Math. Ann., 1932, v. 106, pp.295-307.

9W. Bumside. On an unsettled question in the theory of/discontinuous groups. — Quart. J. Pure Appl. Math., 1902, v.33, pp. 230-238.

10П. С. Новиков. С. И. Аяян. О бесконечных периодических группах. I, II, III. — Известия АН СССР. сер. магем . 1968. т.32, №1, с.212-244, №2, с.251-524, №3, с.709-731.

С. В. Иванова11 и И. Г. Лысёнка12, где рассмотрен случай четных показателей.

Для наиболее общей постановки вопроса рассмотрим тождество хт — хт+", т > 0, n > 1. Проблема слов для моноидов (полугрупп с единицей), свободных в многообразии, заданном этим тождеством, включает в себя и случай свободных бернсайдовых групп (при т = 0). Вполне естественна задача о решении проблемы слов для свободных бернсайдовых моноидов для любых ш, п, и она неоднократно ставилась разными авторами, в частности, JI. Н. Шевриным, о чем сказано в обзоре М. Садира и О. Харлампович13. Очень хорошо известна проблема слов для свободных бернсайдовых полугрупп, заданных тождеством х1 = ,т3 — см. Свердловскую тетрадь14. Для случая п = 1 хорошо известна задача, ставившаяся Бжозовскн15 о регулярности классов слов, равных данному в таких полугруппах (последнее тесно связано с проблемой слов).

Теперь расскажем о работах в данном направлении. Во-первых, случай т = 1 непосредственно сводится к теории групп, как следует из работы Кадоурека и Полака16. Далее, обе проблемы — проблема слов н проблема регулярности — были решены недавно Мак-Каммондом17 для т > 6 и независимо де Лукой и Варриккио18 для т > 5, п = 1.

Важно заметить, что проблема равенства слов (термов) для свободных алгебраических систем может быть весьма сложной или даже вовсе неразрешимой — в качестве примера можно привести работу Фриза19, где доказывается неразрешимость проблемы равенства для свободных модулярных решеток.

Помимо проблемы слов для групп и полугрупп мы будем затрагивать также такие темы, относящиеся к комбинаторной теории этих алгебраических систем, как уравнения в свободных группах и полугруппах, автоморфизмы свободных групп. Говоря об уравнениях, следует упомянуть фундаментальные работы Г. С. Мака-нина об алгоритмической разрешимости уравнений в свободных полугруппах2' и

"S. V. ivanov. The free Burnside groups of sufficiently large exponents. — Int. J. of Alg. and Comput., 1994, v.4, pp. 1-308.

12И. Г. Лысёяок. Бесконечные бернсайдовы группы четного периода. — Известия РАН, сер. ма-тем., 1996, т.60, №3, с.3-224.

"О. G. Kharlampovich and М. V. Sapir. Algorithmic problems in varieties. — Int. J. of Alg. and Comput., v.5,.m-5 (1995).

14Свердловская тетрадь. Нерешенные задачи теории полугрупп. — Выпуск третий. Свердловск, 1989.

i5J. A. Brzozowski. Open problems about regular languages. — In: R V. Book, editor, Formal Language Theory, Perspectives and Open Problems. Academic Press, 1980, New York. NY, pp. 2347.

16J. Kadourek and L. Polak. On free semigroups satisfying xr ~ r. — Simon Stevin. 1990, v.64, pp. 3-19.

17J. McCammond. The solution to the word problem for the relatively free semigroups satisfying Г" = T"+6 with a > 6. — Int. J. of Algebra and Comput., 1991, v.l, X>1, pp. 1-32.

18A. de Luca and S. Varricchio. On noncounting regular classes. — Theor. Сотр. Sci., 1992, v.100, pp. 67-104.

"R. Freese. Free modular lattices. — Trans. Amer. Math. Soc.. 1980, v.261, pp. 81-91.

20Г. С. Макании. Проблема разрешимости уравнений в свободной полугруппе. — Матем. сб., 1977, т.ЮЗ, №2, с.147-236.

свободных группах21, а также работу А. А. Разборова22 об описании решений уравнений в свободных группах. Что касается автоморфизмов свободных групп, то здесь мы будем пользоваться результатами Мак-Кула23 о стабилизаторах элементов, а также важной теоремой Герстена о неподвижных точках автоморфизмов свободных групп24.

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

В теории групп диаграммы ван Кампена (или диаграммы сокращений) систематически изучаются с конца 60-х годов. Глава V уже упоминавшейся монографии Линдона и Шуппа полностью посвящена этому вопросу. Из более современных работ укажем монографию А. Ю. Ольшанского25, в которой на основе диаграмм развит мощный метод, приведший к построению большого количества групп с новыми свойствами в работах как самого автора монографии, так и его учеников. Наша кандидатская диссертация была посвящена именно использованию этого подхода для построения новых групп, см. по этому поводу работы автора28,27,53. Этот же подход был вновь применен автором в недавней работе [13].

В теории полугрупп диаграммы были использованы несколько позже. Это было сделано впервые в работе Е. В. Кашинцева29. Впоследствии теории полугрупповых диаграмм были посвящены отдельные работы, например, работа Реммерса30. Диаграммы в группах и полугруппах являются эффективным средством, полезным во многих исследованиях. Помимо проблемы слов, их можно эффективно применять для исследования вложимости полугрупп в группы — см. работу Кашинцева31, а также

"Г. С. Маканин. Уравнения в свободных группах. — Изв. АН СССР, сер. матем., 1982, т.46, C.U99-127Î.

22А. А. Разборов. О системах уравнений в свободных группах. — Изв. АН СССР, сер. матем., 1984, Т.48, с.779-832.

23J. McCool.- Some finitely presented subgroups of the automorphism group of a free group. — J. Algebra, 1975, v.35, pp. 205-213. '

24S. M. Gersten. On fixed points of automorphisms of finitely generated free groups. — Bull. Amer. Math. Soc., 1983, v.8, pp. 451-454.

25A. Ю. Ольшанский. Геометрия определяющих соотношений в группах. — М., Наука, 1989.-'

26В. С. Губа. Об условиях, при которых 2-порожденные подгруппы в группах с малым сокращением свободны.— Известия вузов. Математика. 1986, №7, с. 12-19.

VB. С. Губа. Конечно-порожденная полная группа. — Известия АН СССР, сер. матем., 1986, т.50, №5, с.883-924.

23В. С. Губа. Конечно-порожденная простая группа со свободными 2-порожденными подгруппами. — Сиб. матем. ж., 1986, т.27, JSÈ5, с.50-67.

23Е. В. Кашинцев. Графы и проблема слов для конечно-представленных полугрупп. — Уч. зап. Тульского пед. института, 2 (1970), 290-302.

30J. H. Remmers. On the geometry of semigroup presentations. — Advances in Math:, v.36(3), 1980, pp.283r296

3IE. V. Kashintsev. Small cancellation conditions and embeddability of semigroups in groups. — Int.

для исследования проблем делимости в полугруппах и во многих других случаях.

Особого рассмотрения требует тема, касающаяся групп диаграмм. Это новый класс групп, элементами которых являются полугрупповые диаграммы. Исследование этого класса групп является новым направлением, промежуточным между теорией групп и полугрупп. Первые результаты в этом направлении получены в диссертации Килибарды32. К этим группам независимо пришел также Прайд33, поставивший о них ряд открытых проблем.

Цель работы и научная новизна. Целью диссертации является решение ряда известных проблем комбинаторной теории групп и полугрупп, а также теории формальных языков. При решении применяются как комбинаторные, так и геометрические методы. К главным результатам диссертации можно отнести следующие:

• Доказано, что системы уравнений от конечного числа неизвестных в свободных группах эквивалентны своим конечным подсистемам.

• Доказана гипотеза Эренфойхта о тестовых множествах.

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

• Доказано, что свободная бернсайдова полугруппа с тождеством Хт = А'т+'' имеет разрешимую проблему равенства слов при т > 3, п > 1.

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

• Завершена начатая Е. В. Кашинцевым классификация условий малого сокращения. необходимых для вложения полугрупп в группы. В терминах этих условий (см. определения ниже) доказано, что ■

- полугруппы класса Л'|. вложимы в группы;

— при любом q существуют полугруппы с сокращением, не вложимые в группы, принадлежащие классу A'j.

• Доказано, что класс групп диаграмм содержит группу Р. Томпсона F.

• Доказано, что группы диаграмм обладают однозначным извлечением корней (в частности, не имеют кручения).

J. of Alg. and Сотр., v.2, No.4 (1992), 433-441.

32V. Kilibarda. On the algebra of semigroup diagrams. — PhD thesis, Univ. of Nebraska, Lineóla,

1994.

33S. J. Pride. Low-dimensional homotopy jheory for monoids. — Int. J. of Alg. and Comput., v.o. HQ,

1995, pp. 631-649.

• Решена проблема сопряженности для групп диаграмм над полугрупповыми копредставлениями с разрешимой проблемой слов, включая проблему сопряженности в группе Р. Томпсона.

• Описаны перестановочные элементы в группах диаграмм и централизаторы элементов.

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

Кроме того, в диссертации получен ряд результатов, относящихся к проблеме слов для полугрупп с одним определяющим соотношением. Так, для полугрупп вида (а,Ь | Ь<3а = а) Доказана равносильность трех алгоритмических проблем: проблемы равенства, проблемы левой делимости и проблемы правой делимости. При исследовании вопросов о вложимости полугрупп в группы дал ответ на вопрос 3.47 из Свердловской тетради.

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

Практическая и теоретическая ценность. Работа носит теоретический характер. Ее результаты могут быть применены в различных разделах теории групп и полугрупп, в теории формальных языков. Развитые в диссертации вопросы важны для дальнейших исследований по проблеме слов в группах и полугруппах, для изучения групп диаграмм. Многие доказанные в диссертации теоремы могут быть включены в спецкурсы для студентов и аспирантов.

Апробация работы. Результаты автора, вошедшие в диссертацию, докладывались на многочисленных научных семинарах у нас в стране и за рубежом: семпнары в МГУ — в течение 1984-1996 гг. — по теории групп (рук. профессора А. Л .Шмель-кия и А. Ю. Ольшанский), по алгоритмическим проблемам алгебры (рук. чл.-корр. РАН С. И. Адян), научно-исследовательский семинар кафедры высшей алгебры (зав. . — чл.-корр. РАН А. И. Костршшн); в 1992 г. и 1996 г. — семинар в Уральском госуниверситете, г. Екатеринбург (рук. проф. Л. Н. Шеврин); в университетах Велико* бриташш (Глазго, Эдинбург, Манчестер) в 1993-1995 гг., США (Нью-Йорк, Беркли, Линкольн, Сакраменто, Чико) в 1994-1995 гг., Франции (Париж) в 1996 г. Результаты диссертации докладывались на XVIII Всесоюзной алгебраической конференции (Кишинев, 1985), Школе по теории алгебраических систем (Омск, 1985), XI Всесоюзном симпозиуме по теории групп (Кунгурка, 1989), Сибирских школах "Алгебра п Анализ" (Иркутск, 1992-1993 гг.), на, международных конференциях по теорий полугрупп (Йорк, Великобритания - 1993 г.. Порту, Португалия - 1994 г., Санкт-. Петербург, Россия - 1995 г.).

Публикации. Основные результаты диссертации опубликованы в 13 работах автора, указанных в конце автореферата.

Структура и объем диссертации. Диссертация состоит из введения и шести глав. Первая глава содержит основные определения; в главах 2-6 излагаются результаты диссертации. Для набора текста диссертации использована издательская система MgX. Полный объем диссертации составляет 184 страницы, из которых 10 страниц занимает библиография, включающая 144 наименования.

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

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

Глава 1 имеет вводный характер. В ней собраны необходимые определения и основные факты, используемые в диссертации.

Глава 2 разбита на два раздела. В разделе 2.1 доказывается гипотеза Эренфойхта о тестовых множествах. Пусть £ — конечный алфавит, и пусть L С S+ — формальный язык, т.е. произвольное множество слов. Рассмотрим еще один алфавит П, и пусть д, h — два гомоморфизма свободной полугруппы £+ в свободную полугруппу П+. Допустим, что требуется выяснить, совпадают ли гомоморфизмы д, h на множестве L. Предположим, что в L имеется конечное подмножество Т такое, что g и h совпадают на L тогда, и только тогда, когда они совпадают на Т. В этом случае можно проверить факт совпадения ff и h на конечном множестве Т. Такое подмножество Т, общее для всех пар гомоморфизмов, называется тестовым множеством. Эренфойхт предположил (см.34), что всякий язык обладает тестовым подмножеством. Эта гипотеза была доказана для различных классов языков (см.35). В работе36 было показано, что гипотеза Эренфойхта равносильна утверждению о том, что всякая система уравнений в свободной полугруппе с конечным числом неизвестных эквивалентна некоторой своей конечной подсистеме.

В декабре 1984 года автор доказал, что. всякая система уравнений в свободной группе с конечным числом неизвестных эквивалентна некоторой своей конечной подсистеме. Отсюда легко вытекает как аналогичное утверждение об уравнениях в полугруппах, так и гипотеза Эренфойхта. Доказательство базируется на двух хорошо известных фактах: изоморфной представимости свободных групп ранга 2 матрицами размером 2 х.2 с целыми коэффициентами, а также теоремой Гильбер-. та о базисе. Последняя есть не что иное, как 'утверждение о том, что любая система дяофантовых уравнений с конечным числом переменных эквивалентна конечной подсистеме. Доказательство было анонсировано в [1] и опубликовано в [2]. Оно сразу же стало широко известным — см., например, информационную заметку Мак-Нотона37

34К. Culik II and A. Salomaa. Test sets and checking' vvords for homomorphism equivalence. — Л. of Computers and System Sciences, 1980, v.20, pp.379-395v '

35J. Karhumäki. The Ehrenfeucht conjecture: A compactness claim for finitely generated free monoids.

— Theor. Comp. Sei., 1984, v.29, pp.285-308.

36K. Culik II and J. Karhumäki. Systems of equations over a free monoid and Ehrenfeucht's Conjecture.

— Discrete Math., 1983, v.43, pp.139-163.

3,R. McNaughton. A proof of the Ehrenfeucht Conjecture. — Informal Memorandum. Rensselaer Polytechnic Institute, 1985.

или послесловие А. А. Мучника и А. Л. Семенова к книге38. Независимо от автора, гипотезу Эренфойхта решили также Алберт и Лоренс39. Они использовали результаты Ф. Холла о метабелевых группах.

Определение. Пусть L С Е+ — произвольный язык. Конечное подмножество Т языка L называется тестовым множеством, если для любой пары (д, h) гомоморфизмов свободной полугруппы в произвольную свободную полугруппу, д(х) = h(x) для всех х е L тогда и только тогда, когда д(х) = h{x) для всех х £ Т.

Гипотеза Эренфойхта. Всякий язык над конечным алфавитом обладает тестовым подмножеством.

Мы доказываем эту гипотезу с помощью следующего факта.

Теорема 2.1.1. Всякая система уравнений е свободной группе (в свободной полугруппе) от конечного числа неизвестных эквивалентна некоторой своей конечной подсистеме.

Отсюда вытекает доказательство гипотезы Эренфойхта.

Теорема 2.1.2. Для любого языка L над конечным алфавитом имеется тестовое подмножество Т в L.

В разделе 2.2 рассматривается еще одно применение Теоремы 2.1.1. Напомним некоторые факты об автоморфизмах свободных групп. Пусть F„ — свободная группа ранга п. Рассмотрим произвольный ее автоморфизм <р € Aut.Fn. Неподвижной подгруппой автоморфизма <р называется множество элементов из F„, переходящих в себя под действием tp, т.е. { х £ Fa | ip(x) — х }.

Как уже говорилось, в 1982 году Герстен получил фундаментальный результат о неподвижных точках .автоморфизмов свободных групп. Теорема Герстена утверждает, что неподвижная подгруппа автоморфизма свободной группы конечного ранга является конечно-порожденной. Позднее было дано много других доказательств этого факта, включая разнообразные его обобщения. Отметим очень короткое доказательство, данное в работе40, где этот результат доказан для любых эндоморфизмов. ■ Бествина и Хэндел41 дали решение проблемы Скотта, доказав, что ранг неподвижной-подгруппы не превышает п. . '

Рассмотрим любое множество G С Aut Fn автоморфизмов группы F„. Пусть Fix G — неподвижная подгруппа этого множества автоморфизмов, т.е. FixG = { х € Fn j ¡р(х) = I Vy £ Gj. В своей работе42 Герстен 'спрашивает, верно ли обобщение его

38А. Саломаа. Жемчужины теории формальных языков. — М., Мир, 1986.

39М. Н. Albert and J. Lawrence. A proof of Ehrenfeucht.'s conjecture. —Theor. Comp. Sei., 1985, №1, pp. 121-123.

40R. Z. Goldstein and E. C. Turner. Automorphisms of free groups and their fixed points. — tnv. . Math., 1984, v.78, pp. 1-12.

41M. Bestvina and M. Handel. Train tracks and automorphisms of free groups. — Ann. Math. Ser.2, 1992, v.135, Ml, pp. 1-51.

42S. M. Gersten. Fixed points of automorphisms of free groups. — Adv. Math., 1987, v.64, pp. 51-85.

результата для случая любого множества автоморфизмов, т.е. будет ли Fix G всегда конечно порождена.

Автором дан положительный ответ на этот вопрос в [3]. Доказательство использует Теорему 2.1.1. Независимо ответ на этот же вопрос был дан С. Томасом в работе43. Вместо Теоремы 2.1.1 там использовано ее обобщение, полученное Стол-лингсом в44.

Сформулируем основной результат раздела 2.2.

Теорема 2.2.1. Неподвижная подгруппа любого множества автоморфизмов свободной группы конечного ранга является конечно-порожденной.

Глава 3 посвящена решению проблемы слов в свободных бернсайдовых моноидах (полугруппах), заданных тождеством хт = хт+". Как уже говорилось, случаи m — О и m = 1 относятся к теории групп. Предыдущие результаты в этой области о разрешимости проблемы слов были получены Мак-Каммондом для m > 6 и независимо де Лукой и Варриккио для m > 5, n = 1. Доказательство Мак-Каммонда использует язык автоматов (т.е. размеченных графов). На этом языке формулируются базовые понятия, и доказательство лемм (их более 40) ведется с помощью сложной совместной индукции по натуральному параметру, называемому рангом. В работе де Луки и Варриккио используются методы, традиционные для комбинаторики на словах, которой посвящена монография Лотэра45. Авторы отмечают, что их метод не работает при m = 2 и m = 3, но выражают надежду, что его можно распространить на случай m = 4 (напомним, что в этой работе исследуется лишь случай п — 1). В обеих цитированных выше работах помимо решения проблемы слов решается также проблема Бжозовски о регулярности классов конгруэтности слов (т.е. при тех же условиях доказывается, что множество всех слов, равных данному в этих полугруппах, образует регулярный язык).

В отличие от теоретико-групповой ситуации оценки параметров в работах Мак-Каммонда и де Луки, Варриккио давали надежду, что возможно полное исследование вопроса о проблеме слов. Автором сделан значительный шаг в этом направлении. Именно, в работах [4], [5] показано, что проблема слов и проблема регулярности конгруэнц-классов имеют положительные решения уже при m > 3. Лишь случай m — 2 остается открытым.

Распространение оценки на случай m > 4 было сделано автором [4] (в этой работе также охвачен случай m = 3, п = 1) и независимо А. П. до Лаго46. Автор опирался на работу Мак-Каммонда. В результате радикального упрощения приведенного в этой работе доказательства удалось не только улучшить оценку, но и уменьшить

43S. Thomas. Fixed points of automorphisms of finitely generated free groups. — Proc. Amer. Math. Soc., 1988, V.103, №1, p. 333.

44J. R. Stallings. Finiteness properties of matrix representations. — Adv. Math., 1986, v.124, pp.337346.

45M. Lothaire. Combinatorics on Words. — V. 17 of Encyclopedia of Mathematics and its Applications, Addison-Wesley, 1983.

46A. P. do Lago. On the burnside semigroups xn = i"+m. — In: I. Simon, editor, LATIN 92, v.583 of Lect. Notes in Comp. Sei. Berlin, 1992, Springer-Verlag, pp.329-343.

число лемм, использованных в цикле совместной индукции, до четырех. Интересно, что хотя автоматы играют основополагающую роль в работе Мак-Каммонда, автор в [4] совсем не использует это средство, давая все основные определения прямым способом. Отметим, что доказательство Мак-Каммонда в принципе почти без изменений работает и для случая m = 4, если его немного модифицировать. Однако его упрощение важно не столько само по себе, сколько как шаг к случаю m = 3, который является существенно более сложным и о котором речь пойдет ниже. Работа до Лаго представляет собой усовершенствование метода де Луки и Варриккио.

Различие случаев m = 3 и m = 4 вызвано леммой 3.1.5. Именно в ней существенно используется аргумент, требующий предположения m > 4. Этот аргумент никак не применим при m = 3. Хотя речь идет об изменениях в доказательстве всего одной леммы, но' нужно помнить, что доказываемые леммы связаны циклом совместной индукции, поэтому это сказывается и на всех остальных леммах, составляющих цикл. Доказательство для случая то > 4 дается нами в разделе 3.1. Для преодоления трудностей, связанных с переходом к случаю га = 3 нам приходится применять гораздо более скрупулезный комбинаторный анализ слов, добавляя несколько новых понятий к основным и вводя в рассмотрение принципиально новые утверждения, увеличивая до 10 количество лемм цикла, участвующих в доказательстве с помощью совместной индукции. По существу, целыо является доказательство леммы 3.2.10, которая сама имеет очень сложное доказательство, и требующая к тому же нескольких "подготовительных" лемм. Чтобы подчеркнуть точность оценок, используемых при этом, заметим, что одна из наиболее часто применяемых технических лемм (так называемая лемма Файна - Уилфа47), используемая во всех без исключения работах, связанных с периодическими словами (в том числе во всех выше цитированных), применяется в своей наиболее сильной форме (см. лемму 3.1.1), в то время как во всех остальных работах вполне достаточно ее ослабленного варианта. Раздел 3.2,. в котором проводятся доказательства для случая m — Z, несмотря на его сравнительно небольшой объем, мы считаем одним из наиболее сложных и одним из наиболее существенных в нашей диссертации.

Итак, в главе 3 мы доказываем следующий основной результат.

Теорема 3.2.11. Пусть m > 3, п > 1. Тогда проблема слов для полугруппы

В(2, m, п) = ( S I Тт = Тт+Л, Т е Е* )

разрешима. Кроме того, для любого слова w над S множество [ю] всех слов -над S, равных w в B(S,m,n), есть регулярный язык.

Отметим, что по данному слову w мы можем эффективно указать автомат, зада- . ющий язык [ty], что дает еще один способ решения проблемы слов.

Решение проблемы слов и метод исследования свободных бернсайдовых полугрупп дают возможность получать и другие результаты об этих полугруппах. Ска: жем. Мак-Каммондом описаны максимальные подгруппы в В(г, тп,п) при m > б,

,7К. J. Fine, M. S. Wilf. Uniqueness theorem for periodic functions. — Proc. Amer. Math. Soc., 1965, v.16, pp. 109-114.

до Л aro описал отношения Грина в рассматриваемых полугруппах, а в совместной работе автора и С. Прайда [12] техника работ [4, 5] применяется для вычисления целочисленных гомологий и когомологий для свободных бернсайдовых полугрупп. Для вычисления гомологий используется метод Кобаяси48.

Последний раздел 3.3 данной главы является как бы приложением к основным результатам. Он посвящен изучению уравнений в свободной полугруппе, которые можно рассматривать как обобщение уравнений Линдона - Шютценберже (см. работу49, где рассматриваются уравнения хку' = гт, к,(,т > 2 в свободной группе). Мы показываем, что третья степень простого слова не может быть представлена в виде произведения периодических слов с более короткими периодами (теорема 3.3.5). Этот результат был доказан автором в [6]. Он очевиден, если рассматривать четвертую степень слова и выше (ср. разницу между случаями m > 4 и m — 3 при исследовании свободных бернсайдовых полугрупп), но нетривиален, если брать куб слова. Утверждения подобного рода представляют самостоятельный интерес, а также могут быть применены при исследовании проблем бернсайдовского типа в группах и полугруппах. Кроме того, в разделе 3.3 мы приводим еще один результат, касающийся разложения квадрата простого слова в произведение периодических слов с более короткими периодами (теорема 3.3.6).

Глава 4 посвящена вопросам о вложении полугрупп в группы. Легко понять, что необходимым условием изоморфной вложимости полугруппы в группу является закон двустороннего сокращения в полугруппе. Это условие не является достаточным, что было впервые доказано А. И. Мальцевым50. Мальцев помимо всего прочего дал описание необходимых и достаточных условий на языке квазитождеств. Список этих квазитождеств бесконечен, и поэтому далеко не всегда бывает легко проверить, удовлетворяет ли данная полугруппа этим квазитожде.ствам. Поэтому интерес представляют такие достаточные условия, которые выполнялись бы для широкого класса полугрупп и были при этом легко устанавливаемы. Классическим примером условия, достаточного для вложения в группу полугруппы с двусторонним сокращением, является (правое) условие Ope: любые два главных, правых идеала имеют непустое пересечение. (Это условие выполнено для всех полугрупп, удовлетворяющих нетривиальному полугрупповому тождеству.) Б. Н. Новиков спрашивает в Свердловской тетради, будет ли достаточным для вложениЯ'обобщенное условие Ope. Мы показываем в разделе 4.1, что оно не будет достаточным.

С комбинаторной точки зрения интересно нахождение условий вложимости в группу полугрупп, заданных своими копредставлениями. Например, С. И. Адян доказал в51, что полугруппа, заданная копредставлением без циклов, вложима в

-;_

4SY. Kobayashi. Complete rewriting systems and homology of monoid algebras. — Journal of Pure and Appl. Alg., 1990, v.65, pp.263-275. .

49R. C. Lyndon and M. P. Schiitzenberger. The equation aM — bNcp in a free group. — Michigan Math. J., 1962, v.9, pp.289-298. ' V

50A. I. Maltsev. On the immersion of an algebraic ling into a field. — Math.Ann., vol.133 (1937). 686-691.

51C. И. Адян. Определяющие соотношения и алгоритмические проблемы для групп и полугрупп.

группу. В своей работе 1992 года (см. выше) Е. В. Кашиннев исследует копред-ставления с так называемыми условиями малого сокращения. Таких условий два: Cs{p) п j0(g). Условие Cs(p) означает, что никакое определяющее слово не может быть произведением менее, чем р кусков, где под куском понимается слово, имеющее по крайней мере два различных вхождения в определяющие слова. Условие D(q) означает, что как в левом, так и в правом графе системы соотношений нет циклов длиной меньше q. (Например, D(оо) есть условие отсутствия циклов.) Рассматриваемые условия являются естественными и представляют собой полугрупповые аналоги хорошо изученных условий малого сокращения в группах. Кашинцев вводит классы

полугрупп, которые могут быть заданы копредставлениями с условиями С,(р) и D(q). Возникает общий вопрос: при каких р и q все полугруппы класса вложимы в группы? Результат Адяна, цитированный выше, означает, что полугруппы класса iff вложимы в группы. Анализируя пример Мальцева, легко понять, что в классе есть полугруппы, не вложимые в группы, даже при наличии закона двустороннего сокращения.

В своей работе Кашпнцевым получены два основных результата. Во-первых, он доказывает, что полугруппы классов К\ и iff вложимы в группы. Во-вторых, он приводит примеры полугрупп из 7f| для любого натурального q, которые в группы не вложимы. Он ставит поэтому следующие два естественных вопроса. Будут ли вложимы в группы все полугруппы класса if|? (Этот класс собственно содержит объединение классов К] и iff.) Можно ли^для любого q > 2 привести примеры полугрупп с двусторонним сокращением из класса которые бы в группы не вкладывались?

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

Теорема 4.2.1. Все полугруппы класса А'| вложимы в группы.

Интересно отметить, какими свойствами обладают эти группы. У Кацшнцева отмечено, что полугруппы из К\ и iff вкладываются-в • группы, удовлетворяющие (групповому) условию малого сокращения С(6)'. Мы же показываем, что полугруппы класса К\ могут быть вложены в группы с условиями малого сокращения С(4) и Т(4) (определения групповых условий малого сокращения можно монографии Линдона и' Шуппа). .....

Теорема 4.2.2. Для любого q > 2 существует полугруппа с двусторонним сокращением, принадлежащая классу Kj, не вложимая в группу.

Результаты данной главы опубликованы автором в [7].

Глава 5 посвящена исследованиям по проблеме слов для полугрупп с одним определяющим соотношением. Как уже говорилось, первые примеры конечных ассоциативных исчислений с неразрешимой проблемой равенства были построены независимо А. А. Марковым и Постом. Ю. В. Матиясевич52 построил пример, показывающий.

— Труды МИАН им. В. А. Стсклова, 1966, т.85, с.1-124.

52Ю. В. Матиясевич. Простые примеры неразрешимых ассоциативных исчислений. — ДАН

что существуют неразрешимые ассоциативные исчисления с тремя определяющими соотношениями. До сих пор открытым является вопрос, будет ли разрешима проблема равенства слов для полугрупп с одним определяющим соотношением. Этот вопрос интересен еще и потому, что для групп с одним определяющим соотношением разрешимость проблемы слов доказана Магнусом еще в тридцатые годы.

Вначале расскажем о результатах по проблеме слов для полугрупп с одним определяющим соотношением (на самом деле мы рассматриваем полугруппы с единицей, т.е. моноиды). Помимо проблемы равенства слов, традиционный интерес представляют также проблемы левой и правой делимости. С. И. Адян доказал, что моноиды, заданные соотношением вида А — 1, имеют разрешимые проблемы равенства и делимости слов. Он также доказал, что проблема слов разрешима для случая несократимого соотношения. Отметим, что разрешимость проблем делимости для таких полугрупп — открытый вопрос. В работе Адяна53 введен важный алгоритм, к изучению работы которого сводятся в известном смысле данные проблемы. В работе54 изучается случай соотношения, сократимого с обеих сторон, и доказывается, что этот случай можно свести либо к уже решенным вопросам, либо к случаю соотношения, сократимого с одной стороны. Еще одно доказательство сведения можно найти в55. Случай полугрупп, заданных соотношениями вида а = ЪА изучался в работах Г. У. Оганесяна56,57. В первой из работ, в частности, была установлена разрешимость проблем равенства и левой делимости слов для случая соотношения вида а = (ЬР)та, т > 1. Во второй работе проблема слов для полугрупп с соотношением вида а = бфа сведена к проблеме делимости для полугрупп без циклов. (Последняя долгое время считалась решенной, но в58 замечено, что доказательство, данное в59, ошибочно.)

Таким образом, в настоящее время проблема слов сведена к случаям полугрупп с двумя порождающими о, Ь, заданных при помощи соотношения одного из видов: а = ЬС^а или аРа — ЪС^а. Заметим, что обе полугруппы задаются соотношениями без левых циклов. Для таких полугрупп разрешимость проблемы левой делимости влечет разрешимость проблемы слов.

Мы в данной главе анализируем прежде всего случай полугрупп с соотношени-

СССР, 1967, т.173, №6, с.1264-1266.

53С. И. Адян. О преобразованиях слов в полугруппе, заданной системой определяющих соотношений. — Алгебра и логика, 1976, т.15, №6, С.6Н-621.

54С. И. Адян, Г. У. Оганесян. К проблемам равенства и делимости в полугруппах с одним определяющим соотношением. — Известия АН СССР, сер.матем., 1978, т.42,1^62, с.219-225.

55С. И. Адян, Г. У. Оганесян. О проблемах равенства и делимости для полугрупп с одним соот-_ ношением. — Матем. заметки, 1987, т.41, вып.З, с.412-421.

56Г. У. Оганесян. О проблемах равенства и делимости в полугруппах с определяющим соотношением вида а = ЬА. — Известия АН СССР, сер.матем., 1978, т.42, КЗ, с.602-612.

57Г. У. Оганесян. О полугруппах с одним соотношением и полугруппах без циклов. — Известия АН СССР, сер.матем., 1982, т.46, Ш, с.88-94.

58С .И. Адян. К проблеме делимости для моноидов, заданных одним соотношением. — Матем.заметки, 1994, т.55, вып.1, с.3-9.

590. А. Саркисян. О проблемах тождества и делимости в полугруппах и группах без циклов. — Известия АН СССР, сер.матем., 1981, т.45, №6, с.1424-1441.

ем первого вида: а = Ь(}а. Нас интересуют следующие алгоритмические проблемы: проблема слов, проблема левой делимости и проблема правой делимости.

В разделе 5.1 мы доказываем утверждение о том, что для любых моноидов с левосторонним сокращением проблема слов для них сводится к проблеме вхождения элементов свободной группы в так называемое полунормальное замыкание некоторого конечного множества (а потому и проблема слов в целом может быть сведена к этому). Полезно сравнить этот результат с теоремой Магнуса, которая может быть переформулирована в терминах проблемы вхождения в нормальное замыкание.

Раздел 5.2 посвящен исследованию полугрупп, заданных соотношением а = ЬС^а, в терминах полугрупп концов. Этот подход использовался Оганесяном. Если П — полугруппа, то пусть 5(П) — подполугруппа в П, порожденная всеми концами слова ЬС}а. Оганесян доказал, что проблемы левой делимости для этих полугрупп эквивалентны, а также что 5(П) задается копредставлением без циклов. Мы выясняем, что это копредставление путем упрощений не всегда приводится к одному определяющему соотношению. Однако группа С?(П), в которую 5(П) изоморфно вкладывается, всегда может быть задана при помощи одного соотношения (Теорема 5.2.1). Этот результат очень важен по многим причинам. Во-первых, он позволяет решить проблему слов в подполугруппе 5(П), что является частным случаем проблемы слов в П. Во-вторых (Следствие 5.2.4), это позволяет свести проблему левой делимости для П к проблеме вхождения в конечно-порожденную подполугруппу группы с одним определяющим соотношением. (На самом деле можно даже утверждать, что проблема делимости эквивалентна некоторой конкретной разновидности проблемы вхожде-' ния.) Это вскрывает большую сложность рассматриваемой проблемы. В-третьих, мы извлекаем отсюда ряд положительных результатов в случав, когда С(П) оказывается свободной группой (Теорема 5.2.7). Эта ситуация охватывает большинство случаев, когда разрешимость проблемы слов и проблемы левой делимости были известны, например, случай, когда ЬС? — истинная степень. И, наконец, в-четвертых, мы используем этот результат в разделе 5.4 для изучения проблемы правой делимости.

Результаты о связи--.^роблемы левой делимости для полугруппы П, заданной с -помощью а = а| с другими проблемами, показывают ее сложность. В разделе 5.3 . мы выясняем, что и проблема равенства не проще: именно, мы доказываем эквивалентность проблем равенства и левой делимости для таких полугрупп (Теорема 5.3.3). При доказательстве мы существенно пользуемся фактом асферичности групп с одним определяющим соотношением.

Раздел 5.4 посвящен изучению проблемы правой делимости для полугрупп с соотношением а = ЬС^а. Доказывается, что она также равносильна проблеме слов (Теорема 5.4.5). Отсюда, в частности, вытекает решение проблемы правой делимости для всех случаев, рассмотренных в Теореме 5.2.7.

Раздел 5.5 посвящен исследованию алгебраических условий, накладываемых на полугруппу в случае, если она обладает копредставлением без односторонних (скажем, левых) циклов. Давно известно, что в таких полугруппах выполнен закон левостороннего сокращения. Из работ Оганесяна вытекает, что в полугруппе без левых

циклов с присоединенными единицей и нулем пересечение главных правых идеалов есть главный правый идеал. В результате устанавливается взаимно однозначное соответствие между элементами полугруппы и главными правыми идеалами. Операция пересечения главных правых идеалов индуцирует операцию на множестве элементов полугруппы, превращая ее в полурешетку, т.е. коммутативную полугруппу идемпотентов. Изучению этой полурешетки и посвящен раздел. Основной является Теорема 5.5.3, в которой доказывается, что идеалы полурешетки имеют ранг < 2 в том смысле, что любой конечно порожденный идеал полурешетки порождается также двумя элементами. Все алгебраические условия, отмеченные выше, не являются достаточными для того, чтобы полугруппа имела копредставление без левых циклов. Интересно было бы найти другие необходимые условия. Содержание данного раздела актуально еще и в связи с желательностью распространения подхода Оганесяна на полугруппы, заданные в виде аРа = Ь(Ца.

Глава 6 посвящена результатам, полученным в области групп диаграмм. Это новое направление, равным образом относящееся как к теории групп, так и к теории полугрупп, возникло сравнительно недавно. Достаточно полное изложение результатов о группах диаграмм, известных в настоящее время, содержится в объемной работе автора и М.В.Сапира [10] (см. также [9]). В диссертацию включены результаты о группах диаграмм, доказательства которых даны автором.

Полугрупповые диаграммы — это хорошо -известные геометрические объекты, используемые в теории систем Туэ (=полу групповых копредставлений). Роль полугрупповых диаграмм в изучении полугрупп аналогична роли диаграмм ван Кампена в изучений групп (см. по этому поводу работы, цитированные в начале автореферата).

С каждым выводом полугруппового соотношения из определяющих можно связать естественный геометрический объект -— полугрупповую диаграмму. Пусть А ;— такая диаграмма. ■ На нее можно смотреть как. на размеченный плоский граф (граф, нарисованный на плоскости), который имеет два отмеченных пути 1ор(Д) и Ьо1;(Д). Эти пути имеют общие начальные и общие конечные вершины, и вся диаграмма находится между этими двумя путями таким образом, что объединение этих двух путей есть граница диаграммы. Как известно, два слова и и и равны по модулю, системы Туэ V = (здесь И есть алфавит, и 71 есть множество соотношений)

тогда и только тогда, когда существует полугрупповая диаграмма А такая, что метка 1;ор(Д) есть и, метка ЬоЦД) есть V, и метка .границы каждой клетки (области) А есть где 6 = 4 или < = 5 принадлежит "К. Такие диаграммы называются диаграммами над V. .

На множестве полугрупповых диаграмм о^еделена частичная ассоциативная операция, называемая конкатенацией. Если, цетка Ъо1;(Д) совпадает с меткой 1ор( А'), то мы можем рассмотреть конкатенацию диаграмм Д и А', отождествляя Ьо^Д) с 1ор(Д'). Эта операция превращает множество диаграмм в частичную полугруппу. Для любого слова и над алфавитом 2 множество всех диаграмм Д над V с 1ор(Д) и ЬоЦД), имеющими метку и, есть полугруппа относительно конкатенации.

Такие диаграммы называются сферическими («, «)-диаграммами.

Мы говорим, что две клетки ж и 7г' диаграммы Д над Т образуют диполь, если ж есть зеркальный образ тт', и bot(x) = top(îr'). Мы можем удалять диполи в полугрупповых диаграммах. Эта операция приводит к отношению эквивалентности, которое на самом деле есть конгруэнция на частичной полугруппе всех диаграмм над V. Легко видеть, что соответствующая факторполугруппа полугруппы всех сферических («, и)-диаграмм над V есть группа. Эта группа называется группой диаграмм над копредставлением V с базой и и обозначается D{V,v).

Отметим, что можно рассматривать любые копредставления моноидов, то есть допускать соотношения вида и = 1, где 1 есть пустое слово. Диаграммы при этом не являются наиболее удобными геометрическими объектами, представляющими выводы. Более удобные геометрические объекты — это так называемые моноидные схемы, которые, по-существу, суть дуальные графы диаграмм. (В настоящей диссертации мы не рассматриваем моноидных схем, являющихся обобщением диаграмм, но читатель может найти их определение и другую информацию в [10].)

Понятие группы диаграмм было предложено Дж. Микином и М. Сапиром и впервые использовано В. Килибардой в ее диссертации. В частности, она доказала, что любой класс эквивалентности полугрупповых диаграмм содержит единственную диаграмму без диполей. Такие диаграммы называются приведенными.

Килибарда также доказала, что любая группа диаграмм над полугрупповым копредставлением V изоморфна фундаментальной группе естественного 2-комплекса, соответствующего этому копредставлению. Мы называем этот комплекс комплексом Сквайера копредставления V и обозначаем его К{Т). Вершинами этого комплекса служат произвольные слова над 2, ребра соответствуют элементарным выводам (применениям соотношений из 71), 2-клетки соответствуют независимым элементарным выводам (точное определение см. в разделе 6.3). По поводу комплекса Сквайера, независимо введенного несколькими авторами, см. диссертацию Килибарды и работы60,61.

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

Естественно можно поставить вопрос: насколько велик класс групп диаграмм над. копредставлениями полугрупп? Килибарда в своей диссертации доказала, что этот класс замкнут относительно конечных прямых произведений и содержит свободные группы любого конечного ранга. Она также сделала попытку доказать, что любая:

60С. С. Squier. A iiniteness condition for rewriting systems, revision by F. Otto and Y. Kobayashi. — Theoret. Comput. Sei., 131:271-294, 1994.

61S. ]■ Pride. Geometric methods in combinatorial group theory. — In: J. Fountain ed., Semigroups, Formal Languages and Groups. Kluwer Acad. Publ., Dordrecht, 1995, pp. 215-232.

группа диаграмм не имеет кручения и даже обладает однозначным извлечением корней (ап = Ьп => а = Ь). Хотя доказательства Килибарды этих двух фактов оказались ошибочными, результаты тем не менее верны (хотя их доказательства весьма нетривиальны, см. раздел 6.9). Чтобы найти более сложные примеры групп диаграмм, Килибарда пыталась вычислить группы диаграмм копредставления (х | х1 = х) с базой х. Она нашла несколько соотношений этой группы. Далее автор доказал, что эта группа диаграмм есть хорошо известная группа F, которая была открыта Р. Томпсоном в 1965 г. Она задается непредставлением с бесконечным числом порождающих

(zo,xb... | X? =Xj+i, j > i >0)

и может быть также задана с помощью двух порождающих и двух определяющих соотношений. Эта группа была предметом многочисленных исследований с тех пор. Богатую информацию о группе F можно найти в обзоре62. (Уместно упомянуть здесь также работу [11], в которой исследуется функция Дэна этой группы.) В результате было получено новое представление группы Томпсона: представление полугрупповыми диаграммами над очень простым (в действительности, простейшим возможным) копредставлением тривиальной полугруппы. Это также явилось дополнительным свидетельство того, что класс групп диаграмм нуждается в более детальном изучении. Интерес к группам диаграмм подкрепляется еще и тем обстоятельством, что диаграммы, как, скажем, матрицы или подстановки, являются удобными объектами для вычислений: если группа представима диаграммами, то она имеет очень быстрый алгоритм решения проблемы слов.

В разделе 6.1 дается определение операций над-диаграммами, а само определение групп диаграмм дается в разделе 6.2.

Мы используем результат из диссертации Килибарды о том, что любой класс эквивалентности диаграмм содержит в точности одну приведенную диаграмму (т.е. диаграмму без диполей). Используем мы также важный результат оттуда же о том, что любая группа диаграмм D[V, U) над полугрупповым копредставлением V изоморфна фундаментальной группе связной компоненты комплекса Сквайера K(V) с базовой точкой V. Это позволяет нам вычислить копредставления нескольких интересных групп диаграмм, включая группу Р. Томпсона.

В разделе 6.4 исследуется, как группы диаграмм меняются, если мы меняем базу без изменения копредставления, или если мы меняем копредставление.

В разделе 6.5 мы доказываем один из принципиальных результатов главы, который обеспечивает путь вычисления минимального (в смысле числа порождающих) копредставления группы диаграмм над любой полной (=конфлюентной и.нетеровой) переписывающей системой, задающей моноид. Этот результат важен, потому что может быть доказано, что каждая группа диаграмм есть ретракт группы диаграмм над такой полной системой. Оказывается, что если копредсталение V моноида является полным, то любая группа диаграмм D(V, U) есть LOG-группа. Таким образом,

e2J. W. Саппон, W. J. Floyd, and W. R. Parry. Notes on Richard Thompson's groups F and T. — Technical Report GCG63, Geometry Center. University of Minnesota, January, 1994.

всякая группа диаграмм есть ретракт LOG-группы. Напомним, что LOG-rpynna задается в терминах размеченного ориентированного графа (отсюда аббревиатура LOG). Кратко говоря, это группа, заданная соотношениями вида а = Ьс, где а, Ь, с — порождающие. Группы такого вида возникали в математике не раз (например, таковы группы узлов); абстрактный термин "LOG-группа" введен, по-видимому, в работе63. В отечественной литературе такие группы часто называются С-группами; см. недавние работы Ю.В.Кузьмина64,65, где рассматривается их интересные топологические и алгебраические характеризации.

Описание групп диаграмм над полными системаи позволяет нам доказать, в частности, следующие результаты о группах диаграмм (см. разделы 6.5-6.8). .

Теорема 6.7.2. Пусть V — (£,72.) — моноидное копредставление, U 6 £*, и пусть G = D(V,U). Тогда факторгруппа G по коммутанту G' есть свободная абелева группа.

Теорема 6.7.2 отвечает на вопрос Прайда. Отметим также Теорему 6.7.4: если V есть полное копредставление, и каждая группа диаграмм над ним конечно порождена, то каждая группа диаграмм над V конечно представлена. Еще один результат о конечной представимости — Теорема 6.6.7: если V есть конечное копредставление конечного моноида, то каждая группа диаграмм над V конечно представлена. (Заметим, что этот результат не следует из очевидных соображений даже для простейшего задания тривиального моноида.) Следует обратить внимание и на Теорему 6.6.5: существуют конечно-порожденные, но не конечно представимые группы диаграмм над конечными полным полугрупповым копредставлениями.

В разделе 6.8 мы показываем (Теорема 6.8.1), что все три определения Прайда асферичности копредставления моноида эквивалентны в случае полугрупповых ко-представлений, а второе и третье определения эквивалентны в случае произвольных копредегавлений моноидов.

В заключительном разделе 6.9 мы развиваем исчисление, которое может быть названо комбинаторикой на полугрупйовых диаграммах. Сходство между диаграммами и словами ("диаграммы — это двумерные слова") ведет к некоторому сходству между комбинаторикой на словах в смысле Лотэра и комбинаторикой на диаграммах. Геометрическая природа диаграмм позволяет использовать геометрию в изучении комбинаторных свойств диаграмм. Например, рассмотрим уравнение ху = ух в группе диаграмм. Удобно (и возможно в некоторых важных случаях) нарисовать диаграмму ху на сфере и затем рассмотреть группу автоморфизмов сферического графа, получающегося в результате, индуцированных гомеоморфизмами сферы. Описание этой группы позволяет описать все решения этого уравнения. (Заметим, что можно использовать похожий аргумент, чтобы решить уравнение ху = ух в

63YV. A. Bogley. Retractive maps and local collapsibility. — PhD thesis, Univ. of Oregon, 1987.

MIO. В. Кузьмин. Об одном способе постоения С-групп. — Известия РАН, сер. матем., 1995, т.59, №4, с. 105-124.

65Ю. В. Кузьмин. Группы заузленных компактных поверхностей и центральные расширения. — Матем. сб., 1996, т.187, №2, с.81-102.

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

Теорема 6.9.23. Пусть V = (£,%) — полугрупповое копредставление с разрешимой проблемой слое. Тогда проблема сопряженности диаграмм пад V разрешима. В частности, длг каждого слова V € £+ группа В('Р, Ц) имеет разрешимую проблему сопряженности (для естественного представления элементов этой группы сферическими (1/,1/)-диаграмми).

Этот результат влечет разрешимость проблемы сопряженности в группе Р. Томпсона F.

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

Теорема 6.9.35. Пусть Р = (£,71) — полугрупповое копредставление, и пусть <2 = (1) — группа диаграмм, А € в, А ф 1. Тогда централизатор Са(А) элемента А в группе С изоморфен конечному прямому произведению нескольких групп, каждая из которых есть либо бесконечная циклическая группа, либо группа диаграмм вида Р(Р,11') над тем же копредставлением с некоторой базой.

Из этой теоремы вытекает, что в группе Р. Томпсона централизатор любого элемента есть конечное прямое произведение групп, изоморфных бесконечной цикли-, ческой группе Ъ или группе F. . .

РАБОТЫ АВТОРА ПО ТЕМЕ ДИССЕРТАЦИИ

1. В.С.Губа. Эквивалентность бесконечных систем уравнений в свободных группах и полугруппах конечным подсистемам. — XVIII Всесоюзная алгебраическая конференция. Кишинев, 16-18 сентября 1985 г. Тезисы сообщений. Часть первая. Кишинев, 1985, с.148.

2. В.С.Губа. Эквивалентность бесконечных систем уравнений в свободных группах и полугруппах конечным подсистемам. — Матем. заметки, 1986, т.40, вып.З, с.321-324.

3. В.С.Губа. Неподвижные точки автоморфизмов свободных групп. — XI Всесоюзный симпозиум по теории групп, посвященный 60-летию чл.-корр. АН СССР М.И.Каргаполова. Кунгурка, 31 января-2 февраля 1989 г. Тезисы сообщений. Свердловск, 1989, с. 148-149.

4. V.S.Guba. The word problem for the relatively free semigroup satisfying Tm = Tm+" with m > 4 or m = 3, n — 1. — International Journal of Algebra and Computation, 1993, v.3, Л12, pp. 125-140.

5. V.S.Guba. The word problem for the relatively free semigroup satisfying Tm = 7,ro+n with m > 3. — Int. J. of Alg. and Comput., 1993, v.3, №3, pp. 335-347.

6. V.S.Guba. Some properties of periodic words. Glasgow University Preprint Series. №93/09, 1993, pp. 1-7.

7. B.C.Губа. Об условиях вложимости полугрупп в группы. — Матем. заметки, 1994, т.56, вып.2, с.3-14.

8. V.S.Guba. On the relationship between the word problem and the divisibility problems in one-relator semigroups. — In: International conference "Semigroups and their applications including semigroups rings" in honour of E.S.Ljapin. St .-Petersburg, Russia, 19-30 June, 1995. Abstracts. St.-Petersburg, 1995, pp. 18-19.

9. V.S.Guba and M.V.Sapir. Diagram groups. — In: International conference "Semigroups and their applications including semigroups rings" in honour of E.S.Ljapin. St> Petersburg, Russia, 19-30 June, 1995. Abstracts. St.-Petersburg, 1995, pp. 19-20.

10. V.S.Guba and M.V.Sapir. Diagram groups. — Institute Blaise Pascal, University Paris VI-VII. OTP, .95/22. Paris, 1995, pp. 1-119. .

11. V.S.Guba and M.V.Sapir. The Delin function and a regular set of normal forms' for. R.Thompson's group F. Glasgow University Brcprint Series. №94/75, 1994, pp. 1-13.

12. V.S.Guba and S.J.Pride. Low dimensional (co)homology of free Burnside monoids. — Journal of Pure and Applied Algebra, 1996, v, 108, pp. 61-79.

13. B.C.Губа. О группах со свободным транзитивным действием на множестве флагов проективной плоскости. — Снб. матем. ж., 1996, т.37, №5, с.1030-1049.