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

edit

Suppose G is a finite group with generating sequence   which acts on the finite set  . A common task in computational group theory is to compute the orbit of some element   under G. At the same time, one can record a Schreier vector for  . This vector can then be used to find an element   satisfying  , for any  . Use of Schreier vectors to perform this requires less storage space and time complexity than storing these g explicitly.

Formal definition

edit

All variables used here are defined in the overview.

A Schreier vector for   is a vector   such that:

  1.  
  2. For   (the manner in which the   are chosen will be made clear in the next section)
  3.   for  

Use in algorithms

edit

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 Ω,  
for i in { 0, 1, …, n }:
set v[i] = 0
set orbit = { ω }, v[ω] = −1
for α in orbit and i in { 1, 2, …, r }:
if   is not in orbit:
append   to orbit
set  
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  
return g

References

edit
  • 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