Schreier vector explained

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 v = (v[ 1 ],v[ 2 ],...,v[n]) such that:v[\omega] = -1

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 :

set v[''i''] = 0

set orbit =, v[''ω''] = −1

for α in orbit and i in :

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 ^{-1} _{k}} , k = v[\alpha]

return g