Randomized black-box group algorithm for fixed-class nilpotency testing

Summary

Item	Value
Problem being solved	fixed-class nilpotency testing problem: determine whether a group is nilpotent of a given nilpotency class $c$, i.e., if the nilpotency class is at most the specified value $c$.
Input format	a finite group $G$ given via an encoding of a group. A positive integer $c$. 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 nilpotent of class at most the specified value (but we're not sure) and No if the group is not (nilpotent of class at most the specified value). In the latter case, can also output a proof in the form of a tuple of length $c+1$ whose left-normed iterated commutator is not the identity. 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	($O(c\log _{2}N)$ plus $O(c)$ times the time for group operations) times $O(2^{c})$ (this $O(2^{c})$ terms describes the fact that the larger the value of $c$, the more the number of times the randomized test needs to run in order to achieve a fixed threshold probability of certainty).

Facts

• Fixed-class tuple fraction is bounded away from one for groups not of that class

Idea and outline

The idea is simple: pick a random tuple of elements $x_{1},x_{2},\dots ,x_{c+1}\in G$ and compute the left-normed iterated commutator $[[\dots [x_{1},x_{2}],\dots ,x_{c}],x_{c+1}]$. If $G$ has class at most $c$, this equals the identity element. Otherwise, by the fact that fixed-class tuple fraction is bounded away from one for groups not of that class, the probability of this being equal to the identity element is at most $1-(3/2^{c+2})$.

If the test is done $r$ times, the probability that a group not of class at most $c$ will fool the test all times is at most:

$\left(1-{\frac {3}{2^{c+2}}}\right)^{r}$

If we want to bring this probability down to less than a given number $\alpha$, choose $r$ greater than:

${\frac {\ln \alpha }{\ln \left(1-{\frac {3}{2^{c+2}}}\right)}}$

Analysis of running time

Each step involves a selection of random elements, which, due to lookup and recording costs, takes $O(c\log _{2}N)$ time. Then, it involves the group multiplication and equality checking, done $O(c)$ times.

The number of steps that we need to perform depends on $c$. As noted above, if we want an error probability of at most $\alpha$, we need to choose the number of times as:

${\frac {\ln \alpha }{\ln \left(1-{\frac {3}{2^{c+2}}}\right)}}$

This is $O(2^{c})$.