Making it Fast

We now have a basic intersection algorithm. How can we make it faster? There are two broad families of improvements: making use of permutations in \(G \cap H\) we have already found, and proving that parts of the search contain no element of \(G \cap H\).

Making use of partial knowledge of \(G \cap H\)

Some parts of our search are redundant and can be pruned. Early in search we find the permutation \((4,5) \in G \cap H\). Later, we try to find a permutation where \(1^p = 4\). After this, there is no need to search for one where \(1^p = 5\). Why? There are two cases.

  • There is a permutation where \(1^p = 4\) (in this problem there is: \((1,4)(2,6)(3,5) \in G \cap H\)). We can find a permutation where \(1^p = 5\) by multiplying these two together, getting \((1,5,3,4)(2,6)\).

  • If there were no permutation where \(1^p = 4\) in \(G \cap H\), there is no point searching for one where \(1^p = 5\) either, because if one existed, we could multiply it by \((4,5)\) to get a permutation where \(1^p = 4\), which cannot exist.

How do we formalise this? As we find members of \(G \cap H\), we keep track of the orbits of \(G \cap H\) and only check one value in each orbit. An exact treatment will appear in a later chapter.

Proving parts of search contain no element of \(G \cap H\)

This is where the majority of the research into improving backtrack search in permutation groups (and backtrack search in general) has gone.

Looking at the output of FindExtendingElementGH, there are obvious ways to improve it. We certainly shouldn’t test mappings like [3, 2, 1, 1], as permutations are invertible.

More generally, consider the second stage of our search, when we are looking for \(G_1 \cap H_1\). We can ask GAP for the orbits of \(G_1\) and \(H_1\):

Orbits(Stabilizer(G, 1));
# [ [ 2, 3 ], [ 4, 5, 6 ] ]
Orbits(Stabilizer(H, 1));
# [ [ 2, 4, 5 ], [ 3, 6 ] ]

From this, the orbit of \(2\) in \(G_1 \cap H_1\) must be contained in \(\{2,3\} \cap \{2,4,5\}\), which means the orbit of \(2\) is just \(\{2\}\).

By the same reasoning, both \(3\) and \(6\) are fixed, leaving the only non-trivial orbit as \(\{4,5\}\). This does not mean that \(G_1 \cap H_1\) contains a permutation \(p\) where \(4^p = 5\); the orbit may still split. However, this is the only case we need to consider. We have reduced our search for \(G_1 \cap H_1\) to a single permutation: \((4,5)\).