Search Reduction

Last chapter, we reached the following question: given two groups \(G\) and \(H\), is there any permutation \(p \in G \cap H\) where \(1^p = i\)? To help answer it, we need another use of stabiliser 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 problem can be answered using stabiliser chains, and in GAP is implemented by 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)
RepresentativeAction(G, [1,2], [2,6], OnTuples);
# fail
RepresentativeAction(H, [1,2], [2,6], OnTuples);
# (1,2,6,5,3,4)

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

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

This pattern will recur throughout backtrack search: we try to prove a subproblem has an answer or not, and get back yes, no, or don’t know.

So how can we 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\), we 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\).
\(\ldots\)

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? \(G\) maps \([1,2]\) only to \([2,1]\) and \([2,3]\), while \(H\) maps \([1,2]\) to \([2,1]\), \([2,3]\), and \([2,6]\). So any element of \(G \cap H\) which maps \(1\) to \(2\) must map \([1,2]\) to \([2,1]\).

Continuing: mapping \([1,2,3]\) to \([2,1,x]\) for different \(x\)? It turns out \(G\) only maps to \([2,1,3]\), while \(H\) maps to \([2,1,4]\) and \([2,1,5]\). So there is no element of \(G \cap H\) which maps \(1\) to \(2\).

Let’s encapsulate this as a GAP function. It is fairly long, but we’ll work through it.

Aside: Info

The Info function lets us print information about what our algorithm is doing. It takes a name for the type of info (we use InfoGroup, for group algorithms), the importance (lower numbers are more important), and the information to print. To see messages, run SetInfoLevel(InfoGroup, 1);, which prints all messages of level 1 or less.

Algorithm

FindExtendingElementGH takes two groups, a bound maxpnt, and an array \(\mathit{Array} = [x_1,\dots,x_n]\). It searches for a permutation \(p \in G \cap H\) such that \(i^p = \mathit{Array}[i]\) for all \(i \in \{1,\ldots,n\}\).

## 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 either returns 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 turns 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 it:

SetInfoLevel(InfoGroup, 3);
FindExtendingElementGH(G, 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 act 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}\). We could pass \(n\) around in all our functions, but instead we use LargestMovedPoint(G). This gives the largest integer \(n\) 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.
  if G = Group(()) or H = Group(()) then
    Info(InfoGroup, 1, "Reached base case");
    return [()];
  fi;

  # Recursive call for intersection of point
  # stabiliser 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;

# Set 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? The next chapter begins to answer that.