| Izvestiya: Mathematics |
|
|
|
|
|
This article is cited in 3 scientific papers (total in 3 papers) Undecidability of the submonoid membership problem for free nilpotent group of class V. A. Roman'kov Omsk Branch of Sobolev Institute of Mathematics, Siberian Branch of the Russian Academy of Sciences
Bibliographic databases:
     IntroductionAlgorithmic problems in groups constitute a classical research topic in algebra, which has topological origins and analogues. At present, these problems are attracting more attention, since algebraic cryptography schemes are based on their intractability in some classes of non-commutative groups, and non-commutative groups themselves serve as platforms for implementing schemes and algorithms of non-commutative algebraic cryptography. The interest in the complexity of algorithms for solving such problems and the possibility of their effective use in practical applications has increased significantly. For more details, see the books [1]–[3]. Along with the classical M. Dehn’s problems of word, conjugacy, and membership and the H. Tietze’s isomorphism problem, which were formulated at the beginning of the 20th century, their natural generalizations, as well as other algorithmic problems, have been actively studied in recent decades (see the surveys [4]–[8]). In the present paper, we consider the membership problem for a finitely generated submonoid – this being the most important fragment of the more general rational subset membership problem for a group. A special case of this problem is the subgroup membership problem. Here, we are talking about free nilpotent groups of finite rank, and so it is important to note that, according to the classical result of Mal’cev [9], the subgroup membership problem for a finitely generated nilpotent group is algorithmically decidable. The submonoid membership problem for a non-commutative group is currently considered as a transfer, to the non-commutative setting, of the classical problem of integer linear programming, where the membership problem in a submonoid of a free abelian group appears. A new line of research (non-commutative discrete optimization) has arisen and is being developed (see [10], Chap. 5). Here, a special attention is paid to the class of finitely generated nilpotent groups as the closest to the class of abelian groups. The main result of the paper is a proof of the algorithmic undecidability of the submonoid membership problem in a fixed finitely generated submonoid of a free nilpotent group of class $2$ of sufficiently large rank, and a generalization of this result to free nilpotent groups of arbitrary class $l\geqslant 3$. The rational subset membership problem for groups has been extensively studied. M. Lohrey in his survey paper [11] on this topic, formulated the problem of the existence of a finitely generated nilpotent group with undecidable submonoid membership problem (Problem 24). This problem was also touched upon by B. Steinberg at various scientific seminars. In [12] (see also the book [13]), the author proved that the rational subset membership problem is algorithmically undecidable for a free nilpotent group of any class $l \geqslant 2$ of sufficiently large rank $r$. The proof is based on an interpretation of the Diophantine equations in this group. However, the question of decidability of the submonoid membership problem in such a group remained open. The rational subsets appearing in the proof were far from being submonoids. We recall some definitions. The class of rational subsets of a group $G$ is the smallest class containing all finite subsets of the group, which is closed under the operations of union, product, and the Kleene operation of generating a submonoid $K^*$ of the group $G$ by a subset $K$. The notion of a rational subset of a group is a natural generalization of the classical notion of a regular subset of a free monoid. Note that an arbitrary subgroup $H$ of $G$ is rational if and only if it is finitely generated (see, for example, [13], [14]). There is an analogue of Kleene’s theorem on specification of regular subsets of a free monoid by finite automata: a subset $R$ of $G$ is rational if and only if $R$ is the output set of a finite automaton over $G$ (for definitions and basic properties of rational subsets in groups, see the book [13] and the paper [14]). The structure of the paper is as follows. In § 1, we give some definitions and auxiliary results on the rational subset membership problem for a group. In § 2, the main result of the paper is given – a finitely generated submonoid of a free nilpotent group of class $2$ of sufficiently large rank is constructed for which the membership problem is algorithmically undecidable. As a corollary, this result can be extended to free nilpotent groups of class $l \geqslant 3$. In the present paper, we use the standard notation for a free abelian group $A_r$ of rank $r$ and a free nilpotent group $N_{r,l}$ of rank $r$ of nilpotency class $l$. By $[x, y] = x^{-1}y^{-1}xy$ we denote the commutator of elements $x$, $y$ of a group $G$, and by $G'$, its derived subgroup (commutant). As usual, $\mathbb{Z}$ denotes the set of integers, and $\mathbb{N}$, the set of natural numbers. For $k \in \mathbb{N}$, $\mathbb{N}_k$ denotes the set of the first $k$ natural numbers. § 1. The rational set membership problem for a groupWe denote by $\operatorname{Rat}(G)$ the class of rational subsets of a group $G$. By definition, $\operatorname{Rat}(G)$ is the smallest class that contains all finite subsets of $G$ and that is closed with respect to the following operations: $\bullet$ union: $R_1, R_2 \in \operatorname{Rat}(G)\ \Rightarrow\ R_1 \cup R_2 \in \operatorname{Rat}(G)$; $\bullet$ product: $R_1, R_2 \in \operatorname{Rat}(G)\ \Rightarrow\ R_1 \cdot R_2 = \{r_1r_2 \colon r_1\in R_1,\, r_2\in R_2\}\in \operatorname{Rat}(G)$; $\bullet$ taking the monoid generated by a set: $R\in \operatorname{Rat}(G)\ \Rightarrow\ R^* = \bigcup_{i=1}^{\infty} R^i \cup \{1\} \in \operatorname{Rat}(G)$. Examples of rational subsets are finitely generated (and only finitely generated) subgroups and finitely generated submonoids. In the general case, the class $\operatorname{Rat}(G)$ is not closed under the operations of intersection and complement. Results on characterization of finitely generated groups $G$ in which $\operatorname{Rat}(G)$ is a Boolean algebra, that is, a class that is closed under the intersection and complement operations, are given in [13] and [15]. We present some well-known results on the rational subset membership problem for a group. Positive results: $\bullet$ Benois [16]. The rational subset membership problem is decidable for free groups. $\bullet$ Eilenberg and Schützenberger [17] (for an independent proof, see [18]). The rational subset membership problem is decidable for abelian groups. $\bullet$ Grunschlag [19]. The decidability of the rational subset membership problem is preserved under finite extensions of groups. $\bullet$ Nedbay [20]. The decidability of the rational subset membership problem is preserved under free products of groups. Negative results: $\bullet$ Roman’kov [12]. For any $l \geqslant 2$ and sufficiently large $r$, the rational subset membership problem for a free nilpotent group $N_{r,l}$ is undecidable. $\bullet$ Lohrey and Steinberg [21]. The free metabelian group $M_r$ of rank $r \geqslant 2$ contains a finitely generated submonoid for which the membership problem is undecidable. The proofs in [12] are based on undecidability of Hilbert’s tenth problem, and in [21], on undecidability of the problem of the existence of a combinatorial tiling (for other numerous results on the rational subset membership problem, see the survey [11]). Note that the submonoid membership problem for a free abelian group $A_r \simeq \mathbb{Z}^r$ is related to the following integer linear programming problem: for a given integer matrix $A$ of size $m\times r$ and a vector $b \in \mathbb{Z}^r$, determine whether there exists a solution $x \in \mathbb{N}^m$ of the equation $xA = b$. In the group-theoretic language, this is the membership problem in a submonoid of the group $A_r$ generated by the rows of the matrix $A$. It is known that this version of the integer linear programming problem is NP-complete. The submonoid membership problem for arbitrary groups is currently considered as a natural generalization of the problem of integer linear programming. For a survey of the corresponding results, see [10]. § 2. An example of a finitely generated submonoid of a free nilpotent group of class two of sufficiently large rank for which the membership problem is undecidableGiven a set of commuting variables $\zeta_1, \dots, \zeta_t$, a Diophantine polynomial is a polynomial $D(\zeta_1, \dots, \zeta_t)$ with integer coefficients in these variables. In the present paper, we will write an arbitrary Diophantine equation in the form
$$
\begin{equation}
D(\zeta_1, \dots, \zeta_t) = \xi,\qquad \xi \in \mathbb{Z},
\end{equation}
\tag{1}
$$
where the polynomial on the left-hand side has zero free term. Recall that Hilbert’s tenth problem asks whether there exists an algorithm which, given a Diophantine equation, determines whether this equation has an integer solution. Matiyasevich (see [22]–[24]) proved that such an algorithm does not exist. In addition, he established the existence of a Diophantine polynomial $D_0(\zeta_1, \dots, \zeta_{t_0})$ with zero constant term such that, for the class of Diophantine equations of the form,
$$
\begin{equation}
D_0(\zeta_1,\dots, \zeta_{t_0}) = \xi,\qquad \xi \in \mathbb{Z},
\end{equation}
\tag{2}
$$
there is no algorithm that determines the solvability of equations of this class in integers. Since the above equation is obviously solvable for $\xi = 0$, this class of equations is algorithmically unsolvable under the additional constraint $\xi \ne 0$. Subsequently, it was found that Hilbert’s tenth problem is algorithmically unsolvable even for Diophantine equations with thirteen unknowns (see [24]), and then, with nine unknowns (see [25]). 2.1. Skolem systemsIn the book [26], Skolem showed that any Diophantine equation $D(\zeta_1, \dots, \zeta_t) = \xi$ is equivalent to a system of equations in a large number of variables of three types: $\zeta' \zeta'' - \zeta''' =0$, $\zeta' + \zeta'' - \zeta'''=0$ and $\zeta' - \zeta'' = 0$, as well as one equation of the form $\zeta' - \xi =0$, $\xi \in \mathbb{Z}$, where each variable $\zeta'$, $\zeta''$, $\zeta'''$ either occurs in a record of the source polynomial $D(\zeta_1, \dots, \zeta_t)$, or is introduced additionally. Such a system is called a Skolem system. In what follows, we write the equations of a Skolem system in the form $\zeta'\zeta'' = \zeta'''$, $\zeta' + \zeta'' = \zeta'''$, $\zeta' = \zeta''$ and $\zeta' = \xi$, respectively. 2.1.1. Algorithm for obtaining a Skolem systemLet us show how to write a Skolem system using an equation of the form (2). We assume that either all the coefficients of the polynomial $D_0(\zeta_1, \dots, \zeta_{t_0})$ 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 by $-1$. Let us 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. Let us introduce a new variable $\zeta'''$ and augment the system with the new equation $\zeta'\zeta''= \zeta'''$, simultaneously replacing the product $\zeta'\zeta''$ by $\zeta'''$. This reduces the degree of the monomial by 1. If this monomial becomes linear, we pass to the next monomial. If not, then we proceed similarly with the given monomial until it is linear. Next, we pass 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. Further, we introduce new variables, replacing $\zeta' + \zeta''$ in this sum with $\zeta'''$ (similarly, we replace $- \zeta' - \zeta''$ by $- \zeta''' $), adding the equation $\zeta' + \zeta'' = \zeta'''$ to the system. We continue this process. If all coefficients in the algebraic sum are $1$’s, then the last equation will be $\zeta = \xi$, 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'' = \xi$. We replace $\zeta' - \zeta''$ by $\zeta'''$, adding the equation $\zeta' = \zeta'' + \zeta'''$. We include in the system the equation $\zeta''' = \xi $, which remains after all the replacements. As a result, we obtain a Skolem system. 2.1.2. Positive Diophantine equations and Skolem systemsA Diophantine equation will be called positive if it has a solution in positive integers. Similarly, a Skolem system will be called positive if it has a solution in positive integers. Lemma 1. The solvability of an arbitrary Diophantine equation (1) is equivalent to that of some positive Diophantine equation in $2t$ variables effectively constructed from this equation. Proof. We write each variable $\zeta_i$ as the difference of new variables $\zeta_i' - \zeta_i''$. Substituting the indicated differences in place of the variables of equation (1), we obtain the Diophantine equation
$$
\begin{equation}
D_1(\zeta_1', \zeta_1'', \dots, \zeta_t', \zeta_t'') = 0.
\end{equation}
\tag{3}
$$
Obviously, the solvability of equation (1) in integers implies that of equation (3) in positive integers, and vice versa. Lemma 2. The solvability of an arbitrary Diophantine equation (1) with $\xi \ne 0$ (in particular, equations (2)) is equivalent to the existence of a solution of some positive Skolem system $S = S_{\xi }$ effectively constructed from this equation. Proof. First of all, following Lemma 1, we construct from equation (1) an equivalent positive Diophantine equation
$$
\begin{equation}
D'(\zeta_1', \zeta_1'', \dots, \zeta_{t}', \zeta_{t}'') = \xi.
\end{equation}
\tag{4}
$$
Here, $\zeta_i = \zeta_i' - \zeta_i''$, $i = 1, \dots, t$. Next, we write, for the resulting equation (4), an equivalent Skolem system, as explained in § 2.1.1 above. At the same time, the replacements of $\zeta'\zeta''$ by $\zeta'''$ and $\zeta' + \zeta''$ by $\zeta'''$ lead to positive input variables $\zeta'''$. One time it may be necessary to change variables for an equation of the form $\zeta'-\zeta'' = \xi$. If $\xi > 0$, then we introduce a new variable $\zeta'''$, replacing this equation by $\zeta' = \zeta'' + \zeta'''$ and $\zeta''' = \xi$, which we add to the system. If $\xi < 0$, then we introduce a new variable $\zeta'''$, replacing this equation by $\zeta'' = \zeta' + \zeta'''$ and $\zeta''' = - \xi$, which we add to the system. It is obvious that the solvability of equation (4) (and hence of equation (1)) is equivalent to the existence of a solution in positive integers for the resulting Skolem system $S_{\xi}$, and vice versa. Consider the positive Skolem system $S_{\xi}$ thus obtained. For later purposes, we need to renumber the variables, introduce new variables, and order the equations of the system $S_{\xi}$. For simplicity, the notation $S_{\xi}$ does not change in this process. Assume that there are $c$ equations of the form $\zeta_i\zeta_j=\zeta_l$ in $S_{\xi}$. Introducing, if necessary, new variables $\zeta_i'$, and making appropriate substitutions of the form $\zeta_i$ for $\zeta_i'$, we will achieve that each variable will appear in these equations exactly once. Equations of the form $\zeta_i'=\zeta_i$ will be added to the system $S_{\xi}$. The notation $S_{\xi}$ does not change in this process. Next, we renumber the variables so that all $c$ equations of the above form read as
$$
\begin{equation}
\zeta_{1}\zeta_{2}= \zeta_{3},\quad \dots, \quad \zeta_{3(c-1)+1} \zeta_{3(c-1)+2}= \zeta_{3c}.
\end{equation}
\tag{5}
$$
Let the system $S_{\xi}$ contain $d$ equations of the form $\zeta_i+\zeta_j = \zeta_l$. Proceeding as above, we will make sure that among the variables of the considered set of equations there will be no variables of the previous subsystem, and each variable will enter these equations exactly once. 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_{3c+1}, \dots, \zeta_{3(c+d)}$, and the subsystem itself will take the form
$$
\begin{equation}
\zeta_{3c+1} + \zeta_{3c+2} = \zeta_{3(c+1)},\quad \dots,\quad \zeta_{3(c+d-1) +1} + \zeta_{3(c+d-1) +2} = \zeta_{3(c+d)}.
\end{equation}
\tag{6}
$$
Next, we write the third subsystem consisting of equations related to the equality of variables, except for a special equation containing the parameter $\xi$:
$$
\begin{equation}
\zeta_i = \zeta_j,\qquad (i, j) \in I \subseteq \mathbb{N} \times \mathbb{N}.
\end{equation}
\tag{7}
$$
It remains to write a special equation For simplicity, we assume that $t$ is the largest index of variables and $t > 3(c+d)$. This can be achieved by introducing an additional variable if necessary.On the set of all variables $\{\zeta_1, \dots, \zeta_t\}$, equalities (7) define equivalence classes obtained by closing the written equality relations with respect to reflexivity and transitivity. In each such class $[\zeta_i] = \{\zeta_i, \zeta_{i_1}, \dots, \zeta_{i_{s(i)}}\}$, we choose one representative of $\zeta_i$. Let $T$ be the set of all chosen representatives. We assume that its elements do not occur in the equations of subsystems (5) and (6). We also do not include the variable $\zeta_t$ from equation (8) into $T$. These conditions can easily be satisfied by introducing new variables if necessary. We believe that they are provided in the process under consideration. Thus, $\zeta_1, \dots, \zeta_t$ are all variables of the system $S_{\xi}$. 2.2. The main resultTheorem. There exists a finitely generated submonoid $M$ of a free nilpotent group $N_r = N_{r,2}$ of sufficiently large rank $r$ for which the membership problem is algorithmically undecidable. 2.2.1. The scheme of the proofBy Lemma 2, using a Diophantine equation of the form (2) with parameter $\xi \ne 0$, one can effectively construct a positive Skolem system $S_{\xi}$ in a larger number of variables whose solvability in positive integers is equivalent to that of the chosen equation in integers. The group $N_r$ is selected (its rank $r$ is determined). A finite set of generating elements of the submonoid $M$ of the group $N_r$ is determined. The submonoid $M$ does not depend on $\xi$. The element $g(\xi)\in N_r$ is also defined depending on $\xi$. Further arguments are as follows. Assume that the membership problem of elements of the form $g(\xi )$ in a submonoid $M$ is algorithmically decidable. The following will be established: if the corresponding algorithm shows that the element $g(\xi )$ belongs to the submonoid $M$, then the system $S_{\xi}$ is solvable in positive integers, and hence the corresponding equation (2) with the parameter $\xi $ has a solution in integers. Further, it will be proved that if an equation of the form (2) with the parameter $\xi$ has a solution, and hence the system $S_{\xi}$ is solvable in positive integers, then the element $g(\xi )$ belongs to the submonoid $M$. This implies that the solvability of the membership problem in $M$ allows us to determine the solvability of equations of the form (2) in integers. Since the latter problem is algorithmically undecidable, and so is the membership problem in $M$. 2.2.2. Construction of the submonoid $M$ and elements of the form $g(\xi )$Bases of the groups $N_r$ and $N_r'$. We represent the basis of the group $N_r$ as the union of three pairwise disjoint sets:
$$
\begin{equation*}
X = \{x_1, \dots, x_t\},\qquad Y = \{y_1, \dots, y_6\},\qquad Z = \{z_1, \dots,z_4\}.
\end{equation*}
\notag
$$
In this case, $r = t + 10$. The images of these elements form a basis for the free abelian quotient group. The basis of the commutant $N_r'$, qua free abelian group, is the set of all possible commutators from the basis elements of the group $N_r$ of the form
$$
\begin{equation*}
\begin{gathered} \, [x_j, x_i]\quad (j > i),\qquad [y_q, y_p]\quad (q > p),\qquad [z_v, z_s]\quad (v > s), \\ [y_q, x_i],\qquad [z_v, x_i],\qquad [z_v, y_c], \end{gathered}
\end{equation*}
\notag
$$
where $i, j = 1, \dots, t$; $p, q = 1, \dots, 6$; $s, v = 1,\dots, 4$. The rank of the commutant $N_r'$, qua free abelian group, is $\binom{t+10}2$. Generating elements of a submonoid $M$ and transfer of considerations to the group $N$. Lemma 3. Let $G$ be a group, $M$ be its submonoid. Assume that $M$ contains a normal subgroup $K$ of $G$. Then $g\in G$ belongs to $M$ if and only if its image $\overline{g}$ belongs to the image $\overline{M}$ of the submonoid $M$ in the quotient group $\overline{G} = G/K$. Proof. Obviously, if $g\in M$, then $\overline{g}\in \overline{M}$. Let $\overline{g} = \overline{m}$ be the image of some element $m \in M$. Hence $g = mh$ for some $h\in K$. Since $K\leqslant M$, we have $h\in M$, and hence $g\in M$, proving the lemma. As generators of the submonoid $M$, we choose the elements $y_i, z_i$, $i = 1, \dots, 4$, and $m_i = x_iu_i$, $m_i^{-} = x_i^{-1}$, where $u_i\in N_r'$ for $i = 1, \dots, t$ (the elements $u_i$ will be defined in the next section), as well as elements of the subset $W\subseteq N_r'$. The subset $W$ contains all possible elements of the form $[x_j, x_i]^{\pm 1}$, $j > i$, except for the cases when $j > i$ are indices of the variables in the left-hand side of an equation from (5), that is, where the pair $(j, i)$ belongs to the set $\{(2, 1),\, \dots,\, (3(c- 1)+ 2,\, 3(c-1)+1)\}$. In addition, $W$ includes all elements of the form $[z_4, x_l]^{\pm 1}$, except where $l$ is the corresponding index of the variable on the right-hand side of an equation in (6), that is, where $l$ belongs to the set $\{3(c+1),\, \dots,\, 3(c+d)\}$. The elements of $W$ generate a submonoid $K$, which is a normal subgroup of the group $N_r$. Consider the group $N = N_r/K$. Let us transfer the arguments to the group $N$, in which, by Lemma 3, the membership problem in the image of the submonoid $M$ is equivalent to the original membership problem in $M$. For simplicity, for $N$ we retain the notation for the images of the submonoid and elements of the group $N_r$ under consideration. All the commutators included in $W$ are equal to $1$ in the group $N$. Note that in $N$ the elements $m_i$, $m_i^{-}$ commute with the elements $m_j$, $m_j^{-}$ in all cases except where $(j, i) \in \{(2,1),\, (5,4),\, \dots,\, (3(c-1)+ 2, 3(c-1)+1)\}$. Also, the element $z_4$ commutes with all elements $m_l$, $m_l^{-}$, except for the cases where $l \in \{3(c+1),\, \dots,\, 3(c+d )\}$. The quotient group $N/N'$ is isomorphic to the quotient group $N_r/N_r'$, that is, is a free abelian group of rank $r$ whose basis is induced by the basis $X\cup Y \cup Z$ of the group $N_r$. Since all commutators of the form $[x_j, x_i], [z_4, x_l]$ included in $W$ belong to the basis of the commutant $N_r'$, the images of the remaining elements of this basis form a basis for the commutant $N'$ as a free abelian group. Thus,
$$
\begin{equation*}
\begin{aligned} \, &\{[x_j, x_{j-1}]\ (j = 2, 5, \dots, 3(c-1)+2),\ [y_q, y_p]\ (q > p), \\ &\qquad [z_v, z_s]\ (s, v = 1, \dots, 4,\, v > s),\ [y_q, x_i]\ (i=1, \dots, t), \\ &\qquad [z_v, x_i]\ (v= 1, 2, 3,\, i=1, \dots, t),\ [z_v, y_p]\ (v = 1, \dots, 4), \\ &\qquad [z_4, x_l]\ (l=3(c+1), \dots, 3(c+d))\}, \end{aligned}
\end{equation*}
\notag
$$
where $p, q = 1, \dots, 6$, is a basis for the commutant $N'$. Definition of the elements $u_i\in N'$ included in the generators $m_i$, $i = 1, \dots, t$The elements $u_i$, as well as the elements $m_i=x_iu_i$, correspond to the variables $\zeta_i$, $i = 1, \dots, t$. To define the elements $u_i$, $u_j$ and $u_l $ corresponding to equations of the form $\zeta_i\zeta_j = \zeta_l$ in (5), we set
$$
\begin{equation}
\begin{alignedat}{2} u_i &= [y_2, x_i][y_3, x_i][y_4, x_i], &\qquad i &= 1, 4, \dots, 3(c-1) + 1, \\ u_j &= [y_1, x_j][y_2,x_j][y_3, x_j][z_2, x_j], &\qquad j &= 2, 5, \dots, 3(c-1) +2, \\ u_l &= [y_2, x_l][y_3, x_l][x_{l-1}, x_{l-2}]^{-1}, &\qquad l &= 3, 6, \dots, 3c. \end{alignedat}
\end{equation}
\tag{9}
$$
Thus, the values of the elements $u_1, \dots, u_{3c}$, and hence, of $m_1, \dots, m_{3c}$), are defined. To define the elements $u_i$, $u_j$ and $u_l$ corresponding to equations of the form $\zeta_i + \zeta_j = \zeta_l$ in (6), we set
$$
\begin{equation}
\begin{alignedat}{2} u_i &= [y_2, x_i][y_3, x_i][z_4, x_{i+2}], &\qquad i &= 3c+1, 3(c +1) +1, \dots, 3(c + d - 1) +1, \\ u_j &= [y_2, x_j][y_3, x_j][z_4, x_{j+1}], &\qquad j &= 3c+2, 3(c +1) +2, \dots, 3(c + d - 1) +2, \\ u_l &= [y_2, x_l][y_3, x_l], &\qquad l &= 3(c+1), 3(c+2), \dots, 3(c+d). \end{alignedat}
\end{equation}
\tag{10}
$$
Thus, the values of the elements $u_{3c+1}, \dots, u_{3(c+d)}$, and hence, of the elements $m_{3c+1}, \dots, m_{3(c+d)}$, are defined. If the variable $\zeta_i$ is included in $T$ (in particular $i > 3(c+d)$), we set
$$
\begin{equation}
u_i = [y_2, x_i][y_3, x_i][z_3, x_i][z_3, x_{i_1}] \cdots [z_3, x_{i_{s(i)}}].
\end{equation}
\tag{11}
$$
Here, the indexes correspond to the equivalence class $[\zeta_i]=\{\zeta_i, \zeta_{i_1}, \dots, \zeta_{i_{s(i)}}\}$. For the remaining variables $\zeta_i$, $i > 3(c+d)$ (not included in $T$), except $\zeta_t$, we set For the variable $\zeta_t$ which enters the singular equation (8), we set So, the elements $u_i$ for $i = 3(c+d) +1, \dots, t$, and hence, $m_{3(c+d)+1}, \dots, m_{t}$, are defined.Thus, all the generating elements of the submonoid $M$ are defined. Elements $g(\xi )$ tested for membership in the submonoid $M$. We set
$$
\begin{equation}
g(\xi ) = z_1y_1z_2y_2z_3z_4y_3y_4\cdot \prod_{j\in J}[z_1,x_j]^{-1}\cdot \prod_{i\in J'}[z_2, x_i]^{-1}\cdot [y_6, y_5]^{\xi},
\end{equation}
\tag{14}
$$
where $J = \{2, 5, \dots, 3(c - 1)+2\}$, $J' = \mathbb{N}_t \setminus J$. 2.2.3. Possible expressions of the elements $g(\xi )$ as products of generating elements of the submonoid $M$ and their connection with the solution of the system $S_{\xi}$First, we prove an auxiliary assertion. Lemma 4. Let $N_s=N_{s,2}$ be a free nilpotent group of class two with basis $v_1, \dots, v_s$. Then any two distinct products of basic elements, each of which is included in the expression exactly once, define distinct elements of the group $N_s$. Proof. For $s=2$, the assertion is obvious, since $v_2v_1 = v_1v_2[v_2, v_1]$, $[v_2, v_1] \ne 1$. Suppose that $s\geqslant 3$ and there are two expressions of the indicated type of one element of the group $N_s$: $v_{i_1}\cdots v_{i_s} = v_{j_1}\cdots v_{j_s}$. We choose $i_l\ne i_1, i_s$ and pass to the quotient group $N_s$ by the normal closure of the element $x_{i_l}$, which is isomorphic to the group $N_{s-1}=N_{s-1,2}$. Inducting, we conclude that either $i_1=j_1$ if $j_1\ne i_l$ or $i_s=j_s$ otherwise. Both cases are treated similarly. Let, for definiteness, $i_s = j_s$. The proof completes by multiplying both sides of the considered equality on the right by $v_{i_s}^{-1}$ and inducting on the rank. Note that in the general case the semigroup generated by the basic elements of the group $N_s$ is not free. For example, $v_1v_2^2v_1 = v_2v_1^2v_2$. Let us continue the proof of the theorem. Lemma 5. Suppose that the element $g(\xi )$ belongs to $M$. Then $g(\xi )$ can be represented in terms of generators of the submonoid $M$ as in which $A, \dots, I$ are products of generators of $M$ $m_i$, $m_i^{-}$, $i = 1, \dots, t$. Proof. From representation (14) it follows that the generators $y_i$, $z_i$, $i = 1, \dots, 4$ must appear in the right-hand side of (15) exactly once (as in (14)). To establish this, factorizing the group $N$ by the normal closure of the elements $y_5, y_6, x_1, \dots, x_t$, we obtain a free nilpotent group $N_8=N_{8,2}$ with a basis consisting of the images of the elements $y_i$, $z_i$, $i = 1, \dots, 4$.
To show a one-time occurrence assertion, consider the natural homomorphism of the group $N$ into the free abelian group $N_8/N_8'$. The image of an arbitrary element $h\in N$ has the canonical form $\overline{h}=\prod_{i=1}^4\overline{y}_i^{\,\alpha_i}\overline{z}_i^{\ ,\beta_i}$ in the induced basis $\{\overline{y}_i, \overline{z}_i,\, i = 1, \dots, 4\}$, where $\alpha_i$, $\beta_i$ are the total powers in $h$ of the elements $y_i$ and $z_i$, respectively. Since, for the element $g(\xi )$, its image in $N_8/N_8'$ coincides with that of the product $z_1y_1z_2y_2z_3z_4y_3y_4$ for which all $\alpha_i$, $\beta_i$ are equal to $1$, this must be the same for any of its expressions in $N$. Since (15) can contain only positive powers of generators of the submonoid $M$, each of the elements $y_i$, $z_i$, $i = 1, \dots, 4$, must be included in the expression of the right of (15) exactly once. To obtain the required result about the order in which the basic elements $y_i$, $z_i$, $i = 1, \dots, 4$, appear on the right of (15), it suffices to pass to the images of the element $g(\xi )$ and of the right-hand side of (15) in the group $N_8$ and use Lemma 4. Since the image of the element $g(\xi)$ in the free abelian quotient group $N/N'$ does not depend on the elements of the form $x_i^{\pm 1}$, the total exponent of any element $m_i$ on the right of (15) should coincide with that of the element $m_i^{-}$. We consider this total exponent as the parameter $\zeta_i$. Next, to determine the location of elements of the form $m_i$, $m_i^{-}$ on the right of (15), a collection process is analyzed consisting in consecutive transfers, for each $i$, of all elements of the form $m_i$, $m_i ^{-}$ from right to left to their leftmost occurrence. The formulas $vm_i = m_iv[v, x_i]$, $vm_i^{-} = m_i^{-}v[v, x_i^{-1}] = m_i^{-}v[v, x_i]^{-1}$ will be used. The commuting elements $m_i$, $m_i^{-},$ after the completion of the collection process, make it possible to cancel all elements of the form $x_i^{\pm 1}$. The position of the elements of $N'$ in the expression does not matter, since $N'$ is a central subgroup. Note that $\zeta_i > 0$ for $i=1, \dots, t$. Indeed, if the elements $m_j$, $m_j^{-}$, $j \in J$, are not included in the right-hand side of (15), then the collection process cannot give a non-zero exponent of $[z_1, x_j]$. If the elements $m_i$, $m_i^{-}$, $i\in J'$, are not included in the right-hand side of (15), then the collection process cannot give a non-zero exponent of $[z_2, x_i]$. At the same time, the element $g(\xi )$ contains in expression (14) the element $[z_1, x_j]^{-1}$, $j \in J$, and the element $[z_2, x_i ]^{-1}$, $i \in J'$, which contradicts the assumption. Let $v$ be one of the generators $z_2$, $y_i$, $i = 1, \dots, 4$, of $N$. Then the commutator $[v, x_i]$ is not included in $W$, and hence it is a basic element of $N'$. Under this assumption, the following result holds. Lemma 6. 1. Let $u_i$ (and hence $m_i$) contain the commutator $[v, x_i]$ in its expression (see (9)–(13)). Then all entries of the elements $m_i^{-}$ must be on the right-hand side of $v$, and all entries of $m_i$, on the left-hand side. 2. Let $u_i$ (and hence $m_i$) do not contain $[v, x_i]$ for $v \in \{y_1, \dots, y_4, z_2\}$ in its expression (see (9)–(13)) and, moreover, expression (14) of the element $g(\xi)$ do not contain this commutator. Then the total exponents of the elements $m_i$ and $m_i^{-}$ to the right (and hence also to the left) of $v$ must coincide. Proof. 1. It is directly verified that in expression (14) of the element $g(\xi )$ and in the expressions of the elements $u_j$ (and $m_j$), $j \ne i$, there are no exponents of the commutator $[v, x_i ]$ in question. Next, the total exponent $m_i^{\zeta_i}$ contains the factor $[v, x_i]^{\zeta_i}$. To fulfill equality (15) it is necessary that this factor should be canceled due to the elements added as a result of the collection process relative to the elements $m_i$, $m_i^{-}$. The transfer of $m_i$ through $v$ adds a positive exponent of $[v, x_i]$, but the transfer of $m_i^{-}$ adds a negative exponent. To obtain in the collection process the maximally possible absolute value exponent of $[v, x_i]^{-\zeta_i}$, all entries of $m_i^{-}$ must be on the right-hand side of $v$. Moreover, all entries of $m_i$ must be on the left-hand side of $v$, otherwise the collection process will add a positive exponent of $[v, x_i]$ and no reduction will occur. Full reduction at the indicated location is obvious.
2. The exponents of the commutator $[v, x_i]$ appearing as a result of the collection process must cancel each other. If the total exponent of $m_i$ to the right of $v$ is $\xi_1$, and the total exponent of $m_i^{-}$ is $\xi_2$, then the collection process will add the element $[v, x_i]^{\xi_1 - \xi_2}$. So $\xi_1 = \xi_2$. Corollary 1. 1. Let $i = 1, 4, \dots, 3(c-1)+1$. Then all entries of $m_i$ belong to $CD$, and all entries of $m_i^{-}$, to $I$. 2. Let $i = 2, 5, \dots, 3(c-1)+2$. Then all entries of $m_i$ belong to $AB$, and all entries $m_i^{-}$, to $H$. 3. Let $i = 3, 6, \dots, 3c$ or $i = 3c+1, \dots, t$. Then all entries $m_i$ belong to $CD$, and all entries $m_i^{-}$, to $H$. Proof. 1. In this case, assertion 1 of Lemma 6 is applicable for $v= y_2, y_3, y_4$, whence it follows that all entries of $m_i$ belong to $ABCD$ (to the left of $y_2$), and all entries of $m_i^{-}-I$ (to the right of $y_4$). In this case, the exponent of $[v, x_i]^{\zeta_i}$ is reduced. Assertion 2 is applicable for $v=y_1$. Hence the location of $m_i$ is refined: all entries belong to $CD$.
2. Assertion 1 of Lemma 6 is applicable for $v= y_1, y_2, y_3, z_2$, which implies that all entries of $m_i$ belong to $AB$ (to the left of $y_1$), and all entries of $m_i ^{-}$ lie in $HI$ (to the right of $y_3$). In this case, the degree $[v, x_i]^{\zeta_i}$ is reduced. Assertion 2 is applicable for $v=y_4$. Hence the location of $m_i^{-}$ is refined: all entries belong to $H$. 3. Assertion 1 of Lemma 6 is applicable for $v= y_2, y_3$, which implies that all entries of $m_i$ belong to $ABCD$ (to the left of $y_2$), and all entries of $m_i^{-}$ lie in $HI$ (to the right of $y_3$). In this case, the exponent $[v, x_i]^{\zeta_i}$ is reduced. Assertion 2 is applicable for $v=y_1, y_4$. Hence the location of $m_i$ is refined: all entries belong to $CD$, and $m_i^{-}$: all entries belong to $H$. Corollary 1 is proved. If the element $g(\xi )$ belongs to $M$, then any positive integer parameter $\zeta_i$ corresponding to $m_i$ of the submonoid $M$ is a solution of the system $S_{\xi}$. Further, we consider the elements $z_i$, $i = 1, \dots, 4$, to clarify the positions of the elements $m_i$, $m_i^{-}$ in the right-hand side of equality (15). We consider role of the generator $z_1$. For any $j\in J$, the element $g(\xi )$ contains the element $[z_1, x_j]^{-1}$ in expression (14). The elements $[z_1, x_j]^{\pm 1}$ are not included in the standard expressions in the generators of the submonoid $M$. They can appear only as a result of the collection process of the elements $m_j$, $m_j^{-}$. This is possible if exactly one element $m_j$ is on the left-hand side of $z_1$, that is, this element is in $A$, but the other elements $m_j$ must be included in $B$. Next we consider role of $z_2$. For any $i \in J'$, all $m_i$ enter $CD$ by Lemma 6. The element $g(\xi )$ contains $[z_2, x_i]^{-1}$ in expression (14). The elements $[z_2, x_i]^{\pm 1}$ are not included in the standard expression in generators of $M$. They can appear only as a result of the collection process for $m_i$, $m_i^{-}$; note that there is precisely one element $m_i$ on the left-hand side of $z_2$. Hence, it must enter $C$, and the other must enter $D$. Consider the generators $z_3$ (which provide equalities (7)) and $z_4$ (which provide equality (6)). Lemma 6 shows that all elements $m_i^{-}$ enter $HI$, and all elements of the form $m_i$ lie in $ADCD$. This means that in the collection process all elements $m_i^{-}$ go through $z_3$ and $z_4$. Consider the set $T$ of representatives of the equivalence classes $[\zeta_i]$ corresponding to equations of the form $\zeta_i = \zeta_j$ from (7). Let $i$ be the index of one of these representatives. According to (11), the element $u_i$ contains in its expression the product $[z_3, x_i][z_3, x_{i_1}] \cdots [z_3, x_{i_{s(i)}}]$ corresponding to the equivalence class $[\zeta_i]=\{\zeta_i, \zeta_{i_1}, \dots, \zeta_{i_{s(i)}}\}$. After an application of the collection process in equality (15) to the elements $m_i$ and $m_i^{-}$ and reduction of the elements $x_i^{\pm 1}$, the factor $c_i = [z_3, x_i]^{\zeta_i}[z_3, x_{i_1}]^{\zeta_i} \cdots [z_3, x_{i_{s(i)}}]^{\zeta_i}$ remains. There are no elements of the form $[z_3, x_k]^{\pm 1}$ in the expression of the element $g(\xi)$, they are also absent in the expressions of the generators $m_j$ for $j \ne i$. The factors $[z_3, x_k]^{-\zeta_k}$, $k = i, i_1, \dots, i_{s(i)}$, appear in the collectio nprocess when elements $m_k^{-}$ pass through $z_3$. Their product cancels with $c_i$ (which is necessary to satisfy equality (15)) only when $\zeta_i = \zeta_{i_1} = \dots = \zeta_{i_{s(i)}} $. This conclusion is valid for all equivalence classes. Hence (15) implies the equalities of subsystem (7). Consider in the system $S_{\xi}$ all equations of the form $\zeta_i + \zeta_j = \zeta_l$ from (6). After the collection process and cancellation in (15) of the elements $x_i^{\pm 1}$, $x_j^{\pm 1}$ and $x_l^{\pm 1}$, the exponents of the commutator $[ z_4, x_l]$ should be reduced. From the elements $m_i^{\zeta_i}$, $m_j^{\zeta_j}$ the factor $[z_4, x_l]^{\zeta_i + \zeta_j}$ remains, since $u_i$ contains the factor $[z_4, x_l] $, and $u_j$ is a factor of $[z_4, x_l]$ (see (10)). Since $[z_4, x_i], [z_4, x_j]\in W$, the collection process when passing $m_i^{-}$ and $m_j^{-}$ through $z_4$ does not give non-identity commutators. On the other hand, the element $m_l^{-}$, , does not contain exponents of the element $[z_4, x_l]$ as factors, but adds the element $[z_4, x_l]^{-\zeta_l}$ to the expression when passing through $z_4$. The complete cancellation of the exponents of the commutator $[z_4, x_l]$, which is necessary to satisfy equality (15), occurs only when $\zeta_i+\zeta_j = \zeta_l$. Hence, the validity of equality (15) implies that the equalities of subsystem (6) hold. Consider in the system $S_{\xi}$ all equations of the form $\zeta_i \zeta_j = \zeta_l$ from (5). By Lemma 6, all elements $m_j$ belong to $AB$, and all elements $m_j^{-}$ lie in $H$. The elements $m_i$ belong to $CD$, and $m_i^{-}$ lie in $I$. The collection process for $m_j$, $m_j^{-}$ will give the factor $[m_j^{\zeta_j}, m_i^{\zeta_i}] = [x_j , x_i]^{\zeta_i\zeta_j}$ after passing of $m_j^{-}$ through $m_i$. The element $m_l^{\zeta_l}$ contains the factor $[x_j, x_i]^{\zeta_l}$ (see (9)), which must decrease when the collection process ends. This is only possible if $\zeta_i\zeta_j = \zeta_l$. Hence, equality (15) implies the equalities of subsystem (5). Consider the only equation (8) of the system $S_{\xi}$ which includes $\xi$ and the element $x_t$ corresponding to its variable $\zeta_t$. After carrying out the collection process for the elements $m_t, m_t^{-1}$ and excluding from the right-hand side of equality (15) the elements $x_t^{\pm 1}$, the factor $[y_6, y_5]^{\zeta_t}$ equal to the element to the left-hand side $[y_6, y_5]^{\xi}$ remains, which means that equality (8) holds. Final arrangement of generators $m_i$, $m_i^{-}$ in the right-hand side of the equality (15)Thus, given the positive Skolem system $S_{\xi}$, we define an expression of the form (15) with the above arrangement of generators of the form $m_i$, $m_i^{-}$, $i = 1, \dots, t $, that is,
$$
\begin{equation}
\begin{aligned} \, &g(\xi ) = \underbrace{m_2m_5 \cdots m_{3(c-1)+2}}_{A} \cdot z_1 \cdot \underbrace{m_2^{\zeta_2 - 1}m_5^{\zeta_5-1} \cdots m_{3(c-1)+2}^{\zeta_{3(c-1)+2}-1}}_B \cdot y_1 \nonumber \\ &\ \times \underbrace{m_1m_3\cdots m_{3(c-1)+1}m_{3c} \cdot \prod_{i=3c+1}^tm_i}_C \cdot z_2 \nonumber \\ &\ \times \underbrace{m_1^{\zeta_1-1}m_3^{\zeta_3-1}\cdots m_{3(c-1)+1}^{\zeta_{3(c-1}-1}m_{3c}^{\zeta_{3c}-1} \cdot \prod_{i=3c+1}^tm_i^{\zeta_i-1}}_D \cdot y_2z_3z_4y_3 \nonumber \\ &\ \times\underbrace{(m_2^{-})^{\zeta_2}(m_3^{-})^{\zeta_3}(m_5^{-})^{\zeta_5}(m_6^{-})^{\zeta_6}\cdots (m_{3(c-1)+2}^{-})^{\zeta_{3(c-1)+2}}(m_{3c}^{-})^{\zeta_{3c}} \cdot \prod_{i=3c+1}^t(m_i^{-})^{\zeta_i}}_H \cdot y_4 \nonumber \\ &\ \times \underbrace{(m_1^{-})^{\zeta_1}(m_4^{-})^{\zeta_4}\cdots (m_{3(c-1)+1}^{-})^{\zeta_{3(c-1)+1}}}_I. \end{aligned}
\end{equation}
\tag{16}
$$
The set $\zeta_1, \dots , \zeta_t$ is a solution of the considered system $S_{\xi}$, from which the solution of the Diophantine equation (2) is obtained. 2.2.4. Proof that the element $g(\xi )$ belongs to the submonoid $M$ in the case of solvability of the system $S_{\xi}$We will use the above conventions and notation. Let $\zeta_1, \dots, \zeta_t$ be a set of positive integers that is a solution of the positive Scolem system $S_{\xi}$. Hence equalities (5)–(8) hold. We take in the group $N$ the elements $m_i=x_iu_i$, $m_i^{-}=x_i^{-1}$ with their total exponents $\zeta_i$ for $i = 1, \dots, t$. The elements $u_i$, $i = 1, \dots, t$, are defined by formulas (9)–(13). To prove that the element $g(\xi)$ belongs to the submonoid $M$ of the group $N$ it suffices to prove (16). Consider a collection process that consists in sequential transfer in a fixed expression (16) of elements of the form $m_i^{-}$ up to entries of $m_i$ and complete cancellation of the factors $x_i^{\pm 1}$ for $i =1 , \dots, t$. To verify that the element $g(\xi)$ belongs to $M$ it suffices to establish that after the completion of the collection process, the representation of this element via (14) will remain on the right-hand side of (16). Since the order of entries of the elements $y_i$, $z_i$, $i = 1, \dots, 4$, does not change in the course of the collection process, we pay attention only to the appearance and cancellation of the exponents of basic elements from $N'$. We start the collection process with generators $m_i$, $m_i^{-}$ for $i = 1, \dots, 3c$, corresponding to the variables of subsystem (5) of $S_{\xi}$. Let us move the elements $m_j^{-}$ for $j \in J = \{ 2, 5, \dots, 3(c-1)+2\}$ from $H$ to $AB$. After cancelling all entries of $x_j^{\pm 1}$, the following factor of $m_j^{\zeta_j}$ remains:
$$
\begin{equation}
u_j^{\zeta_j} = ([y_1, x_j][y_2,x_j][y_3, x_j][z_2, x_j])^{\zeta_j}.
\end{equation}
\tag{17}
$$
In the collection process, the elements $m_j^{-}$ must go through $y_1, y_2, y_3, z_1, \dots, z_4$. In $A$, only one $m_j^{-}$ moves through $z_1$. This adds $[z_1, x_j]^{-1}$ to (16), which is also included in $g(\xi)$ defined in (14). Passing through $z_4$ does not add any elements to the expression, since $[z_4, x_j] \in W$, and, therefore, is trivial in $N$. We can assume that the entire exponent of $(m_j^{-})^{\zeta_j}$ is moved through the generators $y_1$, $y_2$, $y_3$, $z_2$, $z_3$. In this case, the additional product
$$
\begin{equation*}
([y_1, x_j][y_2, x_j] [y_3, x_j][z_2, x_j])^{-\zeta_j}\cdot [z_3, x_j]^{-\zeta_j}
\end{equation*}
\notag
$$
appears in the expression, the first factor of which cancels with element (17). The factor $[z_3, x_j]^{-\zeta_j}$ does not cancel. In this process, $(m_j^{-})^{\zeta_j}$, when passing through $CD$, also passes through the total exponent $m_{j-1}^{\zeta_{j-1}}$. The following element is added to the right-hand side of (16):
$$
\begin{equation}
[x_{j-1}^{\zeta_{j-1}}, x_j^{-\zeta_j}]=[x_j, x_{j-1}]^{\zeta_{j-1}\zeta_j}.
\end{equation}
\tag{18}
$$
Let us continue the collection process by moving the elements $m_l^{-}$, for $l = 3, 6, \dots,3c$, from $H$ to $CD$. After cancelling all entries of $x_l^{\pm 1}$, the following factor of $m_l^{\zeta_l}$ remains:
$$
\begin{equation}
u_l^{\zeta_l} = ([y_2,x_l][y_3, x_l])^{\zeta_l}\cdot [x_{l-1}, x_{l-2}]^{-\zeta_l}.
\end{equation}
\tag{19}
$$
The element $[x_{l-1}, x_{l-2}]^{-\zeta_l}$ in its expression is canceled with element (18), since the exponents (with $j = l- 1$) satisfy the equation $\zeta_{l-1}\zeta_{l-2}=\zeta_l$ of subsystem (5). Since $m_l$ occurs exactly once in $C$, only one $m_l^{-}$ passes through $z_2$. This transfer adds $[z_2, x_l]^{-1}$, which occurs in expression (14) of $g(\xi )$. Passing through $z_4$ does not add any element, because $[z_4, x_l] \in W$, and, therefore, is trivial in $N$. It remains to consider the transition of the element $(m_l^{-})^{\zeta_l}$ through $y_2$, $y_3$, $z_3$. An additional product $([y_2, x_l] [y_3, x_l])^{-\zeta_l}\cdot [z_3, x_l]^{-\zeta_l}$ appears in the expression, the first factor of which cancels with the first factor of element (19). The element $[z_3, x_l]^{-\zeta_l}$ remains in the expression. Let us transfer the elements $m_i^{-}$ for $i = 1, 4, \dots, 3(c-1) + 1$ from $I$ to $CD$. After cancelling all entries of $x_i^{\pm 1}$, the following factor of $m_i^{\zeta_i}$ remains:
$$
\begin{equation}
u_i^{\zeta_i} = ([y_2,x_i][y_3, x_i][y_4, x_i])^{\zeta_i}.
\end{equation}
\tag{20}
$$
Since $m_i$ occurs exactly once in $C$, only one $m_i^{-}$ passes through $z_2$. This adds $[z_2, x_i]^{-1}$, which occurs in expression (14) of $g(\xi )$. Passing through $z_4$ does not add elements to the expression, since $[z_4, x_i] \in W$, and, therefore, is trivial in $N$. The transitions of the element $(m_i^{-})^{\zeta_i}$ through the elements $y_2$, $y_3$, $y_4$, $z_3$ add the product $([y_2,x_i ][y_3, x_i][y_4, x_i])^{-\zeta_i}$ to the right-hand side of (16), which is reduced with the element (20), and also add the element $[z_3, x_i]^{-\zeta_i}$. By this moment, the collection process has been carried out for all elements $m_i$, $m_i^{-}$ for $i = 1, \dots, 3c$. After that, the right-hand side of (16) contains the product Also the collection process added the element
$$
\begin{equation}
g_1=\prod_{j\in J}[z_1, x_j]^{-1}[z_2, x_{j-1}]^{-1}[z_2, x_{j+1}]^{-1}
\end{equation}
\tag{22}
$$
which corresponds to the same factor of the element $g(\xi )$ in (14). Let us continue the collection process for the elements $m_i, m_i^{-}$ for $i = 3(c-1)+1, \dots, 3(c+d)$ corresponding to the subsystem (6) of $S_{\xi}$. The transfer of the elements $m_l^{-}$ for $l=3(c+1), \dots, 3(c+d)$ from $H$ to $CD$. There is precisely one element $m_l^{-}$ which is moved through $z_2$ to $C$. This gives $[z_2, x_l]^{-1}$, which is present in the expression of $g(\xi )$. After cancellation all entries of $x_l^{\pm 1}$, $m_l^{\zeta_l}$ is reduced to the factor The transitions of $m_l^{-}$ through $y_2, y_3, z_3, z_4$ add the product
$$
\begin{equation}
([y_2,x_l][y_3, x_i])^{-\zeta_l}\cdot [z_3, x_l]^{-\zeta_l}\cdot [z_4, x_l]^{-\zeta_l},
\end{equation}
\tag{24}
$$
the first factor of which cancels with the element (23). The transfer the elements $m_i^{-}$ for $i = 3c+ 1, \dots, 3(c+d-1)+1$ from $H$ to $CD$. After cancellation of all entries of $x_i^{\pm 1}$, the element $m_i^{\zeta_i}$ reduces to the factor
$$
\begin{equation}
u_i^{\zeta_i} = ([y_2,x_i][y_3, x_i])^{\zeta_i}\cdot [z_4, x_{i+2}]^{\zeta_i}.
\end{equation}
\tag{25}
$$
There is precisely one element $m_i^{-}$ which moves through $z_2$ to C. This gives the element $[z_2, x_i]^{-1}$, which presents in the expression of $g(\xi)$ in (14). The transfer through $z_4$ does not add any element to the expression, because $[z_4, x_i] \in W$ and so is trivial in $N$. The transfers of $m_i^{-}$ through $y_2$, $y_3$, $z_3$ add the product $([y_2,x_i][y_3, x_i])^{-\zeta_i}$, which cancels with the first factor of the element(25), and also add the element $[z_3, x_i]^{-\zeta_i}$. The transfers of the elements $m_j^{-}$ for $j = 3c+ 2, \dots, 3(c+d-1)+2$ from $H$ to $CD$ are considered similarly. The element $m_j^{\zeta_j}$ reduces to the factor
$$
\begin{equation}
u_j^{\zeta_j} = ([y_2,x_j][y_3, x_j])^{\zeta_j}\cdot [z_4, x_{j+1}]^{\zeta_j}.
\end{equation}
\tag{26}
$$
There is precisely one element $m_j^{-}$ which moves through $z_2$ to $C$. This gives $[z_2, x_j]^{-1}$, which is present in the expression of $g(\xi)$ in (14). The transfer through $z_4$ does not add elements to the expression, because $[z_4, x_j] \in W$, and so, is trivial in $N$. The transfers of $m_j^{-}$ through $y_2$, $y_3$, $z_3$ add the product $([y_2,x_j][y_3, x_j])^{-\zeta_j}$, which cancels with the first factor of element (25), and also add the element $[z_3, x_j]^{-\zeta_j}$. At the end of the collection process of $m_i$, $m_i^{-}$ for $i = 3(c-1)+1, \dots, 3(c+d)$ the right-hand side of equation (16) will contain the product
$$
\begin{equation}
\prod_{l=3(c+1),\, \dots,\, 3(c+d)}[z_4, x_l]^{-(\zeta_{l-2} +\zeta_{l-1}-\zeta_l)}
\end{equation}
\tag{27}
$$
(see the right-hand elements in (24)–(26), bearing in mind that there $i=l-2$, $j=l-1$). This product is equal to $1$, since all exponents of its factors are equal to $0$, because the corresponding equations $\zeta_{l-2} + \zeta_{l-1} =\zeta_l$ of subsystem (6) of $S_{\xi}$ are satisfied. Also the right-hand side of (16) will contain the product In addition, the product will appear, which corresponds to the same factor of $g(\xi )$ in (14).Let us move on to the final step of the collection process for the elements $m_i$, $m_i^{-}$ for $i = 3(c+d)+1, \dots, t$, corresponding to variables of subsystem (7) and the equation (8) of $S_{\xi}$. Each $m_i^{-}$ moves from $H$ to $CD$, and only one of them moves to $C$, adding $[z_2, x_i]^{-\zeta_i}$ into the expression in the right-hand side of equality (16). These added elements are included in the expression of $g(\xi)$ in (14). The added product has the form If $\zeta_i\notin T$, $i\ne t$, then $m_i^{\zeta_i}$ leaves the factor After the transition of $(m_i^{-})^{\zeta_i}$, the product $([y_2, x_i][y_3, x_i])^{-\zeta_i}\cdot [z_3, x_i]^{-\zeta_i}$ is added to the expression, in which the first factor cancels with element (31).For $i=t$, we have
$$
\begin{equation}
u_t^{\zeta_t} = ([y_2, x_t][y_3, x_t])^{\zeta_t}\cdot [y_6, y_5]^{\zeta_t}.
\end{equation}
\tag{32}
$$
The second factor coincides with the factor $[y_6, y_5]^{\xi}$ in expression (14) of $g(\xi )$, because $\zeta_t = \xi$ according to equation (8). After moving of $m_t^{-}$ from $H$ to $CD$, the product $([y_2, x_t][y_3, x_t])^{-\zeta_t}\cdot [z_3, x_t]^{-\zeta_t}$ is added to the expression, the first factor of which cancels with the first factor of element (32). If $\zeta_i \in T$, then $m_i^{\zeta_i}$ leaves the factor
$$
\begin{equation}
u_i^{\zeta_i}=([y_2, x_i][y_3, x_i])^{\zeta_i}\cdot ([z_3, x_i][z_3, x_{i_1}] \cdots [z_3, x_{i_{s(i)}}])^{\zeta_i}.
\end{equation}
\tag{33}
$$
Since the variables under consideration satisfy subsystem (7) of $S_{\xi}$, the equalities $\zeta_i = \zeta_{i_1} = \dots = \zeta_{i_{s(i)}}$ are satisfied. Hence the second factor of the right-hand side of (33) is $[z_3,x_i]^{\zeta_i}[z_3, x_{i_1}]^{\zeta_{i_1}} \cdots [z_3, x_{i_{s(i)}}]^{\zeta_{i_{s(i)}}}$. After collecting of $(m_i^{-})^{\zeta_i}$, the product $([y_2, x_i][y_3, x_i])^{-\zeta_i}\cdot [z_3, x_i]^{- \zeta_i}$ is added to the expression whose first factor cancels with the first factor of element (33). Hence is an element that has not yet been cancelled, which has appeared as a result of the final step of the collection process. Taking into account the elements $w_1$ not cancelled at the previous steps from (21) and $w_2$ from (28), we get The second factors of the elements $u_i^{\zeta_i}$ in (33) give the product
$$
\begin{equation}
\prod_{\{i\colon \zeta_i\in T\}}^t[z_3, x_i]^{\zeta_i},
\end{equation}
\tag{36}
$$
which cancels with $w$ from (34). The product of the elements $g_i$, $i = 1,2,3$, defined in (22), (29) and (30), multiplied by $z_1y_1z_2y_2z_3z_4y_3y_4$, gives expression (14) of $g(\xi)$. So, after the completion of the collection process, the right-hand side of equality (16) coincides with that of representation (14) of the element $g(\xi)$. This completes the proof of the theorem. Corollary 2. For any $l\geqslant 3$ in a free nilpotent group $N_{r,l}$ of sufficiently large rank $r$, there exists a finitely generated submonoid $\widetilde{M}$, whose membership problem is algorithmically undecidable. Proof. Consider the standard homomorphism $\rho \colon N_{r,l} \to N_{r}$. Denote by $\widetilde{M}$ the complete inverse image of the submonoid $M$. Since the subgroup $\operatorname{ker}(\rho) = \gamma_3(N_{r,l})$ (the third member of the lower central series of the group $N_{r,l}$) is finitely generated, $\widetilde{M} $ is a finitely generated submonoid. By Lemma 3, the membership problem in the submonoid $\widetilde{M}$ for the group $N_{r,l}$ is equivalent to that in the submonoid $M$ for the group $N_r$. So this problem is algorithmically undecidable. A short report about the results obtained (without proofs) was published in [27]. Sufficient conditions for the solvability of the membership problem for a finitely generated submonoid of a free nilpotent group of class $2$ of finite rank are given in [28]. The author is sincerely grateful to the referees for their comments and suggestions, which enabled him to significantly improve the presentation by eliminating gaps and inaccuracies in the proofs and presentation of the paper. 
Citation in format AMSBIB
\Bibitem{Rom23} |
|
||||||||||||||||||||||||||
|
Contact us: |
Terms of Use
|
Registration to the website |
Logotypes |
|