Dear GAP forum,

Jens Baek Joergensen <jbj@daimi.aau.dk> asks:
> Consider the call:
>
> PermGroupOps.SubgroupProperty(G, P);
>
> where G is some permutation group and P:G->Bool is some property. If every
> element in G satisfies P, it seems to me like this function call terminates
> very quickly - even when G is large. Is this observation correct and can it
> be justified be referring to some general property of the backtrack
> algorithm? (I assume that PermGroupOps.SubgroupProperty is the
> GAP-implementation of the backtrack algorithm described, e.g., in Butler's
> book "Fundamental Algorithms for Permutation Groups").
>
> If G is the symmetrical group for some natural number n, I think I can
> prove that the backtrack algorithm terminates after having tested exactly
> n-1 permutations. Does this result generalize to all kinds of permutation
> groups? Perhaps the number of permutations to test is equal to the number
> of elements in the considered base for G?

The backtrack algorithm maintains a subgroup K, which contains the
elements of G which are already known to satisfy property P.
If all elements of G satisfy P then K increases each time when a
permutation is tested; consequently, the maximal length of subgroup chains
in G is an upper bound for the number of elements tested.

Slightly more precisely, consider the point stabilizer chain

G=G_1 > G_2 > ... > G_m > G_{m+1}=1.

The backtrack algorithm works in a ``bottom-up'' manner, first
determining the subgroup of G_{i+1} satisfying P, before considering
the elements of G_i \setminus G_{i+1}. If G_{i+1} is always a
maximal subgroup of G_i (1 \le i \le m) then the first element of
G_i \setminus G_{i+1} which we test increases K to G_i.
So, the total number of elements tested is indeed the number of
base points. This happens e.g. in the case of the symmetric group.

In general, it may be possible that more elements are
added to K=G_{i+1} before it reaches K=G_i, corresponding to a
subgroup chain between G_i and G_{i+1}.

Best regards,
Akos Seress