How to calculate coset intersection in gap

Question

Given a finite group $G$ and two of its subgroups $S_1,S_2$, I'd like to calculate the intersection of the cosets of $S_1$ and $S_2$.

This works but it's taking too long as the group size gets larger :

G:=(group);

S1:=Subgroup(G,...);Cosets1:=RightCosets(G,S1);

S2:=Subgroup(G,...);Cosets2:=RightCosets(G,S2);

R:=List(Cosets1,x->List(Cosets2,y->Size(Intersection(x,y))));

Are there faster ways to do this.

If it simplifies the problem, instead of the actual size of the intersection I can also use a binary indicator whether the two cosets intersect or not.

Answer 1

There is no special routine for the intersection of cosets - it computes elements lists and intersects these. Thus the inefficiency when working in larger groups. In general, in GAP, working with transversals instead of cosets is faster, and the command PositionCanonical finds the transversal position corresponding to a given element.

The intersection of cosets of subgroups $S$, respectively $T$, is a coset of $S\cap T$ (Intersection of cosets). To find which cosets of $T$ a coset $Sx$ intersects, it is thus sufficient to split $Sx$ into cosets of $S\cap T$ (representatives are $cx$ where $c$ runs through a transversal of $S\cap T$ in $S$), and for each such coset $(S\cap T) cx$ find the coset of $T$ in which the representative $cx$ lies.

You can do so in GAP as follows (example, but this should work quickly for much larger sizes):

gap> G:=SymmetricGroup(6);;
gap> S:=Stabilizer(G,[1,2],OnSets);;T:=Stabilizer(G,[1,2,3],OnSets);;
gap> Ttrans:=RightTransversal(G,T);
RightTransversal(Sym( [ 1 .. 6 ] ),Group([ (4,5,6), (4,5), (1,2,3), (1,2) ]))
gap> ST:=Intersection(S,T);;
gap> ST:=Intersection(S,T);
Group([ (5,6), (4,5,6), (1,2)(5,6) ])
gap> STt:=RightTransversal(S,ST);
RightTransversal(Group([ (3,4,5,6), (3,4), (1,2) ]),Group(
[ (5,6), (4,5,6), (1,2)(5,6) ]))
gap> x:=(2,4,5);; # whatever element you want
gap> List(STt,c->PositionCanonical(Ttrans,c*x));
[ 5, 9, 8, 2 ]

So the coset $Sx$ intersects the cosets of $T$ with representatives in Positions 2,5,9,8. A brute-force check (not recommended in general) for this is:

gap> Filtered([1..Length(Ttrans)],y->Length(Intersection(S*x,T*Ttrans[y]))>0);
[ 2, 5, 8, 9 ]

(This approach assumes that the group is given as a permutation group (or a PCGroup). And - unavoidably - this becomes more expensive if the indices $[S:S\cap T]$ or $[G:T]$ become larger. But for example I tried itin $M_{24}$ (order ~$2\cdot 10^8$), it just took seconds. )