2

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.

Daniel S.
  • 530
  • 2
    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 '22 at 22:10
  • I'm trying to develop a computer aided proof for iteratively refuting cycles of greater lengths. I have something like it, but it requires large maximum cycle members. A fixed lower bound is therefor not suitable. I need something that depends on the cycle length and can be increased for larger cycles. – Daniel S. Jul 14 '22 at 22:43
  • @RoddyMacPhee I'm not quite getting what you mean. Can you add an explanation in plain English, please? – Daniel S. Jul 14 '22 at 22:46
  • 1
    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 ( https://go.helms-net.de/math/collatz/CombinatoricalCountForNumberOfCyclicOrbits.pdf ) 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". – Gottfried Helms Jul 14 '22 at 23:29
  • (... cntd...) At the moment I've not much energy for this; if you like my derivation and my conjecture about an upper bound (below table 2.2) feel free to compose an own answer; I'll likely be absent next days or maximally shall be a bit lurking... – Gottfried Helms Jul 14 '22 at 23:34
  • ehhm, adding one more explanation: the lower bound for the maximal element in a cycle of length $N$ is the "mean"-value $a_\mu$ which I show in table 2.1 and 2.2. This table shows this for a specific subset of $N$'s - for that for which the $a_\mu$-value is maximal. In table 2.3 I show some example for the "opposite "subset of $N$'s: where the mean values are smallest (and thus the maximal values are thus as well lower-bounded. Rigid bounds are provided by formulae of G. Rhin and W. Ellison (not documented there) and a better estimate conjectured by me. – Gottfried Helms Jul 14 '22 at 23:49
  • 1
    @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? – Daniel S. Jul 15 '22 at 05:39
  • @Daniel - Well, this is done with Pari/GP and it is easy to document this up to $N$ with a million digits - just 2 simple formulas to evaluate. This means to get the heuristic information. Explicite bounds, as far as they depend on the distance $2^S - 3^N$ or $S \cdot \ln 2 - N \cdot \ln 3$, can be derived by the Ellison bound resp the Rhin-bound (Rhin has been discussed here several posts). However I didn't find something more useful than the pure observation with this; if it shall have any chance to be helpful for the conjecture we need something else related additionally ... – Gottfried Helms Jul 15 '22 at 06:20
  • A bit more discussion about Ellison & Rhin-bounds, and my conjecture, can be found in the "sandbox" https://math.meta.stackexchange.com/a/4668. This was intended to expand to a full initial posting for "big list" and be posted then to MSE. But I'm not strong these days and cannot well proceed. If this is as well in your direction, why not step up on this and expand/make complete that sandbox-draft of mine? – Gottfried Helms Jul 15 '22 at 06:24
  • 4
    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. – Peter Jul 15 '22 at 13:11
  • @Peter the heuristical argument suggests that the probability of a large cycle is extremely low, close to 0, but larger than 0. The same argument suggests that the probability of a diverging sequence is exactly 0. So the heuristic argument is even stronger against diverging sequences than against large cycles. – Daniel S. Jul 16 '22 at 11:52
  • I think that the $3/4$-argument (which I think you mean) is not the only argument in the case of cycles. The wikipedia article contains a lot about possible cycles , but nothing about possible diverging sequences is mentioned. So I wonder whether we actually can be "surer" that diverging sequences do not occur. – Peter Jul 16 '22 at 12:44
  • @Peter Put another way: Is there a heuristic argument for the probability of large cycles to be exactly 0? Because there is such a strong argument against diverging sequences. If there is no such strong argument against large cycles, then the argument against diverging sequences is indeed stronger. But anyways, I invite you to contribute to my other question at https://math.stackexchange.com/questions/4494017/whats-the-probability-of-large-cycles-in-the-collatz-graph . – Daniel S. Jul 16 '22 at 12:49
  • That is the point : I never heard of a strong argument against diverging sequences apart from the $3/4$-argument. For the cycles, we know that they must be awfully long, but for the diverging sequences, there is no similar formulation to convince one that they should not exist. – Peter Jul 16 '22 at 12:55
  • @Peter A diverging sequence is longer than any cycle. That's exactly the difference which makes it's probability 0 and the probability of cycles greater than 0. – Daniel S. Jul 16 '22 at 13:42
  • 1
    @ 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? – Daniel S. Jul 19 '22 at 09:54

1 Answers1

2

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.

image1 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 image2 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()$...