Generating random elements in finite groups.
type: Item
instance of: scholarly article
title: Generating random elements in finite groups.
zbMATH Open document ID: 1169.20035
author: John D. Dixon
published in: The Electronic Journal of Combinatorics
publication date: 2009-04-07T00:00:00Z
full work available at URL: https://eudml.org/doc/130477
full work available at URL: v15i1r94.html
review text: 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.
reviewed by: Andrea Lucchini
Mathematics Subject Classification ID: 20P05
Mathematics Subject Classification ID: 20D60
Mathematics Subject Classification ID: 20F05
Mathematics Subject Classification ID: 68W20
Mathematics Subject Classification ID: 60B15
Mathematics Subject Classification ID: 20-04
zbMATH DE Number: 5540999
zbMATH Keywords: finite groups
zbMATH Keywords: random elements
zbMATH Keywords: algorithms
zbMATH Keywords: random generators of groups
zbMATH Keywords: probability distributions
MaRDI profile type: Publication
description: scientific article; zbMATH DE number 5540999