[GAP Forum] Finding a representative which moves fewest points

[Warwick Harvey]

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