Search Reduction 2

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

We can prove some parts of our search don’t have to be performed. Early in search we find the permutation \((4,5) \in G \cap H\). Later, we try finding a permutation where \(1^p = 4\). There is no need after this to search for a permutation 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 permutations together, to get \((1,5,3,4)(2,6)\).

** If we had found no permutation where \(1^p = 4\) in \(G \cap H\), there is no point searching for one where \(1^p=5\), as if we found such a permutation, we could again multiply it by \((4,5)\) and get a permutation where \(1^p = 4\), which can’t exist!

How can we formalise this idea? 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 discussion of this algorithm will appear in a future post!

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 searches in general) is performed.

Looking at the output of FindExtendingElement, there are a number of easy ways it can be improved. We certainly shouldn’t test mappings like [ 3, 2, 1, 1 ], as permutations are invertible!

More generally, let us consider the second stage of our search, when we are looking for \(G_1 \cap H_1\). We can ask GAP to give us 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, we can deduce the orbit of \(2\) in \(G_1 \cap H_1\) must be contained in \(\{2,3\} \cap \{2,4,5\}\), which means that actually 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\}\). Of course, this does not mean that \(G_1 \cap H_1\) contains a permutation \(p\) where \(4^p = 5\), this orbit may still split. However, this is the only case which we need to consider. We have reduced our search for \(G_1 \cap H_1\) to having to consider a single permutation: \((4,5)\)!