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

[Alexander Hulpke]

Dear Forum, Dear Erick Matsen,

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

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

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