The Diophantine problem in iterated wreath products of free abelian groups is undecidable

Olga Kharlampovich, Alexei Miasnikov · 2025

Read The Diophantine problem in iterated wreath products of free abelian groups is undecidable by Olga Kharlampovich, Alexei Miasnikov (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2502-09442.txt.

Introduction

Olga Kharlampovich and Alexei Miasnikov prove a negative result in a 2025 math paper on equations in certain groups. The Diophantine problem asks whether a method exists that can decide, for any set of equations in a group, whether the equations have a solution. For some groups the answer is yes, and for others no such method can exist.

The groups here are built by stacking wreath products of free abelian groups, a layered way of joining groups, more than once. The authors show that for any such stack built from non-trivial groups, the problem cannot be decided by any algorithm. The result maps a firm limit on what equation-solving tools can do for this broad family of groups.

Catalog record

CREATOROlga Kharlampovich, Alexei Miasnikov
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE31 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2502-09442

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

The Diophantine problem in iterated wreath products of free abelian groups is undecidable Olga Kharlampovich, Alexei Miasnikov Abstract 1 Itroduction It is known that the first-order theory of any finitely generated solvable group is decidable if and only if the group is virtually abelian: Ershov proved this for nilpotent groups [ 3 ] , Romanovskii generalized it to the polycyclic case [ 10 ] , and finally, Noskov established the result for all finitely generated solvable groups [ 8 ] . For the universal theories of solvable groups the situation is much less clear. In 1998 Chapuis proved that free metabelian groups have decidable universal theory [ 1 ] . The question whether the universal theory of free solvable groups of class \geq 3 is decidable is still open, though it is undecidable provided that the Diophantine problem for {\mathbb{Q}} is undecidable [ 1 ] . Equations are particular types of universal formulas, but they allowed to have constants, so the Diophantine problem in a group could be harder than its universal theory. Thus, the Diophantine problem in free solvable non-abelian groups is undecidable: Romankov showed this for the metabelian case [ 10 ] , and Garreta, Myasnikov, Ovchinnikov - for the general one [ 4 ] (though Romankov proved undecidability of single equations, which is harder). Iterated wreath products of free abelian groups in some respect are similar to free solvable groups. Indeed, from the algebraic view-point there is so-called Magnus embedding of free solvable groups S into iterated wreath products T of free abelian groups, that allows to solve various problems in S by reduction to T . but the universal theories of iterated wreath products of free abelian groups are decidable [ 1 ] . However, it was shown in 2012 by Myasnikov and Romanovskii that the Diophantine problem in iterated wreath products of k\geq 2 infinite cyclic groups is undecidable [ 7 ] (the authors stated the result as undecidability of the universal theories of such groups with constants in the language, but the proof is about the Diophantine problem). In particular, the Diophantine problem in the group {\mathbb{Z}}\,{\rm wr}\,{\mathbb{Z}} is undecidable. In 2024 Dong using a different argument also proved that the Diophantine problem in {\mathbb{Z}}\,{\rm wr}\,{\mathbb{Z}} is undecidable. In this paper we prove (Theorem 4.3 ) that the Diophantine problem in iterated restricted wreath products G={\mathbb{Z}}^{m_{k}}\,{\rm wr}\,({\mathbb{Z}}^{m_{k-1}}\,{\rm wr}\,(\ldots({\mathbb{Z}}^{m_{3}}\,{\rm wr}\,({\mathbb{Z}}^{m_{2}}\,{\rm wr}\,{\mathbb{Z}}^{m_{1}})\ldots),\ \ k\geq 2, of arbitrary non-trivial free abelian groups of finite ranks is undecidable, i.e., there is no algorithm that given a finite system of group equations with coefficients in G decides whether or not the system has a solution in G . Our proof is based on the ideas from [ 7 ] and [ 6 ] . In [ 5 ] we showed that the Diophantine problem for quadratic equations in metabelian Baumslag-Solitar groups BS(1,k) and in wreath products A\,{\rm wr}\,\mathbb{Z} , where A is a finitely generated abelian group and \mathbb{Z} is an infinite cyclic group, is decidable, i.e. there is an algorithm that given a finite quadratic system of equations with constants in such a group decides whether or not the system has a solution in the group. We showed also that one can decide if there are non-trivial solutions of systems of equations without coefficients in these groups. In the published version of this paper we stated that the Diophantine problem in metabelain non-abelian groups BS(1,k) is decidable. Unfortunately, the proof of this is incorrect, so the decidability of the Diophantine problem in such groups is still open. 2 Wreath products of groups In this section we describe some algebraic properties of wreath products that we use in the sequel. 2.1 General properties Let A and B be arbitrary groups. Denote by G=B\,{\rm wr}\,A the restricted wreath product of A and B . We fix this notation throughout the whole paper. By construction, the group G is a semidirect product N\rtimes A , where N is the direct product N\simeq\Pi_{a\in A}B_{a} of isomorphic copies B_{a} of B , termed the base group of this wreath product, and A , termed the active group, acts on N by shifting the copies B_{a} in N . Namely if f\in\Pi_{a\in A}B_{a} is viewed as a function f:A\to\cup_{a\in A}B_{a} , then the action of a\in A on f results in a function f^{a}(x)=f(ax) for any x\in A . As usual, elements g\in G can be written uniquely in a normal form g=af , where a\in A,f\in N , and the multiplication is given by a_{1}f_{1}\cdot a_{2}f_{2}=a_{1}a_{2}f_{1}^{a_{2}}f_{2}. (1) Note that in this case f^{a}=a^{-1}fa - the conjugation of f by a . The groups A and B canonically embed into G via the maps a\in A\to a\cdot 1_{N}\in G and b\in B\to f_{b} , where f_{b}(x)=1 for x\neq 1 and f_{b}(1)=b . We often identify A and B with their images in G , so B is identified with the copy B_{1} . We list below some known properties of wreath products G . 1) The subgroup N of G is precisely the normal closure N=ncl(B) of B in G . 2) If B is abelian then N is also abelian. Furthermore, in this case the action of A on N extends linearly to the action of the integer group ring {\mathbb{Z}}A on N , so for u=\Sigma n_{i}a_{i}\in{\mathbb{Z}}A and t\in N t^{u}=\Pi(t^{n_{i}})^{a_{i}} . This makes N into {\mathbb{Z}}A -module. Observe, that we use here the multiplicative notation for the action of {\mathbb{Z}}A on N , which matches naturally with the conjugation notation in G . 3) If B is abelian then for any 1\neq b\in B one has C_{G}(b)=N . Proof. 1) and 2) are obvious. 3) Let 1\neq b\in B . Since N is a direct product N\simeq\Pi_{a\in A}B_{a} of isomorphic copies B_{a} of B , every element in N commutes with b . Every element not in N has form af , 1\neq a\in A,f\in N . Since fb=bf and ab\neq ba , af does not commute with b . ∎ 2.2 Wreath products of free abelian groups Let A and B be free abelian groups with bases \{a_{1},\ldots,a_{m}\} and \{b_{1},\ldots,b_{n}\} , respectively. If not said otherwise, we vew the groups A and B in the multiplicative notation. Let G=B\,{\rm wr}\,A . We list below some known properties of G . 3) The ring {\mathbb{Z}}A is isomorphic to the ring of Laurent polynomials {\mathbb{Z}}A\simeq{\mathbb{Z}}[a_{1},a_{1}^{-1},\ldots,a_{m},a_{m}^{-1}], so sometimes we identify {\mathbb{Z}}A with Z[a_{1},a_{1}^{-1},\ldots,a_{m},a_{m}^{-1}] . 4) ZA -module N is a free {\mathbb{Z}}A -module with basis b_{1},\ldots,b_{n} . Now we describe the members G_{n} of the lower central series of G . Recall that G_{1}=G and G_{i+1}=[G,G_{i}] for 1<i\in{\mathbb{N}} . Denote by \Delta the augmentation ideal of {\mathbb{Z}}A , that is the kernel of the homomorphism {\mathbb{Z}}A\to{\mathbb{Z}} induced by the trivial homomorphism A\to 1 . As an ideal \Delta is generated by elements a_{1}-1,\ldots,a_{m}-1 of {\mathbb{Z}}A . To see this note that a_{i}^{-1}-1=\frac{1-a_{i}}{a_{i}} and uv-1=u(v-1)+(u-1) for u,v\in A . Let \Delta^{i} be the i th-power of \Delta , i.e., it is an ideal in {\mathbb{Z}}A generated by all products of the type (y_{1}-1)\ldots(y_{i}-1) , where y_{j}\in\{a_{1},\ldots,a_{m}\} . Denote by N^{\Delta^{i}} the {\mathbb{Z}}A -submodule of N generated by all elements u^{P} , where u\in N

Read the complete text