Generating random elements in finite groups. (Q1010821)

From MaRDI portal
scientific article
Language Label Description Also known as
English
Generating random elements in finite groups.
scientific article

    Statements

    Generating random elements in finite groups. (English)
    0 references
    0 references
    7 April 2009
    0 references
    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.
    0 references
    finite groups
    0 references
    random elements
    0 references
    algorithms
    0 references
    random generators of groups
    0 references
    probability distributions
    0 references

    Identifiers

    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references