Strong generating set

In <a href="/facts/Abstract_algebra/YNNE1CNz">abstract algebra</a>, especially in the area of <a href="/facts/Group_theory/NfowcI5H">group theory</a>, a strong generating set of a <a href="/facts/Permutation_group/vRsNNwwx">permutation group</a> is a <a href="/facts/Generating_set_of_a_group/B9q5lnFY">generating set</a> that clearly exhibits the permutation structure as described by a stabilizer chain. A stabilizer chain is a sequence of <a href="/facts/Subgroup/r91mBgpa">subgroups</a>, each containing the next and each stabilizing one more point.
Let 
 
 
 
 G
 ≤
 
 S
 
 n
 
 
 
 
 {\displaystyle G\leq S_{n}}
 
 be a <a href="/facts/Permutation_group/vRsNNwwx">group of permutations</a> of the set 
 
 
 
 {
 1
 ,
 2
 ,
 …
 ,
 n
 }
 .
 
 
 {\displaystyle \{1,2,\ldots ,n\}.}
 
 Let

B
        =
        (
        
          β
          
            1
          
        
        ,
        
          β
          
            2
          
        
        ,
        …
        ,
        
          β
          
            r
          
        
        )
      
    
    {\displaystyle B=(\beta _{1},\beta _{2},\ldots ,\beta _{r})}

be a sequence of distinct <a href="/facts/Integers/PUwwrawx">integers</a>, 
 
 
 
 
 β
 
 i
 
 
 ∈
 {
 1
 ,
 2
 ,
 …
 ,
 n
 }
 ,
 
 
 {\displaystyle \beta _{i}\in \{1,2,\ldots ,n\},}
 
 such that the <a href="/facts/Group_action_(mathematics)/Vh9VtUUw">pointwise stabilizer</a> of 
 
 
 
 B
 
 
 {\displaystyle B}
 
 is trivial (i.e., let 
 
 
 
 B
 
 
 {\displaystyle B}
 
 be a <a href="/facts/Base_(group_theory)/qk7gWj5R">base</a> for 
 
 
 
 G
 
 
 {\displaystyle G}
 
). Define

B
          
            i
          
        
        =
        (
        
          β
          
            1
          
        
        ,
        
          β
          
            2
          
        
        ,
        …
        ,
        
          β
          
            i
          
        
        )
        ,
        
      
    
    {\displaystyle B_{i}=(\beta _{1},\beta _{2},\ldots ,\beta _{i}),\,}

and define 
 
 
 
 
 G
 
 (
 i
 )
 
 
 
 
 {\displaystyle G^{(i)}}
 
 to be the pointwise stabilizer of 
 
 
 
 
 B
 
 i
 
 
 
 
 {\displaystyle B_{i}}
 
. A strong generating set (SGS) for G relative to the base 
 
 
 
 B
 
 
 {\displaystyle B}
 
 is a <a href="/facts/Set_(mathematics)/BfucfHMq">set</a>

S
        ⊆
        G
      
    
    {\displaystyle S\subseteq G}

such that

⟨
        S
        ∩
        
          G
          
            (
            i
            )
          
        
        ⟩
        =
        
          G
          
            (
            i
            )
          
        
      
    
    {\displaystyle \langle S\cap G^{(i)}\rangle =G^{(i)}}

for each 
 
 
 
 i
 
 
 {\displaystyle i}
 
 such that 
 
 
 
 1
 ≤
 i
 ≤
 r
 
 
 {\displaystyle 1\leq i\leq r}
 
.
The base and the SGS are said to be non-redundant if

G
          
            (
            i
            )
          
        
        ≠
        
          G
          
            (
            j
            )
          
        
      
    
    {\displaystyle G^{(i)}\neq G^{(j)}}

for 
 
 
 
 i
 ≠
 j
 
 
 {\displaystyle i\neq j}
 
.
A base and strong generating set (BSGS) for a group can be computed using the <a href="/facts/Schreier%25E2%2580%2593Sims_algorithm/ugYjVQkM">Schreier–Sims algorithm</a>.

<ul><li>A. Seress, Permutation Group Algorithms, Cambridge University Press, 2002.</li></ul>

Strong generating set open-in-new

Strong generating set