ОЦЕНКИ, СВЯЗАННЫЕ С ТЕОРЕМОЙ ШИРШОВА О ВЫСОТЕ

Работа посвящена получению оценок в теореме Ширшова о высоте. Слово W называется n-разбиваемым, если его можно представить в виде W = W0W1 · · · Wn где подслова W1, . . . , Wn идут в порядке лексикогра- фического убывания. Из не n-разбиваемых слов состоит базис алгебры с тождеством степени n. А. И. Ширшов показал, что множество слов, не яв- ляющихся n-разбиваемыми, над алфавитом из l букв имеет ограниченную высоту h над Y – множеством слов степени не выше n−1. Мы показываем, что h < Φ(n, l), где Φ(n, l) = 296l · n 12 log3 n+36 log3 log3 n+91 . Пусть l, n и d > n – некоторые натуральные числа. Тогда все слова над l-буквенном алфавитом длины больше, чем Ψ(n, d, l), либо содержат x d , либо являются n-разбиваемыми, где Ψ(n, d, l) = 227l(nd) 3 log3 (nd)+9 log3 log3 (nd)+36 . В 1993 году Е. И. Зельманов поставил следующий вопрос в Днестров- ской тетради: “Пусть F2,m – свободное 2-порожденное ассоциативное кольцо с тож- деством x m = 0. Верно ли, что класс нильпотентности кольца F2,m растет экспоненциально по m?” В работе показано, что в l-порожд¨енной ассоциативной алгебре с тождеством x d = 0 класс нильпотентности меньше, чем Ψ(d, d, l). Тем самым получаются субэкспоненциальные оценки на индекс нильпотентно- сти ниль-алгебр для произвольной характеристики. Изначальная оценка высоты у Ширшова носила рекурсивный характер, в 1982 году была получена двойная экспонента, в 1992 году – экспо- ненциальная оценка. Доказательство использует идею В. Н. Латышева, связанную с приме- нением теоремы Дилуорса к исследованию не n-разбиваемых слов. Нам представляется, что теорема о высоте имеет глубокую связь с задачами современной комбинаторики, в частности, Рамсеевского типа. С помощью такого рода соображений получаются верхние и нижние оценки количества периодов длины 2, 3,(n−1) в не n-разбиваемом слове, отличающиеся только постоянным множителем.

1. Burnside W. On an unsettled question in the theory of discontinuous groups // Quart. J. Math. 1902. Vol. 33. P. 230–238.

2. Курош А. Г. Проблемы теории колец, связанные с проблемой Бeрнсайда о периодических группах // Изв. АН СССР. Сер. Мат. 1941. Т. 5, вып. 3. C. 233–240.

3. Kaplansky I. On a problem of Kurosch and Jacobson // Bull. AMer. Math. Soc. 1946. Vol. 52. P. 496–500.

4. Levitzki J. On a problem of A. Kurosch // Bull. AMer. Math. Soc. 1946. Vol. 52. P. 1033–1035.

5. Dilworth R. P. A Decomposition Theorem for Partially Ordered Sets // Annals of Mathematics. 1950. Vol. 51(1). P. 161–166.

6. Ширшов А. И. Подалгебры свободных лиевых алгебр // Мат. сб. 1953. Т. 33(75), № 2. C. 441–452.

7. Ширшов А. И. Подалгебры свободных коммутативных и свободных анти- коммутативных алгебр // Мат. сб. 1954. Т. 34(76), № 1. C. 81–88.

8. Ширшов А. И. О кольцах с тождественными соотношениями // Мат. сб. 1957. Т. 43(85), № 2. C. 277–283.

9. Ширшов А. И. О некоторых неассоциативных нилькольцах и алгебраических алгебрах // Мат. сб. 1957. Т. 41(83), № 3. C. 381–394.

10. Ширшов А. И. О свободных адгебрах Ли // Мат. сб. 1958. Т. 45(87), № 2. C. 113–122.

11. Ширшов А. И. Некоторые алгоритмические проблемы для ϵ-алгебр // Сиб. мат. журн. 1962. T. 3, № 1. C. 132–137.

12. Ширшов А. И. Некоторые алгоритмические проблемы для алгебр Ли // Сиб. мат. журн. 1962. T. 3, № 2. C. 292–296.

13. Belov A. J., Borisenko V. V., Latysev V. N. Monomial Algebras / A. J. Belov, V. V. Borisenko, V. N. Latysev. — NY.: Plenum, 1997.

14. Уфнаровский В. А. Комбинаторные и асимптотические методы в алгебре // Итоги науки и техн.. Сер. Соврем. пробл. мат. Фундам. направления. 1990. № 57. С. 5–177.

15. Пчелинцев С. В. Теорема о высоте для альтернативных алгебр // Мат. сб. 1984. T. 124, № 4. C. 557–567.

16. Мищенко С. П. Вариант теоремы о высоте для алгебр Ли // Мат. заметки. 1990. T. 47, № 4. C. 83–89.

17. Белов А. Я. О базисе Ширшова относительно свободных алгебр сложно- сти n // Мат. сб. 1988. T. 135, № 31. C. 373–384.

18. Kanel-Belov A., Rowen L. H. Computational aspects of polynomial identities / A. Kanel-Belov, L. H. Rowen. Research Notes in Mathematics 9. — Wellesley, MA: AK Peters, Ltd., 2005.

19. Ciocanu Gh. Independence and quasiregularity in algebras. II. // Izv. Akad. Nauk Respub. Moldova Mat. 1997. № 70. P. 70–134.

20. Ciocanu Gh. Local finiteness of algebras // Mat. Issled Moduli, Algebry, Topol. 1988. №105. P. 153–198.

21. Ciocanu Gh., Kozhukhar E. P. Independence and nilpotency in algebras // Izv. Akad. Nauk Respub. Moldova Mat. 1993. № 2. P. 51–95.

22. Ciocanu Gh. Independence and quasiregularity in algebras // Dokl. Akad. Nauk. 1994. Vol. 337, no. 3.

23. Уфнаровский В. А. Теорема о независимости и ее следствия // Мат. сб. 1985. Т. 128(170), № 1(9). C. 124–132.

24. Ufnarovskii V. A., Ciocanu Gh. Nilpotent matrices // Mat. Issled. Algebry, Koltsa i Topologii. 1985. № 85. P. 130–155.

25. Белов А. Я. О рациональности рядов Гильберта относительно свободных алгебр // Успехи мат. наук. 1997. T. 52, № 2. P. 153–154.

26. Lothaire M. Combinatorics of words // Cambridge: Cambridge mathematical library, 1983.

27. Латышев В. Н. Комбинаторные порождающие полилинейных полиномиальных тождеств // Фундам. и прикл. мат. 2006. Т. 12, № 2. С. 101–110.

28. Колотов А. Г. О верхней оценке высоты в конечно порожденных алгебрах с тождествами // Сиб. мат. журн. 1982. T. 23, № 1. С. 187–189.

29. Днестровская тетрадь: оперативно-информац. сборник. 4-е изд., Новосибирск: изд. ин–та мат. СО АН СССР, 1993. — 73 C.

30. Belov A. Ya. Some estimations for nilpotency of nil-algebras over a field of an arbitrary characteristic and height theorem // Commun. Algebra. 1992. Vol. 20, № 10. P. 2919–2922.

31. Drensky V. Free Algebras and PI-algebras: Graduate Course in Algebra // Singapore: Springer-Verlag, 2000.

32. Харитонов М. И. Оценки на структуру кусочной периодичности в теореме Ширшова о высоте // Вестник Московского университета, Серия 1, Математика. Механика. 2013. №1. C. 10–16.

33. Харитонов М. И. Оценки на количество перестановочно упорядоченных множеств // Вестник Московского университета, Серия 1, Математика. Механика. 2015. № 2. В печати. 34. Klein A. A. Indices of nilpotency in a P I-ring // Archiv der Mathematik. 1985. Vol. 44, № 4. P. 323–329.

34. Klein A. A. Bounds for indices of nilpotency and nility // Archiv der Mathematik. 2000. Vol. 74, № 1. P. 6–10.

35. Procesi C. Rings with polynomial identities // N.Y.: 1973. — 189 p.

36. Белов А. Я. Размерность Гельфанда–Кириллова относительно свободных ассоциативных алгебр // Мат. сб. 2004. Т. 195, № 12. P. 3–26.

37. Кузьмин Е. Н. О теореме Нагаты-Хигмана // Cб. трудов, посвященный 60-летию акад. Илиева. София, 1975 — С. 101–107.

38. Размыслов Ю. П. Тождества алгебр и их представлений. М.: Наука, 1989. 432 с.

39. Жевлаков К. А., Слинько А. М., Шестаков И. П., Ширшов А. И. Кольца, близкие к ассоциативным, первое издание. M.: Современная алгебра. 1978. 438 с.

40. Белов А. Я. Проблемы бернсайдовского типа, теоремы о высоте и о независимости // Фундам. и прикл. мат. 2007. Т. 13, вып. 5. C. 19–79.

41. Lopatin A. A. On the nilpotency degree of the algebra with identity x n = 0 // Journal of Algebra. 2012. № 371. P. 350–366.

42. Чибриков Е. С. О высоте Ширшова конечнопорожденной ассоциативной алгебры, удовлетворяющей тождеству степени четыре // Известия Алтайского государственного университета. 2001. № 1(19). C. 52–56.

43. Харитонов М. И. Двусторонние оценки существенной высоты в теореме Ширшова о высоте // Вестник Московского университета. Серия 1, Математика. Механика. 2012. № 2. C. 20–24.

44. Белов А. Я., Харитонов М. И. Субэкспоненциальные оценки в теореме Шир- шова о высоте // Мат. сб. 2012. № 4. С. 81–102.

45. Белов А. Я. О нешпехтовых многообразиях // Фундам. и прикл. мат. 1999. Т. 5, вып. 1. C. 47–66.

46. Белов А. Я., Харитонов М. И. Оценки высоты в смысле Ширшова и на ко- личество фрагментов малого периода // Фундам. и прикл. мат. 2012. Т. 17, вып. 5. C. 21–54.

47. Челноков Г. Р. О нижней оценке количества k+1-разбиваемых перестановок // Модел. и анализ информ. систем. 2007. Т. 14, №4. C. 53–56.

48. Gessel I. M. Symmetric Functions and P-Recursiveness // J. Combin. Theory Ser. A. 1990. Vol. 53. P. 257–285.

49. Гришин А. В. Примеры не конечной базируемости Т-пространств и Т- идеалов в характеристике 2 // Фундам. и прикл. мат. 1999. Т. 5, вып. 1. C. 101–118.

50. Кемер А. Р. Конечная базируемость тождеств ассоциативных алгебр // Ал- гебра и логика. 1987. T. 26, №5. C. 597–641.

51. Knuth D. E. Permutations, matrices, and generalized Young tableux // Pacific journal of mathematics. 1970. Vol. 34, № 3. P. 709–727.

52. Латышев В. Н. К теореме Регева о тождествах тензорного произведения PI-алгебр // УМН. 1972. Т. 27, №4(166). C. 213–214.

53. Латышев В. Н. Нематричные многообразия ассоциативных алгебр. М.: Изд- во Моск. ун-та, 1977.

54. Schensted C. Longest increasing and decreasing subsequences // Canad. J. Math. 1961. №13. P. 179–191.

55. Щиголев В. В. Примеры бесконечно базируемых T-идеалов // Фундам. и прикл. мат. 1999. Т. 5, вып. 1. C. 307–312.

56. Specht W. Gesetze in Ringen. I. // Math. Z. 1950. Vol. 52. P. 557–589.

57. Sapir M. V. Combinatorial algebra: syntax and semantics // Springer, 2014.

58. Amitsur S. A., Levitzki J. Minimal identities for algebras // Proc. Amer. Math. Soc. 1950. №2. P. 449–463.

59. Li F., Tzameret I. Matrix dentities and proof complexity lower bounds // 2013.

60. Lopatin A. A., Shestakov I. P. Associative nil-algebras over finite fields // International Journal of Algebra and Computation. 2013. Vol. 23, № 8. P. 1881– 1894.

61. Бугаенко В. О. Обобщенная теорема Ван дер Вардена // Мат. просвещение. Сер. 3. 2006. Вып. 10. С. 151 – 160.

62. Хинчин А. Я. Три жемчужины теории чисел. М.: Наука, 1979.

63. Клячко А. А. Спецкурс по теории групп. 2009.

64. Зимин А. И. Блокирующие множества термов // Мат. сб. 1982. Т. 119(161), № 3(11). C. 363–375.

65. Regev A. Existence of polinomial identities in A ⊗F B // Bull. Amer. Math. Soc. 1971. Vol. 77, № 6. P. 1067–1069.

66. Фрид А. Э. Введение в комбинаторику слов: лекции, 2011.

67. Bergman G. M. The Diamond Lemma for Ring Theory // Advances in mathematics. 1978. Vol. 29. P. 178–218.

68. Beidar K. I., Martindale W. S. III, Mikhalev A. V. Rings with generalized identities // K. I. Beidar, W. S. Martindale III, A. V. Mikhalev. Pure and applied mathematics, 1995.

69. Латышев В. Н. ЕНС Прикладные проблемы алгебры. 2012.

70. Kaplansky I. Rings with a polynomial identity // Bull. Amer. Math. Soc. 1948. Vol. 54. P. 575–580.

71. Thue A. Uber unendliche Zeichenreihen // Norske Vid. Selsk. Skr., I. Mat. Nat. ¨ Kl., Christiana. 1906. Vol. 7. P. 1–22.

72. Morse M. Recurrent Geodesics on a Surface of Negative Curvature // Trans. Amer. Math. Soc. 1921. Vol. 22. P. 84–100.

73. Berstel J. Mots sans carr´e et morphismes it´er´es // Discrete Math. 1979. Vol. 29. P. 235–244.

74. Berstel J. Sur les mots sans carr´e d´efinis par un morphisme // Springer-Verlag, 1979.

75. Crochemore M. Sharp characterizations of square-free morphisms // Theoret. Comput. Sci. 1982. Vol. 18. P. 221–226.

76. wiki:en. Rauzy fractal.

77. wiki:ru. Минимальная форма автомата.

78. wiki:ru. Диаграмма состояний (теория автоматов)