22

コラッツ予想に関する予想の提案

4388
1
$$\newcommand{bm}[0]{\boldsymbol} \newcommand{o}[2]{\ordi{#1}{#2}{}} \newcommand{ok}[2]{\ordi{}{#1}{#2}} \newcommand{ordi}[3]{\frac{d #1^{#3}}{d #2^{#3}}} \newcommand{p}[2]{\part{#1}{#2}{}} \newcommand{part}[3]{\frac{\partial #1^{#3}}{\partial #2^{#3}}} \newcommand{pk}[2]{\part{}{#1}{#2}} \newcommand{Q}[0]{\mathbb{Q}} \newcommand{Res}[0]{\operatorname{Res}} $$

はじめに

どうもこんにちは、🐟️🍊みかん🍊🐟️です。今回はCollatz予想に関する非常に強い予想について話していこうと思います。個人的には非常に興味深い主張です。この予想を、現在仮として「Collatz有界予想」とよんでいます。

Collatz予想は、本稿執筆時点で未解決、あるいは解決されたという数学界のコンセンサスが得られていない主張であり、近年ではTerence Taoにより「殆ど全ての正整数においての成立」を証明されています。ヒューリスティクス的思考でも「正しそうだ」という感じがしていて、多くの数学に興味を持つ人は「恐らく正しいであろう」という考えを持っていることと思います。Wikipediaによると、Collatz予想は1930年代頃にCollatzにより考え出された予想で、Fermat最終定理同様「小学生でも理解できる」予想になっています。なおこの記事では、Collatz変換を

$$ c(n)= \begin{cases}\frac n2&\mathrm{if}\ 2|n\\3n+1&\mathrm{otherwise} \end{cases} $$

で定義し、その$k$回合成を$c^{(k)}$で表すことにします。

コラッツ有界予想の提案

そもそも、Collatz予想とは次のようなものでした。

Collatz予想

いかなる正整数$n$に対しても、ある自然数$k$が存在して

$$ c^{(k)}(n)=1 $$

ならしめうるであろう。

これは次の主張と明らかに同値です。

Collatz予想(変形版)

いかなる正整数$n$に対しても、ある自然数$k$が存在して

$$ c^{(k)}(n)< n $$

ならしめうるであろう。

このCollatz予想で遊ぶ上で、私はこの$k$を固定して考えたときの$c^{(k)}$の挙動に興味をもちました。特に$k=n$として考えることで得られるこのCollatz有界予想は、$c^{(n)}(n)$の挙動について次のような主張をします。

Collatz有界予想

いかなる正整数$n$に対しても、$c^{(n)}$は有界であろう。特に、

$$ c^{(n)}(n)\le7288 $$

となるであろう。

ちなみに等号成立は$n=63$で起こります。因みにこの予想はもっと精緻化する余地があります(具体的に有界でないような$k$の取り方の限界はどれくらいのオーダーであるのか、ect)が、下手に$k=\lfloor\sqrt n\rfloor$にするよりは見た目がきれいかな、と思いこの形式で書かせてもらいました。

この主張を認めれば、現在行われている数値計算を鑑みれば直ちにCollatz予想を得ますが、逆は恐らく不可能であると考えられます。ここからは、この予想を得た経緯について話していきます。

発想

元をたどれば約一年前、当時高校二年生の頃でした。一学期の期末試験終了後、友人と僕とがCollatz予想で遊び始めるという出来事が起こり、$c^{(n)}(n)$の挙動がどうなるかに僕が興味を持ちました。後日彼にcomputingして貰ったところ、非常に興味深い結果となりました。当時のコードを僕が記憶していないというのもあり、昨日僕が書いたコードと実行結果を添付したいと思います。コードは以下の通りです。

      import math
def c(n, steps):
    num = n
    for _ in range(steps):
        if n == 1:
            break
        if n % 2 == 0:
            n //= 2
        else:
            n = 3 * n + 1
        num = n
    return num

def main():
    try:
        n = int(input("自然数を入力してください:"))
        max = 0
        if n <= 0:
            raise ValueError("自然数を入力してください")
        for i in range(1, n+1):
            ulam = c(i, i)
            if ulam > max:
                max = ulam
                print([i,max])
        print("end")
    except ValueError as e:
        print("エラー:", e)
if __name__ == "__main__":
    main()
    

このようにコードしたのは、要するに「記録が更新」されているところのみを考えれば有界性を考察する上では十分であろう、ということによります。興味かおありでしたら、適当にmainのコードを書き換えてあげればいろいろCollatz予想で遊べると思います。

n=1000000として実行したときの結果が以下の通りになります。

[1, 1] [3, 16] [9, 26] [27, 466] [31, 1186] [47, 1276] [62, 2429] [63, 7288] end

どうでしょうか。「成立する」というには根拠不足が過ぎますが、なんとなく「そうなりそう」な気がしてきませんか...?彼がプログラムして計算したときには私もその隣で実行結果を見ていて、そのときは予想だにしなかった結果に驚きを分かち合った思い出があります。

おわりに

どうであったでしょうか。この「Collatz有界予想」は、大雑把にいえばCollatz写像の合成による減少速度が引数の増大速度を上回ることを予想していますが、当然Collatz予想よりも強い予想であると考えられます。僕のような数弱には予想をたてることしかできませんが、少しでも皆様の興味を惹けたのでしたら幸いです。読んでいただきありがとうございました。

おまけ

話に$k=\lfloor\sqrt n\rfloor$を出してしまったので、このときの予想だけ語ります。

Collatz有界予想

いかなる正整数$n$に対しても、$c^{(\lfloor\sqrt n\rfloor)}$は有界であろう。特に、

$$ c^{(\lfloor\sqrt n\rfloor)}(n)\le3830704 $$

となるであろう。

これは$n=8510$での等号成立を想定しています。しかし、$k=\lfloor\ln n\rfloor$としたときは有界ではありません。これは$k=\lfloor\operatorname{lc} n\rfloor$のときを考えて、特に$c^{(k(10^n))}(10^n)=5^n$であることを考えれば殆ど明らかです。従って、(連続体仮説を仮定すれば)$k$のオーダーは代数関数程度になるだろうことが分かります。

今後の展望としては他の代数関数でも有界性あるいは上限の候補値を調べてみること、非有界なる場合における発散速度のオーダーを調べることなどが挙げられますが、ここでそれらの予想を明言するのは(目的を逸脱する恐れがあるので)避けることにし、この記事はここで締めようと思います。最後まで読んでいただきありがとうございました。

投稿日:2023721
OptHub AI Competition

この記事を高評価した人

高評価したユーザはいません

この記事に送られたバッジ

バッジはありません。

投稿者

級数

コメント

他の人のコメント

コメントはありません。
読み込み中...
読み込み中