コラッツ予想って帰納法でゴリ押しすれば証明できんじゃね？という思いつき

コラッツ予想とは

そもそもコラッツ予想ってなんぞやという話から。
これはドイツの数学者であるローター・コラッツが提唱した予想です。
小中学生でも理解できる単純な論題なのですが、証明が非常に難しく、80年以上もの間数学者の頭を悩ませている未解決問題として認定されています。
数学者の中には「ハマると病む難問」「宇宙人が仕掛けた罠」などと噂する人もいるとか。

内容は以下の通りです。
任意の自然数 n に対して、以下で定められる操作について考える。
・nが偶数の場合、nを2で割る
・nが奇数の場合、nに3をかけて1を足す
このとき、nの初期値が何であっても、有限回の操作のうちに必ず1に収束する。

例えば5なら5→16→8→4→2→1、7なら7→22→11→34→17→52→26→13→40→20→10→5→16→8→4→2→1という感じですね。一見するととても簡単なのですが、数によって挙動が全く違っていて、この挙動の不規則性が数学者を苦戦させる要因となっています。

つい最近になって、株式会社音圧爆上げくんという日本のベンチャー企業がこの問題に1億円もの懸賞金をかけました。解けたら一生働かずに済みます。夢がありますね。

コラッツ予想の現状

数学者は様々なアプローチでこれに臨んでいます。
特に有名なアプローチは、やはり「コラッツ予想は限りなく正しい」ことを証明したテレンス・タオ氏のものでしょう。なんでも偏微分方程式を使ったらしいです。整数問題に偏微分って、どう使えばいいか全く想像つきませんよね。

直感的に分かりやすいアプローチとして挙げられるのは、自然数を1から順に調べて統計的に挙動を予測する方法でしょう。このアプローチでは、なんと1から2^68までの全ての自然数について検証しているみたいです。2^10が大体10^3なので、10^18個を優に越す数は調べているという計算になりますね。怖。
そしてこのアプローチからは、
①1から2^68までの全ての自然数に対してコラッツ予想は成立する
②しかしその挙動の中に規則性は見つからない
という2つの結論が得られました。

今回使うアプローチ

本noteでは、前項で挙げた「自然数を1から順に調べて統計的に挙動を予測する方法」の結論を使って、コラッツ予想の帰納法的証明を試みます。

何をやるかというと、先程のアプローチで得られた「1から2^68までの全ての自然数に対してコラッツ予想は成立する」という結論の活用による問題の単純化です。
このアプローチはいくら行ったところで、「コラッツ予想は限りなく正しい」ことを証明するのみで、「全ての自然数に対してコラッツ予想は成立する」ことを証明することはできません。なぜなら数は無限に存在し、1からnまでの数に対して検証を行ったところで、n+1以上の数は残ってしまうためです。

しかし、「全ての自然数は、コラッツ予想の操作過程において自身より小さい自然数となる」ことを証明できたらどうでしょうか？
例えば2^68+1がコラッツ予想の操作過程において2^68以下の自然数になったとします。そうしたら、2^68以下の全ての自然数は1に収束するわけですから、2^68+1も1に収束するはずですよね。
2^68+2は2で割ると2^34+1となり、2^34+1が1に収束することは既知なので、2^68+2も1に収束するはずです。
これで理論上、「2^68+2以下の全ての自然数に対してコラッツ予想が成立する」ことが証明できます。
そして2^68+3がコラッツ予想の操作過程で2^68+2以下となれば……
以下この繰り返しにより、コラッツ予想は帰納法的に証明できるはずです。

実際にやってみる

ということで、やります。

証明1：全ての自然数は、コラッツ予想の操作過程において自身より小さい自然数となる

(1)nが偶数のとき
2で割る操作によりn/2となるため、正しい。

(2)nが奇数のとき
全ての奇数はn=4k+1、及びn=4k+3に分類できる。
(2-1)n=4k+1のとき
3(4k+1)+1=12k+4
(12k+4)/2*2=3k+1となるため、正しい。
(2-2)n=4k+3のとき
3(4k+3)+1=12k+10
(12k+10)/2=6k+5

nが偶数のとき、及び4k+1のときに証明を成立させることは可能ですが、4k+3に対して証明が手詰まりになってしまいますね。ここで、全ての4k+3が8k+3、及び8k+7になることを生かして場合分けを細かくしてみます。
(2-2-1)n=8k+3のとき
3(8k+3)+1=24k+10
(24k+10)/2=12k+5=4(3k+1)+1
(2-2-2)n=8k+7のとき
3(8k+7)+1=24k+22
(24k+22)/2=12k+11=4(3k+2)+3
どうやら8k+3はコラッツ予想の操作過程で4k+1となるようです。4k+1に対して証明が成立することは既知なので、うまく使えそうな気はするんですが。うーん。

8k+7については16k+7、16k+15に分類して更に場合分けを細かくしてみます。
(2-2-2-1)n=16k+7のとき
3(16k+7)+1=48k+22
(48k+22)/2=24k+11=8(3k+1)+3
(2-2-2-2)n=16k+15のとき
3(16k+15)+1=48k+46
(48k+46)/2=24k+23=8(3k+2)+7
16k+7もコラッツ予想の操作過程で8k+3となり、最終的に4k+1となりそうですね。この法則性でいくと、32k+15も32k+15→16k+7→8k+3→4k+1という過程を経て4k+1になりそうです。つまり、「全ての奇数は、コラッツ予想の操作過程において4k+1となる」ことが言えそうですね。というわけで、証明をこちらに切り替えてみます。

証明2：全ての奇数は、コラッツ予想の操作過程において4k+1となる

帰納法で証明します。
仮定：f(m)=2^(m+2)k+2^(m+1)-1はコラッツ予想の操作過程において4k+1となる。

(i)m=1のとき
f(1)=8k+3より、自明。
(ii)m=n-1において仮定が成立するとき
仮定より、f(n-1)=2^(n+1)k+2^n-1はコラッツ予想の操作過程において4k+1となる。
f(n)=2^(n+2)k+2^(n+1)-1
→奇数の操作を加え、3*2^(n+2)k+3*2^(n+1)-2
→偶数の操作を加え、
3*2^(n+1)k+3*2^n-1
=2^(n+1)(3k+1)+2^n-1
=f(n-1)
従って、m=nにおいても仮定は成立。
よって、f(m)はコラッツ予想の操作過程において4k+1となる。

続いて、g(m)=2^(m+2)k+2^(m+2)-1についても考えてみます。
k=2aのとき、
g(m)=2^(m+3)a+2^(m+2)-1=f(m+1)で、4k+1となる。
k=2a+1のとき、
g(m)=2^(m+3)a+2^(m+3)-1=g(m+1)で、同形に回帰する。
k=2a+1となり続ける場合を除いて、4k+1となりそうです。そしてk=2a+1となり続ける場合、g(m)は無限に大きくなり続けるので、やはり全ての奇数は4k+1となると言えるのではないでしょうか。

……しかし4k+1の使い方が思いつかないのでダメですね。

結論

実際に証明を試みて、感覚的にも理論的にも正しそうだと思いはしたのですが、「限りなく正しい」と「正しい」の差を埋めるのがどこまでも難しい問題なんですね、これ。さすがに80年の重みは違います。

よって結論、むり！！！！！(終)