数学大好き宣言！

勉強メモ。おもしろいことを探していきたい。

トップ > 数学 > 【コラッツ予想】Eliahou の log3/log2 による考察

【コラッツ予想】Eliahou の log3/log2 による考察

数学

Wikipedia のコラッツ予想のページにこんな記述がある：

Eliahouは1993年の論文で、サイクルの最小値が 2^40 を超えるならば、周期の長さ p が

{\displaystyle p=301994a+17087915b+85137581c}
となることを示した。ここで{\displaystyle a,b,c}は非負整数で、{\displaystyle b\geq 1} かつ {\displaystyle ac=0}である。この結果は、{\displaystyle \log 3/\log 2}の 連分数展開と関連している。

連分数と関係するとは、どういうことだろう。とても興味深い。
そこで論文を見つけてきた：www.sciencedirect.com
その方法というのがとてもおもしろい。説明を試みる。

基本的定義、約束
・自然数から自然数への写像Tを、
T(n)={\begin{cases}n/2&{\mbox{}}n が偶数のとき\\(3n+1)/2 &{\mbox{}}nが奇数のとき\end{cases}}
で定義する。3n+1した後2で割るという「ショートカット」をしていることに注意。
・自然数nに対して、\Omega(n) = \{n, T(n), T(T(n)), \cdots , T^i(n), \cdots \}と定義する。以後、nを明示せずにΩと書くこともある。
・任意のx\in \Omegaに対してあるkが存在してT^k(x)=xとなるとき、\Omegaをサイクルという。
・サイクル\Omegaの元のうち、奇数だけを集めた部分集合を\Omega_1と書く。
・サイクル\Omegaの最大元をM, 最小元をmと書く(Ωを省略する)。

本題
Eliahouの方法の核は、次の不等式だ：\Omegaがサイクルのとき、
\dfrac{\log3}{\log2} \lt \dfrac{|\Omega|}{|\Omega_1|} \leq \dfrac{\log(3+m^{-1})}{\log 2}
この記事ではひとまずこの定理を示す。

証明：
\Omegaはサイクルだから、
\displaystyle \prod_{n\in \Omega} n = \prod_{n \in \Omega}T(n)
よって
\displaystyle \prod_{n\in \Omega} \frac{T(n)}{n} =1
ここで、
nが偶数のとき\dfrac{T(n)}{n}=\dfrac{1}{2},
nが奇数のとき\dfrac{T(n)}{n}=\dfrac{3+n^{-1}}{2}だから、
\displaystyle \prod_{n\in \Omega} \frac{T(n)}{n} = \prod_{n\in \Omega} (\frac{1}{2}) \prod_{n \in \Omega_1}(3+n^{-1})=(\frac{1}{2})^{|\Omega|} \prod_{n \in \Omega_1}(3+n^{-1})
よって
\displaystyle (\frac{1}{2})^{|\Omega|} \prod_{n \in \Omega_1}(3+n^{-1}) =1 だから
\displaystyle\prod_{n \in \Omega_1}(3+n^{-1}) = 2^{|\Omega|}

任意のnに対してm\leq n, M\geq nだから、
m^{-1}\geq n^{-1}, M^{-1}\leq n^{-1}.
よって
3^{|\Omega_1|} \lt (3+M^{-1})^{|\Omega_1|} \leq \prod_{n \in \Omega_1}(3+n^{-1}) \leq (3+m^{-1})^{|\Omega_1|}
よって
3^{|\Omega_1|} \lt 2^{|\Omega|} \leq (3+m^{-1})^{|\Omega_1|}
自然対数をとって
|\Omega_1|\log 3 \lt |\Omega|\log 2 \lt |\Omega_1|\log (3+m^{-1})
両辺を|\Omega_1|\log 2で割って
\dfrac{\log 3}{\log 2} \lt \dfrac{|\Omega|}{|\Omega_1|} \lt \dfrac{\log (3+m^{-1})}{\log 2}□

コンピューターによる計算で、2^68以下の数はコラッツ予想を満たす、つまりループしないことが分かっているから、mはかなり大きいとしてよい。右辺はmが大きければどんどん\frac{\log 3}{\log 2} に近付くから、 \frac{|\Omega|}{|\Omega_1|} は\frac{\log 3}{\log 2}のとても良い有理数近似でなければならないことになる。
連分数はとても良い近似を与えることが知られており、この話につながっていく。
一旦、終わり

終わりに(感想)
log3/log2 が出てくることは、ヒューリスティックな議論でもわかりそうだ。xが奇数のときT(x)=(3/2)x + (1/2) だが、十分大きいxでは+1/2の効果は小さくなり、だいたい(3/2)x と見なせる。
よって、T^k(n)=n とし、k回のうち、(3/2)x + (1/2) である回数をaとすると
n≒(1/2)^{k-a} (3/2)^b n よって(1/2)^{k-a} (3/2)^a≒1
整理して3^a≒2^k よって k/a ≒ \log3 / \log2
実際k=|\Omega|, a=|\Omega_1|だから近い式が得られた。
つまり、\log3 / \log2 は、ちゃんと最初の数に戻ってくるようなちょうどいい比率ということか。