Misplaced Pages

In abstract algebra, especially in the area of group theory, a strong generating set of a permutation group is a generating set that clearly exhibits the permutation structure as described by a stabilizer chain. A stabilizer chain is a sequence of subgroups, each containing the next and each stabilizing one more point.

Let ${\displaystyle G\leq S_{n}}$ be a group of permutations of the set ${\displaystyle \{1,2,\ldots ,n\}.}$ Let

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

be a sequence of distinct integers, ${\displaystyle \beta _{i}\in \{1,2,\ldots ,n\},}$ such that the pointwise stabilizer of ${\displaystyle B}$ is trivial (i.e., let ${\displaystyle B}$ be a base for ${\displaystyle G}$). Define

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

and define ${\displaystyle G^{(i)}}$ to be the pointwise stabilizer of ${\displaystyle B_{i}}$. A strong generating set (SGS) for G relative to the base ${\displaystyle B}$ is a set

${\displaystyle S\subseteq G}$

such that

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

for each ${\displaystyle i}$ such that ${\displaystyle 1\leq i\leq r}$.

The base and the SGS are said to be non-redundant if

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

for ${\displaystyle i\neq j}$.

A base and strong generating set (BSGS) for a group can be computed using the Schreier–Sims algorithm.

References

• A. Seress, Permutation Group Algorithms, Cambridge University Press, 2002.

• Computational group theory
• Permutation groups