\documentclass[10pt]{amsart}
\usepackage[cp1251]{inputenc}
\usepackage[english,russian]{babel}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{amsfonts}
\usepackage{graphicx}
\usepackage{longtable}

\def\udcs{512.54,\,510.53} 
\def\mscs{20F10} 
\setcounter{page}{144}

\newtheorem{lemma}{Lemma}
\newtheorem{theorem}{Theorem}
\newtheorem{definition}{Definition}
\newtheorem{corollary}{Corollary}
\newtheorem{proposition}{Proposition}
\newtheorem{remark}{Remark}

\def\logo{{\bf\huge S\raisebox{0.2ex}{\hspace{0.55ex}\raisebox{0.05ex}e\hspace{-1.65ex}$\bigcirc$}MR}}

\def\semrtop
     {
  \vbox{
     \noindent\logo
     \hspace{80mm}\raisebox{1ex}{ISSN 1813-3304 }

     \vspace{5mm}

     \begin{center}
     {\huge СИБИРСКИЕ \ ЭЛЕКТРОННЫЕ} \\[2mm]
     {\huge МАТЕМАТИЧЕСКИЕ ИЗВЕСТИЯ} \\[2mm]
     {\large Siberian Electronic Mathematical Reports} \\[1mm]
     {\LARGE\tt{http://semr.math.nsc.ru}}\\[0.5mm]
     {\small ФГАОУ ВО "Сибирский федеральный университет", СФУ и Институт математики им. С.Л.Соболева СО РАН, Омский филиал}\\[-1mm]
     {\small Federal State Autonomous Educational Institution of Higher Education "Siberian Federal University" and Sobolev Institute of Mathematics SB RAS, Omsk Branch}
     \end{center}
     \vspace{-3mm}
     \noindent
     \begin{tabular}{c}
     \hphantom{aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa} \\
     \hline\hline
     \end{tabular}

     \vspace{1mm}
     {\flushleft\it Том 19, стр. 144--144 (2022) \hspace{65mm}{\rm\small УДК \udcs}}
     \newline
     	{\rm\small DOI~10.33048/semi.2022.19.xxx}\hphantom{aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa}{\rm\small MSC\ \ \mscs }
  }%\vbox
}

\begin{document}



\renewcommand{\refname}{References}


\thispagestyle{empty}

\title[Undecidability  of the submonoid membership problem]{Undecidability of the submonoid membership problem for a  sufficiently large finite direct power of the Heisenberg group}
\author{{V.A. ROMAN'KOV}}%
\address{Vitalii Anatolievich Roman'kov  
\newline\hphantom{iii} Federal State Autonomous Educational Institution of Higher Education "Siberian Federal University",
\newline\hphantom{iii} 79/10, Svobodny pr., 
\newline\hphantom{iii} Krasnoyarsk, 660041, Russia;
\newline\hphantom{iii}
Sobolev Institute of Mathematics, Omsk Branch,
\newline\hphantom{iii} 13, Pevtsov str., 
\newline\hphantom{iii} Omsk, 644099, Russia}%
\email{romankov48@mail.ru}%

\thanks{\sc Roman'kov, V.A.,
Undecidability of the submonoid membership problem for a  sufficiently large finite direct power of the Heisenberg group}
\thanks{\copyright \ 2022 Roman'kov V.A}
\thanks{\rm The research was supported with a grant from the Russian Science Foundation\,  (project No. 19-71-10017)}
\thanks{\it Received on ?, ??, 2022, published on ? ?? 2022}%


\semrtop \vspace{1cm}
\maketitle
 
%{\small
\begin{quote}
\noindent
{\sc 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 \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. 


\noindent{\bf Keywords:} nilpotent group, Heisenberg group, direct product, submonoid membership problem, rational set,  decidability, Hilbert's 10th problem, interpretability of Diophantine equations in groups.
 \end{quote}
 
 \section{Introduction}
\label{sec:1}
 
The submonoid membership problem for finitely generated nilpotent groups, which has attracted the attention of a number of researchers in recent years, is considered.  Recall that this is the problem of the existence of an algorithm that determines, given an arbitrary element $g$ and a finitely generated submonoid $M$ of a group $G$, whether $g$ belongs to $M$. Note that in \cite{RomTwo} the author announced a negative solution to this problem for a free nilpotent group $N_{k,c}$ of nilpotency class $c\geq 2$  of sufficiently large rank $k$. This result will appear in \cite{RomIzv}. This gives an answer to the well-known question of M. Lohrey and B. Steinberg (\cite{LohSur}, Open problem 24)  about the existence of a finitely generated nilpotent group with an unsolvable  submonoid membership problem. Moreover, the existence in $N_{k,c}$ of a finitely generated submonoid $M$  with the unsolvable  membership problem was established. The proof shows how, from an arbitrary Diophantine equation $P$, an element $g$ and a finitely generated submonoid $M$ of the group $N_{k,c}$ are effectively constructed such that $g$ belongs to $M$ if and only if the equation $P$ is solvable in integers. Then the undecidability of Hilbert's 10th problem allows us to obtain from this result the undecidability of the membership problem for $N_{k.c}$ with respect to $M$. 


In \cite{Col} the authors prove that the somewhat more general  the subsemigroup membership problem is solvable for the Heisenberg group $\mathbb{H}=H(3, \mathbb{Z})$ consisting of upper triangular integer matrices with units along the diagonal. In other words, $\mathbb{H}$ is the free nilpotent group $N_{2,2}$. Earlier in \cite{Ko} it was shown how to solve the  problem of belonging of the identity matrix to finitely generated subsemigroups in $\mathbb{H}$.
 In \cite{Col}, the question was raised about the solvability of the submonoid membership problem for a direct power of the Heisenberg group.
 
This paper is a continuation of our previous papers: the paper \cite{RomTwo} mentioned above and the recently published paper \cite{RomPos}, in which sufficient conditions for the solvability of the submonoid  membership problem for a free nilpotent group of the  class $2$ with respect to a given submonoid $M$ were presented, as well as the upcoming paper \cite{RomIzv}. Our objective in this paper is to prove the undecidability of the submonoid membership problem for a sufficiently large finite direct power $\widetilde{\mathbb{H}}=\mathbb{H}^n$ of the Heisenberg group $\mathbb{H}$. Just as in \cite{RomIzv}, we prove that, given any Diophantine equation $P$, one can effectively construct an element $g$ and a finitely generated submonoid $\widetilde{M}$ of  the group $\widetilde{\mathbb{H}}$ such that  $g$ belongs to $\widetilde{M}$ if and only if the equation $P$ is solvable in integers. Again, the undecidability of Hilbert's 10th problem allows us to obtain from this result the undecidability of the membership problem for $\widetilde{\mathbb{H}}$ with respect to $\widetilde{M}$.

This result also easily implies the existence of a submonoid $M$ of a free nilpotent group $N_{k,c}$ of sufficiently large rank $k$ of any class $c \geq 2$ with the unsolvable problem of belonging to  $M$. 


Note that a special case of the submonoid membership problem for $G$ is the classical membership problem, which came from M. Dehn, where $M$ is a finitely generated subgroup. In a different terminology, it is called the {\it generalized word problem}.  
A.I. Maltsev \cite{Mal} showed that this problem is decidable for any finitely generated nilpotent group. It is worth noting that in the class of finitely generated nilpotent groups, almost all basic algorithmic problems (word, conjugacy, isomorphism, etc.) are solved positively. The exceptions are the problem of endomorphic reducibility and a number of problems related to equations and identities in groups. See surveys \cite{NRR} -- \cite{RomAT}  on this subject.

The submonoid membership problem is the most important fragment of the more general  rational subset membership problem. See survey \cite{LohSur}.

This problem for a non-commutative group is currently considered as a transfer of the classical problem of integer linear programming, where the submonoid membership problem   for a free abelian group appears on a non-commutative platform. A new line of research has emerged and is being developed -- noncommutative discrete optimization. The chapter ``Discrete optimization in groups'' in the book \cite{GAGTA} is devoted to this direction. In this case, special attention is paid to the class of finitely generated nilpotent groups, which is closest to the class of abelian groups.


\section{Diophantine equations and Skolem systems}
\label{sec:2}

Let $\zeta_1, \ldots , \zeta_t$ be an arbitrary set of commuting variables. A polynomial $D(\zeta_1, \ldots , \zeta_t)$ with integer coefficients in these variables is called {\it Diophantine}.

In this paper, we will write an arbitrary Diophantine equation in the form
\begin{equation}
\label{eq:1}
D(\zeta_1, \ldots , \zeta_t) = \upsilon ,\, \upsilon \in \mathbb{Z},
\end{equation} 
\noindent
where the polynomial from the left-hand side has zero constant term.


 
\subsection
 {Skolem systems}
 \label{ssec:1}
 In the monograph \cite{Skolem}, T. Skolem showed that any Diophantine equation  is equivalent to a system of equations in a larger number of variables of three types:
$\zeta \zeta' - \zeta'' =0,\, \zeta + \zeta' - \zeta''=0, \zeta - \zeta' = 0 ,$ and one equation of the form $\zeta - \upsilon =0\, (\upsilon \in \mathbb{Z})$, where each variable  $\zeta , \zeta', \zeta'' $ either occurs in the notation of the original polynomial $D(\zeta_1, \ldots , \zeta_t)$, or is introduced additionally. Such a system is called the {\it Skolem system}. In what follows, we also write the equations of the Skolem system in the form $\zeta\zeta' = \zeta''$,\,
$\zeta + \zeta' = \zeta''$,\, $\zeta = \zeta',$\, and\, $\zeta = \upsilon ,$\, respectively.

 \subsubsection
 {Algorithm for obtaining the Skolem system}
 \label{sssec:1} 
 We  show how to write the Skolem system equivalent to an equation of the form (\ref{eq:1}). We assume that either all the coefficients of the polynomial $D(\zeta_1, \ldots , \zeta_{t})$ are positive, or there are coefficients of different signs among them. If initially all these coefficients are negative, then we pass to the equation obtained by multiplying both parts of (\ref{eq:1}) by $-1$.
 
 We take one of the non-linear monomials on the left-hand side of the considered equation. Let $\zeta \zeta'$ be the product of its two factors. We  introduce a new variable $\zeta''$ and write a new equation $\zeta\zeta'= \zeta''$ into the system, simultaneously replacing the product $\zeta \zeta'$ in the monomials  by $\zeta''$. The degree of the monomial under consideration will decrease by one. If it has become linear, go to the next monomial. If not, then we continue to act similarly with the given monomial until it becomes linear.
 
 Then we move  to the next monomial, and so on. As a result, the left-hand side of the equation will be represented as an algebraic sum of variables. Next, we introduce new variables, replacing $\zeta + \zeta'$ in this sum by $\zeta''$ (similarly, $- \zeta - \zeta'$ is replaced by $- \zeta''$ ), adding the equation $\zeta + \zeta' = \zeta''$ to the system. We continue this process. If all coefficients in the algebraic sum are equal to $1$, then the last equation will be of the form $\zeta = \upsilon$, which we will also include in the system. If terms of different signs were present, then by transforming all the terms on the left-hand side, we arrive at an equation of the form $\zeta - \zeta' = \upsilon$. Then we set $\zeta = \zeta' + \zeta''$ and $\zeta'' = \upsilon .$
 
 
 
  
 \subsubsection{Nonnegative  Diophantine equations and Skolem systems}
 \label{sssec:2}
 A Diophantine equation that is considered solvable if it has a solution in nonnegative integers is called {\it nonnegative}. Similarly, a Skolem system for which decidability means the existence of a solution in nonnegative integers is called {\it nonnegative}.
 
   
 \begin{lemma} 
 \label{le:1}
  Solvability of an arbitrary Diophantine equation (\ref{eq:1})
is equivalent to the solvability of some nonnegative Diophantine equation in $2t$ variables effectively constructed from this equation. The resulting equation is equivalent to the nonnegative Skolem system $S_{\upsilon}$.
\end{lemma}
Proof. 
 We write each variable $\zeta_i$ as the difference of the new variables $\zeta_i' - \zeta_i''.$ Substituting these differences for the variables of the equation (\ref{eq:1}), we obtain the nonnegative Diophantine equation 
\begin{equation}
\label{eq:2}
D_1(\zeta_1', \zeta_1'', \ldots , \zeta_t', \zeta_t'') = 0.
\end{equation}
Obviously, the solvability of the equation (\ref{eq:1}) in integers implies the solvability of the equation (\ref{eq:2}) in nonnegative integers, and vice versa.

Based on the nonnegative equation obtained in this way, we build the Skolem system, as described in the   \ref{sssec:1}. All substitutions of the form $\zeta \zeta ' = \zeta ''$ and $\zeta + \zeta ' = \zeta ''$ lead to nonnegative variables of the Skolem system.  
An exception is possible only at the final replacement, when it is necessary to transform the equation of the form $\zeta - \zeta' = \upsilon$   for $\upsilon < 0$. Then we set $\zeta ' = \zeta + \zeta ''$ and $\zeta'' = - \upsilon .$ In all cases the last equation has the form $\zeta = |\upsilon |.$
\hfill $\square$ 

 

Consider the obtained nonnegative Skolem system $S_{\upsilon}$.  For what follows, we need the renumbering of variables, the introduction of new variables, and the ordering of the equations of the $S_{\upsilon}$ system. For simplicity, the notation $S_{\upsilon}$ does not change in this process.

Assume that $S_{\upsilon}$ contains $e$ equations of the form $\zeta_i\zeta_j=\zeta_l$. Introducing new variables $\zeta_s$ and making appropriate substitutions of the form $\zeta_i$ for $\zeta_s$, we achieve that each variable will appear in these equations exactly once. Equations of the form $\zeta_s=\zeta_i$ for the new $\zeta_s$ we  add to the system $S_{\upsilon}$. Next, we renumber the variables in such a way that all $e$ equations  take the form
$$
\zeta_{1}\zeta_{2}= \zeta_{3},
$$
 \begin{equation}
\label{eq:3} 
  \ldots  \\ 
\end{equation}
$$
 \zeta_{3(e-1)+1} \zeta_{3(e-1)+2}= \zeta_{3e}.
 $$
Let the system $S_{\upsilon}$ contains $d$ equations of the form $\zeta_i+\zeta_j = \zeta_l.$ Similarly to the case just considered, we will ensure that among the variables of the considered set of equations there will be no variables of the previous subsystem, and each variable in their entries will appear in these equations exactly once. Next, we renumber the variables of this subsystem in such a way that all $d$ equations of the indicated form will include only the variables $\zeta_{3e+1}, \ldots , \zeta_{3(e+d)},$ and the subsystem itself will take the form
$$
\zeta_{3e+1} + \zeta_{3e+2} = \zeta_{3(e+1)},
$$
\begin{equation}
\label{eq:4}
 \ldots 
 \end{equation} 
 $$\zeta_{3(e+d-1) +1} + \zeta_{3(e+d-1) +2} = \zeta_{3(e+d)}.$$

Next, we write the third system, consisting of equations related to the equalites of variables.  We write  all equalities of the form $\zeta_i=\zeta_j,$ for pairs with different indices $1\leq i, j\leq 3(e+d)$, which follow from the set of all equalities. It suffices to fix one representative $\zeta$ in each class of equal variables and write down all equations of the form $\zeta = \zeta'$ for the remaining variables $\zeta'$ from this class. Then we renumber all the equations of this subsystem    by assigning them the numbers $e+d +1, \ldots , e + d + q$, respectively. We have the system of equations 
\begin{equation}
\label{eq:5}
P_k \sim \zeta_{i(k)} = \zeta_{j(k)},\,  i(k)\not= j(k), 1 \leq  i(k), j(k)\leq 3(e+d), k= e+d+1, \ldots , e+d+q. 
\end{equation}
It remains to write a special equation
\begin{equation}
\label{eq:6}
\zeta_t = |\upsilon |.
\end{equation}

Except for the trivial equation (\ref{eq:1}) of the form $\zeta_1=\upsilon \, (t=1)$, the variable $\zeta_t$ is present in the system (\ref{eq:5}). Hence, $\zeta_1, \ldots , \zeta_{3e}, \zeta_{3e+1}, \ldots , \zeta_{3(e+d)}$ are all variables of the system $S_{\upsilon}$. 
 It is obvious that the system $S_{\upsilon }$ is equivalent to the new system  thus replaced. 


\section{Auxiliary assertions}
\label{sec:3}

Now we prove a number of auxiliary assertions. The commutator $[g, f]$ of two elements $g$ and $f$ of a group $G$ is defined as $g^{-1}f^{-1}gf$. Then $gf = fg[g,f]$.

Recall that the group $\mathbb{H}$ is generated by the transvections $a=t_{12}$ and $b=t_{23}$, and its center is the infinite cyclic group generated by their commutator $c=[b, a]=t_{13}^{-1}$. Then for any $\alpha , \beta \in \mathbb{Z},$  $b^{\beta}a^{\alpha} =a^{\alpha}b^{\beta}c^{\alpha \beta}.$ Further in the paper, $\mathbb{H}^k =  \prod_{i=1}^k\mathbb{H}(i)$ denotes the direct product of $k$ copies of the group $\mathbb{H}$. Denote the transvections $t_{12}, t_{23}, t_{13}^{-1}$  in the $i$-th copy ($i=1, \ldots , k $) as $a_i, b_i, c_i$ respectively. In what follows, $b_{i\to j}\, (i < j)$ means $b_i \cdot \ldots \cdot b_j$.


\begin{lemma}
\label{le:2}
Let $M$ be a submonoid of $\mathbb{H}$ generated by $g_1=ac, b$ and $g_2=a^{-1}$. 
Then  any representation of $b$ in terms of the generators of $M$ has the form 
\begin{equation}
\label{eq:7}
b = g_1^{\zeta}bg_2^{\zeta}, \zeta \in \mathbb{N}\cup\{0\}.
\end{equation}
\end{lemma}
Proof. 
Obviously, the generator $b$ of the submonoid $M$ appears exactly once among the factors of the right-hand side (\ref{eq:7}), and the total exponents of the occurrences of the other two generators $g_1$ and $g_2$ are equal. Then the cancellation of the degree $c^{\zeta}$ occurs only for the indicated arrangement of the generators of the submonoid on the right-hand side (\ref{eq:7}).

The cancellation  occurs during the commutator collecting process, which consists in the transition of $g_2^{\zeta}$ through $b$. Namely, 
\begin{equation}
\label{eq:8}
g_1^{\zeta}bg_2^{\zeta} = (a^{\zeta}c^{\zeta})a^{-\zeta}b[b, a^{-\zeta}]  = b.
\end{equation}
 \hfill $\square$
 
 The scheme of the exact location of the generators of the submonoid $M$ when expressing the element $b$ is as follows.
 $$
 \begin{vmatrix}
 &&g_1^{\zeta}& b & g_2^{\zeta}\\
 \mathbb{H}:&b=&a^{\zeta}c^{\zeta}& b & a^{-\zeta}
 \end{vmatrix}.
 $$
  \begin{center} Table 1.
 \end{center}
  


The following lemma allows us to interpret equations of the form $\zeta + \zeta ' = \zeta ''$ in the group $\mathbb{H}^4$.
\begin{lemma} 
\label{le:3}
  Let $M$ be a submonoid of $\mathbb{H}^4$ generated by $g_1=a_1c_1c_4, g_2=a_2c_2c_4, g_3=a_3c_3c_4^{-1}, g_4=a_1^{-1}, g_5=a_2^{-1}, g_6=a_3^{-1}$, and $f_1 = b_1b_2b_3.$ Then the representation of 
$\dot{b}=b_{1\to 3}$ in terms of the generators of $M$ has the form
\begin{equation}
\label{eq:9}\dot{b}=g_1^{\zeta}g_2^{\zeta '}g_3^{\zeta ''}f_1g_4^{\zeta}g_5^{\zeta '}g_6^{\zeta ''}\end{equation}
\noindent  Such a representation for nonnegative integers $\zeta , \zeta', \zeta''$ exists if and only if $\zeta + \zeta' = \zeta''$. 
\end{lemma}
Proof.
We note that for given positive $\zeta , \zeta ', \zeta ''$, the form (\ref{eq:9}) is uniquely determined up to a permutation of the factors $g_i$\, $(i=1, 2, 3)$ on the left-hand side and $g_j $\, $(j = 4, 5, 6)$ on the right-hand side of the factor $f_1$. For null value of $\zeta , \zeta '$ or $\zeta ''$, we  assume that the corresponding generator  is located as indicated.
 
Obviously, the generator $f_1$ of the submonoid $M$  occurs exactly once  among the factors of the right-hand side of (\ref{eq:9}),  and the total exponents of  occurrences of any pair of generators $g_i$ and $g_{i+3}$ for $i = 1, 2, 3$   are the same, say $\zeta , \zeta '$ and $\zeta ''$, respectively. The location of the factors $g_i$ and $g_{i+3}$  for $i=1,2,3$ with respect to $f_1$ follows from Lemma \ref{le:2}. The representation (\ref{eq:9}) for nonnegative integers $\zeta , \zeta', \zeta''$ exists if and only if 
$\zeta + \zeta' = \zeta''$. If the equality (\ref{eq:9}) holds, then the component in 
$\mathbb{H}(4)$ must be $c_4^{\zeta + \zeta'  = \zeta''} = 1$, hence  $\zeta + \zeta' = \zeta''$. If the equality 
$\zeta +\zeta' = \zeta''$ is true, then (\ref{eq:9}) is checked directly.
 \hfill $\square$
 
 The scheme of the exact location of the components of the generators of the submonoid $M$ when expressing the element $\dot{b}$ is as follows (empty positions correspond to trivial elements). 
 $$
 \begin{vmatrix}
 &\dot{b}=&g_1^{\zeta}&g_2^{\zeta '}&g_3^{\zeta ''}&f_1&g_4^{\zeta}&g_5^{\zeta '}&g_6^{\zeta ''}\\
\mathbb{H}(1):&b_1=&a_1^{\zeta}c_1^{\zeta }&&&b_1&a_1^{-\zeta}&\\
\mathbb{H}(2):&b_2=&&a_2^{\zeta '}c_2^{\zeta '}&&b_2&&a_2^{-\zeta '}\\
\mathbb{H}(3):&b_3=&&&a_3^{\zeta ''}c_3^{\zeta ''}&b_3&&&a_3^{-\zeta ''}\\
\mathbb{H}(4):&1=&c_4^{\zeta}&c_4^{\zeta '}&c_4^{-\zeta ''}&&&\\
 \end{vmatrix}
 $$
 \begin{center} Table 2.
 \end{center}
  
\begin{lemma}
\label{le:4}
Let $M'$ be a submonoid of $\mathbb{H}^6$ generated by $g_1' = a_1c_1, g_2' = a_2c_2, g_3' = a_1^{-1}a_3c_3, g_4'= a_2^{-1}a_4c_4, f_1' = b_1b_2, f_2' = b_3b_4,g_5'= a_3^{-1}a_5c_5, 
g_6'=a_4^{-1}a_6c_6, f_3' = b_5b_6, g_7' = a_5^{-1}, g_8' = a_6^{-1}.$   Then the representation of 
$b_{1-6}$  in terms of the generators of $M'$ has the form
\begin{equation}
\label{eq:10}
b_{1\to 6}=(g_1')^{\zeta}(g_2')^{\zeta '}f_1'(g_3')^{\zeta}(g_4')^{\zeta '}f_2'(g_5')^{\zeta}(g_6')^{\zeta '}f_3'(g_7')^{\zeta}(g_8')^{\zeta '}.
\end{equation}
\end{lemma}
Proof.
For given positive $\zeta , \zeta '$ the form (\ref{eq:10}) is defined uniquely up to a permutation of the  generators  $g_1', g_2'$ on the left-hand side  and $g_3', g_4'$ on the right-hand side of $f_1'$,  $g_5',g_6'$ on the left-hand side  and $g_7',g_8'$ on the right-hand side of $f_3'$. For null value of $\zeta $ or  $\zeta '$, we  assume that the corresponding generator  is located as indicated.

The proof is similar to the proof of Lemma \ref{le:3} and follows from Lemma \ref{le:2}. Obviously, each of the generators $f_1', f_2', f_3'$ of the submonoid $M'$  occurs exactly once  among the factors of the right-hand side of (\ref{eq:9}),  and the total exponents of  occurrences of any pair of generators $(g_1', g_3'), (g_2', g_4'), (g_3',g_5'), (g_4',g_6')$ and $(g_5',g_7'), \newline (g_6',g_8')$    are the same, respectively.  Then the quadruples of generators $(g_1', g_3', g_5', g_7')$ and $(g_2', g_4', g_6', g_8')$ have the same exponents, say $\zeta$ and  $\zeta '$, respectively. The location of the factors $g_i'$th  with respect to $f_j'$th  follows from Lemma \ref{le:2}. 
 \hfill $\square$



 The scheme of the exact location of the components of the generators of the submonoid $M'$ when expressing the element $b_{1\to 6}$ is as follows (empty positions correspond to trivial elements).
 $$
 \begin{vmatrix}
 &b_{1\to 6}=&(g_1')^{\zeta}(g_2')^{\zeta '}&f_1'&(g_3')^{\zeta}(g_4')^{\zeta '}&f_2'&(g_5')^{\zeta}(g_6')^{\zeta '}&f_3'&(g_7')^{\zeta}(g_8')^{\zeta '}\\
\mathbb{H}(1):&b_1=&a_1^{\zeta}c_1^{\zeta}&b_1&a_1^{-\zeta}   &&&&\\
\mathbb{H}(2):&b_2=&a_2^{\zeta '}c_2^{\zeta '}&b_2&a_2^{-\zeta '}&&&&\\
\mathbb{H}(3):&b_3=&&&a_3^{\zeta}c_3^{\zeta}&b_3&a_3^{-\zeta}&&\\
\mathbb{H}(4):&b_4=&&&a_4^{\zeta '}c_4^{\zeta '}&b_4&a_4^{-\zeta '}&&\\  
\mathbb{H}(5):&b_5=&&&&&a_5^{\zeta}c_5^{\zeta}&b_5&a_5^{-\zeta}\\  
\mathbb{H}(6):&b_6=&&&&&a_6^{\zeta '}c_6^{\zeta '}&b_6&a_6^{-\zeta '}\\  
 \end{vmatrix}.
 $$
 \begin{center} Table 3.
 \end{center}
 
 \begin{lemma}
\label{le:5}
Consider the group $\mathbb{H}^8$. Let $M$ be its submonoid generated by the elements $g_1 = a_1c_1a_7, 
g_2=a_2c_2, f_1=b_1b_2, g_3= a_1^{-1}a_3c_3, 
g_4= a_2^{-1}a_4c_4b_7, 
 f_2=b_3b_4, g_5= a_3^{-1}a_5c_5a_7^{-1}, 
g_6=a_4^{-1}a_6c_6, f_3 = b_5b_6, g_7=a_5^{-1}, 
g_8=a_6^{-1}b_7^{-1}$ (whose projections onto $\mathbb{H}^6$ coincide with the generators of the submonoid $M'$ in the lemma \ref{le:4} with the same notation, but with $'$), and by the elements   $g_9= a_8c_8c_7, f_4=b_8, g_{10}=a_8^{-1}.$ 
Then the representation of 
$\ddot{b}= b_{1\to 6}b_8$  in terms of the generators of $M$ has the  form
\begin{equation}
\label{eq:11}\ddot{b}=g_1^{\zeta}g_2^{\zeta '}f_1g_3^{\zeta}g_4^{\zeta '}f_2g_5^{\zeta}g_6^{\zeta '}f_3g_7^{\zeta}g_8^{\zeta '}g_9^{\zeta ''}f_4g_{10}^{\zeta ''}.\end{equation}
Such a representation for nonnegative integers $\zeta , \zeta', \zeta''$ exists if and only if $\zeta \zeta' = \zeta''$. 
\end{lemma}
Proof. For given positive $\zeta , \zeta '$ the form (\ref{eq:11}) is defined uniquely up to a permutation of the  generators  $g_1, g_2$ on the left-hand side  and $g_3, g_4$ on the right-hand side of $f_1$,  $g_5,g_6$ on the left-hand side  and $g_7,g_8$ on the right-hand side of $f_3$. We also note that the last three generators  are uniquely located relative to each other, but in relation to other generators they can occupy any position, since these elements  commute with other generators. For given positive $\zeta , \zeta ', \zeta ''$ the equality  $\zeta \cdot \zeta ' = \zeta ''$ is necessary and sufficient for the indicated occurrence of the element $\ddot{b}$ in the submonoid $M$. For null value of $\zeta , \zeta '$ or $\zeta ''$, we assume that the corresponding generator  is located as indicated.
It is clear that the configuration of the factors in (\ref{eq:10}) is preserved for their counterparts in (\ref{eq:11}).
Such a representation for nonnegative integers $\zeta , \zeta', \zeta''$ exists if and only if 
$\zeta \zeta' = \zeta''$. If the equality (\ref{eq:11}) holds, then the component in 
$\mathbb{H}(7)$ must be $c_7^{\zeta'' - \zeta \zeta'} = 1$, hence  $\zeta \zeta' = \zeta''$. If the equality 
$\zeta \zeta' = \zeta''$ is true, then (\ref{eq:11}) is checked directly.
\hfill $\square$

 The scheme of the exact location of the components of the generators of the submonoid $M$ when expressing the element $\ddot{b}$ is as follows (empty positions correspond to trivial elements). The  scheme  consists of the table 4 presenting all the generators except   $g_9, f_4, g_{10}$ and table 4' presenting these three generators with components on  the last two rows, corresponding $\mathbb{H}(7)$ and $\mathbb{H}(8)$ respectively,  and additional to table 4 three columns. The remaining components of these elements  are trivial.
$$
 \begin{vmatrix} \hspace{1.7cm}\ddot{b}  \,\, =  g_1^{\zeta}g_2^{\zeta }&f_1&g_3^{\zeta}g_4^{\zeta '}&f_2&g_5^{\zeta}g_6^{\zeta '}&f_3&g_7^{\zeta}g_8^{\zeta '}\\\hspace{0.8cm}\mathbb{H}(1):  b_1 = a_1^{\zeta}c_1^{\zeta }&b_1&a_1^{-\zeta}&&&&&\\
\hspace{1cm} \mathbb{H}(2): \, b_2=a_2^{\zeta '}c_2^{\zeta '}&b_2&a_2^{-\zeta '}&&&&&\\
\mathbb{H}(3):  \,\,  b_3=&&a_3^{\zeta}c_3^{\zeta}&b_3&a_3^{-\zeta}&&&\\
\, \mathbb{H}(4): \, b_4=&&a_4^{\zeta '}c_4^{\zeta '}&b_4&a_4^{-\zeta '}&&&\\
\, \mathbb{H}(5): \, b_5=&&&&a_5^{\zeta}c_5^{\zeta}&b_5&a_5^{-\zeta}&\\
\, \mathbb{H}(6): \, b_6=&&&&a_6^{\zeta '}c_6^{\zeta '}&b_6&a_6^{-\zeta '}&\\ 
\hspace{0.6cm} \mathbb{H}(7): \, \, 1 \, =  \, \,a_7^{\zeta}&&b_7^{\zeta '}&&a_7^{-\zeta}&&b_7^{-\zeta '}
\\
\, \mathbb{H}(8): \, \, b_8= &&&&&&&\\
 \end{vmatrix}
 $$
  \begin{center} Table 4.
  \end{center}
  
$$
\begin{vmatrix}  
& g_9 ^{\zeta''}& f_4 & g_{10}^{\zeta''}\\
\mathbb{H}(7):  & c_7^{\zeta''}&&\\  
\mathbb{H}(8): &a_8^{\zeta''}c_8^{\zeta''}&b_8&a_8^{-\zeta''}\\
 \end{vmatrix} 
 $$ 
 \begin{center}
 Table 4'. 
 \end{center}

 
 
 
 
  
 
\section{Choosing a direct power of the Heisenberg group and constructing a submonoid in it for which the membership problem is equivalent to the solvability of the given Diophantine equation}
\label{sec:4}

First, a Diophantine  equation (\ref{eq:1}) is taken. Then the equivalent nonnegative Skolem system $S_{\upsilon}$ is constructed from this equation. The variables and equations of this system are ordered and written as specified in (\ref{eq:3}--\ref{eq:6}).

To the resulting system $S_{\upsilon}$ we associate the group $\widetilde{\mathbb{H}}=\mathbb{H}^{8e+4d+q+1}$. The first $8e$ factors of this group are sequentially divided into $e$ blocks of $8$  factors each: $B_1, \ldots ,  B_e,$ where $B_i =   \mathbb{H}(8(i-1) + 1) \times \ldots \times \mathbb{H}(8(i-1)+ 8),\, i = 1, \ldots , e.$ Each block in accordance with the lemma \ref{le:5} corresponds to equation with the same system number in (\ref{eq:3}). The following $d$ blocks of $4$ factors each are $B_{e+1}, \ldots , B_{e+d}$, where $B_{e + i} = \mathbb{H}(8e + 4(i - 1) + 1) \times \ldots \times \mathbb{H}(8e + 4(i-1)+ 4),\, i = 1, \ldots , d.$ Each block $B_{e+i}$ in accordance with the lemma \ref{le:3} corresponds to  equation with the  system number $i$ in (\ref{eq:4}). Remaining $q+1$ factors are not divided into blocks. The next  $q$ factors 
$\mathbb{H}(k),\, k = 8e+4d+1, \ldots , 8e+4d+q$  correspond to the system (\ref{eq:5}). The last factor $\mathbb{H}(8e+4d+q+1)$ corresponds to the equation (\ref{eq:6}).

We construct a submonoid $\widetilde{M}$ of the group $\widetilde{\mathbb{H}}$ by defining its generating elements in accordance with lemmas \ref{le:3} and \ref{le:5} modified by adding multipliers to some of them from the factors $\mathbb{H}(8e+ 4d + k)$ for $k = 1, \ldots q$, taking into account the equation (\ref{eq:6}), that corresponds to the last factor $\mathbb{H}(8e+4d+q+1).$
 The generating elements of the submonoid $\widetilde{M}$ will be denoted as $\tilde{g}$ or $\tilde{f}$ with indices.
  The form of these generators is defined below.
\paragraph{\bf 
Construction of submonoid generators associated with the system (\ref{eq:3}).}
 Consider first the equations of system (\ref{eq:3}). The blocks $B_1, \ldots , B_e$ correspond sequentially to these equations. 
 We compose the group  
 \begin{equation}
 \label{eq:12}
 B(1) = \prod_{i=1}^eB_i \simeq \mathbb{H}^{8e}.
 \end{equation}
 Let $\overline{M}(1)$ denote the projection of the submonoid $\widetilde{M}$ under construction into the group $B(1)$. 

 
 Let $\mu_i: \mathbb{H}^8 \rightarrow B_i$  for $i = 1, \ldots , e$ be an isomorphism  in which the generators $a_j, b_j$ of the 
factor  
$\mathbb{H}(j)$ map to  $a_{8(i-1) +j}, b_{8(i-1) +j}$ respectively for $j = 1, \ldots , 8.$

For $B_i$ ($i = 1, \ldots , e$) we   denote  $b(i) = \mu_i(\ddot{b})$ and set  
 $$(\bar{g}_{10(i-1)+1}, \bar{g}_{10(i-1)+2}, \bar{f}_{4(i-1)+1}, \bar{g}_{10(i-1) + 3}, \bar{g}_{10(i-1)+4}, \bar{f}_{4(i-1)+2}, \bar{g}_{10(i-1)+ 5}, \bar{g}_{10(i-1)+ 6},$$
\begin{equation}
\label{eq:13} 
 \bar{f}_{4(i-1)+3}, \bar{g}_{10(i-1)+ 7}, \bar{g}_{10(i-1)+ 8},  \bar{g}_{10(i-1)+ 9},\newline \bar{f}_{4(i-1)+4}, \bar{g}_{10(i-1)+ 10}) = 
\end{equation}$$= \mu_i(g_1, g_2, f_1, g_3, g_4, f_2, g_5, 
g_6, f_3, g_7, g_8,  g_9, f_4, g_{10}).$$  
Denote by $\overline{M}_i$ the submonoid of $B_i$ generated by the just defined elements. Obviously, $\overline{M}(1) = \prod_{i=1}^e\overline{M}_i$. Then for each $B_{i}, i = 1, \ldots , e,$  the natural analog of the statement of the lemma \ref{le:5} is valid, as well as the analogue of the expression (\ref{eq:11}) with the unknowns $\zeta , \zeta', \zeta''$ replaced by $ \zeta_{3(i-1 )+1}, \zeta_{3(i-1)+2}, \zeta_{3(i-1) +3}$ respectively. Namely,  the representation of 
$b(i)$  in terms of the generators of $\overline{M}_i$ has the  form

\begin{equation}
\label{eq:14}
b(i)=\bar{g}_{10(i-1) +1}^{\zeta_{3(i-1)+1}} \ldots \bar{f}_{4(i-1)+1} \ldots  
\bar{g}_{10(i-1)+ 10}^{\zeta_{3(i-1) +3}}.
\end{equation} 
An analogue of the assertion about the uniqueness of such a representation made in the proof of  lemma \ref{le:5} is also true. 
 
 It follows from these statements and the lemma \ref{le:5} that an element $\bar{b}(1)= \prod_{i=1}^eb(i)$ belongs to the submonoid $\overline{M}(1)$ of the group $B(1)$ if and only if the variables $\zeta_i,\, i=1, \ldots , 3e,$ are a solution to the system (\ref{eq:3}).



Consider now the equations of the system (\ref{eq:4}). The blocks $B_{e+1}, \ldots , B_{e+d}$ correspond sequentially to these equations.
 Now we define  
 \begin{equation}
 \label{eq:15}
 B(2) = \prod_{i=e+1}^{e+d}B_i \simeq \mathbb{H}^{4d}.
 \end{equation} 
  Let $\overline{M}(2)$ denote the projection of the submonoid $\widetilde{M}$ under construction into the group $B(2)$. 

 
 Let $\nu_i: \mathbb{H}^4 \rightarrow B_{e+i}$  for $i = 1, \ldots , d$ be an isomorphism  in which the generators $a_j, b_j$ of the 
factor  $\mathbb{H}(j)$ map to  $a_{8e +4(i-1) +j}, b_{8e+4(i-1) +j}$ respectively for $j = 1, \ldots , 4.$
 
 For $B_{e+i}$ ($i = 1, \ldots , d$) we   denote  $b(e+i) = \nu_i(\dot{b})$ and set  
 $$(\bar{g}_{10e+4(i-1)+1}, \bar{g}_{10e+4(i-1)+2}, \bar{g}_{10e + 4(i-1) + 3}, 
 \bar{f}_{4e + 4(i-1)+1}, \bar{g}_{10e + 4(i-1) + 4},$$
  \begin{equation}
 \label{eq:16} \bar{g}_{10e+ 4(i-1)+5}, 
 \bar{g}_{10e+ 4(i-1)+ 6} = \nu_i(g_1, g_2, g_3, f_1, g_4, g_5, g_6).
 \end{equation}
Denote by $\overline{M}_{e +i}$ the submonoid of $B_{e+i}$ generated by the just defined elements.  Obviously, $\overline{M}(2) = \prod_{i=1}^d\overline{M}_{e+i}$.Then for each $B_{e+i},\, i = 1, \ldots , d,$  the natural analog of the statement of the lemma \ref{le:3} is valid, as well as the analogue of the expression (\ref{eq:9}) with the unknowns $\zeta , \zeta', \zeta''$ replaced by $ \zeta_{3e+3(i-1 )+1}, \zeta_{3e+ 3(i-1)+2}, \zeta_{3e+3(i-1) +3}$ respectively. Namely,  the representation of 
$b(e+i)$  in terms of the generators of $\overline{M}_{e+i}$ has the  form
$$
b(e+i)=\bar{g}_{10e+4(i-1) +1}^{\zeta_{3e+3(i-1)+1}}, \bar{g}_{10e+4(i-1) +2},^{\zeta_{3e+3(i-1)+2}}, \bar{g}_{10e+4(i-3) +3}^{\zeta_{3e+3(i-1)+3}}\bar{f}_{4e+4(i-1)+1}\cdot$$
\begin{equation}
\label{eq:17}
\cdot  \bar{g}_{10e+4(i-1)+ 4}^{\zeta_{3e +3(i-1) +4}}\bar{g}_{10e+4(i-1)+ 5}^{\zeta_{3e +3(i-1) +5}}\bar{g}_{10e+4(i-1)+ 6}^{\zeta_{3e +3(i-1) +6}}.
\end{equation} 
An analogue of the assertion about the uniqueness of such a representation made in the proof of  lemma \ref{le:3} is also true. 
 
 It follows from these statements and the lemma \ref{le:3} that an element $\bar{b}(2)= \prod_{i=1}^{d}b(e+i)$ belongs to the submonoid $\overline{M}(2)$ of the group $B(2)$ if and only if the variables $\zeta_{3e +i},\, i=1, \ldots , 3e+3d,$ are a solution to the system (\ref{eq:3}).

We set $\overline{\mathbb{H}}^{8e+4d} = \prod_{i=1}^{e+d}{B_i}$ and its submonoid $\overline{M} = \overline{M}(1)\cdot \overline{M}(2)$ generated by their generaing elements. We put $\bar{b} = b(1)b(2)$. It follows from the above considerations that the element $\bar{b}$ belongs to $\overline{M}$ if and only if the combined system of equations (\ref{eq:3}) and \ref{eq:4}) is solvable in integer nonnegative numbers $\zeta_1, \ldots , \zeta_{3(e+d)}$.


\paragraph{\bf  Construction of generators of the submonoid $\widetilde{M}$ associated with the system $S_{\upsilon}$}
Since all  variables of the systems (\ref{eq:3}) and (\ref{eq:4}) are pairwise distinct, both of them are decidable together. It remains to take into account the equalities between these variables in the system (\ref{eq:5}) and   the system (\ref{eq:6}). So, we consider the system $S_{\upsilon}$  of equations, which is the union of all four systems: (\ref{eq:3}) -- (\ref{eq:6}).  We are going to construct a submonoid $\widetilde{M}$ of the group $\widetilde{H}$, whose membership problem is equivalent to the solvability of the system $S_{\upsilon}$ in nonnegative integers. 

We take the already defined components of the generated elements $\bar{g}_i$th and $\bar{f}_j$th of the submonoid $\overline{M}$  and define them as components corresponding to the elements $\tilde{g}_i$th and $\tilde{f}_j$th  under construction. Then we supplement some of the elements  $\tilde{g}_i$th with new components in the factors of $\mathbb{H}(i)$ for $i=e+d+ 1, \ldots , e+ d + q +1$. 

We do this as follows.
 For any equation $P_{e+d+k}\, (k=1, \ldots , q)$ of the form  $\zeta_{i(k)}  = \zeta_{j(k)}$ from (\ref{eq:5})  we find among the representations (\ref{eq:14}) and (\ref{eq:17}) one of the generating elements $\bar{g}_l$ of the submonoid $\overline{M}$   whose  exponent is equal to $\zeta_{i(k)}$. Add the element $с_{8e+4d+k}$ to the component $8e+4d+ k$ of $\tilde{g}_l$. Then we similarly find element $\bar{g}_t$ with the exponent $\zeta_{j(k)}$ and add the element $c_{8e+4d +k}^{-1}$ to $\tilde{g}_t,$. This component will be trivial in the considered product of generating elements of the submonoid $\widetilde{M}$ if and only if $\zeta_{i(k)}=\zeta_{j(k)}$. 
 
Then for equation (\ref{eq:6}), we find among the representations (\ref{eq:14}) and (\ref{eq:17}) one of the generating elements $\bar{g}_s$ of the submonoid $\overline{M}$ whose  exponent is equal to $\zeta_{t}$ and add the element $c_{8e+4d+q+1}$ to the $8e+4d+q+1$th component of $\tilde{g}_s$. Note, that this component is equal to $c_{8e+4d+q+1}^{\zeta_t}$ in the considered product of the generators of $\widetilde{M}$. 
 

The process of constructing the generators of the submonoid $\widetilde{M}$ of the group $\widetilde{\mathbb{H}}$  is completed.

We define the element 
\begin{equation}
\label{eq:18}
g(\upsilon)= \bar{b}c_{8e+4d+q+1}^{|\upsilon |}.
\end{equation} 
Then $g(\upsilon)$ belongs to  
$\widetilde{M}$ if and only if the system $S_{\upsilon}$ has a solution in the nonnegative integers. 

\section{Main results}
\label{sec:5}
 In this section we   give formal proofs of the main results.

\begin{theorem}
\label{th:1}
For any Diophantine equation (\ref{eq:1}) there exists a direct power $\widetilde{\mathbb{H}}=\mathbb{H}^n$ of the Heisenberg group $\mathbb{H}$, a finitely generated submonoid $\widetilde{M}$ in it and an element $g(\upsilon )\in \widetilde{\mathbb{H}}$ such that the equation (\ref{eq:1}) is solvable in integers if and only if $g(\upsilon )$ belongs to $\widetilde{M}.$ The parameter $n$,  the element $g(\upsilon )$, and the finite set of generators of the submonoid $\widetilde{M}$ are effectively determined. The submonoid $\widetilde{M}$ depends only on the Diophantine polynomial $D$ on the left-hand side (\ref{eq:1}).
\end{theorem}


Proof.
We take the equation (\ref{eq:1}) and construct a nonnegative Skolem system $S_{\upsilon}$ equivalent to it, as explained in the point 2.1.1 and Lemma \ref{le:1}.
Suppose that the system  $S_{\upsilon}$  has a solution $\zeta_1, \ldots , \zeta_{3(e+d)}$.  In this case equations (\ref{eq:3}--\ref{eq:6}) turn into equalities.

We set $n = 8e+4d+q+1$. 
Construct the generating elements $\tilde{g}_i$ for $i = 1, \ldots , 10e, 10e+1, \ldots , 10e + 6d$  and  $\tilde{f}_j$ for $j = 1, \ldots , 4e, 4e+1, \ldots , 4e+d$ of the submonoid $\widetilde{M}$, as described in the section \ref{sec:4}. We define the element  $g(\upsilon )$ by the formula (\ref{eq:18}. From the statements obtained in section \ref{sec:4}  it follows that 
$g(\upsilon)$ belongs to $\widetilde{M}$.


 

Suppose now that the element $g(\upsilon )$ belongs  $\widetilde{M}$.  Then  the equalities (\ref{eq:3}) and (\ref{eq:4}) hold ( Lemmas \ref{le:3} and \ref{le:5}, formulas (\ref{eq:14}) and (\ref{eq:17})). 
 The components with numbers $8e+4d+k\, (k=1, \ldots , q)$ must be trivial, which corresponds to the fulfillment of the equalities (\ref{eq:5}). The ($8e+4d+q+1$)th component must be equal to $c_{8e+4d+q+1}^{|\upsilon |},$ which means that (\ref{eq:6}) satisfied. Consequently, the exponents $\zeta_1, \ldots , \zeta_{3(e+d)}$, with which the generators of the submonoid $\widetilde{M}$ enter the representation of the element $g(\upsilon )$, are the solution of the system $S_{\upsilon }$.
\hfill $\square$

Recall that Hilbert's 10th problem is the question of the existence of an algorithm that, given a
Diophantine equation determines whether it has an integer solution.
Yu.V. Matiyasevich (see \cite{Mat1}--\cite{MatRob}) proved that such an algorithm does not exist. In addition, he established that there exists a Diophantine polynomial $D_0(\zeta_1, \ldots , \zeta_{t})$ with a zero constant term such that there is no algorithm that determines the solvability of equations of the form
\begin{equation}
\label{eq:19}
D_0(\zeta_1, \ldots , \zeta_t) = \upsilon ,\, \upsilon \in \mathbb{Z}.
\end{equation}


From the undecidability of Hilbert's 10th problem and  Theorem \ref{th:1}, it follows that the submonoid membership problem in the class of finite direct powers of the Heisenberg group is undecidable.

The existence of an algorithmically unsolvable equation of the form (\ref{eq:19}) with a fixed left-hand side and parameter $\upsilon$ allows us to establish the following stronger assertion.

\begin{theorem}
\label{th:2}
For sufficiently large $n\in \mathbb{N}$, the direct power $\widetilde{\mathbb{H}}=\mathbb{H}^n$ of the Heisenberg group $\mathbb{H}$ contains a finitely generated submonoid $\widetilde{M}$
 with an unsolvable membership problem.
\end{theorem}
Proof. First, an equation of the form (\ref{eq:19}), which is unsolvable in integers, is taken. Then the equivalent nonnegative Skolem system $S(\upsilon )$ is constructed from this equation. The rest of the proof completely repeats the proof of the Theorem \ref{th:1}.  Variations of the parameter $\upsilon$ in the equation (\ref{eq:19}) correspond to variations of the element $g(\upsilon ).$ The submonoid $\widetilde{M}$ does not change. An element $g(\upsilon )$ belongs to  $\widetilde{M}$ if and only if the system $S_{\upsilon}$ is solvable in 
nonnegative integers. This is equivalent to saying that the equation (\ref{eq:19}) with this parameter is solvable in integers. This implies the assertion of the theorem.
\hfill $\square$

Note that the existence of a finitely generated submonoid with an unsolvable membership problem in a finitely generated nilpotent group implies the existence of a similar submonoid in the corresponding free nilpotent group.

\begin{proposition}
\label{pr:1}
For $k, c \in \mathbb{N}$, let $N$ be a  $k$-generated nilpotent group of class $c$ that has a finitely generated submonoid $M$ with the undecidable membership problem. Then the free nilpotent group $N_{k,c}$ contains a finitely generated submonoid $\widetilde{M}$ with an undecidable membership problem.
\end{proposition}
Proof. Consider the natural homomorphism $\phi : N_{k,c} \rightarrow N.$ Let $\widetilde{M}$ denote the full pre-image of the submonoid $M$ in $N_{k,c}$. An element $g\in N$ belongs to $M$ if and only if any of its inverse images $\tilde{g}$ belongs to $\widetilde{M}$. It remains to note that the submonoid $\widetilde{M}$ is finitely generated.

Let $\widetilde{M}$ is generated by elements $\tilde{g}_1, \ldots , \tilde{g}_l$. For each of these generators $g_i$, take some inverse image $\tilde{g}_i$ in the group $N_{k,c}.$ The group $N_{k,c}$ is Noetherian, so ker($\mu$) is a finitely generated subgroup. Let ker($\phi$) = gp($f_1, \ldots , f_t$). Then the submonoid $M$ is generated by the elements $g_1, \ldots , g_l, f_1^{\pm 1}, \ldots , f_t^{\pm 1}$. 
\hfill $\square$

It follows from the Theorem \ref{th:2} and the Proposition \ref{pr:1} that a submonoid with an unsolvable membership problem exists in any free nilpotent group $N_{k,c}$ for $c\geq 2$ of sufficiently large rank $k$.


 \bigskip
\begin{thebibliography}{11}


\bibitem{GAGTA} F.  Bassino,  I. Kapovich,  M. Lohrey, A. Miasnikov, A. Nicaud, A. Nikolaev, I. Rivin, V. Shpilrain,  A. Ushakov, P. Weil, {\it Complexity and Randomness in Group Theory: GAGTA BOOK 1}. Walter de Gruyter, Berlin, Boston, 2020, 386~p.

 \bibitem{Col} T. Colcombet, J. Ouaknine, P. Semukhin, J. Worrell, 
{\it On reachability problems for low dimensional matrix semigroups} In: C. Baier  (ed.) et al., 
{\it 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)},
LIPIcs, {\bf 132}, Schloss Dagstuhl -- Leibniz-Zentrum f$\ddot{\rm u}$r Informatik,
Dagstuhl, Germany, 2019, 44:1--44:15.

\bibitem{Ko} S.-Ki Ko, R. Niskanen,  R. Niskanen, and I. Potapov,  {\it On the identity problem for the special linear group and the Heisenberg group}, In: I. Chatzigiannakis, C. Kaklamanis, D. Marx, and D. Sannella (Eds), 45th Intern. Colloquium on Automata, Languages, and Programming (ICALP 2018), LIPIcs,  {\bf 132}, Schloss Dagstuhl – Leibniz-Zentrum f$\ddot{\rm u}$r Informatik, Dagstuhl, Germany, 2018, 132:1--132:15.   


\bibitem{LohSur} M. Lohrey, {\it The rational subset membership problem for groups: 
A survey}, In C. Campbell, M. Quick, E. Robertson, \& C. Roney-Dougal (Eds.),  Selected 
papers of the conference, St. Andrews, UK, August, 2013,  London Mathematical 
Society Lecture Note Series, {\bf 422},  Cambridge University Press, 2015, 368--389,
Zbl 1346.20043  

\bibitem{Mal} A.I. Maltsev, {\it Homomorphisms onto finite groups}, Ivanov Gos. Ped. Inst. Uchen. Zap., {\bf 18} \  (1958), 49--60.

\bibitem{Mat1} Yu. V. Matiyasevich, {\it The Diophantineness of enumerable set}, Soviet Mathematics, {\bf 11}:2 (1970),   354--357.

\bibitem{Mat2} Yu. V. Matiyasevich, {\it Diophantine representation of enumerable predicate}, Izvestiya  Math., {\bf 5}:1 (1971), 1--28. Zbl 0219.02035


\bibitem{Mat3} Yu.  Matiyasevich, {\it Some purely mathematical results inspired by mathematical logic}, In: Proc. Fifth Intern. Congr. Logic, Methodology and Philos. of Sci., London, Ont., 1995, 121--127.
 
\bibitem{MatRob}  Y. Matijasevic, J. Robinson, {\it Reduction of Diophantine equation to one in 13 
unknowns}, Acta Arith., {\bf 27}\, (1975),  521--553.

\bibitem{NRR} G.A. Noskov, V.N. Remeslennikov,  V.A. Roman'kov, {\it Infinite groups}, J.
 Sov. Math., {\bf 18}:5 (1982), 669--735. Zbl 0479.20001

\bibitem{RemRom} V.N. Remeslennikov, V.A. Roman'kov, {\it Model-theoretic and algorithmic 
questions in group theory}, J. Sov. Math., {\bf 31}:3 (1985), 2887--2939. Zbl 0573.20031


\bibitem{RomAT} V.A. Roman'kov, {\it Algorithmic theory of solvable groups}, Prikl. 
Diskr. Mat., {\bf 52}  (2021), 16--64. Zbl 7382418
%http://www.mathnet.ru/links/0fe4641973a3622e9178f5cfcd783670/pdm736.pdf

\bibitem{RomTwo} V.A. Roman'kov, {\it Two problems for solvable and nilpotent groups}, 
Algebra and Logic,  {\bf 59}:6 (2021), 483--492. Zbl 7350231 
%http://www.scopus.com/inward/record.url?eid=2-s2.0-85054964522$\&$partnerID=MN8TOARS
%https://doi.org/10.1515/gcc-2018-0009


\bibitem{RomPos} V.A, Roman'kov, {\it Positive elements and sufficient conditions for solvability of the submonoid membership problem for nilpotent groups of class two}, Siberian Electronic Mathematical Reports, {\bf 19}:2 (2022), 387--403. 

\bibitem{RomIzv} V.A. Roman'kov, {\it 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). 

\bibitem{Skolem} T. Skolem, {\it  Diophantische Gleichungen}, Springer, Berlin, 1938, 130 p.

\end{thebibliography}
\end{document}
\bar{b}(1) = \prod_{i=1}^eb(i)$

