Upper bound on the elements of a Collatz cycle

Question

Let $T$ be the (shortcuted) Collatz map: $T(x) = x/2$ when $x$ is even and $T(x) = (3x+1)/2$ when $x$ is odd.

Böhm and Sontacchi, 1978 show that if $x = T^n(x)$ then $x < 3^n$ with $x,n\in\mathbb{N}^+$.

Can this bound be improved to $2^n$?

This question is relevant when analysing Collatz cycles in binary as it asks if iterates in a positive integer cycle of size $n$ can always be represented on $n$ bits or not. We originally asked the question in this paper which studies Collatz in base 2 and 3 -- this is not meant to do self-promotion but merely to give more context on this question.

Arguably, the question is interesting per se as it is generally hard to give any kind of non-trivial results concerning Collatz cycles (such as Eliahou, 1993 or [Steiner, 1977]).

Thank you very much in advance,

Answer 1

I am not aware of any previous answer in a publication, but asymptotically sharper bounds are known. For example, in the context of the $``3x+d"$ generalization, Belaga and Mignotte found that

$$ x < d \cdot k^{C} \cdot \left( \frac{3}{2}\right)^k$$ where $C>0$ is a constant and $k$ is the number of odd terms in the cycle (see Perigee, Apogee Upper Bounds from Belaga and Mignotte).

In fact, the desired bound can be proved by using Corollary 13 in Simons and de Weger (2005):

$$ x_{min} < A \cdot m \cdot k^{13.3}$$

where $x_{min}$ is the smallest term of the cycle, $A = 457.41 \ldots$ is a constant and $m$ is the number of sequences of consecutive odd terms in the cycle, making it a $m$-cycle. Note that $m \leq k$.

For a term $x$ of the cycle, we have $x \leq x_{min} \cdot 2^k$ as $T(y) \leq 2y$ for every odd integer $y$ (worst-case scenario). Finally, we get $$ x < A \cdot k^{14.3} \cdot 2^k$$ and, using the well-known inequality $n/k > \rho = \log_2 3 $ (see, e.g., here) and the obvious one $k \leq n$, $$ x < A \cdot n^{14.3} \cdot 2^{n/\rho}.$$

To conclude the proof, observe that the right hand side is smaller than $2^n$ for $n \geq 400$, whereas the minimal length of a non-trivial cycle is at least 17087915, according to Eliahou's paper. Moreoever, the bound $x < 2^n$ also holds for the trivial cycle (1,2).

Answer 2

$x_{max}<3^k<2^n$ (with $k$ the number of odd steps)

Collatz Conjecture: For a cycle where the maximum odd integer is $x_{max}$, does it follow that $x_{max} < 3^n$

Answer 3

As an addendum to @OlivierRozier's answer I'll show an estimate for an upper bound which is much sharper than that of Rhin - but only based on heuristics.

For $N$ (number of odd steps in my notation) and $S=\lceil N \cdot \log_2 3\rceil$ I conjecture that $$ {1 \over C \cdot N \cdot \ln N} \lt S \cdot \ln 2 - N \ln 3 \tag 1 $$ which holds, with $C=10$, for all $ 2< N <10^{1\,000\,000} $ with a remarkable smooth fitting curve (tested with Pari/GP with according digits precision). My derivations for $a_\min$, $a_\max$ and $\alpha=a_\text{mean}$ (denoting the according elements of a hypothetical cycle) are below; the result is that $$ \alpha \qquad (=a_\text{mean}) \lt C \cdot N^2 \ln N / 3 \qquad \text{with } C=11 \tag {2a}$$ $$ a_\min \lt (1-(2/3)^N) \cdot C \cdot N \ln N \qquad \text{with } C=11 \tag {2b}$$ $$ a_\max \lt 1.5^{N-1} \cdot ( C \cdot N \ln N +1)\qquad \text{with } C=11 \tag {2c}$$ In the tayloring of simple forms for the key-values $a_\min,a_\max,\alpha$ I leave small errors out; that errors are captured by the increase of $C=10$ to $C=11$ in the formulae. I think, that process of calculation can be made more precise with more work invested...

Pictures:

In the following a plot of the empirical (rational) values for the key values as colored dots, the bounds giving continuous curves of related colors, and the Rhin-bound for the $\alpha$-value for $N=1 \ldots 100$ is inserted to compare the preciseness of the estimates:

To see wider range, but not be killed by oversizing there is another plot where I use the most critical cases $N$, but only that $N$ from the continued fractions of $\log_2 3$, so $N \in \{1,5,41,306,15601,79335,190537 , \ldots \} $ Here $N=190537$ is the most critical point for the upper bounds; to satisfy the bounds at this coordinate I needed to adapt $C=11$ to compensate the neglected error-terms in the definition of the key-values.
Note: the $a_\max$ values increase too much for a good display in the picture, so for the $a_\max$-values I document their logarithms, see the related y-scale on the rhs of the picture.

Definitions for the key-values $\alpha, a_\min, a_\max$

(I'm using my notation here, because it is much error-provoking to translate notations "on-the-fly", so to say, please bear with me)

For a cycle in the odd elements $a_k$ with $N$ steps $3x+1$ and $S$-steps $x/2$ we can state the basic equation

$$ 2^S = (3+{1\over a_1 })(3+{1\over a_2 })\cdots(3+{1\over a_N }) \tag {3a}$$ We can assume a value $\alpha = a_\text{mean}$ as a rough mean-value of the $a_k$ and determine its value by the collection of the equal parentheses as product $$ 2^S = (3+{1\over \alpha })^N \tag {3b} $$ From this the value of the rough mean can be determined $$ 2^{S/N} = 3+{1\over \alpha } \tag {3c} $$ $$ \alpha = {1 \over 2^{S/N} -3 } \tag {3d} $$ This is the option to determine that value for one current selection of $N$ (and thus $S$). To have an upper bound functionally depending on $N$ we have to refer to the Rhin or to the Ellison bound, and develop differently: $$ {2^S \over 3^N} = (1+{1\over 3 \alpha })^N \tag {3f} $$ .... logarithmize ... $$ S \cdot \ln 2 - N \cdot \ln 3 = N \cdot \log(1+{1\over 3 \alpha }) \tag {3g} $$ apply Rhin-bound: $$ {1 \over 457 N^{13.3}} \lt S \cdot \ln 2 - N \cdot \ln 3 = N \cdot \log(1+{1\over 3 \alpha }) \tag {3h} $$ $$ {1 \over 457 N^{14.3}} \lt \log(1+{1\over 3 \alpha }) \\ {1 \over 457 N^{14.3}} \lt {1\over 3 \alpha } $$ arriving at $$ \text{Rhin bound:} \qquad \alpha \lt 153 N^{14.3} \tag {3i} $$ and because $\alpha$ is a rough mean for the $a_k$ we know that $a_\min$ must be smaller, and $a_\max$ must be larger than $ \alpha$.

Next, $a_\min$ for some given $N$ should be detected.
We assume, that -after we have already the idea of a rough mean $\alpha$ the $a_\min$ and $ a_\max$ should be identified by the "widest stretch" between the $a_k$, meaning $a_k={ 3a_{k-1}+1 \over 2}$ and thus the cycle should have the form of an "1-cycle" (in the Steiner/Simons-sense).
For such a cycle we have the formula for $a_\min $ ($=a_1$ by convention): $$ a_\min = {3^N -2^N\over 2^S - 3^N} $$ So, for a given pair $(N,S)$ we can give the value $a_1$ - which of course is mostly rational. To give a upper bound as a function dependend on $N$ I propose again to try my "$N \ln N$"-bound . Let's start with $$ a_\min = {3^N -2^N\over 2^S - 3^N} \tag {4a} $$ Then adapting this for the "$N \ln N$"-bound conjecture: $$ 2^S-3^N = {3^N -2^N\over a_\min} \\ 2^S/3^N = 1+{1 -2^N/3^N \over a_\min} $$ $$ S \ln2 - N \ln3 = \log( 1+{1 -2^N/3^N \over a_\min}) \tag {4b} $$ Getting now to the relation to $a_\min$: $$ { 1 \over 11 \cdot N \ln N} \lt S \ln2 - N \ln3 = \log( 1+{1 -2^N/3^N \over a_\min}) \\ { 1 \over 11 \cdot N \ln N} \lt \log( 1+{1 -2^N/3^N \over a_\min}) \\ { 1 \over 11 \cdot N \ln N} \lt {1 -2^N/3^N \over a_\min} $$ Finally $$ a_\min \lt (1 -2^N/3^N) \cdot 11 \cdot N \ln N \tag {4c} $$ and $$ \text{ub } a_\min = (1 -(2/3)^N) \cdot 11 \cdot N \ln N \tag {4d} $$ and to make the formula smoother, and for larger $N$ with vanishing error, we can simply say (conjecturally) $$ \text{ub } a_\min = 11 \cdot N \ln N \\ a_\min \lt 11 \cdot N \ln N \\ \tag {4e} $$ From that "1-cycle" structure we have also the formula for the $a_\max$ value. This is $$ a_N = 1.5^{N-1} \cdot(a_1+1) -1 \tag {5a} $$ from where the upper bound follows by simple insertion: $$ \text{ub } a_\max = 1.5^{N-1} \cdot 11 \cdot N \ln N \\ a_\max \lt 1.5^{N-1} \cdot 11 \cdot N \ln N \tag {5b} $$ With a bit more handwork this could be made more precise; for me at the moment it seems to be enough to have a rough proposal for the upper bound of the $a_\max$ - which using the sharp "$N \ln N$"-bound is $(3/2)^N \cdot 7 \cdot N \ln N$ . This is larger than $(3/2)^N$ but only by the factor $N \ln N$ and thus obviously smaller than $3^N$ and if $N$ has not its few smallest values ($N \ge 22$ to be exact), is also smaller than $2^N$.

Well, repeated: this "$N \ln N$"-bound-estimate is only a conjecture, I don't have a proof so far.