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. 
@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},
     publisher = {mathdoc},
     volume = {20},
     number = {1},
     year = {2023},
     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
PB  - mathdoc
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
%I mathdoc
%U http://geodesic.mathdoc.fr/item/SEMR_2023_20_1_a9/
%G en
%F SEMR_2023_20_1_a9
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/

[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