Roman’kov, V. A. Undecidability of the submonoid membership problem for free nilpotent group of class \(l\geqslant 2\) of sufficiently large rank. (English. Russian original) Zbl 1535.20164 Izv. Math. 87, No. 4, 798-816 (2023); translation from Izv. Ross. Akad. Nauk, Ser. Mat. 87, No. 4, 166-185 (2023). The submonoid membership for the abelian group \(\mathbb{Z}^n\) has a nice description from integer linear programming. Given an \(m\times n\) matrix \(A\) over \(\mathbb{Z}\) and a vector \(b\in \mathbb{Z}^n\), determine whether there exists \(x\in\mathbb{N}^m\) such that \(xA=b\). The submonoid is the \(\mathbb{N}\)-span of the rows of \(A\). The problem of finding such an \(x\) is NP-complete. The submonoid membership problem for arbitrary groups is a non-commutative analog of integer linear programming. Problem 24 of M. Lohrey [Lond. Math. Soc. Lect. Note Ser. 422, 368–389 (2015; Zbl 1346.20043)] asks whether there exists a finitely generated nilpotent group with an undecidable submonoid membership problem. The answer is affirmative and the paper under review gives a proof of this fact.The main result asserts the existence of a finitely generated submonoid of a free nilpotent group of class \(2\) and sufficiently large rank \(r\) such that the membership problem for this submonoid is undecidable. The proof is based on the result that Hilbert’s tenth problem has a negative answer [Yu. V. Matiyasevich, Desyataya problema Gil’berta (Russian). Moskva: Nauka (1993; Zbl 0790.03009)]: there is no algorithm that, given a Diophantine equation, can decide if the equation has a solution in the integers. As a corollary, the author shows that the assumption of class \(2\) can be relaxed to class \(l\geqslant 2\). The submonoid in \(N_{r,l}\), the \(r\)-generated class \(l\) free nilpotent group, is obtained from the full pre-image of the submonoid from \(N_{r,2}\) under the projection \(N_{r,l} \to N_{r, 2}\). Reviewer: Joshua Maglione (Magdeburg) Cited in 1 ReviewCited in 2 Documents MSC: 20F10 Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) 20F18 Nilpotent groups 20F16 Solvable groups, supersolvable groups 20F05 Generators, relations, and presentations of groups 03D35 Undecidability and degrees of sets of sentences Keywords:submonoid membership problem; nilpotent group; Hilbert’s tenth problem; interpretability of equations in groups Citations:Zbl 1346.20043; Zbl 0790.03009 × Cite Format Result Cite Review PDF Full Text: DOI MNR References: [1] A. Myasnikov, V. Shpilrain, and A. Ushakov, Group-based cryptography, Adv. Courses Math. CRM Barcelona, Birkhäuser Verlag, Basel 2008. · Zbl 1248.94004 · doi:10.1007/978-3-7643-8827-0 [2] A. Myasnikov, V. Shpilrain, and A. Ushakov, Non-commutative cryptography and complexity of group-theoretic problems, Math. Surveys Monogr., vol. 177, Amer. Math. Soc., Providence, RI 2011. · Zbl 1248.94006 · doi:10.1090/surv/177 [3] V. A. Roman’kov, Algebraic cryptography, Izd-vo Omsk. Univ., Omsk 2020. (Russian) · Zbl 1481.94121 [4] S. I. Adian and V. G. Durnev, “Decision problems for groups and semigroups”, Uspekhi Mat. Nauk 55:2(332) (2000), 3-94; · Zbl 0958.20029 · doi:10.1070/RM2000v055n02ABEH000267 [5] English transl., Russian Math. Surveys 55:2 (2000), 207-296. · doi:10.1070/RM2000v055n02ABEH000267 [6] G. A. Noskov, V. N. Remeslennikov, and V. A. Roman’kov, “Infinite groups”, Itogi Nauki i Tekhniki. Ser. Algebra. Topol. Geom., vol. 17, VINITI, Moscow 1979, pp. 65-157; English transl., J. Soviet Math. 18:5 (1982), 669-735. · Zbl 0479.20001 · doi:10.1007/BF01091962 [7] V. N. Remeslennikov and V. A. Roman’kov, “Model-theoretic and algorithmic questions in group theory”, Itogi Nauki i Tekhniki. Ser. Algebra. Topol. Geom., vol. 21, VINITI, Moscow 1983, pp. 3-79; English transl., J. Soviet Math. 31:3 (1985), 2887-2939. · Zbl 0573.20031 · doi:10.1007/BF02106805 [8] V. A. Roman’kov, “On algorithmic problems of group theory”, Vestn. Omsk. Univ., 2017, no. 2, 18-27. [9] Ch. F. Miller, III, “Decision problems in algebraic classes of groups (a survey)”, Word problems: decision problems and the Burnside problem in group theory, Dedicated to H. Neumann (Univ. California, Irvine, CA 1969), Stud. Logic Found. Math., vol. 71, North-Holland, Amsterdam 1973, pp. 507-523. · Zbl 0288.20052 · doi:10.1016/S0049-237X(08)71917-7 [10] A. I. Mal’cev, “On homomorphisms onto finite groups”, Uch. zap. Ivan. Ped. Univ. 18:5 (1958), 49-60; English transl., Amer. Math. Soc. Transl. Ser. 2, vol. 119, Amer. Math. Soc., Providence, RI 1983, pp. 67-79. · Zbl 0511.20026 · doi:10.1090/trans2/119/08 [11] F. Bassino, I. Kapovich, M. Lohrey, A. Miasnikov, C. Nicaud, A. Nikolaev, I. Rivin, V. Shpilrain, A. Ushakov, and P. Weil, Complexity and randomness in group theory. GAGTA book 1, De Gruyter, Berlin 2020. · Zbl 1515.20003 · doi:10.1515/9783110667028 [12] M. Lohrey, “The rational subset membership problem for groups: a survey”, Groups St. Andrews 2013, London Math. Soc. Lecture Note Ser., vol. 422, Cambridge Univ. Press, Cambridge 2015, pp. 368-389. · Zbl 1346.20043 · doi:10.1017/CBO9781316227343.024 [13] V. A. Roman’kov, “On the occurence problem for rational subsets of a group”, Combinartorial and coputational methods in mechanics, Sb. Nauchn. Tr., OmskGU, Omsk 1999, pp. 235-242. (in Russian) [14] V. A. Roman’kov, Rational subsets in groups, Izd-vo Omsk gos. univ., Omsk 2014. [15] R. H. Gilman, “Formal languages and infinite groups”, Geometric and computational perspectives on infinite groups (Minneapolis, MN, New Brunswick, NJ 1994), DIMACS Ser. Discrete Math. Theoret. Comput. Sci., vol. 25, Amer. Math. Soc., Providence, RI 1996, pp. 27-51. · Zbl 0851.20030 · doi:10.1090/dimacs/025/03 [16] V. A. Roman’kov, “Polycyclic, metabelian or soluble of type (FP)∞ groups with Boolean algebra of rational sets and biautomatic soluble groups are virtually abelian”, Glasg. Math. J. 60:1 (2018), 209-218. · Zbl 1427.20041 · doi:10.1017/S0017089516000677 [17] M. Benois, “Parties rationnelles du groupe libre”, C. R. Acad. Sci. Paris Sér. A 269 (1969), 1188-1190. · Zbl 0214.03903 [18] S. Eilenberg and M. P. Schützenberger, “Rational sets in commutative monoids”, J. Algebra 13:2 (1969), 173-191. · Zbl 0206.02703 · doi:10.1016/0021-8693(69)90070-2 [19] M. Yu. Nedbaj, “On the occurrence problem in rational subsets of finitely generated Abelian groups”, Vestn. Omsk. Univ., 1999, no. 3, 37-41. · Zbl 0943.20028 [20] Z. Grunschlag, Algorithms in geometric group theory, PhD thesis, Univ. of California, Berkeley 1999. [21] M. Yu. Nedbaj, “The occurrence problem in a rational subset of the free product of groups”, Vestn. Omsk. Univ., 2000, no. 2, 17-18. · Zbl 1027.20017 [22] M. Lohrey and B. Steinberg, “Tilings and submonoids of metabelian groups”, Theory Comput. Syst. 48:2 (2011), 411-427. · Zbl 1229.20025 · doi:10.1007/s00224-010-9264-9 [23] Yu. V. Matiyasevich, “Diophantine representation of enumerable predicates”, Izv. Akad. Nauk SSSR Ser. Mat. 35:1 (1971), 3-30; English transl., Math. USSR-Izv. 5:1 (1971), 1-28. · Zbl 0252.02047 · doi:10.1070/IM1971v005n01ABEH001004 [24] Yu. V. Matijasevič, “Some purely mathematical results inspired by mathematical logic”, Logic, foundations of mathematics and computability theory, Proc. 5th internat. congr. logic, methodology and philos. of sci., Part I (Univ. Western Ontario, London, ON 1975), Univ. Western Ontario Ser. Philos. Sci., vol. 9, Reidel, Dordrecht 1977, pp. 121-127. · Zbl 0377.02001 · doi:10.1007/978-94-010-1138-9_7 [25] Y. Matijasevič and J. Robinson, “Reduction of an arbitrary Diophantine equation to one in 13 unknowns”, Acta Arith. 27 (1975), 521-553. · Zbl 0279.10019 · doi:10.4064/aa-27-1-521-553 [26] J. P. Jones, “Undecidable Diophantine equations”, Bull. Amer. Math. Soc. (N.S.) 3:2 (1980), 859-862. · Zbl 0442.03028 · doi:10.1090/S0273-0979-1980-14832-6 [27] T. Skolem, Diophantische Gleichungen, Ergeb. Math. Grenzgeb., vol. 5, Springer, Berlin 1938. · JFM 64.0112.02 [28] V. A. Roman’kov, “Two problems for solvable and nilpotent groups”, Algebra i Logika 59:6 (2020), 719-733; English transl., Algebra and Logic 59:6 (2021), 483-492. · Zbl 1515.20164 · doi:10.1007/s10469-021-09617-z [29] V. A. Roman’kov, “Positive elements and sufficient conditions for solvability of the submonoid membership problem for nilpotent groups of class two”, Sib.Èlektron. Mat. Izv. 19:1 (2022), 387-403. · Zbl 1547.20116 · doi:10.33048/semi.2022.19.034 [30] Vitalii A. Roman’kov Sobolev Institute of Mathematics of Siberian Branch of Russian Academy of Science (Omsk Branch) [31] E-mail: romankov48@mail.ru 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.