Membership test (subgroup description)

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 $G$ equipped with an encoding $C$ . An abstract subgroup $H$ of $G$ .

Definition part

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

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 $G$ 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 $(H, M)$ where $H$ is a subgroup of $G$ and $M$ is a membership test for $H$ in $G$ .

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 $H_{1}$ and $H_{2}$ be two subgroups of $G$ with membership tests $M_{1}$ and $M_{2}$ respectively. Then, $H_{1} \cap H_{2}$ has membership test $M_{1} \land M_{2}$ .

Composition

This subgroup description rule is transitive

Suppose $H$ has a membership test in $G$ , and $K$ has a membership test in $H$ . Then we get a natural membership test for $K$ in $G$ .

Transfer operator

Template:Transfer-closed sdr A membership test for $H$ in $G$ also gives a membership test for $H \cap K$ in $K$ .

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 $p$ such that the following holds: For any subgroup $H$ of the $n^{t h}$ member, there is an algorithm whose running time is bound above by $p (n)$ that acts as a membership test for $H$ in $G_{n}$ .

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.