[GAP Forum] A permutation group with huge finite orbits

[Stefan Kohl]

Dear Alexander,

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

Then you had notably more patience than me -- thanks and congratulations!

-- I stopped the computation after about 5700000000 iterations and a maximum
slightly above 10^40000.

> How do you know that all cycles for smaller positive integers are finite
> - was it checked with a help of a computer?

Yes, I have checked that by computer. -- Most cycles are MUCH shorter!
In any case, checking all cycles for positive integers less than 173176
took altogether MUCH less computing time than even only the 5700000000
iterations I did on the cycle of 173176 -- let alone the 15621898577 you did!!

Short cycles (length <= 100) intersecting nontrivially with [0..100]
are for example:

gap> ShortCycles(g,[0..100],100);
[ [ 0 ], [ 1, 4, 12, 18, 15, 10, 11, 14, 19, 13, 9, 8, 6, 7, 5 ], [ 2, 3 ],
  [ 16, 24, 42, 43, 29, 28, 36, 54, 59, 58, 55, 50, 51, 37, 25, 20, 30, 31,
      34, 39, 38, 35, 21, 17 ], [ 22, 23 ], [ 26, 27 ], [ 46, 47 ],
  [ 52, 78, 75, 70, 71, 74, 79, 53 ], [ 62, 63 ],
  [ 76, 114, 119, 118, 115, 110, 111, 77 ], [ 82, 83 ], [ 86, 87 ],
  [ 92, 138, 135, 130, 131, 134, 139, 93 ] ]

Actually the natural density of the set of integers belonging to cycles
of length <= 24 is at least 47/108. -- To find this, we use that finite
cycles of that particular permutation often (likely: always) come in infinite
series that correspond to cycles on the set of all residue classes of Z:

gap> cycs := ShortResidueClassCycles(g,480,24);
[ [ 2(60), 3(60) ], [ 22(60), 23(60) ], [ 26(60), 27(60) ],
  [ 46(60), 47(60) ],
  [ 52(120), 78(180), 75(180), 70(180), 71(180), 74(180), 79(180), 53(120) ],
  [ 76(120), 114(180), 119(180), 118(180), 115(180), 110(180), 111(180),
      77(120) ],
  [ 92(120), 138(180), 135(180), 130(180), 131(180), 134(180), 139(180),
      93(120) ],
  [ 116(120), 174(180), 179(180), 178(180), 175(180), 170(180), 171(180),
      117(120) ],
  [ 16(480), 24(720), 42(1080), 43(1080), 29(720), 28(720), 36(1080),
      54(1620), 59(1620), 58(1620), 55(1620), 50(1620), 51(1620), 37(1080),
      25(720), 20(720), 30(1080), 31(1080), 34(1080), 39(1080), 38(1080),
      35(1080), 21(720), 17(480) ],
  [ 176(480), 264(720), 402(1080), 403(1080), 269(720), 268(720), 396(1080),
      594(1620), 599(1620), 598(1620), 595(1620), 590(1620), 591(1620),
      397(1080), 265(720), 260(720), 390(1080), 391(1080), 394(1080),
      399(1080), 398(1080), 395(1080), 261(720), 177(480) ],
  [ 232(480), 348(720), 516(1080), 774(1620), 779(1620), 778(1620),
      775(1620), 770(1620), 771(1620), 517(1080), 345(720), 340(720),
      510(1080), 511(1080), 514(1080), 519(1080), 518(1080), 515(1080),
      341(720), 344(720), 522(1080), 523(1080), 349(720), 233(480) ],
  [ 392(480), 588(720), 876(1080), 1314(1620), 1319(1620), 1318(1620),
      1315(1620), 1310(1620), 1311(1620), 877(1080), 585(720), 580(720),
      870(1080), 871(1080), 874(1080), 879(1080), 878(1080), 875(1080),
      581(720), 584(720), 882(1080), 883(1080), 589(720), 393(480) ] ]
gap> time; # quick
203
gap> Density(Union(Flat(cycs)));
47/108

Also finding the lengths of all cycles containing positive integers
less than 1000 takes no more than a few seconds:

gap> CycleRepresentativesAndLengths(g,[0..1000]);
[ [ 1, 15 ], [ 2, 2 ], [ 16, 24 ], [ 22, 2 ], [ 26, 2 ], [ 32, 6296 ],
  [ 46, 2 ], [ 52, 8 ], [ 56, 296 ], [ 62, 2 ], [ 76, 8 ], [ 82, 2 ],
  [ 86, 2 ], [ 92, 8 ], [ 106, 2 ], [ 112, 104 ], [ 116, 8 ], [ 122, 2 ],
  [ 136, 440 ], [ 142, 2 ], [ 146, 2 ], [ 152, 40 ], [ 166, 2 ], [ 172, 8 ],
  [ 176, 24 ], [ 182, 2 ], [ 196, 8 ], [ 202, 2 ], [ 206, 2 ], [ 212, 8 ],
  [ 226, 2 ], [ 232, 24 ], [ 236, 8 ], [ 242, 2 ], [ 256, 56 ], [ 262, 2 ],
  [ 266, 2 ], [ 272, 408 ], [ 286, 2 ], [ 292, 8 ], [ 296, 104 ], [ 302, 2 ],
  [ 316, 8 ], [ 322, 2 ], [ 326, 2 ], [ 332, 8 ], [ 346, 2 ], [ 352, 264 ],
  [ 356, 8 ], [ 362, 2 ], [ 376, 1304 ], [ 382, 2 ], [ 386, 2 ], [ 392, 24 ],
  [ 406, 2 ], [ 412, 8 ], [ 416, 200 ], [ 422, 2 ], [ 436, 8 ], [ 442, 2 ],
  [ 446, 2 ], [ 452, 8 ], [ 466, 2 ], [ 472, 104 ], [ 476, 8 ], [ 482, 2 ],
  [ 496, 24 ], [ 502, 2 ], [ 506, 2 ], [ 512, 696 ], [ 526, 2 ], [ 532, 8 ],
  [ 536, 3912 ], [ 542, 2 ], [ 556, 8 ], [ 562, 2 ], [ 566, 2 ], [ 572, 8 ],
  [ 586, 2 ], [ 592, 888 ], [ 596, 8 ], [ 602, 2 ], [ 616, 728 ], [ 622, 2 ],
  [ 626, 2 ], [ 632, 2776 ], [ 646, 2 ], [ 652, 8 ], [ 656, 24 ], [ 662, 2 ],
  [ 676, 8 ], [ 682, 2 ], [ 686, 2 ], [ 692, 8 ], [ 706, 2 ], [ 712, 24 ],
  [ 716, 8 ], [ 722, 2 ], [ 736, 495448 ], [ 742, 2 ], [ 746, 2 ],
  [ 752, 1272 ], [ 766, 2 ], [ 772, 8 ], [ 776, 376 ], [ 782, 2 ],
  [ 796, 8 ], [ 802, 2 ], [ 806, 2 ], [ 812, 8 ], [ 826, 2 ], [ 832, 120 ],
  [ 836, 8 ], [ 842, 2 ], [ 856, 2264 ], [ 862, 2 ], [ 866, 2 ], [ 872, 24 ],
  [ 886, 2 ], [ 892, 8 ], [ 896, 132760 ], [ 902, 2 ], [ 916, 8 ],
  [ 922, 2 ], [ 926, 2 ], [ 932, 8 ], [ 946, 2 ], [ 952, 456 ], [ 956, 8 ],
  [ 962, 2 ], [ 976, 24 ], [ 982, 2 ], [ 986, 2 ], [ 992, 1064 ] ]
gap> time;
2824

I still think that likely all cycles are finite --
if my understanding of it is right, besides the regularities mentioned above,
cycles behave in some sense roughly like a simple random walk on Z, and are
finite if the random walk is recurrent. In this "model", +1 in the random walk
on Z roughly corresponds to multiplication by some constant, and -1 corresponds
to division by that constant. If that describes cycles of g in a satisfactory
way, that means of course also that cycles may sometimes be pretty long --
for example if a random walk on Z has reached a value in the 100000's, it
usually takes a while until it gets back to 0 for the next time ... .

Proving finiteness of all cycles may be pretty hard, however.

Best wishes,

    Stefan