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 $\mathrm{\Omega }=\{1,2,...,n\}$. A common task in computational group theory is to compute the orbit of some element $\omega \in \mathrm{\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 \mathrm{\Omega }$ is a vector $𝐯=(v[1],v[2],...,v[n])$ such that:

1. $v[\omega ]=-1$
2. 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)
3. $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 }:

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

References

• Template:Citation
• Template:Citation
• Template:Citation