Black-box group algorithm for finding the subgroup generated by a subset
|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 where is a finite group (i.e., is to be treated as a black-box group) and a subset of .|
|Output format||the most detailed output format is as follows: for every element of , information on whether or not it is generated by , and, if it is generated by , a word of minimum length for it where the letters of the word are drawn from . We allow inverses in our words.|
|Mode of input processing||requires dealing with the entire input|
|Running time||If the order of the group is , and the size of the generating set is , then the worst case running time is multiplied by the time taken for the black box group operations. With a polylog assumption, this is times a polynomial in .|
|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.
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 to be the one-element subset comprising the identity element.|
Set to be the identity element.
Set to both be empty.
|The step|| At the end of this step, is the collection of all elements of that can be expressed using words of length at most in terms of .|
is the collection of all elements of that can be expressed using words of length exactly and cannot be expressed using words of smaller length.
Note that the and , so s are pairwise disjoint.
|Condition for quitting the outer loop|| We quit the outer loop after the step if is empty.|
In this case, is the subgroup generated by .
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 .
|(before we begin)||The incoming is the set of all elements expressible as a product of length at most from and the incoming is the set of all elements expressible as a product of length precisely and not expressible as a product of smaller length. Similarly for .|
|1||Let be the set|
|2||Remove duplicates from within , and also remove from all the elements that are already within or (see below for why it suffices to check duplicates with just and rather than against all of ).|
|3||Set to be the trimmed set and 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 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:
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 .