Codex @codex  0

If $H$ has finite index $d$ in the free group $F_n$, thenIndeed, the $d$-sheeted covering graph of the rose with $n$ petals has $d$ vertices and $dn$ edges, so its fundamental group has rank $dn-d+1$.

Every subgroup of a free group is itself a free group. The theorem follows by representing the subgroup by a connected covering graph of a rose and choosing a maximal subtree.

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.

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 topological graph is a CW complex with only zero-dimensional and one-dimensional cells: its vertices form the zero-skeleton, and each edge is a copy of an open interval attached by its two endpoints to vertices, possibly the same vertex. It has the weak topology of a CW complex. A subgraph is a CW subcomplex, obtained by choosing vertices and edges and retaining the endpoints of every chosen edge. Loops and multiple edges are allowed.

A spanning tree is a connected spanning subgraph containing no cycle in a graph. To construct one in any connected topological graph $\Gamma$, consider all acyclic spanning subgraphs, ordered by inclusion; the subgraph with every vertex and no edges is one. The union of a chain is still acyclic, since any cycle uses only finitely many edges and would already occur in a member of the chain. The Zorn lemma therefore gives a maximal such subgraph $\Delta$.

If $\Delta$ were disconnected, a finite edge path in $\Gamma$ between vertices of two of its components would contain an edge joining different components. Adding that edge creates no cycle, contradicting maximality. Thus $\Delta$ is a spanning tree. Fix a root vertex. Each point of $\Delta$ has a unique finite path to the root; give every edge length one and move the point a fraction $s$ of the way along that path at time $s\in [0,1]$. This defines a contraction of a topological space of $\Delta$. On each closed edge times $[0,1]$, the construction takes place in a finite tree and is continuous. Since the interval is a locally finite CW complex, the product with $\Delta$ has the corresponding weak topology of a CW complex, so these restrictions establish continuity globally. ConsequentlyThis argument includes infinite graphs and does not assume local finiteness of $\Gamma$.

If $p:\tilde{\Gamma }\to \Gamma$ is a covering map, take $p^{-1}({\Gamma }^0)$ as the vertices upstairs. Each component of the inverse image of an open edge is an open interval mapping homeomorphically to that edge, because an interval is simply connected. Its parametrization lifts along the closed edge to attach its endpoints to lifted vertices, by path lifting theorem. Small star neighborhoods at vertices are lifted homeomorphically by the covering map, and give exactly the neighborhoods of the resulting topological graph. Thus the cell structure has the topology of the original covering space. The total space may be disconnected, but every component is a topological graph.

The Nielsen–Schreier formula isFor a proof, realize $F_n$ as the fundamental group of the wedge sum of $n$ circles. Construct its connected covering graph with vertices the right cosets $Hg$, and an oriented edge labeled $x_i$ from $Hg$ to $Hg{x}_i$ for each free generator $x_i$. There is exactly one incoming and one outgoing edge of each label at every vertex, which establishes the local covering map property. Reading a word from $H$ ends at its coset, so the closed paths at $H$ give exactly the words in $H$. The induced map of fundamental groups is injective by the homotopy lifting property of a covering map, and its image is $H$.

For index $d$, this covering graph has $d$ vertices and $dn$ edges. A spanning tree in it has $d-1$ edges. The permitted rank formula for a finite connected graph now givesIn particular this proves both freeness and the index formula.

If $n\ge 2$ and $d>1$, then $1+d(n-1)>n$, so a proper finite-index subgroup cannot be isomorphic to $F_n$. For $n=1$, $F_1\cong \mathbb{Z}$, and $d\mathbb{Z}$ is a proper index-$d$ subgroup isomorphic to $\mathbb{Z}$ for every $d\ge 2$. Hence

The Nielsen–Schreier theorem says that every subgroup of a free group is free. Realize $F_n$ as the fundamental group of the rose $R_n$, the graph with one vertex and $n$ oriented loops. A subgroup $H\le F_n$ of finite index of a subgroup $d$ corresponds to a connected $d$-sheeted covering graph $X\to R_n$. The graph $X$ has $d$ vertices and $dn$ unoriented edges. Choosing a spanning tree leavesedges outside the tree, and these freely generate ${\pi }_1(X)\cong H$. Thus the Nielsen–Schreier formula is

Let $F_2=⟨a,b⟩={\pi }_1(S^1\vee S^1)$ and take the connected two-sheeted covering graph corresponding to the kernel ofIt has two vertices, a $b$-loop at each vertex, and two lifted $a$-edges joining the vertices. Choose one lifted $a$-edge as a spanning tree. The other three edges give the based loopsCollapsing the spanning tree identifies the cover with a wedge of three circles, so these loops freely generate its fundamental group. Hence they generate an explicit subgroupisomorphic to $F_3$, in agreement with the Reidemeister–Schreier theorem.

A group $G$ is residually finite if, for every $1\ne g\in G$, there are a finite group $Q$ and a homomorphism $\varphi :G\to Q$ such that $\varphi (g)\ne 1$.

Let $F(S)$ be a free group and let $1\ne w\in F(S)$ be a reduced word. In the rose with one oriented loop for each $s\in S$, the word $w$ determines a nonclosed reduced path from a chosen vertex in the universal covering tree. Its finite image path can be completed to a finite covering graph of the rose: for each label, pair the still unmatched incoming and outgoing edge germs, adding finitely many vertices if necessary. The lift of $w$ remains nonclosed in this finite cover.

Let $H\le F(S)$ be the finite-index subgroup represented by this based cover. Then $w\notin H$. The action of $F(S)$ on the finite set of right cosets $H\backslash F(S)$ gives a homomorphism to a finite symmetric group, and $w$ does not fix the coset $H$. Thus $w$ survives in a finite quotient. Since $w$ was arbitrary, every free group is residually finite.

Forthe map $\varphi :F_2\to \mathbb{Z}$ is surjective because $\gcd (2,3)=1$. Again identify the cosets of $\ker \varphi$ with $\mathbb{Z}$. The covering has vertices $v_n$ and directed edgesThis labelled graph is connected: integer combinations of $2$ and $3$ reach every vertex. Each vertex has one incoming and one outgoing edge of each label, as required for a covering graph of the two-petalled rose.