Vector de Schreier

En matemáticas , especialmente en el campo de la teoría de grupos computacional , un vector de Schreier es una herramienta para reducir la complejidad temporal y espacial necesaria para calcular las órbitas de un grupo de permutaciones .

Supongamos que G es un grupo finito con secuencia generadora${\displaystyle X=\{x_{1},x_{2},...,x_{r}\}}$que actúa sobre el conjunto finito${\displaystyle \Omega =\{1,2,...,n\}}$Una tarea común en la teoría de grupos computacional es calcular la órbita de algún elemento .${\displaystyle \omega \in \Omega }$bajo G. Al mismo tiempo, se puede registrar un vector de Schreier para${\displaystyle \omega }$Este vector se puede utilizar para encontrar un elemento.${\displaystyle g\in G}$satisfactorio${\displaystyle \omega ^{g}=\alpha }$, para cualquier${\displaystyle \alpha \in \omega ^{G}}$El uso de vectores de Schreier para realizar esto requiere menos espacio de almacenamiento y complejidad temporal que almacenar estos g explícitamente.

Todas las variables utilizadas aquí están definidas en la descripción general.

Un vector de Schreier para${\displaystyle \omega \in \Omega }$es un vector${\displaystyle \mathbf {v} =(v[1],v[2],...,v[n])}$de tal manera que:

1. ${\displaystyle v[\omega ]=-1}$
2. Para${\displaystyle \alpha \in \omega ^{G}\setminus \{{\omega }\},v[\alpha ]\in \{1,...,r\}}$(la manera en que el${\displaystyle v[\alpha ]}$Las opciones elegidas se aclararán en la siguiente sección.
3. ${\displaystyle v[\alpha ]=0}$para${\displaystyle \alpha \notin \omega ^{G}}$

Aquí ilustramos, mediante pseudocódigo , el uso de vectores de Schreier en dos algoritmos.

• Algoritmo para calcular la órbita de ω bajo G y el vector de Schreier correspondiente.

Entrada: ω en Ω ,${\displaystyle X=\{x_{1},x_{2},...,x_{r}\}}$

para i en { 0, 1, …, n }:

establecer v [ i ] = 0

establecer órbita = { ω }, v [ ω ] = −1

para α en órbita e i en { 1, 2, …, r }:

si${\displaystyle \alpha ^{x_{i}}}$no está en órbita :

añadir${\displaystyle \alpha ^{x_{i}}}$a órbita

colocar${\displaystyle v[\alpha ^{x_{i}}]=i}$

órbita de retorno , v

• Algoritmo para encontrar un g en G tal que ω ^g = α para algún α en Ω , utilizando el v del primer algoritmo.

Entrada: v , α , X

si v [ α ] = 0:

devolver falso

establecemos g = e y k = v [ α ] (donde e es el elemento identidad de G )

mientras k ≠ −1:

colocar${\displaystyle g={x_{k}}g,\alpha =\alpha ^{x_{k}^{-1}},k=v[\alpha ]}$

devolver g

• Butler, G. (1991), Algoritmos fundamentales para grupos de permutaciones , Lecture Notes in Computer Science, vol.  559, Berlín, Nueva York: Springer-Verlag , ISBN 978-3-540-54955-0, MR 1225579 
• Holt, Derek F. (2005), A Handbook of Computational Group Theory , Londres: CRC Press , ISBN 978-1-58488-372-2
• Seress, Ákos (2003), Algoritmos de grupos de permutación , Cambridge Tracts in Mathematics, vol.  152, Cambridge University Press , ISBN 978-0-521-66103-4, MR 1970241