[MathJax on]

4 Emulating traditional interfaces with Vole

4.1 The concept

The functionality of Vole overlaps with that of GAP and its other packages, such as images and Digraphs.

Vole has its own native interface, which is described in Chapter 5, and which offers highly configurable access to the underlying graph backtracking algorithm. This is the recommended interface to Vole for most users.

However, Vole also provides wrappers around its native interface that allow Vole to emulate some existing interfaces. The purpose of these wrappers is to lower the ‘barrier to entry’ of Vole, so that users who are already familiar with the existing GAP/package functions can quickly get started with Vole.

Where we identify that GAP, or a package, provides a function whose result could reasonably be computed with Vole, we provide a wrapper function whose interface closely matches that of the original function, but which uses Vole to perform the computation. We do not claim that the Vole wrapper functions are necesarily faster than the original functions; see Section 4.1-1.

For example, the GAP function Normaliser (Ref 39.11-1) can be used to compute normalisers of permutation groups. Since Vole can also be used for such computations, we provide the corresponding function Vole.Normaliser (4.4-4), which can be used in the same way. Thus Normaliser(G,U) and Vole.Normaliser(G,U) will (barring bugs!) return equal groups for all permutation groups G and U.

All such functions are contained in the Vole (4.2-1) record, which is documented in Section 4.2. The functions themselves are individually documented in Sections 4.4–4.6.

4.1-1 A warning

Vole's emulated interfaces do not necessarily exhibit the full flexibility, power, and speed of Vole. This is especially for those users who are interesting in controlling and specifying the refiners that are used in a given search, for whom the native interface (Chapter 5) is necessary.

In addition, please note that the Vole wrapper functions (almost) always use the graph backtracking algorithm, and so they may be significantly slower than the corresponding original functions when those functions can cleverly simplify the problem (and perhaps even choose a completely different algorithm), based on the properties of the groups and permutations that are involved.

See Section 1.4 for further comments about the relative performance of Vole in comparison to other tools.

4.2 The Vole record

4.2-1 Vole

Vole is a record that contains all of the Vole wrapper functions that are provided to emulate aspects of GAP, and its packages images and Digraphs. The components of this record are functions that are named to coincide with the corresponding GAP/images/Digraphs functions.

For example, Vole.Normaliser (4.4-4) emulates Normaliser (Ref 39.11-1).

gap> LoadPackage("vole", false);;
gap> Set(RecNames(Vole));
[ "AutomorphismGroup", "CanonicalDigraph", "CanonicalImage", 
  "CanonicalImagePerm", "CanonicalPerm", "Centraliser", "Centralizer", 
  "DigraphCanonicalLabelling", "Intersection", "IsConjugate", 
  "IsIsomorphicDigraph", "IsomorphismDigraphs", "Normaliser", "Normalizer", 
  "RepresentativeAction", "Stabiliser", "Stabilizer", "TwoClosure" ]

4.3 The group actions built into Vole

The supported combinations of objects and actions are the same for the functions in this chapter that require one or two objects, and a corresponding action. This information is shown in the following table and applies, in particular, to:

• Vole.Stabiliser (4.4-2)

• Vole.RepresentativeAction (4.4-3)

• Vole.CanonicalPerm (4.5-1)

• Vole.CanonicalImage (4.5-2)

4.4 Vole functions emulating built-in GAP functions

The following table gives a summary of the Vole wrapper functions and the corresponding GAP functions.

4.4-1 Intersection

Returns: A perm group, a right coset, or an empty list

Vole.Intersection emulates the built-in GAP operation Intersection (Ref 30.5-2), and returns the intersection of the group and/or right coset arguments.

If all of the arguments are groups, then Vole.Intersection again returns a group. Otherwise, if the result is nonempty, then Vole.Intersection returns a GAP right coset object. Note that this non-group case differs from GAP's Intersection (Ref 30.5-2), which always returns a list.

Note that Vole performs the whole intersection in one search, rather than iteratively intersecting the arguments.

There are many reasons why GAP may be faster than Vole for any particular problem; see Section 1.4 for some discussion about this. It may be possible to obtain better performance from Vole by specifying custom refiners with the native interface, see Chapter 5 and Chapter 7.

gap> A6 := AlternatingGroup(6);;
gap> D12 := DihedralGroup(IsPermGroup, 12);;
gap> Vole.Intersection(A6, D12);
Group([ (2,6)(3,5), (1,3,5)(2,4,6) ])
gap> Vole.Intersection(A6 * (1,2), D12 * (3,4));
RightCoset(Group([ (2,6)(3,5), (1,3)(4,6) ]),(1,5,4,2,6,3))
gap> Vole.Intersection(A6 * (1,2), D12 * (3,4), PSL(2,5));
[  ]

4.4-2 Stabiliser

Returns: An permutation group

Vole.Stabiliser emulates the built-in GAP operation Stabiliser (Ref 41.5-2).

The stabiliser of an object in a group G under some group action is the subgroup of G of those elements that fix object under action, i.e. all permutations g in G such that action(object,g)=object.

The permitted combinations of objects and actions are given in the table below.

The default action, in the case that the argument is not given, is OnPoints (Reference: OnPoints). This is the name in GAP of the action given by the ^ operator, i.e. it corresponds to object^g, where g in G. See \^ (Reference: ^).

There are many reasons why GAP may be faster than Vole for any particular problem; see Section 1.4 for some discussion about this. It may be possible to obtain better performance from Vole by specifying custom refiners with the native interface, see VoleFind.Group (5.2-2) and Chapter 7.

gap> Vole.Stabiliser(PGL(2,5), [1,2,3], OnSets);
Group([ (1,3)(5,6), (1,2,3)(4,5,6) ])
gap> D := JohnsonDigraph(4,2);;
gap> G := Stabiliser(PSL(2,5), D, OnDigraphs);;
gap> G = Group([ (1,4,5)(2,6,3), (1,4)(3,6) ]);
true
gap> Elements(G)
>  = SortedList(Filtered(PSL(2,5), g -> OnDigraphs(D, g) = D));
true

4.4-3 RepresentativeAction

Returns: A permutation, or fail

Vole.RepresentativeAction emulates the built-in GAP function RepresentativeAction (Ref 41.6-1).

This function returns an element of the permutation group G that maps object1 to object2 under the given group action, if such an element exists, and it returns fail otherwise.

The permitted combinations of objects and actions are given in the table below.

The default action, in the case that the argument is not given, is OnPoints (Reference: OnPoints). This is the name in GAP of the action given by the ^ operator, i.e. it corresponds to object^g, where g in G. See \^ (Reference: ^).

There are many reasons why GAP may be faster than Vole for any particular problem; see Section 1.4 for some discussion about this. It may be possible to obtain better performance from Vole by specifying custom refiners with the native interface, see VoleFind.Rep (5.2-1) and Chapter 7.

gap> Vole.RepresentativeAction(SymmetricGroup(4), (1,2,3), (1,2,4));
(1,4,3,2)
gap> RepresentativeAction(AlternatingGroup(4), (1,2,3), (1,2,4));
fail
gap> D := CycleDigraph(6);;
gap> Vole.RepresentativeAction(PGL(2,5), D, DigraphReverse(D), OnDigraphs);
(1,4)(2,3)(5,6)

4.4-4 Normaliser

Returns: An permutation group

Vole.Normaliser emulates the built-in GAP operation Normaliser (Ref 39.11-1).

If G and U are permutation groups, then this function returns the normaliser of U in G, N_{G}(U), which is the stabiliser of U under conjugation by G. If U is instead a permutation, then Vole.Normalizer(G,U) returns N_{G}(\langle U \rangle).

There are many reasons why GAP may be faster than Vole for any particular problem; see Section 1.4 for some discussion about this. It may be possible to obtain better performance from Vole by specifying custom refiners with the native interface, see VoleFind.Group (5.2-2) and Chapter 7.

gap> Vole.Normaliser(SymmetricGroup(6), PSL(2,5)) = PGL(2,5);
true
gap> D12 := DihedralGroup(IsPermGroup, 12);;
gap> Vole.Normaliser(SymmetricGroup(6), (1,2,3,4,5,6)) = D12;
true

4.4-5 Centraliser

Returns: An permutation group

Vole.Centraliser emulates the built-in GAP operation Centraliser (Ref 35.4-4).

If G is a group and x is a permutation, then this function returns the subgroup of G comprising its elements that commute with x.

If instead x is group, then this function returns the subgroup of G comprising its elements that commute with all elements of x.

gap> Vole.Centraliser(MathieuGroup(12), (1,11,9,4,3,2)(5,7,8,6,12,10));
Group([ (1,2,3,4,9,11)(5,10,12,6,8,7), (1,5,3,12,9,8)(2,10,4,6,11,7) ])
gap> Vole.Centraliser(Group((1,2,3,4,5,6)), DihedralGroup(IsPermGroup, 12));
Group([ (1,4)(2,5)(3,6) ])

4.4-6 IsConjugate

Returns: true or false

Vole.IsConjugate emulates the built-in GAP function IsConjugate (Ref 39.10-9).

This function returns true if there exists an element of the permutation group G that conjugates x to y, and false otherwise, where x and y are either both permutations, or both permutation groups. Note that x and y are not required to be contained in G.

This function immediately delegates to Vole.RepresentativeAction (4.4-3), which finds a representative conjugating element, or proves that none exists.

There are many reasons why GAP may be faster than Vole for any particular problem; see Section 1.4 for some discussion about this. It may be possible to obtain better performance from Vole by specifying custom refiners with the native interface, see VoleFind.Rep (5.2-1) and Chapter 7.

Conjugacy of permutations:

gap> # Conjugacy of permutations
gap> x := (1,2,3,4,5);; y := (1,2,3,4,6);;
gap> Vole.IsConjugate(SymmetricGroup(6), x, y);
true
gap> Vole.IsConjugate(AlternatingGroup(6), x, y);
false
gap> Vole.IsConjugate(Group([ (5,6) ]), x, y);
true

Conjugacy of groups:

gap> x := Group([ (1,2,3,4,5) ]);;
gap> y := Group([ (1,2,3,4,6) ]);;
gap> Vole.IsConjugate(SymmetricGroup(6), x, y);
true
gap> Vole.IsConjugate(Group([ (1,2)(3,4) ]), x, y);
false
gap> Vole.IsConjugate(Group([ (5,6) ]), x, y);
true

4.4-7 TwoClosure

Returns: A permutation group

Vole.TwoClosure emulates the built-in GAP function TwoClosure (Ref 43.12-3) for a permutation group.

The 2-closure of a permutation group G is the largest group whose orbitals (orbits on pairs of positive integers) coincide with those of G; equivalently, it is the intersection of the automorphism groups of the orbital graphs of G.

Warning: this function currently requires the OrbitalGraphs package, and it will give an error if OrbitalGraphs is not yet loaded.

There are many reasons why GAP may be faster than Vole for any particular problem; see Section 1.4 for some discussion about this. It may be possible to obtain better performance from Vole by specifying custom refiners with the native interface, see VoleFind.Group (5.2-2) and Chapter 7.

gap> LoadPackage("orbitalgraphs", false);;
gap> G := Group([ (1,4)(2,5), (1,3,5)(2,4,6) ]);;  # A4 on six points
gap> (3,6) in G;
false
gap> Vole.TwoClosure(G) = ClosureGroup(G, (3,6));
true

4.5 Vole functions emulating the images package

The following table gives a summary of the correspondence between Vole and the images package.

4.5-1 CanonicalPerm

Returns: A permutation

These functions, which are synonyms of each other, emulate CanonicalImagePerm (images 2.1-3) from the images package, although they supports a wider range of objects and actions.

Suppose that G is a group, and that object and object2 belong to a set on which G has a group action. Then Vole.CanonicalPerm(G,object,action) returns an element g of G, and Vole.CanonicalPerm(G,object2,action) returns an element h of G, such that object and object2 are in the same orbit of G under action if and only if object^g = object2^h.

The permitted combinations of objects and actions are given in the table below.

The default action, in the case that the argument is not given, is OnPoints (Reference: OnPoints). This is the name in GAP of the action given by the ^ operator, i.e. it corresponds to object^g, where g in G. See \^ (Reference: ^).

The native Vole interface for this kind of computation is provided by VoleFind.CanonicalPerm (5.3-2).

Warning: The permutation given by a canonical search and the canonical image that it defines are not guaranteed to be the same across different sessions. In particular, canonical permutations/labellings and images may differ in different versions of Vole, in different versions of GAP, and on different hardware.

gap> Vole.CanonicalPerm(PSL(2,5), JohnsonDigraph(4,2), OnDigraphs);
(1,2,6)(3,4,5)

4.5-2 CanonicalImage

Returns: An image of object

This function emulates CanonicalImage (images 2.1-3) from the images package, although it supports a wider range of objects and actions.

Vole.CanonicalImage returns object^g, where g is the permutation returned by Vole.CanonicalPerm(G,object,action). See Vole.CanonicalPerm (4.5-1) for more information.

The permitted combinations of objects and actions are given in the table below.

The default action, in the case that the argument is not given, is OnPoints (Reference: OnPoints). This is the name in GAP of the action given by the ^ operator, i.e. it corresponds to object^g, where g in G. See \^ (Reference: ^).

The native Vole interface for this kind of computation is provided by VoleFind.CanonicalPerm (5.3-2).

Warning: The permutation given by a canonical search and the canonical image that it defines are not guaranteed to be the same across different sessions. In particular, canonical permutations/labellings and images may differ in different versions of Vole, in different versions of GAP, and on different hardware.

In the following example, we find that three different tuples of points have two different canonical images in A_5:

gap> tuple1 := [1,2,3,4];; tuple2 := [1,2,3,5];; tuple3 := [1,5,2,3];;
gap> A5 := AlternatingGroup(5);;
gap> Vole.CanonicalImage(A5, tuple1, OnTuples);
[ 5, 4, 3, 2 ]
gap> Vole.CanonicalImage(A5, tuple2, OnTuples);
[ 4, 5, 3, 2 ]
gap> Vole.CanonicalImage(A5, tuple3, OnTuples);
[ 4, 5, 3, 2 ]

Therefore, the tuples with the same canonical image are in the same orbit of A_5, and those with different canonical images are in different orbits:

gap> Vole.RepresentativeAction(A5, tuple1, tuple2, OnTuples);
fail
gap> Vole.RepresentativeAction(A5, tuple1, tuple3, OnTuples);
fail
gap> Vole.RepresentativeAction(A5, tuple2, tuple3, OnTuples);
(2,5,3)

4.6 Vole functions emulating the Digraphs package

The following table gives a summary of the correspondence between Vole and the Digraphs package.

4.6-1 AutomorphismGroup

Returns: A permutation group

Vole.AutomorphismGroup emulates the Digraphs package functions AutomorphismGroup (Digraphs 7.2-2), NautyAutomorphismGroup (Digraphs 7.2-4), and BlissAutomorphismGroup (Digraphs 7.2-3).

This function returns the automorphism group of the digraph D. The automorphism group of D is the stabiliser of D in SymmetricGroup(DigraphVertices(D)) under its natural action on digraphs, namely OnDigraphs (Digraphs 7.1-1). The Vole function Vole.Stabiliser (4.4-2) can be used to compute the stabiliser of D in an arbitrary permutation group.

Support for specifying vertex and/or edge colours has not yet been implemented, sorry. We are working on it!

gap> Vole.AutomorphismGroup(JohnsonDigraph(4,2));
Group([ (3,4), (2,3,5,4), (1,2,6,5)(3,4) ])

4.6-2 DigraphCanonicalLabelling

Returns: A permutation

Vole.DigraphCanonicalLabelling emulates the Digraphs package functions BlissCanonicalLabelling (Digraphs 7.2-7) and NautyCanonicalLabelling (Digraphs 7.2-7).

If D is a digraph, and G=SymmetricGroup(DigraphVertices(D)), then this function is a shortcut to Vole.CanonicalPerm(G,D,OnDigraphs). It is also possible to use Vole.CanonicalPerm (4.5-1) to canonise D in an arbitrary permutation group.

Support for specifying vertex and/or edge colours has not yet been implemented, sorry. We are working on it!

Warning: The permutation given by a canonical search and the canonical image that it defines are not guaranteed to be the same across different sessions. In particular, canonical permutations/labellings and images may differ in different versions of Vole, in different versions of GAP, and on different hardware.

gap> Vole.DigraphCanonicalLabelling(JohnsonDigraph(4,2));
(1,2,4,5,3,6)

4.6-3 CanonicalDigraph

Returns: A digraph

Vole.CanonicalDigraph emulates the Digraphs package functions BlissCanonicalDigraph (Digraphs 7.2-9) and NautyCanonicalDigraph (Digraphs 7.2-9).

If D is a digraph, and G=SymmetricGroup(DigraphVertices(D)), then this function is a shortcut to Vole.CanonicalImage(G,D,OnDigraphs). It is also possible to use Vole.CanonicalImage (4.5-2) to canonise D in an arbitrary permutation group.

Warning: The permutation given by a canonical search and the canonical image that it defines are not guaranteed to be the same across different sessions. In particular, canonical permutations/labellings and images may differ in different versions of Vole, in different versions of GAP, and on different hardware.

gap> Vole.CanonicalDigraph(JohnsonDigraph(4,2));
<immutable digraph with 6 vertices, 24 edges>

4.6-4 IsIsomorphicDigraph

Returns: true or false

Vole.IsIsomorphicDigraph emulates the Digraphs package function IsIsomorphicDigraph (Digraphs 7.2-15).

If D1 and D2 are digraphs, then this function returns true if there exists any permutation that maps D1 to D2 under the OnDigraphs (Digraphs 7.1-1) action, and it returns false otherwise. See also IsomorphismDigraphs (4.6-5), which this function calls.

gap> D := CycleDigraph(6);;
gap> Vole.IsIsomorphicDigraph(D, DigraphReverse(D));
true
gap> Vole.IsIsomorphicDigraph(D, DigraphDual(D));
false

4.6-5 IsomorphismDigraphs

Returns: A permutation, or fail

Vole.IsomorphismDigraphs emulates the Digraphs package function IsomorphismDigraphs (Digraphs 7.2-17).

If D1 and D2 are digraphs, then this function returns some permutation that maps D1 to D2 under the OnDigraphs (Digraphs 7.1-1) action, if one exists, and it returns fail otherwise. In other words, this function call is equivalent to VoleFind.Rep(Constraint.Transport(D1,D2,OnDigraphs).

Vole can also find such a permutation subject to additional properties, such as belonging to particular groups or cosets, or stabilising certain objects. See VoleFind.Rep (5.2-1) for more information.

gap> D := CycleDigraph(6);;
gap> Vole.IsomorphismDigraphs(D, DigraphReverse(D));
(1,4)(2,3)(5,6)
gap> Vole.IsomorphismDigraphs(D, DigraphDual(D));
fail

generated by GAPDoc2HTML