Strong generating set

Quality 0.50 · 5 views · Updated 2 months ago

title: "Strong generating set" type: doc version: 1 created: 2026-02-28 author: "Wikipedia contributors" status: active scope: public tags: ["computational-group-theory", "permutation-groups"] topic_path: "general/computational-group-theory" source: "https://en.wikipedia.org/wiki/Strong_generating_set" license: "CC BY-SA 4.0" wikipedia_page_id: 0 wikipedia_revision_id: 0

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.

::callout[type=info title="Wikipedia Source"] This article was imported from Wikipedia and is available under the Creative Commons Attribution-ShareAlike 4.0 License. Content has been adapted to SurfDoc format. Original contributors can be found on the article history page. ::