Abstract: 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 ∈ M. In this paper, we prove that for a sufficientlylarge direct power Hn of the Heisenberg group H, there existsa 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 memb ership 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 sufficiently 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.

Cite: Roman'kov V.A.
Undecidability of the submonoid membership problem for a sufficiently large finite direct power of the heisenberg group
Сибирские электронные математические известия (Siberian Electronic Mathematical Reports). 2023. V.20. N1. P.293-305. DOI: 10.33048/semi.2023.20.024 WOS Scopus РИНЦ

Dates:

Submitted:	Oct 5, 2022
Published print:	Mar 31, 2023
Published online:	Mar 31, 2023

Identifiers:

Web of science:	WOS:000959070400018
Scopus:	2-s2.0-85167888442
Elibrary:	54768296

Citing:

DB	Citing
Web of science	3
Scopus	4
Elibrary	2

Altmetrics: