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

Let $\pi :G\to G/K$ be the quotient group homomorphism. Its restriction to $X$ is injective because its kernel there is $K\cap X=\{1\}$. Since $g\in K$, $\pi (x_{i}g)=\pi (x_i)$ for every generator. Let $F_n$ be the abstract free group on letters $a_1,\dots ,a_n$ and define the surjective group homomorphism $\alpha :F_n\to ⟨x_{1}g,\dots ,x_{n}g⟩$ by $\alpha (a_i)=x_{i}g$. If $w\in \ker \alpha$, thenInjectivity on $X$ implies $w(x_1,\dots ,x_n)=1$ in $X$. Those elements are a free basis of a group, so $w$ is the empty reduced word in $F_n$. Thus $\ker \alpha =\{1\}$. This is freeness detected by a quotient, and proves

The class-two qualifier is essential: the presentation is in the variety of two-step nilpotent groups, so ${\gamma }_3(G)=1$ is included. Use the group commutator convention $[a,b]=a^{-1}{b}^{-1}ab$ and put $c=[x,y]$. Centrality and the allowed commutator identities give $[x^3,y]=c^3$, so an ordinary finite presentation of the same group isThe commutator subgroup is generated by $c$: modulo it the two generators commute, and centrality makes its normal closure simply its cyclic subgroup. To prove that $c$ has exactly order three and that no hidden relations remain, construct the group on triplesThe bilinear cross term makes multiplication associative: both bracketings contribute $-a^{\prime }b-a^{\prime \prime }b-a^{\prime \prime }{b}^{\prime }$ to the last coordinate. The identity is $(0,0,0)$ and the inverse is $(-a,-b,-r-ab)$. The elements $X=(1,0,0)$ and $Y=(0,1,0)$ have central commutator $(0,0,1)$ of order three, and generate $E$.

Conversely $yx=xy{c}^{-1}$ permits word collection in a two-step nilpotent group, expressing every element as $x^a{y}^b{c}^r$ with $r$ taken modulo three. The map $x\mapsto X$, $y\mapsto Y$, $c\mapsto (0,0,1)$ sends that collected word to $(a,b,r)$. Equality of such coordinates is therefore necessary as well as sufficient. This proves the unique normal form and the requested finite presentations:To solve the word problem for a group, first total the exponents of $x$ and $y$; they give the quotient coordinates $a,b$. If either is nonzero, the word is nonidentity. For the central coordinate, scan the word maintaining $(a,b,r)$ initially zero. Reading $x^{\epsilon }$ changes $(a,r)$ to $(a+\epsilon ,r-\epsilon b)$, while reading $y^{\epsilon }$ changes $b$ to $b+\epsilon$, with $\epsilon =\pm 1$. Reduce $r$ modulo three. HenceFor example, $[x^2,y][x,y]=c^{2}c=1$, whereas $y{x}^2{y}^{-1}{x}^{-2}=c^{-2}=c\ne 1$. Both examples have zero abelian quotient coordinates; the second finite presentation detects their different central coordinates. The displayed one-relator presentation without the class-two laws would be a different group.

All three generators commute, so the group is the abelian group ${\mathbb{Z}}^3$ modulo the integer relation lattice generated by $(2,6,0)$ and $(1,2,2)$. Thus $x^m{y}^n{z}^k=1$ exactly whenEliminating $a,b$ gives $6m-2n-k=0$, and $n=6a+2b$ is even. Conversely, if $n$ is even and $k=6m-2n$, take $a=n/2-m$ and $b=3m-n$; these are integers and reproduce all three coordinates. ThereforeOne can also see the invariant factors directly. The second relation gives $x=y^{-2}{z}^{-2}$. Substitution into the first gives $y^2{z}^{-4}=1$. Put $t=y{z}^{-2}$; thenThe two presentations are equivalent by the explicit substitutions in both directions, so this is not just a quotient guess. An arbitrary input word is first converted, using commutativity, to its exponent totals $m,n,k$. Its coordinates are $(n\mathrm{mod}2,k+2n-6m)$, giving a terminating word problem for a group algorithm.

The allowed algebraic characterization is the Boone-Higman theorem:The simple group $S$ need not itself be finitely presented. The primary statement is Theorem I of An algebraic characterization of groups with soluble word problem. In particular, a finitely generated group with insoluble word problem for a group cannot embed in any finitely presented simple group: otherwise take that group as both $S$ and $P$ in the characterization.

Use the following effective form of the permitted Messuage lemma for groups. Given a finite group presentation of $K$ and a word $w$, one can algorithmically write a finite presentation $K_w$ such that $w=1$ in $K$ implies $K_w=1$, while $w\ne 1$ implies that $K$ embeds in $K_w$. The construction is performed without first deciding whether $w$ is trivial. A collapse-and-embedding lemma with these properties is also stated as Lemma 5.13 in Combinatorial Group Theory. No proof of that allowed lemma is needed here.

Fix a finitely presented group $U$ with insoluble word problem for a group, whose existence is allowed. For each input word $w$ in its generators, construct $U_w$ by the lemma and then form the finite presentation ofIf $w=1$, then $P_w\cong C_2$, which is a nontrivial simple group. If $w\ne 1$, the lemma embeds $U$ in $U_w$, and the normal form theorem for a free product embeds $U_w$ in $P_w$. If $P_w$ were simple, it would be a finitely presented simple group containing $U$, contradicting the characterization. HenceAn algorithm deciding simplicity from arbitrary finite presentations would therefore solve the insoluble word problem for a group in $U$. This proves simplicity of finitely presented groups is algorithmically undecidable. Using $C_2$ avoids any convention about whether the trivial group is called simple.

Use a deterministic single-tape Turing machine with finite tape alphabet $A$ containing a blank symbol $B$, and finite control states. Its instruction of a Turing machine has the formIt reads $a$, writes $b$, changes state, and moves the head left, right, or stays. An instantaneous description of a Turing machine records the state, scanned position, and tape contents; cells outside the finite recorded window are blank. The initial description places the head at the first input symbol, or at a blank for an empty input. A tape infinite in both directions is used here; extending the recorded window does not change its infinite blank surroundings.

Introduce a dedicated halting state $q_H$ and replace every undefined transition by a stay instruction to $q_H$, retaining the scanned symbol. Give $q_H$ no instructions. This effective normalization changes only the final bookkeeping step, not whether the original machine halts. Keep its initial state $q_1$ and tape alphabet unchanged. State letters, tape letters, and the new symbols $h,q$ are mutually disjoint.

Represent a finite description by the wordThe head scans the first letter of $v$ if there is one; if $v$ is empty it scans an implicit blank just beyond the recorded right end. The letters of $u$ are in left-to-right order, and the remaining right-hand letters follow the scanned cell. The markers bound a window, not walls of the physical tape. Thus the input is represented exactly by $h{q}_{1}wh$, including $w$ empty.

Define the semigroup simulation of a Turing machine by taking generators $A$, all state letters, $h$, and $q$, with the following finite list of defining equalities. For each ordinary instruction, use its row below; in a left-move row add the first relation for every $c\in A$:These are the cases where a scanned cell is explicitly present. For the instructions reading $B$, add boundary cases when the right-hand word is empty:A left move at the recorded left end supplies a new scanned blank $B$; a right move at the right end can keep the next blank implicit. Each equality can be checked by reading the new scanned cell and written symbol. For instance $c{q}_{i}a=q_{j}cb$ leaves the head scanning $c$, with the just-written $b$ to its right. Every transition is one of these local substitutions, including either finite-window boundary case.

Finally add only the terminal cleanup equalitiesThere are finitely many generators and relations, and every side is a nonempty word. Thus these equations define a finite semigroup presentation $\gamma (T)$, not merely a rewriting program. In particular, its equalities may be used in either direction.

If $T$ halts on $w$, the simulated forward computation takes $h{q}_{1}wh$ to some $hu{q}_{H}vh$. The cleanup relations remove $u$ and $v$, then $h{q}_{H}h=q$. This proves the forward implication.

For the converse, equality in a semigroup presentation is witnessed by a finite sequence of replacements in contexts, in either direction. Before the first cleanup relation is used, every word reached from $h{q}_{1}wh$ is still a valid description: it has exactly two outer $h$ markers, exactly one state letter, tape symbols between them, and nothing outside. The transition equalities and their inverses preserve this form. A forward transition sends its interpreted configuration $C$ to its unique successor $D$. Since the machine is deterministic, $C$ eventually halts if and only if $D$ eventually halts. Consequently eventual halting is invariant even when such an equality is traversed backward; no reversibility hypothesis on the machine is needed.

Any first cleanup replacement must already encounter $q_H$. The inverse erasure rules also require $q_H$, and the inverse acceptance rule requires $q$, which cannot appear before an acceptance replacement. Therefore a derivation reaching the one-letter word $q$ first reaches a description in state $q_H$ using only simulation equalities. Halting invariance along this initial part of the derivation implies that the original input configuration halts. ThusThe converse proof is what prevents arbitrary inverse uses of the defining relations from becoming spurious halting certificates.

Let $m$ be the order of a group element $g$, allowing $m=\infty$. For finite $m$, take $C=⟨a\mid a^{nm}=1⟩$; for infinite $m$, take $C=⟨a\mid ⟩\cong \mathbb{Z}$. SetThe normal form theorem for a free product embeds both factors, so $G$ is a free factor. The cyclic subgroup $A=⟨a^n⟩$ has order $m$, just as $D=⟨g⟩$ does. Hence $a^{nr}\mapsto g^r$ is a well-defined group isomorphism $A\to D$, and we may form the HNN extensionThe single displayed conjugacy relation implements the full cyclic isomorphism by taking integer powers. Britton's lemma embeds $G_1$ in $H$, so the original $G$ is preserved. Now takeCancellation of successive $t{t}^{-1}$ gives $h^n=t^{-1}{a}^{n}t=g$. This proves the adjoining a root by an HNN extension construction and all required embedding claims. If $g=1$, then $m=1$, $C=C_n$, and $A=D=\{1\}$; the HNN relation is vacuous and the same calculation gives $h^n=1$. The construction also works for $n=1$. It uses the actual order of $g$ as an existence parameter, not an algorithm for determining an unknown order.

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.

First prove the torsion in an HNN extension statement directly from Britton's lemma. Let $z$ have finite order in an HNN extension of $G$. Among its conjugates, choose a reduced normal-form word with the smallest possible number $k$ of stable letters. If $k=0$, that conjugate lies in the embedded base $G$, so its finite order and the base's torsion-free group property force it to be the identity.

Suppose instead that $k>0$. There are no internal pinches in an HNN extension because the word is reduced. There is also no pinch at the join of its end with its beginning. Indeed, write it as $g_0{t}^{{\epsilon }_1}{g}_1\cdots t^{{\epsilon }_k}{g}_k$ and conjugate off $g_0$ to obtain $t^{{\epsilon }_1}{g}_1\cdots t^{{\epsilon }_k}(g_k{g}_0)$. If the joined subword $t^{{\epsilon }_k}(g_k{g}_0)t^{{\epsilon }_1}$ were a pinch, its two signs would be opposite; conjugating by $t^{{\epsilon }_1}$ and using the pinch relation would reduce the stable-letter count by two, contradicting minimality. Thus every positive power is reduced with exactly $rk$ stable letters in the $r$th power. Britton's lemma makes every such power nonidentity, contradicting finite order. We have provedThe base embeds by the same lemma, so finite order has not been lost or artificially introduced by a quotient.

For the countable torsion-free embedding with two conjugacy classes, start with $G_0=G$. Given a countable torsion-free $G_j$, list all ordered pairs $(a,b)$ of its nonidentity elements. Both elements have infinite order, so the assignment $a^r\mapsto b^r$ is an isomorphism between their infinite cyclic subgroups. Successively adjoin one stable letter for each pair with relation $t_{a,b}^{-1}a{t}_{a,b}=b$. Each HNN extension embeds the previous group and is torsion-free by the result just proved. Let $G_{j+1}$ be the union after all pairs from $G_j$ have been treated. It remains countable because only countably many generators were added, and torsion-free because any element and any purported finite-order equation occur in a finite stage.

Repeat this whole process: new stable letters and their products must also be included in later pair lists. In the final increasing unionthe original $G$ embeds and torsion-freeness and countability persist. Any two nonidentity elements lie together in some $G_j$ and are conjugate in $G_{j+1}$. Thus every countable torsion-free group embeds in a countable torsion-free group in which all nonidentity elements are conjugate. If the initial group is nontrivial there are exactly two conjugacy classes; for the trivial group the stated condition is vacuous, or one can begin with $\mathbb{Z}$ instead. The listing is set-theoretic; no algorithm for recognizing nonidentity elements is assumed.

False. Take the finite, hence countable, cyclic group $C_6=⟨a\mid a^6=1⟩$. Its elements $a^3$ and $a^2$ have orders two and three. A group embedding preserves the order of every element, whereas conjugate group elements have the same order: $(s^{-1}xs{)}^r=s^{-1}{x}^{r}s$. Therefore their images cannot be conjugate in any containing group. This gives the required obstruction. The torsion-free group hypothesis in Question 5 avoids this conflict of element orders.

False: free rank is not monotone under subgroup embeddings. In fact every finite-rank free group embeds in $F_2$, hence in every $F_m$ with $m>1$. Let $a,b$ freely generate a rank-two subgroup and set $z_i=a^{i}b{a}^{-i}$ for $0\le i<n$.

To prove that these form a free basis of a group for their subgroup, take a nonempty reduced word and combine each maximal run with the same index into a block $z_{i_1}^{e_1}\cdots z_{i_r}^{e_r}$, with $e_j\ne 0$ and $i_{j+1}\ne i_j$. Its expansion isEvery interior $a$ power and every $b$ power is nonzero, so the free reduction leaves a nonempty word. This proves the conjugates of one free generator freely generate property and injectivity of $F_n\to F_m$. In particular,

False. We construct a two-generated countable group that cannot embed in any finitely presented group. Choose a subset $S\subseteq {\mathbb{N}}_{>0}$ which is not a recursively enumerable set, for example a positive-integer coding of the complement of the halting set. Such sets exist because there are only countably many finite programs but uncountably many subsets of the positive integers. On generators $b_i$ indexed by $i\in \mathbb{Z}$, form the possibly infinite-graph Right-angled Artin groupThe shift $\sigma (b_i)=b_{i+1}$ preserves the defining relations and has inverse shift $i\mapsto i-1$, so it is an automorphism. Form the semidirect productIts base embeds by the definition of a semidirect product. Since $b_i=t^i{b}_0{t}^{-i}$, the group is generated by just $b_0,t$ and is countable.

The shift-invariant graph groups encode arbitrary sets construction has the exact testThe forward direction for $n\in S$ is a defining edge relation. If $n\notin S$, kill all vertex generators except $b_0,b_n$. Every defining commutator then either contains a killed generator or is trivial; no relation is imposed between these two retained generators. Thus there is a retraction of $B_S$ onto the rank-two free group on $b_0,b_n$. Their commutator is a nonempty reduced word there, so it is nonidentity in $B_S$ and remains so in $G_S$.

Now suppose $G_S$ embedded in a finitely presented group $P$. Choose fixed words $u,v$ in its finite generators representing the images of $b_0,t$. The null words of $P$ are recursively enumerable: enumerate all finite products of conjugates of its relators and their inverses, then freely reduce. Substituting $u,v$ into $[b_0,t^n{b}_0{t}^{-n}]$ and dovetailing these enumerations for all $n>0$ would enumerate exactly $S$, contradicting its choice. These finitely many image words may be hard-coded; the argument does not require an algorithm finding an embedding. This proves the enumerable identities of finitely generated subgroups obstruction and supplies a concrete construction of the required countable counterexample.

True. Let $G=⟨X\mid R⟩$ and $H=⟨Y\mid S⟩$, using disjoint finite generating alphabets. The direct product of groups has finite presentationThe commuting relations let every word be reordered as a word in $X$ followed by a word in $Y$; the two projections then show that no additional relations within either factor are imposed. For an input word $w$, form its projections $w_X$ and $w_Y$ by deleting all letters from the other factor. Evaluate each projection with the given word problem for a group algorithm for that factor. The product coordinates giveBoth component algorithms halt, so this is a terminating algorithm. No subgroup-membership procedure or comparison between unknown presentations is required.

False. Use the two-generated group $G_S$ constructed in part (iii) for a non-recursively-enumerable $S$. Sending the two free generators to $b_0,t$ gives a surjective group homomorphismThe source is a finitely presented group, with presentation $⟨a,b\mid ⟩$. The target is not finitely presented: if it were, its null words could be enumerated from a finite set of relators, and the tested commutators would enumerate $S$, as proved in part (iii). Thus even a quotient of a rank-two free group need not admit a finite presentation. A quotient by a finitely normally generated kernel would be finitely presented, but the assertion places no such restriction on its kernel.

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.