# Schreier's lemma

## Statement

### Constructive statement

Suppose $H$ is a subgroup of a group $G$, and $S$ is a left transversal of $H$ in $G$ with the property that the representative of the coset $H$ itself is the identity element. Suppose $A$ is a generating set for $G$. Then, define $B$ as the set of all elements in $H$ that can be written as $s'^{-1}as$ where $s'$ and $s$ are in $S$ and $a$ is in $A$.

Then, $B$ is a generating set for $H$.

### Factual statement

Any subgroup of finite index in a finitely generated group (see also: subgroup of finite index in finitely generated group) is finitely generated. This follows because when $A$ and $S$ are both finite sets, so is $B$.

## Related facts

### Applications

• Local finiteness is extension-closed: A locally finite group is a group in which every finitely generated subgroup is finite. If $G$ is a group with a locally finite normal subgroup $N$ such that $G/N$ is also locally finite, then $G$ is locally finite. The proof of this uses Schreier's lemma.
• Freeness is subgroup-closed: Any subgroup of a free group is free, and moreover, if the subgroup has finite index, the number of generators of the subgroup is given as a function of the number of generators of the whole group, and the index of the subgroup. The proof of this is based on a closer analysis of the constructive statement of Schreier's lemma.

### Analogues in other algebraic structures

• Artin-Tate lemma: This states that if $A \le B$ are algebras over a commalg:Noetherian ring $R$, with $B$ finitely generated as a $R$-algebra and $B$ finitely generated as an $A$-module, then $A$ is finitely generated as a $R$-algebra. Here, being finitely generated as a $R$-algebra plays the analogous role to being a finitely generated group, and $B$ being finitely generated as an $A$-module plays the analogous role to a subgroup of finite index.

## Proof

### Proof idea

The key idea is to rewrite words originally in terms of $A$ in terms of $B$, with a possible leading term from $S$. If the word happens to be in the subgroup, the leading term from $S$ must be trivial, and thus, the word originally written in terms of $A$ is expressible in terms of $B$.

### Proof details in the form of a proof by induction

Given: A group $G$ with a subgroup $H$ having a left transversal $S$. $A$ is a generating set for $G$. $B$ is defined as the set of all elements of $H$ expressible as $s'^{-1}as$ where $s',s \in S$ and $a \in A$.

To prove: $\langle B \rangle = H$.

Proof: Let $C = A \cup A^{-1}$ be the set of all elements of $A$ and their inverses. Let $D = B \cup B^{-1}$ be the set of all elements of $B$ and their inverses. We will prove that for any $n$:

$C^n \subseteq SD^n$,

where $C^n, D^n$ denote the elements of $G$ expressible as products of length at most $n$ from elements of $C$, $D$ respectively.

We prove this claim by induction on $n$. Let's first do the case $n = 1$. We need to show that any element of $C$ is in $SD$. We make two cases:

• The element is an element $a \in A$: [SHOW MORE]
• The element is $a^{-1}$, with $a \in A$: [SHOW MORE]

We now give the induction step.

Suppose $g \in C^n$. Then we can either write $g = ag'$ or write $g = a^{-1}g'$ for $a \in A, g' \in C^{n-1}$. We examine both cases.

• $g = ag', a \in A$: [SHOW MORE]
• $g = a^{-1}g', a \in A$: [SHOW MORE]

Thus, we have established that:

$C^n \subseteq SD^n$.

Now, any element of $H$ is in particular an element of $G$, and since $A$ generates $G$, every element of $H$ is in $C^n$. Thus, for any element $h \in H$, we have:

$h = sd, s \in S, d \in D^n$.

But since $D \subseteq H$, we have $D^n \subseteq H$, so $d \in H$. In particular, this yields $s = hd^{-1} \in H$. But the coset representative in $H$ is by assumption trivial, so we get $h \in D^n$. Thus, $h \in \langle B \rangle$. Since $h$ was arbitrary, this shows that every element of $H$ is in the subgroup generated by $B$.

### Proof details in the form of writing down expressions

Schreier's lemma can give an algorithm to compute a generating set for a subgroup starting from a generating set of the whole group and a system of coset representatives for the subgroup. The idea is to traverse all tuples of the form $s'^{-1}as$ where $a \in A$ and $s,s' \in S$.
The problem of determining a system of coset representatives is solved by means of a bradth-first search in the Cayley graph of the action of $G$ on $G/H$ in terms of the specified generating set of $G$.