Information Technology Reference
In-Depth Information
We now describe the algorithm to compute the strong generating set of a permu-
tation group that was given in its complete form by Furst et al. [
FHL80
] based on
ideas from Sims [
Sim78
]. It is based on the following lemma due to Schreier and
hence it (and similar algorithms) are some times called
Schreier-Sims algorithm
.
Lemma 3.3
(Schreier's Lemma)
Let G be a group and H be a subgroup of G. Let
T be any right tr
an
sversal of H in G that contains
1
as a coset representative. For
each
g
in G, let
g
denote the unique coset representative of H
g
in T . Let S be a
generating set for G then set
S
={
)
−
1
ts
(
ts
|
t
,
s
∗
S
}
generates the group H .
Let
S
be the generating set of a permutation group
G
. The main idea of the
algorithm is that once we have a right transversal
C
1
of
G
(
1
)
in
G
(
0
)
G
,we
can use Schreier's Lemma 11.3.3 to compute the Schreier generating set for
G
(
1
)
.
We then recursively compute the strong generating set for
G
(
1
)
. At each stage of
the algorithm, we compute the right transversal
C
i
+
1
and recurse on the Schreier
generating set of
G
(
i
+
1
)
obtained in that stage.
The right transversal
C
1
is computed by starting with the set
T
0
=
=
1 and induc-
tively compute
T
i
+
1
as follows:
T
i
+
1
is the union of
T
i
and a subset of
T
i
S
such
that
T
i
+
1
does not contain any redundant representative of same right coset of
G
(
1
)
,
i.e.
T
i
+
1
does not contain two distinct elements
g
1
and
g
2
such that
α
g
1
=
α
g
1
.
If at some point
T
i
+
1
T
i
, we stop the procedure. Since the set
C
1
can at most
have
n
elements this procedure has to terminate in polynomially many steps. The
actual algorithm [
FHL80
] can be significantly more efficient by computing all
the transversals
C
i
's simultaneously through a sifting procedure. We summarise
all the polynomial-time solvable tasks that uses the Schreier-Sims procedure in the
following lemma.
=
Lemma 3.4
(Furst, Hopegraft and Luks)
There are polynomial-time algorithms for
the computational tasks:
1.
computing a strong generating set,
2.
computing the order of a permutation group,
3.
checking the membership of a permutation
g
∗
Sym
(ˇ)
in a given permutation
group G.
The Schreier-Sims algorithm can be generalised to find the generating set of a
subgroup
H
of a permutation group
G
, given indirectly by a membership oracle,
provided the index
#
G
#
H
is small. We state this in the next lemma.
Lemma 3.5
ˇ
via a generating set S and computes the generating set of a subgroup H of G given
via a membership oracle, i.e. a procedure to test whether a given element
g
of G is
actually an element of H . The algorithm takes time polynomial in
#
S,
#
There is algorithm that takes as input a permutation group G on
ˇ
and the
#
G
index
#
H
.