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

Question

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

Answer 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'$)

Answer 2

You say that "the largest cycle contains more than half the elements, whereas the probability for this to happen in a random permutation is roughly $\ln(2)$". But this doesn't account for a thing or two. (1) we can prove there are no 1-cycles, so only derangements on $2^k-2$ need be considered. And (2) maybe we can prove there are no 2-cycles after the $k=2$ case, so we would only need consider permutations lacking a transposition.

Let's just eliminate $1$-cycles for starters. The number of derangements on $2^k-2$ elements is within an integer of $\frac{\left(2^k-2\right)!}{e}$ while the number of $(2^k-2)$-cycles is $(2^k-3)!$. So the probability of a random derangement being a full cycle is about $\frac{e}{2^k-2}$. The exact values for $k=2,3,4,5$ are $1,\frac{120}{265},\frac{479001600}{2467007773},\frac{304888344611713860501504000000}{3364864615063302680426807870189}$. Their product is about $0.00796$, relatively a good deal greater than $\frac{1}{5040}$.

Now if we can prove that there are no $2$-cycles beyond the $k=2$ case then these numbers become a lot larger, roughly $\frac{e^{1.5}}{2^k-2}$ according to OEIS. Then for $k=3,4,5$ we have $\frac{3}{4},\frac{1247400}{3896663},0.149\ldots$, and the product is about $0.035$.

[So far I'm only able to prove there is no $2$-cycle in certain cases, so it's not yet clear that $2$-cycles can be tossed out.]

This has only looked at the probabilities when asking for a full cycle permutation. If we ask for the permutations with a cycle of at least half length, the numbers rise dramatically. For example with $k=3$, once you exclude 1-cycles and 2-cycles, all that is left is 6-cycles and pairs of disjoint 3-cycles. So there is a 100% chance of a random transposition-free derangement having a cycle of at least half-length. For $k=4$, I worked out there is about an 84% chance of a random transposition-free derangement having a cycle of at least half-length.

This effect of excluding singletons (and possibly transpositions) will taper off quickly as $k$ rises. But I think it is a significant factor in raising the odds for this observation to be happening at low $k$.