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

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

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 Ω, [math]\displaystyle{ X = \{x_1,x_2,...,x_r\} }[/math]

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

set v[i] = 0

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

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

if [math]\displaystyle{ \alpha^{x_i} }[/math] is not in orbit:

append [math]\displaystyle{ \alpha^{x_i} }[/math] to orbit

set [math]\displaystyle{ v[\alpha^{x_i}] = i }[/math]

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 [math]\displaystyle{ g = {x_k}g, \alpha = \alpha^{x_k^{-1}}, k = v[\alpha] }[/math]

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 
• Holt, Derek F. (2005), A Handbook of Computational Group Theory, London: CRC Press, ISBN 978-1-58488-372-2, https://archive.org/details/handbookofcomput0000holt 
• Seress, Ákos (2003), Permutation group algorithms, Cambridge Tracts in Mathematics, 152, Cambridge University Press, ISBN 978-0-521-66103-4