Introduction
A one-relator group has a finite presentation
G = ⟨ X ∣ r ⟩ . G = \langle X \mid r \rangle. G = ⟨ X ∣ r ⟩ . One-relator groups with torsion are hyperbolic [44 ] . They are residually finite by Wise’s theorem [59 ] , and hereditarily conjugacy separable by [42 ] . Their isomorphism problem is decidable by the isomorphism algorithm for hyperbolic groups [10 ] . Torsion-free one-relator groups have more varied properties. For example, BS( 2 , 3 ) (2,3) ( 2 , 3 )
Definition 1.1. For nonzero integers m , n m,n m , n
BS ( m , n ) = ⟨ a , t ∣ t a m t − 1 = a n ⟩ . \operatorname{BS}(m,n) = \langle a,t \mid ta^{m}t^{-1} = a^{n} \rangle. BS ( m , n ) = ⟨ a , t ∣ t a m t − 1 = a n ⟩ . A group is B S BS B S BS ( m , n ) \operatorname{BS}(m,n) BS ( m , n ) BS ( 1 , 1 ) = Z 2 \operatorname{BS}(1,1) = \mathbb{Z}^2 BS ( 1 , 1 ) = Z 2 BS ( m , n ) \operatorname{BS}(m,n) BS ( m , n ) unimodular if ∣ m ∣ = ∣ n ∣ |m| = |n| ∣ m ∣ = ∣ n ∣ non-unimodular otherwise.
Throughout the paper, [ x , y ] = x y x − 1 y − 1 [x,y]=xyx^{-1}y^{-1} [ x , y ] = x y x − 1 y − 1 A d = d − 1 A d A^{d}=d^{-1}Ad A d = d − 1 A d Th ( G ) \operatorname{Th}(G) Th ( G ) G G G G G G G G G
Our first result, Theorem 2.4 , gives a finite first-order characterization of BS-freeness among torsion-free one-relator groups. Corollary 2.6 extends it to groups with torsion. Thus a BS-free one-relator group cannot be elementarily equivalent to a one-relator group containing a Baumslag–Solitar subgroup.
In § 5 , we prove that, for fixed ∣ m ∣ > 1 |m| > 1 ∣ m ∣ > 1 BS ( 1 , m ) \operatorname{BS}(1,m) BS ( 1 , m ) G G G Theorem 5.7 ). The admissible parameters are the pairs satisfying a ≠ 1 a \ne1 a = 1 t a t − 1 = a m tat^{-1}=a^{m} t a t − 1 = a m BS ( 1 , m ) \operatorname{BS}(1,m) BS ( 1 , m ) ( Z , + , ∣ , 0 , 1 ) (\mathbb{Z},+,\mid,0,1) ( Z , + , ∣ , 0 , 1 ) [30 , 12 ] , this implies undecidability of the elementary theory of G G G
§ 6 proves a general arithmetic theorem. Let U U U a ∈ U a \in U a ∈ U ⟨ a ⟩ \langle a\rangle ⟨ a ⟩ U U U
s a m s − 1 = a n , ∣ m ∣ ≠ ∣ n ∣ , sa^{m}s^{-1}=a^{n}, \qquad|m| \ne|n|, s a m s − 1 = a n , ∣ m ∣ = ∣ n ∣ , then arithmetic is uniformly, regularly and injectively interpretable in U U U Theorem 6.2 ). The formulas are independent of m , n m,n m , n s s s ∣ Δ ( s ) ∣ ≠ 1 |\Delta(s)| \ne1 ∣Δ ( s ) ∣ = 1
§ 7 applies this result to one-relator groups. If H = ⟨ a , s ⟩ ≅ BS ( m , n ) H=\langle a,s\rangle\cong\operatorname{BS}(m,n) H = ⟨ a , s ⟩ ≅ BS ( m , n ) M = Comm G ( ⟨ a ⟩ ) M=\operatorname{Comm}_{G}(\langle a\rangle) M = Comm G (⟨ a ⟩) H H H H H H M M M M M M M M M Theorem 7.1 ).
Every fixed finitely presented group is therefore uniformly, regularly and injectively interpretable in these groups by arithmetic coding. The resulting group operation need not be the inherited group operation. One computable translation reduces integer arithmetic to the elementary theory of every group in the class. These results concern the full elementary theory; the Diophantine problems are considered in § 8 .
We also discuss bi-interpretability. The soluble groups in Theorem 6.2 are precisely BS ( 1 , k ) \operatorname{BS}(1,k) BS ( 1 , k ) ∣ k ∣ > 1 |k| > 1 ∣ k ∣ > 1 k > 1 k > 1 k > 1 [12 ] , together with a definable reconstruction from an index-two subgroup for k < − 1 k < -1 k < − 1 Z \mathbb{Z} Z
The unimodular groups BS ( k , k ) \operatorname{BS}(k,k) BS ( k , k ) BS ( k , − k ) \operatorname{BS}(k,-k) BS ( k , − k ) k > 1 k > 1 k > 1 Z \mathbb{Z} Z § 9 also describes the cyclic action giving BS ( k , k ) = F k × Z \operatorname{BS}(k,k)=F_k \times\mathbb{Z} BS ( k , k ) = F k × Z
For the recognition and algorithmic results we use the following result, stated as Theorem 1.1 in [46 ] and denoted below by (H).
Cited result 1.2 (H). Every finitely generated BS-free one-relator group is word-hyperbolic.
We also use the virtual compact specialness result stated as Theorem 1.1 in [47 ] . We have read both papers, but have not verified all details of their proofs. Our conclusions that use these results are conditional on their validity, and we indicate these dependencies explicitly.
All our original model-theoretic results are independent of both cited results. These include the first-order characterization of BS-freeness in § 2 , the interpretation and undecidability results in § 5 –§ 7 , and the model-theoretic results on unimodular groups in § 9 . They originate in our earlier manuscript, written in 2019. The applications of known results on hyperbolic groups to all BS-free one-relator groups, including Corollary 4.3, use (H).
Under (H), Theorem 3.8 gives a terminating recognition algorithm. On a negative input the algorithm constructs generators of an embedded BS ( 1 , n ) \operatorname{BS}(1,n) BS ( 1 , n ) n ≥ 2 n \ge2 n ≥ 2 Z 2 \mathbb{Z}^{2} Z 2
A finitely generated group is word-hyperbolic if geodesic triangles in its Cayley graph are uniformly thin. Hyperbolic groups contain neither Z 2 \mathbb{Z}^{2} Z 2 Lemma 2.2 therefore implies that they are BS-free. Consequently, (H) identifies BS-freeness with hyperbolicity for one-relator groups. This gives the isomorphism and conjugacy results in § 4 , as well as decidability of equations. For torsion-free groups in this class, decidability of the elementary theory follows from the results on torsion-free hyperbolic groups [26 , 50 ] .
§ 10 gives an effective construction of a virtual free-by-cyclic presentation for a hyperbolic one-relator group, assuming the virtual compact specialness result stated as Theorem 1.1 in [47 ] . Theorem 10.2 constructs a finite-index normal subgroup H H H H H H H H H Proposition 10.10 gives a separate construction by enumeration of finite presentations and Tietze transformations.
In § 11 , we prove that, for a finitely generated torsion-free virtually free-by-cyclic group, toral relative hyperbolicity is equivalent to CSA, and also to the absence of F 2 × Z F_{2} \times\mathbb{Z} F 2 × Z Theorem 11.1 ). Here the free kernel need not be finitely generated. In the nonabelian case, the noncyclic peripheral subgroups may be chosen isomorphic to Z 2 \mathbb{Z}^{2} Z 2 [46 , 47 ] .
§ 12 applies these results to decision problems. Let C C C C C C Proposition 12.1 gives a uniform algorithm on C C C Z 2 \mathbb{Z}^{2} Z 2 [53 ] , with the hypotheses specified in § 12 . These algorithms do not require a procedure recognizing the class C C C
We shall use the theorem about torsion in one-relator groups [40 Chapter II] . After free and cyclic reduction, a trivial relator gives a free group, a nontrivial proper-power relator gives a group with torsion, and a non-power relator gives a torsion-free group.
First-order properties
Definition 2.1. A group is locally cyclic if every finitely generated subgroup is cyclic. A subgroup A ≤ G A \leq G A ≤ G malnormal if A ∩ g A g − 1 = 1 A \cap gAg^{-1} = 1 A ∩ g A g − 1 = 1 g ∉ A g \notin A g ∈ / A CSA if its maximal abelian subgroups are malnormal. Write C G ( x ) = { u : [ x , u ] = 1 } C_G(x) = \{u : [x,u] = 1\} C G ( x ) = { u : [ x , u ] = 1 }
We use the following results on subgroups of one-relator groups. An abelian subgroup of a torsion-free one-relator group is either locally cyclic or isomorphic to Z 2 \mathbb{Z}^2 Z 2 [19 Lemma 5] , since the only abelian group BS ( 1 , m ) \operatorname{BS}(1,m) BS ( 1 , m ) BS ( 1 , 1 ) \operatorname{BS}(1,1) BS ( 1 , 1 ) F 2 × Z F_2 \times\mathbb{Z} F 2 × Z BS ( 1 , m ) \operatorname{BS}(1,m) BS ( 1 , m ) [19 Theorem 7] .
Lemma 2.2. Every Baumslag–Solitar group contains either Z 2 \mathbb{Z}^2 Z 2 BS ( 1 , n ) \operatorname{BS}(1,n) BS ( 1 , n ) n ≥ 2 n \geq2 n ≥ 2
Proof. This is [16 Lemma 2.10] , with a sign adjustment. If ∣ m ∣ , ∣ n ∣ > 1 |m|, |n| > 1 ∣ m ∣ , ∣ n ∣ > 1 ⟨ a , b ∣ a n = b m ⟩ \langle a,b \mid a^n = b^m\rangle ⟨ a , b ∣ a n = b m ⟩ b = t a t − 1 b = tat^{-1} b = t a t − 1 z = a n = b m z = a^n = b^m z = a n = b m ⟨ z ⟩ \langle z\rangle ⟨ z ⟩ C ∣ n ∣ ∗ C ∣ m ∣ C_{|n|} * C_{|m|} C ∣ n ∣ ∗ C ∣ m ∣ a b ab ab ⟨ z , a b ⟩ ≅ Z 2 \langle z,ab\rangle\cong\mathbb{Z}^2 ⟨ z , ab ⟩ ≅ Z 2 BS ( 1 , k ) \operatorname{BS}(1,k) BS ( 1 , k ) k = ± 1 k = \pm1 k = ± 1 Z 2 \mathbb{Z}^2 Z 2 k ≥ 2 k \geq2 k ≥ 2 k ≤ − 2 k \leq-2 k ≤ − 2 BS ( 1 , k 2 ) \operatorname{BS}(1,k^2) BS ( 1 , k 2 )
Consider the following sentences in the language of groups:
C T : = ∀ x , u , v ( x ≠ 1 ∧ [ x , u ] = [ x , v ] = 1 ⇒ [ u , v ] = 1 ) , (1) \mathrm{CT} := \forall x,u,v\ \left(x \ne1 \land[x,u] = [x,v] = 1 \Rightarrow[u,v] = 1\right), \tag*{(1)} CT := ∀ x , u , v ( x = 1 ∧ [ x , u ] = [ x , v ] = 1 ⇒ [ u , v ] = 1 ) , (1) M a l : = ∀ x , y , t ( x ≠ 1 ∧ y ≠ 1 ∧ [ x , y ] = [ x , t y t − 1 ] = 1 ⇒ [ x , t ] = 1 ) , (2) \mathrm{Mal} := \forall x,y,t\ \left(x \ne1 \land y \ne1 \land[x,y] = [x,tyt^{-1}] = 1 \Rightarrow[x,t] = 1\right), \tag*{(2)} Mal := ∀ x , y , t ( x = 1 ∧ y = 1 ∧ [ x , y ] = [ x , t y t − 1 ] = 1 ⇒ [ x , t ] = 1 ) , (2) S q : = ∀ x , u , v ( x ≠ 1 ∧ [ x , u ] = [ x , v ] = 1 ⇒ ∃ w ( [ x , w ] = 1 ∧ ( u = w 2 ∨ v = w 2 ∨ u v = w 2 ) ) ) . (3) \begin{aligned}
\mathrm{Sq} := {}& \forall x,u,v\ \left(x \ne1 \land[x,u] = [x,v] = 1 \Rightarrow\right.\\
&\left. \exists w\ ([x,w] = 1 \land(u = w^2 \lor v = w^2 \lor uv = w^2))\right). \tag*{(3)}
\end{aligned} Sq := ∀ x , u , v ( x = 1 ∧ [ x , u ] = [ x , v ] = 1 ⇒ ∃ w ([ x , w ] = 1 ∧ ( u = w 2 ∨ v = w 2 ∨ uv = w 2 )) ) . (3) Here chains of equalities abbreviate conjunctions. Put
C S A : = C T ∧ M a l , Φ : = C S A ∧ S q . \mathrm{CSA} := \mathrm{CT} \land\mathrm{Mal}, \qquad\Phi:= \mathrm{CSA} \land\mathrm{Sq}. CSA := CT ∧ Mal , Φ := CSA ∧ Sq . Lemma 2.3. For every group G G G G ⊨ C S A G \models\mathrm{CSA} G ⊨ CSA G G G G G G S q \mathrm{Sq} Sq A = C G ( x ) A = C_G(x) A = C G ( x ) dim F 2 ( A / 2 A ) ≤ 1 \dim_{\mathbb{F}_2}(A/2A) \leq1 dim F 2 ( A /2 A ) ≤ 1
Proof. The sentence CT says that every nontrivial centralizer is abelian; these centralizers are then precisely the maximal abelian subgroups. For A = C G ( x ) A = C_G(x) A = C G ( x ) A ∩ t A t − 1 A \cap tAt^{-1} A ∩ t A t − 1 y ≠ 1 y \ne1 y = 1 y , t y t − 1 ∈ A y, tyt^{-1} \in A y , t y t − 1 ∈ A t ∈ A t \in A t ∈ A
In an abelian group, Sq states that, for any two classes u ˉ , v ˉ ∈ A / 2 A \bar{u}, \bar{v} \in A/2A u ˉ , v ˉ ∈ A /2 A u ˉ , v ˉ , u ˉ + v ˉ \bar{u}, \bar{v}, \bar{u} + \bar{v} u ˉ , v ˉ , u ˉ + v ˉ
Theorem 2.4. For every torsion-free one-relator group G G G
G is BS -free ⟺ G ⊨ Φ . G\text{ is } \operatorname{BS}\text{-free} \iff G \models\Phi. G is BS -free ⟺ G ⊨ Φ. Proof. Suppose first that G G G F 2 × Z F_2 \times\mathbb{Z} F 2 × Z Z 2 \mathbb{Z}^2 Z 2 BS ( 1 , m ) \operatorname{BS}(1,m) BS ( 1 , m ) Z 2 \mathbb{Z}^2 Z 2 u , v u,v u , v c c c ⟨ u , v ⟩ \langle u,v\rangle ⟨ u , v ⟩ u = c i , v = c j u = c^i, v = c^j u = c i , v = c j i , j , i + j i,j,i+j i , j , i + j G ⊨ Φ G \models\Phi G ⊨ Φ
Conversely, suppose G ⊨ Φ G \models\Phi G ⊨ Φ Z 2 \mathbb{Z}^{2} Z 2 S q Sq S q Z 2 \mathbb{Z}^{2} Z 2 G G G Z 2 \mathbb{Z}^{2} Z 2 BS ( 1 , n ) \operatorname{BS}(1,n) BS ( 1 , n )
Theorem 2.4 does not use either result from [46 , 47 ] . Combining it with (H), the same sentence characterizes hyperbolicity among torsion-free one-relator groups.
Corollary 2.5. Within torsion-free one-relator groups, the three sentences
CSA ∧ S q , CSA ∧ ¬ S q , ¬ CSA \operatorname{CSA} \wedge Sq,\qquad\operatorname{CSA} \wedge\neg Sq,\qquad\neg\operatorname{CSA} CSA ∧ S q , CSA ∧ ¬ S q , ¬ CSA define a partition: respectively the BS-free groups, the CSA groups containing Z 2 \mathbb{Z}^{2} Z 2
The recognition problem is considered in § 3 . The first-order characterization alone does not provide an algorithm for evaluating Φ \Phi Φ
Corollary 2.6. The sentence
Ψ : = ∃ z ( z ≠ 1 ∧ z 2 = 1 ) ∨ Φ \Psi:= \exists z\ (z \ne1 \wedge z^{2} = 1) \vee\Phi Ψ := ∃ z ( z = 1 ∧ z 2 = 1 ) ∨ Φ characterizes BS-freeness within all finitely generated one-relator groups. Consequently, two one-relator groups, one BS-free and the other containing a Baumslag–Solitar subgroup, cannot be elementarily equivalent.
Proof. For torsion-free inputs this is Theorem 2.4 . A one-relator group with torsion is hyperbolic and hence BS-free. If it has an involution, the first disjunct holds. Otherwise it contains no infinite dihedral subgroup, so is CSA by [19 Theorem 8] . Newman’s centralizer theorem [44 Theorem 2] says that its nontrivial centralizers are cyclic; hence S q Sq S q Ψ \Psi Ψ
Recognition of BS-free one-relator groups
We construct a recognition procedure using a Magnus hierarchy and finite witnesses for Baumslag–Solitar subgroups. All tree actions are simplicial and without inversions. An element is elliptic if it fixes a vertex and hyperbolic on the tree if it translates along an axis. Its translation length is
ℓ T ( g ) = min v ∈ V ( T ) d T ( v , g v ) . \ell_T(g) = \min_{v \in V(T)} d_T(v,gv). ℓ T ( g ) = v ∈ V ( T ) min d T ( v , g v ) . Lemma 3.1. For a nontrivial non-power relator, one can construct a finite hierarchy
G = G 0 ≥ G 1 ≥ ⋯ ≥ G N = 1 , G i = ⟨ G i + 1 , t i ∣ t i A i t i − 1 = B i ⟩ , G = G_0 \geq G_1 \geq\cdots\geq G_N = 1,\qquad G_i = \langle G_{i+1},t_i \mid t_i A_i t_i^{-1} = B_i\rangle, G = G 0 ≥ G 1 ≥ ⋯ ≥ G N = 1 , G i = ⟨ G i + 1 , t i ∣ t i A i t i − 1 = B i ⟩ , where the groups G i G_i G i A i , B i A_i,B_i A i , B i G i + 1 G_{i+1} G i + 1 G G G A i , B i A_i,B_i A i , B i ℓ T i ( g ) > 0 \ell_{T_i}(g) > 0 ℓ T i ( g ) > 0
Proof. Use Linton’s construction of a one-relator hierarchy by Z \mathbb{Z} Z [38 ] . Its construction consists of finite graph operations in cyclic covers. The cyclic character is obtained by integer linear algebra; domains, overlaps, spanning trees, and their inclusion maps are computable. One may enumerate admissible finite domains until the finite graph conditions and the required strict decrease of complexity hold. Let Γ \Gamma Γ λ : S 1 → Γ \lambda:S^1 \to\Gamma λ : S 1 → Γ ∣ λ ∣ |\lambda| ∣ λ ∣
( ∣ λ ∣ − ∣ V ( λ ( S 1 ) ) ∣ , rank π 1 Γ ) ; \left(|\lambda|-|V(\lambda(S^1))|,\operatorname{rank}\pi_1\Gamma\right); ( ∣ λ ∣ − ∣ V ( λ ( S 1 )) ∣ , rank π 1 Γ ) ; see also the explicit construction in [46 Lemma 8.3] . Existence at each nonterminal step and strict decrease ensure termination. The Freiheitssatz and the HNN normal form show that the inclusions in the hierarchy are injective. The terminal group is finite cyclic; as it embeds in a torsion-free group, it is trivial.
Magnus’s extended word-problem algorithm decides membership in the edge groups [40 ] . When membership holds, an expression in their generators can be found by enumeration and the word problem. This makes Britton reduction and cyclic Britton reduction effective. An element has positive tree translation length precisely when its cyclically reduced HNN form contains a stable letter.
Lemma 3.2. In any group, if u u u v u v − 1 = u n vuv^{-1}=u^n v u v − 1 = u n ∣ n ∣ ≥ 2 |n|\ge2 ∣ n ∣ ≥ 2 ⟨ u , v ⟩ ≅ BS ( 1 , n ) \langle u,v\rangle\cong\operatorname{BS}(1,n) ⟨ u , v ⟩ ≅ BS ( 1 , n )
Proof. Write BS ( 1 , n ) = Z [ 1 / n ] ⋊ Z \operatorname{BS}(1,n)=\mathbb{Z}[1/n]\rtimes\mathbb{Z} BS ( 1 , n ) = Z [ 1/ n ] ⋊ Z ( q , k ) ( r , l ) = ( q + n k r , k + l ) (q,k)(r,l)=(q+n^k r,k+l) ( q , k ) ( r , l ) = ( q + n k r , k + l ) ( 1 , 0 ) (1,0) ( 1 , 0 ) ( q , k ) (q,k) ( q , k ) k ≠ 0 k\ne0 k = 0 ( 1 , 0 ) (1,0) ( 1 , 0 ) ( n k − 1 , 0 ) ≠ ( 0 , 0 ) (n^k-1,0)\ne(0,0) ( n k − 1 , 0 ) = ( 0 , 0 ) u u u
Lemma 3.3. At a level of the hierarchy, suppose
a ∈ G i + 1 ∖ { 1 } , g ∈ G i , [ a , g ] = 1 , ℓ T i ( g ) > 0. a\in G_{i+1}\setminus\{1\},\qquad g\in G_i,\qquad[a,g]=1,\qquad\ell_{T_i}(g)>0. a ∈ G i + 1 ∖ { 1 } , g ∈ G i , [ a , g ] = 1 , ℓ T i ( g ) > 0. Then ⟨ a , g ⟩ ≅ Z 2 \langle a,g\rangle\cong\mathbb{Z}^2 ⟨ a , g ⟩ ≅ Z 2
Proof. If a p g q = 1 a^p g^q=1 a p g q = 1 g q = a − p g^q=a^{-p} g q = a − p ℓ T i ( g q ) = ∣ q ∣ ℓ T i ( g ) \ell_{T_i}(g^q)=|q|\ell_{T_i}(g) ℓ T i ( g q ) = ∣ q ∣ ℓ T i ( g ) q = 0 q=0 q = 0 a ≠ 1 a\ne1 a = 1
Lemma 3.4. If G G G Z 2 \mathbb{Z}^2 Z 2 Lemma 3.3 exists at some level of the computed hierarchy.
Proof. Choose the largest i i i G i G_i G i C ≅ Z 2 C\cong\mathbb{Z}^2 C ≅ Z 2 C C C T i T_i T i G i + 1 G_{i+1} G i + 1 C C C g g g C C C g g g C → Z C\to\mathbb{Z} C → Z a ≠ 1 a\ne1 a = 1 G i + 1 G_{i+1} G i + 1 a ∈ G i + 1 a\in G_{i+1} a ∈ G i + 1
Definition 3.5. For a torsion-free input and its fixed computed hierarchy, a certificate of type S is a tuple ( u , v , n ) (u,v,n) ( u , v , n ) n ≥ 2 n\ge2 n ≥ 2
u ≠ 1 , v u v − 1 = u n . (4) u\ne1,\qquad vuv^{-1}=u^n. \tag*{(4)} u = 1 , v u v − 1 = u n . (4) A certificate of type A is a tuple ( i , a , g ) (i,a,g) ( i , a , g )
a ∈ G i + 1 ∖ { 1 } , g ∈ G i , [ a , g ] = 1 , ℓ T i ( g ) > 0. (5) a\in G_{i+1}\setminus\{1\},\qquad g\in G_i,\qquad[a,g]=1,\qquad\ell_{T_i}(g)>0. \tag*{(5)} a ∈ G i + 1 ∖ { 1 } , g ∈ G i , [ a , g ] = 1 , ℓ T i ( g ) > 0. (5) All words are written in the computed alphabets, with explicit images in the original presentation.
Proposition 3.6. There is a semialgorithm that halts exactly on one-relator groups containing a Baumslag–Solitar subgroup. When it halts, it gives explicit generators of an embedded BS ( 1 , n ) \operatorname{BS}(1,n) BS ( 1 , n ) n ≥ 2 n \ge2 n ≥ 2 Z 2 \mathbb{Z}^2 Z 2
Proof. Trivial and proper-power relators define subgroups BS-free groups. On a nontrivial non-power input, construct the hierarchy and enumerate all tuples in (S) and (A), across the finitely many levels. Every check terminates by Lemma 3.1 . It follows from Lemmas 3.2 and 3.3 that the procedure halts only when G G G Lemma 2.2 . An embedded solvable group supplies an (S) tuple, and an embedded Z 2 \mathbb{Z}^2 Z 2 Lemma 3.4 . Enumeration eventually reaches it.
Definition 3.7. For a finite presentation P P P Hyp ( P ) \operatorname{Hyp}(P) Hyp ( P ) hyperbolicity-detection semialgorithm [48 pp. 193–200] . On hyperbolic inputs it certifies hyperbolicity and computes a thin-triangle constant δ \delta δ [10 Section 2.3.1] recall the procedure.
Theorem 3.8. Under (H), the following uniform procedure decides BS-freeness and hyperbolicity for arbitrary finite one-relator presentations.
Freely and cyclically reduce r r r r = 1 r = 1 r = 1 r r r
For a remaining input, compute the hierarchy of Lemma 3.1 .
Run Hyp ( ⟨ X ∣ r ⟩ ) \operatorname{Hyp}(\langle X \mid r\rangle) Hyp (⟨ X ∣ r ⟩)
A hyperbolicity certificate gives the answer BS-free. An (S) or (A) certificate gives the answer contains BS, together with the subgroup generators and their data that can be checked algorithmically.*
Hyperbolicity data can also be computed in every hyperbolic case.
Proof. Every answer returned by the procedure is correct, by Newman’s theorem, Lemmas 3.2 and 3.3 , and the fact that hyperbolic groups are BS-free. For a negative input, Proposition 3.6 guarantees termination of the search. For a positive input, (H) guarantees that Hyp \operatorname{Hyp} Hyp Hyp \operatorname{Hyp} Hyp δ \delta δ
Remark 3.9. On an input containing a Baumslag–Solitar subgroup, the procedure constructs an embedded BS ( 1 , n ) \operatorname{BS}(1,n) BS ( 1 , n ) n ≥ 2 n \ge2 n ≥ 2 Z 2 \mathbb{Z}^2 Z 2
Algorithmic and model-theoretic consequences
The corollaries below apply known theorems on hyperbolic groups to BS-free one-relator groups using (H). This dependence concerns these applications: the original model-theoretic results of the paper are independent of both results cited from [46 , 47 ] .
Corollary 4.1. Assume (H). There is a uniform algorithm comparing a BS-free one-relator group G G G H H H G ≅ H G \cong H G ≅ H
Proof. Recognize H H H [10 ] .
Corollary 4.2. Assume (H). On the recognized class of BS-free one-relator groups, the conjugacy and simultaneous conjugacy problems, and satisfiability of finite systems of equations and inequations with coefficients, are uniformly decidable. These statements include the torsion case.
Proof. Compute hyperbolicity data and apply the hyperbolic-group algorithms in [10 Section 2.3] and [9 ] .
Corollary 4.3. Assume (H). Every torsion-free BS-free one-relator group has decidable elementary theory and effective reduction of formulas to Boolean combinations of ∀ ∃ \forall\exists ∀∃
Proof. Follows the corresponding torsion-free hyperbolic-group results: [26 , 50 ] for elementary theory and algebraic geometry, the standard hyperbolic centralizer and automaticity theorems, and [51 ] for Hopficity.
A group is equationally Noetherian if every system of equations in finitely many variables has the same solution set as a finite subsystem. Under (H), the elementary-equivalence results for torsion-free hyperbolic groups [50 ] apply to torsion-free BS-free one-relator groups. By Corollary 2.6 , every one-relator group elementarily equivalent to a BS-free one-relator group is itself BS-free.
Corollary 4.4. Assume (H). If G G G G → H G \to H G → H H → G H \to G H → G G ≅ H G \cong H G ≅ H
Proof. The composite is a surjective endomorphism of the Hopfian group G G G G → H G \to H G → H
Remark 4.5. If a hyperbolic group has a finite quasiconvex hierarchy in the sense of Wise, then it is virtually compact special [59 ] . It is therefore residually finite and has a finite-index subgroup which embeds in a right-angled Artin group. Here the edge groups of the hierarchy must be quasiconvex in the ambient group at each splitting.
Interpretation of solvable Baumslag–Solitar groups
We recall the definition of interpretability.
Definition 5.1. An algebraic structure B B B interpretable in a structure G G G D ⊆ G r D \subseteq G^r D ⊆ G r E E E D D D D / E D/E D / E B B B regular if these parameters range over a nonempty definable set P P P B B B P P P injective if E E E uniform if the defining formulas are the same for every structure in the class. See [28 Section 4.2] .
Lemma 5.2. Every subgroup of a torsion-free one-relator group is locally cyclic, contains a nonabelian free group, or is isomorphic to BS ( 1 , n ) \operatorname{BS}(1,n) BS ( 1 , n ) n n n Z 2 \mathbb{Z}^2 Z 2
Proof. This is [19 Lemma 5] ; no finite-generation assumption on the subgroup is required.
Lemma 5.3. Let G G G A ≤ G A \leq G A ≤ G C G ( A ) C_G(A) C G ( A )
Proof. Put L = C G ( A ) L = C_G(A) L = C G ( A ) A ≤ Z ( L ) A \leq Z(L) A ≤ Z ( L ) L L L F F F A ∩ F = 1 A \cap F = 1 A ∩ F = 1 Z ( F ) Z(F) Z ( F ) f ∈ F f \in F f ∈ F A ⟨ f ⟩ A\langle f\rangle A ⟨ f ⟩ A × Z A \times\mathbb{Z} A × Z Z 2 \mathbb{Z}^2 Z 2
By [19 Lemma 5] , L L L BS ( 1 , n ) \operatorname{BS}(1,n) BS ( 1 , n ) ∣ n ∣ > 1 |n| > 1 ∣ n ∣ > 1 n = − 1 n = -1 n = − 1 n = 1 n = 1 n = 1 Z 2 \mathbb{Z}^2 Z 2 A A A L L L
Lemma 5.4. Let G G G ∣ m ∣ ≥ 2 |m| \geq2 ∣ m ∣ ≥ 2
a ≠ 1 , t a t − 1 = a m . a \ne1,\qquad tat^{-1} = a^m. a = 1 , t a t − 1 = a m . Define
D = D m ( a , t ) = { x ∈ G : [ x , a ] = 1 , t x t − 1 = x m } . D = D_m(a,t) = \{x \in G : [x,a] = 1,\ txt^{-1} = x^m\}. D = D m ( a , t ) = { x ∈ G : [ x , a ] = 1 , t x t − 1 = x m } . Then D D D t D t − 1 = D tDt^{-1} = D t D t − 1 = D C G ( D ) = D C_G(D) = D C G ( D ) = D
Proof. By Lemma 3.2 , the pair a , t a,t a , t BS ( 1 , m ) \operatorname{BS}(1,m) BS ( 1 , m )
A = ⋃ j > 0 t − j ⟨ a ⟩ t j ≅ Z [ 1 / ∣ m ∣ ] . A = \bigcup_{j>0} t^{-j}\langle a\rangle t^j \cong\mathbb{Z}[1/|m|]. A = j > 0 ⋃ t − j ⟨ a ⟩ t j ≅ Z [ 1/∣ m ∣ ] . The cyclic groups form an increasing chain; A A A t t t Lemma 5.3 gives that L = C G ( A ) L = C_G(A) L = C G ( A ) t L t − 1 = L tLt^{-1} = L t L t − 1 = L
We claim D = L D = L D = L x ∈ D x \in D x ∈ D j ≥ 0 j \geq0 j ≥ 0
t j [ x , t − j a t j ] t − j = [ x m j , a ] = 1. t^j[x,t^{-j}at^j]t^{-j} = [x^{m^j},a] = 1. t j [ x , t − j a t j ] t − j = [ x m j , a ] = 1. Thus x x x A A A D ⊆ L D \subseteq L D ⊆ L x ∈ L x \in L x ∈ L p ≠ 0 p \ne0 p = 0 q q q x p = a q x^p = a^q x p = a q t x t − 1 txt^{-1} t x t − 1 x m x^m x m L L L
( t x t − 1 ) p = a m q = ( x m ) p . (txt^{-1})^p = a^{mq} = (x^m)^p. ( t x t − 1 ) p = a m q = ( x m ) p . Unique roots in the torsion-free abelian group L L L t x t − 1 = x m txt^{-1} = x^m t x t − 1 = x m x ∈ D x \in D x ∈ D
Since A ≤ D A \leq D A ≤ D D D D
D ≤ C G ( D ) ≤ C G ( A ) = D , D \leq C_G(D) \leq C_G(A) = D, D ≤ C G ( D ) ≤ C G ( A ) = D , which proves self-centralization. The other assertions follow from D = L D = L D = L
Proposition 5.5. With the notation above, put N = N G ( D ) N = N_G(D) N = N G ( D ) n n n ∣ n ∣ ≥ 2 |n| \geq2 ∣ n ∣ ≥ 2
N ≅ BS ( 1 , n ) , D ≅ Z [ 1 / n ] , N / D ≅ Z . N \cong\operatorname{BS}(1,n),\qquad D \cong\mathbb{Z}[1/n],\qquad N/D \cong\mathbb{Z}. N ≅ BS ( 1 , n ) , D ≅ Z [ 1/ n ] , N / D ≅ Z . Under the standard orientation of this quotient, the image of t t t k ≥ 1 k \geq1 k ≥ 1
n k = m , k ≤ ⌊ log 2 ∣ m ∣ ⌋ . n^k = m,\qquad k \leq\lfloor\log_2 |m| \rfloor. n k = m , k ≤ ⌊ log 2 ∣ m ∣ ⌋ . Moreover, ⟨ D , t ⟩ ≅ BS ( 1 , m ) \langle D,t\rangle\cong\operatorname{BS}(1,m) ⟨ D , t ⟩ ≅ BS ( 1 , m ) k k k N N N
Proof. Conjugation gives N / D ↪ Aut ( D ) N/D \hookrightarrow\operatorname{Aut}(D) N / D ↪ Aut ( D ) C G ( D ) = D C_G(D)=D C G ( D ) = D ( Q , + ) (\mathbb{Q},+) ( Q , + ) N N N ⟨ a , t ⟩ \langle a,t\rangle ⟨ a , t ⟩ [19 Lemma 5] gives N ≅ BS ( 1 , n ) N \cong\operatorname{BS}(1,n) N ≅ BS ( 1 , n ) n = 1 , − 1 n=1,-1 n = 1 , − 1 Z 2 \mathbb{Z}^2 Z 2 D D D
In Z [ 1 / n ] ⋊ Z \mathbb{Z}[1/n]\rtimes\mathbb{Z} Z [ 1/ n ] ⋊ Z Z [ 1 / n ] × { 0 } \mathbb{Z}[1/n]\times\{0\} Z [ 1/ n ] × { 0 } Z \mathbb{Z} Z n h n^h n h h ≠ 0 h\ne0 h = 0 D D D B B B B B B D D D B ≤ C N ( D ) = D B\le C_N(D)=D B ≤ C N ( D ) = D B = D B=D B = D
If t t t k k k D D D n k n^k n k Lemma 5.4 identifies this action as multiplication by m m m n k = m n^k=m n k = m ∣ n ∣ ≥ 2 |n|\ge2 ∣ n ∣ ≥ 2 ∣ m ∣ ≥ 2 |m|\ge2 ∣ m ∣ ≥ 2 k ≥ 1 k\ge1 k ≥ 1 k ≤ ⌊ log 2 ∣ m ∣ ⌋ k\le\lfloor\log_2|m|\rfloor k ≤ ⌊ log 2 ∣ m ∣ ⌋ Z [ 1 / n ] = Z [ 1 / m ] \mathbb{Z}[1/n]=\mathbb{Z}[1/m] Z [ 1/ n ] = Z [ 1/ m ] ⟨ D , t ⟩ = D ⋊ ⟨ t ⟩ \langle D,t\rangle=D\rtimes\langle t\rangle ⟨ D , t ⟩ = D ⋊ ⟨ t ⟩ m m m BS ( 1 , m ) \operatorname{BS}(1,m) BS ( 1 , m ) N / D N/D N / D k Z k\mathbb{Z} k Z
Definition 5.6. Fix ∣ m ∣ ≥ 2 |m|\ge2 ∣ m ∣ ≥ 2 K = ⌊ log 2 ∣ m ∣ ⌋ K=\lfloor\log_2|m|\rfloor K = ⌊ log 2 ∣ m ∣ ⌋
P m ( a , t ) : = ( a ≠ 1 ∧ t a t − 1 = a m ) , P_m(a,t):=(a\ne1\land tat^{-1}=a^m), P m ( a , t ) := ( a = 1 ∧ t a t − 1 = a m ) , d m ( x ; a , t ) : = ( [ x , a ] = 1 ∧ t x t − 1 = x m ) , d_m(x;a,t):=([x,a]=1\land txt^{-1}=x^m), d m ( x ; a , t ) := ([ x , a ] = 1 ∧ t x t − 1 = x m ) , ν m ( g ; a , t ) : = ∀ x ( d m ( x ; a , t ) ⟷ d m ( g x g − 1 ; a , t ) ) . \nu_m(g;a,t):=\forall x\left(d_m(x;a,t)\longleftrightarrow d_m(gxg^{-1};a,t)\right). ν m ( g ; a , t ) := ∀ x ( d m ( x ; a , t ) ⟷ d m ( g x g − 1 ; a , t ) ) . For 1 ≤ j ≤ K 1\le j\le K 1 ≤ j ≤ K
R j ( z ; a , t ) : = ν m ( z ; a , t ) ∧ ∃ y ( ν m ( y ; a , t ) ∧ d m ( z y − j ; a , t ) ) . R_j(z;a,t):=\nu_m(z;a,t)\land\exists y\left(\nu_m(y;a,t)\land d_m(zy^{-j};a,t)\right). R j ( z ; a , t ) := ν m ( z ; a , t ) ∧ ∃ y ( ν m ( y ; a , t ) ∧ d m ( z y − j ; a , t ) ) . For 1 ≤ k ≤ K 1\le k\le K 1 ≤ k ≤ K
η k ( a , t ) : = R k ( t ; a , t ) ∧ ⋀ j = k + 1 K ¬ R j ( t ; a , t ) , \eta_k(a,t):=R_k(t;a,t)\land\bigwedge_{j=k+1}^{K}\neg R_j(t;a,t), η k ( a , t ) := R k ( t ; a , t ) ∧ j = k + 1 ⋀ K ¬ R j ( t ; a , t ) , where an empty conjunction is true. Finally, define the group domain
Δ m ( g ; a , t ) : = ⋁ k = 1 K ( η k ( a , t ) ∧ R k ( g ; a , t ) ) . \Delta_m(g;a,t):=\bigvee_{k=1}^{K}\left(\eta_k(a,t)\land R_k(g;a,t)\right). Δ m ( g ; a , t ) := k = 1 ⋁ K ( η k ( a , t ) ∧ R k ( g ; a , t ) ) . Theorem 5.7. Let m m m ∣ m ∣ > 1 |m|>1 ∣ m ∣ > 1 G G G BS ( 1 , m ) \operatorname{BS}(1,m) BS ( 1 , m ) BS ( 1 , m ) \operatorname{BS}(1,m) BS ( 1 , m ) G G G m m m P m ( a , t ) P_m(a,t) P m ( a , t ) Δ m ( g ; a , t ) \Delta_m(g;a,t) Δ m ( g ; a , t ) BS ( 1 , m ) \operatorname{BS}(1,m) BS ( 1 , m ) G G G m m m
Proof. The group G G G BS ( 1 , m ) \operatorname{BS}(1,m) BS ( 1 , m ) P m P_m P m P m P_m P m Lemma 3.2 . Fix any such pair. Lemma 5.4 and Proposition 5.5 apply to it. The formulas d m , ν m d_m,\nu_m d m , ν m D , N D,N D , N
Write h : N → N / D ≅ Z h:N\to N/D\cong\mathbb{Z} h : N → N / D ≅ Z h ( t ) = k h(t)=k h ( t ) = k z ∈ N z\in N z ∈ N
R j ( z ; a , t ) ⟺ h ( z ) ∈ j Z . R_j(z;a,t)\Longleftrightarrow h(z)\in j\mathbb{Z}. R j ( z ; a , t ) ⟺ h ( z ) ∈ j Z . Indeed z y − j ∈ D zy^{-j} \in D z y − j ∈ D h ( z ) = j h ( y ) h(z) = jh(y) h ( z ) = j h ( y ) N N N R j ( t ; a , t ) R_j(t; a,t) R j ( t ; a , t ) j ∣ k j \mid k j ∣ k 1 ≤ k ≤ K 1 \le k \le K 1 ≤ k ≤ K j ≤ K j \le K j ≤ K k k k η j \eta_j η j η k \eta_k η k
It follows that Δ m ( G ; a , t ) = h − 1 ( k Z ) = ⟨ D , t ⟩ \Delta_m(G; a,t) = h^{-1}(k\mathbb{Z}) = \langle D,t\rangle Δ m ( G ; a , t ) = h − 1 ( k Z ) = ⟨ D , t ⟩ BS ( 1 , m ) \operatorname{BS}(1,m) BS ( 1 , m ) m m m
Corollary 5.8. If a one-relator group G G G BS ( 1 , m ) \operatorname{BS}(1,m) BS ( 1 , m ) ∣ m ∣ > 1 |m| > 1 ∣ m ∣ > 1 G G G
Proof. Such a group is torsion-free: a one-relator group with torsion is hyperbolic and contains no Baumslag–Solitar subgroup. If m < − 1 m < -1 m < − 1 BS ( 1 , m 2 ) \operatorname{BS}(1,m^2) BS ( 1 , m 2 ) m ≥ 2 m \ge2 m ≥ 2
By Theorem 5.7 , BS ( 1 , m ) \operatorname{BS}(1,m) BS ( 1 , m ) G G G Z \mathbb{Z} Z BS ( 1 , m ) \operatorname{BS}(1,m) BS ( 1 , m ) [12 Theorem 3 and Section 4.4] , composes with this interpretation. Its parameter conditions and quantifiers are relativized to Δ m \Delta_m Δ m
Let σ \sigma σ Δ m \Delta_m Δ m σ Δ m ( a , t ) \sigma^{\Delta_m}(a,t) σ Δ m ( a , t )
BS ( 1 , m ) ⊨ σ ⟺ G ⊨ ∃ a ∃ t ( P m ( a , t ) ∧ σ Δ m ( a , t ) ) . \operatorname{BS}(1,m) \models\sigma\quad\Longleftrightarrow\quad G \models\exists a\,\exists t\left(P_m(a,t) \land\sigma^{\Delta_m}(a,t)\right). BS ( 1 , m ) ⊨ σ ⟺ G ⊨ ∃ a ∃ t ( P m ( a , t ) ∧ σ Δ m ( a , t ) ) . Every admissible pair gives the same abstract group, so this equivalence is valid even for sentences with arbitrary quantifier alternation. It reduces the undecidable theory of BS ( 1 , m ) \operatorname{BS}(1,m) BS ( 1 , m ) Th ( G ) \operatorname{Th}(G) Th ( G )
Example 5.9. Let
G = ⟨ b , t ∣ t b 2 t − 1 = b 4 ⟩ , a = b 2 . G = \langle b,t \mid tb^2t^{-1} = b^4\rangle,\qquad a = b^2. G = ⟨ b , t ∣ t b 2 t − 1 = b 4 ⟩ , a = b 2 . The elements b b b c = t − 1 b 2 t c = t^{-1}b^2t c = t − 1 b 2 t C G ( a ) C_G(a) C G ( a ) [ b , c ] ≠ 1 [b,c] \ne1 [ b , c ] = 1 C G ( a ) C_G(a) C G ( a ) c 2 = a c^2 = a c 2 = a t c t − 1 = c 2 tct^{-1} = c^2 t c t − 1 = c 2 c ∈ D 2 ( a , t ) c \in D_2(a,t) c ∈ D 2 ( a , t ) Lemma 5.4 , D 2 ( a , t ) D_2(a,t) D 2 ( a , t ) t t t K = 1 K = 1 K = 1 Δ 2 \Delta_2 Δ 2 N G ( D 2 ( a , t ) ) N_G(D_2(a,t)) N G ( D 2 ( a , t )) BS ( 1 , 2 ) \operatorname{BS}(1,2) BS ( 1 , 2 )
Example 5.10. In G = ⟨ b , t ∣ t b t − 1 = b 2 ⟩ G = \langle b,t \mid tbt^{-1} = b^2\rangle G = ⟨ b , t ∣ t b t − 1 = b 2 ⟩ a = b 3 a = b^3 a = b 3 ⟨ a , t ⟩ \langle a,t\rangle ⟨ a , t ⟩ G G G D 2 ( a , t ) D_2(a,t) D 2 ( a , t ) Δ 2 \Delta_2 Δ 2 G G G Theorem 5.7 may properly contain the initially given copy of BS ( 1 , m ) \operatorname{BS}(1,m) BS ( 1 , m )
Uniform arithmetic in groups of cohomological dimension two
All cohomological dimensions in this section are over Z \mathbb{Z} Z commensurable if their intersection has finite index in both. For an infinite cyclic subgroup D ≤ U D \le U D ≤ U
Comm U ( D ) = { g ∈ U : D and g D g − 1 are commensurable } . \operatorname{Comm}_U(D) = \{g \in U : D \text{ and } gDg^{-1} \text{ are commensurable}\}. Comm U ( D ) = { g ∈ U : D and g D g − 1 are commensurable } . This is a subgroup. We say that D D D commensurated by U U U Comm U ( D ) = U \operatorname{Comm}_U(D) = U Comm U ( D ) = U
Definition 6.1. A generalized Baumslag–Solitar group, or GBS group, is the fundamental group of a finite connected graph of infinite cyclic groups with injective edge maps.
Theorem 6.2. Let C C C U U U cd U ≤ 2 \operatorname{cd} U \le2 cd U ≤ 2 a , s ∈ U a,s \in U a , s ∈ U m , n m,n m , n ⟨ a ⟩ \langle a\rangle ⟨ a ⟩ U U U
s m a m s − 1 = a n , ∣ m ∣ ≠ ∣ n ∣ . s^{m}a^{m}s^{-1}=a^{n}, \qquad|m|\ne|n|. s m a m s − 1 = a n , ∣ m ∣ = ∣ n ∣. The ring ( Z , + , × , 0 , 1 ) (\mathbb{Z},+,\times,0,1) ( Z , + , × , 0 , 1 ) C C C m , n m,n m , n U U U
We prove the theorem by defining ( Z , + , ∣ , 0 , 1 ) (\mathbb{Z},+,|,0,1) ( Z , + , ∣ , 0 , 1 ) [49 ] . We use the usual convention that every integer divides zero and that zero divides only zero.
Subgroups and centralizers
We shall use the following two structural results.
Theorem 6.3. A finitely generated group of cohomological dimension two with a commensurated infinite cyclic subgroup is a GBS group.
This is the form of [32 Theorem C] stated in [4 proof of Theorem 3.2] .
Theorem 6.4. A countable soluble group of cohomological dimension at most two is locally cyclic or isomorphic to B S ( 1 , k ) BS(1,k) B S ( 1 , k ) k k k Z 2 \mathbb{Z}^2 Z 2
For dimension two this is [18 Theorem 5] ; see also [33 Theorem 3 and its proof] . Dimension one follows from the Stallings–Swan theorem [2 Chapter VIII] .
Lemma 6.5. Suppose ⟨ a ⟩ \langle a\rangle ⟨ a ⟩ U U U
Δ : U ⟶ Q × , g a r g − 1 = a q ⟹ Δ ( g ) = q / r ( r , q ≠ 0 ) . \Delta:U\longrightarrow\mathbb{Q}^{\times}, \qquad ga^{r}g^{-1}=a^{q}\ \Longrightarrow\ \Delta(g)=q/r \quad(r,q\ne0). Δ : U ⟶ Q × , g a r g − 1 = a q ⟹ Δ ( g ) = q / r ( r , q = 0 ) . It is unchanged when ⟨ a ⟩ \langle a\rangle ⟨ a ⟩
ker Δ = ⋃ r ≥ 1 C U ( a r ) , \ker\Delta=\bigcup_{r\ge1}C_U(a^r), ker Δ = r ≥ 1 ⋃ C U ( a r ) , where the union is directed by divisibility of r r r
Proof. Two conjugation relations give the same ratio after taking common powers. Applying two conjugations to a sufficiently large common power proves multiplicativity. Comparing common powers also proves the assertion about commensurable cyclic subgroups. Finally, Δ ( g ) = 1 \Delta(g)=1 Δ ( g ) = 1 g g g a a a C U ( a r ) , C U ( a q ) ≤ C U ( a r q ) C_U(a^r),C_U(a^q)\le C_U(a^{rq}) C U ( a r ) , C U ( a q ) ≤ C U ( a r q ) r , q > 0 r,q>0 r , q > 0
The homomorphism Δ \Delta Δ modular homomorphism . In a GBS tree, adjacent vertex stabilizers contain their common edge stabilizer with finite index. Following a finite path shows that all vertex stabilizers are commensurable. They are therefore commensurated by the group and define the same modular homomorphism. A GBS group is non-unimodular if Δ ( U ) ⊈ { 1 , − 1 } \Delta(U)\not\subseteq\{1,-1\} Δ ( U ) ⊆ { 1 , − 1 } [35 Section 2] .
If s a m s − 1 = a n sa^{m}s^{-1}=a^{n} s a m s − 1 = a n ∣ m ∣ ≠ ∣ n ∣ |m|\ne|n| ∣ m ∣ = ∣ n ∣ a a a ∣ m ∣ ℓ ( a ) = ∣ n ∣ ℓ ( a ) |m|\ell(a)=|n|\ell(a) ∣ m ∣ ℓ ( a ) = ∣ n ∣ ℓ ( a ) ⟨ a ⟩ \langle a\rangle ⟨ a ⟩ a a a
Lemma 6.6. Let U , a , s , m , n U,a,s,m,n U , a , s , m , n Theorem 6.2 . Every finitely generated subgroup containing a , s a,s a , s U U U BS ( 1 , k ) \operatorname{BS}(1,k) BS ( 1 , k )
Proof. Let J J J a , s a,s a , s ⟨ a ⟩ \langle a\rangle ⟨ a ⟩ cd J = 2 \operatorname{cd} J=2 cd J = 2 Theorem 6.3 makes J J J a a a Δ \Delta Δ ∣ Δ ( s ) ∣ ≠ 1 |\Delta(s)|\ne1 ∣Δ ( s ) ∣ = 1
Let K ≤ U K\le U K ≤ U K 0 ≤ K K_0\le K K 0 ≤ K J J J [52 ] implies that K 0 K_0 K 0 K 0 K_0 K 0 Z \mathbb{Z} Z K 0 K_0 K 0 Theorem 6.4 makes it metabelian. Since metabelianity is a group identity, K K K Theorem 6.4 to K K K
Lemma 6.7. Let V V V C C C z ≠ 1 z\ne1 z = 1 C V ( z ) C_V(z) C V ( z ) D = Z ( C V ( z ) ) D=Z(C_V(z)) D = Z ( C V ( z ))
δ ( x ; z ) : = [ x , z ] = 1 ∧ ∀ y ( [ y , z ] = 1 ⇒ [ x , y ] = 1 ) . (6) \delta(x;z):=[x,z]=1\land\forall y\bigl([y,z]=1\Rightarrow[x,y]=1\bigr). \tag*{(6)} δ ( x ; z ) := [ x , z ] = 1 ∧ ∀ y ( [ y , z ] = 1 ⇒ [ x , y ] = 1 ) . (6) Proof. Put C = C V ( z ) C=C_V(z) C = C V ( z ) 1 ≠ z ∈ D 1\ne z\in D 1 = z ∈ D C C C F F F D ∩ F ≤ Z ( F ) = 1 D\cap F\le Z(F)=1 D ∩ F ≤ Z ( F ) = 1 1 ≠ f ∈ F 1\ne f\in F 1 = f ∈ F D ⟨ f ⟩ = D × ⟨ f ⟩ D\langle f\rangle=D\times\langle f\rangle D ⟨ f ⟩ = D × ⟨ f ⟩ ⟨ z , f ⟩ ≅ Z 2 \langle z,f\rangle\cong\mathbb{Z}^2 ⟨ z , f ⟩ ≅ Z 2 Theorem 6.4 identifies it with Z 2 \mathbb{Z}^2 Z 2 D D D Lemma 5.2 or Lemma 6.6 , respectively, gives C ≅ BS ( 1 , k ) C\cong\operatorname{BS}(1,k) C ≅ BS ( 1 , k ) BS ( 1 , − 1 ) \operatorname{BS}(1,-1) BS ( 1 , − 1 ) Z ( C V ( z ) ) Z(C_V(z)) Z ( C V ( z ))
Lemma 6.8. If U ∈ C U\in C U ∈ C z = a r z=a^r z = a r r ≥ 1 r\ge1 r ≥ 1 Z ( C U ( z ) ) Z(C_U(z)) Z ( C U ( z )) ⟨ a ⟩ \langle a\rangle ⟨ a ⟩ U U U
Proof. If every C U ( a r ) C_U(a^r) C U ( a r ) ker Δ = ⋃ r ≥ 1 C U ( a r ) \ker\Delta=\bigcup_{r\ge1}C_U(a^r) ker Δ = ⋃ r ≥ 1 C U ( a r ) U / ker Δ U/\ker\Delta U / ker Δ U U U z z z Z ( C U ( z ) ) Z(C_U(z)) Z ( C U ( z )) a r a^r a r
Lemma 6.9. Let U ∈ C U\in C U ∈ C ∣ Δ ( s ) ∣ ≠ 1 |\Delta(s)|\ne1 ∣Δ ( s ) ∣ = 1 C U ( s ) C_U(s) C U ( s )
Proof. For x ∈ C U ( s ) x\in C_U(s) x ∈ C U ( s ) J = ⟨ a , s , x ⟩ J=\langle a,s,x\rangle J = ⟨ a , s , x ⟩ Δ ( s ) \Delta(s) Δ ( s ) Lemma 6.6 show that J J J a a a s s s C J ( s ) C_J(s) C J ( s ) s s s w w w w p = a q w^p=a^q w p = a q p , q p,q p , q w w w s s s Δ ( s ) = 1 \Delta(s)=1 Δ ( s ) = 1 C J ( s ) C_J(s) C J ( s )
Choose a prime ℓ \ell ℓ v ℓ ( Δ ( s ) ) ≠ 0 v_\ell(\Delta(s))\ne0 v ℓ ( Δ ( s )) = 0
v ℓ ∘ Δ : C U ( s ) ⟶ Z v_\ell\circ\Delta:C_U(s)\longrightarrow\mathbb{Z} v ℓ ∘ Δ : C U ( s ) ⟶ Z is injective: for each x ∈ C U ( s ) x\in C_U(s) x ∈ C U ( s ) C J ( s ) C_J(s) C J ( s ) s s s Z \mathbb{Z} Z
Intersections with conjugates of cyclic subgroups
Lemma 6.10. Let J J J D = ⟨ d ⟩ D=\langle d\rangle D = ⟨ d ⟩
Δ ( r ) = ε q p , ε ∈ { 1 , − 1 } , p , q ≥ 1 , gcd ( p , q ) = 1 , p ≠ q . \Delta(r)=\frac{\varepsilon q}{p},\qquad\varepsilon\in\{1,-1\},\qquad p,q\geq1,\qquad\gcd(p,q)=1,\qquad p\ne q. Δ ( r ) = p εq , ε ∈ { 1 , − 1 } , p , q ≥ 1 , g cd( p , q ) = 1 , p = q . There is an integer e ≥ 1 e\geq1 e ≥ 1 n ≥ 1 n\geq1 n ≥ 1
D ∩ r − n D r n = ⟨ d e p n ⟩ , D ∩ r n D r − n = ⟨ d e q n ⟩ , (7) D\cap r^{-n}Dr^n=\langle d^{ep^n}\rangle,\qquad D\cap r^nDr^{-n}=\langle d^{eq^n}\rangle, \tag*{(7)} D ∩ r − n D r n = ⟨ d e p n ⟩ , D ∩ r n D r − n = ⟨ d e q n ⟩ , (7) r n d e p n r − n = d ε n e q n . (8) r^nd^{ep^n}r^{-n}=d^{\varepsilon^neq^n}. \tag*{(8)} r n d e p n r − n = d ε n e q n . (8) In particular, for every nonzero integer n n n
( D ∩ r − n D r n ) ( D ∩ r n D r − n ) = ⟨ d e ⟩ . (9) (D\cap r^{-n}Dr^n)(D\cap r^nDr^{-n})=\langle d^e\rangle. \tag*{(9)} ( D ∩ r − n D r n ) ( D ∩ r n D r − n ) = ⟨ d e ⟩ . (9) Proof. The element r r r v v v D D D x x x r r r
V = Stab J ( x ) = ⟨ b ⟩ , D ∩ V = ⟨ d h ⟩ = ⟨ b ℓ ⟩ , V=\operatorname{Stab}_J(x)=\langle b\rangle,\qquad D\cap V=\langle d^h\rangle=\langle b^\ell\rangle, V = Stab J ( x ) = ⟨ b ⟩ , D ∩ V = ⟨ d h ⟩ = ⟨ b ℓ ⟩ , where h , ℓ > 0 h,\ell>0 h , ℓ > 0 b b b g ≥ 1 g\geq1 g ≥ 1
V ∩ r − 1 V r = ⟨ b g p ⟩ , r b g p r − 1 = b ε g q . V\cap r^{-1}Vr=\langle b^{gp}\rangle,\qquad rb^{gp}r^{-1}=b^{\varepsilon gq}. V ∩ r − 1 V r = ⟨ b g p ⟩ , r b g p r − 1 = b ε g q . The image is V ∩ r V r − 1 = ⟨ b g q ⟩ V\cap rVr^{-1}=\langle b^{gq}\rangle V ∩ r V r − 1 = ⟨ b g q ⟩
The vertices x , r − 1 x , … , r − n x x,r^{-1}x,\ldots,r^{-n}x x , r − 1 x , … , r − n x b j b^j b j r n b j r − n r^nb^jr^{-n} r n b j r − n V V V V V V gcd ( p , q ) = 1 \gcd(p,q)=1 g cd( p , q ) = 1
V ∩ r − n V r n = ⟨ b g p n ⟩ , r n b g p n r − n = b ε n g q n . V\cap r^{-n}Vr^n=\langle b^{g p^n}\rangle,\qquad r^nb^{gp^n}r^{-n}=b^{\varepsilon^ngq^n}. V ∩ r − n V r n = ⟨ b g p n ⟩ , r n b g p n r − n = b ε n g q n . Suppose d j ∈ D d^j\in D d j ∈ D r n d j r − n ∈ D r^nd^jr^{-n}\in D r n d j r − n ∈ D v v v r − n v r^{-n}v r − n v x x x v v v r n v r^nv r n v x x x D ∩ V D\cap V D ∩ V d h k = b ℓ k d^{hk}=b^{\ell k} d hk = b ℓ k
g p n ∣ ℓ k , p n ∣ k . gp^n\mid\ell k,\qquad p^n\mid k. g p n ∣ ℓ k , p n ∣ k . The first condition is membership in the domain inside V V V ε n ℓ k q n / p n \varepsilon^n\ell kq^n/p^n ε n ℓ k q n / p n ℓ \ell ℓ D ∩ V D\cap V D ∩ V k = p n u k=p^nu k = p n u g ∣ ℓ u g\mid\ell u g ∣ ℓ u
e = h g gcd ( g , ℓ ) . e=\frac{hg}{\gcd(g,\ell)}. e = g cd( g , ℓ ) h g . Finally, gcd ( p n , q n ) = 1 \gcd(p^n,q^n)=1 g cd( p n , q n ) = 1 n n n n n n
Divisibility of exponents
Lemma 6.11. Let q > p ≥ 1 q>p\geq1 q > p ≥ 1 F j = q j − p j F_j=q^j-p^j F j = q j − p j j ≥ 0 j\geq0 j ≥ 0 i , j i,j i , j
gcd ( F i , F j ) = F gcd ( i , j ) . \gcd(F_i,F_j)=F_{\gcd(i,j)}. g cd( F i , F j ) = F g c d ( i , j ) . For arbitrary integers i , j i,j i , j
i ∣ j ⟺ F ∣ i ∣ ∣ F ∣ j ∣ . i\mid j\quad\Longleftrightarrow\quad F_{\lvert i\rvert}\mid F_{\lvert j\rvert}. i ∣ j ⟺ F ∣ i ∣ ∣ F ∣ j ∣ . Proof. For j ≥ i ≥ 1 j \ge i \ge1 j ≥ i ≥ 1
F j − q j − i F i = p i F j − i . F_j-q^{j-i}F_i=p^iF_{j-i}. F j − q j − i F i = p i F j − i . Since gcd ( F i , p ) = 1 \gcd(F_i,p)=1 g cd( F i , p ) = 1 F j F_j F j F 0 = 0 F_0=0 F 0 = 0 F 0 = 0 F_0=0 F 0 = 0
The nonsoluble case
For parameters z , s ∈ U z,s \in U z , s ∈ U
D = δ ( U ; z ) , R s = { x ∈ D : s x s − 1 ∈ D } , S s = { x ∈ D : s − 1 x s ∈ D } . D=\delta(U;z),\qquad R_s=\{x\in D:sxs^{-1}\in D\},\qquad S_s=\{x\in D:s^{-1}xs\in D\}. D = δ ( U ; z ) , R s = { x ∈ D : s x s − 1 ∈ D } , S s = { x ∈ D : s − 1 x s ∈ D } . Thus R s = D ∩ s − 1 D s R_s=D\cap s^{-1}Ds R s = D ∩ s − 1 D s S s = D ∩ s D s − 1 S_s=D\cap sDs^{-1} S s = D ∩ sD s − 1 P n ( z , s ) P_n(z,s) P n ( z , s )
z ≠ 1 z\ne1 z = 1 C U ( z ) C_U(z) C U ( z )
∀ g ∃ x ( x ≠ 1 ∧ δ ( x ; z ) ∧ δ ( g x g − 1 ; z ) ) \forall g\,\exists x\ (x\ne1\land\delta(x;z)\land\delta(gxg^{-1};z)) ∀ g ∃ x ( x = 1 ∧ δ ( x ; z ) ∧ δ ( g x g − 1 ; z ))
R s ≠ S s R_s\ne S_s R s = S s
The third condition is inequality of two definable sets, so it is also first-order. By Lemma 6.7 , D D D D D D U U U Δ D \Delta_D Δ D D D D ∣ Δ D ( s ) ∣ ≠ 1 |\Delta_D(s)|\ne1 ∣ Δ D ( s ) ∣ = 1 s s s R s R_s R s S s S_s S s
Assume P n ( z , s ) P_n(z,s) P n ( z , s )
A = R s S s , T = C U ( s ) , E = T 2 = { v 2 : [ v , s ] = 1 } . (10) A=R_sS_s,\qquad T=C_U(s),\qquad E=T^2=\{v^2:[v,s]=1\}. \tag*{(10)} A = R s S s , T = C U ( s ) , E = T 2 = { v 2 : [ v , s ] = 1 } . (10) The product defining A A A D D D
For verification, write D = ⟨ d ⟩ D=\langle d\rangle D = ⟨ d ⟩ T = ⟨ r ⟩ T=\langle r\rangle T = ⟨ r ⟩ Lemma 6.9 with base subgroup D D D r r r
Δ D ( r ) = ε q / p , q > p ≥ 1 , gcd ( p , q ) = 1. \Delta_D(r)=\varepsilon q/p,\qquad q>p\ge1,\qquad\gcd(p,q)=1. Δ D ( r ) = εq / p , q > p ≥ 1 , g cd( p , q ) = 1. Since s = r k s=r^k s = r k k ≠ 0 k\ne0 k = 0 ⟨ d , r ⟩ \langle d,r\rangle ⟨ d , r ⟩ s s s Lemma 6.10 gives
A = ⟨ d e ⟩ . A=\langle d^e\rangle. A = ⟨ d e ⟩ . Put c = d e c=d^e c = d e n ≥ 0 n\ge0 n ≥ 0
r n c p n r − n = c ε n q n , r n c j r − n ∈ A ⟺ p n ∣ j . r^nc^{p^n}r^{-n}=c^{\varepsilon^nq^n},\qquad r^nc^jr^{-n}\in A\Longleftrightarrow p^n\mid j. r n c p n r − n = c ε n q n , r n c j r − n ∈ A ⟺ p n ∣ j . These integers and generators are used only in the proof; they do not occur in the defining formulas.
For y ∈ E y\in E y ∈ E
I y = { y x y − 1 x − 1 : x ∈ A , y x y − 1 ∈ A } . (11) I_y=\{yxy^{-1}x^{-1}:x\in A,\ yxy^{-1}\in A\}. \tag*{(11)} I y = { y x y − 1 x − 1 : x ∈ A , y x y − 1 ∈ A } . (11) If α ( x ; z , s ) \alpha(x;z,s) α ( x ; z , s ) A A A I y I_y I y
ι ( w , y ; z , s ) : = ∃ x ( α ( x ; z , s ) ∧ α ( y x y − 1 ; z , s ) ∧ w = y x y − 1 x − 1 ) . (12) \iota(w,y;z,s):=\exists x\left(\alpha(x;z,s)\land\alpha(yxy^{-1};z,s)\land w=yxy^{-1}x^{-1}\right). \tag*{(12)} ι ( w , y ; z , s ) := ∃ x ( α ( x ; z , s ) ∧ α ( y x y − 1 ; z , s ) ∧ w = y x y − 1 x − 1 ) . (12) Since E = ⟨ r 2 ⟩ E=\langle r^2\rangle E = ⟨ r 2 ⟩
I r 2 j = ⟨ c q 2 ∣ j ∣ − p 2 ∣ j ∣ ⟩ ( j ∈ Z ) . (13) I_{r^{2j}}=\langle c^{q^{2|j|}-p^{2|j|}}\rangle\qquad(j\in\mathbb{Z}). \tag*{(13)} I r 2 j = ⟨ c q 2∣ j ∣ − p 2∣ j ∣ ⟩ ( j ∈ Z ) . (13) For j = 0 j=0 j = 0 I 1 = { 1 } I_1=\{1\} I 1 = { 1 } E E E
Div ( y 1 , y 2 ; z , s ) ⟺ I y 2 ⊆ I y 1 . (14) \operatorname{Div}(y_1,y_2;z,s)\Longleftrightarrow I_{y_2}\subseteq I_{y_1}. \tag*{(14)} Div ( y 1 , y 2 ; z , s ) ⟺ I y 2 ⊆ I y 1 . (14) Subgroup inclusion is expressed by ∀ w ( ι ( w , y 2 ; z , s ) ⇒ ι ( w , y 1 ; z , s ) ) \forall w\ (\iota(w,y_2;z,s)\Rightarrow\iota(w,y_1;z,s)) ∀ w ( ι ( w , y 2 ; z , s ) ⇒ ι ( w , y 1 ; z , s )) Lemma 6.11 , applied to p 2 , q 2 p^2,q^2 p 2 , q 2
Div ( r 2 i , r 2 j ; z , s ) ⟺ i ∣ j . (15) \operatorname{Div}(r^{2i},r^{2j};z,s)\Longleftrightarrow i\mid j. \tag*{(15)} Div ( r 2 i , r 2 j ; z , s ) ⟺ i ∣ j . (15) The soluble case
If U ∈ C U\in\mathcal{C} U ∈ C Theorem 6.4 gives
U ≅ BS ( 1 , k ) = B ⋊ ⟨ v ⟩ , B = Z [ 1 / ∣ k ∣ ] , ∣ k ∣ > 1. U\cong\operatorname{BS}(1,k)=B\rtimes\langle v\rangle,\qquad B=\mathbb{Z}[1/|k|],\quad|k|>1. U ≅ BS ( 1 , k ) = B ⋊ ⟨ v ⟩ , B = Z [ 1/∣ k ∣ ] , ∣ k ∣ > 1. Here conjugation by v v v B B B k k k U → U / B ≅ Z U\to U/B\cong\mathbb{Z} U → U / B ≅ Z height map ; the height of b v j bv^j b v j j j j Z 2 \mathbb{Z}^2 Z 2 Z 2 \mathbb{Z}^2 Z 2 m 2 = n 2 m^2=n^2 m 2 = n 2
Let P s ( z , s ) \mathcal{P}_{s}(z,s) P s ( z , s )
z ≠ 1 , C U ( z ) is abelian and normal in U , [ z , s ] ≠ 1. z\ne1,\qquad C_U(z)\text{ is abelian and normal in }U,\qquad[z,s]\ne1. z = 1 , C U ( z ) is abelian and normal in U , [ z , s ] = 1. Normality here is the first-order condition
∀ g ∀ x ( [ x , z ] = 1 ⟺ [ g x g − 1 , z ] = 1 ) . \forall g\,\forall x\ \bigl([x,z]=1\Longleftrightarrow[gxg^{-1},z]=1\bigr). ∀ g ∀ x ( [ x , z ] = 1 ⟺ [ g x g − 1 , z ] = 1 ) . These conditions force C U ( z ) = B C_U(z)=B C U ( z ) = B s ∉ B s\notin B s ∈ / B B B B B B B B B B z ∈ B ∖ { 1 } z\in B\setminus\{1\} z ∈ B ∖ { 1 } B B B
Set
A = C U ( z ) = B , T = C U ( s ) , E = T 2 . A=C_U(z)=B,\qquad T=C_U(s),\qquad E=T^2. A = C U ( z ) = B , T = C U ( s ) , E = T 2 . Projection to U / B ≅ Z U/B\cong\mathbb{Z} U / B ≅ Z T T T T ∩ B T\cap B T ∩ B s s s T = ⟨ r ⟩ T=\langle r\rangle T = ⟨ r ⟩ r r r h h h Q = k 2 h > 1 Q=k^{2h}>1 Q = k 2 h > 1
I r 2 j = ( Q ∣ j ∣ − 1 ) B ( j ∈ Z ) . I_{r^{2j}}=(Q^{|j|}-1)B\qquad(j\in\mathbb{Z}). I r 2 j = ( Q ∣ j ∣ − 1 ) B ( j ∈ Z ) . For negative j j j Q Q Q B B B
Every positive integer Q j − 1 Q^j-1 Q j − 1 k k k d , e d,e d , e e B ⊆ d B eB\subseteq dB e B ⊆ d B d ∣ e d\mid e d ∣ e Z \mathbb{Z} Z e / d ∈ Z [ 1 / ∣ k ∣ ] e/d\in\mathbb{Z}[1/|k|] e / d ∈ Z [ 1/∣ k ∣ ] d d d k k k Lemma 6.11 , with p = 1 p=1 p = 1 q = Q q=Q q = Q (15) in this case as well.
The admissible parameters and the interpretation
To be metabelian is expressed by the sentence
Met : = ∀ x 1 , x 2 , x 3 , x 4 [ [ x 1 , x 2 ] , [ x 3 , x 4 ] ] = 1. \operatorname{Met}:=\forall x_1,x_2,x_3,x_4\ [[x_1,x_2],[x_3,x_4]]=1. Met := ∀ x 1 , x 2 , x 3 , x 4 [[ x 1 , x 2 ] , [ x 3 , x 4 ]] = 1. For groups in C \mathcal{C} C Theorem 6.4 . Define
P 0 ( z , s ) : = ( ¬ Met ∧ P n ( z , s ) ) ∨ ( Met ∧ P s ( z , s ) ) . \mathcal{P}_{0}(z,s):=(\neg\operatorname{Met}\wedge\mathcal{P}_{n}(z,s))\vee(\operatorname{Met}\wedge\mathcal{P}_{s}(z,s)). P 0 ( z , s ) := ( ¬ Met ∧ P n ( z , s )) ∨ ( Met ∧ P s ( z , s )) . Use the definition of A A A (10) when ¬ Met \neg\operatorname{Met} ¬ Met A = C U ( z ) A=C_{U}(z) A = C U ( z ) Met \operatorname{Met} Met α ( x ; z , s ) \alpha(x;z,s) α ( x ; z , s ) E E E
η ( y ; s ) : = ∃ v ( [ v , s ] = 1 ∧ y = v 2 ) . \eta(y;s):=\exists v\left([v,s]=1\wedge y=v^{2}\right). η ( y ; s ) := ∃ v ( [ v , s ] = 1 ∧ y = v 2 ) . In (14) require also η ( y 1 ; s ) \eta(y_{1};s) η ( y 1 ; s ) η ( y 2 ; s ) \eta(y_{2};s) η ( y 2 ; s )
P ( z , s , u ) : = P 0 ( z , s ) ∧ η ( u ; s ) ∧ u ≠ 1 ∧ ∀ y ( η ( y ; s ) ⇒ Div ( u , y ; z , s ) ) . (16) \mathcal{P}(z,s,u):=\mathcal{P}_{0}(z,s)\wedge\eta(u;s)\wedge u\ne1
\wedge\forall y\left(\eta(y;s)\Rightarrow\operatorname{Div}(u,y;z,s)\right). \tag*{(16)} P ( z , s , u ) := P 0 ( z , s ) ∧ η ( u ; s ) ∧ u = 1 ∧ ∀ y ( η ( y ; s ) ⇒ Div ( u , y ; z , s ) ) . (16) Proof of Theorem 6.2. For every pair satisfying P 0 \mathcal{P}_{0} P 0 E = ⟨ r 2 ⟩ E=\langle r^{2}\rangle E = ⟨ r 2 ⟩ Div ( r 2 i , r 2 j ; z , s ) \operatorname{Div}(r^{2i},r^{2j};z,s) Div ( r 2 i , r 2 j ; z , s ) i ∣ j i\mid j i ∣ j (16) select exactly u = r 2 u=r^{2} u = r 2 u = r − 2 u=r^{-2} u = r − 2
Z ⟶ E , n ⟼ u n \mathbb{Z}\longrightarrow E,\qquad n\longmapsto u^{n} Z ⟶ E , n ⟼ u n identifies ( Z , + , ∣ , 0 , 1 ) (\mathbb{Z},+,\mid,0,1) ( Z , + , ∣ , 0 , 1 ) ( E , ⋅ , Div , 1 U , u ) (E,\cdot,\operatorname{Div},1_{U},u) ( E , ⋅ , Div , 1 U , u )
The parameter set is nonempty. In the nonsoluble case choose z = a r z=a^{r} z = a r Lemma 6.8 and take an element s s s ∣ Δ ( s ) ∣ ≠ 1 |\Delta(s)|\ne1 ∣Δ ( s ) ∣ = 1 P n \mathcal{P}_{n} P n z z z s s s P s \mathcal{P}_{s} P s E E E u u u
All the formulas are fixed, equality is ordinary equality, and every admissible tuple gives the same structure. This proves uniformity, regularity and injectivity. Applying the classical definition of multiplication in ( Z , + , ∣ , 0 , 1 ) (\mathbb{Z},+,\mid,0,1) ( Z , + , ∣ , 0 , 1 )
Corollary 6.12. Arithmetic is uniformly, regularly and injectively interpretable in each of the following classes:
non-unimodular GBS groups;
increasing unions of non-unimodular GBS groups whose integral cohomological dimension is two.
Proof. A GBS group has an aspherical graph of circles of dimension two. In the non-unimodular case a vertex generator a a a s s s ⟨ a ⟩ \langle a\rangle ⟨ a ⟩ Theorem 6.2 .
For U = ⋃ i G i U=\bigcup_iG_i U = ⋃ i G i a , s a,s a , s G 0 G_0 G 0 G i G_i G i a a a G i G_i G i ⟨ a ⟩ \langle a\rangle ⟨ a ⟩ U U U U U U
Corollary 6.13. The interpretation is uniform over all groups BS ( m , n ) \operatorname{BS}(m,n) BS ( m , n ) m , n ≠ 0 m,n\ne0 m , n = 0 ∣ m ∣ ≠ ∣ n ∣ |m|\ne|n| ∣ m ∣ = ∣ n ∣
Example 6.14. In G = BS ( 2 , 3 ) = ⟨ a , t ∣ t a 2 t − 1 = a 3 ⟩ G=\operatorname{BS}(2,3)=\langle a,t\mid ta^{2}t^{-1}=a^{3}\rangle G = BS ( 2 , 3 ) = ⟨ a , t ∣ t a 2 t − 1 = a 3 ⟩ D = ⟨ a ⟩ = C G ( a ) D=\langle a\rangle=C_{G}(a) D = ⟨ a ⟩ = C G ( a ) t t t D D D D D D E = C G ( t ) 2 = ⟨ t 2 ⟩ E=C_{G}(t)^{2}=\langle t^{2}\rangle E = C G ( t ) 2 = ⟨ t 2 ⟩
I t 2 j = ⟨ a 9 ∣ j ∣ − 4 ∣ j ∣ ⟩ . I_{t^{2j}}=\left\langle a^{9|j|-4|j|}\right\rangle. I t 2 j = ⟨ a 9∣ j ∣ − 4∣ j ∣ ⟩ . For example, I t 2 = ⟨ a 5 ⟩ I_{t^{2}}=\langle a^{5}\rangle I t 2 = ⟨ a 5 ⟩ I t 4 = ⟨ a 65 ⟩ I_{t^{4}}=\langle a^{65}\rangle I t 4 = ⟨ a 65 ⟩
Bi-interpretability
Definition 6.15. Two structures are bi-interpretable if they are interpretable in one another and both composite interpretations are definably isomorphic to the original structures. Parameters are allowed in the interpretations and in the two isomorphisms.
Proposition 6.16. For every integer k k k ∣ k ∣ > 1 |k| > 1 ∣ k ∣ > 1 BS ( 1 , k ) \operatorname{BS}(1,k) BS ( 1 , k ) Z \mathbb{Z} Z Theorem 6.2 is bi-interpretable with Z \mathbb{Z} Z
Proof. For k > 1 k > 1 k > 1 [12 Theorem 3] . For the remaining case write
G = BS ( 1 , − k ) = B ⋊ ⟨ t ⟩ , B = Z [ 1 / k ] , k > 1 , G = \operatorname{BS}(1,-k) = B \rtimes\langle t\rangle,\qquad B = \mathbb{Z}[1/k],\qquad k > 1, G = BS ( 1 , − k ) = B ⋊ ⟨ t ⟩ , B = Z [ 1/ k ] , k > 1 , where t t t B B B − k -k − k a a a s = t 2 s = t^2 s = t 2
H = B ⋊ ⟨ s ⟩ ≅ BS ( 1 , k 2 ) . H = B \rtimes\langle s\rangle\cong\operatorname{BS}(1,k^2). H = B ⋊ ⟨ s ⟩ ≅ BS ( 1 , k 2 ) . Since B = C G ( a ) B = C_G(a) B = C G ( a ) C G ( t ) = ⟨ t ⟩ C_G(t) = \langle t\rangle C G ( t ) = ⟨ t ⟩ H = C G ( a ) C G ( t ) 2 H = C_G(a)C_G(t)^2 H = C G ( a ) C G ( t ) 2 G G G
Inside H H H B = C H ( a ) B = C_H(a) B = C H ( a ) ⟨ s ⟩ = C H ( s ) \langle s\rangle= C_H(s) ⟨ s ⟩ = C H ( s ) h ∈ H h \in H h ∈ H h = b v h = bv h = b v b ∈ B b \in B b ∈ B v ∈ ⟨ s ⟩ v \in\langle s\rangle v ∈ ⟨ s ⟩ t t t
τ ( b v ) = b − k v . \tau(bv) = b^{-k}v. τ ( b v ) = b − k v . On H × { 0 , 1 } H \times\{0,1\} H × { 0 , 1 }
( h , i ) ( h ′ , j ) = ( h τ i ( h ′ ) s i j , i + j ( m o d 2 ) ) . (h,i)(h',j) = (h\tau^i(h')s^{ij},i+j\pmod2). ( h , i ) ( h ′ , j ) = ( h τ i ( h ′ ) s ij , i + j ( mod 2 )) . The two-element set is coded by 1 H , s 1_H,s 1 H , s ( h , i ) ↦ h t i (h,i)\mapsto ht^i ( h , i ) ↦ h t i G G G G G G H H H H × { 0 } H \times\{0\} H × { 0 } h ↦ ( h , 0 ) h\mapsto(h,0) h ↦ ( h , 0 ) G G G H H H H ≅ BS ( 1 , k 2 ) H\cong\operatorname{BS}(1,k^2) H ≅ BS ( 1 , k 2 ) Z \mathbb{Z} Z
The final assertion follows from Theorem 6.4 and the exclusion of k = 1 , − 1 k=1,-1 k = 1 , − 1
For fixed k > 1 k > 1 k > 1 BS ( 1 , − k ) \operatorname{BS}(1,-k) BS ( 1 , − k )
a ≠ 1 , t a t − 1 = a − k a\ne1,\qquad tat^{-1}=a^{-k} a = 1 , t a t − 1 = a − k forces a a a t t t H H H τ \tau τ H H H H H H
Proposition 6.17. There is a group in C \mathcal{C} C Z \mathbb{Z} Z
Proof. Let
U = ⟨ a , t 0 , t 1 , … ∣ t i a t i − 1 = a 2 ( i ≥ 0 ) ⟩ . U=\langle a,t_0,t_1,\ldots\mid t_iat_i^{-1}=a^2\ (i\ge0)\rangle. U = ⟨ a , t 0 , t 1 , … ∣ t i a t i − 1 = a 2 ( i ≥ 0 )⟩ . This is the fundamental group of a graph of infinite cyclic groups with one vertex and countably many loop edges. Its graph of circles is an aspherical two-dimensional complex. It contains BS ( 1 , 2 ) \operatorname{BS}(1,2) BS ( 1 , 2 ) cd U = 2 \operatorname{cd}U=2 cd U = 2 ⟨ a ⟩ \langle a\rangle ⟨ a ⟩ Δ ( t i ) = 2 \Delta(t_i)=2 Δ ( t i ) = 2 i i i U U U t i t_i t i
If U U U Z \mathbb{Z} Z U U U
Commensurators and arithmetic in one-relator groups
Theorem 7.1. The ring ( Z , + , × , 0 , 1 ) (\mathbb{Z}, +, \times, 0, 1) ( Z , + , × , 0 , 1 )
A one-relator group G G G cd G ≤ 2 \operatorname{cd} G \le2 cd G ≤ 2 [39 ] , and this bound passes to subgroups [2 Chapter VIII] .
The commensurator of the base cyclic subgroup
Fix
H = ⟨ a , s ⟩ ≅ BS ( m , n ) , s a m s − 1 = a n , ∣ m ∣ ≠ ∣ n ∣ , H = \langle a,s\rangle\cong\operatorname{BS}(m,n), \qquad sa^{m}s^{-1} = a^{n}, \qquad|m| \ne|n|, H = ⟨ a , s ⟩ ≅ BS ( m , n ) , s a m s − 1 = a n , ∣ m ∣ = ∣ n ∣ , and put M = Comm G ( ⟨ a ⟩ ) M = \operatorname{Comm}_G(\langle a\rangle) M = Comm G (⟨ a ⟩) M M M ⟨ a ⟩ \langle a\rangle ⟨ a ⟩ Theorem 6.2 .
Lemma 7.2. For every nonzero integer r r r
C G ( a r ) ≤ M , C G ( a r ) = C M ( a r ) . C_G(a^r) \le M, \qquad C_G(a^r) = C_M(a^r). C G ( a r ) ≤ M , C G ( a r ) = C M ( a r ) . Proof. An element centralizing a r a^r a r ⟨ a ⟩ \langle a\rangle ⟨ a ⟩ a r a^r a r M M M
Proposition 7.3. The subgroup M M M G G G
Some z = a r z = a^r z = a r r ≥ 1 r \ge1 r ≥ 1 D = Z ( C G ( z ) ) D = Z(C_G(z)) D = Z ( C G ( z ))
M = { g ∈ G : ∃ x ( δ ( x ; z ) ∧ x ≠ 1 ∧ δ ( g x g − 1 ; z ) ) } . (17) M = \{g \in G : \exists x\ (\delta(x;z) \land x \ne1 \land\delta(gxg^{-1};z))\}. \tag*{(17)} M = { g ∈ G : ∃ x ( δ ( x ; z ) ∧ x = 1 ∧ δ ( g x g − 1 ; z ))} . (17) Every C G ( a r ) C_G(a^r) C G ( a r ) r ≥ 1 r \ge1 r ≥ 1 M ≅ BS ( 1 , k ) M \cong\operatorname{BS}(1,k) M ≅ BS ( 1 , k ) ∣ k ∣ > 1 |k| > 1 ∣ k ∣ > 1
M = N G ( C G ( a ) ) . (18) M = N_G(C_G(a)). \tag*{(18)} M = N G ( C G ( a )) . (18) Proof. In the first case, Lemma 6.7 makes D D D a r a^r a r ⟨ a ⟩ \langle a\rangle ⟨ a ⟩ Comm G ( D ) = M \operatorname{Comm}_G(D) = M Comm G ( D ) = M (17) .
In the second case, Lemmas 6.5 and 7.2 show that ker ( Δ : M → Q × ) \ker(\Delta: M \to\mathbb{Q}^{\times}) ker ( Δ : M → Q × ) M M M Theorem 6.4 and the unequal-power relation give M ≅ BS ( 1 , k ) M \cong\operatorname{BS}(1,k) M ≅ BS ( 1 , k ) ∣ k ∣ > 1 |k| > 1 ∣ k ∣ > 1
Let B ≅ Z [ 1 / ∣ k ∣ ] B \cong\mathbb{Z}[1/|k|] B ≅ Z [ 1/∣ k ∣ ] a a a M / B ≅ Z M/B \cong\mathbb{Z} M / B ≅ Z m a ˉ = n a ˉ m\bar{a}=n\bar{a} m a ˉ = n a ˉ m ≠ n m \ne n m = n C M ( a ) = B C_M(a)=B C M ( a ) = B C G ( a ) = B C_G(a)=B C G ( a ) = B M M M B B B g ∈ N G ( B ) g \in N_G(B) g ∈ N G ( B ) a a a g a g − 1 gag^{-1} g a g − 1 B B B g ∈ M g \in M g ∈ M (18) .
Proposition 7.4. Every finitely generated subgroup J J J H ≤ J ≤ M H \leq J \leq M H ≤ J ≤ M G G G H H H M M M M M M H H H
Moreover, M M M G G G H H H M M M H H H G G G
Proof. The first assertion is Lemma 6.6 applied inside M M M K K K H H H a a a K K K ⟨ a ⟩ \langle a\rangle ⟨ a ⟩ K ≤ M K \leq M K ≤ M M = { g 1 , g 2 , … } M=\{g_1,g_2,\ldots\} M = { g 1 , g 2 , … } ⟨ H , g 1 , … , g i ⟩ \langle H,g_1,\ldots,g_i\rangle ⟨ H , g 1 , … , g i ⟩
If M M M K K K H H H x ∈ M x \in M x ∈ M ⟨ K , x ⟩ \langle K,x\rangle ⟨ K , x ⟩ x ∈ K x \in K x ∈ K K = M K=M K = M
All applications of Kropholler’s theorem here are to finitely generated subgroups. We do not assume that the commensurator is finitely generated.
A definable family of admissible subgroups
To prove regularity in Theorem 7.1 , we give first-order conditions on the parameters defining the intermediate subgroup. Write
AbC ( z ) : = ∀ x ∀ y ( ( [ x , z ] = 1 ∧ [ y , z ] = 1 ) ⇒ [ x , y ] = 1 ) . \operatorname{AbC}(z) := \forall x \forall y \left(([x,z]=1 \land[y,z]=1) \Rightarrow[x,y]=1\right). AbC ( z ) := ∀ x ∀ y ( ([ x , z ] = 1 ∧ [ y , z ] = 1 ) ⇒ [ x , y ] = 1 ) . For z ∈ G z \in G z ∈ G
μ n ( g ; z ) : = ∃ x ( δ ( x ; z ) ∧ x ≠ 1 ∧ δ ( g x g − 1 ; z ) ) , \mu_n(g;z) := \exists x\left(\delta(x;z) \land x \ne1 \land\delta(gxg^{-1};z)\right), μ n ( g ; z ) := ∃ x ( δ ( x ; z ) ∧ x = 1 ∧ δ ( g x g − 1 ; z ) ) , μ s ( g ; z ) : = ∀ x ( [ x , z ] = 1 ⟺ [ g x g − 1 , z ] = 1 ) . \mu_s(g;z) := \forall x\left([x,z]=1 \Longleftrightarrow[gxg^{-1},z]=1\right). μ s ( g ; z ) := ∀ x ( [ x , z ] = 1 ⟺ [ g x g − 1 , z ] = 1 ) . The second formula defines N z = N G ( C G ( z ) ) N_z=N_G(C_G(z)) N z = N G ( C G ( z )) z ≠ 1 z \ne1 z = 1 ¬ AbC ( z ) \neg\operatorname{AbC}(z) ¬ AbC ( z ) Comm G ( D z ) \operatorname{Comm}_G(D_z) Comm G ( D z ) D z = Z ( C G ( z ) ) D_z=Z(C_G(z)) D z = Z ( C G ( z ))
R s ( z ) = { x ∈ D z : s x s − 1 ∈ D z } , S s ( z ) = { x ∈ D z : s − 1 x s ∈ D z } . R_s(z)=\{x\in D_z:sxs^{-1}\in D_z\}, \qquad S_s(z)=\{x\in D_z:s^{-1}xs\in D_z\}. R s ( z ) = { x ∈ D z : s x s − 1 ∈ D z } , S s ( z ) = { x ∈ D z : s − 1 x s ∈ D z } . Define the first parameter condition by
Q n ( z ) : = z ≠ 1 ∧ ¬ AbC ( z ) ∧ ∃ s ( μ n ( s ; z ) ∧ R s ( z ) ≠ S s ( z ) ) . Q_n(z):=z\ne1\land\neg\operatorname{AbC}(z)\land\exists s\left(\mu_n(s;z)\land R_s(z)\ne S_s(z)\right). Q n ( z ) := z = 1 ∧ ¬ AbC ( z ) ∧ ∃ s ( μ n ( s ; z ) ∧ R s ( z ) = S s ( z ) ) . For the second condition, relativize the metabelian identity to N z N_z N z
Q s ( z ) : = z ≠ 1 ∧ AbC ( z ) ∧ Met N z ∧ ∃ x , y ∈ N z ( [ x 2 , y 2 ] ≠ 1 ) . Q_s(z):=z\ne1\land\operatorname{AbC}(z)\land\operatorname{Met}^{N_z}\land\exists x,y\in N_z\left([x^2,y^2]\ne1\right). Q s ( z ) := z = 1 ∧ AbC ( z ) ∧ Met N z ∧ ∃ x , y ∈ N z ( [ x 2 , y 2 ] = 1 ) . All subgroup-membership conditions and restricted quantifiers in these expressions abbreviate the displayed first-order formulas. Let
Q ( z ) : = Q n ( z ) ∨ Q s ( z ) , (19) Q(z):=Q_n(z)\lor Q_s(z), \tag*{(19)} Q ( z ) := Q n ( z ) ∨ Q s ( z ) , (19) μ ( g ; z ) : = ( ¬ AbC ( z ) ∧ μ n ( g ; z ) ) ∨ ( AbC ( z ) ∧ μ s ( g ; z ) ) . (20) \mu(g;z):=\left(\neg\operatorname{AbC}(z)\land\mu_n(g;z)\right)\lor\left(\operatorname{AbC}(z)\land\mu_s(g;z)\right). \tag*{(20)} μ ( g ; z ) := ( ¬ AbC ( z ) ∧ μ n ( g ; z ) ) ∨ ( AbC ( z ) ∧ μ s ( g ; z ) ) . (20) Lemma 7.5. If Q ( z ) Q(z) Q ( z ) M z = μ ( G ; z ) M_z=\mu(G;z) M z = μ ( G ; z ) C C C G G G Q ( G ) Q(G) Q ( G )
Proof. Suppose Q n ( z ) Q_n(z) Q n ( z ) M z M_z M z D z D_z D z R s ( z ) ≠ S s ( z ) R_s(z)\ne S_s(z) R s ( z ) = S s ( z ) s s s M z M_z M z Theorem 6.2 .
Suppose Q s ( z ) Q_s(z) Q s ( z ) M z = N z M_z=N_z M z = N z G G G Theorem 6.4 , it is locally cyclic or isomorphic to BS ( 1 , k ) \operatorname{BS}(1,k) BS ( 1 , k ) BS ( 1 , 1 ) \operatorname{BS}(1,1) BS ( 1 , 1 ) BS ( 1 , − 1 ) \operatorname{BS}(1,-1) BS ( 1 , − 1 ) Q s Q_s Q s M z ≅ BS ( 1 , k ) M_z\cong\operatorname{BS}(1,k) M z ≅ BS ( 1 , k ) ∣ k ∣ > 1 |k|>1 ∣ k ∣ > 1 M z ∈ C M_z\in C M z ∈ C
For nonemptiness, apply Proposition 7.3 to the given subgroup H H H z = a r z=a^r z = a r Q n ( z ) Q_n(z) Q n ( z ) z = a z=a z = a N z = M ≅ BS ( 1 , k ) N_z=M\cong\operatorname{BS}(1,k) N z = M ≅ BS ( 1 , k ) ∣ k ∣ > 1 |k|>1 ∣ k ∣ > 1 Q s ( z ) Q_s(z) Q s ( z )
Proof of Theorem 7.1 . For every w w w Q ( w ) Q(w) Q ( w ) Theorem 6.2 inside M w M_w M w P \mathcal{P} P (16) . A parameter formula in G G G
P G ( w , z , s , u ) : = Q ( w ) ∧ μ ( z ; w ) ∧ μ ( s ; w ) ∧ μ ( u ; w ) ∧ P M w ( z , s , u ) , P_G(w,z,s,u):=Q(w)\land\mu(z;w)\land\mu(s;w)\land\mu(u;w)\land P^{M_w}(z,s,u), P G ( w , z , s , u ) := Q ( w ) ∧ μ ( z ; w ) ∧ μ ( s ; w ) ∧ μ ( u ; w ) ∧ P M w ( z , s , u ) , where every quantifier in P M w P^{M_w} P M w μ ( G ; w ) \mu(G;w) μ ( G ; w )
Lemma 7.5 and Theorem 6.2 show that P G ( G ) P_G(G) P G ( G )
Corollary 7.6. With the notation above, arithmetic is uniformly, regularly and injectively interpretable in the pure group M M M M M M Z \mathbb{Z} Z
Proof. Apply Theorem 6.2 and Proposition 6.16 , respectively, to M M M
The second assertion is a statement about the commensurator M M M G G G
Further interpretations and undecidability
Lemma 7.7. Every fixed finitely presented group is absolutely and injectively interpretable in ( Z , + , × , 0 , 1 ) (\mathbb{Z},+,\times,0,1) ( Z , + , × , 0 , 1 )
Proof. Fix H = ⟨ x 1 , … , x r ∣ R 1 , … , R k ⟩ H=\langle x_1,\ldots,x_r\mid R_1,\ldots,R_k\rangle H = ⟨ x 1 , … , x r ∣ R 1 , … , R k ⟩ x 1 ± 1 , … , x r ± 1 x_1^{\pm1},\ldots,x_r^{\pm1} x 1 ± 1 , … , x r ± 1 Z \mathbb{Z} Z W W W
The relation F ( u , v ) F(u,v) F ( u , v ) H H H [12 ] , Section 2.1. For an injective interpretation, use
W min = { u ∈ W : ∀ v ∈ W ( v < u ⇒ ¬ F ( v , u ) ) } . W_{\min}=\{u\in W:\forall v\in W\,(v<u\Rightarrow\neg F(v,u))\}. W m i n = { u ∈ W : ∀ v ∈ W ( v < u ⇒ ¬ F ( v , u ))} . Each equivalence class has one least code. On W min W_{\min} W m i n F ( concat ( u , v ) , w ) F(\operatorname{concat}(u,v),w) F ( concat ( u , v ) , w )
Corollary 7.8. Every fixed finitely presented group is uniformly, regularly and injectively interpretable in every group in C C C
Proof. Compose Lemma 7.7 with Theorem 6.2 or Theorem 7.1. The admissible parameter set is unchanged.
These group operations are obtained by arithmetic coding. The definable subgroup in Theorem 5.7, in contrast, has the inherited group operations.
Corollary 7.9. Every one-relator group containing a non-unimodular Baumslag–Solitar subgroup has undecidable elementary theory. One computable translation of arithmetic sentences works for all groups in this class. The same assertion holds for the class C C C
Proof. Let P ( c ˉ ) P(\bar{c}) P ( c ˉ ) σ I ( c ˉ ) \sigma^{I}(\bar{c}) σ I ( c ˉ ) σ \sigma σ
σ ^ : = ∃ c ˉ ( P ( c ˉ ) ∧ σ I ( c ˉ ) ) . \hat{\sigma} := \exists\bar{c}\left(P(\bar{c}) \wedge\sigma^{I}(\bar{c})\right). σ ^ := ∃ c ˉ ( P ( c ˉ ) ∧ σ I ( c ˉ ) ) . Every admissible tuple gives the standard integer ring, and there is at least one such tuple. Hence, for every group V V V
V ⊨ σ ^ ⟺ Z ⊨ σ . V \models\hat{\sigma} \Longleftrightarrow\mathbb{Z} \models\sigma. V ⊨ σ ^ ⟺ Z ⊨ σ . The translation is computable and independent of V V V [55 ] .
The results of this section do not use either result from [46 , 47 ] . Their defining formulas contain universal quantifiers; the Diophantine problems are considered separately in Section 8.
Equations and other decision problems
Proposition 8.1. For every integer n > 1 n > 1 n > 1 BS ( 1 , n ) \operatorname{BS}(1,n) BS ( 1 , n )
Proof. The arithmetic interpretation is due to Khelif [30 ] ; the stronger regular bi-interpretation and elementary-equivalence classification are given in [28 ] , [12 ] . For Noetherianity, the standard faithful representation is
a ⟼ ( 1 1 0 1 ) , t ⟼ ( n 0 0 1 ) . a \longmapsto\begin{pmatrix}1 & 1 \\ 0 & 1\end{pmatrix}, \qquad t \longmapsto\begin{pmatrix}n & 0 \\ 0 & 1\end{pmatrix}. a ⟼ ( 1 0 1 1 ) , t ⟼ ( n 0 0 1 ) . It identifies Z [ 1 / n ] ⋊ Z \mathbb{Z}[1/n] \rtimes\mathbb{Z} Z [ 1/ n ] ⋊ Z GL 2 ( Q ) \operatorname{GL}_2(\mathbb{Q}) GL 2 ( Q )
Proposition 8.2. For nonzero integers m , n m,n m , n BS ( m , n ) \operatorname{BS}(m,n) BS ( m , n )
min { ∣ m ∣ , ∣ n ∣ } = 1 or ∣ m ∣ = ∣ n ∣ . \min\{|m|, |n|\} = 1 \quad\text{or} \quad|m| = |n|. min { ∣ m ∣ , ∣ n ∣ } = 1 or ∣ m ∣ = ∣ n ∣. Moreover, BS ( m , ± m ) \operatorname{BS}(m,\pm m) BS ( m , ± m )
Proof. The Noetherianity criterion is [23 Proposition 5.18] , citing [1 ] . The unimodular groups have the explicit finite-index direct products of Proposition 9.1; apply [6 Theorem 3.1] for equations and inequations, including recognizable constraints.
In particular, the groups BS ( m , ± m ) \operatorname{BS}(m,\pm m) BS ( m , ± m )
Theorem 8.3. The Diophantine problem is undecidable in the one-relator group
B d = ⟨ a , t ∣ ( t a t − 1 ) a ( t a t − 1 ) − 1 = a d B_d=\langle a,t\mid(tat^{-1})a(tat^{-1})^{-1}=a^d B d = ⟨ a , t ∣ ( t a t − 1 ) a ( t a t − 1 ) − 1 = a d for every integer d ≥ 2 d\ge2 d ≥ 2
For prime d d d [21 Theorem 1.1] ; Nyberg-Brodda [45 Theorem A] gives all d ≥ 2 d\ge2 d ≥ 2 B d B_d B d BS ( 1 , d ) \operatorname{BS}(1,d) BS ( 1 , d ) Lemma 3.2 , taking u = a u=a u = a v = t a t − 1 v=tat^{-1} v = t a t − 1 Corollary 5.8 also gives undecidability of Th ( B d ) \operatorname{Th}(B_d) Th ( B d )
This does not settle arbitrary systems of equations in BS ( 1 , n ) \operatorname{BS}(1,n) BS ( 1 , n ) [41 ] , concern a restricted class of equations. Likewise, undecidability of a full elementary theory does not imply undecidability of its positive existential fragment.
Proposition 8.4. There is an unconditional algorithm deciding whether an arbitrary one-relator group is fully residually free.
Proof. A finitely generated group is fully residually free if every finite set of nonidentity elements survives simultaneously under some homomorphism to a free group; these are the limit groups. Bumagin- Kharlampovich - Miasnikov [3 ] and Groves–Wilton [22 ] gives a recognition algorithm from a finite presentation and a solution to its word problem. Magnus supplies the latter uniformly for one-relator groups.
Theorem 8.5. For m ≥ 1 m\ge1 m ≥ 1
K m = ⟨ a , t ∣ [ t , a ( a − 1 t − 1 a t ) − m ] = 1 ⟩ K_m=\langle a,t\mid[t,a(a^{-1}t^{-1}at)^{-m}]=1\rangle K m = ⟨ a , t ∣ [ t , a ( a − 1 t − 1 a t ) − m ] = 1 ⟩ has a retract isomorphic to BS ( m , m + 1 ) \operatorname{BS}(m,m+1) BS ( m , m + 1 ) K 2 K_2 K 2 K 1 K_1 K 1
This is [57 Theorem 1.3] . In particular, a one-relator group with a commutator relator need not be Hopfian, residually finite, or automatic. Since K 1 K_1 K 1 BS ( 1 , 2 ) \operatorname{BS}(1,2) BS ( 1 , 2 ) Corollary 5.8 applies to K 1 K_1 K 1 m ≥ 2 m\ge2 m ≥ 2 Corollary 6.13 and Corollary 7.9 also imply that Th ( K m ) \operatorname{Th}(K_m) Th ( K m ) K m K_m K m [17 ] give further nonautomatic one-relator groups containing no BS ( m , n ) \operatorname{BS}(m,n) BS ( m , n ) m ≠ ± n m\ne\pm n m = ± n
Unimodular Baumslag–Solitar groups
By changing the sign of both parameters, every Baumslag–Solitar group with ∣ m ∣ = ∣ n ∣ = k > 1 \lvert m\rvert=\lvert n\rvert=k>1 ∣ m ∣ = ∣ n ∣ = k > 1 BS ( k , k ) \operatorname{BS}(k,k) BS ( k , k ) BS ( k , − k ) \operatorname{BS}(k,-k) BS ( k , − k ) F r F_r F r r r r
Proposition 9.1. For k > 1 k>1 k > 1
In G + = BS ( k , k ) G_+=\operatorname{BS}(k,k) G + = BS ( k , k )
G + ⟶ C k , a ⟼ 1 ‾ , t ⟼ 0 ‾ G_+\longrightarrow C_k,\qquad a\longmapsto\overline{1},\quad t\longmapsto\overline{0} G + ⟶ C k , a ⟼ 1 , t ⟼ 0 has index k k k F k × Z F_k\times\mathbb{Z} F k × Z
In G − = BS ( k , − k ) G_{-}=\operatorname{BS}(k,-k) G − = BS ( k , − k )
G − ⟶ C k × C 2 , a ⟼ ( 1 ‾ , 0 ‾ ) , t ⟼ ( 0 ‾ , 1 ‾ ) G_{-}\longrightarrow C_k\times C_2,\qquad a\longmapsto(\overline{1},\overline{0}),\qquad t\longmapsto(\overline{0},\overline{1}) G − ⟶ C k × C 2 , a ⟼ ( 1 , 0 ) , t ⟼ ( 0 , 1 ) has index 2 k 2k 2 k F 2 k − 1 × Z F_{2k-1}\times\mathbb{Z} F 2 k − 1 × Z
Proof. For the first assertion, put
z = a k , x i = a i t a − i ( 0 ≤ i < k ) . z=a^k,\qquad x_i=a^ita^{-i}\quad(0\leq i<k). z = a k , x i = a i t a − i ( 0 ≤ i < k ) . Reidemeister–Schreier rewriting, with representatives 1 , a , … , a k − 1 1,a,\ldots,a^{k-1} 1 , a , … , a k − 1
H + = ⟨ z , x 0 , … , x k − 1 ∣ [ z , x i ] = 1 ( 0 ≤ i < k ) ⟩ . H_{+}=\langle z,x_0,\ldots,x_{k-1}\mid[z,x_i]=1\ (0\leq i<k)\rangle. H + = ⟨ z , x 0 , … , x k − 1 ∣ [ z , x i ] = 1 ( 0 ≤ i < k )⟩ . Thus H + = F ( x 0 , … , x k − 1 ) × ⟨ z ⟩ H_{+}=F(x_0,\ldots,x_{k-1})\times\langle z\rangle H + = F ( x 0 , … , x k − 1 ) × ⟨ z ⟩ C k C_k C k
For the second assertion, let A = ⟨ a k ⟩ A=\langle a^k\rangle A = ⟨ a k ⟩ G − G_{-} G − a a a t t t
G − / A ≅ C k ∗ Z . G_{-}/A\cong C_k\ast\mathbb{Z}. G − / A ≅ C k ∗ Z . Let H − H_{-} H − H ‾ − \overline{H}_{-} H − H ‾ − \overline{H}_{-} H − C k ∗ Z → C k × C 2 C_k\ast\mathbb{Z}\to C_k\times C_2 C k ∗ Z → C k × C 2
View C k ∗ Z C_k\ast\mathbb{Z} C k ∗ Z C k C_k C k C k C_k C k H ‾ − \overline{H}_{-} H − 2 k / k = 2 2k/k=2 2 k / k = 2 2 k 2k 2 k H ‾ − ≅ F 2 k − 1 \overline{H}_{-}\cong F_{2k-1} H − ≅ F 2 k − 1
Every element of H − H_{-} H − t t t A A A
1 ⟶ A ⟶ H − ⟶ F 2 k − 1 ⟶ 1 1\longrightarrow A\longrightarrow H_{-}\longrightarrow F_{2k-1}\longrightarrow1 1 ⟶ A ⟶ H − ⟶ F 2 k − 1 ⟶ 1 is therefore central and splits: choose lifts of a free basis of the quotient. Their generated subgroup maps isomorphically onto the free quotient and meets A A A H − = F 2 k − 1 × A H_{-}=F_{2k-1}\times A H − = F 2 k − 1 × A
Example 9.2. The group BS ( 2 , 2 ) \operatorname{BS}(2,2) BS ( 2 , 2 )
⟨ t , a t a − 1 , a 2 ⟩ = F ( t , a t a − 1 ) × ⟨ a 2 ⟩ . \langle t,ata^{-1},a^2\rangle=F(t,ata^{-1})\times\langle a^2\rangle. ⟨ t , a t a − 1 , a 2 ⟩ = F ( t , a t a − 1 ) × ⟨ a 2 ⟩ . The group BS ( 2 , − 2 ) \operatorname{BS}(2,-2) BS ( 2 , − 2 ) F 3 × Z F_3\times\mathbb{Z} F 3 × Z
The elementary theories of the direct products
We record the effective separation of formulas which will also be used for the periodic action. It is the finite-product instance of the Feferman–Vaught method [15 ] .
Lemma 9.3. Let A , B A,B A , B
⋁ ν = 1 N ( α ν ( x ˉ ) ∧ β ν ( y ˉ ) ) . \bigvee_{\nu=1}^{N}\left(\alpha_{\nu}(\bar{x})\wedge\beta_{\nu}(\bar{y})\right). ν = 1 ⋁ N ( α ν ( x ˉ ) ∧ β ν ( y ˉ ) ) . where α ν \alpha_{\nu} α ν A A A β ν \beta_{\nu} β ν B B B
Proof. Atomic formulas belong to one sort. Finite disjunctions of separated conjunctions are closed effectively under Boolean operations, by distributivity and disjunctive normal form. For an A \mathcal{A} A x x x
⋁ ν ( α ν ∧ β ν ) ⟷ ⋁ ν ( ( ∃ x α ν ) ∧ β ν ) , \bigvee_{\nu}\left(\alpha_{\nu}\land\beta_{\nu}\right)\ \longleftrightarrow\ \bigvee_{\nu}\left((\exists x\ \alpha_{\nu})\land\beta_{\nu}\right), ν ⋁ ( α ν ∧ β ν ) ⟷ ν ⋁ ( ( ∃ x α ν ) ∧ β ν ) , because x x x β ν \beta_{\nu} β ν α ν , β ν \alpha_{\nu},\beta_{\nu} α ν , β ν
Corollary 9.4. For every fixed r ≥ 1 r\geq1 r ≥ 1 F r × Z F_r\times\mathbb{Z} F r × Z
Proof. The theories of F r F_r F r ( Z , + ) (\mathbb{Z},+) ( Z , + ) [27 ] and Presburger arithmetic; the rank-one case is also additive arithmetic. Interpret the product on pairs with coordinatewise multiplication and inverse. Each atomic equality becomes a conjunction of one equality in each sort. Apply Lemma 9.3 .
The periodic action and the full theory
Proposition 9.5. Let F k = F ( x 0 , … , x k − 1 ) F_k=F(x_0,\ldots,x_{k-1}) F k = F ( x 0 , … , x k − 1 ) σ ∈ Aut ( F k ) \sigma\in\operatorname{Aut}(F_k) σ ∈ Aut ( F k ) σ ( x i ) = x i + 1 ( m o d k ) \sigma(x_i)=x_{i+1\pmod{k}} σ ( x i ) = x i + 1 ( mod k )
BS ( k , k ) ≅ F k ⋊ σ Z , \operatorname{BS}(k,k)\cong F_k\rtimes_{\sigma}\mathbb{Z}, BS ( k , k ) ≅ F k ⋊ σ Z , where the generator of Z \mathbb{Z} Z a a a x i x_i x i a i t a − i a^ita^{-i} a i t a − i
Proof. The semidirect product has presentation
⟨ a , x 0 , … , x k − 1 ∣ a x i a − 1 = x i + 1 ( m o d k ) ( 0 ≤ i < k ) ⟩ . \langle a,x_0,\ldots,x_{k-1}\mid ax_ia^{-1}=x_{i+1\pmod{k}}\ (0\leq i<k)\rangle. ⟨ a , x 0 , … , x k − 1 ∣ a x i a − 1 = x i + 1 ( mod k ) ( 0 ≤ i < k )⟩ . Eliminating x 1 , … , x k − 1 x_1,\ldots,x_{k-1} x 1 , … , x k − 1 ⟨ a , x 0 ∣ a k x 0 a − k = x 0 ⟩ \langle a,x_0\mid a^kx_0a^{-k}=x_0\rangle ⟨ a , x 0 ∣ a k x 0 a − k = x 0 ⟩ x 0 = t x_0=t x 0 = t BS ( k , k ) \operatorname{BS}(k,k) BS ( k , k )
Proposition 9.6. If Th ( F k , ⋅ , − 1 , 1 , σ ) \operatorname{Th}(F_k,\cdot,{}^{-1},1,\sigma) Th ( F k , ⋅ , − 1 , 1 , σ ) Th ( BS ( k , k ) ) \operatorname{Th}(\operatorname{BS}(k,k)) Th ( BS ( k , k )) ( F k , σ ) (F_k,\sigma) ( F k , σ ) ( Z , + , 0 , 1 ) (\mathbb{Z},+,0,1) ( Z , + , 0 , 1 )
Proof. Every element has a unique expression w a k h + r wa^{kh+r} w a k h + r w ∈ F k w\in F_k w ∈ F k h ∈ Z h\in\mathbb{Z} h ∈ Z 0 ≤ r < k 0\leq r<k 0 ≤ r < k ( w , h , r ) (w,h,r) ( w , h , r ) σ k = 1 \sigma^k=1 σ k = 1
( w , h , r ) ( v , j , s ) = ( w σ r ( v ) , h + j + ⌊ r + s k ⌋ , ( r + s ) mod k ) . (21) (w,h,r)(v,j,s)=\left(w\sigma^r(v),h+j+\left\lfloor\frac{r+s}{k}\right\rfloor,(r+s)\mathbin{\operatorname{mod}} k\right). \tag*{(21)} ( w , h , r ) ( v , j , s ) = ( w σ r ( v ) , h + j + ⌊ k r + s ⌋ , ( r + s ) mod k ) . (21) Inversion is
( w , h , r ) − 1 = { ( w − 1 , − h , 0 ) , r = 0 , ( σ − r ( w − 1 ) , − h − 1 , k − r ) , r > 0. (22) (w,h,r)^{-1}=
\begin{cases}
(w^{-1},-h,0), & r=0,\\
(\sigma^{-r}(w^{-1}),-h-1,k-r), & r>0.
\end{cases} \tag*{(22)} ( w , h , r ) − 1 = { ( w − 1 , − h , 0 ) , ( σ − r ( w − 1 ) , − h − 1 , k − r ) , r = 0 , r > 0. (22) For fixed residue coordinates, every group term has a free-group coordinate which is a term in the language with σ \sigma σ
∃ g φ ( g ) ⟷ ⋁ r = 0 k − 1 ∃ w ∃ h φ ^ ( w , h , r ) . \exists g\ \varphi(g) \longleftrightarrow\bigvee_{r=0}^{k-1} \exists w\ \exists h\ \widehat{\varphi}(w,h,r). ∃ g φ ( g ) ⟷ r = 0 ⋁ k − 1 ∃ w ∃ h φ ( w , h , r ) . Universal quantifiers are treated by conjunction over the residues and universal quantification over the two infinite coordinates. Apply Lemma 9.3 . Presburger arithmetic decides the integer sentences, and the assumed algorithm decides the free-group sentences. Thus the procedure terminates on every input sentence.
Remark 9.7. Proposition 9.6 is conditional. Decidability of the pure free-group theory does not supply a decision procedure for its expansion by σ \sigma σ w w w σ ( w ) \sigma(w) σ ( w ) … \ldots … σ k − 1 ( w ) \sigma^{k-1}(w) σ k − 1 ( w ) σ \sigma σ
∃ w ( w ≠ 1 ∧ σ ( w ) = w ) \exists w\ (w \ne1 \land\sigma(w)=w) ∃ w ( w = 1 ∧ σ ( w ) = w ) is false, whereas independent orbit coordinates would permit a nonidentity solution to the corresponding equality.
There is a second formulation of the sufficient condition. Put
V k = F k ⋊ σ C k ≅ C k ∗ Z . V_k = F_k \rtimes_{\sigma} C_k \cong C_k * \mathbb{Z}. V k = F k ⋊ σ C k ≅ C k ∗ Z . where the generator c c c C k C_k C k x i x_i x i x i + 1 x_{i+1} x i + 1 k k k x i x_i x i i > 0 i>0 i > 0 ⟨ c , x 0 ∣ c k = 1 ⟩ \langle c,x_0 \mid c^k=1\rangle ⟨ c , x 0 ∣ c k = 1 ⟩
ρ : V k ⟶ C k , ρ ( c ) = c , ρ ( x 0 ) = 1. \rho: V_k \longrightarrow C_k,\qquad\rho(c)=c,\quad\rho(x_0)=1. ρ : V k ⟶ C k , ρ ( c ) = c , ρ ( x 0 ) = 1. Then ker ρ = F k \ker\rho=F_k ker ρ = F k σ \sigma σ c c c Th ( V k , ker ρ , c ) \operatorname{Th}(V_k,\ker\rho,c) Th ( V k , ker ρ , c ) Th ( F k , σ ) \operatorname{Th}(F_k,\sigma) Th ( F k , σ ) Th ( B S ( k , k ) ) \operatorname{Th}(\mathrm{BS}(k,k)) Th ( BS ( k , k )) ker ρ \ker\rho ker ρ
The analysis of free groups expanded by finite-quotient predicates in [13 ] supplies related Makanin–Razborov diagrams, towers and formal-solution results. Those results on positive theory do not give the full decision theorem required in Proposition 9.6. For B S ( k , − k ) \mathrm{BS}(k,-k) BS ( k , − k )
Effective virtual free-by-cyclic presentations
Assuming the virtual compact specialness result stated as Theorem 1.1 in [47 ] , we construct a virtual free-by-cyclic presentation for a hyperbolic one-relator group. We compute a finite-index normal subgroup, an embedding in a mapping torus of a finite-rank free-group automorphism, and a finite HNN presentation. The free kernel may have infinite rank.
Virtual free-by-cyclic subgroups
Definition 10.1. A group H H H free-by-cyclic if there is an exact sequence
1 ⟶ K ⟶ H ⟶ C ⟶ 1 , 1 \longrightarrow K \longrightarrow H \longrightarrow C \longrightarrow1, 1 ⟶ K ⟶ H ⟶ C ⟶ 1 , where K K K C ≤ Z C \le\mathbb{Z} C ≤ Z K K K C C C virtually free-by-cyclic if it has a finite-index subgroup with this property.
If C ≠ 0 C \ne0 C = 0 C C C Z \mathbb{Z} Z s s s 1 1 1 H = K ⋊ β ⟨ s ⟩ H = K \rtimes_{\beta} \langle s \rangle H = K ⋊ β ⟨ s ⟩ β ( k ) = s k s − 1 \beta(k) = sks^{-1} β ( k ) = s k s − 1
E α = F d ⋊ α ⟨ t ⟩ = ⟨ a 1 , … , a d , t ∣ t a i t − 1 = α ( a i ) , 1 ≤ i ≤ d ⟩ . (23) E_{\alpha} = F_d \rtimes_{\alpha} \langle t \rangle= \langle a_1,\ldots,a_d,t \mid ta_i t^{-1} = \alpha(a_i),\ 1 \le i \le d \rangle. \tag*{(23)} E α = F d ⋊ α ⟨ t ⟩ = ⟨ a 1 , … , a d , t ∣ t a i t − 1 = α ( a i ) , 1 ≤ i ≤ d ⟩ . (23) Thus elements of E α E_{\alpha} E α w t n wt^n w t n w ∈ F d w \in F_d w ∈ F d π : E α → Z \pi: E_{\alpha} \to\mathbb{Z} π : E α → Z π ( w t n ) = n \pi(wt^n) = n π ( w t n ) = n
The result stated as Theorem 1.1 in [47 ] asserts that every hyperbolic one-relator group is virtually compact special. Corollary 18.1 of that paper then gives a finite-index subgroup embedded in a group of the form (23) . The group F d F_d F d F d F_d F d
Theorem 10.2. Assume the result stated as Theorem 1.1 in [47 ] . There is a uniform algorithm which, given a finite one-relator presentation
G = ⟨ X ∣ r ⟩ G = \langle X \mid r \rangle G = ⟨ X ∣ r ⟩ of a hyperbolic group, computes the following data:
(i) a finite-index normal subgroup H ⊴ G H \trianglelefteq G H ⊴ G H H H H H H X X X H H H
(ii) an integer d ≥ 0 d \ge0 d ≥ 0 α ∈ Aut ( F d ) \alpha\in\operatorname{Aut}(F_d) α ∈ Aut ( F d ) ι : H ↪ E α \iota: H \hookrightarrow E_{\alpha} ι : H ↪ E α H H H
(iii) a homomorphism χ : H → C \chi: H \to C χ : H → C C = 0 C = 0 C = 0 C = Z C = \mathbb{Z} C = Z K K K C = Z C = \mathbb{Z} C = Z s s s χ ( s ) = 1 \chi(s) = 1 χ ( s ) = 1
(iv) if C = 0 C = 0 C = 0 H H H C = Z C = \mathbb{Z} C = Z H H H K K K s s s s − 1 s^{-1} s − 1
An effective basis in (iv) means a basis indexed by a decidable set, with a computable word for each basis element. The set may be infinite. The images under conjugation are computed as finite words in the basis.
To prove termination, we shall use the following quasiconvex embedding theorem.
Lemma 10.3. Let G G G G G G G G G E α E_{\alpha} E α (23) .
Proof. Theorem 1.1 of Kielak–Linton [31 ] gives cd Q ( G ) ≤ 2 \operatorname{cd}_{\mathbb{Q}}(G) \le2 cd Q ( G ) ≤ 2 b 2 ( 2 ) ( G ) = 0 b_2^{(2)}(G) = 0 b 2 ( 2 ) ( G ) = 0 cd Q ( G ) ≤ 1 \operatorname{cd}_{\mathbb{Q}}(G) \le1 cd Q ( G ) ≤ 1 L ≤ G L \le G L ≤ G Z \mathbb{Z} Z (23) . The normal core of L L L G G G L L L
For a hyperbolic one-relator group, the virtual compact specialness result stated in [47 ] , together with [31 ] , Corollary 1.3, gives the hypotheses of Lemma 10.3 . This also applies to trivial and proper-power relators. If G G G
Construction of an embedding
From a finite presentation of a hyperbolic group one can compute a hyperbolicity constant, a solution of the word problem, and a shortlex automatic structure; see [29 Section 2.4] . The procedure detecting hyperbolicity terminates precisely on hyperbolic presentations.
Lemma 10.4. There is a uniform partial algorithm which, given a finite presentation of a hyperbolic group E E E y 1 , … , y k y_1,\ldots,y_k y 1 , … , y k Q = ⟨ y 1 , … , y k ⟩ Q=\langle y_1,\ldots,y_k\rangle Q = ⟨ y 1 , … , y k ⟩ Q Q Q
Q = ⟨ y 1 , … , y k ∣ S ⟩ Q=\langle y_1,\ldots,y_k\mid S\rangle Q = ⟨ y 1 , … , y k ∣ S ⟩ with the indicated identification of generators.
Proof. Kapovich’s algorithm [25 ] detects quasiconvexity. Alternatively, [29 Theorem 4.1 and Corollary 4.2] compute the Stallings graph and a quasiconvexity constant. These data solve membership in Q Q Q
They also give an effective quasi-isometric embedding of the Cayley graph of Q Q Q E E E Q Q Q S S S E E E
Lemma 10.5. Suppose H = ⟨ h 1 , … , h k ∣ R ⟩ H=\langle h_1,\ldots,h_k\mid R\rangle H = ⟨ h 1 , … , h k ∣ R ⟩ E E E ⟨ y 1 , … , y k ∣ S ⟩ \langle y_1,\ldots,y_k\mid S\rangle ⟨ y 1 , … , y k ∣ S ⟩ Q = ⟨ y 1 , … , y k ⟩ ≤ E Q=\langle y_1,\ldots,y_k\rangle\le E Q = ⟨ y 1 , … , y k ⟩ ≤ E h i ↦ y i h_i\mapsto y_i h i ↦ y i H → Q H\to Q H → Q
R ( y 1 , … , y k ) = 1 in E , S ( h 1 , … , h k ) = 1 in H . (24) R(y_1,\ldots,y_k)=1\text{ in }E,\qquad S(h_1,\ldots,h_k)=1\text{ in }H. \tag*{(24)} R ( y 1 , … , y k ) = 1 in E , S ( h 1 , … , h k ) = 1 in H . (24) Both conditions are decidable.
Proof. The first condition defines a homomorphism H → Q H\to Q H → Q Q → H Q\to H Q → H
Proposition 10.6. There is a uniform algorithm on finite presentations of hyperbolic groups satisfying the conclusion of Lemma 10.3 which computes the data in Theorem 10.2 (i)–(ii). In the second case of that lemma the ambient group can be chosen hyperbolic and the image quasiconvex. In the virtually free case the construction may give H = F d ↪ F d × Z H=F_d\hookrightarrow F_d\times\mathbb{Z} H = F d ↪ F d × Z
Proof. First compute a word-problem algorithm for G G G n n n G G G Sym ( n ) \operatorname{Sym}(n) Sym ( n ) ρ \rho ρ
H ρ = ker ρ = ⟨ h 1 , … , h k ∣ R ρ ⟩ H_\rho=\ker\rho=\langle h_1,\ldots,h_k\mid R_\rho\rangle H ρ = ker ρ = ⟨ h 1 , … , h k ∣ R ρ ⟩ and words for the h i h_i h i G G G ρ \rho ρ h i h_i h i G G G
Run the following two searches in parallel.
In the first, enumerate finite sequences of Tietze transformations starting from each presentation of H ρ H_\rho H ρ H ρ H_{\rho} H ρ F d F_d F d F d × Z F_d \times\mathbb{Z} F d × Z Z \mathbb{Z} Z H ρ = 1 H_{\rho}=1 H ρ = 1
In the second, enumerate all ranks d d d F d F_d F d Aut ( F d ) \operatorname{Aut}(F_d) Aut ( F d ) E α E_{\alpha} E α (23) and run hyperbolicity recognition on each such presentation. Whenever hyperbolicity has been established for E α E_{\alpha} E α H ρ H_{\rho} H ρ y 1 , … , y k ∈ E α y_1,\ldots,y_k \in E_{\alpha} y 1 , … , y k ∈ E α
Check R ρ ( y 1 , … , y k ) = 1 R_{\rho}(y_1,\ldots,y_k)=1 R ρ ( y 1 , … , y k ) = 1 Lemma 10.4 . When it produces a presentation with relators S S S S ( h 1 , … , h k ) = 1 S(h_1,\ldots,h_k)=1 S ( h 1 , … , h k ) = 1 G G G Lemma 10.5 .
Interleave both searches and their subsidiary computations so that each computation is eventually carried out for arbitrarily many steps.
If G G G Lemma 10.3 supplies a finite-index normal H ρ H_{\rho} H ρ E α E_{\alpha} E α
The first test in (24) defines a homomorphism to E α E_{\alpha} E α
A finite HNN presentation
Identify the subgroup constructed in Proposition 10.6 with its image H ≤ E α H \leq E_{\alpha} H ≤ E α n i = π ( h i ) n_i=\pi(h_i) n i = π ( h i ) n i n_i n i H ≤ F d H \leq F_d H ≤ F d H H H C = 0 C=0 C = 0 K = H K=H K = H
Otherwise let
q = gcd ( n 1 , … , n k ) > 0 , χ = 1 q π ∣ H : H ↠ Z . q=\gcd(n_1,\ldots,n_k)>0,\qquad\chi=\frac{1}{q}\pi|_H:H\twoheadrightarrow\mathbb{Z}. q = g cd( n 1 , … , n k ) > 0 , χ = q 1 π ∣ H : H ↠ Z . Bézout coefficients give a word s s s h i h_i h i π ( s ) = q \pi(s)=q π ( s ) = q e i = χ ( h i ) e_i=\chi(h_i) e i = χ ( h i ) z i = h i s − e i z_i=h_i s^{-e_i} z i = h i s − e i
H = ⟨ s , z 1 , … , z k ⟩ , K = ker χ = H ∩ F d . H=\langle s,z_1,\ldots,z_k\rangle,\qquad K=\ker\chi=H\cap F_d. H = ⟨ s , z 1 , … , z k ⟩ , K = ker χ = H ∩ F d . The subgroup theorem for free groups proves that K K K
Write s = c t q s=ct^q s = c t q s s s
β : F d ⟶ F d , β ( w ) = c α q ( w ) c − 1 . (25) \beta:F_d\longrightarrow F_d,\qquad\beta(w)=c\alpha^q(w)c^{-1}. \tag*{(25)} β : F d ⟶ F d , β ( w ) = c α q ( w ) c − 1 . (25) Its restriction preserves K K K H = K ⋊ β ⟨ s ⟩ H=K\rtimes_{\beta}\langle s\rangle H = K ⋊ β ⟨ s ⟩
Proposition 10.7. From the preceding data one can compute free groups A , D ≤ B ≤ K A,D\leq B\leq K A , D ≤ B ≤ K θ : A → D \theta:A\to D θ : A → D
H ≅ ⟨ b 1 , … , b ℓ , s | s U j ( b ) s − 1 = V j ( b ) , 1 ≤ j ≤ p ⟩ . (26) H\cong\left\langle b_1,\ldots,b_{\ell},s\ \middle|\ sU_j(b)s^{-1}=V_j(b),\ 1\leq j\leq p\right\rangle. \tag*{(26)} H ≅ ⟨ b 1 , … , b ℓ , s s U j ( b ) s − 1 = V j ( b ) , 1 ≤ j ≤ p ⟩ . (26) where the b i b_i b i B B B U j U_j U j A A A V j = θ ( U j ) V_j=\theta(U_j) V j = θ ( U j ) H H H χ \chi χ
Proof. Adjoin the generator s s s h i h_i h i z i s e i z_i s^{e_i} z i s e i
P = ⟨ s , z 1 , … , z k ∣ R ′ ⟩ P=\langle s,z_1,\ldots,z_k\mid R'\rangle P = ⟨ s , z 1 , … , z k ∣ R ′ ⟩ in which each relator has exponent sum zero in s s s N ≥ 1 N\geq1 N ≥ 1 s s s R ′ R' R ′ − N ≤ j ≤ N -N\leq j\leq N − N ≤ j ≤ N
z i , j = β j ( z i ) = s j z i s − j ∈ F d . z_{i,j}=\beta^j(z_i)=s^jz_i s^{-j}\in F_d. z i , j = β j ( z i ) = s j z i s − j ∈ F d . Define
B = ⟨ z i , j : 1 ≤ i ≤ k , − N ≤ j ≤ N ⟩ , B=\langle z_{i,j}:1\leq i\leq k,\ -N\leq j\leq N\rangle, B = ⟨ z i , j : 1 ≤ i ≤ k , − N ≤ j ≤ N ⟩ , A = ⟨ z i , j : 1 ≤ i ≤ k , − N ≤ j < N ⟩ , A=\langle z_{i,j}:1\leq i\leq k,\ -N\leq j<N\rangle, A = ⟨ z i , j : 1 ≤ i ≤ k , − N ≤ j < N ⟩ , D = ⟨ z i , j : 1 ≤ i ≤ k , − N < j ≤ N ⟩ . D=\langle z_{i,j}:1\leq i\leq k,\ -N<j\leq N\rangle. D = ⟨ z i , j : 1 ≤ i ≤ k , − N < j ≤ N ⟩ . Then β ( A ) = D \beta(A)=D β ( A ) = D F d F_d F d [54 ] computes their free bases and rewrites the basis elements of A A A β \beta β U j , V j U_j,V_j U j , V j B B B b i b_i b i z i , j z_{i,j} z i , j
Let P P P (26) . It is the HNN extension of B B B A , D A,D A , D β ∣ A \left.\beta\right|_A β ∣ A B ≤ H B\leq H B ≤ H s ∈ H s\in H s ∈ H P → H P\to H P → H s s s z i , 0 z_{i,0} z i , 0
In P P P
s z i , j s − 1 = z i , j + 1 ( − N ≤ j < N ) . sz_{i,j}s^{-1}=z_{i,j+1}\qquad(-N\leq j<N). s z i , j s − 1 = z i , j + 1 ( − N ≤ j < N ) . It follows, for positive and negative j j j z i , j = s j z i , 0 s − j z_{i,j}=s^jz_{i,0}s^{-j} z i , j = s j z i , 0 s − j P P P R ′ R' R ′ s s s N N N z i , j z_{i,j} z i , j B ≤ F d B\leq F_d B ≤ F d H H H P P P s ↦ s s\mapsto s s ↦ s z i ↦ z i , 0 z_i\mapsto z_{i,0} z i ↦ z i , 0 H → P H\to P H → P
The two maps fix s s s z i , 0 z_{i,0} z i , 0 z i , j z_{i,j} z i , j b i b_i b i B B B s s s 1 1 1 B B B 0 0 0 χ \chi χ
The free kernel and its automorphism
Proposition 10.9. If H ≤ E α H\leq E_\alpha H ≤ E α π ( H ) ≠ 0 \pi(H)\ne0 π ( H ) = 0 B B B K = H ∩ F d K=H\cap F_d K = H ∩ F d k ∈ K k\in K k ∈ K k k k B B B β \beta β β − 1 \beta^{-1} β − 1 B B B
Proof. Lemma 10.4 gives a membership algorithm for H H H E α E_\alpha E α w ∈ F d w\in F_d w ∈ F d K K K H H H
Consider the right-coset Schreier graph of K K K F d F_d F d a 1 , … , a d a_1,\ldots,a_d a 1 , … , a d K w Kw K w a i a_i a i K w Kw K w K w a i Kwa_i K w a i
K w = K v ⟺ w v − 1 ∈ K . Kw=Kv\quad\Longleftrightarrow\quad wv^{-1}\in K. K w = K v ⟺ w v − 1 ∈ K . Represent each vertex by the shortest, and then lexicographically least, reduced word in its coset. The representative of a given coset is computable by a finite search: its length is at most that of the given word. These representatives form a prefix-closed transversal, and determine a computable spanning tree rooted at K K K
For every unoriented edge outside this tree, choose its orientation labelled by a positive basis letter. If the edge goes from K u Ku K u K v Kv K v a i a_i a i u u u v v v
c e = u a i v − 1 ∈ K . c_e=ua_iv^{-1}\in K. c e = u a i v − 1 ∈ K . The Schreier basis theorem identifies B = { c e : e is outside the spanning tree } \mathcal{B}=\{c_e:e\text{ is outside the spanning tree}\} B = { c e : e is outside the spanning tree } K K K B \mathcal{B} B
A word representing an element of K K K B \mathcal{B} B β ( c e ) \beta(c_e) β ( c e ) β − 1 ( c e ) \beta^{-1}(c_e) β − 1 ( c e ) F d F_d F d K K K s s s K K K B \mathcal{B} B
We obtain the effective presentation
H = ⟨ s , c e ( e ∈ J ) | s c e s − 1 = W e ( B ) ( e ∈ J ) ⟩ , (27) H=\left\langle s,c_e\ (e\in J)\mathrel{}\middle|\mathrel{} sc_es^{-1}=W_e(\mathcal{B})\ (e\in J)\right\rangle, \tag*{(27)} H = ⟨ s , c e ( e ∈ J ) s c e s − 1 = W e ( B ) ( e ∈ J ) ⟩ , (27) where J J J W e W_e W e e e e (26) and (27) to the original finite-index subgroup are explicit.
Proof of Theorem 10.2 . The assumed virtual compact specialness result and [31 Corollary 1.3] give the hypotheses of Lemma 10.3 . Proposition 10.6 therefore constructs (i)–(ii). If the first search succeeds, use the embedding H = F d ≤ F d × Z H=F_d\leq F_d\times\mathbb{Z} H = F d ≤ F d × Z C = 0 C=0 C = 0 π \pi π H H H F d F_d F d Propositions 10.7 and 10.9 . These constructions give all the remaining data.
Finite-rank kernels
If a finite-index subgroup with finite-rank free kernel is known to exist, it can be found directly by the following procedure.
Proposition 10.10. There is a uniform partial algorithm on finite presentations which terminates whenever the input group has a finite-index subgroup isomorphic to F e ⋊ γ Z F_e\rtimes_\gamma\mathbb{Z} F e ⋊ γ Z e < ∞ e<\infty e < ∞
Proof. Enumerate the kernels of all finite permutation representations and their Reidemeister–Schreier presentations. Enumerate all ranks e e e γ ∈ Aut ( F e ) \gamma\in\operatorname{Aut}(F_e) γ ∈ Aut ( F e ) (23) . Search for finite Tietze sequences joining the subgroup presentations to these mapping-torus presentations, interleaving all searches.
It suffices to enumerate normal subgroups. Suppose L ≤ G L\leq G L ≤ G L = F e ⋊ Z L=F_e\rtimes\mathbb{Z} L = F e ⋊ Z H H H G G G H ∩ F e H\cap F_e H ∩ F e F e F_e F e H H H Z \mathbb{Z} Z H H H Z \mathbb{Z} Z
Corollary 10.11. Assume the result stated as Corollary 4.10 in [47 ] . Let F F F φ : F → F \varphi: F \to F φ : F → F Z \mathbb{Z} Z
Proof. By the cited result, the ascending HNN extension has a finite-index subgroup with finite-rank free kernel. Apply Proposition 10.10 to its finite presentation.
The character obtained in this corollary need not be the restriction of the original ascending HNN height.
Example 10.12. The finite-rank conclusion cannot hold for every hyperbolic one-relator group. Let G G G g ≥ 2 g \ge2 g ≥ 2 H ≤ G H \le G H ≤ G
χ ( H ) = [ G : H ] ( 2 − 2 g ) < 0. \chi(H) = [G : H](2 - 2g) < 0. χ ( H ) = [ G : H ] ( 2 − 2 g ) < 0. A finite-rank free-by-Z \mathbb{Z} Z Z \mathbb{Z} Z Theorem 10.2 cannot in general be required to have finite rank.
Remark 10.13. Termination follows from the existence theorems, without an a priori bound on the finite index, the ambient rank, or the lengths of the generator images. The argument gives no bound on the running time. Proposition 10.10 is a semialgorithm; it does not decide whether an arbitrary finitely presented group is virtually finite-rank free-by-Z \mathbb{Z} Z
Toral relative hyperbolicity of virtually free-by-cyclic groups
We prove that a finitely generated torsion-free virtually free-by-cyclic group is toral relatively hyperbolic if and only if it is CSA. As in § 10 , the free kernel may have infinite rank.
A group is toral relatively hyperbolic if it is torsion-free and hyperbolic relative to a finite family of finitely generated abelian subgroups. We allow the empty peripheral family and, for an abelian group, the family consisting of the group itself. The Klein bottle group is
K = ⟨ a , s ∣ s a s − 1 = a − 1 ⟩ . K = \langle a, s \mid sas^{-1} = a^{-1} \rangle. K = ⟨ a , s ∣ s a s − 1 = a − 1 ⟩ . Theorem 11.1. Let G G G
G G G
G G G
G G G F 2 × Z F_2 \times\mathbb{Z} F 2 × Z K K K
When G G G Z 2 \mathbb{Z}^2 Z 2
We first prove the assertion for finite-rank free kernels, then pass to arbitrary-rank kernels and finite extensions.
Finite-rank free kernels
Lemma 11.2. Let F r F_r F r J = F r ⋊ α ⟨ t ⟩ J = F_r \rtimes_\alpha\langle t\rangle J = F r ⋊ α ⟨ t ⟩ J J J F 2 × Z F_2 \times\mathbb{Z} F 2 × Z K K K J J J Z 2 \mathbb{Z}^2 Z 2
Proof. Suppose a polynomial subgroup for the outer class of α \alpha α [34 Lemma 1.5] , there are q ≥ 1 q \geq1 q ≥ 1 g ∈ F r g \in F_r g ∈ F r
β = Inn ( g ) ∘ α q , rank Fix ( β ) ≥ 2. \beta= \operatorname{Inn}(g) \circ\alpha^q, \qquad\operatorname{rank}\operatorname{Fix}(\beta) \geq2. β = Inn ( g ) ∘ α q , rank Fix ( β ) ≥ 2. Here Inn ( g ) ( x ) = g x g − 1 \operatorname{Inn}(g)(x) = gxg^{-1} Inn ( g ) ( x ) = g x g − 1 t x t − 1 = α ( x ) txt^{-1} = \alpha(x) t x t − 1 = α ( x ) x , y ∈ Fix ( β ) x,y \in\operatorname{Fix}(\beta) x , y ∈ Fix ( β ) s = g t q s = gt^q s = g t q s s s ⟨ x , y ⟩ ≅ F 2 \langle x,y\rangle\cong F_2 ⟨ x , y ⟩ ≅ F 2 J → Z J \to\mathbb{Z} J → Z ⟨ s ⟩ ∩ ⟨ x , y ⟩ = 1 \langle s\rangle\cap\langle x,y\rangle= 1 ⟨ s ⟩ ∩ ⟨ x , y ⟩ = 1
⟨ x , y , s ⟩ ≅ F 2 × Z , \langle x,y,s\rangle\cong F_2 \times\mathbb{Z}, ⟨ x , y , s ⟩ ≅ F 2 × Z , a contradiction. Thus every maximal polynomial subgroup is cyclic.
If r ≥ 2 r \geq2 r ≥ 2 α \alpha α F r F_r F r [11 Theorem 3.5] , makes J J J
Z ⋊ ε Z , ε ∈ { 1 , − 1 } . \mathbb{Z} \rtimes_\varepsilon\mathbb{Z}, \qquad\varepsilon\in\{1,-1\}. Z ⋊ ε Z , ε ∈ { 1 , − 1 } . It is Z 2 \mathbb{Z}^2 Z 2 K K K J J J
For r = 0 r = 0 r = 0 J ≅ Z J \cong\mathbb{Z} J ≅ Z r = 1 r = 1 r = 1 Z 2 \mathbb{Z}^2 Z 2 K K K
Free kernels of arbitrary rank
Lemma 11.3. Let H H H H H H F 2 × Z F_2 \times\mathbb{Z} F 2 × Z K K K H H H Z 2 \mathbb{Z}^2 Z 2
Proof. The assertion is immediate if H H H H = F ⋊ α Z H = F \rtimes_\alpha\mathbb{Z} H = F ⋊ α Z F F F [36 Theorem 1.1 and Remark 6.2] , H H H P \mathcal{P} P [36 Corollary 4.10] .
No P ∈ P P \in\mathcal{P} P ∈ P F 2 × Z F_2 \times\mathbb{Z} F 2 × Z K K K Lemma 11.2 , each P P P Z 2 \mathbb{Z}^2 Z 2 H H H P = { H } \mathcal{P} = \{H\} P = { H }
The transitivity assertion follows from finite relative presentations. Substitute presentations of the groups P ∈ P P \in\mathcal{P} P ∈ P H H H P \mathcal{P} P [11 Theorem 3.5] .
Passing to finite extensions
Lemma 11.4. A torsion-free virtually Z 2 \mathbb{Z}^2 Z 2 Z 2 \mathbb{Z}^2 Z 2
Proof. Let A ≅ Z 2 A \cong\mathbb{Z}^{2} A ≅ Z 2 Q Q Q ρ : Q → GL ( 2 , Z ) \rho: Q \to\operatorname{GL}(2,\mathbb{Z}) ρ : Q → GL ( 2 , Z ) g ≠ 1 g \ne1 g = 1 m ≥ 1 m \ge1 m ≥ 1 1 ≠ g m ∈ A 1 \ne g^{m} \in A 1 = g m ∈ A g m g^{m} g m g g g ρ ( g ) \rho(g) ρ ( g ) 1 1 1
A nonidentity finite-order matrix in GL ( 2 , Z ) \operatorname{GL}(2,\mathbb{Z}) GL ( 2 , Z ) 1 1 1 − 1 -1 − 1 ρ ( g ) \rho(g) ρ ( g ) 1 ≠ a ∈ A 1 \ne a \in A 1 = a ∈ A − 1 -1 − 1 g a g − 1 = a − 1 gag^{-1}=a^{-1} g a g − 1 = a − 1 ⟨ g ⟩ ∩ ⟨ a ⟩ = 1 \langle g\rangle\cap\langle a\rangle=1 ⟨ g ⟩ ∩ ⟨ a ⟩ = 1 g i = a j g^{i}=a^{j} g i = a j g g g a j = a − j a^{j}=a^{-j} a j = a − j j = i = 0 j=i=0 j = i = 0 ⟨ a , g ⟩ ≅ K \langle a,g\rangle\cong K ⟨ a , g ⟩ ≅ K ρ \rho ρ
Hence A ≤ Z ( Q ) A \le Z(Q) A ≤ Z ( Q ) Q / Z ( Q ) Q/Z(Q) Q / Z ( Q ) Q ′ Q' Q ′ Q ′ = 1 Q'=1 Q ′ = 1 Q Q Q A A A
Lemma 11.5. Suppose G G G H ≤ G H \le G H ≤ G H H H Z 2 \mathbb{Z}^{2} Z 2 G G G K K K G G G Z 2 \mathbb{Z}^{2} Z 2
Proof. Replace H H H H H H G G G H H H
In the remaining case let P 1 , … , P k P_{1},\ldots,P_{k} P 1 , … , P k H H H G G G H H H
Q i = N G ( P i ) . Q_i=N_G(P_i). Q i = N G ( P i ) . Since H H H N H ( P i ) = P i N_H(P_i)=P_i N H ( P i ) = P i Q i ∩ H = P i Q_i \cap H=P_i Q i ∩ H = P i [ Q i : P i ] < ∞ [Q_i:P_i]<\infty [ Q i : P i ] < ∞ G G G G G G Q i Q_i Q i
This follows from the asymptotically tree-graded characterization of relative hyperbolicity in [14 ] . The inclusion H ↪ G H \hookrightarrow G H ↪ G H H H Q i Q_i Q i P i P_i P i H H H G G G
Finally each Q i Q_i Q i Z 2 \mathbb{Z}^{2} Z 2 Q i ≅ Z 2 Q_i \cong\mathbb{Z}^{2} Q i ≅ Z 2
Proof of Theorem 11.1. Assume (3). Choose a finite-index free-by-cyclic subgroup H ≤ G H \le G H ≤ G H H H H ≤ G H \le G H ≤ G
For a torsion-free group hyperbolic relative to abelian groups, every nontrivial centralizer is either cyclic or contained in its unique abelian peripheral conjugate. The almost malnormality of peripherals and of maximal loxodromic elementary subgroups gives the CSA property. Hence (1) implies (2).
If G G G F 2 × Z F_{2} \times\mathbb{Z} F 2 × Z K K K s a s − 1 = a − 1 sas^{-1}=a^{-1} s a s − 1 = a − 1 s s s a a a s s s a = a − 1 a=a^{-1} a = a − 1
Corollary 11.6. Every finitely generated torsion-free CSA one-relator group which is virtually free-by-cyclic is toral relatively hyperbolic. In particular, this applies to
G = ⟨ X ∣ [ u , v ] ⟩ G=\langle X\mid[u,v]\rangle G = ⟨ X ∣ [ u , v ]⟩ whenever virtual free-by-cyclicity is established independently.
Corollary 11.7. Every finitely generated subgroup of a torsion-free CSA virtually free-by-cyclic group is itself toral relatively hyperbolic.
Proof. If L ≤ G L \leq G L ≤ G H ≤ G H \leq G H ≤ G L ∩ H L \cap H L ∩ H L L L H H H L L L Theorem 11.1 applies.
CSA one-relator groups
The results above do not establish toral relative hyperbolicity for every torsion-free CSA one-relator group containing Z 2 \mathbb{Z}^{2} Z 2
We recall a reduction using one-relator towers. By [37 Propositions 4.3 and 4.6, Lemmas 4.4 and 5.2] , a factored one-relator tower is stable down to a primitive extension core, unless it is stable throughout or encounters a powered core. A powered core is noncyclic and generated by a , b a,b a , b a m = b n ≠ 1 a^{m}=b^{n}\neq1 a m = b n = 1 a , b a,b a , b
It remains to prove toral relative hyperbolicity for the two-generator primitive extension cores not satisfying the hypotheses above, and to prove relative quasiconvexity of the Magnus subgroups used in the stable part of the tower. The condition on segment stabilizers alone does not imply this relative quasiconvexity.
Algorithmic cases for CSA one-relator groups
Let G = ⟨ X ∣ r ⟩ G=\langle X \mid r\rangle G = ⟨ X ∣ r ⟩
P ( G ) : G is CSA and contains a subgroup isomorphic to Z 2 . \mathcal{P}(G):\qquad G\text{ is CSA and contains a subgroup isomorphic to }\mathbb{Z}^{2}. P ( G ) : G is CSA and contains a subgroup isomorphic to Z 2 . An algorithm on a specified class is required to terminate on every presentation defining a group in that class. It need not decide membership in the class. A semialgorithm for a property terminates precisely when that property holds.
A recognition algorithm
Proposition 12.1. Let C \mathcal{C} C C \mathcal{C} C C \mathcal{C} C Z 2 ≤ G \mathbb{Z}^{2}\leq G Z 2 ≤ G P ( G ) \mathcal{P}(G) P ( G )
Proof. Use the uniform solution of the word problem for one-relator groups. First check whether the generators commute pairwise. If they do, G G G Z 2 \mathbb{Z}^{2} Z 2
Otherwise run the following two searches in parallel.
(i) Enumerate word triples ( a , b , g ) (a,b,g) ( a , b , g )
a ≠ 1 , b ≠ 1 , [ a , b ] = [ a , g b g − 1 ] = 1 , [ a , g ] ≠ 1. (28) a \ne1,\quad b \ne1,\quad[a,b]=[a,gbg^{-1}]=1,\quad[a,g]\ne1. \tag*{(28)} a = 1 , b = 1 , [ a , b ] = [ a , g b g − 1 ] = 1 , [ a , g ] = 1. (28) Such a triple proves that G G G P ( G ) \mathcal{P}(G) P ( G )
(ii) Run Dahmani’s recognition algorithm for relative hyperbolicity with abelian peripheral groups [7 ] . When it returns an exact relative presentation, compute the ranks of the peripheral groups. Then G G G P ( G ) \mathcal{P}(G) P ( G )
A group is not CSA if and only if a triple satisfying (28) exists. Indeed, in a CSA group, b b b g b g − 1 gbg^{-1} g b g − 1 a a a g g g b ≠ 1 b\ne1 b = 1 a , g ∈ C G ( b ) a,g\in C_G(b) a , g ∈ C G ( b ) G G G
Search (i) terminates if G G G G G G C \mathcal{C} C [8 Lemma 10.1] , and every Z 2 \mathbb{Z}^2 Z 2
The procedure decides both properties on C \mathcal{C} C § 3 , the proof gives no bound on its running time.
Applications
We apply Proposition 12.1 to the following classes. Except in the first case, CSA is a property to be decided. The conclusions in Cases 6–9 and the finite-hierarchy application assume the combination statement of [53 ] , with the hypotheses given in Case 7.
Case 1. Toral relatively hyperbolic groups. Such a group is CSA. Dahmani’s algorithm computes a peripheral structure, and the ranks of the peripheral groups decide P ( G ) \mathcal{P}(G) P ( G )
Case 2. Virtually free-by-cyclic groups. Suppose G G G
F ⋊ α Z , F\rtimes_{\alpha}\mathbb{Z}, F ⋊ α Z , where F F F
G is CSA ⟺ G is toral relatively hyperbolic . G\text{ is CSA}\quad\Longleftrightarrow\quad G\text{ is toral relatively hyperbolic}. G is CSA ⟺ G is toral relatively hyperbolic . Proposition 12.1 therefore decides both CSA and P ( G ) \mathcal{P}(G) P ( G )
Case 3. Ascending HNN extensions of finite-rank free groups. Suppose
G ≅ ⟨ F , t ∣ t x t − 1 = ϕ ( x ) ( x ∈ F ) ⟩ , ϕ : F ↪ F , G\cong\langle F,t\mid txt^{-1}=\phi(x)\ (x\in F)\rangle,\qquad\phi:F\hookrightarrow F, G ≅ ⟨ F , t ∣ t x t − 1 = ϕ ( x ) ( x ∈ F )⟩ , ϕ : F ↪ F , with F F F G G G ( 1 , d ) (1,d) ( 1 , d ) d ≥ 2 d\ge2 d ≥ 2 [43 Theorem 4.7] . The automorphism case is already included in Case 2.
Case 4. Partial ascending extensions with a free-factor domain. Suppose
G ≅ ⟨ F , t ∣ t a t − 1 = ψ ( a ) ( a ∈ A ) ⟩ , F = A ∗ B , G \cong\langle F,t \mid tat^{-1}=\psi(a)\ (a\in A)\rangle,\qquad F=A*B, G ≅ ⟨ F , t ∣ t a t − 1 = ψ ( a ) ( a ∈ A )⟩ , F = A ∗ B , where F F F ψ : A ↪ F \psi:A\hookrightarrow F ψ : A ↪ F G G G L L L [5 ] . If G G G L L L L L L G G G [24 ] . The cited embedding theorem requires A A A F F F
Case 5. Finitely generated subgroups of free-group mapping tori. More generally, suppose G G G [36 ] . If G G G
Case 6. Finite graphs of free groups with cyclic edge groups. Suppose G G G N = 1 N=1 N = 1
Case 7. Stable graphs of toral relatively hyperbolic groups. Suppose G G G
vertex groups are finitely generated and toral relatively hyperbolic;
edge groups are finitely generated free and relatively quasiconvex in both endpoint vertex groups;
for some N ≥ 1 N\geq1 N ≥ 1 N N N
The stable combination statement in [53 ] gives CSA ⇒ \Rightarrow ⇒
Case 8. Overlapping commutator relators. Let A A A B B B C C C
x ∈ F ( A ∪ B ) ∖ F ( B ) , y ∈ F ( B ∪ C ) ∖ F ( B ) , 1 ≠ z ∈ F ( B ) . x\in F(A\cup B)\setminus F(B),\qquad y\in F(B\cup C)\setminus F(B),\qquad1\ne z\in F(B). x ∈ F ( A ∪ B ) ∖ F ( B ) , y ∈ F ( B ∪ C ) ∖ F ( B ) , 1 = z ∈ F ( B ) . The groups
G = ⟨ A , B , C ∣ [ x y , z ] = 1 ⟩ G=\langle A,B,C\mid[xy,z]=1\rangle G = ⟨ A , B , C ∣ [ x y , z ] = 1 ⟩ satisfy the hypotheses of Case 7. Rewrite the relation as x − 1 z x = y z y − 1 x^{-1}zx=yzy^{-1} x − 1 z x = y z y − 1 F ( B ) ∗ Z F(B)*\mathbb{Z} F ( B ) ∗ Z N = 2 N=2 N = 2 x , y , z x,y,z x , y , z
Case 9. Exceptional Magnus intersections. Suppose the presentation has Magnus subgroups generated by A ∪ B A \cup B A ∪ B B ∪ C B \cup C B ∪ C A A A B B B C C C
⟨ A , B ⟩ ∩ ⟨ B , C ⟩ ⊋ ⟨ B ⟩ . \langle A,B\rangle\cap\langle B,C\rangle\supsetneq\langle B\rangle. ⟨ A , B ⟩ ∩ ⟨ B , C ⟩ ⊋ ⟨ B ⟩ . Linton’s dichotomy gives either a 2-free group or a two-generator one-relator generalized Baumslag–Solitar subgroup H H H [37 Theorem 3.17 and Remark 3.18] . The 2-free case is hyperbolic. In the other case, CSA forces the nonfree group H H H Z 2 \mathbb{Z}^{2} Z 2 Z 2 \mathbb{Z}^{2} Z 2
Finite hierarchies. The same conclusion holds for a finite hierarchy whose terminal groups satisfy one of Cases 1–5 and whose successive splittings satisfy the free-edge, relative-quasiconvexity and segment-stabilizer assumptions of Case 7. If the total group is CSA, all vertex groups inherit CSA, so induction gives toral relative hyperbolicity. The existence of such a hierarchy is a hypothesis of this application.
Explicit examples and recognition of presentations
A family of CSA groups containing Z 2 \mathbb{Z}^{2} Z 2 For every integer m ≥ 2 m \ge2 m ≥ 2
G m = ⟨ b , t ∣ [ t , b − 1 t b t − 1 b − m ] = 1 ⟩ G_m = \langle b,t \mid[t,b^{-1}tbt^{-1}b^{-m}] = 1\rangle G m = ⟨ b , t ∣ [ t , b − 1 t b t − 1 b − m ] = 1 ⟩ satisfies P ( G m ) \mathcal{P}(G_m) P ( G m ) a = b − 1 t b t − 1 b − m a=b^{-1}tbt^{-1}b^{-m} a = b − 1 t b t − 1 b − m
G m ≅ ⟨ a , b , t ∣ [ t , a ] = 1 , t b t − 1 = b a b m ⟩ . G_m \cong\langle a,b,t \mid[t,a] = 1,\ tbt^{-1} = bab^{m}\rangle. G m ≅ ⟨ a , b , t ∣ [ t , a ] = 1 , t b t − 1 = ba b m ⟩ . The free-group calculation and the relative expansion theorem give relative hyperbolicity with the single peripheral subgroup ⟨ a , t ⟩ ≅ Z 2 \langle a,t\rangle\cong\mathbb{Z}^{2} ⟨ a , t ⟩ ≅ Z 2 G m G_m G m
For the standard Baumslag–Solitar presentations BS ( m , n ) = ⟨ a , t ∣ t a m t − 1 = a n ⟩ \operatorname{BS}(m,n) = \langle a,t \mid ta^{m}t^{-1} = a^{n}\rangle BS ( m , n ) = ⟨ a , t ∣ t a m t − 1 = a n ⟩ m , n ≠ 0 m,n \ne0 m , n = 0 ( m , n ) = ( 1 , 1 ) (m,n) = (1,1) ( m , n ) = ( 1 , 1 ) ( − 1 , − 1 ) (-1,-1) ( − 1 , − 1 ) Z 2 \mathbb{Z}^{2} Z 2 [19 ] .
Recognition from presentations. For finite-rank free-by-cyclic, ascending, and partial ascending presentations with free-factor domain, free-group algorithms verify injectivity and the required basis conditions. Finite graphs of free groups with injective cyclic edge maps can also be enumerated. A finite sequence of Tietze transformations verifies that one of these presentations defines the original group. One can similarly enumerate finite-index subgroups together with finite-rank free-by-cyclic presentations. Applying Proposition 12.1 to these presentations gives semialgorithms for P ( G ) \mathcal{P}(G) P ( G )
This enumeration need not decide whether a group belongs to one of the classes. For infinite-rank kernels in Case 2, unspecified embeddings in Case 5, and the geometric hypotheses of Case 7, the decision procedures apply under the stated assumptions.
Arbitrary torsion-free one-relator groups
The following procedures apply to every torsion-free one-relator group:
The search for a triple satisfying (28) terminates precisely when G G G
The hyperbolicity-detection procedure terminates on hyperbolic groups. Such a group contains no Z 2 \mathbb{Z}^{2} Z 2 P ( G ) \mathcal{P}(G) P ( G )
Finitely many commutator tests decide whether G G G P ( G ) \mathcal{P}(G) P ( G )
Whenever the relative-hyperbolicity procedure produces an abelian peripheral subgroup of rank at least two, P ( G ) \mathcal{P}(G) P ( G ) P ( G ) \mathcal{P}(G) P ( G )
( G torsion-free one-relator and CSA , Z 2 ≤ G ) ⟹ G toral relatively hyperbolic (G\text{ torsion-free one-relator and CSA},\quad\mathbb{Z}^{2}\leq G)\Longrightarrow G\text{ toral relatively hyperbolic} ( G torsion-free one-relator and CSA , Z 2 ≤ G ) ⟹ G toral relatively hyperbolic in general. The results above do not prove this implication for every commutator presentation ⟨ X ∣ [ u , v ] ⟩ \langle X\mid[u,v]\rangle ⟨ X ∣ [ u , v ]⟩
The forbidden-subgroup criterion in [19 ] gives a semialgorithm for failure of CSA. A finite unsuccessful search does not prove CSA. The decision algorithms above use, in addition, the implication from CSA to toral relative hyperbolicity in each stated class.
Acknowledgment. The development of algorithms from the results stated in [46 , 47 ] and the editing of this paper were carried out with the assistance of ChatGPT 6 Pro. Our original model-theoretic results are due to the authors and originate in our earlier manuscript, written in 2020; they are independent of both cited results.
