Proof of Bound for Growth of Divergent Trajectory in $3x+1$ Problem In this paper, Lagarias makes the following claim in section 2.7 (Do divergent trajectories exist?).

Context

$$T(x) = \left\{ \begin{array}{rl} \dfrac{3x + 1}{2}, &amp; 2 \nmid x \\ \dfrac{x}{2}, &amp; 2 \mid x \end{array} \right.$$

$$\begin{align*} \tag{2.30} \lim_{k \to \infty} |T^{(k)}(n_0)| = \infty \end{align*}$$

Claim

If a divergent trajectory $\{T^{(k)}(n_0) : 0 \leq k &lt; \infty\}$ exists, it cannot be equidistributed $\pmod{2}$. Indeed if one defines

$N^*(k) = |\{j : j \leq k \mathrm{\ and\ } T^{(j)}(n_0) \equiv 1 \pmod{2}\}|$,

then it can be proved that the condition (2.30) implies that

$$\begin{align*} \tag{2.31} \liminf_{k \to \infty} \dfrac{N^*(k)}{k} \geq (\log_2 3)^{-1} \approx .63097 \end{align*}$$

Question

How can this statement be proved?

Difficulty

It seems like the author may be ignoring the $+1$ term under the assumption that the factors will dominate. (I've seen this assumption made often for heuristic arguments for the truth of the Collatz conjecture.) I don't see how such an assumption can be justified.

Given any length $n$ sequence of $n - k$ zeros and $k$ ones, we can find an $x \in \mathbb{N}$ such that

$$T^n(x) = \dfrac{3^k x + m}{2^n}$$

where

$$3^k - 2^k \leq m \leq 2^{n-k}(3^k - 2^k)$$

Now, suppose, for example, $n = 2k$. Then, we have the bound

$$T^n(x) \leq \dfrac{3^k x + 2^{n-k}(3^k - 2^k)}{2^n} = \left(\dfrac{3}{4}\right)^k x + \left(\dfrac{3}{2}\right)^k - 1$$

and the exponential "$+1$" term dominates for large $n$. Now, of course, $m$ won't always be as large as possible, but even if we look at "random" $m$, that only introduces a constant factor in front of the exponential.

Additional Questions

Is the proof of this statement difficult? Is that why the author doesn't include it? Is there a paper containing a proof?
I contacted the author, and he was kind enough to write up a proof for me. I have attempted to simplify his proof for presentation here. I also use some notation without explanation to reduce clutter; the meanings should be clear. The trick is to use an apparently well known result from lattice theory.
Proposition 1 (Lattice Theory rotation trick)
If $b_1, b_2, \ldots, b_\ell$ are real numbers such that
\begin{align*}
   b_1 + b_2 + \cdots + b_\ell = r \ell
  \end{align*}
($\ell \geq 2$) then the lattice path
\begin{align*}
   (0, 0), (1, b_1), (2, b_1 + b_2), \ldots, (\ell, b_1 + b_2 + \cdots + b_\ell) = (\ell, r \ell)
  \end{align*}
has a cyclic forward shift by some $k$ with $0 \leq k \leq \ell - 1$
\begin{align*}
   (0, 0), (1, b_{k+1}), (2, b_{k+1} + b_{k+2}), \ldots, (\ell, b_{k+1} + b_{k+2} + \cdots + b_\ell + b_1 + b_2 + \cdots + b_k) = (\ell, r \ell)
  \end{align*}
so that
\begin{align*}
   b_{\overline{k+1}} + b_{\overline{k+2}} + \cdots + b_{\overline{k+j}} \leq jr
  \end{align*}
for all $1 \leq j \leq \ell$, where $\overline{k+i} \equiv k + i \pmod{\ell}$ and $1 \leq \overline{k+i} \leq \ell$.
Proof
Let $k$ be the smallest index such that the point $(k, b_1 + b_2 + \cdots + b_k)$ is not above the line $y = rx$ and the distance between this point and the line is maximum. Notice that $k \leq \ell - 1$ by the extreme value theorem.
Corollary 2
If $n_1 &lt; n_2 &lt; \ldots &lt; n_k$ and $r = n_k/k$, then there is some $\hat{k}$ with $1 \leq \hat{k} \leq k - 1$ such that
\begin{align*}
    n_{k-\hat{k}+1} - n_j \geq (k - \hat{k} + 1 - j) r
   \end{align*}
for all $1 \leq j \leq k - \hat{k}$.
Proof
Apply Propositon 1 to the sequence
\begin{align*}
   b_1 = n_k - n_{k-1}, b_2 = n_{k-1} - n_{k-2}, \ldots, b_{k-1} = n_2 - n_1, b_k = n_1
  \end{align*}
Lemma 3 (bound on additive term)
For odd $x \in \mathbb{N}$, suppose that
\begin{align*}
   T^n(x) = \dfrac{3^k}{2^n}x + e(x, k)\;\;\;\;\; e(x, k) = \sum_{i=0}^{k-1} \dfrac{3^i}{2^{n_k - n_{k-1-i}}}
  \end{align*}
where $r = n/k \geq \log_2 3$. Then there is a $1 \leq \hat{k} &lt; k$ such that
\begin{align*}
   e(x,k-\hat{k}) \leq \dfrac{1}{2^r - 3}
  \end{align*}
Proof
Let $r = n/k = (\log_2 3)(1 + \delta)$, where $\delta &gt; 0$, and apply Corollary 2 to $0 = n_0 &lt; n_1 &lt; \cdots &lt; n_{k-1}$ to find an index $\hat{k}$ such that $1 \leq \hat{k} &lt; k$ and
\begin{align*}
   n_{k-\hat{k}} - n_{j-1} \geq (k - \hat{k} - j + 1)r
  \end{align*}
for all $1 \leq j \leq k - \hat{k}$. Then,
\begin{align*}
   2^{n_{k-\hat{k}} - n_{i-1}} \geq 2^{(k-\hat{k}-i+1)r} = 3^{(k-\hat{k}-i+1)(1+\delta)}
  \end{align*}
and
\begin{align*}
   e(x, k - \hat{k}) &amp; = \sum_{i=1}^{k-\hat{k}} \dfrac{3^{k-\hat{k}-i}}{2^{n_{k-\hat{k}}-n_{i-1}}} \\
    &amp; \leq \sum_{i=1}^{k-\hat{k}} \dfrac{3^{k-\hat{k}-i}}{3^{(k-\hat{k}-i+1)(1 + \delta)}} \\
    &amp; = \dfrac{1}{3} \sum_{i=1}^{k-\hat{k}} \dfrac{1}{3^{(k-\hat{k}-i+1)\delta}} \\
    &amp; \leq \dfrac{1}{3^{1+\delta} - 3} \\
    &amp; = \dfrac{1}{2^r - 3}
  \end{align*}
Remark
The key fact about Lemma 3 is that the bound is independent of both $x$ and $e(x,k)$, depending only on the value of $r = n/k$. It achieves this by making the choice $\hat{k}$ that depends on $x$ and showing that such a choice must exist for every $x$ with $r \geq \log_2 3$. This is the ``trick.&quot;
Theorem 4
If $x, T(x), T^2(x), \ldots$ is a divergent trajectory with
\begin{align*}
   k(x, n) = |\{T^j(x) \equiv 1 \pmod{2} : 0 \leq j &lt; n\}|
  \end{align*}
then
\begin{align*}
   \liminf_{n \to \infty} \dfrac{k(x, n)}{n} \geq \log_3 2
  \end{align*}
Proof
Since $x$ has a divergent trajectory, there must be a sequence $y_0 &lt; y_1 &lt; y_2 &lt; \cdots$ such that $y_j = T^{n_j}(x)$, for some natural numbers $n_0 &lt; n_1 &lt; n_2 &lt; \cdots$, and such that $T^n(y_j) &gt; y_j$ for all $n \in \mathbb{N}$. For each (fixed) $y_j$, we have
\begin{align*}
   \liminf_{n \to \infty} \dfrac{k(x, n)}{n} = \liminf_{n \to \infty} \dfrac{k(x, n) - k(x, n_j)}{n - n_j} = \liminf_{n \to \infty} \dfrac{k(y_j, n)}{n}
  \end{align*}
Now, suppose that
\begin{align*}
   \liminf_{n \to \infty} \dfrac{k(x, n)}{n} &lt; \log_3 2
  \end{align*}
Then, there is some constant $c$ such that
\begin{align*}
   \dfrac{k(x, n)}{n} \leq \dfrac{1}{c} &lt; \log_3 2
  \end{align*}
infinitely often, and, in particular, for each $y_j$, there is always an $n$ such that
\begin{align*}
   \dfrac{k(y_j, n)}{n} \leq \dfrac{1}{c} &lt; \log_3 2
  \end{align*}
Let $d = c - \log_2 3 &gt; 0$. Then, $n \geq k(y_j, n)(\log_2 3 + d)$ implies
\begin{align*}
   2^n \geq 3^{k(y_j, n)} 2^{kd} \geq 3^{k(y_j, n)} 2^d \iff \dfrac{3^{k(y_j, n)}}{2^n} \leq 2^{-d}
  \end{align*}
Let $r = n/k(y_j, n) \geq c$. Applying Lemma 3, we have an $n^*$ such that
\begin{align*}
   T^{n^*}(y_j) \leq 2^{-d} y_j + \dfrac{1}{2^r - 3} \leq 2^{-d} y_j + \dfrac{1}{2^c - 3}
  \end{align*}
where the values $c$ and $d$ are constant across all the $y_j$ (i.e., for each $y_j$, there is an $n^*$ such that the bound holds). Since $2^{-d} &lt; 1$ and $y_j$ grow unbounded, there is a
\begin{align*}
   y_j &gt; \dfrac{1}{(2^c - 3)(1 - 2^{-d})}
  \end{align*}
at which point
\begin{align*}
   T^{n^*}(y_j) &lt; y_j
  \end{align*}
contradicting our construction of the $y_j$ and proving
\begin{align*}
   \liminf_{n \to \infty} \dfrac{k(x,n)}{n} \geq \log_3 2
  \end{align*}
Remark
If you find any errors in the above, it is almost certainly from my attempt to simplify the proof I was given and not from the author.
The "+1" term is just included in the bound,
$$3^{N^*(k)}\leq\frac{T^{(k)}(n_0)}{n_0}2^{k}$$ 

see construction here: A possible way to prove non-cyclicity of eventual counterexamples of the Collatz conjecture?

If you start with this:

$$T^{(k)}(n_0) = \frac{3^{N^*(k)}}{2^{m_1+m_2+...+m_i}}\cdot n_0+\frac{3^{N^*(k)-1}}{2^{m_1+m_2+...+m_i}}+\frac{3^{N^*(k)-2}}{2^{m_1+m_2+...+m_{i-1}}}+...+\frac{3^0}{2^{m_1}}$$
see construction here: $(n_0) \to (n_i)$ and $(n_0+k\cdot2^j)\to(n_i+k\cdot3^i)$, same Glide?

This can be simplified to
$$T^{(k)}(n_0) = \frac{3^{N^*(k)}}{2^k}\cdot n_0+\alpha N^*(k)$$
where $\alpha &lt; \frac{1}{3}$ as shown in this paper: https://arxiv.org/abs/1710.01525v1

$$2^k = 3^{N^*(k)}\frac{n_0}{T^{(k)}(n_0)-\alpha N^*(k)}$$
$$k = N^*(k)\log_23+\log_2(\frac{n_0}{T^{(k)}(n_0)-\alpha N^*(k)})$$

Now as long as $T^{(k)}(n_0)-\alpha N^*(k)&gt;=n_0$

$$k \leq N^*(k)\log_2(3)$$
$$\frac{N^*(k)}{k} \geq \frac{1}{\log_23}$$

I didn't check Theorem F, but i guess this is linked to his remark "cannot go too slowly"