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 = \$ which acts on the finite set $\Omega = \$. 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 ...,v such that:

# $v$omega= -1
# For \alpha \in \omega^G \setminus \ , v alpha\in \ (the manner in which the v alpha/math> 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 = \$

:for ''i'' in :
::set ''v'' 'i''= 0

:set ''orbit'' = , ''v'' 'ω''= −1

:for ''α'' in ''orbit'' and ''i'' in :
::if $\alpha^$ is not in ''orbit'':
:::append $\alpha^$ to ''orbit''
:::set v alpha^= 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 = g, \alpha = \alpha^, k = v alpha/math>

:return ''g''

References

*
*
*{{Citation , last1=Seress , first1=Ákos , title=Permutation group algorithms , publisher=Cambridge University Press , series=Cambridge Tracts in Mathematics , isbn=978-0-521-66103-4 , mr=1970241 , year=2003 , volume=152

Computational group theory
Permutation groups