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> LoadPackage("vole", false);; 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 BacktrackKit: Constraints 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
See the end of the manual entry for VoleFind.Canonical (5.3-1) for an example of canonisation with Vole.
generated by GAPDoc2HTML