Schreiers lemma

Inom matematik är Schreiers lemma ett teorem i gruppteori som används i Schreier–Sims-algoritmen och även för att hitta en presentation av en undergrupp .

Påstående

Antag att $H$ är en undergrupp av $G$ , som ändligt genereras med genereringsmängden ${\displaystyle S} ,$ det vill säga $G=\langle S\rangle$ .

Låt $R$ vara en höger transversal av $H$ i $G$ . Med andra ord, $R$ är (bilden av) ett avsnitt av kvotmappen $G\to H\backslash G$ , där $H\backslash G}$ betecknar uppsättningen av höger cosets av $H$ i $G$ .

Vi gör definitionen att givet $g$ ∈ $G$ , ${\overline {g}}$ är den valda representanten i den tvärgående $R$ av coset $Hg$ , det vill säga,

$g\in H{\overline {g}}.$

Sedan genereras $H$ av uppsättningen

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

Därför innebär i synnerhet Schreiers lemma att varje undergrupp av ändligt index i en ändligt genererad grupp återigen genereras ändligt.

Exempel

Låt oss fastställa det uppenbara faktum att gruppen Z ₃ = Z /3 Z verkligen är cyklisk. Via Cayleys teorem är Z ₃ en undergrupp till den symmetriska gruppen S ₃ . Nu,

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

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

där $e$ är identitetspermutationen. Notera S ₃ = $\scriptstyle \langle$ { s ₁ =(1 2), s ₂ = (1 2 3) } $\scriptstyle \rangle$ .

Z ₃ har bara två coset, Z ₃ och S ₃ \ Z ₃ , så vi väljer tvärgående { t ₁ = e , t ₂ =(1 2) }, och vi har

${\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{matris}}$

Till sist,

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

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

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

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

Sålunda, enligt Schreiers undergruppslemma, genererar { e, (1 2 3) } Z ₃ , men att ha identiteten i genereringsmängden är redundant, så vi kan ta bort den för att erhålla en annan genereringsmängd för Z ₃ , { (1 2 3 ) } (som förväntat).

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