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 $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

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

This article is issued from Wikipedia - version of the 1/15/2012. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.