Collatz Conjecture: For a cycle where the maximum odd integer is $x_{max}$, does it follow that $x_{max} < 3^n$

Question

I am working on understanding the upper limit in the case where a non-trivial cycle exists for the Collatz Conjecture.

Is the following reasoning valid for establishing that the maximum odd integer in a cycle consisting $n$ odd integers is less than $3^n$?

Let:

• $\nu_2(x)$ be the 2-adic valuation of $x$
• $n > 5$ be an integer
• $x_1, x_2, \dots, x_n$ be the distinct odd integers that make up a cycle of length $n$ with:
  • $x_{i+1} = \dfrac{3x_i+1}{2^{\nu_2(3x_i+1)}}$
  • $x_{i+n} = x_i$
  • $x_{max}$ is the highest odd integer in the cycle
• $p_0, p_1, \dots p_n$ be integers such that:
  • $p_0 = 0$
  • $p_{i+1} = p_i + \nu_2(3x_{i+1}+1)$
  • $p_n > p_{n-1} > \dots > p_1 > p_0 = 0$

(1) Since $x_1, \dots x_n$ is a cycle, we can assume that $x_1 = x_{max}$

(2) It follows from reasoning in step 2 here: $$2^{p_n}x_{n+1} - 3^{n}x_1 = x_{max}\left(2^{p_n} - 3^n\right) = \sum\limits_{i=0}^{n-1}3^{n-1-i}2^{p_i}$$

(3) From reasoning here for a cycle: $$p_n < 2n$$

(4) $\sum\limits_{i=0}^{n-1}3^{n-1-i}2^{p_i} < 6^n$ since:

$$\sum\limits_{i=0}^{n-1}3^{n-1-i}2^{p_i} < 3^{n-1} + 4^{n-1} + (2^{2n-n+1})(\sum\limits_{i=1}^{n-2}3^{n-i-i}2^{i}) < 3^{n-1} + 4^{n-1} + 2^{n+1}(3^{n-1}-2^{n-1}) = 3^{n-1} + 4^{n-1} + 4(6^{n-1} - 4^{n-1}) < 6^{n-1} + 6^{n-1} + 4\times6^{n-1} = 6^n$$

(5) $2^{p_n} \ge 2^{\lceil{n}\log_2{3}\rceil} > 3^n$

• From reasoning here, since $n > 5$, it follows that $2^{p_n} - 3^n > 2^n$

• It follows that $x_{max} < \dfrac{6^n}{2^n} = 3^n$

Did I make a mistake? Is there any step that is unclear? Is there a simpler argument to reach the same conclusion?

---

Edit:

There is no advantage to the 2 cases in step 5. I have updated to simplify based on suggestions in the comment.

Answer 1

The start of your reasoning is quite good, although there are some issues with your later steps. Otherwise, your arguments are basically correct.

In your (4), there are several relatively minor mistakes, but your overall upper bound still applies. Using your result of $p_n \lt 2n$, then each $p_{i+1} \gt p_{i}$ for $1 \le i \le n - 1$ means each lower index $p$ value must be at least one less than the one above, with this giving that for all $0 \le j \le n - 1$

$$p_{n-j} \lt 2n - j \tag{1}\label{eq1A}$$

Thus, for example, $p_{n - 1} \lt 2n - 1$ and $p_i \lt 2n - (n - i) = n + i$ for all $1 \le i \le n$ (thus, for example, $p_1 \lt n + 1$). This then, along with $n \gt 5$, gives

$$\begin{equation}\begin{aligned} \sum_{i=0}^{n-1}3^{n-1-i}2^{p_i} & \lt 3^{n-1} + 2^{2n-1} + (2^n)\left(\sum_{i=1}^{n-2}3^{n-1-i}2^{i}\right) \\ & = 3^{n-1} + 2(2^{2(n-1)}) + (2^n)((2)(3)(3^{n-2} - 2^{n-2})) \\ & = 3^{n-1} + 2(4^{n-1}) + (2^2)((2)(3))(6^{n-2} - 4^{n-2}) \\ & \lt 6^{n-1} + 6^{n-1} + (4)(6)(6^{n-2}) \\ & = 6^{n-1} + 6^{n-1} + 4(6^{n-1}) \\ & = 6^n \end{aligned}\end{equation}\tag{2}\label{eq2A}$$

You made a mistake with using $4^{n-1}$ instead of $2(4^{n-1})$. Also, since the starting point for $i = 1$ has a factor of $2^i = 2$ instead the summation, the common factor outside is $2^n$, not $2^{n+1}$. Finally, assuming you tried to use the actual summation instead of performing several steps at once, then note the summation has a factor of $3$ outside, with the exponents inside being $n - 2$, not $n - 1$. To see this, using the sum of a geometric series formula gives

$$\begin{equation}\begin{aligned} \sum_{i=1}^{n-2}3^{n-1-i}2^{i} & = 2(3^{n-2})\left(\frac{1 - \left(\frac{2}{3}\right)^{n-2}}{1 - \frac{2}{3}}\right) \\ & = 2(3^{n-2})\left(\frac{\frac{3^{n-2} - 2^{n-2}}{3^{n-2}}}{\frac{1}{3}}\right) \\ & = 2(3)(3^{n-2} - 2^{n-2}) \end{aligned}\end{equation}\tag{3}\label{eq3A}$$

Regarding your step (5), here are a few more details. With $m = \left\lceil n\log_2 3 \right\rceil$ being the positive exponent $m$ which allows $2^m - 3^n \gt 0$, then since $2^{p_n} \gt 3^n$, we have $p_n \ge m$. This then gives from your linked answer for $n \gt 5$ that

$$2^{p_n} - 3^n \ge 2^{\left\lceil n\log_2 3 \right\rceil} - 3^n \gt 2^n \tag{4}\label{eq4A}$$

Answer 2

This is possibly rather a comment than an answer because I cannot pinpoint the exact position of the likely glitch in your arguments. However perhaps this derivation here implies some hint

update: I've misread Larry's notation of the $p_k$. So I replace my text introducing the exponents $A_k = \nu_2(3x_k+1)$ such that $p_1=A_1$, $p_2=A_1+A_2$ and $p_n=A_1+A_2+...+A_n$ where now also $P=p_n$ (for easier notation in the exponents). For an "1-cycle" all except one are $A_k=1$.

---

The largest "stretch" between the smallest and the largest element $x_{\min}$ and $x_{\max}$ in an assumed cycle occurs if all but one (odd!) step are increasing, so the exponents except of only one are $A_k=1$ (this is then the "1-cycle"). And more concretely we have then about $x_\min = x_2$ and $$x_\max=x_1 = 1.5^{n-1} \cdot (x_2+1) -1 \tag 1$$ $\phantom {quad quad quad quad quad} $ _{This can be seen in my short essay on the 1-cycle in eq (3.1a) and (3.1b) on pg 4.}

Let us write:$$A_1+A_2+...+A_n =P (=p_n)$$ which is also (for this type of cycle) $$P \overset {\text{def}}=A_1+(n-1)\cdot 1 = (A_1-1)+n $$ then it is required that $P$ is such that $2^P \gt 3^n$ , or, let's take its minimal possible value $P=\lceil \gamma \cdot n \rceil$ where $\gamma = \log_2(3)\approx 1.58$.

From the equations of the "1-cycle" (for instance in my cited essay) we know that the minimal element is determinable by $$ x_\min = { 3^n-2^n \over 2^P - 3^n }={ 2^P-2^n \over 2^P - 3^n }-1 = 2^n \cdot { 2^q-1 \over 2^P - 3^n }-1 \tag 2\\ \small{\text{ where we introduce for notational easiness }q=A_1-1} $$ Here the fraction-term $w_n \overset{\text{def}}= { 2^q-1 \over 2^P - 3^n } $ becomes the critical part for us, because we can proceed $$ x_\max = 1.5^{n-1} \cdot (x_\min+1)-1 \\ = 1.5^{n-1} \cdot (2^n \cdot { 2^q-1 \over 2^P - 3^n }-1 +1)-1 \\ = 1.5^{n-1} \cdot (2^n \cdot w_n)-1$$ $$ x_\max = 2 \cdot 3^{n-1} \cdot w_n -1 \overset?\le 3^n \tag 3 -1$$

Your question is answered to the positive if $w_n \le 1.5$ for all $n$.
_{update 2: Rereading the OP's post - your observation in "step 5" is sufficient that $w_n \lt 1$ for $n \gt 5$, and which introduces the non-elementary aspect of rational approximation and makes your conjecture safe. Sorry for not having seen this immediately}

---

However, I've never arrived at (or have seen) an elementary proof, that this is always the case, so I don't believe your derivation is without error (but my answer hopefully gives some hint, where).
Actually the numerical analysis for small $n$ indeed confirm that $w\le 1$ (compute the most critical cases for $n \in\{3,5,17,29,41,94,...\}$ from the generalized convergents of the continued fraction of $\gamma$), and for larger $n$ the theory of rational approximation of transcendental numbers (like it has been done for the disproof of the "1-cycle", see reference to Simons/deWeger in my essay) shall show that $w_n$ indeed will be smaller than $1$ for all $n \gt n_\min$.

So the conjecture is true, but something in your arguments has very likely a glitch.

---

Here empirical values for some $n$:

 n    w_n
 -----------
  1   1.0
  2   0.428571428571
  3   0.6
  4   0.148936170213
  5   0.538461538462
  6   0.0508474576271
  7   0.0162388685175
  8   0.0190067443286
  9   0.00481467329003
 10   0.00971173115462
 11   0.00149417038248
 12   0.000493101414524
 ...

and the list of the local maxima of that values, due to the convergents of the continued fraction of $\gamma$

 n    w_n
 -----------
  1   1.0
  3   0.6
  5   0.538461538462
 17   0.000201474525683
 29   0.0000000753989313627
 41   3.98990329587 E-11
 94   5.41070634693 E-27
 ...  ...