Past exam of the mathematics course of the University of Cambridge / 2016 / iii / Paper 104 (Infinite Groups and Decision Problems)

The free product $G_1\ast G_2$ is obtained by taking disjoint copies of the elements of the two groups as generators and imposing precisely their internal multiplication relations. Equivalently, if $G_i=⟨X_i\mid R_i⟩$ with disjoint $X_i$, thenA nontrivial free product has both factors different from the trivial group.

The normal form theorem for a free product says that every element has a unique expressionwhere the empty expression represents the identity. The $g_j$ are called syllables in a free product. Thus nonempty alternating products cannot be the identity, and the natural maps of the factors into the free product are injective.

For existence, multiply adjacent syllables from the same factor and delete identity syllables until the word alternates. Each change uses a defining relation and decreases the number of syllables. To establish uniqueness without assuming that these reductions are confluent, let $\mathcal{W}$ be the set of alternating nonidentity syllable sequences, including the empty sequence. For $h\in G_i$, define a permutation $L_h$ of $\mathcal{W}$ by prepending $h$, multiplying into the first syllable if it belongs to $G_i$, and deleting it if that product is the identity; for $h=1$, do nothing.

The multiplication law inside $G_i$ gives $L_h{L}_k=L_{hk}$ for $h,k\in G_i$, and $L_h^{-1}=L_{h^{-1}}$. This can be checked at the first syllable: if a product deletes it, the next syllable belongs to the other factor and is treated as a new first syllable. Hence the defining relations give a group action of $G_1\ast G_2$ on $\mathcal{W}$. An alternating word $g_1\cdots g_r$ sends the empty sequence to its own syllable sequence. Two such words representing the same group element induce the same permutation, and therefore have identical sequences. This proves the normal form theorem for a free product.

The universal property of a free product states that, for group homomorphisms $f_i:G_i\to H$, there is a unique group homomorphism $f:G_1\ast G_2\to H$ extending both. Explicitly,The internal multiplication relations are respected because each $f_i$ is a group homomorphism, so this assignment descends from words to the presented group. Alternatively, multiplication of two normal forms is concatenation followed by precisely those internal relations, which do not change its value in $H$. Uniqueness holds because the two factors generate the free product.

$\boxed{A_5\text{ is not a nontrivial free product}.}$ If $g\ne 1$ and $h\ne 1$ belong to different factors, the powers $(gh{)}^r$ have distinct normal forms of length $2r$. Every nontrivial free product is therefore an infinite group, whereas the alternating group $A_5$ is a finite group of order $60$.

$\boxed{{\mathbb{Z}}^4\text{ is not a nontrivial free product}.}$ In a nontrivial free product, nonidentity elements $g,h$ from different factors satisfy $gh\ne hg$, since these are distinct alternating normal forms. Such a group is not an abelian group, whereas the free abelian group ${\mathbb{Z}}^4$ is abelian.

Eliminate $t$ using $t=xs{x}^{-1}$. The remaining relation $xt{x}^{-1}=s$ becomes $x^{2}s{x}^{-2}=s$, which follows from $x^2=1$. These Tietze transformations giveBoth factors are nontrivial, so this is a nontrivial free product. Conversely, in $C_2\ast ⟨s⟩$ the definition $t=xs{x}^{-1}$ satisfies both conjugation relations, confirming that eliminating $t$ loses no relation.

A topological graph is a CW complex with only zero-dimensional and one-dimensional cells: its vertices form the zero-skeleton, and each edge is a copy of an open interval attached by its two endpoints to vertices, possibly the same vertex. It has the weak topology of a CW complex. A subgraph is a CW subcomplex, obtained by choosing vertices and edges and retaining the endpoints of every chosen edge. Loops and multiple edges are allowed.

A spanning tree is a connected spanning subgraph containing no cycle in a graph. To construct one in any connected topological graph $\Gamma$, consider all acyclic spanning subgraphs, ordered by inclusion; the subgraph with every vertex and no edges is one. The union of a chain is still acyclic, since any cycle uses only finitely many edges and would already occur in a member of the chain. The Zorn lemma therefore gives a maximal such subgraph $\Delta$.

If $\Delta$ were disconnected, a finite edge path in $\Gamma$ between vertices of two of its components would contain an edge joining different components. Adding that edge creates no cycle, contradicting maximality. Thus $\Delta$ is a spanning tree. Fix a root vertex. Each point of $\Delta$ has a unique finite path to the root; give every edge length one and move the point a fraction $s$ of the way along that path at time $s\in [0,1]$. This defines a contraction of a topological space of $\Delta$. On each closed edge times $[0,1]$, the construction takes place in a finite tree and is continuous. Since the interval is a locally finite CW complex, the product with $\Delta$ has the corresponding weak topology of a CW complex, so these restrictions establish continuity globally. ConsequentlyThis argument includes infinite graphs and does not assume local finiteness of $\Gamma$.

If $p:\tilde{\Gamma }\to \Gamma$ is a covering map, take $p^{-1}({\Gamma }^0)$ as the vertices upstairs. Each component of the inverse image of an open edge is an open interval mapping homeomorphically to that edge, because an interval is simply connected. Its parametrization lifts along the closed edge to attach its endpoints to lifted vertices, by path lifting theorem. Small star neighborhoods at vertices are lifted homeomorphically by the covering map, and give exactly the neighborhoods of the resulting topological graph. Thus the cell structure has the topology of the original covering space. The total space may be disconnected, but every component is a topological graph.

The Nielsen–Schreier formula isFor a proof, realize $F_n$ as the fundamental group of the wedge sum of $n$ circles. Construct its connected covering graph with vertices the right cosets $Hg$, and an oriented edge labeled $x_i$ from $Hg$ to $Hg{x}_i$ for each free generator $x_i$. There is exactly one incoming and one outgoing edge of each label at every vertex, which establishes the local covering map property. Reading a word from $H$ ends at its coset, so the closed paths at $H$ give exactly the words in $H$. The induced map of fundamental groups is injective by the homotopy lifting property of a covering map, and its image is $H$.

For index $d$, this covering graph has $d$ vertices and $dn$ edges. A spanning tree in it has $d-1$ edges. The permitted rank formula for a finite connected graph now givesIn particular this proves both freeness and the index formula.

If $n\ge 2$ and $d>1$, then $1+d(n-1)>n$, so a proper finite-index subgroup cannot be isomorphic to $F_n$. For $n=1$, $F_1\cong \mathbb{Z}$, and $d\mathbb{Z}$ is a proper index-$d$ subgroup isomorphic to $\mathbb{Z}$ for every $d\ge 2$. Hence

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.

Substitution sends the defining relation toThus the assignment respects the relator and extends to a group homomorphism $\boxed{\theta :S\to S}$.

The image contains $t$ and $a^2$, hence also $t{a}^2{t}^{-1}=a^3$. It therefore contains $a=a^3(a^2{)}^{-1}$, so it contains both generators of $S$. More explicitly,which proves surjectivity.

For the commutator $c=[a,ta{t}^{-1}]$, the image isThe last equality holds because two powers of the same element commute.

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

We give a finite semigroup presentation using the convention that $s_0$ is blank, the tape is unbounded in both directions, and a transition $\delta (q_i,s_j)=(q_k,s_p,D)$ writes $s_p$ and moves in direction $D$. The Turing machine is deterministic, and the halting state $q_0$ has no outgoing transition. A finite configuration is encoded bywith the head scanning the first symbol of $v$; if $v$ is empty, it scans an implicit blank. Unrepresented cells beyond the boundary markers $h$ are blank. An additional generator $q$ records completed halting and erasure.

The generators of the semigroup are $S\bigsqcup Q\bigsqcup \{h,q\}$. Its relations have the following finite families. For every right-moving transition, includeFor every left-moving transition and every tape symbol $s_{\ell }$, includeIf stationary moves are part of the chosen machine model, include $q_i{s}_j=q_k{s}_p$ for each such move. Include the boundary-padding relations, for every state $q_i$,They supply a blank immediately to the left of the head when needed, or at the right boundary when the current scanned cell was implicit. Finally includeWriting ${\mathcal{R}}_T$ for this displayed list, the answer is the explicit finite semigroup presentationAll relations are between nonempty words; no group inverses or empty-word generator are used. The transition families are finite because the transition table and alphabet are finite, and the padding and erasure families are visibly finite. The declared head convention determines which side of a tape symbol carries a state letter.

If the Turing machine halts on $w$, follow its computation from $h{q}_{1}wh$. A transition at an already represented cell is one of the corresponding relations. At a boundary, first insert the required blank using a padding relation. Thus the computation gives a finite equality derivation to $hu{q}_{0}vh$. Replace $q_0$ by $q$, erase the symbols of $u,v$ using $s_{j}q=q=q{s}_j$, and erase both boundary markers. This proves $h{q}_{1}wh=q$ in the semigroup.

For the converse, equality in a presented semigroup means a finite sequence of contextual replacements using defining relations in either direction. In any derivation from $h{q}_{1}wh$ to $q$, consider the first occurrence of the special symbol $q$. Before it occurs, the erasure relations cannot be used in either direction. Each word therefore still has exactly two markers $h$, exactly one state letter, and the form $hu{q}_{i}vh$. Both directions of a transition relation join configurations linked by one actual machine step; both directions of a boundary-padding relation merely change how much blank tape is represented.

The first occurrence of $q$ must come from $q_0=q$ in the forward direction. Hence the initial configuration is connected, by transitions in either direction and harmless padding, to a configuration in state $q_0$. For a deterministic Turing machine, the property of eventually reaching $q_0$ is invariant along each transition edge: if $C\to D$ is a step, then $C$ halts if and only if $D$ halts, since that step is the unique next step of $C$ and $C$ is not already in the halting state. The same property is unchanged by padding. A finite path of these edges to $q_0$ therefore shows that the initial configuration halts.

ConsequentlyThe invariance argument is necessary because equality in a semigroup presentation allows reversed transitions as well as forward computation steps.

In a direct product of groups, $(a,b{)}^r=(a^r,b^r)$. Thus a finite order for $(a,b)$ makes both coordinate orders finite. Conversely, if their orders are $p$ and $q$, the least positive exponent annihilating both is their least common multiple. Hencewhen both orders are finite; if either coordinate has infinite order, so does $(a,b)$.

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.

The base free product for the group encoding of a modular machine isThe letters $x,y$ generate the first factor, and $t$ generates the second. Let $T_K$ be the kernel of the group homomorphism $K\to ⟨x,y⟩\cong {\mathbb{Z}}^2$ that kills $t$. Thenis a free group with this displayed free basis of a group. Indeed every word in $K$ can be rewritten as a product of such conjugates followed by an element of $⟨x,y⟩$, so they generate the kernel. A freely reduced product of these conjugates is nontrivial by the normal form theorem for a free product: after combining adjacent occurrences of the same conjugate, different successive indices give a nonzero intervening $x,y$-syllable. Thus there is no relation among the proposed basis elements.

For clarity, a modular machine of modulus $m>1$ has at most one instruction for each residue pair $(a,b)$, with $0\le a,b<m$ and $0\le c<m^2$. Its right and left transitions are respectivelyIts halting set at a designated terminal configuration $H_0(\mathcal{M})$ consists of the nonnegative pairs whose forward computation reaches $(0,0)$, including $(0,0)$ itself. These formulas explain the exponents in the associated-subgroup maps below.

For $M>a\ge 0$ and $N>b\ge 0$, defineThe normal form theorem for a free product giveswhere $X,Y,T$ map to $x^M,y^N,t(a,b)$. To see injectivity, expand an alternating word in $⟨x^M,y^N⟩$ and powers of $t(a,b)$. The conjugating $x,y$ factors commute with the lattice syllables, so each intervening nonidentity lattice syllable stays nonidentity in the expanded free-product normal form.

Its intersection with $T_K$ is the free group with basisThis follows by moving all $x^M,y^N$ factors to the right; the zero-exponent lattice remainder characterizes membership in the kernel.

The required isomorphisms are specified on the three generators byandEach source and target has the same presentation $⟨X,Y,T\mid [X,Y]=1⟩$, and each displayed assignment identifies its three abstract generators. Hence these are genuine isomorphisms, not merely maps of generating sets.

On the kernel basis they give exactly the machine transitions:For example, rewrite the first input as $x^{-mu}{y}^{-mv}t(a_i,b_i)x^{mu}{y}^{mv}$ and apply ${\varphi }_i$ to each factor. These identities also hold for negative $u,v$, since they are identities in the groups.

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.

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.

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

An isomorphism-invariant Markov property of finitely presented groups $\rho$ has two finitely presented witnesses: a group $A_{+}$ with $\rho$, and a group $A_{-}$ which cannot embed in any finitely presented group having $\rho$. In symbols,The second condition is an obstruction to embedding, stronger than merely saying that $A_{-}$ itself fails the property.

Let $U$ be a fixed finitely presented group with unsolvable word problem for a group. Form the finitely presented free product $P=U\ast A_{-}$. Given a word $w$ in the generators of $U$, apply part (a) to this $P$ and $w$, and output the finite presentation ofIf $w=1$ in $U$, it is also $1$ in $P$, so $P(w)$ is trivial and $B(w)\cong A_{+}$ has $\rho$. If $w\ne 1$ in $U$, its image stays nontrivial in the free product $P$, and $P$ embeds in $P(w)$. Therefore $A_{-}$ embeds in $B(w)$, which cannot have $\rho$. We have the effective equivalenceAn algorithm recognizing whether an arbitrary finite group presentation has $\rho$ would decide the unsolvable word problem for a group $U$. This contradiction proves the Adian–Rabin theorem: no Markov property of finitely presented groups is algorithmically decidable.

The auxiliary Higman group $Q$ has no nontrivial finite quotients of a group. One can use this permitted property directly, but there is a short verification. In any finite quotient, let $n_i$ be the order of the image of $a_i$. Since conjugation sends $a_{i+1}$ to its square, $n_{i+1}$ must be odd. If some $n_i>1$, choose the least prime number $p$ dividing any $n_i$. It is odd. Conjugation by the preceding generator givesThe multiplicative order of $2$ modulo $p$ is therefore a divisor of $n_{i-1}$. It is greater than one and divides $p-1$ by the Fermat little theorem, so it has a prime divisor smaller than $p$. That prime also divides $n_{i-1}$, contradicting the choice of $p$. Hence every $n_i=1$ and the quotient is trivial.

Given any finitely presented group $P$, form $\hat{P}=P\ast ⟨v⟩$, and apply part (a) to the word $w=v$. This word is nontrivial by the normal form theorem for a free product, so the output $J=\hat{P}(v)$ contains $P$ by the embedding already proved.

To check its finite quotients, let $f:J\to F$ be any group homomorphism to a finite group. The image of the copy of $Q$ is trivial by the preceding property. The identifications $u_j=a_3^{j+1}{a}_1{a}_3^{-(j+1)}$ make all $f(u_j)$ trivial. Thus the equations $u_j^{-1}c{u}_j=g_j$ give, in the image,Since $f(c)=f(z)$, this forces $f(x_i)=1$ for all generators of $\hat{P}$, including $v$. The defining word $c=[v,z]$ then has trivial image, so $f(z)=f(d)=1$ as well. Every generator of $J$ has trivial image. ThereforeThis uses the concrete construction of part (a), not an assumption that arbitrary quotients preserve an embedding of $P$.

Every finitely presented group $P$ embeds in $P\times C_2$ by $p\mapsto (p,1)$. This direct product of groups is finitely presented: combine finite presentations of the factors and add the finitely many cross-commutation relations between their generators. Projection onto $C_2$ gives a nontrivial finite quotient of a group.

Thus no finitely presented $P$ can serve as the forbidden witness $A_{-}$ for this property. Hence