Реферат: The submonoid membership problem (SMP) for a finitely generated (f.g.) group $G$ is the question of the existence of an algorithm that, given an arbitrary set m_1, ... , m_k, g of elements of G, finds out whether g belongs to mon(m_1, ... , m_k). This work continues two our previous papers: [RomPos], in which sufficient conditions for the solvability of MP for a free nilpotent group of the class 2 with respect to a given submonoid M were presented, and [RomTwo] in which the affirmative answer is announced to the known question of M. Lohrey and B. Steinberg about the existence of a f.g. nilpotent group with an unsolvable SMP. The full proof of the claimed solution is contained in the article [RomIzv] accepted for publication. In this work, we propose another solution to Lohrey-Steinberg's problem. It also answers the question of T. Colcombet et al. [Col] about the existence of such a group in the class of direct powers of the Heisenberg group. Note that in \cite{Col} these authors prove that the somewhat more general the subsemigroup MP is solvable for the single Heisenberg group. Our proofs are based on the undecidability of Hilbert's 10th problem and interpretation of Diophantine equations in nilpotent groups. Theorem 1. For any Diophantine equation D(\zeta_1, \ldots , \zeta_l) = \upsilon, \upsilon \in Z$, there exists a direct power H^n of the Heisenberg group, a f.g. submonoid M = M(D) and an element g(\upsilon ) such that the equation is solvable in integers if and only if $g (\upsilon ) belongs to M. All the parameters are effectively determined. Theorem 2. For sufficiently large n the group H^n contains a f.g. submonoid M with an unsolvable MP. This implies the existence of a submonoid with an unsolvable MP in any free nilpotent group N_{k,c} of sufficiently large rank k of the class c > 1. Bibliography [RomPos] V.A. Roman'kov, Positive elements and sufficient conditions for solvability of the submonoid membership problem for nilpotent groups of class two, Siberian Electronic Mathematical Reports, 19:2 (2022), 387--403. [RomTwo] V.A. Roman'kov, Two problems for solvable and nilpotent groups, Algebra and Logic, 59:6 (2021), 483--492. [RomIzv] 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. (accepted for publication). [Col] T. Colcombet, J. Ouaknine, P. Semukhin, J. Worrell, On reachability problems for low dimensional matrix semigroups. In: 46th Intern. Coll. on Automata, Languages, and Programming (ICALP 2019), LIPIcs, 132, Dagstuhl, Germany, 2019, 44:1--44:15.

Библиографическая ссылка: Roman'kov V.A.
Undecidability of the submonoid membership problem for a sufficiently large finite direct power of the Heisenberg group
Международная конференция "МАЛЬЦЕВСКИЕ ЧТЕНИЯ" 14-18 Nov 2022