[GAP Forum] Finding a representative which moves fewest points

Alexander Hulpke hulpke at math.colostate.edu
Thu Apr 1 19:50:18 BST 2004


Dear GAP Forum,

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:

gap> g:=Group((1,3,2),(2,4,3));;
gap> p1:=1;         
gap> p2:=3;
gap> r:=RepresentativeAction(g,p1,p2);
(1,3)(2,4)
gap> s:=Stabilizer(g,p2);
Group([ (1,2,4) ])
gap> best:=r;
(1,3)(2,4)
gap> best:=r;bm:=NrMovedPoints(best);
(1,3)(2,4)
4
gap> for x in Enumerator(s) do
> a:=r*x;
> if NrMovedPoints(a)<bm then
> best:=a;bm:=NrMovedPoints(best);
> fi;
> od;
gap> best;
(1,3,2)

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.

Best wishes,

  Alexander Hulpke

-- Colorado State University, Department of Mathematics,
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




More information about the Forum mailing list