Membership test to generating set

This article describes a group-finding problem, that is, a problem where we have to explicitly find a generating set of a group that is specified through certain conditions

Description

Given data

A group $G$, sitting inside some universe group $U$, is specified by means of a generating set $A$ of $G$. $H$ is given as a subgroup of finite index in $G$, wherein:

• We are given a black-box algorithm for the membership testing problem in $H$.
• We have an algorithm for membership testing in $G$.

Goal

Find a generating set for $H$ whose size is bounded by the index of $H$ times the size of the given generating set for $G$.

Relation with other problems

Problems solved using this

Interestingly this algorithm is used for a problem that, on the surface of it, appears the reverse of this one -- finding a membership test using a generating set. PLACEHOLDER FOR INFORMATION TO BE FILLED IN: [SHOW MORE]

One of the people editing this page intended to fill in this information at a later stage, but hasn't gotten around to doing it yet. If you see this placeholder for a long time, file an error report at the error reporting page.

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]\left|A\right|$.

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$.