[GAP Forum] A permutation group with huge finite orbits

[Alexander Konovalov]

Dear Stefan,

On 12 Nov 2012, at 11:20, Stefan Kohl wrote:

> Dear Forum,
> 
> this is to pose you a little problem, in no way a general question but just
> a nice example -- maybe some of you finds the answer:
> 
> Let r(m) denote the residue class r + mZ of the integers.
> Given disjoint residue classes r1(m1) and r2(m2), let the class transposition
> (r1(m1),r2(m2)) be the permutation of Z which interchanges r1+k*m1 and r2+k*m2
> for every integer k and which fixes all other points.
> 
> Put a := (0(2),1(2)), b := (0(5),4(5)) and c := (1(4),0(6)), and let
> 
>                         G := <a,b,c> < Sym(Z).
> 
> The claims on this group are:
> 
>  1. All orbits under the action of G on Z are finite.
>  2. Except for the orbit of 0, orbits of G coincide with cycles of g := abc.
> 
> None of these has been proved so far, but it is known that all cycles of g
> containing positive integers less than 173176 are finite -- e.g. the cycle
> of 32 has length 6296, the one of 736 has length 495448, and the cycle of
> 25952 has length 245719352 and a maximum of about 10^5759.
> 
> The little problem for you is now to find the length of the cycle of 173176.
> This may require nothing more than a little patience -- but who knows ... !

I've started this computation a week ago, being lured by hopefully little
patience that I may need to have, having no hint from you how much patience 
do I really need ;-). So, after one week, the last line of the output says:

New maximum with 76785 digits reached after 15621898577 iterations. 

Hope this is useful if anybody else would be interested in this problem.
I've stopped it now since the computer must be restarted by some other 
reasons. Is this the new upper bound, or you've already managed to achieve 
a higher number of iterations on your own? How do you know that all cycles 
for smaller positive integers are finite - was it checked with a help of a 
computer?

Thanks,
Alexander




> You may deal with the problem in GAP as follows:
> 
> gap> LoadPackage("rcwa");
> gap> a := ClassTransposition(0,2,1,2);;
> gap> b := ClassTransposition(0,5,4,5);;
> gap> c := ClassTransposition(1,4,0,6);;
> gap> G := Group(a,b,c);
> <rcwa group over Z with 3 generators>
> gap> g := a*b*c;
> <rcwa permutation of Z with modulus 60>
> gap> Length(Cycle(g,32));
> 6296
> gap> Length(Cycle(g,736));
> 495448
> gap> Length(Cycle(g,173176));
> 
> The last command will exhaust the memory of your computer even if it has
> a lot, so I suggest not to store the iterates:
> 
> n := 173176; length := 0; max := n;
> repeat
>  n := n^g;
>  length := length + 1;
>  if n > max then
>    max := n;
>    Print("New maximum with ",LogInt(n,10)+1," digits reached after ",
>          length," iterations.\n");
>  fi;
> until n = 173176;
> Print("The cycle length is ",length,".\n");
> 
> Please let me know if you have any questions or if you find something, and
> 
> Good luck!
> 
>    Stefan
> 
> -----------------------------------------------------------------------------
> http://www.gap-system.org/DevelopersPages/StefanKohl/
> -----------------------------------------------------------------------------
> 
> 
> 
> _______________________________________________
> Forum mailing list
> Forum at mail.gap-system.org
> http://mail.gap-system.org/mailman/listinfo/forum


--
Dr. Alexander Konovalov               School of Computer Science
& Centre for Interdisciplinary Research in Computational Algebra
University of St Andrews                 Tel +44/0 (1334) 461633
http://www.cs.st-andrews.ac.uk/~alexk    Fax +44/0 (1334) 463278
The University of St Andrews is a charity registered in Scotland:No.SC013532