Strong generating set

From Wikipedia, the free encyclopedia
Jump to: navigation, search

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 G \leq S_n be a group of permutations of the set \{ 1, 2, \ldots, n \}. 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 (i.e., 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  B_i . A strong generating set (SGS) for G relative to the base  B is a set

 S \subseteq G

such that

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

for each  i such that  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.


References[edit]

  • A. Seress, Permutation Group Algorithms, Cambridge University Press, 2002.