Лемма Шрейера

В математике лемма Шрайера — это теорема теории групп, в алгоритме Шрайера-Симса , а также для поиска представления подгруппы используемая .

Заявление

Предполагать $H$ является подгруппой ​ $G$, который конечно генерируется с помощью набора генераторов $S$, то есть, $G=\langle S\rangle$.

Позволять $R$ правой трансверсалой быть $H$ в $G$. Другими словами, $R$ это (образ) часть факторкарты $G\to H\backslash G$, где $H\backslash G$ обозначает множество правых смежных классов $H$ в $G$.

Определение дано с учетом того, что $g\in G$, ${\overline {g}}$ является выбранным представителем в поперечном $R$ из одноклассника $Hg$, то есть,

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

Затем $H$ генерируется набором

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

Отсюда, в частности, из леммы Шрайера следует, что каждая подгруппа конечного индекса конечно порожденной группы снова конечно порождена.

Пример

Группа Z ₃ = Z /3 Z циклическая. По Кэли теореме Z ₃ является подгруппой симметрической группы S ₃ . Сейчас,

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

где $e$ это тождественная перестановка. Примечание S ₃ = $\scriptstyle \langle${ с ₁ = (1 2), с ₂ = (1 2 3) } $\scriptstyle \rangle$.

Z ₃ имеет только два смежных класса, Z ₃ и S ₃ \ Z ₃ , поэтому мы выбираем трансверсаль { t ₁ = e , t ₂ =(1 2) }, и мы имеем

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

Окончательно,

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

Таким образом, по лемме Шрайера о подгруппе { e, (1 2 3) } порождает Z ₃ , но наличие единицы в порождающем наборе избыточно, поэтому ее можно удалить, чтобы получить другой порождающий набор для Z ₃ , { (1 2 3 ) } (как и ожидалось).

Ссылки

• Сересс, А. Алгоритмы группы перестановок. Издательство Кембриджского университета, 2002.