Шуровость и отделимость ассоциативных схем тема автореферата и диссертации по математике, 01.01.06 ВАК РФ

Санкт-Петербургский государственный университет

На правах рукописи

ЕВДОКИМОВ СЕРГЕЙ АЛЕКСЕЕВИЧ Шуровость и отделимость ассоциативных схем

01.01.06 - математическая логика, алгебра и теория чисел

АВТОРЕФЕРАТ

диссертации на соискание учёной степени доктора физико-математических наук

Санкт-Петербург - 2005

Работа вынопнена в Санкт-Петербургском институте информашки и автоматизации РАН.

Официальные оппоненты:

докюр физико-математических наук, академик РАО. профессор Марк Иванович Башмаков

доктор физико-математических наук, член-корреспондент Р\Н, профессор Александр Алексеевич Махнев

доктор физико-математических наук Максим Михайлович Скриганов

Ведущая организация:

Математический институт имени В.А Стекчова РАН

Защита состоится ,у п1 I*- Ьо 2005 г. в _ ( о часов па

заседании диссертационного совета Д 212 232 29 по защите диссертаций на соискание учёной степени доктора наук при Санкт-Петербургском государственном университете по адресу 198504, Санки-Петербург Старый Петергоф, Университетский нр , д 28, матрматико-механичргкий факультет.

С диссертацией можно ознакомиться в Научной библиотеке Санкт-Петербургского государственного университета по адресу: 199034, Санкт-Петербург. Университетская наб., д. 7/9.

Защита будет проходить в Петербургском отделении Математического института имени В.А.Стеклова РАН по адресу: Санкт-Петербург, наб. реки Фонтанки, д. 27.

Автореферат разослан

2005 г.

Учёный секретарь совета доктор физико-математических наук, Д профессор уф^—Нежинский В М.

пти

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы. Ассоциативные схемы, или схемы отношений, изучению которых посвящена настоящая работа, возникают в различных областях математики, хотя и не всегда под одним и тем же названием Так сям термин появится в работах Боуза и его коллет (1939-1959 п ) о б"ок-схема\ в рамках теории планирования с татистических экспериментов, соответсвующий объект является здесь симметричной схемой. Однако ешё ранее ь известной работе Шура (1933). заложившей основы теории Б-колец, уже появляется понятие нентралнзаторного кольца группы перестановок (которое в транзитивном случае есть не что иное, как алгебра Гекке исходной группы по стабилизатору гонки), фактически совпадающее с алгеброй смежности ассоциативной схемы специального вида Общая теория ассоциативных схем возникает независимо как теория когерентных конфигураций в работах Д Хигмана (1970), посвящён-ных изучению групп ранга 3, и как 1еория клеточных алгебр в работах Вейгфейтера и Лемана (196^,1976), посвященных вычислительной сложности проблемы изоморфизма ¡рафов В настоящее время структурная теория однородных схем развита в книге Цишанга (1995) где они называются обобщёнными группами и рассматриваются как обобщения гр^пп и билдинюв Такие схемы и их алгебры смежности доставляют наиболее важные примеры (7-алгебр (обобщающих алгебры характеров конечных групп) гипергрупп алт ебр в плашиерелевой двойственности и многозначных групп Охметим также появившиеся в последнее время работы Джа-герй Баннаи и др , посвяшёнчые построению инвариантов зацеплений и узлов на основе теории ассоциативных схем Наконец, упомянем обнаруженные автором неожиданные связи между теорией схем отношений и задччей эффективного разложения многочленов на множители над конечным полем (1994).

Многие задачи теории схем отношений, называемых далее также про-< ю схемами в той и 1и иной степени связаны с изучением их групп автоморфизмов и с построением различного рода систем инвариантов изоморфизма В контексте теории групп перестановок упомянем в этой связи известную работу Д Хигмана (1970), пехвящённую характеризации классических групп ранга 3 в терминах их подстепеней Ещё одним примером является подход к описанию конечных простых групп как групп автоморфизмов подходящих схем отношений В рамках алгебраической комбинаторики (сравнительно недавно возникшей области математики) одна из важнейших задач состоит в нахождении необходимых и доста-ючных условий того, чтобы данный дистанционно-регулярный граф был дистанционно-транзитивным Уже упоминавшаяся выше проблема изо-мопсЬизма гпасЬов. одна из А V и л а м е нзд^ ь нь чл * * и < их проблем со-

1 БИБЛИОТЕКА |

еяеъ

временной теории сложности вычислений, является специальным случаем проблемы изоморфизма схем. Идейно близкой к рассматриваемой проблематике оказывается и задачи из программной работы Р Брауэра (1963) по теории представлений конечных групп, а именно, какую информацию необходимо добавить к таблице характеров конечной группы, чтбы получить рр полное множество инвариантов

Анализ этих, а также и ряда других задач алгебраической комбинаторики естественным образом приводит к двум следующим проблемам Первая из них восходит к Виландту (1963), который интересовался, при каких условиях данное Э-кольцо возникает из подходящей группы перестановок с регулярной подгруппой В общей теории схем отношений ^та проблема сводится к выяснению того, совпадает ли данная схема со схемой 2-орбит своей группы автоморфизмов В чесгь Шура, имевшего де ло с объектами только такого рода, её называют проблемой шуровости Вторая проблема, называемая ниже проблемой отделимости, заключа ется в нахождении условий, при которых данная схема определяется с точностью до изоморфизма своими числами пересечений. Фактически, ббльшая часть работ последнего времени но алгебраической комбинаторике (включая известную монографию Баннаи и Ито, 1984) посвящена решению этой проблемы для специальных классов однородных схем. большинство из которых коммутативны и даже симметричны Исследование двух указанных выше проблем и составляет основное содержание настоящей диссертации.

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

Цель работы. Построение теории многомерных расширений схем отношений и применение её к исследованию проблем шуровости и отделимости, а также в задаче эффективной факторизации многочленов над конечным полем В рамках теории схем исследование в-колец над конечной циклической группой и, в частности, гипотезы Шура-Клина о таких кольцах. Алгебраическая аксиоматика схем отношений.

Методы исследований. Применяются общие методы теории групп перестановок. теории представлений групп и алгебр, теории конечных полей, а также новые методы, предложенные автором, включая обобщение метода инвариантных отношений, введённого Виландтом

Научная новизна. В диссертации получены следующие новые результаты

1 Пос троена теория многомерных расширений схем отношений- в рамках чтой теории для произвольной схемы введены и изучены числа шу-ровости и отделимости. характеризующие соответственно её близость к схеме 2-орбит группы перестановок, и близость её подобий к подобиям, индуцированным изоморфизмами.

2 Получены оценки сверху чисел шуровости и отделимости ряда схем отношений с классическими параметрами В частности, показано, что для схем Джонсона, Хэмминга и Грассмана эти числа не превосходят 2.

3 Доказано, чго число отделимости произвольной циклотомической схемы на конечном поле не превосходит базового числа её группы автоморфизмов и, как следствие, не превосходит 3.

4 Построены примеры семейств схем отношений с произвольно большими числами шуровости и отделимости.

5 Введены и полностью охарактеризованы нормальные Б-кольца над конечной циклической группой, что позволило уточнить классификацию произвольных Б-колец над такими группами.

6 Доказано, что класс всех Б-копец над конечными циклическими группами не является ни шуровым, ни отделимым. В частности, опровергнута ипютеза Шура-К шна о юм, что каждое Б-кольцо над конечной циклической группой возникает из подхолящей группы перестановок, содержащей эту циклическую группу в качестве регулярной под1руппы

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

8 Развита теория алгебр в планшерелевой двойственности и показано, чю она включает в себя как теорию клеточных алгебр, так и теорию Б-колец.

9. В предположении обобщённой гипотезы Римана построен детерминированный алгоритм квазиполиномиальной сложности для разложения на множители произвольного многочлена над конечным полем

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

Апробация работы. Основные результаты диссертации многократно докладывались и обсуждались на алгебраическом семинаре им Д К.Фад-деева (СПбГУ), на семинаре по теории сложности вычислений (ПОМИ), на семинаре по теории представлений и динамическим системам (ПОМИ),

на семинаре по информатика и компьютерным технологиям (СПИИРШ;, на университетском семинаре по алгебраической комбинаторике i Эйн дховена (Нидерланды) и на университетских математических семинарах г Ренна (Франция) и гг Бонна и Мюнхена (Германия) а также бы m представлены на следующих конференциях'

1 Международная конференция "Открытые проблемы теории ассоциативных схем", Пусан, Корея, июль 2004 г (приглашённый док чад)

2 Международная конференция по логике и вычислительной сложности (LCCS' 2001), Кретей. Франция, сентябрь 2001 г (приглашённый доклад),

3 Первый международный симпозиум по алгоритмической теории чисел (ANTS1), Итака. США май 1994 г (приглашённый доклад),

4. Международная конференция "Ассоциативные схемы, коды и дизайны" Пусан, Корея, июль 2004 г ,

5 Шестая международная конференция по приложениям компьютер ной алгебры (IMACS), Санк;-Петербург Россия, июнь 2000 г.,

6 Международная конференция "А норитмы и теория чисел" Шаосс Дагштуль, Германия, октябрь 1998 г.

7. Пятый чешско-словацкий симпозиум по комбинаторике, теории графов, алгоритмам и их приложениям, Прага, "Чехия, июль 1998 г ,

8 Международная конференция "Формальные степенные ряды л a i-1ебраиче(кая комбинаторика", Торонто, Канада, июнь 199S г .

9 Шестнадцатая британская конференция по комбинаторике (ВСС16), Лондон, Англия, июль 1997, г

10. Международная алгебраическая конференция памяш Д К Фадде-ева, Санкт-Петербург, Россия, июнь 1997 г,

11 Международная конференция "Конечные поля. теория и приложения", Обервольфах, Германия, январь 1997 г.,

12 Четвертый международный симпозиум по эффективным методам в алгебраической 1еометрии (MEGA 96). Эйндхозен Нидер 1энды. июнь 1996 г.,

13 Международная конференция памяти Л.А Катужнина "Алгебра и комбинаторика: взаимные связи и приложения". Кёнигштейн, Германия, апрель 1994 г,

14. Всесоюзная конференция но конструктивным методам и алгоритмам в теории чисел. Минск, Белоруссия, сентябрь 1989 г.

15. Всесоюзная конференция по ал) ори гмическич проблемам. Северная Осетия, сентябрь 1987 г.,

16 Седьмой венгерский коллоквиум по комбинаторике конечных и бесконечных множеств, Эгер. Венгрия, июль 1987 г.,

17 Восьмая всесоюзная конференция по магематчес к >п логике, Mot к ва сентябрь 1986 i

Практическая ценность. Работа носит теоретический хараюер Её результаты могу г быгь испо (ьзовапы в алгебраической комбинаторике, теории групп, теории чисел, рычис штрльной алгебре и теории графов, а также в теории планирования эксперимента и в математических моделях телекоммуникационных сетей связи

Публикации. Основное содержание диссертации опубликовано в 12 научных сгагьях, список которых приведён в конце автореферата.

Структура и объём работы. Диссерл яция со<" гоит из введения пяти г'лав и списка литературы, содержащего Я8 названий Общий объём дис-сертапии составляет 155 страниц

КРАТКОЕ СОДЕРЖАНИЕ РАБОТЫ

Во введении даётся обший обзор резу тьтатов, относящихся к тематике диссертации, и обсуждаются мотивировки решаемых в ней задач

Ниже для конечного множес тва V группа всех перестановок -элементов -»того множества обозначается через SymfVj, алгебра всех комплексных матриц, строки и столбцы которых занумерованы его элементами, через Maty, а единичная матрица и матрица из всех единиц соответственно через Iv и .Д- Через W\ обозначается мощность множества V

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

В этой главе приводятся необходимые для дальнейшего определения и факты из теории схем отношений и клеточных алгебр, а также форм)' лируются проблемы шуровости и отделимосги

§1.1. Общая теория. Пусть V - конечное множество и R - некоторое множество непустых бинарных отношений на нём Следующее определение принадлежит Д Хигману.

Определение 1.1. Пара С -= (V.1Z) называется когерентной конфигурацией с семой отношений или просто схемой на V, если выполнены следующие условия:

(51) 1Z образует разбиение мноэн ества V2,

(52) диагональ Mnootcecmea V2 является объединением элементов из Л,

(53) Л замкнуто относительно перестановки координат,

(54) если R, S, Т е П, mo vucao |{и € V (u,v) е R, (и, го) е S}\ не зависит от выбора пары (u,w) € Т.

Числа из условия (Б4) называются числами пересечении схемы С и обозначаются через с\ $ Элементы множеств V и Л называются соответственно точками и базисными отношениями. а мощное ги этих множеств степенью и рангом схемы С

Две схемы С ~ (V. 7?) и С — {V'.V.') называются изоморфными, ее пи IV = ТИ для некоторой биекции / : V —> V', называемой изоморфизмом схемы С на схему С. Группа

Аи1(С) = {/ е Зут(У) • /?/ - Л V/? е 71},

называется группой автоморфизмов схемы С Будем говорить что схемы С и С' подобны, если

с^ 5 = Сд^ ^у-, Д, 51,7 €7?.,

для некоторой биекции Я I—» из "Л на 7?/, называемой подобием схемы С на схему С. В данном параграфе определяются и изучаются клетки блоки, факторы, ограничения и расширения произвольных схем, а также однородные, примитивные, коммутативные и симметричные схемы, Определяются также точечные расширения схемы С являющие-

ся комбинаторным аналогом поточечных стабилизаторов в теории групп перестановок, и изучаются свойства схем, сохраняющиеся при подобиях Алгебры смежности схем отношений совпадают с клеточными алгебрами., введёнными Вейсфейлером и Леманом, то есть линейными подпространствами IV пространства Ма^, удовлетворяющими следующим условиям:

(УА) IV, Jv е IV,

(\У2) IV замкнуто относительно матричного и адамарова умножений, (\¥3) IV замкнуто относительно транспонирования

При этом числа пересечений схемы С совпадают со структурными константами отвечающей ей алгебры V/ относительно линейною базиса, состоящего из матриц смежности отношений из Л: подобия схем переходят в изоморфизмы клеточных алгебр как алгебр с двумя умножениями

§1.2. Примеры. Здесь приводятся важнейшие примеры схем отношений и клеточных алгебр, включающие ценлрализаторные ал1 ебры групп перестановок, а 1гебры Гекке, схемы сопряженных классов конечной группы (алгебра смежности такой схемы двойственна алгебре характеров) цик-лотомические схемы, схемы дистанционно-регулярных графов, схемы частичных геометрий и симметричных и квазисимметричных блок-схем, а также схемы конечных проективных и аффинных плоскостей

§1.3. Операции. Рассматриваются прямая сумма ЕВ тензорное произведение ® и сгпетение ? схем; дтя каждой из операций вычисляется группа автоморфизмов результирующей схемы и описываются подобия. Предложена новая конструкция, с помощью которой, с одной стороны, определяется сплетение семей« 1ва схем со схемой, обобщающее как прямую сумму и обычное сплетение схем, так и некоторый более сложный его вариант, рассмотренный ранее Вейсфейлером. а с другой, вычисляются многомерные расширения таких сплетений (см. §3 3)

§1.4. Шуровость и отделимость схем. Рассматриваются проблемы шуровости и отделимости схем отношений, играющие ключевую роль в данной работе Схема С на множестве V называется шуровой. если она является замкнутым обьектом при соответствии Галуа

С ^ Аи^С'), Г 1Пу(Г)

между множеством всех схем на V и множеством всех групп перестановок на V, где 1пу(Г) - схема 2-орбит группы Г, другими словами, если С — 1п\-(Аи1(С)) Проблема шуровости состоит в проверке того являет-(я ли шуровым данный класс схем ю есть является ли каждая схема из этого класса шуровой Если класс состоит из единственной схемы, то с алгоритмической точки зрения проблема шуровости сводится к задаче эффективного нахождения группы автоморфизмов этой схемы.

Пусть К. - некоторый класс схем Схема С называется отделимой относительно )С, если Ьо(С, С', 0 для всех подобий кр . С —' С, где С € К. и ко- множество всех изоморфизмов С на С. индуцирующих <р. Если при этом 1С совпадает с классом всех схем, то схема С называется отделимой Проблема отделимости состоит в проверке того, отделим ли данный ктасс схем относительно класса К то есть отделима ли относительно /С каждая схема из этого класса Особый интерес представляют отделимые классы, т.е. такие, которые отделимы относительно класса всех схем Частным случаем проблемы отделимости является также проблема изоморфизма графов - одна из наиболее известных нерешённых задач теории сложности вычислений, с одной стороны, >^Р-полнота этой задачи не доказана, а с друюй. для её решения не известно ни одного алгоритма полиномиальной сложности

Доказано, что свойства схемы быть шуровой или отделимой сохраняются при введённых выше операциях 51, и ? Кроме тою. установлено, что проблемы шуровости и отделимости положительно решаются в классе всех 1-регулярных схем, являющихся комбинаторным аналогом групп перестановок с точной регулярной орбитой (по определению каждая схема 1гз лот к пасса содержит точку, мощность окрестности которой в каждом базисном отношении этой схемы не превосходит 1)

Теорема 1.23. Любая 1-регулярная схема отделима и шурова

Приведённая теорема будет существенным образом использована в главах 3 и 4 при доказательстве основных результатов диссертации.

§1.5. Кольца Шура и схемы Кэли. Пусть G - конечная группа Схема С называется схечой Кэли над G, если Grlqht < A ut (С), где Giujht - группа перестановок на G инд\цированная правыми умножениями Категория схем Кэли над группой G естественным образом изоморфна категории колец Шура (кратко S-колец) над той же группой, то есть линейных подпространсл в группового кольца QG'j. замкнутых относительно инволюции g i— g"1, группового и адамарова умножений, а также содержащих единицы по обоим умножениям. Это позволяет перенести понятия шуровосги и отделимости со схем на S-кольца.

Для полного описания S-колец над конечной циклической группой (см. главу 4) вводится понятие нормальности.

Определение 1.30. Схема Кэли С над рруппой G называется нормальной, если G right является нормальной подгруппой группы Aul (С)

Доказано, что каждая схема Кэли, являющаяся расширением нормальной схемы Кэли над той же группой, нормальна, а тензорное произведение схем Кэли нормально тогда и только тогда, когда нормален каждый сомножитель. Более того, как показывает следующая теорема группы автоморфизмов нормальных схем Кэли над группой G суть в точности 2-замкнутые подгруппы её голоморфа G ■ Auf (G), содержащие G

Теорема 1.32. Пусть С - схема Кэли пад группой G Тогда С нормальна в том и только в том случае ее au Aut(C) < G ■ Aut(G)

Будем называть S-кольцо нормальным, если нормальна отвечающая ему схема Кзли Из полученных результатов следует, что S-кольцо А над G нормально в том и только в том случае если Aut(^) £ Aut(G), где группа Aut(.4) но определению равна сгабитизатору точки 1с; в группе автоморфизмов соответегвучощей схемы Кэли.

§1.6. Линейные представления клеточных алгебр. 3/учь изучаются свойства схем отношений, связанные с линейными представлениями их алгебр смежности (являющимися, как известно, полупростыми над С). А именно, пусть W < Mat,v - клеточная алгебра и ~P(W) - множество её примитивных центральных идемпотентов Дтя Р С V(W) обозначим через пр степень неприводимого представления алгебры W. отвечающего Р и через гпр кратность этого представления в её естественном матричном представлении. Следующая теорема, обобщает известный факт из теории представлений конечных групп.

Теорема 1.37. Пусть W < Maty - однородная клеточная алгебра Тогда

(1) пр < гпр для веет Р е V{W),

(2) равенство пр = тр выполнено для всех Р 6 V(W) тогда и только тогда, когда W - регулярная алгебра

Упорядоченный набор (п . , ¡л,) Vh называется базой схемы С на V, если схема CVli lh гривиальна. Минимальный размер базы (число 6) обозначается через Ь(С) и называется базовы м числом схемы С. База называется несводимой, если СЬи ф CVu ,v,_ 1 для всех г. Следующая теорема обобщает один результат Робинсона (1997) о примитивных группах перестановок.

Теорема 1.40. Пусть С - примитивная схема и W - её алгебра смежности Тогда размер каждой несводимой базы схемы С не превосходит гпр/пр для любого неглавного идемпотпентпа Р G V(W) алгебры W В частности,

b(C) < mm(тр/пр) < (п - 1 )/(г - 1),

где Р пробегает множество всех таких идемпотентов, an иг- степень и ранг схемы С

Доказанная теорема позволяет получить новые оценки сверху порядка группы автоморфизмов примитивной (хемы (а потому и примитивной i руппы перестановок) в терминах степеней её базисных отношений и их двойственных аналогов

Следствие 1.47. Пусть С - примитивная схема степени п. Тогда

\ Aut(C)| < n{dmiTlf......| Aut(C)| < n(dmm)d- I Aut(C)| < n(dav)l-"~\

где dmin и dav (соотв. dmin и dav) - минимальная и средняя степени (соотв минимальная и средняя двойственные степени) схемы С.

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

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

§2.1. Обобщённые С-алгебры. Коммутативные С-алгебры (алгебры характеров) в связи со схемами отношений рассматривались в монографии Баннаи и Ито (1984) Позже был определён их некоммутативный

аналог. Заметим, что во всех этих случаях схемы отношений, приводящие к С-алгебрам такого типа, обязаны быть однородными Для того, чтобы охватить и неоднородный случай мы вводим понятие обобщённой С-алгебры Пусть А - ассоциативная алгебра над С с единицей 1, полулинейным инволютивным антиавтоморфизмом * и выделенным линейным базисом 72. Предположим, что для некоторого конечного множества I имеется разложение 72 — причём множества 72, 3 попарно

дизъюнктны и

A,jAm С Sj,kA,h l,J,k,l£l,

где A%:J - линейная оболочка множества 72,; и 6 - сим-вол Кронекера.

Определение 2.1 Пара (А,71) называется обобщённой С-алгеброй если выполнены следующие условия:

(СП) 1 = где е, S 72,,,, и (72м)* = 72,, для всех i,j е I,

(С2) структурные константы с'«, алгебры А относительно базиса 1Z вещественны,

(С3) для любых г 6 72, ^ и з 6 72Jit имеет место равенство c®*s = d(r)Sr\s-где rf(r) > О,

(С4) существуют положительные числа пг,г £ I, для которых линейное отображение (rf4) Л —> Mat/ такое, что с]г ) = nj2n~ если г е 72,,.,, и 0 в противном случае, является ^-гомоморфизмом

Под изоморфизмом обобщенных С-алгебр мы понимаем ^-изоморфизм соответствующих алгебр, сохраняющий базисы. Если |/| — 1, то обобщённая С'-алгебра называется однородной, или просто С-алгеброй.

Каждая пара (Л, 71), где А - клеточная алгебра и 71 - её стандартный базис из {0,1}-матриц, является обобщённой С-алгеброй (I равно множеству клеток соответствующей схемы), у которой все структурные константы неотрицательны. Более того, если алгебра А коммутативна, то неотрицательны также и её константы Крейна, т е. структурные константы двойственной С-алгебры Это мотивирует следующее определение. Обобщённая С-алгебра {A,TV) называется положитеяьной, если

(Р1) все структурные константы г' алгебры Л относительно базиса 71 неотрицательны,

(Р2) конус Л+ = {ао* : а € Л} неотрицательных элементов алгебры А замкнут относительно покоординатного умножения, определяемого базисом 71.

Теорема 2.5. Для любой клеточной алгебры отвечаюу^ая ей обобщённая С-алгебра является положительной

§2.2. Спаривание и его свойства. Этот параграф является вспомогательным для следующего, в котором клеточные алгебры описываются как алгебры в планшерелевой двойственности Пусть А, В - полу простые конечномерные ^-алгебры над С с единицами Ц и и

билинейная форма, приводящая их в невырожденную двойственность как линейные пространства над С.

Спаривание (1) называется положительным, если конусы

к \ = {% & А ■ (х, /) > о V/ е В+}, Кв = {! ев (х, /) > о у* б Л+},

двойственные к конусам В+ — {//* : / € В] и А+ = {хх* : х £ А}, замкн\ты относительно умножений и инволюций в алгебрах А и В соответственно Г1о двойственности положительность спаривания равносильна тому, что коумножения 5а и 5д и коинволюции г]а и г\в являются положительными отображениями (на самом деле положительность ко-инволюций следует из положительности коумножений и в этом случае первые являются даже ^-изоморфизмами).

В теории алгебр Хопфа одно из коумножений (а тогда автоматически и второе) является по определению *-гомоморфизмом алгебр Поскольку *-юмоморфизм есть положительное отображение, аксиоматика положительных спариваний представляет собой естественное ос чабление аксиоматики алгебр Хопфа.

Далее, пусть I - конечное множество и

симмехри'шые разложения единиц в алгебрах А и В (такие, д ¡я которых е* А — и е* в = е^в при всех /) Будем говорить, что разложения (2) согласованы со спариванием (1), если (Аг0, 5а,,;) — {0} для всех (^з) Ф (кЛ) и прямые разложения А = Шг^е/и В — Вг 3

устойчивы относительно действия инволюций (а потому и коинволюций) в обеих алгебрах, где А1}] — е^дЛт7л(е51л), В1а = ег1вВг)в(е}1в)- Положим

1А = {х £ А (х.е^ц) =0, £ /},1в = {/ € В. (ем,д./) = 0. г.] € /}, где е, л = А) и ег>7,в = е1,в'Пв{е],в)-

{, ) : Ах В-» С

(1)

(2)

Спаривание (1) называется клеточным относительно согласованных с ним разложений единиц (2), если 1а а 1ц - Д1ттороннис идеалы в алгебрах А и В соответственно и, более того, линейные отображения

Спаривание называется клеточным, если существуют согласованные с ним разложения единиц, относительно которых оно клеючно и более того, однороднъм. если |/| = 1. Гомоморфность отображений <1а и ¿в означает соответственно, что

Пусть хд и Хв ~ положительные следы на алгебрах А я В Будем говорить, что спаривание (1) изометрично относительно \А и хв, если преобразования Фурье В^а А —* В и Рв В —> А, определяемые формулами

являются изометриями между гильбертовыми пространствами {А, (, )а) и (В,(, )и), связанными со следами ха и хв- Спаривание называется изометричным, если оно изометрично относительно некоторых положительных следов Отметим, что изометричность отображений Т7^ и Рв эквивалентна естественным соотношениям ортогональности в алгебрах В и А соответственно

§2,3. Планшерелева двойственность. В -пом параграфе устанавливается связь между алгебрами в планшерелевой двойственности и основными объектами алгебраической комбинаторики

Определение 2.10. Будем ?оворить, что две *-плгебры А и В, спаренные посредством (1), нагодятся в плапыерелевой двойственность, есль спаривание положительно, клеточно и изометрично. В этом случае спаривание (, ) называется планшерелевым

Понятие планшерелевой двойственности восходит к Кирову (1974], который фактически определил и изучил его в однородном случае. Определение Керова. однако, несколько отличается от приведённого выше, поскольку планшерелевость у него не была явно выражена через свойства спаривания

йА А —> Ма(;/, (ёА)г0{х) = п^/х,

(х,РА(у)) = (х,ч)А. (Рв(д),Л = (!,д)в,

Удобно иметь дело с планшерелевыми тройками, то есть такими тройками (Л, £?,(, )), для которых спаривание (. ) планшерелево. Под изоморфизмом троек мы понимаем пару изоморфизмов между соответствующими алгебрами, сохраняющих билинейные формы. Тройка называется однородной, если спаривание однородно.

Если Т = (Л,В,{, )) - планшерелева тройка, то найдутся согласованные разложения единиц 1 А = е,,л и 1 в = е»,в> относительно которых спаривание клеточно, и положительные следы ха и Хв> относительно которых спаривание изометрично. Доказывается, что следы ха и хв по существу определены однозначно и для каждого г € / элементы алгебр В1Л и Лм, задаваемые по двойственности их ограничениями соответственно на алгебры А1г и пропорциональны некоторым примитивным центральным идемпотентам тг,в и тг а- Если одна из алгебр Л, В коммутативна и {т%1А^г,в) — 1 Для всех г, т<э такую тройку Т будем называ1ь нормализованной. Следующее утверждение, вскрывает в силу теоремы 2.5 алгебраическую природу схем отношений.

Теорема 2.14. Категории положительных обобщённых С-алгебр и нормализованных тианшерелевых троек, в которых одна из алгебр (например, вторая) коммутативна, эквивалентны

Особый интерес представляют планшерелевы тройки Т = (Л, В, (, )), у которых коумножения и 5 в обладают определённым свойством гс> моморфности. Положим

Т' = (Л,В, (,)'). где (х,/у = п;](х,1), хеАг,„!еВг,3.

Будем называть тройку Т обобщённой тройкой Хопфа, если коумножения и отвечающие Т', являются гомоморфизмами алгебр, и просто тройкой Хопфа, если дополнительно 5'а(1а) — 1д®1л и <5'в(1в) = 1в?Лв, т е , если она однородна Примерами троек Хопфа и обобщённых троек Хопфа являются соответственно групповые и матричные тройки, возникающие естественным образом из групповых алхебр конечных групп и полных матричных алгебр (в обоих случаях второе умножение покомпонентное).

Теорема 2.15. Каждая нормализованная обобщённая тройка Хопфа, в которой вторая алгебра коммутативна, изоморфна прямой сумме тензорных произведений групповых и матричных троек. Более того, каждая нормализованная тройка Хопфа с тем же свойством изоморфна некоторой групповой тройке.

Таким образом, клеточные алгебры и Б-кольца можно рассматривать как подтройки соответственно матричных и групповых троек, т е. элемен-

тарных нормализованных обобщённых тройка Хопфа, в которых вторая алгебра коммутативна.

§2.4. Многозначные группы. Пусть X - множество и (Х)п - его пая симметрическая степень. Следуя Бухштаберу (199а). под л-значной группой X на X понимается отображение 1x1-» {Х)п. играющее роть умножения и обладающее такими свойствами, как ассоциативность, существование единицы и слабого обратного элемента При п = 1 мы получаем обычную группу Одним из примеров явтяется п-значная косетная группа на множестве орбит группы автоморфизмов порядка п некоторой группы, представляющая собой частный случай конструкции Дельсарта

Обнаружена тесная связь теории многозначных групп с алгебраической комбинаторикой. А именно, с одной стороны, естественное усиление аксиомы обратного элемента приводит к понятию инволютивной многозначной группы, а с другой, вводятся в рассмотрение комбинаторные алгебры, т е. С-алгебры, все структурные константы которых суть неот-рицатетьные рациональные числа (в бесконечномерном случае требуется ещё некоторое условие ограниченности) Для каждой инволютивной многозначной группы X на множестве X определим С-алгебру А(Х) как групповую алгебру этой группы с выделенным базисом X (подходящим образом нормированным) и для каждой комбинаторной алгебры А обозначим через Х(А) многозначную группу, .множество элементов которой совпадает с выделенным базисом атгебрьт, а умножение индуцировано её умножением.

Теорема 2.22. Отображения X ¡—> А(Х), А >—> Х(А) задают эквивалентность между категориями инволютивных многозначных групп и комбинаторных алгебр

Используя доказанный результат, мы строим бесконечное семейство трёхэлементных многозначных групп и получаем для них проостой критерий косетности что даёт новые нетривиатьные примеры некогетных многозначных групп.

Глава 3. Многомерные инварианты схем

В этой главе строится теория многомерных инвариантов схем отношений; в рамках этой теории определены и изучены числа шуровости и отделимости схемы, характеризующие соответственно близость этой схемы к схеме 2-орбит группы перестановок, и близость ее подобий к подобиям, индуцированным изоморфизмами.

§3.1. Многомерные расширения схем и подобий. Известно, что проблема изоморфизма в классе всех графов полиномиальна эквивалентна

задаче нахождения труппы автоморфизмов графа (Бабаи. 1995), которая, в свою очередь, эквивалентна задаче построения шурова замыкания схемы, т. е. схемы 2-орбит её группы автоморфизмов Попытки алгоритмического решения последней привели к различного рода многомерным конструкциям (Фридпанд, 1989, Вейсфейлер, 1976) Однако, как выяснилось в ряде работ автора, посвященных проблемам шуровости и отделимости. имеется универсальный алгебраический объект, с помощью которого удаётся не только интерпретировать как упомянутые выше конструкции, так и известные характеризации классических ассоциативных схем, но и получать новые результаты (см. главу 4).

Определение 3.1. Для натурального числа т назовём гп-расширением схемы С наименьшую схему С'т' на \гт, где V - множество точек схемы С. содержанию т-ую тензорную степень Ст схемы С и рефлексивное отношение, отвечающее диагонали множества \'т

Ситуация та же что и в теории групп перестановок Подобно тому, как для изучения гр\ппы Г £ 'Зут(У) полезно рассматривать её естественные действия на Ут при различных т (каждое такое действие совпадает как группа перестановок со стабилизатором диагонали этого множества в группе Гт). так и для получения информации о шуровом замыкании и симметриях схемы отношений мы рассматриваем её т-расшир^ния Аналогично, поскольку очевидно, каждый изоморфизм схем индуцирует изоморфизм их ттг-расширений, для получения информации об изоморфизмах естественно ограничиться рассмотрением лишь тех подобий, которые расширяются до подобий т-расширений.

Определение 3.2. Подобие ■ф : С(т) —* ¿'(т) называется т-росишре-нием подобия р ■ С —» С, если на Ст оно совпадает с т-ой тензорной степенью р и переводит диагональ в диагональ.

Отметим, что схема С(т> существенно неоднородна, группа Аи^С'"')) канонически изоморфна зруппе АиЦС) и С(Г> = С для всех С. Более того, в случае своего существования т-рагширенис р<-т'1 подобия у> определено однозначно и — для всех р

§3.2. Числа отделимости и шуровости. Здесь определяются и изучаются числовые инварианты схем и подобий, связанные с т-расширениями. Мы говорим, что схема С на V является т-замкнутой, если она совпадает со схемой С-[т , полученной естественным переносом на V ограничения схемы С('н) на диагональ множества У"1. Аналогично подобие схем называется т подобием, если оно имеет гг)-рэ( ширение Множество всех -по юбий схемы С на осему С' обозначим через 5нпт(С С)

Теорема 3.7. Для любых схем С и С' степени п справедливы (леду-ющие утверждения-

с = с(:) < . <cw = . = ct0G),

Sim(C,C') = Sinn (С, С') D ... D Simn(C,C') = ...= SimХ{С,С'),

где С^ - схема 2-орбит группы Aut(C) и Sim00(C,(T') - множество всех подобий схемыС на гхемуС, индуцированных изоморфизмами этих схем.

Схема С называется т-шуровой, если С<т> = с'00', и т-отделимой относительно некоторого класса К схем, если Simm(C,C') — 1Sim00(C.C') для любой схемы С из /С. Если при эюм 1С совпадает с классом всех схем, то схема С называется тп-отделимой Натуральные числа

t(C) = тт{т • С — m-шурова}. s(C) — min{m • С — тп-отдепима}

называются соответственно числом шуровости и числом отделимости схемы С

Из теоремы 3.7 следует, что 1 < t(C) < п и 1 £ s(C) < п для всех схем С. Очевидно. t(C) 1 (соотв s(C) = 1) юма и только тогда, ко1да схема С шурова (соотв отделима) Удивительным и нетривиальным оказывается то, что приведённая верхняя оценка асимптотически точна (см §3.4)

В обшем случае вычисление чисел шуровости и отделимости схемы С оказывается трудной задачей Справедливы, однако, стедующие оценки этих чисел в терминах её точечных расширений Си ^

Теорема 3.12. Пусть С - схема v rr> - натуральное число Если схем,а CVl, ,и,„_1 является 1-регулярной для некоторых точек Vi, ,vm~i, то s(C) <т и t(C) <rn. В частности, s (С) < 6(C) + 1 и t(C) < 6(C) t- 1, где b(C) - базовое число схемы С

Доказательство следующей теоремы использует результаты §3 3

Теорема 3.14. Пусть С\, Сч - схемы и С - любая ггз схем С\ ЕЕ Сг, Ci ®С2, Ci }С2 Тогда s(С) - max{s(Ci), s(C2)} и t(C) = max{i(Ci), ¿(Co)}

Сделаем несколько замечаний о взаимосвязи между отделимостью и характеризацией схем. Говоря о том, что числа пересечений схем С и С одинаковы, мы всегда имеем в виду, что задано некоторое подобие • С С Таким образом, схема С характеризуется своими числами пересечений тогда и только тогда, когда ь(С) = 1 Такое понимание харак-теризации схем полностью согласуется с точкой зрения принятой в книге Баннаи и Ито Далее, числа пересечений схемы удобно рассматривать как m-мерные числа пересечений схемы С В этом случае естественно считать m-мерные числа пересечений схем С и С одинаковыми, если

числа пересечений схем С и С' одинаковы и соответствующее подобие <р имеет то-расширение. Таким образом, схема С характеризуется своими т-мерными числами пересечений (числами пересечений схемы С(ттогда и топько тогда, когда «(С) < тп

§3.3. Поведение при операциях. В этом параграфе вычисляются т-расширения прямой суммы и тензорного произведения схем, а также сплетения семейства схем со схемой. Это позволяет в каждом из случаев получить критерии т-замкнутос1и и т-шуровости результирующей схемы. В качестве другого следствия удаётся вычислить т-расширения подобий этой схемы и дать критерий ее те-отделимости. Для доказательства результатов параграфа используется вспомогательная схема из §3.1.

§3.4. ПсевдпотделимьIе и псевдошуровы схемы. Целью параграфа является доказательство следующей теоремы

Теорема 3.29. Существуют схемы с произвольно большими числами отделимости и шуровости Более того,

ИтЫ" ^ > 0, НтЫ1 Щ- > О,

п(С)-*ос П(С) п(С)->оо П(С)

где С пробегает класс всех схем и п(С) - степень схемы С Оба неравенства остаются справедливыми и в том случае, когда С пробегает класс всех однородных схем, а в случае первого неравенства - дао/се шуровых однородных схем.

В основе доказательства лежит конструкция специальных схем отношений, каждая из которых допускает группу автоморфизмов, индуцированную полурегупярным действием четверной группы Клейна с достаточно большим числом орбит, и с точностью до изоморфизма определяется некоторым кубическим графом на множестве своих клеток (орбит этой группы) При этом, если граф трехсвязен, то схема шурова, а ее подобие, связанное с "переключением"в окрестности одной вершины, не индуцируется никаким изоморфизмом. Выбирая в качестве таких графов опре-де генные семейства экспандеров (частным случаем экспандера является граф Рамапуджана) и используя имеющий явный когомологический характер достаточный признак ш-подобия, мы доказываем первое неравенство теоремы Нешуровы схемы, требуемые для доказательства второго неравенства, строятся как сплетения семейств шуровых схем из описанного класса, связанных построенными выше подобиями, со схемой степени 2. При этом используется критерий т-шуровости сплетения из §3.3

§3.5. Многомерные расширения и (К, Л)-регулярность графов.

Пусть Л - подграф графа К и (1 > 0 - целое число. Граф Г называется

(К, Л) -регулярным степени д, если ¡юбое вложени° 'V ч Г продолжается до вложения К в Г ровно с/ способами (К, Л) регулярность есгсс [ванным образом обобщает понятия регулярности и сильной регулярности 1рафа, а также свойство графа локально быть графом определенного типа. Граф схемы отношений не всегда является (К, Л)-регулярньгм для нетривиальных К и Л и потому удобно рассматривать регулярность относительно бинарных отношений па Ут, 1де V множество вершин графа Г и тп -натуральное число. При этом Г еегь 'К Л)-регулярный граф степени с1 тогда и только тогда, когда Г есть (К, А)-регулярный граф степени (I относительно (Ут)2.

Теорема 3.34. Пусть Г - граф С = С(Г) - его схема и гп - натурало-по( число Тогда для всех допустимых К, А, с! имеют четп следуыил/г утверждения.

(1) Г есть (К, А)-регулярпый граф относительно любого базисного отношения схемы С^ для всех допустимых графов К и Л,

(2) если Г есть (К, к)-регулярный граф относительно базисного отношения Я схемы С(ш) и - т-подобие схемы С, то Г'"3 егть (К, А)-регулярный граф той же степени относите гьчо отношения В?1 '

Развитая техника исполь зуек я д 1я анализа Мч ловия введенного для сильно-регулярных графов Д Хигманом (1970] и перенесенного на раскрашенные графы Клином (1994). На нашем языке граф Г удовлетворяет ¿-условию тогда и только илда, ко! да он являеи я (К, Л)-ре1 улярньш для всех графов К с не более чем t вершинами и всех его подграфов А с не более чем 2 вершинами и одним ребром.

Теорема 3.36. Раскрашенный граф т-замкнутой сг^мы удовлетворяет Зт-условию

В качестве с теделвия получаем, что для любой схемы С степени п справедливы неравенства з(С) £ [гс/3"1 и ¿(С) < \п/3]

§3.6. Отделимость и шуровость классических схем. Применение теории (К, Л)-регулярности к схемам с классическими параметрами даёт следующее утверждение.

Теорема 3.38. Пусть С - схема дистанционно-регулярного графи с параметрами графа Джонсона или Хэмминга, или с сема Грагсмана Тогда ¿^С) < 2 и ¿(С) < 2.

В действительности, если С - схема Джонсона, Хэмминга или Грас-смана, то, очевидно. ОС.) = 1 Более того, в первых двух с лучаях в(С) = 1 тогда и только тогда когда С отлична от схем соответственно Чанга

или Дуба, для которых оба чиста равны 2 В случае схемы Граггмана доказательство опирается ira хорошо известную характер« ¡ацию ! рафа Грассмапа в терминах его подграфов которая фактичег к и означает его 'К Л)-рс'гулярнос ib для подходящих графов К и А Это даем возможность нспользоват1> результаты §3 5

§3.7. Отделимость и шуровость схем конечных плоскостей. В ?том параграфе изучаются отделимость и шуровость схем конечных проективных и аффинных плоскостей, опреде зенных в 2

Теорема 3.45. Пусть С схема конечной проективной плосгости "оряОьа q. Тогда ь(С) £ 5 г log2 !og2 q и t(C) < 5 + log2 lo«2 q.

Вычисления показывают, чго схемы всех проективных плоскостей пс-рядка 9 являются 2-замкнутыми, и потому в силу п'оремы 3 36 их графы удовлетворяют 6-условию. Это даёт первые примеры дистанционно-регулярных, но не дистанционно-транзитивных графов диаметра 3 удовлетворяющих 6-условию

Теорема 3.46. Пусть С - схема ■конечной аффинной плоскости Тогда ь(С) < 2 и t(C) < 2

Теорема является непосредственным следствием того, что ь{С) £ 2 и НС) < 2 для любой импримитивной 3/2-однородной схемы С

Глава 4. Циркулянтньте S-кольца и отделимость циклотомических схем

В этой главе оценивается сверху число отде шмости произвольной цик-чотомической схемы на конечном поле, характеризуются нормальные S-кольца над циклической группой и опровертается гипотеза Шура-Клина

§4.1. Циклотомические схемы и нормальные схемы Кэли. Пусть F - конечное по ю порядка q и H - подгруппа индекса m его мультипликативной ipynnbi У. Схема С на F с базисными отношениями

Ra = {(х,у) € F2 ■ х-у£аН} a£f

называется цик ютомичесгой Схемы такою типа были введены Дель-сарлом и позднее Макконнел доказал, что

Aut(Cj < {х ^ ох" + Ь, х € F а е Я, b h F, сг € Aut(F)} (3j

для любой собственной (т.е ранга, большего 2) пиклотомической схемы С В этом параграфе для каждой пиклотомической схемы С опреде шют ся две вспомогательные схемы Кэли С* и С* над группами соответственно

G — F* и Г = AGLi(Fj. При этом имеет место следующее утверждения, которое будет использовано в §4.7 для вычисления числа отделимости схемы С.

Теорема 4.1. Пусть С - собственная цикл от омическая схем,а на конечном поле F. Тогда имеют место следующие утверждения.

(1) Aut(C*) < G Aut(F) и Aut(C*) < Г • Aut(F); в частности, схемы Кэли С* и С* нормальны,

(2) G - блок схемы С* и (C*)G > С*,

(3) схемы Си и С* (соотв. С^ и С*) шуровы или нет одновременно

§4.2. Обобщённые сплетения S-колец. Здесь мы определяем операцию обобщённого сплетения S-колец, которая независимо была введена под именем "wedge product"Леунгом и Маном Пусть G - конечная группа и L.U - её подгруппы, причём L < U и L нормальна в G. Кроме того, пусть .4-1 и Л2 - S-кольца над группами U и G/L такие, что (Ai)[j/l = («4г)г//ь- Доказано, что существует наименьшее S-кольцо А над группой G, для которого Ли — ^ti и Aq/l — Дг- Оно называется обобщённым сплетением S-колец А\ и Ai (нетривиальным, если L ф {1} и U Ф G). Грубо говоря, S-кольцо Л получается, отождествлением фактор-S-кольца первого операнда с под-Э-кольцом второго. В частности, если U = L, то схема Кэли, отвечающая кольцу Л. является стетением схем Кэли. отвечающих Л\ и Ai-

Пусть Л к Л' - S-кольца над группами G и G", являющиеся обобщёнными сплетениями S-колец Л\ и Л2 над группами U и G/L, и S-колец Л\ и Л'2 над группами U' и G'/Ь'. Доказано, что отображение

V >-* (<PU,<PC/L)

задаёт биекцию между множеством слабых изоморфизмов 1р : А А' таких, что <ри(Ац) = А'ц, и <Pg/l[A-g/l) — и множеством пар

(•УъУг) слабых изоморфизмов ipi : А\ —» Л\, р2 ' Л2 > Л'2, для которых (ipi)u/l — (4>2)u'/l'• Более того, если /i,/2 изоморфизмы Кэли соответственно из Ли в А'ц, и из Aq/i в A'g,/L,, совпадающие на U/L, то существует целое семейство сильных изоморфизмов / из А в А! таких, что fu = /1, fa/L — /2- В частности, кольца Л и Л' сильно изоморфны

Отметим, что S-кольцо А над группой G является обобщённым (плетением тогда и только тогда, когда найдутся подгруппы L, U группы G, как и выше, такие, что

(1) Ь.и € ЩА).

(2) I < ш(\{Х) для всех X е в (А) таких, что X С С\1г,

1Др гас!(ЛГ) -- {д £ С ■ дХ = Хд = X}, 5(Д) - множество базисных ветичин кольца А и Н{А) множество подгрупп группы С, каждая из которых явтяется объединением базисных величин В этом случае мы говорим, что А удовлетворяет II/Ь-условию

§4.3. Циркулянтные Э-кольца. Б-кольца над конечной циклической группой (кратко, циркулянтные 5-кольца) интенсивно изучались в рамках алгебраической комбинаторики. Однако лишь сравнительно недавно появилась удовлетворительная теория таких колец. А именно, Леунгом и Маном (1998) было доказано, что каждое циркулянтное Б-кольцо может быть получено из орбитных Б-колец и Б-колец раша 2 с помощью операций тензорного произведения и обобщённого сплетения (Б-кольцо над группой С называется орбитным, если все его базисные величины являются орбитами некоторой группы К <

Поскольку каждое нетривиальное обобщённое сплетение имеет достаточно много автоморфизмов (т.е. автоморфизмов отвечающей ему схемы К эли, фиксирующих единицу группы), эго приводит к следующему интересному утверждению.

Теорема 4.13. Пусть А ~ в-кольцо над циклической группой (7. Тогда Ат(_4) = {1} в том и только в том случае, если А = С [О]

В завершение параграфа устанавливаются два необходимых условия нормачьности циркулянт ного Б-кольца, которые будут использованы при доказательстве критерия нормальности.

Теорема 4.14. Пусть А ~ нормальное 5-кольцо над циклической группой С Предположим, что А нетривиально удовлетворяет и/Ь-условию для некоторых подгрупп Ь и II группы С. Тогда \Ь\ — \С/11\ = 2

Теорема 4.15. Каждое нормальное циркулянтное Б-кольцо является орбитным, причём порядок его радикала не превосходит 2.

Здесь радикалом циркулянтного Б-кольца мы называем группу гаг](А). где X - базисная величина этого кольца, содержащая единицу

§4.4. Критерий нормальности и его следствия. Сформулируем основной результат главы о нормальных циркулянтных Б-кольцах, который доказывается в §4.5. Ниже для простого числа р через Ср обозначается си ювская р-подгруппа циклической группы С, группа Аи^С^) естественным образом отождествляется с подгруппой группы Аи(:(С) Под

радикалом гас!^) 1руппы К < Аи^С) мы понимаем радикал орбит ног о Б-кольца этой группы.

Теорема 4.16. Пусть С - схема Кэли над циклической группой С и А - отвечающее ей Б-кольцо. Тогда следующие утверждения равносильны

(1) схема Кэли С нормальна (эквивалентно, Б-кольцо А нормально),

(2) Су = 1пу(АГ, С) для некоторой группы К < Аи^С), где V = 1<-7';

(3) А орбитное кольцо некоторой группы К ^ Аи^С) такой, что | гас1(/<")) < 2 и группа АаЬ(Ср) не содержится в К для всех простых р > 5 с условием \СР\ = р

Следующие утверждения выводятся из критерия нормальности. Следствие 4.18. Пусть С? - циклическая группа. Тогда отображения

Г 1пу(Г), С ^ Аи(;(С)

определяют биекцию между 2-замкнутыми подгруппами голоморфа группы С, содержащими С, и нормальными схемами Кэли над С

Следствие 4.19. Радикал циркулянгпного Б-кольца тривиален то гда и только тогда, когда это кольцо равно тензорному прои ¡ведению нормального Б-кольца с тривиальным радикалом и Б-колец ранга 2

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

Теорема 4.20. Каждое циркулянтное Б-кольцо может быть полу-чено из нормальных Б-колец и Б-колец ранга 2 с помощью операций тензорного произведения и обобщенного сплетения

Как будет доказано в §4.8, класс всех циркулянтных Б-колец (соотв. циркулянтных схем Кэли) не является ни шуровым, ни отделимым (соотв самоотделимым). Ещё одно следствие теоремы 4 16 показывает, что в предположении нормальности ситуация в корне иная

Следствие 4.24. Класс всех нормальных циркулянтных Б-колец (соотв. нормальных циркулянтныг схем Кэаи) является как шуровым, так и отделимым (соотв. самоотделимым).

§4.5. Доказательство критерия нормальности. Этот параграф посвящен доказательству теоремы 4.16.

§4.6. Одна техническая теорема. В этом параграфе мы доказываем техническое утверждение об Б-копьцах специального вида над группой

А0Ь1(Р). которое будет использовано в §4 7 для вычисления схемы С*, определённой в §4 1

Теорема 4.28. Пусть Р - -конечное поле, Г — А ■ й - полупрямое произведение аддитивной группы А этого поля на его мультипликативную группу С и 9 - элемент группы Г с А-компонентой и С-компонентой — . Предположим, что А есть Б-колъцо над группой Г такое, что

(1) <3,в<?в е ЩА),

(2) Ас, и ~ орбитные кольца некоторой группы К < Аи^Р), Тогда А - орбитное кольцо группы К.

§4.7. Отделимость циклотомических схем. Следующие три утверждения, первое из которых говорит о том, что все многомерные и точечные расширения циклотомической схемы шуровы, представляют основные результаты главы 4 о циклотомических схемах. Ниже для группы перестановок Г через Ь(Г) мы обозначаем её базовое число, т.е. минимальное число точек, для которых подгруппа группы Г, оставляющая на месте каждую из них, тривиальна.

Теорема 4.34. Пусть С - циклотомическая схема на конечном попе Р. Тогда

(1) Ъ{С) = Ь(АиКС)),

(2) С%1< = 1пу(Аи1(С)1)1, ¡) для всех т > 1 и у\,..., ьт-г & V,

(3) С1™* = 1пу„г(АЫ(С)) для всех т> 1

Теорема 4.35. Пусть С - циклотомическая схема на конечном поле Тогда ъ{С) < Ь{АиЦС)).

Вторая теорема является следствием первой и оценки числа отделимости, доказанной в теореме 3 12. Для доказательства же первой теоремы с помощью критерия нормальности и теоремы 4.28 предварительно устанавливается, что схемы С* и С* шуровы, а затем используются свойства 1-регулярных схем Следующее утверждение, показывающее, что каждая циклотомическая схема с точностью до изоморфизма определяется уже своими 3-мерными числами пересечений непосредственно вытекает из теоремы 4.35 и результата Макконнела (см (3))

Следствие 4.36. Число отделимости любой циклотомической схемы не превосходит 3.

§4.8. Отделимость и шуровость циркулянтных Я-колец. Гипотеза

Шура-Клина. В 1933 году И Щур. используя введённый им мех од 5-колец, показал, что каждая примитивная группа перестановок, содержащая регулярную циклическую подгруппу составного порядка, является дважды транзитивной Сам Шур длительное время считал, что каждое Б-кольцо определяется подходящей группой перестановок. Это предположение оказалось, однако, неверным и первые контрпримеры были найдены Виландтом. Отметим, что все эти контрпримеры являются Э-кольцами над нециклическими группами Принимая во внимание то, что сам Шур работал в основном с Б-кольцами над циклической группой, и тот факт, что такие Э-кольца являются шуровыми, если порядок группы равен степени простого числа или произведению двух различных простых чисел (Клин, Пёшель и др., 1974-1981 гг.), естественно предположить, что любое Б-кольцо над конечной циклической группой шурово. С 1979 года это утверждение известно как гипотеза Шура-Клина Некоторые эксперты полагали, что эта гипотеза во всяком случае справедлива, если порядок группы свободен от квадратов. Основным результатом данного параграфа является следующая теорема, опровергающая, в частности, гипотезу Шура-Клина даже в этом случае.

Теорема 4.38. Пусть п — Р1Р2Р1Р4П', где РьР2-Рз,Р-1 - простые числа с условием {рьрг} ^ {рз 1Р4} = 0 и п' - натуральное чиспо, и П = Н.О.Д. (Р1 - 1,р2 - 1,Рз - 1 ,Р4~ !)• Тогда

(1) если В > 2, то над циклической ¿руаиой порядка п существуют нешуровы Б-кольца,

(2) если. П не делится на квадрат простого числа, то над циклической группой порядка п существуют неотделимые Б-кольца.

В основе доказательства теоремы 4 38 лежит оригинальная алгебраическая конструкция, связанная с итеративным применением к специальным орбитным циркулянтным Б-кольцам операции обобщённого сплетения, введенной в §4 2. Наименьшие примеры как нешуровых, так и неотделимых колец, гарантируемые этой теоремой, возникают при п = 52 • И2 в общем случае и при п = 5 13 • 17 • 29 в предположении, что п свободно от квадратов.

Формулируемое ниже утверждение является прямым следствием теоремы 4.38.

Теорема 4.37. Класс всех циркулянтных Я-колец (соотв. циркулянтных схем Кэли) не является ни шуровым, ни отделимым (соотв самоотделимым).

Глава 5. Факторизация многочленов и схемы отношений

В этой главе строится детерминированный алгоритм факторизации мноючлепа над конечным полем. В предположении обобщённой гипотезы Римдна сложное ib этого алгоритма квазиполиномиальна. По< коньку гипотеза используется лишь для эффективного извлечения корней в конечных полях, результат может быть сформулирован также следующим образом, любое полиномиальное уравнение с одним ней шестным над конечным полем может быть "решено в радикалах"за квазиполиномиаль-р ное время. Последующий анализ алгоритма вскрыл неожиданные глубо-

кие связи между факторизацией мноючленов и схемами отношений, что явилось одним из мотивов развития для нос ледних теории многомерных ti расширений (см. главу 3).

§5.1. Построение конечного поля и эффективное извлечение корней. В jtom параграфе развивается алгоритмическая техника для эффективной работы с конечными полями, которая будет использована в этой главе Ниже мы творим, что конечное поле характеристики р, задано явно если для некоторого его базиса нал простым подполем 1FP известно разложение по этому базису произведения любых двух базисных элементов Предполагается, что элементы ноля Fp представляются естественным образом так, что операции в нём совершаются за время (logp)0'1) Так что, операции в явно заданном конечном поле порядка q требуют времени flogr/)°(1>. Здесь и ниже под временем работы ашоригма понимается число совершаемых им битовых операций Отметим, что вероятностные алгоритмы полиномиальной сложности для факторизации давно известны (Рабин, 1980), ниже мы интересуемся лишь детерминированными.

Следующая теорема, отвечающая на вопросы поставленные Хуангом (1985 ), представляет основной результат этого параграфа

Теорема 5.1. Пусть q степень простого числа Тогда в предположении обобщенной гипотезы Римана следующие задачи могут быть решены зи полиномиальное время' (1) найти явное задание конечного поля порядка q,

(2) найти все изоморфизмы, между двумя реализациями конечного по, ля порядка q,

(3) найти все корни п-ой степени из данного элемента конечного поля порядка q,

т с за время (logд)0(1) для первых двух задач и за время (nlogq)0^1^ для третьей.

§5.2. Квазиполиномиальный алгоритм. Проблема эффективной факторизации многочлена над конечным полем активно изучалась в рамках

теории сложности вычислений (Хуанг, 1985, Евдокимов, 1989, Л^нстра, 1991 и др.). Однако до формулируемого ниже результата были известны лишь два заслуживающих внимания с теоретической точки зрения алгоритма факторизации произвольного многочлена степени п над конечным полем порядка д = рт: алгоритм Берлекэмпа (1970), время работы которого не превосходит (птр)°{1] {без всяких предположений), и алгоритм Роньяи (1987), время работы которого не превосходит (ппгп\ощр)°^ (в предположении обобщённой гипотезы Римана)

Теорема 5.16. В предположении обобь^ённой гипотезы Римана разложение многочлена степени г? над явно заданным конечным полем к порядка д на неприводимые лгножители может быть найдено за время

(71,Овп10ёв)°(1)

Хорошо известно (Берлекэмп, 1970), что задача о разложении многочлена / над к полиномиально эквивалентна задаче о нахождении делителя нуля в алгебре /с[Х]/(/), причём при доказательстве теоремы 5.16, не умаляя общности, можно ограничиться случаем расщепимого многочлена (т.е. имеющего столько различных корней в к, какова его степень). Последняя же задача решается в процессе некоторой многомерной конструкции многократным применением следующего утверждения.

Теорема 5.15. Пусть А - явно заданная расщепимая алгебра размерности й над полем порядка д Тогда в предположении обобщённой гипотезы Римана по нетождественному -эндоморфизму алгебры А за вречя (dlogq)0<^1^ можно найти делитель нуля, в А

Следует отметить, что алгоритм теоремы 5.16 работает рекурсивно, причём мы рассматриваем многочлены не только над полем к, но также и над расшепимыми алгебрами над к. По заданному на входе расщепи-мому многочлену / над такой алгеброй Ло наш алгоритм находит либо корень многочлена / над А^, либо делитель нуля в Л0. Если А0 = к, то поскольку в поле к нет делителей нуля, алгоритм находит корень многочлена / над к.

§5.3. Проблема факторизации и проблема шуровооти. В процессе анализа алгоритма теоремы 5.16 автором была обнаружена связь между факторизацией многочленов и схемами отношений. При этом естественным образом возник один интересный класс схем, именно класс нечётных схем, у каждой из которых по определению мощность любого базисного отношения нечётна Такие схемы отношений можно рассматривать как комбинаторный аналог групп перестановок нечётного порядка. Основные свойства нечётных схем перечислены в следующей лемме

Лемма 5.21. Имеют места следующие утверждения-

(1) схема нечётна тогда и только тогда, когда все её симметричные базисные отношения рефлексивны,

(2) каждое расширение нечётной схемы нечётно,

(3) прямая сумма, тензорное произведение и сплетение нечётных схем нечётны,

(4) порядок группы автоморфизмов нечётной схемы нечетен; если к тому же схема примитивна и шурова, то это число не превосходит, п.3, где п степень схемы.

Следующее утверждение, фактически вытекающее из теоремы 5.15, является в алгоритмическом смысле главным связуюшим звеном между многочленами и нечётными схемами.

Теорема 5.22. Пусть f - расщепимый многочлен степени п над полем к порядка q Тогда в предположении обобщённой гипотезы, Рима-на за время (nlogq)ol-li можно построить неявное задание некоторой нечётной, схемы на множестве его корней

Здесь под неявным заданием схемы на множестве корней V многочлена / понимаехся задание её базисных отношений идемпотентами тензорного квадрата над к алгебры А — k\X]/(f). При таком задании примитивные идемпотенты алгебры А (находящиеся во взаимно-однозначном соответствии с элементами множества V) могут быть неизвестны, их нахождение и составляет суть рассматриваемой задачи

Легко видеть, что задача факторизации многочлена / эффективно сводится к случаю, келда нечётная схема из теоремы 5 22 однородна и даже примитивна Поэтому использование некоторой модификации алгоритма теоремы 5 16 с учётом леммы 5.21 даёт следующее утверждение.

Теорема 5.23. Пусть {tn}£Li - такая последовательность целых чисел, что t(C) £ tn для всех схем С степени п, расширяющих некоторую примитивную нечётную схему той, же степени. Тогда в предположении обобщенной гипотезы Римана задача разложения на множители многочлена степени л над явно заданным полем порядка q может быть решена за время (n'" \ogq)a(-l\

Из теоремы 3 12 следует, что в качестве tn можно взять число Ьп + 1, где bn = max6(C). причём С пробегает все примитивные нечётные схемы степени и Таким образом, любая нетривиальная оценка сверху базового числа примитивной нечетной схемы приводит к улучшению оценки в задаче факторизации

РАБОТЫ АВТОРА ПО ТЕМЕ ДИССЕРТАЦИИ

1. С А Евдокимов, Факторизация разрешимого многочлена над ъо-нечным полем v обобщенная гипотеза Римапа Записки научных семинаров ЛОМИ, 176 (1989), 104-117.

2 S Evdokimov, Factorization of polynomials over finite fields m suhexpo-nential time under GRH, Lecture Notes in Computer Science, 877 (1994). 209-219

3 С А Евдокимов, И H Пономаренко. Два неравенства для параметров клеточной алгебры. Записки научных семинаров ПОМИ, 240 (1997), 82- 95

4 А. М. Вершик, С. А Евдокимов, И Н Пономаренко, Алгебры в планшерелевой двойствеппост,и и алгебраическая комбинаторика Функциональный анализ и его приложения, 31 (1997), 4, 34 46

5 С А Евдокимов, И Н Пономаренко. О примитивных клртпчиых алгебрах, Записки научных семинаров ПОМИ, 256 (1999), 38-68

6. S Evdokimov, М. Karpinski, I Ponomarenko, On a new high dimensional Weisfeiler-Leman algorithm, Journal of Algebraic Combinatorics, 10 (1999), 29 45.

7 S Evdokimov I Ponomarenko, Isomorphism of coloured graphs with slowly increasing multiplicity of Jordan blocks, C'ombinatoiira. 19 (1999), 321 -333.

8 S. Evdokimov. I. Ponomarenko, On highly closed cellular algebras and highly closed isomorphisms, Electronic J. of Combinatorics, 6 (1999), ^Rie

9. S. Evdokimov, I. Ponomarenko, Separability number and Schurity number of coherent configurations Electronic Journal of Combinatorics, 7 (2000), #R31

10. S Evdokimov, I. Ponomarenko, G. Tinhofer, Forestal algebras and algebraic forests (on a new class of weakly compact graphs). Discrete Mathematics, 225 (2000), 149-172.

11 С. А Евдокимов, И H Пономаренко, Об одном гемействе ьпт ut Шура над конечной циклической группой. Ат1ебра и анализ, 13 (2001) 3 139-154

12. С А Евдокимов, И II Пономаренко, Характеризация циклото-мических схем и нормальные кольца Шура над циклической, группой, Алгебра и анализ, 14 (2002), 2, 11-55

Отпечатано в ООО «ПОЛЭКС», Санкт-Петербург, В.О., Средний пр.,4 Подписано в печать 20.04.2005. Усл. печ. л. 2,; Зак. № 54. Тираж 100 экз.

1 0 09 8

РНБ Русский фонд

2006-4 6965

it

Введение

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 Циркулянтные S-кольца и отделимость циклотомических схем

4.1 Циклотомические схемы и нормальные схемы Кэли.

4.2 Обобщённые сплетения S-колец.

4.3 Циркулянтные S-кольца.

4.4 Критерий нормальности и его следствия.

4.5 Доказательство критерия нормальности.

4.6 Одна техническая теорема.

4.7 Отделимость циклотомических схем.

4.8 Отделимость и шуровость циркулянтных S-колец. Гипотеза Шура-Клина

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-орбит своей группы автоморфизмов. В честь Шура, имевшего дело с объектами только такого рода, её называют проблемой шуровости. Вторая проблема, называемая ниже проблемой отделимости, заключается в нахождении условий, при которых данная схема определяется с точностью до изоморфизма своими числами пересечений. Фактически ббльшая часть работ последнего времени по алгебраической комбинаторике (включая известную монографию Баннаи и Ито [1]) посвящена решению этой проблемы для специальных классов однородных схем, большинство из которых коммутативны и даже симметричны. Исследование двух указанных выше проблем и составляет основное содержание настоящей диссертации.

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

Диссертация состоит из 5 глав, к изложению основных результатов которых мы и переходим.

1. Э. Баннаи, Т. Ито, Алгебраическая комбинаторика. Схемы отношений, Перев. с англ.-М.: Мир, 1987.2. 3. И. Боревич, И. Р. Шафаревич, Теория чисел, М., 1964.

2. В. М. Бухштабер, А. М. Вершик, С. А. Евдокимов, И. Н. Пономаренко, Комбинаторные алгебры и многозначные инволютивные группы, Функциональный анализ и его приложения, 30 (1996), 3, 12-18.

3. В. М. Бухштабер, Е. Г. Рис, Многозначные группы и п-алгебры Хопфа, Успехи математических наук, 51 (1996), 4, 149-150.

4. Г. Вейль, Классические группы. Их инварианты и представления, М.: ИЛ, 1947.

5. Б. Ю. Вейсфейлер, А. А. Леман, Приведение графа к каноническому виду и возникающая при этом алгебра, НТИ, сер.2, (1968), 9, 12-16.

6. А. М. Вершик, Геометрическая теория состояний, граница фон Неймана, двойственность С*- алгебр, Записки научн. сем. ЛОМИ, т. 29, 1972, 147-154.

7. А. М. Вершик, С. А. Евдокимов, И. Н. Пономаренко, Алгебры в планшерелевой двойственности и алгебраическая комбинаторика, Функциональный анализ и его приложения, 31 (1997), 4, 34-46.

8. И. М. Виноградов, Основы теории чисел, М., (1972).

9. Я. Ю. Гольфанд, М. X. Клин, Н. Л. Наймарк, О структуре в-колец надй2т, "XVI Всесоюзная алгебраическая конференция", Часть 2, Ленинград, ЛОМИ, (1981), 195-196.

10. С. А. Евдокимов, Факторизация разрешимого многочлена над конечным полем и обобщённая гипотеза Римана, Записки научных семинаров ЛОМИ, 176 (1989), 104-117 (предпубликация, 1986).

11. С. Евдокимов, И. Пономаренко, Два неравенства для параметров клеточной алгебры, Записки научных семинаров ПОМИ, 240 (1997), 82-95.

12. С. Евдокимов, И. Пономаренко, О примитивных клеточных алгебрах, Записки научных семинаров ПОМИ, 256 (1999), 38-68.

13. С. Евдокимов, И. Пономаренко, Об одном семействе колец Шура над конечной циклической группой, Алгебра и анализ, 13 (2001), 3, 139-154.

14. С. Евдокимов, И. Пономаренко, Характеризация циклотомических схем и нормальные кольца Шура над циклической группой, Алгебра и анализ, 14 (2002), 2, 11-55.

15. Л. А. Калужнин, М. X. Клин, О некоторых максимальных подгруппах симметрических и знакопеременных групп, Матем. сборник, 87 (1972), 1, 91-121.

16. С. В. Керов. Двойственность конечномерных *-алгебр, Вестник ЛГУ, сер. ма-тем., N. 7, 1974, 23-29.

17. С. В. Керов, Двойственность *-алгебр и её применения в теории представлений групп, Диссертация на соиск. степени к.ф.м.н., 1974, Ленинград.

18. С. В. Керов, Двойные алгебры функций на конечной группе, Записки научных семинаров ЛОМИ, 39 (1974), 182-185.

19. Р. Лидл, Г. Нидеррайтер, Конечные поля. Т. 1, 2, М.: Мир, 1988.

20. С. Лэнг, Алгебра, М.: Мир, 1968.

21. С. Маклейн, Гомология, М.: Мир, 1966.

22. А. А. Махнев, Частичные геометрии и их расширения, Успехи математических наук, 54 (1999), вып.5, 25-76.

23. А. М. Adleman, Н . W. Lenstra, Jr., Finding irreducible polynomials over finite fields, Proc. 18th ACM Symp. on Theory of Computing (STOC) Berkeley, (1986), 350-353.

24. L. Babai, On the order of uniprimitive permutation groups, Annals of Math., 113 (1981), 553-568.

25. L. Babai, Automorphism groups, isomorphism, reconstruction, in R. L Graham, (ed.) et al., Handbook of combinatorics. Vol. 1-2. Amsterdam: Elsevier (North-Holland), (1995), 1447-1540.

26. L. Babai, W. Kantor,E. M. Luks, Computational complexity and the classification of finite simple groups, Proceedings of the 24th Ann. Symp. Found. Comput. Sci, 1983, 162-171.

27. L. Babai, and E.M. Luks, Canonical labeling of graphs, Proc. 15th ACM STOC, (1983), 171-183.

28. E. Bannai, Et. Bannai, Generalized generalized spin models models (four-weight spin models), Рас. J. Math., 170 (1995), 1-16.

29. E. R. Berlekamp, Factoring polynomials over large finite fields, Math. Сотр., 24 (1970), 713-735.

30. С. Berge, Graphs and Hypergraphs, North-Holland Publ. Co., London, 1973.

31. T. Beth, D. Jungnickel, H. Dieter, Design theory, Cambridge University Press, (1986).

32. R. C. Bose, D. M. Mesner, On linear associative algebras corresponding to association schemes of partially balanced designs, Ann. Math. Statist., 30 (1959), 21—38.

33. R. C. Bose, K. R. Nair, Partially balanced incomplete block designs, Sankhy, 4 (1939), 337-372.

34. W. G. Bridges, R. A. Mena, Rational circulants with rational spectra and cyclic strongly regular graphs, Ars Combin., 8 (1979), 143-161.

35. R. Brauer, Representations of finite groups, in: Lectures on Modern Mathematics, Vol. I, 1963, 133-175.

36. A. E. Brouwer, A. M. Cohen, A. Neumaier, Distance-regular graphsSpringer, Berlin, 1989.

37. P. Burgisser, M. Clausen, M. Shokrollahi, Algebraic Complexity Theory, Springer, New York & Berlin, 1997.

38. A. E. Brouwer, J. H. van Lint, Strongly Regular Graphs and Partial Geometries. In: "Enumeration and Design Proc. Silver Jubilee Conf. on Combinatorics. Waterloo, 1982", (ed. D. M. Jackson, S. A. Vanstone), Acad. Press Toronto, 1984, 85-122.

39. V. M. Buchstaber, E. G. Rees, Multivalued groups, their representations and Hopf algebras, Transform. Groups, 2 (1997), 4, 325-349.

40. P. Dembowski, Finite Geometries, Springer, Berlin, 1968.

41. J. D. Dixon, B. Mortimer, Permutation groups, Graduate Texts in Mathematics, No. 163, Springer-Verlag New York, 1996.

42. M. Enock, L. Vainerman, Deformation of a Kac algebra by an abelian subgroup, Comm. Math. Phys., 178 (1996), 571-595.

43. S. Evdokimov, Factorization of polynomials over finite fields in subexponential time under GRH, Lecture Notes in Computer Science, 877 (1994), 209-219.

44. S. Evdokimov, I. Ponomarenko, Isomorphism of coloured graphs with slowly increasing multiplicity of Jordan blocks, Combinatorica, 19 (1999), 321-333.

45. S. Evdokimov, M. Karpinski, I. Ponomarenko, On a New High Dimensional Weisfeiler-Leman Algorithm, Journal of Algebraic Combinatorics, 10 (1999), 29-45.

46. S. Evdokimov, I. Ponomarenko, On highly closed cellular algebras and highly closed isomorphisms, Electronic J. of Combinatorics, 6 (1999), #R18 (MR2000e:05160).

47. S. Evdokimov, I. Ponomarenko, Separability Number and Schurity Number of Coherent Configurations, Electronic Journal of Combinatorics, 7 (2000), #R31.

48. S. Evdokimov, I. Ponomarenko, G. Tinhofer, Forestal algebras and algebraic forests (on a new class of weakly compact graphs), Discrete Mathematics, 225 (2000), 149172.

49. I. A. Faradzev, M. H. Klin, M. E. Muzychuk, Cellular rings and groups of automorphisms of graphs, in: I.A. Faradzev et al. (eds): Investigations in algebraic theory of combinatorial objects, Kluwer Acad. Publ., Dordrecht, 1994, 1-152.

50. S. Friedland, Coherent algebras and the graph isomorphism problem, Discrete Applied Math., 25 (1989), 73-98.

51. R. W. Goldbach, H. L. Claasen, Cyclotomic schemes over finite rings, Indag. Math. (N.S.), 3 (1992), 301-312.

52. A. Hanaki, I. Miyamoto, Classification of primitive association schemes of order up to 22, Kyushu J. Math., 54 (2000), 81-86.

53. D. G. Higman, Coherent configurations i., Rend. Mat. Sem. Padova, 44 (1970), 1-25.

54. D. G. Higman, Characterization of families of rank 3 permutation groups by the subdegree I, II, Arch. Math., 21 (1970), 151-156; 353-361.

55. D. G. Higman,Coherent algebras, Linear Algebra Appl., 93 (1987), 209-239.

56. M.-D. A. Huang, Riemann hypothesis and finding roots over finite-fields, Proc. 17th ACM Symp. on Theory of Computing (STOC) New-York, (1985), 121-130.

57. D. R. Hughes, F. C. Piper, Projective Planes, Springer-Verlag, New York, Heidelberg, Berlin, 1973.

58. F. Jaeger, Towards a classification of spin models in terms of association schemes, in Progress in Algebraic Combinatorics, Advanced Studies in Pure Math., 24 (1996), 197-225.

59. F. Jaeger, K. Nomura, Symmetric versus non-symmetric spin models for link invariants, J. Algebraic Combin., 10 (1999), 241-278.

60. Ch. Kassel, Quantum Groups, Springer-Verlag, 1994.

61. S. A. Katre, The cyclotomic problem, Adhikari, S. D. (ed.) et al., Current trends in number theory, Proceedings of the international conference on number theory, Allahabad, India, (2002), 59-72.

62. M. H. Klin, R. Pöschel, The König problem, the isomorphism problem for cyclic graphs and the method of Schur rings, Colloq. Math. Soc. J. Bolyai, 25 (1978), 405-434.

63. J. C. Lagarias, H. L. Montgomery, A. M. Odlyzko, A bound for the Least Prime Ideal in the Chebotarev Density Theorem, Inv. Math., 54 (1979), 271-296.

64. F. Lazebnik, V. A. Ustimenko, A. J. Woldar, A new series of dense graphs of high girth, Bull. Amer. Math. Soc. (N.S.), 32 (1995), 73-79.

65. H. W. Lenstra, Jr., Finding isomorphisms between finite fields, Math. Comp., 56 (1991), 329-347.

66. K. H. Leung, S. H. Man, On Schur Rings over Cyclic Groups, II, J. Algebra, 183 (1996), 273-285.

67. K. H. Leung, S. H. Man, On Schur Rings over Cyclic Groups, Israel J. Math., 106 (1998), 251-267.

68. R. Mathon, A note on the graph isomorphism counting problem, Inform. Process. Lett., 8 (1979), 131-132.

69. R. McConnel, Pseudo-ordered polynomials over a finite field, Acta Arith., 8 (1963), 127-151.

70. E. Mendelsohn, Every (finite) group is the group of automorphisms of a (finite) strongly regular graph, Ars Combinatoria, 6 (1978), 75-86.

71. M. E. Muzychuk, The structure of basis sets of Schur rings over cyclic groups, J. of Algebra, 169 (1994), 655-678.

72. M. E. Muzychuk, Difference sets with n = 2pm, Journal of Algebraic Combinatorics, 7 (1998), 77-89.

73. M. Muzychuk, A solution of the isomorphism problem for circulant graphs, Proc. London Math. Soc., 88 (2004), 1-41.

74. P. P. Palfy, A polynomial bound for the orders of primitive solvable groups, J. of Algebra, 77 (1982), 127-137.

75. R. Poschel, Untersuchungen von S-Ringen insbesondere im Gruppenring von p-Gruppen, Math. Nachr., 60 (1974), 1-27.

76. M. 0. Rabin, Probabilistic algorithms in finite fields, SIAM J. Comput., 9 (1980), 273-280.

77. G. R. Robinson, On the Base size and rank of a Primitive Permutation group, J. of Algebra, 187 (1997), 320-321.

78. L. Rónyai, Factoring polynomials over finite fields, Proc. 28th IEEE Symp. on Foundations of Computer Science (FOCS) New-York, (1987), 132-137.

79. I. Schur, Zür Theorie der einfach transitiven Permutationgruppen, S.-B. Preus Akad. Wiss. Phys.-Math. KL, (1933), 598-623.

80. I. E. Shparlinski, Finite fields: theory and computation. The meeting point of number theory, computer science, coding theory and cryptography, Mathematics and its Applications (Dordrecht), Kluwer Academic Publishers (1999).

81. V. A. Ustimenko, On a group theoretical constructions of expanding graphs, Journal of Algebra and Discrete Mathematics, (2003), 3, 102-109.

82. M. Watkins, Connectivity of transitive graphs, J. Combin. Theory, 8 (1970), 23-29.

83. B. Weisfeiler (editor), On construction and identification of graphs, Springer Lecture Notes, 558, 1976.

84. H. Wielandt, Finite permutation groups, Academic press, New York London, 1964.

85. H. Wielandt, Permutation groups through invariant relations and invariant functions, Lect. Notes Dept. Math. Ohio St. Univ., Columbus, 1969.

86. N. J. Wildberger, Lagrange's theorem and integrality for finite commutative hypergroups with applications to strongly regular graphs, J. Algebra, 182 (1996), 1-37.

87. P.-H. Zieschang, Algebraic Approach to Association Schemes, Springer, Berlin & Heidelberg, 1996.