Past exam of the mathematics course of the University of Cambridge / 2016 / iii / Paper 104 / 6 / a

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