Содержание к диссертации
Введение
1 Схемы отношений и клеточные алгебры 21
1.1 Общая теория 21
1.2 Примеры .- 27
1.3 Операции 31
1.4 Шуровость и отделимость схем 36
1.5 Кольца Шура и схемы Кэли 42
1.6 Линейные представления клеточных алгебр 46
2 Алгебраическая природа схем отношений 52
2.1 Обобщённые С-алгебры 52
2.2 Спаривание и его свойства 55
2.3 Планшерелева двойственность 62
2.4 Многозначные группы 70
3 Многомерные инварианты схем 75
3.1 Многомерные расширения схем и подобий 75
3.2 Числа отделимости и шуровости 78
3.3 Поведение при операциях 81
3.4 Псевдоотделимые и псевдошуровы схемы 86
3.5 Многомерные расширения и (К, Л)-регулярность графов 94
3.6 Отделимость и шуровость классических схем 98
3.7 Отделимость и шуровость схем конечных плоскостей 102
4 Циркулянтные S-кольца и отделимость циклотомических схем 104
4.1 Циклотомические схемы и нормальные схемы Кэли . 104
4.2 Обобщённые сплетения S-колец 107
4.3 Циркулянтные S-кольца 111
4.4 Критерий нормальности и его следствия 116
4.5 Доказательство критерия нормальности 119
4.6 Одна техническая теорема . 123
4.7 Отделимость циклотомических схем 127
4.8 Отделимость и шуровость циркулянтных S-колец. Гипотеза Шура-Клина128
5 Факторизация многочленов и схемы отношений 132
5.1 Построение конечного поля и эффективное извлечение корней 132
5.2 Квазиполиномиальный алгоритм 136
5.3 Проблема факторизации и проблема шуровости . 144
Введение к работе
Ассоциативные схемы, или схемы отношений, изучению которых посвящена настоящая работа, возникают в различных областях математики, хотя-и пе всегда под одним и тем же названием. Так, сам термин появился в работах Боуза и его коллег о блок-схемах в рамках теории планирования статистических экспериментов [34, 33]; соответствующий объект является здесь симметричной схемой. Однако ещё раггее в известной работе Шура [80], заложившей основы теории S-колец, уже появляется понятие централизаторного кольца группы перестановок (которое в транзитивном случае есть не что иное как алгебра Геккс исходной группы по стабилизатору точки), фактически совпадающее с алгеброй смежности ассоциативной схемы специального вида. Общая теория схем отношений возникает независимо как теория когерентных конфигураций в работах Д.Хигмана [54, 55], посвященных изучению групп ранга 3, и как теория клеточных алгебр в работах Вейсфейлера и Лемана [6, 84], посвященных вычислительной сложности проблемы изоморфизма графов. В настоящее время структурная теория однородных схем отношений развита в книге Цишанга [88], где они называются обобщёнными группами и рассматриваются как обобщения групп и билдингов. Такие схемы и их алгебры смежности доставляют наиболее важные примеры С-алгебр (обобщающих алгебры характеров конечных групп), гииергрупп, алгебр в планшерслевой двойственности и многозначных групп (см. [1, 87, 17, 40]). Отметим также появившиеся в последнее время работы Джагера, Баннаи и др., посвященные построению инвариантов зацеплений и узлов на основе теории ассоциативных схем (см. [59, 60, 29]). Наконец, упомянем обнаруженные автором неожиданные связи между теорией схем отношений и задачей эффективного разложения многочленов на множители над конечным полем (см. [44] и последнюю главу диссертации) .
Многие задачи теории схем отношений, называемых далее также просто схемами, в той или иной степени связаны с изучением их групп автоморфизмов и с построением различного рода систем инвариантов изоморфизма. В контексте теории групп перестановок упомянем в этой связи известную работу Д.Хигмана [55], посвященную характеризации классических групп ранга 3 в терминах их подстепспей. Ещё одним примером является подход к описанию конечных простых групп как групп автоморфизмов подходящих схем отношений. В рамках алгебраической комбинаторики (сравнительно недавно возникшей области математики) одна из важнейших задач состоит в нахождении необходимых и достаточных условий того, чтобы данный дистанционно-регулярный граф был дистанционно-транзитивным. Уже упоминавшаяся выше проблема изоморфизма графов, одна из фундаментальных нерешённых проблем современной теории сложности вычислений, является специальным случаем проблемы изоморфизма схем. Идейно близкой к рассматриваемой проблематике оказывается и задача из программной работы Р.Брауэра [36] по теории представлений конечных групп, а именно, какую информацию необходимо добавить к таблице характеров конечной группы, чтобы получить её полное множество инвариантов.
Анализ: этих, а также ряда других задач алгебраической комбинаторики естественным образом приводит к двум следующим проблемам. Первая из них восходит к Виландту [85], который интересовался, при каких условиях данное S-кольцо возникает из подходящей группы перестановок с регулярной подгруппой. В общей теории схем отношений эта проблема сводится к выяснению того, совпадает ли данная схе-
ма со схемой 2-орбит ссоси группы автоморфизмов. В честь Шура, имевшего дело с объектами только такого рода, её называют проблемой шуровости. Вторая проблема, называемая ниже проблемой отделимости, заключается в нахождении условий, при которых данная схема определяется с точностью до изоморфизма своими числами пересечений. Фактически бблыпая часть работ последнего времени по алгебраической комбинаторике (включая известную монографию Баннаи и Ито [1]) посвящена решению этой проблемы для специальных классов однородных схем, большинство из которых коммутативны и даже симметричны. Исследование двух указанных выше проблем и составляет основное содержание настоящей диссертации..
Следует отметить, что современная теория схем отношений имеет дело в основном с однородными схемами; ситуация такова, как если бы в теории групп перестановок рассматривались лишь транзитивные группы. С точки зрения проблем шуровости и отделимости это сильно ограничивает набор инвариантов, которые можно использовать для их решения, что, в частности, не позволяет ввести количественные характеристики шуровости и отделимости, то есть определить в какой степени данная схема отличается соответственно от шуровой или отделимой. Отсутствие развитой структурной теории неоднородных схем вынуждает автора затратить определённые усилия на восполнение этого пробела.
Диссертация состоит из 5 глав, к изложению основных результатов которых мы и переходим.
Операции
Если группа Г транзитивна, то эта алгебра изоморфна алгебре Гекке группы Г по стабилизатору точки (изоморфизм переводит базисные матрицы в двойные классы смежности). Обратно, каждая алгебра Гекке, построенная по конечной группе Г и её подгруппе А, может быть получена таким образом из группы перестановок, индуцированной правым действием Г на множестве её левых классов по Д.
Схемы сопряжённых классов. Пусть G - конечная группа. Обозначим через Г группу перестановок, индуцированную действием на G подгруппы G Inn(G) её голоморфа, отвечающей внутренним автоморфизмам (G действует на себе правыми умножениями). Схема С = ГПУ(Г) называется схемой сопряженных классов: группы G. Поскольку алгебра смежности этой схемы изоморфна центру групповой алгебры группы G, схема С коммутативна. Очевидно, Г = {Gright, Gieft). Поэтому группа Aut(C) совпадает с 2-замыканием группы, стоящей в правой части равенства. Заметам также, что элементы множества (С) отвечают нормальным подгруппам исходной группы G. Поэтому схема С примитивна тогда и только тогда, когда эта группа является простой. Поскольку числа пересечений схемы С выражаются через значения таблицы характеров группы G (см. [1]), две схемы сопряжённых классов подобны тогда и только тогда, когда соответствующие группы имеют одинаковые таблицы характеров.
Циклотомические схемы. Пусть F - конечное поле порядка q и Н - подгруппа индекса m его мультипликативной группы Fx. Тогда, как легко видеть, базисные отношения схемы С = Inv(r), где Г - полупрямое произведение аддитивной группы поля F и группы Н, имеют вид До = {{х,у) Є F2 : х - у Є аН}. а Є F. Следуя [37], мы называем С циклотпомической схемой на F (по поводу обобщения этого понятия на конечные кольца см. [52]). Легко видеть, что число пересечений схемы С, отвечающее отношениям Яа, Ль, Rc с о, Ь, с ф 0, равно количеству решений ,Ї? {0,1,...,(7- 1)/етг—1} уравнения agm +b = cgmT}, где д - примитивный элемент поля F. Явное вычисление этих целых чисел, называемых циклотомическими, является трудной теоретико-числовой проблемой (см. [20, с.305]). Более того, в отличие от многих классических схем числа пересечений циклотомической схемы не определяют её с точностью до изоморфизма, Например, известно много попарно неизоморфных схем, возникающих из конференс-матриц и матриц Адамара и имеющих те же числа пересечений, что и схемы Пэли, т.е. циклотомические схемы с m = 2. 1.2.2 Дистанционно-регулярные графы
Пусть Г - простой связный граф диаметра d с множеством вершин V и множеством рёбер R. Для г [0, d] обозначим через Ri, бинарное отношение на V, состоящее из всех пар вершин, находящихся на расстоянии і в Г. В частности, R0 = Д(У) и Ri — R. Легко видеть, что отношения семейства 72 = {Ri}f 0 образуют разбиение множества V2.
Определение 1.7 Граф Г называется дистанционно-регулярным, если пара С (Г) = (VjlZ) является схемой на V. Если при этом d = 2, то граф называется сильно-регулярным. Дистанционно-регулярный граф называется дистанционно-транзитивным, если его группа автоморфизмов действует транзитивно на каждом элементе из П. Отметим, что дашюе определение дистанционно-регулярного графа эквивалентно стандартному (см., например, [371) и отличается от него лишь выбором языка. Приводимые ниже факты из теории таких графов излагаются также на языке схем. Из определения следует, что схема дистанционно-регулярного графа симметрична и потому коммутативна. Пусть Г - дистанционно-регулярный граф. Тогда полный набор чисел пересечений схемы С (Г) однозначно определяются числами cR и c R при і Є [d\: называемыми числами пересечений или параметрами графа Г. Если дистанционно-регулярные графы Г и Г имеют одни и те же числа пересечений, то легко видеть, что отображение из множества базисных отношений схемы С (Г) в множество базисных отношений схемы С (Г ), переводяшее Ri в R {, является биекцией и, более того, индуцирует подобие этих схем. Обратно, если р - подобие схемы С(Г) на некоторую схему С с множеством точек V, то граф Г = (V, Rv) является дистанционно-регулярным и его параметры совпадают с параметрами графа Г.
Граф Джонсона. Пусть п,к - неотрицательные целые числа, к п. Граф Г = J(ntk), вершинами которого являются А подмножества множества [ті], а рёбрами пары (u, v) такие, что [uf\v\ = к — 1, называется графом Джонсона. Известно, что Г - дистанционно-транзитивный граф диаметра d = min(k,n — k), который однозначно определяется своими параметрами, если (п,к) ф (8,2) (см. [37, п. 9.1.В]). Если же [п, к) = (8,2), то любой дистанционно-регулярный граф, имеющий те же параметры, что и Г, изоморфен либо Г, либо одному из трёх графов Чанга, ни один из которых не является дистанционно-транзитивным. Граф Хэмминга, Пусть d 0 и q 2- целые числа. Граф Г = H(d,q)t являющийся произведением d копий полного графа на множестве [а], называется графом Хэмминга. Таким образом, множество вершин графа Г равно [q]d и две вершины смежны тогда и только тогда, когда они различаются точно в одной координате. Известно, что Г - дистанционно-транзитивный граф диаметра d, однозначно определяющийся своими параметрами за исключением тех случаев, когда q — 4 и d 2 (см. [37, п. 9.2.В]). Если q — 4, то любой дистанционно-регулярный граф, имеющий те же параметры, что и Г, изоморфен графу Daib, который является произведением а копий графа Шрикханде и Ь копий полного графа на 4 вершинах, где а 0 и Ъ О - целые числа, для которых 2а + h — d. Очевидно, D0,d = Г. Если же о 1, то граф Оа не является дистанционно-транзитивным. Он называется графом Дуба. Граф Грассмана, Пусть - конечное поле порядка q и п, к - неотрицательные целые числа, к п. Граф Г = Jq(n,k), множеством вершин которого являются к-подпространства n-мерного линейного пространства над полем F, ач множеством рёбер пары (it, v) такие, что dim(unu) = к—1, называется графом Грассмапа. Известно, что Г - дистанционно-транзитивный граф диаметра d = min(k, п к), который однозначно определяется своими параметрами при условии п к п — 3, (q, к) (2, п) {см. [37, с.272]).
Спаривание и его свойства
Мы будем рассматривать тройки (Л, В, (, )), где А,В конечномерные -алгебры над С с единицами 1д и 1# и (,):ЛхВ С (35) - билинейная форма, приводящая их в невырожденную двойственность как линейные пространства над С. Под изоморфизмом троек мы понимаем пару изоморфизмов между соответствующими алгебрами, сохраняющих билинейные формы. Прямая сумма и тензорное произведение троек определяются естественным образом. Элементы алгебр А и В будут обозначаться через х, у, г,... и f,g,h,... соответственно. Пусть А и В суть двойственные пространства к А и В. Тогда спаривание (35), будучи невырожденным, индуцирует линейные изоморфизмы из В в Л и из Л в В. Образ функционала х в обоих случаях обозначается через х. Используя двойственность между алгебрами Л и В, можно переносить структуры из А в В и наоборот. Например, можно рассматривать коинволюции т\А и г\в в Л и В, т.е. операции, сопряжённые к инволюциям в В и Л; fa (я), /) = КТО, ( , Пв{ї)) = WJ), хе А, /ЄВ. (36) Легко видеть, что это полулинейные 1-1 отображения. Не умаляя общности, будем считать, что они являются -изоморфизмами (см. п. 2.2.2). По двойственности отсюда следует, что линейные отображения 6А:А АА, 6В:В ВВ, (37) сопряжённые к умножениям в алгебрах В и Л и называемые коумножениями, перестановочны с инволюциями, т.е. являются -отображениями. В п. 2.2.3 для конечного множества / мы будем рассматривать также симметричные разложения единиц 8 в алгебрах А и В (т.е. такие разложения, для которых e iA — eitA И е\в — еІВ при всех г). Положим А = е дЛ д д), В = е вВт]В(е гв)- Тогда из сказанного выше следует, что Jfc(Aj) = 4 , . Пв{В ) = ВІМ itjL (39) Будем говорить, что разложения единиц (38) согласованы со спариванием (35), если {Aij,Bki) = {0} для всех (i,j) ф (fc, I) и прямые разложения А= Аи, В = В (40) устойчивы относительно действия инволюций (а потому и коинволюций) в обеих алгебрах. Тогда, очевидно, (, ) индуцирует для каждой лары (i,j) Є I2 невырожденное спаривание между пространствами Aij и Bij. Отметим, что идемпотенты ЄІ:А и Г)А( ,А), а также е в и Ї?В(Є ,В) перестановочны для всех г, j, или, что равносильно, VA JA) = ej,i,A ЦВ{ЄІ,З,В) = емв, i,j Є І, (41) где е д = ЄІ Ї]А{ ,А) И eij,B = ei,BVB(ej,B)- Действительно, поскольку первое из разложений (40) инвариантно относительно щ, причём »?д(1д) = 1д отображение 77л осуществляет перестановку элементов е -,д. При этом в силу (39) и того факта, что ei А = ei,Ai оно переводит і-ую строку в г-ый столбец, а по инволютивности и наоборот, г-ый столбец в г-ую строку. Поэтому 77д(е д) — ej,i,A-Мы будем также предполагать, что ПІ = (е(]д, еііВ) 0, і є І. (42)
Это предположение не ограничивает общности, поскольку, как мы.увидим ниже, в условиях п. 2.2.3 щ ф 0 при всех і и потому (42) следует из условий п. 2.2.2. Положим КА = {хєА: {x,/) 0V/eB+}, Яв = {/ЄБ: (x,f) 0 Vz Є A+}, где A+ = {xx : xeA}tB+ = {// : f Є B}. Определение 2.6 Спаривание (35) называется положительным, если конусы К А и Кв, двойственные к конусам В+ и А+, замкнуты относительно умнозісений и инволюций в алгебрах А и В соответственно. 8Под разложением единицы в алгебре мы понимаем представление единицы этой алгебры в виде суммы попарно ортогональных ненулевых идсмпотентов. По двойственности положительность спаривания равносильна тому, что коумноження 5А И 5В И коинволюций Т}А И Г)В ЯВЛЯЮТСЯ положительными отображениями в том смысле, что 6А(А+) СА+ Л+, 5В(В+) CS+ В+, VA(A+) С Л+, VB(B+) С В+. В теории алгебр Хопфа одно из коумножений (а тогда автоматически и второе), а также одна из коинволюций (а тогда автоматически и вторая) является по определению -гомоморфизмом алгебр (см. [61]). Поскольку -гомоморфизм есть положительное отображение, аксиоматика положительных троек представляет собой естественное ослабление аксиоматики алгебр Хопфа. На самом деле замкнутость конусов К А И KB относительно инволюций следует уже из их замкнутости относительно умножений и, более того, в этом случае коинволюций Г}А и TJB являются -изоморфизмами алгебр. Действительно, если конус К А устойчив относительно умножения в алгебре А, то легко видеть, что таким же свойством обладает и множество SA = {х є А : {%,/ ) = (ж,/) V/ Є В}, откуда следует, что коумножение 5В является -отображением и потому по двойственности коинволюция гомоморфна. Аналогично, если конус К в устойчив относительно умножения в алгебре В, то гомоморфна коинволюция г}в 2.2.3 Клеточность Положим ХА = {х Є А : (х, eiJiB) = 0, і J Є /}, Тв = {/ Є В : (eitj,A, /) = 0, i,j Є 1} (здесь и ниже мы используем обозначения п. 2.2.1). Положим также nij = п1/2п)/2 іІЄ/, где ns = {ЄІ,А,ЄІ,В) Определение 2.7 Спаривание (35) называется клеточным, относительно согласованных с ним разложений единиц (38), если ТА и1в - двусторонние идеалы в алгебрах А и В соответственно и, более того, линейные отображения dA:A. Mat/, (dA)id(х) = nrj(х, eiJ B), (43) dB: В - Mat/, {dB)id(f} = nYJ(eiJiA,/) (44) являются гомоморфизмами алгебре Спаривание называется клеточным, если существуют согласованные с ним разложения единиц, относительно которых оно клеточно, 9Из первой части определения следует, что щ ф 0 при всех і. Действительно, если {ЄЇ,Л,ЄІ,В) =0, то в силу утверждения (1) леммы 2.8 е;,д Є ТА И, следовательно, A j С Хд при всех j. Но тогда (ЯЄі,.в) = 0 для всех х є А, что противоречит невырожденности спаривания. Отметим, что если спаривание клеточно, то ХА и Хв - наибольшие двусторонние идеалы, содержащиеся в множествах {х Є А : (х, 1в) = 0} и {/ є В : {1А, I) — 0}. Действительно, если, например, X С А - такой идеал, то в силу согласованности спаривания {х, е в) = {%А ЯА{ ,А), 1В) = 0 для всех х Є Л, то есть X С2д.
Обратно, всякая полуторалинейная форма с этим свойством совпадает с (, )х для единственным образом определённого следа Х- Отметим, что форма (51) сопряжённо симметрична тогда и только тогда, когда т(тг,х) является вещественным числом для всех 7г (эквивалентно, xlx ) = Х(х) Для ссех х) п положительно определена тогда и только тогда, когда т(тт}х) 0 для всех тг (эквивалентно, х(хх ) 0 Для всех х 0). В последнем случае мы говорим, что х является положительным.
Числа отделимости и шуровости
Пусть С - схема на V и т - натуральное число. Положим где J: ни («,...,«)- диагональное отображение из К в Vm. Схема С называется го-замыканием схемы С. Последняя называется тп-замкнутой, если С = С . Очевидно, С С; в частности, любая схема является 1-замкнутой. Пример схемы, 2-замыкаиие которой не равно ей самой, даёт единственная с ТОЧЕЮСТЬЮ до изоморфизма несимметричная однородная схема степени 15 и ранга 3. Легко видеть, что шурова схема m-замкпута при всех т. Подобие р схем называется т-подобием, если оно имеет m-расширепие; индуцированное подобие т-замыканий обозначим через 1$-т . Множество всех m-подобий схемы С на схему С обозначается через Simm(C,C }- Очевидно, Sim.i(C,C) = Sim(C,C), в то время как не всякое подобие является 2-подобием (см. примеры из 3.6), Если / : С — С - изоморфизм, то и его декартова степень fm является изоморфизмом схемы Ст на схему (С )т и переводит Д(т) в (Д )(т). Поэтому fm Є Iso((?m\ (C )(m)) и индуцированное им подобие является m-расширением подобия, индуцированного /, которое тем самым является т-подобием. Теорема 3.7 Для любых схем С и С степени п справедливы следующие утверждения: С = С{1) ... С(п) = ...=С{ао), (73) Sim(C,C) = Sim!(С, С) Э ... Э Simn(C,C) = ... = Simro(C,C), (74) где С - схема 2-орбит группы Airt(C) и Sim C C) - множество всех подобий схемы С на схему С, индуцированных изоморфизмами этих схем. Доказательство. Включения С С т и Simt(C,C) D Simm(C,C) при I m, следуют из теоремы 3.6. Остальное вытекает из теоремы 1.23 и леммы 3.9 ниже, для доказательства которой нам потребуется следующее вспомогательное утверждение. Лемма 3.8 Пусть С - схема на V, I т натуральные числа и С = ОтК Для Vi,..., vm-i Є V положим U — {и є Vm : щ+і = vi} і Є [т — І}}. Тогда V"є Ш(С) и с (С— ( V где С : Vі — U - биекция, переводящая [щ,..., щ) в (щ,...,«/,«!,..., vm-i). Доказательство. То, что U Є В(С), вытекает из утверждения (1) теоремы 3.3. Далее, очевидно, (дЮ)С = дм пи2, Яс = (Я V2{-m l)) П U2, где Я - любое бинарное отношение на Vі. Отсюда следует, что схеме Су принадлежит как отношение (Д ) , так и любое отношение Я , где Я = j=i Щ, причём каждое Щ либо является отношением схемы С, либо совпадает с одним из одноэлементных отношений {(vi,Vi)} при і Є [т — 1} (последнее снова в силу утверждения (1) теоремы 3.3). Поэтому Си [((CV1 VmJ) , (Д )с] = [(С У, Д 1 = (cCZJY что и требовалось доказать.» Лемма 3.9 Пусть С - схема ига - натуральное число. Если схема Ст „m_l явля ется 1-регулярной для некоторых точек vu ., vm-i, то схема &т также явля ется 1-регулярной. Доказательство. Поскольку C„Ii.. jl)m_1 является 1-регулярной схемой, то по лемме 1.22 и лемме 3.8 (при і = 1} схема Си, определённая в последней лемме, также является 1-регулярной. Обозначим через v — [vu.. .,vm-i,vm) какую-нибудь её регулярную точку и докажем, что v является также регулярной точкой схемы С = &т\ Для і Є {1,..., т] положим Ег = {(й,й ) Є Vm х Vm : щ = и\}. Тогда достаточно доказать, что УгЄ{1,...,т} Уи(Ут/Е{ ЗЩеТ1 (С): (#)« («) = И- (75) Действительно, если її є Vm, то, очевидно, {и) р 1 Ui, где Ui класс эквивалентности Eit содержащий точку и. Согласно (75) Ui = (Ri)out{v), где 7 Є 1Z (С) для всех г. Поэтому {й} = Rout(v), где R = р Ri. Поскольку, очевидно, R Є 7 (С), то v - регулярная точка схемы С.
Докажем формулу (75). Предположим сначала, что і = m. Для С/ Є Vm/Em существует точка v EV такая, что U = {й Є Vm : um — v}. Обозначим через R базисное отношение схемы С, содержащее пару (її, v ). Тогда dou R) = 1, поскольку R С Е и v является регулярной точкой схемы Су. Поэтому U = Я (и), где Я - бинарное отношение на множестве V"1, матрица смежности которого равна Л(Я ) = A(R)A(Em). Поскольку Ет Є {С), мы имеем R Є Л{С). Пусть теперь і произвольно. Обозначим через G образ естественного представления симметрической группы степени т перестановочными матрицами кольца Maty" . Тогда, очевидно, G С W{C). Поскольку действие группы G правыми умножениями на множестве {А(ЕІ) : г 1,... , т} транзитивно, то общий случай сводится к случаю г = тл Пусть С - схема.и т - натуральное число. Определение ЗЛО Схема С называется т-шуровой, если С = С " , и т-отделимой относительно некоторого класса схем /С, если SiiiimfCjC ) = Sim C C) для любой схемы С из К. Если при этом К совпадает с классом всех схем, то схема С называется т-отделимой. Из формулы (73) (соответственно (74)) следует, что m-шурова (соответственно т-отделимая относительно К) схема является J-шуровой (соответственно /-отделимой относительно К) для всех I т, и что любая схема степени п является га-шуровой и 71-отделимой, Положим t(C)=mm{m: С — m-шурова}, s(C) = min{m : С т-отделима} к назовём эти натуральные числа соответственно числом гиурооости и числом отделимости схемы С. В некоторых случаях числа отделимости и шуровости легко вычисляются. Так, если гк(С) = 2 или схема С является 1-регулярной, то s(C) = () = 1 (см. теорему 1.23). В частности, для любой тривиальной схемы эти числа равны 1. Как следствие определений п. 1.2.2 и 1.4 получаем ещё один пример. Теорема 3.11 Пусть Г - дистанционно-регулярный граф и С = С(Г). Тогда (1) граф Г однозначно определяется своими параметрами тогда и только тогда, когда s(C) = 1, (2) граф Г является дистанционно-транзитивным тогда и только тогда, когда t(C) = 1.М Отметим также, что теорема 1.23 и лемма 3.9 влекут следующее утверждение. Теорема 3.12 Пусть С - схема и т 1 - натуральное число. Если схема Сщ Vm_1 является 1-регулярной для некоторых точек vL,,., ,г т_і, то s(C) т и t(C) т. В частности, s(C) b(C) + 1 и t(C) b(C) + 1, где b(C) - базовое число схемы См Из [25] следует, что Ъ{С) 4 /nlogn для любой примитивной схемы С степени п и ранга, не меньшего 3. Поэтому по теореме 3.12 получаем такое утверждение. Следствие 3.13 Если С - примитивная схема степени п и ранга, не меньшего 3, то s(C) \4 /nlogn] ut(C) [4у log n . Пример схемы ранга 2 показывает, что числа s{C) и t(C) могут сильно отличаться от числа Ь(С). С другой стороны, существуют нетривиальные примеры, для которых имеют место равенства. Действительно, пусть С - схема силыю-регулярного графа степени 10 на 26 вершинах, отмеченного как #4 в [84, с. 176]. Тогда прямое вычисление показывает, что Ъ(С) — 1. Поскольку группа Aut(C) интранзитивна, то схема С нешурова и потому t(C) 1. Кроме того, ${С) 2, поскольку существуют сильнорегулярные графы с теми же параметрами, не изоморфные данному.
Обобщённые сплетения S-колец
Пусть Лк - S-кольцо над группой Gk {к = 1,2), М - группа и 7Г0 : G\ — М и го : М — G2 - соответственно эпиморфизм и мономорфизм такие, что кегЫе5 (Л), Im(io) Є 5 (Лг), ( ) = ()-1). (102) Пусть, кроме того, G - некоторая группа и г: Gi — G и тг: G — G2 - мономорфизм и эпиморфизм такие, что 1т(г) кег(тг), тго о го = г о ТТ. (ЮЗ) Легко видеть, что кег(7г) = г(кег(7г0)) и 1т(г) = 7г_1(1т(го)) Теорема 4.4 Пусть А — наименьшее S-колъцо над группой G, содержащее мнооке-ство г{Л\) итГ Лг). Тогда S{A) = Si(A) U S2(A), 5І(Д) П S2{A) = 0, edeSi(A) = {i{X) : X Є S{A1)}uS2(A) = {n l{X) : X Є 5(Д8), С G2\Im(io7r)}. Доказательство. Обозначим через А подмодуль модуля C[G], порождённый множеством -Б = {(Х ) : X Є $i(A)US2(A)}. Из формул (102) и (103) следует, что 5і(Л)П52(Л) = 0 и элементы множества 5і(Л)и5г(-4) образуют разбиение группы G.
Таким образом, множество является С-базисом модуля А . Ясно, что, А С А. Поэтому для завершения доказательства достаточно проверить, что А С А . С этой целью мы докажем сначала, что множество г(Аі) итг 1(Л2) содержится в А , а затем установим, что модуль А замкнут относительно группового умножения в C[G]. Нетривиальная часть первого утверждения состоит D проверке того, что (тг-1 РО) Є t(A) Для всех X Є S(A2), X С Im(to тг). (104) Пусть X = (г о тг)(У) для некоторого Y (Z G\. Тогда в силу равенства і о -к = XQ О г0 мы имеем X = (тг0 г0)(У) = го(я"о(У))- Если теперь X Є ?(Ла), то формула (102) влечёт, что множество л"о(У) принадлежит множеству 5((го)-1(- 2)) и ([ о) 1( 2)) — 5(тто(Лі)). Поэтому 7Г0(У) Є S(jrD(.4i)). Предполагая, не умаляя общности, что Y есть объединение классов смежности по группе кег(їг0), мы заключаем, что Y S (Ai) (см. п. 1.5.1). Таким образом, - (х))=а -\(г о ооо))=ту)) и, следовательно, (тг 1(Х)) Є г (Лі). Пусть теперь Х ,У Є 5і(Л) U 53(Л). Докажем, что (X )(Y ) Є Л . Если Х ,У Є 5і(Л), то это есть следствие замкнутости кольца Лі относительно группового умножения в С[(?і]. Если X ,Y Є (Л), то это следует из непосредственно проверяемого равенства (6) (6) = -466), 6,6ЄС[С2Ь (105) где а = кег(тг), замкнутости кольца A i относительно умножения в C[G2] и формулы (104). Пусть, наконец, Xі є Sl[А) и У S2(A). Тогда X = і(Х) для X Є ?(Лі), У = тг"1 ) Для У е СЛг)» С G2\Im(io7r), и из равенства (102) мы находим, что 7г0( ) = (jo)_1(i?) для некоторого Z Є S(A2). Достаточно доказать, что аХ ШГ ) = bn-1(t(Z)t(Y)) (106) для некоторого целого Ъ. С этой целью заметим, что X С ir l(Z) и положительное целое число \X C\Lg\ не зависит от выбора Lg С it l{Z), где І = кег(7г) (см. п. 1.5.1). Обозначим это число через Ъ. Тогда, очевидно, {Х! П Lg) {Lh) = b(Lgh) для всех h Є G. С другой стороны, (Lp)(L/i) = a(Lgh). Таким образом, №)№) = Ъ Y, L9h) = Ь Е ( = (Ь/о)(т-г(г))(1А). Замечая теперь, что ,{Lh) — (7г_1(7г(І.Д)), суммируя по всем Lh С У (при этом {1} пробегает У) и применяя (105) для х (Z) и & — (У), мы получаем (Юб).и
Мы говорим, что S-кольцо А, определённое в теореме 4.4, является обобщённым сплетением S-колец Лі и А-г относительно М = (М, го,яо) и G = (G,i,n) и обозначаем его через Ai 1{м,о) Л.2. Если G\ - подгруппа группы G, GQ. - фактор-группа группы G с ядром L С G\, М — G\jL и г,г0, тг, 7г0 - естественные инъекции и сюръ-екции, то обобщённое сплетение называется стандартным. Легко видеть, что любое обобщённое сплетение отличается от стандартного лишь на изоморфизм Кэли.
Важный частный случай нашей конструкции, объясняющий её название, возникает при \М\ — 1. Если обобщённое сплетение является стандартным, то каждый элемент из $(А) либо совпадает с некоторым элементом из S(.4i) либо равен объединению классов смежности по G\, принадлежащих некоторому множеству X S(A2), X ф {1 ?Л; в этом случае схема Кэли, отвечающая кольцу Л, является сплетением схем, отвечающих Лі и Аі. Далее, группа G, над которой определено А, является расширением С?2 при помощи G\. Хорошо известно (см. [22]), что в абелевом случае классы таких расширений по модулю изоморфизмов, тождественных на G\ и G2, образуют относительно операции сложения расширений конечную абелеву группу Ext2(G2,Gi). Например, если группы G\ и G2 циклические порядков щ и п2, то группа Extz(G2,Gi) также циклическая, причём её порядок равен Н.О.Д.(пі,П2), а образующим отвечают циклические группы G.
Для произвольной тройки М. легко найти группу G1 и гомоморфизмы г и 7Г, удовлетворяющие соотношениям (103), причём, если группы Gi и ( циклические, то G также можно выбрать циклической. Конечно, в общем случае группа G не определяется единственным образом с точностью до изоморфизма. Более того, если такие группы и изоморфны, то отвечающие им обобщённые сплетения не обязаны быть изоморфными по Кэли даже при \М\ = 1. Тем не менее имеет место следующее утверждение, фактически вытекающее из доказываемой ниже леммы 4.8. Теорема 4.5 При фиксированных А\7 А2 и J\A все S-колъца А\ \{м,9) - 2 попарно сильно изоморфным Изучим теперь слабые изоморфизмы обобщённых сплетений, которые без умаления общности будем считать стандартными. Теорема 4.6 Пусть А = Лії(м,е) 2 иА = А хЦм ,g )A 2 -стандартные обобщённые сплетения. Тогда отображение V iVGnVG») (107) определяет биекцию между множеством слабых изоморфизмов р : А —+ А таких, что {GiY G\, {G2)4 = G2, и множеством пар ( ь г) слабых изоморфизмов i : Л\ — А[ и р2 : Аг А 2, для которых ( рі)м — ( г) м Доказательство.
Описание всех циркулянтпых S-колец (т.е. S-колец над конечными циклическими группами) было получено в [67, 68]. В следующих двух теоремах мы переформулируем эти результаты в виде, удобном для последующего использования. Ниже S-кольцо Л над группой G называется плотным, если множество Н(Л) содержит все подгруппы группы G. Легко видеть, что любое орбитное циркулянтное S-кольцо плотно.
Теорема 4.10 Пусть А - S-кольцо над конечной циклической группой G. Предположим, что оно не является плотным. Тогда справедливо по крайней мере одно из следующих двух утверждений: (1) Л нетривиально удовлетворяет U/L-условию для некоторых подгрупп L,U группы G таких, что произведение \L\-\G/U\ не является квадратом простого числа, (2) Л = Лі Лі1 где Лі - S-кольцо ранга 2 над подгруппой составного порядка группы G. Доказательство. Заметим, что в контексте теоремы утверждение (2) можно заменить на следующее: либо гк( 4) = 2, либо Л = Лі 8 Лг% где Лі ф Л и Лг ф Л. Действительно, если Л — Лі Л%, то Лі = Ла Лі — Лс2 ДО3 некоторых подгрупп С?і,С?2 Є "Н(Л) таких, что G = G\ х G2. Поскольку кольцо Л не является плотным, то по крайней мере одно из S-колец Лі, Лі, скажем Лі, также не является плотным, и потому по индукции можно считать, что для Лі выполнено утверждение (1) или утверждение (2). Во втором случае требуемое утверждение очевидно. В первом же случае кольцо А\ нетривиально удовлетворяет Ui /Li-условию для некоторых подгрупп L\, U\ группы Gi таких, что \Li\-\GijU\] не равно квадрату простого числа. Но тогда, очевидно, кольцо А нетривиально удовлетворяет U/L-условию для U = Ui х G2 и L = 1ц. Поскольку \G/U\ = \G\jUi\, требуемое утверждение доказано.
Выведем теорему из результатов статьи [68], сохраняя используемую в ней нумерацию утверждений. Не умаляя общности, будем считать, что гк(Л) 2. Предположим, что некоторая силовская подгруппа группы G не принадлежит множеству Н(А). Тогда легко видеть, что выполнено условие следствия 4.3 или теоремы 4.5. В первом случае по следствию 4.3 получаем, что либо А — А\ Аг, где А\ ф А, А% ф Л, либо А нетривиально удовлетворяет U/L-условию так, что число G/f/ является составным, и потому L \G/U\ не может быть квадратом простого числа. Во втором случае по теореме 4.5 кольцо А нетривиально удовлетворяет U/L-условию так, что \G/U\ — р - простое число. Согласно предложению 4.4, группа L может быть выбрана так, чтобы число \L\ не являлось степенью р, откуда снова следует требуемое утверждение. Пусть, наконец, множество Ti{A) содержит все силовские подгруппы группы G. Тогда по теореме 5.2 либо А = А\ А2, где А\ ф А, А ф А, либо кольцо А нетривиально удовлетворяет U/L-услоъию так, что одно из чисел \L\, \G/U\ делится на р2 для некоторого простого р. Таким образом, теорема полностью доказана.