1
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ @ahulpke : $G$ is defined abstractly as a quotient of a free group. the subgroups are generated by a subset of the generators of $G$. Since I know $G$ is finite, I turn it into a permutation group using IsomorphismPermGroup; that speeded things up considerably; but now I need another boost in speed for larger groups (>100K elements). $\endgroup$
    – unknown
    Commented Nov 23, 2020 at 18:44

1 Answer 1

3
$\begingroup$

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. )

$\endgroup$
1
  • $\begingroup$ Thanks a lot for your response. I'm seeing considerable speedup already (>10x). Your solution has the added advantage of allowing the description of "R" as a sparse matrix (which it is); so there should be even more efficiency still. $\endgroup$
    – unknown
    Commented Nov 23, 2020 at 20:17

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .