# Brute-force black-box group algorithm for fixed-class nilpotency testing

## 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^{c+1}c)$ 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 $O(N \operatorname{polylog} N)$. 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 $c + 1$ elements of $G$ (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 $c$.