Fixed-class nilpotency testing problem

Definition

The fixed-class nilpotency testing problem is a general class of problems where:

1. A group is specified using some suitable group description rule (which may be an encoding, multi-encoding, or description using a presentation, among other possibilities).
2. A positive integer $c$ is specified.
3. We are asked to output Yes/No based on whether the group is a nilpotent group of nilpotency class at most $c$.

A proof version of the problem also asks, in case the group is not nilpotent of class at most $c$, for an explicit tuple of length $c+1$ of elements of the group for which the iterated left-normed commutator is not the identity.

Equivalent problems

Testing whether a given group has precisely a given nilpotency class

The above problem is equivalent to the precise class nilpotency testing problem: determining whether the nilpotency class of a given group is precisely $c$, i.e., whether the group has class $c$ but not $c-1$. Here's how:

• Reducing the precise class nilpotency testing problem for $c$ to the fixed-class nilpotency testing problem: Check that we get a Yes for the fixed-class nilpotency testing problem for $c$ and a No for $c-1$.
• Reducing the fixed-class nilpotency testing problem for $c$ to the precise class nilpotency testing problem: Check that we get a Yes for at least (and hence exactly) one of the values $0,1,2,\dots ,c$.

Determination of precise nilpotency class

The above problem is also equivalent to the problem of determining the precise nilpotency class as follows:

• Reducing the precise nilpotency class determination problem to the fixed-class nilpotency testing problem: Do the fixed-class nilpotency testing for 1,2,3,... and stop as soon as you get a Yes.
• Reducing the fixed-class nilpotency testing problem for class $c$to the precise nilpotency class determination problem: Determine the precise nilpotency class, then check whether it exists and is less than or equal to $c$.

Algorithms

Black-box group algorithms

These work for a group specified by means of an encoding.

Algorithm	Additional information needed for algorithm, if any	Time taken, where $N$ is the order of the group	Type of algorithm
brute-force black-box group algorithm for fixed-class nilpotency testing	enumeration of all group elements, either already given or computable	($O(N^{c+1})$ times the time taken for group multiplication plus inversion) plus (time taken for enumeration of elements)	deterministic
black-box group algorithm for fixed-class nilpotency testing given a generating set	generating set of size $s$ already given	$O(s^{c'+1})$ times the time taken for group multiplication plus inversion, where $c'=\min\{c,\log _{2}N\}$ if the order of the group is known to be $N$, otherwise set $c'=c$	deterministic
generating set-based black-box group algorithm for fixed-class nilpotency testing	enumeration of all group elements, either already given or computable	($O(N\log ^{2}N)$ times the time taken for group multiplication) plus (time taken for enumeration of elements)	deterministic
randomized black-box group algorithm for fixed-class nilpotency testing	ability to sample uniformly at random from the group. Note that a generic random number generator, along with a full enumeration of group elements, can achieve this.	$O(2^{c}c)$ times the maximum of $O(\log _{2}N)$ and the time for group operations	randomized, with No answers always being correct but the Yes answers possibly being wrong. This puts the problem in co-RP.
nondeterministic black-box group algorithm for fixed-class nilpotency testing	enumeration of all group elements	$O(N\log N)$ times the time for group operations	nondeterministic, requires guessing the generating set.