Proof of Bound for Growth of Divergent Trajectory in $3x+1$ Problem

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.