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

Лемма Шрайера — теорема из теории групп, использующаяся в алгоритме Шрайера-Симса. Теорема была доказана Отто Шрайером в 1927 году^[1].

Из теоремы следует, что у конечно порождённой группы любая подгруппа с конечным индексом также является конечно порождённой^[2].

Пусть ${\displaystyle H}$ — некоторая подгруппа конечно порождённой группы ${\displaystyle G}$ с порождающим множеством ${\displaystyle S}$, то есть, ${\displaystyle G=\langle S\rangle }$.

Пусть ${\displaystyle R=G/H}$ — трансверсаль левых смежных классов ${\displaystyle gH}$. Обозначим через ${\displaystyle {\overline {x}}}$ представителя смежного класса, в котором содержится ${\displaystyle x\in G}$.

В таких обозначениях подгруппа ${\displaystyle H}$ порождена множеством ${\textstyle \{({\overline {sg}})^{-1}sg:g\in R,s\in S\}}$.

В алгоритме Шрайера — Симса теорема применяется для специфического случая когда ${\displaystyle G}$ действует на множестве ${\displaystyle \Omega }$ и ${\displaystyle H=G_{\omega }}$ является стабилизатором некоторого элемента ${\displaystyle \omega \in \Omega }$.

Между элементами орбиты ${\displaystyle G\omega }$ и трансверсалью ${\displaystyle G/G_{\omega }}$ есть взаимо-однозначное соответствие. А именно, все элементы одного смежного класса переводят ${\displaystyle \omega }$ в один и тот же элемент орбиты.

Поэтому обозначим через ${\displaystyle {\overline {\alpha }}}$ элемент ${\displaystyle G/G_{\omega }}$, который переводит ${\displaystyle \omega }$ в ${\displaystyle \alpha }$, то есть, ${\displaystyle {\overline {\alpha }}\omega =\alpha }$. В таких обозначениях лемму можно записать следующим образом: ${\textstyle G_{\omega }=\langle \{({\overline {s\alpha }})^{-1}s{\overline {\alpha }}|\alpha \in G_{\omega },s\in S\}\rangle }$.

• Алгоритм Шрайера — Симса