Membership test to generating set

Description

Given data

A group $G$ is specified by means of an encoding, and we are given a generating set $A$ of $G$ . We are also given a membership test for a subgroup $H$ of $G$ .

(We make the log-size assumption).

Goal

We need to find a logarithmically size generating set for $H$ .

Relation with other problems

Problems it reduces to

Generating set-finding problem: Clearly, if we can directly use the encoding on $H$ to find a generating set for $H$ , then we can obviously solve the preceding problem (viz finding a generating setof $H$ with the additional datum of a generating set on $G$ ).

Solution

Outline

The solution proceeds in two steps:

Finding a system of coset representatives of $H$ in $G$
Using Schreier's lemma and membership testing in $H$ to obtain a generating set for $H$

Finding a system of coset representatives

The idea is to view the action of $G$ on the coset space $G / H$ . This is a transitive group action.

Construct a graph with vertex set $G / H$ wherein two cosets are adjacent if one can be taken to the other by left multiplication by an element of $A$ . Now, by doing a breadth-first search in this graph, we can find, for each member of $G / H$ , a path from $H$ to that, and hence a group element of $G$ that lies in that coset.

Hence, we have found a system of coset representatives.

Note that the number of steps that a breadth-first search takes equals the number of edges in the graph. The number of edges in this case is $[G : H] | A |$ .

Using this to obtain a set of generators

We simply use Schreier's lemma to explicitly construct the generating set of the subgroup, invoking the membership test in $H$ wherever needed.

Variants and cleverer solutions

There are two problems with the above general solution:

The size of the generating set obtained could be quite large (it is proportional to the index of the subgroup)
The time taken is also proportional to the index of the subgroup

The solution lies in finding a tower of subgroups from the whole group to the given subgroup, such that:

The index between any two adjacent members is polynomially bounded in $n$
The number of steps is polynomially bounded (this is automatically guaranteed, for instance, if the size of the universe group is exponentially bounded in $n$ , as happens in the case of permutation groups)

And simultaneously also in finding an an algorithm that can, at every stage, bring the size of the generating set down to a polynomial function of $n$ .