Preview

Чебышевский сборник

Расширенный поиск

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

https://doi.org/10.22405/2226-8383-2014-15-4-55-123

Полный текст:

Аннотация

Работа посвящена получению оценок в теореме Ширшова о высоте. Слово 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. Диаграмма состояний (теория автоматов)


Для цитирования:


Харитонов М.И. ОЦЕНКИ, СВЯЗАННЫЕ С ТЕОРЕМОЙ ШИРШОВА О ВЫСОТЕ. Чебышевский сборник. 2014;15(4):55-123. https://doi.org/10.22405/2226-8383-2014-15-4-55-123

For citation:


Kharitonov M.I. ESTIMATES IN SHIRSHOV HEIGHT THEOREM. Chebyshevskii Sbornik. 2014;15(4):55-123. (In Russ.) https://doi.org/10.22405/2226-8383-2014-15-4-55-123

Просмотров: 104


Creative Commons License
Контент доступен под лицензией Creative Commons Attribution 4.0 License.


ISSN 2226-8383 (Print)