# 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_2N \}$ 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^cc)$ times the maximum of $O(\log_2N)$ 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.