コラッツ予想

コラッツ予想の規則を写像として書くと、

1回の飛行は$n$から始まり、$f(n)$、$f(f(n))$……と進み、1に到達すると終わります。その先は1 → 4 → 2 → 1を巡るだけだからです。予想は、すべての正の整数がそこに到達すると述べています。ここでは整数を1つずつ、または群れで飛ばせます。数百桁の整数でも構いません。予想をもっともらしく感じさせる大まかな議論と比べ、その議論がなぜ証明ではないのかを見られます。

横軸はステップ数、縦軸は値で、通常は対数目盛りです。元の値を選ぶと、おなじみの雹のように上下する図になります。群れの各数は色付きの線なので、多くの数が通る区間ほど色が強くなります。暗い背景では明るく、明るい背景では濃くなります。見ている数は強調表示され、現在位置には赤い点が付きます。飛行の予測は難しく、27は9,232まで上がり、1に着くまで111ステップかかるのに、28は18ステップです。

なぜ信じられているのでしょうか。奇数のステップは必ず偶数を生むので、その直後の2で割る操作とまとめて1回の短縮ステップと数えます。ここで各ステップの偶奇を、偏りのないコインを独立に投げた結果だと仮定します。半分の確率で$n$はおよそ3/2倍に、残り半分で1/2倍になるので、短縮ステップ1回による$\ln n$の平均変化は

となります。このモデルなら数は小さくなり、典型的には短縮ステップ2回ごとに3/4倍になります。対数軸上の破線がこの傾向を示し、同程度の大きさで100個以上の群れに対して描かれます。ただし着地は考慮していません。1に到達した数は底にとどまるので、終わりに近づくと、この軸上での群れの平均の高さは破線よりゆっくり下がります。

コイン投げは、数が平均的にどう振る舞うかを表すモデルにすぎません。予想が述べているのはすべての正の整数についてであり、1に決して到達しない飛行が1つでもあれば反例になります。

負の数は、この議論が見落とすものを示します。同じ規則を負の数に使うとループができ、−5 → −14 → −7 → −20 → −10 → −5など3つが知られています。コイン投げのモデルはそこでも縮小を予測しますが、どのループも1周すると$\log|n|$の変化はちょうど0です。平均的に下がる傾向があってもループは排除できず、正の数でも同じです。

サンゴは飛行を逆向きにします。1から逆に伸ばすと、群れの経路は木になります。新しい数が偶数なら各辺は前の辺から$+\alpha$、奇数なら$-\alpha \log_2 3$だけ曲がります。αは曲げ角で設定します。1から逆に進むと、偶数のステップは数を2倍にして、その$\log_2$を1増やします。奇数のステップはそれを$\log_2 3$より少し多く減らします。したがってnに到達する辺の向きは、真上から合計$\alpha \log_2 n$だけ回り、さらに奇数のステップごとに少し加わります。つまり回転角にnの大きさが記録されます。枝に沿って方向は1回の飛行の数とともに上がったり下がったりするので、各枝は飛行を巻いたものです。飛行が合流するところで枝も合流します。この表現では、予想は1から伸ばした木がすべての正の整数を含む、と述べています。

この問題は一般に、1930年代にこの種の問いを考えたロタール・コラッツに帰されています。サンゴの描き方はエドマンド・ハリスの「Collatz seaweed」（2016年）に基づいています。