sampling elements of a finite group: efficiency of the product replacement algorithm with an accumulator.
Michał Marcinkowski, Piotr Mizerka · 2025
Read sampling elements of a finite group: efficiency of the product replacement algorithm with an accumulator. by Michał Marcinkowski, Piotr Mizerka (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2512-18302.txt.
Introduction
Michał Marcinkowski and Piotr Mizerka sharpen a classic random walk for picking elements of a finite group. The product replacement method stirs a set of group generators by swapping in products, and software uses it to sample group members. Their variant adds an accumulator that collects single elements as output, not just fresh generator sets.
They prove the output turns near uniform after a set number of steps. That count grows like the square of the generator count times the log of the group size. It is a faster mixing than past bounds gave. Spectral gap tools and computer aided checks carry the proof. Random group sampling underlies tests in algebra software, so faster mixing means quicker, fairer picks.
Catalog record
| CREATOR | Michał Marcinkowski, Piotr Mizerka |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 52 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2512-18302
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
sampling elements of a finite group: efficiency of the product replacement algorithm with an accumulator. Michał Marcinkowski, Piotr Mizerka Abstract . Let G G be a finite group generated by k k elements. The well-known product replacement algorithm provides an effective method for sampling generating sets of G G . We study a refinement of this algorithm that is designed to output individual elements of G G . We show that after O ( k 2 log | G | ) O(k^{2}\log|G|) steps, the distribution of the output is close to uniform on G G , which improves upon the best results known to date. The proof proceeds via spectral gap estimates and uses computer assisted calculations. 1. Introduction Let G be a finite group. We are interested in an efficient algorithm that samples elements of G from a nearly uniform distribution. Such algorithms play a central role in computational group theory, as many other algorithms require access to random group elements [ 5 , 21 ] . Often one deals with finite groups that are astronomically large, e.g., the Rubik’s cube group has an order about 10^{19} . Thus one cannot simply generate the list of elements and choose one at random, as generating such a list would require prohibitive time and memory. We therefore need some additional information on G to use in the sampling procedure. It is not a restrictive assumption to suppose that, together with G , we are given a generating tuple S (in this context it is more convenient to use tuples rather than generating sets). We can then multiply the generators in various ways and thereby produce elements of G as output. To this end, we need to assume that we have an efficient procedure for inverting and multiplying elements of G , as well as an efficient way to represent the results of these operations on a computer. Such groups are called “black-box” groups, since when describing particular algorithms operating on them, we will not be concerned with the details of how these operations are implemented. Subgroups of permutation groups or matrix groups over finite rings are among the most important examples of black-box groups. The simplest method to sample an element from G given its generating tuple S , is to perform a lazy random walk on the Cayley graph of (G,S\cup S^{-1}) starting from the identity. By the standard theory, the distribution of this random walk converges to the uniform distribution. However, even for very simple groups such as {\mathbb{Z}}_{n} , the number of steps required in order to be close to the uniform distribution can make this approach intractable if n is large. There exist algorithms that are much more efficient than a random walk on a Cayley graph. One of the most important techniques for designing such samplers is based on the product replacement algorithm. This algorithm was first introduced in [ 4 ] and is again based on a random walk, but this time not on the Cayley graph, but rather on the graph of all generating k -tuples, where k=|S| . Thus the algorithm first outputs a generating tuple, and then one can take the first element of the tuple as the output element of G . It was reported that this technique works well in practice and passes statistical tests. However, in general the distribution of this random element does not converge to the uniform distribution, see [ 1 ] or Example 2.2 . For a survey of the product replacement algorithm and related problems see [ 26 ] . In order to overcome this difficulty, variants of the product replacement algorithm were proposed [ 13 ] . In particular, in the “rattle” version it is clear that the limiting distribution is uniform, but the rate of convergence remained unknown. It was observed that the behavior of the original product replacement algorithm, which samples a generating k -tuple, is related to Kazhdan’s property (T) for \operatorname{SAut}(\operatorname{F}_{k}) [ 17 ] . The question whether \operatorname{SAut}(\operatorname{F}_{k}) has property (T) was a longstanding question and was answered affirmatively in the breakthrough papers [ 7 , 9 ] for k>4 , and in [ 22 ] the remaining case of \operatorname{SAut}(\operatorname{F}_{4}) was settled. Even more importantly, very good estimates were obtained for the corresponding spectral gaps. From those estimates it immediately follows that the mixing rate of the original product replacement algorithm is of order O(k^{2}\log|G|) . This means that after O(k^{2}\log|G|) steps the algorithm outputs a generating tuple from a distribution that is close to uniform. The problem of finding good estimates for product replacement algorithms that sample an element from G has remained open. A step towards such estimates was made in [ 14 ] , where the “rattle” version was analyzed. However, it is assumed there that k is of order \log|G| , which can be prohibitively large when G is large. In this paper we focus on a variant of the product replacement algorithm that is a slight modification of the “rattle” and is easier to analyze from the point of view of group actions. We call it the product replacement accumulator algorithm . It is based on a random walk on the space of generating tuples extended by one additional element - the accumulator. After t steps of the random walk, the accumulator is returned. Our main theorem is the following. Theorem ( Theorem 5.6 ) . Suppose that G is a finite group equipped with a generating k -tuple, with k>5 , and let U_{G} denote the uniform distribution on G . Let \nu_{t} be the distribution of the random element returned by the product replacement accumulator algorithm after t steps. Then \|\nu_{t}-U_{G}\|_{\mathrm{tv}}<\epsilon\text{ for }t\geq\frac{23k^{2}}{k-5}((k+1)\log|G|+\log(\epsilon^{-1})), where \|\!\cdot\!\|_{\mathrm{tv}} is the total variation distance and \log is the natural logarithm. This result should be interpreted as follows: we need to make about \frac{23k^{2}}{k-5}(k\log|G|+1) steps to ensure that \|\nu_{t}-U_{G}\|_{\mathrm{tv}}<e^{-1} , where e denotes Euler’s number. This is the most expensive part. From then on, every time we make an additional \frac{23k^{2}}{k-5} steps, we are guaranteed that \nu_{t} is e -times closer to the uniform distribution. We want to highlight, that one of the most interesting aspects of Theorem 5.6 , as well as [ 7 , Section 5.2] , is that the bound on t depends only on |G| . It does not depend at all on the more intrinsic structure of G . The estimates in Theorem 5.6 are virtually the same as those for the mixing time of the original product replacement algorithm obtained in [ 7 ] , so passing from sampling a generating tuple to sampling an element of G does not incur much additional overhead. We want to stress that the product replacement accumulator algorithm is very simple: in one step it performs only one multiplication and at most one inversion of group elements. There are no other computations involved, so what matters is only how many steps of the algorithm one needs to perform and the cost of group operations in G . Moreover, the required memory is very modest: one needs to store only k+1 elements of G . It is possible that the convergence of