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

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

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

ФормулировкаПравить

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

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

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

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

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

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

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

См. такжеПравить

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