In mathematics, especially the field of computational group theory, a Schreier vector is a tool for reducing the time and space complexity required to calculate orbits of a permutation group.
Overview Suppose G is a finite group with generating sequence X = { x 1 , x 2 , . . . , x r } {\displaystyle X=\{x_{1},x_{2},...,x_{r}\}} which acts on the finite set Ω = { 1 , 2 , . . . , n } {\displaystyle \Omega =\{1,2,...,n\}} . A common task in computational group theory is to compute the orbit of some element ω ∈ Ω {\displaystyle \omega \in \Omega } under G. At the same time, one can record a Schreier vector for ω {\displaystyle \omega } . This vector can then be used to find an element g ∈ G {\displaystyle g\in G} satisfying ω g = α {\displaystyle \omega ^{g}=\alpha } , for any α ∈ ω G {\displaystyle \alpha \in \omega ^{G}} . Use of Schreier vectors to perform this requires less storage space and time complexity than storing these g explicitly.
Formal definition All variables used here are defined in the overview. A Schreier vector for ω ∈ Ω {\displaystyle \omega \in \Omega } is a vector v = ( v [ 1 ] , v [ 2 ] , . . . , v [ n ] ) {\displaystyle \mathbf {v} =(v[1],v[2],...,v[n])} such that:
v [ ω ] = − 1 {\displaystyle v[\omega ]=-1}
For α ∈ ω G ∖ { ω } , v [ α ] ∈ { 1 , . . . , r } {\displaystyle \alpha \in \omega ^{G}\setminus \{{\omega }\},v[\alpha ]\in \{1,...,r\}} (the manner in which the v [ α ] {\displaystyle v[\alpha ]} are chosen will be made clear in the next section)
v [ α ] = 0 {\displaystyle v[\alpha ]=0} for α ∉ ω G {\displaystyle \alpha \notin \omega ^{G}}
Use in algorithms Here we illustrate, using pseudocode, the use of Schreier vectors in two algorithms
Algorithm to compute the orbit of ω under G and the corresponding Schreier vector Input: ω in Ω, X = { x 1 , x 2 , . . . , x r } {\displaystyle X=\{x_{1},x_{2},...,x_{r}\}}
for i in { 0, 1, …, n }: set v[i] = 0 set orbit = { ω }, v[ω] = −1 for α in orbit and i in { 1, 2, …, r }: if α x i {\displaystyle \alpha ^{x_{i}}} is not in orbit: append α x i {\displaystyle \alpha ^{x_{i}}} to orbit set v [ α x i ] = i {\displaystyle v[\alpha ^{x_{i}}]=i}
return orbit, v Algorithm to find a g in G such that ωg = α for some α in Ω, using the v from the first algorithm Input: v, α, X if v[α] = 0: return false set g = e, and k = v[α] (where e is the identity element of G) while k ≠ −1: set g = x k g , α = α x k − 1 , k = v [ α ] {\displaystyle g={x_{k}}g,\alpha =\alpha ^{x_{k}^{-1}},k=v[\alpha ]}
return g
References
Butler, G. (1991), Fundamental algorithms for permutation groups, Lecture Notes in Computer Science, vol. 559, Berlin, New York: Springer-Verlag, ISBN 978-3-540-54955-0, MR 1225579 Holt, Derek F. (2005), A Handbook of Computational Group Theory, London: CRC Press, ISBN 978-1-58488-372-2 Seress, Ákos (2003), Permutation group algorithms, Cambridge Tracts in Mathematics, vol. 152, Cambridge University Press, ISBN 978-0-521-66103-4, MR 1970241
