Strong generating set

From Wikipedia, the free encyclopedia

Let G \leq S_n be a permutation group. Let

B = (\beta_1, \beta_2, \ldots, \beta_r)

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

B_i = (\beta_1, \beta_2, \ldots, \beta_i) ,

and define G(i) to be the pointwise stabilizer of Bi. A strong generating set (SGS) for G relative to the base B is a set

S \subset G

such that

\langle S \cap G^{(i)} \rangle = G^{(i)}

for each 1 \leq i \leq r .

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

G^{(i)} \neq G^{(j)}

for i \neq j .

A base and strong generating set (BSGS) for a group can be computed using the Schreier-Sims algorithm.