I was thinking about the Collatz Conjecture yesterday, and as opposed to trying to prove it, I was considering what would make the conjecture false. There were only two cases I could think of:
- We find a number that begins a sequence that trends out to infinity ($3n+1$ dominates the $\frac{n}{2}$)
- We encounter a sequence of numbers that always results in itself/a completely isolated sequence.
I would assume the primary contradiction to look for would be number one, but what sort of research could be done into the second idea? Is the second idea even possible?
Are there any other failures of the Collatz Conjecture that I haven't thought of?
Best Answer
In the "syracuse"-formulation of the collatz-transformation $T:= a_{n+1}={3a_n+1 \over 2^{A_n}}$ on odd a where $A_n$ is the greatest value that keeps $a_{n+1}$ integer we can eleganly write a formula to approach the cycle-problem.
Let's write in the following example $a,b,c,...$ for $a_1,a_2,a_3,...$ and $A,B,C,...$ for $A_1,A_2,A_3,...$ then we have for the example-assumtion of a 3-step-cycle $$ b= {3a+1\over2^A} \qquad c= {3b+1\over2^B} \qquad a= {3c+1\over2^C} \qquad $$ and the equation must hold: $$ bca = \left({3a+1\over2^A}\right)\left({3b+1\over2^B}\right)\left({3c+1\over2^C}\right)$$ Reordering gives the "critical equation" for the general cycle problem (it is obvious how it can be extended to as many assumed steps as wished?) with $S=A+B+C+...$ and $N=(number-of-steps)$ $$ 2^S = \left(3+{1\over a}\right)\left(3+{1\over b}\right)\left(3+{1\over c}\right) \\ =3^N \left(1+{1\over 3a}\right)\left(1+{1\over 3b}\right)\left(1+{1\over 3c}\right) $$ One can immediately see, that the S must be so that a perfect power of 2 is slightly greater then the N 'th perfect power of 3. But we find empirically, that perfect powers of 2 and 3 are not very near - so the parentheses must be big and thus the elements $a_k$ of the cycle must be small ! You might try to find yourself possible $a,b,c$ for an assumed 3-step cycle which gives the critical equation
$$ 32 = 27 \left(1+{1\over 3a}\right)\left(1+{1\over 3b}\right)\left(1+{1\over 3c}\right) $$ and only assuming the most general facts, that $a,b,c$ are all odd, distinct and not divisible by 3. Can you disprove the 3-step-cycle?
Well, since we know, that all $a_k \lt 2^{50} $ are not member of a cycle, the fractions in the parentheses are very small and we need a lot of parentheses and thus a high N, to increase $3^N$ to the next perfect power $2^S$ - by this formula we can derive a general lower bound for the number of steps required given a lower bound for the elements of the cycle $a_k$ .
This "critical equation" does not suffice for the disproof of cycles alone, because for any lower bound of a we can find a lower bound of N which lets the rhs reach and "overtake" the next perfect power of 2. The next step of possible research seems then to re-introduce the remaining modular requirements on subsequent $a_k$ . There has been real progress on the general "critical equation" assuming certain structures in the $a_k$, namely that of an "1-cycle" and "m-cycle" structure, specific simple and restricted forms of assumed cycles, which could then be disproved by the known distance-characteristic of powers of 2 to powers of 3, using the continued fraction of $\log(3)/ \log(2)$ and theory of rational approximation of linear forms in logarithms.
(See the wikipedia article where I also linked to online available articles of John Simons and Benne de Weger. The basic article of Ray Steiner is unfortunately not freely available online - this is really a grief!)