Проблемы степени и степенной сопряженности в группах с условиями С(4) & Т(4) тема автореферата и диссертации по математике, 01.01.06 ВАК РФ

ВВЕДЕНИЕ.

Глава 1. АНАЛОГ ТЕОРЕМЫ ЛИПШУЦА ДЛЯ ГРУПП С УСЛОВИЕМ

С(4)&Т(4).

§ 1. Предварительные сведения.

§2. Элементы конечного порядка в группах с условием С(4)&Т(4).

§3. Элементы бесконечного порядка в группах с условием С(4)&Т(4).

Глава 2. РАЗРЕШИМОСТЬ ПРОБЛЕМ СТЕПЕНИ И КОРНЯ В ГРУППАХ

С УСЛОВИЕМ С(4)&Т(4).

Глава 3. ТРАНСЛЯЦИОННЫЕ ЧИСЛА В ГРУППАХ С УСЛОВИЕМ

С(4)&Т(4).

§1. Предварительные сведения.

§2. Доказательство основного результата.

Глава 4. ПРОБЛЕМА СТЕПЕННОЙ СОПРЯЖЕННОСТИ В ГРУППАХ С

УСЛОВИЕМ С(4)&Т(4)&Р/с и С(5)&Т(4).

§ 1. Проблема слабой степенной сопряженности в группах с условием

С(4)&Т(4).

§2. Проблема степенной сопряженности в группах с условием

С(4)&Т(4)&Р*.

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

С(5)&Т(4).

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

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

П.С. Новиковым в работах, связанных с исследованием проблемы равенства была доказана неразрешимость проблемы равенства слов в конечно определенных группах [10], им же доказана неразрешимость проблемы изоморфизма групп. Примеры конечно определенных групп с неразрешимой проблемой равенства были также даны Буном в работе [19].

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

С.И. Адяном определено понятие наследственного нетривиального свойства группы и доказано, что не существует алгоритма, позволяющего для произвольной конечно определенной группы распознать выполнимость некоторого свойства, представляющего собой объединение нетривиального наследственного и инвариантного свойства, если только существуют группы, обладающие этим свойством [1]. Из этого результата следует, что практически все проблемы, относящиеся к конечно определенным группам, в общем случае неразрешимы.

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

Долгое время практически единственным классом конечно определенных групп (кроме матричных групп) с разрешимой проблемой равенства был класс групп с одним определяющим соотношением. Для этого класса проблема равенства была полностью решена Магнусом в 1932 году [33].

Другим классом конечно определенных групп с разрешимой проблемой равенства является класс групп с малыми сокращениями определяющих слов. Пусть группа G задана своим представлением G = (X;R). Пусть X - конечный алфавит, содержащий символы \ i е 1, . ,п. Конечное множество R циклически несократимых слов в алфавите X назовем симметризованным, если вместе с каждым словом г е R слово r1e R и все циклически перестановки слов r±l также содержатся в R. Общее начало двух различных слов из R назовем куском.

Рассматриваются следующие условия малого сокращения:

1) Условие С'(А-), 0 < X < 1 - длина любого куска меньше X от длины соответствующего определяющего соотношения;

2) Условие C(p),pelk. Никакой элемент из R не является произведением менее чем р кусков.

3)Условие T(q), qeVi. Пусть 3 <h<q. Для любого набора слов rh . из R, таких, что последовательные элементы гг, гг+1 не являются взаимно обратными, по крайней мере, одно из произведений Г\Г2, . . ., Г[,.\Ги, Г},Г\ приведено.

Заметим, что из условия С(—) следует условие С(р+1). Р

Изучение групп с малым сокращением, появившихся в работах М. Дэна, началось в конце сороковых годов. Идеи М. Дэна о малых сокращениях были применены В.А.Тартаковским к решению проблемы равенства слов для конечно определенных факторгрупп свободных произведений циклических групп по множеству определяющих соотношений R, удовлетворяющему условию С(7) [14], [15], [16]. Используя идеи В.А. Тартаковского, М.Д.Гриндлингером были определены классы групп с условием малого сокращения и решены проблемы

1 1 равенства и сопряженности слов в классе С'(—) и С( —)&Т(4) [27], [28].

6 4

Из результата Линдона о положительном решении проблемы равенства в классе групп с условием С(6) следует разрешимость данной проблемы в группах с условием С I") [30]. А.И. Гольдбергом [7] было доказано, что любая конечно определенная группа допускает представление, в котором длина каждого 1 куска не превышает — длины соотношения, отсюда следует, что класс групп с условием является предельным. Группы с условиями С(6), С(4)&Т(4) и

С(3)&Т(6), являющиеся обобщением класса групп с условием малого сокращения С '(X), были введены Линдоном и для них им была решена проблема равенства слов [8].

Шупп показал, что класс групп с малым сокращением и разрешимой проблемой сопряженности также широк, как аналогичный класс относительно проблемы равенства, в частности, он содержит группы с условием [37]. В работе [21] Комерфорд показал, что в группах с условиями малого сокращения подгруппы конечного индекса наследуют свойство иметь разрешимую проблему сопряженности.

Герстеном и Шортом было введено понятие биавтоматных групп и доказано, что в биавтоматных группах разрешима проблема равенства и сопряженности. Показано, что группы с условиями C(p)&T(q) при (p,q) е {(3,6), (4,4), (6,3)} являются биавтоматными [25], [26].

Применение свободных конструкций не сохраняет разрешимости проблемы равенства, а значит, и проблемы сопряженности; в ряде работ изучались достаточные условия, при которых такое условие все же имеет место. Коммер-форд и Трюффо доказали, что в свободном произведении групп, удовлетворяющих условию С(~), объединенных по циклической подгруппе, разрешима 6 проблема сопряженности [23].

Обобщением проблемы сопряженности является проблема степенной сопряженности: существует ли алгоритм, выясняющий по двум произвольным групповым словам w, v от порождающих элементов группы, существуют ли ненулевые целые числа п, т такие, что слова w'\ vm представляют сопряженные элементы группы.

В ряде работ Мак-Кула, Комерфорда, Липшуца рассматривались следующие алгоритмические проблемы:

Проблема порядка: каков порядок элемента?

Проблема степени: входит ли элемент в данную циклическую подгруппу? Проблема корня: извлекается ли из элемента нетривиальный корень? Для групп с условием C(p)8iT{q)&cP, где условие Р означает, что все куски имеют единичную длину эти проблемы решены И. Каповичем [29].

В группах с условием С'(—) разрешимость проблем порядка, степени и 6 корня была доказана Липшуцом [31]. Им же доказано, что для любой пары взаимно простых чисел т, п существует рекурсивно определенная группа, в которой проблема извлечения корня т-ой степени разрешима, а п-ой степени - нет [32].

Мак-Кулом доказана разрешимость проблемы степени в группах с одним соотношением [34]. Им доказано существование групп с разрешимой проблемой равенства и неразрешимыми проблемами порядка и степени [35].

Для групп с условиями C(p)&T(q), (p,q) е {(3,6), (4,4), (6,3)} Баглеем и Прайдом решена проблема порядка [18].

Результат Аншела и Стиба, доказавших проблему сопряженности для степеней элементов в свободном произведении групп с условием Сг(-), объе8 диненных по циклической подгруппе [17], был усилен Комерфордом в работе

22]. Им доказывается, что для свободного произведения групп с условием

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

Для групп с условием С(6) проблемы порядка, степени и корня положительно решены Н.В. Безверхним, также решена проблема степенной сопряженности для групп с условием С(6)&Д, где условие означает, что все куски имеют одинаковую длину, равную к [6].

В данной работе для групп, удовлетворяющих условиям С(4)&Т(4) решены следующие проблемы:

• Проблема порядка.

• Проблема степени.

• Проблема корня.

• Проблема степенной сопряженности.

• Показано, что группа G, удовлетворяющая условиям С(4)&Т(4) является строго трансляционно дискретной.

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

Пусть группа G имеет копредставление G — (X;R), где R симметризованное множество; пусть F - свободная группа с базисом X, N - нормальное замыкание множества R в F. Если элемент w из F равен единице в G, то weN тогда и только тогда, когда w - щхг{~1щ щ1г2±1м2. и~хг^хип в свободной группе, где г. eR при i = 1, . . . , п. Согласно теореме Ван Кампена существует связная одно-связная диаграмма над R с граничной меткой равной w [8].

Диаграммы являются эффективным инструментом при изучении таких вопросов, как равенство элемента единице, сопряженность двух элементов или их степеней и других. Диаграммы впервые появились в работах ван Кампена [40], но применение нашли только через 30 лет. В 1966 году диаграммы были переоткрыты Линдоном [30], который с их помощью изучал теорию малых сокращений уже геометрическими методами.

Конечное симметризованное множество R удовлетворяет условию С(4)&Т(4), если выполняются следующие условия:

1)Условие С(4). Никакой элемент из R не является произведением менее чем четырёх кусков.

2)Условие Т(4). Пусть 3 < h < 4. Рассмотрение такого неравенства продиктовано лишь строгостью соблюдения условия малого сокращения Т(q), приведенного выше, и в нашем случае h = 3. Пусть г\, . . . , г/г - элементы из R, такие, что последовательные элементы гъ г,ц не являются взаимно обратными. Тогда, по крайней мере одно из произведений г\г2, . . . , rh-\fh, Wi приведено. П

Для групп с условием С" — &Т(4) Липшуцом было дано следующее W описание элементов: элемент w такой группы либо 1) имеет конечный порядок, либо 2) бесконечный порядок, причем от слова w можно перейти к слову w0, любая степень которого ^-несократима, либо 3) элемент w имеет бесконечный порядок, но слово w2 ^-сократимо, тогда можно перейти к слову w0, сопряженному слову w2, любая степень которого ^-несократима

В главе 1 приводятся понятия дэновской области, полосы, вводится понятие R, R -несократимого слова и доказывается аналог теоремы Липшуца для рассматриваемого класса групп. Первой решается проблема порядка.

Теорема 1.1. Пусть G = (X; К) - группа с условием С(4)&Т(4), w - циклически приведённое слово в алфавите X, п - его порядок в группе G, причём пфО, пф\. Тогда в R существует слово вида s\ где t> I, s - слово в алфавите X, такое, что слова / и/ сопряжены в группе G при некоторых 1 <р< ^ и 1 < к <2.

Следствие 1.1.1. Существует алгоритм, позволяющий по слову w определить, конечен ли его порядок в группе G.

Данное утверждение было доказано ранее Баглеем и Прайдом другими методами [18]. Методы, разработанные автором при доказательстве теоремы 1.1, позволяют получить основные результаты диссертации.

Геометрический подход позволил использовать числовые неравенства, вытекающие из условий малого сокращения. Примерами таких неравенств являются формула кривизны [8] ( ]Г[3 - /(D)] > 4), используемая для доказательном ства важного вспомогательного результата; а также теорема о площади [8] (| М ' Y

4 -/(D)] ), используемая для решения проблемы степенной сопря

DeM I -4 женности в данном классе групп. Здесь i(D) - число неориентированных внутренних ребер области D диаграммы М,\М| - число областей диаграммы М. Точки над знаками сумм означают, что суммирование ведётся только по граничным областям диаграммы.

Для элементов бесконечного порядка доказывается следующая теорема: Теорема 2.1. Существует алгоритм, строящий по любому циклически несократимому слову w, представляющему в группе G = (X;R) с условием С(4)&Т(4) элемент бесконечного порядка, сопряженное с wk, к < 2 в группе G слово wq, любая степень которого R, R - несократима.

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

Теорема 2.2. Пусть М - приведенная диаграмма, являющаяся диском (граничный цикл (дМ) - простая замкнутая кривая), divl = y^S, пусть (fiy), (fid) -R,R - несократимые слова. Тогда число областей, граничащих с /и д, одинаково.

Основным результатом второй главы является

Теорема 1.2. В группах с условием С(4)&Т(4) разрешима проблема вхождения в циклическую подгруппу.

Заметим, что согласно теореме Рипса в общем случае проблема вхождения в данном классе групп не разрешима [36].

Следствие 1.2.1. В группах с условием С(4)&Т(4) разрешима проблема корня. То есть по данному слову w е G можно определить существуют ли такие п е М{1} и v е G, что w = vn в группе G.

Следствие 2.1.2. В группе G с условием С(4)&Т(4) любая возрастающая последовательность циклических подгрупп стабилизируется.

Для пояснения основного результата третьей главы дадим несколько определений.

Каждый элемент geG может быть представлен как произведение g = л;^1 Xj1. хгде Xj е X, i е . . ., п. Минимальное п с таким свойством назовем Х-длинной элемента g и обозначим l^g).

Тогда для любого geG определим трансляционное число элемента g отlx(gn) носительно X как предел тх (g) = lim —-. я-> 00 Yl

Герстеном и Шортом доказано, что этот предел всегда существует [25]. Ими же показано, в частности, что постоянно на классе сопряженных элементов группы G. Определим трансляционное число класса сопряженности а следующим образом тх(а) ~ Tx(g), где g - некоторой элемент класса а.

Группа G строго трансляционно дискретна, если она трансляционно сепарабельна (любой элемент с трансляционным числом 0 имеет конечный порядок) и для любого конечного порождающего множества X и для любого вещественного числа г количество классов сопряженности а таких, что тх(а) < г, конечно.

Основным результатом третьей главы является

Теорема 1.3. Пусть G = (.X.; R) - конечно определенная группа с условием С(4)&Т(4). Тогда G строго трансляционно дискретна.

Тем самым усилен результат И. Каповича, доказавшего то же утверждение для групп с условием С(4)&Т(4)&Р, где условие Р означает, что все куски относительно представления G = {Х\ R) имеют единичную длину [29].

Четвертая глава посвящена проблемам степенной сопряженности в группах с условием С(4)&Т(4)&Р/с и С(5)&Т(4).

Сначала доказывается алгоритмическая разрешимость проблемы слабой степенной сопряженности в группах с условием С(4)&Т(4).

Теорема 1.4. В группе G с условием С(4)&Т(4) алгоритмически разрешима проблема слабой степенной сопряженности, то есть по любым словам w, v е G можно выяснить, существует ли целое число п такое, что слова W, v сопряжены в группе G.

Далее определяется класс групп с малыми сокращениями с дополнительным условием Pk. Будем говорить, что группа G = (X; R) с условием С(4)&Т(4) удовлетворяет условию Р/(, если всякое разбиение любого определяющего отношения на минимальное число кусков содержит только куски длины к. Для групп с условием С(4)&Т(4)&Р/с доказан следующий результат

Теорема 2.4. Пусть М - приведённая кольцевая диаграмма сопряженности циклически R,R- несократимых слов w2n, v~2m . дМ=сти г, (fid) = w2", f{r) =v~2m. Тогда, если в М есть область 1) такая, что /(D) = 2, то существует константа С, зависящая только от длин слов w, v и от длин определяющих соотношений в симметризованном множестве R, удовлетворяющем условиям С(4)&Т(4)&Р/с, такая, что п,т<С.

При доказательстве теоремы 2.4 получается один интересный факт.

Пусть все степени слов w, v R,R- несократимы и слова wn, vm сопряжены в группе G, причем числа и, т минимальные с таким свойством.

Пусть Мо - простая диаграмма сопряженности слов w2n, v~2m, Мо = (uKi)u(Kj/i), где К, - дисковые поддиаграммы в Мо, a yj~ соединяющие их простые пути. дМ0 = оо и То. Пусть Ка = (J/3 , М\ = М0 \Ка, . , А/, = Mh

DeM0,dDr>dM*

К(Т ^ . Кольцевая диаграмма имеет толщину h, если |Ка | = 0, |I ^ 0. Тогда пусть при указанных выше условиях диаграмма имеет толщину h > , тогда площадь любого диска К а Мо удовлетворяет неравенству:

N1

IКI >----, где N - число граничных областей диска К.

2(|v|max|wz-|)

В последнем параграфе третьей главы для класса групп с условием С(5)&Т(4) доказана следующая

Теорема 3.4. В группах с условием С(5)&Т(4) алгоритмически разрешима проблема степенной сопряженности слов.

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

Все результаты диссертации опубликованы в работах [4], [5], [13], [41] и докладывались на алгебраическом семинаре А.Л. Шмелькина, А.Ю. Ольшанского (МГУ, 2001 г.), на алгебраическом семинаре под руководством В.Н. Безверхнего (ТГПУ, 1998-2001гг.).

1. Адян С.И. Неразрешимость некоторых алгоритмических проблем в теории групп // Труды Мое. мат. об-ва. 1957. Т.6 с.231-298.

2. Безверхний В.Н. О нормализаторах элементов в С(р)&Т(д)-группах. Алгоритмические проблемы теории групп и полугрупп. Межвузовский сборник научных трудов. Тульский гос. пед. ун-т им. Л.Н.Толстого, 1994, с.4 58.

3. Решение проблемы сопряженности слов в некоторых классах групп. Алгоритмические проблемы теории групп и полугрупп. Межвузовский сборник научных трудов. Тула, 1990. 2.

4. Проблема степенной сопряженности в группах с условием С(4)&Т(4)&Д, С(5)&Т(4). Алгоритмические проблемы теории групп и полугрупп. Межвузовский сборник научных трудов. Тула: Изд-во Тул. гос. пед. ун-та им. Л.Н.Толстого, 2001, с. 120 - 139.

5. Безверхний Н.В. Проблемы степени и степенной сопряженности в группах с малыми сокращениями. Диссертация на соискание ученой степени кандидата физико-математических наук. Москва, 1999.

6. Гольдберг А.И., О невозможности усиления некоторых результатов Гринд-лингера и Линдона. Успехи мат. наук, 1978, 33, №6, с.201 202.

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

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

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

10. Новиков П.С., Адян С.И. Проблема тождества для полугрупп с односторонним сокращением. Z. math. Log. und Grundl. Math., 1958, 4, №1, с.66 88 (РЖМатю 19596 4361).

11. Ольшанский А.Ю. Геометрия определяющих соотношений в группах. М: Наука, 1989.

12. Паршикова Е.В. Проблема слабой степенной сопряженности в группах с условием С(4)&Т(4). Алгоритмические проблемы теории групп и полугрупп. Межвузовский сборник научных трудов. Тула: Изд-во Тул. гос. пед. ун-та им. Л.Н.Толстого, 2001, с. 179 - 185.

13. Тартаковский В.А. Решение проблемы тождества для групп с /г-сократимым базисом при к > 6. Изв. АН СССР. Сер. мат., 1949, 13, с.483 494.

14. Метод решета в теории групп. Мат. сб., 1949, 25, с.З 50.16. -, Применение метода решета к решению проблемы тождества в некоторых типах групп. Мат. сб., 1949, 25, с.251 274.

15. Anshel М., Stebe P. Conjugate powers in free products with amalgamation. Houston J. Math., 2 №2, p. 139 147.

16. Bogley W.A., Pride P., Aspherical relative presentations, Pros. Of the Edinburg Math. Soc., 1992, 35, p. 1 -39.

17. Boone W.W. Certain simple, unsolvable problems of group theory. V, VI. Proc. Kon. ned. akad. wetensch., 1957, A60 №1, 22 27; №2, c.227 - 232; Indag. math., 1957, 19, №1, 22 - 27; №2, p.227 - 232 (РЖМат, 1959, 78).

18. Britton J.L. Solution of the word problem for certain types of groups. I, II. Proc. Glasgow Math. Assoc., 1956, 3, №1, c.45 54; №2, p.68 - 90.

19. Comerford L.P. Subgroups of small cancellation groups. J. London Math. Soc., 1978, 17, №3, p.422 424.22. -, A note on power-conjugacy. Houston J. Math., 1977, 3, №3, p.337-341.

20. Comerford L.P. Truffault B. The conjugacy problem for free products of six-groups with cyclic amalgamation. Math. Z., 1976, 149, №2, p.169 181.

21. Gersten S., Short H. Rational subgroups of biautomatic groups, Ann. Math., 134 (1991), p.125-158.

22. Small cancellation theory and automatic groups, Inven. math., 102 (1990), p.305 334.

23. Part II, Inven. math., 105 (1991), p,641 - 662.

24. Greendlinger M. Dehn's algorithm for the word problem. Commun. Pure and Appl. Math., 1960, 13, №1, p.67 83.

25. On Dehn's algorithms for the conjugacy and word problems, with applications. Commun. Pure and Appl. Math., 1960, 13, №4, p.641 677.

26. Kapovich I., Small cancellation groups and translation numbers, Amer. Math. Soc., V. 349, № 5, may 1997, 1851

27. Lyndon R.C. On Dehn's algorithm. Math. Ann., 1966, 166, №3, p.208 228.

28. Lipschutz S. On Greendlinger groups. Commun. Pure and Appl. Math., 1970, 23, №5, p.743 747.

29. Lipschutz S, Lipschutz M. A note on root decision problems in groups. Can. J. Math., 1973, 25, №4, p.702 705.

30. Magnus W. Das Identitatsproblem fur Gruppen mit einer definieren den Ralation. Math. Ann., 1932, 102, p.295 307.

31. McCool J. Unsolvable problems in groups with solvable word problem. Can. J. Math., 1970, 22, №4, p.836 838.

32. The power problem for groups with one defining relator. Proc. Amer. Math. Soc, 1971, 28, №2, p.427 - 430.

33. Rips E. Subgroups of small cancellation groups. Bull London Math. Soc., 1982, 14, p.45-47.

34. Schiec H. Ahnlichkeitsanalyse von Gruppenrelationen. Acta math., 1956, 96, №3 4, p.157 - 252.

35. Schupp P.E. On Dehn's algorithm and the conjugacy problem. Math. Ann, 1968, 178, №2, p.119 130.

36. Turing A.M. The word problem in subgroups with cancellation. Math. Ann, 1950, 52,p.491 -505.40. van Kampen E.R., On some lemmas in the theory of groups. Amer.J.Math, 1933, V.55, p.268 273.

37. Паршикова E.B. Трансляционные числа в группах с условием С(4)&Т(4). Тезисы докладов Всероссийской научной конференции «Современные проблемы математики, механики и информатики». Тула: ТулЕУ, 2001. с.71-72.рис.1рис.2рис.3Е