Лемма Шрайера — теорема из теории групп, использующаяся в алгоритме Шрайера-Симса. Теорема была доказана Отто Шрайером в 1927 году.
Из теоремы следует, что у конечно порождённой группы любая подгруппа с конечным индексом также является конечно порождённой.
Формулировка Пусть — некоторая подгруппа конечно порождённой группы с порождающим множеством , то есть, .
Пусть — трансверсаль левых смежных классов . Обозначим через представителя смежного класса, в котором содержится .
В таких обозначениях подгруппа порождена множеством .
Доказательство
Формулировка для орбит В алгоритме Шрайера — Симса теорема применяется для специфического случая когда действует на множестве и является стабилизатором некоторого элемента .
Между элементами орбиты и трансверсалью есть взаимо-однозначное соответствие. А именно, все элементы одного смежного класса переводят в один и тот же элемент орбиты.
Поэтому обозначим через элемент , который переводит в , то есть, . В таких обозначениях лемму можно записать следующим образом: .
См. также Алгоритм Шрайера — Симса
Примечания
Категория:Вычислительная теория групп