Subnormality testing problem

This article describes the subgroup property testing problem for the subgroup property: {{{property}}}Property "Specific information about" (as page type) with input value "{{{property}}}" contains invalid characters or is incomplete and therefore can cause unexpected results during a query or annotation process.
View other subgroup property testing problems

This article describes a problem in the setup where the group(s) involved is/are defined by means of an embedding in a suitable universe group (such as a linear or a permutation group) -- viz in terms of generators described as elements sitting inside this universe group

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]

One of the people editing this page intended to fill in this information at a later stage, but hasn't gotten around to doing it yet. If you see this placeholder for a long time, file an error report at the error reporting page.

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.