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 given via an encoding of a group A mechanism for picking elements uniformly at random, independently over the elements of , 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
Idea and outline
The idea is simple: pick a random pair of elements and check whether they commute. If is abelian, they definitely do. If 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 . If the process is repeated times, then the probability, for a non-abelian group, that the pair of elements chosen each time would commute is . 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 .