Why do the triangular numbers initially form long cycles mod $2^k$?

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

Solution 1:

This is a nice question, thank you for anyone who reopened it.
If the calculation of Mr Joriki is correct, there is a case (say $k=19$ ) where the length of the longest cycle does not exist $\dfrac{2^k}{2}$. So I guess it is not a good lower bound for all $k$, I cannot say much about the situations in which $k$ is sufficiently large).
Here, by this post, I'll give an elementary explanation for :

• Why the length of the longest cycle goes to infinity when $k$ get larges? and in fact, I'll give a lower bound of order $O(k) $

Explosion of the length of the longest cycle

For $k\ge 2$
Let :

• $T(n)$ is the respective $n-th$ triangular numbers, that is $T: n \longmapsto \dfrac{n(n+1)}{2}$
• $ord(x)$ denote the length of the orbit of $T$ by the mapping $T$, that is: $ord(x)$ is the smallest number $m \ge 1$ such that :$T^m(x)=x \mod 2^k$
  
• $n,m$ be two postive integer such that $k>n$ and $2(n-m+1) \ge k+1$ (1) and $2^{k-n} > m$ (2)

Then, for any integers $x, s $ , we have: $$\begin{equation} T(x+s2^n)=T(x)+\underbrace{(2x+1)}_{A_1} s2^{n-1} \mod 2^k \\ T^2(x+s2^n)= T(x)+\underbrace{(2x+1)(2T(x)+1)}_{A_2}s2^{n-2} \mod 2^k \\ ... \\T^m(x+s2^n)=T(x)+A_ms2^{n-m} \mod 2^k \end{equation} $$ for $A_m= (2x+1)(2T(x)+1)...\left(2T^{m-1}(x)+1\right)$

Remark: The inequality (1) is just here to make sure all the equations above hold. We will not revisit them until the last step.

From the above identities, we see the following lemma which is also the centre of my demonstration.
Lemma
If $s$ is an integer in $[0,2^{k-n})$, one of the following assertions is wrong:

• $ord(x)$ and $ ord(x+s2^{n})$ are not bigger than $m$
• $ord(x)=ord(x+s2^n)=u$
  

Proof
If both are true, we can imply that: $$x+s2^{n}= T^u(x+s^{n})=T^u(x)+A_us.2^{n-u}=x+A_us2^{n-u} \mod 2^k$$ $$\longleftrightarrow s2^n= A_us2^{n-u} \mod 2^k$$ which is wrong because $A_u$ is an odd number and $s$ is a nonnegative integer not exceeding $2^{k-n}$.

Now back to our quest of finding the lower bound.
Assume that for all integer $y \in \{0,1,2,...,2^k-1\}=: B$ , $$ord(y) \le m$$ For any nonnegative integer $x$ such that $0 \le x < 2^n$, let us consider the following set: $$C:=\{ x+s2^n | 0 \le s < 2^{k-n} \}$$ Clearly,

• $C \subset B$
• $ \#C = 2^{k-n}$
• $1 \le ord(y) \le m $ for all $y \in C$

Because $2^{k-n}>m$ (condition (2)), then by Directlet's principle, there are two elements $y_1,y_2 \in C$ such that $ord(y_1)=ord(y_2)\le m$.
Which is wrong thanks to our above lemma

So for all $n,m$ which sastify our condition (1) and (2), there must be an integer $y \in [0,2^{k-1})$ such that: $ord(y) \ge m+1$

So our longest cycle must have the length of at least $m+1$
Besides, we see that for $k$ big enough, $n=\dfrac{3k}{5}$ and $m=k/10$ sasitify our conditions (1) and (2). So:
Conclusion
For $k$ big enough (say, from $k \ge 10$ on), the length of our longest cycle has a $k/10$ as lower bound.
Discussion

• In fact, there are some freedoms in our solution that may promise a better bound.
• $T$ is a very interesting function as one may easily think that $T(x+2^k)=T(x) \mod 2^k$ though, in fact, it is wrong.
• The same procedure can be applied to other polynomials $Q$ in $\mathbb{Q}[X]$ than $T$ and other numbers $a$ than $2$ to achieve the lower bound of order $O(k)$ for the longest cycle. (Just with some good relation between $a$ and $Q'$)