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

• Евдокимов, Сергей Алексеевич
• доктор физико-математических наук
• 2004

Оглавление диссертации доктор физико-математических наук Евдокимов, Сергей Алексеевич

Введение

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 глав, к изложению основных результатов которых мы и переходим.

Список литературы диссертационного исследования доктор физико-математических наук Евдокимов, Сергей Алексеевич, 2004 год

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.