Jerrum's filter
Contents
Summary
Item | Value |
---|---|
Problem being solved | small generating set-finding problem |
Input format | set , generating set for group of permutations on . In other words, is a subgroup of the symmetric group of degree . |
Output format | a new generating set for |
Guaranteed (general) properties of output generating set | Size is at most Size is at most the size of |
Guaranteed (order-specific) properties of output generating set | It is a Jerrum-reduced generating set for the chosen ordering. |
Theoretical significance | shows that the subgroup rank of the symmetric group of degree is at most (we can do much better, in fact, it is at most -- see subgroup rank of symmetric group is about half the degree, but there is no short algorithm to produce such a small generating set in general). |
Mode of input processing | online -- each element of is taken one at a time. Applying the algorithm to an initial segment of is equivalent to terminating the algorithm applied to once that initial segment has been processed. |
Running time | for processing each element of , so a total of . In practice, the running time could be much less for many elements. |
Memory requirement | (excluding input storage, since input is processed online) -- need to store and manipulate permutations on elements at a time, as well as a graph with edges. |
Effect of repeated application | The filter is an idempotent filter -- applying it again to the generating set produced by one iteration of the algorithm does not yield any improvement. |
Competing algorithms | Sims filter is an alternate algorithm. It creates a possibly larger generating set (a Sims-reduced generating set) but takes less time () to produce the generating set. A Jerrum-reduced generating set is already Sims-reduced. Jerrum's filter is used if getting a small generating set is more important (e.g., if the generating set is being used intensively in the future) while the Sims filter is used if a quick and dirty generating set suffices. |
Switching options if it is taking too long | At any stage, the algorithm can be terminated with the output on the input processed so far plus the unprocessed input. The output created in this fashion is guaranteed to still be at most as big as . |
Single parallelizable version | Splitting into subsets of equal size, applying Jerrum's filter to all of them in parallel and then applying Jerrum's filter to the union of the reduced generating sets takes time . If with , the optimal and the time taken is , as opposed to in serial. Note: In practice, the algorithm may run much faster. |
Related problems
Problems that use the Jerrum's filter
In any problem that reduces to the small generating set-finding problem, we can use Jerrum's filter. For instance:
- In the order-finding problem, we need to repeatedly pass from a generating set of the bigger group to the smaller group. Jerrum's filter can be applied here to cut the size of the generating set after every occasion where we pass from the bigger group to the smaller group.
Other algorithms for the same problem
An alternative algorithm that can be used in place of Jerrum's filter is the Sims filter. The Sims filter outputs, in general, a much larger generating set, but the advantage of this filter is that it takes far less time.
In the Schreier-Sims algorithm, for instance, we use the Sims filter.
Idea and outline
Broad idea
Recall that usually, when a group with generating set acts on a set , we construct a graph where two vertices in (the cardinality set on which acts) are joined by a directed edge if there is an element in that takes one to the other. This graph has a lot of edges, in particular, it has edges for each element of (some of these edges may be loops).
The graph that we look at in Jerrum's filter has only one edge for each element of , namely the edge from the least point moved by that element.
The idea is to keep transforming the generating set (which automatically keeps transforming the graph) till we attain an acyclic graph. The number of edges in this graph is at most , and hence, once the graph has been made acyclic, the generating set has also been made small.
Outer loop of algorithm
Let be a generating set of the group . The target of Jerrum's filter is to, starting from , construct a small generating set from .
Jerrum's filter uses an online algorithm. The algorithm reads in an element of at a time and keeps constructing a generating set that always generates the same subgroup as the part of read so far, and that is always small in size.
Aspect of outer loop | Details |
---|---|
Initialization | Set to be the empty set Set as the empty graph whose vertices are the elements of |
Beginning of each step | Read a new element of |
Guaranteed conditions at the end of each step of the outer loop | (as constructed so far) generates the same subgroup of as the part of that has been read so far. The size of is at most the size of the part of that has been read so far. The size of is at most . and are related as follows: for every element of , there is an edge in from the least element moved by it to its image (that is, for , if is the smallest element moved by , there will be an edge from to ). has no other edges. (as an undirected graph) is an acyclic graph. In particular, it has at most edges. |
The processing within each step
Suppose is the part of that had been read in the past, is the new element, and . Denote the size of at the beginning of the step by .
No. | Goal | Steps | Subgroup generated by | Size of (relative terms) at the end of this part | Size of (absolute bounds) at the end of this part | Relation between and | Restrictions of at the end of this part | Run-time bound for this step |
---|---|---|---|---|---|---|---|---|
-- (before we begin) | -- | -- | Same as subgroup generated by | at most at most size of |
is obtained from by constructing one edge, for every element of , from the least element moved by it to its image. | (as an undirected graph) is acyclic. | -- | |
1 | Update and so that generates the same subgroup as | [SHOW MORE] | Same as subgroup generated by | either or . | at most at most size of . |
is obtained from by constructing one edge, for every element of , from the least element moved by it to its image. | (as an undirected graph) has cyclomatic number at most one. Hence, it has at most one cycle, and if it does have a cycle, that cycle must involve the newly added edge. | (this is roughly the time cost of checking equality with existing elements, adding the element, making changes to the graph etc. We could probably do better, but in any case this is not the bottleneck step). |
2 | Fix and so that becomes acyclic. | Iterate the fix the cycle inner loop (see below) as long as (as an undirected graph) is not acyclic. | Same as subgroup generated by | either or | at most at most |
is obtained from by constructing one edge, for every element of , from the least element moved by it to its image. | (as an undirected graph) is acyclic. | , obtained as running time for each iteration and number of iterations. |
Below is the fix the cycle inner loop. Note that this loop is initiated only in case we did actually change to . The loop steps are denoted IL1, IL2, etc. to avoid confusion with the numbering above:
Inner loop step no. | What the step does | Why it works and what is guaranteed | Size of (relative terms) | Size of (absolute bound) | Why does the subgroup generated by remain equal to ? | Run-time bound for this step |
---|---|---|---|---|---|---|
IL1 | Find a cycle in as an undirected graph | There is exactly one cycle. This is because there is at least one cycle (otherwise we would have quit the loop) and there is at most one cycle (because the cyclomatic number never exceeds one). Further, the cycle, if it exists, must include the edge that was most recently added. | remains | at most at most |
no change to in this step | -- we are trying to find a cycle in a graph with edges and vertices. |
IL2 | Find the smallest element (of ) that is a vertex in the cycle. Call it . Find an edge in the cycle coming out of and let be the corresponding element of . | By the construction of , every edge must be from a smaller element to a bigger element. Since is the smallest element of the cycle, an edge of the cycle containing is between and a bigger element of , hence it must be coming out of . | remains | at most at most |
no change to in this step | |
IL3 (bottleneck step) | Consider the following element of : a cyclic product of the elements around the cycle, based at that smallest element, with suitable use of inverses. | is a product of elements of the cycle and their inverses, all of which originate in a vertex that is at least equal to . Thus, fixes . It also fixes because it is a cyclic product corresponding to a cycle that starts and ends at . | remains | at most at most |
no change to in this step | : we have to do a multiplication of at most elements, and each single multiplication takes time. |
IL4 | If is the identity element: Delete from and delete the corresponding edge from . Exit the loop. | We know that has cyclomatic number one, so deleting one edge of a cycle in makes it acyclic. | conditional: if the condition applies, the size becomes (and we exit the loop). If it doesn't, the size remains . | conditional: at most at most |
If the cyclic product is the identity element, then that means that can be rewritten in terms of the elements of corresponding to the remaining elements of the cycle, which means it is redundant as an element of . Thus, it can be deleted. | |
IL5 | Delete from , add to . Delete the edge corresponding to from , and add an edge corresponding to to . | The size remains | at most at most |
The cyclic product can be written as (or ) times a product of other elements of and their inverses. Conversely, can be written in terms of and these other elements. Thus, replacing by does not change the subgroup generated. |
Note that there are two ways that the fix the cycle loop could terminate. The first is that we reach a stage where we enter the " is the identity element case" and this we exit the loop with the size of equal to , i.e., the reading in of did not in fact increase the size of . The other case is that we reach a stage that the graph becomes acyclic at the end of the inner loop iteration. In this case, the size of is , i.e., the reading in of did increment the size.
Note also that if already has size , the loop must terminate through the identity element case since there is no scope for the size to increase.
We now show that the do-while loop terminates in finitely many iterations.
Weight argument
Define the weight of a permutation as the smallest element moved by it, and define the weight of a set of permutations as the sum of the weights of individual permutations in that set. We show that the process must terminate in finitely many steps. In fact, the number of steps is at most , which is , because . The argument is below:
Step no. | Assertion | Explanation |
---|---|---|
W1 | The size of never exceeds | See the size bounds column above. |
W2 | In every iteration, the newly added permutation to has higher weight than the deleted permutation. In graph terms, the newly added edge originates from a higher vertex than the deleted edge. | The permutation being deleted has weight . The permutation being added is a product of individual permutations all with weight at least , so it fixes . Since it is a cyclic product based at , it also fixes . Thus, the weight of is at least , which is strictly greater than (see (IL3)-(IL5)). |
W3 | The total weight of increases strictly (by at least one) at every iteration of the fix the cycle loop. | This is obvious from Step (W2). |
W4 | The total weight of is at most , and in particular, is bounded | The weight of every permutation is at most , and the size of is bounded by (W1). |
W5 | The fix the cycle loop must terminate after finitely many iterations, after which becomes acyclic (i.e., it has no undirected cycles). Moreover, the number of iterations is at most . | This follows immediately from Steps (W3) and (W4) -- the total weight is increasing at every iteration by at least one, but is bounded from above. |
Analysis of running time
The run-time bounds column in the algorithm show that the total run time for reading each element is . The bottleneck step is the fix the cycle inner loop, which could iterate times and within which each iteration takes time. Within each iteration of the loop, the bottleneck step is the computation of a product of permutations corresponding to a cycle in .
The total running time is .
If is much smaller than , then the step sizes can be bounded better in terms of . However, in this case, Jerrum's filter may not be useful as it may not actually reduce the size of the generating set.