Search Reduction 1

Search Reduction 1

This is the third in a series of articles exploring backtracking search. Be sure to read the earlier two articles in this series first! Our aim is to build an efficient algorithm for performing intersection of permutation groups:

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) ])

Last time, we reached the point where we have to answer the following question: Given two groups \(G\) and \(H\), is there any permutation \(p \in G \cap H\) where \(1^p = i\). To help us with this, we need another use of the Stabilizer Chains.

Representative Action

Consider the following problem:

Representative Action

Given a permutation group \(G\) and two lists of integers \(X = [x_1,\ldots,x_n]\) and \(Y = [y_1,\ldots,y_n]\), find a permutation \(p \in G\) such that \(x_i^p = y_i\) for all \(i\) (or prove none exists).

This function can be answered using stabilizer chains, and in GAP is implemented with the function RepresentativeAction. Here are some examples.

RepresentativeAction(G, [1], [3], OnTuples);
# (1,3,2)
RepresentativeAction(G, [1,2], [2,3], OnTuples);
# (1,2,3)
RepresentativeAction(H, [1,2], [2,3], OnTuples);
# (1,2,3,4,6,5)
RepresentativeAction(G, [1], [2], OnTuples);
# (1,2)
RepresentativeAction(H, [1], [2], OnTuples);
# (1,2)(3,4)(5,6)
gap> RepresentativeAction(G, [1,2], [2,6], OnTuples);
# fail
gap> RepresentativeAction(H, [1,2], [2,6], OnTuples);
# (1,2,6,5,3,4)

What can we tell from these examples? As \(G\) does not contain a permutation which maps \([1,2]\) to \([2,6]\), then \(G \cap H\) certainly cannot contain such a permutation.

Does \(G \cap H\) contain a permutation which maps \([1]\) to \([2]\)? We don’t know yet. Just because \(G\) and \(G\) both contain such permutations, doesn’t mean that they share any permutations which map \([1]\) to \([2]\).

This is always going to be a pattern we will see again and again – we will try to prove if some problem has an answer or not, and answer yes, no, or don’t know.

So, how can be find the elements of \(G \cap H\) where \(1^p=2\)? More splitting! If \(G \cap H\) contains a permutation such that \(1^p = 2\), then we can consider where that permutation maps \(2\), splitting our search into another \(n-1\) pieces.

  • Find \(p \in G \cap H\) where \(1^p = 2\), \(2^p = 1\).
  • Find \(p \in G \cap H\) where \(1^p = 2\), \(2^p = 3\).
  • Find \(p \in G \cap H\) where \(1^p = 2\), \(2^p = 4\).
  • …
  • Find \(p \in G \cap H\) where \(1^p = 2\), \(2^p = n-1\).

There are \(n-1\) pieces, because there can’t be a permutation \(p\) where \(1^p=2\) and \(2^p=2\)!

So, what do we find here? It turns out \(G\) maps \([1,2]\) to \([2,1]\) and \([2,3]\), while \(H\) maps \([1,2]\) to \([2,1]\), \([2,3]\) and \([2,6]\). Therefore, any element of \(G \cap H\) which maps \(1\) to \(2\) must map \([1,2]\) to \([2,1]\).

So, let’s carry on, what about mapping \([1,2,3]\) to \([2,1,x]\) for different values of \(x\)? It turns out \(G\) only maps to \([2,1,3]\), while \(H\) maps to \([2,1,4]\) and \([2,1,5]\). So, this tells us there is no element of \(G \cap H\) which maps \(1\) to \(2\)!

Let’s try writing a GAP function to encapsulate this. This function is fairly long, but we will work our way through it.

Aside - Info

The Info function lets us print information about what our algorithm is doing. The function takes a name for the type of info (we will use InfoGroup, which is for group algorithms), the importance of information (lower numbers are more important), and then the information to print.

To see the messages, run SetInfoLevel(InfoGroup, 1);, which will print all messages of level 1 or smaller.

Algorithm

We will now write a function FindExtendingElement, which will, given an array \(X = [x_1,\dots,x_n]\) and a list of GroupCheckers, will see if there is any element of $

## Given two groups G and H and an array Array,
## find a permutation p in G and H such that i^p = Array[i]
## for all i in [1..Length(Array)],
## Where G and H are subgroups of SymmetricGroup(maxpnt).
## Returns p, or fail if no such permutation exists
FindExtendingElementGH := function(G, H, maxpnt, Array)
  local pg, ph, retperm, n, i, newarray;

  n := Length(Array);

  # First we look for permutations which map [1..n] to Array
  # if any return fail, then return fail
  if RepresentativeAction(G, [1..n], Array, OnTuples) = fail then
      Info(InfoGroup, 3, "FEE: No permutation in G for ", Array);
      return fail;
  fi;

  if RepresentativeAction(H, [1..n], Array, OnTuples) = fail then
      Info(InfoGroup, 3, "FEE: No permutation in H for ", Array);
      return fail;
  fi;

  # Check if we have assigned all points
  # PermList will turn a list into a GAP permutation
  if n = maxpnt then
    Info(InfoGroup, 3, "FEE: Found ", PermList(Array));
    return PermList(Array);
  fi;

  # In this case, we need to recursively search.
  # Let's try adding a new member to our array.
  # We don't bother skipping the case where we would
  # build non-permutations, they will just fail
  Info(InfoGroup, 3, "FEE: Extending ", Array, " with another point");
  for i in [1..maxpnt] do
    newarray := Concatenation(Array, [i]);
    retperm := FindExtendingElementGH(G, H, maxpnt, newarray);
    if retperm <> fail then
      return retperm;
    fi;
  od;
  return fail;
end;

Let’s try running our function:

SetInfoLevel(InfoGroup, 3);
FindExtendingElement([GroupChecker(G), GroupChecker(H)], 6, [3]);
#I  FEE: Extending [ 3 ] with another point
#I  FEE: No permutation in H for [ 3, 1 ]
#I  FEE: Extending [ 3, 2 ] with another point
#I  FEE: Extending [ 3, 2, 1 ] with another point
#I  FEE: No permutation in G for [ 3, 2, 1, 1 ]
#I  FEE: No permutation in G for [ 3, 2, 1, 2 ]
#I  FEE: No permutation in G for [ 3, 2, 1, 3 ]
#I  FEE: Extending [ 3, 2, 1, 4 ] with another point
#I  FEE: No permutation in G for [ 3, 2, 1, 4, 1 ]
#I  FEE: No permutation in G for [ 3, 2, 1, 4, 2 ]
#I  FEE: No permutation in G for [ 3, 2, 1, 4, 3 ]
#I  FEE: No permutation in G for [ 3, 2, 1, 4, 4 ]
#I  FEE: Extending [ 3, 2, 1, 4, 5 ] with another point
#I  FEE: No permutation in G for [ 3, 2, 1, 4, 5, 1 ]
#I  FEE: No permutation in G for [ 3, 2, 1, 4, 5, 2 ]
#I  FEE: No permutation in G for [ 3, 2, 1, 4, 5, 3 ]
#I  FEE: No permutation in G for [ 3, 2, 1, 4, 5, 4 ]
#I  FEE: No permutation in G for [ 3, 2, 1, 4, 5, 5 ]
#I  FEE: Found (1,3)
(1,3)

Aside - LargestMovedPoint

We assume our permutation groups are acting on a finite set \(\{1 \ldots n\}\). But, how do we find \(n\)? GAP does not store this value – it acts as if all groups act on \(\mathbb{N}\), the set of all natural numbers. We could pass \(n\) around in all our functions, but instead we use the function LargestMovedPoint(G). This function gives us the largest integer \(n\) which is moved by any member of \(G\), we can ignore any larger points when doing intersections.

# Find the intersection of two permutation groups G and H on [1..n],
# assuming that G and H both fix [1..pnt]
# (pnt might be 0, then G and H may fix nothing)
BasicIntersectionLoop := function(G, H, n, pnt)
  local loopgroup, loopG, loopH, i, cosetreps, rep;

  # Base case: If either G or H is the identity group, the
  # intersection is the identity group! Return list of
  # generators
  if G = Group(()) or H = Group(()) then
    Info(InfoGroup, 1, "Reached base case");
    return [()];
  fi;

  # Perform a recursive call for intersection of point
  # stabilizer of pnt + 1
  loopG := Stabilizer(G, pnt + 1);
  loopH := Stabilizer(H, pnt + 1);
  loopgroup := BasicIntersectionLoop(loopG, loopH, n, pnt + 1);

  # Now look for coset representatives
  cosetreps := [];
  for i in [pnt + 2..n] do
    rep := FindExtendingElementGH(G,H, n,
                                Concatenation([1..pnt], [i]));
    if rep <> fail then
      Add(cosetreps, rep);
    fi;
  od;

  return Concatenation(loopgroup, cosetreps);
end;

# This just sets up our recursive loop, finding the set which G
# and H act on (using LargestMovedPoint)
BasicIntersection := function(G, H)
  local lmp;
  lmp := Minimum(LargestMovedPoint(G), LargestMovedPoint(H));
  return Group(BasicIntersectionLoop(G, H, lmp, 0));
end;

Now we have a basic intersection algorithm, which produces a set of generators! How can we improve this search? There are several ways. We will begin by heading off in a totally different direction, into graph isomorphism.