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

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

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

Формулировка

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

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

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

Формулировка для орбит

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

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

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

См. также

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