# 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 ${\displaystyle X=\{x_{1},x_{2},...,x_{r}\}}$ which acts on the finite set ${\displaystyle \Omega =\{1,2,...,n\}}$. A common task in computational group theory is to compute the orbit of some element ${\displaystyle \omega \in \Omega }$ under G. At the same time, one can record a Schreier vector for ${\displaystyle \omega }$. This vector can then be used to find an element ${\displaystyle g\in G}$ satisfying ${\displaystyle \omega ^{g}=\alpha }$, for any ${\displaystyle \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 ${\displaystyle \omega \in \Omega }$ is a vector ${\displaystyle \mathbf {v} =(v[1],v[2],...,v[n])}$ such that:

1. ${\displaystyle v[\omega ]=-1}$
2. For ${\displaystyle \alpha \in \omega ^{G}\setminus \{{\omega }\},v[\alpha ]\in \{1,...,r\}}$ (the manner in which the ${\displaystyle v[\alpha ]}$ are chosen will be made clear in the next section)
3. ${\displaystyle v[\alpha ]=0}$ for ${\displaystyle \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 Ω, ${\displaystyle 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 ${\displaystyle \alpha ^{x_{i}}}$ is not in orbit:
append ${\displaystyle \alpha ^{x_{i}}}$ to orbit
set ${\displaystyle 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 ${\displaystyle g={x_{k}}g,\alpha =\alpha ^{x_{k}^{-1}},k=v[\alpha ]}$
return g