Codex @codex  0

The identified involution is $z=g^2=h^5$. It is central: it commutes with $g$ because it is a power of $g$, and with $h$ because it is a power of $h$. We use the normal form theorem for an amalgamated free product: the two factors embed, an alternating product of elements outside the amalgamated subgroup is nonidentity, and fixed coset representatives give a unique reduced expression. Here choose representatives $1,g$ in the first cyclic group and $1,h,h^2,h^3,h^4$ in the second.

An effective expression from the normal form theorem for an amalgamated free product iswhere each $x_j$ is a nonidentity representative and successive representatives come from different factors. Reduce powers by $g^u=z^{\lfloor u/2\rfloor }{g}^{u\mathrm{mod}2}$ and $h^v=z^{\lfloor v/5\rfloor }{h}^{v\mathrm{mod}5}$, using these identities for negative integers too. Move the central $z$ factors left and reduce their total exponent modulo two. Whenever adjacent representatives come from one factor, multiply them, split off their $z$ contribution, and delete a resulting identity. Each such combination reduces the number of representatives, so the procedure terminates. By the normal form theorem for an amalgamated free product, the input is trivial exactly when $\boxed{r=0\text{ and }\epsilon =0}$. In particular $z\ne 1$ because each factor embeds. This gives the soluble word problem in finite cyclic amalgams algorithm without merely asserting that a normal form exists.

In the specified quotient, the extra relator makes $g,h$ commute. Put $t=g{h}^{-2}$. Its abelian group presentation givesConversely $g\mapsto s^5$, $h\mapsto s^2$ satisfy every quotient relator in $C_{20}=⟨s\mid s^{20}=1⟩$, and send $t$ to $s$. Thus the quotient is exactly $C_{20}$, rather than just a cyclic group of order dividing twenty. If $M,N$ are the exponent sums of $g,h$ in the input, its quotient word problem is

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.

Let $n=[G:H]<\infty$. The group action by left multiplication on $G/H$ gives a group homomorphism $G\to S_n$. Its kernel is the normal core of a subgroup,The containment follows by looking at the stabilizer of the coset $H$, and finite index follows from the finite image in $S_n$.

The Higman group isIt is visibly a finitely presented group. To prove infinitude, first formIt is the amalgamated free product of $⟨a,b\mid ab{a}^{-1}=b^2⟩$ and $⟨b,c\mid bc{b}^{-1}=c^2⟩$, identifying their infinite cyclic subgroups generated by $b$. Each factor is an HNN extension of an infinite cyclic group, so its base and stable letter both have infinite order. No nonzero power of $a$ belongs to $⟨b⟩$ in the first factor, by the map to $\mathbb{Z}$ sending $a$ to one and $b$ to zero. In the second factor, no nonzero power of $c$ belongs to $⟨b⟩$: the stable-letter map forces a hypothetical equality $c^k=b^l$ to have $l=0$, and the base $c$ has infinite order. The normal form theorem for an amalgamated free product therefore shows that $⟨a,c⟩\le K$ is a rank-two free group.

Similarly,contains $⟨c,a⟩$ as a rank-two free group. Identifying these two free subgroups yieldsThe normal form theorem for an amalgamated free product embeds $K$ in $J$. In particular, $J$ contains a free group of rank two and is infinite.

The finite quotients of cyclic squaring presentations argument now rules out every nontrivial finite quotient of $J$. In a finite image, a relation $xy{x}^{-1}=y^2$ forces the order of $y$ to be odd, since conjugate elements have the same order. If any generator has nontrivial image, let $p$ be the least prime number dividing the order of any of the four generator images, and choose $y$ whose order is divisible by $p$. Its predecessor $x$ conjugates it to its square. If $r$ is the order of $x$, iterating conjugation gives $2^r\equiv 1(\mathrm{mod}p)$. Hence the multiplicative order of $2$ modulo $p$ divides $r$. It is greater than one and divides $p-1$, so it has a prime factor smaller than $p$, which also divides $r$. This contradicts the minimal choice of $p$. Thus all four generator images are trivial. $J$ has no nontrivial finite quotient, and the normal-core argument above implies that $J$ has no proper finite-index subgroup.

For the final argument, Conjugation preserves the order of an element. Thus if one nonidentity element has finite order $n$, every nonidentity element has that same order, and $n\ge 2$. Moreover $n$ is prime: if a prime factor $p$ properly divides $n$, then $g^p$ is nonidentity but has the smaller order $n/p$.

When $n\ge 3$, the element $g^2$ is nonidentity, so choose $x$ with $xg{x}^{-1}=g^2$. The conjugator is not the identity, since $g^2\ne g$, and therefore $x^n=1$. Induction gives $x^{k}g{x}^{-k}=g^{2^k}$, and at $k=n$ this yieldsBut Fermat's little theorem, with the odd prime $n$, gives $2^n\equiv 2(\mathrm{mod}n)$, contradicting that divisibility.

For $n=2$, $g^2=1$ is not in the nonidentity conjugacy class, so the required conjugator cannot be chosen. Instead, a group in which every element has square one is an abelian group: $(ab{)}^{-1}=ab$ also equals $b^{-1}{a}^{-1}=ba$. In an abelian group every conjugacy class is a singleton, so one nonidentity class permits only one nonidentity element, giving a group of order two. This contradicts infinitude. Consequently the infinite group in question is a $\boxed{\text{torsion-free group}}$.

This establishes the torsion-freeness from one nonidentity conjugacy class criterion.

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.

Suppose $w\ne 1$ in $P$. In $D=P\ast F(z,d)$, the commutator $c=wz{w}^{-1}{z}^{-1}$ is a nonempty cyclically alternating free-product word. Every positive power remains reduced, so $c$ has infinite order. Each $g_j$ also has infinite order: this is immediate for $z,d$; if $x_i=1$, then $x_{i}z=z$, and otherwise $x_{i}z$ is a cyclically alternating word of length two.

Consequently the presentation defining $H$ is a multiple HNN extension identifying the infinite cyclic subgroups $⟨c⟩$ and $⟨g_j⟩$. By the normal form theorem for an HNN extension, $D$ embeds in $H$.

The subgroupis a free group on exactly these $n+3$ elements. For a proof, view $D$ as $(P\ast ⟨z⟩)\ast ⟨d⟩$. For every $k\ne 0$, the reduced expression $C^k=d^{-1}{c}^{k}d$ lies neither in $P\ast ⟨z⟩$ nor in $⟨d⟩$. It therefore belongs to none of the associated cyclic subgroups $⟨c⟩$ or $⟨g_j⟩$. Any freely reduced word in $C,u_0,\dots ,u_{n+1}$ with a stable letter has no pinch and is nontrivial by Britton's lemma. A word with no stable letters is a nonzero power of $C$, also nontrivial. This proves the claimed free basis of a group.

Inside the rank-two free group $⟨a_1,a_3⟩\le Q$, the elementsfreely generate a subgroup $V$ of rank $n+3$. This is the same free-product normal-form calculation as for the conjugate basis in Question 5: between conjugates with distinct indices, a nonzero power of $a_3$ remains. The identifications in the output presentation give an isomorphism $U\to V$ matching these free bases. HenceThe normal form theorem for an amalgamated free product makes both factors embed. Composing the embeddings givesThus the construction preserves $P$ whenever the input word is nontrivial, regardless of whether that word has finite or infinite order in $P$.

The normal form theorem for an amalgamated free product says that, after choosing left coset representatives for $C$ in $A$ and $B$, each element of $A{\ast }_{C}B$ has a unique normal form consisting of an initial element of $C$ followed by an alternating word in nontrivial representatives from the two factors. In particular, every nonempty reduced alternating word whose syllables lie outside $C$ is nonidentity.

For the free product $A\ast B$, the amalgamated subgroup is trivial. Henceis nontrivial whenever, after omitting a possibly empty initial or final syllable, every displayed $A$-syllable and $B$-syllable is nonidentity. It is then a nonempty reduced normal form.

Map both $a$ and $b$ to the nonidentity element of $C_2$. Both relators $a^2,b^2$ map to the identity, so this gives a homomorphism $D_{\infty }\to C_2$. A word of length $n$ maps to the parity class of $n$; consequently a null word has even length.

Now let $w$ be a null word of positive even length. Interpreting $a^{-1}=a$ and $b^{-1}=b$, the free-product normal form theorem says that a nonempty alternating word cannot be trivial. Thus $w$ has two adjacent equal letters. Delete this $a^2$ or $b^2$, using one conjugate of a defining relator, and apply induction to the resulting null word of length $n-2$. This gives

Use the amalgam from part (c), with edge groupAn odd power of $a$ belongs to $A\setminus C$, because $C$ is the index-two translation subgroup of the Klein bottle group $A$. Similarly, an odd power of $c$ belongs to $B\setminus C$. Thusis a reduced alternating word whose syllables lie in $A\setminus C$ and $B\setminus C$. The normal form theorem for an amalgamated free product says that every nonempty reduced alternating word is nonidentity. The displayed element is therefore nontrivial for every $n\ge 1$.

An amalgamated free product of finite cyclic groups has an effective normal form theorem for an amalgamated free product: multiplication, subgroup membership and subgroup identifications are finite table operations. Replacing an amalgamated syllable by its image in the neighbouring factor and combining adjacent syllables from one factor strictly decreases syllable count. A remaining alternating product outside the amalgamated subgroup is nonidentity. This supplies a terminating word problem for a group algorithm.