Strong generating set

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 \( G\leq S_{n} \) be a group of permutations of the set \( \{1,2,\ldots ,n\} \). Let

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

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

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

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

\( S\subseteq G \)

such that

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

for each i such that \( 1\leq i\leq r \).

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

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

for \( 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.