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

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

.

В 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].

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Краткое содержание работы.

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

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

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

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

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

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

Лемма 1.5. Пусть (? — конечно порожденная группа Артина с древесной структурой. Слова и у, для которых [М[ = 1,|Н| = 1, сопряжены в О тогда и только тогда, когда существует ломанная, состоящая из ребер дерево-графа Г, которая соединяет вершины, соответствующие данным образующим группы, и каждому из ребер выделенного пути соответствует соотношение с нечетным числомКокстера, причем, если м>=хк, то у=у1, где.

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

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

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

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

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

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

Теорема 2.2. Существует алгоритм, строящий по любому несократимому слову сопряженное с ним или с его квадратом в группе Артина с древесной структурой слово м'0, любая степень которого К и К — несократима.

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

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

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

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

Лемма 2.9. Пусть О — конечно порожденная группа Артина с древесной структурой с множеством образующих А, А <со. И пусть м><�еО, ч>-К и Я несократимое слово не равное единиц в <7. Слово м? равно некоторому слову veGJ, где — параболическая подгруппа группы С с множеством образующих.

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

Лемма 2,10. Пусть О — конечно порожденная группа Артина с древесной структурой, с множеством образующих А, А<�со, И пусть м>- циклически.

Я и К — несократимое, тупиковое слово, не равное единице в О. Слово м> сопряжено некоторому слову veGJ, то есть существует слово 2⁰ такое, что у,[|у|| > 2, GJ — параболическая подгруппа группы О с множеством образующих, а А. Тогда м>, г — слова на образующих Аг.

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

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

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

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

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

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

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

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

Теорема 2.6. В группах Артина с древесной структурой разрешима проблема пересечения двух циклических подгрупп, т. е. по любым двум словам м>, V «Е С можно установить, существуют ли натуральные числа тип, что слова м? т и Vя равны в группе С.

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

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

Лемма 3.2. Пусть (?- конечно порожденная группа Артина с древесной структуройслово такое, что м> = а*, С О) — централизатор элемента м>.

Тогда группа Су, (м>) является свободным произведением циклических групп и 1.

СМ = (а)хС, М, где С"(м>) = П*(?г), где гг = ,.

Т=1.

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

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

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

Заключение

.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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