Question regarding 1-cycles in the Collatz conjecture

collatz conjectureelementary-number-theoryproblem solving

The question is whether there is a simple explanation for the following observation, or whether the observation is an incorrect inference from limited cases. The context assumes 1-cycle loops in the Collatz conjecture (I know that Steiner proved that there are no 1-cycles; I am thinking about an old question from a distinguished reader regarding any approaches that do not require sophisticated relations among transcendental numbers or advanced theorems).

Assumptions:

(1) A loop of n elements, {$X_1, X_2,…X_n$} can be characterized by the equation $$\frac{3^n-2^n}{2^m-3^n}=X_1$$

(2) m is not free but is limited to integers that satisfy $nLog_2{3}<m<nLog_2{3}+1$.

(3) Every $X_i$ in the loop is associated with a number $b_i$ where $$\frac {b_i}{2^m – 3^n} = X_i$$

(4) For a 1-cycle, $b_1$ = $3^n – 2^n$

(5) For a 1-cycle, the $b_i$ are related by $$b_{i+1} = \frac {3}{2} * b_i + \frac {2^m – 3^n}{2}$$

Inferences:

(6) From (3) every $b_i$ must be divisible by $2^m – 3^n$.

(7) If two numbers a and b are divisible by d, then a-b is divisible by d.
Since the differences are divisible by d then the differences of the differences must be divisible by d, etc.

Observation:

(8) If we compute the appropriate values $b_i$ for a given n (and consequently by assumption (2), a pair {m,n}), then take the differences between consecutive $b_i$, then the differences of the differences, etc., we can construct tables such as the following:

For n=5 and m=8:

$b_i$	1st diff	2nd diff	3rd diff	4th diff
211
323	112
491	168	56
743	252	84	28
1121	378	126	42	14

Following the same procedure for n=8, m=13 and we get:

$b_i$	1st diff	2nd diff	3rd diff	4th diff	5th diff	6th diff	7th diff
6305
10273	3968
16225	5952	1984
25153	8928	2976	992
38545	13392	4464	1488	496
58633	20088	6696	2232	744	248
88765	30132	10044	3348	1116	372	124
133963	45198	15066	5022	1674	558	186	62

For n = 9 and m = 15 the last element is 126.

(9) The last element in the table is equal to $2^{m-n+1} – 2$

(10) The diagonal starting from the last element of the table and working backward proceeds in multiples of 2.

(11) The last row, starting from the last value, proceeds backward in multiples of 3.

(12) Stating from the last element we can fill out the table up to the first column. We can do this, for the ith column, 1 < i < n, by either by adding terms from the $i+1$ column to the diagonal elements that vary by factors of 2, or by subtracting terms from the $i+1$ column from the last row of the table, which vary by factors of 3. If we know the first element of the first column, we can fill out the rest by adding the terms in the second column.

(13) For the pair n=7, m=12 the difference is 5, the same for the pair n=8, m=13. The last element in the tables for each is 62.

(14) It would seem that any function in which the elements of the first column are related to each other in an orderly way will produce an orderly table; for example, if we start with the Fibonacci sequence, even if we start somewhere in the middle, the table will reproduce the earlier terms in the sequence:


21
34	13
55	21	8
89	34	13	5
144	55	21	8	3

Questions:

(14) Is it true that the last term in the 1-cycle related tables should be $2^{m-n+1} – 2$ for all permissible {n,m} pairs? By permissible I mean those which satisfy (2).

(15) If the answer to (14) is true, is there a straight-forward explanation for this?

(15) By (6) and (7) it would seem that every entry a given table would have to be divisible by $2^m – 3^n$ in order for there to be a 1-cycle. (Obviously 211 in the table for n=5 is a prime number, so there are no 5 element 1-cycles.) Is this true?

(16) Since all $b_i$ are odd numbers, and $2^{m-n+1} – 2$ is an even number, does this imply that $2^m – 3^n$ should also divide $2^{m-n} -1$, assuming that that the other assumptions regarding 1-cycles are satisfied?

(17) And I guess I should throw in, are any of the assumptions wrong as applied to 1-cycles in the Collatz conjecture?

(18) Any suggestions as to how to go about searching for answers to these on the internet?

ADDENDUM:

Thank you to Collag3n, Eric Shumard and Gottfried Helms. You are all very helpful. I didn't quite follow all of the math, but I did notice this in Mr. Shumard's response:

"from which $(2^{Pn}−3^n)|(2^{Pn−n}−1)$ follows", and from Collag3n's response:

"so in the end $2^m-3^n\nmid2^{m-n}-1$"

(19) So is this the kind of contradiction that demonstrates that there can be no 1-cycles?

Final Observations

(20) The equation given in (1) completely characterizes a 1-cycle for a given n; that is, given n we can compute all of the $X_i$ in the loop. This is because there is a one-to-one relationship between m and n for 1-cycles. This is not necessarily the case for any k-cycles other than 1. However, equations for the first 2 $b_i$ do completely describe these cycles, because the last term of the equation for $b_2$ is $2^{m-1}$.

(21) In finding values in the difference table that are not divisible by $2^m-3^n$ we can do consecutive divisions by 2 until we reach an odd number, rather than taking the difference of even numbers. The smallest difference between any two numbers in the difference table will then be an odd number which will have to be divisible by $2^m-3^n.$ This is true for any k-cycle or combination of k-cycles.

(22) For a 2-cycle, if it is possible to show that every difference table produces a number that is not divisible by $2^m – 3^n$, considering only those $b_i$ up to the point where $X_i > X_{i+1}$, i.e., the "break in the ascending sequence of the cycle, then there can be no 3-cycles, nor any other k-cycles, since the element of the difference table that precludes a 2-cycle will also be present in the difference table for higher order cycles. One may get away with including $b_{i+2}$ in computing the difference table.

Best Answer

Yes, you should have $2^m-3^n|2^{m-n}-1$ since $X_1+1=\frac{2^m-3^n+3^n-2^n}{2^m-3^n}=\frac{2^m-2^n}{2^m-3^n}$ and the denominator is odd so you can ignore the power of 2 in the numerator for the divisibility.

Notice that since $m<2n$ you can see that $2^{m-n}-1<2^n$, but we know (with Rhin's bound and for $n>5$) that $2^m-3^n>2^n$ so in the end $2^m-3^n\nmid2^{m-n}-1$

Also, I didn't try it myself, but it made me think of this Mathlologer video. Perhaps something you would want to explore: https://youtu.be/4AuV93LOPcE?t=2042

Related Solutions

[Math] $5n+1$, $3n-1$ problem, smallest repeating cycle and Collatz conjecture

If you take $k=2^m-1$, then the $kn+1$ problem maps $$1 \mapsto 2^m \mapsto 2^{m-1} \mapsto \cdots \mapsto 1.$$ In this case, the cycle length is $O(\log k)$. This is significantly different to $2k$. (A similar construction works for the $kn-1$ problem.)

[Math] Intuition behind lack of cycles in the Collatz Conjecture

Consider the "compacted" formula (as also used in the "Syracuse"-version of the Collatz), defining one "step" beginning on $a$ going to $b$ (both odd $\ge 1$): $$ b = {3a+1\over 2^A } \tag 1$$ where $A$ contains the number of halving-steps.

Now to have a (very) simple cycle of just one step we must have: $$ a = {3a+1\over 2^A } \tag 2$$ It is simple to show, there is no solution except when $a=1$ only by rearranging: $$ a = {3a+1\over 2^A } \\ 2^A = {3a+1\over a } $$ $$ 2^A = 3+{1\over a } \tag3\\ $$ and having the rhs a perfect power of $2$ requires $a=1$, thus allowing (only) the well known "trivial" cycle $1 \to 1$.

Now extending this to a two-step cycle we need to have $$\begin{array}{} b = {3a+1\over 2^A } & a = {3b+1\over 2^B }\\ \end{array} \tag 4$$ with some so far undetermined $A$ and $B$.
To see better the space of possible solutions we can take the product of the lhs's $a \cdot b$ and which must equal the product of the rhs's: $$\begin{array}{} a \cdot b = {3a+1\over 2^A } \cdot {3b+1\over 2^B } \end{array}$$ resulting in the required equality

$$\begin{array}{} 2^{A+B} = (3+{1\over a}) \cdot (3+{1\over b }) \end{array} \tag 5$$ This shows, we can only have a solution if the rhs becomes at least integer, which is difficult enough , but actually must even equal a perfect power of 2, larger than $3^2=9$ and namely must equal $16$. Now what values must $a,b$ have such that the rhs equals $16$? Both must contain $a=b=1$ and that is the already known trivial cycle, and no other solution in possible.

Now you see the pattern, how this generalizes to the disproof of the 3-step-cycle, 4-step-cycle, and so on for the N-step-cycle.

Unfortunately, for several $N$ the possibility for small $a,b,c,...$ exists "theoretically", which means, that the rhs-product can reach a perfect power of 2 by some $1 \lt (a_1 \ne a_2 \ne a_3 \cdots \ne a_N)$ - one might just try some $N$ by hand, remembering the conditions that all members of an assumed cycle should be greater than $1$, should be odd, should not be divisible by $3$ and that all involved $a_k$ should be different from each other, to get a better intuition.

Now to proceed more we introduce the knowledge, that by simple heuristics we already know, that $a_k \gt 1000$ (can be done manually with a programming language) or $a_k \gt 1 000 000 $ and even $a_k \gt 2^{60} $ (the latter by an extensive numerical search by de Oliviera and by Rosendaal).
If we introduce that knowledge and assume the minimal $a_1$ being, say $a_1=1+2^{60} $ , $a_2 = {3a_1+1\over 2^{A_1}} $ and so on , we find that for all manually reachable $N$ the rhs is disappointingly near to the value of $3^N$ and no perfect power of $2$ is only in any realistic distance from that. One can find, using the continued fraction of $\beta = \log(3)/\log(2)$, we need $N \gt 150 000 $ (or even much more don't have the actual value at hand).

Well, this shall just give an intuition as to why cycles are much unlikely.
If you like to do more, allow negative numbers for $a_1,a_2,...$ and see how and which solutions for small $N$ you can get.

Or proceed and compare the $5x+1$ problem with this: we find actually two or three possible cycles for small $N$ and $a_1 \lt 100 $ but after that the above method can be used to say much more about the nonexistence of certain $N$-step cycles. I've even found two cycles for the $181 x+1$-version having $N=2$ and small $a_1 \lt 100$ but after that, the formula comparing the rhs-product for $N$ steps to perfect powers of $2$ indicates the same "difficulty" for cycles to exist.

[Update] Just to have an example, how a (possibly infinite, don't know at the moment) set of $N$ can be ruled out for a solution to exist.
Assume for example $N=12$. So we have on the rhs 12 parentheses of the form $(3+1/a_k)$, whose product should equal $2^S$ (where I use in general the letter $S$ for $S=A_1+A_2+...A_{12}$, just the sum of exponents, which is also the number of even-steps). Then what is the next possible perfect power of 2 above $3^{12}$? we get, using $\beta=\log(3)/ \log(2)$: $S=\lceil N \cdot \beta \rceil = 20$,thus we have the condition $$2^{20} =(3+ {1\over a_1})(3+ {1\over a_2})...(3+ {1\over a_{12}}) \tag 6$$and the solution for smallest $1 \ne (a_1 \ne a_2 ... \ne a_{12})$ is $$2^{20} \overset?=(3+ {1\over 5})(3+ {1\over 7})(3+ {1\over 11})...(3+ {1\over 37}) \tag 7$$ Of course we could simply compute the values of the LHS and the RHS getting $$ 2^{20}= 1048576 \gt 697035.738776 $$ and because increasing the values for the $a_k$ would even decrease the value of the rhs there is no solution and thus no $N=12$-step cycle. But for the sake of generality we proceed differently.
Instead we do a rough estimate for the mean-value of the $a_k$. Assume all $a_k$ are equal to their "mean" $a_m$, then we can rewrite the equation $$ 2^S = (3+{1\over a_m})^N \\ 2^{S/N} = (3+{1\over a_m})\\ 2^{S/N} -3 = {1\over a_m}\\ {1 \over 2^{S/N} -3} = a_m \tag 7 $$ $$ a_m = {1 \over 2^{20/12}-3}\approx 5.72075494219... \tag 8 $$ and because $a_m$ is somehow a rough mean, some $a_k$ must be smaller and some must be larger. But there is only one possible value for any $a_k \lt a_m$ namely $a_1=5$. After that, rearranging one parenthese with that value assumed to the lhs in eq(6) we get $$ 2^S/(3+1/5) = (3+{1\over a_m})^{N-1} \\ 2^{20} \cdot 5/16 = (3+{1\over a_m})^{11} \\ a_m \approx 5.79638745091$$ and we find, that there is no way that $a_m$ can be a rough mean of the remaining $11$ $a_k$ since there is no more odd integer $a_k$ in $1 \ne 3 \ne 5 \lt a_k $ so a $N=12$-step-cycle cannot exist.
We see nicely, that for some $N$ we can exclude the possibility of a cycle just based on the basic assumptions on the form of the members of a possible cycle $a_k$ by the formula (6) and for such $N$ do not need to recurse to the $a_k \gt 2^{60}$ found by de Oliviera and Rosendaal.

However, and this leads to the observation that we need for the general solution of the cycle-problem some deeper thinking, there are some $N$ for which $2^S$ is comfortably near to $3^N$ so we can allow a set of small $a_k$ such that the rhs can approach the lhs. The continued fraction of $\beta$ gives us pairs of $N$ and $S$ where $2^S$ are especially near to $3^N$ and for which a cycle cannot be excluded by this method alone.

[update 2]
I've not done this before explicitely, but trying the continued fraction-convergents and filling into $a_k$ the set of consecutive smallest possible integers ($5,7,11,13,...)$ we get the following small table

N           S      lhs=2^S            rhs = (3+1/a_k)*()...    lhs/rhs        a_m
    1,      2,             4       ,          3.2        ,      1.25               1    ~ 2^0
    5,      8,           256       ,        292.571428571,      0.875             31.81 ~ 2^5
   41,     65, 3.68934881474 E   19, 5.44736223436 E   19,      0.677           1192.08 ~ 2^10
  306,    485, 9.98959536101 E  145, 5.57867460455 E  146,      0.179          99780.79 ~ 2^16
15601,  24727, 3.70427126979 E 7443, 1.06756786898 E 7444,      0.346      285817586.21 ~ 2^28
79335, 125743, 2.59863196329 E37852, 8.97264176433 E37852,      0.289     7216102492.69 ~ 2^33

and we see, that the RHS can reach the LHS for that specific $N$ and thus the assumption of the smallest possible values for the $a_k$ does not suffice to exclude the possibility of a cycle. The "mean" $a_m$, estimated by the geometric mean of all parentheses as proposed above, are in the last column; they increase with the size of $N$ and we get an impression as at which cyclelength $N$ this allows values of $a_1 >2^{60}$ and thus this method has its heuristical limit: the last entry in the last row means $a_m \approx 2^{33}$ and this means, that the knowledge that $a_1>2^{60}$ suffices to have disproved all cycles of steps $N \le 79335$.

But it might anyway be interesting to see, what explicitely smallest value for $a_1$ (which we can assume to be the smallest of the cycle) and the following sequence of consecutive possible members would suffice to have the LHS smaller than the RHS. That would surely be a nice exercise ...

Best Answer

Related Solutions

[Math] $5n+1$, $3n-1$ problem, smallest repeating cycle and Collatz conjecture

[Math] Intuition behind lack of cycles in the Collatz Conjecture

Related Question