[GAP Forum] efficient ways of computing orbit-stabilizers on equivalence classes of surjections

[Alexander Hulpke]

Dear Forum, Dear Will Chen,

While it always is worth to use a recent version of GAP, I don’t think the issue you describe would have changed since the release you use. Also PSL2(7) looks pathetically small for what you’re doing — I would expect that this should be doable easily for orders up in the millions.

> My current routine essentially goes like this:

Without knowing the commands it is somewhat hard to point to where the issue is, but here are a few pointers that might be of help:

First, instrumentize your code. Have it print out where in your algorithm you are.
Before running it call 
GASMAN(“messages”);
to get some printout about memory usage. Then run the code on a larger example and see where memory actually gets used (I have a suspicion below). 
> 
> 1. Compute GQuotients(F2,G)
> 2. Compute the orbits of Aut(G) on GQuotients(F2,G) to get a complete list
> of surjections F2 -> G, call it GQComplete

It is of course slightly ironic that GQuotients first does work to eliminate Aut(G)-conjugates and you then recreate them...

> 3. Compute the orbits of Inn(G) on GQComplete, store each orbit
> "AsSSortedList" (strictly sorted list)
> 4. Let SAut(F2) be the subgroup of Aut(F2) mapping onto SL(2,Z) (ie,
> automorphisms of "determinant 1"). Then I compute the orbits of SAut(F2)
> acting by composition on the set of orbits from (3), where each orbit is a
> "strictly sorted list”.

I think one issue could be the representation of objects (and the cost of strictly sorting homomorphisms). Could you — instead of storing homomorphisms — simply store the element tuples that are images of the standard generators of F2. These element tuples are are more easily, and should also have decent methods if you decided to use dictionaries.

Then instead of GQuotients, you would simply take those pairs out of the cartesian product G X G that generate G.

Next you might want to work with Inn(G)-orbits by picking a ``canonical’’ orbit representative. For the pair (a,b), conjugate a to its canonical conjugacy class representative (using `RepresentativeAction’) with an element x, getting (a^x,b^x), and then minimize b^x under the centralizer of a^x. For larger groups (once we get to millions) this could substantially save on storage.

> 5. Pick representatives of each orbit, compute their stabilizers.

This stabilizer calculation is where I would suspect memory gets used. You have an infinite group — SL2(Z) — in a nonstandard representation (automorphisms) and will fall into the standard method for stabilizer (at least I think so) that is aimed at finite groups.

If you can confirm that this suspicion is true, let me know, because I think there is another way to calculate this stabilizer from the action on the image by changing the representation.

Best,

   Alexander Hulpke

-- Colorado State University, Department of Mathematics,
Weber Building, 1874 Campus Delivery, Fort Collins, CO 80523-1874, USA
email: hulpke at math.colostate.edu, Phone: ++1-970-4914288
http://www.math.colostate.edu/~hulpke