# Are there known lower bounds for the values in a cycle in the Collatz graph?

I've found kind of the reverse of what I'm looking for. I've found lower bounds for the length of a cycle when the cycle's members have a certain minimum value. For example, they can be found on Wikipedia here: https://en.wikipedia.org/wiki/Collatz_conjecture#Cycle_length

I'm looking for the reverse: For a given cycle length, I want to get lower bounds for the members of the cycle. I'm specifically interested in the lower bound of the maximum value in the cycle.

• Your linked Wikipedia article says "As of 2020, the conjecture has been checked by computer for all starting values up to $2^{68} ≈ 2.95×10^{20}$", so any potential cycle must consist entirely of numbers higher than that. Is that good enough for you?
– Dan
Jul 14, 2022 at 22:10
• I've just recently produced a table with such values, although in another context (in another question here in MSE). Here is the pdf-file ( go.helms-net.de/math/collatz/… ) I explain the method how to compute such bound. The relevant table is in part 2, it shows lower bound, roughly mean (=upper bound for the smallest element), upper bound. Interestingly, but even much intuitively, the lower- and upper bounds are taken for some potential cycle, when it were a "1-cycle". Jul 14, 2022 at 23:29
• @GottfriedHelms you are working on exactly the same problem as me, you are heading in the same direction, and you're far ahead of me. What's your conclusion so far? Is it still a lot of computational work to check for cycles of some large length N+S? Jul 15, 2022 at 5:39
• If the Collatz conjecture is false than probably because there exist diverging collatz sequences. The heuristical evidence against the existence of cycles other than $(4,2,1)$ is overwhelming. Jul 15, 2022 at 13:11
• @ close voters! This question is perfectly fine. If you really think it violates community rules or is not specific enough, then please state the details. Otherwise, how am I supposed to understand and improve my next question? Jul 19, 2022 at 9:54

For cycles of a given length N there are at least 3 bounds:

• a value for a roughly mean of all elements: $$a_{\text{mean}}$$. It is
• an upper bound for the minimal element $$a_\min$$ : $$\qquad a_\min \le a_\text{mean} \qquad$$ and
• as well a lower bound for its largest element $$a_\max$$:$$\qquad a_\text{mean} \le a_\max \qquad$$
• a lower bound $$a_{\small{lb}}=a_{\text{min_1cycle}}$$ for $$a_\min$$ from the formula for the 1-cycle, which has the widest spread between its elements. This is because only increasing steps occur from first to last element until from the last element by "one step" the orbit falls down to the first element
• an upper bound $$a_{\small{up}}=a_{\text{max_1cycle}}$$ for $$a_\max$$ from the formula for the 1-cycle - for the same arguments as before.

Given some $$N$$ (the number of odd elements, number of the $$3x+1$$-operations),
... we find the number $$S$$ of $$x/2$$-operations by $$S=\lceil N \log_2 3\rceil \qquad \qquad$$ (1a)
... and call the value $$S-N=B$$ for notational convenience. $$\qquad \qquad$$ (1b)

From the transfer-rule in the "Syracuse"-style on the odd numbers $$a_k$$ $$a_{k+1}= {3a_k+1 \over 2^{A_k}} \tag {2a}$$ we denote the product-equality-formula $$a_1 a_2 \cdots a_N = {3a_1+1 \over 2^{A_1}}{3a_2+1 \over 2^{A_2}}\cdots {3a_N+1 \over 2^{A_N}} \tag {2b}$$ and develop $$\overset{\underbrace{ 2^{A_1}2^{A_2}\cdots 2^{A_N} }}{ 2^S} = \left(3+{1 \over a_1}\right)\left(3+{1 \over a_2}\right) \cdots \left(3+{1 \over a_N}\right) \tag{2c}$$

Average $$a_\text{mean}$$ given N

Now if we have an average value $$a_\text{mean}$$ with $$a_1,a_2,...a_N = a_\text{mean}$$ then this eqation goes to $$2^S = \left(3+{1 \over a_\text{mean}}\right) ^N \tag{3a}$$ and from this $$2^{S/N} = 3+{1 \over a_\text{mean}} \\ 2^{S/N} -3 = {1 \over a_\text{mean}} \\ a_\text{mean} = {1 \over 2^{S/N} -3} \tag{3b}$$

The lower bound for $$a_\min$$ from the 1-cycle formula
From the 1-cycle equation we find the first element $$a_1$$ which is also assumed to be the smallest element: $$(a_\min=)\qquad a_1 = {3^N - 2^N \over 2^S-3^N } \tag{4a}$$ which can, for further analyses, be rewritten as $$a_1 +1 = {2^S - 2^N \over 2^S-3^N } \\ a_1 +1 = 2^N {2^B - 1 \over 2^S-3^N } \tag{4b}$$

The upper bound $$a_\max$$ from the 1-cycle formula
Accordingly to the previous, $$a_N$$ has in the 1-cycle a simple determination from $$a_1$$: $$\begin{array} {rll} a_N &= ({3\over2})^{N-1} (a_1+1)-1 \\ a_N &= ({3\over2})^{N-1} \left( 2^N {2^B - 1 \over 2^S-3^N } \right) -1\\ a_N &= 3^{N-1} \cdot 2 {2^B - 1 \over 2^S-3^N } -1 \\ \end{array} \tag{5a}$$

Note: Due to the notation of the transferfunction in the "Syracuse" style, we do not "see" one more intermediate number, larger than $$a_n$$, but which occurs in the transfer from $$a_N$$ to $$a_1$$. This is the (even) number $$c=3a_N+1$$ which were the maximal number occuring in the cycle when the original COllatz-transfer function were used, and which were $$d={3a_N+1 \over 2}$$ but which is even as well and thus gets skipped over in the notations of the "syracuse"-style. It is to mention that $$d$$ has the form $$d = {3 \cdot (3^{N-1} \cdot 2 {2^B - 1 \over 2^S-3^N } -1 )+1 \over 2} \\ = 3^N \cdot {2^B - 1 \over 2^S-3^N } -1 \tag{5b}$$ which is even, has to be divided by more factors $$2$$ and is thus not mentioned in the syracuse-notation before the next odd element $$a_1$$ in the cycle .

So we have formulae for the widest possible interval (and as well a rough mean value) in which the elements $$a_k$$ of an assumed cycle can lay: $$\text{given some } N \implies a_\min \le a_1 \cdots a_k \cdots \lt a_\text{mean} \le \cdots a_k \cdots \le a_\max \tag{6}$$

The hullcurves of the bounds when looking at $$N = 1...\infty$$
So far we have determinations for the range for the $$a_k$$ given one individual $$N$$. But this does not give a smooth impression: when increasing $$N$$ then that intervals and the means jitter seemingly wild and unpredictably.

The most general answer to your question is now, whether there are some smooth curves - lower bounds for the $$a_\min$$s and for the $$a_\text{mean}$$s along the increasing $$N$$.

The most simple result here is surely that the lower bound for $$a_1$$ in a 1-cycle must be $$1$$ because for increasing $$N$$ the cases where $$2^S \to 2 \cdot 3^N$$ we get a $$3^N$$ in the denominator and this cancels the whole term in (4a) towards $$1$$. Those extreme cases occur when $$N$$ are (generalized) convergents of the continued fraction of $$\log_2(3)$$ , for instance $$N \in \{ 4,7,12,53,359,665,...\}$$. For the mean values $$a_\text{mean}$$ we find empirically that the minimal $$a_\text{mean}$$ approach $${a_\text{mean} \over N} \to (\log 2)^2$$, but from below.

edited The formulae that I know give hullcurves as upper instead of lower bounds when applied for the mean and minimal values, but might be interesting/useful here anyway.

We find, that the jittering of the ranges has it extremes at $$N$$ from the convergents of the continued fraction of $$\log_2(3)$$ (and the "generalized" convergents, but which are often not explicitely mentioned in related articles).

Moreover, there are smooth functions of $$N$$, which give a upper bound for the $$a_\min$$ and $$a_\text{mean}$$. Those are so far as I know all derived from properties of linear forms of logarithms, here of logarithms of $$2$$ and $$3$$.

One meanwhile well known formula is the -here in MSE often called- "Rhin-bound", after a result of G. Rhin such that $${1 \over 457 N^{13.3} } \le S \log 2 - N \log 3 \qquad \text{ for} N \ge 1 \tag{7a}$$ With this, we can reformulate the $$a_\text{mean}$$ formula $$\begin{array} {rl} a_\text{mean} &= {1 \over 2^{S/N}-3} \\ 2^{S/N}-3 &={1 \over a_\text{mean}} \\ {2^{S/N} \over 3} & =1+{1 \over 3 a_\text{mean}} \\ S/N \log 2 - 1 \log 3 &= \log \left( 1+{1 \over 3 a_\text{mean}} \right) \end{array} \tag{7b}$$ The lhs here can easily be identified with the rhs in the "Rhin-bound" and with the adaption for $$N$$ we get $$\begin{array} {rl} {1 \over 457 N^{13.3}\cdot N } &\le \log \left( 1+{1 \over 3 a_\text{mean}} \right) \end{array} \tag{7c}$$ In the rhs the $$\log$$-expression can be removed because it goes quickly to the fractional value alone when this becomes small: $$\begin{array} {rl} {1 \over 457 N^{13.3}\cdot N } &\le {1 \over 3 a_\text{mean}} \\ 3 a_\text{mean} &\le 457 N^{14.3} \\ a_\text{mean} &\le 153 N^{14.3} \end{array} \tag{7d}$$

Similarly this can be done to get a smooth upper-bound function for the $$a_\min$$.

Unfortunately that upper bounds (=lower bounds for the $$S \log 2 - N \log 3$$-expressions) are really weak (while they are still sufficient, for instance, to disprove the existence of an 1-cycle) and it is surely interesting, to find some other estimates which are tighter to the empirical values (of course still a smooth curve is expected). By the empirical heuristics up to $$N \le 10^{2\,000\,000}$$ I've conjectured a stronger lower bound for the logarithm-difference: $${ 1\over 10 N \log N} \lt S \log 2 - N \log 3 \tag {7e}$$ which can as well be expressed in the possibly more common form $${ 1 \over C N^2 \log N} \lt { S \over N} - \log_2 3 \\ \qquad \qquad C=10 \log 2 \approx 6.9 \tag {7f}$$ where diverging from the commonly used exponent $$N^{2+\epsilon}$$ I removed the $$\epsilon$$ and replaced it by the $$\log N$$-factor.

There is no proof for this yet, but the curve is a much nicer hullcurve and much stronger lower bound than the Rhin-curve.

For the upper bound of $$a_\text{mean}$$ we get by this $$\begin{array} {rl} { 1\over 10 N^2 \log N} &\lt S/N \log 2 - 1 \log 3 = {1 \over 3 a_\text{mean}} \\ 3 a_\text{mean} &\lt 10 N^2 \log N \\ a_\text{mean} &\lt 4 N^2 \log N \end{array} \tag {7g}$$

Similarly the other bounds (in the sense of (eq 6)) can be retrieved from this.

A visual comparision
An excerpt from another (so far only planned) answer elsewhere.
I denote my conjectural limit-formula with the logarithm instead of the $$\epsilon$$ in $$N^{2+\epsilon}$$ as "LBLambda", took the Rhin-bound and as well another bound from W. Ellison. The latter is as well derived from the "linear forms in logarithms" but puts its estimate in a different formula. The term "Lambda" is short name for the expression $$\small {\Lambda(N) = S \log 2 - N \log 3}$$

(...) To trigger the interest, here some pictures, how the three estimates behave in contrast to the empirical values. Here I adapted the Ellison-estimate to a $$\Lambda()$$-version. We see, that the empirical $$\Lambda()$$ jitter between $$0$$ and $$1/2 \cdot \ln 2$$ (blue dots), the values at $$N=\{2,5,12,53,...\}$$ show very small distances, and even decreasing towards zero. The idea is to have a continuous function $$f(N)$$ which can supply a lower bound, such that we can say $$\Lambda(N,S) \gt f(N)$$ .

The red curve for the Ellison-estimate is below of the empirical values only for $$N \gt 17$$ while the green curve for the Rhin-estimate is so near the zero-line, that we barely see it.
My estimate shown by the brown curve is always below the $$\Lambda()$$ .
To see a bit more detail, and to get aware of the basic characteristics of the estimates, a picture in log()-scalings is more appropriate. Picture 2: x,y logarithmic scaling Here we see the characteristics better. All three methods of estimates work for $$N$$ towards $$=200$$. Ellison took a much different shape compared with Rhin's, and while Rhin's lower bound is unfortunate small over the whole range, the Ellison's is initally too large, then better than Rhin's but from about $$N \approx 700$$ it decreases much faster than Rhin's. So, for the larger $$N$$, Rhin's lower bound should be preferred, but for the moderate values in $$N$$ Ellison's estimate gives a simpler formulation and a better lower bound.
But the "LBLam"-function has the best characteristic; it is nearly parallel to a lower hullcurve, and also is valid from the smallest $$N=2$$ on. That this property holds forever, that means the formula is analytically useful for all $$N$$, has not been proved, but empirical heuristic show that it holds for all $$N$$ up to $$1$$ million decimal digits and is always tight to the most extreme small values of $$\Lambda()$$...