# Strong generating set

> Mediated Wiki article. Canonical URL: https://mediated.wiki/source/Strong_generating_set
> Markdown URL: https://mediated.wiki/source/Strong_generating_set.md
> Source: https://en.wikipedia.org/wiki/Strong_generating_set
> Source revision: 1195407545
> License: Creative Commons Attribution-ShareAlike 4.0 International (https://creativecommons.org/licenses/by-sa/4.0/)

In [abstract algebra](/source/abstract_algebra), especially in the area of [group theory](/source/group_theory), a '''strong generating set''' of a [permutation group](/source/permutation_group) is a [generating set](/source/Generating_set_of_a_group) that clearly exhibits the permutation structure as described by a '''stabilizer chain'''.  A stabilizer chain is a sequence of [subgroup](/source/subgroup)s, each containing the next and each stabilizing one more point.

Let <math>G \leq S_n</math> be a [group of permutations](/source/permutation_group) of the set <math>\{ 1, 2, \ldots, n \}.</math>  Let 

:<math> B = (\beta_1, \beta_2, \ldots, \beta_r) </math> 

be a sequence of distinct [integers](/source/integers), <math>\beta_i \in \{ 1, 2, \ldots, n \} ,</math> such that the [pointwise stabilizer](/source/Group_action_(mathematics)) of <math> B </math> is trivial (i.e., let <math> B </math> be a [base](/source/Base_(group_theory)) for <math> G </math>).  Define 

:<math> B_i = (\beta_1, \beta_2, \ldots, \beta_i),\, </math>

and define <math> G^{(i)} </math> to be the pointwise stabilizer of <math> B_i </math>. A '''strong generating set''' (SGS) for G relative to the base <math> B </math> is a [set](/source/Set_(mathematics)) 

:<math> S \subseteq G </math> 

such that 

:<math> \langle S \cap G^{(i)} \rangle = G^{(i)} </math> 

for each <math> i </math> such that <math> 1 \leq i \leq r </math>.

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

:<math> G^{(i)} \neq G^{(j)} </math> 

for <math> i \neq j </math>.

A base and strong generating set (BSGS) for a group can be computed using the [Schreier–Sims algorithm](/source/Schreier%E2%80%93Sims_algorithm).

==References==
* A. Seress, ''Permutation Group Algorithms'',  Cambridge University Press, 2002.

{{DEFAULTSORT:Strong Generating Set}}
Category:Computational group theory
Category:Permutation groups

---
Adapted from the Wikipedia article [Strong generating set](https://en.wikipedia.org/wiki/Strong_generating_set) by Wikipedia contributors ([contributor history](https://en.wikipedia.org/wiki/Strong_generating_set?action=history)). Available under [Creative Commons Attribution-ShareAlike 4.0 International](https://creativecommons.org/licenses/by-sa/4.0/). Changes may have been made.