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.
Suppose G is a finite group with generating sequence
X
=
{
x
1
,
x
2
,
.
.
.
,
x
r
}
which acts on the finite set
Ω
=
{
1
,
2
,
.
.
.
,
n
}
. 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
g
∈
G
satisfying
ω
g
=
α
, for any
α
∈
ω
G
. Use of Schreier vectors to perform this requires less storage space and time complexity than storing these g explicitly.
All variables used here are defined in the overview.
A Schreier vector for
ω
∈
Ω
is a vector
v
=
(
v
[
1
]
,
v
[
2
]
,
.
.
.
,
v
[
n
]
)
such that:
-
v
[
ω
]
=
−
1
- For
α
∈
ω
G
∖
{
ω
}
,
v
[
α
]
∈
{
1
,
.
.
.
,
r
}
(the manner in which the
v
[
α
]
are chosen will be made clear in the next section)
-
v
[
α
]
=
0
for
α
∉
ω
G
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
α
x
i
is not in
orbit:
append
α
x
i
to
orbit
set
v
[
α
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
,
α
=
α
x
k
−
1
,
k
=
v
[
α
]
return
g
