Normality testing problem
This article describes the subgroup property testing problem for the subgroup property: normal subgroup
A GAP command using the algorithms for this problem is available at: IsNormal
View other subgroup property testing problems
The normality testing problem refers to a general class of problems where a group is specified using a suitable group description rule, a subgroup is specified using a suitable subgroup description rule, and we need to determine whether the subgroup is a normal subgroup of the whole group.
Separate testing for being a subgroup
The version discussed here will assume that we are given a guarantee that the subgroup is indeed a subgroup of the group, so that we do not need to verify that. Another version of the problem simply specifies the group and the (alleged) subgroup using subgroup description rules inside a bigger group. The normality testing problem in this case splits into two parts: first, verify that the subgroup is indeed a subgroup (this reduces to the subgroup testing problem), and second, verify normality conditional to being a subgroup.
Proof version of the problem
A proof version of the problem asks, in case the subgroup is not normal, for an explicit choice of element from the group and element from the subgroup such that the corresponding conjugate is not in the subgroup.
Problems solved using this problem
- Normal closure-finding problem: This problem asks for a generating set for the normal closure of in . Normal closure-finding can be solved using the normality testing problem, by expanding the group each time by throwing in a new conjugate. Since the size of the subgroup generated each time increases by a factor of at least , the number of iterations of the algorithm is at most the logarithm of the index of the subgroup.
- Subnormality testing problem: This relies in turn on normal closure-finding
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.
|Algorithm||Additional information needed for algorithm, if any||Time taken, where is the order of the group and is the order of the subgroup||Type of algorithm|
|brute-force black-box group algorithm for normality testing||enumeration of all group elements and subgroup elements, either already given or computable.||( times (the time taken for group multiplication + )) plus (time taken for enumeration of group elements) plus (time taken for enumeration of subgroup elements)||deterministic|
|randomized black-box group algorithm for normality testing||oracles that generate elements uniformly at random for both the group and the subgroup, and a membership test for the subgroup||(time taken for the random oracles) + (time taken for group multiplication and inversion) + (time taken for the membership test)||randomized|
|generating set-cum-membership test-based black-box group algorithm for normality testing||generating set for the group, generating set for the subgroup, and a membership test for the subgroup|
|membership test-based black-box group algorithm for normality testing||enumeration of all group elements, membership test for subgroup||times the time taken for group operations|