This chapter describes the methods for backtrack search in the **genss** package. Note that the code in this area is not yet very stable and is almost certainly going to change in subsequent versions of this package. This might also concern the interfaces and calling conventions.

`‣ SetwiseStabilizer` ( G, op, M ) | ( operation ) |

Returns: a record

This operation computes the setwise stabiliser of the set `M`. So `G` must be a group acting on some set \(\Omega\), this action is given by the action function `op`. The set `M` must consist of elements \(\Omega\). The result is a record with the components `setstab`

containing the setwise stabiliser and `S`

containing a stabiliser chain for it.

This operation uses backtrack search in a specially crafted stabiliser chain for `G` doing not much intelligent pruning of the search tree, so expect possible long delays!

`‣ SetwiseStabilizerPartitionBacktrack` ( G, op, M ) | ( operation ) |

Returns: a record

This operation computes the setwise stabiliser of the set `M`. So `G` must be a group acting on some set \(\Omega\), this action is given by the action function `op`. The set `M` must consist of elements \(\Omega\). The result is a record with the components `setstab`

containing the setwise stabiliser and `S`

containing a stabiliser chain for it.

This operation uses backtrack search in a specially crafted stabiliser chain for `G`. It does some ideas coming from partition backtrack but does not (yet) implement a full featured partition backtrack, so expect possible longish delays!

`‣ BacktrackSearchStabilizerChainElement` ( S, P, g, pruner ) | ( operation ) |

Returns: `fail`

or a group element

Let \(G\) be the group described by the stabiliser chain `S`. The group element `g` must be some element in an overgroup \(\hat G\)of \(G\) such that the function `P` described below is defined on the whole of \(\hat G\)

This operation implements a generic backtrack search in the coset \(G\textit{g}\) looking for an element \(x\ in G\) such that `P`\((x\textit{g})\) is `true`

where `P` is a function on \(\hat G\)taking values `true`

and `false`

. The operation returns the group element \(x\) if one is found or `fail`

if none was found.

The search tree is given by the stabiliser chain, each node corresponds to a right coset of one of the stabilisers in the chain. The leaves correspond to right cosets of the identity group, i.e. to group elements in \(G\textit{g}\)

To make this backtrack search efficient some pruning of the search tree has to be done. To this end there is the fourth argument `pruner` which can either be `false`

(in which case no pruning at all happens) or a **GAP** function taking 5 arguments and returning either `true`

or `false`

. The function `pruner` is called for every node in the search tree before the backtrack search descents into the subtrees. If the `pruner` function returns `false`

, the complete subtree starting at the current node is pruned and no further search is performed there. If the result is `true`

(or `pruner` was equal to `false`

altogether) then the subtree starting at the current node is searched recursively. Obviously, the `pruner` function needs to know the current position in the search tree, which it is told by its arguments.

Each node in the search tree corresponds to a coset of some stabiliser of the stabiliser chain in its previous one. To set up some notation, let \( G = S_0 > S_1 > S_2 > \cdots > S_m > S_{{m+1}} = \{1\} \) be the stabiliser chain and let \( O_1, O_2, \ldots, O_m \) be the basic orbits. Then for the node corresponding to the coset \(S_i t\textit{g}\) for \(i \ge 1\) and some transversal element \(t\) contained in \(S_{{i-1}}\) the arguments with which the `pruner` function is called are the following: The first argument is the stabiliser chain object corresponding to \(S_{{i-1}}\). The second argument is the index of the element in \(O_i\) corresponding to the transversal element \(t\). The third argument is the group element \(t\textit{g}\) and the fourth argument is equal to the actual transversal element \(t\). The fifth argument is a word in the generators used to enumerate \(O_i\) expressing \(t\), the word comes as a list of integers which are the generator numbers.

`‣ BacktrackSearchStabilizerChainSubgroup` ( S, P, pruner ) | ( operation ) |

Returns: `fail`

or a stabiliser chain

Let \(G\) be the group described by the stabiliser chain `S`. This operation implements a generic backtrack search in the stabiliser chain `S` looking for the subgroup \(H\) of the group \(G\) described by `S` of all elements \(x\) for which `P`\((x)\) is `true`

, where `P` is a function on \(G\) taking values `true`

or `false`

. Note that of course `P` must be such that \(H\) is actually a subgroup! The operation returns a stabiliser chain describing the group \(H\).

The search tree is given by the stabiliser chain, each node corresponds to a right coset of one of the stabilisers in the chain. The leaves correspond to right cosets of the identity group, i.e. to group elements in \(G\)

To make this backtrack search efficient some pruning of the search tree has to be done. To this end there is the fourth argument `pruner` which can either be `false`

(in which case no pruning at all happens) or a **GAP** function taking 5 arguments and returning either `true`

or `false`

. The function `pruner` is called for every node in the search tree before the backtrack search descents into the subtrees. If the `pruner` function returns `false`

, the complete subtree starting at the current node is pruned and no further search is performed there. If the result is `true`

(or `pruner` was equal to `false`

altogether) then the subtree starting at the current node is searched recursively. Obviously, the `pruner` function needs to know the current position in the search tree, which it is told by its arguments.

Each node in the search tree corresponds to a coset of some stabiliser of the stabiliser chain in its previous one. To set up some notation, let \( G = S_0 > S_1 > S_2 > \cdots > S_m > S_{{m+1}} = \{1\} \) be the stabiliser chain and let \( O_1, O_2, \ldots, O_m \) be the basic orbits. Then for the node corresponding to the coset \(S_i t\textit{g}\) for \(i \ge 1\) and some transversal element \(t\) contained in \(S_{{i-1}}\) the arguments with which the `pruner` function is called are the following: The first argument is the stabiliser chain object corresponding to \(S_{{i-1}}\). The second argument is the index of the element in \(O_i\) corresponding to the transversal element \(t\). The third and fourth arguments are the transversal element \(t\). The fifth argument is a word in the generators used to enumerate \(O_i\) expressing \(t\), the word comes as a list of integers which are the generator numbers.

generated by GAPDoc2HTML