Schreier vector

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

Suppose G is a finite group with generating sequence $X=\{x_{1},x_{2},...,x_{r}\}$ which acts on the finite set $\Omega =\{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 $\omega$ . This vector can then be used to find an element $g\in G$ satisfying $\omega ^{g}=\alpha$ , 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.

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:

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

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=\{x_{1},x_{2},...,x_{r}\}

for i in { 0, 1, …, n }:

set v[i] = 0

set orbit = { ω }, v[ω] = −1

for α in orbit and i in { 1, 2, …, r }:

\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

References

Butler, G. (1991), Fundamental algorithms for permutation groups, Lecture Notes in Computer Science, 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, 152, Cambridge University Press, ISBN 978-0-521-66103-4, MR 1970241

This article is issued from Wikipedia - version of the 9/25/2014. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.