Brute-force black-box group algorithm for fixed-class nilpotency testing
From Groupprops
Summary
Item | Value |
---|---|
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 ![]() ![]() |
Output format | Yes/No depending on whether ![]() ![]() In the case of a No answer, can also output a tuple of length ![]() |
Running time | (![]() |
Competing algorithms | generating set-based black-box group algorithm for fixed-class nilpotency testing: This is much faster, about ![]() 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
.