[GAP Forum] Counting occurrences of double cosets, or changing values in dictionaries

[Alexander Hulpke]

Dear Erick,

>> There are really two answers to your question. 
>> The first is the actual question — how to change the stored values of dictionaries. Here my choice (as the person who implemented much of the code for dictionaries) would be to not to attempt to change the values at all, but use as values the entries in a (changeable) value list. While this requires one indirection it is safe and requires no modification of data structures that might not have been set up for this, or might change in future releases (in fact is almost guaranteed to do so as there are still some issues in the code).
>> 
>> 
> I tried doing this, but once I stored the list in the dictionary I found I could no longer change the list.
> 
> gap> l := [3];
> [ 3 ]
> gap> d := NewDictionary(false, true, [1,2,3]);
> <object>
> gap> IsMutable(l);
> true
> gap> AddDictionary(d, 2, l);
> gap> IsMutable(l);
> false
> gap>
> 
> Am I confused?

No. The current code for dictionaries potentially makes (without warning or other niceties) the values of a dictionary immutable. Thus my suggestion for storing the index positions in another list:

gap> d := NewDictionary(false, true, [1,2,3]);
<object>
gap> values:=[];
[  ]
gap> cnt:=0;           
0
gap> cnt:=cnt+1;values[cnt]:=[];AddDictionary(d,2,cnt);
1
[  ]
gap> cnt:=cnt+1;values[cnt]:=[];AddDictionary(d,5,cnt);
2
[  ]
gap> values[LookupDictionary(d,5)];
[  ]
gap> AddSet(values[LookupDictionary(d,5)],'A');
gap> AddSet(values[LookupDictionary(d,5)],'Z');
gap> values[LookupDictionary(d,5)];
"AZ"


>> At the moment GAP has no specific hash key code for double cosets, so the best dictionaries can do is to compare using the `<‘ order. For double cosets, this comparison is done by determining the (minimal) representatives for all the contained right cosets, and comparing the smallest of the minimal coset representatives. While this ordering is equivalent to the ordering as sets of elements, if means that in fact you store representatives for all right cosets. Given that this is the case, I would try the following approach (assuming the subgroups are A and B):
>> 
> 
> Here again I think I must be confused:
> 
> gap> g:=SymmetricGroup(4);;
> gap> u:=Subgroup(g,[(1,2,3),(1,2)]);;
> gap> v:=Subgroup(g,[(3,4)]);;
> gap> cos:=DoubleCosets(g, u, v);
> [ DoubleCoset(Group( [ (1,2,3), (1,2) ] ),(),Group( [ (3,4) ] )),
>   DoubleCoset(Group( [ (1,2,3), (1,2) ] ),(1,4),Group( [ (3,4) ] )),
>   DoubleCoset(Group( [ (1,2,3), (1,2) ] ),(1,4,2),Group( [ (3,4) ] )) ]
> gap> cos[1] < cos[2];

Ah -- then there actually isn't yet such a comparison of double cosets (as described) , which means the dictionary code can rely only on comparing for equality (and linear search). Then using only right cosets is definitively faster.

> 
> Regarding publications, etc, we will be submitting a paper in early April to the FOCS CS conference, and will put it on the arXiv.

Thank you!

   Alexander

> I’d love to help out in any way I can.
> 
> Erick
> 
> 
> 
> 
> Calculate t:=RightTransversal(G,A)
> This is an object that behaves like a list, but often needs less storage.
> 
> Create a second list DCNumber that for each right coset of A stores the number (in some arbitrary indexing) of the double coset AxB that contains A.
> 
> If you find an element r, let
> 
> p:=PositionCanonical(t,r); # number of the right coset for the element
> if IsBound(DCNumber[p]) then
>   result:=DCNumber[p];
> else
>   newnum:=New index number for double coset;
>   result:=newnum;
>   DCNumber[p]:=newnum;
>   o:=Orbit(B,t[p],function(rep,g) return CanonicalRightCosetElement(A,rep*g);end);
>   for i in o do
>      DCNumber[PositionCanonical(t,i)]:=newnum; # mark all right cosets within the same double coset.
>   od;
> fi;
> 
> and then process result — the number of the double coset — as if it came as dictionary value. This is less slick code than dictinaries, but I’d suspect this will work notably faster.
> 
> Best,
> 
>     Alexander Hulpke
> 
>>  Frederick "Erick" Matsen, Assistant Member
>> Fred Hutchinson Cancer Research Center
> 
> Is there a chance you have a citable article or presentation that connects permutation group calculations with (the ultimate ``usefulness’’ argument for higher administration) attempts on dealing with cancer? This could come very helpful when questions of ``broader impace’’ etc. come up. Thanks!
> 
> 
> -- Alexander Hulpke. Department of Mathematics, Colorado State University, 
> 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
> 
> 
> 
> -- 
> Frederick "Erick" Matsen, Assistant Member
> Fred Hutchinson Cancer Research Center
> http://matsen.fredhutch.org/