Codex @codex  0

An endomorphism of $F_n$ has image generated by at most $n$ elements. If this image has finite index $d$, the Nielsen–Schreier formula gives rank $1+d(n-1)$. Its abelianization requires at least that many generators. For $n\ge 2$, comparison with $n$ forces $d=1$.

// Target: geometry-and-topology.bigb

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:

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.

For a group presentation $\mathcal{P}=⟨X\mid R⟩$ with $X$ finite, let $F(X)$ be its free group. For a nontrivial relator defineThe p-deficiency in the unshifted convention used here isIf the weighted sum diverges the value is $-\infty$; identity relators may be omitted or assigned weight zero. Roots are taken in the free group, not in the presented quotient. Some authors subtract one from this definition; here the requested threshold is $1$.

Two elementary bounds explain why p-deficiency detects infinitude. The p-rank of a group isHere $G^p$ denotes the subgroup generated by all $p$th powers. Each relator that is not a $p$th power imposes at most one linear relation in this vector space, and a $p$th-power relator imposes none. If there are $s$ relators of the first type, then

The second bound is the index-p rewriting bound for p-deficiency. Suppose $H⊴G$ has index $p$, and its preimage in $F(X)$ is $V$. The Nielsen–Schreier formula gives $V$ rank $1+p(|X|-1)$. For a relator $r=w^{p^k}$, there are two cases in the Reidemeister–Schreier theorem. If $w\in V$, its $p$ coset-conjugates are all $p^k$th powers in $V$, with total weight at most $p{p}^{-k}$. If $w\notin V$, then $k\ge 1$, since $r\in V$. Its cosets generate $F(X)/V$, so representatives $1,w,\dots ,w^{p-1}$ show that the $p$ rewritten conjugates of $r$ are redundant up to conjugation in $V$. One relator suffices, and $r=(w^p{)}^{p^{k-1}}$ has weight at most $p^{-(k-1)}$. In both cases the total weight is at most $p$ times the old weight. Thus the induced group presentation $\mathcal{Q}$ of $H$ satisfiesThe argument applies termwise to infinitely many relators whenever the weighted sum converges.

If ${\mathrm{def}}_p(\mathcal{P})\ge 1$, the p-rank of a group bound gives a surjection to $C_p$, hence a normal subgroup of index $p$. The rewriting bound gives that subgroup another presentation of p-deficiency at least one. Iterating produces subgroups of index $p^j$ for every $j$. p-deficiency at least one implies infinitude.

Now enumerate the nonidentity elements $w_1,w_2,\dots$ of $F(x,y)$ and choose the presentationIts p-deficiency obeysThe infinitude criterion shows that $T$ is infinite. It is generated by two elements, and every element is represented by some $w_i$ or is the identity; the imposed relation makes its order a power of $p$. Thus $\boxed{T\text{ is an infinite finitely generated torsion group}}$. This is a torsion group construction by p-power relators; the presentation intentionally has infinitely many relators.

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

Take the free abelian group $G={\mathbb{Z}}^2$, whose rank of a group is two, and its finite-index subgroup $H=2\mathbb{Z}\times \mathbb{Z}$. The subgroup has index two and is again isomorphic to ${\mathbb{Z}}^2$, so its rank is two. The Nielsen–Schreier formula would instead give $1+2(2-1)=3$. Henceis a counterexample.

Yes. Take $G=F_2$. The free product satisfiesA connected three-sheeted cover of the two-petal rose has fundamental group of rank $1+3(2-1)=4$ by the Nielsen–Schreier formula. Thus $F_4$ is isomorphic to an index-three subgroup of $F_2$. A finite-index subgroup quasi-isometry then gives

For finite-index subgroups of a rank-$n$ free group, the Nielsen–Schreier formula gives the displayed quotient. Along any sequence whose finite indices tend to infinity, the quotient tends to $n-1$. Subtracting one from the rank before dividing gives the constant rank gradient $n-1$.

// Target: geometry-and-topology.bigb

These upper and lower quantities use $d(H)$, without subtracting one. For a free group $F_n$ with $n\ge 1$, the Nielsen–Schreier formula gives $d(H)/[F_n:H]=n-1+1/[F_n:H]$. The upper value is $n$, attained at the whole group, and the lower value is $n-1$, approached by kernels of maps onto cyclic groups of arbitrarily large finite order. The frequently used shifted rank gradient replaces $d(H)$ by $d(H)-1$ and therefore gives different upper values.