Jump to content

Schreier vector

From Wikipedia, the free encyclopedia

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. For (the manner in which the are chosen will be made clear in the next section)
  2. 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