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\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}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]
In this case, let $s$ be the coset representative of $a$ . Then $a=s(s^{-1}ae)$ , where $e$ is the identity element. Since the identity element is the coset representative of $H$ , $s^{-1}ae\in B$ so $s^{-1}ae\in D$ by definition, so $a\in SD$ .
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=(eas)^{-1}$ . By assumption, $as\in H$ , so $e$ is its coset representative, so $(eas)\in B$ , so $(eas)^{-1}\in D$ , again showing that $a^{-1}=s(eas)^{-1}\in SD$ .

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]
By the induction step, write $g'=sd$ , with $s\in S,d\in D^{n-1}$ . Then $g=asd$ . Let $s'$ be the coset representative of $as$ . Then, $g=s'(s'^{-1}as)d$ . By assumption, $s'^{-1}as\in B\subseteq D$ , so $g\in SDD^{n-1}=SD^{n}$ .
$g=a^{-1}g',a\in A$ : [SHOW MORE]
By the induction step, write $g'=sd$ , with $s\in S,d\in D^{n-1}$ . Then $g=a^{-1}sd$ . 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}as'$ , which is by definition in $B$ . Hence, $s'^{-1}a^{-1}s\in B^{-1}\subseteq D$ . Thus, $g\in SDD^{n-1}=SD^{n}$ .

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

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

Further information: Finding a generating set from a membership test