Collatz cycle necessary condition.

598 Views Asked by At

Has it been established that a nontrivial m-cycle of the Collatz conjecture on the positive integers would require two consecutive raises (i.e., if $\{x_1, x_2, \ldots x_n\}$ is the odd positive integers in an m-cycle, that $x_j, x_{j+1}$ for some $j \in [1,n-1]$ or $x_n, x_1$ must both be congruent to $3 \pmod{4}$)?

I can show this, but about what I'm thinking isn't pretty, and I would rather reference work that has already been done than reinvent the wheel.

1

There are 1 best solutions below

4
On

Hmm, I don't know, whether someone has worked out such a statement explicitly. But it seems fairly easy to prove: one step of the increasing type does less than one step of any of the decreasing types (we're on the "odd-numbers-only" method), so in a cycle or m-cycle we need more increasing steps than decreasing steps. And this makes automatically sure, that there are a number of neighbored increasing steps required/involved (except of the example with the trivial cycle).
(I hope I did not misunderstand your question)

[update]
After reading your comment I'll show, that there is a very simple and powerful formula to discuss the option of cycles. We look at the Collatz-transformation in the "Syracuse"-form
$$ a \to b := b = {3a +1\over 2^A } $$ which deals with the odd numbers $a,b$ only.
Then, to become a 1-step-cycle we must have, that $b=a$ and we can write $$ \begin{eqnarray} b &= {3a +1\over 2^A } & \qquad \text{ and at the same moment}\\ b&=a \end{eqnarray}$$ such that we can write $$ a = {3a +1\over 2^A } $$ and try to find a solution $$ 2^A = 3 + {1\over a } $$ Because for positive $a$ the rhs in between $3 ..4$ there can be only one solution, namely $a=1$ and $A=2$. For negative $a$ we can have $a=-1, A=1$, so $a=1,a=-1$ generate a 1-step-cycle and this are the only solutions.

If we look at the 2-step-cycle we can write $$ \begin{eqnarray} b &= {3a +1\over 2^A } \\ c &= {3b +1\over 2^B } & \qquad \text{ and at the same moment, to have a cycle} \\ a&=c \end{eqnarray}$$ Then we can write the trivial equation of products $$ a \cdot b ={3b +1\over 2^B }\cdot {3a +1\over 2^A } $$ We can rearrange to get $$ 2^{A+B} = (3+{1\over b })\cdot(3+{1\over a}) $$ and here we see, that the rhs can only be in the interval $9..16$ if $a,b$ are positive and $4..9$ if $a,b$ are negative. Because the lhs is a perfect power of $2$ only the solutions $$2^{A+B}=16 \to a=1,b=1$$ and $$2^{A+B}=4 \to a=-1,b=-1$$ and $$2^{A+B}=8 \to a=-5,b=-7$$ are possible where the first two solutions are the "trivial" ones which are already 1-step-cycles.


This scheme can in principle be extended to any number of steps; however it needs a (finite, at least) number of checks, whether perfect powers of 2 can occur by the parentheses on the rhs.

If we denote the number of parentheses on the rhs with $N$ (which is also the number of steps) and the sum of the exponents on the lhs with $S$ then we get in principle one general relation between $2^S$ and $3^N$ by $$2^S = (3+1/a)(3+1/b)(3+1/c)...(3+1/m)$$ Factoring out $3^N$ gives $$2^S = 3^N(1+1/3a)(1+1/3b)(1+1/3c)...(1+1/3m)$$ and this shows a very characteristic relation between $2^S$ and $3^N$, where for $N$ greater than some very small number (which define the above trivial and nearly-trivial cases) $N \lt S \lt 2N$ .

Finally, this shows that we must have many exponents $X_k \in \{A,B,C,...\}$ with $X_k=1$ and only few $Y_j \in \{A,B,C,...\}$with $Y_j \ge 2$ where any exponent $X_k=1$ means an ascending step and $Y_j \ge 2$ means a decreasing step.

But since we'll have by this in a (sufficiently long) cycle always more increasing steps than decreasing steps, it follows that some increasing steps must be neighbored. This explains your question/statement (well, as far as we discuss cycles whose elements $a,b,c,...$ are all bigger than $1$ or all smaller than $-1$ and where $N>2$ and all elements are different, none is $\pm 1 $)

(You might be interested in my small treatise where I deal with this a bit more broad&wide)