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 [math]\displaystyle{ G \leq S_n }[/math] be a group of permutations of the set [math]\displaystyle{ \{ 1, 2, \ldots, n \}. }[/math] Let

[math]\displaystyle{ B = (\beta_1, \beta_2, \ldots, \beta_r) }[/math]

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

[math]\displaystyle{ B_i = (\beta_1, \beta_2, \ldots, \beta_i),\, }[/math]

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

[math]\displaystyle{ S \subseteq G }[/math]

such that

[math]\displaystyle{ \langle S \cap G^{(i)} \rangle = G^{(i)} }[/math]

for each [math]\displaystyle{ i }[/math] such that [math]\displaystyle{ 1 \leq i \leq r }[/math].

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

[math]\displaystyle{ G^{(i)} \neq G^{(j)} }[/math]

for [math]\displaystyle{ i \neq j }[/math].

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.