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

:<math> B = (\beta_1, \beta_2, \ldots, \beta_r) </math>

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

:<math> B_i = (\beta_1, \beta_2, \ldots, \beta_i),\, </math>

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

:<math> S \subseteq G </math>

such that

:<math> \langle S \cap G^{(i)} \rangle = G^{(i)} </math>

for each <math> i </math> such that <math> 1 \leq i \leq r </math>.

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

:<math> G^{(i)} \neq G^{(j)} </math>

for <math> 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.

{{DEFAULTSORT:Strong Generating Set}} Category:Computational group theory Category:Permutation groups