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} a s$ 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 \leq 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.

Related ideas

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} a s$ where $s^{'}, s \in S$ and $a \in A$ .

To prove: $⟨ B ⟩ = 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 S D^{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 $S D$ . We make two cases:

The element is an element $a \in A$ : [SHOW MORE]
In this case, let $s$ be the coset representative of $a$ . Then $a = s (s^{- 1} a e)$ , where $e$ is the identity element. Since the identity element is the coset representative of $H$ , $s^{- 1} a e \in B$ so $s^{- 1} a e \in D$ by definition, so $a \in S D$ .
The element is $a^{- 1}$ , with $a \in A$ : [SHOW MORE]
In this case, let $s$ be the coset representative of $a^{- 1}$ . Then, $a^{- 1} = s (s^{- 1} a^{- 1} e)$ . We can write $s^{- 1} a^{- 1} e = (e a s)^{- 1}$ . By assumption, $a s \in H$ , so $e$ is its coset representative, so $(e a s) \in B$ , so $(e a s)^{- 1} \in D$ , again showing that $a^{- 1} = s (e a s)^{- 1} \in S D$ .

We now give the induction step.

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

$g = a g^{'}, a \in A$ : [SHOW MORE]
By the induction step, write $g^{'} = s d$ , with $s \in S, d \in D^{n - 1}$ . Then $g = a s d$ . Let $s^{'}$ be the coset representative of $a s$ . Then, $g = s^{'} (s'^{- 1} a s) d$ . By assumption, $s'^{- 1} a s \in B \subseteq D$ , so $g \in S D D^{n - 1} = S D^{n}$ .
$g = a^{- 1} g^{'}, a \in A$ : [SHOW MORE]
By the induction step, write $g^{'} = s d$ , with $s \in S, d \in D^{n - 1}$ . Then $g = a^{- 1} s d$ . Suppose $s^{'}$ is the coset representative of $a^{- 1} s$ . Then, $g = s^{'} (s'^{- 1} a^{- 1} s) d$ . The middle term $s'^{- 1} a^{- 1} s$ is the inverse of $s^{- 1} a s^{'}$ , which is by definition in $B$ . Hence, $s'^{- 1} a^{- 1} s \in B^{- 1} \subseteq D$ . Thus, $g \in S D D^{n - 1} = S D^{n}$ .

Thus, we have established that:

$C^{n} \subseteq S D^{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 = s d, 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 = h d^{- 1} \in H$ . But the coset representative in $H$ is by assumption trivial, so we get $h \in D^{n}$ . Thus, $h \in ⟨ B ⟩$ . 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

PLACEHOLDER FOR INFORMATION TO BE FILLED IN: [SHOW MORE]

As an algorithm

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} a s$ 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$ .

Further information: Finding a generating set from a membership test