Estimates in Shirshov Height theorem

M. I. Kharitonov

Čebyševskij sbornik, Tome 15 (2014) no. 4, pp. 55-123.

Résumé

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=W_0W_1\cdots W_n$ such that $W_1\prec W_2\prec\dots\prec W_n$. If an affine algebra $A$ satisfies polynomial identity of degree $n$ then $A$ is spanned by non $n$-divisible words of generators $a_1\prec\dots\prec a_l$. 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 $\leqslant n-1$. We show, that $h\Phi(n,l)$, where $$\Phi(n,l) = 2^{96} l\cdot n^{12\log_3 n + 36\log_3\log_3 n + 91}.$$ Let $l$, $n$ и $d \geqslant n$ be positive integers. Then all the words over alphabet of cardinality $l$ which length is greater than $\Psi(n,d,l)$ are either $n$-divisible or contain $d$-th power of subword, where $$\Psi(n,d,l)=2^{27} l (nd)^{3 \log_3 (nd)+9\log_3\log_3 (nd)+36}.$$ In 1993 E. I. Zelmanov asked the following question in Dniester Notebook: "Suppose that $F_{2, m}$ is a 2-generated associative ring with the identity $x^m=0.$ Is it true, that the nilpotency degree of $F_{2, 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 $\Psi(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. Bibliography: 79 titles.

Détail

Keywords: Height theorem, combinatorics on words, $n$-divisibility, Dilworth theorem, Burnside type problems.

Bibliographie

[1] Burnside W., “On an unsettled question in the theory of discontinuous groups”, Quart. J. Math., 33 (1902), 230–238

[2] Kurosch A., “Ringtheoretische Probleme, die mit dem Burnsideschen Problem über periodische Gruppen in Zusammenhang stehen”, Izv. Akad. Nauk SSSR, Ser. Mat., 5:3 (1941), 233–240 (Russian)

[3] Kaplansky I., “On a problem of Kurosch and Jacobson”, Bull. Amer. Math. Soc., 52 (1946), 496–500 | DOI

[4] Levitzki J., “On a problem of A. Kurosch”, Bull. AMer. Math. Soc., 52 (1946), 1033–1035 | DOI

[5] Dilworth R. P., “A Decomposition Theorem for Partially Ordered Sets”, Annals of Mathematics, 51:1 (1950), 161–166 | DOI

[6] Shirshov A. I., “Subalgebras of free Lie algebras”, Mat. Sb. (N.S.), 33(75):2 (1953), 441–452 (Russian)

[7] Shirshov A. I., “Subalgebras of free commutative and free anticommutative algebras”, Mat. Sb. (N.S.), 34(76):1 (1954), 81–88 (Russian)

[8] Shirshov A. I., “On rings with identity relations”, Mat. Sb. (N.S.), 43(85):2 (1957), 277–283 (Russian)

[9] Shirshov A. I., “On some non-associative null-rings and algebraic algebras”, Mat. Sb. (N.S.), 41(83):3 (1957), 381–394 (Russian)

[10] Shirshov A. I., “On free Lie rings”, Mat. Sb. (N.S.), 45(87):2 (1958), 113–122 (Russian)

[11] Shirshov A. I., “Nekotorye algoritmicheskie problemy dlja $\epsilon$-algebr”, Sib. Mat. J., 3:1 (1962), 132–137 (Russian)

[12] Shirshov A. I., “Nekotorye algoritmicheskie problemy dlja algebr Li”, Sib. Mat. J., 3:2 (1962), 292–296 (Russian)

[13] Belov A. J., Borisenko V. V., Latysev V. N., Monomial Algebras, Plenum, N.Y., 1997

[14] Ufnarovskii V. A., “Combinatorial and asymptotic methods in algebra”, Itogi Nauki i Tekhniki, Ser. Sovrem. Probl. Mat. Fund. Napr., 57, 1990, 5–177 (Russian)

[15] Pchelintsev S. V., “A theorem on height for alternative algebras”, Mat. Sb. (N.S.), 124:4 (1984), 557–567 (Russian)

[16] Mishchenko S. P., “A variant of the height theorem for Lie algebras”, Mat. zametki, 47:4 (1990), 83–89 (Russian)

[17] Belov A. Ya., “On a Shirshov basis of relatively free algebras of complexity $n$”, Matem. sb., 135:31 (1988), 373–384 (Russian)

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

[19] Ciocanu Gh., “Independence and quasiregularity in algebras, II”, Izv. Akad. Nauk Respub. Moldova Mat., 1997, no. 70, 70–134

[20] Ciocanu Gh., “Local finiteness of algebras”, Mat. Issled Moduli, Algebry, Topol., 105 (1988), 153–198

[21] Ciocanu Gh., Kozhukhar E. P., “Independence and nilpotency in algebras”, Izv. Akad. Nauk Respub. Moldova Mat., 1993, no. 2, 51–95

[22] Ciocanu Gh., “Independence and quasiregularity in algebras”, Dokl. Akad. Nauk, 337:3 (1994)

[23] Ufnarovskii V. A., “An independence theorem and its consequences”, Mat. Sb. (N.S.), 128(170):1(9) (1985), 124–132 (Russian)

[24] Ufnarovskii V. A., Ciocanu Gh., “Nilpotent matrices”, Mat. Issled. Algebry, Koltsa i Topologii, 85 (1985), 130–155

[25] Belov A. Ya., “On the rationality of Hilbert series of relatively free algebras”, Russian Math. Surveys, 52:2 (1997), 153–154 (Russian) | DOI

[26] Lothaire M., Combinatorics of words, Cambridge mathematical library, Cambridge, 1983

[27] Latyshev V. N., “Combinatorial generators of the multilinear polynomial identities”, Fundam. Prikl. Mat., 12:2 (2006), 101–110 (Russian)

[28] Kolotov A. G., “An upper estimate for height in finitely generated algebras with identities”, Sib. Mat. J., 23:1 (1982), 187–189 (Russian)

[29] Dnestr copy-book: a collection of operative information, 4 ed., Institute of mathematics, SO AN USSR, Novosibirsk, 1993, 73 pp. (Russian)

[30] Belov A. Ya., “Some estimations for nilpotency of nil-algebras over a field of an arbitrary characteristic and height theorem”, Commun. Algebra, 20:10 (1992), 2919–2922 | DOI

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

[32] Kharitonov M. I., “Estimates of a structure of piece-wise periodicity in Shirshov's height theorem”, Moscow University Mathematics Bulletin, Seriya 1, Matematika. Mekhanika, 2013, no. 1, 10–16 (Russian)

[33] Kharitonov M. I., “Estimates on the number of partially ordered sets”, Moscow University Mathematics Bulletin, Seriya 1, Matematika. Mekhanika, 2015, no. 2 (Russian)

[34] Klein A. A., “Indices of nilpotency in a $PI$-ring”, Archiv der Mathematik, 44:4 (1985), 323–329 | DOI

[35] Klein A. A., “Bounds for indices of nilpotency and nility”, Archiv der Mathematik, 74:1 (2000), 6–10 | DOI

[36] Procesi C., Rings with polynomial identities, N.Y., 1973, 189 pp.

[37] Belov A. Ya., “The Gel'fand–Kirillov dimension of relatively free associative algebras”, Sb. Math., 195:12 (2004), 3–26 (Russian) | DOI

[38] Kuzmin E. N., “O teoreme Nagaty–Higmana”, Collection of papers dedicated to the 60th anniversary of academician Iliev, Sofia, 1975, 101–107 (Russian)

[39] Razmyslov Yu. P., Identities of algebras and their representations, Nauka, M., 1989, 432 pp. (Russian)

[40] Zhevlakov K. A., Slinko A. M., Shestakov I. P., Shirshov A. I., Kol'ca, blizkie k associativnym, first edition, Sovremennaja algebra, M., 1978 (Russian)

[41] Belov A. Ya., “Burnside-type problems, theorems on height, and independence”, J. Math. Sci., 13:5 (2007), 19–79 (Russian)

[42] Lopatin A. A., “On the nilpotency degree of the algebra with identity $x^n = 0$”, Journal of Algebra, 371 (2012), 350–366 | DOI

[43] Chibrikov Ye. S., “On Shirshov height of a finitely generated associative algebra satisfying an identity of degree four”, Izvestiya Altaiskogo gosudarstvennogo universiteta, 2001, no. 1(19), 52–56 (Russian)

[44] Kharitonov M. I., “Estimates of a structure of piece-wise periodicity in Shirshov's height theorem”, Moscow University Mathematics Bulletin, Seriya 1, Matematika. Mekhanika, 2012, no. 2, 20–24 (Russian)

[45] Belov A. Ya., Kharitonov M. I., “Subexponential estimates in Shirshov's theorem on height”, Sb. Math., 203:4 (2012), 81–102 (Russian) | DOI

[46] Belov A. Ya., “On non-Spechtian varieties”, J. Math. Sci., 5:1 (1999), 47–66 (Russian)

[47] Belov A. Ya., Kharitonov M. I., “Subexponential estimates in the height theorem and estimates on numbers of periodic parts of small periods”, J. Math. Sci., 17:5 (2012), 21–54 (Russian)

[48] Chelnokov G. R., “On the lower estimate for $k+1$-nondecomposible permutations”, Model. Anal. Inform. Sist., 14:4 (2007), 53–56 (Russian)

[49] Gessel I. M., “Symmetric Functions and P-Recursiveness”, J. Combin. Theory Ser. A, 53 (1990), 257–285 | DOI

[50] Grishin A. V., “Examples of T-spaces and T-ideals over a field of characteristic 2 without the finite basis property”, Fundam. Prikl. Mat., 5:1 (1999), 101–118 (Russian)

[51] Kemer A. R., “Konechnaja baziruemost' tozhdestv associativnyh algebr”, Algebra i logika, 26:5 (1987), 597–641 (Russian)

[52] Knuth D. E., “Permutations, matrices, and generalized Young tableux”, Pacific journal of mathematics, 34:3 (1970), 709–727 | DOI

[53] Latyshev V. N., “On Regev's theorem on identities in a tensor product of PI-algebras”, Uspekhi Mat. Nauk., 27:4(166) (1972), 213–214 (Russian)

[54] Latyshev V. N., Nonmatrix varieties of associative algebras, MSU, M., 1977 (Russian)

[55] Schensted C., “Longest increasing and decreasing subsequences”, Canad. J. Math., 13 (1961), 179–191 | DOI

[56] Shchigolev V. V., “Examples of infinitely based T-ideals”, Fundam. Prikl. Mat., 5:1 (1999), 307–312 (Russian)

[57] Specht W., “Gesetze in Ringen, I”, Math. Z., 52 (1950), 557–589 | DOI

[58] Sapir M. V., Combinatorial algebra: syntax and semantics, Springer, 2014

[59] Amitsur S. A., Levitzki J., “Minimal identities for algebras”, Proc. Amer. Math. Soc., 1950, no. 2, 449–463 | DOI

[60] Li F., Tzameret I., Matrix dentities and proof complexity lower bounds, 2013

[61] Lopatin A. A., Shestakov I. P., “Associative nil-algebras over finite fields”, International Journal of Algebra and Computation, 23:8 (2013), 1881–1894 | DOI

[62] Bugaenko V. O., “Obobshhennaja teorema Van der Vardena”, Mat. Pros., Ser. 3, 2006, no. 10, 151–160 (Russian)

[63] Hinchin A. Ja., Tri zhemchuzhiny teorii chisel, Nauka, M., 1979 (Russian)

[64] Klyachko A. A., Special Course on Group Theory, 2009 (Russian)

[65] Zimin A. I., “Blocking sets of terms”, Mat. Sb. (N.S.), 119(161):3(11) (1982), 363–375 (Russian)

[66] Regev A., “Existence of polinomial identities in $A\otimes_F B$”, Bull. Amer. Math. Soc., 77:6 (1971), 1067–1069 | DOI

[67] Frid A. E., Introduction to the combinatorics of words, Lections, 2011 (Russian)

[68] Bergman G. M., “The Diamond Lemma for Ring Theory”, Advances in mathematics, 29 (1978), 178–218 | DOI

[69] Beidar K. I., Martindale W. S. III, Mikhalev A. V., “Rings with generalized identities”, Pure and applied mathematics, 1995

[70] Latyshev V. N., ENS Prikladnye problemy algebry, 2012 (Russian)

[71] Kaplansky I., “Rings with a polynomial identity”, Bull. Amer. Math. Soc., 54 (1948), 575–580 | DOI

[72] Thue A., “Über unendliche Zeichenreihen”, Norske Vid. Selsk. Skr., I. Mat. Nat. Kl., Christiana, 7 (1906), 1–22

[73] Morse M., “Recurrent Geodesics on a Surface of Negative Curvature”, Trans. Amer. Math. Soc., 22 (1921), 84–100 | DOI

[74] Berstel J., “Mots sans carré et morphismes itérés”, Discrete Math., 29 (1979), 235–244 | DOI

[75] Berstel J., Sur les mots sans carré définis par un morphisme, Springer-Verlag, 1979

[76] Crochemore M., “Sharp characterizations of square-free morphisms”, Theoret. Comput. Sci., 18 (1982), 221–226 | DOI

[77] wiki:en. Rauzy fractal

[78] wiki:ru. Minimal'naja forma avtomata

[79] wiki:en. State diagram