# 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*

## Contents

## Description

### Given data

Our universe is some group (such as a linear group or a permutation group) in which products and inverses can be readily computed.

A group in is specified by a generating set , and an element in is given.

### Goal

We are required to determine whether is in .

### Default

By default, when we refer to the membership testing problem, we refer to the membership testing problem in permutation groups, viz 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, is the symmetric group on a finite set of cardinality . Then, we specify the following in the input:

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

The input length is thus something like times the cardinality of . (the arises from the length of each permutation description.

### Goal

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

### Time complexity

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

## Solution

### Outline

Appealing to the order-finding problem, we have the idea outlined above, find the order of , and of the group generated by along with , 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]