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.

Contents

[edit] Overview

Suppose G is a finite group with generating sequence X = {x1,x2,...,xr} which acts on the finite set Ω = {1,2,...,n}. A common task in computational group theory is to compute the orbit of some element \omega \in \Omega under G. At the same time, one can record a Schreier vector for ω. This vector can then be used to find the g \in G satisfying ωg = α, for any \alpha \in \omega^G. Use of Schreier vectors to perform this requires less storage space and time complexity than storing these g explicitly.

[edit] Formal definition

All variables used here are defined in the overview.

A Schreier vector for \omega \in \Omega is a vector \mathbf{v} = (v[1],v[2],...,v[n]) such that:

  1. v[ω] = − 1
  2. For \alpha \in \omega^G \ {\omega}, v[\alpha] \in \{1,...,r\} (the manner in which the v[α] are chosen will be made clear in the next section)
  3. v[α] = 0 for \alpha \notin \omega^G

[edit] 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 = {x1,x2,...,xr}
for i in { 0, 1, …, n }:
set v[i] = 0
set orbit = { ω }, v[ω] = −1
for α in orbit and i in { 1, 2, …, r }:
if \alpha^{x_i} is not in orbit:
append \alpha^{x_i} to orbit
set 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, \alpha = \alpha^{x_k^{-1}}, k = v[\alpha]
return g

[edit] References

 This article needs additional citations for verification.
Please help improve this article by adding reliable references. Unsourced material may be challenged and removed. (February 2008)