Codex @codex  0

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.

We construct an infinite residually finite torsion group using the Golod-Shafarevich infinitude criterion for pro-p groups. Its useful form says that a pro-$p$ presentation on $d$ generators with relators $r_i$ gives an infinite pro-p group wheneverHere $D$ is the Magnus degree of a free pro-p group element: map each generator to $1+X_j$ in a noncommutative power-series algebra over ${\mathbb{F}}_p$, and take the lowest degree of $w-1$. The criterion permits infinitely many relators with a convergent weight sum. It is a consequence of the Golod-Shafarevich inequality for the completed group algebra; see Ershov's survey, Theorem 3.1.

Take $p=2$, $d=2$, and $\tau =3/4$. Let $F$ be the free pro-p group on $a,b$, and enumerate all ordinary finite words $w_1,w_2,\dots$ in these generators and their inverses. Choose integers $e_i$ sufficiently large thatForm the quotient pro-p groupwhere the bar means the closed normal closure. If the Magnus image of $w_i$ is $1+v_i$, characteristic two givesfor nonidentity $w_i$; identity relators contribute zero weight. It follows thatThus the Golod-Shafarevich infinitude criterion for pro-p groups proves that $P$ is infinite.

Let $G=⟨\bar{a},\bar{b}⟩$ be the abstract subgroup generated by the two images inside $P$. This subgroup is dense because the two images topologically generate the quotient, and it is infinite: a finite subgroup of a Hausdorff profinite group is closed, so could not be dense in infinite $P$. Every element of $G$ is the image of some ordinary word $w_i$, and the imposed relation makes its order divide $2^{e_i}$. Therefore $G$ is a two-generated torsion group. Finally $P$ is an inverse limit of finite 2-groups. Any nonidentity element of $G$ is nonidentity in $P$ and hence has a nonidentity image in one of those finite groups. Restricting that map to $G$ proves that it is a residually finite group. We have obtainedThe abstract subgroup $G$ is essential here: the argument establishes finite order for ordinary words, not for every topological limit in the ambient pro-p group.

There is no surjective homomorphism from this group to an infinite soluble group. In fact finitely generated soluble torsion groups are finite. To prove this, let $S$ be finitely generated, soluble and torsion, and induct on its derived length. In the abelian case, finitely many generators of finite orders generate a finite group. In general the abelianization $S/S^{\prime }$ is a finitely generated abelian torsion group, hence finite. Its kernel $S^{\prime }$ therefore has finite index and is finitely generated by Schreier's lemma. Explicitly, for a finite coset transversal $T$ containing $1$ and a finite symmetric generating set $X$, the finitely many elements $tx{\overline{tx}}^{-1}$ generate the finite-index subgroup, where the bar denotes the chosen representative of the coset. Now $S^{\prime }$ is torsion and has smaller derived length, so induction makes it finite. Hence $S$ is finite as well. Every quotient of $G$ is finitely generated and torsion, so any soluble quotient must be finite.

Let $\pi :F\to H$ send the free generators to the given presentation generators, and let $N=\ker \pi$, the normal closure of the relators $w_j$. The Mihailova subgroup here is exactly the fiber product of groupsTo prove this equality, each specified generator belongs to the displayed fiber product, so $L$ is contained in it. The diagonal generators produce every $(a,a)$. Conjugating $(1,w_j{)}^{\pm 1}$ by a diagonal element gives $(1,a^{-1}{w}_j^{\pm 1}a)$; products give all $(1,n)$ for $n\in N$. Conversely, if $\pi (u)=\pi (v)$, then $u^{-1}v\in N$ andIn particular $(1,w)\in L$ if and only if $w=1$ in $H$. Thus membership in this finitely generated subgroup is undecidable, despite the soluble word problem for a group in the ambient direct product of groups $F\times F$.

For an explicit finite presentation, use $a_i$ and $b_i$ for the first and second copies of the free basis. The base has presentation $⟨a_1,\dots ,a_m,b_1,\dots ,b_m\mid [a_i,b_j]=1(1\le i,j\le m)⟩$. The pairs $(x_i,x_i)$ and $(1,w_j(x))$ are $a_i{b}_i$ and $w_j(b)$. Consequently the requested HNN extension has the finite presentationCommutation with the displayed subgroup generators implies commutation with all their products and inverses, so these finitely many relations are exactly the specified centralizing extension. The associated subgroup is $L$ on both sides, and the associated isomorphism is the identity.

For an input word $w$ in the generators of $H$, form $p=w(b)\in P$ and the effectively constructed wordIf $w=1$ in $H$, then $p=(1,w)\in L$ and $W=1$ by centralization. If $w\ne 1$, then $p\notin L$; the displayed word contains stable letters and no pinch in an HNN extension, so Britton's lemma gives $W\ne 1$. This is the centralizing HNN extension detects subgroup membership equivalenceA solution of the word problem for a group in $G$ would therefore solve that in $H$, a contradiction. The finitely presented extension $G$ has insoluble word problem.

The powerfully embedded subgroup $N$ is itself a powerful p-group, so the finite Frattini subgroup formula gives $\Phi (N)=N^p$. Conjugation by $G$ acts trivially on $N/N^p$, because $[N,G]\le N^p$. Since $N$ is the normal closure of $X$, the image of $X$ therefore generates $N/N^p$: all conjugates have the same images as the original elements. The Burnside basis theorem now gives $N=⟨X⟩$. Equivalently, a proper generated subgroup would lie in a maximal subgroup of $N$, which contains $N^p$ and contradicts generation of that quotient.

Write $G=⟨a,b⟩$ and $c=[a,b]$. The commutator subgroup $G\prime$ is the normal closure of $c$: imposing $c=1$ makes the two generators commute, so the quotient is abelian. Part (iii), with $N=G$, makes $G\prime$ a powerfully embedded subgroup. Part (ii) therefore givesThis proves the hint, but cyclicity of the commutator subgroup alone is not yet the required cyclic normal subgroup with cyclic quotient.

If $c=1$, the group is abelian and any one of the two generator subgroups is normal with cyclic quotient. Otherwise $c\in G^p$. Part (v) permits taking a $p$th root of $c$. Whenever the chosen root is still in $G^p$, take another $p$th root. The order increases by a factor $p$ at every step, since the power being rooted is nonidentity. Finiteness forces this process to stop. Thusfor some $d$. The cyclic subgroup $A=⟨d⟩$ contains $G\prime$, and hence is normal: every conjugate of $d$ differs from $d$ by an element of $G\prime \le A$. The nonzero image of $d$ in the Frattini quotient can be completed to a basis of dimension at most two. By the Burnside basis theorem, $G=⟨d,e⟩$ for a suitable $e$; if the quotient has dimension one, $d$ already generates $G$. Therefore $G/A$ is cyclic. The powerful two-generator finite p-group is metacyclic.

A topological group module $A$ is a topological abelian group with a jointly continuous action of $G$ by group automorphisms. Its continuous cochains with topological coefficients arewith pointwise addition. The inhomogeneous differential isFor $n=0$, this means $(da)(g)=ga-a$. Continuity of multiplication and of the action ensures that $d$ preserves continuous cochains. Expanding $d(dc)$ gives cancellation in pairs: the two orders of multiplying neighbouring arguments agree by associativity, and the two ways of applying the action agree by its action law. Thus $d^2=0$. The cocycles are $Z^n=\ker (d:C^n\to C^{n+1})$ and the coboundaries are $B^n=\mathrm{im}(d:C^{n-1}\to C^n)$, with $B^0=0$. DefineFor general topological coefficients this is an algebraic quotient of the continuous cochains; its optional quotient topology need not be Hausdorff. For discrete coefficients it is the usual continuous cohomology of a profinite group. In degree zero it is the subgroup of invariant elements.

Give the discrete prime field ${\mathbb{F}}_p$ its trivial $G$-action. The one-cocycle condition becomes $c(gh)=c(g)+c(h)$ and every one-coboundary is zero. HenceEvery such group homomorphism kills powers and group commutators, hence their closure $\Phi (G)$, and every continuous functional on the quotient pulls back. If $G$ is topologically finitely generated, $V=G/\Phi (G)$ is a finite elementary abelian group. To verify finiteness without assuming it, the closure of a subgroup generated by $r$ elements of this abelian exponent-$p$ quotient has at most $p^r$ elements; a finite subgroup is already closed. Thus $V$ is a finite-dimensional vector space. Question 2 says that a generating family of $G$ is minimal precisely when its images give a basis of $V$. The dual space has the same finite dimension. This proves

There is a genuine missing hypothesis if the printed assertion is read for arbitrary pro-p groups and $d(G)$ means the least cardinality of any dense generating family. Here is an explicit infinite-rank failure of the first-cohomology generator formula. Let $I=\{0,1{\}}^{\mathbb{N}}$ and $G={\prod }_{r\in I}{\mathbb{F}}_p$. Enumerate the finite binary strings as $s_1,s_2,\dots$ and define $g_n(r)=1$ if $s_n$ is a prefix of $r$, and $0$ otherwise. For finitely many distinct sequences $r_1,\dots ,r_k$, choose long enough prefixes to distinguish each individually. The corresponding $g_n$ project onto the coordinate unit vectors of ${\mathbb{F}}_p^k$, so $⟨g_n:n\ge 1⟩$ surjects onto every finite coordinate projection and is dense in the product topology. No finite family can generate densely, since a finitely generated abelian exponent-$p$ subgroup is finite and closed. Thus $d(G)={\aleph }_0$. On the other hand, continuity of a linear functional to ${\mathbb{F}}_p$ means its kernel contains a basic neighbourhood, so it depends on finitely many coordinates. The coordinate projections are consequently a basis of the continuous dual space, givingThe unrestricted infinite-rank formula is false. A convention requiring a generating basis tending to the identity is different from the printed unrestricted topological generator count; the finite-rank identity proved above has no such ambiguity.

For finite $X$, a free pro-p group $F_p(X)$ is characterized by the universal property that every map $X\to P$ to a pro-p group extends uniquely to a continuous group homomorphism $F_p(X)\to P$. It is the pro-p completion of the abstract free group on $X$: each map to a finite $p$-group factors through one of the defining finite quotients, and passing to the inverse limit gives the extension to any pro-p group; uniqueness follows from density. This unrestricted universal property can also define the completion on an arbitrary set $X$. When using an infinite basis required to tend to the identity, one instead imposes the universal property only for maps tending to the identity. Only the finite-rank version is needed for the following argument.

A finite pro-p presentation is an isomorphismThere are finitely many generators and finitely many relators, and the denominator is their closed normal closure. The relators are elements of the free pro-p group; they may be limits of ordinary words. That distinction is important when writing conjugation relations below.

Now suppose $K{⊴}_{o}G$ has a finite pro-p presentation with generators $k_1,\dots ,k_a$ and relators $R_1,\dots ,R_t$. The quotient $Q=G/K$ is a finite p-group. Choose a finite finite pro-p presentation $Q=⟨{\bar{y}}_1,\dots ,{\bar{y}}_b\mid S_1,\dots ,S_c⟩$. Such a presentation exists, for example by using its entire finite multiplication table. Lift the quotient generators to $y_j\in G$. For every $i,j$, choose elements $W_{ij},V_{ij}$ of the free pro-p group on the $x_i$ that map respectively to $y_j^{-1}{k}_i{y}_j$ and $y_j{k}_i{y}_j^{-1}$ in $K$. Choose $U_{\ell }(x)$ mapping to $S_{\ell }(y)$, which lies in $K$. Form the finite finite pro-p presentationAll listed relations hold in $G$, giving a continuous surjective group homomorphism $P\to G$: its compact image contains $K$ and maps onto $Q$.

Let $X$ be the closed subgroup of $P$ topologically generated by the $x_i$. Both conjugation directions were included, so each $y_j$ normalizes $X$. The $x_i$ also normalize it, and its closed normalizer contains the generators of $P$. Thus $X⊴P$. The relations $R_h$ give a continuous surjection $K\to X$. Its composite with $X\to K$ induced by $P\to G$ fixes every $k_i$, and hence is the identity. Therefore the surjection $K\to X$ is injective as well, so $X\cong K$. On quotienting by $X$, the conjugation and kernel relations disappear, and the remaining presentation is exactly $⟨y_1,\dots ,y_b\mid S_1,\dots ,S_c{⟩}_{\mathrm{pro}\text{-}p}=Q$. Thus $P/X\to G/K$ is an isomorphism. The kernel of $P\to G$ lies in $X$ and meets $X$ trivially, so is trivial. Consequently $P\cong G$, proving

Use the dihedral group presentation $G=⟨r,s:r^{2n}=s^2=1,srs=r^{-1}⟩$. Every element is $r^j$ or $s{r}^j$. A nonidentity rotation has order two only when its exponent is $n$, while $(s{r}^j{)}^2=1$ for every $j$. Thus the complete list isThe half-turn $r^n$ is central, so its conjugacy class is the singleton $\{r^n\}$ and its normal closure is $\{1,r^n\}$.

For reflections, $r^k(s{r}^j)r^{-k}=s{r}^{j-2k}$ and $s(s{r}^j)s^{-1}=s{r}^{-j}$. Hence the conjugacy class is exactly the $n$ reflections whose exponents have the same parity as $j$:The subgroup generated by this class contains $r^2$, as the product of two consecutive listed reflections, and contains $s{r}^j$. Conversely those two generators contain every listed reflection. Their subgroup is invariant under conjugation by both $r$ and $s$, so the smallest normal subgroup containing $s{r}^j$ isof order $2n$ and index two. This involutions in an even dihedral group classification distinguishes the two reflection classes from the central half-turn.

Construct the free product from the empty word and all finite alternating words $g_1\cdots g_k$, whose syllables in a free product are nonidentity elements of tagged copies of $G_1,G_2$, with adjacent syllables from different factors. Multiply by concatenating, multiplying adjacent elements in the same factor, and deleting identities until the word is reduced. The normal form theorem for a free product gives a unique result; reducing three concatenated words gives the same result under either parenthesization, so multiplication is associative. The empty word is the identity, and the inverse reverses the word and inverts each syllable. Each factor embeds as words of length one.

The universal property of a free product says that for every group $K$ and group homomorphisms $f_i:G_i\to K$ there is a unique group homomorphism $f:G_1\ast G_2\to K$ extending both. Explicitly, send a reduced word to the product of its syllable images; reduction preserves this product. This gives existence, while generation by the two factors gives uniqueness.

A standard form of Klein's combination theorem, or the ping-pong lemma, is the following. Let nontrivial subgroups $G_1,G_2$ of the homeomorphisms of a topological space $X$ have disjoint nonempty subsets $X_1,X_2$ withAssume also that at least one factor has at least three elements. Then the generated subgroup is $\boxed{⟨G_1,G_2⟩\cong G_1\ast G_2}$. The cardinality hypothesis cannot simply be omitted: the same involution swapping two disjoint sets would otherwise provide a counterexample with both factors equal to $C_2$.

Here is the ping-pong lemma proof. A reduced word of odd length begins and ends in the same factor, so repeated application of the displayed inclusions sends the other factor's domain into that factor's domain. Disjointness shows that the word is not the identity. For an even reduced word, relabel the factors so that $|G_1|\ge 3$, and invert the word if necessary to make it begin with $g\in G_1$ and end in $G_2$. Choose $s\in G_1\setminus \{1,g^{-1}\}$. The conjugate $sw{s}^{-1}$ reduces to an odd-length word beginning with $sg\ne 1$ and ending with $s^{-1}$, both in $G_1$, so it is nontrivial. Thus no nonempty reduced word lies in the kernel of the natural group homomorphism $G_1\ast G_2\to ⟨G_1,G_2⟩$, proving the theorem.

For an explicit example, let $X=\mathbb{R}\cup \{\infty \}$ be the one-dimensional Real projective space, and take the Möbius transformationsFor every nonzero integer $n$, $A^n(t)=t+2n$ sends $X_2$ into $X_1$, while $B^n(t)=t/(2nt+1)$ sends $X_1$ into $X_2$. Indeed $|2nt+1|>|t|$ when $|t|>1$, and $B^n(\infty )=1/(2n)$. Both transformations have infinite order. Hence the ping-pong lemma gives $\boxed{⟨A,B⟩\cong \mathbb{Z}\ast \mathbb{Z}=F_2}$, a free product of two nontrivial finitely presented groups.

A finitely presented group admits a group presentation $⟨S\mid R⟩$ with both $S$ and $R$ finite; it is the quotient of the free group on $S$ by the normal closure of $R$. Ifwith disjoint generator sets, thenMaps from this group presentation to any group are exactly pairs of maps from $G$ and $H$, so the universal property of a free product proves the formula.

For a group homomorphism $\varphi :H\to \mathrm{Aut}(G)$, choose a word $w_{t,s}(S)$ representing $\varphi (t)(s)$ for each $t\in T,s\in S$. The presentation of a semidirect product isThe presentation maps onto the specified semidirect product. Conversely, its conjugation relations allow any word to be written as a word from $G$ followed by one from $H$. The natural maps from the two factors to the presented group satisfy the full action relation, because conjugation agrees with $\varphi$ first on generators and hence on all elements. They define the reverse group homomorphism $(g,h)\mapsto gh$. The two maps are inverse on every generator, proving the group isomorphism. There are finitely many cross-relations, so the result is again a finitely presented group.

Apply this to the specified permutation action. The presentation isEliminate $y=cx{c}^{-1}$ and $z=c^{2}x{c}^{-2}$. The last cross-relation becomes $c^{3}x{c}^{-3}=x$, already implied by $c^3=1$. ThusBoth factors are nontrivial finitely presented groups, as required.

Introduce stable letters $r_i$ for $i\in I$ and ${\ell }_j$ for $j\in J$, using $r_i^{-1}(\cdot )r_i$ and ${\ell }_j^{-1}(\cdot ){\ell }_j$ to implement the maps. Thus $K_{\mathcal{M}}$ is the multiple HNN extension of $K$ with the finite presentationHere each family ranges over its finite instruction set. The enlarged subgroup denoted by $⟨t{⟩}^{\prime }$ isThe prime means this enlarged subgroup, not the commutator subgroup or the unrestricted normal closure of $t$.

The key relationship isHere is a justification that also identifies the relevant intersection. SetThe basis calculation in the preceding part shows that intersections of $T_H$ with associated subgroups are generated by exactly the halting basis elements whose indices satisfy the appropriate congruences. Since the machine is deterministic and $(0,0)$ is terminal, halting at $(0,0)$ is equivalent for the two ends of every instruction edge. Therefore ${\varphi }_i$ and ${\phi }_j$ map these intersections onto the corresponding intersections in their targets. The same assertion holds on the integer lattices after declaring pairs with a negative coordinate nonhalting: the bounds on $a,b,c$ imply that each coordinate's sign is preserved by a transition and its inverse.

Apply Britton's lemma to a word in $B_H$ which represents an element of $K$. If it has stable letters, it must have a pinch. The base coefficient of that pinch lies in $T_H$ and an associated subgroup, and the intersection property just proved makes its transported image lie in $T_H$ again. Successive pinch removals therefore keep all base coefficients in $T_H$, and eventually remove every stable letter. It follows thatFinally, $t=t(0,0)$ belongs to $T_H$, so $L\subseteq B_H$. In the opposite direction, induction backwards along any computation ending at $(0,0)$ shows that every halting basis element lies in $L$: if $t(r^{\prime },s^{\prime })$ for the next configuration is in $L$, then the transition identity expresses $t(r,s)$ as $r_{i}t(r^{\prime },s^{\prime })r_i^{-1}$ or ${\ell }_{j}t(r^{\prime },s^{\prime }){\ell }_j^{-1}$. Thus $B_H=L$ andBecause $T_H$ is generated by a subset of a free basis of a group of $T_K$, a single basis element $t(r,s)$ belongs to it exactly when $(r,s)$ is a halting index. This proves the boxed relationship.

We construct the output presentation explicitly, using HNN extensions and an amalgamated free product. Throughout, $P$ also denotes the group given by the input finite group presentation, and $X=\{x_1,\dots ,x_n\}$. Every word introduced below is a literal computable word in the displayed generators; testing whether $w=1$ is never part of the construction.

First fix the auxiliary Higman groupWe need two facts: $⟨a_1,a_3⟩$ is a free group of rank two, and the normal closure of $a_1$ is $Q$. The latter follows immediately from the relations: setting $a_1=1$ forces successively $a_2=a_2^2$, $a_3=a_3^2$, and $a_4=a_4^2$, hence all three are $1$.

Here is a normal-form verification of the first fact. The three-generator groupis an amalgamated free product of two Baumslag-Solitar groups $BS(1,2)$ along their infinite cyclic subgroups generated by $a_2$. Their base cyclic groups embed by Britton's lemma, so this amalgamation is legitimate. Nonzero powers of $a_1$ in the first factor lie outside $⟨a_2⟩$, as shown by the homomorphism recording the exponent of its stable letter $a_1$. Nonzero powers of $a_3$ in the second factor also lie outside $⟨a_2⟩$: the stable-letter exponent map first forces a putative equality $a_3^r=a_2^s$ to have $s=0$, and then injectivity of the base cyclic group forces $r=0$. The normal form theorem for an amalgamated free product therefore makes $⟨a_1,a_3⟩$ a rank-two free group in $Q_{123}$.

The same argument applies to $Q_{341}$, formed from the other two cyclic conjugation relations. The full $Q$ is $Q_{123}{\ast }_{⟨a_1,a_3⟩}{Q}_{341}$, so that rank-two free group embeds in $Q$ as well. In particular $a_1$ has infinite order.

Now take the free productand setIntroduce $n+2$ letters $u_0,\dots ,u_{n+1}$, and define the finite presentationFinally impose the Higman relations and identifyThus the algorithm outputsThe symbols $c,C,g_j$ in this display are abbreviations for the explicit words above, not extra generators. Renaming the finitely many new generators to avoid $X$ makes this a uniform effective construction.

If $w=1$ in $P$, its image is the identity in the output group, so $c=1$. The equations $u_j^{-1}c{u}_j=g_j$ then give $z=d=1$ and $x_{i}z=1$ for every $i$, hence $x_i=1$. Therefore $C=1$, and the relation $C=a_1$ gives $a_1=1$. Since the normal closure of $a_1$ is $Q$, every $a_i$ is $1$. The remaining identifications make every $u_j$ equal to $1$ as well. All output generators vanish, provingThis proves collapse even when the original group $P$ itself is nontrivial.

Let $S$ be a nontrivial simple group inside a finitely presented group $P$, and fix $a\ne 1$ in $S$. For an input word $w$ in $S$, enumerate products of conjugates in $P$ of $w^{\pm 1}$ and proofs in $P$ that such a product equals $a$. This search terminates exactly when $w\ne 1$: the normal closure of a nontrivial element of $S$ is all of $S$, and its conjugators are also elements of $P$, while a null word has only trivial conjugates. Run this search alongside the enumerable proofs that $w=1$. Exactly one search terminates, solving the word problem for a group on any specified finitely generated subgroup of $S$. No effective generating set for the possibly infinitely generated $S$ is needed.