~ Consideration on Collatz conjecture ~

ごあいさつ

こんにちは。タンジェントこと田中ジェン太郎と申します。
いつもは VTuber(ごっこ) をして、数学とは全く関係ないことで遊んでいます。
本記事は、コラッツ予想について、田中ジェン太郎の主観から考えてみるものです。
過去に某サイトで同様の記事を書いたのですが、残念なことにそのサイトが閉鎖してしまいましたので、
新たにこちらのサイトにてお世話になります。
何かわかったことがあれば追記していくというやり方で書いていきますので、
見出しの前後の直接的な関連性がなくただ雑多で脈絡がないものになっていきますが悪しからず。
よろしくお願いいたします。
あわよくばコラッツ予想を解明して1.2億円をもらいます。

コラッツ予想とは

コラッツ予想

「偶数の時は$2$で割り，奇数の時は$3$倍して$1$足す操作を繰り返すと，いつかは必ず$1$を得るであろう」
というのがこの予想の主張です。
　ここで、$f(\cdot )$に自然数$n$を代入して次の値$f(n)$を算出することを、
「$n$に関数$f$を作用させる」と呼ぶことにし、
自然数$n$に対してコラッツ予想の主張が成立する場合、
｢$n$はコラッツ予想に従う｣と呼ぶことにします。
（後述の「ショートカット形式」についても同様）

コラッツ予想のショートカット形式

$n$が奇数のとき、$3n+1$は明らかに偶数であるため、
コラッツ予想は以下のショートカット形式として考えることもできます；

今回はこのショートカット形式を採用し議論を進めます。理由は後述。

もしも予想が正しくなかったら？

もしも予想が正しくない場合、つまり、もしもコラッツ予想に従わない数が存在する場合、
それは複数存在します。操作をした場合の数の移り変わり方は以下の$2$通りです；

• 循環する（元の数に戻ってくる）
• 無限に発散する（有界でない）

そして、（存在する場合）コラッツ予想に従わない数について、以下のことが分かっています。

つまり、コラッツ予想が正しいかどうかを確かめる際は、$4$で割って$3$あまる数さえ調べればよいことになります。

連続で奇数を得続けると？

なぜショートカット形式$T$を用いるか

通常の形式$f$を用いる際、奇数に作用させて得られる数は必ず偶数になりますが、
ショートカット形式の関数$T$に奇数を代入して得られる数は奇数である場合もあります．
例えば$n=7$のとき；

ショートカット形式$T$で奇数を得続けたとき

次ではショートカット形式$T$を用いて、奇数を連続で得続ける回数と、
$T(n)$に代入する自然数$n$の関係性について議論します。
関数の合成の過程で必ず偶数を挟む$f$より、奇数を得ることがある$T$のほうが何かと都合がよいのです。
これがショートカット形式$T$を採用する理由です。

先の例の$n=7$の場合ですと、$n=7,t=3$で、

$$T^3(7)={\left({\displaystyle \frac{3}{2}}\right)}^3(7+1)-1=26$$

となり、この例では確かに正しいことがわかりますね。

奇数を連続で得続ける回数

$T^t(n)$は偶数であるとしましたから、$T^t(n)+1={\displaystyle \frac{3^t}{2^t}}(n+1)$ は当然ながら奇数になります。

ということは、${\displaystyle \frac{3^t}{2^t}}(n+1)$という式の分母$2^t$は、式自体が自然数であるために

$(n+1)$と打ち消しあうようにして払われなければならず、

かつ、式は奇数であるために${\displaystyle \frac{n+1}{2^t}}$ は奇数でなければなりません。

このことから、$n+1$ は、素因数$2$をちょうど$t$個もつことがわかります。

さらに，補題１の式では$2$で$t$回割り、$3$を$t$回乗じていることになるため、
$n+1$の素因数$2$を$3$に置き換えれば、$T^t(n)+1$を得られることになります．

また、補題１の式を変形・整理すれば、

$$T^t(n)={\left({\displaystyle \frac{3}{2}}\right)}^t(n+1)-1\Rightarrow {\displaystyle \frac{T^t(n)+1}{n+1}}={\displaystyle \frac{3^t}{2^t}}\Rightarrow n+1:T^t(n)+1=2^t:3^t$$

という比で表すこともできます．

コラッツ予想の計算コストを大幅に削減 ～これで∃●ﾉﾘのTKM先生もﾆｯｺﾘ～

以上のことから、$n+1$の素因数$2$の個数が、偶数を得るまでに行った$T$の合成回数や、その偶数がどんな数かを調べるための手がかりになり、
逆に$n+1$の素因数$3$の個数が、どんな奇数に$T$を何回作用させればその$n$を得られるかを調べるための手がかりにもなるのです。
これにより、関数を合成した後の数を算出する時間を大幅に短縮することが可能となります。
以下で例を挙げます；

どんな時に奇数／偶数を得るか？

自然数$n$に対して$T$を作用させて得た$T(n)$が偶数か奇数かどうかを一般に判別する方法はわかりませんが、
逆に、$n$および$T(n)$の偶奇で、$n$がどのよう数であるかを、$4$で割ったときのあまりで区分することは可能です。

これを表に表すと以下の通り；

このことから、もしコラッツ予想が正しくない数が存在するとして、その最小値$c$は$c\equiv 3\mathrm{mod}4$のため、
$T(c)$は必ず奇数であるとわかります。
また、奇数$n$に対し$T(n)$が奇数かつ$T(\eta )=n$となる奇数$\eta$が存在する場合、
$n\equiv 11\mathrm{mod}12$ であることが導かれます。（証明は割愛）

$T^t(n)$が$2$の冪$2^{\tau }$になるとき

コラッツ予想は、計算の結果が$1$になることが最終目標です。しかしながら途中で$2$の冪にさえなれば、
あとはそこから$2$で割り続けて$1$を得られるわけですから、$2$の冪はコラッツ予想に従うことがわかります。
もしも$T^t(n)$が$2$の冪$2^{\tau }$になった場合の、その指数$\tau$と$n$や$t$の関係性について調べてみましょう。

$t$と，$2^{\tau }$の冪指数$\tau$の関係

以上，$t$と$\tau$の関係が分かるのですが，では$\tau$自体は一体どんな数になるでしょうか。
それを考えるにあたり、次でいくつか補題を扱います。

$\tau$ってどんな数？ ～下準備～

$t=1$から$5$まで実際に確認してみると、

$$\begin{array}{llll}t=1\mathrm{の}\mathrm{と}\mathrm{き}& 2& =3\cdot 1-1& \equiv -1\mathrm{mod}3\\ t=2\mathrm{の}\mathrm{と}\mathrm{き}& 8& =9\cdot 1-1& \equiv -1\mathrm{mod}9\\ t=3\mathrm{の}\mathrm{と}\mathrm{き}& 512& =27\cdot 19-1& \equiv -1\mathrm{mod}27\\ t=4\mathrm{の}\mathrm{と}\mathrm{き}& 134217728& =81\cdot 1657009-1& \equiv -1\mathrm{mod}81\\ t=5\mathrm{の}\mathrm{と}\mathrm{き}& 2417851639229258349412352& =243\cdot 9950006745799417075771-1& \equiv -1\mathrm{mod}243\end{array}$$

となります。最後のほうエグいですね。読みますか？
2杼[ｼﾞｮ] 4178 垓[ｶﾞｲ] 5163 京[ｹｲ] 9229兆 2583億 4941万 2352 です。もう人が現代社会で扱う領域を超えている。
この補題は数学的帰納法を用いて証明できます。やってみてね。
もっと言うと、合同式は両辺を累乗しても合同関係は成り立つわけですから、
奇数$p$を用いて　$2^{3^{t-1}p}\equiv -1\mathrm{mod}{3}^t$　が成り立つことも分かります。
この合同式の左辺を移項すれば、

$$2^{3^{t-1}p}+1\equiv 0\mathrm{mod}{3}^t$$

となります。このことを用いて何をしたいかは、勘のいいガキ鋭い方であればもうお分かりですね。

証明しよう 間違いのないように (♪ ～ ﾁｭｰﾘﾝｸﾞﾗﾌﾞ～)

そうです。補題2の条件下で上記の合同式が成り立っていてくれれば，
$\tau$は一定の式で表すことができるのです。なんて素晴らしい。
ようは$\tau =3^{t-1}p$であってくれれば良いのです。
しかし，これを何の証明もなしに使うことは許されません。
$\tau$を他の表し方でしか表せない場合が存在するかも知れない。
もしかすると$\tau$が偶数になる場合が存在するかもしれない。
その可能性を潰し、上記の式ただ一通りに表すことが許されるよう、次の補題を扱います；

これも数学的帰納法を用いて証明が可能です。
（長ったらしいので、面倒な人は「ﾊｲﾊｲ､証明できるんですね」程度に思って読み飛ばしてもらって大丈夫です）

ふでやすめ

ここまでお読みいただきありがとうございます。そしてお疲れ様です。
「あれ、何を考えているんだったっけ？」
と忘れかけてしまっている方のために、
ここで改めて周知します。

ショートカット形式$T$を自然数$n$に作用させ、
「連続で奇数を得続け、$t$回目で初めて偶数を、しかも$2$の冪$2^{\tau }$を得た」
ことを考えるにあたり，$2^{\tau }$の指数$\tau$はどんな数なのか？

ということを調べていました。ここまでの証明でほぼ答えは出ているのですが、次でまとめに入ります。

$\tau$ってどんな数？ ～まとめ～

証明は前述の通りです．

例を挙げてみましょう。

はい、ちゃんと一定の式で表せることがわかりました。

コラッツ予想、一部解明？

具体的な自然数$n$から$\tau$の値を導き出せたならば、その逆もできますね。

　定理ってほどじゃないですが…。　証明は、これまでの議論を用いて$T^t(n)$から逆算すれば明らかです。
前述の$n=151$の場合でも $t=3,\tau =9(p=1)$から導くことができます。

<!!--

$2$の冪じゃなくて、一般の偶数について考えたい！

本題はここから

　本来はこちらが議論の主題です。といいますのも、そもそも計算のスタートは最初に選んできた奇数$n$です。
そこから$t$および$T^t(n)$と$\tau$の値が決まるわけですから。
　先の$2$の冪になる場合の議論では、最終的に「$T^t(n)=2^{\tau }$になる$n$はいくつでしょう」というお話でした。例に挙げた自然数$n$も、あくまで$T^t(n)$の計算結果が$2$の冪になる$n$の値を選んだに過ぎず、平たく言えば$2$の冪に対する忖度です。
「あ！$n=151$としたら$T^t(n)$が$2^{\tau }$になったぞぉ～！（すっとぼけ）」
という具合に。
よっぽどの偶然でも起きない限り、$T^t(n)$の値が$2$の冪になることはないでしょう。

$n⟶$偶数$⟶\overline{n}$を得るまで

　先ほどは$T^t(n)=2^{\tau }$となる場合について考えましたが，次は$2$の冪ではない一般の偶数について話を広げます。
つまり，$T^t(n)=2^{\tau }\overline{n}$となる奇数$\overline{n}$がある場合です。$\overline{n}=1$のときはまさしく$T^t(n)$が$2$の冪になる場合ですね。
次は無作為に奇数$n$を選んだときの$t$および $T^t(n)=2^{\tau }\overline{n}$となる$\tau ,\overline{n}$の値を考えてみましょう。

$n$の表し方

　ところで、$n$から$T^t(n)$を得るのにあたり、$n+1$の素因数$2$を$3$に置き換える操作が入るわけですが、
なぜそのような操作が必要とされることになったのでしょうか？これは実際に計算で確かめてみる他ありません。
$n+1$から素因数$2$を分離して表すと、$m$を奇数として$2^{t}m$となります。
$n=2^{t}m-1$ を$T(n)$に代入して得る数は

$$T(n)={\displaystyle \frac{3(2^{t}m-1)+1}{2}}=2^{t-1}3m-1$$ ですね。

この式のとらえ方として、「$n$の第$1$項の素因数$2$の指数が$1$つ減り、$3$が$1$つ増えた」とみなすことができます。
$t$が十分大きければ、この$T(n)$も奇数です。もう一度$T$を作用させてみると、

$$T^2(n)=T(2^{t-1}3m-1)={\displaystyle \frac{3(2^{t-1}3m-1)+1}{2}}=2^{t-2}{3}^{2}m-1$$ となります。

つまるところ$T(\cdot )$の操作というのは、「作用前の式の第$1$項の素因数$2$の指数を$1$つ減らし、$3$を$1$つ増やす」
ことと全く同じなのです。これが可能な回数が$t$回のため、「$n+1$の因数$2$を$3$に置き換える」ことで、
$T^t(n)$を得ることができるのですね。
このことから、$n=2^{t}m-1$という表し方は、コラッツ予想を考えるにあたって有効な手段だと思われます。
ちなみに、前述の注意と同様の理由で、奇数$m$には因数$3$が含まれていないものと考えてください。

　さて、コラッツ予想の（ショートカット形式の）操作は$n$からスタートし、
$T^t(n)={\left({\displaystyle \frac{3}{2}}\right)}^t(n+1)-1=2^{\tau }\overline{n},T^{\tau }(2^{\tau }\overline{n})=\overline{n}$　で、次の奇数$\overline{n}$を得るまでがワンセット。

$($$T(n)$は$n$が偶数の時に$2$で割る関数であることをお忘れなく…$)$
　この$\overline{n}$に当てはまる数が$1$になったとき、$n$に関してコラッツ予想は正しいといえます。
では、途中で得る偶数の$2^{\tau }\overline{n}$について、$\tau$や$\overline{n}$はどんな値になるでしょうか。
先ほどのように$\tau =3^{t-1}p$ だと嬉しかったのですが、そう都合よく上手くいくものではありません。
どうにかして$n=2^{t}m-1$と$T^t(n)=2^{\tau }\overline{n}$の間に別の繋がりを見つけられないものでしょうか。
　ここからは、手探りで試行錯誤をしている状態のものをプロトタイプとして記述していきます。

スタートの$n$に制限を持たせる

　これまで口酸っぱく述べたこととして、前述の$n=2^{t}m-1$で$m$は因数に$3$を持たないかどうか、つまり$3$の倍数でない奇数かどうかに注意を向けておりました。なぜ$3$を気にしているか、ここで改めて詳しくお話しします。

$T^t(n)$を得るまでの通過点の奇数と見なされる

　ここで仮に$n=2^{t}m-1$の$m$が素因数$3$を持つとしましょう。奇数$\mu$を用いて$m=3\mu$ と表せますので、
$n=2^{t}3\mu -1$ です。これは前述の"操作"に基づいて考えれば、$T(2^{t+1}\mu -1)=n$と考えることはできませんか？
このように、$m$が$3$の倍数であった場合、$T$を作用させて奇数$n$を得るような奇数が存在することになるため、
$T^t(n)$を得るにあたり、スタートに代入する奇数として$n$と$2^{t+1}\mu -1$のどちらを入れて考えても、
$T^{t+1}(2^{t+1}\mu -1)=T^t(n)$となって変わらないよね、となるわけです。
　逆に$m$が$3$の倍数にならないようにしてスタートするとき、$T$を作用させて$n$を得るのに入れる数は偶数$2n$しかありません。このようなとき、$n$は$3$で割ったときのあまりが$0$か$1$となるような奇数です。
そして、前に述べた表から、

$n$が$4$で割ると$1$あまる数$\Rightarrow T(n)$は偶数で、
$n$が$4$で割ると$3$あまる数$\Rightarrow T(n)$は奇数となります。

これを表に表すと以下の通り；

コラッツ予想に従わない数が存在するとき、その最小は$4$で割って$3$あまるので、
考えるべき数は、表の下の段の$2$つになります。