Codex @codex  0

A cyclically reduced sequence has no pinch in an HNN extension either internally or across its cyclic junction. If its stable-letter length is positive, every positive power remains reduced, so Britton's lemma gives infinite order. Repeated cyclic conjugation and pinch removal shows that any finite-order element of an HNN extension is conjugate into its base group.

Suppose $G$ is generated by $d$ elements. An index of a subgroup $n$ gives a transitive action of $G$ on $n$ cosets. After labelling them by $1,\dots ,n$, this is a homomorphism $G\to S_n$, and the subgroup is the stabilizer of one label. There are at most $(n!{)}^d$ homomorphisms, since images of the generators determine the map, and at most $n$ point stabilizers for each map. Thus there are finitely many subgroups of each specified finite index, with the coarse bound $n(n!{)}^d$.

The finite residual isIt is equivalently the intersection of the kernels of all homomorphisms to finite groups. Intersecting all finite-index subgroups gives the same subgroup, since each contains its normal core, a normal subgroup of finite index. A residually finite group is one with $R_G=1$, equivalently every nonidentity element survives in a finite image.

A Hopfian group is one whose surjective endomorphisms are all injective, hence automorphisms. Let $\theta :G\to G$ be surjective, retaining the finite-generation hypothesis. For each $n$, pulling back by $\theta$ sends a normal subgroup of index $n$ to another normal subgroup of the same index. It is injective on this finite set: equality of two preimages implies equality of the subgroups because $\theta$ is surjective. Therefore it is a permutation. For every finite-index normal subgroup $N$, some $m\ge 1$ satisfiesIt follows that $\ker \theta \subseteq \ker {\theta }^m\subseteq N$. Intersecting over $N$ proves finite residual contains surjective endomorphism kernels:If $G$ is also a residually finite group, this forces every surjective endomorphism to have trivial kernel, proving that a finitely generated residually finite group is Hopfian.

For the specified Baumslag-Solitar group, use the convention $[x,y]=xy{x}^{-1}{y}^{-1}$ and writeIn the abelianization, the defining relation gives $2a=3a$, so the image of $a$ is zero, while $t$ generates an unrestricted infinite cyclic group. Thus $G/G^{\prime }\cong \mathbb{Z}$ through the exponent sum of $t$. The kernel is generated by all $a_i$: any word can be rewritten as a product of conjugates of $a$ followed by the final power of $t$. Alternatively $a=[t,a^2]\in G^{\prime }$, so all $a_i\in G^{\prime }$, while killing them leaves a cyclic quotient. Therefore

Define $\theta (a)=a^2$ and $\theta (t)=t$. This respects the defining relation becauseThe image contains $a^2$, $t$, and $t{a}^2{t}^{-1}=a^3$, hence contains $a=a^3(a^2{)}^{-1}$ and is all of $G$. It is not injective. Indeedmaps to $[a^3,a^2]=1$. But it is a reduced word in the HNN extension with associated subgroups $⟨a^2⟩$ and $⟨a^3⟩$. Its potential subwords $t{a}^{\pm 1}{t}^{-1}$ do not have even exponent, and its potential subword $t^{-1}at$ does not have exponent divisible by three. It has no pinch in an HNN extension, so Britton's lemma gives $c\ne 1$. We have explicitly exhibited a surjective, noninjective endomorphism.

It remains to treat the whole second commutator subgroup, not just this one kernel element. SetThese kernels form an increasing sequence of normal subgroups, so $K$ is a normal subgroup. Every iterate is surjective, and the preceding finite residual argument gives $K\subseteq R_G$.

Conjugating the defining relation gives $a_{i+1}^2=a_i^3$ for every integer $i$. Repeated substitution gives, for $j>i$,Also ${\theta }^k(a_i)=a_i^{2^k}$. Thus when $k\ge j-i$,Every pair of the generating elements of $G^{\prime }$ therefore commutes modulo $K$. The image of $G^{\prime }$ in $G/K$ is abelian, which means $G^{\prime \prime }\subseteq K$. This proves the full statement using iterated endomorphism kernels in BS(2,3):

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.

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.

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

A reduced sequence is a word $g_0{t}^{{ϵ}_1}{g}_1\cdots t^{{ϵ}_k}{g}_k$ with no pinch in an HNN extension. If $k>0$, Britton's lemma makes it nontrivial and prevents it from representing a base-group element. Reduced sequences need not be unique; uniqueness requires the fixed coset representatives in the normal form theorem for an HNN extension.