How do I compute orbits of bit lists or determine random orbit elements

efficiently.

as well as on what you plan to do with the result. Thus the following are

only some hints that should suffice for reasonable input I can imagine.

If the performance is insufficient there are several further routes of

improvement, but many will require more information on the group structure.

In this case, or if you encounter problems, please feel free to contact us

again.

I would store the bit lists as vectors over GF2. (This is in preference to

bit lists since hash functions are installed for vectors but not for bit

lists.) the action on this vectors is by permutation -- this is given by the

GAP operation `Permuted'. Thus, for example (see the manual for the

respective operations for a complete description).

Create the permutation group (I use a predefined one on 20 points, but

obviously you can use more)

g:=TransitiveGroup(20,1000);

create the vector. We convert it in a immutable compressed format to save

memory and enable efficient hashing.

v:=[0,1,1,1,0,0,0,0,1,0,1,0,1,1,0,1,0,1,0,1]*Z(2); ConvertToVectorRep(v,2); MakeImmutable(v);

some orbit calculation:

Orbit(g, GF(2)^20, v, Permuted); ^ acting group ^ domain that contains the orbit (needed for hashing) ^ start point ^ action function

The drawback is that the `Permuted' action each time has to compute the

inverse of the acting permutation, as we see by looking at the code:

me:=ApplicableMethod(Permuted,[v,g.1]); Print(me); function ( list, perm ) return list{OnTuples( [ 1 .. Length( list ) ], perm ^ -1 )}; end;

Therefore it is beneficial to compute the index permutation lists first and

use a modified action function that will use these lists:

gens:=GeneratorsOfGroup(g); plists:=List(gens,i->OnTuples([1..20],i^-1));; MyPermuted:=function(l,p) return l{p}; end;

Now we let g act by its generators `gens' via their ``images'' plists. this

saves the inversion and is faster.

Orbit(g,GF(2)^20,v,gens,plists,MyPermuted);

To get a random orbit element, the easiest way would be to act by a random

group element. Here the time is used in `Random' and so we do not need to

act cleverly:

Permuted(v,Random(g));

If the group `g' is very big, setting up the stabilizer chain needed for

`Random' is time consuming. Instead it might be sufficient to use only

pseudo random elements (equal distribution is not guaranteed, but usually

reasonably good), for which the initial setup is easier.

Permuted(v,PseudoRandom(g));

(In both cases the first random element takes a bit longer than the

subsequent ones.)