Randomized black-box group algorithm for abelianness testing

Summary

Item	Value
Problem being solved	abelianness testing problem: testing whether a given group is abelian
Input format	A finite group $G$ given via an encoding of a group A mechanism for picking elements uniformly at random, independently over the elements of $G$, as many times as necessary
Output format	Maybe/No, with Maybe if the group may be abelian (but we're not sure) and No if the group is not abelian. In the non-abelian case, it is possible to explicitly output a pair of non-commuting elements as well. Moreover, the probability (over random choices made) of outputing Maybe if the answer is No can be made arbitrarily small with a trade-off between the probability and the constant behind the big-oh notation in the time taken by the algorithm.
Running time	(order of the time for random element generation) plus big-oh of the time taken for group operations.

Facts

• Commuting fraction more than five-eighths implies abelian

Idea and outline

The idea is simple: pick a random pair of elements $x,y\in G$ and check whether they commute. If $G$ is abelian, they definitely do. If $G$ is non-abelian, then the fact that commuting fraction more than five-eighths implies abelian forces that the probability of the randomly selected elements commuting is at most $5/8$. If the process is repeated $k$ times, then the probability, for a non-abelian group, that the pair of elements chosen each time would commute is $(5/8)^{k}$. This can be made arbitrarily small.

Analysis of running time

Each step involves a selection of random elements, so that contributes time proportional to the time taken to select random elements. Then, it involves the group multiplication and equality checking. Whichever of these steps is critical (i.e., takes the most time) determines the big-oh analysis of running time.

Overall, if we make the log-size assumption about the encoding, then the total time taken is of the order of a polynomial in $\log _{2}N$.