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

==Summary==

{| class="sortable" border="1"
! 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]] <math>G</math> given via an [[encoding of a group]]. A positive integer <math>c</math>.
|-
| Output format || Yes/No depending on whether <math>G</math> has nilpotency class at most <math>c</math>.<br>In the case of a ''No'' answer, can also output a tuple of length <math>c + 1</math> whose iterated left-normed commutator is not the identity element.
|-
| Running time || (<math>O(N^{c+1}c)</math> 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 <math>O(N \operatorname{polylog} N)</math>. However, it is harder to code.<br>[[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 <math>c + 1</math> elements of <math>G</math> (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 <math>c</math>.