Открыть главное меню

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

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

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

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

Пусть  трансверсаль левых смежных классов  . Обозначим через   представителя смежного класса, в котором содержится  .

В таких обозначениях подгруппа   порождена множеством  .

ДоказательствоПравить

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

В алгоритме Шрайера-Симса теорема применяется для специфического случая когда   действует на множестве   и   является стабилизатором некоторого элемента  .

Между элементами орбиты   и трансверсалью   есть взаимо-однозначное соответствие. А именно, все элементы одного смежного класса переводят   в один и тот же элемент орбиты.

Поэтому обозначим через   элемент  , который переводит   в  , то есть,  . В таких обозначениях лемму можно записать следующим образом:  .

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

ПримечанияПравить

  1. Otto Schreier. Die Untergruppen der freien Gruppen // Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg. — 1927-12. — Т. 5, вып. 1. — С. 161–183. — ISSN 1865-8784 0025-5858, 1865-8784. — DOI:10.1007/bf02952517.
  2. Hall, Marshall 1910-1990 Verfasser. The Theory of Groups. — ISBN 9780486816906, 0486816907.