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

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

Инченко Оксана Владимировна

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

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

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

Москва - 2010

1 1 ЛЕВ 7010

003491648

Работа выполнена на кафедре алгебры, математического анализа и геометрии факультета математики, физики и информатики Тульского государственного педагогического университета им. Л.Н. Толстого.

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

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

Защита диссертации состоится 1 марта 2010 года в 16 часов на заседании Диссертационного совета Д 212.154.32 при Московском педагогическом государственном университете по адресу 107140, г. Москва, ул. Краснопрудная, д. 14, математический факультет МПГУ, ауд. 301.

С диссертацией можно ознакомиться в библиотеке Московского педагогического государственного университета по адресу: 119992, г. Москва, ул. Малая Пироговская, д. 1.

профессор Шмелькин Альфред Львович

кандидат физико-математических наук, Куликова Ольга Викторовна Ведущая организация: Ивановский государственный университет

Автореферат разослан

2010г.

Ученый секретарь диссертационного совета

О.В. Муравьева

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

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

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

Группа Артина - это группа &, заданная копредставлением с системой образующих я(,/е/, |/|<°°, и соотношениями а1и1аг.. = а]а1аг.., где слова, стоящие слева и справа, состоят каждое из чередующихся букв а. и а], Шц - элемент симметрической матрицы Кокстера М = (яг). ^

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

2 Новиков П.С. Неразрешимость проблемы сопряженности в теории групп. // Изв. АН СССР - Серия Математика. - Том 18. - С. 485-524.

соответствующей данной группе G, причем при i * j, mtj = mjt, m. e {2,3,..}.

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

Класс групп Артина содержит группы кос, копредставление которых было получено Артином, решившим в данном классе групп проблему тождества слов, используя геометрические методы4. Алгебраическая теория групп кос была построена Марковым A.A., который решил проблему равенства другими методами5. Гарсайдом и независимо Маканиным Г.С. для групп кос была решена проблема сопряженности слов6, доказано, что нормализатор любого элемента групп кос конечно порожден, и построен алгоритм выписывающий образующие этого нормализатора7. Гурзо Г.Г. получила алгоритм для нахождения образующих централизатора конечного множества элементов группы кос8. Отметим, что до настоящего времени неизвестна разрешимость проблемы равенства в конечно определенных группах Артина.

В 1972 году Брискорном и Сайто был введен класс групп - группы Артина конечного типа9. Группа Артина называется группой Артина конечного типа, если соответствующая ей группа Кокстера конечна. Брискорн и Сайто доказали разрешимость проблем равенства и

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

4 Artin Е. Theorie der Zöpfe //Abh. math. Semin. Univ. Hamburg. -1925. - 4. - P. 47-72.

5 Марков A.A. Основы алгебраической теории кос. II Труды математического института АН СССР.-1945.-С. 16.

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

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

8 Гурзо Г.Г. О централизаторах конечных множеств элементов группы кос. // Математические заметки. - 1985. - 37. - №1. - С. 3-6.

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

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

В 1983 году Аппелем К. и Шуппом П. был выделен класс групп Артина большого и экстрабольшого типа10. Если все числа ти симметрической

матрицы Кокстера для групп Артина или Кокстера больше либо равны трем, то группы называются группами Артина или Кокстера большого типа. Если все числа /п. симметрической матрицы Кокстера для групп Артина или Кокстера больше трех, то группы называются группами Артина или Кокстера экстраболъшого типа. Для групп Артина и Кокстера экстрабольшого типа Шуппом П. и Аппелем К. было получено решение проблем равенства и сопряженности слов10. Безверхним В.Н. и Кузнецовой А.Н. доказано, что группы Артина большого типа не имеют кручения", и в данном классе групп разрешима проблема вхождения в циклическую подгруппу12. Аппелем К. и независимо Безверхним В.Н. была решена проблема сопряженности слов13, Безверхним В.Н. доказана разрешимость обобщенной проблемы сопряженности слов14 для групп Артина большого типа. Для групп Кокстера

10 Appel К., Schupp Р. Artin groups and infinite Coxeter groups// Invenf. Math. - 1983. - V. 72. -P. 201-220.

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

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

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

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

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

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

Итак, пусть б конечно-порожденная группа Артина.

И пусть й - соответствующая группе б конечно порожденная группа Кокстера, полученная присоединением соотношений а* = 1, I = 1, п, и имеющая копредставление С = ^а|,...а/,(а1)2,(^а;.)т"1<1,у Каждой

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

ребра е, то ребру соответствует соотношение вида = (а¡а¡У" для

группы ¿г и (а а/)"' =1 для группы й. Группа Артина или Кокстера имеет древесную структуру, если граф Г* является дерево - графом.

15 Безверхний В.Н., Добрынина И.В. Решение проблемы сопряженности слов в группах Кокстера большого типа. // Чебышевский сборник: Труды V Международной конференции «Алгебра и теория чисел: современные проблемы и приложения» - Тула. -2003. - Т.4. - Выпуск 1(5).- 2004. - С. 10-33.

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

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

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

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

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

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

МсСатшопс! (Маккамонд) исследовал прямоугольные группы, то есть группы Кокстера с древесной структурой в случае, когда все числа т0

симметрической матрицы Кокстера принимают значения т. ={0,2}. В

диссертации рассмотрен общий случай, когда числа симметрической

матрицы Кокстера принимают значения тц е {0,2,3,..}.

Цель работы

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

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

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

20 Цпс1оп Я. Оп ОеЬпЧ а^опИп. МаШ. Апп., - 1966. - 166 - Р. 208-228.

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

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

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

1. дано описание централизатора элементов конечного порядка;

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

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

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

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

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

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

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

Основные результаты диссертации докладывались на семинаре «Алгоритмические проблемы теории групп и полугрупп» под руководством профессора Безверхнего В.Н. (ТГПУ им. Л.Н.Толстого, 2004г., 2005г.,

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

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

Публикации

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

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

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

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

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

Лемма 1. Пусть б - конечно порожденная группа Кокстера с древесной структурой. Слова у и к, длина каждого из которых равна единице в группе Кокстера б, сопряжены тогда только тогда, когда существует

22 Громов М.Л, Гиперболические группы. - Ижевск: Институт компьютерных исследований, 2002.

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

Слово и> назовем И-несократшшм (или И-приведенным), если м свободно приведено и не содержит подслова 5 такого, что причем

г = , ге И и |л|>|г|, где Я - все циклически несократимые слова равные единице в С.

Поддиаграмма Я = и"=1 Ц образует полосу в ^-приведенной диаграмме М с граничным циклом ЭМ = У^З, если

1. VI, 1 = 1, п -1 Э£>,Р] = е, где е - ребро;

2. V/, I = 1,п ЭО(р)у = у1, где у. - связный путь, причем \у\ > 1;

3. |эд,пи = !эд. иэо.Пг)! и |эо.Пг|=|эо. \(эл.|>)|;

4. у/, у = хп-\ |эо.пН=1э^П4

Слово м И - несократимо, если приведенная диаграмма М, граничной меткой которой является слово и\ не содержит полос.

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

Циклически К и /? - несократимое слово и> в группе Кокстера й назовем тупиковым, если к нему не применимо кольцевое сокращение.

Лемма 2. Пусть V, и> - тупиковые слова из С и пусть V и и» сопряжены в й. Тогда |у| = |н| и никакое слово кеб такое, что |и| < |и] не сопряжено с V.

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

Выделим в дереве-графе Г конечно порожденной группы Кокстера б с древесной структурой связный подграф Г , где у - количество вершин,

принадлежащих дереву-графу Гг Подгруппу группы С, порожденную

образующими, соответствующими вершинам дерева - графа Г1, назовем

параболической подгруппой группы О и обозначим ее через С.. Во второй

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

Лемма 3. Пусть С - конечно порожденная группа Кокстера с древесной структурой, с множеством образующих А, |А|<°°. И пусть п>еС, и> -тупиковое слово не равное единице в (?. Слово ы сопряжено некоторому слову уе то есть существует слово ге О такое, что z~'wz = v, где |у[>2, - параболическая подгруппа с множеством образующих А1, А. с А. Тогда м,I - слова на образующих А.. Из леммы 3 следует

Следствие 1. Пусть С конечно порожденная группа Кокстера с древесной структурой, - параболическая подгруппа группы б. Пусть м -

тупиковое слово из группы Б, \vsGj . Тогда С0О) = Сс (уу), где Сс(и») -

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

Третий параграф первой главы посвящен описанию централизатора элементов конечного порядка. Доказаны следующие утверждения:

Лемма 4. Пусть б - конечно порожденная группа Кокстера с древесной структурой; и> - циклически /¿-несократимое слово в С, и>е С^ , > 1, где подгруппа СоЬ имеет копредставленис СаЬ={а,Ъ\а1,Ьг,(аЬ)т-^,таЬ>2, Тогда централизатор элемента ы есть циклическая группа конечного порядка, порожденная элементом длины два.

Пусть слово VveG, | и] = 1 и С(и>) - централизатор слова ю. Обозначим через СнО) подгруппу полученную из С(и>) вычеркиванием из множества порождающих слов элемента и\

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

В четвертом параграфе главы рассматривается проблема обобщенной сопряженности слов, которая состоит в том, что необходимо установить существует ли алгоритм, позволяющий для любых двух конечных множеств слов {уД=|/1 из группы определить, существует ли такое г из той же

группы,что &"., (г"Уг = у().

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

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

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

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

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

Группа С удовлетворяет условию максимальности, если всякая возрастающая последовательность ее подгрупп Я, < Н2 <..., стабилизируется, то есть существует натуральное число п такое, что для любогоМ>п, Ны = Я„=1 -... .

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

Безверхним В.Н. был получен следующий результат23: Теорема 2. Пусть б древесное произведение групп

объединенных по изоморфным подгруппам и.. < ^ и V ~ < с помощью фиксированного набора конструктивных изоморфизмов {/р0}: (р.. ) = . Тогда, если подгруппы У. и и ^ обладают условием максимальности и в

сомножителях разрешимы проблемы:

1. проблема вхождения;

2. проблема пересечения классов смежности любой конечно порожденной подгруппы Н < б, с подгруппой У < б,;

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

ив<с„

то в группе б разрешима проблема вхождения.

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

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

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

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

циклической подгруппе, то есть й = С,, * . Здесь доказаны теоремы:

(«,№)

Теорема 3. Пересечение конечного числа конечно порожденных подгрупп группы й = Б * С/, конечно порождено и существует алгоритм,

" ("'К)

выписывающий образующие этого пересечения.

Теорема 4. В группе в * Сл разрешима проблема пересечения

Ьк)

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

В четвертом параграфе дано обобщение на случай свободного произведения п двупорожденных групп Костера с объединением:

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

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

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

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

Теорема 7. В группе С? = * ^ разрешима проблема

(°'К)

сопряженности конечно порожденных подгрупп.

На основе полученного результата, методом математической индукции, в третьем параграфе доказана

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

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

Публикации автора по теме диссертации

[1] Безверхний В.Н., Инчепко О.В. Разрешимость проблемы вхождения в параболические подгруппы в группах Кокстера с древесной структурой, // Известия Тульского государственного университета. Серия Дифференциальные уравнения и прикладные задачи. -Выпуск 1. - 2006. - С. 47-58. - 0,69 пл. (Авторский вклад - 70%), (Бюллетень №4 от 2005 г.).

[2] Инченко О.В. Проблема обобщенной сопряженности слов в группах Кокстера с древесной структурой. // Известия Тульского

[4]

[5]

[6]

[7]

государственного университета. Естественные науки. - 2008. -Выпуск 2 - С. 40-48. - 0,5 п.л.

Безверхний В.Н., Инченко О.В. Проблема пересечения конечно порожденных подгрупп в группах Кокстера с древесной структурой. // Известия Тульского государственного университета. Естественные науки. - 2009. - Выпуск 2. - С.16-31. - 0,94 п.л. (Авторский вклад - 70%).

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

Безверхний В.Н., Инченко О.В. О кручении в группах Кокстера с древесной структурой. // Чебышевский сборник. - Том 6 - Выпуск 1. -2005. - С. 5-12. - 0,44 п.л. (Авторский вклад - 70%). Безверхний В.Н., Инченко О.В. Централизатор элементов конечного порядка конечно порожденной группы Кокстера с древесной структурой. // Чебышевский сборник. - Том 9. - Выпуск 1(25). - 2008. -С. 17-28. - 0,69 п.л. (Авторский вклад - 70%).

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

Подп. к печ. 25.01.2010 Объем 1 пл. Заказ №.16 Тир 100 экз. Типография МПГУ

Введение.

Глава 1. Метод диаграмм при решении некоторых алгоритмических проблем в конечно порожденных группах Кокстера с древесной структурой.

1. Диаграммы над конечно порожденными группами Кокстера с древесной структурой.

2. Параболические подгруппы.

3. Описание централизатора элементов конечного порядка.

4. Разрешимость проблемы обобщенной сопряженности слов.

Глава 2. Проблема пересечения конечно порожденных подгрупп в конечно порожденных группах Кокстера с древесной структурой

1. Разрешимость проблемы вхождения.

2. Базовые понятия.

3. Случай свободного произведения двух двупорожденных групп Кокстера объединенных по конечной циклической подгруппе.

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

Глава 3. Проблема сопряженности подгрупп.

1. Необходимые утверждения.

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

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

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

Комбинаторная теория групп долгое время развивалась под влиянием геометрии и топологии. Как самостоятельная наука со своей проблематикой она оформилась по существу только после того, как в 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.