Order-finding problem
Template:Basic computational problem
This article describes a problem in the setup where the group(s) involved is/are defined by means of an embedding in a suitable universe group (such as a linear or a permutation group) -- viz in terms of generators described as elements sitting inside this universe groupTemplate:Presentation-setup at
Contents
Description
Given data
There is a universe group in which multiplication and inverse operations can be readily performed.
A subgroup of is specified by means of a generating set for where the elements of are specified using some standard format for elements in .
Goal
Determine the order of .
Relation with other problems
Problems that reduce to it
- Membership testing problem: Suppose we can solve the order-finding problem. Then, to solve the membership testing problem using it, do the following. Let be a generating set for and be an element which we want to test for membership in . Find the order of (as the subgroup generated by ) and the order of the subgroup generated by along with . The two orders are equal if and only if contains .
Incidentally, this may not actually solve the problem of finding a word in the generators for the given element.
Problems it reduces to
- Strong generating set-finding problem: In fact, the algorithm that we describe here is, in essence, the same as the Schreier-Sims algorithm for computing a strong generating set.
Solution
Basic idea
The idea behind solving the order-finding problem for comes from the following descending chain of subgroups:
where .
By an easy coset counting argument:
Also, we have:
Thus, if we have an algorithm to compute each of the indices , then we can compute the order of .
Obstacles and overcoming them
The cardinality equals the size of the orbit of under the action of and this orbit can be easily computed by a breadth-first search in the graph for the action. In fact, we can even compute a system of coset representatives for in by using the breadth-first search. Further information: minimal Schreier system
The problem, however, is: how do we get a generating set for starting from a generating set for , To solve this problem, we can use Schreier's lemma which provides a constructive approach to obtaining a generating set for the subgroup from a generating set for the whole group and a system of coset representatives (the more general problem is finding a generating set from a membership test).
This still leaves another problem: Each time we go downward on the chain, the size of the generating set may go up by a factor of (because the index of the subgroup is ). Thus, we need to keep the size of the subset small at every stage. This can be done using a small generating set-finding algorithm, such as the Sims filter or the Jerrum's filter.
Flow of the algorithm
Description of the step of the algorithm:
Start with: a generating set for
Do the following:
- Finding coset representatives: Using a breadth-first search, find a minimal Schreier system of coset representatives for in
- Finding the index: From this, obtain
- Finding a generating set: Using the coset representatives and the generating set , obtain a (possibly larger) generating set for . This uses Schreier's lemma
- Filtering the generating set: Apply a filter to trim the size, and call the filtered generating set .
Analysis of running time
- Finding coset representatives: This takes time since that is the number of edges in the graph.
- Finding the index: This comes for free
- Finding a generating set: This takes time since terms need to be computed and the computation of each requires multiplication operations (which take time).
- Filtering the generating set: This takes time dependent on the choice of filter. A naive analysis on Jerrum's filter reveals that the time taken is because the new generating set with which we start is itself of size . Similarly a naive analysis of the Sims filter reveals that the time it takes is .
Now, if we apply the filter right at the start, then at every step, is polynomially bounded. Thus:
Total time = Time taken to apply filter at the start + Time taken at each stage
Thus:
- In the case of Jerrum's filter:
- In the case of Sims filter: