abstract algebra In mathematics, more specifically algebra, abstract algebra or modern algebra is the study of algebraic structures. Algebraic structures include groups, rings, fields, modules, vector spaces, lattices, and algebras over a field. The te ...

, especially in the area of

group theory In abstract algebra, group theory studies the algebraic structures known as group (mathematics), groups. The concept of a group is central to abstract algebra: other well-known algebraic structures, such as ring (mathematics), rings, field ...

, a strong generating set of a

permutation group In mathematics, a permutation group is a group ''G'' whose elements are permutations of a given set ''M'' and whose group operation is the composition of permutations in ''G'' (which are thought of as bijective functions from the set ''M'' to ...

is a

generating set In mathematics and physics, the term generator or generating set may refer to any of a number of related concepts. The underlying concept in each case is that of a smaller set of objects, together with a set of operations that can be applied t ...

that clearly exhibits the permutation structure as described by a

stabilizer chain Stabilizer, stabiliser, stabilisation or stabilization may refer to: Chemistry and food processing * Stabilizer (chemistry), a substance added to prevent unwanted change in state of another substance ** Polymer stabilizers are stabilizers use ...

. A stabilizer chain is a sequence of

subgroup In group theory, a branch of mathematics, given a group ''G'' under a binary operation ∗, a subset ''H'' of ''G'' is called a subgroup of ''G'' if ''H'' also forms a group under the operation ∗. More precisely, ''H'' is a subgrou ...

s, each containing the next and each stabilizing one more point. Let

G \leq S_n

be a group of permutations of the set

\.

Let :

B = (\beta_1, \beta_2, \ldots, \beta_r)

be a sequence of distinct

integers An integer is the number zero (), a positive natural number (, , , etc.) or a negative integer with a minus sign ( −1, −2, −3, etc.). The negative numbers are the additive inverses of the corresponding positive numbers. In the language ...

\beta_i \in \ ,

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^

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^ \rangle = G^

for each

i

such that

1 \leq i \leq r

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

G^ \neq G^

for

i \neq j

. A base and strong generating set (BSGS) for a group can be computed using the

Schreier–Sims algorithm The Schreier–Sims algorithm is an algorithm in computational group theory, named after the mathematicians Otto Schreier and Charles Sims. This algorithm can find the order of a finite permutation group, test membership (is a given permutation ...

References

* A. Seress, ''Permutation Group Algorithms'', Cambridge University Press, 2002. {{DEFAULTSORT:Strong Generating Set Computational group theory Permutation groups