Past exam of the mathematics course of the University of Cambridge / 2008 / iii / Paper 2 (Decision Problems in Group Theory)

The identified involution is $z=g^2=h^5$. It is central: it commutes with $g$ because it is a power of $g$, and with $h$ because it is a power of $h$. We use the normal form theorem for an amalgamated free product: the two factors embed, an alternating product of elements outside the amalgamated subgroup is nonidentity, and fixed coset representatives give a unique reduced expression. Here choose representatives $1,g$ in the first cyclic group and $1,h,h^2,h^3,h^4$ in the second.

An effective expression from the normal form theorem for an amalgamated free product iswhere each $x_j$ is a nonidentity representative and successive representatives come from different factors. Reduce powers by $g^u=z^{\lfloor u/2\rfloor }{g}^{u\mathrm{mod}2}$ and $h^v=z^{\lfloor v/5\rfloor }{h}^{v\mathrm{mod}5}$, using these identities for negative integers too. Move the central $z$ factors left and reduce their total exponent modulo two. Whenever adjacent representatives come from one factor, multiply them, split off their $z$ contribution, and delete a resulting identity. Each such combination reduces the number of representatives, so the procedure terminates. By the normal form theorem for an amalgamated free product, the input is trivial exactly when $\boxed{r=0\text{ and }\epsilon =0}$. In particular $z\ne 1$ because each factor embeds. This gives the soluble word problem in finite cyclic amalgams algorithm without merely asserting that a normal form exists.

In the specified quotient, the extra relator makes $g,h$ commute. Put $t=g{h}^{-2}$. Its abelian group presentation givesConversely $g\mapsto s^5$, $h\mapsto s^2$ satisfy every quotient relator in $C_{20}=⟨s\mid s^{20}=1⟩$, and send $t$ to $s$. Thus the quotient is exactly $C_{20}$, rather than just a cyclic group of order dividing twenty. If $M,N$ are the exponent sums of $g,h$ in the input, its quotient word problem is

Use $c=[a,b]=a^{-1}{b}^{-1}ab$. The two defining relators say that $c$ commutes with $a,b$, hence is central. The given group commutator identities giveConsequently a word collection in a two-step nilpotent group algorithm maintains an integer triple $(m,n,k)$, initially $(0,0,0)$. Reading $a^{ϵ}$, with $ϵ=\pm 1$, changes it to $(m+ϵ,n,k-nϵ)$; reading $b^{ϵ}$ changes it to $(m,n+ϵ,k)$. Each step uses the displayed multiplication rule and reads one letter, so it terminates and produces the requested expression.

By the stipulated uniqueness, the word is trivial exactly when $\boxed{(m,n,k)=(0,0,0)}$, which solves its word problem for a group. Moreover the commutator subgroup is $⟨c⟩$: the quotient by $⟨c⟩$ is abelian, and $c$ itself is a commutator. It is central, so the nilpotency class is at most two. Uniqueness also implies $c\ne 1$, since $(0,0,1)$ and $(0,0,0)$ are distinct triples. Hence the exact nilpotency class is $\boxed{2}$.

The primitive recursive functions are the smallest collection containing zero functions, successor $S(n)=n+1$, and coordinate projections, and closed under composition and primitive recursion. The recursion scheme forms $F$ from already constructed functions $G,H$ byConstants follow by composing successor with zero. Define addition, multiplication and exponentiation successively byAt each stage the initial and step functions are compositions of primitive recursive functions already available. Induction on $n$ gives $A(m,n)=m+n$, $M(m,n)=mn$, and $E(m,n)=m^n$, with the recursive convention $0^0=1$. Composition with the second projection now gives

A recursive function $f:{\mathbb{N}}^k\to \mathbb{N}$ is a total computable function: an algorithm halts on every input and returns the specified value. Equivalently it is an everywhere-defined member of the partial recursive functions, obtained from the initial zero, successor and projection functions by composition, primitive recursion and unbounded minimization. In minimization $\mu y[g(\mathbf{x},y)=0]$, the sequential search must find a zero after all earlier tests have been defined; otherwise the result is undefined. The Church–Turing thesis allows the algorithmic formulation here.

A recursively enumerable set $E\subseteq {\mathbb{N}}^k$ is the domain of a partial computable function. Thus an algorithm halts and accepts exactly on members of $E$, and may run forever on nonmembers. Equivalently an algorithm lists exactly its elements, allowing repetition and allowing an empty output for the empty set. To pass from a listing to a membership semidecision, wait for the input to appear. To pass back, use dovetailing on all inputs and list each whose recognizing computation halts. This differs from a recursive set, whose zero-one characteristic function is total recursive and decides both membership and nonmembership.

The halting problem asks whether program $e$ halts on input $x$, given effective codes for both. Suppose a total decision algorithm $H(e,x)$ returned one exactly when that computation halts. Construct a program $D$ which, on input $e$, computes $H(e,e)$ and then loops forever if the answer is one, but halts if it is zero. Let $d$ be the code of $D$. If $H(d,d)=1$, the specification of $D$ makes it diverge, while if $H(d,d)=0$ the same specification makes it halt. Both alternatives contradict correctness. Therefore the halting problem is $\boxed{\text{undecidable}}$. This is a diagonal argument, not merely the observation that individual simulations can run forever.

Let $K=\{e:\text{program }e\text{ halts on input }e\}$. Simulating the specified program semidecides membership, or dovetailing all simulations enumerates $K$, so $K$ is a recursively enumerable set. The same diagonal program rules out a total decision algorithm for $K$. Thus $\boxed{K\text{ is recursively enumerable but not recursive}}$. Encoding a pair $(e,x)$ also gives an enumerable nonrecursive set of all halting program-input pairs.

Suppose $G=⟨g_1,\dots ,g_n\mid R⟩$ has a finite group presentation. Work in the free product $B=G\ast F(a,b)$ and putThe $u_i$ freely generate a subgroup of $F(a,b)$. Indeed, in a reduced word in these conjugates, combine adjacent powers with the same index. Expanding the remaining word leaves nonzero powers of $a$ separated by nonzero powers of $b$, so the normal form theorem for a free product makes it nonidentity. This proves the free conjugate bases in a rank-two free group fact we need.

The group homomorphism $B\to F(a,b)$ killing $G$ sends $v_i$ to $a^{-i}b{a}^i$, including $v_0=b$. These are a free conjugate basis by the same argument with $a,b$ interchanged. A nonempty reduced word in the $v_i$ therefore has nontrivial image and cannot be trivial in $B$. Thus $u_i\mapsto v_i$ extends to an isomorphism between the two rank-$(n+1)$ free groups embedded in $B$.

Adjoin one stable letter implementing this isomorphism:We assume Britton's lemma, including its assertion that the base embeds in this HNN extension, and the factor-embedding assertion of the normal form theorem for a free product. Hence $G\hookrightarrow E$. The presentation is finite, and its relations express every generator in $a,t$:Eliminating $b,g_i$ by Tietze transformations therefore gives a two-generator finite presentation with $\boxed{G\hookrightarrow E=⟨a,t⟩}$. This explicitly constructs the two-generator HNN embedding; it does not rely on an arbitrary two-generator embedding preserving finite presentability.

The Messuage lemma for groups is the following effective collapse-versus-embedding statement: from a finite group presentation for $K$ and a word $w$, one can algorithmically write a finite presentation $K_w$ such that $w=1$ in $K$ makes $K_w$ trivial, whereas $w\ne 1$ makes the specified copy of $K$ embed in $K_w$. It can also be arranged that the image of $w$ normally generates $K_w$. We use this lemma as an assumed construction, as requested; the construction of its presentation does not require deciding which case applies.

Let $P$ be a finitely presented group with insoluble word problem for a group, whose existence is allowed. Set $K=P\ast ⟨z⟩$, with $z$ of infinite order. It is finitely presented, and the normal form theorem for a free product embeds both $P$ and the infinite cyclic factor. Thus an input word $w$ from $P$ is trivial in $K$ exactly when it is trivial in $P$, while $K$ is certainly infinite.

Apply the Messuage lemma for groups to this $K,w$. If $w=1$ in $P$, the constructed group $K_w$ is trivial and hence finite. If $w\ne 1$, it contains $K$ and is infinite. ConsequentlyA hypothetical algorithm deciding infinitude from arbitrary finite group presentations would therefore decide every input word in $P$, a contradiction. There is no such algorithm. The infinite cyclic free factor ensures the reduction does not need an additional assumption about the size of $P$.

The Higman embedding theorem says that a finitely generated group embeds in a finitely presented group if and only if it has a recursive presentation of a group, that is, a presentation on finitely many generators with a recursively enumerable set of relators. We use its embedding direction as an assumed theorem. The reverse direction follows by expressing subgroup generators as words in the larger group and enumerating finite products of conjugates of its relators and their inverses; comparison after free reduction enumerates all null words in the subgroup. This is the enumerable identities of finitely generated subgroups argument. The theorem does not assume that the recursively presented group's word problem for a group is decidable.

Take a recursively enumerable set $S\subseteq {\mathbb{N}}_{>0}$ that is not recursive, for example the diagonal halting set from Question 2 shifted by one. To obtain a finitely generated group with recursive presentation but undecidable word problem for a group, first define the countable Right-angled Artin groupTranslation of the indices gives an automorphism $a_i\mapsto a_{i+1}$. The semidirect product with its infinite cyclic shift is generated by $a=a_0,t$ and has presentationTo verify this presentation, the semidirect product satisfies its relators, while the reverse map sends $a_i$ to $t^{i}a{t}^{-i}$; all translated commutation relations follow by conjugation. These maps are inverse on their generators. Thus $B_S$ embeds in $G_S$.

For $n\in S$, the word $[a_0,a_n]$ is trivial. For $n\notin S$, map $a_0,a_n$ to the free generators $x,y$ of $F(x,y)$ and every other $a_i$ to one. Every defining commutator of $B_S$ maps to one, since the only possible relation involving both surviving generators would have separation $n$, which is absent. The resulting group homomorphism sends $[a_0,a_n]$ to the nontrivial reduced word $[x,y]$. HenceThis proves the shift-invariant graph groups encode arbitrary sets construction rather than supposing that a missing relator automatically means a nontrivial word. A word algorithm for $G_S$ would decide $S$, so none exists. Since $S$ is enumerable, the displayed two-generator presentation is a recursive presentation of a group. By the Higman embedding theorem, $G_S$ embeds in a finitely presented group $G_0$. A word algorithm for $G_0$, composed with substitution of the two fixed generator-image words, would solve the word problem for $G_S$. Therefore $\boxed{G_0\text{ is finitely presented with insoluble word problem}}$.

Write $R=⟨⟨r_j:j\in J⟩{⟩}_F$ and let $\pi :F\to G_0=F/R$ be the quotient group homomorphism. The subgroup in the question is exactly the fiber product of groupsEvery specified generator belongs to the right-hand side, so one inclusion is immediate. For the reverse inclusion, diagonal generator pairs produce $(u,u)$ for every $u\in F$. Alsoso their products and inverses produce $(1,r)$ for every $r\in R$. If $\pi (u)=\pi (v)$, then $u^{-1}v\in R$ and $(u,v)=(u,u)(1,u^{-1}v)\in H$, proving equality.

In particular $\boxed{(1,w)\in H⟺w\in R⟺w=1\text{ in }{G}_0}$. Constructing the input pair $(1,w)$ is effective, so a solution of the membership problem for a subgroup $H\le F\times F$ would solve the insoluble word problem for a group in $G_0$. The subgroup membership problem is therefore undecidable. This is the Mihailova subgroup construction; its finite generating set follows from the finiteness of $X,J$.

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.

A subgroup $H\le G$ is a benign subgroup when there are an embedding of $G$ into a finitely presented group $E$ and a finitely generated subgroup $L\le E$ with $G\cap L=H$. Finite generation is required of $L$, not of $H$ itself. We use Britton's lemma, the normal form theorem for an amalgamated free product, and, for the final quotient assertion, the Higman embedding theorem.

Choose witnesses $E_H,L_H$ and $E_K,L_K$ for $H,K$. The amalgamated free product $P=E_H{\ast }_G{E}_K$ embeds both witnesses and their common copy of $G$. It is finitely presented: take their two finite presentations and add the finitely many equalities identifying the images of a finite generating set of $G$. These equalities identify all elements of $G$, so they present precisely the amalgam. The original intersections $G\cap L_H=H$ and $G\cap L_K=K$ are preserved by the embeddings.

Now form the finitely presented groupOnly finitely many commutation relators, one for each of the chosen subgroup generators, are needed. The subgroup $Q=⟨G,t,s⟩$ is exactly the multiple HNN extension of $G$ centralizing $H$ and $K$. To prove this claim, take a word in $G,t,s$ reduced for those associated subgroups. It remains reduced in $T$: a $t$-pinch with a coefficient in $G$ occurs precisely when that coefficient lies in $L_H\cap G=H$, and an $s$-pinch precisely when it lies in $K$. Britton's lemma therefore prevents any extra relation, and it also embeds $G$.

Write $G^u=u^{-1}Gu$. The subgroup $L_{\cap }=G^{ts}$ is finitely generated. If $s^{-1}{t}^{-1}gts\in G$, Britton reduction must first pinch $t^{-1}gt$, requiring $g\in H$; its value is then $g$. The remaining $s^{-1}gs$ can represent a base element only if $g\in K$, and then its value is again $g$. Conversely every $g\in H\cap K$ commutes with both letters. Henceso the intersection is benign.

For the join, put $J=⟨H,K⟩$ and $L_{\vee }=⟨G^t,G^s⟩$, again finitely generated. The subgroup generated by $G,G^t,G^s$ in $Q$ isIndeed, expanding conjugate-copy syllables as $t^{-1}gt$ or $s^{-1}gs$ shows that the only possible Britton reductions are exactly the identifications in the indicated amalgamations; a reduced amalgam word therefore has no additional way to become trivial.

We use this elementary consequence of amalgam normal forms: if $C\le D\le A$, then inside $A{\ast }_{C}B$ the subgroup $⟨D,B⟩$ is $D{\ast }_{C}B$ and intersects $A$ exactly in $D$. A reduced expression with a $B\setminus C$ syllable cannot lie in $A$, because multiplying it by an inverse base element still leaves a reduced nontrivial amalgam word. Apply this first to $G{\ast }_H{G}^t$ with $D=J$, obtaining $D_1=⟨J,G^t⟩$ and $D_1\cap G=J$. Since $K\le J\le D_1$, apply it again in $U=(G{\ast }_H{G}^t){\ast }_K{G}^s$ to obtain $⟨D_1,G^s⟩\cap (G{\ast }_H{G}^t)=D_1$.

Each element of $H$ lies in $G^t$, and each element of $K$ lies in $G^s$, since the corresponding stable letter centralizes it. Thus $J\le L_{\vee }$, and $L_{\vee }=⟨D_1,G^s⟩$. Intersecting the previous identities with $G$ givesThis proves the intersection and join of benign subgroups construction with actual finitely generated witnesses inside $T$.

Finally let $N◃G$ be benign, witnessed by $N=G\cap L$ in a finitely presented group $E$. Choose finite generators $X$ for $G$ and express both $X$ and a finite generating set for $L$ as words in $E$. Enumerate every word $w$ on $X$, every word $v$ on those generators of $L$, and every finite proof in the presentation of $E$ that their substituted words are equal. Dovetail these searches and list $w$ when such a proof is found. Exactly the words representing elements of $G\cap L=N$ are listed: membership has a finite expression in the generators of $L$, and every valid equality has a finite relator proof. Since $N$ is normal, these are exactly the null words of $G/N$.

Use this enumerable list as relators on the finite alphabet $X$. Its normal closure is precisely the kernel of $F(X)\to G/N$, so it is a recursive presentation of a group for $G/N$. The Higman embedding theorem now yieldsThis is normal benign subgroup quotient embedding; no word algorithm for $E$ or membership algorithm for $L$ was assumed.