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

[Erick Matsen]

Dear Alexander—

Yes, I’m well aware of the breadth of your contributions to GAP4. Thank you
for that, and for your detailed response.

First, I’m a little confused about some of the statements you made. I am
running GAP, Version 4.7.5 of 24-May-2014.

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?

The second answer goes closer to what you are actually doing, namely
> identifying double cosets.
>
> 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];
Error, no method found! For debugging hints type ?Recovery from NoMethodFound
Error, no 1st choice method found for `<' on 2 arguments called from
<function "HANDLE_METHOD_NOT_FOUND">( <arguments> )
 called from read-eval loop at line 40 of *stdin*
you can 'quit;' to quit to outer loop, or
you can 'return;' to continue
brk>

Thank you for your help, and suggestions below, which I will think about
once we get the above sorted out.

Regarding publications, etc, we will be submitting a paper in early April
to the FOCS CS conference, and will put it on the arXiv. 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/