Schreier vector

From Wikipedia, the free encyclopedia

In computational group theory, a Schreier vector is a tool for reducing the time and space complexity required to calculate transversal elements.

[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 would be to compute the orbit of some element \omega \in \Omega under G. At the same time as we do this, we can computer a Schreier vector for ω. This vector can then be used later 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 than storing these g explicitly and has a lower time complexity than computing the g directly.

[edit] Formal definition

(All variables used here are defined as per 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: \omega \in \Omega, X = {x1,x2,...,xr}
for i \in \{0,1,...,n\}:
set v[i] = 0
set orbit = {ω},v[ω] = − 1
for \alpha \in orbit and i \in \{0,1,...,n\}:
if \alpha^x_i \notin 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 \alpha \in \Omega, using the v from the first algorithm
Input: \mathbf{v}, \alpha, X
if v[α] = 0:
return false
set g = e, k = v[α] (where e is the identity element of G)
while k != -1:
set g = {x_k}g, \alpha = \alpha_k^{x^{-1}}, k = v[\alpha]
return g
Retrieved from "http://en.wikipedia.org../../../s/c/h/Schreier_vector.html"