Brute-force black-box group algorithm for fixed-class nilpotency testing
|Problem being solved||fixed-class nilpotency testing problem: determine whether a group is nilpotent of a given nilpotency class, i.e., if the nilpotency class is at most the specified value.|
|Input format||a finite group given via an encoding of a group. A positive integer .|
|Output format|| Yes/No depending on whether has nilpotency class at most .|
In the case of a No answer, can also output a tuple of length whose iterated left-normed commutator is not the identity element.
|Running time||( times the time for group operations), plus the time taken for enumerating all group elements|
|Competing algorithms|| generating set-based black-box group algorithm for fixed-class nilpotency testing: This is much faster, about . However, it is harder to code.|
randomized black-box group algorithm for fixed-class nilpotency testing
|Parallelizable version||The computations of iterated commutators can be massively parallelized, if all the parallel processes can simultaneously access the algorithms for the group operations.|
Idea and outline
The idea is simple: take every tuple of elements of (possibly repeated), and compute their iterated left-normed commutator. If this is the identity for every tuple, then that means that the nilpotency class is at most .