Subnormality testing problem

This article describes the subgroup property testing problem for the subgroup property: subnormal subgroup
View other subgroup property testing problems

Description

Given data

Our universe is some group $U$ (such as a linear group or a permutation group) in which products and inverses can be readily computed.

A group $G$ in $U$ is specified by a generating set $A$ , and a subgroup $H$ of $G$ is specified by a generating set $B$ . (We are given a guarantee that $H$ is a subgroup of $G$ , if not, we can test it using the algorithm for the subgroup testing problem).

Goal

We are required to determine whether $H$ is subnormal in $G$ .

Definition of subnormality used

A subgroup $H$ is termed subnormal in a group $G$ if the following holds:

Consider the descending chain $G_{i}$ defined as follows: $G_{0} = G$ and $G_{i + 1}$ is the normal closure of $H$ in $G_{i}$ . Then, there exists an $n$ for which $G_{n} = H$ .

The smallest such $n$ is termed the subnormal depth of $H$ .

Relation with other problems

Problems it reduces to

As per the above formulation of the subnormality testing problem, it reduces naturally to the normal closure-finding]] problem, which in turn reduces to the normality testing problem, which in turn reduces to the membership testing problem.

Solution

If membership testing for the subgroup exists

In case a membership test exists for the subgroup, we use the idea outlined above for reducing to the membership testing problem. The step-wise algorithm is provided below:

PLACEHOLDER FOR INFORMATION TO BE FILLED IN: [SHOW MORE]

In particular, because the membership problem can be solved for permutation groups, the normality testing problem can be solved in polynomial-time for permutation groups.