ESTIMATES IN SHIRSHOV HEIGHT THEOREM
https://doi.org/10.22405/2226-8383-2014-15-4-55-123
Abstract
The paper is devoted to subexponential estimations in Shirshov’s Height theorem. A word W is n-divisible, if it can be represented in the following form: W = W0W1 · · · Wn such that W1 ≺ W2 ≺ · · · ≺ Wn. If an affine algebra A satisfies polynomial identity of degree n then A is spanned by non n-divisible words of generators a1 ≺ · · · ≺ al . A. I. Shirshov proved that the set of non n-divisible words over alphabet of cardinality l has bounded height h over the set Y consisting of all the words of degree 6 n−1. We show, that h < Φ(n, l), where Φ(n, l) = 296l · n 12 log3 n+36 log3 log3 n+91 . Let l, n и d > n be positive integers. Then all the words over alphabet of cardinality l which length is greater than Ψ(n, d, l) are either n-divisible or contain d-th power of subword, where Ψ(n, d, l) = 227l(nd) 3 log3 (nd)+9 log3 log3 (nd)+36 . In 1993 E. I. Zelmanov asked the following question in Dniester Notebook: “Suppose that F2,m is a 2-generated associative ring with the identity x m = 0. Is it true, that the nilpotency degree of F2,m has exponential growth?” We give the definitive answer to E. I. Zelmanov by this result. We show that the nilpotency degree of l-generated associative algebra with the identity x d = 0 is smaller than Ψ(d, d, l). This imply subexponential estimations on the nilpotency index of nil-algebras of an arbitrary characteristics. Original Shirshov’s estimation was just recursive, in 1982 double exponent was obtained, an exponential estimation was obtained in 1992.
Our proof uses Latyshev idea of Dilworth theorem application. We think that Shirshov’s height theorem is deeply connected to problems of modern combinatorics. In particular this theorem is related to the Ramsey theory. We obtain lower and upper estimates of the number of periods of length 2, 3,(n−1) in some non n-divisible word. These estimates are differ only by a constant
About the Author
M. I. Kharitonov
Московский государственный университет имени М. В. Ломоносова
Russian Federation
Russian Federation
References
1. Burnside, W. 1902, "On an unsettled question in the theory of discontinuous groups" , Quart. J. Math., vol. 33, pp. 230–238.
2. Kurosch, А. 1941, "Ringtheoretische Probleme, die mit dem Burnsideschen Problem ¨uber periodische Gruppen in Zusammenhang stehen" , Izv. Akad. Nauk SSSR, Ser. Mat., vol. 5, iss. 3, pp. 233–240. (Russian)
3. Kaplansky, I. 1946, "On a problem of Kurosch and Jacobson" , Bull. AMer. Math. Soc., vol. 52., pp. 496–500.
4. Levitzki, J. 1946, "On a problem of A. Kurosch" , Bull. AMer. Math. Soc., vol. 52, pp. 1033–1035.
5. Dilworth, R. P. 1950, "A Decomposition Theorem for Partially Ordered Sets" , Annals of Mathematics., vol. 51(1), pp. 161–166.
6. Shirshov, А. I. 1953, "Subalgebras of free Lie algebras" , Mat. Sb. (N.S.), vol. 33(75), no. 2, pp. 441–452. (Russian)
7. Shirshov, А. I. 1954, "Subalgebras of free commutative and free anticommutative algebras" , Mat. Sb. (N.S.), vol. 34(76), no. 1, pp. 81–88. (Russian)
8. Shirshov, А. I. 1957, "On rings with identity relations" , Mat. Sb. (N.S.), vol. 43(85), no. 2, pp. 277–283. (Russian)
9. Shirshov, А. I. 1957, "On some non-associative null-rings and algebraic algebras" , Mat. Sb. (N.S.), vol. 41(83), no. 3., pp. 381–394. (Russian)
10. Shirshov, А. I. 1958, "On free Lie rings" , Mat. Sb. (N.S.), vol. 45(87), №2, pp. 113–122. (Russian)
11. Shirshov, А. I. 1962, "Nekotorye algoritmicheskie problemy dlja ϵ-algebr" , Sib. Mat. J., vol. 3, №1, pp. 132–137. (Russian)
12. Shirshov, А. I. 1962, "Nekotorye algoritmicheskie problemy dlja algebr Li" , Sib. Mat. J., vol. 3, №2, pp. 292–296. (Russian)
13. Belov, A. J., Borisenko, V. V. & Latysev, V. N. 1997, "Monomial Algebras" , NY.: Plenum.
14. Ufnarovskii, V. А. 1990, "Combinatorial and asymptotic methods in algebra" , Itogi Nauki i Tekhniki, Ser. Sovrem. Probl. Mat. Fund. Napr. № 57, pp. 5–177. (Russian)
15. Pchelintsev, S. V. 1984, "A theorem on height for alternative algebras" , Mat. Sb. (N.S.)., vol. 124, № 4, pp. 557–567. (Russian)
16. Mishchenko, S. P. 1990, "A variant of the height theorem for Lie algebras" , Mat. zametki., vol. 47, № 4, pp. 83–89. (Russian)
17. Belov, А. Ya. 1988, "On a Shirshov basis of relatively free algebras of complexity n" , Matem. sb., vol. 135, № 31, pp. 373–384. (Russian)
18. Kanel-Belov, A. & Rowen, L. H. 2005, "Computational aspects of polynomial identities" , Research Notes in Mathematics 9. Wellesley, MA: AK Peters, Ltd.
19. Ciocanu, Gh. 1997, "Independence and quasiregularity in algebras. II." , Izv. Akad. Nauk Respub. Moldova Mat. № 70, pp. 70–134.
20. Ciocanu, Gh. 1988, "Local finiteness of algebras" , Mat. Issled Moduli, Algebry, Topol. №105, pp. 153–198.
21. Ciocanu, Gh. & Kozhukhar, E. P. 1993, "Independence and nilpotency in algebras" , Izv. Akad. Nauk Respub. Moldova Mat. № 2, pp. 51–95.
22. Ciocanu, Gh. 1994, "Independence and quasiregularity in algebras" , Dokl. Akad. Nauk., vol. 337, no. 3.
23. Ufnarovskii, V. A. 1985, "An independence theorem and its consequences" , Mat. Sb. (N.S.)., vol. 128(170), no. 1(9), pp. 124–132. (Russian)
24. Ufnarovskii, V. A. & Ciocanu, Gh. 1985, "Nilpotent matrices" , Mat. Issled. Algebry, Koltsa i Topologii. № 85, pp. 130–155.
25. Belov, А. Ya. 1997, "On the rationality of Hilbert series of relatively free algebras" , Russian Math. Surveys., vol. 52, № 2, pp. 153–154. (Russian)
26. Lothaire, M. 1983, "Combinatorics of words" , Cambridge: Cambridge mathematical library.
27. Latyshev, V. N. 2006, "Combinatorial generators of the multilinear polynomial identities" , Fundam. Prikl. Mat., vol. 12, no. 2, pp. 101–110. (Russian)
28. Kolotov, A. G. 1982, "An upper estimate for height in finitely generated algebras with identities" , Sib. Mat. J., vol. 23, № 1, pp. 187–189. (Russian)
29. "Dnestr copy-book: a collection of operative information. Issue 4," , Novosibirsk: Institute of mathematics, SO AN USSR, 1993. — 73 p. (Russian)
30. Belov, A. Ya. 1992, "Some estimations for nilpotency of nil-algebras over a field of an arbitrary characteristic and height theorem" , Commun. Algebra., vol. 20, № 10, pp. 2919–2922.
31. Drensky, V. 2000, "Free Algebras and PI-algebras: Graduate Course in Algebra" , Singapore: Springer-Verlag
32. Kharitonov, M. I. 2013, "Estimates of a structure of piece-wise periodicity in Shirshov’s height theorem" , Moscow University Mathematics Bulletin, Seriya 1, Matematika. Mekhanika. №1, pp. 10–16. (Russian)
33. Kharitonov, M. I. 2015, "Estimates on the number of partially ordered sets" , Moscow University Mathematics Bulletin, Seriya 1, Matematika. Mekhanika. № 2. In print. (Russian)
34. Klein, A. A. 1985, "Indices of nilpotency in a P I-ring" , Archiv der Mathematik., vol. 44, № 4, pp. 323–329.
35. Klein, A. A. 2000, "Bounds for indices of nilpotency and nility" , Archiv der Mathematik., vol. 74, № 1, pp. 6–10.
36. Procesi, C. 1973, "Rings with polynomial identities" , N.Y. 189 p.
37. Belov, А. Ya. 2004, "The Gel’fand–Kirillov dimension of relatively free associative algebras" , Sb. Math., vol. 195, no. 12, pp. 3–26. (Russian)
38. Kuzmin, E. N. 1975, "O teoreme Nagaty-Higmana" , Collection of papers dedicated to the 60th anniversary of academician Iliev. Sofia, pp. 101–107. (Russian)
39. Razmyslov, Yu. P. 1989, "Identities of algebras and their representations" , М.: Nauka, 432 p. (Russian)
40. Zhevlakov, K. A., Slinko, A. M., Shestakov, I. P. & Shirshov, A. I. 1978, "Kol’ca, blizkie k associativnym, first edition" , M.: Sovremennaja algebra. (Russian)
41. Belov, А. Ya. 2007, "Burnside-type problems, theorems on height, and independence" , J. Math. Sci., vol. 13, no. 5, pp. 19–79. (Russian)
42. Lopatin, A. A. 2012, "On the nilpotency degree of the algebra with identity x n = 0" , Journal of Algebra. № 371, pp. 350–366.
43. Chibrikov, Ye. S. 2001, "On Shirshov height of a finitely generated associative algebra satisfying an identity of degree four" , Izvestiya Altaiskogo gosudarstvennogo universiteta. №1(19), pp. 52–56. (Russian)
44. Kharitonov, M. I. 2012, "Estimates of a structure of piece-wise periodicity in Shirshov’s height theorem" , Moscow University Mathematics Bulletin, Seriya 1, Matematika. Mekhanika. №2, pp. 20–24. (Russian)
45. Belov, А. Ya. & Kharitonov, М. I. 2012, "Subexponential estimates in Shirshov’s theorem on height" , Sb. Math. №4, pp. 81–102. (Russian)
46. Belov, А. Ya. 1999, "On non-Spechtian varieties" , J. Math. Sci., vol. 5, no. 1, pp. 47–66. (Russian)
47. Belov, А. Ya. & Kharitonov, М. I. 2012, "Subexponential estimates in the height theorem and estimates on numbers of periodic parts of small periods" , J. Math. Sci., vol. 17, no. 5, pp. 21–54. (Russian)
48. Chelnokov, G. R. 2007, "On the lower estimate for k+1-nondecomposible permutations " , Model. Anal. Inform. Sist., vol. 14, №4, pp. 53–56. (Russian)
49. Gessel, I. M. 1990, "Symmetric Functions and P-Recursiveness" , J. Combin. Theory Ser. A., vol. 53, pp. 257–285.
50. Grishin, А. V. 1999, "Examples of T-spaces and T-ideals over a field of characteristic 2 without the finite basis property" , Fundam. Prikl. Mat., vol. 5, no. 1, pp. 101–118. (Russian)
51. Kemer, A. R. 1987, "Konechnaja baziruemost’ tozhdestv associativnyh algebr" , Algebra i logika., vol. 26, №5, pp. 597–641. (Russian)
52. Knuth, D. E. 1970, "Permutations, matrices, and generalized Young tableux" , Pacific journal of mathematics., vol. 34, № 3, pp. 709–727.
53. Latyshev, V. N. 1972, "On Regev’s theorem on identities in a tensor product of PI-algebras" , Uspekhi Mat. Nauk., vol. 27, №4(166), pp. 213–214. (Russian)
54. Latyshev, V. N. 1977, "Nonmatrix varieties of associative algebras" , М.: MSU. (Russian)
55. Schensted, C. 1961, "Longest increasing and decreasing subsequences" , Canad. J. Math. №13, pp. 179–191.
56. Shchigolev, V. V. 1999, "Examples of infinitely based T-ideals" , Fundam. Prikl. Mat., vol. 5, no. 1, pp. 307–312. (Russian)
57. Specht, W. 1950, "Gesetze in Ringen. I." , Math. Z., vol. 52, pp. 557–589.
58. Sapir, M. V. 2014, "Combinatorial algebra: syntax and semantics" , Springer.
59. Amitsur, S. A. & Levitzki, J.1950, "Minimal identities for algebras" , Proc. Amer. Math. Soc. №2, pp. 449–463.
60. Li, F. & Tzameret, I. 2013, "Matrix dentities and proof complexity lower bounds."
61. Lopatin, A. A. & Shestakov, I. P. 2013, "Associative nil-algebras over finite fields" , International Journal of Algebra and Computation., vol. 23, № 8, pp. 1881–1894.
62. Bugaenko, V. О. 2006, "Obobshhennaja teorema Van der Vardena" , Mat. Pros., Ser. 3. №10, pp. 151–160. (Russian)
63. Hinchin, A. Ja. 1979, "Tri zhemchuzhiny teorii chisel" , M.: Nauka. (Russian)
64. Klyachko, А. А. 2009, "Special Course on Group Theory" . (Russian)
65. Zimin, А. I. 1982, "Blocking sets of terms" , Mat. Sb. (N.S.), vol. 119(161), № 3(11), pp. 363–375. (Russian)
66. Regev, A. 1971, "Existence of polinomial identities in A ⊗F B" , Bull. Amer. Math. Soc., vol. 77, no. 6, pp. 1067–1069.
67. Frid, А. E. 2011, "Introduction to the combinatorics of words" , Lections (Russian)
68. Bergman, G. M. 1978, "The Diamond Lemma for Ring Theory" , Advances in mathematics., vol. 29, pp. 178–218.
69. Beidar, K. I., Martindale, W. S. III & Mikhalev, A. V. 1995, "Rings with generalized identities" , Pure and applied mathematics.
70. Latyshev, V. N. 2012, "ENS Prikladnye problemy algebry" . (Russian)
71. Kaplansky, I. 1948, "Rings with a polynomial identity" , Bull. Amer. Math. Soc., vol. 54, pp. 575–580.
72. Thue, A. 1906, "Uber unendliche Zeichenreihen" , ¨ Norske Vid. Selsk. Skr., I. Mat. Nat. Kl. Christiana., vol. 7, pp. 1–22.
73. Morse, M. 1921, "Recurrent Geodesics on a Surface of Negative Curvature" , Trans. Amer. Math. Soc., vol. 22, pp. 84–100.
74. Berstel, J. 1979, "Mots sans carr´e et morphismes it´er´es" , Discrete Math., vol. 29, pp. 235–244.
75. Berstel, J. 1979, "Sur les mots sans carr´e d´efinis par un morphisme" , SpringerVerlag.
76. Crochemore, M. 1982, "Sharp characterizations of square-free morphisms" , Theoret. Comput. Sci., vol. 18, pp. 221–226.
77. wiki:en. Rauzy fractal.
78. wiki:ru. Minimal’naja forma avtomata.
79. wiki:en. State diagram.
Review
For citations:
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
Views:
435
Email this article 