As discussed at Triangular numbers ($\text{mod } 2^n$) as a permutation of $\{0,1,2,\dots,2^n-1\}$ and What is the set of triangular numbers mod $n$?, mapping the integer $n$ for $0\le n\lt2^k$ to the residue of the corresponding triangular number $\frac12n(n+1)$ modulo $2^k$ yields a permutation. For example, for $k=3$:
$$ 01234567\\ 01362754 $$
I noticed that up to $k=5$, all elements except for $0$ and $1$ (which are always mapped to themselves) form a single cycle of length $2^k-2$. The probability for a uniformly random permutation of length $n$ to consist of a single cycle is $\frac1n$, so if these permutations (excluding $0$ and $1$) could be considered uniformly random, the probability for this to happen would be only $\frac12\cdot\frac16\cdot\frac1{14}\cdot\frac1{30}=\frac1{5040}$. That was reason enough to check whether the pattern continues for greater $k$.
It turns out that it doesn't, as for $k=6$ there is a $3$-cycle: $(4,10,55)$. Nevertheless, at first unusually large cycle lengths persist: For all $k$ from $2$ to $12$, except for $k=7$, the largest cycle contains more than half the elements, whereas the probability for this to happen in a random permutation is roughly $\ln 2$. In fact, in $9$ of these $11$ cases (all except $k=6$ and $k=7$), the largest cycle contains more than $\frac45$ of the elements; the probability for that is roughly $\ln\frac54\approx0.223$ per case, so the probability for it to happen at least $9$ times out of $11$ is only $\sum_{k=9}^{11}\binom{11}k\left(\ln\frac54\right)^k\left(1-\ln\frac54\right)^{11-k}\approx5\cdot10^{-5}$.
However, this pattern, too, doesn't continue: For $k$ from $2$ to $30$, there are $21$ cases with cycles of more than half the elements, which is about the expected number $29\ln2\approx20.1$; and for $k$ from $13$ to $30$ there are only $4$ cases with cycles of more than $\frac45$ of the elements, which is almost exactly the expected number $18\ln\frac54\approx4.0$.
My question is: Is there an explanation for this initial tendency to form long cycles? Or should we put it down to coincidence?
For your convenience, here's the code I used to find the cycle lengths, and here are the results up to $k=30$:
4 : 2
8 : 6
16 : 14
32 : 30
64 : 40, 19, 3
128 : 55, 48, 14, 6, 3
256 : 247, 4, 3
512 : 488, 7, 6, 6, 3
1024 : 818, 157, 47
2048 : 1652, 371, 23
4096 : 4060, 25, 9
8192 : 3754, 3609, 412, 321, 79, 12, 3
16384 : 15748, 292, 190, 71, 24, 22, 13, 13, 9
32768 : 20161, 11349, 333, 305, 281, 218, 72, 44, 3
65536 : 20128, 17231, 16759, 8072, 2377, 579, 295, 60, 33
131072 : 85861, 26603, 9389, 3887, 3365, 682, 594, 488, 118, 49, 23, 6, 5
262144 : 159827, 89991, 5749, 5465, 592, 231, 118, 100, 42, 24, 3
524288 : 211265, 176243, 59029, 35639, 28496, 6122, 4245, 1239, 713, 632, 244, 146, 133, 59, 39, 36, 6
1048576 : 620076, 216520, 131454, 68118, 7535, 2111, 1235, 1028, 225, 213, 36, 20, 3
2097152 : 993084, 583840, 394263, 87941, 31835, 3389, 1648, 459, 306, 273, 45, 35, 14, 10, 8
4194304 : 1487646, 1119526, 942359, 429054, 118037, 64446, 28806, 3238, 323, 291, 186, 126, 118, 102, 12, 11, 10, 7, 4
8388608 : 2542051, 2462220, 2040680, 1138236, 93072, 45880, 19664, 16473, 14243, 6319, 2917, 2598, 2160, 1414, 514, 118, 23, 19, 5
16777216 : 12137774, 4004239, 271250, 253890, 43860, 33597, 25495, 4132, 2575, 157, 116, 67, 35, 9, 8, 6, 4
33554432 : 28169497, 2552414, 1401622, 1019221, 356682, 21006, 14735, 10242, 8223, 566, 135, 45, 21, 15, 6
67108864 : 32223531, 29360424, 3530597, 932310, 809707, 99109, 83093, 67418, 1612, 364, 248, 248, 166, 21, 14
134217728 : 87591110, 34361487, 3360928, 3343185, 3291274, 1345478, 353498, 323522, 158252, 47767, 17776, 11159, 5927, 2681, 2343, 530, 235, 208, 162, 84, 59, 31, 30
268435456 : 232647749, 24918738, 5559122, 3742461, 525140, 384941, 278834, 197080, 62977, 48736, 21684, 16632, 13525, 8993, 3073, 2721, 1625, 1262, 153, 5, 3
536870912 : 379598603, 129063661, 26279056, 665648, 483286, 222289, 137686, 106713, 94323, 80276, 59199, 41767, 15498, 10615, 5066, 2816, 2699, 1579, 113, 10, 7
1073741824 : 877039442, 181409872, 7571387, 6549459, 921247, 240525, 3924, 3416, 1602, 894, 54
from Hot Weekly Questions - Mathematics Stack Exchange
Post a Comment