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

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

Аверина Яна Сергеева«

МЕРЫ И НОРМАЛЬНЫЕ ФОРМЫ ДЛЯ ФУНДАМЕНТАЛЬНОЙ ГРУППЫ КОНЕЧНОГО ГРАФА ГРУПП

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

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

Омск 2006

Работа выполнена на кафедре математической логики и логического программирования Омского государственного университета им. Ф.М. Достоевского

Научный руководитель: заслуженный деятель науки РФ,

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

профессор "

Ремесленников Владимир Никанорович

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

Будкин Александр Иванович

кандидат физико-математических наук, старший научный сотрудник Есып Евгений Семенович

Ведущая организация: Новосибирский государственный архитектурно-

строительный университет

/г 4?

Защита состоится 23 марта 2006 года в ^У на заседании диссертационного совета К 212.179.01 при Омском государственном университете по адресу: 644077, Омск, пр. Мира 55а.

С диссертацией можно ознакомиться в библиотеке ОмГУ. Автореферат разослан 20 февраля 2006 г.

Ученый секретарь диссертационного совета, кандидат физ.-мат. наук, доцент

М. А. Шевелин

В1. пик,

ооосд ¿НОЗ

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

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

В 1926 году Э. Артин сформулировал понятие свободного произведения групп на языке нормальных форм. Независимо от него в 1927 году О. Шрайер также ввел это понятие, используя язык представления групп с помощью порождающих и определяющих соотношений; в том же году он дал определение группы новой конструкции - свободного произведения с объединенной подгруппой - и описал нормальные формы элементов таких групп. А.Г. Курошем в 1934 году была доказана структурная теорема о подгруппах свободного произведения групп. В 1949 году в совместной работе Г. Хигмана, Б. Неймана и X. Нейман было введено понятие еще одной свободной конструкции -НЫН-расшнрения групп.

В 1968-1969 годах возникает теория Басса-Серра, объясняющая с геометрической точки зрения многие результаты, полученные для групп, являющихся свободными конструкциями. В то же время Ж.-П. Серром было дано определение фундаментальной группы графа групп, обобщающее понятия свободного произведения с объединением и НИЫ-расширения (см. [1]).

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

нем работает плохо.

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

Вероятностные меры на свободных группах были введены в работе А. В. Боровика, А. Г. Мясникова и В. И. Ремесленникова [5]. В работе [9] эти вероятностные меры были распространены на свободные групповые конструкции и применены для исследования генерической сложности проблемы равенства слов и проблемы сопряженности. По этим направлениям проводятся исследования в диссертации.

Цель работы. Основные цели работы следующие:

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

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

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

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

Научная новизна работы. Все результаты кандидатской диссертации являются новыми и получены как лично автором, так и в тесном соавторстве с Френкель Е.В. Так, первые три главы о мультипликативных мерах на свободных конструкциях, асимптотических оценках и о нормальных формах для фундаментальных групп графов групп получены в соавторстве с Френкель Е.В. при равном вкладе обоих авторов. Остальные результаты кандидатской диссертации получены автором индивидуально.

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

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

Апробация работы. Результаты работы доложены на:

Международной алгебраической конференции: International Algebraic Conference to the ЮО"1 birthday of P.G. Kontorovich and 70th birthday of L.N.Shevrin (Екатеринбург, 2005), a также на семинарах в Омском филиале Института математики им. C.J1. Соболева СО РАН, семинарах кафедры алгебры ОмГУ и студенческих конференциях в ОмГУ.

Публикация. Результаты диссертации были опубликованы в работах [17, 18,19,20, 21]. Работы [17,18,19,20] выполнены совместно с Е.В. Френкель при равном участии обеих сторон.

Структура и объем работы. Диссертация изложена на 68 страницах, состоит из введе ния, четырех глав и библиографии. Главы разбиты на параграфы. Библиография содержит 21 наименование.

Основные результаты диссертации следующие:

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

- введено понятие строго разреженного подмножества свободной группы F и найден критерий строгой разреженности регулярною подмножества F. Этот критерий применен для доказательства строгой разреженности конкретных подмножеств F;

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

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

Содержание работы

Определим свободные групповые конструкции, исследуемые в диссертации. Для заданного графа У будем обозначать через У0 множество его вершин и через У' -множество ребер. Отображения а : У1 -* У0, ш: У' -» У0 и -: У' У1 являют собой стандартные операции взятия начала ребра, конца ребра и его обращения соответственно. В частности, для всякого ребра е имеем е = е и ё * е.

Граф групп (G,Y) состоит из связного графа Y, наборов групп {GJve У0}, {AJeeY1} и вложений {аг: Ас GaM \ eeY1} с условием А, = Ае.

Обозначим через F(G,Y) фактор-группу свободного произведения всех вершинных групп {G, ¡ V е Г0} и свободной группы с базисом {te ¡eeY1} по нормальному замыканию множества элементов {t~lat(g)tt(at(g))~l, 'Л \ее Y1, gе А,}. Определение. Фундаментальной группой nt{G,Y,T) графа групп (G.Y) относительно максимального поддерева Т графа У называется фактор-группа группы F(G, Y) по нормальному замыканию множества элементов {tt, е е Т'}.

Частным случаем фундаментальной группы является свободное произведение групп. Ооределенне. Пусть S¡- множество порождающих, Ä,- множество определяющих соотношений группы А = (Sl ¡ Я,}, S2 - множество порождающих, Л2- множество определяющих соотношений группы В = (S2 | Я2). Свободным произведением А*В групп А и В называется группа, заданная представлением А » В = (5,, S21 R¡, R¡) Л и В называют свободными множителями группы А*В. В развернутой форме эти определения приведены в работах [1,2, 3,4]. Первая и вторая главы диссертации посвящены мерам на свободных групповых конструкциях В параграфе 1.1 на свободном произведении циклических групп конечного

г

порядка С = вводится атомарная вероятностная мера ¡u:G R*. Напомним, что м

мера ц на счетном множестве X называется атомарной, если каждое подмножество Y а X измеримо.

Для свободных произведений групп известно (см., например, [2]), что любой элемент g группы G имеет однозначную запись

g'gßi-■■■•«*> О)

где рядом стоящие множители принадлежат различным Д и неединичны. Определим, следуя [13], на G целочисленную функцию длины, полагая |-|:G->Z, \1\=0, а для всякого неединичного а из А, М=/. Если элемент g записан в виде (1), то

/=i

На G следующим образом вводится атомарная вероятностная мера fx. Пусть d(n) -произвольное дискретное вероятностное распределение d • N R*, d(0)=0, тогда для

любого элемента g длины п из G p(g) = , где | | - число элементов длины л в G

\S. I

Для построения меры используем геометрическое распределение d(n) = pq"~1, где neN,0<p<l,q = l-p.

В параграфе 1.1 получена формула для вычисления меры подгрупп группы О следую-1

щеговида Н = Ял, 1 <í<г где Ни~подгруппа Л, .

■-i

В параграфе 1.2 проводится исследование введенной меры на предмет ее мультипликативности. Этот термин был введен в работе [5]. Мера fi называется мультипликативной, если для любых элементов и, v е G таких, что | uv |=| и | +1 v |, выполнено равенство H(uv) = ft(ü)fi{v). В работе введено следующее

Определение 1.2. Назовем меру квазимультипликативной, если существует неотрицательное вещественное число с, такое что для любых элементов u,veG таких, что | uv 1=1 и | +1V |, выполнено равенство [¿(uv) - с/л(и)ц(у). Доказано утверждение:

г

Предложение 1.1. Пусть G = , где А- циклическая порядка а + 1, 1 ¿ /'</■; а и г

i-i

полагаем конечными. Тогда мера ц на группе G квазимультипликативна.

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

В следующей главе проводится исследование подмножеств специального вида конечно порожденной свободной группы F относительно введенной на ней меры. Мера вводится так же, как и в предыдущей главе с использованием геометрического распределения и следующей функции длины на F. А именно, пусть F - свободная группа ранга z над алфавитом X = {x¡ ,...,xj. Элементами группы F являются редуцированные слова (т.е такие слова, которые не содержат полслов вида хх' или х"'х). Длиной элемента /из F является число букв в его записи; будем обозначать длину слова через |/|. В работе [5] A.B. Боровиком, А.Г. Мясниковым и В.Н. Ремесленниковым было введено понятие разреженного подмножества F. В качестве усиления этого понятия в параграфе 2.2 данной диссертации определено строго разреженное подмножество F.

Определение 2.3. Будем называть множество Я строго разреженным, если существуют такие действительные неотрицательные числа ц и С, где 0<д<! и натуральное число

что для всякого к>Ы верно следующее неравенство ^ ^ ^ < •

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

Пусть X - множество букв. Х-диграфом называется граф, ребра которого размечены элементами множества Л", детальное определение см., например, в [10]. Приведем определение Х-полноты, связанное с размеченными графами (^-диграфами) Х-диграф Г называется ^-полным, если для каждой его вершины V и каждой метки х е X существует одно и только одно ребро с меткой х, с началом в V и существует одно и только < одно ребро с меткой * и с концом в V (см. [10]).

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

Теорема 2.1. Пусть Я - регулярное подмножество Р, Г- конечный граф для И Если Г связный и не является Х-полным, то Я строго разреженное в F множество.

В качестве следствия из Теоремы 2.1 получен следующий результат:

Теорема 2.2. Пусть Я - конечнопорожденная подгруппа ¥ бесконечного индекса, тогда Я является строго разреженным подмножеством

В параграфе 2.2 доказано, что строгая разреженность сохраняется при некоторых операциях над множествами. Кроме того, в параграфе 2.4 доказана строгая разреженность класса сопряженности любого элемента 7% объединения строго разреженного множества правых классов смежности по подгруппе конечного индекса, а также самих классов смежности и некоторых других подмножеств (Утверждения 2.7-2.10).

Утверждение 2.7. Пусть А - конечно порожденная подгруппа бесконечного индекса, а/ - произвольный неединичный элемент свободной группы Р Обозначим через /А и А}-соответственно левый и правый смежные классы по А, через Аг = {/"'а/1 а е А] - сопряженную с ней подгруппу. Тогда множества /А, А/ и А' являются строго разреженными в У7

Для формулировки следующего результата определим понятие множества специальных представителей для подгруппы Я в группе /<\ В каждом правом классе смежности по Н мы выбираем представитель причем из единичного класса Я выбираем представитель единицу. Более того, представители выбираем так, что каждый из них имеет минимальную длину в своем классе и вся система представителей является шрайеровой (такой выбор возможен, см., например, [8]).

Утверждение 2.8. Пусть Я- подгруппа бесконечного индекса свободной группы Р, 50 - строго разреженное подмножество множества 5 специальных представителей для подгруппы Я. Тогда множество М - ^Яя также является строго разреженным в Р.

Утверждение 2.9. Пусть Н - конечно порожденная подгруппа бесконечного индекса

свободной группы Р. Тогда множество Н' = является строго разреженным в К

/«я

Утверждение 2.10. Пусть А - неединичный элемент группы К Тогда множество Иг = {/"'А/1 / е Р} - класс сопряженных с А элементов, является строго разреженным в Р.

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

Теорема 2.13. Пусть А и В - конечнопорожденные подгруппы 1руппы Р, пусть, кроме того, обе они бесконечного индекса. Тогда для произвольного элемента/из Р двойной класс смежности А/В = {а/Ь | а е А,Ь е В] является разреженным в Р

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

Пусть ж, (О, У, Т) - фундаментальная группа конечного графа групп (У, С) Введем систему представителей. Если С, и б, - вершинные группы такие, что существует ребро е, еК'\Г', причем а(е1) = и, й)(е:) = V, то будем обозначать через Ре- множестве представителей правых смежных классов группы Ои по подгруппе ас (А1), Р-е - множество представителей правых смежных классов группы С?„ по подгруппе а- (А,). Для ребра е, е Т' будем обозначать через Р, множество представителей правых смежных

классов группы G„ по подгруппе а^ (Л;), где а(е^) = и , Р_т - множество представителей правых смежных классов группы G, по подгруппе а-^ (Aj), где а>(ej) = v Множество всех представителей обозначим Р.

В параграфах 3.2-3.4 определены нормальные формы и процедуры для приведения к ним для фундаментальных групп конкретных графов.

Для каждого из вложений {а^ | еч е Т'} в следующем параграфе было введено понятие (/-нормальной формы элемента фундаментальной группы ^i{G,Y,T) конечного графа групп.

Определение 3.9. ^-нормальной формой элемента g группы я-|(6',У,7") называется запись g = h-t*px ■■■■■t''pk, гдеэлемент Леа, (Aq) (если Г1 =0,то Л е G,), pt € Р и еt б {-1,0,1}, j = 1,. -., к, причем если

• е = 0, то Pj_, и р — представители различных вершинных групп;

• Sj =-1,то pj еРе/;

• £j то р j € Р-^;

Построена процедура приведения к ^-нормальной форме записи элемента фундаментальной группы конечного графа групп (Процедура I).

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

Найдено достаточное условие для эффективности Процедуры I. Для понимания его формулировки введем некоторые определения и обозначения

Определение 3.10 (прегрупповой длины записи элемента). Произвольный элемент g группы nx(G,Y,T) имеет запись

S-fcCft ■•■••£«,. (2)

где и>0, gjS [JGV ,j = 0,...,и, и £у е {-1,0,1}, J = l,...,n, причем, если sJ =0, то

gj-i И gj ~ непустые слова и лежат в различных вершинных группах. На записях элементов группы ^(G.^.r) определим целочисленную функцию прегрупповой длины L следующим образом: для всякого неединичного gy б |JGV положим L{g1) = 1, считаем

L(l) = 0, также положим L (t'' ) = 1 при е1 е {-1,1}. Если элемент g имеет зап п — j f _ V4 jiп л . V* / *s>\

Ши,ю - ¿s^gj'-rL^'l, >■

J'4 1-1

Зафиксируем группу Н=<Х | Я> Через С^РФ обозначается следующая проблема-пусть Ф - множество конечно порожденных подгрупп Я; для данного £> е Ф требуется найти рекурсивное множество Р представителей Я по О и алгоритм Аи, который для заданного ю е /Г(ЛГ) находит представление у/ = </ • р, где с? е Д р е Р.

Теорема 3.5. Пусть тг, (С, У,Г) - фундаментальная группа конечного графа групп У. Тоща если в каждой вершинной группе V е У" разрешима проблема СЛ5? для всех ее реберных подгрупп, то процедура I эффективно находит нормальную форму для произвольного элемента g е 7Г,(<5, У,Т).

Произведена оценка сложности процедуры I в случае, когда вершинные и реберные группы свободны и конечно порождены (Теорема 3.6).

Теорема 3.6. Пусть ж, (О, У, Т) - фундаментальная группа конечного графа групп У, причем все вершинные и реберные группы конечно порождены и свободны. Тогда длина слова в нормальной форме, полученного на выходе процедуры I, не более чем экспоненциальна по отношению к прегрупповой длине входного слова.

В четвертой главе введены понятия редуцированной и циклически редуцированной форм элементов фундаментальной группы конечного графа групп. Данные понятия являются обобщением соответствующих форм для Я7УЛГ-расширений и свободных произведений с объединением, тщательно изученных в прошлом веке. В диссертации исследованы некоторые свойства этих форм.

Одним из основных результатов четвертой главы является критерий сопряженности для элементов фундаментальной группы конечного графа групп. В параграфе 4.1 введем определения необходимые для формулировки критерия. Определение 4.3. Будем говорить, что элемент geGv вкладывается в вершинную группу (?„, где и * V, если существуют последовательность отображений аг,...,ае^, где еТ', и последовательность элементов е Ас ,.,.,/4 е А,^ такие, что

« = «е/1(/;) = аг/1 (/) = ••• = «,,(/*) = (Л),причем, «(<;„) = V и ю(е,*) = и.

Определение 4.4, Будем говорить, что тройка неединичных элементов а, Ь, с расщепляется, если выполнено одно из условий:

• элементы а е 0„, бе б,, се С», причем ы*у, V # и> и найдутся такие неединичные элементы А, и Ь2, что Ъ-Ьу-Ьг и вкладывается в <3„, а вкладывается в О,,;

• элементы ябб,, себ», Ь = 1е и

о элемент я вкладывается в о-ДД,), причем элемент а,, удовлетворяющий

равенству <Л€ = /,а,, вкладывается в О. или о элемент с вкладывается в аг(Ае), причем элемент с,, удовлетворяющий равенству = /,.£•, вкладывается в 0„;

• элементы а е с е Ь = 1е~> и

о элемент о вкладывается в аг(Д), причем элемент в, , удовлетворяющий

равенству а/,"' = г/'а,, вкладывается в (?„ или о элемент с вкладывается в ае(Ае), причем элемент с,, удовлетворяющий равенству с,/,"' = 1~'с, вкладывается в <5„. Определение 4.5. Запись £ = g(lt''g¡ где е {-1,0,1}, у" = Iпричем, если

в = 0, то и непустые слова и лежат в различных вершинных группах, называется редуцированной формой элемента # при выполнешш следующих условий:

1. если в) = 0, то произведение не вкладывается в одну вершинную группу;

2. никакая тройка подряд идущих множителей не расщепляется;

3. если = -1 и е^ = 1, и /, = ^ , то gJ не вкладывается в ае (Ас, );

4. если е;=1 и е^, = -1, и = , то не вкладывается в а- (А );

5. во всех фрагментах вида записи £ элемент не вкладывается в подгруппу

a. а^ (Д, ), если е/ = 1;

b. ),если =-1.

Будем считать, чго элемент где е, е {-1,0,1}, € Ои, и е У", образует слог, если либо с, =0, либо г, * О, =1, либо вкладывается в а, (А1) при /г, =-1, ив

а, (Л) при = 1.

Определение 4.6. Слоговой длиной элемента g назовем число слогов в его редуцированной записи.

Циклической перестановкой записи элемента g = g^■■■. будем называть произвольную циклическую перестановку слогов этой записи.

Определение 4.7. Запись g = g0t''g¡ называется циклически редуцированной

формой элемента g, если любая ее циклическая перестановка редуцирована. Были доказаны следующие теоремы.

Теорема 4.4. Пусть g = gx■...■t'•g„ и А = /ц К - редуцированные слова, представляющие один элемент группы тг,(<7,У,Т). Тогда ^¡(И) и для всех ] = .,п элементы gl и вкладываются в одну и ту же вершинную группу б, и = .

Теорема 4.5. Пусть g = g0t'lgl ■...■ - редуцированное слово, представляющее элемент группы ях{С,У,Т), а g"лc^r'T) = |/б К,7*)} - класс сопряженных с # элементов. Тогда элемент с наименьшей слоговой длиной в классе '¿"-"'" Т) циклически редуцирован.

Для решения проблемы сопряженности нужно описать ситуацию, когда ¡(Ь§) = т.е. слоговая длина элемента gEЯ^(G,Y,T) сохраняется при умножении на элемент Ь € и б» >с этой целью введем обозначения и определение.

Пусть & е и<?г - первый неединичный множитель указанного вида в редуцированной

форме £=• & 0<к<п элемента g. Введем последовательносп

элементов следующим образом:

Ь0=Ь,

•

К'-

Определение 4.12. Будем говорить, что Ь сливается с g слева, если в вышеприведенных обозначениях выполнены условия:

1. вкладывается в а-^ (Аг^), если - -1, и в ас (А, ), если = 1, при 0£/<(*-1);

2. bk вкладывается в вершинную группу для gk. Аналогичным образом вводится понятие слияния справа.

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

Теорема 4.6. Пусть g = g^'lg, ■■■■■t'"g„ я h = ty"'hi-...-ter-hm - сопряженные циклически редуцированные элементы группы ж, (G, У, Т). Тогда s(g)=s(h) и h можно получить из g, беря некоторую его циклическую перестановку g' и сопрягая подходящим элементом Ь, сливающимся с g' слева и справа.

Важным следствием теорем 4.5 и 4.6 является следующее утверждение:

Следствие 4.2. Пусть g - элемент группы лг, (G, Y, Т). Тогда слоговая длина любой циклически редуцированной записи из класса g"'i,J-r-,) является инвариантом для всех циклически редуцированных элементов этого класса. Данное число наименьшее среди слоговых длин всех элементов из g*(0J!-').

Список литературы

[1] Serre J.-P. Trees // Berlin-Heidelberg-New York: Springer-Verlag, 1980

[2] В.Магнус, A.Kappac, Д.Солитэр Комбинаторная теория групп I IM : Наука, 1974.

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

[4] Богопольский О.В. Введение в теорию групп // М.: Современная математика, 2002.

[5] A.V. Borovik, A. G. Myasnikov, V. N. Remeslennikov Multiplicative measures on free groups И International Jomal of Algebra and Computations 13 (2003), P. 705-731.

[6] I. Kapovich, A. Myasnikov, P. Schupp, V. Shpilrain Generic-Case Complexity Decision Problems in Group Theory and Random Walks // Jornal of Algebra 264 (2003), no 2, P. 665694.

[7] David B.A. Epstein and others, Word Processing in Groups II Jones and Bartlett Publishers, 1992.

[8] Каргаполов М.И., Мерзляков Ю.И. Основы теории групп И М.: Наука, 1977.

[9] A.V. Borovik, A. G. Myasnikov, V. N. Remeslennikov The Conjugacy Problem in Amalgamated Products I: Regular Elements and Black Holes II to appear- International Jornal of Algebra and Computations.

[10] Kapovich I., Myasnikov A. Stallings Foldings and Subgroups of Free Groups, Jornal of Algebra 248 (2002), no 2, P. 608 - 668.

[11] Gregory Quenell Combinatorics on free product graphs Geometry of the spectrum II (Seattle, WA, 1993), Amer. Math. Soc., Providence, RI, 1994, pp. 257-281.

[12] Laurent Bartholdi Counting Paths in Graphs II arxiv:math co/0012161 vl 18 Dec 2000.

[13] E.C. Есып, В.Н.Ремесленников Уравнения от одной переменной над свободными произведениями циклических групп II Препринт ном. 31. Омск: ОмГАУ, 2000.

[14] Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи IIМ.: Мир, 1982.

[15] Я .С. Аверина, Е.В. Френкель Полиномиальный алгоритм приведения олементов некоторых групп Баумслага-Солитера к нормальной форме II Вестник Омского университета, 2004, выпуск 2(32), с. 16-18.

[16] Я.С Аверина, Е.В. Френкель Разреженность классов смежности по подгруппам свободной группы II Вестник Омского университета, 2004, выпуск 4 (34), с. 25 - 27

Работы автора по теме диссертации

[17] Я С Аверина, RB. Френкель Вычисление меры подгрупп свободного произведения циклических групп!! Вестник Омского университета, 2002, выпуск 3(25), с. 13-15

[18] Я.С. Аверина, Е.В. Френкель Разреженность классов смежности по подгруппам свободной группы!! Препринт№00-01, Омск: Омск. Госуниверситет, 2004 - 14с.

[19] Я.С. Аверина, Е.В. Френкель Алгоритм приведения к канонической нормальной

форме элементов фундаментальных групп графов групп!/ Препринт№00-02, Омск: "

Изд-во ОмГУ, 2005 - 20с.

[20] Я.С. Аверина, Е.В. Френкель О строго разреженных подмножествах свободной j группы/У Сибирские электронные математические известия, ISSN 1813-3304, ТОМ 2

(2005), с. 1-13, http://semr.math.nsc.nl

[21] Я.С. Аверина Критерий сопряженности для элементов фундаментальной группы конечного графа групп/'! Препринт№00-03, Омск: Отдел оперативной полиграфии фирмы «Банковский сервис», 2006 - 16 с.

Аверина Яна Сергеевна

МЕРЫ И НОРМАЛЬНЫЕ ФОРМЫ ДЛЯ ФУНДАМЕНТАЛЬНОЙ ГРУППЫ КОНЕЧНОГО ГРАФА ГРУПП

Специальность 01.01.06 - математическая логика, алгебра и теория чисел

АВТОРЕФЕРАТ

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

Подписано в печать 00.10.05. Форм» бумаги 60x841/16 Печ. л. 1,25. Уч.-изд. л. 1Д5. Тираж 50 экз. Заказ № 000.

Отдел оперативной полиграфии фирмы "Банковский сервис", 644042, г Омск, пр Маркса, 18/1

i

i

¿POCA

4403

Введение

Глава 1. Вычисление меры подгрупп свободного произведения циклических групп.

1.1. Вычисление мер подгрупп.

1.2. Мультипликативность меры

Глава 2. Разреженные и строго разреженные подмножества свободной группы.

2.1. Регулярные подмножества свободной группы.

2.2. Определение и простейшие свойства строго разреженных множеств.

2.3. Критерий строгой разреженности регулярных подмножеств свободной группы.

2.4. Конструкции над строго разреженными множествами.

2.5. Разреженность двойного класса смежности по подгруппам бесконечного индекса.

Глава 3. Алгоритмы приведения элементов фундаментальных групп конечных графов групп к нормальной форме.

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

3.2. Случай линейного графа.;.

3.3. «Чупа-чупс».

3.4. Треугольник.

3.5. Произвольный конечный граф.;.

3.6. Единственность ^-нормальной формы элементов фундаментальной группы конечного графа групп.

3.6.1. Граф У-дерево

3.6.2. Граф Уне является деревом

3.7. Оценка процедуры I .'.

Глава 4. Критерий сопряженности для элементов фундаментальной группы конечного графа групп.

4.1. Обозначения и основные определения.

4.2. Ассоциированный граф является деревом.

4.3. Произвольный конечный граф групп.

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

В 192G году Э. Артин сформулировал понятие свободного произведения групп на языке нормальных форм. Независимо от него в 1927 году О. Шрайср также ввел это понятие, используя язык представления групп с помощью порождающих и определяющих соотношений; в том же году он дал определение группы повой конструкции -свободного произведения с объединенной подгруппой - и описал нормальные формы элементов таких групп. А.Г. Курошем в 1934 год}' была доказана структурная теорема о подгруппах свободного произведения групп. В 1949 году в совместной работе Г. Хиг-мапа, Б. Неймана и X. Неймаи было введено понятие еще одной свободной конструкции — HNN-расширепия групп.

В 19С8-1969 годах возникает теория Басса-Серра, объясняющая с геометрической точки зрения многие результаты, полученные для групп, являющихся свободными конструкциями. В то же время Ж.-П. Серром было дано определение фундаментальной группы графа групп, обобщающее понятия свободного произведения с объединением и HNN-расширения (см. [1]).

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

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

Вероятностные меры на свободных группах были введены в работе А. В. Боровика, А. Г. Мяснпкова и В. Н. Ремссленникова [5]. В работе [9] эти вероятностные меры были распространены па свободные групповые конструкции и применены для исследования генерической сложности проблемы равенства слов и проблемы сопряженности.

По этим направлениям проводятся исследования в диссертации.

1. Serre J.-P. Trees 1. Berlin-Heidelberg-New York: Springer-Verlag, 1980.

2. В.Магнус, A.Kappac, Д.Солитэр Комбинаторная теория групп // М.: Наука, 1974.

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

4. Богопольский О.В. Введение в теорию групп И М.: Современная математика, 2002.

5. A.V. Borovik, A. G. Myasnikov, V. N. Remeslennikov Multiplicative measures on free groups II International Jornal of Algebra and Computations 13 (2003), P. 705-731.

6. I. Kapovich, A. Myasnikov, P. Schupp, V. Shpilrain Generic-Case Complexity Decision Problems in Group Theory and Random Walks // Jornal of Algebra 264 (2003), no 2, P. 665-694.

7. David B.A. Epstein and others, Word Processing in Groups II Jones and Bartlett Publishers, 1992.

8. Каргаполов М.И., Мерзляков IO.И. Основы теории групп IIМ.: Наука, 1977.

9. A.V. Borovik, A. G. Myasnikov, V. N. Remeslennikov The Conjugacy Problem in Amalgamated Products I: Regular Elements and Black Holes II to appear: International Jornal of Algebra and Computations.

10. Kapovich I., Myasnikov A. Stallings Foldings and Subgroups of Free Groups, Jornal of Algebra 248 (2002), no 2, P. 608 668.

11. Gregory Quenell Combinatorics on free product graphs Geometry of the spectrum II (Seattle, WA, 1993), Amer. Math. Soc., Providence, RI, 1994, pp. 257-281.

12. Laurent Bartholdi Counting Paths in Graphs II arxiv:math.co/0012161 vl 18 Dec 2000.

13. E.C. Есып, В.H.Ремесленников Уравнения от одной переменной над свободными произведениями циклических групп II Препринт ном. 31. Омск: ОмГАУ, 2000.

14. Гэри М., Джонсон Д. Вычислительные машины и труднореишемые задачи II М.: Мир, 1982.

15. Я.С. Аверина, Е.В. Френкель Полиномиальный алгоритм приведения элементов некоторых групп Баумслага-Солитера к нормальной форме II Вестник Омского университета, 2004, выпуск 2(32), с. 16- 18.

16. Я.С. Аверина, Е.В. Френкель Разреэюенность классов смеэ/сности по подгруппам свободной группы II Вестник Омского университета, 2004, выпуск 4 (34), с. 25 27.

17. Я.С. Аверина, Е.В. Френкель Вычисление меры подгрупп свободного произведения циклических групп!/ Вестник Омского университета, 2002, выпуск 3(25), с. 13 15.

18. Я.С. Аверина, Е.В. Френкель Разреженность классов смеэ/сности по подгруппам свободной группы!/ Препринт№00-01, Омск: Омск. Госуниверситет, 2004 14с.

19. Я.С. Аверина, Е.В. Френкель Алгоритм приведения к канонической нормальной форме элементов фундаментальных групп графов групп/! Преприпт№00-02, Омск: Изд-во ОмГУ, 2005-20с.

20. Я.С. Аверина, Е.В. Френкель О строго разреэюенных подмножествах свободной группы!7 Сибирские электронные математические известия, ISSN 1813-3304, ТОМ 2 (2005), с.1-13, http://semr.matli.nsc.ru.

21. Я.С. Аверина Критерий сопряженности для элементов фундаментальной группы конечного графа групп!! Препринт№00-03, Омск: Отдел оперативной полиграфии фирмы «Банковский сервис», 2006 1 б с.