Содержание к диссертации
Введение
Плана I. Вычисление меры подгрупп свободного произведения циклических групп 6
1.1. Вычисление мер подгрупп , 6
1.2. Мультипликативность меры , 30
Глава 2. Разреженные и строго разреженные подмножества свободной группы 12
2.1. Регулярные подмножества свободной группы , 12
2.2. Определение и простейшие свойства строго разреженных множеств 15
2.3. Критерий строгой разреженности регулярных подмножеств свободной группы 18
2.4. Конструкции над строго разреженными множествами 21
2.5. Разреженность двойного класса смежности по подгруппам бесконечного индекса ,, 25
Глава 3. Алгоритмы приведения элементов фундаментальных групп конечных графов групп к нормальной форме 32
3.1. Основные определения 32
3.2. Случай линейного графа : 33
3.3. «Чупа-чупс»., 36
3.4. Треугольник 38
3.5. Произвольный конечный граф ; , 41
3.6. Единственность -нормальной формы элементов фундаментальной группы конечного графа групп , 45
3.6.1. Граф У-дерево 45
3.6.2. Граф Уне является деревом 47
3.7. Оценка процедуры I ; 48
Глава 4. Критерий сопряженности для элементов фундаментальной группы конечного графа групп 52
4.1. Обозначения и основные определения 52
4.2. Ассоциированный граф является деревом 55
4.3. Произвольный конечный граф групп , 59
Список литературы
- Мультипликативность меры
- Критерий строгой разреженности регулярных подмножеств свободной группы
- Случай линейного графа
- Ассоциированный граф является деревом
Введение к работе
Среди многих проблем, которыми занимается комбинаторная теория групп, важнейшими являются алгоритмические проблемы и изучение свойств свободных конструкций над группами. В последние годы бурно развивается и статистическая теория групп, предметом которой является определение различных мер па группах, вычисление роста групп, порождающих функции, функций Дэна и т.д. Исследования в данной диссертации проводятся в рамках этих двух направлений теории групп.
В 192G году Э, Артнн сформулировал понятие свободного произведения групп па языке нормальных форм. Независимо от него в 1927 году О. Шрайср также ввел это понятие, используй язык представления групп с помощью порождающих и определяющих соотношении; и том же году он дал определение группы поной конструкции -свободного произведения с объединенной подгруппой - п описал нормальные формы элементов таких групп. А.Г. Курошем и 1934 году была доказана структурная теорема о подгруппах свободного произведения групп. В 1949 году в совместной работе Г. Хиг-мана, Б. Неймана п X, Нейман было введено понятие еще одной свободной конструкции — HNN-расширешія групп.
В 19С8-19С9 годах возникает теория Басса-Серра, объясняющая с геометрической точки зрения многие результаты, полученные для групп, являющихся свободными конструкциями. В то же время Ж.-П. Серром было дано определение фундаментальной группы графа групп, обобщающее понятия свободного произведения с объединением и HNN-расширения (см, [1]),
В настоящее время свободные групповые конструкции широко используются в комбинаторной теории групп, в частности, при построении примеров, связанных со сложностью алгоритмических проблем (например, для доказательства неразрешимости классических алгоритмических проблем). При исследовании упомянутых проблем, как разрешимых, так п неразрешимых, плодотворной является идея стратификации входных данных по сложности рассматриваемых алгоритмических проблем. На этом пути определяется регулярная часть алгоритма, то есть множеств входных данных, на которых алгоритм работает быстро (например, в линейное или квадратичное время), а также дополнение к регулярной части - черная дыра алгоритма - множество элементов, про которые мы либо не знаем, как на нем работает алгоритм, либо знаем, что алгоритм па нем работает плохо.
Как правило, при решении алгоритмических проблем вычисления проводятся либо со словами свободной группы, либо со стандартными нормальными формами для
фундаментальных групп графов групп. Поэтому важным для изучения свободных конструкции над группами является решение таких задач, как нахождение удобных нормальных форм и определение хороших вероятностных мер для измерения регулярной части алгоритма, его черной дыры и других подмножеств.
Вероятностные меры па свободных группах были введены в работе А. В. Бороішка, А. Г. Мисгппшва и В. Н. Ремесленников а [5], В работе [9] эти вероятностные меры были распространены на свободные групповые конструкции и применены для исследования геперпчсеїшіі сложности проблемы равенства слов и проблемы сопряженности.
По этим направлениям проводятся исследования и диссертации.
Мультипликативность меры
При решении ряда алгоритмических проблем и качественной оценке алгоритмов возникает необходимость однозначного представления элементов группы в виде слов — так называемой канонической нормальной формы. Цель данной части диссертации — определение канонических нормальных форм для фундаментальных групп графов групп специального вндн" также указание алгоритмов приведення записи произвольного элемента к этой форме. Основным результатом является построение алгоритма приведения к канонической нормальной форме записи элемента фундаментальной группы произвольного конечного графа групп и оценка его сложности в случае, когда вершинные и реберные группы свободны и конечно порождены. Вначале; мы рассмотрим конкретные графы групп, а затем перейдем к общей ситуации.
В этой части работы напомним некоторые определения, которые понадобятся в дальнейшем (подробнее см., например, [1]). Приведем определение графа групп и его фундаментальной группы. Для заданного графа У будем обозначать через У0 множество его вершки и через У1 — множество ребер. Отображения а : Ух - Уа,ш : У] —» У0, п 7 : У 1 -» У1 являют собой стандартные операции взятия начала ребра, конца ребра и его обращения соответственно. В частности, для всякого ребра с имеем с = а и ё / с.
Определение 3.1, Граф групп (G, Y) состоит из связиого графа Y, наборов групп {Gv \v Є Y0}, {Aa с Є У1} и вложений {ає : Ає - Gu(e) j є Є Y1} с условием А?_ = ,. Обозначим через F(G, К) (})актор-группу свободного произведения всех вершинных групп Gv,v Є У0 и свободной группы с базисом {te\e Є У1} по нормальному замыканию множества элементов
Напомним, что максимальное (по включению) поддерево Т графа Y удовлетворяет равенству Т = К0. Существует несколько определении фундаментальной группы графа групп, мы же будем пользоваться следующим:
Определение 3.2. Фундаментальной группой it\(G,Y,T) графа групп {G,Y) относительно максимального поддерева Т графа Y называется фактор-группа группы F(G,Y) по нормальному замыканию мпооїсества элементов {te,e Є Т1}.
С точностью до изоморфизма группа TT\_(G,Y,T) ПО зависит от выбранного максимального поддерева Т(см., например, [1]). С учетом сделанной оговорки будем писать тгі(С,У) вместо 7Г,(а,Г,Г).
Далее для заданного графа групп (G, У) будем говорить, что две группы, GV2, являются соседними, если вершины Vi и V2 инцидентны одному ребру в выбранном максимальном дереве Т. Согласно определению 3.2., фундаментальная группа графа групп {G,Y) имеет представление: Определение 3.3. в[—нормальной формой элемента,д группы с представлением (3.1) называется запись
Замечание. Аналогичным образом вводится понятие нормальной формы для оставшихся трех вложении, причем разновидность нормальной формы однозначно определяется выбранным вложением реберной подгруппы в вершинную группу. Отметим, что элемент h в записі! элемента g принадлежит той подгруппе, которая определяет тип нормальной формы, В дальнейшем мы не будем утомлять читателя перечислением этих нормальных форм и фактов, касающихся каждой пз них в отдельности, подразумевая, однако, что все они равноправны. Теперь мы можем сформулировать следующую теорему.
Теорема 3.1, Произвольный элемент g группы 7i"i(G, У) с представлением (3.1) имеет единственную норліальпую форму.
Доказательство существовании формы (3.2) следует из процедуры приведения элемента к нормальной форме для линейного графа, которая будет описана ниже. Единственность будет доказана в параграфе 3.6 для произвольного конечного графа групп. Для описания процедуры приведения элемента к нормальной форме нам понадобится следующее
Зафиксируем представителей правых классов смежности: пусть Ре, — множество представителен правых смежных классов группы G\ по подгруппе а,., (Лі) , P l — множество представителей правых смежных классов группы G2 по подгруппе ctgj (Ді), / — множество представителей правых смежных классов группы G2 по подгруппе а Лг), Р(:.г — множество представителей правых смежных классов группы G2 по подгруппе ае2(Л2); множество всех представителей, как и прежде, обозначим Р.
Определим множество нормальных форм для каждого вложения реберной подгруппы Лі и вершинные группы d и G2.
Определенно 3.5. в і — нормальной формой элемента g группы с представлением (3.4) называется запись
Замечание. Аналогично определяется ej —нормальная форма элементов группы с: представлением (3.4). В дальнейшем, как и в случае линейного графа, мы будем работать с е\ — нормальной формой элементов. Поэтому будем опускать иногда название ребра и писать просто «нормальная ([юрма» там, где не может возникнуть двусмысленности. Сформулируем теорему, характеризующую эту нормальную форму. Теорема 3.2. Произвольный элемент д группы с представлением (3.4) имеет единственную е\ —нормальную форму.
Существование такой формы мы покажем при помощи нижеприведенной процедуры, а единственность следует из теоремы для произвольного конечного графа групп, которая будет доказана позднее.
Критерий строгой разреженности регулярных подмножеств свободной группы
Сложность процедуры I. Под сложностью процедуры будем понимать кол и честі 10 элементарных операций, проделываемых па данном входе д. За операцию примем представление элемента вершинной группы в виде произведении элемента реберной подгруппы и представителя соответствующего правого класса смежности процедуры I. Иными словами, элементарная операция процедуры — это решение CRSP в вершинной группе для се реберной подгруппы.
Оценим количество элементарных операций процедуры I. Па вход этой процедуры подается слово д вида (3.16), запись которого имеет прегрунповую длину п. Напомним, что чеі)ел d мы обозначили диаметр максимального поддерева Т графа У. Мы утверждаем, что алгоритм проделывает на данном входе не более чем (2-п+1)-г/операций. В самом деле, для обработки каждого слога производится не более 2d операций: в случае, когда ЄІ Ф 0, для обработки слога нам может потребоваться два шага, на каждом из которых мы делаем не более d операций. Еще d операций может понадобится на первом шаге. В частности, это доказывает справедливость теоремы 3.5.
Однако при решении алгоритмических проблем принципиально важно оценить не только число операций, по и длину выхода алгоритма (см., например, [14]). Ниже будет показано, что за однпу операцию длина слова1 может экспоненциально возрасти.
На каждом шаге процедуры нам приходится решать CRSP в вершинных группах для реберных подгрупп, н потому рост длины канонической формы существенным образом зависит от роста длины в процессе работы алгоритма для решения CRSP. Из [10] известно, что CRSP разрешима в свободных конечно порожденных группах. Поэтому
Здесь под «длиной слова» / понимается длина п обычном смысле, то есть количество символов и его записи. Будем обозначать ее через /. в дальнейшем мы ограничимся рассмотрением лишь тех групп TT\_(G, У), у которых все вершинные и реберные группы конечно порождены п свободны. Кроме того, будем полагать, что для различных вершинных групп Gi F(X) и Gj F{Y) алфавиты А и У не пересекаются. Рассмотрим некоторую вершинную группу Gi и одну из ее реберных подгрупп Ау Пусть щ — представитель из класса Aj(j, полученный в результате обработки gi алгоритмом AJP для решения CRSP. В 10j были сформулированы следующие результаты, характеризующие решение CRSP. (і) Для данного снова ді Є G{ представитель р имеет минимальную длину в классе Ajg. (и) Существует константа М; такая, что для всякого Є Gi, если у, = а р, то jn Iffil + МІ. (in) Время, затрачиваемое на работу алгоритма AjP па входе gi, ограничено сверху величиной Lii\(ji\ для некоторой константы Li.
Кроме CRSP, и процедуре I замаскирован переписывающий процесс Р, а именно: пусть Gi и Gi — вершинные группы, нпцедентные одному ребру (в пашем случае Gj F(X), d F(y), где А и У — конечные алфавиты), Aj — рсбе;)пая подгруппа, соответствующая одному из ребер е, соединяющих вершины для Gj и G(. В силу наличия изоморфных вложений Aj в Gi и Gi, а также соотношении вида (ye(Aj)a ](Aj) или t lo.(.(Aj)ta 1(Aj)(\i зависимости оттого, входит или пет ребро а в максимальное поддерево Г) произвольное слово w из Aj может быть записано в порождающих Ui,...,Uk = Aj, где щ, і — \,к слова із ал ([завите А , либо в порождающих vi,..., vk = Aj, где Vi — слова от У. Если w записано в порождающих viy г — 1,к, то есть w = w{v\,..., Vk), его можно переписать как w — w{u\,.,., itk), выражая Vi через Uj. И наоборот, если w = w(ui,... ,іік), то можно получить его записі) и порождающих Vi. Для вершинных групп Gi и G{ и их реберной подгруппы Aj введем константу Xnj =тах{Ащ(и,и),Лщ(и,и)}, где
Рассмотрим иеедннпчпып элемент д = д\дг, 7i Gi, gi Є Gj. Для приведення д к канонической нормальной форме нужно воспользоваться ШАГОМ 2 процедуры I. Сначала представляем r/2 LJ виде wqpe, где w-2 = 2( 1,...,) Є Aj, pc — представитель минимальной длимы из класса Aj j2. Используя факты (г), (гг) и неравенства (3.19), получим iw2(ui,...,«jt) \щ\д2\ + MGt,Aj І5І + Л/С),лл- п \Ре\ Ы \о\- По всем вершинным группам и их реберным подгруппам выберем максимальные константы MQUA- И Xitj, обозначим их М п Л соответственно.
Итак, в последней теореме мы оценили рост длины нормальной формы в процессе обработки слова процедурой 1 для случая, когда все вершинные и реберные группы конечно порождены и свободны. Длина формы является экспоненциальной по отношению к прегрупповой длине записи входа. Эта оценка является достижимой (подробнее; см. [15]).
Случай линейного графа
Пусть теперь п 2, m 2. Поскольку оба элемента редуцированы, то, по лемме 4.1., можно утверждать, что тройки дп, /і 1, /( -і и 9п-іі9т пт ие расщепляются; однако, запись gh l редуцированной не явлется, и поэтому сокращение происходит только по одной причине: элементы дп и h 1 вкладываются в одну вершинную группу. Следовательно, элемент h } представИм в виде /і"1 д„ 1 сь где Сі лежит в реберной подгруппе, вкладывающейся в вершинную группу для дп-\ или /i !_j. Для определенности будем полагать, что сх вкладывается в вершинную группу для gn i Покажем, что дальнейшие сокращения могут произойти только между В самом деле, пусть это ие так, то есть произведение дп 2 9 \ = 2 попадает в одну из реберных подгрупп. Тогда тройка /H-2J ?n-i)5n является расщепляемой при bi = дп-2с2, и 2 = С\. Но слово д является редуцированным п, значит, тройка gn-2,9n-i 9n перасщепляема.
Применяя индуктивное предположение, получаем утверждение теоремы. Выше мы уже охарактеризовали редуцированную форму элемента; опишем теперь свойство циклически редуцированной формы слова. Теорема 4.2. Пусть редуцированное слово, представляющее элемент группы, заданной представлением (4-4), о g i(G v) = {f xgf\f Є Яі(С?, У)} — класс элементов, сопряоїсепних с g. Тогда, элемент с пагімспьшей слоновой длиной в классе gX {c ,Y) циклически редуцирован.
Доказательство. Пусть h — элемент наименьшей слоговой длины в классе дп а . Предположим, что h = hi - ... hm не является циклически редуцированным. Тогда либо /її и hm вкладываются в одну вершинную группу, либо расщепляются тройки hm-uhm,hi или hin,hufi2.
Пусть сперва hi » hm вкладываются в одну вершинную группу. Сопряжем элемент Іь при помощи /гт; у полученного элемента слоговая длина меньше, чем у h п мы пришли к противоречию с минимальностью его длины.
Если же тропка hrri-i,hnijh расщепляется (значит, hm = h\ Ь2), то сопрягаем h при помощи frj снова получаем слово меньшей длины. Аналогично поступаем, если расщепляется тропка hm,hiJh-
Замечание. Данная теорема показывает, что для каждого элемента группы (4Л) и его классе сопряженности содержится циклически редуцирован и ын элемент.
В следующем параграфе будет доказан критерий сопряженности элементов фундаментальной группы произвольного конечного графа, из которого будет следовать приведенная ниже теорема 4.3. Однако сформулируем критерий сопряженности и дли случаи, когда ассоциированный грае]) является деревом, ибо в общем случае он выглядит более сложно. Доказательство же этого результата мы произведем в следующем параграфе для случая произвольного конечного графа групп случая.
Теорема 4.3. Пусть— сопряоїсенньїе циклически редуцированные элементы группы, заданной представлением (4-4)- Тогда т = п и h, М0Э1СП0 получить из д, беря его циклическую перестановку gi gi и сопрягая подходящим элементом Ь, вкладывающилгея в вершинные группы, для yi и и+\.
Замечание. В случае, когда граф групп является отрезком, теорема 4.3. совпадает с критерием сопряженности элементов свободного произведения групп с объединенной подгруппой — см. [2].
Следствие 4.1. Пусть g — элемент группы, заданной представлением (4-4)- Тогда слоговая длина любой циклически редуцированной записи из класса gv a является инвариантом для. всех циклически редуцированных элементов этого класса. Данное число наименьшее среда слоговых длин всех элементов Доказательство. Этот факт напрямую следует из того, что элемент наименьшей ;иіп-иы в классе дл с, г циклически редуцирован, и псе такие элементы имеют одинаковую длину.
Вернемся к изучению проблемы сопряженности для фундаментальной группы произвольного связного конечного графа групп У, Редуцированные и циклически редуцированные формы элементов группы, заданной представлением (4,1), обладают темп же свойствами, что и формы для случая, когда ассоциированный граф —дерево. Доказательства этих свойств проводятся аналогично доказательствам теорем 4.2. и 4.3.
Правая часті) равенства (4.5) не является циклически редуцированной записью, а по условию элемент h циклически редуцирован, следовательно, для этой записи не выполнены условия из определении редуцированной формы. Поскольку формы элементов Z и у редуцированы, то нарушения условия «быть редуцированной записью» и (4.5) могут происходить только на стыках слов z, д и z l. В силу симметричности ситуации, достаточно рассмотреть один из двух стыков. Мы отдадим предпочтение стыку между z и д. Для нарушения определения редуцированности (и данном случае возможно нарушение только первого его пункта), нужно чтобы слоги zk и до вкладывались в одну вершинную группу, то есті), пользуясь соглашением первого параграфа, можно записать zk -до = сл.
Перейдем к рассмотрению каждого из этих вариантов.
1. Индукцией по длине сопрягающего элемента можно показать, что на стыках слов z и д невозможно выполнение первого условия из определения расщепления (иначе эле-мет h не был бы циклически редуцированным), тем самым отсекается первый вариант.
2. В силу циклической редуцированности д и условий для 1элемент дп(д01 Ь [1} является циклически редуцированным. Кроме того s(g ) = .s(r/), ибо при помощи групповых соотношений произведение b-igl записывается как одни слог, а произведение д. Таким образом, запись h принимает вид:
Слоговая длина элемента z! = z0t . .J Zk-i, сопрягающего /, меньше, чем s(z) п, следовательно, по предположению индукции, h является циклической перестапоіікой д1 с последующим сопряжением элементом Ь, удовлетворяющим требованию теоремы. Заметим, что все циклические перестановки д , кроме тождественной, совпадают с перестановками исходной записи элемента д, и чтобы доказать теорему для таких перестановок достаточно воспользоваться индукционным предположением. Если же мы имеем дело именно с тождественной перестановкой, то заметим, что для /j] выполнены условия даіпюіі теоремы. ДеПствителыю, т.к. нарушения редуцирован ост и происходят [го второму варианту, то by сливается с перестановкой (ду ... дпд0 ) слева, а поскольку по построению Ь\ = ei Су і 1, то слияние справа также имеет место. По эти же условия вер]ил и для элемента й, а значит, для произведения Ь- by. Следовательно, /t получен из д его перестановкой {ду.. -ш1\ 9пдок\\) " сопряжением Ь-Ь\, что п доказывает теорему .для данного случая.
Ассоциированный граф является деревом
Среди многих проблем, которыми занимается комбинаторная теория групп, важнейшими являются алгоритмические проблемы и изучение свойств свободных конструкций над группами. В последние годы бурно развивается и статистическая теория групп, предметом которой является определение различных мер па группах, вычисление роста групп, порождающих функции, функций Дэна и т.д. Исследования в данной диссертации проводятся в рамках этих двух направлений теории групп.
В 192G году Э, Артнн сформулировал понятие свободного произведения групп па языке нормальных форм. Независимо от него в 1927 году О. Шрайср также ввел это понятие, используй язык представления групп с помощью порождающих и определяющих соотношении; и том же году он дал определение группы поной конструкции -свободного произведения с объединенной подгруппой - п описал нормальные формы элементов таких групп. А.Г. Курошем и 1934 году была доказана структурная теорема о подгруппах свободного произведения групп. В 1949 году в совместной работе Г. Хиг-мана, Б. Неймана п X, Нейман было введено понятие еще одной свободной конструкции — HNN-расширешія групп.
В 19С8-19С9 годах возникает теория Басса-Серра, объясняющая с геометрической точки зрения многие результаты, полученные для групп, являющихся свободными конструкциями. В то же время Ж.-П. Серром было дано определение фундаментальной группы графа групп, обобщающее понятия свободного произведения с объединением и HNN-расширения (см, [1]),
В настоящее время свободные групповые конструкции широко используются в комбинаторной теории групп, в частности, при построении примеров, связанных со сложностью алгоритмических проблем (например, для доказательства неразрешимости классических алгоритмических проблем). При исследовании упомянутых проблем, как разрешимых, так п неразрешимых, плодотворной является идея стратификации входных данных по сложности рассматриваемых алгоритмических проблем. На этом пути определяется регулярная часть алгоритма, то есть множеств входных данных, на которых алгоритм работает быстро (например, в линейное или квадратичное время), а также дополнение к регулярной части - черная дыра алгоритма - множество элементов, про которые мы либо не знаем, как на нем работает алгоритм, либо знаем, что алгоритм па нем работает плохо.
Как правило, при решении алгоритмических проблем вычисления проводятся либо со словами свободной группы, либо со стандартными нормальными формами для фундаментальных групп графов групп. Поэтому важным для изучения свободных конструкции над группами является решение таких задач, как нахождение удобных нормальных форм и определение хороших вероятностных мер для измерения регулярной части алгоритма, его черной дыры и других подмножеств.
Вероятностные меры па свободных группах были введены в работе А. В. Бороішка, А. Г. Мисгппшва и В. Н. Ремесленников а [5], В работе [9] эти вероятностные меры были распространены на свободные групповые конструкции и применены для исследования геперпчсеїшіі сложности проблемы равенства слов и проблемы сопряженности. По этим направлениям проводятся исследования и диссертации.
