База (теория групп)

Позволять $G$ — конечная группа подстановок, действующая на множестве $\Omega$. Последовательность

$B=[\beta _{1},\beta _{2},...,\beta _{k}]$

из k различных элементов $\Omega$ является базой для G, если единственный элемент $G$ который исправляет все $\beta _{i}\in B$ поточечно является единичным элементом $G$.

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

Не у каждой группы есть база. В частности, если групповое действие не является точным , то базы не существует. Это связано с тем, что по определению неверного действия существует несколько элементов $G$ которые фиксируют каждый элемент в $B$ точечно.

Часто бывает полезно иметь дело с базами и мощными генераторными установками, поскольку с ними может быть легче работать, чем со всей группой. Группа может иметь небольшую базу по сравнению с множеством, на котором она действует. В «лучшем случае» база может иметь размер 1, как в случае с аддитивной группой целых чисел . С другой стороны, симметричные группы и знакопеременные группы имеют большие базы (симметричная группа имеет _Sn размер базы n - 1), и часто существуют специализированные алгоритмы, которые имеют дело с этими случаями.