Generating set-checking problem

This article describes a basic decision problem in computational group theory

Description

Given data

We are given an encoding of a group $G$ and are given a subset $A$ of $G$ (by explicit specification of the code-words for all elements).

Goal

We are required to determine whether or not $A$ is a generating set of $G$.

Reduction to membership testing problem

Further information: Generating set-checking reduces to membership testing The following three things are true:

• The generating set-checking problem has a co-nondeterministic polynomial-time many-one reduction to the membership testing problem
• If we are given a uniform (or near-uniform) random sampling algorithm, the generating set-checking problem has a co-R reduction to the membership testing problem.
• If we are already given some other generating set of the group, the generating set-checking problem has a deterministic polynomial-time negative truth table reduction to the membership testing problem.

Membership testing problem (co-nondeterministic)

Recall that in the membership testing problem, we are given a subset $A$ of $G$ and are required to formulate a test that will take in an element of $G$ and output whether that element is in the subgroup $H$ generated by $A$.

The generating set-checking problem has a co-nondeterministic reduction to the membership testing problem in the following sense. If a given subset does not generate the whole group, then we can find a short proof of the fact invoking the membership testing problem. Namely, pick an element $g\in G$ that is not in the subgroup generated by the $A$, and then prove that it actually is not in the subset by invoking the membership testing problem.

Membership testing problem (given a generating set)

If we can find another set $B$ that is also a generating set for the group, then the problem of checking whether $A$ is a generating set can be reduced to the membership testing problem as follows: for every element of $B$, apply the membership testing problem to check whether that element lies in the subgroup generated by $A$.

Thus, we have a polynomial-time positive truth table reduction to the membership testing problem provided we already have a generating set.

Membership testing problem (given a random sampler)

If we have a random sampler (that is, an algorithm that saples randomly from the group) we could try the following approach:

• Use the random sampler to output $g\in G$
• Check whether $g$ is in the subgroup generated by $A$

Note that if in any such run we get a no, we are confirmed that $A$ is not a generating set. If, on the other hand, we get a yes at any stage, we still have the possibility that $A$ is a generating set.

If $H$ is a proper subgroup of $G$, then the index of $H$ in $G$ is at least 2, hence there are at least as many elements outside $H$ as inside $H$. Hence, if the random sampler is uniform or near-uniform we have a non-negligible property of hitting on an element outside the group fairly soon.

This thus gives us a co-randomized reduction to the membership testing problem.