Undecidability of the submonoid membership problem for free nilpotent group of class $l\geqslant 2$ of sufficiently large rank

V. A. Roman'kov

Izvestiya. Mathematics , Tome 87 (2023) no. 4, pp. 798-816.

Résumé

An answer is given to the question of M. Lohrey and B. Steinberg on decidability of the submonoid membership problem for a finitely generated nilpotent group. Namely, a finitely generated submonoid of a free nilpotent group of class $2$ of sufficiently large rank $r$ is constructed, for which the membership problem is algorithmically undecidable. This implies the existence of a submonoid with similar property in any free nilpotent group of class $l \geqslant 2$ of rank $r$. The proof is based on the undecidability of Hilbert's tenth problem.

Détail

Keywords: submonoid membership problem, nilpotent group, Hilbert's tenth problem, interpretability of equations in groups.

Bibliographie

[1] A. Myasnikov, V. Shpilrain, and A. Ushakov, Group-based cryptography, Adv. Courses Math. CRM Barcelona, Birkhäuser Verlag, Basel, 2008 | DOI | MR | Zbl

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

[3] V. A. Roman'kov, Algebraic cryptography, Izd-vo Omsk. Univ., Omsk, 2020 (Russian)

[4] S. I. Adian and V. G. Durnev, “Decision problems for groups and semigroups”, Uspekhi Mat. Nauk, 55:2(332) (2000), 3–94 ; English transl. Russian Math. Surveys, 55:2 (2000), 207–296 | DOI | MR | Zbl | DOI

[5] G. A. Noskov, V. N. Remeslennikov, and V. A. Roman'kov, “Infinite groups”, Itogi Nauki i Tekhniki. Ser. Algebra. Topol. Geom., 17, VINITI, Moscow, 1979, 65–157 ; English transl. J. Soviet Math., 18:5 (1982), 669–735 | MR | Zbl | DOI

[6] V. N. Remeslennikov and V. A. Roman'kov, “Model-theoretic and algorithmic questions in group theory”, Itogi Nauki i Tekhniki. Ser. Algebra. Topol. Geom., 21, VINITI, Moscow, 1983, 3–79 ; English transl. J. Soviet Math., 31:3 (1985), 2887–2939 | MR | Zbl | DOI

[7] V. A. Roman'kov, “On algorithmic problems of group theory”, Vestn. Omsk. Univ., 2017, no. 2, 18–27

[8] 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., 71, North-Holland, Amsterdam, 1973, 507–523 | DOI | MR | Zbl

[9] 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, 119, Amer. Math. Soc., Providence, RI, 1983, 67–79 | Zbl | DOI

[10] 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 | DOI | MR | Zbl

[11] M. Lohrey, “The rational subset membership problem for groups: a survey”, Groups St. Andrews 2013, London Math. Soc. Lecture Note Ser., 422, Cambridge Univ. Press, Cambridge, 2015, 368–389 | DOI | MR | Zbl

[12] 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, 235–242 (in Russian)

[13] V. A. Roman'kov, Rational subsets in groups, Izd-vo Omsk gos. univ., Omsk, 2014

[14] 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., 25, Amer. Math. Soc., Providence, RI, 1996, 27–51 | DOI | MR | Zbl

[15] V. A. Roman'kov, “Polycyclic, metabelian or soluble of type $(\mathrm{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

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

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

[18] M. Yu. Nedbaj, “On the occurrence problem in rational subsets of finitely generated Abelian groups”, Vestn. Omsk. Univ., 1999, no. 3, 37–41 | Zbl

[19] Z. Grunschlag, Algorithms in geometric group theory, PhD thesis, Univ. of California, Berkeley, 1999 | MR

[20] 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

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

[22] 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 | MR | Zbl | DOI

[23] 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., 9, Reidel, Dordrecht, 1977, 121–127 | DOI | MR | Zbl

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

[25] J. P. Jones, “Undecidable Diophantine equations”, Bull. Amer. Math. Soc. (N.S.), 3:2 (1980), 859–862 | DOI | MR | Zbl

[26] T. Skolem, Diophantische Gleichungen, Ergeb. Math. Grenzgeb., 5, Springer, Berlin, 1938 | Zbl

[27] 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 | DOI | MR | Zbl | DOI

[28] 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 | DOI | MR | Zbl