Schreier vector

Overview

Suppose G is a finite group with generating sequence X = { x 1 , x 2 , . . . , x r } which acts on the finite set Ω = { 1 , 2 , . . . , n } . A common task in computational group theory is to compute the orbit of some element ω ∈ Ω under G. At the same time, one can record a Schreier vector for ω . This vector can then be used to find an element g ∈ G satisfying ω g = α , for any α ∈ ω 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 ω ∈ Ω is a vector v = ( v [ 1 ] , v [ 2 ] , . . . , v [ n ] ) such that:

1. v [ ω ] = − 1
2. For α ∈ ω G ∖ { ω } , v [ α ] ∈ { 1 , . . . , r } (the manner in which the v [ α ] are chosen will be made clear in the next section)
3. v [ α ] = 0 for α ∉ ω 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] = 0set orbit = { ω }, v[ω] = −1for α in orbit and i in { 1, 2, …, r }:if α x i is not in orbit:append α x i to orbitset v [ α 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, α, Xif v[α] = 0:return falseset g = e, and k = v[α] (where e is the identity element of G)while k ≠ −1:set g = x k g , α = α x k − 1 , k = v [ α ] return g