Subnormality testing problem: Difference between revisions

Latest revision as of 20:56, 25 June 2013

This article describes the subgroup property testing problem for the subgroup property: subnormal subgroup
A GAP command using the algorithms for this problem is available at: IsSubnormal
View other subgroup property testing problems

Definition

The subnormality testing problem refers to a general class of problems where a group is specified using a suitable group description rule, a subgroup is specified using a suitable subgroup description rule, and we need to determine whether the subgroup is a subnormal subgroup of the group.

Fixed-depth version

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

Relation with other problems

Normal closure-finding problem is the problem to which the reduction is most direct.
Normality testing problem is a related problem.

@@ Line 1: / Line 1: @@
-{{subgroup property testing problem|[[subnormal subgroup]]}}
+{{subgroup property testing problem|property=subnormal subgroup|GAP command = IsSubnormal}}
-{{embedding-setup problem}}
+==Definition==
-==Description==
+The '''subnormality testing problem''' refers to a general class of problems where a [[group]] is specified using a suitable [[group description rule]], a [[subgroup]] is specified using a suitable [[subgroup description rule]], and we need to determine whether the subgroup is a [[subnormal subgroup]] of the group.
-===Given data===
+===Fixed-depth version===
-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.
+{{fillin}}
-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===
-We are required to determine whether <math>H</math> is [[subnormal subgroup|subnormal]] in <math>G</math>.
-===Definition of subnormality used===
-A subgroup <math>H</math> is termed '''subnormal''' in a group <math>G</math> if the following holds:
-Consider the descending chain <math>G_i</math> defined as follows: <math>G_0 = G</math> and <math>G_{i+1}</math> is the [[normal closure]] of <math>H</math> in <math>G_i</math>. Then, there exists an <math>n</math> for which <math>G_n = H</math>.
-The smallest such <math>n</math> is termed the subnormal depth of <math>H</math>.
 ==Relation with other problems==
-===Problems it reduces to===
+* [[Normal closure-finding problem]] is the problem to which the reduction is most direct.
+* [[Normality testing problem]] is a related problem.
-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:
-{{fillin}}
-In particular, because the membership problem can be solved for [[permutation group]]s, the normality testing problem can be solved in polynomial-time for permutation groups.