Codex @codex  0

To adjoin an $n$th root of $g\in G$, let $m$ be the order of a group element $g$ and take a cyclic group $C=⟨a⟩$ of order $nm$ when $m$ is finite, or infinite order when $g$ has infinite order. In the free product $G\ast C$, $⟨a^n⟩$ and $⟨g⟩$ have the same order. The HNN extension with $t^{-1}{a}^{n}t=g$ therefore embeds its base by Britton's lemma, and $h=t^{-1}at$ satisfies $h^n=g$. If $g=1$, take $C$ of order $n$ and identify the two trivial subgroups. This is an existence construction, not an algorithm for finding an unknown element order.

The integer matrices $A=(\begin{array}{cc}1& 2\\ 0& 1\end{array})$ and $B=(\begin{array}{cc}1& 0\\ 2& 1\end{array})$ generate a discrete subgroup. For every nonzero integer $m$, $A^m$ sends $|x|<1$ into $|x|>1$, while $B^m$ sends $|x|>1$, including infinity, into $|x|<1$. The ping-pong lemma identifies their subgroup as the free product of two infinite cyclic groups. This separates the proof of discreteness from the proof of freeness.

For nontrivial groups $A,B$, the free product $A\ast B$ is amenable exactly in the exceptional case $A\cong B\cong C_2$. In that case it is the infinite dihedral group, hence a virtually cyclic group and amenable. In every other case the normal form theorem for a free product and the ping-pong lemma produce a subgroup isomorphic to $F_2$; the fact that a subgroup of an amenable group is amenable then obstructs amenability.

The category of groups has groups as objects and group homomorphisms as morphisms. Its product is the direct product of groups, and its coproduct is the free product, as expressed by the universal property of a free product.

Suppose $P$ has a soluble word problem for a group and $z$ generates an infinite cyclic group. In $P\ast ⟨z⟩$, for $g\ne 1$ the words $gz$ and $[g,z]$ are cyclically reduced with two and four syllables respectively. Their nonzero powers have syllable lengths $2|k|$ and $4|k|$. Given an input's reduced free product form, its length bounds the possible exponents; compare the finitely many candidates using the base word algorithm. Membership and the exponent in each of these infinite cyclic subgroups are therefore computable, with no algorithm for the order of $g$ required.

A finite group presentation has finitely many generators and finitely many relators. It defines the quotient of the free group on $X$ by the normal closure of $R$. Free products of finitely presented groups and HNN extensions along explicitly finitely generated associated subgroups have finite presentations obtained by adjoining finitely many generators and relations.

In $F(a,b)$, any set of distinct conjugates $b^{-i}a{b}^i$ freely generates its subgroup. Combine adjacent powers of the same conjugate in a reduced word. After expansion, distinct successive indices leave nonzero intervening powers of $b$, and the intervening nonzero powers of $a$ cannot cancel in the free product $⟨a⟩\ast ⟨b⟩$. The same argument works with $a,b$ interchanged and for finite or countably infinite sets of indices.

A subgroup $A$ is a free factor of $G$ if $G$ is isomorphic to a free product $A\ast B$ by an isomorphism restricting to the inclusion of $A$, for some subgroup $B$. The normal form theorem for a free product ensures that both factors embed. A free factor need not be a normal subgroup.

A free product $A\ast B$ is nontrivial as a splitting when both factors differ from the trivial group. Alternating words $(ab{)}^r$ with $a,b\ne 1$ in different factors show that every such splitting gives an infinite group. The distinct normal forms $ab$ and $ba$ also show that the group is not an abelian group.

A normal form for free groups and free product of groups represents elements by reduced words. In a free group, adjacent inverse letters cancel; in a free product, alternating nonidentity syllables from different factors are unique. In an amalgamated free product, chosen coset representatives produce the corresponding reduced form relative to the common subgroup.

Every element of a free product $G\ast H$ has a unique expression $u_1\cdots u_n$ in which each $u_i$ is a nonidentity element of one factor and adjacent syllables belong to different factors. The identity corresponds to the empty word.

A normal surface meets each tetrahedron in disjoint disks of the four triangular and three quadrilateral types. Its arcs in a face join distinct edges, each disk meets an edge at most once, and at most one quadrilateral type occurs in a tetrahedron. These last requirements exclude, for example, a disk with an octagonal boundary.

We first establish the surgery operation needed for the sphere system. Suppose a disk $D$ disjoint from the other spheres compresses one sphere $S$. It produces spheres $S^{\prime }$ and $S^{\prime \prime }$. Small parallel copies of the three spheres bound a three-times punctured three-sphere $P$. Denote the old piece on the uncompressed side by $A$, and the two pieces on the compressed side by $B^{\prime }$ and $B^{\prime \prime }$. If both $B^{\prime }$ and $B^{\prime \prime }$ were punctured three-spheres, then $P$ glued to them would also be a punctured three-sphere, contrary to the hypothesis on the original cut manifold. Choose, say, $B^{\prime }$ which is not of this type, and retain $S^{\prime }$ alone in place of $S$.

The other new piece is $A\cup P\cup B^{\prime \prime }$. It too cannot be a punctured three-sphere. If it were, cap its external boundary spheres to make $S^3$. All the spheres separating $A$ from the attached pieces then bound three-balls by the Three-dimensional Schoenflies theorem; the component containing $A$ would be a punctured three-sphere, contradicting the hypothesis on $A$. Thus the sphere surgery preserving nontrivial complementary pieces keeps exactly $k$ spheres and keeps every complementary piece nontrivial. The assumption that all spheres separate ensures that the old and new pieces used here really are distinct sides.

Apply general position to the whole sphere system, avoiding the vertices and making it transverse to edges and faces. We describe a terminating normalization, allowing the replacement operation just proved as well as isotopy. If some component of its intersection with a tetrahedron is not a disk, choose a boundary circle innermost among circles not bounding such disk components. A disk just inside the tetrahedral boundary gives a compression; if intervening disk components occur, first push them into collars of their boundary disks. Perform the compression and retain one new sphere as above. This replaces a non-disk tetrahedral piece by disk pieces without increasing edge intersections. Repetition is finite: every compression divides the original sphere along a separating circle, and the sum of $1-\chi$ over the non-disk planar tetrahedral pieces decreases; disk components can then be put in boundary collars. A closed sphere component wholly in a tetrahedron is impossible, because it would cut off a three-ball, contrary to the complementary-piece condition.

Now each tetrahedral piece is a disk. A face circle innermost in a face allows its incident disk to be moved through that face disk, removing the circle. This reduces the number of face intersections without increasing the edge weight. A returning face arc similarly gives an edge bigon across which the surface can be pushed, reducing the number of edge intersections by two. Restore tetrahedral disk pieces by the preceding operations whenever necessary.

It remains to exclude multiple intersections of a disk with an edge, which the absence of returning face arcs alone does not exclude. Suppose a tetrahedral disk meets an edge twice. Among such disks choose a pair of intersections consecutive on the edge and with no other surface intersection between them. Such a pair exists: an intervening disk crosses the edge interval an even number of times, so passing to an innermost intervening pair eventually gives consecutive points. Join them by an arc in the disk. The disk pieces divide the tetrahedron into three-balls, and this arc together with the edge interval lies in the boundary of one of these three-balls. It therefore bounds a bigon with interior disjoint from the surface. Push across the bigon to reduce edge weight by two. At fixed weight the previous moves reduce face and non-disk complexity; the edge weight itself is a nonnegative integer. Hence the whole process terminates. A final tetrahedral disk meets each edge at most once, and its boundary separates either one vertex from three or two vertices from two. It is respectively a normal triangle or quadrilateral. Thus a normal system of exactly $k$ spheres with the required complementary-piece property exists.

For the finite decomposition, we need a bound on such normal systems, not merely an assertion that they have been normalized. Let $f_2$ be the number of faces of the fixed triangulation. In a triangular face cut by normal arcs, all but at most four complementary regions are rectangles between adjacent parallel arcs. Thus at most $4f_2$ complementary three-dimensional components contain a nonrectangular face region. Every remaining component is assembled from product regions between parallel normal disks, so is an interval bundle whose boundary components are spheres. Its connected base is either $S^2$ or ${\mathbb{RP}}^2$. The product $S^2\times I$ is a punctured three-sphere, and is excluded. The other possibility is the twisted interval bundle over ${\mathbb{RP}}^2$, namely ${\mathbb{RP}}^3$ with a three-ball removed. Each such piece contributes a distinct ${\mathbb{F}}_2$ summand to $H_1(M;{\mathbb{F}}_2)$: gluing along spheres does not identify first-homology classes, by the Mayer–Vietoris sequence. Since $k$ separating spheres give $k+1$ components, we obtain the explicit finite bound

For an arbitrary closed connected $X$, first cut out nonseparating spheres. A neighbourhood of one such sphere together with an arc joining its two sides is a punctured $S^2$-bundle over $S^1$; the bundle is the product or the twisted bundle according to the orientation of the attaching identification. Its complement is connected, so this extracts a connected sum factor. The mod-two first Betti number of the remaining capped manifold decreases by one. Hence only finitely many such extractions are possible. The remaining manifolds have only separating spheres.

Whenever a remaining factor is not a prime three-manifold, split it along a sphere into two factors neither homeomorphic to $S^3$. Viewed in the original remaining manifold, all these successive splitting spheres form a disjoint system whose pieces are not punctured three-spheres. The normalization and bound just proved prohibit infinitely many such splittings. This proves existence of a finite prime decomposition, including for $X$ without assuming orientability.

For completeness, both sphere bundles extracted above are prime three-manifolds. Their fundamental group is $\mathbb{Z}$, so a separating sphere and the van Kampen theorem express $\mathbb{Z}$ as a free product in which one capped factor has trivial fundamental group. Its punctured piece lifts homeomorphically to the universal cover $S^2\times \mathbb{R}$, identified with ${\mathbb{R}}^3\setminus \{0\}$. That compact lifted piece has one spherical boundary and must be the bounded side of this sphere in ${\mathbb{R}}^3$. It misses the origin, so the Three-dimensional Schoenflies theorem makes it a three-ball. The corresponding capped factor is $S^3$, as required.

Suppose now that $X$ is orientable. A prime factor which is not an irreducible three-manifold contains a nonseparating sphere: an essential separating sphere would already split it nontrivially. Extracting the corresponding sphere bundle shows that the factor must be $S^2\times S^1$. Thus the other nontrivial primes are irreducible.

Consider two prime decompositions. Represent each by a sphere system, including one nonseparating sphere in each $S^2\times S^1$ factor. The capped pieces are now the irreducible factors and copies of $S^3$. Make the two sphere systems transverse. To remove their intersections, choose a circle innermost on a sphere of the second system and surger the first system along its disk. Retain both surgery spheres temporarily. The old sphere and the new pair bound a three-times punctured sphere; adding the pair and then deleting the old sphere only inserts or removes spherical punctures.

This operation cannot alter an irreducible capped piece: every new sphere in that piece bounds a three-ball, so it can only split off a punctured $S^3$ piece. The other pieces were already punctured $S^3$, where the same conclusion follows from the Three-dimensional Schoenflies theorem. After small displacements the surgery removes the chosen intersection circle and introduces none. Repeat until the sphere systems are disjoint. Their union is a common refinement, and its non-$S^3$ capped irreducible pieces are precisely those of each original decomposition. Hence these factors agree, up to order and orientation-preserving homeomorphism.

Finally, the number $r$ of $S^2\times S^1$ factors is determined bywhere the sum runs over the common irreducible factors. This uses additivity of first homology under connected sum, not a claim that the fundamental group determines a manifold. Therefore the orientable prime decomposition is unique up to order and insertion or deletion of $S^3$ factors.

The possible ranks and the corresponding homeomorphism types areThere is no example for $n=2$ or $n\ge 4$. The uniqueness here is topological, not uniqueness of a Riemannian metric.

To see the restrictions, use the prime decomposition of a closed orientable three-manifold. Its fundamental group is the free product of the prime three-manifold groups. A free product of two nontrivial groups is nonabelian, so at most one summand can have nontrivial fundamental group. The remaining simply connected summands are three-spheres by the Poincaré conjecture. If the nontrivial summand is not irreducible, it is $S^2\times S^1$, giving rank one. If it is irreducible and has infinite fundamental group, the sphere theorem for three-manifolds makes it aspherical. Its fundamental group is then a dimension-three Poincare duality group. But ${\mathbb{Z}}^n$ is a duality group of dimension $n$, as seen from the torus classifying space or its Koszul resolution, so $n=3$.

For rank three, the flat case of the geometrization theorem says that a closed irreducible orientable three-manifold with fundamental group ${\mathbb{Z}}^3$ admits a flat metric. Write it as ${\mathbb{R}}^3/\Gamma$. By the Bieberbach theorem, $\Gamma$ contains a full-rank translation lattice $\Lambda$. If $g=(R,v)\in \Gamma$ commutes with translation by each $\lambda \in \Lambda$, then $R\lambda =\lambda$ for every lattice vector, forcing $R=I$. Since $\Gamma$ itself is abelian, it consists entirely of translations. Its quotient is therefore the three-torus. Rank zero follows directly from the Poincaré conjecture, and rank one was already determined by the prime decomposition of a closed orientable three-manifold. Historically, before the Poincare theorem, the uniqueness conclusions were phrased allowing connected sums with homotopy three-spheres; the modern theorem removes that ambiguity.

The six flat types below mean the six closed orientable flat three-manifold types. There are infinitely many individual flat metrics and there are additional noncompact flat Riemannian manifolds. In each closed case the universal cover is Euclidean space and the deck transformation group is a torsion-free crystallographic group. The holonomy groups of closed orientable flat three-manifolds are $1,C_2,C_3,C_4,C_6,C_2\times C_2$.

The first is a flat torus ${\mathbb{R}}^3/\Lambda$, with trivial holonomy. For each cyclic case choose a planar lattice $L$ admitting the relevant rotation $R_m$, and generate the deck transformation group by translations in $L$ and the screwIts $m$th power is unit translation along the axis. A nontrivial holonomy element has nonzero axial displacement modulo integers, so has no fixed point. All transformations preserve orientation. A compact prism fundamental domain gives compactness. Equivalently, the manifold is a torus mapping torus with finite-order monodromy. In planar lattice bases one may takeThe half-turn uses any planar lattice, the quarter-turn a square lattice, and the third- and sixth-turns a hexagonal lattice. These give respectively the half-turn flat three-manifold, third-turn flat three-manifold, quarter-turn flat three-manifold, and sixth-turn flat three-manifold. Their holonomies have orders $2,3,4,6$, and their first Betti numbers are all one, since the only fixed direction of holonomy is the screw axis.

The sixth type is the Hantzsche-Wendt manifold. A concrete group is generated byTheir linear parts are commuting half-turns about perpendicular axes. Moreover ${\alpha }^2$, ${\beta }^2$ and $(\alpha \beta {)}^2$ are translations by $(1,0,0)$, $(0,1,0)$ and $(0,0,-1)$. Their translation subgroup is the unit cubic lattice and their linear quotient is $C_2\times C_2$. In each nontranslation coset, the displacement along the fixed axis is a half-integer, so the action is free. The quotient is compact and orientable. No vector is fixed by both linear parts, so its first Betti number is zero. Bieberbach classification gives precisely these six affine types; the explicit screw descriptions distinguish them without identifying arbitrary finite quotients with holonomy.

The Seifert-van Kampen theorem states that if a space is covered by path-connected open sets $U,V$ with path-connected intersection containing a basepoint, then its fundamental group is the free product ${\pi }_1(U)\ast {\pi }_1(V)$ modulo the normal subgroup generated by identifying the two images of each loop in $U\cap V$. More generally it is the corresponding pushout of groups.

A wedge of two circles has fundamental group $F(a,b)$, the free group on their two loops: apply the theorem to thickened circle neighborhoods whose intersection is contractible and use ${\pi }_1(S^1)=\mathbb{Z}$. Represent the torus by a square with opposite edges identified. Remove an interior disk; the remainder deformation retracts onto this wedge. Replacing the disk attaches a two-cell whose boundary follows $ab{a}^{-1}{b}^{-1}$. A disk neighborhood and the punctured torus have annular intersection, and van Kampen kills precisely that boundary loop. HenceA torus with a point removed retracts to a torus with a small open disk removed, and then to the same wedge. ThusFor the connected sum, remove a disk from each torus and glue their boundary circles with reversed orientations. The two pieces have free groups $F(a,b)$ and $F(c,d)$ and their overlap is an annulus. Its boundary generators correspond to $[a,b]$ and $[c,d{]}^{-1}$, where $[a,b]=ab{a}^{-1}{b}^{-1}$. ThereforeThe boundary relation is essential: this group is neither the free group on four generators nor the abelian group ${\mathbb{Z}}^4$.

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.

The sphere $\{p\}\times S^2$ in $S^1\times S^2$ is nonseparating: its complement is $(S^1\setminus \{p\})\times S^2$, which is connected. A sphere bounding a ball separates, so this product is not an irreducible three-manifold.

To show it is prime, suppose a separating sphere cuts it into compact pieces $V,W$ with one spherical boundary each. The Seifert-van Kampen theorem givesA free product of two nontrivial groups is nonabelian: choose nonidentity elements in the two factors; their products in the two orders are distinct reduced words. Hence one factor, say ${\pi }_1(V)$, is trivial. The inclusion of this simply connected compact piece lifts to the universal cover $\mathbb{R}\times S^2\cong {\mathbb{R}}^3\setminus \{0\}$. The lift is an embedding: equality of lifted points would imply equality of their projections in $V$. Its image $\tilde{V}$ is compact with boundary the lifted sphere.

Use the three-dimensional Schoenflies theorem: a locally flat embedded sphere in ${\mathbb{R}}^3$ bounds a ball, and its compact side is that ball. The interior of $\tilde{V}$ is both open and closed in the corresponding complement component, and compactness rules out the unbounded component. Thus $\tilde{V}$ is the bounded ball, and $V$ itself is a ball. Capping $V$ gives $S^3$, so every connected-sum decomposition is trivial. Therefore $S^1\times S^2$ is prime but not irreducible.

Now let a prime closed connected orientable $M$ fail irreducibility. A sphere not bounding a ball cannot separate: if it did, primeness would make one capped side $S^3$, and the three-dimensional Schoenflies theorem would make its uncapped side a ball. Thus there is a nonseparating sphere $S$. Its two-sided neighborhood is $S^2\times [-1,1]$. Since the complement is connected, join its two boundary spheres by an embedded arc in that complement and thicken the arc. The union is a punctured $S^2\times S^1$: the thickened arc joins the two ends of the sphere-cylinder, and the remaining boundary is one sphere. This is the nonseparating sphere gives a sphere-circle summand construction and yieldsThe product is not $S^3$, since its fundamental group is $\mathbb{Z}$. Primeness forces $N\cong S^3$, soThe background results used are van Kampen, the explicit universal cover of the product, and the locally flat three-dimensional Schoenflies theorem; no Poincaré-conjecture argument is needed.

The free product $G_1\ast G_2$ is a group with homomorphisms from $G_1,G_2$ such that any pair of homomorphisms $G_i\to K$ extends uniquely to a homomorphism $G_1\ast G_2\to K$. Concretely its elements are reduced words with nonidentity syllables alternating between the factors. Multiply by concatenating and then combining adjacent syllables from the same factor, deleting identities. The empty word is the identity, and this normal form theorem for a free product also makes the factor maps injective.

The Klein combination theorem, in its ping-pong form, is as follows. Suppose two nontrivial subgroups $A,B$ act on a set $X$, with disjoint nonempty subsets $X_A,X_B$, such thatIf at least one factor has at least three elements, then $⟨A,B⟩\cong A\ast B$ through the natural factor maps. The cardinality condition is needed in this version: two order-two groups can have the same image swapping the two domains.

Here is the proof. Assume $|A|\ge 3$. A reduced word beginning and ending with an $A$-syllable sends $X_B$ into $X_A$ by successive application of the displayed inclusions, so cannot act as the identity. A word beginning and ending in $B$ becomes one of the preceding type on conjugating by any nonidentity $a\in A$. If it begins in $A$ and ends in $B$, choose $a\in A$ different from both $1$ and its first syllable. The word $a^{-1}wa$ remains reduced after combining its first two syllables and begins and ends in $A$, so again it is nonidentity. If it begins in $B$ and ends in $A$, apply this last argument to its inverse. Every nonempty reduced word is covered, so the natural homomorphism $A\ast B\to ⟨A,B⟩$ has trivial kernel. This proves the Klein combination theorem.

Apply it to the two cyclic groups generated by the given Möbius transformations. On $X=\mathbb{R}\cup \{\infty \}$ takeTheir powers areFor $m\ne 0$ and $|x|<1$, $|x+2m|\ge 2|m|-|x|>1$, so $f^m{X}_B\subseteq X_A$. For $x\in X_A$, put $1/\infty =0$; thenso $g^m{X}_A\subseteq X_B$. The powers displayed also show that both transformations have infinite order. The Klein combination theorem consequently gives

For the finite-index formula, realize the free group $F_n$ as the fundamental group of the rose with $n$ edges. A subgroup $H$ of index $i$ corresponds to a connected $i$-sheeted covering graph. Explicitly, its vertices are right cosets $Hx$ and for each basis generator $s_j$ there is a directed edge $Hx\to Hx{s}_j$ projecting to the corresponding rose edge. This graph is connected because basis words reach every coset, and the based loops correspond precisely to words in $H$.

The covering graph has $i$ vertices and $ni$ geometric edges: each positively oriented rose edge has one lift from each vertex. A maximal tree has $i-1$ edges, and the complementary edges freely generate its fundamental group. Thus $H$ is a free group with the Nielsen–Schreier formulaThis uses the connected cover associated with $H$; no claim that arbitrary disconnected covers are connected is needed.

Finally the specified basis of $F_n$ gives $d(F_n)\le n$. Its abelianization is ${\mathbb{Z}}^n$, by the universal property of the free group, and reduction modulo two gives a quotient $(\mathbb{Z}/2\mathbb{Z}{)}^n$. Images of any generating set must span this $n$-dimensional vector space, so it contains at least $n$ members. Therefore $\boxed{d(F_n)=n}$, and the same argument applies to the free group $H$ above.

Using exactly the unshifted definition printed in the paper, the unshifted rank gradients are determined byThe supremum is $n$, attained for $H=F_n$. For $n\ge 1$, mapping one basis generator onto a generator of $\mathbb{Z}/i\mathbb{Z}$ and the others to zero provides subgroups of every positive index $i$. Hence the infimum is $n-1$, approached as $i\to \infty$:For the trivial free group $F_0$, both values are zero. Subtracting one from $d(H)$ would change the upper answer; that is a different convention from the one requested here.

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