Тип публикации: статья из журнала
Год издания: 2023
Идентификатор DOI: 10.33048/semi.2023.20.024
Ключевые слова: nilpotent group, Heisenberg group, direct product, submonoid membership problem, rational set, decidability, Hilbert's 10th problem, interpretability of Diophantine equations in groups
Аннотация: 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 G M. In this paper, we prove that for a sufficiently large direct power Hn of the Heisenberg group 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 Nk,c of sufficient!у large rank k of the class c > 2. The proofs are based on the undecidability of Hilbert’s 10th problem and interpretation of Diophantine equations in nilpotent groups.
Журнал: Сибирские электронные математические известия
Выпуск журнала: Т. 20, № 1
Номера страниц: 293-305
ISSN журнала: 18133304
Место издания: Новосибирск
Издатель: Институт математики им. С.Л. Соболева СО РАН