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 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 .