Содержание к диссертации
Введение
1 Описание алгоритма построения группы В(т,п) 12
1.1. Понятие слов в В(гп,п) и отношение порядка на них 12
1.2. Построение Ks{rn,n) 14
1.3. Условие конечности группы В(т,п) 20
2 Реализация алгоритма на известных группах бернсаидового типа 22
2.1. Группа В(2,3) 22
2.2. Группа (2,4) 36
2.3. Группа В(3,3) 50
3 Группа В{2,5) 60
3.1. Построение Ki(2,b) 60
3.2. Построение Л"2о(2,5) 61
3.3. Об одном коммутаторе в В(2,5) 66
4 К вопросу о распознавании группы L2{7) по спектру 69
5 Компьютерная реализация алгоритма 77
5.1. Реализация алгоритма на языке MATLAB 7 77
5.2. Реализация алгоритма на языке FORTRAN 90 81
Список литературы 97
Введение к работе
Актуальность темы. Комбинаторную теорию групп можно охарактеризовать как теорию групп, которые описываются порождающими и определяющими соотношениями, где в качестве модели используется модель, известная как "комбинаторика слов". Как самостоятельная наука со своей проблематикой она оформилась по существу только после того, как в 1911 г. М. Дэн сформулировал основные алгоритмические проблемы теории групп: проблему распознавания равенства, известную в литературе также под названием "проблема тождества", проблему сопряжённости и проблему изоморфизма. Ученику М. Дэна, В. Магнусу, принадлежит также существенный вклад в исследовании такой важной проблемы теории групп — проблемы Бернсайда [23] о периодических группах, поставленной в 1902 г.: Будет ли конечной группа с т порождающими и тождественным соотношением хп — 1? Намеченный Магнусом в его работах (начиная с 1935 г.) подход к исследованию проблемы Бернсайда привёл в 1950 г. к формулировке новой проблемы, которая в нашей литературе известна под названием "ослабленная" проблема Бернсайда [29]: конечно ли число конечных т порождённых групп периода п? По элементарной теореме Пуанкаре это означает существование универсальной максимальной конечной группы Ва(т,п). Подход Магнуса лежит в основе доказательства полученных в дальнейшем результатов по этим проблемам. Группа
В(т,п) = $/$", т>1, которая получается факторизацией свободной группы 5 = 5(m) с т ^~ разующими по нормальной подгруппе З71, порождённой n-ми степенями всех элементов из $, называется сейчас свободной бернсайдовой груп- пой показателя (или периода) п.
Её конечность, установленная в разное время для п — 2 (тривиальный случай), п — 3 (Бернсайд У.), п = 4 (Бернсайд У. для т = 2; Санов И.Н. [20] для произвольного т), п = 6 (Холл М. [25]), была поставлена под сомнение при п > 72 П.С. Новиковым в его заметке [16]. Отрицательное решение проблемы Бернсайда было получено впервые лишь в 1964 году Е.С. Голодом [4,5] на основе универсальной конструкции Е.С. Голода — И.Р. Шафаревича. Позднее СВ. Алешиным [2], Р.И. Гри-горчуком [6], В.И. Сущанским [21] была предложена целая серия отрицательных примеров. Доказательство бесконечности группы В(т,п), т > 2, для нечётных показателей п > 4381 было дано в работе П.С. Новикова - СИ. Адяна [17], а для нечётных п > 665 — в книге СИ. Адяна [1]. Гораздо более доступный и геометрически наглядный вариант доказательства для нечётных п > ДО10 был предложен А.Ю. Ольшанским [18], который впоследствии [19], на основе усовершенствованного метода, построил для каждого достаточно большого простого числа р бесконечную р-группу, все собственные подгруппы которой имеют порядок р. В работах СВ. Иванова [27] и И.Г. Лысёнка [13] показано, что для достаточно больших чётных, п группа В(т,п) также бесконечна (у Иванова п > 248 и п делится на 29, у Лысёнка n = 16& > 8000).
Вопрос о существовании универсальной конечной группы В0(т,п) приобрел права гражданства в начале 40-х годов после работ В. Магнуса [30-33], О. Грюна [24], Г. Цассенхауза [39], Р. Бэра [22]. Именно тогда в случае простого показателя п = р была получена редукция теоретико-групповой задачи о существовании Во(т, п) к вопросу о локальной нильпотентности алгебры Ли L над Zp, удовлетворяющей тож- дественному соотношению [tw*-1] = [... [[«, v], v],..., v]-0 (условию ЭнееляЕр-i). Результаты не замедлили сказаться: существование Во(2,5) было установлено в 1955 г. [9], В0(т, 5) — в 1956 г. [10,26], В$(т,р) — в 1958 г. [11]. Окончательное положительное решение ослабленной проблемы Бернсайда для любых тип было получено Зель-мановым. Естественно, возник вопрос о совпадении групп В${гп,п) и В(т,п). Как отмечено выше, Во(го,п) = В(т,п) для п = 2,3,4,6. Во(т,п) ф В(т,п) для нечётных п > 665 и для чётных п [п > 248 и п делится на 29,n = 16k > 8000).
Общая идея алгоритмической комбинаторики от Евклида и до наших дней — представить основные алгебраические структуры в виде объектов, поддающихся вычислительной обработке, и ответить на два основных вопроса: что такое вычисление математического объекта; как его вычислить наиболее эффективно.
В рамках этой концепции машинный эксперимент по группам В(т, п) внушителен. Большинство работ в этом направлении используют комбинаторно-перечислительные методы в коммутаторном исчислении, базирующиеся на конструкциях алгебры Ли [38]. Следует сказать о различных постановках проблем бернсайдового типа (А.Г. Курош) [12]. Так, В.В. Блудов [3] изучает группы показателя 4, А.И. Скопин [28,35,36] — показателей 8, 9, 16, 25, 27 и др.
Цель диссертации. Цель диссертации — создать комбинаторный алгоритм для вычисления элементов и соотношений в бернсайдовых и других периодических группах и проиллюстрировать его эффективность для доказательства конечности указанных групп.
Основные результаты диссертации:
Создан алгоритм, основанный на комбинаторике слов, для вычисления элементов и соотношений в бернсайдовых и других периодических группах и его реализации на языках MATLAB 7 и FORTRAN 90.
Найден критерий (теорема 1) конечности группы В(т,п), основанный на комбинаторной структуре данного алгоритма.
Для группы В{2,5) получено: раннее неизвестный список соотношений С2о(2,5) (табл. 3.3.) для всех слов, не превосходящих по длине 20; с учётом полученного списка соотношений из а) вычислен коммутатор специального вида а12(0,1), который является критерием конечности группы В(2,5) снизу.
4. Доказана теорема 10, которая редуцирует проблему распознаваемо сти 1-2(7) к группам, порождённым инволюциями.
Методы исследования. Применяются методы дискретной математики, включая методы комбинаторной теории групп, а также теории комбинаторных алгоритмов.
Научная новизна. Все основные результаты диссертации являются новыми.
Теоретическая значимость и практическая ценность. Результаты, из- -* ложенные в диссертации, имеют теоретическое значение и могут быть использованы как в дальнейших исследованиях в комбинаторной теории групп, так и при чтении специальных курсов по дискретной математике и'алгебре.
Структура и объём работы. Диссертация состоит из введения и пяти g глав основного текста. Список литературы состоит из 50 наименований.
Работа изложена на 102 страницах текста.
Апробация, Результаты диссертации докладывались автором на Второй Всероссийской научной конференции "Проектирование инженерных и научных приложений в среде MATLAB" в 2004 г. в г. Москве, "Маль-цевских чтениях" 2004, 2005 гг., на XLII Международной научной студенческой конференции в 2004 г. "Студент и научно-технический прогресс", проходившей в г.Новосибирске, Международной конференции, посвященной 75-летию со дня рождения профессора А.И. Кокорина * "АЛиК-2004", проходившей в г. Иркутске, VI Международной конфе- ренции "Дискретные модели в теории управляющих систем" в 2004 г. в г. Москве, Международной алгебраической конференции посвященной 100-летию со дня рождения П.Г. Конторовича и 70-летию Л.Н. Шеврина, в 2005 г. в г. Екатеринбурге. Они неоднократно обсуждались на семи- «, нарах в Красноярском государственном университете, Красноярском го- сударственном аграрном университете и Красноярской государственной архитектурно-строительной академии.
Публикации. Основные результаты по теме диссертации опубликованы в [40]- [50].
Содержание диссертации
Как отмечалось выше, большинство численных экспериментов по проблеме Бернсайда связаны с конструкциями алгебры Ли. В настоящей диссертации предложен комбинаторный алгоритм, доказывающий конечность группы В(т,п), основанный на её комбинаторной структуре.
В главе 1 описан алгоритм, который позволяет представить В(т,п) в виде предела последовательности объектов К3(т,п). Объект Ks(m,n) — {P3,AS,CS,T3} представляет собой множество всех слов группы Бернсайда Р3, не превосходящих по длине s, с заданной на этом множестве таблицей умножения Т3, обрабатывая которую при помощи алгоритма Л3, мы получаем список соотношений Cs.
В результате работы алгоритма строится последовательность объ ектов К\,К2...,KS, Она обладает тем свойством, что если группа бесконечна, то её "предел" при s, стремящемся к бесконечности, равен группе В(тп,п). Если же K3(m,n) = Ks+i(m,n), то имеет место приводимая ниже теорема, которая даёт критерий конечности группы В(т,п).
Теорема 1. Пусть s є N и s наименьшее со свойством Ks(m,n) = Ks+i(m,n), тогда \В(т,п)\ < \Р3(т,п)\,
В главе 2 показана реализация алгоритма на известных конечных группах В(2,3), В(2,4) и В(3,3). Приведённые результаты полностью согласуются с известными данными об этих группах. Кроме того, доказаны следующие теоремы;
Теорема 2. Объект К$(2,3) изоморфен группе В(2,3).
Теорема 3. Пусть группа G =< х,у\х3 — у3 = l,yxyx = ххуу, ххухх = уухуу.уухх = хуху}уухух = хууху,хуух = ухху >, тогда группа G изоморфна группе В(2,3).
Теорема 4. Объект К2$(2,А) изоморфен группе 5(2,4).
В работе найден список соотношений С объекта if2o(2,4), такой, что имеет место
Теорема 5. Пусть группа G =< х, у\хА = у4 = 1, С) >, тогда группа G изоморфна группе 5(2,4).
Теорема 6. Объект /Сі2(3,3) изоморфен группе 5(3,3).
В работе найден список соотношений С\ объекта /Сі2(3,3), такой, что имеет место
Теорема 7. Пусть группа G —< х,у,г\хъ = уг = гъ — \,С\ >, тогда группа G изоморфна группе 5(3,3).
Теоремы 3,5,7 характеризуют группы 5(2,3), 5(2,4) и 5(3,3) в классе всех групп через порождающие и соотношения.
В главе 3 приведены численные результаты по доказательству конечности группы 5(2,5). Построен объект /С2о(2,5), порядок которого сопоставим с 59, а также приведена статистика данного объекта. Рассмотрена динамика изменения коммутатора аі2(0,1) = [...[[0,1],0]1...1]0] в зависимости от получаемых соотношений на каждом шаге. Приведён список соотношений для группы 5(2,5).
В главе 4 изучается один из вопросов, сформулированных В.Д. Мазуровым в [14]: распознаваема ли группа L2(7) по спектру в классе всех групп?
Основным результатом главы 4 является теорема 10, в которой доказывается, что проблему распознаваемости достаточно решить для групп, порождённых инволюциями.
Теорема 10. Если для произвольной группы М, порождённой инволюциями и удовлетворяющей условию ш(М) = w(L2(7)), выполняется М = //2(7), то и для произвольной группы G, со свойством u(G) = ш(Ь2(7)), выполняется G = L2(7).
Для доказательства теоремы 10 была использована Теорема 9. Пусть М — группа и а)о;(М)Со;С^2(7))-{1,2,3,4,7}; /3) произведение любых двух инволюций из М есть 2-элемент, т.е \/v,w Є М \vw\ = {1,2,4}, если \v\ — \w\ — 2.
Тогда М — расширение 2-группы посредством примарной группы.
В свою очередь, для доказательства теоремы 9 была использована
Теорема 8. Пусть М — {хі,х2,хз | х\ = х\ = х\ = е) — группа, порождённая тремя инволюциями х\, х2, х$ и: a) w(M) С 07(^(7)) = (1,2,3,4,7}; (3) произведение любых двух инволюций из М есть 2-элемент, т.е Vu.wgM \vw\ = {1,2,4}, если \v\ — \w\ = 2.
Тогда \М\ < 210 и ш(М) = {1,2,4}.
Следует отметить, что для доказательства теоремы 8 использовались компьютерные вычисления, базирующиеся на алгоритме из главы 1, а также комбинаторный анализ множества возможных соотношений для указанной группы.
В главе 5 для алгоритма из главы 1 приведены тексты программ, написанных на компьютерных алгоритмических языках MATLAB 7 и FORTRAN 90.
Во время работы над диссертацией автор получал поддержку Российского фонда фундаментальных исследований (грант № 03-01-00905).
Автор выражает благодарность научным руководителям профессору А.К. Шлёпкину и профессору Г.П. Егорычеву за постановку задачи, помощь в работе и внимание с их стороны. Также автор выражает благодарность С.А. Тарасову за помощь при написании программы на языке FORTRAN 90.
Построение Ks{rn,n)
Положим по определению — множество слов из В(т:п), имеющих длину 1 и упорядоченных относительно введённого в п. 1.1. порядка " " меньше. Заметим, что Pi есть упорядоченное множество образующих. 2) Определение алгоритма А\. Aj — алгоритм п-апериодичности, который преобразует любое слово w є V(m) в n-апериодическое слово v. Опишем работу данного алгоритма. 1. Задаём исходное слово w. 2. Вычисляем длину слова w : S(w) — I. a) Если I п, то слово w заведомо является п-апериодическим, следовательно w = v. Алгоритм завершён. b) Если I п, то тогда задаем п последовательно идущих в w слов xi,x2,...,Xk,...,xn одинаковой дли w — px\x2... Xk ... xnq. Длину и месторасположение слов хи (к = 1,...,п) в слове w можно задать исчерпывающим образом посредством двух параметров г и j, где: j — 1,2,...,[] ([-] — целая часть от отношения ) — параметр, задающий длину слов хк , г = 1,2,..., (J — jn + 1) — параметр, задающий месторасположение слов fc в слове w. Таким образом: 3. Задаём начальное значение значение длин слов х : У = 1. 4. Задаём начальное месторасположение слов х& і = 1 (при г = 1 последовательность слов начинается с начала слова w, т.е. w — х\.. . хпд. 5. Сравниваем слова а : х\ = х% = — хп ( ). a) Если ( ) выполняется , то слово w сокращается, т.е. w = рх\... xnq — in = pq. Возвращаемся в пункт 2. b) Если ( ) не выполняется, делаем проверку неравенства г (i-jn + 1) ( ). 6. а) Если ( ) выполняется, то увеличиваем значение параметра г на единицу г = г + 1, смещая тем самым слова #ьна один индекс вправо вдоль w. Затем возвращаемся к пункту 5. Ь) Если ( ) не выполняется, делаем проверку неравенства j [ ] 7. а) Если ( ) выполняется, то увеличиваем значение параметра j на единицу j = j + 1, увеличивая тем самым длины слов х на единицу. Затем возвращаемся к пункту 4. Ь) Если ( )не выполняется, то это означает, что слово w п-апериодическое, т. е. w = v. Алгоритм завершен.
Это означает, что слова vioVj и vioVk равны как элементы группы, поэтому Пусть для определённости Vj vk отностительно отношения " ". Поэтому, считая по определению С8 = Cs-i = {ci,c2,... ,Cr-i} и Or = {VJ — Vk], полагаем Далее, строим алгоритм A — ЛІ A . Рассмотрим работу алгоритма Ay. По индукции Аа — Ai А АСг_1. Опишем подробно действие А\ на все слова у Є В(т,п),записав Cs в следующем виде: 1. у — А\{у) — n-апериодизируем слово у и введём параметр к, который указывает номер соотношения в списке соотношений Cs \ 3. Делаем проверку у pwkq ( ): а)если ( ) выполняется, то у = pv q. Возвращаемся в пункт 1. б)если ( ) не выполняется, то делаем проверку к г — 1 ( ). 4. Если ( ) выполняется, то к = fc + І, возвращаемся в пункт 3. В том случае, если ( ) не выполняется алгоритм Ав завершает работу. Таким образом: Затем, домножая АІ на А , получим АІ , который действует на все слова у Є В(тп,п) следующим образом: Далее применяя алгоритм As} ко всем словам из Р\ \ получим Ps \ инвариантную относительно As. Заметим, что, так как PJ инва-ринтна относительно АІ \ то PJ J достаточно проверить алгоритмом А . Таким образом, если любое слово у из Ps равно pwrq, то данное слово нужно удалить из РІ по той причине, что оно будет графически рав- г»(1) но, какому-то слову уа, находящемуся раньше в последовательности ry \ Действительно, АСг(у) = ACr(pwrq) = pvrq = у0 pwrq. В результате, получим: то список соотношении Cs пополнится новым соотношением Cr+1 = {vm - vi}, т.е.
Вслед за изменением списка соотношений, изменятся также алгоритм, последовательность и таблица умножения (Ав А3\ рР AJLI ря(з) И Т№ л] т ) Данный процесс будет продолжаться до тех пор, пока при каком- то z таблица умножения Ts станет инвариантной относительно алгоритма Аз , т.е. в Tf не найдётся ни одной строки iQ, такой что Когда это будет выполнено, мы получим, что Ps = Ps, As — As, C(sz) = Csw TP = Ts. Таким образом объект Ks{m,n) = {Ps, А3,Г5,С5} построен. 1.3. Условие конечности группы В(тп,п) Теорема 1. Пусть s Є N и з наименьшее со свойством Ks(m}n) — Ks+i(m;n)t тогда Доказательство. Поскольку то Ps — P3+i — Ps+2 = — Другими словами, для любого слова w, As(m,n)(w) — v Є Р3. Возьмём произвольный элемент g В(т,п). Запишем его в виде произведения свободных порождающих, т.е. g — а\ с 2 . otT, где а{ Є {xi,x2,... ,m}. Рассмотрим слово v\ = ai -а2...аг- Применим алгоритм А3 к слову v\. A3(vi) = Aa(oti а2...аг) = v = af а 2...а Гі , где а Є {хі}х2,...,хт}. Как было показано выше, v Є Ps(m,n). Из описания алгоритма As следует, что д — а\ а2 .. о и Г\ $. Это означает, что элемент д представим в виде слова v Є Ps. С другой стороны, из определения слова следует, что различным элементам дъ д2 Є В(т,п) будут соответствовать различные слова wi, v2 Є Ps{m,n), в противном случае д\ и д2 будут равны как элементы группы. В данной главе рассмотрены примеры построения известных бернсайдо- вых групп (2,3), 5(3,3) и 5(2,4). 2.1. Группа 5(2,3) 1)Строим объект #і(2,3) - { ьРьГьС .Здесь: Ах — алгоритм 3-апериодичности, который преобразует произвольное слово w в 3-апериодическое слово v, т.е. v ф pxxxq. Pi — последовательность, где е — пустое слово,{0,1} — образующие объекта. На последовательности Pi введём отношение порядка " " (меньше), полагая по определению є 0 1.
Группа (2,4)
Обозначим через u){G) спектр группы G, т.е. множество порядков эле ментов из 7. Например, ш(Ь2(7)) — {1,2,3,4,7}. Группа G из класса С называется распознаваемой в С по спектру u(G), если любая груп па Я є С, для которой и)(Н) — w(G), изоморфна G. Другими словами, G распознаваема в С, если hc{G) = 1, где he — число попарно неизо- морфных групп # Є С, изоспектральных группе G, т.е. имеющих тот же спектр, что и G. В работе [14] В.Д. Мазуров сформулировал следующий вопрос: Распознаваема ли группа 2 (7) по спектру в классе всех групп? В настоящей главе этот вопрос сводится к группам, порождённым инволюциями, и доказывается, что в группе G с OJ(G) — w(L2(7)) всегда есть две инволюции, не порождающие 2-группу. Теорема 8. Пусть М — {хі,Х2,хз ] х\ — х\ — х\ — е) — группа, порождённая тремя инволюциями х\, x i, х$ и: /3) произведение любых двух инволюций из М есть 2-элемент, т.е Тогда \М\ 210 и и{М) = {1,2,4}. Доказательство. Построим группу М при помощи алгоритма, описанного в главе 1. Пусть Х\ — 1) Строим объект Кх — {Аі, Рь 71, Сі}. Здесь: Лі — алгоритм поиска и замены соотношений из С\. Блок апериодичности не рассматривается (п — оо). где е — пустое слово, {0,1,2} - образующие объекта. На последовательности Pi введём отношение порядка " " (меньше), полагая по определению е 0 1 2. Заметим, что в Р2 все слова длины 2 являются произведениями инволюций, поэтому их порядок по определению равен 1, 2 или 4. Вследствие чего список соотношений С% пополнится новыми соотношениями: С2 = {е = 02,е = 12,е - 22,е - (10)4,е - (20)4,е = (01)4,е = (21)4, е = (02)4,е - 3) Переходим к построению К3: В Р3 среди слов длины 3 выделим "очевидные инволюции" 010, 020, 101, 121, 202 и 212 (действительно (010)2 = 01(00)10 = 0(11)0 = 00 = е и т.д.). Сгруппируем оставшиеся слова длины 3 по парам: 210 и 012; 120 и 021; 201 и 102. Очевидно, сгруппированные слова являются взаимнооб-ратными друг к другу (действительно 210 012 = е и 012 210 = еи т.д.), следовательно 210 = (012(, 120 = (021( и 201( = 102. Рассмотрим несколько случаев. а) Предположим, что 210 = 3, тогда список соотношений Сз пополнится новым соотношением (210)3 = е. Далее, используя компьютерные вычисления, получим, что в объекте Kj Пусть, теперь, 210 — 7, тогда в список соотношений С3 добавится новое соотношение (210)7 — е. Далее, используя компьютерные вычисления, получим, что в объекте КЦ При этом таблица умножения Тп будет такая же как и табл. 4.2. И, снова, приходим к противоречию с предположением о том, что 210 = 7.
К аналогичному результату приводят предположения о том, что 120 - 7 или 201 - 7. Поэтому 120 ф 7 и 201 ф Совместное рассмотрение случаев (а,б) доказывает, что слова 210, 012, 120, 021, 201 и 102 не могут иметь порядок 3 и 7. Следовательно, данные слова должны иметь порядок 1, 2 или 4. Это означает справедливость следующих соотношений: (210)4 = е, (012)4 = є, (120)4 = е, (021)4 = е, (201)4 = є и (102)4 = е. Добавим эти соотношения в С3: Сз - {е - 02,е = 12,е = 22,е - (10)4,е = (20)4,е = (01)4,е = (21)4, е - (02)4,е - 4) Переходим к построению КІ и последующих объектов Ks, с учётом соотношений из табл. 4.3. В конечном итоге, получим, что Затем, используя компьютерные вычисления, получим, что таблица умножения Т14 удовлетворяет всем групповым свойствам. Таким образом, последовательность Ри с таблцей умножения Ти образует группу, изоморфную М. Непосредственной проверкой находим, чтош(М) = {1,2,4}. Теорема доказана. Следствие 1. Пусть (10)2 = е, (20)2 = є, (21)2 = е . Тогда, прямым вычислением получим, что \М\ = 8. Следствие 2. Пусть (10)2 = є, (210)2 — е. Тогда, прямым вычислением получим, что \М\ = 16. Следствие 3. Пусть (210)2 = е. Тогда, прямым вычислением получим, что \М\ = 32. Следствие 4. Пусть (10)2 = е. Тогда, прямым вычислением получим, что \М\ = 64. Теорема 9. Пусть М — группа и a) a/(M)Cw(L2(7)) = {1,2,3,4,7}; /3) произведение любых двух инволюций из М есть 2-элемент, т.е Тогда М — расширение 2-группы посредством примарной группы. Доказательство. Лемма 1. Любой элемент h є М порядка 4 и любая инволюция х Є М порождают конечную подгруппу периода 4. Доказательство. Рассмотрим группу V — /i2, х, xh . По теореме 8 U — конечная 2-группа. Так как (h2)h = h2 Є U, xh U и (xh)h = xh є U, то Jjh = и и U U,h , поэтому U,h — конечная 2-группа. Лемма доказана. Лемма 2. Подгруппа, порождённая всеми инволюциями группы М, является 2-группой. Доказательство. Пусть I — множество инволюций группы М. Достаточно показать, что (х\Хъ...хп)4 = 1 для любых хі,Х2,...,хп Є І и любого натурального п. Это верно для п 1. Пусть это верно для какого-то s. Тогда (xix2- -х3)А = 1 для любых Xi,x2,... ,xs Є І. По лемме 1 (хіХ2-. .xs),xs+i — конечная группа (для любых Xi,X2,. ,xa,x3+i I), которая является группой периода 4. Поэтому {х\Х2.. 5-ы)4 — 1- Лемма доказана. Лемма 3. Пусть Н — наибольшая нормальная 2 -подгруппа из М. Тогда М/Н не содержит инволюций. Доказательство. Предположим противное. По предыдущей лемме Я ф 1. Если в М/Н любые две инволюции порождают 2 -подгруппу, то поскольку ш(М/Н) С ш(М) С CJ(L2(7)), все инволюции М/Н по лемме 2 порождают нетривиальную 2 -подгруппу, полный прообраз которой является 2-группой, собственным образом содержащей Я, что противоречит выбору Н. Поэтому в М/Н есть две инволюции а, Ь, произведение которых является нетривиальным элементом простого нечётного порядка. Если а,Ь — прообразы а,Ь в М, то а,Ь — конечная группа. Пусть h — нетривиальный элемент из Я. Тогда h a,b — конечное множество.
Поскольку Я локально конечна, Я0 = h a,b является нетривиальной конечной 2-подгруппой, инвариантной относительно а, 6 , и в подгруппе М0 = Но- о, Ь силовская р-подгруппа Р для некоторого нечётного числа р нетривиальна. Так как Р действует без неподвижных точек на МоПЯ / 1, то NM0{P) — a,b и поэтому является группой диэдра. Но тогда в М0 \ Я есть инволюция, что противоречит выбору Я. Лемма доказана. Лемма 4. М является расширением 2 -группы посредством примаркой группы. Доказательство. Предположим противное. Пусть Я — подгруппа из предыдущей леммы. По лемме 3 М/Н является {3,7}-группой и, следовательно, М содержит элемент а порядка 3. Поскольку Я локально конечна, Я, а локально конечна. Если ее,у,z є Я, то М0 = x,y,z,a — конечная группа и Н0 = М0Г\Н — конечная группа, на которой элемент а порядка 3 действует при сопряжении без неподвижных точек. По [34] Я0 двусту-пенно нильпотентна и, следовательно, [[re,y]- z] = 1. Это показывает, что Я двуступенно нильпотентна. Пусть Z — Z(H). Тогда М/Н — группа, действующая свободно на абелевой 2-группе Z, и по [7] центр М/Н содержит элемент порядка 3. Но тогда М/Н содержит элемент порядка 21, что противоречит условию. Лемма и теорема доказаны. Теорема 10. Если для произвольной группы М, порождённой инволюциями и удовлетворяющей условию ш(М) — ш( (7)), выполняется М L2{7)f то и для произвольной группы G, со свойством u{G) — аі(І 2(7)), выполняется G = Ь2(7). Доказательство. Пусть М — подгруппа, порождённая всеми инволюциями группы G. Тогда M G. Если ш(М) — UJ(G), то по предположению М = Ь2{7). По условию на G, Сс(М) = 1 и поэтому G Aut М. Отсюда G = Ь2(7) или PGL2{7), но в PGL2(7) есть элемент порядка 6, поэтому G = Ь2(7), и заключение в этом случае верно. Пусть ш(М) Ф w(C?). Если 4 LO{M), ТО ПО [15] это невозможно. Поэтому либо 3 w(M), либо 7 ш(М). Если 3 ф ш(М), то ПО лемме 6 из [8], М нильпотентна и, следовательно, является 2-группой. По теореме 9 ш(С) ф и){Ь2{7)). Противоречие. Если З Є о (М), а 7 фи(М), то по [20] М локально конечна. По [37] М нильпотентна и, следовательно, в М есть элемент порядка 6 u(L2(7)). Противоречие. Теорема доказана.
Построение Л"2о(2,5)
Актуальность темы. Комбинаторную теорию групп можно охарактеризовать как теорию групп, которые описываются порождающими и определяющими соотношениями, где в качестве модели используется модель, известная как "комбинаторика слов". Как самостоятельная наука со своей проблематикой она оформилась по существу только после того, как в 1911 г. М. Дэн сформулировал основные алгоритмические проблемы теории групп: проблему распознавания равенства, известную в литературе также под названием "проблема тождества", проблему сопряжённости и проблему изоморфизма. Ученику М. Дэна, В. Магнусу, принадлежит также существенный вклад в исследовании такой важной проблемы теории групп — проблемы Бернсайда [23] о периодических группах, поставленной в 1902 г.: Будет ли конечной группа с т порождающими и тождественным соотношением хп — 1? Намеченный Магнусом в его работах (начиная с 1935 г.) подход к исследованию проблемы Бернсайда привёл в 1950 г. к формулировке новой проблемы, которая в нашей литературе известна под названием "ослабленная" проблема Бернсайда [29]: конечно ли число конечных т порождённых групп периода п? По элементарной теореме Пуанкаре это означает существование универсальной максимальной конечной группы Ва(т,п). Подход Магнуса лежит в основе доказательства полученных в дальнейшем результатов по этим проблемам. Группа которая получается факторизацией свободной группы 5 = 5(m) с т разующими по нормальной подгруппе З71, порождённой n-ми степенями всех элементов из $, называется сейчас свободной бернсайдовой груп- пой показателя (или периода) п. Её конечность, установленная в разное время для п — 2 (тривиальный случай), п — 3 (Бернсайд У.), п = 4 (Бернсайд У. для т = 2; Санов И.Н. [20] для произвольного т), п = 6 (Холл М. [25]), была поставлена под сомнение при п 72 П.С. Новиковым в его заметке [16]. Отрицательное решение проблемы Бернсайда было получено впервые лишь в 1964 году Е.С. Голодом [4,5] на основе универсальной конструкции Е.С. Голода — И.Р. Шафаревича. Позднее СВ. Алешиным [2], Р.И. Гри-горчуком [6], В.И. Сущанским [21] была предложена целая серия отрицательных примеров.
Доказательство бесконечности группы В(т,п), т 2, для нечётных показателей п 4381 было дано в работе П.С. Новикова - СИ. Адяна [17], а для нечётных п 665 — в книге СИ. Адяна [1]. Гораздо более доступный и геометрически наглядный вариант доказательства для нечётных п ДО10 был предложен А.Ю. Ольшанским [18], который впоследствии [19], на основе усовершенствованного метода, построил для каждого достаточно большого простого числа р бесконечную р-группу, все собственные подгруппы которой имеют порядок р. В работах СВ. Иванова [27] и И.Г. Лысёнка [13] показано, что для достаточно больших чётных, п группа В(т,п) также бесконечна (у Иванова п 248 и п делится на 29, у Лысёнка n = 16& 8000). Вопрос о существовании универсальной конечной группы В0(т,п) приобрел права гражданства в начале 40-х годов после работ В. Магнуса [30-33], О. Грюна [24], Г. Цассенхауза [39], Р. Бэра [22]. Именно тогда в случае простого показателя п = р была получена редукция теоретико-групповой задачи о существовании Во(т, п) к вопросу о локальной нильпотентности алгебры Ли L над Zp, удовлетворяющей тож- дественному соотношению (условию ЭнееляЕр-i). Результаты не замедлили сказаться: существование Во(2,5) было установлено в 1955 г. [9], В0(т, 5) — в 1956 г. [10,26], В$(т,р) — в 1958 г. [11]. Окончательное положительное решение ослабленной проблемы Бернсайда для любых тип было получено Зель-мановым. Естественно, возник вопрос о совпадении групп В${гп,п) и В(т,п). Как отмечено выше, Во(го,п) = В(т,п) для п = 2,3,4,6. Во(т,п) ф В(т,п) для нечётных п 665 и для чётных п [п 248 и п делится на 29,n = 16k 8000). Общая идея алгоритмической комбинаторики от Евклида и до наших дней — представить основные алгебраические структуры в виде объектов, поддающихся вычислительной обработке, и ответить на два основных вопроса: что такое вычисление математического объекта; как его вычислить наиболее эффективно. В рамках этой концепции машинный эксперимент по группам В(т, п) внушителен. Большинство работ в этом направлении используют комбинаторно-перечислительные методы в коммутаторном исчислении, базирующиеся на конструкциях алгебры Ли [38]. Следует сказать о различных постановках проблем бернсайдового типа (А.Г. Курош) [12]. Так, В.В. Блудов [3] изучает группы показателя 4, А.И. Скопин [28,35,36] — показателей 8, 9, 16, 25, 27 и др.
Реализация алгоритма на языке MATLAB 7
Цель диссертации. Цель диссертации — создать комбинаторный алгоритм для вычисления элементов и соотношений в бернсайдовых и других периодических группах и проиллюстрировать его эффективность для доказательства конечности указанных групп. Основные результаты диссертации: 1. Создан алгоритм, основанный на комбинаторике слов, для вычисления элементов и соотношений в бернсайдовых и других периодических группах и его реализации на языках 2. Найден критерий (теорема 1) конечности группы В(т,п), основанный на комбинаторной структуре данного алгоритма. 3. Для группы В{2,5) получено: a) раннее неизвестный список соотношений С2о(2,5) (табл. 3.3.) для всех слов, не превосходящих по длине 20; b) с учётом полученного списка соотношений из а) вычислен коммутатор специального вида а12(0,1), который является критерием конечности группы В(2,5) снизу. 4. Доказана теорема 10, которая редуцирует проблему распознаваемо сти 1-2(7) к группам, порождённым инволюциями. Методы исследования. Применяются методы дискретной математики, включая методы комбинаторной теории групп, а также теории комбинаторных алгоритмов. Научная новизна. Все основные результаты диссертации являются новыми. Теоретическая значимость и практическая ценность. Результаты, из- - ложенные в диссертации, имеют теоретическое значение и могут быть использованы как в дальнейших исследованиях в комбинаторной теории групп, так и при чтении специальных курсов по дискретной математике и алгебре. Структура и объём работы. Диссертация состоит из введения и пяти g глав основного текста. Список литературы состоит из 50 наименований. Работа изложена на 102 страницах текста. Апробация, Результаты диссертации докладывались автором на Второй Всероссийской научной конференции "Проектирование инженерных и научных приложений в среде MATLAB" в 2004 г. в г. Москве, "Маль-цевских чтениях" 2004, 2005 гг., на XLII Международной научной студенческой конференции в 2004 г. "Студент и научно-технический прогресс", проходившей в г.Новосибирске, Международной конференции, посвященной 75-летию со дня рождения профессора А.И. Кокорина "АЛиК-2004", проходившей в г. Иркутске, VI Международной конфе- ренции "Дискретные модели в теории управляющих систем" в 2004 г. в г. Москве, Международной алгебраической конференции посвященной 100-летию со дня рождения П.Г. Конторовича и 70-летию Л.Н. Шеврина, в 2005 г. в г. Екатеринбурге. Они неоднократно обсуждались на семи- «, нарах в Красноярском государственном университете, Красноярском го- сударственном аграрном университете и Красноярской государственной архитектурно-строительной академии. Публикации.
Основные результаты по теме диссертации опубликованы в [40]- [50]. Как отмечалось выше, большинство численных экспериментов по проблеме Бернсайда связаны с конструкциями алгебры Ли. В настоящей диссертации предложен комбинаторный алгоритм, доказывающий конечность группы В(т,п), основанный на её комбинаторной структуре. В главе 1 описан алгоритм, который позволяет представить В(т,п) в виде предела последовательности объектов К3(т,п). Объект Ks(m,n) — {P3,AS,CS,T3} представляет собой множество всех слов группы Бернсайда Р3, не превосходящих по длине s, с заданной на этом множестве таблицей умножения Т3, обрабатывая которую при помощи алгоритма Л3, мы получаем список соотношений Cs. В результате работы алгоритма строится последовательность объ ектов К\,К2...,KS, Она обладает тем свойством, что если группа бесконечна, то её "предел" при s, стремящемся к бесконечности, равен группе В(тп,п). Если же K3(m,n) = Ks+i(m,n), то имеет место приводимая ниже теорема, которая даёт критерий конечности группы В(т,п). Теорема 1. Пусть s є N и s наименьшее со свойством Ks(m,n) = Ks+i(m,n), тогда \В(т,п)\ В главе 2 показана реализация алгоритма на известных конечных группах В(2,3), В(2,4) и В(3,3). Приведённые результаты полностью согласуются с известными данными об этих группах. Кроме того, доказаны следующие теоремы; Теорема 2. Объект К$(2,3) изоморфен группе В(2,3). Теорема 3. Пусть группа G = х,у\х3 — у3 = l,yxyx = ххуу, ххухх = уухуу.уухх = хуху}уухух = хууху,хуух = ухху , тогда группа G изоморфна группе В(2,3). Теорема 4. Объект К2$(2,А) изоморфен группе 5(2,4). В работе найден список соотношений С объекта if2o(2,4), такой, что имеет место Теорема 5. Пусть группа G = х, у\хА = у4 = 1, С) , тогда группа G изоморфна группе 5(2,4). Теорема 6. Объект /Сі2(3,3) изоморфен группе 5(3,3). В работе найден список соотношений С\ объекта /Сі2(3,3), такой, что имеет место Теорема 7. Пусть группа G — х,у,г\хъ = уг = гъ — \,С\ , тогда группа G изоморфна группе 5(3,3). Теоремы 3,5,7 характеризуют группы 5(2,3), 5(2,4) и 5(3,3) в классе всех групп через порождающие и соотношения. В главе 3 приведены численные результаты по доказательству конечности группы 5(2,5). Построен объект /С2о(2,5), порядок которого сопоставим с 59, а также приведена статистика данного объекта. Рассмотрена динамика изменения коммутатора аі2(0,1) = [...[[0,1],0]1...1]0] в зависимости от получаемых соотношений на каждом шаге. Приведён список соотношений для группы 5(2,5). В главе 4 изучается один из вопросов, сформулированных В.Д. Мазуровым в [14]: распознаваема ли группа L2(7) по спектру в классе всех групп? Основным результатом главы 4 является теорема 10, в которой доказывается, что проблему распознаваемости достаточно решить для групп, порождённых инволюциями.
Теорема 10. Если для произвольной группы М, порождённой инволюциями и удовлетворяющей условию ш(М) = w(L2(7)), выполняется М = //2(7), то и для произвольной группы G, со свойством u(G) = ш(Ь2(7)), выполняется G = L2(7). Для доказательства теоремы 10 была использована Теорема 9. Пусть М — группа и /3) произведение любых двух инволюций из М есть 2-элемент, т.е Тогда М — расширение 2-группы посредством примарной группы. В свою очередь, для доказательства теоремы 9 была использована Теорема 8. Пусть М — {хі,х2,хз х\ = х\ = х\ = е) — группа, порождённая тремя инволюциями (3) произведение любых двух инволюций из М есть 2-элемент, т.е VU.WGM \VW\ = {1,2,4}, если \v\ — \w\ = 2. Следует отметить, что для доказательства теоремы 8 использовались компьютерные вычисления, базирующиеся на алгоритме из главы 1, а также комбинаторный анализ множества возможных соотношений для указанной группы. В главе 5 для алгоритма из главы 1 приведены тексты программ, написанных на компьютерных алгоритмических языках MATLAB 7 и FORTRAN 90. Во время работы над диссертацией автор получал поддержку Российского фонда фундаментальных исследований (грант № 03-01-00905). Автор выражает благодарность научным руководителям профессору А.К. Шлёпкину и профессору Г.П. Егорычеву за постановку задачи, помощь в работе и внимание с их стороны. Также автор выражает благодарность С.А. Тарасову за помощь при написании программы на языке FORTRAN 90.