Коммутаторы и произведения квадратов в частично-коммутативных группах Шестаков Сергей Леонидович

Содержание к диссертации

Введение

1 Основные понятия 13

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

1.2 Диаграммы ван Кампена 14

1.3 Уравнения в группах 19

2 Описание коммутаторов 23

2.1 Частично-коммутативные группы 23

2.2 Уравнение [х, у] = д в частично-коммутативных группах . 34

3 Произведения двух квадратов 44

3.1 Уравнение х2у2 = д в частично-коммутативных группах . 44

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

• Диаграммы ван Кампена
• Уравнения в группах
• Частично-коммутативные группы
• Уравнение [х, у] = д в частично-коммутативных группах

Введение к работе

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

Частично-коммутативная группа — это группа, заданная при помощи образующих и определяющих соотношений, каждое из которых имеет вид ab = Ьа, где а,Ь — различные образующие. Можно сказать, что частично-коммутативные группы занимают промежуточное положение между свободными группами и свободными абелевыми группами, где есть все возможные соотношения коммутативности между образующими. Таким образом, и свободные группы, и свободные абелевы группы являются частными случаями частично-коммутативных групп.

В свою очередь, частично-коммутативные группы являются частным случаем артиновых групп. В артиновых группах все соотношения имеют вид ab... = Ьа..., где a, b — различные образующие, причем в любом определяющем соотношении длины левой и правой части равны. Если в артиновой группе длины левых и правых частей всех соотношений равны 2, то группа будет частично-коммутативной. Частично-коммутативные группы называют также прямоугольными артиновыми группами (right-angled Artin groups) и графическими группами (graph groups). С каждой артиновой группой можно связать группу Кокстера, добавляя соотношения вида а² = 1 для всех порождающих группы. Для артиновых групп и групп Кокстера может быть доказан ряд утверждений, сходных с доказанными нами для частично-коммутативных групп (например, лемма 2). Естественно предположить, что могут быть предприняты попытки исследовать в этих группах разрешимость квадратичных уравнений при помощи схожих методов.

Частично-коммутативные группы тесно связаны со свободными группами и обладают многими свойствами, которыми обладают и свободные группы. Так, в частично-коммутативных группах схожим образом со свободными решаются проблема слов и проблема сопряженности, доказательства можно найти в [25] (см. также [12, 17]). В работе [10] доказано, что любые два некоммутирующих элемента в частично-коммутативной группе образуют базис свободной группы. Кроме того, как и в свободных группах, члены нижнего центрального ряда имеют тривиальное пересечение, откуда следует, что частично-коммутативные группы линейно упорядочиваемы (см. [11]).

Эти результаты можно считать обобщениями аналогичных результатов для свободных групп. Однако следующие факты показывают, что частично-коммутативные группы обладают рядом специфических интересных свойств. В группе F2 х F2, которая, очевидно, является частично-коммутативной, существуют конечно-порожденные подгруппы с неразрешимой проблемой вхождения (см. [6]). Кроме того, в работе [18] дока-

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

Частично-коммутативные группы тесно связаны с классом групп диаграмм [13], а именно, существует группа диаграмм G, являющаяся полупрямым произведением некоторой (бесконечно-порожденной) частично-коммутативной группы и группы Р. Томпсона F такая, что всякая счетная группа диаграмм вкладывается bG [14]. Многие (но не все) частично-коммутативные группы являются группами диаграмм [3, 14].

В настоящей работе исследуются вопросы о разрешимости в частично-коммутативных группах уравнений вида [х, у] = д и х²у² = д, где д — некоторый элемент группы. Указана явная форма для коммутаторов (Теорема 1) и произведений квадратов (Теорема 2) в частично-коммутативных группах. Таким образом, вопросы о том, равен ли данный элемент группы коммутатору или произведению двух квадратов, сводятся к легко проверяемым условиям (Следствия 2 и 3). Тем самым, в частности, обобщаются известные результаты Уикса для свободных групп [22, 23]. В диссертации показано как описания коммутаторов и произведений двух квадратов в свободных группах, данные У иксом, прямо выводятся из наших описаний для частично-коммутативных групп.

Заметим, что результаты Уикса для свободных групп и их обобщения тесно связаны с классификацией двумерных многообразий. Пусть дано некоторое квадратичное слово W от п переменных, то есть слово, в котором каждая переменная (в степени 1 или —1) встречается ровно 2 раза. Рассмотрим 2п-угольник на плоскости и разметим его стороны символами переменных, входящими в W, так, чтобы каждой стороне соответ-

5 ствовала одна буква, и при обходе контура многоугольника с некоторой вершины по часовой стрелке по ребрам читалось бы слово W. Теперь склеим пары ребер, которым сопоставлены одноименные переменные. В результате получим некоторое двумерное многообразие, которое однозначно определяется исходным словом W. Слово W в дальнейшем будем называть разверткой этого многообразия. Как известно [1], любое двумерное многообразие гомеоморфію или сфере с п ручками (ориентируемый случай), или сфере с п дырами, закленными листами Мебиуса (неориентируемый случай). Из этого следует, что все квадратичные слова (а значит, и все квадратичные уравнения) разбиваются на 2 класса — ориентируемые и неориентируемые.

Слово [хі,уі].. .[х_п,у_п] является простейшей разверткой для сферы с п ручками, а слово х\.. .х\ — для сферы с п листами Мебиуса. При помощи простейших топологических операций любая развертка может быть преобразована в слово одного из этих видов. Из этого следует, что любое квадратичное слово при помощи некоторого автоморфизма можно перевести либо в слово вида [х\, у\\ ... [х_п, у_п], либо в слово вида х\ ... х\. Поэтому уравнения [х\, у і]... [х_п, у_п] — д и х\ ... х\ = д играют важную роль в классе квадратичных уравнений.

Теперь рассмотрим топологическую интерпретацию результатов Уик-са и их обобщений для свободных групп. Как доказал Уикс, циклически приведенное слово является коммутатором в свободной группе тогда и только тогда, когда некоторый его циклический сдвиг имеет вид ABCA~^lB~^lC~^l. Это слово является разверткой ориентируемой поверхности рода 1 (сферы с одной ручкой, т. е. тора), которая в некотором смысле исчерпывает все развертки тора. А именно, если число переменных в развертке тора больше 3, то она, может быть преобразована в слово ABCA~^lB~^lC~^l путем переобозначений переменных и циклических сдвигов. Если число переменных меньше 3, то развертка получается из слова ABCA~^lB~^lC~^l путем замены некоторых переменных на пустые слова.

Для произведения двух коммутаторов, которое соответствует сфере с 2 ручками, имеется уже 8 форм Уикса от 9 переменных каждая. Каждое из этих слов является разверткой сферы с 2 ручками, а вместе они исчерпывают в описанном выше смысле все развертки. Вообще, для уравнения [^xi, 2/1 ] [^xni Уп] — 9 решения, являющиеся также развертками сферы с п ручками, записываются в виде слов от 6п — 3 переменных [8]. В работах [19, 20] указаны формы, описывающие все решения уравнений вида [zi,t/i]... [х_п,у_п] = д и подсчитано точное число таких решений ("максимальных ориентируемых форм Уикса").

Далее излагаем содержание диссертации.

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

В параграфе 1.2 дано определение диаграмм ван Кампена. В данной работе используется расширенное понятие диаграмм ван Кампена, в которых наряду с обычными клетками допускается также наличие так называемых 0-клеток. Такое расширение предложено А. Ю. Ольшанским [7] и позволяет, в частности, добиться того, чтобы контур диаграммы и контуры всех клеток были простыми замкнутыми кривыми. Мы приво-

7 дим доказательство леммы ван Кампена в модифицированной формулировке.

В параграфе 1.3 рассматривается понятие уравнения в группах. Приведены некоторые известные результаты об уравнениях в свободных и частично-коммутативных группах. Приведено доказательство результата Уикса для уравнения [х, у] = д в свободных группах, поскольку при доказательстве основных результатов диссертации используются идеи этого доказательства.

В главе 2 дано определение частично-коммутативных групп, доказаны некоторые вспомогательные леммы и приведен алгоритм решения уравнения [х, у] = д в частично-коммутативных группах.

В параграфе 2.1 рассмотрено понятие частично-коммутативных групп и некоторые их необходимые далее свойства. Пусть G — частично-коммутативная группа, заданная копредставлением V = (Е | TZ). Пусть W — слово над алфавитом Е, причем W = У/\аЪУ/2, где a, b Є S и среди определяющих соотношений есть соотношение [а, b] = 1 (далее будем обозначать этот факт а *-* Ь). Тогда можно перейти от слова W к слову W = ; такой переход будем далее называть элементарным преобразованием. Слова W и V назовем эквивалентными, если V может быть получено из W при помощи элементарных преобразований. Через [W] обозначим класс эквивалентности слова W. Очевидно, все слова из [W] равны W в группе G. Заметим, что в свободной группе любой класс эквивалентности [W] состоит из одного слова W.

По аналогии со свободной группой, слово W назовем приведенным в частично-коммутативной группе G, если все слова из класса [W] приве-

8 дены в свободной группе. Любое слово в частично-коммутативной группе можно привести, находя в его классе эквивалентности неприведенное слово и сокращая в нем пары взаимно-обратных букв, пока это возможно. В отличие от свободных групп, привести слово можно различными способами, однако полученные слова будут эквивалентны. Аналогично слово W называется циклически приведенным, если все слова из класа [W] циклически приведены в свободной группе. Приведенные слова U и V назовем циклически эквивалентными, если V может быть получено из U при помощи переходов к эквивалентным словам и циклических сдвигов.

Слова U и V назовем коммутирующими побуквенно (обозначается С/ <-> К), если для любой буквы a^±l, входящей в слово U и любой буквы 6^і1, входящей в слово V', где a, b Є S, среди определяющих соотношений есть соотношение ab — Ьа. (В частности, если буква х Є Е*¹ входит в U, то x^±l не входит в V.)

Леммы 2 и 3 доказываются геометрическим методом с использованием диаграмм ван Кампена.

Лемма 2. Если слово W не приведено в частично-коммутативной группе, то в нем есть подслово вида xUx~^l, где х Є Е*¹ иїн[/.

Лемма 3. Приведенные в G слова U и V равны в G тогда и только тогда, когда U ~ V. В частности, приведенные формы одного и того же слова эквивалентны.

Далее доказываются две леммы, имеющие технический характер. Из них выводится

Следствие 1. Слово W в частично-коммутативной группе G не яв-

9 ляется циклически приведенным в G тогда и только тогда, когда существует его циклический сдвиг W', содержащий подслово вида xYx~^l (х Є Е*¹), причем х *-> Y.

Лемма 6. Два циклически приведенных в G слова V и W сопряжены в G тогда и только тогда, когда V циклически эквивалентно W. В частности, циклические приведенные формы одного и того же слова циклически эквивалентны.

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

Эти леммы показывают сходство между свободными и частично-коммутативными группами с учетом того, что в свободной группе каждый класс эквивалентности [W] состоит из одного слова W, условие U <-» V эквивалентно условию "U = 1 или V = 1", а условие U ~ V эквивалентно условию "V является циклическим сдвигом С/". В частности, как следует из лемм, проблемы слов и сопряженности в частично-коммутативных группах решаются при помощиа алгоритмов, похожих на соответствующие алгоритмы для свободных групп.

В параграфе 2.2 приводится один из основных результатов диссертации — описание коммутаторов в частично-коммутативных группах. На основе этого описания доказывается существование алгоритма, определяющего разрешимость уравнения [х, у] = д в частично-коммутативных группах. Приведем основную идею доказательства. Пусть слово W является коммутатором. Тогда для некоторых слов А и В выполняется равенство W = АВА^В^-1 в группе G. Пусть слово АВА~^ХВ~¹ не является циклически приведенным в группе G. Тогда по Следствию 1 в нем

10 есть циклическое подслово видагсУгг^-1, где х Є Е*¹, х «-» Y, и мы можем осуществить сокращение, заменяя подслово xYx~^l на Y. Далее исследуется, как меняется тип слова при всех возможных таких сокращениях, то есть при циклическом приведении слова W. В результате доказывается теорема о форме коммутатора в частично-коммутативных группах:

Теорема 1. Слово W в частично-коммутативной группе G является коммутатором тогда и только тогда, когда некоторая его циклически приведенная форма А представима в виде А\А^... АщА^А^¹.. А"¹, и для любых чисел а, /3, у, 5 таких, что \, где а, Ъ Є XI^і1, причем а *-» Ъ. Тогда элементарным преобразованием назовем переход от слова W к слову W = . Будем говорить, что W ~ V, если V может быть получено из W при помощи элементарных преобразований. Очевидно, что ~ есть отношение эквивалентности

25 на множестве всех групповых слов. Слова, находящиеся в данном отношении, будут в дальнейшем называться эквивалентными (в группе G). Через [W] обозначим класс эквивалентности слова W. Очевидно, все слова из [W] равны W в группе G.

Слово W называется приведенным в частично-коммутативной группе G, если всякое слово V, эквивалентное W, приведено в свободной группе, т.е. никакое V [W] не имеет вида V\aa~¹V2 (а Є Е^±х). Если V = V\aa~^lV2i то мы можем произвести сокращение, перейдя к слову V1V2. Любое слово в частично-коммутативной группе можно привести (вообще говоря, многими способами), то есть для любого слова W существует последовательность слов W = W\,W2, , W_n = V, где V приведено вС, и каждое Wi+i получено из Wi (1 < і < п) при помощи элементарных преобразований или сокращений. При этом, очевидно, V равно W в группе G. Всякое приведенное слово V, равное W в G, будем называть приведенной формой слова W в группе G.

Отметим, что этот факт позволяет решать в частично-коммутативных группах проблему равенства слов (см. [12], а также строгое обоснование ниже). Чтобы определить, равны ли слова W и V, достаточно их привести и для полученных слов проверить, совпадают ли их классы эквивалентности. Это можно сделать, так как класс эквивалентности любого слова конечен.

Далее мы будем использовать диаграммы ван Кампена. Заметим, что в частично-коммутативных группах метка любой клетки имеет вида-6- а^-1 Ъ~¹ или а 1 а^-1 1.

26 Введем понятие полосы, которое часто используется при работе с диаграммами. Пусть U — V в частично-коммутативной группе G, заданной копредставлением V = (Е | 7Z). Рассмотрим диаграмму ван Кампена над V, осуществляющую это равенство. Рассмотрим вхождение некоторой буквы а Є Е^±х в слово U. Будем строить полосу, начиная с ребра ео, соответствующего этому вхождению. К ео примыкает некоторая клетка 7Гі- Такая клетка в диаграммах над V имеет метку контура аЪа~¹Ъ~¹ при а «-> b или же является 0-клеткой с меткой контура а 1 а"¹ 1.

Заметим, что в любой клетке для ребра с меткой а найдется лежащее напротив него ребро с этой же меткой. Обозначим через е\ ребро клетки 7Гі, лежащее напротив ео- Продолжим процедуру, выбирая клетку 7Г2 ^ 7i"i, примыкающую к е\ и т.д., пока не получим ребро е_п, лежащее на границе. Таким образом, для любого вхождения буквы в слово U (или V) можно рассмотреть полосу, начинающуюся с этого вхождения. При этом все клетки полосы будут попарно различны, так как полоса не может иметь самопересечений из-за вида определяющих соотношений.

Определение. Слова [/иУв частично-коммутативной группе G называются коммутирующими побуквенно (обозначается U <-> V), если для любой буквы a^±l, входящей в слово U и любой буквы 6^і1, входящей

27 в слово V, где а, Ь Є Е, среди определяющих соотношений есть соотношение ab = Ъа. (В частности, если буква х Є T,^±l входит в U, то х^±1 не входит bV.)

Лемма 2 Слово W в частично-коммутативной группе G не является приведенным в G тогда и только тогда, когда W содержит под-слово вида xUx~^l (х Є 2^і1), где х <-» U.

Доказательство. Если W = WixUx~¹W2 и х <-> U, то W не приведено вСпо определению, так как эквивалентно слову W\Uxx~¹W2.

Докажем обратное. Из определения следует, что если W не приведено в G, то оно равно в G более короткому слову V (при желании последнее можно считать приведенным в G). Пусть Д — диаграмма, осуществляющая равенство W = V. Рассмотрим полосы, исходящие из всех букв слова W. Так как \W\ > \V\, то некоторые из этих полос заканчиваются на W. Каждая полоса, начинающаяся и заканчивающаяся на W, задает разбиение вида W = WixUx~¹W2, где х Є XI^і1. Среди всех таких полос выберем полосу П, у которой значение \U\ минимально.

Все полосы, начинающиеся на U, пересекают П. В противном случае была бы полоса, начинающаяся и заканчивающаяся на U, что противоречило бы минимальности выбора слова U.

Итак, полоса, начинающаяся с любой буквы у слова С/, пересекает полосу П. Это означает, что в П есть клетка, осуществляющая равенство ху = ух, то есть х <г-> у. Следовательно, х <-> U.

Лемма доказана.

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

Лемма 3 Приведенные в G слова U и V равны в G тогда и только тогда, когда U ~ V. В частности, приведенные формы одного и того же слова эквивалентны.

Доказательство. Если U ~ V, то U и V равны в G. Докажем обратное индукцией по сумме длин слов U и V.

Если U и V оба пусты, то доказывать нечего. Поэтому предположим без ограничения общности, что U непусто. Рассмотрим диаграмму, осуществляющую равенство U = V. Первую букву слова U обозначим через х. Положим U = xU'. Рассмотрим полосу, исходящую из х, обозначая

29 ее через П. Из доказательства леммы 2 вытекает, что эта полоса не может заканчиваться на U, следовательно, она заканчивается на V. Тогда V = YxZ. Каждая полоса, начинающаяся на какой-либо букве слова У, пересекает полосу П. Следовательно, Y <-> х. Поэтому V ~ xYZ.

Так как U = xll', то U' = YZ в группе G. При этом U' приведено в G как подслово приведенного в G слова U. Слово YZ приведено в G, так как в противном случае было бы не приведено также слово xYZ, а, следовательно, и эквивалентное ему слово V = YxZ. Слова U' и YZ в сумме имеют меньшую длину, чем U и У, и мы можем применить предположение индукции. Отсюда U' ~ YZ. Следовательно, xU' ~ xYZ, поэтому U ~ V.

Лемма доказана.

Определение. Пусть U = XY, V = YX для некоторых слов X, Y. Тогда будем говорить, что V получено из U циклическим сдвигом.

Определение. Слово W называется циклически приведенным в частично-коммутативной группе G, если всякое слово V, эквивалентное W, циклически приведено в свободной группе.

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

Определение. Будем говорить, что слова V и W циклически эквивалентны в G (обозначается V ~ W), если V и W циклически приведены в G, и W может быть получено из V при помощи элементарных преобразований и циклических сдвигов. Циклически эквивалентные слова сопряжены в G. Очевидно, ~ есть отношение эквивалентности на множестве циклически приведенных слов.

Лемма 4 Пусть W = UabV, a,b Є Е*¹, причем а <-> Ь. Если все циклические сдвиги слова W приведены в G, то и все циклические сдвиги слова W' = UbaV приведены в G.

Доказательство. Всякому циклическому сдвигу слова W, не разрезающему подслово Ьа, соответствует циклический сдвиг слова W, в котором Ьа заменено на ab. Оба этих циклических сдвига эквивалентны и потому оба оказываются приведенными.

Осталось рассмотреть циклический сдвиг слова W, который графически равен aVUb. Допустим, что он не приведен. Тогда по лемме 2 он содержит подслово вида xYx^-1, где х Є Е*¹, причем х «-* Y. Если слово xYx~^l содержится в aVU, то слово aVU не приведено, и потому не будет приведен циклический сдвиг слова W, графически равный abVU (так как последний эквивалентен b- aVU). Аналогично рассматривается случай, когда слово xYx~^l содержится в VUb. Поэтому остается последний случай, когда xYx~^l совпадает с aVUb, что невозможно, так как а

31 и b не взаимно обратны. Лемма доказана.

Доказанная лемма по сути утверждает, что свойство слова иметь все циклические сдвиги приведенными в(?не меняется при замене слова на эквивалентное ему в группе.

Лемма 5 Слово W циклически приведено в G тогда и только тогда, когда все его циклические сдвиги приведены в G.

Доказательство. Пусть W циклически приведено в G, а некоторый его циклический сдвиг не приведен. Тогда по лемме 2 он содержит подслово вида xYx^-1, где х <-> Y. Следовательно, W содержит циклическое подслово вида xYx~^l. Поскольку W приведено, то W не может содержать это подслово. Следовательно, W можно представить в виде Y2X~^lW'xY\, где Y = Y{Yi. Поскольку х <-> Y\, х «-» >2, имеем W ~ x~^lY2\V'Yix, то есть W не является циклически приведенным, что противоречит условию леммы.

Пусть W не циклически приведено. Тогда оно эквивалентно слову, не циклически приведенному в свободной группе, то есть слову, у которого есть циклический сдвиг, не приведенный в свободной группе. Тогда по лемме 4 у эквивалентного ему слова W есть не приведенный в G циклический сдвиг.

Лемма доказана.

Следствие 1 Слово W в частично-коммутативной группе G не является циклически приведенным в G тогда и только тогда, когда существует его циклический сдвиг W, содероісащий подслово вида xYx~^l (х Є 2^і1), причем х

32 Это прямо следует из лемм 2 и 5.

Определение. Пусть слово U = U\ х ІІ2, где х Є Ті^±]-. Тогда U~^l = U₂~^l - х~¹ t/f¹. В этом случае указанные вхождения х в U и х~¹ в U~^l будем называть согласованными.

Лемма 6 Два циклически приведенных в G слова V uW сопряжены в G тогда и только тогда, когда V ~ W. В частности, циклические приведенные формы одного и того же слова циклически эквивалентны.

Доказательство. Если V ~ W, то, очевидно, V и W сопряжены в G.

Докажем обратное. Пусть V сопряжено W в G. Тогда V сопряжено в G любому слову, которое циклически эквивалентно W. Выберем самое короткое слово U такое, что V = U~^lW'U в группе G для некоторого W ~ W. Очевидно, U должно быть приведенным в G. Положим Z = U~^lW'U. Докажем, что Z приведено в G. Пусть это не так. Тогда по лемме 2 в Z содержится подслово вида x~^lYx, где х Є 2^і1, причем х <-> Y. Так как W приведено в G, то x~^lYx не содержится в W'. Поэтому либо х~¹ содержится в U^-1, либо х содержится в U. В силу симметрии можно считать, что х~¹ содержится в U~^l.

Поскольку слово U приведено, то х не содержится в С/^-1. Предположим, что х содержится в W. Тогда U~^l = Щ¹х~¹иї¹, W = , причем х «-> U{^lW\. Подставим выражения для U^±1 и W в Z. Получим: Z = (U₂~¹x~¹U{¹)(WixW2){UixU2). Теперь воспользуемся коммутативностью х с U^¹ и с Wi в G. Получим, что Z равно в G слову U₂~^lU{^lW_lW₂xU_lU₂. Итак, Z равно в G слову {U_lU₂)-^lW_lW2x{U_lU₂).

Очевидно, W циклически эквивалентно W1W2X (с учетом ТОГО, ЧТО X коммутирует с W\), a U\Щ имеет меньшую длину, чем U. Следовательно, мы получили противоречие с выбором U.

Предположим теперь, что х содержится в U, причем это его вхождение согласовано с рассмотренным выше вхождением х~~¹ в U~^l. Тогда U = U\xU2, причем х <-> Ui^lW'Ui. Подставим выражение для U^±l в Z. Получим Z = U₂~^lx'~^lU^:[^lW'UixU2- Теперь мы снова сокращаем х~¹ с х, пользуясь коммутативностью, получая, что Z равно в G слову (UiU2)~¹W(U1U2). Очевидно, длина U1U2 меньше, чем длина U, поэтому мы опять получили противоречие с выбором U.

Остался последний случай: х содержится в U, причем вхождения х^-1 в U~^l и х в U не согласованы. В силу симметрии можно считать, что согласованное с первой буквой слова x~^lYx вхождение х в слово U расположено левее, чем последняя буква слова x~^lYx, то есть входит в слово Y. Тогда мы можем сократить эти два согласованных вхождения, как в предыдущем случае, так как содержащееся между ними подслово слова Y по-прежнему побуквенно коммутирует с х. Вновь приходим к противоречию с выбором U.

В итоге мы получили, что слово Z приведено в G. Так как V = Z в группе G, а V и Z приведены в G, то V ~ Z по лемме 3. Так как V циклически приведено в G, то и Z циклически приведено в G по определению. Поэтому U должно быть пустым. Следовательно, V = W в G. Тогда V ~ W в силу леммы 3. Поскольку W ~ W, то У ~ W, что и требовалось доказать.

Лемма доказана.

Заметим, что лемма 6 позволяет решать в частично-коммутативных группах проблему сопряженности. Чтобы определить, сопряжены или нет слова V и W, достаточно их циклически привести (каким-либо способом) и определить, будут ли полученные слова циклически эквивалентны. Последнее можно сделать эффективно, так как для каждого слова класс циклически эквивалентных ему слов конечен.

Проблема сопряженности в частично-коммутативных группах была решена в [17].

2.2 Уравнение [х,у] = д в частично-коммутативных группах

В данном параграфе мы даем описание коммутаторов в частично-коммутативных группах (Теорема 1) и основанный на нем алгоритм, проверяющий разрешимость коммутаторных уравнений вида [х, у] = д в этих группах (Следствие 2). Мы считаем, что могут быть предприняты попытки распространить использованные здесь идеи для решения уравнения [х, у] = д в группе Р. Томпсона F и в более широком классе групп диаграмм, которые тесно связаны с частично-коммутативными группами [13, 14].

Введем понятие триангуляционного графа. Рассмотрим выпуклый т-угольник. Проведем в нем диагонали так, чтобы они образовывали триангуляцию этого m-угольника. Полученный граф назовем триангуляционным. Триангуляционный граф, у которого каждой вершине сопоставлено некоторое слово А{ (1 < г < т), называется размеченным триангуляционным графом.

35 Заметим, что при т = 3 размеченный триангуляционный граф (для данного набора слов) единственный, при т = 4 имеется два различных размеченных триангуляционных графа, так как в четырехугольнике диагональ можно провести двумя различными способами.

А_л An Ал А?

Лі А_1к .А₂

Определение. Будем говорить, что слово А в частично-коммутативной группе G удовлетворяет условию С(т) (т > 3), если А может быть представлено как А1А2 ... АтА^А^¹... Л"¹ для некоторых (возможно, пустых) слов Ai, ..., А_т, и существует размеченный триангуляционный граф с т вершинами, имеющими метки А\, ..., А_т (при чтении по часовой стрелке), удовлетворяющий следующему условию: если две различные вершины, помеченные словами А{ и Aj не соединены в триангуляционном графе, то Аі <-» Aj.

Для дальнейшего удобства введем обозначение -і л-1 v[Ai,..., А_т) = А\... A_mAi ... А

Будем считать, что слово v(Ai,..., А_т) автоматически удовлетворяет условию С(т) при 0 < т < 2.

Из определения ясно, что слово, представимое в виде у(А\, А2, A3), всегда удовлетворяет условию С(3). Для того чтобы слово, представимое в виде у(А\,А2,Аз,А4), удовлетворяло условию С(4), достаточно, чтобы Лг побуквенно коммутировало с А^ (как на рисунке выше) или А\ побуквенно коммутировало с А^, если проведена другая диагональ.

Очевидно, что условие С(т) инвариантно относительно циклических сдвигов слова А, начинающихся с любого из слов Af^l (1 < і < т).

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

Теорема 1 Слово W в частично-коммутативной группе G является коммутатором тогда и только тогда, когда некоторая его циклически приведенная форма А представима в видеА\Аі... АтА^А^¹ .. А^ и для любых чисел а, /3, у, S таких, что 1<а/у<5<т выполняется хотя бы одно из условий: А_п <-> Л₇ или Ар «-» А$.

Следствие 2 Для любой частично-коммутативной группы G, заданной конечным копредставлением, алгоритмически разрешимо свойство данного элемента быть коммутатором. Иными словами, существует алгоритм, проверяющий разрешимость уравнений вида [х, у] = g в группе G.

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

Для каждого из слов списка нужно проверить, не имеет ли оно вид С(т) для какого-либо т. Достаточно заметить, что в условии теоремы можно считать все слова А\, ..., А_т непустыми, поэтому значения т ограничены сверху.

Доказательство теоремы 1. Для начала убедимся в том, что условие из формулировки теоремы, относящееся к слову А, эквивалентно

37 условию С(т). В самом деле, пусть слово А имеет вид С(т). Пусть числа а, /3, 7, S удовлетворяют условию 1<а<Р<^/у<6<т. Тогда т > 4 и вершины А_а, Ау не являются соседними в m-угольнике. То же самое верно для вершин Ар и А$. Поскольку в триангуляционном графе никакие две диагонали не пересекаются, то либо не соединены вершины с метками А_а и Л₇, либо не соединены вершины с метками Ар и А. Поэтому либо А_а <-» А-у, либо Ар <-» А$.

Обратно, пусть слово А удовлетворяет условию из формулировки. Если т < 2, то условие С(т) выполнено. При т > 3 рассмотрим контур выпуклого ш-угольника, вершины которого помечены словами А\, ..., А_т. Проведем все те диагонали, концы которых помечены словами, не коммутирующими побуквенно. По условию, никакие две из проведенных диагоналей не пересекаются во внутренних точках. Остается дополнить полученный граф до триангуляционного.

Достаточность. Пусть A = v(A\,..., А_т), и для А выполнено условие С(т). Будем доказывать индукцией по т, что А является коммутатором. При m < 2 это очевидно. Рассмотрим случай т > 3. Рассмотрим размеченный триангуляционный граф. Легко видеть, что в любой триангуляции выпуклого m-угольника есть вершина валентности 2. С учетом сделанного перед теоремой замечания об инвариантности А относительно подходящих циклических сдвигов, можно считать, что это вершина с меткой А_т. Из определения размеченного триангуляционного графа и условия С(т) для А следует, что А_т <-> А{ при всех г, удовлетворяющих условию 2 < г < т — 2. В частности, А_т коммутирует с /^...Дті-г-(Все равенства далее рассматриваются в группе G.) Вставим А_т¹А_т по-

38 еле А_х в слове А. Тогда A = А₁(А-¹А_т)А₂ ... A_m-iA_mA\^x... А^__ХА^. Воспользуемся указанной выше коммутативностью и получим, что A = A\A_m А2 ... A_mA_m-iA_mAi ... А_т_₁А_т .

Теперь обозначим А\А~^ через А[, A_mA_m-i через А'_т_₁. В результате получим, что А равно в G слову A' = v(A[,A2,..., A'_m_ij.

Проверим, что А' удовлетворяет условию С(т — 1). Из исходного триангуляционного графа исключим вершину А_т с двумя исходящими из нее ребрами. Получим (га — 1)-угольник, в котором метку А\ заменим на А[, а метку А_т-\ — на А!_т__х. Если в исходном графе не было ребра между вершиной А\ и вершиной Аі (3 < г < га — 2), то А\ <-» А{. Так как и А_т побуквенно коммутирует с А{, то для слова А[ = А\А~^ также будет выполняться условие А[ «-» Аі. Те же рассуждения можно провести и для слова А!_т__х. Следовательно, А' имеет вид С(т — 1). По предположению индукции А' является коммутатором. Поскольку А = А' в G, то и А является коммутатором. Достаточность доказана.

Необходимость. Поскольку W является коммутатором, то для некоторых слов X, Y выполняется W = [X, Y) = X~^lY~^lXY в G. В частности, X~^lY~^lXY удовлетворяет условию С(2) и сопряжено W в G. Рассмотрим все слова, сопряженные W и удовлетворяющие условию С (га) при каком-либо га. Выберем среди них слово наименьшей длины и обозначим его через А. Тогда A = v(A\,..., А_т) для некоторого га. Наша цель — доказать, что А циклически приведено в G. Тогда А будет циклически приведенной формой слова W.

Будем вести доказательство от противного. Пусть А не является циклически приведенным. Тогда по следствию 1 существует циклическое

39 подслово слова А вида xUx^-1, где х «-» U, х Є Е^±:. В силу инвариантности условия С (га) относительно подходящих циклических сдвигов можно считать, что х входит в А\.

Предположим сначала, что слово, расположенное между некоторым вхождением буквы хъ А\п согласованным вхождением буквы ге^-1 в А{¹, коммутирует с я; в группе G. Тогда данные вхождения букв х, х~¹ можно вычеркнуть из слова Л, в результате чего слово А заменится на более короткое и равное ему в группе слово A' = v(A[,A2, .., А_т), где А[ получено из А\ вычеркиванием буквы х. Поскольку состав букв, входящих в рассматриваемые слова, мог только уменьшиться, все побуквешю коммутирующие слова таковыми и остались, и потому А' имеет вид С (га), что противоречит выбору слова А.

Из замечания предыдущего абзаца сразу следует, что слово xUx~^x не содержит вхождения буквы х~¹ в слово Aj¹, согласованного с вхождением начальной буквы хв А\. Более того, слово xUx~^l обязано содержаться в А\... А_т. Действительно, в противном случае последняя буква слова xUx"¹ входит в Л^-1 и расположена левее вхождения буквы х^-1 в то же слово, согласованного с вхождением начальной буквы слова xUx~~^l в А\. Но тогда вхождение буквы а; в Лі, согласованное с вхождением последней буквы х~^г слова xUx~^l, расположено правее первой буквы подслова xUx~^l, и потому между некоторыми двумя согласованными вхождениями х^±г, как и выше, находится коммутирующее с х слово, что невозможно.

Если слово xUx~^l содержится в Лі, то можно заменить слово Лі на более короткое, равное ему в группе слово А[, заменяя подслово xUx~^l

40 на U. Слово A' = v(A'₁, А₂,..., А_т), очевидно, будет равно А в G, и будет удовлетворять условию С (га), поскольку в А\ набор букв не увеличился, а остальные слова не изменились. В результате мы вновь получим противоречие с выбором А.

Итак, xUx"¹ не содержится в А\. Последняя буква слова xUx~~^l входит в некоторое слово А_к при 2 < к < га. Тогда А\ = А[хА", Ak = А'_кх~¹А_к, причем х <-» А'[ и х <-» А'_к. Тогда мы можем заменить в v(A\,..., А_т) слово А\ на слово А_хА![х, а А_к заменить на, х~¹ А!_кА_к. Новое слово будет иметь такую же длину и также будет удовлетворять условию С (га) ввиду неизменности состава букв. Поэтому можно фактически считать, что первая буква слова xUx~^l является последней буквой слова А\, последняя буква слова xUx~^l — первой буквой слова А_к, причем х побуквенно коммутирует с U = Ач ... А_к-\.

Теперь рассмотрим два случая.

Случай 1. Пусть к = т, т.е. х~¹ — первая буква слова А_т. Тогда А\ = А[х, А_т = х~¹А'_т, причем х <-» А{ при всех 2 < г < т. Тогда

А = А[хА₂... Am-xx^A'nX-¹^)-¹^¹... А^А'т)'¹^

Теперь сократим пару вхождений х и х~¹ в первой половине слова А, пользуясь коммутативностью и положим A_m+i = х~¹. Получим, что А равно в G слову

А = A_xAт_іЛ_тл_7П+і(Л₁) А₂ ...А_т_₁(А_т) А_т+1.

Докажем, что слово А¹ удовлетворяет условию С(т + 1). Добавим к размеченному триангуляционному графу для слова А вершину А_т+і и соединим ее с вершинами Лі, А_т. При этом вершины А\ и А_т будут со-

41 'государственная! ⁴¹ і 5.ИВЛИОТЕКА І единены друг с другом диагональю. Очевидно, новый граф также будет размеченным триангуляционным графом. Поскольку в слове А[ состав букв не увеличился по сравнению с Аі, то А[ будет побуквенно коммутировать со всеми словами Л*, с которыми побуквенно коммутирует А\. Аналогичный вывод справедлив и для слова А'_т. Со словом A_m+i, равным х~¹, побуквенно коммутируют слова Лі при всех 2 < г < т, что нам и требуется, поскольку в новом размеченном триангуляционном графе вершина А_т+і не соединена ни с одной вершиной, кроме Лі и А_т. В итоге мы получили, что А равно в G слову А', которое имеет меньшую длину, чем А и удовлетворяет условию С(т + 1), что противоречит выбору А. Можно заметить, что этот этап доказательства является в некотором смысле обращением доказательства достаточности в данной теореме.

Случай 2. Пусть к < т, т. е. х"¹ — первая буква слова Ak, где 2 < к <т. Тогда А\ = А'_гх, Ak = х~¹А_ъ причем х <-> Л* при всех 2 < г < к. Тогда

Л = v{A[x, Л₂,..., А_к-_Ъх~¹А!_к, А_к+1,..., А_т).

Теперь сократим пару вхождений х и х~¹ в первой половине слова Л, пользуясь коммутативностью. Получим, что Л равно в G слову

Л = А₁... А_к ... А_тх (А^ ... \А_к) хА_к+1... А_т .

Заметим, что, как и в предыдущем случае, слово А[ побуквенно коммутирует со всеми словами Л^, с которыми побуквенно коммутировало слово Лі, и аналогичное утверждение верно для слова А'_к.

Поскольку х входит в Лі, а х~¹ входит в А_к, то Лі не коммутирует с А_к побуквенно. Тогда они соединены диагональю в размеченном триангуляционном графе. Многоугольник, образованный вершинами Лі, А_к, А_к+і,

42 ..., А_т, также триангулирован. Ребро, соединяющее А\ и А_к, входит в некоторый из треугольников разбиения. Поэтому существует вершина Ai, где к < I < т, которая соединена ребром и с Лі, и с Л&, причем единственная. Поскольку в триангуляционном графе никакие две диагонали не пересекаются, х <-> А{ при всех і таких, что к < г < I. Докажем это от противного. Допустим, что существует Ai (к < і < I) такое, что х не коммутирует побуквенно с Ai. Тогда и А\ как слово, содержащее х, не коммутирует побуквенно с Aj. Это означает, что диагонали, соединяющие Ак с Ai и А\ с Ai, пересекаются, что противоречит определению триангуляции. Поэтому х <-> А{ при к < г < I. Аналогично доказывается, что х побуквенно коммутирует с Аі при І < і < т. В частности, х *-> А_к\_г... Af}_v Л/4-1... А_т <-> х. Соответствующие вхождения в слово А' можно переставить. Преобразуем в соответствии с этим слово А'. Оно равно в G слову

А₁... А_к . А\х Лл-1 . А_т\А_х ) ... \А_к) ... А₁_₁хА₁ ... А_т .

Теперь положим A'i = Aix~^l и получим, что А равно в G слову A" = v{A!_l,A₂,...,A_k-i,A_k,A_k+_l,...,A_l__l,A!_l,A_l+l,...,A_m).

Докажем, что А" удовлетворяет условию С(т). В размеченном триангуляционном графе для А заменим метки слов Лі, А_к, Аі на А[, А'_к, А\ соответственно. Как уже отмечалось, А[ побуквенно коммутирует побуквенно со всеми словами Ai, с которыми побуквенно коммутирует Лі; аналогичное утверждение верно для А'_к. Буква х коммутирует побуквенно со всеми словами Аі при г ф 1, і ф к, г ф I. Отсюда вытекает, что слово Л; = Л/х^-1 коммутирует побуквенно со всеми словами Аі, с

43 которыми А\ не была соединена диагональю. В итоге мы нашли слово А", которое удовлетворяет условию С(т), равно А в группе G и имеет меньшую длину. Это вновь противоречит выбору А. Все случаи рассмотрены. Теорема доказана.

Замечание. Пусть G — частично-коммутативная группа с к порождающими. Тогда без ограничения общности можно считать, что числот в формулировке теоремы не превышает числа Рамсея R(4, к + 1). Более тонкий анализ показывает, что т можно считать не превосходящим Зк.

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

Покажем, как результат Уикса для свободных групп [23] вытекает из нашего описания. Заметим, что в свободной группе условие U <-* V имеет место тогда и только тогда, когда хотя бы одно из слов U, V пусто. Поэтому если слово A = v(Ai,...,A_m) удовлетворяет условию С(т), то из непустоты слов А\, ..., А_т сразу вытекает, что в соответствущем триангуляционном графе любые две вершины должны быть соединены ребром, поэтому т < 3. При т = 3 получаем слово А1А2А3АЇ¹ А^¹ А^¹, то есть форму Уикса, а при т < 3, очевидно, получим частные случаи этого слова. Таким образом, результат Уикса для коммутаторного уравнения в свободной группе прямо следует из нашего описания.

Диаграммы ван Кампена

Здесь обход каждой из клеток с некоторого места в любом направлении дает слово aba lb l или 6с6_1с-1, а обход контура всей диаграммы — слово acbc la lb l. Из этого следует, что в группе выполняется соотношение acbc la lb l = 1 или acb = Ьас.

Теперь, следуя монографии [7], рассмотрим формальное понятие диаграммы над копредставлением группы.

Сначала мы рассмотрим понятие клеточного разбиения поверхности. Диаграммы можно рассматривать на различных поверхностях, но нам потребуются только дисковые диаграммы, поэтому будем далее считать, что X — это топологический диск. Пусть Р — некоторый п-угольник на плоскости или круг с п отмеченными на ограничивающей его окружности вершинами, если п = 1,2. Обозначим его вершины через А\, Л2, ..., Ап, а ребра — через А1А2, А2А3, АпА\. Пусть / — непрерывное отображение Р X, причем выполняются следующие условия: 1. Ограничение / на внутренность Р является вложением в X. 2. Ограничение / на внутренность любой стороны многоугольника Р является вложением в X. 3. Если для некоторых точек а и b из Р выполняется f(a) = f(b), то а и b принадлежат границе дР, причем если а — вершина в Р, то и b — вершина, а если а не является вершиной, то образы сторон, на которых лежат а и Ь, совпадают в X (при этом, очевидно, b также не будет верши ной Р). Таким образом, при отображении / могут склеиваться вершины и ребра многоугольника Р. Тогда пара (П,/), где П = f(P), называется п-уголъной клеткой в X. Клеточным разбиением А поверхности X называется множество клеток (Пі, /і), (ГІ2, /2),..., (Пт, /т) такое, что выпоняются условия::

2. Пересечение любой пары различных клеток П и П,- пусто или состоит из нескольких общих ребер и общих вершин этих клеток.

Вершины клеток (то есть образы вершин соответствующих многоугольников) называются вершинами клеточного разбиения, ориентированные стороны клеток — ребрами клеточного разбиения.

Произвольное клеточное разбиение поверхности X называется картой на X. Зададим на диске ориентацию: будем считать, что контуры клеток обходятся против часовой стрелки, а контур самого диска — по часовой стрелке. Контур (любой клетки и всей карты) из п сторон задается ребрами ei,..., еп; при этом путь р = е\... еп замкнут. Всякий контур можно рассматривать с точностью до циклического сдвига, меняя начало пути р.

Пусть группа G задана копредставлением V = (Е 71). Пусть на некоторой карте Д задана размечающая функция /?, которая каждому ребру е из Д сопоставляет слово р(е) над Е, и при этом (е-1) = (р(е) 1. Меткой пути р = е\... еп называется слово (р(р) = (р{е{)... (р{еп). Если р — пустой путь, то (р(р) = 1 по определению. Хотя метка ребра может состоять из нескольких букв, но ясно, что при помощи разбиения ре бер можно добиться того, чтобы метка каждого ребра была буквой или пустым словом.

Клетка П карты А с контуром р = е\... еп называется lZ-клеткой (типа 1), если метка контура (р(р) графически равна некоторому циклическому сдвигу слова R или R l, где R Є 7Z. Клетка П называется 0-клеткой (типа 2), если при некоторых і j выполняется следующее: (р(еі) = а Є S, (f(ej) = a-1, p(ek) = 1 при к ф i,j. Клетка П называется 0-клеткой (типа 3), если /?(ег) = 1 Для всех 1 г п. Очевидно, что метка контура любой 0-клетки равна 1 в свободной группе.

Карта А называется диаграммой над копредставлением V, если любая клетка из А является 7-клеткой или 0-клеткой.

Приведенное здесь понятие диаграммы отличается от классического (см. [4]) тем, что наряду с 7?.-клетками используются также и 0-клетки. Любую диаграмму ван Кампена можно преобразовать, (см. [7]) используя 0-клетки, так, что контур диаграммы и контуры всех клеток будут простыми замкнутыми кривыми.

Уравнения в группах

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

Частично-коммутативная группа — это группа, заданная копредстав-лением вида V = (Е 71), где Е — множество образующих, 1Z — множество определяющих соотношений, причем все соотношения имеют вид [rcj, ] = 1, где Х{, Xj — различные образующие. Для этих групп используются также термины "графические группы" (graph groups) и "прямоугольные артиповы группы" (right-angled Artin groups). Для полугрупп и моноидов с аналогичным свойством термин "частично-коммутативные" является общепринятым.

Любая частично-коммутативная группа может быть задана при помощи (простого) графа Г следующим образом: множеством порождающих группы будет множество всех вершин графа; порождающие Х{, Xj коммутируют, то есть среди определяющих соотношений есть соотноше 23 ниє [rcj,#j] тогда и только тогда, когда соответствующие Х{ и Xj вершины соединены в графе Г ребром. В этом случае мы вводим обозначение xfl - xf1. Группу, заданную таким образом при помощи графа Г мы будем обозначать G(T).

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

Зафиксируем некоторую частично-коммутативную группу G, заданную при помощи простого графа Г.

Далее мы рассматриваем некоторые элементарные факты о частично-коммутативных группах, необходимые нам для доказательства основного результата. Похожие утверждения содержатся в статье [17].

Введем понятие элементарного преобразования. Пусть W = \V1abW2, где а, Ъ Є XIі1, причем а -» Ъ. Тогда элементарным преобразованием назовем переход от слова W к слову W = \V1baW2. Будем говорить, что W V, если V может быть получено из W при помощи элементарных преобразований. Очевидно, что есть отношение эквивалентности на множестве всех групповых слов. Слова, находящиеся в данном отношении, будут в дальнейшем называться эквивалентными (в группе G). Через [W] обозначим класс эквивалентности слова W. Очевидно, все слова из [W] равны W в группе G.

Слово W называется приведенным в частично-коммутативной группе G, если всякое слово V, эквивалентное W, приведено в свободной группе, т.е. никакое V [W] не имеет вида V\aa 1V2 (а Є Е±х). Если V = V\aa lV2i то мы можем произвести сокращение, перейдя к слову V1V2. Любое слово в частично-коммутативной группе можно привести (вообще говоря, многими способами), то есть для любого слова W существует последовательность слов W = W\,W2, Wn = V, где V приведено вС, и каждое Wi+i получено из Wi (1 і п) при помощи элементарных преобразований или сокращений. При этом, очевидно, V равно W в группе G. Всякое приведенное слово V, равное W в G, будем называть приведенной формой слова W в группе G.

Отметим, что этот факт позволяет решать в частично-коммутативных группах проблему равенства слов (см. [12], а также строгое обоснование ниже). Чтобы определить, равны ли слова W и V, достаточно их привести и для полученных слов проверить, совпадают ли их классы эквивалентности. Это можно сделать, так как класс эквивалентности любого слова конечен

Частично-коммутативные группы

Предположим сначала, что слово, расположенное между некоторым вхождением буквы хъ А\п согласованным вхождением буквы ге-1 в А{1, коммутирует с я; в группе G. Тогда данные вхождения букв х, х 1 можно вычеркнуть из слова Л, в результате чего слово А заменится на более короткое и равное ему в группе слово A = v(A[,A2, Ат), где А[ получено из А\ вычеркиванием буквы х. Поскольку состав букв, входящих в рассматриваемые слова, мог только уменьшиться, все побуквешю коммутирующие слова таковыми и остались, и потому А имеет вид С (га), что противоречит выбору слова А.

Из замечания предыдущего абзаца сразу следует, что слово xUx x не содержит вхождения буквы х 1 в слово Aj1, согласованного с вхождением начальной буквы хв А\. Более того, слово xUx l обязано содержаться в А\... Ат. Действительно, в противном случае последняя буква слова xUx"1 входит в Л-1 и расположена левее вхождения буквы х-1 в то же слово, согласованного с вхождением начальной буквы слова xUx l в А\. Но тогда вхождение буквы а; в Лі, согласованное с вхождением последней буквы х г слова xUx l, расположено правее первой буквы подслова xUx l, и потому между некоторыми двумя согласованными вхождениями х±г, как и выше, находится коммутирующее с х слово, что невозможно.

Если слово xUx l содержится в Лі, то можно заменить слово Лі на более короткое, равное ему в группе слово А[, заменяя подслово xUx l на U. Слово A = v(A 1, А2,..., Ат), очевидно, будет равно А в G, и будет удовлетворять условию С (га), поскольку в А\ набор букв не увеличился, а остальные слова не изменились. В результате мы вновь получим противоречие с выбором А.

Итак, xUx"1 не содержится в А\. Последняя буква слова xUx l входит в некоторое слово Ак при 2 к га. Тогда А\ = А[хА", Ak = А кх 1Ак, причем х -» А [ и х -» А к. Тогда мы можем заменить в v(A\,..., Ат) слово А\ на слово АхА![х, а Ак заменить на, х 1 А!кАк. Новое слово будет иметь такую же длину и также будет удовлетворять условию С (га) ввиду неизменности состава букв. Поэтому можно фактически считать, что первая буква слова xUx l является последней буквой слова А\, последняя буква слова xUx l — первой буквой слова Ак, причем х побуквенно коммутирует с U = Ач ... Ак-\. Теперь рассмотрим два случая.

Случай 1. Пусть к = т, т.е. х 1 — первая буква слова Ат. Тогда А\ = А[х, Ат = х 1А т, причем х А{ при всех 2 г т. Тогда А = А[хА2... Am-xx A nX-1 )-1 1... А А т) 1 Теперь сократим пару вхождений х и х 1 в первой половине слова А, пользуясь коммутативностью и положим Am+i = х 1. Получим, что А равно в G слову А = AxA i... лт_іЛтл7П+і(Л1) А2 ...Ат_1(Ат) Ат+1.

Докажем, что слово А1 удовлетворяет условию С(т + 1). Добавим к размеченному триангуляционному графу для слова А вершину Ат+і и соединим ее с вершинами Лі, Ат. При этом вершины А\ и Ат будут со единены друг с другом диагональю. Очевидно, новый граф также будет размеченным триангуляционным графом. Поскольку в слове А[ состав букв не увеличился по сравнению с Аі, то А[ будет побуквенно коммутировать со всеми словами Л , с которыми побуквенно коммутирует А\. Аналогичный вывод справедлив и для слова А т. Со словом Am+i, равным х 1, побуквенно коммутируют слова ЛІ при всех 2 г т, что нам и требуется, поскольку в новом размеченном триангуляционном графе вершина Ат+і не соединена ни с одной вершиной, кроме Лі и Ат. В итоге мы получили, что А равно в G слову А , которое имеет меньшую длину, чем А и удовлетворяет условию С(т + 1), что противоречит выбору А. Можно заметить, что этот этап доказательства является в некотором смысле обращением доказательства достаточности в данной теореме.

Уравнение [х, у] = д в частично-коммутативных группах

Будем вести доказательство от противного. Пусть А не является циклически приведенным. Тогда по следствию 1 существует циклическое подслово слова А вида xUx l, где х - U, х Є 2і1. Заметим, что условие Q(m) инвариантно относительно циклического сдвига, начинающегося со второго вхождения слова А\ в слово А (то есть ровно с середины слова А). Поэтому можно считать, что х входит в первую половину слова А, то есть содержится в подслове AmBm_i... В\А\С.

Из условия х U следует, что х±х не содержится в U. Поэтому не может быть, чтобы U содержало вторую половину слова А, то есть подслово AiB{1... B _iAmC l. Значит, xUx"1 — подслово в А.

I. Сначала разберем случай, когда я;-1 содержится во второй половине слова А. Рассмотрим три под случая.

Случай 1.1. Буква х содержится в одном из слов АІ, 1 г т. Тогда из условия х - U следует, что х 1 содержится во втором вхождении слова А{ в слово А, так как в противном случае слово U содержало бы хотя бы одну букву x±l. Действительно, если последняя буква слова xUx l расположена левее второго вхождения А{ в А, то парная ей буква содержится в U. Аналогично, если х-1 расположена правее второго вхождения АІ, то U содержит букву, парную первой букве слова xUx l.

Эти же соображения показывают, что последняя буква слова xUx l, входящая в АІ, расположена левее вхождения, парного первой букве слова xUx l. Таким образом, АІ имеет вид A{ = А х А хА - . При этом U = А 1 Ві-!... В САгВї1... Br} . Подставим слово А{ в слово А: А = Ат... ВіА АЧхАЧ ... AlCAl... А р 1 А хА В 1... AmC l. Теперь заменим в слове А подслово xUx l на U и воспользуемся коммутативностью х 1 с А[ и х с Л" (последнее вытекает из того, что А - , А { входят в U). Получим, что А равно в G слову Ат В{Х А А Ai ... A\GA\... AiAi Ai xBi ... AmC

Обозначим BiX l через Д, а А А -А - — через At. Получим, что в группе G слово А равно А = v(A\, Д,..., Л , Д,..., Ат, С). Докажем, что А удовлетворяет условию Q(m). Достаточно проверить условия побук-венной коммутативности для Д, так как состав букв в слове А{ не увеличился по сравнению со словом Ai, а остальные слова не изменились. Поскольку В І = В{Х, то достаточно проверить несколько условий коммутативности, относящихся к х. Во-первых, х -» С, так как С входит в U; во-вторых, х - Aj и х - Bj при j г, так как слова Aj и Bj входят в U при j і; в-третьих, х - Aj при j i + lnx r- Bj при j г, так как х входит в слово А{.

В итоге мы видим, что А удовлетворяет условию Q(m) и имеет меньшую длину, чем А, что противоречит условию выбора слова А.

Случай 1.2. Буква х содержится в одном из слов ВІ, 1 і т. Тогда из условия х - U следует, что х-1 содержится в слове Дг\ причем вхождения ж в Д и х г в Д-1 являются парными. (См. аргумент, использованный при рассмотрении предыдущего случая.) Следовательно, ВІ = В[хВ 1, а[/Е B Ai... AiCAi... Ai(B") l. Теперь мы подставим выражение для Д в А, сократим через слово U пару букв х, х 1 и обозначим В[В 1 через Д. Тогда мы получим, что А равно в группе G слову A = v{A\, Д,..., АІ, ВІ, ..., Ат, С). Поскольку в Д состав букв не увеличился по сравнению с ВІ, а, остальные слова не изменились, то А удовлетворяет условию Q(m). Поскольку А короче, чем А, то мы опять получили противоречие с выбором слова А.

Случай 1.3. Буква х содержится в слове С. Пусть х 1 содержится в одном из слов вида А{ или Bf1 во второй половине слова А. Заметим, что условие Q(m) инвариантно относительно операции, заключающейся в переносе слова С 1 из конца в начало и последующей заменой получившегося слова на обратное. Если мы применим эту операцию в данном случае, то получим слово, в котором подслово xUx l находится целиком в первой половине. Этот случай будет рассмотрен ниже.

Пусть теперь х 1 содержится в слове С-1. Тогда, как и выше, из условия х - U вытекает, что вхождения х в С и х-1 в С-1 являются парными. Поэтому С = С хС", U = С"А\.. .Ат(С") 1. Теперь мы можем подставить выражение для С в слово Л, сократить буквы х и х 1 через слово U, обозначить С С" через С и получить противоречие с выбором Л, как и выше. Все три подслучая рассмотрены. П. Перейдем к рассмотрению случаев, когда xUx l целиком содержится в первой половине слова А.

Легко видеть, что слово xUx l не может содержаться целиком ни в одном из слов вида АІ, ВІ ИЛИ С. В противном случае мы можем заменить в нем подслово xUx l на U, не увеличивая состава букв и перейти от А = v(A\, Ві,..., Дп-ь Ат, С) к более короткому слову вида Q(m), равному ABG.

Похожие диссертации на Коммутаторы и произведения квадратов в частично-коммутативных группах

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