Schreier’s lemma


Let G be a group, H a subgroupMathworldPlanetmathPlanetmath and T transversal of H in G. For every gG, we denote by g¯ the unique element tT such that Hg=Ht. We also insist that 1T. Under these conditions we can state Schreier’s lemma.

Lemma 1 (Schreier).

Given a group G=S, a subgroup H, and transversal T for G/H, then the set

U=H{ts(ts¯)-1:sS,tT}

generates H.

Proof.

[1] We show that H is generated by UU-1. We already know U is contained in H and we know every element hH is expressible as a word over S, as S generates G. So h=s1sk where siSS-1. Note that h=1s1sk which is of the form u1uiti+1si+1sk for ujUU-1, ti+1T and sjSS-1, where i=0. We assume for induction that h has this form for some i. Now we perform the sleight-of-hand.

h = u1uiti+1si+1sk
= u1uiti+1si+1(ti+1si+1¯)-1(ti+1si+1¯)si+2sk
= u1ui(ti+1si+1(ti+1si+1¯)-1)ti+1si+1¯si+2sk
= u1uiui+1ti+2si+2sk

by letting ui+1=ti+1si+1(ti+1si+1¯)-1 which is in UU-1, and ti+2=ti+1si+1¯T. At the end of the iteration we have replaced all the si’s with elements of UU-1 and the last element tkT. However, U lies in H so the product u1ukH and as hH and h=u1uktk we know tkH. As Htk=H, and tkT we now use the fact that 1T to assert that tk=1. So h is a word in UU-1 and thus U generates H. ∎

The lemma was discovered in the course of studying free groupsMathworldPlanetmath as a way to produce generatorsPlanetmathPlanetmathPlanetmathPlanetmathPlanetmath for a subgroup of a free group. The Reidemeister-Schreier theorem strengthened this result to produce a presentationMathworldPlanetmath for H given one for G and a transversal of G/H.

The lemma lead to an unexpected use in the 1970’s where it was rediscovered by various authors to solve certain problems in computational group theory. Sims used the result to find generators of the stabilizerMathworldPlanetmath of a point in a permutation groupMathworldPlanetmath. This method could then be repeated to find generators for each stabilizer in a stabilizer chain of a base of the group. A naive approach can result in exponentially many generators, so Sims’ algorithmMathworldPlanetmath additionally removes unnecessary generators along the way. This is now called the Schreier-Sims algorithm.

Independently a version of this algorithm was developed by Frust, Hopcroft, and Luks as a means to prove the polynomial-time complexity of various problems in finite groupMathworldPlanetmath theory and graph theoryMathworldPlanetmath. Many improvements followed including versions by Knuth, Jerum, and even a probabilistic nearly linear time method by Seress.

The lemma still finds use in non-finite groups as Schreier had intended. The associated algorithms have been repeatedly improved principally by the work of George Havas and Colin Ramsay.

References

  • 1 Seress, Ákos Permutation group algorithms, Cambridge Tracts in Mathematics, vol. 152, Cambridge University Press, Cambridge, 2003.
Title Schreier’s lemma
Canonical name SchreiersLemma
Date of creation 2013-03-22 15:53:55
Last modified on 2013-03-22 15:53:55
Owner Algeboy (12884)
Last modified by Algeboy (12884)
Numerical id 17
Author Algeboy (12884)
Entry type Theorem
Classification msc 20K27
Synonym Schreier-Sims
Related topic LiftsTransversals
Related topic FindingTheOrderOfAGroup