2
$\begingroup$

In studies of the Collatz conjecture, what research has asserted the existence of a $k$-length cycle and drawn conclusions about its smallest element $m$? In particular, about the behavior of $m$ as $k \rightarrow \infty$?

I know that this question tried, this question speculated, and that the existence of $k$-length cycles given $m$ has been studied a lot. For example Lagarias (1985) used a result by Yoneda that $m > 2^{40}$ and a theorem by Crandall (quoted as Theorem I) to prove that there are no nontrivial cycles of period length less than $k = 275,000$. I am interested in the other direction, of properties of $m$ given $k$.

EDIT: I am especially interested in lower bounds for $m$, and whether it has been shown that $m \rightarrow \infty$ as $k \rightarrow \infty$ (thanks to @rukhin for the answer concerning an upper bound on $m$).

Many thanks in advance.

$\endgroup$
  • 1
    $\begingroup$ see my question math.stackexchange.com/q/2848446/1714 . I have discussed the same problem there, but for the generalized Collatz-problem $mx+1$ instead of $3x+1$ only. Just insert $3$ for $m$ and use the formulae there. Note, that for $m=5$ the formulae give immediately the known values for the first 3-step-cycle ($a_1 = 13$) $\endgroup$ – Gottfried Helms Aug 17 '18 at 14:12
2
$\begingroup$

Here is a table, based on computation of my earlier answer (see there). I got the N for which the lower bounds $a_\text{min_1cyc}$ are relatively highest by the continued fractions of $\lambda=\log(3)/\log(2)$.

$a_m$ is the very rough "mean" value of all $a_k$ by ${1\over 2^{S/N}-3}$, such that it is a good upper bound for $a_\min$.

A slightly better (=smaller) upper bound occurs, when the $a_1 \cdots a_N$ are assumed to be packed as tight as possible (though all different), so roughly in steps of $3$, and still solving rhs = lhs. I called it $a_\text{min_compact}$. Because the exact computation is time (or memory)-consumptive I've shown this only for $N \le 10000$
The improvement over $a_m$ however is only marginal, so this reduced display may not be critical.

A lower bound, as you have asked, occurs if we assume the $a_k$ being in a so-called "1-cycle" which means also that they have the widest distance of each other and are consecutive iterates $a_{k+1}=(3a_k+1)/2$.
The minimal $a_k$ of any type of cycle cannot be smaller than $a_\text{min_1cyc}$. I was surprised myself when I saw such large values for the large N ,btw.

              N     lhs=2^S/3^N      amin_1cyc             amin_compact      am   
   ----------------------------------------------------------------------------------
              1 (1+0.333333333333): 1.00000000000  <= a_1 <=     0 < 1 
              5 (1+0.0534979423868): 16.2307692308 <= a_1 <=    25 < 31.8135643475 
             41 (1+0.0115288518086): 86.7389013502 <= a_1 <=  1133 < 1192.08534275 
            306 (1+0.0010227617964): 977.744772545 <= a_1 <= 99323 < 99780.7914439 
          15601 (1+0.0000181947538): 54960.8972938 <= a_1 <= undef < 285817586.219 
          79335 (1+0.0000036647273): 272871.592753 <= a_1 <= undef < 7216102492.69
         190537 (1+0.0000000645075): 15502072.2362 <= a_1 <= undef < 984572810981. 
       10781274 (1+0.0000000122069): 81920324.7724 <= a_1 <= undef < 2.9440182 E14 
      171928773 (1+0.0000000017892): 558903955.481 <= a_1 <= undef < 3.2030557 E16 
      397573379 (1+1.05843488 E-10): 9447912335.13 <= a_1 <= undef < 1.2520794 E18 
     6586818670 (1+1.01231253 E-11): 98783722251.5 <= a_1 <= undef < 2.1689015 E20 
   137528045312 (1+8.98654870 E-13): 1.1127742 E12 <= a_1 <= undef < 5.1012555 E22 
  5409303924479 (1+6.59287766 E-14): 1.5167883 E13 <= a_1 <= undef < 2.7349230 E25 
 11571718688839 (1+1.28966827 E-14): 7.7539319 E13 <= a_1 <= undef < 2.9908772 E26 
431166034846567 (1+1.33377903 E-15): 7.4974937 E14 <= a_1 <= undef < 1.0775548 E29 

A plot of that empirical values suggests, that the square-roots of the maximal $am$ (relevant $N$ indicated by the convergents of the continued fraction of $\log_2(3)$) are roughly equivalent to $N$ (the $a_{min:1cyc}$ even to seem to be equivalent to $N$). (The term "Perigee" comes from Belaga's work which has kindly been linked to by @rukhin)

image

$\endgroup$
2
$\begingroup$

Belaga gives an upper bound on the "perigee" of a cycle; the reference can be found here.

EDIT: For a lower bound on the perigee, see my response here. It follows from a Bohm-Sontacchi-style argument.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.