はじめに
表題の件について、既存研究[1]よりも単純なアプローチを発見したため、ご報告します。
既存研究とは「長さ」の定義が若干異なる点、私自身がまだ既存研究をあまり読み込めていない点について、ご了承ください。
コメント、ご指摘いただけましたら幸いです。
記号、用語の定義
- 「サイクル」とは、ある数に対してコラッツ操作を複数回適用した際に元の数に戻ってくるまでの一連の過程を指します。
- サイクルの「長さ」とは、サイクルの中で3倍して1を足す操作を行う回数を指します。
- 長さnのサイクルで出現する数字を、x_nで表します（x_nは素因数に2と3を持たない正の整数）。x_{k+1}は、x_kに3をかけて1を足した後に、奇数になるまで2を割り続けた数になります。また、x_{n+1}はx_1になります。
-
x_kからx_{k+1}を導出する際に2で割る回数をp_kで表します。
- 「この数以下の数については全てコラッツ予想が成立する」という最大の数をMで表します。2024年現在、既知のMは2^{68}です[2]。
長さnのサイクルの存在有無に関する判定式
n \log_2 \left(3 + \frac{1}{M} \right) - [n \log_2 3] < 1
であれば、長さnのサイクルは存在しません。ここで、[]はガウス記号を表しています。
導出過程
まず、定義より、以下の等式が成立します。
\begin{aligned}
3 x_1 + 1 &= x_2 \cdot 2^{p_1} \\
3 x_2 + 1 &= x_3 \cdot 2^{p_2} \\
\vdots \\
3 x_n + 1 &= x_1 \cdot 2^{p_n}
\end{aligned}
左辺と右辺についてそれぞれ総積をとると、
\begin{aligned}
(3 x_1 + 1) (3 x_2 + 1) \cdots (3 x_n + 1) &= x_1 x_2 \cdots x_n \cdot 2^{p_1 + p_2 + \cdots + p_n} \\
2^{p_1 + p_2 + \cdots + p_n} &= \frac{(3 x_1 + 1) (3 x_2 + 1) \cdots (3 x_n + 1)}{x_1 x_2 \cdots x_n} \\
&=\left(3+\frac{1}{x_1}\right)\left(3+\frac{1}{x_2}\right) \cdots \left(3+\frac{1}{x_n}\right)
\end{aligned}
となり、両辺に底が2の\logをとると、
p_1 + p_2 + \cdots + p_n = \log_2 \left\{\left(3+\frac{1}{x_1}\right)\left(3+\frac{1}{x_2}\right) \cdots \left(3+\frac{1}{x_n}\right) \right\}
となります。
右辺の下限値について、各x_kが無限大に近づいた場合に、右辺はn \log_2 3となります。
次に、右辺の上限値について、各x_kは少なくともMより大きいため、右辺はn \log_2 \left(3 + \frac{1}{M} \right)よりも大きな値をとりません（各x_kの値が全て異なることを利用すれば最大値をもう少し引き下げられますが、計算コストが大きくなります）。
すなわち、p_1 + p_2 + \cdots + p_nのとりうる値の範囲は、
n \log_2 3 < p_1 + p_2 + \cdots + p_n < n \log_2 \left(3 + \frac{1}{M} \right)
であり、この範囲の中に整数値が存在しなければ、長さnのサイクルは存在しないといえます。
つまり、n \log_2 3の小数部分n \log_2 3 - [n\log_2 3]に、上限値と下限値の差n \log_2 \left(3 + \frac{1}{M} \right) - n \log_2 3を加えた値が1を上回らなければ、長さnのサイクルは存在しません。これを整理すると、前節の判定式になります。
なお、上限値と下限値の差は
n \log_2 \left( 1 + \frac{1}{3M} \right)
と変形することができ、Mに2^{68}を代入すると、約1.63n \times 10^{-21}となります。
実際の計算
実際に計算を行ってみたところ、n=72057431991で初めて反例が出ました。
この結果は文献[3]と一致します。
よくよく見ると文献[1][3]と同じような式になっていたので当然の結果でした。。。
（ちなみに、文献[1][3]では、サイクルを形成する場合は2で割る回数と3をかけて1を足す回数が\log_2 3に近づくことを利用して、\log_2 3の連分数近似との誤差を考慮しているようです。まだ詳細読めてませんが。）
以降では、各x_kの取りうる値をより厳密に検証し、上限値の引き下げを試みたいと思います。
上限値の引き下げ
文献[3]では、Mの値が4.35849 \times 10^{21}以上になれば、n=72057431991のサイクルの存在可能性を否定できると言っています。これを引き下げてみようと思います。同じような試みは文献[4]でも行われており、こちらでは3.26969 \times 10^{21}までの引き下げに成功しています（元のサイクルを複数のk-サイクルに分割して、各k-サイクルの下限値を考慮しているようです）。
ここから検証に入っていきたいと思います。まず、各x_kについて、値が最小となるのは、3倍して1を足した後にMを下回らない範囲で2で割り続けていった場合であると考えられます。
これを実際に計算していき、\log_2 3との誤差の比
\frac{\sum_{k=1}^{n} \log_2 \left(3 + \frac{1}{x_k} \right) - n \log_2 3}{n \log_2 \left(3 + \frac{1}{M} \right) - n \log_2 3}
を求めると、概ね0.7214になります（計算が大変なのでn=100000くらいまでしか回していませんが、基本的にはnが大きくなるほど収束傾向にあり、0.7214は上回らないと思われます）。
ここで、誤差をn \log_2 \left( 1 + \frac{1}{3M} \right)の0.7214倍と考えると、n=72057431991のサイクルの存在可能性を否定するためのMの値は3.14421 \times 10^{21}以上になればよいことになります。
誤差の比が\frac{1}{2 \ln 2}に収束しそうな気配があるのですが、私の力では解析的にこれを導出することができず。。。
参考文献
[1] Eliahou, Shalom (1993-08-01). “The 3x+1 problem: new lower bounds on nontrivial cycle lengths”. Discrete Mathematics 118 (1): 45–56. https://doi.org/10.1016%2F0012-365X(93)90052-U
[2] Barina, D. Convergence verification of the Collatz problem. J Supercomput (2020). https://doi.org/10.1007/s11227-020-03368-x
［3］https://www.probleme-syracuse.fr/cargo/Sinisalo_collatz.pdf
[4] https://arxiv.org/pdf/2201.00406
Discussion