Permutation group algorithm for membership testing

From Groupprops
Jump to: navigation, search

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]