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

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

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

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

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

АВТОРЕФЕРАТ

диссертации на соискание ученой степени

кандидата физико-математических наук

Ярославль - 2013

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

на кафедре алгебры, математического анализа и геометрии факультета математики, физики и информатики.

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

Официальные оппоненты:

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

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

Московский государственный университет им. М.В. Ломоносова

Защита состоится 20 декабря в 14 часов на заседании диссертационного совета Д 212.002.03 при Ярославском государственном университете им.

П.Г. Демидова по адресу 150008, г. Ярославль, ул. Союзная, 144, ауд.

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

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

Ученый секретарь диссертационного совета С.И. Яблокова

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

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

Пусть G – конечно порожденная группа Артина с копредставлением mij mij m ji G a1, a2,..., an ; ai a j a j ai ai a j ai... - слово длины mij, состоящее, где ai a j из mij чередующихся букв ai и a j, i j, mij - число, соответствующее симметрической матрице Кокстера, mij 2 при i j. Если к определяющим соотношениям группы Артина добавить соотношения вида: i I, ai2 1, то получим копредставление соответствующей группы Кокстера.

Группы Артина конечного типа являются обобщением групп кос, которые ввел в 1925 году Э. Артин2. Группы кос имеют копредставление Bn 1 1, 2,..., n ; i i 1 i i 1 i i 1, i 1, n 1; i j j i, i, j 1, n, i j 1. Группа Артина называется группой Артина конечного типа, если соответствующая ей группа Кокстера конечна.

Группы Кокстера были введены Х. С. М. Кокстером 3 в 1934 году.

Понятие данной группы возникло в теории дискретных групп, порождаемых данного класса групп подробно представлена в работах Н. Бурбаки4.

В 1912 г. М. Дэном5 были сформулированы фундаментальные изоморфизма групп.

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

56-79.

Artin E. 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 -621.

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

Dehn M. Uber unendliche diskontinuierliche Gruppen. // Math. Annal. – 1912. – V.71. – P.116-144.

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

Проблема равенства слов в группах кос Bn1 решена Э. Артином7. Г.С.

сопряженности в Bn1. А также Г.С. Маканин10 показал, что нормализатор выписывающий его образующие.

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

К. Аппелем и П. Шуппом11 в 1983 г. выделены классы групп Артина большого и экстрабольшого типа. Если mij 3 для всех i j, то G называется Новиков П. С. Об алгоритмической неразрешимости проблемы тождества в теории групп. / / Труды МИАН СССР. – 1955. – Т.44. – С.3-143.

Artin E. Theory of braids. // Ann. Math. – 1947. – V.48. – P. 101-126.

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

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

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

Appel K., Schupp P. Artin groups and infinite Coxter groups. // Invent. Math. – 1983. – V. 72. – P. 201-220.

группой Артина (Кокстера) большого типа. Если же mij 3, то группа называется группой Артина (Кокстера) экстрабольшого типа. П. Шупп и К.

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

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

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

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

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

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

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

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

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

Безверхний В.Н. О группах Артина, Кокстера с древесной структурой. // Алгебра и теория чисел:

Современные проблемы и приложения. – Тезисы докладов V Международной конференции. – Тула. – 2003.С. 33 – 34.

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

Целью данной работы является изучение конечно порожденных групп Артина с древесной структурой, а также доказательство разрешимости некоторых алгоритмических проблем в данном классе групп. Поставленная цель предполагает решение следующих задач: описать диаграммы над данным классом групп, изучить их свойства; доказать разрешимость циклическую подгруппу, проблемы вхождения в параболическую подгруппу, Baudisch. A. Subgroups of semifree groups. // Acta Math. Acad. Sci. Hungar. – 1981. – 38(1-4). – P.19-28.

Van Wyk. 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(1). – P.34-60.

Droms. C. Isomorphisms of graph groups. //Proc. 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.1 – 20.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Lindon R. On Dehn’s algoritm. //Math. Ann. – 1966. – 166-P. 208-228.

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

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

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

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

Слово w G, G - группа Артина с древесной структурой, называется R - приведенным, если w свободно приведено в F и не содержит подслово s, являющееся подсловом некоторого соотношения r, r s t, где s r, где R - все циклические несократимые слова равные единице в G.

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

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

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

Лемма 1.5. Пусть G – конечно порожденная группа Артина с тогда и только тогда, когда существует ломанная, состоящая из ребер дерево-графа Г, которая соединяет вершины, соответствующие данным образующим группы, и каждому из ребер выделенного пути соответствует x, y a11, a2 1,..., an 1.

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

В слове w есть R -сокращение, если в приведенной диаграмме М, граничной меткой которой является слово w, выделяется полоса.

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

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

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

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

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

несократимому слову w сопряженное с ним или с его квадратом в группе Артина с древесной структурой слово w0, любая степень которого R и R несократима.

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

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

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

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

Лемма 2.9. Пусть G - конечно порожденная группа Артина с древесной структурой с множеством образующих А, А. И пусть w G, w R и R - несократимое слово не равное единице в G. Слово w равно некоторому слову v G j, где G j - параболическая подгруппа группы G с множеством образующих A j, A j A. Тогда w - слово на образующих A j.

Лемма 2.10. Пусть G - конечно порожденная группа Артина с древесной структурой, с множеством образующих А, А. И пусть w G, w циклически R и R - несократимое, тупиковое слово, не равное единице в G. Слово w сопряжено некоторому слову v G j, то есть существует слово z G такое, что z wz v, v 2, G j - параболическая подгруппа группы G с множеством образующих A j, A j A. Тогда w, z - слова на образующих A j.

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

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

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

сопряженности слов, если существует алгоритм, позволяющий для любых двух слов w, v G установить существуют ли натуральные числа m и n, и элемент z G такие, что z 1 w m z v n. Доказана основная теорема:

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

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

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

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

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

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

элемента w. Тогда группа C w (w) является свободным произведением Для доказательства следующего результата необходимо представить группу G в виде древесного произведения.

которого являются двупорожденные группы Артина. Группы Артина соответствуют данные подгруппы, соединены ребром в древесном графе.

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

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

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

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

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

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

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

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

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

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

[1] Безверхний, В.Н. Проблема равенства и сопряженности слов в группах Артина с древесной структурой [Текст] / В.Н. Безверхний, О.Ю.

Карпова* // Известия Тульского государственного университета. Серия Математика. Механика. Информатика. - 2006. - Том 12. - Выпуск 1. С.67-82.

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

Безверхний, // Известия Тульского государственного университета.

Естественные науки. Естественные науки. – 2009. – Выпуск 3. - C.42Статьи в других журналах:

[4] Безверхний, В.Н. Проблема вхождения в циклическую подгруппу в группах Артина с древесной структурой [Текст] / В.Н. Безверхний, О.Ю. Карпова* // Чебышевский сборник. - 2008. – Tом 9. – Выпуск [5] Платонова, О.Ю. О структуре централизатора элементов единичной слоговой длины в группах Артина с древесной структурой [Текст] /О.Ю. Платонова // Чебышевский сборник. - 2010. – Tом 11. - Выпуск [6] Платонова, О.Ю. Проблема пересечения циклических подгрупп в группах Артина с древесной структурой [Текст] /О.Ю. Платонова // Чебышевский сборник. - 2010. – Tом 11. - Выпуск 2(34). - С.85-96.

* - фамилия Карпова изменена на Платонову в связи с вступлением в брак.