Permutation group algorithm for membership testing

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.

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 $G$ (generated by $A$ ) and separately compute the order of the group generated by $A$ along with $x$ . $x$ is in $G$ 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 $A$ and $B$ inside $U$ and we are asked whether the group $G$ generated by $A$ contains the group $H$ generated by $B$ . 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 $B$ , whether it is a member of $G$ .

Normality testing problem: Given generating sets $A$ for $G$ and $B$ for $H$ , the problem asks whether $H$ is a normal subgroup of $G$ . 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 $B$ by an element in $A$ must be in $B$ .

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)

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]