Generating random elements in finite groups.
The main result of the paper gives a theoretical justification of an algorithm proposed by Gene Cooperman, for constructing random generators for finite groups. If \(x_1,\dots,x_m\) is a list of elements in \(G\), then the random cube \(\text{Cube}(x_1,\dots,x_m)\) is the probability distribution on \(G\) induced by the map \((\varepsilon_1,\dots,\varepsilon_m)\mapsto x_1^{\varepsilon_1}\cdots x_m^{\varepsilon_m}\) from the uniform distribution on \(\{0,1\}^m\). The author proves the following: let \(x_1,\dots,x_d\) be a list of generators for \(G\) and consider a sequences of cubes \(W_k:=\text{Cube}(x_k^{-1},\dots,x_1^{-1},x_1,\dots,x_k)\), where for \(k>d\), \(x_k\) is chosen at random from \(W_{k-1}\). For each \(\delta>0\) there is a constant \(K_\delta>0\) independent of \(G\) such that, with probability at least \(1-\delta\), the distribution \(W_m\) is 1/4-uniform when \(m\geq d+K_\delta\lg|G|\). The value obtained for the constant \(K_\delta\) and the fact that the number of group operations to construct the random element generator is proportional to \(\log^2|G|\) still means that a direct implementation of an algorithm based on this result may be impractical: in the final part of the paper the author examines some possible ways in which the process may be speeded up and how shorter random element generators might be constructed.
scientific article; zbMATH DE number 5540999