Введение к работе
Актуальность темы. Комбинаторная: теория групп давно оформилась в качестве самостоятельного раздела теории групп. Отличительной особенностью комбинаторного подхода к теории групп является задание групп с помощью порождающих и определяющих соотношений. Одним из источников этого подхода можно назвать алгебраическую топологию. Его основы были развиты еще в начале века в работах А. Пуанкаре и М. Дэна. В настоящее время имеется целый ряд книг, посвященных данному вопросу; достаточно назвать монографии Карраса, Магнуса и Солитэра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 Thge;— J. Symb. Logic, 1947, v.12, pp.I-11.
8 W. Magnus: Das Identitats - Problem fur Gruppen mit einer defmierenden 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, Ж, с.212-244, №2, с.251-524, №3, с.709-731.
С. В. Иванова11 и И. Г. Лысёнка12, где рассмотрен случай четных показателей.
Для наиболее общей постановки вопроса рассмотрим тождество хт = хга+, т > О, п > 1. Проблема слов для моноидов (полугрупп с единицей), свободных в многообразии, заданном этим тождеством, включает в себя и случай свободных бернсайдовых групп (при т = 0). Вполне естественна задача о решении проблемы слов для свободных бернсайдовых моноидов для любых т, п, и она неоднократно ставилась разными авторами, в частности, Л. Н. Шевриным, о чем сказано в обзоре М. Сапира и О. Харлампович13. Очень хорошо известна проблема слов для свободных бернсайдовых полугрупп, заданных тождеством х1 = ,т3 — см. Свердловскую тетрадь14. Для случая п = 1 хорошо известна задача, ставившаяся Бжозовскн15 о регулярности классов слов, равных данному в таких полугруппах (последнее тесно связано с проблемой слов).
Теперь расскажем о работах в данном направлении. Во-первых, случай т = 1 непосредственно сводится к теории групп, как следует из работы Кадоурека и Полака16. Далее, обе проблемы — проблема слов и проблема регулярности — были решены недавно Мак-Каммондом17 для т > 6 я независимо де Лукой и Варриккио18 для т > 5, п = 1.
Важно заметить, что проблема равенства слов (термов) для свободных алгебраических систем может быть весьма сложной или даже вовсе неразрешимой — в качестве примера можно привести работу Фриза19, где доказывается неразрешимость проблемы равенства для свободных модулярных решеток.
Помимо проблемы слов для групп и полугрупп мы будем затрагивать также такие темы, относящиеся к комбинаторной теории этих алгебраических систем, как уравнения в свободных группах и полугруппах, автоморфизмы свободных групп. Говоря об уравнениях, следует упомянуть фундаментальные работы Г. С. Мака-нина об алгоритмической разрешимости уравнений в свободных полугруппах2' и
US. V. ivanov. The free Burrtside groups of sufficiently large exponents. — Int. J. of Aig. and Comput., 1994, v.4, pp. 1-308.
12И. Г. Лысёиок. Бесконечные бернсайдовы группы четного периода. — Известия РАН, сер. ыа-тем., 1996, т.60, №, с.3-224.
130. G. Kharlampovich and М. V. Sapir. Algorithmic problems in varieties. — Int. J. of Alg. and Comput., v.5,.№4-5 (1995).
14Свердловская тетрадь. Нерешенные задачи теории полугрупп. — Выпуск третий. Свердловск, 1989.
15J. 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. 23-47.
16J. Kadourek and L. Polak. On free semigroups satisfying xr c: . — Simon Stevin. 1990, v.64, pp. 3-19.
1TJ. McCammond. The solution to the word problem for the relatively free semigroups satisfying T" = Ta+6 with a > 6. — Int. J. of Algebra and Comput., 1991, v.l, m, 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Г. C. Маканин. Проблема разрешимости уравнений в свободной полугруппе. — Матем. сб., 1977, т.ЮЗ, ]*2, с.147-236.
свободных группах21, а также работу А. А. Разборова22 об описании решений уравнений в свободных группах. Что касается автоморфизмов свободных групп, то здесь мы будем пользоваться результатами Мак-Кула23 о стабилизаторах элементов, а также важной теоремой Герстена о неподвижных точках автоморфизмов свободных групп24.
Выше шла речь о проблематике, использующей в основном комбинаторные методы. Далее речь пойдет о вопросах, использующих для своего решения геометрические методы. В настоящее время разделы комбинаторной теории групп, использующих геометрические подходы, весьма обширны, и в качестве очень актуальной темы можно упомянуть гиперболические в смысле Громова и автоматные группы. Мы же будем говорить конкретно о подходе, связанном с диаграммами.
В теории групп диаграммы ван Кампена (или диаграммы сокращений) систематически изучаются с конца 60-х годов. Глава V уже упоминавшейся монографии Линдона и Шуппа полностью посвящена этому вопросу. Из более современных работ укажем монографию А. Ю. Ольшанского25, в которой на основе диаграмм развит мощный метод, приведший к построению большого количества групп с новыми свойствами в работах как самого автора монографии, так и его учеников. Наша кандидатская диссертация была посвящена именно использованию этого подхода для построения новых групп, см. по этому поводу работы автора28,27,33. Этот же подход был вновь применен автором в недавней работе [13].
В теории полугрупп диаграммы были использованы несколько позже. Это было сделано впервые в работе Е. В. Кашинцева29. Впоследствии теории полугрупповых диаграмм были посвящены отдельные работы, например, работа Реммерса30. Диаграммы в группах и полугруппах являются эффективным средством, полезным во многих исследованиях. Помимо проблемы слов, их можно эффективно применять для исследования вложимости полугрупп в группы — см. работу Кашинцева31, а также
21Г. С. Маканин. Уравнения в свободных группах. — Изв. АН СССР, сер. матем., 1982, т.46, С.Ш9-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.
2SA. Ю. Ольшанский. Геометрия определяющих соотношений в группах. — М., Наука, 1989.'-'
26В. С. Губа. Об условиях, при которых 2-порожденные подгруппы в группах с малым сокращением свободны.— Известия вузов. Математика. 1986, №7, с. 12-19.
VB. С. Губа. Конечно-порожденная полная группа. — Известия АН СССР, сер. матем., 1986, т.50, №5, с.883-924.
23В. С. Губа. Конечно-порожденная простая группа со свободными 2-порождешшми подгруппами. — Сиб. матем. ж., 1986, т.27, JS65, с.50-67.
29Е.. В. Кашинцев. Графы и проблема слов для конечно-представленных полугрупп. — Уч. зап. Тульского пед. института, 2 (1970), 290-302.
30J. Н. Remmers. On the geometry of semigroup presentations. — Advances in Math:, v.36(3), 1980, pp.283r296
31E. V. Kashintsev. Small cancellation conditions and embeddability of semigroups in groups. — Int.
для исследования проблем делимости в полугруппах и во многих других случаях.
Особого рассмотрения требует тема, касающаяся групп диаграмм. Это новый класс групп, элементами которых являются полугрупповые диаграммы. Исследование этого класса групп является новым направлением, промежуточным между теорией групп и полугрупп. Первые результаты в этом направлении получены в диссертации Килибарды32. К этим группам независимо пришел также Прайд33, поставивший о них ряд открытых проблем.
Цель работы и научная новизна. Целью диссертации является решение ряда известных проблем комбинаторной теории групп и полугрупп, а также теории формальных языков. При решении применяются как комбинаторные, так и геометрические методы. К главным результатам диссертации можно отнести следующие:
Доказано, что системы уравнений от конечного числа неизвестных в свободных группах эквивалентны своим конечным подсистемам.
Доказана гипотеза Эренфойхта о тестовых множествах.
Доказано, что подгруппа неподвижных точек любого множества автоморфизмов свободной группы конечного ранга является конечно-порожденной.
Доказано, что свободная бернсайдова полугруппа с тождеством Хт = А"+'' имеет разрешимую проблему равенства слов при т > 3, п > 1.
При тех же ограничениях натип доказано, что класс конгруэнтности любого слова в этих полугруппах есть регулярный язык.
Завершена начатая Е. В. Кашинцевым классификация условий малого сокращения, необходимых для вложения полугрупп в группы. В терминах этих условий (см. определения ниже) доказано, что ' _
- полугруппы класса Л'|. вложимы в группы;
— при любом q существуют полугруппы с сокращением, не вложимые в груп
пы, принадлежащие классу А'|.
Доказано, что класс групп диаграмм содержит группу Р. Томпсона 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, Lincoln, 1994.
33S. J. Pride. Low-dimensional homotopy jheory for monoids. — Int. J. of Alg. and Comput., v.5. H6, 1995, pp. 631-649.
Решена проблема сопряженности для групп диаграмм над полугрупповыми копредставлеииями с разрешимой проблемой слов, включая проблему сопряженности в группе Р. Томпсона.
Описаны перестановочные элементы в группах диаграмм и централизаторы элементов.
Показано, что факторгруппы по коммутанту групп диаграмм являются свободными абелевыми, что дает ответ на вопрос Прайда.
Кроме того, в диссертации получен ряд результатов, относящихся к проблеме слов для полугрупп с одним определяющим соотношением. Так, для полугрупп вида {а,Ь | bQa = о) Доказана равносильность трех алгоритмических проблем: проблемы равенства, проблемы левой делимости и проблемы правой делимости. При исследовании вопросов о вложимости полугрупп в группы дан ответ на вопрос 3.47 из Свердловской тетради.
Все результаты диссертации являются новыми.
Практическая и теоретическая ценность. Работа носит теоретический характер. Ее результаты могут быть применены в различных разделах теории групп и полугрупп, в теории формальных языков. Развитые в диссертации вопросы важны для дальнейших исследований по проблеме слов в группах и полугруппах, для изучения групп диаграмм. Многие доказанные в диссертации теоремы могут быть включены в спецкурсы для студентов и аспирантов.
Апробация работы. Результаты автора, вошедшие в диссертацию, докладывались на многочисленных научных семинарах у нас в стране и за рубежом: семинары в МГУ — в течение 1984-1996 гг. — по теории групп (рук. профессора А. Л .Шмель-кия и А. Ю. Ольшанский), по алгоритмическим проблемам алгебры (рук. чл.-корр. РАН С. И. Адян), научно-исследовательский семинар кафедры высшей алгебры (зав. . — чл.-корр. РАН А. И. Костршшн); в 1992 г. и 1996 г. — семинар в Уральском roc- . университете, г. Екатеринбург (рук. проф. Л. Н. Шеврии); в университетах Великобритании (Глазго, Эдинбург, Манчестер) в 1993-1995 гг., США (Нью-Йорк, Беркли, Линкольн, Сакраменто, Чико) в 1994-1995 гг., Франции (Париж) в 1996 г. Результаты диссертации докладывались на XVIII Всесоюзной алгебраической конференции (Кишинев, 1985), Школе по теории алгебраических систем (Омск, 1985), XI Всесоюзном симпозиуме по теории групп (Кунгурка, 1989), Сибирских школах "Алгебра и Анализ" (Иркутск, 1992-1993 гг.), на международных конференциях по теорий полугрупп (Йорк, Великобритания - 1993 г.. Порту, Португалия - 1994 г., Санкт-. Петербург, Россия - 1995 г.).
Публикации. Основные результаты диссертации опубликованы в 13 работах автора, указанных в конце автореферата.
Структура и объем диссертации. Диссертация состоит из введения и шести глав. Первая глава содержит основные определения; в главах 2-6 излагаются результаты диссертации. Для набора текста диссертации использована издательская система LKTgX. Полный объем диссертации составляет 184 страницы, из которых 10 страниц занимает библиография, включающая 144 наименования.