Membership test (subgroup description)

From Groupprops

This article defines a subgroup description rule, viz a rule that allows us to describe subgroups of a group in terms of encodings of the whole group

Definition

Setup

A group equipped with an encoding . An abstract subgroup of .

Definition part

A membership test for in is a test that takes as input the code-word for some element of (that is, it takes as input a string guaranteed to be a code-word for an element of ) and outputs whether it is a code-word for an element in .

Relation with other subgroup description rules

Stronger subgroup description rules

Many subgroup description rules automatically give a membership test. These include:


Weaker subgroup description rules

Relation with a generating set

A priori, it is not clear whether a membership test provides us an efficient generating set, nor is it clear whether a generating set provides us with an efficient membership test. However, it turns out that when is the symmetric group equipped with its usual encoding, we can in fact obtain a membership test from a generating set.

The general problem of finding a membership test from a generating set is termed the membership testing problem.

Effect of subgroup operators

We are interested in pairs where is a subgroup of and is a membership test for in .

Intersection of subgroups

This subgroup description rule is intersection-closed, viz a description of the subgroups can be used to obtain a description of their intersection

Let and be two subgroups of with membership tests and respectively. Then, has membership test .

Composition

This subgroup description rule is transitive

Suppose has a membership test in , and has a membership test in . Then we get a natural membership test for in .

Transfer operator

Template:Transfer-closed sdr A membership test for in also gives a membership test for in .

Related subgroup properties

In general, we are interested in subgroups for which there exist fast algorithms for membership testing. This notion of fast usually means fast as a function of the size of the subgroup, possibly the index of the subgroup, and possibly the logarithm of the size of the whole group.

Polynomial time-recognizability

An encoding of an IAPS of groups is termed subgroup-polynomial-time-recognizable if there exists a polynomial such that the following holds: For any subgroup of the member, there is an algorithm whose running time is bound above by that acts as a membership test for in .

An operator on subgroups is termed polynomial-time-recognizability-preserving if the time bound on the membership test on the subgroup obtained after applying the operator, is bounded by a polynomial in the time bounds on the membership test on the original subgroups.

Thus, from observations above, the intersection operator, the transfer operator, the composition operator, are all polynomial-time-recognizability-preserving.