Permutation group algorithm for membership testing: Difference between revisions

Latest revision as of 19:24, 25 June 2013

This article describes a basic decision problem in computational group theory

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 an element $g$ in $U$ is given.

Goal

We are required to determine whether $g$ is in $G$ .

Default

By default, when we refer to the membership testing problem, we refer to the membership testing problem in permutation groups, viz $U$ is the symmetric group on a finite set. For a study of the problem on linear groups, refer membership testing problem for linear groups.

Turing description (for the permutation case)

Given data

Here, $U$ is the symmetric group on a finite set $S$ of cardinality $n$ . Then, we specify the following in the input:

The value of $n$
Every element of $A$ as a permutation on $n$ letters (using any of the standard methods for describing a permutation)
A permutation on $n$ letters (using the same standard method of describing a permutation)

The input length is thus something like $p o l y (n)$ times the cardinality of $A$ . (the $p o l y (n)$ arises from the length of each permutation description.

Goal

We need to determine whether the given permutation lies inside the subgroup generated by $A$ .

Time complexity

The time complexity of any algorithm for membership testing is measured as a function of $n$ and the cardinality of $A$ .

Solution

Outline

Appealing to the order-finding problem, we have the idea outlined above, find the order of $G$ , and of the group generated by $A$ along with $x$ , and check if these values are equal.

However, looking inside the algorithm for the order-finding problem helps us solve membership testing, not just as a decision problem, but also in terms of getting a word in the generators for the given element (if indeed it is a member).

The idea is as follows:

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

@@ Line 18: / Line 18: @@
 By default, when we refer to the membership testing problem, we refer to the membership testing problem in permutation groups, viz <math>U</math> is the symmetric group on a finite set. For a study of the problem on linear groups, refer [[membership testing problem for linear groups]].
-==Relation with other problems==
-===Problems it reduces to===
-* [[Order-finding problem]]: Suppose we have an algorithm that, given any generating set, computes the order of the group generated by that generating set. Then, we can compute the order of the group <math>G</math> (generated by <math>A</math>) and separately compute the order of the group generated by <math>A</math> along with <math>x</math>. <math>x</math> is in <math>G</math> if and only if the two orders are equal.
-===Problems that are solved using it===
-* [[Subgroup testing problem]]: For this problem, we are given sets <math>A</math> and <math>B</math> inside <math>U</math> and we are asked whether the group <math>G</math> generated by <math>A</math> contains the group <math>H</math> generated by <math>B</math>. The subgroup testing problem reduces to the membership testing problem via a positive truth-table reduction. The idea of the reduction is to check, for each element in <math>B</math>, whether it is a member of <math>G</math>.
-* [[Normality testing problem]]: Given generating sets <math>A</math> for <math>G</math> and <math>B</math> for <math>H</math>, the problem asks whether <math>H</math> is a [[normal subgroup]] of <math>G</math>. The normality testing problem reduces to the membership testing problem via a positive truth-table reduction. The idea is to first use the [[subgroup testing problem]] and to then check whether every conjugate of an element in <math>B</math> by an element in <math>A</math> must be in <math>B</math>.
-* [[Normal closure-finding]]: This is solved using the normality testing problem
-* [[Subnormality testing problem]]: This is solved using the normal closure-finding algorithm
 ==Turing description (for the permutation case)==