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
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.
We are required to determine whether is in .
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)
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.
We need to determine whether the given permutation lies inside the subgroup generated by .
The time complexity of any algorithm for membership testing is measured as a function of and the cardinality of .
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]