Black-box group algorithm for finding the subgroup generated by a subset
Contents
Summary
Item | Value |
---|---|
Problem being solved | a multitude of problems: generating set to membership test for black-box groups: Given a generating set for a subgroup of a black-box group, find a membership test for the subgroup. In this particular case, the membership test is constructed by explicitly enumerating all the elements of the subgroup. generating set-checking problem: testing whether a subset of a group is a generating set for the whole group. given a generating set for a subgroup of a black-box group, finding a shortest word in terms of that generating set that can be used to describe a particular element of the group. |
Input format | an encoding of a group ![]() ![]() ![]() ![]() ![]() |
Output format | the most detailed output format is as follows: for every element of ![]() ![]() ![]() ![]() |
Theoretical significance | -- |
Mode of input processing | requires dealing with the entire input |
Running time | If the order of the group is ![]() ![]() ![]() ![]() ![]() |
Memory requirement | PLACEHOLDER FOR INFORMATION TO BE FILLED IN: [SHOW MORE] |
Idea and outline
Before beginning, we replace by
. Note that this does not affect the subgroup generated, but does simplify some of our searches for cycles in the Cayley graph.
Broad idea
The idea is to construct the Cayley graph for the subgroup generated by . Each iteration of our process goes one layer further out from the part of the graph that has been constructed so far.
At each iteration, we keep track of which elements of the group correspond to the boundary of the Cayley graph so far, i.e., which are the elements that have just been added in the final iteration. For the next iteration, it suffices to look only at the edges emanating from these. We also keep track of which elements have already been included in the graph, so that we can identify repetitions as we move through the graph.
Outer loop of algorithm
Each step of the outer loop corresponds to expanding one step more in the whole Cayley graph.
Aspect of outer loop | Details |
---|---|
Initialization step | Set ![]() Set ![]() Set ![]() |
The ![]() |
At the end of this step, ![]() ![]() ![]() ![]() ![]() ![]() ![]() Note that the ![]() ![]() ![]() |
Condition for quitting the outer loop | We quit the outer loop after the ![]() ![]() In this case, ![]() ![]() |
From a storage viewpoint, it is necessary only to store, for the stage, the values
and none of the smaller
s or
s.
The process within each step
We now detail the step in detail, for
.
Step no. | Details |
---|---|
(before we begin) | The incoming ![]() ![]() ![]() ![]() ![]() ![]() |
1 | Let ![]() ![]() |
2 | Remove duplicates from within ![]() ![]() ![]() ![]() ![]() ![]() ![]() |
3 | Set ![]() ![]() ![]() |
Why this works
It remains to prove that the process within each step has the desired properties, i.e., if the input from the stage is correct, then the output at the
stage is correct.
First, note that the original, untrimmed set contains all the possibilities for elements that have minimum word length precisely
. We need to show that our trimming process brings us down to precisely the elements that have minimum word length precisely
. In other words, we need to show that if an element of
has minimum word length less than
, that minimum word length must be either
or
.
To see this, suppose the minimum word length is . Then, we get an equality of the form:
where .
Rearranging, we get:
Thus, we have rewritten as an element of
(this is crucially where we use that our generating set is a symmetric subset, hence closed under taking inverses), a contradiction to the definition.
Analysis of running time
The running time of each step is times the costs of the black box group operations (performing multiplication, inverting elements). Since the
s are all pairwise disjoint and their union is bounded in size by the size of the whole group, the running time is
times the cost of the group multiplication and equality checking. If we make the log-size assumption, then this is
times a polynomial in
.