[GAP Forum] Finding a representative which moves fewest points
Warwick Harvey
wh at icparc.ic.ac.uk
Mon Apr 19 18:21:22 BST 2004
Dear Alexander, dear GAP Forum,
Thanks for your feedback.
On Thu, Apr 01, 2004 at 11:50:18AM -0700, Alexander Hulpke wrote:
> Warwick Harvey asked:
>
> > What I would like is a function like RepresentativeAction which returns a
> > representative that moves as few points as possible. Taking the example
> > from the manual:
> >
> > gap> g:=Group((1,3,2),(2,4,3));;
> > gap> RepresentativeAction(g,1,3);
> > (1,3)(2,4)
> >
> > I would like instead the element (1,3,2), since this only moves 3 points
> > rather than 4. I tried constructing cosets of the stabilizer of 1 and using
> > RepresentativeSmallest on the appropriate coset, but of course the notion of
> > smallest there is not what I want.
>
> Basically you want to find an element x in the stabilizer of 3 so that r*x
> fixes many points. If your group is of moderate degree, probvably the
> following brute-force approach works:
Thanks. Unfortunately, by the time I apply it to real problems, a brute
force search is out of the question. The first real problem I tried it on
required solving a sequence of a couple of hundred such problems on groups
growing to size 2e35 (large base groups with lots of block structure).
> If your group gets bigger so that you do not want to run through all
> elements in s, I would consider to map some points according to the orbits
> of s.
Indeed. In the last couple of weeks I have developed a backtracking search
algorithm which appears to be quite effective; each of the above instances
is solved in less than a minute, often under a second (1.7GHz Centrino
processor). The minimal representatives had between 52 and 260 moved points
out of 1170. The real key was finding a good lower bound on the number of
points that must be moved in a representative. If anybody is interested in
the details I am happy to pass them on.
One thing I noticed while working on this which surprised me (probably just
my naivete) was that something like RepresentativeAction(g, 1, 2) was
significantly slower than Orbit(g, 1) - at least for my groups. Presumably
the algorithm that RepresentativeAction uses is a general one, and there's
no specialisation for this easy case. (Either that, or Orbit is doing
something smarter than I expected.) (This is using 4.3 - I haven't tried
4.4 yet.)
Cheers,
Warwick
More information about the Forum
mailing list