Мощная генераторная установка

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

Позволять $G\leq S_{n}$ — группа перестановок множества $\{1,2,\ldots ,n\}.$ Позволять

$B=(\beta _{1},\beta _{2},\ldots ,\beta _{r})$

быть последовательностью различных целых чисел , $\beta _{i}\in \{1,2,\ldots ,n\},$ такой, что стабилизатор точечный $B$ тривиально (т.е. пусть $B$ быть основой для $G$). Определять

$B_{i}=(\beta _{1},\beta _{2},\ldots ,\beta _{i}),\,$

и определить $G^{(i)}$ быть точечным стабилизатором $B_{i}$. Сильная генераторная установка (SGS) для G относительно базы $B$ это набор

$S\subseteq G$

такой, что

$\langle S\cap G^{(i)}\rangle =G^{(i)}$

для каждого $i$ такой, что $1\leq i\leq r$.

База и SGS называются неизбыточными, если

$G^{(i)}\neq G^{(j)}$

для $i\neq j$.

Базовый и сильный порождающий набор (BSGS) для группы можно вычислить с помощью алгоритма Шрайера – Симса .

Ссылки

• А. Сересс, Алгоритмы группы перестановок , издательство Кембриджского университета, 2002.