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

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

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

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

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

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

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

${\ Displaystyle S \ substeq G}$

такой, что

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

для каждого такого, что .${\ displaystyle i}$${\ Displaystyle 1 \ Leq я \ Leq г}$

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

${\ Displaystyle G ^ {(я)} \ neq G ^ {(j)}}$

для .${\ displaystyle i \ neq j}$

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

Ссылки [ править ]

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