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

• Кузнецова, Анна Николаевна
• кандидат физико-математических наук
• 2009

Оглавление диссертации кандидат физико-математических наук Кузнецова, Анна Николаевна

Введение.

Глава 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 страниц машинописного текста.

Список литературы диссертационного исследования кандидат физико-математических наук Кузнецова, Анна Николаевна, 2009 год

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.