Automorphism groups and canonical labels¶

For details see section 3 of [Feu2013].

Definitions¶

Let \(G\) be a group which acts on a finite set \(X\) and let \(\mathcal{L}(G)\) denote the set of subgroups of \(G\). We say that a mapping \(Can_G: X \rightarrow X \times G \times \mathcal{L}(G), x \mapsto \left( CF_G(x), T_G(x), G_x \right)\) with

\(CF_G(gx) = CF_G(x)\) for all \(x \in X\) and all \(g\in G\) (canonical form)

\(CF_G(x) = T_G(x) x\) for all \(x \in X\) (transporter element)

\(G_x = \{g \in G \mid gx=x\}\) (stabilizer)

is a canonization algorithm.

Let \(H\) be another group acting on a set \(Y\). A pair \((\theta, \omega)\) with a homomorphism \(\theta: G \rightarrow H\) and \(\omega: X \rightarrow Y\) is called a homomorphism of group actions if \(\omega(gx) = \theta(g)\omega(x)\) for all \(g \in G\), for all \(x \in X\). In the case that \(G=H\) and \(\theta = id_G\), we call \(\omega\) a \(G\)-homomorphism.

A standard partition is a sequence \(C = (C_1, ..., C_k)\) of subsets of \([n] = \{0, \ldots, n-1\}\) where the \(C_i\) are disjoint, consecutive intervals and their union is equal to \([n]\). Each element is called a cell and the elements lying in a cell of cardinality 1 are called fixed points. Let \(I_C\) be a sequence of all fixed points of \(C\) (the exact ordering is important, but will be determined by the algorithm). The stabilizer of \((S_n)_C\) is a standard Young subgroup of \(S_n\).

Requirements¶

In the following we want to present an efficient algorithm for the canonization problem in the case that the group action is of type \(G \rtimes S_n\) on \(X^n\). For this goal, we suppose that the group action of \(G = G \rtimes \{id\}\) on \(X^n\) has the following properties:

– The action of \(G \rtimes \{id\}\) on \(X^n\) is given by a direct product of
(maybe different) group actions of \(G\) on \(X\).

—For every \(i \in \{0, \ldots, n-1\}\) let \(\Pi^{(i)}: X^n \rightarrow X\) be the projection to the \(i\)-th coordinate. The function \(\Pi^{(i)}\) is an invariant under the action of the subgroup \((S_n)_i = \{\pi \in S_n \mid \pi(i) = i\}\).

Let \((i_0, \ldots, i_{k-1}) = I \subseteq \{0, \ldots, n-1\}\) be an injective sequence. We define \(\Pi^{(I)}(x) := (\Pi^{(i_0)}(x), \ldots, \Pi^{(i_{k-1})}(x))\). We call an element \(x \in X\) \(I\)-semicanonical if and only if \(\Pi^{(I)}(x) \leq \Pi^{(I)}(gx)\) for all \(g \in G\).

For each \(x \in X^n\) there is obviously an \(I\)-semicanonical element in the orbit \(Gx\). Suppose that \(x\) is already \(I\)-semicanonical and \(J\) is an injective sequence which extends \(I\) by one further coordinate \(i\), then we call the process of computing a \(J\)-semicanonical representative the inner minimization at position \(i\).

This could be described by a group action of the stabilizer \(G_{\Pi^{(I)}(x)}\). on \(x_i\).

Partitions and refinements¶

Now the idea for the canonization algorithm for the action of \(G \rtimes S_n\) on \(X^n\) can be formulated as follows. Let us suppose that we want to canonize \(x \in X^n\). We build a backtrack tree in the following manner:

each node gets represented by a quadruple \((C, I_C, y, G_{\Pi^{(I_C)}(y))})\) where \(C\) is an ordered partition, \(I_C\) a subsequence of its fixed points, \(y \in X^n\) is \(I_C\)-semicanonical and \(G_{\Pi^{(I_C)}(y))}\) is the remaining group of the inner action
the root node is on level \(0\) and gets represented by \((([n]), (), x, G)\)
nodes with \(| I_C | = n\), i.e. all coordinates are fixed, will be leafs and we have \(G_{\Pi^{(I_C)}(y))} = G_y\)
the children of some other node \((C, I_C, y, G_{\Pi^{(I_C)}(y))})\) are constructed by
- picking one cell \(C_j\) with \(| C_j |\) (the choice has to be invariant in some sense)
- separating the point \(\min(C_j)\) from its cell \(C_j\) which leads to the partition \(D\) and the sequence \(I_D\)
- building the \(| C_j |\) successors \((D, I_D, z_k, G_{\Pi^{(I_D)}(z_k))})\) by applying the permutation \(\sigma_k := (\min(C_j), k)\) for all \(k \in C_j\) to \(y\) and computing an \(I_D\)-semicanonical representative \(z_k\) of \(\sigma_k y\)
if the projection \(\Pi^{(I_D)}(z_k)\) is not optimal then we stop the backtracking in this node (i.e. prune the subtree below this node)
the tree is traversed in a depth-first manner
the smallest reached leaf node is defined to be the canonical form (the defined ordering takes all comparisons in predecessors also into account)
equal leaf nodes correspond to automorphism of \(x\), they could be used to define further pruning methods.

We are able to speed up the computation by making use of refinements (i.e. \((S_n)_C\)-homomorphisms). Suppose we constructed a node \((C, I_C, y, G_{\Pi^{(I_C)}(y))})\). We define \(Y := \{z \in X^n \mid \Pi^{(I_C)}(z) = \Pi^{(I_C)}(y)\}\) and we search for functions \(\omega: Y \rightarrow \ZZ^n\) which are constant on the orbits of \(G_{\Pi^{(I_C)}(y)}\) and compatible with the action of \((S_n)_C\) on both sides. Then we compute a permutation \(\pi \in (S_n)_C\) which cell-wisely sorts the entries of \(\omega(y)\). Afterwards we are allowed to reduce ourselves to the stabilizer \((S_n)_D\) of \(\omega(\pi y)\). If this stabilizer contains further fixed points, they are appended (in some fixed order) to the sequence \(I_C\) in order to define \(I_D\). Furthermore the element \(y\) gets updated by an \(I_D\)-semicanonical representative of this orbit. These refinements could also be applied iteratively.

As said before, the backtrack search tree is traversed in a depth-first search manner, hence we maintain a candidate for the result. Each newly constructed node is compared to this candidate. If it:

compares larger, then we can prune the subtree rooted in this node
compares smaller, then we replace the candidate by the actual node (more precisely by the next leaf node we will construct, for this we use the boolean flag _is_candidate_initialized)
compares equal we just continue.

Implementation Details¶

The class PartitionRefinement_generic provides a framework for such a backtracking. It maintains the partition \(C\) and the sequence \(I_C\). Instead of permuting the elements \(x \in X\) during the construction of nodes and in the refinements, we use a PartitionStack, see sage.groups.perm_gps.partn_ref.data_structures. Hence, \(C = (C_1, ..., C_k)\) and \(I_C\) will be maintained implicitly. If \(\pi \in S_n\) is the permutation applied to this node, then we will store \(\pi(I_C)\) and in the partition stack we will store \((\pi(C_1), ..., \pi(C_k))\).

The class further decides when we have to call the inner minimization and which subtrees could be pruned by the use of automorphisms, see LabelledBranching for more details.

Derived classes¶

Derived classes have to implement the following methods, see the method descriptions for more information:

Cython functions:
- bint _inner_min_(self, int pos, bint * inner_group_changed)
- bint _refine(self, bint * part_changed)
- tuple _store_state_(self)
- void _restore_state_(self, tuple act_state)
- void _store_best_(self)
- void _latex_act_node(self, str comment=None) (to use the implemented debugging method via printing the backtrack tree using latex)
- bint _minimization_allowed_on_col(self, int pos)
Python functions:
- get_canonical_form(self)
- get_transporter(self)
- get_autom_gens(self)

AUTHORS:

Thomas Feulner (2012-11-15): initial version

REFERENCES:

[Feu2013]

class sage.groups.perm_gps.partn_ref2.refinement_generic.LabelledBranching[source]¶

Bases: object

This class implements complete labelled branchings.

To each subgroup of \(S_n\) we can uniquely assign a directed forest on \(n\) vertices, where the edges \((i,j)\) fulfill \(i<j\) and some further conditions on the edge labels (which we do not want to state). This graph is called a complete labelled branching.

The edges \((i,j)\) will be stored in a vector father with father_j = -1 if \(j\) is a root of a tree, and father_j = i if \(i\) is the predecessor of \(j\), i.e. is an \((i,j)\) is an edge.

EXAMPLES:

Sage

sage: from sage.groups.perm_gps.partn_ref2.refinement_generic import LabelledBranching
sage: L = LabelledBranching(3)
sage: L.add_gen(libgap.eval('(1,2,3)'))
sage: L.get_order()
3
sage: L.small_generating_set()
[(1,2,3)]

Python

>>> from sage.all import *
>>> from sage.groups.perm_gps.partn_ref2.refinement_generic import LabelledBranching
>>> L = LabelledBranching(Integer(3))
>>> L.add_gen(libgap.eval('(1,2,3)'))
>>> L.get_order()
3
>>> L.small_generating_set()
[(1,2,3)]

add_gen(gen)[source]¶

Add a further generator to the group and update the complete labeled branching.

EXAMPLES:

Sage

sage: from sage.groups.perm_gps.partn_ref2.refinement_generic import LabelledBranching
sage: L = LabelledBranching(3)
sage: L.add_gen(libgap.eval('(1,2,3)'))

Python

>>> from sage.all import *
>>> from sage.groups.perm_gps.partn_ref2.refinement_generic import LabelledBranching
>>> L = LabelledBranching(Integer(3))
>>> L.add_gen(libgap.eval('(1,2,3)'))

get_order()[source]¶

Return the order of the group stored by self.

EXAMPLES:

Sage

sage: from sage.groups.perm_gps.partn_ref2.refinement_generic import LabelledBranching
sage: L = LabelledBranching(3)
sage: L.get_order()
1
sage: L.add_gen(libgap.eval('(1,2,3)'))
sage: L.get_order()
3

Python

>>> from sage.all import *
>>> from sage.groups.perm_gps.partn_ref2.refinement_generic import LabelledBranching
>>> L = LabelledBranching(Integer(3))
>>> L.get_order()
1
>>> L.add_gen(libgap.eval('(1,2,3)'))
>>> L.get_order()
3

small_generating_set()[source]¶

Return a small set of generators of the group stored by self.

EXAMPLES:

Sage

sage: from sage.groups.perm_gps.partn_ref2.refinement_generic import LabelledBranching
sage: L = LabelledBranching(3)
sage: L.small_generating_set()
[()]
sage: L.add_gen(libgap.eval('(1,2,3)'))
sage: L.small_generating_set()
[(1,2,3)]

Python

>>> from sage.all import *
>>> from sage.groups.perm_gps.partn_ref2.refinement_generic import LabelledBranching
>>> L = LabelledBranching(Integer(3))
>>> L.small_generating_set()
[()]
>>> L.add_gen(libgap.eval('(1,2,3)'))
>>> L.small_generating_set()
[(1,2,3)]

class sage.groups.perm_gps.partn_ref2.refinement_generic.PartitionRefinement_generic[source]¶

Bases: object

Implement the partition and refinement framework for group actions \(G \rtimes S_n\) on \(X^n\) as described in sage.groups.perm_gps.partn_ref2.refinement_generic.

get_autom_gens()[source]¶

Return a list of generators we have computed.

EXAMPLES:

Sage

sage: from sage.groups.perm_gps.partn_ref2.refinement_generic import PartitionRefinement_generic
sage: P = PartitionRefinement_generic(5)
sage: P.get_autom_gens()
Traceback (most recent call last):
...
NotImplementedError

Python

>>> from sage.all import *
>>> from sage.groups.perm_gps.partn_ref2.refinement_generic import PartitionRefinement_generic
>>> P = PartitionRefinement_generic(Integer(5))
>>> P.get_autom_gens()
Traceback (most recent call last):
...
NotImplementedError

get_autom_order_permutation()[source]¶

Return the order of the automorphism group we have computed.

EXAMPLES:

Sage

sage: from sage.groups.perm_gps.partn_ref2.refinement_generic import PartitionRefinement_generic
sage: P = PartitionRefinement_generic(5)
sage: P.get_autom_order_permutation()
1

Python

>>> from sage.all import *
>>> from sage.groups.perm_gps.partn_ref2.refinement_generic import PartitionRefinement_generic
>>> P = PartitionRefinement_generic(Integer(5))
>>> P.get_autom_order_permutation()
1

get_canonical_form()[source]¶

Return the canonical form we have computed.

EXAMPLES:

Sage

sage: from sage.groups.perm_gps.partn_ref2.refinement_generic import PartitionRefinement_generic
sage: P = PartitionRefinement_generic(5)
sage: P.get_canonical_form()
Traceback (most recent call last):
...
NotImplementedError

Python

>>> from sage.all import *
>>> from sage.groups.perm_gps.partn_ref2.refinement_generic import PartitionRefinement_generic
>>> P = PartitionRefinement_generic(Integer(5))
>>> P.get_canonical_form()
Traceback (most recent call last):
...
NotImplementedError

get_transporter()[source]¶

Return the transporter element we have computed.

EXAMPLES:

Sage

sage: from sage.groups.perm_gps.partn_ref2.refinement_generic import PartitionRefinement_generic
sage: P = PartitionRefinement_generic(5)
sage: P.get_transporter()
Traceback (most recent call last):
...
NotImplementedError

Python

>>> from sage.all import *
>>> from sage.groups.perm_gps.partn_ref2.refinement_generic import PartitionRefinement_generic
>>> P = PartitionRefinement_generic(Integer(5))
>>> P.get_transporter()
Traceback (most recent call last):
...
NotImplementedError