Generating Random Elements in Finite Groups

Let $G$ be a finite group of order $g$. A probability distribution $Z$ on $G\ $is called $\varepsilon$-uniform if $\left\vert Z(x)-1/g\right\vert \leq\varepsilon/g$ for each $x\in G$. If $x_{1},x_{2},\dots,x_{m}$ is a list of elements of $G$, then the random cube $Z_{m}:=Cube(x_{1},\dots,x_{m}) $ is the probability distribution where $Z_{m}(y)$ is proportional to the number of ways in which $y$ can be written as a product $x_{1}^{\varepsilon_{1}}x_{2}^{\varepsilon_{2}}\cdots x_{m}^{\varepsilon_{m}}$ with each $\varepsilon _{i}=0$ or $1$. Let $x_{1},\dots,x_{d} $ be a list of generators for $G$ and consider a sequence of cubes $W_{k}:=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}$. 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 $W_{m}$ is $1/4$-uniform when $m\geq d+K_{\delta }\lg\left\vert G\right\vert $. 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.

Fetched live from OpenAlex and de-inverted. Abstracts are not stored in this database: the inverted indexes are 8.6 GB of the frame’s 9.3 GB of text, and the host has 13 GB free.