Normality 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 normal in $G$.

Relation with other problems

Problems it reduces to

• Membership testing problem: The normality testing problem reduces to the membership testing problem via a positive truth-table reduction. The queries involve testing whether each conjugate of an element of $B$ by an element of $A$ is in $H$, and we are supposed to take the logical conjunction of answers to all the queries. The number of queries equals the product of the sizes of $A$ and $B$.

• Subgroup testing problem: The normality testing problem reduces to the subgroup problem via a positive truth-table reduction. The queries consider each conjugate of $H$ by elements of $A$, and asking whether those conjugates are subgroups of $H$. The number of queries equals the size of $A$.

Problems that are solved using it

• Normal closure-finding: 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

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 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.