---

Setting

The paper's notation (pp. 1--3). On the rationals with odd denominator, written $\mathbb Q[(2)]$, the Collatz sequence is $x_n=g_0(x_{n-1})=x_{n-1}/2$ when the numerator of $x_{n-1}$ is even and $x_n=g_1(x_{n-1})=(3x_{n-1}+1)/2$ when it is odd (1). $S_{l,n}$ is the set of 0-1 sequences of length $l$ with exactly $n$ ones, $S_l$ the union over $n$, and $S$ the union over $l$; $l(s)$ and $n(s)$ are the length and the number of ones of $s$. The function $\varphi:S\to\mathbb N$ is defined by $\varphi(\{\})=0$, $\varphi(s0)=\varphi(s)$ and $\varphi(s1)=3\varphi(s)+2^{l(s)}$ (2), so that

$$\varphi(s)=\sum_{j=1}^{l(s)}s_j\,3^{s_{j+1}+\cdots+s_{l(s)}}\,2^{j-1}$$

(3). By Lemma 2 (p. 3, credited to Lagarias), each $s\in S$ determines one cycle in $\mathbb Q[(2)]$ of length $l(s)$, the one through $x_0=\varphi(s)/(2^{l(s)}-3^{n(s)})$ whose parity sequence is $s$. With $\lambda_l$ the left shift $(s_1,\ldots,s_l)\mapsto(s_2,\ldots,s_l,s_1)$, $\sigma(s)$ is the set of the rotations $\lambda_l^k(s)$, $k=1,\ldots,l$, and

$$M_{l,n}:=\max_{s\in S_{l,n}}\Bigl\{\min_{t\in\sigma(s)}\varphi(t)\Bigr\}$$

(p. 3). The rotations of $s$ are the parity sequences read from the other elements of the same cycle, so for $2^l>3^n$ the quotient $M_{l,n}/(2^l-3^n)$ is the largest minimum a cycle with parity data $(l,n)$ can have; the paper uses it this way in (5) (p. 3) and (11) (p. 10).

Statement

Lemma 5 (p. 5): "Let $n\le l$ be natural numbers. Let $\tilde s_i:=\lceil i\frac nl\rceil-\lceil(i-1)\frac nl\rceil$ (for $1\le i\le l$), then $\varphi(\tilde s)=\min_{t\in\sigma(\tilde s)}\{\varphi(t)\}=M_{l,n}$."

The paper writes $\tilde s(l,n)$ for this sequence. Combined with (3) it gives Corollary 1 (p. 6): for every $l$ and $n\le l$,

$$M_{l,n}=\sum_{j=1}^{l}\Bigl(\Bigl\lceil j\frac nl\Bigr\rceil-\Bigl\lceil(j-1)\frac nl\Bigr\rceil\Bigr)2^{j-1}3^{\,n-\lceil j\frac nl\rceil}.$$

So when $2^l>3^n$ the cycle generated by $\tilde s(l,n)$ is, among the cycles with $l$ steps and $n$ odd steps, one whose minimum is as large as possible. This is the sense in which the paper calls the criterion of Theorem 4 optimal (p. 11).

Source. Lorenz Halbeisen and Norbert Hungerbühler, Optimal bounds for the length of rational Collatz cycles, Acta Arith. 78 (1997), 227--239; Lemma 5 on p. 5 and Corollary 1 on p. 6 of the authors' preprint named on the source card, numbered 1--13 rather than by the journal's pagination.

Read depth. Claims checked: the statements and the definitions on pp. 1--6 were read on the print, and the proof on p. 5 was read. Nothing here is independently reviewed.

Proof pointer

Page 5. Lemma 4 (p. 4) shows that among distinct sequences of $S_{l,n}$, one whose partial sums are everywhere at most another's has the larger value of $\varphi$. Any $t\in S_{l,n}$ has a rotation whose partial sums all lie on or above the line $k\,n/l$, starting where $t$'s staircase falls furthest below that line, and $\tilde s$ lies between that rotation and the line, so $\varphi(\tilde s)$ is at least the least value of $\varphi$ on $\sigma(t)$. Every rotation of $\tilde s$ has partial sums at most those of $\tilde s$, so by Lemma 4 again $\tilde s$ is the minimizer within its own class.

Dependencies

Lemma 4 (p. 4) and formula (3) (p. 3).

Bears on

• #1135: background only. The paper's $g_0,g_1$ are the problem's $f$ extended to $\mathbb Q[(2)]$, and a cycle of $f$ in the positive integers other than $\{1,2\}$ would answer the problem in the negative. The lemma identifies the largest possible minimum of a cycle with given parity data; it does not exclude any cycle.