Black-box group algorithm for abelianness testing given a generating set

From Groupprops
Jump to: navigation, search

Summary

Item Value
Problem being solved abelianness testing problem: determine whether a given group is abelian
Input format a finite group G given via an encoding of a group, a generating set S for G
Note: We do not need all the black-box operations associated with an encoding. In fact, this algorithm uses only the multiplication operation. In particular, this algorithm applies to situations where we have encodings without explicit algorithms for the membership test, identity element, or inverse map.
Output format Yes/No depending on whether G is abelian. In the No case it is also possible to output a pair of elements that do not commute.
Theoretical significance Shows that the problem is in co-RP. However, the problem is already known to be in P, so this is not of much use.
Running time O(s^2) times the time taken for group operations, where s is the size of the generating set.
If S is a generating set of minimum size, then s \le \log_2N.
Black-box group operations used in algorithm group multiplication only
equality testing if we use a multi-encoding instead.
Competing algorithms black-box group algorithm for abelianness testing: Works without being given a generating set, but takes more time.
nondeterministic black-box group algorithm for abelianness testing
randomized black-box group algorithm for abelianness testing
Corollary algorithms generating set-based black-box group algorithm for abelianness testing tests for abelianness by first constructing a generating set using the black-box group algorithm for small generating set-finding problem and then applying the algorithm of this page to that generating set. (For the idea used here, see conversion of black-box group algorithm dependent on generating set to black-box group algorithm).
Parallelizable version The algorithm can be parallelized, and this parallelization is most useful when the time taken for group operations is significantly greater than the time taken to execute the parallelization, but all the group operations can be accessed by multiple parallel processes.

Idea and outline

The idea is to check, for every pair of elements from S, whether they commute. If every pair of elements from S commute, the group is abelian. If any pair does not commute, the group is non-abelian.

Applicability

Black-box group operations used

The algorithm outlined here uses only the black-box multiplication. It does not use the other black-box group operations, such as the identity element, the inverse map, or the membership test.

Thus, this algorithm applies to situations where we have encodings without explicit algorithms for the membership test, identity element, or inverse map.

Applicability to multi-encodings

A multi-encoding of a group is like an encoding, but a single group element may have more than one associated codeword in the encoding. For a multi-encoding, we usually need to additionally specify an equality test to determine whether two codewords represent the same group element.

The black-box group algorithm given here adapts to multi-encodings, and requires both the multiplication and the equality test.