Generating set-based black-box group algorithm for fixed-class nilpotency testing

From Groupprops
Jump to: navigation, search

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 G given via an encoding of a group. A positive integer c.
Output format Yes/No depending on whether G has nilpotency class at most c.
In the case of a No answer, can also output a tuple of length c + 1 whose iterated left-normed commutator is not the identity element.
Running time (O(N\log_2^2N) times the time for group operations) + (time taken for enumeration).
Note that almost all the time is taken coming up for the generating set. If the generating set is already available, the actual time to run the algorithm is O(\log_2N^{\min \{c,\log_2N \} + 1}) which is o(N).
Competing algorithms brute-force black-box group algorithm for fixed-class nilpotency testing: This is much slower, but easier 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

We do this in two steps:

  1. Black-box group algorithm for small generating set-finding problem
  2. Black-box group algorithm for fixed-class nilpotency testing given a generating set