Codex @codex  0

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.

First prove the torsion in an HNN extension statement directly from Britton's lemma. Let $z$ have finite order in an HNN extension of $G$. Among its conjugates, choose a reduced normal-form word with the smallest possible number $k$ of stable letters. If $k=0$, that conjugate lies in the embedded base $G$, so its finite order and the base's torsion-free group property force it to be the identity.

Suppose instead that $k>0$. There are no internal pinches in an HNN extension because the word is reduced. There is also no pinch at the join of its end with its beginning. Indeed, write it as $g_0{t}^{{\epsilon }_1}{g}_1\cdots t^{{\epsilon }_k}{g}_k$ and conjugate off $g_0$ to obtain $t^{{\epsilon }_1}{g}_1\cdots t^{{\epsilon }_k}(g_k{g}_0)$. If the joined subword $t^{{\epsilon }_k}(g_k{g}_0)t^{{\epsilon }_1}$ were a pinch, its two signs would be opposite; conjugating by $t^{{\epsilon }_1}$ and using the pinch relation would reduce the stable-letter count by two, contradicting minimality. Thus every positive power is reduced with exactly $rk$ stable letters in the $r$th power. Britton's lemma makes every such power nonidentity, contradicting finite order. We have provedThe base embeds by the same lemma, so finite order has not been lost or artificially introduced by a quotient.

For the countable torsion-free embedding with two conjugacy classes, start with $G_0=G$. Given a countable torsion-free $G_j$, list all ordered pairs $(a,b)$ of its nonidentity elements. Both elements have infinite order, so the assignment $a^r\mapsto b^r$ is an isomorphism between their infinite cyclic subgroups. Successively adjoin one stable letter for each pair with relation $t_{a,b}^{-1}a{t}_{a,b}=b$. Each HNN extension embeds the previous group and is torsion-free by the result just proved. Let $G_{j+1}$ be the union after all pairs from $G_j$ have been treated. It remains countable because only countably many generators were added, and torsion-free because any element and any purported finite-order equation occur in a finite stage.

Repeat this whole process: new stable letters and their products must also be included in later pair lists. In the final increasing unionthe original $G$ embeds and torsion-freeness and countability persist. Any two nonidentity elements lie together in some $G_j$ and are conjugate in $G_{j+1}$. Thus every countable torsion-free group embeds in a countable torsion-free group in which all nonidentity elements are conjugate. If the initial group is nontrivial there are exactly two conjugacy classes; for the trivial group the stated condition is vacuous, or one can begin with $\mathbb{Z}$ instead. The listing is set-theoretic; no algorithm for recognizing nonidentity elements is assumed.

False, even when the HNN extension also has a finite presentation. Take the base $P=F_m\times F_m$ and its Mihailova subgroup $L$ from Question 4(b). Its word problem for a group is soluble: project a word to each free factor and freely reduce both projections, as in part (iv). The base is finitely presented, but the HNN extensionhas insoluble word problem by the explicit reduction in Question 4(b). Namely, for an input word $w$ in the presentation with insoluble word problem, set $p=(1,w)$; thenThe obstruction is undecidable membership in the associated subgroup, not undecidable equality in the base. Soluble base word problem alone does not let one recognize the pinches needed for a normal form theorem for an HNN extension algorithm.

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.

$\boxed{BS(3,4)\text{ is not residually finite}.}$ We exhibit a nonidentity element killed by every finite quotient.

In any finite image, let $r$ be the order of the image of $a$. The relation conjugating $a^3$ to $a^4$ givesThus $\gcd (r,3)=\gcd (r,4)=1$. Since $3$ is invertible modulo $r$, the relation implies that the image of $ba{b}^{-1}$ is a power of the image of $a$. Therefore every finite image kills the group commutatorusing $[s,t]=s^{-1}{t}^{-1}st$.

View $BS(3,4)$ as an HNN extension of $⟨a⟩\cong \mathbb{Z}$, with associated subgroups $⟨a^3⟩$ and $⟨a^4⟩$. A pinch in an HNN extension would be $b{a}^{3j}{b}^{-1}$ or $b^{-1}{a}^{4j}b$. The word $w$ has none: its intervening exponents are $-1,1,1$, incompatible with the required divisibilities $3,4,3$. By Britton's lemma, $w\ne 1$. Hence finite quotients fail to separate this nonidentity element, proving the conclusion.

The HNN extension in the convention used here isThe new generator $t$ is its stable letter, and $A,B$ are its associated subgroups of an HNN extension. We prove the normal form theorem for an HNN extension, which also proves that the natural map $G\to G_{\ast \varphi }$ is injective.

Set $C_{+}=A$, $C_{-}=B$, ${\psi }_{+}=\varphi$, and ${\psi }_{-}={\varphi }^{-1}$. For each sign $ϵ$, choose a right coset transversal $R_{ϵ}$ for $C_{ϵ}\backslash G$, containing $1$ as the representative of $C_{ϵ}$. Thus every $g\in G$ has a unique decomposition $g=cr$, with $c\in C_{ϵ}$ and $r\in R_{ϵ}$. A normal form iswhere $g_0\in G$ is unrestricted and the case $k=0$ is just $g_0$.

Here is a constructive proof. Let $\mathcal{N}$ be the set of these formal sequences. Left multiplication by $h\in G$ changes only $g_0$ to $h{g}_0$. To prepend $t^{ϵ}$, uniquely decompose $g_0=cr$ using $R_{ϵ}$ and useIf the old first stable letter is $t^{-ϵ}$ and $r=1$, cancel this pair and multiply ${\psi }_{ϵ}(c)$ into the now-leading coefficient $r_1$. Otherwise retain the new first stable letter. Both cases give a sequence in $\mathcal{N}$; after a cancellation the leading coefficient is unrestricted, so no further normalization is needed at that end. Prepending the letters of a word from right to left proves existence.

These operations define permutations of $\mathcal{N}$. The base-group operations satisfy $L_h{L}_{h^{\prime }}=L_{h{h}^{\prime }}$. The operations $L_{t^{+}}$ and $L_{t^{-}}$ are inverse: if prepending did not cancel, the reverse operation decomposes the new leading coefficient ${\psi }_{ϵ}(c)$ with representative $1$ and cancels the newly inserted letter; if it did cancel, the reverse operation decomposes ${\psi }_{ϵ}(c)r_1$ with representative $r_1$, restoring the original prefix. The normal-form restriction rules out an unwanted second cancellation in the latter case.

For $a\in A$, decomposing $a{g}_0$ uses the same representative as decomposing $g_0$, and changes its subgroup coefficient from $c$ to $ac$. Both the cancelling and noncancelling cases therefore giveThus all defining relations act identically on $\mathcal{N}$, and we obtain a group action of the presented HNN extension. Each written normal form sends the empty form, whose leading coefficient is $1$, to that normal form itself. Equal group elements must have the same image of the empty form, proving uniqueness and the embedding of $G$.

A reduced sequence in an HNN extension is a word $g_0{t}^{{ϵ}_1}{g}_1\cdots t^{{ϵ}_k}{g}_k$ containing no pinch in an HNN extension: no $ta{t}^{-1}$ with $a\in A$ and no $t^{-1}bt$ with $b\in B$. Equivalently, whenever ${ϵ}_{i+1}=-{ϵ}_i$, one requires $g_i\notin C_{{ϵ}_i}$.

Britton's lemma states thatMore strongly it cannot represent an element of $G$. To prove this from the normal form theorem for an HNN extension, normalize the coefficients from right to left. Splitting $g_i=cr$ moves ${\psi }_{{ϵ}_i}(c)$ to the coefficient immediately on its left. If the preceding stable letter has the opposite sign, this transported factor belongs to the subgroup relevant to that inverse pair; multiplying by it cannot turn a coefficient outside that subgroup into one inside it. If the signs agree, cancellation is impossible anyway. Hence no stable letter disappears during normalization of a reduced sequence. Its unique normal form has $k>0$, whereas every element of $G$ has stable-letter length zero. This proves Britton's lemma. The same proof works with finitely many stable letters, with pinches requiring the same letter and its inverse.

Use a reduced sequence in an HNN extension for $\gamma$. By repeatedly conjugating a prefix to the other end and reducing any resulting pinch, one obtains a cyclically reduced sequence in an HNN extension: either an element of the base group, or a sequence of positive stable-letter length with no pinch even across its cyclic junction. For example, after conjugating away the initial base coefficient, write it as $t^{{ϵ}_1}{g}_1\cdots t^{{ϵ}_k}{g}_k$. A pinch across the junction can occur only if ${ϵ}_k=-{ϵ}_1$ and $g_k\in C_{{ϵ}_k}$. Moving the first stable letter to the end then exposes that pinch and reduces the stable-letter length by two. Iteration must terminate.

If the resulting cyclically reduced sequence has $k>0$, every positive power remains reduced and has stable-letter length equal to that power times $k$. By Britton's lemma, none is the identity. Thus a finite-order element must be conjugate into the base group $G$. Since $G$ embeds in the HNN extension, the order of a base-group element is unchanged, and conjugation also preserves order. ThereforeThe argument also applies to several stable letters: cyclic pinches must involve a stable letter and its own inverse.

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.

Form the HNN extension which centralizes $L$:This is the extension associated to the identity isomorphism $L\to L$; relations on the displayed finite generating set imply $k^{-1}hk=h$ for all $h\in L$. Since $K_{\mathcal{M}}$ is finitely presented and $I,J$ are finite, this is a finite group presentation.

For any $g\in K_{\mathcal{M}}$,The forward implication follows from Britton's lemma: if $g\notin L$, the word $k^{-1}gk{g}^{-1}$ is reduced with two stable letters and cannot be the identity. The reverse implication is the defining centralization relation. Consequently the computable wordsatisfiesAn algorithm for the word problem for a group $G_{\mathcal{M}}$ would therefore decide the nonrecursive set $H_0(\mathcal{M})$, a contradiction. Hence $\boxed{G_{\mathcal{M}}\text{ has unsolvable word problem}}$.

The factors ${\mathbb{Z}}^2$ and $\mathbb{Z}$ are torsion-free groups, and so is their free product $K$. Indeed every element of a free product is conjugate either into one factor or to an alternating word whose first and last syllables lie in different factors. A word of the latter kind has nonempty reduced powers of every positive length, so has infinite order. A nonidentity element of either factor also has infinite order.

By the finite-order result in part (b), every finite-order element of the multiple HNN extension $K_{\mathcal{M}}$ is conjugate into the torsion-free base $K$, and hence is the identity. Apply the same result once more to $G_{\mathcal{M}}$, whose base is $K_{\mathcal{M}}$. It follows thatThus the failure of a word problem for a group to be decidable does not require torsion.

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$.

Introduce $b=t^{-1}at$. The presentation may be written as the HNN extensionof the Baumslag-Solitar group $\mathrm{BS}(1,2)=⟨a,b\mid ba{b}^{-1}=a^2⟩$, with stable letter $t$ identifying the infinite cyclic subgroups $⟨a⟩$ and $⟨b⟩$. Britton's lemma embeds the base group in the HNN extension. In particular, $a$ has infinite order, so $G$ is infinite. It is also nonabelian because $ba{b}^{-1}=a^2\ne a$.

The HNN extension is the Baumslag-Solitar groupIts Bass-Serre tree has vertices $G/⟨u⟩$ and oriented edges $G/⟨u⟩$, with the two endpoint maps induced by the identity embedding and the index-two embedding $n\mapsto 2n$. At each vertex there is one incident edge on the identity side and two on the index-two side. The underlying unoriented tree is therefore infinite and $3$-regular, with an orientation in which every vertex has one incoming and two outgoing edges, up to reversing the convention.

A stable letter is the new generator of an HNN extension which implements an isomorphism between two specified subgroups by conjugation. In the convention $ta{t}^{-1}=\varphi (a)$, it moves elements of the source subgroup $A$ to the target subgroup $B$; using $t^{-1}at=\varphi (a)$ reverses the naming convention.

Every finite-order element of an HNN extension is conjugate to a finite-order element of its base. Choose a conjugate minimizing the number of stable letters. If this number is positive, no pinch is possible either internally or across the end-to-start join, since a boundary pinch would allow a conjugation shortening it. Every positive power is then reduced with positive stable-letter length, and Britton's lemma makes it nonidentity. In particular, an HNN extension of a torsion-free group is torsion-free.

For $G=⟨g_i\mid R⟩$, put $B=G\ast F(a,b)$, $u_0=a$, $v_0=b$, $u_i=b^{-i}a{b}^i$ and $v_i=g_i{a}^{-i}b{a}^i$ for $i\ge 1$. The $u_i$ freely generate by free conjugate bases in a rank-two free group. The $v_i$ do too: projection killing $G$ maps them to a free conjugate basis, so no reduced word in them is trivial. The HNN extension adjoining $t^{-1}{u}_{i}t=v_i$ embeds $G$ by Britton's lemma. Since $b=t^{-1}at$ and $g_i=t^{-1}{u}_{i}t(a^{-i}b{a}^i{)}^{-1}$, its generators reduce to $a,t$. For finitely many $g_i$ and $R$ this is a finite group presentation; for effective countably many generators and enumerable $R$ it is a two-generator recursive presentation of a group.