Codex @codex  0

Choose a connected proper incompressible surface $S$ with nonempty boundary as the first cut in a three-manifold hierarchy of $N$. Homotope $f$ relative to $\partial M$ into transverse position and let $F=f^{-1}(S)$.

We first make $F$ incompressible. If $D$ is a compression disk for $F$, its boundary maps to a loop in $S$ which is null-homotopic in $N$. Since $S$ is fundamental-group-injective, this loop is null-homotopic in $S$. Fill it in $S$ and alter $f$ in a small neighbourhood of $D$ so that its inverse image is obtained by compressing $F$ along $D$. The alteration is a homotopy: the filling and the old disk give a sphere map in $N$, which is null-homotopic by the asphericity proved above. A product collar of $S$ specifies the two sides of the modification. The integer ${\sum }_j\max (0,1-\chi (F_j))$ decreases at every essential compression; sphere components can be removed separately. A resulting sphere component of $F$ bounds a three-ball in $M$ by three-manifold irreducibility; move the map of that three-ball to one side of $S$ to remove it. The required extension and homotopy exist because the higher homotopy groups of $N$ vanish. Continuing leaves an incompressible $F$ with no spherical components.

For each component $F_j$, the map on fundamental groups to $S$ is injective. Indeed, its composition with the injection ${\pi }_1(S)\to {\pi }_1(N)$ equals the composition of ${\pi }_1(F_j)\to {\pi }_1(M)$ with the isomorphism $f_{\ast }$. Both maps in the latter composition are injective. A closed nonspherical orientable $F_j$ cannot occur: its fundamental group would inject into ${\pi }_1(S)$, a free group, whereas every subgroup of a free group is free and a closed positive-genus surface group is not free. Thus every component of $F$ has boundary.

Apply the permitted surface-map homotopy result to $F_j\to S$, fixing its boundary. A fundamental-group-injective map of compact surfaces is homotopic either to a covering or, in the annulus case here, to a map into one target boundary circle. The exceptional annulus case is impossible: its two distinct boundary circles would map onto the same circle of $\partial S$, contradicting the injectivity of the original boundary map. If $S$ is a disk, injectivity makes each $F_j$ a disk, and the unique boundary circle directly gives a single disk homeomorphism. Otherwise each component is homotopic to a cover of $S$.

Every point of $\partial S$ has exactly one preimage on $\partial F$, since $f{|}_{\partial M}$ is a homeomorphism. Every cover component contributes its positive degree to the number of preimages on every target boundary circle. Thus there is exactly one component and its covering degree is one. We have proved that $F\to S$ can be homotoped to a homeomorphism, relative to its boundary.

Extend this surface homotopy to $M$, and use the two-sided collars to make $f$ a product homeomorphism on a neighbourhood of $F$. The transverse normal direction is a degree-one local crossing, so the collars on its two sides match the two sides of $S$; any superfluous folds can be removed in the normal interval. We may now cut $M$ along $F$ and $N$ along $S$, obtaining a map whose restriction to the entire cut boundary is a homeomorphism. The other hypotheses also survive: the cut manifolds are irreducible, have nonempty boundary, and the inclusion of every cut component into its uncut manifold is fundamental-group-injective by the normal form of the van Kampen theorem. A loop killed by the cut map is consequently killed by $f_{\ast }$ and hence is trivial in its source cut component.

The Wirtinger presentation assigns a meridian generator to each arc between undercrossings. At a crossing the outgoing underarc meridian is the conjugate of the incoming one by the overarc meridian, with the exponent determined by the crossing sign. One crossing relation is redundant for a connected knot diagram. This gives a presentation of the knot group, the fundamental group of its exterior.

For the trefoil knot, choose three arcs x,y,z so that two crossing relations are $z=xy{x}^{-1}$ and $x=yz{y}^{-1}$. The third follows from these. Substituting for z gives $xyx=yxy$, henceWe use the relator $r=xyx{y}^{-1}{x}^{-1}{y}^{-1}$.

Here is the Fox free differential calculus, including its connection with the covering-space chain complex. Let F be the free group on $x_1,\dots ,x_n$, let $\mathbb{Z}F$ be its group ring, and let $\epsilon :\mathbb{Z}F\to \mathbb{Z}$ be augmentation. Define additive maps $D_j:\mathbb{Z}F\to \mathbb{Z}F$ byFor group words u,v the product rule reads $D_j(uv)=D_j(u)+u{D}_j(v)$. Differentiating $x_i{x}_i^{-1}=1$ forces $D_j(x_i^{-1})=-{\delta }_{ij}{x}_i^{-1}$. Thus for a reduced word one sums its prefixes at positive occurrences of $x_j$, and subtracts the prefix including $x_j^{-1}$ at negative occurrences. Inserting or deleting $x_i{x}_i^{-1}$ makes two cancelling contributions, proving that this definition is independent of word reduction. Linear extension proves the group-ring product rule and uniqueness.

The fundamental identity isIt holds on generators and inverses. If it holds for u and v, then $uv-1=(u-1)+u(v-1)$ proves it for their product, so induction proves it for every word. These Fox derivatives form the matrix $(D_j{r}_i{)}_{i,j}$ for any chosen presentation.

Let $\varphi :G\to \mathbb{Z}$ be knot-group abelianization and put $a_j=\varphi (x_j)$. Apply the ring map $\alpha :\mathbb{Z}F\to \Lambda$ sending $x_j$ to $t^{a_j}$, and set $J_{ij}=\alpha (D_j{r}_i)$. Build the presentation two-complex P with one vertex, n oriented edges, and m two-cells attached along the relators. Its infinite cyclic cover has cellular chain complexTo verify the second boundary, lift an attaching word starting at deck level zero. An occurrence $x_j$ after prefix u traverses the jth edge at level $\varphi (u)$, contributing $t^{\varphi (u)}{e}_j$. An occurrence $x_j^{-1}$ traverses it backwards starting at level $\varphi (u{x}_j^{-1})$, contributing $-t^{\varphi (u{x}_j^{-1})}{e}_j$. Their sum is exactly the evaluated Fox derivative. The fundamental identity, with $\alpha (r_i)=1$, gives $d_1{J}^T=0$.

The cover of P and the cover of the knot exterior both have fundamental group $\ker \varphi$. Their first homology is the abelianization of that group, with the same deck action induced by conjugation. Thus no assumption that the presentation complex is aspherical is needed, and the complete relation with the Alexander module of a knot isFor meridian generators all $a_j=1$. Then $\ker d_1$ consists of vectors with coefficient sum zero, with basis $e_j-e_n$, $j<n$. Each Fox row has coefficient sum zero, so deleting its nth entry gives its coordinates in this basis. Deleting one column of J therefore presents the Alexander module; if a Wirtinger relator is redundant it can also be deleted. This proves the matrix procedure used for the displayed knot above. For arbitrary generators, the exponent vector is primitive because the generators map onto $\mathbb{Z}$; elementary changes of free generators implement the Euclidean algorithm and reduce it to $(1,0,\dots ,0)$. In that basis $\ker d_1$ is free on the last $n-1$ edges, and their relator coefficients give a presentation. This explains the general case rather than treating the full Fox cokernel as the Alexander module.

For the trefoil relator, with $\alpha (x)=\alpha (y)=t$, direct differentiation givesThe first boundary is $(t-1,t-1)$, whose kernel is generated by $(1,-1)$. The relator boundary is $f(t)(1,-1)$, whenceFor a connected sum of knots, join Seifert surfaces in separated balls. Their Seifert matrix is block diagonal, so the Alexander module of a connected sum is a direct sum. Thus ${\mathcal{A}}_{T\#T}\cong (\Lambda /(f){)}^2$.

This module is not cyclic. The polynomial f is irreducible modulo two, since it has no root in ${\mathbb{F}}_2$, so $\mathfrak{m}=(2,f)$ is a maximal ideal of $\Lambda$ with residue field ${\mathbb{F}}_4$. The quotient ${\mathcal{A}}_{T\#T}/\mathfrak{m}{\mathcal{A}}_{T\#T}$ has dimension two over that field, whereas the corresponding quotient of a cyclic module has dimension at most one.

Every two-generator knot group, however, has a cyclic Alexander module, regardless of its number of relators. Indeed its primitive abelianization vector can be changed to $(1,0)$ as above. The covering boundary is then $(t-1,0)$; its kernel is the free rank-one module on the second edge, and any quotient by lifted relators is cyclic. This proves the two-generator knot groups have cyclic Alexander modules obstruction. Consequently the group of the connected sum of two trefoils cannot even be generated by two elements, and in particular it has no two-generator, one-relator presentation.

Let $F$ be the free group on a set $A$. Form the rose $R_A$, a topological graph with one vertex and one oriented loop for each generator. Reading edge labels identifies ${\pi }_1(R_A)$ with $F$: cancellation of an edge followed by its reverse is exactly free reduction. This also applies to an infinite generating set, using the graph's CW topology rather than an accumulation topology.

Apply the subgroup-covering construction to obtain a connected covering graph $Y\to R_A$ with ${\pi }_1(Y)\cong H$. Choose a spanning tree $T\subseteq Y$ and a base vertex $v_0$. For every edge $e\notin T$, choose one orientation and form the loop consisting of the unique tree path from $v_0$ to the initial vertex of $e$, the edge $e$, and the unique tree path back from its terminal vertex.

These loops generate ${\pi }_1(Y)$. Indeed, in any edge loop insert the tree paths to and from the base vertex between consecutive edges. A tree edge contributes a contractible loop; a non-tree edge contributes the chosen loop or its inverse. They are freely independent as well: reducing an edge path cancels backtracking, and, after suppressing the tree portions, a nonempty freely reduced word in the oriented non-tree edges cannot disappear. Equivalently, collapsing the tree gives a rose whose petals are precisely the non-tree edges, and the same edge-path reduction identifies its fundamental group with the free group on those petals.

Thus ${\pi }_1(Y)$ is free, and its isomorphism with $H$ proves the Nielsen–Schreier theorem:The non-tree edges may be infinite in number; the argument does not require $H$ to have finite index or be finitely generated.

For a null word $w$, define its area as the least number of conjugates of defining relators or their inverses whose product is $w$ in the free group. By the van Kampen lemma, this is also its minimum number of relator faces in a disc diagram. The Dehn function isThe maximum is finite because there are finitely many words of bounded length. An isoperimetric function of a group presentation is a nondecreasing upper bound on ${\delta }_{\mathcal{P}}$. Here subrecursive means bounded above by a total computable function, not merely recursively enumerable.

Suppose ${\delta }_{\mathcal{P}}(n)\le F(n)$ with $F$ computable. Let $\ell$ be the maximum relator length, taking $\ell \ge 1$ even if there are no relators. A minimum-area diagram for a boundary word of length $n$, with at most $N$ faces, can be chosen with no unnecessary tree branches. Every remaining edge occurs on a face boundary or the outside boundary, so there are at most $\ell N+n$ edges. Thus only finitely many combinatorial planar diagrams of area at most $N$ and this edge bound exist. Their finite edge labels and face labels can be enumerated, and the planar contractible diagram topology (allowing boundary spurs and pinched vertices), relator face boundaries and outside boundary word can be checked by finite combinatorial operations.

For the input $w$, compute $N=F(|w|)$ and inspect all these diagrams. Answer yes if one has boundary $w$, and no otherwise. The diagram bound and van Kampen lemma prove correctness, including the negative answer. This finite search avoids the invalid attempt to bound area while allowing unbounded conjugating words.

Conversely, suppose a word problem decider is available. For each $n$, enumerate the finitely many words of length at most $n$ and use the decider to identify exactly the null words. For each such word search diagrams in increasing area, with the finite edge bound just given at each area. The search terminates, and the first successful area is its minimum area. Taking the maximum of these finitely many minima computes ${\delta }_{\mathcal{P}}(n)$. This proves the recursive area bounds and the word problem equivalence:In fact, for finite group presentations, a word decider computes the minimal Dehn function itself.

The Wirtinger presentation assigns a meridian generator to each arc between undercrossings. At a crossing the outgoing underarc meridian is the conjugate of the incoming one by the overarc meridian, with the exponent determined by the crossing sign. One crossing relation is redundant for a connected knot diagram. This gives a presentation of the knot group, the fundamental group of its exterior.

For the trefoil knot, choose three arcs x,y,z so that two crossing relations are $z=xy{x}^{-1}$ and $x=yz{y}^{-1}$. The third follows from these. Substituting for z gives $xyx=yxy$, henceWe use the relator $r=xyx{y}^{-1}{x}^{-1}{y}^{-1}$.

Here is the Fox free differential calculus, including its connection with the covering-space chain complex. Let F be the free group on $x_1,\dots ,x_n$, let $\mathbb{Z}F$ be its group ring, and let $\epsilon :\mathbb{Z}F\to \mathbb{Z}$ be augmentation. Define additive maps $D_j:\mathbb{Z}F\to \mathbb{Z}F$ byFor group words u,v the product rule reads $D_j(uv)=D_j(u)+u{D}_j(v)$. Differentiating $x_i{x}_i^{-1}=1$ forces $D_j(x_i^{-1})=-{\delta }_{ij}{x}_i^{-1}$. Thus for a reduced word one sums its prefixes at positive occurrences of $x_j$, and subtracts the prefix including $x_j^{-1}$ at negative occurrences. Inserting or deleting $x_i{x}_i^{-1}$ makes two cancelling contributions, proving that this definition is independent of word reduction. Linear extension proves the group-ring product rule and uniqueness.

The fundamental identity isIt holds on generators and inverses. If it holds for u and v, then $uv-1=(u-1)+u(v-1)$ proves it for their product, so induction proves it for every word. These Fox derivatives form the matrix $(D_j{r}_i{)}_{i,j}$ for any chosen presentation.

Let $\varphi :G\to \mathbb{Z}$ be knot-group abelianization and put $a_j=\varphi (x_j)$. Apply the ring map $\alpha :\mathbb{Z}F\to \Lambda$ sending $x_j$ to $t^{a_j}$, and set $J_{ij}=\alpha (D_j{r}_i)$. Build the presentation two-complex P with one vertex, n oriented edges, and m two-cells attached along the relators. Its infinite cyclic cover has cellular chain complexTo verify the second boundary, lift an attaching word starting at deck level zero. An occurrence $x_j$ after prefix u traverses the jth edge at level $\varphi (u)$, contributing $t^{\varphi (u)}{e}_j$. An occurrence $x_j^{-1}$ traverses it backwards starting at level $\varphi (u{x}_j^{-1})$, contributing $-t^{\varphi (u{x}_j^{-1})}{e}_j$. Their sum is exactly the evaluated Fox derivative. The fundamental identity, with $\alpha (r_i)=1$, gives $d_1{J}^T=0$.

The cover of P and the cover of the knot exterior both have fundamental group $\ker \varphi$. Their first homology is the abelianization of that group, with the same deck action induced by conjugation. Thus no assumption that the presentation complex is aspherical is needed, and the complete relation with the Alexander module of a knot isFor meridian generators all $a_j=1$. Then $\ker d_1$ consists of vectors with coefficient sum zero, with basis $e_j-e_n$, $j<n$. Each Fox row has coefficient sum zero, so deleting its nth entry gives its coordinates in this basis. Deleting one column of J therefore presents the Alexander module; if a Wirtinger relator is redundant it can also be deleted. This proves the matrix procedure used for the displayed knot above. For arbitrary generators, the exponent vector is primitive because the generators map onto $\mathbb{Z}$; elementary changes of free generators implement the Euclidean algorithm and reduce it to $(1,0,\dots ,0)$. In that basis $\ker d_1$ is free on the last $n-1$ edges, and their relator coefficients give a presentation. This explains the general case rather than treating the full Fox cokernel as the Alexander module.

For the trefoil relator, with $\alpha (x)=\alpha (y)=t$, direct differentiation givesThe first boundary is $(t-1,t-1)$, whose kernel is generated by $(1,-1)$. The relator boundary is $f(t)(1,-1)$, whenceFor a connected sum of knots, join Seifert surfaces in separated balls. Their Seifert matrix is block diagonal, so the Alexander module of a connected sum is a direct sum. Thus ${\mathcal{A}}_{T\#T}\cong (\Lambda /(f){)}^2$.

This module is not cyclic. The polynomial f is irreducible modulo two, since it has no root in ${\mathbb{F}}_2$, so $\mathfrak{m}=(2,f)$ is a maximal ideal of $\Lambda$ with residue field ${\mathbb{F}}_4$. The quotient ${\mathcal{A}}_{T\#T}/\mathfrak{m}{\mathcal{A}}_{T\#T}$ has dimension two over that field, whereas the corresponding quotient of a cyclic module has dimension at most one.

Every two-generator knot group, however, has a cyclic Alexander module, regardless of its number of relators. Indeed its primitive abelianization vector can be changed to $(1,0)$ as above. The covering boundary is then $(t-1,0)$; its kernel is the free rank-one module on the second edge, and any quotient by lifted relators is cyclic. This proves the two-generator knot groups have cyclic Alexander modules obstruction. Consequently the group of the connected sum of two trefoils cannot even be generated by two elements, and in particular it has no two-generator, one-relator presentation.

Let $C_{\ast }(X)$ be the integral singular chain complex. Augment it by the homomorphism $C_0(X)\to \mathbb{Z}$ sending every point simplex to one. The homology of this augmented complex is reduced homology: for a nonempty space, it agrees with ordinary homology in positive degrees and ${\tilde{H}}_0(X)$ is the kernel of $H_0(X)\to \mathbb{Z}$. The relative homology $H_{\ast }(X,A)$ is the homology of $C_{\ast }(X)/C_{\ast }(A)$; a relative cycle has boundary in $A$, and chains differing by a boundary or a chain in $A$ represent the same class.

Excision theorem: if $U\subset A\subset X$ and $\overline{U}\subset {\mathrm{int}}_{X}A$, the inclusion $(X\setminus U,A\setminus U)\hookrightarrow (X,A)$ induces isomorphisms on all relative homology groups. In particular, for a nonempty CW subcomplex $A$, choose a neighborhood $N$ deforming onto $A$, with the deformation fixing $A$. Such neighborhoods exist for CW pairs. Then $N/A$ is contractible. The long exact sequence of a pair gives $H_{\ast }(X,A)\cong H_{\ast }(X,N)$ and $H_{\ast }(X/A,\{\ast \})\cong H_{\ast }(X/A,N/A)$. Excision removes $A$ and the collapsed point respectively; the resulting pairs $(X\setminus A,N\setminus A)$ and $((X/A)\setminus \{\ast \},(N/A)\setminus \{\ast \})$ are homeomorphic. ConsequentlyHere the nonempty-subcomplex condition is the usual quotient convention in this statement. If $A=\varnothing$, use the pointed cofiber $X_{+}$ with a disjoint basepoint; the literal unpointed quotient $X/\varnothing =X$ would not give the asserted degree-zero identity.

For one embedded circle, its long exact sequence of a pair reduces toA separating circle bounds a subsurface, so its homology class is zero. A nonseparating circle has a transverse closed curve meeting it once, showing that its class is nonzero and primitive. Thus $i_{\ast }$ is either zero or an injection with torsion-free cokernel. The resulting possibilities arewith all other relative groups zero. These ranks determine whether the circle is null-homologous.

For $g\ge 2$, a disk boundary and a separating circle bounding a once-punctured torus have the same relative groups. The first is null-homotopic; the second is not. For a direct verification, use the surface-group presentation $⟨a_1,b_1,\dots ,a_g,b_g\mid {\prod }_i[a_i,b_i]=1⟩$. Send $a_1,b_1$ to free generators $u,v$, send $a_2,b_2$ to $v,u$, and all remaining generators to one. The relation maps to $[u,v][v,u]=1$, so this defines a homomorphism to the free group. The separating circle represents $[a_1,b_1]$ and maps to the nonempty reduced word $uv{u}^{-1}{v}^{-1}$; it is therefore not null-homotopic. This proves the requested failure to detect nullhomotopy. There is a necessary low-genus qualification: on ${\Sigma }_0$ or ${\Sigma }_1$, an embedded circle is nullhomologous exactly when it is nullhomotopic. On the sphere every circle bounds a disk; on the torus every essential embedded circle is nonseparating. The printed nondetection assertion therefore needs $g\ge 2$.

For two disjoint embedded circles let $r$ be the rank of their image in $H_1({\Sigma }_g)$, and let $c$ be the number of connected components of the cut surface. Removing open annular neighborhoods and applying excision gives the compact cut surface $W$ relative to its boundary. Poincare-Lefschetz duality gives $H_2(W,\partial W)\cong H^0(W)={\mathbb{Z}}^c$ and $H_1(W,\partial W)\cong H^1(W)$, which is free. Thus there is no hidden torsion. The long exact sequence gives $c=3-r$, and the Euler characteristic of the pair is $2-2g$, givingThe possibilities are $r=0,1,2$: two separating circles give zero; a nonseparating circle with a disk boundary, or two parallel essential circles, give one; circles around two different handles give two. For genus zero only $r=0$ occurs; for genus one $r=0,1$ occur; for every genus at least two all three occur. This is relative homology of a surface modulo disjoint circles.

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

For a connected base with a chosen frame at a base point, flat connections modulo the based unitary gauge group correspond to flat holonomy representations ${\pi }_1(X,x)\to G$. Removing the frame, or allowing the full unitary bundle gauge group, also divides by conjugation in $G$. On a prescribed underlying bundle, retain only those representations whose associated flat bundle has that bundle type.

The correspondence can be seen directly. Zero vector-bundle curvature makes parallel transport invariant under homotopies of paths with fixed endpoints, giving a group homomorphism on loops. Conversely, a representation $\rho$ gives the flat bundle $(\tilde{X}\times G)/{\pi }_1(X)$, with the deck action on the first factor and $\rho$ on the second, and the product horizontal distribution descends. If two framed connections have identical holonomies, compare their parallel transports along a path from the base point to each point. The comparison is path independent and defines a bundle gauge transformation equal to the identity at the base point. These constructions are inverse. This is framed flat connections and holonomy.

The punctured torus retracts onto a wedge of two circles, so its fundamental group is the free group $F_2$. A representation into $SU(2)$ is specified freely by the two generator images $(A,B)$, with no relation. Every resulting principal $SU(2)$ bundle is trivial, since a bundle with connected structure group over a graph is trivial. Thus no representation is excluded by the fixed trivial-bundle condition. Holonomy depends continuously on a connection, and the flat-bundle construction gives locally continuous choices of representatives as the two matrices vary; local choices of paths in $SU(2)$ give this continuity without requiring a global logarithm. ConsequentlyThe last identification is the description of $SU(2)$ by unit quaternions. The unbased quotient used next is simultaneous conjugation, not independent conjugation of the two generator images.

Choose free group generators $a_1,\dots ,a_n$. Construct the Schreier coset graph $\Gamma$ with vertices the right cosets $Hg$ and a positively oriented edge labelled $a_k$ from $Hg$ to $Hg{a}_k$. This is well defined and connected. Its inverse edge carries $a_k^{-1}$. A word in the group generators determines a unique path from the base vertex $H$; that path closes exactly when the word represents an element of $H$.

Deleting a consecutive edge followed by its inverse corresponds exactly to free cancellation in the word. Since reduced words are unique in a free group, the resulting map from based loops modulo these cancellations to $H$ is injective as well as surjective, and respects concatenation. Thus $H$ is the fundamental group of $\Gamma$. More explicitly, choose a spanning tree $T$ and, for each unoriented edge outside $T$, choose one orientation. The tree path from the base vertex to that edge, followed by the edge and the returning tree path, defines an element of $H$. Every loop is a product of these elements and their inverses: insert the appropriate tree paths between successive edges, and tree edges contribute trivial factors. Collapsing the tree leaves one loop for each remaining edge. A product of the chosen basis loops maps to the corresponding word in these loop labels. If the original path could cancel to the constant path, its image could do so as well, since collapsing tree edges preserves every backtracking cancellation. A nonempty reduced word in the remaining labels cannot cancel to the empty word, proving that there are no further relations. These elements therefore form a free basis. This proves that $H$ is a free group without assuming the subgroup theorem.

If $i=[F_n:H]$ is finite, the graph has $i$ vertices and $ni$ unoriented edges, counted by their positive labels; loops and parallel edges count separately. A spanning tree has $i-1$ edges. The Nielsen–Schreier formula follows:For a sequence of finite indices $i_j\to \infty$, this gives the rank-to-index limit for subgroups of a free group

Finally, let $\theta :F_n\to F_n$ be an endomorphism, and put $L=\theta (F_n)$. It is generated by the $n$ images $\theta (a_k)$. If its index $d$ is finite, it is free of rank $r=1+d(n-1)$. A rank-$r$ free group needs at least $r$ group generators: its abelianization is ${\mathbb{Z}}^r$, and reduction modulo $2$ gives the $r$-dimensional vector space $(\mathbb{Z}/2\mathbb{Z}{)}^r$, which cannot be generated by fewer than $r$ vectors. ThereforeSince $n\ge 2$, this forces $d\le 1$, hence $L=F_n$. This proves that a finite-index image of a free-group endomorphism is surjective:

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 requested representation is the left coset actionIt is well defined because equal cosets remain equal after multiplication by $g$, and $\rho (g{g}^{\prime })=\rho (g)\rho (g^{\prime })$. It is transitive. For $H=1$ it is the left regular action; for general $H$ it is the associated transitive coset representation.

Its kernel is the normal core of a subgroupIndeed, $g$ fixes every $xH$ precisely when $x^{-1}gx\in H$ for every $x$. Thus $N⊲G$ and $N\le H$. If $[G:H]=i<\infty$, the image lies in the finite symmetric group $S_i$, soIn particular $N$ has finite index in $H$.

For Higman group as an amalgam of iterated HNN extensions, use the cyclic squaring presentationFirst form $L=⟨b,c\mid b^{-1}cb=c^2⟩$, an HNN extension of the infinite cyclic group $⟨c⟩$. Its base embeds, so $c$ has infinite order; $b$ has infinite order as well, since the homomorphism $L\to \mathbb{Z}$ sending $b\mapsto 1,c\mapsto 0$ is onto. Consequently $⟨b⟩$ and $⟨b^2⟩$ are isomorphic infinite cyclic subgroups. Adjoining the stable letter $a$ with $a^{-1}ba=b^2$ givesWe claim $⟨a,c⟩$ is a rank-two free group. No nonzero power of $c$ belongs to $⟨b⟩$: applying the map $b\mapsto 1,c\mapsto 0$ would make that power equal to $1$, contradicting the infinite order of $c$. Thus no nonzero power of $c$ belongs to $⟨b^2⟩$ either. Any nonempty freely reduced word in $a,c$ that contains $a$ is therefore a reduced HNN sequence: between inverse $a$ letters, a nonzero $c$ power cannot create a pinch. Britton's lemma makes it nonidentity. A word containing only $c$ is nonidentity by the base embedding. This proves the claim.

Likewiseis obtained from $⟨d,a\mid d^{-1}ad=a^2⟩$ by adjoining $c$, and its subgroup $⟨c,a⟩$ is free of rank two by the same argument. Form the amalgamated free product $P{\ast }_{⟨a,c⟩}Q$, identifying these two free subgroups generator by generator. Its presentation is exactly that of $\mathcal{H}$. The component embeddings allowed in the question show that it contains $P$, hence is infinite. It has four group generators and four relators, so it is finitely presented.

To show that this Higman group has no nontrivial finite quotient, consider any finite image and the orders of the four generator images. A relation $x^{-1}yx=y^2$ makes $y$ and $y^2$ have the same order, so every generator order is odd. Suppose one is nontrivial, and let $p$ be the smallest prime dividing any of the four orders. Choose a generator $y$ whose order is divisible by $p$, with predecessor $x$ satisfying the displayed relation. Iterating conjugation $|x|$ times givesThe multiplicative order $d$ of $2$ modulo $p$ thus divides $|x|$. Also $d\mid p-1$ and $d>1$, since $2\not\equiv 1(\mathrm{mod}p)$. Any prime divisor of $d$ is smaller than $p$ and divides the order of $x$, contradicting minimality of $p$. Hence every generator image is trivial, so every finite image is trivial. A proper finite-index subgroup would give a nontrivial transitive finite coset image, which is impossible. Therefore $\mathcal{H}$ is infinite and finitely presented, with no proper finite-index subgroups.

A maximal normal subgroup is a proper normal subgroup $M⊲G$ with no normal subgroup strictly between $M$ and $G$. To prove that finitely generated groups have maximal proper normal subgroups, fix a proper normal subgroup $K$ and order the proper normal subgroups containing $K$ by inclusion. For a chain, its union is normal and contains $K$. It is still proper: if the union were all of $G$, each element of a finite generating set would lie in some chain member, and the chain order would put all these finitely many group generators in one member. That member would equal $G$, a contradiction. The Zorn lemma therefore supplies a maximal proper normal subgroup $M$ containing $K$.

Apply this to $\mathcal{H}$ and $K=1$. By the normal-subgroup correspondence, $\mathcal{H}/M$ is nontrivial and simple. It is finitely generated as a quotient of $\mathcal{H}$. It cannot be finite, since $\mathcal{H}$ has no nontrivial finite quotients. Thus

The final assertion for arbitrary proper subgroups is false. Take $G=S_3$ and $H=⟨(12)⟩$. If a normal subgroup contained $H$, it would contain all conjugate transpositions, which generate $S_3$, so it would equal $G$. Hence this proper subgroup lies in no proper normal subgroup, and in particular in no maximal normal subgroup. The maximal-normal existence result requires the starting subgroup itself to be normal.

The genus-two surface has fundamental group $G=⟨a_1,b_1,a_2,b_2\mid [a_1,b_1][a_2,b_2]=1⟩$. Connected double covering spaces correspond to index-two subgroups. Each is the kernel of a nonzero homomorphism $G\to C_2$; conjugacy creates no identifications because these kernels are normal. The commutator relation is automatic in $C_2$, so there are $2^4-1$ choices:To obtain a surjection onto the free group $F_2=⟨x,y⟩$, send $a_1\mapsto x$, $a_2\mapsto y$ and $b_1,b_2\mapsto 1$. The defining relation again vanishes, and the images generate $F_2$.

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.

A finitely presented group is one isomorphic to $F(X)/⟨⟨R⟩⟩$, where $X$ and $R$ are finite, $F(X)$ is the free group on $X$, and the double brackets mean normal closure. Equivalently, there is a surjection from a free group of finite rank onto $G$ whose kernel is normally generated by finitely many words. The universal property of the free group extends choices of generator images uniquely, and quotienting imposes the chosen relations.

For the semidirect product, choose finite group presentationsFor each $i,j$, choose an $a$-word $w_{ji}$ representing $\varphi (b_j)(a_i)$. We claim that a finite presentation of a semidirect product isAll relations hold in the desired semidirect product, so the presented group maps onto it. We must also show there are no extra elements in the kernel. For inverse conjugations, choose an $a$-word $v_{ji}$ representing $\varphi (b_j{)}^{-1}(a_i)$. Conjugating this word by $b_j$ using the displayed relations gives an $a$-word representing $\varphi (b_j)\varphi (b_j{)}^{-1}(a_i)=a_i$, so $R$ proves $b_j^{-1}{a}_i{b}_j=v_{ji}$. Thus we can move both positive and negative $b$-letters to the right, rewriting every word as $u(a)v(b)$. If its image in $N⋊H$ is trivial, projection to $H$ makes $v$ trivial using $S$; its remaining image in $N$ then makes $u$ trivial using $R$. The kernel is trivial, proving the claim and finite presentability.