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

Question

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?

Answer 1

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.

Answer 2

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"

Answer 3

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.