Positive elements and sufficient conditions for solvability of the submonoid membership problem for nilpotent groups of class two

V. A. Roman'kov

Sibirskie èlektronnye matematičeskie izvestiâ, Tome 19 (2022) no. 1, pp. 387-403.

Résumé

Over the past 20–25 years, a fruitful connection has emerged between group theory and computer science. Significant attention began to be paid to the algorithmic problems of group theory in view of their open applications. In addition to the traditional questions of solvability, the questions of complexity and effective solvability began to be studied. This paper provides a brief overview of this area. Attention is drawn to algorithmic problems related to rational subsets of groups which are a natural generalization of regular sets. The submonoid membership problem for free nilpotent groups, which has attracted the attention of a number of researchers in recent years, is considered. It is shown how the apparatus of subsets of positive elements makes it possible to obtain sufficient conditions for the solvability of this problem in the case of nilpotency class two. Note that the author announced a negative solution to this problem for a free nilpotent group of nilpotency class at least two of sufficiently large rank (the full proof is in print). This gives an answer to the well-known question of Lohrey-Steinberg about the existence of a finitely generated nilpotent group with an unsolvable submonoid membership problem. In view of this result, finding sufficient conditions for the solvability of this problem for nilpotent groups of class two is an urgent problem.

Détail

Keywords: nilpotent group, submonoid membership problem, rational set, positive elements, solvability.

Bibliographie

[1] S.I. Adian, “Algorithmic unsolvability of problems of recognition of certain properties of groups”, Dokl. Akad. Nauk SSSR, 103:4 (1955), 533–535 | MR | Zbl

[2] S.I. Adian, “Unsolvability of some algorithmic problems in the theory of groups”, Tr. Mosk. Mat. Obshch., 6, 1957, 231–298 | MR | Zbl

[3] S.I. Adian, V.G. Durnev, “Decision problems for groups and semigroups”, Russ. Math. Surv., 55:2 (2000), 207–296 | DOI | MR | Zbl

[4] V. Diekert, O. Kharlampovich, M. Lohrey, A. Myasnikov, “Algorithmic problems in group theory (Dagstuhl Seminar 19131)”, Dagstuhl Reports, 9:3 (2019), 83–110 | MR

[5] F. Bassino, I. Kapovich, M. Lohrey, A. Miasnikov, C. Nicaud, A. Nikolaev, I. Rivin, Complexity and randomness in group theory, GAGTA, 1, eds. A. Ushakov, P. Weil,, de Gruyter, Berlin, 2020 | MR | Zbl

[6] G. Baumslag, F.B. Cannonito, D.J.S. Robinson, “The algorithmic theory of finitely generated metabelian groups”, Trans. Am. Math. Soc., 344:2 (1994), 629–648 | DOI | MR | Zbl

[7] G. Baumslag, F.B. Cannonito, D.J.S. Robinson, D. Segal, “The algorithmic theory of polycyclic-by-finite groups”, J. Algebra, 141:1 (1991), 118–149 | DOI | MR | Zbl

[8] G. Baumslag, D. Gildenhuys, R. Strebel, “Algorithmically insoluble problems about finitely presented solvable groups, Lie and associative algebras. I”, J. Pure Appl. Algebra, 39 (1986), 53–94 | DOI | MR | Zbl

[9] G. Baumslag, D. Gildenhuys, R. Strebel, “Algorithmically insoluble problems about finitely presented solvable groups, Lie and associative algebras. II”, J. Algebra, 97 (1985), 278–285 | DOI | MR | Zbl

[10] M. Benois, “Parties rationnelles du groupe libre”, C. R. Acad. Sci. Paris, Sér. A, 269 (1969), 1188–1190 | MR | Zbl

[11] S.P. Boyd, L. Vandenberghe, Convex optimization, Cambridge University Press, Cambridge, 2004 | MR | Zbl

[12] T. Colcombet, J. Ouaknine, P. Semukhin, J. Worrell, “On reachability problems for low dimensional matrix semigroups”, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019), LIPIcs, 132, eds. C. Baier et al., Schloss Dagstuhl – Leibniz-Zentrum f$\ddot{\rm u}$r Informatik, Dagstuhl, 2019, 44:1–44:15 | MR

[13] S. Eilenberg, M.P. Schützenberger, “Rational sets in commutative monoids”, J. Algebra, 13 (1969), 173–191 | DOI | MR | Zbl

[14] E. Formanek, “Conjugacy separability in polycyclic groups”, J. Algebra, 42:1 (1976), 1–10 | DOI | MR | Zbl

[15] R.H. Gilman, “Formal languages and infinite groups”, Geometric and computational perspectives on infinite groups, Proceedings of a joint DIMACS/Geometry Center workshop (January 3–14, 1994, the University of Minnesota, Minneapolis, MN, USA and March 17-20, 1994, Princeton, NJ, USA), DIMACS, Ser. Discrete Math. Theor. Comput. Sci., 25, eds. Baumslag G. et al., AMS, Providence, 1996, 27–51 | DOI | MR | Zbl

[16] F. Grunewald, D. Segal, “The solubility of certain decision problems in arithmetic and algebra”, Bull. Am. Math. Soc., New Ser., 1:6 (1979), 915–918 | DOI | MR | Zbl

[17] F. Grunewald, D. Segal, “Some general algorithms. I: Arithmetic groups”, Ann. Math. (2), 112:3 (1980), 531–583 ; “Some general algorithms. II: Nilpotent groups”, 585–617 | DOI | MR | Zbl | Zbl

[18] Z. Grunschlag, Algorithms in geometric group theory, PhD thesis, University of California, Berkley, 1999 | MR

[19] P. Hall, Nilpotent groups, Notes of lectures given at the Canadian Mathematical Congress, summer seminar (University of Alberta, Edmonton, 12-30 August 1957), Queen Mary College (University of London), London, 1969 | MR | Zbl

[20] M. Hall jun., The theory of groups, The Macmillan Company, New York, 1959 | MR | Zbl

[21] O.G. Harlampovich, “A finitely presented solvable group with undecidable word problem”, Math. USSR-Izvestiya, 19:1 (1982), 151–169 | DOI | MR

[22] R. Lipton, Y. Zalstein, “Word problems solvable in logspace”, J. Assoc. Comput. Math., 24 (1977), 522–526 | DOI | MR | Zbl

[23] M. Lohrey, “The rational subset membership problem for groups: a survey”, Groups St Andrews 2013, Selected papers of the conference, London Mathematical Society Lecture Note Series, 422, eds. Campbell C.M. et al., Cambridge University Press, 2015, 368–389 | MR | Zbl

[24] M. Lohrey, B. Steinberg, “Tilings and submonoids of metabelian groups”, Theory Comput. Syst., 48:2 (2011), 411–427 | DOI | MR | Zbl

[25] J. Macdonald, A. Myasnikov, A. Nikolaev, S. Vassileva, Logspace and compressed-word computations in nilpotent groups, arXiv: 1503.03888v3 | MR

[26] J. Macdonald, A. Miasnikov, D. Ovchinnikov, “Low-complexity computations for nilpotent subgroup problems”, Int. J. Algebra Comput., 29:4 (2019), 639–661 | DOI | MR | Zbl

[27] Y. Matijasevic, J. Robinson, “Reduction of an arbitrary diophantine equation to one in 13 unknowns”, Acta Arith., 27 (1975), 521–553 | DOI | MR | Zbl

[28] Ch.F. III Miller, “Decision problems in algebraic classes of groups (a survey)”, Studies Logic Foundations Math., 71 (1973), 507–523 | DOI | MR | Zbl

[29] A. Myasnikov, V. Roman'kov, “On rationality of verbal subsets in a group”, Theory Comput. Syst., 52:4 (2013), 587–598 | DOI | MR | Zbl

[30] A. Myasnikov, V. Shpilrain, A. Ushakov, Group-based cryptography, Advanced Courses in Mathematics, CRM, Barcelona; Birkhäuser, 2008 | MR | Zbl

[31] A. Myasnikov, V. Shpilrain, A. Ushakov, Non-commutative cryptography and complexity of group-theoretic problems, Mathematical Surveys and Monographs, 177, Amer. Math. Soc., Providence, 2011 | DOI | MR | Zbl

[32] M.Yu. Nedbay, “The rational subset membership problem for finitely generated abelian groups”, Vestnik Omskogo universiteta, 1999:3 (1999), 37–41

[33] M.Yu. Nedbay, “The rational subset membership problem for free products of groups”, Vestnik Omskogo universiteta, 2000:2 (2000), 17–18

[34] M. Newman, Integral matrices, Pure and Applied Mathematics, 45, Academic Press, New York-London, 1972 | MR | Zbl

[35] G.A. Noskov, “Conjugacy problem in metabelian groups”, Math. Notes, 31:4 (1982), 252–258 | DOI | MR | Zbl

[36] G.A. Noskov, V.N. Remeslennikov, V.A. Roman'kov, “Infinite groups”, J. Sov. Math., 18:5 (1982), 669–735 | DOI | Zbl

[37] P.S. Novikov, “On the algorithmic unsolbability of the word problem”, Dokl. Akad. Nauk SSSR, 85:4 (1952), 709–712 | MR | Zbl

[38] P.S. Novikov, “On the algorithmic unsolvability of the word problem in group theory”, Tr. Mat. Inst. Steklova, 44, Acad. Sci. USSR, M., 1955 | MR | Zbl

[39] M.O. Rabin, “Recursive unsolvability of group theoretic problems”, Ann. Math. (2), 67 (1958), 172–194 | DOI | MR | Zbl

[40] V.N. Remeslennikov, “Conjugacy in polycyclic groups”, Algebra Logic, 8 (1971), 404–411 | DOI | MR | Zbl

[41] V.N. Remeslennikov, V.A. Roman'kov, “Model-theoretic and algorithmic questions in group theory”, J. Sov. Math., 31:3 (1985), 2887–2939 | DOI | MR | Zbl

[42] N.S. Romanovskii, “Some algorithmic problems for solvable groups”, Algebra Logika, 13:1 (1974), 26–34 | DOI | MR | Zbl

[43] N.S. Romanovskii, “The occurrence problem for extensions of abelian groups by nilpotent groups”, Sib. Math. J., 21 (1980), 273–276 | DOI | MR | Zbl

[44] V.A. Roman'kov, “Automorphisms of groups”, Acta Appl. Math., 29:3 (1992), 241–280 | DOI | MR | Zbl

[45] V.A. Roman'kov, “On the occurence problem for rational subsets of a group”, Combinatorial and computing methods in mathematics, Omsk State University, Omsk, 1999, 235–242

[46] V.A. Roman'kov, Rational subsets in groups, Omsk State Univrersity, Omsk, 2014

[47] V.A. Roman'kov, “On algorithmic problems in group theory”, Vestnik Omskogo universiteta, 2017:2(84) (2017), 18–27

[48] V.A. Roman'kov, Essays in algebra and cryptology. Solvable groups, Omsk State University, Omsk, 2017

[49] V.A. Roman'kov, “Polycyclic, metabelian, or soluble of type (FP)$_\infty$ groups with Boolean algebra of rational sets and biautomatic soluble groups are virtually abelian”, Glasg. Math. J., 60:1 (2018), 209–218 | DOI | MR | Zbl

[50] V.A. Roman'kov, Algebraic cryptology, OmSU, Omsk, 2020

[51] V.A. Roman'kov, “Two problems for solvable and nilpotent groups”, Algebra Logic, 59:6 (2021), 483–492 | DOI | MR | Zbl

[52] V.A. Roman'kov, “Algorithmic theory of solvable groups”, Prikl. Diskr. Mat., 52 (2021), 16–64 | MR | Zbl

[53] R.A. Sarkisjan, “Algorithmic questions for linear algebraic groups, I”, Math. USSR, Sb., 41:2 (1982), 149–189 | DOI | MR | Zbl

[54] R.A. Sarkisjan, “Algorithmic questions for linear algebraic groups, II”, Math. USSR, Sb., 41:3 (1982), 329–359 | DOI | MR | Zbl

[55] D. Segal, “Decidable properties of polycyclic groups”, Proc. Lond. Math. Soc., III. Ser., 61:3 (1990), 497–528 | DOI | MR | Zbl

[56] E.I. Timoshenko, “Algorithmic problems for metabelian groups”, Algebra and Logic, 12:2 (1973), 132–137 | DOI | MR

[57] O.A. Yurak, “On the simultaneous reduction of elements of abelian groups to positive form”, Vestnik Omskogo universiteta, 2006:3 (2006), 18–19

[58] O.A. Yurak, “On the simultaneous reduction of elements of abelian groups to positive form, II”, Vestnik Omskogo universiteta, 2006:4 (2006), 7–8

[59] O.A. Yurak, “Positive elements of the Heisenberg group”, Vestnik Omskogo universiteta, 2008:2 (2008), 16–19