Положительные элементы и рациональные множества в группах тема диссертации и автореферата по ВАК РФ 01.01.06, кандидат физико-математических наук Воронина, Ольга Александровна

• Воронина, Ольга Александровна
• кандидат физико-математических наук
• 2012

Оглавление диссертации кандидат физико-математических наук Воронина, Ольга Александровна

СОДЕРЖАНИЕ

ВВЕДЕНИЕ

ГЛАВА 1 ЭЛЕМЕНТЫ ПОЛОЖИТЕЛЬНОГО ВИДА В ГРУППАХ

1.1 Основные определения

1.1.1 Порождающие множества

1.1.2 Положительные элементы в группах

1.1.3 Положительные элементы в свободных абелевых группах и векторных пространствах

1.2 Одновременное приведение элементов абелевых групп и векторных пространств к положительному виду

1.2.1 Основные определения

1.2.2 Необходимые факты геометрического характера

1.2.3 Основные результаты

1.3 Нильпотентные группы

1.3.1 Основные определения

1.3.2 Порождающие множества нильпотентных групп

1.3.3 Основные результаты

ГЛАВА 2 РАЦИОНАЛЬНЫЕ МНОЖЕСТВА В ГРУППАХ

2.1 Основные определения

2.1.1 Рациональные множества

2.1.2 Группы Коксетера

2.2 О рациональных множествах разрешимых групп

2.2.1 Известные результаты

2.2.2 Основные результаты

2.3 О 4-порожденных прямоугольных группах Коксетера

2.3.1 Известные результаты

2.3.2 Основные результаты

ЛИТЕРАТУРА

Введение диссертации (часть автореферата) на тему «Положительные элементы и рациональные множества в группах»

ВВЕДЕНИЕ

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

Одно из наиболее актуальных направлений исследований в теории групп определяется различными вопросами о каноническом представлении элементов группы и ее подмножеств тем или иным эффективным способом. Это определяет связь теоретико-групповых проблем с проблемами теории формальных языков.

Комбинаторная теория групп, основы которой изложены в монографиях Магнуса, Карраса, Солитера [27], Линдона, Шуппа [26], связана с представлениями групп через порождающие элементы и определяющие соотношения. Особое значение в ней придается конечным представлениям и соответственно конечно определенным группам. Многочисленные примеры таких групп представлены в книге Коксетера, Мозера [4]. Исторический обзор содержится в [31]. При данном подходе выделяются группы, допускающие нормальные формы элементов, эффективные переписывающие процессы и т.п.

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

Подмножества свободного моноида называется языками. Среди них выделяются, например, регулярные (рациональные) языки и их различные обобщения. Классическая теория полугрупп исследует регулярные множества и конечные автоматы. Теорема Клини устанавливает связь между этими понятиями. См. по этому поводу монографии [6], [9], [15], [24].

Данное направление получило также свое теоретико-групповое развитие. Во многом этому способствовали известные лекции Гилмана [7]. В теоретико-групповом контексте одним из подходов является рассмотрение формальных языков вместе с гомоморфизмами в группы. В частности, одна из известных задач - нахождение формальных языков из некоторого класса (например, рациональных), которые отображаются на группу биективно. С другой стороны, рациональные множества можно рассматривать непосредственно в группах, являющихся частным случаем моноидов. Подобные исследования представляют самостоятельный интерес. Укажем, например [3], [10-11], [16-20], [28-29].

В настоящей работе изучаются положительные элементы свободных абелевых групп и группы Гейзенберга, а также рациональные подмножества разрешимых групп. Понятия положительного и потенциально положительного элемента свободной группы дано А. Мясниковым, В. Шпильрайном в известном сборнике нерешенных проблем теории групп - «Open problems in combinatorial and geometric group theory» [1]. Нами рассматривается естественное обобщение этих понятий на произвольные группы. Мы также несколько изменили терминологию, говоря об элементах положительных относительно данной системы порождающих элементов и положительных элементах.

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

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

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

Заметим в этой связи, что в любой конечно порожденной почти абелевой группе все рациональные подмножества булеву алгебру образуют. То же самое можно сказать о свободных моноидах и свободных группах. Г. А. Баженова доказала [20], что класс групп с отмеченным свойством замкнут относительно свободных произведений и конечных расширений. Однако в классе конечно порожденных разрешимых групп все известные примеры групп с этим свойством почти абелевы. Г.А. Баженова установила в своих работах [3], [17], [18], [19], что любая нильпотентная, полициклическая, метабелева группа с этим свойством почти абелева. Она также доказала, что конечно порожденные разрешимые группы конечного ранга с этим свойством почти абелевы. В целом, однако, гипотеза В.А. Романькова остается открытой.

В работе рассмотрены конечно порожденные матричные группы и нильпотентные расширения абелевых групп. Для них доказаны теоремы, аналогичные теоремам Г.А. Баженовой. Также рассмотрены рациональные подмножества 4-порожденной прямоугольной группы Коксетера.

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

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

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

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

1. Найдены необходимые и достаточные условия одновременного приведения набора элементов свободной абелевой группы Ап (векторного

пространства 0" или Я") к положительному виду.

2. Описаны положительные элементы группы Гейзенберга.

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

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

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

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

Апробация работы. Результаты диссертации докладывались на международной конференции «Алгебра и математическая логика», посвященной 100-летию со дня рождения В.В. Морозова (г. Казань, 2011 г.), а также на Омском алгебраического семинаре.

Публикации. Основные результаты диссертации опубликованы в пяти работах ([32]-[36]).

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

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

(векторного пространства О" или Яп) к положительному виду и о положительных элементах группы Гейзенберга О.

Вторая глава содержит некоторые известные определения и результаты см. [17], [19] о рациональных множествах и группе Коксетера, используемые для получения основных результатов. В данной главе доказывается, что если в прямом произведении конечно порожденной разрешимой группы С с бесконечной циклической группой I все рациональные подмножества

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

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

Заключение диссертации по теме «Математическая логика, алгебра и теория чисел», Воронина, Ольга Александровна

2.3.2 Основные результаты

Сформулируем и докажем несколько утверждений о приведении слов языка {а, Ь, с,с!}* к некоторому стандартному виду так, что задаваемый словом элемент группы при этом не изменяется.

Лемма 5. 1) Если Я с; [а, Ь, с} - рациональный язык, то существует рациональный язык Я' с {а, с}* {е, Ъ} такой, что (р(Я)~ (р(Я').

2) Если Яс:{Ь,с,с1}*- рациональный язык, то существует рациональный язык Я' с \Ь, с} такой, что (р{я) = (р{Я').

Доказательство. Пусть R задано автоматом Г = (V,E,v0,VT), где метки ребер равны s,a,b,c. Построим новый автомат Г' = (V,E',v'0,V^), где множество вершин - V'= Vx{s,b}\j{t), начальная вершина - v'0=(v0,s), множество выходных вершин Vf={t}, t- новый символ, а множество ребер Е' определяется следующим образом: для любого ребра (v1?/1,v2)e Е, если Л = е,а,с, то Е! содержит ребра ((vl5é:),Л,(у2,Ь)) и ((vj, ô), A, (v2,¿»)); если же Л = Ь, то Е' содержит ((vj,£-),£-,(v2,&)) и {iyvb\s,{y2,s^)\ кроме того, для каждой вершины v е VT множество Е' содержит ((v, s), s, t) и ((v, b), b, t). Других ребер нет.

Автомат Г' задает рациональный язык, который мы обозначаем буквой R'. Неформально, переход от Г к Г' - это добавление "ячейки памяти" (мы заменяем V на V = Fx — ) так, что, когда мы идем по некоторому пути, то любая встретившаяся буква а или с попадает в выходное слово, как и раньше, а встретившаяся буква b — не попадает, но четность числа встретившихся букв b запоминается (если мы находимся в вершине вида (v,è), значит, нам встретилось нечетное число букв Ь, если в вершине (v,e), то встретилось четное число букв Ь), и если в конце пути это число оказывается нечетным, то мы добавляем в выходное слово одну букву Ь. Поскольку ср(Ь) перестановочно с ср(а) и (р{с), то изменение выходного слова несущественно с точки зрения того, какой элемент группы оно задает, то есть

Доказательство пункта 2) полностью аналогично.

Лемма 6. 1) Если Rœ{ci,c}* {s,b}~ рациональный язык, то существует рациональный язык R' ç {s, с){ас) {s, a}{s, b} такой, что

2) Если Я<^{Ь,с1} {в, с] - рациональный язык, то существует такой рациональный язык Я' с: {е, Ь}(с1ЬУ {е, £/}{<?, с), что

Доказательство. 1) Пусть язык Я задан конечным автоматом Г = (У,Е,у0,Ут), в котором метки ребер равны е, а, Ь, с. Пусть МсГхГ- множество всех таких пар вершин , у2 ) автомата Г, что в автомате Г существует путь из v, в у2 с меткой Л е 1). Пусть Е' - Е{] {(у,, е, у2 ) | ^, у2 ) е М). Автомат Гх = (У,Е',у0,Ут) задает рациональный язык Ях =з Я.

Заметим, что если имеется путь в автомате Гх с меткой Л, то можно переделать его в путь в автомате Г, заменив каждое ребро из Е'\Е с началом в вершине у, и концом в вершине у2 на путь в Г из V, в у2 с меткой из <р~1( 1).

Метка переделанного пути Л' будет возможно, не равна Л, но элементы группы, представленные словами Л и Л' равны:

Далее, если некоторое слово w принадлежит языку Я, то в языке Я' = Ях П {е, с}(ас)* {в, а}{е, Ь} найдется слово V такое что (р{м>) = .

Действительно, слово м>, во-первых, принадлежит языку Ях, то есть являются меткой некоторого пути р = (у0,/1,у1),(у1,/2,у2),.,(уи1,/„,у„) в автомате Гх (здесь е Ут), во-вторых, принадлежит языку (ас)* {б, Ь}. (Можно записать м? = 1х12.1п; здесь каждое /г равно либо с, либо а, либо либо Ъ либо с.)

Если слово м> содержит подслово и, равное аа либо сс, то слово м = /-./-+от соответствует некоторому подпути в = у/„1,у/,.,у/+т пути р.

Пара (yjx,VJ+m) принадлежит М, и существует ребро Е' в автомате Гх. Заменим в пути р фрагмент в на ребро Метка полученного пути м>1=1х.1]х1]+т+х.1п принадлежит языку Ях и языку ас) {е,Ь}, кроме того, (р{учх) = (р{м?). Далее, слово к/ короче, чем слово м?. Повторяя процесс удаления подслов вида аа и сс получаем в итоге слово м?' О, и все Я{ равны а или с, причем всегда Ф 1М (буквы а и с чередуются), а е равно либо в, либо Ъ. Но это и означает, что е К.

Видим, что

Лемма 7. 1) Если Я с {б, Ь}(с!Ь)*{е, <Л\{£, с} - рациональный язык, то существуют такие рациональные языки Ях, Я2, Я3, Я4, Я5, что

Я = Ях и Я2Ь и Я3с и Я4сЬ ия5, и языки Я1, г = 1, 2, 3, 4, состоят из слов вида

1), а Я5 с {е, Ь, с, сЪ}.

2) Если Я с {е, с)(ас) {е, а}{а, Ь} - рациональный язык, то существуют такие рациональные языки Ях, Я2, Я3, ЯА, Я5, что Я = Ях иЯ2ЬиЯ3сиЯАЬсия5, и языки Я(, г = 1, 2, 3, 4, состоят из слов вида

2), а Я5 с {е, Ь, с, Ьс}.

Доказательство.

1) Разобьем язык Я на части следующим образом. Пусть = Я П {а,с}*сЬ -этот язык состоит из всех слов языка Я, которые оканчиваются на сЬ; далее пусть £3 =ЯП{я,с}*с = (Я\5,4)П{я,с}*с - это те слова языка Я, которые оканчиваются на с; далее, S2 = (R \ ^4)П {а,с}*Ь - это те слова языка R, которые оканчиваются на Ь, но не на cb; и, наконец, = R\(S2[j S3[j S4) -это те слова языка R, которые не оканчиваются ни на Ъ, ни на с.

Ясно, что R = (5, U S2 U S3 U S4) • Далее, для i = 1, 2,3, 4, определим языки S' следующим образом: S¡ = S¡, S'2 = {w e {a, c}* \wb g S2}, S'3 = {w e {a,c}* | wc e S3}, £4 = {w e {а, с}* | web e S4}. Видим, что

Языки S¡, i = 1,2,3,4, рациональны (для доказательства их рациональности можно использовать следующий факт: если А - конечный алфавит, i? с А*- некоторый язык над этим алфавитом, w е Л* -произвольное слово, и язык Rw рационален, то язык R также рационален). Кроме того, для z = l,2,3,4, S[ <^{£,с}(ас)* {е,а}, то есть слова языка S¡ состоят из букв ¿г и с и не содержат подслов аа и сс. Несложно также проверить, что слова языка S¡ не оканчиваются на букву с. Положим R¡ - S¡ \ {s} при i = 1, 2, 3, 4. Языки R¿ состоят из слов вида (1).

Заметим теперь, что множество R5 = R\(Rl[j R2b U R3c U R4cb) содержится в конечном множестве {s, b, с, cb}.

Утверждение пункта 1) доказано. Утверждение пункта 2) аналогично.

Теорема 8. Пусть язык Rcz{a,b,c,d} рационален. Тогда существует такой рациональный язык R', состоящий из слов вида (*), что (p{R') =

Доказательство. Пусть язык R задан конечным автоматом Г = (V,E,v0,VT), в котором метки ребер равны е, а, Ь, с, d, be.

Можно считать, что если две вершины из V соединены путем с меткой w такой, что (p{w) равно одному из значений 1, (p{b), (р{с) или леммы 6.)

Для каждой пары вершин (у,,у2)е Vх V определим рациональные языки Р(у15у2) и <2(у 1зу2) следующим образом: в автомате Г сделаем у, начальной вершиной, а у2 - единственной выходной вершиной. Далее, удалим все ребра с меткой с1. Полученный конечный автомат задает язык Р(у,,у2)с; {а, Ь, с}". Если же удалить ребра с меткой не а а, то получим другой конечный автомат, задающий некоторый рациональный язык (¿{у^у-^с! [Ь, с, ¿/}\

Применяя леммы 5, 6, 7, получим для каждой пары (у,,У2)еКхК рациональные языки

Р'{у 15у2), Рх{ух,У2), />(у„у2), р3(у],у2), рду^), р5(^,у2) такие, что (р{Р{ух, у2 )) = (р{Р'{ух, у2 )) и р^1^2) = р1(у1,у2)ир2ь,у2)би/,з(^1^2)си/)4(у1,у2)сж/)5(у,,у2), причем языки ^(у15у2), г = 1,2,3,4 состоят из слов вида (1), а {е,Ь,с, сЪ}.

Аналогично для каждой пары (у,, у2 ) е V х V получим рациональные языки б'О'л)» 61(^^2)» 62(^2)» £3(^2), 64(^1^2), 65(^^2) такие, что , у2 )) = , )) и причем языки бг^!,У2), г = 1,2,3,4 состоят из слов вида (2), а ь>М

Теперь мы можем построить обобщенный автомат Г' над {а,Ь,с,с1}* который даст нам требуемый язык Я' или язык, отличающийся от Я' лишь добавлением конечного числа элементов.

Множество вершин автомата Г' - это множество (Ух{б, Ь, с, Ьс}х {/,//})У {и0,ит}, где 1,П,и0,ит - новые символы. Вершина и0

- начальная, вершина ит - единственная выходная. Далее, ребра автомата Г' получаются следующим образом.

Во-первых, для каждой пары (ух,у2)

Я'-) ух,£,1),рх(ух,у2), (у2,£,//)) ух,с,1),сорх{ух,у2), (у2,£,п)) v ((v ((v ((v ((v ((v ((v ((v ((v ((v ((v ((v ((v ((v ((v ((v ((v

1\р2(ух,у2),{у2,ъ,п)) , с, 1),сор2(ух,у2),(у2, ъ,п)) ,£,1),Р3(ух,у2), (у2,с,п)) , с, /), с О р3 (ух, у2 ), (у2, с, ii)) ,£,1\ра{ух,у2),{у2,ъс,щ) ,с,/),сор4(V,,у2), (у2,Ъс,ii)) ,£,//), 2), (у2,£,1)) £>2(у,,У2), (у2,Ь,1)) ,с,П),()2(ух,У2), (У2,ЪС,1)) ,£,11), ()ЪЬ>Х,У2\ (у2,С,1)) ,с,п),<2(v2,£,1)) ,£,11),£>4{УХ,У2), (у2,Ьс,1)) с,//),е4(у1,у2)> (У2,Ь,1)) ,Ъ,1),Рх(ух,у2), (у2,Ь,П)) ,Ьс,1),сОРх(ух,у2), (у2,Ь,Щ) ,Ь,1),Р2(ух,у2), (у2,£,Н))

1, Ьс, /), сОР2 (V], У2), (у2, е, II)) ((^1, Ь, I), Р3 (у, , у2 ), (у2 , Ьс, II)) ((V, ,Ьс,1),с О Р3 (V,, V,), (у2, Ьс, II)) ((V! ,Ъ,1), Р4(V!, ), {у2,С, II)) (0^1, Ьс, /), С О Р4 (V!, У2 ), (V2, с, II))

V!, 6с,Я), А О а(У„У2), (У2,с,/)) ((^Д/Д&О&Су,,^), (У2Д/)) ((у„ Ьс,II), Ъ О е2(у„г2), (у2,6с,/)) {^ъ,п),ъод^х,у2),{у2,с,1)) ух,ЪС,П),Ъ02^х,У2\(V 2,е,/))

О 64(^^2), (у2,М))

Во-вторых, существуют два ребра (м0, {г}, (у0 ,£,/)) и (м0, {¿г}, (у0 , //)). В-третьих, для каждой вершины у е¥т, для каждого х е {б-, Ь, с, Ьс] и для каждого у е {1,11} существует ребро у), {х},ит).

Символ О, используемый выше, означает следующее. Если слово имеет вид (1), то элемент группы ср(с)(р{м) можно записать словом со, имеющим вид (1). (Если м> начиналось на букву с, то м> = ссо, иначе со = см?.) Слово со вида (1), которое определяется таким образом однозначно, обозначим символом сОм?.

Аналогично, если слово имеет вид (2), то элемент группы (р{Ь)(р{ можно записать (единственным) словом со, имеющим вид (2), и мы обозначаем Ь О м> = со.

Далее, если язык М с {а,с}* состоит из слов вида (1), то мы обозначаем сОМ = {сОм?\м?еМ}, а язык состоит из слов вида (2), то

ЬО М = {ЬОм?\м? е М}. Если язык М рационален, то язык с О М, (соответственно ЬОМ) также рационален.

В другом контексте символ О не определен.

Обозначим язык заданный автоматом Г', буквой £. Легко видеть, что язык £ состоит из слов вида (*). Действительно, любой "успешный" путь в данном автомате имеет либо вид и0,{е},И, = (у0,£,/)), (щ,1х,и2), (и2,/2,и3),.,(ип!, 1пх,ип=ит) (где п> 2, и для всех нечетных 1</<и-1 вершина и1 содержится в Ух [е, Ь, с, Ьс]х {/}, а для всех четных 1 < г < п -1 вершина и1 содержится в V х [б, Ь, с, Ьс]у. {//} либо вид и0, их = (у0,£,II)), (щ,1х,и2), (и2,/2,иъ),.,(ипх,1пх,ип=ит) (где п > 2, и для всех нечетных 1 < / < п -1 вершина иг- содержится в Ух \е, Ъ, с, Ьс\у. {//}, а для всех четных \

Но если ребро ведет из (ух,х,1) в то его меткой является множество слов вида (1), а если ребро ведет из {ух,х,П) в (у2,%,1), то его меткой является множество слов вида (2). Таким образом, произведение к—К-2 состоит из слов вида (*), у которых "остаточная часть" (суффикс-множитель, являющийся словом вида (3)) равна е\ далее, 1ПХ - это всегда одноэлементное множество, содержащее некоторое слово вида (3).

Теперь можно приступить к доказательству того, что 5 "почти равно" требуемому Я'. Вначале докажем, что

1,(р(Ь),(р{с\

Пусть ^ Пусть р = (у0,Я1,у1),(у1Д2,у2),.,(у„1Д„,у„), где УпеУГ

- путь в автомате Г с меткой уу = ЛХ.ЯП е Я такой, что g = к. Можно считать, что слово w со свойством cpiyv) = g, путь р и его разбиение на подпути выбраны так, что подпутей к минимально. В частности, тогда либо для всех нечетных 1 < / < к слово 6ùi принадлежит {а, Ь, с] , а для всех четных / слово coi принадлежит {b, с, d) , либо наоборот, для нечетных i col g {b, с, d}*, а для четных i coi g [а, Ъ, с} .

Далее, либо к = 1 и (p{w)e {l,(p{b\(p(c),(p{bc)}, либо ни для каждого coi не выполняется равенство (р(о)^] = 1, (p(cD¿)- подпуть Vj на это ребро, мы можем присоединить его к предыдущему или последующему подпути, но тогда число подпутей можно уменьшить - получается противоречие.)

Далее, coi g /,(v/.;] , ) или coi g Q{y¡. ¡, vJt ), и существует такое - (v,. ■»JU Л (vJH, v> U /' (v,,.,, v,. > и /', (vjH, V, I/., или, соответственно, такое в, s а Ьн, vh )u a (vyH, v,, > и a (v,,,, Vji > и a, Ь,ч, vy, , что (p{pi) = (р{в¡). В частности, (p{0x).(р{вк ) = g.

Теперь индукцией по i = l,.,k покажем, что в автомате Г' существует путь

M0,{4v0), (vq,?;,^), (VJ , Г2 , V2 ) , ., (v,.,,^.^) такой,что vm={vjm,xm,ym j, m = 0,1, и ср{вх ). хр(в1 ) е çfc. Iixl ). Если для i утверждение верно, то для i +1 выберем из списка или из списка 02 (у., у.+] )&, 04(vJ|ivJм})ci то множество, которому принадлежит <9г+1. Обозначим это множество £>. Видим, что (р{вх).(р{вм)&(р(Тх.Т,х1В).

Пусть £> равно > у//+] (здесь г = 1, 2, 3 или 4, а а равно £, Ь, с или сЬ). Тогда если хг = £ или хг■ = Ъ, то в автомате Г' существует ребро {у^^у;^,!)?^^^)?^^,!!)), где хм равно тому из слов £,Ь,с,Ьс, которое представляет элемент (р(х{а). (Заметим, что ср(Ь)(р(о) = гр(в)ср(Ь).) Полагаем Т1+] = Рг{уи,у]м).

Если же х(. = с или хг -Ьс, то в автомате Г' существует ребро где х.+1 равно тому из слов

Ь,с,Ьс, которое представляет элемент (р{х^)(р{с)~{

1 + 1 г v у/ у1+1 /

Полагаем Уг+1 = (у/+1,хг+1,//), и в данном случае утверждение доказано для I + 1.

Аналогично, пусть £> равно Qr{yj ,Vjм)a (здесь г = 1,2,3 или 4, а а равно £, Ь, с или Ьс). Тогда если х- = £ или х1■ = с, то в автомате Г' существует ребро ={у],х1,П)дг{угде х;+| равно тому из слов £,Ь,с,Ьс, которое представляет элемент (р{х^). (В данном случае мы имеем перестановочность ср(с)(р(о) = (р{р)(р{с).) Полагаем Т1+1 = Qr{yj ,Vj^ ).

Если хг- = Ъ или х1 =Ьс, то в автомате Г' существует ребро (у, = (ул , х;, //), ЬО(2г (у., у/ +1), (у/ +1, х;+|, /)), где хм равно тому из слов Ь, с, Ьс, которое представляет элемент (р{х()(р(Ь)~\р{а). (Буква с из слова х; переставляется направо через Qr, на букву Ъ мы умножаем ()г слева.) Полагаем Т1+1=ЬО()г (у, , у]м).

Полагаем угЧ1 = (у^ ,хг+1,/), и утверждение доказано для г +1. Далее, видим, что из вершины Ук = (уп, хк, ук) ведет ребро с меткой {хк} в вершину ит. Присоединяя его к пути, только что построенному по индукции, получаем "успешный" путь в автомате Г' с меткой м = т\-ткхк с 5, но ё = ср{вх).(р{вк)е (р(Тх.Ткхк) с . Включение (51) доказано. Теперь докажем, что

52)

Пусть g = (р{м), м? е 5. Тогда в автомате Г' существует путь (щ,{е\их =(у1,е,у1)), (их,1х,и2),(и2,12,щ\.,(ипх,1п^,ип = ит), где п> 2, и для каждого 1 < г < п -1 вершина и1 - {у1, х1, у1) содержится в V х [е, Ь, с, Ьс]х {/,//}, такой, что м>

Такой принцип построения ребер в автомате Г'.)

Кроме того, известно, что 1пх - {хпх} и хх = а.

Тогда g = (р{у?) = (р{1х).(р{1п2)(р{1пх) содержится в произведении

Определим язык Я', построение которого было главной целью доказательства: Я' = 5 и {и> е Ь, с, Ьс} | ср{м?) е (р{Я^\ ■ Теорема доказана.

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

Доказательство. Пусть Я - рациональное подмножество группы Ск4. Тогда множество Я равно (р{0) для некоторого рационального языка ()с:{£,Ь,с,£}}*. По теореме 8 можно считать, что язык содержится в Ь. Поскольку Ск4 - биекция (см. предположение 3), то (рациональный) язык L\Q отображается на Ск4 \Я при отображении ср. Значит, множество Ск4 \ Я рационально. Предложение доказано.

В итоге мы получаем следующий результат: все 4-порожденнные прямоугольные группы Коксетера являются ЯБВА -группами.

Список литературы диссертационного исследования кандидат физико-математических наук Воронина, Ольга Александровна, 2012 год

ЛИТЕРАТУРА

[1] Baumslag G., Myasnikov A. G., Shpilrain V. Open problems in combinatorial group theory, second edition, from: "Combinatorial and geometric group theory (New York, 2000/Hoboken, NJ, 2001)", // Contemp. Math. 296, Amer. Math. Soc., 2002, Problem F34. 1-38.

[2] Baumslag G., Myasnikov A., Roman'kov V. Two theorems about Equationally Noetherian Groups// Journal of Algebra, v. 194, 1997, 654-664.

[3] Bazhenova G. A. Rational sets in polycyclic groups// Международная конференция "Комбинаторные и вычислительные методы в математике". -Омск, 1999, 76-81.

[4] Coxeter H.S.M., Moser W.O.J. Generators and relations for discrete groups// Springer-Verlag, New York - Heidelberg, 1972.

[5] Coxeter H. S. M., Descrete groups generated by reflections// Annals of Mathematics, v. 35, 1934, 588-621.

[6] Eilenberg S. Automata, Languages, and Machines, A and B// New York: Academic Press, 1974.

[7] Gilman R.H. Formal Languages and Infinite Groups// DIMACS Series in Discrete Mathematics and Theoretical computer science, AMS. - 1996, v. 25, 27-51.

[8] Grunschlag Z. Algorithms in Geometric Group Theory// PhD thesis, University of California at Berkley, 1990.

[9] Harrison H. Introduction to Formal Language Theory// Addison-Wesley Reading, MA., 1979.

[10] Herbst Т., Thomas R.M. Group presentations, formal languages and characterizations of one-couter group// Theoret. Comput. Sci. v. 112, 1993, 187-213.

[11] Kambites M., Silva P. V., and Steinberg B. On the rational subset problem for groups // Journal of Algebra, 309, 2007, 622-639.

[12] Kapovich I. One-relator groups and the Howson property// Comm. In Algebra. N.3, v. 27, 1999, 1057-1072.

[13] Lohrey M., Steinberg B. The submonoids and rational subset membership problems for graph groups // Journal of Algebra 320(2), 2008, 728-755.

[14] Lohrey M., Steinberg B. Tilings and submonoids of metabelian mroups, Theory of Computing Systems, Springer, New-York, 1432-1435.

[15] Revesz G. Introduction to Formal Languages // McGraw Hill, New York, 1983.

[16] Roman kov V. A. On the occurrence problem for rational subsets of group// Международная конференция "Комбинаторные и вычислительные методы в математике". - Омск, 1999, 235 - 242.

[17] Баженова Г. А. Замкнутость одного класса групп относительно свободного произведения// Сиб. матем. журн., 2000, 4, №41, 740-743.

[18] Баженова Г. А. О регулярных множествах в группах// Kurosh Algebraic Conference '98, МГУ, Москва, 1998, 137-138.

[19] Баженова Г. А. О рациональных множествах в конечно порожденных нильпотентных группах// Алгебра и логика. Т.4, №39, 2000, 379 - 394.

[20] Баженова Г. А. О рациональных множествах в разрешимых группах. Кандидатская диссертация// Омск: ОмГУ, 1999.

[21] Берже М. Геометрия Т-1// М.: Мир, 1984.

[22] БиркгофГ. Теория структурам.: 1952.

[23] Ван дер Варден Б. Л. Алгебра// М.: Наука, 1976.

[24] Карпов Ю. Г. Теория автоматов// СПб.: Питер, 2002.

[25] Каргаполов М.И., Мерзляков Ю.И. Основы теории групп// 3-е изд., М.: Наука, 1982.

[26] Линдон Р., Шупп П. Комбинаторная теория групп// М.: Мир, 1980.

[27] Магнус В., Каррас Л., Солитер Д. Комбинаторная теория групп// М.: Наука, 1974.

[28] Недбай М.Ю. Некоторые свойства рациональных множеств в группах// Международный семинар по теории групп. - Екатеринбург, 2001, 158-160.

[29] Недбай М.Ю. О высоте рациональных подмножеств в группах// Вестник Омского университета. Вып. 4. - Омск: Изд-во ОмГУ, 2000, 11-13.

[30] Супруненко Д.А. Группы матриц// М.: Наука, Физматлит, 1972.

[31] Чандлер Б., Магнус В. Развитие комбинаторной теории групп// Очерк истории развития идей. М. Мир, 1985.

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

[32] Юрак O.A. Об одновременном приведении элементов абелевых групп к положительному виду// Вестник Омского университета №3, Омск, 2006, 18-20.

[33] Юрак O.A. Об одновременном приведении элементов абелевых групп к положительному виду II// Вестник Омского университета №4, Омск, 2006, 15-16.

[34] Юрак O.A. Положительные элементы группы Гейзенберга. Positive elements of the Heisenberg group are completely described// Вестник Омского университета №2, Омск, 2008, 16-19.

[35] Воронина O.A. О рациональных подмножествах разрешимых групп// Материалы международной конференции «Алгебра и математическая логика», Казань: КФУ, 2011, 69-70.

[36] Воронина O.A. О рациональных подмножествах разрешимых групп// Вестник Омского университета №2, Омск, 2011, 19-24.