How to find generators for subgroups of free groups?

Question

For simplicity, consider $F_2$ a free group generated by two elements $\{a,b\}$. Let's say I am given a finite index subgroup $H\subset F_2$, for example $H=\{a^{i_1}b^{j_1}...a^{i_n}b^{j_n}:\,i_1+...+i_n=0\,(\mathrm{mod}\, 2)\}=\ker(f:F_2\to\mathbb Z/2\mathbb Z\,\,\text{by}\,\,a\mapsto1,b\mapsto0\}$. By Nielsen-Schreier theorem, this subgroup is free and is generated by $3$ elements. I figured out that one possible choice can be given by $\{aba^{-1},aba,b\}$, but I could not prove this rigorously.

(1) How to prove that the two subgroups are the same?

(2) While I was thinking about (1), I realized that I could not even show that $\langle aba^{-1},aba,b\rangle$ is normal. So a related question is, given a finite set of generators in $F_2$, is there a general way to determine whether it generates a normal subgroup?

I tried to think about both questions in terms of covering spaces and Cayley graphs, but my knowledge on both subjects are limited.

Answer 1

Most proofs of the Nielsen-Schreier theorem proceed by following a recipe for finding generators of the subgroup $H$ in $F$ and then proving that they are free generators.

You start by finding a (right) Schreier (= prefix closed) transversal of $H$ in $F$. Let $X$ be a set of free generators of $F$ and, for $g \in F$, let $\bar{g}$ denote the unique element of $U$ with $Hg = H\bar{g}$.

Then the subset of non-identity elements of the set $$\{ux \overline{ux}^{-1} : u \in U, x \in X \}$$ freely generates $H$.

In your example, we can take $U = \{1,a\}$, leading to the free generating set $\{b,a^2,aba^{-1}\}$ of $H$, which is the same as that found in the answer by kabenyuk.

You can check normality of a subgroup $H$ of $F$ by constructing the permutation representation of $F$ on the cosets of $H$ in $F$, and then checking whether the generators of $H$ all act trivially on this set.

The above method of testing for normality is fine for subgroups of moderately small finite index, but for arbitrary finitely generated subgroups, you can use the fact that membership testing in such subgroups is possible (using methods based on Stallings' Folding) and then testing membership of $xgx^{-1}$ and $x^{-1}gx$ in $H$ for all $x \in X$ and generators $g$ of $H$.

Answer 2

There is a simpler system of generating groups $H=\langle aba^{-1},a^2,b\rangle$. How to check it? Since $aba^{-1}\cdot a^2=aba$, then $H\leq\langle aba^{-1},a^2,b\rangle$. The inverse inclusion follows from the equality $a^2=(aba^{-1})^{-1}\cdot aba$.

The answers to your two questions follow from the decidability of the occurrence problem for free groups. This problem was solved by J. Nielsen in 1921. I think his algorithms are stated in books: Lyndon R.C.,Schupp P.E.,Combinatorial group theory, Magnus W., Karrass A., Solitar D.,Combinatorial group theory.

---

To answer @Accumulation's question I will add a few words. Now we have three subgroups: $$ \langle aba^{-1},aba,b\rangle,\ \langle aba^{-1},a^2,b\rangle,\ \mathrm{and}\ \operatorname{Ker}(f). $$ Here $f:F_2\rightarrow\mathbb{Z}_2$, $f(a)=1$, $f(b)=0$. We know that $$ \langle aba^{-1},aba,b\rangle=\langle aba^{-1},a^2,b\rangle, $$ $$ \langle aba^{-1},a^2,b\rangle\leq\operatorname{Ker}(f), $$ $$ |F_2:\operatorname{Ker}(f)|=2. $$

Let $B=\langle aba^{-1},a^2,b\rangle$. By induction on the word length of $F_2$ we prove that $F_2=B\cup Ba$.

Let $w\in F_2$.

1. $w=w'a$, $w'\in B$ $\Rightarrow$ $w\in Ba$.

2. $w=w'a$, $w'\in Ba$ $\Rightarrow$ $w'=w''a$, $w''\in B$ $\Rightarrow$ $w=w''\cdot a^2\in B$.

3. $w=w'b$, $w'\in B$ $\Rightarrow$ $w=w'\cdot b\in B$.

4. $w=w'b$, $w'\in Ba$ $\Rightarrow$ $w'=w''a$, $w''\in B$ $\Rightarrow$ $w=w''\cdot ab=w''\cdot aba^{-1}\cdot a\in Ba$.

The cases $w=w'a^{-1}$ and $w=w'b^{-1}$ are similarly.

It follows that $$ |F_2:\langle aba^{-1},a^2,b\rangle|=2. $$ So $\langle aba^{-1},a^2,b\rangle=\operatorname{Ker}(f)$.