×

Computing the order of a solvable permutation group. (English) Zbl 0701.20001

If a group G of permutations is given by a set of generators usually the first step for its investigation is the determination of a base and a strong generating system by one of the versions of the Schreier-Sims method [cf. J. S. Leon; Math. Comput. 35, 941-974 (1980; Zbl 0444.20001)]. In this article the author describes a new method, which works if G is soluble (it runs into an endless cycle if G is not soluble). The method is not only considerably faster in many cases tested, but it also constructs at the same time a “polycyclic generating sequence”, i.e. a sequence of generators \(y_ 1,...,y_ t\) of G such that with \(H_ i=<y_ i,...,y_ t>\) one has \(H_ i\triangleleft H_{i-1}\) for \(1<i\leq t\) and \(H_ 1=G\). There are a number of computational problems, e.g. the determination of the conjugacy classes, for which rather efficient solutions are known for soluble groups using such a polycyclic generating sequence, while they are notoriously difficult using only base and strong generating set. Like other computational methods for soluble groups this one exploits the fact that an orbit of a normal subgroup of a group G is a block for G.
Reviewer: J.Neubüser

MSC:

20B40 Computational methods (permutation groups) (MSC2010)
20F05 Generators, relations, and presentations of groups
20F16 Solvable groups, supersolvable groups
68W30 Symbolic computation and algebraic computation
20-04 Software, source code, etc. for problems pertaining to group theory
20B05 General theory for finite permutation groups

Citations:

Zbl 0444.20001
Full Text: DOI

References:

[1] Babai, L., On the length of subgroup chains in symmetric groups, Comm. Algebra, 14, 1729-1736 (1986) · Zbl 0604.20004
[2] Cannon, J., A computational toolkit for finite permutation groups, (Proceedings of the Rutgers Group Theory Year. Proceedings of the Rutgers Group Theory Year, 1983-1984 (1984), Cambridge University Press: Cambridge University Press New York), 1-18 · Zbl 0648.20002
[3] Dixon, J. D., The solvable length of a solvable linear group, Math. Z., 107, 151-158 (1968) · Zbl 0175.30302
[4] Jerrum, M., A compact representation for permutation groups, J. Algorith., 7, 60-78 (1986) · Zbl 0597.68036
[5] Leon, J. S., On an algorithm for finding a base and strong generating set for a group given by generating permutations, Math. Comp., 35, 941-974 (1980) · Zbl 0444.20001
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.