Введение к работе
Актуальность темы. В своей известной монографии "Геометрическая алгебра" М.Артин па стр.79 пишет: "В современной математике исследование симметрии данной математической структуры приводит, как правило, к наиболее значительным результатам". Поскольку значительная часть математических структур может быть определена в терминах отношений (различной арности), естественно изучать группы автоморфизмов семейств отношений. Такой подход впервые возникает у Галуа, который фактически определяет группу уравнения, как группу автоморфизмов семейства отношений на множестве его корней. По сути тот же подход используется и в работе Шура (1933), в которой он обобщает теорему Всрнсайда о примитивных группах перестановок с регулярной циклической подгруппой посредством изучения бинарных отношений, инвариантных относительно последней. Алгебраическим аналогом возникающих при этом комбинаторных структур являются кольца, известные теперь как кольца Шура. Систематическое использование этого подхода было начато Виландтом (1969) и привело к появлению метода инвариантных отношений, суть которого состоит в изучении произвольных групп, как групп автоморфизмов подходящих семейств отношений. Уже в случае бинарных отношений этот метод позволил получить характеризацию некоторых классов групп ранга 3 и построить ряд спорадических простых групп таких, например, как группа Хигмана-Симса.
Общая теория семейств бинарных отношений, наследующих свойства бинарных инвариантных отношений групп перестановок, была заложена Д.Хигманом (1970) и, независимо, в работе Вейсфейлераи Лемана (1968). Такие семейства были названы когерентными конфигурациями, более современное название которых - ассоциативные схемы или просто схемы -связано с появлением двух известных монографий: Баннаи и Ито (1984), где теория схем отношений рассматривалась как обобщение теории представлений конечных групп, и Врауэра, Коэна и Ноймайера (1989), где класс схем дистанционно-регулярных графов изучался с алгебраической, геометрической и комбинаторной точек зрения. Среди паиболее впечатляющих применений теории схем отметим отметим классическую теорему Бабаи (1981), дающую асимптотически точную оценку максимального порядка примитивной группы перестановок, не являющейся дважды транзитивной.
Одной из наиболее важных задач математики является нахождение полного множества инвариантов изоморфизма объектов заданной категории. В случае конечных объектов такое множество всегда может быть выбрано конечным и потому естественная проблема состоит в поиске иаи-
меньшего количества инвариантов. С алгоритмической точки зрения проблема изоморфизма заключается в оценке сложности наиболее эффективного алгоритма, проверяющего изоморфизм двух заданных объектов. Известно, что проблема изоморфизма конечных алгебраических структур сводится к проблеме изоморфизма конечных графов, являющейся одной из наиболее известных нерешённых проблем теории сложности вычислений. Именно эта проблема привела Вейсфейлера и Лемана в 1968 г. к открытию клеточных алгебр, которые есть ни что иное как алгебры смежности схем отношений. Связав с каждым графом клеточную алгебру, порождённую его матрицей смежности, они фактически показали, что проблема изоморфизма графов полиномиально эквивалентна проблеме нахождения группы автоморфизмов схемы отношений. Эти идеи, актуальные и в настоящее время, привели к появлению ряда эффективных алгоритмов решения последней проблемы в естественных классах графов и схем, определяемых с помощью тех или иных алгебраических ограничений.
Исходным пунктом настоящей работы является соответствие Галуа между множеством всех схем С на конечном множестве V и множеством всех подгрупп Г симметрической группы Sym(V), задаваемое отображениями
Cy~>Aut(C), Гн-іпу(Г), (1)
где Aut(C) - группа автоморфизмов схемы С и 1пу(Г) - схема орбит группы Г относительно её индуцированного действия на V2. Замкнутыми объектами в этом соответствии являются шуровы схемы и 2-замкнутые группы. Следует отмстить, что соответствие (1), не являясь взаимнооднозначным, становится таковым при некоторых условиях. Важный пример такой ситуации возникает для классов схем и груші, для которых справедлив аналог теоремы Виркгофа о дважды стохастических матрицах; соответствующая теория развивается в главе 6. Правая часть соответствия (1) легла в основу метода Шура, применяемого к схемам, группа автоморфизмов которых содержит регулярную подгруппу. Накладывая на такие схемы условие инвариантности относительно автоморфизмов этой подгруппы, удаётся существенно обобщить известную теорему Бернсайда-Шура о группах перестановок (глава 4).
С вычислительной точки зрения можно легко найти схему группы перестановок эффективным алгоритмом, в то время как нахождение группы автоморфизмов - трудная задача, полиномиально эквивалентная проблеме изоморфизма графов. Эта задача упрощается, если известна некоторая априорная информация о группе автоморфизмов или сё можно получить изучая структуру соответствующей схемы. В первом случае примером является долгое время остававшаяся нерешённой проблема на-
хождения эффективного алгоритма построения группы автоморфизмов циркулянтной схемы (у такой схемы группа автоморфизмов содержит регулярную циклическую подгруппу). Эта проблема полностью решается в главе 5 на основе значительного развития теории таких схем, построенной в последнее время. Во втором случае, используя известную теорему Жордана о линейных группах, мы доказываем, что группа автоморфизмов произвольной однородной схемы содержит разрешимую подгруппу, индекс которой ограничен некоторой функцией, зависящей от инвариантов линейных представлений алгебры смежности этой схемы. Это позволяет построить алгоритм для нахождения канонической формы и группы автоморфизмов в классе всех схем, работающий полиномиальное время, когда упомянутые инварианты растут медленно в сравнении со степенью схемы (глава 3).
Цель работы. Основной целью диссертации является исследование на основе соответствия (1) групп автоморфизмов ассоциативных схем как с сугубо теоретической, так и с алгоритмической точек зрения.
Методы исследований. Применяются общие методы теории групп перестановок, теории представлений групп и алгебр, теории сложности вычислений, а также новые методы, предложенные автором, включая обобщение метода инвариантных отношений, введённого Виландтом.
Научная новизна. В диссертации получены следующие новые результаты.
-
Получено обобщение теоремы Бернсайда-Шура о группах перестановок с регулярной подгруппой, основанное на построении теории колец Шура над конечными коммутативными кольцами.
-
Доказан аналог теоремы Жордана о группах с точным линейным представлением для транзитивных групп перестановок с ограниченными степенями неприводимых представлений, входящих в перестановочное.
-
Введено и изучено понятие комбинаторной компактности ассоциативных схем и групп перестановок, позволяющее значительно обобщить теорему Биркгофа о дважды стохастических матрицах.
-
Изучены группы автоморфизмов схем Кэли над циклической группой. В частности, получена характеризация разрешимых групп в этом классе.
-
Введены и полностью охарактеризованы лесовидные схемы и их группы автоморфизмов. Полученные результаты позволили объяснить с алгебраической точки зрения эффективность комбинаторных алгоритмов проверки изоморфизма для нескольких хорошо известных классов графов.
-
Впервые построен алгоритм полиномиальной сложности для рас-
познавания схем Кэли над циклической группой и вычисления их групп автоморфизмов. Доказано, что с его помощью можно эффективно найти полную систему попарно неэквивалентных представлений Кэли таких схем.
-
Определена каноническая форма в классе всех ассоциативных схем, сложность вычисления которой растёт полиномиально при медленно растущей максимальной кратности неприводимых представлений их алгебр смежности
-
Описан эффективный алгоритм вычисления 2-замыкашш групп перестановок в классе разрешимых групп, включающем все нильпотентные группы и все группы нечётного порядка.
-
Введена конструкция сплетения схемы с группой перестановок, позволяющая строить новые бесконечные семейства примитивных нешуро-вых схем. Получены необходимые и достаточные условия примитивности и шуровости схемы, получающейся с помощью такого сплетения.
Апробация работы. Основные результаты диссертации многократно докладывались и обсуждались на алгебраическом семинаре им. Д.К.Фад-десва (СПбГУ), на семинаре по теории сложности вычислений (ПОМИ), на семинаре но теории представлений и динамическим системам (ПОМИ), на семинаре по информатике и компьютерным технологиям (СПИИРАН), на университетских математических семинарах г. Ренна (Франция) и it. Бонна и Мюнхена (Германия), а также были представлены на следующих конференциях:
-
Вторая международная конференция "Методы логики в математике", Санкт-Петербург, Россия, июль 2005 г. (приглашённый доклад),
-
Международная конференция "Открытые проблемы теории ассоциативных схем", Пусан, Корея, июль 2004 г. (приглашённый доклад),
-
Вторая международная конференция по математическим алгоритмам, Нижний Новгород, Россия, июнь 1995 г. (приглашённый доклад),
-
Международная конференция "Последние достижения в теории ассоциативных схем", Санкт-Петербург, Россия, июль 2005 г.,
-
Международная конференция "Ассоциативные схемы, коды и дизайны", Пусан, Корея, июль 2004 г.,
-
Шестая международная конференция по приложениям компьютерной алгебры (IMACS), Санкт-Петербург, Россия, июнь 2000 г.,
-
Пятый чешско-словацкий симпозиум но комбинаторике, теории графов, алгоритмам и их приложениям, Прага, Чехия, июль 1998 г.,
-
Международная конференция "Формальные степенные ряды и алгебраическая комбинаторика", Торонто, Канада, июнь 1998 г.,
-
Международная алгебраическая конференция памяти Д.К.Фадде-ева, Санкт-Петербург, Россия, июнь 1997 г.,
-
Международная конференция памяти Л.А.Калужнина "Алгебра и комбинаторика: взаимные связи и приложения", Кёнигштейн, Германия, апрель 1994 г.,
-
Международная конференция по алгебраической комбинаторике (ALCOM), Владимир, Россия, август 1991 г.,
-
Восьмая всесоюзная конференция по математической логике, Москва, сентябрь 1986 г.
Практическая ценность. Работа носит теоретический характер. Её результаты могут быть использованы в алгебраической комбинаторике, теории групп, вычислительной алгебре и теории графов, а также в теории планирования эксперимента и в математических моделях телекоммуникационных сетей связи.
Публикации. Основное содержание диссертации опубликовано в 13 научных статьях, список которых приведён в конце автореферата.
Структура и объём работы. Диссертация состоит из введения, шести глав и списка литературы, содержащего 81 название. Общий объём диссертации составляет 118 страниц.
