Группы автоморфизмов ассоциативных схем

• Автор: Пономаренко, Илья Николаевич
• Шифр специальности: 01.01.06
• Научная степень: Докторская
• Год защиты: 2005
• Место защиты: Санкт-Петербург
• Количество страниц: 118 с.

1 Общая теория

1.1 Схемы отношений

1.2 Алгебры смежности

1.3 Группы перестановок

1.4 Алгоритмы

2 2-замыкания групп перестановок

2.1 Прямые суммы и тензорные произведения

2.2 Сплетения групп и сплетения схем

2.3 Экспонеицирование схемы с группой перестановок

2.4 Нахождение 2-замыканий в классах разрешимых групп

3 Каноническая форма в классе всех схем

3.1 Линейные инварианты схем и групп
3.2 Теорема Жордана и группы перестановок
3.3 Канонические формы и канонические пометки
3.4 Основной алгоритм
4 Теорема Бернсайда-Шура и её обобщение
4.1 Кольца Шура и схемы Кэли
4.2 Кольца Шура над коммутативными кольцами
4.3 Теорема о разделяющей подгруппе
4.4 Доказательства теорем 4.11 и 4
5 Канонические формы циркулянтных схем
5.1 Квазинормальные и сингулярные схемы
5.2 Структура циркулянтных схем
5.3 Циклическая база разрешимой группы
5.4 Распознавание циркулянтных схем
5.5 Проверка изоморфизма циркулянтных графов
6 Теорема Биркгофа для схем и групп
6.1 Комбинаторная компактность
6.2 Примеры компактных схем, групп и графов
6.3 Алгоритм проверки изоморфизма компактных схем
6.4 Лссовидиыс схемы и алгебраические леса
Список литературы

В своей известной монографии "Геометрическая алгебра"М.Артин на стр.79 пишет: "В современной математике исследование симметрии данной математической структуры приводит, как правило, к наиболее значительным результатам". Поскольку значительная часть математических структур может быть определена в терминах отношений (различной арности), естественно изучать группы автоморфизмов семейств отношений. Такой подход впервые возникает у Галуа, который фактически определяет группу уравнения, как группу автоморфизмов семейства отношений на множестве его корней. По сути тот же подход используется и в работе Шура [71], в которой он обобщает теорему Бернсайда о примитивных группах перестановок с регулярной циклической подгруппой посредством изучения бинарных отношений, инвариантных относительно последней. Алгебраическим аналогом возникающих при этом комбинаторных структур и являются кольца, известные теперь как кольца Шура. Систематическое использование этого подхода было начато Виландтом в [79] и привело к появлению метода инвариантных отношений, сутыо которого и является изучение произвольных групп, как групп автоморфизмов подходящих семейств отношений. Уже в случае бинарных отношений этот метод позволил получить характеризацию некоторых групп ранга 3 [48] и построить ряд спорадических простых групп таких, например, как группа Хигмана-Симса.
Общая теория семейств бинарных отношений, наследующих свойства бинарных инвариантных отношений групп перестановок, была заложена в работе Хигмана [49] и, независимо, в работе Вейсфейлера и Лемана [4] (см. ниже). Такие семейства были названы когерентными конфигурациями, более современное название которых - ассоциативные схемы или просто схемы - связано с появлением монографий [1, 29, 81]. Среди наиболее впечатляющих применений теории схем отметим отметим классическую теорему Бабаи, дающую асимптотически точную оценку максимального порядка примитивной группы перестановок, не являющейся дважды транзитивной [21].
Одной из наиболее важных задач математики является нахождение полного множества инвариантов изоморфизма объектов заданной категории. В случае конечных объектов такое множество всегда может быть выбрано конечным и потому естественная проблема состоит в поиске наименьшего количества инвариантов. С алгоритмической точки зрения проблема изоморфизма заключается в оценке сложности наиболее эффективного алгоритма, проверяющего изоморфизм двух заданных объектов. Известно, что проблема изоморфизма конечных алгебраических структур сводится к проблеме изоморфизма конечных графов, являющейся одной из наиболее известных нерешённых проблем теории сложности вычислений [11, 22, 24]. Именно эта проблема привела Вейсфейлера и Лемана к открытию клеточных алгебр, которые есть ни что иное как алгебры смежности схем отношений [4]. Связав с каждым графом клеточную алгебру, порождённую его матрицей смежности, они фактически показали, что проблема изоморфизма графов полиномиально эквивалентна проблеме нахождения группы автоморфизмов схем отношений [77]. Эти идеи в дальнейшем были развиты в ряде работ [14, 07, 27, 35, 36].
Основной целыо диссертации является исследование групп автоморфизмов ассоциативных схем как с сугубо теоретической, так и с алгоритмической точек зрения. Ключевым моментом здесь служит соответствие Галуа между множеством всех схем С на конечном множестве V и множеством всех подгрупп Г симметрической группы

Бут(П), задаваемое отображениями
СнАиОД, Г 1пу(Г), (1)
где Ап! (С) - группа автоморфизмов схемы С и 1пг(Г) - схема орбит группы Г относительно её индуцированного действия на V2. Замкнутыми объектами в этом соответствии являются шуровы схемы и 2-замкнутые группы. Следует отметить, что соответствие (1), не являясь взаимно-однозначным, становится таковым при некоторых условиях. Важный пример такой ситуации возникает для классов схем и групп, для которых справедлив аналог теоремы Биркгофа о дважды стохастических матрицах; мы развиваем соответствующую теорию в главе б. Правая часть соответствия (1) легла в основу метода Шура, применяемого к схемам, группа автоморфизмов которых содержит регулярную подгруппу. Накладывая на такие схемы условие инвариантности относительно автоморфизмов этой подгруппы, удаётся существенно обобщить известную теорему Бернсайда-Шура о группах перестановок (
глава 4).
С вычислительной точки зрения можно легко найти схему группы эффективным алгоритмом, в то время как нахождение группы автоморфизмов - трудная задача, полиномиально эквивалентная проблеме изоморфизма графов. Эта задача упрощается, если известна некоторая априорная информация о группе автоморфизмов или её можно получить изучая структуру соответствующей схемы. В первом случае примером является долгое время остававшаяся нерешённой проблема нахождения эффективного алгоритма построения группы автоморфизмов циркулянтной схемы (у такой схемы группа автоморфизмов содержит регулярную циклическую подгруппу). Мы полностью решаем эту проблему в главе 5 значительно развивая теорию таких схем, построенную в последнее время [52, 9]. Во втором случае, используя известную теорему Жордана о линейных группах, мы доказываем, что группа автоморфизмов произвольной однородной схемы содержит разрешимую подгруппу, индекс которой ограничен некоторой функцией, зависящей от инвариантов линейных представлений алгебры смежности этой схемы. Это позволяет построить алгоритм для нахождения канонической формы и группы автоморфизмов в классе всех схем, работающий полиномиальное время, когда упомянутые инварианты растут медленно в сравнении со степенью схемы (
глава 3).
Диссертация состоит из б глав, к изложению основных результатов которых мы и переходим.
Глава 1. Схемы отношений, группы перестановок, алгоритмы
Эта глава носит вводный характер; здесь приводятся необходимые определения и обозначения, используемые на протяжении всей работы. К сожалению, не существует устоявшейся системы обозначений и понятий в общей теории ассоциативных схем. Например, в монографиях [80, 81] система обозначений отражает взгляд автора на ассоциативные схемы как на обобщение абстрактных групп. Мы же, исходя из того, что схемы в большей степени подобны группам перестановок, используем обозначения и понятия перестановочных представлений, согласованные с [5].
Пусть V - конечное множество. Следуя Д.Хигману, под когерентной конфигурацией, схемой отношений, или просто схемой на V мы понимаем пару С = (V, Л), где Л - замкнутое относительно перестановки координат разбиение множества V2 такое, что диагональ Д(У) множества V2 является объединением элементов из Л и

3.3 Канонические формы и канонические пометки
3.3.1. Под упорядоченной схемой С мы понимаем схему с линейным порядком на множестве её базисных отношений. Этот порядок индуцирует линейный порядок на множестве её клеток и лексикографические порядки на множествах сё отношений и эквивалентностей, а также линейный порядок на базисных отношениях схем Сх/е, где X £ В1(С) и Е £ В (С). Изоморфизмом упорядоченных схем называется обычный изоморфизм, сохраняющий линейный порядок на множестве базисных отношений. Две упорядоченные схемы на одном и том же множестве считаются равными, если тождественная перестановка этого множества является изоморфизмом этих схем. Если С £ 2Ц - упорядоченная схема и д : V —> V' - биекция, то по определению порядок базисных отношений схемы С9 — (V', Л9) считается равным порядку, индуцированному этой биекцией.
Для схемы С £ 2Ц и отношения Л С V2, линейный порядок на множестве базисных отношений схемы [С, Щ определяется как линейный порядок, вычисляемый каноническим алгоритмом Вейсфейлера-Лемана (см. [77, Глава М]). Такой порядок обладает следующим свойством:
[С, Щ9 = [С9, И9} для каждой биекции д с областью определения V. (44)
Схема [С, Л] вместе с соответствующим упорядочением базисных отношений может быть построена за полиномиальное время от степени схемы С.
Наш подход к проблеме канонизации схем восходит к работе [25] и подобен подходу, использованному в работе [35]. Именно, под классом смежности на множестве V мощности п будем понимать множество С = йд, где д : V —* [п] - биекция и С < 8ут(Н) - группа (эквивалентно, С = дС, где С < Эупфп)). Определим V-пару как пару Р = (С, С), где С 6 2Ц - упорядоченная схема и С - класс смежности на V. Эта пара изоморфна Г'-паре Г', Р = Р если существует биекция а : V —* V' такая, что Р9 = Р', где Р9 = (С9,д~1С).
Пусть V ~ класс пар Р, замкнутый относительно изоморфизмов пар, и содержащий подкласс Р0, состоящий из всех [п]-пар для всех натуральных чисел га. Отображение СГ : V —> То называется канонической формой на V, если выполнены следующие условия:
(С1) УР £ V : СГ(Р) = Р,
(С2) УР, Р'еР: Р = Р’ & СГ (Р) = С¥{Р').
Любая биекция /г, для которой Рн = СГ(Р) называется канонической пометкой пары Р. Множество всех таких биекций образует класс смежности СЦР) = АиЬ(Р)1г = (Аи1;(С) П (?)/ц где Р = (С, Од), называемый классом смежности канонических пометок пары Р относительно канонической формы СГ. Очевидно, имеет место следующее равенство:
СЦР?) = д-1 СЦР) (45)
для каждой биекции д с областью определения V. Обратно, пусть Р СЦР) - произвольное отображение, сопоставляющее Г-иаре Р £ V непустое множество СЦР)
биекций из V на [га] так, что пара Рк не зависит от выбора биекции Н £ СЦР), и