[MathJax off]

2 Minimal and Canonical Images

Given a group \(G\) and action \(A\), the minimal image of an object \(O\) is the smallest image of \(O\) under any element of \(G\), under the action \(A\).

As a more concrete example, let us consider the minimal image of the set [2,3,5,7] under a group \(G\).

We can calculate all the images of our set under \(G\), then choose the smallest one.

gap> G := Group((1,2,3)(4,5,6)(7,8,9),(1,4,7)(2,5,8)(3,6,9));;
gap> List(G, g -> OnSets([2,3,5,7], g) );
[ [ 2, 3, 5, 7 ], [ 1, 2, 4, 9 ], [ 1, 3, 6, 8 ], [ 2, 4, 8, 9 ], 
  [ 1, 6, 7, 8 ], [ 3, 5, 7, 9 ], [ 1, 5, 6, 8 ], [ 3, 4, 5, 7 ], 
  [ 2, 4, 6, 9 ] ]
gap> Minimum(List(G, g -> OnSets([2,3,5,7], g) ) );
[ 1, 2, 4, 9 ]

This is very inefficient, as it requires enumerating all members of \(G\). The images package produces a function MinimalImage (2.2-1), which performs this same operation more efficiently.

gap> LoadPackage("images", false);
true
gap> MinimalImage(G, [2,3,5,7], OnSets);
[ 1, 2, 4, 9 ]

The most common use of MinimalImage is to categorise objects into equivalence classes. This next example shows [2,3,5,7] and [1,6,7,8] are in the same orbit, while [3,5,7,8] is in a different orbit.

gap> MinimalImage(G, [2,3,5,7], OnSets);
[ 1, 2, 4, 9 ]
gap> MinimalImage(G, [1,6,7,8], OnSets);
[ 1, 2, 4, 9 ]
gap> MinimalImage(G, [3,5,7,8], OnSets);
[ 1, 2, 6, 8 ]

The result configuration option changes what is returned: the image itself (GetImage, the default), a permutation performing the mapping (GetPerm), or just whether the object already is its own image (GetBool, which is often much faster to compute).

gap> p := MinimalImage(G, [2,3,5,7], OnSets, rec(result := GetPerm));
(1,3,2)(4,6,5)(7,9,8)
gap> OnSets([2,3,5,7], p);
[ 1, 2, 4, 9 ]
gap> MinimalImage(G, [2,3,5,7], OnSets, rec(result := GetBool));
false

In this situation, we do not really need the minimal image, just a method of telling if two sets are in the same equivalence class.

Motivated by this, this package provides CanonicalImage (2.2-5). CanonicalImage(G,O,A) returns some image of \(O\) by an element of \(G\) under the action \(A\), guaranteeing that if two objects O1 and O2 are in the same orbit of \(G\) then CanonicalImage(G,O1,A) = CanonicalImage(G,O2,A). However, the canonical image is not "minimal" under any sensible ordering. The advantage of CanonicalImage is that it is much faster than MinimalImage, often by orders of magnitude.

WARNING: The value of MinimalImage will remain identical between versions of GAP and the Images package, unless bugs are discovered. This is not true for CanonicalImage.

2.1 Supported objects and actions

MinimalImage (2.2-1), CanonicalImage (2.2-5) and their variants accept the following combinations of object and action. The action argument defaults to OnPoints in every case, which for lists is not a supported action, so for lists the action should always be given.

• a set of positive integers, with OnSets;

• a list of positive integers, with OnTuples;

• a set of sets of positive integers, with OnSetsSets;

• a list of sets of positive integers, with OnTuplesSets;

• a positive integer, with OnPoints;

• a permutation, transformation or partial permutation, with OnPoints (that is, up to conjugacy);

• a digraph (from the Digraphs package), with OnDigraphs (the group must move only vertices of the digraph, and multidigraphs are not supported);

• a multiplication (Cayley) table, with OnMultiplicationTables (2.2-2);

• a fundamental structure (see Chapter 3), with OnFundamental.

For digraphs the order minimised is the sorted list of arcs, compared lexicographically, so the minimal image is the relabelling whose arc list Set(DigraphEdges(D)) is smallest. This is neither the ordering of < on digraph objects nor the lexicographic order on adjacency matrices read row by row as 0/1 strings. An undirected graph is represented by a symmetric digraph and needs no separate treatment.

Not every configuration option applies to every combination: the stabilizer and getStab options only affect sets, transformations, permutations, partial permutations, digraphs and multiplication tables, and the order option is ignored for OnSetsSets. See ImagesAdvancedConfig (2.2-6) for the details.

2.2 Function documentation

2.2-1 MinimalImage

MinimalImage returns the minimal image of pnt under the group G. IsMinimalImage returns a boolean which is true if MinimalImage would return pnt (so the value is its own minimal image).

MinimalImagePerm returns a permutation in G which maps pnt to its minimal image.

The supported combinations of pnt and act are listed in Section 2.1. The option Config defines a number of advanced configuration options, which are described in ImagesAdvancedConfig (2.2-6). Note that passing an order option changes which image these functions compute: with any order other than CanonicalConfig_Minimum they behave like CanonicalImage (2.2-5) and the result need not be minimal.

2.2-2 OnMultiplicationTables

The action of a permutation g on a multiplication (Cayley) table: the table of the isomorphic structure on the relabelled elements, so OnMultiplicationTables(T, g)[i^g][j^g] = T[i][j]^g. A table is a list of \(n\) rows of length \(n\) with entries in [1..n], as produced by MultiplicationTable; two magmas are isomorphic precisely when their tables lie in the same orbit under SymmetricGroup(n).

MinimalImage (2.2-1) with this action returns the lexicographically least table in the orbit (comparing tables row by row, which is GAP's ordering of the tables as lists), so it is a distinguished representative of the isomorphism class of the magma.

gap> T := MultiplicationTable(CyclicGroup(4));;
gap> MinimalImage(SymmetricGroup(4), T, OnMultiplicationTables);
[ [ 1, 2, 3, 4 ], [ 2, 1, 4, 3 ], [ 3, 4, 2, 1 ], [ 4, 3, 1, 2 ] ]

2.2-3 IsMinimalImageLessThan

IsMinimalImageLessThan checks if the minimal image of A under the group G is smaller than B.

It returns MinImage.Smaller, MinImage.Equal or MinImage.Larger, if the minimal image of A is smaller, equal or larger than B.

A and B must be sets of the same size, and act must be OnSets; no other actions are currently supported, and this function accepts no configuration record.

2.2-4 MinimalImageOrderedPair

MinimalImageOrderedPair returns the lexicographically smallest pair [A,B] such that some single g in G maps pair[1] to A and pair[2] to B under act. MinimalImageUnorderedPair instead minimises over both orderings of the pair, so exchanging the two entries of pair does not change the result. The default action is OnPoints.

2.2-5 CanonicalImage

CanonicalImage returns a canonical image of pnt under the group G. IsCanonicalImage returns a boolean which is true if CanonicalImage would return pnt (so the value is its own canonical image).

CanonicalImagePerm returns a permutation in G which maps pnt to its canonical image.

By default, these functions use CanonicalConfig_Fast, an alias for the fastest known ordering (currently CanonicalConfig_RareRatioOrbitFixPlusMin), which may change in new versions of the package. The supported combinations of pnt and act are listed in Section 2.1. The option Config defines a number of advanced configuration options, which are described in ImagesAdvancedConfig (2.2-6). These include the ability to choose the canonicalising algorithm used.

2.2-6 ImagesAdvancedConfig

This section describes the advanced configuration options for both MinimalImage (2.2-1) and CanonicalImage (2.2-5). Assume we have called MinimalImage (2.2-1) or CanonicalImage (2.2-5) with arguments (G,O,A).

order

The search ordering used while building the image. The most useful values are:

CanonicalConfig_Minimum

Lexicographically smallest image -- same as using MinimalImage.

CanonicalConfig_FixedMinOrbit

Lexicographically smallest set under the ordering of the integers given by the MinOrbitPerm function. This ordering (and CanonicalConfig_FixedMaxOrbit) is not supported when canonicalising transformations, permutations or partial permutations, and will raise an error there.

CanonicalConfig_Fast

The current best algorithm, and the default for CanonicalImage (2.2-5). It is an alias, currently for CanonicalConfig_RareRatioOrbitFixPlusMin, and may change between versions of the package.

The full list of orderings, whose behaviour is described in the paper [JJPW19], is: CanonicalConfig_Minimum, CanonicalConfig_MinOrbit, CanonicalConfig_MaxOrbit, CanonicalConfig_SingleMaxOrbit, CanonicalConfig_RareOrbit, CanonicalConfig_CommonOrbit, CanonicalConfig_RareRatioOrbit, CanonicalConfig_CommonRatioOrbit, CanonicalConfig_RareRatioOrbitFix, CanonicalConfig_CommonRatioOrbitFix, CanonicalConfig_RareRatioOrbitFixPlusMin, CanonicalConfig_RareRatioOrbitFixPlusRare, CanonicalConfig_RareRatioOrbitFixPlusCommon, CanonicalConfig_RareOrbitPlusMin, CanonicalConfig_RareOrbitPlusRare, CanonicalConfig_RareOrbitPlusCommon, CanonicalConfig_FixedMinOrbit, CanonicalConfig_FixedMaxOrbit and CanonicalConfig_Fast.

Note that these values are the value of the order component of the configuration record, as in rec(order := CanonicalConfig_Fast) -- passing one directly as the whole configuration record is an error. For the action OnSetsSets the ordering is currently ignored, and the minimal image is computed whatever order is given.

result

What to return: GetImage (the image, the default), GetPerm (a permutation in G mapping O to its image, as MinimalImagePerm (2.2-1) returns), or GetBool (true if O is its own image, as IsMinimalImage (2.2-1) returns, which is often much faster than computing the image).

stabilizer

The group Stabilizer(G,O,A), or a subgroup of this group; see Stabilizer (Reference: Stabilizer). If this group is large, it is more efficient to pre-calculate it. Default behaviour is to calculate the group, pass Group(()) to disable this behaviour. The generators of the given group are checked to stabilize O (which characterises being a subgroup of the stabilizer), and a group failing the check is rejected with an error, so accidentally reusing a stabilizer computed for a different object cannot silently produce wrong answers. The "vole" engine computes its own stabilizer and ignores this option.

When canonicalising transformations, permutations, partial permutations or digraphs, the default stabilizer is computed with the ferret package when it is loaded, which is much faster for groups of large degree; without ferret a slower fallback is used. For permutations the default is the centralizer, and for digraphs under the full symmetric group on their vertices it is the automorphism group of the digraph. For the minimum orderings (which MinimalImage (2.2-1) and its variants use), an object whose orbit under G is small is answered by enumerating the orbit directly, and then no stabilizer is needed at all.

This option is honoured for sets, transformations, permutations, partial permutations and digraphs. It is silently ignored for OnTuples, OnTuplesSets, points and fundamental structures, and for OnSetsSets only the trivial group is accepted.

Beware of passing Group(()) together with one of the dynamic orderings when the true stabilizer of O is very large: the search then rediscovers the stabilizer piecemeal, and can take many seconds on instances the default settings solve instantly. The same applies to disableStabilizerCheck.

Passing a stabilizer can also change which representative a non-minimum ordering selects. MinimalImage (2.2-1) and its variants are unaffected -- the minimum of an orbit is the minimum of that orbit whatever the search was told -- but the dynamic orderings prune and rank using the stabilizer, so CanonicalImage (2.2-5) may return a different (equally valid) representative when a stabilizer is supplied than when it is computed. The same holds for the other options which change how the stabilizer is obtained or used, namely disableStabilizerCheck and bruteForce. (getStab is not among them: it only reports the stabilizer the computation arrived at anyway, and never changes the computation.) Each fixed choice of settings still gives a canonical form -- the answer is constant on the orbit -- so what matters is to use one setting throughout a computation, and not to compare canonical images produced under different ones. No attempt is made here to say which orderings are sensitive to this and which are not.

disableStabilizerCheck (default false)

By default, during search we perform cheap checks to try to find extra elements of the stabilizer. Pass true to disable this check, this will make the algorithm MUCH slower if the stabilizer argument is a subgroup.

getStab (default false)

Store the stabilizer calculated during the search in the stab component of the configuration record that was passed in. With the "vole" engine this is Stabilizer(G,O,A); with the native engine it is a subgroup stabilizing the returned image, and may be a proper subgroup. It is honoured on the same paths as stabilizer.

This reports a stabilizer only when a search was run to obtain one. A transformation, permutation, partial permutation or digraph whose orbit is short is answered by the enumeration pre-pass described under bruteForce below, which walks the orbit and computes no stabilizer at all; such a call deposits fail in stab. Pass bruteForce := false alongside getStab to insist on the search, and so on a stabilizer, at the price of the search's cost on an object the enumeration answers in microseconds. Test the component rather than assuming a group.

bruteForce (default "auto")

Whether to try the orbit-enumeration pre-pass described under stabilizer above, which answers an object whose orbit under G is small without any stabilizer chain at all. The pre-pass applies to transformations, permutations, partial permutations and digraphs; on every other path this option has no effect.

Under the default "auto" the pre-pass enumerates up to a work budget balancing the measured cost of enumeration against the measured cost of the search, computed from the degree, the number of generators and the size of the encoded object, and gives up and runs the search when the orbit does not close within it. The budget consults nothing but those constants, so it does not depend on session state (in particular, whether a stabilizer chain for G has already been computed changes nothing). Passing false always runs the search. Passing true removes the budget: the orbit is enumerated however large it turns out to be, so pass it only when you know the orbit is small. The budget is a heuristic and is sometimes wrong in both directions, which is what these two overrides are for.

For the minimum orderings all three settings compute the same answer, because the pre-pass minimises exactly the order the search minimises; they differ only in how long they take. Note that IsMinimalImage (2.2-1) stops the enumeration at the first image smaller than O, so it can answer false even for orbits which would run past the budget.

Under a non-minimum ordering the pre-pass returns the minimum of the orbit, which is constant on the orbit and so is a canonical form, but is not the representative the search would have selected. Both are valid; they are different. This is the same settings-dependence described under stabilizer above, and the same rule applies: use one setting throughout. Whether the pre-pass runs at all is decided from the orbit alone, so it cannot split a single orbit between the two.

search (default "bfs")

Which search strategy the native engine uses. The default "bfs" is the frontier search: it stores every partial image achieving the minimal prefix, which can exhaust memory on highly symmetric inputs (a cyclic group's multiplication table of order 12 exceeds 8GB). Passing "iterative" stores none of them, re-enumerating the realisations of the fixed prefix at every level: bounded memory, at the price of re-enumeration time. Passing "hybrid" runs the frontier search while each stored level fits under frontierLimit nodes, and switches to re-enumeration from the last stored frontier only when a level would exceed the cap, so it matches the default search's speed when memory suffices and degrades gracefully instead of running out of memory. All three produce identical results.

"iterative" and "hybrid" are experimental. They support only the minimum ordering on unblocked domains (which excludes sets of sets); any other ordering is rejected with an error.

frontierLimit (default chosen from the input)

The cap on the nodes stored per level by search := "hybrid"; the other searches ignore it. When it is not given, the cap is Maximum(1000, QuoInt(50000000, m)) nodes for an object encoded on m points, which roughly bounds the stored list entries rather than the node count. After a hybrid run the global _IMAGES_HYBRID_STATS holds the widest frontier actually stored and the level at which the search switched to re-enumeration (fail if it never did), which is the information needed to tune the cap.

engine (default "native")

Which algorithm to use to compute the canonical image. The default "native" uses this package's own algorithm. Passing "vole" instead computes the canonical image using the vole package (via VoleFind.Canonical), which supports the same actions except for fundamental structures (Chapter 3). vole must already be loaded; an error is raised if it is requested but not available. Note that vole produces a different (but equally valid) canonical representative, so the two engines must not be mixed for a given computation. The "vole" engine only applies to CanonicalImage (2.2-5); it cannot compute minimal images and will raise an error if requested to.

generated by GAPDoc2HTML