GAP QA #1

Action on Bit lists

Keywords: Orbit, Permuted, Bit list

Respondent:

Alexander Hulpke ( hulpke@math.colostate.edu)

Question:

A permutation Group G acts on N points acts on bit-sequences of length N.
How do I compute orbits of bit lists or determine random orbit elements
efficiently.

Answer:

The best way to proceed depends a bit on the structure of the group involved
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.)

GAP QA #1

Action on Bit lists

Respondent:

Question:

Answer:

Back to the GAP QA list