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

[Erick Matsen]

Alexander—

This was indeed very helpful. Here is my version of the code:

NewDCCounter := function(g, u, v)
    return rec(
        g := g,
        u := u,
        v := v,
        max_idx := 0,
        dc_number := [],
        t := RightTransversal(g, u),
        counts := []);
end;;

AddDCCounter := function(dcc, r)
    local dcn, i, o;
    p := PositionCanonical(dcc.t, r); # Number of the right coset for
the element.
    if IsBound(dcc.dc_number[p]) then
        dcn := dcc.dc_number[p];
        dcc.counts[dcn] := dcc.counts[dcn] + 1;
    else
        dcc.max_idx := dcc.max_idx + 1;
        dcc.counts[dcc.max_idx] := 1;
        dcc.dc_number[p] := dcc.max_idx;
        # Mark all right cosets within the same double coset, via
        # orbit of right coset (dcc.u, t[p]) under dcc.v by right
multiplication.
        o := Orbit(dcc.v, CanonicalRightCosetElement(dcc.u, dcc.t[p]),
        #o := Orbit(dcc.v, dcc.t[p],
            function(pnt, s)
                return CanonicalRightCosetElement(dcc.u, pnt*s);
            end);
        for i in o do
            dcc.dc_number[PositionCanonical(dcc.t, i)] := dcc.max_idx;
        od;
    fi;
end;;

and it in action:

gap> mdcc := NewDCCounter(SymmetricGroup(4),
Subgroup(g,[(1,2,3),(1,2)]), Subgroup(g,[(3,4)]));
rec( counts := [  ], dc_number := [  ], g := Sym( [ 1 .. 4 ] ), max_idx := 0,
  t := RightTransversal(Sym( [ 1 .. 4 ] ),Group([ (1,2,3), (1,2) ])),
u := Group([ (1,2,3), (1,2) ]),
  v := Group([ (3,4) ]) )
gap> AddDCCounter(mdcc, (1,2)); mdcc;
rec( counts := [ 1 ], dc_number := [ 1,,, 1 ], g := Sym( [ 1 .. 4 ] ),
max_idx := 1,
  t := RightTransversal(Sym( [ 1 .. 4 ] ),Group([ (1,2,3), (1,2) ])),
u := Group([ (1,2,3), (1,2) ]),
  v := Group([ (3,4) ]) )
gap> AddDCCounter(mdcc, (1,2,3)); mdcc;
rec( counts := [ 2 ], dc_number := [ 1,,, 1 ], g := Sym( [ 1 .. 4 ] ),
max_idx := 1,
  t := RightTransversal(Sym( [ 1 .. 4 ] ),Group([ (1,2,3), (1,2) ])),
u := Group([ (1,2,3), (1,2) ]),
  v := Group([ (3,4) ]) )
gap> AddDCCounter(mdcc, (1,2,4)); mdcc;
rec( counts := [ 2, 1 ], dc_number := [ 1, 2,, 1 ], g := Sym( [ 1 .. 4
] ), max_idx := 2,
  t := RightTransversal(Sym( [ 1 .. 4 ] ),Group([ (1,2,3), (1,2) ])),
u := Group([ (1,2,3), (1,2) ]),
  v := Group([ (3,4) ]) )
gap>
gap> AddDCCounter(mdcc, (2,4)); mdcc;
rec( counts := [ 2, 1, 1 ], dc_number := [ 1, 2, 3, 1 ], g := Sym( [ 1
.. 4 ] ), max_idx := 3,
  t := RightTransversal(Sym( [ 1 .. 4 ] ),Group([ (1,2,3), (1,2) ])),
u := Group([ (1,2,3), (1,2) ]),
  v := Group([ (3,4) ]) )
gap>
gap> AddDCCounter(mdcc, (1,4)); mdcc;
rec( counts := [ 2, 2, 1 ], dc_number := [ 1, 2, 3, 1 ], g := Sym( [ 1
.. 4 ] ), max_idx := 3,
  t := RightTransversal(Sym( [ 1 .. 4 ] ),Group([ (1,2,3), (1,2) ])),
u := Group([ (1,2,3), (1,2) ]),
  v := Group([ (3,4) ]) )
gap>
gap> AddDCCounter(mdcc, (1,4)); mdcc;
rec( counts := [ 2, 3, 1 ], dc_number := [ 1, 2, 3, 1 ], g := Sym( [ 1
.. 4 ] ), max_idx := 3,
  t := RightTransversal(Sym( [ 1 .. 4 ] ),Group([ (1,2,3), (1,2) ])),
u := Group([ (1,2,3), (1,2) ]),
  v := Group([ (3,4) ]) )
gap>

Please let me know if there is anything I can do with respect to Broader
Impacts. It looks like I’ll be giving a talk in the 2016 AMS conference in
Seattle, so perhaps we can meet then.

Erick
​

On Tue, Mar 10, 2015 at 7:57 AM, Alexander Hulpke <hulpke at fastmail.fm>
wrote:

> 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/
>
>


-- 
Frederick "Erick" Matsen, Assistant Member
Fred Hutchinson Cancer Research Center
http://matsen.fredhutch.org/