> < ^ Date: Fri, 16 Aug 2002 12:44:34 +0100
> < ^ From: Steve Linton <sal@dcs.st-and.ac.uk >
> < ^ Subject: Re: large permutation groups

Dear GAP Forum,

On Thu 8 August, Bill Thurston asked about identification of An in its natural
action for n of the order of thousands or tens of thousands.

There is a well known procedure, technically a one-sided Monte Carlo randomized
algorithm, which will identity An in this situation with high probability. If
An is identified, then this identification is correct, but there is a risk of
An being missed due to bad luck, which can be controlled but not, as far as we
know, eliminated at comparably low cost. We are investigating appropriate
ways of dealing with this situation.

This procedure has been known for a long time, but, it seems, was omitted from
GAP4 by an oversight. We have now implemented it. The implementation has
been sent directly to Prof. Thurston, and will be incorporated in the next
release of GAP. If you would find this feature useful in the meantime, please
send email to gap-trouble@dcs.st-and.ac.uk and we would be delighted to send
you the code.

Can I also thank Prof. Thurston for including an indication of the purposes for
which he is using GAP and encourage others to do likewise. It is both
interesting for others to read and helpful to us in understanding user
questions and problems if we have some understanding of the context from which
they arise.

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

> < [top]