Күшті генератор жиынтығы - Strong generating set

Жылы абстрактілі алгебра, әсіресе топтық теория, а күшті генератор жиынтығы а ауыстыру тобы Бұл генератор жиынтығы а. сипатталғандай ауыстыру құрылымын анық көрсетеді тұрақтандырғыш тізбегі. Тұрақтандырғыш тізбегі - тізбегі кіші топтар, әрқайсысы келесі және тұрақтандырушы тағы бір нүктеден тұрады.

Келіңіздер ${ displaystyle G leq S_ {n}}$ болуы а ауыстыру тобы жиынтықтың ${ displaystyle {1,2, ldots, n }.}$ Келіңіздер

${ displaystyle B = ( beta _ {1}, beta _ {2}, ldots, beta _ {r})}$

нақты бірізділік болуы керек бүтін сандар, ${ displaystyle beta _ {i} in {1,2, ldots, n },}$ сияқты бағыттаушы тұрақтандырғыш туралы ${ displaystyle B}$ тривиальды (яғни, рұқсат етілсін) ${ displaystyle B}$ болуы а негіз үшін ${ displaystyle G}$). Анықтаңыз

${ displaystyle B_ {i} = ( бета _ {1}, бета _ {2}, ldots, бета _ {i}), ,}$

және анықтаңыз ${ displaystyle G ^ {(i)}}$ нүктелік тұрақтандырғыш болуы керек ${ displaystyle B_ {i}}$. A күшті генератор жиынтығы (SGS) негізге қатысты G үшін ${ displaystyle B}$ Бұл орнатылды

${ displaystyle S subseteq G}$

осындай

${ displaystyle langle S cap G ^ {(i)} rangle = G ^ {(i)}}$

әрқайсысы үшін ${ displaystyle i}$ осындай ${ displaystyle 1 leq i leq r}$.

Негізі және SGS деп айтылады артық емес егер

${ displaystyle G ^ {(i)} neq G ^ {(j)}}$

үшін ${ displaystyle i neq j}$.

Топтың негізін және күшті генерациялау жиынтығын (BSGS) есептеуге болады Шрайер-Симс алгоритмі.

Әдебиеттер тізімі

• A. Seress, Permutation Group алгоритмдері, Кембридж университетінің баспасы, 2002 ж.