Normal closure-finding problem: Difference between revisions

Latest revision as of 20:48, 25 June 2013

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

Description

The normal closure-finding problem is the general name for a class of problems where a group $G$ is described using a group description rule, a subgroup $H$ is described using a subgroup description rule, and our goal is to use a (specified) subgroup description rule to find the normal closure $H^{G}$ .

Relation with other problems

Problems it reduces to

Normality testing problem: See black-box reduction of normal closure-finding in terms of generating sets to normality testing.

@@ Line 1: / Line 1: @@
-{{subgroup operator computation problem|[[normal closure]]}}
+{{subgroup operator computation problem|normal closure}}
 ==Description==
-===Given data===
+The '''normal closure-finding problem''' is the general name for a class of problems where a group <math>G</math> is described using a [[group description rule]], a [[subgroup]] <math>H</math> is described using a [[subgroup description rule]], and our goal is to use a (specified) [[subgroup description rule]] to find the [[normal closure]] <math>H^G</math>.
-Our universe is some group <math>U</math> (such as a linear group or a permutation group) in which products and inverses can be readily computed.
-A group <math>G</math> in <math>U</math> is specified by a generating set <math>A</math>, and a subgroup <math>H</math> of <math>G</math> is specified by a generating set <math>B</math>. (We are given a guarantee that <math>H</math> is a subgroup of <math>G</math>, if not, we can test it using the algorithm for the [[subgroup testing problem]]).
-===Goal===
-Let <math>K</math> be the [[normal closure]] of <math>H</math> in <math>G</math>. We are required to determine a generating set <math>C</math> for <math>K</math>.
 ==Relation with other problems==
@@ Line 17: / Line 9: @@
 ===Problems it reduces to===
-* [[Membership testing problem]]: Normal closure-finding can be effected using the membership testing problem for ''all'' subgroups of <math>U</math>. The idea is as follows: let <math>K_0 = H</math> and <math>C_0 = B</math>. At each stage, check whether <math>K_i</math> is normal in <math>G</math> (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 <math>K_i</math> that is not in <math>K_i</math>. Add this to the current generating set <math>C_i</math> and hence get a generating set <math>C_{i+1}</math> for <math>K_{i+1}</math>. This process terminates after a finite number of steps and the stable values give <math>K</math> and <math>C</math>.
+* [[Normality testing problem]]: See [[black-box reduction of normal closure-finding in terms of generating sets to normality testing]].