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 $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 the $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 $mathbf\{v\}\; =\; (v\; [1]\; ,v\; [2]\; ,...,v\; [n]\; )$ such that:

# $v\; [omega]\; =\; -1$
# For $alpha\; in\; omega^G\; \{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\; otin\; 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

*Citation | last1=Butler | first1=G. | title=Fundamental algorithms for permutation groups | publisher=Springer-Verlag | location=Berlin, New York | series=Lecture Notes in Computer Science | isbn=978-3-540-54955-0 | id=MathSciNet | id = 1225579 | year=1991 | volume=559
*Citation | last1=Holt | first1=Derek F. | title=A Handbook of Computational Group Theory | publisher=CRC Press | location=London | isbn=978-1-58488-372-2 | year=2005
*Citation | last1=Seress | first1=Ákos | title=Permutation group algorithms | publisher=Cambridge University Press | series=Cambridge Tracts in Mathematics | isbn=978-0-521-66103-4 | id=MathSciNet | id = 1970241 | year=2003 | volume=152