[GAP Forum] complexity of the "orbit" function

[Sven Reichard]

<By mistake, the following was sent before to Miguel Marco personally 
instead of the Forum>

  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?


The orbit algorithm computes both the orbit and the stabilizer at the
same time. However, it needs to store the whole orbit, which in your
case exceeds the available memory. You can certainly compute the
stabilizer in advance and check if its index exceeds a certain bound.

As far as I know, the time complexity depends on the orbit length and on
the number of given generators.

A way to reduce the memory requirements in some cases would be "double
inducing" (in the sense of Farad\v{z}ev). That is, first compute the
images of all sets under the group G and find the induced action G'.
Then identify the elements of your original set of sets with points of
this action; finally, compute the orbit of this set of points under G'.
The advantage is that you don't need to store several copies of the same
set; moreover - correct me if I'm wrong - the representation of lists of
integers is more compact.

This doesn't help if the images are all disjoint; however, in this case
it shouldn't hurt memory-wise.

Code to illustrate the idea, not tested:

SetSetOrbit := function( group, setset )
   local sets, induced, set, orbit;
   # find the images of all sets
   sets := Union( Orbits( group, setset, OnSets ) );
   # induced action on sets
   induced := Action( group, sets, OnSets );
   # represent our setset as a set under the induce action
   set := Set( List( setset, x -> Position( sets, x ) ) );
   # find the orbit
   orbit := Orbit( induced, set, OnSets );
   # finally, revert to sets of sets.
   orbit := List( orbit, x -> sets{x} );
   return orbit;
end;

I have used code like this to find orbits of length more than 10^6.

Hope this helps,

Sven.