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

The \textit{submonoid membership problem} for a group \(G\) is the decision problem with input an \((n+1)\)-tuple of elements \(g_0,g_1,\dots,g_n\), and output whether \(g_0\) belongs to the submonoid of \(G\) generated by \(g_1,\dots,g_n\).\N\NThis paper focusses on the case of nilpotent groups \(G\), which we assume finitely generated so there is no ambiguity as to how the \(g_i\) are represented as input. Note that a particular case (that of instances of the form \((g_0,g_1,g_1^{-1},\dots,g_n,g_n^{-1})\)) of the submonoid membership problem is the \textit{subgroup membership problem}, aka \textit{generalized word problem}, which is decidable in all finitely generated nilpotent groups, by a classical result of \textit{A. I. Mal'tsev} [Transl., Ser. 2, Am. Math. Soc. 119, 67--79 (1983; Zbl 0511.20026); translation from Uch. Zap. Ivanov. Gos. Pedagog Inst. 18, 49--60 (1958)].\N\NA prominent example of nilpotent group is the \textit{Heisenberg group} \(H\) of upper-triangular \(3\times3\) integer matrices. By \textit{T. Colcombet} et al. [LIPIcs -- Leibniz Int. Proc. Inform. 132, Article 44, 15 p. (2019; Zbl 07561537)] the submonoid membership problem is solvable in \(H\). On the contrary, the main result of the present paper is that, for sufficiently large \(n\), the submonoid membership problem is unsolvable in the direct power \(H^n\).\N\NNote that \(H\) is the free nilpotent group of class \(2\) on \(2\) generators. The above extends a result by the same author [Izv. Math. 87, No. 4, 798--816 (2023; Zbl 1535.20164); translation from Izv. Ross. Akad. Nauk, Ser. Mat. 87, No. 4, 166--185 (2023)] that the submonoid membership problem is undecidable in the free nilpotent group of class \(2\) on a sufficiently large number of generators.\N\NThe method of proof is to interpret Diophantine equations over the integers into a power of the Heisenberg group and to reduce in this manner to undecidability of Hilbert's 10th problem, proven by \textit{Yu. V. Matiyasevich} [Sov. Math., Dokl. 11, 354--358 (1970; Zbl 0212.33401); translation from Dokl. Akad. Nauk SSSR 191, 279--282 (1970)].