コラッツの問題の操作から得られるディオファントス方程式の解について

何かと話題のコラッツ予想について、いじってみた結果をまとめます。

コラッツ予想は、非常に簡単に見える予想でありながら、今のところ誰も解いていない問題となっています。
なぜか高額な懸賞金も掛けられ、アマチュア数学者でも証明にチャレンジしている人は多いかと思います。

私は数学の非専門家で、高校数学以下の知識しかない人間ですが、なんとなく面白い整理の仕方が見つかったので、そちらをまとめてみようと思います。

指摘やアドバイスは大歓迎なので、何かあればコメントをお願いします！

なお、本記事の内容は、 以前Qiitaに書いた内容 を整理したものになります。

基本情報

コラッツ予想とは

自然数$n \geq 1$について、以下の操作を繰り返すと、必ず$1$に辿り着く($1$から$4$の間をループする)という予想です。[1]

• $n$が偶数の場合、$2$で割る。
• $n$が奇数の場合、$3$倍し、$1$を足す。
• 上記の結果を新たに$n$とする。

2023年11月現在、未解決の予想となっています。
もともとポール・エルデシュにより500ドルの懸賞金が掛けられていました。(小切手は現在も管理されているようです)
2021年7月、株式会社音圧爆上げくんにより、さらに1億2000万円の懸賞金が掛けられました。[2]

重要な進展

• $ 2^{68} $まではコンピューターにより予想が成り立つことが検証されているようです。[3]
• テレンス・タオにより、「コラッツ写像のほとんどの軌道は、ほぼ有界な値に達する」ことが証明されました。[4]

コラッツの問題の操作を数式で表現する

2つの操作を繰り返した結果が$1$に辿り着く、というのは、等式で表すと以下の通りになります。
$3n + 1$が3回発生し、$2$で割るタイミング(各タイミングで、$2$で割れるだけ割る)が4回あった場合を考えます。
$n$を初期値とし、$a,b,c,d$をそれぞれ$3n + 1$の後に$2$で割った回数とします。

$$ 2^{-d}(3 \cdot 2^{-c}(3 \cdot 2^{-b}(3 \cdot 2^{-a}n + 1) + 1) + 1) = 1 $$

この式を展開します。

$$ 3^{3} \cdot 2^{-(a + b + c + d)}n + 3^{2} \cdot 2^{-(b + c + d)} + 3 \cdot 2^{-(c + d)} + 2^{-d} = 1 $$

両辺に$2^{a + b + c + d}$を掛けます。

$$ 3^{3}n + 3^{2} \cdot 2^{a} + 3 \cdot 2^{a+b} + 2^{a+b+c} = 2^{a + b + c + d} $$

係数の$3$に指数を補ってみます。

$$ 3^{3}n + 3^{2} \cdot 2^{a} + 3^{1} \cdot 2^{a+b} + 3^{0} \cdot 2^{a+b+c} = 2^{a + b + c + d} $$

このように変形すると、コラッツの問題の操作は、ある自然数$n$に$3$のべき乗を掛け($3^{3}n$)、$3$のべき乗($3^{2}$～$3^{0}$)をビットシフト($2^{a}$)して足し合わせ、$2$のべき乗を作る、という操作だと見なせます。

(なお、$a,b,c,d \dots$には一定の制約があります。
まず、$n$が奇数の時に行う$3n + 1$は必ず偶数になるので、どの$a,b,c,d \dots$も$1$以上になります。
さらに、コラッツの操作の逆を$1$から行った場合を考えると、例えば$d$は$4, 6, 8, \dots$のいずれかになります。
後続の変数も先行する変数により制約を受けます)

上記の式は、$a,b,c,d$を変数とした指数型ディオファントス方程式と見なすこともできます。

もしコラッツ予想が肯定的に解かれたとしたら、すべての自然数$ n \geq 1 $について、
$n$に応じた適切な数の項を持つ上記の形の指数型ディオファントス方程式は、解をもつことになります。

ベクトルの内積の形で書き換える

線形代数との関連は不明ですが、先ほどの式はベクトルの内積の形で見やすくなるので、書き方を変えてみます。

$3$の次数の昇順に項を並び替えます。

$$ 3^{0} \cdot 2^{a+b+c} + 3^{1} \cdot 2^{a+b} + 3^{2} \cdot 2^{a} + 3^{3}n = 2^{a + b + c + d} $$

$2$のべき乗および$n$と$3$のべき乗にベクトルを分けてみます。

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

考察

コラッツの問題の操作は、自然数$n \geq 1$について、ディオファントス方程式

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

のうち解となるものを探しに行くアルゴリズムと見なすことができます。

ディオファントス方程式の可解性を調べる問題はふつう非常に難しいそうなのですが、
コラッツの問題では、いとも簡単に解を見つけ出しているように見えます。

一般的には、ディオファントス方程式の可解性を調べるアルゴリズムは決定不能であることが知られています。(ヒルベルトの第10問題の証明による)[5]

すべての$n$について解を持つ方程式があるかについても、証明は難しいように思います。
(証明出来たらコラッツ予想が解ける？)
巨大な$n$については、もしかしたらどれだけ項を増やしても解が無いかもしれません。
また、個別の$n$については判定でき、どれもアルゴリズムで求められるのに、$n$全体については決定不能である場合も考えられます。

感覚的な理解

しっかりした証明は難しいですが、アルゴリズムで解が探せる理由は感覚的には捉えられます。
$n$を2進数のビットパターンと考えると、コラッツの操作ではそのビットを$3n + 1$で消していく手順を行っていると見なせます。

先ほどの方程式の見方では、$3$のべき乗のビットパターンを下位ビットから当てていき、上位ビットに$1$を集めて、最後にまとめて$3^{0} = 1$で倒して$2^{a + b + c \dots }$にしている、と見ることができます。

足し算は、ビット演算で見ると、下位ビットの$1$を倒し、桁上がり(キャリー)で上位ビットの$0$に移動させていく、という操作なので、下位ビットに当たるように数を足していけば、上位へビットが高密度に集まって、やがては$2^{a + b + c \dots} - 1$(メルセンヌ数)になり、最後の$1$を加えて$2^{a + b + c \dots}$になっています。

問題は、$3$のべき乗のビットパターンで必ずメルセンヌ数にできるのか？ という点です。
$n$に掛ける$3^{t-1}$($t$は項の数)を大きくしていくと、$n$に関わらず、ビットパターンは$3^t$によるものが支配的になります。
$3^{t-1}$のビットパターンは、無理数($\log_{2}3$)が関わっていて、基本的に予測ができません。周期性も無いと思われます。
その予測ができないパターンについて、$3$のべき乗のビットパターンを当てることによりメルセンヌ数(をビットシフトしたもの)が作れる、という性質を証明する必要があります。

今後の展望

コラッツの問題をいじっていて色々面白そうなものが見えてきたので、関連するトピックには興味が湧いてきました。
以下のような内容に触れられるようになってみたいです。

• テレンス・タオの証明[4]
  • 現在のところ人類がもっとも証明までたどり着いた地点だと思われます。この手法を発展させることで証明できるかも？
• ヒルベルト第10問題の証明
  • 指数型ディオファントス方程式をディオファントス方程式の組に直したりできるようです。また、ディオファントス方程式でチューリングマシンをエンコードできるというのも凄すぎます。
• 楕円曲線論
  • フェルマーの最終定理のように、楕円曲線の有理点の問題になったりしないでしょうか……。
• ディオファントス幾何学
  • 何か関係あるのかなと思いつつ、入門するだけで一生掛かりそうです……。