# Schreier's lemma

## Statement

### Constructive statement

Suppose is a subgroup of a group , and is a left transversal of in with the property that the representative of the coset itself is the identity element. Suppose is a generating set for . Then, define as the set of all elements in that can be written as where and are in and is in .

Then, is a generating set for .

### 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 and are both finite sets, so is .

## Related facts

### Applications

- Local finiteness is extension-closed: A locally finite group is a group in which every finitely generated subgroup is finite. If is a group with a locally finite normal subgroup such that is also locally finite, then 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 are algebras over a commalg:Noetherian ring , with finitely generated as a -algebra and finitely generated as an -module, then is finitely generated as a -algebra. Here, being
*finitely generated*as a -algebra plays the analogous role to being a finitely generated group, and being finitely generated as an -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 in terms of , with a possible leading term from . If the word happens to be in the subgroup, the leading term from must be trivial, and thus, the word originally written in terms of is expressible in terms of .

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

**Given**: A group with a subgroup having a left transversal . is a generating set for . is defined as the set of all elements of expressible as where and .

**To prove**: .

**Proof**: Let be the set of all elements of and their inverses. Let be the set of all elements of and their inverses. We will prove that for any :

,

where denote the elements of expressible as products of length at most from elements of , respectively.

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

- The element is an element : [SHOW MORE]
- The element is , with : [SHOW MORE]

We now give the induction step.

Suppose . Then we can either write or write for . We examine both cases.

Thus, we have established that:

.

Now, any element of is in particular an element of , and since generates , every element of is in . Thus, for any element , we have:

.

But since , we have , so . In particular, this yields . But the coset representative in is by assumption trivial, so we get . Thus, . Since was arbitrary, this shows that every element of is in the subgroup generated by .

### 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 where and .

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 on in terms of the specified generating set of .

`Further information: Finding a generating set from a membership test`