Normal closure-finding problem: Difference between revisions

Revision as of 20:20, 25 June 2013

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

Description

Given data

Our universe is some group $U$ specified by means of an encoding.

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

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

Revision as of 20:18, 25 June 2013 (view source) Vipul (talk \| contribs) No edit summary ← Older edit		Revision as of 20:20, 25 June 2013 (view source) Vipul (talk \| contribs) (→‎Problems it reduces to) Newer edit →
Line 17:		Line 17:
	===Problems it reduces to===		===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 to normality testing]].