Base (teoría de grupos)

Dejar${\displaystyle G}$sea ​​un grupo de permutaciones finito que actúa sobre un conjunto${\displaystyle \Omega }$Una secuencia

${\displaystyle B=[\beta _ {1},\beta _ {2},...,\beta _ {k}]}$

de k elementos distintos de${\displaystyle \Omega }$es una base para G si el único elemento de${\displaystyle G}$que arregla cada${\displaystyle \beta _{i}\in B}$puntualmente es el elemento identidad de${\displaystyle G}$. ^{[ 1 ]}

Las bases y los conjuntos generadores fuertes son conceptos importantes en la teoría de grupos computacional . Una base y un conjunto generador fuerte (a menudo denominados en conjunto BSGS) para un grupo se pueden obtener utilizando el algoritmo de Schreier-Sims . ^{[ 2 ]}

No todos los grupos tienen una base. En particular, si una acción grupal no es fiel , entonces no existe una base. Esto se debe a que, por definición de una acción infiel, hay múltiples elementos de${\displaystyle G}$que corrigen cada elemento en${\displaystyle B}$punto por punto.

A menudo resulta beneficioso trabajar con bases y conjuntos generadores fuertes, ya que pueden ser más fáciles de manejar que el grupo completo. Un grupo puede tener una base pequeña en comparación con el conjunto sobre el que actúa. En el mejor de los casos, una base puede tener tamaño 1, como en el caso del grupo aditivo de los enteros . Por otro lado, los grupos simétricos y alternantes tienen bases grandes (el grupo simétrico S _n tiene una base de tamaño n − 1), y a menudo existen algoritmos especializados para estos casos.