I have been reading the Simon & Weger (2005) paper on the Collatz Conjecture.
Let:
$u$ be a natural number.
$\delta = \dfrac{\log 3}{\log 2}$
$p_n/q_n$ be the $n$th convergent to $\delta$
$T(u) = \begin{cases} \frac{1}{2}(3u + 1), && \text{if }u\text{ is odd}\\ \frac{1}{2}u, && \text{if }u\text{ is even}\\ \end{cases}$
sequence be an increasing subsequence of odd integers followed by a decreasing subsequence of even integers
a cycle be an $m$-cycle if it consists of $m$ sequences with a total of $K$ odd numbers and a total of $L$ even numbers.
a non-trivial cycle be any cycle that contains natural numbers greater than $2$.
a sequence is periodic if there exists an integer $p \ge 1$ in the sequence $\{ u, T(u), T^2(u), \dots, T^{p}(u) \}$ where:
- $T^0(u) = u$
- $T^{i+1}(u) = T(T^i(u))$
- $T^p(u) = u$
$t_0, t_1, \dots, t_{m-1}$ be the indices of the $m$ local minima in an $m$-cycle such that:
- $t_0 = 0$
- $t_0 < t_1 < t_2 < \dots < t_{m-1} < p$
$s_0, s_1, \dots, s_{m-1}$ be the indices of the $m$ local maxima in an $m$-cycle such that:
- $t_0 < s_0 < t_1 < s_1 < \dots < t_{m-1} < s_{m-1} \le p-1$
$x_i, y_i$ be the values of the local minima and maxima so that:
- $x_i = T^{t_i}(u)$
- $y_i = T^{s_i}(u)$
$X_0$ be the absolute minima
$k_i, l_i$ be defined so that:
- $k_i = s_i - t_i$ for $i = 0, \dots, m-1$
- $l_i = t_{i+1} - s_i$ for $i = 0, \dots, m-2$ and $l_{m-1} = p + t_0 - s_{m-1}$
- $K = \sum\limits_{i=0}^{m-1}k_i$
- $L = \sum\limits_{i=0}^{m-1}l_i$
- $\Lambda = (K+L)\log2 - K\log3$
Question:
I had a question about Lemma 10 which states the following conclusion: $$\text{if }q_n + q_{n+1} \le (\log 2)\frac{X_0}{m}\text{, then }K > q_n$$
I am clear on the first steps:
(1) Assume $K \le q_n$
(2) $\Lambda = (\log2)(K+L) - K\log3 = (\log2)|(K+L) - K\delta|$
I am not clear on the next step:
$$(\log2)|(K+L) - K\delta| \ge (\log2)|p_n - q_n\delta|$$
I am trying to understand why:
$$(K+L) - K\delta \ge p_n - q_n\delta$$
From $K \le q_n$, I just need to understand why:
$$(K+L) \ge p_n$$
The argument suggests that Lemma 9 might help here with 9(c) and 9(b). It is not clear to me how Lemma 9 relates to reasoning about $K+L$.
Lemma 9 includes the following points:
9(a) If $p/q$ is a rational approximation to $\delta$ satisfying $|p - q\delta| < \dfrac{1}{(2q)}$, then $p/q$ is a convergent
9(b) $|p_n - q_n\delta| > \dfrac{1}{q_n + q_{n+1}} > \dfrac{1}{(a_{n+1} + 2)q_n}$
9(c) If $p/q$ is a rational approximation to $\delta$, and if $q < q_n$, then $|p-q\delta| \ge |p_n - q_n\delta|$
9(d) If $n$ is odd, then $p_n - q_n\delta > 0$; if $n$ is even, then $p_n - q_n\delta < 0$
Note: $a_i$ is an integer used in the Chain Equation (2.1) in the paper which applies to the case of a non-trivial $m$-cycle.