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

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

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

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

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

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

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

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

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

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

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

См. также

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