Introduction
The question of decidability of (systems of) equations in groups is widely known as the Diophantine Problem for groups, and we denote it by D P \mathcal{DP} DP , or by D P ( G ) \mathcal{DP}(G) DP ( G ) when it refers to a group G G G . We extend the D P \mathcal{DP} DP by requiring that the solution sets satisfy certain constraints, and study this augmented problem in one-relator groups and more generally, free-by-cyclic groups. We give the most general statements if the groups have non-trivial centre, but we also obtain results for several groups with trivial centre.
Among several types of constraints (see § 4.1 ), we focus on abelian predicates, which we also call abelianisation constraints , and denote by a b \mathrm{ab} ab . These constraints require that the ‘abelian form’ of the solutions, where any two symbols commute, satisfies a given set of equations as well; equivalently, the constraints can be viewed as equations in the abelianisation of G G G . This problem, denoted by D P ( G , a b ) \mathcal{DP}(G,\mathrm{ab}) DP ( G , ab ) for a group G G G , was introduced in [14 ] , where it was shown to be undecidable in hyperbolic groups and right-angled Artin groups, if these have sufficiently large abelianisation; that is, they have abelianisation with torsion-free rank greater than 2.
Studying the Diophantine Problem with abelianisation constraints can often give methods for studying the ‘plain’ Diophantine Problem. For example, if the commutator width in a group G G G is finite, then the commutator subgroup in G G G is definable in D P ( G ) \mathcal{DP}(G) DP ( G ) , and so D P ( G ) \mathcal{DP}(G) DP ( G ) and D P ( G , a b ) \mathcal{DP}(G,\mathrm{ab}) DP ( G , ab ) are equivalent. This has been leveraged in Thompson’s group F F F to prove undecidability of the Diophantine Problem [28 ] , using the non-trivial fact that F F F has finite commutator width [30 ] . In other cases, the commutator subgroup may not be definable in D P ( G ) \mathcal{DP}(G) DP ( G ) , but one can often use similar techniques to compare exponent sums of various elements, as has been successful when showing the Diophantine Problems in various groups are undecidable, including certain GBS groups [33 ] , groups of the form F 3 × F 2 F_3 \times F_2 F 3 × F 2 [33 ] and one-relator groups [32 ] . An important open question in the area is also whether the Diophantine Problem is decidable in the Grigorchuk group G \mathcal{G} G and related branch groups. Since G \mathcal{G} G has finite commutator width [4 ] , D P ( G , a b ) = D P ( G ) \mathcal{DP}(\mathcal{G},\mathrm{ab})=\mathcal{DP}(\mathcal{G}) DP ( G , ab ) = DP ( G ) , and so understanding the Diophantine Problem with abelianisation constraints would settle this open question.
When free-by-cyclic groups have non-trivial centre, the fact that the Diophantine Problem is decidable follows from [15 ] (see Theorem 1.1 ). The main goal of the paper is to show that a stronger result holds in these groups when their abelianisation is virtually Z \mathbb{Z} Z : the Diophantine Problem with abelianisation constraints is decidable.
2020 Mathematics Subject Classification. 20F10, 20F65, 68Q45.
Key words and phrases. equations in groups, one-relator groups, free-by-cyclic groups, decidability.
We use several characterisations of one-relator groups with centre and the related classes of groups described below. In particular, we will use the fact that all groups of type (ii) - (v) contain (i) (see § 4.4 for a justification of the implications):
(i) infinite one-relator groups with non-trivial centre (O);
(ii) generalised Baumslag-Solitar (GBS) groups with non-trivial centre (GBS);
(iii) [finitely generated free]-by-cyclic groups with non-trivial centre (FbC);
(iv) free-by-cyclic groups of the form F ⋊ φ Z F \rtimes_{\varphi} \mathbb{Z} F ⋊ φ Z for some finitely generated free group F F F and some automorphism φ ∈ Aut ( F ) \varphi\in\operatorname{Aut}(F) φ ∈ Aut ( F ) that has finite order in Out ( F ) \operatorname{Out}(F) Out ( F ) (FbZf);
(v) virtually F × Z F \times\mathbb{Z} F × Z for some finitely generated free group F F F (vFZ).
( i ) ⇒ [ 5 ] ( i i ) ⇔ [ 38 ] ( i i i ) ⇔ [ 38 ] ( i v ) ⇒ Lemma 2.7 ( v ) (i) \xRightarrow{[5]} (ii) \xLeftrightarrow{[38]} (iii) \xLeftrightarrow{[38]} (iv) \xRightarrow{\textit{Lemma 2.7}} (v) ( i ) [ 5 ] ( ii ) [ 38 ] ( iii ) [ 38 ] ( i v ) Lemma 2.7 ( v )
The main result of [15 ] , which states that the Diophantine Problem is decidable in all groups that are virtually direct products of hyperbolic groups, implies the following.
Theorem 1.1. The Diophantine Problem is decidable in (v), and therefore in (i) - (iv).
Furthermore, the groups we are interested in (one-relator with centre, free-by-cyclic, GBS) are finite-index subgroups of direct products of specific hyperbolic groups (see Prop. 3.2 ), in the spirit of [15 ] , and the Diophantine Problem is well understood in these direct products. Thus we can reduce the Diophantine Problem (with or without constraints) in free-by-cyclic and one-relator groups with centre to the problem of solving equations in direct products of hyperbolic groups with recognisable (plus some additional) constraints. Moreover, when D P ( G , a b ) \mathit{DP}(G,\mathrm{ab}) DP ( G , ab ) is decidable, we can describe the solutions sets to systems of equations in terms of formal languages, as EDT0L languages. This is a class of languages that describes the solutions in many classes of groups, in particular hyperbolic [12 ] and abelian, which are relevant here (see [16 ] for an overview).
Our first main result is:
Theorem 1.2. Let G G G be a [finitely-generated free]-by-cyclic group with centre and virtually cyclic abelianisation. Then D P ( G , a b ) \mathit{DP}(G,\mathrm{ab}) DP ( G , ab ) is decidable and EDT0L.
This immediately implies:
Corollary 1.3. Let G G G be a one-relator group with centre and virtually cyclic abelianisation. Then D P ( G , a b ) \mathit{DP}(G,\mathrm{ab}) DP ( G , ab ) is decidable and EDT0L.
The class of groups in the statement of Theorem 1.2 are in fact exactly the tree-GBS groups, that is, the generalised Baumslag-Solitar groups whose defining graph (as a graph of groups) is a tree. Thus we have
Corollary 1.4. Let G G G be a tree-GBS group. Then D P ( G , a b ) \mathit{DP}(G,\mathrm{ab}) DP ( G , ab ) is decidable and EDT0L.
In contrast in recent work it has been shown that there are GBS-groups with undecidable Diophantine Problem; see [33 ] . Using this connection we shall see that Theorem 1.2 may also be applied to the more general class of tree-products of infinite cyclic groups (i.e. a graph product where all vertex groups are Z \mathbb{Z} Z and the defining graph is a tree) to show the following.
Theorem 1.5. Let G G G be a tree product of infinite cyclic groups. Then G G G has decidable Diophantine Problem with EDT0L solutions. Furthermore:
if all edge groups are infinite cyclic then D P ( G , a b ) \mathit{DP}(G,\mathrm{ab}) DP ( G , ab ) is decidable and EDT0L;
otherwise, D P ( G , a b ) \mathit{DP}(G,\mathrm{ab}) DP ( G , ab ) is undecidable.
When the torsion-free rank of the abelianisation is ≥ 3 \ge3 ≥ 3 , we obtain undecidability results.
Theorem 1.6. Let G G G be a [finitely generated free]-by-cyclic group with non-trivial centre and a torsion-free rank 3 or greater abelianisation. Then D P ( G , a b ) \mathit{DP}(G,\mathrm{ab}) DP ( G , ab ) is undecidable.
We note that while we do utilise finite index subgroups and extensions in our reasoning in this paper, in general it is unknown whether decidability of the Diophantine Problem is preserved under taking finite index subgroups or extensions. Also, D P ( G , a b ) \mathit{DP}(G,\mathrm{ab}) DP ( G , ab ) is know not to be preserved when taking finite index subgroups. It is known that for every RAAG, there is a corresponding RACG that contains it as a subgroup of finite index. Now in [14 ] it is proved that (a) If G G G is a right-angled Artin group that is not abelian then D P ( G , a b ) \mathit{DP}(G,\mathrm{ab}) DP ( G , ab ) is undecidable, and also that (b) If H H H is a right-angled Coxeter group then D P ( H , a b ) \mathit{DP}(H,\mathrm{ab}) DP ( H , ab ) is decidable. Hence if we take any non abelian RAAG G G G it has a finite index extension H H H with G ≤ H G \leq H G ≤ H of finite index (the RACG described above) such that D P ( H , a b ) \mathit{DP}(H,\mathrm{ab}) DP ( H , ab ) is decidable but D P ( G , a b ) \mathit{DP}(G,\mathrm{ab}) DP ( G , ab ) has undecidable with G G G a finite index subgroup of H H H .
For groups with trivial centre we have the following results.
Theorem 1.7. Let G = ⟨ a , b , t ∣ t a t − 1 = a b , t b t − 1 = b ⟩ G = \langle a,b,t \mid tat^{-1} = ab, tbt^{-1} = b\rangle G = ⟨ a , b , t ∣ t a t − 1 = ab , t b t − 1 = b ⟩ be the ‘first hydra group’. Then D P ( G , a b ) \mathit{DP}(G,\mathrm{ab}) DP ( G , ab ) is undecidable.
We note that whether the first hydra group (or any other hydra group) has a decidable Diophantine Problem is an open problem.
Recall that a cyclically pinched group G G G is a free product of two finite rank free groups amalgamated over an infinite cyclic group; that is,
G = F ( a 1 , … , a n ) ∗ Z F ( b 1 , … , b m ) , G = F(a_{1},\ldots,a_{n}) *_{\mathbb{Z}} F(b_{1},\ldots,b_{m}), G = F ( a 1 , … , a n ) ∗ Z F ( b 1 , … , b m ) ,
and the amalgamation is of the form ⟨ U ⟩ = ⟨ V ⟩ ≅ Z \langle U\rangle= \langle V\rangle\cong\mathbb{Z} ⟨ U ⟩ = ⟨ V ⟩ ≅ Z , where U ∈ F ( a 1 , … , a n ) U \in F(a_{1},\ldots,a_{n}) U ∈ F ( a 1 , … , a n ) and V ∈ F ( b 1 , … , b m ) V \in F(b_{1},\ldots,b_{m}) V ∈ F ( b 1 , … , b m ) are non-trivial. By noticing that these groups are relatively hyperbolic with sufficiently well-behaved parabolics, we are able to apply existing combination results to obtain the following:
Corollary 1.8. The existential theory (and hence the Diophantine Problem) is decidable in all cyclically pinched groups.
Cyclically pinched groups provide a rare example of a class of groups where the decidability of the Diophantine Problem with abelianisation constraints can be fully classified, without a ‘gap’ corresponding to a specific abelianisation. In this case, those with virtually cyclic abelianisation are amongst the decidable examples.
Theorem 1.9. Let G G G be a cyclically pinched group. Then D P ( G , a b ) \mathit{DP}(G,\mathrm{ab}) DP ( G , ab ) is decidable if and only if G G G has exactly two generators. In the case that G G G has two generators, D P ( G , a b ) \mathit{DP}(G,\mathrm{ab}) DP ( G , ab ) is EDT0L.
In [14 ] it is shown that for a hyperbolic group G G G if the abelianisation of G G G has torsion-free rank ≥ 2 \geq2 ≥ 2 D P ( G , a b ) \mathit{DP}(G,\mathrm{ab}) DP ( G , ab ) is undecidable, while if the abelianisation of G G G is finite then D P ( G , a b ) \mathit{DP}(G,\mathrm{ab}) DP ( G , ab ) is decidable. This motivates the study of D P ( G , a b ) \mathit{DP}(G,\mathrm{ab}) DP ( G , ab ) for hyperbolic groups (and finitely generated groups more generally) with torsion-free rank 1 1 1 . As explained in [14 ] the decidability of D P ( G , a b ) \mathit{DP}(G,\mathrm{ab}) DP ( G , ab ) when G G G has decidable Diophantine Problem and its abelianisation has torsion-free rank 1 1 1 remains an open problem. Motivated by this in Problem 4 in [14 ] it is asked whether the braid group on three strands ⟨ a , b ∣ a b a = b a b ⟩ \langle a,b \mid aba=bab\rangle ⟨ a , b ∣ aba = bab ⟩ (or more generally, odd dihedral Artin groups) have decidable D P ( G , a b ) \mathit{DP}(G,\mathrm{ab}) DP ( G , ab ) . Observing that every odd dihedral Artin groups are isomorphic to a torus knot group of the form ⟨ x , y ∣ x 2 = y m ⟩ \langle x,y \mid x^{2}=y^{m}\rangle ⟨ x , y ∣ x 2 = y m ⟩ (see for example [17 Lemma 2.8] ) we may apply the results in this paper to give a positive answer to that question:
Corollary 1.10. Let T p , q = ⟨ a , b ∣ a p = b q ⟩ T_{p,q} = \langle a,b \mid a^{p}=b^{q}\rangle T p , q = ⟨ a , b ∣ a p = b q ⟩ with p , q ≥ 2 p,q \geq2 p , q ≥ 2 . Then D P ( G , a b ) \mathit{DP}(G,\mathrm{ab}) DP ( G , ab ) is decidable. In particular D P ( G , a b ) \mathit{DP}(G,\mathrm{ab}) DP ( G , ab ) is decidable in every torus-knot group and D P ( G , a b ) \mathit{DP}(G,\mathrm{ab}) DP ( G , ab ) is decidable in every odd dihedral Artin group.
The main tool used to prove undecidability results in this paper is interpretability using systems of equations, which allows us to translate one structure into another and to reduce the Diophantine Problem from one structure to the other. The main reductions are to the Diophantine Problem in the ring of integers, which is a classical undecidable problem (Hilbert’s 10th problem).
Connections to computer science.
The Diophantine Problem with abelianisation constraints in groups is inspired by work in theoretical computer science, where the study of equations with language theoretic, length and abelianisation constraints in free monoids has a long tradition and is a very active field of research [1 , 9 , 21 , 27 , 31 ] .
Deciding whether a free monoid equation has solutions satisfying linear length constraints is a major open question, of both theoretical importance (if undecidable, it would provide a new solution to Hilbert’s 10th problem for Diophantine polynomials) and practical implications, in the context of string/SMT solvers for security analysis, formal verification, the robustness of Web applications, and more [2 ] . SMT solvers, which have boomed over the last 10 years, consider first-order formulae in a wide context, such as the real numbers, integers, data structures, and strings over finite alphabets. The question is then whether there is a solution for a first-order formula that is significantly more complex than what is handled by SAT-solvers: the name ‘satisfiability modulo theories’ (SMT) expresses the fact that the solvers work ‘modulo’ a certain theory (beyond the Boolean framework) in first-order logic with equality. In algebraic terms, this means solving equations in free monoids and related structures (as many of the constraints lead naturally to commutativity or other relations between the alphabet letters), as every string can be seen as an element over the generators of a finitely generated monoid or group.
Declaration of (no) AI usage
No AI tools were used for proving any results, making any conjectures or generating any examples.
No AI tools were used for any aspects of the writing or editing of this paper.
Acknowledgements
The first author benefited from the support provided by the Deutsche Forschungsgemeinschaft (DFG, German Research Foundation) under Germany’s Excellence Strategy – The Berlin Mathematics Research Center MATH+ (EXC-2046/1, EXC-2046/2, project ID: 390685689).
The research of the second and third-named authors was supported by the EPSRC Fellowship grant EP/V032003/1 ‘Algorithmic, topological and geometric aspects of infinite groups, monoids and inverse semigroups’.
Preliminaries
Let x = { X 1 , … , X m } \mathbf{x} = \{X_1,\ldots,X_m\} x = { X 1 , … , X m } be a set of variables, where m ≥ 1 m \ge1 m ≥ 1 . For a group G G G , a finite system of equations in G G G over the variables x \mathbf{x} x is a finite subset E E E of the free product G ∗ F ( x ) G * F(\mathbf{x}) G ∗ F ( x ) , where F ( x ) F(\mathbf{x}) F ( x ) is the free group on x \mathbf{x} x . If E = { w 1 , … , w n } E = \{w_1,\ldots,w_n\} E = { w 1 , … , w n } , then a solution to the system ( w 1 = 1 ) ∧ ⋯ ∧ ( w n = 1 ) (w_1 = 1) \wedge\cdots\wedge(w_n = 1) ( w 1 = 1 ) ∧ ⋯ ∧ ( w n = 1 ) is a homomorphism ϕ : G ∗ F ( x ) → G \phi: G * F(\mathbf{x}) \to G ϕ : G ∗ F ( x ) → G , such that ϕ ( w 1 ) = ⋯ = ϕ ( w n ) = 1 G \phi(w_1) = \cdots= \phi(w_n) = 1_G ϕ ( w 1 ) = ⋯ = ϕ ( w n ) = 1 G and ϕ ( g ) = g \phi(g) = g ϕ ( g ) = g for all g ∈ G g \in G g ∈ G . If E E E has a solution, then it is satisfiable.
For a group G G G , we say that systems of equations over G G G are decidable over G G G if there is an algorithm to determine whether any given system is satisfiable. The question of decidability of systems of equations in G G G is called the Diophantine Problem for G G G , and denoted D P ( G ) DP(G) D P ( G ) .
The Diophantine Problem with constraints
We can augment the Diophantine Problem for a group by requiring that the solutions belong to certain sets, which we call constraints (see [14 ] and [13 ] for more background). We start by defining formal language constraints.
Let Σ \Sigma Σ be a finite alphabet and let S = Σ ± 1 S = \Sigma^{\pm1} S = Σ ± 1 . Suppose G G G is a group generated by S S S , and let π : S ∗ → G \pi: S^* \to G π : S ∗ → G be the natural projection from the free monoid S ∗ S^* S ∗ generated by S S S to G G G , taking a word over the generators to the element it represents in the group. A language is regular if it is recognised by a finite state automaton, as is standard.
Definition 2.1.
(1) A subset L L L of G G G is recognisable if the full preimage π − 1 ( L ) \pi^{-1}(L) π − 1 ( L ) is a regular subset of S ∗ S^* S ∗ .
(2) A subset L L L of G G G is rational if L L L is the image π ( R ) \pi(R) π ( R ) of a regular subset R R R of S ∗ S^* S ∗ .
It follows immediately from the definition that recognisable subsets of G G G are rational.
Let E \mathcal{E} E be a system of equations on variables x = { X 1 , … , X k } \mathbf{x} = \{X_1,\ldots,X_k\} x = { X 1 , … , X k } in a group G G G . The Diophantine Problem with rational (resp. recognisable) constraints asks about the existence of solutions to E \mathcal{E} E , with some of the variables restricted to taking values in finitely many specified rational (resp. recognisable) sets. We write D P ( G , Rat ) \mathit{DP}(G,\operatorname{Rat}) DP ( G , Rat ) and D P ( G , Rec ) \mathit{DP}(G,\operatorname{Rec}) DP ( G , Rec ) for the two cases.
While there are many non-rational constraints of interest (see [10 ] ), we focus here on abelianisation constraints. For any group G G G , let ab : G → G a b \operatorname{ab}:G\to G^{\mathrm{ab}} ab : G → G ab be the natural abelianisation map to G a b = G / G ′ G^{\mathrm{ab}}=G/G' G ab = G / G ′ , that is, the quotient of G G G by its commutator subgroup. We write D P ( G , ab ) \mathit{DP}(G,\operatorname{ab}) DP ( G , ab ) for the D P \mathit{DP} DP where an abelian predicate is added, or equivalently, abelianisation constraints are imposed. A set of abelianisation constraints is a system Θ \Theta Θ of equations in the group G a b G^{\mathrm{ab}} G ab , and D P ( G , ab ) \mathit{DP}(G,\operatorname{ab}) DP ( G , ab ) asks whether a solution to E \mathcal{E} E exists such that the abelianisation of the solution satisfies the system Θ \Theta Θ in G a b G^{\mathrm{ab}} G ab .
Example 2.2. Let F ( A ) F(A) F ( A ) be the free group of rank 2 2 2 with basis A = { α , β } A=\{\alpha,\beta\} A = { α , β } and abelianisation ab : F ( A ) → Z 2 \operatorname{ab}:F(A)\to\mathbb{Z}^2 ab : F ( A ) → Z 2 . For the set of variables { X , Y , Z } \{X,Y,Z\} { X , Y , Z } consider the equation
X 2 α Y = Y Z − 2 α . X^2\alpha Y=YZ^{-2}\alpha. X 2 α Y = Y Z − 2 α . An instance of D P ( G , a b ) \mathit{DP}(G,\mathbf{ab}) DP ( G , ab ) would be to ask if there is a solution σ \sigma σ such that
a b ( σ ( X ) ) + a b ( σ ( Z ) ) = ( 0 , 0 ) . \mathbf{ab}(\sigma(X))+\mathbf{ab}(\sigma(Z))=(0,0). ab ( σ ( X )) + ab ( σ ( Z )) = ( 0 , 0 ) . The answer is ‘yes’, as the triple ( α β , α , α − 1 β − 1 ) (\alpha\beta,\alpha,\alpha^{-1}\beta^{-1}) ( α β , α , α − 1 β − 1 ) shows: σ 0 ( X ) = α β \sigma_0(X)=\alpha\beta σ 0 ( X ) = α β , σ 0 ( Y ) = α \sigma_0(Y)=\alpha σ 0 ( Y ) = α and σ 0 ( Z ) = ( β α ) − 1 \sigma_0(Z)=(\beta\alpha)^{-1} σ 0 ( Z ) = ( β α ) − 1 satisfies σ 0 ( X 2 α Y ) = σ 0 ( Y Z − 2 α ) \sigma_0(X^2\alpha Y)=\sigma_0(YZ^{-2}\alpha) σ 0 ( X 2 α Y ) = σ 0 ( Y Z − 2 α ) . Moreover, σ 0 \sigma_0 σ 0 satisfies a b ( σ 0 ( X ) ) = − a b ( σ 0 ( Z ) ) = ( 1 , 1 ) \mathbf{ab}(\sigma_0(X))=-\mathbf{ab}(\sigma_0(Z))=(1,1) ab ( σ 0 ( X )) = − ab ( σ 0 ( Z )) = ( 1 , 1 ) , so the abelianisation constraint holds.
A key notion associated to a system of equations is that of a D P ( G ) \mathit{DP}(G) DP ( G ) -definable set.
Definition 2.3. Let G G G be a group. A set D ⊂ G × ⋯ × G = G m D\subset G\times\cdots\times G=G^m D ⊂ G × ⋯ × G = G m is called D P ( G ) \mathit{DP}(G) DP ( G ) -definable, if there exists a system E D \mathcal{E}_D E D of equations with variables ( X 1 , … , X m , Y 1 , … , Y k ) = ( x , y ) (X_1,\ldots,X_m,Y_1,\ldots,Y_k)=(\mathbf{x},\mathbf{y}) ( X 1 , … , X m , Y 1 , … , Y k ) = ( x , y ) , and constants from G G G , satisfying the following: a tuple a ∈ G m \mathbf{a}\in G^m a ∈ G m is in D D D if and only if there exists b ∈ G k \mathbf{b}\in G^k b ∈ G k such that ( a , b ) (\mathbf{a},\mathbf{b}) ( a , b ) is a solution to the system E D \mathcal{E}_D E D . In this case E D \mathcal{E}_D E D is said to define D D D in G G G .
Example 2.4.
The most frequent type of D P ( G ) \mathit{DP}(G) DP ( G ) -definable set in a group G G G encountered in this paper will be the centraliser of an element g g g , that is, the set C G ( g ) = { h ∈ G ∣ g h = h g } C_G(g)=\{h\in G\mid gh=hg\} C G ( g ) = { h ∈ G ∣ g h = h g } . An element x ∈ G x\in G x ∈ G belongs to C G ( g ) C_G(g) C G ( g ) if and only if x x x is a solution to the equation X g = g X Xg=gX X g = g X .
Another classical example is the centre Z ( G ) = { g ∈ G ∣ g h = h g ∀ h ∈ G } Z(G)=\{g\in G\mid gh=hg\ \forall h\in G\} Z ( G ) = { g ∈ G ∣ g h = h g ∀ h ∈ G } of a group G G G generated by a finite set { g 1 , … , g n } \{g_1,\ldots,g_n\} { g 1 , … , g n } . Indeed, an element x ∈ G x\in G x ∈ G lies in Z ( G ) Z(G) Z ( G ) if and only if x x x satisfies the system of equations ( [ X , g 1 ] = 1 ) ∧ ⋯ ∧ ( [ X , g n ] = 1 ) ([X,g_1]=1)\land\cdots\land([X,g_n]=1) ([ X , g 1 ] = 1 ) ∧ ⋯ ∧ ([ X , g n ] = 1 ) .
Using D P ( G ) \mathit{DP}(G) DP ( G ) -definability one can interpret one algebraic structure into another in the standard model-theoretic way. We do not formalise this here, but refer the reader to Section 2.3 for the precise definitions. A common thread throughout this paper is to use interpretability (see [14 ] ) to encode addition and multiplication in Z \mathbb{Z} Z into the D P ( G , ab ) \mathit{DP}(G,\operatorname{ab}) DP ( G , ab ) for some group G G G , and by the undecidability of Hilbert’s 10th Problem, get the same result for G G G .
Existential theory
For various combination results, we will use the existential theory in a group G G G . The existential theory is a generalisation of the Diophantine Problem, to allow all first-order sentences built from existential quantifiers, the constants in G G G together with the logical operators ∧ \land ∧ (‘and’), ∨ \lor ∨ (‘or’) and ¬ \neg ¬ (‘not’). De Morgan’s laws allow one to factor all of the or operators to the front of the sentence, so all such sentences are equivalent to finite disjunctions of systems of equations and inequations in our group (where by an inequation, we mean an expression of the form w ≠ 1 w\ne1 w = 1 where w ∈ F ( x ) ∗ G w\in F(\mathbf{x})*G w ∈ F ( x ) ∗ G ).
EDT0L solutions
A fruitful line of research over the last ten years has been to describe the solutions to systems of equations in groups in terms of formal languages. The class of EDT0L languages has proved particularly suitable, as it describes solutions in many important classes of groups, including hyperbolic groups [12 ] , virtually direct products of hyperbolic groups [35 ] and single equations in one variable in the Heisenberg group [36 ] . We do not need the definition of this class of languages here as we rely on combination results from known characterisations, and refer the reader to [16 ] for definitions and an overview of the area.
When passing to direct products, the decidability of the Diophantine Problem with rational constraints is not closed, with F 2 × Z F_{2} \times\mathbb{Z} F 2 × Z being a counterexample [33 ] and F 2 × F 2 F_{2} \times F_{2} F 2 × F 2 even having an undecidable subgroup membership problem [44 ] . If the rational constraints are forced to be fully contained in one of the factors, then one can obtain positive results in this direction.
Proposition 2.5. Let G 1 G_{1} G 1 and G 2 G_{2} G 2 be groups. Suppose that D P ( G 1 , Rat ) \mathcal{DP}(G_{1},\operatorname{Rat}) DP ( G 1 , Rat ) and D P ( G 2 ) \mathcal{DP}(G_{2}) DP ( G 2 ) are decidable (EDT0L). Then the Diophantine Problem with rational constraints fully contained in G 1 × { 1 } G_{1} \times\{1\} G 1 × { 1 } is decidable (EDT0L) in G 1 × G 2 G_{1} \times G_{2} G 1 × G 2 .
Proof. Let E \mathcal{E} E be a system of equations in G 1 × G 2 G_{1} \times G_{2} G 1 × G 2 , with set of solutions S S S . Let E 1 \mathcal{E}_{1} E 1 and E 2 \mathcal{E}_{2} E 2 be the projections of E \mathcal{E} E onto G 1 G_{1} G 1 and G 2 G_{2} G 2 , respectively, with sets of solutions S 1 S_{1} S 1 and S 2 S_{2} S 2 , respectively. Then
S = { ( x , y ) ∣ x ∈ S 1 , y ∈ S 2 } . S = \{(x,y) \mid x \in S_{1}, y \in S_{2}\}. S = {( x , y ) ∣ x ∈ S 1 , y ∈ S 2 } .
So if we add rational constraints to E \mathcal{E} E that are fully contained in G 1 G_{1} G 1 , under the projections these just add rational constraints to E 1 \mathcal{E}_{1} E 1 and leave E 2 \mathcal{E}_{2} E 2 unchanged, and the above equality still holds. In particular, S S S is empty if and only if S 1 = ∅ S_{1} = \varnothing S 1 = ∅ or S 2 = ∅ S_{2} = \varnothing S 2 = ∅ , which we can decide using D P ( G 1 , Rat ) \mathcal{DP}(G_{1},\operatorname{Rat}) DP ( G 1 , Rat ) and D P ( G 2 ) \mathcal{DP}(G_{2}) DP ( G 2 ) , respectively.
For the claim about EDT0L solutions, we can apply [35 Proposition 4.10] . This does not cover the rational constraints, but it does show that if S 1 S_{1} S 1 and S 2 S_{2} S 2 correspond to EDT0L solution languages, then so does S S S , with respect to the natural inherited normal form of direct products. Thus even with the addition of rational constraints to S 1 S_{1} S 1 , the proof of [35 Proposition 4.10] will still imply that S S S corresponds to an EDT0L solution language. □
Same groups, different looks
The focus of this paper are free-by-cyclic groups, so semidirect products of the form F n ⋊ ϕ Z F_{n} \rtimes_{\phi} \mathbb{Z} F n ⋊ ϕ Z , where ϕ \phi ϕ is an automorphism of F n F_{n} F n , with n ≥ 1 n \ge1 n ≥ 1 .
In particular, we consider free-by-cyclic groups with non-trivial centre. Baumslag and Taylor [5 ] proved that each one-relator group with non-trivial centre is { f.g. free } \{\text{f.g. free}\} { f.g. free } -by-cyclic F n ⋊ ϕ Z F_{n} \rtimes_{\phi} \mathbb{Z} F n ⋊ ϕ Z for some n ≥ 1 n \ge1 n ≥ 1 . They also proved that there is an algorithm that takes any one-relator group as input and decides whether that group has a non-trivial centre.
Another relevant class of groups are the Generalised Baumslag-Solitar (GBS) groups. These are the fundamental groups of finite graphs of infinite cyclic groups [38 ] . We assume familiarity with Bass-Serre theory and define each such group based on a graph of groups Γ ( V , E ) \Gamma(V,E) Γ ( V , E ) , where Γ \Gamma Γ is a connected graph with vertex set V = V ( Γ ) V = V(\Gamma) V = V ( Γ ) and edge set E = E ( Γ ) E = E(\Gamma) E = E ( Γ ) , and an infinite cyclic group is attached to every vertex and edge. To every edge e ∈ E e \in E e ∈ E we associate a start-vertex s ( e ) s(e) s ( e ) and terminus t ( e ) t(e) t ( e ) , an involution e ↦ e ˉ e \mapsto\bar{e} e ↦ e ˉ , and local groups G e = G e ˉ G_{e} = G_{\bar{e}} G e = G e ˉ and G s ( e ) , G t ( e ) G_{s(e)}, G_{t(e)} G s ( e ) , G t ( e ) (all isomorphic to Z \mathbb{Z} Z ). Furthermore, there are inclusion maps ι e , 1 : G e → G s ( e ) \iota_{e,1}\colon G_{e} \to G_{s(e)} ι e , 1 : G e → G s ( e ) and ι e , 2 : G e → G t ( e ) \iota_{e,2}\colon G_{e} \to G_{t(e)} ι e , 2 : G e → G t ( e ) given by multiplication by some integers p e p_{e} p e and q e q_{e} q e .
It turns out that GBS groups with non-trivial centre are free-by-cyclic:
Proposition 2.6 ([38 Proposition 4.1] ). For any group G G G the following are equivalent:
G G G is a GBS group with a non-trivial centre;
there exists n ≥ 1 n \ge1 n ≥ 1 and ϕ ∈ Out ( F n ) \phi\in\operatorname{Out}(F_{n}) ϕ ∈ Out ( F n ) of finite order such that G = F n ⋊ ϕ Z G = F_{n} \rtimes_{\phi} \mathbb{Z} G = F n ⋊ ϕ Z .
In fact, it follows from [38 ] that the classes of groups (ii), (iii) and (iv) listed in the Introduction are all equal to each other.
(ii) generalised Baumslag-Solitar (GBS) groups with non-trivial centre (GBS);
(iii) [f.g. free]-by-cyclic groups with non-trivial centre (FbC); (iv) free-by-cyclic groups of the form F ⋊ ϕ Z F \rtimes_{\phi} \mathbb{Z} F ⋊ ϕ Z for some finitely generated free group F F F and some automorphism ϕ ∈ Aut ( F ) \phi\in\operatorname{Aut}(F) ϕ ∈ Aut ( F ) that has finite order in Out ( F ) \operatorname{Out}(F) Out ( F ) (FbZf);
Thus if G G G is a GBS group with a non-trivial centre then G G G is virtually F r × Z F_r \times\mathbb{Z} F r × Z , r ≥ 1 r \ge1 r ≥ 1 , by Lemma 2.7 , which is a standard result. Therefore free-by-cyclic groups with acting automorphism ϕ \phi ϕ of finite order in Out ( − ) \operatorname{Out}(-) Out ( − ) (FbZf) are virtually direct products, where the product has the form F × Z F \times\mathbb{Z} F × Z (vFZ).
Lemma 2.7. Let G G G be any group and let ϕ \phi ϕ be an automorphism of finite order in Out ( G ) \operatorname{Out}(G) Out ( G ) . The group G ⋊ ϕ Z G \rtimes_{\phi} \mathbb{Z} G ⋊ ϕ Z contains G × Z G \times\mathbb{Z} G × Z with finite index.
Example 2.8. The classes of groups (ii)-(iii)-(iv) of free-by-cyclic groups with centre (FbC, equivalently GBS or FbZf) do not coincide with the class (v) of virtually F × Z F \times\mathbb{Z} F × Z for some finitely generated free group F F F , as free-by-cyclic groups are torsion-free, whilst virtually F × Z F \times\mathbb{Z} F × Z groups need not be.
The main protagonists of the paper have yet another characterisation. They are central extensions of hyperbolic groups (even stronger, free-by-cyclic groups with centre are central extensions of virtually free groups), and so by work of Liang have decidable Diophantine Problem [39 ] .
Computable translations between (i) – (v)
We have from [37 ] that [f.g. free]-by-cyclic groups with centre are in fact GBS with centre, which admit a presentation that we wish to work with. However, when translating between these different isomorphic presentations, we require the process to be effective, so that our algorithm can perform them. The proof is not difficult; we simply iterate through all possible Tietze transformations.
Lemma 2.9. There is an algorithm that takes as input any [f.g. free]-by-cyclic presentation for a group G G G with non-trivial centre and a virtually cyclic abelianisation and outputs a GBS presentation defining G G G of the form
⟨ { a v ∣ v ∈ V ( T ) } ∣ { a s ( e ) p e = a t ( e ) q e ∣ e ∈ E ( T ) } ⟩ , \left\langle\{a_v \mid v \in V(T)\} \mathrel{\big|} \{a_{s(e)}^{p_e} = a_{t(e)}^{q_e} \mid e \in E(T)\}\right\rangle, ⟨ { a v ∣ v ∈ V ( T )} { a s ( e ) p e = a t ( e ) q e ∣ e ∈ E ( T )} ⟩ , for some finite rooted tree T T T and some p e , q e ∈ Z > 0 p_e,q_e \in\mathbb{Z}_{>0} p e , q e ∈ Z > 0 for all e ∈ E ( T ) e \in E(T) e ∈ E ( T ) .
Proof. Let G G G be a free-by-cyclic group with centre and a virtually cyclic abelianisation. By [37 Theorem 1.1(1)] there is a finite rooted tree T T T such that G G G admits a presentation of the form
⟨ { a v ∣ v ∈ V ( T ) } ∣ { a s ( e ) p e = a t ( e ) q e ∣ e ∈ E ( T ) } ⟩ , \left\langle\{a_v \mid v \in V(T)\} \mathrel{\big|} \{a_{s(e)}^{p_e} = a_{t(e)}^{q_e} \mid e \in E(T)\}\right\rangle, ⟨ { a v ∣ v ∈ V ( T )} { a s ( e ) p e = a t ( e ) q e ∣ e ∈ E ( T )} ⟩ ,
for some p e , q e ∈ Z > 0 p_e,q_e \in\mathbb{Z}_{>0} p e , q e ∈ Z > 0 for all e ∈ E ( T ) e \in E(T) e ∈ E ( T ) , satisfying the conditions in the statement of the lemma, that defines G G G . The set of all finite presentations of G G G can be recursively enumerated by starting with the presentation ⟨ A ∣ r = 1 ⟩ \langle A \mid r = 1\rangle ⟨ A ∣ r = 1 ⟩ and repeatedly applying Tietze transformations. So the algorithm proceeds by listing the finite presentations of G G G in this way and at each step checking whether any of the finite presentations listed thus has the GBS form above. Since we know at the outset that G G G admits some presentation of this form this algorithm will terminate at the point where the finite list of presentations of G G G we have computed contains at least one presentation of the correct form. □
The argument used in the proof of Lemma 2.9 is quite general and can be used to establish the following result.
Lemma 2.10. There is an algorithm that takes as input any non-cyclic one-relator group G G G with non-trivial centre and outputs a [f.g. free]-by-cyclic F n ⋊ ϕ Z F_n \rtimes_{\phi} \mathbb{Z} F n ⋊ ϕ Z presentation defining G G G , that is, a finite presentation of the form
⟨ A , t ∣ t a t − 1 = w a ( a ∈ A ) ⟩ (1) \langle A,t \mid tat^{-1} = w_a \ (a \in A)\rangle \tag*{(1)} ⟨ A , t ∣ t a t − 1 = w a ( a ∈ A )⟩ (1) where each w a ∈ F A w_a \in F_A w a ∈ F A and the map a ↦ w a a \mapsto w_a a ↦ w a ( a ∈ A ) (a \in A) ( a ∈ A ) induces an automorphism ϕ \phi ϕ of the free group F A F_A F A .
Proof. There are classical algorithms due to Nielsen and Whitehead (see [42 ] ) that take any mapping θ : A → F A \theta\colon A \to F_A θ : A → F A (where A A A is a finite set) as input and determine whether or not θ \theta θ extends to an automorphism of F A F_A F A . This implies that there is an algorithm that takes any finite group presentation ⟨ B ∣ Q ⟩ \langle B \mid Q\rangle ⟨ B ∣ Q ⟩ and decides whether or not it has the form (1) given in the statement of the lemma. We can thus apply exactly the same argument from the proof of Theorem 2.9. □
Exponent sums
A useful concept when dealing with abelianisations of groups is that of exponent sums. This simply considers projections of the group onto maximal copies of Z \mathbb{Z} Z that are present in the abelianisation. We typically consider exponent-sums of generators, although the definition is more general.
Definition 2.11. Let G G G be a group and let a ∈ G a \in G a ∈ G be such that ab ( a ) ≅ Z \operatorname{ab}(a) \cong\mathbb{Z} ab ( a ) ≅ Z and ab ( G ) = ⟨ ab ( a ) ⟩ ⊕ K \operatorname{ab}(G) = \langle\operatorname{ab}(a) \rangle\oplus K ab ( G ) = ⟨ ab ( a )⟩ ⊕ K , for some group K K K ; that is, ⟨ ab ( a ) ⟩ \langle\operatorname{ab}(a) \rangle ⟨ ab ( a )⟩ is a maximal copy of Z \mathbb{Z} Z in ab ( G ) \operatorname{ab}(G) ab ( G ) . The exponent-sum of g ∈ G g \in G g ∈ G with respect to a a a is denoted expsum a ( g ) \operatorname{expsum}_{a}(g) expsum a ( g ) and is defined to be the image of g g g under the epimorphism from G G G to Z \mathbb{Z} Z defined by composing the map ab \operatorname{ab} ab with the projection onto ⟨ ab ( a ) ⟩ \langle\operatorname{ab}(a) \rangle ⟨ ab ( a )⟩ .
Decidability for free-by-cyclic groups with non-trivial centre and virtually cyclic abelianisation
In this section we show another facet of free-by-cyclic groups with non-trivial centre by embedding them into direct products, as in Proposition 3.2 . As already observed, the class of one-relator groups with non-trivial centre is contained in the class of [f.g. free]-by-cyclic groups with non-trivial centre. In Theorem 1.2 we prove that D P ( G , ab ) DP(G,\operatorname{ab}) D P ( G , ab ) is decidable in a free-by-cyclic G G G if both the centre and the abelianisation satisfy the hypothesis. The proof is similar to proving the decidability of the ‘plain’ Diophantine Problem exhibited in [15 ] ; one first embeds the group as a finite-index subgroup inside a direct product of hyperbolic groups, and then notices that this direct product has a decidable Diophantine Problem with recognisable constraints. In our case, the hyperbolic groups are a virtually free group V V V and Z \mathbb{Z} Z and the commutator subgroup is a a finitely generated subgroup of V V V . This setting allows us to apply Theorem 2.5, noting that the Diophantine Problem in a virtually free group with rational constraints is decidable [20 ] and has EDT0L solutions [23 ] , to complete the proof.
In order to prove that some of these facts occur, we first move to the world of GBS groups based on trees. We require some notation to work with these groups.
Notation 3.1. If T T T is a rooted tree, we define an order on T T T (both on edges and vertices), where the root is minimal, and two items are comparable if they both lie on a minimal path from the root, with the ‘closer’ one being smaller in this partial order. Further, if e ∈ E ( T ) e \in E(T) e ∈ E ( T ) , then we define s ( e ) s(e) s ( e ) and t ( e ) t(e) t ( e ) to be the two ends of e e e such that s ( e ) < t ( e ) s(e) < t(e) s ( e ) < t ( e ) (note that s ( e ) ≠ t ( e ) s(e) \ne t(e) s ( e ) = t ( e ) since T T T is a tree).
Proposition 3.2. Let G G G be a [f.g. free]-by-cyclic group with non-trivial centre and virtually cyclic abelianisation.
Then G G G embeds as a finite index subgroup in V × Z V \times\mathbb{Z} V × Z for some virtually free group V V V . Moreover, V × Z V \times\mathbb{Z} V × Z and the embedding of G G G into V × Z V \times\mathbb{Z} V × Z are computable from the presentation for G G G .
To prove this proposition, we use the fact that if a GBS group has non-trivial centre and virtually cyclic abelianisation, then the defining graph of the GBS group is a tree. This follows from [37 Theorem 1.1 (1)] .
Proof. The group G G G is a GBS group, as seen in § 4.4 . Moreover, by [37 ] Theorem 1.1 (1) it is a GBS based on a tree, so there is a rooted tree T T T with root o o o such that G G G admits the presentation
⟨ { a v ∣ v ∈ V ( T ) } ∣ { a s ( e ) p e = a t ( e ) q e ∣ e ∈ E ( T ) } ⟩ \left\langle\{a_v \mid v \in V(T)\} \mathrel{\big|} \{a_{s(e)}^{p_e} = a_{t(e)}^{q_e} \mid e \in E(T)\}\right\rangle ⟨ { a v ∣ v ∈ V ( T )} { a s ( e ) p e = a t ( e ) q e ∣ e ∈ E ( T )} ⟩
for some p e , q e ∈ Z > 0 p_e,q_e \in\mathbb{Z}_{>0} p e , q e ∈ Z > 0 for all e ∈ E ( T ) e \in E(T) e ∈ E ( T ) . In addition, Theorem 2.9 tells us that this presentation is computable from a presentation for G G G .
Note that for all v ∈ V ( T ) v \in V(T) v ∈ V ( T ) , a o ∏ e ∈ E ( T ) p e = G a v n v a_o^{\prod_{e \in E(T)}p_e} = {}_G a_v^{n_v} a o ∏ e ∈ E ( T ) p e = G a v n v , for some n v ∈ Z n_v \in\mathbb{Z} n v ∈ Z . Thus a o ∏ e ∈ E ( T ) p e ∈ Z ( G ) a_o^{\prod_{e \in E(T)}p_e} \in Z(G) a o ∏ e ∈ E ( T ) p e ∈ Z ( G ) , and so ⟨ a o ∏ e ∈ E ( T ) p e ⟩ ⊴ G \langle a_o^{\prod_{e \in E(T)}p_e} \rangle\trianglelefteq G ⟨ a o ∏ e ∈ E ( T ) p e ⟩ ⊴ G . Set V = G / ⟨ a o ∏ e ∈ E ( T ) p e ⟩ V = G/\langle a_o^{\prod_{e \in E(T)}p_e} \rangle V = G / ⟨ a o ∏ e ∈ E ( T ) p e ⟩ , and note that a presentation for V V V is computable from the GBS presentation for G G G . We will show that V V V is virtually free, by showing that it is the fundamental group of a finite graph of groups, with finite vertex and edge groups. Such groups are always virtually free. Since for all v ∈ V ( T ) v \in V(T) v ∈ V ( T ) , we have a 0 ∏ e ∈ E ( T ) p e = G a v n v a_0^{\prod_{e\in E(T)}p_e} =_G a_v^{n_v} a 0 ∏ e ∈ E ( T ) p e = G a v n v for some n v ∈ Z n_v \in\mathbb{Z} n v ∈ Z , so the subgroup ⟨ a v ⟩ \langle a_v\rangle ⟨ a v ⟩ has order at most n v n_v n v in V V V , and thus we can express V V V using the following presentation, where we let n 0 : = ∏ e ∈ E ( T ) p e n_0 := \prod_{e\in E(T)}p_e n 0 := ∏ e ∈ E ( T ) p e . We have replaced a v a_v a v with x v x_v x v to avoid confusion between V V V and G G G .
⟨ { x v ∣ v ∈ V ( T ) } ∣ { x s ( e ) p e = x t ( e ) q e ∣ e ∈ E } ∪ { x v n v ∣ v ∈ V ( T ) } ⟩ . \left\langle\{x_v \mid v \in V(T)\} \mathrel{\big|} \{x_{s(e)}^{p_e}=x_{t(e)}^{q_e} \mid e \in E\}\cup\{x_v^{n_v}\mid v\in V(T)\}\right\rangle. ⟨ { x v ∣ v ∈ V ( T )} { x s ( e ) p e = x t ( e ) q e ∣ e ∈ E } ∪ { x v n v ∣ v ∈ V ( T )} ⟩ .
This presentation is just that of the fundamental group of a graph of groups with underlying graph T T T , and where the set of vertex groups is { ⟨ x v ∣ x v n v = 1 ⟩ ∣ v ∈ V ( T ) } \{\langle x_v\mid x_v^{n_v}=1\rangle\mid v\in V(T)\} {⟨ x v ∣ x v n v = 1 ⟩ ∣ v ∈ V ( T )} . This is a finite collection of finite groups, and so the fundamental group, which is V V V , must therefore be virtually free.
We next show that G G G embeds with finite index in V × ⟨ d ∣ ⟩ ≅ V × Z V\times\langle d\mid\ \rangle\cong V\times\mathbb{Z} V × ⟨ d ∣ ⟩ ≅ V × Z , and show that the embedding is computable. To do so, we must first define Q = ⟨ t ∣ t ∏ e ∈ E ( T ) p e q e ⟩ Q=\langle t\mid t^{\prod_{e\in E(T)}p_eq_e}\rangle Q = ⟨ t ∣ t ∏ e ∈ E ( T ) p e q e ⟩ and maps σ : V → Q \sigma:V\to Q σ : V → Q and τ : ⟨ d ⟩ → Q \tau:\langle d\rangle\to Q τ : ⟨ d ⟩ → Q by σ ( x v ) = t ∏ e ∈ E ( T ) , e < v p e ⋅ ∏ e ∈ E ( T ) , e ≮ v q e \sigma(x_v)=t^{\prod_{e\in E(T),e<v}p_e\cdot\prod_{e\in E(T),e\not<v}q_e} σ ( x v ) = t ∏ e ∈ E ( T ) , e < v p e ⋅ ∏ e ∈ E ( T ) , e < v q e and τ ( d ) = t \tau(d)=t τ ( d ) = t . Next define S ≤ V × ⟨ d ∣ ⟩ S\leq V\times\langle d\mid\ \rangle S ≤ V × ⟨ d ∣ ⟩ by S = { ( v , d p ) ∈ V × ⟨ d ∣ ⟩ ∣ σ ( v ) = τ ( d p ) } S=\{(v,d^p)\in V\times\langle d\mid\ \rangle\mid\sigma(v)=\tau(d^p)\} S = {( v , d p ) ∈ V × ⟨ d ∣ ⟩ ∣ σ ( v ) = τ ( d p )} . Finally, define ψ : G → V × ⟨ d ∣ ⟩ \psi:G\to V\times\langle d\mid\ \rangle ψ : G → V × ⟨ d ∣ ⟩ by ψ ( a v ) = ( x v , d ∏ e ∈ E ( T ) , e < v p e ⋅ ∏ e ∈ E ( T ) , e ≮ v q e ) \psi(a_v)=(x_v,d^{\prod_{e\in E(T),e<v}p_e\cdot\prod_{e\in E(T),e\not<v}q_e}) ψ ( a v ) = ( x v , d ∏ e ∈ E ( T ) , e < v p e ⋅ ∏ e ∈ E ( T ) , e < v q e ) , and note that ψ \psi ψ is computable from the generalised Baumslag–Solitar presentation for G G G . We shall show that ψ \psi ψ is a homomorphism with im ψ = S \operatorname{im}\psi=S im ψ = S , leaving it remaining to show that S S S has finite index in V × ⟨ d ∣ ⟩ V\times\langle d\mid\ \rangle V × ⟨ d ∣ ⟩ .
We begin by showing that ψ \psi ψ is a homomorphism, which we do by showing that it satisfies the relations of G G G . Let f ∈ E ( T ) f\in E(T) f ∈ E ( T ) . Then
( ψ ( a s ( f ) ) ) p f = V ( x s ( f ) p f , d p f ⋅ ∏ e ∈ E ( T ) , e < s ( f ) p e ⋅ ∏ e ∈ E ( T ) , e ≮ s ( f ) q e ) = V ( x t ( f ) q f , d q f ⋅ ∏ e ∈ E ( T ) , e < t ( f ) p e ⋅ ∏ e ∈ E ( T ) , e ≮ t ( f ) q e ) = ( ψ ( a t ( e ) ) ) q e . \begin{aligned}
\left(\psi(a_{s(f)})\right)^{p_f}
={}_{V}\left(x_{s(f)}^{p_f},d^{p_f\cdot\prod_{e\in E(T),e<s(f)}p_e\cdot\prod_{e\in E(T),e\not<s(f)}q_e}\right) \\
&={}_{V}\left(x_{t(f)}^{q_f},d^{q_f\cdot\prod_{e\in E(T),e<t(f)}p_e\cdot\prod_{e\in E(T),e\not<t(f)}q_e}\right)
=\left(\psi(a_{t(e)})\right)^{q_e}.
\end{aligned} ( ψ ( a s ( f ) ) ) p f = V ( x s ( f ) p f , d p f ⋅ ∏ e ∈ E ( T ) , e < s ( f ) p e ⋅ ∏ e ∈ E ( T ) , e < s ( f ) q e ) = V ( x t ( f ) q f , d q f ⋅ ∏ e ∈ E ( T ) , e < t ( f ) p e ⋅ ∏ e ∈ E ( T ) , e < t ( f ) q e ) = ( ψ ( a t ( e ) ) ) q e .
Thus ψ \psi ψ is a homomorphism.
We next show that im ψ ⊆ S \operatorname{im}\psi\subseteq S im ψ ⊆ S . Since S S S is a subgroup, it suffices to show that ψ ( a v ) ∈ S \psi(a_v)\in S ψ ( a v ) ∈ S for all v ∈ V ( T ) v\in V(T) v ∈ V ( T ) . So let v ∈ V ( T ) v\in V(T) v ∈ V ( T ) . Then ψ ( a v ) = ( x v , d ∏ e ∈ E ( T ) , e < v p e ⋅ ∏ e ∈ E ( T ) , e ≮ v q e ) \psi(a_v)=(x_v,d^{\prod_{e\in E(T),e<v}p_e\cdot\prod_{e\in E(T),e\not<v}q_e}) ψ ( a v ) = ( x v , d ∏ e ∈ E ( T ) , e < v p e ⋅ ∏ e ∈ E ( T ) , e < v q e ) . In addition, σ ( x v ) = t ∏ e ∈ E ( T ) , e < v p e ⋅ ∏ e ∈ E ( T ) , e ≮ v q e = τ ( d ∏ e ∈ E ( T ) , e < v p e ⋅ ∏ e ∈ E ( T ) , e ≮ v q e ) \sigma(x_v)=t^{\prod_{e\in E(T),e<v}p_e\cdot\prod_{e\in E(T),e\not<v}q_e}=\tau(d^{\prod_{e\in E(T),e<v}p_e\cdot\prod_{e\in E(T),e\not<v}q_e}) σ ( x v ) = t ∏ e ∈ E ( T ) , e < v p e ⋅ ∏ e ∈ E ( T ) , e < v q e = τ ( d ∏ e ∈ E ( T ) , e < v p e ⋅ ∏ e ∈ E ( T ) , e < v q e ) . Thus ψ ( a v ) ∈ S \psi(a_v)\in S ψ ( a v ) ∈ S , and im ψ ⊆ S \operatorname{im}\psi\subseteq S im ψ ⊆ S .
To show im ψ = S \operatorname{im}\psi=S im ψ = S , it thus suffices to show that S ⊆ im ψ S\subseteq\operatorname{im}\psi S ⊆ im ψ . So let ( h , d p ) ∈ S (h,d^p)\in S ( h , d p ) ∈ S . Let f : G → V f:G\to V f : G → V be the natural quotient map, and note that ψ \psi ψ maps an element g ∈ G g\in G g ∈ G to ( f ( g ) , d q ) (f(g),d^q) ( f ( g ) , d q ) , for some q ∈ Z q\in\mathbb{Z} q ∈ Z . Since f f f is surjective, we have that there exists g ∈ G g\in G g ∈ G such that ψ ( g ) = ( h , d q ) \psi(g)=(h,d^q) ψ ( g ) = ( h , d q ) , for some q ∈ Z q\in\mathbb{Z} q ∈ Z . We next show that p ≡ q ( m o d ∏ e ∈ E ( T ) p e q e ) p\equiv q\pmod{\prod_{e\in E(T)}p_eq_e} p ≡ q ( mod ∏ e ∈ E ( T ) p e q e ) . Since ( h , d p ) , ( h , d q ) ∈ S (h,d^p),(h,d^q)\in S ( h , d p ) , ( h , d q ) ∈ S , we have that σ ( h ) = Q τ ( d p ) = Q τ ( d q ) \sigma(h)={}_Q\tau(d^p)={}_Q\tau(d^q) σ ( h ) = Q τ ( d p ) = Q τ ( d q ) . Thus t p = Q t q t^p={}_Qt^q t p = Q t q , and so p ≡ q ( m o d ∏ e ∈ E ( T ) p e q e ) p\equiv q\pmod{\prod_{e\in E(T)}p_eq_e} p ≡ q ( mod ∏ e ∈ E ( T ) p e q e ) . It remains to find an element k ∈ G k\in G k ∈ G such that ψ ( k ) = ( 1 , d p − q ) \psi(k)=(1,d^{p-q}) ψ ( k ) = ( 1 , d p − q ) . Since p − q ≡ 0 ( m o d ∏ e ∈ E ( T ) p e q e ) p-q\equiv0\pmod{\prod_{e\in E(T)}p_eq_e} p − q ≡ 0 ( mod ∏ e ∈ E ( T ) p e q e ) , we have that x 0 p − q ∏ e ∈ E ( T ) q e = V 1 x_0^{\frac{p-q}{\prod_{e\in E(T)}q_e}}={}_V1 x 0 ∏ e ∈ E ( T ) q e p − q = V 1 , and so
ψ ( a 0 p − q ∏ e ∈ E ( T ) q e ) = V × ⟨ d ∣ ⟩ ( x 0 p − q ∏ e ∈ E ( T ) q e , d ( p − q ) ⋅ ∏ e ∈ E ( T ) , e < 0 p e ∏ e ∈ E ( T ) , e ≮ 0 q e ∏ e ∈ E ( T ) q e ) = V × ⟨ d ∣ ⟩ ( 1 , d ( p − q ) ⋅ ∏ e ∈ E ( T ) q e ∏ e ∈ E ( T ) q e ) = V × ⟨ d ∣ ⟩ ( 1 , d p − q ) . \begin{aligned}
\psi\left(a_0^{\frac{p-q}{\prod_{e\in E(T)}q_e}}\right)
={}_{V\times\langle d\mid\ \rangle}
\left(x_0^{\frac{p-q}{\prod_{e\in E(T)}q_e}},d^{\frac{(p-q)\cdot\prod_{e\in E(T),e<0}p_e\prod_{e\in E(T),e\not<0}q_e}{\prod_{e\in E(T)}q_e}}\right) \\
&={}_{V\times\langle d\mid\ \rangle}
\left(1,d^{\frac{(p-q)\cdot\prod_{e\in E(T)}q_e}{\prod_{e\in E(T)}q_e}}\right)
={}_{V\times\langle d\mid\ \rangle}(1,d^{p-q}).
\end{aligned} ψ ( a 0 ∏ e ∈ E ( T ) q e p − q ) = V × ⟨ d ∣ ⟩ ( x 0 ∏ e ∈ E ( T ) q e p − q , d ∏ e ∈ E ( T ) q e ( p − q ) ⋅ ∏ e ∈ E ( T ) , e < 0 p e ∏ e ∈ E ( T ) , e < 0 q e ) = V × ⟨ d ∣ ⟩ ( 1 , d ∏ e ∈ E ( T ) q e ( p − q ) ⋅ ∏ e ∈ E ( T ) q e ) = V × ⟨ d ∣ ⟩ ( 1 , d p − q ) .
Thus ψ ( g a 0 p − q ∏ e ∈ E ( T ) q e ) = V × ⟨ d ∣ ⟩ ( h , d q ) ( 1 , d p − q ) = V × ⟨ d ∣ ⟩ ( h , d p ) \psi\left(ga_0^{\frac{p-q}{\prod_{e\in E(T)}q_e}}\right)={}_{V\times\langle d\mid\ \rangle}(h,d^q)(1,d^{p-q})={}_{V\times\langle d\mid\ \rangle}(h,d^p) ψ ( g a 0 ∏ e ∈ E ( T ) q e p − q ) = V × ⟨ d ∣ ⟩ ( h , d q ) ( 1 , d p − q ) = V × ⟨ d ∣ ⟩ ( h , d p ) . We can conclude that im ψ = S \operatorname{im}\psi=S im ψ = S .
To complete the proofs of our claims about ψ \psi ψ , it remains to show that ψ \psi ψ is injective. Let g ∈ ker ψ g\in\ker\psi g ∈ ker ψ . Since ψ \psi ψ maps g g g to 1 1 1 in the V V V -coordinate, we have that g ∈ ker f = ⟨ a 0 n 0 ⟩ g\in\ker f=\langle a_0^{n_0}\rangle g ∈ ker f = ⟨ a 0 n 0 ⟩ , and so g = a 0 p n 0 g=a_0^{pn_0} g = a 0 p n 0 for some p ∈ Z p\in\mathbb{Z} p ∈ Z . Thus ψ ( g ) = ( 1 , d p n 0 ∏ e ∈ E ( T ) q e ) \psi(g)=(1,d^{pn_0\prod_{e\in E(T)}q_e}) ψ ( g ) = ( 1 , d p n 0 ∏ e ∈ E ( T ) q e ) . As n 0 ≠ 0 n_0\ne0 n 0 = 0 and q e ≠ 0 q_e\ne0 q e = 0 for all e ∈ E ( T ) e\in E(T) e ∈ E ( T ) , it thus follows that equating the second coordinate in the expression for ψ ( g ) \psi(g) ψ ( g ) to 1 1 1 implies that p = 0 p=0 p = 0 . Thus g = 1 g=1 g = 1 and ψ \psi ψ is injective.
Since ψ : G → V × ⟨ d ∣ ⟩ \psi:G\to V\times\langle d\mid\ \rangle ψ : G → V × ⟨ d ∣ ⟩ , with im ψ = S \operatorname{im}\psi=S im ψ = S , we have that G ≅ S G\cong S G ≅ S . Thus to complete the proof, it remains to show that [ V × ⟨ d ∣ ⟩ : S ] < ∞ [V\times\langle d\mid\ \rangle:S]<\infty [ V × ⟨ d ∣ ⟩ : S ] < ∞ . Define ϕ : V × ⟨ d ∣ ⟩ → Q × Q \phi:V\times\langle d\mid\ \rangle\to Q\times Q ϕ : V × ⟨ d ∣ ⟩ → Q × Q by ϕ ( h , d p ) = ( σ ( h ) , τ ( d p ) ) \phi(h,d^p)=\bigl(\sigma(h),\tau(d^p)\bigr) ϕ ( h , d p ) = ( σ ( h ) , τ ( d p ) ) . Let ( h , d p ) ∈ ker ϕ (h,d^p)\in\ker\phi ( h , d p ) ∈ ker ϕ . Then σ ( h ) = Q 1 = Q τ ( d p ) \sigma(h)={}_Q1={}_Q\tau(d^p) σ ( h ) = Q 1 = Q τ ( d p ) , and so ( h , d p ) ∈ S (h,d^p)\in S ( h , d p ) ∈ S . Thus ker ϕ ⊆ S \ker\phi\subseteq S ker ϕ ⊆ S , and so [ G : S ] ≤ [ G : ker ϕ ] < ∞ [G:S]\leq[G:\ker\phi]<\infty [ G : S ] ≤ [ G : ker ϕ ] < ∞ . ∎
It is not difficult to show that the commutator subgroups of our groups are indeed finitely generated, and thus rational. We include the short proof below for completeness.
Lemma 3.3. Let G G G be a [f.g. free]-by-cyclic group with centre and virtually cyclic abelianisation. Then the commutator subgroup [ G , G ] [G,G] [ G , G ] is finitely generated free. Moreover, a finite generating set for [ G , G ] [G,G] [ G , G ] can be computed from a presentation for G G G .
Proof. Since G G G has a virtually cyclic abelianisation, G / [ G , G ] ≅ Z × A G/[G,G] \cong\mathbb{Z} \times A G / [ G , G ] ≅ Z × A , for some finite abelian group A A A . Note that A A A is computable from the presentation. Noting that [ G , G ] ⊆ F [G,G] \subseteq F [ G , G ] ⊆ F and so [ G , G ] ∩ Z = { 1 } [G,G] \cap\mathbb{Z} = \{1\} [ G , G ] ∩ Z = { 1 } , we have G / [ G , G ] ≅ F ⋊ ϕ Z / [ F ⋊ ϕ Z , F ⋊ ϕ Z ] ≅ F / [ F ⋊ ϕ Z , F ⋊ ϕ Z ] × Z G/[G,G] \cong F \rtimes_{\phi} \mathbb{Z}/[F \rtimes_{\phi} \mathbb{Z}, F \rtimes_{\phi} \mathbb{Z}] \cong F/[F \rtimes_{\phi} \mathbb{Z}, F \rtimes_{\phi} \mathbb{Z}] \times\mathbb{Z} G / [ G , G ] ≅ F ⋊ ϕ Z / [ F ⋊ ϕ Z , F ⋊ ϕ Z ] ≅ F / [ F ⋊ ϕ Z , F ⋊ ϕ Z ] × Z . Therefore, F / [ G , G ] ≅ A F/[G,G] \cong A F / [ G , G ] ≅ A . Thus [ G , G ] [G,G] [ G , G ] is a finite-index subgroup of F F F , and so is finitely-generated free. Moreover, by enumerating all finite-index subgroups H H H of F F F , checking if they are normal, and then when they are, computing the quotient F / H F/H F / H , and checking if it is isomorphic to A A A , we can compute a finite generating set for [ G , G ] [G,G] [ G , G ] . □
The second requirement of Theorem 2.5 is that the rational constraint (in our case the commutator subgroup) be fully contained in one of the factors of the direct product. The proof of the following firstly makes that observation and then applies Theorem 2.5.
Proposition 3.4. Let G G G be a finitely generated group such that [ G , G ] [G,G] [ G , G ] is finitely generated and such that G G G embeds as a finite index subgroup into V × A V \times A V × A for some virtually (f.g.) free group V V V and (f. g.) abelian group A A A .
If V × A V \times A V × A , the embedding of G G G into V × A V \times A V × A and the finite generating set for [ G , G ] [G,G] [ G , G ] are considered as input or computable, then G G G has decidable D P ( G , a b ) DP(G,\mathrm{ab}) D P ( G , ab ) .
Proof. First note that [ G , G ] ⊆ [ V × A , V × A ] = [ V , V ] ⊆ V [G,G] \subseteq[V \times A,V \times A] = [V,V] \subseteq V [ G , G ] ⊆ [ V × A , V × A ] = [ V , V ] ⊆ V . Since [ G , G ] [G,G] [ G , G ] is finitely generated, it is a rational subset of V × A V \times A V × A that is fully contained in V V V . Next, notice that as G G G has finite index in V × A V \times A V × A , it is a recognisable set.
Let E 0 E_0 E 0 be a system of equations with abelianisation constraints in G G G . Since G ≤ V × A G \leq V \times A G ≤ V × A with finite index, this can be translated into a system of equations E 1 E_1 E 1 in V × A V \times A V × A with the recognisable constraints that every variable lies in G G G , along with the rational constraints that X ∈ [ G , G ] X \in[G,G] X ∈ [ G , G ] for each abelianisation constraint in E 0 E_0 E 0 .
By [23 Theorem 14.2] , D P ( V , R a t ) DP(V,\mathrm{Rat}) D P ( V , Rat ) and D P ( A , R a t ) DP(A,\mathrm{Rat}) D P ( A , Rat ) are both decidable and EDT0L. Thus Theorem 2.5 implies that the Diophantine Problem in V × A V \times A V × A with rational constraints fully contained in V V V is EDT0L. To add the recognisable constraints, apply [35 Proposition 6.1] . □
We can now combine the results from this section to obtain the following.
Theorem 1.2. Let G G G be a [finitely-generated free]-by-cyclic group with centre and virtually cyclic abelianisation. Then D P ( G , a b ) DP(G,\mathrm{ab}) D P ( G , ab ) is decidable and EDT0L.
Proof. By Theorem 3.4, it suffices to show that [ G , G ] [G,G] [ G , G ] is finitely generated with a finite generating set computable from G G G and G G G embeds with finite index into V × Z V \times\mathbb{Z} V × Z , for some virtually finitely generated free group V V V , with V × Z V \times\mathbb{Z} V × Z and the embedding computable from the presentation for G G G . The former follows by Theorem 3.3 and the latter by Theorem 3.2. □
Since the class of one-relator groups with centre is a proper subclass of the class of [finitely-generated free]-by-cyclic groups with centre, we have the following.
Corollary 1.3. Let G G G be a one-relator group with centre and virtually cyclic abelianisation. Then D P ( G , a b ) DP(G,\mathrm{ab}) D P ( G , ab ) is decidable and EDT0L.
Proof. By [46 Theorem 1] , one-relator groups with centre and virtually cyclic abelianisation are GBS groups with centre. We can moreover use an identical argument to that provided in Theorem 2.9 to compute a free-by-cyclic presentation for a one-relator group with centre from a one-relator presentation. The result thus follows from Theorem 1.2. □
Tree products of infinite cyclic groups and tree-GBS groups
In the previous section we made use of the fact that any [f.g. free]-by-cyclic group with non trivial centre and virtually cyclic abelianisation is isomorphic to a GBS-group where, as a graph of groups, the underlying graph is a tree. So a tree-GBS group is a graph of groups where all vertex and edge groups are Z \mathbb{Z} Z , and the underlying graph of the graph of groups is a tree. Note that graphs of groups where the graph is a tree are usually called tree of groups in the literature. So a tree-GBS group is a tree of groups with infinite cyclic edge and vertex groups. Members of this class are called tree-GBS groups in the literature. The tree-GBS groups are also closely related to another class of groups, namely tree products of infinite cyclic groups. A tree product of infinite cyclic groups is a graph of groups where all the vertex groups are Z \mathbb{Z} Z and the underlying graph is a tree. Thus the only difference with tree-GBS groups is that the edge groups can be either Z \mathbb{Z} Z or { 1 } \{1\} { 1 } in a tree product of infinite cyclic groups. It is immediate from the definitions that any tree product of infinite cyclic groups is a free product of tree-GBS groups, where the free product decomposition is obtained by deleting all the edges labelled by { 1 } \{1\} { 1 } in the graph product description of the group. In this section we explore the connections with tree-GBS groups and more generally for tree products of infinite cyclic groups. Tree products of infinite cyclic groups have been studied e.g. in [45 ] where is proved that every tree product of infinite cyclic groups is a Garside group. Some papers on tree-GBS groups include e.g. [26 ] and [34 ] .
First we observe that the class of free-by-cyclic groups considered in the previous section are exactly the tree-GBS groups.
Proposition 4.1. The following are equivalent for a finitely generated group G G G :
(1) G G G is a tree-GBS group;
(2) G G G is a [f.g. free]-by-cyclic group with non trivial centre and virtually cyclic abelianisation.
Proof. It follows from Lemma 2.9 that if G G G is a [f.g. free]-by-cyclic group with non trivial centre and virtually cyclic abelianisation then G G G is a tree-GBS group.
For the converse, let G G G be a tree-GBS group. The fact that every tree-GBS group has non-trivial center is proved in the first two paragraphs of the proof of Proposition 3.2. Alternatively the fact that every tree-GBS group has non-trivial center can be deduced from [37 Theorem 1.1] together with the fact that the first Betti number of a tree is 0. We already say above that it is a consequence of [38 ] that the class of GBS groups with non-trivial center is equal to the class of [f.g. free]-by-cyclic group with non trivial centre. Hence it follows that G G G is a [f.g. free]-by-cyclic group with non trivial centre. To complete the proof we just need to verify that every tree-GBS group has a virtually cyclic abelianisation. This follows from [37 Theorem 1.1] or alternatively from [47 Theorem 2] which are general results that compute the torsion-free rank of the abelianisation of a GBS group. □ \square □
In general, the decidability of the Diophantine Problem is not preserved when taking graphs of groups. Some positive results exist in this direction: see, for example [41 ] . On the other hand there are even GBS groups with undecidable Diophantine Problems [33 ] . The following result show that for tree products of infinite cyclic groups the Diophantine Problem is decidable, and for this class the result classifies exactly when D P ( G , a b ) \mathcal{DP}(G,\mathrm{ab}) DP ( G , ab ) is decidable.
Theorem 1.5. Let G G G be a tree product of infinite cyclic groups. Then G G G has decidable Diophantine Problem. Furthermore:
(1) if all edge groups are infinite cyclic then D P ( G , a b ) \mathcal{DP}(G,\mathrm{ab}) DP ( G , ab ) is decidable and EDTOL;
(2) otherwise, D P ( G , a b ) \mathcal{DP}(G,\mathrm{ab}) DP ( G , ab ) is undecidable.
Proof. Since G G G is a tree product of infinite cyclic groups it follows that G G G is a free product of tree-GBS groups. From Theorem 3.2 and Theorem 4.1, each of the individual tree-GBS groups is virtually a direct product of hyperbolic groups, and thus has a decidable existential theory by [15 Theorem 3.1] . We can thus apply [41 Theorem 1] which shows stability of the existential theory under free products, to conclude that G G G has a decidable existential theory, and hence Diophantine Problem. For (1), if all the edge groups are infinite cyclic then G G G is a tree-GBS group and thus by Proposition 4.1 and Theorem 1.2 it follows that D P ( G , ab ) \mathit{DP}(G,\operatorname{ab}) DP ( G , ab ) is decidable and EDT0L.
It remains to prove (2). For this we need to show if at least one of the edge groups is trivial then D P ( G , ab ) \mathit{DP}(G,\operatorname{ab}) DP ( G , ab ) is undecidable. Let T T T be the underlying tree in the graph of groups defining G G G , and let T ‾ \overline{T} T be the forest obtained from T T T deleting all edges whose edge groups are trivial. Let T ‾ 1 , … , T ‾ m \overline{T}_1,\ldots,\overline{T}_m T 1 , … , T m be the connected components of T ‾ \overline{T} T . From our case assumption, at least one such edge must exist, and so T ‾ \overline{T} T has at least two connected components; that is, m ≥ 2 m \ge2 m ≥ 2 . We have that G ≅ π 1 ( T ‾ 1 ) ∗ ⋯ ∗ π 1 ( T ‾ m ) G \cong\pi_1(\overline{T}_1) * \cdots* \pi_1(\overline{T}_m) G ≅ π 1 ( T 1 ) ∗ ⋯ ∗ π 1 ( T m ) . Moreover, by definition, each π 1 ( T ‾ i ) \pi_1(\overline{T}_i) π 1 ( T i ) is a tree-GBS group, and thus has a virtually infinite cyclic abelianisation [37 Theorem 1.1] . Since we additionally have that ab ( G ) = ab ( π 1 ( T ‾ 1 ) ) × ⋯ × ab ( π 1 ( T ‾ m ) ) \operatorname{ab}(G) = \operatorname{ab}(\pi_1(\overline{T}_1)) \times\cdots\times\operatorname{ab}(\pi_1(\overline{T}_m)) ab ( G ) = ab ( π 1 ( T 1 )) × ⋯ × ab ( π 1 ( T m )) , it follows that for each i i i there exists v i ∈ π 1 ( T ‾ i ) v_i \in\pi_1(\overline{T}_i) v i ∈ π 1 ( T i ) such that ⟨ ab G ( v i ) ⟩ ≅ Z \langle\operatorname{ab}_G(v_i)\rangle\cong\mathbb{Z} ⟨ ab G ( v i )⟩ ≅ Z .
Now consider the subgroup H = ⟨ v 1 , … , v m ⟩ H = \langle v_1,\ldots,v_m\rangle H = ⟨ v 1 , … , v m ⟩ of G G G . Since each v i v_i v i projects onto an infinite order element in ab ( G ) \operatorname{ab}(G) ab ( G ) , we must have that each v i v_i v i has infinite order in G G G . As each lie in a distinct factor in the free product defining G G G , it follows that H H H is free of rank m m m . To complete our proof, we show that any algorithm that can decide D P ( G , ab ) \mathit{DP}(G,\operatorname{ab}) DP ( G , ab ) can decide D P ( H , ab ) \mathit{DP}(H,\operatorname{ab}) DP ( H , ab ) . Since the latter is undecidable [14 Theorem A] , this will complete the proof. To do so, we first construct a retract from G G G onto H H H . We do this by constructing retracts r i : π 1 ( T ‾ i ) → ⟨ v i ⟩ r_i \colon\pi_1(\overline{T}_i) \to\langle v_i\rangle r i : π 1 ( T i ) → ⟨ v i ⟩ for each i i i . Let i ∈ { 1 , … , m } i \in\{1,\ldots,m\} i ∈ { 1 , … , m } . Then ab G ( π 1 ( T ‾ i ) ) \operatorname{ab}_G(\pi_1(\overline{T}_i)) ab G ( π 1 ( T i )) is virtually Z \mathbb{Z} Z [37 Theorem 1.1] , and so retracts onto the copy of Z \mathbb{Z} Z inside it. Composing this retract with ab G \operatorname{ab}_G ab G gives a function from π 1 ( T ‾ i ) \pi_1(\overline{T}_i) π 1 ( T i ) to Z \mathbb{Z} Z that maps v i v_i v i to the generator. It thus follows that there is a retract r i : π 1 ( T ‾ i ) → ⟨ v i ⟩ r_i \colon\pi_1(\overline{T}_i) \to\langle v_i\rangle r i : π 1 ( T i ) → ⟨ v i ⟩ . As G G G is a free product of the groups π 1 ( T ‾ i ) \pi_1(\overline{T}_i) π 1 ( T i ) , these now define a unique retract r : G → H r \colon G \to H r : G → H that extends each of the retracts r i r_i r i .
Now suppose that E \mathcal{E} E is a system of equations in H H H with abelianisation constraints. We can assume every equation in E \mathcal{E} E is of the form X Y = Z XY = Z X Y = Z , where X X X , Y Y Y and Z Z Z can be either constants or variables (see for example [11 Section 4] ). We will use E \mathcal{E} E to define a new system E ‾ \overline{\mathcal{E}} E of equations with abelianisation constraints in G G G that admits a a solution if and only if E \mathcal{E} E does. For each equation X Y = Z XY = Z X Y = Z in H H H , add the same equation to E ‾ \overline{\mathcal{E}} E . To consider the abelianisation constraints, write ab ( G ) = Z m × A \operatorname{ab}(G) = \mathbb{Z}^m \times A ab ( G ) = Z m × A , where A A A is a finite abelian group, and let p p p be the exponent of A A A . For each abelianisation constraint X ∈ [ H , H ] X \in[H,H] X ∈ [ H , H ] , add the abelianisation constraint X p ∈ [ G , G ] X^p \in[G,G] X p ∈ [ G , G ] to E ‾ \overline{\mathcal{E}} E . Naturally, every solution to E \mathcal{E} E will be a solution to E ‾ \overline{\mathcal{E}} E . Moreover, if there exist x , y , z ∈ G x,y,z \in G x , y , z ∈ G such that x y = z xy=z x y = z , then r ( x ) r ( y ) = r ( z ) r(x)r(y)=r(z) r ( x ) r ( y ) = r ( z ) . If x ∈ G x \in G x ∈ G is such that x p ∈ [ G , G ] x^p \in[G,G] x p ∈ [ G , G ] , then r ( x ) r(x) r ( x ) will lie in [ H , H ] [H,H] [ H , H ] if and only if the exponent-sum of each v i v_i v i in r ( x ) r(x) r ( x ) is $0$, which is true if and only if the exponent-sum of each v i v_i v i in r ( x p ) r(x^p) r ( x p ) is 0 0 0 . By the definition of r r r , this holds if and only if for each i i i the exponent-sum across all of the elements mapped by r r r to v i v_i v i is $0 (noting that the p p p th power ensures nothing in A A A can appear). But since x p ∈ [ G , G ] x^p \in[G,G] x p ∈ [ G , G ] , this must hold, and so we can conclude that r ( x ) ∈ [ H , H ] r(x) \in[H,H] r ( x ) ∈ [ H , H ] . We have thus shown that if E ‾ \overline{\mathcal{E}} E admits a solution, then applying r r r to this solution yields a solution to E \mathcal{E} E . We can conclude that E \mathcal{E} E admits a solution if and only if E ‾ \overline{\mathcal{E}} E does. Since E ‾ \overline{\mathcal{E}} E is computable from E \mathcal{E} E , we can thus use D P ( G , ab ) \mathit{DP}(G,\operatorname{ab}) DP ( G , ab ) to solve D P ( H , ab ) \mathit{DP}(H,\operatorname{ab}) DP ( H , ab ) . Since the latter is undecidable [14 Theorem A] , the result follows. □
In [37 Theorem 1.1] and [47 Theorem 2] , formulas are given for the torsion free rank of the abelianisations of GBS groups, given in terms of Betti numbers of their defining graphs. In particular those results may be applied to describe exactly those GBS groups with virtually cyclic abelianisation:
Combining our results with Levitt’s theorem describing the rank of the abelianisation of a GBS group in terms of the graph of groups [37 Theorem 1.1] gives the following:
Corollary 4.2. Let G G G be a GBS group with virtually cyclic abelianisation. Then one of the following holds:
G G G is a tree-GBS group and D P ( G , ab ) \mathit{DP}(G,\operatorname{ab}) DP ( G , ab ) is decidable and EDT0L; or else
G ≅ B S ( m , n ) G \cong BS(m,n) G ≅ B S ( m , n ) for some m , n m,n m , n with ∣ m ∣ ≠ ∣ n ∣ |m| \ne|n| ∣ m ∣ = ∣ n ∣ .
The question for B S ( m , n ) BS(m,n) B S ( m , n ) (case (2)) remains open. Indeed, it is not even know whether the Diophantine Problem is decidable for any B S ( m , n ) BS(m,n) B S ( m , n ) for some m , n m,n m , n with ∣ m ∣ ≠ ∣ n ∣ |m| \ne|n| ∣ m ∣ = ∣ n ∣ . It was however recently shown [33 ] that every group B S ( m , n ) BS(m,n) B S ( m , n ) with 1 < m < n 1 < m < n 1 < m < n is quasi-isometric to a group with an undecidable Diophantine Problem. The addition of abelianisation constraints does not make a difference in the case of B S ( 1 , n ) BS(1,n) B S ( 1 , n ) , as here every element of the commutator subgroup is a product of a bounded number of commutators, and so the commutator subgroups is definable in the Diophantine Problem.
Undecidability results for free-by-cyclic groups
In this section we exhibit free-by-cyclic groups G G G for which D P ( G , a b ) DP(G,\mathrm{ab}) D P ( G , ab ) is undecidable, providing a counterpoint to the classes of groups in § 5 and § 6 , where the problem is decidable. The undecidability is connected both to the abelianisation being ‘larger’ than virtually cyclic, and to the centre being trivial.
Free-by-cyclic groups with abelianisations of torsion-free rank at least 3
We show that in free-by-cyclic groups with centre, when the rank of the torsion-free part of the abelianisation is greater than or equal to 3, the problems we have considered before become undecidable. A key tool to establish this, and of independent interest, is Proposition 5.1 .
Proposition 5.1. Let G G G be a finitely generated group.
If D P ( G , a b ) DP(G,\mathrm{ab}) D P ( G , ab ) is decidable, then D P ( G / Z ( G ) , a b ) DP(G/Z(G),\mathrm{ab}) D P ( G / Z ( G ) , ab ) is decidable.
Proof. Let Q = G / Z ( G ) Q = G/Z(G) Q = G / Z ( G ) . Fix a lift s : Q → G s: Q \to G s : Q → G that satisfies s ( 1 Q ) = 1 G s(1_Q) = 1_G s ( 1 Q ) = 1 G . Then every element in G G G can be expressed in the form s ( q ) z s(q)z s ( q ) z for some q ∈ Q q \in Q q ∈ Q and z ∈ Z ( G ) z \in Z(G) z ∈ Z ( G ) . Moreover, if s ( q ) z = s ( q ′ ) z ′ s(q)z = s(q')z' s ( q ) z = s ( q ′ ) z ′ , then s ( q ) ( s ( q ′ ) ) − 1 ∈ Z ( G ) s(q)(s(q'))^{-1} \in Z(G) s ( q ) ( s ( q ′ ) ) − 1 ∈ Z ( G ) , and so s ( q ) = s ( q ′ ) g s(q) = s(q')g s ( q ) = s ( q ′ ) g for some g ∈ Z ( G ) g \in Z(G) g ∈ Z ( G ) . It follows that q = q ′ q = q' q = q ′ and z = z ′ z = z' z = z ′ , and so this representation is unique.
Take X Y Z = 1 XYZ = 1 X Y Z = 1 to be an equation in Q Q Q , where X X X , Y Y Y and Z Z Z are variables or constants. Let X ˉ \bar{X} X ˉ just denote a variable in G G G if X X X is a variable, and denote s ( X ) s(X) s ( X ) if X X X is a constant. Define Y ˉ \bar{Y} Y ˉ and Z ˉ \bar{Z} Z ˉ analogously. Then X Y Z = 1 XYZ = 1 X Y Z = 1 has a solution in Q Q Q if and only if the system with constraints ( X ˉ Y ˉ Z ˉ ) = U ∧ ( U ∈ Z ( G ) ) (\bar{X}\bar{Y}\bar{Z}) = U \land(U \in Z(G)) ( X ˉ Y ˉ Z ˉ ) = U ∧ ( U ∈ Z ( G )) has a solution. Moreover, the solutions to this new system are exactly the solutions to X Y Z = 1 XYZ = 1 X Y Z = 1 in Q Q Q lifted by s s s and then multiplied by some element of Z ( G ) Z(G) Z ( G ) . Note that Z ( G ) Z(G) Z ( G ) is D P ( G ) DP(G) D P ( G ) -definable (see Example 2.4(2)). Thus this system with constraints ( X ˉ Y ˉ Z ˉ = U ) ∧ ( U ∈ Z ( G ) ) (\bar{X}\bar{Y}\bar{Z} = U) \land(U \in Z(G)) ( X ˉ Y ˉ Z ˉ = U ) ∧ ( U ∈ Z ( G )) is equivalent to a (unconstrained) system in G G G .
At this point, we have shown that the decidability of D P ( G , a b ) DP(G,\mathrm{ab}) D P ( G , ab ) implies the decidability of D P ( Q ) DP(Q) D P ( Q ) , so it remains to consider the abelianisation constraints in Q Q Q . Let q ∈ Q q \in Q q ∈ Q . We claim that q ∈ [ Q , Q ] q \in[Q,Q] q ∈ [ Q , Q ] if and only if s ( q ) ∈ [ G , G ] Z ( G ) s(q) \in[G,G]Z(G) s ( q ) ∈ [ G , G ] Z ( G ) . First, by applying the projection homomorphism from G G G to Q Q Q , s ( q ) ∈ [ G , G ] Z ( G ) s(q) \in[G,G]Z(G) s ( q ) ∈ [ G , G ] Z ( G ) implies q ∈ [ Q , Q ] q \in[Q,Q] q ∈ [ Q , Q ] . Second, suppose that q ∈ [ Q , Q ] q \in[Q,Q] q ∈ [ Q , Q ] . Then q = c 1 ⋯ c m q = c_1 \cdots c_m q = c 1 ⋯ c m , for commutators c 1 , … , c m ∈ Q c_1,\ldots,c_m \in Q c 1 , … , c m ∈ Q . Thus s ( q ) = s ( c 1 ) ⋯ s ( c m ) z s(q) = s(c_1)\cdots s(c_m)z s ( q ) = s ( c 1 ) ⋯ s ( c m ) z , for some z ∈ Z ( G ) z \in Z(G) z ∈ Z ( G ) , and so s ( q ) ∈ [ G , G ] Z ( G ) s(q) \in[G,G]Z(G) s ( q ) ∈ [ G , G ] Z ( G ) , as required. As a product of two D P ( G , a b ) DP(G,\mathrm{ab}) D P ( G , ab ) -definable sets, [ G , G ] Z ( G ) [G,G]Z(G) [ G , G ] Z ( G ) is also D P ( G , a b ) DP(G,\mathrm{ab}) D P ( G , ab ) -definable. We can thus replace any abelianisation constraint X ∈ [ Q , Q ] X \in[Q,Q] X ∈ [ Q , Q ] , where X X X is a variable with X ˉ ∈ [ G , G ] Z ( G ) \bar{X} \in[G,G]Z(G) X ˉ ∈ [ G , G ] Z ( G ) to complete our encoding of D P ( Q , a b ) DP(Q,\mathrm{ab}) D P ( Q , ab ) into D P ( G , a b ) DP(G,\mathrm{ab}) D P ( G , ab ) .
Remark 5.2. Note that the reverse direction in Proposition 5.1 does not hold: the 3 × 3 3 \times3 3 × 3 Heisenberg group over the integers is a counterexample as a central extension of Z 2 \mathbb{Z}^2 Z 2 [25 ] . In fact, there is a finitely generated class 2 nilpotent group (and thus a central extension of a finitely generated abelian group) with undecidable single equation problem [48 ] , and thus even in case of single equations the converse to the above fails to hold.
Theorem 1.6. Let G G G be a [f.g. free]-by-cyclic group with non-trivial centre and a torsion-free rank 3 or greater abelianisation. Then D P ( G , a b ) DP(G,\mathrm{ab}) D P ( G , ab ) is undecidable.
Proof. By [7 Corollary 3.7] the group G / Z ( G ) G/Z(G) G / Z ( G ) is virtually free. As the rank of the abelianisation of G G G is 3 or more, and Z ( G ) Z(G) Z ( G ) is cyclic ([7 Lemma 3.4] ) the rank of the abelianisation of G / Z ( G ) G/Z(G) G / Z ( G ) is 2 or more. We can therefore apply [14 Theorem B] to conclude that D P ( G / Z ( G ) , a b ) DP(G/Z(G),\mathrm{ab}) D P ( G / Z ( G ) , ab ) is undecidable, and so Theorem 5.1 tells us that D P ( G , a b ) DP(G,\mathrm{ab}) D P ( G , ab ) is undecidable.
We now consider various cases without centre, starting with the first hydra group.
The first hydra group
The object of study in this section is a free-by-cyclic group with abelianisation equal to Z 2 \mathbb{Z}^{2} Z 2 and trivial centre, more commonly given by its one-relator presentation
K = ⟨ c , q ∣ c ( q c q − 1 ) = ( q c q − 1 ) c ⟩ . K=\langle c,q\mid c(qcq^{-1})=(qcq^{-1})c\rangle. K = ⟨ c , q ∣ c ( q c q − 1 ) = ( q c q − 1 ) c ⟩ .
We will show that D P ( K , a b ) \mathcal{DP}(K,\mathrm{ab}) DP ( K , ab ) is undecidable by using the isomorphism between K K K and G G G given in Lemma 5.3 and working with a free-by-cyclic presentation F ⋊ ϕ Z F\rtimes_{\phi}\mathbb{Z} F ⋊ ϕ Z for this group, where ϕ \phi ϕ sends a a a to a b ab ab and b b b to b b b . Note that ϕ \phi ϕ has infinite order in Out ( F ) \operatorname{Out}(F) Out ( F ) , so by [7 Lemma 3.4] the centre of K K K is trivial. We note that D P ( K ) \mathcal{DP}(K) DP ( K ) is undecidable.
This is the ‘first’ hydra group defined by Dison and Riley [24 ] , and enjoys various nice properties such as CAT(0) and biautomatic. We show that this group has an undecidable Diophantine Problem with abelianisation constraints. We expect the fundamental idea of our proof will work for all hydra groups, only our method for computing centralisers does not seem to, so some alternative approach for computing these centralisers will be needed.
We will mostly be using the free-by-cyclic description of K K K given below as G G G . However, in order to compute certain centralisers, it is easier to view K K K as the semidirect product of the right-angled Artin group on a bi-infinite line with Z \mathbb{Z} Z , so we give the isomorphism between the two standard presentations for K K K .
Lemma 5.3 ([33 Lemma 5.4] ). There is an isomorphism Θ \Theta Θ from
G = ⟨ a , b , t ∣ t a t − 1 = a b , t b t − 1 = b ⟩ G=\langle a,b,t\mid tat^{-1}=ab,\ tbt^{-1}=b\rangle G = ⟨ a , b , t ∣ t a t − 1 = ab , t b t − 1 = b ⟩ to K = ⟨ c , q ∣ c ( q c q − 1 ) = ( q c q − 1 c ) ⟩ K=\langle c,q\mid c(qcq^{-1})=(qcq^{-1}c)\rangle K = ⟨ c , q ∣ c ( q c q − 1 ) = ( q c q − 1 c )⟩ defined by a ↦ c q − 1 a\mapsto cq^{-1} a ↦ c q − 1 , b ↦ q c q − 1 c − 1 b\mapsto qcq^{-1}c^{-1} b ↦ q c q − 1 c − 1 , and t ↦ c t\mapsto c t ↦ c .
In addition, let c i = q i c q − i c_i=q^icq^{-i} c i = q i c q − i , where i ∈ Z i\in\mathbb{Z} i ∈ Z . Then A ( Γ ) = ⟨ { c i ∣ i ∈ Z } ⟩ A(\Gamma)=\langle\{c_i\mid i\in\mathbb{Z}\}\rangle A ( Γ ) = ⟨{ c i ∣ i ∈ Z }⟩ is the right-angled Artin group on an infinite line, and
K ≅ A ( Γ ) ⋊ ϕ Z , K\cong A(\Gamma)\rtimes_{\phi}\mathbb{Z}, K ≅ A ( Γ ) ⋊ ϕ Z , where ϕ ∈ Aut ( A ( Γ ) ) \phi\in\operatorname{Aut}(A(\Gamma)) ϕ ∈ Aut ( A ( Γ )) is defined by c i ↦ c i + 1 c_i\mapsto c_{i+1} c i ↦ c i + 1 .
Our proof of undecidability requires various sets to be D P ( G , a b ) \mathcal{DP}(G,\mathrm{ab}) DP ( G , ab ) -definable. Centralisers provide a useful source for these, since they are always D P ( G , a b ) \mathcal{DP}(G,\mathrm{ab}) DP ( G , ab ) -definable (they are, in fact D P ( G ) \mathcal{DP}(G) DP ( G ) -definable). We prove this using the normal form for semidirect products: either that for the F 2 F_2 F 2 -by-Z \mathbb{Z} Z presentation or that for the A ( Γ ) A(\Gamma) A ( Γ ) -by-Z \mathbb{Z} Z presentation.
Lemma 5.4. Let G = ⟨ a , b , t ∣ t a t − 1 = a b , t b t − 1 = b ⟩ G=\langle a,b,t\mid tat^{-1}=ab,\ tbt^{-1}=b\rangle G = ⟨ a , b , t ∣ t a t − 1 = ab , t b t − 1 = b ⟩ and K = ⟨ c , q ∣ c ( q c q − 1 ) = ( q c q − 1 ) c ⟩ K=\langle c,q\mid c(qcq^{-1})=(qcq^{-1})c\rangle K = ⟨ c , q ∣ c ( q c q − 1 ) = ( q c q − 1 ) c ⟩ , and let c i c_i c i be as defined in Theorem 5.3. Then
(1) C G ( a ) = ⟨ a ⟩ C_G(a)=\langle a\rangle C G ( a ) = ⟨ a ⟩ ;
(2) C G ( b ) = ⟨ b , t ⟩ C_G(b)=\langle b,t\rangle C G ( b ) = ⟨ b , t ⟩ ;
(3) C G ( a b a − 1 ) = ⟨ a b a − 1 , t ⟩ C_G(aba^{-1})=\langle aba^{-1},t\rangle C G ( ab a − 1 ) = ⟨ ab a − 1 , t ⟩ ;
(4) C K ( c i ) = ⟨ c i − 1 , c i , c i + 1 ⟩ C_K(c_i)=\langle c_{i-1},c_i,c_{i+1}\rangle C K ( c i ) = ⟨ c i − 1 , c i , c i + 1 ⟩ ;
(5) C G ( t ) = ⟨ a b a − 1 , b , t ⟩ C_G(t)=\langle aba^{-1},b,t\rangle C G ( t ) = ⟨ ab a − 1 , b , t ⟩ .
Proof. (1): Let u t k ∈ G ut^k\in G u t k ∈ G , where u u u is a word over { a ± 1 , b ± 1 } \{a^{\pm1},b^{\pm1}\} { a ± 1 , b ± 1 } . Then u t k ∈ C G ( a ) ut^k\in C_G(a) u t k ∈ C G ( a ) if and only if a u t k = G u t k a = G u a b k t aut^k=_G ut^ka=_G uab^kt a u t k = G u t k a = G u a b k t , which holds if and only if a u = F ( a , b ) u a b k au=_{{F(a,b)}}uab^k a u = F ( a , b ) u a b k . This can only happen if k = 0 k=0 k = 0 , as seen by taking the abelianisation on both sides, and so a u = F ( a , b ) u a au=_{{F(a,b)}}ua a u = F ( a , b ) u a , which implies u u u is a power of a a a . It follows that C G ( a ) = ⟨ a ⟩ C_G(a)=\langle a\rangle C G ( a ) = ⟨ a ⟩ .
(2): First note that b , t ∈ C G ( b ) b,t\in C_G(b) b , t ∈ C G ( b ) , and so ⟨ b , t ⟩ ⊆ C G ( b ) \langle b,t\rangle\subseteq C_G(b) ⟨ b , t ⟩ ⊆ C G ( b ) . Now let u t k ∈ C G ( b ) ut^k\in C_G(b) u t k ∈ C G ( b ) . Then b u t k = u t k b = u b t k but^k=ut^kb=ubt^k b u t k = u t k b = u b t k , and so u b = b u ub=bu u b = b u ; that is, u ∈ C F ( a , b ) ( b ) = ⟨ b ⟩ u\in C_{F(a,b)}(b)=\langle b\rangle u ∈ C F ( a , b ) ( b ) = ⟨ b ⟩ . Thus u t k = b l t k ∈ ⟨ b , t ⟩ ut^k=b^lt^k\in\langle b,t\rangle u t k = b l t k ∈ ⟨ b , t ⟩ , and so C G ( b ) = ⟨ b , t ⟩ C_G(b)=\langle b,t\rangle C G ( b ) = ⟨ b , t ⟩ .
(3): We have that t a b a − 1 = a b ⋅ b ⋅ b − 1 a − 1 t = a b a − 1 t taba^{-1}=ab\cdot b\cdot b^{-1}a^{-1}t=aba^{-1}t t ab a − 1 = ab ⋅ b ⋅ b − 1 a − 1 t = ab a − 1 t , and so ⟨ a b a − 1 , t ⟩ ⊆ C G ( a b a − 1 ) \langle aba^{-1},t\rangle\subseteq C_G(aba^{-1}) ⟨ ab a − 1 , t ⟩ ⊆ C G ( ab a − 1 ) . Let u t k ∈ C G ( a b a − 1 ) ut^k\in C_G(aba^{-1}) u t k ∈ C G ( ab a − 1 ) . Then a b a − 1 ⋅ u t k = G u t k ⋅ a b a − 1 = G u a b a − 1 t k aba^{-1}\cdot ut^k=_G ut^k\cdot aba^{-1}=_G uaba^{-1}t^k ab a − 1 ⋅ u t k = G u t k ⋅ ab a − 1 = G u ab a − 1 t k . Thus u a b a − 1 = F ( a , b ) a b a − 1 u uaba^{-1}=_{{F(a,b)}}aba^{-1}u u ab a − 1 = F ( a , b ) ab a − 1 u , and so u ∈ C F ( a , b ) ( a b a − 1 ) = ⟨ a b a − 1 ⟩ u\in C_{F(a,b)}(aba^{-1})=\langle aba^{-1}\rangle u ∈ C F ( a , b ) ( ab a − 1 ) = ⟨ ab a − 1 ⟩ ; then u t k ∈ ⟨ a b a − 1 , t ⟩ ut^k\in\langle aba^{-1},t\rangle u t k ∈ ⟨ ab a − 1 , t ⟩ , and C G ( a b a − 1 ) = ⟨ a b a − 1 , t ⟩ C_G(aba^{-1})=\langle aba^{-1},t\rangle C G ( ab a − 1 ) = ⟨ ab a − 1 , t ⟩ .
(4): From the presentation of A ( Γ ) A(\Gamma) A ( Γ ) , we have that ⟨ c i − 1 , c i , c i + 1 ⟩ ⊆ C K ( c i ) \langle c_{i-1},c_i,c_{i+1}\rangle\subseteq C_K(c_i) ⟨ c i − 1 , c i , c i + 1 ⟩ ⊆ C K ( c i ) . Now let u q k ∈ C K ( c i ) uq^k\in C_K(c_i) u q k ∈ C K ( c i ) , where u ∈ A ( Γ ) u\in A(\Gamma) u ∈ A ( Γ ) and k ∈ Z k\in\mathbb{Z} k ∈ Z . Then c i u q k = K u q k c i = K u c k + i q k c_iuq^k=_K uq^kc_i=_K uc_{k+i}q^k c i u q k = K u q k c i = K u c k + i q k , and so c i u = A ( Γ ) u c k + i c_i u=_{{A(\Gamma)}}uc_{k+i} c i u = A ( Γ ) u c k + i ; that is c i c_i c i is conjugate in A ( Γ ) A(\Gamma) A ( Γ ) to c k + i c_{k+i} c k + i . It follows that c i c_i c i and c k + i c_{k+i} c k + i are conjugate in the abelianisation of A ( Γ ) A(\Gamma) A ( Γ ) ; that is, they are equal in the abelianisation. But generators in A ( Γ ) A(\Gamma) A ( Γ ) are mapped to generators in the infinite rank free group, and so the images of c i c_i c i and c i + k c_{i+k} c i + k cannot be equal in the abelianisation unless c i = c i + k c_i=c_{i+k} c i = c i + k . Thus k = 0 k=0 k = 0 , and so C K ( c i ) ⊆ A ( Γ ) C_K(c_i)\subseteq A(\Gamma) C K ( c i ) ⊆ A ( Γ ) . Since the C A ( Γ ) ( c i ) = ⟨ c i − 1 , c i , c i + 1 ⟩ C_{A(\Gamma)}(c_i)=\langle c_{i-1},c_i,c_{i+1}\rangle C A ( Γ ) ( c i ) = ⟨ c i − 1 , c i , c i + 1 ⟩ ([49 The Centralizer Theorem] , see also [22 Proposition 2.1] ), the result follows.
(5): We compute C G ( t ) C_G(t) C G ( t ) by considering its image in the (isomorphic) group K K K , using the isomorphism from Theorem 5.3. So we instead need to compute C K ( c ) C_K(c) C K ( c ) . From (4), C K ( c ) = C K ( c 0 ) = ⟨ c − 1 , c 0 , c 1 ⟩ = ⟨ q − 1 c q , c , q c q − 1 ⟩ C_K(c)=C_K(c_0)=\langle c_{-1},c_0,c_1\rangle=\langle q^{-1}c q,c,qcq^{-1}\rangle C K ( c ) = C K ( c 0 ) = ⟨ c − 1 , c 0 , c 1 ⟩ = ⟨ q − 1 c q , c , q c q − 1 ⟩ . The preimage of this subgroup under the isomorphism from Theorem 5.3 is ⟨ t − 1 a t a − 1 t , t , b t ⟩ = ⟨ a b − 1 a − 1 t , t , b t ⟩ = ⟨ a b a − 1 , b , t ⟩ \langle t^{-1}ata^{-1}t,t,bt\rangle=\langle ab^{-1}a^{-1}t,t,bt\rangle=\langle aba^{-1},b,t\rangle ⟨ t − 1 a t a − 1 t , t , b t ⟩ = ⟨ a b − 1 a − 1 t , t , b t ⟩ = ⟨ ab a − 1 , b , t ⟩ .
Using the centralisers we computed, we now have that the following sets are definable using the Diophantine Problem in G G G .
Lemma 5.5. Let G = ⟨ a , b , t ∣ t a t − 1 = a b , t b t − 1 = b ⟩ G=\langle a,b,t\mid tat^{-1}=ab,tbt^{-1}=b\rangle G = ⟨ a , b , t ∣ t a t − 1 = ab , t b t − 1 = b ⟩ . Then the following subsets of G G G are D P ( G ) DP(G) D P ( G ) -definable:
(1) ⟨ a ⟩ \langle a\rangle ⟨ a ⟩ ;
(2) ⟨ b , t ⟩ \langle b,t\rangle ⟨ b , t ⟩ ;
(3) ⟨ a b a − 1 , t ⟩ \langle aba^{-1},t\rangle ⟨ ab a − 1 , t ⟩ ;
(4) ⟨ t ⟩ \langle t\rangle ⟨ t ⟩ .
Proof. As centralisers are D P ( G ) DP(G) D P ( G ) -definable, (1), (2) and (3) analogously follow from Theorem 5.4(1), (2) and (3). For (4), note that ⟨ t ⟩ = ⟨ a b a − 1 , t ⟩ ∩ ⟨ b , t ⟩ \langle t\rangle=\langle aba^{-1},t\rangle\cap\langle b,t\rangle ⟨ t ⟩ = ⟨ ab a − 1 , t ⟩ ∩ ⟨ b , t ⟩ . Since intersections of D P ( G ) DP(G) D P ( G ) -definable sets are D P ( G ) DP(G) D P ( G ) -definable and both of these sets are D P ( G ) DP(G) D P ( G ) -definable ((2) and (3)), the result follows.
The next centraliser we use is not powerful enough on its own to give undecidability in any obvious way. However, when we take its abelianisation, it does encode a divisibility condition in the ring of integers, that will be important to reduce Hilbert’s 10th problem in the ring of integers to D P ( G ) DP(G) D P ( G ) . We do not explicitly compute this centraliser; just its abelianisation.
Lemma 5.6. Let G = ⟨ a , b , t ∣ t a t − 1 = a b , t b t − 1 = b ⟩ G=\langle a,b,t\mid tat^{-1}=ab,tbt^{-1}=b\rangle G = ⟨ a , b , t ∣ t a t − 1 = ab , t b t − 1 = b ⟩ . Fix k ∈ Z k\in\mathbb{Z} k ∈ Z . Then
ab ( C G ( a t k ) ) = { a k ℓ t k ∣ ℓ ∈ Z } . \operatorname{ab}(C_G(at^k))=\{a^{k\ell}t^k\mid\ell\in\mathbb{Z}\}. ab ( C G ( a t k )) = { a k ℓ t k ∣ ℓ ∈ Z } .
Proof. We use the isomorphism and notation of Theorem 5.3. We have that C G ( a t k ) = C K ( c 0 q k c 0 − 1 ) = C K ( c − 1 k c 0 q − 1 ) C_G(at^k)=C_K(c_0q^k c_0^{-1})=C_K(c_{-1}^k c_0q^{-1}) C G ( a t k ) = C K ( c 0 q k c 0 − 1 ) = C K ( c − 1 k c 0 q − 1 ) . Let u q ℓ ∈ C K ( c − 1 k c 0 q − 1 ) uq^\ell\in C_K(c_{-1}^k c_0q^{-1}) u q ℓ ∈ C K ( c − 1 k c 0 q − 1 ) , where u ∈ A ( Γ ) u\in A(\Gamma) u ∈ A ( Γ ) and ℓ ∈ Z \ell\in\mathbb{Z} ℓ ∈ Z . Then we use u q ℓ ⋅ c − 1 k c 0 q − 1 = c − 1 k c 0 q − 1 ⋅ u q ℓ uq^\ell\cdot c_{-1}^k c_0q^{-1}=c_{-1}^k c_0q^{-1}\cdot uq^\ell u q ℓ ⋅ c − 1 k c 0 q − 1 = c − 1 k c 0 q − 1 ⋅ u q ℓ and rewrite as
u c ℓ − 1 k c ℓ q ℓ − 1 = u q ℓ ⋅ c − 1 k c 0 q − 1 = c − 1 k c 0 q − 1 ⋅ u q ℓ = c − 1 k c 0 ⋅ ( u ) ϕ − 1 ⋅ q ℓ − 1 . \begin{aligned}
u c_{\ell-1}^k c_\ell q^{\ell-1}=u q^\ell\cdot c_{-1}^k c_0q^{-1} \\
&=c_{-1}^k c_0q^{-1}\cdot uq^\ell\\
&=c_{-1}^k c_0\cdot(u)^{\phi^{-1}}\cdot q^{\ell-1}.
\end{aligned} u c ℓ − 1 k c ℓ q ℓ − 1 = u q ℓ ⋅ c − 1 k c 0 q − 1 = c − 1 k c 0 q − 1 ⋅ u q ℓ = c − 1 k c 0 ⋅ ( u ) ϕ − 1 ⋅ q ℓ − 1 .
Thus c − 1 k c 0 ⋅ ( u ) ϕ − 1 = u c ℓ − 1 k c ℓ c_{-1}^k c_0\cdot(u)^{\phi^{-1}}=u c_{\ell-1}^k c_\ell c − 1 k c 0 ⋅ ( u ) ϕ − 1 = u c ℓ − 1 k c ℓ and so ( u ) ϕ − 1 = c 0 − 1 c − 1 − k u c ℓ − 1 k c ℓ (u)^{\phi^{-1}}=c_0^{-1}c_{-1}^{-k}u c_{\ell-1}^k c_\ell ( u ) ϕ − 1 = c 0 − 1 c − 1 − k u c ℓ − 1 k c ℓ .
Abelianising, noting that exponent-sums of the c i c_i c i s are well-defined inside the infinite right-angled Artin group, gives:
(1) expsum c i ( ( u ) ϕ − 1 ) = expsum c i ( u ) \operatorname{expsum}_{c_i}((u)^{\phi^{-1}})=\operatorname{expsum}_{c_i}(u) expsum c i (( u ) ϕ − 1 ) = expsum c i ( u ) , for all i ∉ { − 1 , 0 , ℓ − 1 , ℓ } i\notin\{-1,0,\ell-1,\ell\} i ∈ / { − 1 , 0 , ℓ − 1 , ℓ } ;
(2) expsum c − 1 ( ( u ) ϕ − 1 ) = expsum c − 1 ( u ) − k \operatorname{expsum}_{c_{-1}}((u)^{\phi^{-1}})=\operatorname{expsum}_{c_{-1}}(u)-k expsum c − 1 (( u ) ϕ − 1 ) = expsum c − 1 ( u ) − k ;
(3) expsum c 0 ( ( u ) ϕ − 1 ) = expsum c 0 ( u ) − 1 \operatorname{expsum}_{c_0}((u)^{\phi^{-1}})=\operatorname{expsum}_{c_0}(u)-1 expsum c 0 (( u ) ϕ − 1 ) = expsum c 0 ( u ) − 1 ;
(4) expsum c ℓ − 1 ( ( u ) ϕ − 1 ) = expsum c ℓ − 1 ( u ) + k \operatorname{expsum}_{c_{\ell-1}}((u)^{\phi^{-1}})=\operatorname{expsum}_{c_{\ell-1}}(u)+k expsum c ℓ − 1 (( u ) ϕ − 1 ) = expsum c ℓ − 1 ( u ) + k ;
(5) expsum c ℓ ( ( u ) ϕ − 1 ) = expsum c ℓ ( u ) + 1 \operatorname{expsum}_{c_\ell}((u)^{\phi^{-1}})=\operatorname{expsum}_{c_\ell}(u)+1 expsum c ℓ (( u ) ϕ − 1 ) = expsum c ℓ ( u ) + 1 .
These each imply, respectively:
(1) expsum c i + 1 ( u ) = expsum c i ( u ) \operatorname{expsum}_{c_{i+1}}(u)=\operatorname{expsum}_{c_i}(u) expsum c i + 1 ( u ) = expsum c i ( u ) , for all i ∉ { − 1 , 0 , ℓ − 1 , ℓ } i\notin\{-1,0,\ell-1,\ell\} i ∈ / { − 1 , 0 , ℓ − 1 , ℓ } ;
(2) expsum c 0 ( u ) = expsum c − 1 ( u ) − k \operatorname{expsum}_{c_0}(u)=\operatorname{expsum}_{c_{-1}}(u)-k expsum c 0 ( u ) = expsum c − 1 ( u ) − k ;
(3) expsum c 1 ( u ) = expsum c 0 ( u ) − 1 \operatorname{expsum}_{c_1}(u)=\operatorname{expsum}_{c_0}(u)-1 expsum c 1 ( u ) = expsum c 0 ( u ) − 1 ;
(4) expsum c ℓ ( u ) = expsum c ℓ − 1 ( u ) + k \operatorname{expsum}_{c_\ell}(u)=\operatorname{expsum}_{c_{\ell-1}}(u)+k expsum c ℓ ( u ) = expsum c ℓ − 1 ( u ) + k ;
(5) expsum c ℓ + 1 ( u ) = expsum c ℓ ( u ) + 1 \operatorname{expsum}_{c_{\ell+1}}(u)=\operatorname{expsum}_{c_\ell}(u)+1 expsum c ℓ + 1 ( u ) = expsum c ℓ ( u ) + 1 . From (1), we have expsum c ℓ + 1 ( u ) = expsum c ℓ + 2 ( u ) = ⋯ \operatorname{expsum}_{c_{\ell+1}}(u)=\operatorname{expsum}_{c_{\ell+2}}(u)=\cdots expsum c ℓ + 1 ( u ) = expsum c ℓ + 2 ( u ) = ⋯ , and so these values must all be 0, as u u u cannot have have infinitely many c i c_i c i with non-zero exponent-sum. Similarly, expsum c − 1 ( u ) = expsum c − 2 ( u ) = ⋯ = 0 \operatorname{expsum}_{c_{-1}}(u)=\operatorname{expsum}_{c_{-2}}(u)=\cdots=0 expsum c − 1 ( u ) = expsum c − 2 ( u ) = ⋯ = 0 . Taken with (2) and (5), these imply that expsum c 0 ( u ) = − k \operatorname{expsum}_{c_0}(u)=-k expsum c 0 ( u ) = − k and expsum c ℓ ( u ) = − 1 \operatorname{expsum}_{c_\ell}(u)=-1 expsum c ℓ ( u ) = − 1 . Then (3) and (4) can be applied to show that expsum c 1 ( u ) = expsum c ℓ − 1 ( u ) = − ( k + 1 ) \operatorname{expsum}_{c_1}(u)=\operatorname{expsum}_{c_{\ell-1}}(u)=-(k+1) expsum c 1 ( u ) = expsum c ℓ − 1 ( u ) = − ( k + 1 ) . Finally, (1) implies that expsum c i ( u ) = − ( k + 1 ) \operatorname{expsum}_{c_i}(u)=-(k+1) expsum c i ( u ) = − ( k + 1 ) for all i ∈ { 1 , … , ℓ − 1 } i\in\{1,\ldots,\ell-1\} i ∈ { 1 , … , ℓ − 1 } . We can conclude that ab ( u q ℓ ) = \operatorname{ab}(uq^\ell)= ab ( u q ℓ ) =
ab ( c 0 − k c 1 − ( k + 1 ) ⋯ c ℓ − 1 − ( k + 1 ) c ℓ − 1 q ℓ ) . \operatorname{ab}\left(c_0^{-k}c_1^{-(k+1)}\cdots c_{\ell-1}^{-(k+1)}c_\ell^{-1}q^\ell\right). ab ( c 0 − k c 1 − ( k + 1 ) ⋯ c ℓ − 1 − ( k + 1 ) c ℓ − 1 q ℓ ) .
Using the fact that c i = q i c q − i c_i=q^icq^{-i} c i = q i c q − i gives
ab ( u q ℓ ) = ab ( c − k ⋅ ∏ i = 1 ℓ − 1 ( q i c − ( k + 1 ) q − i ) ⋅ q ℓ c − 1 q − ℓ q ℓ ) . \operatorname{ab}(uq^\ell)=\operatorname{ab}\left(c^{-k}\cdot\prod_{i=1}^{\ell-1}(q^ic^{-(k+1)}q^{-i})\cdot q^\ell c^{-1}q^{-\ell}q^\ell\right). ab ( u q ℓ ) = ab ( c − k ⋅ i = 1 ∏ ℓ − 1 ( q i c − ( k + 1 ) q − i ) ⋅ q ℓ c − 1 q − ℓ q ℓ ) .
Moving to the original (free-by-cyclic) presentation for G G G via the map q ↦ a − 1 t q\mapsto a^{-1}t q ↦ a − 1 t and c ↦ t c\mapsto t c ↦ t gives
ab ( u q ℓ ) = ab ( t − k ⋅ ∏ i = 1 ℓ − 1 ( a − 1 t ) i t − ( k + 1 ) ( a − 1 t ) − i ⋅ ( a − 1 t ) ℓ t − ℓ ) = ab ( a − ℓ t − k + ℓ − 1 ⋅ ∏ i = 1 ℓ − 1 ( t − ( k + 1 ) ) ) = ab ( a − ℓ t ℓ − ( k + 1 ) − ( ℓ − 1 ) ( k + 1 ) ) = ab ( a − ℓ t − k ℓ ) . \begin{aligned}
\operatorname{ab}(uq^\ell)=\operatorname{ab}\left(t^{-k}\cdot\prod_{i=1}^{\ell-1}(a^{-1}t)^i t^{-(k+1)}(a^{-1}t)^{-i}\cdot(a^{-1}t)^\ell t^{-\ell}\right) \\
&=\operatorname{ab}\left(a^{-\ell}t^{-k+\ell-1}\cdot\prod_{i=1}^{\ell-1}\left(t^{-(k+1)}\right)\right) \\
&=\operatorname{ab}\left(a^{-\ell}t^{\ell-(k+1)-(\ell-1)(k+1)}\right) \\
&=\operatorname{ab}\left(a^{-\ell}t^{-k\ell}\right).
\end{aligned} ab ( u q ℓ ) = ab ( t − k ⋅ i = 1 ∏ ℓ − 1 ( a − 1 t ) i t − ( k + 1 ) ( a − 1 t ) − i ⋅ ( a − 1 t ) ℓ t − ℓ ) = ab ( a − ℓ t − k + ℓ − 1 ⋅ i = 1 ∏ ℓ − 1 ( t − ( k + 1 ) ) ) = ab ( a − ℓ t ℓ − ( k + 1 ) − ( ℓ − 1 ) ( k + 1 ) ) = ab ( a − ℓ t − k ℓ ) .
We have thus shown that ab ( C G ( a t k ) ) ⊆ { a ℓ t k ℓ ∣ ℓ ∈ Z } \operatorname{ab}(C_G(at^k))\subseteq\{a^{\ell t^{k\ell}}\mid\ell\in\mathbb{Z}\} ab ( C G ( a t k )) ⊆ { a ℓ t k ℓ ∣ ℓ ∈ Z } . The reverse containment follows since ⟨ a t k ⟩ ⊆ C G ( a t k ) \langle at^k\rangle\subseteq C_G(at^k) ⟨ a t k ⟩ ⊆ C G ( a t k ) and ab ( ⟨ a t k ⟩ ) = { a ℓ t k ℓ ∣ ℓ ∈ Z } \operatorname{ab}(\langle at^k\rangle)=\{a^{\ell t^{k\ell}}\mid\ell\in\mathbb{Z}\} ab (⟨ a t k ⟩) = { a ℓ t k ℓ ∣ ℓ ∈ Z } .
The next lemma gives the D P ( G , ab ) \mathcal{DP}(G,\operatorname{ab}) DP ( G , ab ) -definable sets we will need to encode multiplication of integers into D P ( G , ab ) \mathcal{DP}(G,\operatorname{ab}) DP ( G , ab ) .
Lemma 5.7. Let G = ⟨ a , b , t ∣ t a t − 1 = a b , t b t − 1 = b ⟩ G=\langle a,b,t\mid tat^{-1}=ab,tbt^{-1}=b\rangle G = ⟨ a , b , t ∣ t a t − 1 = ab , t b t − 1 = b ⟩ . Then the following sets are D P ( G , ab ) \mathcal{DP}(G,\operatorname{ab}) DP ( G , ab ) -definable.
(1) ⟨ a , b ⟩ \langle a,b\rangle ⟨ a , b ⟩ ;
(2) { u t k ∈ G ∣ expsum a ( u ) = 0 } \{ut^k\in G\mid\operatorname{expsum}_a(u)=0\} { u t k ∈ G ∣ expsum a ( u ) = 0 } ;
(3) { u t k ∈ G ∣ expsum a ( u ) = k } \{ut^k\in G\mid\operatorname{expsum}_a(u)=k\} { u t k ∈ G ∣ expsum a ( u ) = k } ;
(4) { ( a t k , a ℓ t k ℓ ) ∣ k , ℓ ∈ Z } \{(at^k,a^\ell t^{k\ell})\mid k,\ell\in\mathbb{Z}\} {( a t k , a ℓ t k ℓ ) ∣ k , ℓ ∈ Z } .
Proof. The proofs of the four parts are very similar, relying on information about the abelianisation of several sets, and the fact that ab ( b ) = 1 \operatorname{ab}(b)=1 ab ( b ) = 1 , which follows immediately from the presentation of G G G . Additionally, note that a a a -exponent sums are well-defined, as ab ( G ) = ab ( a ) ⊕ ab ( t ) \operatorname{ab}(G)=\operatorname{ab}(a)\oplus\operatorname{ab}(t) ab ( G ) = ab ( a ) ⊕ ab ( t ) .
For (1), we claim that ⟨ a , b ⟩ = [ G , G ] ⟨ a ⟩ \langle a,b\rangle=[G,G]\langle a\rangle ⟨ a , b ⟩ = [ G , G ] ⟨ a ⟩ . As a product of D P ( G , ab ) \mathcal{DP}(G,\operatorname{ab}) DP ( G , ab ) -definable sets is D P ( G , ab ) \mathcal{DP}(G,\operatorname{ab}) DP ( G , ab ) -definable, and, the latter is D P ( G , ab ) \mathcal{DP}(G,\operatorname{ab}) DP ( G , ab ) -definable (Theorem 5.5(1)), showing this equality thus shows (1). Let u ∈ ⟨ a , b ⟩ u\in\langle a,b\rangle u ∈ ⟨ a , b ⟩ . Then u a − expsum a ( u ) ∈ [ G , G ] ua^{-\operatorname{expsum}_a(u)}\in[G,G] u a − expsum a ( u ) ∈ [ G , G ] , and so u ∈ [ G , G ] ⟨ a ⟩ u\in[G,G]\langle a\rangle u ∈ [ G , G ] ⟨ a ⟩ . Conversely, let u t k a ℓ ∈ [ G , G ] ⟨ a ⟩ ut^ka^\ell\in[G,G]\langle a\rangle u t k a ℓ ∈ [ G , G ] ⟨ a ⟩ . Then k = 0 k=0 k = 0 and expsum a ( u ) = 0 \operatorname{expsum}_a(u)=0 expsum a ( u ) = 0 , and so u t k a ℓ = u a ℓ ∈ ⟨ a , b ⟩ ut^ka^\ell=ua^\ell\in\langle a,b\rangle u t k a ℓ = u a ℓ ∈ ⟨ a , b ⟩ , as required.
For (2), we claim that { u t k ∈ G ∣ expsum a ( u ) = 0 } = [ G , G ] ⟨ t ⟩ \{ut^k\in G\mid\operatorname{expsum}_a(u)=0\}=[G,G]\langle t\rangle { u t k ∈ G ∣ expsum a ( u ) = 0 } = [ G , G ] ⟨ t ⟩ , which is D P ( G , ab ) \mathcal{DP}(G,\operatorname{ab}) DP ( G , ab ) -definable as a product of D P ( G , ab ) \mathcal{DP}(G,\operatorname{ab}) DP ( G , ab ) -definable sets, using Theorem 5.5(4). The proof of this claim is identical to the analogous proof in (1).
For (3), we will show that { u t k ∈ G ∣ expsum a ( u ) = k } = [ G , G ] C G ( a t ) \{ut^k\in G\mid\operatorname{expsum}_a(u)=k\}=[G,G]C_G(at) { u t k ∈ G ∣ expsum a ( u ) = k } = [ G , G ] C G ( a t ) . This suffices, as the latter is a product of two D P ( G , ab ) \mathcal{DP}(G,\operatorname{ab}) DP ( G , ab ) -definable sets. First note that Theorem 5.6 tells us that ab ( C G ( a t ) ) = { a ℓ t ℓ ∣ ℓ ∈ Z } \operatorname{ab}(C_G(at))=\{a^\ell t^\ell\mid\ell\in\mathbb{Z}\} ab ( C G ( a t )) = { a ℓ t ℓ ∣ ℓ ∈ Z } . We now show that { u t k ∈ G ∣ expsum a ( u ) = k } = [ G , G ] C G ( a t ) \{ut^k\in G\mid\operatorname{expsum}_a(u)=k\}=[G,G]C_G(at) { u t k ∈ G ∣ expsum a ( u ) = k } = [ G , G ] C G ( a t ) . This is equivalent to showing that ab ( { u t k ∈ G ∣ expsum a ( u ) = k } ) = ab ( C G ( a t ) ) \operatorname{ab}(\{ut^k\in G\mid\operatorname{expsum}_a(u)=k\})=\operatorname{ab}(C_G(at)) ab ({ u t k ∈ G ∣ expsum a ( u ) = k }) = ab ( C G ( a t )) . But ab ( { u t k ∈ G ∣ expsum a ( u ) = k } ) = { a k t k ∣ k ∈ Z } \operatorname{ab}(\{ut^k\in G\mid\operatorname{expsum}_a(u)=k\})=\{a^kt^k\mid k\in\mathbb{Z}\} ab ({ u t k ∈ G ∣ expsum a ( u ) = k }) = { a k t k ∣ k ∈ Z } , which we have just noted equals ab ( C G ( a t ) ) \operatorname{ab}(C_G(at)) ab ( C G ( a t )) , as required.
It remains to show (4). Let E 1 \mathcal{E}_1 E 1 and E 2 \mathcal{E}_2 E 2 be systems of equations in G G G each with a variable Z 1 Z_1 Z 1 and Z 2 Z_2 Z 2 , respectively, such that the set of solutions to Z i Z_i Z i in E i \mathcal{E}_i E i is ⟨ t ⟩ \langle t\rangle ⟨ t ⟩ , which exists by Theorem 5.5(4). Let F \mathcal{F} F be a system of equations in G G G with a variable V V V such that the set of solutions to V V V is ⟨ a ⟩ \langle a\rangle ⟨ a ⟩ . Next, note that by Theorem 5.6, we have that the set of solutions to ( X , Y ) (X,Y) ( X , Y ) in the system
E 1 ∧ E 2 ∧ ( X = a Z 1 ) ∧ ( U X = X U ) ∧ ( ab ( U ) = ab ( Y ) ) ∧ ( Y = V Z 2 ) \mathcal{E}_1 \land\mathcal{E}_2 \land(X=aZ_1) \land(UX=XU) \land(\operatorname{ab}(U)=\operatorname{ab}(Y)) \land(Y=VZ_2) E 1 ∧ E 2 ∧ ( X = a Z 1 ) ∧ ( U X = X U ) ∧ ( ab ( U ) = ab ( Y )) ∧ ( Y = V Z 2 )
is { ( a t k , a ℓ t k ℓ ) ∣ k , ℓ ∈ Z } \{(at^k,a^\ell t^{k\ell}) \mid k,\ell\in\mathbb{Z}\} {( a t k , a ℓ t k ℓ ) ∣ k , ℓ ∈ Z } , as required. □
We can now prove the main theorem of this section: that D P ( G , ab ) DP(G,\operatorname{ab}) D P ( G , ab ) is undecidable. The proof repeatedly applies Theorem 5.7 to encode Hilbert’s 10th problem in the ring of integers into D P ( G , ab ) DP(G,\operatorname{ab}) D P ( G , ab ) .
Theorem 5.8. Let G = ⟨ a , b , t ∣ t a t − 1 = a b , t b t − 1 = b ⟩ G=\langle a,b,t\mid tat^{-1}=ab,\ tbt^{-1}=b\rangle G = ⟨ a , b , t ∣ t a t − 1 = ab , t b t − 1 = b ⟩ . Then D P ( G , ab ) DP(G,\operatorname{ab}) D P ( G , ab ) is undecidable
Proof. We show that Hilbert’s 10th problem over the ring of integers reduces to D P ( G , ab ) DP(G,\operatorname{ab}) D P ( G , ab ) . The copy of Z \mathbb{Z} Z in G G G we use is ⟨ a ⟩ \langle a\rangle ⟨ a ⟩ , which is D P ( G , ab ) DP(G,\operatorname{ab}) D P ( G , ab ) -definable by Theorem 5.5(1). To encode Hilbert’s 10th problem in Z \mathbb{Z} Z , it suffices to encode the two types of equation U + V = W U+V=W U + V = W and U V = W UV=W U V = W , where U U U , V V V and W W W can be either variables or constants. Addition is immediate: we simply define new variables/constants X U X_U X U , X V X_V X V and X W X_W X W , by X U = a U X_U=a^U X U = a U if U U U is a constant and then add the constraints X U ∈ ⟨ a ⟩ X_U\in\langle a\rangle X U ∈ ⟨ a ⟩ (which is D P ( G , ab ) DP(G,\operatorname{ab}) D P ( G , ab ) -definable) if U U U is a variable, along with the analogous statements for V V V and W W W , and then add the equation X U X V = X W X_U X_V=X_W X U X V = X W .
Multiplication requires the application of Theorem 5.7. We achieve this by intersecting various sets we know to be D P ( G , ab ) DP(G,\operatorname{ab}) D P ( G , ab ) -definable. We have from Theorem 5.5(1) and (4), that { ( a i , a j , a m , a t k , a ℓ t k ℓ ) ∣ i , j , k , ℓ , m ∈ Z } \{(a^i,a^j,a^m,at^k,a^\ell t^{k\ell})\mid i,j,k,\ell,m\in\mathbb{Z}\} {( a i , a j , a m , a t k , a ℓ t k ℓ ) ∣ i , j , k , ℓ , m ∈ Z } is D P ( G , ab ) DP(G,\operatorname{ab}) D P ( G , ab ) -definable. So let X 1 X_1 X 1 , X 2 X_2 X 2 , X 3 X_3 X 3 , X 4 X_4 X 4 and X 5 X_5 X 5 be variables in a system E \mathcal{E} E of equations with abelianisation constraints in G G G such that the set of solutions to ( X 1 , X 2 , X 3 , X 4 , X 5 ) (X_1,X_2,X_3,X_4,X_5) ( X 1 , X 2 , X 3 , X 4 , X 5 ) in E \mathcal{E} E is the stated set. We then add the additional D P ( G , ab ) DP(G,\operatorname{ab}) D P ( G , ab ) -definable constraints to E \mathcal{E} E :
X 1 ( a − 1 X 4 ) − 1 ∈ { u t r ∈ G ∣ expsum a ( u ) = r } X_1(a^{-1}X_4)^{-1}\in\{ut^r\in G\mid\operatorname{expsum}_a(u)=r\} X 1 ( a − 1 X 4 ) − 1 ∈ { u t r ∈ G ∣ expsum a ( u ) = r } ;
X 2 X 5 − 1 ∈ { u t r ∈ G ∣ expsum a ( u ) = 0 } X_2X_5^{-1}\in\{ut^r\in G\mid\operatorname{expsum}_a(u)=0\} X 2 X 5 − 1 ∈ { u t r ∈ G ∣ expsum a ( u ) = 0 } ;
X 3 ( X 2 − 1 X 5 ) − 1 ∈ { u t r ∈ G ∣ expsum a ( u ) = r } X_3(X_2^{-1}X_5)^{-1}\in\{ut^r\in G\mid\operatorname{expsum}_a(u)=r\} X 3 ( X 2 − 1 X 5 ) − 1 ∈ { u t r ∈ G ∣ expsum a ( u ) = r } .
The constraints are all D P ( G , ab ) DP(G,\operatorname{ab}) D P ( G , ab ) -definable, by Theorem 5.7(2) and (3). Furthermore, (i) is equivalent to i = k i=k i = k , (ii) is equivalent to j = ℓ j=\ell j = ℓ , and given (ii), (iii) is equivalent to m = k ℓ m=k\ell m = k ℓ . Thus with these additional constraints the set of solutions to ( X 1 , X 2 , X 3 ) (X_1,X_2,X_3) ( X 1 , X 2 , X 3 ) is { a k , a ℓ , a k ℓ ∣ k , ℓ ∈ Z } \{a^k,a^\ell,a^{k\ell}\mid k,\ell\in\mathbb{Z}\} { a k , a ℓ , a k ℓ ∣ k , ℓ ∈ Z } . We have thus defined multiplication using the Diophantine Problem with abelianisations constraints in G G G . The undecidability of D P ( G , ab ) DP(G,\operatorname{ab}) D P ( G , ab ) now follows from the undecidability of Hilbert’s 10th problem over the ring of integers [43 ] . □
Cyclically pinched groups
In this section we fully classify which cyclically pinched groups have decidable Diophantine Problems with abelianisation constraints. A cyclically pinched group G G G is a free product of two finite rank free groups amalgamated over an infinite cyclic group; that is,
G = F ( a 1 , … , a n ) ∗ Z F ( b 1 , … , b m ) , G=F(a_1,\ldots,a_n)*_{\mathbb{Z}}F(b_1,\ldots,b_m), G = F ( a 1 , … , a n ) ∗ Z F ( b 1 , … , b m ) ,
and the amalgamation is of the form ⟨ u ⟩ = ⟨ v ⟩ ≅ Z \langle u\rangle=\langle v\rangle\cong\mathbb{Z} ⟨ u ⟩ = ⟨ v ⟩ ≅ Z , where u ∈ F ( a 1 , … , a n ) u\in F(a_1,\ldots,a_n) u ∈ F ( a 1 , … , a n ) and v ∈ F ( b 1 , … , b m ) v\in F(b_1,\ldots,b_m) v ∈ F ( b 1 , … , b m ) are non-trivial. As we will show, the only case when cyclically pinched groups have a decidable Diophantine Problem with abelianisation constraints is when they have only two generators, and are thus one-relator groups with centre. This allows us to apply results from Section 3.
A fairly straightforward combination of existing results, gives that the Diophantine Problem (without constraints) is decidable in all cyclically pinched groups.
Corollary 1.8. The existential theory (and hence Diophantine Problem) is decidable in all cyclically pinched groups.
Proof. Let G = F ( a 1 , … , a m ) ∗ Z F ( b 1 , … , b m ) G=F(a_1,\ldots,a_m)*_{\mathbb{Z}}F(b_1,\ldots,b_m) G = F ( a 1 , … , a m ) ∗ Z F ( b 1 , … , b m ) be a cyclically pinched group across words u u u and v v v . If at least one of u u u and v v v is not a power, then G G G is hyperbolic by [6 Corollary (2), page 99] so we can apply [20 Theorem 1] to conclude that D P ( G ) DP(G) D P ( G ) is decidable. If u u u and v v v are both powers, then write u = u ˉ p u=\bar{u}^p u = u ˉ p and v = v ˉ q v=\bar{v}^q v = v ˉ q with u ˉ ∈ F ( a 1 , … , a n ) \bar{u}\in F(a_1,\ldots,a_n) u ˉ ∈ F ( a 1 , … , a n ) and v ˉ ∈ F ( b 1 , … , b m ) \bar{v}\in F(b_1,\ldots,b_m) v ˉ ∈ F ( b 1 , … , b m ) . Then
G = F ( a 1 , … , a n ) ∗ ⟨ u ˉ ⟩ ⟨ u ˉ , v ˉ ∣ u ˉ p = v ˉ q ⟩ ∗ ⟨ v ˉ ⟩ F ( b 1 , … , b m ) . G=F(a_1,\ldots,a_n)*_{\langle\bar{u}\rangle}\langle\bar{u},\bar{v}\mid\bar{u}^p=\bar{v}^q\rangle*_{\langle\bar{v}\rangle}F(b_1,\ldots,b_m). G = F ( a 1 , … , a n ) ∗ ⟨ u ˉ ⟩ ⟨ u ˉ , v ˉ ∣ u ˉ p = v ˉ q ⟩ ∗ ⟨ v ˉ ⟩ F ( b 1 , … , b m ) .
By Dahmani’s combination theorem [18 Theorem 0.1] , G G G is hyperbolic relative to free groups and the middle torus knot group. We have that the existential theory in free groups is decidable (see for example [20 Theorem 1] ), and the torus knot group is a one-relator group with centre, and thus by Theorem 3.2 is a finite-index subgroup of a group that is virtually a direct product of hyperbolic groups, and so also has a decidable existential theory, by [15 Theorem 3.1] . Hence all parabolic groups are torsion-free and have decidable existential theories, and so we can apply [19 Theorem 0.1] to conclude that the existential theory (and hence Diophantine Problem) of G G G is decidable. □
As with many proofs of undecidability of Diophantine-like problems, we begin by computing various centralisers.
Lemma 6.1. Let G = ⟨ a 1 , … , a r , b 1 , … , b r ∣ u = v ⟩ G = \langle a_1,\ldots,a_r,b_1,\ldots,b_r \mid u=v\rangle G = ⟨ a 1 , … , a r , b 1 , … , b r ∣ u = v ⟩ , where u ∈ { a 1 , a 1 − 1 , … , a n , a n − 1 } ∗ u \in\{a_1,a_1^{-1},\ldots,a_n,a_n^{-1}\}^* u ∈ { a 1 , a 1 − 1 , … , a n , a n − 1 } ∗ and v ∈ { b 1 , b 1 − 1 , … , b s , b s − 1 } ∗ v \in\{b_1,b_1^{-1},\ldots,b_s,b_s^{-1}\}^* v ∈ { b 1 , b 1 − 1 , … , b s , b s − 1 } ∗ be such that r ≥ 2 r \ge2 r ≥ 2 , s ≥ 1 s \ge1 s ≥ 1 and u u u is cyclically reduced and not a power of a 1 a_1 a 1 or a 2 a_2 a 2 . Then
(1) C G ( a 1 ) = ⟨ a 1 ⟩ C_G(a_1)=\langle a_1\rangle C G ( a 1 ) = ⟨ a 1 ⟩ ;
(2) C G ( a 2 ) = ⟨ a 2 ⟩ C_G(a_2)=\langle a_2\rangle C G ( a 2 ) = ⟨ a 2 ⟩ ;
(3) At least one of the following holds:
(a) There exists q ∈ Z q \in\mathbb{Z} q ∈ Z such that for all k ∈ Z ∖ { q } k \in\mathbb{Z}\setminus\{q\} k ∈ Z ∖ { q } , we have C G ( a 1 a 2 k ) = ⟨ a 1 a 2 k ⟩ C_G(a_1a_2^k)=\langle a_1a_2^k\rangle C G ( a 1 a 2 k ) = ⟨ a 1 a 2 k ⟩ . In addition, C G ( a 1 2 a 2 2 ) = ⟨ a 1 2 a 2 2 ⟩ C_G(a_1^2a_2^2)=\langle a_1^2a_2^2\rangle C G ( a 1 2 a 2 2 ) = ⟨ a 1 2 a 2 2 ⟩ ;
(b) C G ( a 1 a 2 k ) = ⟨ a 1 a 2 k ⟩ C_G(a_1a_2^k)=\langle a_1a_2^k\rangle C G ( a 1 a 2 k ) = ⟨ a 1 a 2 k ⟩ for all k ∈ Z k \in\mathbb{Z} k ∈ Z .
Proof. For (1) ((2) is symmetric), we must first show that a 1 a_1 a 1 is not conjugate (in ⟨ a 1 , … , a r ⟩ \langle a_1,\ldots,a_r\rangle ⟨ a 1 , … , a r ⟩ ) to any element in ⟨ u ⟩ \langle u\rangle ⟨ u ⟩ . But if it were, then there would exist g ∈ ⟨ a 1 , … , a r ⟩ g \in\langle a_1,\ldots,a_r\rangle g ∈ ⟨ a 1 , … , a r ⟩ and k ∈ Z ∖ { 0 } k \in\mathbb{Z}\setminus\{0\} k ∈ Z ∖ { 0 } satisfying g u k g − 1 = a 1 gu^kg^{-1}=a_1 g u k g − 1 = a 1 . It follows that a 1 a_1 a 1 is a k k k th power, and so k = ± 1 k=\pm1 k = ± 1 . Thus g u g − 1 = a 1 ± 1 gug^{-1}=a_1^{\pm1} g u g − 1 = a 1 ± 1 , and so u u u is conjugate to a power of a 1 a_1 a 1 , contradicting the fact that u u u is cyclically reduced and not a power of a 1 a_1 a 1 . Thus a 1 a_1 a 1 is not conjugate to any element in ⟨ u ⟩ \langle u\rangle ⟨ u ⟩ . We can therefore apply [3 Proposition 2.3] to conclude that C G ( a 1 ) = C ⟨ a 1 , … , a r ⟩ ( a 1 ) = ⟨ a 1 ⟩ C_G(a_1)=C_{\langle a_1,\ldots,a_r\rangle}(a_1)=\langle a_1\rangle C G ( a 1 ) = C ⟨ a 1 , … , a r ⟩ ( a 1 ) = ⟨ a 1 ⟩ .
For (3), noting that u u u is cyclically reduced, we have two cases: either u u u is conjugate to a power of a 1 a 2 q a_1a_2^q a 1 a 2 q , or it is not. If it is not, then we can apply the same argument we used to show C G ( a 1 ) = ⟨ a 1 ⟩ C_G(a_1)=\langle a_1\rangle C G ( a 1 ) = ⟨ a 1 ⟩ to conclude that a 1 a 2 q a_1a_2^q a 1 a 2 q is not conjugate to a power of u u u , and hence by [3 Proposition 2.3] , C G ( a 1 a 2 ) = C ⟨ a 1 , … , a r ⟩ ( a 1 a 2 ) = ⟨ a 1 a 2 ⟩ C_G(a_1a_2)=C_{\langle a_1,\ldots,a_r\rangle}(a_1a_2)=\langle a_1a_2\rangle C G ( a 1 a 2 ) = C ⟨ a 1 , … , a r ⟩ ( a 1 a 2 ) = ⟨ a 1 a 2 ⟩ . Otherwise, we have that u = g ( a 1 a 2 q ) g − 1 u=g(a_1a_2^q)g^{-1} u = g ( a 1 a 2 q ) g − 1 . In this case, noting that non-trivial powers of a 1 a 2 2 a_1a_2^2 a 1 a 2 2 and a 1 a 2 k a_1a_2^k a 1 a 2 k for k ∈ Z ∖ { q } k\in\mathbb{Z}\setminus\{q\} k ∈ Z ∖ { q } are never conjugate in ⟨ a 1 , … , a r ⟩ \langle a_1,\ldots,a_r\rangle ⟨ a 1 , … , a r ⟩ , we have that u u u is not conjugate to a power of a 1 a 2 k a_1a_2^k a 1 a 2 k for all k ∈ Z ∖ { q } k\in\mathbb{Z}\setminus\{q\} k ∈ Z ∖ { q } . Applying exactly the same argument again, we can conclude that C G ( a 1 a 2 k ) = C ⟨ a 1 , … , a r ⟩ ( a 1 a 2 k ) = ⟨ a 1 a 2 k ⟩ C_G(a_1a_2^k)=C_{\langle a_1,\ldots,a_r\rangle}(a_1a_2^k)=\langle a_1a_2^k\rangle C G ( a 1 a 2 k ) = C ⟨ a 1 , … , a r ⟩ ( a 1 a 2 k ) = ⟨ a 1 a 2 k ⟩ . □
We next show that the Diophantine Problem with abelianisation constraints is undecidable for a large class of cyclically pinched groups whose presentations satisfy various conditions. As we will see later, it turns out that almost all cyclically pinched groups are isomorphic to one of these. The proof uses the sets we showed were definable as centralisers, together with the commutator subgroup to encode Hilbert’s 10th problem over the ring of integers into the Diophantine Problem with abelianisation constraints of our cyclically pinched group.
Proposition 6.2. Let G = ⟨ a 1 , … , a r , b 1 , … , b s ∣ u = v ⟩ G=\langle a_1,\ldots,a_r,b_1,\ldots,b_s\mid u=v\rangle G = ⟨ a 1 , … , a r , b 1 , … , b s ∣ u = v ⟩ , where u ∈ { a 1 , a 1 − 1 , … , a n , a n − 1 } ∗ u\in\{a_1,a_1^{-1},\ldots,a_n,a_n^{-1}\}^* u ∈ { a 1 , a 1 − 1 , … , a n , a n − 1 } ∗ and v ∈ { b 1 , b 1 − 1 , … , b s , b s − 1 } ∗ v\in\{b_1,b_1^{-1},\ldots,b_s,b_s^{-1}\}^* v ∈ { b 1 , b 1 − 1 , … , b s , b s − 1 } ∗ are such that r ≥ 2 r\ge2 r ≥ 2 , s ≥ 1 s\ge1 s ≥ 1 and u u u is cyclically reduced and not a power of a 1 a_1 a 1 or a 2 a_2 a 2 . Then D P ( G , a b ) DP(G,\mathrm{ab}) D P ( G , ab ) is undecidable.
Proof. We encode the integers together with addition and the squaring map into G G G via the cyclic subgroup ⟨ a 2 ⟩ \langle a_2\rangle ⟨ a 2 ⟩ . This can encode multiplication, and thus Hilbert’s 10th problem over Z \mathbb{Z} Z , since for all x , y ∈ Z x,y\in\mathbb{Z} x , y ∈ Z we have ( x + y ) 2 = x 2 + 2 x y + y 2 (x+y)^2=x^2+2xy+y^2 ( x + y ) 2 = x 2 + 2 x y + y 2 , and so the equations X Y = Z XY=Z X Y = Z and 2 Z + X 2 + Y 2 = ( X + Y ) 2 2Z+X^2+Y^2=(X+Y)^2 2 Z + X 2 + Y 2 = ( X + Y ) 2 are equivalent. Since Hilbert’s 10th problem over the ring Z \mathbb{Z} Z is undecidable [43 ] , encoding this will give the desired undecidability.
First note that ⟨ a 2 ⟩ \langle a_2\rangle ⟨ a 2 ⟩ is D P ( G , a b ) DP(G,\mathrm{ab}) D P ( G , ab ) -definable, as a centraliser, by Theorem 6.1(2). Encoding addition of integers realised as powers of a 2 a_2 a 2 can be done using products in this cyclic subgroup; that is, the equation Z 1 + Z 2 = Z 3 Z_1+Z_2=Z_3 Z 1 + Z 2 = Z 3 in Z \mathbb{Z} Z can be encoded by X 1 X 2 = X 3 X_1X_2=X_3 X 1 X 2 = X 3 , with the constraints X 1 , X 2 , X 3 ∈ ⟨ a 2 ⟩ X_1,X_2,X_3\in\langle a_2\rangle X 1 , X 2 , X 3 ∈ ⟨ a 2 ⟩ . Since these sets are D P ( G , a b ) \mathcal{D}\mathcal{P}(G,\mathbf{ab}) DP ( G , ab ) -definable, this is all D P ( G , a b ) \mathcal{D}\mathcal{P}(G,\mathbf{ab}) DP ( G , ab ) -definable. To deal with the case that some of Z 1 Z_1 Z 1 , Z 2 Z_2 Z 2 and Z 3 Z_3 Z 3 are constants, we just replace X i X_i X i with the constant a 2 Z i a_2^{Z_i} a 2 Z i .
We now encode the squaring unary operation (on the ring Z \mathbb{Z} Z ). If q q q from Theorem 6.1(3)(a) exists, define p = ( q + 1 ) m o d 2 p=(q+1)\bmod2 p = ( q + 1 ) mod 2 . If q q q doesn’t exist (that is, we are in case (b)), simply set p = 0 p=0 p = 0 . We define a system of equations with abelianisation constraints in G G G to show that the set { ( a 2 2 i + p , a 2 j , a 2 ( 2 i + p ) j ) ∣ i , j ∈ Z } \{(a_2^{2i+p},a_2^j,a_2^{(2i+p)j})\mid i,j\in\mathbb{Z}\} {( a 2 2 i + p , a 2 j , a 2 ( 2 i + p ) j ) ∣ i , j ∈ Z } is D P ( G , a b ) \mathcal{D}\mathcal{P}(G,\mathbf{ab}) DP ( G , ab ) -definable. Consider the system
( T a 2 = a 2 T ) ∧ (2) (Ta_2=a_2T)\wedge \tag*{(2)} ( T a 2 = a 2 T ) ∧ (2)
( X = T 2 a 2 p ) ∧ (3) (X=T^2a_2^p)\wedge \tag*{(3)} ( X = T 2 a 2 p ) ∧ (3)
( Y ( a 1 X ) = ( a 1 X ) Y ) ∧ (4) (Y(a_1X)=(a_1X)Y)\wedge \tag*{(4)} ( Y ( a 1 X ) = ( a 1 X ) Y ) ∧ (4)
( U a 1 = a 1 U ) ∧ (5) (Ua_1=a_1U)\wedge \tag*{(5)} ( U a 1 = a 1 U ) ∧ (5)
( V a 2 = a 2 V ) ∧ (6) (Va_2=a_2V)\wedge \tag*{(6)} ( V a 2 = a 2 V ) ∧ (6)
( a b ( Y ) = a b ( U V ) ) ∧ (7) (\mathbf{ab}(Y)=\mathbf{ab}(UV))\wedge \tag*{(7)} ( ab ( Y ) = ab ( U V )) ∧ (7)
\begin{cases}
Wa_1a_2=a_1a_2W & q\ne1\text{ or }q\text{ does not exist}\\
Wa_1^2a_2^2=a_1^2a_2^2W & q=1
\end{cases}
\wedge \tag*{(8)}\end{cases}
( S a 2 = a 2 S ) ∧ (9) (Sa_2=a_2S)\wedge \tag*{(9)} ( S a 2 = a 2 S ) ∧ (9)
\begin{cases}
Z=S & q\ne1\text{ or }q\text{ does not exist}\\
Z=S^2 & q=1
\end{cases}
\wedge \tag*{(10)}\end{cases}
( a b ( W ) = a b ( U Z ) ) . (11) (\mathbf{ab}(W)=\mathbf{ab}(UZ)). \tag*{(11)} ( ab ( W ) = ab ( U Z )) . (11)
We claim that the set of solutions to ( X , Z , V ) (X,Z,V) ( X , Z , V ) is { ( a 2 2 i + p , a 2 j , a 2 ( 2 i + p ) j ) ∣ i , j ∈ Z } \{(a_2^{2i+p},a_2^j,a_2^{(2i+p)j})\mid i,j\in\mathbb{Z}\} {( a 2 2 i + p , a 2 j , a 2 ( 2 i + p ) j ) ∣ i , j ∈ Z } . Using the centraliser descriptions of G G G from Theorem 6.1(1) and (2), we have that the solutions to X X X from (2) and (3) are { a 2 2 i + p ∣ i ∈ Z } \{a_2^{2i+p}\mid i\in\mathbb{Z}\} { a 2 2 i + p ∣ i ∈ Z } , and so the solutions to ( X , Y ) (X,Y) ( X , Y ) from (2), (3) and (4) are { ( a 2 2 i + p , ( a 1 a 2 2 i + p ) j ) ∣ i , j ∈ Z } \{(a_2^{2i+p},(a_1a_2^{2i+p})^j)\mid i,j\in\mathbb{Z}\} {( a 2 2 i + p , ( a 1 a 2 2 i + p ) j ) ∣ i , j ∈ Z } .
We can again use the centraliser descriptions to see that the solutions to (5) and (6) are ⟨ a 1 ⟩ \langle a_1\rangle ⟨ a 1 ⟩ and ⟨ a 2 ⟩ \langle a_2\rangle ⟨ a 2 ⟩ , respectively. Combining these with (7) along with the fact that the solutions to ( X , Y ) (X,Y) ( X , Y ) from (2), (3) and (4) are { ( a 2 2 i + p , ( a 1 a 2 2 i + p ) j ) ∣ i , j ∈ Z } \{(a_2^{2i+p},(a_1a_2^{2i+p})^j)\mid i,j\in\mathbb{Z}\} {( a 2 2 i + p , ( a 1 a 2 2 i + p ) j ) ∣ i , j ∈ Z } , gives that the set of solutions to ( X , Y , U , V ) (X,Y,U,V) ( X , Y , U , V ) from these equations is
{ ( a 2 2 i + p , ( a 1 a 2 2 i + p ) j , a 1 j , a 2 ( 2 i + p ) j ) ∣ i , j ∈ Z } . \{(a_2^{2i+p},(a_1a_2^{2i+p})^j,a_1^j,a_2^{(2i+p)j})\mid i,j\in\mathbb{Z}\}. {( a 2 2 i + p , ( a 1 a 2 2 i + p ) j , a 1 j , a 2 ( 2 i + p ) j ) ∣ i , j ∈ Z } .
At this point we very nearly have that the claimed set is D P ( G , a b ) \mathcal{D}\mathcal{P}(G,\mathbf{ab}) DP ( G , ab ) -definable, except that the j j j appears as the exponent of a 1 a_1 a 1 , rather that a 2 a_2 a 2 . The remaining equations deal with this, but ‘copying’ the exponent of U U U onto a 2 a_2 a 2 within the exponent of Z Z Z . To see this, note that regardless of the existence or value of q q q , the equations (8), (9), (10) and (11) imply that the set of solutions to Z Z Z is contained in ⟨ a 2 ⟩ \langle a_2\rangle ⟨ a 2 ⟩ and a 2 j a_2^j a 2 j is a solution to Z Z Z if and only if a 1 j a_1^j a 1 j is a solution to U U U . We can conclude that the set of solutions to ( X , Z , V ) (X,Z,V) ( X , Z , V ) in the above system is { ( a 2 2 i + p , a 2 j , a 2 ( 2 i + p ) j ) ∣ i , j ∈ Z } \{(a_2^{2i+p},a_2^j,a_2^{(2i+p)j})\mid i,j\in\mathbb{Z}\} {( a 2 2 i + p , a 2 j , a 2 ( 2 i + p ) j ) ∣ i , j ∈ Z } .
We can now finally encode the squaring function. First, let E \mathcal{E} E be the above system of equations with abelianisation constraints such that the set of solutions to ( X , Z , V ) (X,Z,V) ( X , Z , V ) is { ( a 2 2 i + p , a 2 j , a 2 ( 2 i + p ) j ) ∣ i , j ∈ Z } \{(a_2^{2i+p},a_2^j,a_2^{(2i+p)j})\mid i,j\in\mathbb{Z}\} {( a 2 2 i + p , a 2 j , a 2 ( 2 i + p ) j ) ∣ i , j ∈ Z } . Then consider the system with all equations in E \mathcal{E} E , together with the equation that X = Z 2 a 2 p X=Z^2a_2^p X = Z 2 a 2 p . Then the set of solutions to ( X , Z , V ) (X,Z,V) ( X , Z , V ) in this new system is { ( a 2 2 j + p , a 2 j , a 2 4 j 2 + 4 p j + p 2 ) ∣ j ∈ Z } \{(a_2^{2j+p},a_2^j,a_2^{4j^2+4pj+p^2})\mid j\in\mathbb{Z}\} {( a 2 2 j + p , a 2 j , a 2 4 j 2 + 4 p j + p 2 ) ∣ j ∈ Z } . Further adding the equation 4 Z 2 + 4 p Z + p 2 = V 4Z_2+4pZ+p^2=V 4 Z 2 + 4 pZ + p 2 = V , where Z 2 Z_2 Z 2 is a new variable, gives that the set of solutions to ( Z , Z 2 ) (Z,Z_2) ( Z , Z 2 ) is { ( a 2 j , a 2 j 2 ) ∣ j ∈ Z } \{(a_2^j,a_2^{j^2})\mid j\in\mathbb{Z}\} {( a 2 j , a 2 j 2 ) ∣ j ∈ Z } . We have now encoded Z \mathbb{Z} Z with addition and squaring into D P ( G , a b ) \mathcal{D}\mathcal{P}(G,\mathbf{ab}) DP ( G , ab ) , which as discussed at the beginning of this proof is enough to encode Hilbert’s 10th problem over Z \mathbb{Z} Z , and thus conclude undecidability. □
We can now prove our classification of Diophantine Problems with abelianisation constraints in cyclically pinched groups. The proof relies heavily on Theorem 6.2 and the decidability of the Diophantine Problem with abelianisation constraints in one-relator groups with centre and virtually cyclic abelianisation Theorem 1.3. Most of the proof shows that all cyclically pinched groups that are not ‘obviously’ one-relator groups with centre, do in fact lie in the class studied in Theorem 6.2.
Theorem 1.9. Let G G G be a cyclically pinched group. Then D P ( G , a b ) \mathcal{D}\mathcal{P}(G,\mathrm{ab}) DP ( G , ab ) is decidable if and only if G G G has exactly two generators. In the case that G G G has two generators, D P ( G , a b ) \mathcal{D}\mathcal{P}(G,\mathrm{ab}) DP ( G , ab ) is E D T 0 L \mathrm{EDT0L} EDT0L .
Proof. Case 1: G G G has two generators. Then G G G is a one-relator group with centre, with the presentation
⟨ a 1 , b 1 ∣ a 1 p = b 1 q ⟩ , \langle a_1,b_1 \mid a_1^p=b_1^q\rangle, ⟨ a 1 , b 1 ∣ a 1 p = b 1 q ⟩ ,
for some p , q ∈ Z p,q\in\mathbb{Z} p , q ∈ Z . If p ≠ 1 p\ne1 p = 1 or q ≠ 1 q\ne1 q = 1 , then G G G has a virtually cyclic abelianisation, and so Theorem 1.3 tells us that D P ( G , a b ) \mathcal{D}\mathcal{P}(G,\mathrm{ab}) DP ( G , ab ) is decidable (and E D T 0 L \mathrm{EDT0L} EDT0L ). Otherwise, p = q = 1 p=q=1 p = q = 1 , and so G ≅ Z 2 G\cong\mathbb{Z}^2 G ≅ Z 2 . As an abelian group, abelianisation constraints in Z 2 \mathbb{Z}^2 Z 2 are trivial, and so D P ( Z 2 , a b ) \mathcal{D}\mathcal{P}(\mathbb{Z}^2,\mathrm{ab}) DP ( Z 2 , ab ) is decidable (and E D T 0 L \mathrm{EDT0L} EDT0L ; see for example [29 Corollary 3.13] ).
Case 2: G G G has at least three generators. Then G G G has the presentation
⟨ a 1 , … , a r , b 1 , … , b s ∣ u = v ⟩ , \langle a_1,\ldots,a_r,b_1,\ldots,b_s \mid u=v\rangle, ⟨ a 1 , … , a r , b 1 , … , b s ∣ u = v ⟩ ,
where r ≥ 2 r\ge2 r ≥ 2 , s ≥ 1 s\ge1 s ≥ 1 , u ∈ { a 1 , a 1 − 1 , … , a r , a r − 1 } ∗ u\in\{a_1,a_1^{-1},\ldots,a_r,a_r^{-1}\}^{*} u ∈ { a 1 , a 1 − 1 , … , a r , a r − 1 } ∗ and v ∈ { b 1 , b 1 − 1 , … , b s , b s − 1 } ∗ v\in\{b_1,b_1^{-1},\ldots,b_s,b_s^{-1}\}^{*} v ∈ { b 1 , b 1 − 1 , … , b s , b s − 1 } ∗ . We first show that we can assume without loss of generality that u u u is cyclically reduced. Suppose that u ≡ x w x − 1 u\equiv xwx^{-1} u ≡ x w x − 1 , for some freely reduced words x , w ∈ { a 1 , a 1 − 1 , … , a r , a r − 1 } ∗ x,w\in\{a_1,a_1^{-1},\ldots,a_r,a_r^{-1}\}^{*} x , w ∈ { a 1 , a 1 − 1 , … , a r , a r − 1 } ∗ , with w w w cyclically reduced. For each i ∈ { 1 , … , r } i\in\{1,\ldots,r\} i ∈ { 1 , … , r } , apply the Tietze transformation to the presentation ⟨ a 1 , … , a r , b 1 , … , b s ∣ x w x − 1 = v ⟩ \langle a_1,\ldots,a_r,b_1,\ldots,b_s\mid xwx^{-1}=v\rangle ⟨ a 1 , … , a r , b 1 , … , b s ∣ x w x − 1 = v ⟩ that introduces the redundant generator c i = x a i x − 1 c_i=xa_ix^{-1} c i = x a i x − 1 . Then G G G has the presentation:
⟨ a 1 , … , a r , c 1 , … , c r , b 1 , … , b s ∣ c i = x a i x − 1 , w ˉ = v ⟩ , \langle a_1,\ldots,a_r,c_1,\ldots,c_r,b_1,\ldots,b_s\mid c_i=xa_ix^{-1},\ \bar{w}=v\rangle, ⟨ a 1 , … , a r , c 1 , … , c r , b 1 , … , b s ∣ c i = x a i x − 1 , w ˉ = v ⟩ ,
where w ˉ \bar{w} w ˉ is the word obtained from w w w by replacing each occurrence of a i a_i a i with c i c_i c i . Then w ˉ \bar{w} w ˉ is cyclically reduced. In addition, we can now apply the Tietze transformation that removes the redundant generators a i = x − 1 c i x a_i=x^{-1}c_ix a i = x − 1 c i x for all i i i , giving the following presentation for G G G :
⟨ c 1 , … , c r , b 1 , … , b s ∣ w ˉ = v ⟩ . \langle c_1,\ldots,c_r,b_1,\ldots,b_s\mid\bar{w}=v\rangle. ⟨ c 1 , … , c r , b 1 , … , b s ∣ w ˉ = v ⟩ .
This is a cyclically pinched presentation where the first of the two equal words is cyclically reduced. By returning to our original notation of a i a_i a i s and u u u , we can now assume without loss of generality that u u u is cyclically reduced.
Since u u u is cyclically reduced and the only cyclic permutations of powers of a 1 a_1 a 1 and a 2 a_2 a 2 are themselves powers of a 1 a_1 a 1 and a 2 a_2 a 2 , we have that u u u is conjugate to a power of a 1 a_1 a 1 or a 2 a_2 a 2 if and only if u u u is equal to a power of a 1 a_1 a 1 or a 2 a_2 a 2 . Thus if u u u is not equal to a power of a 1 a_1 a 1 or a 2 a_2 a 2 , we can apply Theorem 6.2 to conclude that D P ( G , a b ) \mathcal{D}\mathcal{P}(G,\mathrm{ab}) DP ( G , ab ) is undecidable. So now suppose that u u u is a power of a 1 a_1 a 1 or a 2 a_2 a 2 ; without loss of generality suppose u = a 1 p u=a_1^p u = a 1 p , where p ∈ Z ∖ { 0 } p\in\mathbb{Z}\setminus\{0\} p ∈ Z ∖ { 0 } . If r > 2 r>2 r > 2 then applying the Tietze transformation that swaps the labels a 1 a_1 a 1 and a 3 a_3 a 3 gives an isomorphic presentation where u u u is not a power of a 1 a_1 a 1 or a 2 a_2 a 2 , and so Theorem 6.2 can be applied to give undecidability. Similarly, if s > 1 s>1 s > 1 , then either v v v is a power of some b i b_i b i , in which case swapping the labels a 1 a_1 a 1 and b 2 b_2 b 2 also gives undecidability; otherwise v v v is not a power of b 1 b_1 b 1 or b 2 b_2 b 2 , in which case swapping the labels a 1 a_1 a 1 with b 1 b_1 b 1 and a 2 a_2 a 2 with b 2 b_2 b 2 gives undecidability. This leaves the case where r = 2 r=2 r = 2 and s = 1 s=1 s = 1 ; that is G G G has the presentation
⟨ a 1 , a 2 , b 1 ∣ a 1 p = b 1 q ⟩ , \langle a_1,a_2,b_1\mid a_1^p=b_1^q\rangle, ⟨ a 1 , a 2 , b 1 ∣ a 1 p = b 1 q ⟩ ,
where q ∈ Z ∖ { 0 } q\in\mathbb{Z}\setminus\{0\} q ∈ Z ∖ { 0 } . Now apply a Tietze transformation introducing the new generator c = a 1 a 2 − 1 c=a_1a_2^{-1} c = a 1 a 2 − 1 . Thus G ≅ ⟨ a 1 , a 2 , b 1 , c ∣ a 1 p = b 1 q , c = a 1 a 2 − 1 ⟩ G\cong\langle a_1,a_2,b_1,c\mid a_1^p=b_1^q,c=a_1a_2^{-1}\rangle G ≅ ⟨ a 1 , a 2 , b 1 , c ∣ a 1 p = b 1 q , c = a 1 a 2 − 1 ⟩ . Since a 1 = c a 2 a_1=ca_2 a 1 = c a 2 , we can apply a Tietze transformation removing the redundant generator a 1 a_1 a 1 , giving G ≅ ⟨ a 2 , b 1 , c ∣ ( c a 2 ) p = b 1 q ⟩ G\cong\langle a_2,b_1,c\mid(ca_2)^p=b_1^q\rangle G ≅ ⟨ a 2 , b 1 , c ∣ ( c a 2 ) p = b 1 q ⟩ . Finally, applying the Tietze transformation that renames c c c to be a 1 a_1 a 1 , gives that G ≅ ⟨ a 1 , a 2 , b 1 ∣ ( a 1 a 2 ) p = b 1 q ⟩ G\cong\langle a_1,a_2,b_1\mid(a_1a_2)^p=b_1^q\rangle G ≅ ⟨ a 1 , a 2 , b 1 ∣ ( a 1 a 2 ) p = b 1 q ⟩ . Again, Theorem 6.2 gives that D P ( G , a b ) \mathcal{D}\mathcal{P}(G,\mathrm{ab}) DP ( G , ab ) is undecidable. □
Remarks and open questions
In this paper we exhibited several classes of one-relator and free-by-cyclic groups where the Diophantine problem with abelianisation constraints is decidable if the abelianisation is “small” i.e. virtually Z \mathbb{Z} Z , and groups where D P ( G , a b ) \mathcal{D}\mathcal{P}(G,\mathrm{ab}) DP ( G , ab ) is undecidable and the abelianisation has torsion-free rank greater than 2 2 2 . There are examples of free by cyclic groups with centre of the form F n ⋊ ϕ Z F_n\rtimes_\phi\mathbb{Z} F n ⋊ ϕ Z and Z 2 \mathbb{Z}^2 Z 2 abelianisation where we do not yet know whether D P ( G , a b ) \mathit{DP}(G,\mathrm{ab}) DP ( G , ab ) is decidable. For instance we do not know whether the group ⟨ a , b , t ∣ t a t − 1 = b , t b t − 1 = a ⟩ \langle a,b,t \mid tat^{-1}=b,\ tbt^{-1}=a\rangle ⟨ a , b , t ∣ t a t − 1 = b , t b t − 1 = a ⟩ has a decidable D P ( G , a b ) \mathit{DP}(G,\mathrm{ab}) DP ( G , ab ) .
It should be noted, however, that the Diophantine Problem itself, so without constraints, for free-by-cyclic groups remains an open and difficult problem. Recent related results show that the Diophantine Problem is undecidable in one-relator groups [8 , 32 ] . More generally, it is also open whether there is an ascending HNN-extensions of free groups. It has recently been proved [40 ] that the conjugacy problem is decidable in ascending HNN-extensions of free groups.
A class of groups where D P ( G ) \mathit{DP}(G) DP ( G ) is known to be decidable [15 ] but it is unclear whether adding constraints changes this is the class of even dihedral Artin groups.
Question 7.1. Is D P ( G , a b ) \mathit{DP}(G,\mathrm{ab}) DP ( G , ab ) decidable if G G G is an even dihedral Artin group? Each such group is isomorphic to the Baumslag-Solitar group B S ( p , p ) = ⟨ a , t ∣ t a p t − 1 = a p ⟩ BS(p,p)=\langle a,t \mid ta^{p}t^{-1}=a^{p}\rangle B S ( p , p ) = ⟨ a , t ∣ t a p t − 1 = a p ⟩ , p ≥ 2 p\geq2 p ≥ 2 .
The groups B S ( p , p ) BS(p,p) B S ( p , p ) above have the torsion-free rank of the abelianisation equal to 2. The case of soluble Baumslag-Solitar groups, which have torsion-free rank of the abelianisation equal to 1, is also open, both in terms of the D P ( G ) \mathit{DP}(G) DP ( G ) and D P ( G , a b ) \mathit{DP}(G,\mathrm{ab}) DP ( G , ab ) . Note that in this case, both of these questions are equivalent as solvable Baumslag-Solitar groups have finite commutator width.
Question 7.2. Is D P ( G , a b ) \mathit{DP}(G,\mathrm{ab}) DP ( G , ab ) decidable in B S ( 1 , p ) = ⟨ a , t ∣ t a t − 1 = a p ⟩ BS(1,p)=\langle a,t \mid tat^{-1}=a^{p}\rangle B S ( 1 , p ) = ⟨ a , t ∣ t a t − 1 = a p ⟩ , p ≥ 2 p\geq2 p ≥ 2 ?
It would be interesting to classify which GBS groups have decidable Diophantine Problem, but this is likely a difficult problem since it remains open even for the Baumslag-Solitar groups B S ( 1 , n ) BS(1,n) B S ( 1 , n ) . A key theme in this area is that Decidability of D P ( G , a b ) \mathit{DP}(G,\mathrm{ab}) DP ( G , ab ) is influenced by the torsion free rank of the abelianisation of the group under consideration. Indeed, as explained in [14 ] the decidability of D P ( G , a b ) \mathit{DP}(G,\mathrm{ab}) DP ( G , ab ) when G G G has decidable Diophantine Problem and its abelianisation has torsion-free rank 1 remains an open problem. More precisely, the following is an open problem:
Question 7.3. Does there exist a group G G G with the following properties:
G G G is finitely generated with decidable Diophantine Problem;
the abelianisation of G G G is virtually cyclic; and
D P ( G , a b ) \mathit{DP}(G,\mathrm{ab}) DP ( G , ab ) is undecidable.
While undecidability in all our results relies on encoding arithmetic into systems of equations, will the same hold for single equations?
Question 7.4. Do our undecidability results hold if we only look at single equations with abelianisation constraints?
Laura Ciobanu: Technische Universität Berlin, Institut für Mathematik, 10623 Berlin, Germany and Heriot-Watt University, Department of Mathematics, EH14 4AS Edinburgh, UK
Robert D. Gray: School of Engineering, Mathematics and Physics, University of East Anglia, Norwich NR4 7TJ, UK
Alex Levine: School of Engineering, Mathematics and Physics, University of East Anglia, Norwich NR4 7TJ, UK