[GAP Forum] Intersection of groups

[Alexander Hulpke]

Dear Forum, Dear Katie Morrison,

> Hi all, I was wondering if there was a command to find the intersection of
> two groups that was more efficient than just the standard Intersection
> command.  I'm currently trying to intersect two matrix groups, one which has
> size on the order of 10^13 and the other which has size on the order of
> 10^22.  I let GAP run overnight and it still had not found the intersection
> of these two groups when I used the Intersection command.

Normally `Intersection'  should do as good as it is implemented, but here you're running into a particular quirk of GAP (This could be considered as a bug, and I will have a look at it to see whether this can be fixed for the future):

The two  groups you created don't share a common overgroup (which could be simply GL). At this point, GAP does not try to construct such an overgroup, but calculates the intersection using cosets for both subgroups. This turns out to be a very tedious process and I believe that it could take days to complete.

A remedy is easy: Force both groups to be subgroups of the appropriate GL -- in your example:

gap> parent:=GL(8,3);
GL(8,3)
gap> u1:=AsSubgroup(parent,GOn);
<matrix group of size 79234877030400 with 3 generators>
gap> u2:=AsSubgroup(parent,StabMats);
<matrix group of size 25337383648548677222400 with 5 generators>
gap> Intersection(u1,u2);
<group of 8x8 matrices in characteristic 3>

This should work reasonably quick.

You might wonder why GAP in the first place tries to avoid constructing the common overgroup: At the moment, intersection of subgroups of a matrix group uses a faithful permutation representation of the common parent group. If you now have two small matrix groups (order a few hundred) for which the common overgroup is huge (say two cyclic subgroups of GL(20,11)), this permutation representation will fail (or be at least very slow), while the more naive intersection will work fine.

We need to select a break-even point for the choice of method.

Hope this helps,

   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