Geodesic
Undecidability of the submonoid membership problem for a sufficiently large finite direct power of the Heisenberg group
Sibirskie èlektronnye matematičeskie izvestiâ, Tome 20 (2023) no. 1, pp. 293-305

Voir la notice de l'article provenant de la source Math-Net.Ru

The submonoid membership problem for a finitely generated group $G$ is the decision problem, where for a given finitely generated submonoid $M$ of $G$ and a group element $g$ it is asked whether $g \in M$. In this paper, we prove that for a sufficiently large direct power $\mathbb{H}^n$ of the Heisenberg group $\mathbb{H}$, there exists a finitely generated submonoid $M$ whose membership problem is algorithmically unsolvable. Thus, an answer is given to the question of M. Lohrey and B. Steinberg about the existence of a finitely generated nilpotent group with an unsolvable submonoid membership problem. It also answers the question of T. Colcombet, J. Ouaknine, P. Semukhin and J. Worrell about the existence of such a group in the class of direct powers of the Heisenberg group. This result implies the existence of a similar submonoid in any free nilpotent group $N_{k,c}$ of sufficiently large rank $k$ of the class $c\geq 2$. The proofs are based on the undecidability of Hilbert's 10th problem and interpretation of Diophantine equations in nilpotent groups.
Keywords: nilpotent group, Heisenberg group, direct product, submonoid membership problem, rational set, decidability, Hilbert's 10th problem, interpretability of Diophantine equations in groups. 
V. A. Roman'kov. Undecidability of the submonoid membership problem for a sufficiently large finite direct power of the Heisenberg group. Sibirskie èlektronnye matematičeskie izvestiâ, Tome 20 (2023) no. 1, pp. 293-305. http://geodesic.mathdoc.fr/item/SEMR_2023_20_1_a9/
@article{SEMR_2023_20_1_a9,
     author = {V. A. Roman'kov},
     title = {Undecidability of the submonoid membership problem for a sufficiently large finite direct power of the {Heisenberg} group},
     journal = {Sibirskie \`elektronnye matemati\v{c}eskie izvesti\^a},
     pages = {293--305},
     year = {2023},
     volume = {20},
     number = {1},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/SEMR_2023_20_1_a9/}
}
TY  - JOUR
AU  - V. A. Roman'kov
TI  - Undecidability of the submonoid membership problem for a sufficiently large finite direct power of the Heisenberg group
JO  - Sibirskie èlektronnye matematičeskie izvestiâ
PY  - 2023
SP  - 293
EP  - 305
VL  - 20
IS  - 1
UR  - http://geodesic.mathdoc.fr/item/SEMR_2023_20_1_a9/
LA  - en
ID  - SEMR_2023_20_1_a9
ER  - 
%0 Journal Article
%A V. A. Roman'kov
%T Undecidability of the submonoid membership problem for a sufficiently large finite direct power of the Heisenberg group
%J Sibirskie èlektronnye matematičeskie izvestiâ
%D 2023
%P 293-305
%V 20
%N 1
%U http://geodesic.mathdoc.fr/item/SEMR_2023_20_1_a9/
%G en
%F SEMR_2023_20_1_a9

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

[2] 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, Germany, 2019, 44 | MR | Zbl

[3] S.-Ki Ko, R. Niskanen, R. Niskanen, I. Potapov, “On the identity problem for the special linear group and the Heisenberg group”, 45th international colloquium on automata, languages, and programming. ICALP 2018, Proceedings (Prague, Czech Republic, July 9-13, 2018), LIPIcs - Leibniz Int. Proc. Inform., 107, eds. Chatzigiannakis Ioannis et al., 2018, 132 | MR | Zbl

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

[5] A.I. Maltsev, “On homomorphisms onto finite groups”, Transl., Ser. 2, Am. Math. Soc., 119 (1983), 67–79 | Zbl

[6] Yu.V. Matiyasevich, “Enumerable sets are diophantine”, Sov. Math., Dokl., 11:2 (1970), 354–357 | MR | Zbl

[7] Yu.V. Matiyasevich, “A Diophantine representation of enumerable predicates”, Izv. Akad. Nauk SSSR, Ser. Mat., 35 (1971), 3–30 | MR | Zbl

[8] Yu. Matiyasevich, “Some purely mathematical results inspired by mathematical logic”, Proc. Fifth Intern. Congr. Logic, Methodology and Philos. of Sci. (London, Ont., 1995), 1977, 121–127 | MR | Zbl

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

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

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

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

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

[14] V.A, Roman'kov, “Positive elements and sufficient conditions for solvability of the submonoid membership problem for nilpotent groups of class two”, Sib. Èlectron. Mat. Izv., 19:1 (2022), 387–403 | MR | Zbl

[15] V.A. Roman'kov, “Unsolvability of the submonoid membership problem for a free nilpotent group of class $l\geq 2$ of a sufficiently large rank”, Izvestiya Math. (to appear) | MR

[16] T. Skolem, Diophantische Gleichungen, Springer, Berlin, 1938 | Zbl