[GAP Forum] A permutation group with huge finite orbits

Stefan Kohl stefan at mcs.st-and.ac.uk
Mon Nov 12 11:20:19 GMT 2012


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 ... !

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/
-----------------------------------------------------------------------------





More information about the Forum mailing list