[MathJax off]

6 Constraints

6.1 Bounds associated with a constraint or refiner

In GAP, permutations are defined on the set of all positive integers (although each permutation may move only a finite set of points, and there is a system-dependent maximum point that is allowed to be moved).

Vole can only search within a concrete finite symmetric group. Therefore, when giving Vole a collection of constraints that define a search problem, the search space must be bounded. More specifically, Vole must be easily able to deduce a positive integer k such that the whole search can take place within Sym([1..k]). This guarantees that Vole will terminate (given sufficient resources).

To help Vole make such a deduction, each constraint and refiner is associated with the following values: a largest moved point, and a largest required point.

Any call to VoleFind.Group (5.2-2) or VoleFind.Coset (5.2-3) requires at least one constraint that defines a finite largest moved point, and any call to VoleFind.Representative (5.2-1) requires at least one constraint that defines a finite largest required point or a finite largest moved point.

Largest moved point

The largest moved point of a constraint is either infinity, or a positive integer k for which it is known a priori that any permutation satisfying the constraint fixes all points strictly greater than k.

For example, the largest moved point of the constraint Constraint.InGroup(G) is LargestMovedPoint(G), see LargestMovedPoint (Ref 42.3-2). On the other hand, any permutation stabilises the empty set, so there is not largest moved point of the constraint Constraint.Stabilise([],OnSets); therefore the value in this case must be infinity.

Largest required point

The largest required point of a constraint is either infinity, or a positive integer k such that there exists a permutation satisfying the constraint if and only if there exists a permutation in Sym([1..k]) satisfying the constraint.

For example, if set is a set of positive integers, then the largest required point of the constraint Constraint.Stabilise(set,OnSets) is Maximum(set).

The largest moved point of a constraint can serve as an upper bound for the largest required point of a constraint.

gap> LoadPackage("vole", false);;

6.2 The concept of constraints

Fundamentally, the partition backtrack algorithm (and its generalisations) performs a search for permutations that satisfy a collection of constraints.

A constraint is a true/false mathematical property of permutations, such that if the set of permutations satisfying the property is nonempty, then that set must be a (possibly infinite) permutation group, or a coset thereof. For constraints to be useful in practice, it should be ‘easy’ to test whether any given permutation satisfies the property.

For example:

• “is a member of the group \(G = \langle X \rangle\)”,

• “transports the set A to the set B”,

• “commutes with the permutation \(x\)”,

• “conjugates the group \(G = \langle X \rangle\) to the group \(H = \langle Y \rangle\)”,

• “is an automorphism of the graph \(\Gamma\)”, and

• “is even”

are all examples of constraints. On the other hand:

• “is a member of the socle of the group \(G\)”, and

• “is a member of a largest maximal subgroup of the group \(G\)”

do not qualify, unless generating sets for the socle and the largest maximal subgroups of \(G\) are already known, and there is a unique such maximal subgroup (in which case these properties become instances of the constraint “is a member of the group defined by the generating set...”).

The term ‘constraint’ comes from the computer science field of constraint satisfaction problems, constraint programming, and constraint solvers, with which backtrack search algorithms are very closely linked.

A number of built in constraints, and the functions to create them, are contained in the Constraint (6.3-1) record. The members of this record are documented individually in Section 6.4.

To perform a search, it is necessary to (at least implicitly) specify constraints that, in conjunction, define the permutation(s) that you wish to find. A constraint will typically be converted into one or more refiners by that the time that a search takes place. Refiners are introduced in Chapter 7, which are the low-level code which implement constraints. We do not explicitly document the conversion of constraints into refiners; the conversion may change in the future.

6.3 The Constraints record

6.3-1 Constraint

Constraint is a record that contains functions for producing all of the constraints provided by default.

The members of Constraint are documented individually in Section 6.4.

The members whose names differ only by their “-ise” and “-ize” endings are synonyms, included to accommodate different spellings in English.

gap> LoadPackage("BacktrackKit", false);;
gap> Set(RecNames(Constraint));
[ "Centralise", "Centralize", "Conjugate", "Everything", "InCoset",
  "InGroup", "InLeftCoset", "InRightCoset", "IsEven", "IsOdd", "IsTrivial",
  "LargestMovedPoint", "MovedPoints", "None", "Normalise", "Normalize",
  "Nothing", "Stabilise", "Stabilize", "Transport" ]

6.4 Constraints via the Constraint record

In this section, we individually document the functions of the Constraint (6.3-1) record, which can be used to create the built-in constraints provided by BacktrackKit.

Many of these constraints come in pairs, with a “group” version, and a corresponding “coset” version. These relationships are given in the following table.

6.4-1 Constraint.InGroup

Returns: A constraint

This constraint is satisfied by precisely those permutations in the permutation group G.

gap> con1 := Constraint.InGroup(DihedralGroup(IsPermGroup, 8));
<constraint: in group: Group( [ (1,2,3,4), (2,4) ] )>
gap> con2 := Constraint.InGroup(AlternatingGroup(4));
<constraint: in group: AlternatingGroup( [ 1 .. 4 ] )>

6.4-2 Constraint.InCoset

Returns: A constraint

This constraint is satisfied by precisely those permutations in the GAP right coset object U.

See also Constraint.InLeftCoset (6.4-4) and Constraint.InRightCoset (6.4-3), which allow a coset to be specifed by a subgroup and a representative element.

gap> U := PSL(2,5) * (3,4,6);
RightCoset(Group([ (3,5)(4,6), (1,2,5)(3,4,6) ]),(3,4,6))
gap> Constraint.InCoset(U);
<constraint: in coset: Group( [ (3,5)(4,6), (1,2,5)(3,4,6) ] ) * (3,4,6)

6.4-3 Constraint.InRightCoset

Returns: A constraint

This constraint is satisfied by precisely those permutations in the right coset of the group G determined by the permutation x.

See also Constraint.InLeftCoset (6.4-4) for the left-hand version, and Constraint.InCoset (6.4-2) for a GAP right coset object.

gap> Constraint.InRightCoset(PSL(2,5), (3,4,6));
<constraint: in coset: Group( [ (3,5)(4,6), (1,2,5)(3,4,6) ] ) * (3,4,6)

6.4-4 Constraint.InLeftCoset

Returns: A constraint

This constraint is satisfied by precisely those permutations in the left coset of the group G determined by the permutation x.

See also Constraint.InRightCoset (6.4-3) for the right-hand version, and Constraint.InCoset (6.4-2) for a GAP right coset object.

gap> Constraint.InLeftCoset(PSL(2,5), (3,4,6));
<constraint: in coset: Group( [ (3,6)(4,5), (1,2,5)(3,4,6) ] ) * (3,4,6)

6.4-5 Constraint.Transport

Returns: A constraint

This constraint is satisfied by precisely those permutations that map object1 to object2 under the given group action, i.e. all permutations g such that action(object1,g)=object2. Note that the set of such permutations may be infinite.

The combinations of objects and actions that are supported by Constraint.Transport are given in the table below.

The default action, in the case that the argument is not given, is OnPoints (Reference: OnPoints). This is the name in GAP of the action given by the ^ operator, i.e. it corresponds to object^g, where g in G. See \^ (Reference: ^).

gap> setofsets1 := [[1, 3, 6], [2, 3, 6]];;
gap> setofsets2 := [[1, 2, 5], [1, 5, 7]];;
gap> con := Constraint.Transport(setofsets1, setofsets2, OnSetsSets);
<constraint: transporter of [ [ 1, 3, 6 ], [ 2, 3, 6 ] ] to [ [ 1, 2, 5 ], [ 1\
, 5, 7 ] ] under OnSetsSets>

6.4-6 Constraint.Stabilise

Returns: A constraint

This constraint is satisfied by precisely those permutations that fix object under the given group action, i.e. all permutations g such that action(object,g)=object. Note that the set of such permutations may be infinite.

The combinations of objects and actions that are supported by Constraint.Stabilise are given in the table below.

The default action, in the case that the argument is not given, is OnPoints (Reference: OnPoints). This is the name in GAP of the action given by the ^ operator, i.e. it corresponds to object^g, where g in G. See \^ (Reference: ^).

gap> con1 := Constraint.Stabilise(CycleDigraph(6), OnDigraphs);
<constraint: stabiliser of CycleDigraph(6) under OnDigraphs>
gap> con2 := Constraint.Stabilise([2,4,6], OnSets);
<constraint: stabiliser of [ 2, 4, 6 ] under OnSets>

6.4-7 Constraint.Normalise

Returns: A constraint

This constraint is satisfied by precisely those permutations that normalise the permutation group G, i.e. that preserve G under conjugation.

Note that the set of such permutations is infinite.

gap> Constraint.Normalise(PSL(2,5));
<constraint: normalise Group( [ (3,5)(4,6), (1,2,5)(3,4,6) ] )>

6.4-8 Constraint.Centralise

Returns: A constraint

This constraint is satisfied by precisely those permutations that commute with G, if G is a permutation, or that commute with every element of G, if G is a permutation group.

Note that the set of such permutations is infinite.

gap> D12 := DihedralGroup(IsPermGroup, 12);;
gap> Constraint.Centralise(D12);
<constraint: centralise group Group( [ (1,2,3,4,5,6), (2,6)(3,5) ] )>
gap> x := (1,6)(2,5)(3,4);;
gap> Constraint.Centralise(x);
<constraint: centralise perm (1,6)(2,5)(3,4)>

6.4-9 Constraint.Conjugate

Returns: A constraint

This constraint is satisfied by precisely those permutations that conjugate x to y, where x and y are either both permutations, or both permutation groups.

Note that the set of such permutations may be infinite.

This constraint is equivalent to Constraint.Transport(x,y,OnPoints).

gap> Constraint.Conjugate((3,4)(2,5,1), (1,2,3)(4,5));
<constraint: conjugate perm (1,2,5)(3,4) to (1,2,3)(4,5)>

6.4-10 Constraint.MovedPoints

Returns: A constraint

This constraint is a shorthand for Constraint.InGroup(SymmetricGroup(pointlist)). See Constraint.InGroup (6.4-1).

gap> con1 := Constraint.MovedPoints([1..5]);
<constraint: moved points: [ 1 .. 5 ]>
gap> con2 := Constraint.MovedPoints([2,6,4,5]);
<constraint: moved points: [ 2, 6, 4, 5 ]>

6.4-11 Constraint.LargestMovedPoint

Returns: A constraint

This constraint is a shorthand for Constraint.InGroup(SymmetricGroup(point)), where point is a nonnegative integer. See Constraint.InGroup (6.4-1).

gap> con := Constraint.LargestMovedPoint(5);
<constraint: largest moved point: 5>

6.4-12 Constraint.IsEven

This constraint is satisfied by the even permutations, i.e. those permutations with sign 1. In other words, this constraint restricts a search to some alternating group.

Note that the set of such permutations is infinite.

gap> Constraint.IsEven;
<constraint: is even permutation>
gap> Representative(Constraint.IsEven);
()

6.4-13 Constraint.IsOdd

This constraint is satisfied by the odd permutations, i.e. those permutations with sign -1. In other words, this constraint restricts a search to the unique coset of some alternating group.

Note that the set of such permutations is infinite.

gap> Constraint.IsOdd;
<constraint: is odd permutation>
gap> Representative(Constraint.IsOdd);
(1,2)

6.4-14 Constraint.IsTrivial

This constraint is satisfied by the identity permutation and no others.

This constraint will typically not be required by the user.

gap> Constraint.IsTrivial;
<trivial constraint: is identity permutation>
gap> Representative(Constraint.IsTrivial);
()

6.4-15 Constraint.None

This constraint is satisfied by no permutations.

This constraint will typically not be required by the user.

gap> Constraint.None;
<empty constraint: satisfied by no permutations>
gap> Representative(Constraint.None);
fail

6.4-16 Constraint.Everything

This constraint is satisfied by all permutations.

This constraint will typically not be required by the user.

gap> Constraint.Everything;
<constraint: satisfied by all permutations>
gap> Representative(Constraint.Everything);
()

generated by GAPDoc2HTML