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 ≤ S n {\displaystyle G\leq S_{n}} be a group of permutations of the set { 1 , 2 , … , n } . {\displaystyle \{1,2,\ldots ,n\}.} Let
B = ( β 1 , β 2 , … , β r ) {\displaystyle B=(\beta _{1},\beta _{2},\ldots ,\beta _{r})}be a sequence of distinct integers, β i ∈ { 1 , 2 , … , n } , {\displaystyle \beta _{i}\in \{1,2,\ldots ,n\},} such that the pointwise stabilizer of B {\displaystyle B} is trivial (i.e., let B {\displaystyle B} be a base for G {\displaystyle G} ). Define
B i = ( β 1 , β 2 , … , β i ) , {\displaystyle B_{i}=(\beta _{1},\beta _{2},\ldots ,\beta _{i}),\,}and define G ( i ) {\displaystyle G^{(i)}} to be the pointwise stabilizer of B i {\displaystyle B_{i}} . A strong generating set (SGS) for G relative to the base B {\displaystyle B} is a set
S ⊆ G {\displaystyle S\subseteq G}such that
⟨ S ∩ G ( i ) ⟩ = G ( i ) {\displaystyle \langle S\cap G^{(i)}\rangle =G^{(i)}}for each i {\displaystyle i} such that 1 ≤ i ≤ r {\displaystyle 1\leq i\leq r} .
The base and the SGS are said to be non-redundant if
G ( i ) ≠ G ( j ) {\displaystyle G^{(i)}\neq G^{(j)}}for i ≠ j {\displaystyle i\neq j} .
A base and strong generating set (BSGS) for a group can be computed using the Schreier–Sims algorithm.
- A. Seress, Permutation Group Algorithms, Cambridge University Press, 2002.