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

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

003491653

Кузнецова Анна Николаевна

НЕКОТОРЫЕ АЛГОРИТМИЧЕСКИЕ ПРОБЛЕМЫ В ГРУППАХ АРТИНА БОЛЬШОГО И ЭКСТРАБОЛЬШОГО ТИПА

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

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

1 1 ф£В 2010

Москва-2010

003491653

Работа выполнена на кафедре алгебры, математического анализа и геометрии факультета Математики, физики и информатики Тульского государственного педагогического университета им. Л.Н. Толстого.

Научный руководитель: доктор физико-математических наук,

профессор Безверхний Владимир Николаевич

Официальные оппоненты: доктор физико-математических наук,

профессор Шмелькин Альфред Львович

кандидат физико-математических наук, доцент Пронина Елена Владиславовна

Ведущая организация: Ивановский государственный университет

Защита диссертации состоится «_]_» марта 2010 г. в 17-00 часов на заседании Диссертационного совета Д 212.154.32 при Московском педагогическом государственном университете по адресу: 107140, г. Москва, ул. Краснопрудная, д. 14, математический факультет МПГУ, ауд. 301.

С диссертацией можно ознакомиться в библиотеке Московского педагогического государственного университета по адресу: 119992, г. Москва, ул. Малая Пироговская, д. 1.

Автореферат разослан » 2010 г.

Ученый секретарь

Диссертационного совета Муравьева О.В.

Общая характеристика работы

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

Проблемы равенства, сопряженности слов и изоморфизма получили отрицательное решение в работах П.С. Новикова. Им был построен пример конечно определенной группы с неразрешимой проблемой равенства слов1, тем самым была доказана неразрешимость проблемы сопряженности слов в классе конечно определенных цзупп. П.С. Новиков построил пример группы с разрешимой проблемой равенства2, но неразрешимой проблемой сопряженности слов. Используя полученные результаты, им была доказана неразрешимость проблемы изоморфизма. Таким образом, была показана неразрешимость основных алгоритмических проблем в классе конечно определенных групп. Поэтому возникла задача изучения данных проблем в определенных классах конечно определенных фупп. В связи с этим большой интерес представляет собой класс конечно определенных групп Артина и Кокстера.

Группа Артина - это группа в, заданная системой образующих ап г е/, |/|<оо, и системой определяющих соотношений аааг.. = ада^..., еI, где слова, стоящие слева и справа, состоят из т чередующихся букв а, и а), ¡Ф _/; т - элемент симметрической матрицы Кокстера (>яД , имеющей вид

1 Новиков П.С. Об алгоритмической неразрешимости проблемы тождества слов в теории групп // Труды математического института АН СССР. - 1955.

2 Новиков П.С. Неразрешимость проблемы сопряженности в теории групп // Изв. АН СССР, сер. Мат. - Т. 18.

-С. 4X5-524.

т.,

*

* * 1

v

причем, при г Ф j, т.. = mß, т. > 2. Если к определяющим

соотношениям группы Артина добавить соотношения вида: V; = 1, получим копредставление соответствующей группы Кокстера. Группы Кокстера, со времени их введения Кокстером в 1935 году, были подробно изучены. Обстоятельное изложение полученных результатов имеется у Бурбаки3.

Класс групп Артина содержит группы кос, копредставление которых было получено Артином, решившим в данном классе групп проблему равенства слов, используя геометрические методы4. Алгебраическая теория ipynn кос была построена A.A. Марковым5, который решил проблему равенства аналитическим методом. Проблема сопряженности в группе кос была решена Ф. Гарсайдом6 и независимо Г.С. Маканиным7. В 1971 г. Г.С. Маканин доказал, что нормализатор любого элемента групп кос конечно порожден, и указал алгоритм построения образующих этого нормализатора8. Г.Г. Гурзо путем обобщения метода, описанного в работе8, получила алгоритм для нахождения образующих централизатора конечного множества элементов группы кос9. Отметим, что до настоящего времени неизвестна разрешимость проблемы равенства в конечно определенных группах Артина.

В 1972 году Брискорном и Сайто был введен класс групп - группы Артина конечного типа10. Группа Артина называется группой Артина конечного типа, если соответствующая ей группа Кокстера конечна. Брискорн и Сайто доказали разрешимость проблем равенства и сопряженности слов в данном

Бурбаки Н. Группы и алгебры Ли. - М.: Мир, 1972. * Artin Е. Theorie der Zöpfe //Abh. math. Semin. Univ. Hamburg, 1925. - V. 4. - P. 47-72.

5 Марков A.A. Основы алгебраической теории кос II Труды математического института АН СССР. - 1945. -№16.

6 Гарсайд Ф. Группы кос и другие группы//Математика: Сб. переводов. - 1970. - №4.-С. 113-132.

' Маканин Г.С. Проблема сопряженности в группах кос II Доклады АН СССР. - 1968.—Т.182. - №3. - С. 495496.

' Маканин Г.С. О нормализаторах группы кос // Математический сборник. -197 J. - Т. 86. - №2. - С. 171 -179. ' Гурзо Г.Г. О централизаторах конечных множеств элементов группы кос // Математические заметки. -

1985.-Т. 37. -№1. - С. 3-6.

10 Брискорн Э., Сайто К. Группы Артина и группы Кокстера // Математика: Сб. переводов. -1974. - №6. - С. 56-79.

классе групп. Для групп Артина конечного типа В.Н. Безверхним и В.А. Гринблатом было получено решение проблемы вхождения в циклическую подгруппу". Ю.Э. Трубицын12 и В.А. Гринблат13 доказали разрешимость проблемы обобщенной сопряженности слов в данном классе групп. Также для групп Артина конечно типа В.Н. Безверхний доказал неразрешимость проблемы вхождения в неприводимые группы Артина конечного типа14.

В 1983 году К. Аппелем и П. Шуппом был выделен класс групп Артина большого и экстрабольшого типа15.

Если все числа т. при * } симметрической матрицы Кокстера для групп

Артина (Кокстера) больше либо равны трем, то группы называются группами Артина (Кокстера) большого типа. Если все числа т1} при / *)

симметрической матрицы Кокстера для групп Артина (Кокстера) больше трех, то группы называются группами Артина (Кокстера) экстрабольшого типа. Для групп Артина и Кокстера экстрабольшого типа П. Шуппом и К. Аппелем было получено решение проблем равенства и сопряженности слов15. К. Аппелем и независимо В.Н. Безверхним была решена проблема сопряженности слов16 в группах Артина большого типа; В.Н. Безверхний получил решение обобщенной сопряженности слов для групп Артина большого типа17.

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

11 Безверхний В.Н., Гринблат В.А. О проблеме вхождения в группах Артина конечного типа // Сибирский математический журнал. -1982. - Вып. 23. - №4. - С. 19-28.

12 Трубицын Ю.Э. О нормализаторах конечных множеств в группах Артина конечного типа // Алгоритмические проблемы теории групп и полугрупп. Межвузовский сборник научных трудов. Тула: Тул. гос. пед. ин-т, 1986. - С. 68-71.

13 Гринблат В.А. О нормализаторах групп Артина // Алгоритмические проблемы теории групп и полугрупп. Тула,-1981.-С. 82-94.

" Безверхний В.Н. Неразрешимость проблемы вхождения в группах Артина конечного типа // Сибирский математический журнал. -1985. - Т. 26. - №5. - С. 27-42.

15 Appel К., Schupp P. Aitin groups and infinite Coxeter groups // Invenf. Math.- 1983. - V. 72. - P. 201-220.

" Безверхний В.Н. Решение проблемы сопряженности слов в группах Артина большого типа // Алгоритмические проблемы теории групп и полугрупп: Межвузовский сборник научных трудов. - 1989. -Т. 5.-J&1.-C. 1-38.

17 Безверхний В.Н. Решение обобщенной сопряженности слов в группах Артина большого типа// Фундаментальная и прикладная математика. -1999. -Т J. -Jfel. -С.1-38.

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

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

1. доказано, что группы Артина большого типа свободны от кручения;

2. решена проблема вхождения в циклическую подгруппу в группах Артина большого типа;

3. показана разрешимость проблемы слабой степенной сопряженности в группах Артина большого типа;

4. получено описание диаграмм над конечно порожденными группами Артина экстрабольшого типа;

5. установлена разрешимость проблемы степенной сопряженности слов в группах Артина экстрабольшого типа;

6. решена проблема пересечения циклических подгрупп в группах Артина экстрабольшого типа.

Методы исследования. При доказательстве основных результатов в работе используется метод диаграмм, введенный ван Кампеном в 1933 году и вновь переоткрытый Р. Линдоном в 1966 году18.

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

" ЬМоп К. Оп ИеЬп'з а^огйт. МаА. Апп. -1966 - V. 166. - Р. 208-228

4

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

Апробация результатов. Основные результаты диссертации докладывались на семинаре "Алгоритмические проблемы теории групп и полугрупп" под руководством профессора Безверхнего В.Н. (Тула, 2005-2008 гг.), на международной научно-практической конференции "Л.Эйлер и российское образование, наука и культура" (Тула, 2007 г.), международной алгебраической конференции, посвященной 100-летию со дня рождения А.Г. Куроша (МГУ им. М.В. Ломоносова, 2008 г.), семинаре по теории групп кафедры Высшей алгебры МГУ им. М.В. Ломоносова под руководством профессоров А.Л. Шмелькина, А.Ю. Ольшанского и доцента A.A. Клячко (МГУ им. М.В. Ломоносова, 2009 г.).

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

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

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

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

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

Пусть С = (А\Я) - группа Артина большого типа, где А - (аДб/-множество образующих, а Я- симметризованное множество определяющих соотношений. Пусть V/ - произвольный элемент из б, обозначим через его длину в свободной группе Р, заданной на образующих А = (а,),е;, а через ||и|- его слоговую длину в группе рассматривая Р в виде свободного произведения бесконечных циклических групп ^ = {а,).

Свободно приведенное слово и» группы Артина большого типа назовем Я-приводимым (или Я-сократимым), если м> содержит подслово 5, являющееся подсловом некоторого соотношения геЛ, г = 56, где |б|<2. В противном

случае слово у; назовем Я — неприводимым или Я -приведенным.

Циклически /{-приведенное слово у/ группы Артина большого типа назовем Я- приводимым (или Я- сократимым), если в его некоторой циклической перестановке и>" можно выделить подслово где каждое

содержится в некоторой группе (7^ и является подсловом соотношения

е Я, причем, при (-1 и ( = п имеет место

М-М-М-Ш-М-М-1 и да» «■ 1<'<». 1К1НК,!И>

|&,|| = 2. В противном случае слово V/ назовем Я - приведенным.

Второй параграф посвящен элементам бесконечного порядка в группах Артина большого типа и доказательству следующего результата:

Теорема 1.1. Группа Артина большого типа свободна от кручения.

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

Проблема вхождения в циклическую подгруппу заключается в нахождении алгоритма, позволяющего определить, является ли в группе О слово и» степенью некоторого слова V, то есть м> = у", п > 1.

Проблема слабой степенной сопряженности слов заключается в нахождении такого алгоритма, что для любых слов е. й и V £ (и>) можно определить, существует ли слово г Еб, что гЛхг е (и»).

В первом параграфе второй главы получен алгоритм, строящий по циклически Я, Я -несократимому слову н> из группы Артина большого типа в сопряженное с ним или с его квадратом в в слово и>0, любая степень которого Я, Я - несократима.

Обозначим через 6М граничный цикл диаграммы М. Граничная область £) диаграммы М называется правильной, если дОпдМ- связное множество. В противном случае область О называется неправильной.

Следующие три утверждения описывают структуру диаграммы в случае решения проблемы вхождения в циклическую подгруппу в группах Артина большого типа. Символом !'(£>) обозначено число внутренних ребер в граничном цикле области Д а(у) - начальная точка пути у, а>(у) - конечная точка пути у.

Лемма 2.4. Пусть М - приведенная диаграмма, являющаяся диском (граничный цикл (дМ) - простая замкнутая кривая), дМ - у и 8; <р{у), (р(8)- Я,Я-несократимые слова; в М больше двух областей и нет неправильных областей. Тогда существуют области Д и Ов е М такие, что

1) Д пдМ и Д пдМ - связные множества, а(у) = а(8) = А, 0(у) = о(6) = В.

2) ЭД пу&0, <ЗД п8*0, дО„пу*0, йДп5* О и все четыре множества содержат ребра.

Следствие 2.2 (из леммы 2.4). Если в диаграмме М, удовлетворяющей условиям леммы 2.4, более двух областей и нет неправильных областей, то диаграмма М имеет следующую структуру: /(Д ) - /(Д)~2; все другие граничные области в М имеют от трех до пяти внутренних ребер. Если О,,..., Д - области, граничащие су, Д = Д, Д = Д; Д,.... Д - области, граничащие с 8, Д = Д, Д = Д и они пронумерованы по ходу следования при движении от А к В вдоль у и 8, то области с ¡{О) = 5 и ¡(П) = 3 чередуются вдоль границ у и 8, число областей с внутренней степенью 3 равно числу областей с внутренней степенью 5 либо на одну больше; причем, если не учитывать области с г{В) = 4, то любые две области с внутренней степенью 5 разделены областью с внутренней степенью 3 и области с тремя внутренними ребрами расположены в самой левой и самой правой позициях вдоль у и 8.

Лемма 2.5. Пусть М - приведенная диаграмма, являющаяся диском (граничный цикл (дМ) — простая замкнутая кривая), 5М = уи8; <р(у), <р(8) - Я, Я - несократимые слова. Тогда число областей, граничащих с у и 8 одинаково.

Далее доказана основная теорема первого параграфа:

Теорема 2.3. В группе Артина большого типа разрешима проблема вхождения в циклическую подгруппу.

Во втором параграфе второй главы исследуется разрешимость проблемы слабой степенной сопряженности слов в группах Артина большого типа. Для этого введены понятия острова и полуострова19 в кольцевой диаграмме, специального слоя в кольцевой диаграмме.

Пусть М - кольцевая связная Л-диаграмма, являющаяся диаграммой сопряженности слов из группы Артина большого типа. Тогда внешний (внутренний) слой из М назовем специальным слоем, если образующие его области £>, ,...,£>„, удовлетворяют следующим условиям:

1) V/, 1 < } < п -1 г\ есть ребро;

2) Д п Ц, есть ребро;

3) /(Д) = 3, /(£>2) = /(Д) = ... = /фп) = 4.

Доказано, что кольцевая диаграмма сопряженности слов не содержит специального слоя:

Лемма 2.9. Пусть М— приведенная кольцевая диаграмма сопряженности слов м>а" и \а, дМ = у и<5\ <КУ)-Щ> <р(3)-у 0; слово Я, - несократимо и не является циклически Я-сократимым, любая степень слова м>0 Л,Я -несократима. Тогда ни один из граничных слоев диаграммы Мне является специальным.

Далее установлена разрешимость следующей алгоритмической проблемы в группах Артина большого типа:

Теорема 2.5. В группе С - группе Артина большого типа алгоритмически разрешима проблема слабой степенной сопряженности, то есть по любым словам е б таким, что уй(н') можно выяснить, существует ли целое

число п такое, что слова V сопряжены в группе б.

Третья глава посвящена изучению конечно порожденных групп Артина экстрабольшого типа, а именно описанию структуры диаграмм над группами

19 Паршикова Е.В. Проблема слабой степенной сопряженности в группах с условием С(4)&Т(4) // Алгоритмические проблемы теории групп и полугрупп: Межвузовский сборник научных трудов. - Тула, 2001.-С. 179-185.

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

Проблема степенной сопряженности слов заключается в следующем: найти алгоритм, с помощью которого по любым словам V и у/ группы С? можно определить, существуют ли такие ненулевые целые числа от, и, что слова у", и>"сопряжены в группе (7.

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

существует ли ненулевые целые числа ппт такие, что слова и равны в группе (7.

В первом параграфе третьей главы введены преобразования диаграммы, которые позволяют получить минимальную диаграмму, соответствующую изучаемой группе, сформулированы определения деновской области (что соответствует Я-сокращению), полосы (что соответствует Я -сокращению).

Пусть (7 = - группа Артина экстрабольшого типа, где А - множество образующих, а Л - симметризованное множество определяющих соотношений.

Свободно приведенное слово ю группы Артина экстрабольшого типа называется Я -приводимым (или Я-сократимым), если н> содержит подслово я, являющееся подсловом некоторого соотношения г е Я, г = $Ь, где |б| < |х|. В противном случае слово ы называется Л - приведенным.

Перечислим основные результаты первого параграфа:

Лемма 3.3. В группе Артина экстрабольшого типа

=(а1,а1;(а1а^т' = (а^для любого нетривиального ¡{-приведенного

и'еС<\ можно эффективно определить, существуют ли и,, к/ , г = 1,? такие, что в С1; выполняется равенство

ы = а": а) а"'...а)'а"'"..л"'а) (1),

причем >у и слово в правой части равенства (1) начинаются и заканчиваются на разные буквы, ||и| £ ..л*' | и слово

а"'а*,а"г...а*,а""'..д"'а*? имеет минимальную слоговую длину; если такой набор целых чисел существует, то он единственен.

Лемма 3.4. Пусть м> - нетривиальное К-приведенное слово из группы Артина экстрабольшого типа = (апау,(а,а^ '' = Тогда

существует алгоритм, выписывающий показатели степеней образующих и,, к1 е 2, I = 1,/ в равенстве

и> = в? а1; а? ...а*' а,..л? а; (1),

причем ||м|> |д"'а*'а"\..а',| и слово а"'а)'а"' -а ¡а"-' ..л"'а) имеет

минимальную слоговую длину.

Лемма 3.5. Существует алгоритм, позволяющий для любого циклически приведенного слова и> группы Артина экстрабольшого типа выяснить, является ли ю Л-приведенным.

Лемма 3.7. Пусть М - К-приееденная связная односвязная диаграмма группы Артина экстрабольшого типа, не содержащая деновских областей. Тогда Мявляется однослойной диаграммой.

Будем говорить, что дМПдО есть правильная часть диаграммы М, если ЭМПбО есть объединение последовательности замкнутых ребер /,,...,/„, которые встречаются в данном порядке в некотором граничном цикле для £> и в некотором граничном цикле для М.

Пусть М - приведенная связная односвязная Л-диаграмма группы Артина экстрабольшого типа с граничными циклами у и 6. Тогда последовательность граничных областей п> 2 образует полосу

Я = и О, в М, если

ы

1) V/, 1 ££ и дМ П ЗЦ - правильная часть М;

2) V/, границы областей Д и Дч, пересекаются по ребру;

3) |гпздН<Упдд|+2,|гп0дИ<^ад|+2;

|упЗД| = |<Уп5Д| У/, 1 < j <п.

Циклически Ä-приведенное слово w группы Артина экстрабольшого типа назовем R - приведенным или специально R-приведенным, если w является 1раничной меткой приведенной диаграммы, не содержащей полос.

Лемма 3.8. Существует алгоритм, позволяющий для любого циклически R-приведенного слова w из группы Артина экстрабольшого типа выяснить, является ли w специально R-приведенным.

Из лемм 3.5 и 3.8 следует результат К.Аппеля и П.Шуппа о разрешимости проблемы равенства слов в группах Артина экстрабольшого типа15.

Второй параграф третьей главы полностью посвящен проблеме степенной сопряженности слов в группах Артина экстрабольшого типа. Доказана основная теорема:

Теорема 3.3. В группе Артина экстрабольшого типа G алгоритмически разрешима проблема степенной сопряженности, то есть по любым словам w.veG можно выяснить, существует ли ненулевые целые числа пит такие, что слова w", v" сопряжены в группе G.

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

Теорема 3.4. В группе Артина экстрабольшого типа G алгоритмически разрешима проблема пересечения циклических подгрупп, то есть по любым словам w, v б G можно выяснить, существует ли такие ненулевые целые числа пит, что слова W и v" равны в группе G.

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

Публикации автора по теме диссертации

[1] Безверхний В.Н., Кузнецова А.Н. Проблема вхождения в циклическую подгруппу в группах Артина большого и экстрабольшого типа // Известия Тульского государственного университета. Серия Математика. Механика. Информатика. - 2005. - Т. 11. - С. 76-93. - 1,12 пл. (Авторский вклад 70%) (Журнал включен в перечень изданий. См. Бюллетень № 4 за 2005 г.).

[2] Кузнецова А.Н. Разрешимость проблемы слабой степенной сопряженности в группах Артина большого типа // Известия Тульского государственного университета. Естественные науки. -2008. - Выпуск 2. - С. 29-39. - 0,68 пл.

[3] Безверхний В.Н., Кузнецова А.Н. О кручении групп Артина большого типа // Чебышевский сборник. - 2005. - Т. 6. - Выпуск 1. - С. 13-21.- 0,56 п.л. (Авторский вклад 70%).

[4] Безверхний В.Н., Кузнецова А.Н. Проблема корня в группах Артина большого типа // Л.Эйлер и российское образование, наука и культура: Материалы международной научно-практической конференции - Тула: Изд-во Тул.гос.пед.ун-та им.Л.Н.Толстого, 2007. - С. 36-43. - 0,5 п.л. (Авторский вклад 70%).

[5] Безверхний В.Н., Кузнецова А.Н. Проблема слабой степенной сопряженности в группах Артина большого типа II Л.Эйлер и российское образование, наука и культура: Материалы международной научно-практической конференции - Тула: Изд-во Тул.гос.пед.ун-та им.Л.Н.Толстого, 2007. - С. 195-202.-0,5 п.л. (Авторский вклад 70%).

[6] Безверхний В.Н., Кузнецова А.Н. Разрешимость проблемы степенной сопряженности слов в группах Артина экстрабольшого типа // Чебышевский сборник. - 2008. - Т. 9. - Выпуск 1(25). - С. 50-69. - 1,25 п.л. (Авторский вклад 70%).

[7] Кузнецова А.Н. О пересечении циклических подгрупп в группах Артина экстрабольшого типа // Вестник Тульского государственного

13

университета. Дифференциальные уравнения и прикладные задачи. -2008. - Выпуск 1. - С. 76-86. - 0,68 п.л. [8] Безверхний В.Н., Кузнецова А.Н. Разрешимость проблем степенной сопряженности слов и пересечения циклических подгрупп в группах Артина экстрабольшого типа II Международная алгебраическая конференция, посвященная 100-летию со дня рождения А.Г. Куроша. Тезисы докладов. - Москва: Изд-во Московского гос. ун-та, 2008. - С. 33-34,- 0,12 п.л. (Авторство не разделено).

Подп. к печ. 25.01.2010 Объем 1 пл. Заказ №. 15 Тир 100 экз. Типография МПГУ

Введение.

Глава 1. Группы Артина большого типа. Элементы бесконечного порядка.

1. Диаграммы над конечно порожденными группами Артина большого типа.

2. Элементы бесконечного порядка в группах Артина большого типа.

Глава 2. Проблемы вхождения в циклическую подгруппу и слабой степенной сопряженности слов в группах Артина большого типа.

1. Проблема вхождения в циклическую подгруппу,.34'

2. Проблема слабойстепенной сопряженности слов.

Глава 3. Группы Артина экстрабольшого типа. Проблемы степенной сопряженности^ слов и пересечения циклических подгрупп.

1. Диаграммы над конечно порожденными группами Артина экстрабольшого типа.

2. Проблема степенной сопряженности слов.

3. Проблема пересечения циклических подгрупп.

Актуальность темы

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

Проблемы равенства, сопряженности слов и изоморфизма получили отрицательное решение в работах П.С. Новикова. В [22] им был построен пример конечно определенной группы с неразрешимой проблемой равенства слов, тем самым была доказана неразрешимость проблемы сопряженности слов В1 классе конечно определенных групп. В [23] П.С. Новиков построил пример группы с разрешимой проблемой равенства, но неразрешимой проблемой сопряженности слов. Используя полученные результаты, им была доказана неразрешимость, проблемы изоморфизма. Таким образом, была показана неразрешимость основных алгоритмических проблем в классе конечно определенных групп. Поэтому возникла задача изучения данных проблем в отдельных классах конечно определенных групп. В связи с этим большой интерес представляет собой класс конечно определенных групп Артина и Кокстера.

Группа Артина — это группа О, заданная системой образующих а1, е/, |/|<оо, и системой определяющих соотношений ар. а^. — а ар. .^ е /, где слова, стоящие слева и справа, состоят из тц чередующихся букв а1 и а , у; тц- элемент симметрической матрицы Кокстера то )Мс/ > имеющей вид

1 т\ ту . * к причем, при / Ф у, т1} = т}1, тч> 2.

Если к определяющим соотношениям группы Артина добавить соотношения вида: V/ е /, а] = 1, получим копредставление соответствующей группы Кокстера. Группы Кокстера, со времени^ их введения Кокстером в 1935 году, были подробно изучены. Обстоятельное изложение полученных результатов имеется у Бурбаки [12].

Класс групп Артина содержит группы кос, копредставление которых было получено Артином, решившим в данном классе групп проблему равенства слов, используя геометрические методы [28]. Алгебраическая' теория групп кос была построена A.A. Марковым [20], который; решил проблему равенства аналитическим методом: Проблема сопряженности в группе кос была решена Ф. Гарсайдом [13] и независимо E.G. Маканиным [18]. В 1971 г. Г.С. Маканин [19] доказал, что нормализатор любого элемента групп кос конечно порожден и указал; алгоритм? построения образующих этого нормализатора. Г.Г. Гурзо [15] путем обобщения метода, описанного в [19], получила алгоритм для нахождения образующих централизатора конечного множества- элементовгруппы кос. Отметим, что до настоящего времени неизвестна разрешимость проблемы, равенства в конечно определенных группах Артина;.

В 1972 году Э. Брискорном и К. Сайто [11] был введен класс групп -группы Артина конечного типа. Группа Артина- называется группой Артина конечного типа, если соответствующая em группа Кокстера конечна. Э. Брискорн и К. Сайто доказали разрешимость проблем равенства и сопряженности слов в данном классе групп [11]. Для групп Артина конечного типа В.Н. Безверхним; и В.А. Гринблатом было получено решение проблемы вхождения в циклическую подгруппу [8]. Ю.Э. Трубицин [25] и В.А. Гринблат [14] доказали разрешимость, проблемы обобщенной сопряженности слов в данном классе групп. Также для групп Артина конечно типа В.Н. Безверхний доказал неразрешимость проблемы вхождения в неприводимые группы Артина конечного типа [2].

В 1983 году К. Аппелем и П. Шуппом был выделен класс групп, Артина большого и экстрабольшого типа [27].

Если все числа тц при i Ф j симметрической матрицы Кокстера для групп Артина (Кокстера) больше либо равны трем, то группы называются группами Артина (Кокстера) большого типа. Если все числа ту при: i Ф j симметрической матрицы Кокстера для групп Артина (Кокстера) больше трех, то группы называются группами Артина (Кокстера) экстраболъшого типа. Для групп Артина и Кокстера экстрабольшого типа П. Шуппом и К. Аппелем [27] было получено решение проблем равенства и сопряженности' слов. К. Аппелем и независимо В.Н. Безверхним была решена проблема сопряженности слов в группах Артина большого типа [4]; В.Н. Безверхний получил решение обобщенной сопряженности слов для групп Артина большого типа [5].

Цель работы

Данная работа посвящена описанию решения некоторых алгоритмических проблем в конечно порожденных группах Артина большого и экстрабольшого типа.

1. Доказать, что группы Артина большого типа свободны от кручения.

2. Дать решение проблемы вхождения в циклическую подгруппу в группах Артина большого типа.

3. Получить решение проблемы слабой степенной сопряженности в группах Артина большого типа.

4. Доказать разрешимость проблемы степенной сопряженности в группах Артина экстрабольшого типа.

5. Описать решение проблемы пересечения циклических подгрупп в группах Артина экстрабольшого типа.

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

Краткое описание работы

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

-сокращению), (5-г)-области, полосы (что соответствует Я -сокращению).

Во втором - доказана

Теорема 1.1 [30]. Группа Артина большого типа свободна от кручения.

Вторая глава содержит два параграфа и посвящена решению проблем вхождения в циклическую подгруппу и слабой степенной сопряженности' слов в группах Артина большого типа.

Проблема вхождения в циклическую подгруппу заключается в следующем: найти алгоритм, позволяющий определить, является ли в группе О слово м> степенью некоторого слова v, то есть ж = V", п> 1.

Проблема слабой степенной сопряженности заключается в нахождении такого алгоритма, что для любых слов >у,уеОг и V £ (м?) можно определить, существует ли такое слово г е , что е .

В первом параграфе доказываются

Лемма 2.1 [311. Пусть слово м> группы (г Артина большого типа циклически Я, Я — несократимо. Существует алгоритм, строящий по слову -и> сопряэюенное с ним или с его квадратом в группе (7 слово м?0, любая степень которого Я,Я — несократима.

Лемма 2.4 [31]. Пусть М — приведенная диаграмма, являющаяся диском (граничный цикл (дМ) — простая замкнутая кривая), дМ — у kj S ; ср(у\ ф(8)~ —несократимые слова; в М больше двух областей и нет неправильных областей. Тогда существуют области D x и DH е М такие, что

1) Da п дМ и DB Г\ дМ - связные множества, ос{у) = а(8) — А, й)(у) = со(8) = В.

2) dDA с\уф 0, дDa nS^O, dDB слуФ 0; dDB г\0Ф О и все четыре множества содержат ребра.

Замечание (из леммы 2.4) [31]. Для любой области D еМ i(D) е {3,4,5} и в диаграмме М число областей с внутренней степенью-3 равно числу областей с внутренней степенью 5 либо на одну больше, причем любые две области с внутренней степенью 5 разделены областью с внутренней степенью 3, остальные области имеют внутреннюю степень 4.

Символ D™ будет обозначать область диаграммы М, имеющую максимально возможное к внутренних ребер, где т — порядковый номер области.

Следствие 2.2 (из леммы 2.4) [31]. Если в диаграмме М, удовлетворяющей условиям леммы 2.4, более двух областей и нет неправильных областей, то диаграмма М имеет следующую структуру: i(DA) = i(DB) —2; все граничные области в М имеют от трех до пяти внутренних ребер. Если £>,., Ds - области, граничащие с у, DX—DA, Ds=DB; Dx,., Dt - области, граничащие с 8, D, = Dx, Dt=DB и они пронумерованы по ходу следования при двиэюении от А к В вдоль у и 8, то области типа D\{1> 2) и (Je > 2) чередуются вдоль у и 8, причем, если не учитывать области типа D4A(q > 2), то области с тремя внутренними ребрами расположены в самой левой и самой правой позициях вдоль у и 8.

Лемма 2.5 [311. Пусть М — приведенная диаграмма, являющаяся диском (граничный цикл (дМ) — простая замкнутая кривая), дМ — у и 8 ; <Р(у)> ~ — несократимые слова. Тогда число областей, граничащих с у и 8 одинаково.

Теорема 2.3 [31]. В группе Артина большого типа разрешима проблема вхождения в циклическую подгруппу: существует алгоритм, позволяющий по любым словам определить, принадлежит ли слово м> циклической подгруппе (у).

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

Пусть М - кольцевая связная ^-диаграмма, являющаяся диаграммой сопряженности слов из группы Артина большого типа. Тогда внешний (внутренний) слой из М назовем специальным слоем, если образующие его области А. А, удовлетворяют следующим условиям:

1) у/, 1 < ] < п -1, п I) +1 есть ребро;

2) Ц п Д есть ребро;

3) /(А) = з, /(Д) = Д) =. = /(А) = 4.

Доказаны следующие леммы и теоремы:

Лемма 2.9 [351. Пусть М — приведенная кольцевая диаграмма сопряженности слов м>0" и у0, дМ = у^8, (р(у) = , ц>{8) = слово у0 Я,Л —несократимо и не является циклически специально Я-сократимым, любая степень слова и>0 Я, К — несократима. Тогда ни один из граничных слоев диаграммы Мне является специальным.

Лемма 2.11 [35]. Пусть М = М0 - кольцевая приведенная диаграмма

4 2 сопряженности слов м>0" и у0. Тогда п<т.—¡рк>Нго , г&е го ~ самое

1к1 длинное слово из Я.

Теорема 2.5 [35] . В группе (7 — группе Артина большого типа алгоритмически разрешима проблема слабой степенной сопряженности, то есть по любым словам v е С таким, что v £ ("и7}, можно выяснить, существуют ли целое число п и слово геб такие, что слова м?", V сопряжены в группе (7.

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

Проблема степенной сопряженности слов заключается в нахождении алгоритма, с помощью которого по любым словам V и м? группы С можно определить, существуют ли целые числа т; п и существует ли такое слово геС, что слова Vй, сопряжены в группе (г.

Проблема пересечения циклических подгрупп заключается в следующем: по любым словам выяснить, существует ли целые числа п и т такие, что слова и Vя равны в группе С.

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

Лемма 3.3 [34]. В группе Артина экстрабольшого типа (а^а^ар^ " - / для любого нетривиального Я-приведенного слова \veGi; можно эффективно определить, существуют ли и , к1 е2, / = 1,/ такие, что в (51 выполняется равенство ч> = а^а)а^ .ак;а"^ .а]'а) (1), причем и слово в правой части равенства (1) начинаются и п, К. И, К, at aJ1a¡ .а! и слово а"'ак/а:\.ак; и слово a"1 ak¡ а"г .ак; .a"'akj имеет заканчиваются на разные буквы, ||w|| > a"lakla"2 .ak'a¡"1 .a"'ak' имеет минимальную слоговую длину; если такой набор целых чисел существует, то он единственен.

Лемма 3.4 [341. Пусть w — нетривиальное R-приведенное слово из группы Артина экстрабольшого типа Gy =(ai,aJ',{alaj^ " — (яд) Тогда существует алгоритм, выписывающий показатели степеней образующих nt, kt eZ, i — \,t в равенстве w = .ак;апГ.а*а\) (1), причем ||w|| > минимальную слоговую длину.

Лемма 3.5 [34]. Существует алгоритм, позволяющий для любого циклически приведенного слова w группы Артина экстрабольшого типа выяснить, является ли w R-приведенным.

Лемма 3.6 [34]. Пусть М — приведенная связная односвязная R-диаграмма группы Артина экстрабольшого типа, не содержащая деновских областей. Тогда Мне содержит внутренней области.

Лемма 3.7 [34]. Пусть М — приведенная связная односвязная диаграмма группы Артина экстрабольшого типа, dM = y\j8, <р(у), (p{S)~ R - несократимые слова. Тогда М является однослойной диаграммой.

Лемма 3.8 [34]. Существует алгоритм, позволяющий для любого циклически R-приведенного слова w из группы Артина экстрабольшого типа выяснить, является ли w специально R-приведенным.

Из лемм 3.5 и 3.8 [34] следует результат К.Аппеля и П.Шуппа о разрешимости проблемы равенства слов в группах Артина экстрабольшого типа [27].

Второй параграф третьей главы посвящен проблеме степенной сопряженности слов в группах Артина экстрабольшого типа.

Доказана следующая теорема:

Теорема 3.3 [341. В группе Артина экстраболъшого типа (7 алгоритмически разрешима проблема степенной сопряженности, то есть по любым словам >с,УбС можно выяснить, существует ли целые числа п, т и слово г е (7 такие, что слова , V" сопряжены в группе (У.

В третьем параграфе рассматривается разрешимость проблемы пересечения циклических подгрупп в группах Артина экстрабольшого типа. Доказана основная теорема данного параграфа:

Теорема 3.4 [36/. В группе Артина экстраболъшого типа (? алгоритмически разрешима проблема пересечения циклических подгрупп, то есть по любым словам можно выяснить, существует ли целые числа пит такие, что слова м?т и у" равны в группе &

Научная новизна

1. Доказано, что группы Артина большого типа свободны от кручения.

2. Решена проблема вхождения в циклическую подгруппу в группах Артина большого типа.

3. Решена проблема слабой степенной сопряженности в группах Артина большого типа.

4. Получено описание диаграмм над конечно порожденными группами Артина экстрабольшого типа.

5. Установлена разрешимость проблемы степенной сопряженности слов в группах Артина экстрабольшого типа.

6. Решена проблема пересечения циклических подгрупп в группах Артина экстрабольшого типа.

Все полученные результаты являются новыми и могут быть использованы при решении различных задач теории групп и полугрупп.

Апробация работы

Результаты работы докладывались на Тульском городском семинаре «Алгоритмические проблемы теории групп и полугрупп» профессора В.Н. Безверхнего (Тула, 2005-2008 гг.), международной научно-практической конференции "JI. Эйлер и российское образование, наука и культура" (Тула, 2007 г.), международной алгебраической конференции, посвященной 100-летию со дня рождения А.Г. Куроша (МГУ им. М.В. Ломоносова, 2008 г.), семинаре по теории групп кафедры высшей алгебры МГУ им. М.В. Ломоносова под руководством профессоров А.Л. Шмелькина, А.Ю. Ольшанского и доцента A.A. Клячко (МГУ им. М.В. Ломоносова, 2009 г.).

Публикации

Результаты работы опубликованы в статьях [30]-[37].

Объем работы

Диссертация состоит из введения, трех глав, семи параграфов и списка литературы из 37 наименований. Диссертация содержит 100 страниц машинописного текста.

1. Бардаков В.Г. К теории групп кос // Математический сборник. - 1992.- Вып. 183. №6. - С. 3-42.

2. Безверхний В.Н. Неразрешимость проблемы вхождения в группах Артина конечного типа // Сибирский математический журнал. 1985.- Вып. 26. №5. - С. 27-42.

3. Безверхний В.Н. Неразрешимость проблемы сопряженности подгрупп для свободных произведений свободных групп с объединением // Сборник научных трудов кафедры высшей математики. — Тула, 1975. -№3.-С. 90-94.

4. Безверхний В.Н. Решение проблемы сопряженности слов в группах Артина большого типа// Алгоритмические проблемы теории групп и полугрупп: Межвузовский сборник научных трудов. Тула: Тул. гос. пед. ин-т, 1986.-С. 1-38.

5. Безверхний В.Н. Решение обобщенной сопряженности слов в группах Артина большого типа // Фундаментальная и прикладная математика.- 1999. Т 5. - №1. - С. 1-38.

6. Безверхний В.Н. Решение проблемы вхождения в классе НЫ>Т-групп // Алгоритмические проблемы теории групп и полугрупп: Межвузовский сборник научных трудов. Тула: Тул. гос. пед. ин-т, 1981.-С. 20-62.

7. Безверхний В.Н. Решение проблемы вхождения в некоторых классах групп с одним определяющим соотношением // Алгоритмические проблемы теории групп и полугрупп. Межвузовский сборник научных трудов. Тула: Тул. гос. пед. ин-т, 1986. — С.3-21.

8. Безверхний В.Н., Гринблат В.А. О проблеме вхождения в группах Артина конечного типа // Сибирский математический журнал. 1982.- Вып. 23. №4. - С. 19-28.

9. Безверхний В.Н., Паршикова E.B. Решение проблемы вхождения в циклическую подгруппу в группах с условием С(4)&Т(4) // Алгоритмические проблемы теории групп и полугрупп: Межвузовский сборник научных трудов. — Тула, 2001. — С. 97-120.

10. Безверхний В.Н., Устян А.Е. Решение проблемы сопряженности слов в моноидах Артина большого типа // Алгоритмические проблемы теории групп и полугрупп: Межвузовский сборник научных трудов. — Тула, 2001.-С. 139-164.

11. Брискорн Э., Сайто К. Группы Артина и группы Коксетера // Математика: Сб. переводов. 1974. - №6. - С. 56-79.

12. Бурбаки Н. Группы и алгебры Ли. М.: Мир, 1972.

13. Гарсайд Ф. Группы кос и другие группы // Математика: Сб. переводов. 1970.-№4.-С. 113-132.

14. Гринблат В.А. О нормализаторах групп Артина // Алгоритмические проблемы теории групп и полугрупп. — Тула, 1981. С. 82-94.

15. Гурзо Г.Г. О централизаторах конечных множеств элементов группы кос // Математические заметки. 1985. - Вып.37. - №1. — С. 3-6.

16. Линдон Р., Шупп П. Комбинаторная теория групп. М.: Наука, 1980.

17. Магнус В. и др. Комбинаторная теория групп / Магнус В., Каррас А., Солитер Д. М.: Наука, 1974.

18. Маканин Г.С. Проблема сопряженности в группах кос // Доклады АН СССР. 1968. - Т. 182. - №3. - С. 495-496.

19. Маканин Г.С. О нормализаторах группы кос // Математический сборник. 1971. - Вып. 86. - №2. - С. 171-179.

20. Марков A.A. Основы алгебраической теории кос // Труды математического института АН СССР. 1945. — Вып. 16.

21. Михайлова К.А. Проблема вхождения для прямых произведений групп // Математический сборник. — 1966. Т 70. — С. 241-251.

22. Новиков П.С. Об алгоритмической неразрешимости проблемы тождества слов в теории групп // Труды Математического института АН СССР. 1955.

23. Новиков П.С. Неразрешимость проблемы сопряженности в теории групп // Изв. АН СССР, сер. Мат. Т. 18. - С. 485-524.

24. Паршикова Е.В. Проблема слабой степенной сопряженности в группах с условием С(4)&Т(4) // Алгоритмические проблемы теории групп и полугрупп: Межвузовский сборник научных трудов. — Тула, 2001. С. 179-185.

25. Трубицын Ю.Э. О нормализаторах конечных множеств в группах Артина конечного типа // Алгоритмические проблемы теории групп и полугрупп. Межвузовский сборник научных трудов. Тула: Тул. гос. пед. ин-т, 1986.-С. 68-71.

26. Appel К. One Artin groups and Coxeter groups of large type // Contemp. Math. 1984. - V. 33. - P. 50-78.

27. Appel K, Schupp P. Artin groups and infinite Coxeter groups // Invenf.Math. 1983. - №72. - P. 201-220.

28. Artin E. Theorie der Zopfe //Abh. math. Semin. Univ. Hamburg. 1925. -V. 4.-P. 47-72.

29. Lipschutz S. On powers in generalized free products of groups // Arch. Math. 1968.-P. 575-576.

30. Безверхний B.H., Кузнецова A.H. О кручении групп Артина большого типа // Чебышевский сборник. 2005. — Т. 6. - №1. - С. 13-21.

31. Безверхний В.Н., Кузнецова А.Н. Проблема вхождения в циклическую подгруппу в группах Артина большого типа // Известия ТГУ, Математика. Механика. Информатика. 2005. — Вып. 2: Математика. -№1. - С. 76-93.

32. Безверхний В.Н., Кузнецова А.Н. Проблема корня в группах Артина большого типа // Л.Эйлер и российское образование, наука и культура:Материалы междунар. науч.-практ. конф. Тула: Изд-во Тул.гос.пед.ун-та им.Л.Н.Толстого. - 2007. - С. 36-43.

33. Кузнецова А.Н. Проблема слабой степенной сопряженности в группах Артина большого типа // Л.Эйлер и российское образование, наука и культура: Материалы междунар. науч.-практ. конф. Тула: Изд-во Тул.гос.пед.ун-та им. Л.Н.Толстого. - 2007. - С. 195-202.

34. Безверхний В.Н., Кузнецова А.Н. Разрешимость проблемы степенной сопряженности слов в группах Артина экстрабольшого типа // Чебышевский сборник. 2008. - Т. 9. - №1 (25). - С. 50-69.

35. Кузнецова А.Н. Разрешимость проблемы слабой степенной сопряженности в группах Артина большого типа // Известия 11 У, Естественные науки. 2008. - №2: Математика. — С. 29-39.

36. Кузнецова А.Н. О пересечении циклических подгрупп в группах Артина экстрабольшого типа // Вестник 11 У. Дифференциальные уравнения и прикладные задачи. 2008. - №1. - С. 76-86.