Schreier–Sims Algorithm
Prerequisites: Basic Concepts of Abstract Algebra, Group Theory, Permutations and Arrangements
Introduction
The Schreier–Sims algorithm is an algorithm in computational group theory, named after mathematicians Otto Schreier and Charles Sims. This algorithm can solve many problems in polynomial time, such as finding the order of a finite permutation group, checking whether a given permutation is contained in a given group, etc. The Schreier–Sims algorithm was first introduced by Sims in 1970 based on Schreier's lemma. In 1981[^knuth-year], Donald Knuth further improved the algorithm's runtime. Later, a faster randomized version of the algorithm was developed. Computer algebra systems (such as GAP and Magma) typically use highly optimized Monte Carlo versions of this algorithm[^monte-carlo].
Notation
Following the convention in computational group theory literature, this article denotes group actions as right actions, meaning that composition of permutations proceeds from left to right. The group actions discussed in this article can all be regarded as permutation actions, although some algorithms also hold for more general group actions. Correspondingly, the set of the group action is by default \(X=\{1,2,\cdots,n\}\), and its elements are called points. The result of permutation \(g\) acting on point \(x\) is denoted as \(x^g\); sometimes it is also said that permutation \(g\) moves point \(x\) to point \(x^g\). Finally, under the action of permutation group \(G\), the orbit of point \(x\) is denoted as \(x^G=\{x^g:g\in G\}\), and its stabilizer is denoted as \(G_x=\{g\in G:x^g=x\}\). The concept of stabilizer can also be generalized to a set \(B\subseteq X\), whose stabilizer is defined as \(G_B=\bigcap_{x\in B}G_x\).
Overview
The Schreier–Sims algorithm mainly attempts to solve the following problem:
- Given a set \(S\) consisting of some permutations on a set \(X\) of size \(n\), how can we efficiently store the permutation group \(G=\langle S\rangle\) generated by \(S\) in a computer and complete a series of query tasks about this group?
Clearly, the size of such a group \(G\) may be very large, far exceeding the sizes of the set \(X\) and the generating set \(S\). For example, the symmetric group \(S_n=\langle(123\cdots n),(12)\rangle\) of degree \(n\) has size \(n!\), but it can be generated by just two permutations. Storing every element of the group is unrealistic.
Similar to constructing a basis for a vector space using Gaussian elimination, the idea of the Schreier–Sims algorithm is to find a "basis" for the finite permutation group \(G\):
- The input to the algorithm is a generating set \(S\) of \(G\), containing several permutations;
- If the group \(G\) is nontrivial, we can always find a point \(\beta\) whose position changes under the action of \(G\), i.e., \(|\beta^G|>1\);
- Find the orbit \(\Delta=\beta^{G}\) of point \(\beta\), and for each point \(\delta\in\Delta\), find a permutation \(t_{\delta}\) in group \(G\) that moves point \(\beta\) to \(\delta\);
- Find a generating set \(S'\) for the stabilizer \(G_{\beta}\) of point \(\beta\);
- Recursively call the algorithm on \(G'=\langle S'\rangle\) until the trivial group \(\{e\}\) is obtained.
The rationale behind this idea is that the stabilizer \(G_{\beta}\) of point \(\beta\) is a subgroup of group \(G\), and its set of (right) cosets forms a partition of group \(G\). Moreover, these cosets correspond one-to-one with the orbit \(\beta^G\) of point \(\beta\), and the permutations \(t_{\delta}\) obtained in step 3 are the representatives of these cosets. This set \(T\) of coset representatives is called a transversal of the stabilizer \(G_{\beta}\). In other words, each element \(g\) in group \(G\) corresponds uniquely to a pair \((h,t)\in G_\beta\times T\), and \(g=ht\). Therefore, as long as we can find a way to store the subgroup \(G_{\beta}\) and the corresponding transversal \(T\), we can store the entire group \(G\). However, the problem of storing the subgroup \(G_{\beta}\) has already been solved—just recursively call the algorithm.
Of course, there are many details to be sorted out in the implementation of the algorithm, which is the main content of this article. But before that, we should first examine the result obtained after calling the algorithm, to see what structure the algorithm uses to store the group and what query problems it can solve. For this purpose, some concepts should be clarified.
Stabilizer Chain
Suppose the algorithm is called on group \(G=\{S\}\), for a total of \(k\) times; and during the \(i\)-th call, the input is a set of permutations \(S^{(i-1)}\), the point found is \(\beta_i\), the transversal obtained is \(T_i\), and the generating set obtained for the stabilizer is \(S^{(i)}\). If we denote \(G^{(i)}=\langle S^{(i)}\rangle\), then the algorithm actually obtains the subgroup chain
Moreover, each subgroup in the chain is a stabilizer
Thus, the Schreier–Sims algorithm can be seen as computing such a stabilizer chain.
Base and Strong Generating Set
If a subset \(B\) of set \(X\) satisfies \(G_B=\{e\}\), then \(B\) is called a base of the permutation group \(G\). Clearly, the algorithm above yields a base \(B=\{\beta_1,\cdots,\beta_k\}\). This means that the result of permutation \(g\in G\) acting on these points uniquely determines this permutation within group \(G\). Moreover, the base output by the algorithm also satisfies the condition
That is, each point in the base contains effective information about the elements in the group. Such a base is called nonredundant. The algorithm always outputs a nonredundant base. The stabilizer chain corresponding to such a base is strictly descending.
At the same time, the union of the generating sets obtained by the algorithm
is also a generating set for group \(G\), and it satisfies \(\langle\bar S\cap G^{(i)}\rangle = G^{(i)}\). A generating set satisfying this condition is called a strong generating set of group \(G\) relative to base \(B\). Therefore, the Schreier–Sims algorithm can also be seen as computing a base and strong generating set (BSGS) for group \(G\). This statement is equivalent to the stabilizer chain statement, and this article does not distinguish between them.
Of course, the algorithm also obtains a series of orbits \(\Delta_i=\beta_{i}^{G^{(i-1)}}\) and corresponding transversals \(T_i\). These orbits are called the fundamental orbits of group \(G\). When this article mentions the stabilizer chain or base and strong generating set of group \(G\), it is always assumed that the corresponding fundamental orbits and transversals have been computed together.
Data Structure
This article will provide a series of pseudocode. In the pseudocode, the stabilizer chain (or base and strong generating set) of a group is stored in a data structure \(C\):
The data members of this structure are respectively the generating set \(S\) of the current group, the fundamental orbit \(\Delta\), the corresponding transversal \(T\), and the stabilizer \(C'\) stored as a nested substructure. Of course, the stabilizer \(C'\) is also such a structure. The entire group is actually stored in a layered structure, each layer describing a group in the stabilizer chain. The innermost layer is an empty structure, representing \(G^{(k)}=\{e\}\).
In the pseudocode, the members of this data structure can be accessed by \(C.generators\), \(C.orbit\), \(C.transversal\), and \(C.next\), respectively. The first element of the orbit \(C.orbit[0]\) is by default the point \(\beta\) in the base, and the corresponding coset representative \(C.transversal[\beta]\) is by default the identity transformation \(e\). Note that although array indexing is used here to access elements in the orbit and transversal, they are not necessarily stored as arrays; they should be understood as providing methods to access the first element of the orbit and to query the corresponding coset representative based on a point in the orbit. Implementation details will be discussed later.
Applications
After obtaining the base and strong generating set of a group, a series of query problems about the group can be solved. Among them, the most basic, and also the most frequently encountered in algorithm competitions, are queries for the order of the group and queries about whether a given permutation belongs to the given group.
Order of the Group
If the base and strong generating set of group \(G\) are known, then applying Lagrange's theorem and the orbit-stabilizer theorem, the order of group \(G\) can be computed as
Therefore, simply multiply the sizes of all transversals \(T_i\) (or equivalently, the lengths of the fundamental orbits \(\Delta_i\)) to obtain the order of group \(G\).
Membership Testing
Given the base and strong generating set of group \(G\), we can also determine whether a given permutation \(h\) belongs to group \(G\). This is called the membership testing problem.
This problem can be solved recursively. To determine \(h\in G^{(i-1)}\), first find the coset representative \(t\in T_i\) of the coset of \(G^{(i)}\) containing \(h\). If found, then set \(h'=ht^{-1}\), so \(h=h't\) and \(h\in G^{(i-1)}\) is equivalent to \(h'\in G^{(i)}\); the problem reduces to determining \(h'\in G^{(i)}\). If such a \(t\) cannot be found, or if we have recursed to \(G^{(k)}=\{e\}\) but \(h\neq e\), we can conclude that \(h\notin G\). In fact, this process not only determines \(h\in G\), but in the case \(h\in G\), it can also express \(h\) as a product of a series of coset representatives \(t_k\cdots t_2t_1\), where \(t_i\in T_i\). For elements in group \(G\), such a representation exists and is unique. This again proves that the formula for the order of the group above is correct.
Now write this process as the following pseudocode:
As we will see later, the membership testing problem is also an important component in the implementation of the Schreier–Sims algorithm discussed in this article.
Computation of Orbits, Transversals, and Stabilizers
To implement the Schreier–Sims algorithm, we must first solve the following subproblem:[^orbit-algo]
- Given a generating set \(S\) for group \(G\) and a point \(\beta\), how to compute the orbit \(\beta^G\), the corresponding transversal \(T\), and a generating set for the stabilizer \(G_\beta\)?
This is the problem to be solved in this section.
Storage of Orbits and Transversals
To obtain the orbit and transversal, we can simply search. Pseudocode is as follows:
In concrete implementation, both breadth-first search and depth-first search are acceptable. The number of states traversed by the search is \(|S||T|\), and as long as the orbit and transversal are stored reasonably, the time complexity is completely acceptable.
In the context of permutation groups, an orbit is just a set of at most \(n\) points. To efficiently perform lookup and addition operations, we can use a boolean array or an unordered set for storage. This way, both operations have \(O(1)\) time complexity, and the overall space usage is \(O(n)\). Of course, depending on the implementation of the transversal, we may need to additionally mark the position of the first element.
The problem is what data structure to use to store the corresponding transversal \(T\).
Direct Storage
The simplest method is to directly store every element \(t\) in the transversal \(T\). A single permutation stored in one-line notation requires exactly \(n\) space, so storing such a transversal has space complexity \(O(|T|n)\). The advantage of this approach is that accessing a single coset representative has \(O(1)\) time complexity, at the cost that the initial computation of these coset representatives has time complexity \(O(|T|n)\).
Schreier Tree
Another common approach is to implement a tree structure to store the transversal. It is called a Schreier tree or Schreier vector[^schreier-vector]. It takes \(\beta\) as the root and the elements \(\delta\) in the orbit \(\Delta\) as vertices. Each time a new vertex \(\gamma=\delta^s\) is obtained during the search, an edge is added from the old vertex \(\delta\) to the new vertex \(\gamma\), with the edge recording the index (or pointer) of the permutation \(s\) in the generating set \(S\). Since the generating set is already stored, the additional space complexity for storing the transversal is \(O(|T|)\). For cases where \(n\) is very large, this can effectively save space, and the initial computation has complexity \(O(|T|)\). However, the side effect is that each time we need to obtain a coset representative, we must traverse the edges on the path from the vertex to the root and recompute the coset representative, so the time complexity heavily depends on the depth of the Schreier tree. In general cases, the tree depth may reach \(O(n)\).
In concrete implementation, we need to weigh the time and space complexity according to the actual situation. For scenarios possibly involved in algorithm competitions, \(n\) is usually not large, space is abundant, and time complexity often becomes the bottleneck. We will see later that the most time-consuming step of the Schreier–Sims algorithm requires accessing coset representatives many times, so using direct storage is often better. However, for some application scenarios, \(n\) may be very large, storage space may be more constrained, and it may be necessary to use Schreier trees to store transversals. For such cases, to avoid excessive depth of Schreier trees, researchers have proposed many methods to reconstruct shallow Schreier trees when the tree depth becomes too deep. Interested readers can refer to the literature at the end of the article.
In the pseudocode, this article will not distinguish the specific implementation of transversals, but only assume that the data structure storing the transversal \(T\) implements operations to access and modify the corresponding coset representative \(T[\delta]\) based on orbit element \(\delta\in\Delta\).
Schreier's Lemma
After obtaining the orbit \(\beta^G\) and transversal \(T\), Schreier's lemma then provides a method to obtain a generating set for the stabilizer \(G_\beta\).
Schreier's Lemma
Let group \(G=\langle S\rangle\) have a subgroup \(H\le G\). Let \(T\) be a (right) transversal of subgroup \(H\), with \(e\in T\)[^schreier-lemma-unity], and denote the coset representative \(t\in T\) of \(g\in G\) as \(\overline g\). Then, the set
is a generating set for subgroup \(H\). Its elements are called Schreier generators of subgroup \(H\).
Proof
First, by the definition of coset representatives, \(ts(\overline{ts})^{-1}\in H\) holds for all \(t\in T,s\in S\), so \(\langle U\rangle\subseteq H\).
Conversely, for any \(h\in H\), since \(S\) is a generating set for \(G\ge H\), there must exist a sequence \(s_i\in S\cup S^{-1}\) such that
holds. Let \(t_1=e\), and recursively define \(t_{i+1}=\overline{s_it_i}\in T\). Then, we have
And for each \(i=1,2,\cdots,r\), we have \(t_is_it_{i+1}^{-1}=t_is_i(\overline{t_is_i})^{-1}\in U\cup U^{-1}\subseteq H\), so \(t_{r+1}\in H\). But \(H\cap T=\{e\}\), so \(t_{r+1}=e\). This shows that any \(h\in H\) can be written as a product of a sequence of \(u_i=t_is_it_{i+1}^{-1}\in U\cup U^{-1}\), i.e., \(U\) generates \(H\).
Since the subgroup corresponding to transversal \(T\) is the stabilizer \(G_\beta\), after obtaining transversal \(T\) and combining it with the generating set \(S\) of group \(G\), we can obtain a generating set for the stabilizer \(G_\beta\).
Algorithm
By slightly modifying the above pseudocode, we can obtain a generating set for the stabilizer while computing the orbit and transversal:
In the pseudocode, for each pair \((\delta,s)\), only when no new element is produced in the orbit is \(t_\delta st_{\delta^s}^{-1}\) a new Schreier generator; otherwise, it is the identity transformation \(e\). Therefore, the actual number of Schreier generators generated by the algorithm (including the initial identity transformation) is at most
For general cases, this upper bound is tight.[^upper-bound] However, for the finite groups we actually deal with, this upper bound is quite loose: most of these newly obtained Schreier generators are duplicates of previously obtained generators or can be composed from previous generators.
Since the basic flow of the Schreier–Sims algorithm can be implemented as recursively calling the above algorithm for computing orbits and stabilizers, we have already obtained a naive implementation of the Schreier–Sims algorithm at this point. However, without filtering, the growth rate of the number of Schreier generators is exponential: repeatedly applying \(O(|S_{i}|)=O(|S_{i-1}||T_i|)\) shows that the size of the generating set of the innermost stabilizer will reach \(O(|S||G|)\). This is obviously absurdly inefficient because the innermost stabilizer is \(\{e\}\).
Sims' work provides a method to limit the growth rate of the number of Schreier generators, ensuring that the final strong generating set \(\bar S\) has size \(O(n^2)\). This allows computing the base and strong generating set in polynomial time.
Schreier–Sims Algorithm
To solve the above problem, this section discusses an incremental implementation of the Schreier–Sims algorithm, which yields a strong generating set of size \(O(n^2)\).
Filtering
The core optimization of the Schreier–Sims algorithm over the naive algorithm is quite concise: it requires that before adding any Schreier generator to the generating set of the stabilizer, it must first undergo filtering (sifting). Filtering means first determining whether the new Schreier generator already exists in the subgroup generated by the existing generators, and then only adding those generators that do not yet exist. For this, we only need to use the membership testing algorithm \(\textrm{MembershipTest}(C,h)\) from earlier.
However, the prerequisite for doing this is that based on the Schreier generators already produced for the current group, we have already constructed the stabilizer chain (or base and strong generating set) of the group they generate. This means that each time we add a new Schreier generator to the generating set of the stabilizer, we need to dynamically maintain the inner stabilizer chain for subsequent filtering. But each insertion of a generator at the current layer may produce multiple Schreier generators, which may lead to multiple updates of the inner structure; and each update of the inner structure may trigger multiple updates of even deeper structures.
It seems that the exponential explosion problem mentioned earlier still exists. Actually not. Because filtering is done in advance, only when the generator to be added actually causes the expansion of a certain layer's structure will that layer's structure be updated. This indicates that the number of updates per layer actually equals the number of times the group stored in that layer strictly increases. However, a group of size \(|G|\) has at most a subgroup chain of length \(\log|G|\); because Lagrange's theorem guarantees that each increase in the subgroup chain length at least doubles the group size. This shows that a single-layer structure will be updated at most \(\log|G|\) times, so the final strong generating set \(\bar S\) has size \(|B|\log|G|\).
This estimate can be further improved. Because the group \(G\) appearing here is known to be a subgroup of the symmetric group \(S_n\) of degree \(n\), the length of the subgroup chain of \(G\) cannot exceed that of \(S_n\). It can be proved[^subgroup-chain] that the length of a strictly increasing subgroup chain of \(S_n\) does not exceed \(3n/2\). This shows that the number of updates per layer is actually \(O(n)\). Obviously, the size of the base also does not exceed \(n\). Therefore, the final strong generating set \(\bar S\) has size \(O(n^2)\).
The filtering method mentioned here was proposed by Sims and is also called the Sims filter. There is also a more complex filtering method proposed by Jerrum, called the Jerrum filter, which can guarantee that the resulting strong generating set has size \(O(n)\). Interested readers can study it on their own.
For the filtering process, a small optimization is that in the implementation of \(\textrm{MembershipTest}(C,h)\), we do not output a boolean value, but output the final "sifted element"[^siftee] \(h\) (i.e., replace lines 10 and 14 in the pseudocode with \(\textbf{return }h\)). If the "sifted element" \(h\neq e\), it means membership testing failed, and we can directly add the "sifted element" \(h\) instead of the original \(h\) to the current layer. Here, the "sifted element" \(h\) has already removed several coset representative factors, thus moving fewer elements, so it reduces local computation. This optimization has no impact on the overall complexity.
Procedure
Now we can describe the specific procedure of the Schreier–Sims algorithm: First, initialize an empty structure \(C\) to store the stabilizer chain of the group. Then, add the generators from the generating set \(S\) one by one to structure \(C\). The final structure \(C\) is the stabilizer chain of group \(\langle S\rangle\). Pseudocode is as follows:
The core of the algorithm lies in the step of adding a new generator \(s\) to the current \(C\), i.e., the subroutine \(\textrm{Extend}(C,s)\). As mentioned earlier, before and after adding permutation \(s\), we must ensure that \(C\) is a stabilizer chain. Thus, before adding permutation \(s\), we can first perform filtering. If \(s\) is not in the existing group, we incrementally compute the orbit, transversal, and Schreier generators. Here, "incremental" means not recomputing what has already been computed. Only this can guarantee correct complexity.
Consider how to modify \(\textrm{OrbitTransversalStabilizer}(S,\beta)\) into an incremental version. The state space searched by the algorithm is \(\Delta\times S\). After adding a new generator \(s\), the state space becomes \(\Delta'\times\left(S\cup\{s\}\right)\). The difference between the two is
This means that when adding a new generator \(s\), we first need to compute combinations of the new generator \(s\) with the old orbit and corresponding transversal; if new orbit elements are obtained in this process, we then consider combinations of these elements with all generators (both old and new); the process repeats until the orbit no longer extends.
Pseudocode for adding permutation \(g\) to structure \(C\) is as follows:
This gives the complete Schreier–Sims algorithm.
Another Implementation
The above implementation is already correct, but lines \(12\sim 19\) and \(23\sim 30\) are slightly repetitive. Based on this, Knuth proposed a recursive implementation in his paper, which is more concise. His approach is to view this repetitive part as an update to the transversal (and orbit). Each time the transversal is updated, it is combined with all generators, and depending on whether new coset representatives are produced, it decides whether to recursively call itself or the generator addition procedure. Pseudocode is as follows:
Comparing this pseudocode with that in the previous section, we can see it is correct. Moreover, there is no difference in complexity between the two.
Complexity
To analyze the complexity of the Schreier–Sims algorithm, we need some notation. Let the length of permutations be \(n\), the size of the generating set \(|S|\) be \(m\). The length of the obtained (nonredundant) base is denoted \(|B|\). Moreover, in the final data structure, for the \(i\)-th stabilizer \(G_i\) from the outside inward, the number of generators is denoted \(|S_{i-1}|\), and the size of the transversal (or the length of the orbit) is denoted \(|T_i|\). Below we analyze the time complexity required by the incremental implementation of the Schreier–Sims algorithm described above. The algorithm mainly consists of two parts: filtering, and computation of orbits, transversals, and Schreier generators.
The initially input generators and the Schreier generators obtained during the algorithm all need filtering,
本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用