×

A random base change algorithm for permutation groups. (English) Zbl 0835.20007

Summary: A new random base change algorithm is presented for a permutation group \(G\) acting on \(n\) points whose worst case asymptotic running time is better for groups with a small to moderate size base than any known deterministic algorithm. To achieve this time bound, the algorithm requires a random generator \(\text{Rand}(G)\) producing a random element of \(G\) with the uniform distribution and so that the time for each call to \(\text{Rand}(G)\) is bounded by some function \(f(n,G)\). The random base change algorithm has probability \(1-1/|G|\) of completing in time \(O(f(n,G)\log|G|)\) and outputting a data structure for representing the point stabilizer sequence relative to the new ordering. The algorithm requires \(O(n\log|G|)\) space and the data structure produced can be used to test group membership in time \(O(n\log|G|)\). Since the output of this algorithm is a data structure allowing generation of random group elements in time \(O(n\log|G|)\), repeated application of the random base change algorithms for different orderings of the permutation domain of \(G\) will always run in time \(O(n\log^2|G|)\). An earlier version of this work appeared [the authors, J. Symb. Comput. 12, 475-497 (1991; Zbl 0790.20006)].

MSC:

20B40 Computational methods (permutation groups) (MSC2010)
20P05 Probabilistic methods in group theory
68W30 Symbolic computation and algebraic computation
20-04 Software, source code, etc. for problems pertaining to group theory
20F05 Generators, relations, and presentations of groups

Citations:

Zbl 0790.20006

Software:

Cayley; GAP
PDFBibTeX XMLCite
Full Text: DOI