Шуровость и отделимость ассоциативных схем

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

1 Схемы отношений и клеточные алгебры

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

». 1.2 Примеры

1.3 Операции

{ 1.4 Шуровость и отделимость схем

1.5 Кольца Шура и схемы Кэли

1.6 Линейные представления клеточных алгебр

2 Алгебраическая природа схем отношений

2.1 Обобщённые С-алгебры

2.2 Спаривание и его свойства

' і 2.3 Планшерелева двойственность

2.4 Многозначные группы
3 Многомерные инварианты схем
3.1 Многомерные расширения схем и подобий
3.2 Числа отделимости и шуровости
3.3 Поведение при операциях
3.4 Псевдоотделимые и псевдошуровы схемы
3.5 Многомерные расширения и (К, Л)-регулярность графов
3.6 Отделимость и шуровость классических схем
3.7 Отделимость и шуровость схем конечных плоскостей
4 Циркулянтные Б-кольца и отделимость циклотомических схем
4 4.1 Циклотомические схемы и нормальные схемы Кэли
; 4.2 Обобщённые сплетения Б-колец
4.3 Циркулянтные Б-кольца
4.4 Критерий нормальности и его следствия
4.5 Доказательство критерия нормальности
4.6 Одна техническая теорема
4.7 Отделимость циклотомических схем
4.8 Отделимость и шуровость циркулянтных Б-колец. Гипотеза Шура-Клина128
5 Факторизация многочленов и схемы отношений
5.1 Построение конечного поля и эффективное извлечение корней
5.2 Квазиполиномиальный алгоритм
5.3 Проблема факторизации и проблема шуровости

Ассоциативные схемы, или схемы отношений, изучению которых посвящена настоящая работа, возникают в различных областях математики, хотя -и не всегда под одним и тем же названием. Так, сам термин появился в работах Боуза и его коллег о блок-схемах в рамках теории планирования статистических экспериментов [34, 33]; соответствующий объект является здесь симметричной схемой. Однако ещё ранее в известной работе Шура [80], заложившей основы теории Я-колец, уже появляется понятие централизаторного кольца группы перестановок (которое в транзитивном случае есть не что иное как алгебра Гекке исходной группы по стабилизатору точки), фактически совпадающее с алгеброй смежности ассоциативной схемы специального вида. Общая теория схем отношений возникает независимо как теория когерентных конфигураций в работах Д.Хигмана [54, 55], посвящённых изучению групп ранга 3, и как теория клеточных алгебр в работах Вейсфейлера и Лемана [6, 84], посвящённых вычислительной сложности проблемы изоморфизма графов. В настоящее время структурная теория однородных схем отношений развита в книге Цишанга [88], где они называются обобщёнными группами и рассматриваются как обобщения групп и билдингов. Такие схемы и их алгебры смежности доставляют наиболее важные примеры С-алгебр (обобщающих алгебры характеров конечных групп), гипергрупп, алгебр в планшерелевой двойственности и многозначных групп (см. [1, 87, 17, 40]). Отметим также появившиеся в последнее время работы Джагера, Баннаи и др., посвящённые построению инвариантов зацеплений и узлов на основе теории ассоциативных схем (см. [59, 60, 29]). Наконец, упомянем обнаруженные автором неожиданные связи между теорией схем отношений и задачей эффективного разложения многочленов на множители над конечным полем (см. [44] и последнюю главу диссертации).
Многие задачи теории схем отношений, называемых далее также просто схемами, в той или иной степени связаны с изучением их групп автоморфизмов и с построением различного рода систем инвариантов изоморфизма. В контексте теории групп перестановок упомянем в этой связи известную работу Д.Хигмана [55], посвящённую характеризации классических групп ранга 3 в терминах их иодстепеней. Ещё одним примером является подход к описанию конечных простых групп как групп автоморфизмов подходящих схем отношений. В рамках алгебраической комбинаторики (сравнительно недавно возникшей области математики) одна из важнейших задач состоит в нахождении необходимых и достаточных условий того, чтобы данный дистанционно-регулярный граф был дистанционно-транзитивным. Уже упоминавшаяся выше проблема изоморфизма графов, одна из фундаментальных нерешённых проблем современной теории сложности вычислений, является специальным случаем проблемы изоморфизма схем. Идейно близкой к рассматриваемой проблематике оказывается и задача из программной работы Р. Брауэра [36] по теории представлений конечных групп, а именно, какую информацию необходимо добавить к таблице характеров конечной группы, чтобы получить её полное множество инвариантов.
Анализ этих, а также ряда других задач алгебраической комбинаторики естественным образом приводит к двум следующим проблемам. Первая из них восходит к Виландту [85], который интересовался, при каких условиях данное Б-кольцо возникает из подходящей группы перестановок с регулярной подгруппой. В общей теории схем отношений эта проблема сводится к выяснению того, совпадает ли данная схема со схемой 2-орбит своей группы автоморфизмов. В честь Шура, имевшего дело с объектами только такого рода, её называют проблемой шуровости. Вторая проблема, называемая ниже проблемой отделимости, заключается в нахождении условий, при которых данная схема определяется с точностью до изоморфизма своими числами пересечений. Фактически бблыная часть работ последнего времени по алгебраиче-4 ской комбинаторике (включая известную монографию Баннаи и Ито [1]) посвящена
решению этой проблемы для специальных классов однородных схем, большинство из которых коммутативны и даже симметричны. Исследование двух указанных выше проблем и составляет основное содержание настоящей диссертации
Следует отметить, что современная теория схем отношений имеет дело в основном с однородными схемами; ситуация такова, как если бы в теории групп перестановок рассматривались лишь транзитивные группы. С точки зрения проблем шуровости и отделимости это сильно ограничивает набор инвариантов, которые можно исиоль-*• зовать для их решения, что, в частности, не позволяет ввести количественные характеристики шуровости и отделимости, то есть определить в какой степени данная ( схема отличается соответственно от шуровой или отделимой. Отсутствие развитой
структурной теории неоднородных схем вынуждает автора затратить определённые усилия на восполнение этого пробела.
Диссертация состоит из 5 глав, к изложению основных результатов которых мы и переходим.
Глава 1. Схемы отношений и клеточные алгебры
Основные определения и примеры. Пусть V - конечное множество. Следуя Д.Хигману, под когерентной конфигурацией, схемой отношений, или просто схемой на V мы понимаем пару С = (V, 72), где 72 - разбиение множества V2 такое, что С-линейная оболочка W матриц смежности бинарных отношений, образующих это разбиение, замкнута относительно матричного умножения, эрмитова сопряжения и содержит единицу алгебры Maty. Алгебра W называется алгеброй смежности схемы С; такие алгебры суть в точности клеточные алгебры, введённые Вейсфейлером и Леманом.
Схемы С и С' называются подобными, если существует изоморфизм между их алгебрами смежности, сохраняющий адамарово (покомпонентное) умножение. На языке схем это означает, что существует такая биекция <р множества 72 базисных отношений схемы С на множество базисных отношений схемы С', что
1 cr,s = ch*’,svi! R,S,T € 72,
где Сд s - числа пересечений схемы С (т.е. структурные константы алгебры W относительно её базиса, состоящего из матриц смежности базисных отношений).
Как показывают простые примеры (см. п. 1.2.2), не всякое подобие индуцируется изоморфизмом, т.е. биекцией множества V точек схемы С на множество точек схемы С', сохраняющей базисные отношения. Аналогично не всякое базисное отношение схемы С является 2-орбитой её группы автоморфизмов
Aut(C) = {/ 6 Sym(K): Rf = Д-VR € 72}.
Именно эти два обстоятельства и приводят к основным задачам, рассматриваемым в настоящей диссертации. Всё изложенное выше составляет материал §1.1, где также определяются и изучаются клетки, блоки, ограничения, факторы и расширения

совпадает с множеством и*, и}. Обозначим через X клетку алгебры Гк,
содержащую V. Тогда {щ} х X является базисным отношением алгебры „к.
Поскольку, очевидно, ({щ} х X) П Eq(B) = {(щ,г>)}, то X = {г)}.«
Вернёмся к доказательству теоремы. Пусть (щ, - • •, г>ь) - несводимая база схемы С и Ре 'Р(У) - неглавный идемпотент. Покажем, что при к 6 [Ь] сумма

= (32)

является прямой. Достаточно проверить, что VPvk П Ьк^1 = {0} для всех к е [£>]. Пусть АУк 6 Ьк-1 для некоторой матрицы А 6 IVР. Тогда несводимость выбранной базы гарантирует по лемме 1.43, что Ец(Л) ф Д(К). Поэтому либо матрица А имеет нулевой столбец, либо по лемме 1.42 матрица смежности эквивалентности Eq(yl) принадлежит алгебре 1Г. В обоих случаях А = 0. В первом случае это следует из однородности IV. Во втором лее при А ф 0 примитивность ¥ влечёт равенство Eq(A) = V х V. Это означает, что А кратна фу, что противоречит выбору Р.
Из леммы 1.38 следует, что бш^ИКРад) = п2Р при всех г. С другой стороны, Ьь С РСУ и сЕт(РС’/) = пгрпр. Таким образом, прямое разложение (32) при к = Ъ влечёт неравенство
Ьпр < тпрпр,
что и доказывает теорему.«
С помощью теоремы 1.40 и формулы (31) получаем следующее утверждение.
Следствие 1.44 Если С - примитивная схема, то Ь(С) < (1ау(С).я
Пусть Г < Бут(У) - группа перестановок. Тогда, очевидно, 6(Г) < Ь(С), где 6(Г) -базовое число группы Г и С = 1пу(Г), причём, если группа Г примитивна, то примитивна и схема С. С другой стороны, согласно [5, теорема III.5.В] обёртывающая алгебра Епу(Г) группы Г совпадает с централизатором алгебры 2(Г) в Ма1у и обратно. Более того, 7>(Епу(Г)) = 'Р(Я(Г')) и степень пп (соотв. кратность тж) неприводимого представления ж группы Г, отвечающего идемпотенту Р из этого множества, равна тр (соотв. пР). Таким образом, теорема 1.40 приводит к следующему утверждению, доказанному иным путём в [78].
Теорема 1.45 Если Г - примитивная группа перестановок степени п, то Ь(Г) < тш(п,/т,) < (п - 1 )/(г - 1),

где я пробегает все неглавные неприводимые представления группы Г, входящие в её перестановочное представление, иг- ранг группы Г.«
1.6.3 Группы автоморфизмов примитивных схем
Очевидную верхнюю оценку |Г| < порядка группы перестановок Г степени п можно уточнить следующим образом.