[GAP Forum] efficient hamming distance computation

[A L]

Thanks for the enthusiastic response, Dmitrii. I have tried to respond in
the body of your email, below.
I also wanted to point out that I am (somewhat) familiar with the
theoretical literature related to this problem, and I am mostly interested
in learning more about the specific implementation in GAP. For instance, if
the most efficient way to compute d(a,b) in GAP is to compute the fixed
points of ab^-1, which efficient functions should I call to perform this
computation?


On Thu, Jan 17, 2013 at 4:52 AM, Dmitrii (Dima) Pasechnik
<dima at ntu.edu.sg>wrote:

> On 17 January 2013 15:52, A L <group.compute at gmail.com> wrote:
> > Hello,
> >
> > For a project, I need to compute the minimal Hamming distance between a
> > fixed permutation and a (large) permutation group.
> it would be good to know how large the group can be, and what is its
> degree n.
>
> Let me be a little more specific. At the moment, I am looking at the
families of groups PGL(2,q) where q ~ 50, so let's say n ~ 100k.

>
> > What is the "correct"
> > way to do this in GAP? I am looking for the most efficient method, both
> for
> > the Hamming distance computation between individual elements, as well as
> > ways to avoid brute-force comparison with each element in the group
> > (perhaps utilizing information about the group's structure).
>
> Note that if H is your group and g your permutation, then the Hamming
> distance d(H,g) between H and g equals d(H,HgH), for HgH the double
> coset of H in <H,g>, or in S_n, does not matter.
> (This holds as d(f,g)=d(hf,hg)=d(hfh',hgh') for any f,h,h' in H.)
>

Can you clarify what you mean in the section starting here:

> So you might begin by trying to find a "nicer" element in Hg.
> E.g. you might want to find such an element with maximum (or just
> large) number of fixed points. Then the pointwise stabilizer of these
> points in H will contain the closest to g element, as far as I can
> see.
>
and ending here.

Another point of view might be useful if you can construct the set of
> double cosets of H in S_n. Then you can create a graph structure on
> them using transpositions: H is connected to HtH for a transposition t
> not in H (and so for any g in HtH one has d(H,g)=2, for g in Htt'H one
> would have d(H,g)=3 or 4,... ), etc.
>
> Perhaps there are even better methods for your problem: indeed,
> computing d(,) seems to be an extension of a procedure to check
> whether g is in H, and this is studied very extensively.
>
Which (specific) references do you have in mind?

> Seems to be a natural and interesting problem, IMHO!
>
> HTH,
> Dmitrii
>
>
> >
> > Any help or pointers/references would be appreciated. I am new to GAP and
> > have tried my best to wade through the extensive documentation.
> > _______________________________________________
> > Forum mailing list
> > Forum at mail.gap-system.org
> > http://mail.gap-system.org/mailman/listinfo/forum
>
> CONFIDENTIALITY:This email is intended solely for the person(s) named and
> may be confidential and/or privileged.If you are not the intended
> recipient,please delete it,notify us and do not copy,use,or disclose its
> content.
>
> Towards A Sustainable Earth:Print Only When Necessary.Thank you.
>