This chapter details the Fundamental and Combinatorial records, which are used for creating and manipulating structured data representations within GAP. It also covers functions for converting these structures into graphs and for computing their stabilizers and canonical forms.
Fundamental structures can be passed directly to CanonicalImage (2.2-5), CanonicalImagePerm (2.2-5) and IsCanonicalImage (2.2-5), with the action OnFundamental (which is also the default action for them). Note: unless the group is a direct product of natural symmetric groups (such as the full symmetric group on the atoms), canonicalising a fundamental structure requires the optional vole package to be loaded. The graph computations in this chapter use bliss, through the required Digraphs package.
As a first example we canonicalise Latin squares, considering two squares equivalent (isotopic) if one can be reached from the other by permuting rows, permuting columns, and renaming symbols. We represent a square as a 2D matrix whose row and column indices are drawn from points disjoint from the symbols, and attach a colouring so rows, columns and symbols cannot be exchanged with each other.
gap> LoadPackage("images", false); true gap> n := 4;; gap> row := [n+1..2*n];; col := [2*n+1..3*n];; gap> enc := m -> Combinatorial.WithColoring( > Combinatorial.Matrix2D(m, row, col), [[1..n], row, col]);; gap> klein := [[1,2,3,4],[2,1,4,3],[3,4,1,2],[4,3,2,1]];;
Now any group acting on the points [1..3*n] can be used to canonicalise; permutations which mix the colour classes are excluded by the colouring. The canonical image is the same whichever equivalent square we start from: here we scramble the Klein table by swapping two symbols, two rows and two columns. The order 4 Latin squares fall into exactly two isotopy classes, represented by the Klein and cyclic group tables, and the canonical images separate them.
gap> klein2 := [[3,1,2,4],[1,3,4,2],[2,4,3,1],[4,2,1,3]];; gap> z4 := [[1,2,3,4],[2,3,4,1],[3,4,1,2],[4,1,2,3]];; gap> can1 := CanonicalImage(SymmetricGroup(3*n), enc(klein), OnFundamental);; gap> can2 := CanonicalImage(SymmetricGroup(3*n), enc(klein2), OnFundamental);; gap> can3 := CanonicalImage(SymmetricGroup(3*n), enc(z4), OnFundamental);; gap> can1 = can2; true gap> can1 = can3; false
As a second example, the multiplication table of a semigroup of order \(n\) can be canonicalised up to isomorphism as a 2D matrix on which SymmetricGroup(n) acts simultaneously on values, rows and columns.
gap> mat := [[1,2,3,4],[1,4,3,2],[1,2,4,3],[4,2,1,3]];; gap> fullm := Combinatorial.Matrix2D(mat, [1..4], [1..4]);; gap> CanonicalImagePerm(SymmetricGroup(4), fullm); (1,4,3,2)
A pair of such tables can be treated as an ordered pair with Combinatorial.Tuple, or as an unordered pair with Combinatorial.Multiset.
‣ Fundamental | ( global variable ) |
The Fundamental record provides the basic building blocks for representing structured data. These structures are records typically containing kind, contents, and type fields. It also defines constants for different kinds of structures.
The following components are available in the Fundamental record:
AtomOf( a )Returns a new fundamental structure representing an Atom with value a.
AtomOfWithType( a, t )Returns a new fundamental structure representing an Atom with value a and type t.
CollectionOf( l )Returns a new fundamental structure representing the collection containing the list l.
CollectionOfWithType( l, t )Returns a new fundamental structure representing the collection containing the list l, of type t.
TupleOf( l )Returns a new fundamental structure representing the tuple containing the list l..
TupleOfWithType( l, t )Returns a new fundamental structure representing the tuple containing the list l, of type t.
The record also contains the constants AtomType, CollectionType and TupleType, the possible values of the kind field of a fundamental structure.
The Fundamental record provides the basic building blocks such as atoms, collections, and tuples. Building upon these, the Combinatorial record offers convenient constructors for common mathematical objects.
‣ Combinatorial | ( global variable ) |
The Combinatorial record provides a collection of functions to construct various standard combinatorial objects. These objects are built using the underlying structures defined in Fundamental (3.2-1).
The following components are available in the Combinatorial record:
Atom( a )Returns a fundamental atom structure representing a. This is equivalent to calling Fundamental.AtomOfWithType( a, "atom" ).
Set( l )Returns a fundamental collection structure representing a set from the list l. The elements in l are typically fundamental structures themselves. This is equivalent to calling Fundamental.CollectionOfWithType( l, "set" ).
Multiset( l )Returns a fundamental collection structure representing a multiset from the list l. This is equivalent to calling Fundamental.CollectionOfWithType( l, "multiset" ).
Tuple( l )Returns a fundamental tuple structure from the list l. This is equivalent to calling Fundamental.TupleOfWithType( l, "tuple" ).
Matrix( vals, index )Constructs a 1D matrix representation. vals is a list of values and index is a list of corresponding indices. The function asserts that vals and index have the same length. The matrix is represented as a fundamental collection of type "matrix1dtop", where each element is a fundamental tuple of type "matrix1d" containing a pair [val, idx].
Matrix2D( vals, index1, index2 )Constructs a 2D matrix representation. vals is a 2D list (list of lists) of values, index1 is a list of row indices, and index2 is a list of column indices. The function asserts that the dimensions match. The matrix is represented as a fundamental collection of type "matrix2dtop", where each element is a fundamental tuple of type "matrix2d" containing a triplet [val, idx1, idx2].
Permutation( p )Converts a GAP permutation p into a fundamental structure. It lists the moved points of p as pairs [point, point^p]. Each such pair is converted into a fundamental tuple of atoms. These tuples are then collected into a fundamental collection of type "permutation".
Transformation( p )Converts a GAP transformation p into a fundamental structure. Similar to Permutation, it uses moved points [point, point^p] and forms a fundamental collection of type "transformation".
PartialPermutation( p )Converts a GAP partial permutation p into a fundamental structure. Similar to Permutation, it uses moved points [point, point^p] and forms a fundamental collection of type "partialpermutation".
OrderedPartition( p )Converts a list of lists p into a fundamental tuple of collections of type "orderedpartition": the order of the parts matters, the order within each part does not.
WithColoring( f, cols )Attaches a colouring to the fundamental structure f: cols is a list of lists of points, and two points may only be mapped to each other if they lie in the same list. This is the way to restrict which relabellings of f are considered.
The following functions operate on these fundamental structures:
‣ OnFundamental( f, p ) | ( function ) |
Applies a permutation p to a fundamental structure f or to an integer.
If f is an integer, it returns the image of f under p (i.e., f^p).
If f is a fundamental structure (a record with kind, contents, and type fields):
If f.kind is Fundamental.AtomType, it applies p to f.contents.
If f.kind is Fundamental.CollectionType, it recursively calls OnFundamental on each element of f.contents with p, and the resulting list of contents is sorted.
If f.kind is Fundamental.TupleType, it recursively calls OnFundamental on each element of f.contents with p. The order of elements in the tuple is preserved.
A new fundamental structure is returned with the modified contents, while the kind and type fields are preserved from the original structure f. An error is raised if f has an invalid kind.
The action is also installed as the power operation, so f^p may be used instead.
This function describes how permutations act on fundamental structures.
‣ AtomsOfFundamentalStructure( f ) | ( function ) |
Returns the set of all atoms (the underlying points) occurring anywhere in the fundamental structure f.
‣ GraphOfFundamentalStructure( s, omega, parts ) | ( function ) |
Constructs a graph representation of a fundamental structure s.
s is the fundamental structure to be converted into a graph. omega is a list of atomic elements (often integers) that form the base points of the graph. These are typically the objects upon which permutations will act. parts is a list of lists, representing a partition of omega. This partition is used to assign initial colors to the vertices corresponding to elements of omega. For an element j in parts[i], its corresponding vertex is colored with [Fundamental.PAtom, i]. Elements of omega not in any list in parts are colored with Fundamental.PAtom.
The function returns a record, let's call it graph, with the following components:
verticesA list of records, where each record represents a vertex in the graph. Each vertex record has at least name, colour, height, and id fields.
edgesA list of pairs [u, v], where u and v are IDs of vertices, representing directed edges from u to v.
omegaThe length of the input list omega.
atomsA hash map where keys are the elements from omega and values are the IDs of their corresponding vertices in graph.vertices.
The graph construction recursively traverses the fundamental structure s, creating vertices for atoms, collections, and tuples, and connecting them appropriately. Optimizations (_IMAGES_DO_ATOM_OPT, _IMAGES_DO_TUPLE_OPT) might affect the exact structure for performance.
This function explains the conversion of a fundamental structure into a graph representation, which is essential for the subsequent algorithms. The stabilizer of these structures can be computed, either over the full symmetric group or within a user-specified group:
‣ StabilizerOfFundamentalStructure( fs, omega[, parts] ) | ( function ) |
Computes the stabilizer group of the fundamental structure fs with respect to a set of base points omega.
fs is the fundamental structure. omega is a list of atomic elements, representing the set of points on which the resulting group will act. parts (optional) is a partition of omega, used for coloring the graph derived from fs. If not provided, an empty partition [] is used.
The function first converts the fundamental structure fs into a digraph using _convertToDigraph (which internally calls GraphOfFundamentalStructure (3.2-5)). This digraph also has an associated vertex coloring based on parts and the types of internal nodes. Then, it computes the automorphism group of this colored digraph using BlissAutomorphismGroup from the Digraphs package. Finally, the resulting automorphism group is returned as a permutation group acting on the points in omega.
‣ StabilizerOfFundamentalStructureWithGroup( fs, omega, grp ) | ( function ) |
Computes the stabilizer of the fundamental structure fs within a given permutation group grp. This function requires the vole package to be loaded.
fs is the fundamental structure. omega is a list of atomic elements, which must contain every atom of fs and every point moved by grp. grp is a permutation group acting on the points in omega. The search for stabilizing permutations is restricted to grp.
The function converts fs into a colored digraph (using _convertToDigraph with omega as a single part for coloring). It then constructs a candidate group for VoleFind.Group by combining grp (acting on omega vertices) with the symmetric group on the remaining non-omega vertices of the graph. VoleFind.Group is used to find the subgroup of this candidate group that stabilizes the digraph and its coloring. The resulting group is then restricted to act only on the vertices corresponding to omega and is returned.
Similarly, canonical permutations can be found:
‣ CanonicalPermOfFundamentalStructure( fs, omega ) | ( function ) |
Computes a canonicalizing permutation for the fundamental structure fs with respect to omega. This function assumes the full symmetric group is acting on omega.
fs is the fundamental structure. omega is a list of atomic elements.
This function is a convenience wrapper that calls CanonicalPermOfFundamentalStructureWithGroup (3.2-9) with fs, omega, and SymmetricGroup(omega). It requires the vole package to be loaded. It returns a permutation acting on omega that maps fs to its canonical form.
‣ CanonicalPermOfFundamentalStructureWithGroup( fs, omega, grp ) | ( function ) |
Computes a canonicalizing permutation for the fundamental structure fs with respect to omega, restricting the search to the group grp. This function requires the vole package to be loaded.
fs is the fundamental structure. omega is a list of atomic elements, which must contain every atom of fs and every point moved by grp. grp is a permutation group acting on the points in omega.
Similar to StabilizerOfFundamentalStructureWithGroup (3.2-7), this function converts fs to a colored digraph. It forms a candidate group by combining grp (acting on omega vertices) with the symmetric group on non-omega vertices. VoleFind.CanonicalPerm is then used to find a permutation from this candidate group that maps the digraph (and its coloring) to a canonical form. The resulting permutation is restricted to act on omega and is returned. This permutation, when applied to omega and used to relabel fs, would yield a canonical representation of fs under the action of grp.
Finally, a utility function for refining canonical labellings with respect to colorings is provided:
‣ MakeCanonicalLabellingRespectColors( n, p, colours ) | ( function ) |
Adjusts a permutation p (acting on [1..n]) to create a new permutation that respects a given coloring. The intent is to refine a canonical labeling p such that elements within the same color class are ordered canonically based on their preimages under p.
n is the number of points being permuted; it is raised internally if p or colours mention larger points, and points of [1..n] not in any colour class are treated as one extra class. p is the input permutation, typically a canonical labeling permutation obtained from a graph algorithm. colours is a list of lists, where each inner list colours[i] contains points belonging to the i-th color class. These inner lists are treated as sets.
The function works as follows:
It first determines the color class for each point j in [1..n].
It computes the inverse of p, let this be p_inv. The list ListPerm(p_inv, n) gives the order in which points val appear if we iterate i from 1 to n and take val = i^(p_inv).
It then constructs a new permutation. For each i from 1 to n, it considers the point val = i^(p_inv). This point val belongs to some color class, say col_val.
The point val is mapped by the new permutation to the next available (i.e., smallest unassigned) point within its own color class colours[col_val], according to the ordering defined by iterating through i.
The effect is that the output permutation, when applied, will order the points such that all points of the first color class come first (ordered among themselves by their p_inv values), then all points of the second color class (similarly ordered), and so on.
generated by GAPDoc2HTML