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}, & 2 \nmid x \\ \dfrac{x}{2}, & 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 < \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?
 A: 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 < n_2 < \ldots < 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} < 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 > 0$, and apply Corollary 2 to $0 = n_0 < n_1 < \cdots < n_{k-1}$ to find an index $\hat{k}$ such that $1 \leq \hat{k} < 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}) & = \sum_{i=1}^{k-\hat{k}} \dfrac{3^{k-\hat{k}-i}}{2^{n_{k-\hat{k}}-n_{i-1}}} \\
    & \leq \sum_{i=1}^{k-\hat{k}} \dfrac{3^{k-\hat{k}-i}}{3^{(k-\hat{k}-i+1)(1 + \delta)}} \\
    & = \dfrac{1}{3} \sum_{i=1}^{k-\hat{k}} \dfrac{1}{3^{(k-\hat{k}-i+1)\delta}} \\
    & \leq \dfrac{1}{3^{1+\delta} - 3} \\
    & = \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."
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 < 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 < y_1 < y_2 < \cdots$ such that $y_j = T^{n_j}(x)$, for some natural numbers $n_0 < n_1 < n_2 < \cdots$, and such that $T^n(y_j) > 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} < \log_3 2
  \end{align*}
Then, there is some constant $c$ such that
\begin{align*}
   \dfrac{k(x, n)}{n} \leq \dfrac{1}{c} < \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} < \log_3 2
  \end{align*}
Let $d = c - \log_2 3 > 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} < 1$ and $y_j$ grow unbounded, there is a
\begin{align*}
   y_j > \dfrac{1}{(2^c - 3)(1 - 2^{-d})}
  \end{align*}
at which point
\begin{align*}
   T^{n^*}(y_j) < 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.
A: 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 < \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)>=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"
A: Lagarias likely hasn't included it because it's trivial.
Let the down transform $t_d$ be an instance of $(3x+1)/4$ and the up transform $t_u$ be an instance of $(3x+1)/2$.
Then take as a representative of a sequence equidistributed mod $2$ the following: $t_d,t_d,t_d,\ldots$
Mod 2, this goes $1,0,1,0,1\ldots$
Now supposing the ones vanished, i.e. $T(x)=3x/2$ or $x/2^r$, then $T^{(2k)}(x)=(3/4)^kx$ which is clearly descending so this equidistributed sequence falls.
With a little work on what ratio of $t_l$ to $t_d$ are required to make a sequence constant, Lagarias' inequality instantly follows from his earlier assumption that the sequence diverges and is therefore greater than constant:
$\begin{align*} \tag{2.31} \liminf_{k \to \infty} \dfrac{N^*(k)}{k} \geq (\log_2 3)^{-1} \approx .63097 \end{align*}$
Now, on the vanishing of the $1$ part of $3x+1$:
Since the sequence is assumed to diverge, for every subsequence $S_{x_0}$ of length $n_0+1$ and satistying $x_n>x_0$ we can identify a higher subsequence $S_{x_{n_0+1}}$ of length $n_1$ which also satisfies $x_{n_0+n_1+1}>x_{n_0+1}$.
Then by induction over the $p$ in $n_p$, we see that:
$\lim_{p\to\infty}T^{(k)}(x_{n_p})/x_{n_p}=3^r/2^q$ where $r$ counts $3x+1$ and $q$ counts $/2$.

It then follows from the commutativity of multiplication, that as $x\to\infty$ the order of $t_l,t_d$ in the sequence ceases to matter and the result above for $1,0,1,0,\ldots\pmod2$ holds for all equidistributed sequences.

I haven't accommodated for e.g. divisions by $8$ or greater but this is throguh lack of time, care and skill rather than these being difficult to accommodate.
