[GAP Forum] complexity of the "orbit" function

[Derek Holt]

On Wed, Jul 06, 2005 at 02:01:38PM +0200, Miguel Marco wrote:
> Dear gap forum
> 
> I am doing some calculations that involve calculating the orbit of permutation 
> groups over sets of sets. The problem is that in some cases, the procedure 
> excedes the memory of my computer. I want to detect when will that happen, in 
> order to separate the cases where that calculation will take too much memory 
> from the rest.
> My question is: what does the complexity of the "orbit" function deppend on? 
> The order of the group?, the index of the stabilizer of the object? And how 
> can i estimate it before attempting to caluclate the actual orbit?

Can I just add one further comment to the detailed replies that you have
already received.

There are methods available for estimating the sizes of orbits without
calculating the whole orbit. Thye can help you to decide whether it is
likely to be feasible to enumerate the whole orbit.

The idea is to start computing the orbit s^G = [ s=s1, s2, s3, ... ] of  s
under G in the usual way, by applying generators of G to s1, s2, s3, in turn.
At the same time you count coincidences, where a coincidence means an
application of a generator g to an orbit element si producing an element
si^g  that is already in S.

If at some stage you have computed   n  orbit elements while finding
L  coincidences, then s^2/(2L) is an estimate of the orbit length.

This is discussed briefly in Section 9 of
Bettina Eick, C.R. Leedham-Green and E.A. O'Brien
 ``Constructing automorphism groups of p-groups", 
Comm. Algebra 30 (2002), 2271-2295.

Derek Holt.