[GAP Forum] Question regarding testing lex min representatives of orbits

[Steve Linton]

Dear GAP Forum,

Jim Ostrowski asked:

On Mon, 29 Oct 2007 16:36:13 -0400
"jim ostrowski" <jao204 at gmail.com> wrote:

 I need to check
> if there exists a set F' in the orbit of F (w.r.t. a given symmetry group)
> which is lexicographically smaller than F. For example, I have a group
> consisting of the permutation (1,2). I need to test if the set (word) {2,3}
> is a lex min representative of its orbit (which it is not, since {1,3} <
> {2,3}).
> 
> Can I do this directly in GAP? I have tried to read through the
> documentation, and I haven't seen anything that makes me think I can do it.
> If not, is there any other software available which would do this? Would it
> be difficult to write code in GAP which would do this?
> 

There is a function SmallestImageSet in the GRAPE package which could be used
for this. That function is based on some code of mine, and if it would be
useful I can probably send you a more recent version. In particular, I have
versions that test for lex-minimality rather than constructing the lex-minimal
element, which can be cheaper.

> Assuming I am able to do the above, I am next interested in testing for lex
> min using a rank vector. So, using the above example, if the rank of the
> element "2" is less than the rank of the element "1", then {2,3} < {1,3}.
> 
I would suggest conjugating your permutation group so as to renumber the
points so that the natural order on points corresponds to your "ranks". Then
you have reduced the problem to the one avove.

> Thank you for reading my question. I feel bad asking what I am sure is a
> basic question, but I thought it wouldn't hurt to send this out before I
> start having to code something from scratch.

No problem. I've been meaning for years to put all my "Smallest Image" code
into a proper package, I just haven't got round to it.

	Steve

-- 
Steve Linton	School of Computer Science  &
      Centre for Interdisciplinary Research in Computational Algebra
	     University of St Andrews 	 Tel   +44 (1334) 463269
http://www.cs.st-and.ac.uk/~sal 	 Fax   +44 (1334) 463278