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

Definition

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.

Related problems

Problems solved using this problem

• Normal closure-finding problem: This problem asks for a generating set for the normal closure of $H$ in $G$. 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 $2$, 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

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.

Algorithm	Additional information needed for algorithm, if any	Time taken, where $N$ is the order of the group and $M$ 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.	($O(NM)$ times (the time taken for group multiplication + $O(M)$)) 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	$O(N\log_2^2N)$ times the time taken for group operations

Permutation group algorithms

• Generating set-based permutation group algorithm for normality testing