Sims 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	Size is at most $(\genfrac{}{}{0ex}{}{n}{2})=n(n-1)/2$ Size is at most the size of $A$
Guaranteed (order-specific) properties of output	It is a Sims-reduced generating set.
Theoretical significance	shows that the subgroup rank of the symmetric group of degree $n$ is at most $(\genfrac{}{}{0ex}{}{n}{2})$ (we can do much better -- in fact it is at most $(n+1)/2$)
Mode of input processing	As presented here, the algorithms requires storage and manipulation of the entire generating set.
Running time (worst-case)	$O(|A|n^2)$
Memory requirement	$O(max\{\left|A\right|,n^2\})$
Effect of repeated application	The filter is an idempotent filter -- applying it again to the output it produces yields no change.
Sensitivity to order of inputs	The algorithm could produce somewhat different output generating sets depending on the order in which the elements of the input generating set are fed into it.
Competing algorithms	Jerrum's filter is an alternate algorithm. It produces a generating set (a Jerrum-reduced generating set) guaranteed to be smaller, but has a much larger worst-case running time ($O(|A|n^4)$). Sims filter is preferable for getting a quick and dirty generating set, for instance, as an intermediate step to Schreier-Sims algorithm.
Switching option if the algorithm is taking too long	The algorithm can be stopped at any outer pass, and the output it yields is of size at most the size of $A$.

Definitions used

Sims-reduced generating set

Further information: Sims-reduced generating set

Given a permutation group on $\{1,2,3,\dots ,n\}$, a Sims-reduced generating set for it is a generating set with the property that given any $i<j$, there is at most one element in the generating set that sends $i$ to $j$ and fixes all elements less than $i$.

By definition, a Sims-reduced generating set has size at most $(\genfrac{}{}{0ex}{}{n}{2})$.

Relation with other algorithms

Better algorithms

• Jerrum's filter is considered a better algorithm than the Sims filter because it is online, and it is guaranteed to produce a generating set of smaller size (a generating set produced by this filter is termed a Jerrum-reduced generating set). The Sims filter is faster to apply once; however, an algorithm that requires repeated use of the filtered set may prefer Jerrum's filter because the resulting set being small, algorithms that depend on the size of the resulting set are likely to work better.

Idea and outline

Broad idea

The Sims filter works by constructing a partially filled $n\times n$ tableau capable of storing elements of the group, such that:

• The tableau entry with row $i$ and column $j$ must fix all elements upto $i-1$ and must send $i$ to $j$.

The algorithms works in $n$ stages, filling in the $i^{th}$ row of the tableau at the $i^{th}$ stage.

Description of each iteration

Let $A$ denote the initial generating set.

Let $B$ denote the current generating set (initially set $B$ to be $A$). Then, at the $i^{th}$ stage, look at those elements of $B$ that are not already in the tableau. By the manner in which we construct things, it'll turn out that all the elements not already in the tableau must fix the first $i-1$ elements.

Now, as you linearly traverse over the elements of $B$ that are not already in the tableau, do the following:

• If $g$ sends $i$ to $j$ and there is no element yet in the tableau's $(i,j{)}^{th}$ position, put $g$ there.
• If $g$ sends $i$ to $j$ and there is already an element $h$ in the tableau's $(i,j{)}^{th}$ entry, replace $g$ by $g^{-1}h$. This new element will fix $i$ (keep the new element in $B$ bot do not put it in the tableau, it will be handled in the later rounds).
• If $g^{-1}h=e$, remove it (note: this might well be the case even if the original generating set had distinct elements).

Clearly, at every step, the property that $B$ generates the group is preserved, hence, finally we will have a generating set of size $n^2$.

Analysis of running time

Let's analyze the time for each row. For each pass, there are as many as $\left|B\right|$ elements to scan, and for each scanned element, the time taken is roughly $O(n)$. Since $\left|B\right|\le \left|A\right|$ throughout, the total time taken for filling each row is bounded above by $\left|A\right|n$.

Thus, the total time across all rows is $O(|A|n^2)$.