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 
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 
satisfying ωg = α, for any 
. 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 is a vector ![\mathbf{v} = (v[1],v[2],...,v[n])](../../../math/c/c/e/ccef6199ac0ccabafe3c7decfca2e705.png)
such that:
- v[ω] = − 1
- For
![\alpha \in \omega^G \ {\omega}, v[\alpha] \in \{1,...,r\}](../../../math/f/5/e/f5efe3f704944a33617da7b69af03d69.png)
(the manner in which the v[α] are chosen will be made clear in the next section) - v[α] = 0 for
[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: , X = {x1,x2,...,xr}
- for
:
- set v[i] = 0
- set orbit = {ω},v[ω] = − 1
- for
orbit and :
- if
orbit:
- append
to orbit - set
![v[\alpha^x_i] = i](../../../math/7/c/6/7c6d741a5c8dafa40ce6e627baa91eaf.png)
- append
- if
- return orbit, v
- Algorithm to find a such that ωG = α for some
, using the v from the first algorithm
- Input:
- 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]](../../../math/1/4/1/141a79718d5688515b9e99aa9e3446dd.png)
- set
- return g
