The product replacement prospector. (Q654033)

Many algorithms in computational group theory depend on being able to compute a list of independent random elements from a large group \(G\) where the group is defined by a small generating set and an appropriate group operation (technically, we are working with a black box group). The most popular program currently used to generate such elements is the product replacement algorithm (PRA) [\textit{F. Celler, C. R. Leedham-Green, S. H. Murray, A. C. Niemeyer} and \textit{E. A. O'Brien}, Commun. Algebra 23, No. 13, 4931-4948 (1995; Zbl 0836.20094)] which has the virtue of being quite fast. Although extensively studied, the theoretical basis for the PRA is still weak. However, experimental evidence indicates that in practice the PRA produces roughly random elements which are not too dependent. (It has been shown that the mixing time for the PRA is bounded by a polynomial in \(\ln|G|\) but in practice the algorithm is never run for sufficiently long to reach the bounds proved to ensure adequate mixing.) Fortunately in many applications we are only concerned to find an element from a subset \(S\subseteq G\) where \(|G|/|S|\) is polynomial in \(\ln|G|\) and in these cases the PRA seems to work well. The present paper proposes a new heuristic to improve the PRA. It keeps a new temporary list (called the sampler) which is statistically tested from time to time to see whether recently generated elements appear random. If they are sufficiently random then the algorithm continues, but if they are not then the algorithm backtracks. All of the elements generated can be stored as short straight line programs. The new algorithm (called the product replacement prospector) has been implemented in the computer algebra system MAGMA and experimental evidence suggests that it is superior to the PRA.