Lemat Schreiera

W matematyce lemat Schreiera jest twierdzeniem z teorii grup używanym w algorytmie Schreiera-Simsa , a także do znajdowania prezentacji podgrupy .

Oświadczenie

Załóżmy, że $jest$ podgrupą , która jest generowana w sposób skończony za pomocą zestawu generującego $\ langle S$$=$ sol $⟩$ \ Displaystyle G .

Niech ${\ displaystyle R}$ będzie prawą poprzeczną względem ${\ displaystyle H}$ w ${\ displaystyle G}$ . Innymi słowy, $\ Displaystyle R$ (obrazem) fragmentem mapy ilorazowej $R$${\ Displaystyle G \ do H \ ukośnikiem odwrotnym G}$ gdzie zbiór prawych cosetów H ${\ displaystyle H}$ w ${\ displaystyle G}$ .

Dokonujemy definicji, że dany $jest$ wybranym przedstawicielem w poprzecznym zestawie ${$$\ displaystyle R$${\ Displaystyle Hg}$$\$ displaystyle , czyli

${\ displaystyle g \ w H. {\ overline {g}}.}$

Następnie zestaw jest generowany przez ${\ displaystyle H}$

${\ Displaystyle \ {rs ({\ overline {rs}}) ^ {-1} | r \ w R, s \ w S \}.}$

Stąd w szczególności lemat Schreiera implikuje, że każda podgrupa skończonego indeksu grupy skończenie generowanej jest ponownie generowana skończenie.

Przykład

Ustalmy ewidentny fakt, że grupa Z ₃ = Z /3 Z jest rzeczywiście cykliczna. Z twierdzenia Cayleya Z ₃ jest podgrupą grupy symetrycznej S ₃ . Teraz,

${\ Displaystyle \ mathbb {Z} _ {3} = \ {e, (1 \ 2 \ 3), (1 \ 3 \ 2) \}}$

${\ Displaystyle S_ {3} = \ {e, (1 \ 2), (1 \ 3), (2 \ 3), (1 \ 2 \ 3), (1 \ 3 \ 2) \} }$

gdzie $.$ permutacją tożsamości Uwaga S ₃ = ${\ Displaystyle \ scriptstyle \ langle}$ { s ₁ = (1 2), s ₂ = (1 2 3)} ${\ Displaystyle \ scriptstyle \ rangle}$ .

Z ₃ ma tylko dwa współzbiory, Z ₃ i S ₃ \ Z ₃ , więc wybieramy poprzeczny { t ₁ = e , t ₂ = (1 2) } i mamy

${\ Displaystyle {\ rozpocząć {macierz} t_ {1} s_ {1} = (1 \ 2) i \ quad {\ tekst {tak}} \ quad & {\ overline {t_ {1} s_ {1}} }=(1\ 2)\\t_{1}s_{2}=(1\ 2\ 3)&\quad {\text{so}}\quad &{\overline {t_{1}s_{2 }}}=e\\t_{2}s_{1}=e,&\quad {\text{so}}\quad &{\overline {t_{2}s_{1}}}=e\\t_ {2}s_{2}=(2\ 3),&\quad {\text{so}}\quad &{\overline {t_{2}s_{2}}}=(1\ 2).\\ \end{macierz}}}$

Wreszcie,

${\ Displaystyle t_ {1} s_ {1} {\ overline {t_ {1} s_ {1}}} ^ {-1} = e}$

${\ Displaystyle t_ {1} s_ {2} {\ overline {t_ {1} s_ {2}}} ^ {- 1} = (1 \ 2 \ 3 )}$

${\ Displaystyle t_ {2} s_ {1} {\ overline {t_ {2} s_ {1}}} ^ {- 1} = e}$

${\ Displaystyle t_ {2} s_ {2} {\ overline {t_ {2} s_ {2}}} ^ {-1} = (1 \ 2 \ 3).}$

Zatem na mocy lematu podgrupy Schreiera { e, (1 2 3) } generuje Z ₃ , ale posiadanie tożsamości w zbiorze prądotwórczym jest zbędne, więc możemy go usunąć, aby otrzymać inny zespół prądotwórczy dla Z ₃ , { (1 2 3 ) } (zgodnie z oczekiwaniami).

• Seress, A. Algorytmy grup permutacji. Cambridge University Press, 2002.