There are two interfaces to Vole, the 'Simple Interface', which are methods which start with Vole., and the 'Full Interface', which are methods which start with VoleFind.. The simple interface is no less efficient, each of the simple interface methods just call a problem in the full interface. Some problems cannot be expressed in the simple interface, in particular problems which involve solving multiple problems simultaneously.
The 'simple interface' to Vole consists of functions whose names begin Vole.. These methods implement existing methods in core GAP, and some GAP packages.
These functions are given as follows (grouped into sections:)
The following functions have very high quality implementations. The Canonical methods are described below, and are otherwise implemented in the Images package.
CanonicalImage
CanonicalPerm
CanonicalImagePerm
RepresentativeAction
IsConjugate
Stabilizer
These functions are implemented in Digraphs. They are generally slower than the functions provided there, but can be faster for multi-edge and edge-coloured graphs. Vole is much better when we want to search on a group other than the automorphism group on the vertices.
AutomorphismGroup
CanonicalDigraph
DigraphCanonicalLabelling
IsIsomorphicDigraph
IsomorphismDigraphs
These functions are standard group algorithms. Vole can sometimes outperform GAP, particularly when cosets are involved (for example coset intersection), but GAP is often faster for many problems.
TwoClosure
Centralizer
Normalizer
Intersection
Centraliser
Finding a canonical image always requires two arguments:
The group in which we are searching.
The object whose canonical image we want to find.
As a simple example, let's consider 3 sets, and if they are in the same orbit of \(M_{12}\).
gap> LoadPackage("vole", false);; gap> s := [1,2,3,4,5,6]; [ 1, 2, 3, 4, 5, 6 ] gap> t := [2,4,6,8,10,12]; [ 2, 4, 6, 8, 10, 12 ] gap> u := [3,6,9,12,15,18]; [ 3, 6, 9, 12, 15, 18 ] gap> M12 := MathieuGroup(12);; gap> Vole.CanonicalImage(M12, s, OnSets); [ 2, 6, 8, 9, 11, 12 ] gap> Vole.CanonicalImage(M12, t, OnSets); [ 2, 6, 8, 9, 11, 12 ] gap> Vole.CanonicalImage(M12, u, OnSets); [ 2, 3, 4, 5, 15, 18 ]
As \(s\) and \(t\) have the same canonical image, this means they are in the same orbit of \(M_{12}\), which \(u\) is in a different orbit.
How can we find the permutation in \(M_{12}\) which maps \(s\) to \(t\)? The function CanonicalImagePerm gives the permutation which maps something to it's canonical image.
gap> ps := Vole.CanonicalImagePerm(M12, s, OnSets); (1,6,9,5,2,12)(3,8,4,11,10,7) gap> pt := Vole.CanonicalImagePerm(M12, t, OnSets); (1,3,4,12,2,6,11,7)(9,10) gap> OnSets(s, ps); # Gives the canonical image from earlier [ 2, 6, 8, 9, 11, 12 ] gap> OnSets(s, ps*(pt^-1)); # Gives t [ 2, 4, 6, 8, 10, 12 ] gap> ps*(pt^-1) in M12; true
As we can see here, it is easy to get the canonical image from the result of CanonicalImagePerm, but the reverse is not true!
We can find the canonical image of many different types of objects, for example:
gap> Vole.CanonicalImage(M12, [[1,2,3,4],[4,5,6,7]], OnSetsSets); [ [ 2, 3, 7, 12 ], [ 3, 6, 10, 11 ] ] gap> Vole.CanonicalImage(M12, [[1,2,3,4],[4,5,6,7]], OnSetsTuples); [ [ 2, 8, 3, 6 ], [ 6, 4, 10, 5 ] ] gap> Vole.CanonicalImage(M12, DigraphCycle(12), OnDigraphs); <immutable digraph with 12 vertices, 12 edges>
Note that while we could use a tool like Nauty, from the GRAPE or Digraphs packages, to calculate the canonical image of our graph, that doesn't support adding searching within a named group.
The CanonicalImage and CanonicalImagePerm functions work on a wide range of GAP objects and actions -- if there an object or action you find is not implemented, please report it at The vole issue tracker and we will investigate if it is possible to add.
We will begin by working through an example of the intersection of a normaliser and a stabiliser, and then look at how this problem can be more efficiently and directly solved in Vole.
Suppose that we wish to compute the intersection of the stabiliser in \(M_{12}\) of the set \(S:=\{1,2,4,5\}\) with the normaliser of \(H\) in \(G\), where \(H\) and \(G\) are defined by the generating sets given below:
gap> M12 := MathieuGroup(12);; gap> S := [ 1, 2, 4, 5 ];; gap> G := Group([(1,8,7,2,3,10,9,4)(5,6,11,12), (3,11)(4,12,6,8,10)]);; gap> H := Group([(1,2,3,4,9,10,5,6,11,8)(7,12), (1,5,9)(6,12)(8,10)]);;
Thus we wish to compute \({Stab}_{M_{12}}(\{1,2,3,5\}) \cap N_{G}(H)\).
For future reference, we note that the result is a dihedral group with eight elements.
gap> answer := Group([(1,2)(3,10)(4,5)(6,7)(8,9)(11,12), > (2,4)(3,7)(8,12)(9,11)]); Group([ (1,2)(3,10)(4,5)(6,7)(8,9)(11,12), (2,4)(3,7)(8,12)(9,11) ]) gap> StructureDescription(answer); "D8"
With the GAP library, there are several ways to compute this. For example, we can stick as closely to the statement as possible, and first compute the stabiliser and the normaliser separately, and then intersect them:
gap> Intersection(Stabiliser(M12, S, OnSets), > Normaliser(G, H)) > = answer; true
Or we can slightly reformulate the task, and first intersect \(M_{12}\) with \(G\), and then compute the stabiliser of the set in that smaller group, and finally compute the normaliser of \(H\) in that (even smaller) stabiliser:
gap> M12andG := Intersection(M12, G);; gap> stab := Stabiliser(M12andG, S, OnSets);; gap> Normaliser(stab, H) = answer; true
Or we could switch things in the previous example and compute the normaliser before computing the stabiliser in that normaliser:
gap> M12andG := Intersection(M12, G);; gap> norm := Normaliser(M12andG, H);; gap> Stabiliser(norm, S, OnSets) = answer; true
There are several further combinations. Each of the above strategies can be emulated in Vole by prepending “Vole.” to the beginning of each call to Stabiliser, Normaliser, and Intersection, as described in Chapter 4. However, this is not the recommended approach, as we will see below.
gap> stab := Vole.Stabiliser(M12, S, OnSets);; gap> norm := Vole.Normaliser(G, H);; gap> answer = Vole.Intersection(stab, norm); true
We quickly realise that solving our problem with the GAP library interface really requires three separate steps to be undertaken in sequence. This raises some potential disadvantages.
Although each of the above strategies will give the correct answer, it is not obvious which approach gives the best performance: should we compute the normaliser in the stabiliser, or vice versa, or should we do something else? It is not necessarily easy to answer this.
Breaking the problem up into three separate steps requires three instances of a backtrack search, where each instance is unaware of the ones to come. This is not ideal for a number of reasons.
Firstly, backtrack search can be expensive, and so we should aim to minimise the number of times that it is required.
Secondly, a search tends to be quicker when there are more ‘restrictions’ on the search space. Therefore, it is typically better to perform one search with many restrictions rather than performing several searches that each have few restrictions.
The ‘Vole’ way of solving this is problem is to do it in one step with the function VoleFind.Group (5.2-2).
For most users, the easiest way to solve the problem with VoleFind.Group (5.2-2) is to find a collection of constraints that together specify the problem. Constraints are discussed in Chapter 7 of the BacktrackKit manual.
Specifically, we are looking for all permutations that are contained in \(M_{12}\), that stabilise the set \(\{1,2,3,5\}\), that are also contained in \(G\), and that normalise \(H\). Therefore, we can solve the problem with the following constraints:
gap> VoleFind.Group(Constraint.InGroup(M12), > Constraint.Stabilize(S, OnSets), > Constraint.InGroup(G), > Constraint.Normalize(H)) > = answer; true
Vole performs only one search to solve the whole problem.
In order to solve the problem as specified, Vole chooses appropriate refiners for the given collection of constraints. Refiners are documented in Chapter 7. The more confident user may wish to directly specify one or more refiners instead of, and/or in addition to, some of the constraints.
For example, a user may know (or just hope) that the group \(H\) is well-suited to the technique that the refiner GB_Con.NormaliserSimple from the GraphBacktracking package uses to refine for the normaliser. This refiner may be included instead of, or as well as, the constraint Constraint.Normalize(H), since the refiner implies that constraint, but it is perfectly acceptable (and sometimes a good idea) to use multiple refiners for the same constraint.
gap> VoleFind.Group(Constraint.InGroup(M12), > Constraint.Stabilize(S, OnSets), > Constraint.InGroup(G), > GB_Con.NormaliserSimple(H)) > = answer; true gap> VoleFind.Group(Constraint.InGroup(M12), > Constraint.Stabilize(S, OnSets), > Constraint.InGroup(G), > Constraint.Normalise(H), > GB_Con.NormaliserSimple(H)) > = answer; true
generated by GAPDoc2HTML