A Random Base Change Algorithm for Permutation Groups

✍ Scribed by Gene Cooperman; Larry Finkelstein

• Publisher: Elsevier Science
• Year: 1994
• Tongue: English
• Weight: 549 KB
• Volume: 17
• Category: Article
• ISSN: 0747-7171
• DOI: 10.1006/jsco.1994.1032

✦ Synopsis

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 (\operatorname{Rand}(G)) producing a random element of (G) with the uniform distribution and so that the time for each call to (\operatorname{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\left(n \log ^{2}|G|\right)). An earlier version of this work appeared in Cooperman and Finkelstein (1992b).