I have been given a grant by Google for the summer of 2008 to work on permutation groups and partition refinement algorithms in Sage. This page is where I am organizing the work I am doing. I am also keeping a blog.
Goals
- Make permutation groups as independent from GAP as possible: This will be an implicit result of the rest of the work that gets done. This will hopefully speed up some functions as well.
Refactor existing code in Sage.
- Adapt Leon's approach to the isomorphism problem: Currently the approach is to compute a canonical label for each object, and check for equality. Instead, two search trees should be searched at the same time, since this is computationally equivalent if the inputs are isomorphic, and much much faster when they are not, since the search trees will have substantially different structure.
Investigate projective planes of order 16: Gordon Royle pointed out to me earlier this year that there were examples of incidence structures which gave nauty a hard time but which Leon's program was able to handle easily. I wish to be able to explain what the differences are that make this happen.
Different types of refinement processes: The refinement process used in the current setup is the original one described by McKay. However, several improvements/modifications of this are known, which work better in some cases and worse in others.
Piperno describes a method of multirefinement which chooses the best move at each step, making the refinement process more expensive but the size of the search tree smaller.
Sparsity of Symmetries takes advantage of sparse symmetry, i.e. permutations which leave most vertices fixed, to improve runtimes over nauty and its competitors saucy and bliss.
Schreier-Sims algorithm for computing a base and strong generating set. Schreier-Todd-Coxeter-Sims algorithm for computing, in addition, a defining set of relations in terms of the strong generators. (Explanations here.)
Leon notation
( A dictionary to go from Leon's Greek nonsense to something sensible to me. )
E_\Pi(i, N(\Pi)) - split N(\Pi) out of the ith cell of \Pi and put it at the end.
S_{\alpha,i} - E_\Pi(i, \Pi_i \cap \{\alpha\}) - split \alpha out of the ith cell of \Pi and put the rest at the end (radical divergence from McKay, IMHO).
S_{A,i} - same thing with A a subset. S_{A,i,j} - split \alpha_j from cell i. S_{\Phi,i,j} - intersect \Pi_i with \Phi_j.
D_{E,\Phi,i,j}
Define \Xi to be the orbit partition of the subgroup of E which respects \Phi, after applying an element t of E which takes (in order) the fixed cells of \Phi to those of \Pi. Define D_{E,\Phi,i,j} to be E_\Pi(i, \Pi_i \cap \Xi_j). This is independent of t, since the orbits of E_\Phi will translate similarly. As far as I can tell, there is no mention of this in any of McKay's work, but I could be wrong - it may be intrinsic to his R(G,\Pi,\alpha).
In his definition of R-base, the thing to note is that R and D are both refinements that do not go beyond the "coarsest equitable refinement", and he requires that only when the current partition is irreducible with respect to these two that we take one from S, which is like McKay's \perp notation.
Small algorithms which may be necessary
- change base
- Algorithm to express an element of a group in terms of strong generators, in the form of Prop. 1 in [Leon].