Subgroups of Free Groups and Schreier Rewriting

Let $K\le F(X)$ be the subgroup generated by the image of $X$. The inclusion $X\hookrightarrow K$ extends, by [L1], to a homomorphism $\varphi :F(X)\to K$, and the inclusion $K\hookrightarrow F(X)$ composed with $\varphi$ agrees with the identity of $F(X)$ on $X$. Uniqueness in [L1] therefore forces $(K\hookrightarrow F(X))\circ \varphi ={\mathrm{id}}_{F(X)}$, so $K=F(X)$. Thus every element of $F(X)$ is represented by a word on $X\bigsqcup X^{-1}$.

Let $Hg$ be any vertex. Choose a word $a_1\cdots a_n$ on $X\bigsqcup X^{-1}$ that represents $g$, and delete adjacent inverse pairs until the word is reduced. Reading the remaining letters from the base vertex $H$ follows the edges of [L3] forward for letters in $X$ and backward for letters in $X^{-1}$, and after the first $j$ letters one is at the coset $H{a}_1\cdots a_j$. The final vertex is therefore $Hg$, so the graph is connected.

For fixed $Hg$ and $x\in X$, [L3] gives exactly one outgoing $x$-edge, namely $Hg\to Hgx$. The same edge starts at $Hg{x}^{-1}$ and ends at $Hg$, so it is also the unique incoming $x$-edge into $Hg$. This is the required determinism.

Let $T$ be a rooted spanning tree. For each vertex $v$, let $p_v$ be the unique simple path in $T$ from $H$ to $v$, and let $\tau (v)$ be its label. A simple path in a tree never backtracks, so $\tau (v)$ is reduced. Because $T$ is spanning, every coset has some label $\tau (v)$; because $T$ is a tree, the path $p_v$ is unique, so no two distinct words $\tau (v)$ label the same vertex. Any initial segment of $\tau (v)$ labels an initial subpath of $p_v$, hence labels the tree path to an earlier vertex. Therefore $\{\tau (v)\}$ is a Schreier system.

Conversely, let $\mathcal{T}$ be a Schreier system. For each non-base representative $t=x_1\cdots x_n\in \mathcal{T}$, join the vertex $Ht$ to the vertex $H{x}_1\cdots x_{n-1}$ by the final labeled edge used to read $t$. Because prefixes stay in $\mathcal{T}$, every non-base vertex acquires exactly one parent; because the parent has smaller word length, repeatedly following parent edges must terminate at $H$. Thus every vertex is connected to $H$, and a cycle cannot occur because along a cycle one could not keep decreasing length and return to the starting vertex. So these parent edges form a rooted spanning tree.

The two constructions are inverse. Reading the tree path from $H$ recovers each representative in the Schreier system, and taking parent edges from the prefixes of those representatives reconstructs the original rooted tree.

Because $\overline{tx}$ represents the same right coset as $tx$, one has $Htx=H\overline{tx}$.

Right-multiplying the equality of step 1.1 by ${\overline{tx}}^{-1}$ gives $Hs(t,x)=H$. Hence $s(t,x)\in H$.

It is enough to treat one elementary cancellation. By symmetry it suffices to consider $u=px{x}^{-1}q$ and $v=pq$ with $x\in X$. Let $t=\bar{p}$ and $u_1=\overline{px}$. In the rewrite of $u$, the letter $x$ contributes $s(t,x)$ and the following letter $x^{-1}$ contributes $s(t,x{)}^{-1}$, so these two adjacent letters freely cancel.

After those two letters are read, the current coset is again $Hp$, so the successive representatives used for the remaining suffix $q$ are exactly the same whether one starts from $u$ or from $v$. Thus one elementary free cancellation turns $\tau (u)$ into $\tau (v)$. Repeating this argument along a finite chain of elementary cancellations and reverse insertions proves that the two rewrites are freely equivalent, and hence represent the same subgroup element.

Let $h\in H$, and choose any word $w$ on $X\bigsqcup X^{-1}$ representing $h$. By [L3], free-reducing $w$ does not change its rewrite, so we may assume $w=a_1\cdots a_n$ is reduced. If $t_j$ denotes the chosen representative of the coset of the prefix $a_1\cdots a_j$, and if ${\sigma }_j$ is the $j$th Schreier rewriting factor from [L1], then $t_{j-1}{a}_j={\sigma }_j{t}_j$ for every $j$.

Multiplying the identities from step 1.1 yields $h=w={\sigma }_1\cdots {\sigma }_n{t}_n=\tau (w)t_n$. Because $h\in H$, the last coset is $H$, so the final representative is $t_n=1$. Thus $h=\tau (w)$ is a product of Schreier generators and their inverses.

By [L2], each Schreier generator belongs to $H$, so the same is true for its inverse. After deleting the trivial factors in the product from step 2.1, we obtain an expression for $h$ as a product of nontrivial Schreier generators and their inverses. Therefore those nontrivial generators generate $H$.

Let $T$ be the rooted spanning tree corresponding to the given Schreier system by [L1]. If the positive edge from $Ht$ to $Htx$ lay in $T$, then the unique tree path from $H$ to $Htx$ would be the tree path to $Ht$ followed by that edge, so its label would be $tx$ and [L2] would give $s(t,x)=tx(tx{)}^{-1}=1$. Therefore every nontrivial Schreier generator corresponds to a unique positive edge outside $T$.

Take a nonempty reduced word in the nontrivial tree Schreier generators and their inverses. Replace each letter by its based loop from [L2] and concatenate those loops. Cancel adjacent inverse tree segments whenever they appear. Tree segments can disappear this way, but an edge outside $T$ can disappear only by meeting its own reverse immediately, which would mean that two consecutive Schreier generators were inverse letters, contrary to the reducedness of the word. So after all cancellations there remains a closed path whose label is a nonempty reduced word on $X\bigsqcup X^{-1}$.

By [L3], the nonempty reduced word from step 2.1 is not the identity in the ambient free group. Hence the original reduced word in the tree Schreier generators is nontrivial in $H$. Therefore those generators are freely independent.

Suppose first that $X$ is finite, or that $X$ is countable with a chosen enumeration. Then reduced words on $X\bigsqcup X^{-1}$ are ordered first by length and then lexicographically, so every nonempty set of reduced words has a shortlex least element. Choose in each right coset of $H$ its least reduced representative. If $u$ is an initial segment of the chosen representative $w$ for the coset $Hw$, and if the coset $Hu$ had a smaller reduced representative $u^{\mathrm{\prime }}$, then replacing the prefix $u$ of $w$ by $u^{\mathrm{\prime }}$ would produce a smaller representative of $Hw$, impossible. Hence the chosen representatives form a Schreier system.

For arbitrary $X$, [L1] lets us well-order the basis. The same shortlex construction as in step 1.1 then produces a Schreier system. In the countable case, the only choice principle visible in the statement is the weaker bookkeeping of [L2], because step 1.1 already gives the representatives canonically once the enumeration is fixed.

Let $\mathcal{T}$ be a Schreier system obtained from step 1.1 or step 2.1. By [L4], its nontrivial Schreier generators generate $H$, and by [L3] they are freely independent. Therefore [L5] makes them a free basis of $H$.

By [L1], choose a free basis $X$ of $F$ with $\mathrm{\mid }X\mathrm{\mid }=n$. Let $\mathrm{\Gamma }={\mathrm{Sch}}_X(H)$, and choose a rooted spanning tree $T$ in $\mathrm{\Gamma }$. Since the vertices of $\mathrm{\Gamma }$ are the right cosets of $H$, there are $d$ vertices. For each vertex and each $x\in X$, the Schreier graph has exactly one outgoing $x$-edge, so $\mathrm{\Gamma }$ has $dn$ positive labeled edges.

The tree $T$ has exactly $d-1$ edges. An edge $Ht\stackrel{x}{\to }Htx$ lies in $T$ exactly when the chosen representative of $Htx$ is $tx$, and then the corresponding Schreier generator is $tx(tx{)}^{-1}=1$. Every positive edge outside $T$ gives one nontrivial Schreier generator, so the number of nontrivial generators is $dn-(d-1)=1+d(n-1)$.

By [L3], the nontrivial generators counted in step 2.1 form a free basis of $H$. Therefore $H$ has finite rank and $\mathrm{rank}(H)=1+d(n-1)$.

Choose a free basis $X$ of $F$ with at least two elements, and fix distinct $x,y\in X$. Let $L=⟨x,y⟩$. For any group $G$ and any function $u:\{x,y\}\to G$, extend $u$ to a function on $X$ by sending every basis element outside $\{x,y\}$ to $e_G$. The universal property in [L1] then gives a unique homomorphism $F\to G$, whose restriction to $L$ extends $u$. Hence $\{x,y\}$ is a free basis of $L$, so [L2] gives $\mathrm{rank}(L)=2$.

For $m=1$, the cyclic subgroup $⟨x⟩$ has free basis $\{x\}$. Now assume $m\ge 2$. Because $L$ is free on $\{x,y\}$, there is a surjective homomorphism $\pi :L\to (\mathbb{Z}\mathrm{/}(m-1),+)$ with $\pi (x)=1$ and $\pi (y)=0$. Let $H_m=\ker \pi$. Then $[L:H_m]=m-1$, so [L3] gives $\mathrm{rank}(H_m)=1+(m-1)=m$.

The subgroup $⟨x⟩$ handles $m=1$, and the subgroups $H_m\le L\le F$ handle every $m\ge 2$. Therefore $F$ has subgroups of every finite rank.

By [L3], the set $S$ of nontrivial Schreier generators is a free basis of $H^{\mathrm{\prime }}$. Therefore the inclusion $S\hookrightarrow H^{\mathrm{\prime }}$ extends to an isomorphism $\rho :F(S)\to H^{\mathrm{\prime }}$.

By [L1], the ambient quotient is $G=F(X)\mathrm{/}N$ with $N=⟨\text{\hspace{0.17em}⁣}⟨R⟩\text{\hspace{0.17em}⁣}{⟩}_{F(X)}$. The restriction of the quotient map to $H^{\mathrm{\prime }}$ has image $H$ and kernel $H^{\mathrm{\prime }}\cap N$, so [L5] gives $H\cong H^{\mathrm{\prime }}\mathrm{/}(H^{\mathrm{\prime }}\cap N)$. By [L2], every element of $H^{\mathrm{\prime }}\cap N$ is a finite product of conjugates $u{r}^{\pm 1}{u}^{-1}$ with $u\in F(X)$ and $r\in R$. Writing $u=ht$ with $h\in H^{\mathrm{\prime }}$ and $t\in \mathcal{T}$ turns each such conjugate into $h(t{r}^{\pm 1}{t}^{-1})h^{-1}$, so $H^{\mathrm{\prime }}\cap N$ is contained in the normal closure in $H^{\mathrm{\prime }}$ of the elements $tr{t}^{-1}$. Conversely, each $tr{t}^{-1}$ lies in $H^{\mathrm{\prime }}\cap N$, and $H^{\mathrm{\prime }}\cap N$ is normal in $H^{\mathrm{\prime }}$, so that normal closure is exactly $H^{\mathrm{\prime }}\cap N$.

Let $q:H^{\mathrm{\prime }}\to H^{\mathrm{\prime }}\mathrm{/}(H^{\mathrm{\prime }}\cap N)$ be the quotient map, and put $\bar{\rho }=q\circ \rho :F(S)\to H^{\mathrm{\prime }}\mathrm{/}(H^{\mathrm{\prime }}\cap N)\cong H$. Fix $t\in \mathcal{T}$ and $r\in R$, and write $tr{t}^{-1}=a_1\cdots a_n$. Let $t_j$ and ${\sigma }_j$ be the successive representatives and rewriting factors from [L4]. If $a_j=x\in X$, then [L6] gives ${\sigma }_j=s(t_{j-1},x)=t_{j-1}x{t}_j^{-1}$, so $t_{j-1}{a}_j={\sigma }_j{t}_j$. If $a_j=x^{-1}$, then $t_{j-1}$ is the chosen representative of the coset $H^{\mathrm{\prime }}{t}_{j}x$, so [L6] gives ${\sigma }_j=s(t_j,x{)}^{-1}=t_{j-1}{x}^{-1}{t}_j^{-1}$ and again $t_{j-1}{a}_j={\sigma }_j{t}_j$. Multiplying these identities yields $tr{t}^{-1}={\sigma }_1\cdots {\sigma }_n{t}_n=\rho (\tau (tr{t}^{-1}))$, because $tr{t}^{-1}\in H^{\mathrm{\prime }}$ forces $t_n=1$ by [L4]. Since $tr{t}^{-1}\in H^{\mathrm{\prime }}\cap N$, every rewritten relator $\tau (tr{t}^{-1})$ lies in $\ker \bar{\rho }$.

Conversely, if $w\in \ker \bar{\rho }$, then $\rho (w)\in H^{\mathrm{\prime }}\cap N$. By step 1.2, $\rho (w)$ is a finite product of conjugates in $H^{\mathrm{\prime }}$ of the elements $tr{t}^{-1}$ and their inverses. Replacing each $tr{t}^{-1}$ by the equal element $\rho (\tau (tr{t}^{-1}))$ from step 2.1 and applying the isomorphism ${\rho }^{-1}$ shows that $w$ lies in the normal closure of the words $\tau (tr{t}^{-1})$ in $F(S)$. Therefore $\ker \bar{\rho }=⟨\text{\hspace{0.17em}⁣}⟨\tau (tr{t}^{-1}):t\in \mathcal{T},r\in R⟩\text{\hspace{0.17em}⁣}{⟩}_{F(S)}$.

The map $\bar{\rho }$ is surjective onto $H^{\mathrm{\prime }}\mathrm{/}(H^{\mathrm{\prime }}\cap N)\cong H$, so [L5] gives $F(S)\mathrm{/}\ker \bar{\rho }\cong H$. Substituting the kernel description from step 3.1 yields $H\cong ⟨S\mid \tau (tr{t}^{-1})\text{ for }t\in \mathcal{T},r\in R⟩$, which is the Reidemeister-Schreier presentation.

If $r^{\mathrm{\prime }}$ is obtained from $r$ by one elementary cancellation or reverse insertion, then for every transversal element $t$ the word $t{r}^{\mathrm{\prime }}{t}^{-1}$ is obtained from $tr{t}^{-1}$ by the same local free reduction inside the middle block. Therefore [L2] gives $\tau (tr{t}^{-1})=\tau (t{r}^{\mathrm{\prime }}{t}^{-1})$.

Any freely equivalent pair $r,r^{\mathrm{\prime }}$ is connected by finitely many such moves, so the equality from step 1.1 persists through the whole chain. Thus every rewritten relator produced from $r$ is identical to the one produced from $r^{\mathrm{\prime }}$.

By [L1], replacing a generator of a normal closure by the same group element does not change that normal closure. Hence the presentation described in [L3] is independent of which freely equivalent word is chosen to represent each ambient relator.

Choose a finite presentation $G=⟨X\mid R⟩$ and a finite right transversal $\mathcal{T}$ for $H$. By [L1], the sets $X$ and $R$ are finite, so the sets of pairs $(t,x)$ with $t\in \mathcal{T}$, $x\in X\bigsqcup X^{-1}$ and $(t,r)$ with $t\in \mathcal{T}$, $r\in R$ are finite.

By [L2], the subgroup $H$ has a presentation whose generators are among the Schreier generators $s(t,x)$ and whose relators are the rewritten words $\tau (tr{t}^{-1})$. Step 1.1 shows that both families are finite. Therefore $H$ is finitely presented.

Choose a finite free basis $X$ of $F$ and generators $h_1,\dots ,h_m$ of $H$. At a base vertex $v$, attach one reduced loop labeled by each $h_i$. Repeatedly fold pairs of equally labeled edges with the same initial vertex. Each fold preserves the set of labels of closed based paths and strictly decreases the number of edges, so after finitely many folds we obtain a finite connected folded pointed $X$-labeled graph $\mathrm{\Gamma }$ whose closed based labels are exactly the subgroup $H$.

For a fixed $x\in X$, each existing $x$-edge contributes one outgoing $x$-incidence and one incoming $x$-incidence. Therefore the number of vertices missing an outgoing $x$-edge equals the number missing an incoming $x$-edge. Pair those deficits and add finitely many new $x$-edges; doing this for every $x\in X$ produces a finite connected folded $X$-regular graph $\widehat{\mathrm{\Gamma }}$ containing $\mathrm{\Gamma }$.

Choose a spanning tree $T_{\mathrm{\Gamma }}$ of $\mathrm{\Gamma }$ and extend it to a spanning tree $T$ of $\widehat{\mathrm{\Gamma }}$. For each oriented edge $e$ outside $T_{\mathrm{\Gamma }}$, the tree path from the basepoint to the initial vertex of $e$, followed by $e$ and the reverse tree path from its terminal vertex, is a based loop. The loops obtained from one orientation of every non-tree edge freely generate the based loops of $\mathrm{\Gamma }$: deleting tree backtracking rewrites every closed path in them, while a nonempty reduced word in these loop generators leaves a non-tree edge after cancellation and hence is a nontrivial reduced path. Since $\mathrm{\Gamma }$ is folded and its closed labels are exactly $H$, their labels form a free basis $B_H$ of $H$.

Let $K$ be the set of labels of closed based paths in $\widehat{\mathrm{\Gamma }}$. The graph is folded and $X$-regular, so every reduced word on $X\bigsqcup X^{-1}$ is read from the basepoint along a unique path. Two words end at the same vertex exactly when their quotient labels a closed based path, that is, exactly when they lie in the same right coset of $K$. Hence the vertices of $\widehat{\mathrm{\Gamma }}$ are the right cosets of $K$, so $[F:K]=\mathrm{\mid }V(\widehat{\mathrm{\Gamma }})\mathrm{\mid }$ is finite. Because every closed based path of $\mathrm{\Gamma }$ is still closed in $\widehat{\mathrm{\Gamma }}$, one has $H\le K$.

Apply the same tree-loop argument to the finite $X$-regular graph $\widehat{\mathrm{\Gamma }}$. Its non-tree edges consist of those of $\mathrm{\Gamma }$ together with a disjoint set of added edges, so their loop labels form a free basis $B_H\bigsqcup C$ of $K$. By [L3], the subgroup generated by $B_H$ is a free factor of the subgroup generated by $B_H\bigsqcup C$, namely of $K$. Thus $H$ is a free factor of the finite-index subgroup $K$.

In the free group $F(a,b)$, let $\varphi :F(a,b)\to \mathbb{Z}$ send $a\mapsto 1$ and $b\mapsto 0$, and let $H=\ker \varphi$. The right cosets of $H$ are $H{a}^n$ for $n\in \mathbb{Z}$, and $\mathcal{T}=\{a^n:n\in \mathbb{Z}\}$ is a Schreier system.

For this system, the nontrivial Schreier generators are exactly the conjugates $a^{n}b{a}^{-n}$ for $n\in \mathbb{Z}$, because $s(a^n,a)=1$ and $s(a^n,b)=a^{n}b{a}^{-n}$. By [L1], this infinite family is a free basis of $H$.

A free basis cannot be finite when it contains infinitely many distinct elements, so $H$ is not finitely generated. This subgroup of the rank-two free group $F(a,b)$ refutes the statement.

Let $H\le F(a,b)$ be the index-two subgroup consisting of words with even exponent sum in $a$, and use the Schreier system $\mathcal{T}=\{1,a\}$ for its two right cosets.

The raw Schreier generators are $s(1,a)=1$, $s(1,b)=b$, $s(a,a)=a^2$, and $s(a,b)=ab{a}^{-1}$. So the full list already contains the identity element.

A free basis cannot contain the identity, whereas [L3] keeps only the nontrivial generators and thereby produces the actual basis $\{b,a^2,ab{a}^{-1}\}$. Hence the raw list is not always a free basis.

Consider the index-two subgroup $H\le F(a,b)$ consisting of words with even exponent sum in $a$. Here the ambient free group has rank $n=2$ and $d=[F(a,b):H]=2$.

By [L1], $\mathrm{rank}(H)=1+2(2-1)=3$, whereas the false formula predicts $dn=4$.

Since $3\mathrm{\ne }4$, this subgroup refutes the statement.

Let $G=F(a,b)=⟨a,b\mid ⟩$, and let $H\le G$ be the subgroup of words with even exponent sum in $a$. The two right cosets are $H$ and $Ha$, so both $\{1,a\}$ and $\{1,a^{-1}\}$ are Schreier systems.

With the Schreier system $\{1,a\}$, the nontrivial Schreier generators are $b$, $a^2$, and $ab{a}^{-1}$. With the Schreier system $\{1,a^{-1}\}$, the corresponding nontrivial Schreier generators are $b$, $a^2$, and $a^{-1}ba$. These are different generator lists.

The subgroup presented is the same subgroup $H$, but the rewritten generators depend on the chosen representatives. Therefore the Reidemeister-Schreier presentation does depend on the transversal.