×

New approaches to plactic monoid via Gröbner-Shirshov bases. (English) Zbl 1309.16014

The semigroup algebra of the plactic monoid \(Pl(A)\) with finite generating set \(A=\{1,2,\ldots ,n\}\), over a field \(F\), is considered. Recall that the elements of \(Pl(A)\) are in a one-to-one correspondence with semistandard Young tableaux, [see A. Lascoux, B. Leclerc, J.-Y. Thibon in Algebraic combinatorics on words. Cambridge: Cambridge University Press (2002; Zbl 1001.68093)]. A presentation of \(Pl(A)\) (whence also of the algebra) based on the set of generators consisting of all rows (defined as the non-decreasing words) and with the set of defining relations, each involving a word of length \(2\) and a word of length at most \(2\) in these generators, is given. Then it is shown that this presentation yields a Gröbner-Shirshov basis of the algebra, with respect to the deg-lex order coming from a natural ordering of the set of all rows.
The second main result shows that a Gröbner-Shirshov basis is also obtained from another presentation of the monoid \(Pl(A)\). Namely, a presentation based on the set of generators consisting of all columns (strictly decreasing words) and with the defining relations again of the same type. This Gröbner-Shirshov basis is finite. The latter construction was independently obtained by A. J. Cain et al. [J. Algebra 423, 37-53 (2015; Zbl 1311.20055)], who also obtained further combinatorial properties of \(Pl(A)\), using this presentation. Notice also that it was observed by Ł. Kubat and the reviewer that the natural presentation of \(Pl(A)\) yields a finite Gröbner-Shirshov basis (with respect to the natural deg-lex order on \(A\)) exactly when \(n\leq 3\) [Algebra Colloq. 21, No. 4, 591-596 (2014; Zbl 1304.16026)].

MSC:

16S15 Finite generation, finite presentability, normal forms (diamond lemma, term-rewriting)
16S36 Ordinary and skew polynomial rings and semigroup rings
20M25 Semigroup rings, multiplicative semigroups of rings
13P10 Gröbner bases; other bases for ideals and modules (e.g., Janet and border bases)
20M05 Free semigroups, generators and relations, word problems
05E15 Combinatorial aspects of groups and algebras (MSC2010)
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Adams, William W.; Loustaunau, Philippe, An Introduction to Gröbner Bases, Grad. Stud. Math., vol. 3 (1994), American Mathematical Society (AMS) · Zbl 0803.13015
[2] Bergman, G. M., The diamond lemma for ring theory, Adv. Math., 29, 178-218 (1978) · Zbl 0326.16019
[3] Bokut, L. A., Insolvability of the word problem for Lie algebras, and subalgebras of finitely presented Lie algebras, Math. USSR, Izv., 36, 1173-1219 (1972)
[4] Bokut, L. A., Imbeddings into simple associative algebras, Algebra Logika, 15, 117-142 (1976)
[5] Bokut, L. A.; Chen, Yuqun, Gröbner-Shirshov bases: some new results, (Proceedings of the Second International Congress in Algebra and Combinatorics (2008), World Scientific), 35-56 · Zbl 1207.16023
[7] Bokut, L. A.; Chen, Yuqun; Chen, Yongshan, Composition-Diamond lemma for tensor product of free algebras, J. Algebra, 323, 2520-2537 (2010) · Zbl 1198.16022
[8] Bokut, L. A.; Chen, Yuqun; Chen, Yongshan, Groebner-Shirshov bases for Lie algebras over a commutative algebra, J. Algebra, 337, 82-102 (2011) · Zbl 1263.17003
[9] Bokut, L. A.; Chen, Yuqun; Chen, Weiping; Li, Jing, New approaches to plactic monoid via Gröbner-Shirshov bases · Zbl 1309.16014
[10] Bokut, L. A.; Chen, Yuqun; Deng, Xueming, Gröbner-Shirshov bases for Rota-Baxter algebras, Sib. Math. J., 51, 6, 978-988 (2010) · Zbl 1235.16021
[11] Bokut, L. A.; Chen, Yuqun; Li, Yu, Lyndon-Shirshov basis and anti-commutative algebras, J. Algebra, 378, 173-183 (2013) · Zbl 1297.17004
[12] Bokut, L. A.; Chen, Yuqun; Liu, Cihua, Gröbner-Shirshov bases for dialgebras, Internat. J. Algebra Comput., 20, 3, 391-415 (2010) · Zbl 1245.17001
[13] Bokut, L. A.; Chen, Yuqun; Mo, Qiuhui, Gröbner-Shirshov bases and embeddings of algebras, Internat. J. Algebra Comput., 20, 875-900 (2010) · Zbl 1236.16022
[14] Bokut, L. A.; Chen, Yuqun; Mo, Qiuhui, Gröbner-Shirshov bases for semirings, J. Algebra, 385, 47-63 (2013) · Zbl 1286.16038
[15] Bokut, L. A.; Chen, Yuqun; Shum, K. P., Some new results on Groebner-Shirshov bases, (Proceedings of International Conference on Algebra 2010, Advances in Algebraic Structures (2012)), 53-102 · Zbl 1264.16025
[16] Bokut, L. A.; Fong, Y.; Ke, W.-F.; Kolesnikov, P. S., Gröbner and Gröbner-Shirshov bases in algebra and conformal algebras, Fundam. Appl. Math., 6, 3, 669-706 (2000) · Zbl 0990.17007
[17] Bokut, L. A.; Kolesnikov, P. S., Gröbner-Shirshov bases: from their incipiency to the present, J. Math. Sci., 116, 1, 2894-2916 (2003) · Zbl 1069.16026
[18] Bokut, L. A.; Kolesnikov, P. S., Gröbner-Shirshov bases, conformal algebras and pseudo-algebras, J. Math. Sci., 131, 5, 5962-6003 (2005) · Zbl 1150.16020
[19] Bokut, L. A.; Kukin, G., Algorithmic and Combinatorial Algebra (1994), Kluwer Academic Publ.: Kluwer Academic Publ. Dordrecht · Zbl 0826.17002
[20] (Bokut, L. A.; Latyshev, V.; Shestakov, I.; Zelmanov, E., Selected works of A.I. Shirshov (2009), Birkhäuser: Birkhäuser Basel, Boston, Berlin), translated by M. Bremner, M. Kochetov
[21] Buchberger, B., An algorithmical criteria for the solvability of algebraic systems of equations, Aequationes Math., 4, 374-383 (1970)
[22] Buchberger, B.; Collins, G. E.; Loos, R.; Albrecht, R., Computer Algebra, Symbolic and Algebraic Computation, Computing Supplementum, vol. 4 (1982), Springer-Verlag: Springer-Verlag New York
[23] Buchberger, B.; Winkler, Franz, Gröbner Bases and Applications, London Math. Soc. Lecture Note Ser., vol. 251 (1998), Cambridge University Press: Cambridge University Press Cambridge · Zbl 0883.00014
[24] Cain, A. J.; Gray, R.; Malheiro, A., Finite Gröbner-Shirshov bases for Plactic algebras and biautomatic structures for Plactic monoids · Zbl 1311.20055
[25] Chen, Yongshan; Chen, Yuqun, Groebner-Shirshov bases for matabelian Lie algebras, J. Algebra, 358, 143-161 (2012) · Zbl 1305.17006
[26] Cox, David A.; Little, John; O’Shea, Donal, Ideals, Varieties and Algorithms: An Introduction to Computational Algebraic Geometry and Commutative Algebra, Undergrad. Texts Math. (1992), Springer-Verlag: Springer-Verlag New York · Zbl 0756.13017
[27] Eisenbud, David, Commutative Algebra with a View Toward Algebraic Geometry, Grad. Texts in Math., vol. 150 (1995), Springer-Verlag: Springer-Verlag Berlin and New York · Zbl 0819.13001
[28] Hironaka, H., Resolution of singularities of an algebraic variety over a field if characteristic zero, I, II, Ann. of Math., 79, 109-203 (1964), 205-326 · Zbl 0122.38603
[29] Kang, S.-J.; Lee, K.-H., Gröbner-Shirshov bases for irreducible \(s l_{n + 1}\)-modules, J. Algebra, 232, 1-20 (2000) · Zbl 1023.17001
[30] Knuth, D. E., Permutations, matrices, and generalized Young tableaux, Pacific J. Math., 34, 709-727 (1970) · Zbl 0199.31901
[31] Kubat, Lukasz; Okniński, Jan, Gröbner-Shirshov bases for plactic algebras, Algebra Colloq., 21, 591-596 (2014) · Zbl 1304.16026
[32] Lascoux, A.; Leclerc, B.; Thibon, J. Y., The plactic monoid, (Algebraic Combinatorics on Words (2002), Cambridge Univ. Press)
[33] Lascoux, A.; Schützenberger, M.-P., Le monoide plaxique, (De Luca, A., Non-Commutative Structures in Algebra and Geometric Combinatorics. Non-Commutative Structures in Algebra and Geometric Combinatorics, Quad. Ric. Sci., vol. 109 (1981), Consiglio Nazionale delle Ricerche), 129-156 · Zbl 0517.20036
[34] Mikhalev, A. A.; Zolotykh, A. A., Standard Gröbner-Shirshov bases of free algebras over rings, I. Free associative algebras, Internat. J. Algebra Comput., 8, 6, 689-726 (1998) · Zbl 0923.16024
[35] Schensted, C., Longest increasing and decreasing sub-sequences, Canad. J. Math., 13, 179-191 (1961) · Zbl 0097.25202
[36] Shirshov, A. I., Some algorithmic problem for Lie algebras, Sibirsk. Mat. Zh.. Sibirsk. Mat. Zh., SIGSAM Bull., 33, 2, 3-6 (1999), English translation in · Zbl 1097.17502
[37] Shirshov, A. I., Some algorithmic problem for \(ε\)-algebras, Sibirsk. Mat. Zh., 3, 132-137 (1962) · Zbl 0143.25602
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.