Let $G$ be a group and $H$ a subgroup with finite index $d$. Then for any finite generating set $S$ of $G$, does $S^{\le k}$ contain a generating set of $H$ where $k$ is a constant depending only on $d$? When $S$ is symmetric, i.e. $S=S^{-1}$, the conclusion holds by [Shalen-Wagreich's Lemma 3.4](https://www.jstor.org/stable/2154149?origin=crossref) and $k=2d-1$. But I wonder whether it still holds when $S$ is non-symmetric? Or is there a counterexample?



Does the Shalen-Wagreich lemma holds for non-symmetric generating sets?
The answer is **yes**, with $k = 2d - 1$ as a sharp upper bound.


This follows from a classical combinatorial result of Otto Schreier known as [Schreier's lemma](https://en.wikipedia.org/wiki/Schreier%27s_lemma) [1, Proof of Proposition I.3.7].
These ideas of Otto Schreier go back to 1927 and already establish [2, Lemma 3.4] of Peter Shalen and Philip Wagreich
(1992), that is, they are sufficient to show that $2d - 1$ is an upper bound when $S = S^{-1}$.
In this case, Peter Shalen and Philip Wagreich have proved in addition that $2d - 1$ is a sharp upper bound [2, Remark 3.5].


For $S$ a subset of a group $G$ and $n \in \mathbb{N}\_{\ge 0}$,
we denote by $S^{\le n}$ the set of elements of $G$
which can be written as product of at most $n$ elements of $S$.



> 
> **Claim.** Let $G$ be a group and let $H$ be a subgroup of finite index $d$ in $G$. Let $S$ be a generating subset of $G$.
> Then $H$ is generated by a subset of $S^{\le 2d -1 }$.
> 
> 
> 


The proof of the above claim is a variation on [2, Proof of Lemma 3.4].
We shall rely on the following key fact, which is certainly well-known: there is a spanning sub-tree of the Schreier graph of $H$ in $G$ with respect to $S$, endowed with an "affluent" labeling: the edges in every edge path joining the root to a leaf are labelled by the element of $S$, as opposed to elements of $S \cup S^{-1}$ in the original proof.


**Definition.** Let $G$ be a free group with basis $S$ and let $H$ be a subgroup of $G$. The *[Schreier coset graph](https://en.wikipedia.org/wiki/Schreier_coset_graph)* $\operatorname{Schreier}\_{G, S}(H)$ of $G$ in $H$ with respect to $S$ is the directed and labelled multi-graph whose vertices are the right cosets $Hg$ for $g \in G$ and there is an edge labelled by $s$ from $Hg$ to $Hgs$ for every $g \in G$ and $s \in S$ (distinct labels yield distinct edges).


The above definition agrees with the covering of a bouquet of circles labelled by the elements of $S$ which is considered in the proof of [2, Lemma 3.4].



> 
> **Lemma 1.** Let $G$ be a free group with basis $S$, let $H$ be subgroup of finite index $d$ in $G$. Let $\Gamma = \operatorname{Schreier}\_{G, S}(H)$.
> Then $\Gamma$ is [strongly connected](https://en.wikipedia.org/wiki/Strongly_connected_component), i.e, every pair of vertices can be joined by a directed path.
> 
> 
> 



> 
> *Proof of Lemma 1.* Let $g \in G, s \in S$. Since $H$ has index $d$ in $G$, there is a smallest integer $n = n(Hg) \in \{1, \dots, d\}$ such that $Hgs^n = Hg$, equivalently,
> $Hgs^{-1} = Hgs^{n - 1}$. Consider now two vertices $Hg$ and $Hg'$ with $g, g' \in G$ and write $g^{-1}g'$ as a word on $S \cup S^{-1}$.
> It is sufficient prove that $Hg$ and $Hg'$ are connected by a directed path if the length of $w$ is $1$, as the result follows by immediate induction.
> If $w = s \in S$, the result is obvious. If $w = s^{-1}$ for some $s \in S$, then the directed path defined by the sequence of vertices $Hg, Hgs, \dots, Hgs^{n(Hg)-1} = Hgs^{-1}$ joins $Hg$ to $Hg' = Hgs^{-1}$.
> 
> 
> 



> 
> **Lemma 2.** Let $G$ be a free group with basis $S$, let $H$ be subgroup of finite index $d$ in $G$. Let $\Gamma = \operatorname{Schreier}\_{G, S}(H)$.
> Then for every vertex $v$ of $\Gamma$, there is an *affluent* directed spanning tree $T$ of $\Gamma$ rooted at $v$, i.e., $T$ is a directed tree such that every leaf of
> $T$ can be connected to $v$ by a directed path starting from $v$.
> 
> 
> 



> 
> *Proof of Lemma 2.* Since $\Gamma$ is finite, we can find a maximal affluent subtree $T$ of $\Gamma$ rooted at $v$. It only remains to show that $Hg$ is vertex of $T$ for every
> $g \in \Gamma$. Reasoning by contradiction, we assume that there is $g \in G$ such that $Hg$ is not a vertex of $T$. Let $p$ be a directed path joining $Hg$ to $T$ with shortest length. (Such a path exists by Lemma 1). Adjoining $p$ to $T$ results in a larger affluent subtree, which contradicts the maximality of $T$.
> 
> 
> 


We are now in position to prove the main claim.



> 
> *Proof of the Claim.* We can assume, without loss of generality, that $G$ is a free group with basis $S$. By [1, Proposition III.3.1], the subgroup $H$ identifies with the fundamental group of $\Gamma = \operatorname{Schreier}\_{G, S}(H)$ with base point $H = H \cdot 1$. Let $T$ be an affluent spanning tree of $\Gamma$ rooted at $H$ given by Lemma 2.
> For $v$ a vertex of $\Gamma$, we denote by $p\_v$
> the unique directed path joining $H$ to $v$ within $T$. Then $H$ is generated by the homotopy classes of the loops $\gamma(Hg, s) = p\_{Hg} \cdot s \cdot p\_{Hgs}^{-1}$ with $g \in G$ [1, Proof of Proposition III.2.1].
> Now let $q\_{s, Hg}$ denote a directed path from $Hgs$ to $Hg$ in $\Gamma$ of length at most $d - 1$.
> Then $H$ is also generated by the loops $\gamma(Hg, s) \cdot p\_{Hgs} \cdot q\_{s,Hg} = p\_{Hg} \cdot s \cdot q\_{s,Hg}$ and $p\_{Hgs} \cdot q\_{s, Hg}$ for $g \in G, s \in S$. As the latter generators are words over $S$ of length at most $2d - 1$, the proof is complete.
> 
> 
> 




---


[1] R. Lyndon and P. Schupp, "Combinatorial Group Theory", 1977.  

[2] P. Shalen and P. Wagreich, "Growth Rates, Zp-Homology, and Volumes of Hyperbolic 3-Manifolds", 1992


