Intersection by Backtracking

We now return to the problem we set out to solve: intersecting two permutation groups \(G\) and \(H\). Both will be given as a set of generators. In GAP, the Group function constructs a group from a list of generators, and Intersection finds the intersection of two groups. Let’s see a short example.

G := Group((1,2,3), (1,2), (1,4)(2,5)(3,6));
H := Group((1,3,6), (3,6), (1,2)(3,4)(5,6));
R := Intersection(G,H);
# Group([ (4,5), (1,3)(4,5), (1,4,3,5)(2,6) ])
Group([ (1,2,3), (1,2), (1,4)(2,5)(3,6) ])
Group([ (1,3,6), (3,6), (1,2)(3,4)(5,6) ])
Group([ (4,5), (1,3)(4,5), (1,4,3,5)(2,6) ])
Note

We use lines starting with # to show GAP’s output.

So, how can we implement Intersection ourselves? You might hope the next step is a clever mathematical trick which finds the intersection quickly. Unfortunately, no such algorithm is known. The problem is wrapped up with other important open problems in computer science, such as whether graph isomorphism or NP-complete problems can be solved quickly. We are not going to get into that here.

However, just because we cannot produce an algorithm that’s always fast does not stop us producing something fast for as many groups as possible.

Let’s start with the simplest possible implementation: enumerate all permutations in \(G\), and check each one for membership in \(H\).

IntersectionEnumerate := function(G,H)
  local result, g;
  result := [];
  for g in G do
    if g in H then
      Add(result, g);
    fi;
  od;
  return Group(result);
end;

IntersectionEnumerate(G, H);
# Group([ (), (4,5), (1,3), (1,3)(4,5), (1,4)(2,6)(3,5),
#         (1,4,3,5)(2,6), (1,5,3,4)(2,6), (1,5)(2,6)(3,4) ])

One obvious problem: haven’t we just replaced one piece of GAP magic (Intersection) with two different pieces of GAP magic?

Both can be efficiently implemented using a base and strong generating set, also known as a stabiliser chain, which we saw in the previous chapter. For now, we will accept these operations as efficient primitives and build on top.

If your only interest is the worst-case complexity over all intersection problems, IntersectionEnumerate is surprisingly close to the state of the art. None of the algorithms we will discuss beat it by very much in a theoretical sense. However — as you might hope — we can outperform it in many practical cases.

The fundamental idea behind all our improvements is backtracking search, also known as divide-and-conquer. We split our problem into sub-problems which are (hopefully) easier to solve, then stitch the answers back together.

Basic backtracking

So, how can we split the search for Intersection(G,H)? One natural method is to search for subgroups and cosets contained inside the group we want. Let’s try that.

A brief aside: point stabiliser

The point stabiliser of an integer \(x\) in a permutation group \(G\) is the subgroup of \(G\) which fixes \(x\). This is often denoted \(G_x\). How can we find this subgroup in GAP? First, a slow function:

StabPointEnumerate := function(G,x)
  local result, g;
  result := [];
  for g in G do
    if x^g = x then
      Add(result, g);
    fi;
  od;
  return Group(result);
end;

StabPointEnumerate(G, 1);
# Group([ (), (5,6), (4,5,6), (4,5), (4,6,5), (4,6),
#          (2,3), (2,3)(5,6), (2,3)(4,5,6), (2,3)(4,5),
#          (2,3)(4,6,5), (2,3)(4,6) ])

Of course, we don’t want to do this in practice. Finding the point stabiliser is another thing we can calculate using stabiliser chains. In GAP:

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

Notice that Stabilizer produces a shorter answer than StabPointEnumerate. Both produce the same group, but Stabilizer returns a set of generators rather than every element.

Back to backtracking

We will split the problem of finding \(G \cap H\) into \(n\) pieces, where \(n\) is the largest moved point of either \(G\) or \(H\):

  • Find \(p \in G \cap H\) where \(1^p = 1\).
  • Find \(p \in G \cap H\) where \(1^p = 2\).
  • \(\ldots\)
  • Find \(p \in G \cap H\) where \(1^p = n\).

Consider the first of these sets. A permutation \(p\) where \(1^p = 1\) is in \(G \cap H\) if and only if it is in both \(G_1\) and \(H_1\). So we need Intersection(Stabilizer(G, 1), Stabilizer(H,1)). This is another intersection problem, but a smaller one, so will (hopefully) be easier to solve. Call this intersection \(R\).

Now we apply a little group theory. We know \(R \subseteq G \cap H\), so we can divide \(G \cap H\) into a list of cosets of \(R\). Let’s pick a single permutation in some coset of \(R\) — for example \(q = (1,3)(4,5)\), which we know is in \(G \cap H\) from our brute-force enumeration.

As all \(p \in R\) satisfy \(1^p = 1\), all permutations in the coset \(qR\) satisfy \(1^p = 3\). In general, each subproblem produces either:

  • A coset of \(R\), or
  • No permutations.

(A full proof is left to the interested reader.)

So we don’t need to find all solutions to each subproblem after the first — we only need to find one permutation from each (or prove no permutation exists). That already gives us a significant gain.

How can we quickly find which of these subsearches contains a permutation from \(G \cap H\)? That is the subject of a huge amount of research. The next chapter discusses some methods.