a question about the Collatz conjecture (relation of smallest number in a cycle and minimal cycle-length)

Question

I've only done a bit of research on the current findings, not sure if anyone here can answer this.

Q1: I just haven't been able to find,

• has it been shown yet that a it is impossible for a loop to exist,
• and for a counter example to exist does it have to grow to infinity?

Q2: I've seen that all numbers up to 2^60 have been checked, and using this information I'm able to show that no loops exist of length 101 or less (as a lower bound).

Has something like this been shown before? I just can't seem to find much information on it.

Answer 1

It has neither been shown that a loop other than the trivial $\{4,2,1\}$ does not exist, nor that there exists a trajectory that grows to infinity.

Answer 2

On Q1: @Klangen has already answered.
On Q2: That has been done, at least since R.Crandall's study in 1978.

There is an easy formula how you can disprove loops of the length of N (odd numbers) from the knowledge, that no number $a_1 < \chi$ can be member of a nontrivial loop (since they've all checked up to some limit $\chi$, which by the time seem to be $\chi_{\small 2019}=87 \cdot 2^{60}$ ). That process is very simple and can be done for instance with Pari/GP in few lines of code.

Here the first few $N$ can be used to determine, that for loop-length $N$ (odd numbers) the minimal element $a_1$ must be smaller than some $\chi$. If $\chi$ is our upper limit of all consecutive numbers $a$ checked to be convergent, a loop of this length $N$ cannot occur (the number $S$ in the table is the number of divisions by $2$):

for(N=2,30,S=ceil(N*ld3);a_mean=(2^(S/N)-3);if(a_mean>1e-1,next()); print("N=",N," S="S,," a_1 <", 1/a_mean))

N=5 S=8 a_1 <31.81356435
N=8 S=13 a_1 <11.84530260
N=10 S=16 a_1 <31.81356435
N=13 S=21 a_1 <15.64144437
N=15 S=24 a_1 <31.81356435
N=16 S=26 a_1 <11.84530260
N=17 S=27 a_1 <146.7715891
N=18 S=29 a_1 <18.22480824
N=19 S=31 a_1 <10.15029702
N=20 S=32 a_1 <31.81356435
N=21 S=34 a_1 <13.94273766
N=22 S=35 a_1 <80.70304398
N=23 S=37 a_1 <20.09651637
N=24 S=39 a_1 <11.84530260
N=25 S=40 a_1 <31.81356435
N=26 S=42 a_1 <15.64144437
N=27 S=43 a_1 <62.86002764
N=28 S=45 a_1 <21.51503268
N=29 S=46 a_1 <386.2846256
N=30 S=48 a_1 <31.81356435

I stopped the output here, but for $N \le 100$ the upper bound for $a_1$ is very small, much smaller than the current known $\chi_{2019}$.
Here we proceed simply to $2 \le N \le 3000$ and document only that $N$ where the upper bound for $a_1$ is at least $1e5$

for(N=2,3000,S=ceil(N*ld3);a_mean=(2^(S/N)-3);if(a_mean>1e-5,next()); print("N=",N," S="S,," a_1 < ", 1/a_mean, " ~ 2^", floor(-log(a_mean)/l2)))

N=971 S=1539 a_1 < 330749.4970 ~ 2^18
N=1277 S=2024 a_1 < 212745.4992 ~ 2^17
N=1583 S=2509 a_1 < 174546.8464 ~ 2^17
N=1636 S=2593 a_1 < 583287.1405 ~ 2^19
N=1889 S=2994 a_1 < 155653.6267 ~ 2^17
N=1942 S=3078 a_1 < 330749.4970 ~ 2^18
N=2195 S=3479 a_1 < 144382.7969 ~ 2^17
N=2248 S=3563 a_1 < 251503.8361 ~ 2^17
N=2301 S=3647 a_1 < 860563.0163 ~ 2^19
N=2501 S=3964 a_1 < 136895.8416 ~ 2^17
N=2554 S=4048 a_1 < 212745.4992 ~ 2^17
N=2607 S=4132 a_1 < 454137.6774 ~ 2^18
N=2807 S=4449 a_1 < 131561.1466 ~ 2^17
N=2860 S=4533 a_1 < 189759.9235 ~ 2^17
N=2913 S=4617 a_1 < 330749.4970 ~ 2^18
N=2966 S=4701 a_1 < 1166399.316 ~ 2^20

The largest upper bounds relative to $N$ occur at convergents of the continued fraction of the $\log_2(3)$ . Here is a table only for $N$ from this set of first 30 convergents. At the somehow famous $N=397573379$ the upper bound for $a_1$ is approx $2^{60}$ so up to until recent years a cycle with that length $N$ could not be excluded with this simple formula alone. The more recently considered length $N=6586818670$ with $a_1 < 2.168901553 E20 \approx 2^{67}$ has been excluded by the yoyo@home-project in 2017 (if I've that correctly in mind):

for(k=2,30,N=cvgts[2,k];S=ceil(N*ld3);a_mean=(2^(S/N)-3);if(a_mean>1e-5,next()); print("N=",N," S="S,," a_1 < ", 1/a_mean, " ~ 2^", floor(-log(a_mean)/l2)))

N=15601 S=24727 a_1 < 285817586.2 ~ 2^28
N=79335 S=125743 a_1 < 7216102493. ~ 2^32
N=190537 S=301994 a_1 < 9.845728110 E11 ~ 2^39
N=10590737 S=16785922 a_1 < 5093068.134 ~ 2^22
N=10781274 S=17087915 a_1 < 2.944018243 E14 ~ 2^48
N=53715833 S=85137582 a_1 < 25831855.26 ~ 2^24
N=171928773 S=272500658 a_1 < 3.203055713 E16 ~ 2^54
N=225644606 S=357638240 a_1 < 108512118.1 ~ 2^26
N=397573379 S=630138897 a_1 < 1.252079477 E18 ~ 2^60   ****************
N=6189245291 S=9809721695 a_1 < 2976397830. ~ 2^31
N=6586818670 S=10439860591 a_1 < 2.168901553 E20 ~ 2^67  ***************
N=65470613321 S=103768467014 a_1 < 3.148470972 E10 ~ 2^34
N=137528045312 S=217976794617 a_1 < 5.101255583 E22 ~ 2^75
N=753110839881 S=1193652440099 a_1 < 3.621697580 E11 ~ 2^38
N=5409303924479 S=8573543875303 a_1 < 2.734923048 E25 ~ 2^84
N=6162414764360 S=9767196315402 a_1 < 2.963495073 E12 ~ 2^41
N=11571718688839 S=18340740190704 a_1 < 2.990877298 E26 ~ 2^87
N=52449289519716 S=83130157078218 a_1 < 2.522277663 E13 ~ 2^44

Answer 3

Reformulate the Collatz iteration in a compact form as

(1) $v_n = z_n + 2^{2n+1-r}m_r$

for any input $u \in 2\mathbb{N}+1 \not \equiv 0\pmod{3}$ such that $u=3m_r+r$ where $r=1$ if $u \equiv 1\pmod{3}$ or $r=2$ if $u \equiv 2\pmod{3}$ and $z_n = \sum_{i=1}^{n} 2^{i-1}$ for $n \in \mathbb{N}$. Iterating (1) by one step for each $n \in \mathbb{N}$ yields an infinite set $\{v_n\}_{n \in \mathbb{N}}$, termed sibling set, arising from parent $u$. Suppose we consider $u$ and $v_n$ as vertices connected by edge $(u, v_n)$ from $u$ to $v_n$ for every $n \in \mathbb{N}$. Then starting with $u_0=1$, repeatedly iterating (1) constructs an arborescence graph $G=(V,E)$ that is the union of infinitely many sibling sets, with root at $r_0$, vertex set $V$ and edge set $E$, as shown here. Every path of any length from the root in $G$ represents an odd Collatz sequence in reverse. It can be shown that every vertex in $G$ is unique and that $V=2\mathbb{N}+1$, i.e. $V$ exactly covers the set of odd natural numbers. Since $G$ is weakly connected, then we infer that: (i) only the trivial loop exists (but is necessarily ignored in $G$) and (ii) every odd Collatz sequence always converges to $1$ (hence, cannot diverge). These results, subject to further scrutiny, answer both questions under Q1 above.