Undecidability of the submonoid membership problem for a sufficiently large finite direct power of the Heisenberg group

V. A. Roman'kov

Sibirskie èlektronnye matematičeskie izvestiâ, Tome 20 (2023) no. 1, pp. 293-305

Résumé

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.

Détail

Keywords: nilpotent group, Heisenberg group, direct product, submonoid membership problem, rational set, decidability, Hilbert's 10th problem, interpretability of Diophantine equations in groups.