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 .
 
Search WWH ::




Custom Search