コラッツ予想ノート

コラッツ予想について

コラッツ予想についていじりまわした結果を記録します。

Wikipedia コラッツの問題

TL;DR

コラッツ予想は、

• ビット列で見ると、一定のルールで下位ビットを消し続けて1にしているように見える。
• 式を色々整理するとディオファントス方程式の形になり、その解があるかどうかの問題になる。
• ディオファントス方程式の可解性を証明するのはやばそう……。しかも初期値によって項の数とか色々変化する……。
• New! フィールズ賞を持つ天才テレンス・タオが、2019年に、ほとんどすべての整数について1となることを証明したとの論文を発表しました。

基本的なこと

コラッツ予想とは

コラッツ予想とは、任意の自然数(0を除く)について、

• 偶数なら、2で割る。
• 奇数なら、3倍して1を足す。

上記を繰り返すと、必ずいつかは 1→4→2→1→4→2→1→4→2→1…… のループに入る、という予想です。

$ 5 \times 2^{60} $まで実際に計算して確かめられているので、おそらく成り立つようなのですが、2018年現在まだ証明も反証もできていないようです。

数学者ポール・エルデシュにより、500ドル の賞金が掛けられていることで有名です。（賞金はまだ管理されているようで、解けば小切手がもらえるようです。参考Wikipedia)

いくつかの例

• 5→16→8→4→2→1
• 11→34→17→52→26→13→40→20→10→5→16→8→4→2→1

27→82→41→124→62→31→94→47→142→71→214→107→322→161→484→242→121→364→182→91→274→1 37→412→206→103→310→155→466→233→700→350→175→526→263→790→395→1186→593→1780→890 →445→1336→668→334→167→502→251→754→377→1132→566→283→850→425→1276→638→319→958→ 479→1438→719→2158→1079→3238→1619→4858→2429→7288→3644→1822→911→2734→1367→4102 →2051→6154→3077→9232→4616→2308→1154→577→1732→866→433→1300→650→325→976→488→24 4→122→61→184→92→46→23→70→35→106→53→160→80→40→20→10→5→16→8→4→2→1

とりあえず言えること

• 数字の大小と1になるまでのステップ数にそれほど関連がない。
• 1に到るまでの数は大きくも小さくもなる。
• ステップを繰り返すうちに数が合流していき、最終的に$ 2^n $になって1になる。
• 奇数のとき$3n + 1$ということは$3(2n + 1) + 1 = 6n + 4$、これは偶数のためすぐ$3n + 2$になる。つまり、実際は奇数のとき$\frac{3n + 1}{2}$されている。

コラッツ予想を2進数で見る

コラッツ予想での処理の様子は、2進数で見るととても直感的です。
コラッツ予想の各ステップは、2進数ビット列に対する下記の処理に言い換えられます。

• 先頭ビットが立っていない場合(0の場合)
  • 1桁右シフト
• 先頭ビットが立っている場合(1の場合)
  • 現在の数と、1桁左シフトした数を足し、さらに1を足す。(2n + n + 1 = 3n + 1)

例

5 = 101

1:   101
2: 10000 (101 + 1010 = 1111, 1111 + 1)
3:  1000
4:   100
5:    10
6:     1

書くのが面倒なので、2進数の桁の方向を逆（左から右）にします。

11 = "1101"

 1: 1101
 2: 010001
 3: 10001
 4: 001011
 5: 01011
 6: 1011
 7: 000101
 8: 00101
 9: 0101
10: 101
11: 00001
12: 0001
13: 001
14: 01
15: 1

この処理の様子は、以前に可視化を行いました。

以下の様子が見て取れます。

• 立っているビットの多いメルセンヌ素数のような数ほど、1になるまで時間が掛かりそう。
• 初期値として用意されたビットを消費し尽くすと、$3^n$で作られたランダムなビットの処理になる。
• $3^n$で作られたランダムなビットは密度が低いので、比較的早く処理されてしまう。
• 0を消す処理を無視すると、立っているビットの列をどんどん高位に追い詰めて、最終的にビットが1つだけの$2^n$の数にしてしまっているように見える。

証明に向けた妄想

初期値に何を与えても、最終的には$3^n$が作り出す2進数のビット列が現れることになります。

もし$3^n$が作り出すビット1の密度が一定以上高くならないと証明できたら、$3n+1$でのビットの処理速度(1ステップあたり平均2ビット)を超えて数が伸びることができず、最終的には必ず1になってしまうことになります。

$3^n$が作り出すビットの密度が高くないことは、見た限りは明らかに思えますが、未来永劫絶対にそんな密度の高いビット列は出てこないというのを証明するのは難しい気がします。
$3^n$のビット列のパターンは基本的には$\log_2 3$に依存していて、つまり無理数に基づいています。

無理数のビット列の密度はどの程度予測できるものなのでしょうか……。

もし密度が一定以上高い領域が現れるとしたら、その部分を盾にしてビット列は伸びることができます。そのビット列が現れるまでの十分に長いビット列を初期値に与えれば、密度の高い部分を周期的に出現させることで、1に収束することを阻止できるかもしれません。

別の見方をすれば、ビット列で巧妙にプログラミングすることで、1になることを阻止できる可能性があることになります。ビット列をプログラムのコードと見なせば、$ 5 \times 2^{60} $(たかだか8バイトのソースコード……)などまだまだ短くて、少しも可能性を試していないことになります。

コラッツ予想を逆から見る

コラッツ予想の操作

• 偶数なら、2で割る。
• 奇数なら、3倍して1を足す。(偶数になるので、続けて2で割る)
• 上記の繰り返しで最後には1になる。

の逆を考えると、1から始めて、

• 2倍する。
• 以下の場合は、続けて1引いて3で割ってよい。
  • 1引いた数が3で割り切れる。
  • 1引いて3で割った数が奇数になる。

コラッツ予想が肯定的に証明されるなら、この繰り返しで全ての自然数が網羅できることになります。

数式で表すと、下記のような感じになります。

\begin{align}
&1 \\
&1 \cdot 2^a \\
&3^{-1}(1 \cdot 2^a - 1) \\
&2^b3^{-1}(1 \cdot 2^a - 1) \\
&3^{-1}\{2^b3^{-1}(1 \cdot 2^a - 1) - 1\} \\
&2^c3^{-1}\{2^b3^{-1}(1 \cdot 2^a - 1) - 1\} \\
\end{align}

この数式が、任意の自然数$x$と一致することになります。
最後の式を例に整理してみます。

\begin{align}
&2^c3^{-1}\{2^b3^{-1}(1 \cdot 2^a - 1) - 1\} &\\
&2^{b+c}3^{-2}(1 \cdot 2^a - 1) - 2^c3^{-1} &(2^c3^{-1}を分配)\\
&2^{a+b+c}3^{-2} - 2^{b+c}3^{-2} - 2^c3^{-1} &(2^{b+c}3^{-2}を分配)\\
&3^{-2}(2^{a+b+c} - 2^{b+c} - 2^c3^1) &(全体を3^{-2}で割る)
\end{align}

この式が$x$と等しくなります。

x = 3^{-2}(2^{a+b+c} - 2^{b+c} - 2^c3^1)

上記の両辺を$3^2$します。

\begin{align}
3^2x &= 2^{a+b+c} - 2^{b+c} - 2^c3^1 &\\
2^{b+c} + 2^c3^1 + 3^2x &= 2^{a+b+c} \quad &(移項)
\end{align}

これは結構面白い式だと思いました。
$a,b,c$は続けて2倍した回数、つまり、各操作の繰り返しの中で連続して2で割った回数です。
$3^2,3^1$は、$3n+1$した回数になります。

要するに、任意の自然数と、それを各操作で$3n+1$した回数・2で割った回数を合わせて上記の式を作ると

2^{2で割った回数の合計}

になる、ということです。

ベクトルとその内積の形で、より見やすく整理できます。

2^{a+b+c} = (2^{b+c}, 2^c, x) \cdot (3^0, 3^1, 3^2)

$3n+1$の回数に応じて、式は以下のように変わっていくことになります。

\begin{align}
2^{a} &= (x) \cdot (3^0) \\
2^{a+b} &= (2^b, x) \cdot (3^0, 3^1) \\
2^{a+b+c} &= (2^{b+c}, 2^c, x) \cdot (3^0, 3^1, 3^2) \\
2^{a+b+c+d} &= (2^{b+c+d}, 2^{c+d}, 2^d, x) \cdot (3^0, 3^1, 3^2, 3^3) \\
&\cdots
\end{align}

コラッツ予想が成り立つとすると、以下のように言えることになります。

• 任意の自然数について、上記の式の中に必ず整数解を持つものがある。
• かつ、その整数解は唯一の解である。 (ある数から1になる経路が1つしかないため。2つあるとすると、数が偶数でも奇数でもあることになってしまって矛盾)

ただし、$a,b,c$は1引いて3で割る必要がある関係で、一定の制約があります。(各文字に入れられるのが偶数または奇数のみとなるはず)

証明に向けた妄想

2^{b+c} + 2^c3^1 + 3^2x = 2^{a+b+c}

のような式の整数解を探すのは、指数型ディオファントス方程式の整数解を探す問題になりそうです。

ディオファントス方程式の整数解を探すのは、調べた限りだいぶやばそうです。

Wikipedia: ディオファントス方程式

大数学者ヒルベルトが20世紀初頭に提起した23の問題の第10問題として、ディオファントス方程式が整数解を持つか否かを有限的に判定する方法を挙げていますが、リンク先に書いてあるとおり否定的に解決されています。

ヒルベルトの第10問題については、こちらにとても面白いページが公開されていました。

ヒルベルトの第１０問題

そもそも、$x^n+y^n=z^n \quad (n \geqq 3)$に解があるかどうかすら人類は解くのに360年を要してしまっています。(フェルマーの最終定理)

いっぽうで、

2^{b+c} + 2^c3^1 + 3^2x = 2^{a+b+c}

の形にまとめることで視覚的にはわかりやすくなった部分もあります。すこし変形すると、

2^{b+c} + 2^c3^1 = 2^{a+b+c} - 3^2x

で、$2^{b+c} + 2^c3^1$により$3^2x$の2の補数を作っていることになります。

2^{b+c+d}3^0 + 2^{b+c}3^2 + 2^c3^3 = 3^3xの2の補数

こうして見ると、$3^n$を$2^{b+c+d}$などでスライドさせて、$3^3x$のビットパターンを組み合わせて2の補数を合成しているように思えます。

$3^n$を組み合わせて2の補数を生成しなければならない制約から、$a,b,c,d$などには一定の上限が設けられるように思います。(際限なく$a,b,c,d$を増やしすぎると、各ビットパターンが離れすぎて2の補数が作れなくなります)

もし$x$から$3n+1$する回数の上限($3^n$の上限)が求められれば、それに対応する$a,b,c,d \cdots$の数も決まり、さらにその上限も決められるかもしれません。
そうすれば、任意の$x$について可能なパターンを調べ尽くし、式の整数解が存在するか有限的に確かめられることになります。
その範囲内で必ず整数解が存在するということが証明できれば、コラッツ予想は肯定的に証明されたことになります。

感想

最初にビット列の表現で見始めて、視覚的には1に収束することがなんとなくわかりましたが、いまいち他の数学とどう繋がるのかわかりませんでした。

逆から見たものを数式の形にしたことで、色々な数学の話とつながって、かつ、どうしてコラッツの問題が難しいのか、それが明らかにできた気がしてよかったです。

この先は地道に数学を勉強して、ちゃんとした整数論やベクトル解析やその他諸々の難しい数学の知識を蓄えて再挑戦するほかありません。

そういった勉強の遥かな目標地点として、この未解決問題があってくれて、とても嬉しいです。

(追記)2019年の進捗

グリーン・タオの定理などで有名なテレンス・タオが、ほとんどすべての整数について1になるという証明を2019年9月にarXivに掲載したようです!

arXivのURLはこちらです。
https://arxiv.org/abs/1909.03562

本人によるブログ記事はこちらです。
https://terrytao.wordpress.com/2019/09/10/almost-all-collatz-orbits-attain-almost-bounded-values/

論文の内容はまだまだ理解が至らないですが、これは解決まであと少しなのかも……。