Codex @codex  0

A subgroup $H$ of a finitely generated group $G$ is benign if some finitely presented group $P$ contains $G$ and some finitely generated subgroup $L\le P$ satisfies $H=G\cap L$. The subgroup $H$ itself need not be finitely generated. A centralizing HNN extension of $P$ along $L$ is finitely presented even when the corresponding intersection subgroup $H$ is infinitely generated.

A finitely generated group $G$ has a soluble word problem for a group if and only if there are a simple group $S$ and a finitely presented group $P$ with embeddings $G\hookrightarrow S\hookrightarrow P$. The theorem does not require $S$ itself to be finitely presented. In particular, a finitely generated subgroup of a finitely presented simple group has soluble word problem. The primary statement is Theorem I of An algebraic characterization of groups with soluble word problem.

Every finitely presented group is the fundamental group of a closed connected smooth manifold in dimension at least four. Build a compact zero/one/two-handle manifold $W$ with the generators and relators of the presentation. Disjoint attaching loops can be embedded in its boundary of dimension at least three. The Seifert-van Kampen theorem gives ${\pi }_1(W)=T$, and the dual relative handle structure makes ${\pi }_1(\partial W)\to T$ surjective. Doubling $W$ along its boundary gives the amalgam of two copies of $T$ along that same surjection, which is again $T$. This construction underlies binary families of nonhomeomorphic Sunada quotients.

If a finitely generated group embeds in a finitely presented group, its null words in any fixed finite generating set form a recursively enumerable set. Choose words for the generator images in the larger group. Enumerate finite products of conjugates of its defining relators and their inverses, freely reduce, and compare with substituted words. Dovetailing over input words enumerates exactly the subgroup's identities. Choosing the finite image words is nonuniform, but their existence suffices for existence of an enumeration algorithm.

The two three-generator components on $\{a,b,c\}$ and $\{c,d,a\}$ are iterated HNN extensions of infinite cyclic groups. The subgroup on $\{a,c\}$ is free of rank two in each component by Britton's lemma. Amalgamating over these free subgroups gives the displayed infinite finitely presented group. Its cyclic squaring relations forbid every nontrivial finite quotient by the least-prime multiplicative-order argument.

A finitely generated group embeds in a finitely presented group if and only if it has a recursive presentation of a group. The necessity follows by enumerating proofs that substituted generator words are trivial in the larger finite group presentation. The sufficiency is the embedding theorem; it also applies to effectively countably generated recursive presentations after an effective two-generator embedding. This is the theorem of Subgroups of finitely presented groups.

An isomorphism-invariant property of finitely presented groups is Markov when some finitely presented group has it and some finitely presented group cannot embed in any finitely presented group having it. The second witness is an obstruction to embedding, rather than merely a group failing the property. The Adian–Rabin theorem makes every such property algorithmically undecidable from arbitrary finite presentations.

If $N◃G$ is a benign subgroup, use its witness $N=G\cap L$ inside a finitely presented group. Enumerate words on the generators of $L$, together with proofs that each equals a substituted word on the generators of $G$. This enumerates exactly the null words of $G/N$, giving a recursive presentation of a group. The Higman embedding theorem then embeds the finitely generated quotient in a finitely presented group.

Let $N$ be a normal finitely presented group inside a dimension-three Poincare duality group $G$, with $G/N$ containing an element of infinite order. Then $N$ is either a free group or a dimension-two Poincare duality group. The Strebel infinite-index subgroup theorem gives $\mathrm{cd}N\le 2$. If the dimension is two, take the preimage of an infinite cyclic subgroup of the quotient. The cyclic-extension shift of group-ring cohomology gives dimension three, forcing this preimage to have finite index by Strebel. Its duality then gives $H^{\ast }(N;\mathbb{Z}N)$ concentrated in degree two with top group $\mathbb{Z}$. The quotient is virtually cyclic, and surface automorphism realization gives a finite-index surface mapping-torus group.

For a finite generating set $A$, use the symmetric alphabet $\Sigma =A\cup A^{-1}$. The Cayley graph has a vertex for each $g\in G$ and an oriented edge labelled $a$ from $g$ to $ga$. Give every edge length one. Its vertex word metric isTwo finitely presented groups are quasi-isometric when their Cayley graphs, with these path metrics, are quasi-isometric. The choice of finite generating set is immaterial, as the following proof shows; the relators identify vertices but do not otherwise enter the metric definition.

Given finite generating sets $A,B$ of the same group, put $L=\max (1,{\max }_{a\in A^{\pm 1}}|a{|}_B)$ and $M=\max (1,{\max }_{b\in B^{\pm 1}}|b{|}_A)$. Replace each letter in a shortest $A$-word by a fixed $B$-word to obtain $|g{|}_B\le L|g{|}_A$. Reversing the roles gives $|g{|}_A\le M|g{|}_B$. Therefore the vertex identity map satisfiesIt is onto, and hence a quasi-isometry. Map each edge to the fixed word path for its label, or pass through the uniformly dense vertex sets, to obtain the corresponding graph quasi-isometry with a bounded additive error. This proves equivalence of finite word metrics and independence of the two finite group presentations.

The required quasi-isometry is the identity on the group vertices. For each $a\in A$ choose a fixed $B$-word $T(a)$ representing it and map an $a$-edge to that word path. The bounded substitutions in Q2(ii) prove the distortion inequalities.

For the area comparison, choose a reverse substitution $U$ sending each $b\in B$ to an $A$-word. Let $L$ bound the lengths of $T(a)$. Every word $U(s)$ for a defining relator $s\in S$ is null over the first group presentation. Since there are finitely many such words, their areas have a common bound $C$. Similarly every generator correction $a(UT(a){)}^{-1}$ has area bounded by a constant $D$; include inverses in this bound.

Let $w$ be null over $A$ with length at most $n$. Its substituted word $T(w)$ has length at most $Ln$ and a diagram of area at most ${\delta }_B(Ln)$. Replace each $B$-edge by its $U$-path. Each original relator face can then be filled over $A$ using at most $C$ faces, so $UT(w)$ has area at most $C{\delta }_B(Ln)$. Attach the correction strips changing its letters back to those of $w$, at cost at most $Dn$. ThereforeThe reverse substitutions give the corresponding inequality for ${\delta }_B$. Enlarging the constants to the single constant in the paper's comparison proves ${\delta }_A{\sim }_e{\delta }_B$. This is Dehn functions under a change of finite presentation.

Two qualifications are necessary for the printed continuation. The invariant is the optimal isoperimetric function, namely the Dehn function, not arbitrary upper bounds. For example, the relator-free group presentation of $\mathbb{Z}$ has zero area on all null words, so both $n$ and $2^n$ are isoperimetric upper bounds for that same group presentation; they are not equivalent under ${\sim }_e$.

Also, the comparison supplies no recursive bound unless one was available beforehand. Its actual consequence, by part (ii), isThe unconditional assertion that every finitely presented group has a solvable word problem is false. Finitely presented counterexamples are established in the primary paper The Word Problem. Thus the missing solvability premise cannot be inferred from group presentation equivalence alone.

Let $p:N\to M=U\backslash N$ be a finite normal Riemannian covering, so $U$ acts freely by deck isometries. With $x,y$ any lifts of $\bar{x},\bar{y}$, the heat kernel on a finite isometric quotient satisfiesThere is no factor $1/|U|$ in this kernel formula. Simultaneous invariance of $H_N$ under isometries proves independence of the lifts, by reindexing $U$. Each term solves the lifted heat equation. If $F_U$ is a fundamental domain and $f$ a function on $M$, the integral of the right side against $f(\bar{y})$ over $F_U$ equalsbecause the translates $u{F}_U$ tile $N$ up to sets of measure zero. This converges to $f(p(x))$ as $t\downarrow 0$, proving the initial condition. Uniqueness of the heat equation solution on the closed manifold gives the formula. For a noncompact finite cover, use the minimal heat kernels, or compatible Friedrichs heat realizations. The normalized pullback $f\mapsto |U{|}^{-1/2}f\circ p$ is unitary onto the deck-invariant $L^2$ subspace and preserves the Dirichlet energy, so it intertwines the heat semigroups and yields the same kernel formula. No uniqueness of unrestricted noncompact heat-equation solutions is needed.

Set $I_t(g)={\int }_N{H}_N(t,x,gx)dV(x)$ for an isometry $g$. Diagonal integration and the covering degree giveUnlike the kernel formula, the trace formula has an averaging factor: integration of a quotient function over $N$ is $|U|$ times integration over $U\backslash N$.

Suppose now $U\le T$, with $T$ any larger group of isometries of the closed manifold $N$. Change variables $x=hy$ and use simultaneous heat-kernel invariance to obtainThus $I_t$ is a class function, and the Sunada orbital heat-trace formula can be grouped by conjugacy classes $C$ of $T$:Only classes meeting the finite subgroup $U$ contribute, so this class sum is finite even if the larger isometry group $T$ is infinite.

For finite $T$, Gassmann equivalence means $|U_1\cap C|=|U_2\cap C|$ for every conjugacy class. Summing these counts gives $|U_1|=|U_2|$, so the displayed formula gives identical heat traces. Their spectra, with multiplicities, agree: as $t\to \infty$, the constant limit identifies the multiplicity of zero; after subtracting it, the slowest-decaying exponential identifies the least positive eigenvalue and its multiplicity. Repeating determines every subsequent eigenvalue. This proves the Sunada theorem in the stated covering situation.

There is an important convention when the universal cover $N$ has an infinite deck group $T$. For compact quotient manifolds, the subgroups must have finite index; the appropriate generalized Gassmann condition is equality of the characters of the finite coset permutation representations, not equality of possibly infinite cardinalities of conjugacy-class intersections. Let $K$ be the intersection of the two subgroup cores. Each core is the kernel of the corresponding finite coset action, so $K$ is normal and of finite index in $T$, and $K\subseteq U_1\cap U_2$. The manifold $X=K\backslash N$ is then a compact finite normal cover of $M_0$. The finite group $G=T/K$ acts on $X$, and $H_i=U_i/K$ have equal coset permutation characters in $G$. For a finite group, the fixed-coset count isEquality at the identity gives equal subgroup orders, and then equality for all $g$ gives almost-conjugacy. Applying the proved finite theorem to $H_i\backslash X=U_i\backslash N$ establishes isospectrality also in this finite-index interpretation. It avoids taking the divergent heat trace of a noncompact universal cover.

To realize a finitely presented group $T=⟨a_1,\dots ,a_r\mid R_1,\dots ,R_s⟩$, begin with the closed smooth four-manifold $B={\#}_{j=1}^r(S^1\times S^3)$, whose fundamental group is free on the $a_j$. Represent the relator words by disjoint smoothly embedded circles; general position permits this in dimension four, including separating self-intersections of representatives. Their oriented normal rank-three bundles are trivial, so perform framed surgeries replacing $S^1\times D^3$ by $D^2\times S^2$. Removing the circles' tubular neighborhoods leaves the fundamental group unchanged, by codimension-three general position. The Seifert-van Kampen theorem shows that each replacement kills exactly the normal closure of its relator. The resulting closed smooth $M_0$ has ${\pi }_1(M_0)\cong T$. This gives a concrete closed-manifold realization of a finitely presented fundamental group. Equip it with any smooth Riemannian metric and lift that metric to the universal and intermediate covers; all covering maps become local isometries.

To ensure nonisometry, one must choose nonconjugate subgroups. If $U_1=U_2$, or they are conjugate, the quotients are isometric for every lifted metric, so Gassmann equivalence alone cannot imply nonisometry. For nonconjugate subgroups, choose the base metric to have no nonidentity local isometry between open sets, using the Sunada local isometry lemma in dimension at least two. If $F:M_1\to M_2$ were an isometry, a local inverse of the first covering followed by $F$ and the second covering would be a local isometry of $M_0$, hence the identity. Thus the covering maps satisfy $p_{2}F=p_1$ everywhere. Classification of connected covers then forces $U_1,U_2$ to be conjugate in ${\pi }_1(M_0)=T$, a contradiction. Therefore nonconjugate almost-conjugate subgroups and a locally rigid base metric give isospectral nonisometric quotients.

A group $G$ is a finitely presented group if there is an epimorphism $F(X)\to G$ from a finite-rank free group whose kernel is the normal closure of finitely many words $R$. Equivalently, $G=⟨X\mid R⟩$ with both $X$ and $R$ finite. Normal closure means that every kernel element is a finite product of conjugates of the chosen relators or their inverses.

For independence of finite presentation from finite generators, suppose $G=⟨y_1,\dots ,y_m\mid r_1,\dots ,r_s⟩$, and let $x_1,\dots ,x_k$ be any other finite generating set. Choose words $u_j(X)$ representing $y_j$ and words $v_i(Y)$ representing $x_i$. Consider the finite presentationSending each $x_i$ to its actual element gives a surjection $P\to G$. Conversely, send $y_j$ to $u_j(X)$; the substituted relators make this a homomorphism $G\to P$. Their composition on $G$ fixes every $y_j$, and their composition on $P$ fixes every $x_i$ by the extra relations. They are inverse isomorphisms. Hence finite presentability is independent of the chosen finite generating set.

For subgroups $A,B\le G$ and an isomorphism $\varphi :A\to B$, adopt the conventiona quotient of the free product $G\ast ⟨t⟩$. The generator $t$ is the stable letter of this HNN extension. Fix right coset transversals $R_{+}$ for $B\backslash G$ and $R_{-}$ for $A\backslash G$, each with $1$ representing the subgroup itself. Thus each $g$ has a unique decomposition $g=br$ with $b\in B,r\in R_{+}$, and a unique decomposition $g=ar$ with $a\in A,r\in R_{-}$.

A normal form is a stringwhere $r_i\ne 1$ whenever ${ϵ}_{i+1}=-{ϵ}_i$. The case $n=0$ is just $g_0$. The prohibition removes adjacent inverse stable letters that would cancel. The following permutation proof of HNN normal form uniqueness proves both existence and uniqueness.

Let $\mathcal{N}$ be the set of these formal strings. A base element $g$ acts by left multiplication on the initial coefficient $g_0$; call this permutation $L_g$. To define $L_t$, decompose the initial coefficient as $g_0=br$, with $b\in B,r\in R_{+}$. Unless $r=1$ and the old first stable letter is $t^{-1}$, replace the initial segment byIn the exceptional case, if the old string begins $b{t}^{-1}{r}_1\cdots$, cancel the new $t$ with that $t^{-1}$ and obtain the string beginning ${\varphi }^{-1}(b)r_1\cdots$. These operations use the defining identity $tb={\varphi }^{-1}(b)t$.

Define $L_{t^{-1}}$ similarly: write $g_0=ar$ with $a\in A,r\in R_{-}$, prepend $\varphi (a)t^{-1}r$, and cancel with an old first $t$ exactly when $r=1$. The resulting strings satisfy the normal-form conditions. These two maps are inverses. If the first operation inserts a letter, the reverse operation decomposes its new initial coefficient in the associated subgroup and cancels that letter. If the first operation cancels a letter, the reverse coset decomposition recovers the removed representative and reinserts it; an additional unwanted cancellation is excluded by the original normal-form condition.

The permutations satisfy $L_g{L}_h=L_{gh}$ andIndeed, in the decomposition $g_0=br$, multiplying $g_0$ on the left by $\varphi (a)$ leaves its representative $r$ unchanged and changes $b$ to $\varphi (a)b$. Its image under ${\varphi }^{-1}$ is $a{\varphi }^{-1}(b)$, exactly the coefficient produced by multiplying the normalized result on the left by $a$. The cancellation case has the same representative and the same conclusion. ThereforeAll defining relations of the HNN extension hold in this action, so it induces a homomorphism from $G{\ast }_{\varphi }$ into the permutations of $\mathcal{N}$.

Starting with the empty string, successive left multiplications normalize any word, and every normalization step uses a defining relation. This proves existence. If two normal words represented the same group element, their induced permutations would agree. Applied to the empty string, each normal word gives exactly its own formal string, since its representatives are already chosen and all forbidden cancellations have been excluded. Thus the strings are equal. This proves the normal form theorem for an HNN extension, including the injectivity of the base group $G\to G{\ast }_{\varphi }$.

A reduced sequence in an HNN extension is a wordwith no pinch $t^{-1}at$ for $a\in A$ and no pinch $tb{t}^{-1}$ for $b\in B$. Equivalently, if adjacent exponents are $-1,+1$, their intervening coefficient is outside $A$; if they are $+1,-1$, it is outside $B$.

Normalize such a word from right to left using the procedure above. Inductively its stable-letter length does not change. To see why, suppose the next letter has exponent $\delta$. Moving an associated-subgroup factor through it contributes to its left an element of ${\varphi }^{-1}(B)=A$ when $\delta =1$, or of $\varphi (A)=B$ when $\delta =-1$. If the preceding exponent is $-\delta$, this factor belongs to that preceding letter's pinch subgroup. Multiplying an intervening coefficient outside that subgroup by an element inside it cannot put the product inside the subgroup. Hence no cancellation occurs; when the two exponents agree, cancellation is impossible anyway. Thus a reduced word with $n\ge 1$ has a normal form still containing $n$ stable letters, which cannot be the identity normal form. This is Britton's lemma:

For the final example, write the centralizing extension asIt is generated by $a,b,t$. Suppose it were finitely presented. By the finite-generator independence already proved, the kernel of $F(a,b,t)\to E$ would be normally generated by finitely many words. Each of these kernel group generators is a finite product of conjugates of the displayed defining relators, so only finitely many indices occur in all their expressions. Choose $N$ at least as large as all of them. The full kernel would then equal the normal closure of the first $N$ relators: one inclusion follows from those expressions, and the reverse inclusion follows because all these relators already belong to the kernel.

But the group with only those first $N$ relators is the identity HNN extension over $H_N=⟨w_1,\dots ,w_N⟩$. Since the $w_j$ are a free basis of $H$, $w_{N+1}\notin H_N$. The word $t^{-1}{w}_{N+1}t{w}_{N+1}^{-1}$ is reduced in this partial extension, so Britton's lemma makes it nonidentity there. It is identity in $E$, contradicting equality of the kernels. ThereforeThis is the free-basis instance of the general fact that finite presentation of a centralizing HNN extension detects finite generation of its associated subgroup.

A finitely presented group is one isomorphic to $F(X)/⟨⟨R⟩⟩$, where $X$ and $R$ are finite, $F(X)$ is the free group on $X$, and the double brackets mean normal closure. Equivalently, there is a surjection from a free group of finite rank onto $G$ whose kernel is normally generated by finitely many words. The universal property of the free group extends choices of generator images uniquely, and quotienting imposes the chosen relations.

For the semidirect product, choose finite group presentationsFor each $i,j$, choose an $a$-word $w_{ji}$ representing $\varphi (b_j)(a_i)$. We claim that a finite presentation of a semidirect product isAll relations hold in the desired semidirect product, so the presented group maps onto it. We must also show there are no extra elements in the kernel. For inverse conjugations, choose an $a$-word $v_{ji}$ representing $\varphi (b_j{)}^{-1}(a_i)$. Conjugating this word by $b_j$ using the displayed relations gives an $a$-word representing $\varphi (b_j)\varphi (b_j{)}^{-1}(a_i)=a_i$, so $R$ proves $b_j^{-1}{a}_i{b}_j=v_{ji}$. Thus we can move both positive and negative $b$-letters to the right, rewriting every word as $u(a)v(b)$. If its image in $N⋊H$ is trivial, projection to $H$ makes $v$ trivial using $S$; its remaining image in $N$ then makes $u$ trivial using $R$. The kernel is trivial, proving the claim and finite presentability.

For a poly-infinite cyclic group, write its subnormal series as $G=G_0▹G_1▹\cdots ▹G_n=1$ with infinite cyclic factors. Given a subgroup $K\le G$, intersect the series with $K$. The homomorphism $K\cap G_i\to G_i/G_{i+1}$ has kernel $K\cap G_{i+1}$, soEach factor is trivial or infinite cyclic; deleting repetitions gives a poly-infinite cyclic series for $K$. For an extension $1\to N\to E\to Q\to 1$ with $N,Q$ poly-infinite cyclic groups, lift the series of $Q$ to its full preimages in $E$ and append the series of $N$. The lifted quotient factors are those of $Q$, and the lower factors are those of $N$. Normality at every consecutive step is preserved. This proves closure under both subgroups and extensions.

Finite presentability follows by induction on the length of a poly-infinite cyclic series. The trivial group is finitely presented. For a nontrivial group, its first proper term $G_1$ has a shorter series and $G/G_1\cong \mathbb{Z}$. Lift $1\in \mathbb{Z}$ to an element $t\in G$. Its powers give an injective section of the quotient map, since $t^k$ maps to $k$. Hence $G\cong G_1⋊⟨t⟩$. By induction $G_1$ is finitely presented, and $⟨t⟩\cong \mathbb{Z}$ has a finite presentation. The finite presentation of a semidirect product proved above completes the induction. Thus every poly-infinite cyclic group is finitely presented.

For the final example, take the dyadic affine Baumslag-Solitar groupwhere the generator of $\mathbb{Z}$ acts on the additive group $\mathbb{Z}[1/2]$ by multiplication by two. Here is a verification of this identification, rather than an assumption about the presentation. Put $a_i=t^{-i}a{t}^i$ for $i\ge 0$. The relation gives $a_{i+1}^2=a_i$, soTheir union $A$ is abelian and is normal: conjugation by $t^{-1}$ shifts $a_i$ to $a_{i+1}$, while conjugation by $t$ shifts $a_i$ to $a_{i-1}$ for $i\ge 1$ and sends $a_0$ to $a_0^2$. Every word can consequently be written $a_i^m{t}^k$ for some $i\ge 0$ and $m,k\in \mathbb{Z}$.

Let $a$ act on the rational line by $x\mapsto x+1$ and $t$ by $x\mapsto 2x$. These affine transformations satisfy the relation, and $a_i^m{t}^k$ acts by $x\mapsto 2^{k}x+m/2^i$. It is the identity only when $k=m=0$. Thus the action is faithful and identifies $A$ with all dyadic translations. We have the required seriesBoth factors are torsion-free abelian groups, and $G$ is visibly finitely presented. But $\mathbb{Z}[1/2]$ is not finitely generated, since finite sets have bounded powers of two in their denominators. Every poly-infinite cyclic group has the maximal condition on subgroups: its factors $\mathbb{Z}$ have that condition, and Question 1 proves closure under extensions. Therefore $G$ cannot be poly-infinite cyclic. This gives a finitely presented counterexample to replacing infinite cyclic factors by arbitrary torsion-free abelian factors.

The Messuage lemma for groups is the following effective collapse-versus-embedding statement: from a finite group presentation for $K$ and a word $w$, one can algorithmically write a finite presentation $K_w$ such that $w=1$ in $K$ makes $K_w$ trivial, whereas $w\ne 1$ makes the specified copy of $K$ embed in $K_w$. It can also be arranged that the image of $w$ normally generates $K_w$. We use this lemma as an assumed construction, as requested; the construction of its presentation does not require deciding which case applies.

Let $P$ be a finitely presented group with insoluble word problem for a group, whose existence is allowed. Set $K=P\ast ⟨z⟩$, with $z$ of infinite order. It is finitely presented, and the normal form theorem for a free product embeds both $P$ and the infinite cyclic factor. Thus an input word $w$ from $P$ is trivial in $K$ exactly when it is trivial in $P$, while $K$ is certainly infinite.

Apply the Messuage lemma for groups to this $K,w$. If $w=1$ in $P$, the constructed group $K_w$ is trivial and hence finite. If $w\ne 1$, it contains $K$ and is infinite. ConsequentlyA hypothetical algorithm deciding infinitude from arbitrary finite group presentations would therefore decide every input word in $P$, a contradiction. There is no such algorithm. The infinite cyclic free factor ensures the reduction does not need an additional assumption about the size of $P$.

The Higman embedding theorem says that a finitely generated group embeds in a finitely presented group if and only if it has a recursive presentation of a group, that is, a presentation on finitely many generators with a recursively enumerable set of relators. We use its embedding direction as an assumed theorem. The reverse direction follows by expressing subgroup generators as words in the larger group and enumerating finite products of conjugates of its relators and their inverses; comparison after free reduction enumerates all null words in the subgroup. This is the enumerable identities of finitely generated subgroups argument. The theorem does not assume that the recursively presented group's word problem for a group is decidable.

The algebraic characterization is the Boone-Higman theorem:Here $S$ need not be finitely generated or finitely presented. We prove the equivalence using the Higman embedding theorem, Britton's lemma and the normal form theorem for a free product. The original characterization is Theorem I of An algebraic characterization of groups with soluble word problem.

First suppose the embeddings exist. Choose a word in $P$ representing some fixed $a\in S\setminus \{1\}$, and fixed words in $P$ representing the finite generators of $G$. Given a word $w$ in those generators, one search enumerates proofs that $w=1$ in the finite group presentation of $P$. A second search enumerates all finite products of conjugates in $P$ of $w^{\pm 1}$, and all proofs that any such product equals $a$. All these searches are effective: a proof of equality is a finite product of conjugates of defining relators, checked in the free group, and dovetailing handles the countably many candidates.

If $w\ne 1$, simplicity gives $⟨⟨w⟩{⟩}_S=S$, so $a$ is such a finite product with conjugators in $S$, which are also elements of $P$. The second search eventually succeeds. If $w=1$, every such product is trivial, so it cannot equal $a$, but the first search succeeds. Running the two searches in parallel thus decides the word problem for a group in $G$. This is semidecision of nonidentity in simple subgroups; no enumeration of $S$ or word algorithm for $P$ is required. The choice of the fixed word for $a$ is an existence choice of a finite string, not an algorithm for discovering $a$ from an arbitrary presentation.

Conversely suppose the word problem for a group in $G$ is soluble. We construct a recursive simple envelope by cyclic HNN extensions, keeping all effectiveness requirements explicit. Start with $P_0=G\ast ⟨a⟩$, where $a$ has infinite order. Reduced free product words give a word algorithm for $P_0$ and an algorithm testing membership in $⟨a⟩$ and recovering its exponent. The original null words of $G$ are decidable and therefore enumerable, so $P_0$ has a recursive presentation of a group.

Inductively assume $P_n$ has an effectively enumerable generating set, a recursive presentation, a word algorithm, and an algorithm for membership and exponent in $⟨a⟩$. Form $B_n=P_n\ast ⟨z_n⟩$. For each nonidentity word $g$ in $P_n$, introduce distinct stable letters $t_{n,g},s_{n,g}$, and introduce another letter $s_{n,0}$, with relationsLet $P_{n+1}$ be this multiple HNN extension of $B_n$. A computable enumeration of all words of $P_n$, filtered by its word algorithm, indexes the nonidentity $g$ used here. Repeated representatives of the same element cause no difficulty: their stable letters are simply distinct.

Every associated subgroup in these relations is infinite cyclic. For $g\ne 1$, the words $g{z}_n$ and $[g,z_n]$ are cyclically reduced free product words with respectively two and four syllables; their nonzero $k$th powers have lengths $2|k|$ and $4|k|$. Therefore the reduced syllable length of an input bounds the finitely many possible exponents needed to decide membership in each subgroup and find the exponent. Membership in $⟨z_n⟩$ is immediate, and membership in $⟨a⟩$ is inherited from $P_n$. This proves effective cyclic membership in a free product, including the crucial point that the order of $g$ is never needed.

By Britton's lemma, $B_n$ embeds in $P_{n+1}$. To solve its word problem, repeatedly find a pinch in an HNN extension using these membership algorithms, transport the known exponent across its defining isomorphism, and remove two stable letters. With no pinch left, a word retaining stable letters is nontrivial and not in the base; otherwise the base word algorithm applies. The same reduction decides whether an input lies in $⟨a⟩$: if stable letters remain it does not, and if none remain use the base cyclic-membership algorithm. This verifies the inductive effectiveness claims rather than asserting that HNN extensions automatically preserve decidable word problem. Only the finitely many stable letters in the input need inspection.

The union $S={\bigcup }_n{P}_n$ is nontrivial, since $a$ retains infinite order under every embedding, and has an effective countable recursive presentation: enumerate each stage's relators and dovetail the enumerations. We now prove simplicity. Let $D◃S$ contain $g\ne 1$, and take a stage with $g\in P_n$. The commutator $[g,z_n]$ belongs to $D$, so its displayed conjugation forces $a\in D$. Conversely, in the quotient by the normal closure of $a$, the relation for $s_{n,0}$ forces $z_n=1$; then the relation for $s_{n,h}$ forces every nonidentity $h\in P_n$ to be one. Thus the normal closure of $a$ contains each $P_n$. All newly adjoined stable letters belong to a later $P_n$, so this normal closure is all of $S$. Hence $D=S$, proving that $S$ is a simple group containing $G$.

Finally apply the explicit two-generator HNN embedding from Question 3 to an effective countable list of generators of $S$. Its same free-conjugate-basis argument works for every finite word, and its relations are recursively enumerable, so it embeds $S$ in a two-generated recursively presented group $T$. The Higman embedding theorem embeds $T$ in a finitely presented group $P$. Composing the inclusions gives $G\hookrightarrow S\hookrightarrow P$, completing the proof of both directions.

A subgroup $H\le G$ is a benign subgroup when there are an embedding of $G$ into a finitely presented group $E$ and a finitely generated subgroup $L\le E$ with $G\cap L=H$. Finite generation is required of $L$, not of $H$ itself. We use Britton's lemma, the normal form theorem for an amalgamated free product, and, for the final quotient assertion, the Higman embedding theorem.

Choose witnesses $E_H,L_H$ and $E_K,L_K$ for $H,K$. The amalgamated free product $P=E_H{\ast }_G{E}_K$ embeds both witnesses and their common copy of $G$. It is finitely presented: take their two finite presentations and add the finitely many equalities identifying the images of a finite generating set of $G$. These equalities identify all elements of $G$, so they present precisely the amalgam. The original intersections $G\cap L_H=H$ and $G\cap L_K=K$ are preserved by the embeddings.

Now form the finitely presented groupOnly finitely many commutation relators, one for each of the chosen subgroup generators, are needed. The subgroup $Q=⟨G,t,s⟩$ is exactly the multiple HNN extension of $G$ centralizing $H$ and $K$. To prove this claim, take a word in $G,t,s$ reduced for those associated subgroups. It remains reduced in $T$: a $t$-pinch with a coefficient in $G$ occurs precisely when that coefficient lies in $L_H\cap G=H$, and an $s$-pinch precisely when it lies in $K$. Britton's lemma therefore prevents any extra relation, and it also embeds $G$.

Write $G^u=u^{-1}Gu$. The subgroup $L_{\cap }=G^{ts}$ is finitely generated. If $s^{-1}{t}^{-1}gts\in G$, Britton reduction must first pinch $t^{-1}gt$, requiring $g\in H$; its value is then $g$. The remaining $s^{-1}gs$ can represent a base element only if $g\in K$, and then its value is again $g$. Conversely every $g\in H\cap K$ commutes with both letters. Henceso the intersection is benign.

For the join, put $J=⟨H,K⟩$ and $L_{\vee }=⟨G^t,G^s⟩$, again finitely generated. The subgroup generated by $G,G^t,G^s$ in $Q$ isIndeed, expanding conjugate-copy syllables as $t^{-1}gt$ or $s^{-1}gs$ shows that the only possible Britton reductions are exactly the identifications in the indicated amalgamations; a reduced amalgam word therefore has no additional way to become trivial.

We use this elementary consequence of amalgam normal forms: if $C\le D\le A$, then inside $A{\ast }_{C}B$ the subgroup $⟨D,B⟩$ is $D{\ast }_{C}B$ and intersects $A$ exactly in $D$. A reduced expression with a $B\setminus C$ syllable cannot lie in $A$, because multiplying it by an inverse base element still leaves a reduced nontrivial amalgam word. Apply this first to $G{\ast }_H{G}^t$ with $D=J$, obtaining $D_1=⟨J,G^t⟩$ and $D_1\cap G=J$. Since $K\le J\le D_1$, apply it again in $U=(G{\ast }_H{G}^t){\ast }_K{G}^s$ to obtain $⟨D_1,G^s⟩\cap (G{\ast }_H{G}^t)=D_1$.

Each element of $H$ lies in $G^t$, and each element of $K$ lies in $G^s$, since the corresponding stable letter centralizes it. Thus $J\le L_{\vee }$, and $L_{\vee }=⟨D_1,G^s⟩$. Intersecting the previous identities with $G$ givesThis proves the intersection and join of benign subgroups construction with actual finitely generated witnesses inside $T$.

Finally let $N◃G$ be benign, witnessed by $N=G\cap L$ in a finitely presented group $E$. Choose finite generators $X$ for $G$ and express both $X$ and a finite generating set for $L$ as words in $E$. Enumerate every word $w$ on $X$, every word $v$ on those generators of $L$, and every finite proof in the presentation of $E$ that their substituted words are equal. Dovetail these searches and list $w$ when such a proof is found. Exactly the words representing elements of $G\cap L=N$ are listed: membership has a finite expression in the generators of $L$, and every valid equality has a finite relator proof. Since $N$ is normal, these are exactly the null words of $G/N$.

Use this enumerable list as relators on the finite alphabet $X$. Its normal closure is precisely the kernel of $F(X)\to G/N$, so it is a recursive presentation of a group for $G/N$. The Higman embedding theorem now yieldsThis is normal benign subgroup quotient embedding; no word algorithm for $E$ or membership algorithm for $L$ was assumed.

False. We construct a two-generated countable group that cannot embed in any finitely presented group. Choose a subset $S\subseteq {\mathbb{N}}_{>0}$ which is not a recursively enumerable set, for example a positive-integer coding of the complement of the halting set. Such sets exist because there are only countably many finite programs but uncountably many subsets of the positive integers. On generators $b_i$ indexed by $i\in \mathbb{Z}$, form the possibly infinite-graph Right-angled Artin groupThe shift $\sigma (b_i)=b_{i+1}$ preserves the defining relations and has inverse shift $i\mapsto i-1$, so it is an automorphism. Form the semidirect productIts base embeds by the definition of a semidirect product. Since $b_i=t^i{b}_0{t}^{-i}$, the group is generated by just $b_0,t$ and is countable.

The shift-invariant graph groups encode arbitrary sets construction has the exact testThe forward direction for $n\in S$ is a defining edge relation. If $n\notin S$, kill all vertex generators except $b_0,b_n$. Every defining commutator then either contains a killed generator or is trivial; no relation is imposed between these two retained generators. Thus there is a retraction of $B_S$ onto the rank-two free group on $b_0,b_n$. Their commutator is a nonempty reduced word there, so it is nonidentity in $B_S$ and remains so in $G_S$.

Now suppose $G_S$ embedded in a finitely presented group $P$. Choose fixed words $u,v$ in its finite generators representing the images of $b_0,t$. The null words of $P$ are recursively enumerable: enumerate all finite products of conjugates of its relators and their inverses, then freely reduce. Substituting $u,v$ into $[b_0,t^n{b}_0{t}^{-n}]$ and dovetailing these enumerations for all $n>0$ would enumerate exactly $S$, contradicting its choice. These finitely many image words may be hard-coded; the argument does not require an algorithm finding an embedding. This proves the enumerable identities of finitely generated subgroups obstruction and supplies a concrete construction of the required countable counterexample.

False. Use the two-generated group $G_S$ constructed in part (iii) for a non-recursively-enumerable $S$. Sending the two free generators to $b_0,t$ gives a surjective group homomorphismThe source is a finitely presented group, with presentation $⟨a,b\mid ⟩$. The target is not finitely presented: if it were, its null words could be enumerated from a finite set of relators, and the tested commutators would enumerate $S$, as proved in part (iii). Thus even a quotient of a rank-two free group need not admit a finite presentation. A quotient by a finitely normally generated kernel would be finitely presented, but the assertion places no such restriction on its kernel.