## Generating random elements in finite groups.

### Summary

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