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

Платонова, Оксана Юрьевна

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

Платонова, Оксана Юрьевна АВТОР

кандидата физико-математических наук УЧЕНАЯ СТЕПЕНЬ

Тула МЕСТО ЗАЩИТЫ

2013 ГОД ЗАЩИТЫ

01.01.06 КОД ВАК РФ

Диссертация по математике на тему «Решение некоторых алгоритмических проблем в группах Артина с древесной структурой»

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

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

Платонова Оксана Юрьевна

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

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

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

2-1 "ОЯ 2013

Ярославль - 2013

005538993

Работа выполнена в Федеральном государственном бюджетном образовательном учреждении высшего профессионального образования «Тульский государственный педагогический университет им. Л.Н. Толстого» на кафедре алгебры, математического анализа и геометрии факультета математики, физики и информатики.

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

Безверхний Владимир Николаевич Официальные оппоненты:

Глухов Михаил Михайлович, доктор физико — математических наук, профессор Академии криптографии РФ, академик-секретарь отделения Академии криптографии РФ

Инченко Оксана Владимировна, кандидат физико-математических наук, доцент ФГБОУ ВПО «Тульский государственный университет»

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

ФГБОУ ВПО «Московский государственный университет им. М.В. Ломоносова»

Защита состоится 20 декабря в 14 часов на заседании диссертационного совета Д 212.002.03 при Ярославском государственном университете им. П.Г. Демидова по адресу 150008, г. Ярославль, ул. Союзная, 144, ауд. 426

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

Автореферат разослан и/3» ноября 2013г.

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

диссертационного совета

С.И. Яблокова

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

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

В 1972 г. Э. Брискорн и К. Сайто1 ввели класс групп, который назвали группами Артина.

Пусть G — конечно порожденная группа Артина с копредставлением G = (a„a2,...,a„-,(alaiy' = где = а,а ¡а,... - слово длины т,(, состоящее из

m:t чередующихся букв а, и а(, - число, соответствующее симметрической

матрице Кокстера, т,( > 2 при ы j. Если к определяющим соотношениям группы Артина добавить соотношения вида: V/ с- /,а; -1, то получим копредставление соответствующей группы Кокстера.

Группы Артина конечного типа являются обобщением групп кос, которые ввел в 1925 году Э. Артин2. Группы кос имеют копредставление в,., =(<?,......г„,£г, =<т,.1ст,<7,„./=йГ:Т;ст,а, =<т^„/,у = Г^,|'-./|>1)- группа Артина называется

группой Артина конечного типа, если соответствующая ей группа Кокстера конечна.

Группы Кокстера были введены X. С. М. Кокстером3 в 1934 году. Понятие данной группы возникло в теории дискретных групп, порождаемых отражениями относительно гиперплоскостей. Алгебраическая теория данного класса групп подробно представлена в работах Н. Бурбаки4.

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

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

1 Брискорн 0. Сайто К. Группы Артина и группы Кокстера./' Математика: Сб. переводов. - !974. - № 6 - С. 56-79.

2 Artin Е. Theorie der Zorfe // Abh. math. Semin. Univ. Hamburg. - 1925. - V, 4. - P 47-72.

' Coxeter H. S. M. Discrete groups generated by reflections ■<" Ann. Math. - 1934. - V. 35 - P 588 -62 E.

J Бурбаки H. Группы и алгебры Ли - М.: Мир. 1972.

' Dehn М Uber unendliche diskontinuierliche Gruppen Math. Annal. - 1912 - V.7! P.116-H-i.

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

Проблема равенства слов в группах кос решена Э. Артином7. Г.С. Маканиным8 и независимно Ф. Гарсайдом9 получено решение проблемы сопряженности в Bntl. А также Г.С. Маканин10 показал, что нормализатор любого элемента группы кос конечно порожден и построил алгоритм, выписывающий его образующие.

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

К. Аппелем и П. Шуппом" в 1983 г. выделены классы групп Артина большого и экстрабольшого типа. Если тч > 3 для всех /*_/, то G называется группой Артина (Кокстера) большого типа. Если же >3, то группа называется группой Артина (Кокстера) экстрабольшого типа. П. Шупп и К. Аппель показали разрешимость проблемы равенства и сопряженности слов для групп Артина и

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

7 Artin Е. Theory ofbraids. /< Ann. Math. - 1947. - V.48. - P. 101-126.

* Маканин Г.С. Проблема сопряженности слов в группе кос. //Доклады АН СССР. - 1968. - Т. 182, №3. - С.495-496. ' ГарсайдФ. Группа кос и другие группы. -v Математика: Сб. переводов. - 1970. -Л»4. - С. 113-132.

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

" Appel К., Schupp P. Artin groups and infinite Coxter groups.. Invent. Math. 1983. - V. 72. - P. 201-220.

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

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

В.Н. Безверхним были выделены конечно порожденные группы Артина и Кокстера с древесной структурой16.

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

соотношение вида (аа У"" =(а,а,}"'" для группы G. Группа Артина G имеет древесную структуру, если граф Г' является дерево - графом.

В графе Г" всегда можно выделить максимальное дерево-граф Г, который соответствует группе, имеющей древесную структуру, для которой группа Артина с графом Г' является гомоморфным образом.

Степень разработанности темы исследования

Впервые прямоугольные группы Артина, т. е. группы с древесной структурой были изучены Баудишом'7, которого в свою очередь интересовали двупорожденные подгруппы в случае, когда все числа симметрической матрицы Кокстера принимают значения т„ = {о,2}. Затем данный класс групп подвергся

■ Безверхний В.Н, Кузнецова А Н, О кручении групп Артина большого типа. // Чебышевский сборник - T 6 - В ! -2005.-С. 13-22.

Безверхний В Н . Кузнецова А Н. Решение проблемы вхождения в циклическую подгруппу в группах Артина большого типа. // Известия ТулГУ. - Серия Математика. Механика. Информатика . - Т. I I. - 2005. - С.76-94.

Безверхний В Н. Решение проблемы сопряженности слов в группах Артина и Кокстера большого типа. ,'• Алгоритмические проблемы теории групп и полугрупп: Межвузовский сборник научных трудов. - ! 983. - С.26-62.

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

" Безверхний В Н. О группах Артина. Кокстера с древесной структурой. < Алгебра и теория чисел: Современные проблемы и приложения. - Тезисы докладов V Международной конференции. - Тула. - 2003 - С. 33 34. Baudisch A. Subgroups of semifree groups 7 Acta Math. Acad. Sei. Hungar. - I98L - 38(1-4). P. 19-28.

широкому изучению, были решены многие алгоритмические задачи. Прямоугольные группы Артина являются биавтоматными18, они имеют конечно порожденную группу автоморфизмов19. Две прямоугольные группы Артина изоморфны тогда и только тогда, когда изоморфны их графы20. В работах Бествина и Брэди21 были описаны некоторые подгруппы прямоугольных групп, которые обладают специфическими гомологическими свойствами. Вайсом22 было доказано, что в прямоугольных группах Артина всякая квазивыпуклая подгруппа финитно отделима. В диссертации рассмотрен общий случай, когда числа симметрической матрицы Кокстера принимают значения /я,., = {0,2Д...}.

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

Основные положения, выносимые на защиту и научная новизна

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

Van Wvk. L. Graph groups are biautomatic. .<'/ J. Pure Appl. Algebra. - 1994. - 94(3). - P.341-352.

''' Servatius. H. Automorphisms of graph groups. //J. Algebra. - 1989. - 126( I) - P.34-60

Droms. C Isomorphisms of graph groups. ,v'Pr*. Amer. Math. Soc. - 1987. - 100(3). - P.407-408.

Bestvina M.. Brady N. Morse theory and finiteness properties of groups. /Invent. Math. - 1997. - 129(3). - P.445-470. "" Hsu T . Wise D T. Separating quasiconvex subgroups of right-angled Artin groups. Mathematics Subject Classification.

2000. -P.l -20.

1) в группах Артина с древесной структурой разрешима проблема сопряженности слов;

2) группы Артина с древесной структурой являются группами без кручения;

3) в группах Артина с древесной структурой разрешима проблема вхождения в циклическую подгруппу;

4) в группах Артина с древесной структурой разрешима проблема вхождения в параболическую подгруппу;

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

6) в группах Артина с древесной структурой разрешима проблема степенной сопряженности слов;

7) в группах Артина с древесной структурой разрешима проблема пересечения циклических подгрупп;

8) получено описание централизатора элементов в группах Артина с древесной структурой.

Теоретическая и практическая значимость работы

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

Методология и методы исследования

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

=» ЫтоЗоп Я. Оп ОеЬпЧ а^огкт. //Май». Апп. - 1966. - 166-Р. 208-228.

Степень достоверности результатов

Степень достоверности результатов данной работы подтверждается полными и подробными математическими доказательствами.

Апробация результатов

Основные результаты диссертации докладывались на семинаре «Алгоритмические проблемы теории групп и полугрупп» под руководством профессора Безверхнего В.Н. (ТГПУ им. Л.Н. Толстого, 2005 - 2010гг.), на Международной научной практической конференции «Современные проблемы математики, механики, информатики» (ТулГУ, 2006-2010гг.), на Международной научно-практической конференции «Л. Эйлер и российское образование, наука и культура» (ТГПУ им. Л.Н. Толстого, 2007г.), на VII Международной конференции «Алгебра и теория чисел: современные проблемы и приложения» (Тула, 2010г.), на алгебраическом семинаре под руководством профессора Шмелькина А.Л. (МГУ, 2012г.).

Публикации

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

Структура диссертации -

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

Основное содержание работы

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

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

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

В первом разделе первой главы введены преобразования диаграммы, которые мы можем проводить с диаграммами для данного класса групп, определены понятие деновской области (что соответствует Л - сокращению), понятия особой и специально особой точки, 5-/ области, описаны структура и свойства диаграмм над конечно порожденными группами Артина с древесной структурой.

Слово №еС, О - группа Артина с древесной структурой, называется Я-приведенным, если м свободно приведено в Г и не содержит подслово 5,

являющееся полсловом некоторого соотношения = где > где Л - все

циклические несократимые слова равные единице в О.

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

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

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

Лемма 1.5. Пусть С - конечно порожденная группа Артина с древесной структурой. Слова и- и у, для которых |м| = |,|,| = 1. сопряжены в С тогда и только тогда, когда существует ломанная, состоящая из ребер дерево-графа Г. которая соединяет вершины, соответствующие данньш образующим группы, и каждол!у из ребер выделенного пути соответствует соотношение с нечетным числом Кокетера. причем, если »•=.*'. то у = .у\ где ^»'.о!1.....о;1}.

В третьем разделе определены понятия «полосы» и «/? - сокращения», которые использовали при доказательстве теоремы о кручении элементов в данном классе групп.

Поддиаграмма я = У"1Д образует полосу в Л-приведенной диаграмме М с

граничным циклом ам = ^у¡5, если

1. V/, / = 1,и-1 зцр) ад„ = где е,- ребро;

2. V/. / = 17» сдр]Г = У(, где -связный путь, причем |г |>1;

3. ]го,О| = Ииа0>ГИ и |гА,ОНаЛ"иао»ГИ;

4. у/, у = 2, я -1 |гю,р1г|+2 = |го/(го,П/)|-

В слове 1С есть Л-сокращение, если в приведенной диаграмме Л/, граничной меткой которой является слово и1, выделяется полоса.

Теорема 1.3. Группа Артина с древесной структурой свободна от кручения.

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

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

В первом разделе второй главы мы исследовали вопрос о разрешимости проблемы вхождения в циклическую подгруппу в группах Артина с древесной структурой, которая заключается в нахождении алгоритма, позволяющего определить, является ли слово и- группы О степенью некоторого слова V в О, то есть и' = V" ,я > 1.

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

Теорема 2.2. Существует алгоритм, строящий по любому несократимому слову »■ сопряженное с ним или с его квадратом в группе Артина с древесной структурой слово »'„. любая степень которого Я и Л - несократима.

Затем доказана основная теорема первого раздела.

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

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

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

Лемма 2.9. Пусть в - конечно порожденная группа Артина с древесной структурой с множеством образующих Л.|Л|<®. И пусть неб, н'-Л и Я -несократимое слово не равное единице в О. Слово ме равно некоторому слову уеС,, где О, - параболическая подгруппа группы в с множеством образующих А1,А1 а А. Тогда »■ - слово на образующих Аг

Лемма 2.10. Пусть О - конечно порожденная группа Артина с древесной структурой, с .множеством образующих А,\А\<т. И пусть и1 еС. 1С- циклически Я и Л - несократимое, тупиковое слово, не равное единице в С. Слово м-сопряжено некоторому слову VсОто есть существует слово :еС такое, что

= у,||г||>2, - параболическая подгруппа группы С с множеством

образующих А1,А1 с. А. Тогда п.г - слова на образующих Аг

Будем говорить, что в группе С разрешима проблема слабой степенной сопряженности, если для любых двух слов оеС, где н1 е Ы), найдется целое число п такое, что слова № и V" сопряжены в группе в .

Теорема 2.4. В группе Артина с древесной структурой разрешима алгоритмическая проблема слабой степенной сопряженности.

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

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

= V". Доказана основная теорема:

Георема 2.5. В группе Артина с древесной структурой разрешима проблема степенной сопряженности.

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

Основным результатом первого раздела третьей главы является доказательство следующей теоремы.

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

можно установить, существуют ли натуральные числа тип, что слова и V" равны в группе С.

Во втором разделе третьей главы описывается структура централизатора элементов группы.

Для слов из группы С с единичной слоговой длиной имеет место следующее утверждение:

Лемма 3.2. Пусть О- конечно порожденная группа Артина с древесной структурой; слово н е О такое, что „■ = „', С(н>) - централизатор элемента Тогда группа С„(») является свободным произведением циклических групп и

СМ = {а)хС,Ли'), где С.,(№) = П*<г,.), где ?г=г, г2 '...г, ..^г",- -"'-Г'. г(еС..

г = \ У

Для доказательства следующего результата необходимо представить группу С в виде древесного произведения.

Группе с соответствует конечный дерево - граф Г,„ вершинами которого являются двупорожденные группы Артина. Группы Артина ср = и

С,„ объединены по циклическим подгруппам ич,=(а1), и<, и

(/„, ={«;), и,„<С,ц, если вершины, которым соответствуют данные подгруппы, соединены ребром в древесном графе.

Тогда представление группы С как древесное произведение групп вида С,} с

циклическим объединением имеет вид: С = ^П'^ ич ~ где 11 а = {а,)*и= (а/)'

/е/,,у е л,,/, <со,/, <со. Поэтому каждый элемент может быть представлен в

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

Для слов, принадлежащих группе О и имеющих слоговую длину больше единицы, имеет место следующая теорема:

Теорема 3.4. Пусть С - конечно порожденная группа Артина с древесной структурой; слово м> - циклически несократимое в свободной группе и не равное 1 в С, |Н| > 1. Тогда централизатор элемента м> есть либо бесконечная циклическая подгруппа, либо свободная абелевая группа ранга 2.

Заключение

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

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

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

больше 1 есть либо бесконечная циклическая подгруппа, либо свободная абелевая группа ранга 2.

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

Возможно, решение алгоритмических проблем в группах Артина с древесной структурой поможет в исследовании этих же задач в общих классах групп Артина.

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

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

Статьи в журналах, рекомендованные ВАК РФ:

[1] Безверхний, В.Н. Проблема равенства и сопряженности слов в группах Артина с древесной структурой [Текст] / В.Н. Безверхний, О.Ю. Карпова^/ Известия Тульского государственного университета. Серия Математика. Механика. Информатика. - 2006. - Том 12. - Выпуск 1. - С.67-82.

[2] Безверхний, В.Н. О кручении в группах Артина с древесной структурой [Текст] / В.Н. Безверхний, О.Ю. Карпова // Известия Тульского государственного университета. Естественные науки. - 2008. - Выпуск 2. -С.6-17.

[3] Карпова, О.Ю. Решение проблемы степенной сопряженности в группах Артина с древесной структурой [Текст] / О.Ю. Карпова, В.Н. Безверхний, // Известия Тульского государственного университета. Естественные науки. Естественные науки. - 2009. - Выпуск 3. - С.42-59.

Статьи в других журналах:

[4] Безверхний, В.Н. Проблема вхождения в циклическую подгруппу в группах Артина с древесной структурой [Текст] / В.Н. Безверхний, О.Ю. Карпова // Чебышевский сборник. - 2008. - Том 9. - Выпуск 1(25). - С.30-50.

[5] Платонова, О.Ю. О структуре централизатора элементов единичной слоговой длины в группах Артина с древесной структурой [Текст] /О.Ю. Платонова// Чебышевский сборник. - 2010. - Том 11. - Выпуск 2(34). - С.73-84.

[6] Платонова, О.Ю. Проблема пересечения циклических подгрупп в группах Артина с древесной структурой [Текст] /О.Ю. Платонова // Чебышевский сборник. - 2010. - Том 11. - Выпуск 2(34). - С.85-96.

*Фамшия изменена на Платонову в связи с вступлением в брак

Подписано в печать 30.10.2013 г. Формат60x90'"'. Бу мага офсетная. Гарнитура Тайме. Усл. печ. л. 1,0. Заказ Тираж 100 экз.

ФГБОУ ВПО «Российским химико-технологический университет им. ЛИ. Менделеева» Новомосковский институт (филиал). Издательский центр 301665 Новомосковск, Тульская обл., Дружбы, 8

Текст научной работы диссертации и автореферата по математике, кандидата физико-математических наук, Платонова, Оксана Юрьевна, Тула

61 14-1/244

Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования «Тульский государственный педагогический

университет им Л.Н. Толстого»

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

Платонова Оксана Юрьевна

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

АРТИНА С ДРЕВЕСНОЙ СТРУКТУРОЙ

01.01.06 - математическая логика, алгебра и теория чисел Диссертация на соискание ученой степени кандидата физико-математических

наук

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

Тула-2013

Оглавление

Введение.......................................................................................3

Глава 1. Проблема сопряженности в группах Артина с древесной структурой...................................................................................13

1.1. Диаграммы над группой Артина с древесной структурой...................13

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

с древесной структурой.......................................................................................20

1.3. О кручении в группах Артина с древесной структурой...........................31

Глава 2. Решение проблемы степенной сопряженности в группах Артина с древесной структурой.......................................................................41

2.1. Проблема вхождения в циклическую подгруппу в группах Артина с древесной структурой.....................................................................41

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

2.3. Проблема степенной сопряженности в группах Артина с древесной

структурой..................................................................................71

Глава 3. Структура централизатора элементов в группах Артина с древесной

структурой......................................................................................81

3.1.0 пересечении циклических подгрупп в группах Артина с древесной

структурой..................................................................................81

3.2. О структуре централизатора элементов в группах Артина с древесной

структурой..................................................................................89

Заключение.................................................................................108

Библиографический список.............................................................111

Введение

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

В 1972 г. Э. Брискорном и К. Сайто [19] был введен класс групп, который назвали группами Артина.

Пусть О - конечно порожденная группа Артина с копредставлением

0 = = где (ар^* =а,а]а1... - слово длины т0, состоящее

из т.1} чередующихся букв а, и а}, тц - число, соответствующее

симметрической матрице Кокстера, т0 > 2 при г * ) . Если к определяющим соотношениям группы Артина добавить соотношения вида: V/ е /, а,2 = 1, то получим копредставление соответствующей группы Кокстера.

Группы Артина конечного типа являются обобщением групп кос, которые ввел в 1925 году Э. Артин [35], Группы кос имеют копредставление

= {сп.сгг.....агя;ег/сг/+10"/ = ^н.!«7"^!'1' = - = сг^.г,/ = - > . Группа

Артина называется группой Артина конечного типа, если соответствующая ей группа Кокстера конечна.

Группы Кокстера были введены X. С. М. Кокстером [40] в 1934 году. Понятие данной группы возникло в теории дискретных групп, порождаемых отражениями относительно гиперплоскостей. Алгебраическая теория данного класса групп подробно представлена в работах Н. Бурбаки [20].

В 1912 г. М. Дэном [41] были сформулированы фундаментальные алгоритмические проблемы теории групп: проблема равенства, сопряженности слов в конечно определенных группах, проблема изоморфизма групп.

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

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

Проблема равенства слов в группах кос Вп+1 решена Э. Артином [36]. Г.С. Маканиным [26] и независимно Ф. Гарсайдом [21] получено решение проблемы сопряженности слов в Вп+]. А также Г.С. Маканин [27] показал, что нормализатор

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

Э. Брискорн и К. Сайто [19] показали разрешимость проблем равенства и сопряженности слов в группах Артина конечного типа. Для данного класса групп В.Н. Безверхним и В.А. Гринблатом было получено решение проблемы вхождения в циклическую подгруппу [6]. Ю.Э. Трубицын и В.А. Гринблат доказали разрешимость проблемы обобщенной сопряженности слов в данном классе групп. В.Н. Безверхний доказал неразрешимость проблемы вхождения в неприводимые группы Артина конечного типа.

К. Аппелем и П. Шуппом [33] в 1983 г. выделены классы групп Артина большого и экстрабольшого типа. Если ти > 3 для всех 1ф у, то называется

группой Артина (Кокстера) большого типа. Если же т.. > 3, то группа С

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

решение проблемы обобщенной сопряженности слов [4] для групп Артина большого типа.

В.Н. Безверхним были выделены конечно порожденные группы Артина и Кокстера с древесной структурой [5].

Пусть О - конечно порожденная группа Артина. Каждой конечно порожденной группе Артина О соответствует конечный граф Г*, между вершинами которого и образующими группы можно установить соответствие такое, что если щ и а} являются вершинами ребра е, то ребру соответствует

соотношение вида Для группы б. Группа Артина (7 имеет

древесную структуру, если граф Г* является дерево - графом.

В графе Г* всегда можно выделить максимальное дерево-граф Г, который соответствует группе, имеющей древесную структуру, для которой группа Артина с графом Г* является гомоморфным образом.

Возможно решение алгоритмических проблем в группах Артина с древесной структурой поможет в исследовании этих же задач в общих классах групп Артина.

Степень разработанности темы исследования

Впервые прямоугольные группы Артина, т. е. группы с древесной структурой были изучены Баудишом [37], которого в свою очередь интересовали двупорожденные подгруппы, т. е. подгруппы, для которых все числа симметрической матрицы Кокстера принимают значения т9 - {0,2}. Затем данный

класс групп подвергся широкому изучению, были решены многие алгоритмические задачи. Прямоугольные группы Артина являются биавтоматными [48], они имеют конечно порожденную группу автоморфизмов [47]. Две прямоугольные группы Артина изоморфны тогда и только тогда, когда изоморфны их графы [42]. В работах Бествина и Брэди [23] были описаны некоторые подгруппы прямоугольных групп, которые обладают специфическими гомологическими свойствами. Вайсом [46] было доказано, что в прямоугольных

группах Артина всякая квазивыпуклая подгруппа финитно отделима. В диссертации рассмотрен общий случай, когда числа симметрической матрицы Кокстера принимают значения ту = {0,2,3,...}.

Цели задачи работы

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

- описать диаграммы над данным классом групп, изучить их свойства;

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

- описать структуру централизатора элементов группы.

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

В данной работе получены результаты, являющиеся новыми и состоящие в следующем:

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

■ получено, что группа Артина с древесной структурой является группой без кручения;

■ доказана теорема вхождения в циклическую подгруппу для групп Артина с древесной структурой;

■ решена проблема вхождения в параболическую подгруппу в данном классе групп;

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

■ решена проблема степенной сопряженности слов для групп Артина с

древесной структурой;

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

группах Артина с древесной структурой;

■ дано описание централизатора элементов в группах Артина с древесной

структурой.

Теоретическая и практическая значимость работы

Методология и методы исследования

В диссертации при доказательстве основных результатов используется метод диаграмм, введенный ван Кампеном в 1933 году и вновь переоткрытом Р. Линдоном в 1966 году [44].

Положения, выносимые на защиту

На защиту выносятся следующие положения: