Black-box group algorithm for fixed-class nilpotency testing given a generating set
Summary
Item | Value |
---|---|
Problem being solved | fixed-class nilpotency testing problem: determine whether a group is nilpotent of a given nilpotency class, i.e., the nilpotency class is at most equal to a specified value. |
Input format | a finite group of order given via an encoding of a group. A positive integer . A generating set of size for . |
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 with letters from whose iterated left-normed commutator is not the identity element. |
Running time | times the time for group operations. Here if we know , otherwise simply set . For small values of , . |
Black-box group operations used | group multiplication, inverse map, and identity element. This algorithm does not use the membership test. for a multi-encoding, also needs equality 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. |
Applications
Combined with black-box group algorithm for small generating set-finding problem, this gives us the generating set-based black-box group algorithm for fixed-class nilpotency testing.
Idea and outline
First, note that if a group of order is nilpotent, its nilpotency class is at most (in fact, it is at most ). Thus, checking if the group has nilpotency class at most is equivalent to checking if the group has nilpotency class at most where . This is useful if we know . If we do not, we simply use .
To check this, it suffices to verify that all iterated left-normed commutators of length from elements of give the identity element.
In practice, we could tweak the algorithm a little bit: run it on every smaller value than (i.e., check all commutators of length 2, then all commutators of length 3, ...). Since we're using iterated left-normed commutators, the commutators computed in any one iteration can be used to save time for the next iteration. An advantage of this is that if the group has smaller nilpotency class, the algorithm terminates faster.
Analysis of running time
For checking each tuple: Each of these commutator computations requires commutator computations, and each commutator computation requires three multiplications and one inversion, so we have a total of group operations. Thus, the time taken to check a tuple is times the time taken for group operations.
Total time: The total time is times the time taken for each tuple.