Fast Monte Carlo algorithms for permutation groups (Q1892223): Difference between revisions

Many algorithms are known for efficient computation with permutation groups given by a list of generators. Usually a first step is to compute a strong generating set (SGS) which generates the chain of point- stabilizer subgroups. This paper presents a new algorithm for computing an SGS. The algorithm is Monte Carlo, meaning that random choices are used and there is a small probability that the result is not an SGS, but an arbitrarily small bound on the error probability can be guaranteed by repeating the algorithm enough times. The asymptotic worst-case time of the new algorithm is, up to polylog factors \((\log^c n)\), only \(n^3\), as opposed to \(n^4\) or \(n^5\) for previously known SGS algorithms (where \(n\) is the size of the permutation domain). Also the analysis of the new algorithm uses only elementary group theory, unlike the fastest previous algorithm which referred to the classification of finite simple groups. The key idea is that ``random subproducts'' of the generators can be used instead of truly random elements of the group (which are difficult to produce without already having an SGS). Using this, fast Monte Carlo algorithms are given for reducing redundant generating sets and for computing normal closures, and these are used in the SGS algorithm. Several related questions are also discussed, including applications to ``black box groups'' (such as matrix groups) and systems of linear equations.