In mathematics

Mathematics

Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...

, especially the field of computational group theory

Computational group theory

In mathematics, computational group theory is the study ofgroups by means of computers. It is concernedwith designing and analysing algorithms anddata structures to compute information about groups...

, a Schreier vector is a tool for reducing the time and space complexity required to calculate orbits of a permutation group

Permutation group

In mathematics, a permutation group is a group G whose elements are permutations of a given set M, and whose group operation is the composition of permutations in G ; the relationship is often written as...

.

Overview

Suppose G is a finite group

Group (mathematics)

In mathematics, a group is an algebraic structure consisting of a set together with an operation that combines any two of its elements to form a third element. To qualify as a group, the set and the operation must satisfy a few conditions called group axioms, namely closure, associativity, identity...

 with generating sequence which acts

Group action

In algebra and geometry, a group action is a way of describing symmetries of objects using groups. The essential elements of the object are described by a set, and the symmetries of the object are described by the symmetry group of this set, which consists of bijective transformations of the set...

 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:

1. 
2. For (the manner in which the are chosen will be made clear in the next section)
3. for

Use in algorithms

Here we illustrate, using pseudocode

Pseudocode

In computer science and numerical computation, pseudocode is a compact and informal high-level description of the operating principle of a computer program or other algorithm. It uses the structural conventions of a programming language, but is intended for human reading rather than machine reading...

, 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 }:

set v[i] = 0

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

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

if is not in orbit:

append to orbit

set

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

return g