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.
ReferencesEdit
- A. Seress, Permutation Group Algorithms, Cambridge University Press, 2002.