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.


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)

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)

| cite | improve this answer | |
  • $\begingroup$ The method I had in mind involved finding the characteristic equation of the adjacency matrix of size n. If you assume there are no consecutive raises, then I'm pretty sure you can make the matrix upper triangular without difficulty, which gives a characteristic equation of $p(t) = t^{n-1}(t - 1)$, which shows that the only cycle is the single fixed point $1$. $\endgroup$ – user144527 May 14 '14 at 20:16
  • $\begingroup$ Also, there is a cycle involving alternating increasing and decreasing steps: $\{-5, -7\}$. We need the fact that the numbers are positive (which is implicit in the construction of the adjacency matrix). $\endgroup$ – user144527 May 14 '14 at 20:28
  • $\begingroup$ @user144527 : besides the update of my answer I'd like to understand how you'd arrive at some adjacency-matrix ; I'm just not much familiar with that concept (besides some simple ideas steming from the discussion of continued fractions where they also occur) $\endgroup$ – Gottfried Helms May 16 '14 at 14:43
  • $\begingroup$ Let $C_n$ be the $n \times n$ matrix such that $C_n e_j = e_{T(j)}$ if $j, T(j) \leq n$ and $C_n e_j = 0$ if $j \leq n$ but $T(j) > n$. If $T(n) = (3n + 1)/2^k$ where $n \equiv a_k \pmod{2^{k+1}}$ and $a_k = 3, 1, 13, 5, \ldots$ is the sequence defined by $a_1 = 3$, $a_2 = 1$, $a_{n+2} = 4a_n + 1$, then $C_n$ is the adjacency matrix of the directed graph of the odd-only Collatz transformation on integers bounded by $n$. Since any cycle is bounded, showing that $1$ is the only nonzero eigenvalue of $C_n$ for all $n \in \mathbb{N}$ is equivalent to showing there are no nontrivial cycles. $\endgroup$ – user144527 May 24 '14 at 19:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.