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 which acts. A common task in computational group theory is to compute the orbit. 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.

such that:

1. are chosen will be made clear in the next section)

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 Ω

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

  1. set v[i] = 0

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

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

  1. is not in orbit:

     1. to orbit

  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:

  1. return false

  set g = e, and k = v[α] (where e is the identity element of G)

  while k ≠ −1:

  return g

References