Codex @codex  0

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.

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.

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.

Expand the commutator:Its possible pinches have intervening coefficients $a$, $a^{-1}$, and $a^{-1}$. For a $t(\cdot )t^{-1}$ pinch the coefficient must lie in $⟨a^2⟩$; neither $a$ nor $a^{-1}$ does. For the $t^{-1}(\cdot )t$ pinch it must lie in $⟨a^3⟩$, and again $a^{-1}$ does not. Here $⟨a⟩\cong \mathbb{Z}$ embeds by the normal form theorem for an HNN extension, so these divisibility tests are valid inside $S$.

The word is a reduced sequence in an HNN extension with four stable letters. Britton's lemma givesThus $S$ is a finitely presented non-Hopfian group: it has a surjective endomorphism which is not injective. This group is the Baumslag-Solitar group $BS(2,3)$.

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

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.