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.

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 $poly(n)$ times the cardinality of $A$. (the $poly(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]

One of the people editing this page intended to fill in this information at a later stage, but hasn't gotten around to doing it yet. If you see this placeholder for a long time, file an error report at the error reporting page.