Abelianness testing problem

Definition

The abelianness testing problem is a general class of problems where 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), and we need to determine whether the group is an abelian group.

A proof version of the problem also asks for an explicit pair of non-commuting elements from the group if it turns out to not be abelian.

Related testing problems

• Fixed-class nilpotency testing problem
• Solvability testing problem

Algorithms

Black-box group algorithms

These work for a group specified by means of an encoding. However, the algorithms require only the use of the group multiplication algorithm and do not require the membership test, inverse map, or identity element algorithms, so they work for "encodings" that only have the group multiplication algorithm incorporated.

If we were to use a multi-encoding instead of an encoding, then the "time taken for multiplication" in the time estimates below would need to be replaced by "time taken for multiplication + time taken for equality checking" to obtain the correct estimates. With that caveat, all the stated algorithms below can be adapted to multi-encodings.

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 abelianness testing	enumeration of all group elements, either already given or computable	($O(N^2)$ times the time taken for group multiplication) plus (time taken for enumeration of elements)	deterministic
black-box group algorithm for abelianness testing given a generating set	generating set of size $s$ already given	$O(s^2)$ times the time taken for group multiplication	deterministic
generating set-based black-box group algorithm for abelianness 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 abelianness 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(1)$ times the time for group multiplication, plus $O(\log_2N)$	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 abelianness testing	enumeration of all group elements	$O(N\log N)$ times the time for group operations	nondeterministic, requires guessing the generating set.

Permutation group algorithms

Consider a group of permutations on a set of size $n$ specified by means of a generating set. We can test for abelianness using the permutation group algorithm for abelianness testing. The idea of this is to use the generating set (either directly or first apply the Sims filter to it and then use the resultant smaller generating set) in the black-box group algorithm for abelianness testing given a generating set.