Schreier vector
≈ 2 min read
Names in other languages
No names in other languages are held for this entry yet.
Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.
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.
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 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 \Omega is a vector \mathbf{v} = (v[1],v[2],...,v[n]) such that: v[\omega] = -1 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) 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
Text derived from https://en.wikipedia.org/w/index.php?oldid=931364559 under CC BY-SA 4.0; modifications have been made.