If there are $k_1, k_2, \dots, k_n$ divisions by $2$ in a Collatz cycle, then $k_1 + \dots + k_n \geq n$, but can we get a greater lower bound?

Question

Let $f(x) = |3x + 1|_2(3x + 1)$ be the accelerated Collatz function, where $|3x + 1| = 2^{-\nu_2(3x + 1)}$ is the $2$-adic absolute value.

Clearly for all $x$ odd we have $\nu_2(3x + 1) \geq 1$ so that if the "divisions by $2^{\nu_2(3x_i + 1)}$" in an odd cycle $(x_1, x_2, \dots, x_n)$ of length $n$ go:

$$ 2^{-k_1}, 2^{-k_2}, \dots, 2^{-k_n} $$

which brings us back to $x_1$ we have the trivial lower bound $$\sum_{i=1}^{n} k_i = k_1 + k_2 + \dots + k_n \geq n$$. I'm needing better bounds than this. For example, for sufficiently large $n$ (the cycle length) or $x$ (the input to $f$) do we have for example:

$$ \sum_{i=1}^n k_i \geq 2n $$ ?

Please provide a link to an article about this, or guide me on how to improve from the trivial bound.

Answer 1

With $k=\sum_{i=1}^{n} k_i$ the number of "even" steps and $n$ the number of "odd" steps you have $$x_n=\frac{3^n}{2^k}\cdot x_0+\delta_n$$ where $\delta_n$ is the accumulation of "+1" (a sum of power of 2 and 3 over $2^k$)

From here you get $$x_n>\frac{3^n}{2^k}\cdot x_0$$ and with $x_n=x_0$ $$2^k>3^n$$ $$k>n\cdot \log_2(3)$$ $$k\geq \lceil n\cdot \log_2(3)\rceil$$ Not only this is a lower bound, but this is also believed (not proven) to be an equality.

Answer 2

This should not be seen as new answer; it is meant as an explanative comment to the Collag3n's answer, due to OP's additional comments

The following way to express things with the focus the OP has, is my favorite, and I think that scheme as especially clear.

The one-step formula can be expressed as ("Syracuse style"): $$ a_{k+1} = { 3a_k+1\over 2^{A_k}} \tag 1$$ $ \qquad \qquad $ where the $A_k = \nu_2(3 a_k+1)$ .

a.1) For a cycle of 1 step we can write $$ a_1 = { 3a_1+1\over 2^{A_1}} \qquad \qquad \implies \quad 2^{A_1}=\left( 3+ {1\over a_1} \right) \tag {2.1} $$ a.2) For a cycle of 2 step we can write $$ a_2 = { 3a_1+1\over 2^{A_1}} \qquad \qquad a_1 = { 3a_2+1\over 2^{A_2}} \\ a_1 \cdot a_2 = { 3a_1+1\over 2^{A_1}}\cdot{ 3a_2+1\over 2^{A_2}} \implies \quad 2^{A_1}2^{A_2}=\left( 3+ {1\over a_1} \right)\left( 3+ {1\over a_2} \right) \tag {2.2} $$ b) Generalizing: Let's use the symbols $N$ for the (n)umber of $a_k$, and $S$ for the (s)um of the $A_k$, so we have here $N=2$ and we see immediately that in $$ 2^S=\left( 3+ {1\over a_1} \right)\left( 3+ {1\over a_2} \right) \tag 3$$ (assuming all $a_k>0$) the rhs can only be in the interval $\{9 .. 16\}$ = $\{3^N .. 4^N\}$. In the general case for any $N$ and all $a_k>0$ we have thus $$3^N \lt \text{rhs} \le 4^N = 2^{2N} \tag 4$$

The minimal case $\text{rhs}=3^N$ can only occur as limit, when all $a_k "=" \infty$ and the maximal case $\text{rhs}=2^{2N}$ only if all $a_k=1$ (and by the formula (1) thus all $A_k=2$). Introducing the lhs in the inequality means $$3^N \lt 2^S \overset?= \text{rhs} \le 4^N = 2^{2N}$$ The lower bound for $S$ is by this $S \ge \lceil N \cdot \log_2(3) \rceil $ and we have immediately $$ \lceil N \cdot \log_2(3) \rceil \le S \le 2N \tag 5 $$

The second part of your question, whether for some cycle of -perhaps large- $N$ it can happen, that $S$ exceeds it lower bound, for instance such that $S=\lceil N \cdot \log_2(3) \rceil+1$ is not easily to answer here; this depends on the approximability of $2^S$ and $3^N$ and the distance must be very small relative to $N$ resp $3^N$.

But in your last command you additionally ask, whether it can happen that all $A_k=1$: this can only happen if all $a_k=-1$ such that we have $$ 2^S \overset?=\left( 3+ {1\over -1} \right)^N = (3-1)^N=2^N \\ \implies S=N \implies \text{all } A_k=1 \tag 6$$ For all other cases where any $a_k \ne -1$ it is necessary that $S>N$ and thus some $A_k>1$ (and for positive $a_k$ the lower bound for the number of $A_k \ge 2$ can be calculated for each $N$ individually) .

---

Update The question whether it might be possible, that a cycle sums the $A_k$ to $S=C+1$ where $C=\lceil N \cdot ß\rceil$ and $ß=\log_2(3)$ can be answered by the assumption of a roughly (fractional) mean value of all $a_k$, say "$\alpha$". We look at the generalization of eq (3), but in the better to handle form $$ {2^S \over 3^N } = (1+\frac1{3a_1})\cdot(1+\frac1{3a_2})\cdots(1+\frac1{3a_N}) = (1+\frac1{3 \alpha})^N \tag 7$$
From this we can get the "mean" value $$ {2^{S/N} \over 3} = 1+\frac1{3 \alpha} $$ $\phantom{-----}$ and assuming $S=C+1$ $$ \alpha = {1 \over 3} \cdot {1\over 2^{(C+1)/N - ß}-1} \tag 8 $$ $\qquad \qquad \qquad \qquad $ Note: Here the exponent at $2$ can be better rewritten as $$ \qquad \qquad \qquad \qquad \small {C+1\over N}-ß = {\lceil N ß \rceil +1 \over N} - ß = { 2+ N ß - \{N ß \} \over N } - ß = { 2 - \{N ß \} \over N } $$ $\qquad \qquad \qquad \qquad $ where the notation $ \{ x \} $ means the fractional part of $x$ and this latter form is better to use when $N$ and thus $C$ become very large numbers.
We have then that the "mean" values $\alpha$ in most cases are very small, and since the minimal value in the assumed cycle (assumed to be in $a_1$ ) must be smaller than that "mean" value $\alpha$ we have that $a_1 \lt 5$ and thus an a priori forbidden value.
But the convergents of the continued fractions of $ ß=\log_2(3)$ indicate those $N$ where the denominator in eq (8) becomes small and thus $\alpha$ arrives at meaningful values. A short list of this, taken from $N$ and $C$ from that convergents, shows this:

        N*1.0         alpha         N/alpha
                5, 2.07381859665, 2.41101126592
               41, 19.2298809957, 2.13209847784
              306, 146.771589110, 2.08487215991
            15601, 7502.13151589, 2.07954232300
            79335, 38151.7019781, 2.07946161997
           190537, 91628.7531413, 2.07944551757
         10781274, 5184696.58678, 2.07944164515
        171928773, 82680262.3510, 2.07944155124
        397573379, 191192380.562, 2.07944154381
       6586818670, 3167590209.94, 2.07944154182
1.37528045312 E11, 66137009651.3, 2.07944154169
5.40930392448 E12, 2.6013253 E12, 2.07944154168
1.15717186888 E13, 5.5648203 E12, 2.07944154168
...

Interestingly, the ratio $N/\alpha$ seems to converge to something a bit over $2$, and if $\alpha$ were a sort of median then we were lucky here with the disproof: then $N/2$ of the members of a cycle must be smaller than that median, and by an average stepping of $a_{k+1}-a_k \sim 3$ we had $a_1 \sim \alpha - 3/2 N \sim N/2-3N/2 \sim - N$. But unfortunately, $\alpha$ is of course not a median.

Anyway, I've played with that more precise idea and up to $N=190537$ This shows, that we need more information to exclude the possibility of a cycle with $S \ge C+1$ . Here is a table to show, if we fill in eq (3), extended up to $N$ parentheses, into the $a_k$ the lowest possible values $a_k \in \{5,7,11,13,...\}$ beginning with $a_1=5$ and look, whether in the rhs would occur a value $2^{S^*}$ equal or larger than $2^{S}=2^{C+1}$. We check for this the value $S^*(N,a_1)=\log_2(\text{rhs})$ and the criterion $crit= S^* - C$.
Table 1:

                    a1=5        
     N       C   S*(N,a1) S* - C    
--------------------------------
     2,      4,    3.33, -0.669
     3,      5,    4.95, -0.041
     5,      8,    8.19,  0.192
    10,     16,   16.21,  0.214
    17,     27,   27.38,  0.387
    29,     46,   46.48,  0.488
    41,     65,   65.56,  0.562

We show, up to $N=41$, only that $N$ for which the criterion increases, and although we've taken the smallest possible value $5$ into $a_1$ the rhs does not go up to $S^* \ge C+1$. Here $N=41$ is already an entry from the convergents of the cont.frac. and so I show the next $N$ from that convergents only:
Table 2

                        a1=5             a1=7
   N       C      S*(N,a1)   S*-C     S*(N,a1)   S*-C 
----------------------------------------------------
    41,     65,     65.56, 0.562      63.82, -1.179
   306,    485,    485.89, 0.895     484.15, -0.848
(  612,    970,    971.01, 1.005   )                 N=612 not in cvgts, but is first case for S*>C+1
 15601,  24727,  24728.52, 1.527   24726.78, -0.218
 79335, 125743, 125744.78, 1.787  125743.04,  0.042
190537, 301994, 301995.92, 1.928  301994.18,  0.183
   ...     ...        ...    ...       ...      ...

At least, for $N=15601$ and $a_1=5$, we see that $S^* \ge C+1$, and for $N=190537$ we arrive nearly $S^* = C+2 - \varepsilon$ and of course this shall continue and extend for the following convergents.

Unfortunately, the Q&d-procedure with which I compute this values cannot handle significantly larger $N$ (a more sophisticated procedure for N to arbitrary size is possible if Hurwitz-zeta is employed but I don't have my older studies at hand) so we have only a tendency. But I've supplied as well the results, when we begin with $a_1=7$ instead of $a_1=5$ in the previous table. This small step invalidates already all found solutions so far: we have $S^* \lt C+1$ for all $N \le 190537$.

Conclusion: after we know, that any cycle cannot have a minimal element $a_1 \lt 2^{64}$ (or so, see wikipedia) we might have an idea how large any $N$ must be to allow $S^* \ge C+1$ at all. (I've not yet checked the idea of @collagen, maybe that arguments suffice to really exclude the possibility of $S* \ge C+1$ at all).