Generating random elements in finite groups. (Q1010821)

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.