プログラマー的、雑なコラッツ予想の証明法？

唐突にこれを思い出して、アニメーションが気に入らないのを直した。

https://collatz-conjecture-calculator.netlify.app/

GPTに聞いてみる。

コラッツ予想の証明法で、以下の反証はありますか？

任意の数を2進数のビット列に変換する。

処理１（偶数の時、n÷２は1bit目が1になるまでビットシフトと考える）

処理２（奇数の時、3n+1は1bit目に注目すると、３回ビットが変わる、つまりNOT）

自明１：二進数なので0,1以外は存在しない。

自明２：処理１では、どんな数でも必ず1bit目に1が来る。

自明３：3n+1した結果がどんなビット列であろうが0が存在する限り、列が詰まる（やべー！0を含む確率になってしまった・・・）

自明４：処理２により必ず0が存在する

反証１：これを満たさないビット列は0,1以外で構成された数のみ。

自明４：反証１は自明１により存在しない。

1に収束することが明示的でないが・・・

証明完了？？

テレンス・タオの2019年の論文

背景：Collatz予想とは

• 基本的な操作
  任意の正の整数 $n$ に対し、

  • $n$が偶数なら $n/2$
    

  • $n$が奇数なら $3n+1$
    を繰り返すと、最終的に1に到達する、という未解決の予想です。

• 従来のアプローチ
  多くの数値実験や部分結果はありますが、すべての自然数について1に到達するという完全な証明は得られていません。

---

タオの論文の主な成果

• 「ほとんどすべての整数」についての結果
  タオは、任意の正の整数のうち、例外となるもの（もし存在するとしてもその割合が0）を除けば、ほとんどすべての整数について Collatz の軌道が「ほぼ有界」な値域に入ることを示しました。
  これは、もし Collatz予想が正しいなら「ほとんどの整数の軌道は最終的に1に収束する」とみなせる状況に近いと言えます。

• 「ほぼ有界」の意味
  論文では、どんなに小さな上界 $A$ を取っても、自然数全体の中で、その軌道が最終的に $A$ 以下に落ち込む整数の割合が 1 に近づく、という形で証明されています。
  つまり、例外の可能性がある数はあっても、その集合の自然密度は 0 であるという結果です。

---

使用された手法

• 解析的・確率論的手法
  タオは、Collatz写像の振る舞いをランダムなプロセスに近い形で捉えることで、その長期的な動きを解析しました。
  エルゴード理論や解析的手法、さらには確率論のアイデアを組み合わせ、軌道がある有界な範囲に入る確率を厳密に評価しています。

• 自然数の密度の概念
  「ほとんどすべての整数」という表現は、すべての自然数の中で例外となる数の割合がゼロである（すなわち自然密度1である）という意味です。
  このアプローチは、すべての整数について証明するのが難しい問題に対して、「例外は極めて稀である」ことを示す手法として有効です。

詳しく聞いてみる。

1. Collatz予想とその背景

• 基本的な操作
  任意の正の整数 $n$ に対し、

  • $n$ が偶数なら $n\mathrm{/}2$

  • $n$ が奇数なら $3n+1$
    を繰り返すと、最終的に1に到達するかどうかがCollatz予想の問です。

• 未解決問題としての難しさ
  数値実験では非常に多くの数が1にたどり着いているものの、すべての整数に対してこの性質が成り立つかどうかは、依然として証明されていません。

---

2. 「ほとんどすべての整数」という意味

• 自然数の密度
  ここで「ほとんどすべての整数」とは、たとえば $N$ 以下の整数の中で、この性質（軌道がある有界な領域に入る性質）を持たない整数の数を $N$ で割った極限が0になる、という意味です。
  つまり、もし $A(N)$ を $N$以下で性質を満たさない数の個数とすると、

  $$\lim_{N\to\infty} \frac{A(N)}{N} = 0$$
  

  ということになります。例外は「極めて稀」であり、全体から見れば無視できる、という意味です。

---

3. タオの論文の主張とその手法

• 主張の内容
  タオは、Collatz写像の軌道に対して、確率的・解析的な手法を用いることで、「任意に小さな上界 $A$ をとった場合に、ほとんどの整数のCollatz軌道は最終的に $A$ 以下の値に入る」という結果を示しました。
  これは、もし本当にCollatz予想が正しいならば、例外があったとしてもその割合はゼロになるという見方に対応します。

• 使用された手法の概要

  1. 解析的・確率論的アプローチ
     Collatz写像は、厳密な意味では決定論的な操作ですが、大きな数に対してはその挙動が非常に「ランダム」に見えるため、確率論的な手法で扱うことができます。タオはこの性質を利用して、軌道がどのように動くかを統計的に解析しました。

  2. エルゴード理論や停止時間解析
     数列がどのくらいの速さである有界な領域に入るかを調べるために、停止時間（ある基準値以下になるまでのステップ数）の分布など、エルゴード理論的な考察も応用されました。

  3. 「ほぼ有界」性の証明
     任意の大きな $N$ に対して、ほとんどの $n\le N$ について、Collatz写像の軌道が最終的に非常に小さな値に落ち込む（たとえば、ある固定の $A$ 以下になる）ことを示すことで、例外となる数が自然密度的に0であることを導き出しました。

• この結果の意味
  この証明は、もしCollatz予想が間違っている（つまり、1に収束しない整数が存在する）としても、そのような整数は非常に稀で、全体から見れば無視できる（自然密度0）ということを意味します。
  一方、逆に言えば、「ほとんどすべての整数」については、予想される通りの振る舞い（最終的に有界な領域、ひいては1に近づく）が実現されるということです。

---

4. この結果の意義と今後の課題

• 意義

  • 数学界においてCollatz予想は非常に有名で難解な問題ですが、タオの結果はその中でも「大多数」の場合についての理解を大きく深めたものです。

  • もし例外が存在するとしても、その反例は非常に特殊で稀なものでなければならないことが示され、Collatz予想が「ほぼ正しい」ことを裏付けています。

• 今後の課題

  • なお、タオの論文はすべての正の整数について1に到達することを証明しているわけではありません。

  • 自然密度0の例外が存在する可能性（理論上は無視できるが、厳密に否定されていない）については未解決です。

  • このため、Collatz予想そのものの完全な解決には、まだ残された問題があることになります。

---

まとめ

テレンス・タオの2019年の論文は、Collatz写像における「ほとんどすべての整数」が最終的にある有界な値域に入る、つまり軌道が「ほぼ有界」であることを証明しました。

• 自然数全体の中で、例外となる（軌道が有界にならない）数は極めて稀である（自然密度0）

• これにより、Collatz予想が間違っているとすれば、その反例は全体から見れば無視できるほど小さい集合に限られるという新たな知見が得られました。

この結果はCollatz予想の「全体解決」には至らないものの、これまでの解析とは異なるアプローチで大多数の整数に対する理解を深め、今後の完全な証明に向けた重要な一歩と考えられています。