Normal closure-finding problem

This article describes the subgroup operator computation problem for the subgroup operator: [[normal closure]]

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

Let $K$ be the normal closure of $H$ in $G$. We are required to determine a generating set $C$ for $K$.

Relation with other problems

Problems it reduces to

• Membership testing problem: Normal closure-finding can be effected using the membership testing problem for all subgroups of $U$. The idea is as follows: let $K_0=H$ and $C_0=B$. At each stage, check whether $K_i$ is normal in $G$ (the normality testing problem, which again reduces to membership testing). If not, the algorithm for normality testing will yield a conjugate of an element in $K_i$ that is not in $K_i$. Add this to the current generating set $C_i$ and hence get a generating set $C_{i+1}$ for $K_{i+1}$. This process terminates after a finite number of steps and the stable values give $K$ and $C$.