Jerrum's filter

Summary

Item	Value
Problem being solved	small generating set-finding problem
Input format	set $S=\{1,2,3,\dots ,n\}$, generating set $A$ for group $G$ of permutations on $S$. In other words, $G$ is a subgroup of the symmetric group of degree $n$.
Output format	a new generating set for $G$
Guaranteed (general) properties of output generating set	Size is at most $n-1$ Size is at most the size of $A$
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 $n$ is at most $n-1$ (we can do much better, in fact, it is at most $(n+1)/2$ -- 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 $A$ is taken one at a time. Applying the algorithm to an initial segment of $A$ is equivalent to terminating the algorithm applied to $A$ once that initial segment has been processed.
Running time	$O(n^{4})$ for processing each element of $A$, so a total of $O(|A|n^{4})$. In practice, the running time could be much less for many elements.
Memory requirement	$O(n^{2})$ (excluding input storage, since input is processed online) -- need to store and manipulate $O(n)$ permutations on $n$ elements at a time, as well as a graph with $O(n)$ 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 ($O(|A|n^{2})$) 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 $A$.
Single parallelizable version	Splitting $A$ into $k$ 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 $O(|A|n^{4}/k)+O(n^{5}k)$. If $|A|=O(n^{\alpha })$ with $\alpha >1$, the optimal $k=O(n^{(\alpha -1)/2})$ and the time taken is $O(n^{(9+\alpha )/2})$, as opposed to $O(n^{4+\alpha })$ 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 $G$ with generating set $A$ acts on a set $S$, we construct a graph where two vertices in $S$ (the cardinality $n$ set on which $G$ acts) are joined by a directed edge if there is an element in $A$ that takes one to the other. This graph has a lot of edges, in particular, it has $n$ edges for each element of $A$ (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 $A$, 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 $n-1$, and hence, once the graph has been made acyclic, the generating set has also been made small.

Outer loop of algorithm

Let $A$ be a generating set of the group $G$. The target of Jerrum's filter is to, starting from $A$, construct a small generating set from $G$.

Jerrum's filter uses an online algorithm. The algorithm reads in an element of $A$ at a time and keeps constructing a generating set that always generates the same subgroup as the part of $A$ read so far, and that is always small in size.

Aspect of outer loop	Details
Initialization	Set $B$ to be the empty set Set $X$ as the empty graph whose vertices are the elements of $S$
Beginning of each step	Read a new element of $A$
Guaranteed conditions at the end of each step of the outer loop	$B$ (as constructed so far) generates the same subgroup of $S_{n}$ as the part of $A$ that has been read so far. The size of $B$ is at most the size of the part of $A$ that has been read so far. The size of $B$ is at most $n-1$. $X$ and $B$ are related as follows: for every element of $B$, there is an edge in $X$ from the least element moved by it to its image (that is, for $b\in B$, if $i$ is the smallest element moved by $b$, there will be an edge from $i$ to $b.i$). $X$ has no other edges. $X$ (as an undirected graph) is an acyclic graph. In particular, it has at most $n-1$ edges.

The processing within each step

Suppose $A_{0}$ is the part of $a$ that had been read in the past, $a$ is the new element, and $A_{1}=A_{0}\cup \{a\}$. Denote the size of $B$ at the beginning of the step by $s$.

No.	Goal	Steps	Subgroup generated by $B$	Size of $B$ (relative terms) at the end of this part	Size of $B$ (absolute bounds) at the end of this part	Relation between $B$ and $X$	Restrictions of $X$ at the end of this part	Run-time bound for this step
-- (before we begin)	--	--	Same as subgroup generated by $A_{0}$	$s$	at most $n-1$ at most size of $A_{0}$	$X$ is obtained from $B$ by constructing one edge, for every element of $B$, from the least element moved by it to its image.	$X$ (as an undirected graph) is acyclic.	--
1	Update $B$ and $X$ so that $B$ generates the same subgroup as $A_{1}=A_{0}\cup \{a\}$	[SHOW MORE] Read the new letter $a$. If $a=e$ or $a\in B$ or $a^{-1}\in B$, do not change $B$ at all. Otherwise, replace $B$ by $B\cup \{a\}$. Find the smallest element of $S$ moved by $a$, and add an edge from this element to its image under $a$ (if the edge is already present, add it as a double edge, step (2) will in fact fix the problem of the cycle of length two).	Same as subgroup generated by $A_{1}$	either $s$ or $s+1$.	at most $n$ at most size of $A_{1}$.	$X$ is obtained from $B$ by constructing one edge, for every element of $B$, from the least element moved by it to its image.	$X$ (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.	$O(n^{2})$ (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 $X$ and $B$ so that $X$ becomes acyclic.	Iterate the fix the cycle inner loop (see below) as long as $X$ (as an undirected graph) is not acyclic.	Same as subgroup generated by $A_{1}$	either $s$ or $s+1$	at most $n-1$ at most $|A_{1}|$	$X$ is obtained from $B$ by constructing one edge, for every element of $B$, from the least element moved by it to its image.	$X$ (as an undirected graph) is acyclic.	$O(n^{4})$, obtained as $O(n^{2})$ running time for each iteration and $O(n^{2})$ number of iterations.

Below is the fix the cycle inner loop. Note that this loop is initiated only in case we did actually change $B$ to $B\cup \{a\}$. 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 $B$ (relative terms)	Size of $B$ (absolute bound)	Why does the subgroup generated by $B$ remain equal to $\langle A_{1}\rangle$?	Run-time bound for this step
IL1	Find a cycle in $X$ 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 $s+1$	at most $n$ at most $|A_{1}|$	no change to $B$ in this step	$O(n)$ -- we are trying to find a cycle in a graph with $O(n)$ edges and $O(n)$ vertices.
IL2	Find the smallest element (of $S=\{1,2,3,\dots ,n\}$) that is a vertex in the cycle. Call it $m$. Find an edge in the cycle coming out of $m$ and let $g$ be the corresponding element of $B$.	By the construction of $X$, every edge must be from a smaller element to a bigger element. Since $m$ is the smallest element of the cycle, an edge of the cycle containing $m$ is between $m$ and a bigger element of $S$, hence it must be coming out of $m$.	remains $s+1$	at most $n$ at most $|A_{1}|$	no change to $B$ in this step	$O(n)$
IL3 (bottleneck step)	Consider the following element $h$ of $G$: a cyclic product of the elements around the cycle, based at that smallest element, with suitable use of inverses.	$h$ is a product of elements of the cycle and their inverses, all of which originate in a vertex that is at least equal to $m$. Thus, $h$ fixes $1,2,\dots ,m-1$. It also fixes $m$ because it is a cyclic product corresponding to a cycle that starts and ends at $m$.	remains $s+1$	at most $n$ at most $|A_{1}|$	no change to $B$ in this step	$O(n^{2})$: we have to do a multiplication of at most $n$ elements, and each single multiplication takes $O(n)$ time.
IL4	If $h$ is the identity element: Delete $g$ from $B$ and delete the corresponding edge from $X$. Exit the loop.	We know that $X$ has cyclomatic number one, so deleting one edge of a cycle in $X$ makes it acyclic.	conditional: if the condition applies, the size becomes $s$ (and we exit the loop). If it doesn't, the size remains $s+1$.	conditional: at most $n-1$ at most $|A_{0}|$	If the cyclic product $h$ is the identity element, then that means that $g$ can be rewritten in terms of the elements of $B$ corresponding to the remaining elements of the cycle, which means it is redundant as an element of $B$. Thus, it can be deleted.	$O(1)$
IL5	Delete $g$ from $B$, add $h$ to $B$. Delete the edge corresponding to $g$ from $X$, and add an edge corresponding to $h$ to $X$.		The size remains $s+1$	at most $n$ at most $|A_{1}|$	The cyclic product $h$ can be written as $g$ (or $g^{-1}$) times a product of other elements of $B$ and their inverses. Conversely, $g$ can be written in terms of $h$ and these other elements. Thus, replacing $g$ by $h$ does not change the subgroup generated.	$O(n)$

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 "$h$ is the identity element case" and this we exit the loop with the size of $B$ equal to $s$, i.e., the reading in of $A$ did not in fact increase the size of $B$. 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 $B$ is $s+1$, i.e., the reading in of $a$ did increment the size.

Note also that if $B$ already has size $n-1$, 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 $n(s+1)$, which is $O(n^{2})$, because $s+1\leq n$. The argument is below:

Step no.	Assertion	Explanation
W1	The size of $B$ never exceeds $s+1$	See the size bounds column above.
W2	In every iteration, the newly added permutation to $B$ 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 $g$ being deleted has weight $m$. The permutation $h$ being added is a product of individual permutations all with weight at least $m$, so it fixes $1,2,3,\dots ,m-1$. Since it is a cyclic product based at $m$, it also fixes $m$. Thus, the weight of $h$ is at least $m+1$, which is strictly greater than $m$ (see (IL3)-(IL5)).
W3	The total weight of $B$ 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 $B$ is at most $n(s+1)$, and in particular, is bounded	The weight of every permutation is at most $n$, and the size of $B$ is bounded by (W1).
W5	The fix the cycle loop must terminate after finitely many iterations, after which $X$ becomes acyclic (i.e., it has no undirected cycles). Moreover, the number of iterations is at most $n(s+1)$.	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 $O(n^{4})$. The bottleneck step is the fix the cycle inner loop, which could iterate $O(n^{2})$ times and within which each iteration takes $O(n^{2})$ time. Within each iteration of the loop, the bottleneck step is the computation of a product of permutations corresponding to a cycle in $X$.

The total running time is $O(|A|n^{4})$.

If $|A|$ is much smaller than $n$, then the step sizes can be bounded better in terms of $|A|$. However, in this case, Jerrum's filter may not be useful as it may not actually reduce the size of the generating set.