Strong generating set explained

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

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)} ≠ G ^{(j)}

for

i ≠ 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.