Does the Shalen-Wagreich lemma holds for non-symmetric generating sets?

Question

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 and $k=2d-1$. But I wonder whether it still holds when $S$ is non-symmetric? Or is there a counterexample?

Answer 1

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 [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 $\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, 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