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

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

.

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

Группа Артина — это группа О, заданная копредставлением с системой образующих ап / е/, |/|<оо, и соотношениями а1а]аг. = а}ар.г., где слова, стоящие слева и справа, состоят каждое из тц чередующихся букв а) и а}, тц элемент симметрической матрицы Кокстера М = (тя.). соответствующей данной группе С, ти = т. у1, при j, ту е {2,3,.}.

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

Класс групп Артина содержит группы кос, копредставление которых было получено Артином, решившим в данном классе групп проблему тождества слов, используя геометрические методы [35]. Алгебраическая теория групп кос была построена Марковым A.A. [28], который решил проблему равенства другими методами. Гарсайдом и независимо Маканиным Г. С. для групп кос была решена проблема сопряженности слов [26], а в [27] доказано, что нормализатор любого элемента групп кос конечно порожден, и построен алгоритм выписывающий образующие этого нормализатора. Гурзо Г. Г. получила алгоритм для нахождения образующих централизатора конечного множества элементов группы кос [22]. Отметим, что до настоящего времени неизвестна разрешимость проблемы равенства в конечно определенных группах Артина.

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

В 1983 году Аппелем К. и Шуппом П. был выделен класс групп Артина большого и экстрабольшого типа. [33]. Если все числа mtJ симметрической матрицы Кокстера для групп Артина или Кокстера больше либо равны трем, то группы называются труппами Артина или Кокстера большого типа. Если все числа т симметрической матрицы Кокстера для групп Артина или Кокстера больше трех, то группы называются группами Артина или Кокстера экстрабольшого типа. Для групп Артина и Кокстера экстрабольшого типа.

Шуппом П. и Аппелем К. [33] было получено решение проблем равенства и сопряженности слов. Безверхним В. Н и Кузнецовой А. Н. доказано, что группы Артина большого типа не имеют кручения [14], и в данном классе групп разрешима проблема вхождения в циклическую подгруппу [15]. Аппелем К. и независимо Безверхним В. Н была решена проблема сопряженности слов [6], в [7] Безверхним В. Н. доказана разрешимость обобщенной проблемы сопряженности слов для групп Артина большого типа. Для групп Кокстера большого типа Безверхним В. Н и Добрыниной И. В. доказана разрешимость проблемы сопряженности слов [10], описаны элементы конечного порядка [11], дано решение проблемы степенной сопряженности слов [12], а также решение проблемы обобщенной сопряженности слов [13].

В классах конечно-порожденных групп Артина и Кокстера Безверхним В. Н. в [8] были выделены новые классы групп: конечно-порожденные группы Артина и Кокстера с древесной структурой. Итак, пусть С конечно-порожденная группа Артина. И пусть Сг — соответствующая группе С? конечно порожденная группа Кокстера, полученная присоединением соотношений а* = 1, г = 1, п, и имеющая копредставление О = {а.1,.ап{а1)21 <1^'<п. Каждой конечно порожденной группе Артина С и группе Кокстера О соответствует конечный граф Г*, между вершинами которого и образующими группы можно установить соответствие такое, что, если а1 и а} являются вершинами ребра е, то ребру соответствует соотношение вида [ар^" для группы О и а1а})т" = 1 для группы С?. Группа Артина или Кокстера имеет древесную структуру, если граф Г' является дерево — графом.

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

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

МсСапшюпс! (Маккамонд) исследовал прямоугольные группы, то есть группы Кокстера с древесной структурой в случае, когда все числа т симметрической матрицы Кокстера принимают значения ту = {0,2}. В диссертации рассмотрен общий случай, когда числа т симметрической матрицы Кокстера принимают значения т. е {0,2,3,.}.

Цель работы.

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

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

При доказательстве некоторых результатов в работе используется метод диаграмм, который был введен ван Кампеном в 1933 году и вновь переоткрыт Линд оном Р. в 1966 году [38]. При доказательстве основных результатов был использован метод специального множества слов, введенный и примененный Безверхним В. Н. при решении некоторых алгоритмических проблем в свободных конструкциях групп [2].

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

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

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

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

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

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

Теоретическая и практическая ценность.

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

Апробация диссертации.

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

Публикации.

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

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

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

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

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

3. Безверхний В. Н. Решение проблемы сопряженности подгрупп в одном классе НЫН-групп //Алгоритмические проблемы теории групп и полугрупп и их приложение. ТГПИ им. Л. Н. Толстого, 1983 г. с.50−80.

4. Безверхний В. Н. Решение проблемы вхождения в некоторых классах групп с одним определяющим соотношением //Алгоритмические проблемы теории групп и полугрупп. ТГПИ им. Л. Н. Толстого, 1986 г. -с.3−22.

5. Безверхний В. Н. О пересечении подгрупп в НИИ-группах //Фундаментальная и прикладная математика 1998, том 4, № 1, -с. 199−222.

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

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

8. Безверхний В. Н. О группах Артина, Кокстера с древесной структурой //Алгебра и теория чисел: Современные проблемы и приложения. Тезисы докладов V Международной конференции. Тула, 2003, с. 33 34.

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

10. Безверхний В. Н., И. В. Добрынина И.В. Об элементах конечного порядка в группах Кокстера большого типа //Чебышевский сборник т.5, выпуск 1(9), 2004. с.30−39.

11. Безверхний В. Н., Добрынина И. В. Решение проблемы степенной сопряженности слов в группах Кокстера большого типа //Международная научная конференция. «Современные проблемы Математики, Механики, Информатики». Тезисы докладов. 2005. с.43−45.

12. Безверхний В. Н., Добрынина И. В. Решение проблемы обобщенной сопряженности слов в группах Кокстера большого типа //Чебышевский сборник т.5, выпуск 1(9), 2004. с. 39 62.

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

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

15. Безверхний В. Н., Логачева Е. С. Решение проблемы сопряженности подгрупп в одном классе НЬЛЧгрупп // Известия ТулГУ Серия Математика. Механика. Информатика. 2006. Том 12. Выпуск 1. с. 83−101.

16. Безверхний В. Н., Паршикова Е. В. Решение проблемы вхождения в циклическую подгруппу в группах с условием С (4)&Т (4) //Алгоритмические проблемы теории групп и полугрупп. ТГПУ им. Л. Н. Толстого, 2001. с.97−120.

17. Инченко О. В. Пересечение некоторых подгрупп конечно порожденнной группы Кокстера с древесной структурой //Чебышевский сборник. Том 9. Вып. 1(25), 2008, с.108−122.

18. Инченко О. В. Проблема обобщенной сопряженности слов в группах Кокстера с древесной структурой //Известия ТулГУ Естественные науки.2008. Выпуск 2, с.40−48.

19. Инченко О. В. Проблема сопряженности подгрупп в конечно порожденных группах Кокстера с древесной структурой//Материалы Международной научной конференции «Современные проблемы математики, механики, информатики» Тула, 2008, с. 6.

20. Безверхний В. Н., Инченко О. В. Проблема пересечения конечно порожденных подгрупп в группах Кокстера с древесной структурой// Известия ТулГУ Естественные науки. 2009. Вып.2. с. 16−31.

21. Инченко О. В. Проблема сопряженности подгрупп в свободном произведении двух двупорожденных групп Кокстера, объединенных по конечной циклической подгруппе // Известия ТулГУ Естественные науки.2009. Вып.2. с.38−54.