Schreiersovo lemma - Schreiers lemma - Wikipedia

V matematice Schreierovo lemma je teorém v teorie skupin použitý v Algoritmus Schreier – Sims a také pro nalezení a prezentace a podskupina.

Prohlášení

Předpokládat ${ displaystyle H}$ je podskupina z ${ displaystyle G}$, který je definitivně generován generující sadou ${ displaystyle S}$, to znamená, G = ${ displaystyle scriptstyle langle S rangle}$.

Nechat ${ displaystyle R}$ mít pravdu příčný z ${ displaystyle H}$ v ${ displaystyle G}$. Jinými slovy, ${ displaystyle R}$ je (obraz) a sekce kvocientové mapy ${ displaystyle G to H zpětné lomítko G}$, kde ${ displaystyle H zpětné lomítko G}$ označuje množinu správné kosety z ${ displaystyle H}$ v ${ displaystyle G}$.

Děláme definici, která je uvedena ${ displaystyle g}$∈${ displaystyle G}$, ${ displaystyle { overline {g}}}$ je zvolený zástupce v příčném směru ${ displaystyle R}$ coset ${ displaystyle Hg}$, to znamená,

${ displaystyle g v H { overline {g}}.}$

Pak ${ displaystyle H}$ je generován množinou

${ displaystyle {rs ({ overline {rs}}) ^ {- 1} | r v R, s v S }}$

Příklad

Pojďme prokázat evidentní fakt, že skupina Z₃ = Z/3Z je skutečně cyklický. Přes Cayleyho věta, Z₃ je podskupinou symetrická skupina S₃. Nyní,

${ 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) }}$

kde ${ displaystyle e}$ je permutace identity. Poznámka S₃ = ${ displaystyle scriptstyle langle}${ s₁=(1 2), s₂ = (1 2 3) }${ displaystyle scriptstyle rangle}$.

Z₃ má jen dva kosety, Z₃ a S₃ \ Z₃, takže vybereme příčný { t₁ = E, t₂= (1 2)}, a máme

${ displaystyle { begin {matrix} t_ {1} s_ {1} = (1 2), & quad { text {so}} 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 {matrix}}}$

Konečně,

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

Schreierovým podskupinovým lemmatem se tedy vygeneruje {e, (1 2 3)} Z₃, ale mít identitu v generující sadě je nadbytečné, takže ji můžeme odebrat a získat další generující sadu pro Z₃, {(1 2 3)} (podle očekávání).

Reference

• Seress, A. Permutation Group Algorithms. Cambridge University Press, 2002.