Dixon, John D.

Generating random elements in finite groups.

Electron. J. Comb. 15(1), Research Paper R94, 13 p. (2008)


Summary: Let G be a finite group of order g. A probability distribution Z on G is called $\epsilon $-uniform if |$Z(x) - 1/g| \leq \epsilon /g$ for each x $\in G$. If x1, x2, . . . , xm is a list of elements of G, then the random cube Zm := $Cube(x1, . . . , xm)$ is the probability distribution where $Zm(y)$ is proportional to the number of ways in which y can be written as a product x$\epsilon 1$ 1 x$\epsilon 22 \cdot \cdot \cdot x\epsilon $m m with each $\epsilon i = 0$ or 1. Let x1, . . . , xd be a list of generators for G and consider a sequence of cubes Wk := $Cube(x - 1, . . . , x - 1 k 1 , x1, . . . , xk)$ where, for k > d, xk is chosen at random from Wk - 1. Then we prove that for each $\delta > 0$ there is a constant K$\delta > 0$ independent of G such that, with probability at least $1 - \delta $, the distribution Wm is 1/4-uniform when m $\geq d + K\delta $lg |G|. This justifies a proposed algorithm of Gene Cooperman for constructing random generators for groups. We also consider modifications of this algorithm which may be more suitable in practice.

Mathematics Subject Classification

20P05, 20D60, 20C05, 20-04, 68W20