Strong generating set

From Free net encyclopedia

Let <math>G \leq S_n</math> be a permutation group. 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 (ie: 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 \subset G </math>

such that

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

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