Schreier's lemma

From Groupprops
Jump to: navigation, search

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.

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]
  • 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

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