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 which acts on the finite set. 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 satisfying, for any. 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 such that:
  2. For
  3. for

    Use in algorithms

Here we illustrate, using pseudocode, the use of Schreier vectors in two algorithms